From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/9080 Path: news.gmane.org!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: Possible infinite loop in qsort() Date: Sun, 10 Jan 2016 13:15:57 +0100 Message-ID: <20160110121557.GR23362@port70.net> References: <20160109082139.GD2016@debian> <20160109090719.GA385@nyan> <20160110040516.GQ238@brightrain.aerifal.cx> <20160110113852.GE2016@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 1452428176 21169 80.91.229.3 (10 Jan 2016 12:16:16 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 10 Jan 2016 12:16:16 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-9093-gllmg-musl=m.gmane.org@lists.openwall.com Sun Jan 10 13:16:16 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 1aIEup-0003yT-VF for gllmg-musl@m.gmane.org; Sun, 10 Jan 2016 13:16:12 +0100 Original-Received: (qmail 5122 invoked by uid 550); 10 Jan 2016 12:16:10 -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 4080 invoked from network); 10 Jan 2016 12:16:09 -0000 Mail-Followup-To: musl@lists.openwall.com Content-Disposition: inline In-Reply-To: <20160110113852.GE2016@debian> User-Agent: Mutt/1.5.24 (2015-08-30) Xref: news.gmane.org gmane.linux.lib.musl.general:9080 Archived-At: * Markus Wichmann [2016-01-10 12:38:53 +0100]: > What I did was make sure that nel * width is greater than the greatest > Leonardo number * width that's representable in the architecture's > size_t. That is possible for every given width. The inequation I just size_t overflow is not a problem unsigned overflow is well defined and the loop is guaranteed to finish, the only question if it finishes before lp array is filled, and the answer is yes if object size is restricted to <= SIZE_MAX/2 > gave boils down to nel > max{l | l is Leonardo number, l * width < 2^32} > > But since there are (plenty of) Leonardo numbers between 2^31 and 2^32, > and object size (nel * width) is limited to <2^31, with a valid object > the calculation can't overflow. And with an invalid object, I don't know > if the code as given would even work, as pointer differences wouldn't > work. Haven't tested that one, either. invalid input is ub and qsort does not try catch such ub