mem.c 57.8 KB
Newer Older
Bob Halley's avatar
base  
Bob Halley committed
1
/*
Automatic Updater's avatar
Automatic Updater committed
2
 * Copyright (C) 2004-2009  Internet Systems Consortium, Inc. ("ISC")
Mark Andrews's avatar
Mark Andrews committed
3
 * Copyright (C) 1997-2003  Internet Software Consortium.
4
 *
Automatic Updater's avatar
Automatic Updater committed
5
 * Permission to use, copy, modify, and/or distribute this software for any
Bob Halley's avatar
base  
Bob Halley committed
6 7
 * 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
/* $Id: mem.c,v 1.152 2009/09/02 04:25:19 jinmei Exp $ */
19 20

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

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

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

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

30
#include <isc/magic.h>
Bob Halley's avatar
Bob Halley committed
31
#include <isc/mem.h>
32
#include <isc/msgs.h>
33
#include <isc/once.h>
34
#include <isc/ondestroy.h>
35
#include <isc/string.h>
Bob Halley's avatar
update  
Bob Halley committed
36
#include <isc/mutex.h>
37
#include <isc/print.h>
Michael Graff's avatar
Michael Graff committed
38
#include <isc/util.h>
39
#include <isc/xml.h>
Bob Halley's avatar
update  
Bob Halley committed
40

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

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

/*
 * Constants.
 */

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

Bob Halley's avatar
base  
Bob Halley committed
60 61 62
/*
 * Types.
 */
63 64 65
typedef struct isc__mem isc__mem_t;
typedef struct isc__mempool isc__mempool_t;

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

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

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

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

struct stats {
Bob Halley's avatar
Bob Halley committed
101 102 103 104
	unsigned long		gets;
	unsigned long		totalgets;
	unsigned long		blocks;
	unsigned long		freefrags;
Bob Halley's avatar
base  
Bob Halley committed
105 106
};

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

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

114 115
/* List of all active memory contexts. */

116
static ISC_LIST(isc__mem_t)	contexts;
117
static isc_once_t		once = ISC_ONCE_INIT;
118
static isc_mutex_t		lock;
119

120 121 122 123 124 125
/*%
 * Total size of lost memory due to a bug of external library.
 * Locked by the global lock.
 */
static isc_uint64_t		totallost;

126 127
struct isc__mem {
	isc_mem_t		common;
128
	isc_ondestroy_t		ondestroy;
129
	unsigned int		flags;
130
	isc_mutex_t		lock;
131 132 133
	isc_memalloc_t		memalloc;
	isc_memfree_t		memfree;
	void *			arg;
Bob Halley's avatar
base  
Bob Halley committed
134
	size_t			max_size;
135
	isc_boolean_t		checkfree;
Bob Halley's avatar
base  
Bob Halley committed
136
	struct stats *		stats;
137
	unsigned int		references;
138 139
	char			name[16];
	void *			tag;
140
	size_t			quota;
Bob Halley's avatar
Bob Halley committed
141
	size_t			total;
142
	size_t			inuse;
143
	size_t			maxinuse;
144 145 146 147 148
	size_t			hi_water;
	size_t			lo_water;
	isc_boolean_t		hi_called;
	isc_mem_water_t		water;
	void *			water_arg;
149
	ISC_LIST(isc__mempool_t) pools;
150
	unsigned int		poolcnt;
151

152
	/*  ISC_MEMFLAG_INTERNAL */
153 154 155 156 157 158 159 160 161
	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;

162
#if ISC_MEM_TRACKLINES
163
	debuglist_t *	 	debuglist;
164
	unsigned int		debuglistcnt;
Michael Graff's avatar
Michael Graff committed
165
#endif
166 167

	unsigned int		memalloc_failures;
168
	ISC_LINK(isc__mem_t)	link;
Michael Graff's avatar
Michael Graff committed
169 170
};

171 172
#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
173

