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