On Wed, Aug 22, 2018 at 2:49 PM, Daniel Borkmann <dan...@iogearbox.net> wrote:
> All BPF hash and LRU maps currently have a known and global seed
> we feed into jhash() which is 0. This is suboptimal, thus fix it
> by generating a random seed upon hashtab setup time which we can
> later on feed into jhash() on lookup, update and deletions.
>
> Fixes: 0f8e4bd8a1fc8 ("bpf: add hashtable type of eBPF maps")
> Signed-off-by: Daniel Borkmann <dan...@iogearbox.net>
> Acked-by: Alexei Starovoitov <a...@kernel.org>
Acked-by: Song Liu <songliubrav...@fb.com>
> ---
> kernel/bpf/hashtab.c | 23 +++++++++++++----------
> 1 file changed, 13 insertions(+), 10 deletions(-)
>
> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index 04b8eda..03cc59e 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c
> @@ -15,6 +15,7 @@
> #include <linux/jhash.h>
> #include <linux/filter.h>
> #include <linux/rculist_nulls.h>
> +#include <linux/random.h>
> #include <uapi/linux/btf.h>
> #include "percpu_freelist.h"
> #include "bpf_lru_list.h"
> @@ -41,6 +42,7 @@ struct bpf_htab {
> atomic_t count; /* number of elements in this hashtable */
> u32 n_buckets; /* number of hash buckets */
> u32 elem_size; /* size of each element in bytes */
> + u32 hashrnd;
> };
>
> /* each htab element is struct htab_elem + key + value */
> @@ -371,6 +373,7 @@ static struct bpf_map *htab_map_alloc(union bpf_attr
> *attr)
> if (!htab->buckets)
> goto free_htab;
>
> + htab->hashrnd = get_random_int();
> for (i = 0; i < htab->n_buckets; i++) {
> INIT_HLIST_NULLS_HEAD(&htab->buckets[i].head, i);
> raw_spin_lock_init(&htab->buckets[i].lock);
> @@ -402,9 +405,9 @@ static struct bpf_map *htab_map_alloc(union bpf_attr
> *attr)
> return ERR_PTR(err);
> }
>
> -static inline u32 htab_map_hash(const void *key, u32 key_len)
> +static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd)
> {
> - return jhash(key, key_len, 0);
> + return jhash(key, key_len, hashrnd);
> }
>
> static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
> @@ -470,7 +473,7 @@ static void *__htab_map_lookup_elem(struct bpf_map *map,
> void *key)
>
> key_size = map->key_size;
>
> - hash = htab_map_hash(key, key_size);
> + hash = htab_map_hash(key, key_size, htab->hashrnd);
>
> head = select_bucket(htab, hash);
>
> @@ -597,7 +600,7 @@ static int htab_map_get_next_key(struct bpf_map *map,
> void *key, void *next_key)
> if (!key)
> goto find_first_elem;
>
> - hash = htab_map_hash(key, key_size);
> + hash = htab_map_hash(key, key_size, htab->hashrnd);
>
> head = select_bucket(htab, hash);
>
> @@ -824,7 +827,7 @@ static int htab_map_update_elem(struct bpf_map *map, void
> *key, void *value,
>
> key_size = map->key_size;
>
> - hash = htab_map_hash(key, key_size);
> + hash = htab_map_hash(key, key_size, htab->hashrnd);
>
> b = __select_bucket(htab, hash);
> head = &b->head;
> @@ -880,7 +883,7 @@ static int htab_lru_map_update_elem(struct bpf_map *map,
> void *key, void *value,
>
> key_size = map->key_size;
>
> - hash = htab_map_hash(key, key_size);
> + hash = htab_map_hash(key, key_size, htab->hashrnd);
>
> b = __select_bucket(htab, hash);
> head = &b->head;
> @@ -945,7 +948,7 @@ static int __htab_percpu_map_update_elem(struct bpf_map
> *map, void *key,
>
> key_size = map->key_size;
>
> - hash = htab_map_hash(key, key_size);
> + hash = htab_map_hash(key, key_size, htab->hashrnd);
>
> b = __select_bucket(htab, hash);
> head = &b->head;
> @@ -998,7 +1001,7 @@ static int __htab_lru_percpu_map_update_elem(struct
> bpf_map *map, void *key,
>
> key_size = map->key_size;
>
> - hash = htab_map_hash(key, key_size);
> + hash = htab_map_hash(key, key_size, htab->hashrnd);
>
> b = __select_bucket(htab, hash);
> head = &b->head;
> @@ -1071,7 +1074,7 @@ static int htab_map_delete_elem(struct bpf_map *map,
> void *key)
>
> key_size = map->key_size;
>
> - hash = htab_map_hash(key, key_size);
> + hash = htab_map_hash(key, key_size, htab->hashrnd);
> b = __select_bucket(htab, hash);
> head = &b->head;
>
> @@ -1103,7 +1106,7 @@ static int htab_lru_map_delete_elem(struct bpf_map
> *map, void *key)
>
> key_size = map->key_size;
>
> - hash = htab_map_hash(key, key_size);
> + hash = htab_map_hash(key, key_size, htab->hashrnd);
> b = __select_bucket(htab, hash);
> head = &b->head;
>
> --
> 2.9.5
>
