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

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

[Turritopsis Dohrnii Teo En Ming]

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

Good day from Singapore,

I recently stumbled upon this insightful article and wanted to share it with you.

Article: New Linux glibc flaw lets attackers get root on major distros
Link: https://www.bleepingcomputer.com/news/security/new-linux-glibc-flaw-lets-attackers-get-root-on-major-distros/

Thank you.

Regards,

Mr. Turritopsis Dohrnii Teo En Ming
Targeted Individual in Singapore
Blogs:
https://tdtemcerts.blogspot.com
https://tdtemcerts.wordpress.com
GIMP also stands for Government-Induced Medical Problems.

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

[Xi Ruoyao]

On Wed, 2024-01-31 at 14:08 +0000, Turritopsis Dohrnii Teo En Ming
wrote:
> Subject: New GNU C Library (glibc) security flaw reported on 30 Jan 2024
> 
> Good day from Singapore,
> 
> I recently stumbled upon this insightful article and wanted to share it with you.
> 
> Article: New Linux glibc flaw lets attackers get root on major distros
> Link: https://www.bleepingcomputer.com/news/security/new-linux-glibc-flaw-lets-attackers-get-root-on-major-distros/

I cannot see why https://www.qualys.com/2024/01/30/qsort.txt is a
**Glibc** security issue.  The standard is clear that if you pass a non-
transitive comparator to qsort, you invoke an undefined behavior.

While Glibc can try to make qsort "robust" due to the Hyrum rule, the
real security issue is in the programs calling qsort with bad
comparators.  Even if Glibc makes qsort "robust" those programs are
still vulnerable with a different libc.  Yes there is some security
issue, but the CVE numbers should be assigned to those broken programs,
not Glibc.

-- 
Xi Ruoyao <xry111@xry111.site>
School of Aerospace Science and Technology, Xidian University

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

[Vincent Lefevre]

On 2024-01-31 22:23:32 +0800, Xi Ruoyao wrote:
> On Wed, 2024-01-31 at 14:08 +0000, Turritopsis Dohrnii Teo En Ming
> wrote:
> > Subject: New GNU C Library (glibc) security flaw reported on 30 Jan 2024
> > 
> > Good day from Singapore,
> > 
> > I recently stumbled upon this insightful article and wanted to share it with you.
> > 
> > Article: New Linux glibc flaw lets attackers get root on major distros
> > Link: https://www.bleepingcomputer.com/news/security/new-linux-glibc-flaw-lets-attackers-get-root-on-major-distros/
> 
> I cannot see why https://www.qualys.com/2024/01/30/qsort.txt is a
> **Glibc** security issue.  The standard is clear that if you pass a non-
> transitive comparator to qsort, you invoke an undefined behavior.

This is what the ISO C standard says. But the glibc manual explicitly
allows non-transitive comparators.

See the example in 9.1 Defining the Comparison Function:

   Here is an example of a comparison function which works with an array
of numbers of type ‘double’:

     int
     compare_doubles (const void *a, const void *b)
     {
       const double *da = (const double *) a;
       const double *db = (const double *) b;

       return (*da > *db) - (*da < *db);
     }

The non-transitivity can be demonstrated with the following test
program:

#include <stdio.h>
#include <math.h>

int
compare_doubles (const void *a, const void *b)
{
  const double *da = (const double *) a;
  const double *db = (const double *) b;

  return (*da > *db) - (*da < *db);
}

int main (void)
{
  double t[3] = { 1.0, NAN, 2.0 };
  printf ("%d\n", compare_doubles(t+0, t+1));
  printf ("%d\n", compare_doubles(t+1, t+2));
  printf ("%d\n", compare_doubles(t+0, t+2));
  return 0;
}

which gives

0
0
-1

while the initial 0 0 implies a third 0 with a transitive comparator.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

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

[Adhemerval Zanella Netto]

On 31/01/24 11:55, Vincent Lefevre wrote:
> On 2024-01-31 22:23:32 +0800, Xi Ruoyao wrote:
>> On Wed, 2024-01-31 at 14:08 +0000, Turritopsis Dohrnii Teo En Ming
>> wrote:
>>> Subject: New GNU C Library (glibc) security flaw reported on 30 Jan 2024
>>>
>>> Good day from Singapore,
>>>
>>> I recently stumbled upon this insightful article and wanted to share it with you.
>>>
>>> Article: New Linux glibc flaw lets attackers get root on major distros
>>> Link: https://www.bleepingcomputer.com/news/security/new-linux-glibc-flaw-lets-attackers-get-root-on-major-distros/
>>
>> I cannot see why https://www.qualys.com/2024/01/30/qsort.txt is a
>> **Glibc** security issue.  The standard is clear that if you pass a non-
>> transitive comparator to qsort, you invoke an undefined behavior.
> 
> This is what the ISO C standard says. But the glibc manual explicitly
> allows non-transitive comparators.
> 
> See the example in 9.1 Defining the Comparison Function:
> 
>    Here is an example of a comparison function which works with an array
> of numbers of type ‘double’:
> 
>      int
>      compare_doubles (const void *a, const void *b)
>      {
>        const double *da = (const double *) a;
>        const double *db = (const double *) b;
> 
>        return (*da > *db) - (*da < *db);
>      }
> 
> The non-transitivity can be demonstrated with the following test
> program:
> 
> #include <stdio.h>
> #include <math.h>
> 
> int
> compare_doubles (const void *a, const void *b)
> {
>   const double *da = (const double *) a;
>   const double *db = (const double *) b;
> 
>   return (*da > *db) - (*da < *db);
> }
> 
> int main (void)
> {
>   double t[3] = { 1.0, NAN, 2.0 };
>   printf ("%d\n", compare_doubles(t+0, t+1));
>   printf ("%d\n", compare_doubles(t+1, t+2));
>   printf ("%d\n", compare_doubles(t+0, t+2));
>   return 0;
> }
> 
> which gives
> 
> 0
> 0
> -1
> 
> while the initial 0 0 implies a third 0 with a transitive comparator.
> 

I see this is an manual issue rather than a GNU 'extension' to qsort semantic.
And I think we should fix BZ#31322 by using a transitive comparison instead of
trying to support such cases.

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

[Vincent Lefevre]

