Back to index

openldap  2.4.31
zn_malloc.c
Go to the documentation of this file.
00001 /* zn_malloc.c - zone-based malloc routines */
00002 /* $OpenLDAP$*/
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 2003-2012 The OpenLDAP Foundation.
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted only as authorized by the OpenLDAP
00010  * Public License.
00011  *
00012  * A copy of this license is available in the file LICENSE in the
00013  * top-level directory of the distribution or, alternatively, at
00014  * <http://www.OpenLDAP.org/license.html>.
00015  */
00016 /* Portions Copyright 2004 IBM Corporation
00017  * All rights reserved.
00018  * Redistribution and use in source and binary forms, with or without
00019  * modification, are permitted only as authorized by the OpenLDAP
00020  * Public License.
00021  */
00022 /* ACKNOWLEDGEMENTS
00023  * This work originally developed by Jong-Hyuk Choi for inclusion in
00024  * OpenLDAP Software.
00025  */
00026 
00027 #include "portable.h"
00028 
00029 #include <stdio.h>
00030 #include <ac/string.h>
00031 #include <sys/types.h>
00032 #include <fcntl.h>
00033 
00034 #include "slap.h"
00035 
00036 #ifdef SLAP_ZONE_ALLOC
00037 
00038 #include <sys/mman.h>
00039 
00040 static int slap_zone_cmp(const void *v1, const void *v2);
00041 void * slap_replenish_zopool(void *ctx);
00042 
00043 static void
00044 slap_zo_release(void *data)
00045 {
00046        struct zone_object *zo = (struct zone_object *)data;
00047        ch_free( zo );
00048 }
00049 
00050 void
00051 slap_zn_mem_destroy(
00052        void *ctx
00053 )
00054 {
00055        struct zone_heap *zh = ctx;
00056        int pad = 2*sizeof(int)-1, pad_shift;
00057        int order_start = -1, i, j;
00058        struct zone_object *zo;
00059 
00060        pad_shift = pad - 1;
00061        do {
00062               order_start++;
00063        } while (pad_shift >>= 1);
00064 
00065        ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
00066        for (i = 0; i < zh->zh_zoneorder - order_start + 1; i++) {
00067               zo = LDAP_LIST_FIRST(&zh->zh_free[i]);
00068               while (zo) {
00069                      struct zone_object *zo_tmp = zo;
00070                      zo = LDAP_LIST_NEXT(zo, zo_link);
00071                      LDAP_LIST_REMOVE(zo_tmp, zo_link);
00072                      LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_tmp, zo_link);
00073               }
00074        }
00075        ch_free(zh->zh_free);
00076 
00077        for (i = 0; i < zh->zh_numzones; i++) {
00078               for (j = 0; j < zh->zh_zoneorder - order_start + 1; j++) {
00079                      ch_free(zh->zh_maps[i][j]);
00080               }
00081               ch_free(zh->zh_maps[i]);
00082               munmap(zh->zh_zones[i], zh->zh_zonesize);
00083               ldap_pvt_thread_rdwr_destroy(&zh->zh_znlock[i]);
00084        }
00085        ch_free(zh->zh_maps);
00086        ch_free(zh->zh_zones);
00087        ch_free(zh->zh_seqno);
00088        ch_free(zh->zh_znlock);
00089 
00090        avl_free(zh->zh_zonetree, slap_zo_release);
00091 
00092        zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00093        while (zo) {
00094               struct zone_object *zo_tmp = zo;
00095               zo = LDAP_LIST_NEXT(zo, zo_link);
00096               if (!zo_tmp->zo_blockhead) {
00097                      LDAP_LIST_REMOVE(zo_tmp, zo_link);
00098               }
00099        }
00100        zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00101        while (zo) {
00102               struct zone_object *zo_tmp = zo;
00103               zo = LDAP_LIST_NEXT(zo, zo_link);
00104               ch_free(zo_tmp);
00105        }
00106        ldap_pvt_thread_mutex_unlock(&zh->zh_mutex);
00107        ldap_pvt_thread_rdwr_destroy(&zh->zh_lock);
00108        ldap_pvt_thread_mutex_destroy(&zh->zh_mutex);
00109        ch_free(zh);
00110 }
00111 
00112 void *
00113 slap_zn_mem_create(
00114        ber_len_t initsize,
00115        ber_len_t maxsize,
00116        ber_len_t deltasize,
00117        ber_len_t zonesize
00118 )
00119 {
00120        struct zone_heap *zh = NULL;
00121        ber_len_t zpad;
00122        int pad = 2*sizeof(int)-1, pad_shift;
00123        int size_shift;
00124        int order = -1, order_start = -1, order_end = -1;
00125        int i, j;
00126        struct zone_object *zo;
00127 
00128        Debug(LDAP_DEBUG_NONE,
00129               "--> slap_zn_mem_create: initsize=%d, maxsize=%d\n",
00130               initsize, maxsize, 0);
00131        Debug(LDAP_DEBUG_NONE,
00132               "++> slap_zn_mem_create: deltasize=%d, zonesize=%d\n",
00133               deltasize, zonesize, 0);
00134 
00135        zh = (struct zone_heap *)ch_calloc(1, sizeof(struct zone_heap));
00136 
00137        zh->zh_fd = open("/dev/zero", O_RDWR);
00138 
00139        if ( zonesize ) {
00140               zh->zh_zonesize = zonesize;
00141        } else {
00142               zh->zh_zonesize = SLAP_ZONE_SIZE;
00143        }
00144 
00145        zpad = zh->zh_zonesize - 1;
00146        zh->zh_numzones = ((initsize + zpad) & ~zpad) / zh->zh_zonesize;
00147 
00148        if ( maxsize && maxsize >= initsize ) {
00149               zh->zh_maxzones = ((maxsize + zpad) & ~zpad) / zh->zh_zonesize;
00150        } else {
00151               zh->zh_maxzones = ((initsize + zpad) & ~zpad) / zh->zh_zonesize;
00152        }
00153 
00154        if ( deltasize ) {
00155               zh->zh_deltazones = ((deltasize + zpad) & ~zpad) / zh->zh_zonesize;
00156        } else {
00157               zh->zh_deltazones = ((SLAP_ZONE_DELTA+zpad) & ~zpad) / zh->zh_zonesize;
00158        }
00159 
00160        size_shift = zh->zh_zonesize - 1;
00161        do {
00162               order_end++;
00163        } while (size_shift >>= 1);
00164 
00165        pad_shift = pad - 1;
00166        do {
00167               order_start++;
00168        } while (pad_shift >>= 1);
00169 
00170        order = order_end - order_start + 1;
00171 
00172        zh->zh_zones = (void **)ch_malloc(zh->zh_maxzones * sizeof(void*));
00173        zh->zh_znlock = (ldap_pvt_thread_rdwr_t *)ch_malloc(
00174                                           zh->zh_maxzones * sizeof(ldap_pvt_thread_rdwr_t *));
00175        zh->zh_maps = (unsigned char ***)ch_malloc(
00176                                    zh->zh_maxzones * sizeof(unsigned char**));
00177 
00178        zh->zh_zoneorder = order_end;
00179        zh->zh_free = (struct zh_freelist *)
00180                                    ch_malloc(order * sizeof(struct zh_freelist));
00181        zh->zh_seqno = (unsigned long *)ch_calloc(zh->zh_maxzones,
00182                                                                              sizeof(unsigned long));
00183        for (i = 0; i < order; i++) {
00184               LDAP_LIST_INIT(&zh->zh_free[i]);
00185        }
00186        LDAP_LIST_INIT(&zh->zh_zopool);
00187 
00188        for (i = 0; i < zh->zh_numzones; i++) {
00189               zh->zh_zones[i] = mmap(0, zh->zh_zonesize, PROT_READ | PROT_WRITE,
00190                                                  MAP_PRIVATE, zh->zh_fd, 0);
00191               zh->zh_maps[i] = (unsigned char **)
00192                                    ch_malloc(order * sizeof(unsigned char *));
00193               for (j = 0; j < order; j++) {
00194                      int shiftamt = order_start + 1 + j;
00195                      int nummaps = zh->zh_zonesize >> shiftamt;
00196                      assert(nummaps);
00197                      nummaps >>= 3;
00198                      if (!nummaps) nummaps = 1;
00199                      zh->zh_maps[i][j] = (unsigned char *)ch_malloc(nummaps);
00200                      memset(zh->zh_maps[i][j], 0, nummaps);
00201               }
00202 
00203               if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
00204                      slap_replenish_zopool(zh);
00205               }
00206               zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00207               LDAP_LIST_REMOVE(zo, zo_link);
00208               zo->zo_ptr = zh->zh_zones[i];
00209               zo->zo_idx = i;
00210               LDAP_LIST_INSERT_HEAD(&zh->zh_free[order-1], zo, zo_link);
00211 
00212               if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
00213                      slap_replenish_zopool(zh);
00214               }
00215               zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00216               LDAP_LIST_REMOVE(zo, zo_link);
00217               zo->zo_ptr = zh->zh_zones[i];
00218               zo->zo_siz = zh->zh_zonesize;
00219               zo->zo_idx = i;
00220               avl_insert(&zh->zh_zonetree, zo, slap_zone_cmp, avl_dup_error);
00221               ldap_pvt_thread_rdwr_init(&zh->zh_znlock[i]);
00222        }
00223 
00224        LDAP_STAILQ_INIT(&zh->zh_latency_history_queue);
00225        ldap_pvt_thread_mutex_init(&zh->zh_mutex);
00226        ldap_pvt_thread_rdwr_init(&zh->zh_lock);
00227 
00228        return zh;
00229 }
00230 
00231 void *
00232 slap_zn_malloc(
00233     ber_len_t size,
00234        void *ctx
00235 )
00236 {
00237        struct zone_heap *zh = ctx;
00238        ber_len_t size_shift;
00239        int pad = 2*sizeof(int)-1, pad_shift;
00240        int order = -1, order_start = -1;
00241        struct zone_object *zo, *zo_new, *zo_left, *zo_right;
00242        ber_len_t *ptr, *new;
00243        int idx;
00244        unsigned long diff;
00245        int i, j, k;
00246 
00247        Debug(LDAP_DEBUG_NONE,
00248               "--> slap_zn_malloc: size=%d\n", size, 0, 0);
00249 
00250        if (!zh) return ber_memalloc_x(size, NULL);
00251 
00252        /* round up to doubleword boundary */
00253        size += 2*sizeof(ber_len_t) + pad;
00254        size &= ~pad;
00255 
00256        size_shift = size - 1;
00257        do {
00258               order++;
00259        } while (size_shift >>= 1);
00260 
00261        pad_shift = pad - 1;
00262        do {
00263               order_start++;
00264        } while (pad_shift >>= 1);
00265 
00266 retry:
00267 
00268        ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
00269        for (i = order; i <= zh->zh_zoneorder &&
00270                      LDAP_LIST_EMPTY(&zh->zh_free[i-order_start]); i++);
00271 
00272        if (i == order) {
00273               zo_new = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
00274               LDAP_LIST_REMOVE(zo_new, zo_link);
00275               ptr = zo_new->zo_ptr;
00276               idx = zo_new->zo_idx;
00277               diff = (unsigned long)((char*)ptr -
00278                             (char*)zh->zh_zones[idx]) >> (order + 1);
00279               zh->zh_maps[idx][order-order_start][diff>>3] |= (1 << (diff & 0x7));
00280               *ptr++ = zh->zh_seqno[idx];
00281               *ptr++ = size - 2*sizeof(ber_len_t);
00282               zo_new->zo_ptr = NULL;
00283               zo_new->zo_idx = -1;
00284               LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_new, zo_link);
00285               ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00286               Debug(LDAP_DEBUG_NONE, "slap_zn_malloc: returning 0x%x, 0x%x\n",
00287                             ptr, (int)ptr>>(zh->zh_zoneorder+1), 0);
00288               return((void*)ptr);
00289        } else if (i <= zh->zh_zoneorder) {
00290               for (j = i; j > order; j--) {
00291                      zo_left = LDAP_LIST_FIRST(&zh->zh_free[j-order_start]);
00292                      LDAP_LIST_REMOVE(zo_left, zo_link);
00293                      if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
00294                             slap_replenish_zopool(zh);
00295                      }
00296                      zo_right = LDAP_LIST_FIRST(&zh->zh_zopool);
00297                      LDAP_LIST_REMOVE(zo_right, zo_link);
00298                      zo_right->zo_ptr = zo_left->zo_ptr + (1 << j);
00299                      zo_right->zo_idx = zo_left->zo_idx;
00300                      Debug(LDAP_DEBUG_NONE,
00301                             "slap_zn_malloc: split (left=0x%x, right=0x%x)\n",
00302                             zo_left->zo_ptr, zo_right->zo_ptr, 0);
00303                      if (j == order + 1) {
00304                             ptr = zo_left->zo_ptr;
00305                             diff = (unsigned long)((char*)ptr -
00306                                           (char*)zh->zh_zones[zo_left->zo_idx]) >> (order+1);
00307                             zh->zh_maps[zo_left->zo_idx][order-order_start][diff>>3] |=
00308                                           (1 << (diff & 0x7));
00309                             *ptr++ = zh->zh_seqno[zo_left->zo_idx];
00310                             *ptr++ = size - 2*sizeof(ber_len_t);
00311                             LDAP_LIST_INSERT_HEAD(
00312                                           &zh->zh_free[j-1-order_start], zo_right, zo_link);
00313                             LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_left, zo_link);
00314                             ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00315                             Debug(LDAP_DEBUG_NONE,
00316                                    "slap_zn_malloc: returning 0x%x, 0x%x\n",
00317                                    ptr, (int)ptr>>(zh->zh_zoneorder+1), 0);
00318                             return((void*)ptr);
00319                      } else {
00320                             LDAP_LIST_INSERT_HEAD(
00321                                           &zh->zh_free[j-1-order_start], zo_right, zo_link);
00322                             LDAP_LIST_INSERT_HEAD(
00323                                           &zh->zh_free[j-1-order_start], zo_left, zo_link);
00324                      }
00325               }
00326               assert(0);
00327        } else {
00328 
00329               if ( zh->zh_maxzones < zh->zh_numzones + zh->zh_deltazones ) {
00330                      ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00331                      Debug( LDAP_DEBUG_TRACE,
00332                             "zn_malloc %lu: ch_malloc\n",
00333                             (long)size, 0, 0);
00334                      Debug(LDAP_DEBUG_NONE,
00335                             "slap_zn_malloc: returning 0x%x, 0x%x\n",
00336                             ptr, (int)ptr>>(zh->zh_zoneorder+1), 0);
00337                      return (void*)ch_malloc(size);
00338               }
00339 
00340               for (i = zh->zh_numzones; i < zh->zh_numzones+zh->zh_deltazones; i++) {
00341                      zh->zh_zones[i] = mmap(0, zh->zh_zonesize, PROT_READ | PROT_WRITE,
00342                                                         MAP_PRIVATE, zh->zh_fd, 0);
00343                      zh->zh_maps[i] = (unsigned char **)
00344                                           ch_malloc((zh->zh_zoneorder - order_start + 1) *
00345                                           sizeof(unsigned char *));
00346                      for (j = 0; j < zh->zh_zoneorder-order_start+1; j++) {
00347                             int shiftamt = order_start + 1 + j;
00348                             int nummaps = zh->zh_zonesize >> shiftamt;
00349                             assert(nummaps);
00350                             nummaps >>= 3;
00351                             if (!nummaps) nummaps = 1;
00352                             zh->zh_maps[i][j] = (unsigned char *)ch_malloc(nummaps);
00353                             memset(zh->zh_maps[i][j], 0, nummaps);
00354                      }
00355        
00356                      if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
00357                             slap_replenish_zopool(zh);
00358                      }
00359                      zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00360                      LDAP_LIST_REMOVE(zo, zo_link);
00361                      zo->zo_ptr = zh->zh_zones[i];
00362                      zo->zo_idx = i;
00363                      LDAP_LIST_INSERT_HEAD(&zh->
00364                                           zh_free[zh->zh_zoneorder-order_start],zo,zo_link);
00365        
00366                      if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
00367                             slap_replenish_zopool(zh);
00368                      }
00369                      zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00370                      LDAP_LIST_REMOVE(zo, zo_link);
00371                      zo->zo_ptr = zh->zh_zones[i];
00372                      zo->zo_siz = zh->zh_zonesize;
00373                      zo->zo_idx = i;
00374                      avl_insert(&zh->zh_zonetree, zo, slap_zone_cmp, avl_dup_error);
00375                      ldap_pvt_thread_rdwr_init(&zh->zh_znlock[i]);
00376               }
00377               zh->zh_numzones += zh->zh_deltazones;
00378               ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00379               goto retry;
00380        }
00381 }
00382 
00383 void *
00384 slap_zn_calloc( ber_len_t n, ber_len_t size, void *ctx )
00385 {
00386        void *new;
00387 
00388        new = slap_zn_malloc( n*size, ctx );
00389        if ( new ) {
00390               memset( new, 0, n*size );
00391        }
00392        return new;
00393 }
00394 
00395 void *
00396 slap_zn_realloc(void *ptr, ber_len_t size, void *ctx)
00397 {
00398        struct zone_heap *zh = ctx;
00399        int pad = 2*sizeof(int)-1, pad_shift;
00400        int order_start = -1, order = -1;
00401        struct zone_object zoi, *zoo;
00402        ber_len_t *p = (ber_len_t *)ptr, *new;
00403        unsigned long diff;
00404        int i;
00405        void *newptr = NULL;
00406        struct zone_heap *zone = NULL;
00407 
00408        Debug(LDAP_DEBUG_NONE,
00409               "--> slap_zn_realloc: ptr=0x%x, size=%d\n", ptr, size, 0);
00410 
00411        if (ptr == NULL)
00412               return slap_zn_malloc(size, zh);
00413 
00414        zoi.zo_ptr = p;
00415        zoi.zo_idx = -1;
00416 
00417        if (zh) {
00418               ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
00419               zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
00420               ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00421        }
00422 
00423        /* Not our memory? */
00424        if (!zoo) {
00425               /* duplicate of realloc behavior, oh well */
00426               new = ber_memrealloc_x(ptr, size, NULL);
00427               if (new) {
00428                      return new;
00429               }
00430               Debug(LDAP_DEBUG_ANY, "ch_realloc of %lu bytes failed\n",
00431                             (long) size, 0, 0);
00432               assert(0);
00433               exit( EXIT_FAILURE );
00434        }
00435 
00436        assert(zoo->zo_idx != -1);  
00437 
00438        zone = zh->zh_zones[zoo->zo_idx];
00439 
00440        if (size == 0) {
00441               slap_zn_free(ptr, zh);
00442               return NULL;
00443        }
00444 
00445        newptr = slap_zn_malloc(size, zh);
00446        if (size < p[-1]) {
00447               AC_MEMCPY(newptr, ptr, size);
00448        } else {
00449               AC_MEMCPY(newptr, ptr, p[-1]);
00450        }
00451        slap_zn_free(ptr, zh);
00452        return newptr;
00453 }
00454 
00455 void
00456 slap_zn_free(void *ptr, void *ctx)
00457 {
00458        struct zone_heap *zh = ctx;
00459        int size, size_shift, order_size;
00460        int pad = 2*sizeof(int)-1, pad_shift;
00461        ber_len_t *p = (ber_len_t *)ptr, *tmpp;
00462        int order_start = -1, order = -1;
00463        struct zone_object zoi, *zoo, *zo;
00464        unsigned long diff;
00465        int i, k, inserted = 0, idx;
00466        struct zone_heap *zone = NULL;
00467 
00468        zoi.zo_ptr = p;
00469        zoi.zo_idx = -1;
00470 
00471        Debug(LDAP_DEBUG_NONE, "--> slap_zn_free: ptr=0x%x\n", ptr, 0, 0);
00472 
00473        if (zh) {
00474               ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
00475               zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
00476               ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00477        }
00478 
00479        if (!zoo) {
00480               ber_memfree_x(ptr, NULL);
00481        } else {
00482               idx = zoo->zo_idx;
00483               assert(idx != -1);
00484               zone = zh->zh_zones[idx];
00485 
00486               size = *(--p);
00487               size_shift = size + 2*sizeof(ber_len_t) - 1;
00488               do {
00489                      order++;
00490               } while (size_shift >>= 1);
00491 
00492               pad_shift = pad - 1;
00493               do {
00494                      order_start++;
00495               } while (pad_shift >>= 1);
00496 
00497               ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
00498               for (i = order, tmpp = p; i <= zh->zh_zoneorder; i++) {
00499                      order_size = 1 << (i+1);
00500                      diff = (unsigned long)((char*)tmpp - (char*)zone) >> (i+1);
00501                      zh->zh_maps[idx][i-order_start][diff>>3] &= (~(1 << (diff & 0x7)));
00502                      if (diff == ((diff>>1)<<1)) {
00503                             if (!(zh->zh_maps[idx][i-order_start][(diff+1)>>3] &
00504                                           (1<<((diff+1)&0x7)))) {
00505                                    zo = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
00506                                    while (zo) {
00507                                           if ((char*)zo->zo_ptr == (char*)tmpp) {
00508                                                  LDAP_LIST_REMOVE( zo, zo_link );
00509                                           } else if ((char*)zo->zo_ptr ==
00510                                                         (char*)tmpp + order_size) {
00511                                                  LDAP_LIST_REMOVE(zo, zo_link);
00512                                                  break;
00513                                           }
00514                                           zo = LDAP_LIST_NEXT(zo, zo_link);
00515                                    }
00516                                    if (zo) {
00517                                           if (i < zh->zh_zoneorder) {
00518                                                  inserted = 1;
00519                                                  zo->zo_ptr = tmpp;
00520                                                  Debug(LDAP_DEBUG_NONE,
00521                                                         "slap_zn_free: merging 0x%x\n",
00522                                                         zo->zo_ptr, 0, 0);
00523                                                  LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start+1],
00524                                                                zo, zo_link);
00525                                           }
00526                                           continue;
00527                                    } else {
00528                                           if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
00529                                                  slap_replenish_zopool(zh);
00530                                           }
00531                                           zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00532                                           LDAP_LIST_REMOVE(zo, zo_link);
00533                                           zo->zo_ptr = tmpp;
00534                                           zo->zo_idx = idx;
00535                                           Debug(LDAP_DEBUG_NONE,
00536                                                  "slap_zn_free: merging 0x%x\n",
00537                                                  zo->zo_ptr, 0, 0);
00538                                           LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
00539                                                         zo, zo_link);
00540                                           break;
00541 
00542                                           Debug(LDAP_DEBUG_ANY, "slap_zn_free: "
00543                                                  "free object not found while bit is clear.\n",
00544                                                  0, 0, 0);
00545                                           assert(zo != NULL);
00546 
00547                                    }
00548                             } else {
00549                                    if (!inserted) {
00550                                           if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
00551                                                  slap_replenish_zopool(zh);
00552                                           }
00553                                           zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00554                                           LDAP_LIST_REMOVE(zo, zo_link);
00555                                           zo->zo_ptr = tmpp;
00556                                           zo->zo_idx = idx;
00557                                           Debug(LDAP_DEBUG_NONE,
00558                                                  "slap_zn_free: merging 0x%x\n",
00559                                                  zo->zo_ptr, 0, 0);
00560                                           LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
00561                                                         zo, zo_link);
00562                                    }
00563                                    break;
00564                             }
00565                      } else {
00566                             if (!(zh->zh_maps[idx][i-order_start][(diff-1)>>3] &
00567                                           (1<<((diff-1)&0x7)))) {
00568                                    zo = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
00569                                    while (zo) {
00570                                           if ((char*)zo->zo_ptr == (char*)tmpp) {
00571                                                  LDAP_LIST_REMOVE(zo, zo_link);
00572                                           } else if ((char*)tmpp == zo->zo_ptr + order_size) {
00573                                                  LDAP_LIST_REMOVE(zo, zo_link);
00574                                                  tmpp = zo->zo_ptr;
00575                                                  break;
00576                                           }
00577                                           zo = LDAP_LIST_NEXT(zo, zo_link);
00578                                    }
00579                                    if (zo) {
00580                                           if (i < zh->zh_zoneorder) {
00581                                                  inserted = 1;
00582                                                  Debug(LDAP_DEBUG_NONE,
00583                                                         "slap_zn_free: merging 0x%x\n",
00584                                                         zo->zo_ptr, 0, 0);
00585                                                  LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start+1],
00586                                                                zo, zo_link);
00587                                                  continue;
00588                                           }
00589                                    } else {
00590                                           if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
00591                                                  slap_replenish_zopool(zh);
00592                                           }
00593                                           zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00594                                           LDAP_LIST_REMOVE(zo, zo_link);
00595                                           zo->zo_ptr = tmpp;
00596                                           zo->zo_idx = idx;
00597                                           Debug(LDAP_DEBUG_NONE,
00598                                                  "slap_zn_free: merging 0x%x\n",
00599                                                  zo->zo_ptr, 0, 0);
00600                                           LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
00601                                                         zo, zo_link);
00602                                           break;
00603 
00604                                           Debug(LDAP_DEBUG_ANY, "slap_zn_free: "
00605                                                  "free object not found while bit is clear.\n",
00606                                                  0, 0, 0 );
00607                                           assert(zo != NULL);
00608 
00609                                    }
00610                             } else {
00611                                    if ( !inserted ) {
00612                                           if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
00613                                                  slap_replenish_zopool(zh);
00614                                           }
00615                                           zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00616                                           LDAP_LIST_REMOVE(zo, zo_link);
00617                                           zo->zo_ptr = tmpp;
00618                                           zo->zo_idx = idx;
00619                                           Debug(LDAP_DEBUG_NONE,
00620                                                  "slap_zn_free: merging 0x%x\n",
00621                                                  zo->zo_ptr, 0, 0);
00622                                           LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
00623                                                         zo, zo_link);
00624                                    }
00625                                    break;
00626                             }
00627                      }
00628               }
00629               ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00630        }
00631 }
00632 
00633 static int
00634 slap_zone_cmp(const void *v1, const void *v2)
00635 {
00636        const struct zone_object *zo1 = v1;
00637        const struct zone_object *zo2 = v2;
00638        char *ptr1;
00639        char *ptr2;
00640        ber_len_t zpad;
00641 
00642        zpad = zo2->zo_siz - 1;
00643        ptr1 = (char*)(((unsigned long)zo1->zo_ptr + zpad) & ~zpad);
00644        ptr2 = (char*)zo2->zo_ptr + ((char*)ptr1 - (char*)zo1->zo_ptr);
00645        ptr2 = (char*)(((unsigned long)ptr2 + zpad) & ~zpad);
00646        return (int)((char*)ptr1 - (char*)ptr2);
00647 }
00648 
00649 void *
00650 slap_replenish_zopool(
00651        void *ctx
00652 )
00653 {
00654        struct zone_heap* zh = ctx;
00655        struct zone_object *zo_block;
00656        int i;
00657 
00658        zo_block = (struct zone_object *)ch_malloc(
00659                                    SLAP_ZONE_ZOBLOCK * sizeof(struct zone_object));
00660 
00661        if ( zo_block == NULL ) {
00662               return NULL;
00663        }
00664 
00665        zo_block[0].zo_blockhead = 1;
00666        LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, &zo_block[0], zo_link);
00667        for (i = 1; i < SLAP_ZONE_ZOBLOCK; i++) {
00668               zo_block[i].zo_blockhead = 0;
00669               LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, &zo_block[i], zo_link );
00670        }
00671 
00672        return zo_block;
00673 }
00674 
00675 int
00676 slap_zn_invalidate(
00677        void *ctx,
00678        void *ptr
00679 )
00680 {
00681        struct zone_heap* zh = ctx;
00682        struct zone_object zoi, *zoo;
00683        struct zone_heap *zone = NULL;
00684        int seqno = *((ber_len_t*)ptr - 2);
00685        int idx = -1, rc = 0;
00686        int pad = 2*sizeof(int)-1, pad_shift;
00687        int order_start = -1, i;
00688        struct zone_object *zo;
00689 
00690        pad_shift = pad - 1;
00691        do {
00692               order_start++;
00693        } while (pad_shift >>= 1);
00694 
00695        zoi.zo_ptr = ptr;
00696        zoi.zo_idx = -1;
00697 
00698        ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
00699        zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
00700 
00701        if (zoo) {
00702               idx = zoo->zo_idx;
00703               assert(idx != -1);
00704               madvise(zh->zh_zones[idx], zh->zh_zonesize, MADV_DONTNEED);
00705               for (i = 0; i < zh->zh_zoneorder - order_start + 1; i++) {
00706                      int shiftamt = order_start + 1 + i;
00707                      int nummaps = zh->zh_zonesize >> shiftamt;
00708                      assert(nummaps);
00709                      nummaps >>= 3;
00710                      if (!nummaps) nummaps = 1;
00711                      memset(zh->zh_maps[idx][i], 0, nummaps);
00712                      zo = LDAP_LIST_FIRST(&zh->zh_free[i]);
00713                      while (zo) {
00714                             struct zone_object *zo_tmp = zo;
00715                             zo = LDAP_LIST_NEXT(zo, zo_link);
00716                             if (zo_tmp && zo_tmp->zo_idx == idx) {
00717                                    LDAP_LIST_REMOVE(zo_tmp, zo_link);
00718                                    LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_tmp, zo_link);
00719                             }
00720                      }
00721               }
00722               if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
00723                      slap_replenish_zopool(zh);
00724               }
00725               zo = LDAP_LIST_FIRST(&zh->zh_zopool);
00726               LDAP_LIST_REMOVE(zo, zo_link);
00727               zo->zo_ptr = zh->zh_zones[idx];
00728               zo->zo_idx = idx;
00729               LDAP_LIST_INSERT_HEAD(&zh->zh_free[zh->zh_zoneorder-order_start],
00730                                                         zo, zo_link);
00731               zh->zh_seqno[idx]++;
00732        } else {
00733               Debug(LDAP_DEBUG_NONE, "zone not found for (ctx=0x%x, ptr=0x%x) !\n",
00734                             ctx, ptr, 0);
00735        }
00736 
00737        ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00738        Debug(LDAP_DEBUG_NONE, "zone %d invalidate\n", idx, 0, 0);
00739        return rc;
00740 }
00741 
00742 int
00743 slap_zn_validate(
00744        void *ctx,
00745        void *ptr,
00746        int seqno
00747 )
00748 {
00749        struct zone_heap* zh = ctx;
00750        struct zone_object zoi, *zoo;
00751        struct zone_heap *zone = NULL;
00752        int idx, rc = 0;
00753 
00754        zoi.zo_ptr = ptr;
00755        zoi.zo_idx = -1;
00756 
00757        zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
00758 
00759        if (zoo) {
00760               idx = zoo->zo_idx;
00761               assert(idx != -1);
00762               assert(seqno <= zh->zh_seqno[idx]);
00763               rc = (seqno == zh->zh_seqno[idx]);
00764        }
00765 
00766        return rc;
00767 }
00768 
00769 int slap_zh_rlock(
00770        void *ctx
00771 )
00772 {
00773        struct zone_heap* zh = ctx;
00774        ldap_pvt_thread_rdwr_rlock(&zh->zh_lock);
00775 }
00776 
00777 int slap_zh_runlock(
00778        void *ctx
00779 )
00780 {
00781        struct zone_heap* zh = ctx;
00782        ldap_pvt_thread_rdwr_runlock(&zh->zh_lock);
00783 }
00784 
00785 int slap_zh_wlock(
00786        void *ctx
00787 )
00788 {
00789        struct zone_heap* zh = ctx;
00790        ldap_pvt_thread_rdwr_wlock(&zh->zh_lock);
00791 }
00792 
00793 int slap_zh_wunlock(
00794        void *ctx
00795 )
00796 {
00797        struct zone_heap* zh = ctx;
00798        ldap_pvt_thread_rdwr_wunlock(&zh->zh_lock);
00799 }
00800 
00801 int slap_zn_rlock(
00802        void *ctx,
00803        void *ptr
00804 )
00805 {
00806        struct zone_heap* zh = ctx;
00807        struct zone_object zoi, *zoo;
00808        struct zone_heap *zone = NULL;
00809        int idx;
00810 
00811        zoi.zo_ptr = ptr;
00812        zoi.zo_idx = -1;
00813 
00814        ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
00815        zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
00816        ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00817 
00818        if (zoo) {
00819               idx = zoo->zo_idx;
00820               assert(idx != -1);
00821               ldap_pvt_thread_rdwr_rlock(&zh->zh_znlock[idx]);
00822        }
00823 }
00824 
00825 int slap_zn_runlock(
00826        void *ctx,
00827        void *ptr
00828 )
00829 {
00830        struct zone_heap* zh = ctx;
00831        struct zone_object zoi, *zoo;
00832        struct zone_heap *zone = NULL;
00833        int idx;
00834 
00835        zoi.zo_ptr = ptr;
00836        zoi.zo_idx = -1;
00837 
00838        ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
00839        zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
00840        ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00841 
00842        if (zoo) {
00843               idx = zoo->zo_idx;
00844               assert(idx != -1);
00845               ldap_pvt_thread_rdwr_runlock(&zh->zh_znlock[idx]);
00846        }
00847 }
00848 
00849 int slap_zn_wlock(
00850        void *ctx,
00851        void *ptr
00852 )
00853 {
00854        struct zone_heap* zh = ctx;
00855        struct zone_object zoi, *zoo;
00856        struct zone_heap *zone = NULL;
00857        int idx;
00858 
00859        zoi.zo_ptr = ptr;
00860        zoi.zo_idx = -1;
00861 
00862        ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
00863        zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
00864        ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00865 
00866        if (zoo) {
00867               idx = zoo->zo_idx;
00868               assert(idx != -1);
00869               ldap_pvt_thread_rdwr_wlock(&zh->zh_znlock[idx]);
00870        }
00871 }
00872 
00873 int slap_zn_wunlock(
00874        void *ctx,
00875        void *ptr
00876 )
00877 {
00878        struct zone_heap* zh = ctx;
00879        struct zone_object zoi, *zoo;
00880        struct zone_heap *zone = NULL;
00881        int idx;
00882 
00883        zoi.zo_ptr = ptr;
00884        zoi.zo_idx = -1;
00885 
00886        ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
00887        zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
00888        ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
00889 
00890        if (zoo) {
00891               idx = zoo->zo_idx;
00892               assert(idx != -1);
00893               ldap_pvt_thread_rdwr_wunlock(&zh->zh_znlock[idx]);
00894        }
00895 }
00896 
00897 #define T_SEC_IN_USEC 1000000
00898 
00899 static int
00900 slap_timediff(struct timeval *tv_begin, struct timeval *tv_end)
00901 {
00902        uint64_t t_begin, t_end, t_diff;
00903 
00904        t_begin = T_SEC_IN_USEC * tv_begin->tv_sec + tv_begin->tv_usec;
00905        t_end  = T_SEC_IN_USEC * tv_end->tv_sec  + tv_end->tv_usec;
00906        t_diff  = t_end - t_begin;
00907        
00908        if ( t_diff < 0 )
00909               t_diff = 0;
00910 
00911        return (int)t_diff;
00912 }
00913 
00914 void
00915 slap_set_timing(struct timeval *tv_set)
00916 {
00917        gettimeofday(tv_set, (struct timezone *)NULL);
00918 }
00919 
00920 int
00921 slap_measure_timing(struct timeval *tv_set, struct timeval *tv_measure)
00922 {
00923        gettimeofday(tv_measure, (struct timezone *)NULL);
00924        return(slap_timediff(tv_set, tv_measure));
00925 }
00926 
00927 #define EMA_WEIGHT 0.999000
00928 #define SLAP_ZN_LATENCY_HISTORY_QLEN 500
00929 int
00930 slap_zn_latency_history(void* ctx, int ea_latency)
00931 {
00932 /* TODO: monitor /proc/stat (swap) as well */
00933        struct zone_heap* zh = ctx;
00934        double t_diff = 0.0;
00935 
00936        zh->zh_ema_latency = (double)ea_latency * (1.0 - EMA_WEIGHT)
00937                                    + zh->zh_ema_latency * EMA_WEIGHT;
00938        if (!zh->zh_swapping && zh->zh_ema_samples++ % 100 == 99) {
00939               struct zone_latency_history *zlh_entry;
00940               zlh_entry = ch_calloc(1, sizeof(struct zone_latency_history));
00941               zlh_entry->zlh_latency = zh->zh_ema_latency;
00942               LDAP_STAILQ_INSERT_TAIL(
00943                             &zh->zh_latency_history_queue, zlh_entry, zlh_next);
00944               zh->zh_latency_history_qlen++;
00945               while (zh->zh_latency_history_qlen > SLAP_ZN_LATENCY_HISTORY_QLEN) {
00946                      struct zone_latency_history *zlh;
00947                      zlh = LDAP_STAILQ_FIRST(&zh->zh_latency_history_queue);
00948                      LDAP_STAILQ_REMOVE_HEAD(
00949                                    &zh->zh_latency_history_queue, zlh_next);
00950                      zh->zh_latency_history_qlen--;
00951                      ch_free(zlh);
00952               }
00953               if (zh->zh_latency_history_qlen == SLAP_ZN_LATENCY_HISTORY_QLEN) {
00954                      struct zone_latency_history *zlh_first, *zlh_last;
00955                      zlh_first = LDAP_STAILQ_FIRST(&zh->zh_latency_history_queue);
00956                      zlh_last = LDAP_STAILQ_LAST(&zh->zh_latency_history_queue,
00957                                           zone_latency_history, zlh_next);
00958                      t_diff = zlh_last->zlh_latency - zlh_first->zlh_latency;
00959               }
00960               if (t_diff >= 2000) {
00961                      zh->zh_latency_jump++;
00962               } else {
00963                      zh->zh_latency_jump = 0;
00964               }
00965               if (zh->zh_latency_jump > 3) {
00966                      zh->zh_latency_jump = 0;
00967                      zh->zh_swapping = 1;
00968               }
00969        }
00970        return zh->zh_swapping;
00971 }
00972 #endif /* SLAP_ZONE_ALLOC */