sl_malloc.c 18.8 KB
Newer Older
1
2
/* sl_malloc.c - malloc routines using a per-thread slab */
/* $OpenLDAP$ */
Kurt Zeilenga's avatar
Kurt Zeilenga committed
3
4
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
5
 * Copyright 2003-2020 The OpenLDAP Foundation.
Kurt Zeilenga's avatar
Kurt Zeilenga committed
6
7
8
9
10
11
12
13
14
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted only as authorized by the OpenLDAP
 * Public License.
 *
 * A copy of this license is available in the file LICENSE in the
 * top-level directory of the distribution or, alternatively, at
 * <http://www.OpenLDAP.org/license.html>.
15
16
17
18
19
20
21
22
23
 */

#include "portable.h"

#include <stdio.h>
#include <ac/string.h>

#include "slap.h"

Howard Chu's avatar
Howard Chu committed
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#ifdef USE_VALGRIND
/* Get debugging help from Valgrind */
#include <valgrind/memcheck.h>
#define	VGMEMP_MARK(m,s)	VALGRIND_MAKE_MEM_NOACCESS(m,s)
#define VGMEMP_CREATE(h,r,z)	VALGRIND_CREATE_MEMPOOL(h,r,z)
#define VGMEMP_TRIM(h,a,s)	VALGRIND_MEMPOOL_TRIM(h,a,s)
#define VGMEMP_ALLOC(h,a,s)	VALGRIND_MEMPOOL_ALLOC(h,a,s)
#define VGMEMP_CHANGE(h,a,b,s)	VALGRIND_MEMPOOL_CHANGE(h,a,b,s)
#else
#define	VGMEMP_MARK(m,s)
#define VGMEMP_CREATE(h,r,z)
#define VGMEMP_TRIM(h,a,s)
#define VGMEMP_ALLOC(h,a,s)
#define VGMEMP_CHANGE(h,a,b,s)
#endif

Hallvard Furuseth's avatar
Hallvard Furuseth committed
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*
 * This allocator returns temporary memory from a slab in a given memory
 * context, aligned on a 2-int boundary.  It cannot be used for data
 * which will outlive the task allocating it.
 *
 * A new memory context attaches to the creator's thread context, if any.
 * Threads cannot use other threads' memory contexts; there are no locks.
 *
 * The caller of slap_sl_malloc, usually a thread pool task, must
 * slap_sl_free the memory before finishing: New tasks reuse the context
 * and normally reset it, reclaiming memory left over from last task.
 *
 * The allocator helps memory fragmentation, speed and memory leaks.
 * It is not (yet) reliable as a garbage collector:
 *
 * It falls back to context NULL - plain ber_memalloc() - when the
 * context's slab is full.  A reset does not reclaim such memory.
 * Conversely, free/realloc of data not from the given context assumes
 * context NULL.  The data must not belong to another memory context.
 *
 * Code which has lost track of the current memory context can try
 * slap_sl_context() or ch_malloc.c:ch_free/ch_realloc().
 *
 * Allocations cannot yet return failure.  Like ch_malloc, they succeed
 * or abort slapd.  This will change, do fix code which assumes success.
 */

/*
 * The stack-based allocator stores (ber_len_t)sizeof(head+block) at
69
70
 * allocated blocks' head - and in freed blocks also at the tail, marked
 * by ORing *next* block's head with 1.  Freed blocks are only reclaimed
Hallvard Furuseth's avatar
Hallvard Furuseth committed
71
72
73
74
 * from the last block forward.  This is fast, but when a block is never
 * freed, older blocks will not be reclaimed until the slab is reset...
 */

75
76
77
78
79
80
#ifdef SLAP_NO_SL_MALLOC /* Useful with memory debuggers like Valgrind */
enum { No_sl_malloc = 1 };
#else
enum { No_sl_malloc = 0 };
#endif

81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#define SLAP_SLAB_SOBLOCK 64

struct slab_object {
    void *so_ptr;
	int so_blockhead;
    LDAP_LIST_ENTRY(slab_object) so_link;
};

struct slab_heap {
    void *sh_base;
    void *sh_last;
    void *sh_end;
	int sh_stack;
	int sh_maxorder;
    unsigned char **sh_map;
    LDAP_LIST_HEAD(sh_freelist, slab_object) *sh_free;
	LDAP_LIST_HEAD(sh_so, slab_object) sh_sopool;
};

