Re: [PATCH v3 3/8] btrace: Use binary search to find instruction.

Re: [PATCH v3 3/8] btrace: Use binary search to find instruction.

[Doug Evans]

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  <tim.wiederhake@intel.com>
  >
  > 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) <functions>: 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]

[PATCH v3 0/8] Python bindings for btrace recordings

[Tim Wiederhake]

This patch series adds Python bindings for btrace recordings.

V1 of this series can be found here:
https://sourceware.org/ml/gdb-patches/2016-10/msg00733.html

V2 of this series can be found here:
https://sourceware.org/ml/gdb-patches/2016-11/msg00084.html

Changes in V3:
- Rebased to current master.
- Replaced some strncmp with strcmp in patch 4 ("Add record_start function").
- Incorporated Eli's feedback regarding the documentation part.

Tim Wiederhake (8):
  btrace: Count gaps as one instruction explicitly.
  btrace: Export btrace_decode_error function.
  btrace: Use binary search to find instruction.
  Add record_start function.
  python: Create Python bindings for record history.
  python: Implement btrace Python bindings for record history.
  python: Add tests for record Python bindings
  Add documentation for new instruction record Python bindings.

 gdb/Makefile.in                               |   4 +
 gdb/NEWS                                      |   4 +
 gdb/btrace.c                                  | 163 +++--
 gdb/btrace.h                                  |  21 +-
 gdb/doc/python.texi                           | 237 ++++++
 gdb/python/py-btrace.c                        | 994 ++++++++++++++++++++++++++
 gdb/python/py-btrace.h                        |  32 +
 gdb/python/py-record.c                        | 257 +++++++
 gdb/python/py-record.h                        |  57 ++
 gdb/python/python-internal.h                  |   7 +
 gdb/python/python.c                           |  14 +
 gdb/record-btrace.c                           | 131 ++--
 gdb/record-full.c                             |  20 +
 gdb/record.c                                  |  28 +
 gdb/record.h                                  |   5 +
 gdb/target-debug.h                            |   2 +
 gdb/target-delegates.c                        |  33 +
 gdb/target.c                                  |   7 +
 gdb/target.h                                  |  10 +
 gdb/testsuite/gdb.python/py-record-btrace.c   |  48 ++
 gdb/testsuite/gdb.python/py-record-btrace.exp | 160 +++++
 21 files changed, 2096 insertions(+), 138 deletions(-)
 create mode 100644 gdb/python/py-btrace.c
 create mode 100644 gdb/python/py-btrace.h
 create mode 100644 gdb/python/py-record.c
 create mode 100644 gdb/python/py-record.h
 create mode 100644 gdb/testsuite/gdb.python/py-record-btrace.c
 create mode 100644 gdb/testsuite/gdb.python/py-record-btrace.exp

-- 
2.7.4

[PATCH v3 3/8] btrace: Use binary search to find instruction.

[Tim Wiederhake]

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  <tim.wiederhake@intel.com>

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) <functions>: 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->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

RE: [PATCH v3 3/8] btrace: Use binary search to find instruction.

[Metzger, Markus T]

> -----Original Message-----
> From: Wiederhake, Tim
> Sent: Monday, November 21, 2016 4:49 PM
> To: gdb-patches@sourceware.org
> Cc: palves@redhat.com; Metzger, Markus T <markus.t.metzger@intel.com>
> Subject: [PATCH v3 3/8] btrace: Use binary search to find instruction.
> 
> 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  <tim.wiederhake@intel.com>
> 
> 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) <functions>: New field.


> -  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->function = bfun;
>    it->index = number - bfun->insn_offset;

This could be simplified a bit.  Instead of checking the very small (i.e. zero
in practice) and very big numbers upfront, we can let them fall through the
binary search loop - both cases are unlikely.

Also the loop could be simplified by merging the termination check and the
check in the loop body so we end up with only one of the checks for low
numbers.

The algorithm looks good, however, and IIUC we're going to change that
again with an in-progress patch series.  So we might as well leave it as-is
and consider this in the final version.


Looks good to me.

Thanks,
Markus.

Intel Deutschland GmbH
Registered Address: Am Campeon 10-12, 85579 Neubiberg, Germany
Tel: +49 89 99 8853-0, www.intel.de
Managing Directors: Christin Eisenschmid, Christian Lamprechter
Chairperson of the Supervisory Board: Nicole Lau
Registered Office: Munich
Commercial Register: Amtsgericht Muenchen HRB 186928