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
_______________________________________________
systemd-devel mailing list
systemd-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/systemd-devel
