libbpf: add resizable non-thread safe internal hashmap
authorAndrii Nakryiko <andriin@fb.com>
Fri, 24 May 2019 18:59:00 +0000 (11:59 -0700)
committerAlexei Starovoitov <ast@kernel.org>
Fri, 24 May 2019 21:05:57 +0000 (14:05 -0700)
commite3b924224028c6fc31545e3812eecbe2ddbf35f6
treef5fdfaf2fac6e21b7c7b9d044ab73cf068fa6423
parent9db324314d29442c8bb8212dd40a3bb26f86c1c9
libbpf: add resizable non-thread safe internal hashmap

There is a need for fast point lookups inside libbpf for multiple use
cases (e.g., name resolution for BTF-to-C conversion, by-name lookups in
BTF for upcoming BPF CO-RE relocation support, etc). This patch
implements simple resizable non-thread safe hashmap using single linked
list chains.

Four different insert strategies are supported:
 - HASHMAP_ADD - only add key/value if key doesn't exist yet;
 - HASHMAP_SET - add key/value pair if key doesn't exist yet; otherwise,
   update value;
 - HASHMAP_UPDATE - update value, if key already exists; otherwise, do
   nothing and return -ENOENT;
 - HASHMAP_APPEND - always add key/value pair, even if key already exists.
   This turns hashmap into a multimap by allowing multiple values to be
   associated with the same key. Most useful read API for such hashmap is
   hashmap__for_each_key_entry() iteration. If hashmap__find() is still
   used, it will return last inserted key/value entry (first in a bucket
   chain).

For HASHMAP_SET and HASHMAP_UPDATE, old key/value pair is returned, so
that calling code can handle proper memory management, if necessary.

Signed-off-by: Andrii Nakryiko <andriin@fb.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
tools/lib/bpf/Build
tools/lib/bpf/hashmap.c [new file with mode: 0644]
tools/lib/bpf/hashmap.h [new file with mode: 0644]