mem.c 57.9 KB
Newer Older
Bob Halley's avatar
base  
Bob Halley committed
1
/*
Automatic Updater's avatar
Automatic Updater committed
2
 * Copyright (C) 2004-2009  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
 */

18
/* $Id: mem.c,v 1.153 2009/09/02 23:43:54 each Exp $ */
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 78 79 80 81 82
#define FLARG_PASS	, file, line
#define FLARG		, const char *file, int line
#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 147 148
	size_t			hi_water;
	size_t			lo_water;
	isc_boolean_t		hi_called;
	isc_mem_water_t		water;
	void *			water_arg;
149
	ISC_LIST(isc__mempool_t) pools;
150
	unsigned int		poolcnt;
151

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

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

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

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

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

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

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

214
static void
215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257
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);
258 259
ISC_MEMFUNC_SCOPE void *
isc___mem_reallocate(isc_mem_t *ctx, void *ptr, size_t size FLARG);
260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327
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);
ISC_MEMFUNC_SCOPE void
isc__mem_setwater(isc_mem_t *ctx, isc_mem_water_t water, void *water_arg,
		  size_t hiwater, size_t lowater);
ISC_MEMFUNC_SCOPE void
isc__mem_waterack(isc_mem_t *ctx0, int flag);
ISC_MEMFUNC_SCOPE void
isc__mem_setname(isc_mem_t *ctx, const char *name, void *tag);
ISC_MEMFUNC_SCOPE const char *
isc__mem_getname(isc_mem_t *ctx);
ISC_MEMFUNC_SCOPE void *
isc__mem_gettag(isc_mem_t *ctx);
ISC_MEMFUNC_SCOPE isc_result_t
isc__mempool_create(isc_mem_t *mctx, size_t size, isc_mempool_t **mpctxp);
ISC_MEMFUNC_SCOPE void
isc__mempool_setname(isc_mempool_t *mpctx, const char *name);
ISC_MEMFUNC_SCOPE void
isc__mempool_destroy(isc_mempool_t **mpctxp);
ISC_MEMFUNC_SCOPE void
isc__mempool_associatelock(isc_mempool_t *mpctx, isc_mutex_t *lock);
ISC_MEMFUNC_SCOPE void *
isc___mempool_get(isc_mempool_t *mpctx FLARG);
ISC_MEMFUNC_SCOPE void
isc___mempool_put(isc_mempool_t *mpctx, void *mem FLARG);
ISC_MEMFUNC_SCOPE void
isc__mempool_setfreemax(isc_mempool_t *mpctx, unsigned int limit);
ISC_MEMFUNC_SCOPE unsigned int
isc__mempool_getfreemax(isc_mempool_t *mpctx);
ISC_MEMFUNC_SCOPE unsigned int
isc__mempool_getfreecount(isc_mempool_t *mpctx);
ISC_MEMFUNC_SCOPE void
isc__mempool_setmaxalloc(isc_mempool_t *mpctx, unsigned int limit);
ISC_MEMFUNC_SCOPE unsigned int
isc__mempool_getmaxalloc(isc_mempool_t *mpctx);
ISC_MEMFUNC_SCOPE unsigned int
isc__mempool_getallocated(isc_mempool_t *mpctx);
ISC_MEMFUNC_SCOPE void
isc__mempool_setfillcount(isc_mempool_t *mpctx, unsigned int limit);
ISC_MEMFUNC_SCOPE unsigned int
isc__mempool_getfillcount(isc_mempool_t *mpctx);
#ifdef BIND9
ISC_MEMFUNC_SCOPE void
isc__mem_printactive(isc_mem_t *ctx0, FILE *file);
ISC_MEMFUNC_SCOPE void
isc__mem_printallactive(FILE *file);
ISC_MEMFUNC_SCOPE void
isc__mem_checkdestroyed(FILE *file);
ISC_MEMFUNC_SCOPE unsigned int
isc__mem_references(isc_mem_t *ctx0);
#endif

static struct isc__memmethods {
	isc_memmethods_t methods;

