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

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

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

-- 
2.17.1

[PATCH 1/3] bpf: allow zero-initializing hash map seed

[Lorenz Bauer]

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

[PATCH 2/3] tools: sync linux/bpf.h

[Lorenz Bauer]

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

[PATCH 3/3] tools: add selftest for BPF_F_ZERO_SEED

[Lorenz Bauer]

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

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

[Daniel Borkmann]

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

Re: [PATCH 1/3] bpf: allow zero-initializing hash map seed

[Jann Horn]

On Mon, Oct 1, 2018 at 12:47 PM Lorenz Bauer <lmb@cloudflare.com> wrote:
>
> 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();
> +

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.

Re: [PATCH 1/3] bpf: allow zero-initializing hash map seed

[Lorenz Bauer]

On Tue, 2 Oct 2018 at 21:00, Jann Horn <jannh@google.com> 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

Re: [PATCH 1/3] bpf: allow zero-initializing hash map seed

[Jann Horn]

On Fri, Oct 5, 2018 at 9:42 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
> On Tue, 2 Oct 2018 at 21:00, Jann Horn <jannh@google.com> 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.

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?

Re: [PATCH 1/3] bpf: allow zero-initializing hash map seed

[Lorenz Bauer]

On Fri, 5 Oct 2018 at 15:12, Jann Horn <jannh@google.com> wrote:
>
> On Fri, Oct 5, 2018 at 9:42 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
> > On Tue, 2 Oct 2018 at 21:00, Jann Horn <jannh@google.com> 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.
>
> 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

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

[Lorenz Bauer]

On Mon, 1 Oct 2018 at 20:12, Daniel Borkmann <daniel@iogearbox.net> wrote:
>
> 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.

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

Re: [PATCH 1/3] bpf: allow zero-initializing hash map seed

[Jann Horn]

On Fri, Oct 5, 2018 at 4:21 PM Lorenz Bauer <lmb@cloudflare.com> wrote:
> On Fri, 5 Oct 2018 at 15:12, Jann Horn <jannh@google.com> wrote:
> > On Fri, Oct 5, 2018 at 9:42 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
> > > On Tue, 2 Oct 2018 at 21:00, Jann Horn <jannh@google.com> 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.
> >
> > 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.

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

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

[Jann Horn]

On Fri, Oct 5, 2018 at 4:27 PM Lorenz Bauer <lmb@cloudflare.com> wrote:
>
> On Mon, 1 Oct 2018 at 20:12, Daniel Borkmann <daniel@iogearbox.net> wrote:
> >
> > 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.
>
> 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
.

Re: [PATCH 1/3] bpf: allow zero-initializing hash map seed

[Alexei Starovoitov]

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.

Re: [PATCH 1/3] bpf: allow zero-initializing hash map seed

[Lorenz Bauer]

On Fri, 5 Oct 2018 at 22:07, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> 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.
>

Ok, I'll respin and address the comments.

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

www.cloudflare.com

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

[Lorenz Bauer]

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

[PATCH v2 1/3] bpf: allow zero-initializing hash map seed

[Lorenz Bauer]

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 <lmb@cloudflare.com>
---
 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

[PATCH v2 2/3] tools: sync linux/bpf.h

[Lorenz Bauer]

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

Signed-off-by: Lorenz Bauer <lmb@cloudflare.com>
---
 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

[PATCH v2 3/3] tools: add selftest for BPF_F_ZERO_SEED

[Lorenz Bauer]

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 <lmb@cloudflare.com>
---
 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

Re: [PATCH v2 1/3] bpf: allow zero-initializing hash map seed

[Song Liu]

On Mon, Oct 8, 2018 at 3:34 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
>
> 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 <lmb@cloudflare.com>
> ---
>  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)

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

Other than this
Acked-by: Song Liu <songliubraving@fb.com>


>
>  /* 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
>

Re: [PATCH v2 2/3] tools: sync linux/bpf.h

[Song Liu]

On Mon, Oct 8, 2018 at 3:34 AM Lorenz Bauer <lmb@cloudflare.com> 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.

>
> Signed-off-by: Lorenz Bauer <lmb@cloudflare.com>
> ---
>  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)

Same as 01.

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

Re: [PATCH v2 3/3] tools: add selftest for BPF_F_ZERO_SEED

[Song Liu]

On Mon, Oct 8, 2018 at 3:34 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
>
> 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 <lmb@cloudflare.com>
> ---
>  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)

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

Thanks,
Song

> +{
> +       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
>

Re: [PATCH v2 2/3] tools: sync linux/bpf.h

[Lorenz Bauer]

On Tue, 9 Oct 2018 at 01:12, Song Liu <liu.song.a23@gmail.com> wrote:
>
> On Mon, Oct 8, 2018 at 3:34 AM Lorenz Bauer <lmb@cloudflare.com> 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.

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

Re: [PATCH v2 1/3] bpf: allow zero-initializing hash map seed

[Lorenz Bauer]

On Tue, 9 Oct 2018 at 01:08, Song Liu <liu.song.a23@gmail.com> wrote:
>
> > --- 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

Re: [PATCH v2 1/3] bpf: allow zero-initializing hash map seed

[Song Liu]

On Thu, Oct 25, 2018 at 8:12 AM Lorenz Bauer <lmb@cloudflare.com> wrote:
>
> On Tue, 9 Oct 2018 at 01:08, Song Liu <liu.song.a23@gmail.com> wrote:
> >
> > > --- 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

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

[Lorenz Bauer]

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

[PATCH v3 1/4] bpf: allow zero-initializing hash map seed

[Lorenz Bauer]

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 <lmb@cloudflare.com>
---
 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

[PATCH v3 2/4] bpf: move BPF_F_QUERY_EFFECTIVE after map flags

[Lorenz Bauer]

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 <lmb@cloudflare.com>
---
 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

[PATCH v3 3/4] tools: sync linux/bpf.h

[Lorenz Bauer]

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 <lmb@cloudflare.com>
---
 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

[PATCH v3 4/4] tools: add selftest for BPF_F_ZERO_SEED

[Lorenz Bauer]

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 <lmb@cloudflare.com>
---
 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

Re: [PATCH v3 0/4] bpf: allow zero-initialising hash map seed

[Song Liu]

> On Nov 16, 2018, at 3:41 AM, Lorenz Bauer <lmb@cloudflare.com> 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
> 

Re: [PATCH v3 0/4] bpf: allow zero-initialising hash map seed

[Song Liu]

> On Nov 16, 2018, at 3:41 AM, Lorenz Bauer <lmb@cloudflare.com> 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 <songliubraving@fb.com>

Re: [PATCH v3 0/4] bpf: allow zero-initialising hash map seed

[Daniel Borkmann]

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!