[patch] Convert frame_stash to a hash table

[patch] Convert frame_stash to a hash table

[Phil Muldoon]

One of the things I have noticed with frame filters is a significant
penalty when printing backtraces.  This is because the frame filters
invalidate the frame_stash.  The reason for this is as follows.

Python frames do not store the GDB frame, nor should they.  If they
did, every time the frame cache is invalidated the Python object would
be pointing to the memory freed by the invalidated frame.  What Python
frames do store is the frame_id.  This is permanent, and allows Python
to fetch the frame on demand.

This on-demand nature is facilitated by a macro in the Python code:

FRAPY_REQUIRE_VALID

which fetches the frame with

frame_find_by_id.

All Python frame functions call this macro, and thus, all Python frame
functions end up using frame_find_by_id before each operation.  That's
fine until you consider that Python frames almost act like a random
access method of fetching frames, and the existing frame_stash being a
single entry stash cannot cope with this.

On single or occasional frame access this is fine and not noticeable.
But on large numbers of sustained frame accesses, like in backtrace,
this performance penalty of searching the frame cache (because the
frame_stash has been invalidated) mounts up and causes a significant
penalty.  Here are some tests from the existing code in GDB:

Test case is 20,000 frames printed in a backtrace.

Before patch, no frame filters.

real	0m3.081s
user	0m1.745s
sys	0m0.435s

Before patch, with frame filters.

real	4m16.094s
user	3m42.718s
sys	0m30.561s

As you can see there is a considerable performance penalty.  With the
patch that converts frame_stash to a hash table, these are the
numbers:

After patch, no frame filters

real	0m3.089s
user	0m1.765s
sys	0m0.414s

After patch, with frame filters

real	0m3.867s
user	0m3.296s
sys	0m0.414s

As you can see, the performance penalty is removed.  The "no frame
filters" timings after the patch do appear to be slightly larger, but,
using "time" is not very deterministic on such small numbers.  I
largely think we can ignore the difference with "no frame filters"
before and after the patch.  However "with frame filters" shows a
massive improvement.

Here are some gprof images that show the profiling statistics of "with
frame filters" before and after the patch:

Before patch:

http://picobot.org/withoutpatch_filters.png

After patch:

http://picobot.org/withpatch_filters.png

(These are large images)

The numbers in the brackets in each box are the important ones to look
at.  Without the patch, GDB spends a large amount of time in
get_prev_frame, which indicates constant hitting of the frame cache.

I think this patch improves the frame_stash "with filters" without 
affecting "no filters" performance.

Tested on x8664 with no regressions.

What do you think?

Cheers,

Phil


2013-05-16  Phil Muldoon  <pmuldoon@redhat.com>

	* frame.c (frame_stash): Convert to htab.
	(frame_addr_hash): New function.
	(frame_addr_hash_eq): New function.
	(frame_stash_create): Convert function to create
	a hash table.
	(frame_stash_add): Convert function to add an entry to a hash
	table.
	(frame_stash_find): Convert function to search the hash table.
	(frame_stash_invalidate): Convert function to empty the hash
	table.
	(get_frame_id): Only add to stash if a frame_id is created.
	(_initialize_frame): Call frame_stash_create.


--
	
Index: frame.c
===================================================================
RCS file: /cvs/src/src/gdb/frame.c,v
retrieving revision 1.317
diff -u -r1.317 frame.c
--- frame.c	10 Apr 2013 15:11:11 -0000	1.317
+++ frame.c	16 May 2013 12:57:05 -0000
@@ -43,6 +43,7 @@
 #include "block.h"
 #include "inline-frame.h"
 #include "tracepoint.h"
+#include "hashtab.h"
 
 static struct frame_info *get_prev_frame_1 (struct frame_info *this_frame);
 static struct frame_info *get_prev_frame_raw (struct frame_info *this_frame);
@@ -128,38 +129,101 @@
   enum unwind_stop_reason stop_reason;
 };
 
-/* A frame stash used to speed up frame lookups.  */
+/* A frame stash used to speed up frame lookups.  Create a hash table
+   to stash frames previously accessed from the frame cache for
+   quicker subsequent retrieval.  The hash table is emptied whenever
+   the frame cache is invalidated.  */
+static htab_t frame_stash;
+
+/* Internal function to calculate a hash from the frame_id addresses,
+   using as many valid addresses as possible.  Frames below level 0
+   are not stored in the hash table.  */
+static hashval_t
+frame_addr_hash (const void *ap)
+{
+  const struct frame_info *frame = ap;
+  const struct frame_id f_id = frame->this_id.value;
+  hashval_t hash = 0;
+
+  if (! f_id.stack_addr_p && ! f_id.code_addr_p && ! f_id.special_addr)
+    gdb_assert ("Cannot calculate hash for frame_id.");
+
+  if (f_id.stack_addr_p == 1)
+    hash = iterative_hash (&f_id.stack_addr,
+			   sizeof (f_id.stack_addr), hash);
+  if (f_id.code_addr_p == 1)
+    hash =  iterative_hash (&f_id.code_addr,
+			   sizeof (f_id.code_addr), hash);
+  if (f_id.special_addr_p == 1)
+    hash = iterative_hash (&f_id.special_addr,
+			   sizeof (f_id.special_addr), hash);
 
-/* We currently only stash one frame at a time, as this seems to be
-   sufficient for now.  */
-static struct frame_info *frame_stash = NULL;
+  return hash;
+}
 
-/* Add the following FRAME to the frame stash.  */
+/* Internal equality function for the hash table.  This function
+   defers equality operations to frame_id_eq.  */
+static int
+frame_addr_hash_eq (const void *a, const void *b)
+{
+  const struct frame_info *f_entry = a;
+  const struct frame_info *f_element = b;
+
+  return frame_id_eq (f_entry->this_id.value,
+		      f_element->this_id.value);
+}
 
+/* Internal function to create the frame_stash hash table.  100 seems
+   to be a good compromise to start the hash table at.  */
 static void
