* Re: [PATCH v3 bpf-next 05/12] libbpf: add resizable non-thread safe internal hashmap
2019-07-18 0:24 ` [PATCH v3 bpf-next 05/12] libbpf: add resizable non-thread safe internal hashmap Arnaldo Carvalho de Melo
@ 2019-07-18 3:35 ` Andrii Nakryiko
0 siblings, 0 replies; 2+ messages in thread
From: Andrii Nakryiko @ 2019-07-18 3:35 UTC (permalink / raw)
To: Arnaldo Carvalho de Melo
Cc: Andrii Nakryiko, Alexei Starovoitov, Daniel Borkmann, Networking,
bpf, Kernel Team, linux-perf-users, Jiri Olsa, Namhyung Kim,
Adrian Hunter
On Wed, Jul 17, 2019 at 5:24 PM Arnaldo Carvalho de Melo
<arnaldo.melo@gmail.com> wrote:
>
> Em Fri, May 24, 2019 at 11:59:00AM -0700, Andrii Nakryiko escreveu:
> > 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.
>
> This is breaking the tools/perf build in some systems where __WORDSIZE use in
> tools/lib/bpf/hashmap.h is not finding the definition of __WORDSIZE,
> which I think requires using:
>
> #include <limits.h>
>
> Or perhaps
>
> #include <stdint.h>
>
> Non-exhaustive search on a fedora:30 system:
>
> [acme@quaco perf]$ grep "define.*__WORDSIZE" /usr/include/*/*.h
> /usr/include/bits/elfclass.h:#define __ELF_NATIVE_CLASS __WORDSIZE
> /usr/include/bits/siginfo-arch.h:#if defined __x86_64__ && __WORDSIZE == 32
> /usr/include/bits/timesize.h:# define __TIMESIZE __WORDSIZE
> /usr/include/bits/wordsize.h:# define __WORDSIZE 64
> /usr/include/bits/wordsize.h:# define __WORDSIZE 32
> /usr/include/bits/wordsize.h:#define __WORDSIZE32_SIZE_ULONG 0
> /usr/include/bits/wordsize.h:#define __WORDSIZE32_PTRDIFF_LONG 0
> /usr/include/bits/wordsize.h:# define __WORDSIZE_TIME64_COMPAT32 1
> /usr/include/bits/wordsize.h:# define __WORDSIZE_TIME64_COMPAT32 0
> [acme@quaco perf]$ grep bits\/wordsize.h /usr/include/*.h
> /usr/include/bfd.h:#include <bits/wordsize.h>
> /usr/include/limits.h:#include <bits/wordsize.h>
> /usr/include/pthread.h:#include <bits/wordsize.h>
> /usr/include/stdint.h:#include <bits/wordsize.h>
> /usr/include/tiffconf.h:#include <bits/wordsize.h>
> [acme@quaco perf]$
>
> On fedora:30 it works, probably because some header included from there
> ends up adding the file that has that def, but these fail, for instance:
>
> [perfbuilder@quaco linux-perf-tools-build]$ export PERF_TARBALL=http://192.168.124.1/perf/perf-5.2.0.tar.xz
> [perfbuilder@quaco linux-perf-tools-build]$ time dm
> 1 13.57 alpine:3.4 : FAIL gcc (Alpine 5.3.0) 5.3.0, clang version 3.8.0 (tags/RELEASE_380/final)
> 2 13.78 alpine:3.5 : FAIL gcc (Alpine 6.2.1) 6.2.1 20160822, clang version 3.8.1 (tags/RELEASE_381/final)
> 3 12.42 alpine:3.6 : FAIL gcc (Alpine 6.3.0) 6.3.0, clang version 4.0.0 (tags/RELEASE_400/final)
> 4 15.01 alpine:3.7 : FAIL gcc (Alpine 6.4.0) 6.4.0, Alpine clang version 5.0.0 (tags/RELEASE_500/final) (based on LLVM 5.0.0)
> 5 13.80 alpine:3.8 : FAIL gcc (Alpine 6.4.0) 6.4.0, Alpine clang version 5.0.1 (tags/RELEASE_501/final) (based on LLVM 5.0.1)
> 6 15.37 alpine:3.9 : FAIL gcc (Alpine 8.3.0) 8.3.0, Alpine clang version 5.0.1 (tags/RELEASE_502/final) (based on LLVM 5.0.1)
> 7 15.10 alpine:3.10 : FAIL gcc (Alpine 8.3.0) 8.3.0, Alpine clang version 8.0.0 (tags/RELEASE_800/final) (based on LLVM 8.0.0)
> 8 15.26 alpine:edge : FAIL gcc (Alpine 8.3.0) 8.3.0, Alpine clang version 7.0.1 (tags/RELEASE_701/final) (based on LLVM 7.0.1)
> 9: amazonlinux:1^C
>
> I'm trying to see if adding #include <limits.h> fixes the problems in
> all the distros in my container based build test suite.
>
> Lets see with at least alpine:3.4:
>
> Nope, didn't work, will try revisiting this tomorrow...
>
> I'll let it build anyway to see if this fails in other systems/libcs,
> BTW, Alpine uses musl libc.
So it seems like __WORDSIZE is declared in bits/wordsize.h for glibc
and in bits/reg.h for musl, so something like the following should fix
this issue, but I can't easily verify. Can you please see if these
changes fix the issue on your side?
#ifdef __GLIBC__
#include <bits/wordsize.h>
#else
#include <bits/reg.h>
#endif
>
> - Arnaldo
>
> > 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>
> > ---
> > tools/lib/bpf/Build | 2 +-
> > tools/lib/bpf/hashmap.c | 229 ++++++++++++++++++++++++++++++++++++++++
> > tools/lib/bpf/hashmap.h | 173 ++++++++++++++++++++++++++++++
> > 3 files changed, 403 insertions(+), 1 deletion(-)
> > create mode 100644 tools/lib/bpf/hashmap.c
> > create mode 100644 tools/lib/bpf/hashmap.h
> >
> > diff --git a/tools/lib/bpf/Build b/tools/lib/bpf/Build
> > index ee9d5362f35b..dcf0d36598e0 100644
> > --- a/tools/lib/bpf/Build
> > +++ b/tools/lib/bpf/Build
> > @@ -1 +1 @@
> > -libbpf-y := libbpf.o bpf.o nlattr.o btf.o libbpf_errno.o str_error.o netlink.o bpf_prog_linfo.o libbpf_probes.o xsk.o
> > +libbpf-y := libbpf.o bpf.o nlattr.o btf.o libbpf_errno.o str_error.o netlink.o bpf_prog_linfo.o libbpf_probes.o xsk.o hashmap.o
> > diff --git a/tools/lib/bpf/hashmap.c b/tools/lib/bpf/hashmap.c
> > new file mode 100644
> > index 000000000000..6122272943e6
> > --- /dev/null
> > +++ b/tools/lib/bpf/hashmap.c
> > @@ -0,0 +1,229 @@
> > +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
> > +
> > +/*
> > + * Generic non-thread safe hash map implementation.
> > + *
> > + * Copyright (c) 2019 Facebook
> > + */
> > +#include <stdint.h>
> > +#include <stdlib.h>
> > +#include <stdio.h>
> > +#include <errno.h>
> > +#include <linux/err.h>
> > +#include "hashmap.h"
> > +
> > +/* start with 4 buckets */
> > +#define HASHMAP_MIN_CAP_BITS 2
> > +
> > +static void hashmap_add_entry(struct hashmap_entry **pprev,
> > + struct hashmap_entry *entry)
> > +{
> > + entry->next = *pprev;
> > + *pprev = entry;
> > +}
> > +
> > +static void hashmap_del_entry(struct hashmap_entry **pprev,
> > + struct hashmap_entry *entry)
> > +{
> > + *pprev = entry->next;
> > + entry->next = NULL;
> > +}
> > +
> > +void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
> > + hashmap_equal_fn equal_fn, void *ctx)
> > +{
> > + map->hash_fn = hash_fn;
> > + map->equal_fn = equal_fn;
> > + map->ctx = ctx;
> > +
> > + map->buckets = NULL;
> > + map->cap = 0;
> > + map->cap_bits = 0;
> > + map->sz = 0;
> > +}
> > +
> > +struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
> > + hashmap_equal_fn equal_fn,
> > + void *ctx)
> > +{
> > + struct hashmap *map = malloc(sizeof(struct hashmap));
> > +
> > + if (!map)
> > + return ERR_PTR(-ENOMEM);
> > + hashmap__init(map, hash_fn, equal_fn, ctx);
> > + return map;
> > +}
> > +
> > +void hashmap__clear(struct hashmap *map)
> > +{
> > + free(map->buckets);
> > + map->cap = map->cap_bits = map->sz = 0;
> > +}
> > +
> > +void hashmap__free(struct hashmap *map)
> > +{
> > + if (!map)
> > + return;
> > +
> > + hashmap__clear(map);
> > + free(map);
> > +}
> > +
> > +size_t hashmap__size(const struct hashmap *map)
> > +{
> > + return map->sz;
> > +}
> > +
> > +size_t hashmap__capacity(const struct hashmap *map)
> > +{
> > + return map->cap;
> > +}
> > +
> > +static bool hashmap_needs_to_grow(struct hashmap *map)
> > +{
> > + /* grow if empty or more than 75% filled */
> > + return (map->cap == 0) || ((map->sz + 1) * 4 / 3 > map->cap);
> > +}
> > +
> > +static int hashmap_grow(struct hashmap *map)
> > +{
> > + struct hashmap_entry **new_buckets;
> > + struct hashmap_entry *cur, *tmp;
> > + size_t new_cap_bits, new_cap;
> > + size_t h;
> > + int bkt;
> > +
> > + new_cap_bits = map->cap_bits + 1;
> > + if (new_cap_bits < HASHMAP_MIN_CAP_BITS)
> > + new_cap_bits = HASHMAP_MIN_CAP_BITS;
> > +
> > + new_cap = 1UL << new_cap_bits;
> > + new_buckets = calloc(new_cap, sizeof(new_buckets[0]));
> > + if (!new_buckets)
> > + return -ENOMEM;
> > +
> > + hashmap__for_each_entry_safe(map, cur, tmp, bkt) {
> > + h = hash_bits(map->hash_fn(cur->key, map->ctx), new_cap_bits);
> > + hashmap_add_entry(&new_buckets[h], cur);
> > + }
> > +
> > + map->cap = new_cap;
> > + map->cap_bits = new_cap_bits;
> > + free(map->buckets);
> > + map->buckets = new_buckets;
> > +
> > + return 0;
> > +}
> > +
> > +static bool hashmap_find_entry(const struct hashmap *map,
> > + const void *key, size_t hash,
> > + struct hashmap_entry ***pprev,
> > + struct hashmap_entry **entry)
> > +{
> > + struct hashmap_entry *cur, **prev_ptr;
> > +
> > + if (!map->buckets)
> > + return false;
> > +
> > + for (prev_ptr = &map->buckets[hash], cur = *prev_ptr;
> > + cur;
> > + prev_ptr = &cur->next, cur = cur->next) {
> > + if (map->equal_fn(cur->key, key, map->ctx)) {
> > + if (pprev)
> > + *pprev = prev_ptr;
> > + *entry = cur;
> > + return true;
> > + }
> > + }
> > +
> > + return false;
> > +}
> > +
> > +int hashmap__insert(struct hashmap *map, const void *key, void *value,
> > + enum hashmap_insert_strategy strategy,
> > + const void **old_key, void **old_value)
> > +{
> > + struct hashmap_entry *entry;
> > + size_t h;
> > + int err;
> > +
> > + if (old_key)
> > + *old_key = NULL;
> > + if (old_value)
> > + *old_value = NULL;
> > +
> > + h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
> > + if (strategy != HASHMAP_APPEND &&
> > + hashmap_find_entry(map, key, h, NULL, &entry)) {
> > + if (old_key)
> > + *old_key = entry->key;
> > + if (old_value)
> > + *old_value = entry->value;
> > +
> > + if (strategy == HASHMAP_SET || strategy == HASHMAP_UPDATE) {
> > + entry->key = key;
> > + entry->value = value;
> > + return 0;
> > + } else if (strategy == HASHMAP_ADD) {
> > + return -EEXIST;
> > + }
> > + }
> > +
> > + if (strategy == HASHMAP_UPDATE)
> > + return -ENOENT;
> > +
> > + if (hashmap_needs_to_grow(map)) {
> > + err = hashmap_grow(map);
> > + if (err)
> > + return err;
> > + h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
> > + }
> > +
> > + entry = malloc(sizeof(struct hashmap_entry));
> > + if (!entry)
> > + return -ENOMEM;
> > +
> > + entry->key = key;
> > + entry->value = value;
> > + hashmap_add_entry(&map->buckets[h], entry);
> > + map->sz++;
> > +
> > + return 0;
> > +}
> > +
> > +bool hashmap__find(const struct hashmap *map, const void *key, void **value)
> > +{
> > + struct hashmap_entry *entry;
> > + size_t h;
> > +
> > + h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
> > + if (!hashmap_find_entry(map, key, h, NULL, &entry))
> > + return false;
> > +
> > + if (value)
> > + *value = entry->value;
> > + return true;
> > +}
> > +
> > +bool hashmap__delete(struct hashmap *map, const void *key,
> > + const void **old_key, void **old_value)
> > +{
> > + struct hashmap_entry **pprev, *entry;
> > + size_t h;
> > +
> > + h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
> > + if (!hashmap_find_entry(map, key, h, &pprev, &entry))
> > + return false;
> > +
> > + if (old_key)
> > + *old_key = entry->key;
> > + if (old_value)
> > + *old_value = entry->value;
> > +
> > + hashmap_del_entry(pprev, entry);
> > + free(entry);
> > + map->sz--;
> > +
> > + return true;
> > +}
> > +
> > diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h
> > new file mode 100644
> > index 000000000000..03748a742146
> > --- /dev/null
> > +++ b/tools/lib/bpf/hashmap.h
> > @@ -0,0 +1,173 @@
> > +/* SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) */
> > +
> > +/*
> > + * Generic non-thread safe hash map implementation.
> > + *
> > + * Copyright (c) 2019 Facebook
> > + */
> > +#ifndef __LIBBPF_HASHMAP_H
> > +#define __LIBBPF_HASHMAP_H
> > +
> > +#include <stdbool.h>
> > +#include <stddef.h>
> > +#include "libbpf_internal.h"
> > +
> > +static inline size_t hash_bits(size_t h, int bits)
> > +{
> > + /* shuffle bits and return requested number of upper bits */
> > + return (h * 11400714819323198485llu) >> (__WORDSIZE - bits);
> > +}
> > +
> > +typedef size_t (*hashmap_hash_fn)(const void *key, void *ctx);
> > +typedef bool (*hashmap_equal_fn)(const void *key1, const void *key2, void *ctx);
> > +
> > +struct hashmap_entry {
> > + const void *key;
> > + void *value;
> > + struct hashmap_entry *next;
> > +};
> > +
> > +struct hashmap {
> > + hashmap_hash_fn hash_fn;
> > + hashmap_equal_fn equal_fn;
> > + void *ctx;
> > +
> > + struct hashmap_entry **buckets;
> > + size_t cap;
> > + size_t cap_bits;
> > + size_t sz;
> > +};
> > +
> > +#define HASHMAP_INIT(hash_fn, equal_fn, ctx) { \
> > + .hash_fn = (hash_fn), \
> > + .equal_fn = (equal_fn), \
> > + .ctx = (ctx), \
> > + .buckets = NULL, \
> > + .cap = 0, \
> > + .cap_bits = 0, \
> > + .sz = 0, \
> > +}
> > +
> > +void hashmap__init(struct hashmap *map, hashmap_hash_fn hash_fn,
> > + hashmap_equal_fn equal_fn, void *ctx);
> > +struct hashmap *hashmap__new(hashmap_hash_fn hash_fn,
> > + hashmap_equal_fn equal_fn,
> > + void *ctx);
> > +void hashmap__clear(struct hashmap *map);
> > +void hashmap__free(struct hashmap *map);
> > +
> > +size_t hashmap__size(const struct hashmap *map);
> > +size_t hashmap__capacity(const struct hashmap *map);
> > +
> > +/*
> > + * Hashmap insertion strategy:
> > + * - 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).
> > + */
> > +enum hashmap_insert_strategy {
> > + HASHMAP_ADD,
> > + HASHMAP_SET,
> > + HASHMAP_UPDATE,
> > + HASHMAP_APPEND,
> > +};
> > +
> > +/*
> > + * hashmap__insert() adds key/value entry w/ various semantics, depending on
> > + * provided strategy value. If a given key/value pair replaced already
> > + * existing key/value pair, both old key and old value will be returned
> > + * through old_key and old_value to allow calling code do proper memory
> > + * management.
> > + */
> > +int hashmap__insert(struct hashmap *map, const void *key, void *value,
> > + enum hashmap_insert_strategy strategy,
> > + const void **old_key, void **old_value);
> > +
> > +static inline int hashmap__add(struct hashmap *map,
> > + const void *key, void *value)
> > +{
> > + return hashmap__insert(map, key, value, HASHMAP_ADD, NULL, NULL);
> > +}
> > +
> > +static inline int hashmap__set(struct hashmap *map,
> > + const void *key, void *value,
> > + const void **old_key, void **old_value)
> > +{
> > + return hashmap__insert(map, key, value, HASHMAP_SET,
> > + old_key, old_value);
> > +}
> > +
> > +static inline int hashmap__update(struct hashmap *map,
> > + const void *key, void *value,
> > + const void **old_key, void **old_value)
> > +{
> > + return hashmap__insert(map, key, value, HASHMAP_UPDATE,
> > + old_key, old_value);
> > +}
> > +
> > +static inline int hashmap__append(struct hashmap *map,
> > + const void *key, void *value)
> > +{
> > + return hashmap__insert(map, key, value, HASHMAP_APPEND, NULL, NULL);
> > +}
> > +
> > +bool hashmap__delete(struct hashmap *map, const void *key,
> > + const void **old_key, void **old_value);
> > +
> > +bool hashmap__find(const struct hashmap *map, const void *key, void **value);
> > +
> > +/*
> > + * hashmap__for_each_entry - iterate over all entries in hashmap
> > + * @map: hashmap to iterate
> > + * @cur: struct hashmap_entry * used as a loop cursor
> > + * @bkt: integer used as a bucket loop cursor
> > + */
> > +#define hashmap__for_each_entry(map, cur, bkt) \
> > + for (bkt = 0; bkt < map->cap; bkt++) \
> > + for (cur = map->buckets[bkt]; cur; cur = cur->next)
> > +
> > +/*
> > + * hashmap__for_each_entry_safe - iterate over all entries in hashmap, safe
> > + * against removals
> > + * @map: hashmap to iterate
> > + * @cur: struct hashmap_entry * used as a loop cursor
> > + * @tmp: struct hashmap_entry * used as a temporary next cursor storage
> > + * @bkt: integer used as a bucket loop cursor
> > + */
> > +#define hashmap__for_each_entry_safe(map, cur, tmp, bkt) \
> > + for (bkt = 0; bkt < map->cap; bkt++) \
> > + for (cur = map->buckets[bkt]; \
> > + cur && ({tmp = cur->next; true; }); \
> > + cur = tmp)
> > +
> > +/*
> > + * hashmap__for_each_key_entry - iterate over entries associated with given key
> > + * @map: hashmap to iterate
> > + * @cur: struct hashmap_entry * used as a loop cursor
> > + * @key: key to iterate entries for
> > + */
> > +#define hashmap__for_each_key_entry(map, cur, _key) \
> > + for (cur = ({ size_t bkt = hash_bits(map->hash_fn((_key), map->ctx),\
> > + map->cap_bits); \
> > + map->buckets ? map->buckets[bkt] : NULL; }); \
> > + cur; \
> > + cur = cur->next) \
> > + if (map->equal_fn(cur->key, (_key), map->ctx))
> > +
> > +#define hashmap__for_each_key_entry_safe(map, cur, tmp, _key) \
> > + for (cur = ({ size_t bkt = hash_bits(map->hash_fn((_key), map->ctx),\
> > + map->cap_bits); \
> > + cur = map->buckets ? map->buckets[bkt] : NULL; }); \
> > + cur && ({ tmp = cur->next; true; }); \
> > + cur = tmp) \
> > + if (map->equal_fn(cur->key, (_key), map->ctx))
> > +
> > +#endif /* __LIBBPF_HASHMAP_H */
> > --
> > 2.17.1
>
> --
>
> - Arnaldo
^ permalink raw reply [flat|nested] 2+ messages in thread