mem.c 30.4 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 24
#include <string.h>

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

Bob Halley's avatar
base  
Bob Halley committed
27
#include <isc/assertions.h>
28
#include <isc/error.h>
Bob Halley's avatar
Bob Halley committed
29
#include <isc/mem.h>
30
#include <isc/ondestroy.h>
31
#include <isc/result.h>
Bob Halley's avatar
Bob Halley committed
32

33
#ifndef ISC_SINGLETHREADED
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
Bob Halley committed
36
#else
Bob Halley's avatar
Bob Halley committed
37 38
#define LOCK(l)
#define UNLOCK(l)
Bob Halley's avatar
update  
Bob Halley committed
39 40
#endif

Bob Halley's avatar
Bob Halley committed
41
#ifndef ISC_MEM_FILL
42 43
	/*
	 * XXXMPA
Bob Halley's avatar
Bob Halley committed
44
	 * We want this on during development to catch:
45 46 47 48 49 50
	 * 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
51 52 53 54 55 56 57 58
#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

59 60 61 62 63 64 65 66 67 68 69

/*
 * 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
70 71 72 73
/*
 * Types.
 */

74 75 76 77 78
typedef struct element element;

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

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

struct stats {
Bob Halley's avatar
Bob Halley committed
91 92 93 94
	unsigned long		gets;
	unsigned long		totalgets;
	unsigned long		blocks;
	unsigned long		freefrags;
Bob Halley's avatar
base  
Bob Halley committed
95 96
};

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

100
struct isc_mem {
Bob Halley's avatar
Bob Halley committed
101
	unsigned int		magic;
102
	isc_ondestroy_t		ondestroy;
Bob Halley's avatar
Bob Halley committed
103
	isc_mutex_t		lock;
104 105 106
	isc_memalloc_t		memalloc;
	isc_memfree_t		memfree;
	void *			arg;
Bob Halley's avatar
base  
Bob Halley committed
107 108
	size_t			max_size;
	size_t			mem_target;
Bob Halley's avatar
Bob Halley committed
109 110
	element **		freelists;
	element *		basic_blocks;
111 112 113
	unsigned char **	basic_table;
	unsigned int		basic_table_count;
	unsigned int		basic_table_size;
Bob Halley's avatar
Bob Halley committed
114 115
	unsigned char *		lowest;
	unsigned char *		highest;
116
	isc_boolean_t		checkfree;
117
	isc_boolean_t		trysplit;
Bob Halley's avatar
base  
Bob Halley committed
118
	struct stats *		stats;
119
	unsigned int		references;
120
	size_t			quota;
Bob Halley's avatar
Bob Halley committed
121
	size_t			total;
122
	size_t			inuse;
Michael Graff's avatar
Michael Graff committed
123 124 125 126 127 128 129
	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
130
	/* always unlocked */
Michael Graff's avatar
Michael Graff committed
131
	unsigned int	magic;		/* magic number */
Michael Graff's avatar
Michael Graff committed
132
	isc_mutex_t    *lock;		/* optional lock */
Michael Graff's avatar
Michael Graff committed
133
	isc_mem_t      *mctx;		/* our memory context */
Michael Graff's avatar
Michael Graff committed
134 135 136
	/* 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
137 138 139 140 141 142 143 144 145
	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
146 147 148 149
	/* Debugging only. */
#if ISC_MEMPOOL_NAMES
	char		name[16];	/* printed name in stats reports */
#endif
Bob Halley's avatar
base  
Bob Halley committed
150 151
};

152 153 154
/*
 * Forward.
 */
Bob Halley's avatar
base  
Bob Halley committed
155

Michael Graff's avatar
Michael Graff committed
156
static inline size_t		quantize(size_t);
Mark Andrews's avatar
Mark Andrews committed
157 158
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
159

160 161 162
/*
 * Private Inline-able.
 */
Bob Halley's avatar
base  
Bob Halley committed
163

164
static inline size_t
Bob Halley's avatar
base  
Bob Halley committed
165
quantize(size_t size) {
166
	int temp;
Bob Halley's avatar
base  
Bob Halley committed
167 168

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

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

180 181 182
/*
 * Private.
 */
183 184 185 186 187 188 189 190 191 192

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
193
	free(ptr);
194 195
}

196 197 198
/*
 * Public.
 */
Bob Halley's avatar
base  
Bob Halley committed
199

Bob Halley's avatar
Bob Halley committed
200
isc_result_t
201 202 203
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
204
{
205
	isc_mem_t *ctx;
Bob Halley's avatar
Bob Halley committed
206 207

	REQUIRE(ctxp != NULL && *ctxp == NULL);
208 209
	REQUIRE(memalloc != NULL);
	REQUIRE(memfree != NULL);
Bob Halley's avatar
base  
Bob Halley committed
210

211
	ctx = (memalloc)(arg, sizeof *ctx);
Michael Graff's avatar
Michael Graff committed
212 213 214
	if (ctx == NULL)
		return (ISC_R_NOMEMORY);

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

Bob Halley's avatar
base  
Bob Halley committed
265
	*ctxp = ctx;
Bob Halley's avatar
Bob Halley committed
266
	return (ISC_R_SUCCESS);
Bob Halley's avatar
base  
Bob Halley committed
267 268
}

