[PATCH 0/5] gdb: Store section map in an interval tree

[PATCH 0/5] gdb: Store section map in an interval tree

[Ilya Leoshkevich]

Hi,

When debugging JITs that report ~10k sections, GDB slows to a crawl,
even with the recent optimization [1].  The problem is that the
algorithmic complexity of adding N new sections is O((N**2)*log(N)),
because the code calls update_section_map() and thus std::sort() N
times.

This series aims to reduce this to O(N*log(N)) by storing sections in
an interval tree and updating it incrementally instead of rebuilding it
every time from scratch.  The interval tree is chosen instead of
simpler alternatives in order to handle overlapping sections.

- Patch 1 introduces obstack_newvec() for allocating obj_section
  objects, which later become non-POD types.
- Patches 2-3 introduce interval tree implementation and tests for it.
- Patch 5 is the actual optimization.

The performance testing [2] results can be found here: [3].

This series survives the regtest on x86_64, power and s390x.

Best regards,
Ilya

[1] https://sourceware.org/git/?p=binutils-gdb.git;a=commit;h=625b6eae091709b95471eae92d42dc6bc71e6553
[2] https://sourceware.org/pipermail/gdb-patches/2022-May/189592.html
[3] https://github.com/iii-i/binutils-gdb/blob/section-map-20220601-2/gdb/testsuite/jit.png


Ilya Leoshkevich (5):
  gdbsupport: Introduce obstack_newvec
  gdbsupport: Introduce interval_tree
  gdbsupport: Add interval_tree unit tests
  gdbsupport: Add interval_tree fuzzing harness
  gdb: Optimize section map

 gdb/Makefile.in                         |   1 +
 gdb/objfiles.c                          | 384 +++++-----
 gdb/objfiles.h                          |  15 +-
 gdb/symfile.c                           |   2 +-
 gdb/unittests/interval_tree-selftests.c | 400 +++++++++++
 gdbsupport/gdb_obstack.h                |  26 +
 gdbsupport/interval_tree.h              | 915 ++++++++++++++++++++++++
 7 files changed, 1526 insertions(+), 217 deletions(-)
 create mode 100644 gdb/unittests/interval_tree-selftests.c
 create mode 100644 gdbsupport/interval_tree.h

-- 
2.35.3

[PATCH 1/5] gdbsupport: Introduce obstack_newvec

[Ilya Leoshkevich]

obstack_calloc() allocates multiple objects, but doesn't call their
constructors.  obstack_new() allocates a single object and calls its
constructor.  Introduce a new function that does both.
---
 gdbsupport/gdb_obstack.h | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

diff --git a/gdbsupport/gdb_obstack.h b/gdbsupport/gdb_obstack.h
index 5e870cb7981..201ed99216f 100644
--- a/gdbsupport/gdb_obstack.h
+++ b/gdbsupport/gdb_obstack.h
@@ -59,6 +59,32 @@ obstack_new (struct obstack *ob, Args&&... args)
   return object;
 }
 
