[DTrace-devel] [PATCH REVIEW v2 00/11] hashtab cleanups and corresponding speedups

[Nick Alcock]

This series dumps a bunch of handrolled hash tables in favour of the
expanding dt_htab (though some handrolled hashtabs are still there: these
are mostly the easy ones).  All these hash tables are the same size,
_dtrace_strbuckets, i.e. 211 buckets: given that many of them store many
thousands of entries, this was not good for performance.

The symbol lookup machinery had worse performance problems: we were doing
linear searches over modules and hashtab lookups (in horribly mis-sized hash
tables) in each one, and because of the way fbt population works we were
doing this tens of thousands of times per dtrace invocation.  Fixing this to
do a single htab lookup per name lookup speeds things up really quite a lot
(DTrace startup time drops by about 66%, and make check runtime falls by
15--20 minutes). Plus the code is *much* easier to follow.

We throw out a lot of symtab-specific complexity: purging of duplicate
symbols (which was necessary because they'd disrupt the hash table, even
though they were very rare and doing the duplicate elimination was quite
expensive), separate tracking of names for packed and nonpacked symtabs
(adding complexity to every lookup for the sake of saving *one line* in
the symtab packing code), and more.

To make way for this we throw out some facilities that have never been used
in any kernel new enough to support BPF DTrace: support for built-in kernel
module CTF and the shared CTF repo linked into a fake ctf.ko module rather
than stored in a separate .ctfa file, and the ctf_module_dump program which
tracked down in-tree module CTF and dumped it, using a program in
libdtrace-ctf; objdump --ctf does a perfectly good job nowadays.

We augment the hashtable machinery, making dt_htab_destroy call _del on
every allocated element, so you can destroy a nonempty htab without leaking
memory or leaving any wild interior pointers, and use _del to delete htab
entries everywhere we can (everywhere other than dt_module), rather than
dragging round lists everywhere just to keep track of what we've allocated
just so we can store it in hash tables. dt_module can't do this since it is
ordering-dependent: in future, we might add ordered htabs, but in the
absence of those, it still drags a list around with it.

Since some of these lists are used to iterate over and clean up hash tables
by code that doesn't care about the iteration order, we add a _next-style
iterator (see <https://sourceware.org/git/?p=binutils-gdb.git;a=commit;h=688d28f62146bf07b2ce1efd5380768d5ead418d>
for the general idea) to iterate over all members of a hash table in bucket
order, and a new dt_htab_next_del function that deletes the item the
iterator is currently pointing at without invalidating the iterator.

Thanks to Eugene Loh for a seriously useful review, without which none of
this would have been possible.

Changes since v1:
 - dropped .xz-compressed modules: upstreamed
 - rebased on latest dev
 - drop dt_htab_insert_unique
 - add ctf_module_dump removal and linked-in .ko module removal
 - add dt_htab_entries and dt_htab_next*: adjust ops vectors accordingly;
   fix minor bug in dt_htab_stats in the process
 - arrange to delete all buckets and call _del ops on all live entries
   on hashtab deletion, making _del a proper destructor; drop
   dt_htab_purge now we are doing this properly
 - use destructors wherever possible rather than keeping everything in
   separate lists; convert the speculations code to use a destructor too;
   convert users of these lists to use dt_htab_next where needed

Nick Alcock (11):
  cmd: delete ctf_module_dump
  modules: purge linked-in shared ctf.ko module support
  htab: add dt_htab_entries
  htab: have dt_htab_destroy del all the elements
  speculations: use a destructor rather than hand-freeing
  kernpath: delete the dt_kernpath 'public API wrappers'
  htab reduction: kernpath
  htab: add a _next-style iterator
  htab reduction: providers
  htab reduction: modules
  htab reduction: symtab

 cmd/Build                    |  16 +-
 cmd/ctf_module_dump.c        | 314 ---------------------------------
 libdtrace/dt_consume.c       |  85 +++++----
 libdtrace/dt_dof.c           |   4 +-
 libdtrace/dt_htab.c          | 116 +++++++++++-
 libdtrace/dt_htab.h          |  15 +-
 libdtrace/dt_impl.h          |  35 ++--
 libdtrace/dt_kernel_module.c | 129 +++++++-------
 libdtrace/dt_kernel_module.h |  23 +--
 libdtrace/dt_module.c        | 329 +++++++++++++----------------------
 libdtrace/dt_module.h        |   3 +-
 libdtrace/dt_open.c          |  31 +---
 libdtrace/dt_pcb.c           |   8 +-
 libdtrace/dt_probe.c         |   4 +-
 libdtrace/dt_program.c       |   8 +-
 libdtrace/dt_provider.c      |  96 +++++-----
 libdtrace/dt_provider.h      |   3 +-
 libdtrace/dt_symtab.c        | 231 ++++++++++--------------
 libdtrace/dt_symtab.h        |  22 ++-
 libdtrace/libdtrace.ver      |   7 -
 20 files changed, 562 insertions(+), 917 deletions(-)
 delete mode 100644 cmd/ctf_module_dump.c

-- 
2.33.1.257.g9e0974a4e8