On 2024-01-31 12:52:35 -0300, Adhemerval Zanella Netto wrote:
> On 31/01/24 11:55, Vincent Lefevre wrote:
[...]
> > This is what the ISO C standard says. But the glibc manual explicitly
> > allows non-transitive comparators.
> > 
> > See the example in 9.1 Defining the Comparison Function:
> > 
> >    Here is an example of a comparison function which works with an array
> > of numbers of type ‘double’:
> > 
> >      int
> >      compare_doubles (const void *a, const void *b)
> >      {
> >        const double *da = (const double *) a;
> >        const double *db = (const double *) b;
> > 
> >        return (*da > *db) - (*da < *db);
> >      }
> > 
> > The non-transitivity can be demonstrated with the following test
> > program:
> > 
> > #include <stdio.h>
> > #include <math.h>
> > 
> > int
> > compare_doubles (const void *a, const void *b)
> > {
> >   const double *da = (const double *) a;
> >   const double *db = (const double *) b;
> > 
> >   return (*da > *db) - (*da < *db);
> > }
> > 
> > int main (void)
> > {
> >   double t[3] = { 1.0, NAN, 2.0 };
> >   printf ("%d\n", compare_doubles(t+0, t+1));
> >   printf ("%d\n", compare_doubles(t+1, t+2));
> >   printf ("%d\n", compare_doubles(t+0, t+2));
> >   return 0;
> > }
> > 
> > which gives
> > 
> > 0
> > 0
> > -1
> > 
> > while the initial 0 0 implies a third 0 with a transitive comparator.
> 
> I see this is an manual issue rather than a GNU 'extension' to qsort semantic.
> And I think we should fix BZ#31322 by using a transitive comparison instead of
> trying to support such cases.

If this was intentional, users may already use such a nontransitive
comparison function. If this was not intentional, this shows that
the problem is not obvious and that users less experienced than the
glibc developers may fall in such a trap. So, in addition to make
the glibc manual clear on the subject, I think that the library
should handle such cases gracefully rather than considering that
such cases will never occur. For instance, this could be just an
indeterminate ordering. Or if the goal is to warn the user about
the issue (in case it is detected), an assertion failure instead
of indeterminate ordering.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

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

[Siddhesh Poyarekar]

On 2024-01-31 11:23, Vincent Lefevre wrote:
> If this was intentional, users may already use such a nontransitive
> comparison function. If this was not intentional, this shows that
> the problem is not obvious and that users less experienced than the
> glibc developers may fall in such a trap. So, in addition to make
> the glibc manual clear on the subject, I think that the library
> should handle such cases gracefully rather than considering that
> such cases will never occur. For instance, this could be just an
> indeterminate ordering. Or if the goal is to warn the user about
> the issue (in case it is detected), an assertion failure instead
> of indeterminate ordering.
> 

The advisory[1] has a statement on behalf of the glibc security team, 
reproduced here for convenience:

~~~
This memory corruption in the GNU C Library through the qsort function 
is invoked by an application passing a non-transitive comparison 
function, which is undefined according to POSIX and ISO C standards.  As 
a result, we are of the opinion that the resulting CVE, if any, should 
be assigned to any such calling applications and subsequently fixed by 
passing a valid comparison function to qsort and not to glibc.  We 
however acknowledge that this is a quality of implementation issue and 
we fixed this in a recent refactor of qsort.  We would like to thank 
Qualys for sharing their findings and helping us validate our recent 
changes to qsort.
~~~

Hopefully this addresses your concern; the current glibc implementation 
*is* robust to these issues (the advisory explicitly calls that out) but 
the manual also needs to be fixed so that we don't give the incorrect 
impression that this is a GNU extension.

Thanks,
Sid

[1] https://www.qualys.com/2024/01/30/qsort.txt

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

[Xi Ruoyao]

On Wed, 2024-01-31 at 12:52 -0300, Adhemerval Zanella Netto wrote:

/* snip */

> 
> I see this is an manual issue rather than a GNU 'extension' to qsort semantic.
> And I think we should fix BZ#31322 by using a transitive comparison instead of
> trying to support such cases.

To me the documentation is correct (though arguably in a very subtle
way):

   Here is an example of a comparison function which works with an array
of numbers of type ‘double’:

     int
     compare_doubles (const void *a, const void *b)
     {
       const double *da = (const double *) a;
       const double *db = (const double *) b;

       return (*da > *db) - (*da < *db);
     }

It says "numbers."  But NaN literally means, "Not a Number."  C23 says:

Floating types shall be able to represent signed zeros or an unsigned
zero and all normalized floating-point numbers. In addition, floating
types may be able to contain other kinds of floating-point numbers, such
as subnormal floating-point numbers and unnormalized floating-point
numbers, and values that are not floating-point numbers, such as NaNs
and (signed and unsigned) infinities.  A NaN is a value signifying Not-
a-Number.

So at least in C23 it's clear that NaN and infinite values are not
numbers.

-- 
Xi Ruoyao <xry111@xry111.site>
School of Aerospace Science and Technology, Xidian University

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

[Vincent Lefevre]

On 2024-02-01 02:47:18 +0800, Xi Ruoyao wrote:
> On Wed, 2024-01-31 at 12:52 -0300, Adhemerval Zanella Netto wrote:
> 
> /* snip */
> 
> > 
> > I see this is an manual issue rather than a GNU 'extension' to qsort semantic.
> > And I think we should fix BZ#31322 by using a transitive comparison instead of
> > trying to support such cases.
> 
> To me the documentation is correct (though arguably in a very subtle
> way):
> 
>    Here is an example of a comparison function which works with an array
> of numbers of type ‘double’:
> 
>      int
>      compare_doubles (const void *a, const void *b)
>      {
>        const double *da = (const double *) a;
>        const double *db = (const double *) b;
> 
>        return (*da > *db) - (*da < *db);
>      }
> 
> It says "numbers."  But NaN literally means, "Not a Number."

Yes, the point is to sort numbers. But since NaN may occur, the code
must not yield undefined behavior in such a case. This is the goal
of NaN: avoid undefined behavior for operations that do not make any
sense, and be able to detect errors at the end.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

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

[Vincent Lefevre]

On 2024-02-01 01:51:55 +0100, Vincent Lefevre wrote:
> Yes, the point is to sort numbers. But since NaN may occur, the code
> must not yield undefined behavior in such a case. This is the goal
> of NaN: avoid undefined behavior for operations that do not make any
> sense, and be able to detect errors at the end.

BTW, note that the ISO C standard sometimes uses "number" even
when this can be a NaN. For instance, in 7.12.7.2:

  The fabs functions compute the absolute value of a
  floating-point number x.

(though this has been changed in C23). But the term "number"
is still used in C23 for ceil and floor.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

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

[Xi Ruoyao]

