[Bug 213922] crafted data could cause qsort to exhaust stack space
bugzilla-noreply at freebsd.org
bugzilla-noreply at freebsd.org
Sun Oct 30 20:10:31 UTC 2016
https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=213922
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 at FreeBSD.org
Reporter: jhoward at 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. However,
it always sorts the "left" section by recursion, even when it is large relative
to the "right" section.
Imagine crafted data such that each time the routine must recurse the "right"
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.
--
You are receiving this mail because:
You are the assignee for the bug.
More information about the freebsd-bugs
mailing list