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-2004 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 void print_slheap(int level, void *ctx);
32 struct slab_heap *sh = data;
33 int pad = 2*sizeof(int)-1, pad_shift;
34 int order_start = -1, i;
35 struct slab_object *so;
38 ber_memfree_x(sh->sh_base, NULL);
39 ber_memfree_x(sh, NULL);
44 } while (pad_shift >>= 1);
46 for (i = 0; i <= sh->sh_maxorder - order_start; i++) {
47 so = LDAP_LIST_FIRST(&sh->sh_free[i]);
49 struct slab_object *so_tmp = so;
50 so = LDAP_LIST_NEXT(so, so_link);
51 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_tmp, so_link);
53 ch_free(sh->sh_map[i]);
58 so = LDAP_LIST_FIRST(&sh->sh_sopool);
60 struct slab_object *so_tmp = so;
61 so = LDAP_LIST_NEXT(so, so_link);
62 if (!so_tmp->so_blockhead) {
63 LDAP_LIST_REMOVE(so_tmp, so_link);
66 so = LDAP_LIST_FIRST(&sh->sh_sopool);
68 struct slab_object *so_tmp = so;
69 so = LDAP_LIST_NEXT(so, so_link);
72 ber_memfree_x(sh->sh_base, NULL);
73 ber_memfree_x(sh, NULL);
77 BerMemoryFunctions slap_sl_mfuncs =
78 { slap_sl_malloc, slap_sl_calloc, slap_sl_realloc, slap_sl_free };
83 ber_set_option( NULL, LBER_OPT_MEMORY_FNS, &slap_sl_mfuncs );
87 static struct slab_heap *slheap;
97 struct slab_heap *sh = NULL;
99 int pad = 2*sizeof(int)-1, pad_shift;
100 int order = -1, order_start = -1, order_end = -1;
102 struct slab_object *so, *so_block;
107 ldap_pvt_thread_pool_getkey(
108 ctx, (void *)slap_sl_mem_init, (void **)&sh, NULL );
111 /* round up to doubleword boundary */
117 sh = ch_malloc(sizeof(struct slab_heap));
118 sh->sh_base = ch_malloc(size);
122 ldap_pvt_thread_pool_setkey(ctx, (void *)slap_sl_mem_init,
123 (void *)sh, slap_sl_mem_destroy);
125 } else if ( size > (char *)sh->sh_end - (char *)sh->sh_base ) {
126 sh->sh_base = ch_realloc(sh->sh_base, size);
128 sh->sh_last = sh->sh_base;
129 sh->sh_end = (char *) sh->sh_base + size;
130 sh->sh_stack = stack;
133 size_shift = size - 1;
136 } while (size_shift >>= 1);
141 } while (pad_shift >>= 1);
143 order = order_end - order_start + 1;
146 sh = (struct slab_heap *) ch_malloc(sizeof(struct slab_heap));
147 sh->sh_base = ch_malloc(size);
151 ldap_pvt_thread_pool_setkey(ctx, (void *)slap_sl_mem_init,
152 (void *)sh, slap_sl_mem_destroy);
155 for (i = 0; i <= sh->sh_maxorder - order_start; i++) {
156 so = LDAP_LIST_FIRST(&sh->sh_free[i]);
158 struct slab_object *so_tmp = so;
159 so = LDAP_LIST_NEXT(so, so_link);
160 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_tmp, so_link);
162 ch_free(sh->sh_map[i]);
164 ch_free(sh->sh_free);
167 so = LDAP_LIST_FIRST(&sh->sh_sopool);
169 struct slab_object *so_tmp = so;
170 so = LDAP_LIST_NEXT(so, so_link);
171 if (!so_tmp->so_blockhead) {
172 LDAP_LIST_REMOVE(so_tmp, so_link);
175 so = LDAP_LIST_FIRST(&sh->sh_sopool);
177 struct slab_object *so_tmp = so;
178 so = LDAP_LIST_NEXT(so, so_link);
182 if (size > (char *)sh->sh_end - (char *)sh->sh_base) {
183 sh->sh_base = realloc(sh->sh_base, size);
186 sh->sh_end = (char *)sh->sh_base + size;
187 sh->sh_maxorder = order_end;
189 sh->sh_free = (struct sh_freelist *)
190 ch_malloc(order * sizeof(struct sh_freelist));
191 for (i = 0; i < order; i++) {
192 LDAP_LIST_INIT(&sh->sh_free[i]);
195 LDAP_LIST_INIT(&sh->sh_sopool);
197 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
198 so_block = (struct slab_object *)ch_malloc(
199 SLAP_SLAB_SOBLOCK * sizeof( struct slab_object));
200 so_block[0].so_blockhead = 1;
201 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, &so_block[0], so_link);
202 for (k = 1; k < SLAP_SLAB_SOBLOCK; k++) {
203 so_block[k].so_blockhead = 0;
204 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, &so_block[k], so_link);
206 so = LDAP_LIST_FIRST(&sh->sh_sopool);
207 LDAP_LIST_REMOVE(so, so_link);
208 so->so_ptr = sh->sh_base;
210 so = LDAP_LIST_FIRST(&sh->sh_sopool);
211 LDAP_LIST_REMOVE(so, so_link);
212 so->so_ptr = sh->sh_base;
215 LDAP_LIST_INSERT_HEAD(&sh->sh_free[order-1], so, so_link);
217 sh->sh_map = (unsigned char **)
218 ch_malloc(order * sizeof(unsigned long *));
219 for (i = 0; i < order; i++) {
220 sh->sh_map[i] = (unsigned char *)
221 ch_malloc(size >> (1 << (order_start + i + 3)));
222 memset(sh->sh_map[i], 0, size >> (1 << (order_start + i + 3)));
224 sh->sh_stack = stack;
238 /* separate from context */
239 ldap_pvt_thread_pool_setkey( ctx, (void *)slap_sl_mem_init, NULL, NULL );
249 struct slab_heap *sh = ctx;
251 int pad = 2*sizeof(int)-1, pad_shift;
252 int order = -1, order_start = -1;
253 struct slab_object *so_new, *so_left, *so_right, *so_block;
254 ber_len_t *ptr, *new;
258 /* ber_set_option calls us like this */
259 if (!ctx) return ber_memalloc_x(size, NULL);
261 Debug(LDAP_DEBUG_ANY, "slap_sl_malloc (%d)\n", size, 0, 0);
263 /* round up to doubleword boundary */
264 size += pad + sizeof(ber_len_t);
268 if ((char *)sh->sh_last + size >= (char *)sh->sh_end) {
269 Debug(LDAP_DEBUG_TRACE,
270 "slap_sl_malloc of %lu bytes failed, using ch_malloc\n",
272 return ch_malloc(size);
275 *new++ = size - sizeof(ber_len_t);
276 sh->sh_last = (char *) sh->sh_last + size;
277 return( (void *)new );
279 size_shift = size - 1;
282 } while (size_shift >>= 1);
287 } while (pad_shift >>= 1);
289 for (i = order; i <= sh->sh_maxorder &&
290 LDAP_LIST_EMPTY(&sh->sh_free[i-order_start]); i++);
293 so_new = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
294 LDAP_LIST_REMOVE(so_new, so_link);
295 ptr = so_new->so_ptr;
296 diff = (unsigned long)((char*)ptr -
297 (char*)sh->sh_base) >> (order + 1);
298 sh->sh_map[order-order_start][diff>>3] |= (1 << (diff & 0x7));
299 *ptr++ = size - sizeof(ber_len_t);
300 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_new, so_link);
302 } else if (i <= sh->sh_maxorder) {
303 for (j = i; j > order; j--) {
304 so_left = LDAP_LIST_FIRST(&sh->sh_free[j-order_start]);
305 LDAP_LIST_REMOVE(so_left, so_link);
306 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
307 so_block = (struct slab_object *)ch_malloc(
308 SLAP_SLAB_SOBLOCK * sizeof(struct slab_object));
309 so_block[0].so_blockhead = 1;
310 LDAP_LIST_INSERT_HEAD(
311 &sh->sh_sopool, &so_block[0], so_link);
312 for (k = 1; k < SLAP_SLAB_SOBLOCK; k++) {
313 so_block[k].so_blockhead = 0;
314 LDAP_LIST_INSERT_HEAD(
315 &sh->sh_sopool, &so_block[k], so_link);
317 so_right = LDAP_LIST_FIRST(&sh->sh_sopool);
318 LDAP_LIST_REMOVE(so_right, so_link);
319 so_right->so_ptr = so_left->so_ptr + (1 << j);
321 so_right = LDAP_LIST_FIRST(&sh->sh_sopool);
322 LDAP_LIST_REMOVE(so_right, so_link);
323 so_right->so_ptr = so_left->so_ptr + (1 << j);
325 if (j == order + 1) {
326 ptr = so_left->so_ptr;
327 diff = (unsigned long)((char*)ptr -
328 (char*)sh->sh_base) >> (order+1);
329 sh->sh_map[order-order_start][diff>>3] |=
331 *ptr++ = size - sizeof(ber_len_t);
332 LDAP_LIST_INSERT_HEAD(
333 &sh->sh_free[j-1-order_start], so_right, so_link);
334 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_left, so_link);
337 LDAP_LIST_INSERT_HEAD(
338 &sh->sh_free[j-1-order_start], so_right, so_link);
339 LDAP_LIST_INSERT_HEAD(
340 &sh->sh_free[j-1-order_start], so_left, so_link);
344 Debug( LDAP_DEBUG_TRACE,
345 "slap_sl_malloc of %lu bytes failed, using ch_malloc\n",
347 return (void*)ch_malloc(size);
353 slap_sl_calloc( ber_len_t n, ber_len_t size, void *ctx )
357 new = slap_sl_malloc( n*size, ctx );
359 memset( new, 0, n*size );
365 slap_sl_realloc(void *ptr, ber_len_t size, void *ctx)
367 struct slab_heap *sh = ctx;
369 int pad = 2*sizeof(int)-1, pad_shift;
370 int order_start = -1, order = -1;
371 struct slab_object *so;
372 ber_len_t *p = (ber_len_t *)ptr, *new;
376 return slap_sl_malloc(size, ctx);
378 /* Not our memory? */
379 if (!sh || ptr < sh->sh_base || ptr >= sh->sh_end) {
380 /* duplicate of realloc behavior, oh well */
381 new = ber_memrealloc_x(ptr, size, NULL);
385 Debug(LDAP_DEBUG_ANY, "ch_realloc of %lu bytes failed\n",
388 exit( EXIT_FAILURE );
392 slap_sl_free(ptr, ctx);
397 /* Never shrink blocks */
401 /* If reallocing the last block, we can grow it */
402 } else if ((char *)ptr + p[-1] == sh->sh_last) {
404 sh->sh_last = (char *)sh->sh_last + size - p[-1];
407 /* Nowhere to grow, need to alloc and copy */
409 new = slap_sl_malloc(size, ctx);
410 AC_MEMCPY(new, ptr, p[-1]);
415 newptr = slap_sl_malloc(size, ctx);
417 AC_MEMCPY(newptr, ptr, size);
419 AC_MEMCPY(newptr, ptr, p[-1]);
421 slap_sl_free(ptr, ctx);
427 slap_sl_free(void *ptr, void *ctx)
429 struct slab_heap *sh = ctx;
430 int size, size_shift, order_size;
431 int pad = 2*sizeof(int)-1, pad_shift;
432 ber_len_t *p = (ber_len_t *)ptr, *tmpp;
433 int order_start = -1, order = -1;
434 struct slab_object *so, *so_block;
436 int i, k, inserted = 0;
438 Debug( LDAP_DEBUG_ANY, "slap_sl_free \n", 0, 0, 0);
440 if (!sh || ptr < sh->sh_base || ptr >= sh->sh_end) {
441 ber_memfree_x(ptr, NULL);
442 } else if (sh->sh_stack && (char *)ptr + p[-1] == sh->sh_last) {
445 } else if (!sh->sh_stack) {
447 size_shift = size + sizeof(ber_len_t) - 1;
450 } while (size_shift >>= 1);
455 } while (pad_shift >>= 1);
457 for (i = order, tmpp = p; i <= sh->sh_maxorder; i++) {
458 order_size = 1 << (i+1);
459 diff = (unsigned long)((char*)tmpp - (char*)sh->sh_base) >> (i+1);
460 sh->sh_map[i-order_start][diff>>3] &= (~(1 << (diff & 0x7)));
461 if (diff == ((diff>>1)<<1)) {
462 if (!(sh->sh_map[i-order_start][(diff+1)>>3] &
463 (1<<((diff+1)&0x7)))) {
464 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
466 if ((char*)so->so_ptr == (char*)tmpp) {
467 LDAP_LIST_REMOVE( so, so_link );
468 } else if ((char*)so->so_ptr ==
469 (char*)tmpp + order_size) {
470 LDAP_LIST_REMOVE(so, so_link);
473 so = LDAP_LIST_NEXT(so, so_link);
476 if (i < sh->sh_maxorder) {
479 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start+1],
484 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
485 so_block = (struct slab_object *)ch_malloc(
487 sizeof( struct slab_object));
488 so_block[0].so_blockhead = 1;
489 LDAP_LIST_INSERT_HEAD( &sh->sh_sopool,
490 &so_block[0], so_link );
491 for ( k = 1; k < SLAP_SLAB_SOBLOCK; k++ ) {
492 so_block[k].so_blockhead = 0;
493 LDAP_LIST_INSERT_HEAD( &sh->sh_sopool,
494 &so_block[k], so_link );
496 so = LDAP_LIST_FIRST(&sh->sh_sopool);
497 LDAP_LIST_REMOVE(so, so_link);
500 so = LDAP_LIST_FIRST(&sh->sh_sopool);
501 LDAP_LIST_REMOVE(so, so_link);
504 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
508 Debug(LDAP_DEBUG_ANY, "slap_sl_free: "
509 "free object not found while bit is clear.\n",
516 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
517 so_block = (struct slab_object *)ch_malloc(
519 sizeof(struct slab_object));
520 so_block[0].so_blockhead = 1;
521 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool,
522 &so_block[0], so_link);
523 for (k = 1; k < SLAP_SLAB_SOBLOCK; k++) {
524 so_block[k].so_blockhead = 0;
525 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool,
526 &so_block[k], so_link);
528 so = LDAP_LIST_FIRST(&sh->sh_sopool);
529 LDAP_LIST_REMOVE(so, so_link);
532 so = LDAP_LIST_FIRST(&sh->sh_sopool);
533 LDAP_LIST_REMOVE(so, so_link);
536 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
542 if (!(sh->sh_map[i-order_start][(diff-1)>>3] &
543 (1<<((diff-1)&0x7)))) {
544 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
546 if ((char*)so->so_ptr == (char*)tmpp) {
547 LDAP_LIST_REMOVE(so, so_link);
548 } else if ((char*)tmpp == so->so_ptr + order_size) {
549 LDAP_LIST_REMOVE(so, so_link);
553 so = LDAP_LIST_NEXT(so, so_link);
556 if (i < sh->sh_maxorder) {
558 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start+1], so, so_link);
562 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
563 so_block = (struct slab_object *)ch_malloc(
565 sizeof(struct slab_object));
566 so_block[0].so_blockhead = 1;
567 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool,
568 &so_block[0], so_link);
569 for (k = 1; k < SLAP_SLAB_SOBLOCK; k++) {
570 so_block[k].so_blockhead = 0;
571 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool,
572 &so_block[k], so_link );
574 so = LDAP_LIST_FIRST(&sh->sh_sopool);
575 LDAP_LIST_REMOVE(so, so_link);
578 so = LDAP_LIST_FIRST(&sh->sh_sopool);
579 LDAP_LIST_REMOVE(so, so_link);
582 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
586 Debug(LDAP_DEBUG_ANY, "slap_sl_free: "
587 "free object not found while bit is clear.\n",
594 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
595 so_block = (struct slab_object *)ch_malloc(
597 sizeof(struct slab_object));
598 so_block[0].so_blockhead = 1;
599 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool,
600 &so_block[0], so_link );
601 for (k = 1; k < SLAP_SLAB_SOBLOCK; k++) {
602 so_block[k].so_blockhead = 0;
603 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool,
604 &so_block[k], so_link );
606 so = LDAP_LIST_FIRST(&sh->sh_sopool);
607 LDAP_LIST_REMOVE(so, so_link);
610 so = LDAP_LIST_FIRST(&sh->sh_sopool);
611 LDAP_LIST_REMOVE(so, so_link);
614 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
625 slap_sl_context( void *ptr )
627 struct slab_heap *sh = NULL;
633 ctx = ldap_pvt_thread_pool_context();
635 ldap_pvt_thread_pool_getkey(ctx, (void *)slap_sl_mem_init,
639 if (sh && ptr >= sh->sh_base && ptr <= sh->sh_end) {
646 print_slheap(int level, void *ctx)
648 struct slab_heap *sh = ctx;
649 int order_start = -1;
650 int pad = 2*sizeof(int)-1, pad_shift;
651 struct slab_object *so;
655 Debug(level, "NULL memctx\n", 0, 0, 0);
662 } while (pad_shift >>= 1);
664 Debug(level, "sh->sh_maxorder=%d\n", sh->sh_maxorder, 0, 0);
666 for (i = order_start; i <= sh->sh_maxorder; i++) {
668 Debug(level, "order=%d\n", i, 0, 0);
669 for (j = 0; j < (1<<(sh->sh_maxorder-i))/8; j++) {
670 Debug(level, "%02x ", sh->sh_map[i-order_start][j], 0, 0);
674 Debug(level, "%02x ", sh->sh_map[i-order_start][0], 0, 0);
676 Debug(level, "\n", 0, 0, 0);
677 Debug(level, "free list:\n", 0, 0, 0);
678 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
680 Debug(level, "%x\n",so->so_ptr, 0, 0);
681 so = LDAP_LIST_NEXT(so, so_link);