100
enum {
101
102
	Align = sizeof(ber_len_t) > 2*sizeof(int)
		? sizeof(ber_len_t) : 2*sizeof(int),
103
104
105
106
107
	Align_log2 = 1 + (Align>2) + (Align>4) + (Align>8) + (Align>16),
	order_start = Align_log2 - 1,
	pad = Align - 1
};

Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
108
static struct slab_object * slap_replenish_sopool(struct slab_heap* sh);
Pierangelo Masarati's avatar
Pierangelo Masarati committed
109
#ifdef SLAPD_UNUSED
110
static void print_slheap(int level, void *ctx);
Pierangelo Masarati's avatar
Pierangelo Masarati committed
111
#endif
112

113
/* Keep memory context in a thread-local var */
114
115
116
117
118
119
120
121
# define memctx_key ((void *) slap_sl_mem_init)
# define SET_MEMCTX(thrctx, memctx, kfree) \
	ldap_pvt_thread_pool_setkey(thrctx,memctx_key, memctx,kfree, NULL,NULL)
# define GET_MEMCTX(thrctx, memctxp) \
	((void) (*(memctxp) = NULL), \
	 (void) ldap_pvt_thread_pool_getkey(thrctx,memctx_key, memctxp,NULL), \
	 *(memctxp))

122
/* Destroy the context, or if key==NULL clean it up for reuse. */
123
void
124
slap_sl_mem_destroy(
125
126
127
128
129
	void *key,
	void *data
)
{
	struct slab_heap *sh = data;
130
	struct slab_object *so;
131
	int i;
132

133
134
135
	if (!sh)
		return;

136
	if (!sh->sh_stack) {
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
		for (i = 0; i <= sh->sh_maxorder - order_start; i++) {
			so = LDAP_LIST_FIRST(&sh->sh_free[i]);
			while (so) {
				struct slab_object *so_tmp = so;
				so = LDAP_LIST_NEXT(so, so_link);
				LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_tmp, so_link);
			}
			ch_free(sh->sh_map[i]);
		}
		ch_free(sh->sh_free);
		ch_free(sh->sh_map);

		so = LDAP_LIST_FIRST(&sh->sh_sopool);
		while (so) {
			struct slab_object *so_tmp = so;
			so = LDAP_LIST_NEXT(so, so_link);
			if (!so_tmp->so_blockhead) {
				LDAP_LIST_REMOVE(so_tmp, so_link);
			}
		}
		so = LDAP_LIST_FIRST(&sh->sh_sopool);
		while (so) {
			struct slab_object *so_tmp = so;
			so = LDAP_LIST_NEXT(so, so_link);
			ch_free(so_tmp);
		}
163
164
165
	}

	if (key != NULL) {
166
167
168
		ber_memfree_x(sh->sh_base, NULL);
		ber_memfree_x(sh, NULL);
	}
169
170
}

171
172
BerMemoryFunctions slap_sl_mfuncs =
	{ slap_sl_malloc, slap_sl_calloc, slap_sl_realloc, slap_sl_free };
173
174

void
175
slap_sl_mem_init()
176
{
177
178
	assert( Align == 1 << Align_log2 );

179
	ber_set_option( NULL, LBER_OPT_MEMORY_FNS, &slap_sl_mfuncs );
180
181
}

