From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:44622) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bCRNv-0000g6-VL for qemu-devel@nongnu.org; Mon, 13 Jun 2016 08:54:33 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bCRNq-00053I-SZ for qemu-devel@nongnu.org; Mon, 13 Jun 2016 08:54:30 -0400 Received: from mx1.redhat.com ([209.132.183.28]:60582) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bCRNq-00053C-KY for qemu-devel@nongnu.org; Mon, 13 Jun 2016 08:54:26 -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 1D9E546202 for ; Mon, 13 Jun 2016 12:54:26 +0000 (UTC) From: Markus Armbruster References: <1464712890-14262-1-git-send-email-eblake@redhat.com> <1464712890-14262-4-git-send-email-eblake@redhat.com> <87y46p4afp.fsf@dusky.pond.sub.org> <574EF664.5060205@redhat.com> Date: Mon, 13 Jun 2016 14:54:23 +0200 In-Reply-To: <574EF664.5060205@redhat.com> (Eric Blake's message of "Wed, 1 Jun 2016 08:51:16 -0600") Message-ID: <8737ohw8ow.fsf@dusky.pond.sub.org> MIME-Version: 1.0 Content-Type: text/plain Subject: Re: [Qemu-devel] [PATCH v2 3/3] qapi: Fix memleak in string visitors on int lists List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Eric Blake Cc: Paolo Bonzini , qemu-devel@nongnu.org, "Michael S. Tsirkin" Eric Blake writes: > On 06/01/2016 01:47 AM, Markus Armbruster wrote: >> Eric Blake 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.