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