From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/9074 Path: news.gmane.org!not-for-mail From: Markus Wichmann Newsgroups: gmane.linux.lib.musl.general Subject: Possible infinite loop in qsort() Date: Sat, 9 Jan 2016 09:21:39 +0100 Message-ID: <20160109082139.GD2016@debian> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1452327720 2597 80.91.229.3 (9 Jan 2016 08:22:00 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 9 Jan 2016 08:22:00 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-9087-gllmg-musl=m.gmane.org@lists.openwall.com Sat Jan 09 09:22:00 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 1aHomd-0002Bp-1Z for gllmg-musl@m.gmane.org; Sat, 09 Jan 2016 09:21:59 +0100 Original-Received: (qmail 17917 invoked by uid 550); 9 Jan 2016 08:21:57 -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 17869 invoked from network); 9 Jan 2016 08:21:51 -0000 Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) X-Provags-ID: V03:K0:SLuauZpraenbQnLq/rpzw+nBbJKD+idKt9RNh9A6W7M9t/fEoPG /4t/IOlBlGV1J1ZSHPmMCN91Ia5VAV3CDGoG6DqRl88mQmnMcm17aY78xUNOG+5yO3EEBh0 F43LMWgRWb8xUZJNEi0h0UN87yd3hBlxfDNIyLJ70sdx2W9I1NxPhBGIgtknOFZjxivLN5Y abIPGoUfdLO/g5d/HporA== X-UI-Out-Filterresults: notjunk:1;V01:K0:UNyhJMSTAB4=:aEA+3Sueibf1uNkvXy7APH DytRosd4bbw73V0K90n8LikgshSEXOHe46iQiI4qUoyIIN/Lf4B5dJNqIbC7qXyQQCEmvAGUX bp1EpyDwqHGLrjYI9y3iF7MCVi6kanjzfDcyLZZ4R2V6u/GT4xyblp+nhYGR5oTZBrwrJ+Cm9 WGsTwPQr57sGmDRa3nv8MbxewMXajZz33INMGX2ofCWdJRJO9Awoe5p2JpU9mpq+sfEazU9hx UFGnh+qUDZYmowlV1sQroGciE1t5pqsEP26uCyd6ZkrgegGrdkF6LA3ORGkkbwojqNciSttnZ 1tsVbKytYoV/SFMVCwha6lmMOlovcgEWAnVS8ESr+jLMTLdI2+R89KP6IcJ1JdEpYamUWh0aZ Y5Ga69LmvtM4pIZZ+7ZSz+Z6+F1Y/x6rUVmOHL+TJQlEH3WBP3vvWJThZN6QGZixYETfexaxd zsal7akPQpP2xEPtpdPmZehzDvlM4zxHhOunNB7hi/NNbMhO4CRwItgbj8xaAuObm6yQK3gpt hCCxU02p9+lwsbX/zCkoD9J355y0+mcH5Pp0H8+XcFBOiGxsj0as4Y0/knqVHI0ljkNO4Gt4p Ck+adYWTVMFr5hHEpQ7b8gac+dI3KivNGhfOv+z7oXWTY13odrrA317LP9g+Hod0e8ydxNgt+ i4EpErcKbYb1gXsvsrBxFXnkQXDWyQkCIsZogkD9PGfkMx7e9K55PhvoEEU6L3m2MpnvgToua oKDxp6pAMfdDXYN8i0kPKw0MmSijtF/NJOUPBPVejjLHN9OR5W52ZWEakIbfnC1+laMm8HRT Xref: news.gmane.org gmane.linux.lib.musl.general:9074 Archived-At: 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? Ciao, Markus