mem.c 11.7 KB
Newer Older
Bob Halley's avatar
base  
Bob Halley committed
1
/*
Bob Halley's avatar
Bob Halley committed
2 3
 * Copyright (C) 1997, 1998  Internet Software Consortium.
 * 
Bob Halley's avatar
base  
Bob Halley committed
4 5 6
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
Bob Halley's avatar
Bob Halley committed
7
 * 
Bob Halley's avatar
base  
Bob Halley committed
8 9 10 11 12 13 14 15 16 17
 * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS
 * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE
 * CONSORTIUM 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
Bob Halley committed
18
#include <config.h>
Bob Halley's avatar
base  
Bob Halley committed
19 20 21

#include <stdio.h>
#include <stdlib.h>
Bob Halley's avatar
Bob Halley committed
22
#include <stddef.h>
Bob Halley's avatar
base  
Bob Halley committed
23 24 25
#include <string.h>

#include <isc/assertions.h>
26
#include <isc/error.h>
Bob Halley's avatar
Bob Halley committed
27
#include <isc/mem.h>
Bob Halley's avatar
Bob Halley committed
28

29
#ifndef ISC_SINGLETHREADED
Bob Halley's avatar
update  
Bob Halley committed
30
#include <isc/mutex.h>
Bob Halley's avatar
Bob Halley committed
31 32 33 34
#include "util.h"
#else
#define LOCK(ctx)
#define UNLOCK(ctx)
Bob Halley's avatar
update  
Bob Halley committed
35 36
#endif

Bob Halley's avatar
base  
Bob Halley committed
37 38 39 40 41 42
/*
 * Types.
 */

typedef struct {
	void *			next;
Bob Halley's avatar
Bob Halley committed
43
} element;
Bob Halley's avatar
base  
Bob Halley committed
44 45 46 47 48 49 50 51 52

typedef struct {
	size_t			size;
	/*
	 * This structure must be ALIGNMENT_SIZE bytes.
	 */
} *size_info;

struct stats {
Bob Halley's avatar
Bob Halley committed
53 54 55 56
	unsigned long		gets;
	unsigned long		totalgets;
	unsigned long		blocks;
	unsigned long		freefrags;
Bob Halley's avatar
base  
Bob Halley committed
57 58
};

Bob Halley's avatar
Bob Halley committed
59 60 61 62
#define MEM_MAGIC			0x4D656d43U	/* MemC. */
#define VALID_CONTEXT(c)		((c) != NULL && \
					 (c)->magic == MEM_MAGIC)

Bob Halley's avatar
Bob Halley committed
63
struct isc_memctx {
Bob Halley's avatar
Bob Halley committed
64 65
	unsigned int		magic;
	isc_mutex_t		lock;
Bob Halley's avatar
base  
Bob Halley committed
66 67
	size_t			max_size;
	size_t			mem_target;
Bob Halley's avatar
Bob Halley committed
68 69
	element **		freelists;
	element *		basic_blocks;
70 71 72
	unsigned char **	basic_table;
	unsigned int		basic_table_count;
	unsigned int		basic_table_size;
Bob Halley's avatar
Bob Halley committed
73 74
	unsigned char *		lowest;
	unsigned char *		highest;
Bob Halley's avatar
base  
Bob Halley committed
75 76 77 78 79 80 81
	struct stats *		stats;
};

/* Forward. */

static size_t			quantize(size_t);

Bob Halley's avatar
Bob Halley committed
82
/* Constants. */
Bob Halley's avatar
base  
Bob Halley committed
83 84 85 86 87

#define DEF_MAX_SIZE		1100
#define DEF_MEM_TARGET		4096
#define ALIGNMENT_SIZE		sizeof (void *)
#define NUM_BASIC_BLOCKS	64			/* must be > 1 */
88
#define TABLE_INCREMENT		1024
Bob Halley's avatar
base  
Bob Halley committed
89 90 91

/* Private Inline-able. */

Bob Halley's avatar
update  
Bob Halley committed
92
static inline size_t 
Bob Halley's avatar
base  
Bob Halley committed
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
quantize(size_t size) {
	int remainder;

	/*
	 * If there is no remainder for the integer division of 
	 *
	 *	(rightsize/ALIGNMENT_SIZE)
	 *
	 * then we already have a good size; if not, then we need
	 * to round up the result in order to get a size big
	 * enough to satisfy the request and be aligned on ALIGNMENT_SIZE
	 * byte boundaries.
	 */
	remainder = size % ALIGNMENT_SIZE;
	if (remainder != 0)
        	size += ALIGNMENT_SIZE - remainder;
	return (size);
}

