[Qemu-devel] [PATCH 0/2] Fix leak in handling of integer lists as strings

[Qemu-devel] [PATCH 0/2] Fix leak in handling of integer lists as strings

[Eric Blake]

The qapi string-input and string-output visitors can leak memory
when used on integer lists that were set up such that the range
list needed to merge adjacent/overlapping ranges; detected by
valgrind on test-string-{input,output}-visitor.

It doesn't hurt that the overall series removes more code than it adds.

Eric Blake (2):
  qapi: Simplify use of range.h
  qapi: Fix memleak in string visitors on int lists

 include/qemu/range.h         | 107 +++++++++++++++++--------------------------
 qapi/string-input-visitor.c  |  17 ++-----
 qapi/string-output-visitor.c |   4 +-
 3 files changed, 48 insertions(+), 80 deletions(-)

-- 
2.5.5

[Qemu-devel] [PATCH 1/2] qapi: Simplify use of range.h

[Eric Blake]

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 does 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, and to pick a function name that makes
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.

Note that no one used the return value of range_merge(), and that
it can only be called if its precondition was satisfied, so
simplify that while in the area.

The declaration of range_compare() had to be hoisted earlier
in the file.

CC: qemu-stable@nongnu.org
Signed-off-by: Eric Blake <eblake@redhat.com>
---
 include/qemu/range.h         | 49 +++++++++++++++++++-------------------------
 qapi/string-input-visitor.c  | 17 ++++-----------
 qapi/string-output-visitor.c |  4 ++--
 3 files changed, 27 insertions(+), 43 deletions(-)

diff --git a/include/qemu/range.h b/include/qemu/range.h
index c903eb5..4a4801b 100644
--- a/include/qemu/range.h
+++ b/include/qemu/range.h
@@ -65,30 +65,36 @@ 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)
+static inline void 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;
-        }
+    if (range1->end < range2->end) {
+        range1->end = range2->end;
+    }
+    if (range1->begin > range2->begin) {
+        range1->begin = range2->begin;
+    }
+}
+
+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;
     }
-
-    return -1;
 }

-static inline GList *g_list_insert_sorted_merged(GList *list,
-                                                 gpointer data,
-                                                 GCompareFunc func)
+static inline 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;
     }

@@ -111,23 +117,10 @@ static inline GList *g_list_insert_sorted_merged(GList *list,
     }

     if (!l) {
-        list = g_list_insert_sorted(list, data, func);
+        list = g_list_insert_sorted(list, data, range_compare);
     }

     return list;
 }

-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;
-    }
-}
-
 #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,
-- 
2.5.5

[Qemu-devel] [PATCH 2/2] qapi: Fix memleak in string visitors on int lists

[Eric Blake]

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, especially since
we are hard-coding things to a list of ranges; so just rewrite
the thing to open-code the traversal and comparisons, making
the range_compare() helper function give us a nicer answer,
avoiding the need to pass any callbacks to g_list_*(). And
reusing range_extend() ensures 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.

CC: qemu-stable@nongnu.org
Signed-off-by: Eric Blake <eblake@redhat.com>
---
 include/qemu/range.h | 78 +++++++++++++++++++++-------------------------------
 1 file changed, 31 insertions(+), 47 deletions(-)

diff --git a/include/qemu/range.h b/include/qemu/range.h
index 4a4801b..9955cca 100644
--- a/include/qemu/range.h
+++ b/include/qemu/range.h
@@ -59,67 +59,51 @@ 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 -1 if @a < b, 1 if greater, and 0 if they overlap. */
+static inline int range_compare(Range *a, Range *b)
 {
-    return !(range1->end < range2->begin || range2->end < range1->begin);
-}
-
-static inline 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 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)) {
+    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 */
 static inline GList *range_list_insert(GList *list, Range *data)
 {
-    GList *l, *next = NULL;
-    Range *r, *nextr;
+    GList *l = list;

-    if (!list) {
-        list = g_list_insert_sorted(list, data, range_compare);
-        return list;
+    /* Range lists require no empty ranges */
+    assert(data->begin || data->end);
+
+    /* Skip all list elements strictly less than data */
+    while (l && range_compare(l->data, data) < 0) {
+        l = l->next;
+    }
+
+    /* If no list, or rest of list exceeds data, insert data and done */
+    if (!l || range_compare(l->data, data) > 0) {
+        return g_list_insert_before(list, l, data);
     }

-    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);
+    /* Merge data into current list element */
+    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) {
+        range_extend(l->data, l->next->data);
+        g_free(l->next->data);
+        /* We know we aren't deleting the list head, so shave time
+         * by passing l instead of list */
+        if (g_list_delete_link(l, l->next) != l) {
+            abort();
         }
     }

-    if (!l) {
-        list = g_list_insert_sorted(list, data, range_compare);
-    }
-
     return list;
 }

-- 
2.5.5

