mem.c 40.4 KB
Newer Older
Bob Halley's avatar
base  
Bob Halley committed
1
/*
Mark Andrews's avatar
Mark Andrews committed
2
 * Copyright (C) 2004, 2005  Internet Systems Consortium, Inc. ("ISC")
Mark Andrews's avatar
Mark Andrews committed
3
 * Copyright (C) 1997-2003  Internet Software Consortium.
4
 *
Bob Halley's avatar
base  
Bob Halley committed
5 6 7
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
8
 *
Mark Andrews's avatar
Mark Andrews committed
9 10 11 12 13 14 15
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
Bob Halley's avatar
base  
Bob Halley committed
16 17
 */

Mark Andrews's avatar
Mark Andrews committed
18
/* $Id: mem.c,v 1.124 2005/08/23 04:05:50 marka Exp $ */
19 20

/*! \file */
David Lawrence's avatar
David Lawrence committed
21

Bob Halley's avatar
Bob Halley committed
22
#include <config.h>
Bob Halley's avatar
base  
Bob Halley committed
23 24 25

#include <stdio.h>
#include <stdlib.h>
Bob Halley's avatar
Bob Halley committed
26
#include <stddef.h>
Bob Halley's avatar
base  
Bob Halley committed
27

Michael Graff's avatar
Michael Graff committed
28 29
#include <limits.h>

30
#include <isc/magic.h>
Bob Halley's avatar
Bob Halley committed
31
#include <isc/mem.h>
32
#include <isc/msgs.h>
33
#include <isc/ondestroy.h>
34
#include <isc/string.h>
Bob Halley's avatar
Bob Halley committed
35

Bob Halley's avatar
update  
Bob Halley committed
36
#include <isc/mutex.h>
Michael Graff's avatar
Michael Graff committed
37
#include <isc/util.h>
Bob Halley's avatar
update  
Bob Halley committed
38

39 40 41
#define MCTXLOCK(m, l) if (((m)->flags & ISC_MEMFLAG_NOLOCK) == 0) LOCK(l)
#define MCTXUNLOCK(m, l) if (((m)->flags & ISC_MEMFLAG_NOLOCK) == 0) UNLOCK(l)

42 43 44
#ifndef ISC_MEM_DEBUGGING
#define ISC_MEM_DEBUGGING 0
#endif
45
LIBISC_EXTERNAL_DATA unsigned int isc_mem_debugging = ISC_MEM_DEBUGGING;
46 47 48 49 50 51 52

/*
 * Constants.
 */

#define DEF_MAX_SIZE		1100
#define DEF_MEM_TARGET		4096
53 54
#define ALIGNMENT_SIZE		8		/*%< must be a power of 2 */
#define NUM_BASIC_BLOCKS	64		/*%< must be > 1 */
55
#define TABLE_INCREMENT		1024
Michael Graff's avatar
Michael Graff committed
56
#define DEBUGLIST_COUNT		1024
57

Bob Halley's avatar
base  
Bob Halley committed
58 59 60
/*
 * Types.
 */
61
#if ISC_MEM_TRACKLINES
Michael Graff's avatar
Michael Graff committed
62 63 64 65
typedef struct debuglink debuglink_t;
struct debuglink {
	ISC_LINK(debuglink_t)	link;
	const void	       *ptr[DEBUGLIST_COUNT];
66
	unsigned int		size[DEBUGLIST_COUNT];
Michael Graff's avatar
Michael Graff committed
67 68 69 70
	const char	       *file[DEBUGLIST_COUNT];
	unsigned int		line[DEBUGLIST_COUNT];
	unsigned int		count;
};
Bob Halley's avatar
base  
Bob Halley committed
71

Michael Graff's avatar
Michael Graff committed
72 73 74 75 76 77
#define FLARG_PASS	, file, line
#define FLARG		, const char *file, int line
#else
#define FLARG_PASS
#define FLARG
#endif
78

Michael Graff's avatar
Michael Graff committed
79
typedef struct element element;
80 81 82
struct element {
	element *		next;
};
Bob Halley's avatar
base  
Bob Halley committed
83 84

typedef struct {
85
	/*!
Bob Halley's avatar
base  
Bob Halley committed
86 87
	 * This structure must be ALIGNMENT_SIZE bytes.
	 */
88 89
	union {
		size_t		size;
90
		isc_mem_t	*ctx;
91 92
		char		bytes[ALIGNMENT_SIZE];
	} u;
Bob Halley's avatar
Bob Halley committed
93
} size_info;
Bob Halley's avatar
base  
Bob Halley committed
94 95

struct stats {
Bob Halley's avatar
Bob Halley committed
96 97 98 99
	unsigned long		gets;
	unsigned long		totalgets;
	unsigned long		blocks;
	unsigned long		freefrags;
Bob Halley's avatar
base  
Bob Halley committed
100 101
};

102 103
#define MEM_MAGIC		ISC_MAGIC('M', 'e', 'm', 'C')
#define VALID_CONTEXT(c)	ISC_MAGIC_VALID(c, MEM_MAGIC)
Bob Halley's avatar
Bob Halley committed
104

105
#if ISC_MEM_TRACKLINES
106
typedef ISC_LIST(debuglink_t)	debuglist_t;
107
#endif
108

