1 /* Implement a cached obstack. 2 Written by Fred Fish <fnf@cygnus.com> 3 Rewritten by Jim Blandy <jimb@cygnus.com> 4 5 Copyright (C) 1999-2023 Free Software Foundation, Inc. 6 7 This file is part of GDB. 8 9 This program is free software; you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation; either version 3 of the License, or 12 (at your option) any later version. 13 14 This program is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 21 22 #include "defs.h" 23 #include "gdbsupport/gdb_obstack.h" 24 #include "bcache.h" 25 26 #include <algorithm> 27 28 namespace gdb { 29 30 /* The type used to hold a single bcache string. The user data is 31 stored in d.data. Since it can be any type, it needs to have the 32 same alignment as the most strict alignment of any type on the host 33 machine. I don't know of any really correct way to do this in 34 stock ANSI C, so just do it the same way obstack.h does. */ 35 36 struct bstring 37 { 38 /* Hash chain. */ 39 struct bstring *next; 40 /* Assume the data length is no more than 64k. */ 41 unsigned short length; 42 /* The half hash hack. This contains the upper 16 bits of the hash 43 value and is used as a pre-check when comparing two strings and 44 avoids the need to do length or memcmp calls. It proves to be 45 roughly 100% effective. */ 46 unsigned short half_hash; 47 48 union 49 { 50 char data[1]; 51 double dummy; 52 } 53 d; 54 }; 55 56 57 /* Growing the bcache's hash table. */ 58 59 /* If the average chain length grows beyond this, then we want to 60 resize our hash table. */ 61 #define CHAIN_LENGTH_THRESHOLD (5) 62 63 void 64 bcache::expand_hash_table () 65 { 66 /* A table of good hash table sizes. Whenever we grow, we pick the 67 next larger size from this table. sizes[i] is close to 1 << (i+10), 68 so we roughly double the table size each time. After we fall off 69 the end of this table, we just double. Don't laugh --- there have 70 been executables sighted with a gigabyte of debug info. */ 71 static const unsigned long sizes[] = { 72 1021, 2053, 4099, 8191, 16381, 32771, 73 65537, 131071, 262144, 524287, 1048573, 2097143, 74 4194301, 8388617, 16777213, 33554467, 67108859, 134217757, 75 268435459, 536870923, 1073741827, 2147483659UL 76 }; 77 unsigned int new_num_buckets; 78 struct bstring **new_buckets; 79 unsigned int i; 80 81 /* Count the stats. Every unique item needs to be re-hashed and 82 re-entered. */ 83 m_expand_count++; 84 m_expand_hash_count += m_unique_count; 85 86 /* Find the next size. */ 87 new_num_buckets = m_num_buckets * 2; 88 for (unsigned long a_size : sizes) 89 if (a_size > m_num_buckets) 90 { 91 new_num_buckets = a_size; 92 break; 93 } 94 95 /* Allocate the new table. */ 96 { 97 size_t new_size = new_num_buckets * sizeof (new_buckets[0]); 98 99 new_buckets = (struct bstring **) xmalloc (new_size); 100 memset (new_buckets, 0, new_size); 101 102 m_structure_size -= m_num_buckets * sizeof (m_bucket[0]); 103 m_structure_size += new_size; 104 } 105 106 /* Rehash all existing strings. */ 107 for (i = 0; i < m_num_buckets; i++) 108 { 109 struct bstring *s, *next; 110 111 for (s = m_bucket[i]; s; s = next) 112 { 113 struct bstring **new_bucket; 114 next = s->next; 115 116 new_bucket = &new_buckets[(this->hash (&s->d.data, s->length) 117 % new_num_buckets)]; 118 s->next = *new_bucket; 119 *new_bucket = s; 120 } 121 } 122 123 /* Plug in the new table. */ 124 xfree (m_bucket); 125 m_bucket = new_buckets; 126 m_num_buckets = new_num_buckets; 127 } 128 129 130 /* Looking up things in the bcache. */ 131 132 /* The number of bytes needed to allocate a struct bstring whose data 133 is N bytes long. */ 134 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n)) 135 136 /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has 137 never seen those bytes before, add a copy of them to BCACHE. In 138 either case, return a pointer to BCACHE's copy of that string. If 139 optional ADDED is not NULL, return 1 in case of new entry or 0 if 140 returning an old entry. */ 141 142 const void * 143 bcache::insert (const void *addr, int length, bool *added) 144 { 145 unsigned long full_hash; 146 unsigned short half_hash; 147 int hash_index; 148 struct bstring *s; 149 150 if (added != nullptr) 151 *added = false; 152 153 /* Lazily initialize the obstack. This can save quite a bit of 154 memory in some cases. */ 155 if (m_total_count == 0) 156 { 157 /* We could use obstack_specify_allocation here instead, but 158 gdb_obstack.h specifies the allocation/deallocation 159 functions. */ 160 obstack_init (&m_cache); 161 } 162 163 /* If our average chain length is too high, expand the hash table. */ 164 if (m_unique_count >= m_num_buckets * CHAIN_LENGTH_THRESHOLD) 165 expand_hash_table (); 166 167 m_total_count++; 168 m_total_size += length; 169 170 full_hash = this->hash (addr, length); 171 172 half_hash = (full_hash >> 16); 173 hash_index = full_hash % m_num_buckets; 174 175 /* Search the hash m_bucket for a string identical to the caller's. 176 As a short-circuit first compare the upper part of each hash 177 values. */ 178 for (s = m_bucket[hash_index]; s; s = s->next) 179 { 180 if (s->half_hash == half_hash) 181 { 182 if (s->length == length 183 && this->compare (&s->d.data, addr, length)) 184 return &s->d.data; 185 else 186 m_half_hash_miss_count++; 187 } 188 } 189 190 /* The user's string isn't in the list. Insert it after *ps. */ 191 { 192 struct bstring *newobj 193 = (struct bstring *) obstack_alloc (&m_cache, 194 BSTRING_SIZE (length)); 195 196 memcpy (&newobj->d.data, addr, length); 197 newobj->length = length; 198 newobj->next = m_bucket[hash_index]; 199 newobj->half_hash = half_hash; 200 m_bucket[hash_index] = newobj; 201 202 m_unique_count++; 203 m_unique_size += length; 204 m_structure_size += BSTRING_SIZE (length); 205 206 if (added != nullptr) 207 *added = true; 208 209 return &newobj->d.data; 210 } 211 } 212 213 214 /* See bcache.h. */ 215 216 unsigned long 217 bcache::hash (const void *addr, int length) 218 { 219 return fast_hash (addr, length, 0); 220 } 221 222 /* See bcache.h. */ 223 224 int 225 bcache::compare (const void *left, const void *right, int length) 226 { 227 return memcmp (left, right, length) == 0; 228 } 229 230 /* Free all the storage associated with BCACHE. */ 231 bcache::~bcache () 232 { 233 /* Only free the obstack if we actually initialized it. */ 234 if (m_total_count > 0) 235 obstack_free (&m_cache, 0); 236 xfree (m_bucket); 237 } 238 239 240 241 /* Printing statistics. */ 242 243 static void 244 print_percentage (int portion, int total) 245 { 246 if (total == 0) 247 /* i18n: Like "Percentage of duplicates, by count: (not applicable)". */ 248 gdb_printf (_("(not applicable)\n")); 249 else 250 gdb_printf ("%3d%%\n", (int) (portion * 100.0 / total)); 251 } 252 253 254 /* Print statistics on BCACHE's memory usage and efficacity at 255 eliminating duplication. NAME should describe the kind of data 256 BCACHE holds. Statistics are printed using `gdb_printf' and 257 its ilk. */ 258 void 259 bcache::print_statistics (const char *type) 260 { 261 int occupied_buckets; 262 int max_chain_length; 263 int median_chain_length; 264 int max_entry_size; 265 int median_entry_size; 266 267 /* Count the number of occupied buckets, tally the various string 268 lengths, and measure chain lengths. */ 269 { 270 unsigned int b; 271 int *chain_length = XCNEWVEC (int, m_num_buckets + 1); 272 int *entry_size = XCNEWVEC (int, m_unique_count + 1); 273 int stringi = 0; 274 275 occupied_buckets = 0; 276 277 for (b = 0; b < m_num_buckets; b++) 278 { 279 struct bstring *s = m_bucket[b]; 280 281 chain_length[b] = 0; 282 283 if (s) 284 { 285 occupied_buckets++; 286 287 while (s) 288 { 289 gdb_assert (b < m_num_buckets); 290 chain_length[b]++; 291 gdb_assert (stringi < m_unique_count); 292 entry_size[stringi++] = s->length; 293 s = s->next; 294 } 295 } 296 } 297 298 /* To compute the median, we need the set of chain lengths 299 sorted. */ 300 std::sort (chain_length, chain_length + m_num_buckets); 301 std::sort (entry_size, entry_size + m_unique_count); 302 303 if (m_num_buckets > 0) 304 { 305 max_chain_length = chain_length[m_num_buckets - 1]; 306 median_chain_length = chain_length[m_num_buckets / 2]; 307 } 308 else 309 { 310 max_chain_length = 0; 311 median_chain_length = 0; 312 } 313 if (m_unique_count > 0) 314 { 315 max_entry_size = entry_size[m_unique_count - 1]; 316 median_entry_size = entry_size[m_unique_count / 2]; 317 } 318 else 319 { 320 max_entry_size = 0; 321 median_entry_size = 0; 322 } 323 324 xfree (chain_length); 325 xfree (entry_size); 326 } 327 328 gdb_printf (_(" M_Cached '%s' statistics:\n"), type); 329 gdb_printf (_(" Total object count: %ld\n"), m_total_count); 330 gdb_printf (_(" Unique object count: %lu\n"), m_unique_count); 331 gdb_printf (_(" Percentage of duplicates, by count: ")); 332 print_percentage (m_total_count - m_unique_count, m_total_count); 333 gdb_printf ("\n"); 334 335 gdb_printf (_(" Total object size: %ld\n"), m_total_size); 336 gdb_printf (_(" Unique object size: %ld\n"), m_unique_size); 337 gdb_printf (_(" Percentage of duplicates, by size: ")); 338 print_percentage (m_total_size - m_unique_size, m_total_size); 339 gdb_printf ("\n"); 340 341 gdb_printf (_(" Max entry size: %d\n"), max_entry_size); 342 gdb_printf (_(" Average entry size: ")); 343 if (m_unique_count > 0) 344 gdb_printf ("%ld\n", m_unique_size / m_unique_count); 345 else 346 /* i18n: "Average entry size: (not applicable)". */ 347 gdb_printf (_("(not applicable)\n")); 348 gdb_printf (_(" Median entry size: %d\n"), median_entry_size); 349 gdb_printf ("\n"); 350 351 gdb_printf (_(" \ 352 Total memory used by bcache, including overhead: %ld\n"), 353 m_structure_size); 354 gdb_printf (_(" Percentage memory overhead: ")); 355 print_percentage (m_structure_size - m_unique_size, m_unique_size); 356 gdb_printf (_(" Net memory savings: ")); 357 print_percentage (m_total_size - m_structure_size, m_total_size); 358 gdb_printf ("\n"); 359 360 gdb_printf (_(" Hash table size: %3d\n"), 361 m_num_buckets); 362 gdb_printf (_(" Hash table expands: %lu\n"), 363 m_expand_count); 364 gdb_printf (_(" Hash table hashes: %lu\n"), 365 m_total_count + m_expand_hash_count); 366 gdb_printf (_(" Half hash misses: %lu\n"), 367 m_half_hash_miss_count); 368 gdb_printf (_(" Hash table population: ")); 369 print_percentage (occupied_buckets, m_num_buckets); 370 gdb_printf (_(" Median hash chain length: %3d\n"), 371 median_chain_length); 372 gdb_printf (_(" Average hash chain length: ")); 373 if (m_num_buckets > 0) 374 gdb_printf ("%3lu\n", m_unique_count / m_num_buckets); 375 else 376 /* i18n: "Average hash chain length: (not applicable)". */ 377 gdb_printf (_("(not applicable)\n")); 378 gdb_printf (_(" Maximum hash chain length: %3d\n"), 379 max_chain_length); 380 gdb_printf ("\n"); 381 } 382 383 int 384 bcache::memory_used () 385 { 386 if (m_total_count == 0) 387 return 0; 388 return obstack_memory_used (&m_cache); 389 } 390 391 } /* namespace gdb */ 392