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

Subversion Repositories or1k

[/] [or1k/] [trunk/] [gdb-5.3/] [gdb/] [bcache.c] - Blame information for rev 1765

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 1181 sfurman
/* Implement a cached obstack.
2
   Written by Fred Fish <fnf@cygnus.com>
3
   Rewritten by Jim Blandy <jimb@cygnus.com>
4
 
5
   Copyright 1999, 2000, 2002 Free Software Foundation, Inc.
6
 
7
   This file is part of GDB.
8
 
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.
13
 
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.
18
 
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.  */
23
 
24
#include "defs.h"
25
#include "gdb_obstack.h"
26
#include "bcache.h"
27
#include "gdb_string.h"         /* For memcpy declaration */
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
  struct bstring *next;
41
  size_t length;
42
 
43
  union
44
  {
45
    char data[1];
46
    double dummy;
47
  }
48
  d;
49
};
50
 
51
 
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.  */
55
 
56
struct bcache
57
{
58
  /* All the bstrings are allocated here.  */
59
  struct obstack cache;
60
 
61
  /* How many hash buckets we're using.  */
62
  unsigned int num_buckets;
63
 
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;
67
 
68
  /* Statistics.  */
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 */
74
};
75
 
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.
78
 */
79
 
80
unsigned long
81
hash(const void *addr, int length)
82
{
83
                const unsigned char *k, *e;
84
                unsigned long h;
85
 
86
                k = (const unsigned char *)addr;
87
                e = k+length;
88
                for (h=0; k< e;++k)
89
                {
90
                                h *=16777619;
91
                                h ^= *k;
92
                }
93
                return (h);
94
}
95
 
96
/* Growing the bcache's hash table.  */
97
 
98
/* If the average chain length grows beyond this, then we want to
99
   resize our hash table.  */
100
#define CHAIN_LENGTH_THRESHOLD (5)
101
 
102
static void
103
expand_hash_table (struct bcache *bcache)
104
{
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
115
  };
116
  unsigned int new_num_buckets;
117
  struct bstring **new_buckets;
118
  unsigned int i;
119
 
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)
124
      {
125
        new_num_buckets = sizes[i];
126
        break;
127
      }
128
 
129
  /* Allocate the new table.  */
130
  {
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);
134
 
135
    bcache->structure_size -= (bcache->num_buckets
136
                               * sizeof (bcache->bucket[0]));
137
    bcache->structure_size += new_size;
138
  }
139
 
140
  /* Rehash all existing strings.  */
141
  for (i = 0; i < bcache->num_buckets; i++)
142
    {
143
      struct bstring *s, *next;
144
 
145
      for (s = bcache->bucket[i]; s; s = next)
146
        {
147
          struct bstring **new_bucket;
148
          next = s->next;
149
 
150
          new_bucket = &new_buckets[(hash (&s->d.data, s->length)
151
                                     % new_num_buckets)];
152
          s->next = *new_bucket;
153
          *new_bucket = s;
154
        }
155
    }
156
 
157
  /* Plug in the new table.  */
158
  if (bcache->bucket)
159
    xfree (bcache->bucket);
160
  bcache->bucket = new_buckets;
161
  bcache->num_buckets = new_num_buckets;
162
}
163
 
164
 
165
/* Looking up things in the bcache.  */
166
 
167
/* The number of bytes needed to allocate a struct bstring whose data
168
   is N bytes long.  */
169
#define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
170
 
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.  */
174
void *
175
bcache (const void *addr, int length, struct bcache *bcache)
176
{
177
  int hash_index;
178
  struct bstring *s;
179
 
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);
183
 
184
  bcache->total_count++;
185
  bcache->total_size += length;
186
 
187
  hash_index = hash (addr, length) % bcache->num_buckets;
188
 
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))
193
      return &s->d.data;
194
 
195
  /* The user's string isn't in the list.  Insert it after *ps.  */
196
  {
197
    struct bstring *new
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;
203
 
204
    bcache->unique_count++;
205
    bcache->unique_size += length;
206
    bcache->structure_size += BSTRING_SIZE (length);
207
 
208
    return &new->d.data;
209
  }
210
}
211
 
212
 
213
/* Allocating and freeing bcaches.  */
214
 
215
struct bcache *
216
bcache_xmalloc (void)
217
{
218
  /* Allocate the bcache pre-zeroed.  */
219
  struct bcache *b = XCALLOC (1, struct bcache);
220
  obstack_specify_allocation (&b->cache, 0, 0, xmalloc, xfree);
221
  return b;
222
}
223
 
224
/* Free all the storage associated with BCACHE.  */
225
void
226
bcache_xfree (struct bcache *bcache)
227
{
228
  if (bcache == NULL)
229
    return;
230
  obstack_free (&bcache->cache, 0);
231
  xfree (bcache->bucket);
232
  xfree (bcache);
233
}
234
 
235
 
236
 
237
/* Printing statistics.  */
238
 
239
static int
240
compare_ints (const void *ap, const void *bp)
241
{
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;
245
}
246
 
247
 
248
static void
249
print_percentage (int portion, int total)
250
{
251
  if (total == 0)
252
    printf_filtered ("(not applicable)\n");
253
  else
254
    printf_filtered ("%3d%%\n", portion * 100 / total);
255
}
256
 
257
 
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
261
   its ilk.  */
262
void
263
print_bcache_statistics (struct bcache *c, char *type)
264
{
265
  int occupied_buckets;
266
  int max_chain_length;
267
  int median_chain_length;
268
 
269
  /* Count the number of occupied buckets, and measure chain lengths.  */
270
  {
271
    unsigned int b;
272
    int *chain_length
273
      = (int *) alloca (c->num_buckets * sizeof (*chain_length));
274
 
275
    occupied_buckets = 0;
276
 
277
    for (b = 0; b < c->num_buckets; b++)
278
      {
279
        struct bstring *s = c->bucket[b];
280
 
281
        chain_length[b] = 0;
282
 
283
        if (s)
284
          {
285
            occupied_buckets++;
286
 
287
            while (s)
288
              {
289
                chain_length[b]++;
290
                s = s->next;
291
              }
292
          }
293
      }
294
 
295
    /* To compute the median, we need the set of chain lengths sorted.  */
296
    qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
297
           compare_ints);
298
 
299
    if (c->num_buckets > 0)
300
      {
301
        max_chain_length = chain_length[c->num_buckets - 1];
302
        median_chain_length = chain_length[c->num_buckets / 2];
303
      }
304
    else
305
      {
306
        max_chain_length = 0;
307
        median_chain_length = 0;
308
      }
309
  }
310
 
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");
317
 
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");
323
 
324
  printf_filtered ("    Total memory used by bcache, including overhead: %ld\n",
325
                   c->structure_size);
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");
331
 
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);
340
  else
341
    printf_filtered ("(not applicable)\n");
342
  printf_filtered ("    Maximum hash chain length: %3d\n", max_chain_length);
343
  printf_filtered ("\n");
344
}
345
 
346
int
347
bcache_memory_used (struct bcache *bcache)
348
{
349
  return obstack_memory_used (&bcache->cache);
350
}

powered by: WebSVN 2.1.0

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