mem.c 58.9 KB
Newer Older
Bob Halley's avatar
base  
Bob Halley committed
1
/*
Tinderbox User's avatar
Tinderbox User committed
2
 * Copyright (C) 2004-2010, 2012  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
 */

Mark Andrews's avatar
Mark Andrews committed
18
/* $Id$ */
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
#define FLARG_PASS	, file, line
78
#define FLARG		, const char *file, unsigned int line
Michael Graff's avatar
Michael Graff committed
79 80 81 82
#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
	size_t			hi_water;
	size_t			lo_water;
	isc_boolean_t		hi_called;
147
	isc_boolean_t		is_overmem;
148 149
	isc_mem_water_t		water;
	void *			water_arg;
150
	ISC_LIST(isc__mempool_t) pools;
151
	unsigned int		poolcnt;
152

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

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

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

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

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

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

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

215
static void
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
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);
259 260
ISC_MEMFUNC_SCOPE void *
isc___mem_reallocate(isc_mem_t *ctx, void *ptr, size_t size FLARG);
261 262 263 264 265 266 267 268 269 270 271 272
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);
273 274
ISC_MEMFUNC_SCOPE isc_boolean_t
isc__mem_isovermem(isc_mem_t *ctx);
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 326 327 328 329 330
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.
	 */
331
#ifndef BIND9
332 333
	void *createx, *create, *create2, *ondestroy, *stats,
		*setquota, *getquota, *setname, *getname, *gettag;
334
#endif
335 336 337 338 339 340 341 342 343
} memmethods = {
	{
		isc__mem_attach,
		isc__mem_detach,
		isc__mem_destroy,
		isc___mem_get,
		isc___mem_put,
		isc___mem_putanddetach,
		isc___mem_allocate,
344
		isc___mem_reallocate,
345 346 347 348 349 350
		isc___mem_strdup,
		isc___mem_free,
		isc__mem_setdestroycheck,
		isc__mem_setwater,
		isc__mem_waterack,
		isc__mem_inuse,
351
		isc__mem_isovermem,
352
		isc__mempool_create
353 354 355 356 357 358 359 360 361
	}
#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
362 363 364 365 366 367 368 369
};

static struct isc__mempoolmethods {
	isc_mempoolmethods_t methods;

	/*%
	 * The following are defined just for avoiding unused static functions.
	 */
370
#ifndef BIND9
371
	void *getfreemax, *getfreecount, *getmaxalloc, *getfillcount;
372
#endif
373 374 375 376 377 378 379 380 381 382 383
} 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
384 385 386 387 388 389
	}
#ifndef BIND9
	,
	(void *)isc__mempool_getfreemax, (void *)isc__mempool_getfreecount,
	(void *)isc__mempool_getmaxalloc, (void *)isc__mempool_getfillcount
#endif
390
};
391

392
/*!
Michael Graff's avatar
Michael Graff committed
393 394 395
 * mctx must be locked.
 */
static inline void
396
add_trace_entry(isc__mem_t *mctx, const void *ptr, unsigned int size
Michael Graff's avatar
pasto  
Michael Graff committed
397
		FLARG)
Michael Graff's avatar
Michael Graff committed
398 399 400
{
	debuglink_t *dl;
	unsigned int i;
401
	unsigned int mysize = size;
Michael Graff's avatar
Michael Graff committed
402

403
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
404 405 406 407
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_ADDTRACE,
					       "add %p size %u "
					       "file %s line %u mctx %p\n"),
408
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
409

410
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
411 412
		return;

413 414
	if (mysize > mctx->max_size)
		mysize = mctx->max_size;
415

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

	dl->ptr[0] = ptr;
446
	dl->size[0] = size;
Michael Graff's avatar
Michael Graff committed
447 448 449 450
	dl->file[0] = file;
	dl->line[0] = line;
	dl->count = 1;

451
	ISC_LIST_PREPEND(mctx->debuglist[mysize], dl, link);
452
	mctx->debuglistcnt++;
Michael Graff's avatar
Michael Graff committed
453 454 455
}

static inline void
456
delete_trace_entry(isc__mem_t *mctx, const void *ptr, unsigned int size,
Michael Graff's avatar
Michael Graff committed
457 458 459 460 461
		   const char *file, unsigned int line)
{
	debuglink_t *dl;
	unsigned int i;

462
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
463 464 465 466
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_DELTRACE,
					       "del %p size %u "
					       "file %s line %u mctx %p\n"),
