[07/12] gdb: link breakpoint locations with intrusive_list

  Replace the hand-maintained linked lists of breakpoint locations with
and intrusive list.

 - Remove breakpoint::loc, add breakpoint::m_locations.

 - Add methods for the various manipulations that need to be done on the
   location list.

 - bp_location currently has a default constructor because of one use
   in hoist_existing_locations.  hoist_existing_locations now returns a
   bp_location_list, and doesn't need the default-constructor
   bp_location anymore, so remove the bp_location default constructor.

 - Add a call to clear_locations in delete_breakpoint to avoid a
   use-after-free when struct breakpoint objects get deleted

bp_location_range uses reference_to_pointer_iterator, so that all
existing callers of breakpoint::locations don't need to change right
now.  It will be removed in the next patch.

The rest of the changes are to adapt the call sites to use the new
methods, of breakpoint::locations, rather than breakpoint::loc directly.

Change-Id: I25f7ee3d66a4e914a0540589ac414b3b820b6e70
---
 gdb/breakpoint.c | 258 ++++++++++++++++++++++++-----------------------
 gdb/breakpoint.h |  77 ++++++++++----
 gdb/tracepoint.c |   4 +-
 3 files changed, 188 insertions(+), 151 deletions(-)
  

Simon Marchi via Gdb-patches <gdb-patches@sourceware.org> writes:

