mem.c 38 KB
Newer Older
Bob Halley's avatar
base  
Bob Halley committed
1
/*
Mark Andrews's avatar
Mark Andrews committed
2
 * Copyright (C) 1997-2002  Internet Software Consortium.
3
 *
Bob Halley's avatar
base  
Bob Halley committed
4 5 6
 * 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.
7
 *
8 9 10 11 12 13 14 15
 * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM
 * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
 * INTERNET SOFTWARE CONSORTIUM 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
 */

18
/* $Id: mem.c,v 1.114 2003/07/25 00:01:12 marka Exp $ */
David Lawrence's avatar
David Lawrence committed
19

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

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

Michael Graff's avatar
Michael Graff committed
26 27
#include <limits.h>

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

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

37 38 39
#ifndef ISC_MEM_DEBUGGING
#define ISC_MEM_DEBUGGING 0
#endif
40
LIBISC_EXTERNAL_DATA unsigned int isc_mem_debugging = ISC_MEM_DEBUGGING;
41

42 43 44 45 46 47 48 49 50 51
/*
 * Define ISC_MEM_USE_INTERNAL_MALLOC=1 to use the internal malloc()
 * implementation in preference to the system one.  The internal malloc()
 * is very space-efficient, and quite fast on uniprocessor systems.  It
 * performs poorly on multiprocessor machines.
 */
#ifndef ISC_MEM_USE_INTERNAL_MALLOC
#define ISC_MEM_USE_INTERNAL_MALLOC 0
#endif

52 53 54 55 56 57
/*
 * Constants.
 */

#define DEF_MAX_SIZE		1100
#define DEF_MEM_TARGET		4096
58 59
#define ALIGNMENT_SIZE		8		/* must be a power of 2 */
#define NUM_BASIC_BLOCKS	64		/* must be > 1 */
60
#define TABLE_INCREMENT		1024
Michael Graff's avatar
Michael Graff committed
61
#define DEBUGLIST_COUNT		1024
62

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

Michael Graff's avatar
Michael Graff committed
77 78 79 80 81 82
#define FLARG_PASS	, file, line
#define FLARG		, const char *file, int line
#else
#define FLARG_PASS
#define FLARG
#endif
83

Michael Graff's avatar
Michael Graff committed
84
typedef struct element element;
85 86 87
struct element {
	element *		next;
};
Bob Halley's avatar
base  
Bob Halley committed
88 89 90 91 92

typedef struct {
	/*
	 * This structure must be ALIGNMENT_SIZE bytes.
	 */
93 94 95 96
	union {
		size_t		size;
		char		bytes[ALIGNMENT_SIZE];
	} u;
Bob Halley's avatar
Bob Halley committed
97
} size_info;
Bob Halley's avatar
base  
Bob Halley committed
98 99

struct stats {
Bob Halley's avatar
Bob Halley committed
100 101
	unsigned long		gets;
	unsigned long		totalgets;
102
#if ISC_MEM_USE_INTERNAL_MALLOC
Bob Halley's avatar
Bob Halley committed
103 104
	unsigned long		blocks;
	unsigned long		freefrags;
105
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */
Bob Halley's avatar
base  
Bob Halley committed
106 107
};

108 109
#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
110

111
#if ISC_MEM_TRACKLINES
112
typedef ISC_LIST(debuglink_t)	debuglist_t;
113
#endif
114

115
struct isc_mem {
Bob Halley's avatar
Bob Halley committed
116
	unsigned int		magic;
117
	isc_ondestroy_t		ondestroy;
Bob Halley's avatar
Bob Halley committed
118
	isc_mutex_t		lock;
119 120 121
	isc_memalloc_t		memalloc;
	isc_memfree_t		memfree;
	void *			arg;
Bob Halley's avatar
base  
Bob Halley committed
122
	size_t			max_size;
123
	isc_boolean_t		checkfree;
Bob Halley's avatar
base  
Bob Halley committed
124
	struct stats *		stats;
125
	unsigned int		references;
126
	size_t			quota;
Bob Halley's avatar
Bob Halley committed
127
	size_t			total;
128
	size_t			inuse;
129
	size_t			maxinuse;
130 131 132 133 134
	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
135
	ISC_LIST(isc_mempool_t)	pools;
136 137 138 139 140 141 142 143 144 145 146 147

#if ISC_MEM_USE_INTERNAL_MALLOC
	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;
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */

148
#if ISC_MEM_TRACKLINES
149
	debuglist_t *	 	debuglist;
Michael Graff's avatar
Michael Graff committed
150
#endif
151 152

