mem.c 30.6 KB
Newer Older
Bob Halley's avatar
base  
Bob Halley committed
1
/*
Bob Halley's avatar
Bob Halley committed
2
 * Copyright (C) 1997, 1998, 1999, 2000  Internet Software Consortium.
Bob Halley's avatar
Bob Halley committed
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.
Bob Halley's avatar
Bob Halley committed
7
 * 
Bob Halley's avatar
base  
Bob Halley committed
8 9 10 11 12 13 14 15 16 17
 * 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
Bob Halley committed
18
#include <config.h>
Bob Halley's avatar
base  
Bob Halley committed
19 20 21

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

Michael Graff's avatar
Michael Graff committed
24 25
#include <limits.h>

Bob Halley's avatar
Bob Halley committed
26
#include <isc/mem.h>
27
#include <isc/ondestroy.h>
28
#include <isc/string.h>
Bob Halley's avatar
Bob Halley committed
29

30
#ifndef ISC_SINGLETHREADED
Bob Halley's avatar
update  
Bob Halley committed
31
#include <isc/mutex.h>
Michael Graff's avatar
Michael Graff committed
32
#include <isc/util.h>
Bob Halley's avatar
Bob Halley committed
33
#else
Bob Halley's avatar
Bob Halley committed
34 35
#define LOCK(l)
#define UNLOCK(l)
Bob Halley's avatar
update  
Bob Halley committed
36 37
#endif

Bob Halley's avatar
Bob Halley committed
38
#ifndef ISC_MEM_FILL
39 40
	/*
	 * XXXMPA
Bob Halley's avatar
Bob Halley committed
41
	 * We want this on during development to catch:
42 43 44 45 46 47
	 * 1. some reference after free bugs.
	 * 2. some failure to initalise bugs.
	 */
#define ISC_MEM_FILL 1
#endif

Michael Graff's avatar
Michael Graff committed
48 49 50 51 52 53 54 55
#ifndef ISC_MEMPOOL_NAMES
/*
 * During development it is nice to be able to see names associated with
 * memory pools.
 */
#define ISC_MEMPOOL_NAMES 1
#endif

56 57 58 59 60 61 62 63 64 65 66

/*
 * Constants.
 */

#define DEF_MAX_SIZE		1100
#define DEF_MEM_TARGET		4096
#define ALIGNMENT_SIZE		8
#define NUM_BASIC_BLOCKS	64			/* must be > 1 */
#define TABLE_INCREMENT		1024

Bob Halley's avatar
base  
Bob Halley committed
67 68 69 70
/*
 * Types.
 */

71 72 73 74 75
typedef struct element element;

struct element {
	element *		next;
};
Bob Halley's avatar
base  
Bob Halley committed
76 77 78 79 80

typedef struct {
	/*
	 * This structure must be ALIGNMENT_SIZE bytes.
	 */
81 82 83 84
	union {
		size_t		size;
		char		bytes[ALIGNMENT_SIZE];
	} u;
Bob Halley's avatar
Bob Halley committed
85
} size_info;
Bob Halley's avatar
base  
Bob Halley committed
86 87

struct stats {
Bob Halley's avatar
Bob Halley committed
88 89 90 91
	unsigned long		gets;
	unsigned long		totalgets;
	unsigned long		blocks;
	unsigned long		freefrags;
Bob Halley's avatar
base  
Bob Halley committed
92 93
};

94 95
#define MEM_MAGIC		0x4D656d43U	/* MemC. */
#define VALID_CONTEXT(c)	((c) != NULL && (c)->magic == MEM_MAGIC)
Bob Halley's avatar
Bob Halley committed
96

97
struct isc_mem {
Bob Halley's avatar
Bob Halley committed
98
	unsigned int		magic;
99
	isc_ondestroy_t		ondestroy;
Bob Halley's avatar
Bob Halley committed
100
	isc_mutex_t		lock;
101 102 103
	isc_memalloc_t		memalloc;
	isc_memfree_t		memfree;
	void *			arg;
Bob Halley's avatar
base  
Bob Halley committed
104 105
	size_t			max_size;
	size_t			mem_target;
Bob Halley's avatar
Bob Halley committed
106 107
	element **		freelists;
	element *		basic_blocks;
108 109 110
	unsigned char **	basic_table;
	unsigned int		basic_table_count;
	unsigned int		basic_table_size;
Bob Halley's avatar
Bob Halley committed
111 112
	unsigned char *		lowest;
	unsigned char *		highest;
113
	isc_boolean_t		checkfree;
114
	isc_boolean_t		trysplit;
Bob Halley's avatar
base  
Bob Halley committed
115
	struct stats *		stats;
116
	unsigned int		references;
117
	size_t			quota;
Bob Halley's avatar
Bob Halley committed
118
	size_t			total;
119
	size_t			inuse;
Michael Graff's avatar
Michael Graff committed
120 121 122 123 124 125 126
	ISC_LIST(isc_mempool_t)	pools;
};