On Thu, 2024-02-01 at 01:51 +0100, Vincent Lefevre wrote:
> On 2024-02-01 02:47:18 +0800, Xi Ruoyao wrote:
> > On Wed, 2024-01-31 at 12:52 -0300, Adhemerval Zanella Netto wrote:
> > 
> > /* snip */
> > 
> > > 
> > > I see this is an manual issue rather than a GNU 'extension' to qsort semantic.
> > > And I think we should fix BZ#31322 by using a transitive comparison instead of
> > > trying to support such cases.
> > 
> > To me the documentation is correct (though arguably in a very subtle
> > way):
> > 
> >    Here is an example of a comparison function which works with an array
> > of numbers of type ‘double’:
> > 
> >      int
> >      compare_doubles (const void *a, const void *b)
> >      {
> >        const double *da = (const double *) a;
> >        const double *db = (const double *) b;
> > 
> >        return (*da > *db) - (*da < *db);
> >      }
> > 
> > It says "numbers."  But NaN literally means, "Not a Number."
> 
> Yes, the point is to sort numbers. But since NaN may occur, the code
> must not yield undefined behavior in such a case. This is the goal
> of NaN: avoid undefined behavior for operations that do not make any
> sense, and be able to detect errors at the end.

When we sort *numbers* NaN cannot be passed to the comparator.  The
standard disallows qsort to randomly construct a value not in the array
and compare it with the provided comparator:

   The implementation shall ensure that the second argument of the
   comparison function (when called from bsearch), or both arguments
   (when called from qsort), are pointers to elements of the array.  The
   first argument when called from bsearch shall equal key.
   
If the Glibc qsort implementation really construct an NaN and then compare
it with something using the comparator, then this qsort implementation
would be completely wrong and we should assign a CVE number for Glibc.  But
if I read the advisory correct this has not happened, at all.

So if the programmer knows for sure he's sorting an array of numbers,
this comparator is perfectly correct.  It's only wrong when there is one
or multiple NaN in the array.

And I doubt if silently producing a NaN is really good for error
detection.  Simply crashing when an invalid operation happens is easier
for debugging, IMO.  And it's possible with "feenableexcept
(FE_INVALID)" (where FP exceptions are supported).

-- 
Xi Ruoyao <xry111@xry111.site>
School of Aerospace Science and Technology, Xidian University

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

[Vincent Lefevre]

On 2024-02-01 14:41:04 +0800, Xi Ruoyao wrote:
> On Thu, 2024-02-01 at 01:51 +0100, Vincent Lefevre wrote:
> > On 2024-02-01 02:47:18 +0800, Xi Ruoyao wrote:
> > > On Wed, 2024-01-31 at 12:52 -0300, Adhemerval Zanella Netto wrote:
> > > 
> > > /* snip */
> > > 
> > > > 
> > > > I see this is an manual issue rather than a GNU 'extension' to qsort semantic.
> > > > And I think we should fix BZ#31322 by using a transitive comparison instead of
> > > > trying to support such cases.
> > > 
> > > To me the documentation is correct (though arguably in a very subtle
> > > way):
> > > 
> > >    Here is an example of a comparison function which works with an array
> > > of numbers of type ‘double’:
> > > 
> > >      int
> > >      compare_doubles (const void *a, const void *b)
> > >      {
> > >        const double *da = (const double *) a;
> > >        const double *db = (const double *) b;
> > > 
> > >        return (*da > *db) - (*da < *db);
> > >      }
> > > 
> > > It says "numbers."  But NaN literally means, "Not a Number."
> > 
> > Yes, the point is to sort numbers. But since NaN may occur, the code
> > must not yield undefined behavior in such a case. This is the goal
> > of NaN: avoid undefined behavior for operations that do not make any
> > sense, and be able to detect errors at the end.
> 
> When we sort *numbers* NaN cannot be passed to the comparator.

What I mean is that the intent is to sort numbers. But in any case,
the code needs to consider that NaN may occur; the result would be
an array in an indeterminate order, but the code must not produce
undefined behavior with consequences like memory corruption. If the
code is designed considering that NaN cannot occur, e.g. because
the user is required to ensure that before calling qsort, then
this must explicitly be documented with a non-ambiguous vocabulary
(typically using "assume").

> And I doubt if silently producing a NaN is really good for error
> detection. Simply crashing when an invalid operation happens is
> easier for debugging, IMO. And it's possible with "feenableexcept
> (FE_INVALID)" (where FP exceptions are supported).

Silently producing a NaN on "invalid" inputs is what happens in
practice, following the spec of the IEEE 754 standard. For instance,
sqrt(-1.) silently returns NaN (a flag is also set). But in general,
the user will not check for NaN (by testing the value or the flag)
after every operation/function, even when it is known that they can
generate a NaN. He will let NaN propagate (the flag can also be
checked later as it is sticky).

Note also that getting a NaN does not necessarily mean that the
program is buggy: after a sequence of computations, there may be
code to decide what to do when a NaN is obtained. So enabling
traps for FE_INVALID is not necessarily correct.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

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

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 134 bytes --]

No matter what we do to the qsort implementation, the manual should 
avoid any confusion about qsorting NaNs. Proposed patch attached.

