1 /* Implement a cached obstack.
2 Written by Fred Fish <fnf@cygnus.com>
3 Rewritten by Jim Blandy <jimb@cygnus.com>
5 Copyright (C) 1999-2019 Free Software Foundation, Inc.
7 This file is part of GDB.
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.
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.
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/>. */
24 /* Local non-gdb includes. */
26 #include "gdb_obstack.h"
28 /* The type used to hold a single bcache string. The user data is
29 stored in d.data. Since it can be any type, it needs to have the
30 same alignment as the most strict alignment of any type on the host
31 machine. I don't know of any really correct way to do this in
32 stock ANSI C, so just do it the same way obstack.h does. */
38 /* Assume the data length is no more than 64k. */
39 unsigned short length
;
40 /* The half hash hack. This contains the upper 16 bits of the hash
41 value and is used as a pre-check when comparing two strings and
42 avoids the need to do length or memcmp calls. It proves to be
43 roughly 100% effective. */
44 unsigned short half_hash
;
54 /* The old hash function was stolen from SDBM. This is what DB 3.0
55 uses now, and is better than the old one. */
58 hash(const void *addr
, int length
)
60 return hash_continue (addr
, length
, 0);
63 /* Continue the calculation of the hash H at the given address. */
66 hash_continue (const void *addr
, int length
, unsigned long h
)
68 const unsigned char *k
, *e
;
70 k
= (const unsigned char *)addr
;
80 /* Growing the bcache's hash table. */
82 /* If the average chain length grows beyond this, then we want to
83 resize our hash table. */
84 #define CHAIN_LENGTH_THRESHOLD (5)
87 bcache::expand_hash_table ()
89 /* A table of good hash table sizes. Whenever we grow, we pick the
90 next larger size from this table. sizes[i] is close to 1 << (i+10),
91 so we roughly double the table size each time. After we fall off
92 the end of this table, we just double. Don't laugh --- there have
93 been executables sighted with a gigabyte of debug info. */
94 static unsigned long sizes
[] = {
95 1021, 2053, 4099, 8191, 16381, 32771,
96 65537, 131071, 262144, 524287, 1048573, 2097143,
97 4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
98 268435459, 536870923, 1073741827, 2147483659UL
100 unsigned int new_num_buckets
;
101 struct bstring
**new_buckets
;
104 /* Count the stats. Every unique item needs to be re-hashed and
107 m_expand_hash_count
+= m_unique_count
;
109 /* Find the next size. */
110 new_num_buckets
= m_num_buckets
* 2;
111 for (i
= 0; i
< (sizeof (sizes
) / sizeof (sizes
[0])); i
++)
112 if (sizes
[i
] > m_num_buckets
)
114 new_num_buckets
= sizes
[i
];
118 /* Allocate the new table. */
120 size_t new_size
= new_num_buckets
* sizeof (new_buckets
[0]);
122 new_buckets
= (struct bstring
**) xmalloc (new_size
);
123 memset (new_buckets
, 0, new_size
);
125 m_structure_size
-= m_num_buckets
* sizeof (m_bucket
[0]);
126 m_structure_size
+= new_size
;
129 /* Rehash all existing strings. */
130 for (i
= 0; i
< m_num_buckets
; i
++)
132 struct bstring
*s
, *next
;
134 for (s
= m_bucket
[i
]; s
; s
= next
)
136 struct bstring
**new_bucket
;
139 new_bucket
= &new_buckets
[(m_hash_function (&s
->d
.data
, s
->length
)
141 s
->next
= *new_bucket
;
146 /* Plug in the new table. */
148 m_bucket
= new_buckets
;
149 m_num_buckets
= new_num_buckets
;
153 /* Looking up things in the bcache. */
155 /* The number of bytes needed to allocate a struct bstring whose data
157 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
159 /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
160 never seen those bytes before, add a copy of them to BCACHE. In
161 either case, return a pointer to BCACHE's copy of that string. If
162 optional ADDED is not NULL, return 1 in case of new entry or 0 if
163 returning an old entry. */
166 bcache::insert (const void *addr
, int length
, int *added
)
168 unsigned long full_hash
;
169 unsigned short half_hash
;
176 /* Lazily initialize the obstack. This can save quite a bit of
177 memory in some cases. */
178 if (m_total_count
== 0)
180 /* We could use obstack_specify_allocation here instead, but
181 gdb_obstack.h specifies the allocation/deallocation
183 obstack_init (&m_cache
);
186 /* If our average chain length is too high, expand the hash table. */
187 if (m_unique_count
>= m_num_buckets
* CHAIN_LENGTH_THRESHOLD
)
188 expand_hash_table ();
191 m_total_size
+= length
;
193 full_hash
= m_hash_function (addr
, length
);
195 half_hash
= (full_hash
>> 16);
196 hash_index
= full_hash
% m_num_buckets
;
198 /* Search the hash m_bucket for a string identical to the caller's.
199 As a short-circuit first compare the upper part of each hash
201 for (s
= m_bucket
[hash_index
]; s
; s
= s
->next
)
203 if (s
->half_hash
== half_hash
)
205 if (s
->length
== length
206 && m_compare_function (&s
->d
.data
, addr
, length
))
209 m_half_hash_miss_count
++;
213 /* The user's string isn't in the list. Insert it after *ps. */
215 struct bstring
*newobj
216 = (struct bstring
*) obstack_alloc (&m_cache
,
217 BSTRING_SIZE (length
));
219 memcpy (&newobj
->d
.data
, addr
, length
);
220 newobj
->length
= length
;
221 newobj
->next
= m_bucket
[hash_index
];
222 newobj
->half_hash
= half_hash
;
223 m_bucket
[hash_index
] = newobj
;
226 m_unique_size
+= length
;
227 m_structure_size
+= BSTRING_SIZE (length
);
232 return &newobj
->d
.data
;
237 /* Compare the byte string at ADDR1 of lenght LENGHT to the
238 string at ADDR2. Return 1 if they are equal. */
241 bcache::compare (const void *addr1
, const void *addr2
, int length
)
243 return memcmp (addr1
, addr2
, length
) == 0;
246 /* Free all the storage associated with BCACHE. */
249 /* Only free the obstack if we actually initialized it. */
250 if (m_total_count
> 0)
251 obstack_free (&m_cache
, 0);
257 /* Printing statistics. */
260 print_percentage (int portion
, int total
)
263 /* i18n: Like "Percentage of duplicates, by count: (not applicable)". */
264 printf_filtered (_("(not applicable)\n"));
266 printf_filtered ("%3d%%\n", (int) (portion
* 100.0 / total
));
270 /* Print statistics on BCACHE's memory usage and efficacity at
271 eliminating duplication. NAME should describe the kind of data
272 BCACHE holds. Statistics are printed using `printf_filtered' and
275 bcache::print_statistics (const char *type
)
277 int occupied_buckets
;
278 int max_chain_length
;
279 int median_chain_length
;
281 int median_entry_size
;
283 /* Count the number of occupied buckets, tally the various string
284 lengths, and measure chain lengths. */
287 int *chain_length
= XCNEWVEC (int, m_num_buckets
+ 1);
288 int *entry_size
= XCNEWVEC (int, m_unique_count
+ 1);
291 occupied_buckets
= 0;
293 for (b
= 0; b
< m_num_buckets
; b
++)
295 struct bstring
*s
= m_bucket
[b
];
305 gdb_assert (b
< m_num_buckets
);
307 gdb_assert (stringi
< m_unique_count
);
308 entry_size
[stringi
++] = s
->length
;
314 /* To compute the median, we need the set of chain lengths
316 qsort (chain_length
, m_num_buckets
, sizeof (chain_length
[0]),
317 compare_positive_ints
);
318 qsort (entry_size
, m_unique_count
, sizeof (entry_size
[0]),
319 compare_positive_ints
);
321 if (m_num_buckets
> 0)
323 max_chain_length
= chain_length
[m_num_buckets
- 1];
324 median_chain_length
= chain_length
[m_num_buckets
/ 2];
328 max_chain_length
= 0;
329 median_chain_length
= 0;
331 if (m_unique_count
> 0)
333 max_entry_size
= entry_size
[m_unique_count
- 1];
334 median_entry_size
= entry_size
[m_unique_count
/ 2];
339 median_entry_size
= 0;
342 xfree (chain_length
);
346 printf_filtered (_(" M_Cached '%s' statistics:\n"), type
);
347 printf_filtered (_(" Total object count: %ld\n"), m_total_count
);
348 printf_filtered (_(" Unique object count: %lu\n"), m_unique_count
);
349 printf_filtered (_(" Percentage of duplicates, by count: "));
350 print_percentage (m_total_count
- m_unique_count
, m_total_count
);
351 printf_filtered ("\n");
353 printf_filtered (_(" Total object size: %ld\n"), m_total_size
);
354 printf_filtered (_(" Unique object size: %ld\n"), m_unique_size
);
355 printf_filtered (_(" Percentage of duplicates, by size: "));
356 print_percentage (m_total_size
- m_unique_size
, m_total_size
);
357 printf_filtered ("\n");
359 printf_filtered (_(" Max entry size: %d\n"), max_entry_size
);
360 printf_filtered (_(" Average entry size: "));
361 if (m_unique_count
> 0)
362 printf_filtered ("%ld\n", m_unique_size
/ m_unique_count
);
364 /* i18n: "Average entry size: (not applicable)". */
365 printf_filtered (_("(not applicable)\n"));
366 printf_filtered (_(" Median entry size: %d\n"), median_entry_size
);
367 printf_filtered ("\n");
369 printf_filtered (_(" \
370 Total memory used by bcache, including overhead: %ld\n"),
372 printf_filtered (_(" Percentage memory overhead: "));
373 print_percentage (m_structure_size
- m_unique_size
, m_unique_size
);
374 printf_filtered (_(" Net memory savings: "));
375 print_percentage (m_total_size
- m_structure_size
, m_total_size
);
376 printf_filtered ("\n");
378 printf_filtered (_(" Hash table size: %3d\n"),
380 printf_filtered (_(" Hash table expands: %lu\n"),
382 printf_filtered (_(" Hash table hashes: %lu\n"),
383 m_total_count
+ m_expand_hash_count
);
384 printf_filtered (_(" Half hash misses: %lu\n"),
385 m_half_hash_miss_count
);
386 printf_filtered (_(" Hash table population: "));
387 print_percentage (occupied_buckets
, m_num_buckets
);
388 printf_filtered (_(" Median hash chain length: %3d\n"),
389 median_chain_length
);
390 printf_filtered (_(" Average hash chain length: "));
391 if (m_num_buckets
> 0)
392 printf_filtered ("%3lu\n", m_unique_count
/ m_num_buckets
);
394 /* i18n: "Average hash chain length: (not applicable)". */
395 printf_filtered (_("(not applicable)\n"));
396 printf_filtered (_(" Maximum hash chain length: %3d\n"),
398 printf_filtered ("\n");
402 bcache::memory_used ()
404 if (m_total_count
== 0)
406 return obstack_memory_used (&m_cache
);