109
struct isc_mem {
Bob Halley's avatar
Bob Halley committed
110
	unsigned int		magic;
111
	isc_ondestroy_t		ondestroy;
112
	unsigned int		flags;
Bob Halley's avatar
Bob Halley committed
113
	isc_mutex_t		lock;
114 115 116
	isc_memalloc_t		memalloc;
	isc_memfree_t		memfree;
	void *			arg;
Bob Halley's avatar
base  
Bob Halley committed
117
	size_t			max_size;
118
	isc_boolean_t		checkfree;
Bob Halley's avatar
base  
Bob Halley committed
119
	struct stats *		stats;
120
	unsigned int		references;
121
	size_t			quota;
Bob Halley's avatar
Bob Halley committed
122
	size_t			total;
123
	size_t			inuse;
124
	size_t			maxinuse;
125 126 127 128 129
	size_t			hi_water;
	size_t			lo_water;
	isc_boolean_t		hi_called;
	isc_mem_water_t		water;
	void *			water_arg;
Michael Graff's avatar
Michael Graff committed
130
	ISC_LIST(isc_mempool_t)	pools;
131

132
	/*  ISC_MEMFLAG_INTERNAL */
133 134 135 136 137 138 139 140 141
	size_t			mem_target;
	element **		freelists;
	element *		basic_blocks;
	unsigned char **	basic_table;
	unsigned int		basic_table_count;
	unsigned int		basic_table_size;
	unsigned char *		lowest;
	unsigned char *		highest;

142
#if ISC_MEM_TRACKLINES
143
	debuglist_t *	 	debuglist;
Michael Graff's avatar
Michael Graff committed
144
#endif
145 146

	unsigned int		memalloc_failures;
Michael Graff's avatar
Michael Graff committed
147 148
};

149 150
#define MEMPOOL_MAGIC		ISC_MAGIC('M', 'E', 'M', 'p')
#define VALID_MEMPOOL(c)	ISC_MAGIC_VALID(c, MEMPOOL_MAGIC)
Michael Graff's avatar
Michael Graff committed
151 152

struct isc_mempool {
Michael Graff's avatar
Michael Graff committed
153
	/* always unlocked */
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
	unsigned int	magic;		/*%< magic number */
	isc_mutex_t    *lock;		/*%< optional lock */
	isc_mem_t      *mctx;		/*%< our memory context */
	/*%< locked via the memory context's lock */
	ISC_LINK(isc_mempool_t)	link;	/*%< next pool in this mem context */
	/*%< optionally locked from here down */
	element	       *items;		/*%< low water item list */
	size_t		size;		/*%< size of each item on this pool */
	unsigned int	maxalloc;	/*%< max number of items allowed */
	unsigned int	allocated;	/*%< # of items currently given out */
	unsigned int	freecount;	/*%< # of items on reserved list */
	unsigned int	freemax;	/*%< # of items allowed on free list */
	unsigned int	fillcount;	/*%< # of items to fetch on each fill */
	/*%< Stats only. */
	unsigned int	gets;		/*%< # of requests to this pool */
	/*%< Debugging only. */
170
#if ISC_MEMPOOL_NAMES
171
	char		name[16];	/*%< printed name in stats reports */
Michael Graff's avatar
Michael Graff committed
172
#endif
Bob Halley's avatar
base  
Bob Halley committed
173 174
};

175 176 177
/*
 * Private Inline-able.
 */
Bob Halley's avatar
base  
Bob Halley committed
178

179
#if ! ISC_MEM_TRACKLINES
Michael Graff's avatar
Michael Graff committed
180 181 182
#define ADD_TRACE(a, b, c, d, e)
#define DELETE_TRACE(a, b, c, d, e)
#else
183
#define ADD_TRACE(a, b, c, d, e) \
184 185 186 187 188 189
	do { \
		if ((isc_mem_debugging & (ISC_MEM_DEBUGTRACE | \
					  ISC_MEM_DEBUGRECORD)) != 0 && \
		     b != NULL) \
		         add_trace_entry(a, b, c, d, e); \
	} while (0)
Michael Graff's avatar
Michael Graff committed
190 191
#define DELETE_TRACE(a, b, c, d, e)	delete_trace_entry(a, b, c, d, e)

192 193 194
static void
print_active(isc_mem_t *ctx, FILE *out);

195
/*!
Michael Graff's avatar
Michael Graff committed
196 197 198 199
 * mctx must be locked.
 */
static inline void
add_trace_entry(isc_mem_t *mctx, const void *ptr, unsigned int size
Michael Graff's avatar
pasto  
Michael Graff committed
200
		FLARG)
Michael Graff's avatar
Michael Graff committed
201 202 203 204
{
	debuglink_t *dl;
	unsigned int i;

205
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
206 207 208 209
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_ADDTRACE,
					       "add %p size %u "
					       "file %s line %u mctx %p\n"),
210
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
211

212
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
213 214
		return;

215 216 217 218
	if (size > mctx->max_size)
		size = mctx->max_size;

	dl = ISC_LIST_HEAD(mctx->debuglist[size]);