#define MEMPOOL_MAGIC		0x4D454d70U	/* MEMp. */
#define VALID_MEMPOOL(c)	((c) != NULL && (c)->magic == MEMPOOL_MAGIC)

struct isc_mempool {
Michael Graff's avatar
Michael Graff committed
127
	/* always unlocked */
Michael Graff's avatar
Michael Graff committed
128
	unsigned int	magic;		/* magic number */
Michael Graff's avatar
Michael Graff committed
129
	isc_mutex_t    *lock;		/* optional lock */
Michael Graff's avatar
Michael Graff committed
130
	isc_mem_t      *mctx;		/* our memory context */
Michael Graff's avatar
Michael Graff committed
131 132 133
	/* 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
134 135 136 137 138 139 140 141 142
	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
143 144 145 146
	/* Debugging only. */
#if ISC_MEMPOOL_NAMES
	char		name[16];	/* printed name in stats reports */
#endif
Bob Halley's avatar
base  
Bob Halley committed
147 148
};

149 150 151
/*
 * Forward.
 */
Bob Halley's avatar
base  
Bob Halley committed
152

Michael Graff's avatar
Michael Graff committed
153
static inline size_t		quantize(size_t);
Mark Andrews's avatar
Mark Andrews committed
154 155
static inline void		mem_putunlocked(isc_mem_t *, void *, size_t);
static inline void *		mem_getunlocked(isc_mem_t *, size_t);
Bob Halley's avatar
base  
Bob Halley committed
156

157 158 159
/*
 * Private Inline-able.
 */
Bob Halley's avatar
base  
Bob Halley committed
160

161
static inline size_t
Bob Halley's avatar
base  
Bob Halley committed
162
quantize(size_t size) {
163
	int temp;
Bob Halley's avatar
base  
Bob Halley committed
164 165

	/*
166
	 * Round up the result in order to get a size big
Bob Halley's avatar
base  
Bob Halley committed
167 168 169
	 * enough to satisfy the request and be aligned on ALIGNMENT_SIZE
	 * byte boundaries.
	 */
170

171 172
	if (size == 0)
		return (ALIGNMENT_SIZE);
Mark Andrews's avatar
Mark Andrews committed
173
	temp = size + (ALIGNMENT_SIZE - 1);
174
	return (temp - temp % ALIGNMENT_SIZE); 
Bob Halley's avatar
base  
Bob Halley committed
175 176
}

177 178 179
/*
 * Private.
 */
180 181 182 183 184 185 186 187 188 189

static void *
default_memalloc(void *arg, size_t size) {
	(void)arg;
	return (malloc(size));
}

static void
default_memfree(void *arg, void *ptr) {
	(void)arg;
James Brister's avatar
James Brister committed
190
	free(ptr);
191 192
}

193 194 195
/*
 * Public.
 */
Bob Halley's avatar
base  
Bob Halley committed
196

Bob Halley's avatar
Bob Halley committed
197
isc_result_t
198 199 200
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)
Bob Halley's avatar
Bob Halley committed
201
{
202
	isc_mem_t *ctx;
Bob Halley's avatar
Bob Halley committed
203 204

	REQUIRE(ctxp != NULL && *ctxp == NULL);
205 206
	REQUIRE(memalloc != NULL);
	REQUIRE(memfree != NULL);
Bob Halley's avatar
base  
Bob Halley committed
207

208
	ctx = (memalloc)(arg, sizeof *ctx);
Michael Graff's avatar
Michael Graff committed
209 210 211
	if (ctx == NULL)
		return (ISC_R_NOMEMORY);

Bob Halley's avatar
base  
Bob Halley committed
212 213 214 215 216 217 218 219
	if (init_max_size == 0)
		ctx->max_size = DEF_MAX_SIZE;
	else
		ctx->max_size = init_max_size;
	if (target_size == 0)
		ctx->mem_target = DEF_MEM_TARGET;
	else
		ctx->mem_target = target_size;
220 221 222 223
	ctx->memalloc = memalloc;
	ctx->memfree = memfree;
	ctx->arg = arg;
	ctx->freelists = (memalloc)(arg, ctx->max_size * sizeof (element *));
Mark Andrews's avatar
Mark Andrews committed
224
	if (ctx->freelists == NULL) {
225
		(memfree)(arg, ctx);
Bob Halley's avatar
Bob Halley committed
226
		return (ISC_R_NOMEMORY);
Bob Halley's avatar
base  
Bob Halley committed
227
	}
228
	ctx->checkfree = ISC_TRUE;
229
	ctx->trysplit = ISC_FALSE;
Bob Halley's avatar
Bob Halley committed
230 231
	memset(ctx->freelists, 0,
	       ctx->max_size * sizeof (element *));
232 233
	ctx->stats = (memalloc)(arg,
				(ctx->max_size+1) * sizeof (struct stats));
Bob Halley's avatar
base  
Bob Halley committed
234
	if (ctx->stats == NULL) {
235 236
		(memfree)(arg, ctx->freelists);
		(memfree)(arg, ctx);
Bob Halley's avatar
Bob Halley committed
237
		return (ISC_R_NOMEMORY);
Bob Halley's avatar
base  
Bob Halley committed
238 239 240
	}
	memset(ctx->stats, 0, (ctx->max_size + 1) * sizeof (struct stats));
	ctx->basic_blocks = NULL;
241 242 243
	ctx->basic_table = NULL;
	ctx->basic_table_count = 0;
	ctx->basic_table_size = 0;
Bob Halley's avatar
base  
Bob Halley committed
244 245
	ctx->lowest = NULL;
	ctx->highest = NULL;
Bob Halley's avatar
Bob Halley committed
246
	if (isc_mutex_init(&ctx->lock) != ISC_R_SUCCESS) {
247 248 249
		(memfree)(arg, ctx->stats);
		(memfree)(arg, ctx->freelists);
		(memfree)(arg, ctx);
Bob Halley's avatar
Bob Halley committed
250
		UNEXPECTED_ERROR(__FILE__, __LINE__,
Bob Halley's avatar
Bob Halley committed
251
				 "isc_mutex_init() failed");
Bob Halley's avatar
Bob Halley committed
252
		return (ISC_R_UNEXPECTED);
Bob Halley's avatar
update  
Bob Halley committed
253
	}
254
	ctx->references = 1;
255
	ctx->quota = 0;
Bob Halley's avatar
Bob Halley committed
256
	ctx->total = 0;
257
	ctx->inuse = 0;
Bob Halley's avatar
Bob Halley committed
258
	ctx->magic = MEM_MAGIC;
259
	isc_ondestroy_init(&ctx->ondestroy);
Michael Graff's avatar
Michael Graff committed
260 261
	ISC_LIST_INIT(ctx->pools);

Bob Halley's avatar
base  
Bob Halley committed
262
	*ctxp = ctx;
Bob Halley's avatar
Bob Halley committed
263
	return (ISC_R_SUCCESS);
Bob Halley's avatar
base  
Bob Halley committed
264 265
}