/* Public. */

Bob Halley's avatar
Bob Halley committed
114 115 116 117 118 119 120
isc_result_t
isc_memctx_create(size_t init_max_size, size_t target_size,
		  isc_memctx_t *ctxp)
{
	isc_memctx_t ctx;

	REQUIRE(ctxp != NULL && *ctxp == NULL);
Bob Halley's avatar
base  
Bob Halley committed
121 122 123 124 125 126 127 128 129 130

	ctx = malloc(sizeof *ctx);
	if (init_max_size == 0)
		ctx->max_size = DEF_MAX_SIZE;
	else
		ctx->max_size = init_max_size;
	if (target_size == 0)
		ctx->mem_target = DEF_MEM_TARGET;
	else
		ctx->mem_target = target_size;
Bob Halley's avatar
Bob Halley committed
131
	ctx->freelists = malloc(ctx->max_size * sizeof (element *));
Bob Halley's avatar
base  
Bob Halley committed
132 133
	if (ctx->freelists == NULL) {
		free(ctx);
Bob Halley's avatar
Bob Halley committed
134
		return (ISC_R_NOMEMORY);
Bob Halley's avatar
base  
Bob Halley committed
135 136
	}
	memset(ctx->freelists, 0,
Bob Halley's avatar
Bob Halley committed
137
	       ctx->max_size * sizeof (element *));
Bob Halley's avatar
base  
Bob Halley committed
138 139 140 141
	ctx->stats = malloc((ctx->max_size+1) * sizeof (struct stats));
	if (ctx->stats == NULL) {
		free(ctx->freelists);
		free(ctx);
Bob Halley's avatar
Bob Halley committed
142
		return (ISC_R_NOMEMORY);
Bob Halley's avatar
base  
Bob Halley committed
143 144 145
	}
	memset(ctx->stats, 0, (ctx->max_size + 1) * sizeof (struct stats));
	ctx->basic_blocks = NULL;
146 147 148
	ctx->basic_table = NULL;
	ctx->basic_table_count = 0;
	ctx->basic_table_size = 0;
Bob Halley's avatar
base  
Bob Halley committed
149 150
	ctx->lowest = NULL;
	ctx->highest = NULL;
Bob Halley's avatar
Bob Halley committed
151
	if (isc_mutex_init(&ctx->lock) != ISC_R_SUCCESS) {
Bob Halley's avatar
update  
Bob Halley committed
152 153 154
		free(ctx->stats);
		free(ctx->freelists);
		free(ctx);
Bob Halley's avatar
Bob Halley committed
155
		UNEXPECTED_ERROR(__FILE__, __LINE__,
Bob Halley's avatar
Bob Halley committed
156
				 "isc_mutex_init() failed");
Bob Halley's avatar
Bob Halley committed
157
		return (ISC_R_UNEXPECTED);
Bob Halley's avatar
update  
Bob Halley committed
158
	}
Bob Halley's avatar
Bob Halley committed
159
	ctx->magic = MEM_MAGIC;
Bob Halley's avatar
base  
Bob Halley committed
160
	*ctxp = ctx;
Bob Halley's avatar
Bob Halley committed
161
	return (ISC_R_SUCCESS);
Bob Halley's avatar
base  
Bob Halley committed
162 163 164
}

void
Bob Halley's avatar
Bob Halley committed
165
isc_memctx_destroy(isc_memctx_t *ctxp) {
166
	unsigned int i;
Bob Halley's avatar
Bob Halley committed
167
	isc_memctx_t ctx;
168

Bob Halley's avatar
base  
Bob Halley committed
169
	REQUIRE(ctxp != NULL);
170
	ctx = *ctxp;
Bob Halley's avatar
Bob Halley committed
171 172 173
	REQUIRE(VALID_CONTEXT(ctx));

	ctx->magic = 0;
174 175 176 177 178 179 180 181 182

	for (i = 0; i <= ctx->max_size; i++)
		INSIST(ctx->stats[i].gets == 0);

	for (i = 0; i < ctx->basic_table_count; i++)
		free(ctx->basic_table[i]);
	free(ctx->freelists);
	free(ctx->stats);
	free(ctx->basic_table);
Bob Halley's avatar
Bob Halley committed
183
	(void)isc_mutex_destroy(&ctx->lock);
184
	free(ctx);
Bob Halley's avatar
base  
Bob Halley committed
185 186 187 188

	*ctxp = NULL;
}