Michael Graff's avatar
Michael Graff committed
219 220 221
	while (dl != NULL) {
		if (dl->count == DEBUGLIST_COUNT)
			goto next;
222
		for (i = 0; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
223 224
			if (dl->ptr[i] == NULL) {
				dl->ptr[i] = ptr;
225
				dl->size[i] = size;
Michael Graff's avatar
Michael Graff committed
226 227 228 229 230 231 232 233 234 235 236 237 238 239
				dl->file[i] = file;
				dl->line[i] = line;
				dl->count++;
				return;
			}
		}
	next:
		dl = ISC_LIST_NEXT(dl, link);
	}

	dl = malloc(sizeof(debuglink_t));
	INSIST(dl != NULL);

	ISC_LINK_INIT(dl, link);
240
	for (i = 1; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
241
		dl->ptr[i] = NULL;
242
		dl->size[i] = 0;
Michael Graff's avatar
Michael Graff committed
243 244 245 246 247
		dl->file[i] = NULL;
		dl->line[i] = 0;
	}

	dl->ptr[0] = ptr;
248
	dl->size[0] = size;
Michael Graff's avatar
Michael Graff committed
249 250 251 252
	dl->file[0] = file;
	dl->line[0] = line;
	dl->count = 1;

253
	ISC_LIST_PREPEND(mctx->debuglist[size], dl, link);
Michael Graff's avatar
Michael Graff committed
254 255 256 257 258 259 260 261 262
}

static inline void
delete_trace_entry(isc_mem_t *mctx, const void *ptr, unsigned int size,
		   const char *file, unsigned int line)
{
	debuglink_t *dl;
	unsigned int i;

263
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
264 265 266 267
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_DELTRACE,
					       "del %p size %u "
					       "file %s line %u mctx %p\n"),
268
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
269

270
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
271 272
		return;

273 274 275 276
	if (size > mctx->max_size)
		size = mctx->max_size;

	dl = ISC_LIST_HEAD(mctx->debuglist[size]);
Michael Graff's avatar
Michael Graff committed
277
	while (dl != NULL) {
278
		for (i = 0; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
279 280
			if (dl->ptr[i] == ptr) {
				dl->ptr[i] = NULL;
281
				dl->size[i] = 0;
Michael Graff's avatar
Michael Graff committed
282 283 284 285 286 287
				dl->file[i] = NULL;
				dl->line[i] = 0;

				INSIST(dl->count > 0);
				dl->count--;
				if (dl->count == 0) {
288
					ISC_LIST_UNLINK(mctx->debuglist[size],
Michael Graff's avatar
Michael Graff committed
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305
							dl, link);
					free(dl);
				}
				return;
			}
		}
		dl = ISC_LIST_NEXT(dl, link);
	}

	/*
	 * If we get here, we didn't find the item on the list.  We're
	 * screwed.
	 */
	INSIST(dl != NULL);
}
#endif /* ISC_MEM_TRACKLINES */

306 307 308 309 310
static inline size_t
rmsize(size_t size) {
	/*
 	 * round down to ALIGNMENT_SIZE
	 */
311
	return (size & (~(ALIGNMENT_SIZE - 1)));
312 313
}

314
static inline size_t
Bob Halley's avatar
base  
Bob Halley committed
315
quantize(size_t size) {
316
	/*!
317
	 * Round up the result in order to get a size big
Bob Halley's avatar
base  
Bob Halley committed
318 319 320
	 * enough to satisfy the request and be aligned on ALIGNMENT_SIZE
	 * byte boundaries.
	 */
321

Mark Andrews's avatar
Mark Andrews committed
322
	if (size == 0U)
323
		return (ALIGNMENT_SIZE);
324
	return ((size + ALIGNMENT_SIZE - 1) & (~(ALIGNMENT_SIZE - 1)));
Bob Halley's avatar
base  
Bob Halley committed
325 326
}

