From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 44584 invoked by alias); 30 Nov 2016 23:43:50 -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 44575 invoked by uid 89); 30 Nov 2016 23:43:50 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-4.6 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_NONE,RP_MATCHES_RCVD,SPF_PASS autolearn=ham version=3.3.2 spammy=insufficient, H*M:sk:f403045, H*MI:sk:f403045, BEGIN X-HELO: mail-pf0-f202.google.com Received: from mail-pf0-f202.google.com (HELO mail-pf0-f202.google.com) (209.85.192.202) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 30 Nov 2016 23:43:39 +0000 Received: by mail-pf0-f202.google.com with SMTP id i88so7816701pfk.0 for ; Wed, 30 Nov 2016 15:43:39 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:message-id:date:subject:from:to:cc; bh=/SF7/Hvve3g7poN7FcXUTMtaAuymNaBLQ5Yl3pdUaDE=; b=l6uf/l9TTCtjl4F3mWgsSLSPxcSkXahKJhegU+PTDZABV0EyaRK51c3eUzTG3ZHZto +phUMg+jD/FEXtG1JGccohnBep6AAYXs6HqmR/UbKXTvf4K3N3I2Yvqm4V07m06bUB1U kTQCcuFyMpLb0ySDQ7zAgldJyH6WDy4TvPKwGJPmmPH3woBJ7UBWOVCQTeM51DyU4KmJ NS3wPm6OmlBC4eLHupDiI8IkjJTCYYf1Ckn5Ou5IE1mtvVMMJL1dgVeysuq78Iv2QFGI Jcnpqk4X1LnYy1liWX7+bSAQvSjGlVe0XpPg8ZFpC9oBazaMEcmjRlcMJ054DUgo7nqi ii8Q== X-Gm-Message-State: AKaTC01xlt6rBKfNed9Mz5Pkv+fEvcVQYrKy/NPky1abEzq3PLBnDjNHBbvjRBsbP+0QLkwA8A== MIME-Version: 1.0 X-Received: by 10.99.149.88 with SMTP id t24mr18403934pgn.93.1480549418348; Wed, 30 Nov 2016 15:43:38 -0800 (PST) Message-ID: Date: Wed, 30 Nov 2016 23:43:00 -0000 Subject: Re: [PATCH v3 3/8] btrace: Use binary search to find instruction. From: Doug Evans To: Tim Wiederhake Cc: gdb-patches@sourceware.org, palves@redhat.com, markus.t.metzger@intel.com Content-Type: text/plain; charset=UTF-8; format=flowed; delsp=yes X-IsSubscribed: yes X-SW-Source: 2016-11/txt/msg01036.txt.bz2 Tim Wiederhake writes: > 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. > > 2016-11-21 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 | 39 +++++++++++++++++++++++++++++++++------ > gdb/btrace.h | 7 +++++++ > 2 files changed, 40 insertions(+), 6 deletions(-) > > diff --git a/gdb/btrace.c b/gdb/btrace.c > index ac7d46e..c878407 100644 > --- a/gdb/btrace.c > +++ b/gdb/btrace.c > @@ -1810,6 +1810,8 @@ 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); > @@ -1817,6 +1819,11 @@ btrace_fetch (struct thread_info *tp) > > btrace_clear_history (btinfo); > btrace_compute_ftrace (tp, &btrace); > + > + VEC_truncate (btrace_fun_p, btinfo->functions, 0); > + > + for (bfun = btinfo->begin; bfun != NULL; bfun = bfun->flow.next) > + VEC_safe_push (btrace_fun_p, btinfo->functions, bfun); > } > > do_cleanups (cleanup); > @@ -1839,6 +1846,8 @@ btrace_clear (struct thread_info *tp) > > btinfo = &tp->btrace; > > + VEC_free (btrace_fun_p, btinfo->functions); > + > it = btinfo->begin; > while (it != NULL) > { > @@ -2429,20 +2438,38 @@ btrace_find_insn_by_number (struct btrace_insn_iterator *it, > unsigned int number) > { > const struct btrace_function *bfun; > + unsigned int upper, lower, average; > > - 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; > > + average = lower + (upper - lower) / 2; > + bfun = VEC_index (btrace_fun_p, btinfo->functions, average); > + > + while ((number >= bfun->insn_offset + ftrace_call_num_insn (bfun)) > + || (number < bfun->insn_offset)) > + { > + if (number < bfun->insn_offset) > + upper = average - 1; > + else > + lower = average + 1; > + > + average = lower + (upper - lower) / 2; > + bfun = VEC_index (btrace_fun_p, btinfo->functions, average); > + } It's a bit hard to reason about the correctness of this loop for all edge conditions, but maybe it's just insufficient familiarity with bfun. Ok to leave as is, just thinking out loud. > + > it->function = bfun; > it->index = number - bfun->insn_offset; > - > return 1; > } > > diff --git a/gdb/btrace.h b/gdb/btrace.h > index d0497b4..6de2307 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 > LGTM otherwise. [with same proviso regarding others comments]