libbacktrace/mmap.c

   1 /* mmap.c -- Memory allocation with mmap.
   2    Copyright (C) 2012-2021 Free Software Foundation, Inc.
   3    Written by Ian Lance Taylor, Google.
   4
   5 Redistribution and use in source and binary forms, with or without
   6 modification, are permitted provided that the following conditions are
   7 met:
   8
   9     (1) Redistributions of source code must retain the above copyright
  10     notice, this list of conditions and the following disclaimer.
  11
  12     (2) Redistributions in binary form must reproduce the above copyright
  13     notice, this list of conditions and the following disclaimer in
  14     the documentation and/or other materials provided with the
  15     distribution.
  16
  17     (3) The name of the author may not be used to
  18     endorse or promote products derived from this software without
  19     specific prior written permission.
  20
  21 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  22 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  23 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  24 DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
  25 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  26 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  27 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  29 STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  30 IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31 POSSIBILITY OF SUCH DAMAGE.  */
  32
  33 #include "config.h"
  34
  35 #include <errno.h>
  36 #include <string.h>
  37 #include <stdlib.h>
  38 #include <unistd.h>
  39 #include <sys/types.h>
  40 #include <sys/mman.h>
  41
  42 #include "backtrace.h"
  43 #include "internal.h"
  44
  45 #ifndef HAVE_DECL_GETPAGESIZE
  46 extern int getpagesize (void);
  47 #endif
  48
  49 /* Memory allocation on systems that provide anonymous mmap.  This
  50    permits the backtrace functions to be invoked from a signal
  51    handler, assuming that mmap is async-signal safe.  */
  52
  53 #ifndef MAP_ANONYMOUS
  54 #define MAP_ANONYMOUS MAP_ANON
  55 #endif
  56
  57 #ifndef MAP_FAILED
  58 #define MAP_FAILED ((void *)-1)
  59 #endif
  60
  61 /* A list of free memory blocks.  */
  62
  63 struct backtrace_freelist_struct
  64 {
  65   /* Next on list.  */
  66   struct backtrace_freelist_struct *next;
  67   /* Size of this block, including this structure.  */
  68   size_t size;
  69 };
  70
  71 /* Free memory allocated by backtrace_alloc.  */
  72
  73 static void
  74 backtrace_free_locked (struct backtrace_state *state, void *addr, size_t size)
  75 {
  76   /* Just leak small blocks.  We don't have to be perfect.  Don't put
  77      more than 16 entries on the free list, to avoid wasting time
  78      searching when allocating a block.  If we have more than 16
  79      entries, leak the smallest entry.  */
  80
  81   if (size >= sizeof (struct backtrace_freelist_struct))
  82     {
  83       size_t c;
  84       struct backtrace_freelist_struct **ppsmall;
  85       struct backtrace_freelist_struct **pp;
  86       struct backtrace_freelist_struct *p;
  87
  88       c = 0;
  89       ppsmall = NULL;
  90       for (pp = &state->freelist; *pp != NULL; pp = &(*pp)->next)
  91         {
  92           if (ppsmall == NULL || (*pp)->size < (*ppsmall)->size)
  93             ppsmall = pp;
  94           ++c;
  95         }
  96       if (c >= 16)
  97         {
  98           if (size <= (*ppsmall)->size)
  99             return;
 100           *ppsmall = (*ppsmall)->next;
 101         }
 102
 103       p = (struct backtrace_freelist_struct *) addr;
 104       p->next = state->freelist;
 105       p->size = size;
 106       state->freelist = p;
 107     }
 108 }
 109
 110 /* Allocate memory like malloc.  If ERROR_CALLBACK is NULL, don't
 111    report an error.  */
 112
 113 void *
 114 backtrace_alloc (struct backtrace_state *state,
 115                  size_t size, backtrace_error_callback error_callback,
 116                  void *data)
 117 {
 118   void *ret;
 119   int locked;
 120   struct backtrace_freelist_struct **pp;
 121   size_t pagesize;
 122   size_t asksize;
 123   void *page;
 124
 125   ret = NULL;
 126
 127   /* If we can acquire the lock, then see if there is space on the
 128      free list.  If we can't acquire the lock, drop straight into
 129      using mmap.  __sync_lock_test_and_set returns the old state of
 130      the lock, so we have acquired it if it returns 0.  */
 131
 132   if (!state->threaded)
 133     locked = 1;
 134   else
 135     locked = __sync_lock_test_and_set (&state->lock_alloc, 1) == 0;
 136
 137   if (locked)
 138     {
 139       for (pp = &state->freelist; *pp != NULL; pp = &(*pp)->next)
 140         {
 141           if ((*pp)->size >= size)
 142             {
 143               struct backtrace_freelist_struct *p;
 144
 145               p = *pp;
 146               *pp = p->next;
 147
 148               /* Round for alignment; we assume that no type we care about
 149                  is more than 8 bytes.  */
 150               size = (size + 7) & ~ (size_t) 7;
 151               if (size < p->size)
 152                 backtrace_free_locked (state, (char *) p + size,
 153                                        p->size - size);
 154
 155               ret = (void *) p;
 156
 157               break;
 158             }
 159         }
 160
 161       if (state->threaded)
 162         __sync_lock_release (&state->lock_alloc);
 163     }
 164
 165   if (ret == NULL)
 166     {
 167       /* Allocate a new page.  */
 168
 169       pagesize = getpagesize ();
 170       asksize = (size + pagesize - 1) & ~ (pagesize - 1);
 171       page = mmap (NULL, asksize, PROT_READ | PROT_WRITE,
 172                    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
 173       if (page == MAP_FAILED)
 174         {
 175           if (error_callback)
 176             error_callback (data, "mmap", errno);
 177         }
 178       else
 179         {
 180           size = (size + 7) & ~ (size_t) 7;
 181           if (size < asksize)
 182             backtrace_free (state, (char *) page + size, asksize - size,
 183                             error_callback, data);
 184
 185           ret = page;
 186         }
 187     }
 188
 189   return ret;
 190 }
 191
 192 /* Free memory allocated by backtrace_alloc.  */
 193
 194 void
 195 backtrace_free (struct backtrace_state *state, void *addr, size_t size,
 196                 backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
 197                 void *data ATTRIBUTE_UNUSED)
 198 {
 199   int locked;
 200
 201   /* If we are freeing a large aligned block, just release it back to
 202      the system.  This case arises when growing a vector for a large
 203      binary with lots of debug info.  Calling munmap here may cause us
 204      to call mmap again if there is also a large shared library; we
 205      just live with that.  */
 206   if (size >= 16 * 4096)
 207     {
 208       size_t pagesize;
 209
 210       pagesize = getpagesize ();
 211       if (((uintptr_t) addr & (pagesize - 1)) == 0
 212           && (size & (pagesize - 1)) == 0)
 213         {
 214           /* If munmap fails for some reason, just add the block to
 215              the freelist.  */
 216           if (munmap (addr, size) == 0)
 217             return;
 218         }
 219     }
 220
 221   /* If we can acquire the lock, add the new space to the free list.
 222      If we can't acquire the lock, just leak the memory.
 223      __sync_lock_test_and_set returns the old state of the lock, so we
 224      have acquired it if it returns 0.  */
 225
 226   if (!state->threaded)
 227     locked = 1;
 228   else
 229     locked = __sync_lock_test_and_set (&state->lock_alloc, 1) == 0;
 230
 231   if (locked)
 232     {
 233       backtrace_free_locked (state, addr, size);
 234
 235       if (state->threaded)
 236         __sync_lock_release (&state->lock_alloc);
 237     }
 238 }
 239
 240 /* Grow VEC by SIZE bytes.  */
 241
 242 void *
 243 backtrace_vector_grow (struct backtrace_state *state,size_t size,
 244                        backtrace_error_callback error_callback,
 245                        void *data, struct backtrace_vector *vec)
 246 {
 247   void *ret;
 248
 249   if (size > vec->alc)
 250     {
 251       size_t pagesize;
 252       size_t alc;
 253       void *base;
 254
 255       pagesize = getpagesize ();
 256       alc = vec->size + size;
 257       if (vec->size == 0)
 258         alc = 16 * size;
 259       else if (alc < pagesize)
 260         {
 261           alc *= 2;
 262           if (alc > pagesize)
 263             alc = pagesize;
 264         }
 265       else
 266         {
 267           alc *= 2;
 268           alc = (alc + pagesize - 1) & ~ (pagesize - 1);
 269         }
 270       base = backtrace_alloc (state, alc, error_callback, data);
 271       if (base == NULL)
 272         return NULL;
 273       if (vec->base != NULL)
 274         {
 275           memcpy (base, vec->base, vec->size);
 276           backtrace_free (state, vec->base, vec->size + vec->alc,
 277                           error_callback, data);
 278         }
 279       vec->base = base;
 280       vec->alc = alc - vec->size;
 281     }
 282
 283   ret = (char *) vec->base + vec->size;
 284   vec->size += size;
 285   vec->alc -= size;
 286   return ret;
 287 }
 288
 289 /* Finish the current allocation on VEC.  */
 290
 291 void *
 292 backtrace_vector_finish (
 293   struct backtrace_state *state ATTRIBUTE_UNUSED,
 294   struct backtrace_vector *vec,
 295   backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
 296   void *data ATTRIBUTE_UNUSED)
 297 {
 298   void *ret;
 299
 300   ret = vec->base;
 301   vec->base = (char *) vec->base + vec->size;
 302   vec->size = 0;
 303   return ret;
 304 }
 305
 306 /* Release any extra space allocated for VEC.  */
 307
 308 int
 309 backtrace_vector_release (struct backtrace_state *state,
 310                           struct backtrace_vector *vec,
 311                           backtrace_error_callback error_callback,
 312                           void *data)
 313 {
 314   size_t size;
 315   size_t alc;
 316   size_t aligned;
 317
 318   /* Make sure that the block that we free is aligned on an 8-byte
 319      boundary.  */
 320   size = vec->size;
 321   alc = vec->alc;
 322   aligned = (size + 7) & ~ (size_t) 7;
 323   alc -= aligned - size;
 324
 325   backtrace_free (state, (char *) vec->base + aligned, alc,
 326                   error_callback, data);
 327   vec->alc = 0;
 328   if (vec->size == 0)
 329     vec->base = NULL;
 330   return 1;
 331 }