mem.c 59.7 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 275 276
ISC_MEMFUNC_SCOPE size_t
isc__mem_maxinuse(isc_mem_t *ctx);
ISC_MEMFUNC_SCOPE size_t
isc__mem_total(isc_mem_t *ctx);
277 278
ISC_MEMFUNC_SCOPE isc_boolean_t
isc__mem_isovermem(isc_mem_t *ctx);
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 331 332 333 334
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.
	 */
335
#ifndef BIND9
336 337
	void *createx, *create, *create2, *ondestroy, *stats,
		*setquota, *getquota, *setname, *getname, *gettag;
338
#endif
339 340 341 342 343 344 345 346 347
} memmethods = {
	{
		isc__mem_attach,
		isc__mem_detach,
		isc__mem_destroy,
		isc___mem_get,
		isc___mem_put,
		isc___mem_putanddetach,
		isc___mem_allocate,
348
		isc___mem_reallocate,
349 350 351 352 353 354
		isc___mem_strdup,
		isc___mem_free,
		isc__mem_setdestroycheck,
		isc__mem_setwater,
		isc__mem_waterack,
		isc__mem_inuse,
355 356
		isc__mem_maxinuse,
		isc__mem_total,
357
		isc__mem_isovermem,
358
		isc__mempool_create
359 360 361 362 363 364 365 366 367
	}
#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
368 369 370 371 372 373 374 375
};

static struct isc__mempoolmethods {
	isc_mempoolmethods_t methods;

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

398
/*!
Michael Graff's avatar
Michael Graff committed
399 400 401
 * mctx must be locked.
 */
static inline void
402
add_trace_entry(isc__mem_t *mctx, const void *ptr, unsigned int size
Michael Graff's avatar
pasto  
Michael Graff committed
403
		FLARG)
Michael Graff's avatar
Michael Graff committed
404 405 406
{
	debuglink_t *dl;
	unsigned int i;
407
	unsigned int mysize = size;
Michael Graff's avatar
Michael Graff committed
408

409
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
410 411 412 413
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_ADDTRACE,
					       "add %p size %u "
					       "file %s line %u mctx %p\n"),
414
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
415

416
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
417 418
		return;

419 420
	if (mysize > mctx->max_size)
		mysize = mctx->max_size;
421

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

	dl->ptr[0] = ptr;
452
	dl->size[0] = size;
Michael Graff's avatar
Michael Graff committed
453 454 455 456
	dl->file[0] = file;
	dl->line[0] = line;
	dl->count = 1;

457
	ISC_LIST_PREPEND(mctx->debuglist[mysize], dl, link);
458
	mctx->debuglistcnt++;
Michael Graff's avatar
Michael Graff committed
459 460 461
}

static inline void
462
delete_trace_entry(isc__mem_t *mctx, const void *ptr, unsigned int size,
Michael Graff's avatar
Michael Graff committed
463 464 465 466 467
		   const char *file, unsigned int line)
{
	debuglink_t *dl;
	unsigned int i;

468
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
469 470 471 472
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_DELTRACE,
					       "del %p size %u "
					       "file %s line %u mctx %p\n"),
473
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
474

475
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
476 477
		return;

478 479 480 481
	if (size > mctx->max_size)
		size = mctx->max_size;

	dl = ISC_LIST_HEAD(mctx->debuglist[size]);
