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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gdb-7.2/] [gdb/] [bcache.c] - Blame information for rev 841

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 330 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
 
156
    new_buckets = (struct bstring **) xmalloc (new_size);
157
    memset (new_buckets, 0, new_size);
158
 
159
    bcache->structure_size -= (bcache->num_buckets
160
                               * sizeof (bcache->bucket[0]));
161
    bcache->structure_size += new_size;
162
  }
163
 
164
  /* Rehash all existing strings.  */
165
  for (i = 0; i < bcache->num_buckets; i++)
166
    {
167
      struct bstring *s, *next;
168
 
169
      for (s = bcache->bucket[i]; s; s = next)
170
        {
171
          struct bstring **new_bucket;
172
          next = s->next;
173
 
174
          new_bucket = &new_buckets[(hash (&s->d.data, s->length)
175
                                     % new_num_buckets)];
176
          s->next = *new_bucket;
177
          *new_bucket = s;
178
        }
179
    }
180
 
181
  /* Plug in the new table.  */
182
  if (bcache->bucket)
183
    xfree (bcache->bucket);
184
  bcache->bucket = new_buckets;
185
  bcache->num_buckets = new_num_buckets;
186
}
187
 
188
 
189
/* Looking up things in the bcache.  */
190
 
191
/* The number of bytes needed to allocate a struct bstring whose data
192
   is N bytes long.  */
193
#define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
194
 
195
/* Find a copy of the LENGTH bytes at ADDR in BCACHE.  If BCACHE has
196
   never seen those bytes before, add a copy of them to BCACHE.  In
197
   either case, return a pointer to BCACHE's copy of that string.  */
198
const void *
199
bcache (const void *addr, int length, struct bcache *bcache)
200
{
201
  return bcache_full (addr, length, bcache, NULL);
202
}
203
 
204
/* Find a copy of the LENGTH bytes at ADDR in BCACHE.  If BCACHE has
205
   never seen those bytes before, add a copy of them to BCACHE.  In
206
   either case, return a pointer to BCACHE's copy of that string.  If
207
   optional ADDED is not NULL, return 1 in case of new entry or 0 if
208
   returning an old entry.  */
209
 
210
const void *
211
bcache_full (const void *addr, int length, struct bcache *bcache, int *added)
212
{
213
  unsigned long full_hash;
214
  unsigned short half_hash;
215
  int hash_index;
216
  struct bstring *s;
217
 
218
  if (added)
219
    *added = 0;
220
 
221
  /* Lazily initialize the obstack.  This can save quite a bit of
222
     memory in some cases.  */
223
  if (bcache->total_count == 0)
224
    {
225
      /* We could use obstack_specify_allocation here instead, but
226
         gdb_obstack.h specifies the allocation/deallocation
227
         functions.  */
228
      obstack_init (&bcache->cache);
229
    }
230
 
231
  /* If our average chain length is too high, expand the hash table.  */
232
  if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD)
233
    expand_hash_table (bcache);
234
 
235
  bcache->total_count++;
236
  bcache->total_size += length;
237
 
238
  full_hash = hash (addr, length);
239
  half_hash = (full_hash >> 16);
240
  hash_index = full_hash % bcache->num_buckets;
241
 
242
  /* Search the hash bucket for a string identical to the caller's.
243
     As a short-circuit first compare the upper part of each hash
244
     values.  */
245
  for (s = bcache->bucket[hash_index]; s; s = s->next)
246
    {
247
      if (s->half_hash == half_hash)
248
        {
249
          if (s->length == length
250
              && ! memcmp (&s->d.data, addr, length))
251
            return &s->d.data;
252
          else
253
            bcache->half_hash_miss_count++;
254
        }
255
    }
256
 
257
  /* The user's string isn't in the list.  Insert it after *ps.  */
258
  {
259
    struct bstring *new
260
      = obstack_alloc (&bcache->cache, BSTRING_SIZE (length));
261
 
262
    memcpy (&new->d.data, addr, length);
263
    new->length = length;
264
    new->next = bcache->bucket[hash_index];
265
    new->half_hash = half_hash;
266
    bcache->bucket[hash_index] = new;
267
 
268
    bcache->unique_count++;
269
    bcache->unique_size += length;
270
    bcache->structure_size += BSTRING_SIZE (length);
271
 
272
    if (added)
273
      *added = 1;
274
 
275
    return &new->d.data;
276
  }
277
}
278
 
279
/* Allocating and freeing bcaches.  */
280
 
281
struct bcache *
282
bcache_xmalloc (void)
283
{
284
  /* Allocate the bcache pre-zeroed.  */
285
  struct bcache *b = XCALLOC (1, struct bcache);
286
 
287
  return b;
288
}
289
 
290
/* Free all the storage associated with BCACHE.  */
291
void
292
bcache_xfree (struct bcache *bcache)
293
{
294
  if (bcache == NULL)
295
    return;
296
  /* Only free the obstack if we actually initialized it.  */
297
  if (bcache->total_count > 0)
298
    obstack_free (&bcache->cache, 0);
299
  xfree (bcache->bucket);
300
  xfree (bcache);
301
}
302
 
303
 
304
 
305
/* Printing statistics.  */
306
 
307
static void
308
print_percentage (int portion, int total)
309
{
310
  if (total == 0)
311
    /* i18n: Like "Percentage of duplicates, by count: (not applicable)" */
312
    printf_filtered (_("(not applicable)\n"));
313
  else
314
    printf_filtered ("%3d%%\n", (int) (portion * 100.0 / total));
315
}
316
 
