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