269 270 271 272 273 274 275 276 277
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));
}

278 279
static void
destroy(isc_mem_t *ctx) {
280
	unsigned int i;
281
	isc_ondestroy_t ondest;
282

Bob Halley's avatar
Bob Halley committed
283
	ctx->magic = 0;
284

Michael Graff's avatar
Michael Graff committed
285
	INSIST(ISC_LIST_EMPTY(ctx->pools));
286
	INSIST(ctx->references == 0);
Michael Graff's avatar
Michael Graff committed
287

288 289 290 291 292 293 294 295 296 297 298
	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
	
299 300

	for (i = 0; i < ctx->basic_table_count; i++)
301 302 303 304
		(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);
305

306 307
	ondest = ctx->ondestroy;

Bob Halley's avatar
Bob Halley committed
308
	(void)isc_mutex_destroy(&ctx->lock);
309
	(ctx->memfree)(ctx->arg, ctx);
Bob Halley's avatar
base  
Bob Halley committed
310

311
	isc_ondestroy_notify(&ondest, ctx);
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 368 369 370
}

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

Bob Halley's avatar
base  
Bob Halley committed
372 373 374
	*ctxp = NULL;
}

375 376 377 378 379 380 381 382 383 384 385 386
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);
}


387 388 389 390 391 392 393 394 395 396 397
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);
}

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

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

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

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

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

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

	return (ISC_TRUE);
462 463
}

Bob Halley's avatar
base  
Bob Halley committed
464
void *
Bob Halley's avatar
Bob Halley committed
465
isc__mem_get(isc_mem_t *ctx, size_t size)
Michael Graff's avatar
Michael Graff committed
466
{
Bob Halley's avatar
base  
Bob Halley committed
467 468
	void *ret;

Bob Halley's avatar
Bob Halley committed
469
	REQUIRE(VALID_CONTEXT(ctx));
Michael Graff's avatar
Michael Graff committed
470

Bob Halley's avatar
Bob Halley committed
471
	LOCK(&ctx->lock);
Mark Andrews's avatar
Mark Andrews committed
472
	ret = mem_getunlocked(ctx, size);
Michael Graff's avatar
Michael Graff committed
473 474 475 476 477
	UNLOCK(&ctx->lock);

	return (ret);
}