174
struct isc__mempool {
Michael Graff's avatar
Michael Graff committed
175
	/* always unlocked */
176
	isc_mempool_t	common;		/*%< common header of mempool's */
177
	isc_mutex_t    *lock;		/*%< optional lock */
178
	isc__mem_t      *mctx;		/*%< our memory context */
179
	/*%< locked via the memory context's lock */
180
	ISC_LINK(isc__mempool_t)	link;	/*%< next pool in this mem context */
181 182 183 184 185 186 187 188 189 190 191
	/*%< 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. */
192
#if ISC_MEMPOOL_NAMES
193
	char		name[16];	/*%< printed name in stats reports */
Michael Graff's avatar
Michael Graff committed
194
#endif
Bob Halley's avatar
base  
Bob Halley committed
195 196
};

197 198 199
/*
 * Private Inline-able.
 */
Bob Halley's avatar
base  
Bob Halley committed
200

201
#if ! ISC_MEM_TRACKLINES
Michael Graff's avatar
Michael Graff committed
202 203 204
#define ADD_TRACE(a, b, c, d, e)
#define DELETE_TRACE(a, b, c, d, e)
#else
205
#define ADD_TRACE(a, b, c, d, e) \
206 207 208 209
	do { \
		if ((isc_mem_debugging & (ISC_MEM_DEBUGTRACE | \
					  ISC_MEM_DEBUGRECORD)) != 0 && \
		     b != NULL) \
Automatic Updater's avatar
Automatic Updater committed
210
			 add_trace_entry(a, b, c, d, e); \
211
	} while (0)
Michael Graff's avatar
Michael Graff committed
212 213
#define DELETE_TRACE(a, b, c, d, e)	delete_trace_entry(a, b, c, d, e)

214
static void
215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325
print_active(isc__mem_t *ctx, FILE *out);

/*%
 * The following can be either static or public, depending on build environment.
 */

#ifdef BIND9
#define ISC_MEMFUNC_SCOPE
#else
#define ISC_MEMFUNC_SCOPE static
#endif

ISC_MEMFUNC_SCOPE 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_MEMFUNC_SCOPE isc_result_t
isc__mem_createx2(size_t init_max_size, size_t target_size,
		  isc_memalloc_t memalloc, isc_memfree_t memfree, void *arg,
		  isc_mem_t **ctxp, unsigned int flags);
ISC_MEMFUNC_SCOPE isc_result_t
isc__mem_create(size_t init_max_size, size_t target_size, isc_mem_t **ctxp);
ISC_MEMFUNC_SCOPE isc_result_t
isc__mem_create2(size_t init_max_size, size_t target_size,
		 isc_mem_t **ctxp, unsigned int flags);
ISC_MEMFUNC_SCOPE void
isc__mem_attach(isc_mem_t *source, isc_mem_t **targetp);
ISC_MEMFUNC_SCOPE void
isc__mem_detach(isc_mem_t **ctxp);
ISC_MEMFUNC_SCOPE void
isc___mem_putanddetach(isc_mem_t **ctxp, void *ptr, size_t size FLARG);
ISC_MEMFUNC_SCOPE void
isc__mem_destroy(isc_mem_t **ctxp);
ISC_MEMFUNC_SCOPE isc_result_t
isc__mem_ondestroy(isc_mem_t *ctx, isc_task_t *task, isc_event_t **event);
ISC_MEMFUNC_SCOPE void *
isc___mem_get(isc_mem_t *ctx, size_t size FLARG);
ISC_MEMFUNC_SCOPE void
isc___mem_put(isc_mem_t *ctx, void *ptr, size_t size FLARG);
ISC_MEMFUNC_SCOPE void
isc__mem_stats(isc_mem_t *ctx, FILE *out);
ISC_MEMFUNC_SCOPE void *
isc___mem_allocate(isc_mem_t *ctx, size_t size FLARG);
ISC_MEMFUNC_SCOPE void
isc___mem_free(isc_mem_t *ctx, void *ptr FLARG);
ISC_MEMFUNC_SCOPE char *
isc___mem_strdup(isc_mem_t *mctx, const char *s FLARG);
ISC_MEMFUNC_SCOPE void
isc__mem_setdestroycheck(isc_mem_t *ctx, isc_boolean_t flag);
ISC_MEMFUNC_SCOPE void
isc__mem_setquota(isc_mem_t *ctx, size_t quota);
ISC_MEMFUNC_SCOPE size_t
isc__mem_getquota(isc_mem_t *ctx);
ISC_MEMFUNC_SCOPE size_t
isc__mem_inuse(isc_mem_t *ctx);
ISC_MEMFUNC_SCOPE void
isc__mem_setwater(isc_mem_t *ctx, isc_mem_water_t water, void *water_arg,
		  size_t hiwater, size_t lowater);
