2 * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (c) 1997,1999 by Internet Software Consortium.
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
15 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 /* When this symbol is defined allocations via memget are made slightly
20 bigger and some debugging info stuck before and after the region given
21 back to the caller. */
22 /* #define DEBUGGING_MEMCLUSTER */
23 #define MEMCLUSTER_ATEND
26 #if !defined(LINT) && !defined(CODECENTER)
27 static const char rcsid[] = "$Id: memcluster.c,v 1.3.2.3 2004/03/17 00:40:15 marka Exp $";
30 #include "port_before.h"
32 #include <sys/types.h>
34 #include <sys/param.h>
37 #include <netinet/in.h>
38 #include <arpa/inet.h>
39 #include <arpa/nameser.h>
47 #include <isc/memcluster.h>
48 #include <isc/assertions.h>
50 #include "port_after.h"
52 #ifdef MEMCLUSTER_RECORD
53 #ifndef DEBUGGING_MEMCLUSTER
54 #define DEBUGGING_MEMCLUSTER
58 #define DEF_MAX_SIZE 1100
59 #define DEF_MEM_TARGET 4096
61 typedef u_int32_t fence_t;
65 #if defined(DEBUGGING_MEMCLUSTER)
66 #if defined(MEMCLUSTER_RECORD)
75 #define SMALL_SIZE_LIMIT sizeof(memcluster_element)
76 #define P_SIZE sizeof(void *)
77 #define FRONT_FENCEPOST 0xfebafeba
78 #define BACK_FENCEPOST 0xabefabef
79 #define FENCEPOST_SIZE 4
81 #ifndef MEMCLUSTER_LITTLE_MALLOC
82 #define MEMCLUSTER_BIG_MALLOC 1
83 #define NUM_BASIC_BLOCKS 64
95 static size_t max_size;
96 static size_t mem_target;
97 static size_t mem_target_half;
98 static size_t mem_target_fudge;
99 static memcluster_element ** freelists;
100 #ifdef MEMCLUSTER_RECORD
101 static memcluster_element ** activelists;
103 #ifdef MEMCLUSTER_BIG_MALLOC
104 static memcluster_element * basic_blocks;
106 static struct stats * stats;
110 static size_t quantize(size_t);
111 #if defined(DEBUGGING_MEMCLUSTER)
112 static void check(unsigned char *, int, size_t);
118 meminit(size_t init_max_size, size_t target_size) {
120 #if defined(DEBUGGING_MEMCLUSTER)
121 INSIST(sizeof(fence_t) == FENCEPOST_SIZE);
123 if (freelists != NULL) {
127 if (init_max_size == 0U)
128 max_size = DEF_MAX_SIZE;
130 max_size = init_max_size;
131 if (target_size == 0U)
132 mem_target = DEF_MEM_TARGET;
134 mem_target = target_size;
135 mem_target_half = mem_target / 2;
136 mem_target_fudge = mem_target + mem_target / 4;
137 freelists = malloc(max_size * sizeof (memcluster_element *));
138 stats = malloc((max_size+1) * sizeof (struct stats));
139 if (freelists == NULL || stats == NULL) {
144 max_size * sizeof (memcluster_element *));
145 memset(stats, 0, (max_size + 1) * sizeof (struct stats));
146 #ifdef MEMCLUSTER_RECORD
147 activelists = malloc((max_size + 1) * sizeof (memcluster_element *));
148 if (activelists == NULL) {
152 memset(activelists, 0,
153 (max_size + 1) * sizeof (memcluster_element *));
155 #ifdef MEMCLUSTER_BIG_MALLOC
162 __memget(size_t size) {
163 return (__memget_record(size, NULL, 0));
167 __memget_record(size_t size, const char *file, int line) {
168 size_t new_size = quantize(size);
169 #if defined(DEBUGGING_MEMCLUSTER)
170 memcluster_element *e;
172 fence_t fp = BACK_FENCEPOST;
176 #if !defined(MEMCLUSTER_RECORD)
180 if (freelists == NULL)
181 if (meminit(0, 0) == -1)
187 if (size >= max_size || new_size >= max_size) {
188 /* memget() was called on something beyond our upper limit. */
189 stats[max_size].gets++;
190 stats[max_size].totalgets++;
191 #if defined(DEBUGGING_MEMCLUSTER)
192 e = malloc(new_size);
199 #ifdef MEMCLUSTER_RECORD
202 e->next = activelists[max_size];
203 activelists[max_size] = e;
205 e->fencepost = FRONT_FENCEPOST;
206 p = (char *)e + sizeof *e + size;
207 memcpy(p, &fp, sizeof fp);
208 return ((char *)e + sizeof *e);
210 return (malloc(size));
215 * If there are no blocks in the free list for this size, get a chunk
216 * of memory and then break it up into "new_size"-sized blocks, adding
217 * them to the free list.
219 if (freelists[new_size] == NULL) {
225 #ifdef MEMCLUSTER_BIG_MALLOC
226 if (basic_blocks == NULL) {
227 new = malloc(NUM_BASIC_BLOCKS * mem_target);
233 next = curr + mem_target;
234 for (i = 0; i < (NUM_BASIC_BLOCKS - 1); i++) {
235 ((memcluster_element *)curr)->next = next;
240 * curr is now pointing at the last block in the
243 ((memcluster_element *)curr)->next = NULL;
246 total_size = mem_target;
248 basic_blocks = basic_blocks->next;
250 if (new_size > mem_target_half)
251 total_size = mem_target_fudge;
253 total_size = mem_target;
254 new = malloc(total_size);
260 frags = total_size / new_size;
261 stats[new_size].blocks++;
262 stats[new_size].freefrags += frags;
263 /* Set up a linked-list of blocks of size "new_size". */
265 next = curr + new_size;
266 for (i = 0; i < (frags - 1); i++) {
267 #if defined (DEBUGGING_MEMCLUSTER)
268 memset(curr, 0xa5, new_size);
270 ((memcluster_element *)curr)->next = next;
274 /* curr is now pointing at the last block in the array. */
275 #if defined (DEBUGGING_MEMCLUSTER)
276 memset(curr, 0xa5, new_size);
278 ((memcluster_element *)curr)->next = freelists[new_size];
279 freelists[new_size] = new;
282 /* The free list uses the "rounded-up" size "new_size". */
283 #if defined (DEBUGGING_MEMCLUSTER)
284 e = freelists[new_size];
285 ret = (char *)e + sizeof *e;
287 * Check to see if this buffer has been written to while on free list.
289 check(ret, 0xa5, new_size - sizeof *e);
291 * Mark memory we are returning.
293 memset(ret, 0xe5, size);
295 ret = freelists[new_size];
297 freelists[new_size] = freelists[new_size]->next;
298 #if defined(DEBUGGING_MEMCLUSTER)
301 e->fencepost = FRONT_FENCEPOST;
302 #ifdef MEMCLUSTER_RECORD
305 e->next = activelists[size];
306 activelists[size] = e;
308 p = (char *)e + sizeof *e + size;
309 memcpy(p, &fp, sizeof fp);
313 * The stats[] uses the _actual_ "size" requested by the
314 * caller, with the caveat (in the code above) that "size" >= the
315 * max. size (max_size) ends up getting recorded as a call to
319 stats[size].totalgets++;
320 stats[new_size].freefrags--;
321 #if defined(DEBUGGING_MEMCLUSTER)
322 return ((char *)e + sizeof *e);
329 * This is a call from an external caller,
330 * so we want to count this as a user "put".
333 __memput(void *mem, size_t size) {
334 __memput_record(mem, size, NULL, 0);
338 __memput_record(void *mem, size_t size, const char *file, int line) {
339 size_t new_size = quantize(size);
340 #if defined (DEBUGGING_MEMCLUSTER)
341 memcluster_element *e;
342 memcluster_element *el;
343 #ifdef MEMCLUSTER_RECORD
344 memcluster_element *prev;
350 #if !defined (MEMCLUSTER_RECORD)
355 REQUIRE(freelists != NULL);
362 #if defined (DEBUGGING_MEMCLUSTER)
363 e = (memcluster_element *) ((char *)mem - sizeof *e);
364 INSIST(e->fencepost == FRONT_FENCEPOST);
365 INSIST(e->size == size);
366 p = (char *)e + sizeof *e + size;
367 memcpy(&fp, p, sizeof fp);
368 INSIST(fp == BACK_FENCEPOST);
369 INSIST(((int)mem % 4) == 0);
370 #ifdef MEMCLUSTER_RECORD
372 if (size == max_size || new_size >= max_size)
373 el = activelists[max_size];
375 el = activelists[size];
376 while (el != NULL && el != e) {
380 INSIST(el != NULL); /* double free */
382 if (size == max_size || new_size >= max_size)
383 activelists[max_size] = el->next;
385 activelists[size] = el->next;
387 prev->next = el->next;
391 if (size == max_size || new_size >= max_size) {
392 /* memput() called on something beyond our upper limit */
393 #if defined(DEBUGGING_MEMCLUSTER)
399 INSIST(stats[max_size].gets != 0U);
400 stats[max_size].gets--;
404 /* The free list uses the "rounded-up" size "new_size": */
405 #if defined(DEBUGGING_MEMCLUSTER)
406 memset(mem, 0xa5, new_size - sizeof *e); /* catch write after free */
407 e->size = 0; /* catch double memput() */
408 #ifdef MEMCLUSTER_RECORD
412 #ifdef MEMCLUSTER_ATEND
414 el = freelists[new_size];
415 while (el != NULL && el->next != NULL)
420 freelists[new_size] = e;
422 e->next = freelists[new_size];
423 freelists[new_size] = (void *)e;
426 ((memcluster_element *)mem)->next = freelists[new_size];
427 freelists[new_size] = (memcluster_element *)mem;
431 * The stats[] uses the _actual_ "size" requested by the
432 * caller, with the caveat (in the code above) that "size" >= the
433 * max. size (max_size) ends up getting recorded as a call to
436 INSIST(stats[size].gets != 0U);
438 stats[new_size].freefrags++;
442 __memget_debug(size_t size, const char *file, int line) {
444 ptr = __memget_record(size, file, line);
445 fprintf(stderr, "%s:%d: memget(%lu) -> %p\n", file, line,
451 __memput_debug(void *ptr, size_t size, const char *file, int line) {
452 fprintf(stderr, "%s:%d: memput(%p, %lu)\n", file, line, ptr,
454 __memput_record(ptr, size, file, line);
458 * Print the stats[] on the stream "out" with suitable formatting.
461 memstats(FILE *out) {
463 #ifdef MEMCLUSTER_RECORD
464 memcluster_element *e;
467 if (freelists == NULL)
469 for (i = 1; i <= max_size; i++) {
470 const struct stats *s = &stats[i];
472 if (s->totalgets == 0U && s->gets == 0U)
474 fprintf(out, "%s%5d: %11lu gets, %11lu rem",
475 (i == max_size) ? ">=" : " ",
476 i, s->totalgets, s->gets);
478 fprintf(out, " (%lu bl, %lu ff)",
479 s->blocks, s->freefrags);
482 #ifdef MEMCLUSTER_RECORD
483 fprintf(out, "Active Memory:\n");
484 for (i = 1; i <= max_size; i++) {
485 if ((e = activelists[i]) != NULL)
487 fprintf(out, "%s:%d %p:%d\n",
488 e->file != NULL ? e->file :
489 "<UNKNOWN>", e->line,
490 (char *)e + sizeof *e, e->size);
503 for (i = 1; i <= max_size; i++)
504 if (stats[i].gets != 0U)
512 * Round up size to a multiple of sizeof(void *). This guarantees that a
513 * block is at least sizeof void *, and that we won't violate alignment
514 * restrictions, both of which are needed to make lists of blocks.
517 quantize(size_t size) {
520 * If there is no remainder for the integer division of
524 * then we already have a good size; if not, then we need
525 * to round up the result in order to get a size big
526 * enough to satisfy the request _and_ aligned on P_SIZE boundaries.
528 remainder = size % P_SIZE;
530 size += P_SIZE - remainder;
531 #if defined(DEBUGGING_MEMCLUSTER)
532 return (size + SMALL_SIZE_LIMIT + sizeof (int));
538 #if defined(DEBUGGING_MEMCLUSTER)
540 check(unsigned char *a, int value, size_t len) {
542 for (i = 0; i < len; i++)
543 INSIST(a[i] == value);