src/atomic_ops_malloc.c

   1 /*
   2  * Copyright (c) 2005 Hewlett-Packard Development Company, L.P.
   3  * Original Author: Hans Boehm
   4  *
   5  * This file may be redistributed and/or modified under the
   6  * terms of the GNU General Public License as published by the Free Software
   7  * Foundation; either version 2, or (at your option) any later version.
   8  *
   9  * It is distributed in the hope that it will be useful, but WITHOUT ANY
  10  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  11  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License in the
  12  * file doc/COPYING for more details.
  13  */
  14
  15 #if defined(HAVE_CONFIG_H)
  16 # include "config.h"
  17 #endif
  18
  19 #define AO_REQUIRE_CAS
  20 #include "atomic_ops_stack.h"
  21 #include <string.h>     /* for ffs, which is assumed reentrant. */
  22 #include <stdlib.h>
  23 #ifdef AO_TRACE_MALLOC
  24 # include <stdio.h>
  25 # include <pthread.h>
  26 #endif
  27
  28 /*
  29  * We round up each allocation request to the next power of two
  30  * minus one word.
  31  * We keep one stack of free objects for each size.  Each object
  32  * has an initial word (offset -sizeof(AO_t) from the visible pointer)
  33  * which contains either
  34  *      The binary log of the object size in bytes (small objects)
  35  *      The object size (a multiple of CHUNK_SIZE) for large objects.
  36  * The second case only arises if mmap-based allocation is supported.
  37  * We align the user-visible part of each object on a GRANULARITY
  38  * byte boundary.  That means that the actual (hidden) start of
  39  * the object starts a word before this boundary.
  40  */
  41
  42 #ifndef LOG_MAX_SIZE
  43 # define LOG_MAX_SIZE 16
  44         /* We assume that 2**LOG_MAX_SIZE is a multiple of page size. */
  45 #endif
  46
  47 #ifndef ALIGNMENT
  48 # define ALIGNMENT 16
  49         /* Assumed to be at least sizeof(AO_t).         */
  50 #endif
  51
  52 #define CHUNK_SIZE (1 << LOG_MAX_SIZE)
  53
  54 #ifndef AO_INITIAL_HEAP_SIZE
  55 #  define AO_INITIAL_HEAP_SIZE (2*(LOG_MAX_SIZE+1)*CHUNK_SIZE)
  56 #endif
  57
  58 char AO_initial_heap[AO_INITIAL_HEAP_SIZE];
  59
  60 static volatile AO_t initial_heap_ptr = (AO_t)AO_initial_heap;
  61 static volatile char *initial_heap_lim = AO_initial_heap + AO_INITIAL_HEAP_SIZE;
  62
  63 #if defined(HAVE_MMAP)
  64
  65 #include <sys/types.h>
  66 #include <sys/stat.h>
  67 #include <fcntl.h>
  68 #include <sys/mman.h>
  69
  70 static volatile AO_t mmap_enabled = 0;
  71
  72 void
  73 AO_malloc_enable_mmap(void)
  74 {
  75   AO_store(&mmap_enabled, 1);
  76 }
  77
  78 static char *get_mmaped(size_t sz)
  79 {
  80   char * result;
  81
  82   assert(!(sz & (CHUNK_SIZE - 1)));
  83   if (!mmap_enabled) return 0;
  84 # if defined(MAP_ANONYMOUS)
  85     result = mmap(0, sz, PROT_READ | PROT_WRITE,
  86                   MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
  87 # elif defined(MAP_ANON)
  88     result = mmap(0, sz, PROT_READ | PROT_WRITE,
  89                   MAP_PRIVATE | MAP_ANON, -1, 0);
  90 # else
  91     {
  92       int zero_fd = open("/dev/zero", O_RDONLY);
  93       result = mmap(0, sz, PROT_READ | PROT_WRITE,
  94                     MAP_PRIVATE, zero_fd, 0);
  95       close(zero_fd);
  96     }
  97 # endif
  98   if (result == MAP_FAILED) result = 0;
  99   return result;
 100 }
 101
 102 /* Allocate an object of size (incl. header) of size > CHUNK_SIZE.      */
 103 /* sz includes space for an AO_t-sized header.                          */
 104 static char *
 105 AO_malloc_large(size_t sz)
 106 {
 107  char * result;
 108  /* The header will force us to waste ALIGNMENT bytes, incl. header.    */
 109    sz += ALIGNMENT;
 110  /* Round to multiple of CHUNK_SIZE.    */
 111    sz = (sz + CHUNK_SIZE - 1) & ~(CHUNK_SIZE - 1);
 112  result = get_mmaped(sz);
 113  if (result == 0) return 0;
 114  result += ALIGNMENT;
 115  ((AO_t *)result)[-1] = (AO_t)sz;
 116  return result;
 117 }
 118
 119 static void
 120 AO_free_large(char * p)
 121 {
 122   AO_t sz = ((AO_t *)p)[-1];
 123   if (munmap(p - ALIGNMENT, (size_t)sz) != 0)
 124     abort();  /* Programmer error.  Not really async-signal-safe, but ... */
 125 }
 126
 127
 128 #else /*  No MMAP */
 129
 130 void
 131 AO_malloc_enable_mmap(void)
 132 {
 133 }
 134
 135 static char *get_mmaped(size_t sz)
 136 {
 137   return 0;
 138 }
 139
 140 static char *
 141 AO_malloc_large(size_t sz)
 142 {
 143   return 0;
 144 }
 145
 146 static void
 147 AO_free_large(char * p)
 148 {
 149   abort();  /* Programmer error.  Not really async-signal-safe, but ... */
 150 }
 151
 152 #endif /* No MMAP */
 153
 154 static char *
 155 get_chunk(void)
 156 {
 157   char *initial_ptr;
 158   char *my_chunk_ptr;
 159   char * my_lim;
 160
 161 retry:
 162   initial_ptr = (char *)AO_load(&initial_heap_ptr);
 163   my_chunk_ptr = (char *)(((AO_t)initial_ptr + (ALIGNMENT - 1))
 164                           & ~(ALIGNMENT - 1));
 165   if (initial_ptr != my_chunk_ptr)
 166     {
 167       /* Align correctly.  If this fails, someone else did it for us.   */
 168       AO_compare_and_swap_acquire(&initial_heap_ptr, (AO_t)initial_ptr,
 169                                   (AO_t)my_chunk_ptr);
 170     }
 171   my_lim = my_chunk_ptr + CHUNK_SIZE;
 172   if (my_lim <= initial_heap_lim)
 173     {
 174       if (!AO_compare_and_swap(&initial_heap_ptr, (AO_t)my_chunk_ptr,
 175                                                   (AO_t)my_lim))
 176         goto retry;
 177       return my_chunk_ptr;
 178     }
 179   /* We failed.  The initial heap is used up.   */
 180   my_chunk_ptr = get_mmaped(CHUNK_SIZE);
 181   assert (!((AO_t)my_chunk_ptr & (ALIGNMENT-1)));
 182   return my_chunk_ptr;
 183 }
 184
 185 /* Object free lists.  Ith entry corresponds to objects */
 186 /* of total size 2**i bytes.                                    */
 187 AO_stack_t AO_free_list[LOG_MAX_SIZE+1];
 188
 189 /* Chunk free list, linked through first word in chunks.        */
 190 /* All entries of size CHUNK_SIZE.                              */
 191 AO_stack_t AO_chunk_free_list;
 192
 193 /* Break up the chunk, and add it to the object free list for   */
 194 /* the given size.  Sz must be a power of two.                  */
 195 /* We have exclusive access to chunk.                           */
 196 static void
 197 add_chunk_as(void * chunk, size_t sz, unsigned log_sz)
 198 {
 199   char *first = (char *)chunk + ALIGNMENT - sizeof(AO_t);
 200   char *limit = (char *)chunk + CHUNK_SIZE - sz;
 201   char *next, *p;
 202
 203   for (p = first; p <= limit; p = next) {
 204     next = p + sz;
 205     AO_stack_push(AO_free_list+log_sz, (AO_t *)p);
 206   }
 207 }
 208
 209 static int msbs[16] = {0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4};
 210
 211 /* Return the position of the most significant set bit in the   */
 212 /* argument.                                                    */
 213 /* We follow the conventions of ffs(), i.e. the least           */
 214 /* significant bit is number one.                               */
 215 int msb(size_t s)
 216 {
 217   int result = 0;
 218   int v;
 219   if ((s & 0xff) != s) {
 220     /* The following shift often generates warnings on 32-bit arch's    */
 221     /* That's OK, because it will never be executed there.              */
 222     /* Doing the shift only in a conditional expression suppresses the  */
 223     /* warning with the modern compilers.                               */
 224     if (sizeof(size_t) > 4 && (v = s >> 32) != 0)
 225       {
 226         s = v;
 227         result += 32;
 228       }
 229     if ((s >> 16) != 0)
 230       {
 231         s >>= 16;
 232         result += 16;
 233       }
 234     if ((s >> 8) != 0)
 235       {
 236         s >>= 8;
 237         result += 8;
 238       }
 239   }
 240   if (s > 15)
 241     {
 242       s >>= 4;
 243       result += 4;
 244     }
 245   result += msbs[s];
 246   return result;
 247 }
 248
 249 void *
 250 AO_malloc(size_t sz)
 251 {
 252   AO_t *result;
 253   size_t adj_sz = sz + sizeof(AO_t);
 254   int log_sz;
 255   if (sz > CHUNK_SIZE)
 256     return AO_malloc_large(sz);
 257   log_sz = msb(adj_sz-1);
 258   result = AO_stack_pop(AO_free_list+log_sz);
 259   while (0 == result) {
 260     void * chunk = get_chunk();
 261     if (0 == chunk) return 0;
 262     adj_sz = 1 << log_sz;
 263     add_chunk_as(chunk, adj_sz, log_sz);
 264     result = AO_stack_pop(AO_free_list+log_sz);
 265   }
 266   *result = log_sz;
 267 # ifdef AO_TRACE_MALLOC
 268     fprintf(stderr, "%x: AO_malloc(%lu) = %p\n",
 269                     (int)pthread_self(), (unsigned long)sz, result+1);
 270 # endif
 271   return result + 1;
 272 }
 273
 274 void
 275 AO_free(void *p)
 276 {
 277   char *base = (char *)p - sizeof(AO_t);
 278   int log_sz;
 279
 280   if (0 == p) return;
 281   log_sz = *(AO_t *)base;
 282 # ifdef AO_TRACE_MALLOC
 283     fprintf(stderr, "%x: AO_free(%p sz:%lu)\n", (int)pthread_self(), p,
 284                     (unsigned long)
 285                       (log_sz > LOG_MAX_SIZE? log_sz : (1 << log_sz)));
 286 # endif
 287   if (log_sz > LOG_MAX_SIZE)
 288     AO_free_large(p);
 289   else
 290     AO_stack_push(AO_free_list+log_sz, (AO_t *)base);
 291 }