ISC_MEMFUNC_SCOPE void
isc__mem_waterack(isc_mem_t *ctx0, int flag);
ISC_MEMFUNC_SCOPE void
isc__mem_setname(isc_mem_t *ctx, const char *name, void *tag);
ISC_MEMFUNC_SCOPE const char *
isc__mem_getname(isc_mem_t *ctx);
ISC_MEMFUNC_SCOPE void *
isc__mem_gettag(isc_mem_t *ctx);
ISC_MEMFUNC_SCOPE isc_result_t
isc__mempool_create(isc_mem_t *mctx, size_t size, isc_mempool_t **mpctxp);
ISC_MEMFUNC_SCOPE void
isc__mempool_setname(isc_mempool_t *mpctx, const char *name);
ISC_MEMFUNC_SCOPE void
isc__mempool_destroy(isc_mempool_t **mpctxp);
ISC_MEMFUNC_SCOPE void
isc__mempool_associatelock(isc_mempool_t *mpctx, isc_mutex_t *lock);
ISC_MEMFUNC_SCOPE void *
isc___mempool_get(isc_mempool_t *mpctx FLARG);
ISC_MEMFUNC_SCOPE void
isc___mempool_put(isc_mempool_t *mpctx, void *mem FLARG);
ISC_MEMFUNC_SCOPE void
isc__mempool_setfreemax(isc_mempool_t *mpctx, unsigned int limit);
ISC_MEMFUNC_SCOPE unsigned int
isc__mempool_getfreemax(isc_mempool_t *mpctx);
ISC_MEMFUNC_SCOPE unsigned int
isc__mempool_getfreecount(isc_mempool_t *mpctx);
ISC_MEMFUNC_SCOPE void
isc__mempool_setmaxalloc(isc_mempool_t *mpctx, unsigned int limit);
ISC_MEMFUNC_SCOPE unsigned int
isc__mempool_getmaxalloc(isc_mempool_t *mpctx);
ISC_MEMFUNC_SCOPE unsigned int
isc__mempool_getallocated(isc_mempool_t *mpctx);
ISC_MEMFUNC_SCOPE void
isc__mempool_setfillcount(isc_mempool_t *mpctx, unsigned int limit);
ISC_MEMFUNC_SCOPE unsigned int
isc__mempool_getfillcount(isc_mempool_t *mpctx);
#ifdef BIND9
ISC_MEMFUNC_SCOPE void
isc__mem_printactive(isc_mem_t *ctx0, FILE *file);
ISC_MEMFUNC_SCOPE void
isc__mem_printallactive(FILE *file);
ISC_MEMFUNC_SCOPE void
isc__mem_checkdestroyed(FILE *file);
ISC_MEMFUNC_SCOPE unsigned int
isc__mem_references(isc_mem_t *ctx0);
#endif

static struct isc__memmethods {
	isc_memmethods_t methods;

	/*%
	 * The following are defined just for avoiding unused static functions.
	 */
326
#ifndef BIND9
327 328
	void *createx, *create, *create2, *ondestroy, *stats,
		*setquota, *getquota, *setname, *getname, *gettag;
329
#endif
330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345
} memmethods = {
	{
		isc__mem_attach,
		isc__mem_detach,
		isc__mem_destroy,
		isc___mem_get,
		isc___mem_put,
		isc___mem_putanddetach,
		isc___mem_allocate,
		isc___mem_strdup,
		isc___mem_free,
		isc__mem_setdestroycheck,
		isc__mem_setwater,
		isc__mem_waterack,
		isc__mem_inuse,
		isc__mempool_create
346 347 348 349 350 351 352 353 354
	}
#ifndef BIND9
	,
	(void *)isc__mem_createx, (void *)isc__mem_create,
	(void *)isc__mem_create2, (void *)isc__mem_ondestroy,
	(void *)isc__mem_stats, (void *)isc__mem_setquota,
	(void *)isc__mem_getquota, (void *)isc__mem_setname,
	(void *)isc__mem_getname, (void *)isc__mem_gettag
#endif
355 356 357 358 359 360 361 362
};

