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