+/* Allocate NUMBER objects on OB and call their default constructors.  Note
+   that obstack_free() won't call their destructors: this has to be done
+   manually.  */
+
+template <typename T>
+static inline T *
+obstack_newvec (obstack *ob, size_t number)
+{
+  T *objects = static_cast<T *> (obstack_alloc (ob, number * sizeof (T)));
+  for (size_t i = 0; i < number; i++)
+    {
+      try
+	{
+	  new (objects + i) T ();
+	}
+      catch (...)
+	{
+	  for (size_t j = 0; j < i; j++)
+	    (objects + j)->~T ();
+	  obstack_free (ob, objects);
+	  throw;
+	};
+    }
+  return objects;
+}
+
 /* Unless explicitly specified, GDB obstacks always use xmalloc() and
    xfree().  */
 /* Note: ezannoni 2004-02-09: One could also specify the allocation
-- 
2.35.3

Re: [PATCH 1/5] gdbsupport: Introduce obstack_newvec

[Tom Tromey]

>>>>> "Ilya" == Ilya Leoshkevich <iii@linux.ibm.com> writes:

Ilya> obstack_calloc() allocates multiple objects, but doesn't call their
Ilya> constructors.  obstack_new() allocates a single object and calls its
Ilya> constructor.  Introduce a new function that does both.

Is there some reason you want to keep these objects on the obstack at
all?  There's no requirement to do that in gdb, and it's probably
simpler to just use ordinary C++ allocation instead.

Tom

Re: [PATCH 1/5] gdbsupport: Introduce obstack_newvec

[Ilya Leoshkevich]

On Thu, 2022-06-02 at 08:31 -0600, Tom Tromey wrote:
> > > > > > "Ilya" == Ilya Leoshkevich <iii@linux.ibm.com> writes:
> 
> Ilya> obstack_calloc() allocates multiple objects, but doesn't call
> their
> Ilya> constructors.  obstack_new() allocates a single object and
> calls its
> Ilya> constructor.  Introduce a new function that does both.
> 
> Is there some reason you want to keep these objects on the obstack at
> all?  There's no requirement to do that in gdb, and it's probably
> simpler to just use ordinary C++ allocation instead.
> 
> Tom

Not really, the only reason is that it used to be this way.  I can use
new[]/delete[] instead - this will simplify things.

[PATCH 2/5] gdbsupport: Introduce interval_tree

[Ilya Leoshkevich]

Currently adding or removing a single section causes
update_section_map() to rebuild the section map from scratch, which
involves calling std::sort(), so the complexity of that is O(N*log(N).

Adding N JITed sections has the complexity O((N**2)*log(N)), because
adding each section involves breakpoint handling, which needs to
resolve PCs and thus calls update_section_map().  When N is around 10k,
this renders GDB unusable.

Therefore an efficient data structure that can handle incremental
updates is needed.  Interval trees fit the bill: the updates and
lookups are in O(log(N)).  They also support overlapping intervals,
which is important for debuginfo handling and diagnosing GDB internal
problems - an obvious std::map<CORE_ADDR, ...> alternative cannot do
that.

This patch adds an implementation based on "Introduction to
Algorithms".  The naming and the code structure try to stay as close to
the book as possible.  Some ideas are also borrowed from Linux Kernel's
interval_tree_generic.h.
---
 gdbsupport/interval_tree.h | 915 +++++++++++++++++++++++++++++++++++++
 1 file changed, 915 insertions(+)
 create mode 100644 gdbsupport/interval_tree.h

diff --git a/gdbsupport/interval_tree.h b/gdbsupport/interval_tree.h
new file mode 100644
index 00000000000..b62982c52d5
--- /dev/null
+++ b/gdbsupport/interval_tree.h
@@ -0,0 +1,915 @@
+/* Interval tree for GDB, the GNU debugger.
+   Copyright (C) 2022 Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef GDBSUPPORT_INTERVAL_TREE_H
+#define GDBSUPPORT_INTERVAL_TREE_H
+
+/* Based on:
+
+   Cormen T. H., Leiserson C. E., Rivest R. L., and Stein C..  2009.
+   Introduction to Algorithms, Third Edition (3rd ed.).  The MIT Press.
+   Section 13: Red-Black Trees.
+   Section 14.3: Interval trees.  */
+
+#include "gdbsupport/gdb_assert.h"
+#include "gdbsupport/gdb_optional.h"
+#include <algorithm>
+#include <iterator>
+#include <utility>
+
+/* Forward declarations.  */
+
+template <typename Interval> struct interval_traits;
+template <typename Interval, typename Traits> class interval_tree;
+template <typename Interval, typename Traits> class interval_tree_key;
+template <typename Interval, typename Traits> class interval_tree_node;
+template <typename Interval, typename Traits> class interval_tree_iterator;
+template <typename Interval, typename Traits>
+class interval_tree_find_iterator;
+template <typename Interval, typename Traits> class interval_tree;
+
+/* Accessors for INTERVAL's low and high endpoints.  */
+
+template <typename Interval> struct interval_traits
+{
+  typedef typename Interval::endpoint_type endpoint_type;
+
+  static endpoint_type
+  low (const Interval &t)
+  {
+    return t.low;
+  }
+
+  static endpoint_type
+  high (const Interval &t)
+  {
+    return t.high;
+  }
+};
+
+/* Interval tree key that uses both the low and the high interval ends.
+   Strictly speaking, only the low end is enough, however, using the high one
+   as a tie-breaker makes the iteration order more predictable.
+   For internal use only.  */
+
+template <typename Interval, typename Traits> class interval_tree_key
+{
+private:
+  using endpoint_type = typename Traits::endpoint_type;
+
+  interval_tree_key (endpoint_type low, endpoint_type high)
+      : m_low (low), m_high (high)
+  {
+  }
+
+  bool
+  operator<= (endpoint_type rhs) const
+  {
+    return m_low <= rhs;
+  }
+
+  bool
+  operator>= (endpoint_type rhs) const
+  {
+    return m_low >= rhs;
+  }
+
+  bool
+  operator<(const interval_tree_key &rhs) const
+  {
+    return m_low != rhs.m_low ? m_low < rhs.m_low : m_high < rhs.m_high;
+  }
+
+  bool
+  operator<= (const interval_tree_key &rhs) const
+  {
+    return m_low != rhs.m_low ? m_low < rhs.m_low : m_high <= rhs.m_high;
+  }
+
+  endpoint_type m_low;
+  endpoint_type m_high;
+
+  friend class interval_tree<Interval, Traits>;
+  friend class interval_tree_node<Interval, Traits>;
+};
+
+/* Interval tree node.  This is either a regular node, which holds a
+   user-specified interval, or a nil node, which does not.  For internal use
+   only.  */
+
+template <typename Interval, typename Traits> class interval_tree_node
+{
+private:
+  enum class direction
+  {
+    left,
+    right
+  };
+
+  enum class color
+  {
+    black,
+    red
+  };
+
+  using endpoint_type = typename Traits::endpoint_type;
+  using key_type = interval_tree_key<Interval, Traits>;
+
+  interval_tree_node () = default;
+
+  template <typename... Args>
+  explicit interval_tree_node (Args &&...args)
+      : m_int (gdb::in_place_t (), std::forward<Args> (args)...),
+	m_max (high ())
+  {
+  }
+
+  /* Prevent copies and moves - nodes must stay where they are created,
+     otherwise unwanted iterator invalidation may happen.  */
+
+  interval_tree_node (const interval_tree_node &) = delete;
+  interval_tree_node &operator= (const interval_tree_node &) = delete;
+  interval_tree_node (interval_tree_node &&) = delete;
+  interval_tree_node &operator= (interval_tree_node &&) = delete;
+
+  endpoint_type
+  low () const
+  {
+    return Traits::low (*m_int);
+  }
+
+  endpoint_type
+  high () const
+  {
+    return Traits::high (*m_int);
+  }
+
+  key_type
+  key () const
+  {
+    return key_type (low (), high ());
+  }
+
+  interval_tree_node *&
+  child (direction which)
+  {
+    if (which == direction::left)
+      return m_left;
+    else
+      return m_right;
+  }
+
+  interval_tree_node *
+  sibling (direction which) const
+  {
+    return m_p->child (which);
+  }
+
+  bool
+  is_child (direction which) const
+  {
+    return this == sibling (which);
+  }
+
+  direction
+  which_child () const
+  {
+    return is_child (direction::left) ? direction::left : direction::right;
+  }
+
+  color m_color;
+  gdb::optional<Interval> m_int;
+  interval_tree_node *m_left;
+  interval_tree_node *m_right;
+  interval_tree_node *m_p;
+  endpoint_type m_max;
+
+  friend class interval_tree_iterator<Interval, Traits>;
+  friend class interval_tree_find_iterator<Interval, Traits>;
+  friend class interval_tree<Interval, Traits>;
+};
+
+/* Interval tree iterator.  Returns intervals with smaller low endpoints first,
+   using high endpoints as tie-breakers.  Intervals with identical endpoints
+   are returned in an undefined order.  */
+
+template <typename Interval, typename Traits> class interval_tree_iterator
+{
+public:
+  using node = interval_tree_node<Interval, Traits>;
+  using tree = interval_tree<Interval, Traits>;
+
+  /* Create an iterator referring to an OBJECT from an INTERVAL within a
+     TREE.  */
+
+  static interval_tree_iterator
+  from_interval (tree &tree, Interval *object)
+  {
+    return interval_tree_iterator (
+	&tree, reinterpret_cast<node *> (reinterpret_cast<char *> (object)
+					 - offsetof (node, m_int)));
+  }
+
+  bool
+  operator== (const interval_tree_iterator &rhs) const
+  {
+    return m_x == rhs.m_x;
+  }
+
+  bool
+  operator!= (const interval_tree_iterator &rhs) const
+  {
+    return !(*this == rhs);
+  }
+
+  Interval &
+  operator* () const
+  {
+    return *m_x->m_int;
+  }
+
+  Interval *
+  operator->() const
+  {
+    return &**this;
+  }
+
+protected:
+  explicit interval_tree_iterator (tree *tree, node *x)
+      : m_tree (tree), m_x (x)
+  {
+  }
+
+  tree *m_tree;
+  node *m_x;
+
+  friend class interval_tree<Interval, Traits>;
+};
+
+/* Interval tree search iterator.  Returns intervals that overlap [LOW, HIGH].
+   Intervals with smaller low endpoints are returned first, high endpoints are
+   used as tie-breakers.  Intervals with identical endpoints are returned in an
+   undefined order.  */
+
+template <typename Interval, typename Traits>
+class interval_tree_find_iterator
+    : public interval_tree_iterator<Interval, Traits>
+{
+public:
+  using node = interval_tree_node<Interval, Traits>;
+  using endpoint_type = typename node::endpoint_type;
+  using tree = interval_tree<Interval, Traits>;
+
+  interval_tree_find_iterator &
+  operator++ ()
+  {
+    this->m_x = this->m_tree->interval_search_next (this->m_x, this->m_low,
+						    this->m_high);
+    return *this;
+  }
+
+  interval_tree_find_iterator
+  operator++ (int)
+  {
+    interval_tree_find_iterator result = *this;
+    ++(*this);
+    return result;
+  }
+
+private:
+  interval_tree_find_iterator (tree *tree, node *start, endpoint_type low,
+			       endpoint_type high)
+      : interval_tree_iterator<Interval, Traits> (tree, start), m_low (low),
+	m_high (high)
+  {
+    if (this->m_x != &this->m_tree->m_nil)
+      this->m_x = this->m_tree->interval_search (this->m_x, this->m_low,
+						 this->m_high);
+  }
+
+  endpoint_type m_low;
+  endpoint_type m_high;
+
+  friend class interval_tree<Interval, Traits>;
+};
+
+/* A container for intervals.  Supports efficient addition, lookup of
+   overlapping intervals and removal.  */
+
+template <typename Interval, typename Traits = interval_traits<Interval> >
+class interval_tree
+{
+public:
+  using node = interval_tree_node<Interval, Traits>;
+  using direction = typename node::direction;
+  using color = typename node::color;
+  using endpoint_type = typename node::endpoint_type;
+  using iterator = interval_tree_iterator<Interval, Traits>;
+
+  interval_tree () { m_nil.m_color = color::black; }
+
+  ~interval_tree () { rb_free (m_root); }
+
+  iterator
+  begin ()
+  {
+    if (m_root == &m_nil)
+      return end ();
+    return iterator (this, tree_minimum (m_root));
+  }
+
+  iterator
+  end ()
+  {
+    return iterator (this, &m_nil);
+  }
+
+  /* Construct a new interval and insert it into this tree.
+     Return an iterator pointing to this interval.  */
+
+  template <typename... Args>
+  iterator
+  emplace (Args &&...args)
+  {
+    node *z = new node (std::forward<Args> (args)...);
+    rb_insert (z);
+    return iterator (this, z);
+  }
+
+  /* Find all intervals in this tree that overlap with [LOW, HIGH].  */
+
+  interval_tree_find_iterator<Interval, Traits>
+  find (endpoint_type low, endpoint_type high)
+  {
+    return interval_tree_find_iterator<Interval, Traits> (this, m_root, low,
+							  high);
+  }
+
+  /* Remove a single interval from this tree.
+     All iterators except POS stay valid.  */
+
+  void
+  erase (iterator pos)
+  {
+    rb_delete (pos.m_x);
+    delete pos.m_x;
+  }
+
+  /* Remove all intervals from this tree.  */
+
+  void
+  clear ()
+  {
+    rb_free (m_root);
+    m_root = &m_nil;
+  }
+
+  /* Print T and check its invariants.  */
+
+  template <typename Stream>
+  friend Stream &
+  operator<< (Stream &stream, const interval_tree &t)
+  {
+    if (t.m_root == &t.m_nil)
+      stream << "(nil)\n";
+    else
+      {
+	t.rb_print (stream, t.m_root);
+	int black_height = -1;
+	t.rb_check (t.m_root, 0, black_height);
+      }
+    return stream;
+  }
+
+private:
+  static direction
+  opposite (direction where)
+  {
+    return where == direction::left ? direction::right : direction::left;
+  }
+
+  /* Link V in place of U.  */
+
+  void
+  rb_transplant (node *u, node *v)
+  {
+    if (u->m_p == &m_nil)
+      m_root = v;
+    else
+      u->m_p->child (u->which_child ()) = v;
+    v->m_p = u->m_p;
+  }
+
+  /* Perform a left or a right rotation of X.
+
+          |                     |
+        x=A                   x=C
+         / \     left ==>      / \
+        B y=C    <== right  y=A   E
+           / \               / \
+          D   E             B   D
+  */
+
+  void
+  rotate (node *x, direction where)
+  {
+    node *y = x->child (opposite (where));
+    x->child (opposite (where)) = y->child (where);
+    if (y->child (where) != &m_nil)
+      y->child (where)->m_p = x;
+    rb_transplant (x, y);
+    y->child (where) = x;
+    x->m_p = y;
+    update_max_1 (x);
+    update_max_1 (y);
+  }
+
+  /* Restore the red-black tree invariants after inserting node Z.  */
+
+  void
+  rb_insert_fixup (node *z)
+  {
+    while (z->m_p->m_color == color::red)
+      {
+	direction which = z->m_p->which_child ();
+	node *y = z->m_p->sibling (opposite (which));
+	/* In the drawings below we assume that z's parent is a left child.  */
+	if (y->m_color == color::red)
+	  {
+	    /* Case 1: z's uncle (y) is red.
+	       It is sufficient to adjust colors.
+	       Whether z itself is a left or a right child does not matter,
+	       in the drawing below we assume it is a left child.
+
+			      |                           |
+			  C(black)                   z=C(red)
+			 /        \                    /     \
+		     B(red)   y=D(red)   ==>      B(black)  D(black)
+		    /      \    /     \           /       \ /       \
+	      z=A(red)                        A(red)
+		/     \                       /     \
+	    */
+	    z->m_p->m_color = color::black;
+	    y->m_color = color::black;
+	    z->m_p->m_p->m_color = color::red;
+	    z = z->m_p->m_p;
+	  }
+	else
+	  {
+	    if (z->is_child (opposite (which)))
+	      {
+		/* Case 2: z's uncle (y) is black and z is a right child.
+		   Rotate left in order to turn this into case 3.
+
+			    |
+			C(black)
+			/       \
+		    A(red)       y
+		    /     \
+		   m  z=B(red)
+			/     \
+		       n       k
+		*/
+		z = z->m_p;
+		rotate (z, which);
+	      }
+	    /* Case 3: z's uncle (y) is black and z is a left child.
+	       Rotate right and adjust colors.
+
+			    |                       |
+			C(black)                B(black)
+			/       \               /       \
+		    B(red)       y          A(red)     C(red)
+		    /     \         ==>     /     \    /     \
+	      z=A(red)    k                m       n  k       y
+		/     \
+	       m       n
+	    */
+	    z->m_p->m_color = color::black;
+	    z->m_p->m_p->m_color = color::red;
+	    rotate (z->m_p->m_p, opposite (which));
+	  }
+      }
+    m_root->m_color = color::black;
+  }
+
+  /* Insert node Z into this tree.  */
+
+  void
+  rb_insert (node *z)
+  {
+    /* Find an insertion point according to the key.
+       Update m_max along the way.  */
+    node *y = &m_nil;
+    node *x = m_root;
+    direction which;
+    while (x != &m_nil)
+      {
+	y = x;
+	which = z->key () < x->key () ? direction::left : direction::right;
+	x = x->child (which);
+	if (y->m_max < z->high ())
+	  y->m_max = z->high ();
+      }
+
+    /* Perform insertion.  */
+    z->m_p = y;
+    if (y == &m_nil)
+      {
+	m_root = z;
+      }
+    else
+      {
+	y->child (which) = z;
+	update_max_1 (y);
+      }
+
+    /* Restore the red-black tree invariants.  */
+    z->m_left = &m_nil;
+    z->m_right = &m_nil;
+    z->m_color = color::red;
+    rb_insert_fixup (z);
+  }
+
+  /* Find an interval with the smallest key in a subtree rooted at X.  */
+
+  node *
+  tree_minimum (node *x)
+  {
+    while (x->m_left != &m_nil)
+      x = x->m_left;
+    return x;
+  }
+
+  /* Recompute m_max of node X.  */
+
+  void
+  update_max_1 (node *x)
+  {
+    x->m_max = x->high ();
+    if (x->m_left != &m_nil && x->m_left->m_max > x->m_max)
+      x->m_max = x->m_left->m_max;
+    if (x->m_right != &m_nil && x->m_right->m_max > x->m_max)
+      x->m_max = x->m_right->m_max;
+  }
+
+  /* Recompute m_max of node X and its ancestors.  */
+
+  void
+  update_max (node *x)
+  {
+    for (; x != &m_nil; x = x->m_p)
+      update_max_1 (x);
+  }
+
+  /* Restore the red-black tree invariants after deleting a node.
+     Note that X is not the deleted node, but rather the node at which
+     inconsistencies start.  */
+
+  void
+  rb_delete_fixup (node *x)
+  {
+    while (x != m_root && x->m_color == color::black)
+      {
+	direction which = x->which_child ();
+	/* In the drawings below we assume that x is a left child.  */
+	node *w = x->sibling (opposite (which));
+	if (w->m_color == color::red)
+	  {
+	    /* Case 1: x's sibling (w) is red.
+	       Adjust colors and rotate left in order to turn this into case 2,
+	       3 or 4.
+
+			 |                                     |
+		     A(black)                              C(black)
+		     /       \                             /       \
+	      x=B(black)  w=C(red)         ==>         A(red)   E(black)
+			    /     \                    /     \
+		       D(black)  E(black)       x=B(black)  w=D(black)
+	    */
+	    w->m_color = color::black;
+	    x->m_p->m_color = color::red;
+	    rotate (x->m_p, which);
+	    w = x->sibling (opposite (which));
+	  }
+	if (w->m_left->m_color == color::black
+	    && w->m_right->m_color == color::black)
+	  {
+	    /* Case 2: x's sibling (w) is black, and so are w's children.
+	       It is sufficient to adjust colors.  */
+	    w->m_color = color::red;
+	    x = x->m_p;
+	  }
+	else
+	  {
+	    if (w->child (opposite (which))->m_color == color::black)
+	      {
+		/* Case 3: x's sibling (w) is black, w's left child is red,
+		   and w's right child is black.  Adjust colors and rotate
+		   right in order to turn this into case 4.
+
+			     |
+			     A
+			  /     \
+		   x=B(black)  w=D(black)
+				 /       \
+			     E(red)   F(black)
+		*/
+		w->child (which)->m_color = color::black;
+		w->m_color = color::red;
+		rotate (w, opposite (which));
+		w = x->sibling (opposite (which));
+	      }
+	    /* Case 4: x's sibling (w) is black, and w's right child is red.
+	       Adjust colors and rotate left.
+
+			 |                                  |
+		       A(?)                             w=E(?)
+		      /     \                          /      \
+	       x=B(black)  w=E(black)      =>    A(black)  D(black)
+			     /       \              /    \
+			    G      D(red)      x=B(black) G
+	    */
+	    w->m_color = x->m_p->m_color;
+	    x->m_p->m_color = color::black;
+	    w->child (opposite (which))->m_color = color::black;
+	    rotate (x->m_p, which);
+	    /* No more inconsistencies can arise, exit the loop.  */
+	    x = m_root;
+	  }
+      }
+    x->m_color = color::black;
+  }
+
+  /* Remove node Z from this tree.  */
+
+  void
+  rb_delete (node *z)
+  {
+    node *y = z;
+    color y_original_color = y->m_color;
+    node *x;
+    if (z->m_left == &m_nil)
+      {
+	/* There is no left subtree, link z's right subtree in place of z.  */
+	x = z->m_right;
+	rb_transplant (z, z->m_right);
+	z->m_right = &m_nil;
+	update_max (z->m_p);
+      }
+    else if (z->m_right == &m_nil)
+      {
+	/* There is no right subtree, link z's left subtree in place of z.  */
+	x = z->m_left;
+	rb_transplant (z, z->m_left);
+	z->m_left = &m_nil;
+	update_max (z->m_p);
+      }
+    else
+      {
+	/* y is z's successor: the leftmost node in z's right subtree.  It has
+	   no left subtree.  First, link its right subtree (x) in its
+	   place.  */
+	y = tree_minimum (z->m_right);
+	y_original_color = y->m_color;
+	x = y->m_right;
+	node *m;
+	if (y->m_p == z)
+	  {
+	    x->m_p = y; /* x may be &m_nil.  */
+	    m = y;
+	  }
+	else
+	  {
+	    m = y->m_p;
+	    rb_transplant (y, x);
+	    y->m_right = z->m_right;
+	    y->m_right->m_p = y;
+	  }
+	/* Now that y is unlinked from its original position, link it in z's
+	   place.  */
+	rb_transplant (z, y);
+	y->m_left = z->m_left;
+	y->m_left->m_p = y;
+	y->m_color = z->m_color;
+	z->m_left = &m_nil;
+	z->m_right = &m_nil;
+	/* Finally, recompute m_max, which we need to do from y's parent's
+	   position.  If y's parent was z, then use y itself, because y was
+	   linked in z's position.  Otherwise, use y's original parent.  */
+	update_max (m);
+      }
+
+    if (y_original_color == color::black)
+      {
+	/* Restore the red-black tree invariants.  The inconsistencies start at
+	   the deepest node that was touched.  */
+	rb_delete_fixup (x);
+      }
+  }
+
+  /* Print node X and its descendants.  */
+
+  template <typename Stream>
+  void
+  rb_print (Stream &stream, const node *x, int indent = 0,
+	    const char *prefix = "") const
+  {
+    std::fill_n (std::ostream_iterator<char> (stream), indent, ' ');
+    stream << prefix << (x->m_color == color::black ? "B" : "R") << " ["
+	   << x->low () << ", " << x->high () << "] | " << x->m_max << "\n";
+    if (x->m_left != &m_nil)
+      rb_print (stream, x->m_left, indent + 1, "L");
+    if (x->m_right != &m_nil)
+      rb_print (stream, x->m_right, indent + 1, "R");
+  }
+
+  /* Check invariants of this node and of its descendants.  */
+
+  void
+  rb_check (const node *x, int cur_black_height, int &black_height) const
+  {
+    /* The root must be black.  */
+    if (x == m_root)
+      {
+	gdb_assert (x->m_p == &m_nil);
+	gdb_assert (x->m_color == color::black);
+      }
+
+    /* If a node is red, then both its children must be black.  */
+    if (x->m_color == color::red)
+      gdb_assert (x->m_left->m_color == color::black
+		  && x->m_right->m_color == color::black);
+
+    /* Interval's low endpoint must not be greater than its high endpoint.  */
+    gdb_assert (x->low () <= x->high ());
+
+    /* All simple paths from root to leaves must contain the same number of
+       black nodes.  */
+    if (x->m_left == &m_nil || x->m_right == &m_nil)
+      {
+	if (black_height < 0)
+	  black_height = cur_black_height;
+	else
+	  gdb_assert (black_height == cur_black_height);
+      }
+
+    endpoint_type max = x->high ();
+
+    /* Descend into the left subtree.  */
+    if (x->m_left != &m_nil)
+      {
+	gdb_assert (x->m_left->m_p == x);
+	gdb_assert (x->m_left->key () <= x->key ());
+	if (max < x->m_left->m_max)
+	  max = x->m_left->m_max;
+	rb_check (x->m_left,
+		  cur_black_height
+		      + (x->m_left->m_color == color::black ? 1 : 0),
+		  black_height);
+      }
+
+    /* Descend into the right subtree.  */
+    if (x->m_right != &m_nil)
+      {
+	gdb_assert (x->m_right->m_p == x);
+	gdb_assert (x->key () <= x->m_right->key ());
+	if (max < x->m_right->m_max)
+	  max = x->m_right->m_max;
+	rb_check (x->m_right,
+		  cur_black_height
+		      + (x->m_right->m_color == color::black ? 1 : 0),
+		  black_height);
+      }
+
+    gdb_assert (x->m_max == max);
+  }
+
+  /* Free node X and its descendants.  */
+
+  void
+  rb_free (node *x)
+  {
+    if (x == &m_nil)
+      return;
+    rb_free (x->m_left);
+    rb_free (x->m_right);
+    delete x;
+  }
+
+  /* Find the leftmost interval overlapping [LOW, HIGH] in the subtree rooted
+     at node X.  */
+
+  node *
+  interval_search (node *x, endpoint_type low, endpoint_type high)
+  {
+    for (;;)
+      {
+	if (x->m_left != &m_nil && low <= x->m_left->m_max)
+	  {
+	    /* If there is no overlap in the left subtree, there is none
+	       elsewhere either (this is not intuitive, see Theorem 14.2 in the
+	       book).  Descend.  */
+	    x = x->m_left;
+	    continue;
+	  }
+
+	if (high < x->low ())
+	  {
+	    /* x and its right subtree are to the right of the searched
+	       interval.  There is no overlap.  */
+	    return &m_nil;
+	  }
+
+	if (low <= x->high ())
+	  {
+	    /* x is the overlapping interval.  */
+	    return x;
+	  }
+
+	if (x->m_right != &m_nil && low <= x->m_right->m_max)
+	  {
+	    /* The right subtree may contain an overlap.  Descend.  */
+	    x = x->m_right;
+	    continue;
+	  }
+
+	/* There is no overlap.  */
+	return &m_nil;
+      }
+  }
+
+  /* Find the leftmost interval to the right of node X that overlaps
+     [LOW, HIGH].  X must be previously returned by interval_search () or by
+     interval_search_next ().  */
+
+  node *
+  interval_search_next (node *x, endpoint_type low, endpoint_type high)
+  {
+    for (;;)
+      {
+	/* We are not interested in the nodes to the left of X, since all the
+	   overlaps there have already been reported.  Therefore, ignore the
+	   left subtree.  */
+
+	if (x->m_right != &m_nil && low <= x->m_right->m_max)
+	  {
+	    /* If there is no overlap in the right subtree, there is none
+	       elsewhere either.  This can be proven the same way as
+	       Theorem 14.2 from the book.  */
+	    return interval_search (x->m_right, low, high);
+	  }
+
+	/* Go up until we find a node we haven't examined yet (its right
+	   subtree is also not examined).  It must be a left child.  */
+	bool from_right;
+	do
+	  {
+	    from_right = x->is_child (node::direction::right);
+	    x = x->m_p;
+	    if (x == &m_nil)
+	      return &m_nil;
+	  }
+	while (from_right);
+
+	if (high < x->low ())
+	  {
+	    /* x and its right subtree are to the right of the searched
+	       interval.  There is no overlap.  */
+	    return &m_nil;
+	  }
+
+	if (low <= x->high ())
+	  {
+	    /* x is the overlapping interval.  */
+	    return x;
+	  }
+      }
+  }
+
+  /* Convenience sentinel node.  Its m_int is not initialized.  The code above
+     can temporarily assign values to its members: for example, being able to
+     do x->m_p = y in rb_delete () simplifies things significantly.  */
+  node m_nil;
+
+  node *m_root = &m_nil;
+
+  friend class interval_tree_find_iterator<Interval, Traits>;
+};
+
+#endif /* GDBSUPPORT_INTERVAL_TREE_H */
-- 
2.35.3

