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 3 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
);