sl_malloc.c revision 1.1.1.1.2.2
1 /* sl_malloc.c - malloc routines using a per-thread slab */ 2 /* $OpenLDAP: pkg/ldap/servers/slapd/sl_malloc.c,v 1.39.2.6 2008/02/11 23:34:15 quanah Exp $ */ 3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>. 4 * 5 * Copyright 2003-2008 The OpenLDAP Foundation. 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted only as authorized by the OpenLDAP 10 * Public License. 11 * 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>. 15 */ 16 17 #include "portable.h" 18 19 #include <stdio.h> 20 #include <ac/string.h> 21 22 #include "slap.h" 23 24 static struct slab_object * slap_replenish_sopool(struct slab_heap* sh); 25 #ifdef SLAPD_UNUSED 26 static void print_slheap(int level, void *ctx); 27 #endif 28 29 void 30 slap_sl_mem_destroy( 31 void *key, 32 void *data 33 ) 34 { 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; 39 40 if (sh->sh_stack) { 41 ber_memfree_x(sh->sh_base, NULL); 42 ber_memfree_x(sh, NULL); 43 } else { 44 pad_shift = pad - 1; 45 do { 46 order_start++; 47 } while (pad_shift >>= 1); 48 49 for (i = 0; i <= sh->sh_maxorder - order_start; i++) { 50 so = LDAP_LIST_FIRST(&sh->sh_free[i]); 51 while (so) { 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); 55 } 56 ch_free(sh->sh_map[i]); 57 } 58 ch_free(sh->sh_free); 59 ch_free(sh->sh_map); 60 61 so = LDAP_LIST_FIRST(&sh->sh_sopool); 62 while (so) { 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); 67 } 68 } 69 so = LDAP_LIST_FIRST(&sh->sh_sopool); 70 while (so) { 71 struct slab_object *so_tmp = so; 72 so = LDAP_LIST_NEXT(so, so_link); 73 ch_free(so_tmp); 74 } 75 ber_memfree_x(sh->sh_base, NULL); 76 ber_memfree_x(sh, NULL); 77 } 78 } 79 80 BerMemoryFunctions slap_sl_mfuncs = 81 { slap_sl_malloc, slap_sl_calloc, slap_sl_realloc, slap_sl_free }; 82 83 void 84 slap_sl_mem_init() 85 { 86 ber_set_option( NULL, LBER_OPT_MEMORY_FNS, &slap_sl_mfuncs ); 87 } 88 89 #ifdef NO_THREADS 90 static struct slab_heap *slheap; 91 #endif 92 93 void * 94 slap_sl_mem_create( 95 ber_len_t size, 96 int stack, 97 void *ctx, 98 int new 99 ) 100 { 101 struct slab_heap *sh; 102 ber_len_t size_shift; 103 int pad = 2*sizeof(int)-1, pad_shift; 104 int order = -1, order_start = -1, order_end = -1; 105 int i; 106 struct slab_object *so; 107 108 #ifdef NO_THREADS 109 sh = slheap; 110 #else 111 void *sh_tmp = NULL; 112 ldap_pvt_thread_pool_getkey( 113 ctx, (void *)slap_sl_mem_init, &sh_tmp, NULL ); 114 sh = sh_tmp; 115 #endif 116 117 if ( !new ) 118 return sh; 119 120 /* round up to doubleword boundary */ 121 size += pad; 122 size &= ~pad; 123 124 if (stack) { 125 if (!sh) { 126 sh = ch_malloc(sizeof(struct slab_heap)); 127 sh->sh_base = ch_malloc(size); 128 #ifdef NO_THREADS 129 slheap = sh; 130 #else 131 ldap_pvt_thread_pool_setkey(ctx, (void *)slap_sl_mem_init, 132 (void *)sh, slap_sl_mem_destroy, NULL, NULL); 133 #endif 134 } else if ( size > (char *)sh->sh_end - (char *)sh->sh_base ) { 135 void *newptr; 136 137 newptr = ch_realloc( sh->sh_base, size ); 138 if ( newptr == NULL ) return NULL; 139 sh->sh_base = newptr; 140 } 141 sh->sh_last = sh->sh_base; 142 sh->sh_end = (char *) sh->sh_base + size; 143 sh->sh_stack = stack; 144 return sh; 145 } else { 146 size_shift = size - 1; 147 do { 148 order_end++; 149 } while (size_shift >>= 1); 150 151 pad_shift = pad - 1; 152 do { 153 order_start++; 154 } while (pad_shift >>= 1); 155 156 order = order_end - order_start + 1; 157 158 if (!sh) { 159 sh = (struct slab_heap *) ch_malloc(sizeof(struct slab_heap)); 160 sh->sh_base = ch_malloc(size); 161 #ifdef NO_THREADS 162 slheap = sh; 163 #else 164 ldap_pvt_thread_pool_setkey(ctx, (void *)slap_sl_mem_init, 165 (void *)sh, slap_sl_mem_destroy, NULL, NULL); 166 #endif 167 } else { 168 for (i = 0; i <= sh->sh_maxorder - order_start; i++) { 169 so = LDAP_LIST_FIRST(&sh->sh_free[i]); 170 while (so) { 171 struct slab_object *so_tmp = so; 172 so = LDAP_LIST_NEXT(so, so_link); 173 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_tmp, so_link); 174 } 175 ch_free(sh->sh_map[i]); 176 } 177 ch_free(sh->sh_free); 178 ch_free(sh->sh_map); 179 180 so = LDAP_LIST_FIRST(&sh->sh_sopool); 181 while (so) { 182 struct slab_object *so_tmp = so; 183 so = LDAP_LIST_NEXT(so, so_link); 184 if (!so_tmp->so_blockhead) { 185 LDAP_LIST_REMOVE(so_tmp, so_link); 186 } 187 } 188 so = LDAP_LIST_FIRST(&sh->sh_sopool); 189 while (so) { 190 struct slab_object *so_tmp = so; 191 so = LDAP_LIST_NEXT(so, so_link); 192 ch_free(so_tmp); 193 } 194 195 if (size > (char *)sh->sh_end - (char *)sh->sh_base) { 196 void *newptr; 197 198 newptr = realloc( sh->sh_base, size ); 199 if ( newptr == NULL ) return NULL; 200 sh->sh_base = newptr; 201 } 202 } 203 sh->sh_end = (char *)sh->sh_base + size; 204 sh->sh_maxorder = order_end; 205 206 sh->sh_free = (struct sh_freelist *) 207 ch_malloc(order * sizeof(struct sh_freelist)); 208 for (i = 0; i < order; i++) { 209 LDAP_LIST_INIT(&sh->sh_free[i]); 210 } 211 212 LDAP_LIST_INIT(&sh->sh_sopool); 213 214 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) { 215 slap_replenish_sopool(sh); 216 } 217 so = LDAP_LIST_FIRST(&sh->sh_sopool); 218 LDAP_LIST_REMOVE(so, so_link); 219 so->so_ptr = sh->sh_base; 220 221 LDAP_LIST_INSERT_HEAD(&sh->sh_free[order-1], so, so_link); 222 223 sh->sh_map = (unsigned char **) 224 ch_malloc(order * sizeof(unsigned char *)); 225 for (i = 0; i < order; i++) { 226 int shiftamt = order_start + 1 + i; 227 int nummaps = size >> shiftamt; 228 assert(nummaps); 229 nummaps >>= 3; 230 if (!nummaps) nummaps = 1; 231 sh->sh_map[i] = (unsigned char *) ch_malloc(nummaps); 232 memset(sh->sh_map[i], 0, nummaps); 233 } 234 sh->sh_stack = stack; 235 return sh; 236 } 237 } 238 239 void 240 slap_sl_mem_detach( 241 void *ctx, 242 void *memctx 243 ) 244 { 245 #ifdef NO_THREADS 246 slheap = NULL; 247 #else 248 /* separate from context */ 249 ldap_pvt_thread_pool_setkey( ctx, (void *)slap_sl_mem_init, 250 NULL, 0, NULL, NULL ); 251 #endif 252 } 253 254 void * 255 slap_sl_malloc( 256 ber_len_t size, 257 void *ctx 258 ) 259 { 260 struct slab_heap *sh = ctx; 261 ber_len_t size_shift; 262 int pad = 2*sizeof(int)-1, pad_shift; 263 int order = -1, order_start = -1; 264 struct slab_object *so_new, *so_left, *so_right; 265 ber_len_t *ptr, *newptr; 266 unsigned long diff; 267 int i, j; 268 269 #ifdef SLAP_NO_SL_MALLOC 270 return ber_memalloc_x( size, NULL ); 271 #endif 272 273 /* ber_set_option calls us like this */ 274 if (!ctx) return ber_memalloc_x(size, NULL); 275 276 /* round up to doubleword boundary */ 277 size += sizeof(ber_len_t) + pad; 278 size &= ~pad; 279 280 if (sh->sh_stack) { 281 if ((char *)sh->sh_last + size >= (char *)sh->sh_end) { 282 Debug(LDAP_DEBUG_TRACE, 283 "slap_sl_malloc of %lu bytes failed, using ch_malloc\n", 284 (long)size, 0, 0); 285 return ch_malloc(size); 286 } 287 newptr = sh->sh_last; 288 *newptr++ = size - sizeof(ber_len_t); 289 sh->sh_last = (char *) sh->sh_last + size; 290 return( (void *)newptr ); 291 } else { 292 size_shift = size - 1; 293 do { 294 order++; 295 } while (size_shift >>= 1); 296 297 pad_shift = pad - 1; 298 do { 299 order_start++; 300 } while (pad_shift >>= 1); 301 302 for (i = order; i <= sh->sh_maxorder && 303 LDAP_LIST_EMPTY(&sh->sh_free[i-order_start]); i++); 304 305 if (i == order) { 306 so_new = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]); 307 LDAP_LIST_REMOVE(so_new, so_link); 308 ptr = so_new->so_ptr; 309 diff = (unsigned long)((char*)ptr - 310 (char*)sh->sh_base) >> (order + 1); 311 sh->sh_map[order-order_start][diff>>3] |= (1 << (diff & 0x7)); 312 *ptr++ = size - sizeof(ber_len_t); 313 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_new, so_link); 314 return((void*)ptr); 315 } else if (i <= sh->sh_maxorder) { 316 for (j = i; j > order; j--) { 317 so_left = LDAP_LIST_FIRST(&sh->sh_free[j-order_start]); 318 LDAP_LIST_REMOVE(so_left, so_link); 319 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) { 320 slap_replenish_sopool(sh); 321 } 322 so_right = LDAP_LIST_FIRST(&sh->sh_sopool); 323 LDAP_LIST_REMOVE(so_right, so_link); 324 so_right->so_ptr = (void *)((char *)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] |= 330 (1 << (diff & 0x7)); 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); 335 return((void*)ptr); 336 } else { 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); 341 } 342 } 343 } else { 344 Debug( LDAP_DEBUG_TRACE, 345 "slap_sl_malloc of %lu bytes failed, using ch_malloc\n", 346 (long)size, 0, 0); 347 return (void*)ch_malloc(size); 348 } 349 } 350 351 /* FIXME: missing return; guessing... */ 352 return NULL; 353 } 354 355 void * 356 slap_sl_calloc( ber_len_t n, ber_len_t size, void *ctx ) 357 { 358 void *newptr; 359 360 newptr = slap_sl_malloc( n*size, ctx ); 361 if ( newptr ) { 362 memset( newptr, 0, n*size ); 363 } 364 return newptr; 365 } 366 367 void * 368 slap_sl_realloc(void *ptr, ber_len_t size, void *ctx) 369 { 370 struct slab_heap *sh = ctx; 371 int pad = 2*sizeof(int) -1; 372 ber_len_t *p = (ber_len_t *)ptr, *newptr; 373 374 if (ptr == NULL) 375 return slap_sl_malloc(size, ctx); 376 377 #ifdef SLAP_NO_SL_MALLOC 378 return ber_memrealloc_x( ptr, size, NULL ); 379 #endif 380 381 /* Not our memory? */ 382 if (!sh || ptr < sh->sh_base || ptr >= sh->sh_end) { 383 /* duplicate of realloc behavior, oh well */ 384 newptr = ber_memrealloc_x(ptr, size, NULL); 385 if (newptr) { 386 return newptr; 387 } 388 Debug(LDAP_DEBUG_ANY, "ch_realloc of %lu bytes failed\n", 389 (long) size, 0, 0); 390 assert(0); 391 exit( EXIT_FAILURE ); 392 } 393 394 if (size == 0) { 395 slap_sl_free(ptr, ctx); 396 return NULL; 397 } 398 399 if (sh->sh_stack) { 400 /* round up to doubleword boundary */ 401 size += pad + sizeof( ber_len_t ); 402 size &= ~pad; 403 404 /* Never shrink blocks */ 405 if (size <= p[-1]) { 406 newptr = p; 407 408 /* If reallocing the last block, we can grow it */ 409 } else if ((char *)ptr + p[-1] == sh->sh_last && 410 (char *)ptr + size < (char *)sh->sh_end ) { 411 newptr = p; 412 sh->sh_last = (char *)sh->sh_last + size - p[-1]; 413 p[-1] = size; 414 415 /* Nowhere to grow, need to alloc and copy */ 416 } else { 417 newptr = slap_sl_malloc(size, ctx); 418 AC_MEMCPY(newptr, ptr, p[-1]); 419 } 420 return newptr; 421 } else { 422 void *newptr2; 423 424 newptr2 = slap_sl_malloc(size, ctx); 425 if (size < p[-1]) { 426 AC_MEMCPY(newptr2, ptr, size); 427 } else { 428 AC_MEMCPY(newptr2, ptr, p[-1]); 429 } 430 slap_sl_free(ptr, ctx); 431 return newptr2; 432 } 433 } 434 435 void 436 slap_sl_free(void *ptr, void *ctx) 437 { 438 struct slab_heap *sh = ctx; 439 int size, size_shift, order_size; 440 int pad = 2*sizeof(int)-1, pad_shift; 441 ber_len_t *p = (ber_len_t *)ptr, *tmpp; 442 int order_start = -1, order = -1; 443 struct slab_object *so; 444 unsigned long diff; 445 int i, inserted = 0; 446 447 if (!ptr) 448 return; 449 450 #ifdef SLAP_NO_SL_MALLOC 451 ber_memfree_x( ptr, NULL ); 452 return; 453 #endif 454 455 if (!sh || ptr < sh->sh_base || ptr >= sh->sh_end) { 456 ber_memfree_x(ptr, NULL); 457 } else if (sh->sh_stack && (char *)ptr + p[-1] == sh->sh_last) { 458 p--; 459 sh->sh_last = p; 460 } else if (!sh->sh_stack) { 461 size = *(--p); 462 size_shift = size + sizeof(ber_len_t) - 1; 463 do { 464 order++; 465 } while (size_shift >>= 1); 466 467 pad_shift = pad - 1; 468 do { 469 order_start++; 470 } while (pad_shift >>= 1); 471 472 for (i = order, tmpp = p; i <= sh->sh_maxorder; i++) { 473 order_size = 1 << (i+1); 474 diff = (unsigned long)((char*)tmpp - (char*)sh->sh_base) >> (i+1); 475 sh->sh_map[i-order_start][diff>>3] &= (~(1 << (diff & 0x7))); 476 if (diff == ((diff>>1)<<1)) { 477 if (!(sh->sh_map[i-order_start][(diff+1)>>3] & 478 (1<<((diff+1)&0x7)))) { 479 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]); 480 while (so) { 481 if ((char*)so->so_ptr == (char*)tmpp) { 482 LDAP_LIST_REMOVE( so, so_link ); 483 } else if ((char*)so->so_ptr == 484 (char*)tmpp + order_size) { 485 LDAP_LIST_REMOVE(so, so_link); 486 break; 487 } 488 so = LDAP_LIST_NEXT(so, so_link); 489 } 490 if (so) { 491 if (i < sh->sh_maxorder) { 492 inserted = 1; 493 so->so_ptr = tmpp; 494 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start+1], 495 so, so_link); 496 } 497 continue; 498 } else { 499 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) { 500 slap_replenish_sopool(sh); 501 } 502 so = LDAP_LIST_FIRST(&sh->sh_sopool); 503 LDAP_LIST_REMOVE(so, so_link); 504 so->so_ptr = tmpp; 505 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start], 506 so, so_link); 507 break; 508 509 Debug(LDAP_DEBUG_TRACE, "slap_sl_free: " 510 "free object not found while bit is clear.\n", 511 0, 0, 0); 512 assert(so != NULL); 513 514 } 515 } else { 516 if (!inserted) { 517 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) { 518 slap_replenish_sopool(sh); 519 } 520 so = LDAP_LIST_FIRST(&sh->sh_sopool); 521 LDAP_LIST_REMOVE(so, so_link); 522 so->so_ptr = tmpp; 523 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start], 524 so, so_link); 525 } 526 break; 527 } 528 } else { 529 if (!(sh->sh_map[i-order_start][(diff-1)>>3] & 530 (1<<((diff-1)&0x7)))) { 531 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]); 532 while (so) { 533 if ((char*)so->so_ptr == (char*)tmpp) { 534 LDAP_LIST_REMOVE(so, so_link); 535 } else if ((char*)tmpp == (char *)so->so_ptr + order_size) { 536 LDAP_LIST_REMOVE(so, so_link); 537 tmpp = so->so_ptr; 538 break; 539 } 540 so = LDAP_LIST_NEXT(so, so_link); 541 } 542 if (so) { 543 if (i < sh->sh_maxorder) { 544 inserted = 1; 545 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start+1], so, so_link); 546 continue; 547 } 548 } else { 549 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) { 550 slap_replenish_sopool(sh); 551 } 552 so = LDAP_LIST_FIRST(&sh->sh_sopool); 553 LDAP_LIST_REMOVE(so, so_link); 554 so->so_ptr = tmpp; 555 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start], 556 so, so_link); 557 break; 558 559 Debug(LDAP_DEBUG_TRACE, "slap_sl_free: " 560 "free object not found while bit is clear.\n", 561 0, 0, 0 ); 562 assert(so != NULL); 563 564 } 565 } else { 566 if ( !inserted ) { 567 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) { 568 slap_replenish_sopool(sh); 569 } 570 so = LDAP_LIST_FIRST(&sh->sh_sopool); 571 LDAP_LIST_REMOVE(so, so_link); 572 so->so_ptr = tmpp; 573 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start], 574 so, so_link); 575 } 576 break; 577 } 578 } 579 } 580 } 581 } 582 583 void * 584 slap_sl_context( void *ptr ) 585 { 586 struct slab_heap *sh; 587 void *ctx, *sh_tmp; 588 589 if ( slapMode & SLAP_TOOL_MODE ) return NULL; 590 591 #ifdef NO_THREADS 592 sh = slheap; 593 #else 594 ctx = ldap_pvt_thread_pool_context(); 595 596 sh_tmp = NULL; 597 ldap_pvt_thread_pool_getkey( 598 ctx, (void *)slap_sl_mem_init, &sh_tmp, NULL); 599 sh = sh_tmp; 600 #endif 601 602 if (sh && ptr >= sh->sh_base && ptr <= sh->sh_end) { 603 return sh; 604 } 605 return NULL; 606 } 607 608 static struct slab_object * 609 slap_replenish_sopool( 610 struct slab_heap* sh 611 ) 612 { 613 struct slab_object *so_block; 614 int i; 615 616 so_block = (struct slab_object *)ch_malloc( 617 SLAP_SLAB_SOBLOCK * sizeof(struct slab_object)); 618 619 if ( so_block == NULL ) { 620 return NULL; 621 } 622 623 so_block[0].so_blockhead = 1; 624 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, &so_block[0], so_link); 625 for (i = 1; i < SLAP_SLAB_SOBLOCK; i++) { 626 so_block[i].so_blockhead = 0; 627 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, &so_block[i], so_link ); 628 } 629 630 return so_block; 631 } 632 633 #ifdef SLAPD_UNUSED 634 static void 635 print_slheap(int level, void *ctx) 636 { 637 struct slab_heap *sh = ctx; 638 int order_start = -1; 639 int pad = 2*sizeof(int)-1, pad_shift; 640 struct slab_object *so; 641 int i, j, once = 0; 642 643 if (!ctx) { 644 Debug(level, "NULL memctx\n", 0, 0, 0); 645 return; 646 } 647 648 pad_shift = pad - 1; 649 do { 650 order_start++; 651 } while (pad_shift >>= 1); 652 653 Debug(level, "sh->sh_maxorder=%d\n", sh->sh_maxorder, 0, 0); 654 655 for (i = order_start; i <= sh->sh_maxorder; i++) { 656 once = 0; 657 Debug(level, "order=%d\n", i, 0, 0); 658 for (j = 0; j < (1<<(sh->sh_maxorder-i))/8; j++) { 659 Debug(level, "%02x ", sh->sh_map[i-order_start][j], 0, 0); 660 once = 1; 661 } 662 if (!once) { 663 Debug(level, "%02x ", sh->sh_map[i-order_start][0], 0, 0); 664 } 665 Debug(level, "\n", 0, 0, 0); 666 Debug(level, "free list:\n", 0, 0, 0); 667 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]); 668 while (so) { 669 Debug(level, "%lx\n", (unsigned long) so->so_ptr, 0, 0); 670 so = LDAP_LIST_NEXT(so, so_link); 671 } 672 } 673 } 674 #endif 675
Indexes created Mon Mar 30 00:23:01 UTC 2026