Re: [PATCH 2/5] gdbsupport: Introduce interval_tree

[Pedro Alves]

On 2022-06-02 14:35, Ilya Leoshkevich wrote:
> 
> Adding N JITed sections has the complexity O((N**2)*log(N)), because
> adding each section involves breakpoint handling, which needs to
> resolve PCs and thus calls update_section_map().  When N is around 10k,
> this renders GDB unusable.

Does this adding of N JITed sections happen in batch?  Like, is this from
jit_inferior_init, where we loop over JIT objects?  Or is it so that we
get notified about JIT objects, one at a time?

In places where we add symbols in batch, we defer breakpoint re_setting exactly
to avoid problems like this, via SYMFILE_DEFER_BP_RESET or something similar.
Looks like jit.c doesn't try to do that.  Or is it not possible in the scenario
in question?  Like, doesn't the JIT API let you register more than one object
file at once?

Re: [PATCH 2/5] gdbsupport: Introduce interval_tree

[Ilya Leoshkevich]

On Thu, 2022-06-02 at 15:12 +0100, Pedro Alves wrote:
> On 2022-06-02 14:35, Ilya Leoshkevich wrote:
> > 
> > Adding N JITed sections has the complexity O((N**2)*log(N)),
> > because
> > adding each section involves breakpoint handling, which needs to
> > resolve PCs and thus calls update_section_map().  When N is around
> > 10k,
> > this renders GDB unusable.
> 
> Does this adding of N JITed sections happen in batch?  Like, is this
> from
> jit_inferior_init, where we loop over JIT objects?  Or is it so that
> we
> get notified about JIT objects, one at a time?
> 
> In places where we add symbols in batch, we defer breakpoint
> re_setting exactly
> to avoid problems like this, via SYMFILE_DEFER_BP_RESET or something
> similar.
> Looks like jit.c doesn't try to do that.  Or is it not possible in
> the scenario
> in question?  Like, doesn't the JIT API let you register more than
> one object
> file at once?

