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

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

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

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

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

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

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

#if ISC_MEM_CHECKOVERRUN
	size += 1;
#endif

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

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

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

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

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

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

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

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

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

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

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

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

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

912 913
}

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

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

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

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

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

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

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