> Replace the hand-maintained linked lists of breakpoint locations with
> and intrusive list.
>
>  - Remove breakpoint::loc, add breakpoint::m_locations.
>
>  - Add methods for the various manipulations that need to be done on the
>    location list.
>
>  - bp_location currently has a default constructor because of one use
>    in hoist_existing_locations.  hoist_existing_locations now returns a
>    bp_location_list, and doesn't need the default-constructor
>    bp_location anymore, so remove the bp_location default constructor.
>
>  - Add a call to clear_locations in delete_breakpoint to avoid a
>    use-after-free when struct breakpoint objects get deleted
>
> bp_location_range uses reference_to_pointer_iterator, so that all
> existing callers of breakpoint::locations don't need to change right
> now.  It will be removed in the next patch.
>
> The rest of the changes are to adapt the call sites to use the new
> methods, of breakpoint::locations, rather than breakpoint::loc directly.
>
> Change-Id: I25f7ee3d66a4e914a0540589ac414b3b820b6e70
> ---
>  gdb/breakpoint.c | 258 ++++++++++++++++++++++++-----------------------
>  gdb/breakpoint.h |  77 ++++++++++----
>  gdb/tracepoint.c |   4 +-
>  3 files changed, 188 insertions(+), 151 deletions(-)
>
> diff --git a/gdb/breakpoint.c b/gdb/breakpoint.c
> index e9b6574bba77..6ec0f6a11e88 100644
> --- a/gdb/breakpoint.c
> +++ b/gdb/breakpoint.c
> @@ -1049,13 +1049,18 @@ set_breakpoint_condition (struct breakpoint *b, const char *exp,
>  	     the error and the condition string will be rejected.
>  	     This two-pass approach is taken to avoid setting the
>  	     state of locations in case of a reject.  */
> -	  for (bp_location *loc : b->locations ())
> +	  auto bp_loc_range = b->locations ();
> +	  for (auto bp_loc_it = bp_loc_range.begin ();
> +	       bp_loc_it != bp_loc_range.end ();
> +	       ++bp_loc_it)
>  	    {
> +	      bp_location &loc = **bp_loc_it;
> +

You could switch this to:

  for (const bp_location *loc : b->locations ())

if we could also do .... (continued below)

>  	      try
>  		{
>  		  const char *arg = exp;
> -		  parse_exp_1 (&arg, loc->address,
> -			       block_for_pc (loc->address), 0);
> +		  parse_exp_1 (&arg, loc.address,
> +			       block_for_pc (loc.address), 0);
>  		  if (*arg != 0)
>  		    error (_("Junk at end of expression"));
>  		  break;
> @@ -1065,7 +1070,7 @@ set_breakpoint_condition (struct breakpoint *b, const char *exp,
>  		  /* Condition string is invalid.  If this happens to
>  		     be the last loc, abandon (if not forced) or continue
>  		     (if forced).  */
> -		  if (loc->next == nullptr && !force)
> +		  if (std::next (bp_loc_it) == bp_loc_range.end () && !force)

... this:

  if (loc == b->last_loc ())
    throw

This requires adding 'breakpoint::last_loc ()' but we already have
'breakpoint::first_loc ()' so that doesn't seem crazy, and I think the
resulting code would be easier to read maybe?

>  		    throw;
>  		}
>  	    }
> @@ -1878,8 +1883,9 @@ add_dummy_location (struct breakpoint *b,
>  {
>    gdb_assert (!b->has_locations ());
>  
> -  b->loc = new bp_location (b, bp_loc_other);
> -  b->loc->pspace = pspace;
> +  bp_location *loc = new bp_location (b, bp_loc_other);
> +  loc->pspace = pspace;
> +  b->add_location (*loc);
>  }
>  
>  /* Assuming that B is a watchpoint:
> @@ -1982,7 +1988,7 @@ update_watchpoint (struct watchpoint *b, bool reparse)
>    /* We don't free locations.  They are stored in the bp_location array
>       and update_global_location_list will eventually delete them and
>       remove breakpoints if needed.  */
> -  b->loc = NULL;
> +  b->clear_locations ();
>  
>    if (within_current_scope && reparse)
>      {
> @@ -2081,7 +2087,6 @@ update_watchpoint (struct watchpoint *b, bool reparse)
>  		{
>  		  CORE_ADDR addr;
>  		  enum target_hw_bp_type type;
> -		  struct bp_location *loc, **tmp;
>  		  int bitpos = 0, bitsize = 0;
>  
>  		  if (v->bitsize () != 0)
> @@ -2113,10 +2118,9 @@ update_watchpoint (struct watchpoint *b, bool reparse)
>  		  else if (b->type == bp_access_watchpoint)
>  		    type = hw_access;
>  
> -		  loc = b->allocate_location ();
> -		  for (tmp = &(b->loc); *tmp != NULL; tmp = &((*tmp)->next))
> -		    ;
> -		  *tmp = loc;
> +		  bp_location *loc = b->allocate_location ();
> +		  b->add_location (*loc);
> +
>  		  loc->gdbarch = v->type ()->arch ();
>  
>  		  loc->pspace = frame_pspace;
> @@ -3029,23 +3033,11 @@ breakpoint_program_space_exit (struct program_space *pspace)
>    /* Breakpoints set through other program spaces could have locations
>       bound to PSPACE as well.  Remove those.  */
>    for (bp_location *loc : all_bp_locations ())
> -    {
> -      struct bp_location *tmp;
> -
> -      if (loc->pspace == pspace)
> -	{
> -	  /* ALL_BP_LOCATIONS bp_location has LOC->OWNER always non-NULL.  */
> -	  if (loc->owner->loc == loc)
> -	    loc->owner->loc = loc->next;
> -	  else
> -	    for (tmp = loc->owner->loc; tmp->next != NULL; tmp = tmp->next)
> -	      if (tmp->next == loc)
> -		{
> -		  tmp->next = loc->next;
> -		  break;
> -		}
> -	}
> -    }
> +    if (loc->pspace == pspace)
> +      {
> +	/* ALL_BP_LOCATIONS bp_location has LOC->OWNER always non-NULL.  */
> +	loc->owner->unadd_location (*loc);
> +      }
>  
>    /* Now update the global location list to permanently delete the
>       removed locations above.  */
> @@ -4166,7 +4158,7 @@ breakpoint_init_inferior (enum inf_context context)
>  		   update_watchpoint, when the inferior is restarted.
>  		   The next update_global_location_list call will
>  		   garbage collect them.  */
> -		b->loc = NULL;
> +		b->clear_locations ();
>  
>  		if (context == inf_starting)
>  		  {
> @@ -4518,28 +4510,23 @@ bpstat_locno (const bpstat *bs)
>    const struct breakpoint *b = bs->breakpoint_at;
>    const struct bp_location *bl = bs->bp_location_at.get ();
>  
> -  int locno = 0;
> -
>    if (b != nullptr && b->has_multiple_locations ())
>      {
> -      const bp_location *bl_i;
> -
> -      for (bl_i = b->loc;
> -	   bl_i != bl && bl_i->next != nullptr;
> -	   bl_i = bl_i->next)
> -	locno++;
> +      int locno = 1;
>  
> -      if (bl_i == bl)
> -	locno++;
> -      else
> +      for (bp_location *loc : b->locations ())
>  	{
> -	  warning (_("location number not found for breakpoint %d address %s."),
> -		   b->number, paddress (bl->gdbarch, bl->address));
> -	  locno = 0;
> +	  if (bl == loc)
> +	    return locno;
> +
> +	  ++locno;
>  	}
> +
> +      warning (_("location number not found for breakpoint %d address %s."),
> +	       b->number, paddress (bl->gdbarch, bl->address));
>      }

I might be missing something here, but could this code be simplified by
using std::distance in some way?  We already use std::distance later in
this patch to count the total number of locations, so it feels like this
should work.

I know that the current code allows for the possibility that the
location (from the bp_stat) might not be in the location list of the
breakpoint (from bp_stat), but, surely that can't happen, right?  Surely
the location was originally found by looking through the locations of
the breakpoint... so it should be certain that we find the location.

I guess maybe we could remove the breakpoint_at from bp_stat, and just
use the owner of the bp_location_at variable, that way we could be
certain about all this...

Either way, there's nothing wrong with your code above, just wondering
if we can make it tighter...

>  
> -  return locno;
> +  return 0;
>  }
>  
>  /* See breakpoint.h.  */
> @@ -8178,18 +8165,19 @@ momentary_breakpoint_from_master (struct breakpoint *orig,
>      (new_momentary_breakpoint (orig->gdbarch, type, orig->pspace,
>  			       orig->frame_id, thread));
>    bp_location &orig_loc = orig->first_loc ();
> -  copy->loc = copy->allocate_location ();
> -  set_breakpoint_location_function (copy->loc);
> -
> -  copy->loc->gdbarch = orig_loc.gdbarch;
> -  copy->loc->requested_address = orig_loc.requested_address;
> -  copy->loc->address = orig_loc.address;
> -  copy->loc->section = orig_loc.section;
> -  copy->loc->pspace = orig_loc.pspace;
> -  copy->loc->probe = orig_loc.probe;
> -  copy->loc->line_number = orig_loc.line_number;
> -  copy->loc->symtab = orig_loc.symtab;
> -  copy->loc->enabled = loc_enabled;
> +  bp_location *copy_loc = copy->allocate_location ();
> +  copy->add_location (*copy_loc);
> +  set_breakpoint_location_function (copy_loc);
> +
> +  copy_loc->gdbarch = orig_loc.gdbarch;
> +  copy_loc->requested_address = orig_loc.requested_address;
> +  copy_loc->address = orig_loc.address;
> +  copy_loc->section = orig_loc.section;
> +  copy_loc->pspace = orig_loc.pspace;
> +  copy_loc->probe = orig_loc.probe;
> +  copy_loc->line_number = orig_loc.line_number;
> +  copy_loc->symtab = orig_loc.symtab;
> +  copy_loc->enabled = loc_enabled;
>  
>    breakpoint *b = add_to_breakpoint_chain (std::move (copy));
>    update_global_location_list_nothrow (UGLL_DONT_INSERT);
> @@ -8294,7 +8282,6 @@ handle_automatic_hardware_breakpoints (bp_location *bl)
>  bp_location *
>  code_breakpoint::add_location (const symtab_and_line &sal)
>  {
> -  struct bp_location *new_loc, **tmp;
>    CORE_ADDR adjusted_address;
>    struct gdbarch *loc_gdbarch = get_sal_arch (sal);
>  
> @@ -8312,12 +8299,8 @@ code_breakpoint::add_location (const symtab_and_line &sal)
>  						sal.pspace);
>  
>    /* Sort the locations by their ADDRESS.  */
> -  new_loc = allocate_location ();
> -  for (tmp = &(loc); *tmp != NULL && (*tmp)->address <= adjusted_address;
> -       tmp = &((*tmp)->next))
> -    ;
> -  new_loc->next = *tmp;
> -  *tmp = new_loc;
> +  bp_location *new_loc = this->allocate_location ();
> +  breakpoint::add_location (*new_loc, adjusted_address);

I notice here the code basically does:

  1. Create bp_location object,
  2. Add bp_location object to list,
  3. Initialise bp_location object.

We have to pass adjusted_address through because the address of new_loc
has not yet been initialised.

Could we reorder things so we:

  1. Create bp_location object,
  2. Initialise bp_location object,
  3. Add bp_location object to list.

The benefit I think would be that we can remove these two functions:

  void breakpoint::add_location (bp_location &loc);
  void breakpoint::add_location (bp_location &loc, CORE_ADDR address);

And we replace them with one function:

  void breakpoint::add_location (bp_location &loc, bool sorted = false);

The implementation would be free to use 'loc.address' for the sorting.

>  
>    new_loc->requested_address = sal.pc;
>    new_loc->address = adjusted_address;
> @@ -11623,10 +11606,7 @@ code_breakpoint::say_where () const
>  
>        if (this->has_multiple_locations ())
>  	{
> -	  struct bp_location *iter = loc;
> -	  int n = 0;
> -	  for (; iter; iter = iter->next)
> -	    ++n;
> +	  int n = std::distance (m_locations.begin (), m_locations.end ());
>  	  gdb_printf (" (%d locations)", n);
>  	}
>      }
> @@ -11636,7 +11616,9 @@ code_breakpoint::say_where () const
>  
>  bp_location_range breakpoint::locations () const
>  {
> -  return bp_location_range (this->loc);
> +  return bp_location_range
> +    (bp_location_pointer_iterator (m_locations.begin ()),
> +     bp_location_pointer_iterator (m_locations.end ()));
>  }
>  
>  struct bp_location *
> @@ -11645,6 +11627,43 @@ breakpoint::allocate_location ()
>    return new bp_location (this);
>  }
>  
> +/* See breakpoint.h.  */
> +
> +void
> +breakpoint::add_location (bp_location &loc)
> +{
> +  gdb_assert (loc.owner == this);
> +  gdb_assert (!loc.is_linked ());
> +
> +  m_locations.push_back (loc);
> +}
> +
> +/* See breakpoint.h.  */
> +
> +void
> +breakpoint::add_location (bp_location &loc, CORE_ADDR address)
> +{
> +  gdb_assert (loc.owner == this);
> +  gdb_assert (!loc.is_linked ());
> +
> +  auto ub = std::upper_bound (m_locations.begin (), m_locations.end (),
> +			      address,
> +			      [] (CORE_ADDR left, bp_location &right)
> +				{ return left < right.address; });
> +  m_locations.insert (ub, loc);
> +}
> +
> +/* See breakpoint.h.  */
> +
> +void
> +breakpoint::unadd_location (bp_location &loc)
> +{
> +  gdb_assert (loc.owner == this);
> +  gdb_assert (loc.is_linked ());
> +
> +  m_locations.erase (m_locations.iterator_to (loc));
> +}
> +
>  #define internal_error_pure_virtual_called() \
>    gdb_assert_not_reached ("pure virtual function called")
>  
> @@ -12395,7 +12414,12 @@ delete_breakpoint (struct breakpoint *bpt)
>       belong to this breakpoint.  Do this before freeing the breakpoint
>       itself, since remove_breakpoint looks at location's owner.  It
>       might be better design to have location completely
> -     self-contained, but it's not the case now.  */
> +     self-contained, but it's not the case now.
> +
> +     Clear the location linked list first, otherwise, the intrusive_list
> +     destructor would access the locations after they are freed in
> +     update_global_location_list.  */
> +  bpt->clear_locations ();
>    update_global_location_list (UGLL_DONT_INSERT);
>  
>    /* On the chance that someone will soon try again to delete this
> @@ -12490,17 +12514,16 @@ all_locations_are_pending (struct breakpoint *b, struct program_space *pspace)
>  }
>  
>  /* Subroutine of update_breakpoint_locations to simplify it.
> -   Return true if multiple fns in list LOC have the same name.
> +   Return true if multiple fns in list LOCS have the same name.
>     Null names are ignored.  */
>  
>  static bool
> -ambiguous_names_p (struct bp_location *loc)
> +ambiguous_names_p (const bp_location_range &locs)
>  {
> -  struct bp_location *l;
>    htab_up htab (htab_create_alloc (13, htab_hash_string, htab_eq_string, NULL,
>  				   xcalloc, xfree));
>  
> -  for (l = loc; l != NULL; l = l->next)
> +  for (const bp_location *l : locs)
>      {
>        const char **slot;
>        const char *name = l->function_name.get ();
> @@ -12645,72 +12668,56 @@ update_static_tracepoint (struct breakpoint *b, struct symtab_and_line sal)
>    return sal;
>  }
>  
> -/* Returns true iff locations A and B are sufficiently same that
> +/* Returns true iff location lists A and B are sufficiently same that
>     we don't need to report breakpoint as changed.  */
>  
>  static bool
> -locations_are_equal (struct bp_location *a, struct bp_location *b)
> +locations_are_equal (const bp_location_list &a, const bp_location_range &b)
>  {
> -  while (a && b)
> +  auto a_iter = a.begin ();
> +  auto b_iter = b.begin ();
> +
> +  for (; a_iter != a.end () && b_iter != b.end (); ++a_iter, ++b_iter)
>      {
> -      if (a->address != b->address)
> +      if (a_iter->address != (*b_iter)->address)
>  	return false;
>  
> -      if (a->shlib_disabled != b->shlib_disabled)
> +      if (a_iter->shlib_disabled != (*b_iter)->shlib_disabled)
>  	return false;
>  
> -      if (a->enabled != b->enabled)
> +      if (a_iter->enabled != (*b_iter)->enabled)
>  	return false;
>  
> -      if (a->disabled_by_cond != b->disabled_by_cond)
> +      if (a_iter->disabled_by_cond != (*b_iter)->disabled_by_cond)
>  	return false;
> -
> -      a = a->next;
> -      b = b->next;
>      }
>  
> -  if ((a == NULL) != (b == NULL))
> -    return false;
> -
> -  return true;
> +  return (a_iter == a.end ()) == (b_iter == b.end ());
>  }
>  
> -/* Split all locations of B that are bound to PSPACE out of B's
> -   location list to a separate list and return that list's head.  If
> -   PSPACE is NULL, hoist out all locations of B.  */
> +/* See breakpoint.h.  */
>  
> -static struct bp_location *
> -hoist_existing_locations (struct breakpoint *b, struct program_space *pspace)
> +bp_location_list
> +breakpoint::steal_locations (program_space *pspace)
>  {
> -  struct bp_location head;
> -  struct bp_location *i = b->loc;
> -  struct bp_location **i_link = &b->loc;
> -  struct bp_location *hoisted = &head;
> -
>    if (pspace == NULL)
> -    {
> -      i = b->loc;
> -      b->loc = NULL;
> -      return i;
> -    }
> +    return std::move (m_locations);
>  
> -  head.next = NULL;
> +  bp_location_list ret;
>  
> -  while (i != NULL)
> +  for (auto it = m_locations.begin (); it != m_locations.end (); )
>      {
> -      if (i->pspace == pspace)
> +      if (it->pspace == pspace)
>  	{
> -	  *i_link = i->next;
> -	  i->next = NULL;
> -	  hoisted->next = i;
> -	  hoisted = i;
> +	  bp_location &loc = *it;
> +	  it = m_locations.erase (it);
> +	  ret.push_back (loc);
>  	}
>        else
> -	i_link = &i->next;
> -      i = *i_link;
> +	++it;
>      }
>  
> -  return head.next;
> +  return ret;
>  }
>  
>  /* Create new breakpoint locations for B (a hardware or software
> @@ -12725,8 +12732,6 @@ update_breakpoint_locations (code_breakpoint *b,
>  			     gdb::array_view<const symtab_and_line> sals,
>  			     gdb::array_view<const symtab_and_line> sals_end)
>  {
> -  struct bp_location *existing_locations;
> -
>    if (!sals_end.empty () && (sals.size () != 1 || sals_end.size () != 1))
>      {
>        /* Ranged breakpoints have only one start location and one end
> @@ -12748,7 +12753,7 @@ update_breakpoint_locations (code_breakpoint *b,
>    if (all_locations_are_pending (b, filter_pspace) && sals.empty ())
>      return;
>  
> -  existing_locations = hoist_existing_locations (b, filter_pspace);
> +  bp_location_list existing_locations = b->steal_locations (filter_pspace);
>  
>    for (const auto &sal : sals)
>      {
> @@ -12788,17 +12793,16 @@ update_breakpoint_locations (code_breakpoint *b,
>    /* If possible, carry over 'disable' status from existing
>       breakpoints.  */
>    {
> -    struct bp_location *e = existing_locations;
>      /* If there are multiple breakpoints with the same function name,
>         e.g. for inline functions, comparing function names won't work.
>         Instead compare pc addresses; this is just a heuristic as things
>         may have moved, but in practice it gives the correct answer
>         often enough until a better solution is found.  */
> -    int have_ambiguous_names = ambiguous_names_p (b->loc);
> +    int have_ambiguous_names = ambiguous_names_p (b->locations ());
>  
> -    for (; e; e = e->next)
> +    for (const bp_location &e : existing_locations)
>        {
> -	if ((!e->enabled || e->disabled_by_cond) && e->function_name)
> +	if ((!e.enabled || e.disabled_by_cond) && e.function_name)
>  	  {
>  	    if (have_ambiguous_names)
>  	      {
> @@ -12811,10 +12815,10 @@ update_breakpoint_locations (code_breakpoint *b,
>  		       As mentioned above, this is an heuristic and in
>  		       practice should give the correct answer often
>  		       enough.  */
> -		    if (breakpoint_locations_match (e, l, true))
> +		    if (breakpoint_locations_match (&e, l, true))
>  		      {
> -			l->enabled = e->enabled;
> -			l->disabled_by_cond = e->disabled_by_cond;
> +			l->enabled = e.enabled;
> +			l->disabled_by_cond = e.disabled_by_cond;
>  			break;
>  		      }
>  		  }
> @@ -12823,11 +12827,11 @@ update_breakpoint_locations (code_breakpoint *b,
>  	      {
>  		for (bp_location *l : b->locations ())
>  		  if (l->function_name
> -		      && strcmp (e->function_name.get (),
> +		      && strcmp (e.function_name.get (),
>  				 l->function_name.get ()) == 0)
>  		    {
> -		      l->enabled = e->enabled;
> -		      l->disabled_by_cond = e->disabled_by_cond;
> +		      l->enabled = e.enabled;
> +		      l->disabled_by_cond = e.disabled_by_cond;
>  		      break;
>  		    }
>  	      }
> @@ -12835,7 +12839,7 @@ update_breakpoint_locations (code_breakpoint *b,
>        }
>    }
>  
> -  if (!locations_are_equal (existing_locations, b->loc))
> +  if (!locations_are_equal (existing_locations, b->locations ()))
>      gdb::observers::breakpoint_modified.notify (b);
>  }
>  
> diff --git a/gdb/breakpoint.h b/gdb/breakpoint.h
> index 9f49ed62a9ad..4da64d8c27c8 100644
> --- a/gdb/breakpoint.h
> +++ b/gdb/breakpoint.h
> @@ -33,6 +33,7 @@
>  #include "gdbsupport/next-iterator.h"
>  #include "gdbsupport/iterator-range.h"
>  #include "gdbsupport/refcounted-object.h"
> +#include "gdbsupport/reference-to-pointer-iterator.h"
>  #include "gdbsupport/safe-iterator.h"
>  #include "cli/cli-script.h"
>  #include "target/waitstatus.h"
> @@ -321,11 +322,9 @@ enum bp_loc_type
>    bp_loc_other			/* Miscellaneous...  */
>  };
>  
> -class bp_location : public refcounted_object
> +class bp_location : public refcounted_object, public intrusive_list_node<bp_location>
>  {
>  public:
> -  bp_location () = default;
> -
>    /* Construct a bp_location with the type inferred from OWNER's
>       type.  */
>    explicit bp_location (breakpoint *owner);
> @@ -335,10 +334,6 @@ class bp_location : public refcounted_object
>  
>    virtual ~bp_location () = default;
>  
> -  /* Chain pointer to the next breakpoint location for
> -     the same parent breakpoint.  */
> -  bp_location *next = NULL;
> -
>    /* Type of this breakpoint location.  */
>    bp_loc_type loc_type {};
>  
> @@ -609,9 +604,11 @@ enum watchpoint_triggered
>  
>  extern bool target_exact_watchpoints;
>  
> -/* bp_location linked list range.  */
> -
> -using bp_location_range = next_range<bp_location>;
> +using bp_location_list = intrusive_list<bp_location>;
> +using bp_location_iterator = bp_location_list::iterator;
> +using bp_location_pointer_iterator
> +  = reference_to_pointer_iterator<bp_location_iterator>;
> +using bp_location_range = iterator_range<bp_location_pointer_iterator>;
>  
>  /* Note that the ->silent field is not currently used by any commands
>     (though the code is in there if it was to be, and set_raw_breakpoint
> @@ -633,30 +630,71 @@ struct breakpoint
>    /* Allocate a location for this breakpoint.  */
>    virtual struct bp_location *allocate_location ();
>  
> +  /* Return a range of this breakpoint's locations.  */
> +  bp_location_range locations () const;
> +
> +  /* Add LOC at the end of the location list of this breakpoint.
> +
> +     LOC must have this breakpoint as its owner.  LOC must not already be linked
> +     in a location list.  */
> +  void add_location (bp_location &loc);
> +
> +  /* Add LOC in the location list of this breakpoint, sorted by address.
> +
> +     LOC must have this breakpoint as its owner.  LOC must not already be linked
> +     in a location list.  */
> +  void add_location (bp_location &loc, CORE_ADDR address);

It would be nice for the comment to mention what ADDRESS means here.
However, my earlier comments for where this function is used might mean
this is no longer needed in this form.

Thanks,
Andrew

> +
> +  /* Remove LOC from this breakpoint's location list.  The name is a bit funny
> +     because remove_location is already taken, and means something else.
> +
> +     LOC must be have this breakpoints as its owner.  LOC must be linked in this
> +     breakpoint's location list.  */
> +  void unadd_location (bp_location &loc);
> +
> +  /* Clear the location list of this breakpoint.  */
> +  void clear_locations ()
> +  { m_locations.clear (); }
> +
> +  /* Split all locations of this breakpoint that are bound to PSPACE out of its
> +     location list to a separate list and return that list.  If
> +     PSPACE is nullptr, hoist out all locations.  */
> +  bp_location_list steal_locations (program_space *pspace);
> +
>    /* Return true if this breakpoint has a least one location.  */
>    bool has_locations () const
> -  { return this->loc != nullptr; }
> +  { return !m_locations.empty (); }
>  
>    /* Return true if this breakpoint has a single location.  */
>    bool has_single_location () const
> -  { return this->loc != nullptr && this->loc->next == nullptr; }
> +  {
> +    if (!this->has_locations ())
> +      return false;
> +
> +    return std::next (m_locations.begin ()) == m_locations.end ();
> +  }
>  
>    /* Return true if this breakpoint has multiple locations.  */
>    bool has_multiple_locations () const
> -  { return this->loc != nullptr && this->loc->next != nullptr; }
> +  {
> +    if (!this->has_locations ())
> +      return false;
> +
> +    return std::next (m_locations.begin ()) != m_locations.end ();
> +  }
>  
>    /* Return a reference to the first location of this breakpoint.  */
>    bp_location &first_loc ()
>    {
>      gdb_assert (this->has_locations ());
> -    return *this->loc;
> +    return m_locations.front ();
>    }
>  
>    /* Return a reference to the first location of this breakpoint.  */
>    const bp_location &first_loc () const
>    {
>      gdb_assert (this->has_locations ());
> -    return *this->loc;
> +    return m_locations.front ();
>    }
>  
>    /* Reevaluate a breakpoint.  This is necessary after symbols change
> @@ -753,9 +791,6 @@ struct breakpoint
>      /* Nothing to do.  */
>    }
>  
> -  /* Return a range of this breakpoint's locations.  */
> -  bp_location_range locations () const;
> -
>    breakpoint *next = NULL;
>    /* Type of breakpoint.  */
>    bptype type = bp_none;
> @@ -766,9 +801,6 @@ struct breakpoint
>    /* Number assigned to distinguish breakpoints.  */
>    int number = 0;
>  
> -  /* Location(s) associated with this high-level breakpoint.  */
> -  bp_location *loc = NULL;
> -
>    /* True means a silent breakpoint (don't print frame info if we stop
>       here).  */
>    bool silent = false;
> @@ -864,6 +896,9 @@ struct breakpoint
>       thread 1", which needs outputting before any breakpoint-type
>       specific extra command necessary for B's recreation.  */
>    void print_recreate_thread (struct ui_file *fp) const;
> +
> +  /* Location(s) associated with this high-level breakpoint.  */
> +  bp_location_list m_locations;
>  };
>  
>  /* Abstract base class representing code breakpoints.  User "break"
> diff --git a/gdb/tracepoint.c b/gdb/tracepoint.c
> index 99d175d32e42..3e0bdafa19d3 100644
> --- a/gdb/tracepoint.c
> +++ b/gdb/tracepoint.c
> @@ -3044,8 +3044,6 @@ cond_string_is_same (char *str1, char *str2)
>  static struct bp_location *
>  find_matching_tracepoint_location (struct uploaded_tp *utp)
>  {
> -  struct bp_location *loc;
> -
>    for (breakpoint *b : all_tracepoints ())
>      {
>        struct tracepoint *t = (struct tracepoint *) b;
> @@ -3059,7 +3057,7 @@ find_matching_tracepoint_location (struct uploaded_tp *utp)
>  	  )
>  	{
>  	  /* Scan the locations for an address match.  */
> -	  for (loc = b->loc; loc; loc = loc->next)
> +	  for (bp_location *loc : b->locations ())
>  	    {
>  	      if (loc->address == utp->addr)
>  		return loc;
> -- 
> 2.40.1
  

>> diff --git a/gdb/breakpoint.c b/gdb/breakpoint.c
>> index e9b6574bba77..6ec0f6a11e88 100644
>> --- a/gdb/breakpoint.c
>> +++ b/gdb/breakpoint.c
>> @@ -1049,13 +1049,18 @@ set_breakpoint_condition (struct breakpoint *b, const char *exp,
>>  	     the error and the condition string will be rejected.
>>  	     This two-pass approach is taken to avoid setting the
>>  	     state of locations in case of a reject.  */
>> -	  for (bp_location *loc : b->locations ())
>> +	  auto bp_loc_range = b->locations ();
>> +	  for (auto bp_loc_it = bp_loc_range.begin ();
>> +	       bp_loc_it != bp_loc_range.end ();
>> +	       ++bp_loc_it)
>>  	    {
>> +	      bp_location &loc = **bp_loc_it;
>> +
> 
> You could switch this to:
> 
>   for (const bp_location *loc : b->locations ())
> 
> if we could also do .... (continued below)
> 
>>  	      try
>>  		{
>>  		  const char *arg = exp;
>> -		  parse_exp_1 (&arg, loc->address,
>> -			       block_for_pc (loc->address), 0);
>> +		  parse_exp_1 (&arg, loc.address,
>> +			       block_for_pc (loc.address), 0);
>>  		  if (*arg != 0)
>>  		    error (_("Junk at end of expression"));
>>  		  break;
>> @@ -1065,7 +1070,7 @@ set_breakpoint_condition (struct breakpoint *b, const char *exp,
>>  		  /* Condition string is invalid.  If this happens to
>>  		     be the last loc, abandon (if not forced) or continue
>>  		     (if forced).  */
>> -		  if (loc->next == nullptr && !force)
>> +		  if (std::next (bp_loc_it) == bp_loc_range.end () && !force)
> 
> ... this:
> 
>   if (loc == b->last_loc ())
>     throw
> 
> This requires adding 'breakpoint::last_loc ()' but we already have
> 'breakpoint::first_loc ()' so that doesn't seem crazy, and I think the
> resulting code would be easier to read maybe?
Yeah, that's a good idea.  It makes the code read just like the comment
does (if the loc is the last loc), which is a plus for readability.

Note that I used &b->last_loc (), as I made last_loc return a reference
(like first_loc).

>> @@ -4518,28 +4510,23 @@ bpstat_locno (const bpstat *bs)
>>    const struct breakpoint *b = bs->breakpoint_at;
>>    const struct bp_location *bl = bs->bp_location_at.get ();
>>  
>> -  int locno = 0;
>> -
>>    if (b != nullptr && b->has_multiple_locations ())
>>      {
>> -      const bp_location *bl_i;
>> -
>> -      for (bl_i = b->loc;
>> -	   bl_i != bl && bl_i->next != nullptr;
>> -	   bl_i = bl_i->next)
>> -	locno++;
>> +      int locno = 1;
>>  
>> -      if (bl_i == bl)
>> -	locno++;
>> -      else
>> +      for (bp_location *loc : b->locations ())
>>  	{
>> -	  warning (_("location number not found for breakpoint %d address %s."),
>> -		   b->number, paddress (bl->gdbarch, bl->address));
>> -	  locno = 0;
>> +	  if (bl == loc)
>> +	    return locno;
>> +
>> +	  ++locno;
>>  	}
>> +
>> +      warning (_("location number not found for breakpoint %d address %s."),
>> +	       b->number, paddress (bl->gdbarch, bl->address));
>>      }
> 
> I might be missing something here, but could this code be simplified by
> using std::distance in some way?  We already use std::distance later in
> this patch to count the total number of locations, so it feels like this
> should work.
> 
> I know that the current code allows for the possibility that the
> location (from the bp_stat) might not be in the location list of the
> breakpoint (from bp_stat), but, surely that can't happen, right?  Surely
> the location was originally found by looking through the locations of
> the breakpoint... so it should be certain that we find the location.
> 
> I guess maybe we could remove the breakpoint_at from bp_stat, and just
> use the owner of the bp_location_at variable, that way we could be
> certain about all this...
> 
> Either way, there's nothing wrong with your code above, just wondering
> if we can make it tighter...

I'm not sure about whether we are sure that the location is in its
parent location list, there is perhaps some corner cases about handling
a breakpoint hit event on a location that has been removed since.
However, I see that before putting a location in the moribund_locations
vector, we set its owner to NULL.  So if the owner field is non-NULL, it
should be safe to assume the location is in the list.

I don't think it's easy to use std::distance right now though, because
with the reference_to_pointer_iterator wrapper, we can't go from item to
iterator in O(1).  We can if we had access to the intrusive_list
directly, since it has an "iterator_to" method.

In any case, I will not make such a change in this patch to avoid mixing
things together.  I tried to make this patch a straightforward
translation without any unnecessary algorithmic changes.  I'll check if
it becomes possible at the end of the series though.

>> @@ -8312,12 +8299,8 @@ code_breakpoint::add_location (const symtab_and_line &sal)
>>  						sal.pspace);
>>  
>>    /* Sort the locations by their ADDRESS.  */
>> -  new_loc = allocate_location ();
>> -  for (tmp = &(loc); *tmp != NULL && (*tmp)->address <= adjusted_address;
>> -       tmp = &((*tmp)->next))
>> -    ;
>> -  new_loc->next = *tmp;
>> -  *tmp = new_loc;
>> +  bp_location *new_loc = this->allocate_location ();
>> +  breakpoint::add_location (*new_loc, adjusted_address);
> 
> I notice here the code basically does:
> 
>   1. Create bp_location object,
>   2. Add bp_location object to list,
>   3. Initialise bp_location object.
> 
> We have to pass adjusted_address through because the address of new_loc
> has not yet been initialised.
> 
> Could we reorder things so we:
> 
>   1. Create bp_location object,
>   2. Initialise bp_location object,
>   3. Add bp_location object to list.
> 
> The benefit I think would be that we can remove these two functions:
> 
>   void breakpoint::add_location (bp_location &loc);
>   void breakpoint::add_location (bp_location &loc, CORE_ADDR address);
> 
> And we replace them with one function:
> 
>   void breakpoint::add_location (bp_location &loc, bool sorted = false);
> 
> The implementation would be free to use 'loc.address' for the sorting.

Good idea, I will do that.  That seems like a minor / low-risk change,
so I'll do it in this patch.

For consistency, I moved the "add_location" call after setting
loc->address in update_watchpoint as well, even though it wouldn't
matter in that case.

>> @@ -633,30 +630,71 @@ struct breakpoint
>>    /* Allocate a location for this breakpoint.  */
>>    virtual struct bp_location *allocate_location ();
>>  
>> +  /* Return a range of this breakpoint's locations.  */
>> +  bp_location_range locations () const;
>> +
>> +  /* Add LOC at the end of the location list of this breakpoint.
>> +
>> +     LOC must have this breakpoint as its owner.  LOC must not already be linked
>> +     in a location list.  */
>> +  void add_location (bp_location &loc);
>> +
>> +  /* Add LOC in the location list of this breakpoint, sorted by address.
>> +
>> +     LOC must have this breakpoint as its owner.  LOC must not already be linked
>> +     in a location list.  */
>> +  void add_location (bp_location &loc, CORE_ADDR address);
> 
> It would be nice for the comment to mention what ADDRESS means here.
> However, my earlier comments for where this function is used might mean
> this is no longer needed in this form.

Yes, this gets removed.

Thanks,

Simon
  

Simon Marchi <simon.marchi@efficios.com> writes:

>>> diff --git a/gdb/breakpoint.c b/gdb/breakpoint.c
>>> index e9b6574bba77..6ec0f6a11e88 100644
>>> --- a/gdb/breakpoint.c
>>> +++ b/gdb/breakpoint.c
>>> @@ -1049,13 +1049,18 @@ set_breakpoint_condition (struct breakpoint *b, const char *exp,
>>>  	     the error and the condition string will be rejected.
>>>  	     This two-pass approach is taken to avoid setting the
>>>  	     state of locations in case of a reject.  */
>>> -	  for (bp_location *loc : b->locations ())
>>> +	  auto bp_loc_range = b->locations ();
>>> +	  for (auto bp_loc_it = bp_loc_range.begin ();
>>> +	       bp_loc_it != bp_loc_range.end ();
>>> +	       ++bp_loc_it)
>>>  	    {
>>> +	      bp_location &loc = **bp_loc_it;
>>> +
>> 
>> You could switch this to:
>> 
>>   for (const bp_location *loc : b->locations ())
>> 
>> if we could also do .... (continued below)
>> 
>>>  	      try
>>>  		{
>>>  		  const char *arg = exp;
>>> -		  parse_exp_1 (&arg, loc->address,
>>> -			       block_for_pc (loc->address), 0);
>>> +		  parse_exp_1 (&arg, loc.address,
>>> +			       block_for_pc (loc.address), 0);
>>>  		  if (*arg != 0)
>>>  		    error (_("Junk at end of expression"));
>>>  		  break;
>>> @@ -1065,7 +1070,7 @@ set_breakpoint_condition (struct breakpoint *b, const char *exp,
>>>  		  /* Condition string is invalid.  If this happens to
>>>  		     be the last loc, abandon (if not forced) or continue
>>>  		     (if forced).  */
>>> -		  if (loc->next == nullptr && !force)
>>> +		  if (std::next (bp_loc_it) == bp_loc_range.end () && !force)
>> 
>> ... this:
>> 
>>   if (loc == b->last_loc ())
>>     throw
>> 
>> This requires adding 'breakpoint::last_loc ()' but we already have
>> 'breakpoint::first_loc ()' so that doesn't seem crazy, and I think the
>> resulting code would be easier to read maybe?
> Yeah, that's a good idea.  It makes the code read just like the comment
> does (if the loc is the last loc), which is a plus for readability.
>
> Note that I used &b->last_loc (), as I made last_loc return a reference
> (like first_loc).
>
>>> @@ -4518,28 +4510,23 @@ bpstat_locno (const bpstat *bs)
>>>    const struct breakpoint *b = bs->breakpoint_at;
>>>    const struct bp_location *bl = bs->bp_location_at.get ();
>>>  
>>> -  int locno = 0;
>>> -
>>>    if (b != nullptr && b->has_multiple_locations ())
>>>      {
>>> -      const bp_location *bl_i;
>>> -
>>> -      for (bl_i = b->loc;
>>> -	   bl_i != bl && bl_i->next != nullptr;
>>> -	   bl_i = bl_i->next)
>>> -	locno++;
>>> +      int locno = 1;
>>>  
>>> -      if (bl_i == bl)
>>> -	locno++;
>>> -      else
>>> +      for (bp_location *loc : b->locations ())
>>>  	{
>>> -	  warning (_("location number not found for breakpoint %d address %s."),
>>> -		   b->number, paddress (bl->gdbarch, bl->address));
>>> -	  locno = 0;
>>> +	  if (bl == loc)
>>> +	    return locno;
>>> +
>>> +	  ++locno;
>>>  	}
>>> +
>>> +      warning (_("location number not found for breakpoint %d address %s."),
>>> +	       b->number, paddress (bl->gdbarch, bl->address));
>>>      }
>> 
>> I might be missing something here, but could this code be simplified by
>> using std::distance in some way?  We already use std::distance later in
>> this patch to count the total number of locations, so it feels like this
>> should work.
>> 
>> I know that the current code allows for the possibility that the
>> location (from the bp_stat) might not be in the location list of the
>> breakpoint (from bp_stat), but, surely that can't happen, right?  Surely
>> the location was originally found by looking through the locations of
>> the breakpoint... so it should be certain that we find the location.
>> 
>> I guess maybe we could remove the breakpoint_at from bp_stat, and just
>> use the owner of the bp_location_at variable, that way we could be
>> certain about all this...
>> 
>> Either way, there's nothing wrong with your code above, just wondering
>> if we can make it tighter...
>
> I'm not sure about whether we are sure that the location is in its
> parent location list, there is perhaps some corner cases about handling
> a breakpoint hit event on a location that has been removed since.
> However, I see that before putting a location in the moribund_locations
> vector, we set its owner to NULL.  So if the owner field is non-NULL, it
> should be safe to assume the location is in the list.
>
> I don't think it's easy to use std::distance right now though, because
> with the reference_to_pointer_iterator wrapper, we can't go from item to
> iterator in O(1).  We can if we had access to the intrusive_list
> directly, since it has an "iterator_to" method.
>
> In any case, I will not make such a change in this patch to avoid mixing
> things together.  I tried to make this patch a straightforward
> translation without any unnecessary algorithmic changes.  I'll check if
> it becomes possible at the end of the series though.

Not a problem, I did wonder if there was going to be some reason why
this wasn't a helpful suggestion :)

Thanks for looking into it though.

Andrew

>
>>> @@ -8312,12 +8299,8 @@ code_breakpoint::add_location (const symtab_and_line &sal)
>>>  						sal.pspace);
>>>  
>>>    /* Sort the locations by their ADDRESS.  */
>>> -  new_loc = allocate_location ();
>>> -  for (tmp = &(loc); *tmp != NULL && (*tmp)->address <= adjusted_address;
>>> -       tmp = &((*tmp)->next))
>>> -    ;
>>> -  new_loc->next = *tmp;
>>> -  *tmp = new_loc;
>>> +  bp_location *new_loc = this->allocate_location ();
>>> +  breakpoint::add_location (*new_loc, adjusted_address);
>> 
>> I notice here the code basically does:
>> 
>>   1. Create bp_location object,
>>   2. Add bp_location object to list,
>>   3. Initialise bp_location object.
>> 
>> We have to pass adjusted_address through because the address of new_loc
>> has not yet been initialised.
>> 
>> Could we reorder things so we:
>> 
>>   1. Create bp_location object,
>>   2. Initialise bp_location object,
>>   3. Add bp_location object to list.
>> 
>> The benefit I think would be that we can remove these two functions:
>> 
>>   void breakpoint::add_location (bp_location &loc);
>>   void breakpoint::add_location (bp_location &loc, CORE_ADDR address);
>> 
>> And we replace them with one function:
>> 
>>   void breakpoint::add_location (bp_location &loc, bool sorted = false);
>> 
>> The implementation would be free to use 'loc.address' for the sorting.
>
> Good idea, I will do that.  That seems like a minor / low-risk change,
> so I'll do it in this patch.
>
> For consistency, I moved the "add_location" call after setting
> loc->address in update_watchpoint as well, even though it wouldn't
> matter in that case.
>
>>> @@ -633,30 +630,71 @@ struct breakpoint
>>>    /* Allocate a location for this breakpoint.  */
>>>    virtual struct bp_location *allocate_location ();
>>>  
>>> +  /* Return a range of this breakpoint's locations.  */
>>> +  bp_location_range locations () const;
>>> +
>>> +  /* Add LOC at the end of the location list of this breakpoint.
>>> +
>>> +     LOC must have this breakpoint as its owner.  LOC must not already be linked
>>> +     in a location list.  */
>>> +  void add_location (bp_location &loc);
>>> +
>>> +  /* Add LOC in the location list of this breakpoint, sorted by address.
>>> +
>>> +     LOC must have this breakpoint as its owner.  LOC must not already be linked
>>> +     in a location list.  */
>>> +  void add_location (bp_location &loc, CORE_ADDR address);
>> 
>> It would be nice for the comment to mention what ADDRESS means here.
>> However, my earlier comments for where this function is used might mean
>> this is no longer needed in this form.
>
> Yes, this gets removed.
>
> Thanks,
>
> Simon