In the scenario I'm running into, GDB is notified about them one by
one.  I don't think there is a batch API ([1] doesn't mention anything
like this), but even if there were, it wouldn't help in the general
case, because the decisions to JIT individual methods may be split in
time.

[1]
https://sourceware.org/gdb/onlinedocs/gdb/Registering-Code.html#Registering-Code

Re: [PATCH 2/5] gdbsupport: Introduce interval_tree

[Pedro Alves]

On 2022-06-02 14:35, Ilya Leoshkevich wrote:
> 
> Adding N JITed sections has the complexity O((N**2)*log(N)), because
> adding each section involves breakpoint handling, which needs to
> resolve PCs and thus calls update_section_map().  When N is around 10k,
> this renders GDB unusable.

Does this adding of N JITed sections happen in batch?  Like, is this from
jit_inferior_init, where we loop over JIT objects?  Or is it so that we
get notified about JIT objects, one at a time?

In places where we add symbols in batch, we defer breakpoint re_setting exactly
to avoid problems like this, via SYMFILE_DEFER_BP_RESET or something similar.
Looks like jit.c doesn't try to do that.  Or is it not possible in the scenario
in question?  Like, doesn't the JIT API let you register more than one object
file at once?

Re: [PATCH 2/5] gdbsupport: Introduce interval_tree

[Pedro Alves]

On 2022-06-02 15:12, Pedro Alves wrote:
> On 2022-06-02 14:35, Ilya Leoshkevich wrote:
>>
>> Adding N JITed sections has the complexity O((N**2)*log(N)), because
>> adding each section involves breakpoint handling, which needs to
>> resolve PCs and thus calls update_section_map().  When N is around 10k,
>> this renders GDB unusable.
> 
> Does this adding of N JITed sections happen in batch?  Like, is this from
> jit_inferior_init, where we loop over JIT objects?  Or is it so that we
> get notified about JIT objects, one at a time?
> 
> In places where we add symbols in batch, we defer breakpoint re_setting exactly
> to avoid problems like this, via SYMFILE_DEFER_BP_RESET or something similar.
> Looks like jit.c doesn't try to do that.  Or is it not possible in the scenario
> in question?  Like, doesn't the JIT API let you register more than one object
> file at once?

It has taken me this long to remember that I once wrote a patch series to
tackle this problem...  :-)  It's been on a branch on sourceware since 2016...

See the palves/jit-speedup branch.

I completely forgot that.

There, I added a number of patches deferring breakpoint_re_set in several
different situations, and other simple optimizations that avoid O(N).
It may be those patches are obsolete by now, but maybe they aren't.

For the section sorting issue itself, the branch has this:

~~~~~~~~~~~~~~~~~~
commit 5cd42e9fb13d25febe3da26595d044a57150cee5
Author:     Pedro Alves <palves@redhat.com>
AuthorDate: Fri Apr 1 01:14:30 2016 +0100
Commit:     Pedro Alves <palves@redhat.com>
CommitDate: Mon Sep 19 15:44:41 2016 +0100

    Get rid of sections sorting with qsort and use an incrementally updated addrmap instead
    
    This gives a massive speed up.  The problem with the qsort is that we
    qsort for any one of the thousands of jit loads/unloads, and when you
    have thousands of objfiles, that gets very slow.  In this scenario,
    we're constantly adding/removing a handfull of obj_sections to a set
    of thousands of already-sorted obj_sections.  It's much cheaper to do
    an incremental update.
    
    I'm using a mutable addrmap for this, but I needed to add a new
    primitive that allowed updating a region's object, to handle the case
    of overlapping sections.  The only primitive available, only allows
    setting a value to a currently-NULL region.

~~~~~~~~~~~~~~~~~~

it talks about qsort because back when we hadn't yet moved to C++ std::sort.

As you see, I was using an addrmap for this (gdb/addrmap.h), which is a data structure
we already have.  I wonder whether the new data structure is really needed.  That's
a question I was going to raise anyhow, until I remembered I had once already attempted it
(and seen that it works).

Re: [PATCH 2/5] gdbsupport: Introduce interval_tree

[Ilya Leoshkevich]