Hallvard Furuseth's avatar
Hallvard Furuseth committed
182
/* Create, reset or just return the memory context of the current thread. */
Howard Chu's avatar
Howard Chu committed
183
void *
184
slap_sl_mem_create(
185
	ber_len_t size,
186
	int stack,
187
	void *thrctx,
188
	int new
189
190
)
{
191
	void *memctx;
192
	struct slab_heap *sh;
193
	ber_len_t size_shift;
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
194
	struct slab_object *so;
195
	char *base, *newptr;
196
	enum { Base_offset = (unsigned) -sizeof(ber_len_t) % Align };
197

198
	sh = GET_MEMCTX(thrctx, &memctx);
Howard Chu's avatar
Cleanup    
Howard Chu committed
199
	if ( sh && !new )
200
201
		return sh;

202
203
204
	/* Round up to doubleword boundary, then make room for initial
	 * padding, preserving expected available size for pool version */
	size = ((size + Align-1) & -Align) + Base_offset;
205

206
	if (!sh) {
207
		sh = ch_malloc(sizeof(struct slab_heap));
208
		base = ch_malloc(size);
209
		SET_MEMCTX(thrctx, sh, slap_sl_mem_destroy);
Howard Chu's avatar
Howard Chu committed
210
211
		VGMEMP_MARK(base, size);
		VGMEMP_CREATE(sh, 0, 0);
212
213
	} else {
		slap_sl_mem_destroy(NULL, sh);
214
215
216
		base = sh->sh_base;
		if (size > (ber_len_t) ((char *) sh->sh_end - base)) {
			newptr = ch_realloc(base, size);
217
			if ( newptr == NULL ) return NULL;
Howard Chu's avatar
Howard Chu committed
218
			VGMEMP_CHANGE(sh, base, newptr, size);
219
			base = newptr;
220
		}
221
		VGMEMP_TRIM(sh, base, 0);
222
	}
223
224
225
226
227
228
	sh->sh_base = base;
	sh->sh_end = base + size;

	/* Align (base + head of first block) == first returned block */
	base += Base_offset;
	size -= Base_offset;
229
230
231

	sh->sh_stack = stack;
	if (stack) {
232
		sh->sh_last = base;
233

234
	} else {
235
236
		int i, order = -1, order_end = -1;

237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
		size_shift = size - 1;
		do {
			order_end++;
		} while (size_shift >>= 1);
		order = order_end - order_start + 1;
		sh->sh_maxorder = order_end;

		sh->sh_free = (struct sh_freelist *)
						ch_malloc(order * sizeof(struct sh_freelist));
		for (i = 0; i < order; i++) {
			LDAP_LIST_INIT(&sh->sh_free[i]);
		}

		LDAP_LIST_INIT(&sh->sh_sopool);

		if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
253
			slap_replenish_sopool(sh);
254
		}
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
255
256
		so = LDAP_LIST_FIRST(&sh->sh_sopool);
		LDAP_LIST_REMOVE(so, so_link);
257
		so->so_ptr = base;
258
259
260
261

		LDAP_LIST_INSERT_HEAD(&sh->sh_free[order-1], so, so_link);

		sh->sh_map = (unsigned char **)
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
262
					ch_malloc(order * sizeof(unsigned char *));
263
		for (i = 0; i < order; i++) {
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
264
265
266
267
268
269
270
			int shiftamt = order_start + 1 + i;
			int nummaps = size >> shiftamt;
			assert(nummaps);
			nummaps >>= 3;
			if (!nummaps) nummaps = 1;
			sh->sh_map[i] = (unsigned char *) ch_malloc(nummaps);
			memset(sh->sh_map[i], 0, nummaps);
271
		}
272
	}
273

274
	return sh;
275
276
}

Hallvard Furuseth's avatar
Hallvard Furuseth committed
277
/*
278
279
 * Assign memory context to thread context. Use NULL to detach
 * current memory context from thread. Future users must
Hallvard Furuseth's avatar
Hallvard Furuseth committed
280
281
 * know the context, since ch_free/slap_sl_context() cannot find it.
 */
282
void
283
slap_sl_mem_setctx(
284
	void *thrctx,
285
286
287
	void *memctx
)
{
288
	SET_MEMCTX(thrctx, memctx, slap_sl_mem_destroy);
289
290
}

