| Message ID | 20201029223707.494059-1-irogers@google.com |
|---|---|
| State | Not Applicable |
| Delegated to: | BPF Maintainers |
| Headers | show |
| Series | [v2] libbpf hashmap: Fix undefined behavior in hash_bits | expand |
| Context | Check | Description |
|---|---|---|
| jkicinski/tree_selection | success | Not a local patch |
On Thu, Oct 29, 2020 at 3:38 PM Ian Rogers <irogers@google.com> wrote: > > 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. > > Suggested-by: Andrii Nakryiko <andriin@fb.com>, > Signed-off-by: Ian Rogers <irogers@google.com> > --- Looks good. Thanks and sorry for unnecessary iterations. Acked-by: Andrii Nakryiko <andrii@kernel.org> > tools/lib/bpf/hashmap.h | 15 +++++++++------ > 1 file changed, 9 insertions(+), 6 deletions(-) > > diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h > index d9b385fe808c..10a4c4cd13cf 100644 > --- a/tools/lib/bpf/hashmap.h > +++ b/tools/lib/bpf/hashmap.h > @@ -15,6 +15,9 @@ > static inline size_t hash_bits(size_t h, int bits) > { > /* shuffle bits and return requested number of upper bits */ > + if (bits == 0) > + return 0; > + > #if (__SIZEOF_SIZE_T__ == __SIZEOF_LONG_LONG__) > /* LP64 case */ > return (h * 11400714819323198485llu) >> (__SIZEOF_LONG_LONG__ * 8 - bits); > @@ -174,17 +177,17 @@ bool hashmap__find(const struct hashmap *map, const void *key, void **value); > * @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; }); \ > + for (cur = map->buckets \ > + ? map->buckets[hash_bits(map->hash_fn((_key), map->ctx), map->cap_bits)] \ > + : 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; }); \ > + for (cur = map->buckets \ > + ? map->buckets[hash_bits(map->hash_fn((_key), map->ctx), map->cap_bits)] \ > + : NULL; \ > cur && ({ tmp = cur->next; true; }); \ > cur = tmp) \ > if (map->equal_fn(cur->key, (_key), map->ctx)) > -- > 2.29.1.341.ge80a0c044ae-goog >
> On Oct 29, 2020, at 3:38 PM, Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Thu, Oct 29, 2020 at 3:38 PM Ian Rogers <irogers@google.com> wrote: >> >> 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. >> >> Suggested-by: Andrii Nakryiko <andriin@fb.com>, >> Signed-off-by: Ian Rogers <irogers@google.com> >> --- > > Looks good. Thanks and sorry for unnecessary iterations. > > Acked-by: Andrii Nakryiko <andrii@kernel.org> Acked-by: Song Liu <songliubraving@fb.com>
diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h index d9b385fe808c..10a4c4cd13cf 100644 --- a/tools/lib/bpf/hashmap.h +++ b/tools/lib/bpf/hashmap.h @@ -15,6 +15,9 @@ static inline size_t hash_bits(size_t h, int bits) { /* shuffle bits and return requested number of upper bits */ + if (bits == 0) + return 0; + #if (__SIZEOF_SIZE_T__ == __SIZEOF_LONG_LONG__) /* LP64 case */ return (h * 11400714819323198485llu) >> (__SIZEOF_LONG_LONG__ * 8 - bits); @@ -174,17 +177,17 @@ bool hashmap__find(const struct hashmap *map, const void *key, void **value); * @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; }); \ + for (cur = map->buckets \ + ? map->buckets[hash_bits(map->hash_fn((_key), map->ctx), map->cap_bits)] \ + : 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; }); \ + for (cur = map->buckets \ + ? map->buckets[hash_bits(map->hash_fn((_key), map->ctx), map->cap_bits)] \ + : NULL; \ cur && ({ tmp = cur->next; true; }); \ cur = tmp) \ if (map->equal_fn(cur->key, (_key), map->ctx))
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. Suggested-by: Andrii Nakryiko <andriin@fb.com>, Signed-off-by: Ian Rogers <irogers@google.com> --- tools/lib/bpf/hashmap.h | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-)