	unsigned int		memalloc_failures;
Michael Graff's avatar
Michael Graff committed
153 154
};

155 156
#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
157 158

struct isc_mempool {
Michael Graff's avatar
Michael Graff committed
159
	/* always unlocked */
Michael Graff's avatar
Michael Graff committed
160
	unsigned int	magic;		/* magic number */
Michael Graff's avatar
Michael Graff committed
161
	isc_mutex_t    *lock;		/* optional lock */
Michael Graff's avatar
Michael Graff committed
162
	isc_mem_t      *mctx;		/* our memory context */
Michael Graff's avatar
Michael Graff committed
163 164 165
	/* locked via the memory context's lock */
	ISC_LINK(isc_mempool_t)	link;	/* next pool in this mem context */
	/* optionally locked from here down */
Michael Graff's avatar
Michael Graff committed
166 167 168 169 170 171 172 173 174
	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 */
Michael Graff's avatar
Michael Graff committed
175
	/* Debugging only. */
176
#if ISC_MEMPOOL_NAMES
Michael Graff's avatar
Michael Graff committed
177 178
	char		name[16];	/* printed name in stats reports */
#endif
Bob Halley's avatar
base  
Bob Halley committed
179 180
};

181 182 183
/*
 * Private Inline-able.
 */
Bob Halley's avatar
base  
Bob Halley committed
184

185
#if ! ISC_MEM_TRACKLINES
Michael Graff's avatar
Michael Graff committed
186 187 188
#define ADD_TRACE(a, b, c, d, e)
#define DELETE_TRACE(a, b, c, d, e)
#else
189
#define ADD_TRACE(a, b, c, d, e) \
190 191 192 193 194 195
	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
196 197
#define DELETE_TRACE(a, b, c, d, e)	delete_trace_entry(a, b, c, d, e)

198 199 200
static void
print_active(isc_mem_t *ctx, FILE *out);

Michael Graff's avatar
Michael Graff committed
201 202 203 204 205
/*
 * 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
206
		FLARG)
Michael Graff's avatar
Michael Graff committed
207 208 209 210
{
	debuglink_t *dl;
	unsigned int i;

211
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
212 213 214 215
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_ADDTRACE,
					       "add %p size %u "
					       "file %s line %u mctx %p\n"),
216
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
217

218
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
219 220
		return;

221 222 223 224
	if (size > mctx->max_size)
		size = mctx->max_size;

	dl = ISC_LIST_HEAD(mctx->debuglist[size]);
Michael Graff's avatar
Michael Graff committed
225 226 227
	while (dl != NULL) {
		if (dl->count == DEBUGLIST_COUNT)
			goto next;
228
		for (i = 0; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
229 230
			if (dl->ptr[i] == NULL) {
				dl->ptr[i] = ptr;
231
				dl->size[i] = size;
Michael Graff's avatar
Michael Graff committed
232 233 234 235 236 237 238 239 240 241 242 243 244 245
				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);
246
	for (i = 1; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
247
		dl->ptr[i] = NULL;
248
		dl->size[i] = 0;
Michael Graff's avatar
Michael Graff committed
249 250 251 252 253
		dl->file[i] = NULL;
		dl->line[i] = 0;
	}

	dl->ptr[0] = ptr;
254
	dl->size[0] = size;
Michael Graff's avatar
Michael Graff committed
255 256 257 258
	dl->file[0] = file;
	dl->line[0] = line;
	dl->count = 1;

259
	ISC_LIST_PREPEND(mctx->debuglist[size], dl, link);
Michael Graff's avatar
Michael Graff committed
260 261 262 263 264 265 266 267 268
}

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;

269
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
270 271 272 273
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_DELTRACE,
					       "del %p size %u "
					       "file %s line %u mctx %p\n"),
274
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
275

276
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
277 278
		return;

279 280 281 282
	if (size > mctx->max_size)
		size = mctx->max_size;

	dl = ISC_LIST_HEAD(mctx->debuglist[size]);
Michael Graff's avatar
Michael Graff committed
283
	while (dl != NULL) {
284
		for (i = 0; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
285 286
			if (dl->ptr[i] == ptr) {
				dl->ptr[i] = NULL;
287
				dl->size[i] = 0;
Michael Graff's avatar
Michael Graff committed
288 289 290 291 292 293
				dl->file[i] = NULL;
				dl->line[i] = 0;

				INSIST(dl->count > 0);
				dl->count--;
				if (dl->count == 0) {
294
					ISC_LIST_UNLINK(mctx->debuglist[size],
Michael Graff's avatar
Michael Graff committed
295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
							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 */

