From patchwork Thu Jun 30 13:42:51 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Markus Armbruster X-Patchwork-Id: 642566 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3rgLjB2Cqzz9sR8 for ; Thu, 30 Jun 2016 23:58:06 +1000 (AEST) Received: from localhost ([::1]:49574 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bIcTk-0000FV-3G for incoming@patchwork.ozlabs.org; Thu, 30 Jun 2016 09:58:04 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:50924) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bIcFB-0000Da-SV for qemu-devel@nongnu.org; Thu, 30 Jun 2016 09:43:08 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bIcF6-00039n-76 for qemu-devel@nongnu.org; Thu, 30 Jun 2016 09:43:00 -0400 Received: from mx1.redhat.com ([209.132.183.28]:35572) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bIcF5-00038b-Tj for qemu-devel@nongnu.org; Thu, 30 Jun 2016 09:42:56 -0400 Received: from int-mx11.intmail.prod.int.phx2.redhat.com (int-mx11.intmail.prod.int.phx2.redhat.com [10.5.11.24]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 7FD76C05B1E7 for ; Thu, 30 Jun 2016 13:42:55 +0000 (UTC) Received: from blackfin.pond.sub.org (ovpn-116-16.ams2.redhat.com [10.36.116.16]) by int-mx11.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u5UDgrcY004819 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Thu, 30 Jun 2016 09:42:54 -0400 Received: by blackfin.pond.sub.org (Postfix, from userid 1000) id 1D9031132889; Thu, 30 Jun 2016 15:42:51 +0200 (CEST) From: Markus Armbruster To: qemu-devel@nongnu.org Date: Thu, 30 Jun 2016 15:42:51 +0200 Message-Id: <1467294171-31518-8-git-send-email-armbru@redhat.com> In-Reply-To: <1467294171-31518-1-git-send-email-armbru@redhat.com> References: <1467294171-31518-1-git-send-email-armbru@redhat.com> X-Scanned-By: MIMEDefang 2.68 on 10.5.11.24 X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.32]); Thu, 30 Jun 2016 13:42:55 +0000 (UTC) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 209.132.183.28 Subject: [Qemu-devel] [PULL v2 7/7] qapi: Fix memleak in string visitors on int lists X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" From: 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 Message-Id: <1464712890-14262-4-git-send-email-eblake@redhat.com> Reviewed-by: Markus Armbruster [Comment hoisted out of loop] Signed-off-by: Markus Armbruster --- 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;