gdb/bcache.c

   1 /* Implement a cached obstack.
   2    Written by Fred Fish (fnf@cygnus.com)
   3    Copyright 1995, 1998 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 /* Prototypes for local functions. */
  27
  28 static unsigned int hash PARAMS ((void *, int));
  29
  30 static void *lookup_cache PARAMS ((void *, int, int, struct bcache *));
  31
  32 /* FIXME:  Incredibly simplistic hash generator.  Probably way too expensive
  33  (consider long strings) and unlikely to have good distribution across hash
  34  values for typical input. */
  35
  36 static unsigned int
  37 hash (bytes, count)
  38      void *bytes;
  39      int count;
  40 {
  41   unsigned int len;
  42   unsigned long hashval;
  43   unsigned int c;
  44   const unsigned char *data = bytes;
  45
  46   hashval = 0;
  47   len = 0;
  48   while (count-- > 0)
  49     {
  50       c = *data++;
  51       hashval += c + (c << 17);
  52       hashval ^= hashval >> 2;
  53       ++len;
  54     }
  55   hashval += len + (len << 17);
  56   hashval ^= hashval >> 2;
  57   return (hashval % BCACHE_HASHSIZE);
  58 }
  59
  60 static void *
  61 lookup_cache (bytes, count, hashval, bcachep)
  62      void *bytes;
  63      int count;
  64      int hashval;
  65      struct bcache *bcachep;
  66 {
  67   void *location = NULL;
  68   struct hashlink **hashtablep;
  69   struct hashlink *linkp;
  70
  71   hashtablep = bcachep -> indextable[count];
  72   if (hashtablep != NULL)
  73     {
  74       linkp = hashtablep[hashval];
  75       while (linkp != NULL)
  76         {
  77           if (memcmp (BCACHE_DATA (linkp), bytes, count) == 0)
  78             {
  79               location = BCACHE_DATA (linkp);
  80               break;
  81             }
  82           linkp = linkp -> next;
  83         }
  84     }
  85   return (location);
  86 }
  87
  88 void *
  89 bcache (bytes, count, bcachep)
  90      void *bytes;
  91      int count;
  92      struct bcache *bcachep;
  93 {
  94   int hashval;
  95   void *location;
  96   struct hashlink *newlink;
  97   struct hashlink **linkpp;
  98   struct hashlink ***hashtablepp;
  99
 100   if (count >= BCACHE_MAXLENGTH)
 101     {
 102       /* Rare enough to just stash unique copies */
 103       location = (void *) obstack_alloc (&bcachep->cache, count);
 104       bcachep -> cache_bytes += count;
 105       memcpy (location, bytes, count);
 106       bcachep -> bcache_overflows++;
 107     }
 108   else
 109     {
 110       hashval = hash (bytes, count);
 111       location = lookup_cache (bytes, count, hashval, bcachep);
 112       if (location != NULL)
 113         {
 114           bcachep -> cache_savings += count;
 115           bcachep -> cache_hits++;
 116         }
 117       else
 118         {
 119           bcachep -> cache_misses++;
 120           hashtablepp = &bcachep -> indextable[count];
 121           if (*hashtablepp == NULL)
 122             {
 123               *hashtablepp = (struct hashlink **)
 124                 obstack_alloc (&bcachep->cache, BCACHE_HASHSIZE * sizeof (struct hashlink *));
 125               bcachep -> cache_bytes += BCACHE_HASHSIZE * sizeof (struct hashlink *);
 126               memset (*hashtablepp, 0, BCACHE_HASHSIZE * sizeof (struct hashlink *));
 127             }
 128           linkpp = &(*hashtablepp)[hashval];
 129           newlink = (struct hashlink *)
 130             obstack_alloc (&bcachep->cache, BCACHE_DATA_ALIGNMENT + count);
 131           bcachep -> cache_bytes += BCACHE_DATA_ALIGNMENT + count;
 132           memcpy (BCACHE_DATA (newlink), bytes, count);
 133           newlink -> next = *linkpp;
 134           *linkpp = newlink;
 135           location = BCACHE_DATA (newlink);
 136         }
 137     }
 138   return (location);
 139 }
 140
 141 void
 142 print_bcache_statistics (bcachep, id)
 143      struct bcache *bcachep;
 144      char *id;
 145 {
 146   struct hashlink **hashtablep;
 147   struct hashlink *linkp;
 148   int tidx, tcount, hidx, hcount, lcount, lmax, temp, lmaxt, lmaxh;
 149
 150   for (lmax = lcount = tcount = hcount = tidx = 0; tidx < BCACHE_MAXLENGTH; tidx++)
 151     {
 152       hashtablep = bcachep -> indextable[tidx];
 153       if (hashtablep != NULL)
 154         {
 155           tcount++;
 156           for (hidx = 0; hidx < BCACHE_HASHSIZE; hidx++)
 157             {
 158               linkp = hashtablep[hidx];
 159               if (linkp != NULL)
 160                 {
 161                   hcount++;
 162                   for (temp = 0; linkp != NULL; linkp = linkp -> next)
 163                     {
 164                       lcount++;
 165                       temp++;
 166                     }
 167                   if (temp > lmax)
 168                     {
 169                       lmax = temp;
 170                       lmaxt = tidx;
 171                       lmaxh = hidx;
 172                     }
 173                 }
 174             }
 175         }
 176     }
 177   printf_filtered ("  Cached '%s' statistics:\n", id);
 178   printf_filtered ("    Cache hits: %d\n", bcachep -> cache_hits);
 179   printf_filtered ("    Cache misses: %d\n", bcachep -> cache_misses);
 180   printf_filtered ("    Cache hit ratio: ");
 181   if (bcachep -> cache_hits + bcachep -> cache_misses > 0)
 182     {
 183       printf_filtered ("%d%%\n", ((bcachep -> cache_hits) * 100) /
 184                        (bcachep -> cache_hits + bcachep -> cache_misses));
 185     }
 186   else
 187     {
 188       printf_filtered ("(not applicable)\n");
 189     }
 190   printf_filtered ("    Space used for caching: %d\n", bcachep -> cache_bytes);
 191   printf_filtered ("    Space saved by cache hits: %d\n", bcachep -> cache_savings);
 192   printf_filtered ("    Number of bcache overflows: %d\n", bcachep -> bcache_overflows);
 193   printf_filtered ("    Number of index buckets used: %d\n", tcount);
 194   printf_filtered ("    Number of hash table buckets used: %d\n", hcount);
 195   printf_filtered ("    Number of chained items: %d\n", lcount);
 196   printf_filtered ("    Average hash table population: ");
 197   if (tcount > 0)
 198     {
 199       printf_filtered ("%d%%\n", (hcount * 100) / (tcount * BCACHE_HASHSIZE));
 200     }
 201   else
 202     {
 203       printf_filtered ("(not applicable)\n");
 204     }
 205   printf_filtered ("    Average chain length ");
 206   if (hcount > 0)
 207     {
 208       printf_filtered ("%d\n", lcount / hcount);
 209     }
 210   else
 211     {
 212       printf_filtered ("(not applicable)\n");
 213     }
 214   printf_filtered ("    Maximum chain length %d at %d:%d\n", lmax, lmaxt, lmaxh);
 215 }