[-- Attachment #2: 0001-stdlib-fix-qsort-example-in-manual.patch --]
[-- Type: text/x-patch, Size: 2107 bytes --]

From 8ff74efcc11a77e221808293ed390faf6dea86fe Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Thu, 1 Feb 2024 11:52:46 -0800
Subject: [PATCH] stdlib: fix qsort example in manual

* manual/search.texi (Comparison Functions, Array Sort Function):
Sort an array of long ints, not doubles, to avoid hassles
with NaNs.
---
 manual/search.texi | 21 ++++++++++++---------
 1 file changed, 12 insertions(+), 9 deletions(-)

diff --git a/manual/search.texi b/manual/search.texi
index ffaadc46f5..db577a5332 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -35,19 +35,22 @@ second, zero if they are ``equal'', and positive if the first argument
 is ``greater''.
 
 Here is an example of a comparison function which works with an array of
-numbers of type @code{double}:
+numbers of type @code{long int}:
 
 @smallexample
 int
-compare_doubles (const void *a, const void *b)
+compare_long_ints (const void *a, const void *b)
 @{
-  const double *da = (const double *) a;
-  const double *db = (const double *) b;
+  const long int *la = a;
+  const long int *lb = b;
 
-  return (*da > *db) - (*da < *db);
+  return (*la > *lb) - (*la < *lb);
 @}
 @end smallexample
 
+(The code would have to be more complicated for an array of @code{double},
+to handle NaNs correctly.)
+
 The header file @file{stdlib.h} defines a name for the data type of
 comparison functions.  This type is a GNU extension.
 
@@ -183,16 +186,16 @@ 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.
 
-Here is a simple example of sorting an array of doubles in numerical
+Here is a simple example of sorting an array of @code{long int} in numerical
 order, using the comparison function defined above (@pxref{Comparison
 Functions}):
 
 @smallexample
 @{
-  double *array;
-  int size;
+  long int *array;
+  size_t nmemb;
   @dots{}
-  qsort (array, size, sizeof (double), compare_doubles);
+  qsort (array, nmemb, sizeof *array, compare_long_ints);
 @}
 @end smallexample
 
-- 
2.40.1

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

[Siddhesh Poyarekar]

On 2024-02-01 14:55, Paul Eggert wrote:
> From 8ff74efcc11a77e221808293ed390faf6dea86fe Mon Sep 17 00:00:00 2001
> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Thu, 1 Feb 2024 11:52:46 -0800
> Subject: [PATCH] stdlib: fix qsort example in manual
> 
> * manual/search.texi (Comparison Functions, Array Sort Function):
> Sort an array of long ints, not doubles, to avoid hassles
> with NaNs.
> ---
>  manual/search.texi | 21 ++++++++++++---------
>  1 file changed, 12 insertions(+), 9 deletions(-)

Reviewed-by: Siddhesh Poyarekar <siddhesh@sourceware.org>

> 
> diff --git a/manual/search.texi b/manual/search.texi
> index ffaadc46f5..db577a5332 100644
> --- a/manual/search.texi
> +++ b/manual/search.texi
> @@ -35,19 +35,22 @@ second, zero if they are ``equal'', and positive if the first argument
>  is ``greater''.
>  
>  Here is an example of a comparison function which works with an array of
> -numbers of type @code{double}:
> +numbers of type @code{long int}:
>  
>  @smallexample
>  int
> -compare_doubles (const void *a, const void *b)
> +compare_long_ints (const void *a, const void *b)
>  @{
> -  const double *da = (const double *) a;
> -  const double *db = (const double *) b;
> +  const long int *la = a;
> +  const long int *lb = b;
>  
> -  return (*da > *db) - (*da < *db);
> +  return (*la > *lb) - (*la < *lb);
>  @}
>  @end smallexample
>  
> +(The code would have to be more complicated for an array of @code{double},
> +to handle NaNs correctly.)
> +
>  The header file @file{stdlib.h} defines a name for the data type of
>  comparison functions.  This type is a GNU extension.
>  
> @@ -183,16 +186,16 @@ 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.
>  
> -Here is a simple example of sorting an array of doubles in numerical
> +Here is a simple example of sorting an array of @code{long int} in numerical
>  order, using the comparison function defined above (@pxref{Comparison
>  Functions}):
>  
>  @smallexample
>  @{
> -  double *array;
> -  int size;
> +  long int *array;
> +  size_t nmemb;
>    @dots{}
> -  qsort (array, size, sizeof (double), compare_doubles);
> +  qsort (array, nmemb, sizeof *array, compare_long_ints);
>  @}
>  @end smallexample
>  
> -- 
> 2.40.1

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

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 225 bytes --]

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.

[-- Attachment #2: 0001-Fix-bsearch-qsort-etc.-doc-to-match-POSIX-better.patch --]
[-- Type: text/x-patch, Size: 4407 bytes --]

From 50093b1cb8859fec0ee7ce831c6eec6d8aa43ee9 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sun, 4 Feb 2024 16:53:22 -0800
Subject: [PATCH] Fix bsearch, qsort etc. doc to match POSIX better
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* manual/search.texi (Array Search Function):
Correct the statement about lfind’s mean runtime:
it is proportional to a number (not that number),
and this is true only if random elements are searched for.
Relax the constraint on bsearch’s array argument:
POSIX says it need not be sorted, only partially sorted.
Say that the first arg passed to bsearch’s comparison function
is the key, and the second arg is an array element, as
POSIX requires.  For bsearch and qsort, say that the
comparison function should not alter the array, as POSIX
requires.  For qsort, say that the comparison function
must define a total order, as POSIX requires.
---
 manual/search.texi | 25 +++++++++++++++----------
 1 file changed, 15 insertions(+), 10 deletions(-)

diff --git a/manual/search.texi b/manual/search.texi
index db577a5332..8efb70692d 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -84,8 +84,9 @@ The return value is a pointer to the matching element in the array
 starting at @var{base} if it is found.  If no matching element is
 available @code{NULL} is returned.
 
-The mean runtime of this function is @code{*@var{nmemb}}/2.  This
-function should only be used if elements often get added to or deleted from
+The mean runtime of this function is proportional to @code{*@var{nmemb}/2},
+assuming random elements of the array are searched for.  This
+function should be used only if elements often get added to or deleted from
 the array in which case it might not be useful to sort the array before
 searching.
 @end deftypefun
@@ -122,24 +123,26 @@ bytes.  If one is sure the element is in the array it is better to use
 calling @code{lsearch}.
 @end deftypefun
 
-To search a sorted array for an element matching the key, use the
-@code{bsearch} function.  The prototype for this function is in
+To search a sorted or partially sorted array for an element matching the key,
+use the @code{bsearch} function.  The prototype for this function is in
 the header file @file{stdlib.h}.
 @pindex stdlib.h
 
 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
 @standards{ISO, stdlib.h}
 @safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}}
-The @code{bsearch} function searches the sorted array @var{array} for an object
+The @code{bsearch} function searches @var{array} for an object
 that is equivalent to @var{key}.  The array contains @var{count} elements,
 each of which is of size @var{size} bytes.
 
 The @var{compare} function is used to perform the comparison.  This
-function is called with two pointer arguments and should return an
+function is called with arguments that point to the key and to an
+array element, in that order, and should return an
 integer less than, equal to, or greater than zero corresponding to
-whether its first argument is considered less than, equal to, or greater
-than its second argument.  The elements of the @var{array} must already
-be sorted in ascending order according to this comparison function.
+whether the key is considered less than, equal to, or greater than
+the array element.  The function should not alter the array's contents.
+The @var{array} must consist of all elements that compare less than,
+equal to, and greater than @var{key}, in that order.
 
 The return value is a pointer to the matching array element, or a null
 pointer if no match is found.  If the array contains more than one element
@@ -170,7 +173,9 @@ The @var{compare} function is used to perform the comparison on the
 array elements.  This function is called with two pointer arguments and
 should return an integer less than, equal to, or greater than zero
 corresponding to whether its first argument is considered less than,
-equal to, or greater than its second argument.
+equal to, or greater than its second argument.  The function should
+be consistent with a total ordering on the array elements' values,
+and should not alter the array's contents.
 
 @cindex stable sorting
 @strong{Warning:} If two objects compare as equal, their order after
-- 
2.40.1

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

[Zack Weinberg]

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

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

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 1299 bytes --]

On 2/6/24 07:00, Zack Weinberg wrote:

> 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

Good point about saying explicitly that the array need not be sorted. We 
can add "Although the @var{array} need not be completely sorted,". Done 
in the attached revised patch.

However, the paraphrase you sent was too generous, as it allowed the 
array to be in completely random order if it had no matching element. 
Although I think glibc bsearch works in that case, we're likely better 
off sticking with POSIXish wording.


> 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:

I don't see that in the glibc source. Are you sure about that?

If glibc qsort passes addresses outside the array to the comparison 
function, then it's busted and should get fixed.

