Re: [PATCH 1/3] add QSORT
- From
Kevin Bracey <kevin@bracey.fi>
- Date
- Oct 5, 2016, 15:00 UTC
- Message-ID
- <57F51577.10709@bracey.fi>
- In-Reply-To
- <29d3dde0-c527-3ab8-914c-6fbdc5e81e1c@web.de>
On 04/10/2016 23:31, René Scharfe wrote:
Show 10 quoted lines
> > 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.
Show 21 quoted lines
> 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