266 267 268 269 270 271 272 273 274
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));
}

275 276
static void
destroy(isc_mem_t *ctx) {
277
	unsigned int i;
278
	isc_ondestroy_t ondest;
279

Bob Halley's avatar
Bob Halley committed
280
	ctx->magic = 0;
281

Michael Graff's avatar
Michael Graff committed
282
	INSIST(ISC_LIST_EMPTY(ctx->pools));
283
	INSIST(ctx->references == 0);
Michael Graff's avatar
Michael Graff committed
284

285 286 287 288 289 290 291 292 293 294 295
	if (ctx->checkfree) {
		for (i = 0; i <= ctx->max_size; i++)
			INSIST(ctx->stats[i].gets == 0);
	}

#if 0					/* XXX brister debugging */
	for (i = 0; i < ctx->basic_table_count; i++)
		memset(ctx->basic_table[i], 0x0,
		       NUM_BASIC_BLOCKS * ctx->mem_target);
#endif
	
296 297

	for (i = 0; i < ctx->basic_table_count; i++)
298 299 300 301
		(ctx->memfree)(ctx->arg, ctx->basic_table[i]);
	(ctx->memfree)(ctx->arg, ctx->freelists);
	(ctx->memfree)(ctx->arg, ctx->stats);
	(ctx->memfree)(ctx->arg, ctx->basic_table);
302

303 304
	ondest = ctx->ondestroy;

Bob Halley's avatar
Bob Halley committed
305
	(void)isc_mutex_destroy(&ctx->lock);
306
	(ctx->memfree)(ctx->arg, ctx);
Bob Halley's avatar
base  
Bob Halley committed
307

308
	isc_ondestroy_notify(&ondest, ctx);
309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367
}

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

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

	/*
	 * 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);
	REQUIRE(ctx->references == 1);
	ctx->references--;
	if (ctx->references == 0)
		want_destroy = ISC_TRUE;
	UNLOCK(&ctx->lock);

	if (want_destroy)
		destroy(ctx);
368

Bob Halley's avatar
base  
Bob Halley committed
369 370 371
	*ctxp = NULL;
}

372 373 374 375 376 377 378 379 380 381 382 383
isc_result_t
isc_mem_ondestroy(isc_mem_t *ctx, isc_task_t *task, isc_event_t **event) {
	isc_result_t res;
	
	LOCK(&ctx->lock);
	res = isc_ondestroy_register(&ctx->ondestroy, task, event);
	UNLOCK(&ctx->lock);

	return (res);
}


384 385 386 387 388 389 390 391 392 393 394
isc_result_t
isc_mem_restore(isc_mem_t *ctx) {
	isc_result_t result;

	result = isc_mutex_init(&ctx->lock); 
	if (result != ISC_R_SUCCESS)
		ctx->magic = 0;

	return (result);
}

395
static inline isc_boolean_t
396
more_basic_blocks(isc_mem_t *ctx) {
397 398 399 400 401
	void *new;
	unsigned char *curr, *next;
	unsigned char *first, *last;
	unsigned char **table;
	unsigned int table_size;
Bob Halley's avatar
Bob Halley committed
402
	size_t increment;
403 404 405 406
	int i;

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

407 408 409
	/*
	 * Did we hit the quota for this context?
	 */