312
#if ISC_MEM_USE_INTERNAL_MALLOC
313 314 315 316 317
static inline size_t
rmsize(size_t size) {
	/*
 	 * round down to ALIGNMENT_SIZE
	 */
318
	return (size & (~(ALIGNMENT_SIZE - 1)));
319 320
}

321
static inline size_t
Bob Halley's avatar
base  
Bob Halley committed
322 323
quantize(size_t size) {
	/*
324
	 * Round up the result in order to get a size big
Bob Halley's avatar
base  
Bob Halley committed
325 326 327
	 * enough to satisfy the request and be aligned on ALIGNMENT_SIZE
	 * byte boundaries.
	 */
328

329 330
	if (size == 0)
		return (ALIGNMENT_SIZE);
331
	return ((size + ALIGNMENT_SIZE - 1) & (~(ALIGNMENT_SIZE - 1)));
Bob Halley's avatar
base  
Bob Halley committed
332 333
}

334
static inline isc_boolean_t
335
more_basic_blocks(isc_mem_t *ctx) {
336 337 338 339 340
	void *new;
	unsigned char *curr, *next;
	unsigned char *first, *last;
	unsigned char **table;
	unsigned int table_size;
Bob Halley's avatar
Bob Halley committed
341
	size_t increment;
342 343 344 345
	int i;

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

346 347 348
	/*
	 * Did we hit the quota for this context?
	 */
Bob Halley's avatar
Bob Halley committed
349 350
	increment = NUM_BASIC_BLOCKS * ctx->mem_target;
	if (ctx->quota != 0 && ctx->total + increment > ctx->quota)
351
		return (ISC_FALSE);
352 353 354

	INSIST(ctx->basic_table_count <= ctx->basic_table_size);
	if (ctx->basic_table_count == ctx->basic_table_size) {
355
		table_size = ctx->basic_table_size + TABLE_INCREMENT;
356
		table = (ctx->memalloc)(ctx->arg,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
357
					table_size * sizeof(unsigned char *));
358 359
		if (table == NULL) {
			ctx->memalloc_failures++;
360
			return (ISC_FALSE);
361
		}
362 363 364
		if (ctx->basic_table_size != 0) {
			memcpy(table, ctx->basic_table,
			       ctx->basic_table_size *
Andreas Gustafsson's avatar
Andreas Gustafsson committed
365
			       sizeof(unsigned char *));
366
			(ctx->memfree)(ctx->arg, ctx->basic_table);
367
		}
368 369
		ctx->basic_table = table;
		ctx->basic_table_size = table_size;
370
	}
371

372
	new = (ctx->memalloc)(ctx->arg, NUM_BASIC_BLOCKS * ctx->mem_target);
373 374
	if (new == NULL) {
		ctx->memalloc_failures++;
375
		return (ISC_FALSE);
376
	}
Bob Halley's avatar
Bob Halley committed
377
	ctx->total += increment;
378 379
	ctx->basic_table[ctx->basic_table_count] = new;
	ctx->basic_table_count++;
380

381 382 383
	curr = new;
	next = curr + ctx->mem_target;
	for (i = 0; i < (NUM_BASIC_BLOCKS - 1); i++) {
384
		((element *)curr)->next = (element *)next;
385 386 387 388 389 390 391
		curr = next;
		next += ctx->mem_target;
	}
	/*
	 * curr is now pointing at the last block in the
	 * array.
	 */
Bob Halley's avatar
Bob Halley committed
392
	((element *)curr)->next = NULL;
393 394 395 396 397 398 399
	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;
400 401

	return (ISC_TRUE);
402 403
}