189
static void
Bob Halley's avatar
Bob Halley committed
190
more_basic_blocks(isc_memctx_t ctx) {
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
	void *new;
	unsigned char *curr, *next;
	unsigned char *first, *last;
	unsigned char **table;
	unsigned int table_size;
	int i;

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

	if (ctx->basic_table_count <= ctx->basic_table_size) {
		table_size = ctx->basic_table_size + TABLE_INCREMENT;
		table = malloc(table_size * sizeof (unsigned char *));
		if (table == NULL)
			return;
		memcpy(table, ctx->basic_table,
		       ctx->basic_table_size * sizeof (unsigned char *));
		free(ctx->basic_table);
		ctx->basic_table = table;
		ctx->basic_table_size = table_size;
	} else
		table = NULL;

	new = malloc(NUM_BASIC_BLOCKS * ctx->mem_target);
	if (new == NULL) {
		if (table != NULL)
			free(table);
		return;
	}
	ctx->basic_table[ctx->basic_table_count] = new;
	ctx->basic_table_count++;
	curr = new;
	next = curr + ctx->mem_target;
	for (i = 0; i < (NUM_BASIC_BLOCKS - 1); i++) {
Bob Halley's avatar
Bob Halley committed
224
		((element *)curr)->next = next;
225 226 227 228 229 230 231
		curr = next;
		next += ctx->mem_target;
	}
	/*
	 * curr is now pointing at the last block in the
	 * array.
	 */
Bob Halley's avatar
Bob Halley committed
232
	((element *)curr)->next = NULL;
233 234 235 236 237 238 239 240 241
	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;
}