[-- Attachment #2: 0001-Fix-bsearch-qsort-etc.-doc-to-match-POSIX-better.patch --]
[-- Type: text/x-patch, Size: 4455 bytes --]

From 22837cc7c7f2ab98b823e620c1fa122cd9ad2afa Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sun, 4 Feb 2024 16:53:22 -0800
Subject: [PATCH v2] Fix bsearch, qsort etc. doc to match POSIX better
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* manual/search.texi (Array Search Function):
Correct the statement about lfind’s mean runtime:
it is proportional to a number (not that number),
and this is true only if random elements are searched for.
Relax the constraint on bsearch’s array argument:
POSIX says it need not be sorted, only partially sorted.
Say that the first arg passed to bsearch’s comparison function
is the key, and the second arg is an array element, as
POSIX requires.  For bsearch and qsort, say that the
comparison function should not alter the array, as POSIX
requires.  For qsort, say that the comparison function
must define a total order, as POSIX requires.
---
 manual/search.texi | 26 ++++++++++++++++----------
 1 file changed, 16 insertions(+), 10 deletions(-)

diff --git a/manual/search.texi b/manual/search.texi
index db577a5332..f3de84401d 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -84,8 +84,9 @@ The return value is a pointer to the matching element in the array
 starting at @var{base} if it is found.  If no matching element is
 available @code{NULL} is returned.
 
-The mean runtime of this function is @code{*@var{nmemb}}/2.  This
-function should only be used if elements often get added to or deleted from
+The mean runtime of this function is proportional to @code{*@var{nmemb}/2},
+assuming random elements of the array are searched for.  This
+function should be used only if elements often get added to or deleted from
 the array in which case it might not be useful to sort the array before
 searching.
 @end deftypefun
@@ -122,24 +123,27 @@ bytes.  If one is sure the element is in the array it is better to use
 calling @code{lsearch}.
 @end deftypefun
 
-To search a sorted array for an element matching the key, use the
-@code{bsearch} function.  The prototype for this function is in
+To search a sorted or partially sorted array for an element matching the key,
+use the @code{bsearch} function.  The prototype for this function is in
 the header file @file{stdlib.h}.
 @pindex stdlib.h
 
 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
 @standards{ISO, stdlib.h}
 @safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}}
-The @code{bsearch} function searches the sorted array @var{array} for an object
+The @code{bsearch} function searches @var{array} for an object
 that is equivalent to @var{key}.  The array contains @var{count} elements,
 each of which is of size @var{size} bytes.
 
 The @var{compare} function is used to perform the comparison.  This
-function is called with two pointer arguments and should return an
+function is called with arguments that point to the key and to an
+array element, in that order, and should return an
 integer less than, equal to, or greater than zero corresponding to
-whether its first argument is considered less than, equal to, or greater
-than its second argument.  The elements of the @var{array} must already
-be sorted in ascending order according to this comparison function.
+whether the key is considered less than, equal to, or greater than
+the array element.  The function should not alter the array's contents.
+Although the @var{array} need not be completely sorted,
+it must consist of all elements that compare less than,
+equal to, and greater than @var{key}, in that order.
 
 The return value is a pointer to the matching array element, or a null
 pointer if no match is found.  If the array contains more than one element
@@ -170,7 +174,9 @@ The @var{compare} function is used to perform the comparison on the
 array elements.  This function is called with two pointer arguments and
 should return an integer less than, equal to, or greater than zero
 corresponding to whether its first argument is considered less than,
-equal to, or greater than its second argument.
+equal to, or greater than its second argument.  The function should
+be consistent with a total ordering on the array elements' values,
+and should not alter the array's contents.
 
 @cindex stable sorting
 @strong{Warning:} If two objects compare as equal, their order after
-- 
2.43.0

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

[Xi Ruoyao]

On Tue, 2024-02-06 at 13:30 -0800, Paul Eggert wrote:
> On 2/6/24 07:00, Zack Weinberg wrote:
> 
> > 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
> 
> Good point about saying explicitly that the array need not be sorted. We 
> can add "Although the @var{array} need not be completely sorted,". Done 
> in the attached revised patch.
> 
> However, the paraphrase you sent was too generous, as it allowed the 
> array to be in completely random order if it had no matching element. 
> Although I think glibc bsearch works in that case, we're likely better
> off sticking with POSIXish wording.
> 
> 
> > 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:
> 
> I don't see that in the glibc source. Are you sure about that?
> 
> If glibc qsort passes addresses outside the array to the comparison 
> function, then it's busted and should get fixed.

I don't see this in Glibc 2.39 either.  I've run some test cases with
assertions in compare fn and the assertion has never alarmed.  And the
developers were well aware of this standard requirement writing the
current qsort implementation:

https://sourceware.org/pipermail/libc-alpha/2024-January/154001.html

-- 
Xi Ruoyao <xry111@xry111.site>
School of Aerospace Science and Technology, Xidian University

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

[Zack Weinberg]

[-- Attachment #1: Type: text/plain, Size: 1808 bytes --]

On Tue, Feb 6, 2024, at 4:30 PM, Paul Eggert wrote:
> On 2/6/24 07:00, Zack Weinberg wrote:
>> 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.
> the paraphrase you sent was too generous, as it allowed the 
> array to be in completely random order if it had no matching element
> ... we're likely better off sticking with POSIXish wording.

I see what was wrong with the way I wrote it, but I really don't like
the "POSIXish wording".  To me it trips over the English-language ambiguity
of whether the "all" in "all X, Y, and Z" is meant to apply to Y and Z as
well as X. I revised my suggestion again (see attached patch).

>> 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:
>
> I don't see that in the glibc source. Are you sure about that?

I was wrong about this; I misread the code in qsort.c.  Specifically,
I missed that msort_with_tmp always merges *from* two subsets of the
main array, *into* the temporary array, and then copies the result back
to the main array.  Still, I think it is likely that some C libraries in
the past have failed to implement this requirement (intentionally or not).
In the attached patch I revised that suggestion again and I hope it satisfies
everyone's expectations now.

I might send another patch for this file later; I think it would be clearer to
consolidate most of the new language about how the comparison function is required
to behave into the "Comparison Functions" node.

zw

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Fix-bsearch-qsort-etc.-doc-to-match-POSIX-better.patch --]
[-- Type: text/x-patch; name="0001-Fix-bsearch-qsort-etc.-doc-to-match-POSIX-better.patch", Size: 7390 bytes --]