Bob Halley's avatar
Bob Halley committed
410 411
	increment = NUM_BASIC_BLOCKS * ctx->mem_target;
	if (ctx->quota != 0 && ctx->total + increment > ctx->quota)
412
		return (ISC_FALSE);
413 414 415

	INSIST(ctx->basic_table_count <= ctx->basic_table_size);
	if (ctx->basic_table_count == ctx->basic_table_size) {
416
		table_size = ctx->basic_table_size + TABLE_INCREMENT;
417 418
		table = (ctx->memalloc)(ctx->arg,
					table_size * sizeof (unsigned char *));
419
		if (table == NULL)
420
			return (ISC_FALSE);
421 422 423 424
		if (ctx->basic_table_size != 0) {
			memcpy(table, ctx->basic_table,
			       ctx->basic_table_size *
			       sizeof (unsigned char *));
425
			(ctx->memfree)(ctx->arg, ctx->basic_table);
426
		}
427 428
		ctx->basic_table = table;
		ctx->basic_table_size = table_size;
429
	}
430

431
	new = (ctx->memalloc)(ctx->arg, NUM_BASIC_BLOCKS * ctx->mem_target);
432
	if (new == NULL)
433
		return (ISC_FALSE);
Bob Halley's avatar
Bob Halley committed
434
	ctx->total += increment;
435 436
	ctx->basic_table[ctx->basic_table_count] = new;
	ctx->basic_table_count++;
437

438 439 440
	curr = new;
	next = curr + ctx->mem_target;
	for (i = 0; i < (NUM_BASIC_BLOCKS - 1); i++) {
441
		((element *)curr)->next = (element *)next;
442 443 444 445 446 447 448
		curr = next;
		next += ctx->mem_target;
	}
	/*
	 * curr is now pointing at the last block in the
	 * array.
	 */
Bob Halley's avatar
Bob Halley committed
449
	((element *)curr)->next = NULL;
450 451 452 453 454 455 456
	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;
457 458

	return (ISC_TRUE);
459 460
}

Bob Halley's avatar
base  
Bob Halley committed
461
void *
462
isc__mem_get(isc_mem_t *ctx, size_t size) {
Bob Halley's avatar
base  
Bob Halley committed
463 464
	void *ret;

Bob Halley's avatar
Bob Halley committed
465
	REQUIRE(VALID_CONTEXT(ctx));
Michael Graff's avatar
Michael Graff committed
466

Bob Halley's avatar
Bob Halley committed
467
	LOCK(&ctx->lock);
Mark Andrews's avatar
Mark Andrews committed
468
	ret = mem_getunlocked(ctx, size);
Michael Graff's avatar
Michael Graff committed
469 470 471 472 473
	UNLOCK(&ctx->lock);

	return (ret);
}

474
#if ISC_MEM_FILL != 0 && ISC_MEM_CHECKOVERRUN != 0
475 476 477 478 479 480 481 482 483 484 485 486
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++;
	}
}
487
#endif
488

489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608
static inline void
split(isc_mem_t *ctx, size_t size, size_t new_size) {
	unsigned char *ptr;
	size_t remaining_size;

	/*
	 * Unlink a frag of size 'size'.
	 */
	ptr = (unsigned char *)ctx->freelists[size];
	ctx->freelists[size] = ctx->freelists[size]->next;
	ctx->stats[size].freefrags--;

	/*
	 * Create a frag of size 'new_size' and link it in.
	 */
	((element *)ptr)->next = ctx->freelists[new_size];
	ctx->freelists[new_size] = (element *)ptr;
	ctx->stats[new_size].freefrags++;

	/*
	 * Create a frag of size 'size - new_size' and link it in.
	 */
	remaining_size = size - new_size;
	ptr += new_size;
	((element *)ptr)->next = ctx->freelists[remaining_size];
	ctx->freelists[remaining_size] = (element *)ptr;
	ctx->stats[remaining_size].freefrags++;
}

static inline isc_boolean_t
try_split(isc_mem_t *ctx, size_t new_size) {
	size_t i, doubled_size;

	if (!ctx->trysplit)
		return (ISC_FALSE);

	/*
	 * Try splitting a frag that's at least twice as big as the size
	 * we want.
	 */
	doubled_size = new_size * 2;
	for (i = doubled_size;
	     i < ctx->max_size;
	     i += ALIGNMENT_SIZE) {
		if (ctx->freelists[i] != NULL) {
			split(ctx, i, new_size);
			return (ISC_TRUE);
		}
	}

	/*
	 * No luck.  Try splitting any frag bigger than the size we need.
	 */
	for (i = new_size + ALIGNMENT_SIZE;
	     i < doubled_size;
	     i += ALIGNMENT_SIZE) {
		if (ctx->freelists[i] != NULL) {
			split(ctx, i, new_size);
			return (ISC_TRUE);
		}
	}

	return (ISC_FALSE);
}

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.
			 */
			/*
			 * XXXRTH  "At quota" notification here. 
			 */
			/*
			 * Maybe we can split one of our existing
			 * list frags.
			 */
			return (try_split(ctx, new_size));
		}
	}

	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;
	for (i = 0; i < (frags - 1); i++) {
		((element *)curr)->next = (element *)next;
		curr = next;
		next += new_size;
	}
	/*
	 * 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
609
static inline void *
610
mem_getunlocked(isc_mem_t *ctx, size_t size) {
Michael Graff's avatar
Michael Graff committed
611 612
	size_t new_size = quantize(size);
	void *ret;
Bob Halley's avatar
base  
Bob Halley committed
613 614

	if (size >= ctx->max_size || new_size >= ctx->max_size) {
615 616 617
		/*
		 * memget() was called on something beyond our upper limit.
		 */
