From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-io1-xd2d.google.com (mail-io1-xd2d.google.com [IPv6:2607:f8b0:4864:20::d2d]) by sourceware.org (Postfix) with ESMTPS id CF546385842F for ; Wed, 1 Dec 2021 22:04:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org CF546385842F Received: by mail-io1-xd2d.google.com with SMTP id v23so32877318iom.12 for ; Wed, 01 Dec 2021 14:04:39 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=/Fj1JKwG+oDzaGZxtDebIor6bnm+voLH6MfqDw75gbw=; b=SOns+RM3Xdt1Pho/N7DyMk3Pw5eiQmUnOmYnWwEELvRBYPJGI0sDqLgm+vQ/QVL2hA JRHa7RwcDC4JZi6B87FskKGE5HrALckwjVWnqsUc4JlM/Exhx9SqtW2+P5tmoLWW91hh 8lUMXRCFYHxYFzw/wjftaOJj11QVAuF7aW+bQeLtDUZA5Me+36VQCCmzdeTwnwV1XUm+ Thih2gcL25ounM7FqEbHNweL019H4QseqgaJa4h08srH8NEe3QXxSzCj1H/ASBhUrlFU Um2553+WGQm6xgoaqw36CbuQ0a+7i3j5ihNaFM6Jtt71q2Hg7V7tR96JF8O8LgQKEGlo SpkQ== X-Gm-Message-State: AOAM532eHmyfPGFfWGO4lp+16BOy7Tq4slrQFNTtVg7IrWT9mtis6JXR rNWZ1QSNsoGOAxb9/GsNC0KgdxpIoeXT9g== X-Google-Smtp-Source: ABdhPJxZ+Reyl+yMJ86EkHSkRmxecXcv2k2GGgLZwIM+H4+sQP+GVftjasaryTXNLeGc8wNFSIjVfg== X-Received: by 2002:a05:6638:130f:: with SMTP id r15mr14638559jad.19.1638396279049; Wed, 01 Dec 2021 14:04:39 -0800 (PST) Received: from murgatroyd.Home (97-122-84-67.hlrn.qwest.net. [97.122.84.67]) by smtp.gmail.com with ESMTPSA id l18sm622298iob.17.2021.12.01.14.04.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 01 Dec 2021 14:04:38 -0800 (PST) From: Tom Tromey To: gdb-patches@sourceware.org Cc: Tom Tromey Subject: [PATCH 4/6] Change call_site_find_chain_1 to work recursively Date: Wed, 1 Dec 2021 15:04:30 -0700 Message-Id: <20211201220432.4105152-5-tromey@adacore.com> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20211201220432.4105152-1-tromey@adacore.com> References: <20211201220432.4105152-1-tromey@adacore.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-10.6 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_STOCKGEN, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gdb-patches@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gdb-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 01 Dec 2021 22:04:41 -0000 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 e793bbffd05..398538b54f8 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 (SYMBOL_TYPE (target_func)); + 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 (SYMBOL_TYPE (target_func)); - } - - 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 fdfa4a01b58..386388d71b4 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.31.1