From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 19293 invoked by alias); 7 Jan 2003 23:07:44 -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 19284 invoked from network); 7 Jan 2003 23:07:43 -0000 Received: from unknown (HELO crack.them.org) (65.125.64.184) by 209.249.29.67 with SMTP; 7 Jan 2003 23:07:43 -0000 Received: from nevyn.them.org ([66.93.61.169] ident=mail) by crack.them.org with asmtp (Exim 3.12 #1 (Debian)) id 18W4hT-0006qr-00; Tue, 07 Jan 2003 19:08:07 -0600 Received: from drow by nevyn.them.org with local (Exim 3.36 #1 (Debian)) id 18W2p2-0007LJ-00; Tue, 07 Jan 2003 18:07:48 -0500 Date: Tue, 07 Jan 2003 23:07:00 -0000 From: Daniel Jacobowitz To: Elena Zannoni Cc: gdb-patches@sources.redhat.com, jimb@redhat.com Subject: Re: [RFA] Kill some linear searches in minsyms.c Message-ID: <20030107230747.GD20617@nevyn.them.org> Mail-Followup-To: Elena Zannoni , gdb-patches@sources.redhat.com, jimb@redhat.com References: <20030106042203.GA28848@nevyn.them.org> <15897.54742.251353.385541@localhost.redhat.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <15897.54742.251353.385541@localhost.redhat.com> User-Agent: Mutt/1.5.1i X-SW-Source: 2003-01/txt/msg00297.txt.bz2 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. 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)