bpf: allow zero-initialising hash map seed

Add a new flag BPF_F_ZERO_SEED, which forces a hash map to initialize the seed to zero.

---
 include/uapi/linux/bpf.h | 2 ++
 kernel/bpf/hashtab.c     | 8 ++++++--
 2 files changed, 8 insertions(+), 2 deletions(-)

include/uapi/linux/bpf.h +2 -0

index aa5ccd2385ed..9d15c8f179ac 100644
@@ -252,6 +252,8 @@ enum bpf_attach_type {
 #define BPF_F_NO_COMMON_LRU    (1U << 1)
 /* Specify numa node during map creation */
 #define BPF_F_NUMA_NODE                (1U << 2)
+/* Zero-initialize hash function seed */
+#define BPF_F_ZERO_SEED                (1U << 6)
 
 /* flags for BPF_PROG_QUERY */
 #define BPF_F_QUERY_EFFECTIVE  (1U << 0)

kernel/bpf/hashtab.c +1 -1

index 2c1790288138..a79e123dae62 100644
@@ -23,7 +23,7 @@
 
 #define HTAB_CREATE_FLAG_MASK                                          \
        (BPF_F_NO_PREALLOC | BPF_F_NO_COMMON_LRU | BPF_F_NUMA_NODE |    \
-        BPF_F_RDONLY | BPF_F_WRONLY)
+        BPF_F_RDONLY | BPF_F_WRONLY | BPF_F_ZERO_SEED)
 
 struct bucket {
        struct hlist_nulls_head head;

If this is for testing only, you can slap a capable(CAP_SYS_ADMIN) check in here, right? I doubt it matters, but I don't really like seeing something like this exposed to unprivileged userspace just because you need it for kernel testing.

Quoted 5 lines · Jann Horn

If this is for testing only, you can slap a capable(CAP_SYS_ADMIN) check in here, right? I doubt it matters, but I don't really like seeing something like this exposed to unprivileged userspace just because you need it for kernel testing.

That would mean all tests have to run as root / with CAP_SYS_ADMIN which isn't ideal.

Quoted 9 lines · Lorenz Bauer

Quoted 5 lines · Jann Horn

If this is for testing only, you can slap a capable(CAP_SYS_ADMIN) check in here, right? I doubt it matters, but I don't really like seeing something like this exposed to unprivileged userspace just because you need it for kernel testing.

That would mean all tests have to run as root / with CAP_SYS_ADMIN which isn't ideal.

This patch basically means that it becomes easier for a local user to construct a BPF hash table that has all of its values stuffed into a single hash bucket, correct? Which makes it easier to create a BPF program that generates unusually large RCU stalls by performing ~40000 BPF map lookups, each of which has to walk through the entire linked list of the hash map bucket? I dislike exposing something like that to unprivileged userspace.

And if you want to run the whole BPF test suite with all its tests, don't you already need root privileges? Or is this a different test suite?

Quoted 10 lines · Jann Horn

Quoted 8 lines · Lorenz Bauer

Quoted 4 lines · Jann Horn

If this is for testing only, you can slap a capable(CAP_SYS_ADMIN) check in here, right? I doubt it matters, but I don't really like seeing something like this exposed to unprivileged userspace just because you need it for kernel testing.

That would mean all tests have to run as root / with CAP_SYS_ADMIN which isn't ideal.

Quoted 7 lines

This patch basically means that it becomes easier for a local user to construct a BPF hash table that has all of its values stuffed into a single hash bucket, correct? Which makes it easier to create a BPF program that generates unusually large RCU stalls by performing ~40000 BPF map lookups, each of which has to walk through the entire linked list of the hash map bucket? I dislike exposing something like that to unprivileged userspace.

That's a good point, for which I don't have an answer. You could argue that this was the status quo until the seed was randomised, so it seems like this hasn't been a worry so far. Should it be going forward?

Quoted 3 lines

And if you want to run the whole BPF test suite with all its tests, don't you already need root privileges? Or is this a different test suite?

No, I'm thinking about third parties that want to test their own BPF.

If you enable unprivileged BPF you can use BPF_PROG_TEST_RUN to test your programs without root, if I'm not mistaken.

Can you please describe exactly why something that is not a kernel unit test needs deterministic BPF hash map behavior?

Quoted 3 lines · Jann Horn

Can you please describe exactly why something that is not a kernel unit test needs deterministic BPF hash map behavior?

my use case for deterministic hashing is performance analysis. Both while developing and tuning bpf program and while optimizing kernel side implementation.
Local dos is a valid concern, so requiring root for this flag makes sense.

This patch set adds a new flag BPF_F_ZERO_SEED, which allows forcing the seed used by hash maps to zero. This makes it possible to write deterministic tests.

Based on an off-list conversation with Alexei Starovoitov and Daniel Borkmann.

Lorenz Bauer (3):
bpf: allow zero-initializing hash map seed
tools: sync linux/bpf.h
tools: add selftest for BPF_F_ZERO_SEED

 include/uapi/linux/bpf.h                |  2 +
 kernel/bpf/hashtab.c                    |  8 ++-
 tools/include/uapi/linux/bpf.h          |  2 +
 tools/testing/selftests/bpf/test_maps.c | 67 +++++++++++++++++++++----
 4 files changed, 66 insertions(+), 13 deletions(-)

Quoted 12 lines · Lorenz Bauer

This patch set adds a new flag BPF_F_ZERO_SEED, which allows forcing the seed used by hash maps to zero. This makes it possible to write deterministic tests.

Based on an off-list conversation with Alexei Starovoitov and Daniel Borkmann.

Lorenz Bauer (3):
bpf: allow zero-initializing hash map seed
tools: sync linux/bpf.h
tools: add selftest for BPF_F_ZERO_SEED

Quoted 6 lines

 include/uapi/linux/bpf.h                |  2 +
 kernel/bpf/hashtab.c                    |  8 ++-
 tools/include/uapi/linux/bpf.h          |  2 +
 tools/testing/selftests/bpf/test_maps.c | 67 +++++++++++++++++++++----
 4 files changed, 66 insertions(+), 13 deletions(-)

Please respin with proper SoB for each patch and non-empty commit description.

I think patch 1 should also have a more elaborate commit description on the use case for BPF_F_ZERO_SEED, and I

think also a better comment in the uapi header that this is only meant for testing and not production use.

Thanks,
Daniel

Quoted 21 lines · Daniel Borkmann

Quoted 18 lines · Lorenz Bauer

This patch set adds a new flag BPF_F_ZERO_SEED, which allows forcing the seed used by hash maps to zero. This makes it possible to write deterministic tests.

Based on an off-list conversation with Alexei Starovoitov and Daniel Borkmann.

Lorenz Bauer (3):
bpf: allow zero-initializing hash map seed
tools: sync linux/bpf.h
tools: add selftest for BPF_F_ZERO_SEED

 include/uapi/linux/bpf.h                |  2 +
 kernel/bpf/hashtab.c                    |  8 ++-
 tools/include/uapi/linux/bpf.h          |  2 +
 tools/testing/selftests/bpf/test_maps.c | 67 +++++++++++++++++++++----
 4 files changed, 66 insertions(+), 13 deletions(-)

Quoted 2 lines

Please respin with proper SoB for each patch and non-empty commit description.

What does SoB mean? Point taken about the empty commit message.

Add a new flag BPF_F_ZERO_SEED, which forces a hash map to initialize the seed to zero. This is useful when doing performance analysis both on individual BPF programs, as well as the kernel's hash table implementation.

Signed-off-by Lorenz Bauer <[email protected]>

---
 include/uapi/linux/bpf.h |  2 ++
 kernel/bpf/hashtab.c     | 13 +++++++++++--
 2 files changed, 13 insertions(+), 2 deletions(-)

include/uapi/linux/bpf.h +0 -0

index f9187b41dff6..2c121f862082 100644

include/uapi/linux/bpf.h +0 -0

 /* flags for BPF_PROG_QUERY */
 #define BPF_F_QUERY_EFFECTIVE  (1U << 0)

kernel/bpf/hashtab.c +11 -3

index 2c1790288138..4b7c76765d9d 100644
@@ -23,7 +23,7 @@
 
 #define HTAB_CREATE_FLAG_MASK                                          \
        (BPF_F_NO_PREALLOC | BPF_F_NO_COMMON_LRU | BPF_F_NUMA_NODE |    \
-        BPF_F_RDONLY | BPF_F_WRONLY)
+        BPF_F_RDONLY | BPF_F_WRONLY | BPF_F_ZERO_SEED)
 
 struct bucket {
        struct hlist_nulls_head head;

@@ -244,6 +244,7 @@ static int htab_map_alloc_check(union bpf_attr *attr)
         */
        bool percpu_lru = (attr->map_flags & BPF_F_NO_COMMON_LRU);
        bool prealloc = !(attr->map_flags & BPF_F_NO_PREALLOC);
+       bool zero_seed = (attr->map_flags & BPF_F_ZERO_SEED);
        int numa_node = bpf_map_attr_numa_node(attr);
 
        BUILD_BUG_ON(offsetof(struct htab_elem, htab) !=

@@ -257,6 +258,10 @@ static int htab_map_alloc_check(union bpf_attr *attr)
                 */
                return -EPERM;
 
+       if (zero_seed && !capable(CAP_SYS_ADMIN))
+               /* Guard against local DoS, and discourage production use. */
+               return -EPERM;
+
        if (attr->map_flags & ~HTAB_CREATE_FLAG_MASK)
                /* reserved bits should not be used */
                return -EINVAL;

@@ -373,7 +378,11 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
        if (!htab->buckets)
                goto free_htab;
 
-       htab->hashrnd = get_random_int();
+       if (htab->map.map_flags & BPF_F_ZERO_SEED)
+               htab->hashrnd = 0;
+       else
+               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);
--

2.17.1

include/uapi/linux/bpf.h enum bpf_attach_type { · line 257

Quoted 9 lines

include/uapi/linux/bpf.h +2 -0

@@ -253,6 +253,8 @@ enum bpf_attach_type {
 #define BPF_F_NO_COMMON_LRU    (1U << 1)
 /* Specify numa node during map creation */
 #define BPF_F_NUMA_NODE                (1U << 2)
+/* Zero-initialize hash function seed. This should only be used for testing. */
+#define BPF_F_ZERO_SEED                (1U << 6)

Please add this line after
#define BPF_F_STACK_BUILD_ID (1U << 5)

Quoted 12 lines · Song Liu

include/uapi/linux/bpf.h enum bpf_attach_type { · line 257

Quoted 9 lines

include/uapi/linux/bpf.h +2 -0

@@ -253,6 +253,8 @@ enum bpf_attach_type {
 #define BPF_F_NO_COMMON_LRU    (1U << 1)
 /* Specify numa node during map creation */
 #define BPF_F_NUMA_NODE                (1U << 2)
+/* Zero-initialize hash function seed. This should only be used for testing. */
+#define BPF_F_ZERO_SEED                (1U << 6)

Please add this line after
#define BPF_F_STACK_BUILD_ID (1U << 5)

I wanted to keep the flags for BPF_MAP_CREATE grouped together. Maybe the correct value is (1U << 3)? It seemed like the other flags were allocated to avoid
overlap between different BPF commands, however, so I tried to follow suit.

Synchronize changes to linux/bpf.h from
commit 88db241b34bf ("bpf: allow zero-initializing hash map seed").

Signed-off-by Lorenz Bauer <[email protected]>

---
 tools/include/uapi/linux/bpf.h | 2 ++
 1 file changed, 2 insertions(+)

tools/include/uapi/linux/bpf.h +0 -0

index f9187b41dff6..2c121f862082 100644

tools/include/uapi/linux/bpf.h +0 -1

 /* flags for BPF_PROG_QUERY */
 #define BPF_F_QUERY_EFFECTIVE  (1U << 0)
--

2.17.1

Quoted 3 lines · Lorenz Bauer

Synchronize changes to linux/bpf.h from
commit 88db241b34bf ("bpf: allow zero-initializing hash map seed").

I guess we cannot keep this hash during git-am? We probably don't need this hash anyway, as the two patches will be applied back to back.

Check that iterating two separate hash maps produces the same order of keys if BPF_F_ZERO_SEED is used.

Signed-off-by Lorenz Bauer <[email protected]>

---
 tools/testing/selftests/bpf/test_maps.c | 68 +++++++++++++++++++++----
 1 file changed, 57 insertions(+), 11 deletions(-)

tools/testing/selftests/bpf/test_maps.c +0 -0

index 9b552c0fc47d..a8d6af27803a 100644

tools/testing/selftests/bpf/test_maps.c +56 -12

+{
+       int i, fd, ret;
+       long long key, value;
+
+       fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
+                           max_entries, map_flags);
+       CHECK(fd < 0,
+             "failed to create hashmap",
+             "err: %s, flags: 0x%x\n", strerror(errno), map_flags);
+
+       for (i = 0; i < max_entries; i++) {
+               key = i; value = key;
+               ret = bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST);
+               CHECK(ret != 0,
+                     "can't update hashmap",
+                     "err: %s\n", strerror(ret));
+       }
+
+       return fd;
+}
+
 static void test_hashmap_walk(int task, void *data)
 {
        int fd, i, max_entries = 1000;
        long long key, value, next_key;
        bool next_key_valid = true;
 
-       fd = bpf_create_map(BPF_MAP_TYPE_HASH, sizeof(key), sizeof(value),
-                           max_entries, map_flags);
-       if (fd < 0) {
-               printf("Failed to create hashmap '%s'!\n", strerror(errno));
-               exit(1);
-       }
-
-       for (i = 0; i < max_entries; i++) {
-               key = i; value = key;
-               assert(bpf_map_update_elem(fd, &key, &value, BPF_NOEXIST) == 0);
-       }
+       fd = helper_fill_hashmap(max_entries);
 
        for (i = 0; bpf_map_get_next_key(fd, !i ? NULL : &key,
                                         &next_key) == 0; i++) {

@@ -305,6 +317,39 @@ static void test_hashmap_walk(int task, void *data)
        close(fd);
 }
 
+static void test_hashmap_zero_seed(void)
+{
+       int i, first, second, old_flags;
+       long long key, next_first, next_second;
+
+       old_flags = map_flags;
+       map_flags |= BPF_F_ZERO_SEED;
+
+       first = helper_fill_hashmap(3);
+       second = helper_fill_hashmap(3);
+
+       for (i = 0; ; i++) {
+               void *key_ptr = !i ? NULL : &key;
+
+               if (bpf_map_get_next_key(first, key_ptr, &next_first) != 0)
+                       break;
+
+               CHECK(bpf_map_get_next_key(second, key_ptr, &next_second) != 0,
+                     "next_key for second map must succeed",
+                     "key_ptr: %p", key_ptr);
+               CHECK(next_first != next_second,
+                     "keys must match",
+                     "i: %d first: %lld second: %lld\n", i,
+                     next_first, next_second);
+
+               key = next_first;
+       }
+
+       map_flags = old_flags;
+       close(first);
+       close(second);
+}
+
 static void test_arraymap(int task, void *data)
 {
        int key, next_key, fd;

@@ -1417,6 +1462,7 @@ static void run_all_tests(void)
        test_hashmap(0, NULL);
        test_hashmap_percpu(0, NULL);
        test_hashmap_walk(0, NULL);
+       test_hashmap_zero_seed();
 
        test_arraymap(0, NULL);
        test_arraymap_percpu(0, NULL);
--

2.17.1

Allow forcing the seed of a hash table to zero, for deterministic execution during benchmarking and testing.

Changes from v2:
* Change ordering of BPF_F_ZERO_SEED in linux/bpf.h

Comments adressed from v1:
* Add comment to discourage production use to linux/bpf.h
* Require CAP_SYS_ADMIN

Lorenz Bauer (4):
bpf: allow zero-initializing hash map seed
bpf: move BPF_F_QUERY_EFFECTIVE after map flags
tools: sync linux/bpf.h
tools: add selftest for BPF_F_ZERO_SEED

include/uapi/linux/bpf.h                |  9 ++--
kernel/bpf/hashtab.c                    | 13 ++++-
tools/include/uapi/linux/bpf.h          | 13 +++--
tools/testing/selftests/bpf/test_maps.c | 68 +++++++++++++++++++++----
4 files changed, 84 insertions(+), 19 deletions(-)

Signature · 1 line

2.17.1

Allow forcing the seed of a hash table to zero, for deterministic execution during benchmarking and testing.

Changes from v2:
* Change ordering of BPF_F_ZERO_SEED in linux/bpf.h

Comments adressed from v1:
* Add comment to discourage production use to linux/bpf.h
* Require CAP_SYS_ADMIN

Lorenz Bauer (4):
bpf: allow zero-initializing hash map seed
bpf: move BPF_F_QUERY_EFFECTIVE after map flags
tools: sync linux/bpf.h
tools: add selftest for BPF_F_ZERO_SEED

include/uapi/linux/bpf.h                |  9 ++--
kernel/bpf/hashtab.c                    | 13 ++++-
tools/include/uapi/linux/bpf.h          | 13 +++--
tools/testing/selftests/bpf/test_maps.c | 68 +++++++++++++++++++++----
4 files changed, 84 insertions(+), 19 deletions(-)

Signature · 1 line

2.17.1

Allow forcing the seed of a hash table to zero, for deterministic execution during benchmarking and testing.

Changes from v2:
* Change ordering of BPF_F_ZERO_SEED in linux/bpf.h

Comments adressed from v1:
* Add comment to discourage production use to linux/bpf.h
* Require CAP_SYS_ADMIN

Lorenz Bauer (4):
bpf: allow zero-initializing hash map seed
bpf: move BPF_F_QUERY_EFFECTIVE after map flags
tools: sync linux/bpf.h
tools: add selftest for BPF_F_ZERO_SEED

 include/uapi/linux/bpf.h                |  9 ++--
 kernel/bpf/hashtab.c                    | 13 ++++-
 tools/include/uapi/linux/bpf.h          | 13 +++--
 tools/testing/selftests/bpf/test_maps.c | 68 +++++++++++++++++++++----
 4 files changed, 84 insertions(+), 19 deletions(-)