467
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
468

469
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
470 471
		return;

472 473 474 475
	if (size > mctx->max_size)
		size = mctx->max_size;

	dl = ISC_LIST_HEAD(mctx->debuglist[size]);
Michael Graff's avatar
Michael Graff committed
476
	while (dl != NULL) {
477
		for (i = 0; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
478 479
			if (dl->ptr[i] == ptr) {
				dl->ptr[i] = NULL;
480
				dl->size[i] = 0;
Michael Graff's avatar
Michael Graff committed
481 482 483 484 485 486
				dl->file[i] = NULL;
				dl->line[i] = 0;

				INSIST(dl->count > 0);
				dl->count--;
				if (dl->count == 0) {
487
					ISC_LIST_UNLINK(mctx->debuglist[size],
Michael Graff's avatar
Michael Graff committed
488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504
							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 */

505 506 507
static inline size_t
rmsize(size_t size) {
	/*
Automatic Updater's avatar
Automatic Updater committed
508
	 * round down to ALIGNMENT_SIZE
509
	 */
510
	return (size & (~(ALIGNMENT_SIZE - 1)));
511 512
}

513
static inline size_t
Bob Halley's avatar
base  
Bob Halley committed
514
quantize(size_t size) {
515
	/*!
516
	 * Round up the result in order to get a size big
Bob Halley's avatar
base  
Bob Halley committed
517 518 519
	 * enough to satisfy the request and be aligned on ALIGNMENT_SIZE
	 * byte boundaries.
	 */
520

Mark Andrews's avatar
Mark Andrews committed
521
	if (size == 0U)
522
		return (ALIGNMENT_SIZE);
523
	return ((size + ALIGNMENT_SIZE - 1) & (~(ALIGNMENT_SIZE - 1)));
Bob Halley's avatar
base  
Bob Halley committed
524 525
}

526
static inline isc_boolean_t
527
more_basic_blocks(isc__mem_t *ctx) {
528 529 530 531 532
	void *new;
	unsigned char *curr, *next;
	unsigned char *first, *last;
	unsigned char **table;
	unsigned int table_size;
Bob Halley's avatar
Bob Halley committed
533
	size_t increment;
534 535 536 537
	int i;

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

538 539 540
	/*
	 * Did we hit the quota for this context?
	 */
Bob Halley's avatar
Bob Halley committed
541
	increment = NUM_BASIC_BLOCKS * ctx->mem_target;
Mark Andrews's avatar
Mark Andrews committed
542
	if (ctx->quota != 0U && ctx->total + increment > ctx->quota)
543
		return (ISC_FALSE);
544 545 546

	INSIST(ctx->basic_table_count <= ctx->basic_table_size);
	if (ctx->basic_table_count == ctx->basic_table_size) {
547
		table_size = ctx->basic_table_size + TABLE_INCREMENT;
548
		table = (ctx->memalloc)(ctx->arg,
Andreas Gustafsson's avatar
Andreas Gustafsson committed
549
					table_size * sizeof(unsigned char *));
550 551
		if (table == NULL) {
			ctx->memalloc_failures++;
552
			return (ISC_FALSE);
553
		}
554 555 556
		if (ctx->basic_table_size != 0) {
			memcpy(table, ctx->basic_table,
			       ctx->basic_table_size *
Andreas Gustafsson's avatar
Andreas Gustafsson committed
557
			       sizeof(unsigned char *));
558
			(ctx->memfree)(ctx->arg, ctx->basic_table);
559
		}
560 561
		ctx->basic_table = table;
		ctx->basic_table_size = table_size;
562
	}
563

564
	new = (ctx->memalloc)(ctx->arg, NUM_BASIC_BLOCKS * ctx->mem_target);
565 566
	if (new == NULL) {
		ctx->memalloc_failures++;
567
		return (ISC_FALSE);
568
	}
Bob Halley's avatar
Bob Halley committed
569
	ctx->total += increment;
570 571
	ctx->basic_table[ctx->basic_table_count] = new;
	ctx->basic_table_count++;
572

573 574 575
	curr = new;
	next = curr + ctx->mem_target;
	for (i = 0; i < (NUM_BASIC_BLOCKS - 1); i++) {
576
		((element *)curr)->next = (element *)next;
577 578 579 580 581 582 583
		curr = next;
		next += ctx->mem_target;
	}
	/*
	 * curr is now pointing at the last block in the
	 * array.
	 */
Bob Halley's avatar
Bob Halley committed
584
	((element *)curr)->next = NULL;
585 586 587 588 589 590 591
	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;
592 593

	return (ISC_TRUE);
594 595
}

596
static inline isc_boolean_t
597
more_frags(isc__mem_t *ctx, size_t new_size) {
598 599 600 601 602
	int i, frags;
	size_t total_size;
	void *new;
	unsigned char *curr, *next;

603
	/*!
604 605 606 607 608 609 610 611 612 613
	 * 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.
			 */
			/*
614
			 * XXXRTH  "At quota" notification here.
615
			 */
616
			return (ISC_FALSE);
617 618 619 620 621 622 623 624 625 626 627 628 629 630 631
		}
	}

	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;
632
	total_size -= new_size;
633 634 635 636
	for (i = 0; i < (frags - 1); i++) {
		((element *)curr)->next = (element *)next;
		curr = next;
		next += new_size;
637 638 639 640 641 642
		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
643
	if (total_size > 0U) {
644 645 646
		((element *)next)->next = ctx->freelists[total_size];
		ctx->freelists[total_size] = (element *)next;
		ctx->stats[total_size].freefrags++;
647 648 649 650 651 652 653 654 655 656 657
	}
	/*
	 * 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
658
static inline void *
659
mem_getunlocked(isc__mem_t *ctx, size_t size) {
Michael Graff's avatar
Michael Graff committed
660 661
	size_t new_size = quantize(size);
	void *ret;
Bob Halley's avatar
base  
Bob Halley committed
662 663

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

689
	/*
Bob Halley's avatar
base  
Bob Halley committed
690 691 692 693
	 * 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.
	 */
694 695
	if (ctx->freelists[new_size] == NULL && !more_frags(ctx, new_size))
		return (NULL);
Bob Halley's avatar
base  
Bob Halley committed
696

697 698 699
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Bob Halley's avatar
base  
Bob Halley committed
700 701 702
	ret = ctx->freelists[new_size];
	ctx->freelists[new_size] = ctx->freelists[new_size]->next;

703
	/*
Bob Halley's avatar
base  
Bob Halley committed
704 705 706 707 708 709 710 711
	 * 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--;
712
	ctx->inuse += new_size;
Bob Halley's avatar
base  
Bob Halley committed
713 714 715

 done:

716
#if ISC_MEM_FILL
717 718
	if (ret != NULL)
		memset(ret, 0xbe, new_size); /* Mnemonic for "beef". */
David Lawrence's avatar
David Lawrence committed
719 720 721
#endif

	return (ret);
Michael Graff's avatar
Michael Graff committed
722 723
}

724 725 726 727 728 729 730 731 732 733 734 735 736 737 738
#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
739
static inline void
740
mem_putunlocked(isc__mem_t *ctx, void *mem, size_t size) {
Michael Graff's avatar
Michael Graff committed
741
	size_t new_size = quantize(size);
Bob Halley's avatar
base  
Bob Halley committed
742

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

759 760
#if ISC_MEM_FILL
#if ISC_MEM_CHECKOVERRUN
761 762
	check_overrun(mem, size, new_size);
#endif
Mark Andrews's avatar
Mark Andrews committed
763 764
	memset(mem, 0xde, new_size); /* Mnemonic for "dead". */
#endif
765

766 767 768
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Mark Andrews's avatar
Mark Andrews committed
769 770
	((element *)mem)->next = ctx->freelists[new_size];
	ctx->freelists[new_size] = (element *)mem;
Bob Halley's avatar
base  
Bob Halley committed
771

772
	/*
Bob Halley's avatar
base  
Bob Halley committed
773 774 775 776 777
	 * 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
778
	INSIST(ctx->stats[size].gets != 0U);
Bob Halley's avatar
base  
Bob Halley committed
779 780
	ctx->stats[size].gets--;
	ctx->stats[new_size].freefrags++;
781
	ctx->inuse -= new_size;
Bob Halley's avatar
base  
Bob Halley committed
782 783
}

784
/*!
785 786 787
 * Perform a malloc, doing memory filling and overrun detection as necessary.
 */
static inline void *
788
mem_get(isc__mem_t *ctx, size_t size) {
789 790 791 792 793 794 795
	char *ret;

#if ISC_MEM_CHECKOVERRUN
	size += 1;
#endif

	ret = (ctx->memalloc)(ctx->arg, size);
796
	if (ret == NULL)
Automatic Updater's avatar
Automatic Updater committed
797
		ctx->memalloc_failures++;
798 799 800 801 802 803 804 805 806 807 808 809 810 811

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

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

828
/*!
829 830 831
 * Update internal counters after a memory get.
 */
static inline void
832
mem_getstats(isc__mem_t *ctx, size_t size) {
833 834 835 836 837 838 839 840 841 842 843 844
	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++;
	}
}

845
/*!
846 847 848
 * Update internal counters after a memory put.
 */
static inline void
849
mem_putstats(isc__mem_t *ctx, void *ptr, size_t size) {
850 851 852 853 854 855
	UNUSED(ptr);

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

	if (size > ctx->max_size) {
856
		INSIST(ctx->stats[ctx->max_size].gets > 0U);
857 858
		ctx->stats[ctx->max_size].gets--;
	} else {
859
		INSIST(ctx->stats[size].gets > 0U);
860 861 862 863
		ctx->stats[size].gets--;
	}
}

David Lawrence's avatar
David Lawrence committed
864 865 866 867 868 869 870
/*
 * Private.
 */

static void *
default_memalloc(void *arg, size_t size) {
	UNUSED(arg);
871
	if (size == 0U)
872
		size = 1;
David Lawrence's avatar
David Lawrence committed
873 874 875 876 877 878 879 880 881
	return (malloc(size));
}

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

882 883
static void
initialize_action(void) {
884
	RUNTIME_CHECK(isc_mutex_init(&lock) == ISC_R_SUCCESS);
Mark Andrews's avatar
Mark Andrews committed
885
	ISC_LIST_INIT(contexts);
886
	totallost = 0;
887 888
}

David Lawrence's avatar
David Lawrence committed
889 890 891 892
/*
 * Public.
 */

893 894 895 896
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)
897
{
898 899
	return (isc__mem_createx2(init_max_size, target_size, memalloc, memfree,
				  arg, ctxp, ISC_MEMFLAG_DEFAULT));
Automatic Updater's avatar
Automatic Updater committed
900

901 902
}

903 904 905 906
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
907
{
908
	isc__mem_t *ctx;
909
	isc_result_t result;
David Lawrence's avatar
David Lawrence committed
910 911 912 913 914

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

915 916
	INSIST((ALIGNMENT_SIZE & (ALIGNMENT_SIZE - 1)) == 0);

917 918
	RUNTIME_CHECK(isc_once_do(&once, initialize_action) == ISC_R_SUCCESS);

Andreas Gustafsson's avatar
Andreas Gustafsson committed
919
	ctx = (memalloc)(arg, sizeof(*ctx));
David Lawrence's avatar
David Lawrence committed
920 921 922
	if (ctx == NULL)
		return (ISC_R_NOMEMORY);

923
	if ((flags & ISC_MEMFLAG_NOLOCK) == 0) {
924
		result = isc_mutex_init(&ctx->lock);
925 926 927 928
		if (result != ISC_R_SUCCESS) {
			(memfree)(arg, ctx);
			return (result);
		}
929 930
	}

931
	if (init_max_size == 0U)
David Lawrence's avatar
David Lawrence committed
932 933 934
		ctx->max_size = DEF_MAX_SIZE;
	else
		ctx->max_size = init_max_size;
935
	ctx->flags = flags;
936
	ctx->references = 1;
937 938
	memset(ctx->name, 0, sizeof(ctx->name));
	ctx->tag = NULL;
939 940 941
	ctx->quota = 0;
	ctx->total = 0;
	ctx->inuse = 0;
942
	ctx->maxinuse = 0;
943 944 945
	ctx->hi_water = 0;
	ctx->lo_water = 0;
	ctx->hi_called = ISC_FALSE;
946
	ctx->is_overmem = ISC_FALSE;
947 948
	ctx->water = NULL;
	ctx->water_arg = NULL;