[PATCH 0/3] bpf: allow zero-initialising hash map seed

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(-)

-- 
2.17.1

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(-)

diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index aa5ccd2385ed..9d15c8f179ac 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h

@@ -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)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 2c1790288138..a79e123dae62 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c

@@ -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;

@@ -373,7 +373,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

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

diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index aa5ccd2385ed..9d15c8f179ac 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h

@@ -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)

-- 
2.17.1

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

diff --git a/tools/testing/selftests/bpf/test_maps.c b/tools/testing/selftests/bpf/test_maps.c
index 9b552c0fc47d..2a1cc00475f6 100644
--- a/tools/testing/selftests/bpf/test_maps.c
+++ b/tools/testing/selftests/bpf/test_maps.c

@@ -257,23 +257,35 @@ static void test_hashmap_percpu(int task, void *data)
 	close(fd);
 }
 
+static int helper_fill_hashmap(int max_entries)
+{
+	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,38 @@ 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 +1461,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

On 10/01/2018 12:45 PM, Lorenz Bauer wrote:

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(-)

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

On Mon, Oct 1, 2018 at 12:47 PM Lorenz Bauer [off-list ref] wrote:

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.

On Tue, 2 Oct 2018 at 21:00, Jann Horn [off-list ref] wrote:

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.

-- 
Lorenz Bauer  |  Systems Engineer
25 Lavington St., London SE1 0NZ

www.cloudflare.com

On Fri, Oct 5, 2018 at 9:42 AM Lorenz Bauer [off-list ref] wrote:

On Tue, 2 Oct 2018 at 21:00, Jann Horn [off-list ref] wrote:

quoted

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?

On Fri, 5 Oct 2018 at 15:12, Jann Horn [off-list ref] wrote:

On Fri, Oct 5, 2018 at 9:42 AM Lorenz Bauer [off-list ref] wrote:

quoted

On Tue, 2 Oct 2018 at 21:00, Jann Horn [off-list ref] wrote:

quoted

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.

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?

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.
-- 
Lorenz Bauer  |  Systems Engineer
25 Lavington St., London SE1 0NZ

www.cloudflare.com

On Mon, 1 Oct 2018 at 20:12, Daniel Borkmann [off-list ref] wrote:

On 10/01/2018 12:45 PM, Lorenz Bauer wrote:

quoted

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(-)

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

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

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

This came out of the off-list discussion we had about map hash functions,
where Alexei expressed concern that your change to randomise the seed
might catch users off-guard. I personally don't have a use case, but decided
to tackle it since it seemed a simple-ish fix to get acquainted with
the code base.

Maybe this isn't needed after all?

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

Will do, if you decide that this is worth having in the first place.

Thanks,
Daniel

Lorenz

-- 
Lorenz Bauer  |  Systems Engineer
25 Lavington St., London SE1 0NZ

www.cloudflare.com

On Fri, Oct 5, 2018 at 4:21 PM Lorenz Bauer [off-list ref] wrote:

On Fri, 5 Oct 2018 at 15:12, Jann Horn [off-list ref] wrote:

quoted

On Fri, Oct 5, 2018 at 9:42 AM Lorenz Bauer [off-list ref] wrote:

quoted

On Tue, 2 Oct 2018 at 21:00, Jann Horn [off-list ref] wrote:

quoted

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.

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?

I don't think that local DoS bugs, or bugs that locally degrade
performance, are a big deal, but I also think that the kernel should
try to avoid having such issues.

quoted

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.

Ah. That wasn't clear to me from your patch description.

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

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

On Fri, Oct 5, 2018 at 4:27 PM Lorenz Bauer [off-list ref] wrote:

On Mon, 1 Oct 2018 at 20:12, Daniel Borkmann [off-list ref] wrote:

quoted

On 10/01/2018 12:45 PM, Lorenz Bauer wrote:

quoted

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(-)

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

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

SoB is the Signed-off-by line. See
https://www.kernel.org/doc/html/v4.17/process/submitting-patches.html#sign-your-work-the-developer-s-certificate-of-origin
.

On Fri, Oct 05, 2018 at 04:27:58PM +0200, Jann Horn wrote:

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.

On Fri, 5 Oct 2018 at 22:07, Alexei Starovoitov
[off-list ref] wrote:

On Fri, Oct 05, 2018 at 04:27:58PM +0200, Jann Horn wrote:

quoted

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.

Ok, I'll respin and address the comments.

-- 
Lorenz Bauer  |  Systems Engineer
25 Lavington St., London SE1 0NZ

www.cloudflare.com

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

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

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                    | 13 ++++-
 tools/include/uapi/linux/bpf.h          |  2 +
 tools/testing/selftests/bpf/test_maps.c | 68 +++++++++++++++++++++----
 4 files changed, 72 insertions(+), 13 deletions(-)

-- 
2.17.1

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 <redacted>
---
 include/uapi/linux/bpf.h |  2 ++
 kernel/bpf/hashtab.c     | 13 +++++++++++--
 2 files changed, 13 insertions(+), 2 deletions(-)

diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index f9187b41dff6..2c121f862082 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h

@@ -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)
 
 /* flags for BPF_PROG_QUERY */
 #define BPF_F_QUERY_EFFECTIVE	(1U << 0)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 2c1790288138..4b7c76765d9d 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c

