Re: Organization of breakpoint locations

[Daniel Jacobowitz <drow at false dot org>]

On Mon, Feb 19, 2007 at 11:38:40AM +0100, Thomas Neumann wrote:
> Hi,
> 
> I would like some suggestions on the organization of breakpoint
> locations in breakpoint.c. Currently, all breakpoint locations are
> stored in a linear list. This does not scale if the number of
> breakpoints is large, see PR 2230 for an example. Instead the
> breakpoints should be stored in a suitable search structure (e.g. a
> balanced tree).
> 
> I have a patch that converts the list into a splay. Works fine, and the
> bottleneck indeed goes away, but I am not satisfied with the approach
> itself.

Have you tested this in any real world use yet?  This is only the
first limitation you'll encounter, I think.  For instance, every time
you step and then stop the program, GDB is going to remove every
breakpoint.  That's going to be just as slow.

> It would be nicer to reuse existing data structures instead of
> implementing a new one. I thought about using splay-tree in libiberty,
> but the breakpoint locations have some unique characteristics: 1. the
> locations have to be organized by address, but the address is not
> necessarily unique. So the search structure must handle duplicates. 2.
> the test suite (and perhaps other code) expect that a breakpoint is
> added "last" in the list, i.e. duplicate handling must keep an order
> within the duplicates. 3. it must be possible to iterate over search
> structure (directly, without callbacks), as otherwise a lot of code has
> to be changed.
> 
> The splay implementation from libiberty satisfies none of these
> constraints.

Why do you think that the splay tree in libiberty can't handle any of
these?  Your key would not be the address, but the address plus the
breakpoint sequence number.  That handles one and two.  Then you can
iterate over items using splay_tree_successor.  The key could be the
same pointer as the value, by the way - it just takes a clever
splay_tree_compare_fn.

Another way is to use the address as a key, but store a VEC of
breakpoints as the values, sorted by number.  That's messier though.

> Is there perhaps something else in the gdb sources that I
> can reuse? Or should I submit my (admittedly quite large) patch? But
> this would probably no longer count as a "small changes" that according
> to CONTRIBUTE do not require a copyright assignment.

To be honest, I don't think this will be a small change either way.

-- 
Daniel Jacobowitz
CodeSourcery