stdlib: Fix qsort memory leak if callback throws (BZ 32058)

Message ID 20240807203544.1720167-1-adhemerval.zanella@linaro.org
State Superseded
Headers
Series stdlib: Fix qsort memory leak if callback throws (BZ 32058) |

Checks

Context Check Description
redhat-pt-bot/TryBot-apply_patch success Patch applied to master at the time it was sent
redhat-pt-bot/TryBot-32bit success Build for i686
linaro-tcwg-bot/tcwg_glibc_build--master-aarch64 success Build passed
linaro-tcwg-bot/tcwg_glibc_check--master-aarch64 success Test passed
linaro-tcwg-bot/tcwg_glibc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_glibc_check--master-arm success Test passed

Commit Message

Adhemerval Zanella Netto Aug. 7, 2024, 8:35 p.m. UTC
  If the input buffer exceeds the stack allocated one, qsort will
malloc a temporary buffer to call mergesort.  Since C++ standard
does allow the callback comparison function to throw [1], the glibc
implementation can potentially leak memory.

The fixes uses a cleanup handler (__libc_cleanup_push /
__libc_cleanup_pop), where recent gcc put in cold code path.

Checked on x86_64-linux-gnu.

[1] https://timsong-cpp.github.io/cppwp/n4950/alg.c.library#4
---
 stdlib/Makefile      | 28 ++++++++++++++++-
 stdlib/qsort.c       | 36 ++++++++++++++++-----
 stdlib/tst-qsort4.c  |  4 +++
 stdlib/tst-qsort7.cc | 74 ++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 133 insertions(+), 9 deletions(-)
 create mode 100644 stdlib/tst-qsort7.cc
  

Comments

Andreas Schwab Aug. 8, 2024, 7:59 a.m. UTC | #1
This can be simplified:

diff --git c/stdlib/qsort.c w/stdlib/qsort.c
index be47aebbe0..7a8a826b83 100644
--- c/stdlib/qsort.c
+++ w/stdlib/qsort.c
@@ -25,6 +25,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <stdbool.h>
+#include <libc-lock.h>
 
 /* Swap SIZE bytes between addresses A and B.  These helpers are provided
    along the generic one as an optimization.  */
@@ -338,6 +339,16 @@ indirect_msort_with_tmp (const struct msort_param *p, void *b, size_t n,
       }
 }
 
+static void
+cancel_handler (void *ptr)
+{
+  void *mem = *(void **) ptr;
+  /* This check for NULL helps the compiler to that is does not generate
+     explicit calls for free (NULL).  */
+  if (mem != NULL)
+    free (mem);
+}
+
 void
 __qsort_r (void *const pbase, size_t total_elems, size_t size,
 	   __compar_d_fn_t cmp, void *arg)
@@ -349,6 +360,9 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
   _Alignas (uint64_t) char tmp[QSORT_STACK_SIZE];
   size_t total_size = total_elems * size;
   char *buf;
+  void *bufmem = NULL;
+
+  __libc_cleanup_push (cancel_handler, &bufmem);
 
   if (size > INDIRECT_SORT_SIZE_THRES)
     total_size = 2 * total_elems * sizeof (void *) + size;
@@ -358,14 +372,15 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
   else
     {
       int save = errno;
-      buf = malloc (total_size);
+      bufmem = malloc (total_size);
       __set_errno (save);
-      if (buf == NULL)
+      if (bufmem == NULL)
 	{
 	  /* Fallback to heapsort in case of memory failure.  */
 	  heapsort_r (pbase, total_elems - 1, size, cmp, arg);
 	  return;
 	}
+      buf = bufmem;
     }
 
   if (size > INDIRECT_SORT_SIZE_THRES)
@@ -393,8 +408,9 @@ __qsort_r (void *const pbase, size_t total_elems, size_t size,
       msort_with_tmp (&msort_param, pbase, total_elems);
     }
 
-  if (buf != tmp)
-    free (buf);
+  __libc_cleanup_pop (0);
+
+  free (bufmem);
 }
 libc_hidden_def (__qsort_r)
 weak_alias (__qsort_r, qsort_r)
  
Florian Weimer Aug. 8, 2024, 11:14 a.m. UTC | #2
* Adhemerval Zanella:

