This is the mail archive of the
gdb@sourceware.org
mailing list for the GDB project.
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;