mem.c 64.3 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, 2013  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/json.h>
31
#include <isc/magic.h>
Bob Halley's avatar
Bob Halley committed
32
#include <isc/mem.h>
33
#include <isc/msgs.h>
34
#include <isc/once.h>
35
#include <isc/ondestroy.h>
36
#include <isc/string.h>
Bob Halley's avatar
update  
Bob Halley committed
37
#include <isc/mutex.h>
38
#include <isc/print.h>
Michael Graff's avatar
Michael Graff committed
39
#include <isc/util.h>
40
#include <isc/xml.h>
Bob Halley's avatar
update  
Bob Halley committed
41

42 43 44
#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)

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

/*
 * Constants.
 */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

217
static void
218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260
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);
261 262
ISC_MEMFUNC_SCOPE void *
isc___mem_reallocate(isc_mem_t *ctx, void *ptr, size_t size FLARG);
263 264 265 266 267 268 269 270 271 272 273 274
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);
275 276 277 278
ISC_MEMFUNC_SCOPE size_t
isc__mem_maxinuse(isc_mem_t *ctx);
ISC_MEMFUNC_SCOPE size_t
isc__mem_total(isc_mem_t *ctx);
279 280
ISC_MEMFUNC_SCOPE isc_boolean_t
isc__mem_isovermem(isc_mem_t *ctx);
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
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
330
#endif /* ISC_MEM_TRACKLINES */
331 332 333 334 335 336 337

static struct isc__memmethods {
	isc_memmethods_t methods;

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

static struct isc__mempoolmethods {
	isc_mempoolmethods_t methods;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	return (ISC_TRUE);
604 605
}

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

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

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

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

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

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

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

 done:

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

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

734 735 736 737 738 739 740 741 742 743 744 745 746 747 748
#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

749
/* coverity[+free : arg-1] */
Michael Graff's avatar
Michael Graff committed
750
static inline void
751
mem_putunlocked(isc__mem_t *ctx, void *mem, size_t size) {
Michael Graff's avatar
Michael Graff committed
752
	size_t new_size = quantize(size);
Bob Halley's avatar
base  
Bob Halley committed
753

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

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

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

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

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

#if ISC_MEM_CHECKOVERRUN
	size += 1;
#endif

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

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

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

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

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

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

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

David Lawrence's avatar
David Lawrence committed
876 877 878 879 880 881 882
/*
 * Private.
 */

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

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

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

David Lawrence's avatar
David Lawrence committed
901 902 903 904
/*
 * Public.
 */

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

913 914
}

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

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

927 928
	INSIST((ALIGNMENT_SIZE & (ALIGNMENT_SIZE - 1)) == 0);

929 930
	RUNTIME_CHECK(isc_once_do(&once, initialize_action) == ISC_R_SUCCESS);

Andreas Gustafsson's avatar
Andreas Gustafsson committed
931
	ctx = (memalloc)(arg, sizeof(*ctx));
David Lawrence's avatar
David Lawrence committed
932 933 934
	if (ctx == NULL)
		return (ISC_R_NOMEMORY);

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

943
	if (init_max_size == 0U)
David Lawrence's avatar
David Lawrence committed
944 945 946
		ctx->max_size = DEF_MAX_SIZE;
	else</