> If the input buffer exceeds the stack allocated one, qsort will
> malloc a temporary buffer to call mergesort.  Since C++ standard
> does allow the callback comparison function to throw [1], the glibc
> implementation can potentially leak memory.
>
> The fixes uses a cleanup handler (__libc_cleanup_push /
> __libc_cleanup_pop), where recent gcc put in cold code path.
>
> Checked on x86_64-linux-gnu.
>
> [1] https://timsong-cpp.github.io/cppwp/n4950/alg.c.library#4
> ---
>  stdlib/Makefile      | 28 ++++++++++++++++-
>  stdlib/qsort.c       | 36 ++++++++++++++++-----
>  stdlib/tst-qsort4.c  |  4 +++
>  stdlib/tst-qsort7.cc | 74 ++++++++++++++++++++++++++++++++++++++++++++
>  4 files changed, 133 insertions(+), 9 deletions(-)
>  create mode 100644 stdlib/tst-qsort7.cc

I think you should add two C cancellation tests, one with exceptions
enabled and one with exceptions disabled.  The one without exceptions
disabled will still fail because __libc_cleanup_push only handles
DWARF-based unwinding, not longjmp-based forced unwind.

Thanks,
Florian
  

Patch

diff --git a/stdlib/Makefile b/stdlib/Makefile
index 347491de53..96a0f39436 100644
--- a/stdlib/Makefile
+++ b/stdlib/Makefile
@@ -354,6 +354,12 @@  tests := \
   tst-xpg-basename \
   # tests
 
+tests-cxx = \
+  tst-qsort7 \
+  # tests-cxx
+
+tests += $(if $(CXX),$(tests-cxx))
+
 tests-internal := \
   tst-qsort4 \
   tst-strtod1i \
@@ -539,7 +545,17 @@  tests-special += $(objpfx)isomac.out
 
 ifeq ($(run-built-tests),yes)
 tests-special += $(objpfx)tst-fmtmsg.out
-endif
+ifeq ($(build-shared),yes)
+ifneq ($(PERL),no)
+generated += \
+  tst-qsort7.mtrace \
+  # generated
+tests-special += \
+  $(objpfx)tst-qsort7-mem.out \
+  # tests-special
+endif # $(build-shared) == yes
+endif # $(PERL) == yes
+endif # $(run-built-tests) == yes
 
 include ../Rules
 
@@ -627,3 +643,13 @@  $(objpfx)tst-setcontext3.out: tst-setcontext3.sh $(objpfx)tst-setcontext3
 $(objpfx)tst-qsort5: $(libm)
 $(objpfx)tst-concurrent-exit: $(shared-thread-library)
 $(objpfx)tst-concurrent-quick_exit: $(shared-thread-library)
+
+CFLAGS-tst-qsort7.o = -std=c++11
+LDLIBS-tst-qsort7 = -lstdc++
+
+tst-qsort7-ENV = MALLOC_TRACE=$(objpfx)tst-qsort7.mtrace \
+		 LD_PRELOAD=$(common-objpfx)/malloc/libc_malloc_debug.so
+
+$(objpfx)tst-qsort7-mem.out: $(objpfx)tst-qsort7.out
+	$(common-objpfx)malloc/mtrace $(objpfx)tst-qsort7.mtrace > $@; \
+	$(evaluate-test)
diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index be47aebbe0..c64540eb91 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -25,6 +25,7 @@ 
 #include <stdlib.h>
 #include <string.h>
 #include <stdbool.h>
+#include <libc-lock.h>
 
 /* Swap SIZE bytes between addresses A and B.  These helpers are provided
    along the generic one as an optimization.  */
@@ -338,6 +339,21 @@  indirect_msort_with_tmp (const struct msort_param *p, void *b, size_t n,
       }
 }
 
+struct cleanup_arg
+{
+  char *tmp;
+  char *buf;
+};
+
+static void
+cancel_handler (void *ptr)
+{
+  /* Restore the old signal handler.  */
+  struct cleanup_arg *clarg = (struct cleanup_arg *) ptr;
+  if (clarg->tmp != clarg->buf)
+    free (clarg->buf);
+}
+
 void
 __qsort_r (void *const pbase, size_t total_elems, size_t size,
 	   __compar_d_fn_t cmp, void *arg)