	/*%
	 * The following are defined just for avoiding unused static functions.
	 */
328
#ifndef BIND9
329 330
	void *createx, *create, *create2, *ondestroy, *stats,
		*setquota, *getquota, *setname, *getname, *gettag;
331
#endif
332 333 334 335 336 337 338 339 340
} memmethods = {
	{
		isc__mem_attach,
		isc__mem_detach,
		isc__mem_destroy,
		isc___mem_get,
		isc___mem_put,
		isc___mem_putanddetach,
		isc___mem_allocate,
341
		isc___mem_reallocate,
342 343 344 345 346 347 348
		isc___mem_strdup,
		isc___mem_free,
		isc__mem_setdestroycheck,
		isc__mem_setwater,
		isc__mem_waterack,
		isc__mem_inuse,
		isc__mempool_create
349 350 351 352 353 354 355 356 357
	}
#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
358 359 360 361 362 363 364 365
};

static struct isc__mempoolmethods {
	isc_mempoolmethods_t methods;

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

388
/*!
Michael Graff's avatar
Michael Graff committed
389 390 391
 * mctx must be locked.
 */
static inline void
392
add_trace_entry(isc__mem_t *mctx, const void *ptr, unsigned int size
Michael Graff's avatar
pasto  
Michael Graff committed
393
		FLARG)
Michael Graff's avatar
Michael Graff committed
394 395 396 397
{
	debuglink_t *dl;
	unsigned int i;

398
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
399 400 401 402
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_ADDTRACE,
					       "add %p size %u "
					       "file %s line %u mctx %p\n"),
403
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
404

405
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
406 407
		return;

408 409 410 411
	if (size > mctx->max_size)
		size = mctx->max_size;

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

	dl->ptr[0] = ptr;
441
	dl->size[0] = size;
Michael Graff's avatar
Michael Graff committed
442 443 444 445
	dl->file[0] = file;
	dl->line[0] = line;
	dl->count = 1;

446
	ISC_LIST_PREPEND(mctx->debuglist[size], dl, link);
447
	mctx->debuglistcnt++;
Michael Graff's avatar
Michael Graff committed
448 449 450
}

