zn_malloc.c revision 1.2
1 /* $NetBSD: zn_malloc.c,v 1.2 2020/08/11 13:15:39 christos Exp $ */ 2 3 /* zn_malloc.c - zone-based malloc routines */ 4 /* $OpenLDAP$*/ 5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>. 6 * 7 * Copyright 2003-2020 The OpenLDAP Foundation. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted only as authorized by the OpenLDAP 12 * Public License. 13 * 14 * A copy of this license is available in the file LICENSE in the 15 * top-level directory of the distribution or, alternatively, at 16 * <http://www.OpenLDAP.org/license.html>. 17 */ 18 /* Portions Copyright 2004 IBM Corporation 19 * All rights reserved. 20 * Redistribution and use in source and binary forms, with or without 21 * modification, are permitted only as authorized by the OpenLDAP 22 * Public License. 23 */ 24 /* ACKNOWLEDGEMENTS 25 * This work originally developed by Jong-Hyuk Choi for inclusion in 26 * OpenLDAP Software. 27 */ 28 29 #include <sys/cdefs.h> 30 __RCSID("$NetBSD: zn_malloc.c,v 1.2 2020/08/11 13:15:39 christos Exp $"); 31 32 #include "portable.h" 33 34 #include <stdio.h> 35 #include <ac/string.h> 36 #include <sys/types.h> 37 #include <fcntl.h> 38 39 #include "slap.h" 40 41 #ifdef SLAP_ZONE_ALLOC 42 43 #include <sys/mman.h> 44 45 static int slap_zone_cmp(const void *v1, const void *v2); 46 void * slap_replenish_zopool(void *ctx); 47 48 static void 49 slap_zo_release(void *data) 50 { 51 struct zone_object *zo = (struct zone_object *)data; 52 ch_free( zo ); 53 } 54 55 void 56 slap_zn_mem_destroy( 57 void *ctx 58 ) 59 { 60 struct zone_heap *zh = ctx; 61 int pad = 2*sizeof(int)-1, pad_shift; 62 int order_start = -1, i, j; 63 struct zone_object *zo; 64 65 pad_shift = pad - 1; 66 do { 67 order_start++; 68 } while (pad_shift >>= 1); 69 70 ldap_pvt_thread_mutex_lock( &zh->zh_mutex ); 71 for (i = 0; i < zh->zh_zoneorder - order_start + 1; i++) { 72 zo = LDAP_LIST_FIRST(&zh->zh_free[i]); 73 while (zo) { 74 struct zone_object *zo_tmp = zo; 75 zo = LDAP_LIST_NEXT(zo, zo_link); 76 LDAP_LIST_REMOVE(zo_tmp, zo_link); 77 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_tmp, zo_link); 78 } 79 } 80 ch_free(zh->zh_free); 81 82 for (i = 0; i < zh->zh_numzones; i++) { 83 for (j = 0; j < zh->zh_zoneorder - order_start + 1; j++) { 84 ch_free(zh->zh_maps[i][j]); 85 } 86 ch_free(zh->zh_maps[i]); 87 munmap(zh->zh_zones[i], zh->zh_zonesize); 88 ldap_pvt_thread_rdwr_destroy(&zh->zh_znlock[i]); 89 } 90 ch_free(zh->zh_maps); 91 ch_free(zh->zh_zones); 92 ch_free(zh->zh_seqno); 93 ch_free(zh->zh_znlock); 94 95 avl_free(zh->zh_zonetree, slap_zo_release); 96 97 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 98 while (zo) { 99 struct zone_object *zo_tmp = zo; 100 zo = LDAP_LIST_NEXT(zo, zo_link); 101 if (!zo_tmp->zo_blockhead) { 102 LDAP_LIST_REMOVE(zo_tmp, zo_link); 103 } 104 } 105 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 106 while (zo) { 107 struct zone_object *zo_tmp = zo; 108 zo = LDAP_LIST_NEXT(zo, zo_link); 109 ch_free(zo_tmp); 110 } 111 ldap_pvt_thread_mutex_unlock(&zh->zh_mutex); 112 ldap_pvt_thread_rdwr_destroy(&zh->zh_lock); 113 ldap_pvt_thread_mutex_destroy(&zh->zh_mutex); 114 ch_free(zh); 115 } 116 117 void * 118 slap_zn_mem_create( 119 ber_len_t initsize, 120 ber_len_t maxsize, 121 ber_len_t deltasize, 122 ber_len_t zonesize 123 ) 124 { 125 struct zone_heap *zh = NULL; 126 ber_len_t zpad; 127 int pad = 2*sizeof(int)-1, pad_shift; 128 int size_shift; 129 int order = -1, order_start = -1, order_end = -1; 130 int i, j; 131 struct zone_object *zo; 132 133 Debug(LDAP_DEBUG_NONE, 134 "--> slap_zn_mem_create: initsize=%d, maxsize=%d\n", 135 initsize, maxsize, 0); 136 Debug(LDAP_DEBUG_NONE, 137 "++> slap_zn_mem_create: deltasize=%d, zonesize=%d\n", 138 deltasize, zonesize, 0); 139 140 zh = (struct zone_heap *)ch_calloc(1, sizeof(struct zone_heap)); 141 142 zh->zh_fd = open("/dev/zero", O_RDWR); 143 144 if ( zonesize ) { 145 zh->zh_zonesize = zonesize; 146 } else { 147 zh->zh_zonesize = SLAP_ZONE_SIZE; 148 } 149 150 zpad = zh->zh_zonesize - 1; 151 zh->zh_numzones = ((initsize + zpad) & ~zpad) / zh->zh_zonesize; 152 153 if ( maxsize && maxsize >= initsize ) { 154 zh->zh_maxzones = ((maxsize + zpad) & ~zpad) / zh->zh_zonesize; 155 } else { 156 zh->zh_maxzones = ((initsize + zpad) & ~zpad) / zh->zh_zonesize; 157 } 158 159 if ( deltasize ) { 160 zh->zh_deltazones = ((deltasize + zpad) & ~zpad) / zh->zh_zonesize; 161 } else { 162 zh->zh_deltazones = ((SLAP_ZONE_DELTA+zpad) & ~zpad) / zh->zh_zonesize; 163 } 164 165 size_shift = zh->zh_zonesize - 1; 166 do { 167 order_end++; 168 } while (size_shift >>= 1); 169 170 pad_shift = pad - 1; 171 do { 172 order_start++; 173 } while (pad_shift >>= 1); 174 175 order = order_end - order_start + 1; 176 177 zh->zh_zones = (void **)ch_malloc(zh->zh_maxzones * sizeof(void*)); 178 zh->zh_znlock = (ldap_pvt_thread_rdwr_t *)ch_malloc( 179 zh->zh_maxzones * sizeof(ldap_pvt_thread_rdwr_t *)); 180 zh->zh_maps = (unsigned char ***)ch_malloc( 181 zh->zh_maxzones * sizeof(unsigned char**)); 182 183 zh->zh_zoneorder = order_end; 184 zh->zh_free = (struct zh_freelist *) 185 ch_malloc(order * sizeof(struct zh_freelist)); 186 zh->zh_seqno = (unsigned long *)ch_calloc(zh->zh_maxzones, 187 sizeof(unsigned long)); 188 for (i = 0; i < order; i++) { 189 LDAP_LIST_INIT(&zh->zh_free[i]); 190 } 191 LDAP_LIST_INIT(&zh->zh_zopool); 192 193 for (i = 0; i < zh->zh_numzones; i++) { 194 zh->zh_zones[i] = mmap(0, zh->zh_zonesize, PROT_READ | PROT_WRITE, 195 MAP_PRIVATE, zh->zh_fd, 0); 196 zh->zh_maps[i] = (unsigned char **) 197 ch_malloc(order * sizeof(unsigned char *)); 198 for (j = 0; j < order; j++) { 199 int shiftamt = order_start + 1 + j; 200 int nummaps = zh->zh_zonesize >> shiftamt; 201 assert(nummaps); 202 nummaps >>= 3; 203 if (!nummaps) nummaps = 1; 204 zh->zh_maps[i][j] = (unsigned char *)ch_malloc(nummaps); 205 memset(zh->zh_maps[i][j], 0, nummaps); 206 } 207 208 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) { 209 slap_replenish_zopool(zh); 210 } 211 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 212 LDAP_LIST_REMOVE(zo, zo_link); 213 zo->zo_ptr = zh->zh_zones[i]; 214 zo->zo_idx = i; 215 LDAP_LIST_INSERT_HEAD(&zh->zh_free[order-1], zo, zo_link); 216 217 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) { 218 slap_replenish_zopool(zh); 219 } 220 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 221 LDAP_LIST_REMOVE(zo, zo_link); 222 zo->zo_ptr = zh->zh_zones[i]; 223 zo->zo_siz = zh->zh_zonesize; 224 zo->zo_idx = i; 225 avl_insert(&zh->zh_zonetree, zo, slap_zone_cmp, avl_dup_error); 226 ldap_pvt_thread_rdwr_init(&zh->zh_znlock[i]); 227 } 228 229 LDAP_STAILQ_INIT(&zh->zh_latency_history_queue); 230 ldap_pvt_thread_mutex_init(&zh->zh_mutex); 231 ldap_pvt_thread_rdwr_init(&zh->zh_lock); 232 233 return zh; 234 } 235 236 void * 237 slap_zn_malloc( 238 ber_len_t size, 239 void *ctx 240 ) 241 { 242 struct zone_heap *zh = ctx; 243 ber_len_t size_shift; 244 int pad = 2*sizeof(int)-1, pad_shift; 245 int order = -1, order_start = -1; 246 struct zone_object *zo, *zo_new, *zo_left, *zo_right; 247 ber_len_t *ptr, *new; 248 int idx; 249 unsigned long diff; 250 int i, j, k; 251 252 Debug(LDAP_DEBUG_NONE, 253 "--> slap_zn_malloc: size=%d\n", size, 0, 0); 254 255 if (!zh) return ber_memalloc_x(size, NULL); 256 257 /* round up to doubleword boundary */ 258 size += 2*sizeof(ber_len_t) + pad; 259 size &= ~pad; 260 261 size_shift = size - 1; 262 do { 263 order++; 264 } while (size_shift >>= 1); 265 266 pad_shift = pad - 1; 267 do { 268 order_start++; 269 } while (pad_shift >>= 1); 270 271 retry: 272 273 ldap_pvt_thread_mutex_lock( &zh->zh_mutex ); 274 for (i = order; i <= zh->zh_zoneorder && 275 LDAP_LIST_EMPTY(&zh->zh_free[i-order_start]); i++); 276 277 if (i == order) { 278 zo_new = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]); 279 LDAP_LIST_REMOVE(zo_new, zo_link); 280 ptr = zo_new->zo_ptr; 281 idx = zo_new->zo_idx; 282 diff = (unsigned long)((char*)ptr - 283 (char*)zh->zh_zones[idx]) >> (order + 1); 284 zh->zh_maps[idx][order-order_start][diff>>3] |= (1 << (diff & 0x7)); 285 *ptr++ = zh->zh_seqno[idx]; 286 *ptr++ = size - 2*sizeof(ber_len_t); 287 zo_new->zo_ptr = NULL; 288 zo_new->zo_idx = -1; 289 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_new, zo_link); 290 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 291 Debug(LDAP_DEBUG_NONE, "slap_zn_malloc: returning 0x%x, 0x%x\n", 292 ptr, (int)ptr>>(zh->zh_zoneorder+1), 0); 293 return((void*)ptr); 294 } else if (i <= zh->zh_zoneorder) { 295 for (j = i; j > order; j--) { 296 zo_left = LDAP_LIST_FIRST(&zh->zh_free[j-order_start]); 297 LDAP_LIST_REMOVE(zo_left, zo_link); 298 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) { 299 slap_replenish_zopool(zh); 300 } 301 zo_right = LDAP_LIST_FIRST(&zh->zh_zopool); 302 LDAP_LIST_REMOVE(zo_right, zo_link); 303 zo_right->zo_ptr = zo_left->zo_ptr + (1 << j); 304 zo_right->zo_idx = zo_left->zo_idx; 305 Debug(LDAP_DEBUG_NONE, 306 "slap_zn_malloc: split (left=0x%x, right=0x%x)\n", 307 zo_left->zo_ptr, zo_right->zo_ptr, 0); 308 if (j == order + 1) { 309 ptr = zo_left->zo_ptr; 310 diff = (unsigned long)((char*)ptr - 311 (char*)zh->zh_zones[zo_left->zo_idx]) >> (order+1); 312 zh->zh_maps[zo_left->zo_idx][order-order_start][diff>>3] |= 313 (1 << (diff & 0x7)); 314 *ptr++ = zh->zh_seqno[zo_left->zo_idx]; 315 *ptr++ = size - 2*sizeof(ber_len_t); 316 LDAP_LIST_INSERT_HEAD( 317 &zh->zh_free[j-1-order_start], zo_right, zo_link); 318 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_left, zo_link); 319 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 320 Debug(LDAP_DEBUG_NONE, 321 "slap_zn_malloc: returning 0x%x, 0x%x\n", 322 ptr, (int)ptr>>(zh->zh_zoneorder+1), 0); 323 return((void*)ptr); 324 } else { 325 LDAP_LIST_INSERT_HEAD( 326 &zh->zh_free[j-1-order_start], zo_right, zo_link); 327 LDAP_LIST_INSERT_HEAD( 328 &zh->zh_free[j-1-order_start], zo_left, zo_link); 329 } 330 } 331 assert(0); 332 } else { 333 334 if ( zh->zh_maxzones < zh->zh_numzones + zh->zh_deltazones ) { 335 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 336 Debug( LDAP_DEBUG_TRACE, 337 "zn_malloc %lu: ch_malloc\n", 338 (long)size, 0, 0); 339 Debug(LDAP_DEBUG_NONE, 340 "slap_zn_malloc: returning 0x%x, 0x%x\n", 341 ptr, (int)ptr>>(zh->zh_zoneorder+1), 0); 342 return (void*)ch_malloc(size); 343 } 344 345 for (i = zh->zh_numzones; i < zh->zh_numzones+zh->zh_deltazones; i++) { 346 zh->zh_zones[i] = mmap(0, zh->zh_zonesize, PROT_READ | PROT_WRITE, 347 MAP_PRIVATE, zh->zh_fd, 0); 348 zh->zh_maps[i] = (unsigned char **) 349 ch_malloc((zh->zh_zoneorder - order_start + 1) * 350 sizeof(unsigned char *)); 351 for (j = 0; j < zh->zh_zoneorder-order_start+1; j++) { 352 int shiftamt = order_start + 1 + j; 353 int nummaps = zh->zh_zonesize >> shiftamt; 354 assert(nummaps); 355 nummaps >>= 3; 356 if (!nummaps) nummaps = 1; 357 zh->zh_maps[i][j] = (unsigned char *)ch_malloc(nummaps); 358 memset(zh->zh_maps[i][j], 0, nummaps); 359 } 360 361 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) { 362 slap_replenish_zopool(zh); 363 } 364 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 365 LDAP_LIST_REMOVE(zo, zo_link); 366 zo->zo_ptr = zh->zh_zones[i]; 367 zo->zo_idx = i; 368 LDAP_LIST_INSERT_HEAD(&zh-> 369 zh_free[zh->zh_zoneorder-order_start],zo,zo_link); 370 371 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) { 372 slap_replenish_zopool(zh); 373 } 374 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 375 LDAP_LIST_REMOVE(zo, zo_link); 376 zo->zo_ptr = zh->zh_zones[i]; 377 zo->zo_siz = zh->zh_zonesize; 378 zo->zo_idx = i; 379 avl_insert(&zh->zh_zonetree, zo, slap_zone_cmp, avl_dup_error); 380 ldap_pvt_thread_rdwr_init(&zh->zh_znlock[i]); 381 } 382 zh->zh_numzones += zh->zh_deltazones; 383 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 384 goto retry; 385 } 386 } 387 388 void * 389 slap_zn_calloc( ber_len_t n, ber_len_t size, void *ctx ) 390 { 391 void *new; 392 393 new = slap_zn_malloc( n*size, ctx ); 394 if ( new ) { 395 memset( new, 0, n*size ); 396 } 397 return new; 398 } 399 400 void * 401 slap_zn_realloc(void *ptr, ber_len_t size, void *ctx) 402 { 403 struct zone_heap *zh = ctx; 404 int pad = 2*sizeof(int)-1, pad_shift; 405 int order_start = -1, order = -1; 406 struct zone_object zoi, *zoo; 407 ber_len_t *p = (ber_len_t *)ptr, *new; 408 unsigned long diff; 409 int i; 410 void *newptr = NULL; 411 struct zone_heap *zone = NULL; 412 413 Debug(LDAP_DEBUG_NONE, 414 "--> slap_zn_realloc: ptr=0x%x, size=%d\n", ptr, size, 0); 415 416 if (ptr == NULL) 417 return slap_zn_malloc(size, zh); 418 419 zoi.zo_ptr = p; 420 zoi.zo_idx = -1; 421 422 if (zh) { 423 ldap_pvt_thread_mutex_lock( &zh->zh_mutex ); 424 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp); 425 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 426 } 427 428 /* Not our memory? */ 429 if (!zoo) { 430 /* duplicate of realloc behavior, oh well */ 431 new = ber_memrealloc_x(ptr, size, NULL); 432 if (new) { 433 return new; 434 } 435 Debug(LDAP_DEBUG_ANY, "ch_realloc of %lu bytes failed\n", 436 (long) size, 0, 0); 437 assert(0); 438 exit( EXIT_FAILURE ); 439 } 440 441 assert(zoo->zo_idx != -1); 442 443 zone = zh->zh_zones[zoo->zo_idx]; 444 445 if (size == 0) { 446 slap_zn_free(ptr, zh); 447 return NULL; 448 } 449 450 newptr = slap_zn_malloc(size, zh); 451 if (size < p[-1]) { 452 AC_MEMCPY(newptr, ptr, size); 453 } else { 454 AC_MEMCPY(newptr, ptr, p[-1]); 455 } 456 slap_zn_free(ptr, zh); 457 return newptr; 458 } 459 460 void 461 slap_zn_free(void *ptr, void *ctx) 462 { 463 struct zone_heap *zh = ctx; 464 int size, size_shift, order_size; 465 int pad = 2*sizeof(int)-1, pad_shift; 466 ber_len_t *p = (ber_len_t *)ptr, *tmpp; 467 int order_start = -1, order = -1; 468 struct zone_object zoi, *zoo, *zo; 469 unsigned long diff; 470 int i, k, inserted = 0, idx; 471 struct zone_heap *zone = NULL; 472 473 zoi.zo_ptr = p; 474 zoi.zo_idx = -1; 475 476 Debug(LDAP_DEBUG_NONE, "--> slap_zn_free: ptr=0x%x\n", ptr, 0, 0); 477 478 if (zh) { 479 ldap_pvt_thread_mutex_lock( &zh->zh_mutex ); 480 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp); 481 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 482 } 483 484 if (!zoo) { 485 ber_memfree_x(ptr, NULL); 486 } else { 487 idx = zoo->zo_idx; 488 assert(idx != -1); 489 zone = zh->zh_zones[idx]; 490 491 size = *(--p); 492 size_shift = size + 2*sizeof(ber_len_t) - 1; 493 do { 494 order++; 495 } while (size_shift >>= 1); 496 497 pad_shift = pad - 1; 498 do { 499 order_start++; 500 } while (pad_shift >>= 1); 501 502 ldap_pvt_thread_mutex_lock( &zh->zh_mutex ); 503 for (i = order, tmpp = p; i <= zh->zh_zoneorder; i++) { 504 order_size = 1 << (i+1); 505 diff = (unsigned long)((char*)tmpp - (char*)zone) >> (i+1); 506 zh->zh_maps[idx][i-order_start][diff>>3] &= (~(1 << (diff & 0x7))); 507 if (diff == ((diff>>1)<<1)) { 508 if (!(zh->zh_maps[idx][i-order_start][(diff+1)>>3] & 509 (1<<((diff+1)&0x7)))) { 510 zo = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]); 511 while (zo) { 512 if ((char*)zo->zo_ptr == (char*)tmpp) { 513 LDAP_LIST_REMOVE( zo, zo_link ); 514 } else if ((char*)zo->zo_ptr == 515 (char*)tmpp + order_size) { 516 LDAP_LIST_REMOVE(zo, zo_link); 517 break; 518 } 519 zo = LDAP_LIST_NEXT(zo, zo_link); 520 } 521 if (zo) { 522 if (i < zh->zh_zoneorder) { 523 inserted = 1; 524 zo->zo_ptr = tmpp; 525 Debug(LDAP_DEBUG_NONE, 526 "slap_zn_free: merging 0x%x\n", 527 zo->zo_ptr, 0, 0); 528 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start+1], 529 zo, zo_link); 530 } 531 continue; 532 } else { 533 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) { 534 slap_replenish_zopool(zh); 535 } 536 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 537 LDAP_LIST_REMOVE(zo, zo_link); 538 zo->zo_ptr = tmpp; 539 zo->zo_idx = idx; 540 Debug(LDAP_DEBUG_NONE, 541 "slap_zn_free: merging 0x%x\n", 542 zo->zo_ptr, 0, 0); 543 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start], 544 zo, zo_link); 545 break; 546 547 Debug(LDAP_DEBUG_ANY, "slap_zn_free: " 548 "free object not found while bit is clear.\n", 549 0, 0, 0); 550 assert(zo != NULL); 551 552 } 553 } else { 554 if (!inserted) { 555 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) { 556 slap_replenish_zopool(zh); 557 } 558 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 559 LDAP_LIST_REMOVE(zo, zo_link); 560 zo->zo_ptr = tmpp; 561 zo->zo_idx = idx; 562 Debug(LDAP_DEBUG_NONE, 563 "slap_zn_free: merging 0x%x\n", 564 zo->zo_ptr, 0, 0); 565 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start], 566 zo, zo_link); 567 } 568 break; 569 } 570 } else { 571 if (!(zh->zh_maps[idx][i-order_start][(diff-1)>>3] & 572 (1<<((diff-1)&0x7)))) { 573 zo = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]); 574 while (zo) { 575 if ((char*)zo->zo_ptr == (char*)tmpp) { 576 LDAP_LIST_REMOVE(zo, zo_link); 577 } else if ((char*)tmpp == zo->zo_ptr + order_size) { 578 LDAP_LIST_REMOVE(zo, zo_link); 579 tmpp = zo->zo_ptr; 580 break; 581 } 582 zo = LDAP_LIST_NEXT(zo, zo_link); 583 } 584 if (zo) { 585 if (i < zh->zh_zoneorder) { 586 inserted = 1; 587 Debug(LDAP_DEBUG_NONE, 588 "slap_zn_free: merging 0x%x\n", 589 zo->zo_ptr, 0, 0); 590 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start+1], 591 zo, zo_link); 592 continue; 593 } 594 } else { 595 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) { 596 slap_replenish_zopool(zh); 597 } 598 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 599 LDAP_LIST_REMOVE(zo, zo_link); 600 zo->zo_ptr = tmpp; 601 zo->zo_idx = idx; 602 Debug(LDAP_DEBUG_NONE, 603 "slap_zn_free: merging 0x%x\n", 604 zo->zo_ptr, 0, 0); 605 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start], 606 zo, zo_link); 607 break; 608 609 Debug(LDAP_DEBUG_ANY, "slap_zn_free: " 610 "free object not found while bit is clear.\n", 611 0, 0, 0 ); 612 assert(zo != NULL); 613 614 } 615 } else { 616 if ( !inserted ) { 617 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) { 618 slap_replenish_zopool(zh); 619 } 620 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 621 LDAP_LIST_REMOVE(zo, zo_link); 622 zo->zo_ptr = tmpp; 623 zo->zo_idx = idx; 624 Debug(LDAP_DEBUG_NONE, 625 "slap_zn_free: merging 0x%x\n", 626 zo->zo_ptr, 0, 0); 627 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start], 628 zo, zo_link); 629 } 630 break; 631 } 632 } 633 } 634 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 635 } 636 } 637 638 static int 639 slap_zone_cmp(const void *v1, const void *v2) 640 { 641 const struct zone_object *zo1 = v1; 642 const struct zone_object *zo2 = v2; 643 char *ptr1; 644 char *ptr2; 645 ber_len_t zpad; 646 647 zpad = zo2->zo_siz - 1; 648 ptr1 = (char*)(((unsigned long)zo1->zo_ptr + zpad) & ~zpad); 649 ptr2 = (char*)zo2->zo_ptr + ((char*)ptr1 - (char*)zo1->zo_ptr); 650 ptr2 = (char*)(((unsigned long)ptr2 + zpad) & ~zpad); 651 return (int)((char*)ptr1 - (char*)ptr2); 652 } 653 654 void * 655 slap_replenish_zopool( 656 void *ctx 657 ) 658 { 659 struct zone_heap* zh = ctx; 660 struct zone_object *zo_block; 661 int i; 662 663 zo_block = (struct zone_object *)ch_malloc( 664 SLAP_ZONE_ZOBLOCK * sizeof(struct zone_object)); 665 666 if ( zo_block == NULL ) { 667 return NULL; 668 } 669 670 zo_block[0].zo_blockhead = 1; 671 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, &zo_block[0], zo_link); 672 for (i = 1; i < SLAP_ZONE_ZOBLOCK; i++) { 673 zo_block[i].zo_blockhead = 0; 674 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, &zo_block[i], zo_link ); 675 } 676 677 return zo_block; 678 } 679 680 int 681 slap_zn_invalidate( 682 void *ctx, 683 void *ptr 684 ) 685 { 686 struct zone_heap* zh = ctx; 687 struct zone_object zoi, *zoo; 688 struct zone_heap *zone = NULL; 689 int seqno = *((ber_len_t*)ptr - 2); 690 int idx = -1, rc = 0; 691 int pad = 2*sizeof(int)-1, pad_shift; 692 int order_start = -1, i; 693 struct zone_object *zo; 694 695 pad_shift = pad - 1; 696 do { 697 order_start++; 698 } while (pad_shift >>= 1); 699 700 zoi.zo_ptr = ptr; 701 zoi.zo_idx = -1; 702 703 ldap_pvt_thread_mutex_lock( &zh->zh_mutex ); 704 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp); 705 706 if (zoo) { 707 idx = zoo->zo_idx; 708 assert(idx != -1); 709 madvise(zh->zh_zones[idx], zh->zh_zonesize, MADV_DONTNEED); 710 for (i = 0; i < zh->zh_zoneorder - order_start + 1; i++) { 711 int shiftamt = order_start + 1 + i; 712 int nummaps = zh->zh_zonesize >> shiftamt; 713 assert(nummaps); 714 nummaps >>= 3; 715 if (!nummaps) nummaps = 1; 716 memset(zh->zh_maps[idx][i], 0, nummaps); 717 zo = LDAP_LIST_FIRST(&zh->zh_free[i]); 718 while (zo) { 719 struct zone_object *zo_tmp = zo; 720 zo = LDAP_LIST_NEXT(zo, zo_link); 721 if (zo_tmp && zo_tmp->zo_idx == idx) { 722 LDAP_LIST_REMOVE(zo_tmp, zo_link); 723 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_tmp, zo_link); 724 } 725 } 726 } 727 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) { 728 slap_replenish_zopool(zh); 729 } 730 zo = LDAP_LIST_FIRST(&zh->zh_zopool); 731 LDAP_LIST_REMOVE(zo, zo_link); 732 zo->zo_ptr = zh->zh_zones[idx]; 733 zo->zo_idx = idx; 734 LDAP_LIST_INSERT_HEAD(&zh->zh_free[zh->zh_zoneorder-order_start], 735 zo, zo_link); 736 zh->zh_seqno[idx]++; 737 } else { 738 Debug(LDAP_DEBUG_NONE, "zone not found for (ctx=0x%x, ptr=0x%x) !\n", 739 ctx, ptr, 0); 740 } 741 742 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 743 Debug(LDAP_DEBUG_NONE, "zone %d invalidate\n", idx, 0, 0); 744 return rc; 745 } 746 747 int 748 slap_zn_validate( 749 void *ctx, 750 void *ptr, 751 int seqno 752 ) 753 { 754 struct zone_heap* zh = ctx; 755 struct zone_object zoi, *zoo; 756 struct zone_heap *zone = NULL; 757 int idx, rc = 0; 758 759 zoi.zo_ptr = ptr; 760 zoi.zo_idx = -1; 761 762 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp); 763 764 if (zoo) { 765 idx = zoo->zo_idx; 766 assert(idx != -1); 767 assert(seqno <= zh->zh_seqno[idx]); 768 rc = (seqno == zh->zh_seqno[idx]); 769 } 770 771 return rc; 772 } 773 774 int slap_zh_rlock( 775 void *ctx 776 ) 777 { 778 struct zone_heap* zh = ctx; 779 ldap_pvt_thread_rdwr_rlock(&zh->zh_lock); 780 } 781 782 int slap_zh_runlock( 783 void *ctx 784 ) 785 { 786 struct zone_heap* zh = ctx; 787 ldap_pvt_thread_rdwr_runlock(&zh->zh_lock); 788 } 789 790 int slap_zh_wlock( 791 void *ctx 792 ) 793 { 794 struct zone_heap* zh = ctx; 795 ldap_pvt_thread_rdwr_wlock(&zh->zh_lock); 796 } 797 798 int slap_zh_wunlock( 799 void *ctx 800 ) 801 { 802 struct zone_heap* zh = ctx; 803 ldap_pvt_thread_rdwr_wunlock(&zh->zh_lock); 804 } 805 806 int slap_zn_rlock( 807 void *ctx, 808 void *ptr 809 ) 810 { 811 struct zone_heap* zh = ctx; 812 struct zone_object zoi, *zoo; 813 struct zone_heap *zone = NULL; 814 int idx; 815 816 zoi.zo_ptr = ptr; 817 zoi.zo_idx = -1; 818 819 ldap_pvt_thread_mutex_lock( &zh->zh_mutex ); 820 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp); 821 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 822 823 if (zoo) { 824 idx = zoo->zo_idx; 825 assert(idx != -1); 826 ldap_pvt_thread_rdwr_rlock(&zh->zh_znlock[idx]); 827 } 828 } 829 830 int slap_zn_runlock( 831 void *ctx, 832 void *ptr 833 ) 834 { 835 struct zone_heap* zh = ctx; 836 struct zone_object zoi, *zoo; 837 struct zone_heap *zone = NULL; 838 int idx; 839 840 zoi.zo_ptr = ptr; 841 zoi.zo_idx = -1; 842 843 ldap_pvt_thread_mutex_lock( &zh->zh_mutex ); 844 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp); 845 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 846 847 if (zoo) { 848 idx = zoo->zo_idx; 849 assert(idx != -1); 850 ldap_pvt_thread_rdwr_runlock(&zh->zh_znlock[idx]); 851 } 852 } 853 854 int slap_zn_wlock( 855 void *ctx, 856 void *ptr 857 ) 858 { 859 struct zone_heap* zh = ctx; 860 struct zone_object zoi, *zoo; 861 struct zone_heap *zone = NULL; 862 int idx; 863 864 zoi.zo_ptr = ptr; 865 zoi.zo_idx = -1; 866 867 ldap_pvt_thread_mutex_lock( &zh->zh_mutex ); 868 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp); 869 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 870 871 if (zoo) { 872 idx = zoo->zo_idx; 873 assert(idx != -1); 874 ldap_pvt_thread_rdwr_wlock(&zh->zh_znlock[idx]); 875 } 876 } 877 878 int slap_zn_wunlock( 879 void *ctx, 880 void *ptr 881 ) 882 { 883 struct zone_heap* zh = ctx; 884 struct zone_object zoi, *zoo; 885 struct zone_heap *zone = NULL; 886 int idx; 887 888 zoi.zo_ptr = ptr; 889 zoi.zo_idx = -1; 890 891 ldap_pvt_thread_mutex_lock( &zh->zh_mutex ); 892 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp); 893 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex ); 894 895 if (zoo) { 896 idx = zoo->zo_idx; 897 assert(idx != -1); 898 ldap_pvt_thread_rdwr_wunlock(&zh->zh_znlock[idx]); 899 } 900 } 901 902 #define T_SEC_IN_USEC 1000000 903 904 static int 905 slap_timediff(struct timeval *tv_begin, struct timeval *tv_end) 906 { 907 uint64_t t_begin, t_end, t_diff; 908 909 t_begin = T_SEC_IN_USEC * tv_begin->tv_sec + tv_begin->tv_usec; 910 t_end = T_SEC_IN_USEC * tv_end->tv_sec + tv_end->tv_usec; 911 t_diff = t_end - t_begin; 912 913 if ( t_diff < 0 ) 914 t_diff = 0; 915 916 return (int)t_diff; 917 } 918 919 void 920 slap_set_timing(struct timeval *tv_set) 921 { 922 gettimeofday(tv_set, (struct timezone *)NULL); 923 } 924 925 int 926 slap_measure_timing(struct timeval *tv_set, struct timeval *tv_measure) 927 { 928 gettimeofday(tv_measure, (struct timezone *)NULL); 929 return(slap_timediff(tv_set, tv_measure)); 930 } 931 932 #define EMA_WEIGHT 0.999000 933 #define SLAP_ZN_LATENCY_HISTORY_QLEN 500 934 int 935 slap_zn_latency_history(void* ctx, int ea_latency) 936 { 937 /* TODO: monitor /proc/stat (swap) as well */ 938 struct zone_heap* zh = ctx; 939 double t_diff = 0.0; 940 941 zh->zh_ema_latency = (double)ea_latency * (1.0 - EMA_WEIGHT) 942 + zh->zh_ema_latency * EMA_WEIGHT; 943 if (!zh->zh_swapping && zh->zh_ema_samples++ % 100 == 99) { 944 struct zone_latency_history *zlh_entry; 945 zlh_entry = ch_calloc(1, sizeof(struct zone_latency_history)); 946 zlh_entry->zlh_latency = zh->zh_ema_latency; 947 LDAP_STAILQ_INSERT_TAIL( 948 &zh->zh_latency_history_queue, zlh_entry, zlh_next); 949 zh->zh_latency_history_qlen++; 950 while (zh->zh_latency_history_qlen > SLAP_ZN_LATENCY_HISTORY_QLEN) { 951 struct zone_latency_history *zlh; 952 zlh = LDAP_STAILQ_FIRST(&zh->zh_latency_history_queue); 953 LDAP_STAILQ_REMOVE_HEAD( 954 &zh->zh_latency_history_queue, zlh_next); 955 zh->zh_latency_history_qlen--; 956 ch_free(zlh); 957 } 958 if (zh->zh_latency_history_qlen == SLAP_ZN_LATENCY_HISTORY_QLEN) { 959 struct zone_latency_history *zlh_first, *zlh_last; 960 zlh_first = LDAP_STAILQ_FIRST(&zh->zh_latency_history_queue); 961 zlh_last = LDAP_STAILQ_LAST(&zh->zh_latency_history_queue, 962 zone_latency_history, zlh_next); 963 t_diff = zlh_last->zlh_latency - zlh_first->zlh_latency; 964 } 965 if (t_diff >= 2000) { 966 zh->zh_latency_jump++; 967 } else { 968 zh->zh_latency_jump = 0; 969 } 970 if (zh->zh_latency_jump > 3) { 971 zh->zh_latency_jump = 0; 972 zh->zh_swapping = 1; 973 } 974 } 975 return zh->zh_swapping; 976 } 977 #endif /* SLAP_ZONE_ALLOC */ 978
Indexes created Sun Mar 29 00:23:15 UTC 2026