@@ -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

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

Signed-off-by: Lorenz Bauer <redacted>
---
 tools/include/uapi/linux/bpf.h | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index f9187b41dff6..2c121f862082 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h

@@ -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)
 
 /* flags for BPF_PROG_QUERY */
 #define BPF_F_QUERY_EFFECTIVE	(1U << 0)

-- 
2.17.1

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 <redacted>
---
 tools/testing/selftests/bpf/test_maps.c | 68 +++++++++++++++++++++----
 1 file changed, 57 insertions(+), 11 deletions(-)

diff --git a/tools/testing/selftests/bpf/test_maps.c b/tools/testing/selftests/bpf/test_maps.c
index 9b552c0fc47d..a8d6af27803a 100644
--- a/tools/testing/selftests/bpf/test_maps.c
+++ b/tools/testing/selftests/bpf/test_maps.c

@@ -257,23 +257,35 @@ static void test_hashmap_percpu(int task, void *data)
 	close(fd);
 }
 
+static int helper_fill_hashmap(int max_entries)
+{
+	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

On Mon, Oct 8, 2018 at 3:34 AM Lorenz Bauer [off-list ref] wrote:

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

Other than this
Acked-by: Song Liu <redacted>

On Mon, Oct 8, 2018 at 3:34 AM Lorenz Bauer [off-list ref] wrote:

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.

Same as 01.

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

On Mon, Oct 8, 2018 at 3:34 AM Lorenz Bauer [off-list ref] wrote:

How about we add map_flags as the second argument of this function?
This will help
avoid the old_flags hack.

Thanks,
Song

On Tue, 9 Oct 2018 at 01:12, Song Liu [off-list ref] wrote:

On Mon, Oct 8, 2018 at 3:34 AM Lorenz Bauer [off-list ref] wrote:

quoted

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.

I copied what was done in one of the previous commits that synced the
header. I'm a bit at a
loss what to put in the commit message otherwise.

-- 
Lorenz Bauer  |  Systems Engineer
25 Lavington St., London SE1 0NZ

www.cloudflare.com

On Tue, 9 Oct 2018 at 01:08, Song Liu [off-list ref] wrote:

quoted

--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h

@@ -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.

-- 
Lorenz Bauer  |  Systems Engineer
25 Lavington St., London SE1 0NZ

www.cloudflare.com

On Thu, Oct 25, 2018 at 8:12 AM Lorenz Bauer [off-list ref] wrote:

On Tue, 9 Oct 2018 at 01:08, Song Liu [off-list ref] wrote:

quoted

quoted

--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h

@@ -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.

I think it should be (1U << 6). We probably should move BPF_F_QUERY_EFFECTIVE
to after BPF_F_STACK_BUILD_ID (and BPF_F_ZERO_SEED).

Also, please rebase against the latest bpf-next tree and resubmit the set.

Thanks,
Song

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(-)

-- 
2.17.1

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 <redacted>
---
 include/uapi/linux/bpf.h |  3 +++
 kernel/bpf/hashtab.c     | 13 +++++++++++--
 2 files changed, 14 insertions(+), 2 deletions(-)

diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 47d606d744cc..8c01b89a4cb4 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h

@@ -269,6 +269,9 @@ enum bpf_attach_type {
 /* Flag for stack_map, store build_id+offset instead of pointer */
 #define BPF_F_STACK_BUILD_ID	(1U << 5)
 
+/* Zero-initialize hash function seed. This should only be used for testing. */
+#define BPF_F_ZERO_SEED		(1U << 6)
+
 enum bpf_stack_build_id_status {
 	/* user space need an empty entry to identify end of a trace */
 	BPF_STACK_BUILD_ID_EMPTY = 0,

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 2c1790288138..4b7c76765d9d 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c

@@ -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

BPF_F_QUERY_EFFECTIVE is in the middle of the flags valid
for BPF_MAP_CREATE. Move it to its own section to reduce confusion.

Signed-off-by: Lorenz Bauer <redacted>
---
 include/uapi/linux/bpf.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 8c01b89a4cb4..05d95290b848 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h

@@ -257,9 +257,6 @@ enum bpf_attach_type {
 /* Specify numa node during map creation */
 #define BPF_F_NUMA_NODE		(1U << 2)
 
-/* flags for BPF_PROG_QUERY */
-#define BPF_F_QUERY_EFFECTIVE	(1U << 0)
-
 #define BPF_OBJ_NAME_LEN 16U
 
 /* Flags for accessing BPF object */

@@ -272,6 +269,9 @@ enum bpf_attach_type {
 /* Zero-initialize hash function seed. This should only be used for testing. */
 #define BPF_F_ZERO_SEED		(1U << 6)
 
+/* flags for BPF_PROG_QUERY */
+#define BPF_F_QUERY_EFFECTIVE	(1U << 0)
+
 enum bpf_stack_build_id_status {
 	/* user space need an empty entry to identify end of a trace */
 	BPF_STACK_BUILD_ID_EMPTY = 0,

-- 
2.17.1

Synchronize changes to linux/bpf.h from
* "bpf: allow zero-initializing hash map seed"
* "bpf: move BPF_F_QUERY_EFFECTIVE after map flags"

Signed-off-by: Lorenz Bauer <redacted>
---
 tools/include/uapi/linux/bpf.h | 13 ++++++++++---
 1 file changed, 10 insertions(+), 3 deletions(-)

diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index 852dc17ab47a..05d95290b848 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h

@@ -257,9 +257,6 @@ enum bpf_attach_type {
 /* Specify numa node during map creation */
 #define BPF_F_NUMA_NODE		(1U << 2)
 
-/* flags for BPF_PROG_QUERY */
-#define BPF_F_QUERY_EFFECTIVE	(1U << 0)
-
 #define BPF_OBJ_NAME_LEN 16U
 
 /* Flags for accessing BPF object */

@@ -269,6 +266,12 @@ enum bpf_attach_type {
 /* Flag for stack_map, store build_id+offset instead of pointer */
 #define BPF_F_STACK_BUILD_ID	(1U << 5)
 
+/* Zero-initialize hash function seed. This should only be used for testing. */
+#define BPF_F_ZERO_SEED		(1U << 6)
+
+/* flags for BPF_PROG_QUERY */
+#define BPF_F_QUERY_EFFECTIVE	(1U << 0)
+
 enum bpf_stack_build_id_status {
 	/* user space need an empty entry to identify end of a trace */
 	BPF_STACK_BUILD_ID_EMPTY = 0,

@@ -2201,6 +2204,8 @@ union bpf_attr {
  *		**CONFIG_NET** configuration option.
  *	Return
  *		Pointer to *struct bpf_sock*, or NULL in case of failure.
+ *		For sockets with reuseport option, *struct bpf_sock*
+ *		return is from reuse->socks[] using hash of the packet.
  *
  * struct bpf_sock *bpf_sk_lookup_udp(void *ctx, struct bpf_sock_tuple *tuple, u32 tuple_size, u32 netns, u64 flags)
  *	Description

@@ -2233,6 +2238,8 @@ union bpf_attr {
  *		**CONFIG_NET** configuration option.
  *	Return
  *		Pointer to *struct bpf_sock*, or NULL in case of failure.
+ *		For sockets with reuseport option, *struct bpf_sock*
+ *		return is from reuse->socks[] using hash of the packet.
  *
  * int bpf_sk_release(struct bpf_sock *sk)
  *	Description

-- 
2.17.1

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 <redacted>
---
 tools/testing/selftests/bpf/test_maps.c | 68 +++++++++++++++++++++----
 1 file changed, 57 insertions(+), 11 deletions(-)

diff --git a/tools/testing/selftests/bpf/test_maps.c b/tools/testing/selftests/bpf/test_maps.c
index 4db2116e52be..9f0a5b16a246 100644
--- a/tools/testing/selftests/bpf/test_maps.c
+++ b/tools/testing/selftests/bpf/test_maps.c

@@ -258,23 +258,35 @@ static void test_hashmap_percpu(int task, void *data)
 	close(fd);
 }
 
+static int helper_fill_hashmap(int max_entries)
+{
+	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++) {

@@ -306,6 +318,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;

@@ -1534,6 +1579,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

On Nov 16, 2018, at 3:41 AM, Lorenz Bauer [off-list ref] wrote:

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(-)

-- 
2.17.1

On Nov 16, 2018, at 3:41 AM, Lorenz Bauer [off-list ref] wrote:

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(-)

-- 
2.17.1

For the series:

Acked-by: Song Liu <redacted>

On 11/16/2018 12:41 PM, Lorenz Bauer wrote:

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(-)

Applied to bpf-next, thanks!