libbacktrace/mmap.c

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