qsort(3) can overflow stack in pathological cases
qsort(3)
is a pure quicksort, which can recurse O(n) times in a pathological case. Since all qsort(3)
recursion is implemented as normal C recursion, this may use a lot of stack space. The pathological case is one where all of the items end up being sorted into one side of the pivot, e.g. when all the lines are the same. As of 2021-12-03 rw -i /dev/zero -c 4093 | tr '\0' '\n' | sort
on volatile (and most likely also on nightly, but I have not tested this) segfaults, but adjusting count to 4092
is just below the limit.
Attached are patched versions on sort.c and qsort_r.c as well as the output produced by cc -o sort sort.c qsort_r.c && rw -i /dev/zero -c 8000 | tr '\0' '\n' | ./sort
which I used to diagnose the problem