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 0
  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 slab *child;
  90     size_t nslabs;
  91     size_t nallocs;
  92     size_t size;
  93     size_t items_per_slab;
  94 };
  95
  96 #define SLAB_MIN     (2 * sizeof(void*))
  97 #define SLAB_GRAIN   sizeof(void*)
  98 #define SLAB_ALIGN   SLAB_GRAIN
  99 #define SMALL_CUTOFF 582
 100 /* Element size < SMALL_CUTOFF -> use small slabs.
 101  * Larger elements are allocated directly using mmap().  The largest
 102  * regularly allocated struct in srvx 1.x is smaller than
 103  * SMALL_CUTOFF, so there is not much point in coding support for
 104  * larger slabs.
 105  */
 106
 107 static struct slabset little_slabs[SMALL_CUTOFF / SLAB_GRAIN];
 108 static struct slab *free_slabs;
 109 unsigned long big_alloc_count;
 110 unsigned long big_alloc_size;
 111 unsigned long slab_count;
 112 unsigned long slab_alloc_count;
 113 unsigned long slab_alloc_size;
 114
 115 #if defined(MAP_ANON)
 116 #elif defined(MAP_ANONYMOUS)
 117 # define MAP_ANON MAP_ANONYMOUS
 118 #else
 119 # define MAP_ANON 0
 120 #endif
 121
 122 static size_t
 123 slab_pagesize(void)
 124 {
 125     static size_t pagesize;
 126     if (pagesize
 127 #if defined(HAVE_GETPAGESIZE)
 128         || (pagesize  = getpagesize())
 129 #endif
 130 #if defined(HAVE_SYSCONF) && defined(_SC_PAGESIZE)
 131         || (pagesize = sysconf(_SC_PAGESIZE))
 132 #endif
 133 #if defined(HAVE_SYSCONF) && defined(_SC_PAGE_SIZE)
 134         || (pagesize = sysconf(_SC_PAGE_SIZE))
 135 #endif
 136         ) return pagesize;
 137     assert(0 && "unable to find system page size");
 138     return pagesize = 4096;
 139 }
 140
 141 static size_t
 142 slab_round_up(size_t size)
 143 {
 144     return (size + slab_pagesize() - 1) & ~(slab_pagesize() - 1);
 145 }
 146
 147 static void *
 148 slab_map(size_t length)
 149 {
 150     static int mmap_fd = -1;
 151     void *res;
 152
 153 #if ! MAP_ANON
 154     if (mmap_fd < 0) {
 155         mmap_fd = open("/dev/zero", 0);
 156         if (mmap_fd < 0)
 157             log_module(MAIN_LOG, LOG_FATAL, "Unable to open /dev/zero for mmap: %s", strerror(errno()));
 158     }
 159 #endif
 160     res = mmap(0, length, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, mmap_fd, 0);
 161     if (res == MAP_FAILED)
 162         log_module(MAIN_LOG, LOG_FATAL, "Unable to mmap %lu bytes (%s).", (unsigned long)length, strerror(errno));
 163     return res;
 164 }
 165
 166 static void *slab_alloc(struct slabset *sset);
 167 static void slab_unalloc(void *ptr, size_t size);
 168
 169 static struct slabset *
 170 slabset_create(size_t size)
 171 {
 172     unsigned int idx;
 173
 174     size = (size < SLAB_MIN) ? SLAB_MIN : (size + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 175     idx = size / SLAB_GRAIN;
 176     assert(idx < ArrayLength(little_slabs));
 177     if (!little_slabs[idx].size) {
 178         little_slabs[idx].size = size;
 179         little_slabs[idx].items_per_slab = (slab_pagesize() - sizeof(struct slab)) / ((size + SLAB_ALIGN - 1) & ~(SLAB_ALIGN - 1));
 180     }
 181     return &little_slabs[idx];
 182 }
 183
 184 static void *
 185 slab_alloc(struct slabset *sset)
 186 {
 187     struct slab *slab;
 188     void **item;
 189
 190     if (!sset->child || !sset->child->free) {
 191         unsigned int ii, step;
 192
 193         /* Allocate new slab. */
 194         if (free_slabs) {
 195             slab = free_slabs;
 196             free_slabs = slab->next;
 197         } else {
 198             item = slab_map(slab_pagesize());
 199             slab = (struct slab*)((char*)item + slab_pagesize() - sizeof(*slab));
 200             slab->base = item;
 201         }
 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         *item = NULL;
 209
 210         /* Link to parent slabset. */
 211         slab->parent = sset;
 212         slab->prev = sset->child;
 213         if (slab->prev) {
 214             slab->next = slab->prev->next;
 215             slab->prev->next = slab;
 216             if (slab->next)
 217                 slab->next->prev = slab;
 218         } else
 219             slab->next = NULL;
 220         assert(!slab->next || slab == slab->next->prev);
 221         assert(!slab->prev || slab == slab->prev->next);
 222         sset->child = slab;
 223         sset->nslabs++;
 224         slab_count++;
 225         /* log_module(MAIN_LOG, LOG_DEBUG, "Allocated new %u-slab %p.", sset->size, slab); */
 226     }
 227
 228     slab = sset->child;
 229     item = slab->free;
 230     assert(((unsigned long)item & (slab_pagesize() - 1))
 231            <= (slab_pagesize() - sizeof(*slab) - sset->size));
 232     slab->free = *item;
 233     if (++slab->used == sset->items_per_slab) {
 234         /* log_module(MAIN_LOG, LOG_DEBUG, "%u-slab %p is empty.", sset->size, item); */
 235         if (sset->child != slab) {
 236             /* Unlink slab and reinsert before sset->child. */
 237             if (slab->prev)
 238                 slab->prev->next = slab->next;
 239             if (slab->next)
 240                 slab->next->prev = slab->prev;
 241             if ((slab->prev = sset->child->prev))
 242                 slab->prev->next = slab;
 243             if ((slab->next = sset->child))
 244                 slab->next->prev = slab;
 245             assert(!slab->next || slab == slab->next->prev);
 246             assert(!slab->prev || slab == slab->prev->next);
 247         } else if (slab->next) {
 248             /* Advance sset->child to next pointer. */
 249             sset->child = slab->next;
 250         }
 251     }
 252     sset->nallocs++;
 253     memset(item, 0, sset->size);
 254     return item;
 255 }
 256
 257 static void
 258 slab_unalloc(void *ptr, size_t size)
 259 {
 260     void **item;
 261     struct slab *slab, *new_next;
 262
 263     item = ptr;
 264     assert(size < SMALL_CUTOFF);
 265     slab = (struct slab*)((((unsigned long)ptr | (slab_pagesize() - 1)) + 1) - sizeof(*slab));
 266     *item = slab->free;
 267     memset(item + 1, 0xde, size - sizeof(*item));
 268     slab->free = item;
 269     slab->parent->nallocs--;
 270
 271     if (slab->used-- == slab->parent->items_per_slab
 272         && slab->parent->child != slab) {
 273         /* Unlink from current position, relink as parent's first child. */
 274         new_next = slab->parent->child;
 275         assert(new_next != NULL);
 276         if (slab->prev)
 277             slab->prev->next = slab->next;
 278         if (slab->next)
 279             slab->next->prev = slab->prev;
 280         if ((slab->prev = new_next->prev))
 281             slab->prev->next = slab;
 282         slab->next = new_next;
 283         new_next->prev = slab;
 284         slab->parent->child = slab;
 285         assert(!slab->next || slab == slab->next->prev);
 286         assert(!slab->prev || slab == slab->prev->next);
 287         /* log_module(MAIN_LOG, LOG_DEBUG, "%u-slab %p became partial.", slab->parent->size, slab); */
 288     } else if (!slab->used) {
 289         /* log_module(MAIN_LOG, LOG_DEBUG, "%u-slab %p became full.", slab->parent->size, slab); */
 290         /* Unlink slab from its parent. */
 291         slab->parent->nslabs--;
 292         slab_count--;
 293         if (slab->prev)
 294             slab->prev->next = slab->next;
 295         if (slab->next)
 296             slab->next->prev = slab->prev;
 297         new_next = slab->next ? slab->next : slab->prev;
 298         if (slab == slab->parent->child)
 299             slab->parent->child = new_next;
 300         if (new_next) {
 301             assert(!new_next->next || new_next == new_next->next->prev);
 302             assert(!new_next->prev || new_next == new_next->prev->next);
 303         }
 304
 305         /* Link to list of free slabs. */
 306         slab->prev = NULL;
 307         slab->parent = NULL;
 308         slab->next = free_slabs;
 309         free_slabs = slab;
 310     }
 311 }
 312
 313 void *
 314 slab_malloc(const char *file, unsigned int line, size_t size)
 315 {
 316     alloc_header_t *res;
 317     size_t real;
 318
 319     assert(size < 1 << 24);
 320     real = (size + sizeof(*res) + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 321     if (real < SMALL_CUTOFF) {
 322         res = slab_alloc(slabset_create(real));
 323         slab_alloc_count++;
 324         slab_alloc_size += size;
 325     } else {
 326         res = slab_map(slab_round_up(real));
 327         big_alloc_count++;
 328         big_alloc_size += size;
 329     }
 330 #if SLAB_DEBUG
 331     res->file_id = get_file_id(file);
 332     res->size = size;
 333     res->line = line;
 334     res->magic = ALLOC_MAGIC;
 335 #else
 336     *res = size;
 337     (void)file; (void)line;
 338 #endif
 339     return res + 1;
 340 }
 341
 342 void *
 343 slab_realloc(const char *file, unsigned int line, void *ptr, size_t size)
 344 {
 345     alloc_header_t *orig;
 346     void *newblock;
 347     size_t osize;
 348
 349     if (!ptr)
 350         return slab_malloc(file, line, size);
 351
 352     verify(ptr);
 353     orig = (alloc_header_t*)ptr - 1;
 354 #if SLAB_DEBUG
 355     osize = orig->size;
 356 #else
 357     osize = *orig;
 358 #endif
 359     if (osize >= size)
 360         return ptr;
 361     newblock = slab_malloc(file, line, size);
 362     memcpy(newblock, ptr, osize);
 363     return newblock;
 364 }
 365
 366 char *
 367 slab_strdup(const char *file, unsigned int line, const char *src)
 368 {
 369     char *target;
 370     size_t len;
 371
 372     len = strlen(src) + 1;
 373     target = slab_malloc(file, line, len);
 374     memcpy(target, src, len);
 375     return target;
 376 }
 377
 378 void
 379 slab_free(UNUSED_ARG(const char *file), UNUSED_ARG(unsigned int line), void *ptr)
 380 {
 381     alloc_header_t *hdr;
 382     size_t real;
 383
 384     if (!ptr)
 385         return;
 386     verify(ptr);
 387     hdr = (alloc_header_t*)ptr - 1;
 388 #if SLAB_DEBUG
 389     hdr->magic = FREE_MAGIC;
 390     real = hdr->size + sizeof(*hdr);
 391 #else
 392     real = *hdr + sizeof(*hdr);
 393 #endif
 394     real = (real + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 395     if (real < SMALL_CUTOFF) {
 396         slab_unalloc(hdr, real);
 397         slab_alloc_count--;
 398         slab_alloc_size -= real - sizeof(*hdr);
 399     } else {
 400         munmap(hdr, slab_round_up(real));
 401         big_alloc_count--;
 402         big_alloc_size -= real - sizeof(*hdr);
 403     }
 404 }
 405
 406 void
 407 verify(const void *ptr)
 408 {
 409     alloc_header_t *hdr;
 410     size_t real;
 411
 412     if (!ptr)
 413         return;
 414
 415     hdr = (alloc_header_t*)ptr - 1;
 416 #if SLAB_DEBUG
 417     real = hdr->size + sizeof(*hdr);
 418     assert(hdr->file_id < file_ids_used);
 419     assert(hdr->magic == ALLOC_MAGIC);
 420 #else
 421     real = *hdr + sizeof(*hdr);
 422 #endif
 423     real = (real + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 424
 425     if (real >= SMALL_CUTOFF)
 426         assert(((unsigned long)ptr & (slab_pagesize() - 1)) == sizeof(*hdr));
 427     else {
 428         struct slab *slab;
 429         size_t expected;
 430
 431         expected = (real + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 432         slab = (struct slab*)((((unsigned long)ptr | (slab_pagesize() - 1)) + 1) - sizeof(*slab));
 433         assert(slab->parent->size == expected);
 434     }
 435 }