mem.c 58 KB
Newer Older
Bob Halley's avatar
base  
Bob Halley committed
1
/*
Automatic Updater's avatar
Automatic Updater committed
2
 * Copyright (C) 2004-2010  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.156 2010/05/12 00:46:55 marka 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
#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 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
{
	debuglink_t *dl;
	unsigned int i;
397
	unsigned int mysize = size;
Michael Graff's avatar
Michael Graff committed
398

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	return (ISC_TRUE);
590 591
}

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

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

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

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

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

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

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

 done:

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

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

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

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

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

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

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

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

#if ISC_MEM_CHECKOVERRUN
	size += 1;
#endif

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

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

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

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

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

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

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

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

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

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

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

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

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

897 898
}

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

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

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

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

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

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

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