1 /* $NetBSD: memcluster.c,v 1.1.1.2 2012/09/09 16:08:02 christos Exp $ */
2
3 /*
4 * Copyright (c) 2005 by Internet Systems Consortium, Inc. ("ISC")
5 * Copyright (c) 1997,1999 by Internet Software Consortium.
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
17 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19
20
21 /* When this symbol is defined allocations via memget are made slightly
22 bigger and some debugging info stuck before and after the region given
23 back to the caller. */
24 /* #define DEBUGGING_MEMCLUSTER */
25 #define MEMCLUSTER_ATEND
26
27
28 #if !defined(LINT) && !defined(CODECENTER)
29 static const char rcsid[] = "Id: memcluster.c,v 1.11 2006/08/30 23:34:38 marka Exp ";
30 #endif /* not lint */
31
32 #include "port_before.h"
33
34 #include <sys/types.h>
35 #include <sys/uio.h>
36 #include <sys/param.h>
37 #include <sys/stat.h>
38
39 #include <netinet/in.h>
40 #include <arpa/inet.h>
41 #include <arpa/nameser.h>
42
43 #include <errno.h>
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <string.h>
47 #include <time.h>
48
49 #include <isc/memcluster.h>
50 #include <isc/assertions.h>
51
52 #include "port_after.h"
53
54 #ifdef MEMCLUSTER_RECORD
55 #ifndef DEBUGGING_MEMCLUSTER
56 #define DEBUGGING_MEMCLUSTER
57 #endif
58 #endif
59
60 #define DEF_MAX_SIZE 1100
61 #define DEF_MEM_TARGET 4096
62
63 typedef u_int32_t fence_t;
64
65 typedef struct {
66 void * next;
67 #if defined(DEBUGGING_MEMCLUSTER)
68 #if defined(MEMCLUSTER_RECORD)
69 const char * file;
70 int line;
71 #endif
72 size_t size;
73 fence_t fencepost;
74 #endif
75 } memcluster_element;
76
77 #define SMALL_SIZE_LIMIT sizeof(memcluster_element)
78 #define P_SIZE sizeof(void *)
79 #define FRONT_FENCEPOST 0xfebafeba
80 #define BACK_FENCEPOST 0xabefabef
81 #define FENCEPOST_SIZE 4
82
83 #ifndef MEMCLUSTER_LITTLE_MALLOC
84 #define MEMCLUSTER_BIG_MALLOC 1
85 #define NUM_BASIC_BLOCKS 64
86 #endif
87
88 struct stats {
89 u_long gets;
90 u_long totalgets;
91 u_long blocks;
92 u_long freefrags;
93 };
94
95 #ifdef DO_PTHREADS
96 #include <pthread.h>
97 static pthread_mutex_t memlock = PTHREAD_MUTEX_INITIALIZER;
98 #define MEMLOCK (void)pthread_mutex_lock(&memlock)
99 #define MEMUNLOCK (void)pthread_mutex_unlock(&memlock)
100 #else
101 /*
102 * Catch bad lock usage in non threaded build.
103 */
104 static unsigned int memlock = 0;
105 #define MEMLOCK do { INSIST(memlock == 0); memlock = 1; } while (0)
106 #define MEMUNLOCK do { INSIST(memlock == 1); memlock = 0; } while (0)
107 #endif /* DO_PTHEADS */
108
109 /* Private data. */
110
111 static size_t max_size;
112 static size_t mem_target;
113 #ifndef MEMCLUSTER_BIG_MALLOC
114 static size_t mem_target_half;
115 static size_t mem_target_fudge;
116 #endif
117 static memcluster_element ** freelists;
118 #ifdef MEMCLUSTER_RECORD
119 static memcluster_element ** activelists;
120 #endif
121 #ifdef MEMCLUSTER_BIG_MALLOC
122 static memcluster_element * basic_blocks;
123 #endif
124 static struct stats * stats;
125
126 /* Forward. */
127
128 static size_t quantize(size_t);
129 #if defined(DEBUGGING_MEMCLUSTER)
130 static void check(unsigned char *, int, size_t);
131 #endif
132
133 /* Public. */
134
135 int
meminit(size_t init_max_size,size_t target_size)136 meminit(size_t init_max_size, size_t target_size) {
137
138 #if defined(DEBUGGING_MEMCLUSTER)
139 INSIST(sizeof(fence_t) == FENCEPOST_SIZE);
140 #endif
141 if (freelists != NULL) {
142 errno = EEXIST;
143 return (-1);
144 }
145 if (init_max_size == 0U)
146 max_size = DEF_MAX_SIZE;
147 else
148 max_size = init_max_size;
149 if (target_size == 0U)
150 mem_target = DEF_MEM_TARGET;
151 else
152 mem_target = target_size;
153 #ifndef MEMCLUSTER_BIG_MALLOC
154 mem_target_half = mem_target / 2;
155 mem_target_fudge = mem_target + mem_target / 4;
156 #endif
157 freelists = malloc(max_size * sizeof (memcluster_element *));
158 stats = malloc((max_size+1) * sizeof (struct stats));
159 if (freelists == NULL || stats == NULL) {
160 errno = ENOMEM;
161 return (-1);
162 }
163 memset(freelists, 0,
164 max_size * sizeof (memcluster_element *));
165 memset(stats, 0, (max_size + 1) * sizeof (struct stats));
166 #ifdef MEMCLUSTER_RECORD
167 activelists = malloc((max_size + 1) * sizeof (memcluster_element *));
168 if (activelists == NULL) {
169 errno = ENOMEM;
170 return (-1);
171 }
172 memset(activelists, 0,
173 (max_size + 1) * sizeof (memcluster_element *));
174 #endif
175 #ifdef MEMCLUSTER_BIG_MALLOC
176 basic_blocks = NULL;
177 #endif
178 return (0);
179 }
180
181 void *
__memget(size_t size)182 __memget(size_t size) {
183 return (__memget_record(size, NULL, 0));
184 }
185
186 void *
__memget_record(size_t size,const char * file,int line)187 __memget_record(size_t size, const char *file, int line) {
188 size_t new_size = quantize(size);
189 #if defined(DEBUGGING_MEMCLUSTER)
190 memcluster_element *e;
191 char *p;
192 fence_t fp = BACK_FENCEPOST;
193 #endif
194 void *ret;
195
196 MEMLOCK;
197
198 #if !defined(MEMCLUSTER_RECORD)
199 UNUSED(file);
200 UNUSED(line);
201 #endif
202 if (freelists == NULL) {
203 if (meminit(0, 0) == -1) {
204 MEMUNLOCK;
205 return (NULL);
206 }
207 }
208 if (size == 0U) {
209 MEMUNLOCK;
210 errno = EINVAL;
211 return (NULL);
212 }
213 if (size >= max_size || new_size >= max_size) {
214 /* memget() was called on something beyond our upper limit. */
215 stats[max_size].gets++;
216 stats[max_size].totalgets++;
217 #if defined(DEBUGGING_MEMCLUSTER)
218 e = malloc(new_size);
219 if (e == NULL) {
220 MEMUNLOCK;
221 errno = ENOMEM;
222 return (NULL);
223 }
224 e->next = NULL;
225 e->size = size;
226 #ifdef MEMCLUSTER_RECORD
227 e->file = file;
228 e->line = line;
229 e->next = activelists[max_size];
230 activelists[max_size] = e;
231 #endif
232 MEMUNLOCK;
233 e->fencepost = FRONT_FENCEPOST;
234 p = (char *)e + sizeof *e + size;
235 memcpy(p, &fp, sizeof fp);
236 return ((char *)e + sizeof *e);
237 #else
238 MEMUNLOCK;
239 return (malloc(size));
240 #endif
241 }
242
243 /*
244 * If there are no blocks in the free list for this size, get a chunk
245 * of memory and then break it up into "new_size"-sized blocks, adding
246 * them to the free list.
247 */
248 if (freelists[new_size] == NULL) {
249 int i, frags;
250 size_t total_size;
251 void *new;
252 char *curr, *next;
253
254 #ifdef MEMCLUSTER_BIG_MALLOC
255 if (basic_blocks == NULL) {
256 new = malloc(NUM_BASIC_BLOCKS * mem_target);
257 if (new == NULL) {
258 MEMUNLOCK;
259 errno = ENOMEM;
260 return (NULL);
261 }
262 curr = new;
263 next = curr + mem_target;
264 for (i = 0; i < (NUM_BASIC_BLOCKS - 1); i++) {
265 ((memcluster_element *)curr)->next = next;
266 curr = next;
267 next += mem_target;
268 }
269 /*
270 * curr is now pointing at the last block in the
271 * array.
272 */
273 ((memcluster_element *)curr)->next = NULL;
274 basic_blocks = new;
275 }
276 total_size = mem_target;
277 new = basic_blocks;
278 basic_blocks = basic_blocks->next;
279 #else
280 if (new_size > mem_target_half)
281 total_size = mem_target_fudge;
282 else
283 total_size = mem_target;
284 new = malloc(total_size);
285 if (new == NULL) {
286 MEMUNLOCK;
287 errno = ENOMEM;
288 return (NULL);
289 }
290 #endif
291 frags = total_size / new_size;
292 stats[new_size].blocks++;
293 stats[new_size].freefrags += frags;
294 /* Set up a linked-list of blocks of size "new_size". */
295 curr = new;
296 next = curr + new_size;
297 for (i = 0; i < (frags - 1); i++) {
298 #if defined (DEBUGGING_MEMCLUSTER)
299 memset(curr, 0xa5, new_size);
300 #endif
301 ((memcluster_element *)curr)->next = next;
302 curr = next;
303 next += new_size;
304 }
305 /* curr is now pointing at the last block in the array. */
306 #if defined (DEBUGGING_MEMCLUSTER)
307 memset(curr, 0xa5, new_size);
308 #endif
309 ((memcluster_element *)curr)->next = freelists[new_size];
310 freelists[new_size] = new;
311 }
312
313 /* The free list uses the "rounded-up" size "new_size". */
314 #if defined (DEBUGGING_MEMCLUSTER)
315 e = freelists[new_size];
316 ret = (char *)e + sizeof *e;
317 /*
318 * Check to see if this buffer has been written to while on free list.
319 */
320 check(ret, 0xa5, new_size - sizeof *e);
321 /*
322 * Mark memory we are returning.
323 */
324 memset(ret, 0xe5, size);
325 #else
326 ret = freelists[new_size];
327 #endif
328 freelists[new_size] = freelists[new_size]->next;
329 #if defined(DEBUGGING_MEMCLUSTER)
330 e->next = NULL;
331 e->size = size;
332 e->fencepost = FRONT_FENCEPOST;
333 #ifdef MEMCLUSTER_RECORD
334 e->file = file;
335 e->line = line;
336 e->next = activelists[size];
337 activelists[size] = e;
338 #endif
339 p = (char *)e + sizeof *e + size;
340 memcpy(p, &fp, sizeof fp);
341 #endif
342
343 /*
344 * The stats[] uses the _actual_ "size" requested by the
345 * caller, with the caveat (in the code above) that "size" >= the
346 * max. size (max_size) ends up getting recorded as a call to
347 * max_size.
348 */
349 stats[size].gets++;
350 stats[size].totalgets++;
351 stats[new_size].freefrags--;
352 MEMUNLOCK;
353 #if defined(DEBUGGING_MEMCLUSTER)
354 return ((char *)e + sizeof *e);
355 #else
356 return (ret);
357 #endif
358 }
359
360 /*%
361 * This is a call from an external caller,
362 * so we want to count this as a user "put".
363 */
364 void
__memput(void * mem,size_t size)365 __memput(void *mem, size_t size) {
366 __memput_record(mem, size, NULL, 0);
367 }
368
369 void
__memput_record(void * mem,size_t size,const char * file,int line)370 __memput_record(void *mem, size_t size, const char *file, int line) {
371 size_t new_size = quantize(size);
372 #if defined (DEBUGGING_MEMCLUSTER)
373 memcluster_element *e;
374 memcluster_element *el;
375 #ifdef MEMCLUSTER_RECORD
376 memcluster_element *prev;
377 #endif
378 fence_t fp;
379 char *p;
380 #endif
381
382 MEMLOCK;
383
384 #if !defined (MEMCLUSTER_RECORD)
385 UNUSED(file);
386 UNUSED(line);
387 #endif
388
389 REQUIRE(freelists != NULL);
390
391 if (size == 0U) {
392 MEMUNLOCK;
393 errno = EINVAL;
394 return;
395 }
396
397 #if defined (DEBUGGING_MEMCLUSTER)
398 e = (memcluster_element *) ((char *)mem - sizeof *e);
399 INSIST(e->fencepost == FRONT_FENCEPOST);
400 INSIST(e->size == size);
401 p = (char *)e + sizeof *e + size;
402 memcpy(&fp, p, sizeof fp);
403 INSIST(fp == BACK_FENCEPOST);
404 INSIST(((u_long)mem % 4) == 0);
405 #ifdef MEMCLUSTER_RECORD
406 prev = NULL;
407 if (size == max_size || new_size >= max_size)
408 el = activelists[max_size];
409 else
410 el = activelists[size];
411 while (el != NULL && el != e) {
412 prev = el;
413 el = el->next;
414 }
415 INSIST(el != NULL); /*%< double free */
416 if (prev == NULL) {
417 if (size == max_size || new_size >= max_size)
418 activelists[max_size] = el->next;
419 else
420 activelists[size] = el->next;
421 } else
422 prev->next = el->next;
423 #endif
424 #endif
425
426 if (size == max_size || new_size >= max_size) {
427 /* memput() called on something beyond our upper limit */
428 #if defined(DEBUGGING_MEMCLUSTER)
429 free(e);
430 #else
431 free(mem);
432 #endif
433
434 INSIST(stats[max_size].gets != 0U);
435 stats[max_size].gets--;
436 MEMUNLOCK;
437 return;
438 }
439
440 /* The free list uses the "rounded-up" size "new_size": */
441 #if defined(DEBUGGING_MEMCLUSTER)
442 memset(mem, 0xa5, new_size - sizeof *e); /*%< catch write after free */
443 e->size = 0; /*%< catch double memput() */
444 #ifdef MEMCLUSTER_RECORD
445 e->file = file;
446 e->line = line;
447 #endif
448 #ifdef MEMCLUSTER_ATEND
449 e->next = NULL;
450 el = freelists[new_size];
451 while (el != NULL && el->next != NULL)
452 el = el->next;
453 if (el)
454 el->next = e;
455 else
456 freelists[new_size] = e;
457 #else
458 e->next = freelists[new_size];
459 freelists[new_size] = (void *)e;
460 #endif
461 #else
462 ((memcluster_element *)mem)->next = freelists[new_size];
463 freelists[new_size] = (memcluster_element *)mem;
464 #endif
465
466 /*
467 * The stats[] uses the _actual_ "size" requested by the
468 * caller, with the caveat (in the code above) that "size" >= the
469 * max. size (max_size) ends up getting recorded as a call to
470 * max_size.
471 */
472 INSIST(stats[size].gets != 0U);
473 stats[size].gets--;
474 stats[new_size].freefrags++;
475 MEMUNLOCK;
476 }
477
478 void *
__memget_debug(size_t size,const char * file,int line)479 __memget_debug(size_t size, const char *file, int line) {
480 void *ptr;
481 ptr = __memget_record(size, file, line);
482 fprintf(stderr, "%s:%d: memget(%lu) -> %p\n", file, line,
483 (u_long)size, ptr);
484 return (ptr);
485 }
486
487 void
__memput_debug(void * ptr,size_t size,const char * file,int line)488 __memput_debug(void *ptr, size_t size, const char *file, int line) {
489 fprintf(stderr, "%s:%d: memput(%p, %lu)\n", file, line, ptr,
490 (u_long)size);
491 __memput_record(ptr, size, file, line);
492 }
493
494 /*%
495 * Print the stats[] on the stream "out" with suitable formatting.
496 */
497 void
memstats(FILE * out)498 memstats(FILE *out) {
499 size_t i;
500 #ifdef MEMCLUSTER_RECORD
501 memcluster_element *e;
502 #endif
503
504 MEMLOCK;
505
506 if (freelists == NULL) {
507 MEMUNLOCK;
508 return;
509 }
510 for (i = 1; i <= max_size; i++) {
511 const struct stats *s = &stats[i];
512
513 if (s->totalgets == 0U && s->gets == 0U)
514 continue;
515 fprintf(out, "%s%5lu: %11lu gets, %11lu rem",
516 (i == max_size) ? ">=" : " ",
517 (unsigned long)i, s->totalgets, s->gets);
518 if (s->blocks != 0U)
519 fprintf(out, " (%lu bl, %lu ff)",
520 s->blocks, s->freefrags);
521 fputc('\n', out);
522 }
523 #ifdef MEMCLUSTER_RECORD
524 fprintf(out, "Active Memory:\n");
525 for (i = 1; i <= max_size; i++) {
526 if ((e = activelists[i]) != NULL)
527 while (e != NULL) {
528 fprintf(out, "%s:%d %p:%lu\n",
529 e->file != NULL ? e->file :
530 "<UNKNOWN>", e->line,
531 (char *)e + sizeof *e,
532 (u_long)e->size);
533 e = e->next;
534 }
535 }
536 #endif
537 MEMUNLOCK;
538 }
539
540 int
memactive(void)541 memactive(void) {
542 size_t i;
543
544 if (stats == NULL)
545 return (0);
546 for (i = 1; i <= max_size; i++)
547 if (stats[i].gets != 0U)
548 return (1);
549 return (0);
550 }
551
552 /* Private. */
553
554 /*%
555 * Round up size to a multiple of sizeof(void *). This guarantees that a
556 * block is at least sizeof void *, and that we won't violate alignment
557 * restrictions, both of which are needed to make lists of blocks.
558 */
559 static size_t
quantize(size_t size)560 quantize(size_t size) {
561 int remainder;
562 /*
563 * If there is no remainder for the integer division of
564 *
565 * (rightsize/P_SIZE)
566 *
567 * then we already have a good size; if not, then we need
568 * to round up the result in order to get a size big
569 * enough to satisfy the request _and_ aligned on P_SIZE boundaries.
570 */
571 remainder = size % P_SIZE;
572 if (remainder != 0)
573 size += P_SIZE - remainder;
574 #if defined(DEBUGGING_MEMCLUSTER)
575 return (size + SMALL_SIZE_LIMIT + sizeof (int));
576 #else
577 return (size);
578 #endif
579 }
580
581 #if defined(DEBUGGING_MEMCLUSTER)
582 static void
check(unsigned char * a,int value,size_t len)583 check(unsigned char *a, int value, size_t len) {
584 size_t i;
585 for (i = 0; i < len; i++)
586 INSIST(a[i] == value);
587 }
588 #endif
589
590 /*! \file */
591