src/alloc-slab.c

   1 /* alloc-slab.c - Slab debugging allocator
   2  * Copyright 2005 srvx Development Team
   3  *
   4  * This file is part of srvx.
   5  *
   6  * srvx is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  */
  16
  17 #include "common.h"
  18 #include "log.h"
  19
  20 #if defined(HAVE_SYS_MMAN_H)
  21 # include <sys/mman.h>
  22 #endif
  23
  24 #if !defined(HAVE_MMAP)
  25 # error The slab allocator requires that your system have the mmap() system call.
  26 #endif
  27
  28 #define SLAB_DEBUG 1
  29
  30 #if SLAB_DEBUG
  31
  32 #define ALLOC_MAGIC 0x1acf
  33 #define FREE_MAGIC  0xfc1d
  34
  35 struct alloc_header {
  36     unsigned int file_id : 8;
  37     unsigned int size : 24;
  38     unsigned int line : 16;
  39     unsigned int magic : 16;
  40 };
  41
  42 static const char *file_ids[256];
  43 static struct file_id_entry {
  44     const char *name;
  45     unsigned int id : 8;
  46 } file_id_map[256];
  47 unsigned int file_ids_used;
  48
  49 static int
  50 file_id_cmp(const void *a_, const void *b_)
  51 {
  52     return strcmp(*(const char**)a_, *(const char**)b_);
  53 }
  54
  55 static unsigned int
  56 get_file_id(const char *fname)
  57 {
  58     struct file_id_entry *entry;
  59
  60     entry = bsearch(&fname, file_id_map, file_ids_used, sizeof(file_id_map[0]), file_id_cmp);
  61     if (entry)
  62         return entry->id;
  63     entry = file_id_map + file_ids_used;
  64     file_ids[file_ids_used] = fname;
  65     entry->name = fname;
  66     entry->id = file_ids_used;
  67     qsort(file_id_map, ++file_ids_used, sizeof(file_id_map[0]), file_id_cmp);
  68     return file_ids_used - 1;
  69 }
  70
  71 typedef struct alloc_header alloc_header_t;
  72
  73 #else
  74
  75 typedef size_t alloc_header_t;
  76
  77 #endif
  78
  79 struct slab {
  80     struct slabset *parent;
  81     struct slab *prev;
  82     struct slab *next;
  83     void *base;
  84     void **free;
  85     unsigned int used;
  86 };
  87
  88 struct slabset {
  89     struct slabset *next;
  90     struct slab *child;
  91     size_t size;
  92     size_t items_per_slab;
  93 };
  94
  95 #define SLAB_MIN     (2 * sizeof(void*))
  96 #define SLAB_GRAIN   sizeof(void*)
  97 #define SLAB_ALIGN   SLAB_GRAIN
  98 #define SMALL_CUTOFF 512
  99 /* Element size < SMALL_CUTOFF -> use small slabs.
 100  * Larger elements are allocated directly using mmap().  The largest
 101  * regularly allocated struct in srvx 1.x is smaller than
 102  * SMALL_CUTOFF, so there is not much point in coding support for
 103  * larger slabs.
 104  */
 105
 106 static struct slabset *little_slabs[SMALL_CUTOFF / SLAB_GRAIN];
 107 static struct slabset slabset_slabs;
 108 unsigned long alloc_count;
 109 unsigned long alloc_size;
 110
 111 #if defined(MAP_ANON)
 112 #elif defined(MAP_ANONYMOUS)
 113 # define MAP_ANON MAP_ANONYMOUS
 114 #else
 115 # define MAP_ANON 0
 116 #endif
 117
 118 static size_t
 119 slab_pagesize(void)
 120 {
 121     static size_t pagesize;
 122     if (pagesize
 123 #if defined(HAVE_GETPAGESIZE)
 124         || (pagesize  = getpagesize())
 125 #endif
 126 #if defined(HAVE_SYSCONF) && defined(_SC_PAGESIZE)
 127         || (pagesize = sysconf(_SC_PAGESIZE))
 128 #endif
 129 #if defined(HAVE_SYSCONF) && defined(_SC_PAGE_SIZE)
 130         || (pagesize = sysconf(_SC_PAGE_SIZE))
 131 #endif
 132         ) return pagesize;
 133     assert(0 && "unable to find system page size");
 134     return pagesize = 4096;
 135 }
 136
 137 static size_t
 138 slab_round_up(size_t size)
 139 {
 140     return (size + slab_pagesize() - 1) & ~(slab_pagesize() - 1);
 141 }
 142
 143 static void *
 144 slab_map(size_t length)
 145 {
 146     static int mmap_fd = -1;
 147     void *res;
 148
 149 #if ! MAP_ANON
 150     if (mmap_fd < 0) {
 151         mmap_fd = open("/dev/zero", 0);
 152         if (mmap_fd < 0)
 153             log_module(MAIN_LOG, LOG_FATAL, "Unable to open /dev/zero for mmap: %s", strerror(errno()));
 154     }
 155 #endif
 156     res = mmap(0, length, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, mmap_fd, 0);
 157     if (res == MAP_FAILED)
 158         log_module(MAIN_LOG, LOG_FATAL, "Unable to mmap %lu bytes (%s).", (unsigned long)length, strerror(errno));
 159     return res;
 160 }
 161
 162 static void *slab_alloc(struct slabset *sset);
 163 static void slab_unalloc(void *ptr, size_t size);
 164
 165 static struct slabset *
 166 slabset_create(size_t size)
 167 {
 168     unsigned int idx;
 169
 170     size = (size < SLAB_MIN) ? SLAB_MIN : (size + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 171     idx = size / SLAB_GRAIN;
 172     assert(idx < ArrayLength(little_slabs));
 173     if (!little_slabs[idx]) {
 174         if (!slabset_slabs.size) {
 175             unsigned int idx2 = (sizeof(struct slabset) + SLAB_GRAIN - 1) / SLAB_GRAIN;
 176             slabset_slabs.size = sizeof(struct slabset);
 177             slabset_slabs.items_per_slab = (slab_pagesize() - sizeof(struct slab)) / ((sizeof(struct slabset) + SLAB_ALIGN - 1) & ~(SLAB_ALIGN - 1));
 178             little_slabs[idx2] = &slabset_slabs;
 179             if (idx == idx2)
 180                 return &slabset_slabs;
 181         }
 182         little_slabs[idx] = slab_alloc(&slabset_slabs);
 183         little_slabs[idx]->size = size;
 184         little_slabs[idx]->items_per_slab = (slab_pagesize() - sizeof(struct slab)) / ((size + SLAB_ALIGN - 1) & ~(SLAB_ALIGN - 1));
 185     }
 186     return little_slabs[idx];
 187 }
 188
 189 static void *
 190 slab_alloc(struct slabset *sset)
 191 {
 192     struct slab *slab;
 193     void **item;
 194
 195     if (!sset->child || !sset->child->free) {
 196         unsigned int ii, step;
 197
 198         /* Allocate new slab. */
 199         item = slab_map(slab_pagesize());
 200         slab = (struct slab*)((char*)item + slab_pagesize() - sizeof(*slab));
 201         slab->base = item;
 202
 203         /* Populate free list. */
 204         step = (sset->size + SLAB_ALIGN - 1) & ~(SLAB_ALIGN - 1);
 205         for (ii = 1, item = slab->free = slab->base;
 206              ii < sset->items_per_slab;
 207              ++ii, item = (*item = (char*)item + step));
 208
 209         /* Link to parent slabset. */
 210         slab->parent = sset;
 211         if ((slab->prev = sset->child)) {
 212             slab->next = slab->prev->next;
 213             slab->prev->next = slab;
 214             if (slab->next)
 215                 slab->next->prev = slab;
 216         }
 217         sset->child = slab;
 218     }
 219
 220     slab = sset->child;
 221     item = slab->free;
 222     slab->free = *item;
 223     if (slab->used++ == sset->items_per_slab) {
 224         if (sset->child != slab) {
 225             /* Unlink slab and reinsert before sset->child. */
 226             if (slab->prev)
 227                 slab->prev->next = slab->next;
 228             if (slab->next)
 229                 slab->next->prev = slab->prev;
 230             if ((slab->prev = sset->child->prev))
 231                 slab->prev->next = slab;
 232             if ((slab->next = sset->child))
 233                 slab->next->prev = slab;
 234         } else if (slab->next) {
 235             /* Advance sset->child to next pointer. */
 236             sset->child = slab->next;
 237         }
 238     }
 239     memset(item, 0, sset->size);
 240     return item;
 241 }
 242
 243 static void
 244 slab_unalloc(void *ptr, size_t size)
 245 {
 246     void **item;
 247     struct slab *slab, *new_next;
 248
 249     item = ptr;
 250     assert(size < SMALL_CUTOFF);
 251     slab = (struct slab*)((((unsigned long)ptr | (slab_pagesize() - 1)) + 1) - sizeof(*slab));
 252     *item = slab->free;
 253     memset(item + 1, 0xde, size - sizeof(*item));
 254     slab->free = item;
 255
 256     if (slab->used-- == slab->parent->items_per_slab
 257         && slab->parent->child != slab) {
 258         new_next = slab->parent->child;
 259         slab->parent->child = slab;
 260     } else if (!slab->used) {
 261         for (new_next = slab;
 262              new_next->next && new_next->next->used;
 263              new_next = new_next->next) ;
 264         new_next = new_next->next;
 265     } else
 266         new_next = NULL;
 267
 268     if (new_next) {
 269         if (slab->prev)
 270             slab->prev->next = slab->next;
 271         if (slab->next)
 272             slab->next->prev = slab->prev;
 273         if ((slab->prev = new_next->prev))
 274             slab->prev->next = slab;
 275         if ((slab->next = new_next->next))
 276             slab->next->prev = slab;
 277     }
 278 }
 279
 280 void *
 281 slab_malloc(const char *file, unsigned int line, size_t size)
 282 {
 283     alloc_header_t *res;
 284     size_t real;
 285
 286     assert(size < 1 << 24);
 287     real = (size + sizeof(*res) + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 288     if (real < SMALL_CUTOFF)
 289         res = slab_alloc(slabset_create(real));
 290     else
 291         res = slab_map(slab_round_up(real));
 292 #if SLAB_DEBUG
 293     res->file_id = get_file_id(file);
 294     res->size = size;
 295     res->line = line;
 296     res->magic = ALLOC_MAGIC;
 297 #else
 298     *res = size;
 299     (void)file; (void)line;
 300 #endif
 301     alloc_count++;
 302     alloc_size += size;
 303     return res + 1;
 304 }
 305
 306 void *
 307 slab_realloc(const char *file, unsigned int line, void *ptr, size_t size)
 308 {
 309     alloc_header_t *orig;
 310     void *newblock;
 311     size_t osize;
 312
 313     if (!ptr)
 314         return slab_malloc(file, line, size);
 315
 316     verify(ptr);
 317     orig = (alloc_header_t*)ptr - 1;
 318 #if SLAB_DEBUG
 319     osize = orig->size;
 320 #else
 321     osize = *orig;
 322 #endif
 323     if (osize >= size)
 324         return ptr;
 325     newblock = slab_malloc(file, line, size);
 326     memcpy(newblock, ptr, size);
 327     return newblock;
 328 }
 329
 330 char *
 331 slab_strdup(const char *file, unsigned int line, const char *src)
 332 {
 333     char *target;
 334     size_t len;
 335
 336     len = strlen(src) + 1;
 337     target = slab_malloc(file, line, len);
 338     memcpy(target, src, len);
 339     return target;
 340 }
 341
 342 void
 343 slab_free(UNUSED_ARG(const char *file), UNUSED_ARG(unsigned int line), void *ptr)
 344 {
 345     alloc_header_t *hdr;
 346     size_t real;
 347
 348     if (!ptr)
 349         return;
 350     verify(ptr);
 351     hdr = (alloc_header_t*)ptr - 1;
 352 #if SLAB_DEBUG
 353     hdr->magic = FREE_MAGIC;
 354     real = hdr->size + sizeof(*hdr);
 355 #else
 356     real = *hdr + sizeof(*hdr);
 357 #endif
 358     real = (real + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 359     if (real < SMALL_CUTOFF)
 360         slab_unalloc(hdr, real);
 361     else
 362         munmap(hdr, slab_round_up(real));
 363     alloc_count--;
 364     alloc_size -= real - sizeof(*hdr);
 365 }
 366
 367 void
 368 verify(const void *ptr)
 369 {
 370     alloc_header_t *hdr;
 371     size_t real;
 372
 373     if (!ptr)
 374         return;
 375
 376     hdr = (alloc_header_t*)ptr - 1;
 377 #if SLAB_DEBUG
 378     real = hdr->size + sizeof(*hdr);
 379     assert(hdr->file_id < file_ids_used);
 380     assert(hdr->magic == ALLOC_MAGIC);
 381 #else
 382     real = *hdr + sizeof(*hdr);
 383 #endif
 384     real = (real + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 385
 386     if (real >= SMALL_CUTOFF)
 387         assert(((unsigned long)ptr & (slab_pagesize() - 1)) == sizeof(*hdr));
 388     else {
 389         struct slab *slab;
 390         size_t expected;
 391
 392         expected = (real + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 393         slab = (struct slab*)((((unsigned long)ptr | (slab_pagesize() - 1)) + 1) - sizeof(*slab));
 394         assert(slab->parent->size == expected);
 395     }
 396 }