From 206bedc2aa113eb3f7cb58668944eb7df82b8894 Mon Sep 17 00:00:00 2001 From: Tom Tromey Date: Fri, 19 Nov 2021 09:23:09 -0700 Subject: [PATCH] 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. --- 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 *resultp, + std::vector &chain, + std::unordered_set &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_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=, j=\\)\[^\r\n\]* gdb_continue_to_breakpoint "self: breakhere" -gdb_test "bt" "^bt\r\n#0 +d \\(i=, j=\\)\[^\r\n\]*\r\n#1 +0x\[0-9a-f\]+ in self \\(i=\\)\[^\r\n\]*\r\n#2 +0x\[0-9a-f\]+ in main \\(\\)\[^\r\n\]*" \ +gdb_test "bt" "^bt\r\n#0 +d \\(i=, j=\\)\[^\r\n\]*\r\n#1 +0x\[0-9a-f\]+ in self \\(i=\\)\[^\r\n\]*\r\n#2 +0x\[0-9a-f\]+ in self2 \\(i=\\)\[^\r\n\]*\r\n#3 +0x\[0-9a-f\]+ in self \\(i=\\)\[^\r\n\]*\r\n#4 +0x\[0-9a-f\]+ in main \\(\\)\[^\r\n\]*" \ "self: bt" gdb_test_no_output "set debug entry-values 1" -- 2.30.2