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
Daniel Jacobowitz writes:
> 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.
ok
Elena
>
> 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)