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