kernel/linux.git/tools/lib/bpf/hashmap.h, branch v6.1.168

libbpf, hashmap: Fix undefined behavior in hash_bits

2020-11-02T22:33:51+00:00

If bits is 0, the case when the map is empty, then the >> is the size of the register which is undefined behavior - on x86 it is the same as a shift by 0. Fix by handling the 0 case explicitly and guarding calls to hash_bits for empty maps in hashmap__for_each_key_entry and hashmap__for_each_entry_safe. Fixes: e3b924224028 ("libbpf: add resizable non-thread safe internal hashmap") Suggested-by: Andrii Nakryiko , Signed-off-by: Ian Rogers Signed-off-by: Daniel Borkmann Acked-by: Andrii Nakryiko Acked-by: Song Liu Link: https://lore.kernel.org/bpf/20201029223707.494059-1-irogers@google.com

libbpf: Extract generic string hashing function for reuse

2020-09-29T00:27:31+00:00

Calculating a hash of zero-terminated string is a common need when using hashmap, so extract it for reuse. Signed-off-by: Andrii Nakryiko Signed-off-by: Alexei Starovoitov Acked-by: John Fastabend Link: https://lore.kernel.org/bpf/20200926011357.2366158-5-andriin@fb.com

libbpf: Fix libbpf hashmap on (I)LP32 architectures

2020-07-10T02:38:55+00:00

On ILP32, 64-bit result was shifted by value calculated for 32-bit long type and returned value was much outside hashmap capacity. As advised by Andrii Nakryiko, this patch uses different hashing variant for architectures with size_t shorter than long long. Fixes: e3b924224028 ("libbpf: add resizable non-thread safe internal hashmap") Signed-off-by: Jakub Bogusz Signed-off-by: Andrii Nakryiko Signed-off-by: Alexei Starovoitov Link: https://lore.kernel.org/bpf/20200709225723.1069937-1-andriin@fb.com

libbpf: Define __WORDSIZE if not available

2020-06-09T23:19:25+00:00

Some systems, such as Android, don't have a define for __WORDSIZE, do it in terms of __SIZEOF_LONG__, as done in perf since 2012: http://git.kernel.org/torvalds/c/3f34f6c0233ae055b5 For reference: https://gcc.gnu.org/onlinedocs/cpp/Common-Predefined-Macros.html I build tested it here and Andrii did some Travis CI build tests too. Signed-off-by: Arnaldo Carvalho de Melo Signed-off-by: Daniel Borkmann Acked-by: Andrii Nakryiko Link: https://lore.kernel.org/bpf/20200608161150.GA3073@kernel.org

libbpf, hashmap: Remove unused #include

2020-05-15T23:05:16+00:00

Remove #include of libbpf_internal.h that is unused. Discussed in this thread: https://lore.kernel.org/lkml/CAEf4BzZRmiEds_8R8g4vaAeWvJzPb4xYLnpF0X2VNY8oTzkphQ@mail.gmail.com/ Signed-off-by: Ian Rogers Signed-off-by: Daniel Borkmann Acked-by: Andrii Nakryiko Link: https://lore.kernel.org/bpf/20200515165007.217120-3-irogers@google.com

libbpf: fix missing __WORDSIZE definition

2019-07-29T13:18:08+00:00

hashmap.h depends on __WORDSIZE being defined. It is defined by glibc/musl in different headers. It's an explicit goal for musl to be "non-detectable" at compilation time, so instead include glibc header if glibc is explicitly detected and fall back to musl header otherwise. Reported-by: Arnaldo Carvalho de Melo Signed-off-by: Andrii Nakryiko Tested-by: Arnaldo Carvalho de Melo Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Daniel Borkmann Fixes: e3b924224028 ("libbpf: add resizable non-thread safe internal hashmap") Link: https://lkml.kernel.org/r/20190718173021.2418606-1-andriin@fb.com Signed-off-by: Arnaldo Carvalho de Melo

libbpf: add resizable non-thread safe internal hashmap

2019-05-24T21:05:57+00:00

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 Signed-off-by: Alexei Starovoitov