I've been trying to figure out the crash in qsort reported here:
http://www.postgresql.org/message-id/flat/CAL8HZuNR2FR1owZHWG-p64GJtNfbbmPx1Y2OXmJ_XuQ3P8YtVA@mail.gmail.com
I first noticed that our qsort code uses an int to hold some transient
values representing numbers of elements. Since the passed array size
argument is a size_t, this is broken; the integer could overflow.
I do not think this is a live bug so far as our core code is concerned,
because tuplesort.c still limits itself to no more than INT_MAX items
to be sorted, and nothing else in the core would even approach that.
However, it's in principle a hazard for third-party modules that might try
to sort more than that; and in any case it's a bug waiting to bite us on
the rear whenever somebody decides they have enough RAM that they should
be able to sort more than INT_MAX items.
However, Yiqing reported the crash as occurring here:
Program terminated with signal 11, Segmentation fault.
#0 0x0000000000785180 in med3_tuple (a=0x7f31613f1028, b=0x7f31613f1040, c=0xffffffff3ffffffd,
cmp_tuple=0x7f43613f1010,state=0x1) at qsort_tuple.c:66
66 {
which is a bit curious because that function does not itself access any
of the data --- it just calls the cmp_tuple function, so even if we'd
somehow computed a bad address, the crash should occur inside the
comparator function, not here.
After awhile a theory occurred to me: the qsort functions recurse without
bothering with a stack depth check, so maybe the SEGV actually represents
running out of stack space. And after a bit of research, that theory
seems pretty plausible. It turns out that qsort is guaranteed to recurse
no deeper than log(N) levels, but *only if you take care to recurse on the
smaller partition and iterate on the larger one*. And we're not doing
that, we just blindly recurse on the left partition. So given a fairly
huge amount of data and some bad luck in partition-picking, it seems
possible that stack overflow explains this report.
I propose to
(1) fix the code to use a size_t variable rather than int where
appropriate;
(2) teach it to recurse on the smaller partition.
It's possible that this issue can only manifest on 9.4 and up where
we have the ability for tuplesort to allocate work arrays approaching
INT_MAX elements. But I don't have a lot of faith in that; I think the
worst-case stack depth for the way we have it now could be as bad as O(N),
so in principle a crash could be possible with significantly smaller input
arrays. I think we'd better back-patch this all the way.
regards, tom lane