GDB (xrefs)
/tmp/gdb-7.10/gdb/bcache.c
Go to the documentation of this file.
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-2015 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 /* The type used to hold a single bcache string. The user data is
27  stored in d.data. Since it can be any type, it needs to have the
28  same alignment as the most strict alignment of any type on the host
29  machine. I don't know of any really correct way to do this in
30  stock ANSI C, so just do it the same way obstack.h does. */
31 
32 struct bstring
33 {
34  /* Hash chain. */
35  struct bstring *next;
36  /* Assume the data length is no more than 64k. */
37  unsigned short length;
38  /* The half hash hack. This contains the upper 16 bits of the hash
39  value and is used as a pre-check when comparing two strings and
40  avoids the need to do length or memcmp calls. It proves to be
41  roughly 100% effective. */
42  unsigned short half_hash;
43 
44  union
45  {
46  char data[1];
47  double dummy;
48  }
49  d;
50 };
51 
52 
53 /* The structure for a bcache itself. The bcache is initialized, in
54  bcache_xmalloc(), by filling it with zeros and then setting the
55  corresponding obstack's malloc() and free() methods. */
56 
57 struct bcache
58 {
59  /* All the bstrings are allocated here. */
60  struct obstack cache;
61 
62  /* How many hash buckets we're using. */
63  unsigned int num_buckets;
64 
65  /* Hash buckets. This table is allocated using malloc, so when we
66  grow the table we can return the old table to the system. */
67  struct bstring **bucket;
68 
69  /* Statistics. */
70  unsigned long unique_count; /* number of unique strings */
71  long total_count; /* total number of strings cached, including dups */
72  long unique_size; /* size of unique strings, in bytes */
73  long total_size; /* total number of bytes cached, including dups */
74  long structure_size; /* total size of bcache, including infrastructure */
75  /* Number of times that the hash table is expanded and hence
76  re-built, and the corresponding number of times that a string is
77  [re]hashed as part of entering it into the expanded table. The
78  total number of hashes can be computed by adding TOTAL_COUNT to
79  expand_hash_count. */
80  unsigned long expand_count;
81  unsigned long expand_hash_count;
82  /* Number of times that the half-hash compare hit (compare the upper
83  16 bits of hash values) hit, but the corresponding combined
84  length/data compare missed. */
85  unsigned long half_hash_miss_count;
86 
87  /* Hash function to be used for this bcache object. */
88  unsigned long (*hash_function)(const void *addr, int length);
89 
90  /* Compare function to be used for this bcache object. */
91  int (*compare_function)(const void *, const void *, int length);
92 };
93 
94 /* The old hash function was stolen from SDBM. This is what DB 3.0
95  uses now, and is better than the old one. */
96 
97 unsigned long
98 hash(const void *addr, int length)
99 {
100  return hash_continue (addr, length, 0);
101 }
102 
103 /* Continue the calculation of the hash H at the given address. */
104 
105 unsigned long
106 hash_continue (const void *addr, int length, unsigned long h)
107 {
108  const unsigned char *k, *e;
109 
110  k = (const unsigned char *)addr;
111  e = k+length;
112  for (; k< e;++k)
113  {
114  h *=16777619;
115  h ^= *k;
116  }
117  return (h);
118 }
119 
120 /* Growing the bcache's hash table. */
121 
122 /* If the average chain length grows beyond this, then we want to
123  resize our hash table. */
124 #define CHAIN_LENGTH_THRESHOLD (5)
125 
126 static void
128 {
129  /* A table of good hash table sizes. Whenever we grow, we pick the
130  next larger size from this table. sizes[i] is close to 1 << (i+10),
131  so we roughly double the table size each time. After we fall off
132  the end of this table, we just double. Don't laugh --- there have
133  been executables sighted with a gigabyte of debug info. */
134  static unsigned long sizes[] = {
135  1021, 2053, 4099, 8191, 16381, 32771,
136  65537, 131071, 262144, 524287, 1048573, 2097143,
137  4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
138  268435459, 536870923, 1073741827, 2147483659UL
139  };
140  unsigned int new_num_buckets;
141  struct bstring **new_buckets;
142  unsigned int i;
143 
144  /* Count the stats. Every unique item needs to be re-hashed and
145  re-entered. */
146  bcache->expand_count++;
147  bcache->expand_hash_count += bcache->unique_count;
148 
149  /* Find the next size. */
150  new_num_buckets = bcache->num_buckets * 2;
151  for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
152  if (sizes[i] > bcache->num_buckets)
153  {
154  new_num_buckets = sizes[i];
155  break;
156  }
157 
158  /* Allocate the new table. */
159  {
160  size_t new_size = new_num_buckets * sizeof (new_buckets[0]);
161 
162  new_buckets = (struct bstring **) xmalloc (new_size);
163  memset (new_buckets, 0, new_size);
164 
165  bcache->structure_size -= (bcache->num_buckets
166  * sizeof (bcache->bucket[0]));
167  bcache->structure_size += new_size;
168  }
169 
170  /* Rehash all existing strings. */
171  for (i = 0; i < bcache->num_buckets; i++)
172  {
173  struct bstring *s, *next;
174 
175  for (s = bcache->bucket[i]; s; s = next)
176  {
177  struct bstring **new_bucket;
178  next = s->next;
179 
180  new_bucket = &new_buckets[(bcache->hash_function (&s->d.data,
181  s->length)
182  % new_num_buckets)];
183  s->next = *new_bucket;
184  *new_bucket = s;
185  }
186  }
187 
188  /* Plug in the new table. */
189  if (bcache->bucket)
190  xfree (bcache->bucket);
191  bcache->bucket = new_buckets;
192  bcache->num_buckets = new_num_buckets;
193 }
194 
195 
196 /* Looking up things in the bcache. */
197 
198 /* The number of bytes needed to allocate a struct bstring whose data
199  is N bytes long. */
200 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
201 
202 /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
203  never seen those bytes before, add a copy of them to BCACHE. In
204  either case, return a pointer to BCACHE's copy of that string. */
205 const void *
206 bcache (const void *addr, int length, struct bcache *cache)
207 {
208  return bcache_full (addr, length, cache, NULL);
209 }
210 
211 /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
212  never seen those bytes before, add a copy of them to BCACHE. In
213  either case, return a pointer to BCACHE's copy of that string. If
214  optional ADDED is not NULL, return 1 in case of new entry or 0 if
215  returning an old entry. */
216 
217 const void *
218 bcache_full (const void *addr, int length, struct bcache *bcache, int *added)
219 {
220  unsigned long full_hash;
221  unsigned short half_hash;
222  int hash_index;
223  struct bstring *s;
224 
225  if (added)
226  *added = 0;
227 
228  /* Lazily initialize the obstack. This can save quite a bit of
229  memory in some cases. */
230  if (bcache->total_count == 0)
231  {
232  /* We could use obstack_specify_allocation here instead, but
233  gdb_obstack.h specifies the allocation/deallocation
234  functions. */
235  obstack_init (&bcache->cache);
236  }
237 
238  /* If our average chain length is too high, expand the hash table. */
239  if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD)
240  expand_hash_table (bcache);
241 
242  bcache->total_count++;
243  bcache->total_size += length;
244 
245  full_hash = bcache->hash_function (addr, length);
246 
247  half_hash = (full_hash >> 16);
248  hash_index = full_hash % bcache->num_buckets;
249 
250  /* Search the hash bucket for a string identical to the caller's.
251  As a short-circuit first compare the upper part of each hash
252  values. */
253  for (s = bcache->bucket[hash_index]; s; s = s->next)
254  {
255  if (s->half_hash == half_hash)
256  {
257  if (s->length == length
258  && bcache->compare_function (&s->d.data, addr, length))
259  return &s->d.data;
260  else
261  bcache->half_hash_miss_count++;
262  }
263  }
264 
265  /* The user's string isn't in the list. Insert it after *ps. */
266  {
267  struct bstring *newobj
268  = obstack_alloc (&bcache->cache, BSTRING_SIZE (length));
269 
270  memcpy (&newobj->d.data, addr, length);
271  newobj->length = length;
272  newobj->next = bcache->bucket[hash_index];
273  newobj->half_hash = half_hash;
274  bcache->bucket[hash_index] = newobj;
275 
276  bcache->unique_count++;
277  bcache->unique_size += length;
278  bcache->structure_size += BSTRING_SIZE (length);
279 
280  if (added)
281  *added = 1;
282 
283  return &newobj->d.data;
284  }
285 }
286 
287 
288 /* Compare the byte string at ADDR1 of lenght LENGHT to the
289  string at ADDR2. Return 1 if they are equal. */
290 
291 static int
292 bcache_compare (const void *addr1, const void *addr2, int length)
293 {
294  return memcmp (addr1, addr2, length) == 0;
295 }
296 
297 /* Allocating and freeing bcaches. */
298 
299 /* Allocated a bcache. HASH_FUNCTION and COMPARE_FUNCTION can be used
300  to pass in custom hash, and compare functions to be used by this
301  bcache. If HASH_FUNCTION is NULL hash() is used and if
302  COMPARE_FUNCTION is NULL memcmp() is used. */
303 
304 struct bcache *
305 bcache_xmalloc (unsigned long (*hash_function)(const void *, int length),
306  int (*compare_function)(const void *,
307  const void *,
308  int length))
309 {
310  /* Allocate the bcache pre-zeroed. */
311  struct bcache *b = XCNEW (struct bcache);
312 
313  if (hash_function)
315  else
316  b->hash_function = hash;
317 
318  if (compare_function)
320  else
322  return b;
323 }
324 
325 /* Free all the storage associated with BCACHE. */
326 void
328 {
329  if (bcache == NULL)
330  return;
331  /* Only free the obstack if we actually initialized it. */
332  if (bcache->total_count > 0)
333  obstack_free (&bcache->cache, 0);
334  xfree (bcache->bucket);
335  xfree (bcache);
336 }
337 
338 
339 
340 /* Printing statistics. */
341 
342 static void
343 print_percentage (int portion, int total)
344 {
345  if (total == 0)
346  /* i18n: Like "Percentage of duplicates, by count: (not applicable)". */
347  printf_filtered (_("(not applicable)\n"));
348  else
349  printf_filtered ("%3d%%\n", (int) (portion * 100.0 / total));
350 }
351 
352 
353 /* Print statistics on BCACHE's memory usage and efficacity at
354  eliminating duplication. NAME should describe the kind of data
355  BCACHE holds. Statistics are printed using `printf_filtered' and
356  its ilk. */
357 void
359 {
360  int occupied_buckets;
361  int max_chain_length;
362  int median_chain_length;
363  int max_entry_size;
364  int median_entry_size;
365 
366  /* Count the number of occupied buckets, tally the various string
367  lengths, and measure chain lengths. */
368  {
369  unsigned int b;
370  int *chain_length = XCNEWVEC (int, c->num_buckets + 1);
371  int *entry_size = XCNEWVEC (int, c->unique_count + 1);
372  int stringi = 0;
373 
374  occupied_buckets = 0;
375 
376  for (b = 0; b < c->num_buckets; b++)
377  {
378  struct bstring *s = c->bucket[b];
379 
380  chain_length[b] = 0;
381 
382  if (s)
383  {
384  occupied_buckets++;
385 
386  while (s)
387  {
388  gdb_assert (b < c->num_buckets);
389  chain_length[b]++;
390  gdb_assert (stringi < c->unique_count);
391  entry_size[stringi++] = s->length;
392  s = s->next;
393  }
394  }
395  }
396 
397  /* To compute the median, we need the set of chain lengths
398  sorted. */
399  qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
401  qsort (entry_size, c->unique_count, sizeof (entry_size[0]),
403 
404  if (c->num_buckets > 0)
405  {
406  max_chain_length = chain_length[c->num_buckets - 1];
407  median_chain_length = chain_length[c->num_buckets / 2];
408  }
409  else
410  {
411  max_chain_length = 0;
412  median_chain_length = 0;
413  }
414  if (c->unique_count > 0)
415  {
416  max_entry_size = entry_size[c->unique_count - 1];
417  median_entry_size = entry_size[c->unique_count / 2];
418  }
419  else
420  {
421  max_entry_size = 0;
422  median_entry_size = 0;
423  }
424 
425  xfree (chain_length);
426  xfree (entry_size);
427  }
428 
429  printf_filtered (_(" Cached '%s' statistics:\n"), type);
430  printf_filtered (_(" Total object count: %ld\n"), c->total_count);
431  printf_filtered (_(" Unique object count: %lu\n"), c->unique_count);
432  printf_filtered (_(" Percentage of duplicates, by count: "));
434  printf_filtered ("\n");
435 
436  printf_filtered (_(" Total object size: %ld\n"), c->total_size);
437  printf_filtered (_(" Unique object size: %ld\n"), c->unique_size);
438  printf_filtered (_(" Percentage of duplicates, by size: "));
440  printf_filtered ("\n");
441 
442  printf_filtered (_(" Max entry size: %d\n"), max_entry_size);
443  printf_filtered (_(" Average entry size: "));
444  if (c->unique_count > 0)
445  printf_filtered ("%ld\n", c->unique_size / c->unique_count);
446  else
447  /* i18n: "Average entry size: (not applicable)". */
448  printf_filtered (_("(not applicable)\n"));
449  printf_filtered (_(" Median entry size: %d\n"), median_entry_size);
450  printf_filtered ("\n");
451 
452  printf_filtered (_(" \
453 Total memory used by bcache, including overhead: %ld\n"),
454  c->structure_size);
455  printf_filtered (_(" Percentage memory overhead: "));
457  printf_filtered (_(" Net memory savings: "));
459  printf_filtered ("\n");
460 
461  printf_filtered (_(" Hash table size: %3d\n"),
462  c->num_buckets);
463  printf_filtered (_(" Hash table expands: %lu\n"),
464  c->expand_count);
465  printf_filtered (_(" Hash table hashes: %lu\n"),
467  printf_filtered (_(" Half hash misses: %lu\n"),
469  printf_filtered (_(" Hash table population: "));
470  print_percentage (occupied_buckets, c->num_buckets);
471  printf_filtered (_(" Median hash chain length: %3d\n"),
472  median_chain_length);
473  printf_filtered (_(" Average hash chain length: "));
474  if (c->num_buckets > 0)
475  printf_filtered ("%3lu\n", c->unique_count / c->num_buckets);
476  else
477  /* i18n: "Average hash chain length: (not applicable)". */
478  printf_filtered (_("(not applicable)\n"));
479  printf_filtered (_(" Maximum hash chain length: %3d\n"),
480  max_chain_length);
481  printf_filtered ("\n");
482 }
483 
484 int
486 {
487  if (bcache->total_count == 0)
488  return 0;
489  return obstack_memory_used (&bcache->cache);
490 }
const void * bcache(const void *addr, int length, struct bcache *cache)
Definition: bcache.c:206
unsigned long hash_continue(const void *addr, int length, unsigned long h)
Definition: bcache.c:106
void xfree(void *)
Definition: common-utils.c:97
unsigned short half_hash
Definition: bcache.c:42
#define _(String)
Definition: gdb_locale.h:40
const void * bcache_full(const void *addr, int length, struct bcache *bcache, int *added)
Definition: bcache.c:218
Definition: bcache.c:32
struct bstring ** bucket
Definition: bcache.c:67
long total_size
Definition: bcache.c:73
#define CHAIN_LENGTH_THRESHOLD
Definition: bcache.c:124
unsigned long expand_count
Definition: bcache.c:80
void printf_filtered(const char *format,...)
Definition: utils.c:2388
static void expand_hash_table(struct bcache *bcache)
Definition: bcache.c:127
int(* compare_function)(const void *, const void *, int length)
Definition: bcache.c:91
static int bcache_compare(const void *addr1, const void *addr2, int length)
Definition: bcache.c:292
long unique_size
Definition: bcache.c:72
struct bcache * bcache_xmalloc(unsigned long(*hash_function)(const void *, int length), int(*compare_function)(const void *, const void *, int length))
Definition: bcache.c:305
Definition: gdbtypes.h:749
#define gdb_assert(expr)
Definition: gdb_assert.h:33
int bcache_memory_used(struct bcache *bcache)
Definition: bcache.c:485
union bstring::@28 d
static void print_percentage(int portion, int total)
Definition: bcache.c:343
void * xmalloc(YYSIZE_T)
int compare_positive_ints(const void *ap, const void *bp)
Definition: utils.c:3046
unsigned long hash(const void *addr, int length)
Definition: bcache.c:98
const char const char int
Definition: command.h:229
unsigned short length
Definition: bcache.c:37
void print_bcache_statistics(struct bcache *c, char *type)
Definition: bcache.c:358
unsigned long(* hash_function)(const void *addr, int length)
Definition: bcache.c:88
long structure_size
Definition: bcache.c:74
char data[1]
Definition: bcache.c:46
Definition: bcache.c:57
#define BSTRING_SIZE(n)
Definition: bcache.c:200
#define qsort
Definition: ada-exp.c:2747
struct bstring * next
Definition: bcache.c:35
void bcache_xfree(struct bcache *bcache)
Definition: bcache.c:327
double dummy
Definition: bcache.c:47
unsigned long half_hash_miss_count
Definition: bcache.c:85
unsigned int num_buckets
Definition: bcache.c:63
unsigned long unique_count
Definition: bcache.c:70
unsigned long expand_hash_count
Definition: bcache.c:81
struct obstack cache
Definition: bcache.c:60
long total_count
Definition: bcache.c:71