404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421
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;

	/*
	 * 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.
			 */
			/*
422
			 * XXXRTH  "At quota" notification here.
423
			 */
424
			return (ISC_FALSE);
425 426 427 428 429 430 431 432 433 434 435 436 437 438 439
		}
	}

	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;
440
	total_size -= new_size;
441 442 443 444
	for (i = 0; i < (frags - 1); i++) {
		((element *)curr)->next = (element *)next;
		curr = next;
		next += new_size;
445 446 447 448 449 450 451 452 453 454
		total_size -= new_size;
	}
	/*
	 * Add the remaining fragment of the basic block to a free list.
	 */
	total_size = rmsize(total_size);
	if (total_size > 0) {
		((element *)next)->next = ctx->freelists[total_size];
		ctx->freelists[total_size] = (element *)next;
		ctx->stats[total_size].freefrags++;
455 456 457 458 459 460 461 462 463 464 465
	}
	/*
	 * 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
466
static inline void *
467
mem_getunlocked(isc_mem_t *ctx, size_t size) {
Michael Graff's avatar
Michael Graff committed
468 469
	size_t new_size = quantize(size);
	void *ret;
Bob Halley's avatar
base  
Bob Halley committed
470 471

	if (size >= ctx->max_size || new_size >= ctx->max_size) {
472 473 474
		/*
		 * memget() was called on something beyond our upper limit.
		 */
Bob Halley's avatar
Bob Halley committed
475 476 477 478
		if (ctx->quota != 0 && ctx->total + size > ctx->quota) {
			ret = NULL;
			goto done;
		}
Mark Andrews's avatar
Mark Andrews committed
479
		ret = (ctx->memalloc)(ctx->arg, size);
480 481 482
		if (ret == NULL) {
			ctx->memalloc_failures++;
			goto done;
Bob Halley's avatar
base  
Bob Halley committed
483
		}
484 485 486 487 488 489 490 491 492 493
		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;
494
		goto done;
Bob Halley's avatar
base  
Bob Halley committed
495 496
	}

497
	/*
Bob Halley's avatar
base  
Bob Halley committed
498 499 500 501
	 * 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.
	 */
502 503
	if (ctx->freelists[new_size] == NULL && !more_frags(ctx, new_size))
		return (NULL);
Bob Halley's avatar
base  
Bob Halley committed
504

505 506 507
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Bob Halley's avatar
base  
Bob Halley committed
508 509 510
	ret = ctx->freelists[new_size];
	ctx->freelists[new_size] = ctx->freelists[new_size]->next;

511
	/*
Bob Halley's avatar
base  
Bob Halley committed
512 513 514 515 516 517 518 519
	 * 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--;
520
	ctx->inuse += new_size;
Bob Halley's avatar
base  
Bob Halley committed
521 522 523

 done:

524
#if ISC_MEM_FILL
525 526
	if (ret != NULL)
		memset(ret, 0xbe, new_size); /* Mnemonic for "beef". */
David Lawrence's avatar
David Lawrence committed
527 528 529
#endif

	return (ret);
Michael Graff's avatar
Michael Graff committed
530 531
}