-frame_stash_add (struct frame_info *frame)
+frame_stash_create (void)
 {
-  frame_stash = frame;
+  frame_stash = htab_create (100,
+			     frame_addr_hash,
+			     frame_addr_hash_eq,
+			     NULL);
 }
 
-/* Search the frame stash for an entry with the given frame ID.
-   If found, return that frame.  Otherwise return NULL.  */
+/* Internal function to add a frame to the frame_stash hash table.  Do
+   not store frames below 0 as they may not have any addresses to
+   calculate a hash.  */
+static void
+frame_stash_add (struct frame_info *frame)
+{
+  /* Do not stash frames below level 0.  */
+  if (frame->level >= 0)
+    {
+      struct frame_info **slot;
+
+      slot = (struct frame_info **) htab_find_slot (frame_stash,
+						    frame,
+						    INSERT);
+      if (*slot != frame)
+	*slot = frame;
+    }
+}
 
+/* Internal function to search the frame stash for an entry with the
+   given frame ID.  If found, return that frame.  Otherwise return
+   NULL.  */
 static struct frame_info *
 frame_stash_find (struct frame_id id)
 {
-  if (frame_stash && frame_id_eq (frame_stash->this_id.value, id))
-    return frame_stash;
+  struct frame_info dummy;
+  struct frame_info *frame;
 
-  return NULL;
+  dummy.this_id.value = id;
+  frame = htab_find (frame_stash, &dummy);
+  return frame;
 }
 
-/* Invalidate the frame stash by removing all entries in it.  */
-
+/* Internal function to invalidate the frame stash by removing all
+   entries in it.  This only occurs when the frame cache is
+   invalidated.  */
 static void
 frame_stash_invalidate (void)
 {
-  frame_stash = NULL;
+  htab_empty (frame_stash);
 }
 
 /* Flag to control debugging.  */
@@ -345,10 +409,9 @@
 	  fprint_frame_id (gdb_stdlog, fi->this_id.value);
 	  fprintf_unfiltered (gdb_stdlog, " }\n");
 	}
+      frame_stash_add (fi);
     }
 
-  frame_stash_add (fi);
-
   return fi->this_id.value;
 }
 