291
void *
292
slap_sl_malloc(
293
294
295
296
    ber_len_t	size,
    void *ctx
)
{
Howard Chu's avatar
Howard Chu committed
297
	struct slab_heap *sh = ctx;
298
	ber_len_t *ptr, *newptr;
299
300

	/* ber_set_option calls us like this */
301
	if (No_sl_malloc || !ctx) {
302
303
		newptr = ber_memalloc_x( size, NULL );
		if ( newptr ) return newptr;
304
		Debug(LDAP_DEBUG_ANY, "slap_sl_malloc of %lu bytes failed\n",
305
			(unsigned long) size );
306
307
308
		assert( 0 );
		exit( EXIT_FAILURE );
	}
309

310
311
312
	/* Add room for head, ensure room for tail when freed, and
	 * round up to doubleword boundary. */
	size = (size + sizeof(ber_len_t) + Align-1 + !size) & -Align;
313

314
	if (sh->sh_stack) {
315
316
317
		if (size < (ber_len_t) ((char *) sh->sh_end - (char *) sh->sh_last)) {
			newptr = sh->sh_last;
			sh->sh_last = (char *) sh->sh_last + size;
Howard Chu's avatar
Howard Chu committed
318
			VGMEMP_ALLOC(sh, newptr, size);
319
320
			*newptr++ = size;
			return( (void *)newptr );
321
		}
322

323
		size -= sizeof(ber_len_t);
324

325
	} else {
326
327
328
		struct slab_object *so_new, *so_left, *so_right;
		ber_len_t size_shift;
		unsigned long diff;
329
		int i, j, order = -1;
330

331
332
333
334
335
		size_shift = size - 1;
		do {
			order++;
		} while (size_shift >>= 1);

336
337
		size -= sizeof(ber_len_t);

338
339
340
341
342
343
344
345
346
347
		for (i = order; i <= sh->sh_maxorder &&
				LDAP_LIST_EMPTY(&sh->sh_free[i-order_start]); i++);

		if (i == order) {
			so_new = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
			LDAP_LIST_REMOVE(so_new, so_link);
			ptr = so_new->so_ptr;
			diff = (unsigned long)((char*)ptr -
					(char*)sh->sh_base) >> (order + 1);
			sh->sh_map[order-order_start][diff>>3] |= (1 << (diff & 0x7));
348
			*ptr++ = size;
349
350
351
352
353
354
355
			LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_new, so_link);
			return((void*)ptr);
		} else if (i <= sh->sh_maxorder) {
			for (j = i; j > order; j--) {
				so_left = LDAP_LIST_FIRST(&sh->sh_free[j-order_start]);
				LDAP_LIST_REMOVE(so_left, so_link);
				if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
356
					slap_replenish_sopool(sh);
357
				}
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
358
359
				so_right = LDAP_LIST_FIRST(&sh->sh_sopool);
				LDAP_LIST_REMOVE(so_right, so_link);
360
				so_right->so_ptr = (void *)((char *)so_left->so_ptr + (1 << j));
361
362
363
364
365
366
				if (j == order + 1) {
					ptr = so_left->so_ptr;
					diff = (unsigned long)((char*)ptr -
							(char*)sh->sh_base) >> (order+1);
					sh->sh_map[order-order_start][diff>>3] |=
							(1 << (diff & 0x7));
367
					*ptr++ = size;
368
369
370
371
372
373
374
375
376
377
378
379
					LDAP_LIST_INSERT_HEAD(
							&sh->sh_free[j-1-order_start], so_right, so_link);
					LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, so_left, so_link);
					return((void*)ptr);
				} else {
					LDAP_LIST_INSERT_HEAD(
							&sh->sh_free[j-1-order_start], so_right, so_link);
					LDAP_LIST_INSERT_HEAD(
							&sh->sh_free[j-1-order_start], so_left, so_link);
				}
			}
		}
380
		/* FIXME: missing return; guessing we failed... */
381
	}
382

383
	Debug(LDAP_DEBUG_TRACE,
384
		"sl_malloc %lu: ch_malloc\n",
385
		(unsigned long) size );
386
	return ch_malloc(size);
387
388
}

389
390
391
392
#define LIM_SQRT(t) /* some value < sqrt(max value of unsigned type t) */ \
	((0UL|(t)-1) >>31>>31 > 1 ? ((t)1 <<32) - 1 : \
	 (0UL|(t)-1) >>31 ? 65535U : (0UL|(t)-1) >>15 ? 255U : 15U)

393
void *
394
slap_sl_calloc( ber_len_t n, ber_len_t size, void *ctx )
395
{
396
	void *newptr;
397
	ber_len_t total = n * size;
398

399
400
401
	/* The sqrt test is a slight optimization: often avoids the division */
	if ((n | size) <= LIM_SQRT(ber_len_t) || n == 0 || total/n == size) {
		newptr = slap_sl_malloc( total, ctx );
402
		memset( newptr, 0, n*size );
403
404
	} else {
		Debug(LDAP_DEBUG_ANY, "slap_sl_calloc(%lu,%lu) out of range\n",
405
			(unsigned long) n, (unsigned long) size );
406
407
		assert(0);
		exit(EXIT_FAILURE);
408
	}
409
	return newptr;
410
411
412
}

