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

[Qemu-devel] [PATCH v2 0/3] 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
(modulo copyright blurbs)

v2:
- split out new patch 1 util/range.c, to make code motion easier to follow
- address review comments from Markus

Eric Blake (3):
  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

 include/qemu/range.h         | 91 ++++++++++----------------------------------
 qapi/string-input-visitor.c  | 17 ++-------
 qapi/string-output-visitor.c |  4 +-
 util/range.c                 | 76 ++++++++++++++++++++++++++++++++++++
 util/Makefile.objs           |  1 +
 5 files changed, 104 insertions(+), 85 deletions(-)
 create mode 100644 util/range.c

-- 
2.5.5

[Qemu-devel] [PATCH v2 1/3] range: Create range.c for code that should not be inline

[Eric Blake]

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>
---
 include/qemu/range.h | 79 ++++++++++++++------------------------------------
 util/range.c         | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 util/Makefile.objs   |  1 +
 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/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;
+}
diff --git a/util/Makefile.objs b/util/Makefile.objs
index a8a777e..12db03a 100644
--- a/util/Makefile.objs
+++ b/util/Makefile.objs
@@ -32,3 +32,4 @@ util-obj-y += buffer.o
 util-obj-y += timed-average.o
 util-obj-y += base64.o
 util-obj-y += log.o
+util-obj-y += range.o
-- 
2.5.5

[Qemu-devel] [PATCH v2 2/3] 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 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>
---
 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

[Qemu-devel] [PATCH v2 3/3] 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, 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>
---
 util/range.c | 75 +++++++++++++++++++++++-------------------------------------
 1 file changed, 29 insertions(+), 46 deletions(-)

diff --git a/util/range.c b/util/range.c
index dd46092..56e6baf 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));
+
+    for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
+        /* Skip all list elements strictly less than 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);
-        }
+    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

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

[Markus Armbruster]

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, 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>
> ---
>  util/range.c | 75 +++++++++++++++++++++++-------------------------------------
>  1 file changed, 29 insertions(+), 46 deletions(-)
>
> diff --git a/util/range.c b/util/range.c
> index dd46092..56e6baf 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));

Consider { begin = 0, end = 0 }.

Since zero @end means 2^64, this encodes the (non-empty) range
0..2^64-1.

range.h's comment

 * Notes:
 *   - ranges must not wrap around 0, but can include the last byte ~0x0LL.
 *   - this can not represent a full 0 to ~0x0LL range.

appears to be wrong.  The actual limitation is "can't represent ranges
wrapping around zero, and can't represent the empty range starting at
zero."  Would you like to correct it?

I'm afraid range.h is too clever by half.

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

Let's put the comment before the loop.  It describes the whole loop.
Also makes the emptiness of the body more obvious.

>
> -    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;

I think I could fix up things on commit (assuming we agree on what needs
fixing).

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

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 2332 bytes --]

On 06/01/2016 01:47 AM, Markus Armbruster wrote:
> 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).
>>

>>
>> -    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));
> 
> Consider { begin = 0, end = 0 }.
> 
> Since zero @end means 2^64, this encodes the (non-empty) range
> 0..2^64-1.

Or else it means an uninitialized range.  My argument is that no range
can contain 2^64 bytes, and therefore the only possible range that would
be that large (0..2^64-1) is unrepresentable, therefore, if end == 0,
begin must be non-zero for the range to be valid as an initialized range.

> 
> range.h's comment
> 
>  * Notes:
>  *   - ranges must not wrap around 0, but can include the last byte ~0x0LL.
>  *   - this can not represent a full 0 to ~0x0LL range.
> 
> appears to be wrong.  The actual limitation is "can't represent ranges
> wrapping around zero, and can't represent the empty range starting at
> zero."  Would you like to correct it?

I'm not sure what corrections it needs, though.

> 
> I'm afraid range.h is too clever by half.

Unfortunately true.

> 
>> +
>> +    for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
>> +        /* Skip all list elements strictly less than data */
>>      }
> 
> Let's put the comment before the loop.  It describes the whole loop.
> Also makes the emptiness of the body more obvious.

Sure.

> 
> I think I could fix up things on commit (assuming we agree on what needs
> fixing).
> 

Adding other authors of range.h for their opinions...

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

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

[Markus Armbruster]

Eric Blake <eblake@redhat.com> writes:

