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    Copyright 1999, 2000 Free Software Foundation, Inc.
   5
   6    This file is part of GDB.
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 59 Temple Place - Suite 330,
  21    Boston, MA 02111-1307, USA.  */
  22
  23 #include <stddef.h>
  24 #include <stdlib.h>
  25
  26 #include "defs.h"
  27 #include "obstack.h"
  28 #include "bcache.h"
  29 #include "gdb_string.h"         /* For memcpy declaration */
  30
  31 /* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
  32  * and is better than the old one.
  33  */
  34 \f
  35 unsigned long
  36 hash(void *addr, int length)
  37 {
  38                 const unsigned char *k, *e;
  39                 unsigned long h;
  40
  41                 k = (const unsigned char *)addr;
  42                 e = k+length;
  43                 for (h=0; k< e;++k)
  44                 {
  45                                 h *=16777619;
  46                                 h ^= *k;
  47                 }
  48                 return (h);
  49 }
  50 \f
  51 /* Growing the bcache's hash table.  */
  52
  53 /* If the average chain length grows beyond this, then we want to
  54    resize our hash table.  */
  55 #define CHAIN_LENGTH_THRESHOLD (5)
  56
  57 static void
  58 expand_hash_table (struct bcache *bcache)
  59 {
  60   /* A table of good hash table sizes.  Whenever we grow, we pick the
  61      next larger size from this table.  sizes[i] is close to 1 << (i+10),
  62      so we roughly double the table size each time.  After we fall off
  63      the end of this table, we just double.  Don't laugh --- there have
  64      been executables sighted with a gigabyte of debug info.  */
  65   static unsigned long sizes[] = {
  66     1021, 2053, 4099, 8191, 16381, 32771,
  67     65537, 131071, 262144, 524287, 1048573, 2097143,
  68     4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
  69     268435459, 536870923, 1073741827, 2147483659UL
  70   };
  71   unsigned int new_num_buckets;
  72   struct bstring **new_buckets;
  73   unsigned int i;
  74
  75   /* Find the next size.  */
  76   new_num_buckets = bcache->num_buckets * 2;
  77   for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
  78     if (sizes[i] > bcache->num_buckets)
  79       {
  80         new_num_buckets = sizes[i];
  81         break;
  82       }
  83
  84   /* Allocate the new table.  */
  85   {
  86     size_t new_size = new_num_buckets * sizeof (new_buckets[0]);
  87     new_buckets = (struct bstring **) xmalloc (new_size);
  88     memset (new_buckets, 0, new_size);
  89
  90     bcache->structure_size -= (bcache->num_buckets
  91                                * sizeof (bcache->bucket[0]));
  92     bcache->structure_size += new_size;
  93   }
  94
  95   /* Rehash all existing strings.  */
  96   for (i = 0; i < bcache->num_buckets; i++)
  97     {
  98       struct bstring *s, *next;
  99
 100       for (s = bcache->bucket[i]; s; s = next)
 101         {
 102           struct bstring **new_bucket;
 103           next = s->next;
 104
 105           new_bucket = &new_buckets[(hash (&s->d.data, s->length)
 106                                      % new_num_buckets)];
 107           s->next = *new_bucket;
 108           *new_bucket = s;
 109         }
 110     }
 111
 112   /* Plug in the new table.  */
 113   if (bcache->bucket)
 114     xfree (bcache->bucket);
 115   bcache->bucket = new_buckets;
 116   bcache->num_buckets = new_num_buckets;
 117 }
 118
 119 \f
 120 /* Looking up things in the bcache.  */
 121
 122 /* The number of bytes needed to allocate a struct bstring whose data
 123    is N bytes long.  */
 124 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
 125
 126 /* Find a copy of the LENGTH bytes at ADDR in BCACHE.  If BCACHE has
 127    never seen those bytes before, add a copy of them to BCACHE.  In
 128    either case, return a pointer to BCACHE's copy of that string.  */
 129 void *
 130 bcache (void *addr, int length, struct bcache *bcache)
 131 {
 132   int hash_index;
 133   struct bstring *s;
 134
 135   /* If our average chain length is too high, expand the hash table.  */
 136   if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD)
 137     expand_hash_table (bcache);
 138
 139   bcache->total_count++;
 140   bcache->total_size += length;
 141
 142   hash_index = hash (addr, length) % bcache->num_buckets;
 143
 144   /* Search the hash bucket for a string identical to the caller's.  */
 145   for (s = bcache->bucket[hash_index]; s; s = s->next)
 146     if (s->length == length
 147         && ! memcmp (&s->d.data, addr, length))
 148       return &s->d.data;
 149
 150   /* The user's string isn't in the list.  Insert it after *ps.  */
 151   {
 152     struct bstring *new
 153       = obstack_alloc (&bcache->cache, BSTRING_SIZE (length));
 154     memcpy (&new->d.data, addr, length);
 155     new->length = length;
 156     new->next = bcache->bucket[hash_index];
 157     bcache->bucket[hash_index] = new;
 158
 159     bcache->unique_count++;
 160     bcache->unique_size += length;
 161     bcache->structure_size += BSTRING_SIZE (length);
 162
 163     return &new->d.data;
 164   }
 165 }
 166
 167 \f
 168 /* Freeing bcaches.  */
 169
 170 /* Free all the storage associated with BCACHE.  */
 171 void
 172 free_bcache (struct bcache *bcache)
 173 {
 174   obstack_free (&bcache->cache, 0);
 175   if (bcache->bucket)
 176     xfree (bcache->bucket);
 177
 178   /* This isn't necessary, but at least the bcache is always in a
 179      consistent state.  */
 180   memset (bcache, 0, sizeof (*bcache));
 181 }
 182
 183
 184 \f
 185 /* Printing statistics.  */
 186
 187 static int
 188 compare_ints (const void *ap, const void *bp)
 189 {
 190   /* Because we know we're comparing two ints which are positive,
 191      there's no danger of overflow here.  */
 192   return * (int *) ap - * (int *) bp;
 193 }
 194
 195
 196 static void
 197 print_percentage (int portion, int total)
 198 {
 199   if (total == 0)
 200     printf_filtered ("(not applicable)\n");
 201   else
 202     printf_filtered ("%3d%%\n", portion * 100 / total);
 203 }
 204
 205
 206 /* Print statistics on BCACHE's memory usage and efficacity at
 207    eliminating duplication.  NAME should describe the kind of data
 208    BCACHE holds.  Statistics are printed using `printf_filtered' and
 209    its ilk.  */
 210 void
 211 print_bcache_statistics (struct bcache *c, char *type)
 212 {
 213   int occupied_buckets;
 214   int max_chain_length;
 215   int median_chain_length;
 216
 217   /* Count the number of occupied buckets, and measure chain lengths.  */
 218   {
 219     unsigned int b;
 220     int *chain_length
 221       = (int *) alloca (c->num_buckets * sizeof (*chain_length));
 222
 223     occupied_buckets = 0;
 224
 225     for (b = 0; b < c->num_buckets; b++)
 226       {
 227         struct bstring *s = c->bucket[b];
 228
 229         chain_length[b] = 0;
 230
 231         if (s)
 232           {
 233             occupied_buckets++;
 234
 235             while (s)
 236               {
 237                 chain_length[b]++;
 238                 s = s->next;
 239               }
 240           }
 241       }
 242
 243     /* To compute the median, we need the set of chain lengths sorted.  */
 244     qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
 245            compare_ints);
 246
 247     if (c->num_buckets > 0)
 248       {
 249         max_chain_length = chain_length[c->num_buckets - 1];
 250         median_chain_length = chain_length[c->num_buckets / 2];
 251       }
 252     else
 253       {
 254         max_chain_length = 0;
 255         median_chain_length = 0;
 256       }
 257   }
 258
 259   printf_filtered ("  Cached '%s' statistics:\n", type);
 260   printf_filtered ("    Total object count:  %ld\n", c->total_count);
 261   printf_filtered ("    Unique object count: %lu\n", c->unique_count);
 262   printf_filtered ("    Percentage of duplicates, by count: ");
 263   print_percentage (c->total_count - c->unique_count, c->total_count);
 264   printf_filtered ("\n");
 265
 266   printf_filtered ("    Total object size:   %ld\n", c->total_size);
 267   printf_filtered ("    Unique object size:  %ld\n", c->unique_size);
 268   printf_filtered ("    Percentage of duplicates, by size:  ");
 269   print_percentage (c->total_size - c->unique_size, c->total_size);
 270   printf_filtered ("\n");
 271
 272   printf_filtered ("    Total memory used by bcache, including overhead: %ld\n",
 273                    c->structure_size);
 274   printf_filtered ("    Percentage memory overhead: ");
 275   print_percentage (c->structure_size - c->unique_size, c->unique_size);
 276   printf_filtered ("    Net memory savings:         ");
 277   print_percentage (c->total_size - c->structure_size, c->total_size);
 278   printf_filtered ("\n");
 279
 280   printf_filtered ("    Hash table size:           %3d\n", c->num_buckets);
 281   printf_filtered ("    Hash table population:     ");
 282   print_percentage (occupied_buckets, c->num_buckets);
 283   printf_filtered ("    Median hash chain length:  %3d\n",
 284                    median_chain_length);
 285   printf_filtered ("    Average hash chain length: ");
 286   if (c->num_buckets > 0)
 287     printf_filtered ("%3lu\n", c->unique_count / c->num_buckets);
 288   else
 289     printf_filtered ("(not applicable)\n");
 290   printf_filtered ("    Maximum hash chain length: %3d\n", max_chain_length);
 291   printf_filtered ("\n");
 292 }