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 struct slab {
  29     struct slabset *parent;
  30     struct slab *prev;
  31     struct slab *next;
  32     void *base;
  33     void **free;
  34     unsigned int used;
  35 };
  36
  37 struct slabset {
  38     struct slabset *next;
  39     struct slab *child;
  40     size_t size;
  41     size_t items_per_slab;
  42 };
  43
  44 #define SLAB_MIN     (2 * sizeof(void*))
  45 #define SLAB_GRAIN   sizeof(void*)
  46 #define SLAB_ALIGN   SLAB_GRAIN
  47 #define SMALL_CUTOFF 512
  48 /* Element size < SMALL_CUTOFF -> use small slabs.
  49  * Larger elements are allocated directly using mmap().  The largest
  50  * regularly allocated struct in srvx 1.x is smaller than
  51  * SMALL_CUTOFF, so there is not much point in coding support for
  52  * larger slabs.
  53  */
  54
  55 static struct slabset *little_slabs[SMALL_CUTOFF / SLAB_GRAIN];
  56 static struct slabset slabset_slabs;
  57 unsigned long alloc_count;
  58 unsigned long alloc_size;
  59
  60 #if defined(MAP_ANON)
  61 #elif defined(MAP_ANONYMOUS)
  62 # define MAP_ANON MAP_ANONYMOUS
  63 #else
  64 # define MAP_ANON 0
  65 #endif
  66
  67 static size_t
  68 slab_pagesize(void)
  69 {
  70     static size_t pagesize;
  71     if (pagesize
  72 #if defined(HAVE_GETPAGESIZE)
  73         || (pagesize  = getpagesize())
  74 #endif
  75 #if defined(HAVE_SYSCONF) && defined(_SC_PAGESIZE)
  76         || (pagesize = sysconf(_SC_PAGESIZE))
  77 #endif
  78 #if defined(HAVE_SYSCONF) && defined(_SC_PAGE_SIZE)
  79         || (pagesize = sysconf(_SC_PAGE_SIZE))
  80 #endif
  81         ) return pagesize;
  82     assert(0 && "unable to find system page size");
  83     return pagesize = 4096;
  84 }
  85
  86 static size_t
  87 slab_round_up(size_t size)
  88 {
  89     return (size + slab_pagesize() - 1) & ~(slab_pagesize() - 1);
  90 }
  91
  92 static void *
  93 slab_map(size_t length)
  94 {
  95     static int mmap_fd = -1;
  96     void *res;
  97
  98 #if ! MAP_ANON
  99     if (mmap_fd < 0) {
 100         mmap_fd = open("/dev/zero", 0);
 101         if (mmap_fd < 0)
 102             log_module(MAIN_LOG, LOG_FATAL, "Unable to open /dev/zero for mmap: %s", strerror(errno()));
 103     }
 104 #endif
 105     res = mmap(0, length, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, mmap_fd, 0);
 106     if (res == MAP_FAILED)
 107         log_module(MAIN_LOG, LOG_FATAL, "Unable to mmap %lu bytes (%s).", (unsigned long)length, strerror(errno));
 108     return res;
 109 }
 110
 111 static void *slab_alloc(struct slabset *sset);
 112 static void slab_unalloc(void *ptr, size_t size);
 113
 114 static struct slabset *
 115 slabset_create(size_t size)
 116 {
 117     unsigned int idx;
 118
 119     size = (size < SLAB_MIN) ? SLAB_MIN : (size + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 120     idx = size / SLAB_GRAIN;
 121     assert(idx < ArrayLength(little_slabs));
 122     if (!little_slabs[idx]) {
 123         if (!slabset_slabs.size) {
 124             unsigned int idx2 = (sizeof(struct slabset) + SLAB_GRAIN - 1) / SLAB_GRAIN;
 125             slabset_slabs.size = sizeof(struct slabset);
 126             slabset_slabs.items_per_slab = (slab_pagesize() - sizeof(struct slab)) / ((sizeof(struct slabset) + SLAB_ALIGN - 1) & ~(SLAB_ALIGN - 1));
 127             little_slabs[idx2] = &slabset_slabs;
 128             if (idx == idx2)
 129                 return &slabset_slabs;
 130         }
 131         little_slabs[idx] = slab_alloc(&slabset_slabs);
 132         little_slabs[idx]->size = size;
 133         little_slabs[idx]->items_per_slab = (slab_pagesize() - sizeof(struct slab)) / ((size + SLAB_ALIGN - 1) & ~(SLAB_ALIGN - 1));
 134     }
 135     return little_slabs[idx];
 136 }
 137
 138 static void *
 139 slab_alloc(struct slabset *sset)
 140 {
 141     struct slab *slab;
 142     void **item;
 143
 144     if (!sset->child || !sset->child->free) {
 145         unsigned int ii, step;
 146
 147         /* Allocate new slab. */
 148         item = slab_map(slab_pagesize());
 149         slab = (struct slab*)((char*)item + slab_pagesize() - sizeof(*slab));
 150         slab->base = item;
 151
 152         /* Populate free list. */
 153         step = (sset->size + SLAB_ALIGN - 1) & ~(SLAB_ALIGN - 1);
 154         for (ii = 1, item = slab->free = slab->base;
 155              ii < sset->items_per_slab;
 156              ++ii, item = (*item = (char*)item + step));
 157
 158         /* Link to parent slabset. */
 159         slab->parent = sset;
 160         if ((slab->prev = sset->child)) {
 161             slab->next = slab->prev->next;
 162             slab->prev->next = slab;
 163             if (slab->next)
 164                 slab->next->prev = slab;
 165         }
 166         sset->child = slab;
 167     }
 168
 169     slab = sset->child;
 170     item = slab->free;
 171     slab->free = *item;
 172     if (slab->used++ == sset->items_per_slab) {
 173         if (sset->child != slab) {
 174             /* Unlink slab and reinsert before sset->child. */
 175             if (slab->prev)
 176                 slab->prev->next = slab->next;
 177             if (slab->next)
 178                 slab->next->prev = slab->prev;
 179             if ((slab->prev = sset->child->prev))
 180                 slab->prev->next = slab;
 181             if ((slab->next = sset->child))
 182                 slab->next->prev = slab;
 183         } else if (slab->next) {
 184             /* Advance sset->child to next pointer. */
 185             sset->child = slab->next;
 186         }
 187     }
 188     memset(item, 0, sset->size);
 189     return item;
 190 }
 191
 192 static void
 193 slab_unalloc(void *ptr, size_t size)
 194 {
 195     void **item;
 196     struct slab *slab, *new_next;
 197
 198     item = ptr;
 199     assert(size < SMALL_CUTOFF);
 200     slab = (struct slab*)((((unsigned long)ptr | (slab_pagesize() - 1)) + 1) - sizeof(*slab));
 201     *item = slab->free;
 202     slab->free = item;
 203
 204     if (slab->used-- == slab->parent->items_per_slab
 205         && slab->parent->child != slab) {
 206         new_next = slab->parent->child;
 207         slab->parent->child = slab;
 208     } else if (!slab->used) {
 209         for (new_next = slab;
 210              new_next->next && new_next->next->used;
 211              new_next = new_next->next) ;
 212         new_next = new_next->next;
 213     } else
 214         new_next = NULL;
 215
 216     if (new_next) {
 217         if (slab->prev)
 218             slab->prev->next = slab->next;
 219         if (slab->next)
 220             slab->next->prev = slab->prev;
 221         if ((slab->prev = new_next->prev))
 222             slab->prev->next = slab;
 223         if ((slab->next = new_next->next))
 224             slab->next->prev = slab;
 225     }
 226 }
 227
 228 void *
 229 slab_malloc(UNUSED_ARG(const char *file), UNUSED_ARG(unsigned int line), size_t size)
 230 {
 231     size_t real, *res;
 232
 233     real = size + sizeof(size_t);
 234     if (real < SMALL_CUTOFF)
 235         res = slab_alloc(slabset_create(real));
 236     else
 237         res = slab_map(slab_round_up(real));
 238     *res = size;
 239     return res + 1;
 240 }
 241
 242 void *
 243 slab_realloc(const char *file, unsigned int line, void *ptr, size_t size)
 244 {
 245     size_t orig, *newblock;
 246
 247     if (!ptr)
 248         return slab_malloc(file, line, size);
 249
 250     verify(ptr);
 251     orig = ((size_t*)ptr)[-1];
 252     if (orig >= size)
 253         return ptr;
 254     newblock = slab_malloc(file, line, size);
 255     memcpy(newblock, ptr, orig);
 256     return newblock;
 257 }
 258
 259 char *
 260 slab_strdup(const char *file, unsigned int line, const char *src)
 261 {
 262     char *target;
 263     size_t len;
 264
 265     len = strlen(src) + 1;
 266     target = slab_malloc(file, line, len);
 267     memcpy(target, src, len);
 268     return target;
 269 }
 270
 271 void
 272 slab_free(UNUSED_ARG(const char *file), UNUSED_ARG(unsigned int line), void *ptr)
 273 {
 274     size_t real, *size;
 275
 276     if (!ptr)
 277         return;
 278     verify(ptr);
 279     size = (size_t*)ptr - 1;
 280     real = *size + sizeof(size_t);
 281     if (real < SMALL_CUTOFF)
 282         slab_unalloc(size, real);
 283     else
 284         munmap(size, slab_round_up(real));
 285 }
 286
 287 void
 288 verify(const void *ptr)
 289 {
 290     size_t size;
 291
 292     if (!ptr)
 293         return;
 294     else if ((size = ((size_t*)ptr)[-1] + sizeof(size_t)) >= SMALL_CUTOFF)
 295         assert(((unsigned long)ptr & (slab_pagesize() - 1)) == sizeof(size_t));
 296     else {
 297         struct slab *slab;
 298         size_t expected;
 299
 300         expected = (size + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
 301         slab = (struct slab*)((((unsigned long)ptr | (slab_pagesize() - 1)) + 1) - sizeof(*slab));
 302         assert(slab->parent->size == expected);
 303     }
 304 }