478 479 480 481 482 483 484 485 486 487 488 489 490
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++;
	}
}

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 609 610
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
611
static inline void *
Mark Andrews's avatar
Mark Andrews committed
612
mem_getunlocked(isc_mem_t *ctx, size_t size)
Michael Graff's avatar
Michael Graff committed
613 614 615
{
	size_t new_size = quantize(size);
	void *ret;
Bob Halley's avatar
base  
Bob Halley committed
616 617 618

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

647 648 649
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Bob Halley's avatar
base  
Bob Halley committed
650 651 652 653 654 655 656 657 658 659 660 661
	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--;
662
	ctx->inuse += new_size;
Bob Halley's avatar
base  
Bob Halley committed
663 664 665

 done:

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

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

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

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

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

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

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

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

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

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

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

void
Bob Halley's avatar
Bob Halley committed
737
isc__mem_putdebug(isc_mem_t *ctx, void *ptr, size_t size, const char *file,
Bob Halley's avatar
Bob Halley committed
738
		 int line)
Bob Halley's avatar
base  
Bob Halley committed
739 740
{
	fprintf(stderr, "%s:%d: mem_put(%p, %p, %lu)\n", file, line, 
Bob Halley's avatar
Bob Halley committed
741
		ctx, ptr, (unsigned long)size);
Bob Halley's avatar
Bob Halley committed
742
	isc__mem_put(ctx, ptr, size);
Bob Halley's avatar
base  
Bob Halley committed
743 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
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
769 770 771 772
/*
 * Print the stats[] on the stream "out" with suitable formatting.
 */
void
773
isc_mem_stats(isc_mem_t *ctx, FILE *out) {
Bob Halley's avatar
base  
Bob Halley committed
774
	size_t i;
Michael Graff's avatar
Michael Graff committed
775 776
	const struct stats *s;
	const isc_mempool_t *pool;
Bob Halley's avatar
base  
Bob Halley committed
777

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

Michael Graff's avatar
Michael Graff committed
781
	if (ctx->freelists != NULL) {
782
		for (i = 0; i <= ctx->max_size; i++) {
Michael Graff's avatar
Michael Graff committed
783 784 785 786 787 788 789 790 791 792 793 794 795 796
			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
797 798 799 800 801 802 803
	/*
	 * 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
804 805 806
	pool = ISC_LIST_HEAD(ctx->pools);
	if (pool != NULL) {
		fprintf(out, "[Pool statistics]\n");
Michael Graff's avatar
Michael Graff committed
807 808
		fprintf(out, "%15s %10s %10s %10s %10s %10s %10s %10s %1s\n",
			"name", "size", "maxalloc", "allocated", "freecount",
Michael Graff's avatar
Michael Graff committed
809
			"freemax", "fillcount", "gets", "L");
Michael Graff's avatar
Michael Graff committed
810 811
	}
	while (pool != NULL) {
Michael Graff's avatar
Michael Graff committed
812 813 814 815
		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
816
			(pool->lock == NULL ? "N" : "Y"));
Michael Graff's avatar
Michael Graff committed
817
		pool = ISC_LIST_NEXT(pool, link);
Bob Halley's avatar
base  
Bob Halley committed
818 819
	}

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

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

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

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

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

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

/*
840 841
 * 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
842 843 844
 */

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

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

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

Bob Halley's avatar
Bob Halley committed
861
	si = isc__mem_allocate(ctx, size);
862 863 864 865 866 867 868 869
	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
870
isc__mem_free(isc_mem_t *ctx, void *ptr) {
871 872 873
	size_info *si;

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

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

Bob Halley's avatar
Bob Halley committed
881
	si = &(((size_info *)ptr)[-1]);
882 883
	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
884
	isc__mem_put(ctx, si, si->u.size);
Bob Halley's avatar
base  
Bob Halley committed
885 886
}

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

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

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

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

Bob Halley's avatar
Bob Halley committed
911
	ptr = isc__mem_strdup(mctx, s);
912 913 914 915 916 917
	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);
}

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

923
	ctx->checkfree = flag;
924

925 926 927 928 929 930 931 932 933 934 935
	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);
936 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
/*
 * 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);
}

967 968 969 970 971 972 973 974 975 976 977 978 979 980
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
981 982
#ifdef ISC_MEMCLUSTER_LEGACY

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

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

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

997
isc_mem_t *
Bob Halley's avatar
base  
Bob Halley committed
998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024
mem_default_context(void) {
	/* need default_context lock here */
	if (default_context == NULL && meminit(0, 0) == -1)
		return (NULL);
	return (default_context);
}

void *
__memget(size_t size) {
	/* need default_context lock here */
	if (default_context == NULL && meminit(0, 0) == -1)
		return (NULL);
	return (__mem_get(default_context, size));
}

void
__memput(void *mem, size_t size) {
	/* need default_context lock here */
	REQUIRE(default_context != NULL);
	__mem_put(default_context, mem, size);
}

void *
__memget_debug(size_t size, const char *file, int line) {
	void *ptr;
	ptr = __memget(size);
	fprintf(stderr, "%s:%d: memget(%lu) -> %p\n", file, line,
Bob Halley's avatar
Bob Halley committed
1025
		(unsigned long)size, ptr);
Bob Halley's avatar
base  
Bob Halley committed
1026 1027 1028 1029 1030 1031
	return (ptr);
}

void
__memput_debug(void *ptr, size_t size, const char *file, int line) {
	fprintf(stderr, "%s:%d: memput(%p, %lu)\n", file, line, 
Bob Halley's avatar
Bob Halley committed
1032
		ptr, (unsigned long)size);
Bob Halley's avatar
base  
Bob Halley committed
1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048
	__memput(ptr, size);
}

int
memvalid(void *ptr) {
	/* need default_context lock here */
	REQUIRE(default_context != NULL);
	return (mem_valid(default_context, ptr));
}

void
memstats(FILE *out) {
	/* need default_context lock here */
	REQUIRE(default_context != NULL);
	mem_stats(default_context, out);
}
Bob Halley's avatar
Bob Halley committed
1049 1050

#endif /* ISC_MEMCLUSTER_LEGACY */
Michael Graff's avatar
Michael Graff committed
1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078


/*
 * Memory pool stuff
 */


#if 0
/*
 * Free all but "n" items from the pool's free list.  If n == 0, all items
 * will be returned to the mctx.
 */
static void
mempool_release(isc_mempool_t *mpctx, unsigned int n)
{
	isc_mem_t *mctx;
	element *item;
	element *next;
	unsigned int count;

	mctx = mpctx->mctx;

	if (mpctx->freecount <= n)
		return;

	INSIST(mpctx->items != NULL);
	item = mpctx->items;
	for (count = 0 ; count < n ; count++) {
Michael Graff's avatar
Michael Graff committed
1079
		item = item->next;
Michael Graff's avatar
Michael Graff committed
1080 1081 1082 1083 1084 1085 1086 1087 1088
		INSIST(item != NULL);
	}

	/*
	 * All remaining items are to be freed.  Lock the context once,
	 * free them all, and unlock the context.
	 */
	LOCK(&mctx->lock);
	do {
Michael Graff's avatar
Michael Graff committed
1089
		next = item->next;
Michael Graff's avatar
Michael Graff committed
1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100
		mem_putunlocked(mctx, item, mpctx->size);
		INSIST(mpctx->freecount > 0);
		mpctx->freecount--;
		item = next;
	} while (item != NULL);
	UNLOCK(&mctx->lock);
}
#endif

/*
 * Release all items on the free list.  No locking is done, the memory
Michael Graff's avatar
Michael Graff committed
1101
 * context must be locked, and the pool if needed.
Michael Graff's avatar
Michael Graff committed
1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118