This is the mail archive of the
gdb-patches@sources.redhat.com
mailing list for the GDB project.
Re: [RFA] Kill some linear searches in minsyms.c
On Mon, Jan 06, 2003 at 02:15:34PM -0500, Elena Zannoni wrote:
> Daniel Jacobowitz writes:
> > So uh, yeah, and stuff. I found an interesting one today when I wasn't even
> > looking for it. Earlier today I posted an updated patch to make it easy,
> > very easy, to profile GDB. Here's a pretty good sample of why I think this
> > is important. I was actually looking for something completely different,
> > but I noticed this on the way.
> >
> > Consider this patch:
> >
> > 2000-03-06 Jim Blandy <jimb@redhat.com>
> >
> > From Tom Tromey <tromey@cygnus.com> and Keith Seitz <?>:
> >
> > * minsyms.c: #include <ctype.h>, for msymbol_hash_iw.
> > (compact_minimal_symbols): Added `objfile' argument.
> > Put symbols in the objfile's hash table.
> > (install_minimal_symbols): Put symbols in the objfile's demangled
> > hash table.
> > (lookup_minimal_symbol): Use hash table to find symbol in
> > objfile.
> > (msymbol_hash_iw, msymbol_hash, add_minsym_to_hash_table): New
> > functions.
> > (prim_record_minimal_symbol_and_info): Initialize the
> > hash link fields of the new minimal symbol.
> > * symtab.h (struct minimal_symbol): New fields `hash_next',
> > `demangled_hash_next'.
> > (msymbol_hash_iw, msymbol_hash, add_minsym_to_hash_table): Declare.
> > * objfiles.h (MINIMAL_SYMBOL_HASH_SIZE): New define.
> > (struct objfile): New fields `msymbol_hash',
> > `msymbol_demangled_hash'.
> >
> > These replaced a linear search with a hash table. We'd better use it, too,
> > since a good-sized application has an awful lot of minimal symbols.
> > However, two other related functions (that's lookup_minimal_symbol_text and
> > lookup_minimal_symbol_solib_trampoline) were not converted. These get
> > called reasonably often, vis:
> >
>
> What command gdb executing at this point?
My impression was that we had hit a shared library event (Mozilla
plugins are DSOs, so there's lots of these!). Then we call
breakpoint_re_set, which calls breakpoint_re_set_one and then
create_longjmp_breakpoint several times.
> > 0.75 0.43 62/310 create_overlay_event_breakpoint [16]
> > 3.01 1.72 248/310 create_longjmp_breakpoint [5]
> > [4] 48.1 3.76 2.16 310 lookup_minimal_symbol_text [4]
> >
> > That "3.76" is in _seconds_, by the way. Then they proceed to do:
> > 1.26 0.00 9567591/9567734 strcmp_iw [15]
> > 0.90 0.00 27551335/30742029 symbol_demangled_name [17]
> >
> > 27.5 million calls to a wrapper function. My first instinct was that a
> > wrapper function was a bad idea, then. My second instinct was to smack my
> > first instinct upside the head and find out why we were calling it so many
> > times, since I knew we hashed minsyms. Converting them to the hash table
> > once I found the problem was quite easy. The patch is attached; is it OK to
> > commit? No regressions on i386-pc-linux-gnu, for what that's worth, and
> > it's quite straightforward.
> >
>
> how do the numbers for those functions look after your patch?
lookup_minimal_symbol_text and symbol_demangled_name essentially drop
off the profile. symbol_demangled_name still has 3.3 million calls
from some psymbols functions but that's not as bad as before.
> > 2003-01-05 Daniel Jacobowitz <drow@mvista.com>
> >
> > * minsyms.c (enum ms_search_which): New.
> > (lookup_minimal_symbol_internal): New function, broken out from
> > lookup_minimal_symbol.
> > (lookup_minimal_symbol, lookup_minimal_symbol_text)
> > (lookup_minimal_symbol_solib_trampoline): Use them.
> ^^^^
> lookup_minimal_symbol_internal???
>
> I don't like the _internal part, could you call it '_aux' instead?
> This seems more in line with the rest of gdb's names. Hmm, but maybe
> we already have a function by that name. I also winder how much work
Sure, I don't think we do.
> would it be to eventually remove these new functions, that now become
> wrappers.
I'd rather not expose ms_search_which. It's a little hacky; I just
wanted to share the code for the search.
> > + /* Select hash list according to pass. */
> > + if (pass == 1)
> > + msymbol = objfile->msymbol_hash[hash];
> > + else
> > + msymbol = objfile->msymbol_demangled_hash[dem_hash];
> > +
> > + for (; msymbol != NULL && found_symbol == NULL;
> > + msymbol = (pass == 1)
> > + ? msymbol->hash_next
> > + : msymbol->demangled_hash_next)
>
> please, don't do this. This is much worse than the previous while, with the
> updates at the end.
OK. I did that after adding a continue and discovering that I'd
introduced an infinite loop.
> > +
> > + if (which == ms_search_text
> > + && MSYMBOL_TYPE (msymbol) != mst_file_text
> > + && MSYMBOL_TYPE (msymbol) != mst_text)
> > + continue;
> > +
>
> I don't like the fact that the check for ms_search_all is buried
> inside the switch statement, while the other 2 are here. Could you
> have an outer switch for the ms_search_*? Also with your changes will
> the internal switch case mst_solib_trampoline ever be reached? It
> seems like we would find it earlier and return right away.
> The whole flow of control of this function seems a bit confused.
It is, and I only made it more so. Tell you what... I'm going to do
this differently. The callers of lookup_minimal_symbol_text never want
to search the demangled hash anyway; they're looking for linkage names.
Ditto for lookup_minimal_symbol_solib_trampoline. Here's a much more
minimal patch to solve the problem; we can clean up
lookup_minimal_symbol's twisted search logic and the code duplication
separately, later.
Still passes make check, still shaves six seconds (thirty percent or
so) off of "file mozilla-bin; run; exit". Still correctly sets the
longjmp breakpoint once libc has been loaded; I checked that by hand.
--
Daniel Jacobowitz
MontaVista Software Debian GNU/Linux Developer
2003-01-07 Daniel Jacobowitz <drow@mvista.com>
* minsyms.c (lookup_minimal_symbol): Update comment.
(lookup_minimal_symbol_text): Update comment. Use the hash table.
(lookup_minimal_symbol_solib_trampoline): Likewise.
Index: minsyms.c
===================================================================
RCS file: /cvs/src/src/gdb/minsyms.c,v
retrieving revision 1.22
diff -u -p -r1.22 minsyms.c
--- minsyms.c 11 Jul 2002 20:46:19 -0000 1.22
+++ minsyms.c 7 Jan 2003 23:06:57 -0000
@@ -135,14 +135,15 @@ add_minsym_to_demangled_hash_table (stru
/* Look through all the current minimal symbol tables and find the
first minimal symbol that matches NAME. If OBJF is non-NULL, limit
- the search to that objfile. If SFILE is non-NULL, limit the search
- to that source file. Returns a pointer to the minimal symbol that
+ the search to that objfile. If SFILE is non-NULL, the only file-scope
+ symbols considered will be from that source file (global symbols are
+ still preferred). Returns a pointer to the minimal symbol that
matches, or NULL if no match is found.
Note: One instance where there may be duplicate minimal symbols with
the same name is when the symbol tables for a shared library and the
symbol tables for an executable contain global symbols with the same
- names (the dynamic linker deals with the duplication). */
+ names (the dynamic linker deals with the duplication). */
struct minimal_symbol *
lookup_minimal_symbol (register const char *name, const char *sfile,
@@ -248,12 +249,13 @@ lookup_minimal_symbol (register const ch
}
/* Look through all the current minimal symbol tables and find the
- first minimal symbol that matches NAME and of text type.
- If OBJF is non-NULL, limit
- the search to that objfile. If SFILE is non-NULL, limit the search
- to that source file. Returns a pointer to the minimal symbol that
- matches, or NULL if no match is found.
- */
+ first minimal symbol that matches NAME and has text type. If OBJF
+ is non-NULL, limit the search to that objfile. If SFILE is non-NULL,
+ the only file-scope symbols considered will be from that source file
+ (global symbols are still preferred). Returns a pointer to the minimal
+ symbol that matches, or NULL if no match is found.
+
+ This function only searches the mangled (linkage) names. */
struct minimal_symbol *
lookup_minimal_symbol_text (register const char *name, const char *sfile,
@@ -264,6 +266,8 @@ lookup_minimal_symbol_text (register con
struct minimal_symbol *found_symbol = NULL;
struct minimal_symbol *found_file_symbol = NULL;
+ unsigned int hash = msymbol_hash (name) % MINIMAL_SYMBOL_HASH_SIZE;
+
#ifdef SOFUN_ADDRESS_MAYBE_MISSING
if (sfile != NULL)
{
@@ -279,10 +283,9 @@ lookup_minimal_symbol_text (register con
{
if (objf == NULL || objf == objfile)
{
- for (msymbol = objfile->msymbols;
- msymbol != NULL && SYMBOL_NAME (msymbol) != NULL &&
- found_symbol == NULL;
- msymbol++)
+ for (msymbol = objfile->msymbol_hash[hash];
+ msymbol != NULL && found_symbol == NULL;
+ msymbol = msymbol->hash_next)
{
if (SYMBOL_MATCHES_NAME (msymbol, name) &&
(MSYMBOL_TYPE (msymbol) == mst_text ||
@@ -323,12 +326,13 @@ lookup_minimal_symbol_text (register con
}
/* Look through all the current minimal symbol tables and find the
- first minimal symbol that matches NAME and of solib trampoline type.
- If OBJF is non-NULL, limit
- the search to that objfile. If SFILE is non-NULL, limit the search
- to that source file. Returns a pointer to the minimal symbol that
- matches, or NULL if no match is found.
- */
+ first minimal symbol that matches NAME and is a solib trampoline. If OBJF
+ is non-NULL, limit the search to that objfile. If SFILE is non-NULL,
+ the only file-scope symbols considered will be from that source file
+ (global symbols are still preferred). Returns a pointer to the minimal
+ symbol that matches, or NULL if no match is found.
+
+ This function only searches the mangled (linkage) names. */
struct minimal_symbol *
lookup_minimal_symbol_solib_trampoline (register const char *name,
@@ -338,6 +342,8 @@ lookup_minimal_symbol_solib_trampoline (
struct minimal_symbol *msymbol;
struct minimal_symbol *found_symbol = NULL;
+ unsigned int hash = msymbol_hash (name) % MINIMAL_SYMBOL_HASH_SIZE;
+
#ifdef SOFUN_ADDRESS_MAYBE_MISSING
if (sfile != NULL)
{
@@ -353,10 +359,9 @@ lookup_minimal_symbol_solib_trampoline (
{
if (objf == NULL || objf == objfile)
{
- for (msymbol = objfile->msymbols;
- msymbol != NULL && SYMBOL_NAME (msymbol) != NULL &&
- found_symbol == NULL;
- msymbol++)
+ for (msymbol = objfile->msymbol_hash[hash];
+ msymbol != NULL && found_symbol == NULL;
+ msymbol = msymbol->hash_next)
{
if (SYMBOL_MATCHES_NAME (msymbol, name) &&
MSYMBOL_TYPE (msymbol) == mst_solib_trampoline)