1 /* Implement a cached obstack.
2 Written by Fred Fish <fnf@cygnus.com>
3 Rewritten by Jim Blandy <jimb@cygnus.com>
5 Copyright 1999, 2000, 2002 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 2 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, write to the Free Software
21 Foundation, Inc., 59 Temple Place - Suite 330,
22 Boston, MA 02111-1307, USA. */
25 #include "gdb_obstack.h"
27 #include "gdb_string.h" /* For memcpy declaration */
32 /* The type used to hold a single bcache string. The user data is
33 stored in d.data. Since it can be any type, it needs to have the
34 same alignment as the most strict alignment of any type on the host
35 machine. I don't know of any really correct way to do this in
36 stock ANSI C, so just do it the same way obstack.h does. */
52 /* The structure for a bcache itself. The bcache is initialized, in
53 bcache_xmalloc(), by filling it with zeros and then setting the
54 corresponding obstack's malloc() and free() methods. */
58 /* All the bstrings are allocated here. */
61 /* How many hash buckets we're using. */
62 unsigned int num_buckets
;
64 /* Hash buckets. This table is allocated using malloc, so when we
65 grow the table we can return the old table to the system. */
66 struct bstring
**bucket
;
69 unsigned long unique_count
; /* number of unique strings */
70 long total_count
; /* total number of strings cached, including dups */
71 long unique_size
; /* size of unique strings, in bytes */
72 long total_size
; /* total number of bytes cached, including dups */
73 long structure_size
; /* total size of bcache, including infrastructure */
76 /* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
77 * and is better than the old one.
81 hash(const void *addr
, int length
)
83 const unsigned char *k
, *e
;
86 k
= (const unsigned char *)addr
;
96 /* Growing the bcache's hash table. */
98 /* If the average chain length grows beyond this, then we want to
99 resize our hash table. */
100 #define CHAIN_LENGTH_THRESHOLD (5)
103 expand_hash_table (struct bcache
*bcache
)
105 /* A table of good hash table sizes. Whenever we grow, we pick the
106 next larger size from this table. sizes[i] is close to 1 << (i+10),
107 so we roughly double the table size each time. After we fall off
108 the end of this table, we just double. Don't laugh --- there have
109 been executables sighted with a gigabyte of debug info. */
110 static unsigned long sizes
[] = {
111 1021, 2053, 4099, 8191, 16381, 32771,
112 65537, 131071, 262144, 524287, 1048573, 2097143,
113 4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
114 268435459, 536870923, 1073741827, 2147483659UL
116 unsigned int new_num_buckets
;
117 struct bstring
**new_buckets
;
120 /* Find the next size. */
121 new_num_buckets
= bcache
->num_buckets
* 2;
122 for (i
= 0; i
< (sizeof (sizes
) / sizeof (sizes
[0])); i
++)
123 if (sizes
[i
] > bcache
->num_buckets
)
125 new_num_buckets
= sizes
[i
];
129 /* Allocate the new table. */
131 size_t new_size
= new_num_buckets
* sizeof (new_buckets
[0]);
132 new_buckets
= (struct bstring
**) xmalloc (new_size
);
133 memset (new_buckets
, 0, new_size
);
135 bcache
->structure_size
-= (bcache
->num_buckets
136 * sizeof (bcache
->bucket
[0]));
137 bcache
->structure_size
+= new_size
;
140 /* Rehash all existing strings. */
141 for (i
= 0; i
< bcache
->num_buckets
; i
++)
143 struct bstring
*s
, *next
;
145 for (s
= bcache
->bucket
[i
]; s
; s
= next
)
147 struct bstring
**new_bucket
;
150 new_bucket
= &new_buckets
[(hash (&s
->d
.data
, s
->length
)
152 s
->next
= *new_bucket
;
157 /* Plug in the new table. */
159 xfree (bcache
->bucket
);
160 bcache
->bucket
= new_buckets
;
161 bcache
->num_buckets
= new_num_buckets
;
165 /* Looking up things in the bcache. */
167 /* The number of bytes needed to allocate a struct bstring whose data
169 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
171 /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
172 never seen those bytes before, add a copy of them to BCACHE. In
173 either case, return a pointer to BCACHE's copy of that string. */
175 bcache (const void *addr
, int length
, struct bcache
*bcache
)
180 /* If our average chain length is too high, expand the hash table. */
181 if (bcache
->unique_count
>= bcache
->num_buckets
* CHAIN_LENGTH_THRESHOLD
)
182 expand_hash_table (bcache
);
184 bcache
->total_count
++;
185 bcache
->total_size
+= length
;
187 hash_index
= hash (addr
, length
) % bcache
->num_buckets
;
189 /* Search the hash bucket for a string identical to the caller's. */
190 for (s
= bcache
->bucket
[hash_index
]; s
; s
= s
->next
)
191 if (s
->length
== length
192 && ! memcmp (&s
->d
.data
, addr
, length
))
195 /* The user's string isn't in the list. Insert it after *ps. */
198 = obstack_alloc (&bcache
->cache
, BSTRING_SIZE (length
));
199 memcpy (&new->d
.data
, addr
, length
);
200 new->length
= length
;
201 new->next
= bcache
->bucket
[hash_index
];
202 bcache
->bucket
[hash_index
] = new;
204 bcache
->unique_count
++;
205 bcache
->unique_size
+= length
;
206 bcache
->structure_size
+= BSTRING_SIZE (length
);
213 /* Allocating and freeing bcaches. */
216 bcache_xmalloc (void)
218 /* Allocate the bcache pre-zeroed. */
219 struct bcache
*b
= XCALLOC (1, struct bcache
);
220 obstack_specify_allocation (&b
->cache
, 0, 0, xmalloc
, xfree
);
224 /* Free all the storage associated with BCACHE. */
226 bcache_xfree (struct bcache
*bcache
)
230 obstack_free (&bcache
->cache
, 0);
231 xfree (bcache
->bucket
);
237 /* Printing statistics. */
240 compare_ints (const void *ap
, const void *bp
)
242 /* Because we know we're comparing two ints which are positive,
243 there's no danger of overflow here. */
244 return * (int *) ap
- * (int *) bp
;
249 print_percentage (int portion
, int total
)
252 printf_filtered ("(not applicable)\n");
254 printf_filtered ("%3d%%\n", portion
* 100 / total
);
258 /* Print statistics on BCACHE's memory usage and efficacity at
259 eliminating duplication. NAME should describe the kind of data
260 BCACHE holds. Statistics are printed using `printf_filtered' and
263 print_bcache_statistics (struct bcache
*c
, char *type
)
265 int occupied_buckets
;
266 int max_chain_length
;
267 int median_chain_length
;
269 /* Count the number of occupied buckets, and measure chain lengths. */
273 = (int *) alloca (c
->num_buckets
* sizeof (*chain_length
));
275 occupied_buckets
= 0;
277 for (b
= 0; b
< c
->num_buckets
; b
++)
279 struct bstring
*s
= c
->bucket
[b
];
295 /* To compute the median, we need the set of chain lengths sorted. */
296 qsort (chain_length
, c
->num_buckets
, sizeof (chain_length
[0]),
299 if (c
->num_buckets
> 0)
301 max_chain_length
= chain_length
[c
->num_buckets
- 1];
302 median_chain_length
= chain_length
[c
->num_buckets
/ 2];
306 max_chain_length
= 0;
307 median_chain_length
= 0;
311 printf_filtered (" Cached '%s' statistics:\n", type
);
312 printf_filtered (" Total object count: %ld\n", c
->total_count
);
313 printf_filtered (" Unique object count: %lu\n", c
->unique_count
);
314 printf_filtered (" Percentage of duplicates, by count: ");
315 print_percentage (c
->total_count
- c
->unique_count
, c
->total_count
);
316 printf_filtered ("\n");
318 printf_filtered (" Total object size: %ld\n", c
->total_size
);
319 printf_filtered (" Unique object size: %ld\n", c
->unique_size
);
320 printf_filtered (" Percentage of duplicates, by size: ");
321 print_percentage (c
->total_size
- c
->unique_size
, c
->total_size
);
322 printf_filtered ("\n");
324 printf_filtered (" Total memory used by bcache, including overhead: %ld\n",
326 printf_filtered (" Percentage memory overhead: ");
327 print_percentage (c
->structure_size
- c
->unique_size
, c
->unique_size
);
328 printf_filtered (" Net memory savings: ");
329 print_percentage (c
->total_size
- c
->structure_size
, c
->total_size
);
330 printf_filtered ("\n");
332 printf_filtered (" Hash table size: %3d\n", c
->num_buckets
);
333 printf_filtered (" Hash table population: ");
334 print_percentage (occupied_buckets
, c
->num_buckets
);
335 printf_filtered (" Median hash chain length: %3d\n",
336 median_chain_length
);
337 printf_filtered (" Average hash chain length: ");
338 if (c
->num_buckets
> 0)
339 printf_filtered ("%3lu\n", c
->unique_count
/ c
->num_buckets
);
341 printf_filtered ("(not applicable)\n");
342 printf_filtered (" Maximum hash chain length: %3d\n", max_chain_length
);
343 printf_filtered ("\n");
347 bcache_memory_used (struct bcache
*bcache
)
349 return obstack_memory_used (&bcache
->cache
);
This page took 0.035423 seconds and 4 git commands to generate.