@@ -2451,6 +2514,8 @@
 {
   obstack_init (&frame_cache_obstack);
 
+  frame_stash_create ();
+
   observer_attach_target_changed (frame_observer_target_changed);
 
   add_prefix_cmd ("backtrace", class_maintenance, set_backtrace_cmd, _("\
--

	

Re: [patch] Convert frame_stash to a hash table

[Tom Tromey]

>>>>> "Phil" == Phil Muldoon <pmuldoon@redhat.com> writes:

Phil> I think this patch improves the frame_stash "with filters" without 
Phil> affecting "no filters" performance.

Phil> Tested on x8664 with no regressions.

Phil> What do you think?

Thanks, Phil.  I appreciate this.

A few nits below.

Phil> +/* A frame stash used to speed up frame lookups.  Create a hash table
Phil> +   to stash frames previously accessed from the frame cache for
Phil> +   quicker subsequent retrieval.  The hash table is emptied whenever
Phil> +   the frame cache is invalidated.  */
Phil> +static htab_t frame_stash;

We use a blank line between the intro comment and the definition now.
This applies elsewhere.

Phil> +  if (! f_id.stack_addr_p && ! f_id.code_addr_p && ! f_id.special_addr)
Phil> +    gdb_assert ("Cannot calculate hash for frame_id.");

This assert will never fail, since its argument is true.
You want:

gdb_assert (f_id.stack_addr_p || f_id.code_addr_p || f_id.special_addr_p);

Also note the missing "_p" from special_addr_p in the patch.

Phil> +  if (f_id.stack_addr_p == 1)

These are booleans so don't compare against 1.

Phil> +      slot = (struct frame_info **) htab_find_slot (frame_stash,
Phil> +						    frame,
Phil> +						    INSERT);
Phil> +      if (*slot != frame)
Phil> +	*slot = frame;

I think you might as well assign unconditionally.
Otherwise I think readers will wonder when this can happen.
But, I think it can't happen.
Alternatively, if it can happen, then we need a comment.

thanks,
Tom

Re: [patch] Convert frame_stash to a hash table

[Pedro Alves]

On 05/16/2013 02:09 PM, Phil Muldoon wrote:
> 
> One of the things I have noticed with frame filters is a significant
> penalty when printing backtraces.  This is because the frame filters
> invalidate the frame_stash.  The reason for this is as follows.
> 
> Python frames do not store the GDB frame, nor should they.  If they
> did, every time the frame cache is invalidated the Python object would
> be pointing to the memory freed by the invalidated frame.  What Python
> frames do store is the frame_id.  This is permanent, and allows Python
> to fetch the frame on demand.
> 
> This on-demand nature is facilitated by a macro in the Python code:
> 
> FRAPY_REQUIRE_VALID
> 
> which fetches the frame with
> 
> frame_find_by_id.
> 
> All Python frame functions call this macro, and thus, all Python frame
> functions end up using frame_find_by_id before each operation.  That's
> fine until you consider that Python frames almost act like a random
> access method of fetching frames, and the existing frame_stash being a
> single entry stash cannot cope with this.
> 
> On single or occasional frame access this is fine and not noticeable.
> But on large numbers of sustained frame accesses, like in backtrace,
> this performance penalty of searching the frame cache (because the
> frame_stash has been invalidated) mounts up and causes a significant
> penalty.  Here are some tests from the existing code in GDB:

I don't think this is the complete picture, particularly the backtrace
case.  I'll try to sum it, based on what I recall from a previous
discussion.  Please correct me if I am wrong.

When doing a backtrace, you'll end up linearly walking the frame
chain, and normally you don't go back to newer frames -- unwind a
frame (frame.prev()), print info about it, unwind the next, print it,
on and on.  As such, a single frame stashed in the frame stash should be
sufficient.  But it's not.  frapy_older does:

  TRY_CATCH (except, RETURN_MASK_ALL)
    {
      FRAPY_REQUIRE_VALID (self, frame);

      prev = get_prev_frame (frame);
      if (prev)
	prev_obj = (PyObject *) frame_info_to_frame_object (prev);
      else

The frame_find_by_id call in FRAPY_REQUIRE_VALID should be hitting
the frame stashed in the frame stash, as it's still the last frame
we printed.  The problem is actually in frame_info_to_frame_object
(called above), which does:

  TRY_CATCH (except, RETURN_MASK_ALL)
    {

      /* Try to get the previous frame, to determine if this is the last frame
	 in a corrupt stack.  If so, we need to store the frame_id of the next
	 frame and not of this one (which is possibly invalid).  */
      if (get_prev_frame (frame) == NULL
	  && get_frame_unwind_stop_reason (frame) != UNWIND_NO_REASON
	  && get_next_frame (frame) != NULL)
	{
	  frame_obj->frame_id = get_frame_id (get_next_frame (frame));
	  frame_obj->frame_id_is_next = 1;
	}

and given the present frame stash can only hold one frame,
these get_prev_frame/get_next_frame calls constantly invalidate it.

Now, I don't get this "detect corrupt stack" code at all.  It raises
a lot of alarm bells to me.  All frames in the frame chain have an unique
(for a given stopped thread) id.  I don't get the reference to an
invalid frame id.  What's that?  null_frame_id?  I'd call it a bug if any
unwinder is returning that.  Outermost frames use outer_frame_id, which
is valid (outer_frame_id actually should die, but that's another story).
The original submission of this code doesn't seem to explain this.

To be clear, I'm not against the hash stash idea at all.  It's likely to
speed up use cases, even if frame_info_to_frame_object was changed
to not do that dance.

-- 
Pedro Alves

Re: [patch] Convert frame_stash to a hash table

[Phil Muldoon]

On 16/05/13 14:42, Pedro Alves wrote:
> On 05/16/2013 02:09 PM, Phil Muldoon wrote:
> 
> When doing a backtrace, you'll end up linearly walking the frame
> chain, and normally you don't go back to newer frames -- unwind a
> frame (frame.prev()), print info about it, unwind the next, print it,
> on and on.  As such, a single frame stashed in the frame stash should be
> sufficient.  But it's not.  frapy_older does:

When using frame filters, in the case of eliding frames this may not
be the case.  In fact we cannot predict how frame filters will
navigate the stack.

 
>   TRY_CATCH (except, RETURN_MASK_ALL)
>     {
> 
>       /* Try to get the previous frame, to determine if this is the last frame
> 	 in a corrupt stack.  If so, we need to store the frame_id of the next
> 	 frame and not of this one (which is possibly invalid).  */
>       if (get_prev_frame (frame) == NULL
> 	  && get_frame_unwind_stop_reason (frame) != UNWIND_NO_REASON
> 	  && get_next_frame (frame) != NULL)
> 	{
> 	  frame_obj->frame_id = get_frame_id (get_next_frame (frame));
> 	  frame_obj->frame_id_is_next = 1;
> 	}


Yes, this is bogus.  But even if you remove this, the performance hits
still register as significant.

> and given the present frame stash can only hold one frame,
> these get_prev_frame/get_next_frame calls constantly invalidate it. 
> Now, I don't get this "detect corrupt stack" code at all.

Me either, it should be removed.  Hiding the corrupt stack from a
Python consumer seems all kinds of wrong.  I am going to fix this
next.  I decided not to include it in this patch, as I wanted the
focus to be on frame_stash issues where Python scripts can randomly
access frame from all over the stack.

Take this example

f = gdb.newest_frame()

do some other inferior operations happen, stop.

g = gdb.newest_frame()

Now is I access f, say f.type(), that will not be in the frame_stash,
it was from awhile ago.  These kinds of patterns do crop up in frame
filters, because we are filtering, eliding frames.


> To be clear, I'm not against the hash stash idea at all.  It's likely to
> speed up use cases, even if frame_info_to_frame_object was changed
> to not do that dance.

It will be changed, very soon.

Thanks for the comments,

Cheers

Phil

Re: [patch] Convert frame_stash to a hash table

[Phil Muldoon]

On 16/05/13 14:42, Tom Tromey wrote:
>>>>>> "Phil" == Phil Muldoon <pmuldoon@redhat.com> writes:
> 
> Phil> I think this patch improves the frame_stash "with filters" without 
> Phil> affecting "no filters" performance.
> 
> Phil> Tested on x8664 with no regressions.
> 
> Phil> What do you think?
> 
> Thanks, Phil.  I appreciate this.
> 
> A few nits below.

I have fixed up the changes, patch attached.

Cheers,

Phil

--

Index: frame.c
===================================================================
RCS file: /cvs/src/src/gdb/frame.c,v
retrieving revision 1.317
diff -u -r1.317 frame.c
--- frame.c	10 Apr 2013 15:11:11 -0000	1.317
+++ frame.c	16 May 2013 14:08:03 -0000
@@ -43,6 +43,7 @@
 #include "block.h"
 #include "inline-frame.h"
 #include "tracepoint.h"
+#include "hashtab.h"
 
 static struct frame_info *get_prev_frame_1 (struct frame_info *this_frame);
 static struct frame_info *get_prev_frame_raw (struct frame_info *this_frame);
@@ -128,38 +129,107 @@
   enum unwind_stop_reason stop_reason;
 };
 
-/* A frame stash used to speed up frame lookups.  */
+/* A frame stash used to speed up frame lookups.  Create a hash table
+   to stash frames previously accessed from the frame cache for
+   quicker subsequent retrieval.  The hash table is emptied whenever
+   the frame cache is invalidated.  */
+
+static htab_t frame_stash;
+
+/* Internal function to calculate a hash from the frame_id addresses,
+   using as many valid addresses as possible.  Frames below level 0
+   are not stored in the hash table.  */
+
+static hashval_t
+frame_addr_hash (const void *ap)
+{
+  const struct frame_info *frame = ap;
+  const struct frame_id f_id = frame->this_id.value;
+  hashval_t hash = 0;
+
+  if (! f_id.stack_addr_p || ! f_id.code_addr_p || ! f_id.special_addr_p)
+    gdb_assert ("Cannot calculate hash for frame_id.");
+
+  if (f_id.stack_addr_p)
+    hash = iterative_hash (&f_id.stack_addr,
+			   sizeof (f_id.stack_addr), hash);
+  if (f_id.code_addr_p)
+    hash = iterative_hash (&f_id.code_addr,
+			   sizeof (f_id.code_addr), hash);
+  if (f_id.special_addr_p)
+    hash = iterative_hash (&f_id.special_addr,
+			   sizeof (f_id.special_addr), hash);
 
-/* We currently only stash one frame at a time, as this seems to be
-   sufficient for now.  */
-static struct frame_info *frame_stash = NULL;
+  return hash;
+}
+
+/* Internal equality function for the hash table.  This function
+   defers equality operations to frame_id_eq.  */
+
+static int
+frame_addr_hash_eq (const void *a, const void *b)
+{
+  const struct frame_info *f_entry = a;
+  const struct frame_info *f_element = b;
 
-/* Add the following FRAME to the frame stash.  */
+  return frame_id_eq (f_entry->this_id.value,
+		      f_element->this_id.value);
+}
+
+/* Internal function to create the frame_stash hash table.  100 seems
+   to be a good compromise to start the hash table at.  */
+
+static void
+frame_stash_create (void)
+{
+  frame_stash = htab_create (100,
+			     frame_addr_hash,
+			     frame_addr_hash_eq,
+			     NULL);
+}
+
+/* Internal function to add a frame to the frame_stash hash table.  Do
+   not store frames below 0 as they may not have any addresses to
+   calculate a hash.  */
 
 static void
 frame_stash_add (struct frame_info *frame)
 {
-  frame_stash = frame;
+  /* Do not stash frames below level 0.  */
+  if (frame->level >= 0)
+    {
+      struct frame_info **slot;
+
+      slot = (struct frame_info **) htab_find_slot (frame_stash,
+						    frame,
+						    INSERT);
+      *slot = frame;
+    }
 }
 
-/* Search the frame stash for an entry with the given frame ID.
-   If found, return that frame.  Otherwise return NULL.  */
+/* Internal function to search the frame stash for an entry with the
+   given frame ID.  If found, return that frame.  Otherwise return
+   NULL.  */
 
 static struct frame_info *
 frame_stash_find (struct frame_id id)
 {
-  if (frame_stash && frame_id_eq (frame_stash->this_id.value, id))
-    return frame_stash;
+  struct frame_info dummy;
+  struct frame_info *frame;
 
-  return NULL;
+  dummy.this_id.value = id;
+  frame = htab_find (frame_stash, &dummy);
+  return frame;
 }
 
-/* Invalidate the frame stash by removing all entries in it.  */
+/* Internal function to invalidate the frame stash by removing all
+   entries in it.  This only occurs when the frame cache is
+   invalidated.  */
 
 static void
 frame_stash_invalidate (void)
 {
-  frame_stash = NULL;
+  htab_empty (frame_stash);
 }
 
 /* Flag to control debugging.  */
@@ -345,10 +415,9 @@
 	  fprint_frame_id (gdb_stdlog, fi->this_id.value);
 	  fprintf_unfiltered (gdb_stdlog, " }\n");
 	}
+      frame_stash_add (fi);
     }
 
-  frame_stash_add (fi);
-
   return fi->this_id.value;
 }
 
@@ -2451,6 +2520,8 @@
 {
   obstack_init (&frame_cache_obstack);
 
+  frame_stash_create ();
+
   observer_attach_target_changed (frame_observer_target_changed);
 
   add_prefix_cmd ("backtrace", class_maintenance, set_backtrace_cmd, _("\

Re: [patch] Convert frame_stash to a hash table

[Pedro Alves]

On 05/16/2013 02:50 PM, Phil Muldoon wrote:
> On 16/05/13 14:42, Pedro Alves wrote:
>> On 05/16/2013 02:09 PM, Phil Muldoon wrote:
>>
>> When doing a backtrace, you'll end up linearly walking the frame
>> chain, and normally you don't go back to newer frames -- unwind a
>> frame (frame.prev()), print info about it, unwind the next, print it,
>> on and on.  As such, a single frame stashed in the frame stash should be
>> sufficient.  But it's not.  frapy_older does:
> 
> When using frame filters, in the case of eliding frames this may not
> be the case.  In fact we cannot predict how frame filters will
> navigate the stack.

For sure.  However, I think in your backtrace example, the frame
filter actually did nothing, correct?

> 
>  
>>   TRY_CATCH (except, RETURN_MASK_ALL)
>>     {
>>
>>       /* Try to get the previous frame, to determine if this is the last frame
>> 	 in a corrupt stack.  If so, we need to store the frame_id of the next
>> 	 frame and not of this one (which is possibly invalid).  */
>>       if (get_prev_frame (frame) == NULL
>> 	  && get_frame_unwind_stop_reason (frame) != UNWIND_NO_REASON
>> 	  && get_next_frame (frame) != NULL)
>> 	{
>> 	  frame_obj->frame_id = get_frame_id (get_next_frame (frame));
>> 	  frame_obj->frame_id_is_next = 1;
>> 	}
> 
> 
> Yes, this is bogus.  But even if you remove this, the performance hits
> still register as significant.

I'd expected that a simple filter (like I imagine yours was)
you'd not see any performance hit.

> 
>> and given the present frame stash can only hold one frame,
>> these get_prev_frame/get_next_frame calls constantly invalidate it. 
>> Now, I don't get this "detect corrupt stack" code at all.
> 
> Me either, it should be removed.  Hiding the corrupt stack from a
> Python consumer seems all kinds of wrong.  I am going to fix this
> next.  I decided not to include it in this patch, as I wanted the
> focus to be on frame_stash issues where Python scripts can randomly
> access frame from all over the stack.

OK.  Again, I'm not questioning the merit of the patch, but the
example/rationale.  :-)  Personally, I'd rather that was fixed first,
and then the new frame hash stash justified/explained with
with an example where gdb's inefficiencies are exposed even when
gdb's python code is sane.  :-)

> Take this example
> 
> f = gdb.newest_frame()
> 
> do some other inferior operations happen, stop.
> 
> g = gdb.newest_frame()
> 
> Now is I access f, say f.type(), that will not be in the frame_stash,
> it was from awhile ago.  These kinds of patterns do crop up in frame
> filters, because we are filtering, eliding frames.

I'm confused.  :-)  If you do other inferior operations
that resume the inferior, then the new hash stash won't help either.
Resuming the inferior always invalidates all frames, along with the
stash.

-- 
Pedro Alves

Re: [patch] Convert frame_stash to a hash table

[Phil Muldoon]

On 16/05/13 15:23, Pedro Alves wrote:
> On 05/16/2013 02:50 PM, Phil Muldoon wrote:
>> On 16/05/13 14:42, Pedro Alves wrote:
>>> On 05/16/2013 02:09 PM, Phil Muldoon wrote:
>>>
>>> When doing a backtrace, you'll end up linearly walking the frame
>>> chain, and normally you don't go back to newer frames -- unwind a
>>> frame (frame.prev()), print info about it, unwind the next, print it,
>>> on and on.  As such, a single frame stashed in the frame stash should be
>>> sufficient.  But it's not.  frapy_older does:
>>
>> When using frame filters, in the case of eliding frames this may not
>> be the case.  In fact we cannot predict how frame filters will
>> navigate the stack.
> 
> For sure.  However, I think in your backtrace example, the frame
> filter actually did nothing, correct?

Nope, the frame filter did some operations on each frame function
name, and also elided frames.

>> Yes, this is bogus.  But even if you remove this, the performance hits
>> still register as significant.
> 
> I'd expected that a simple filter (like I imagine yours was)
> you'd not see any performance hit.

It did, but ...

>>> and given the present frame stash can only hold one frame,
>>> these get_prev_frame/get_next_frame calls constantly invalidate it. 
>>> Now, I don't get this "detect corrupt stack" code at all.
>>
>> Me either, it should be removed.  Hiding the corrupt stack from a
>> Python consumer seems all kinds of wrong.  I am going to fix this
>> next.  I decided not to include it in this patch, as I wanted the
>> focus to be on frame_stash issues where Python scripts can randomly
>> access frame from all over the stack.
> 
> OK.  Again, I'm not questioning the merit of the patch, but the
> example/rationale.  :-)  Personally, I'd rather that was fixed first,
> and then the new frame hash stash justified/explained with
> with an example where gdb's inefficiencies are exposed even when
> gdb's python code is sane.  :-)

I'll fix this and rerun the performance tests.

>> f = gdb.newest_frame()
>>
>> do some other inferior operations happen, stop.
>>
>> g = gdb.newest_frame()
>>
>> Now is I access f, say f.type(), that will not be in the frame_stash,
>> it was from awhile ago.  These kinds of patterns do crop up in frame
>> filters, because we are filtering, eliding frames.
> 
> I'm confused.  :-)  If you do other inferior operations
> that resume the inferior, then the new hash stash won't help either.
> Resuming the inferior always invalidates all frames, along with the
> stash.

Yes my example was messed up, the second newest_frame should be some
other frame, and delete the whole line about inferior operations.

Cheers

Phil

Re: [patch] Convert frame_stash to a hash table

[Pedro Alves]

On 05/16/2013 03:27 PM, Phil Muldoon wrote:
> I'll fix this and rerun the performance tests.

Thanks.  Could you also post the filter script?  It be useful
to have it in the archives for posterity.

-- 
Pedro Alves

Re: [patch] Convert frame_stash to a hash table

[Phil Muldoon]

On 16/05/13 15:41, Pedro Alves wrote:
> On 05/16/2013 03:27 PM, Phil Muldoon wrote:
>> I'll fix this and rerun the performance tests.
> 
> Thanks.  Could you also post the filter script?  It be useful
> to have it in the archives for posterity.
> 

It is the one in the gdb.python/ testsuite, with the iterations
cranked up 20000.

gdb.python/py-framefilter.c with gdb.python/py-framefilter.py loaded

I can post it if you want, but the only change is the number of
iterations the recursive functions call each other.

Cheers,

Phil

Re: [patch] Convert frame_stash to a hash table

[Tom Tromey]

>>>>> "Phil" == Phil Muldoon <pmuldoon@redhat.com> writes:

Phil> +  if (! f_id.stack_addr_p || ! f_id.code_addr_p || ! f_id.special_addr_p)
Phil> +    gdb_assert ("Cannot calculate hash for frame_id.");

This is still incorrect.

Tom

Re: [patch] Convert frame_stash to a hash table

[Pedro Alves]

On 05/16/2013 03:23 PM, Pedro Alves wrote:

> I'd expected that a simple filter (like I imagine yours was)
> you'd not see any performance hit.

For the archives -- Phil and I spent a bit investigating tihs.
This expectation was just too naive.
The way the current frame stash is managed today (the last
frame get_frame_id is called on) lends itself to all sorts
of random places in the frame code where the stash happens
to flip to the wrong frame, or cases where we'd expect
the stash to be set but isn't (e.g., frapy_older
leaves without the stash set to the older frame).  This
is just too fragile for this use case.  Let's move on with the
new hash stash and be done with it.

Thanks,
-- 
Pedro Alves

Re: [patch] Convert frame_stash to a hash table

[Phil Muldoon]

On 16/05/13 19:16, Tom Tromey wrote:
>>>>>> "Phil" == Phil Muldoon <pmuldoon@redhat.com> writes:
> 
> Phil> +  if (! f_id.stack_addr_p || ! f_id.code_addr_p || ! f_id.special_addr_p)
> Phil> +    gdb_assert ("Cannot calculate hash for frame_id.");
> 
> This is still incorrect.

Apologies, not sure why I did that ;)

New patch attached

Cheers,

Phil

--

Index: frame.c
===================================================================
RCS file: /cvs/src/src/gdb/frame.c,v
retrieving revision 1.317
diff -u -r1.317 frame.c
--- frame.c	10 Apr 2013 15:11:11 -0000	1.317
+++ frame.c	16 May 2013 18:45:57 -0000
@@ -43,6 +43,7 @@
 #include "block.h"
 #include "inline-frame.h"
 #include "tracepoint.h"
+#include "hashtab.h"
 
 static struct frame_info *get_prev_frame_1 (struct frame_info *this_frame);
 static struct frame_info *get_prev_frame_raw (struct frame_info *this_frame);
@@ -128,38 +129,107 @@
   enum unwind_stop_reason stop_reason;
 };
 
-/* A frame stash used to speed up frame lookups.  */
+/* A frame stash used to speed up frame lookups.  Create a hash table
+   to stash frames previously accessed from the frame cache for
+   quicker subsequent retrieval.  The hash table is emptied whenever
+   the frame cache is invalidated.  */
+
+static htab_t frame_stash;
+
+/* Internal function to calculate a hash from the frame_id addresses,
+   using as many valid addresses as possible.  Frames below level 0
+   are not stored in the hash table.  */
+
+static hashval_t
+frame_addr_hash (const void *ap)
+{
+  const struct frame_info *frame = ap;
+  const struct frame_id f_id = frame->this_id.value;
+  hashval_t hash = 0;
+
+  gdb_assert (!f_id.stack_addr_p || !f_id.code_addr_p
+	      || !f_id.special_addr_p);
+
+  if (f_id.stack_addr_p)
+    hash = iterative_hash (&f_id.stack_addr,
+			   sizeof (f_id.stack_addr), hash);
+  if (f_id.code_addr_p)
+    hash = iterative_hash (&f_id.code_addr,
+			   sizeof (f_id.code_addr), hash);
+  if (f_id.special_addr_p)
+    hash = iterative_hash (&f_id.special_addr,
+			   sizeof (f_id.special_addr), hash);
 
-/* We currently only stash one frame at a time, as this seems to be
-   sufficient for now.  */
-static struct frame_info *frame_stash = NULL;
+  return hash;
+}
+
+/* Internal equality function for the hash table.  This function
+   defers equality operations to frame_id_eq.  */
+
+static int
+frame_addr_hash_eq (const void *a, const void *b)
+{
+  const struct frame_info *f_entry = a;
+  const struct frame_info *f_element = b;
 
-/* Add the following FRAME to the frame stash.  */
+  return frame_id_eq (f_entry->this_id.value,
+		      f_element->this_id.value);
+}
+
+/* Internal function to create the frame_stash hash table.  100 seems
+   to be a good compromise to start the hash table at.  */
+
+static void
+frame_stash_create (void)
+{
+  frame_stash = htab_create (100,
+			     frame_addr_hash,
+			     frame_addr_hash_eq,
+			     NULL);
+}
+
+/* Internal function to add a frame to the frame_stash hash table.  Do
+   not store frames below 0 as they may not have any addresses to
+   calculate a hash.  */
 
 static void
 frame_stash_add (struct frame_info *frame)
 {
-  frame_stash = frame;
+  /* Do not stash frames below level 0.  */
+  if (frame->level >= 0)
+    {
+      struct frame_info **slot;
+
+      slot = (struct frame_info **) htab_find_slot (frame_stash,
+						    frame,
+						    INSERT);
+      *slot = frame;
+    }
 }
 
-/* Search the frame stash for an entry with the given frame ID.
-   If found, return that frame.  Otherwise return NULL.  */
+/* Internal function to search the frame stash for an entry with the
+   given frame ID.  If found, return that frame.  Otherwise return
+   NULL.  */
 
 static struct frame_info *
 frame_stash_find (struct frame_id id)
 {
-  if (frame_stash && frame_id_eq (frame_stash->this_id.value, id))
-    return frame_stash;
+  struct frame_info dummy;
+  struct frame_info *frame;
 
-  return NULL;
+  dummy.this_id.value = id;
+  frame = htab_find (frame_stash, &dummy);
+  return frame;
 }
 
-/* Invalidate the frame stash by removing all entries in it.  */
+/* Internal function to invalidate the frame stash by removing all
+   entries in it.  This only occurs when the frame cache is
+   invalidated.  */
 
 static void
 frame_stash_invalidate (void)
 {
-  frame_stash = NULL;
+  htab_empty (frame_stash);
 }
 
 /* Flag to control debugging.  */
@@ -345,10 +415,9 @@
 	  fprint_frame_id (gdb_stdlog, fi->this_id.value);
 	  fprintf_unfiltered (gdb_stdlog, " }\n");
 	}
+      frame_stash_add (fi);
     }
 
