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/>. */
23 #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
;
55 /* Growing the bcache's hash table. */
57 /* If the average chain length grows beyond this, then we want to
58 resize our hash table. */
59 #define CHAIN_LENGTH_THRESHOLD (5)
62 bcache::expand_hash_table ()
64 /* A table of good hash table sizes. Whenever we grow, we pick the
65 next larger size from this table. sizes[i] is close to 1 << (i+10),
66 so we roughly double the table size each time. After we fall off
67 the end of this table, we just double. Don't laugh --- there have
68 been executables sighted with a gigabyte of debug info. */
69 static unsigned long sizes
[] = {
70 1021, 2053, 4099, 8191, 16381, 32771,
71 65537, 131071, 262144, 524287, 1048573, 2097143,
72 4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
73 268435459, 536870923, 1073741827, 2147483659UL
75 unsigned int new_num_buckets
;
76 struct bstring
**new_buckets
;
79 /* Count the stats. Every unique item needs to be re-hashed and
82 m_expand_hash_count
+= m_unique_count
;
84 /* Find the next size. */
85 new_num_buckets
= m_num_buckets
* 2;
86 for (i
= 0; i
< (sizeof (sizes
) / sizeof (sizes
[0])); i
++)
87 if (sizes
[i
] > m_num_buckets
)
89 new_num_buckets
= sizes
[i
];
93 /* Allocate the new table. */
95 size_t new_size
= new_num_buckets
* sizeof (new_buckets
[0]);
97 new_buckets
= (struct bstring
**) xmalloc (new_size
);
98 memset (new_buckets
, 0, new_size
);
100 m_structure_size
-= m_num_buckets
* sizeof (m_bucket
[0]);
101 m_structure_size
+= new_size
;
104 /* Rehash all existing strings. */
105 for (i
= 0; i
< m_num_buckets
; i
++)
107 struct bstring
*s
, *next
;
109 for (s
= m_bucket
[i
]; s
; s
= next
)
111 struct bstring
**new_bucket
;
114 new_bucket
= &new_buckets
[(m_hash_function (&s
->d
.data
, s
->length
)
116 s
->next
= *new_bucket
;
121 /* Plug in the new table. */
123 m_bucket
= new_buckets
;
124 m_num_buckets
= new_num_buckets
;
128 /* Looking up things in the bcache. */
130 /* The number of bytes needed to allocate a struct bstring whose data
132 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
134 /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
135 never seen those bytes before, add a copy of them to BCACHE. In
136 either case, return a pointer to BCACHE's copy of that string. If
137 optional ADDED is not NULL, return 1 in case of new entry or 0 if
138 returning an old entry. */
141 bcache::insert (const void *addr
, int length
, int *added
)
143 unsigned long full_hash
;
144 unsigned short half_hash
;
151 /* Lazily initialize the obstack. This can save quite a bit of
152 memory in some cases. */
153 if (m_total_count
== 0)
155 /* We could use obstack_specify_allocation here instead, but
156 gdb_obstack.h specifies the allocation/deallocation
158 obstack_init (&m_cache
);
161 /* If our average chain length is too high, expand the hash table. */
162 if (m_unique_count
>= m_num_buckets
* CHAIN_LENGTH_THRESHOLD
)
163 expand_hash_table ();
166 m_total_size
+= length
;
168 full_hash
= m_hash_function (addr
, length
);
170 half_hash
= (full_hash
>> 16);
171 hash_index
= full_hash
% m_num_buckets
;
173 /* Search the hash m_bucket for a string identical to the caller's.
174 As a short-circuit first compare the upper part of each hash
176 for (s
= m_bucket
[hash_index
]; s
; s
= s
->next
)
178 if (s
->half_hash
== half_hash
)
180 if (s
->length
== length
181 && m_compare_function (&s
->d
.data
, addr
, length
))
184 m_half_hash_miss_count
++;
188 /* The user's string isn't in the list. Insert it after *ps. */
190 struct bstring
*newobj
191 = (struct bstring
*) obstack_alloc (&m_cache
,
192 BSTRING_SIZE (length
));
194 memcpy (&newobj
->d
.data
, addr
, length
);
195 newobj
->length
= length
;
196 newobj
->next
= m_bucket
[hash_index
];
197 newobj
->half_hash
= half_hash
;
198 m_bucket
[hash_index
] = newobj
;
201 m_unique_size
+= length
;
202 m_structure_size
+= BSTRING_SIZE (length
);
207 return &newobj
->d
.data
;
212 /* Compare the byte string at ADDR1 of lenght LENGHT to the
213 string at ADDR2. Return 1 if they are equal. */
216 bcache::compare (const void *addr1
, const void *addr2
, int length
)
218 return memcmp (addr1
, addr2
, length
) == 0;
221 /* Free all the storage associated with BCACHE. */
224 /* Only free the obstack if we actually initialized it. */
225 if (m_total_count
> 0)
226 obstack_free (&m_cache
, 0);
232 /* Printing statistics. */
235 print_percentage (int portion
, int total
)
238 /* i18n: Like "Percentage of duplicates, by count: (not applicable)". */
239 printf_filtered (_("(not applicable)\n"));
241 printf_filtered ("%3d%%\n", (int) (portion
* 100.0 / total
));
245 /* Print statistics on BCACHE's memory usage and efficacity at
246 eliminating duplication. NAME should describe the kind of data
247 BCACHE holds. Statistics are printed using `printf_filtered' and
250 bcache::print_statistics (const char *type
)
252 int occupied_buckets
;
253 int max_chain_length
;
254 int median_chain_length
;
256 int median_entry_size
;
258 /* Count the number of occupied buckets, tally the various string
259 lengths, and measure chain lengths. */
262 int *chain_length
= XCNEWVEC (int, m_num_buckets
+ 1);
263 int *entry_size
= XCNEWVEC (int, m_unique_count
+ 1);
266 occupied_buckets
= 0;
268 for (b
= 0; b
< m_num_buckets
; b
++)
270 struct bstring
*s
= m_bucket
[b
];
280 gdb_assert (b
< m_num_buckets
);
282 gdb_assert (stringi
< m_unique_count
);
283 entry_size
[stringi
++] = s
->length
;
289 /* To compute the median, we need the set of chain lengths
291 std::sort (chain_length
, chain_length
+ m_num_buckets
);
292 std::sort (entry_size
, entry_size
+ m_unique_count
);
294 if (m_num_buckets
> 0)
296 max_chain_length
= chain_length
[m_num_buckets
- 1];
297 median_chain_length
= chain_length
[m_num_buckets
/ 2];
301 max_chain_length
= 0;
302 median_chain_length
= 0;
304 if (m_unique_count
> 0)
306 max_entry_size
= entry_size
[m_unique_count
- 1];
307 median_entry_size
= entry_size
[m_unique_count
/ 2];
312 median_entry_size
= 0;
315 xfree (chain_length
);
319 printf_filtered (_(" M_Cached '%s' statistics:\n"), type
);
320 printf_filtered (_(" Total object count: %ld\n"), m_total_count
);
321 printf_filtered (_(" Unique object count: %lu\n"), m_unique_count
);
322 printf_filtered (_(" Percentage of duplicates, by count: "));
323 print_percentage (m_total_count
- m_unique_count
, m_total_count
);
324 printf_filtered ("\n");
326 printf_filtered (_(" Total object size: %ld\n"), m_total_size
);
327 printf_filtered (_(" Unique object size: %ld\n"), m_unique_size
);
328 printf_filtered (_(" Percentage of duplicates, by size: "));
329 print_percentage (m_total_size
- m_unique_size
, m_total_size
);
330 printf_filtered ("\n");
332 printf_filtered (_(" Max entry size: %d\n"), max_entry_size
);
333 printf_filtered (_(" Average entry size: "));
334 if (m_unique_count
> 0)
335 printf_filtered ("%ld\n", m_unique_size
/ m_unique_count
);
337 /* i18n: "Average entry size: (not applicable)". */
338 printf_filtered (_("(not applicable)\n"));
339 printf_filtered (_(" Median entry size: %d\n"), median_entry_size
);
340 printf_filtered ("\n");
342 printf_filtered (_(" \
343 Total memory used by bcache, including overhead: %ld\n"),
345 printf_filtered (_(" Percentage memory overhead: "));
346 print_percentage (m_structure_size
- m_unique_size
, m_unique_size
);
347 printf_filtered (_(" Net memory savings: "));
348 print_percentage (m_total_size
- m_structure_size
, m_total_size
);
349 printf_filtered ("\n");
351 printf_filtered (_(" Hash table size: %3d\n"),
353 printf_filtered (_(" Hash table expands: %lu\n"),
355 printf_filtered (_(" Hash table hashes: %lu\n"),
356 m_total_count
+ m_expand_hash_count
);
357 printf_filtered (_(" Half hash misses: %lu\n"),
358 m_half_hash_miss_count
);
359 printf_filtered (_(" Hash table population: "));
360 print_percentage (occupied_buckets
, m_num_buckets
);
361 printf_filtered (_(" Median hash chain length: %3d\n"),
362 median_chain_length
);
363 printf_filtered (_(" Average hash chain length: "));
364 if (m_num_buckets
> 0)
365 printf_filtered ("%3lu\n", m_unique_count
/ m_num_buckets
);
367 /* i18n: "Average hash chain length: (not applicable)". */
368 printf_filtered (_("(not applicable)\n"));
369 printf_filtered (_(" Maximum hash chain length: %3d\n"),
371 printf_filtered ("\n");
375 bcache::memory_used ()
377 if (m_total_count
== 0)
379 return obstack_memory_used (&m_cache
);
This page took 0.057113 seconds and 4 git commands to generate.