From 30259d4588c0b587624afb55daa86fe469fe2d8e Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sun, 4 Feb 2024 16:53:22 -0800
Subject: [PATCH] Fix bsearch, qsort etc. doc to match POSIX better
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* manual/search.texi (Array Search Function):
Correct the statement about lfind’s mean runtime:
it is proportional to a number (not that number),
and this is true only if random elements are searched for.
Relax the constraint on bsearch’s array argument:
POSIX says it need not be sorted, only partially sorted.
Say that the first arg passed to bsearch’s comparison function
is the key, and the second arg is an array element, as
POSIX requires.  For bsearch and qsort, say that the
comparison function should not alter the array, as POSIX
requires.  For qsort, say that the comparison function
must define a total order, as POSIX requires.  Add a warning
that the comparison function should not rely on object addresses.
Clarify how to ensure a stable sort, usage of temporary storage,
and what algorithmic properties qsort may have.
---
 manual/search.texi | 63 ++++++++++++++++++++++++++++++----------------
 1 file changed, 41 insertions(+), 22 deletions(-)

diff --git a/manual/search.texi b/manual/search.texi
index db577a5332..4f373d21ca 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -84,8 +84,9 @@ The return value is a pointer to the matching element in the array
 starting at @var{base} if it is found.  If no matching element is
 available @code{NULL} is returned.
 
-The mean runtime of this function is @code{*@var{nmemb}}/2.  This
-function should only be used if elements often get added to or deleted from
+The mean runtime of this function is proportional to @code{*@var{nmemb}/2},
+assuming random elements of the array are searched for.  This
+function should be used only if elements often get added to or deleted from
 the array in which case it might not be useful to sort the array before
 searching.
 @end deftypefun
@@ -122,24 +123,31 @@ bytes.  If one is sure the element is in the array it is better to use
 calling @code{lsearch}.
 @end deftypefun
 
-To search a sorted array for an element matching the key, use the
-@code{bsearch} function.  The prototype for this function is in
+To search a sorted or partially sorted array for an element matching the key,
+use the @code{bsearch} function.  The prototype for this function is in
 the header file @file{stdlib.h}.
 @pindex stdlib.h
 
 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
 @standards{ISO, stdlib.h}
 @safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}}
-The @code{bsearch} function searches the sorted array @var{array} for an object
+The @code{bsearch} function searches @var{array} for an object
 that is equivalent to @var{key}.  The array contains @var{count} elements,
 each of which is of size @var{size} bytes.
 
 The @var{compare} function is used to perform the comparison.  This
-function is called with two pointer arguments and should return an
+function is called with arguments that point to the key and to an
+array element, in that order, and should return an
 integer less than, equal to, or greater than zero corresponding to
-whether its first argument is considered less than, equal to, or greater
-than its second argument.  The elements of the @var{array} must already
-be sorted in ascending order according to this comparison function.
+whether the key is considered less than, equal to, or greater than
+the array element.  The function should not alter the array's contents.
+
+@var{array} does not need to be completely sorted according to
+@var{compare}, but it does need to be partially sorted with respect to
+@var{key}.  That is, the array must begin with all the elements that
+compare less than @var{key}; next must come all the elements that
+compare equal to @var{key}; and last, all the elements that compare
+greater than @var{key}.  (Any or all of these sub-sequences may be empty.)
 
 The return value is a pointer to the matching array element, or a null
 pointer if no match is found.  If the array contains more than one element
@@ -170,21 +178,33 @@ The @var{compare} function is used to perform the comparison on the
 array elements.  This function is called with two pointer arguments and
 should return an integer less than, equal to, or greater than zero
 corresponding to whether its first argument is considered less than,
-equal to, or greater than its second argument.
+equal to, or greater than its second argument.  The function must
+not alter the array's contents, and must define a total ordering
+of all the array elements, including any unusual values such as
+floating-point NaN (@pxref{Infinity and NaN}) that are present.
+
+@code{qsort} may attempt to allocate large amounts of temporary
+storage, using @code{malloc}.  However, memory allocation failure will
+not prevent it from sorting the array.
 
 @cindex stable sorting
 @strong{Warning:} If two objects compare as equal, their order after
 sorting is unpredictable.  That is to say, the sorting is not stable.
 This can make a difference when the comparison considers only part of
 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{Warning:} The result of @var{compare} should not depend in
+any way on the @emph{addresses} of the objects it is comparing.
+ISO C requires that both addresses passed to the comparison function
+always lie within the original array, and @theglibc{} honors this
+requirement, but other C libraries might not.  More importantly, the
+sorting process may temporarily move objects out of order, so the
+relative positions of objects within the array are meaningless while
+@code{qsort} is running.
 
 Here is a simple example of sorting an array of @code{long int} in numerical
 order, using the comparison function defined above (@pxref{Comparison
@@ -200,11 +220,10 @@ Functions}):
 @end smallexample
 
 The @code{qsort} function derives its name from the fact that it was
-originally implemented using the ``quick sort'' algorithm.
-
-The implementation of @code{qsort} attempts to allocate auxiliary storage
-and use the merge sort algorithm, without violating C standard requirement
-that arguments passed to the comparison function point within the array.
+originally implemented using the ``quick sort'' algorithm.  Modern C
+libraries (including @theglibc{}) may or may not use this algorithm.
+However, you can rely on @code{qsort} to be asymptotically optimal in
+the average case (i.e.@: @math{O(n \log n)}).
 @end deftypefun
 
 @node Search/Sort Example
-- 
2.43.0

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

[Alexander Monakov]

