Bug 10672 - qsort may not be a stable sort under memory exhaustion
Summary: qsort may not be a stable sort under memory exhaustion
Status: RESOLVED FIXED
Alias: None
Product: glibc
Classification: Unclassified
Component: manual (show other bugs)
Version: 2.10
: P2 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2009-09-20 16:52 IST by Anders Kaseorg
Modified: 2014-12-10 15:50 IST (History)
5 users (show)

See Also:
Host:
Target:
Build:
Last reconfirmed:
fweimer: security-


Attachments
Test program (339 bytes, text/plain)
2009-09-20 16:57 IST, Anders Kaseorg
Details
Remove incorrect claim from manual (984 bytes, patch)
2014-07-01 07:05 IST, Anders Kaseorg
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Anders Kaseorg 2009-09-20 16:52:30 IST
The glibc documentation makes this claim:

http://www.gnu.org/software/libc/manual/html_node/Array-Sort-Function.html

“If you want the effect of a stable sort, you can get this result by writing the 
comparison function so that, lacking other reason distinguish between two 
elements, it compares them by their addresses. Note that doing this may make the 
sorting algorithm less efficient, so do it only if necessary.”

However, under certain conditions on the size of the array and its items, 
qsort() may fall back to an in-place quicksort if it cannot allocate memory for 
a temporary array with malloc().  This algorithm is not a stable sort even if 
the comparison function is written in the described manner.

I will attach a simple test program that demonstrates this.
Comment 1 Anders Kaseorg 2009-09-20 16:57:12 IST
Created attachment 4219 [details]
Test program

This program exhausts all the available heap memory using malloc(), then
attempts to do a stable sort using qsort() as described by the glibc manual. 
As you can see from the output, some items with equal values have been
reordered:

…
0 0
0 0
10 4
10 2
10 3
20 1

If you comment the malloc() exhaustion loop, the sort becomes stable:

…
0 0
0 0
10 2
10 3
10 4
20 1
Comment 2 Rich Felker 2011-10-23 08:17:07 IST
This is a bug in the manual. The text about using the address as part of the comparison function is not only ineffective but actually results in undefined behavior due to violation of the requirements on comparison functions. It should just be removed.
Comment 3 paxdiablo 2014-03-11 07:07:20 IST
It's a well known trick that you can make an unstable sort like Quicksort into a stable one by adding an address to the comparison key as the most minor component.

However, this must be the STARTING address of each element and must be populated before the sort proper starts with something like:

for (int i = 0; i < sz; i++) elem[i].startaddr = &(elem[i]);

By using the starting address as the most minor part of the key, the order of otherwise similarly-keyed elements will be preserved.

Using the TRANSITORY address will not work and in fact will break the sort contract as sometimes a will be less than b and sometimes vice versa, depending on their current address in memory. So, yes, that section of the documentation is dead wrong and should be removed or fixed.

And, in fact, qsort() is not REQUIRED to be stable as per the ISO C standard. If you WANT a stable sort, go grab a copy of Mergesort from somewhere.
Comment 4 Anders Kaseorg 2014-07-01 07:05:12 IST
Created attachment 7665 [details]
Remove incorrect claim from manual
Comment 5 Florian Weimer 2014-07-01 08:11:34 IST
(In reply to Anders Kaseorg from comment #4)
> Created attachment 7665 [details]
> Remove incorrect claim from manual

Could you post this patch to the mailing list for review, please?

I think it is best to remove the problematic wording altogether, not attempting to describe the past behavior of the implementation.
Comment 6 Anders Kaseorg 2014-07-01 08:15:26 IST
Posted: https://sourceware.org/ml/libc-alpha/2014-07/msg00002.html
Comment 7 Ondrej Bilka 2014-12-10 15:50:43 IST
fixed.