Re: New GNU C Library (glibc) security flaw reported on 30 Jan 2024

["Zack Weinberg" <zack@owlfolio.org>]

On Sun, Feb 4, 2024, at 7:58 PM, Paul Eggert wrote:
> While we're on the topic, I reviewed the glibc manual's description of 
> qsort, bsearch and lfind and found other instances where the manual 
> disagrees with POSIX or is otherwise obviously incorrect. Proposed patch 
> attached.

I have a couple of suggestions for improvement to these changes:

[bsearch]
...
> +The @var{array} must consist of all elements that compare less than,
> +equal to, and greater than @var{key}, in that order.

This sentence only makes sense to me because of what you said in the
cover letter, about the array not being required to be totally
ordered.  I’d like to suggest instead

  @var{array} does not need to be totally ordered according to
  @var{compare}.  However, all of the elements of @var{array} that
  compare less than @var{key} must be at lower indices than any
  element that compares equal to @var{key}, and all the elements that
  compare greater than @var{key} must be at higher indices than any
  element that compares equal to @var{key}.

This is long enough that it should probably be its own paragraph.

[qsort]

Not related to what you wrote, but: A later paragraph says “the object
addresses passed to the comparison function lie within the array,”
and C2011 7.22.5p2 actually makes this a hard requirement: “The
implementation shall ensure that both arguments [of the comparison
function called by qsort] are pointers to elements of the array.”
It looks to me like there are situations where our implementation
doesn’t do this: specifically, whenever we aren’t doing indirect
sorting but we *are* using a scratch array, we may call the comparison
function with one argument a pointer into the scratch array.
(This might’ve come up in the discussion about changing out the sort
algorithm, I don’t remember for sure.)  Since it seems like it would
be difficult for _any_ qsort implementation that’s not 100% in-place
to hit this requirement, I’d like to suggest these additional changes to
the qsort section:

@@ search.texi:176 @@
  the elements.  Two elements with the same sort key may differ in other
- respects.
+ respects.  The only way to ensure a stable sort, when @var{compare} does
+ not consider all of the data in the objects being sorted, is to augment
+ each object with a tie-breaking value, such as its original array index.

- Although the object addresses passed to the comparison function lie
- within the array, they need not correspond with the original locations
- of those objects because the sorting algorithm may swap around objects
- in the array before making some comparisons.  The only way to perform
- a stable sort with @code{qsort} is to first augment the objects with a
- monotonic counter of some kind.
+ @strong{Portability Note:} The result of @var{compare} should not depend
+ in any way on the @emph{addresses} of the objects it is comparing.
+ The sorting process might temporarily move objects out of order, so the
+ relative positions of objects within the array are unpredictable during
+ the sort.  In addition, although ISO C specifies that both addresses
+ passed to the comparison function should lie within the array,
+ implementations (including @theglibc{}) often do not fulfill this
+ requirement.  It is common for @code{qsort} to copy objects to temporary
+ storage outside the array, and then compare those copies to each other
+ or to objects still within the array.

zw