327
static inline isc_boolean_t
328
more_basic_blocks(isc_mem_t *ctx) {
329 330 331 332 333
	void *new;
	unsigned char *curr, *next;
	unsigned char *first, *last;
	unsigned char **table;
	unsigned int table_size;
Bob Halley's avatar
Bob Halley committed
334
	size_t increment;
335 336 337 338
	int i;

	/* Require: we hold the context lock. */

339 340 341
	/*
	 * Did we hit the quota for this context?
	 */
Bob Halley's avatar
Bob Halley committed
342
	increment = NUM_BASIC_BLOCKS * ctx->mem_target;
Mark Andrews's avatar
Mark Andrews committed
343
	if (ctx->quota != 0U && ctx->total + increment > ctx->quota)
344
		return (ISC_FALSE);
345 346 347

	INSIST(ctx->basic_table_count <= ctx->basic_table_size);
	if (ctx->basic_table_count == ctx->basic_table_size) {
348
		table_size = ctx->basic_table_size + TABLE_INCREMENT;
349
		table = (ctx->memalloc)(ctx->arg,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
350
					table_size * sizeof(unsigned char *));
351 352
		if (table == NULL) {
			ctx->memalloc_failures++;
353
			return (ISC_FALSE);
354
		}
355 356 357
		if (ctx->basic_table_size != 0) {
			memcpy(table, ctx->basic_table,
			       ctx->basic_table_size *
Andreas Gustafsson's avatar
Andreas Gustafsson committed
358
			       sizeof(unsigned char *));
359
			(ctx->memfree)(ctx->arg, ctx->basic_table);
360
		}
361 362
		ctx->basic_table = table;
		ctx->basic_table_size = table_size;
363
	}
364

365
	new = (ctx->memalloc)(ctx->arg, NUM_BASIC_BLOCKS * ctx->mem_target);
366 367
	if (new == NULL) {
		ctx->memalloc_failures++;
368
		return (ISC_FALSE);
369
	}
Bob Halley's avatar
Bob Halley committed
370
	ctx->total += increment;
371 372
	ctx->basic_table[ctx->basic_table_count] = new;
	ctx->basic_table_count++;
373

374 375 376
	curr = new;
	next = curr + ctx->mem_target;
	for (i = 0; i < (NUM_BASIC_BLOCKS - 1); i++) {
377
		((element *)curr)->next = (element *)next;
378 379 380 381 382 383 384
		curr = next;
		next += ctx->mem_target;
	}
	/*
	 * curr is now pointing at the last block in the
	 * array.
	 */
Bob Halley's avatar
Bob Halley committed
385
	((element *)curr)->next = NULL;
386 387 388 389 390 391 392
	first = new;
	last = first + NUM_BASIC_BLOCKS * ctx->mem_target - 1;
	if (first < ctx->lowest || ctx->lowest == NULL)
		ctx->lowest = first;
	if (last > ctx->highest)
		ctx->highest = last;
	ctx->basic_blocks = new;
393 394

	return (ISC_TRUE);
395 396
}

397 398 399 400 401 402 403
static inline isc_boolean_t
more_frags(isc_mem_t *ctx, size_t new_size) {
	int i, frags;
	size_t total_size;
	void *new;
	unsigned char *curr, *next;

404
	/*!
405 406 407 408 409 410 411 412 413 414
	 * Try to get more fragments by chopping up a basic block.
	 */

	if (ctx->basic_blocks == NULL) {
		if (!more_basic_blocks(ctx)) {
			/*
			 * We can't get more memory from the OS, or we've
			 * hit the quota for this context.
			 */
			/*
415
			 * XXXRTH  "At quota" notification here.
416
			 */
417
			return (ISC_FALSE);
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432
		}
	}

	total_size = ctx->mem_target;
	new = ctx->basic_blocks;
	ctx->basic_blocks = ctx->basic_blocks->next;
	frags = total_size / new_size;
	ctx->stats[new_size].blocks++;
	ctx->stats[new_size].freefrags += frags;
	/*
	 * Set up a linked-list of blocks of size
	 * "new_size".
	 */
	curr = new;
	next = curr + new_size;
433
	total_size -= new_size;
434 435 436 437
	for (i = 0; i < (frags - 1); i++) {
		((element *)curr)->next = (element *)next;
		curr = next;
		next += new_size;
438 439 440 441 442 443
		total_size -= new_size;
	}
	/*
	 * Add the remaining fragment of the basic block to a free list.
	 */
	total_size = rmsize(total_size);
Mark Andrews's avatar
Mark Andrews committed
444
	if (total_size > 0U) {
445 446 447
		((element *)next)->next = ctx->freelists[total_size];
		ctx->freelists[total_size] = (element *)next;
		ctx->stats[total_size].freefrags++;
448 449 450 451 452 453 454 455 456 457 458
	}
	/*
	 * curr is now pointing at the last block in the
	 * array.
	 */
	((element *)curr)->next = NULL;
	ctx->freelists[new_size] = new;

	return (ISC_TRUE);
}

Michael Graff's avatar
Michael Graff committed
459
static inline void *
460
mem_getunlocked(isc_mem_t *ctx, size_t size) {
Michael Graff's avatar
Michael Graff committed
461 462
	size_t new_size = quantize(size);
	void *ret;
Bob Halley's avatar
base  
Bob Halley committed
463 464

	if (size >= ctx->max_size || new_size >= ctx->max_size) {
465 466 467
		/*
		 * memget() was called on something beyond our upper limit.
		 */
Mark Andrews's avatar
Mark Andrews committed
468
		if (ctx->quota != 0U && ctx->total + size > ctx->quota) {
Bob Halley's avatar
Bob Halley committed
469 470 471
			ret = NULL;
			goto done;
		}
Mark Andrews's avatar
Mark Andrews committed
472
		ret = (ctx->memalloc)(ctx->arg, size);
473 474 475
		if (ret == NULL) {
			ctx->memalloc_failures++;
			goto done;
Bob Halley's avatar
base  
Bob Halley committed
476
		}
477 478 479 480 481 482 483 484 485 486
		ctx->total += size;
		ctx->inuse += size;
		ctx->stats[ctx->max_size].gets++;
		ctx->stats[ctx->max_size].totalgets++;
		/*
		 * If we don't set new_size to size, then the
		 * ISC_MEM_FILL code might write over bytes we
		 * don't own.
		 */
		new_size = size;
487
		goto done;
Bob Halley's avatar
base  
Bob Halley committed
488 489
	}

490
	/*
Bob Halley's avatar
base  
Bob Halley committed
491 492 493 494
	 * If there are no blocks in the free list for this size, get a chunk
	 * of memory and then break it up into "new_size"-sized blocks, adding
	 * them to the free list.
	 */
495 496
	if (ctx->freelists[new_size] == NULL && !more_frags(ctx, new_size))
		return (NULL);
Bob Halley's avatar
base  
Bob Halley committed
497

498 499 500
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Bob Halley's avatar
base  
Bob Halley committed
501 502 503
	ret = ctx->freelists[new_size];
	ctx->freelists[new_size] = ctx->freelists[new_size]->next;

504
	/*
Bob Halley's avatar
base  
Bob Halley committed
505 506 507 508 509 510 511 512
	 * The stats[] uses the _actual_ "size" requested by the
	 * caller, with the caveat (in the code above) that "size" >= the
	 * max. size (max_size) ends up getting recorded as a call to
	 * max_size.
	 */
	ctx->stats[size].gets++;
	ctx->stats[size].totalgets++;
	ctx->stats[new_size].freefrags--;
513
	ctx->inuse += new_size;
Bob Halley's avatar
base  
Bob Halley committed
514 515 516

 done:

517
#if ISC_MEM_FILL
518 519
	if (ret != NULL)
		memset(ret, 0xbe, new_size); /* Mnemonic for "beef". */
David Lawrence's avatar
David Lawrence committed
520 521 522
#endif

	return (ret);
Michael Graff's avatar
Michael Graff committed
523 524
}

