1 /* sl_malloc.c - malloc routines using a per-thread slab */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 * Copyright 2003-2009 The OpenLDAP Foundation.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
12 * A copy of this license is available in the file LICENSE in the
13 * top-level directory of the distribution or, alternatively, at
14 * <http://www.OpenLDAP.org/license.html>.
20 #include <ac/string.h>
24 static struct slab_object * slap_replenish_sopool(struct slab_heap* sh);
26 static void print_slheap(int level, void *ctx);
35 struct slab_heap *sh = data;
36 int pad = 2*sizeof(int)-1, pad_shift;
37 int order_start = -1, i;
38 struct slab_object *so;
41 ber_memfree_x(sh->sh_base, NULL);
42 ber_memfree_x(sh, NULL);
47 } while (pad_shift >>= 1);
49 for (i = 0; i <= sh->sh_maxorder - order_start; i++) {
50 so = LDAP_LIST_FIRST(&sh->sh_free[i]);
52 struct slab_object *so_tmp = so;
53 so = LDAP_LIST_NEXT(so, so_link);
54 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_tmp, so_link);
56 ch_free(sh->sh_map[i]);
61 so = LDAP_LIST_FIRST(&sh->sh_sopool);
63 struct slab_object *so_tmp = so;
64 so = LDAP_LIST_NEXT(so, so_link);
65 if (!so_tmp->so_blockhead) {
66 LDAP_LIST_REMOVE(so_tmp, so_link);
69 so = LDAP_LIST_FIRST(&sh->sh_sopool);
71 struct slab_object *so_tmp = so;
72 so = LDAP_LIST_NEXT(so, so_link);
75 ber_memfree_x(sh->sh_base, NULL);
76 ber_memfree_x(sh, NULL);
80 BerMemoryFunctions slap_sl_mfuncs =
81 { slap_sl_malloc, slap_sl_calloc, slap_sl_realloc, slap_sl_free };
86 ber_set_option( NULL, LBER_OPT_MEMORY_FNS, &slap_sl_mfuncs );
90 static struct slab_heap *slheap;
93 /* This allocator always returns memory aligned on a 2-int boundary.
95 * The stack-based allocator stores the size as a ber_len_t at both
96 * the head and tail of the allocated block. When freeing a block, the
97 * tail length is ORed with 1 to mark it as free. Freed space can only
98 * be reclaimed from the tail forward. If the tail block is never freed,
99 * nothing else will be reclaimed until the slab is reset...
109 struct slab_heap *sh;
110 ber_len_t size_shift;
111 int pad = 2*sizeof(int)-1, pad_shift;
112 int order = -1, order_start = -1, order_end = -1;
114 struct slab_object *so;
120 ldap_pvt_thread_pool_getkey(
121 ctx, (void *)slap_sl_mem_init, &sh_tmp, NULL );
128 /* round up to doubleword boundary */
134 sh = ch_malloc(sizeof(struct slab_heap));
135 sh->sh_base = ch_malloc(size);
139 ldap_pvt_thread_pool_setkey(ctx, (void *)slap_sl_mem_init,
140 (void *)sh, slap_sl_mem_destroy, NULL, NULL);
142 } else if ( size > (char *)sh->sh_end - (char *)sh->sh_base ) {
145 newptr = ch_realloc( sh->sh_base, size );
146 if ( newptr == NULL ) return NULL;
147 sh->sh_base = newptr;
149 /* insert dummy len */
151 ber_len_t *i = sh->sh_base;
155 sh->sh_end = (char *) sh->sh_base + size;
156 sh->sh_stack = stack;
159 size_shift = size - 1;
162 } while (size_shift >>= 1);
167 } while (pad_shift >>= 1);
169 order = order_end - order_start + 1;
172 sh = (struct slab_heap *) ch_malloc(sizeof(struct slab_heap));
173 sh->sh_base = ch_malloc(size);
177 ldap_pvt_thread_pool_setkey(ctx, (void *)slap_sl_mem_init,
178 (void *)sh, slap_sl_mem_destroy, NULL, NULL);
181 for (i = 0; i <= sh->sh_maxorder - order_start; i++) {
182 so = LDAP_LIST_FIRST(&sh->sh_free[i]);
184 struct slab_object *so_tmp = so;
185 so = LDAP_LIST_NEXT(so, so_link);
186 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_tmp, so_link);
188 ch_free(sh->sh_map[i]);
190 ch_free(sh->sh_free);
193 so = LDAP_LIST_FIRST(&sh->sh_sopool);
195 struct slab_object *so_tmp = so;
196 so = LDAP_LIST_NEXT(so, so_link);
197 if (!so_tmp->so_blockhead) {
198 LDAP_LIST_REMOVE(so_tmp, so_link);
201 so = LDAP_LIST_FIRST(&sh->sh_sopool);
203 struct slab_object *so_tmp = so;
204 so = LDAP_LIST_NEXT(so, so_link);
208 if (size > (char *)sh->sh_end - (char *)sh->sh_base) {
211 newptr = ch_realloc( sh->sh_base, size );
212 if ( newptr == NULL ) return NULL;
213 sh->sh_base = newptr;
216 sh->sh_end = (char *)sh->sh_base + size;
217 sh->sh_maxorder = order_end;
219 sh->sh_free = (struct sh_freelist *)
220 ch_malloc(order * sizeof(struct sh_freelist));
221 for (i = 0; i < order; i++) {
222 LDAP_LIST_INIT(&sh->sh_free[i]);
225 LDAP_LIST_INIT(&sh->sh_sopool);
227 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
228 slap_replenish_sopool(sh);
230 so = LDAP_LIST_FIRST(&sh->sh_sopool);
231 LDAP_LIST_REMOVE(so, so_link);
232 so->so_ptr = sh->sh_base;
234 LDAP_LIST_INSERT_HEAD(&sh->sh_free[order-1], so, so_link);
236 sh->sh_map = (unsigned char **)
237 ch_malloc(order * sizeof(unsigned char *));
238 for (i = 0; i < order; i++) {
239 int shiftamt = order_start + 1 + i;
240 int nummaps = size >> shiftamt;
243 if (!nummaps) nummaps = 1;
244 sh->sh_map[i] = (unsigned char *) ch_malloc(nummaps);
245 memset(sh->sh_map[i], 0, nummaps);
247 sh->sh_stack = stack;
261 /* separate from context */
262 ldap_pvt_thread_pool_setkey( ctx, (void *)slap_sl_mem_init,
263 NULL, 0, NULL, NULL );
273 struct slab_heap *sh = ctx;
274 int pad = 2*sizeof(int)-1, pad_shift;
275 ber_len_t *ptr, *newptr;
277 #ifdef SLAP_NO_SL_MALLOC
278 newptr = ber_memalloc_x( size, NULL );
279 if ( newptr ) return newptr;
281 exit( EXIT_FAILURE );
284 /* ber_set_option calls us like this */
286 newptr = ber_memalloc_x( size, NULL );
287 if ( newptr ) return newptr;
289 exit( EXIT_FAILURE );
292 /* round up to doubleword boundary, plus space for len at head and tail */
293 size += 2*sizeof(ber_len_t) + pad;
297 if ((char *)sh->sh_last + size >= (char *)sh->sh_end) {
298 Debug(LDAP_DEBUG_TRACE,
299 "slap_sl_malloc of %lu bytes failed, using ch_malloc\n",
301 return ch_malloc(size);
303 newptr = sh->sh_last;
304 sh->sh_last = (char *) sh->sh_last + size;
305 size -= sizeof(ber_len_t);
307 *(ber_len_t *)((char *)sh->sh_last - sizeof(ber_len_t)) = size;
308 return( (void *)newptr );
310 struct slab_object *so_new, *so_left, *so_right;
311 ber_len_t size_shift;
312 int order = -1, order_start = -1;
316 size_shift = size - 1;
319 } while (size_shift >>= 1);
324 } while (pad_shift >>= 1);
326 for (i = order; i <= sh->sh_maxorder &&
327 LDAP_LIST_EMPTY(&sh->sh_free[i-order_start]); i++);
330 so_new = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
331 LDAP_LIST_REMOVE(so_new, so_link);
332 ptr = so_new->so_ptr;
333 diff = (unsigned long)((char*)ptr -
334 (char*)sh->sh_base) >> (order + 1);
335 sh->sh_map[order-order_start][diff>>3] |= (1 << (diff & 0x7));
336 *ptr++ = size - sizeof(ber_len_t);
337 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_new, so_link);
339 } else if (i <= sh->sh_maxorder) {
340 for (j = i; j > order; j--) {
341 so_left = LDAP_LIST_FIRST(&sh->sh_free[j-order_start]);
342 LDAP_LIST_REMOVE(so_left, so_link);
343 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
344 slap_replenish_sopool(sh);
346 so_right = LDAP_LIST_FIRST(&sh->sh_sopool);
347 LDAP_LIST_REMOVE(so_right, so_link);
348 so_right->so_ptr = (void *)((char *)so_left->so_ptr + (1 << j));
349 if (j == order + 1) {
350 ptr = so_left->so_ptr;
351 diff = (unsigned long)((char*)ptr -
352 (char*)sh->sh_base) >> (order+1);
353 sh->sh_map[order-order_start][diff>>3] |=
355 *ptr++ = size - sizeof(ber_len_t);
356 LDAP_LIST_INSERT_HEAD(
357 &sh->sh_free[j-1-order_start], so_right, so_link);
358 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_left, so_link);
361 LDAP_LIST_INSERT_HEAD(
362 &sh->sh_free[j-1-order_start], so_right, so_link);
363 LDAP_LIST_INSERT_HEAD(
364 &sh->sh_free[j-1-order_start], so_left, so_link);
368 Debug( LDAP_DEBUG_TRACE,
369 "slap_sl_malloc of %lu bytes failed, using ch_malloc\n",
371 return (void*)ch_malloc(size);
375 /* FIXME: missing return; guessing... */
380 slap_sl_calloc( ber_len_t n, ber_len_t size, void *ctx )
384 newptr = slap_sl_malloc( n*size, ctx );
386 memset( newptr, 0, n*size );
392 slap_sl_realloc(void *ptr, ber_len_t size, void *ctx)
394 struct slab_heap *sh = ctx;
395 int pad = 2*sizeof(int) -1;
396 ber_len_t *p = (ber_len_t *)ptr, *newptr;
399 return slap_sl_malloc(size, ctx);
401 #ifdef SLAP_NO_SL_MALLOC
402 newptr = ber_memrealloc_x( ptr, size, NULL );
403 if ( newptr ) return newptr;
405 exit( EXIT_FAILURE );
408 /* Not our memory? */
409 if (!sh || ptr < sh->sh_base || ptr >= sh->sh_end) {
410 /* duplicate of realloc behavior, oh well */
411 newptr = ber_memrealloc_x(ptr, size, NULL);
415 Debug(LDAP_DEBUG_ANY, "ch_realloc of %lu bytes failed\n",
418 exit( EXIT_FAILURE );
422 slap_sl_free(ptr, ctx);
427 /* round up to doubleword boundary */
428 size += pad + sizeof( ber_len_t );
433 /* Never shrink blocks */
437 /* If reallocing the last block, we can grow it */
438 } else if ((char *)ptr + p[0] == sh->sh_last &&
439 (char *)ptr + size < (char *)sh->sh_end ) {
441 sh->sh_last = (char *)ptr + size;
443 p[size/sizeof(ber_len_t)] = size;
445 /* Nowhere to grow, need to alloc and copy */
447 newptr = slap_sl_malloc(size-sizeof(ber_len_t), ctx);
448 AC_MEMCPY(newptr, ptr, p[0]-sizeof(ber_len_t));
449 /* mark old region as free */
450 p[p[0]/sizeof(ber_len_t)] |= 1;
456 newptr2 = slap_sl_malloc(size, ctx);
458 AC_MEMCPY(newptr2, ptr, size);
460 AC_MEMCPY(newptr2, ptr, p[-1]);
462 slap_sl_free(ptr, ctx);
468 slap_sl_free(void *ptr, void *ctx)
470 struct slab_heap *sh = ctx;
472 ber_len_t *p = (ber_len_t *)ptr, *tmpp;
477 #ifdef SLAP_NO_SL_MALLOC
478 ber_memfree_x( ptr, NULL );
482 if (!sh || ptr < sh->sh_base || ptr >= sh->sh_end) {
483 ber_memfree_x(ptr, NULL);
484 } else if (sh->sh_stack) {
485 tmpp = (ber_len_t *)((char *)ptr + p[-1]);
488 /* reclaim free space off tail */
489 while ( tmpp == sh->sh_last ) {
490 if ( tmpp[-1] & 1 ) {
492 ptr = (char *)tmpp - size;
493 p = (ber_len_t *)ptr;
502 int size_shift, order_size;
503 int pad = 2*sizeof(int)-1, pad_shift;
504 int order_start = -1, order = -1;
505 struct slab_object *so;
510 size_shift = size + sizeof(ber_len_t) - 1;
513 } while (size_shift >>= 1);
518 } while (pad_shift >>= 1);
520 for (i = order, tmpp = p; i <= sh->sh_maxorder; i++) {
521 order_size = 1 << (i+1);
522 diff = (unsigned long)((char*)tmpp - (char*)sh->sh_base) >> (i+1);
523 sh->sh_map[i-order_start][diff>>3] &= (~(1 << (diff & 0x7)));
524 if (diff == ((diff>>1)<<1)) {
525 if (!(sh->sh_map[i-order_start][(diff+1)>>3] &
526 (1<<((diff+1)&0x7)))) {
527 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
529 if ((char*)so->so_ptr == (char*)tmpp) {
530 LDAP_LIST_REMOVE( so, so_link );
531 } else if ((char*)so->so_ptr ==
532 (char*)tmpp + order_size) {
533 LDAP_LIST_REMOVE(so, so_link);
536 so = LDAP_LIST_NEXT(so, so_link);
539 if (i < sh->sh_maxorder) {
542 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start+1],
547 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
548 slap_replenish_sopool(sh);
550 so = LDAP_LIST_FIRST(&sh->sh_sopool);
551 LDAP_LIST_REMOVE(so, so_link);
553 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
557 Debug(LDAP_DEBUG_TRACE, "slap_sl_free: "
558 "free object not found while bit is clear.\n",
565 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
566 slap_replenish_sopool(sh);
568 so = LDAP_LIST_FIRST(&sh->sh_sopool);
569 LDAP_LIST_REMOVE(so, so_link);
571 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
577 if (!(sh->sh_map[i-order_start][(diff-1)>>3] &
578 (1<<((diff-1)&0x7)))) {
579 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
581 if ((char*)so->so_ptr == (char*)tmpp) {
582 LDAP_LIST_REMOVE(so, so_link);
583 } else if ((char*)tmpp == (char *)so->so_ptr + order_size) {
584 LDAP_LIST_REMOVE(so, so_link);
588 so = LDAP_LIST_NEXT(so, so_link);
591 if (i < sh->sh_maxorder) {
593 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start+1], so, so_link);
597 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
598 slap_replenish_sopool(sh);
600 so = LDAP_LIST_FIRST(&sh->sh_sopool);
601 LDAP_LIST_REMOVE(so, so_link);
603 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
607 Debug(LDAP_DEBUG_TRACE, "slap_sl_free: "
608 "free object not found while bit is clear.\n",
615 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
616 slap_replenish_sopool(sh);
618 so = LDAP_LIST_FIRST(&sh->sh_sopool);
619 LDAP_LIST_REMOVE(so, so_link);
621 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
632 slap_sl_context( void *ptr )
634 struct slab_heap *sh;
637 if ( slapMode & SLAP_TOOL_MODE ) return NULL;
642 ctx = ldap_pvt_thread_pool_context();
645 ldap_pvt_thread_pool_getkey(
646 ctx, (void *)slap_sl_mem_init, &sh_tmp, NULL);
650 if (sh && ptr >= sh->sh_base && ptr <= sh->sh_end) {
656 static struct slab_object *
657 slap_replenish_sopool(
661 struct slab_object *so_block;
664 so_block = (struct slab_object *)ch_malloc(
665 SLAP_SLAB_SOBLOCK * sizeof(struct slab_object));
667 if ( so_block == NULL ) {
671 so_block[0].so_blockhead = 1;
672 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, &so_block[0], so_link);
673 for (i = 1; i < SLAP_SLAB_SOBLOCK; i++) {
674 so_block[i].so_blockhead = 0;
675 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, &so_block[i], so_link );
683 print_slheap(int level, void *ctx)
685 struct slab_heap *sh = ctx;
686 int order_start = -1;
687 int pad = 2*sizeof(int)-1, pad_shift;
688 struct slab_object *so;
692 Debug(level, "NULL memctx\n", 0, 0, 0);
699 } while (pad_shift >>= 1);
701 Debug(level, "sh->sh_maxorder=%d\n", sh->sh_maxorder, 0, 0);
703 for (i = order_start; i <= sh->sh_maxorder; i++) {
705 Debug(level, "order=%d\n", i, 0, 0);
706 for (j = 0; j < (1<<(sh->sh_maxorder-i))/8; j++) {
707 Debug(level, "%02x ", sh->sh_map[i-order_start][j], 0, 0);
711 Debug(level, "%02x ", sh->sh_map[i-order_start][0], 0, 0);
713 Debug(level, "\n", 0, 0, 0);
714 Debug(level, "free list:\n", 0, 0, 0);
715 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
717 Debug(level, "%lx\n", (unsigned long) so->so_ptr, 0, 0);
718 so = LDAP_LIST_NEXT(so, so_link);