[PATCH] qsort: Fix a typo causing unnecessary malloc/free

[PATCH] qsort: Fix a typo causing unnecessary malloc/free

[Xi Ruoyao]

In qsort_r we allocate a buffer sized QSORT_STACK_SIZE (1024) on stack
and we intend to use it if all elements can fit into it.  But there is a
typo:

    if (total_size < sizeof buf)
      buf = tmp;
    else
      /* allocate a buffer on heap and use it ... */

Here "buf" is a pointer, thus sizeof buf is just 4 or 8, instead of
1024.

This bug is detected debugging some strange heap corruption running the
Ruby-3.3.0 test suite (on an experimental Linux From Scratch build using
Binutils-2.41.90 and Glibc trunk, and also Fedora Rawhide [1]).  It
seems Ruby is doing some wild "optimization" by jumping into somewhere
in qsort_r instead of calling it normally, resulting in a double free of
buf if we allocate it on heap.  The issue can be reproduced
deterministically with:

    LD_PRELOAD=/usr/lib/libc_malloc_debug.so MALLOC_CHECK_=3 \
    LD_LIBRARY_PATH=. ./ruby test/runner.rb test/ruby/test_enum.rb

in Ruby-3.3.0 tree after building it.  This change would hide the issue
for Ruby, but Ruby is likely still buggy (if using this "optimization"
sorting larger arrays).

[1]:https://kojipkgs.fedoraproject.org//work/tasks/9729/111889729/build.log

Signed-off-by: Xi Ruoyao <xry111@xry111.site>
---
 stdlib/qsort.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index 7f5a00fb33..1c1505e7b2 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -353,7 +353,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
   if (size > INDIRECT_SORT_SIZE_THRES)
     total_size = 2 * total_elems * sizeof (void *) + size;
 
