external/bsd/libbind/dist/isc/memcluster.c

   1 /*      $NetBSD$        */
   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 */