OpenCores
URL https://opencores.org/ocsvn/openrisc_me/openrisc_me/trunk

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gdb-7.1/] [gdb/] [bcache.c] - Blame information for rev 227

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.