Bob Halley's avatar
Bob Halley committed
618 619 620 621
		if (ctx->quota != 0 && ctx->total + size > ctx->quota) {
			ret = NULL;
			goto done;
		}
Mark Andrews's avatar
Mark Andrews committed
622
		ret = (ctx->memalloc)(ctx->arg, size);
Bob Halley's avatar
base  
Bob Halley committed
623
		if (ret != NULL) {
Bob Halley's avatar
Bob Halley committed
624
			ctx->total += size;
625
			ctx->inuse += size;
Bob Halley's avatar
base  
Bob Halley committed
626 627
			ctx->stats[ctx->max_size].gets++;
			ctx->stats[ctx->max_size].totalgets++;
Mark Andrews's avatar
Mark Andrews committed
628 629 630 631 632 633
			/*
			 * 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;
Bob Halley's avatar
base  
Bob Halley committed
634 635 636 637 638 639 640 641 642
		}
		goto done;
	}

	/* 
	 * 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.
	 */
643 644
	if (ctx->freelists[new_size] == NULL && !more_frags(ctx, new_size))
		return (NULL);
Bob Halley's avatar
base  
Bob Halley committed
645

646 647 648
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Bob Halley's avatar
base  
Bob Halley committed
649 650 651 652 653 654 655 656 657 658 659 660
	ret = ctx->freelists[new_size];
	ctx->freelists[new_size] = ctx->freelists[new_size]->next;

	/* 
	 * 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--;
661
	ctx->inuse += new_size;
Bob Halley's avatar
base  
Bob Halley committed
662 663 664

 done:

665 666 667 668 669
#if ISC_MEM_FILL
	if (ret != NULL)
		memset(ret, 0xbe, new_size); /* Mnemonic for "beef". */
#endif

Bob Halley's avatar
base  
Bob Halley committed
670 671 672 673
	return (ret);
}

void
674
isc__mem_put(isc_mem_t *ctx, void *mem, size_t size) {
Bob Halley's avatar
Bob Halley committed
675
	REQUIRE(VALID_CONTEXT(ctx));
Michael Graff's avatar
Michael Graff committed
676

Bob Halley's avatar
Bob Halley committed
677
	LOCK(&ctx->lock);
Mark Andrews's avatar
Mark Andrews committed
678
	mem_putunlocked(ctx, mem, size);
Michael Graff's avatar
Michael Graff committed
679 680 681 682
	UNLOCK(&ctx->lock);
}