525 526 527 528 529 530 531 532 533 534 535 536 537 538 539
#if ISC_MEM_FILL && ISC_MEM_CHECKOVERRUN
static inline void
check_overrun(void *mem, size_t size, size_t new_size) {
	unsigned char *cp;

	cp = (unsigned char *)mem;
	cp += size;
	while (size < new_size) {
		INSIST(*cp == 0xbe);
		cp++;
		size++;
	}
}
#endif

Michael Graff's avatar
Michael Graff committed
540
static inline void
541
mem_putunlocked(isc_mem_t *ctx, void *mem, size_t size) {
Michael Graff's avatar
Michael Graff committed
542
	size_t new_size = quantize(size);
Bob Halley's avatar
base  
Bob Halley committed
543

544
	if (size == ctx->max_size || new_size >= ctx->max_size) {
545 546 547
		/*
		 * memput() called on something beyond our upper limit.
		 */
548
#if ISC_MEM_FILL
Mark Andrews's avatar
Mark Andrews committed
549 550
		memset(mem, 0xde, size); /* Mnemonic for "dead". */
#endif
551
		(ctx->memfree)(ctx->arg, mem);
Mark Andrews's avatar
Mark Andrews committed
552
		INSIST(ctx->stats[ctx->max_size].gets != 0U);
Bob Halley's avatar
base  
Bob Halley committed
553
		ctx->stats[ctx->max_size].gets--;
Bob Halley's avatar
Bob Halley committed
554
		INSIST(size <= ctx->total);
555
		ctx->inuse -= size;
Bob Halley's avatar
Bob Halley committed
556
		ctx->total -= size;
Michael Graff's avatar
Michael Graff committed
557
		return;
Bob Halley's avatar
base  
Bob Halley committed
558 559
	}

560 561
#if ISC_MEM_FILL
#if ISC_MEM_CHECKOVERRUN
562 563
	check_overrun(mem, size, new_size);
#endif
Mark Andrews's avatar
Mark Andrews committed
564 565
	memset(mem, 0xde, new_size); /* Mnemonic for "dead". */
#endif
566

567 568 569
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Mark Andrews's avatar
Mark Andrews committed
570 571
	((element *)mem)->next = ctx->freelists[new_size];
	ctx->freelists[new_size] = (element *)mem;
Bob Halley's avatar
base  
Bob Halley committed
572

573
	/*
Bob Halley's avatar
base  
Bob Halley committed
574 575 576 577 578
	 * The stats[] uses the _actual_ "size" requested by the
	 * caller, with the caveat (in the code above) that "size" >= the
	 * max. size (max_size) ends up getting recorded as a call to
	 * max_size.
	 */
Mark Andrews's avatar
Mark Andrews committed
579
	INSIST(ctx->stats[size].gets != 0U);
Bob Halley's avatar
base  
Bob Halley committed
580 581
	ctx->stats[size].gets--;
	ctx->stats[new_size].freefrags++;
582
	ctx->inuse -= new_size;
Bob Halley's avatar
base  
Bob Halley committed
583 584
}

585
/*!
586 587 588 589 590 591 592 593 594 595 596
 * Perform a malloc, doing memory filling and overrun detection as necessary.
 */
static inline void *
mem_get(isc_mem_t *ctx, size_t size) {
	char *ret;

#if ISC_MEM_CHECKOVERRUN
	size += 1;
#endif

	ret = (ctx->memalloc)(ctx->arg, size);
597 598
	if (ret == NULL)
		ctx->memalloc_failures++;	
599 600 601 602 603 604 605 606 607 608 609 610 611 612

#if ISC_MEM_FILL
	if (ret != NULL)
		memset(ret, 0xbe, size); /* Mnemonic for "beef". */
#else
#  if ISC_MEM_CHECKOVERRUN
	if (ret != NULL)
		ret[size-1] = 0xbe;
#  endif
#endif

	return (ret);
}