On Thu, 2022-06-02 at 15:37 +0100, Pedro Alves wrote:
> On 2022-06-02 15:12, Pedro Alves wrote:
> > On 2022-06-02 14:35, Ilya Leoshkevich wrote:
> > > 
> > > Adding N JITed sections has the complexity O((N**2)*log(N)),
> > > because
> > > adding each section involves breakpoint handling, which needs to
> > > resolve PCs and thus calls update_section_map().  When N is
> > > around 10k,
> > > this renders GDB unusable.
> > 
> > Does this adding of N JITed sections happen in batch?  Like, is
> > this from
> > jit_inferior_init, where we loop over JIT objects?  Or is it so
> > that we
> > get notified about JIT objects, one at a time?
> > 
> > In places where we add symbols in batch, we defer breakpoint
> > re_setting exactly
> > to avoid problems like this, via SYMFILE_DEFER_BP_RESET or
> > something similar.
> > Looks like jit.c doesn't try to do that.  Or is it not possible in
> > the scenario
> > in question?  Like, doesn't the JIT API let you register more than
> > one object
> > file at once?
> 
> It has taken me this long to remember that I once wrote a patch
> series to
> tackle this problem...  :-)  It's been on a branch on sourceware
> since 2016...
> 
> See the palves/jit-speedup branch.
> 
> I completely forgot that.
> 
> There, I added a number of patches deferring breakpoint_re_set in
> several
> different situations, and other simple optimizations that avoid O(N).
> It may be those patches are obsolete by now, but maybe they aren't.
> 
> For the section sorting issue itself, the branch has this:
> 
> ~~~~~~~~~~~~~~~~~~
> commit 5cd42e9fb13d25febe3da26595d044a57150cee5
> Author:     Pedro Alves <palves@redhat.com>
> AuthorDate: Fri Apr 1 01:14:30 2016 +0100
> Commit:     Pedro Alves <palves@redhat.com>
> CommitDate: Mon Sep 19 15:44:41 2016 +0100
> 
>     Get rid of sections sorting with qsort and use an incrementally
> updated addrmap instead
>     
>     This gives a massive speed up.  The problem with the qsort is
> that we
>     qsort for any one of the thousands of jit loads/unloads, and when
> you
>     have thousands of objfiles, that gets very slow.  In this
> scenario,
>     we're constantly adding/removing a handfull of obj_sections to a
> set
>     of thousands of already-sorted obj_sections.  It's much cheaper
> to do
>     an incremental update.
>     
>     I'm using a mutable addrmap for this, but I needed to add a new
>     primitive that allowed updating a region's object, to handle the
> case
>     of overlapping sections.  The only primitive available, only
> allows
>     setting a value to a currently-NULL region.
> 
> ~~~~~~~~~~~~~~~~~~
> 
> it talks about qsort because back when we hadn't yet moved to C++
> std::sort.
> 
> As you see, I was using an addrmap for this (gdb/addrmap.h), which is
> a data structure
> we already have.  I wonder whether the new data structure is really
> needed.  That's
> a question I was going to raise anyhow, until I remembered I had once
> already attempted it
> (and seen that it works).

Ah, interesting - I wasn't aware of addrmap.

You even handle overlapping sections conservatively by associating more
than one with each address range:

struct obj_section_map_addrmap_value
{
  VEC (obj_section_p) *sections;
};

This may use excessive memory if we have sections like [0,0], [0,1],
[0,2], ..., but hopefully that's not something that happens in the
real life often.

It's also interesting that you drop section_map_dirty and just apply
the changes right away.  I wasn't sure whether delaying the processing
was needed for something other than performance, so I kept it.  Same
for inhibit_updates.

I will try to play with addrmap and see if it works for me.

Re: [PATCH 2/5] gdbsupport: Introduce interval_tree

[Tom Tromey]

>>>>> "Pedro" == Pedro Alves <pedro@palves.net> writes:

Pedro> As you see, I was using an addrmap for this (gdb/addrmap.h),
Pedro> which is a data structure we already have.  I wonder whether the
Pedro> new data structure is really needed.  That's a question I was
Pedro> going to raise anyhow, until I remembered I had once already
Pedro> attempted it (and seen that it works).

I was going to ask this as well, though it's worth noting that addrmap
isn't really general purpose in that the ranges have to be CORE_ADDR,
and also you can't remove entries.  The former is something I hacked
around in the new DWARF scanner -- where a real template class might be
cleaner.

Tom

[PATCH 3/5] gdbsupport: Add interval_tree unit tests

[Ilya Leoshkevich]

Test small corner cases as well as a large tree.
---
 gdb/Makefile.in                         |   1 +
 gdb/unittests/interval_tree-selftests.c | 263 ++++++++++++++++++++++++
 2 files changed, 264 insertions(+)
 create mode 100644 gdb/unittests/interval_tree-selftests.c

diff --git a/gdb/Makefile.in b/gdb/Makefile.in
index d80087749de..8d848add1e3 100644
--- a/gdb/Makefile.in
+++ b/gdb/Makefile.in
@@ -456,6 +456,7 @@ SELFTESTS_SRCS = \
 	unittests/function-view-selftests.c \
 	unittests/gdb_tilde_expand-selftests.c \
 	unittests/gmp-utils-selftests.c \
+	unittests/interval_tree-selftests.c \
 	unittests/intrusive_list-selftests.c \
 	unittests/lookup_name_info-selftests.c \
 	unittests/memory-map-selftests.c \
diff --git a/gdb/unittests/interval_tree-selftests.c b/gdb/unittests/interval_tree-selftests.c
new file mode 100644
index 00000000000..98a3f4c15bd
--- /dev/null
+++ b/gdb/unittests/interval_tree-selftests.c
@@ -0,0 +1,263 @@
+/* Tests interval tree for GDB, the GNU debugger.
+   Copyright (C) 2022 Free Software Foundation, Inc.
+
+   This file is part of GDB.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#include "defs.h"
+
+#include "gdbsupport/selftest.h"
+#include <iostream>
+#include <set>
+#include <sstream>
+
+#include "gdbsupport/interval_tree.h"
+
+/* A test type for storing in an interval tree.  Interval tree must be able to
+   handle types without a default constructor, nonmoveable types, and
+   noncopyable types.  */
+
+struct test_interval
+{
+  test_interval (int low, int high) : low (low), high (high) {}
+
+  test_interval () = delete;
+  test_interval (const test_interval &) = delete;
+  test_interval &operator= (const test_interval &) = delete;
+  test_interval (test_interval &&) = delete;
+  test_interval &operator= (test_interval &&) = delete;
+
+  typedef int endpoint_type;
+  const int low;
+  const int high;
+};
+
+/* An expected ordering within an interval tree.  */
+
+struct cmp_test_interval
+{
+  bool
+  operator() (const test_interval &lhs, const test_interval &rhs) const
+  {
+    if (lhs.low != rhs.low)
+      return lhs.low < rhs.low;
+    return lhs.high < rhs.high;
+  }
+};
+
+/* Insert an interval into a tree and verify its integrity.  */
+
+static interval_tree<test_interval>::iterator
+check_emplace (interval_tree<test_interval> &t, int low, int high)
+{
+  auto it = t.emplace (low, high);
+  std::ostringstream () << t;
+  return it;
+}
+
+/* Check that iterator range has specific content.  */
+
+template <typename Iterator, typename EndIterator>
+static void
+check_iterator (Iterator it, EndIterator end)
+{
+  gdb_assert (it == end);
+}
+
+template <typename Iterator, typename EndIterator, typename... Args>
+static void
+check_iterator (Iterator it, EndIterator end, int low, int high,
+		Args &&...args)
+{
+  gdb_assert (it != end);
+  gdb_assert (it->low == low && it->high == high);
+  ++it;
+  check_iterator (it, end, std::forward<Args> (args)...);
+}
+
+/* Remove an interval from a tree and verify its integrity.  */
+
+static void
+check_erase (interval_tree<test_interval> &t,
+	     interval_tree<test_interval>::iterator it)
+{
+  t.erase (it);
+  std::ostringstream () << t;
+}
+
+/* Small tests for various corner cases.  */
+
+static void
+test_interval_tree_1 ()
+{
+  interval_tree<test_interval> t;
+  check_iterator (t.find (0, 1), t.end ());
+  auto it0 = check_emplace (t, 0, 1);
+  check_iterator (t.find (0, 1), t.end (), 0, 1);
+  check_erase (t, it0);
+  check_iterator (t.find (0, 1), t.end ());
+}
+
+static void
+test_interval_tree_2 ()
+{
+  interval_tree<test_interval> t;
+  check_emplace (t, -16119041, -1);
+  check_emplace (t, -1, 184549375);
+  check_emplace (t, 0, 0);
+  check_iterator (t.find (0, 0), t.end (), -1, 184549375, 0, 0);
+}
+
+static void
+test_interval_tree_3 ()
+{
+  interval_tree<test_interval> t;
+  check_emplace (t, 0, 65536);
+  check_emplace (t, -1978987776, 10);
+  check_iterator (t.find (0, 239), t.end (), -1978987776, 10, 0, 65536);
+}
+
+static void
+test_interval_tree_4 ()
+{
+  interval_tree<test_interval> t;
+  check_emplace (t, 0, 59);
+  check_emplace (t, 0, 0);
+  check_iterator (t.find (0, 0), t.end (), 0, 0, 0, 59);
+}
+
+static void
+test_interval_tree_5 ()
+{
+  interval_tree<test_interval> t;
+  check_emplace (t, -16777216, -16711936);
+  check_emplace (t, 0, 0);
+}
+
+static void
+test_interval_tree_6 ()
+{
+  interval_tree<test_interval> t;
+  check_emplace (t, -167772160, -33554186);
+  check_emplace (t, -16908034, -16712192);
+  check_emplace (t, -1, -1);
+  check_emplace (t, 0, 0);
+}
+
+static void
+test_interval_tree_7 ()
+{
+  interval_tree<test_interval> t;
+  check_emplace (t, 621897471, 983770623);
+  check_emplace (t, 0, 0);
+  check_emplace (t, 0, 0);
+  check_emplace (t, 0, 8061696);
+  check_iterator (t.find (0, 0), t.end (), 0, 0, 0, 0, 0, 8061696);
+}
+
+static void
+test_interval_tree_8 ()
+{
+  interval_tree<test_interval> t;
+  auto it0 = check_emplace (t, 1795875964, 1796149007);
+  check_emplace (t, 3855, 252371968);
+  check_erase (t, it0);
+}
+
+static void
+test_interval_tree_9 ()
+{
+  interval_tree<test_interval> t;
+  check_emplace (t, 0, 0);
+  auto it1 = check_emplace (t, -603979523, 853292838);
+  check_erase (t, it1);
+}
+
+static void
+test_interval_tree_10 ()
+{
+  interval_tree<test_interval> t;
+  auto it0 = check_emplace (t, 0, 6);
+  check_emplace (t, -65527, 65280);
+  check_emplace (t, 5636352, 26411009);
+  check_erase (t, it0);
+}
+
+static void
+test_interval_tree_11 ()
+{
+  interval_tree<test_interval> t;
+  auto it0 = check_emplace (t, 62652437, 454794924);
+  check_emplace (t, -188, 1145351340);
+  check_emplace (t, 352332868, 1140916191);
+  check_erase (t, it0);
+}
+
+static void
+test_interval_tree_12 ()
+{
+  interval_tree<test_interval> t;
+  auto it0 = check_emplace (t, -366592, 1389189);
+  auto it1 = check_emplace (t, 16128, 29702);
+  check_emplace (t, 2713716, 1946157056);
+  check_emplace (t, 393215, 1962868736);
+  check_erase (t, it0);
+  check_emplace (t, 2560, 4128768);
+  check_emplace (t, 0, 4128768);
+  check_emplace (t, 0, 125042688);
+  check_erase (t, it1);
+}
+
+/* Performance test: add and lookup 1M intervals.  */
+
+static void
+test_interval_tree_perf ()
+{
+  interval_tree<test_interval> t;
+  const int count = 1000000;
+  for (int i = 0; i < count; i++)
+    t.emplace (i * 5, i * 5 + 5);
+  std::ostringstream () << t;
+  for (int i = 1; i < count; i++)
+    check_iterator (t.find (i * 5 - 2, i * 5 + 2), t.end (), i * 5 - 5, i * 5,
+		    i * 5, i * 5 + 5);
+}
+
+/* Test registration.  */
+
+static void
+test_interval_tree ()
+{
+  test_interval_tree_1 ();
+  test_interval_tree_2 ();
+  test_interval_tree_3 ();
+  test_interval_tree_4 ();
+  test_interval_tree_5 ();
+  test_interval_tree_6 ();
+  test_interval_tree_7 ();
+  test_interval_tree_8 ();
+  test_interval_tree_9 ();
+  test_interval_tree_10 ();
+  test_interval_tree_11 ();
+  test_interval_tree_12 ();
+  test_interval_tree_perf ();
+}
+
+void _initialize_interval_tree_selftests ();
+void
+_initialize_interval_tree_selftests ()
+{
+  selftests::register_test ("interval_tree", test_interval_tree);
+}
-- 
2.35.3

