From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 2091 invoked by alias); 13 Feb 2017 12:38:14 -0000 Mailing-List: contact gdb-patches-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sourceware.org Received: (qmail 1970 invoked by uid 89); 13 Feb 2017 12:38:13 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=1.3 required=5.0 tests=AWL,BAYES_50,KAM_LAZY_DOMAIN_SECURITY,RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=1876, timwiederhakeintelcom, tim.wiederhake@intel.com, sk:btrace_ X-HELO: mga07.intel.com Received: from mga07.intel.com (HELO mga07.intel.com) (134.134.136.100) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 13 Feb 2017 12:38:12 +0000 Received: from orsmga003.jf.intel.com ([10.7.209.27]) by orsmga105.jf.intel.com with ESMTP; 13 Feb 2017 04:38:10 -0800 X-ExtLoop1: 1 Received: from irvmail001.ir.intel.com ([163.33.26.43]) by orsmga003.jf.intel.com with ESMTP; 13 Feb 2017 04:38:09 -0800 Received: from ulvlx001.iul.intel.com (ulvlx001.iul.intel.com [172.28.207.17]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id v1DCc8Ih010232; Mon, 13 Feb 2017 12:38:08 GMT Received: from ulvlx001.iul.intel.com (localhost [127.0.0.1]) by ulvlx001.iul.intel.com with ESMTP id v1DCc89j011593; Mon, 13 Feb 2017 13:38:08 +0100 Received: (from twiederh@localhost) by ulvlx001.iul.intel.com with œ id v1DCc8ee011589; Mon, 13 Feb 2017 13:38:08 +0100 From: Tim Wiederhake To: gdb-patches@sourceware.org Cc: markus.t.metzger@intel.com, palves@redhat.com, xdje42@gmail.com Subject: [PATCH v6 3/9] btrace: Use binary search to find instruction. Date: Mon, 13 Feb 2017 12:38:00 -0000 Message-Id: <1486989450-11313-4-git-send-email-tim.wiederhake@intel.com> In-Reply-To: <1486989450-11313-1-git-send-email-tim.wiederhake@intel.com> References: <1486989450-11313-1-git-send-email-tim.wiederhake@intel.com> X-IsSubscribed: yes X-SW-Source: 2017-02/txt/msg00328.txt.bz2 Currently, btrace_find_insn_by_number will iterate over all function call segments to find the one that contains the needed instruction. This linear search is too slow for the upcoming Python bindings that will use this function to access instructions. This patch introduces a vector in struct btrace_thread_info that holds pointers to all recorded function segments and allows to use binary search. The proper solution is to turn the underlying tree into a vector of objects and use indices for access. This requires more work. A patch set is currently being worked on and will be published later. 2017-02-13 Tim Wiederhake gdb/ChangeLog: * btrace.c (btrace_fetch): Copy function call segments pointer into a vector. (btrace_clear): Clear the vector. (btrace_find_insn_by_number): Use binary search to find the correct function call segment. * btrace.h (brace_fun_p): New typedef. (struct btrace_thread_info) : New field. --- gdb/btrace.c | 45 +++++++++++++++++++++++++++++++++++++++------ gdb/btrace.h | 7 +++++++ 2 files changed, 46 insertions(+), 6 deletions(-) diff --git a/gdb/btrace.c b/gdb/btrace.c index 3c32f09..e242a89 100644 --- a/gdb/btrace.c +++ b/gdb/btrace.c @@ -1837,13 +1837,19 @@ btrace_fetch (struct thread_info *tp) /* Compute the trace, provided we have any. */ if (!btrace_data_empty (&btrace)) { + struct btrace_function *bfun; + /* Store the raw trace data. The stored data will be cleared in btrace_clear, so we always append the new trace. */ btrace_data_append (&btinfo->data, &btrace); btrace_maint_clear (btinfo); + VEC_truncate (btrace_fun_p, btinfo->functions, 0); btrace_clear_history (btinfo); btrace_compute_ftrace (tp, &btrace); + + for (bfun = btinfo->begin; bfun != NULL; bfun = bfun->flow.next) + VEC_safe_push (btrace_fun_p, btinfo->functions, bfun); } do_cleanups (cleanup); @@ -1866,6 +1872,8 @@ btrace_clear (struct thread_info *tp) btinfo = &tp->btrace; + VEC_free (btrace_fun_p, btinfo->functions); + it = btinfo->begin; while (it != NULL) { @@ -2456,20 +2464,45 @@ btrace_find_insn_by_number (struct btrace_insn_iterator *it, unsigned int number) { const struct btrace_function *bfun; + unsigned int upper, lower; - for (bfun = btinfo->end; bfun != NULL; bfun = bfun->flow.prev) - if (bfun->insn_offset <= number) - break; + if (VEC_empty (btrace_fun_p, btinfo->functions)) + return 0; - if (bfun == NULL) + lower = 0; + bfun = VEC_index (btrace_fun_p, btinfo->functions, lower); + if (number < bfun->insn_offset) return 0; - if (bfun->insn_offset + ftrace_call_num_insn (bfun) <= number) + upper = VEC_length (btrace_fun_p, btinfo->functions) - 1; + bfun = VEC_index (btrace_fun_p, btinfo->functions, upper); + if (number >= bfun->insn_offset + ftrace_call_num_insn (bfun)) return 0; + /* We assume that there are no holes in the numbering. */ + for (;;) + { + const unsigned int average = lower + (upper - lower) / 2; + + bfun = VEC_index (btrace_fun_p, btinfo->functions, average); + + if (number < bfun->insn_offset) + { + upper = average - 1; + continue; + } + + if (number >= bfun->insn_offset + ftrace_call_num_insn (bfun)) + { + lower = average + 1; + continue; + } + + break; + } + it->function = bfun; it->index = number - bfun->insn_offset; - return 1; } diff --git a/gdb/btrace.h b/gdb/btrace.h index 1c0b6b3..07ed10c 100644 --- a/gdb/btrace.h +++ b/gdb/btrace.h @@ -187,6 +187,9 @@ struct btrace_function btrace_function_flags flags; }; +typedef struct btrace_function *btrace_fun_p; +DEF_VEC_P (btrace_fun_p); + /* A branch trace instruction iterator. */ struct btrace_insn_iterator { @@ -337,6 +340,10 @@ struct btrace_thread_info struct btrace_function *begin; struct btrace_function *end; + /* Vector of pointer to decoded function segments. These are in execution + order with the first element == BEGIN and the last element == END. */ + VEC (btrace_fun_p) *functions; + /* The function level offset. When added to each function's LEVEL, this normalizes the function levels such that the smallest level becomes zero. */ -- 2.7.4