Re: malloca, freea are not thread-safe

[Bruno Haible]

Hi Florian,

> Could we please fix this issue along those lines?  Thanks.

Done:


2018-02-02  Bruno Haible  <address@hidden>

        malloca, xmalloca: Make multithread-safe.
        Reported by Florian Weimer <address@hidden>.
        Implements an idea by Ondřej Bílka <address@hidden>.
        * lib/malloca.h (malloca): In the stack allocation case, return a
        pointer that is a multiple of 2 * sa_alignment_max.
        (sa_increment): Remove enum item.
        * lib/xmalloca.h (xmalloca): In the stack allocation case, return
        a pointer that is a multiple of 2 * sa_alignment_max.
        * lib/malloca.c (NO_SANITIZE_MEMORY): Remove macro.
        (MAGIC_NUMBER, MAGIC_SIZE, preliminary_header, HEADER_SIZE, header,
        HASH_TABLE_SIZE, mmalloca_results): Remove.
        (small_t): New type.
        (mmalloca, free): Rewritten.
        * lib/malloca.valgrind: Remove file.
        * modules/malloca (Files): Remove it.
        (Depends-on): Remove verify.

diff --git a/lib/malloca.h b/lib/malloca.h
index 8278c58..cbc8fe7 100644
--- a/lib/malloca.h
+++ b/lib/malloca.h
@@ -56,8 +56,10 @@ extern "C" {
    the function returns.  Upon failure, it returns NULL.  */
 #if HAVE_ALLOCA
 # define malloca(N) \
-  ((N) < 4032 - sa_increment                                        \
-   ? (void *) ((char *) alloca ((N) + sa_increment) + sa_increment) \
+  ((N) < 4032 - (2 * sa_alignment_max - 1)                          \
+   ? (void *) (((uintptr_t) alloca ((N) + 2 * sa_alignment_max - 1) \
+                + (2 * sa_alignment_max - 1))                       \
+               & ~(uintptr_t)(2 * sa_alignment_max - 1))            \
    : mmalloca (N))
 #else
 # define malloca(N) \
@@ -119,10 +121,7 @@ enum
                       | (sa_alignment_longlong - 1)
 #endif
                       | (sa_alignment_longdouble - 1)
-                     ) + 1,
-/* The increment that guarantees room for a magic word must be >= sizeof (int)
-   and a multiple of sa_alignment_max.  */
-  sa_increment = ((sizeof (int) + sa_alignment_max - 1) / sa_alignment_max) * 
sa_alignment_max
+                     ) + 1
 };
 
 #endif /* _MALLOCA_H */