-  frame_stash_add (fi);
-
   return fi->this_id.value;
 }
 
@@ -2451,6 +2520,8 @@
 {
   obstack_init (&frame_cache_obstack);
 
+  frame_stash_create ();
+
   observer_attach_target_changed (frame_observer_target_changed);
 
   add_prefix_cmd ("backtrace", class_maintenance, set_backtrace_cmd, _("\

Re: [patch] Convert frame_stash to a hash table

[Tom Tromey]

>>>>> "Phil" == Phil Muldoon <pmuldoon@redhat.com> writes:

Phil> +  gdb_assert (!f_id.stack_addr_p || !f_id.code_addr_p
Phil> +	      || !f_id.special_addr_p);

I think those "!"s should not be there.
You want to ensure that one of these is true.

Tom

Re: [patch] Convert frame_stash to a hash table

[Phil Muldoon]

On 16/05/13 20:07, Tom Tromey wrote:
>>>>>> "Phil" == Phil Muldoon <pmuldoon@redhat.com> writes:
> Phil> +  gdb_assert (!f_id.stack_addr_p || !f_id.code_addr_p
> Phil> +	      || !f_id.special_addr_p);
> 
> I think those "!"s should not be there.
> You want to ensure that one of these is true.
> 
> Tom

Today's not going to be my day.  Apologies, once again.  Patch
attached.

Cheers,

Phil

--

Index: frame.c
===================================================================
RCS file: /cvs/src/src/gdb/frame.c,v
retrieving revision 1.317
diff -u -r1.317 frame.c
--- frame.c	10 Apr 2013 15:11:11 -0000	1.317
+++ frame.c	16 May 2013 19:12:57 -0000
@@ -43,6 +43,7 @@
 #include "block.h"
 #include "inline-frame.h"
 #include "tracepoint.h"
+#include "hashtab.h"
 
 static struct frame_info *get_prev_frame_1 (struct frame_info *this_frame);
 static struct frame_info *get_prev_frame_raw (struct frame_info *this_frame);
@@ -128,38 +129,107 @@
   enum unwind_stop_reason stop_reason;
 };
 
-/* A frame stash used to speed up frame lookups.  */
+/* A frame stash used to speed up frame lookups.  Create a hash table
+   to stash frames previously accessed from the frame cache for
+   quicker subsequent retrieval.  The hash table is emptied whenever
+   the frame cache is invalidated.  */
+
+static htab_t frame_stash;
+
+/* Internal function to calculate a hash from the frame_id addresses,
+   using as many valid addresses as possible.  Frames below level 0
+   are not stored in the hash table.  */
+
+static hashval_t
+frame_addr_hash (const void *ap)
+{
+  const struct frame_info *frame = ap;
+  const struct frame_id f_id = frame->this_id.value;
+  hashval_t hash = 0;
+
+  gdb_assert (f_id.stack_addr_p || f_id.code_addr_p
+	      || f_id.special_addr_p);
+
+  if (f_id.stack_addr_p)
+    hash = iterative_hash (&f_id.stack_addr,
+			   sizeof (f_id.stack_addr), hash);
+  if (f_id.code_addr_p)
+    hash = iterative_hash (&f_id.code_addr,
+			   sizeof (f_id.code_addr), hash);
+  if (f_id.special_addr_p)
+    hash = iterative_hash (&f_id.special_addr,
+			   sizeof (f_id.special_addr), hash);
 
-/* We currently only stash one frame at a time, as this seems to be
-   sufficient for now.  */
-static struct frame_info *frame_stash = NULL;
+  return hash;
+}
+
+/* Internal equality function for the hash table.  This function
+   defers equality operations to frame_id_eq.  */
+
+static int
+frame_addr_hash_eq (const void *a, const void *b)
+{
+  const struct frame_info *f_entry = a;
+  const struct frame_info *f_element = b;
 
-/* Add the following FRAME to the frame stash.  */
+  return frame_id_eq (f_entry->this_id.value,
+		      f_element->this_id.value);
+}
+
+/* Internal function to create the frame_stash hash table.  100 seems
+   to be a good compromise to start the hash table at.  */
+
+static void
+frame_stash_create (void)
+{
+  frame_stash = htab_create (100,
+			     frame_addr_hash,
+			     frame_addr_hash_eq,
+			     NULL);
+}
+
+/* Internal function to add a frame to the frame_stash hash table.  Do
+   not store frames below 0 as they may not have any addresses to
+   calculate a hash.  */
 
 static void
 frame_stash_add (struct frame_info *frame)
 {
-  frame_stash = frame;
+  /* Do not stash frames below level 0.  */
+  if (frame->level >= 0)
+    {
+      struct frame_info **slot;
+
+      slot = (struct frame_info **) htab_find_slot (frame_stash,
+						    frame,
+						    INSERT);
+      *slot = frame;
+    }
 }
 
-/* Search the frame stash for an entry with the given frame ID.
-   If found, return that frame.  Otherwise return NULL.  */
+/* Internal function to search the frame stash for an entry with the
+   given frame ID.  If found, return that frame.  Otherwise return
+   NULL.  */
 
 static struct frame_info *
 frame_stash_find (struct frame_id id)
 {
-  if (frame_stash && frame_id_eq (frame_stash->this_id.value, id))
-    return frame_stash;
+  struct frame_info dummy;
+  struct frame_info *frame;
 
-  return NULL;
+  dummy.this_id.value = id;
+  frame = htab_find (frame_stash, &dummy);
+  return frame;
 }
 
-/* Invalidate the frame stash by removing all entries in it.  */
+/* Internal function to invalidate the frame stash by removing all
+   entries in it.  This only occurs when the frame cache is
+   invalidated.  */
 
 static void
 frame_stash_invalidate (void)
 {
-  frame_stash = NULL;
+  htab_empty (frame_stash);
 }
 
 /* Flag to control debugging.  */
@@ -345,10 +415,9 @@
 	  fprint_frame_id (gdb_stdlog, fi->this_id.value);
 	  fprintf_unfiltered (gdb_stdlog, " }\n");
 	}
+      frame_stash_add (fi);
     }
 
