From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2126) id 998333858002; Mon, 28 Mar 2022 19:56:18 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 998333858002 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable From: Tom Tromey To: gdb-cvs@sourceware.org Subject: [binutils-gdb] Change call_site_find_chain_1 to work recursively X-Act-Checkin: binutils-gdb X-Git-Author: Tom Tromey X-Git-Refname: refs/heads/master X-Git-Oldrev: 394d8c59ea961e1dcf89ec6c8b6d6606b361590a X-Git-Newrev: 206bedc2aa113eb3f7cb58668944eb7df82b8894 Message-Id: <20220328195618.998333858002@sourceware.org> Date: Mon, 28 Mar 2022 19:56:18 +0000 (GMT) X-BeenThere: gdb-cvs@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 28 Mar 2022 19:56:18 -0000 https://sourceware.org/git/gitweb.cgi?p=3Dbinutils-gdb.git;h=3D206bedc2aa11= 3eb3f7cb58668944eb7df82b8894 commit 206bedc2aa113eb3f7cb58668944eb7df82b8894 Author: Tom Tromey Date: Fri Nov 19 09:23:09 2021 -0700 Change call_site_find_chain_1 to work recursively =20 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. =20 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: =20 if (target_call_site) { if (addr_hash.insert (target_call_site->pc ()).second) { /* Successfully entered TARGET_CALL_SITE. */ =20 chain.push_back (target_call_site); break; } } =20 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. =20 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 <=3D (*resultp)->l= ength); } =20 -/* 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 =3D call_site->address (gdbarch, nullptr); + + if (target_func_addr =3D=3D 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 !=3D nullptr; + } + + struct symbol *target_func + =3D func_addr_to_tail_call_list (gdbarch, target_func_addr); + for (struct call_site *target_call_site + =3D TYPE_TAIL_CALL_LIST (target_func->type ()); + target_call_site !=3D nullptr; + target_call_site =3D 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 =3D addr_hash.erase (target_call_site->pc ()); + gdb_assert (removed =3D=3D 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. */ =20 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, COR= E_ADDR caller_pc, target's function will get iterated as already pushed into CHAIN via = their TAIL_CALL_NEXT. */ call_site =3D 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 =3D call_site->address (gdbarch, nullptr); - - if (target_func_addr =3D=3D callee_pc) - { - chain_candidate (gdbarch, &retval, chain); - if (retval =3D=3D 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 =3D NULL; - } - else - { - struct symbol *target_func; - - target_func =3D func_addr_to_tail_call_list (gdbarch, target_func_addr); - target_call_site =3D 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 =3D NULL; - while (!chain.empty ()) - { - call_site =3D chain.back (); - chain.pop_back (); - - size_t removed =3D addr_hash.erase (call_site->pc ()); - gdb_assert (removed =3D=3D 1); - - target_call_site =3D call_site->tail_call_next; - if (target_call_site) - break; - } - } - while (target_call_site); - - if (chain.empty ()) - call_site =3D NULL; - else - call_site =3D 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); =20 if (retval =3D=3D NULL) { diff --git a/gdb/testsuite/gdb.arch/amd64-entry-value.exp b/gdb/testsuite/g= db.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=3D, j= =3D\\)\[^\r\n\]* =20 gdb_continue_to_breakpoint "self: breakhere" =20 -gdb_test "bt" "^bt\r\n#0 +d \\(i=3D, j=3D\\)= \[^\r\n\]*\r\n#1 +0x\[0-9a-f\]+ in self \\(i=3D\\)\[^\r\n\]*= \r\n#2 +0x\[0-9a-f\]+ in main \\(\\)\[^\r\n\]*" \ +gdb_test "bt" "^bt\r\n#0 +d \\(i=3D, j=3D\\)= \[^\r\n\]*\r\n#1 +0x\[0-9a-f\]+ in self \\(i=3D\\)\[^\r\n\]*= \r\n#2 +0x\[0-9a-f\]+ in self2 \\(i=3D\\)\[^\r\n\]*\r\n#3 +0= x\[0-9a-f\]+ in self \\(i=3D\\)\[^\r\n\]*\r\n#4 +0x\[0-9a-f\= ]+ in main \\(\\)\[^\r\n\]*" \ "self: bt" =20 gdb_test_no_output "set debug entry-values 1"