-  if (total_size < sizeof buf)
+  if (total_size < sizeof tmp)
     buf = tmp;
   else
     {
-- 
2.43.0

Re: [PATCH] qsort: Fix a typo causing unnecessary malloc/free

[H.J. Lu]

On Mon, Jan 22, 2024 at 11:32 AM Xi Ruoyao <xry111@xry111.site> wrote:
>
> In qsort_r we allocate a buffer sized QSORT_STACK_SIZE (1024) on stack
> and we intend to use it if all elements can fit into it.  But there is a
> typo:
>
>     if (total_size < sizeof buf)
>       buf = tmp;
>     else
>       /* allocate a buffer on heap and use it ... */
>
> Here "buf" is a pointer, thus sizeof buf is just 4 or 8, instead of
> 1024.

This sounds like a real bug.  A glibc bug report is needed to track it.

> This bug is detected debugging some strange heap corruption running the
> Ruby-3.3.0 test suite (on an experimental Linux From Scratch build using
> Binutils-2.41.90 and Glibc trunk, and also Fedora Rawhide [1]).  It
> seems Ruby is doing some wild "optimization" by jumping into somewhere
> in qsort_r instead of calling it normally, resulting in a double free of
> buf if we allocate it on heap.  The issue can be reproduced
> deterministically with:
>
>     LD_PRELOAD=/usr/lib/libc_malloc_debug.so MALLOC_CHECK_=3 \
>     LD_LIBRARY_PATH=. ./ruby test/runner.rb test/ruby/test_enum.rb
>
> in Ruby-3.3.0 tree after building it.  This change would hide the issue
> for Ruby, but Ruby is likely still buggy (if using this "optimization"
> sorting larger arrays).
>
> [1]:https://kojipkgs.fedoraproject.org//work/tasks/9729/111889729/build.log
>
> Signed-off-by: Xi Ruoyao <xry111@xry111.site>
> ---
>  stdlib/qsort.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
> index 7f5a00fb33..1c1505e7b2 100644
> --- a/stdlib/qsort.c
> +++ b/stdlib/qsort.c
> @@ -353,7 +353,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
>    if (size > INDIRECT_SORT_SIZE_THRES)
>      total_size = 2 * total_elems * sizeof (void *) + size;
>
> -  if (total_size < sizeof buf)
> +  if (total_size < sizeof tmp)
>      buf = tmp;
>    else
>      {
> --
> 2.43.0
>


-- 
H.J.

Re: [PATCH] qsort: Fix a typo causing unnecessary malloc/free

[Xi Ruoyao]

On Mon, 2024-01-22 at 11:46 -0800, H.J. Lu wrote:
> On Mon, Jan 22, 2024 at 11:32 AM Xi Ruoyao <xry111@xry111.site> wrote:
> > 
> > In qsort_r we allocate a buffer sized QSORT_STACK_SIZE (1024) on stack
> > and we intend to use it if all elements can fit into it.  But there is a
> > typo:
> > 
> >      if (total_size < sizeof buf)
> >        buf = tmp;
> >      else
> >        /* allocate a buffer on heap and use it ... */
> > 
> > Here "buf" is a pointer, thus sizeof buf is just 4 or 8, instead of
> > 1024.
> 
> This sounds like a real bug.  A glibc bug report is needed to track it.

https://sourceware.org/bugzilla/show_bug.cgi?id=31276

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

Re: [PATCH] qsort: Fix a typo causing unnecessary malloc/free

[Xi Ruoyao]

On Tue, 2024-01-23 at 03:54 +0800, Xi Ruoyao wrote:
> On Mon, 2024-01-22 at 11:46 -0800, H.J. Lu wrote:
> > On Mon, Jan 22, 2024 at 11:32 AM Xi Ruoyao <xry111@xry111.site> wrote:
> > > 
> > > In qsort_r we allocate a buffer sized QSORT_STACK_SIZE (1024) on stack
> > > and we intend to use it if all elements can fit into it.  But there is a
> > > typo:
> > > 
> > >      if (total_size < sizeof buf)

Hmm, and it seems this should be "<=" instead of "<".  I'm preparing a
V2 with the operator changed too, and the BZ number in commit message...

> > >        buf = tmp;
> > >      else
> > >        /* allocate a buffer on heap and use it ... */
> > > 
> > > Here "buf" is a pointer, thus sizeof buf is just 4 or 8, instead of
> > > 1024.
> > 
> > This sounds like a real bug.  A glibc bug report is needed to track it.
> 
> https://sourceware.org/bugzilla/show_bug.cgi?id=31276
> 

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

[PATCH v2] qsort: Fix a typo causing unnecessary malloc/free (BZ 31276)

[Xi Ruoyao]

In qsort_r we allocate a buffer sized QSORT_STACK_SIZE (1024) on stack
and we intend to use it if all elements can fit into it.  But there is a
typo:

    if (total_size < sizeof buf)
      buf = tmp;
    else
      /* allocate a buffer on heap and use it ... */

Here "buf" is a pointer, thus sizeof buf is just 4 or 8, instead of
1024.  There is also a minor issue that we should use "<=" instead of
"<".

This bug is detected debugging some strange heap corruption running the
Ruby-3.3.0 test suite (on an experimental Linux From Scratch build using
Binutils-2.41.90 and Glibc trunk, and also Fedora Rawhide [1]).  It
seems Ruby is doing some wild "optimization" by jumping into somewhere
in qsort_r instead of calling it normally, resulting in a double free of
buf if we allocate it on heap.  The issue can be reproduced
deterministically with:

    LD_PRELOAD=/usr/lib/libc_malloc_debug.so MALLOC_CHECK_=3 \
    LD_LIBRARY_PATH=. ./ruby test/runner.rb test/ruby/test_enum.rb

in Ruby-3.3.0 tree after building it.  This change would hide the issue
for Ruby, but Ruby is likely still buggy (if using this "optimization"
sorting larger arrays).

[1]:https://kojipkgs.fedoraproject.org/work/tasks/9729/111889729/build.log

Signed-off-by: Xi Ruoyao <xry111@xry111.site>
---

v1 -> v2:
- Use `<=` instead of `<`.
- Add BZ number.

 stdlib/qsort.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index 7f5a00fb33..be47aebbe0 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -353,7 +353,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
   if (size > INDIRECT_SORT_SIZE_THRES)
     total_size = 2 * total_elems * sizeof (void *) + size;
 
-  if (total_size < sizeof buf)
+  if (total_size <= sizeof tmp)
     buf = tmp;
   else
     {
-- 
2.43.0

Re: [PATCH v2] qsort: Fix a typo causing unnecessary malloc/free (BZ 31276)

[Adhemerval Zanella Netto]

On 22/01/24 17:29, Xi Ruoyao wrote:
> In qsort_r we allocate a buffer sized QSORT_STACK_SIZE (1024) on stack
> and we intend to use it if all elements can fit into it.  But there is a
> typo:
> 
>     if (total_size < sizeof buf)
>       buf = tmp;
>     else
>       /* allocate a buffer on heap and use it ... */
> 
> Here "buf" is a pointer, thus sizeof buf is just 4 or 8, instead of
> 1024.  There is also a minor issue that we should use "<=" instead of
> "<".
> 
> This bug is detected debugging some strange heap corruption running the
> Ruby-3.3.0 test suite (on an experimental Linux From Scratch build using
> Binutils-2.41.90 and Glibc trunk, and also Fedora Rawhide [1]).  It
> seems Ruby is doing some wild "optimization" by jumping into somewhere
> in qsort_r instead of calling it normally, resulting in a double free of
> buf if we allocate it on heap.  The issue can be reproduced
> deterministically with:
> 
>     LD_PRELOAD=/usr/lib/libc_malloc_debug.so MALLOC_CHECK_=3 \
>     LD_LIBRARY_PATH=. ./ruby test/runner.rb test/ruby/test_enum.rb
> 
> in Ruby-3.3.0 tree after building it.  This change would hide the issue
> for Ruby, but Ruby is likely still buggy (if using this "optimization"
> sorting larger arrays).
> 
> [1]:https://kojipkgs.fedoraproject.org/work/tasks/9729/111889729/build.log
> 
> Signed-off-by: Xi Ruoyao <xry111@xry111.site>

LGTM, thanks for catching it.

> ---
> 
> v1 -> v2:
> - Use `<=` instead of `<`.
> - Add BZ number.
> 
>  stdlib/qsort.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/stdlib/qsort.c b/stdlib/qsort.c
> index 7f5a00fb33..be47aebbe0 100644
> --- a/stdlib/qsort.c
> +++ b/stdlib/qsort.c
> @@ -353,7 +353,7 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
>    if (size > INDIRECT_SORT_SIZE_THRES)
>      total_size = 2 * total_elems * sizeof (void *) + size;
>  
> -  if (total_size < sizeof buf)
> +  if (total_size <= sizeof tmp)
>      buf = tmp;
>    else
>      {

Re: [PATCH v2] qsort: Fix a typo causing unnecessary malloc/free (BZ 31276)

[Andreas K. Huettel]

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

Am Montag, 22. Januar 2024, 21:31:18 CET schrieb Adhemerval Zanella Netto:
> 
> On 22/01/24 17:29, Xi Ruoyao wrote:
> > In qsort_r we allocate a buffer sized QSORT_STACK_SIZE (1024) on stack
> > and we intend to use it if all elements can fit into it.  But there is a
> > typo:
> > 
> >     if (total_size < sizeof buf)
> >       buf = tmp;
> >     else
> >       /* allocate a buffer on heap and use it ... */
> > 
> > Here "buf" is a pointer, thus sizeof buf is just 4 or 8, instead of
> > 1024.  There is also a minor issue that we should use "<=" instead of
> > "<".
> > 
> > This bug is detected debugging some strange heap corruption running the
> > Ruby-3.3.0 test suite (on an experimental Linux From Scratch build using
> > Binutils-2.41.90 and Glibc trunk, and also Fedora Rawhide [1]).  It
> > seems Ruby is doing some wild "optimization" by jumping into somewhere
> > in qsort_r instead of calling it normally, resulting in a double free of
> > buf if we allocate it on heap.  The issue can be reproduced
> > deterministically with:
> > 
> >     LD_PRELOAD=/usr/lib/libc_malloc_debug.so MALLOC_CHECK_=3 \
> >     LD_LIBRARY_PATH=. ./ruby test/runner.rb test/ruby/test_enum.rb
> > 
> > in Ruby-3.3.0 tree after building it.  This change would hide the issue
> > for Ruby, but Ruby is likely still buggy (if using this "optimization"
> > sorting larger arrays).
> > 
> > [1]:https://kojipkgs.fedoraproject.org/work/tasks/9729/111889729/build.log
> > 
> > Signed-off-by: Xi Ruoyao <xry111@xry111.site>
> 
> LGTM, thanks for catching it.
> 
Great, let's push it.


-- 
Andreas K. Hüttel
dilfridge@gentoo.org
Gentoo Linux developer
(council, toolchain, base-system, perl, libreoffice)

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 981 bytes --]

Re: [PATCH v2] qsort: Fix a typo causing unnecessary malloc/free (BZ 31276)

[Xi Ruoyao]

On Mon, 2024-01-22 at 21:50 +0100, Andreas K. Huettel wrote:
> Am Montag, 22. Januar 2024, 21:31:18 CET schrieb Adhemerval Zanella Netto:
> > 
> > On 22/01/24 17:29, Xi Ruoyao wrote:
> > > In qsort_r we allocate a buffer sized QSORT_STACK_SIZE (1024) on stack
> > > and we intend to use it if all elements can fit into it.  But there is a
> > > typo:
> > > 
> > >     if (total_size < sizeof buf)
> > >       buf = tmp;
> > >     else
> > >       /* allocate a buffer on heap and use it ... */
> > > 
> > > Here "buf" is a pointer, thus sizeof buf is just 4 or 8, instead of
> > > 1024.  There is also a minor issue that we should use "<=" instead of
> > > "<".
> > > 
> > > This bug is detected debugging some strange heap corruption running the
> > > Ruby-3.3.0 test suite (on an experimental Linux From Scratch build using
> > > Binutils-2.41.90 and Glibc trunk, and also Fedora Rawhide [1]).  It
> > > seems Ruby is doing some wild "optimization" by jumping into somewhere
> > > in qsort_r instead of calling it normally, resulting in a double free of
> > > buf if we allocate it on heap.  The issue can be reproduced
> > > deterministically with:
> > > 
> > >     LD_PRELOAD=/usr/lib/libc_malloc_debug.so MALLOC_CHECK_=3 \
> > >     LD_LIBRARY_PATH=. ./ruby test/runner.rb test/ruby/test_enum.rb
> > > 
> > > in Ruby-3.3.0 tree after building it.  This change would hide the issue
> > > for Ruby, but Ruby is likely still buggy (if using this "optimization"
> > > sorting larger arrays).
> > > 
> > > [1]:https://kojipkgs.fedoraproject.org/work/tasks/9729/111889729/build.log
> > > 
> > > Signed-off-by: Xi Ruoyao <xry111@xry111.site>
> > 
> > LGTM, thanks for catching it.
> > 
> Great, let's push it.

Note that I don't have a write access, please push for master and 2.39.

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

Re: [PATCH v2] qsort: Fix a typo causing unnecessary malloc/free (BZ 31276)

[H.J. Lu]

On Tue, Jan 23, 2024 at 12:20 AM Xi Ruoyao <xry111@xry111.site> wrote:
>
> On Mon, 2024-01-22 at 21:50 +0100, Andreas K. Huettel wrote:
> > Am Montag, 22. Januar 2024, 21:31:18 CET schrieb Adhemerval Zanella Netto:
> > >
> > > On 22/01/24 17:29, Xi Ruoyao wrote:
> > > > In qsort_r we allocate a buffer sized QSORT_STACK_SIZE (1024) on stack
> > > > and we intend to use it if all elements can fit into it.  But there is a
> > > > typo:
> > > >
> > > >     if (total_size < sizeof buf)
> > > >       buf = tmp;
> > > >     else
> > > >       /* allocate a buffer on heap and use it ... */
> > > >
> > > > Here "buf" is a pointer, thus sizeof buf is just 4 or 8, instead of
> > > > 1024.  There is also a minor issue that we should use "<=" instead of
> > > > "<".
> > > >
> > > > This bug is detected debugging some strange heap corruption running the
> > > > Ruby-3.3.0 test suite (on an experimental Linux From Scratch build using
> > > > Binutils-2.41.90 and Glibc trunk, and also Fedora Rawhide [1]).  It
> > > > seems Ruby is doing some wild "optimization" by jumping into somewhere
> > > > in qsort_r instead of calling it normally, resulting in a double free of
> > > > buf if we allocate it on heap.  The issue can be reproduced
> > > > deterministically with:
> > > >
> > > >     LD_PRELOAD=/usr/lib/libc_malloc_debug.so MALLOC_CHECK_=3 \
> > > >     LD_LIBRARY_PATH=. ./ruby test/runner.rb test/ruby/test_enum.rb
> > > >
> > > > in Ruby-3.3.0 tree after building it.  This change would hide the issue
> > > > for Ruby, but Ruby is likely still buggy (if using this "optimization"
> > > > sorting larger arrays).
> > > >
> > > > [1]:https://kojipkgs.fedoraproject.org/work/tasks/9729/111889729/build.log
> > > >
> > > > Signed-off-by: Xi Ruoyao <xry111@xry111.site>
> > >
> > > LGTM, thanks for catching it.
> > >
> > Great, let's push it.
>
> Note that I don't have a write access, please push for master and 2.39.
>

Pushed onto master.  2.39 hasn't been branched yet.

Thanks.

-- 
H.J.

Re: [PATCH] qsort: Fix a typo causing unnecessary malloc/free

[Florian Weimer]

* Xi Ruoyao:

> This bug is detected debugging some strange heap corruption running the
> Ruby-3.3.0 test suite (on an experimental Linux From Scratch build using
> Binutils-2.41.90 and Glibc trunk, and also Fedora Rawhide [1]).  It
> seems Ruby is doing some wild "optimization" by jumping into somewhere
> in qsort_r instead of calling it normally, resulting in a double free of
> buf if we allocate it on heap.  The issue can be reproduced
> deterministically with:
>
>     LD_PRELOAD=/usr/lib/libc_malloc_debug.so MALLOC_CHECK_=3 \
>     LD_LIBRARY_PATH=. ./ruby test/runner.rb test/ruby/test_enum.rb
>
> in Ruby-3.3.0 tree after building it.  This change would hide the issue
> for Ruby, but Ruby is likely still buggy (if using this "optimization"
> sorting larger arrays).
>
> [1]:https://kojipkgs.fedoraproject.org//work/tasks/9729/111889729/build.log

Sorry, missed that part.  I suspect it's because the Ruby garbage
collector updates pointers in the array during invocation of the
comparison function, and we later discard those updates when we copy the
sorted runs back into the application-supplied array.  Ruby probably
scans the stack conservatively, triggering object pinning, which is
probably the reason why we don't see the issue with the on-stack copy.

The issue is reproducible with the old (glibc 2.37) qsort_r if the Ruby
test case uses a suitable array size.

We've posted our findings to the Ruby bug:

  <https://bugs.ruby-lang.org/issues/20203>

Thanks,
Florian

Re: [PATCH] qsort: Fix a typo causing unnecessary malloc/free

[Xi Ruoyao]

On Wed, 2024-01-24 at 14:45 +0100, Florian Weimer wrote:
> * Xi Ruoyao:
> 
> > This bug is detected debugging some strange heap corruption running the
> > Ruby-3.3.0 test suite (on an experimental Linux From Scratch build using
> > Binutils-2.41.90 and Glibc trunk, and also Fedora Rawhide [1]).  It
> > seems Ruby is doing some wild "optimization" by jumping into somewhere
> > in qsort_r instead of calling it normally, resulting in a double free of
> > buf if we allocate it on heap.  The issue can be reproduced
> > deterministically with:
> > 
> >     LD_PRELOAD=/usr/lib/libc_malloc_debug.so MALLOC_CHECK_=3 \
> >     LD_LIBRARY_PATH=. ./ruby test/runner.rb test/ruby/test_enum.rb
> > 
> > in Ruby-3.3.0 tree after building it.  This change would hide the issue
> > for Ruby, but Ruby is likely still buggy (if using this "optimization"
> > sorting larger arrays).
> > 
> > [1]:https://kojipkgs.fedoraproject.org//work/tasks/9729/111889729/build.log
> 
> Sorry, missed that part.  I suspect it's because the Ruby garbage
> collector updates pointers in the array during invocation of the
> comparison function, and we later discard those updates when we copy the
> sorted runs back into the application-supplied array.  Ruby probably
> scans the stack conservatively, triggering object pinning, which is
> probably the reason why we don't see the issue with the on-stack copy.
> 
> The issue is reproducible with the old (glibc 2.37) qsort_r if the Ruby
> test case uses a suitable array size.
> 
> We've posted our findings to the Ruby bug:
> 
>   <https://bugs.ruby-lang.org/issues/20203>

Ooooops.  We've disabled the use of qsort_r for Ruby in BLFS for now:
https://wiki.linuxfromscratch.org/blfs/changeset/77b455955c17e22d6aa544c766b30850978960ab.
 I guess their own sort should work with their own GC anyway...

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