> On 06/01/2016 01:47 AM, Markus Armbruster wrote:
>> 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).
>>>
>
>>>
>>> -    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));
>> 
>> Consider { begin = 0, end = 0 }.
>> 
>> Since zero @end means 2^64, this encodes the (non-empty) range
>> 0..2^64-1.
>
> Or else it means an uninitialized range.  My argument is that no range
> can contain 2^64 bytes, and therefore the only possible range that would
> be that large (0..2^64-1) is unrepresentable, therefore, if end == 0,
> begin must be non-zero for the range to be valid as an initialized range.

I'm not sure what you mean by "uninitialized range".  Maybe "invalid
range"?

>> range.h's comment
>> 
>>  * Notes:
>>  *   - ranges must not wrap around 0, but can include the last byte ~0x0LL.
>>  *   - this can not represent a full 0 to ~0x0LL range.
>> 
>> appears to be wrong.  The actual limitation is "can't represent ranges
>> wrapping around zero, and can't represent the empty range starting at
>> zero."  Would you like to correct it?
>
> I'm not sure what corrections it needs, though.
>
>> I'm afraid range.h is too clever by half.
>
> Unfortunately true.
>
>> 
>>> +
>>> +    for (l = list; l && range_compare(l->data, data) < 0; l = l->next) {
>>> +        /* Skip all list elements strictly less than data */
>>>      }
>> 
>> Let's put the comment before the loop.  It describes the whole loop.
>> Also makes the emptiness of the body more obvious.
>
> Sure.
>
>> 
>> I think I could fix up things on commit (assuming we agree on what needs
>> fixing).
>> 
>
> Adding other authors of range.h for their opinions...

No reply.

I find the comments in range.h terminally confusing.

The clear parts:

* we want to have inclusive lower bound <= inclusive upper bound (no
  wrap around), and

* we want to encode the bounds using @start as inclusive lower bound,
  and @end as exclusive upper bound.

This begs the question how end == 0 is to be interpreted.  Options:

(1) It's literally the exclusive upper bound.  An interval with a
non-negative inclusive lower bound and a zero exclusive upper bound is
empty.  There is no way to represent the inclusive upper bound 2^63-1.
This contradicts the comment's claim that you can.

(2) It's 2^64.  Now you cannot represent the inclusive upper bound -1.
You cannot represent the empty interval [0,-1], although you can
represent other empty intervals [b,b-1], b>0.  { start = 0, end = 0 }
encodes the interval [0,2^64-1].  Contradicts the comment's claim that
you can't, unless...

(2') end=0 is special-cased to mean something else when start=0!  Namely
0 instead of 2^64, so that { start=0, end=0 } becomes the empty interval
[0,-1].

The tradeoff between (2) and (2') is between two anomalies: "can't do
[0,-1]", and "can't do [0..2^64-1]".

I prefer (2), because I find the former anomaly less bad, and feel
special-casing @end is bound to lead to bugs.

Whatever option we choose, we should fix the comment to explain it
clearly.

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

[Markus Armbruster]

Markus Armbruster <armbru@redhat.com> writes:

[...]
> I find the comments in range.h terminally confusing.
>
> The clear parts:
>
> * we want to have inclusive lower bound <= inclusive upper bound (no
>   wrap around), and
>
> * we want to encode the bounds using @start as inclusive lower bound,
>   and @end as exclusive upper bound.
>
> This begs the question how end == 0 is to be interpreted.  Options:
>
> (1) It's literally the exclusive upper bound.  An interval with a
> non-negative inclusive lower bound and a zero exclusive upper bound is
> empty.  There is no way to represent the inclusive upper bound 2^63-1.
> This contradicts the comment's claim that you can.
>
> (2) It's 2^64.  Now you cannot represent the inclusive upper bound -1.
> You cannot represent the empty interval [0,-1], although you can
> represent other empty intervals [b,b-1], b>0.  { start = 0, end = 0 }
> encodes the interval [0,2^64-1].  Contradicts the comment's claim that
> you can't, unless...
>
> (2') end=0 is special-cased to mean something else when start=0!  Namely
> 0 instead of 2^64, so that { start=0, end=0 } becomes the empty interval
> [0,-1].
>
> The tradeoff between (2) and (2') is between two anomalies: "can't do
> [0,-1]", and "can't do [0..2^64-1]".
>
> I prefer (2), because I find the former anomaly less bad, and feel
> special-casing @end is bound to lead to bugs.
>
> Whatever option we choose, we should fix the comment to explain it
> clearly.

Unless somebody has better ideas, I'll cook up a patch documenting (2')
and make code conform to it (in case there is code that doesn't).