Bug 10672

Summary:	qsort may not be a stable sort under memory exhaustion
Product:	glibc	Reporter:	Anders Kaseorg <andersk>
Component:	manual	Assignee:	Not yet assigned to anyone <unassigned>
Status:	RESOLVED FIXED
Severity:	normal	CC:	bugdal, fweimer, glibc-bugs, lynneandallan, neleai
Priority:	P2	Flags:	fweimer: security-
Version:	2.10
Target Milestone:	---
Host:		Target:
Build:		Last reconfirmed:
Attachments:	Test program Remove incorrect claim from manual

Description Anders Kaseorg 2009-09-20 16:52:30 UTC

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 UTC

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 UTC

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 UTC

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 UTC

Created attachment 7665 [details]
Remove incorrect claim from manual

Comment 5 Florian Weimer 2014-07-01 08:11:34 UTC

(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 UTC

Posted: https://sourceware.org/ml/libc-alpha/2014-07/msg00002.html

Comment 7 Ondrej Bilka 2014-12-10 15:50:43 UTC

fixed.