static inline void
683
mem_putunlocked(isc_mem_t *ctx, void *mem, size_t size) {
Michael Graff's avatar
Michael Graff committed
684
	size_t new_size = quantize(size);
Bob Halley's avatar
base  
Bob Halley committed
685

686
	if (size == ctx->max_size || new_size >= ctx->max_size) {
687 688 689
		/*
		 * memput() called on something beyond our upper limit.
		 */
Mark Andrews's avatar
Mark Andrews committed
690 691 692
#if ISC_MEM_FILL
		memset(mem, 0xde, size); /* Mnemonic for "dead". */
#endif
693
		(ctx->memfree)(ctx->arg, mem);
Bob Halley's avatar
base  
Bob Halley committed
694 695
		INSIST(ctx->stats[ctx->max_size].gets != 0);
		ctx->stats[ctx->max_size].gets--;
Bob Halley's avatar
Bob Halley committed
696
		INSIST(size <= ctx->total);
697
		ctx->inuse -= size;
Bob Halley's avatar
Bob Halley committed
698
		ctx->total -= size;
Michael Graff's avatar
Michael Graff committed
699
		return;
Bob Halley's avatar
base  
Bob Halley committed
700 701
	}

Mark Andrews's avatar
Mark Andrews committed
702
#if ISC_MEM_FILL
703 704 705
#if ISC_MEM_CHECKOVERRUN
	check_overrun(mem, size, new_size);
#endif
Mark Andrews's avatar
Mark Andrews committed
706 707
	memset(mem, 0xde, new_size); /* Mnemonic for "dead". */
#endif
708

709 710 711
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Mark Andrews's avatar
Mark Andrews committed
712 713
	((element *)mem)->next = ctx->freelists[new_size];
	ctx->freelists[new_size] = (element *)mem;
Bob Halley's avatar
base  
Bob Halley committed
714 715 716 717 718 719 720 721 722 723

	/* 
	 * 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++;
724
	ctx->inuse -= new_size;
Bob Halley's avatar
base  
Bob Halley committed
725 726 727
}

void *
Bob Halley's avatar
Bob Halley committed
728
isc__mem_getdebug(isc_mem_t *ctx, size_t size, const char *file, int line) {
Bob Halley's avatar
base  
Bob Halley committed
729
	void *ptr;
Bob Halley's avatar
Bob Halley committed
730

Bob Halley's avatar
Bob Halley committed
731
	ptr = isc__mem_get(ctx, size);
Bob Halley's avatar
base  
Bob Halley committed
732
	fprintf(stderr, "%s:%d: mem_get(%p, %lu) -> %p\n", file, line,
Bob Halley's avatar
Bob Halley committed
733
		ctx, (unsigned long)size, ptr);
Bob Halley's avatar
base  
Bob Halley committed
734 735 736 737
	return (ptr);
}

void
Bob Halley's avatar
Bob Halley committed
738
isc__mem_putdebug(isc_mem_t *ctx, void *ptr, size_t size, const char *file,
Bob Halley's avatar
Bob Halley committed
739
		 int line)
Bob Halley's avatar
base  
Bob Halley committed
740 741
{
	fprintf(stderr, "%s:%d: mem_put(%p, %p, %lu)\n", file, line, 
Bob Halley's avatar
Bob Halley committed
742
		ctx, ptr, (unsigned long)size);
Bob Halley's avatar
Bob Halley committed
743
	isc__mem_put(ctx, ptr, size);
Bob Halley's avatar
base  
Bob Halley committed
744 745
}

746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769
isc_result_t
isc_mem_preallocate(isc_mem_t *ctx) {
	size_t i;
	isc_result_t result = ISC_R_SUCCESS;
	void *ptr;

	REQUIRE(VALID_CONTEXT(ctx));

	LOCK(&ctx->lock);

	for (i = 0; i < ctx->max_size; i += ALIGNMENT_SIZE) {
		ptr = mem_getunlocked(ctx, i);
		if (ptr == NULL) {
			result = ISC_R_NOMEMORY;
			break;
		}
		mem_putunlocked(ctx, ptr, i);
	}
		
	UNLOCK(&ctx->lock);

	return (result);
}

Bob Halley's avatar
base  
Bob Halley committed
770 771 772 773
/*
 * Print the stats[] on the stream "out" with suitable formatting.
 */
void
774
isc_mem_stats(isc_mem_t *ctx, FILE *out) {
Bob Halley's avatar
base  
Bob Halley committed
775
	size_t i;
Michael Graff's avatar
Michael Graff committed
776 777
	const struct stats *s;
	const isc_mempool_t *pool;
Bob Halley's avatar
base  
Bob Halley committed
778

Bob Halley's avatar
Bob Halley committed
779 780
	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
781

Michael Graff's avatar
Michael Graff committed
782
	if (ctx->freelists != NULL) {
783
		for (i = 0; i <= ctx->max_size; i++) {
Michael Graff's avatar
Michael Graff committed
784 785 786 787 788 789 790 791 792 793 794 795 796 797
			s = &ctx->stats[i];

			if (s->totalgets == 0 && s->gets == 0)
				continue;
			fprintf(out, "%s%5d: %11lu gets, %11lu rem",
				(i == ctx->max_size) ? ">=" : "  ",
				i, s->totalgets, s->gets);
			if (s->blocks != 0)
				fprintf(out, " (%lu bl, %lu ff)",
					s->blocks, s->freefrags);
			fputc('\n', out);
		}
	}

Michael Graff's avatar
Michael Graff committed
798 799 800 801 802 803 804
	/*
	 * Note that since a pool can be locked now, these stats might be
	 * somewhat off if the pool is in active use at the time the stats
	 * are dumped.  The link fields are protected by the isc_mem_t's
	 * lock, however, so walking this list and extracting integers from
	 * stats fields is always safe.
	 */
Michael Graff's avatar
Michael Graff committed
805 806 807
	pool = ISC_LIST_HEAD(ctx->pools);
	if (pool != NULL) {
		fprintf(out, "[Pool statistics]\n");
Michael Graff's avatar
Michael Graff committed
808 809
		fprintf(out, "%15s %10s %10s %10s %10s %10s %10s %10s %1s\n",
			"name", "size", "maxalloc", "allocated", "freecount",
Michael Graff's avatar
Michael Graff committed
810
			"freemax", "fillcount", "gets", "L");
Michael Graff's avatar
Michael Graff committed
811 812
	}
	while (pool != NULL) {
Michael Graff's avatar
Michael Graff committed
813 814 815 816
		fprintf(out, "%15s %10u %10u %10u %10u %10u %10u %10u %s\n",
			pool->name, pool->size, pool->maxalloc,
			pool->allocated, pool->freecount, pool->freemax,
			pool->fillcount, pool->gets,
Michael Graff's avatar
Michael Graff committed
817
			(pool->lock == NULL ? "N" : "Y"));
Michael Graff's avatar
Michael Graff committed
818
		pool = ISC_LIST_NEXT(pool, link);
Bob Halley's avatar
base  
Bob Halley committed
819 820
	}

Bob Halley's avatar
Bob Halley committed
821
	UNLOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
822 823
}

Bob Halley's avatar
Bob Halley committed
824
isc_boolean_t
825
isc_mem_valid(isc_mem_t *ctx, void *ptr) {
Bob Halley's avatar
Bob Halley committed
826
	unsigned char *cp = ptr;
Bob Halley's avatar
Bob Halley committed
827
	isc_boolean_t result = ISC_FALSE;
Bob Halley's avatar
base  
Bob Halley committed
828

Bob Halley's avatar
Bob Halley committed
829 830
	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
831 832

	if (ctx->lowest != NULL && cp >= ctx->lowest && cp <= ctx->highest)
Bob Halley's avatar
Bob Halley committed
833
		result = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
834

Bob Halley's avatar
Bob Halley committed
835
	UNLOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
836

Bob Halley's avatar
Bob Halley committed
837
	return (result);
Bob Halley's avatar
base  
Bob Halley committed
838 839 840
}

/*
841 842
 * Replacements for malloc() and free() -- they implicitly remember the
 * size of the object allocated (with some additional overhead).
Bob Halley's avatar
base  
Bob Halley committed
843 844 845
 */

void *
Bob Halley's avatar
Bob Halley committed
846
isc__mem_allocate(isc_mem_t *ctx, size_t size) {
Bob Halley's avatar
Bob Halley committed
847
	size_info *si;
Bob Halley's avatar
base  
Bob Halley committed
848 849

	size += ALIGNMENT_SIZE;
Bob Halley's avatar
Bob Halley committed
850
	si = isc__mem_get(ctx, size);
Bob Halley's avatar
base  
Bob Halley committed
851 852
	if (si == NULL)
		return (NULL);
853
	si->u.size = size;
Bob Halley's avatar
base  
Bob Halley committed
854 855 856
	return (&si[1]);
}

857
void *
Bob Halley's avatar
Bob Halley committed
858
isc__mem_allocatedebug(isc_mem_t *ctx, size_t size, const char *file,
859 860 861
			int line) {
	size_info *si;

Bob Halley's avatar
Bob Halley committed
862
	si = isc__mem_allocate(ctx, size);
863 864 865 866 867 868 869 870
	if (si == NULL)
		return (NULL);
	fprintf(stderr, "%s:%d: mem_get(%p, %lu) -> %p\n", file, line,
		ctx, (unsigned long)si[-1].u.size, si);
	return (si);
}

void
Bob Halley's avatar
Bob Halley committed
871
isc__mem_free(isc_mem_t *ctx, void *ptr) {
872 873 874
	size_info *si;

	si = &(((size_info *)ptr)[-1]);
Bob Halley's avatar
Bob Halley committed
875
	isc__mem_put(ctx, si, si->u.size);
876 877
}

Bob Halley's avatar
base  
Bob Halley committed
878
void
Bob Halley's avatar
Bob Halley committed
879
isc__mem_freedebug(isc_mem_t *ctx, void *ptr, const char *file, int line) {
Bob Halley's avatar
Bob Halley committed
880
	size_info *si;
Bob Halley's avatar
base  
Bob Halley committed
881

Bob Halley's avatar
Bob Halley committed
882
	si = &(((size_info *)ptr)[-1]);
883 884
	fprintf(stderr, "%s:%d: mem_put(%p, %p, %lu)\n", file, line, 
		ctx, ptr, (unsigned long)si->u.size);
Bob Halley's avatar
Bob Halley committed
885
	isc__mem_put(ctx, si, si->u.size);
Bob Halley's avatar
base  
Bob Halley committed
886 887
}

Bob Halley's avatar
Bob Halley committed
888 889 890 891
/*
 * Other useful things.
 */

Bob Halley's avatar
Bob Halley committed
892
char *
Bob Halley's avatar
Bob Halley committed
893
isc__mem_strdup(isc_mem_t *mctx, const char *s) {
Bob Halley's avatar
Bob Halley committed
894 895 896 897
	size_t len;
	char *ns;

	len = strlen(s);
Bob Halley's avatar
Bob Halley committed
898
	ns = isc__mem_allocate(mctx, len + 1);
Bob Halley's avatar
Bob Halley committed
899 900 901 902 903 904 905
	if (ns == NULL)
		return (NULL);
	strncpy(ns, s, len + 1);
	
	return (ns);
}

906
char *
Bob Halley's avatar
Bob Halley committed
907
isc__mem_strdupdebug(isc_mem_t *mctx, const char *s, const char *file,
908 909 910 911
		      int line) {
	char *ptr;
	size_info *si;

Bob Halley's avatar
Bob Halley committed
912
	ptr = isc__mem_strdup(mctx, s);
913 914 915 916 917 918
	si = &(((size_info *)ptr)[-1]);
	fprintf(stderr, "%s:%d: mem_get(%p, %lu) -> %p\n", file, line,
		mctx, (unsigned long)si->u.size, ptr);
	return (ptr);
}

919 920 921 922
void
isc_mem_setdestroycheck(isc_mem_t *ctx, isc_boolean_t flag) {
	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);
923

924
	ctx->checkfree = flag;
925

926 927 928 929 930 931 932 933 934 935 936
	UNLOCK(&ctx->lock);
}

