|
From: <sv...@va...> - 2005-07-03 17:53:23
|
Author: njn
Date: 2005-07-03 18:53:11 +0100 (Sun, 03 Jul 2005)
New Revision: 4100
Log:
Changed m_hashtable.c to allow the size of the hash table to be specified
when it is created. Fortunately this didn't affect code outside this
module except for the calls to VG_(HT_construct)().
As a result, we save some memory because not all tables have to be as big
as the ones needed for malloc/free tracking.
Modified:
trunk/cachegrind/cg_main.c
trunk/coregrind/m_hashtable.c
trunk/helgrind/hg_main.c
trunk/include/pub_tool_hashtable.h
trunk/massif/ms_main.c
trunk/memcheck/mac_malloc_wrappers.c
trunk/memcheck/mac_shared.c
Modified: trunk/cachegrind/cg_main.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
--- trunk/cachegrind/cg_main.c 2005-07-03 17:10:04 UTC (rev 4099)
+++ trunk/cachegrind/cg_main.c 2005-07-03 17:53:11 UTC (rev 4100)
@@ -118,7 +118,7 @@
static fileCC *CC_table[N_FILE_ENTRIES];
=20
//------------------------------------------------------------
-// Primary data structre #2: Instr-info table
+// Primary data structure #2: Instr-info table
// - Holds the cached info about each instr that is used for simulation.
// - table(BB_start_addr, list(instr_info))
// - For each BB, each instr_info in the list holds info about the
@@ -1160,11 +1160,11 @@
VG_(sprintf)(cachegrind_out_file, "%s/cachegrind.out.%d",
base_dir, VG_(getpid)());
=20
- instr_info_table =3D VG_(HT_construct)();
+ instr_info_table =3D VG_(HT_construct)( 4999 ); // prime, biggish
}
=20
VG_DETERMINE_INTERFACE_VERSION(cg_pre_clo_init, 0)
=20
/*--------------------------------------------------------------------*/
-/*--- end cg_main.c ---*/
+/*--- end ---*/
/*--------------------------------------------------------------------*/
Modified: trunk/coregrind/m_hashtable.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
--- trunk/coregrind/m_hashtable.c 2005-07-03 17:10:04 UTC (rev 4099)
+++ trunk/coregrind/m_hashtable.c 2005-07-03 17:53:11 UTC (rev 4100)
@@ -1,6 +1,6 @@
=20
/*--------------------------------------------------------------------*/
-/*--- A separately chained hash table. m_hashtable.c ---*/
+/*--- A separately-chained hash table. m_hashtable.c ---*/
/*--------------------------------------------------------------------*/
=20
/*
@@ -37,20 +37,13 @@
/*--- Declarations ---*/
/*--------------------------------------------------------------------*/
=20
-/* Holds malloc'd but not freed blocks. Static, so zero-inited by defau=
lt. */
-
-//#define VG_N_CHAINS 80021 /*4999*/ /* a prime number */
-
#define CHAIN_NO(key,tbl) (((UWord)(key)) % tbl->n_chains)
=20
-struct {
+struct _VgHashTable {
UInt n_chains; // should be prime
VgHashNode* chains[0];
-}
-_VgHashTable;
+};
=20
-typedef (struct _VgHashTable *) VgHashTable;
-
/*--------------------------------------------------------------------*/
/*--- Functions ---*/
/*--------------------------------------------------------------------*/
@@ -58,9 +51,10 @@
VgHashTable VG_(HT_construct)(UInt n_chains)
{
/* Initialises to zero, ie. all entries NULL */
- VgHashTable* table =3D=20
- VG_(calloc)(sizeof(struct _VgHashTable) + n_chains*sizeof(VgHashNo=
de*));
+ SizeT sz =3D sizeof(struct _VgHashTable) + n_chains*sizeof(VgHashNode=
*);
+ VgHashTable table =3D VG_(calloc)(1, sz);
table->n_chains =3D n_chains;
+ return table;
}
=20
Int VG_(HT_count_nodes) ( VgHashTable table )
@@ -75,12 +69,13 @@
return n;
}
=20
-/* Puts a new, heap allocated VgHashNode, into the malloclist. */
+/* Puts a new, heap allocated VgHashNode, into the VgHashTable. Prepend=
s
+ the node to the appropriate chain. */
void VG_(HT_add_node) ( VgHashTable table, VgHashNode* node )
{
- UInt chain =3D CHAIN_NO(node->key);
- node->next =3D table->chains[chain];
- table[chain] =3D node;
+ UInt chain =3D CHAIN_NO(node->key, table);
+ node->next =3D table->chains[chain];
+ table->chains[chain] =3D node;
}
=20
/* Looks up a VgHashNode in the table. Also returns the address of
@@ -92,7 +87,7 @@
VgHashNode *prev, *curr;
Int chain;
=20
- chain =3D CHAIN_NO(key);
+ chain =3D CHAIN_NO(key, table);
=20
prev =3D NULL;
curr =3D table->chains[chain];
@@ -106,7 +101,7 @@
}
=20
if (NULL =3D=3D prev)
- *next_ptr =3D & (table->chain[chain]);
+ *next_ptr =3D & (table->chains[chain]);
else
*next_ptr =3D & (prev->next);
=20
Modified: trunk/helgrind/hg_main.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
--- trunk/helgrind/hg_main.c 2005-07-03 17:10:04 UTC (rev 4099)
+++ trunk/helgrind/hg_main.c 2005-07-03 17:53:11 UTC (rev 4100)
@@ -3446,7 +3446,7 @@
}
=20
init_shadow_memory();
- hg_malloc_list =3D VG_(HT_construct)();
+ hg_malloc_list =3D VG_(HT_construct)( 80021 ); // prime, big
}
=20
/* Uses a 1:1 mapping */
Modified: trunk/include/pub_tool_hashtable.h
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
--- trunk/include/pub_tool_hashtable.h 2005-07-03 17:10:04 UTC (rev 4099)
+++ trunk/include/pub_tool_hashtable.h 2005-07-03 17:53:11 UTC (rev 4100)
@@ -36,8 +36,7 @@
as the first two fields match the sizes of these two fields. Require=
s
a bit of casting by the tool. */
=20
-// Problems with this type:
-// - Table is fixed-size. =20
+// Problems with this data structure:
// - Separate chaining gives bad cache behaviour. Hash tables with line=
ar
// probing give better cache behaviour.
// - It's not very abstract, eg. deleting nodes exposes more internals t=
han
@@ -50,13 +49,11 @@
}
VgHashNode;
=20
-typedef
- VgHashNode**
- VgHashTable;
+typedef struct _VgHashTable * VgHashTable;
=20
/* Make a new table. Allocates the memory with VG_(calloc)(), so can be=
freed
- * with VG_(free)(). */
-extern VgHashTable VG_(HT_construct) ( void );
+ with VG_(free)(). n_chains should be prime. */
+extern VgHashTable VG_(HT_construct) ( UInt n_chains );
=20
/* Count the number of nodes in a table. */
extern Int VG_(HT_count_nodes) ( VgHashTable table );
Modified: trunk/massif/ms_main.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
--- trunk/massif/ms_main.c 2005-07-03 17:10:04 UTC (rev 4099)
+++ trunk/massif/ms_main.c 2005-07-03 17:53:11 UTC (rev 4100)
@@ -1830,7 +1830,7 @@
VG_(register_profile_event)(VgpPrintXPts, "print-XPts");
=20
// HP_Chunks
- malloc_list =3D VG_(HT_construct)();
+ malloc_list =3D VG_(HT_construct)( 80021 ); // prime, big
=20
// Dummy node at top of the context structure.
alloc_xpt =3D new_XPt(0, NULL, /*is_bottom*/False);
Modified: trunk/memcheck/mac_malloc_wrappers.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
--- trunk/memcheck/mac_malloc_wrappers.c 2005-07-03 17:10:04 UTC (rev 409=
9)
+++ trunk/memcheck/mac_malloc_wrappers.c 2005-07-03 17:53:11 UTC (rev 410=
0)
@@ -441,7 +441,7 @@
mp->pool =3D pool;
mp->rzB =3D rzB;
mp->is_zeroed =3D is_zeroed;
- mp->chunks =3D VG_(HT_construct)();
+ mp->chunks =3D VG_(HT_construct)( 3001 ); // prime, not so big
=20
/* Paranoia ... ensure this area is off-limits to the client, so
the mp->data field isn't visible to the leak checker. If memory
Modified: trunk/memcheck/mac_shared.c
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
--- trunk/memcheck/mac_shared.c 2005-07-03 17:10:04 UTC (rev 4099)
+++ trunk/memcheck/mac_shared.c 2005-07-03 17:53:11 UTC (rev 4100)
@@ -899,8 +899,8 @@
=20
void MAC_(common_pre_clo_init)(void)
{
- MAC_(malloc_list) =3D VG_(HT_construct)();
- MAC_(mempool_list) =3D VG_(HT_construct)();
+ MAC_(malloc_list) =3D VG_(HT_construct)( 80021 ); // prime, big
+ MAC_(mempool_list) =3D VG_(HT_construct)( 1009 ); // prime, not so=
big
init_prof_mem();
}
=20
|