[deliverable/binutils-gdb.git] / gdb / bcache.c

/* Implement a cached obstack.
   Written by Fred Fish <fnf@cygnus.com>
   Rewritten by Jim Blandy <jimb@cygnus.com>
   Copyright 1999, 2000 Free Software Foundation, Inc.

   This file is part of GDB.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.  */

#include <stddef.h>
#include <stdlib.h>

#include "defs.h"
#include "obstack.h"
#include "bcache.h"
#include "gdb_string.h"		/* For memcpy declaration */

/* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
 * and is better than the old one. 
 */
\f
unsigned long
hash(void *addr, int length)
{
		const unsigned char *k, *e;
		unsigned long h;
		
		k = (const unsigned char *)addr;
		e = k+length;
		for (h=0; k< e;++k)
		{
				h *=16777619;
				h ^= *k;
		}
		return (h);
}
\f
/* Growing the bcache's hash table.  */

/* If the average chain length grows beyond this, then we want to
   resize our hash table.  */
#define CHAIN_LENGTH_THRESHOLD (5)

static void
expand_hash_table (struct bcache *bcache)
{
  /* A table of good hash table sizes.  Whenever we grow, we pick the
     next larger size from this table.  sizes[i] is close to 1 << (i+10),
     so we roughly double the table size each time.  After we fall off 
     the end of this table, we just double.  Don't laugh --- there have
     been executables sighted with a gigabyte of debug info.  */
  static unsigned long sizes[] = { 
    1021, 2053, 4099, 8191, 16381, 32771,
    65537, 131071, 262144, 524287, 1048573, 2097143,
    4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
    268435459, 536870923, 1073741827, 2147483659UL
  };
  unsigned int new_num_buckets;
  struct bstring **new_buckets;
  unsigned int i;

  /* Find the next size.  */
  new_num_buckets = bcache->num_buckets * 2;
  for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
    if (sizes[i] > bcache->num_buckets)
      {
	new_num_buckets = sizes[i];
	break;
      }

  /* Allocate the new table.  */
  {
    size_t new_size = new_num_buckets * sizeof (new_buckets[0]);
    new_buckets = (struct bstring **) xmalloc (new_size);
    memset (new_buckets, 0, new_size);

    bcache->structure_size -= (bcache->num_buckets
			       * sizeof (bcache->bucket[0]));
    bcache->structure_size += new_size;
  }

  /* Rehash all existing strings.  */
  for (i = 0; i < bcache->num_buckets; i++)
    {
      struct bstring *s, *next;

      for (s = bcache->bucket[i]; s; s = next)
	{
	  struct bstring **new_bucket;
	  next = s->next;

	  new_bucket = &new_buckets[(hash (&s->d.data, s->length)
				     % new_num_buckets)];
	  s->next = *new_bucket;
	  *new_bucket = s;
	}
    }

  /* Plug in the new table.  */
  if (bcache->bucket)
    xfree (bcache->bucket);
  bcache->bucket = new_buckets;
  bcache->num_buckets = new_num_buckets;
}

\f
/* Looking up things in the bcache.  */

/* The number of bytes needed to allocate a struct bstring whose data
   is N bytes long.  */
#define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))

/* Find a copy of the LENGTH bytes at ADDR in BCACHE.  If BCACHE has
   never seen those bytes before, add a copy of them to BCACHE.  In
   either case, return a pointer to BCACHE's copy of that string.  */
void *
bcache (void *addr, int length, struct bcache *bcache)
{
  int hash_index;
  struct bstring *s;

  /* If our average chain length is too high, expand the hash table.  */
  if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD)
    expand_hash_table (bcache);

  bcache->total_count++;
  bcache->total_size += length;

  hash_index = hash (addr, length) % bcache->num_buckets;

  /* Search the hash bucket for a string identical to the caller's.  */
  for (s = bcache->bucket[hash_index]; s; s = s->next)
    if (s->length == length
	&& ! memcmp (&s->d.data, addr, length))
      return &s->d.data;

  /* The user's string isn't in the list.  Insert it after *ps.  */
  {
    struct bstring *new
      = obstack_alloc (&bcache->cache, BSTRING_SIZE (length));
    memcpy (&new->d.data, addr, length);
    new->length = length;
    new->next = bcache->bucket[hash_index];
    bcache->bucket[hash_index] = new;

    bcache->unique_count++;
    bcache->unique_size += length;
    bcache->structure_size += BSTRING_SIZE (length);

    return &new->d.data;
  }
}

\f
/* Freeing bcaches.  */