[PATCH 4/5] gdbsupport: Add interval_tree fuzzing harness

[Ilya Leoshkevich]

Add a libFuzzer harness that exercises additions, removals and lookups.
---
 gdb/unittests/interval_tree-selftests.c | 137 ++++++++++++++++++++++++
 1 file changed, 137 insertions(+)

diff --git a/gdb/unittests/interval_tree-selftests.c b/gdb/unittests/interval_tree-selftests.c
index 98a3f4c15bd..85cf376bbd0 100644
--- a/gdb/unittests/interval_tree-selftests.c
+++ b/gdb/unittests/interval_tree-selftests.c
@@ -23,6 +23,12 @@
 #include <set>
 #include <sstream>
 
+#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
+#include <assert.h>
+#undef gdb_assert
+#define gdb_assert assert
+#endif
+
 #include "gdbsupport/interval_tree.h"
 
 /* A test type for storing in an interval tree.  Interval tree must be able to
@@ -259,5 +265,136 @@ void _initialize_interval_tree_selftests ();
 void
 _initialize_interval_tree_selftests ()
 {
+#ifndef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
   selftests::register_test ("interval_tree", test_interval_tree);
+#endif
+}
+
+/* Fuzzing harness.  */
+
+class FuzzerInput
+{
+public:
+  FuzzerInput (const unsigned char *data, size_t size)
+      : m_data (data), m_size (size)
+  {
+  }
+
+  bool
+  end () const
+  {
+    return m_size == 0;
+  }
+
+  template <typename T>
+  T
+  get ()
+  {
+    T result = 0;
+    for (size_t i = 0; i < sizeof (T); i++)
+      result |= read_byte () << (i * 8);
+    return result;
+  }
+
+private:
+  unsigned char
+  read_byte ()
+  {
+    if (end ())
+      return 0;
+    m_data++;
+    m_size--;
+    return m_data[-1];
+  }
+
+  const unsigned char *m_data;
+  size_t m_size;
+};
+
+extern "C" int LLVMFuzzerTestOneInput (const unsigned char *, size_t);
+extern "C" int
+LLVMFuzzerTestOneInput (const unsigned char *data, size_t size)
+{
+  FuzzerInput input (data, size);
+  interval_tree<test_interval> t;
+  std::vector<std::pair<decltype (t)::iterator, size_t> > t_iterators;
+  std::multiset<test_interval, cmp_test_interval> exp;
+  std::vector<decltype (exp)::iterator> exp_iterators;
+  size_t add_counter = 0;
+
+  static const char *debug_str = getenv ("DEBUG");
+  static int debug = debug_str == nullptr ? 0 : atoi (debug_str);
+
+  while (!input.end ())
+    {
+      switch (input.get<char> () % 3)
+	{
+	case 0:
+	  {
+	    /* Add.  */
+	    int low = input.get<int> (), high = input.get<int> ();
+	    if (low > high)
+	      std::swap (low, high);
+	    if (debug)
+	      std::cout << "auto it" << add_counter << " = check_emplace (t, "
+			<< low << ", " << high << ");" << std::endl;
+	    t_iterators.push_back (
+		std::make_pair (t.emplace (low, high), add_counter));
+	    if (debug)
+	      std::cout << "/*\n" << t << "*/" << std::endl;
+	    else
+	      std::ostringstream () << t;
+	    exp_iterators.push_back (exp.emplace (low, high));
+	    add_counter += 1;
+	    break;
+	  }
+	case 1:
+	  {
+	    /* Find.  */
+	    int low = input.get<int> (), high = input.get<int> ();
+	    if (low > high)
+	      std::swap (low, high);
+	    if (debug)
+	      std::cout << "check_iterator (t.find (" << low << ", " << high
+			<< "), t.end ()" << std::flush;
+	    auto it = t.find (low, high);
+	    for (const test_interval &exp_interval : exp)
+	      {
+		if (high < exp_interval.low || low > exp_interval.high)
+		  continue;
+		if (debug)
+		  std::cout << ", " << exp_interval.low << ", "
+			    << exp_interval.high << std::flush;
+		gdb_assert (it->low == exp_interval.low
+			    && it->high == exp_interval.high);
+		++it;
+	      }
+	    if (debug)
+	      std::cout << ");" << std::endl;
+	    gdb_assert (it == t.end ());
+	    break;
+	  }
+	case 2:
+	  {
+	    /* Remove.  */
+	    if (!t_iterators.empty ())
+	      {
+		int index = input.get<int> () % t_iterators.size ();
+		if (debug)
+		  std::cout << "check_erase (t, it"
+			    << t_iterators[index].second << ");" << std::endl;
+		t.erase (t_iterators[index].first);
+		t_iterators.erase (t_iterators.begin () + index);
+		exp.erase (exp_iterators[index]);
+		exp_iterators.erase (exp_iterators.begin () + index);
+                if (debug)
+                  std::cout << "/*\n" << t << "*/" << std::endl;
+                else
+                  std::ostringstream () << t;
+	      }
+	    break;
+	  }
+	}
+    }
+  return 0;
 }
-- 
2.35.3

[PATCH 5/5] gdb: Optimize section map

[Ilya Leoshkevich]

Store section map in an interval_tree.

Do not store sections themselves there, since this would require making
updates on section removal, which the code currently does not have to
do.  Rather, introduce section_map_entry objects and link them with
sections.  Then, manage lazy updates by putting both section and
section_map_entry objects into TODO intrusive lists.  Replace almost
all usages of section_map_dirty with adding to or removing from these
lists.

Since intrusive lists are non-POD types, use obstack_newvec instead of
OBSTACK_CALLOC in order to allocate sections, and also call their
destructors manually.

Keep filtering debuginfo and overlapping sections, but do that on
lookup rather than on insertion.  The reason is that we want to keep
them in case one of the two overlapping sections goes away.
---
 gdb/objfiles.c | 384 ++++++++++++++++++++++---------------------------
 gdb/objfiles.h |  15 +-
 gdb/symfile.c  |   2 +-
 3 files changed, 184 insertions(+), 217 deletions(-)

diff --git a/gdb/objfiles.c b/gdb/objfiles.c
index 4fc859f185a..74e2c290a23 100644
--- a/gdb/objfiles.c
+++ b/gdb/objfiles.c
@@ -53,6 +53,7 @@
 #include "gdb_bfd.h"
 #include "btrace.h"
 #include "gdbsupport/pathstuff.h"
+#include "gdbsupport/interval_tree.h"
 
 #include <algorithm>
 #include <vector>
@@ -62,20 +63,56 @@
 
 DEFINE_REGISTRY (objfile, REGISTRY_ACCESS_FIELD)
 
