1 /* zn_malloc.c - zone-based malloc routines */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 * Copyright 2003-2004 The OpenLDAP Foundation.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
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>.
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
23 * This work originally developed by Jong-Hyuk Choi
24 * 2004/12/09 jongchoi@OpenLDAP.org
30 #include <ac/string.h>
31 #include <sys/types.h>
37 #ifdef SLAP_ZONE_ALLOC
39 static int slap_zone_cmp(const void *v1, const void *v2);
40 void * slap_replenish_zopool(void *ctx);
43 slap_zo_release(void *data)
45 struct zone_object *zo = (struct zone_object *)data;
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;
62 } while (pad_shift >>= 1);
64 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
65 for (i = 0; i <= zh->zh_zoneorder - order_start; i++) {
66 zo = LDAP_LIST_FIRST(&zh->zh_free[i]);
68 struct zone_object *zo_tmp = zo;
69 zo = LDAP_LIST_NEXT(zo, zo_link);
70 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_tmp, zo_link);
75 for (i = 0; i < zh->zh_numzones; i++) {
76 for (j = 0; j < zh->zh_zoneorder - order_start; j++) {
77 ch_free(zh->zh_maps[i][j]);
79 ch_free(zh->zh_maps[i]);
80 munmap(zh->zh_zones[i], zh->zh_zonesize);
83 ch_free(zh->zh_zones);
84 ch_free(zh->zh_seqno);
86 avl_free(zh->zh_zonetree, slap_zo_release);
88 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
90 struct zone_object *zo_tmp = zo;
91 zo = LDAP_LIST_NEXT(zo, zo_link);
92 if (!zo_tmp->zo_blockhead) {
93 LDAP_LIST_REMOVE(zo_tmp, zo_link);
96 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
98 struct zone_object *zo_tmp = zo;
99 zo = LDAP_LIST_NEXT(zo, zo_link);
102 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
103 ldap_pvt_thread_mutex_destroy( &zh->zh_mutex );
115 struct zone_heap *zh = NULL;
117 int pad = 2*sizeof(int)-1, pad_shift;
119 int order = -1, order_start = -1, order_end = -1;
121 struct zone_object *zo;
123 Debug(LDAP_DEBUG_NONE,
124 "--> slap_zn_mem_create: initsize=%d, maxsize=%d\n",
125 initsize, maxsize, 0);
126 Debug(LDAP_DEBUG_NONE,
127 "++> slap_zn_mem_create: deltasize=%d, zonesize=%d\n",
128 deltasize, zonesize, 0);
130 zh = (struct zone_heap *)ch_calloc(1, sizeof(struct zone_heap));
132 zh->zh_fd = open("/dev/zero", O_RDWR);
135 zh->zh_zonesize = zonesize;
137 zh->zh_zonesize = SLAP_ZONE_SIZE;
140 zpad = zh->zh_zonesize - 1;
141 zh->zh_numzones = ((initsize + zpad) & ~zpad) / zh->zh_zonesize;
143 if ( maxsize && maxsize >= initsize ) {
144 zh->zh_maxzones = ((maxsize + zpad) & ~zpad) / zh->zh_zonesize;
146 zh->zh_maxzones = ((initsize + zpad) & ~zpad) / zh->zh_zonesize;
150 zh->zh_deltazones = ((deltasize + zpad) & ~zpad) / zh->zh_zonesize;
152 zh->zh_deltazones = ((SLAP_ZONE_DELTA+zpad) & ~zpad) / zh->zh_zonesize;
155 size_shift = zh->zh_zonesize - 1;
158 } while (size_shift >>= 1);
163 } while (pad_shift >>= 1);
165 order = order_end - order_start + 1;
167 zh->zh_zones = (void **)ch_malloc(zh->zh_maxzones * sizeof(void*));
168 zh->zh_maps = (unsigned char ***)ch_malloc(
169 zh->zh_maxzones * sizeof(unsigned char**));
171 zh->zh_zoneorder = order_end;
172 zh->zh_free = (struct zh_freelist *)
173 ch_malloc(order * sizeof(struct zh_freelist));
174 zh->zh_seqno = (unsigned long *)ch_calloc(zh->zh_maxzones,
175 sizeof(unsigned long));
176 for (i = 0; i < order; i++) {
177 LDAP_LIST_INIT(&zh->zh_free[i]);
179 LDAP_LIST_INIT(&zh->zh_zopool);
181 for (i = 0; i < zh->zh_numzones; i++) {
182 zh->zh_zones[i] = mmap(0, zh->zh_zonesize, PROT_READ | PROT_WRITE,
183 MAP_PRIVATE, zh->zh_fd, 0);
184 zh->zh_maps[i] = (unsigned char **)
185 ch_malloc(order * sizeof(unsigned char *));
186 for (j = 0; j < order; j++) {
187 int shiftamt = order_start + 1 + j;
188 int nummaps = zh->zh_zonesize >> shiftamt;
191 if (!nummaps) nummaps = 1;
192 zh->zh_maps[i][j] = (unsigned char *)ch_malloc(nummaps);
193 memset(zh->zh_maps[i][j], 0, nummaps);
196 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
197 slap_replenish_zopool(zh);
199 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
200 LDAP_LIST_REMOVE(zo, zo_link);
201 zo->zo_ptr = zh->zh_zones[i];
203 LDAP_LIST_INSERT_HEAD(&zh->zh_free[order-1], zo, zo_link);
205 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
206 slap_replenish_zopool(zh);
208 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
209 LDAP_LIST_REMOVE(zo, zo_link);
210 zo->zo_ptr = zh->zh_zones[i];
211 zo->zo_siz = zh->zh_zonesize;
213 avl_insert(&zh->zh_zonetree, zo, slap_zone_cmp, avl_dup_error);
216 ldap_pvt_thread_mutex_init(&zh->zh_mutex);
227 struct zone_heap *zh = ctx;
228 ber_len_t size_shift;
229 int pad = 2*sizeof(int)-1, pad_shift;
230 int order = -1, order_start = -1;
231 struct zone_object *zo, *zo_new, *zo_left, *zo_right;
232 ber_len_t *ptr, *new;
237 Debug(LDAP_DEBUG_NONE,
238 "--> slap_zn_malloc: size=%d\n", size, 0, 0);
240 if (!zh) return ber_memalloc_x(size, NULL);
242 /* round up to doubleword boundary */
243 size += 2*sizeof(ber_len_t) + pad;
246 size_shift = size - 1;
249 } while (size_shift >>= 1);
254 } while (pad_shift >>= 1);
258 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
259 for (i = order; i <= zh->zh_zoneorder &&
260 LDAP_LIST_EMPTY(&zh->zh_free[i-order_start]); i++);
263 zo_new = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
264 LDAP_LIST_REMOVE(zo_new, zo_link);
265 ptr = zo_new->zo_ptr;
266 idx = zo_new->zo_idx;
267 diff = (unsigned long)((char*)ptr -
268 (char*)zh->zh_zones[idx]) >> (order + 1);
269 zh->zh_maps[idx][order-order_start][diff>>3] |= (1 << (diff & 0x7));
270 *ptr++ = zh->zh_seqno[idx];
271 *ptr++ = size - 2*sizeof(ber_len_t);
272 zo_new->zo_ptr = NULL;
274 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_new, zo_link);
275 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
276 Debug(LDAP_DEBUG_NONE, "slap_zn_malloc: returning 0x%x, 0x%x\n",
277 ptr, (int)ptr>>(zh->zh_zoneorder+1), 0);
279 } else if (i <= zh->zh_zoneorder) {
280 for (j = i; j > order; j--) {
281 zo_left = LDAP_LIST_FIRST(&zh->zh_free[j-order_start]);
282 LDAP_LIST_REMOVE(zo_left, zo_link);
283 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
284 slap_replenish_zopool(zh);
286 zo_right = LDAP_LIST_FIRST(&zh->zh_zopool);
287 LDAP_LIST_REMOVE(zo_right, zo_link);
288 zo_right->zo_ptr = zo_left->zo_ptr + (1 << j);
289 zo_right->zo_idx = zo_left->zo_idx;
290 Debug(LDAP_DEBUG_NONE,
291 "slap_zn_malloc: split (left=0x%x, right=0x%x)\n",
292 zo_left->zo_ptr, zo_right->zo_ptr, 0);
293 if (j == order + 1) {
294 ptr = zo_left->zo_ptr;
295 diff = (unsigned long)((char*)ptr -
296 (char*)zh->zh_zones[zo_left->zo_idx]) >> (order+1);
297 zh->zh_maps[zo_left->zo_idx][order-order_start][diff>>3] |=
299 *ptr++ = zh->zh_seqno[zo_left->zo_idx];
300 *ptr++ = size - 2*sizeof(ber_len_t);
301 LDAP_LIST_INSERT_HEAD(
302 &zh->zh_free[j-1-order_start], zo_right, zo_link);
303 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, zo_left, zo_link);
304 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
305 Debug(LDAP_DEBUG_NONE,
306 "slap_zn_malloc: returning 0x%x, 0x%x\n",
307 ptr, (int)ptr>>(zh->zh_zoneorder+1), 0);
310 LDAP_LIST_INSERT_HEAD(
311 &zh->zh_free[j-1-order_start], zo_right, zo_link);
312 LDAP_LIST_INSERT_HEAD(
313 &zh->zh_free[j-1-order_start], zo_left, zo_link);
319 if ( zh->zh_maxzones < zh->zh_numzones + zh->zh_deltazones ) {
320 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
321 Debug( LDAP_DEBUG_TRACE,
322 "slap_zn_malloc of %lu bytes failed, using ch_malloc\n",
324 Debug(LDAP_DEBUG_NONE,
325 "slap_zn_malloc: returning 0x%x, 0x%x\n",
326 ptr, (int)ptr>>(zh->zh_zoneorder+1), 0);
327 return (void*)ch_malloc(size);
330 for (i = zh->zh_numzones; i < zh->zh_numzones+zh->zh_deltazones; i++) {
331 zh->zh_zones[i] = mmap(0, zh->zh_zonesize, PROT_READ | PROT_WRITE,
332 MAP_PRIVATE, zh->zh_fd, 0);
333 zh->zh_maps[i] = (unsigned char **)
334 ch_malloc((zh->zh_zoneorder - order_start + 1) *
335 sizeof(unsigned char *));
336 for (j = 0; j < zh->zh_zoneorder-order_start+1; j++) {
337 int shiftamt = order_start + 1 + j;
338 int nummaps = zh->zh_zonesize >> shiftamt;
341 if (!nummaps) nummaps = 1;
342 zh->zh_maps[i][j] = (unsigned char *)ch_malloc(nummaps);
343 memset(zh->zh_maps[i][j], 0, nummaps);
346 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
347 slap_replenish_zopool(zh);
349 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
350 LDAP_LIST_REMOVE(zo, zo_link);
351 zo->zo_ptr = zh->zh_zones[i];
353 LDAP_LIST_INSERT_HEAD(&zh->
354 zh_free[zh->zh_zoneorder-order_start],zo,zo_link);
356 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
357 slap_replenish_zopool(zh);
359 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
360 LDAP_LIST_REMOVE(zo, zo_link);
361 zo->zo_ptr = zh->zh_zones[i];
362 zo->zo_siz = zh->zh_zonesize;
364 avl_insert(&zh->zh_zonetree, zo, slap_zone_cmp, avl_dup_error);
366 zh->zh_numzones += zh->zh_deltazones;
367 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
373 slap_zn_calloc( ber_len_t n, ber_len_t size, void *ctx )
377 new = slap_zn_malloc( n*size, ctx );
379 memset( new, 0, n*size );
385 slap_zn_realloc(void *ptr, ber_len_t size, void *ctx)
387 struct zone_heap *zh = ctx;
388 int pad = 2*sizeof(int)-1, pad_shift;
389 int order_start = -1, order = -1;
390 struct zone_object zoi, *zoo;
391 ber_len_t *p = (ber_len_t *)ptr, *new;
395 struct zone_heap *zone = NULL;
397 Debug(LDAP_DEBUG_NONE,
398 "--> slap_zn_realloc: ptr=0x%x, size=%d\n", ptr, size, 0);
401 return slap_zn_malloc(size, zh);
407 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
408 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
409 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
412 /* Not our memory? */
414 /* duplicate of realloc behavior, oh well */
415 new = ber_memrealloc_x(ptr, size, NULL);
419 Debug(LDAP_DEBUG_ANY, "ch_realloc of %lu bytes failed\n",
422 exit( EXIT_FAILURE );
425 assert(zoo->zo_idx != -1);
427 zone = zh->zh_zones[zoo->zo_idx];
430 slap_zn_free(ptr, zh);
434 newptr = slap_zn_malloc(size, zh);
436 AC_MEMCPY(newptr, ptr, size);
438 AC_MEMCPY(newptr, ptr, p[-1]);
440 slap_zn_free(ptr, zh);
445 slap_zn_free(void *ptr, void *ctx)
447 struct zone_heap *zh = ctx;
448 int size, size_shift, order_size;
449 int pad = 2*sizeof(int)-1, pad_shift;
450 ber_len_t *p = (ber_len_t *)ptr, *tmpp;
451 int order_start = -1, order = -1;
452 struct zone_object zoi, *zoo, *zo;
454 int i, k, inserted = 0, idx;
455 struct zone_heap *zone = NULL;
460 Debug(LDAP_DEBUG_NONE, "--> slap_zn_free: ptr=0x%x\n", ptr, 0, 0);
463 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
464 zoo = avl_find(zh->zh_zonetree, &zoi, slap_zone_cmp);
465 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
469 ber_memfree_x(ptr, NULL);
473 zone = zh->zh_zones[idx];
476 size_shift = size + 2*sizeof(ber_len_t) - 1;
479 } while (size_shift >>= 1);
484 } while (pad_shift >>= 1);
486 ldap_pvt_thread_mutex_lock( &zh->zh_mutex );
487 for (i = order, tmpp = p; i <= zh->zh_zoneorder; i++) {
488 order_size = 1 << (i+1);
489 diff = (unsigned long)((char*)tmpp - (char*)zone) >> (i+1);
490 zh->zh_maps[idx][i-order_start][diff>>3] &= (~(1 << (diff & 0x7)));
491 if (diff == ((diff>>1)<<1)) {
492 if (!(zh->zh_maps[idx][i-order_start][(diff+1)>>3] &
493 (1<<((diff+1)&0x7)))) {
494 zo = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
496 if ((char*)zo->zo_ptr == (char*)tmpp) {
497 LDAP_LIST_REMOVE( zo, zo_link );
498 } else if ((char*)zo->zo_ptr ==
499 (char*)tmpp + order_size) {
500 LDAP_LIST_REMOVE(zo, zo_link);
503 zo = LDAP_LIST_NEXT(zo, zo_link);
506 if (i < zh->zh_zoneorder) {
509 Debug(LDAP_DEBUG_NONE,
510 "slap_zn_free: merging 0x%x\n",
512 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start+1],
517 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
518 slap_replenish_zopool(zh);
520 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
521 LDAP_LIST_REMOVE(zo, zo_link);
523 Debug(LDAP_DEBUG_NONE,
524 "slap_zn_free: merging 0x%x\n",
526 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
530 Debug(LDAP_DEBUG_ANY, "slap_zn_free: "
531 "free object not found while bit is clear.\n",
538 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
539 slap_replenish_zopool(zh);
541 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
542 LDAP_LIST_REMOVE(zo, zo_link);
544 Debug(LDAP_DEBUG_NONE,
545 "slap_zn_free: merging 0x%x\n",
547 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
553 if (!(zh->zh_maps[idx][i-order_start][(diff-1)>>3] &
554 (1<<((diff-1)&0x7)))) {
555 zo = LDAP_LIST_FIRST(&zh->zh_free[i-order_start]);
557 if ((char*)zo->zo_ptr == (char*)tmpp) {
558 LDAP_LIST_REMOVE(zo, zo_link);
559 } else if ((char*)tmpp == zo->zo_ptr + order_size) {
560 LDAP_LIST_REMOVE(zo, zo_link);
564 zo = LDAP_LIST_NEXT(zo, zo_link);
567 if (i < zh->zh_zoneorder) {
569 Debug(LDAP_DEBUG_NONE,
570 "slap_zn_free: merging 0x%x\n",
572 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start+1],
577 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
578 slap_replenish_zopool(zh);
580 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
581 LDAP_LIST_REMOVE(zo, zo_link);
583 Debug(LDAP_DEBUG_NONE,
584 "slap_zn_free: merging 0x%x\n",
586 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
590 Debug(LDAP_DEBUG_ANY, "slap_zn_free: "
591 "free object not found while bit is clear.\n",
598 if (LDAP_LIST_EMPTY(&zh->zh_zopool)) {
599 slap_replenish_zopool(zh);
601 zo = LDAP_LIST_FIRST(&zh->zh_zopool);
602 LDAP_LIST_REMOVE(zo, zo_link);
604 Debug(LDAP_DEBUG_NONE,
605 "slap_zn_free: merging 0x%x\n",
607 LDAP_LIST_INSERT_HEAD(&zh->zh_free[i-order_start],
614 ldap_pvt_thread_mutex_unlock( &zh->zh_mutex );
619 slap_zone_cmp(const void *v1, const void *v2)
621 const struct zone_object *zo1 = v1;
622 const struct zone_object *zo2 = v2;
627 zpad = zo2->zo_siz - 1;
628 ptr1 = (char*)(((unsigned long)zo1->zo_ptr + zpad) & ~zpad);
629 ptr2 = (char*)zo2->zo_ptr + ((char*)ptr1 - (char*)zo1->zo_ptr);
630 ptr2 = (char*)(((unsigned long)ptr2 + zpad) & ~zpad);
631 return (int)((char*)ptr1 - (char*)ptr2);
635 slap_replenish_zopool(
639 struct zone_heap* zh = ctx;
640 struct zone_object *zo_block;
643 zo_block = (struct zone_object *)ch_malloc(
644 SLAP_ZONE_ZOBLOCK * sizeof(struct zone_object));
646 if ( zo_block == NULL ) {
650 zo_block[0].zo_blockhead = 1;
651 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, &zo_block[0], zo_link);
652 for (i = 1; i < SLAP_ZONE_ZOBLOCK; i++) {
653 zo_block[i].zo_blockhead = 0;
654 LDAP_LIST_INSERT_HEAD(&zh->zh_zopool, &zo_block[i], zo_link );
659 #endif /* SLAP_ZONE_ALLOC */