From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/9082 Path: news.gmane.org!not-for-mail From: Morten Welinder Newsgroups: gmane.linux.lib.musl.general Subject: Re: Possible infinite loop in qsort() Date: Sun, 10 Jan 2016 11:35:04 -0500 Message-ID: References: <20160109082139.GD2016@debian> <20160109090719.GA385@nyan> <20160110040516.GQ238@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: ger.gmane.org 1452443720 20871 80.91.229.3 (10 Jan 2016 16:35:20 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 10 Jan 2016 16:35:20 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-9095-gllmg-musl=m.gmane.org@lists.openwall.com Sun Jan 10 17:35:20 2016 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1aIIxb-00029y-BZ for gllmg-musl@m.gmane.org; Sun, 10 Jan 2016 17:35:19 +0100 Original-Received: (qmail 10015 invoked by uid 550); 10 Jan 2016 16:35:17 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 9994 invoked from network); 10 Jan 2016 16:35:17 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=ZMacNjmwNyH/TZopcYpSi1FNb0WSTxD1nKZ9AiPmM/0=; b=cg8Lghi1s2g5xOGizoYn8h+I1Dr+fAz2b0GmUQb83DMXUiZCwLQvEtc76yhzQSk15D Q26hrLOjxW+T7YfzWhb/rz/64dBERuBaa5MF5GqwBWjIrEQrsBvYThglBiJcywNbOyHq twNNGV0PBJPtuLQF/bqG8OuYHeU1rHfYs3w5xLfRc/VIEce78k6zvbbGcksRsOynhDPu d/JTEGfLd45GjcVuRSTbpiI0+JYOJuZ5Z1eqYHPl3+QtGgWWNlDLFK0KnUMtfrDoulVP EglHLh7jq6Bn7cPIW9TMHP9L3Qf85bjSCF1r7qxZzOcEmNd2DqL247ihWvnMrRblnPJT aYZw== X-Received: by 10.107.158.3 with SMTP id h3mr9869467ioe.59.1452443704988; Sun, 10 Jan 2016 08:35:04 -0800 (PST) In-Reply-To: <20160110040516.GQ238@brightrain.aerifal.cx> Xref: news.gmane.org gmane.linux.lib.musl.general:9082 Archived-At: > Note also that if you do want to use this code on an > implementation without such a guarantee, only the case where > the member size is 1 can possibly have >SIZE_MAX/2 > members. That's correct. > In that case, you can massively optimize out the whole sort > by just counting the number of times each byte appears [...] That isn't. sizeof(char) is guaranteed to be 1. Is it not, however, required to represent bytes. You could have sizeof(pointer) be 1 also and if you so, you really cannot do sorting by counting. M. On Sat, Jan 9, 2016 at 11:05 PM, Rich Felker wrote: > On Sat, Jan 09, 2016 at 10:07:19AM +0100, Felix Janda wrote: >> Markus Wichmann wrote: >> > Hi all, >> > >> > This is the Leonardo number precompute loop in qsort(): >> > >> > for(lp[0]=lp[1]=width, i=2; (lp[i]=lp[i-2]+lp[i-1]+width) < size; i++); >> > >> > I haven't actually tested this, but is it possible that this can become >> > infinite on x32? My reasoning is this: >> > >> > This loop calculates all Leonardo numbers (scaled by width) until one >> > comes along that is greater than the array length. However, that number >> > is never actually needed, we only need to calculate all Leonardo numbers >> > smaller than array size. And there is another problem: What if that >> > smallest Leonardo number greater than array size isn't representable in >> > size_t? In that case, the final addition step will overflow and the >> > inequation will never become false. So if an array is entered that has >> > more elements than the largest representable Leonardo number scaled by >> > width (for instance, an array with more than 866,988,873 ints (size 4)), >> > the above loop becomes infinite: The next Leonardo number is >> > 1,402,817,465, multiplied by 4 that is larger than 2^32, so on a 32-bit >> > architecture, this will overflow. >> > >> > Then I thought more about this: Such an array would be just over 3GB >> > long. You don't have that much address space available on most 32-bit >> > archs because Linux selfishly hogs a whole GB of address space for the >> > kernel. On 64-bit archs, Linux hogs half the address space, so no >> > userspace array can be larger than the largest Leonardo number >> > representable in 64 bits, so it looks like we're safe, right? >> > >> > Except there's x32: 4GB of address space and no kernel infringes on it >> > (x32 is basically x86_64, but we keep the userspace pointers down to 32 >> > bits, so the kernel is way beyond what we're looking at). >> > >> > But as I said, we don't actually need the smallest Leonardo number >> > greater than size, we only need the largest Leonardo numer smaller than >> > size. So this problem could be solved by either of: >> > >> > 1. Checking for overflow. >> > 2. Putting an absolute limit on i. >> > >> > Did I miss anything? >> >> musl enforces that object sizes should not be greater than PTRDIFF_MAX. >> See for example the discussion at >> >> http://www.openwall.com/lists/musl/2013/06/27/7 >> >> So there will not be objects of size 3GB with musl on x32. Since the >> Leonardo numbers grow slower than 2^n in general no overflow should >> happen if "size" is valid. Otherwise, UB was invoked. > > Note also that if you do want to use this code on an implementation > without such a guarantee, only the case where the member size is 1 can > possibly have >SIZE_MAX/2 members. In that case, you can massively > optimize out the whole sort by just counting the number of times each > byte appears (in size_t[UCHAR_MAX+1] space which is tiny), sorting the > pairs (value,count) using the comparison function, then writing out > each value the appropriate number of times. > > Rich