static inline void
451
delete_trace_entry(isc__mem_t *mctx, const void *ptr, unsigned int size,
Michael Graff's avatar
Michael Graff committed
452 453 454 455 456
		   const char *file, unsigned int line)
{
	debuglink_t *dl;
	unsigned int i;

457
	if ((isc_mem_debugging & ISC_MEM_DEBUGTRACE) != 0)
458 459 460 461
		fprintf(stderr, isc_msgcat_get(isc_msgcat, ISC_MSGSET_MEM,
					       ISC_MSG_DELTRACE,
					       "del %p size %u "
					       "file %s line %u mctx %p\n"),
462
			ptr, size, file, line, mctx);
Michael Graff's avatar
Michael Graff committed
463

464
	if (mctx->debuglist == NULL)
Michael Graff's avatar
Michael Graff committed
465 466
		return;

467 468 469 470
	if (size > mctx->max_size)
		size = mctx->max_size;

	dl = ISC_LIST_HEAD(mctx->debuglist[size]);
Michael Graff's avatar
Michael Graff committed
471
	while (dl != NULL) {
472
		for (i = 0; i < DEBUGLIST_COUNT; i++) {
Michael Graff's avatar
Michael Graff committed
473 474
			if (dl->ptr[i] == ptr) {
				dl->ptr[i] = NULL;
475
				dl->size[i] = 0;
Michael Graff's avatar
Michael Graff committed
476 477 478 479 480 481
				dl->file[i] = NULL;
				dl->line[i] = 0;

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

500 501 502
static inline size_t
rmsize(size_t size) {
	/*
Automatic Updater's avatar
Automatic Updater committed
503
	 * round down to ALIGNMENT_SIZE
504
	 */
505
	return (size & (~(ALIGNMENT_SIZE - 1)));
506 507
}

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

Mark Andrews's avatar
Mark Andrews committed
516
	if (size == 0U)
517
		return (ALIGNMENT_SIZE);
518
	return ((size + ALIGNMENT_SIZE - 1) & (~(ALIGNMENT_SIZE - 1)));
Bob Halley's avatar
base  
Bob Halley committed
519 520
}

521
static inline isc_boolean_t
522
more_basic_blocks(isc__mem_t *ctx) {
523 524 525 526 527
	void *new;
	unsigned char *curr, *next;
	unsigned char *first, *last;
	unsigned char **table;
	unsigned int table_size;
Bob Halley's avatar
Bob Halley committed
528
	size_t increment;
529 530 531 532
	int i;

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

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

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

559
	new = (ctx->memalloc)(ctx->arg, NUM_BASIC_BLOCKS * ctx->mem_target);
560 561
	if (new == NULL) {
		ctx->memalloc_failures++;
562
		return (ISC_FALSE);
563
	}
Bob Halley's avatar
Bob Halley committed
564
	ctx->total += increment;
565 566
	ctx->basic_table[ctx->basic_table_count] = new;
	ctx->basic_table_count++;
567

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

	return (ISC_TRUE);
589 590
}

591
static inline isc_boolean_t
592
more_frags(isc__mem_t *ctx, size_t new_size) {
593 594 595 596 597
	int i, frags;
	size_t total_size;
	void *new;
	unsigned char *curr, *next;

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

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

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

684
	/*
Bob Halley's avatar
base  
Bob Halley committed
685 686 687 688
	 * 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.
	 */
689 690
	if (ctx->freelists[new_size] == NULL && !more_frags(ctx, new_size))
		return (NULL);
Bob Halley's avatar
base  
Bob Halley committed
691

692 693 694
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Bob Halley's avatar
base  
Bob Halley committed
695 696 697
	ret = ctx->freelists[new_size];
	ctx->freelists[new_size] = ctx->freelists[new_size]->next;

698
	/*
Bob Halley's avatar
base  
Bob Halley committed
699 700 701 702 703 704 705 706
	 * 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--;
707
	ctx->inuse += new_size;
Bob Halley's avatar
base  
Bob Halley committed
708 709 710

 done:

711
#if ISC_MEM_FILL
712 713
	if (ret != NULL)
		memset(ret, 0xbe, new_size); /* Mnemonic for "beef". */
David Lawrence's avatar
David Lawrence committed
714 715 716
#endif

	return (ret);
Michael Graff's avatar
Michael Graff committed
717 718
}

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

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

754 755
#if ISC_MEM_FILL
#if ISC_MEM_CHECKOVERRUN
756 757
	check_overrun(mem, size, new_size);
#endif
Mark Andrews's avatar
Mark Andrews committed
758 759
	memset(mem, 0xde, new_size); /* Mnemonic for "dead". */
#endif
760

761 762 763
	/*
	 * The free list uses the "rounded-up" size "new_size".
	 */
Mark Andrews's avatar
Mark Andrews committed
764 765
	((element *)mem)->next = ctx->freelists[new_size];
	ctx->freelists[new_size] = (element *)mem;
Bob Halley's avatar
base  
Bob Halley committed
766

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

779
/*!
780 781 782
 * Perform a malloc, doing memory filling and overrun detection as necessary.
 */
static inline void *
783
mem_get(isc__mem_t *ctx, size_t size) {
784 785 786 787 788 789 790
	char *ret;

#if ISC_MEM_CHECKOVERRUN
	size += 1;
#endif

	ret = (ctx->memalloc)(ctx->arg, size);
791
	if (ret == NULL)
Automatic Updater's avatar
Automatic Updater committed
792
		ctx->memalloc_failures++;
793 794 795 796 797 798 799 800 801 802 803 804 805 806

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

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

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

840
/*!
841 842 843
 * Update internal counters after a memory put.
 */
static inline void
844
mem_putstats(isc__mem_t *ctx, void *ptr, size_t size) {
845 846 847 848 849 850
	UNUSED(ptr);

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

	if (size > ctx->max_size) {
851
		INSIST(ctx->stats[ctx->max_size].gets > 0U);
852 853
		ctx->stats[ctx->max_size].gets--;
	} else {
854
		INSIST(ctx->stats[size].gets > 0U);
855 856 857 858
		ctx->stats[size].gets--;
	}
}

David Lawrence's avatar
David Lawrence committed
859 860 861 862 863 864 865
/*
 * Private.
 */

static void *
default_memalloc(void *arg, size_t size) {
	UNUSED(arg);
866
	if (size == 0U)
867
		size = 1;
David Lawrence's avatar
David Lawrence committed
868 869 870 871 872 873 874 875 876
	return (malloc(size));
}

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

877 878
static void
initialize_action(void) {
879
	RUNTIME_CHECK(isc_mutex_init(&lock) == ISC_R_SUCCESS);
Mark Andrews's avatar
Mark Andrews committed
880
	ISC_LIST_INIT(contexts);
881
	totallost = 0;
882 883
}

David Lawrence's avatar
David Lawrence committed
884 885 886 887
/*
 * Public.
 */

888 889 890 891
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)
892
{
893 894
	return (isc__mem_createx2(init_max_size, target_size, memalloc, memfree,
				  arg, ctxp, ISC_MEMFLAG_DEFAULT));
Automatic Updater's avatar
Automatic Updater committed
895

896 897
}

898 899 900 901
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
902
{
903
	isc__mem_t *ctx;
904
	isc_result_t result;
David Lawrence's avatar
David Lawrence committed
905 906 907 908 909

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

910 911
	INSIST((ALIGNMENT_SIZE & (ALIGNMENT_SIZE - 1)) == 0);

912 913
	RUNTIME_CHECK(isc_once_do(&once, initialize_action) == ISC_R_SUCCESS);

Andreas Gustafsson's avatar
Andreas Gustafsson committed
914
	ctx = (memalloc)(arg, sizeof(*ctx));
David Lawrence's avatar
David Lawrence committed
915 916 917
	if (ctx == NULL)
		return (ISC_R_NOMEMORY);

918
	if ((flags & ISC_MEMFLAG_NOLOCK) == 0) {
919
		result = isc_mutex_init(&ctx->lock);
920 921 922 923
		if (result != ISC_R_SUCCESS) {
			(memfree)(arg, ctx);
			return (result);
		}
924 925
	}

926
	if (init_max_size == 0U)
David Lawrence's avatar
David Lawrence committed
927 928 929
		ctx->max_size = DEF_MAX_SIZE;
	else
		ctx->max_size = init_max_size;
930
	ctx->flags = flags;
931
	ctx->references = 1;
932 933
	memset(ctx->name, 0, sizeof(ctx->name));
	ctx->tag = NULL;
934 935 936
	ctx->quota = 0;
	ctx->total = 0;
	ctx->inuse = 0;
937
	ctx->maxinuse = 0;
938 939 940 941 942
	ctx->hi_water = 0;
	ctx->lo_water = 0;
	ctx->hi_called = ISC_FALSE;
	ctx->water = NULL;
	ctx->water_arg = NULL;
943 944 945
	ctx->common.impmagic = MEM_MAGIC;
	ctx->common.magic = ISCAPI_MCTX_MAGIC;
	ctx->common.methods = (isc_memmethods_t *)&memmethods;
946 947 948 949 950
	isc_ondestroy_init(&ctx->ondestroy);
	ctx->memalloc = memalloc;
	ctx->memfree = memfree;
	ctx->arg = arg;
	ctx->stats = NULL;
951
	ctx->checkfree = ISC_TRUE;
952
#if ISC_MEM_TRACKLINES
953
	ctx->debuglist = NULL;
954
	ctx->debuglistcnt = 0;
955
#endif
956
	ISC_LIST_INIT(ctx->pools);
957
	ctx->poolcnt = 0;
958
	ctx->freelists = NULL;
959 960