[systemd-devel] [PATCH 00/26] hashmap rewrite

[Michal Schmidt]

Hello,

I rewrote the hashmaps implementation to use less memory.
See patch PATCH 21/26 for details and some measurements.

I'd like to push this upstream after v217 is released,
unless there are objections.

Key changes that affect other code:
 - Sets and Hashmaps do not remember the insertion order anymore.
   They can still be iterated with *_FOREACH* or *_first*, but
   the order of entries is undefined.

 - There is a new type "LinkedHashmap" to use in the few cases where
   insertion order matters. The cases that I believe need it are
   converted in this patch series.

 - Two hashmap operations that previously could not fail with -ENOMEM
   may now do so:
     *_move
     *_move_one

 - A new hashmap operation is introduced:
     *_reserve
   It can be used to ensure subsequent *_move or *_move_one operations
   will not need to allocate memory and won't fail with -ENOMEM, thus
   bringing back the old implementation's guarantees.
   (Actually it also ensures that for *_put operations, but that should
    not be relied on, because it's an implementation detail.)
   It can also be used as a hint before putting a known number of
   entries into a hashmap, to avoid later automatic resizing.

 - A new ./configure option is introduced:
     --enable-hashmap-debug
   It enables internal checks for invalid mixed use of iterators and
   hashmap-modifying operations. I suggest to use it when developing
   new code.
   It also causes all allocated hashmaps to be tracked in a global
   linked list where they can be inspected from gdb with the provided
   sd_dump_hashmaps gdb command.

Michal Schmidt (26):
  hashmap: add LinkedHashmap as a distinct type
  test: generate tests for LinkedHashmap from Hashmap tests
  test: add and improve hashmap tests
  hashmap: hashmap_move_one should return -ENOENT when 'other' is NULL
  hashmap: drop assert(h) from linked_hashmap_next
  install: make InstallContext::{will_install,have_installed}
    LinkedHashmaps
  journal: make JournalFile::chain_cache a LinkedHashmap
  journal: make Server::user_journals a LinkedHashmap
  journal: make sd_journal::files a LinkedHashmap
  sd-bus: make sd_bus::reply_callbacks a LinkedHashmap
  resolve: make DnsScope::conflict_queue a LinkedHashmap
  shared: split mempool implementation from hashmaps
  hashmap: return more information from resize_buckets
  hashmap: introduce hashmap_reserve()
  test: add test for hashmap_reserve()
  install, cgtop: adjust hashmap_move_one callers for -ENOMEM
    possibility
  unit: place reservations before merging other's dependencies
  hashmap: allow hashmap_move to fail
  unit: adjust for the possibility of set_move failing
  util: add log2u, log2u_round_up
  hashmap: rewrite the implementation
  test: adjust max load factor in test_hashmap_many
  tools: add gdb command to dump hashmap information
  configure.ac: add --enable-hashmap-debug option
  test: test a corner case in hashmap_remove_and_replace
  shared: drop mempool, now unused

 Makefile.am                          |   25 +-
 configure.ac                         |    7 +
 src/cgtop/cgtop.c                    |    4 +-
 src/core/unit.c                      |   65 +-
 src/journal/journal-file.c           |   16 +-
 src/journal/journal-file.h           |    2 +-
 src/journal/journal-internal.h       |    2 +-
 src/journal/journalctl.c             |    6 +-
 src/journal/journald-server.c        |   24 +-
 src/journal/journald-server.h        |    2 +-
 src/journal/sd-journal.c             |   38 +-
 src/libsystemd/sd-bus/bus-internal.h |    2 +-
 src/libsystemd/sd-bus/bus-slot.c     |    2 +-
 src/libsystemd/sd-bus/sd-bus.c       |   14 +-
 src/resolve/resolved-dns-scope.c     |   10 +-
 src/resolve/resolved-dns-scope.h     |    2 +-
 src/shared/hashmap.c                 | 1727 +++++++++++++++++++++++++---------
 src/shared/hashmap.h                 |  351 ++++++-
 src/shared/install.c                 |   58 +-
 src/shared/set.c                     |  162 ----
 src/shared/set.h                     |  119 ++-
 src/shared/util.h                    |   15 +
 src/test/.gitignore                  |    1 +
 src/test/test-hashmap-plain.c        |  864 +++++++++++++++++
 src/test/test-hashmap.c              |  542 +----------
 tools/gdb-sd_dump_hashmaps.py        |   94 ++
 26 files changed, 2878 insertions(+), 1276 deletions(-)
 delete mode 100644 src/shared/set.c
 create mode 100644 src/test/.gitignore
 create mode 100644 src/test/test-hashmap-plain.c
 create mode 100644 tools/gdb-sd_dump_hashmaps.py

-- 
2.1.0