mem.c 60.4 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
#define ADD_TRACE(a, b, c, d, e)
#define DELETE_TRACE(a, b, c, d, e)
205
#define ISC_MEMFUNC_SCOPE
Michael Graff's avatar
Michael Graff committed
206
#else
207
#define ADD_TRACE(a, b, c, d, e) \
208 209 210 211
	do { \
		if ((isc_mem_debugging & (ISC_MEM_DEBUGTRACE | \
					  ISC_MEM_DEBUGRECORD)) != 0 && \
		     b != NULL) \
Automatic Updater's avatar
Automatic Updater committed
212
			 add_trace_entry(a, b, c, d, e); \
213
	} while (0)
Michael Graff's avatar
Michael Graff committed
214 215
#define DELETE_TRACE(a, b, c, d, e)	delete_trace_entry(a, b, c, d, e)

216
static void
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
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);
260 261
ISC_MEMFUNC_SCOPE void *
isc___mem_reallocate(isc_mem_t *ctx, void *ptr, size_t size FLARG);
262 263 264 265 266 267 268 269 270 271 272 273
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);
274 275 276 277
ISC_MEMFUNC_SCOPE size_t
isc__mem_maxinuse(isc_mem_t *ctx);
ISC_MEMFUNC_SCOPE size_t
isc__mem_total(isc_mem_t *ctx);
278 279
ISC_MEMFUNC_SCOPE isc_boolean_t
isc__mem_isovermem(isc_mem_t *ctx);
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
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
329
#endif /* ISC_MEM_TRACKLINES */
330 331 332 333 334 335 336

static struct isc__memmethods {
	isc_memmethods_t methods;

	/*%
	 * The following are defined just for avoiding unused static functions.
	 */
337
#ifndef BIND9
338 339
	void *createx, *create, *create2, *ondestroy, *stats,
		*setquota, *getquota, *setname, *getname, *gettag;
340
#endif
341 342 343 344 345 346 347 348 349
} memmethods = {
	{
		isc__mem_attach,
		isc__mem_detach,
		isc__mem_destroy,
		isc___mem_get,
		isc___mem_put,
		isc___mem_putanddetach,
		isc___mem_allocate,
350
		isc___mem_reallocate,
351 352 353 354 355 356
		isc___mem_strdup,
		isc___mem_free,
		isc__mem_setdestroycheck,
		isc__mem_setwater,
		isc__mem_waterack,
		isc__mem_inuse,
357 358
		isc__mem_maxinuse,
		isc__mem_total,
359
		isc__mem_isovermem,
360
		isc__mempool_create
361 362 363 364 365 366 367 368 369
	}
#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
370 371 372 373 374 375 376 377
};

static struct isc__mempoolmethods {
	isc_mempoolmethods_t methods;

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

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

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

419
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
420 421
		return;

422 423
	if (mysize > mctx->max_size)
		mysize = mctx->max_size;
424

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

	dl->ptr[0] = ptr;
455
	dl->size[0] = size;
Michael Graff's avatar
Michael Graff committed
456 457 458 459
	dl->file[0] = file;
	dl->line[0] = line;
	dl->count = 1;

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

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

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

478
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
479 480
		return;

481 482 483 484
	if (size > mctx->max_size)
		size = mctx->max_size;

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

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

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

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

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

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

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

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

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

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

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

	return (ISC_TRUE);
603 604
}

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

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

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

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

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

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

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

 done:

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

	return (ret);
Michael Graff's avatar
Michael Graff committed
731 732
}

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

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

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

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

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

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

#if ISC_MEM_CHECKOVERRUN
	size += 1;
#endif

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

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

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

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

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

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

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

David Lawrence's avatar
David Lawrence committed
873 874 875 876 877 878 879
/*
 * Private.
 */

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

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

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

David Lawrence's avatar
David Lawrence committed
898 899 900 901
/*
 * Public.
 */

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

910 911
}

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

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

924 925
	INSIST((ALIGNMENT_SIZE & (ALIGNMENT_SIZE - 1)) == 0);

926 927
	RUNTIME_CHECK(isc_once_do(&once, initialize_action) == ISC_R_SUCCESS);

Andreas Gustafsson's avatar
Andreas Gustafsson committed
928
	ctx = (memalloc)(arg, sizeof(*ctx));
David Lawrence's avatar
David Lawrence committed
929 930 931
	if (ctx == NULL)
		return (ISC_R_NOMEMORY);

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

940
	if (init_max_size == 0U)
David Lawrence's avatar
David Lawrence committed
941 942 943
		ctx->max_size = DEF_MAX_SIZE;
	else
		ctx->max_size = init_max_size;
944
	ctx->flags = flags;
945
	ctx->references = 1;
946 947
	memset(ctx->name, 0, sizeof(ctx->name));
	ctx->tag = N