-  frame_stash_add (fi);
-
   return fi->this_id.value;
 }
 
@@ -2451,6 +2520,8 @@
 {
   obstack_init (&frame_cache_obstack);
 
+  frame_stash_create ();
+
   observer_attach_target_changed (frame_observer_target_changed);
 
   add_prefix_cmd ("backtrace", class_maintenance, set_backtrace_cmd, _("\

Re: [patch] Convert frame_stash to a hash table

[Tom Tromey]

>>>>> "Phil" == Phil Muldoon <pmuldoon@redhat.com> writes:

Phil> Today's not going to be my day.  Apologies, once again.  Patch
Phil> attached.

No problem :)
This one is ok.  Thanks!

Tom

Re: [patch] Convert frame_stash to a hash table

[Phil Muldoon]

On 16/05/13 21:23, Tom Tromey wrote:
>>>>>> "Phil" == Phil Muldoon <pmuldoon@redhat.com> writes:
> 
> Phil> Today's not going to be my day.  Apologies, once again.  Patch
> Phil> attached.
> 
> No problem :)
> This one is ok.  Thanks!

So committed as patch follows, thanks.

Cheers,

Phil

2013-05-17  Phil Muldoon  <pmuldoon@redhat.com>

	* frame.c (frame_stash): Convert to htab.
	(frame_addr_hash): New function.
	(frame_addr_hash_eq): New function.
	(frame_stash_create): Convert function to create
	a hash table.
	(frame_stash_add): Convert function to add an entry to a hash
	table.
	(frame_stash_find): Convert function to search the hash table.
	(frame_stash_invalidate): Convert function to empty the hash
	table.
	(get_frame_id): Only add to stash if a frame_id is created.
	(_initialize_frame): Call frame_stash_create.

--

Index: frame.c
===================================================================
RCS file: /cvs/src/src/gdb/frame.c,v
retrieving revision 1.317
retrieving revision 1.318
diff -u -r1.317 -r1.318
--- frame.c	10 Apr 2013 15:11:11 -0000	1.317
+++ frame.c	17 May 2013 08:34:18 -0000	1.318
@@ -43,6 +43,7 @@
 #include "block.h"
 #include "inline-frame.h"
 #include "tracepoint.h"
+#include "hashtab.h"
 
 static struct frame_info *get_prev_frame_1 (struct frame_info *this_frame);
 static struct frame_info *get_prev_frame_raw (struct frame_info *this_frame);
@@ -128,38 +129,107 @@
   enum unwind_stop_reason stop_reason;
 };
 
