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