static struct isc__mempoolmethods {
	isc_mempoolmethods_t methods;

	/*%
	 * The following are defined just for avoiding unused static functions.
	 */
363
#ifndef BIND9
364
	void *getfreemax, *getfreecount, *getmaxalloc, *getfillcount;
365
#endif
366 367 368 369 370 371 372 373 374 375 376
} mempoolmethods = {
	{
		isc__mempool_destroy,
		isc___mempool_get,
		isc___mempool_put,
		isc__mempool_getallocated,
		isc__mempool_setmaxalloc,
		isc__mempool_setfreemax,
		isc__mempool_setname,
		isc__mempool_associatelock,
		isc__mempool_setfillcount
377 378 379 380 381 382
	}
#ifndef BIND9
	,
	(void *)isc__mempool_getfreemax, (void *)isc__mempool_getfreecount,
	(void *)isc__mempool_getmaxalloc, (void *)isc__mempool_getfillcount
#endif
383
};
384

385
/*!
Michael Graff's avatar
Michael Graff committed
386 387 388
 * mctx must be locked.
 */
static inline void
389
add_trace_entry(isc__mem_t *mctx, const void *ptr, unsigned int size
Michael Graff's avatar
pasto  
Michael Graff committed
390
		FLARG)
Michael Graff's avatar
Michael Graff committed
391 392 393 394
{
	debuglink_t *dl;
	unsigned int i;

395
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
396 397 398 399
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_ADDTRACE,
					       "add %p size %u "
					       "file %s line %u mctx %p\n"),
400
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
401

402
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
403 404
		return;

405 406 407 408
	if (size > mctx->max_size)
		size = mctx->max_size;

	dl = ISC_LIST_HEAD(mctx->debuglist[size]);