Michael Graff's avatar
Michael Graff committed
482
	while (dl != NULL) {
483
		for (i = 0; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
484 485
			if (dl->ptr[i] == ptr) {
				dl->ptr[i] = NULL;
486
				dl->size[i] = 0;
Michael Graff's avatar
Michael Graff committed
487 488 489 490 491 492
				dl->file[i] = NULL;
				dl->line[i] = 0;

				INSIST(dl->count > 0);
				dl->count--;
				if (dl->count == 0) {
493
					ISC_LIST_UNLINK(mctx->debuglist[size],
Michael Graff's avatar
Michael Graff committed
494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510
							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 */

511 512 513
static inline size_t
rmsize(size_t size) {
	/*
Automatic Updater's avatar
Automatic Updater committed
514
	 * round down to ALIGNMENT_SIZE
515
	 */
516
	return (size & (~(ALIGNMENT_SIZE - 1)));
517 518
}

519
static inline size_t
Bob Halley's avatar
base  
Bob Halley committed
520
quantize(size_t size) {
521
	/*!
522
	 * Round up the result in order to get a size big
Bob Halley's avatar
base  
Bob Halley committed
523 524 525
	 * enough to satisfy the request and be aligned on ALIGNMENT_SIZE
	 * byte boundaries.
	 */
526

Mark Andrews's avatar
Mark Andrews committed
527
	if (size == 0U)
528
		return (ALIGNMENT_SIZE);
529
	return ((size + ALIGNMENT_SIZE - 1) & (~(ALIGNMENT_SIZE - 1)));
Bob Halley's avatar
base  
Bob Halley committed
530 531
}

532
static inline isc_boolean_t
533
more_basic_blocks(isc__mem_t *ctx) {
534 535 536 537 538
	void *new;
	unsigned char *curr, *next;
	unsigned char *first, *last;
	unsigned char **table;
	unsigned int table_size;
Bob Halley's avatar
Bob Halley committed
539
	size_t increment;
540 541 542 543
	int i;

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

544 545 546
	/*
	 * Did we hit the quota for this context?
	 */
Bob Halley's avatar
Bob Halley committed
547
	increment = NUM_BASIC_BLOCKS * ctx->mem_target;
Mark Andrews's avatar
Mark Andrews committed
548
	if (ctx->quota != 0U && ctx->total + increment > ctx->quota)
549
		return (ISC_FALSE);
550 551 552

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

570
	new = (ctx->memalloc)(ctx->arg, NUM_BASIC_BLOCKS * ctx->mem_target);
571 572
	if (new == NULL) {
		ctx->memalloc_failures++;
573
		return (ISC_FALSE);
574
	}
Bob Halley's avatar
Bob Halley committed
575
	ctx->total += increment;
576 577
	ctx->basic_table[ctx->basic_table_count] = new;
	ctx->basic_table_count++;
578

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

	return (ISC_TRUE);
600 601
}

602
static inline isc_boolean_t
603
more_frags(isc__mem_t *ctx, size_t new_size) {
604 605 606 607 608
	int i, frags;
	size_t total_size;
	void *new;
	unsigned char *curr, *next;

609
	/*!
610 611 612 613 614 615 616 617 618 619
	 * 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.
			 */
			/*
620
			 * XXXRTH  "At quota" notification here.
621
			 */
622
			return (ISC_FALSE);
623 624 625 626 627 628 629 630 631 632 633 634 635 636 637
		}
	}

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

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

695
	/*
Bob Halley's avatar
base  
Bob Halley committed
696 697 698 699
	 * 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.
	 */
700 701
	if (ctx->freelists[new_size] == NULL && !more_frags(ctx, new_size))
		return (NULL);
Bob Halley's avatar
base  
Bob Halley committed
702

703 704 705
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Bob Halley's avatar
base  
Bob Halley committed
706 707 708
	ret = ctx->freelists[new_size];
	ctx->freelists[new_size] = ctx->freelists[new_size]->next;

709
	/*
Bob Halley's avatar
base  
Bob Halley committed
710 711 712 713 714 715 716 717
	 * 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--;
718
	ctx->inuse += new_size;
Bob Halley's avatar
base  
Bob Halley committed
719 720 721

 done:

722
#if ISC_MEM_FILL
723 724
	if (ret != NULL)
		memset(ret, 0xbe, new_size); /* Mnemonic for "beef". */
David Lawrence's avatar
David Lawrence committed
725 726 727
#endif

	return (ret);
Michael Graff's avatar
Michael Graff committed
728 729
}

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

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

765 766
#if ISC_MEM_FILL
#if ISC_MEM_CHECKOVERRUN
767 768
	check_overrun(mem, size, new_size);
#endif
Mark Andrews's avatar
Mark Andrews committed
769 770
	memset(mem, 0xde, new_size); /* Mnemonic for "dead". */
#endif
771

772 773 774
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Mark Andrews's avatar
Mark Andrews committed
775 776
	((element *)mem)->next = ctx->freelists[new_size];
	ctx->freelists[new_size] = (element *)mem;
Bob Halley's avatar
base  
Bob Halley committed
777

778
	/*
Bob Halley's avatar
base  
Bob Halley committed
779 780 781 782 783
	 * 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
784
	INSIST(ctx->stats[size].gets != 0U);
Bob Halley's avatar
base  
Bob Halley committed
785 786
	ctx->stats[size].gets--;
	ctx->stats[new_size].freefrags++;
787
	ctx->inuse -= new_size;
Bob Halley's avatar
base  
Bob Halley committed
788 789
}

790
/*!
791 792 793
 * Perform a malloc, doing memory filling and overrun detection as necessary.
 */
static inline void *
794
mem_get(isc__mem_t *ctx, size_t size) {
795 796 797 798 799 800 801
	char *ret;

#if ISC_MEM_CHECKOVERRUN
	size += 1;
#endif

	ret = (ctx->memalloc)(ctx->arg, size);
802
	if (ret == NULL)
Automatic Updater's avatar
Automatic Updater committed
803
		ctx->memalloc_failures++;
804 805 806 807 808 809 810 811 812 813 814 815 816 817

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

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

834
/*!
835 836 837
 * Update internal counters after a memory get.
 */
static inline void
838
mem_getstats(isc__mem_t *ctx, size_t size) {
839 840 841 842 843 844 845 846 847 848 849 850
	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++;
	}
}

851
/*!
852 853 854
 * Update internal counters after a memory put.
 */
static inline void
855
mem_putstats(isc__mem_t *ctx, void *ptr, size_t size) {
856 857 858 859 860 861
	UNUSED(ptr);

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

	if (size > ctx->max_size) {
862
		INSIST(ctx->stats[ctx->max_size].gets > 0U);
863 864
		ctx->stats[ctx->max_size].gets--;
	} else {
865
		INSIST(ctx->stats[size].gets > 0U);
866 867 868 869
		ctx->stats[size].gets--;
	}
}

David Lawrence's avatar
David Lawrence committed
870 871 872 873 874 875 876
/*
 * Private.
 */

static void *
default_memalloc(void *arg, size_t size) {
	UNUSED(arg);
877
	if (size == 0U)
878
		size = 1;
David Lawrence's avatar
David Lawrence committed
879 880 881 882 883 884 885 886 887
	return (malloc(size));
}

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

888 889
static void
initialize_action(void) {
890
	RUNTIME_CHECK(isc_mutex_init(&lock) == ISC_R_SUCCESS);
Mark Andrews's avatar
Mark Andrews committed
891
	ISC_LIST_INIT(contexts);
892
	totallost = 0;
893 894
}

David Lawrence's avatar
David Lawrence committed
895 896 897 898
/*
 * Public.
 */

899 900 901 902
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)
903
{
904 905
	return (isc__mem_createx2(init_max_size, target_size, memalloc, memfree,
				  arg, ctxp, ISC_MEMFLAG_DEFAULT));
Automatic Updater's avatar
Automatic Updater committed
906

907 908
}

909 910 911 912
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
913
{
914
	isc__mem_t *ctx;
915
	isc_result_t result;
David Lawrence's avatar
David Lawrence committed
916 917 918 919 920

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

921 922
	INSIST((ALIGNMENT_SIZE & (ALIGNMENT_SIZE - 1)) == 0);

923 924
	RUNTIME_CHECK(isc_once_do(&once, initialize_action) == ISC_R_SUCCESS);

Andreas Gustafsson's avatar
Andreas Gustafsson committed
925
	ctx = (memalloc)(arg, sizeof(*ctx));
David Lawrence's avatar
David Lawrence committed
926 927 928
	if (ctx == NULL)
		return (ISC_R_NOMEMORY);

929
	if ((flags & ISC_MEMFLAG_NOLOCK) == 0) {
930
		result = isc_mutex_init(&ctx->lock);
931 932 933 934
		if (result != ISC_R_SUCCESS) {
			(memfree)(arg, ctx);
			return (result);
		}
935 936
	}

937
	if (init_max_size == 0U)
David Lawrence's avatar
David Lawrence committed
938 939 940
		ctx->max_size = DEF_MAX_SIZE;
	else
		ctx->max_size = init_max_size;
941
	ctx->flags = flags;
942
	ctx->references = 1;
943 944
	memset(ctx->name, 0, sizeof(ctx->name));
	ctx->tag = NULL;
945 946 947
	ctx->quota = 0;
	ctx->total = 0;
	ctx->inuse = 0;
948
	ctx->maxinuse = 0;
949 950 951
	ctx->hi_water = 0;
	ctx->lo_water = 0;
	ctx->hi_called = ISC_FALSE;
Tatuya JINMEI 神明達哉's avatar