Jonathan Leffler via tz <tz@iana.org> writes:

I see nothing in the C standard specification of qsort() that says sorting an array with zero members leads to undefined behaviour.

The C standard is silent on this (at least as of C99), but POSIX is absolutely unambiguous: If the nel argument has the value zero, the comparison function pointed to by compar shall not be called and no rearrangement shall take place.

With all that said, the change is trivial — but could be improved by using the test if (nlinks > 1) so that the code doesn't call qsort for a single-element array either; that is already in sorted order, of course.

Indeed --- testing for nlinks > 1 can be defended on performance grounds, whether or not you think you're dealing with a broken libc. I recall that Postgres used to carry some explicit checks to avoid calling bsearch() with zero elements, because the case was broken on nineties-vintage Solaris. I don't recall anyone ever claiming that any version of qsort() has such an issue. regards, tom lane

On Oct 25, 2022, at 9:34 PM, Jonathan Leffler via tz <tz@iana.org> wrote:

I see nothing in the C standard specification of qsort() that says sorting an array with zero members leads to undefined behaviour.

http://port70.net/~nsz/c/c11/n1570.html#7.22.5.2

I see nothing in C90 through C18 that explicitly say anything about passing NULL as base and 0 as nmemb. What I do see is The qsort function sorts an array of nmemb objects, the initial element of which is pointed to by base. The size of each object is specified by size. (from C18, but they all pretty much say the same thing). However, C18, at least, says An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. The element type shall be complete whenever the array type is specified. Array types are characterized by their element type and by the number of elements in the array. An array type is said to be derived from its element type, and if its element type is T, the array type is sometimes called "array of T". The construction of an array type from an element type is called "array type derivation". emphasis on the "nonempty" There are cases where the array size can be omitted, such as extern int foo[]; or struct bar { int nelem; int elements[]; // flexible array member }; but, in the first case, I'm not sure "foo" could be zero-length (as it would have to be defined elsewhere, and you couldn't just have "int foo[0]"), and in the latter case, you could pass "elements" to qsort(), along with "nelem", but C18, at least, says of this case: As a special case, the last member of a structure with more than one named member may have an incomplete array type; this is called a flexible array member. In most situations, the flexible array member is ignored. In particular, the size of the structure is as if the flexible array member were omitted except that it may have more trailing padding than the omission would imply. However, when a . (or-> ) operator has a left operand that is (a pointer to) a structure with a flexible array member and the right operand names that member, it behaves as if that member were replaced with the longest array (with the same element type) that would not make the structure larger than the object being accessed; the offset of the array shall remain that of the flexible array member, even if this would differ from that of the replacement array. If this array would have no elements, it behaves as if it had one element but the behavior is undefined if any attempt is made to access that element or to generate a pointer one past it. so, in that case, a pointer is generated, but the results of trying to use that pointer are undefined. The specification for qsort() says nothing about whether, if "nmemb" is 0, any attempt is made to reference anything through "base".

The POSIX specification for qsort() is quite clear that sorting zero elements is safe.

https://pubs.opengroup.org/onlinepubs/9699919799/functions/qsort.html

If the nel argument has the value zero, the comparison function pointed to by compar shall not be called and no rearrangement shall take place. is a POSIX addition, not present in the C standard. (It probably *should* be in the C standard, but it isn't in anything between C90 and C18.) So, whilst I'd trust any POSIX-compliant system to handle qsort(NULL, 0, ...) sanely, and I'd trust the MSVC qsort() to handle it sanely based on https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/qsort?view... "This function validates its parameters. If compare or number is NULL, or if base is NULL and number is nonzero, or if width is less than zero, the invalid parameter handler is invoked, as described in Parameter validation." which suggests that they consider "base" being NULL and "number" being 0 to be valid and, presumably to be handled sanely, and given that the qsort() implementation is not guaranteed that any attempt to refer to anything pointed to by "base + i", for i >= nelem, will do anything nasty, thus meaning that if nelem == 0, that's "no guarantees for anything pointed to by base", I would *expect* sane behavior from all qsort() implementations. However, the C standard doesn't, as far as I can tell, *explicitly* require sanity in the nelem == 0 case, so maybe there's some weird implementation out there that looks at *base even if nelem == 0.

On 26/10/2022 06:59, Tom Lane via tz wrote:

Guy Harris via tz <tz@iana.org> writes:

...

On Oct 25, 2022, at 9:34 PM, Jonathan Leffler via tz <tz@iana.org> wrote:

...

I see nothing in the C standard specification of qsort() that says sorting an array with zero members leads to undefined behaviour.

...

I see nothing in C90 through C18 that explicitly say anything about passing NULL as base and 0 as nmemb.

Refreshing my memory about this ... I think the argument hinges on this bit in C99, which applies to all C-specified library functions:

7.1.4 Use of library functions

[#1] Each of the following statements applies unless explicitly stated otherwise in the detailed descriptions that follow: If an argument to a function has an invalid value (such as a value outside the domain of the function, or a pointer outside the address space of the program, or a null pointer) or a type (after promotion) not expected by a ^^^^^^^^^^^^ function with variable number of arguments, the behavior is undefined. If a function argument is described as being an array, the pointer actually passed to the function shall have a value such that all address computations and accesses to objects (that would be valid if the pointer did point to the first element of such an array) are in fact valid.

Also in 7.22.5 Searching and sorting utilities, paragraph 1: [...] Pointer arguments on such a call shall still have valid values, as described in 7.1.4.

There's a faction that thinks that the underlined comment entitles every libc function to halt-and-catch-fire when passed a null pointer. Never mind whether a nearby zero count argument clearly forbids it from making any memory accesses associated with that pointer, as expressed by the immediately following sentence.

I side with Winston Churchill in saying "this is nonsense up with which I shall not put". There are no useful grounds for claiming that qsort, memset, memcpy, etc, with a null pointer and a zero count argument should be undefined. It's merely a gotcha for the unwary programmer. C had a similar gotcha back in the nineties for integer division with negative values ... which they eventually fixed. This needs to get fixed in the language standard, not worked around forevermore.

I tend to agree, and was not really aware of the requirement until today! -- -=( Ian Abbott <abbotti@mev.co.uk> || MEV Ltd. is a company )=- -=( registered in England & Wales. Regd. number: 02862268. )=- -=( Regd. addr.: S11 & 12 Building 67, Europa Business Park, )=- -=( Bird Hall Lane, STOCKPORT, SK3 0XA, UK. || www.mev.co.uk )=-

Paul Eggert wrote:

It's not just an academic point. Without the patch, 'zic /dev/null' dumps core on Fedora 36 x86-64... The core dump occurred because GCC translates this: qsort(links, nlinks, sizeof *links, qsort_linkcmp); as if it were this:

if (nlinks == 0) __builtin_trap(); qsort(links, nlinks, sizeof *links, qsort_linkcmp);

This is an astonishing result. It's hard to imagine it's worthwhile for gcc to perform this "optimization". There are some decent resident language lawyers over on Stack Overflow these days. I asked this question there, and several posters have cited language from C17 which seems (like the Posix language others have mentioned here) to directly contraindicate gcc's behavior: These utilities [qsort, bsearch] make use of a comparison function to search or sort arrays of unspecified type. Where an argument declared as size_t nmemb specifies the length of the array for a function, nmemb can have the value zero on a call to that function; the comparison function is not called, a search finds no matching element, and sorting performs no rearrangement. Pointer arguments on such a call shall still have valid values, as described in 7.1.4. [C17 Sec. 7.22.5] https://stackoverflow.com/questions/74207802/qsort-with-size-0 THe only explanation I can think of is that gcc somehow knows that it is calling a recursive `qsort` implementation where the caller is responsible for terminating the recursion -- but even then, surely the behavior on n == 0 should be to do nothing (that is, as if void qsort() had returned immediately) rathern than to gratuitiously abort! Paul, which version of gcc is this, and what is $(GCC_DEBUG_FLAGS) expanding to?

On 2022-10-26 07:09, Steve Summit via tz wrote:

...

The core dump occurred because GCC translates this: qsort(links, nlinks, sizeof *links, qsort_linkcmp); as if it were this:

if (nlinks == 0) __builtin_trap(); qsort(links, nlinks, sizeof *links, qsort_linkcmp); This is an astonishing result. It's hard to imagine it's worthwhile for gcc to perform this "optimization".

Oh, sorry, it's astonishing because I misread the assembly language that GCC generates. The actual translation looks at links, not nlinks. That is, it's translated as if it were: if (links == NULL) __builtin_trap(); qsort(links, nlinks, sizeof *links, qsort_linkcmp); Sorry about the confusion.

Paul, which version of gcc is this, and what is $(GCC_DEBUG_FLAGS) expanding to?

It's GCC 12.2.1 20220819 (Red Hat 12.2.1-2). $(GCC_DEBUG_FLAGS) is the default in the Makefile, which expands to the long string at the end of this email. The key option here is -fsanitize=undefined, which causes GCC to insert extra checking code to trap in many (but not all) places when behavior is undefined; this explains why GCC pessimized the code here. GCC generates the ud2 instruction because $(GCC_DEBUG_FLAGS) also contains -fsanitize-undefined-trap-on-error. I use this option, despite the hassle it causes when debugging, because it means I don't have to worry about libubsan which can be a configuration problem. I use these debugging options partly to check tzcode's portability. Although qsort(NULL, 0, ...) works fine on most practical platforms, as Clive noted there is (or was) an oddball platform or two that is (or was) verrrry picky about pointers, and for a program like zic where portability is more important than performance, it's nice if zic runs even on oddballs. Clive, do you happen to know what these platforms are (or were), and whether they're still supported? As a practical matter, even though the C standard says that expressions like qsort(NULL, 0, ...) and (char *)NULL + 0 have undefined behavior, any new platform would be verrrry wise to define them to work the same way that most practical platforms do; this is true regardless of what the C standard says. And to some extent this means the C standard is not at the sweetest spot it could be in, as a contract between implementers and programmers. I write and see a lot of code where adding 0 to NULL is expected to yield NULL, and nobody thinks twice about it (nor should they). Here's what $(GCC_DEBUG_FLAGS) expands to in the default build: -DTZDIR='"/usr/share/zoneinfo"' -DGCC_LINT -g3 -O3 -fno-common -fsanitize=undefined -fsanitize-address-use-after-scope -fsanitize-undefined-trap-on-error -fstack-protector -Wall -Wextra -Walloc-size-larger-than=100000 -Warray-bounds=2 -Wbad-function-cast -Wbidi-chars=any,ucn -Wcast-align=strict -Wdate-time -Wdeclaration-after-statement -Wdouble-promotion -Wduplicated-branches -Wduplicated-cond -Wformat=2 -Wformat-overflow=2 -Wformat-signedness -Wformat-truncation -Winit-self -Wlogical-op -Wmissing-declarations -Wmissing-prototypes -Wnested-externs -Wnull-dereference -Wold-style-definition -Woverlength-strings -Wpointer-arith -Wshadow -Wshift-overflow=2 -Wstrict-overflow -Wstrict-prototypes -Wstringop-overflow=4 -Wstringop-truncation -Wsuggest-attribute=cold -Wsuggest-attribute=const -Wsuggest-attribute=format -Wsuggest-attribute=malloc -Wsuggest-attribute=noreturn -Wsuggest-attribute=pure -Wtrampolines -Wundef -Wuninitialized -Wunused-macros -Wuse-after-free=3 -Wvariadic-macros -Wvla -Wwrite-strings -Wno-address -Wno-format-nonliteral -Wno-sign-compare -Wno-type-limits -Wno-unused-parameter

<<On Thu, 27 Oct 2022 07:38:42 +0100, "Clive D.W. Feather via tz" <tz@iana.org> said:

Why not? You're assuming that NULL is represented by 32 or 64 zero bits [1]. That's not what all computers do. Unusual architectures may do something completely different

I don't want to speak for Paul, but I think it is a true statement that such an "unusual architecture" would be unsaleable today. Even CHERI uses all-bits-zero-and-untagged as a null pointer. -GAWollman

On 2022-10-26 23:38, Clive D.W. Feather wrote:

You're assuming that NULL is represented by 32 or 64 zero bits [1].

No, I'm not assuming that. I'm aware of the AS/400 and its successor IBM i, whose C compiler ILE C does not use an all-bits-zero representation for null pointers. But as I understand it, on this legacy platform a pointer is internally represented by a memory space reference plus an offset, and adding 0 to a null pointer (using the ADDSPP instruction[1]) does not modify the offset and still gives you a null pointer. So I am unaware of any platform where (char *)0 + 0 does not give you a null pointer. If I'm right, the C standard's prohibition of (char *)0 + 0 is unnecessarily restrictive, as it prohibits programs that are portable in practice. It wouldn't be the first time that a standard is unnecessarily restrictive. Luckily, when writing free software we're free to ignore standards when they're wrong.... [1] https://www.ibm.com/docs/en/i/7.5?topic=instructions-add-space-pointer-addsp...

On 10/27/22 15:53, Brian Inglis via tz wrote:

Itanium NULL pointer representation is -1:

https://refspecs.linuxfoundation.org/cxxabi-1.75.html

That's talking about null data member pointers, not null pointers. Data member pointers are a C++ concept and are different animals from pointers. Some C++ implementations represent null data member pointers with 0, some with -1 (both ideas work reasonably well). Either way, adding 0 to one gives you the same data member pointer you started off with, namely, a null data member pointer (not that this matters for C).

Paul Eggert <eggert@cs.ucla.edu> writes:

The core dump occurred because GCC translates this:

qsort(links, nlinks, sizeof *links, qsort_linkcmp);

as if it were this:

if (nlinks == 0) __builtin_trap(); qsort(links, nlinks, sizeof *links, qsort_linkcmp);

Right, so they are actually going out of their way to make it a gotcha. What point does that serve? regards, tom lane

On Wed, Oct 26, 2022 at 4:03 AM Paul Eggert via tz <tz@iana.org> wrote:

The core dump occurred because GCC translates this:

qsort(links, nlinks, sizeof *links, qsort_linkcmp);

as if it were this:

if (nlinks == 0) __builtin_trap(); qsort(links, nlinks, sizeof *links, qsort_linkcmp);

That is, if qsort's second argument is zero, the code generated by GCC doesn't call the qsort library function. Instead, it directly executes the ud2 instruction <https://www.felixcloutier.com/x86/ud>, which raises the invalid opcode exception. Presumably this is because the GCC maintainers are in the faction that says a null pointer cannot be used to pass a size-zero object to a library function. This is likely the same faction that says "char *p = NULL; return p + 0;" has undefined behavior.

It seems odd that GCC is testing the counter nlinks and not the pointer links. Passing a null pointer is invalid — §7.10.5, §7.10.5.2, §7.1.4 of the C standard (C99 or later) indicate that. But passing nlinks as zero should not cause any trouble according to C99 or later versions of the C standard, or according to POSIX. The C90 standard is silent on the issue of a zero count. However, I think that TZ code can sidestep the whole issue by using: if (nlinks > 1) qsort(links, nlinks, sizeof(*links), qsort_linkcmp); There's no need to sort arrays of size 0 or 1. This avoids any questions about whether a count of zero is valid as an argument to qsort(). -- Jonathan Leffler <jonathan.leffler@gmail.com> #include <disclaimer.h> Guardian of DBD::Informix - v2018.1031 - http://dbi.perl.org "Blessed are we who can laugh at ourselves, for we shall never cease to be amused."

On 2022-10-26 07:54, Jonathan Leffler wrote:

There's no need to sort arrays of size 0 or 1.

Good point, thanks. I installed the first attached patch to do that. The second patch just fixes spacing as a style matter. Although there's a similar issue with bsearch and arrays with zero members, I didn't add a size-zero check there, as the base pointer must be nonnull when bsearch is called, the C standard says that bsearch does the right thing if you give it a valid non-null pointer and a zero nmemb, and I didn't see much point to adding an optimization there. Whereas with qsort, the base pointer might be null so the code must check for either a null pointer or size zero anyway, so why not check for size 1 as that's nearly as cheap and arguably clearer?

Tom Lane via tz said:

7.1.4 Use of library functions

[#1] Each of the following statements applies unless explicitly stated otherwise in the detailed descriptions that follow: If an argument to a function has an invalid value (such as a value outside the domain of the function, or a pointer outside the address space of the program, or a null pointer) or a type (after promotion) not expected by a ^^^^^^^^^^^^ function with variable number of arguments, the behavior is undefined. If a function argument is described as being an array, the pointer actually passed to the function shall have a value such that all address computations and accesses to objects (that would be valid if the pointer did point to the first element of such an array) are in fact valid.

There's a faction that thinks that the underlined comment entitles every libc function to halt-and-catch-fire when passed a null pointer.

They're right.

Never mind whether a nearby zero count argument clearly forbids it from making any memory accesses associated with that pointer, as expressed by the immediately following sentence.

No, because the implementation might do something like: endptr = (unsigned char *) base + nmemb * size; before (or after) checking the value of nmemb.

I side with Winston Churchill in saying "this is nonsense up with which I shall not put".

Actually, he didn't say it.

There are no useful grounds for claiming that qsort, memset, memcpy, etc, with a null pointer and a zero count argument should be undefined.

There are, or were, implementers who disagree with you. -- Clive D.W. Feather | If you lie to the compiler, Email: clive@davros.org | it will get its revenge. Web: http://www.davros.org | - Henry Spencer Mobile: +44 7973 377646

On 2022-10-26 11:55, Garrett Wollman via tz wrote:

In a perhaps less ridiculous case, undefined behavior when such a library function is called with a null pointer for a source argument allows the implementation (especially an inlining compiler) to pre-warm the d-cache before entering the main loop.

Unless I'm misunderstanding your example this sort of optimization cannot be done for qsort, since the base pointer can be valid and non-null but not dereferencable, e.g., qsort has well-defined behavior if the pointer points one past the end of an array and nmemb is zero.