From owner-freebsd-bugs@freebsd.org Sun Oct 30 20:10:31 2016 Return-Path: Delivered-To: freebsd-bugs@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 4D151C27BE9 for ; Sun, 30 Oct 2016 20:10:31 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from kenobi.freebsd.org (kenobi.freebsd.org [IPv6:2001:1900:2254:206a::16:76]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 2329F1183 for ; Sun, 30 Oct 2016 20:10:31 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from bugs.freebsd.org ([127.0.1.118]) by kenobi.freebsd.org (8.15.2/8.15.2) with ESMTP id u9UKAVPv065372 for ; Sun, 30 Oct 2016 20:10:31 GMT (envelope-from bugzilla-noreply@freebsd.org) From: bugzilla-noreply@freebsd.org To: freebsd-bugs@FreeBSD.org Subject: [Bug 213922] crafted data could cause qsort to exhaust stack space Date: Sun, 30 Oct 2016 20:10:31 +0000 X-Bugzilla-Reason: AssignedTo X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: Base System X-Bugzilla-Component: bin X-Bugzilla-Version: CURRENT X-Bugzilla-Keywords: X-Bugzilla-Severity: Affects Many People X-Bugzilla-Who: jhoward@alumni.utexas.net X-Bugzilla-Status: New X-Bugzilla-Resolution: X-Bugzilla-Priority: --- X-Bugzilla-Assigned-To: freebsd-bugs@FreeBSD.org X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_id short_desc product version rep_platform op_sys bug_status bug_severity priority component assigned_to reporter Message-ID: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: https://bugs.freebsd.org/bugzilla/ Auto-Submitted: auto-generated MIME-Version: 1.0 X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 30 Oct 2016 20:10:31 -0000 https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=3D213922 Bug ID: 213922 Summary: crafted data could cause qsort to exhaust stack space Product: Base System Version: CURRENT Hardware: Any OS: Any Status: New Severity: Affects Many People Priority: --- Component: bin Assignee: freebsd-bugs@FreeBSD.org Reporter: jhoward@alumni.utexas.net Quick sort is recursive. It divides the sort data into two sections, moves some elements around, then recurses to sort each section. The BSD implementation, largely taken from Bentley & McIlroy's "Engineering= a Sort Function", omits the tail recursion in order to save stack space. Howe= ver, it always sorts the "left" section by recursion, even when it is large rela= tive to the "right" section. Imagine crafted data such that each time the routine must recurse the "righ= t" section is extremely small. Maybe only a few elements wide. This would necessitate a maximum stack depth on the order of N, where N is the number = of elements being sorted. If, however, the routine always chose to sort the *smaller* of the two sub-sections via recursion, then the maximum stack depth would be at worst log2(N). Qsort should test the "width" of each section before recursing, and always choose to sort the smaller one via recursion. This results in an optimally= low worst-case in terms of required stack space. --=20 You are receiving this mail because: You are the assignee for the bug.=