-/* A frame stash used to speed up frame lookups.  */
+/* A frame stash used to speed up frame lookups.  Create a hash table
+   to stash frames previously accessed from the frame cache for
+   quicker subsequent retrieval.  The hash table is emptied whenever
+   the frame cache is invalidated.  */
+
+static htab_t frame_stash;
+
+/* Internal function to calculate a hash from the frame_id addresses,
+   using as many valid addresses as possible.  Frames below level 0
+   are not stored in the hash table.  */
+
+static hashval_t
+frame_addr_hash (const void *ap)
+{
+  const struct frame_info *frame = ap;
+  const struct frame_id f_id = frame->this_id.value;
+  hashval_t hash = 0;
+
+  gdb_assert (f_id.stack_addr_p || f_id.code_addr_p
+	      || f_id.special_addr_p);
+
+  if (f_id.stack_addr_p)
+    hash = iterative_hash (&f_id.stack_addr,
+			   sizeof (f_id.stack_addr), hash);
+  if (f_id.code_addr_p)
+    hash = iterative_hash (&f_id.code_addr,
+			   sizeof (f_id.code_addr), hash);
+  if (f_id.special_addr_p)
+    hash = iterative_hash (&f_id.special_addr,
+			   sizeof (f_id.special_addr), hash);
 
-/* We currently only stash one frame at a time, as this seems to be
-   sufficient for now.  */
-static struct frame_info *frame_stash = NULL;
+  return hash;
+}
+
+/* Internal equality function for the hash table.  This function
+   defers equality operations to frame_id_eq.  */
+
+static int
+frame_addr_hash_eq (const void *a, const void *b)
+{
+  const struct frame_info *f_entry = a;
+  const struct frame_info *f_element = b;
 
-/* Add the following FRAME to the frame stash.  */
+  return frame_id_eq (f_entry->this_id.value,
+		      f_element->this_id.value);
+}
+
+/* Internal function to create the frame_stash hash table.  100 seems
+   to be a good compromise to start the hash table at.  */
+
+static void
+frame_stash_create (void)
+{
+  frame_stash = htab_create (100,
+			     frame_addr_hash,
+			     frame_addr_hash_eq,
+			     NULL);
+}
+
+/* Internal function to add a frame to the frame_stash hash table.  Do
+   not store frames below 0 as they may not have any addresses to
+   calculate a hash.  */
 
 static void
 frame_stash_add (struct frame_info *frame)
 {
-  frame_stash = frame;
+  /* Do not stash frames below level 0.  */
+  if (frame->level >= 0)
+    {
+      struct frame_info **slot;
+
+      slot = (struct frame_info **) htab_find_slot (frame_stash,
+						    frame,
+						    INSERT);
+      *slot = frame;
+    }
 }
 
