* [Qemu-devel] [PULL v2 1/7] json-streamer: Don't leak tokens on incomplete parse
2016-06-30 13:42 [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30 Markus Armbruster
@ 2016-06-30 13:42 ` Markus Armbruster
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 2/7] qobject: Correct JSON lexer grammar comments Markus Armbruster
` (6 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Markus Armbruster @ 2016-06-30 13:42 UTC (permalink / raw)
To: qemu-devel; +Cc: Eric Blake, qemu-stable
From: Eric Blake <eblake@redhat.com>
Valgrind complained about a number of leaks in
tests/check-qobject-json:
==12657== definitely lost: 17,247 bytes in 1,234 blocks
All of which had the same root cause: on an incomplete parse,
we were abandoning the token queue without cleaning up the
allocated data within each queue element. Introduced in
commit 95385fe, when we switched from QList (which recursively
frees contents) to g_queue (which does not).
We don't yet require glib 2.32 with its g_queue_free_full(),
so open-code it instead.
CC: qemu-stable@nongnu.org
Signed-off-by: Eric Blake <eblake@redhat.com>
Message-Id: <1463608012-12760-1-git-send-email-eblake@redhat.com>
Reviewed-by: Markus Armbruster <armbru@redhat.com>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
qobject/json-streamer.c | 6 ++++++
1 file changed, 6 insertions(+)
diff --git a/qobject/json-streamer.c b/qobject/json-streamer.c
index 0251685..7164390 100644
--- a/qobject/json-streamer.c
+++ b/qobject/json-streamer.c
@@ -20,9 +20,15 @@
#define MAX_TOKEN_COUNT (2ULL << 20)
#define MAX_NESTING (1ULL << 10)
+static void json_message_free_token(void *token, void *opaque)
+{
+ g_free(token);
+}
+
static void json_message_free_tokens(JSONMessageParser *parser)
{
if (parser->tokens) {
+ g_queue_foreach(parser->tokens, json_message_free_token, NULL);
g_queue_free(parser->tokens);
parser->tokens = NULL;
}
--
2.5.5
^ permalink raw reply related [flat|nested] 9+ messages in thread* [Qemu-devel] [PULL v2 2/7] qobject: Correct JSON lexer grammar comments
2016-06-30 13:42 [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30 Markus Armbruster
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 1/7] json-streamer: Don't leak tokens on incomplete parse Markus Armbruster
@ 2016-06-30 13:42 ` Markus Armbruster
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 3/7] checkpatch: There is no qemu_strtod() Markus Armbruster
` (5 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Markus Armbruster @ 2016-06-30 13:42 UTC (permalink / raw)
To: qemu-devel
From: Eric Blake <eblake@redhat.com>
Fix the regex comments describing what we parse as JSON. No change
to the lexer itself, just to the comments:
- The "" and '' string construction was missing alternation between
different escape sequences
- The construction for numbers forgot to handle optional leading '-'
- The construction for numbers was grouped incorrectly so that it
didn't permit '0.1'
- The construction for numbers forgot to mark the exponent as optional
- No mention that our '' string and "\'" are JSON extensions
- No mention of our %d and related extensions when constructing JSON
Signed-off-by: Eric Blake <eblake@redhat.com>
Message-Id: <1465526889-8339-2-git-send-email-eblake@redhat.com>
Reviewed-by: Markus Armbruster <armbru@redhat.com>
[Eric's regexp simplification squashed in]
Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
qobject/json-lexer.c | 19 ++++++++++++++-----
1 file changed, 14 insertions(+), 5 deletions(-)
diff --git a/qobject/json-lexer.c b/qobject/json-lexer.c
index 496374d..af4a75e 100644
--- a/qobject/json-lexer.c
+++ b/qobject/json-lexer.c
@@ -18,11 +18,20 @@
#define MAX_TOKEN_SIZE (64ULL << 20)
/*
- * \"([^\\\"]|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*\"
- * '([^\\']|(\\\"\\'\\\\\\/\\b\\f\\n\\r\\t\\u[0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]))*'
- * 0|([1-9][0-9]*(.[0-9]+)?([eE]([-+])?[0-9]+))
+ * Required by JSON (RFC 7159):
+ *
+ * \"([^\\\"]|\\[\"'\\/bfnrt]|\\u[0-9a-fA-F]{4})*\"
+ * -?(0|[1-9][0-9]*)(.[0-9]+)?([eE][-+]?[0-9]+)?
* [{}\[\],:]
- * [a-z]+
+ * [a-z]+ # covers null, true, false
+ *
+ * Extension of '' strings:
+ *
+ * '([^\\']|\\[\"'\\/bfnrt]|\\u[0-9a-fA-F]{4})*'
+ *
+ * Extension for vararg handling in JSON construction:
+ *
+ * %((l|ll|I64)?d|[ipsf])
*
*/
@@ -213,7 +222,7 @@ static const uint8_t json_lexer[][256] = {
['\t'] = IN_WHITESPACE,
['\r'] = IN_WHITESPACE,
['\n'] = IN_WHITESPACE,
- },
+ },
/* escape */
[IN_ESCAPE_LL] = {
--
2.5.5
^ permalink raw reply related [flat|nested] 9+ messages in thread* [Qemu-devel] [PULL v2 3/7] checkpatch: There is no qemu_strtod()
2016-06-30 13:42 [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30 Markus Armbruster
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 1/7] json-streamer: Don't leak tokens on incomplete parse Markus Armbruster
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 2/7] qobject: Correct JSON lexer grammar comments Markus Armbruster
@ 2016-06-30 13:42 ` Markus Armbruster
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 4/7] qapi: Fix crash on missing alternate member of QAPI struct Markus Armbruster
` (4 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Markus Armbruster @ 2016-06-30 13:42 UTC (permalink / raw)
To: qemu-devel
From: Eric Blake <eblake@redhat.com>
Maybe there should be; but until there is, we should not flag
strtod() calls as something to replaced with qemu_strtod().
We also lack qemu_strtof() and qemu_strtold(), but as no one
has been using strtof() or strtold(), it's not worth complicating
the regex for them.
(Ironically, I had to use 'git commit -n' since checkpatch uses
TAB indents, in violation of its own recommendations.)
Signed-off-by: Eric Blake <eblake@redhat.com>
Message-Id: <1465526889-8339-3-git-send-email-eblake@redhat.com>
Reviewed-by: Markus Armbruster <armbru@redhat.com>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
scripts/checkpatch.pl | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/scripts/checkpatch.pl b/scripts/checkpatch.pl
index c939a32..cf32c8f 100755
--- a/scripts/checkpatch.pl
+++ b/scripts/checkpatch.pl
@@ -2453,7 +2453,7 @@ sub process {
}
# recommend qemu_strto* over strto* for numeric conversions
- if ($line =~ /\b(strto[^k].*?)\s*\(/) {
+ if ($line =~ /\b(strto[^kd].*?)\s*\(/) {
WARN("consider using qemu_$1 in preference to $1\n" . $herecurr);
}
# check for module_init(), use category-specific init macros explicitly please
--
2.5.5
^ permalink raw reply related [flat|nested] 9+ messages in thread* [Qemu-devel] [PULL v2 4/7] qapi: Fix crash on missing alternate member of QAPI struct
2016-06-30 13:42 [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30 Markus Armbruster
` (2 preceding siblings ...)
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 3/7] checkpatch: There is no qemu_strtod() Markus Armbruster
@ 2016-06-30 13:42 ` Markus Armbruster
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 5/7] range: Create range.c for code that should not be inline Markus Armbruster
` (3 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Markus Armbruster @ 2016-06-30 13:42 UTC (permalink / raw)
To: qemu-devel; +Cc: Eric Blake, qemu-stable
From: Eric Blake <eblake@redhat.com>
If a QAPI struct has a mandatory alternate member which is not
present on input, the input visitor reports an error for the
missing alternate without setting the discriminator, but the
cleanup code for the struct still tries to use the dealloc
visitor to clean up the alternate.
Commit dbf11922 changed visit_start_alternate to set *obj to NULL
when an error occurs, where it was previously left untouched.
Thus, before the patch, the dealloc visitor is blindly trying to
cleanup whatever branch corresponds to (*obj)->type == 0 (that is,
QTYPE_NONE, because *obj still pointed to zeroed memory), which
selects the default branch of the switch and sets an error, but
this second error is ignored by the way the dealloc visitor is
used; but after the patch, the attempt to switch dereferences NULL.
When cleaning up after a partial object parse, we specifically
check for !*obj after visit_start_struct() (see gen_visit_object());
doing the same for alternates fixes the crash. Enhance the testsuite
to give coverage for both missing struct and missing alternate
members.
Also add an abort - we expect visit_start_alternate() to either set an
error or to set (*obj)->type to a valid QType that corresponds to
actual user input, and QTYPE_NONE should never be reachable from valid
input. Had the abort() been in place earlier, we might have noticed
the dealloc visitor dereferencing bogus zeroed memory prior to when
commit dbf11922 forced our hand by setting *obj to NULL and causing a
fault.
Test case:
{'execute':'blockdev-add', 'arguments':{'options':{'driver':'raw'}}}
The choice of 'driver':'raw' selects a BlockdevOptionsGenericFormat
struct, which has a mandatory 'file':'BlockdevRef' in QAPI. Since
'file' is missing as a sibling of 'driver', this should report a
graceful error rather than fault. After this patch, we are back to:
{"error": {"class": "GenericError", "desc": "Parameter 'file' is missing"}}
Generated code in qapi-visit.c changes as:
|@@ -2444,6 +2444,9 @@ void visit_type_BlockdevRef(Visitor *v,
| if (err) {
| goto out;
| }
|+ if (!*obj) {
|+ goto out_obj;
|+ }
| switch ((*obj)->type) {
| case QTYPE_QDICT:
| visit_start_struct(v, name, NULL, 0, &err);
|@@ -2459,10 +2462,13 @@ void visit_type_BlockdevRef(Visitor *v,
| case QTYPE_QSTRING:
| visit_type_str(v, name, &(*obj)->u.reference, &err);
| break;
|+ case QTYPE_NONE:
|+ abort();
| default:
| error_setg(&err, QERR_INVALID_PARAMETER_TYPE, name ? name : "null",
| "BlockdevRef");
| }
|+out_obj:
| visit_end_alternate(v);
Reported by Kashyap Chamarthy <kchamart@redhat.com>
CC: qemu-stable@nongnu.org
Signed-off-by: Eric Blake <eblake@redhat.com>
Message-Id: <1466012271-5204-1-git-send-email-eblake@redhat.com>
Reviewed-by: Markus Armbruster <armbru@redhat.com>
Tested-by: Kashyap Chamarthy <kchamart@redhat.com>
[Commit message tweaked]
Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
scripts/qapi-visit.py | 6 ++++++
tests/test-qmp-input-visitor.c | 12 ++++++++++++
2 files changed, 18 insertions(+)
diff --git a/scripts/qapi-visit.py b/scripts/qapi-visit.py
index 70ea8ca..ffb635c 100644
--- a/scripts/qapi-visit.py
+++ b/scripts/qapi-visit.py
@@ -172,6 +172,9 @@ void visit_type_%(c_name)s(Visitor *v, const char *name, %(c_name)s **obj, Error
if (err) {
goto out;
}
+ if (!*obj) {
+ goto out_obj;
+ }
switch ((*obj)->type) {
''',
c_name=c_name(name), promote_int=promote_int)
@@ -206,10 +209,13 @@ void visit_type_%(c_name)s(Visitor *v, const char *name, %(c_name)s **obj, Error
''')
ret += mcgen('''
+ case QTYPE_NONE:
+ abort();
default:
error_setg(&err, QERR_INVALID_PARAMETER_TYPE, name ? name : "null",
"%(name)s");
}
+out_obj:
visit_end_alternate(v);
if (err && visit_is_input(v)) {
qapi_free_%(c_name)s(*obj);
diff --git a/tests/test-qmp-input-visitor.c b/tests/test-qmp-input-visitor.c
index 3b6b39e..1a4585c 100644
--- a/tests/test-qmp-input-visitor.c
+++ b/tests/test-qmp-input-visitor.c
@@ -766,6 +766,8 @@ static void test_visitor_in_errors(TestInputVisitorData *data,
Error *err = NULL;
Visitor *v;
strList *q = NULL;
+ UserDefTwo *r = NULL;
+ WrapAlternate *s = NULL;
v = visitor_input_test_init(data, "{ 'integer': false, 'boolean': 'foo', "
"'string': -42 }");
@@ -778,6 +780,16 @@ static void test_visitor_in_errors(TestInputVisitorData *data,
visit_type_strList(v, NULL, &q, &err);
error_free_or_abort(&err);
assert(!q);
+
+ v = visitor_input_test_init(data, "{ 'str':'hi' }");
+ visit_type_UserDefTwo(v, NULL, &r, &err);
+ error_free_or_abort(&err);
+ assert(!r);
+
+ v = visitor_input_test_init(data, "{ }");
+ visit_type_WrapAlternate(v, NULL, &s, &err);
+ error_free_or_abort(&err);
+ assert(!s);
}
static void test_visitor_in_wrong_type(TestInputVisitorData *data,
--
2.5.5
^ permalink raw reply related [flat|nested] 9+ messages in thread* [Qemu-devel] [PULL v2 5/7] range: Create range.c for code that should not be inline
2016-06-30 13:42 [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30 Markus Armbruster
` (3 preceding siblings ...)
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 4/7] qapi: Fix crash on missing alternate member of QAPI struct Markus Armbruster
@ 2016-06-30 13:42 ` Markus Armbruster
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 6/7] qapi: Simplify use of range.h Markus Armbruster
` (2 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Markus Armbruster @ 2016-06-30 13:42 UTC (permalink / raw)
To: qemu-devel
From: Eric Blake <eblake@redhat.com>
g_list_insert_sorted_merged() is rather large to be an inline
function; move it to its own file. range_merge() and
ranges_can_merge() can likewise move, as they are only used
internally. Also, it becomes obvious that the condition within
range_merge() is already satisfied by its caller, and that the
return value is not used.
The diffstat is misleading, because of the copyright boilerplate.
Signed-off-by: Eric Blake <eblake@redhat.com>
Message-Id: <1464712890-14262-2-git-send-email-eblake@redhat.com>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
include/qemu/range.h | 79 ++++++++++++++------------------------------------
util/Makefile.objs | 1 +
util/range.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 104 insertions(+), 57 deletions(-)
create mode 100644 util/range.c
diff --git a/include/qemu/range.h b/include/qemu/range.h
index c903eb5..c10d56a 100644
--- a/include/qemu/range.h
+++ b/include/qemu/range.h
@@ -1,3 +1,23 @@
+/*
+ * QEMU 64-bit address ranges
+ *
+ * Copyright (c) 2015-2016 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
#ifndef QEMU_RANGE_H
#define QEMU_RANGE_H
@@ -59,63 +79,8 @@ static inline int ranges_overlap(uint64_t first1, uint64_t len1,
return !(last2 < first1 || last1 < first2);
}
-/* 0,1 can merge with 1,2 but don't overlap */
-static inline bool ranges_can_merge(Range *range1, Range *range2)
-{
- return !(range1->end < range2->begin || range2->end < range1->begin);
-}
-
-static inline int range_merge(Range *range1, Range *range2)
-{
- if (ranges_can_merge(range1, range2)) {
- if (range1->end < range2->end) {
- range1->end = range2->end;
- }
- if (range1->begin > range2->begin) {
- range1->begin = range2->begin;
- }
- return 0;
- }
-
- return -1;
-}
-
-static inline GList *g_list_insert_sorted_merged(GList *list,
- gpointer data,
- GCompareFunc func)
-{
- GList *l, *next = NULL;
- Range *r, *nextr;
-
- if (!list) {
- list = g_list_insert_sorted(list, data, func);
- return list;
- }
-
- nextr = data;
- l = list;
- while (l && l != next && nextr) {
- r = l->data;
- if (ranges_can_merge(r, nextr)) {
- range_merge(r, nextr);
- l = g_list_remove_link(l, next);
- next = g_list_next(l);
- if (next) {
- nextr = next->data;
- } else {
- nextr = NULL;
- }
- } else {
- l = g_list_next(l);
- }
- }
-
- if (!l) {
- list = g_list_insert_sorted(list, data, func);
- }
-
- return list;
-}
+GList *g_list_insert_sorted_merged(GList *list, gpointer data,
+ GCompareFunc func);
static inline gint range_compare(gconstpointer a, gconstpointer b)
{
diff --git a/util/Makefile.objs b/util/Makefile.objs
index 45f8794..96cb1e0 100644
--- a/util/Makefile.objs
+++ b/util/Makefile.objs
@@ -34,3 +34,4 @@ util-obj-y += base64.o
util-obj-y += log.o
util-obj-y += qdist.o
util-obj-y += qht.o
+util-obj-y += range.o
diff --git a/util/range.c b/util/range.c
new file mode 100644
index 0000000..f775f2e
--- /dev/null
+++ b/util/range.c
@@ -0,0 +1,81 @@
+/*
+ * QEMU 64-bit address ranges
+ *
+ * Copyright (c) 2015-2016 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include "qemu/osdep.h"
+#include "qemu/range.h"
+
+/*
+ * Operations on 64 bit address ranges.
+ * Notes:
+ * - ranges must not wrap around 0, but can include the last byte ~0x0LL.
+ * - this can not represent a full 0 to ~0x0LL range.
+ */
+
+/* 0,1 can merge with 1,2 but don't overlap */
+static bool ranges_can_merge(Range *range1, Range *range2)
+{
+ return !(range1->end < range2->begin || range2->end < range1->begin);
+}
+
+static void range_merge(Range *range1, Range *range2)
+{
+ if (range1->end < range2->end) {
+ range1->end = range2->end;
+ }
+ if (range1->begin > range2->begin) {
+ range1->begin = range2->begin;
+ }
+}
+
+GList *g_list_insert_sorted_merged(GList *list, gpointer data,
+ GCompareFunc func)
+{
+ GList *l, *next = NULL;
+ Range *r, *nextr;
+
+ if (!list) {
+ list = g_list_insert_sorted(list, data, func);
+ return list;
+ }
+
+ nextr = data;
+ l = list;
+ while (l && l != next && nextr) {
+ r = l->data;
+ if (ranges_can_merge(r, nextr)) {
+ range_merge(r, nextr);
+ l = g_list_remove_link(l, next);
+ next = g_list_next(l);
+ if (next) {
+ nextr = next->data;
+ } else {
+ nextr = NULL;
+ }
+ } else {
+ l = g_list_next(l);
+ }
+ }
+
+ if (!l) {
+ list = g_list_insert_sorted(list, data, func);
+ }
+
+ return list;
+}
--
2.5.5
^ permalink raw reply related [flat|nested] 9+ messages in thread* [Qemu-devel] [PULL v2 6/7] qapi: Simplify use of range.h
2016-06-30 13:42 [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30 Markus Armbruster
` (4 preceding siblings ...)
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 5/7] range: Create range.c for code that should not be inline Markus Armbruster
@ 2016-06-30 13:42 ` Markus Armbruster
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 7/7] qapi: Fix memleak in string visitors on int lists Markus Armbruster
2016-07-01 10:51 ` [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30 Peter Maydell
7 siblings, 0 replies; 9+ messages in thread
From: Markus Armbruster @ 2016-06-30 13:42 UTC (permalink / raw)
To: qemu-devel
From: Eric Blake <eblake@redhat.com>
Calling our function g_list_insert_sorted_merged is a misnomer,
since we are NOT writing a glib function. Furthermore, we are
making every caller pass the same comparator function of
range_merge(): any caller that would try otherwise would break
in weird ways since our internal call to ranges_can_merge() is
hard-coded to operate only on ranges, rather than paying
attention to the caller's comparator.
Better is to fix things so that callers don't have to care about
our internal comparator, by picking a function name and updating
the parameter type away from a gratuitous use of void*, to make
it obvious that we are operating specifically on a list of ranges
and not a generic list. Plus, refactoring the code here will
make it easier to plug a memory leak in the next patch.
range_compare() is now internal only, and moves to the .c file.
Signed-off-by: Eric Blake <eblake@redhat.com>
Message-Id: <1464712890-14262-3-git-send-email-eblake@redhat.com>
Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
include/qemu/range.h | 16 +---------------
qapi/string-input-visitor.c | 17 ++++-------------
qapi/string-output-visitor.c | 4 ++--
util/range.c | 20 ++++++++++++++++----
4 files changed, 23 insertions(+), 34 deletions(-)
diff --git a/include/qemu/range.h b/include/qemu/range.h
index c10d56a..3970f00 100644
--- a/include/qemu/range.h
+++ b/include/qemu/range.h
@@ -79,20 +79,6 @@ static inline int ranges_overlap(uint64_t first1, uint64_t len1,
return !(last2 < first1 || last1 < first2);
}
-GList *g_list_insert_sorted_merged(GList *list, gpointer data,
- GCompareFunc func);
-
-static inline gint range_compare(gconstpointer a, gconstpointer b)
-{
- Range *ra = (Range *)a, *rb = (Range *)b;
- if (ra->begin == rb->begin && ra->end == rb->end) {
- return 0;
- } else if (range_get_last(ra->begin, ra->end) <
- range_get_last(rb->begin, rb->end)) {
- return -1;
- } else {
- return 1;
- }
-}
+GList *range_list_insert(GList *list, Range *data);
#endif
diff --git a/qapi/string-input-visitor.c b/qapi/string-input-visitor.c
index 30b5879..b546e5f 100644
--- a/qapi/string-input-visitor.c
+++ b/qapi/string-input-visitor.c
@@ -61,8 +61,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
cur = g_malloc0(sizeof(*cur));
cur->begin = start;
cur->end = start + 1;
- siv->ranges = g_list_insert_sorted_merged(siv->ranges, cur,
- range_compare);
+ siv->ranges = range_list_insert(siv->ranges, cur);
cur = NULL;
str = NULL;
} else if (*endptr == '-') {
@@ -76,10 +75,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
cur = g_malloc0(sizeof(*cur));
cur->begin = start;
cur->end = end + 1;
- siv->ranges =
- g_list_insert_sorted_merged(siv->ranges,
- cur,
- range_compare);
+ siv->ranges = range_list_insert(siv->ranges, cur);
cur = NULL;
str = NULL;
} else if (*endptr == ',') {
@@ -87,10 +83,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
cur = g_malloc0(sizeof(*cur));
cur->begin = start;
cur->end = end + 1;
- siv->ranges =
- g_list_insert_sorted_merged(siv->ranges,
- cur,
- range_compare);
+ siv->ranges = range_list_insert(siv->ranges, cur);
cur = NULL;
} else {
goto error;
@@ -103,9 +96,7 @@ static int parse_str(StringInputVisitor *siv, const char *name, Error **errp)
cur = g_malloc0(sizeof(*cur));
cur->begin = start;
cur->end = start + 1;
- siv->ranges = g_list_insert_sorted_merged(siv->ranges,
- cur,
- range_compare);
+ siv->ranges = range_list_insert(siv->ranges, cur);
cur = NULL;
} else {
goto error;
diff --git a/qapi/string-output-visitor.c b/qapi/string-output-visitor.c
index d013196..5ea395a 100644
--- a/qapi/string-output-visitor.c
+++ b/qapi/string-output-visitor.c
@@ -85,7 +85,7 @@ static void string_output_append(StringOutputVisitor *sov, int64_t a)
Range *r = g_malloc0(sizeof(*r));
r->begin = a;
r->end = a + 1;
- sov->ranges = g_list_insert_sorted_merged(sov->ranges, r, range_compare);
+ sov->ranges = range_list_insert(sov->ranges, r);
}
static void string_output_append_range(StringOutputVisitor *sov,
@@ -94,7 +94,7 @@ static void string_output_append_range(StringOutputVisitor *sov,
Range *r = g_malloc0(sizeof(*r));
r->begin = s;
r->end = e + 1;
- sov->ranges = g_list_insert_sorted_merged(sov->ranges, r, range_compare);
+ sov->ranges = range_list_insert(sov->ranges, r);
}
static void format_string(StringOutputVisitor *sov, Range *r, bool next,
diff --git a/util/range.c b/util/range.c
index f775f2e..dd46092 100644
--- a/util/range.c
+++ b/util/range.c
@@ -44,14 +44,26 @@ static void range_merge(Range *range1, Range *range2)
}
}
-GList *g_list_insert_sorted_merged(GList *list, gpointer data,
- GCompareFunc func)
+static gint range_compare(gconstpointer a, gconstpointer b)
+{
+ Range *ra = (Range *)a, *rb = (Range *)b;
+ if (ra->begin == rb->begin && ra->end == rb->end) {
+ return 0;
+ } else if (range_get_last(ra->begin, ra->end) <
+ range_get_last(rb->begin, rb->end)) {
+ return -1;
+ } else {
+ return 1;
+ }
+}
+
+GList *range_list_insert(GList *list, Range *data)
{
GList *l, *next = NULL;
Range *r, *nextr;
if (!list) {
- list = g_list_insert_sorted(list, data, func);
+ list = g_list_insert_sorted(list, data, range_compare);
return list;
}
@@ -74,7 +86,7 @@ GList *g_list_insert_sorted_merged(GList *list, gpointer data,
}
if (!l) {
- list = g_list_insert_sorted(list, data, func);
+ list = g_list_insert_sorted(list, data, range_compare);
}
return list;
--
2.5.5
^ permalink raw reply related [flat|nested] 9+ messages in thread* [Qemu-devel] [PULL v2 7/7] qapi: Fix memleak in string visitors on int lists
2016-06-30 13:42 [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30 Markus Armbruster
` (5 preceding siblings ...)
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 6/7] qapi: Simplify use of range.h Markus Armbruster
@ 2016-06-30 13:42 ` Markus Armbruster
2016-07-01 10:51 ` [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30 Peter Maydell
7 siblings, 0 replies; 9+ messages in thread
From: Markus Armbruster @ 2016-06-30 13:42 UTC (permalink / raw)
To: qemu-devel
From: Eric Blake <eblake@redhat.com>
Commit 7f8f9ef1 introduced the ability to store a list of
integers as a sorted list of ranges, but when merging ranges,
it leaks one or more ranges. It was also using range_get_last()
incorrectly within range_compare() (a range is a start/end pair,
but range_get_last() is for start/len pairs), and will also
mishandle a range ending in UINT64_MAX (remember, we document
that no range covers 2**64 bytes, but that ranges that end on
UINT64_MAX have end < begin).
The whole merge algorithm was rather complex, and included
unnecessary passes over data within glib functions, and enough
indirection to make it hard to easily plug the data leaks.
Since we are already hard-coding things to a list of ranges,
just rewrite the thing to open-code the traversal and
comparisons, by making the range_compare() helper function give
us an answer that is easier to use, at which point we avoid the
need to pass any callbacks to g_list_*(). Then by reusing
range_extend() instead of duplicating effort with range_merge(),
we cover the corner cases correctly.
Drop the now-unused range_merge() and ranges_can_merge().
Doing this lets test-string-{input,output}-visitor pass under
valgrind without leaks.
Signed-off-by: Eric Blake <eblake@redhat.com>
Message-Id: <1464712890-14262-4-git-send-email-eblake@redhat.com>
Reviewed-by: Markus Armbruster <armbru@redhat.com>
[Comment hoisted out of loop]
Signed-off-by: Markus Armbruster <armbru@redhat.com>
---
util/range.c | 75 +++++++++++++++++++++++-------------------------------------
1 file changed, 29 insertions(+), 46 deletions(-)
diff --git a/util/range.c b/util/range.c
index dd46092..e90c988 100644
--- a/util/range.c
+++ b/util/range.c
@@ -28,65 +28,48 @@
* - this can not represent a full 0 to ~0x0LL range.
*/
-/* 0,1 can merge with 1,2 but don't overlap */
-static bool ranges_can_merge(Range *range1, Range *range2)
+/* Return -1 if @a < @b, 1 if greater, and 0 if they touch or overlap. */
+static inline int range_compare(Range *a, Range *b)
{
- return !(range1->end < range2->begin || range2->end < range1->begin);
-}
-
-static void range_merge(Range *range1, Range *range2)
-{
- if (range1->end < range2->end) {
- range1->end = range2->end;
- }
- if (range1->begin > range2->begin) {
- range1->begin = range2->begin;
- }
-}
-
-static gint range_compare(gconstpointer a, gconstpointer b)
-{
- Range *ra = (Range *)a, *rb = (Range *)b;
- if (ra->begin == rb->begin && ra->end == rb->end) {
- return 0;
- } else if (range_get_last(ra->begin, ra->end) <
- range_get_last(rb->begin, rb->end)) {
+ /* Zero a->end is 2**64, and therefore not less than any b->begin */
+ if (a->end && a->end < b->begin) {
return -1;
- } else {
+ }
+ if (b->end && a->begin > b->end) {
return 1;
}
+ return 0;
}
+/* Insert @data into @list of ranges; caller no longer owns @data */
GList *range_list_insert(GList *list, Range *data)
{
- GList *l, *next = NULL;
- Range *r, *nextr;
+ GList *l;
- if (!list) {
- list = g_list_insert_sorted(list, data, range_compare);
- return list;
+ /* Range lists require no empty ranges */
+ assert(data->begin < data->end || (data->begin && !data->end));
+
+ /* Skip all list elements strictly less than data */
+ for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
}
- nextr = data;
- l = list;
- while (l && l != next && nextr) {
- r = l->data;
- if (ranges_can_merge(r, nextr)) {
- range_merge(r, nextr);
- l = g_list_remove_link(l, next);
- next = g_list_next(l);
- if (next) {
- nextr = next->data;
- } else {
- nextr = NULL;
- }
- } else {
- l = g_list_next(l);
- }
+ if (!l || range_compare(l->data, data) > 0) {
+ /* Rest of the list (if any) is strictly greater than @data */
+ return g_list_insert_before(list, l, data);
}
- if (!l) {
- list = g_list_insert_sorted(list, data, range_compare);
+ /* Current list element overlaps @data, merge the two */
+ range_extend(l->data, data);
+ g_free(data);
+
+ /* Merge any subsequent list elements that now also overlap */
+ while (l->next && range_compare(l->data, l->next->data) == 0) {
+ GList *new_l;
+
+ range_extend(l->data, l->next->data);
+ g_free(l->next->data);
+ new_l = g_list_delete_link(list, l->next);
+ assert(new_l == list);
}
return list;
--
2.5.5
^ permalink raw reply related [flat|nested] 9+ messages in thread* Re: [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30
2016-06-30 13:42 [Qemu-devel] [PULL v2 0/7] QAPI patches 2016-06-30 Markus Armbruster
` (6 preceding siblings ...)
2016-06-30 13:42 ` [Qemu-devel] [PULL v2 7/7] qapi: Fix memleak in string visitors on int lists Markus Armbruster
@ 2016-07-01 10:51 ` Peter Maydell
7 siblings, 0 replies; 9+ messages in thread
From: Peter Maydell @ 2016-07-01 10:51 UTC (permalink / raw)
To: Markus Armbruster; +Cc: QEMU Developers
On 30 June 2016 at 14:42, Markus Armbruster <armbru@redhat.com> wrote:
> The following changes since commit 297e8005f88d4360480eaa2c07220fa8853f0448:
>
> MAINTAINERS: Remove Blue Swirl leftovers (2016-06-30 13:34:49 +0100)
>
> are available in the git repository at:
>
> git://repo.or.cz/qemu/armbru.git tags/pull-qapi-2016-06-30
>
> for you to fetch changes up to db486cc334aafd3dbdaf107388e37fc3d6d3e171:
>
> qapi: Fix memleak in string visitors on int lists (2016-06-30 15:28:54 +0200)
>
> ----------------------------------------------------------------
> QAPI patches 2016-06-30
>
> ----------------------------------------------------------------
> Eric Blake (7):
> json-streamer: Don't leak tokens on incomplete parse
> qobject: Correct JSON lexer grammar comments
> checkpatch: There is no qemu_strtod()
> qapi: Fix crash on missing alternate member of QAPI struct
> range: Create range.c for code that should not be inline
> qapi: Simplify use of range.h
> qapi: Fix memleak in string visitors on int lists
Applied, thanks.
-- PMM
^ permalink raw reply [flat|nested] 9+ messages in thread