+/* Section map is an interval tree containing sections from all objfiles -
+   including the overlapping ones.  It is updated lazily: the updates are
+   queued in sections_to_add and sections_to_remove intrusive lists, and are
+   applied only when the section map is actually needed.  */
+
+struct section_map_entry
+{
+  explicit section_map_entry (obj_section *section)
+      : section (section), low (section->addr ()),
+	high (section->endaddr () - 1)
+  {
+    gdb_assert (section->section_map_entry == nullptr);
+    section->section_map_entry = this;
+  }
+
+  section_map_entry (const section_map_entry &) = delete;
+  section_map_entry &operator= (const section_map_entry &) = delete;
+  section_map_entry (section_map_entry &&) = delete;
+  section_map_entry &operator= (section_map_entry &&) = delete;
+
+  /* The corresponding section.  */
+  obj_section *section;
+
+  /* For embedding into interval_tree.  */
+  typedef CORE_ADDR endpoint_type;
+  const CORE_ADDR low;
+  const CORE_ADDR high;
+
+  /* Sections that need to be removed from the section map.  */
+  intrusive_list_node<section_map_entry> sections_to_remove;
+};
+
 /* Externally visible variables that are owned by this module.
    See declarations in objfile.h for more info.  */
 
 struct objfile_pspace_info
 {
-  objfile_pspace_info () = default;
-  ~objfile_pspace_info ();
+  interval_tree<section_map_entry> sections;
 
-  struct obj_section **sections = nullptr;
-  int num_sections = 0;
+  /* Sections that need to be added to the section map.  */
+  intrusive_list<obj_section, intrusive_member_node<
+				  obj_section, &obj_section::sections_to_add> >
+      sections_to_add;
 
-  /* Nonzero if object files have been added since the section map
-     was last updated.  */
-  int new_objfiles_available = 0;
+  /* Sections that need to be removed from the section map.  */
+  intrusive_list<
+      section_map_entry,
+      intrusive_member_node<section_map_entry,
+			    &section_map_entry::sections_to_remove> >
+      sections_to_remove;
 
   /* Nonzero if the section map MUST be updated before use.  */
   int section_map_dirty = 0;
@@ -88,11 +125,6 @@ struct objfile_pspace_info
 static const struct program_space_key<objfile_pspace_info>
   objfiles_pspace_data;
 
-objfile_pspace_info::~objfile_pspace_info ()
-{
-  xfree (sections);
-}
-
 /* Get the current svr4 data.  If none is found yet, add it now.  This
    function always returns a valid object.  */
 
@@ -291,9 +323,8 @@ build_objfile_section_table (struct objfile *objfile)
 {
   int count = gdb_bfd_count_sections (objfile->obfd);
 
-  objfile->sections = OBSTACK_CALLOC (&objfile->objfile_obstack,
-				      count,
-				      struct obj_section);
+  objfile->sections
+      = obstack_newvec<struct obj_section> (&objfile->objfile_obstack, count);
   objfile->sections_end = (objfile->sections + count);
   for (asection *sect : gdb_bfd_sections (objfile->obfd))
     add_to_objfile_sections (objfile->obfd, sect, objfile, 0);
@@ -471,8 +502,11 @@ objfile::make (bfd *bfd_, const char *name_, objfile_flags flags_,
   current_program_space->add_objfile (std::unique_ptr<objfile> (result),
 				      parent);
 
-  /* Rebuild section map next time we need it.  */
-  get_objfile_pspace_data (current_program_space)->new_objfiles_available = 1;
+  /* Update section map next time we need it.  */
+  objfile_pspace_info *pspace_info = get_objfile_pspace_data (result->pspace);
+  obj_section *s;
+  ALL_OBJFILE_OSECTIONS (result, s)
+    pspace_info->sections_to_add.push_back (*s);
 
   return result;
 }
@@ -501,6 +535,38 @@ free_objfile_separate_debug (struct objfile *objfile)
     }
 }
 
+/* Schedule removal of all OBJFILE's sections, and call their destructors.  */
+
+void
+objfile_destroy_sections (objfile *objfile)
+{
+  objfile_pspace_info *info = objfiles_pspace_data.get (objfile->pspace);
+  obj_section *s;
+
+  ALL_OBJFILE_OSECTIONS (objfile, s)
+    {
+      if (info != nullptr)
+	{
+	  if (s->sections_to_add.is_linked ())
+	    info->sections_to_add.erase (
+		decltype (info->sections_to_add)::iterator (s));
+
+	  if (s->section_map_entry != nullptr)
+	    {
+	      gdb_assert (s->section_map_entry->section == s);
+	      s->section_map_entry->section = nullptr;
+	      if (!s->section_map_entry->sections_to_remove.is_linked ())
+		info->sections_to_remove.push_back (*s->section_map_entry);
+	    }
+	}
+
+      s->~obj_section ();
+    }
+
+  objfile->sections = NULL;
+  objfile->sections_end = NULL;
+}
+
 /* Destroy an objfile and all the symtabs and psymtabs under it.  */
 
 objfile::~objfile ()
@@ -593,11 +659,10 @@ objfile::~objfile ()
       clear_current_source_symtab_and_line ();
   }
 
+  objfile_destroy_sections (this);
+
   /* Free the obstacks for non-reusable objfiles.  */
   obstack_free (&objfile_obstack, 0);
-
-  /* Rebuild section map next time we need it.  */
-  get_objfile_pspace_data (pspace)->section_map_dirty = 1;
 }
 
 \f
@@ -711,15 +776,20 @@ objfile_relocate1 (struct objfile *objfile,
       objfile->section_offsets[i] = new_offsets[i];
   }
 
-  /* Rebuild section map next time we need it.  */
-  get_objfile_pspace_data (objfile->pspace)->section_map_dirty = 1;
-
-  /* Update the table in exec_ops, used to read memory.  */
-  struct obj_section *s;
+  /* Update section map next time we need it.
+     Update the table in exec_ops, used to read memory.  */
+  objfile_pspace_info *pspace_info
+      = get_objfile_pspace_data (current_program_space);
+  obj_section *s;
   ALL_OBJFILE_OSECTIONS (objfile, s)
     {
       int idx = s - objfile->sections;
 
+      if (s->section_map_entry != nullptr
+	  && !s->section_map_entry->sections_to_remove.is_linked ())
+	pspace_info->sections_to_remove.push_back (*s->section_map_entry);
+      if (!s->sections_to_add.is_linked ())
+	pspace_info->sections_to_add.push_back (*s);
       exec_set_section_address (bfd_get_filename (objfile->obfd), idx,
 				s->addr ());
     }
@@ -1013,180 +1083,51 @@ insert_section_p (const struct bfd *abfd,
   return 1;
 }
 
-/* Filter out overlapping sections where one section came from the real
-   objfile, and the other from a separate debuginfo file.
-   Return the size of table after redundant sections have been eliminated.  */
-
-static int
-filter_debuginfo_sections (struct obj_section **map, int map_size)
-{
-  int i, j;
-
-  for (i = 0, j = 0; i < map_size - 1; i++)
-    {
-      struct obj_section *const sect1 = map[i];
-      struct obj_section *const sect2 = map[i + 1];
-      const struct objfile *const objfile1 = sect1->objfile;
-      const struct objfile *const objfile2 = sect2->objfile;
-      const CORE_ADDR sect1_addr = sect1->addr ();
-      const CORE_ADDR sect2_addr = sect2->addr ();
-
-      if (sect1_addr == sect2_addr
-	  && (objfile1->separate_debug_objfile == objfile2
-	      || objfile2->separate_debug_objfile == objfile1))
-	{
-	  map[j++] = preferred_obj_section (sect1, sect2);
-	  ++i;
-	}
-      else
-	map[j++] = sect1;
-    }
-
-  if (i < map_size)
-    {
-      gdb_assert (i == map_size - 1);
-      map[j++] = map[i];
-    }
-
-  /* The map should not have shrunk to less than half the original size.  */
-  gdb_assert (map_size / 2 <= j);
-
-  return j;
-}
-
-/* Filter out overlapping sections, issuing a warning if any are found.
-   Overlapping sections could really be overlay sections which we didn't
-   classify as such in insert_section_p, or we could be dealing with a
-   corrupt binary.  */
-
-static int
-filter_overlapping_sections (struct obj_section **map, int map_size)
-{
-  int i, j;
-
-  for (i = 0, j = 0; i < map_size - 1; )
-    {
-      int k;
-
-      map[j++] = map[i];
-      for (k = i + 1; k < map_size; k++)
-	{
-	  struct obj_section *const sect1 = map[i];
-	  struct obj_section *const sect2 = map[k];
-	  const CORE_ADDR sect1_addr = sect1->addr ();
-	  const CORE_ADDR sect2_addr = sect2->addr ();
-	  const CORE_ADDR sect1_endaddr = sect1->endaddr ();
-
-	  gdb_assert (sect1_addr <= sect2_addr);
-
-	  if (sect1_endaddr <= sect2_addr)
-	    break;
-	  else
-	    {
-	      /* We have an overlap.  Report it.  */
-
-	      struct objfile *const objf1 = sect1->objfile;
-	      struct objfile *const objf2 = sect2->objfile;
-
-	      const struct bfd_section *const bfds1 = sect1->the_bfd_section;
-	      const struct bfd_section *const bfds2 = sect2->the_bfd_section;
-
-	      const CORE_ADDR sect2_endaddr = sect2->endaddr ();
-
-	      struct gdbarch *const gdbarch = objf1->arch ();
-
-	      complaint (_("unexpected overlap between:\n"
-			   " (A) section `%s' from `%s' [%s, %s)\n"
-			   " (B) section `%s' from `%s' [%s, %s).\n"
-			   "Will ignore section B"),
-			 bfd_section_name (bfds1), objfile_name (objf1),
-			 paddress (gdbarch, sect1_addr),
-			 paddress (gdbarch, sect1_endaddr),
-			 bfd_section_name (bfds2), objfile_name (objf2),
-			 paddress (gdbarch, sect2_addr),
-			 paddress (gdbarch, sect2_endaddr));
-	    }
-	}
-      i = k;
-    }
-
-  if (i < map_size)
-    {
-      gdb_assert (i == map_size - 1);
-      map[j++] = map[i];
-    }
-
-  return j;
-}
-
-
 /* Update PMAP, PMAP_SIZE with sections from all objfiles, excluding any
    TLS, overlay and overlapping sections.  */
 
 static void
