lib/malloca.c

   1 /* Safe automatic memory allocation.
   2    Copyright (C) 2003, 2006-2007, 2009-2017 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2003.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #define _GL_USE_STDLIB_ALLOC 1
  19 #include <config.h>
  20
  21 /* Specification.  */
  22 #include "malloca.h"
  23
  24 #include <stdint.h>
  25
  26 #include "verify.h"
  27
  28 /* Silence a warning from clang's MemorySanitizer.  */
  29 #if defined __has_feature
  30 # if __has_feature(memory_sanitizer)
  31 #  define NO_SANITIZE_MEMORY __attribute__((no_sanitize("memory")))
  32 # endif
  33 #endif
  34 #ifndef NO_SANITIZE_MEMORY
  35 # define NO_SANITIZE_MEMORY
  36 #endif
  37
  38 /* The speed critical point in this file is freea() applied to an alloca()
  39    result: it must be fast, to match the speed of alloca().  The speed of
  40    mmalloca() and freea() in the other case are not critical, because they
  41    are only invoked for big memory sizes.  */
  42
  43 #if HAVE_ALLOCA
  44
  45 /* Store the mmalloca() results in a hash table.  This is needed to reliably
  46    distinguish a mmalloca() result and an alloca() result.
  47
  48    Although it is possible that the same pointer is returned by alloca() and
  49    by mmalloca() at different times in the same application, it does not lead
  50    to a bug in freea(), because:
  51      - Before a pointer returned by alloca() can point into malloc()ed memory,
  52        the function must return, and once this has happened the programmer must
  53        not call freea() on it anyway.
  54      - Before a pointer returned by mmalloca() can point into the stack, it
  55        must be freed.  The only function that can free it is freea(), and
  56        when freea() frees it, it also removes it from the hash table.  */
  57
  58 #define MAGIC_NUMBER 0x1415fb4a
  59 #define MAGIC_SIZE sizeof (int)
  60 /* This is how the header info would look like without any alignment
  61    considerations.  */
  62 struct preliminary_header { void *next; int magic; };
  63 /* But the header's size must be a multiple of sa_alignment_max.  */
  64 #define HEADER_SIZE \
  65   (((sizeof (struct preliminary_header) + sa_alignment_max - 1) / sa_alignment_max) * sa_alignment_max)
  66 union header {
  67   void *next;
  68   struct {
  69     char room[HEADER_SIZE - MAGIC_SIZE];
  70     int word;
  71   } magic;
  72 };
  73 verify (HEADER_SIZE == sizeof (union header));
  74 /* We make the hash table quite big, so that during lookups the probability
  75    of empty hash buckets is quite high.  There is no need to make the hash
  76    table resizable, because when the hash table gets filled so much that the
  77    lookup becomes slow, it means that the application has memory leaks.  */
  78 #define HASH_TABLE_SIZE 257
  79 static void * mmalloca_results[HASH_TABLE_SIZE];
  80
  81 #endif
  82
  83 void *
  84 mmalloca (size_t n)
  85 {
  86 #if HAVE_ALLOCA
  87   /* Allocate one more word, that serves as an indicator for malloc()ed
  88      memory, so that freea() of an alloca() result is fast.  */
  89   size_t nplus = n + HEADER_SIZE;
  90
  91   if (nplus >= n)
  92     {
  93       void *p = malloc (nplus);
  94
  95       if (p != NULL)
  96         {
  97           size_t slot;
  98           union header *h = p;
  99
 100           p = h + 1;
 101
 102           /* Put a magic number into the indicator word.  */
 103           h->magic.word = MAGIC_NUMBER;
 104
 105           /* Enter p into the hash table.  */
 106           slot = (uintptr_t) p % HASH_TABLE_SIZE;
 107           h->next = mmalloca_results[slot];
 108           mmalloca_results[slot] = p;
 109
 110           return p;
 111         }
 112     }
 113   /* Out of memory.  */
 114   return NULL;
 115 #else
 116 # if !MALLOC_0_IS_NONNULL
 117   if (n == 0)
 118     n = 1;
 119 # endif
 120   return malloc (n);
 121 #endif
 122 }
 123
 124 #if HAVE_ALLOCA
 125 void NO_SANITIZE_MEMORY
 126 freea (void *p)
 127 {
 128   /* mmalloca() may have returned NULL.  */
 129   if (p != NULL)
 130     {
 131       /* Attempt to quickly distinguish the mmalloca() result - which has
 132          a magic indicator word - and the alloca() result - which has an
 133          uninitialized indicator word.  It is for this test that sa_increment
 134          additional bytes are allocated in the alloca() case.  */
 135       if (((int *) p)[-1] == MAGIC_NUMBER)
 136         {
 137           /* Looks like a mmalloca() result.  To see whether it really is one,
 138              perform a lookup in the hash table.  */
 139           size_t slot = (uintptr_t) p % HASH_TABLE_SIZE;
 140           void **chain = &mmalloca_results[slot];
 141           for (; *chain != NULL;)
 142             {
 143               union header *h = p;
 144               if (*chain == p)
 145                 {
 146                   /* Found it.  Remove it from the hash table and free it.  */
 147                   union header *p_begin = h - 1;
 148                   *chain = p_begin->next;
 149                   free (p_begin);
 150                   return;
 151                 }
 152               h = *chain;
 153               chain = &h[-1].next;
 154             }
 155         }
 156       /* At this point, we know it was not a mmalloca() result.  */
 157     }
 158 }
 159 #endif