/* Free all the storage associated with BCACHE.  */
void
free_bcache (struct bcache *bcache)
{
  obstack_free (&bcache->cache, 0);
  if (bcache->bucket)
    xfree (bcache->bucket);

  /* This isn't necessary, but at least the bcache is always in a
     consistent state.  */
  memset (bcache, 0, sizeof (*bcache));
}


\f
/* Printing statistics.  */

static int
compare_ints (const void *ap, const void *bp)
{
  /* Because we know we're comparing two ints which are positive,
     there's no danger of overflow here.  */
  return * (int *) ap - * (int *) bp;
}


static void
print_percentage (int portion, int total)
{
  if (total == 0)
    printf_filtered ("(not applicable)\n");
  else
    printf_filtered ("%3d%%\n", portion * 100 / total);
}


/* Print statistics on BCACHE's memory usage and efficacity at
   eliminating duplication.  NAME should describe the kind of data
   BCACHE holds.  Statistics are printed using `printf_filtered' and
   its ilk.  */
void
print_bcache_statistics (struct bcache *c, char *type)
{
  int occupied_buckets;
  int max_chain_length;
  int median_chain_length;

  /* Count the number of occupied buckets, and measure chain lengths.  */
  {
    unsigned int b;
    int *chain_length
      = (int *) alloca (c->num_buckets * sizeof (*chain_length));

    occupied_buckets = 0;

    for (b = 0; b < c->num_buckets; b++)
      {
	struct bstring *s = c->bucket[b];

	chain_length[b] = 0;

	if (s)
	  {
	    occupied_buckets++;
	    
	    while (s)
	      {
		chain_length[b]++;
		s = s->next;
	      }
	  }
      }

    /* To compute the median, we need the set of chain lengths sorted.  */
    qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
	   compare_ints);

    if (c->num_buckets > 0)
      {
	max_chain_length = chain_length[c->num_buckets - 1];
	median_chain_length = chain_length[c->num_buckets / 2];
      }
    else
      {
	max_chain_length = 0;
	median_chain_length = 0;
      }
  }

  printf_filtered ("  Cached '%s' statistics:\n", type);
  printf_filtered ("    Total object count:  %ld\n", c->total_count);
  printf_filtered ("    Unique object count: %lu\n", c->unique_count);
  printf_filtered ("    Percentage of duplicates, by count: ");
  print_percentage (c->total_count - c->unique_count, c->total_count);
  printf_filtered ("\n");

  printf_filtered ("    Total object size:   %ld\n", c->total_size);
  printf_filtered ("    Unique object size:  %ld\n", c->unique_size);
  printf_filtered ("    Percentage of duplicates, by size:  ");
  print_percentage (c->total_size - c->unique_size, c->total_size);
  printf_filtered ("\n");

  printf_filtered ("    Total memory used by bcache, including overhead: %ld\n",
		   c->structure_size);
  printf_filtered ("    Percentage memory overhead: ");
  print_percentage (c->structure_size - c->unique_size, c->unique_size);
  printf_filtered ("    Net memory savings:         ");
  print_percentage (c->total_size - c->structure_size, c->total_size);
  printf_filtered ("\n");

  printf_filtered ("    Hash table size:           %3d\n", c->num_buckets);
  printf_filtered ("    Hash table population:     ");
  print_percentage (occupied_buckets, c->num_buckets);
  printf_filtered ("    Median hash chain length:  %3d\n",
		   median_chain_length);
  printf_filtered ("    Average hash chain length: ");
  if (c->num_buckets > 0)
    printf_filtered ("%3lu\n", c->unique_count / c->num_buckets);
  else
    printf_filtered ("(not applicable)\n");
  printf_filtered ("    Maximum hash chain length: %3d\n", max_chain_length);
  printf_filtered ("\n");
}
Commit	Line	Data
	1	/* Implement a cached obstack.
	2	Written by Fred Fish <fnf@cygnus.com>
	3	Rewritten by Jim Blandy <jimb@cygnus.com>
	4	Copyright 1999, 2000 Free Software Foundation, Inc.
	5
	6	This file is part of GDB.
	7
	8	This program is free software; you can redistribute it and/or modify
	9	it under the terms of the GNU General Public License as published by
	10	the Free Software Foundation; either version 2 of the License, or
	11	(at your option) any later version.
	12
	13	This program is distributed in the hope that it will be useful,
	14	but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	16	GNU General Public License for more details.
	17
	18	You should have received a copy of the GNU General Public License
	19	along with this program; if not, write to the Free Software
	20	Foundation, Inc., 59 Temple Place - Suite 330,
	21	Boston, MA 02111-1307, USA. */
	22
	23	#include <stddef.h>
	24	#include <stdlib.h>
	25
	26	#include "defs.h"
	27	#include "obstack.h"
	28	#include "bcache.h"
	29	#include "gdb_string.h" /* For memcpy declaration */
	30
	31	/* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
	32	* and is better than the old one.
	33	*/
	34	\f
	35	unsigned long
	36	hash(void *addr, int length)
	37	{
	38	const unsigned char k, e;
	39	unsigned long h;
	40
	41	k = (const unsigned char *)addr;
	42	e = k+length;
	43	for (h=0; k< e;++k)
	44	{
	45	h *=16777619;
	46	h ^= *k;
	47	}
	48	return (h);
	49	}
	50	\f
	51	/* Growing the bcache's hash table. */
	52
	53	/* If the average chain length grows beyond this, then we want to
	54	resize our hash table. */
	55	#define CHAIN_LENGTH_THRESHOLD (5)
	56
	57	static void
	58	expand_hash_table (struct bcache *bcache)
	59	{
	60	/* A table of good hash table sizes. Whenever we grow, we pick the
	61	next larger size from this table. sizes[i] is close to 1 << (i+10),
	62	so we roughly double the table size each time. After we fall off
	63	the end of this table, we just double. Don't laugh --- there have
	64	been executables sighted with a gigabyte of debug info. */
	65	static unsigned long sizes[] = {
	66	1021, 2053, 4099, 8191, 16381, 32771,
	67	65537, 131071, 262144, 524287, 1048573, 2097143,
	68	4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
	69	268435459, 536870923, 1073741827, 2147483659UL
	70	};
	71	unsigned int new_num_buckets;
	72	struct bstring **new_buckets;
	73	unsigned int i;
	74
	75	/* Find the next size. */
	76	new_num_buckets = bcache->num_buckets * 2;
	77	for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
	78	if (sizes[i] > bcache->num_buckets)
	79	{
	80	new_num_buckets = sizes[i];
	81	break;
	82	}
	83
	84	/* Allocate the new table. */
	85	{
	86	size_t new_size = new_num_buckets * sizeof (new_buckets[0]);
	87	new_buckets = (struct bstring **) xmalloc (new_size);
	88	memset (new_buckets, 0, new_size);
	89
	90	bcache->structure_size -= (bcache->num_buckets
	91	* sizeof (bcache->bucket[0]));
	92	bcache->structure_size += new_size;
	93	}
	94
	95	/* Rehash all existing strings. */
	96	for (i = 0; i < bcache->num_buckets; i++)
	97	{
	98	struct bstring s, next;
	99
	100	for (s = bcache->bucket[i]; s; s = next)
	101	{
	102	struct bstring **new_bucket;
	103	next = s->next;
	104
	105	new_bucket = &new_buckets[(hash (&s->d.data, s->length)
	106	% new_num_buckets)];
	107	s->next = *new_bucket;
	108	*new_bucket = s;
	109	}
	110	}
	111
	112	/* Plug in the new table. */
	113	if (bcache->bucket)
	114	xfree (bcache->bucket);
	115	bcache->bucket = new_buckets;
	116	bcache->num_buckets = new_num_buckets;
	117	}
	118
	119	\f
	120	/* Looking up things in the bcache. */
	121
	122	/* The number of bytes needed to allocate a struct bstring whose data
	123	is N bytes long. */
	124	#define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
	125
	126	/* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
	127	never seen those bytes before, add a copy of them to BCACHE. In
	128	either case, return a pointer to BCACHE's copy of that string. */
	129	void *
	130	bcache (void addr, int length, struct bcache bcache)
	131	{
	132	int hash_index;
	133	struct bstring *s;
	134
	135	/* If our average chain length is too high, expand the hash table. */
	136	if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD)
	137	expand_hash_table (bcache);
	138
	139	bcache->total_count++;
	140	bcache->total_size += length;
	141
	142	hash_index = hash (addr, length) % bcache->num_buckets;
	143
	144	/* Search the hash bucket for a string identical to the caller's. */
	145	for (s = bcache->bucket[hash_index]; s; s = s->next)
	146	if (s->length == length
	147	&& ! memcmp (&s->d.data, addr, length))
	148	return &s->d.data;
	149
	150	/* The user's string isn't in the list. Insert it after ps. /
	151	{
	152	struct bstring *new
	153	= obstack_alloc (&bcache->cache, BSTRING_SIZE (length));
	154	memcpy (&new->d.data, addr, length);
	155	new->length = length;
	156	new->next = bcache->bucket[hash_index];
	157	bcache->bucket[hash_index] = new;
	158
	159	bcache->unique_count++;
	160	bcache->unique_size += length;
	161	bcache->structure_size += BSTRING_SIZE (length);
	162
	163	return &new->d.data;
	164	}
	165	}
	166
	167	\f
	168	/* Freeing bcaches. */
	169
	170	/* Free all the storage associated with BCACHE. */
	171	void
	172	free_bcache (struct bcache *bcache)
	173	{
	174	obstack_free (&bcache->cache, 0);
	175	if (bcache->bucket)
	176	xfree (bcache->bucket);
	177
	178	/* This isn't necessary, but at least the bcache is always in a
	179	consistent state. */
	180	memset (bcache, 0, sizeof (*bcache));
	181	}
	182
	183
	184	\f
	185	/* Printing statistics. */
	186
	187	static int
	188	compare_ints (const void ap, const void bp)
	189	{
	190	/* Because we know we're comparing two ints which are positive,
	191	there's no danger of overflow here. */
	192	return * (int ) ap - (int *) bp;
	193	}
	194
	195
	196	static void
	197	print_percentage (int portion, int total)
	198	{
	199	if (total == 0)
	200	printf_filtered ("(not applicable)\n");
	201	else
	202	printf_filtered ("%3d%%\n", portion * 100 / total);
	203	}
	204
	205
	206	/* Print statistics on BCACHE's memory usage and efficacity at
	207	eliminating duplication. NAME should describe the kind of data
	208	BCACHE holds. Statistics are printed using `printf_filtered' and
	209	its ilk. */
	210	void
	211	print_bcache_statistics (struct bcache c, char type)
	212	{
	213	int occupied_buckets;
	214	int max_chain_length;
	215	int median_chain_length;
	216
	217	/* Count the number of occupied buckets, and measure chain lengths. */
	218	{
	219	unsigned int b;
	220	int *chain_length
	221	= (int ) alloca (c->num_buckets sizeof (*chain_length));
	222
	223	occupied_buckets = 0;
	224
	225	for (b = 0; b < c->num_buckets; b++)
	226	{
	227	struct bstring *s = c->bucket[b];
	228
	229	chain_length[b] = 0;
	230
	231	if (s)
	232	{
	233	occupied_buckets++;
	234
	235	while (s)
	236	{
	237	chain_length[b]++;
	238	s = s->next;
	239	}
	240	}
	241	}
	242
	243	/* To compute the median, we need the set of chain lengths sorted. */
	244	qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
	245	compare_ints);
	246
	247	if (c->num_buckets > 0)
	248	{
	249	max_chain_length = chain_length[c->num_buckets - 1];
	250	median_chain_length = chain_length[c->num_buckets / 2];
	251	}
	252	else
	253	{
	254	max_chain_length = 0;
	255	median_chain_length = 0;
	256	}
	257	}
	258
	259	printf_filtered (" Cached '%s' statistics:\n", type);
	260	printf_filtered (" Total object count: %ld\n", c->total_count);
	261	printf_filtered (" Unique object count: %lu\n", c->unique_count);
	262	printf_filtered (" Percentage of duplicates, by count: ");
	263	print_percentage (c->total_count - c->unique_count, c->total_count);
	264	printf_filtered ("\n");
	265
	266	printf_filtered (" Total object size: %ld\n", c->total_size);
	267	printf_filtered (" Unique object size: %ld\n", c->unique_size);
	268	printf_filtered (" Percentage of duplicates, by size: ");
	269	print_percentage (c->total_size - c->unique_size, c->total_size);
	270	printf_filtered ("\n");
	271
	272	printf_filtered (" Total memory used by bcache, including overhead: %ld\n",
	273	c->structure_size);
	274	printf_filtered (" Percentage memory overhead: ");
	275	print_percentage (c->structure_size - c->unique_size, c->unique_size);
	276	printf_filtered (" Net memory savings: ");
	277	print_percentage (c->total_size - c->structure_size, c->total_size);
	278	printf_filtered ("\n");
	279
	280	printf_filtered (" Hash table size: %3d\n", c->num_buckets);
	281	printf_filtered (" Hash table population: ");
	282	print_percentage (occupied_buckets, c->num_buckets);
	283	printf_filtered (" Median hash chain length: %3d\n",
	284	median_chain_length);
	285	printf_filtered (" Average hash chain length: ");
	286	if (c->num_buckets > 0)
	287	printf_filtered ("%3lu\n", c->unique_count / c->num_buckets);
	288	else
	289	printf_filtered ("(not applicable)\n");
	290	printf_filtered (" Maximum hash chain length: %3d\n", max_chain_length);
	291	printf_filtered ("\n");
	292	}