void *
413
slap_sl_realloc(void *ptr, ber_len_t size, void *ctx)
414
{
Howard Chu's avatar
Howard Chu committed
415
	struct slab_heap *sh = ctx;
416
	ber_len_t oldsize, *p = (ber_len_t *) ptr, *nextp;
417
	void *newptr;
418

419
420
	if (ptr == NULL)
		return slap_sl_malloc(size, ctx);
421

Howard Chu's avatar
Howard Chu committed
422
	/* Not our memory? */
423
	if (No_sl_malloc || !sh || ptr < sh->sh_base || ptr >= sh->sh_end) {
424
		/* Like ch_realloc(), except not trying a new context */
425
426
427
		newptr = ber_memrealloc_x(ptr, size, NULL);
		if (newptr) {
			return newptr;
428
		}
429
		Debug(LDAP_DEBUG_ANY, "slap_sl_realloc of %lu bytes failed\n",
430
			(unsigned long) size );
431
		assert(0);
432
		exit( EXIT_FAILURE );
433
434
	}

435
436
	if (size == 0) {
		slap_sl_free(ptr, ctx);
437
438
		return NULL;
	}
439

440
441
	oldsize = p[-1];

442
	if (sh->sh_stack) {
443
444
		/* Add room for head, round up to doubleword boundary */
		size = (size + sizeof(ber_len_t) + Align-1) & -Align;
445

Howard Chu's avatar
Cleanup    
Howard Chu committed
446
447
		p--;

448
		/* Never shrink blocks */
449
450
		if (size <= oldsize) {
			return ptr;
451
		}
452
	
453
454
455
		oldsize &= -2;
		nextp = (ber_len_t *) ((char *) p + oldsize);

456
		/* If reallocing the last block, try to grow it */
457
458
459
460
		if (nextp == sh->sh_last) {
			if (size < (ber_len_t) ((char *) sh->sh_end - (char *) p)) {
				sh->sh_last = (char *) p + size;
				p[0] = (p[0] & 1) | size;
461
462
				return ptr;
			}
Howard Chu's avatar
Cleanup    
Howard Chu committed
463

464
465
		/* Nowhere to grow, need to alloc and copy */
		} else {
466
			/* Slight optimization of the final realloc variant */
467
468
			newptr = slap_sl_malloc(size-sizeof(ber_len_t), ctx);
			AC_MEMCPY(newptr, ptr, oldsize-sizeof(ber_len_t));
469
			/* Not last block, can just mark old region as free */
470
471
			nextp[-1] = oldsize;
			nextp[0] |= 1;
472
			return newptr;
473
		}
474

475
476
477
478
479
		size -= sizeof(ber_len_t);
		oldsize -= sizeof(ber_len_t);

	} else if (oldsize > size) {
		oldsize = size;
480
	}
481
482
483
484
485

	newptr = slap_sl_malloc(size, ctx);
	AC_MEMCPY(newptr, ptr, oldsize);
	slap_sl_free(ptr, ctx);
	return newptr;
486
487
488
}

