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