?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Patrick Welche <prlw1@cam.ac.uk>
[netbsd-mini2440.git] / external / bsd / openldap / dist / servers / slapd / sl_malloc.c
blob57346584a8eacb51890e36d74e0251c919b2f357
1 /* sl_malloc.c - malloc routines using a per-thread slab */
2 /* $OpenLDAP: pkg/ldap/servers/slapd/sl_malloc.c,v 1.39.2.6 2008/02/11 23:34:15 quanah Exp $ */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 *
5 * Copyright 2003-2008 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
17 #include "portable.h"
18
19 #include <stdio.h>
20 #include <ac/string.h>
21
22 #include "slap.h"
23
24 static struct slab_object * slap_replenish_sopool(struct slab_heap* sh);
25 #ifdef SLAPD_UNUSED
26 static void print_slheap(int level, void *ctx);
27 #endif
28
29 void
30 slap_sl_mem_destroy(
31 void *key,
32 void *data
33 )
34 {
35 struct slab_heap *sh = data;
36 int pad = 2*sizeof(int)-1, pad_shift;
37 int order_start = -1, i;
38 struct slab_object *so;
39
40 if (sh->sh_stack) {
41 ber_memfree_x(sh->sh_base, NULL);
42 ber_memfree_x(sh, NULL);
43 } else {
44 pad_shift = pad - 1;
45 do {
46 order_start++;
47 } while (pad_shift >>= 1);
48
49 for (i = 0; i <= sh->sh_maxorder - order_start; i++) {
50 so = LDAP_LIST_FIRST(&sh->sh_free[i]);
51 while (so) {
52 struct slab_object *so_tmp = so;
53 so = LDAP_LIST_NEXT(so, so_link);
54 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_tmp, so_link);
55 }
56 ch_free(sh->sh_map[i]);
57 }
58 ch_free(sh->sh_free);
59 ch_free(sh->sh_map);
60
61 so = LDAP_LIST_FIRST(&sh->sh_sopool);
62 while (so) {
63 struct slab_object *so_tmp = so;
64 so = LDAP_LIST_NEXT(so, so_link);
65 if (!so_tmp->so_blockhead) {
66 LDAP_LIST_REMOVE(so_tmp, so_link);
67 }
68 }
69 so = LDAP_LIST_FIRST(&sh->sh_sopool);
70 while (so) {
71 struct slab_object *so_tmp = so;
72 so = LDAP_LIST_NEXT(so, so_link);
73 ch_free(so_tmp);
74 }
75 ber_memfree_x(sh->sh_base, NULL);
76 ber_memfree_x(sh, NULL);
77 }
78 }
79
80 BerMemoryFunctions slap_sl_mfuncs =
81 { slap_sl_malloc, slap_sl_calloc, slap_sl_realloc, slap_sl_free };
82
83 void
84 slap_sl_mem_init()
85 {
86 ber_set_option( NULL, LBER_OPT_MEMORY_FNS, &slap_sl_mfuncs );
87 }
88
89 #ifdef NO_THREADS
90 static struct slab_heap *slheap;
91 #endif
92
93 void *
94 slap_sl_mem_create(
95 ber_len_t size,
96 int stack,
97 void *ctx,
98 int new
99 )
100 {
101 struct slab_heap *sh;
102 ber_len_t size_shift;
103 int pad = 2*sizeof(int)-1, pad_shift;
104 int order = -1, order_start = -1, order_end = -1;
105 int i;
106 struct slab_object *so;
107
108 #ifdef NO_THREADS
109 sh = slheap;
110 #else
111 void *sh_tmp = NULL;
112 ldap_pvt_thread_pool_getkey(
113 ctx, (void *)slap_sl_mem_init, &sh_tmp, NULL );
114 sh = sh_tmp;
115 #endif
116
117 if ( !new )
118 return sh;
119
120 /* round up to doubleword boundary */
121 size += pad;
122 size &= ~pad;
123
124 if (stack) {
125 if (!sh) {
126 sh = ch_malloc(sizeof(struct slab_heap));
127 sh->sh_base = ch_malloc(size);
128 #ifdef NO_THREADS
129 slheap = sh;
130 #else
131 ldap_pvt_thread_pool_setkey(ctx, (void *)slap_sl_mem_init,
132 (void *)sh, slap_sl_mem_destroy, NULL, NULL);
133 #endif
134 } else if ( size > (char *)sh->sh_end - (char *)sh->sh_base ) {
135 void *newptr;
136
137 newptr = ch_realloc( sh->sh_base, size );
138 if ( newptr == NULL ) return NULL;
139 sh->sh_base = newptr;
140 }
141 sh->sh_last = sh->sh_base;
142 sh->sh_end = (char *) sh->sh_base + size;
143 sh->sh_stack = stack;
144 return sh;
145 } else {
146 size_shift = size - 1;
147 do {
148 order_end++;
149 } while (size_shift >>= 1);
150
151 pad_shift = pad - 1;
152 do {
153 order_start++;
154 } while (pad_shift >>= 1);
155
156 order = order_end - order_start + 1;
157
158 if (!sh) {
159 sh = (struct slab_heap *) ch_malloc(sizeof(struct slab_heap));
160 sh->sh_base = ch_malloc(size);
161 #ifdef NO_THREADS
162 slheap = sh;
163 #else
164 ldap_pvt_thread_pool_setkey(ctx, (void *)slap_sl_mem_init,
165 (void *)sh, slap_sl_mem_destroy, NULL, NULL);
166 #endif
167 } else {
168 for (i = 0; i <= sh->sh_maxorder - order_start; i++) {
169 so = LDAP_LIST_FIRST(&sh->sh_free[i]);
170 while (so) {
171 struct slab_object *so_tmp = so;
172 so = LDAP_LIST_NEXT(so, so_link);
173 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_tmp, so_link);
174 }
175 ch_free(sh->sh_map[i]);
176 }
177 ch_free(sh->sh_free);
178 ch_free(sh->sh_map);
179
180 so = LDAP_LIST_FIRST(&sh->sh_sopool);
181 while (so) {
182 struct slab_object *so_tmp = so;
183 so = LDAP_LIST_NEXT(so, so_link);
184 if (!so_tmp->so_blockhead) {
185 LDAP_LIST_REMOVE(so_tmp, so_link);
186 }
187 }
188 so = LDAP_LIST_FIRST(&sh->sh_sopool);
189 while (so) {
190 struct slab_object *so_tmp = so;
191 so = LDAP_LIST_NEXT(so, so_link);
192 ch_free(so_tmp);
193 }
194
195 if (size > (char *)sh->sh_end - (char *)sh->sh_base) {
196 void *newptr;
197
198 newptr = realloc( sh->sh_base, size );
199 if ( newptr == NULL ) return NULL;
200 sh->sh_base = newptr;
201 }
202 }
203 sh->sh_end = (char *)sh->sh_base + size;
204 sh->sh_maxorder = order_end;
205
206 sh->sh_free = (struct sh_freelist *)
207 ch_malloc(order * sizeof(struct sh_freelist));
208 for (i = 0; i < order; i++) {
209 LDAP_LIST_INIT(&sh->sh_free[i]);
210 }
211
212 LDAP_LIST_INIT(&sh->sh_sopool);
213
214 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
215 slap_replenish_sopool(sh);
216 }
217 so = LDAP_LIST_FIRST(&sh->sh_sopool);
218 LDAP_LIST_REMOVE(so, so_link);
219 so->so_ptr = sh->sh_base;
220
221 LDAP_LIST_INSERT_HEAD(&sh->sh_free[order-1], so, so_link);
222
223 sh->sh_map = (unsigned char **)
224 ch_malloc(order * sizeof(unsigned char *));
225 for (i = 0; i < order; i++) {
226 int shiftamt = order_start + 1 + i;
227 int nummaps = size >> shiftamt;
228 assert(nummaps);
229 nummaps >>= 3;
230 if (!nummaps) nummaps = 1;
231 sh->sh_map[i] = (unsigned char *) ch_malloc(nummaps);
232 memset(sh->sh_map[i], 0, nummaps);
233 }
234 sh->sh_stack = stack;
235 return sh;
236 }
237 }
238
239 void
240 slap_sl_mem_detach(
241 void *ctx,
242 void *memctx
243 )
244 {
245 #ifdef NO_THREADS
246 slheap = NULL;
247 #else
248 /* separate from context */
249 ldap_pvt_thread_pool_setkey( ctx, (void *)slap_sl_mem_init,
250 NULL, 0, NULL, NULL );
251 #endif
252 }
253
254 void *
255 slap_sl_malloc(
256 ber_len_t size,
257 void *ctx
258 )
259 {
260 struct slab_heap *sh = ctx;
261 ber_len_t size_shift;
262 int pad = 2*sizeof(int)-1, pad_shift;
263 int order = -1, order_start = -1;
264 struct slab_object *so_new, *so_left, *so_right;
265 ber_len_t *ptr, *newptr;
266 unsigned long diff;
267 int i, j;
268
269 #ifdef SLAP_NO_SL_MALLOC
270 return ber_memalloc_x( size, NULL );
271 #endif
272
273 /* ber_set_option calls us like this */
274 if (!ctx) return ber_memalloc_x(size, NULL);
275
276 /* round up to doubleword boundary */
277 size += sizeof(ber_len_t) + pad;
278 size &= ~pad;
279
280 if (sh->sh_stack) {
281 if ((char *)sh->sh_last + size >= (char *)sh->sh_end) {
282 Debug(LDAP_DEBUG_TRACE,
283 "slap_sl_malloc of %lu bytes failed, using ch_malloc\n",
284 (long)size, 0, 0);
285 return ch_malloc(size);
286 }
287 newptr = sh->sh_last;
288 *newptr++ = size - sizeof(ber_len_t);
289 sh->sh_last = (char *) sh->sh_last + size;
290 return( (void *)newptr );
291 } else {
292 size_shift = size - 1;
293 do {
294 order++;
295 } while (size_shift >>= 1);
296
297 pad_shift = pad - 1;
298 do {
299 order_start++;
300 } while (pad_shift >>= 1);
301
302 for (i = order; i <= sh->sh_maxorder &&
303 LDAP_LIST_EMPTY(&sh->sh_free[i-order_start]); i++);
304
305 if (i == order) {
306 so_new = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
307 LDAP_LIST_REMOVE(so_new, so_link);
308 ptr = so_new->so_ptr;
309 diff = (unsigned long)((char*)ptr -
310 (char*)sh->sh_base) >> (order + 1);
311 sh->sh_map[order-order_start][diff>>3] |= (1 << (diff & 0x7));
312 *ptr++ = size - sizeof(ber_len_t);
313 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_new, so_link);
314 return((void*)ptr);
315 } else if (i <= sh->sh_maxorder) {
316 for (j = i; j > order; j--) {
317 so_left = LDAP_LIST_FIRST(&sh->sh_free[j-order_start]);
318 LDAP_LIST_REMOVE(so_left, so_link);
319 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
320 slap_replenish_sopool(sh);
321 }
322 so_right = LDAP_LIST_FIRST(&sh->sh_sopool);
323 LDAP_LIST_REMOVE(so_right, so_link);
324 so_right->so_ptr = (void *)((char *)so_left->so_ptr + (1 << j));
325 if (j == order + 1) {
326 ptr = so_left->so_ptr;
327 diff = (unsigned long)((char*)ptr -
328 (char*)sh->sh_base) >> (order+1);
329 sh->sh_map[order-order_start][diff>>3] |=
330 (1 << (diff & 0x7));
331 *ptr++ = size - sizeof(ber_len_t);
332 LDAP_LIST_INSERT_HEAD(
333 &sh->sh_free[j-1-order_start], so_right, so_link);
334 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_left, so_link);
335 return((void*)ptr);
336 } else {
337 LDAP_LIST_INSERT_HEAD(
338 &sh->sh_free[j-1-order_start], so_right, so_link);
339 LDAP_LIST_INSERT_HEAD(
340 &sh->sh_free[j-1-order_start], so_left, so_link);
341 }
342 }
343 } else {
344 Debug( LDAP_DEBUG_TRACE,
345 "slap_sl_malloc of %lu bytes failed, using ch_malloc\n",
346 (long)size, 0, 0);
347 return (void*)ch_malloc(size);
348 }
349 }
350
351 /* FIXME: missing return; guessing... */
352 return NULL;
353 }
354
355 void *
356 slap_sl_calloc( ber_len_t n, ber_len_t size, void *ctx )
357 {
358 void *newptr;
359
360 newptr = slap_sl_malloc( n*size, ctx );
361 if ( newptr ) {
362 memset( newptr, 0, n*size );
363 }
364 return newptr;
365 }
366
367 void *
368 slap_sl_realloc(void *ptr, ber_len_t size, void *ctx)
369 {
370 struct slab_heap *sh = ctx;
371 int pad = 2*sizeof(int) -1;
372 ber_len_t *p = (ber_len_t *)ptr, *newptr;
373
374 if (ptr == NULL)
375 return slap_sl_malloc(size, ctx);
376
377 #ifdef SLAP_NO_SL_MALLOC
378 return ber_memrealloc_x( ptr, size, NULL );
379 #endif
380
381 /* Not our memory? */
382 if (!sh || ptr < sh->sh_base || ptr >= sh->sh_end) {
383 /* duplicate of realloc behavior, oh well */
384 newptr = ber_memrealloc_x(ptr, size, NULL);
385 if (newptr) {
386 return newptr;
387 }
388 Debug(LDAP_DEBUG_ANY, "ch_realloc of %lu bytes failed\n",
389 (long) size, 0, 0);
390 assert(0);
391 exit( EXIT_FAILURE );
392 }
393
394 if (size == 0) {
395 slap_sl_free(ptr, ctx);
396 return NULL;
397 }
398
399 if (sh->sh_stack) {
400 /* round up to doubleword boundary */
401 size += pad + sizeof( ber_len_t );
402 size &= ~pad;
403
404 /* Never shrink blocks */
405 if (size <= p[-1]) {
406 newptr = p;
407
408 /* If reallocing the last block, we can grow it */
409 } else if ((char *)ptr + p[-1] == sh->sh_last &&
410 (char *)ptr + size < (char *)sh->sh_end ) {
411 newptr = p;
412 sh->sh_last = (char *)sh->sh_last + size - p[-1];
413 p[-1] = size;
414
415 /* Nowhere to grow, need to alloc and copy */
416 } else {
417 newptr = slap_sl_malloc(size, ctx);
418 AC_MEMCPY(newptr, ptr, p[-1]);
419 }
420 return newptr;
421 } else {
422 void *newptr2;
423
424 newptr2 = slap_sl_malloc(size, ctx);
425 if (size < p[-1]) {
426 AC_MEMCPY(newptr2, ptr, size);
427 } else {
428 AC_MEMCPY(newptr2, ptr, p[-1]);
429 }
430 slap_sl_free(ptr, ctx);
431 return newptr2;
432 }
433 }
434
435 void
436 slap_sl_free(void *ptr, void *ctx)
437 {
438 struct slab_heap *sh = ctx;
439 int size, size_shift, order_size;
440 int pad = 2*sizeof(int)-1, pad_shift;
441 ber_len_t *p = (ber_len_t *)ptr, *tmpp;
442 int order_start = -1, order = -1;
443 struct slab_object *so;
444 unsigned long diff;
445 int i, inserted = 0;
446
447 if (!ptr)
448 return;
449
450 #ifdef SLAP_NO_SL_MALLOC
451 ber_memfree_x( ptr, NULL );
452 return;
453 #endif
454
455 if (!sh || ptr < sh->sh_base || ptr >= sh->sh_end) {
456 ber_memfree_x(ptr, NULL);
457 } else if (sh->sh_stack && (char *)ptr + p[-1] == sh->sh_last) {
458 p--;
459 sh->sh_last = p;
460 } else if (!sh->sh_stack) {
461 size = *(--p);
462 size_shift = size + sizeof(ber_len_t) - 1;
463 do {
464 order++;
465 } while (size_shift >>= 1);
466
467 pad_shift = pad - 1;
468 do {
469 order_start++;
470 } while (pad_shift >>= 1);
471
472 for (i = order, tmpp = p; i <= sh->sh_maxorder; i++) {
473 order_size = 1 << (i+1);
474 diff = (unsigned long)((char*)tmpp - (char*)sh->sh_base) >> (i+1);
475 sh->sh_map[i-order_start][diff>>3] &= (~(1 << (diff & 0x7)));
476 if (diff == ((diff>>1)<<1)) {
477 if (!(sh->sh_map[i-order_start][(diff+1)>>3] &
478 (1<<((diff+1)&0x7)))) {
479 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
480 while (so) {
481 if ((char*)so->so_ptr == (char*)tmpp) {
482 LDAP_LIST_REMOVE( so, so_link );
483 } else if ((char*)so->so_ptr ==
484 (char*)tmpp + order_size) {
485 LDAP_LIST_REMOVE(so, so_link);
486 break;
487 }
488 so = LDAP_LIST_NEXT(so, so_link);
489 }
490 if (so) {
491 if (i < sh->sh_maxorder) {
492 inserted = 1;
493 so->so_ptr = tmpp;
494 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start+1],
495 so, so_link);
496 }
497 continue;
498 } else {
499 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
500 slap_replenish_sopool(sh);
501 }
502 so = LDAP_LIST_FIRST(&sh->sh_sopool);
503 LDAP_LIST_REMOVE(so, so_link);
504 so->so_ptr = tmpp;
505 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
506 so, so_link);
507 break;
508
509 Debug(LDAP_DEBUG_TRACE, "slap_sl_free: "
510 "free object not found while bit is clear.\n",
511 0, 0, 0);
512 assert(so != NULL);
513
514 }
515 } else {
516 if (!inserted) {
517 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
518 slap_replenish_sopool(sh);
519 }
520 so = LDAP_LIST_FIRST(&sh->sh_sopool);
521 LDAP_LIST_REMOVE(so, so_link);
522 so->so_ptr = tmpp;
523 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
524 so, so_link);
525 }
526 break;
527 }
528 } else {
529 if (!(sh->sh_map[i-order_start][(diff-1)>>3] &
530 (1<<((diff-1)&0x7)))) {
531 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
532 while (so) {
533 if ((char*)so->so_ptr == (char*)tmpp) {
534 LDAP_LIST_REMOVE(so, so_link);
535 } else if ((char*)tmpp == (char *)so->so_ptr + order_size) {
536 LDAP_LIST_REMOVE(so, so_link);
537 tmpp = so->so_ptr;
538 break;
539 }
540 so = LDAP_LIST_NEXT(so, so_link);
541 }
542 if (so) {
543 if (i < sh->sh_maxorder) {
544 inserted = 1;
545 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start+1], so, so_link);
546 continue;
547 }
548 } else {
549 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
550 slap_replenish_sopool(sh);
551 }
552 so = LDAP_LIST_FIRST(&sh->sh_sopool);
553 LDAP_LIST_REMOVE(so, so_link);
554 so->so_ptr = tmpp;
555 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
556 so, so_link);
557 break;
558
559 Debug(LDAP_DEBUG_TRACE, "slap_sl_free: "
560 "free object not found while bit is clear.\n",
561 0, 0, 0 );
562 assert(so != NULL);
563
564 }
565 } else {
566 if ( !inserted ) {
567 if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
568 slap_replenish_sopool(sh);
569 }
570 so = LDAP_LIST_FIRST(&sh->sh_sopool);
571 LDAP_LIST_REMOVE(so, so_link);
572 so->so_ptr = tmpp;
573 LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
574 so, so_link);
575 }
576 break;
577 }
578 }
579 }
580 }
581 }
582
583 void *
584 slap_sl_context( void *ptr )
585 {
586 struct slab_heap *sh;
587 void *ctx, *sh_tmp;
588
589 if ( slapMode & SLAP_TOOL_MODE ) return NULL;
590
591 #ifdef NO_THREADS
592 sh = slheap;
593 #else
594 ctx = ldap_pvt_thread_pool_context();
595
596 sh_tmp = NULL;
597 ldap_pvt_thread_pool_getkey(
598 ctx, (void *)slap_sl_mem_init, &sh_tmp, NULL);
599 sh = sh_tmp;
600 #endif
601
602 if (sh && ptr >= sh->sh_base && ptr <= sh->sh_end) {
603 return sh;
604 }
605 return NULL;
606 }
607
608 static struct slab_object *
609 slap_replenish_sopool(
610 struct slab_heap* sh
611 )
612 {
613 struct slab_object *so_block;
614 int i;
615
616 so_block = (struct slab_object *)ch_malloc(
617 SLAP_SLAB_SOBLOCK * sizeof(struct slab_object));
618
619 if ( so_block == NULL ) {
620 return NULL;
621 }
622
623 so_block[0].so_blockhead = 1;
624 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, &so_block[0], so_link);
625 for (i = 1; i < SLAP_SLAB_SOBLOCK; i++) {
626 so_block[i].so_blockhead = 0;
627 LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, &so_block[i], so_link );
628 }
629
630 return so_block;
631 }
632
633 #ifdef SLAPD_UNUSED
634 static void
635 print_slheap(int level, void *ctx)
636 {
637 struct slab_heap *sh = ctx;
638 int order_start = -1;
639 int pad = 2*sizeof(int)-1, pad_shift;
640 struct slab_object *so;
641 int i, j, once = 0;
642
643 if (!ctx) {
644 Debug(level, "NULL memctx\n", 0, 0, 0);
645 return;
646 }
647
648 pad_shift = pad - 1;
649 do {
650 order_start++;
651 } while (pad_shift >>= 1);
652
653 Debug(level, "sh->sh_maxorder=%d\n", sh->sh_maxorder, 0, 0);
654
655 for (i = order_start; i <= sh->sh_maxorder; i++) {
656 once = 0;
657 Debug(level, "order=%d\n", i, 0, 0);
658 for (j = 0; j < (1<<(sh->sh_maxorder-i))/8; j++) {
659 Debug(level, "%02x ", sh->sh_map[i-order_start][j], 0, 0);
660 once = 1;
661 }
662 if (!once) {
663 Debug(level, "%02x ", sh->sh_map[i-order_start][0], 0, 0);
664 }
665 Debug(level, "\n", 0, 0, 0);
666 Debug(level, "free list:\n", 0, 0, 0);
667 so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
668 while (so) {
669 Debug(level, "%lx\n", (unsigned long) so->so_ptr, 0, 0);
670 so = LDAP_LIST_NEXT(so, so_link);
671 }
672 }
673 }
674 #endif
NetBSD on the FriendlyARM MINI2440