gdb/bcache.c

   1 /* Implement a cached obstack.
   2    Written by Fred Fish <fnf@cygnus.com>
   3    Rewritten by Jim Blandy <jimb@cygnus.com>
   4
   5    Copyright 1999, 2000, 2002, 2003 Free Software Foundation, Inc.
   6
   7    This file is part of GDB.
   8
   9    This program is free software; you can redistribute it and/or modify
  10    it under the terms of the GNU General Public License as published by
  11    the Free Software Foundation; either version 2 of the License, or
  12    (at your option) any later version.
  13
  14    This program is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17    GNU General Public License for more details.
  18
  19    You should have received a copy of the GNU General Public License
  20    along with this program; if not, write to the Free Software
  21    Foundation, Inc., 59 Temple Place - Suite 330,
  22    Boston, MA 02111-1307, USA.  */
  23
  24 #include "defs.h"
  25 #include "gdb_obstack.h"
  26 #include "bcache.h"
  27 #include "gdb_string.h"         /* For memcpy declaration */
  28 #include "gdb_assert.h"
  29
  30 #include <stddef.h>
  31 #include <stdlib.h>
  32
  33 /* The type used to hold a single bcache string.  The user data is
  34    stored in d.data.  Since it can be any type, it needs to have the
  35    same alignment as the most strict alignment of any type on the host
  36    machine.  I don't know of any really correct way to do this in
  37    stock ANSI C, so just do it the same way obstack.h does.  */
  38
  39 struct bstring
  40 {
  41   struct bstring *next;
  42   size_t length;
  43
  44   union
  45   {
  46     char data[1];
  47     double dummy;
  48   }
  49   d;
  50 };
  51
  52
  53 /* The structure for a bcache itself.  The bcache is initialized, in
  54    bcache_xmalloc(), by filling it with zeros and then setting the
  55    corresponding obstack's malloc() and free() methods.  */
  56
  57 struct bcache
  58 {
  59   /* All the bstrings are allocated here.  */
  60   struct obstack cache;
  61
  62   /* How many hash buckets we're using.  */
  63   unsigned int num_buckets;
  64
  65   /* Hash buckets.  This table is allocated using malloc, so when we
  66      grow the table we can return the old table to the system.  */
  67   struct bstring **bucket;
  68
  69   /* Statistics.  */
  70   unsigned long unique_count;   /* number of unique strings */
  71   long total_count;     /* total number of strings cached, including dups */
  72   long unique_size;     /* size of unique strings, in bytes */
  73   long total_size;      /* total number of bytes cached, including dups */
  74   long structure_size;  /* total size of bcache, including infrastructure */
  75   /* Number of times that the hash table is expanded and hence
  76      re-built, and the corresponding number of times that a string is
  77      [re]hashed as part of entering it into the expanded table.  The
  78      total number of hashes can be computed by adding TOTAL_COUNT to
  79      expand_hash_count.  */
  80   unsigned long expand_count;
  81   unsigned long expand_hash_count;
  82 };
  83
  84 /* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
  85  * and is better than the old one.
  86  */
  87 \f
  88 unsigned long
  89 hash(const void *addr, int length)
  90 {
  91                 const unsigned char *k, *e;
  92                 unsigned long h;
  93
  94                 k = (const unsigned char *)addr;
  95                 e = k+length;
  96                 for (h=0; k< e;++k)
  97                 {
  98                                 h *=16777619;
  99                                 h ^= *k;
 100                 }
 101                 return (h);
 102 }
 103 \f
 104 /* Growing the bcache's hash table.  */
 105
 106 /* If the average chain length grows beyond this, then we want to
 107    resize our hash table.  */
 108 #define CHAIN_LENGTH_THRESHOLD (5)
 109
 110 static void
 111 expand_hash_table (struct bcache *bcache)
 112 {
 113   /* A table of good hash table sizes.  Whenever we grow, we pick the
 114      next larger size from this table.  sizes[i] is close to 1 << (i+10),
 115      so we roughly double the table size each time.  After we fall off
 116      the end of this table, we just double.  Don't laugh --- there have
 117      been executables sighted with a gigabyte of debug info.  */
 118   static unsigned long sizes[] = {
 119     1021, 2053, 4099, 8191, 16381, 32771,
 120     65537, 131071, 262144, 524287, 1048573, 2097143,
 121     4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
 122     268435459, 536870923, 1073741827, 2147483659UL
 123   };
 124   unsigned int new_num_buckets;
 125   struct bstring **new_buckets;
 126   unsigned int i;
 127
 128   /* Count the stats.  Every unique item needs to be re-hashed and
 129      re-entered.  */
 130   bcache->expand_count++;
 131   bcache->expand_hash_count += bcache->unique_count;
 132
 133   /* Find the next size.  */
 134   new_num_buckets = bcache->num_buckets * 2;
 135   for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
 136     if (sizes[i] > bcache->num_buckets)
 137       {
 138         new_num_buckets = sizes[i];
 139         break;
 140       }
 141
 142   /* Allocate the new table.  */
 143   {
 144     size_t new_size = new_num_buckets * sizeof (new_buckets[0]);
 145     new_buckets = (struct bstring **) xmalloc (new_size);
 146     memset (new_buckets, 0, new_size);
 147
 148     bcache->structure_size -= (bcache->num_buckets
 149                                * sizeof (bcache->bucket[0]));
 150     bcache->structure_size += new_size;
 151   }
 152
 153   /* Rehash all existing strings.  */
 154   for (i = 0; i < bcache->num_buckets; i++)
 155     {
 156       struct bstring *s, *next;
 157
 158       for (s = bcache->bucket[i]; s; s = next)
 159         {
 160           struct bstring **new_bucket;
 161           next = s->next;
 162
 163           new_bucket = &new_buckets[(hash (&s->d.data, s->length)
 164                                      % new_num_buckets)];
 165           s->next = *new_bucket;
 166           *new_bucket = s;
 167         }
 168     }
 169
 170   /* Plug in the new table.  */
 171   if (bcache->bucket)
 172     xfree (bcache->bucket);
 173   bcache->bucket = new_buckets;
 174   bcache->num_buckets = new_num_buckets;
 175 }
 176
 177 \f
 178 /* Looking up things in the bcache.  */
 179
 180 /* The number of bytes needed to allocate a struct bstring whose data
 181    is N bytes long.  */
 182 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
 183
 184 /* Find a copy of the LENGTH bytes at ADDR in BCACHE.  If BCACHE has
 185    never seen those bytes before, add a copy of them to BCACHE.  In
 186    either case, return a pointer to BCACHE's copy of that string.  */
 187 void *
 188 bcache (const void *addr, int length, struct bcache *bcache)
 189 {
 190   int hash_index;
 191   struct bstring *s;
 192
 193   /* If our average chain length is too high, expand the hash table.  */
 194   if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD)
 195     expand_hash_table (bcache);
 196
 197   bcache->total_count++;
 198   bcache->total_size += length;
 199
 200   hash_index = hash (addr, length) % bcache->num_buckets;
 201
 202   /* Search the hash bucket for a string identical to the caller's.  */
 203   for (s = bcache->bucket[hash_index]; s; s = s->next)
 204     if (s->length == length
 205         && ! memcmp (&s->d.data, addr, length))
 206       return &s->d.data;
 207
 208   /* The user's string isn't in the list.  Insert it after *ps.  */
 209   {
 210     struct bstring *new
 211       = obstack_alloc (&bcache->cache, BSTRING_SIZE (length));
 212     memcpy (&new->d.data, addr, length);
 213     new->length = length;
 214     new->next = bcache->bucket[hash_index];
 215     bcache->bucket[hash_index] = new;
 216
 217     bcache->unique_count++;
 218     bcache->unique_size += length;
 219     bcache->structure_size += BSTRING_SIZE (length);
 220
 221     return &new->d.data;
 222   }
 223 }
 224
 225 \f
 226 /* Allocating and freeing bcaches.  */
 227
 228 struct bcache *
 229 bcache_xmalloc (void)
 230 {
 231   /* Allocate the bcache pre-zeroed.  */
 232   struct bcache *b = XCALLOC (1, struct bcache);
 233   obstack_specify_allocation (&b->cache, 0, 0, xmalloc, xfree);
 234   return b;
 235 }
 236
 237 /* Free all the storage associated with BCACHE.  */
 238 void
 239 bcache_xfree (struct bcache *bcache)
 240 {
 241   if (bcache == NULL)
 242     return;
 243   obstack_free (&bcache->cache, 0);
 244   xfree (bcache->bucket);
 245   xfree (bcache);
 246 }
 247
 248
 249 \f
 250 /* Printing statistics.  */
 251
 252 static int
 253 compare_ints (const void *ap, const void *bp)
 254 {
 255   /* Because we know we're comparing two ints which are positive,
 256      there's no danger of overflow here.  */
 257   return * (int *) ap - * (int *) bp;
 258 }
 259
 260
 261 static void
 262 print_percentage (int portion, int total)
 263 {
 264   if (total == 0)
 265     printf_filtered ("(not applicable)\n");
 266   else
 267     printf_filtered ("%3d%%\n", portion * 100 / total);
 268 }
 269
 270
 271 /* Print statistics on BCACHE's memory usage and efficacity at
 272    eliminating duplication.  NAME should describe the kind of data
 273    BCACHE holds.  Statistics are printed using `printf_filtered' and
 274    its ilk.  */
 275 void
 276 print_bcache_statistics (struct bcache *c, char *type)
 277 {
 278   int occupied_buckets;
 279   int max_chain_length;
 280   int median_chain_length;
 281   int max_entry_size;
 282   int median_entry_size;
 283
 284   /* Count the number of occupied buckets, tally the various string
 285      lengths, and measure chain lengths.  */
 286   {
 287     unsigned int b;
 288     int *chain_length = XCALLOC (c->num_buckets + 1, int);
 289     int *entry_size = XCALLOC (c->unique_count + 1, int);
 290     int stringi = 0;
 291
 292     occupied_buckets = 0;
 293
 294     for (b = 0; b < c->num_buckets; b++)
 295       {
 296         struct bstring *s = c->bucket[b];
 297
 298         chain_length[b] = 0;
 299
 300         if (s)
 301           {
 302             occupied_buckets++;
 303
 304             while (s)
 305               {
 306                 gdb_assert (b < c->num_buckets);
 307                 chain_length[b]++;
 308                 gdb_assert (stringi < c->unique_count);
 309                 entry_size[stringi++] = s->length;
 310                 s = s->next;
 311               }
 312           }
 313       }
 314
 315     /* To compute the median, we need the set of chain lengths sorted.  */
 316     qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
 317            compare_ints);
 318     qsort (entry_size, c->unique_count, sizeof (entry_size[0]),
 319            compare_ints);
 320
 321     if (c->num_buckets > 0)
 322       {
 323         max_chain_length = chain_length[c->num_buckets - 1];
 324         median_chain_length = chain_length[c->num_buckets / 2];
 325       }
 326     else
 327       {
 328         max_chain_length = 0;
 329         median_chain_length = 0;
 330       }
 331     if (c->unique_count > 0)
 332       {
 333         max_entry_size = entry_size[c->unique_count - 1];
 334         median_entry_size = entry_size[c->unique_count / 2];
 335       }
 336     else
 337       {
 338         max_entry_size = 0;
 339         median_entry_size = 0;
 340       }
 341
 342     xfree (chain_length);
 343     xfree (entry_size);
 344   }
 345
 346   printf_filtered ("  Cached '%s' statistics:\n", type);
 347   printf_filtered ("    Total object count:  %ld\n", c->total_count);
 348   printf_filtered ("    Unique object count: %lu\n", c->unique_count);
 349   printf_filtered ("    Percentage of duplicates, by count: ");
 350   print_percentage (c->total_count - c->unique_count, c->total_count);
 351   printf_filtered ("\n");
 352
 353   printf_filtered ("    Total object size:   %ld\n", c->total_size);
 354   printf_filtered ("    Unique object size:  %ld\n", c->unique_size);
 355   printf_filtered ("    Percentage of duplicates, by size:  ");
 356   print_percentage (c->total_size - c->unique_size, c->total_size);
 357   printf_filtered ("\n");
 358
 359   printf_filtered ("    Max entry size:     %d\n", max_entry_size);
 360   printf_filtered ("    Average entry size: ");
 361   if (c->unique_count > 0)
 362     printf_filtered ("%ld\n", c->unique_size / c->unique_count);
 363   else
 364     printf_filtered ("(not applicable)\n");
 365   printf_filtered ("    Median entry size:  %d\n", median_entry_size);
 366   printf_filtered ("\n");
 367
 368   printf_filtered ("    Total memory used by bcache, including overhead: %ld\n",
 369                    c->structure_size);
 370   printf_filtered ("    Percentage memory overhead: ");
 371   print_percentage (c->structure_size - c->unique_size, c->unique_size);
 372   printf_filtered ("    Net memory savings:         ");
 373   print_percentage (c->total_size - c->structure_size, c->total_size);
 374   printf_filtered ("\n");
 375
 376   printf_filtered ("    Hash table size:           %3d\n", c->num_buckets);
 377   printf_filtered ("    Hash table expands:        %lu\n",
 378                    c->expand_count);
 379   printf_filtered ("    Hash table hashes:         %lu\n",
 380                    c->total_count + c->expand_hash_count);
 381   printf_filtered ("    Hash table population:     ");
 382   print_percentage (occupied_buckets, c->num_buckets);
 383   printf_filtered ("    Median hash chain length:  %3d\n",
 384                    median_chain_length);
 385   printf_filtered ("    Average hash chain length: ");
 386   if (c->num_buckets > 0)
 387     printf_filtered ("%3lu\n", c->unique_count / c->num_buckets);
 388   else
 389     printf_filtered ("(not applicable)\n");
 390   printf_filtered ("    Maximum hash chain length: %3d\n", max_chain_length);
 391   printf_filtered ("\n");
 392 }
 393
 394 int
 395 bcache_memory_used (struct bcache *bcache)
 396 {
 397   return obstack_memory_used (&bcache->cache);
 398 }