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 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
  29 #include <stddef.h>
  30 #include <stdlib.h>
  31
  32 /* The type used to hold a single bcache string.  The user data is
  33    stored in d.data.  Since it can be any type, it needs to have the
  34    same alignment as the most strict alignment of any type on the host
  35    machine.  I don't know of any really correct way to do this in
  36    stock ANSI C, so just do it the same way obstack.h does.  */
  37
  38 struct bstring
  39 {
  40   struct bstring *next;
  41   size_t length;
  42
  43   union
  44   {
  45     char data[1];
  46     double dummy;
  47   }
  48   d;
  49 };
  50
  51
  52 /* The structure for a bcache itself.  The bcache is initialized, in
  53    bcache_xmalloc(), by filling it with zeros and then setting the
  54    corresponding obstack's malloc() and free() methods.  */
  55
  56 struct bcache
  57 {
  58   /* All the bstrings are allocated here.  */
  59   struct obstack cache;
  60
  61   /* How many hash buckets we're using.  */
  62   unsigned int num_buckets;
  63
  64   /* Hash buckets.  This table is allocated using malloc, so when we
  65      grow the table we can return the old table to the system.  */
  66   struct bstring **bucket;
  67
  68   /* Statistics.  */
  69   unsigned long unique_count;   /* number of unique strings */
  70   long total_count;     /* total number of strings cached, including dups */
  71   long unique_size;     /* size of unique strings, in bytes */
  72   long total_size;      /* total number of bytes cached, including dups */
  73   long structure_size;  /* total size of bcache, including infrastructure */
  74 };
  75
  76 /* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
  77  * and is better than the old one.
  78  */
  79 \f
  80 unsigned long
  81 hash(const void *addr, int length)
  82 {
  83                 const unsigned char *k, *e;
  84                 unsigned long h;
  85
  86                 k = (const unsigned char *)addr;
  87                 e = k+length;
  88                 for (h=0; k< e;++k)
  89                 {
  90                                 h *=16777619;
  91                                 h ^= *k;
  92                 }
  93                 return (h);
  94 }
  95 \f
  96 /* Growing the bcache's hash table.  */
  97
  98 /* If the average chain length grows beyond this, then we want to
  99    resize our hash table.  */
 100 #define CHAIN_LENGTH_THRESHOLD (5)
 101
 102 static void
 103 expand_hash_table (struct bcache *bcache)
 104 {
 105   /* A table of good hash table sizes.  Whenever we grow, we pick the
 106      next larger size from this table.  sizes[i] is close to 1 << (i+10),
 107      so we roughly double the table size each time.  After we fall off
 108      the end of this table, we just double.  Don't laugh --- there have
 109      been executables sighted with a gigabyte of debug info.  */
 110   static unsigned long sizes[] = {
 111     1021, 2053, 4099, 8191, 16381, 32771,
 112     65537, 131071, 262144, 524287, 1048573, 2097143,
 113     4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
 114     268435459, 536870923, 1073741827, 2147483659UL
 115   };
 116   unsigned int new_num_buckets;
 117   struct bstring **new_buckets;
 118   unsigned int i;
 119
 120   /* Find the next size.  */
 121   new_num_buckets = bcache->num_buckets * 2;
 122   for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
 123     if (sizes[i] > bcache->num_buckets)
 124       {
 125         new_num_buckets = sizes[i];
 126         break;
 127       }
 128
 129   /* Allocate the new table.  */
 130   {
 131     size_t new_size = new_num_buckets * sizeof (new_buckets[0]);
 132     new_buckets = (struct bstring **) xmalloc (new_size);
 133     memset (new_buckets, 0, new_size);
 134
 135     bcache->structure_size -= (bcache->num_buckets
 136                                * sizeof (bcache->bucket[0]));
 137     bcache->structure_size += new_size;
 138   }
 139
 140   /* Rehash all existing strings.  */
 141   for (i = 0; i < bcache->num_buckets; i++)
 142     {
 143       struct bstring *s, *next;
 144
 145       for (s = bcache->bucket[i]; s; s = next)
 146         {
 147           struct bstring **new_bucket;
 148           next = s->next;
 149
 150           new_bucket = &new_buckets[(hash (&s->d.data, s->length)
 151                                      % new_num_buckets)];
 152           s->next = *new_bucket;
 153           *new_bucket = s;
 154         }
 155     }
 156
 157   /* Plug in the new table.  */
 158   if (bcache->bucket)
 159     xfree (bcache->bucket);
 160   bcache->bucket = new_buckets;
 161   bcache->num_buckets = new_num_buckets;
 162 }
 163
 164 \f
 165 /* Looking up things in the bcache.  */
 166
 167 /* The number of bytes needed to allocate a struct bstring whose data
 168    is N bytes long.  */
 169 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
 170
 171 /* Find a copy of the LENGTH bytes at ADDR in BCACHE.  If BCACHE has
 172    never seen those bytes before, add a copy of them to BCACHE.  In
 173    either case, return a pointer to BCACHE's copy of that string.  */
 174 void *
 175 bcache (const void *addr, int length, struct bcache *bcache)
 176 {
 177   int hash_index;
 178   struct bstring *s;
 179
 180   /* If our average chain length is too high, expand the hash table.  */
 181   if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD)
 182     expand_hash_table (bcache);
 183
 184   bcache->total_count++;
 185   bcache->total_size += length;
 186
 187   hash_index = hash (addr, length) % bcache->num_buckets;
 188
 189   /* Search the hash bucket for a string identical to the caller's.  */
 190   for (s = bcache->bucket[hash_index]; s; s = s->next)
 191     if (s->length == length
 192         && ! memcmp (&s->d.data, addr, length))
 193       return &s->d.data;
 194
 195   /* The user's string isn't in the list.  Insert it after *ps.  */
 196   {
 197     struct bstring *new
 198       = obstack_alloc (&bcache->cache, BSTRING_SIZE (length));
 199     memcpy (&new->d.data, addr, length);
 200     new->length = length;
 201     new->next = bcache->bucket[hash_index];
 202     bcache->bucket[hash_index] = new;
 203
 204     bcache->unique_count++;
 205     bcache->unique_size += length;
 206     bcache->structure_size += BSTRING_SIZE (length);
 207
 208     return &new->d.data;
 209   }
 210 }
 211
 212 \f
 213 /* Allocating and freeing bcaches.  */
 214
 215 struct bcache *
 216 bcache_xmalloc (void)
 217 {
 218   /* Allocate the bcache pre-zeroed.  */
 219   struct bcache *b = XCALLOC (1, struct bcache);
 220   obstack_specify_allocation (&b->cache, 0, 0, xmalloc, xfree);
 221   return b;
 222 }
 223
 224 /* Free all the storage associated with BCACHE.  */
 225 void
 226 bcache_xfree (struct bcache *bcache)
 227 {
 228   if (bcache == NULL)
 229     return;
 230   obstack_free (&bcache->cache, 0);
 231   xfree (bcache->bucket);
 232   xfree (bcache);
 233 }
 234
 235
 236 \f
 237 /* Printing statistics.  */
 238
 239 static int
 240 compare_ints (const void *ap, const void *bp)
 241 {
 242   /* Because we know we're comparing two ints which are positive,
 243      there's no danger of overflow here.  */
 244   return * (int *) ap - * (int *) bp;
 245 }
 246
 247
 248 static void
 249 print_percentage (int portion, int total)
 250 {
 251   if (total == 0)
 252     printf_filtered ("(not applicable)\n");
 253   else
 254     printf_filtered ("%3d%%\n", portion * 100 / total);
 255 }
 256
 257
 258 /* Print statistics on BCACHE's memory usage and efficacity at
 259    eliminating duplication.  NAME should describe the kind of data
 260    BCACHE holds.  Statistics are printed using `printf_filtered' and
 261    its ilk.  */
 262 void
 263 print_bcache_statistics (struct bcache *c, char *type)
 264 {
 265   int occupied_buckets;
 266   int max_chain_length;
 267   int median_chain_length;
 268
 269   /* Count the number of occupied buckets, and measure chain lengths.  */
 270   {
 271     unsigned int b;
 272     int *chain_length
 273       = (int *) alloca (c->num_buckets * sizeof (*chain_length));
 274
 275     occupied_buckets = 0;
 276
 277     for (b = 0; b < c->num_buckets; b++)
 278       {
 279         struct bstring *s = c->bucket[b];
 280
 281         chain_length[b] = 0;
 282
 283         if (s)
 284           {
 285             occupied_buckets++;
 286
 287             while (s)
 288               {
 289                 chain_length[b]++;
 290                 s = s->next;
 291               }
 292           }
 293       }
 294
 295     /* To compute the median, we need the set of chain lengths sorted.  */
 296     qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
 297            compare_ints);
 298
 299     if (c->num_buckets > 0)
 300       {
 301         max_chain_length = chain_length[c->num_buckets - 1];
 302         median_chain_length = chain_length[c->num_buckets / 2];
 303       }
 304     else
 305       {
 306         max_chain_length = 0;
 307         median_chain_length = 0;
 308       }
 309   }
 310
 311   printf_filtered ("  Cached '%s' statistics:\n", type);
 312   printf_filtered ("    Total object count:  %ld\n", c->total_count);
 313   printf_filtered ("    Unique object count: %lu\n", c->unique_count);
 314   printf_filtered ("    Percentage of duplicates, by count: ");
 315   print_percentage (c->total_count - c->unique_count, c->total_count);
 316   printf_filtered ("\n");
 317
 318   printf_filtered ("    Total object size:   %ld\n", c->total_size);
 319   printf_filtered ("    Unique object size:  %ld\n", c->unique_size);
 320   printf_filtered ("    Percentage of duplicates, by size:  ");
 321   print_percentage (c->total_size - c->unique_size, c->total_size);
 322   printf_filtered ("\n");
 323
 324   printf_filtered ("    Total memory used by bcache, including overhead: %ld\n",
 325                    c->structure_size);
 326   printf_filtered ("    Percentage memory overhead: ");
 327   print_percentage (c->structure_size - c->unique_size, c->unique_size);
 328   printf_filtered ("    Net memory savings:         ");
 329   print_percentage (c->total_size - c->structure_size, c->total_size);
 330   printf_filtered ("\n");
 331
 332   printf_filtered ("    Hash table size:           %3d\n", c->num_buckets);
 333   printf_filtered ("    Hash table population:     ");
 334   print_percentage (occupied_buckets, c->num_buckets);
 335   printf_filtered ("    Median hash chain length:  %3d\n",
 336                    median_chain_length);
 337   printf_filtered ("    Average hash chain length: ");
 338   if (c->num_buckets > 0)
 339     printf_filtered ("%3lu\n", c->unique_count / c->num_buckets);
 340   else
 341     printf_filtered ("(not applicable)\n");
 342   printf_filtered ("    Maximum hash chain length: %3d\n", max_chain_length);
 343   printf_filtered ("\n");
 344 }
 345
 346 int
 347 bcache_memory_used (struct bcache *bcache)
 348 {
 349   return obstack_memory_used (&bcache->cache);
 350 }