Re: [PATCH 1/3] add QSORT

From: Kevin Bracey <kevin@bracey.fi>
Date: Oct 3, 2016, 16:46 UTC
Message-ID: <57F28B6B.1010204@bracey.fi>
In-Reply-To: <83398160-555f-adab-6b1e-3283c533b5ff@web.de>

On 01/10/2016 19:19, René Scharfe wrote:

Show 16 quoted lines

> It's hard to imagine an implementation of qsort(3) that can't handle
> zero elements.  QSORT's safety feature is that it prevents the compiler
> from removing NULL checks for the array pointer.  E.g. the last two
> lines in the following example could be optimized away:
>
> 	qsort(ptr, n, sizeof(*ptr), fn);
> 	if (!ptr)
> 		do_stuff();
>
> You can see that on https://godbolt.org/g/JwS99b -- an awesome website
> for exploring compilation results for small snippets, by the way.
>
> This optimization is dangerous when combined with the convention of
> using a NULL pointer for empty arrays.  Diagnosing an affected NULL
> check is probably quite hard -- it's right there in the code after all
> and not all compilers remove it.

Hang on, hang on. This is either a compiler bug, or you're wrong on your assumption about the specification of qsort.

Either way, the extra layer of indirection is not proper protection. The unwanted compiler optimisation you're inadvertently triggering could still be triggered through the inline.

Now, looking at the C standard, this isn't actually clear to me. The standard says that if you call qsort with nmemb zero, the pointer still has to be "valid". Not totally clear to me if NULL is valid, by their definition in C99 7.1.4. Googling hasn't given me a concrete answer.

The compiler seems to think that NULL wouldn't be valid, so because you've called qsort on it, you've invoked undefined behaviour if it's NULL, so it's free to elide the NULL check.

Kevin