contrib/bind-9.3/lib/bind/isc/memcluster.c

   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.3.206.8 2006/08/30 23:35:06 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