mem.c 38.1 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
 */

18 19 20
/* $Id: mem.c,v 1.119 2005/04/27 04:57:13 sra Exp $ */

/*! \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
#ifndef ISC_MEM_DEBUGGING
#define ISC_MEM_DEBUGGING 0
#endif
42
LIBISC_EXTERNAL_DATA unsigned int isc_mem_debugging = ISC_MEM_DEBUGGING;
43

44
/*!
45 46 47 48 49 50 51 52 53
 * 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

54 55 56 57 58 59
/*
 * Constants.
 */

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

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

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

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

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

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

110 111
#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
112

113
#if ISC_MEM_TRACKLINES
114
typedef ISC_LIST(debuglink_t)	debuglist_t;
115
#endif
116

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

#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 */

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

	unsigned int		memalloc_failures;
Michael Graff's avatar
Michael Graff committed
155 156
};

157 158
#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
159 160

struct isc_mempool {
Michael Graff's avatar
Michael Graff committed
161
	/* always unlocked */
162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
	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. */
178
#if ISC_MEMPOOL_NAMES
179
	char		name[16];	/*%< printed name in stats reports */
Michael Graff's avatar
Michael Graff committed
180
#endif
Bob Halley's avatar
base  
Bob Halley committed
181 182
};

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

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

200 201 202
static void
print_active(isc_mem_t *ctx, FILE *out);

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

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

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

223 224 225 226
	if (size > mctx->max_size)
		size = mctx->max_size;

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

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

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

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;

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

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

281 282 283 284
	if (size > mctx->max_size)
		size = mctx->max_size;

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

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

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

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

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

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

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

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

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

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

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

	return (ISC_TRUE);
404 405
}

406 407 408 409 410 411 412
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;

413
	/*!
414 415 416 417 418 419 420 421 422 423
	 * 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.
			 */
			/*
424
			 * XXXRTH  "At quota" notification here.
425
			 */
426
			return (ISC_FALSE);
427 428 429 430 431 432 433 434 435 436 437 438 439 440 441
		}
	}

	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;
442
	total_size -= new_size;
443 444 445 446
	for (i = 0; i < (frags - 1); i++) {
		((element *)curr)->next = (element *)next;
		curr = next;
		next += new_size;
447 448 449 450 451 452 453 454 455 456
		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++;
457 458 459 460 461 462 463 464 465 466 467
	}
	/*
	 * 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
468
static inline void *
469
mem_getunlocked(isc_mem_t *ctx, size_t size) {
Michael Graff's avatar
Michael Graff committed
470 471
	size_t new_size = quantize(size);
	void *ret;
Bob Halley's avatar
base  
Bob Halley committed
472 473

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

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

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

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

 done:

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

	return (ret);
Michael Graff's avatar
Michael Graff committed
532 533
}

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

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

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

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

582
	/*
Bob Halley's avatar
base  
Bob Halley committed
583 584 585 586 587 588 589 590
	 * 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++;
591
	ctx->inuse -= new_size;
Bob Halley's avatar
base  
Bob Halley committed
592 593
}

594 595
#else /* ISC_MEM_USE_INTERNAL_MALLOC */

596
/*!
597 598 599 600 601 602 603 604 605 606 607
 * 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);
608 609
	if (ret == NULL)
		ctx->memalloc_failures++;	
610 611 612 613 614 615 616 617 618 619 620 621 622 623

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

624
/*!
625 626 627 628 629
 * 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
630
	INSIST(((unsigned char *)mem)[size] == 0xbe);
631 632 633
#endif
#if ISC_MEM_FILL
	memset(mem, 0xde, size); /* Mnemonic for "dead". */
Andreas Gustafsson's avatar
Andreas Gustafsson committed
634 635
#else
	UNUSED(size);
636 637 638 639
#endif
	(ctx->memfree)(ctx->arg, mem);
}

640
/*!
641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656
 * 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++;
	}
}

657
/*!
658 659 660 661 662 663 664 665 666 667
 * 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) {
668
		INSIST(ctx->stats[ctx->max_size].gets > 0U);
669 670
		ctx->stats[ctx->max_size].gets--;
	} else {
671
		INSIST(ctx->stats[size].gets > 0U);
672 673 674 675 676 677
		ctx->stats[size].gets--;
	}
}

#endif /* ISC_MEM_USE_INTERNAL_MALLOC */

David Lawrence's avatar
David Lawrence committed
678 679 680 681 682 683 684
/*
 * Private.
 */

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

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

712 713
	INSIST((ALIGNMENT_SIZE & (ALIGNMENT_SIZE - 1)) == 0);

714 715 716 717
#if !ISC_MEM_USE_INTERNAL_MALLOC
	UNUSED(target_size);
#endif

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

722 723 724 725 726 727 728 729 730
	if (isc_mutex_init(&ctx->lock) != ISC_R_SUCCESS) {
		UNEXPECTED_ERROR(__FILE__, __LINE__,
				 "isc_mutex_init() %s",
				 isc_msgcat_get(isc_msgcat, ISC_MSGSET_GENERAL,
						ISC_MSG_FAILED, "failed"));
		(memfree)(arg, ctx);
		return (ISC_R_UNEXPECTED);
	}

731
	if (init_max_size == 0U)
