This is the mail archive of the gdb@sourceware.org mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Organization of breakpoint locations


Daniel Jacobowitz schrieb:
> sometime this year.  But I think we can add a sequence number to
> bp_location's just like breakpoints have.
>   
and in fact a separate number seems to be needed, as the breakpoint
number is unknown (zero) when the breakpoint location is created. I did
not investigate this further and  just added a number to bp_location.
> I'd like GDB to be able to manage huge breakpoint lists; I'm just
> warning you that a lot more work will have to be done first ;-)
>   
ok, here is a first step: attached is small patch that stores the
breakpoint locations in a splay instead of a list. The patch is fairly
straight forward: mostly one compare function for splay-tree.c and a
number of iterator functions to simplify the access macros. It even
survived a make check. I hope this patch motivates someone to fix the
scalability issues with breakpoints ;-)


Thomas

diff -r -u -b gdb-6.6.original/gdb/breakpoint.c gdb-6.6/gdb/breakpoint.c
--- gdb-6.6.original/gdb/breakpoint.c	2006-10-19 17:58:25.000000000 +0200
+++ gdb-6.6/gdb/breakpoint.c	2007-02-19 22:46:09.283209500 +0100
@@ -53,6 +53,7 @@
 #include "solist.h"
 #include "observer.h"
 #include "exceptions.h"
+#include "splay-tree.h"
 
 #include "gdb-events.h"
 #include "mi/mi-common.h"
@@ -254,11 +255,16 @@
 
 /* Similar iterators for the low-level breakpoints.  */
 
-#define ALL_BP_LOCATIONS(B)  for (B = bp_location_chain; B; B = B->next)
+#define ALL_BP_LOCATIONS(B)							\
+	for (B = bp_location_tree_first();B!=NULL;B = bp_location_tree_next(B))
+
+#define ALL_BP_LOCATIONS_ADDR(B,a)				\
+	for (B = bp_location_tree_first_address(a);B!=NULL;	\
+             B = bp_location_tree_next_address(B,a))
 
 #define ALL_BP_LOCATIONS_SAFE(B,TMP)	\
-	for (B = bp_location_chain;	\
-	     B ? (TMP=B->next, 1): 0;	\
+	for (B = bp_location_tree_first();			\
+            (B!=NULL)?(TMP=bp_location_tree_next(B),1):0;	\
 	     B = TMP)
 
 /* True if breakpoint hit counts should be displayed in breakpoint info.  */
@@ -269,7 +275,9 @@
 
 struct breakpoint *breakpoint_chain;
 
-struct bp_location *bp_location_chain;
+static splay_tree bp_location_tree;
+
+static int bp_location_number;
 
 /* Number of last breakpoint made.  */
 
@@ -339,6 +347,76 @@
    error (_("catch of library unloads not yet implemented on this platform"))
 #endif
 
+/** Compare entries in the breakpoint tree */
+static int
+bp_location_tree_cmp (splay_tree_key l, splay_tree_key r)
+{
+  struct bp_location *lp=(struct bp_location*)l, *rp=(struct bp_location*)r;
+  if (lp->address < rp->address)
+    return -1;
+  if (lp->address > rp->address)
+    return 1;
+  if (lp->number < rp->number)
+    return -1;
+  if (lp->number > rp->number)
+    return 1;
+  return 0;
+}
+
+/** Find the first entry in the breakpoint tree */
+static struct bp_location*
+bp_location_tree_first ()
+{
+  if (bp_location_tree == NULL)
+    return NULL;
+  return (struct bp_location*)splay_tree_min(bp_location_tree)->value;
+}
+
+/** Find the next entry in the breakpoint tree */
+static struct bp_location*
+bp_location_tree_next (struct bp_location* b)
+{
+  splay_tree_node n = splay_tree_successor (bp_location_tree,
+                        (splay_tree_key)b);
+  if (n == NULL)
+    return NULL;
+  return (struct bp_location*)n->value;
+}
+
+/** Find the first entry in the breakpoint tree with a given address*/
+static struct bp_location*
+bp_location_tree_first_address (CORE_ADDR a)
+{
+  struct breakpoint b;
+  struct bp_location l,*r;
+  splay_tree_node n;
+
+  if (bp_location_tree == NULL)
+    return NULL;
+
+  b.number = INT_MIN;
+  l.owner = &b;
+  l.address = a;
+  n = splay_tree_successor (bp_location_tree,(splay_tree_key)&l);
+
+  if (n == NULL)
+    return NULL;
+  r = (struct bp_location*)n->value;
+  if (r->address != a)
+    return NULL;
+  return r;
+}
+
+/** Find the next entry in the breakpoint tree with a given address */
+static struct bp_location*
+bp_location_tree_next_address (struct bp_location* b, CORE_ADDR a)
+{
+  struct bp_location* r = bp_location_tree_next (b);
+  if ((r == NULL)||(r->address != a))
+     return NULL;
+  return r;
+}
+
 /* Return whether a breakpoint is an active enabled breakpoint.  */
 static int
 breakpoint_enabled (struct breakpoint *b)
@@ -3889,7 +3967,7 @@
   if (! breakpoint_address_is_meaningful (bpt))
     return;
 
-  ALL_BP_LOCATIONS (b)
+  ALL_BP_LOCATIONS_ADDR (b, address)
     if (b->owner->enable_state != bp_disabled
 	&& b->owner->enable_state != bp_shlib_disabled
 	&& !b->owner->pending
@@ -4054,18 +4132,6 @@
       internal_error (__FILE__, __LINE__, _("unknown breakpoint type"));
     }
 
-  /* Add this breakpoint to the end of the chain.  */
-
-  loc_p = bp_location_chain;
-  if (loc_p == 0)
-    bp_location_chain = loc;
-  else
-    {
-      while (loc_p->next)
-	loc_p = loc_p->next;
-      loc_p->next = loc;
-    }
-
   return loc;
 }
 