diff --git a/lib/xmalloca.h b/lib/xmalloca.h
index 456f25b..14fc1b9 100644
--- a/lib/xmalloca.h
+++ b/lib/xmalloca.h
@@ -32,8 +32,10 @@ extern "C" {
    the function returns.  Upon failure, it exits with an error message.  */
 #if HAVE_ALLOCA
 # define xmalloca(N) \
-  ((N) < 4032 - sa_increment                                        \
-   ? (void *) ((char *) alloca ((N) + sa_increment) + sa_increment) \
+  ((N) < 4032 - (2 * sa_alignment_max - 1)                          \
+   ? (void *) (((uintptr_t) alloca ((N) + 2 * sa_alignment_max - 1) \
+                + (2 * sa_alignment_max - 1))                       \
+               & ~(uintptr_t)(2 * sa_alignment_max - 1))            \
    : xmmalloca (N))
 extern void * xmmalloca (size_t n);
 #else
diff --git a/lib/malloca.c b/lib/malloca.c
*** a/lib/malloca.c
--- b/lib/malloca.c
***************
*** 1,6 ****
  /* Safe automatic memory allocation.
     Copyright (C) 2003, 2006-2007, 2009-2018 Free Software Foundation, Inc.
!    Written by Bruno Haible <address@hidden>, 2003.
  
     This program is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by
--- 1,6 ----
  /* Safe automatic memory allocation.
     Copyright (C) 2003, 2006-2007, 2009-2018 Free Software Foundation, Inc.
!    Written by Bruno Haible <address@hidden>, 2003, 2018.
  
     This program is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by
***************
*** 21,112 ****
  /* Specification.  */
  #include "malloca.h"
  
- #include <stdint.h>
- 
- #include "verify.h"
- 
- /* Silence a warning from clang's MemorySanitizer.  */
- #if defined __has_feature
- # if __has_feature(memory_sanitizer)
- #  define NO_SANITIZE_MEMORY __attribute__((no_sanitize("memory")))
- # endif
- #endif
- #ifndef NO_SANITIZE_MEMORY
- # define NO_SANITIZE_MEMORY
- #endif
- 
  /* The speed critical point in this file is freea() applied to an alloca()
     result: it must be fast, to match the speed of alloca().  The speed of
     mmalloca() and freea() in the other case are not critical, because they
!    are only invoked for big memory sizes.  */
! 
! #if HAVE_ALLOCA
! 
! /* Store the mmalloca() results in a hash table.  This is needed to reliably
!    distinguish a mmalloca() result and an alloca() result.
! 
!    Although it is possible that the same pointer is returned by alloca() and
!    by mmalloca() at different times in the same application, it does not lead
!    to a bug in freea(), because:
!      - Before a pointer returned by alloca() can point into malloc()ed memory,
!        the function must return, and once this has happened the programmer 
must
!        not call freea() on it anyway.
!      - Before a pointer returned by mmalloca() can point into the stack, it
!        must be freed.  The only function that can free it is freea(), and
!        when freea() frees it, it also removes it from the hash table.  */
  
! #define MAGIC_NUMBER 0x1415fb4a
! #define MAGIC_SIZE sizeof (int)
! /* This is how the header info would look like without any alignment
!    considerations.  */
! struct preliminary_header { void *next; int magic; };
! /* But the header's size must be a multiple of sa_alignment_max.  */
! #define HEADER_SIZE \
!   (((sizeof (struct preliminary_header) + sa_alignment_max - 1) / 
sa_alignment_max) * sa_alignment_max)
! union header {
!   void *next;
!   struct {
!     char room[HEADER_SIZE - MAGIC_SIZE];
!     int word;
!   } magic;
! };
! verify (HEADER_SIZE == sizeof (union header));
! /* We make the hash table quite big, so that during lookups the probability
!    of empty hash buckets is quite high.  There is no need to make the hash
!    table resizable, because when the hash table gets filled so much that the
!    lookup becomes slow, it means that the application has memory leaks.  */
! #define HASH_TABLE_SIZE 257
! static void * mmalloca_results[HASH_TABLE_SIZE];
! 
! #endif
  
  void *
  mmalloca (size_t n)
  {
  #if HAVE_ALLOCA
!   /* Allocate one more word, that serves as an indicator for malloc()ed
!      memory, so that freea() of an alloca() result is fast.  */
!   size_t nplus = n + HEADER_SIZE;
  
    if (nplus >= n)
      {
!       void *p = malloc (nplus);
  
!       if (p != NULL)
          {
!           size_t slot;
!           union header *h = p;
! 
!           p = h + 1;
! 
!           /* Put a magic number into the indicator word.  */
!           h->magic.word = MAGIC_NUMBER;
! 
!           /* Enter p into the hash table.  */
!           slot = (uintptr_t) p % HASH_TABLE_SIZE;
!           h->next = mmalloca_results[slot];
!           mmalloca_results[slot] = p;
! 
            return p;
          }
      }
--- 21,65 ----
  /* Specification.  */
  #include "malloca.h"
  
  /* The speed critical point in this file is freea() applied to an alloca()
     result: it must be fast, to match the speed of alloca().  The speed of
     mmalloca() and freea() in the other case are not critical, because they
!    are only invoked for big memory sizes.
!    Here we use a bit in the address as an indicator, an idea by Ondřej Bílka.
!    malloca() can return three types of pointers:
!      - Pointers ≡ 0 mod 2*sa_alignment_max come from stack allocation.
!      - Pointers ≡ sa_alignment_max mod 2*sa_alignment_max come from heap
!        allocation.
!      - NULL comes from a failed heap allocation.  */
  
! /* Type for holding very small pointer differences.  */
! typedef unsigned char small_t;
  
  void *
  mmalloca (size_t n)
  {
  #if HAVE_ALLOCA
!   /* Allocate one more word, used to determine the address to pass to freea(),
!      and room for the alignment ≡ sa_alignment_max mod 2*sa_alignment_max.  */
!   size_t nplus = n + sizeof (small_t) + 2 * sa_alignment_max - 1;
  
    if (nplus >= n)
      {
!       char *mem = (char *) malloc (nplus);
  
!       if (mem != NULL)
          {
!           char *p =
!             (char *)((((uintptr_t)mem + sizeof (small_t) + sa_alignment_max - 
1)
!                       & ~(uintptr_t)(2 * sa_alignment_max - 1))
!                      + sa_alignment_max);
!           /* Here p >= mem + sizeof (small_t),
!              and p <= mem + sizeof (small_t) + 2 * sa_alignment_max - 1
!              hence p + n <= mem + nplus.
!              So, the memory range [p, p+n) lies in the allocated memory range
!              [mem, mem + nplus).  */
!           ((small_t *) p)[-1] = p - mem;
!           /* p ≡ sa_alignment_max mod 2*sa_alignment_max.  */
            return p;
          }
      }
***************
*** 122,159 ****
  }
  
  #if HAVE_ALLOCA
! void NO_SANITIZE_MEMORY
  freea (void *p)
  {
!   /* mmalloca() may have returned NULL.  */
!   if (p != NULL)
      {
!       /* Attempt to quickly distinguish the mmalloca() result - which has
!          a magic indicator word - and the alloca() result - which has an
!          uninitialized indicator word.  It is for this test that sa_increment
!          additional bytes are allocated in the alloca() case.  */
!       if (((int *) p)[-1] == MAGIC_NUMBER)
!         {
!           /* Looks like a mmalloca() result.  To see whether it really is one,
!              perform a lookup in the hash table.  */
!           size_t slot = (uintptr_t) p % HASH_TABLE_SIZE;
!           void **chain = &mmalloca_results[slot];
!           for (; *chain != NULL;)
!             {
!               union header *h = p;
!               if (*chain == p)
!                 {
!                   /* Found it.  Remove it from the hash table and free it.  */
!                   union header *p_begin = h - 1;
!                   *chain = p_begin->next;
!                   free (p_begin);
!                   return;
!                 }
!               h = *chain;
!               chain = &h[-1].next;
!             }
!         }
!       /* At this point, we know it was not a mmalloca() result.  */
      }
  }
  #endif
--- 75,95 ----
  }
  
  #if HAVE_ALLOCA
! void
  freea (void *p)
  {
!   /* Determine whether p was a non-NULL pointer returned by mmalloca().  */
!   if ((uintptr_t) p & sa_alignment_max)
      {
!       void *mem = (char *) p - ((small_t *) p)[-1];
!       free (mem);
      }
  }
  #endif
+ 
+ /*
+  * Hey Emacs!
+  * Local Variables:
+  * coding: utf-8
+  * End:
+  */
diff --git a/lib/malloca.valgrind b/lib/malloca.valgrind
deleted file mode 100644
index 52f0a50..0000000
--- a/lib/malloca.valgrind
+++ /dev/null
@@ -1,7 +0,0 @@
-# Suppress a valgrind message about use of uninitialized memory in freea().
-# This use is OK because it provides only a speedup.
-{
-    freea
-    Memcheck:Cond
-    fun:freea
-}
diff --git a/modules/malloca b/modules/malloca
index 9d4b40b..8f5ab64 100644
--- a/modules/malloca
+++ b/modules/malloca
@@ -4,7 +4,6 @@ Safe automatic memory allocation.
 Files:
 lib/malloca.h
 lib/malloca.c
-lib/malloca.valgrind
 m4/malloca.m4
 m4/eealloc.m4
 m4/longlong.m4
@@ -13,7 +12,6 @@ Depends-on:
 alloca-opt
 stdint
 xalloc-oversized
-verify
 
 configure.ac:
 gl_MALLOCA