613
/*!
614 615 616 617 618
 * Perform a free, doing memory filling and overrun detection as necessary.
 */
static inline void
mem_put(isc_mem_t *ctx, void *mem, size_t size) {
#if ISC_MEM_CHECKOVERRUN
619
	INSIST(((unsigned char *)mem)[size] == 0xbe);
620 621 622
#endif
#if ISC_MEM_FILL
	memset(mem, 0xde, size); /* Mnemonic for "dead". */
Andreas Gustafsson's avatar
Andreas Gustafsson committed
623 624
#else
	UNUSED(size);
625 626 627 628
#endif
	(ctx->memfree)(ctx->arg, mem);
}

629
/*!
630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645
 * Update internal counters after a memory get.
 */
static inline void
mem_getstats(isc_mem_t *ctx, size_t size) {
	ctx->total += size;
	ctx->inuse += size;

	if (size > ctx->max_size) {
		ctx->stats[ctx->max_size].gets++;
		ctx->stats[ctx->max_size].totalgets++;
	} else {
		ctx->stats[size].gets++;
		ctx->stats[size].totalgets++;
	}
}

646
/*!
647 648 649 650 651 652 653 654 655 656
 * Update internal counters after a memory put.
 */
static inline void
mem_putstats(isc_mem_t *ctx, void *ptr, size_t size) {
	UNUSED(ptr);

	INSIST(ctx->inuse >= size);
	ctx->inuse -= size;

	if (size > ctx->max_size) {
657
		INSIST(ctx->stats[ctx->max_size].gets > 0U);
658 659
		ctx->stats[ctx->max_size].gets--;
	} else {
660
		INSIST(ctx->stats[size].gets > 0U);
661 662 663 664
		ctx->stats[size].gets--;
	}
}

David Lawrence's avatar
David Lawrence committed
665 666 667 668 669 670 671
/*
 * Private.
 */

static void *
default_memalloc(void *arg, size_t size) {
	UNUSED(arg);
672
	if (size == 0U)
673
		size = 1;
David Lawrence's avatar
David Lawrence committed
674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690
	return (malloc(size));
}

static void
default_memfree(void *arg, void *ptr) {
	UNUSED(arg);
	free(ptr);
}

/*
 * Public.
 */

isc_result_t
isc_mem_createx(size_t init_max_size, size_t target_size,
		isc_memalloc_t memalloc, isc_memfree_t memfree, void *arg,
		isc_mem_t **ctxp)
691 692
{
	return (isc_mem_createx2(init_max_size, target_size, memalloc, memfree,
693
				 arg, ctxp, ISC_MEMFLAG_DEFAULT));
694 695 696 697 698 699 700
				 
}

isc_result_t
isc_mem_createx2(size_t init_max_size, size_t target_size,
		 isc_memalloc_t memalloc, isc_memfree_t memfree, void *arg,
		 isc_mem_t **ctxp, unsigned int flags)
