[PATCH 00/11] Various thread lists optimizations

[Simon Marchi via Gdb-patches <gdb-patches@sourceware.org>]

This series contains various optimizations written after profiling
ROCm-GDB [1].  A typical ROCm program may have thousands of threads
(waves), so everything that iterates often on the whole thread list pops
up on the profile report.

Conceptually, the optimizations are:

 - maintain a ptid -> thread map in each inferior, to speed up the
   thread lookups per ptid with find_thread_ptid
 - make all_matching_threads_iterator a bit smarter, depending on the
   filter_ptid passed, it can avoid iterating on all threads.  When the
   filter_ptid points to a specific thread, it can use find_thread_ptid
   to directly find the thread of interest, which is fast thanks to the
   previous point
 - maintain a per-process-target list of threads that are resumed and
   have a pending event.  This helps speed up two hot path cases: when
   we check if we want to re-enable commit-resumed, and when we want to
   fetch a pending event.

Patches up to and including patch 6 are groundwork.  Notably, patch 2
(thanks to Pedro) adds an intrusive_list type, which allows using
intrusive linked lists in a very C++-y way without writing a ton of
boilerplate.  This list type is useful for the patch that maintains a
list of resumed threads with pending events, but we also converted the
per-inferior thread list, the inferior list and the thread
step-over-list to use it.  It helped iron out a few bugs and ensure the
list works well for our purposes.

When debugging a ROCm test program whose threads continuously hit a
condition breakpoint evaluation to false, the speedup observed with
ROCm-GDB is around 5x (a run takes about 30 seconds before and 6 seconds
after).

With x86-64 / Linux, it's less noticeable, because the time we spend in
syscalls to fetch events and resume threads still dominates.  Still,
when trying a program with 1000 threads hitting 100 times each a false
conditional breakpoint, it goes from ~20 seconds to ~16 seconds.  But I
don't really expect anything that noticeable in everyday use cases
though.

[1] https://github.com/ROCm-Developer-Tools/ROCgdb

Pedro Alves (2):
  gdb: introduce intrusive_list, make thread_info use it
  gdb: make inferior_list use intrusive_list

Simon Marchi (9):
  gdb: introduce iterator_range, remove next_adapter
  gdb: use intrusive list for step-over chain
  gdb: add setter / getter for thread_info resumed state
  gdb: make thread_info::suspend private, add getters / setters
  gdb: maintain per-process-target list of resumed threads with pending
    wait status
  gdb: optimize check for resumed threads with pending wait status in
    maybe_set_commit_resumed_all_targets
  gdb: optimize selection of resumed thread with pending event
  gdb: maintain ptid -> thread map, optimize find_thread_ptid
  gdb: optimize all_matching_threads_iterator

 gdb/Makefile.in                            |   1 +
 gdb/ada-tasks.c                            |   4 +-
 gdb/breakpoint.c                           |   7 +-
 gdb/breakpoint.h                           |  10 +-
 gdb/elf-none-tdep.c                        |   2 +-
 gdb/fbsd-tdep.c                            |   6 +-
 gdb/gcore.c                                |   4 +-
 gdb/gdb-gdb.py.in                          |  91 ++-
 gdb/gdb_bfd.h                              |   4 +-
 gdb/gdbthread.h                            | 192 ++++-
 gdb/infcmd.c                               |  33 +-
 gdb/inferior-iter.h                        |  94 +--
 gdb/inferior.c                             | 105 ++-
 gdb/inferior.h                             |  34 +-
 gdb/inflow.c                               |   2 +-
 gdb/infrun.c                               | 476 ++++++------
 gdb/infrun.h                               |   4 +-
 gdb/linux-fork.c                           |   3 +-
 gdb/linux-nat.c                            |  12 +-
 gdb/linux-tdep.c                           |   2 +-
 gdb/objfiles.h                             |   6 +-
 gdb/process-stratum-target.c               |  77 ++
 gdb/process-stratum-target.h               |  26 +
 gdb/progspace.c                            |  11 +-
 gdb/progspace.h                            |  45 +-
 gdb/psymtab.h                              |   2 +-
 gdb/python/py-inferior.c                   |   2 +-
 gdb/record-btrace.c                        |   3 +-
 gdb/record-full.c                          |   3 +-
 gdb/regcache.c                             |   6 +-
 gdb/remote.c                               |  68 +-
 gdb/scoped-mock-context.h                  |  15 +-
 gdb/solist.h                               |   2 +
 gdb/symtab.h                               |  15 +-
 gdb/thread-iter.c                          | 147 +++-
 gdb/thread-iter.h                          |  61 +-
 gdb/thread.c                               | 216 +++---
 gdb/top.h                                  |   6 +-
 gdb/unittests/intrusive_list-selftests.c   | 818 +++++++++++++++++++++
 gdbsupport/intrusive_list.h                | 586 +++++++++++++++
 gdbsupport/iterator-range.h                |  60 ++
 gdbsupport/next-iterator.h                 |  32 +-
 gdbsupport/reference-to-pointer-iterator.h |  82 +++
 43 files changed, 2574 insertions(+), 801 deletions(-)
 create mode 100644 gdb/unittests/intrusive_list-selftests.c
 create mode 100644 gdbsupport/intrusive_list.h
 create mode 100644 gdbsupport/iterator-range.h
 create mode 100644 gdbsupport/reference-to-pointer-iterator.h

-- 
2.32.0