317
 
318
/* Print statistics on BCACHE's memory usage and efficacity at
319
   eliminating duplication.  NAME should describe the kind of data
320
   BCACHE holds.  Statistics are printed using `printf_filtered' and
321
   its ilk.  */
322
void
323
print_bcache_statistics (struct bcache *c, char *type)
324
{
325
  int occupied_buckets;
326
  int max_chain_length;
327
  int median_chain_length;
328
  int max_entry_size;
329
  int median_entry_size;
330
 
331
  /* Count the number of occupied buckets, tally the various string
332
     lengths, and measure chain lengths.  */
333
  {
334
    unsigned int b;
335
    int *chain_length = XCALLOC (c->num_buckets + 1, int);
336
    int *entry_size = XCALLOC (c->unique_count + 1, int);
337
    int stringi = 0;
338
 
339
    occupied_buckets = 0;
340
 
341
    for (b = 0; b < c->num_buckets; b++)
342
      {
343
        struct bstring *s = c->bucket[b];
344
 
345
        chain_length[b] = 0;
346
 
347
        if (s)
348
          {
349
            occupied_buckets++;
350
 
351
            while (s)
352
              {
353
                gdb_assert (b < c->num_buckets);
354
                chain_length[b]++;
355
                gdb_assert (stringi < c->unique_count);
356
                entry_size[stringi++] = s->length;
357
                s = s->next;
358
              }
359
          }
360
      }
361
 
362
    /* To compute the median, we need the set of chain lengths sorted.  */
363
    qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
364
           compare_positive_ints);
365
    qsort (entry_size, c->unique_count, sizeof (entry_size[0]),
366
           compare_positive_ints);
367
 
368
    if (c->num_buckets > 0)
369
      {
370
        max_chain_length = chain_length[c->num_buckets - 1];
371
        median_chain_length = chain_length[c->num_buckets / 2];
372
      }
373
    else
374
      {
375
        max_chain_length = 0;
376
        median_chain_length = 0;
377
      }
378
    if (c->unique_count > 0)
379
      {
380
        max_entry_size = entry_size[c->unique_count - 1];
381
        median_entry_size = entry_size[c->unique_count / 2];
382
      }
383
    else
384
      {
385
        max_entry_size = 0;
386
        median_entry_size = 0;
387
      }
388
 
389
    xfree (chain_length);
390
    xfree (entry_size);
391
  }
392
 
393
  printf_filtered (_("  Cached '%s' statistics:\n"), type);
394
  printf_filtered (_("    Total object count:  %ld\n"), c->total_count);
395
  printf_filtered (_("    Unique object count: %lu\n"), c->unique_count);
396
  printf_filtered (_("    Percentage of duplicates, by count: "));
397
  print_percentage (c->total_count - c->unique_count, c->total_count);
398
  printf_filtered ("\n");
399
 
400
  printf_filtered (_("    Total object size:   %ld\n"), c->total_size);
401
  printf_filtered (_("    Unique object size:  %ld\n"), c->unique_size);
402
  printf_filtered (_("    Percentage of duplicates, by size:  "));
403
  print_percentage (c->total_size - c->unique_size, c->total_size);
404
  printf_filtered ("\n");
405
 
406
  printf_filtered (_("    Max entry size:     %d\n"), max_entry_size);
407
  printf_filtered (_("    Average entry size: "));
408
  if (c->unique_count > 0)
409
    printf_filtered ("%ld\n", c->unique_size / c->unique_count);
410
  else
411
    /* i18n: "Average entry size: (not applicable)" */
412
    printf_filtered (_("(not applicable)\n"));
413
  printf_filtered (_("    Median entry size:  %d\n"), median_entry_size);
414
  printf_filtered ("\n");
415
 
416
  printf_filtered (_("    Total memory used by bcache, including overhead: %ld\n"),
417
                   c->structure_size);
418
  printf_filtered (_("    Percentage memory overhead: "));
419
  print_percentage (c->structure_size - c->unique_size, c->unique_size);
420
  printf_filtered (_("    Net memory savings:         "));
421
  print_percentage (c->total_size - c->structure_size, c->total_size);
422
  printf_filtered ("\n");
423
 
424
  printf_filtered (_("    Hash table size:           %3d\n"), c->num_buckets);
425
  printf_filtered (_("    Hash table expands:        %lu\n"),
426
                   c->expand_count);
427
  printf_filtered (_("    Hash table hashes:         %lu\n"),
428
                   c->total_count + c->expand_hash_count);
429
  printf_filtered (_("    Half hash misses:          %lu\n"),
430
                   c->half_hash_miss_count);
431
  printf_filtered (_("    Hash table population:     "));
432
  print_percentage (occupied_buckets, c->num_buckets);
433
  printf_filtered (_("    Median hash chain length:  %3d\n"),
434
                   median_chain_length);
435
  printf_filtered (_("    Average hash chain length: "));
436
  if (c->num_buckets > 0)
437
    printf_filtered ("%3lu\n", c->unique_count / c->num_buckets);
438
  else
439
    /* i18n: "Average hash chain length: (not applicable)" */
440
    printf_filtered (_("(not applicable)\n"));
441
  printf_filtered (_("    Maximum hash chain length: %3d\n"), max_chain_length);
442
  printf_filtered ("\n");
443
}
444
 
445
int
446
bcache_memory_used (struct bcache *bcache)
447
{
448
  if (bcache->total_count == 0)
449
    return 0;
450
  return obstack_memory_used (&bcache->cache);
451
}

powered by: WebSVN 2.1.0

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