532 533 534 535 536 537 538 539 540 541 542 543 544 545 546
#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
547
static inline void
548
mem_putunlocked(isc_mem_t *ctx, void *mem, size_t size) {
Michael Graff's avatar
Michael Graff committed
549
	size_t new_size = quantize(size);
Bob Halley's avatar
base  
Bob Halley committed
550

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

567 568
#if ISC_MEM_FILL
#if ISC_MEM_CHECKOVERRUN
569 570
	check_overrun(mem, size, new_size);
#endif
Mark Andrews's avatar
Mark Andrews committed
571 572
	memset(mem, 0xde, new_size); /* Mnemonic for "dead". */
#endif
573

574 575 576
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Mark Andrews's avatar
Mark Andrews committed
577 578
	((element *)mem)->next = ctx->freelists[new_size];
	ctx->freelists[new_size] = (element *)mem;
Bob Halley's avatar
base  
Bob Halley committed
579

580
	/*
Bob Halley's avatar
base  
Bob Halley committed
581 582 583 584 585 586 587 588
	 * 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.
	 */
	INSIST(ctx->stats[size].gets != 0);
	ctx->stats[size].gets--;
	ctx->stats[new_size].freefrags++;
589
	ctx->inuse -= new_size;
Bob Halley's avatar
base  
Bob Halley committed
590 591
}

592 593 594 595 596 597 598 599 600 601 602 603 604 605
#else /* ISC_MEM_USE_INTERNAL_MALLOC */

/*
 * 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);
606 607
	if (ret == NULL)
		ctx->memalloc_failures++;	
608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627

#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);
}

/*
 * 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
628
	INSIST(((unsigned char *)mem)[size] == 0xbe);
629 630 631
#endif
#if ISC_MEM_FILL
	memset(mem, 0xde, size); /* Mnemonic for "dead". */
Andreas Gustafsson's avatar
Andreas Gustafsson committed
632 633
#else
	UNUSED(size);
634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665
#endif
	(ctx->memfree)(ctx->arg, mem);
}

/*
 * 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++;
	}
}

/*
 * 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) {
666
		INSIST(ctx->stats[ctx->max_size].gets > 0U);
667 668
		ctx->stats[ctx->max_size].gets--;
	} else {
669
		INSIST(ctx->stats[size].gets > 0U);
670 671 672 673 674 675
		ctx->stats[size].gets--;
	}
}

#endif /* ISC_MEM_USE_INTERNAL_MALLOC */

David Lawrence's avatar
David Lawrence committed
676 677 678 679 680 681 682
/*
 * Private.
 */

