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