Michael Graff's avatar
Michael Graff committed
409 410 411
	while (dl != NULL) {
		if (dl->count == DEBUGLIST_COUNT)
			goto next;
412
		for (i = 0; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
413 414
			if (dl->ptr[i] == NULL) {
				dl->ptr[i] = ptr;
415
				dl->size[i] = size;
Michael Graff's avatar
Michael Graff committed
416 417 418 419 420 421 422 423 424 425 426 427 428 429
				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);
430
	for (i = 1; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
431
		dl->ptr[i] = NULL;
432
		dl->size[i] = 0;
Michael Graff's avatar
Michael Graff committed
433 434 435 436 437
		dl->file[i] = NULL;
		dl->line[i] = 0;
	}

	dl->ptr[0] = ptr;
438
	dl->size[0] = size;
Michael Graff's avatar
Michael Graff committed
439 440 441 442
	dl->file[0] = file;
	dl->line[0] = line;
	dl->count = 1;

443
	ISC_LIST_PREPEND(mctx->debuglist[size], dl, link);
444
	mctx->debuglistcnt++;
Michael Graff's avatar
Michael Graff committed
445 446 447
}

static inline void
448
delete_trace_entry(isc__mem_t *mctx, const void *ptr, unsigned int size,
Michael Graff's avatar
Michael Graff committed
449 450 451 452 453
		   const char *file, unsigned int line)
{
	debuglink_t *dl;
	unsigned int i;

454
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
455 456 457 458
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_DELTRACE,
					       "del %p size %u "
					       "file %s line %u mctx %p\n"),
459
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
460

461
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
462 463
		return;

464 465 466 467
	if (size > mctx->max_size)
		size = mctx->max_size;

	dl = ISC_LIST_HEAD(mctx->debuglist[size]);
Michael Graff's avatar
Michael Graff committed
468
	while (dl != NULL) {
469
		for (i = 0; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
470 471
			if (dl->ptr[i] == ptr) {
				dl->ptr[i] = NULL;
472
				dl->size[i] = 0;
Michael Graff's avatar
Michael Graff committed
473 474 475 476 477 478
				dl->file[i] = NULL;
				dl->line[i] = 0;

				INSIST(dl->count > 0);
				dl->count--;
				if (dl->count == 0) {
479
					ISC_LIST_UNLINK(mctx->debuglist[size],
Michael Graff's avatar
Michael Graff committed
480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496
							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 */

497 498 499
static inline size_t
rmsize(size_t size) {
	/*
Automatic Updater's avatar
Automatic Updater committed
500
	 * round down to ALIGNMENT_SIZE
501
	 */
502
	return (size & (~(ALIGNMENT_SIZE - 1)));
503 504
}

505
static inline size_t
Bob Halley's avatar
base  
Bob Halley committed
506
quantize(size_t size) {
507
	/*!
508
	 * Round up the result in order to get a size big
Bob Halley's avatar
base  
Bob Halley committed
509 510 511
	 * enough to satisfy the request and be aligned on ALIGNMENT_SIZE
	 * byte boundaries.
	 */
512

Mark Andrews's avatar
Mark Andrews committed
513
	if (size == 0U)
514
		return (ALIGNMENT_SIZE);
515
	return ((size + ALIGNMENT_SIZE - 1) & (~(ALIGNMENT_SIZE - 1)));
Bob Halley's avatar
base  
Bob Halley committed
516 517
}

518
static inline isc_boolean_t
519
more_basic_blocks(isc__mem_t *ctx) {
520 521 522 523 524
	void *new;
	unsigned char *curr, *next;
	unsigned char *first, *last;
	unsigned char **table;
	unsigned int table_size;
Bob Halley's avatar
Bob Halley committed
525
	size_t increment;
526 527 528 529
	int i;

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

530 531 532
	/*
	 * Did we hit the quota for this context?
	 */
Bob Halley's avatar
Bob Halley committed
533
	increment = NUM_BASIC_BLOCKS * ctx->mem_target;
Mark Andrews's avatar
Mark Andrews committed
534
	if (ctx->quota != 0U && ctx->total + increment > ctx->quota)
535
		return (ISC_FALSE);
536 537 538

	INSIST(ctx->basic_table_count <= ctx->basic_table_size);
	if (ctx->basic_table_count == ctx->basic_table_size) {
539
		table_size = ctx->basic_table_size + TABLE_INCREMENT;
540
		table = (ctx->memalloc)(ctx->arg,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
541
					table_size * sizeof(unsigned char *));
542 543
		if (table == NULL) {
			ctx->memalloc_failures++;
544
			return (ISC_FALSE);
545
		}
546 547 548
		if (ctx->basic_table_size != 0) {
			memcpy(table, ctx->basic_table,
			       ctx->basic_table_size *
Andreas Gustafsson's avatar
Andreas Gustafsson committed
549
			       sizeof(unsigned char *));
550
			(ctx->memfree)(ctx->arg, ctx->basic_table);
551
		}
552 553
		ctx->basic_table = table;
		ctx->basic_table_size = table_size;
554
	}
555

556
	new = (ctx->memalloc)(ctx->arg, NUM_BASIC_BLOCKS * ctx->mem_target);
557 558
	if (new == NULL) {
		ctx->memalloc_failures++;
559
		return (ISC_FALSE);
560
	}
Bob Halley's avatar
Bob Halley committed
561
	ctx->total += increment;
562 563
	ctx->basic_table[ctx->basic_table_count] = new;
	ctx->basic_table_count++;
564

565 566 567
	curr = new;
	next = curr + ctx->mem_target;
	for (i = 0; i < (NUM_BASIC_BLOCKS - 1); i++) {
568
		((element *)curr)->next = (element *)next;
569 570 571 572 573 574 575
		curr = next;
		next += ctx->mem_target;
	}
	/*
	 * curr is now pointing at the last block in the
	 * array.
	 */
Bob Halley's avatar
Bob Halley committed
576
	((element *)curr)->next = NULL;
577 578 579 580 581 582 583
	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;
584 585

	return (ISC_TRUE);
586 587
}

588
static inline isc_boolean_t
589
more_frags(isc__mem_t *ctx, size_t new_size) {
590 591 592 593 594
	int i, frags;
	size_t total_size;
	void *new;
	unsigned char *curr, *next;

595
	/*!
596 597 598 599 600 601 602 603 604 605
	 * 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.
			 */
			/*
606
			 * XXXRTH  "At quota" notification here.
607
			 */
608
			return (ISC_FALSE);
609 610 611 612 613 614 615 616 617 618 619 620 621 622 623
		}
	}

	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;
624
	total_size -= new_size;
625 626 627 628
	for (i = 0; i < (frags - 1); i++) {
		((element *)curr)->next = (element *)next;
		curr = next;
		next += new_size;
629 630 631 632 633 634
		total_size -= new_size;
	}
	/*
	 * Add the remaining fragment of the basic block to a free list.
	 */
	total_size = rmsize(total_size);
Mark Andrews's avatar
Mark Andrews committed
635
	if (total_size > 0U) {
636 637 638
		((element *)next)->next = ctx->freelists[total_size];
		ctx->freelists[total_size] = (element *)next;
		ctx->stats[total_size].freefrags++;
639 640 641 642 643 644 645 646 647 648 649
	}
	/*
	 * 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
650
static inline void *
651
mem_getunlocked(isc__mem_t *ctx, size_t size) {
Michael Graff's avatar
Michael Graff committed
652 653
	size_t new_size = quantize(size);
	void *ret;
Bob Halley's avatar
base  
Bob Halley committed
654 655

	if (size >= ctx->max_size || new_size >= ctx->max_size) {
656 657 658
		/*
		 * memget() was called on something beyond our upper limit.
		 */
Mark Andrews's avatar
Mark Andrews committed
659
		if (ctx->quota != 0U && ctx->total + size > ctx->quota) {
Bob Halley's avatar
Bob Halley committed
660 661 662
			ret = NULL;
			goto done;
		}
Mark Andrews's avatar
Mark Andrews committed
663
		ret = (ctx->memalloc)(ctx->arg, size);
664 665 666
		if (ret == NULL) {
			ctx->memalloc_failures++;
			goto done;
Bob Halley's avatar
base  
Bob Halley committed
667
		}
668 669 670 671 672 673 674 675 676 677
		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;
678
		goto done;
Bob Halley's avatar
base  
Bob Halley committed
679 680
	}

681
	/*
Bob Halley's avatar
base  
Bob Halley committed
682 683 684 685
	 * 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.
	 */
686 687
	if (ctx->freelists[new_size] == NULL && !more_frags(ctx, new_size))
		return (NULL);
Bob Halley's avatar
base  
Bob Halley committed
688

689 690 691
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Bob Halley's avatar
base  
Bob Halley committed
692 693 694
	ret = ctx->freelists[new_size];
	ctx->freelists[new_size] = ctx->freelists[new_size]->next;

695
	/*
Bob Halley's avatar
base  
Bob Halley committed
696 697 698 699 700 701 702 703
	 * 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--;
704
	ctx->inuse += new_size;
Bob Halley's avatar
base  
Bob Halley committed
705 706 707

 done:

708
#if ISC_MEM_FILL
709 710
	if (ret != NULL)
		memset(ret, 0xbe, new_size); /* Mnemonic for "beef". */
David Lawrence's avatar
David Lawrence committed
711 712 713
#endif

	return (ret);
Michael Graff's avatar
Michael Graff committed
714 715
}

716 717 718 719 720 721 722 723 724 725 726 727 728 729 730
#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
731
static inline void
732
mem_putunlocked(isc__mem_t *ctx, void *mem, size_t size) {
Michael Graff's avatar
Michael Graff committed
733
	size_t new_size = quantize(size);
Bob Halley's avatar
base  
Bob Halley committed
734

735
	if (size == ctx->max_size || new_size >= ctx->max_size) {
736 737 738
		/*
		 * memput() called on something beyond our upper limit.
		 */
739
#if ISC_MEM_FILL
Mark Andrews's avatar
Mark Andrews committed
740 741
		memset(mem, 0xde, size); /* Mnemonic for "dead". */
#endif
742
		(ctx->memfree)(ctx->arg, mem);
Mark Andrews's avatar
Mark Andrews committed
743
		INSIST(ctx->stats[ctx->max_size].gets != 0U);
Bob Halley's avatar
base  
Bob Halley committed
744
		ctx->stats[ctx->max_size].gets--;
Bob Halley's avatar
Bob Halley committed
745
		INSIST(size <= ctx->total);
746
		ctx->inuse -= size;
Bob Halley's avatar
Bob Halley committed
747
		ctx->total -= size;
Michael Graff's avatar
Michael Graff committed
748
		return;
Bob Halley's avatar
base  
Bob Halley committed
749 750
	}

751 752
#if ISC_MEM_FILL
#if ISC_MEM_CHECKOVERRUN
753 754
	check_overrun(mem, size, new_size);
#endif
Mark Andrews's avatar
Mark Andrews committed
755 756
	memset(mem, 0xde, new_size); /* Mnemonic for "dead". */
#endif
757

758 759 760
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Mark Andrews's avatar
Mark Andrews committed
761 762
	((element *)mem)->next = ctx->freelists[new_size];
	ctx->freelists[new_size] = (element *)mem;
Bob Halley's avatar
base  
Bob Halley committed
763

764
	/*
Bob Halley's avatar
base  
Bob Halley committed
765 766 767 768 769
	 * The stats[] uses the _actual_ "size" requested by the
	 * caller, with the caveat (in the code above) that "size" >= the
	 * max. size (max_size) ends up getting recorded as a call to
	 * max_size.
	 */
Mark Andrews's avatar
Mark Andrews committed
770
	INSIST(ctx->stats[size].gets != 0U);
Bob Halley's avatar
base  
Bob Halley committed
771 772
	ctx->stats[size].gets--;
	ctx->stats[new_size].freefrags++;
773
	ctx->inuse -= new_size;
Bob Halley's avatar
base  
Bob Halley committed
774 775
}

776
/*!
777 778 779
 * Perform a malloc, doing memory filling and overrun detection as necessary.
 */
static inline void *
780
mem_get(isc__mem_t *ctx, size_t size) {
781 782 783 784 785 786 787
	char *ret;

#if ISC_MEM_CHECKOVERRUN
	size += 1;
#endif

	ret = (ctx->memalloc)(ctx->arg, size);
788
	if (ret == NULL)
Automatic Updater's avatar
Automatic Updater committed
789
		ctx->memalloc_failures++;
790 791 792 793 794 795 796 797 798 799 800 801 802 803

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

804
/*!
805 806 807
 * Perform a free, doing memory filling and overrun detection as necessary.
 */
static inline void
808
mem_put(isc__mem_t *ctx, void *mem, size_t size) {
809
#if ISC_MEM_CHECKOVERRUN
810
	INSIST(((unsigned char *)mem)[size] == 0xbe);
811 812 813
#endif
#if ISC_MEM_FILL
	memset(mem, 0xde, size); /* Mnemonic for "dead". */
Andreas Gustafsson's avatar
Andreas Gustafsson committed
814 815
#else
	UNUSED(size);
816 817 818 819
#endif
	(ctx->memfree)(ctx->arg, mem);
}

820
/*!
821 822 823
 * Update internal counters after a memory get.
 */
static inline void
824
mem_getstats(isc__mem_t *ctx, size_t size) {
825 826 827 828 829 830 831 832 833 834 835 836
	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++;
	}
}

837
/*!
838 839 840
 * Update internal counters after a memory put.
 */
static inline void
841
mem_putstats(isc__mem_t *ctx, void *ptr, size_t size) {
842 843 844 845 846 847
	UNUSED(ptr);

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

	if (size > ctx->max_size) {
848
		INSIST(ctx->stats[ctx->max_size].gets > 0U);
849 850
		ctx->stats[ctx->max_size].gets--;
	} else {
851
		INSIST(ctx->stats[size].gets > 0U);
852 853 854 855
		ctx->stats[size].gets--;
	}
}

David Lawrence's avatar
David Lawrence committed
856 857 858 859 860 861 862
/*
 * Private.
 */

static void *
default_memalloc(void *arg, size_t size) {
	UNUSED(arg);
863
	if (size == 0U)
864
		size = 1;
David Lawrence's avatar
David Lawrence committed
865 866 867 868 869 870 871 872 873
	return (malloc(size));
}

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

874 875
static void
initialize_action(void) {
876
	RUNTIME_CHECK(isc_mutex_init(&lock) == ISC_R_SUCCESS);
Mark Andrews's avatar
Mark Andrews committed
877
	ISC_LIST_INIT(contexts);
878
	totallost = 0;
879 880
}

David Lawrence's avatar
David Lawrence committed
881 882 883 884
/*
 * Public.
 */

885 886 887 888
ISC_MEMFUNC_SCOPE 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)
889
{
890 891
	return (isc__mem_createx2(init_max_size, target_size, memalloc, memfree,
				  arg, ctxp, ISC_MEMFLAG_DEFAULT));
Automatic Updater's avatar
Automatic Updater committed
892

893 894
}

895 896 897 898
ISC_MEMFUNC_SCOPE isc_result_t
isc__mem_createx2(size_t init_max_size, size_t target_size,
		  isc_memalloc_t memalloc, isc_memfree_t memfree, void *arg,
		  isc_mem_t **ctxp, unsigned int flags)
David Lawrence's avatar
David Lawrence committed
899
{
900
	isc__mem_t *ctx;
901
	isc_result_t result;
David Lawrence's avatar
David Lawrence committed
902 903 904 905 906

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

907 908
	INSIST((ALIGNMENT_SIZE & (ALIGNMENT_SIZE - 1)) == 0);

909 910
	RUNTIME_CHECK(isc_once_do(&once, initialize_action) == ISC_R_SUCCESS);

Andreas Gustafsson's avatar
Andreas Gustafsson committed
911
	ctx = (memalloc)(arg, sizeof(*ctx));
David Lawrence's avatar
David Lawrence committed
912 913 914
	if (ctx == NULL)
		return (ISC_R_NOMEMORY);

915
	if ((flags & ISC_MEMFLAG_NOLOCK) == 0) {
916
		result = isc_mutex_init(&ctx->lock);
917 918 919 920
		if (result != ISC_R_SUCCESS) {
			(memfree)(arg, ctx);
			return (result);
		}
921 922
	}

923
	if (init_max_size == 0U)
David Lawrence's avatar
David Lawrence committed
924 925 926
		ctx->max_size = DEF_MAX_SIZE;
	else
		ctx->max_size = init_max_size;
927
	ctx->flags = flags;
928
	ctx->references = 1;
929 930
	memset(ctx->name, 0, sizeof(ctx->name));
	ctx->tag = NULL;
931 932 933
	ctx->quota = 0;
	ctx->total = 0;
	ctx->inuse = 0;
934
	ctx->maxinuse = 0;
935 936 937 938 939
	ctx->hi_water = 0;
	ctx->lo_water = 0;
	ctx->hi_called = ISC_FALSE;
	ctx->water = NULL;
	ctx->water_arg = NULL;
940 941 942
	ctx->common.impmagic = MEM_MAGIC;
	ctx->common.magic = ISCAPI_MCTX_MAGIC;
	ctx->common.methods = (isc_memmethods_t *)&memmethods;
943 944 945 946 947
	isc_ondestroy_init(&ctx->ondestroy);
	ctx->memalloc = memalloc;
	ctx->memfree = memfree;
	ctx->arg = arg;
	ctx->stats = NULL;
948
	ctx->checkfree = ISC_TRUE;
949
#if ISC_MEM_TRACKLINES
950
	ctx->debuglist = NULL;
951
	ctx->debuglistcnt = 0;
952
#endif
953
	ISC_LIST_INIT(ctx->pools);
954
	ctx->poolcnt = 0;
955
	ctx->freelists = NULL;
956 957 958 959 960 961
	ctx->basic_blocks = NULL;
	ctx->basic_table = NULL;
	ctx->basic_table_count = 0;
	ctx->basic_table_size = 0;
	ctx->lowest = NULL;
	ctx->highest = NULL;
962 963

	ctx->stats = (memalloc)(arg,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
964
				(ctx->max_size+1) * sizeof(struct stats));