| Message ID | 20200508063954.256593-1-irogers@google.com |
|---|---|
| State | Changes Requested |
| Delegated to: | BPF Maintainers |
| Headers | show |
| Series | libbpf hashmap: fix undefined behavior in hash_bits | expand |
On Thu, May 7, 2020 at 11:40 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. > > Signed-off-by: Ian Rogers <irogers@google.com> > --- No need. The only case when bits can be 0 is when hashmap is completely empty (no elements have ever been added yet). In that case, it doesn't matter what value hash_bits() returns, hashmap__for_each_key_entry/hashmap__for_each_key_entry_safe will behave correctly, because map->buckets will be NULL. > tools/lib/bpf/hashmap.h | 2 ++ > 1 file changed, 2 insertions(+) > > diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h > index d5ef212a55ba..781db653d16c 100644 > --- a/tools/lib/bpf/hashmap.h > +++ b/tools/lib/bpf/hashmap.h > @@ -19,6 +19,8 @@ > 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; > return (h * 11400714819323198485llu) >> (__WORDSIZE - bits); > } > > -- > 2.26.2.645.ge9eca65c58-goog >
On Fri, May 8, 2020 at 12:12 AM Andrii Nakryiko <andrii.nakryiko@gmail.com> wrote: > > On Thu, May 7, 2020 at 11:40 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. > > > > Signed-off-by: Ian Rogers <irogers@google.com> > > --- > > No need. The only case when bits can be 0 is when hashmap is > completely empty (no elements have ever been added yet). In that case, > it doesn't matter what value hash_bits() returns, > hashmap__for_each_key_entry/hashmap__for_each_key_entry_safe will > behave correctly, because map->buckets will be NULL. Agreed. Unfortunately the LLVM undefined behavior sanitizer (I've not tested with GCC to the same extent) will cause an exit when it sees >> 64 regardless of whether the value is used or not. It'd be possible to #ifdef this code on whether a sanitizer was present. Thanks, Ian > > tools/lib/bpf/hashmap.h | 2 ++ > > 1 file changed, 2 insertions(+) > > > > diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h > > index d5ef212a55ba..781db653d16c 100644 > > --- a/tools/lib/bpf/hashmap.h > > +++ b/tools/lib/bpf/hashmap.h > > @@ -19,6 +19,8 @@ > > 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; > > return (h * 11400714819323198485llu) >> (__WORDSIZE - bits); > > } > > > > -- > > 2.26.2.645.ge9eca65c58-goog > >
On Fri, May 8, 2020 at 12:21 AM Ian Rogers <irogers@google.com> wrote: > > On Fri, May 8, 2020 at 12:12 AM Andrii Nakryiko > <andrii.nakryiko@gmail.com> wrote: > > > > On Thu, May 7, 2020 at 11:40 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. > > > > > > Signed-off-by: Ian Rogers <irogers@google.com> > > > --- > > > > No need. The only case when bits can be 0 is when hashmap is > > completely empty (no elements have ever been added yet). In that case, > > it doesn't matter what value hash_bits() returns, > > hashmap__for_each_key_entry/hashmap__for_each_key_entry_safe will > > behave correctly, because map->buckets will be NULL. > > Agreed. Unfortunately the LLVM undefined behavior sanitizer (I've not > tested with GCC to the same extent) will cause an exit when it sees >> > 64 regardless of whether the value is used or not. It'd be possible to > #ifdef this code on whether a sanitizer was present. Yeah, let's do that rather than slowing down hashing function. > > Thanks, > Ian > > > > tools/lib/bpf/hashmap.h | 2 ++ > > > 1 file changed, 2 insertions(+) > > > > > > diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h > > > index d5ef212a55ba..781db653d16c 100644 > > > --- a/tools/lib/bpf/hashmap.h > > > +++ b/tools/lib/bpf/hashmap.h > > > @@ -19,6 +19,8 @@ > > > 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; > > > return (h * 11400714819323198485llu) >> (__WORDSIZE - bits); > > > } > > > > > > -- > > > 2.26.2.645.ge9eca65c58-goog > > >
diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h index d5ef212a55ba..781db653d16c 100644 --- a/tools/lib/bpf/hashmap.h +++ b/tools/lib/bpf/hashmap.h @@ -19,6 +19,8 @@ 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; return (h * 11400714819323198485llu) >> (__WORDSIZE - bits); }
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. Signed-off-by: Ian Rogers <irogers@google.com> --- tools/lib/bpf/hashmap.h | 2 ++ 1 file changed, 2 insertions(+)