-update_section_map (struct program_space *pspace,
-		    struct obj_section ***pmap, int *pmap_size)
+update_section_map (program_space *pspace)
 {
-  struct objfile_pspace_info *pspace_info;
-  int alloc_size, map_size, i;
-  struct obj_section *s, **map;
+  objfile_pspace_info *pspace_info = get_objfile_pspace_data (pspace);
 
-  pspace_info = get_objfile_pspace_data (pspace);
   gdb_assert (pspace_info->section_map_dirty != 0
-	      || pspace_info->new_objfiles_available != 0);
+	      || !pspace_info->sections_to_add.empty ()
+	      || !pspace_info->sections_to_remove.empty ());
 
-  map = *pmap;
-  xfree (map);
-
-  alloc_size = 0;
-  for (objfile *objfile : pspace->objfiles ())
-    ALL_OBJFILE_OSECTIONS (objfile, s)
-      if (insert_section_p (objfile->obfd, s->the_bfd_section))
-	alloc_size += 1;
-
-  /* This happens on detach/attach (e.g. in gdb.base/attach.exp).  */
-  if (alloc_size == 0)
+  if (pspace_info->section_map_dirty)
     {
-      *pmap = NULL;
-      *pmap_size = 0;
-      return;
+      pspace_info->sections_to_remove.clear ();
+      pspace_info->sections_to_add.clear ();
+      pspace_info->sections.clear ();
+      pspace_info->section_map_dirty = 0;
+      obj_section *s;
+      for (objfile *objfile : pspace->objfiles ())
+	ALL_OBJFILE_OSECTIONS (objfile, s)
+	  if (insert_section_p (objfile->obfd, s->the_bfd_section))
+	    pspace_info->sections.emplace (s);
     }
-
-  map = XNEWVEC (struct obj_section *, alloc_size);
-
-  i = 0;
-  for (objfile *objfile : pspace->objfiles ())
-    ALL_OBJFILE_OSECTIONS (objfile, s)
-      if (insert_section_p (objfile->obfd, s->the_bfd_section))
-	map[i++] = s;
-
-  std::sort (map, map + alloc_size, sort_cmp);
-  map_size = filter_debuginfo_sections(map, alloc_size);
-  map_size = filter_overlapping_sections(map, map_size);
-
-  if (map_size < alloc_size)
-    /* Some sections were eliminated.  Trim excess space.  */
-    map = XRESIZEVEC (struct obj_section *, map, map_size);
   else
-    gdb_assert (alloc_size == map_size);
-
-  *pmap = map;
-  *pmap_size = map_size;
-}
-
-/* Bsearch comparison function.  */
-
-static int
-bsearch_cmp (const void *key, const void *elt)
-{
-  const CORE_ADDR pc = *(CORE_ADDR *) key;
-  const struct obj_section *section = *(const struct obj_section **) elt;
+    {
+      while (!pspace_info->sections_to_remove.empty ())
+	{
+	  section_map_entry *entry = &pspace_info->sections_to_remove.front ();
+	  pspace_info->sections_to_remove.pop_front ();
+	  auto it = interval_tree<section_map_entry>::iterator::from_interval (
+	      pspace_info->sections, entry);
+	  if (it->section != nullptr)
+	    it->section->section_map_entry = nullptr;
+	  pspace_info->sections.erase (it);
+	}
 
-  if (pc < section->addr ())
-    return -1;
-  if (pc < section->endaddr ())
-    return 0;
-  return 1;
+      for (; !pspace_info->sections_to_add.empty ();
+	   pspace_info->sections_to_add.pop_front ())
+	{
+	  obj_section *s = &pspace_info->sections_to_add.front ();
+	  if (insert_section_p (s->objfile->obfd, s->the_bfd_section))
+	    pspace_info->sections.emplace (s);
+	}
+    }
 }
 
 /* Returns a section whose range includes PC or NULL if none found.   */
@@ -1195,7 +1136,7 @@ struct obj_section *
 find_pc_section (CORE_ADDR pc)
 {
   struct objfile_pspace_info *pspace_info;
-  struct obj_section *s, **sp;
+  obj_section *s;
 
   /* Check for mapped overlay section first.  */
   s = find_pc_mapped_section (pc);
@@ -1204,38 +1145,55 @@ find_pc_section (CORE_ADDR pc)
 
   pspace_info = get_objfile_pspace_data (current_program_space);
   if (pspace_info->section_map_dirty
-      || (pspace_info->new_objfiles_available
+      || !pspace_info->sections_to_remove.empty ()
+      || (!pspace_info->sections_to_add.empty ()
 	  && !pspace_info->inhibit_updates))
-    {
-      update_section_map (current_program_space,
-			  &pspace_info->sections,
-			  &pspace_info->num_sections);
+    update_section_map (current_program_space);
 
-      /* Don't need updates to section map until objfiles are added,
-	 removed or relocated.  */
-      pspace_info->new_objfiles_available = 0;
-      pspace_info->section_map_dirty = 0;
-    }
-
-  /* The C standard (ISO/IEC 9899:TC2) requires the BASE argument to
-     bsearch be non-NULL.  */
-  if (pspace_info->sections == NULL)
+  for (auto it = pspace_info->sections.find (pc, pc);
+       it != pspace_info->sections.end (); ++it)
     {
-      gdb_assert (pspace_info->num_sections == 0);
-      return NULL;
+      if (s == nullptr)
+	{
+	  s = it->section;
+	  continue;
+	}
+      /* We have detected overlapping sections.  */
+      if (s->addr () == it->section->addr ()
+	  && (s->objfile->separate_debug_objfile == it->section->objfile
+	      || it->section->objfile->separate_debug_objfile == s->objfile))
+	{
+	  /* One section came from the real objfile, and the other from a
+	     separate debuginfo file.  */
+	  s = preferred_obj_section (s, it->section);
+	}
+      else
+	{
+	  /* Overlapping sections could really be overlay sections which we
+	     didn't classify as such in insert_section_p, or we could be
+	     dealing with a corrupt binary.  Report it.  */
+	  gdbarch *const gdbarch = s->objfile->arch ();
+
+	  complaint (_ ("unexpected overlap between:\n"
+			" (A) section `%s' from `%s' [%s, %s)\n"
+			" (B) section `%s' from `%s' [%s, %s).\n"
+			"Will ignore section B"),
+		     bfd_section_name (s->the_bfd_section),
+		     objfile_name (s->objfile), paddress (gdbarch, s->addr ()),
+		     paddress (gdbarch, s->endaddr ()),
+		     bfd_section_name (it->section->the_bfd_section),
+		     objfile_name (it->section->objfile),
+		     paddress (gdbarch, it->section->addr ()),
+		     paddress (gdbarch, it->section->endaddr ()));
+
+	  if (sort_cmp (it->section, s))
+	    s = it->section;
+	}
     }
 
-  sp = (struct obj_section **) bsearch (&pc,
-					pspace_info->sections,
-					pspace_info->num_sections,
-					sizeof (*pspace_info->sections),
-					bsearch_cmp);
-  if (sp != NULL)
-    return *sp;
-  return NULL;
+  return s;
 }
 
-
 /* Return non-zero if PC is in a section called NAME.  */
 
 int
diff --git a/gdb/objfiles.h b/gdb/objfiles.h
index a7098b46279..f33bbc8ee6d 100644
--- a/gdb/objfiles.h
+++ b/gdb/objfiles.h
@@ -39,6 +39,7 @@
 #include "jit.h"
 #include "quick-symbol.h"
 #include <forward_list>
+#include "gdbsupport/intrusive_list.h"
 
 struct htab;
 struct objfile_data;
@@ -828,13 +829,19 @@ struct obj_section
   }
 
   /* BFD section pointer */
-  struct bfd_section *the_bfd_section;
+  struct bfd_section *the_bfd_section = nullptr;
 
   /* Objfile this section is part of.  */
-  struct objfile *objfile;
+  struct objfile *objfile = nullptr;
 
   /* True if this "overlay section" is mapped into an "overlay region".  */
-  int ovly_mapped;
+  int ovly_mapped = 0;
+
+  /* The corresponding section map entry, if any.  */
+  struct section_map_entry *section_map_entry = nullptr;
+
+  /* Sections that need to be added to the section map.  */
+  intrusive_list_node<obj_section> sections_to_add;
 };
 
 /* Declarations for functions defined in objfiles.c */
@@ -847,6 +854,8 @@ extern void build_objfile_section_table (struct objfile *);
 
 extern void free_objfile_separate_debug (struct objfile *);
 
+extern void objfile_destroy_sections (objfile *objfile);
+
 extern void objfile_relocate (struct objfile *, const section_offsets &);
 extern void objfile_rebase (struct objfile *, CORE_ADDR);
 
diff --git a/gdb/symfile.c b/gdb/symfile.c
index 6f546f5b059..302b1ec5041 100644
--- a/gdb/symfile.c
+++ b/gdb/symfile.c
@@ -2525,8 +2525,8 @@ reread_symbols (int from_tty)
 
 	  /* NB: after this call to obstack_free, objfiles_changed
 	     will need to be called (see discussion below).  */
+	  objfile_destroy_sections (objfile);
 	  obstack_free (&objfile->objfile_obstack, 0);
-	  objfile->sections = NULL;
 	  objfile->section_offsets.clear ();
 	  objfile->sect_index_bss = -1;
 	  objfile->sect_index_data = -1;
-- 
2.35.3