* [PATCH] libbpf hashmap: Fix undefined behavior in hash_bits
@ 2020-10-29 16:09 Ian Rogers
2020-10-29 17:45 ` Song Liu
2020-10-29 20:16 ` Andrii Nakryiko
0 siblings, 2 replies; 9+ messages in thread
From: Ian Rogers @ 2020-10-29 16:09 UTC (permalink / raw)
To: Alexei Starovoitov, Daniel Borkmann, Martin KaFai Lau, Song Liu,
Yonghong Song, Andrii Nakryiko, John Fastabend, KP Singh, netdev,
bpf, linux-kernel
Cc: Ian Rogers
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 when running with
address sanitizer.
A variant of this patch was posted previously as:
https://lore.kernel.org/lkml/20200508063954.256593-1-irogers@google.com/
Signed-off-by: Ian Rogers <irogers@google.com>
---
tools/lib/bpf/hashmap.h | 14 ++++++++++++++
1 file changed, 14 insertions(+)
diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h
index d9b385fe808c..27d0556527d3 100644
--- a/tools/lib/bpf/hashmap.h
+++ b/tools/lib/bpf/hashmap.h
@@ -12,9 +12,23 @@
#include <stddef.h>
#include <limits.h>
+#ifdef __has_feature
+#define HAVE_FEATURE(f) __has_feature(f)
+#else
+#define HAVE_FEATURE(f) 0
+#endif
+
static inline size_t hash_bits(size_t h, int bits)
{
/* shuffle bits and return requested number of upper bits */
+#if defined(ADDRESS_SANITIZER) || HAVE_FEATURE(address_sanitizer)
+ /*
+ * If the requested bits == 0 avoid undefined behavior from a
+ * greater-than bit width shift right (aka invalid-shift-exponent).
+ */
+ if (bits == 0)
+ return -1;
+#endif
#if (__SIZEOF_SIZE_T__ == __SIZEOF_LONG_LONG__)
/* LP64 case */
return (h * 11400714819323198485llu) >> (__SIZEOF_LONG_LONG__ * 8 - bits);
--
2.29.1.341.ge80a0c044ae-goog
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH] libbpf hashmap: Fix undefined behavior in hash_bits
2020-10-29 16:09 [PATCH] libbpf hashmap: Fix undefined behavior in hash_bits Ian Rogers
@ 2020-10-29 17:45 ` Song Liu
2020-10-29 19:37 ` Ian Rogers
2020-10-29 20:16 ` Andrii Nakryiko
1 sibling, 1 reply; 9+ messages in thread
From: Song Liu @ 2020-10-29 17:45 UTC (permalink / raw)
To: Ian Rogers
Cc: Alexei Starovoitov, Daniel Borkmann, Martin Lau, Yonghong Song,
Andrii Nakryiko, John Fastabend, KP Singh, netdev, bpf,
linux-kernel
> On Oct 29, 2020, at 9:09 AM, 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 when running with
> address sanitizer.
>
> A variant of this patch was posted previously as:
> https://lore.kernel.org/lkml/20200508063954.256593-1-irogers@google.com/
>
> Signed-off-by: Ian Rogers <irogers@google.com>
> ---
> tools/lib/bpf/hashmap.h | 14 ++++++++++++++
> 1 file changed, 14 insertions(+)
>
> diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h
> index d9b385fe808c..27d0556527d3 100644
> --- a/tools/lib/bpf/hashmap.h
> +++ b/tools/lib/bpf/hashmap.h
> @@ -12,9 +12,23 @@
> #include <stddef.h>
> #include <limits.h>
>
> +#ifdef __has_feature
> +#define HAVE_FEATURE(f) __has_feature(f)
> +#else
> +#define HAVE_FEATURE(f) 0
> +#endif
> +
> static inline size_t hash_bits(size_t h, int bits)
> {
> /* shuffle bits and return requested number of upper bits */
> +#if defined(ADDRESS_SANITIZER) || HAVE_FEATURE(address_sanitizer)
I am not very familiar with these features. Is address sanitizer same
as undefined behavior sanitizer (mentioned in previous version)?
> + /*
> + * If the requested bits == 0 avoid undefined behavior from a
> + * greater-than bit width shift right (aka invalid-shift-exponent).
> + */
> + if (bits == 0)
> + return -1;
Shall we return 0 or -1 (0xffffffff) here?
Also, we have HASHMAP_MIN_CAP_BITS == 2. Shall we just make sure we
never feed bits == 0 into hash_bits()?
Thanks,
Song
> +#endif
> #if (__SIZEOF_SIZE_T__ == __SIZEOF_LONG_LONG__)
> /* LP64 case */
> return (h * 11400714819323198485llu) >> (__SIZEOF_LONG_LONG__ * 8 - bits);
> --
> 2.29.1.341.ge80a0c044ae-goog
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] libbpf hashmap: Fix undefined behavior in hash_bits
2020-10-29 17:45 ` Song Liu
@ 2020-10-29 19:37 ` Ian Rogers
0 siblings, 0 replies; 9+ messages in thread
From: Ian Rogers @ 2020-10-29 19:37 UTC (permalink / raw)
To: Song Liu
Cc: Alexei Starovoitov, Daniel Borkmann, Martin Lau, Yonghong Song,
Andrii Nakryiko, John Fastabend, KP Singh, netdev, bpf,
linux-kernel
On Thu, Oct 29, 2020 at 10:45 AM Song Liu <songliubraving@fb.com> wrote:
>
> > On Oct 29, 2020, at 9:09 AM, 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 when running with
> > address sanitizer.
> >
> > A variant of this patch was posted previously as:
> > https://lore.kernel.org/lkml/20200508063954.256593-1-irogers@google.com/
> >
> > Signed-off-by: Ian Rogers <irogers@google.com>
> > ---
> > tools/lib/bpf/hashmap.h | 14 ++++++++++++++
> > 1 file changed, 14 insertions(+)
> >
> > diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h
> > index d9b385fe808c..27d0556527d3 100644
> > --- a/tools/lib/bpf/hashmap.h
> > +++ b/tools/lib/bpf/hashmap.h
> > @@ -12,9 +12,23 @@
> > #include <stddef.h>
> > #include <limits.h>
> >
> > +#ifdef __has_feature
> > +#define HAVE_FEATURE(f) __has_feature(f)
> > +#else
> > +#define HAVE_FEATURE(f) 0
> > +#endif
> > +
> > static inline size_t hash_bits(size_t h, int bits)
> > {
> > /* shuffle bits and return requested number of upper bits */
> > +#if defined(ADDRESS_SANITIZER) || HAVE_FEATURE(address_sanitizer)
>
> I am not very familiar with these features. Is address sanitizer same
> as undefined behavior sanitizer (mentioned in previous version)?
My preference would be to special case bits == 0 without the feature
guards as per the original change, this is the most correct. There is
some feature support for detecting ubsan:
https://github.com/google/sanitizers/issues/765
In my case I see this with address sanitizer and older versions of
clang don't expose ubsan as a feature.
> > + /*
> > + * If the requested bits == 0 avoid undefined behavior from a
> > + * greater-than bit width shift right (aka invalid-shift-exponent).
> > + */
> > + if (bits == 0)
> > + return -1;
>
> Shall we return 0 or -1 (0xffffffff) here?
The value isn't used and so doesn't matter. -1 seemed less likely to
silently succeed.
> Also, we have HASHMAP_MIN_CAP_BITS == 2. Shall we just make sure we
> never feed bits == 0 into hash_bits()?
I think that'd be a different change. I'd be happy to see it.
Thanks,
Ian
> Thanks,
> Song
>
>
> > +#endif
> > #if (__SIZEOF_SIZE_T__ == __SIZEOF_LONG_LONG__)
> > /* LP64 case */
> > return (h * 11400714819323198485llu) >> (__SIZEOF_LONG_LONG__ * 8 - bits);
> > --
> > 2.29.1.341.ge80a0c044ae-goog
> >
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] libbpf hashmap: Fix undefined behavior in hash_bits
2020-10-29 16:09 [PATCH] libbpf hashmap: Fix undefined behavior in hash_bits Ian Rogers
2020-10-29 17:45 ` Song Liu
@ 2020-10-29 20:16 ` Andrii Nakryiko
2020-10-29 20:58 ` Ian Rogers
1 sibling, 1 reply; 9+ messages in thread
From: Andrii Nakryiko @ 2020-10-29 20:16 UTC (permalink / raw)
To: Ian Rogers
Cc: Alexei Starovoitov, Daniel Borkmann, Martin KaFai Lau, Song Liu,
Yonghong Song, Andrii Nakryiko, John Fastabend, KP Singh,
Networking, bpf, open list
On Thu, Oct 29, 2020 at 9:11 AM 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 when running with
> address sanitizer.
>
> A variant of this patch was posted previously as:
> https://lore.kernel.org/lkml/20200508063954.256593-1-irogers@google.com/
>
> Signed-off-by: Ian Rogers <irogers@google.com>
> ---
> tools/lib/bpf/hashmap.h | 14 ++++++++++++++
> 1 file changed, 14 insertions(+)
>
> diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h
> index d9b385fe808c..27d0556527d3 100644
> --- a/tools/lib/bpf/hashmap.h
> +++ b/tools/lib/bpf/hashmap.h
> @@ -12,9 +12,23 @@
> #include <stddef.h>
> #include <limits.h>
>
> +#ifdef __has_feature
> +#define HAVE_FEATURE(f) __has_feature(f)
> +#else
> +#define HAVE_FEATURE(f) 0
> +#endif
> +
> static inline size_t hash_bits(size_t h, int bits)
> {
> /* shuffle bits and return requested number of upper bits */
> +#if defined(ADDRESS_SANITIZER) || HAVE_FEATURE(address_sanitizer)
> + /*
> + * If the requested bits == 0 avoid undefined behavior from a
> + * greater-than bit width shift right (aka invalid-shift-exponent).
> + */
> + if (bits == 0)
> + return -1;
> +#endif
Oh, just too much # magic here :(... If we want to prevent hash_bits()
from being called with bits == 0 (despite the result never used),
let's just adjust hashmap__for_each_key_entry and
hashmap__for_each_key_entry_safe macros:
diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h
index d9b385fe808c..488e0ef236cb 100644
--- a/tools/lib/bpf/hashmap.h
+++ b/tools/lib/bpf/hashmap.h
@@ -174,9 +174,9 @@ 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))
Either way it's a bit ugly and long, but at least we don't have extra
#-driven ugliness.
> #if (__SIZEOF_SIZE_T__ == __SIZEOF_LONG_LONG__)
> /* LP64 case */
> return (h * 11400714819323198485llu) >> (__SIZEOF_LONG_LONG__ * 8 - bits);
> --
> 2.29.1.341.ge80a0c044ae-goog
>
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH] libbpf hashmap: Fix undefined behavior in hash_bits
2020-10-29 20:16 ` Andrii Nakryiko
@ 2020-10-29 20:58 ` Ian Rogers
0 siblings, 0 replies; 9+ messages in thread
From: Ian Rogers @ 2020-10-29 20:58 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Alexei Starovoitov, Daniel Borkmann, Martin KaFai Lau, Song Liu,
Yonghong Song, Andrii Nakryiko, John Fastabend, KP Singh,
Networking, bpf, open list
On Thu, Oct 29, 2020 at 1:16 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Thu, Oct 29, 2020 at 9:11 AM 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 when running with
> > address sanitizer.
> >
> > A variant of this patch was posted previously as:
> > https://lore.kernel.org/lkml/20200508063954.256593-1-irogers@google.com/
> >
> > Signed-off-by: Ian Rogers <irogers@google.com>
> > ---
> > tools/lib/bpf/hashmap.h | 14 ++++++++++++++
> > 1 file changed, 14 insertions(+)
> >
> > diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h
> > index d9b385fe808c..27d0556527d3 100644
> > --- a/tools/lib/bpf/hashmap.h
> > +++ b/tools/lib/bpf/hashmap.h
> > @@ -12,9 +12,23 @@
> > #include <stddef.h>
> > #include <limits.h>
> >
> > +#ifdef __has_feature
> > +#define HAVE_FEATURE(f) __has_feature(f)
> > +#else
> > +#define HAVE_FEATURE(f) 0
> > +#endif
> > +
> > static inline size_t hash_bits(size_t h, int bits)
> > {
> > /* shuffle bits and return requested number of upper bits */
> > +#if defined(ADDRESS_SANITIZER) || HAVE_FEATURE(address_sanitizer)
> > + /*
> > + * If the requested bits == 0 avoid undefined behavior from a
> > + * greater-than bit width shift right (aka invalid-shift-exponent).
> > + */
> > + if (bits == 0)
> > + return -1;
> > +#endif
>
> Oh, just too much # magic here :(... If we want to prevent hash_bits()
> from being called with bits == 0 (despite the result never used),
> let's just adjust hashmap__for_each_key_entry and
> hashmap__for_each_key_entry_safe macros:
>
> diff --git a/tools/lib/bpf/hashmap.h b/tools/lib/bpf/hashmap.h
> index d9b385fe808c..488e0ef236cb 100644
> --- a/tools/lib/bpf/hashmap.h
> +++ b/tools/lib/bpf/hashmap.h
> @@ -174,9 +174,9 @@ 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))
>
> Either way it's a bit ugly and long, but at least we don't have extra
> #-driven ugliness.
This can work with the following changes in hashmap.c. I'll resend
this as a whole patch.
Thanks,
Ian
--- a/tools/lib/bpf/hashmap.c
+++ b/tools/lib/bpf/hashmap.c
@@ -156,7 +156,7 @@ int hashmap__insert(struct hashmap *map,
const void **old_key, void **old_value)
{
struct hashmap_entry *entry;
- size_t h;
+ size_t h = 0;
int err;
if (old_key)
@@ -164,7 +164,9 @@ int hashmap__insert(struct hashmap *map,
if (old_value)
*old_value = NULL;
- h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
+ if (map->buckets)
+ 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)
@@ -208,6 +210,9 @@ bool hashmap__find(const struct hashmap
struct hashmap_entry *entry;
size_t h;
+ if (!map->buckets)
+ return false;
+
h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
if (!hashmap_find_entry(map, key, h, NULL, &entry))
return false;
@@ -223,6 +228,9 @@ bool hashmap__delete(struct hashmap *map
struct hashmap_entry **pprev, *entry;
size_t h;
+ if (!map->buckets)
+ return false;
+
h = hash_bits(map->hash_fn(key, map->ctx), map->cap_bits);
if (!hashmap_find_entry(map, key, h, &pprev, &entry))
return false;
> > #if (__SIZEOF_SIZE_T__ == __SIZEOF_LONG_LONG__)
> > /* LP64 case */
> > return (h * 11400714819323198485llu) >> (__SIZEOF_LONG_LONG__ * 8 - bits);
> > --
> > 2.29.1.341.ge80a0c044ae-goog
> >
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] libbpf hashmap: fix undefined behavior in hash_bits
2020-05-08 7:21 ` Ian Rogers
@ 2020-05-08 18:04 ` Andrii Nakryiko
0 siblings, 0 replies; 9+ messages in thread
From: Andrii Nakryiko @ 2020-05-08 18:04 UTC (permalink / raw)
To: Ian Rogers
Cc: Alexei Starovoitov, Daniel Borkmann, Martin KaFai Lau, Song Liu,
Yonghong Song, Andrii Nakryiko, John Fastabend, KP Singh,
Networking, bpf, open list
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
> > >
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] libbpf hashmap: fix undefined behavior in hash_bits
2020-05-08 7:11 ` Andrii Nakryiko
@ 2020-05-08 7:21 ` Ian Rogers
2020-05-08 18:04 ` Andrii Nakryiko
0 siblings, 1 reply; 9+ messages in thread
From: Ian Rogers @ 2020-05-08 7:21 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Alexei Starovoitov, Daniel Borkmann, Martin KaFai Lau, Song Liu,
Yonghong Song, Andrii Nakryiko, John Fastabend, KP Singh,
Networking, bpf, open list
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
> >
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH] libbpf hashmap: fix undefined behavior in hash_bits
2020-05-08 6:39 [PATCH] libbpf hashmap: fix " Ian Rogers
@ 2020-05-08 7:11 ` Andrii Nakryiko
2020-05-08 7:21 ` Ian Rogers
0 siblings, 1 reply; 9+ messages in thread
From: Andrii Nakryiko @ 2020-05-08 7:11 UTC (permalink / raw)
To: Ian Rogers
Cc: Alexei Starovoitov, Daniel Borkmann, Martin KaFai Lau, Song Liu,
Yonghong Song, Andrii Nakryiko, John Fastabend, KP Singh,
Networking, bpf, open list
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
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH] libbpf hashmap: fix undefined behavior in hash_bits
@ 2020-05-08 6:39 Ian Rogers
2020-05-08 7:11 ` Andrii Nakryiko
0 siblings, 1 reply; 9+ messages in thread
From: Ian Rogers @ 2020-05-08 6:39 UTC (permalink / raw)
To: Alexei Starovoitov, Daniel Borkmann, Martin KaFai Lau, Song Liu,
Yonghong Song, Andrii Nakryiko, John Fastabend, KP Singh, netdev,
bpf, linux-kernel
Cc: Ian Rogers
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(+)
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
^ permalink raw reply related [flat|nested] 9+ messages in thread
end of thread, other threads:[~2020-10-29 20:58 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-10-29 16:09 [PATCH] libbpf hashmap: Fix undefined behavior in hash_bits Ian Rogers
2020-10-29 17:45 ` Song Liu
2020-10-29 19:37 ` Ian Rogers
2020-10-29 20:16 ` Andrii Nakryiko
2020-10-29 20:58 ` Ian Rogers
-- strict thread matches above, loose matches on Subject: below --
2020-05-08 6:39 [PATCH] libbpf hashmap: fix " Ian Rogers
2020-05-08 7:11 ` Andrii Nakryiko
2020-05-08 7:21 ` Ian Rogers
2020-05-08 18:04 ` Andrii Nakryiko
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).