git.sur5r.net Git - openldap/blob - servers/slapd/zn_malloc.c

   1 /* zn_malloc.c - zone-based malloc routines */
   2 /* $OpenLDAP$*/
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2003-2004 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 /* Copyright 2004 IBM Corporation
  17  * All rights reserved.
  18  * Redisribution and use in source and binary forms, with or without
  19  * modification, are permitted only as  authorizd by the OpenLADP
  20  * Public License.
  21  */
  22 /* ACKNOWLEDGEMENTS
  23  * This work originally developed by Jong-Hyuk Choi
  24  * 2004/12/09   jongchoi@OpenLDAP.org
  25  */
  26
  27 #include "portable.h"
  28
  29 #include <stdio.h>
  30 #include <ac/string.h>
  31 #include <sys/types.h>
  32 #include <sys/mman.h>
  33 #include <fcntl.h>
  34
  35 #include "slap.h"
  36
  37 #ifdef SLAP_ZONE_ALLOC
  38
  39 static int slap_zone_cmp(const void *v1, const void *v2);
  40 void * slap_replenish_zopool(void *ctx);
  41
  42 static void
  43 slap_zo_release(void *data)
  44 {
  45         struct zone_object *zo = (struct zone_object *)data;
  46         ch_free( zo );
  47 }
  48
  49 void
  50 slap_zn_mem_destroy(
  51         void *ctx
  52 )
  53 {
  54         struct zone_heap *zh = ctx;
  55         int pad = 2*sizeof(int)-1, pad_shift;
  56         int order_start = -1, i, j;
  57         struct zone_object *zo;
  58
  59         pad_shift = pad - 1;
  60         do {
  61                 order_start++;
  62         } while (pad_shift >>= 1);
  63
  64         ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
  65         for (i = 0; i <= zh->zh_zoneorder - order_start; i++) {
  66                 zo = LDAP_LIST_FIRST(&zh->zh_free[i]);
  67                 while (zo) {
  68                         struct zone_object *zo_tmp = zo;
  69                         zo = LDAP_LIST_NEXT(zo, zo_link);
  70                         LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_tmp, zo_link);
  71                 }
  72         }
  73         ch_free(zh->zh_free);
  74
  75         for (i = 0; i < zh->zh_numzones; i++) {
  76                 for (j = 0; j < zh->zh_zoneorder - order_start; j++) {
  77                         ch_free(zh->zh_maps[i][j]);
  78                 }
  79                 ch_free(zh->zh_maps[i]);
  80                 munmap(zh->zh_zones[i], zh->zh_zonesize);
  81         }
  82         ch_free(zh->zh_maps);
  83         ch_free(zh->zh_zones);
  84         ch_free(zh->zh_seqno);
  85
  86         avl_free(zh->zh_zonetree, slap_zo_release);
  87
  88         zo = LDAP_LIST_FIRST(&zh->zh_zopool);
  89         while (zo) {
  90                 struct zone_object *zo_tmp = zo;
  91                 zo = LDAP_LIST_NEXT(zo, zo_link);
  92                 if (!zo_tmp->zo_blockhead) {
  93                         LDAP_LIST_REMOVE(zo_tmp, zo_link);
  94                 }
  95         }
  96         zo = LDAP_LIST_FIRST(&zh->zh_zopool);
  97         while (zo) {
  98                 struct zone_object *zo_tmp = zo;
  99                 zo = LDAP_LIST_NEXT(zo, zo_link);
 100                 ch_free(zo_tmp);
 101         }
 102         ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
 103         ldap_pvt_thread_mutex_destroy( &zh->zh_mutex );
 104         ch_free(zh);
 105 }
 106
 107 void *
 108 slap_zn_mem_create(
 109         ber_len_t initsize,
 110         ber_len_t maxsize,
 111         ber_len_t deltasize,
 112         ber_len_t zonesize
 113 )
 114 {
 115         struct zone_heap *zh = NULL;
 116         ber_len_t zpad;
 117         int pad = 2*sizeof(int)-1, pad_shift;
 118         int size_shift;
 119         int order = -1, order_start = -1, order_end = -1;
 120         int i, j;
 121         struct zone_object *zo;
 122
 123         Debug(LDAP_DEBUG_NONE,
 124                 "--> slap_zn_mem_create: initsize=%d, maxsize=%d\n",
 125                 initsize, maxsize, 0);
 126         Debug(LDAP_DEBUG_NONE,
 127                 "++> slap_zn_mem_create: deltasize=%d, zonesize=%d\n",
 128                 deltasize, zonesize, 0);
 129
 130         zh = (struct zone_heap *)ch_calloc(1, sizeof(struct zone_heap));
 131
 132         zh->zh_fd = open("/dev/zero", O_RDWR);
 133
 134         if ( zonesize ) {
 135                 zh->zh_zonesize = zonesize;
 136         } else {
 137                 zh->zh_zonesize = SLAP_ZONE_SIZE;
 138         }
 139
 140         zpad = zh->zh_zonesize - 1;
 141         zh->zh_numzones = ((initsize + zpad) & ~zpad) / zh->zh_zonesize;
 142
 143         if ( maxsize && maxsize >= initsize ) {
 144                 zh->zh_maxzones = ((maxsize + zpad) & ~zpad) / zh->zh_zonesize;
 145         } else {
 146                 zh->zh_maxzones = ((initsize + zpad) & ~zpad) / zh->zh_zonesize;
 147         }
 148
 149         if ( deltasize ) {
 150                 zh->zh_deltazones = ((deltasize + zpad) & ~zpad) / zh->zh_zonesize;
 151         } else {
 152                 zh->zh_deltazones = ((SLAP_ZONE_DELTA+zpad) & ~zpad) / zh->zh_zonesize;
 153         }
 154
 155         size_shift = zh->zh_zonesize - 1;
 156         do {
 157                 order_end++;
 158         } while (size_shift >>= 1);
 159
 160         pad_shift = pad - 1;
 161         do {
 162                 order_start++;
 163         } while (pad_shift >>= 1);
 164
 165         order = order_end - order_start + 1;
 166
 167         zh->zh_zones = (void **)ch_malloc(zh->zh_maxzones * sizeof(void*));
 168         zh->zh_maps = (unsigned char ***)ch_malloc(
 169                                         zh->zh_maxzones * sizeof(unsigned char**));
 170
 171         zh->zh_zoneorder = order_end;
 172         zh->zh_free = (struct zh_freelist *)
 173                                         ch_malloc(order * sizeof(struct zh_freelist));
 174         zh->zh_seqno = (unsigned long *)ch_calloc(zh->zh_maxzones,
 175                                                                                         sizeof(unsigned long));
 176         for (i = 0; i < order; i++) {
 177                 LDAP_LIST_INIT(&zh->zh_free[i]);
 178         }
 179         LDAP_LIST_INIT(&zh->zh_zopool);
 180
 181         for (i = 0; i < zh->zh_numzones; i++) {
 182                 zh->zh_zones[i] = mmap(0, zh->zh_zonesize, PROT_READ | PROT_WRITE,
 183                                                         MAP_PRIVATE, zh->zh_fd, 0);
 184                 zh->zh_maps[i] = (unsigned char **)
 185                                         ch_malloc(order * sizeof(unsigned char *));
 186                 for (j = 0; j < order; j++) {
 187                         int shiftamt = order_start + 1 + j;
 188                         int nummaps = zh->zh_zonesize >> shiftamt;
 189                         assert(nummaps);
 190                         nummaps /= 8;
 191                         if (!nummaps) nummaps = 1;
 192                         zh->zh_maps[i][j] = (unsigned char *)ch_malloc(nummaps);
 193                         memset(zh->zh_maps[i][j], 0, nummaps);
 194                 }
 195
 196                 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
 197                         slap_replenish_zopool(zh);
 198                 }
 199                 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
 200                 LDAP_LIST_REMOVE(zo, zo_link);
 201                 zo->zo_ptr = zh->zh_zones[i];
 202                 zo->zo_idx = i;
 203                 LDAP_LIST_INSERT_HEAD(&zh->zh_free[order-1], zo, zo_link);
 204
 205                 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
 206                         slap_replenish_zopool(zh);
 207                 }
 208                 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
 209                 LDAP_LIST_REMOVE(zo, zo_link);
 210                 zo->zo_ptr = zh->zh_zones[i];
 211                 zo->zo_siz = zh->zh_zonesize;
 212                 zo->zo_idx = i;
 213                 avl_insert(&zh->zh_zonetree, zo, slap_zone_cmp, avl_dup_error);
 214         }
 215
 216         ldap_pvt_thread_mutex_init(&zh->zh_mutex);
 217
 218         return zh;
 219 }
 220
 221 void *
 222 slap_zn_malloc(
 223     ber_len_t   size,
 224         void *ctx
 225 )
 226 {
 227         struct zone_heap *zh = ctx;
 228         ber_len_t size_shift;
 229         int pad = 2*sizeof(int)-1, pad_shift;
 230         int order = -1, order_start = -1;
 231         struct zone_object *zo, *zo_new, *zo_left, *zo_right;
 232         ber_len_t *ptr, *new;
 233         int idx;
 234         unsigned long diff;
 235         int i, j, k;
 236
 237         Debug(LDAP_DEBUG_NONE,
 238                 "--> slap_zn_malloc: size=%d\n", size, 0, 0);
 239
 240         if (!zh) return ber_memalloc_x(size, NULL);
 241
 242         /* round up to doubleword boundary */
 243         size += 2*sizeof(ber_len_t) + pad;
 244         size &= ~pad;
 245
 246         size_shift = size - 1;
 247         do {
 248                 order++;
 249         } while (size_shift >>= 1);
 250
 251         pad_shift = pad - 1;
 252         do {
 253                 order_start++;
 254         } while (pad_shift >>= 1);
 255
 256 retry:
 257
 258         ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
 259         for (i = order; i <= zh->zh_zoneorder &&
 260                         LDAP_LIST_EMPTY(&zh->zh_free[i-order_start]); i++);
 261
 262         if (i == order) {
 263                 zo_new = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
 264                 LDAP_LIST_REMOVE(zo_new, zo_link);
 265                 ptr = zo_new->zo_ptr;
 266                 idx = zo_new->zo_idx;
 267                 diff = (unsigned long)((char*)ptr -
 268                                 (char*)zh->zh_zones[idx]) >> (order + 1);
 269                 zh->zh_maps[idx][order-order_start][diff>>3] |= (1 << (diff & 0x7));
 270                 *ptr++ = zh->zh_seqno[idx];
 271                 *ptr++ = size - 2*sizeof(ber_len_t);
 272                 zo_new->zo_ptr = NULL;
 273                 zo_new->zo_idx = -1;
 274                 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_new, zo_link);
 275                 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
 276                 Debug(LDAP_DEBUG_NONE, "slap_zn_malloc: returning 0x%x, 0x%x\n",
 277                                 ptr, (int)ptr>>(zh->zh_zoneorder+1), 0);
 278                 return((void*)ptr);
 279         } else if (i <= zh->zh_zoneorder) {
 280                 for (j = i; j > order; j--) {
 281                         zo_left = LDAP_LIST_FIRST(&zh->zh_free[j-order_start]);
 282                         LDAP_LIST_REMOVE(zo_left, zo_link);
 283                         if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
 284                                 slap_replenish_zopool(zh);
 285                         }
 286                         zo_right = LDAP_LIST_FIRST(&zh->zh_zopool);
 287                         LDAP_LIST_REMOVE(zo_right, zo_link);
 288                         zo_right->zo_ptr = zo_left->zo_ptr + (1 << j);
 289                         zo_right->zo_idx = zo_left->zo_idx;
 290                         Debug(LDAP_DEBUG_NONE,
 291                                 "slap_zn_malloc: split (left=0x%x, right=0x%x)\n",
 292                                 zo_left->zo_ptr, zo_right->zo_ptr, 0);
 293                         if (j == order + 1) {
 294                                 ptr = zo_left->zo_ptr;
 295                                 diff = (unsigned long)((char*)ptr -
 296                                                 (char*)zh->zh_zones[zo_left->zo_idx]) >> (order+1);
 297                                 zh->zh_maps[zo_left->zo_idx][order-order_start][diff>>3] |=
 298                                                 (1 << (diff & 0x7));
 299                                 *ptr++ = zh->zh_seqno[zo_left->zo_idx];
 300                                 *ptr++ = size - 2*sizeof(ber_len_t);
 301                                 LDAP_LIST_INSERT_HEAD(
 302                                                 &zh->zh_free[j-1-order_start], zo_right, zo_link);
 303                                 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_left, zo_link);
 304                                 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
 305                                 Debug(LDAP_DEBUG_NONE,
 306                                         "slap_zn_malloc: returning 0x%x, 0x%x\n",
 307                                         ptr, (int)ptr>>(zh->zh_zoneorder+1), 0);
 308                                 return((void*)ptr);
 309                         } else {
 310                                 LDAP_LIST_INSERT_HEAD(
 311                                                 &zh->zh_free[j-1-order_start], zo_right, zo_link);
 312                                 LDAP_LIST_INSERT_HEAD(
 313                                                 &zh->zh_free[j-1-order_start], zo_left, zo_link);
 314                         }
 315                 }
 316                 assert(0);
 317         } else {
 318
 319                 if ( zh->zh_maxzones < zh->zh_numzones + zh->zh_deltazones ) {
 320                         ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
 321                         Debug( LDAP_DEBUG_TRACE,
 322                                 "slap_zn_malloc of %lu bytes failed, using ch_malloc\n",
 323                                 (long)size, 0, 0);
 324                         Debug(LDAP_DEBUG_NONE,
 325                                 "slap_zn_malloc: returning 0x%x, 0x%x\n",
 326                                 ptr, (int)ptr>>(zh->zh_zoneorder+1), 0);
 327                         return (void*)ch_malloc(size);
 328                 }
 329
 330                 for (i = zh->zh_numzones; i < zh->zh_numzones+zh->zh_deltazones; i++) {
 331                         zh->zh_zones[i] = mmap(0, zh->zh_zonesize, PROT_READ | PROT_WRITE,
 332                                                                 MAP_PRIVATE, zh->zh_fd, 0);
 333                         zh->zh_maps[i] = (unsigned char **)
 334                                                 ch_malloc((zh->zh_zoneorder - order_start + 1) *
 335                                                 sizeof(unsigned char *));
 336                         for (j = 0; j < zh->zh_zoneorder-order_start+1; j++) {
 337                                 int shiftamt = order_start + 1 + j;
 338                                 int nummaps = zh->zh_zonesize >> shiftamt;
 339                                 assert(nummaps);
 340                                 nummaps /= 8;
 341                                 if (!nummaps) nummaps = 1;
 342                                 zh->zh_maps[i][j] = (unsigned char *)ch_malloc(nummaps);
 343                                 memset(zh->zh_maps[i][j], 0, nummaps);
 344                         }
 345
 346                         if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
 347                                 slap_replenish_zopool(zh);
 348                         }
 349                         zo = LDAP_LIST_FIRST(&zh->zh_zopool);
 350                         LDAP_LIST_REMOVE(zo, zo_link);
 351                         zo->zo_ptr = zh->zh_zones[i];
 352                         zo->zo_idx = i;
 353                         LDAP_LIST_INSERT_HEAD(&zh->
 354                                                 zh_free[zh->zh_zoneorder-order_start],zo,zo_link);
 355
 356                         if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
 357                                 slap_replenish_zopool(zh);
 358                         }
 359                         zo = LDAP_LIST_FIRST(&zh->zh_zopool);
 360                         LDAP_LIST_REMOVE(zo, zo_link);
 361                         zo->zo_ptr = zh->zh_zones[i];
 362                         zo->zo_siz = zh->zh_zonesize;
 363                         zo->zo_idx = i;
 364                         avl_insert(&zh->zh_zonetree, zo, slap_zone_cmp, avl_dup_error);
 365                 }
 366                 zh->zh_numzones += zh->zh_deltazones;
 367                 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
 368                 goto retry;
 369         }
 370 }
 371
 372 void *
 373 slap_zn_calloc( ber_len_t n, ber_len_t size, void *ctx )
 374 {
 375         void *new;
 376
 377         new = slap_zn_malloc( n*size, ctx );
 378         if ( new ) {
 379                 memset( new, 0, n*size );
 380         }
 381         return new;
 382 }
 383
 384 void *
 385 slap_zn_realloc(void *ptr, ber_len_t size, void *ctx)
 386 {
 387         struct zone_heap *zh = ctx;
 388         int pad = 2*sizeof(int)-1, pad_shift;
 389         int order_start = -1, order = -1;
 390         struct zone_object zoi, *zoo;
 391         ber_len_t *p = (ber_len_t *)ptr, *new;
 392         unsigned long diff;
 393         int i;
 394         void *newptr = NULL;
 395         struct zone_heap *zone = NULL;
 396
 397         Debug(LDAP_DEBUG_NONE,
 398                 "--> slap_zn_realloc: ptr=0x%x, size=%d\n", ptr, size, 0);
 399
 400         if (ptr == NULL)
 401                 return slap_zn_malloc(size, zh);
 402
 403         zoi.zo_ptr = p;
 404         zoi.zo_idx = -1;
 405
 406         if (zh) {
 407                 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
 408                 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
 409                 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
 410         }
 411
 412         /* Not our memory? */
 413         if (!zoo) {
 414                 /* duplicate of realloc behavior, oh well */
 415                 new = ber_memrealloc_x(ptr, size, NULL);
 416                 if (new) {
 417                         return new;
 418                 }
 419                 Debug(LDAP_DEBUG_ANY, "ch_realloc of %lu bytes failed\n",
 420                                 (long) size, 0, 0);
 421                 assert(0);
 422                 exit( EXIT_FAILURE );
 423         }
 424
 425         assert(zoo->zo_idx != -1);
 426
 427         zone = zh->zh_zones[zoo->zo_idx];
 428
 429         if (size == 0) {
 430                 slap_zn_free(ptr, zh);
 431                 return NULL;
 432         }
 433
 434         newptr = slap_zn_malloc(size, zh);
 435         if (size < p[-1]) {
 436                 AC_MEMCPY(newptr, ptr, size);
 437         } else {
 438                 AC_MEMCPY(newptr, ptr, p[-1]);
 439         }
 440         slap_zn_free(ptr, zh);
 441         return newptr;
 442 }
 443
 444 void
 445 slap_zn_free(void *ptr, void *ctx)
 446 {
 447         struct zone_heap *zh = ctx;
 448         int size, size_shift, order_size;
 449         int pad = 2*sizeof(int)-1, pad_shift;
 450         ber_len_t *p = (ber_len_t *)ptr, *tmpp;
 451         int order_start = -1, order = -1;
 452         struct zone_object zoi, *zoo, *zo;
 453         unsigned long diff;
 454         int i, k, inserted = 0, idx;
 455         struct zone_heap *zone = NULL;
 456
 457         zoi.zo_ptr = p;
 458         zoi.zo_idx = -1;
 459
 460         Debug(LDAP_DEBUG_NONE, "--> slap_zn_free: ptr=0x%x\n", ptr, 0, 0);
 461
 462         if (zh) {
 463                 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
 464                 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
 465                 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
 466         }
 467
 468         if (!zoo) {
 469                 ber_memfree_x(ptr, NULL);
 470         } else {
 471                 idx = zoo->zo_idx;
 472                 assert(idx != -1);
 473                 zone = zh->zh_zones[idx];
 474
 475                 size = *(--p);
 476                 size_shift = size + 2*sizeof(ber_len_t) - 1;
 477                 do {
 478                         order++;
 479                 } while (size_shift >>= 1);
 480
 481                 pad_shift = pad - 1;
 482                 do {
 483                         order_start++;
 484                 } while (pad_shift >>= 1);
 485
 486                 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
 487                 for (i = order, tmpp = p; i <= zh->zh_zoneorder; i++) {
 488                         order_size = 1 << (i+1);
 489                         diff = (unsigned long)((char*)tmpp - (char*)zone) >> (i+1);
 490                         zh->zh_maps[idx][i-order_start][diff>>3] &= (~(1 << (diff & 0x7)));
 491                         if (diff == ((diff>>1)<<1)) {
 492                                 if (!(zh->zh_maps[idx][i-order_start][(diff+1)>>3] &
 493                                                 (1<<((diff+1)&0x7)))) {
 494                                         zo = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
 495                                         while (zo) {
 496                                                 if ((char*)zo->zo_ptr == (char*)tmpp) {
 497                                                         LDAP_LIST_REMOVE( zo, zo_link );
 498                                                 } else if ((char*)zo->zo_ptr ==
 499                                                                 (char*)tmpp + order_size) {
 500                                                         LDAP_LIST_REMOVE(zo, zo_link);
 501                                                         break;
 502                                                 }
 503                                                 zo = LDAP_LIST_NEXT(zo, zo_link);
 504                                         }
 505                                         if (zo) {
 506                                                 if (i < zh->zh_zoneorder) {
 507                                                         inserted = 1;
 508                                                         zo->zo_ptr = tmpp;
 509                                                         Debug(LDAP_DEBUG_NONE,
 510                                                                 "slap_zn_free: merging 0x%x\n",
 511                                                                 zo->zo_ptr, 0, 0);
 512                                                         LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start+1],
 513                                                                         zo, zo_link);
 514                                                 }
 515                                                 continue;
 516                                         } else {
 517                                                 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
 518                                                         slap_replenish_zopool(zh);
 519                                                 }
 520                                                 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
 521                                                 LDAP_LIST_REMOVE(zo, zo_link);
 522                                                 zo->zo_ptr = tmpp;
 523                                                 Debug(LDAP_DEBUG_NONE,
 524                                                         "slap_zn_free: merging 0x%x\n",
 525                                                         zo->zo_ptr, 0, 0);
 526                                                 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
 527                                                                 zo, zo_link);
 528                                                 break;
 529
 530                                                 Debug(LDAP_DEBUG_ANY, "slap_zn_free: "
 531                                                         "free object not found while bit is clear.\n",
 532                                                         0, 0, 0);
 533                                                 assert(zo);
 534
 535                                         }
 536                                 } else {
 537                                         if (!inserted) {
 538                                                 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
 539                                                         slap_replenish_zopool(zh);
 540                                                 }
 541                                                 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
 542                                                 LDAP_LIST_REMOVE(zo, zo_link);
 543                                                 zo->zo_ptr = tmpp;
 544                                                 Debug(LDAP_DEBUG_NONE,
 545                                                         "slap_zn_free: merging 0x%x\n",
 546                                                         zo->zo_ptr, 0, 0);
 547                                                 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
 548                                                                 zo, zo_link);
 549                                         }
 550                                         break;
 551                                 }
 552                         } else {
 553                                 if (!(zh->zh_maps[idx][i-order_start][(diff-1)>>3] &
 554                                                 (1<<((diff-1)&0x7)))) {
 555                                         zo = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
 556                                         while (zo) {
 557                                                 if ((char*)zo->zo_ptr == (char*)tmpp) {
 558                                                         LDAP_LIST_REMOVE(zo, zo_link);
 559                                                 } else if ((char*)tmpp == zo->zo_ptr + order_size) {
 560                                                         LDAP_LIST_REMOVE(zo, zo_link);
 561                                                         tmpp = zo->zo_ptr;
 562                                                         break;
 563                                                 }
 564                                                 zo = LDAP_LIST_NEXT(zo, zo_link);
 565                                         }
 566                                         if (zo) {
 567                                                 if (i < zh->zh_zoneorder) {
 568                                                         inserted = 1;
 569                                                         Debug(LDAP_DEBUG_NONE,
 570                                                                 "slap_zn_free: merging 0x%x\n",
 571                                                                 zo->zo_ptr, 0, 0);
 572                                                         LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start+1],
 573                                                                         zo, zo_link);
 574                                                         continue;
 575                                                 }
 576                                         } else {
 577                                                 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
 578                                                         slap_replenish_zopool(zh);
 579                                                 }
 580                                                 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
 581                                                 LDAP_LIST_REMOVE(zo, zo_link);
 582                                                 zo->zo_ptr = tmpp;
 583                                                 Debug(LDAP_DEBUG_NONE,
 584                                                         "slap_zn_free: merging 0x%x\n",
 585                                                         zo->zo_ptr, 0, 0);
 586                                                 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
 587                                                                 zo, zo_link);
 588                                                 break;
 589
 590                                                 Debug(LDAP_DEBUG_ANY, "slap_zn_free: "
 591                                                         "free object not found while bit is clear.\n",
 592                                                         0, 0, 0 );
 593                                                 assert( zo );
 594
 595                                         }
 596                                 } else {
 597                                         if ( !inserted ) {
 598                                                 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
 599                                                         slap_replenish_zopool(zh);
 600                                                 }
 601                                                 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
 602                                                 LDAP_LIST_REMOVE(zo, zo_link);
 603                                                 zo->zo_ptr = tmpp;
 604                                                 Debug(LDAP_DEBUG_NONE,
 605                                                         "slap_zn_free: merging 0x%x\n",
 606                                                         zo->zo_ptr, 0, 0);
 607                                                 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
 608                                                                 zo, zo_link);
 609                                         }
 610                                         break;
 611                                 }
 612                         }
 613                 }
 614                 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
 615         }
 616 }
 617
 618 static int
 619 slap_zone_cmp(const void *v1, const void *v2)
 620 {
 621         const struct zone_object *zo1 = v1;
 622         const struct zone_object *zo2 = v2;
 623         char *ptr1;
 624         char *ptr2;
 625         ber_len_t zpad;
 626
 627         zpad = zo2->zo_siz - 1;
 628         ptr1 = (char*)(((unsigned long)zo1->zo_ptr + zpad) & ~zpad);
 629         ptr2 = (char*)zo2->zo_ptr + ((char*)ptr1 - (char*)zo1->zo_ptr);
 630         ptr2 = (char*)(((unsigned long)ptr2 + zpad) & ~zpad);
 631         return (int)((char*)ptr1 - (char*)ptr2);
 632 }
 633
 634 void *
 635 slap_replenish_zopool(
 636         void *ctx
 637 )
 638 {
 639         struct zone_heap* zh = ctx;
 640         struct zone_object *zo_block;
 641         int i;
 642
 643         zo_block = (struct zone_object *)ch_malloc(
 644                                         SLAP_ZONE_ZOBLOCK * sizeof(struct zone_object));
 645
 646         if ( zo_block == NULL ) {
 647                 return NULL;
 648         }
 649
 650         zo_block[0].zo_blockhead = 1;
 651         LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, &zo_block[0], zo_link);
 652         for (i = 1; i < SLAP_ZONE_ZOBLOCK; i++) {
 653                 zo_block[i].zo_blockhead = 0;
 654                 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, &zo_block[i], zo_link );
 655         }
 656
 657         return zo_block;
 658 }
 659 #endif /* SLAP_ZONE_ALLOC */