* [RFC] Symbol table hashing patch
@ 2001-10-01 15:46 Daniel Jacobowitz
2001-10-01 16:05 ` Elena Zannoni
0 siblings, 1 reply; 4+ messages in thread
From: Daniel Jacobowitz @ 2001-10-01 15:46 UTC (permalink / raw)
To: gdb-patches
I've taken the patches Daniel Berlin sent me to implement hashed symtabs and
gone over them thoroughly over the past week, and I have something I would
like to see committed. This is an RFC instead of an RFA because I have a
few small FIXME comments I'd like feedback on first, though.
The general structure of the patch:
- First of all, I introduced a macro for looking at all the symbols in a
given block (ALL_BLOCK_SYMBOLS). I then changed all sites. This
changes the order in which symbols will be seen, but with a few
exceptions (below), that's fine. The large change in printcmd.c
is almost entirely whitespace; do not be alarmed unduly :)
- I fixed a logic bug in msymtab_hash_iw.
- I added code to lookup_block_symbol to use the hashtable; nothing
surprising here.
- Based on some experimentation, and Daniel's patch, I increased
MINIMAL_SYMBOL_HASH_SIZE; I went over a set of random binaries
and objfiles on my system, and this seems like a reasonable change.
The C library, for instance, has 1933 msyms; gdb has 3670 without
debug info and 7475 with. A hash table with 349 buckets, while not
entirely unreasonable, seemed a little small. This change is
unrelated to the others, though, if people disagree with it.
- I went to the other symbol readers et al. which create blocks on their
own (dstread.c, jv-lang.c, and mdebugread.c), and made sure that
they marked the blocks they built as unhashed. Better would be to
make them use the normal interface for doing this, but without
any way to test such changes I'm not going to. I'm a little
bit nervous about mdebugread.c in particular, but I'm reasonably
sure that I'm correct.
Now, for the parts I'd like comments on:
- coffread.c:patch_opaque_types used to walk the symbol table backwards,
before it was sorted. Is this important? From the comments I could
not tell.
- Cosmetically, the output of dump_symtab changed. I don't think it's
worth sorting just for this. It causes one testsuite regression,
which I'll fix by tweaking the testsuite if no one insists on sorting.
- Daniel noticed a scary block in search_symbols:
/* Skip the sort if this block is always sorted. */
if (!BLOCK_SHOULD_SORT (b))
sort_block_syms (b);
BLOCK_SHOULD_SORT was formerly "if the block has more than 40 symbols
and is not order-sensitive (list of function arguments, etc)". Sorting
such a function block seems like a very bad idea. OK to remove this?
search_symbols doesn't even need a sorted block; it searches all entries
anyway. The results will no longer be sorted; if it is prefered, we can
sort the results after searching is complete.
--
Daniel Jacobowitz Carnegie Mellon University
MontaVista Software Debian GNU/Linux Developer
2001-10-01 Daniel Jacobowitz <drow@mvista.com>
Based on patch from Daniel Berlin <dan@cgsoftware.com>.
* buildsym.c: Include "demangle.h" for SYMBOL_INIT_DEMANGLED_NAME.
(finish_block) For non-function blocks, hash the symbol table. For
function blocks, mark the symbol table as unhashed.
* minsyms.c (msymbol_hash): Use better hash function.
Return hash value without taking modulus.
(msymbol_hash_iw): Likewise. Terminate loop at '(' properly.
(add_minsym_to_hash_table): Take modulus of msymbol_hash's return
value.
(add_minsym_to_demangled_hash_table): Likewise for msymbol_hash_iw.
(lookup_minimal_symbol): Likewise for both.
* symtab.h (struct block): Add `hashtable' flag.
(BLOCK_HASHTABLE): New macro.
(BLOCK_BUCKETS): New macro.
(BLOCK_BUCKET): New macro.
(ALL_BLOCK_SYMBOLS): New macro.
(BLOCK_SHOULD_SORT): Do not sort hashed blocks.
(struct symbol): Add `hash_next' pointer.
* symtab.c (lookup_block_symbol): Search using the hash table when
possible.
(find_pc_sect_symtab): Use ALL_BLOCK_SYMBOLS.
(search_symbols): Do not attempt to sort hashed blocks or function
blocks. Use ALL_BLOCK_SYMBOLS.
(make_symbol_completion_list): Use ALL_BLOCK_SYMBOLS.
(make_symbol_overload_list): Likewise.
* objfiles.h: Increase MINIMAL_SYMBOL_HASH_SIZE.
* dstread.c (process_dst_block): Clear hashtable bit for new block.
(read_dst_symtab): Likewise.
* jv-lang.c (get_java_class_symtab): Likewise.
* mdebugread.c: Include "gdb_assert.h".
(shrink_block): Assert that the block being modified is not hashed.
* symmisc.c (free_symtab_block): Walk the hash table when freeing
symbols.
(dump_symtab): Recognize hashed blocks. Use ALL_BLOCK_SYMBOLS.
* breakpoint.c (get_catch_sals): Use ALL_BLOCK_SYMBOLS.
* coffread.c (patch_opaque_types): Likewise.
* objfiles.c (objfile_relocate): Likewise.
* stack.c (print_block_frame_locals): Likewise.
(print_block_frame_labels): Likewise.
(print_frame_arg_vars): Likewise.
* tracepoint.c (add_local_symbols): Likewise.
(scope_info): Likewise.
* printcmd.c (print_frame_args): Likewise. Assert that
function blocks do not have hashed symbol tables.
Index: gdb/breakpoint.c
===================================================================
RCS file: /cvs/src/src/gdb/breakpoint.c,v
retrieving revision 1.53
diff -u -p -r1.53 breakpoint.c
--- breakpoint.c 2001/09/18 05:00:48 1.53
+++ breakpoint.c 2001/10/01 22:20:38
@@ -5871,15 +5871,11 @@ get_catch_sals (int this_level_only)
if (blocks_searched[index] == 0)
{
struct block *b = BLOCKVECTOR_BLOCK (bl, index);
- int nsyms;
register int i;
register struct symbol *sym;
- nsyms = BLOCK_NSYMS (b);
-
- for (i = 0; i < nsyms; i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
if (STREQ (SYMBOL_NAME (sym), "default"))
{
if (have_default)
Index: gdb/buildsym.c
===================================================================
RCS file: /cvs/src/src/gdb/buildsym.c,v
retrieving revision 1.11
diff -u -p -r1.11 buildsym.c
--- buildsym.c 2001/04/30 10:30:27 1.11
+++ buildsym.c 2001/10/01 22:20:39
@@ -39,6 +39,7 @@
#include "language.h" /* For "longest_local_hex_string_custom" */
#include "bcache.h"
#include "filenames.h" /* For DOSish file names */
+#include "demangle.h" /* Needed by SYMBOL_INIT_DEMANGLED_NAME */
/* Ask buildsym.h to define the vars it normally declares `extern'. */
#define EXTERN
/**/
@@ -239,17 +240,45 @@ finish_block (struct symbol *symbol, str
/* EMPTY */ ;
}
- block = (struct block *) obstack_alloc (&objfile->symbol_obstack,
- (sizeof (struct block) + ((i - 1) * sizeof (struct symbol *))));
-
/* Copy the symbols into the block. */
- BLOCK_NSYMS (block) = i;
- for (next = *listhead; next; next = next->next)
+ if (symbol)
+ {
+ block = (struct block *)
+ obstack_alloc (&objfile->symbol_obstack,
+ (sizeof (struct block) +
+ ((i - 1) * sizeof (struct symbol *))));
+ BLOCK_NSYMS (block) = i;
+ for (next = *listhead; next; next = next->next)
+ for (j = next->nsyms - 1; j >= 0; j--)
+ {
+ BLOCK_SYM (block, --i) = next->symbol[j];
+ }
+ }
+ else
{
- for (j = next->nsyms - 1; j >= 0; j--)
+ block = (struct block *)
+ obstack_alloc (&objfile->symbol_obstack,
+ (sizeof (struct block) +
+ ((i / 5) * sizeof (struct symbol *))));
+ for (j = 0; j < ((i / 5) + 1); j++)
{
- BLOCK_SYM (block, --i) = next->symbol[j];
+ BLOCK_BUCKET (block, j) = 0;
+ }
+ BLOCK_BUCKETS (block) = (i / 5) + 1;
+ for (next = *listhead; next; next = next->next)
+ {
+ for (j = next->nsyms - 1; j >= 0; j--)
+ {
+ struct symbol *sym;
+ unsigned int hash_index;
+ SYMBOL_INIT_DEMANGLED_NAME (next->symbol[j], &objfile->symbol_obstack);
+ hash_index = msymbol_hash_iw (SYMBOL_SOURCE_NAME (next->symbol[j]));
+ hash_index = hash_index % BLOCK_BUCKETS (block);
+ sym = BLOCK_BUCKET (block, hash_index);
+ BLOCK_BUCKET (block, hash_index) = next->symbol[j];
+ next->symbol[j]->hash_next = sym;
+ }
}
}
@@ -267,6 +296,7 @@ finish_block (struct symbol *symbol, str
struct type *ftype = SYMBOL_TYPE (symbol);
SYMBOL_BLOCK_VALUE (symbol) = block;
BLOCK_FUNCTION (block) = symbol;
+ BLOCK_HASHTABLE (block) = 0;
if (TYPE_NFIELDS (ftype) <= 0)
{
@@ -348,6 +378,7 @@ finish_block (struct symbol *symbol, str
else
{
BLOCK_FUNCTION (block) = NULL;
+ BLOCK_HASHTABLE (block) = 1;
}
/* Now "free" the links of the list, and empty the list. */
Index: gdb/coffread.c
===================================================================
RCS file: /cvs/src/src/gdb/coffread.c,v
retrieving revision 1.20
diff -u -p -r1.20 coffread.c
--- coffread.c 2001/09/20 03:03:39 1.20
+++ coffread.c 2001/10/01 22:20:40
@@ -1446,13 +1446,13 @@ patch_opaque_types (struct symtab *s)
/* Go through the per-file symbols only */
b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), STATIC_BLOCK);
- for (i = BLOCK_NSYMS (b) - 1; i >= 0; i--)
+ /* FIXMED: Originally all symbols, in reverse order, before they are sorted. */
+ ALL_BLOCK_SYMBOLS (b, i, real_sym)
{
/* Find completed typedefs to use to fix opaque ones.
Remove syms from the chain when their types are stored,
but search the whole chain, as there may be several syms
from different files with the same name. */
- real_sym = BLOCK_SYM (b, i);
if (SYMBOL_CLASS (real_sym) == LOC_TYPEDEF &&
SYMBOL_NAMESPACE (real_sym) == VAR_NAMESPACE &&
TYPE_CODE (SYMBOL_TYPE (real_sym)) == TYPE_CODE_PTR &&
Index: gdb/dstread.c
===================================================================
RCS file: /cvs/src/src/gdb/dstread.c,v
retrieving revision 1.7
diff -u -p -r1.7 dstread.c
--- dstread.c 2001/03/06 08:21:06 1.7
+++ dstread.c 2001/10/01 22:20:41
@@ -1407,6 +1407,7 @@ process_dst_block (struct objfile *objfi
symnum++;
}
BLOCK_NSYMS (block) = total_symbols;
+ BLOCK_HASHTABLE (block) = 0;
BLOCK_START (block) = address;
BLOCK_END (block) = address + size;
BLOCK_SUPERBLOCK (block) = 0;
@@ -1491,6 +1492,7 @@ read_dst_symtab (struct objfile *objfile
(total_globals - 1) *
sizeof (struct symbol *));
BLOCK_NSYMS (global_block) = total_globals;
+ BLOCK_HASHTABLE (global_block) = 0;
for (symnum = 0; symnum < total_globals; symnum++)
{
nextsym = dst_global_symbols->next;
Index: gdb/jv-lang.c
===================================================================
RCS file: /cvs/src/src/gdb/jv-lang.c,v
retrieving revision 1.7
diff -u -p -r1.7 jv-lang.c
--- jv-lang.c 2001/03/23 22:48:44 1.7
+++ jv-lang.c 2001/10/01 22:20:42
@@ -106,6 +106,7 @@ get_java_class_symtab (void)
bl = (struct block *)
obstack_alloc (&objfile->symbol_obstack, sizeof (struct block));
BLOCK_NSYMS (bl) = 0;
+ BLOCK_HASHTABLE (bl) = 0;
BLOCK_START (bl) = 0;
BLOCK_END (bl) = 0;
BLOCK_FUNCTION (bl) = NULL;
Index: gdb/mdebugread.c
===================================================================
RCS file: /cvs/src/src/gdb/mdebugread.c,v
retrieving revision 1.15
diff -u -p -r1.15 mdebugread.c
--- mdebugread.c 2001/09/05 02:54:15 1.15
+++ mdebugread.c 2001/10/01 22:20:46
@@ -52,6 +52,7 @@
#include "stabsread.h"
#include "complaints.h"
#include "demangle.h"
+#include "gdb_assert.h"
/* These are needed if the tm.h file does not contain the necessary
mips specific definitions. */
@@ -4154,6 +4155,11 @@ shrink_block (struct block *b, struct sy
(sizeof (struct block)
+ ((BLOCK_NSYMS (b) - 1)
* sizeof (struct symbol *))));
+
+ /* FIXME: Not worth hashing this block as it's built. */
+ /* All callers should have created the block with new_block (), which
+ would mean it was not previously hashed. Make sure. */
+ gdb_assert (BLOCK_HASHTABLE (new) == 0);
/* Should chase pointers to old one. Fortunately, that`s just
the block`s function and inferior blocks */
Index: gdb/minsyms.c
===================================================================
RCS file: /cvs/src/src/gdb/minsyms.c,v
retrieving revision 1.17
diff -u -p -r1.17 minsyms.c
--- minsyms.c 2001/05/29 10:45:10 1.17
+++ minsyms.c 2001/10/01 22:20:47
@@ -96,10 +96,12 @@ msymbol_hash_iw (const char *string)
while (isspace (*string))
++string;
if (*string && *string != '(')
- hash = (31 * hash) + *string;
- ++string;
+ {
+ hash = hash * 67 + *string - 113;
+ ++string;
+ }
}
- return hash % MINIMAL_SYMBOL_HASH_SIZE;
+ return hash;
}
/* Compute a hash code for a string. */
@@ -109,8 +111,8 @@ msymbol_hash (const char *string)
{
unsigned int hash = 0;
for (; *string; ++string)
- hash = (31 * hash) + *string;
- return hash % MINIMAL_SYMBOL_HASH_SIZE;
+ hash = hash * 67 + *string - 113;
+ return hash;
}
/* Add the minimal symbol SYM to an objfile's minsym hash table, TABLE. */
@@ -120,7 +122,7 @@ add_minsym_to_hash_table (struct minimal
{
if (sym->hash_next == NULL)
{
- unsigned int hash = msymbol_hash (SYMBOL_NAME (sym));
+ unsigned int hash = msymbol_hash (SYMBOL_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE;
sym->hash_next = table[hash];
table[hash] = sym;
}
@@ -134,7 +136,7 @@ add_minsym_to_demangled_hash_table (stru
{
if (sym->demangled_hash_next == NULL)
{
- unsigned int hash = msymbol_hash_iw (SYMBOL_DEMANGLED_NAME (sym));
+ unsigned int hash = msymbol_hash_iw (SYMBOL_DEMANGLED_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE;
sym->demangled_hash_next = table[hash];
table[hash] = sym;
}
@@ -162,8 +164,8 @@ lookup_minimal_symbol (register const ch
struct minimal_symbol *found_file_symbol = NULL;
struct minimal_symbol *trampoline_symbol = NULL;
- unsigned int hash = msymbol_hash (name);
- unsigned int dem_hash = msymbol_hash_iw (name);
+ unsigned int hash = msymbol_hash (name) % MINIMAL_SYMBOL_HASH_SIZE;
+ unsigned int dem_hash = msymbol_hash_iw (name) % MINIMAL_SYMBOL_HASH_SIZE;
#ifdef SOFUN_ADDRESS_MAYBE_MISSING
if (sfile != NULL)
Index: gdb/objfiles.c
===================================================================
RCS file: /cvs/src/src/gdb/objfiles.c,v
retrieving revision 1.16
diff -u -p -r1.16 objfiles.c
--- objfiles.c 2001/07/05 21:32:39 1.16
+++ objfiles.c 2001/10/01 22:20:53
@@ -557,16 +557,15 @@ objfile_relocate (struct objfile *objfil
for (i = 0; i < BLOCKVECTOR_NBLOCKS (bv); ++i)
{
struct block *b;
+ struct symbol *sym;
int j;
b = BLOCKVECTOR_BLOCK (bv, i);
BLOCK_START (b) += ANOFFSET (delta, s->block_line_section);
BLOCK_END (b) += ANOFFSET (delta, s->block_line_section);
- for (j = 0; j < BLOCK_NSYMS (b); ++j)
+ ALL_BLOCK_SYMBOLS (b, j, sym)
{
- struct symbol *sym = BLOCK_SYM (b, j);
-
fixup_symbol_section (sym, objfile);
/* The RS6000 code from which this was taken skipped
Index: gdb/objfiles.h
===================================================================
RCS file: /cvs/src/src/gdb/objfiles.h,v
retrieving revision 1.8
diff -u -p -r1.8 objfiles.h
--- objfiles.h 2001/03/06 08:21:11 1.8
+++ objfiles.h 2001/10/01 22:20:53
@@ -202,7 +202,7 @@ extern void print_objfile_statistics (vo
extern void print_symbol_bcache_statistics (void);
/* Number of entries in the minimal symbol hash table. */
-#define MINIMAL_SYMBOL_HASH_SIZE 349
+#define MINIMAL_SYMBOL_HASH_SIZE 2039
/* Master structure for keeping track of each file from which
gdb reads symbols. There are several ways these get allocated: 1.
Index: gdb/printcmd.c
===================================================================
RCS file: /cvs/src/src/gdb/printcmd.c,v
retrieving revision 1.27
diff -u -p -r1.27 printcmd.c
--- printcmd.c 2001/09/12 04:18:08 1.27
+++ printcmd.c 2001/10/01 22:20:54
@@ -38,6 +38,7 @@
#include "symfile.h" /* for overlay functions */
#include "objfiles.h" /* ditto */
#include "completer.h" /* for completion functions */
+#include "gdb_assert.h"
#ifdef UI_OUT
#include "ui-out.h"
#endif
@@ -1806,168 +1807,171 @@ print_frame_args (struct symbol *func, s
if (func)
{
b = SYMBOL_BLOCK_VALUE (func);
+ /* Function blocks are order sensitive, and thus should not be
+ hashed. */
+ gdb_assert (BLOCK_HASHTABLE (b) == 0);
nsyms = BLOCK_NSYMS (b);
- }
- for (i = 0; i < nsyms; i++)
- {
- QUIT;
- sym = BLOCK_SYM (b, i);
+ ALL_BLOCK_SYMBOLS (b, i, sym);
+ {
+ QUIT;
+ sym = BLOCK_SYM (b, i);
- /* Keep track of the highest stack argument offset seen, and
- skip over any kinds of symbols we don't care about. */
+ /* Keep track of the highest stack argument offset seen, and
+ skip over any kinds of symbols we don't care about. */
- switch (SYMBOL_CLASS (sym))
- {
- case LOC_ARG:
- case LOC_REF_ARG:
- {
- long current_offset = SYMBOL_VALUE (sym);
- arg_size = TYPE_LENGTH (SYMBOL_TYPE (sym));
+ switch (SYMBOL_CLASS (sym))
+ {
+ case LOC_ARG:
+ case LOC_REF_ARG:
+ {
+ long current_offset = SYMBOL_VALUE (sym);
+ arg_size = TYPE_LENGTH (SYMBOL_TYPE (sym));
- /* Compute address of next argument by adding the size of
- this argument and rounding to an int boundary. */
- current_offset =
- ((current_offset + arg_size + sizeof (int) - 1)
- & ~(sizeof (int) - 1));
-
- /* If this is the highest offset seen yet, set highest_offset. */
- if (highest_offset == -1
- || (current_offset > highest_offset))
- highest_offset = current_offset;
+ /* Compute address of next argument by adding the size of
+ this argument and rounding to an int boundary. */
+ current_offset =
+ ((current_offset + arg_size + sizeof (int) - 1)
+ & ~(sizeof (int) - 1));
+
+ /* If this is the highest offset seen yet, set highest_offset. */
+ if (highest_offset == -1
+ || (current_offset > highest_offset))
+ highest_offset = current_offset;
- /* Add the number of ints we're about to print to args_printed. */
- args_printed += (arg_size + sizeof (int) - 1) / sizeof (int);
- }
+ /* Add the number of ints we're about to print to args_printed. */
+ args_printed += (arg_size + sizeof (int) - 1) / sizeof (int);
+ }
- /* We care about types of symbols, but don't need to keep track of
- stack offsets in them. */
- case LOC_REGPARM:
- case LOC_REGPARM_ADDR:
- case LOC_LOCAL_ARG:
- case LOC_BASEREG_ARG:
- break;
-
- /* Other types of symbols we just skip over. */
- default:
- continue;
- }
+ /* We care about types of symbols, but don't need to keep track of
+ stack offsets in them. */
+ case LOC_REGPARM:
+ case LOC_REGPARM_ADDR:
+ case LOC_LOCAL_ARG:
+ case LOC_BASEREG_ARG:
+ break;
+
+ /* Other types of symbols we just skip over. */
+ default:
+ continue;
+ }
- /* We have to look up the symbol because arguments can have
- two entries (one a parameter, one a local) and the one we
- want is the local, which lookup_symbol will find for us.
- This includes gcc1 (not gcc2) on the sparc when passing a
- small structure and gcc2 when the argument type is float
- and it is passed as a double and converted to float by
- the prologue (in the latter case the type of the LOC_ARG
- symbol is double and the type of the LOC_LOCAL symbol is
- float). */
- /* But if the parameter name is null, don't try it.
- Null parameter names occur on the RS/6000, for traceback tables.
- FIXME, should we even print them? */
+ /* We have to look up the symbol because arguments can have
+ two entries (one a parameter, one a local) and the one we
+ want is the local, which lookup_symbol will find for us.
+ This includes gcc1 (not gcc2) on the sparc when passing a
+ small structure and gcc2 when the argument type is float
+ and it is passed as a double and converted to float by
+ the prologue (in the latter case the type of the LOC_ARG
+ symbol is double and the type of the LOC_LOCAL symbol is
+ float). */
+ /* But if the parameter name is null, don't try it.
+ Null parameter names occur on the RS/6000, for traceback tables.
+ FIXME, should we even print them? */
- if (*SYMBOL_NAME (sym))
- {
- struct symbol *nsym;
- nsym = lookup_symbol
- (SYMBOL_NAME (sym),
- b, VAR_NAMESPACE, (int *) NULL, (struct symtab **) NULL);
- if (SYMBOL_CLASS (nsym) == LOC_REGISTER)
+ if (*SYMBOL_NAME (sym))
{
- /* There is a LOC_ARG/LOC_REGISTER pair. This means that
- it was passed on the stack and loaded into a register,
- or passed in a register and stored in a stack slot.
- GDB 3.x used the LOC_ARG; GDB 4.0-4.11 used the LOC_REGISTER.
-
- Reasons for using the LOC_ARG:
- (1) because find_saved_registers may be slow for remote
- debugging,
- (2) because registers are often re-used and stack slots
- rarely (never?) are. Therefore using the stack slot is
- much less likely to print garbage.
-
- Reasons why we might want to use the LOC_REGISTER:
- (1) So that the backtrace prints the same value as
- "print foo". I see no compelling reason why this needs
- to be the case; having the backtrace print the value which
- was passed in, and "print foo" print the value as modified
- within the called function, makes perfect sense to me.
-
- Additional note: It might be nice if "info args" displayed
- both values.
- One more note: There is a case with sparc structure passing
- where we need to use the LOC_REGISTER, but this is dealt with
- by creating a single LOC_REGPARM in symbol reading. */
-
- /* Leave sym (the LOC_ARG) alone. */
- ;
+ struct symbol *nsym;
+ nsym = lookup_symbol
+ (SYMBOL_NAME (sym),
+ b, VAR_NAMESPACE, (int *) NULL, (struct symtab **) NULL);
+ if (SYMBOL_CLASS (nsym) == LOC_REGISTER)
+ {
+ /* There is a LOC_ARG/LOC_REGISTER pair. This means that
+ it was passed on the stack and loaded into a register,
+ or passed in a register and stored in a stack slot.
+ GDB 3.x used the LOC_ARG; GDB 4.0-4.11 used the LOC_REGISTER.
+
+ Reasons for using the LOC_ARG:
+ (1) because find_saved_registers may be slow for remote
+ debugging,
+ (2) because registers are often re-used and stack slots
+ rarely (never?) are. Therefore using the stack slot is
+ much less likely to print garbage.
+
+ Reasons why we might want to use the LOC_REGISTER:
+ (1) So that the backtrace prints the same value as
+ "print foo". I see no compelling reason why this needs
+ to be the case; having the backtrace print the value which
+ was passed in, and "print foo" print the value as modified
+ within the called function, makes perfect sense to me.
+
+ Additional note: It might be nice if "info args" displayed
+ both values.
+ One more note: There is a case with sparc structure passing
+ where we need to use the LOC_REGISTER, but this is dealt with
+ by creating a single LOC_REGPARM in symbol reading. */
+
+ /* Leave sym (the LOC_ARG) alone. */
+ ;
+ }
+ else
+ sym = nsym;
}
- else
- sym = nsym;
- }
#ifdef UI_OUT
- /* Print the current arg. */
- if (!first)
- ui_out_text (uiout, ", ");
- ui_out_wrap_hint (uiout, " ");
-
- annotate_arg_begin ();
-
- list_chain = make_cleanup_ui_out_tuple_begin_end (uiout, NULL);
- fprintf_symbol_filtered (stb->stream, SYMBOL_SOURCE_NAME (sym),
- SYMBOL_LANGUAGE (sym), DMGL_PARAMS | DMGL_ANSI);
- ui_out_field_stream (uiout, "name", stb);
- annotate_arg_name_end ();
- ui_out_text (uiout, "=");
+ /* Print the current arg. */
+ if (!first)
+ ui_out_text (uiout, ", ");
+ ui_out_wrap_hint (uiout, " ");
+
+ annotate_arg_begin ();
+
+ list_chain = make_cleanup_ui_out_tuple_begin_end (uiout, NULL);
+ fprintf_symbol_filtered (stb->stream, SYMBOL_SOURCE_NAME (sym),
+ SYMBOL_LANGUAGE (sym), DMGL_PARAMS | DMGL_ANSI);
+ ui_out_field_stream (uiout, "name", stb);
+ annotate_arg_name_end ();
+ ui_out_text (uiout, "=");
#else
- /* Print the current arg. */
- if (!first)
- fprintf_filtered (stream, ", ");
- wrap_here (" ");
-
- annotate_arg_begin ();
-
- fprintf_symbol_filtered (stream, SYMBOL_SOURCE_NAME (sym),
- SYMBOL_LANGUAGE (sym), DMGL_PARAMS | DMGL_ANSI);
- annotate_arg_name_end ();
- fputs_filtered ("=", stream);
+ /* Print the current arg. */
+ if (!first)
+ fprintf_filtered (stream, ", ");
+ wrap_here (" ");
+
+ annotate_arg_begin ();
+
+ fprintf_symbol_filtered (stream, SYMBOL_SOURCE_NAME (sym),
+ SYMBOL_LANGUAGE (sym), DMGL_PARAMS | DMGL_ANSI);
+ annotate_arg_name_end ();
+ fputs_filtered ("=", stream);
#endif
- /* Avoid value_print because it will deref ref parameters. We just
- want to print their addresses. Print ??? for args whose address
- we do not know. We pass 2 as "recurse" to val_print because our
- standard indentation here is 4 spaces, and val_print indents
- 2 for each recurse. */
- val = read_var_value (sym, fi);
+ /* Avoid value_print because it will deref ref parameters. We just
+ want to print their addresses. Print ??? for args whose address
+ we do not know. We pass 2 as "recurse" to val_print because our
+ standard indentation here is 4 spaces, and val_print indents
+ 2 for each recurse. */
+ val = read_var_value (sym, fi);
- annotate_arg_value (val == NULL ? NULL : VALUE_TYPE (val));
+ annotate_arg_value (val == NULL ? NULL : VALUE_TYPE (val));
- if (val)
- {
+ if (val)
+ {
#ifdef UI_OUT
- val_print (VALUE_TYPE (val), VALUE_CONTENTS (val), 0,
- VALUE_ADDRESS (val),
- stb->stream, 0, 0, 2, Val_no_prettyprint);
- ui_out_field_stream (uiout, "value", stb);
- }
- else
- ui_out_text (uiout, "???");
+ val_print (VALUE_TYPE (val), VALUE_CONTENTS (val), 0,
+ VALUE_ADDRESS (val),
+ stb->stream, 0, 0, 2, Val_no_prettyprint);
+ ui_out_field_stream (uiout, "value", stb);
+ }
+ else
+ ui_out_text (uiout, "???");
- /* Invoke ui_out_tuple_end. */
- do_cleanups (list_chain);
+ /* Invoke ui_out_tuple_end. */
+ do_cleanups (list_chain);
#else
- val_print (VALUE_TYPE (val), VALUE_CONTENTS (val), 0,
- VALUE_ADDRESS (val),
- stream, 0, 0, 2, Val_no_prettyprint);
- }
- else
- fputs_filtered ("???", stream);
+ val_print (VALUE_TYPE (val), VALUE_CONTENTS (val), 0,
+ VALUE_ADDRESS (val),
+ stream, 0, 0, 2, Val_no_prettyprint);
+ }
+ else
+ fputs_filtered ("???", stream);
#endif
- annotate_arg_end ();
+ annotate_arg_end ();
- first = 0;
+ first = 0;
+ }
}
/* Don't print nameless args in situations where we don't know
Index: gdb/stack.c
===================================================================
RCS file: /cvs/src/src/gdb/stack.c,v
retrieving revision 1.22
diff -u -p -r1.22 stack.c
--- stack.c 2001/07/14 18:59:07 1.22
+++ stack.c 2001/10/01 22:20:55
@@ -1207,16 +1207,12 @@ static int
print_block_frame_locals (struct block *b, register struct frame_info *fi,
int num_tabs, register struct ui_file *stream)
{
- int nsyms;
register int i, j;
register struct symbol *sym;
register int values_printed = 0;
- nsyms = BLOCK_NSYMS (b);
-
- for (i = 0; i < nsyms; i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
switch (SYMBOL_CLASS (sym))
{
case LOC_LOCAL:
@@ -1246,16 +1242,12 @@ static int
print_block_frame_labels (struct block *b, int *have_default,
register struct ui_file *stream)
{
- int nsyms;
register int i;
register struct symbol *sym;
register int values_printed = 0;
-
- nsyms = BLOCK_NSYMS (b);
- for (i = 0; i < nsyms; i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
if (STREQ (SYMBOL_NAME (sym), "default"))
{
if (*have_default)
@@ -1432,7 +1424,6 @@ print_frame_arg_vars (register struct fr
{
struct symbol *func = get_frame_function (fi);
register struct block *b;
- int nsyms;
register int i;
register struct symbol *sym, *sym2;
register int values_printed = 0;
@@ -1444,11 +1435,8 @@ print_frame_arg_vars (register struct fr
}
b = SYMBOL_BLOCK_VALUE (func);
- nsyms = BLOCK_NSYMS (b);
-
- for (i = 0; i < nsyms; i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
switch (SYMBOL_CLASS (sym))
{
case LOC_ARG:
@@ -1483,7 +1471,6 @@ print_frame_arg_vars (register struct fr
break;
}
}
-
if (!values_printed)
{
fprintf_filtered (stream, "No arguments.\n");
Index: gdb/symmisc.c
===================================================================
RCS file: /cvs/src/src/gdb/symmisc.c,v
retrieving revision 1.5
diff -u -p -r1.5 symmisc.c
--- symmisc.c 2001/03/06 08:21:17 1.5
+++ symmisc.c 2001/10/01 22:20:56
@@ -86,11 +86,17 @@ static void
free_symtab_block (struct objfile *objfile, struct block *b)
{
register int i, n;
- n = BLOCK_NSYMS (b);
+ struct symbol *sym, *next_sym;
+
+ n = BLOCK_BUCKETS (b);
for (i = 0; i < n; i++)
{
- mfree (objfile->md, SYMBOL_NAME (BLOCK_SYM (b, i)));
- mfree (objfile->md, (PTR) BLOCK_SYM (b, i));
+ for (sym = BLOCK_BUCKET (b, i); sym; sym = next_sym)
+ {
+ next_sym = sym->hash_next;
+ mfree (objfile->md, SYMBOL_NAME (sym));
+ mfree (objfile->md, (PTR) sym);
+ }
}
mfree (objfile->md, (PTR) b);
}
@@ -410,6 +416,7 @@ dump_symtab (struct objfile *objfile, st
int len, blen;
register struct linetable *l;
struct blockvector *bv;
+ struct symbol *sym;
register struct block *b;
int depth;
@@ -454,8 +461,12 @@ dump_symtab (struct objfile *objfile, st
fprintf_filtered (outfile, " under ");
gdb_print_host_address (BLOCK_SUPERBLOCK (b), outfile);
}
- blen = BLOCK_NSYMS (b);
- fprintf_filtered (outfile, ", %d syms in ", blen);
+ /* FIXMED: Save total syms count even if hashed? */
+ blen = BLOCK_BUCKETS (b);
+ if (BLOCK_HASHTABLE (b))
+ fprintf_filtered (outfile, ", %d buckets in ", blen);
+ else
+ fprintf_filtered (outfile, ", %d syms in ", blen);
print_address_numeric (BLOCK_START (b), 1, outfile);
fprintf_filtered (outfile, "..");
print_address_numeric (BLOCK_END (b), 1, outfile);
@@ -471,11 +482,12 @@ dump_symtab (struct objfile *objfile, st
if (BLOCK_GCC_COMPILED (b))
fprintf_filtered (outfile, ", compiled with gcc%d", BLOCK_GCC_COMPILED (b));
fprintf_filtered (outfile, "\n");
- /* Now print each symbol in this block */
- for (j = 0; j < blen; j++)
+ /* Now print each symbol in this block. */
+ /* FIXMED: Sort? */
+ ALL_BLOCK_SYMBOLS (b, j, sym)
{
struct print_symbol_args s;
- s.symbol = BLOCK_SYM (b, j);
+ s.symbol = sym;
s.depth = depth + 1;
s.outfile = outfile;
catch_errors (print_symbol, &s, "Error printing symbol:\n",
Index: gdb/symtab.c
===================================================================
RCS file: /cvs/src/src/gdb/symtab.c,v
retrieving revision 1.42
diff -u -p -r1.42 symtab.c
--- symtab.c 2001/07/07 17:19:50 1.42
+++ symtab.c 2001/10/01 22:20:57
@@ -1186,6 +1186,20 @@ lookup_block_symbol (register const stru
register struct symbol *sym_found = NULL;
register int do_linear_search = 1;
+ if (BLOCK_HASHTABLE (block))
+ {
+ unsigned int hash_index;
+ hash_index = msymbol_hash_iw (name);
+ hash_index = hash_index % BLOCK_BUCKETS (block);
+ for (sym = BLOCK_BUCKET (block, hash_index); sym; sym = sym->hash_next)
+ {
+ if (SYMBOL_NAMESPACE (sym) == namespace
+ && SYMBOL_MATCHES_NAME (sym, name))
+ return sym;
+ }
+ return NULL;
+ }
+
/* If the blocks's symbols were sorted, start with a binary search. */
if (BLOCK_SHOULD_SORT (block))
@@ -1414,14 +1428,15 @@ find_pc_sect_symtab (CORE_ADDR pc, asect
if (section != 0)
{
int i;
+ struct symbol *sym = NULL;
- for (i = 0; i < b->nsyms; i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- fixup_symbol_section (b->sym[i], objfile);
- if (section == SYMBOL_BFD_SECTION (b->sym[i]))
+ fixup_symbol_section (sym, objfile);
+ if (section == SYMBOL_BFD_SECTION (sym))
break;
}
- if (i >= b->nsyms)
+ if ((i >= BLOCK_BUCKETS (b)) && (sym == NULL))
continue; /* no symbol in this symtab matches section */
}
distance = BLOCK_END (b) - BLOCK_START (b);
@@ -2513,13 +2528,18 @@ search_symbols (char *regexp, namespace_
for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
{
b = BLOCKVECTOR_BLOCK (bv, i);
+ /* FIXMED: The #if 0'd code seems *very* wrong. It'll sort blocks
+ that we specifically are supposed to avoid sorting. */
+#if 0
+
/* Skip the sort if this block is always sorted. */
if (!BLOCK_SHOULD_SORT (b))
sort_block_syms (b);
- for (j = 0; j < BLOCK_NSYMS (b); j++)
+#endif
+ ALL_BLOCK_SYMBOLS (b, j, sym)
{
QUIT;
- sym = BLOCK_SYM (b, j);
+ /* FIXME: Hoist file_matches out of this loop. */
if (file_matches (s->filename, files, nfiles)
&& ((regexp == NULL || SYMBOL_MATCHES_REGEXP (sym))
&& ((kind == VARIABLES_NAMESPACE && SYMBOL_CLASS (sym) != LOC_TYPEDEF
@@ -2546,6 +2566,7 @@ search_symbols (char *regexp, namespace_
tail = psr;
}
}
+ /* FIXMED: Sort the results? */
}
prev_bv = bv;
}
@@ -3030,9 +3051,8 @@ make_symbol_completion_list (char *text,
/* Also catch fields of types defined in this places which match our
text string. Only complete on types visible from current context. */
- for (i = 0; i < BLOCK_NSYMS (b); i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
COMPLETION_LIST_ADD_SYMBOL (sym, sym_text, sym_text_len, text, word);
if (SYMBOL_CLASS (sym) == LOC_TYPEDEF)
{
@@ -3061,23 +3081,22 @@ make_symbol_completion_list (char *text,
{
QUIT;
b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), GLOBAL_BLOCK);
- for (i = 0; i < BLOCK_NSYMS (b); i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
COMPLETION_LIST_ADD_SYMBOL (sym, sym_text, sym_text_len, text, word);
}
}
ALL_SYMTABS (objfile, s)
{
+ struct symbol *sym;
QUIT;
b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), STATIC_BLOCK);
/* Don't do this block twice. */
if (b == surrounding_static_block)
continue;
- for (i = 0; i < BLOCK_NSYMS (b); i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
COMPLETION_LIST_ADD_SYMBOL (sym, sym_text, sym_text_len, text, word);
}
}
@@ -3181,16 +3200,14 @@ make_file_symbol_completion_list (char *
symbols which match. */
b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), GLOBAL_BLOCK);
- for (i = 0; i < BLOCK_NSYMS (b); i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
COMPLETION_LIST_ADD_SYMBOL (sym, sym_text, sym_text_len, text, word);
}
b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), STATIC_BLOCK);
- for (i = 0; i < BLOCK_NSYMS (b); i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
COMPLETION_LIST_ADD_SYMBOL (sym, sym_text, sym_text_len, text, word);
}
@@ -3568,9 +3585,8 @@ make_symbol_overload_list (struct symbol
/* Also catch fields of types defined in this places which match our
text string. Only complete on types visible from current context. */
- for (i = 0; i < BLOCK_NSYMS (b); i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
overload_list_add_symbol (sym, oload_name);
}
}
@@ -3582,9 +3598,8 @@ make_symbol_overload_list (struct symbol
{
QUIT;
b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), GLOBAL_BLOCK);
- for (i = 0; i < BLOCK_NSYMS (b); i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
overload_list_add_symbol (sym, oload_name);
}
}
@@ -3596,9 +3611,8 @@ make_symbol_overload_list (struct symbol
/* Don't do this block twice. */
if (b == surrounding_static_block)
continue;
- for (i = 0; i < BLOCK_NSYMS (b); i++)
+ ALL_BLOCK_SYMBOLS (b, i, sym)
{
- sym = BLOCK_SYM (b, i);
overload_list_add_symbol (sym, oload_name);
}
}
Index: gdb/symtab.h
===================================================================
RCS file: /cvs/src/src/gdb/symtab.h,v
retrieving revision 1.24
diff -u -p -r1.24 symtab.h
--- symtab.h 2001/07/07 17:19:50 1.24
+++ symtab.h 2001/10/01 22:20:58
@@ -449,6 +449,10 @@ struct block
unsigned char gcc_compile_flag;
+ /* If this is really a hashtable of the symbols, this flag is 1. */
+
+ unsigned char hashtable;
+
/* Number of local symbols. */
int nsyms;
@@ -461,18 +465,34 @@ struct block
#define BLOCK_START(bl) (bl)->startaddr
#define BLOCK_END(bl) (bl)->endaddr
-#define BLOCK_NSYMS(bl) (bl)->nsyms
-#define BLOCK_SYM(bl, n) (bl)->sym[n]
#define BLOCK_FUNCTION(bl) (bl)->function
#define BLOCK_SUPERBLOCK(bl) (bl)->superblock
#define BLOCK_GCC_COMPILED(bl) (bl)->gcc_compile_flag
+#define BLOCK_HASHTABLE(bl) (bl)->hashtable
+/* For BLOCK_HASHTABLE (bl) == 0 blocks only. */
+#define BLOCK_NSYMS(bl) (bl)->nsyms
+#define BLOCK_SYM(bl, n) (bl)->sym[n]
+
+/* For BLOCK_HASHTABLE (bl) == 1 blocks, but these are valid
+ for non-hashed blocks as well - each symbol will appear to be
+ one bucket by itself. */
+#define BLOCK_BUCKETS(bl) (bl)->nsyms
+#define BLOCK_BUCKET(bl, n) (bl)->sym[n]
+
+/* Macro to loop through all symbols in a block BL, in no particular order.
+ i counts which bucket we are in, and sym points to the current symbol. */
+#define ALL_BLOCK_SYMBOLS(bl, i, sym) \
+ for ((i) = 0; (i) < BLOCK_BUCKETS ((bl)); (i)++) \
+ for ((sym) = BLOCK_BUCKET ((bl), (i)); (sym); \
+ (sym) = (sym)->hash_next)
+
/* Nonzero if symbols of block BL should be sorted alphabetically.
Don't sort a block which corresponds to a function. If we did the
sorting would have to preserve the order of the symbols for the
arguments. */
-#define BLOCK_SHOULD_SORT(bl) ((bl)->nsyms >= 40 && BLOCK_FUNCTION (bl) == NULL)
+#define BLOCK_SHOULD_SORT(bl) (!BLOCK_HASHTABLE (bl) && BLOCK_FUNCTION (bl) == NULL)
\f
/* Represent one symbol name; a variable, constant, function or typedef. */
@@ -722,6 +742,8 @@ struct symbol
/* List of ranges where this symbol is active. This is only
used by alias symbols at the current time. */
struct range_list *ranges;
+
+ struct symbol *hash_next;
};
Index: gdb/tracepoint.c
===================================================================
RCS file: /cvs/src/src/gdb/tracepoint.c,v
retrieving revision 1.26
diff -u -p -r1.26 tracepoint.c
--- tracepoint.c 2001/08/23 20:31:36 1.26
+++ tracepoint.c 2001/10/01 22:20:59
@@ -1296,16 +1296,14 @@ add_local_symbols (struct collection_lis
{
struct symbol *sym;
struct block *block;
- int i, nsyms, count = 0;
+ int i, count = 0;
block = block_for_pc (pc);
while (block != 0)
{
QUIT; /* allow user to bail out with ^C */
- nsyms = BLOCK_NSYMS (block);
- for (i = 0; i < nsyms; i++)
+ ALL_BLOCK_SYMBOLS (block, i, sym)
{
- sym = BLOCK_SYM (block, i);
switch (SYMBOL_CLASS (sym))
{
default:
@@ -2335,7 +2333,7 @@ scope_info (char *args, int from_tty)
struct minimal_symbol *msym;
struct block *block;
char **canonical, *symname, *save_args = args;
- int i, j, nsyms, count = 0;
+ int i, j, count = 0;
if (args == 0 || *args == 0)
error ("requires an argument (function, line or *addr) to define a scope");
@@ -2351,14 +2349,13 @@ scope_info (char *args, int from_tty)
while (block != 0)
{
QUIT; /* allow user to bail out with ^C */
- nsyms = BLOCK_NSYMS (block);
- for (i = 0; i < nsyms; i++)
+ ALL_BLOCK_SYMBOLS (block, i, sym)
{
QUIT; /* allow user to bail out with ^C */
if (count == 0)
printf_filtered ("Scope for %s:\n", save_args);
count++;
- sym = BLOCK_SYM (block, i);
+
symname = SYMBOL_NAME (sym);
if (symname == NULL || *symname == '\0')
continue; /* probably botched, certainly useless */
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [RFC] Symbol table hashing patch
2001-10-01 15:46 [RFC] Symbol table hashing patch Daniel Jacobowitz
@ 2001-10-01 16:05 ` Elena Zannoni
2001-10-01 16:38 ` Daniel Jacobowitz
0 siblings, 1 reply; 4+ messages in thread
From: Elena Zannoni @ 2001-10-01 16:05 UTC (permalink / raw)
To: Daniel Jacobowitz; +Cc: gdb-patches
As a first comment,, I would strongly reccommend that you break the
ALL_BLOCK_SYMBOLS changes into a separate patch. That way the
significant changes to the symtab algorithms will become easier to
review. It seems from you comments that the MINIMAL_SYMBOL_HASH_SIZE
is also an independent fix. How about the bug in msymtab_hash_iw, can
that be separated out as well?
What is 113?
Elena
Daniel Jacobowitz writes:
> I've taken the patches Daniel Berlin sent me to implement hashed symtabs and
> gone over them thoroughly over the past week, and I have something I would
> like to see committed. This is an RFC instead of an RFA because I have a
> few small FIXME comments I'd like feedback on first, though.
>
> The general structure of the patch:
> - First of all, I introduced a macro for looking at all the symbols in a
> given block (ALL_BLOCK_SYMBOLS). I then changed all sites. This
> changes the order in which symbols will be seen, but with a few
> exceptions (below), that's fine. The large change in printcmd.c
> is almost entirely whitespace; do not be alarmed unduly :)
> - I fixed a logic bug in msymtab_hash_iw.
> - I added code to lookup_block_symbol to use the hashtable; nothing
> surprising here.
> - Based on some experimentation, and Daniel's patch, I increased
> MINIMAL_SYMBOL_HASH_SIZE; I went over a set of random binaries
> and objfiles on my system, and this seems like a reasonable change.
> The C library, for instance, has 1933 msyms; gdb has 3670 without
> debug info and 7475 with. A hash table with 349 buckets, while not
> entirely unreasonable, seemed a little small. This change is
> unrelated to the others, though, if people disagree with it.
> - I went to the other symbol readers et al. which create blocks on their
> own (dstread.c, jv-lang.c, and mdebugread.c), and made sure that
> they marked the blocks they built as unhashed. Better would be to
> make them use the normal interface for doing this, but without
> any way to test such changes I'm not going to. I'm a little
> bit nervous about mdebugread.c in particular, but I'm reasonably
> sure that I'm correct.
>
> Now, for the parts I'd like comments on:
> - coffread.c:patch_opaque_types used to walk the symbol table backwards,
> before it was sorted. Is this important? From the comments I could
> not tell.
> - Cosmetically, the output of dump_symtab changed. I don't think it's
> worth sorting just for this. It causes one testsuite regression,
> which I'll fix by tweaking the testsuite if no one insists on sorting.
> - Daniel noticed a scary block in search_symbols:
> /* Skip the sort if this block is always sorted. */
> if (!BLOCK_SHOULD_SORT (b))
> sort_block_syms (b);
> BLOCK_SHOULD_SORT was formerly "if the block has more than 40 symbols
> and is not order-sensitive (list of function arguments, etc)". Sorting
> such a function block seems like a very bad idea. OK to remove this?
> search_symbols doesn't even need a sorted block; it searches all entries
> anyway. The results will no longer be sorted; if it is prefered, we can
> sort the results after searching is complete.
>
> --
> Daniel Jacobowitz Carnegie Mellon University
> MontaVista Software Debian GNU/Linux Developer
>
> 2001-10-01 Daniel Jacobowitz <drow@mvista.com>
>
> Based on patch from Daniel Berlin <dan@cgsoftware.com>.
> * buildsym.c: Include "demangle.h" for SYMBOL_INIT_DEMANGLED_NAME.
> (finish_block) For non-function blocks, hash the symbol table. For
> function blocks, mark the symbol table as unhashed.
>
> * minsyms.c (msymbol_hash): Use better hash function.
> Return hash value without taking modulus.
> (msymbol_hash_iw): Likewise. Terminate loop at '(' properly.
> (add_minsym_to_hash_table): Take modulus of msymbol_hash's return
> value.
> (add_minsym_to_demangled_hash_table): Likewise for msymbol_hash_iw.
> (lookup_minimal_symbol): Likewise for both.
>
> * symtab.h (struct block): Add `hashtable' flag.
> (BLOCK_HASHTABLE): New macro.
> (BLOCK_BUCKETS): New macro.
> (BLOCK_BUCKET): New macro.
> (ALL_BLOCK_SYMBOLS): New macro.
> (BLOCK_SHOULD_SORT): Do not sort hashed blocks.
> (struct symbol): Add `hash_next' pointer.
>
> * symtab.c (lookup_block_symbol): Search using the hash table when
> possible.
> (find_pc_sect_symtab): Use ALL_BLOCK_SYMBOLS.
> (search_symbols): Do not attempt to sort hashed blocks or function
> blocks. Use ALL_BLOCK_SYMBOLS.
> (make_symbol_completion_list): Use ALL_BLOCK_SYMBOLS.
> (make_symbol_overload_list): Likewise.
>
> * objfiles.h: Increase MINIMAL_SYMBOL_HASH_SIZE.
>
> * dstread.c (process_dst_block): Clear hashtable bit for new block.
> (read_dst_symtab): Likewise.
> * jv-lang.c (get_java_class_symtab): Likewise.
> * mdebugread.c: Include "gdb_assert.h".
> (shrink_block): Assert that the block being modified is not hashed.
>
> * symmisc.c (free_symtab_block): Walk the hash table when freeing
> symbols.
> (dump_symtab): Recognize hashed blocks. Use ALL_BLOCK_SYMBOLS.
>
> * breakpoint.c (get_catch_sals): Use ALL_BLOCK_SYMBOLS.
> * coffread.c (patch_opaque_types): Likewise.
> * objfiles.c (objfile_relocate): Likewise.
> * stack.c (print_block_frame_locals): Likewise.
> (print_block_frame_labels): Likewise.
> (print_frame_arg_vars): Likewise.
> * tracepoint.c (add_local_symbols): Likewise.
> (scope_info): Likewise.
> * printcmd.c (print_frame_args): Likewise. Assert that
> function blocks do not have hashed symbol tables.
>
> Index: gdb/breakpoint.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/breakpoint.c,v
> retrieving revision 1.53
> diff -u -p -r1.53 breakpoint.c
> --- breakpoint.c 2001/09/18 05:00:48 1.53
> +++ breakpoint.c 2001/10/01 22:20:38
> @@ -5871,15 +5871,11 @@ get_catch_sals (int this_level_only)
> if (blocks_searched[index] == 0)
> {
> struct block *b = BLOCKVECTOR_BLOCK (bl, index);
> - int nsyms;
> register int i;
> register struct symbol *sym;
>
> - nsyms = BLOCK_NSYMS (b);
> -
> - for (i = 0; i < nsyms; i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> if (STREQ (SYMBOL_NAME (sym), "default"))
> {
> if (have_default)
> Index: gdb/buildsym.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/buildsym.c,v
> retrieving revision 1.11
> diff -u -p -r1.11 buildsym.c
> --- buildsym.c 2001/04/30 10:30:27 1.11
> +++ buildsym.c 2001/10/01 22:20:39
> @@ -39,6 +39,7 @@
> #include "language.h" /* For "longest_local_hex_string_custom" */
> #include "bcache.h"
> #include "filenames.h" /* For DOSish file names */
> +#include "demangle.h" /* Needed by SYMBOL_INIT_DEMANGLED_NAME */
> /* Ask buildsym.h to define the vars it normally declares `extern'. */
> #define EXTERN
> /**/
> @@ -239,17 +240,45 @@ finish_block (struct symbol *symbol, str
> /* EMPTY */ ;
> }
>
> - block = (struct block *) obstack_alloc (&objfile->symbol_obstack,
> - (sizeof (struct block) + ((i - 1) * sizeof (struct symbol *))));
> -
> /* Copy the symbols into the block. */
>
> - BLOCK_NSYMS (block) = i;
> - for (next = *listhead; next; next = next->next)
> + if (symbol)
> + {
> + block = (struct block *)
> + obstack_alloc (&objfile->symbol_obstack,
> + (sizeof (struct block) +
> + ((i - 1) * sizeof (struct symbol *))));
> + BLOCK_NSYMS (block) = i;
> + for (next = *listhead; next; next = next->next)
> + for (j = next->nsyms - 1; j >= 0; j--)
> + {
> + BLOCK_SYM (block, --i) = next->symbol[j];
> + }
> + }
> + else
> {
> - for (j = next->nsyms - 1; j >= 0; j--)
> + block = (struct block *)
> + obstack_alloc (&objfile->symbol_obstack,
> + (sizeof (struct block) +
> + ((i / 5) * sizeof (struct symbol *))));
> + for (j = 0; j < ((i / 5) + 1); j++)
> {
> - BLOCK_SYM (block, --i) = next->symbol[j];
> + BLOCK_BUCKET (block, j) = 0;
> + }
> + BLOCK_BUCKETS (block) = (i / 5) + 1;
> + for (next = *listhead; next; next = next->next)
> + {
> + for (j = next->nsyms - 1; j >= 0; j--)
> + {
> + struct symbol *sym;
> + unsigned int hash_index;
> + SYMBOL_INIT_DEMANGLED_NAME (next->symbol[j], &objfile->symbol_obstack);
> + hash_index = msymbol_hash_iw (SYMBOL_SOURCE_NAME (next->symbol[j]));
> + hash_index = hash_index % BLOCK_BUCKETS (block);
> + sym = BLOCK_BUCKET (block, hash_index);
> + BLOCK_BUCKET (block, hash_index) = next->symbol[j];
> + next->symbol[j]->hash_next = sym;
> + }
> }
> }
>
> @@ -267,6 +296,7 @@ finish_block (struct symbol *symbol, str
> struct type *ftype = SYMBOL_TYPE (symbol);
> SYMBOL_BLOCK_VALUE (symbol) = block;
> BLOCK_FUNCTION (block) = symbol;
> + BLOCK_HASHTABLE (block) = 0;
>
> if (TYPE_NFIELDS (ftype) <= 0)
> {
> @@ -348,6 +378,7 @@ finish_block (struct symbol *symbol, str
> else
> {
> BLOCK_FUNCTION (block) = NULL;
> + BLOCK_HASHTABLE (block) = 1;
> }
>
> /* Now "free" the links of the list, and empty the list. */
> Index: gdb/coffread.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/coffread.c,v
> retrieving revision 1.20
> diff -u -p -r1.20 coffread.c
> --- coffread.c 2001/09/20 03:03:39 1.20
> +++ coffread.c 2001/10/01 22:20:40
> @@ -1446,13 +1446,13 @@ patch_opaque_types (struct symtab *s)
>
> /* Go through the per-file symbols only */
> b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), STATIC_BLOCK);
> - for (i = BLOCK_NSYMS (b) - 1; i >= 0; i--)
> + /* FIXMED: Originally all symbols, in reverse order, before they are sorted. */
> + ALL_BLOCK_SYMBOLS (b, i, real_sym)
> {
> /* Find completed typedefs to use to fix opaque ones.
> Remove syms from the chain when their types are stored,
> but search the whole chain, as there may be several syms
> from different files with the same name. */
> - real_sym = BLOCK_SYM (b, i);
> if (SYMBOL_CLASS (real_sym) == LOC_TYPEDEF &&
> SYMBOL_NAMESPACE (real_sym) == VAR_NAMESPACE &&
> TYPE_CODE (SYMBOL_TYPE (real_sym)) == TYPE_CODE_PTR &&
> Index: gdb/dstread.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/dstread.c,v
> retrieving revision 1.7
> diff -u -p -r1.7 dstread.c
> --- dstread.c 2001/03/06 08:21:06 1.7
> +++ dstread.c 2001/10/01 22:20:41
> @@ -1407,6 +1407,7 @@ process_dst_block (struct objfile *objfi
> symnum++;
> }
> BLOCK_NSYMS (block) = total_symbols;
> + BLOCK_HASHTABLE (block) = 0;
> BLOCK_START (block) = address;
> BLOCK_END (block) = address + size;
> BLOCK_SUPERBLOCK (block) = 0;
> @@ -1491,6 +1492,7 @@ read_dst_symtab (struct objfile *objfile
> (total_globals - 1) *
> sizeof (struct symbol *));
> BLOCK_NSYMS (global_block) = total_globals;
> + BLOCK_HASHTABLE (global_block) = 0;
> for (symnum = 0; symnum < total_globals; symnum++)
> {
> nextsym = dst_global_symbols->next;
> Index: gdb/jv-lang.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/jv-lang.c,v
> retrieving revision 1.7
> diff -u -p -r1.7 jv-lang.c
> --- jv-lang.c 2001/03/23 22:48:44 1.7
> +++ jv-lang.c 2001/10/01 22:20:42
> @@ -106,6 +106,7 @@ get_java_class_symtab (void)
> bl = (struct block *)
> obstack_alloc (&objfile->symbol_obstack, sizeof (struct block));
> BLOCK_NSYMS (bl) = 0;
> + BLOCK_HASHTABLE (bl) = 0;
> BLOCK_START (bl) = 0;
> BLOCK_END (bl) = 0;
> BLOCK_FUNCTION (bl) = NULL;
> Index: gdb/mdebugread.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/mdebugread.c,v
> retrieving revision 1.15
> diff -u -p -r1.15 mdebugread.c
> --- mdebugread.c 2001/09/05 02:54:15 1.15
> +++ mdebugread.c 2001/10/01 22:20:46
> @@ -52,6 +52,7 @@
> #include "stabsread.h"
> #include "complaints.h"
> #include "demangle.h"
> +#include "gdb_assert.h"
>
> /* These are needed if the tm.h file does not contain the necessary
> mips specific definitions. */
> @@ -4154,6 +4155,11 @@ shrink_block (struct block *b, struct sy
> (sizeof (struct block)
> + ((BLOCK_NSYMS (b) - 1)
> * sizeof (struct symbol *))));
> +
> + /* FIXME: Not worth hashing this block as it's built. */
> + /* All callers should have created the block with new_block (), which
> + would mean it was not previously hashed. Make sure. */
> + gdb_assert (BLOCK_HASHTABLE (new) == 0);
>
> /* Should chase pointers to old one. Fortunately, that`s just
> the block`s function and inferior blocks */
> Index: gdb/minsyms.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/minsyms.c,v
> retrieving revision 1.17
> diff -u -p -r1.17 minsyms.c
> --- minsyms.c 2001/05/29 10:45:10 1.17
> +++ minsyms.c 2001/10/01 22:20:47
> @@ -96,10 +96,12 @@ msymbol_hash_iw (const char *string)
> while (isspace (*string))
> ++string;
> if (*string && *string != '(')
> - hash = (31 * hash) + *string;
> - ++string;
> + {
> + hash = hash * 67 + *string - 113;
> + ++string;
> + }
> }
> - return hash % MINIMAL_SYMBOL_HASH_SIZE;
> + return hash;
> }
>
> /* Compute a hash code for a string. */
> @@ -109,8 +111,8 @@ msymbol_hash (const char *string)
> {
> unsigned int hash = 0;
> for (; *string; ++string)
> - hash = (31 * hash) + *string;
> - return hash % MINIMAL_SYMBOL_HASH_SIZE;
> + hash = hash * 67 + *string - 113;
> + return hash;
> }
>
> /* Add the minimal symbol SYM to an objfile's minsym hash table, TABLE. */
> @@ -120,7 +122,7 @@ add_minsym_to_hash_table (struct minimal
> {
> if (sym->hash_next == NULL)
> {
> - unsigned int hash = msymbol_hash (SYMBOL_NAME (sym));
> + unsigned int hash = msymbol_hash (SYMBOL_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE;
> sym->hash_next = table[hash];
> table[hash] = sym;
> }
> @@ -134,7 +136,7 @@ add_minsym_to_demangled_hash_table (stru
> {
> if (sym->demangled_hash_next == NULL)
> {
> - unsigned int hash = msymbol_hash_iw (SYMBOL_DEMANGLED_NAME (sym));
> + unsigned int hash = msymbol_hash_iw (SYMBOL_DEMANGLED_NAME (sym)) % MINIMAL_SYMBOL_HASH_SIZE;
> sym->demangled_hash_next = table[hash];
> table[hash] = sym;
> }
> @@ -162,8 +164,8 @@ lookup_minimal_symbol (register const ch
> struct minimal_symbol *found_file_symbol = NULL;
> struct minimal_symbol *trampoline_symbol = NULL;
>
> - unsigned int hash = msymbol_hash (name);
> - unsigned int dem_hash = msymbol_hash_iw (name);
> + unsigned int hash = msymbol_hash (name) % MINIMAL_SYMBOL_HASH_SIZE;
> + unsigned int dem_hash = msymbol_hash_iw (name) % MINIMAL_SYMBOL_HASH_SIZE;
>
> #ifdef SOFUN_ADDRESS_MAYBE_MISSING
> if (sfile != NULL)
> Index: gdb/objfiles.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/objfiles.c,v
> retrieving revision 1.16
> diff -u -p -r1.16 objfiles.c
> --- objfiles.c 2001/07/05 21:32:39 1.16
> +++ objfiles.c 2001/10/01 22:20:53
> @@ -557,16 +557,15 @@ objfile_relocate (struct objfile *objfil
> for (i = 0; i < BLOCKVECTOR_NBLOCKS (bv); ++i)
> {
> struct block *b;
> + struct symbol *sym;
> int j;
>
> b = BLOCKVECTOR_BLOCK (bv, i);
> BLOCK_START (b) += ANOFFSET (delta, s->block_line_section);
> BLOCK_END (b) += ANOFFSET (delta, s->block_line_section);
>
> - for (j = 0; j < BLOCK_NSYMS (b); ++j)
> + ALL_BLOCK_SYMBOLS (b, j, sym)
> {
> - struct symbol *sym = BLOCK_SYM (b, j);
> -
> fixup_symbol_section (sym, objfile);
>
> /* The RS6000 code from which this was taken skipped
> Index: gdb/objfiles.h
> ===================================================================
> RCS file: /cvs/src/src/gdb/objfiles.h,v
> retrieving revision 1.8
> diff -u -p -r1.8 objfiles.h
> --- objfiles.h 2001/03/06 08:21:11 1.8
> +++ objfiles.h 2001/10/01 22:20:53
> @@ -202,7 +202,7 @@ extern void print_objfile_statistics (vo
> extern void print_symbol_bcache_statistics (void);
>
> /* Number of entries in the minimal symbol hash table. */
> -#define MINIMAL_SYMBOL_HASH_SIZE 349
> +#define MINIMAL_SYMBOL_HASH_SIZE 2039
>
> /* Master structure for keeping track of each file from which
> gdb reads symbols. There are several ways these get allocated: 1.
> Index: gdb/printcmd.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/printcmd.c,v
> retrieving revision 1.27
> diff -u -p -r1.27 printcmd.c
> --- printcmd.c 2001/09/12 04:18:08 1.27
> +++ printcmd.c 2001/10/01 22:20:54
> @@ -38,6 +38,7 @@
> #include "symfile.h" /* for overlay functions */
> #include "objfiles.h" /* ditto */
> #include "completer.h" /* for completion functions */
> +#include "gdb_assert.h"
> #ifdef UI_OUT
> #include "ui-out.h"
> #endif
> @@ -1806,168 +1807,171 @@ print_frame_args (struct symbol *func, s
> if (func)
> {
> b = SYMBOL_BLOCK_VALUE (func);
> + /* Function blocks are order sensitive, and thus should not be
> + hashed. */
> + gdb_assert (BLOCK_HASHTABLE (b) == 0);
> nsyms = BLOCK_NSYMS (b);
> - }
>
> - for (i = 0; i < nsyms; i++)
> - {
> - QUIT;
> - sym = BLOCK_SYM (b, i);
> + ALL_BLOCK_SYMBOLS (b, i, sym);
> + {
> + QUIT;
> + sym = BLOCK_SYM (b, i);
>
> - /* Keep track of the highest stack argument offset seen, and
> - skip over any kinds of symbols we don't care about. */
> + /* Keep track of the highest stack argument offset seen, and
> + skip over any kinds of symbols we don't care about. */
>
> - switch (SYMBOL_CLASS (sym))
> - {
> - case LOC_ARG:
> - case LOC_REF_ARG:
> - {
> - long current_offset = SYMBOL_VALUE (sym);
> - arg_size = TYPE_LENGTH (SYMBOL_TYPE (sym));
> + switch (SYMBOL_CLASS (sym))
> + {
> + case LOC_ARG:
> + case LOC_REF_ARG:
> + {
> + long current_offset = SYMBOL_VALUE (sym);
> + arg_size = TYPE_LENGTH (SYMBOL_TYPE (sym));
>
> - /* Compute address of next argument by adding the size of
> - this argument and rounding to an int boundary. */
> - current_offset =
> - ((current_offset + arg_size + sizeof (int) - 1)
> - & ~(sizeof (int) - 1));
> -
> - /* If this is the highest offset seen yet, set highest_offset. */
> - if (highest_offset == -1
> - || (current_offset > highest_offset))
> - highest_offset = current_offset;
> + /* Compute address of next argument by adding the size of
> + this argument and rounding to an int boundary. */
> + current_offset =
> + ((current_offset + arg_size + sizeof (int) - 1)
> + & ~(sizeof (int) - 1));
> +
> + /* If this is the highest offset seen yet, set highest_offset. */
> + if (highest_offset == -1
> + || (current_offset > highest_offset))
> + highest_offset = current_offset;
>
> - /* Add the number of ints we're about to print to args_printed. */
> - args_printed += (arg_size + sizeof (int) - 1) / sizeof (int);
> - }
> + /* Add the number of ints we're about to print to args_printed. */
> + args_printed += (arg_size + sizeof (int) - 1) / sizeof (int);
> + }
>
> - /* We care about types of symbols, but don't need to keep track of
> - stack offsets in them. */
> - case LOC_REGPARM:
> - case LOC_REGPARM_ADDR:
> - case LOC_LOCAL_ARG:
> - case LOC_BASEREG_ARG:
> - break;
> -
> - /* Other types of symbols we just skip over. */
> - default:
> - continue;
> - }
> + /* We care about types of symbols, but don't need to keep track of
> + stack offsets in them. */
> + case LOC_REGPARM:
> + case LOC_REGPARM_ADDR:
> + case LOC_LOCAL_ARG:
> + case LOC_BASEREG_ARG:
> + break;
> +
> + /* Other types of symbols we just skip over. */
> + default:
> + continue;
> + }
>
> - /* We have to look up the symbol because arguments can have
> - two entries (one a parameter, one a local) and the one we
> - want is the local, which lookup_symbol will find for us.
> - This includes gcc1 (not gcc2) on the sparc when passing a
> - small structure and gcc2 when the argument type is float
> - and it is passed as a double and converted to float by
> - the prologue (in the latter case the type of the LOC_ARG
> - symbol is double and the type of the LOC_LOCAL symbol is
> - float). */
> - /* But if the parameter name is null, don't try it.
> - Null parameter names occur on the RS/6000, for traceback tables.
> - FIXME, should we even print them? */
> + /* We have to look up the symbol because arguments can have
> + two entries (one a parameter, one a local) and the one we
> + want is the local, which lookup_symbol will find for us.
> + This includes gcc1 (not gcc2) on the sparc when passing a
> + small structure and gcc2 when the argument type is float
> + and it is passed as a double and converted to float by
> + the prologue (in the latter case the type of the LOC_ARG
> + symbol is double and the type of the LOC_LOCAL symbol is
> + float). */
> + /* But if the parameter name is null, don't try it.
> + Null parameter names occur on the RS/6000, for traceback tables.
> + FIXME, should we even print them? */
>
> - if (*SYMBOL_NAME (sym))
> - {
> - struct symbol *nsym;
> - nsym = lookup_symbol
> - (SYMBOL_NAME (sym),
> - b, VAR_NAMESPACE, (int *) NULL, (struct symtab **) NULL);
> - if (SYMBOL_CLASS (nsym) == LOC_REGISTER)
> + if (*SYMBOL_NAME (sym))
> {
> - /* There is a LOC_ARG/LOC_REGISTER pair. This means that
> - it was passed on the stack and loaded into a register,
> - or passed in a register and stored in a stack slot.
> - GDB 3.x used the LOC_ARG; GDB 4.0-4.11 used the LOC_REGISTER.
> -
> - Reasons for using the LOC_ARG:
> - (1) because find_saved_registers may be slow for remote
> - debugging,
> - (2) because registers are often re-used and stack slots
> - rarely (never?) are. Therefore using the stack slot is
> - much less likely to print garbage.
> -
> - Reasons why we might want to use the LOC_REGISTER:
> - (1) So that the backtrace prints the same value as
> - "print foo". I see no compelling reason why this needs
> - to be the case; having the backtrace print the value which
> - was passed in, and "print foo" print the value as modified
> - within the called function, makes perfect sense to me.
> -
> - Additional note: It might be nice if "info args" displayed
> - both values.
> - One more note: There is a case with sparc structure passing
> - where we need to use the LOC_REGISTER, but this is dealt with
> - by creating a single LOC_REGPARM in symbol reading. */
> -
> - /* Leave sym (the LOC_ARG) alone. */
> - ;
> + struct symbol *nsym;
> + nsym = lookup_symbol
> + (SYMBOL_NAME (sym),
> + b, VAR_NAMESPACE, (int *) NULL, (struct symtab **) NULL);
> + if (SYMBOL_CLASS (nsym) == LOC_REGISTER)
> + {
> + /* There is a LOC_ARG/LOC_REGISTER pair. This means that
> + it was passed on the stack and loaded into a register,
> + or passed in a register and stored in a stack slot.
> + GDB 3.x used the LOC_ARG; GDB 4.0-4.11 used the LOC_REGISTER.
> +
> + Reasons for using the LOC_ARG:
> + (1) because find_saved_registers may be slow for remote
> + debugging,
> + (2) because registers are often re-used and stack slots
> + rarely (never?) are. Therefore using the stack slot is
> + much less likely to print garbage.
> +
> + Reasons why we might want to use the LOC_REGISTER:
> + (1) So that the backtrace prints the same value as
> + "print foo". I see no compelling reason why this needs
> + to be the case; having the backtrace print the value which
> + was passed in, and "print foo" print the value as modified
> + within the called function, makes perfect sense to me.
> +
> + Additional note: It might be nice if "info args" displayed
> + both values.
> + One more note: There is a case with sparc structure passing
> + where we need to use the LOC_REGISTER, but this is dealt with
> + by creating a single LOC_REGPARM in symbol reading. */
> +
> + /* Leave sym (the LOC_ARG) alone. */
> + ;
> + }
> + else
> + sym = nsym;
> }
> - else
> - sym = nsym;
> - }
>
> #ifdef UI_OUT
> - /* Print the current arg. */
> - if (!first)
> - ui_out_text (uiout, ", ");
> - ui_out_wrap_hint (uiout, " ");
> -
> - annotate_arg_begin ();
> -
> - list_chain = make_cleanup_ui_out_tuple_begin_end (uiout, NULL);
> - fprintf_symbol_filtered (stb->stream, SYMBOL_SOURCE_NAME (sym),
> - SYMBOL_LANGUAGE (sym), DMGL_PARAMS | DMGL_ANSI);
> - ui_out_field_stream (uiout, "name", stb);
> - annotate_arg_name_end ();
> - ui_out_text (uiout, "=");
> + /* Print the current arg. */
> + if (!first)
> + ui_out_text (uiout, ", ");
> + ui_out_wrap_hint (uiout, " ");
> +
> + annotate_arg_begin ();
> +
> + list_chain = make_cleanup_ui_out_tuple_begin_end (uiout, NULL);
> + fprintf_symbol_filtered (stb->stream, SYMBOL_SOURCE_NAME (sym),
> + SYMBOL_LANGUAGE (sym), DMGL_PARAMS | DMGL_ANSI);
> + ui_out_field_stream (uiout, "name", stb);
> + annotate_arg_name_end ();
> + ui_out_text (uiout, "=");
> #else
> - /* Print the current arg. */
> - if (!first)
> - fprintf_filtered (stream, ", ");
> - wrap_here (" ");
> -
> - annotate_arg_begin ();
> -
> - fprintf_symbol_filtered (stream, SYMBOL_SOURCE_NAME (sym),
> - SYMBOL_LANGUAGE (sym), DMGL_PARAMS | DMGL_ANSI);
> - annotate_arg_name_end ();
> - fputs_filtered ("=", stream);
> + /* Print the current arg. */
> + if (!first)
> + fprintf_filtered (stream, ", ");
> + wrap_here (" ");
> +
> + annotate_arg_begin ();
> +
> + fprintf_symbol_filtered (stream, SYMBOL_SOURCE_NAME (sym),
> + SYMBOL_LANGUAGE (sym), DMGL_PARAMS | DMGL_ANSI);
> + annotate_arg_name_end ();
> + fputs_filtered ("=", stream);
> #endif
>
> - /* Avoid value_print because it will deref ref parameters. We just
> - want to print their addresses. Print ??? for args whose address
> - we do not know. We pass 2 as "recurse" to val_print because our
> - standard indentation here is 4 spaces, and val_print indents
> - 2 for each recurse. */
> - val = read_var_value (sym, fi);
> + /* Avoid value_print because it will deref ref parameters. We just
> + want to print their addresses. Print ??? for args whose address
> + we do not know. We pass 2 as "recurse" to val_print because our
> + standard indentation here is 4 spaces, and val_print indents
> + 2 for each recurse. */
> + val = read_var_value (sym, fi);
>
> - annotate_arg_value (val == NULL ? NULL : VALUE_TYPE (val));
> + annotate_arg_value (val == NULL ? NULL : VALUE_TYPE (val));
>
> - if (val)
> - {
> + if (val)
> + {
> #ifdef UI_OUT
> - val_print (VALUE_TYPE (val), VALUE_CONTENTS (val), 0,
> - VALUE_ADDRESS (val),
> - stb->stream, 0, 0, 2, Val_no_prettyprint);
> - ui_out_field_stream (uiout, "value", stb);
> - }
> - else
> - ui_out_text (uiout, "???");
> + val_print (VALUE_TYPE (val), VALUE_CONTENTS (val), 0,
> + VALUE_ADDRESS (val),
> + stb->stream, 0, 0, 2, Val_no_prettyprint);
> + ui_out_field_stream (uiout, "value", stb);
> + }
> + else
> + ui_out_text (uiout, "???");
>
> - /* Invoke ui_out_tuple_end. */
> - do_cleanups (list_chain);
> + /* Invoke ui_out_tuple_end. */
> + do_cleanups (list_chain);
> #else
> - val_print (VALUE_TYPE (val), VALUE_CONTENTS (val), 0,
> - VALUE_ADDRESS (val),
> - stream, 0, 0, 2, Val_no_prettyprint);
> - }
> - else
> - fputs_filtered ("???", stream);
> + val_print (VALUE_TYPE (val), VALUE_CONTENTS (val), 0,
> + VALUE_ADDRESS (val),
> + stream, 0, 0, 2, Val_no_prettyprint);
> + }
> + else
> + fputs_filtered ("???", stream);
> #endif
>
> - annotate_arg_end ();
> + annotate_arg_end ();
>
> - first = 0;
> + first = 0;
> + }
> }
>
> /* Don't print nameless args in situations where we don't know
> Index: gdb/stack.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/stack.c,v
> retrieving revision 1.22
> diff -u -p -r1.22 stack.c
> --- stack.c 2001/07/14 18:59:07 1.22
> +++ stack.c 2001/10/01 22:20:55
> @@ -1207,16 +1207,12 @@ static int
> print_block_frame_locals (struct block *b, register struct frame_info *fi,
> int num_tabs, register struct ui_file *stream)
> {
> - int nsyms;
> register int i, j;
> register struct symbol *sym;
> register int values_printed = 0;
>
> - nsyms = BLOCK_NSYMS (b);
> -
> - for (i = 0; i < nsyms; i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> switch (SYMBOL_CLASS (sym))
> {
> case LOC_LOCAL:
> @@ -1246,16 +1242,12 @@ static int
> print_block_frame_labels (struct block *b, int *have_default,
> register struct ui_file *stream)
> {
> - int nsyms;
> register int i;
> register struct symbol *sym;
> register int values_printed = 0;
> -
> - nsyms = BLOCK_NSYMS (b);
>
> - for (i = 0; i < nsyms; i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> if (STREQ (SYMBOL_NAME (sym), "default"))
> {
> if (*have_default)
> @@ -1432,7 +1424,6 @@ print_frame_arg_vars (register struct fr
> {
> struct symbol *func = get_frame_function (fi);
> register struct block *b;
> - int nsyms;
> register int i;
> register struct symbol *sym, *sym2;
> register int values_printed = 0;
> @@ -1444,11 +1435,8 @@ print_frame_arg_vars (register struct fr
> }
>
> b = SYMBOL_BLOCK_VALUE (func);
> - nsyms = BLOCK_NSYMS (b);
> -
> - for (i = 0; i < nsyms; i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> switch (SYMBOL_CLASS (sym))
> {
> case LOC_ARG:
> @@ -1483,7 +1471,6 @@ print_frame_arg_vars (register struct fr
> break;
> }
> }
> -
> if (!values_printed)
> {
> fprintf_filtered (stream, "No arguments.\n");
> Index: gdb/symmisc.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/symmisc.c,v
> retrieving revision 1.5
> diff -u -p -r1.5 symmisc.c
> --- symmisc.c 2001/03/06 08:21:17 1.5
> +++ symmisc.c 2001/10/01 22:20:56
> @@ -86,11 +86,17 @@ static void
> free_symtab_block (struct objfile *objfile, struct block *b)
> {
> register int i, n;
> - n = BLOCK_NSYMS (b);
> + struct symbol *sym, *next_sym;
> +
> + n = BLOCK_BUCKETS (b);
> for (i = 0; i < n; i++)
> {
> - mfree (objfile->md, SYMBOL_NAME (BLOCK_SYM (b, i)));
> - mfree (objfile->md, (PTR) BLOCK_SYM (b, i));
> + for (sym = BLOCK_BUCKET (b, i); sym; sym = next_sym)
> + {
> + next_sym = sym->hash_next;
> + mfree (objfile->md, SYMBOL_NAME (sym));
> + mfree (objfile->md, (PTR) sym);
> + }
> }
> mfree (objfile->md, (PTR) b);
> }
> @@ -410,6 +416,7 @@ dump_symtab (struct objfile *objfile, st
> int len, blen;
> register struct linetable *l;
> struct blockvector *bv;
> + struct symbol *sym;
> register struct block *b;
> int depth;
>
> @@ -454,8 +461,12 @@ dump_symtab (struct objfile *objfile, st
> fprintf_filtered (outfile, " under ");
> gdb_print_host_address (BLOCK_SUPERBLOCK (b), outfile);
> }
> - blen = BLOCK_NSYMS (b);
> - fprintf_filtered (outfile, ", %d syms in ", blen);
> + /* FIXMED: Save total syms count even if hashed? */
> + blen = BLOCK_BUCKETS (b);
> + if (BLOCK_HASHTABLE (b))
> + fprintf_filtered (outfile, ", %d buckets in ", blen);
> + else
> + fprintf_filtered (outfile, ", %d syms in ", blen);
> print_address_numeric (BLOCK_START (b), 1, outfile);
> fprintf_filtered (outfile, "..");
> print_address_numeric (BLOCK_END (b), 1, outfile);
> @@ -471,11 +482,12 @@ dump_symtab (struct objfile *objfile, st
> if (BLOCK_GCC_COMPILED (b))
> fprintf_filtered (outfile, ", compiled with gcc%d", BLOCK_GCC_COMPILED (b));
> fprintf_filtered (outfile, "\n");
> - /* Now print each symbol in this block */
> - for (j = 0; j < blen; j++)
> + /* Now print each symbol in this block. */
> + /* FIXMED: Sort? */
> + ALL_BLOCK_SYMBOLS (b, j, sym)
> {
> struct print_symbol_args s;
> - s.symbol = BLOCK_SYM (b, j);
> + s.symbol = sym;
> s.depth = depth + 1;
> s.outfile = outfile;
> catch_errors (print_symbol, &s, "Error printing symbol:\n",
> Index: gdb/symtab.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/symtab.c,v
> retrieving revision 1.42
> diff -u -p -r1.42 symtab.c
> --- symtab.c 2001/07/07 17:19:50 1.42
> +++ symtab.c 2001/10/01 22:20:57
> @@ -1186,6 +1186,20 @@ lookup_block_symbol (register const stru
> register struct symbol *sym_found = NULL;
> register int do_linear_search = 1;
>
> + if (BLOCK_HASHTABLE (block))
> + {
> + unsigned int hash_index;
> + hash_index = msymbol_hash_iw (name);
> + hash_index = hash_index % BLOCK_BUCKETS (block);
> + for (sym = BLOCK_BUCKET (block, hash_index); sym; sym = sym->hash_next)
> + {
> + if (SYMBOL_NAMESPACE (sym) == namespace
> + && SYMBOL_MATCHES_NAME (sym, name))
> + return sym;
> + }
> + return NULL;
> + }
> +
> /* If the blocks's symbols were sorted, start with a binary search. */
>
> if (BLOCK_SHOULD_SORT (block))
> @@ -1414,14 +1428,15 @@ find_pc_sect_symtab (CORE_ADDR pc, asect
> if (section != 0)
> {
> int i;
> + struct symbol *sym = NULL;
>
> - for (i = 0; i < b->nsyms; i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - fixup_symbol_section (b->sym[i], objfile);
> - if (section == SYMBOL_BFD_SECTION (b->sym[i]))
> + fixup_symbol_section (sym, objfile);
> + if (section == SYMBOL_BFD_SECTION (sym))
> break;
> }
> - if (i >= b->nsyms)
> + if ((i >= BLOCK_BUCKETS (b)) && (sym == NULL))
> continue; /* no symbol in this symtab matches section */
> }
> distance = BLOCK_END (b) - BLOCK_START (b);
> @@ -2513,13 +2528,18 @@ search_symbols (char *regexp, namespace_
> for (i = GLOBAL_BLOCK; i <= STATIC_BLOCK; i++)
> {
> b = BLOCKVECTOR_BLOCK (bv, i);
> + /* FIXMED: The #if 0'd code seems *very* wrong. It'll sort blocks
> + that we specifically are supposed to avoid sorting. */
> +#if 0
> +
> /* Skip the sort if this block is always sorted. */
> if (!BLOCK_SHOULD_SORT (b))
> sort_block_syms (b);
> - for (j = 0; j < BLOCK_NSYMS (b); j++)
> +#endif
> + ALL_BLOCK_SYMBOLS (b, j, sym)
> {
> QUIT;
> - sym = BLOCK_SYM (b, j);
> + /* FIXME: Hoist file_matches out of this loop. */
> if (file_matches (s->filename, files, nfiles)
> && ((regexp == NULL || SYMBOL_MATCHES_REGEXP (sym))
> && ((kind == VARIABLES_NAMESPACE && SYMBOL_CLASS (sym) != LOC_TYPEDEF
> @@ -2546,6 +2566,7 @@ search_symbols (char *regexp, namespace_
> tail = psr;
> }
> }
> + /* FIXMED: Sort the results? */
> }
> prev_bv = bv;
> }
> @@ -3030,9 +3051,8 @@ make_symbol_completion_list (char *text,
> /* Also catch fields of types defined in this places which match our
> text string. Only complete on types visible from current context. */
>
> - for (i = 0; i < BLOCK_NSYMS (b); i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> COMPLETION_LIST_ADD_SYMBOL (sym, sym_text, sym_text_len, text, word);
> if (SYMBOL_CLASS (sym) == LOC_TYPEDEF)
> {
> @@ -3061,23 +3081,22 @@ make_symbol_completion_list (char *text,
> {
> QUIT;
> b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), GLOBAL_BLOCK);
> - for (i = 0; i < BLOCK_NSYMS (b); i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> COMPLETION_LIST_ADD_SYMBOL (sym, sym_text, sym_text_len, text, word);
> }
> }
>
> ALL_SYMTABS (objfile, s)
> {
> + struct symbol *sym;
> QUIT;
> b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), STATIC_BLOCK);
> /* Don't do this block twice. */
> if (b == surrounding_static_block)
> continue;
> - for (i = 0; i < BLOCK_NSYMS (b); i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> COMPLETION_LIST_ADD_SYMBOL (sym, sym_text, sym_text_len, text, word);
> }
> }
> @@ -3181,16 +3200,14 @@ make_file_symbol_completion_list (char *
> symbols which match. */
>
> b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), GLOBAL_BLOCK);
> - for (i = 0; i < BLOCK_NSYMS (b); i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> COMPLETION_LIST_ADD_SYMBOL (sym, sym_text, sym_text_len, text, word);
> }
>
> b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), STATIC_BLOCK);
> - for (i = 0; i < BLOCK_NSYMS (b); i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> COMPLETION_LIST_ADD_SYMBOL (sym, sym_text, sym_text_len, text, word);
> }
>
> @@ -3568,9 +3585,8 @@ make_symbol_overload_list (struct symbol
> /* Also catch fields of types defined in this places which match our
> text string. Only complete on types visible from current context. */
>
> - for (i = 0; i < BLOCK_NSYMS (b); i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> overload_list_add_symbol (sym, oload_name);
> }
> }
> @@ -3582,9 +3598,8 @@ make_symbol_overload_list (struct symbol
> {
> QUIT;
> b = BLOCKVECTOR_BLOCK (BLOCKVECTOR (s), GLOBAL_BLOCK);
> - for (i = 0; i < BLOCK_NSYMS (b); i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> overload_list_add_symbol (sym, oload_name);
> }
> }
> @@ -3596,9 +3611,8 @@ make_symbol_overload_list (struct symbol
> /* Don't do this block twice. */
> if (b == surrounding_static_block)
> continue;
> - for (i = 0; i < BLOCK_NSYMS (b); i++)
> + ALL_BLOCK_SYMBOLS (b, i, sym)
> {
> - sym = BLOCK_SYM (b, i);
> overload_list_add_symbol (sym, oload_name);
> }
> }
> Index: gdb/symtab.h
> ===================================================================
> RCS file: /cvs/src/src/gdb/symtab.h,v
> retrieving revision 1.24
> diff -u -p -r1.24 symtab.h
> --- symtab.h 2001/07/07 17:19:50 1.24
> +++ symtab.h 2001/10/01 22:20:58
> @@ -449,6 +449,10 @@ struct block
>
> unsigned char gcc_compile_flag;
>
> + /* If this is really a hashtable of the symbols, this flag is 1. */
> +
> + unsigned char hashtable;
> +
> /* Number of local symbols. */
>
> int nsyms;
> @@ -461,18 +465,34 @@ struct block
>
> #define BLOCK_START(bl) (bl)->startaddr
> #define BLOCK_END(bl) (bl)->endaddr
> -#define BLOCK_NSYMS(bl) (bl)->nsyms
> -#define BLOCK_SYM(bl, n) (bl)->sym[n]
> #define BLOCK_FUNCTION(bl) (bl)->function
> #define BLOCK_SUPERBLOCK(bl) (bl)->superblock
> #define BLOCK_GCC_COMPILED(bl) (bl)->gcc_compile_flag
> +#define BLOCK_HASHTABLE(bl) (bl)->hashtable
>
> +/* For BLOCK_HASHTABLE (bl) == 0 blocks only. */
> +#define BLOCK_NSYMS(bl) (bl)->nsyms
> +#define BLOCK_SYM(bl, n) (bl)->sym[n]
> +
> +/* For BLOCK_HASHTABLE (bl) == 1 blocks, but these are valid
> + for non-hashed blocks as well - each symbol will appear to be
> + one bucket by itself. */
> +#define BLOCK_BUCKETS(bl) (bl)->nsyms
> +#define BLOCK_BUCKET(bl, n) (bl)->sym[n]
> +
> +/* Macro to loop through all symbols in a block BL, in no particular order.
> + i counts which bucket we are in, and sym points to the current symbol. */
> +#define ALL_BLOCK_SYMBOLS(bl, i, sym) \
> + for ((i) = 0; (i) < BLOCK_BUCKETS ((bl)); (i)++) \
> + for ((sym) = BLOCK_BUCKET ((bl), (i)); (sym); \
> + (sym) = (sym)->hash_next)
> +
> /* Nonzero if symbols of block BL should be sorted alphabetically.
> Don't sort a block which corresponds to a function. If we did the
> sorting would have to preserve the order of the symbols for the
> arguments. */
>
> -#define BLOCK_SHOULD_SORT(bl) ((bl)->nsyms >= 40 && BLOCK_FUNCTION (bl) == NULL)
> +#define BLOCK_SHOULD_SORT(bl) (!BLOCK_HASHTABLE (bl) && BLOCK_FUNCTION (bl) == NULL)
> \f
>
> /* Represent one symbol name; a variable, constant, function or typedef. */
> @@ -722,6 +742,8 @@ struct symbol
> /* List of ranges where this symbol is active. This is only
> used by alias symbols at the current time. */
> struct range_list *ranges;
> +
> + struct symbol *hash_next;
> };
>
>
> Index: gdb/tracepoint.c
> ===================================================================
> RCS file: /cvs/src/src/gdb/tracepoint.c,v
> retrieving revision 1.26
> diff -u -p -r1.26 tracepoint.c
> --- tracepoint.c 2001/08/23 20:31:36 1.26
> +++ tracepoint.c 2001/10/01 22:20:59
> @@ -1296,16 +1296,14 @@ add_local_symbols (struct collection_lis
> {
> struct symbol *sym;
> struct block *block;
> - int i, nsyms, count = 0;
> + int i, count = 0;
>
> block = block_for_pc (pc);
> while (block != 0)
> {
> QUIT; /* allow user to bail out with ^C */
> - nsyms = BLOCK_NSYMS (block);
> - for (i = 0; i < nsyms; i++)
> + ALL_BLOCK_SYMBOLS (block, i, sym)
> {
> - sym = BLOCK_SYM (block, i);
> switch (SYMBOL_CLASS (sym))
> {
> default:
> @@ -2335,7 +2333,7 @@ scope_info (char *args, int from_tty)
> struct minimal_symbol *msym;
> struct block *block;
> char **canonical, *symname, *save_args = args;
> - int i, j, nsyms, count = 0;
> + int i, j, count = 0;
>
> if (args == 0 || *args == 0)
> error ("requires an argument (function, line or *addr) to define a scope");
> @@ -2351,14 +2349,13 @@ scope_info (char *args, int from_tty)
> while (block != 0)
> {
> QUIT; /* allow user to bail out with ^C */
> - nsyms = BLOCK_NSYMS (block);
> - for (i = 0; i < nsyms; i++)
> + ALL_BLOCK_SYMBOLS (block, i, sym)
> {
> QUIT; /* allow user to bail out with ^C */
> if (count == 0)
> printf_filtered ("Scope for %s:\n", save_args);
> count++;
> - sym = BLOCK_SYM (block, i);
> +
> symname = SYMBOL_NAME (sym);
> if (symname == NULL || *symname == '\0')
> continue; /* probably botched, certainly useless */
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [RFC] Symbol table hashing patch
2001-10-01 16:05 ` Elena Zannoni
@ 2001-10-01 16:38 ` Daniel Jacobowitz
2001-10-01 17:40 ` Daniel Berlin
0 siblings, 1 reply; 4+ messages in thread
From: Daniel Jacobowitz @ 2001-10-01 16:38 UTC (permalink / raw)
To: Elena Zannoni; +Cc: gdb-patches
On Mon, Oct 01, 2001 at 07:12:41PM -0400, Elena Zannoni wrote:
>
>
> As a first comment,, I would strongly reccommend that you break the
> ALL_BLOCK_SYMBOLS changes into a separate patch. That way the
> significant changes to the symtab algorithms will become easier to
> review. It seems from you comments that the MINIMAL_SYMBOL_HASH_SIZE
> is also an independent fix. How about the bug in msymtab_hash_iw, can
> that be separated out as well?
>
> What is 113?
>
Yes, msymtab_hash_iw is also independent.
I'll start breaking it up. On the other hand, I can't do all of it until I
get a little feedback - particularly, the sorting issues. So I would
appreciate any comments on the questions asked in the original message.
As for 113, the exact value is up for debate, but it shows a bit of a
problem with the current hash functions: the values of *string are not
evenly distributed. Multiplying by 31 and then adding an ASCII value
of (usually) ~100 doesn't seem very effective. The thing to do would
probably be to take advantage of Zack Weinberg's recent research; he
spent some time finding a good hash function for the set of
identifiers GCC deals with. It's the same one that this patch
introduces:
#define HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
For reference, the post is:
http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
--
Daniel Jacobowitz Carnegie Mellon University
MontaVista Software Debian GNU/Linux Developer
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [RFC] Symbol table hashing patch
2001-10-01 16:38 ` Daniel Jacobowitz
@ 2001-10-01 17:40 ` Daniel Berlin
0 siblings, 0 replies; 4+ messages in thread
From: Daniel Berlin @ 2001-10-01 17:40 UTC (permalink / raw)
To: Daniel Jacobowitz; +Cc: Elena Zannoni, gdb-patches
On Monday, October 1, 2001, at 07:38 PM, Daniel Jacobowitz wrote:
> On Mon, Oct 01, 2001 at 07:12:41PM -0400, Elena Zannoni wrote:
>>
>>
>> As a first comment,, I would strongly reccommend that you break the
>> ALL_BLOCK_SYMBOLS changes into a separate patch. That way the
>> significant changes to the symtab algorithms will become easier to
>> review. It seems from you comments that the MINIMAL_SYMBOL_HASH_SIZE
>> is also an independent fix. How about the bug in msymtab_hash_iw, can
>> that be separated out as well?
>>
>> What is 113?
>>
>
> Yes, msymtab_hash_iw is also independent.
>
> I'll start breaking it up. On the other hand, I can't do all of it
> until I
> get a little feedback - particularly, the sorting issues. So I would
> appreciate any comments on the questions asked in the original message.
>
> As for 113, the exact value is up for debate, but it shows a bit of a
> problem with the current hash functions: the values of *string are not
> evenly distributed. Multiplying by 31 and then adding an ASCII value
> of (usually) ~100 doesn't seem very effective. The thing to do would
> probably be to take advantage of Zack Weinberg's recent research; he
> spent some time finding a good hash function for the set of
> identifiers GCC deals with. It's the same one that this patch
> introduces:
>
> #define HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
>
Yes, that's where i got it.
It's actually in hashtab.c, named htab_hash_string
It beats the FNV-1 hash (in terms of good distributions) by a small
amount on strings, but not on other things.
> For reference, the post is:
> http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
>
> --
> Daniel Jacobowitz Carnegie Mellon University
> MontaVista Software Debian GNU/Linux Developer
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2001-10-01 17:40 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2001-10-01 15:46 [RFC] Symbol table hashing patch Daniel Jacobowitz
2001-10-01 16:05 ` Elena Zannoni
2001-10-01 16:38 ` Daniel Jacobowitz
2001-10-01 17:40 ` Daniel Berlin
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox