Subject: Re: [PATCH 1/3] add QSORT

From: Kevin Bracey <[email-masked]>
Date: Wed, 05 Oct 2016 18:00:07 +0300

On 04/10/2016 23:31, René Scharfe wrote:

>
> So let's summarize; here's the effect of a raw qsort(3) call:
>
> array == NULL  nmemb  bug  QSORT  following NULL check
> -------------  -----  ---  -----  --------------------
>             0      0  no   qsort  is skipped
>             0     >0  no   qsort  is skipped
>             1      0  no   qsort  is skipped (bad!) ******
>             1     >0  yes  qsort  is skipped ******
>
Right - row 3 may not be a bug from the point of view of your internals, 
but it means you violate the API of qsort.Therefore a fix is required.

> With the micro-optimization removed (nmemb > 0) the matrix gets simpler:
>
> array == NULL  nmemb  bug  QSORT  following NULL check
> -------------  -----  ---  -----  --------------------
>             0      0  no   noop   is executed
>             0     >0  no   qsort  is skipped
>             1      0  no   noop   is executed
>             1     >0  yes  qsort  is skipped ******
>
> And with your NULL check (array != NULL) we'd get:
>
> array == NULL  nmemb  bug  QSORT  following NULL check
> -------------  -----  ---  -----  --------------------
>             0      0  no   qsort  reuses check result
>             0     >0  no   qsort  reuses check result
>             1      0  no   noop   reuses check result
>             1     >0  yes  noop   reuses check result
>
> Did I get it right?  AFAICS all variants (except raw qsort) are safe 
> -- no useful NULL checks are removed, and buggy code should be noticed 
> by segfaults in code accessing the sorted array.
I think your tables are correct.

But I disagree that you could ever call invoking the "****" lines safe. 
Unless you have documentation on what limit GCC (and your other 
compilers) are prepared to put on the undefined behaviour of violating 
that "non-null" constraint.

Up to now dereferencing a null pointer has been implicitly (or 
explicitly?) defined as simply generating SIGSEGV. And that has 
naturally extended into NULL passed to library implementations. But 
that's no longer true - it seems bets are somewhat off.

But, as long as you are confident you never invoke that line without a 
program bug - ie an API precondition of your own QSORT is that NULL is 
legal iff nmemb is zero, then I guess it's fine. Behaviour is defined, 
as long as you don't violate your internal preconditions.

Kevin