void
489
slap_sl_free(void *ptr, void *ctx)
490
{
Howard Chu's avatar
Howard Chu committed
491
	struct slab_heap *sh = ctx;
Howard Chu's avatar
Cleanup    
Howard Chu committed
492
	ber_len_t size;
493
	ber_len_t *p = ptr, *nextp, *tmpp;
494

Howard Chu's avatar
Cleanup    
Howard Chu committed
495
496
497
	if (!ptr)
		return;

498
	if (No_sl_malloc || !sh || ptr < sh->sh_base || ptr >= sh->sh_end) {
499
		ber_memfree_x(ptr, NULL);
500
501
502
503
		return;
	}

	size = *(--p);
504

505
506
507
508
509
510
511
	if (sh->sh_stack) {
		size &= -2;
		nextp = (ber_len_t *) ((char *) p + size);
		if (sh->sh_last != nextp) {
			/* Mark it free: tail = size, head of next block |= 1 */
			nextp[-1] = size;
			nextp[0] |= 1;
Howard Chu's avatar
Howard Chu committed
512
513
514
515
			/* We can't tell Valgrind about it yet, because we
			 * still need read/write access to this block for
			 * when we eventually get to reclaim it.
			 */
516
517
518
519
520
		} else {
			/* Reclaim freed block(s) off tail */
			while (*p & 1) {
				p = (ber_len_t *) ((char *) p - p[-1]);
			}
521
			sh->sh_last = p;
522
523
			VGMEMP_TRIM(sh, sh->sh_base,
				(char *) sh->sh_last - (char *) sh->sh_base);
524
		}
525

526
	} else {
Howard Chu's avatar
Cleanup    
Howard Chu committed
527
528
529
		int size_shift, order_size;
		struct slab_object *so;
		unsigned long diff;
530
		int i, inserted = 0, order = -1;
Howard Chu's avatar
Cleanup    
Howard Chu committed
531

532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
		size_shift = size + sizeof(ber_len_t) - 1;
		do {
			order++;
		} while (size_shift >>= 1);

		for (i = order, tmpp = p; i <= sh->sh_maxorder; i++) {
			order_size = 1 << (i+1);
			diff = (unsigned long)((char*)tmpp - (char*)sh->sh_base) >> (i+1);
			sh->sh_map[i-order_start][diff>>3] &= (~(1 << (diff & 0x7)));
			if (diff == ((diff>>1)<<1)) {
				if (!(sh->sh_map[i-order_start][(diff+1)>>3] &
						(1<<((diff+1)&0x7)))) {
					so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
					while (so) {
						if ((char*)so->so_ptr == (char*)tmpp) {
							LDAP_LIST_REMOVE( so, so_link );
						} else if ((char*)so->so_ptr ==
								(char*)tmpp + order_size) {
							LDAP_LIST_REMOVE(so, so_link);
							break;
						}
						so = LDAP_LIST_NEXT(so, so_link);
					}
					if (so) {
						if (i < sh->sh_maxorder) {
							inserted = 1;
							so->so_ptr = tmpp;
							LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start+1],
									so, so_link);
						}
						continue;
					} else {
						if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
565
							slap_replenish_sopool(sh);
566
						}
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
567
568
569
						so = LDAP_LIST_FIRST(&sh->sh_sopool);
						LDAP_LIST_REMOVE(so, so_link);
						so->so_ptr = tmpp;
570
571
572
573
						LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
								so, so_link);
						break;

Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
574
						Debug(LDAP_DEBUG_TRACE, "slap_sl_free: "
575
							"free object not found while bit is clear.\n" );
576
						assert(so != NULL);
577
578
579
580
581

					}
				} else {
					if (!inserted) {
						if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
582
							slap_replenish_sopool(sh);
583
						}
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
584
585
586
						so = LDAP_LIST_FIRST(&sh->sh_sopool);
						LDAP_LIST_REMOVE(so, so_link);
						so->so_ptr = tmpp;
587
588
589
590
591
592
593
594
595
596
597
598
						LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
								so, so_link);
					}
					break;
				}
			} else {
				if (!(sh->sh_map[i-order_start][(diff-1)>>3] &
						(1<<((diff-1)&0x7)))) {
					so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
					while (so) {
						if ((char*)so->so_ptr == (char*)tmpp) {
							LDAP_LIST_REMOVE(so, so_link);
599
						} else if ((char*)tmpp == (char *)so->so_ptr + order_size) {
600
601
602
603
604
605
606
607
608
609
610
611
612
613
							LDAP_LIST_REMOVE(so, so_link);
							tmpp = so->so_ptr;
							break;
						}
						so = LDAP_LIST_NEXT(so, so_link);
					}
					if (so) {
						if (i < sh->sh_maxorder) {
							inserted = 1;
							LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start+1],									so, so_link);
							continue;
						}
					} else {
						if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
614
							slap_replenish_sopool(sh);
615
						}
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
616
617
618
						so = LDAP_LIST_FIRST(&sh->sh_sopool);
						LDAP_LIST_REMOVE(so, so_link);
						so->so_ptr = tmpp;