@@ -4095,6 +4161,14 @@
   b->loc->requested_address = sal.pc;
   b->loc->address = adjust_breakpoint_address (b->loc->requested_address,
                                                bptype);
+  /* Add this breakpoint at the back of the tree.  */
+  b->loc->number = bp_location_number ++;
+  if (bp_location_tree == NULL)
+    bp_location_tree = splay_tree_new (bp_location_tree_cmp, NULL, NULL);
+  splay_tree_insert (bp_location_tree,
+                     (splay_tree_key)b->loc,
+                     (splay_tree_value)b->loc);
+
   if (sal.symtab == NULL)
     b->source_file = NULL;
   else
@@ -6777,8 +6851,7 @@
   if (breakpoint_chain == bpt)
     breakpoint_chain = bpt->next;
 
-  if (bp_location_chain == bpt->loc)
-    bp_location_chain = bpt->loc->next;
+  splay_tree_remove (bp_location_tree, (splay_tree_key)bpt->loc);
 
   /* If we have callback-style exception catchpoints, don't go through
      the adjustments to the C++ runtime library etc. if the inferior
@@ -6809,13 +6882,6 @@
       break;
     }
 
-  ALL_BP_LOCATIONS (loc)
-    if (loc->next == bpt->loc)
-      {
-	loc->next = bpt->loc->next;
-	break;
-      }
-
   check_duplicates (bpt);
   /* If this breakpoint was inserted, and there is another breakpoint
      at the same address, we need to insert the other breakpoint.  */
diff -r -u -b gdb-6.6.original/gdb/breakpoint.h gdb-6.6/gdb/breakpoint.h
--- gdb-6.6.original/gdb/breakpoint.h	2006-04-18 21:20:06.000000000 +0200
+++ gdb-6.6/gdb/breakpoint.h	2007-02-19 22:41:24.485410750 +0100
@@ -238,8 +238,8 @@
 
 struct bp_location
 {
-  /* Chain pointer to the next breakpoint location.  */
-  struct bp_location *next;
+  /* Unique number used for sorting */
+  int number;
 
   /* Type of this breakpoint location.  */
   enum bp_loc_type loc_type;

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]