Re: [patch] Convert frame_stash to a hash table

[Phil Muldoon <pmuldoon@redhat.com>]

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, _("\