-/* Search the frame stash for an entry with the given frame ID.
-   If found, return that frame.  Otherwise return NULL.  */
+/* Internal function to search the frame stash for an entry with the
+   given frame ID.  If found, return that frame.  Otherwise return
+   NULL.  */
 
 static struct frame_info *
 frame_stash_find (struct frame_id id)
 {
-  if (frame_stash && frame_id_eq (frame_stash->this_id.value, id))
-    return frame_stash;
+  struct frame_info dummy;
+  struct frame_info *frame;
 
-  return NULL;
+  dummy.this_id.value = id;
+  frame = htab_find (frame_stash, &dummy);
+  return frame;
 }
 
-/* Invalidate the frame stash by removing all entries in it.  */
+/* Internal function to invalidate the frame stash by removing all
+   entries in it.  This only occurs when the frame cache is
+   invalidated.  */
 
 static void
 frame_stash_invalidate (void)
 {
-  frame_stash = NULL;
+  htab_empty (frame_stash);
 }
 
 /* Flag to control debugging.  */
@@ -345,10 +415,9 @@
 	  fprint_frame_id (gdb_stdlog, fi->this_id.value);
 	  fprintf_unfiltered (gdb_stdlog, " }\n");
 	}
+      frame_stash_add (fi);
     }
 
-  frame_stash_add (fi);
-
   return fi->this_id.value;
 }
 
@@ -2451,6 +2520,8 @@
 {
   obstack_init (&frame_cache_obstack);
 
+  frame_stash_create ();
+
   observer_attach_target_changed (frame_observer_target_changed);
 
   add_prefix_cmd ("backtrace", class_maintenance, set_backtrace_cmd, _("\