| Message ID | 1463458137-19109-3-git-send-email-eblake@redhat.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
[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!
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; }
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(-)