static void *
default_memalloc(void *arg, size_t size) {
	UNUSED(arg);
683
	if (size == 0U)
684
		size = 1;
David Lawrence's avatar
David Lawrence committed
685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703
	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)
{
	isc_mem_t *ctx;
704
	isc_result_t result;
David Lawrence's avatar
David Lawrence committed
705 706 707 708 709

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

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

712 713 714 715
#if !ISC_MEM_USE_INTERNAL_MALLOC
	UNUSED(target_size);
#endif

Andreas Gustafsson's avatar
Andreas Gustafsson committed
716
	ctx = (memalloc)(arg, sizeof(*ctx));
David Lawrence's avatar
David Lawrence committed
717 718 719
	if (ctx == NULL)
		return (ISC_R_NOMEMORY);

720
	if (init_max_size == 0U)
David Lawrence's avatar
David Lawrence committed
721 722 723
		ctx->max_size = DEF_MAX_SIZE;
	else
		ctx->max_size = init_max_size;
724 725 726 727
	ctx->references = 1;
	ctx->quota = 0;
	ctx->total = 0;
	ctx->inuse = 0;
728
	ctx->maxinuse = 0;
729 730 731 732 733 734 735 736 737 738 739
	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;
740
	ctx->checkfree = ISC_TRUE;
741
#if ISC_MEM_TRACKLINES
742
	ctx->debuglist = NULL;
743
#endif
744 745 746 747 748 749 750
	ISC_LIST_INIT(ctx->pools);

#if ISC_MEM_USE_INTERNAL_MALLOC
	ctx->freelists = NULL;
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */

	ctx->stats = (memalloc)(arg,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
751
				(ctx->max_size+1) * sizeof(struct stats));
752 753 754 755
	if (ctx->stats == NULL) {
		result = ISC_R_NOMEMORY;
		goto error;
	}
Andreas Gustafsson's avatar
Andreas Gustafsson committed
756
	memset(ctx->stats, 0, (ctx->max_size + 1) * sizeof(struct stats));
757 758

#if ISC_MEM_USE_INTERNAL_MALLOC
David Lawrence's avatar
David Lawrence committed
759 760 761 762
	if (target_size == 0)
		ctx->mem_target = DEF_MEM_TARGET;
	else
		ctx->mem_target = target_size;
Andreas Gustafsson's avatar
Andreas Gustafsson committed
763
	ctx->freelists = (memalloc)(arg, ctx->max_size * sizeof(element *));
David Lawrence's avatar
David Lawrence committed
764
	if (ctx->freelists == NULL) {
765 766
		result = ISC_R_NOMEMORY;
		goto error;
David Lawrence's avatar
David Lawrence committed
767 768
	}
	memset(ctx->freelists, 0,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
769
	       ctx->max_size * sizeof(element *));
David Lawrence's avatar
David Lawrence committed
770 771 772 773 774 775
	ctx->basic_blocks = NULL;
	ctx->basic_table = NULL;
	ctx->basic_table_count = 0;
	ctx->basic_table_size = 0;
	ctx->lowest = NULL;
	ctx->highest = NULL;
776 777
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */

David Lawrence's avatar
David Lawrence committed
778 779
	if (isc_mutex_init(&ctx->lock) != ISC_R_SUCCESS) {
		UNEXPECTED_ERROR(__FILE__, __LINE__,
780 781 782
				 "isc_mutex_init() %s",
				 isc_msgcat_get(isc_msgcat, ISC_MSGSET_GENERAL,
						ISC_MSG_FAILED, "failed"));
783 784
		result = ISC_R_UNEXPECTED;
		goto error;
David Lawrence's avatar
David Lawrence committed
785
	}
786

787
#if ISC_MEM_TRACKLINES
788 789 790 791
	if ((isc_mem_debugging & ISC_MEM_DEBUGRECORD) != 0) {
		unsigned int i;

		ctx->debuglist = (memalloc)(arg,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
792
				      (ctx->max_size+1) * sizeof(debuglist_t));
793 794 795 796 797 798 799
		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
800
#endif
David Lawrence's avatar
David Lawrence committed
801

802 803
	ctx->memalloc_failures = 0;

David Lawrence's avatar
David Lawrence committed
804 805
	*ctxp = ctx;
	return (ISC_R_SUCCESS);
806 807 808 809 810 811 812 813 814

  error:
	if (ctx) {
		if (ctx->stats)
			(memfree)(arg, ctx->stats);
#if ISC_MEM_USE_INTERNAL_MALLOC
		if (ctx->freelists)
			(memfree)(arg, ctx->freelists);
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */
815 816 817 818
#if ISC_MEM_TRACKLINES
		if (ctx->debuglist)
			(ctx->memfree)(ctx->arg, ctx->debuglist);
#endif /* ISC_MEM_TRACKLINES */
819 820 821 822
		(memfree)(arg, ctx);
	}

	return (result);
David Lawrence's avatar
David Lawrence committed
823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840
}

isc_result_t
isc_mem_create(size_t init_max_size, size_t target_size,
	       isc_mem_t **ctxp)
{
	return (isc_mem_createx(init_max_size, target_size,
				default_memalloc, default_memfree, NULL,
				ctxp));
}

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

	ctx->magic = 0;

841
#if ISC_MEM_USE_INTERNAL_MALLOC
David Lawrence's avatar
David Lawrence committed
842
	INSIST(ISC_LIST_EMPTY(ctx->pools));
843 844
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */

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 873 874 875
		for (i = 0; i <= ctx->max_size; i++) {
#if ISC_MEM_TRACKLINES
			if (ctx->stats[i].gets != 0)
				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
#if ISC_MEM_USE_INTERNAL_MALLOC
David Lawrence's avatar
David Lawrence committed
883 884 885 886
	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);
887
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */
David Lawrence's avatar
David Lawrence committed
888 889 890

	ondest = ctx->ondestroy;

891
	DESTROYLOCK(&ctx->lock);
David Lawrence's avatar
David Lawrence committed
892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930
	(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);

	LOCK(&source->lock);
	source->references++;
	UNLOCK(&source->lock);

	*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));

	LOCK(&ctx->lock);
	INSIST(ctx->references > 0);
	ctx->references--;
	if (ctx->references == 0)
		want_destroy = ISC_TRUE;
	UNLOCK(&ctx->lock);

	if (want_destroy)
		destroy(ctx);

	*ctxp = NULL;
}

