libbacktrace/mmap.c

   1 /* mmap.c -- Memory allocation with mmap.
   2    Copyright (C) 2012-2015 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 /* Memory allocation on systems that provide anonymous mmap.  This
  46    permits the backtrace functions to be invoked from a signal
  47    handler, assuming that mmap is async-signal safe.  */
  48
  49 #ifndef MAP_ANONYMOUS
  50 #define MAP_ANONYMOUS MAP_ANON
  51 #endif
  52
  53 /* A list of free memory blocks.  */
  54
  55 struct backtrace_freelist_struct
  56 {
  57   /* Next on list.  */
  58   struct backtrace_freelist_struct *next;
  59   /* Size of this block, including this structure.  */
  60   size_t size;
  61 };
  62
  63 /* Free memory allocated by backtrace_alloc.  */
  64
  65 static void
  66 backtrace_free_locked (struct backtrace_state *state, void *addr, size_t size)
  67 {
  68   /* Just leak small blocks.  We don't have to be perfect.  */
  69   if (size >= sizeof (struct backtrace_freelist_struct))
  70     {
  71       struct backtrace_freelist_struct *p;
  72
  73       p = (struct backtrace_freelist_struct *) addr;
  74       p->next = state->freelist;
  75       p->size = size;
  76       state->freelist = p;
  77     }
  78 }
  79
  80 /* Allocate memory like malloc.  */
  81
  82 void *
  83 backtrace_alloc (struct backtrace_state *state,
  84                  size_t size, backtrace_error_callback error_callback,
  85                  void *data)
  86 {
  87   void *ret;
  88   int locked;
  89   struct backtrace_freelist_struct **pp;
  90   size_t pagesize;
  91   size_t asksize;
  92   void *page;
  93
  94   ret = NULL;
  95
  96   /* If we can acquire the lock, then see if there is space on the
  97      free list.  If we can't acquire the lock, drop straight into
  98      using mmap.  __sync_lock_test_and_set returns the old state of
  99      the lock, so we have acquired it if it returns 0.  */
 100
 101   if (!state->threaded)
 102     locked = 1;
 103   else
 104     locked = __sync_lock_test_and_set (&state->lock_alloc, 1) == 0;
 105
 106   if (locked)
 107     {
 108       for (pp = &state->freelist; *pp != NULL; pp = &(*pp)->next)
 109         {
 110           if ((*pp)->size >= size)
 111             {
 112               struct backtrace_freelist_struct *p;
 113
 114               p = *pp;
 115               *pp = p->next;
 116
 117               /* Round for alignment; we assume that no type we care about
 118                  is more than 8 bytes.  */
 119               size = (size + 7) & ~ (size_t) 7;
 120               if (size < p->size)
 121                 backtrace_free_locked (state, (char *) p + size,
 122                                        p->size - size);
 123
 124               ret = (void *) p;
 125
 126               break;
 127             }
 128         }
 129
 130       if (state->threaded)
 131         __sync_lock_release (&state->lock_alloc);
 132     }
 133
 134   if (ret == NULL)
 135     {
 136       /* Allocate a new page.  */
 137
 138       pagesize = getpagesize ();
 139       asksize = (size + pagesize - 1) & ~ (pagesize - 1);
 140       page = mmap (NULL, asksize, PROT_READ | PROT_WRITE,
 141                    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
 142       if (page == MAP_FAILED)
 143         error_callback (data, "mmap", errno);
 144       else
 145         {
 146           size = (size + 7) & ~ (size_t) 7;
 147           if (size < asksize)
 148             backtrace_free (state, (char *) page + size, asksize - size,
 149                             error_callback, data);
 150
 151           ret = page;
 152         }
 153     }
 154
 155   return ret;
 156 }
 157
 158 /* Free memory allocated by backtrace_alloc.  */
 159
 160 void
 161 backtrace_free (struct backtrace_state *state, void *addr, size_t size,
 162                 backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
 163                 void *data ATTRIBUTE_UNUSED)
 164 {
 165   int locked;
 166
 167   /* If we are freeing a large aligned block, just release it back to
 168      the system.  This case arises when growing a vector for a large
 169      binary with lots of debug info.  Calling munmap here may cause us
 170      to call mmap again if there is also a large shared library; we
 171      just live with that.  */
 172   if (size >= 16 * 4096)
 173     {
 174       size_t pagesize;
 175
 176       pagesize = getpagesize ();
 177       if (((uintptr_t) addr & (pagesize - 1)) == 0
 178           && (size & (pagesize - 1)) == 0)
 179         {
 180           /* If munmap fails for some reason, just add the block to
 181              the freelist.  */
 182           if (munmap (addr, size) == 0)
 183             return;
 184         }
 185     }
 186
 187   /* If we can acquire the lock, add the new space to the free list.
 188      If we can't acquire the lock, just leak the memory.
 189      __sync_lock_test_and_set returns the old state of the lock, so we
 190      have acquired it if it returns 0.  */
 191
 192   if (!state->threaded)
 193     locked = 1;
 194   else
 195     locked = __sync_lock_test_and_set (&state->lock_alloc, 1) == 0;
 196
 197   if (locked)
 198     {
 199       backtrace_free_locked (state, addr, size);
 200
 201       if (state->threaded)
 202         __sync_lock_release (&state->lock_alloc);
 203     }
 204 }
 205
 206 /* Grow VEC by SIZE bytes.  */
 207
 208 void *
 209 backtrace_vector_grow (struct backtrace_state *state,size_t size,
 210                        backtrace_error_callback error_callback,
 211                        void *data, struct backtrace_vector *vec)
 212 {
 213   void *ret;
 214
 215   if (size > vec->alc)
 216     {
 217       size_t pagesize;
 218       size_t alc;
 219       void *base;
 220
 221       pagesize = getpagesize ();
 222       alc = vec->size + size;
 223       if (vec->size == 0)
 224         alc = 16 * size;
 225       else if (alc < pagesize)
 226         {
 227           alc *= 2;
 228           if (alc > pagesize)
 229             alc = pagesize;
 230         }
 231       else
 232         {
 233           alc *= 2;
 234           alc = (alc + pagesize - 1) & ~ (pagesize - 1);
 235         }
 236       base = backtrace_alloc (state, alc, error_callback, data);
 237       if (base == NULL)
 238         return NULL;
 239       if (vec->base != NULL)
 240         {
 241           memcpy (base, vec->base, vec->size);
 242           backtrace_free (state, vec->base, vec->size + vec->alc,
 243                           error_callback, data);
 244         }
 245       vec->base = base;
 246       vec->alc = alc - vec->size;
 247     }
 248
 249   ret = (char *) vec->base + vec->size;
 250   vec->size += size;
 251   vec->alc -= size;
 252   return ret;
 253 }
 254
 255 /* Finish the current allocation on VEC.  */
 256
 257 void *
 258 backtrace_vector_finish (
 259   struct backtrace_state *state ATTRIBUTE_UNUSED,
 260   struct backtrace_vector *vec,
 261   backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
 262   void *data ATTRIBUTE_UNUSED)
 263 {
 264   void *ret;
 265
 266   ret = vec->base;
 267   vec->base = (char *) vec->base + vec->size;
 268   vec->size = 0;
 269   return ret;
 270 }
 271
 272 /* Release any extra space allocated for VEC.  */
 273
 274 int
 275 backtrace_vector_release (struct backtrace_state *state,
 276                           struct backtrace_vector *vec,
 277                           backtrace_error_callback error_callback,
 278                           void *data)
 279 {
 280   size_t size;
 281   size_t alc;
 282   size_t aligned;
 283
 284   /* Make sure that the block that we free is aligned on an 8-byte
 285      boundary.  */
 286   size = vec->size;
 287   alc = vec->alc;
 288   aligned = (size + 7) & ~ (size_t) 7;
 289   alc -= aligned - size;
 290
 291   backtrace_free (state, (char *) vec->base + aligned, alc,
 292                   error_callback, data);
 293   vec->alc = 0;
 294   return 1;
 295 }