From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 11322 invoked by alias); 19 Feb 2007 22:08:21 -0000 Received: (qmail 11312 invoked by uid 22791); 19 Feb 2007 22:08:19 -0000 X-Spam-Check-By: sourceware.org Received: from pm1.terions.de (HELO pm1.terions.de) (83.137.96.25) by sourceware.org (qpsmtpd/0.31) with ESMTP; Mon, 19 Feb 2007 22:08:12 +0000 Received: (qmail 25233 invoked by uid 98); 19 Feb 2007 22:08:11 -0000 Received: from dslb-084-058-247-087.pools.arcor-ip.net (HELO ?192.168.0.2?) (tn@tneumann.de@84.58.247.87) by mail.s-s-l.net with SMTP; 19 Feb 2007 22:08:11 -0000 Message-ID: <45DA1FDB.8000800@users.sourceforge.net> Date: Tue, 20 Feb 2007 04:46:00 -0000 From: Thomas Neumann User-Agent: Thunderbird 1.5.0.9 (X11/20070103) MIME-Version: 1.0 To: Thomas Neumann , gdb@sourceware.org Subject: Re: Organization of breakpoint locations References: <45D97E30.2060008@users.sourceforge.net> <20070219115744.GC6815@caradoc.them.org> <45D99E03.1050309@users.sourceforge.net> <20070219130342.GA10857@caradoc.them.org> In-Reply-To: <20070219130342.GA10857@caradoc.them.org> Content-Type: multipart/mixed; boundary="------------030201050804070305020704" Mailing-List: contact gdb-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-owner@sourceware.org X-SW-Source: 2007-02/txt/msg00205.txt.bz2 This is a multi-part message in MIME format. --------------030201050804070305020704 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-length: 886 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 --------------030201050804070305020704 Content-Type: text/plain; name="breakpointsinsplay.patch" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="breakpointsinsplay.patch" Content-length: 5781 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; --------------030201050804070305020704--