David Lawrence's avatar
David Lawrence committed
701 702
{
	isc_mem_t *ctx;
703
	isc_result_t result;
David Lawrence's avatar
David Lawrence committed
704 705 706 707 708

	REQUIRE(ctxp != NULL && *ctxp == NULL);
	REQUIRE(memalloc != NULL);
	REQUIRE(memfree != NULL);

709 710
	INSIST((ALIGNMENT_SIZE & (ALIGNMENT_SIZE - 1)) == 0);

Andreas Gustafsson's avatar
Andreas Gustafsson committed
711
	ctx = (memalloc)(arg, sizeof(*ctx));
David Lawrence's avatar
David Lawrence committed
712 713 714
	if (ctx == NULL)
		return (ISC_R_NOMEMORY);

715 716 717 718 719 720
	if ((flags & ISC_MEMFLAG_NOLOCK) == 0) {
		result = isc_mutex_init(&ctx->lock);
		if (result != ISC_R_SUCCESS) {
			(memfree)(arg, ctx);
			return (result);
		}
721 722
	}

723
	if (init_max_size == 0U)
David Lawrence's avatar
David Lawrence committed
724 725 726
		ctx->max_size = DEF_MAX_SIZE;
	else
		ctx->max_size = init_max_size;
727
	ctx->flags = flags;
728 729 730 731
	ctx->references = 1;
	ctx->quota = 0;
	ctx->total = 0;
	ctx->inuse = 0;
732
	ctx->maxinuse = 0;
733 734 735 736 737 738 739 740 741 742 743
	ctx->hi_water = 0;
	ctx->lo_water = 0;
	ctx->hi_called = ISC_FALSE;
	ctx->water = NULL;
	ctx->water_arg = NULL;
	ctx->magic = MEM_MAGIC;
	isc_ondestroy_init(&ctx->ondestroy);
	ctx->memalloc = memalloc;
	ctx->memfree = memfree;
	ctx->arg = arg;
	ctx->stats = NULL;
744
	ctx->checkfree = ISC_TRUE;
745
#if ISC_MEM_TRACKLINES
746
	ctx->debuglist = NULL;
747
#endif
748 749
	ISC_LIST_INIT(ctx->pools);
	ctx->freelists = NULL;
750 751 752 753 754 755
	ctx->basic_blocks = NULL;
	ctx->basic_table = NULL;
	ctx->basic_table_count = 0;
	ctx->basic_table_size = 0;
	ctx->lowest = NULL;
	ctx->highest = NULL;
756 757

	ctx->stats = (memalloc)(arg,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
758
				(ctx->max_size+1) * sizeof(struct stats));
759 760 761 762
	if (ctx->stats == NULL) {
		result = ISC_R_NOMEMORY;
		goto error;
	}
Andreas Gustafsson's avatar
Andreas Gustafsson committed
763
	memset(ctx->stats, 0, (ctx->max_size + 1) * sizeof(struct stats));
764

765
	if ((flags & ISC_MEMFLAG_INTERNAL) != 0) {
Mark Andrews's avatar
Mark Andrews committed
766
		if (target_size == 0U)
767 768 769 770 771 772 773 774 775 776 777
			ctx->mem_target = DEF_MEM_TARGET;
		else
			ctx->mem_target = target_size;
		ctx->freelists = (memalloc)(arg, ctx->max_size *
						 sizeof(element *));
		if (ctx->freelists == NULL) {
			result = ISC_R_NOMEMORY;
			goto error;
		}
		memset(ctx->freelists, 0,
		       ctx->max_size * sizeof(element *));
David Lawrence's avatar
David Lawrence committed
778
	}
779

780
#if ISC_MEM_TRACKLINES
781 782 783 784
	if ((isc_mem_debugging & ISC_MEM_DEBUGRECORD) != 0) {
		unsigned int i;

		ctx->debuglist = (memalloc)(arg,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
785
				      (ctx->max_size+1) * sizeof(debuglist_t));
786 787 788 789 790 791 792
		if (ctx->debuglist == NULL) {
			result = ISC_R_NOMEMORY;
			goto error;
		}
		for (i = 0; i <= ctx->max_size; i++)
			ISC_LIST_INIT(ctx->debuglist[i]);
	}
Michael Graff's avatar
Michael Graff committed
793
#endif
David Lawrence's avatar
David Lawrence committed
794

795 796
	ctx->memalloc_failures = 0;

David Lawrence's avatar
David Lawrence committed
797 798
	*ctxp = ctx;
	return (ISC_R_SUCCESS);
799 800

  error:
801 802
	if (ctx != NULL) {
		if (ctx->stats != NULL)
803
			(memfree)(arg, ctx->stats);
804
		if (ctx->freelists != NULL)
805
			(memfree)(arg, ctx->freelists);
806
#if ISC_MEM_TRACKLINES
807
		if (ctx->debuglist != NULL)
808 809
			(ctx->memfree)(ctx->arg, ctx->debuglist);
#endif /* ISC_MEM_TRACKLINES */
810 811
		if ((ctx->flags & ISC_MEMFLAG_NOLOCK) == 0)
			DESTROYLOCK(&ctx->lock);
812 813 814 815
		(memfree)(arg, ctx);
	}

	return (result);
David Lawrence's avatar
David Lawrence committed
816 817 818 819 820 821
}

isc_result_t
isc_mem_create(size_t init_max_size, size_t target_size,
	       isc_mem_t **ctxp)
{
822 823
	return (isc_mem_createx2(init_max_size, target_size,
				 default_memalloc, default_memfree, NULL,
824
				 ctxp, ISC_MEMFLAG_DEFAULT));
825 826 827 828 829 830 831 832 833
}

isc_result_t
isc_mem_create2(size_t init_max_size, size_t target_size,
		isc_mem_t **ctxp, unsigned int flags)
{
	return (isc_mem_createx2(init_max_size, target_size,
				 default_memalloc, default_memfree, NULL,
				 ctxp, flags));
David Lawrence's avatar
David Lawrence committed
834 835 836 837 838 839 840 841 842 843
}

