From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21607 invoked by alias); 8 Jan 2003 14:22:09 -0000 Mailing-List: contact gdb-patches-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sources.redhat.com Received: (qmail 21598 invoked from network); 8 Jan 2003 14:22:06 -0000 Received: from unknown (HELO mx1.redhat.com) (66.187.233.31) by 209.249.29.67 with SMTP; 8 Jan 2003 14:22:06 -0000 Received: from int-mx1.corp.redhat.com (int-mx1.corp.redhat.com [172.16.52.254]) by mx1.redhat.com (8.11.6/8.11.6) with ESMTP id h08DsCB32265 for ; Wed, 8 Jan 2003 08:54:12 -0500 Received: from pobox.corp.redhat.com (pobox.corp.redhat.com [172.16.52.156]) by int-mx1.corp.redhat.com (8.11.6/8.11.6) with ESMTP id h08ELsa12614 for ; Wed, 8 Jan 2003 09:21:54 -0500 Received: from localhost.redhat.com (romulus-int.sfbay.redhat.com [172.16.27.46]) by pobox.corp.redhat.com (8.11.6/8.11.6) with ESMTP id h08ELqn11573; Wed, 8 Jan 2003 09:21:52 -0500 Received: by localhost.redhat.com (Postfix, from userid 469) id 6152FFF79; Wed, 8 Jan 2003 09:26:16 -0500 (EST) From: Elena Zannoni MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15900.13576.228928.516401@localhost.redhat.com> Date: Wed, 08 Jan 2003 14:22:00 -0000 To: Daniel Jacobowitz Cc: Elena Zannoni , gdb-patches@sources.redhat.com, jimb@redhat.com Subject: Re: [RFA] Kill some linear searches in minsyms.c In-Reply-To: <20030107230747.GD20617@nevyn.them.org> References: <20030106042203.GA28848@nevyn.them.org> <15897.54742.251353.385541@localhost.redhat.com> <20030107230747.GD20617@nevyn.them.org> X-SW-Source: 2003-01/txt/msg00321.txt.bz2 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 > > > > > > From Tom Tromey and Keith Seitz : > > > > > > * minsyms.c: #include , 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 > > > > > > * 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 > > * 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)