public inbox for gdb-cvs@sourceware.org help / color / mirror / Atom feed
From: Tom Tromey <tromey@sourceware.org> To: gdb-cvs@sourceware.org Subject: [binutils-gdb] Change call_site_find_chain_1 to work recursively Date: Mon, 28 Mar 2022 19:56:18 +0000 (GMT) [thread overview] Message-ID: <20220328195618.998333858002@sourceware.org> (raw) https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=206bedc2aa113eb3f7cb58668944eb7df82b8894 commit 206bedc2aa113eb3f7cb58668944eb7df82b8894 Author: Tom Tromey <tromey@adacore.com> Date: Fri Nov 19 09:23:09 2021 -0700 Change call_site_find_chain_1 to work recursively call_site_find_chain_1 has a comment claiming that recursive calls would be too expensive. However, I doubt this is so expensive; and furthermore the explicit state management approach here is difficult both to understand and to modify. This patch changes this code to use explicit recursion, so that a subsequent patch can generalize this code without undue trauma. Additionally, I think this patch detects a latent bug in the recursion code. (It's hard for me to be completely certain.) The bug is that when a new target_call_site is entered, the code does: if (target_call_site) { if (addr_hash.insert (target_call_site->pc ()).second) { /* Successfully entered TARGET_CALL_SITE. */ chain.push_back (target_call_site); break; } } Here, if entering the target_call_site fails, then any tail_call_next elements in this call site are not visited. However, if this code does happen to enter a call site, then the tail_call_next elements will be visited during backtracking. This applies when doing the backtracking as well -- it will only continue through a given chain as long as each element in the chain can successfully be visited. I'd appreciate some review of this. If this behavior is intentional, it can be added to the new implementation. Diff: --- gdb/dwarf2/loc.c | 136 +++++++++++++-------------- gdb/testsuite/gdb.arch/amd64-entry-value.exp | 2 +- 2 files changed, 64 insertions(+), 74 deletions(-) diff --git a/gdb/dwarf2/loc.c b/gdb/dwarf2/loc.c index addf611d8f8..eb1312a5619 100644 --- a/gdb/dwarf2/loc.c +++ b/gdb/dwarf2/loc.c @@ -924,11 +924,65 @@ chain_candidate (struct gdbarch *gdbarch, gdb_assert ((*resultp)->callers + (*resultp)->callees <= (*resultp)->length); } -/* Create and return call_site_chain for CALLER_PC and CALLEE_PC. All the - assumed frames between them use GDBARCH. Use depth first search so we can - keep single CHAIN of call_site's back to CALLER_PC. Function recursion - would have needless GDB stack overhead. Any unreliability results - in thrown NO_ENTRY_VALUE_ERROR. */ +/* Recursively try to construct the call chain. GDBARCH, RESULTP, and + CHAIN are passed to chain_candidate. ADDR_HASH tracks which + addresses have already been seen along the current chain. + CALL_SITE is the call site to visit, and CALLEE_PC is the PC we're + trying to "reach". Returns false if an error has already been + detected and so an early return can be done. If it makes sense to + keep trying (even if no answer has yet been found), returns + true. */ + +static bool +call_site_find_chain_2 + (struct gdbarch *gdbarch, + gdb::unique_xmalloc_ptr<struct call_site_chain> *resultp, + std::vector<struct call_site *> &chain, + std::unordered_set<CORE_ADDR> &addr_hash, + struct call_site *call_site, + CORE_ADDR callee_pc) +{ + /* CALLER_FRAME with registers is not available for tail-call jumped + frames. */ + CORE_ADDR target_func_addr = call_site->address (gdbarch, nullptr); + + if (target_func_addr == callee_pc) + { + chain_candidate (gdbarch, resultp, chain); + /* If RESULTP was reset, then chain_candidate failed, and so we + can tell our callers to early-return. */ + return *resultp != nullptr; + } + + struct symbol *target_func + = func_addr_to_tail_call_list (gdbarch, target_func_addr); + for (struct call_site *target_call_site + = TYPE_TAIL_CALL_LIST (target_func->type ()); + target_call_site != nullptr; + target_call_site = target_call_site->tail_call_next) + { + if (addr_hash.insert (target_call_site->pc ()).second) + { + /* Successfully entered TARGET_CALL_SITE. */ + chain.push_back (target_call_site); + + if (!call_site_find_chain_2 (gdbarch, resultp, chain, + addr_hash, target_call_site, + callee_pc)) + return false; + + size_t removed = addr_hash.erase (target_call_site->pc ()); + gdb_assert (removed == 1); + chain.pop_back (); + } + } + + return true; +} + +/* Create and return call_site_chain for CALLER_PC and CALLEE_PC. All + the assumed frames between them use GDBARCH. Any unreliability + results in thrown NO_ENTRY_VALUE_ERROR. */ static gdb::unique_xmalloc_ptr<call_site_chain> call_site_find_chain_1 (struct gdbarch *gdbarch, CORE_ADDR caller_pc, @@ -958,74 +1012,10 @@ call_site_find_chain_1 (struct gdbarch *gdbarch, CORE_ADDR caller_pc, target's function will get iterated as already pushed into CHAIN via their TAIL_CALL_NEXT. */ call_site = call_site_for_pc (gdbarch, caller_pc); - - while (call_site) - { - CORE_ADDR target_func_addr; - struct call_site *target_call_site; - - /* CALLER_FRAME with registers is not available for tail-call jumped - frames. */ - target_func_addr = call_site->address (gdbarch, nullptr); - - if (target_func_addr == callee_pc) - { - chain_candidate (gdbarch, &retval, chain); - if (retval == NULL) - break; - - /* There is no way to reach CALLEE_PC again as we would prevent - entering it twice as being already marked in ADDR_HASH. */ - target_call_site = NULL; - } - else - { - struct symbol *target_func; - - target_func = func_addr_to_tail_call_list (gdbarch, target_func_addr); - target_call_site = TYPE_TAIL_CALL_LIST (target_func->type ()); - } - - do - { - /* Attempt to visit TARGET_CALL_SITE. */ - - if (target_call_site) - { - if (addr_hash.insert (target_call_site->pc ()).second) - { - /* Successfully entered TARGET_CALL_SITE. */ - - chain.push_back (target_call_site); - break; - } - } - - /* Backtrack (without revisiting the originating call_site). Try the - callers's sibling; if there isn't any try the callers's callers's - sibling etc. */ - - target_call_site = NULL; - while (!chain.empty ()) - { - call_site = chain.back (); - chain.pop_back (); - - size_t removed = addr_hash.erase (call_site->pc ()); - gdb_assert (removed == 1); - - target_call_site = call_site->tail_call_next; - if (target_call_site) - break; - } - } - while (target_call_site); - - if (chain.empty ()) - call_site = NULL; - else - call_site = chain.back (); - } + /* No need to check the return value here, because we no longer care + about possible early returns. */ + call_site_find_chain_2 (gdbarch, &retval, chain, addr_hash, call_site, + callee_pc); if (retval == NULL) { diff --git a/gdb/testsuite/gdb.arch/amd64-entry-value.exp b/gdb/testsuite/gdb.arch/amd64-entry-value.exp index 4f06a303ab2..485d8a5cd1b 100644 --- a/gdb/testsuite/gdb.arch/amd64-entry-value.exp +++ b/gdb/testsuite/gdb.arch/amd64-entry-value.exp @@ -253,7 +253,7 @@ gdb_test "bt" "^bt\r\n#0 +d \\(i=<optimized out>, j=<optimized out>\\)\[^\r\n\]* gdb_continue_to_breakpoint "self: breakhere" -gdb_test "bt" "^bt\r\n#0 +d \\(i=<optimized out>, j=<optimized out>\\)\[^\r\n\]*\r\n#1 +0x\[0-9a-f\]+ in self \\(i=<optimized out>\\)\[^\r\n\]*\r\n#2 +0x\[0-9a-f\]+ in main \\(\\)\[^\r\n\]*" \ +gdb_test "bt" "^bt\r\n#0 +d \\(i=<optimized out>, j=<optimized out>\\)\[^\r\n\]*\r\n#1 +0x\[0-9a-f\]+ in self \\(i=<optimized out>\\)\[^\r\n\]*\r\n#2 +0x\[0-9a-f\]+ in self2 \\(i=<optimized out>\\)\[^\r\n\]*\r\n#3 +0x\[0-9a-f\]+ in self \\(i=<optimized out>\\)\[^\r\n\]*\r\n#4 +0x\[0-9a-f\]+ in main \\(\\)\[^\r\n\]*" \ "self: bt" gdb_test_no_output "set debug entry-values 1"
reply other threads:[~2022-03-28 19:56 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20220328195618.998333858002@sourceware.org \ --to=tromey@sourceware.org \ --cc=gdb-cvs@sourceware.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).