619
620
621
622
						LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
								so, so_link);
						break;

Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
623
						Debug(LDAP_DEBUG_TRACE, "slap_sl_free: "
624
							"free object not found while bit is clear.\n" );
625
						assert(so != NULL);
626
627
628
629
630

					}
				} else {
					if ( !inserted ) {
						if (LDAP_LIST_EMPTY(&sh->sh_sopool)) {
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
631
							slap_replenish_sopool(sh);
632
						}
Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
633
634
635
						so = LDAP_LIST_FIRST(&sh->sh_sopool);
						LDAP_LIST_REMOVE(so, so_link);
						so->so_ptr = tmpp;
636
637
638
639
640
641
642
						LDAP_LIST_INSERT_HEAD(&sh->sh_free[i-order_start],
								so, so_link);
					}
					break;
				}
			}
		}
643
644
	}
}
Howard Chu's avatar
Howard Chu committed
645

646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
void
slap_sl_release( void *ptr, void *ctx )
{
	struct slab_heap *sh = ctx;
	if ( sh && ptr >= sh->sh_base && ptr <= sh->sh_end )
		sh->sh_last = ptr;
}

void *
slap_sl_mark( void *ctx )
{
	struct slab_heap *sh = ctx;
	return sh->sh_last;
}

Hallvard Furuseth's avatar
Hallvard Furuseth committed
661
662
663
664
/*
 * Return the memory context of the current thread if the given block of
 * memory belongs to it, otherwise return NULL.
 */
665
void *
666
slap_sl_context( void *ptr )
667
{
668
	void *memctx;
669
	struct slab_heap *sh;
670

671
672
	if ( slapMode & SLAP_TOOL_MODE ) return NULL;

673
	sh = GET_MEMCTX(ldap_pvt_thread_pool_context(), &memctx);
674
	if (sh && ptr >= sh->sh_base && ptr <= sh->sh_end) {
675
676
677
678
		return sh;
	}
	return NULL;
}
679

Jong Hyuk Choi's avatar
Jong Hyuk Choi committed
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
static struct slab_object *
slap_replenish_sopool(
    struct slab_heap* sh
)
{
    struct slab_object *so_block;
    int i;

    so_block = (struct slab_object *)ch_malloc(
                    SLAP_SLAB_SOBLOCK * sizeof(struct slab_object));

    if ( so_block == NULL ) {
        return NULL;
    }

    so_block[0].so_blockhead = 1;
    LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, &so_block[0], so_link);
    for (i = 1; i < SLAP_SLAB_SOBLOCK; i++) {
        so_block[i].so_blockhead = 0;
        LDAP_LIST_INSERT_HEAD(&sh->sh_sopool, &so_block[i], so_link );
    }

    return so_block;
}

Pierangelo Masarati's avatar
Pierangelo Masarati committed
705
#ifdef SLAPD_UNUSED
706
707
708
709
710
711
712
713
static void
print_slheap(int level, void *ctx)
{
	struct slab_heap *sh = ctx;
	struct slab_object *so;
	int i, j, once = 0;

	if (!ctx) {
714
		Debug(level, "NULL memctx\n" );
715
716
717
		return;
	}

718
	Debug(level, "sh->sh_maxorder=%d\n", sh->sh_maxorder );
719
720
721

	for (i = order_start; i <= sh->sh_maxorder; i++) {
		once = 0;
722
		Debug(level, "order=%d\n", i );
723
		for (j = 0; j < (1<<(sh->sh_maxorder-i))/8; j++) {
724
			Debug(level, "%02x ", sh->sh_map[i-order_start][j] );
725
726
727
			once = 1;
		}
		if (!once) {
728
			Debug(level, "%02x ", sh->sh_map[i-order_start][0] );
729
		}
730
731
		Debug(level, "\n" );
		Debug(level, "free list:\n" );
732
733
		so = LDAP_LIST_FIRST(&sh->sh_free[i-order_start]);
		while (so) {
734
			Debug(level, "%p\n", so->so_ptr );
735
736
737
738
			so = LDAP_LIST_NEXT(so, so_link);
		}
	}
}
Pierangelo Masarati's avatar
Pierangelo Masarati committed
739
#endif