Bob Halley's avatar
base  
Bob Halley committed
242
void *
Bob Halley's avatar
Bob Halley committed
243
__isc_mem_get(isc_memctx_t ctx, size_t size) {
Bob Halley's avatar
base  
Bob Halley committed
244 245 246 247
	size_t new_size = quantize(size);
	void *ret;

	REQUIRE(size > 0);
Bob Halley's avatar
Bob Halley committed
248 249
	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269

	if (size >= ctx->max_size || new_size >= ctx->max_size) {
		/* memget() was called on something beyond our upper limit. */
		ret = malloc(size);
		if (ret != NULL) {
			ctx->stats[ctx->max_size].gets++;
			ctx->stats[ctx->max_size].totalgets++;
		}
		goto done;
	}

	/* 
	 * 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.
	 */
	if (ctx->freelists[new_size] == NULL) {
		int i, frags;
		size_t total_size;
		void *new;
Bob Halley's avatar
Bob Halley committed
270
		unsigned char *curr, *next;
Bob Halley's avatar
base  
Bob Halley committed
271 272

		if (ctx->basic_blocks == NULL) {
273 274
			more_basic_blocks(ctx);
			if (ctx->basic_blocks == NULL) {
Bob Halley's avatar
base  
Bob Halley committed
275 276 277 278 279 280 281 282 283 284 285 286 287 288
				ret = NULL;
				goto done;
			}
		}
		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;
		for (i = 0; i < (frags - 1); i++) {
Bob Halley's avatar
Bob Halley committed
289
			((element *)curr)->next = next;
Bob Halley's avatar
base  
Bob Halley committed
290 291 292 293
			curr = next;
			next += new_size;
		}
		/* curr is now pointing at the last block in the array. */
Bob Halley's avatar
Bob Halley committed
294
		((element *)curr)->next = NULL;
Bob Halley's avatar
base  
Bob Halley committed
295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
		ctx->freelists[new_size] = new;
	}

	/* The free list uses the "rounded-up" size "new_size": */
	ret = ctx->freelists[new_size];
	ctx->freelists[new_size] = ctx->freelists[new_size]->next;

	/* 
	 * 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--;

 done:
Bob Halley's avatar
Bob Halley committed
313
	UNLOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
314 315 316 317 318 319 320 321 322

	return (ret);
}

/* 
 * This is a call from an external caller, 
 * so we want to count this as a user "put". 
 */
void
Bob Halley's avatar
Bob Halley committed
323
__isc_mem_put(isc_memctx_t ctx, void *mem, size_t size) {
Bob Halley's avatar
base  
Bob Halley committed
324 325 326
	size_t new_size = quantize(size);

	REQUIRE(size > 0);
Bob Halley's avatar
Bob Halley committed
327 328
	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
329 330 331 332 333 334 335 336 337 338

	if (size == ctx->max_size || new_size >= ctx->max_size) {
		/* memput() called on something beyond our upper limit */
		free(mem);
		INSIST(ctx->stats[ctx->max_size].gets != 0);
		ctx->stats[ctx->max_size].gets--;
		goto done;
	}

	/* The free list uses the "rounded-up" size "new_size": */
Bob Halley's avatar
Bob Halley committed
339 340
	((element *)mem)->next = ctx->freelists[new_size];
	ctx->freelists[new_size] = (element *)mem;
Bob Halley's avatar
base  
Bob Halley committed
341 342 343 344 345 346 347 348 349 350 351 352

	/* 
	 * 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.
	 */
	INSIST(ctx->stats[size].gets != 0);
	ctx->stats[size].gets--;
	ctx->stats[new_size].freefrags++;

 done:
Bob Halley's avatar
Bob Halley committed
353
	UNLOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
354 355 356
}

void *
Bob Halley's avatar
Bob Halley committed
357
__isc_mem_getdebug(isc_memctx_t ctx, size_t size, const char *file, int line) {
Bob Halley's avatar
base  
Bob Halley committed
358
	void *ptr;
Bob Halley's avatar
Bob Halley committed
359 360

	ptr = __isc_mem_get(ctx, size);
Bob Halley's avatar
base  
Bob Halley committed
361
	fprintf(stderr, "%s:%d: mem_get(%p, %lu) -> %p\n", file, line,
Bob Halley's avatar
Bob Halley committed
362
		ctx, (unsigned long)size, ptr);
Bob Halley's avatar
base  
Bob Halley committed
363 364 365 366
	return (ptr);
}

void
Bob Halley's avatar
Bob Halley committed
367 368
__isc_mem_putdebug(isc_memctx_t ctx, void *ptr, size_t size, const char *file,
		   int line)
Bob Halley's avatar
base  
Bob Halley committed
369 370
{
	fprintf(stderr, "%s:%d: mem_put(%p, %p, %lu)\n", file, line, 
Bob Halley's avatar
Bob Halley committed
371
		ctx, ptr, (unsigned long)size);
Bob Halley's avatar
Bob Halley committed
372
	__isc_mem_put(ctx, ptr, size);
Bob Halley's avatar
base  
Bob Halley committed
373 374 375 376 377 378
}

/*
 * Print the stats[] on the stream "out" with suitable formatting.
 */
void
Bob Halley's avatar
Bob Halley committed
379
isc_mem_stats(isc_memctx_t ctx, FILE *out) {
Bob Halley's avatar
base  
Bob Halley committed
380 381
	size_t i;

Bob Halley's avatar
Bob Halley committed
382 383
	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400

	if (ctx->freelists == NULL)
		return;
	for (i = 1; i <= ctx->max_size; i++) {
		const struct stats *s = &ctx->stats[i];

		if (s->totalgets == 0 && s->gets == 0)
			continue;
		fprintf(out, "%s%5d: %11lu gets, %11lu rem",
			(i == ctx->max_size) ? ">=" : "  ",
			i, s->totalgets, s->gets);
		if (s->blocks != 0)
			fprintf(out, " (%lu bl, %lu ff)",
				s->blocks, s->freefrags);
		fputc('\n', out);
	}

Bob Halley's avatar
Bob Halley committed
401
	UNLOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
402 403
}

Bob Halley's avatar
Bob Halley committed
404 405
isc_boolean_t
isc_mem_valid(isc_memctx_t ctx, void *ptr) {
Bob Halley's avatar
Bob Halley committed
406
	unsigned char *cp = ptr;
Bob Halley's avatar
Bob Halley committed
407
	isc_boolean_t result = ISC_FALSE;
Bob Halley's avatar
base  
Bob Halley committed
408

Bob Halley's avatar
Bob Halley committed
409 410
	REQUIRE(VALID_CONTEXT(ctx));
	LOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
411 412

	if (ctx->lowest != NULL && cp >= ctx->lowest && cp <= ctx->highest)
Bob Halley's avatar
Bob Halley committed
413
		result = ISC_TRUE;
Bob Halley's avatar
base  
Bob Halley committed
414

Bob Halley's avatar
Bob Halley committed
415
	UNLOCK(&ctx->lock);
Bob Halley's avatar
base  
Bob Halley committed
416

Bob Halley's avatar
Bob Halley committed
417
	return (result);
Bob Halley's avatar
base  
Bob Halley committed
418 419 420 421 422 423 424
}

/*
 * Replacements for malloc() and free().
 */

void *
Bob Halley's avatar
Bob Halley committed
425
isc_mem_allocate(isc_memctx_t ctx, size_t size) {
Bob Halley's avatar
base  
Bob Halley committed
426 427 428
	size_info si;

	size += ALIGNMENT_SIZE;
Bob Halley's avatar
Bob Halley committed
429
	si = isc_mem_get(ctx, size);
Bob Halley's avatar
base  
Bob Halley committed
430 431 432 433 434 435 436
	if (si == NULL)
		return (NULL);
	si->size = size;
	return (&si[1]);
}

void
Bob Halley's avatar
Bob Halley committed
437
isc_mem_free(isc_memctx_t ctx, void *ptr) {
Bob Halley's avatar
base  
Bob Halley committed
438 439 440
	size_info si;

	si = &(((size_info)ptr)[-1]);
Bob Halley's avatar
Bob Halley committed
441
	isc_mem_put(ctx, si, si->size);
Bob Halley's avatar
base  
Bob Halley committed
442 443
}

Bob Halley's avatar
Bob Halley committed
444 445
#ifdef ISC_MEMCLUSTER_LEGACY

Bob Halley's avatar
base  
Bob Halley committed
446 447 448 449
/*
 * Public Legacy.
 */

Bob Halley's avatar
Bob Halley committed
450 451
static isc_memctx_t 		default_context = NULL;

Bob Halley's avatar
base  
Bob Halley committed
452 453 454 455 456
int
meminit(size_t init_max_size, size_t target_size) {
	/* need default_context lock here */
	if (default_context != NULL)
		return (-1);
Bob Halley's avatar
Bob Halley committed
457
	return (isc_mem_create(init_max_size, target_size, &default_context));
Bob Halley's avatar
base  
Bob Halley committed
458 459
}

Bob Halley's avatar
Bob Halley committed
460
isc_memctx_t
Bob Halley's avatar
base  
Bob Halley committed
461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487
mem_default_context(void) {
	/* need default_context lock here */
	if (default_context == NULL && meminit(0, 0) == -1)
		return (NULL);
	return (default_context);
}

void *
__memget(size_t size) {
	/* need default_context lock here */
	if (default_context == NULL && meminit(0, 0) == -1)
		return (NULL);
	return (__mem_get(default_context, size));
}

void
__memput(void *mem, size_t size) {
	/* need default_context lock here */
	REQUIRE(default_context != NULL);
	__mem_put(default_context, mem, size);
}

void *
__memget_debug(size_t size, const char *file, int line) {
	void *ptr;
	ptr = __memget(size);
	fprintf(stderr, "%s:%d: memget(%lu) -> %p\n", file, line,
Bob Halley's avatar
Bob Halley committed
488
		(unsigned long)size, ptr);
Bob Halley's avatar
base  
Bob Halley committed
489 490 491 492 493 494
	return (ptr);
}

void
__memput_debug(void *ptr, size_t size, const char *file, int line) {
	fprintf(stderr, "%s:%d: memput(%p, %lu)\n", file, line, 
Bob Halley's avatar
Bob Halley committed
495
		ptr, (unsigned long)size);
Bob Halley's avatar
base  
Bob Halley committed
496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511
	__memput(ptr, size);
}

int
memvalid(void *ptr) {
	/* need default_context lock here */
	REQUIRE(default_context != NULL);
	return (mem_valid(default_context, ptr));
}

void
memstats(FILE *out) {
	/* need default_context lock here */
	REQUIRE(default_context != NULL);
	mem_stats(default_context, out);
}
Bob Halley's avatar
Bob Halley committed
512 513

#endif /* ISC_MEMCLUSTER_LEGACY */