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 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 * 182 __memget(size_t size) { 183 return (__memget_record(size, NULL, 0)); 184 } 185 186 void * 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 365 __memput(void *mem, size_t size) { 366 __memput_record(mem, size, NULL, 0); 367 } 368 369 void 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 * 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 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 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 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 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 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