void
isc_mem_setsplit(isc_mem_t *ctx, isc_boolean_t flag) {
	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);

	ctx->trysplit = flag;

	UNLOCK(&ctx->lock);
937 938 939
}


940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967
/*
 * Quotas
 */

void
isc_mem_setquota(isc_mem_t *ctx, size_t quota) {
	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);

	ctx->quota = quota;

	UNLOCK(&ctx->lock);
}

size_t
isc_mem_getquota(isc_mem_t *ctx) {
	size_t quota;

	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);

	quota = ctx->quota;

	UNLOCK(&ctx->lock);

	return (quota);
}

968 969 970 971 972 973 974 975 976 977 978 979 980 981
size_t
isc_mem_inuse(isc_mem_t *ctx) {
	size_t inuse;

	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);

	inuse = ctx->inuse;

	UNLOCK(&ctx->lock);

	return (inuse);
}

Bob Halley's avatar
Bob Halley committed
982 983
#ifdef ISC_MEMCLUSTER_LEGACY

Bob Halley's avatar
base  
Bob Halley committed
984 985 986 987
/*
 * Public Legacy.
 */

988
static isc_mem_t *default_context = NULL;
Bob Halley's avatar
Bob Halley committed
989

Bob Halley's avatar
base  
Bob Halley committed
990 991
int
meminit(size_t init_max_size, size_t target_size) {
992 993 994
	/*
	 * Need default_context lock here.
	 */
Bob Halley's avatar
base  
Bob Halley committed
995 996
	if (default_context != NULL)
		return (-1);
Bob Halley's avatar
Bob Halley committed
997
	return (isc_mem_create(init_max_size, target_size, &default_context));
Bob Halley's avatar
base  
Bob Halley committed
998 999
}