static void
destroy(isc_mem_t *ctx) {
	unsigned int i;
	isc_ondestroy_t ondest;

	ctx->magic = 0;

	INSIST(ISC_LIST_EMPTY(ctx->pools));
844

845
#if ISC_MEM_TRACKLINES
846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863
	if (ctx->debuglist != NULL) {
		if (ctx->checkfree) {
			for (i = 0; i <= ctx->max_size; i++) {
				if (!ISC_LIST_EMPTY(ctx->debuglist[i]))
					print_active(ctx, stderr);
				INSIST(ISC_LIST_EMPTY(ctx->debuglist[i]));
			}
		} else {
			debuglink_t *dl;

			for (i = 0; i <= ctx->max_size; i++)
				for (dl = ISC_LIST_HEAD(ctx->debuglist[i]);
				     dl != NULL;
				     dl = ISC_LIST_HEAD(ctx->debuglist[i])) {
					ISC_LIST_UNLINK(ctx->debuglist[i],
						 	dl, link);
					free(dl);
				}
864
		}
865
		(ctx->memfree)(ctx->arg, ctx->debuglist);
866
	}
Michael Graff's avatar
Michael Graff committed
867
#endif
David Lawrence's avatar
David Lawrence committed
868 869 870
	INSIST(ctx->references == 0);

	if (ctx->checkfree) {
871 872
		for (i = 0; i <= ctx->max_size; i++) {
#if ISC_MEM_TRACKLINES
Mark Andrews's avatar
Mark Andrews committed
873
			if (ctx->stats[i].gets != 0U)
874 875
				print_active(ctx, stderr);
#endif
876
			INSIST(ctx->stats[i].gets == 0U);
877
		}
David Lawrence's avatar
David Lawrence committed
878 879
	}

880
	(ctx->memfree)(ctx->arg, ctx->stats);
David Lawrence's avatar
David Lawrence committed
881

882 883 884 885 886 887
	if ((ctx->flags & ISC_MEMFLAG_INTERNAL) != 0) {
		for (i = 0; i < ctx->basic_table_count; i++)
			(ctx->memfree)(ctx->arg, ctx->basic_table[i]);
		(ctx->memfree)(ctx->arg, ctx->freelists);
		(ctx->memfree)(ctx->arg, ctx->basic_table);
	}
David Lawrence's avatar
David Lawrence committed
888 889 890

	ondest = ctx->ondestroy;

891 892
	if ((ctx->flags & ISC_MEMFLAG_NOLOCK) == 0)
		DESTROYLOCK(&ctx->lock);
David Lawrence's avatar
David Lawrence committed
893 894 895 896 897 898 899 900 901 902
	(ctx->memfree)(ctx->arg, ctx);

	isc_ondestroy_notify(&ondest, ctx);
}

void
isc_mem_attach(isc_mem_t *source, isc_mem_t **targetp) {
	REQUIRE(VALID_CONTEXT(source));
	REQUIRE(targetp != NULL && *targetp == NULL);

903
	MCTXLOCK(source, &source->lock);
David Lawrence's avatar
David Lawrence committed
904
	source->references++;
905
	MCTXUNLOCK(source, &source->lock);
David Lawrence's avatar
David Lawrence committed
906 907 908 909 910 911 912 913 914 915 916 917 918

	*targetp = source;
}

void
isc_mem_detach(isc_mem_t **ctxp) {
	isc_mem_t *ctx;
	isc_boolean_t want_destroy = ISC_FALSE;

	REQUIRE(ctxp != NULL);
	ctx = *ctxp;
	REQUIRE(VALID_CONTEXT(ctx));

919
	MCTXLOCK(ctx, &ctx->lock);
David Lawrence's avatar
David Lawrence committed
920 921 922 923
	INSIST(ctx->references > 0);
	ctx->references--;
	if (ctx->references == 0)
		want_destroy = ISC_TRUE;
924
	MCTXUNLOCK(ctx, &ctx->lock);
David Lawrence's avatar
David Lawrence committed
925 926 927 928 929 930 931

	if (want_destroy)
		destroy(ctx);

	*ctxp = NULL;
}

932 933 934 935 936 937 938 939 940 941 942 943 944 945
/*
 * isc_mem_putanddetach() is the equivalent of:
 *
 * mctx = NULL;
 * isc_mem_attach(ptr->mctx, &mctx);
 * isc_mem_detach(&ptr->mctx);
 * isc_mem_put(mctx, ptr, sizeof(*ptr);
 * isc_mem_detach(&mctx);
 */

void
isc__mem_putanddetach(isc_mem_t **ctxp, void *ptr, size_t size FLARG) {
	isc_mem_t *ctx;
	isc_boolean_t want_destroy = ISC_FALSE;
946 947
	size_info *si;
	size_t oldsize;
948 949 950 951 952 953 954 955 956 957 958 959

	REQUIRE(ctxp != NULL);
	ctx = *ctxp;
	REQUIRE(VALID_CONTEXT(ctx));
	REQUIRE(ptr != NULL);

	/*
	 * Must be before mem_putunlocked() as ctxp is usually within
	 * [ptr..ptr+size).
	 */
	*ctxp = NULL;

960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979
	if ((isc_mem_debugging & (ISC_MEM_DEBUGSIZE|ISC_MEM_DEBUGCTX)) != 0) {
		if ((isc_mem_debugging & ISC_MEM_DEBUGSIZE) != 0) {
			si = &(((size_info *)ptr)[-1]);
			oldsize = si->u.size - ALIGNMENT_SIZE;
			if ((isc_mem_debugging & ISC_MEM_DEBUGCTX) != 0)
				oldsize -= ALIGNMENT_SIZE;
			INSIST(oldsize == size);
		}
		isc__mem_free(ctx, ptr FLARG_PASS);

		MCTXLOCK(ctx, &ctx->lock);
		ctx->references--;
		if (ctx->references == 0)
			want_destroy = ISC_TRUE;
		MCTXUNLOCK(ctx, &ctx->lock);
		if (want_destroy)
			destroy(ctx);

		return;
	}
980 981 982 983 984 985 986 987 988

	if ((ctx->flags & ISC_MEMFLAG_INTERNAL) != 0) {
		MCTXLOCK(ctx, &ctx->lock);
		mem_putunlocked(ctx, ptr, size);
	} else {
		mem_put(ctx, ptr, size);
		MCTXLOCK(ctx, &ctx->lock);
		mem_putstats(ctx, ptr, size);
	}
989 990

	DELETE_TRACE(ctx, ptr, size, file, line);
991 992