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