@@ -348,19 +364,21 @@  __qsort_r (void *const pbase, size_t total_elems, size_t size,
   /* Align to the maximum size used by the swap optimization.  */
   _Alignas (uint64_t) char tmp[QSORT_STACK_SIZE];
   size_t total_size = total_elems * size;
-  char *buf;
+
+  struct cleanup_arg clarg = { tmp, NULL };
+  __libc_cleanup_push (cancel_handler, &clarg);
 
   if (size > INDIRECT_SORT_SIZE_THRES)
     total_size = 2 * total_elems * sizeof (void *) + size;
 
   if (total_size <= sizeof tmp)
-    buf = tmp;
+    clarg.buf = tmp;
   else
     {
       int save = errno;
-      buf = malloc (total_size);
+      clarg.buf = malloc (total_size);
       __set_errno (save);
-      if (buf == NULL)
+      if (clarg.buf == NULL)
 	{
 	  /* Fallback to heapsort in case of memory failure.  */
 	  heapsort_r (pbase, total_elems - 1, size, cmp, arg);
@@ -376,7 +394,7 @@  __qsort_r (void *const pbase, size_t total_elems, size_t size,
 	  .cmp = cmp,
 	  .arg = arg,
 	  .var = SWAP_VOID_ARG,
-	  .t = buf,
+	  .t = clarg.buf,
 	};
       indirect_msort_with_tmp (&msort_param, pbase, total_elems, size);
     }
@@ -388,13 +406,15 @@  __qsort_r (void *const pbase, size_t total_elems, size_t size,
 	  .cmp = cmp,
 	  .arg = arg,
 	  .var = get_swap_type (pbase, size),
-	  .t = buf,
+	  .t = clarg.buf,
 	};
       msort_with_tmp (&msort_param, pbase, total_elems);
     }
 
-  if (buf != tmp)
-    free (buf);
+  __libc_cleanup_pop (0);
+
+  if (clarg.tmp != clarg.buf)
+    free (clarg.buf);
 }
 libc_hidden_def (__qsort_r)
 weak_alias (__qsort_r, qsort_r)
diff --git a/stdlib/tst-qsort4.c b/stdlib/tst-qsort4.c
index 247917b454..12f1357609 100644
--- a/stdlib/tst-qsort4.c
+++ b/stdlib/tst-qsort4.c
@@ -16,6 +16,10 @@ 
    License along with the GNU C Library; if not, see
    <http://www.gnu.org/licenses/>.  */
 
+#include <pthread.h>
+
+#define __libc_cleanup_push(a, b) pthread_cleanup_push (a, b)
+#define __libc_cleanup_pop(a)     pthread_cleanup_pop (a)
 #include "qsort.c"
 
 #include <stdio.h>
diff --git a/stdlib/tst-qsort7.cc b/stdlib/tst-qsort7.cc
new file mode 100644
index 0000000000..51a0b7d733
--- /dev/null
+++ b/stdlib/tst-qsort7.cc
@@ -0,0 +1,74 @@ 
+/* Test if qsort cleanup memory allocation if the comparison function
+   throws (BZ 32058)
+   Copyright (C) 2024 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <array>
+#include <cstdlib>
+#include <stdexcept>
+#include <mcheck.h>
+
+static int
+compar_func (const void *a1, const void *a2)
+{
+  throw std::logic_error (__func__);
+}
+
+static int
+do_test (void)
+{
+  mtrace ();
+
+  {
+    /* An array smaller than QSORT_STACK_SIZE, check if cleanup handler
+       handles the stack buffer correctly.  */
+    typedef std::array<int, 32> input_t;
+    input_t input = { 0 };
+
+    try
+      {
+	qsort (input.data(),
+	       input.size(),
+	       sizeof (input_t::value_type),
+	       compar_func);
+      }
+    catch (...)
+      {
+      }
+  }
+
+  {
+    /* An array larger than QSORT_STACK_SIZE to force memory allocation.  */
+    typedef std::array<int, 1024> input_t;
+    input_t input = { 0 };
+
+    try
+      {
+	qsort (input.data(),
+	       input.size(),
+	       sizeof (input_t::value_type),
+	       compar_func);
+      }
+    catch (...)
+      {
+      }
+  }
+ 
+  return 0;
+}
+
+#include <support/test-driver.c>