From patchwork Tue May 17 04:08:57 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Eric Blake X-Patchwork-Id: 9108841 Return-Path: X-Original-To: patchwork-qemu-devel@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id EBEE5BF29F for ; Tue, 17 May 2016 04:10:23 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 2B9F220268 for ; Tue, 17 May 2016 04:10:23 +0000 (UTC) Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 4C5082015A for ; Tue, 17 May 2016 04:10:22 +0000 (UTC) Received: from localhost ([::1]:48321 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1b2WKr-0000jC-Fj for patchwork-qemu-devel@patchwork.kernel.org; Tue, 17 May 2016 00:10:21 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:43378) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1b2WJn-0006qO-4N for qemu-devel@nongnu.org; Tue, 17 May 2016 00:09:22 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1b2WJe-0000Lo-MJ for qemu-devel@nongnu.org; Tue, 17 May 2016 00:09:13 -0400 Received: from resqmta-po-07v.sys.comcast.net ([2001:558:fe16:19:96:114:154:166]:56695) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1b2WJe-0000La-GR for qemu-devel@nongnu.org; Tue, 17 May 2016 00:09:06 -0400 Received: from resomta-po-20v.sys.comcast.net ([96.114.154.244]) by comcast with SMTP id 2WHqbBqIbpyio2WJebrXIq; Tue, 17 May 2016 04:09:06 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1463458146; bh=QWRCx+ck6UMJ8yMuqjgqH5JtgvNoUy9gXYCvYDITFT0=; h=Received:Received:From:To:Subject:Date:Message-Id; b=k9S0OHwIQFKer0MANX/s0eTRxbxQp9emcbdvyvSC3OXi9+bB9k+Y1bGKdpM41PvkA Ux5anNnK/CG/jwEH0qiI4qbK4SZzQsUppOFgauFzwFlv+q0ckZnr58r5TMZtdG2FK4 8fR3B4FWZ63uaEnilpHmD75RTDlrrRsPDUYeSuK6qevN1W+mw5RyGBe9PXqd+ian7W 55wSwS36efwO0lj/x3eb01ka01tzIzLKmFKpxErQ6IVa0esY/IhwT6dCpU8kbf5D4v I3fTMdHlxjD9lSvP+yPW9/OwQdyVZbGNb07T8qCjFGbiAxHv0MiElf2IrzroiyzVbM iJfaKf2jZcFtA== Received: from red.redhat.com ([24.10.254.122]) by resomta-po-20v.sys.comcast.net with comcast id vG8x1s0082fD5rL01G95cn; Tue, 17 May 2016 04:09:05 +0000 From: Eric Blake To: qemu-devel@nongnu.org Date: Mon, 16 May 2016 22:08:57 -0600 Message-Id: <1463458137-19109-3-git-send-email-eblake@redhat.com> X-Mailer: git-send-email 2.5.5 In-Reply-To: <1463458137-19109-1-git-send-email-eblake@redhat.com> References: <1463458137-19109-1-git-send-email-eblake@redhat.com> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2001:558:fe16:19:96:114:154:166 Subject: [Qemu-devel] [PATCH 2/2] 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: , Cc: qemu-stable@nongnu.org, armbru@redhat.com Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" X-Spam-Status: No, score=-6.8 required=5.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI, T_DKIM_INVALID, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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 --- 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; }