David Lawrence's avatar
David Lawrence committed
732 733 734
		ctx->max_size = DEF_MAX_SIZE;
	else
		ctx->max_size = init_max_size;
735 736 737 738
	ctx->references = 1;
	ctx->quota = 0;
	ctx->total = 0;
	ctx->inuse = 0;
739
	ctx->maxinuse = 0;
740 741 742 743 744 745 746 747 748 749 750
	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;
751
	ctx->checkfree = ISC_TRUE;
752
#if ISC_MEM_TRACKLINES
753
	ctx->debuglist = NULL;
754
#endif
755 756 757 758 759 760 761
	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
762
				(ctx->max_size+1) * sizeof(struct stats));
763 764 765 766
	if (ctx->stats == NULL) {
		result = ISC_R_NOMEMORY;
		goto error;
	}
Andreas Gustafsson's avatar
Andreas Gustafsson committed
767
	memset(ctx->stats, 0, (ctx->max_size + 1) * sizeof(struct stats));
768 769

#if ISC_MEM_USE_INTERNAL_MALLOC
David Lawrence's avatar
David Lawrence committed
770 771 772 773
	if (target_size == 0)
		ctx->mem_target = DEF_MEM_TARGET;
	else
		ctx->mem_target = target_size;
Andreas Gustafsson's avatar
Andreas Gustafsson committed
774
	ctx->freelists = (memalloc)(arg, ctx->max_size * sizeof(element *));
David Lawrence's avatar
David Lawrence committed
775
	if (ctx->freelists == NULL) {
776 777
		result = ISC_R_NOMEMORY;
		goto error;
David Lawrence's avatar
David Lawrence committed
778 779
	}
	memset(ctx->freelists, 0,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
780
	       ctx->max_size * sizeof(element *));
David Lawrence's avatar
David Lawrence committed
781 782 783 784 785 786
	ctx->basic_blocks = NULL;
	ctx->basic_table = NULL;
	ctx->basic_table_count = 0;
	ctx->basic_table_size = 0;
	ctx->lowest = NULL;
	ctx->highest = NULL;
787 788
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */

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

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

804 805
	ctx->memalloc_failures = 0;

David Lawrence's avatar
David Lawrence committed
806 807
	*ctxp = ctx;
	return (ISC_R_SUCCESS);
808 809

  error:
810 811
	if (ctx != NULL) {
		if (ctx->stats != NULL)
812 813
			(memfree)(arg, ctx->stats);
#if ISC_MEM_USE_INTERNAL_MALLOC
814
		if (ctx->freelists != NULL)
815 816
			(memfree)(arg, ctx->freelists);
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */
817
#if ISC_MEM_TRACKLINES
818
		if (ctx->debuglist != NULL)
819 820
			(ctx->memfree)(ctx->arg, ctx->debuglist);
#endif /* ISC_MEM_TRACKLINES */
821
		DESTROYLOCK(&ctx->lock);
822 823 824 825
		(memfree)(arg, ctx);
	}

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

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;

844
#if ISC_MEM_USE_INTERNAL_MALLOC
David Lawrence's avatar
David Lawrence committed
845
	INSIST(ISC_LIST_EMPTY(ctx->pools));
846 847
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */

848
#if ISC_MEM_TRACKLINES
849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866
	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);
				}
867
		}
868
		(ctx->memfree)(ctx->arg, ctx->debuglist);
869
	}
Michael Graff's avatar
Michael Graff committed
870
#endif
David Lawrence's avatar
David Lawrence committed
871 872 873
	INSIST(ctx->references == 0);

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

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

885
#if ISC_MEM_USE_INTERNAL_MALLOC
David Lawrence's avatar
David Lawrence committed
886 887 888 889
	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);
890
#endif /* ISC_MEM_USE_INTERNAL_MALLOC */
David Lawrence's avatar
David Lawrence committed
891 892 893

	ondest = ctx->ondestroy;

894
	DESTROYLOCK(&ctx->lock);
David Lawrence's avatar
David Lawrence committed
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 931 932 933
	(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;
}

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

960
#if ISC_MEM_USE_INTERNAL_MALLOC
961 962
	LOCK(&ctx->lock);
	mem_putunlocked(ctx, ptr, size);
963 964 965 966 967 968 969
#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);
970 971 972 973
	INSIST(ctx->references > 0);
	ctx->references--;
	if (ctx->references == 0)
		want_destroy = ISC_TRUE;
974

975 976 977 978 979 980
	UNLOCK(&ctx->lock);

	if (want_destroy)
		destroy(ctx);
}

David Lawrence's avatar
David Lawrence committed
981 982 983 984 985 986 987 988 989 990 991 992 993 994
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);
995
#if ISC_MEM_TRACKLINES
996 997 998
	if (ctx->references != 1)
		print_active(ctx, stderr);
#endif
David Lawrence's avatar
David Lawrence committed
999 1000 1001 1002
	REQUIRE(ctx->references == 1);
	ctx->references--;
	UNLOCK(&ctx->lock);

Brian Wellington's avatar
Brian Wellington committed
1003
	destroy(ctx);
David Lawrence's avatar
David Lawrence committed
1004 1005 1006 1007 1008 1009 1010

	*ctxp = NULL;
}

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

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

	return (res);
}


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

David Lawrence's avatar
David Lawrence committed
1025 1026
	REQUIRE(VALID_CONTEXT(ctx));