[-- Attachment #1: Type: text/plain, Size: 1468 bytes --]


On Wed, 7 Feb 2024, Zack Weinberg wrote:

> >> 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:
> >
> > I don't see that in the glibc source. Are you sure about that?
> 
> I was wrong about this; I misread the code in qsort.c.  Specifically,
> I missed that msort_with_tmp always merges *from* two subsets of the
> main array, *into* the temporary array, and then copies the result back
> to the main array.  Still, I think it is likely that some C libraries in
> the past have failed to implement this requirement (intentionally or not).
> In the attached patch I revised that suggestion again and I hope it satisfies
> everyone's expectations now.

I don't understand how that is likely: was it common to use merge sort for
implementation of qsort? For in-place sorting algorithms that mistake is
pretty much impossible to make.

In any case it seems unnecessary (and even impolite maybe, towards the authors
of those other C libraries) to make such implication in the Glibc manual.
It's much nicer to stick to the facts about Glibc itself.

(Glibc VCS briefly carried an implementation with such a mistake around 2002
when Roger Sayle's "Towers of Hanoi merge sort" was applied and then reverted)

Alexander

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

[Zack Weinberg]

On Wed, Feb 7, 2024, at 2:55 PM, Alexander Monakov wrote:
> On Wed, 7 Feb 2024, Zack Weinberg wrote:
>> Still, I think it is likely that some C libraries in
>> the past have failed to implement this requirement (intentionally or not).
>> In the attached patch I revised that suggestion again and I hope it satisfies
>> everyone's expectations now.
>
> I don't understand how that is likely: was it common to use merge sort for
> implementation of qsort? For in-place sorting algorithms that mistake is
> pretty much impossible to make.

It's a subtle requirement that conflicts with a textbook optimization to
*any* sorting algorithm that isn't 100% in-place, and a supermajority of
comparison functions in the wild won't care if it's violated.  It would be
*more* surprising to me if nobody could turn up a qsort implementation that
breaks this rule and always has.

> In any case it seems unnecessary (and even impolite maybe, towards the authors
> of those other C libraries) to make such implication in the Glibc manual.
> It's much nicer to stick to the facts about Glibc itself.

I see where you're coming from but it is even more important that the manual
be clear about what portable code can and cannot rely on.

> (Glibc VCS briefly carried an implementation with such a mistake around 2002
> when Roger Sayle's "Towers of Hanoi merge sort" was applied and then reverted)

Was it reverted because of this mistake?  Do you happen to remember what broke?

zw

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

[Alexander Monakov]

On Wed, 7 Feb 2024, Zack Weinberg wrote:

> On Wed, Feb 7, 2024, at 2:55 PM, Alexander Monakov wrote:
> > I don't understand how that is likely: was it common to use merge sort for
> > implementation of qsort? For in-place sorting algorithms that mistake is
> > pretty much impossible to make.
> 
> It's a subtle requirement that conflicts with a textbook optimization to
> *any* sorting algorithm that isn't 100% in-place,

Sorry, can you explain what optimization you mean here?

> and a supermajority of
> comparison functions in the wild won't care if it's violated.  It would be
> *more* surprising to me if nobody could turn up a qsort implementation that
> breaks this rule and always has.
> 
> > In any case it seems unnecessary (and even impolite maybe, towards the authors
> > of those other C libraries) to make such implication in the Glibc manual.
> > It's much nicer to stick to the facts about Glibc itself.
> 
> I see where you're coming from but it is even more important that the manual
> be clear about what portable code can and cannot rely on.

I think it can be done without making uncertain allegations about other C
libraries.

> > (Glibc VCS briefly carried an implementation with such a mistake around 2002
> > when Roger Sayle's "Towers of Hanoi merge sort" was applied and then reverted)
> 
> Was it reverted because of this mistake?  Do you happen to remember what broke?

I wasn't around back then :)  The commit that reverted it references bug 2880 in
the old GNATS bug tracker. I hope someone on the list knows where it is
archived. The commit message makes it clear it's due to the mistake we're
discussing:
https://sourceware.org/git/?p=glibc.git;a=commit;h=fa8d436c87f156d18208df3819fecee9fc1dbd9e

Alexander

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

[Paul Eggert]

On 2/7/24 12:45, Zack Weinberg wrote:
>> (Glibc VCS briefly carried an implementation with such a mistake around 2002
>> when Roger Sayle's "Towers of Hanoi merge sort" was applied and then reverted)
> Was it reverted because of this mistake?  Do you happen to remember what broke?

As I vaguely recall, no user programs broke. I spotted the failure to 
conform to the C standard while reviewing qsort.c, and sent in a fix. 
Ulrich Drepper then found that my fix was incomplete, and fixed msort.c 
in a similar way.

I'm relying mostly on memory here - I don't have easy access to my old 
mail archive at my then-employer.

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

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 653 bytes --]

On 2024-02-07 09:07, Zack Weinberg wrote:
> I might send another patch for this file later; I think it would be clearer to
> consolidate most of the new language about how the comparison function is required
> to behave into the "Comparison Functions" node.

Since we've made no further progress and it's surely worth improving the 
documentation based on what we had, I installed the attached doc patch. 
This incorporates your suggestions, with some rewording (I hope you like 
it), except I omitted the assertion that other C libraries don't conform 
to the C standard with respect to qsort array addresses, as that's 
something we're not sure about.

[-- Attachment #2: 0001-Fix-bsearch-qsort-doc-to-match-POSIX-better.patch --]
[-- Type: text/x-patch, Size: 7546 bytes --]

From 57581acd9559217e859fdac693145ce6399f4d70 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sat, 6 Apr 2024 08:44:01 -0700
Subject: [PATCH] Fix bsearch, qsort doc to match POSIX better
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* manual/search.texi (Array Search Function):
Correct the statement about lfind’s mean runtime:
it is proportional to a number (not that number),
and this is true only if random elements are searched for.
Relax the constraint on bsearch’s array argument:
POSIX says it need not be sorted, only partially sorted.
Say that the first arg passed to bsearch’s comparison function
is the key, and the second arg is an array element, as
POSIX requires.  For bsearch and qsort, say that the
comparison function should not alter the array, as POSIX
requires.  For qsort, say that the comparison function
must define a total order, as POSIX requires, that
it should not depend on element addresses, that
the original array index can be used for stable sorts,
and that if qsort still works if memory allocation fails.
Be more consistent in calling the array elements
“elements” rather than “objects”.

Co-authored-by: Zack Weinberg <zack@owlfolio.org>
---
 manual/search.texi | 60 +++++++++++++++++++++++++++-------------------
 1 file changed, 36 insertions(+), 24 deletions(-)

diff --git a/manual/search.texi b/manual/search.texi
index db577a5332..cb08c49409 100644
--- a/manual/search.texi
+++ b/manual/search.texi
@@ -84,8 +84,9 @@ The return value is a pointer to the matching element in the array
 starting at @var{base} if it is found.  If no matching element is
 available @code{NULL} is returned.
 
-The mean runtime of this function is @code{*@var{nmemb}}/2.  This
-function should only be used if elements often get added to or deleted from
+The mean runtime of this function is proportional to @code{*@var{nmemb}/2},
+assuming random elements of the array are searched for.  This
+function should be used only if elements often get added to or deleted from
 the array in which case it might not be useful to sort the array before
 searching.
 @end deftypefun
@@ -122,26 +123,34 @@ bytes.  If one is sure the element is in the array it is better to use
 calling @code{lsearch}.
 @end deftypefun
 
-To search a sorted array for an element matching the key, use the
-@code{bsearch} function.  The prototype for this function is in
+To search a sorted or partially sorted array for an element matching the key,
+use the @code{bsearch} function.  The prototype for this function is in
 the header file @file{stdlib.h}.
 @pindex stdlib.h
 
 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
 @standards{ISO, stdlib.h}
 @safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}}
-The @code{bsearch} function searches the sorted array @var{array} for an object
+The @code{bsearch} function searches @var{array} for an element
 that is equivalent to @var{key}.  The array contains @var{count} elements,
 each of which is of size @var{size} bytes.
 
 The @var{compare} function is used to perform the comparison.  This
-function is called with two pointer arguments and should return an
+function is called with arguments that point to the key and to an
+array element, in that order, and should return an
 integer less than, equal to, or greater than zero corresponding to
-whether its first argument is considered less than, equal to, or greater
-than its second argument.  The elements of the @var{array} must already
-be sorted in ascending order according to this comparison function.
-
-The return value is a pointer to the matching array element, or a null
+whether the key is considered less than, equal to, or greater than
+the array element.  The function should not alter the array's contents,
+and the same array element should always compare the same way with the key.
+
+Although the array need not be completely sorted, it should be
+partially sorted with respect to @var{key}.  That is, the array should
+begin with elements that compare less than @var{key}, followed by
+elements that compare equal to @var{key}, and ending with elements
+that compare greater than @var{key}.  Any or all of these element
+sequences can be empty.
+
+The return value is a pointer to a matching array element, or a null
 pointer if no match is found.  If the array contains more than one element
 that matches, the one that is returned is unspecified.
 
@@ -171,20 +180,22 @@ array elements.  This function is called with two pointer arguments and
 should return an integer less than, equal to, or greater than zero
 corresponding to whether its first argument is considered less than,
 equal to, or greater than its second argument.
+The function must not alter the array's contents, and must define a
+total ordering on the array elements, including any unusual values
+such as floating-point NaN (@pxref{Infinity and NaN}).
+Because the sorting process can move elements,
+the function's return value must not depend on the element addresses
+or the relative positions of elements within the array,
+as these are meaningless while @code{qsort} is running.
 
 @cindex stable sorting
-@strong{Warning:} If two objects compare as equal, their order after
+@strong{Warning:} If two elements compare equal, their order after
 sorting is unpredictable.  That is to say, the sorting is not stable.
 This can make a difference when the comparison considers only part of
-the elements.  Two elements with the same sort key may differ in other
-respects.
-
-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.
+the elements and two elements that compare equal may differ in other
+respects.  To ensure a stable sort in this situation, you can augment
+each element with an appropriate tie-breaking value, such as its
+original array index.
 
 Here is a simple example of sorting an array of @code{long int} in numerical
 order, using the comparison function defined above (@pxref{Comparison
@@ -202,18 +213,19 @@ Functions}):
 The @code{qsort} function derives its name from the fact that it was
 originally implemented using the ``quick sort'' algorithm.
 
-The implementation of @code{qsort} attempts to allocate auxiliary storage
+The implementation of @code{qsort} attempts to allocate auxiliary memory
 and use the merge sort algorithm, without violating C standard requirement
 that arguments passed to the comparison function point within the array.
+If the memory allocation fails, @code{qsort} resorts to a slower algorithm.
 @end deftypefun
 
 @node Search/Sort Example
 @section Searching and Sorting Example
 
 Here is an example showing the use of @code{qsort} and @code{bsearch}
-with an array of structures.  The objects in the array are sorted
+with an array of structures.  The elements of the array are sorted
 by comparing their @code{name} fields with the @code{strcmp} function.
-Then, we can look up individual objects based on their names.
+Then, we can look up individual elements based on their names.
 
 @comment This example is dedicated to the memory of Jim Henson.  RIP.
 @smallexample
-- 
2.40.1

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

[Florian Weimer]

* Paul Eggert:

>  The @var{compare} function is used to perform the comparison.  This
> +function is called with arguments that point to the key and to an
> +array element, in that order, and should return an
>  integer less than, equal to, or greater than zero corresponding to
> +whether the key is considered less than, equal to, or greater than
> +the array element.  The function should not alter the array's contents,
> +and the same array element should always compare the same way with the key.

I don't think the requirement described in the last line actually
exists.  Some applications likely reuse the same key object to search
for different values, and the requirement might prohibit that (but it is
ambiguous).

Rest looks okay to me.

Thanks,
Florian

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

[Zack Weinberg]

On Mon, Apr 8, 2024, at 4:28 AM, Florian Weimer wrote:
> * Paul Eggert:
>>  the same array element should always compare the same way with
>>  the key.
>
> I don't think the requirement described in the last line actually
> exists.  Some applications likely reuse the same key object to search
> for different values, and the requirement might prohibit that (but it
> is ambiguous).

I believe what Paul was trying to express here is that *during a single
call to bsearch*, repeated calls to the comparison function with the
same (key, element) pair should return the same result.

In between calls to bsearch, the application is allowed to modify both
the array and the key object, so there cannot be any expectation for the
comparison function to return the same result for the same pair of
*addresses* -- (&key, &element) -- on a second call to bsearch. I see
how the quoted sentence could read that way, though, and I'm not sure
how to fix it.

zw

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

[Paul Eggert]

On 2024-04-22 07:39, Zack Weinberg wrote:
> On Mon, Apr 8, 2024, at 4:28 AM, Florian Weimer wrote:
>> * Paul Eggert:
>>>   the same array element should always compare the same way with
>>>   the key.
>>
>> I don't think the requirement described in the last line actually
>> exists.  Some applications likely reuse the same key object to search
>> for different values, and the requirement might prohibit that (but it
>> is ambiguous).
> 
> I believe what Paul was trying to express here is that *during a single
> call to bsearch*, repeated calls to the comparison function with the
> same (key, element) pair should return the same result.

Yes. I was mimicking POSIX, which says:

> When the same objects ... are passed more than once to the comparison function, the results shall be consistent with one another. That is, the same object shall always compare the same way with the key.

Perhaps we should simply remove the word "always" from the glibc 
manual's phrasing? "Always" is not needed, and removing "always" should 
help avoid the unwanted implication that the requirement applies even to 
earlier or later bsearch invocations.

By the way, this phrase is stating a POSIX requirement. glibc's 
implementation (like pretty much all other implementions) is more 
generous, and doesn't impose the requirement. I didn't bother stating 
this in the manual, as I didn't think it worth the trouble.

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

[Florian Weimer]

* Paul Eggert:

> On 2024-04-22 07:39, Zack Weinberg wrote:
>> On Mon, Apr 8, 2024, at 4:28 AM, Florian Weimer wrote:
>>> * Paul Eggert:
>>>>   the same array element should always compare the same way with
>>>>   the key.
>>>
>>> I don't think the requirement described in the last line actually
>>> exists.  Some applications likely reuse the same key object to search
>>> for different values, and the requirement might prohibit that (but it
>>> is ambiguous).
>> I believe what Paul was trying to express here is that *during a
>> single
>> call to bsearch*, repeated calls to the comparison function with the
>> same (key, element) pair should return the same result.
>
> Yes. I was mimicking POSIX, which says:
>
>> When the same objects ... are passed more than once to the comparison function, the results shall be consistent with one another. That is, the same object shall always compare the same way with the key.
>
> Perhaps we should simply remove the word "always" from the glibc
> manual's phrasing? "Always" is not needed, and removing "always"
> should help avoid the unwanted implication that the requirement
> applies even to earlier or later bsearch invocations.

Makes sense, thanks.

Florian