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-2020 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 "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 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 (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++) 89 if (sizes[i] > m_num_buckets) 90 { 91 new_num_buckets = sizes[i]; 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[(m_hash_function (&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 = m_hash_function (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 && m_compare_function (&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 /* Compare the byte string at ADDR1 of lenght LENGHT to the 215 string at ADDR2. Return 1 if they are equal. */ 216 217 int 218 bcache::compare (const void *addr1, const void *addr2, int length) 219 { 220 return memcmp (addr1, addr2, length) == 0; 221 } 222 223 /* Free all the storage associated with BCACHE. */ 224 bcache::~bcache () 225 { 226 /* Only free the obstack if we actually initialized it. */ 227 if (m_total_count > 0) 228 obstack_free (&m_cache, 0); 229 xfree (m_bucket); 230 } 231 232 233 234 /* Printing statistics. */ 235 236 static void 237 print_percentage (int portion, int total) 238 { 239 if (total == 0) 240 /* i18n: Like "Percentage of duplicates, by count: (not applicable)". */ 241 printf_filtered (_("(not applicable)\n")); 242 else 243 printf_filtered ("%3d%%\n", (int) (portion * 100.0 / total)); 244 } 245 246 247 /* Print statistics on BCACHE's memory usage and efficacity at 248 eliminating duplication. NAME should describe the kind of data 249 BCACHE holds. Statistics are printed using `printf_filtered' and 250 its ilk. */ 251 void 252 bcache::print_statistics (const char *type) 253 { 254 int occupied_buckets; 255 int max_chain_length; 256 int median_chain_length; 257 int max_entry_size; 258 int median_entry_size; 259 260 /* Count the number of occupied buckets, tally the various string 261 lengths, and measure chain lengths. */ 262 { 263 unsigned int b; 264 int *chain_length = XCNEWVEC (int, m_num_buckets + 1); 265 int *entry_size = XCNEWVEC (int, m_unique_count + 1); 266 int stringi = 0; 267 268 occupied_buckets = 0; 269 270 for (b = 0; b < m_num_buckets; b++) 271 { 272 struct bstring *s = m_bucket[b]; 273 274 chain_length[b] = 0; 275 276 if (s) 277 { 278 occupied_buckets++; 279 280 while (s) 281 { 282 gdb_assert (b < m_num_buckets); 283 chain_length[b]++; 284 gdb_assert (stringi < m_unique_count); 285 entry_size[stringi++] = s->length; 286 s = s->next; 287 } 288 } 289 } 290 291 /* To compute the median, we need the set of chain lengths 292 sorted. */ 293 std::sort (chain_length, chain_length + m_num_buckets); 294 std::sort (entry_size, entry_size + m_unique_count); 295 296 if (m_num_buckets > 0) 297 { 298 max_chain_length = chain_length[m_num_buckets - 1]; 299 median_chain_length = chain_length[m_num_buckets / 2]; 300 } 301 else 302 { 303 max_chain_length = 0; 304 median_chain_length = 0; 305 } 306 if (m_unique_count > 0) 307 { 308 max_entry_size = entry_size[m_unique_count - 1]; 309 median_entry_size = entry_size[m_unique_count / 2]; 310 } 311 else 312 { 313 max_entry_size = 0; 314 median_entry_size = 0; 315 } 316 317 xfree (chain_length); 318 xfree (entry_size); 319 } 320 321 printf_filtered (_(" M_Cached '%s' statistics:\n"), type); 322 printf_filtered (_(" Total object count: %ld\n"), m_total_count); 323 printf_filtered (_(" Unique object count: %lu\n"), m_unique_count); 324 printf_filtered (_(" Percentage of duplicates, by count: ")); 325 print_percentage (m_total_count - m_unique_count, m_total_count); 326 printf_filtered ("\n"); 327 328 printf_filtered (_(" Total object size: %ld\n"), m_total_size); 329 printf_filtered (_(" Unique object size: %ld\n"), m_unique_size); 330 printf_filtered (_(" Percentage of duplicates, by size: ")); 331 print_percentage (m_total_size - m_unique_size, m_total_size); 332 printf_filtered ("\n"); 333 334 printf_filtered (_(" Max entry size: %d\n"), max_entry_size); 335 printf_filtered (_(" Average entry size: ")); 336 if (m_unique_count > 0) 337 printf_filtered ("%ld\n", m_unique_size / m_unique_count); 338 else 339 /* i18n: "Average entry size: (not applicable)". */ 340 printf_filtered (_("(not applicable)\n")); 341 printf_filtered (_(" Median entry size: %d\n"), median_entry_size); 342 printf_filtered ("\n"); 343 344 printf_filtered (_(" \ 345 Total memory used by bcache, including overhead: %ld\n"), 346 m_structure_size); 347 printf_filtered (_(" Percentage memory overhead: ")); 348 print_percentage (m_structure_size - m_unique_size, m_unique_size); 349 printf_filtered (_(" Net memory savings: ")); 350 print_percentage (m_total_size - m_structure_size, m_total_size); 351 printf_filtered ("\n"); 352 353 printf_filtered (_(" Hash table size: %3d\n"), 354 m_num_buckets); 355 printf_filtered (_(" Hash table expands: %lu\n"), 356 m_expand_count); 357 printf_filtered (_(" Hash table hashes: %lu\n"), 358 m_total_count + m_expand_hash_count); 359 printf_filtered (_(" Half hash misses: %lu\n"), 360 m_half_hash_miss_count); 361 printf_filtered (_(" Hash table population: ")); 362 print_percentage (occupied_buckets, m_num_buckets); 363 printf_filtered (_(" Median hash chain length: %3d\n"), 364 median_chain_length); 365 printf_filtered (_(" Average hash chain length: ")); 366 if (m_num_buckets > 0) 367 printf_filtered ("%3lu\n", m_unique_count / m_num_buckets); 368 else 369 /* i18n: "Average hash chain length: (not applicable)". */ 370 printf_filtered (_("(not applicable)\n")); 371 printf_filtered (_(" Maximum hash chain length: %3d\n"), 372 max_chain_length); 373 printf_filtered ("\n"); 374 } 375 376 int 377 bcache::memory_used () 378 { 379 if (m_total_count == 0) 380 return 0; 381 return obstack_memory_used (&m_cache); 382 } 383 384 } /* namespace gdb */ 385