931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956
/*
 * 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;

	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;

957
#if ISC_MEM_USE_INTERNAL_MALLOC
958 959
	LOCK(&ctx->lock);
	mem_putunlocked(ctx, ptr, size);
960 961 962 963 964 965 966
#else /* ISC_MEM_USE_INTERNAL_MALLOC */
	mem_put(ctx, ptr, size);
	LOCK(&ctx->lock);
	mem_putstats(ctx, ptr, size);
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */

	DELETE_TRACE(ctx, ptr, size, file, line);
967 968 969 970
	INSIST(ctx->references > 0);
	ctx->references--;
	if (ctx->references == 0)
		want_destroy = ISC_TRUE;
971

972 973 974 975 976 977
	UNLOCK(&ctx->lock);

	if (want_destroy)
		destroy(ctx);
}

David Lawrence's avatar
David Lawrence committed
978 979 980 981 982 983 984 985 986 987 988 989 990 991
void
isc_mem_destroy(isc_mem_t **ctxp) {
	isc_mem_t *ctx;

	/*
	 * This routine provides legacy support for callers who use mctxs
	 * without attaching/detaching.
	 */

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

	LOCK(&ctx->lock);
992
#if ISC_MEM_TRACKLINES
993 994 995
	if (ctx->references != 1)
		print_active(ctx, stderr);
#endif
David Lawrence's avatar
David Lawrence committed
996 997 998 999
	REQUIRE(ctx->references == 1);
	ctx->references--;
	UNLOCK(&ctx->lock);

Brian Wellington's avatar
Brian Wellington committed
1000
	destroy(ctx);
David Lawrence's avatar
David Lawrence committed
1001 1002 1003 1004 1005 1006 1007

	*ctxp = NULL;
}

isc_result_t
isc_mem_ondestroy(isc_mem_t *ctx, isc_task_t *task, isc_event_t **event) {
	isc_result_t res;
1008

David Lawrence's avatar
David Lawrence committed
1009 1010 1011 1012 1013 1014 1015 1016
	LOCK(&ctx->lock);
	res = isc_ondestroy_register(&ctx->ondestroy, task, event);
	UNLOCK(&ctx->lock);

	return (res);
}


Michael Graff's avatar
Michael Graff committed
1017 1018 1019
void *
isc__mem_get(isc_mem_t *ctx, size_t size FLARG) {
	void *ptr;
1020
	isc_boolean_t call_water = ISC_FALSE;
Michael Graff's avatar
Michael Graff committed
1021

David Lawrence's avatar
David Lawrence committed
1022 1023
	REQUIRE(VALID_CONTEXT(ctx));

1024
#if ISC_MEM_USE_INTERNAL_MALLOC
David Lawrence's avatar
David Lawrence committed
1025
	LOCK(&ctx->lock);
Michael Graff's avatar
Michael Graff committed
1026
	ptr = mem_getunlocked(ctx, size);
1027 1028 1029
#else /* ISC_MEM_USE_INTERNAL_MALLOC */
	ptr = mem_get(ctx, size);
	LOCK(&ctx->lock);
Andreas Gustafsson's avatar
style  
Andreas Gustafsson committed
1030
	if (ptr != NULL)
1031
		mem_getstats(ctx, size);
1032 1033
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */

Michael Graff's avatar
Michael Graff committed
1034
	ADD_TRACE(ctx, ptr, size, file, line);
1035
	if (ctx->hi_water != 0U && !ctx->hi_called &&
1036 1037 1038 1039
	    ctx->inuse > ctx->hi_water) {
		ctx->hi_called = ISC_TRUE;
		call_water = ISC_TRUE;
	}
1040 1041
	if (ctx->inuse > ctx->maxinuse) {
		ctx->maxinuse = ctx->inuse;
1042
		if