1000
isc_mem_t *
Bob Halley's avatar
base  
Bob Halley committed
1001
mem_default_context(void) {
1002 1003 1004
	/*
	 * Need default_context lock here.
	 */
Bob Halley's avatar
base  
Bob Halley committed
1005 1006 1007 1008 1009 1010
	if (default_context == NULL && meminit(0, 0) == -1)
		return (NULL);
	return (default_context);
}

void *
1011 1012 1013 1014
isc__legacy_memget(size_t size) {
	/*
	 * Need default_context lock here.
	 */
Bob Halley's avatar
base  
Bob Halley committed
1015 1016
	if (default_context == NULL && meminit(0, 0) == -1)
		return (NULL);
1017
	return (isc__mem_get(default_context, size));
Bob Halley's avatar
base  
Bob Halley committed
1018 1019 1020
}

void
1021 1022 1023 1024
isc__legacy_memput(void *mem, size_t size) {
	/*
	 * Need default_context lock here.
	 */
Bob Halley's avatar
base  
Bob Halley committed
1025
	REQUIRE(default_context != NULL);
1026
	isc__mem_put(default_context, mem, size);
Bob Halley's avatar
base  
Bob Halley committed
1027 1028 1029
}

void *
1030
isc__legacy_memget_debug(size_t size, const char *file, int line) {
Bob Halley's avatar
base  
Bob Halley committed
1031
	void *ptr;
1032
	ptr = isc__legacy_memget(size);
Bob Halley's avatar
base  
Bob Halley committed
1033
	fprintf(stderr, "%s:%d: memget(%lu) -> %p\n", file, line,
Bob Halley's avatar
Bob Halley committed
1034
		(unsigned long)size, ptr);
Bob Halley's avatar
base  
Bob Halley committed
1035 1036 1037 1038
	return (ptr);
}

void
1039
isc__legacy_memput_debug(void *ptr, size_t size, const char *file, int line) {
Bob Halley's avatar
base  
Bob Halley committed
1040
	fprintf(stderr, "%s:%d: memput(%p, %lu)\n", file, line, 
Bob Halley's avatar
Bob Halley committed
1041
		ptr, (unsigned long)size);
1042
	isc__legacy_memput(ptr, size);
Bob Halley's avatar
base  
Bob Halley committed
1043 1044 1045 1046
}

int
memvalid(void *ptr) {
1047 1048 1049
	/*
	 * Need default_context lock here.
	 */
Bob Halley's avatar
base  
Bob Halley committed
1050
	REQUIRE(default_context != NULL);
1051
	return (isc_mem_valid(default_context, ptr));
Bob Halley's avatar
base  
Bob Halley committed
1052 1053 1054 1055
}

void
memstats(FILE *out) {