contrib/bind-9.2.4rc7/lib/bind/isc/memcluster.c

   1 /*
   2  * Copyright (c) 2004 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.2.3 2004/03/17 00:40:15 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 /* Private data. */
  94
  95 static size_t                   max_size;
  96 static size_t                   mem_target;
  97 static size_t                   mem_target_half;
  98 static size_t                   mem_target_fudge;
  99 static memcluster_element **    freelists;
 100 #ifdef MEMCLUSTER_RECORD
 101 static memcluster_element **    activelists;
 102 #endif
 103 #ifdef MEMCLUSTER_BIG_MALLOC
 104 static memcluster_element *     basic_blocks;
 105 #endif
 106 static struct stats *           stats;
 107
 108 /* Forward. */
 109
 110 static size_t                   quantize(size_t);
 111 #if defined(DEBUGGING_MEMCLUSTER)
 112 static void                     check(unsigned char *, int, size_t);
 113 #endif
 114
 115 /* Public. */
 116
 117 int
 118 meminit(size_t init_max_size, size_t target_size) {
 119
 120 #if defined(DEBUGGING_MEMCLUSTER)
 121         INSIST(sizeof(fence_t) == FENCEPOST_SIZE);
 122 #endif
 123         if (freelists != NULL) {
 124                 errno = EEXIST;
 125                 return (-1);
 126         }
 127         if (init_max_size == 0U)
 128                 max_size = DEF_MAX_SIZE;
 129         else
 130                 max_size = init_max_size;
 131         if (target_size == 0U)
 132                 mem_target = DEF_MEM_TARGET;
 133         else
 134                 mem_target = target_size;
 135         mem_target_half = mem_target / 2;
 136         mem_target_fudge = mem_target + mem_target / 4;
 137         freelists = malloc(max_size * sizeof (memcluster_element *));
 138         stats = malloc((max_size+1) * sizeof (struct stats));
 139         if (freelists == NULL || stats == NULL) {
 140                 errno = ENOMEM;
 141                 return (-1);
 142         }
 143         memset(freelists, 0,
 144                max_size * sizeof (memcluster_element *));
 145         memset(stats, 0, (max_size + 1) * sizeof (struct stats));
 146 #ifdef MEMCLUSTER_RECORD
 147         activelists = malloc((max_size + 1) * sizeof (memcluster_element *));
 148         if (activelists == NULL) {
 149                 errno = ENOMEM;
 150                 return (-1);
 151         }
 152         memset(activelists, 0,
 153                (max_size + 1) * sizeof (memcluster_element *));
 154 #endif
 155 #ifdef MEMCLUSTER_BIG_MALLOC
 156         basic_blocks = NULL;
 157 #endif
 158         return (0);
 159 }
 160
 161 void *
 162 __memget(size_t size) {
 163         return (__memget_record(size, NULL, 0));
 164 }
 165
 166 void *
 167 __memget_record(size_t size, const char *file, int line) {
 168         size_t new_size = quantize(size);
 169 #if defined(DEBUGGING_MEMCLUSTER)
 170         memcluster_element *e;
 171         char *p;
 172         fence_t fp = BACK_FENCEPOST;
 173 #endif
 174         void *ret;
 175
 176 #if !defined(MEMCLUSTER_RECORD)
 177         UNUSED(file);
 178         UNUSED(line);
 179 #endif
 180         if (freelists == NULL)
 181                 if (meminit(0, 0) == -1)
 182                         return (NULL);
 183         if (size == 0U) {
 184                 errno = EINVAL;
 185                 return (NULL);
 186         }
 187         if (size >= max_size || new_size >= max_size) {
 188                 /* memget() was called on something beyond our upper limit. */
 189                 stats[max_size].gets++;
 190                 stats[max_size].totalgets++;
 191 #if defined(DEBUGGING_MEMCLUSTER)
 192                 e = malloc(new_size);
 193                 if (e == NULL) {
 194                         errno = ENOMEM;
 195                         return (NULL);
 196                 }
 197                 e->next = NULL;
 198                 e->size = size;
 199 #ifdef MEMCLUSTER_RECORD
 200                 e->file = file;
 201                 e->line = line;
 202                 e->next = activelists[max_size];
 203                 activelists[max_size] = e;
 204 #endif
 205                 e->fencepost = FRONT_FENCEPOST;
 206                 p = (char *)e + sizeof *e + size;
 207                 memcpy(p, &fp, sizeof fp);
 208                 return ((char *)e + sizeof *e);
 209 #else
 210                 return (malloc(size));
 211 #endif
 212         }
 213
 214         /*
 215          * If there are no blocks in the free list for this size, get a chunk
 216          * of memory and then break it up into "new_size"-sized blocks, adding
 217          * them to the free list.
 218          */
 219         if (freelists[new_size] == NULL) {
 220                 int i, frags;
 221                 size_t total_size;
 222                 void *new;
 223                 char *curr, *next;
 224
 225 #ifdef MEMCLUSTER_BIG_MALLOC
 226                 if (basic_blocks == NULL) {
 227                         new = malloc(NUM_BASIC_BLOCKS * mem_target);
 228                         if (new == NULL) {
 229                                 errno = ENOMEM;
 230                                 return (NULL);
 231                         }
 232                         curr = new;
 233                         next = curr + mem_target;
 234                         for (i = 0; i < (NUM_BASIC_BLOCKS - 1); i++) {
 235                                 ((memcluster_element *)curr)->next = next;
 236                                 curr = next;
 237                                 next += mem_target;
 238                         }
 239                         /*
 240                          * curr is now pointing at the last block in the
 241                          * array.
 242                          */
 243                         ((memcluster_element *)curr)->next = NULL;
 244                         basic_blocks = new;
 245                 }
 246                 total_size = mem_target;
 247                 new = basic_blocks;
 248                 basic_blocks = basic_blocks->next;
 249 #else
 250                 if (new_size > mem_target_half)
 251                         total_size = mem_target_fudge;
 252                 else
 253                         total_size = mem_target;
 254                 new = malloc(total_size);
 255                 if (new == NULL) {
 256                         errno = ENOMEM;
 257                         return (NULL);
 258                 }
 259 #endif
 260                 frags = total_size / new_size;
 261                 stats[new_size].blocks++;
 262                 stats[new_size].freefrags += frags;
 263                 /* Set up a linked-list of blocks of size "new_size". */
 264                 curr = new;
 265                 next = curr + new_size;
 266                 for (i = 0; i < (frags - 1); i++) {
 267 #if defined (DEBUGGING_MEMCLUSTER)
 268                         memset(curr, 0xa5, new_size);
 269 #endif
 270                         ((memcluster_element *)curr)->next = next;
 271                         curr = next;
 272                         next += new_size;
 273                 }
 274                 /* curr is now pointing at the last block in the array. */
 275 #if defined (DEBUGGING_MEMCLUSTER)
 276                 memset(curr, 0xa5, new_size);
 277 #endif
 278                 ((memcluster_element *)curr)->next = freelists[new_size];
 279                 freelists[new_size] = new;
 280         }
 281
 282         /* The free list uses the "rounded-up" size "new_size". */
 283 #if defined (DEBUGGING_MEMCLUSTER)
 284         e = freelists[new_size];
 285         ret = (char *)e + sizeof *e;
 286         /*
 287          * Check to see if this buffer has been written to while on free list.
 288          */
 289         check(ret, 0xa5, new_size - sizeof *e);
 290         /*
 291          * Mark memory we are returning.
 292          */
 293         memset(ret, 0xe5, size);
 294 #else
 295         ret = freelists[new_size];
 296 #endif
 297         freelists[new_size] = freelists[new_size]->next;
 298 #if defined(DEBUGGING_MEMCLUSTER)
 299         e->next = NULL;
 300         e->size = size;
 301         e->fencepost = FRONT_FENCEPOST;
 302 #ifdef MEMCLUSTER_RECORD
 303         e->file = file;
 304         e->line = line;
 305         e->next = activelists[size];
 306         activelists[size] = e;
 307 #endif
 308         p = (char *)e + sizeof *e + size;
 309         memcpy(p, &fp, sizeof fp);
 310 #endif
 311
 312         /*
 313          * The stats[] uses the _actual_ "size" requested by the
 314          * caller, with the caveat (in the code above) that "size" >= the
 315          * max. size (max_size) ends up getting recorded as a call to
 316          * max_size.
 317          */
 318         stats[size].gets++;
 319         stats[size].totalgets++;
 320         stats[new_size].freefrags--;
 321 #if defined(DEBUGGING_MEMCLUSTER)
 322         return ((char *)e + sizeof *e);
 323 #else
 324         return (ret);
 325 #endif
 326 }
 327
 328 /*
 329  * This is a call from an external caller,
 330  * so we want to count this as a user "put".
 331  */
 332 void
 333 __memput(void *mem, size_t size) {
 334         __memput_record(mem, size, NULL, 0);
 335 }
 336
 337 void
 338 __memput_record(void *mem, size_t size, const char *file, int line) {
 339         size_t new_size = quantize(size);
 340 #if defined (DEBUGGING_MEMCLUSTER)
 341         memcluster_element *e;
 342         memcluster_element *el;
 343 #ifdef MEMCLUSTER_RECORD
 344         memcluster_element *prev;
 345 #endif
 346         fence_t fp;
 347         char *p;
 348 #endif
 349
 350 #if !defined (MEMCLUSTER_RECORD)
 351         UNUSED(file);
 352         UNUSED(line);
 353 #endif
 354
 355         REQUIRE(freelists != NULL);
 356
 357         if (size == 0U) {
 358                 errno = EINVAL;
 359                 return;
 360         }
 361
 362 #if defined (DEBUGGING_MEMCLUSTER)
 363         e = (memcluster_element *) ((char *)mem - sizeof *e);
 364         INSIST(e->fencepost == FRONT_FENCEPOST);
 365         INSIST(e->size == size);
 366         p = (char *)e + sizeof *e + size;
 367         memcpy(&fp, p, sizeof fp);
 368         INSIST(fp == BACK_FENCEPOST);
 369         INSIST(((int)mem % 4) == 0);
 370 #ifdef MEMCLUSTER_RECORD
 371         prev = NULL;
 372         if (size == max_size || new_size >= max_size)
 373                 el = activelists[max_size];
 374         else
 375                 el = activelists[size];
 376         while (el != NULL && el != e) {
 377                 prev = el;
 378                 el = el->next;
 379         }
 380         INSIST(el != NULL);     /* double free */
 381         if (prev == NULL) {
 382                 if (size == max_size || new_size >= max_size)
 383                         activelists[max_size] = el->next;
 384                 else
 385                         activelists[size] = el->next;
 386         } else
 387                 prev->next = el->next;
 388 #endif
 389 #endif
 390
 391         if (size == max_size || new_size >= max_size) {
 392                 /* memput() called on something beyond our upper limit */
 393 #if defined(DEBUGGING_MEMCLUSTER)
 394                 free(e);
 395 #else
 396                 free(mem);
 397 #endif
 398
 399                 INSIST(stats[max_size].gets != 0U);
 400                 stats[max_size].gets--;
 401                 return;
 402         }
 403
 404         /* The free list uses the "rounded-up" size "new_size": */
 405 #if defined(DEBUGGING_MEMCLUSTER)
 406         memset(mem, 0xa5, new_size - sizeof *e); /* catch write after free */
 407         e->size = 0;    /* catch double memput() */
 408 #ifdef MEMCLUSTER_RECORD
 409         e->file = file;
 410         e->line = line;
 411 #endif
 412 #ifdef MEMCLUSTER_ATEND
 413         e->next = NULL;
 414         el = freelists[new_size];
 415         while (el != NULL && el->next != NULL)
 416                 el = el->next;
 417         if (el)
 418                 el->next = e;
 419         else
 420                 freelists[new_size] = e;
 421 #else
 422         e->next = freelists[new_size];
 423         freelists[new_size] = (void *)e;
 424 #endif
 425 #else
 426         ((memcluster_element *)mem)->next = freelists[new_size];
 427         freelists[new_size] = (memcluster_element *)mem;
 428 #endif
 429
 430         /*
 431          * The stats[] uses the _actual_ "size" requested by the
 432          * caller, with the caveat (in the code above) that "size" >= the
 433          * max. size (max_size) ends up getting recorded as a call to
 434          * max_size.
 435          */
 436         INSIST(stats[size].gets != 0U);
 437         stats[size].gets--;
 438         stats[new_size].freefrags++;
 439 }
 440
 441 void *
 442 __memget_debug(size_t size, const char *file, int line) {
 443         void *ptr;
 444         ptr = __memget_record(size, file, line);
 445         fprintf(stderr, "%s:%d: memget(%lu) -> %p\n", file, line,
 446                 (u_long)size, ptr);
 447         return (ptr);
 448 }
 449
 450 void
 451 __memput_debug(void *ptr, size_t size, const char *file, int line) {
 452         fprintf(stderr, "%s:%d: memput(%p, %lu)\n", file, line, ptr,
 453                 (u_long)size);
 454         __memput_record(ptr, size, file, line);
 455 }
 456
 457 /*
 458  * Print the stats[] on the stream "out" with suitable formatting.
 459  */
 460 void
 461 memstats(FILE *out) {
 462         size_t i;
 463 #ifdef MEMCLUSTER_RECORD
 464         memcluster_element *e;
 465 #endif
 466
 467         if (freelists == NULL)
 468                 return;
 469         for (i = 1; i <= max_size; i++) {
 470                 const struct stats *s = &stats[i];
 471
 472                 if (s->totalgets == 0U && s->gets == 0U)
 473                         continue;
 474                 fprintf(out, "%s%5d: %11lu gets, %11lu rem",
 475                         (i == max_size) ? ">=" : "  ",
 476                         i, s->totalgets, s->gets);
 477                 if (s->blocks != 0U)
 478                         fprintf(out, " (%lu bl, %lu ff)",
 479                                 s->blocks, s->freefrags);
 480                 fputc('\n', out);
 481         }
 482 #ifdef MEMCLUSTER_RECORD
 483         fprintf(out, "Active Memory:\n");
 484         for (i = 1; i <= max_size; i++) {
 485                 if ((e = activelists[i]) != NULL)
 486                         while (e != NULL) {
 487                                 fprintf(out, "%s:%d %p:%d\n",
 488                                         e->file != NULL ? e->file :
 489                                                 "<UNKNOWN>", e->line,
 490                                         (char *)e + sizeof *e, e->size);
 491                                 e = e->next;
 492                         }
 493         }
 494 #endif
 495 }
 496
 497 int
 498 memactive(void) {
 499         size_t i;
 500
 501         if (stats == NULL)
 502                 return (0);
 503         for (i = 1; i <= max_size; i++)
 504                 if (stats[i].gets != 0U)
 505                         return (1);
 506         return (0);
 507 }
 508
 509 /* Private. */
 510
 511 /*
 512  * Round up size to a multiple of sizeof(void *).  This guarantees that a
 513  * block is at least sizeof void *, and that we won't violate alignment
 514  * restrictions, both of which are needed to make lists of blocks.
 515  */
 516 static size_t
 517 quantize(size_t size) {
 518         int remainder;
 519         /*
 520          * If there is no remainder for the integer division of
 521          *
 522          *      (rightsize/P_SIZE)
 523          *
 524          * then we already have a good size; if not, then we need
 525          * to round up the result in order to get a size big
 526          * enough to satisfy the request _and_ aligned on P_SIZE boundaries.
 527          */
 528         remainder = size % P_SIZE;
 529         if (remainder != 0)
 530                 size += P_SIZE - remainder;
 531 #if defined(DEBUGGING_MEMCLUSTER)
 532         return (size + SMALL_SIZE_LIMIT + sizeof (int));
 533 #else
 534         return (size);
 535 #endif
 536 }
 537
 538 #if defined(DEBUGGING_MEMCLUSTER)
 539 static void
 540 check(unsigned char *a, int value, size_t len) {
 541         size_t i;
 542         for (i = 0; i < len; i++)
 543                 INSIST(a[i] == value);
 544 }
 545 #endif