gdb/bcache.c

   1 /* Implement a cached obstack.
   2    Written by Fred Fish (fnf@cygnus.com)
   3    Copyright 1995 Free Software Foundation, Inc.
   4
   5 This file is part of GDB.
   6
   7 This program is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 This program is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program; if not, write to the Free Software
  19 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  20
  21 #include "defs.h"
  22 #include "obstack.h"
  23 #include "bcache.h"
  24 #include "gdb_string.h"         /* For memcpy declaration */
  25
  26 static unsigned int hash PARAMS ((void *, int));
  27 static void *lookup_cache PARAMS ((void *, int, int, struct bcache *));
  28
  29 /* FIXME:  Incredibly simplistic hash generator.  Probably way too expensive
  30  (consider long strings) and unlikely to have good distribution across hash
  31  values for typical input. */
  32
  33 static unsigned int
  34 hash (bytes, count)
  35      void *bytes;
  36      int count;
  37 {
  38   unsigned int len;
  39   unsigned long hashval;
  40   unsigned int c;
  41   const unsigned char *data = bytes;
  42
  43   hashval = 0;
  44   len = 0;
  45   while (count-- > 0)
  46     {
  47       c = *data++;
  48       hashval += c + (c << 17);
  49       hashval ^= hashval >> 2;
  50       ++len;
  51     }
  52   hashval += len + (len << 17);
  53   hashval ^= hashval >> 2;
  54   return (hashval % BCACHE_HASHSIZE);
  55 }
  56
  57 static void *
  58 lookup_cache (bytes, count, hashval, bcachep)
  59      void *bytes;
  60      int count;
  61      int hashval;
  62      struct bcache *bcachep;
  63 {
  64   void *location = NULL;
  65   struct hashlink **hashtablep;
  66   struct hashlink *linkp;
  67
  68   hashtablep = bcachep -> indextable[count];
  69   if (hashtablep != NULL)
  70     {
  71       linkp = hashtablep[hashval];
  72       while (linkp != NULL)
  73         {
  74           if (memcmp (BCACHE_DATA (linkp), bytes, count) == 0)
  75             {
  76               location = BCACHE_DATA (linkp);
  77               break;
  78             }
  79           linkp = linkp -> next;
  80         }
  81     }
  82   return (location);
  83 }
  84
  85 void *
  86 bcache (bytes, count, bcachep)
  87      void *bytes;
  88      int count;
  89      struct bcache *bcachep;
  90 {
  91   int hashval;
  92   void *location;
  93   struct hashlink *newlink;
  94   struct hashlink **linkpp;
  95   struct hashlink ***hashtablepp;
  96
  97   if (count >= BCACHE_MAXLENGTH)
  98     {
  99       /* Rare enough to just stash unique copies */
 100       location = (void *) obstack_alloc (&bcachep->cache, count);
 101       bcachep -> cache_bytes += count;
 102       memcpy (location, bytes, count);
 103       bcachep -> bcache_overflows++;
 104     }
 105   else
 106     {
 107       hashval = hash (bytes, count);
 108       location = lookup_cache (bytes, count, hashval, bcachep);
 109       if (location != NULL)
 110         {
 111           bcachep -> cache_savings += count;
 112           bcachep -> cache_hits++;
 113         }
 114       else
 115         {
 116           bcachep -> cache_misses++;
 117           hashtablepp = &bcachep -> indextable[count];
 118           if (*hashtablepp == NULL)
 119             {
 120               *hashtablepp = (struct hashlink **)
 121                 obstack_alloc (&bcachep->cache, BCACHE_HASHSIZE * sizeof (struct hashlink *));
 122               bcachep -> cache_bytes += BCACHE_HASHSIZE * sizeof (struct hashlink *);
 123               memset (*hashtablepp, 0, BCACHE_HASHSIZE * sizeof (struct hashlink *));
 124             }
 125           linkpp = &(*hashtablepp)[hashval];
 126           newlink = (struct hashlink *)
 127             obstack_alloc (&bcachep->cache, BCACHE_DATA_ALIGNMENT + count);
 128           bcachep -> cache_bytes += BCACHE_DATA_ALIGNMENT + count;
 129           memcpy (BCACHE_DATA (newlink), bytes, count);
 130           newlink -> next = *linkpp;
 131           *linkpp = newlink;
 132           location = BCACHE_DATA (newlink);
 133         }
 134     }
 135   return (location);
 136 }
 137
 138 #if MAINTENANCE_CMDS
 139
 140 void
 141 print_bcache_statistics (bcachep, id)
 142      struct bcache *bcachep;
 143      char *id;
 144 {
 145   struct hashlink **hashtablep;
 146   struct hashlink *linkp;
 147   int tidx, tcount, hidx, hcount, lcount, lmax, temp, lmaxt, lmaxh;
 148
 149   for (lmax = lcount = tcount = hcount = tidx = 0; tidx < BCACHE_MAXLENGTH; tidx++)
 150     {
 151       hashtablep = bcachep -> indextable[tidx];
 152       if (hashtablep != NULL)
 153         {
 154           tcount++;
 155           for (hidx = 0; hidx < BCACHE_HASHSIZE; hidx++)
 156             {
 157               linkp = hashtablep[hidx];
 158               if (linkp != NULL)
 159                 {
 160                   hcount++;
 161                   for (temp = 0; linkp != NULL; linkp = linkp -> next)
 162                     {
 163                       lcount++;
 164                       temp++;
 165                     }
 166                   if (temp > lmax)
 167                     {
 168                       lmax = temp;
 169                       lmaxt = tidx;
 170                       lmaxh = hidx;
 171                     }
 172                 }
 173             }
 174         }
 175     }
 176   printf_filtered ("  Cached '%s' statistics:\n", id);
 177   printf_filtered ("    Cache hits: %d\n", bcachep -> cache_hits);
 178   printf_filtered ("    Cache misses: %d\n", bcachep -> cache_misses);
 179   printf_filtered ("    Cache hit ratio: ");
 180   if (bcachep -> cache_hits + bcachep -> cache_misses > 0)
 181     {
 182       printf_filtered ("%d%%\n", ((bcachep -> cache_hits) * 100) /
 183                        (bcachep -> cache_hits + bcachep -> cache_misses));
 184     }
 185   else
 186     {
 187       printf_filtered ("(not applicable)\n");
 188     }
 189   printf_filtered ("    Space used for caching: %d\n", bcachep -> cache_bytes);
 190   printf_filtered ("    Space saved by cache hits: %d\n", bcachep -> cache_savings);
 191   printf_filtered ("    Number of bcache overflows: %d\n", bcachep -> bcache_overflows);
 192   printf_filtered ("    Number of index buckets used: %d\n", tcount);
 193   printf_filtered ("    Number of hash table buckets used: %d\n", hcount);
 194   printf_filtered ("    Number of chained items: %d\n", lcount);
 195   printf_filtered ("    Average hash table population: ");
 196   if (tcount > 0)
 197     {
 198       printf_filtered ("%d%%\n", (hcount * 100) / (tcount * BCACHE_HASHSIZE));
 199     }
 200   else
 201     {
 202       printf_filtered ("(not applicable)\n");
 203     }
 204   printf_filtered ("    Average chain length ");
 205   if (hcount > 0)
 206     {
 207       printf_filtered ("%d\n", lcount / hcount);
 208     }
 209   else
 210     {
 211       printf_filtered ("(not applicable)\n");
 212     }
 213   printf_filtered ("    Maximum chain length %d at %d:%d\n", lmax, lmaxt, lmaxh);
 214 }
 215
 216 #endif  /* MAINTENANCE_CMDS */