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 */ 217