Re: [Qemu-devel] [PATCH 1/2] qapi: Simplify use of range.h

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> 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 does 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, and to pick a function name that makes
> 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.
>
> Note that no one used the return value of range_merge(), and that
> it can only be called if its precondition was satisfied, so
> simplify that while in the area.
>
> The declaration of range_compare() had to be hoisted earlier
> in the file.
>
> CC: qemu-stable@nongnu.org
> Signed-off-by: Eric Blake <eblake@redhat.com>
> ---
>  include/qemu/range.h         | 49 +++++++++++++++++++-------------------------
>  qapi/string-input-visitor.c  | 17 ++++-----------
>  qapi/string-output-visitor.c |  4 ++--
>  3 files changed, 27 insertions(+), 43 deletions(-)
>
> diff --git a/include/qemu/range.h b/include/qemu/range.h
> index c903eb5..4a4801b 100644
> --- a/include/qemu/range.h
> +++ b/include/qemu/range.h
> @@ -65,30 +65,36 @@ 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)
> +static inline void 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;
> -        }
> +    if (range1->end < range2->end) {
> +        range1->end = range2->end;
> +    }
> +    if (range1->begin > range2->begin) {
> +        range1->begin = range2->begin;
> +    }
> +}

Why can the conditional be dropped?  The commit message doesn't quite
explain.

> +
> +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;
>      }
> -
> -    return -1;
>  }
>
> -static inline GList *g_list_insert_sorted_merged(GList *list,
> -                                                 gpointer data,
> -                                                 GCompareFunc func)
> +static inline GList *range_list_insert(GList *list, Range *data)

Cleans up gratuitous use of void *.  Would you like to mention this in
your commit message?

>  {
>      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;
>      }
>
> @@ -111,23 +117,10 @@ static inline GList *g_list_insert_sorted_merged(GList *list,
>      }
>
>      if (!l) {
> -        list = g_list_insert_sorted(list, data, func);
> +        list = g_list_insert_sorted(list, data, range_compare);
>      }
>
>      return list;
>  }
>
> -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;
> -    }
> -}
> -
>  #endif
[...]

Why on earth does this code live in a header?  Let's move at least
range_list_insert() to util/range.c.  Moving it in PATCH 3/2 would be
fine.

Re: [Qemu-devel] [PATCH 2/2] qapi: Fix memleak in string visitors on int lists

[Markus Armbruster]

[I accidentally sent this just to Eric, resending to list...]

Eric Blake <eblake@redhat.com> writes:

> 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, especially since
> we are hard-coding things to a list of ranges; so just rewrite
> the thing to open-code the traversal and comparisons, making
> the range_compare() helper function give us a nicer answer,
> avoiding the need to pass any callbacks to g_list_*(). And
> reusing range_extend() ensures 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.
>
> CC: qemu-stable@nongnu.org
> Signed-off-by: Eric Blake <eblake@redhat.com>
> ---
>  include/qemu/range.h | 78 +++++++++++++++++++++-------------------------------
>  1 file changed, 31 insertions(+), 47 deletions(-)
>
> diff --git a/include/qemu/range.h b/include/qemu/range.h
> index 4a4801b..9955cca 100644
> --- a/include/qemu/range.h
> +++ b/include/qemu/range.h
> @@ -59,67 +59,51 @@ 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 -1 if @a < b, 1 if greater, and 0 if they overlap. */
> +static inline int range_compare(Range *a, Range *b)
>  {
> -    return !(range1->end < range2->begin || range2->end < range1->begin);
> -}
> -
> -static inline 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 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)) {
> +    if (a->end && a->end < b->begin) {

This gave me pause.  It's owed to Range's subtle semantics.  Zero @start
means zero, but zero @end means 2^64!  Zero a->end cannot be less than
any b->begin, so this conditional computes "a's end < b's begin", or in
other words "a ends before b".  Correct.

>          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 */
>  static inline GList *range_list_insert(GList *list, Range *data)
>  {
> -    GList *l, *next = NULL;
> -    Range *r, *nextr;
> +    GList *l = list;
>
> -    if (!list) {
> -        list = g_list_insert_sorted(list, data, range_compare);
> -        return list;
> +    /* Range lists require no empty ranges */
> +    assert(data->begin || data->end);

Uh, wouldn't { begin = 1, end = 1 } be empty, too?  

Do you mean assert(data->begin < data->end || !data->end)?

> +
> +    /* Skip all list elements strictly less than data */
> +    while (l && range_compare(l->data, data) < 0) {
> +        l = l->next;
> +    }

Recommend

       for (l = list; l && range_compare(l->data, data) < 0; l = l->next)
           ;

> +
> +    /* If no list, or rest of list exceeds data, insert data and done */

I understand what you mean, but "exceeds" seems less than clear.
Perhaps: "If the rest of the list (if any) is strictly greater than
@data".

> +    if (!l || range_compare(l->data, data) > 0) {
> +        return g_list_insert_before(list, l, data);
>      }
>
> -    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);
> +    /* Merge data into current list element */

Suggest: /* 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) {
> +        range_extend(l->data, l->next->data);
> +        g_free(l->next->data);
> +        /* We know we aren't deleting the list head, so shave time
> +         * by passing l instead of list */

s/shave/save/

> +        if (g_list_delete_link(l, l->next) != l) {
> +            abort();
>          }
>      }

Would

           new_l = g_list_delete_link(l, l->next);
           assert(new_l == l);

be clearer?

Does passing l instead of list really save time?

GLib docs on first parameter: "this must point to the top of the list".

Aside: "top of list" sounds odd to me.  They must mean "head".

>
> -    if (!l) {
> -        list = g_list_insert_sorted(list, data, range_compare);
> -    }
> -
>      return list;
>  }

Your code is much clearer.  Thanks!