1 /* alloc-slab.c - Slab debugging allocator
2 * Copyright 2005,2007 srvx Development Team
4 * This file is part of srvx.
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.
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.
20 #if defined(HAVE_SYS_MMAN_H)
21 # include <sys/mman.h>
24 #if !defined(HAVE_MMAP)
25 # error The slab allocator requires that your system have the mmap() system call.
28 #define SLAB_DEBUG_HEADER 1
29 #define SLAB_DEBUG_LOG 2
30 #define SLAB_DEBUG_PERMS 4
32 #if !defined(SLAB_DEBUG)
36 #if !defined(SLAB_RESERVE)
37 # define SLAB_RESERVE 0
40 #if !defined(MAX_SLAB_FREE)
41 # define MAX_SLAB_FREE 1024
44 #if SLAB_DEBUG & SLAB_DEBUG_HEADER
46 #define ALLOC_MAGIC 0x1a
47 #define FREE_MAGIC 0xcf
50 unsigned int size : 24;
51 unsigned int magic : 8;
52 unsigned int file_id : 8;
53 unsigned int line : 16;
56 static const char *file_ids[256];
57 static struct file_id_entry {
61 unsigned int file_ids_used;
64 file_id_cmp(const void *a_, const void *b_)
66 return strcmp(*(const char**)a_, *(const char**)b_);
70 get_file_id(const char *fname)
72 struct file_id_entry *entry;
74 entry = bsearch(&fname, file_id_map, file_ids_used, sizeof(file_id_map[0]), file_id_cmp);
77 entry = file_id_map + file_ids_used;
78 file_ids[file_ids_used] = fname;
80 entry->id = file_ids_used;
81 qsort(file_id_map, ++file_ids_used, sizeof(file_id_map[0]), file_id_cmp);
82 return file_ids_used - 1;
85 typedef struct alloc_header alloc_header_t;
89 typedef size_t alloc_header_t;
94 struct slabset *parent;
107 size_t items_per_slab;
110 #define SLAB_MIN (2 * sizeof(void*))
111 #define SLAB_GRAIN sizeof(void*)
112 #define SLAB_ALIGN SLAB_GRAIN
113 #define SMALL_CUTOFF 576
114 /* Element size < SMALL_CUTOFF -> use small slabs.
115 * Larger elements are allocated directly using mmap(). The largest
116 * regularly allocated struct in srvx 1.x is smaller than
117 * SMALL_CUTOFF, so there is not much point in coding support for
121 static struct slabset little_slabs[SMALL_CUTOFF / SLAB_GRAIN];
122 static struct slab *free_slab_head;
123 static struct slab *free_slab_tail;
124 unsigned long free_slab_count;
125 unsigned long big_alloc_count;
126 unsigned long big_alloc_size;
127 unsigned long slab_count;
128 unsigned long slab_alloc_count;
129 unsigned long slab_alloc_size;
131 #if defined(MAP_ANON)
132 #elif defined(MAP_ANONYMOUS)
133 # define MAP_ANON MAP_ANONYMOUS
138 #if SLAB_DEBUG & SLAB_DEBUG_LOG
142 struct slab_log_entry
156 slab_log_alloc(void *slab, size_t size)
158 struct slab_log_entry sle;
160 gettimeofday(&sle.tv, NULL);
162 sle.size = (ssize_t)size;
167 fname = getenv("SLAB_LOG_FILE");
170 slab_log = fopen(fname, "w");
171 atexit(close_slab_log);
174 fwrite(&sle, sizeof(sle), 1, slab_log);
178 slab_log_free(void *slab, size_t size)
180 struct slab_log_entry sle;
182 gettimeofday(&sle.tv, NULL);
184 sle.size = -(ssize_t)size;
185 fwrite(&sle, sizeof(sle), 1, slab_log);
189 slab_log_unmap(void *slab)
191 struct slab_log_entry sle;
193 gettimeofday(&sle.tv, NULL);
196 fwrite(&sle, sizeof(sle), 1, slab_log);
200 # define slab_log_alloc(SLAB, SIZE)
201 # define slab_log_free(SLAB, SIZE)
202 # define slab_log_unmap(SLAB)
205 #if (SLAB_DEBUG & SLAB_DEBUG_PERMS) && defined(HAVE_MPROTECT)
208 slab_protect(struct slab *slab)
210 mprotect(slab, (char*)(slab + 1) - (char*)slab->base, PROT_NONE);
214 slab_unprotect(struct slab *slab)
216 mprotect(slab, (char*)(slab + 1) - (char*)slab->base, PROT_READ | PROT_WRITE);
220 # define slab_protect(SLAB) (void)(SLAB)
221 # define slab_unprotect(SLAB) (void)(SLAB)
227 static size_t pagesize;
229 #if defined(HAVE_GETPAGESIZE)
230 || (pagesize = getpagesize())
232 #if defined(HAVE_SYSCONF) && defined(_SC_PAGESIZE)
233 || (pagesize = sysconf(_SC_PAGESIZE))
235 #if defined(HAVE_SYSCONF) && defined(_SC_PAGE_SIZE)
236 || (pagesize = sysconf(_SC_PAGE_SIZE))
239 assert(0 && "unable to find system page size");
240 return pagesize = 4096;
244 slab_round_up(size_t size)
246 return (size + slab_pagesize() - 1) & ~(slab_pagesize() - 1);
250 slab_map(size_t length)
252 static int mmap_fd = -1;
257 mmap_fd = open("/dev/zero", 0);
259 log_module(MAIN_LOG, LOG_FATAL, "Unable to open /dev/zero for mmap: %s", strerror(errno()));
262 res = mmap(0, length, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, mmap_fd, 0);
263 if (res == MAP_FAILED)
264 log_module(MAIN_LOG, LOG_FATAL, "Unable to mmap %lu bytes (%s).", (unsigned long)length, strerror(errno));
268 static void *slab_alloc(struct slabset *sset);
269 static void slab_unalloc(void *ptr, size_t size);
271 static struct slabset *
272 slabset_create(size_t size)
276 size = (size < SLAB_MIN) ? SLAB_MIN : (size + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
277 idx = size / SLAB_GRAIN;
278 assert(idx < ArrayLength(little_slabs));
279 if (!little_slabs[idx].size) {
280 little_slabs[idx].size = size;
281 little_slabs[idx].items_per_slab = (slab_pagesize() - sizeof(struct slab)) / ((size + SLAB_ALIGN - 1) & ~(SLAB_ALIGN - 1));
283 return &little_slabs[idx];
287 slab_alloc(struct slabset *sset)
292 if (!sset->child || !sset->child->free) {
293 unsigned int ii, step;
295 /* Allocate new slab. */
296 if (free_slab_head) {
297 slab = free_slab_head;
298 slab_unprotect(slab);
299 if (!(free_slab_head = slab->next))
300 free_slab_tail = NULL;
302 item = slab_map(slab_pagesize());
303 slab = (struct slab*)((char*)item + slab_pagesize() - sizeof(*slab));
307 slab_log_alloc(slab, sset->size);
309 /* Populate free list. */
310 step = (sset->size + SLAB_ALIGN - 1) & ~(SLAB_ALIGN - 1);
311 for (ii = 1, item = slab->free = slab->base;
312 ii < sset->items_per_slab;
313 ++ii, item = (*item = (char*)item + step));
316 /* Link to parent slabset. */
318 slab->prev = sset->child;
320 slab->next = slab->prev->next;
321 slab->prev->next = slab;
323 slab->next->prev = slab;
326 assert(!slab->next || slab == slab->next->prev);
327 assert(!slab->prev || slab == slab->prev->next);
334 assert(((unsigned long)item & (slab_pagesize() - 1))
335 <= (slab_pagesize() - sizeof(*slab) - sset->size));
337 if (++slab->used == sset->items_per_slab) {
338 if (sset->child != slab) {
339 /* Unlink slab and reinsert before sset->child. */
341 slab->prev->next = slab->next;
343 slab->next->prev = slab->prev;
344 if ((slab->prev = sset->child->prev))
345 slab->prev->next = slab;
346 if ((slab->next = sset->child))
347 slab->next->prev = slab;
348 assert(!slab->next || slab == slab->next->prev);
349 assert(!slab->prev || slab == slab->prev->next);
350 } else if (slab->next) {
351 /* Advance sset->child to next pointer. */
352 sset->child = slab->next;
356 memset(item, 0, sset->size);
361 slab_unalloc(void *ptr, size_t size)
363 struct slab *slab, *new_next;
365 assert(size < SMALL_CUTOFF);
366 slab = (struct slab*)((((unsigned long)ptr | (slab_pagesize() - 1)) + 1) - sizeof(*slab));
367 *(void**)ptr = slab->free;
369 slab->parent->nallocs--;
371 if (slab->used-- == slab->parent->items_per_slab
372 && slab->parent->child != slab) {
373 /* Unlink from current position, relink as parent's first child. */
374 new_next = slab->parent->child;
375 assert(new_next != NULL);
377 slab->prev->next = slab->next;
379 slab->next->prev = slab->prev;
380 if ((slab->prev = new_next->prev))
381 slab->prev->next = slab;
382 slab->next = new_next;
383 new_next->prev = slab;
384 slab->parent->child = slab;
385 assert(!slab->next || slab == slab->next->prev);
386 assert(!slab->prev || slab == slab->prev->next);
387 } else if (!slab->used) {
388 slab_log_free(slab, size);
390 /* Unlink slab from its parent. */
391 slab->parent->nslabs--;
393 slab->prev->next = slab->next;
395 slab->next->prev = slab->prev;
396 new_next = slab->next ? slab->next : slab->prev;
397 if (slab == slab->parent->child)
398 slab->parent->child = new_next;
400 assert(!new_next->next || new_next == new_next->next->prev);
401 assert(!new_next->prev || new_next == new_next->prev->next);
405 /* Make sure we have enough free slab pages. */
406 while (free_slab_count < SLAB_RESERVE) {
410 item = slab_map(slab_pagesize());
411 tslab = (struct slab*)((char*)item + slab_pagesize() - sizeof(*slab));
413 tslab->prev = free_slab_tail;
414 free_slab_tail = tslab;
416 free_slab_head = tslab;
418 slab_unprotect(tslab->prev);
419 tslab->prev->next = tslab;
420 slab_protect(tslab->prev);
427 /* Link to list of free slabs. */
430 slab->prev = free_slab_tail;
432 slab_unprotect(slab->prev);
433 slab->prev->next = slab;
434 slab_protect(slab->prev);
436 free_slab_head = slab;
438 free_slab_tail = slab;
441 #if MAX_SLAB_FREE >= 0
442 /* Unlink and unmap old slabs, so accesses to stale-enough
443 * pointers will fault. */
444 while (free_slab_count > MAX_SLAB_FREE) {
447 tslab = free_slab_tail;
448 slab_unprotect(tslab);
449 free_slab_tail = tslab->prev;
451 slab_unprotect(tslab->prev);
452 tslab->prev->next = NULL;
453 slab_protect(tslab->prev);
455 free_slab_head = NULL;
458 slab_log_unmap(slab);
459 munmap(slab->base, slab_pagesize());
467 slab_malloc(const char *file, unsigned int line, size_t size)
472 assert(size < 1 << 24);
473 real = (size + sizeof(*res) + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
474 if (real < SMALL_CUTOFF) {
475 res = slab_alloc(slabset_create(real));
477 slab_alloc_size += size;
479 res = slab_map(slab_round_up(real));
481 big_alloc_size += size;
482 slab_log_alloc(res, size);
484 #if SLAB_DEBUG & SLAB_DEBUG_HEADER
485 res->file_id = get_file_id(file);
488 res->magic = ALLOC_MAGIC;
491 (void)file; (void)line;
497 slab_realloc(const char *file, unsigned int line, void *ptr, size_t size)
499 alloc_header_t *orig;
504 return slab_malloc(file, line, size);
507 orig = (alloc_header_t*)ptr - 1;
508 #if SLAB_DEBUG & SLAB_DEBUG_HEADER
515 newblock = slab_malloc(file, line, size);
516 memcpy(newblock, ptr, osize);
517 slab_free(file, line, ptr);
522 slab_strdup(const char *file, unsigned int line, const char *src)
527 len = strlen(src) + 1;
528 target = slab_malloc(file, line, len);
529 memcpy(target, src, len);
534 slab_free(const char *file, unsigned int line, void *ptr)
542 hdr = (alloc_header_t*)ptr - 1;
543 #if SLAB_DEBUG & SLAB_DEBUG_HEADER
544 hdr->file_id = get_file_id(file);
546 hdr->magic = FREE_MAGIC;
550 (void)file; (void)line;
552 real = (user + sizeof(*hdr) + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
553 if (real < SMALL_CUTOFF) {
554 memset(hdr + 1, 0xde, real - sizeof(*hdr));
555 slab_unalloc(hdr, real);
557 slab_alloc_size -= user;
559 munmap(hdr, slab_round_up(real));
561 big_alloc_size -= user;
566 /* Undefine the verify macro in case we're not debugging. */
569 verify(const void *ptr)
577 hdr = (alloc_header_t*)ptr - 1;
578 #if SLAB_DEBUG & SLAB_DEBUG_HEADER
579 real = hdr->size + sizeof(*hdr);
580 assert(hdr->file_id < file_ids_used);
581 assert(hdr->magic == ALLOC_MAGIC);
583 real = *hdr + sizeof(*hdr);
585 real = (real + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
587 if (real >= SMALL_CUTOFF)
588 assert(((unsigned long)ptr & (slab_pagesize() - 1)) == sizeof(*hdr));
593 expected = (real + SLAB_GRAIN - 1) & ~(SLAB_GRAIN - 1);
594 slab = (struct slab*)((((unsigned long)ptr | (slab_pagesize() - 1)) + 1) - sizeof(*slab));
595 assert(slab->parent->size == expected);