bpf: Introduce resizable hash map
Subsystems (9)
v2 cover bpf: Introduce resizable hash map
This patch series introduces BPF_MAP_TYPE_RHASH, a new hash map type that leverages the kernel's rhashtable to provide resizable hash map for BPF.
The existing BPF_MAP_TYPE_HASH uses a fixed number of buckets determined at map creation time. While this works well for many use cases, it presents challenges when:
1. The number of elements is unknown at creation time
2. The element count varies significantly during runtime
3. Memory efficiency is important (over-provisioning wastes memory, under-provisioning hurts performance)
BPF_MAP_TYPE_RHASH addresses these issues by using rhashtable, which automatically grows and shrinks based on load factor.
The implementation wraps the kernel's rhashtable with BPF map operations:
- Uses bpf_mem_alloc for RCU-safe memory management
- Supports all standard map operations (lookup, update, delete, get_next_key)
- Supports batch operations (lookup_batch, lookup_and_delete_batch)
- Supports BPF iterators for traversal
- Supports BPF_F_LOCK for spin locks in values
- Requires BPF_F_NO_PREALLOC flag (elements allocated on demand)
- max_entries serves as a hard limit, not bucket count
The series includes comprehensive tests:
- Basic operations in test_maps (lookup, update, delete, get_next_key)
- BPF program tests for lookup/update/delete semantics
- BPF_F_LOCK tests with concurrent access
- Stress tests for get_next_key during concurrent resize operations
- Seq file tests
---
Current implementation of the BPF_MAP_TYPE_RHASH does not provide the same strong guarantees on the values consistency under concurrent reads/writes as BPF_MAP_TYPE_HASH.BPF_MAP_TYPE_HASH allocates a new element and atomically swaps the pointer, so RCU readers always see a complete value. BPF_MAP_TYPE_RHASH does memcpy in place with no lock held.
rhash trades consistency for speed (5x improvement in update benchmark):
concurrent readers can observe partially updated data. Two concurrent writers to the same key can also interleave, producing mixed values. As a solution, user may use BPF_F_LOCK to guarantee consistent reads and write serialization.
Summary of the read consistency guarantees:
map type | write mechanism | read consistency
-------------+------------------+--------------------------
htab | alloc, swap ptr | always consistent (RCU) htab F_LOCK | in-place + lock | consistent if reader locks -------------+------------------+-------------------------- rhtab | in-place memcpy | torn reads rhtab F_LOCK | in-place + lock | consistent if reader locks
Benchmarks and s390 tests depend on the
https://lore.kernel.org/linux-crypto/[email protected]/
Changes in v2:
- Added benchmarks
- Reworked all functions that walk the rhashtable, use walk API, instead of directly accessing tbl and future_tbl
- Added rhashtable_walk_enter_from() into rhashtable to support O(1) iteration continuations
- Link to v1: https://lore.kernel.org/r/[email protected]
---
Mykyta Yatsenko (18):
bpf: Register rhash map
bpf: Add resizable hashtab skeleton
bpf: Implement lookup, delete, update for resizable hashtab
rhashtable: Add rhashtable_walk_enter_from()
bpf: Implement get_next_key and free_internal_structs for resizable hashtab
bpf: Implement bpf_each_rhash_elem() using walk API
bpf: Implement batch ops for resizable hashtab
bpf: Implement iterator APIs for resizable hashtab
bpf: Implement alloc and free for resizable hashtab
bpf: Allow timers, workqueues and task_work in resizable hashtab
libbpf: Support resizable hashtable
selftests/bpf: Add basic tests for resizable hash map selftests/bpf: Support resizable hashtab in test_maps selftests/bpf: Resizable hashtab BPF_F_LOCK tests selftests/bpf: Add stress tests for resizable hash get_next_key selftests/bpf: Add BPF iterator tests for resizable hash map
bpftool: Add rhash map documentation
selftests/bpf: Add resizable hashmap to benchmarks
include/linux/bpf_types.h | 1 + include/linux/rhashtable.h | 31 +- include/uapi/linux/bpf.h | 1 + kernel/bpf/hashtab.c | 730 ++++++++++++++++++++- kernel/bpf/map_iter.c | 3 +- kernel/bpf/syscall.c | 4 + kernel/bpf/verifier.c | 1 + lib/rhashtable.c | 53 ++ lib/test_rhashtable.c | 120 ++++ tools/bpf/bpftool/Documentation/bpftool-map.rst | 2 +- tools/bpf/bpftool/map.c | 2 +- tools/include/uapi/linux/bpf.h | 1 + tools/lib/bpf/libbpf.c | 1 + tools/lib/bpf/libbpf_probes.c | 3 + tools/testing/selftests/bpf/bench.c | 6 + .../bpf/benchs/bench_bpf_hashmap_full_update.c | 34 +- .../bpf/benchs/bench_bpf_hashmap_lookup.c | 31 +- .../testing/selftests/bpf/benchs/bench_htab_mem.c | 35 +- .../selftests/bpf/map_tests/htab_map_batch_ops.c | 22 +- tools/testing/selftests/bpf/prog_tests/rhash.c | 502 ++++++++++++++ .../selftests/bpf/progs/bpf_iter_bpf_rhash_map.c | 75 +++ tools/testing/selftests/bpf/progs/rhash.c | 285 ++++++++ tools/testing/selftests/bpf/test_maps.c | 127 +++- 23 files changed, 2012 insertions(+), 58 deletions(-)
---
base-commit: b199f582a924e04f3f3b1050c484798034c61a12
change-id: 20251103-rhash-7b70069923d8
Best regards,
Signature · 1 line
Mykyta Yatsenko <[email protected]>
RFC PATCH v2 1/18 bpf: Register rhash map
From: Mykyta Yatsenko <[email protected]>
Add resizable hash map into enums where it is needed.
--- include/uapi/linux/bpf.h | 1 + kernel/bpf/map_iter.c | 3 ++- kernel/bpf/syscall.c | 3 +++ kernel/bpf/verifier.c | 1 + tools/include/uapi/linux/bpf.h | 1 + 5 files changed, 8 insertions(+), 1 deletion(-)
include/uapi/linux/bpf.h +1 -0
@@ -1046,6 +1046,7 @@ enum bpf_map_type {BPF_MAP_TYPE_CGRP_STORAGE ,BPF_MAP_TYPE_ARENA ,BPF_MAP_TYPE_INSN_ARRAY , +BPF_MAP_TYPE_RHASH , __MAX_BPF_MAP_TYPE };
kernel/bpf/map_iter.c +2 -1
@@ -119,7 +119,8 @@ static int bpf_iter_attach_map(struct bpf_prog *prog, is_percpu = true; else if (map->map_type != BPF_MAP_TYPE_HASH && map->map_type != BPF_MAP_TYPE_LRU_HASH && - map->map_type != BPF_MAP_TYPE_ARRAY) + map->map_type != BPF_MAP_TYPE_ARRAY && + map->map_type != BPF_MAP_TYPE_RHASH) goto put_map; key_acc_size = prog->aux->max_rdonly_access;
kernel/bpf/syscall.c +3 -0
@@ -1287,6 +1287,7 @@ static int map_check_btf(struct bpf_map *map, struct bpf_token *token,case BPF_SPIN_LOCK :case BPF_RES_SPIN_LOCK : if (map->map_type != BPF_MAP_TYPE_HASH && + map->map_type != BPF_MAP_TYPE_RHASH && map->map_type != BPF_MAP_TYPE_ARRAY && map->map_type != BPF_MAP_TYPE_CGROUP_STORAGE && map->map_type != BPF_MAP_TYPE_SK_STORAGE &&
@@ -1464,6 +1465,7 @@ static int map_create(union bpf_attr *attr, bpfptr_t uattr)case BPF_MAP_TYPE_CGROUP_ARRAY :case BPF_MAP_TYPE_ARRAY_OF_MAPS :case BPF_MAP_TYPE_HASH : +case BPF_MAP_TYPE_RHASH :case BPF_MAP_TYPE_PERCPU_HASH :case BPF_MAP_TYPE_HASH_OF_MAPS :case BPF_MAP_TYPE_RINGBUF :
@@ -2199,6 +2201,7 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr) map->map_type ==BPF_MAP_TYPE_PERCPU_HASH || map->map_type ==BPF_MAP_TYPE_LRU_HASH || map->map_type ==BPF_MAP_TYPE_LRU_PERCPU_HASH || + map->map_type ==BPF_MAP_TYPE_RHASH || map->map_type == BPF_MAP_TYPE_STACK_TRACE) { if (!bpf_map_is_offloaded(map)) {bpf_disable_instrumentation ();
kernel/bpf/verifier.c +1 -0
@@ -21816,6 +21816,7 @@ static int check_map_prog_compatibility(struct bpf_verifier_env *env,if (prog->sleepable)switch (map->map_type) {case BPF_MAP_TYPE_HASH : +case BPF_MAP_TYPE_RHASH :case BPF_MAP_TYPE_LRU_HASH :case BPF_MAP_TYPE_ARRAY :case BPF_MAP_TYPE_PERCPU_HASH :
tools/include/uapi/linux/bpf.h +1 -0
@@ -1046,6 +1046,7 @@ enum bpf_map_type {BPF_MAP_TYPE_CGRP_STORAGE ,BPF_MAP_TYPE_ARENA ,BPF_MAP_TYPE_INSN_ARRAY , +BPF_MAP_TYPE_RHASH , __MAX_BPF_MAP_TYPE };
Signature · 1 line
2.52.0
Emil Tsalapatis
reviewerRe: [PATCH RFC bpf-next v2 01/18] bpf: Register rhash map
Quoted 4 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Add resizable hash map into enums where it is needed.
These changes in isolation are difficult to reason about, can we roll this into subsequent patches? Right now this adds a the BPF_MAP_TYPE_RHASH without there being a way to create one.
Quoted 87 lines
Signed-off-by Mykyta Yatsenko <[email protected]>--- include/uapi/linux/bpf.h | 1 + kernel/bpf/map_iter.c | 3 ++- kernel/bpf/syscall.c | 3 +++ kernel/bpf/verifier.c | 1 + tools/include/uapi/linux/bpf.h | 1 + 5 files changed, 8 insertions(+), 1 deletion(-)include/uapi/linux/bpf.h +1
-0@@ -1046,6 +1046,7 @@ enum bpf_map_type {BPF_MAP_TYPE_CGRP_STORAGE ,BPF_MAP_TYPE_ARENA ,BPF_MAP_TYPE_INSN_ARRAY , +BPF_MAP_TYPE_RHASH , __MAX_BPF_MAP_TYPE };kernel/bpf/map_iter.c +2
-1@@ -119,7 +119,8 @@ static int bpf_iter_attach_map(struct bpf_prog *prog, is_percpu = true; else if (map->map_type != BPF_MAP_TYPE_HASH && map->map_type != BPF_MAP_TYPE_LRU_HASH && - map->map_type != BPF_MAP_TYPE_ARRAY) + map->map_type != BPF_MAP_TYPE_ARRAY && + map->map_type != BPF_MAP_TYPE_RHASH) goto put_map; key_acc_size = prog->aux->max_rdonly_access;kernel/bpf/syscall.c +3
-0@@ -1287,6 +1287,7 @@ static int map_check_btf(struct bpf_map *map, struct bpf_token *token,case BPF_SPIN_LOCK :case BPF_RES_SPIN_LOCK : if (map->map_type != BPF_MAP_TYPE_HASH && + map->map_type != BPF_MAP_TYPE_RHASH && map->map_type != BPF_MAP_TYPE_ARRAY && map->map_type != BPF_MAP_TYPE_CGROUP_STORAGE && map->map_type != BPF_MAP_TYPE_SK_STORAGE &&@@ -1464,6 +1465,7 @@ static int map_create(union bpf_attr *attr, bpfptr_t uattr)case BPF_MAP_TYPE_CGROUP_ARRAY :case BPF_MAP_TYPE_ARRAY_OF_MAPS :case BPF_MAP_TYPE_HASH : +case BPF_MAP_TYPE_RHASH :case BPF_MAP_TYPE_PERCPU_HASH :case BPF_MAP_TYPE_HASH_OF_MAPS :case BPF_MAP_TYPE_RINGBUF :@@ -2199,6 +2201,7 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr) map->map_type ==BPF_MAP_TYPE_PERCPU_HASH || map->map_type ==BPF_MAP_TYPE_LRU_HASH || map->map_type ==BPF_MAP_TYPE_LRU_PERCPU_HASH || + map->map_type ==BPF_MAP_TYPE_RHASH || map->map_type == BPF_MAP_TYPE_STACK_TRACE) { if (!bpf_map_is_offloaded(map)) {bpf_disable_instrumentation ();kernel/bpf/verifier.c +1
-0@@ -21816,6 +21816,7 @@ static int check_map_prog_compatibility(struct bpf_verifier_env *env,if (prog->sleepable)switch (map->map_type) {case BPF_MAP_TYPE_HASH : +case BPF_MAP_TYPE_RHASH :case BPF_MAP_TYPE_LRU_HASH :case BPF_MAP_TYPE_ARRAY :case BPF_MAP_TYPE_PERCPU_HASH :tools/include/uapi/linux/bpf.h +1
-0@@ -1046,6 +1046,7 @@ enum bpf_map_type {BPF_MAP_TYPE_CGRP_STORAGE ,BPF_MAP_TYPE_ARENA ,BPF_MAP_TYPE_INSN_ARRAY , +BPF_MAP_TYPE_RHASH , __MAX_BPF_MAP_TYPE };
Re: [PATCH RFC bpf-next v2 01/18] bpf: Register rhash map
Quoted 11 lines · Emil Tsalapatis
Quoted 4 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Add resizable hash map into enums where it is needed.
These changes in isolation are difficult to reason about, can we roll this into subsequent patches? Right now this adds a the
BPF_MAP_TYPE_RHASHwithout there being a way to create one.
Thanks for taking a look, makes sense, I can squash it into the latter commits.
Quoted 88 lines
Quoted 87 lines
Signed-off-by Mykyta Yatsenko <[email protected]>--- include/uapi/linux/bpf.h | 1 + kernel/bpf/map_iter.c | 3 ++- kernel/bpf/syscall.c | 3 +++ kernel/bpf/verifier.c | 1 + tools/include/uapi/linux/bpf.h | 1 + 5 files changed, 8 insertions(+), 1 deletion(-)include/uapi/linux/bpf.h +1
-0@@ -1046,6 +1046,7 @@ enum bpf_map_type {BPF_MAP_TYPE_CGRP_STORAGE ,BPF_MAP_TYPE_ARENA ,BPF_MAP_TYPE_INSN_ARRAY , +BPF_MAP_TYPE_RHASH , __MAX_BPF_MAP_TYPE };kernel/bpf/map_iter.c +2
-1@@ -119,7 +119,8 @@ static int bpf_iter_attach_map(struct bpf_prog *prog, is_percpu = true; else if (map->map_type != BPF_MAP_TYPE_HASH && map->map_type != BPF_MAP_TYPE_LRU_HASH && - map->map_type != BPF_MAP_TYPE_ARRAY) + map->map_type != BPF_MAP_TYPE_ARRAY && + map->map_type != BPF_MAP_TYPE_RHASH) goto put_map; key_acc_size = prog->aux->max_rdonly_access;kernel/bpf/syscall.c +3
-0@@ -1287,6 +1287,7 @@ static int map_check_btf(struct bpf_map *map, struct bpf_token *token,case BPF_SPIN_LOCK :case BPF_RES_SPIN_LOCK : if (map->map_type != BPF_MAP_TYPE_HASH && + map->map_type != BPF_MAP_TYPE_RHASH && map->map_type != BPF_MAP_TYPE_ARRAY && map->map_type != BPF_MAP_TYPE_CGROUP_STORAGE && map->map_type != BPF_MAP_TYPE_SK_STORAGE &&@@ -1464,6 +1465,7 @@ static int map_create(union bpf_attr *attr, bpfptr_t uattr)case BPF_MAP_TYPE_CGROUP_ARRAY :case BPF_MAP_TYPE_ARRAY_OF_MAPS :case BPF_MAP_TYPE_HASH : +case BPF_MAP_TYPE_RHASH :case BPF_MAP_TYPE_PERCPU_HASH :case BPF_MAP_TYPE_HASH_OF_MAPS :case BPF_MAP_TYPE_RINGBUF :@@ -2199,6 +2201,7 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr) map->map_type ==BPF_MAP_TYPE_PERCPU_HASH || map->map_type ==BPF_MAP_TYPE_LRU_HASH || map->map_type ==BPF_MAP_TYPE_LRU_PERCPU_HASH || + map->map_type ==BPF_MAP_TYPE_RHASH || map->map_type == BPF_MAP_TYPE_STACK_TRACE) { if (!bpf_map_is_offloaded(map)) {bpf_disable_instrumentation ();kernel/bpf/verifier.c +1
-0@@ -21816,6 +21816,7 @@ static int check_map_prog_compatibility(struct bpf_verifier_env *env,if (prog->sleepable)switch (map->map_type) {case BPF_MAP_TYPE_HASH : +case BPF_MAP_TYPE_RHASH :case BPF_MAP_TYPE_LRU_HASH :case BPF_MAP_TYPE_ARRAY :case BPF_MAP_TYPE_PERCPU_HASH :tools/include/uapi/linux/bpf.h +1
-0@@ -1046,6 +1046,7 @@ enum bpf_map_type {BPF_MAP_TYPE_CGRP_STORAGE ,BPF_MAP_TYPE_ARENA ,BPF_MAP_TYPE_INSN_ARRAY , +BPF_MAP_TYPE_RHASH , __MAX_BPF_MAP_TYPE };
Re: [PATCH RFC bpf-next v2 01/18] bpf: Register rhash map
Quoted 7 lines · Mykyta Yatsenko
Quoted 6 lines · Emil Tsalapatis
Quoted 4 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Add resizable hash map into enums where it is needed.
Quoted 9 lines
Quoted 5 lines
These changes in isolation are difficult to reason about, can we roll this into subsequent patches? Right now this adds a the
BPF_MAP_TYPE_RHASHwithout there being a way to create one.Thanks for taking a look, makes sense, I can squash it into the latter commits.
For the squashed commit:
Quoted 88 lines
Quoted 88 lines
Quoted 87 lines
Signed-off-by Mykyta Yatsenko <[email protected]>--- include/uapi/linux/bpf.h | 1 + kernel/bpf/map_iter.c | 3 ++- kernel/bpf/syscall.c | 3 +++ kernel/bpf/verifier.c | 1 + tools/include/uapi/linux/bpf.h | 1 + 5 files changed, 8 insertions(+), 1 deletion(-)include/uapi/linux/bpf.h +1
-0@@ -1046,6 +1046,7 @@ enum bpf_map_type {BPF_MAP_TYPE_CGRP_STORAGE ,BPF_MAP_TYPE_ARENA ,BPF_MAP_TYPE_INSN_ARRAY , +BPF_MAP_TYPE_RHASH , __MAX_BPF_MAP_TYPE };kernel/bpf/map_iter.c +2
-1@@ -119,7 +119,8 @@ static int bpf_iter_attach_map(struct bpf_prog *prog, is_percpu = true; else if (map->map_type != BPF_MAP_TYPE_HASH && map->map_type != BPF_MAP_TYPE_LRU_HASH && - map->map_type != BPF_MAP_TYPE_ARRAY) + map->map_type != BPF_MAP_TYPE_ARRAY && + map->map_type != BPF_MAP_TYPE_RHASH) goto put_map; key_acc_size = prog->aux->max_rdonly_access;kernel/bpf/syscall.c +3
-0@@ -1287,6 +1287,7 @@ static int map_check_btf(struct bpf_map *map, struct bpf_token *token,case BPF_SPIN_LOCK :case BPF_RES_SPIN_LOCK : if (map->map_type != BPF_MAP_TYPE_HASH && + map->map_type != BPF_MAP_TYPE_RHASH && map->map_type != BPF_MAP_TYPE_ARRAY && map->map_type != BPF_MAP_TYPE_CGROUP_STORAGE && map->map_type != BPF_MAP_TYPE_SK_STORAGE &&@@ -1464,6 +1465,7 @@ static int map_create(union bpf_attr *attr, bpfptr_t uattr)case BPF_MAP_TYPE_CGROUP_ARRAY :case BPF_MAP_TYPE_ARRAY_OF_MAPS :case BPF_MAP_TYPE_HASH : +case BPF_MAP_TYPE_RHASH :case BPF_MAP_TYPE_PERCPU_HASH :case BPF_MAP_TYPE_HASH_OF_MAPS :case BPF_MAP_TYPE_RINGBUF :@@ -2199,6 +2201,7 @@ static int map_lookup_and_delete_elem(union bpf_attr *attr) map->map_type ==BPF_MAP_TYPE_PERCPU_HASH || map->map_type ==BPF_MAP_TYPE_LRU_HASH || map->map_type ==BPF_MAP_TYPE_LRU_PERCPU_HASH || + map->map_type ==BPF_MAP_TYPE_RHASH || map->map_type == BPF_MAP_TYPE_STACK_TRACE) { if (!bpf_map_is_offloaded(map)) {bpf_disable_instrumentation ();kernel/bpf/verifier.c +1
-0@@ -21816,6 +21816,7 @@ static int check_map_prog_compatibility(struct bpf_verifier_env *env,if (prog->sleepable)switch (map->map_type) {case BPF_MAP_TYPE_HASH : +case BPF_MAP_TYPE_RHASH :case BPF_MAP_TYPE_LRU_HASH :case BPF_MAP_TYPE_ARRAY :case BPF_MAP_TYPE_PERCPU_HASH :tools/include/uapi/linux/bpf.h +1
-0@@ -1046,6 +1046,7 @@ enum bpf_map_type {BPF_MAP_TYPE_CGRP_STORAGE ,BPF_MAP_TYPE_ARENA ,BPF_MAP_TYPE_INSN_ARRAY , +BPF_MAP_TYPE_RHASH , __MAX_BPF_MAP_TYPE };
RFC PATCH v2 2/18 bpf: Add resizable hashtab skeleton
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Added a skeleton for resizable hashtab. Actual implementation follows in the next patches of the series.
--- include/linux/bpf_types.h | 1 + kernel/bpf/hashtab.c | 166 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 167 insertions(+)
include/linux/bpf_types.h +1 -0
@@ -134,6 +134,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_BLOOM_FILTER, bloom_filter_map_ops) BPF_MAP_TYPE(BPF_MAP_TYPE_USER_RINGBUF, user_ringbuf_map_ops) BPF_MAP_TYPE(BPF_MAP_TYPE_ARENA, arena_map_ops) BPF_MAP_TYPE(BPF_MAP_TYPE_INSN_ARRAY, insn_array_map_ops) +BPF_MAP_TYPE(BPF_MAP_TYPE_RHASH, rhtab_map_ops) BPF_LINK_TYPE(BPF_LINK_TYPE_RAW_TRACEPOINT, raw_tracepoint)BPF_LINK_TYPE (BPF_LINK_TYPE_TRACING , tracing)
kernel/bpf/hashtab.c +166 -0
187 lines not on this page · raw message
Signature · 1 line
2.52.0
RFC PATCH v2 3/18 bpf: Implement lookup, delete, update for resizable hashtab
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Use rhashtable_lookup_likely() for lookups, rhashtable_remove_fast() for deletes, and rhashtable_lookup_get_insert_fast() for inserts.
Updates modify values in place under RCU rather than allocating a new element and swapping the pointer (as regular htab does). This trades read consistency for performance: concurrent readers may see partial updates. Users requiring consistent reads should use BPF_F_LOCK.
--- kernel/bpf/hashtab.c | 141 ++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 134 insertions(+), 7 deletions(-)
kernel/bpf/hashtab.c +134 -7
@@ -2755,6 +2755,11 @@ struct bpf_rhtab {u32 elem_size; }; +static inline void *rhtab_elem_value (struct rhtab_elem *l,u32 key_size) +{ +return l->data +round_up (key_size,8 ); +} +static struct bpf_map *rhtab_map_alloc (union bpf_attr *attr) {return ERR_PTR (-EOPNOTSUPP );
@@ -2769,33 +2774,155 @@ static void rhtab_map_free(struct bpf_map *map) { } +static void *rhtab_lookup_elem (struct bpf_map *map,void *key) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +/* Using constant zeroed params to force rhashtable use inlined hashfunc */ +static const struct rhashtable_params params = {0 }; + +return rhashtable_lookup_likely (&rhtab->ht, key, params); +} +static void *rhtab_map_lookup_elem (struct bpf_map *map,void *key)__must_hold (RCU ) { -return NULL ; +struct rhtab_elem *l; + + l =rhtab_lookup_elem (map, key); +return l ?rhtab_elem_value (l, map->key_size) :NULL ; +} + +static int rhtab_delete_elem (struct bpf_rhtab *rhtab,struct rhtab_elem *elem) +{ +int err; + + err =rhashtable_remove_fast (&rhtab->ht, &elem->node, rhtab->params); +if (err) +return err; + +bpf_map_free_internal_structs (&rhtab->map,rhtab_elem_value (elem, rhtab->map.key_size)); +bpf_mem_cache_free_rcu (&rhtab->ma, elem); +return 0 ; }static long rhtab_map_delete_elem (struct bpf_map *map,void *key) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *l; + +guard (rcu)(); + l =rhtab_lookup_elem (map, key); +return l ?rhtab_delete_elem (rhtab, l) : -ENOENT ; +} + +static void rhtab_read_elem_value (struct bpf_map *map,void *dst,struct rhtab_elem *elem, +u64 flags) +{ +void *src =rhtab_elem_value (elem, map->key_size); + +if (flags &BPF_F_LOCK ) +copy_map_value_locked (map, dst, src, true); +else +copy_map_value (map, dst, src); }static int rhtab_map_lookup_and_delete_elem (struct bpf_map *map,void *key,void *value,u64 flags) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *l; +int err; + +if ((flags & ~BPF_F_LOCK ) || + ((flags &BPF_F_LOCK ) && !btf_record_has_field (map->record,BPF_SPIN_LOCK ))) +return -EINVAL ; + +/* Make sure element is not deleted between lookup and copy */ +guard (rcu)(); + + l =rhtab_lookup_elem (map, key); +if (!l) +return -ENOENT ; + +rhtab_read_elem_value (map, value, l, flags); + err =rhtab_delete_elem (rhtab, l); +if (err) +return err; + +check_and_init_map_value (map, value); +return 0 ; } -static long rhtab_map_update_elem (struct bpf_map *map,void *key,void *value,u64 map_flags) +static long rhtab_map_update_existing (struct bpf_map *map,struct rhtab_elem *elem,void *value, +u64 map_flags) { -return -EOPNOTSUPP ; +if (map_flags &BPF_NOEXIST ) +return -EEXIST ; + +if (map_flags &BPF_F_LOCK ) +copy_map_value_locked (map,rhtab_elem_value (elem, map->key_size), value, false); +else +copy_map_value (map,rhtab_elem_value (elem, map->key_size), value); +return 0 ; } -static void rhtab_map_free_internal_structs (struct bpf_map *map) +static long rhtab_map_update_elem (struct bpf_map *map,void *key,void *value,u64 map_flags) { + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *elem, *tmp; + +if (unlikely ((map_flags & ~BPF_F_LOCK ) >BPF_EXIST )) +return -EINVAL ; + +if ((map_flags &BPF_F_LOCK ) && !btf_record_has_field (map->record,BPF_SPIN_LOCK )) +return -EINVAL ; + +guard (rcu)(); + elem =rhtab_lookup_elem (map, key); +if (elem) +return rhtab_map_update_existing (map, elem, value, map_flags); + +if (map_flags &BPF_EXIST ) +return -ENOENT ; + +/* Check max_entries limit before inserting new element */ +if (atomic_read (&rhtab->ht.nelems) >= map->max_entries) +return -E2BIG ; + + elem =bpf_mem_cache_alloc (&rhtab->ma); +if (!elem) +return -ENOMEM ; + +memcpy (elem->data, key, map->key_size); +copy_map_value (map,rhtab_elem_value (elem, map->key_size), value); + + tmp =rhashtable_lookup_get_insert_fast (&rhtab->ht, &elem->node, rhtab->params); +if (tmp) { +bpf_mem_cache_free (&rhtab->ma, elem); +if (IS_ERR (tmp)) +return PTR_ERR (tmp); + +return rhtab_map_update_existing (map, tmp, value, map_flags); + } + +return 0 ; }static int rhtab_map_gen_lookup (struct bpf_map *map,struct bpf_insn *insn_buf) { -return -EOPNOTSUPP ; +struct bpf_insn *insn = insn_buf; +const int ret =BPF_REG_0 ; + +BUILD_BUG_ON (!__same_type (&rhtab_lookup_elem, + (void *(*)(struct bpf_map *map,void *key))NULL )); + *insn++ =BPF_EMIT_CALL (rhtab_lookup_elem); + *insn++ =BPF_JMP_IMM (BPF_JEQ , ret,0 ,1 ); + *insn++ =BPF_ALU64_IMM (BPF_ADD , ret, + offsetof(struct rhtab_elem , data) +round_up (map->key_size,8 )); + +return insn - insn_buf; +} + +static void rhtab_map_free_internal_structs (struct bpf_map *map) +{ }static int rhtab_map_get_next_key (struct bpf_map *map,void *key,void *next_key)
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 03/18] bpf: Implement lookup, delete, update for resizable hashtab
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2783
Quoted 9 lines · Mykyta Yatsenko
kernel/bpf/hashtab.c +7
-0+static void *rhtab_lookup_elem (struct bpf_map *map,void *key) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +/* Using constant zeroed params to force rhashtable use inlined hashfunc */ +static const struct rhashtable_params params = {0 }; + +return rhashtable_lookup_likely (&rhtab->ht, key, params);
How does the asm look like?
Please share 'perf report' or 'perf annotate' for lookup. Maybe worth it to include in commit log.
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2774
Quoted 5 lines
kernel/bpf/hashtab.c +2
-1+} +static void *rhtab_map_lookup_elem (struct bpf_map *map,void *key)__must_hold (RCU ) { -return NULL ;
imo there is no point in such a step by step introduction. Patches 1,2,3 can be squashed.
Re: [PATCH RFC bpf-next v2 03/18] bpf: Implement lookup, delete, update for resizable hashtab
Quoted 4 lines · Alexei Starovoitov
Quoted 2 lines · Mykyta Yatsenko
Quoted 9 lines
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2783
Quoted 7 lines
kernel/bpf/hashtab.c +7
-0+static void *rhtab_lookup_elem (struct bpf_map *map,void *key) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +/* Using constant zeroed params to force rhashtable use inlined hashfunc */ +static const struct rhashtable_params params = {0 }; + +return rhashtable_lookup_likely (&rhtab->ht, key, params);How does the asm look like?
You can see how asm looks like below. An interesting thing is that gcc inlines jhash2, but not clang, which costs a lot of performance.
gcc:
lookup 20.675M ± 0.090M events/sec (approximated from 32 samples of ~48ms)
clang:
cpu00: lookup 15.882M ± 0.530M events/sec (approximated from 32 samples of ~62ms)
I think inlining is also consistent for htab and rhtab (either both inline or both do not inline).
perf annotate on gcc:
Percent | Source code & Disassembly of vmlinux for cpu/cycles/P (18251
samples, percent: local period)
------------------------------------------------------------------------------------------------------------
: 0 0xffffffff8146b630 <rhtab_lookup_elem>:
0.00 : ffffffff8146b630: endbr64
0.10 : ffffffff8146b634: callq 0xffffffff8126c6c0
<__fentry__>
0.00 : ffffffff8146b639: pushq %r15
0.70 : ffffffff8146b63b: pushq %r14
0.03 : ffffffff8146b63d: pushq %r13
0.56 : ffffffff8146b63f: pushq %r12
0.00 : ffffffff8146b641: pushq %rbp
0.00 : ffffffff8146b642: movq %rsi, %rbp
0.00 : ffffffff8146b645: pushq %rbx
0.06 : ffffffff8146b646: movq %rdi, %rbx
0.00 : ffffffff8146b649: subq $0x18, %rsp
0.02 : ffffffff8146b64d: movq 0x120(%rdi), %r12
2.58 : ffffffff8146b654: movzwl 0x132(%rbx), %r8d
0.00 : ffffffff8146b65c: movl 0x8(%r12), %edx
0.12 : ffffffff8146b661: movl %r8d, %eax
0.00 : ffffffff8146b664: movl %r8d, %esi
0.00 : ffffffff8146b667: testb $0x3, %al
0.00 : ffffffff8146b669: je 0xffffffff8146b726
<rhtab_lookup_elem+0xf6>
0.00 : ffffffff8146b66f: movq %rbp, %rdi
0.00 : ffffffff8146b672: callq 0xffffffff81467bd0 <jhash>
0.00 : ffffffff8146b677: movl (%r12), %esi
0.13 : ffffffff8146b67b: subl $0x1, %esi
1.91 : ffffffff8146b67e: andl %eax, %esi
0.00 : ffffffff8146b680: movl %esi, %eax
0.01 : ffffffff8146b682: leaq 0x40(%r12,%rax,8), %r14
2.80 : ffffffff8146b687: movl 0x4(%r12), %eax
0.01 : ffffffff8146b68c: testl %eax, %eax
0.01 : ffffffff8146b68e: jne 0xffffffff8146b821
<rhtab_lookup_elem+0x1f1>
0.00 : ffffffff8146b694: movq %r14, %rax
2.41 : ffffffff8146b697: orq $0x1, %rax
0.00 : ffffffff8146b69b: movq %rax, 0x8(%rsp)
2.63 : ffffffff8146b6a0: movq (%r14), %rcx
13.96 : ffffffff8146b6a3: andq $-0x2, %rcx
0.01 : ffffffff8146b6a7: cmoveq 0x8(%rsp), %rcx
0.02 : ffffffff8146b6ad: movq %rcx, %r15
0.00 : ffffffff8146b6b0: testb $0x1, %cl
0.06 : ffffffff8146b6b3: jne 0xffffffff8146b809
<rhtab_lookup_elem+0x1d9>
0.00 : ffffffff8146b6b9: movzwl 0x136(%rbx), %eax
0.00 : ffffffff8146b6c0: movzwl 0x134(%rbx), %r13d
0.00 : ffffffff8146b6c8: movzwl 0x132(%rbx), %edx
0.00 : ffffffff8146b6cf: movq %rax, 0x10(%rsp)
2.15 : ffffffff8146b6d4: subq %rax, %r13
0.00 : ffffffff8146b6d7: leaq (%r15,%r13), %rdi
0.04 : ffffffff8146b6db: movq %rbp, %rsi
0.00 : ffffffff8146b6de: movq %rdx, (%rsp)
1.13 : ffffffff8146b6e2: callq 0xffffffff81eaa020 <memcmp>
3.18 : ffffffff8146b6e7: movq (%rsp), %rdx
42.96 : ffffffff8146b6eb: testl %eax, %eax
0.00 : ffffffff8146b6ed: jne 0xffffffff8146b7fc
<rhtab_lookup_elem+0x1cc>
0.00 : ffffffff8146b6f3: testq %r15, %r15
0.00 : ffffffff8146b6f6: jne 0xffffffff8146b71c
<rhtab_lookup_elem+0xec>
0.00 : ffffffff8146b6f8: movq 0x30(%r12), %r12
0.00 : ffffffff8146b6fd: testq %r12, %r12
0.00 : ffffffff8146b700: jne 0xffffffff8146b654
<rhtab_lookup_elem+0x24>
0.00 : ffffffff8146b706: addq $0x18, %rsp
0.01 : ffffffff8146b70a: movq %r12, %rax
0.07 : ffffffff8146b70d: popq %rbx
3.71 : ffffffff8146b70e: popq %rbp
0.00 : ffffffff8146b70f: popq %r12
0.02 : ffffffff8146b711: popq %r13
0.09 : ffffffff8146b713: popq %r14
0.03 : ffffffff8146b715: popq %r15
0.09 : ffffffff8146b717: jmp 0xffffffff81ecbb70
<__pi___x86_return_thunk>
0.00 : ffffffff8146b71c: subq 0x10(%rsp), %r15
2.77 : ffffffff8146b721: movq %r15, %r12
0.00 : ffffffff8146b724: jmp 0xffffffff8146b706
<rhtab_lookup_elem+0xd6>
0.00 : ffffffff8146b726: andl $-0x4, %eax
0.00 : ffffffff8146b729: shrl $0x2, %esi
0.00 : ffffffff8146b72c: movq %rbp, %rcx
0.45 : ffffffff8146b72f: leal -0x21524111(%rdx,%rax), %edx
0.01 : ffffffff8146b736: movl %edx, %eax
0.00 : ffffffff8146b738: movl %edx, %edi
0.00 : ffffffff8146b73a: cmpl $0xf, %r8d
0.00 : ffffffff8146b73e: jbe 0xffffffff8146b7a7
<rhtab_lookup_elem+0x177>
0.00 : ffffffff8146b740: addl 0x8(%rcx), %eax
0.00 : ffffffff8146b743: addl (%rcx), %edx
0.00 : ffffffff8146b745: subl $0x3, %esi
0.00 : ffffffff8146b748: addq $0xc, %rcx
0.00 : ffffffff8146b74c: movl %eax, %r8d
0.00 : ffffffff8146b74f: subl %eax, %edx
0.00 : ffffffff8146b751: addl -0x8(%rcx), %edi
0.00 : ffffffff8146b754: roll $0x4, %r8d
0.00 : ffffffff8146b758: addl %edi, %eax
0.00 : ffffffff8146b75a: xorl %edx, %r8d
0.00 : ffffffff8146b75d: movl %r8d, %edx
0.00 : ffffffff8146b760: subl %r8d, %edi
0.00 : ffffffff8146b763: addl %eax, %r8d
0.00 : ffffffff8146b766: roll $0x6, %edx
0.00 : ffffffff8146b769: xorl %edx, %edi
0.00 : ffffffff8146b76b: movl %edi, %edx
0.00 : ffffffff8146b76d: subl %edi, %eax
0.00 : ffffffff8146b76f: addl %r8d, %edi
0.00 : ffffffff8146b772: roll $0x8, %edx
0.00 : ffffffff8146b775: xorl %eax, %edx
0.00 : ffffffff8146b777: movl %edx, %eax
0.00 : ffffffff8146b779: subl %edx, %r8d
0.00 : ffffffff8146b77c: roll $0x10, %eax
0.00 : ffffffff8146b77f: xorl %r8d, %eax
0.00 : ffffffff8146b782: leal (%rdx,%rdi), %r8d
0.00 : ffffffff8146b786: subl %eax, %edi
0.00 : ffffffff8146b788: movl %edi, %edx
0.00 : ffffffff8146b78a: movl %eax, %edi
0.00 : ffffffff8146b78c: rorl $0xd, %edi
0.00 : ffffffff8146b78f: xorl %edx, %edi
0.00 : ffffffff8146b791: leal (%rax,%r8), %edx
0.00 : ffffffff8146b795: movl %edi, %eax
0.00 : ffffffff8146b797: subl %edi, %r8d
0.00 : ffffffff8146b79a: addl %edx, %edi
0.00 : ffffffff8146b79c: roll $0x4, %eax
0.00 : ffffffff8146b79f: xorl %r8d, %eax
0.00 : ffffffff8146b7a2: cmpl $0x3, %esi
0.00 : ffffffff8146b7a5: ja 0xffffffff8146b740
<rhtab_lookup_elem+0x110>
0.00 : ffffffff8146b7a7: cmpl $0x2, %esi
0.01 : ffffffff8146b7aa: je 0xffffffff8146b81c
<rhtab_lookup_elem+0x1ec>
0.01 : ffffffff8146b7ac: cmpl $0x3, %esi
0.01 : ffffffff8146b7af: je 0xffffffff8146b819
<rhtab_lookup_elem+0x1e9>
0.00 : ffffffff8146b7b1: cmpl $0x1, %esi
1.14 : ffffffff8146b7b4: jne 0xffffffff8146b677
<rhtab_lookup_elem+0x47>
0.00 : ffffffff8146b7ba: addl (%rcx), %edx
0.03 : ffffffff8146b7bc: movl %edi, %ecx
0.00 : ffffffff8146b7be: xorl %edi, %eax
0.00 : ffffffff8146b7c0: roll $0xe, %ecx
0.04 : ffffffff8146b7c3: subl %ecx, %eax
0.00 : ffffffff8146b7c5: movl %eax, %ecx
0.00 : ffffffff8146b7c7: xorl %eax, %edx
0.00 : ffffffff8146b7c9: roll $0xb, %ecx
0.85 : ffffffff8146b7cc: subl %ecx, %edx
0.00 : ffffffff8146b7ce: movl %edx, %ecx
0.00 : ffffffff8146b7d0: xorl %edx, %edi
0.03 : ffffffff8146b7d2: rorl $0x7, %ecx
0.06 : ffffffff8146b7d5: subl %ecx, %edi
0.00 : ffffffff8146b7d7: movl %edi, %ecx
0.00 : ffffffff8146b7d9: xorl %edi, %eax
0.13 : ffffffff8146b7db: roll $0x10, %ecx
0.78 : ffffffff8146b7de: subl %ecx, %eax
0.00 : ffffffff8146b7e0: movl %eax, %ecx
0.00 : ffffffff8146b7e2: xorl %eax, %edx
1.22 : ffffffff8146b7e4: roll $0x4, %ecx
0.28 : ffffffff8146b7e7: subl %ecx, %edx
0.00 : ffffffff8146b7e9: xorl %edx, %edi
0.06 : ffffffff8146b7eb: roll $0xe, %edx
1.13 : ffffffff8146b7ee: subl %edx, %edi
0.01 : ffffffff8146b7f0: xorl %edi, %eax
1.37 : ffffffff8146b7f2: rorl $0x8, %edi
4.96 : ffffffff8146b7f5: subl %edi, %eax
0.00 : ffffffff8146b7f7: jmp 0xffffffff8146b677
<rhtab_lookup_elem+0x47>
0.00 : ffffffff8146b7fc: movq (%r15), %r15
3.07 : ffffffff8146b7ff: testb $0x1, %r15b
0.00 : ffffffff8146b803: je 0xffffffff8146b6d7
<rhtab_lookup_elem+0xa7>
0.00 : ffffffff8146b809: cmpq 0x8(%rsp), %r15
0.00 : ffffffff8146b80e: jne 0xffffffff8146b6a0
<rhtab_lookup_elem+0x70>
0.00 : ffffffff8146b814: jmp 0xffffffff8146b6f8
<rhtab_lookup_elem+0xc8>
0.00 : ffffffff8146b819: addl 0x8(%rcx), %eax
0.00 : ffffffff8146b81c: addl 0x4(%rcx), %edi
0.00 : ffffffff8146b81f: jmp 0xffffffff8146b7ba
<rhtab_lookup_elem+0x18a>
0.00 : ffffffff8146b821: movq %r12, %rdi
0.00 : ffffffff8146b824: callq 0xffffffff81840570
<rht_bucket_nested>
0.00 : ffffffff8146b829: movq %rax, %r14
0.00 : ffffffff8146b82c: jmp 0xffffffff8146b694 <rhtab_lookup_elem+0x64>
Quoted 11 lines
Please share 'perf report' or 'perf annotate' for lookup. Maybe worth it to include in commit log.
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2774
Quoted 5 lines
kernel/bpf/hashtab.c +2
-1+} +static void *rhtab_map_lookup_elem (struct bpf_map *map,void *key)__must_hold (RCU ) { -return NULL ;imo there is no point in such a step by step introduction. Patches 1,2,3 can be squashed.
Re: [PATCH RFC bpf-next v2 03/18] bpf: Implement lookup, delete, update for resizable hashtab
Quoted 24 lines · Mykyta Yatsenko
Quoted 4 lines · Alexei Starovoitov
Quoted 2 lines · Mykyta Yatsenko
Quoted 9 lines
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2783
Quoted 7 lines
kernel/bpf/hashtab.c +7
-0+static void *rhtab_lookup_elem (struct bpf_map *map,void *key) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +/* Using constant zeroed params to force rhashtable use inlined hashfunc */ +static const struct rhashtable_params params = {0 }; + +return rhashtable_lookup_likely (&rhtab->ht, key, params);How does the asm look like?
You can see how asm looks like below. An interesting thing is that gcc inlines jhash2, but not clang, which costs a lot of performance.
gcc:
lookup 20.675M ± 0.090M events/sec (approximated from 32 samples of ~48ms)
Quoted 6 lines
clang:
cpu00: lookup 15.882M ± 0.530M events/sec (approximated from 32 samples of ~62ms)I think inlining is also consistent for htab and rhtab (either both inline or both do not inline).
Try other hashes. I recall somebody from isovalent experimented replacing jhash with xxhash and/or siphash in hash map and had nice improvements for certain key sizes.
Daniel Borkmann
maintainerRe: [PATCH RFC bpf-next v2 03/18] bpf: Implement lookup, delete, update for resizable hashtab
Quoted 27 lines · Alexei Starovoitov
Quoted 25 lines · Mykyta Yatsenko
Quoted 4 lines · Alexei Starovoitov
Quoted 2 lines · Mykyta Yatsenko
Quoted 9 lines
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2783
Quoted 7 lines
kernel/bpf/hashtab.c +7
-0+static void *rhtab_lookup_elem (struct bpf_map *map,void *key) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +/* Using constant zeroed params to force rhashtable use inlined hashfunc */ +static const struct rhashtable_params params = {0 }; + +return rhashtable_lookup_likely (&rhtab->ht, key, params);How does the asm look like?
You can see how asm looks like below. An interesting thing is that gcc inlines jhash2, but not clang, which costs a lot of performance.
gcc:
lookup 20.675M ± 0.090M events/sec (approximated from 32 samples of ~48ms)clang:
cpu00: lookup 15.882M ± 0.530M events/sec (approximated from 32 samples of ~62ms)
Quoted 6 lines
Quoted 2 lines
I think inlining is also consistent for htab and rhtab (either both inline or both do not inline).
Try other hashes. I recall somebody from isovalent experimented replacing jhash with xxhash and/or siphash in hash map and had nice improvements for certain key sizes.
[ +Anton ]
page 26+: https://bpfconf.ebpf.io/bpfconf2023/bpfconf2023_material/anton-protopopov-lsf-mm-bpf-2023.pdf
Re: [PATCH RFC bpf-next v2 03/18] bpf: Implement lookup, delete, update for resizable hashtab
Quoted 33 lines · Daniel Borkmann
Quoted 32 lines · Alexei Starovoitov
Quoted 29 lines · Mykyta Yatsenko
Quoted 4 lines · Alexei Starovoitov
Quoted 2 lines · Mykyta Yatsenko
Quoted 11 lines
Quoted 9 lines
kernel/bpf/hashtab.c +3
-0+static void *rhtab_lookup_elem (struct bpf_map *map,void *key) +{ + struct bpf_rhtab *rhtab = container_of(map, struct
bpf_rhtab, map);
+ /* Using constant zeroed params to force rhashtable use inlined hashfunc */
+ static const structrhashtable_paramsparams = { 0 }; +
+ returnrhashtable_lookup_likely(&rhtab->ht, key, params);How does the asm look like?
You can see how asm looks like below. An interesting thing is that gcc inlines jhash2, but not clang, which costs a lot of performance.
gcc:
lookup 20.675M ± 0.090M events/sec (approximated from 32 samples of ~48ms)clang:
cpu00: lookup 15.882M ± 0.530M events/sec (approximated from 32 samples of ~62ms)I think inlining is also consistent for htab and rhtab (either both inline or both do not inline).
Quoted 7 lines
Quoted 3 lines
Try other hashes. I recall somebody from isovalent experimented replacing jhash with xxhash and/or siphash in hash map and had nice improvements for certain key sizes.
[ +Anton ]
page 26+: https://bpfconf.ebpf.io/bpfconf2023/bpfconf2023_material/ anton-protopopov-lsf-mm-bpf-2023.pdf
Thanks for sharing that presentation, looking at the graphs on page 27, jhash2 is actually a better choice for the key size below 10 bytes (correct me if I'm wrong). And for rhashtable it's going to make even bigger difference, because jhash2 is inlined, because it's used by default by rhashtable, while other hash fns we'll have to provide via function pointer -> no inlining, which is a huge difference (see above). Looking at the profiling data, hash fn (when inlined) does not look like a bottleneck memcmp is, though.
Anyways, I'll run benchmarks with other hash functions.
Emil Tsalapatis
reviewerRe: [PATCH RFC bpf-next v2 03/18] bpf: Implement lookup, delete, update for resizable hashtab
In reply to Mykyta YatsenkoQuoted 118 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Use
rhashtable_lookup_likely()for lookups,rhashtable_remove_fast()for deletes, andrhashtable_lookup_get_insert_fast()for inserts.Updates modify values in place under RCU rather than allocating a new element and swapping the pointer (as regular htab does). This trades read consistency for performance: concurrent readers may see partial updates. Users requiring consistent reads should use
BPF_F_LOCK.Signed-off-by Mykyta Yatsenko <[email protected]>--- kernel/bpf/hashtab.c | 141 ++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 134 insertions(+), 7 deletions(-)kernel/bpf/hashtab.c +71
-4@@ -2755,6 +2755,11 @@ struct bpf_rhtab {u32 elem_size; }; +static inline void *rhtab_elem_value (struct rhtab_elem *l,u32 key_size) +{ +return l->data +round_up (key_size,8 ); +} +static struct bpf_map *rhtab_map_alloc (union bpf_attr *attr) {return ERR_PTR (-EOPNOTSUPP );@@ -2769,33 +2774,155 @@ static void rhtab_map_free(struct bpf_map *map) { } +static void *rhtab_lookup_elem (struct bpf_map *map,void *key) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +/* Using constant zeroed params to force rhashtable use inlined hashfunc */ +static const struct rhashtable_params params = {0 }; + +return rhashtable_lookup_likely (&rhtab->ht, key, params); +} +static void *rhtab_map_lookup_elem (struct bpf_map *map,void *key)__must_hold (RCU ) { -return NULL ; +struct rhtab_elem *l; + + l =rhtab_lookup_elem (map, key); +return l ?rhtab_elem_value (l, map->key_size) :NULL ; +} + +static int rhtab_delete_elem (struct bpf_rhtab *rhtab,struct rhtab_elem *elem) +{ +int err; + + err =rhashtable_remove_fast (&rhtab->ht, &elem->node, rhtab->params); +if (err) +return err; + +bpf_map_free_internal_structs (&rhtab->map,rhtab_elem_value (elem, rhtab->map.key_size)); +bpf_mem_cache_free_rcu (&rhtab->ma, elem); +return 0 ; }static long rhtab_map_delete_elem (struct bpf_map *map,void *key) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *l; + +guard (rcu)(); + l =rhtab_lookup_elem (map, key); +return l ?rhtab_delete_elem (rhtab, l) : -ENOENT ; +} + +static void rhtab_read_elem_value (struct bpf_map *map,void *dst,struct rhtab_elem *elem, +u64 flags) +{ +void *src =rhtab_elem_value (elem, map->key_size); + +if (flags &BPF_F_LOCK ) +copy_map_value_locked (map, dst, src, true); +else +copy_map_value (map, dst, src); }static int rhtab_map_lookup_and_delete_elem (struct bpf_map *map,void *key,void *value,u64 flags) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *l; +int err; + +if ((flags & ~BPF_F_LOCK ) || + ((flags &BPF_F_LOCK ) && !btf_record_has_field (map->record,BPF_SPIN_LOCK ))) +return -EINVAL ; + +/* Make sure element is not deleted between lookup and copy */ +guard (rcu)(); + + l =rhtab_lookup_elem (map, key); +if (!l) +return -ENOENT ; + +rhtab_read_elem_value (map, value, l, flags); + err =rhtab_delete_elem (rhtab, l); +if (err) +return err; + +check_and_init_map_value (map, value); +return 0 ; } -static long rhtab_map_update_elem (struct bpf_map *map,void *key,void *value,u64 map_flags) +static long rhtab_map_update_existing(struct bpf_map *map, struct rhtab_elem *elem, void *value,
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2863
Quoted 10 lines
kernel/bpf/hashtab.c +8
-1+ u64 map_flags) { -return -EOPNOTSUPP ; +if (map_flags &BPF_NOEXIST ) +return -EEXIST ; + +if (map_flags &BPF_F_LOCK ) +copy_map_value_locked (map,rhtab_elem_value (elem, map->key_size), value, false); +else +copy_map_value (map,rhtab_elem_value (elem, map->key_size), value);
It looks like Sashiko is accurate about special fields not getting handled here.
Quoted 35 lines
kernel/bpf/hashtab.c +31
-1+return 0 ; } -static void rhtab_map_free_internal_structs (struct bpf_map *map) +static long rhtab_map_update_elem (struct bpf_map *map,void *key,void *value,u64 map_flags) { + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *elem, *tmp; + +if (unlikely ((map_flags & ~BPF_F_LOCK ) >BPF_EXIST )) +return -EINVAL ; + +if ((map_flags &BPF_F_LOCK ) && !btf_record_has_field (map->record,BPF_SPIN_LOCK )) +return -EINVAL ; + +guard (rcu)(); + elem =rhtab_lookup_elem (map, key); +if (elem) +return rhtab_map_update_existing (map, elem, value, map_flags); + +if (map_flags &BPF_EXIST ) +return -ENOENT ; + +/* Check max_entries limit before inserting new element */ +if (atomic_read (&rhtab->ht.nelems) >= map->max_entries) +return -E2BIG ; + + elem =bpf_mem_cache_alloc (&rhtab->ma); +if (!elem) +return -ENOMEM ; + +memcpy (elem->data, key, map->key_size); +copy_map_value (map,rhtab_elem_value (elem, map->key_size), value); + + tmp =rhashtable_lookup_get_insert_fast (&rhtab->ht, &elem->node, rhtab->params);
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2907
Quoted 10 lines
kernel/bpf/hashtab.c +9
-0+if (tmp) { +bpf_mem_cache_free (&rhtab->ma, elem); +if (IS_ERR (tmp)) +return PTR_ERR (tmp); + +return rhtab_map_update_existing (map, tmp, value, map_flags); + } + +return 0 ; }
Note: I am actually skeptical about Sashiko's warning here. Sure, the update may get overwritten even as we are returning 0, but we are providing no guarantees about how long the write will survive in the map, and there is no inherent atomicity between an update and any other operations.
Quoted 10 lines
kernel/bpf/hashtab.c +6
-1static int rhtab_map_gen_lookup (struct bpf_map *map,struct bpf_insn *insn_buf) { -return -EOPNOTSUPP ; +struct bpf_insn *insn = insn_buf; +const int ret =BPF_REG_0 ; + +BUILD_BUG_ON (!__same_type (&rhtab_lookup_elem, + (void *(*)(struct bpf_map *map,void *key))NULL )); + *insn++ =BPF_EMIT_CALL (rhtab_lookup_elem);
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2926
Quoted 10 lines
kernel/bpf/hashtab.c +9
-0+ *insn++ =BPF_JMP_IMM (BPF_JEQ , ret,0 ,1 ); + *insn++ =BPF_ALU64_IMM (BPF_ADD , ret, + offsetof(struct rhtab_elem , data) +round_up (map->key_size,8 )); + +return insn - insn_buf; +} + +static void rhtab_map_free_internal_structs (struct bpf_map *map) +{ }
This gets filled in in later patches, but the fact it's here and a no-op debatably the line into being non-bisectable. Can we move it to the walk patch, since that's where it gets populated?
Quoted 2 lines
kernel/bpf/hashtab.c +0
-0static int rhtab_map_get_next_key (struct bpf_map *map,void *key,void *next_key)
Re: [PATCH RFC bpf-next v2 03/18] bpf: Implement lookup, delete, update for resizable hashtab
Quoted 117 lines · Emil Tsalapatis
Quoted 116 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Use
rhashtable_lookup_likely()for lookups,rhashtable_remove_fast()for deletes, andrhashtable_lookup_get_insert_fast()for inserts.Updates modify values in place under RCU rather than allocating a new element and swapping the pointer (as regular htab does). This trades read consistency for performance: concurrent readers may see partial updates. Users requiring consistent reads should use
BPF_F_LOCK.Signed-off-by Mykyta Yatsenko <[email protected]>--- kernel/bpf/hashtab.c | 141 ++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 134 insertions(+), 7 deletions(-)kernel/bpf/hashtab.c +70
-3@@ -2755,6 +2755,11 @@ struct bpf_rhtab {u32 elem_size; }; +static inline void *rhtab_elem_value (struct rhtab_elem *l,u32 key_size) +{ +return l->data +round_up (key_size,8 ); +} +static struct bpf_map *rhtab_map_alloc (union bpf_attr *attr) {return ERR_PTR (-EOPNOTSUPP );@@ -2769,33 +2774,155 @@ static void rhtab_map_free(struct bpf_map *map) { } +static void *rhtab_lookup_elem (struct bpf_map *map,void *key) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +/* Using constant zeroed params to force rhashtable use inlined hashfunc */ +static const struct rhashtable_params params = {0 }; + +return rhashtable_lookup_likely (&rhtab->ht, key, params); +} +static void *rhtab_map_lookup_elem (struct bpf_map *map,void *key)__must_hold (RCU ) { -return NULL ; +struct rhtab_elem *l; + + l =rhtab_lookup_elem (map, key); +return l ?rhtab_elem_value (l, map->key_size) :NULL ; +} + +static int rhtab_delete_elem (struct bpf_rhtab *rhtab,struct rhtab_elem *elem) +{ +int err; + + err =rhashtable_remove_fast (&rhtab->ht, &elem->node, rhtab->params); +if (err) +return err; + +bpf_map_free_internal_structs (&rhtab->map,rhtab_elem_value (elem, rhtab->map.key_size)); +bpf_mem_cache_free_rcu (&rhtab->ma, elem); +return 0 ; }static long rhtab_map_delete_elem (struct bpf_map *map,void *key) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *l; + +guard (rcu)(); + l =rhtab_lookup_elem (map, key); +return l ?rhtab_delete_elem (rhtab, l) : -ENOENT ; +} + +static void rhtab_read_elem_value (struct bpf_map *map,void *dst,struct rhtab_elem *elem, +u64 flags) +{ +void *src =rhtab_elem_value (elem, map->key_size); + +if (flags &BPF_F_LOCK ) +copy_map_value_locked (map, dst, src, true); +else +copy_map_value (map, dst, src); }static int rhtab_map_lookup_and_delete_elem (struct bpf_map *map,void *key,void *value,u64 flags) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *l; +int err; + +if ((flags & ~BPF_F_LOCK ) || + ((flags &BPF_F_LOCK ) && !btf_record_has_field (map->record,BPF_SPIN_LOCK ))) +return -EINVAL ; + +/* Make sure element is not deleted between lookup and copy */ +guard (rcu)(); + + l =rhtab_lookup_elem (map, key); +if (!l) +return -ENOENT ; + +rhtab_read_elem_value (map, value, l, flags); + err =rhtab_delete_elem (rhtab, l); +if (err) +return err; + +check_and_init_map_value (map, value); +return 0 ; }
Quoted 15 lines
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2863
Quoted 12 lines
kernel/bpf/hashtab.c +9
-2-static long rhtab_map_update_elem (struct bpf_map *map,void *key,void *value,u64 map_flags) +static long rhtab_map_update_existing (struct bpf_map *map,struct rhtab_elem *elem,void *value, +u64 map_flags) { -return -EOPNOTSUPP ; +if (map_flags &BPF_NOEXIST ) +return -EEXIST ; + +if (map_flags &BPF_F_LOCK ) +copy_map_value_locked (map,rhtab_elem_value (elem, map->key_size), value, false); +else +copy_map_value (map,rhtab_elem_value (elem, map->key_size), value);It looks like Sashiko is accurate about special fields not getting handled here.
Special fields are not copied, this is similar to other maps.
Quoted 43 lines
Quoted 43 lines
kernel/bpf/hashtab.c +39
-1+return 0 ; } -static void rhtab_map_free_internal_structs (struct bpf_map *map) +static long rhtab_map_update_elem (struct bpf_map *map,void *key,void *value,u64 map_flags) { + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *elem, *tmp; + +if (unlikely ((map_flags & ~BPF_F_LOCK ) >BPF_EXIST )) +return -EINVAL ; + +if ((map_flags &BPF_F_LOCK ) && !btf_record_has_field (map->record,BPF_SPIN_LOCK )) +return -EINVAL ; + +guard (rcu)(); + elem =rhtab_lookup_elem (map, key); +if (elem) +return rhtab_map_update_existing (map, elem, value, map_flags); + +if (map_flags &BPF_EXIST ) +return -ENOENT ; + +/* Check max_entries limit before inserting new element */ +if (atomic_read (&rhtab->ht.nelems) >= map->max_entries) +return -E2BIG ; + + elem =bpf_mem_cache_alloc (&rhtab->ma); +if (!elem) +return -ENOMEM ; + +memcpy (elem->data, key, map->key_size); +copy_map_value (map,rhtab_elem_value (elem, map->key_size), value); + + tmp =rhashtable_lookup_get_insert_fast (&rhtab->ht, &elem->node, rhtab->params); +if (tmp) { +bpf_mem_cache_free (&rhtab->ma, elem); +if (IS_ERR (tmp)) +return PTR_ERR (tmp); + +return rhtab_map_update_existing (map, tmp, value, map_flags); + } +
Quoted 9 lines
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2907
Quoted 2 lines
kernel/bpf/hashtab.c +1
-0+return 0 ; }Note: I am actually skeptical about Sashiko's warning here. Sure, the update may get overwritten even as we are returning 0, but we are providing no guarantees about how long the write will survive in the map, and there is no inherent atomicity between an update and any other operations.
Right, either way can't guarantee that user going to see it's write anyway, if concurrent writers exist.
Quoted 16 lines
Quoted 16 lines
kernel/bpf/hashtab.c +12
-1static int rhtab_map_gen_lookup (struct bpf_map *map,struct bpf_insn *insn_buf) { -return -EOPNOTSUPP ; +struct bpf_insn *insn = insn_buf; +const int ret =BPF_REG_0 ; + +BUILD_BUG_ON (!__same_type (&rhtab_lookup_elem, + (void *(*)(struct bpf_map *map,void *key))NULL )); + *insn++ =BPF_EMIT_CALL (rhtab_lookup_elem); + *insn++ =BPF_JMP_IMM (BPF_JEQ , ret,0 ,1 ); + *insn++ =BPF_ALU64_IMM (BPF_ADD , ret, + offsetof(struct rhtab_elem , data) +round_up (map->key_size,8 )); + +return insn - insn_buf; +}
Quoted 9 lines
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2926
Quoted 4 lines
kernel/bpf/hashtab.c +3
-0+ +static void rhtab_map_free_internal_structs (struct bpf_map *map) +{ }This gets filled in in later patches, but the fact it's here and a no-op debatably the line into being non-bisectable. Can we move it to the walk patch, since that's where it gets populated?
I think this is bisectable, because with this patch you can't create resizable hashmap anyway (allocation support comes as the last patch of the series). Alexei suggested to to merge these patches, so I'll do that.
Quoted 3 lines
Quoted 2 lines
kernel/bpf/hashtab.c +0
-0static int rhtab_map_get_next_key (struct bpf_map *map,void *key,void *next_key)
Re: [PATCH RFC bpf-next v2 03/18] bpf: Implement lookup, delete, update for resizable hashtab
In reply to Mykyta YatsenkoOn Wed, Apr 08, 2026 at 08:10:08AM -0700, Mykyta Yatsenko wrote:
[...]
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2836
Quoted 11 lines
static int
rhtab_map_lookup_and_delete_elem(struct bpf_map *map, void *key, void *value, u64 flags){kernel/bpf/hashtab.c +7
-1-return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *l; +int err; + +if ((flags & ~BPF_F_LOCK ) || + ((flags &BPF_F_LOCK ) && !btf_record_has_field (map->record,BPF_SPIN_LOCK ))) +return -EINVAL ;
At the moment, we can check the flags using bpf_map_check_op_flags() helper.
This helper can be applied to flags check in this series.
Quoted 16 lines
kernel/bpf/hashtab.c +15
-0+ +/* Make sure element is not deleted between lookup and copy */ +guard (rcu)(); + + l =rhtab_lookup_elem (map, key); +if (!l) +return -ENOENT ; + +rhtab_read_elem_value (map, value, l, flags); + err =rhtab_delete_elem (rhtab, l); +if (err) +return err; + +check_and_init_map_value (map, value); +return 0 ;}
[...]
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2876
Quoted 12 lines
kernel/bpf/hashtab.c +1
-1-static void rhtab_map_free_internal_structs (struct bpf_map *map) +static long rhtab_map_update_elem (struct bpf_map *map,void *key,void *value,u64 map_flags){
kernel/bpf/hashtab.c +8
-0+ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *elem, *tmp; + +if (unlikely ((map_flags & ~BPF_F_LOCK ) >BPF_EXIST )) +return -EINVAL ; + +if ((map_flags &BPF_F_LOCK ) && !btf_record_has_field (map->record,BPF_SPIN_LOCK )) +return -EINVAL ;
ditto
Thanks,
Leon
Quoted 1 line
+ [...]
Re: [PATCH RFC bpf-next v2 03/18] bpf: Implement lookup, delete, update for resizable hashtab
Quoted 16 lines · Leon Hwang
On Wed, Apr 08, 2026 at 08:10:08AM -0700, Mykyta Yatsenko wrote:
[...]kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2836
Quoted 11 lines
static int
rhtab_map_lookup_and_delete_elem(struct bpf_map *map, void *key, void *value, u64 flags){kernel/bpf/hashtab.c +7
-1-return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *l; +int err; + +if ((flags & ~BPF_F_LOCK ) || + ((flags &BPF_F_LOCK ) && !btf_record_has_field (map->record,BPF_SPIN_LOCK ))) +return -EINVAL ;At the moment, we can check the flags using
bpf_map_check_op_flags()helper.
Quoted 2 lines
This helper can be applied to flags check in this series.
Thanks, I'll use it.
Quoted 36 lines
Quoted 16 lines
kernel/bpf/hashtab.c +15
-0+ +/* Make sure element is not deleted between lookup and copy */ +guard (rcu)(); + + l =rhtab_lookup_elem (map, key); +if (!l) +return -ENOENT ; + +rhtab_read_elem_value (map, value, l, flags); + err =rhtab_delete_elem (rhtab, l); +if (err) +return err; + +check_and_init_map_value (map, value); +return 0 ;}
[...]
kernel/bpf/hashtab.c static void rhtab_map_free(struct bpf_map *map) · line 2876
Quoted 12 lines
kernel/bpf/hashtab.c +1
-1-static void rhtab_map_free_internal_structs (struct bpf_map *map) +static long rhtab_map_update_elem (struct bpf_map *map,void *key,void *value,u64 map_flags){
kernel/bpf/hashtab.c +8
-0+ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhtab_elem *elem, *tmp; + +if (unlikely ((map_flags & ~BPF_F_LOCK ) >BPF_EXIST )) +return -EINVAL ; + +if ((map_flags &BPF_F_LOCK ) && !btf_record_has_field (map->record,BPF_SPIN_LOCK )) +return -EINVAL ;ditto
Thanks,
LeonQuoted 1 line
+ [...]
RFC PATCH v2 4/18 rhashtable: Add rhashtable_walk_enter_from()
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
BPF resizable hashmap needs efficient iteration resume for get_next_key and seq_file iterators. rhashtable_walk_enter() always starts from bucket 0, forcing linear skip of already-seen elements.
Add rhashtable_walk_enter_from() that looks up the key's bucket and positions the walker there, so walk_next returns the successor directly. If a resize moved the key to the future table, the walker is migrated to that table.
Refactor __rhashtable_lookup into __rhashtable_lookup_one to reuse the single-table lookup in both the two-table search and the new enter_from positioning.
--- include/linux/rhashtable.h | 31 ++++++++++-- lib/rhashtable.c | 53 ++++++++++++++++++++ lib/test_rhashtable.c | 120 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 199 insertions(+), 5 deletions(-)
include/linux/rhashtable.h +26 -5
@@ -253,6 +253,11 @@ static inline void rhashtable_walk_start(struct rhashtable_iter *iter) (void )rhashtable_walk_start_check (iter); } +void rhashtable_walk_enter_from (struct rhashtable *ht, +struct rhashtable_iter *iter, +const void *key, +const struct rhashtable_params params); +void *rhashtable_walk_next (struct rhashtable_iter *iter);void *rhashtable_walk_peek (struct rhashtable_iter *iter); void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases_shared(RCU);
@@ -613,8 +618,8 @@ static inline int rhashtable_compare(struct rhashtable_compare_arg *arg, }/* Internal function, do not use. */ -static __always_inline struct rhash_head *__rhashtable_lookup( -struct rhashtable *ht,const void *key, +static __always_inline struct rhash_head *__rhashtable_lookup_one( +struct rhashtable *ht,struct bucket_table *tbl,const void *key,const struct rhashtable_params params,const enum rht_lookup_freq freq)__must_hold_shared (RCU )
@@ -624,13 +629,10 @@ static __always_inline struct rhash_head *__rhashtable_lookup( .key = key, };struct rhash_lock_head __rcu *const *bkt; -struct bucket_table *tbl;struct rhash_head *he;unsigned int hash;BUILD_BUG_ON (!__builtin_constant_p (freq)); - tbl =rht_dereference_rcu (ht->tbl, ht); -restart: hash =rht_key_hashfn (ht, tbl, key, params); bkt =rht_bucket (tbl, hash); do {
@@ -646,6 +648,25 @@ static __always_inline struct rhash_head *__rhashtable_lookup(*/ }while (he !=RHT_NULLS_MARKER (bkt)); +return NULL ; +} + +/* Internal function, do not use. */ +static __always_inline struct rhash_head *__rhashtable_lookup( +struct rhashtable *ht,const void *key, +const struct rhashtable_params params, +const enum rht_lookup_freq freq) +__must_hold_shared (RCU ) +{ +struct bucket_table *tbl; +struct rhash_head *he; + + tbl =rht_dereference_rcu (ht->tbl, ht); +restart: + he =__rhashtable_lookup_one (ht, tbl, key, params, freq); +if (he) +return he; +/* Ensure we see any new tables. */ smp_rmb ();
lib/rhashtable.c +53 -0
59 lines not on this page · raw message
lib/test_rhashtable.c +120 -0
138 lines not on this page · raw message
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 04/18] rhashtable: Add rhashtable_walk_enter_from()
Quoted 15 lines · Mykyta Yatsenko
lib/test_rhashtable.c +14
-0+ +/* Test 2: walk_enter_from with non-existent key starts from bucket */ + { +struct test_obj_val key = { .id =99 }; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&ht, &iter, &key, + test_rht_params); +rhashtable_walk_start (&iter); + } + + obj =rhashtable_walk_next (&iter); +while (IS_ERR (obj) &&PTR_ERR (obj) == -EAGAIN ) + obj =rhashtable_walk_next (&iter);
lib/test_rhashtable.c static int threadfunc(void *data) · line 761
Quoted 10 lines
lib/test_rhashtable.c +10
-0+ +/* Should still return some element (iteration from bucket start) */ +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + } + +/* Test 3: verify walk_enter_from + walk_next can iterate remaining elements */ + { +struct test_obj_val key = { .id =0 }; +int count =0 ;
Please de-claude this.
I couldn't force claude to avoid using these pointless indents. Either figure out how to do it or remove it manually.
Re: [PATCH RFC bpf-next v2 04/18] rhashtable: Add rhashtable_walk_enter_from()
Quoted 23 lines · Alexei Starovoitov
Quoted 21 lines · Mykyta Yatsenko
lib/test_rhashtable.c +20
-0+ +/* Test 2: walk_enter_from with non-existent key starts from bucket */ + { +struct test_obj_val key = { .id =99 }; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&ht, &iter, &key, + test_rht_params); +rhashtable_walk_start (&iter); + } + + obj =rhashtable_walk_next (&iter); +while (IS_ERR (obj) &&PTR_ERR (obj) == -EAGAIN ) + obj =rhashtable_walk_next (&iter); + +/* Should still return some element (iteration from bucket start) */ +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + } +
Quoted 8 lines
lib/test_rhashtable.c static int threadfunc(void *data) · line 761
Quoted 4 lines
lib/test_rhashtable.c +4
-0+/* Test 3: verify walk_enter_from + walk_next can iterate remaining elements */ + { +struct test_obj_val key = { .id =0 }; +int count =0 ;Please de-claude this.
I couldn't force claude to avoid using these pointless indents. Either figure out how to do it or remove it manually.
Thanks for the reviews, I'll apply your suggestions here and other patches for the v3.
Re: [PATCH RFC bpf-next v2 04/18] rhashtable: Add rhashtable_walk_enter_from()
In reply to Mykyta YatsenkoQuoted 12 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
BPF resizable hashmap needs efficient iteration resume for
get_next_keyandseq_fileiterators.rhashtable_walk_enter()always starts from bucket 0, forcing linear skip of already-seen elements.Add
rhashtable_walk_enter_from()that looks up the key's bucket and positions the walker there, sowalk_nextreturns the successor directly. If a resize moved the key to the future table, the walker is migrated to that table.
Quoted 5 lines
Refactor
__rhashtable_lookupinto__rhashtable_lookup_oneto reuse the single-table lookup in both the two-table search and the newenter_frompositioning.Signed-off-by Mykyta Yatsenko <[email protected]>
Provided tests are updated:
Quoted 282 lines
--- include/linux/rhashtable.h | 31 ++++++++++-- lib/rhashtable.c | 53 ++++++++++++++++++++ lib/test_rhashtable.c | 120 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 199 insertions(+), 5 deletions(-)include/linux/rhashtable.h +26
-5@@ -253,6 +253,11 @@ static inline void rhashtable_walk_start(struct rhashtable_iter *iter) (void )rhashtable_walk_start_check (iter); } +void rhashtable_walk_enter_from (struct rhashtable *ht, +struct rhashtable_iter *iter, +const void *key, +const struct rhashtable_params params); +void *rhashtable_walk_next (struct rhashtable_iter *iter);void *rhashtable_walk_peek (struct rhashtable_iter *iter); void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases_shared(RCU);@@ -613,8 +618,8 @@ static inline int rhashtable_compare(struct rhashtable_compare_arg *arg, }/* Internal function, do not use. */ -static __always_inline struct rhash_head *__rhashtable_lookup( -struct rhashtable *ht,const void *key, +static __always_inline struct rhash_head *__rhashtable_lookup_one( +struct rhashtable *ht,struct bucket_table *tbl,const void *key,const struct rhashtable_params params,const enum rht_lookup_freq freq)__must_hold_shared (RCU )@@ -624,13 +629,10 @@ static __always_inline struct rhash_head *__rhashtable_lookup( .key = key, };struct rhash_lock_head __rcu *const *bkt; -struct bucket_table *tbl;struct rhash_head *he;unsigned int hash;BUILD_BUG_ON (!__builtin_constant_p (freq)); - tbl =rht_dereference_rcu (ht->tbl, ht); -restart: hash =rht_key_hashfn (ht, tbl, key, params); bkt =rht_bucket (tbl, hash); do {@@ -646,6 +648,25 @@ static __always_inline struct rhash_head *__rhashtable_lookup(*/ }while (he !=RHT_NULLS_MARKER (bkt)); +return NULL ; +} + +/* Internal function, do not use. */ +static __always_inline struct rhash_head *__rhashtable_lookup( +struct rhashtable *ht,const void *key, +const struct rhashtable_params params, +const enum rht_lookup_freq freq) +__must_hold_shared (RCU ) +{ +struct bucket_table *tbl; +struct rhash_head *he; + + tbl =rht_dereference_rcu (ht->tbl, ht); +restart: + he =__rhashtable_lookup_one (ht, tbl, key, params, freq); +if (he) +return he; +/* Ensure we see any new tables. */ smp_rmb ();lib/rhashtable.c +53
-0@@ -692,6 +692,59 @@ void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter) }EXPORT_SYMBOL_GPL (rhashtable_walk_enter); +/** +* rhashtable_walk_enter_from - Initialise a walk starting at a key's bucket +* @ht: Table to walk over +* @iter: Hash table iterator +* @key: Key whose bucket to start from +* @params: Hash table parameters +* +* Like rhashtable_walk_enter(), but positions the iterator at the bucket +* containing @key. If a resize is in progress and @key has been migrated +* to the future table, the walker is moved to that table. +* +* Same constraints as rhashtable_walk_enter() apply. +*/ +void rhashtable_walk_enter_from (struct rhashtable *ht, +struct rhashtable_iter *iter, +const void *key, +const struct rhashtable_params params) +__must_hold (RCU ) +{ +struct bucket_table *tbl; +struct rhash_head *he; + +rhashtable_walk_enter (ht, iter); + +if (!key) +return ; + + tbl =rht_dereference_rcu (ht->tbl, ht); + he =__rhashtable_lookup_one (ht, tbl, key, params, +RHT_LOOKUP_NORMAL ); +if (!he) { +smp_rmb (); + tbl =rht_dereference_rcu (tbl->future_tbl, ht); +if (!tbl) +return ; + + he =__rhashtable_lookup_one (ht, tbl, key, params, +RHT_LOOKUP_NORMAL ); +if (!he) +return ; + +spin_lock (&ht->lock); +list_del (&iter->walker.list); + iter->walker.tbl = tbl; +list_add (&iter->walker.list, &tbl->walkers); +spin_unlock (&ht->lock); + } + + iter->slot =rht_key_hashfn (ht, tbl, key, params); + iter->p = he; +} +EXPORT_SYMBOL_GPL (rhashtable_walk_enter_from); +/** * rhashtable_walk_exit - Free an iterator * @iter: Hash table Iterator lib/test_rhashtable.c +120
-0@@ -23,6 +23,7 @@#include <linux/random.h> #include <linux/vmalloc.h> #include <linux/wait.h> +#include <linux/cleanup.h> #define MAX_ENTRIES 1000000#define TEST_INSERT_FAIL INT_MAX@@ -679,6 +680,122 @@ static int threadfunc(void *data)return err; } +static int __init test_walk_enter_from (void ) +{ +struct rhashtable ht; +struct test_obj objs[4 ]; +struct rhashtable_iter iter; +struct test_obj *obj; +int err, i; + + err =rhashtable_init (&ht, &test_rht_params); +if (err) +return err; + +/* Insert 4 elements with keys 0, 2, 4, 6 */ +for (i =0 ; i <4 ; i++) { + objs[i].value.id = i *2 ; + objs[i].value.tid =0 ; + err =rhashtable_insert_fast (&ht, &objs[i].node, + test_rht_params); +if (err) { +pr_warn ("walk_enter_from: insert %d failed: %d\n" , + i, err); + goto out; + } + } + +/* +* Test 1: walk_enter_from positions at key, walk_next returns +* the successor (not the key itself). +*/ +for (i =0 ; i <4 ; i++) { +struct test_obj_val key = { .id = i *2 }; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&ht, &iter, &key, + test_rht_params); +rhashtable_walk_start (&iter); + } + + obj =rhashtable_walk_next (&iter); +while (IS_ERR (obj) &&PTR_ERR (obj) == -EAGAIN ) + obj =rhashtable_walk_next (&iter); + +/* Successor must not be the key itself */ +if (obj && obj->value.id == i *2 ) { +pr_warn ("walk_enter_from: returned key %d instead of successor\n" , + i *2 ); + err = -EINVAL ; +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + goto out; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + } + +/* Test 2: walk_enter_from with non-existent key starts from bucket */ + { +struct test_obj_val key = { .id =99 }; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&ht, &iter, &key, + test_rht_params); +rhashtable_walk_start (&iter); + } + + obj =rhashtable_walk_next (&iter); +while (IS_ERR (obj) &&PTR_ERR (obj) == -EAGAIN ) + obj =rhashtable_walk_next (&iter); + +/* Should still return some element (iteration from bucket start) */ +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + } + +/* Test 3: verify walk_enter_from + walk_next can iterate remaining elements */ + { +struct test_obj_val key = { .id =0 }; +int count =0 ; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&ht, &iter, &key, + test_rht_params); +rhashtable_walk_start (&iter); + } + +while ((obj =rhashtable_walk_next (&iter))) { +if (IS_ERR (obj)) { +if (PTR_ERR (obj) == -EAGAIN ) +continue ; +break ; + } + count++; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +/* +* Should see at least some elements after key 0. +* Exact count depends on hash distribution. +*/ +if (count ==0 ) { +pr_warn ("walk_enter_from: no elements found after key 0\n" ); + err = -EINVAL ; + goto out; + } + } + +pr_info ("walk_enter_from: all tests passed\n" ); + err =0 ; +out: +rhashtable_destroy (&ht); +return err; +} +static int __init test_rht_init (void ) {unsigned int entries;@@ -738,6 +855,9 @@ static int __init test_rht_init(void)test_insert_duplicates_run (); +pr_info ("Testing walk_enter_from: %s\n" , +test_walk_enter_from () ==0 ?"pass" :"FAIL" ); +if (!tcount)return 0 ;
RFC PATCH v2 5/18 bpf: Implement get_next_key and free_internal_structs for resizable hashtab
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Implement rhtab_map_get_next_key() and rhtab_map_free_internal_structs() of the BPF resizable hashtable. Both are only called from syscall, so it's safe to use rhashtable walk API that uses spinlocks internally.
--- kernel/bpf/hashtab.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 77 insertions(+), 1 deletion(-)
kernel/bpf/hashtab.c +77 -1
@@ -2921,13 +2921,89 @@ static int rhtab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)return insn - insn_buf; } +/* Helper to get next element, handling -EAGAIN during resize */ +static struct rhtab_elem *rhtab_iter_next (struct rhashtable_iter *iter) +{ +struct rhtab_elem *elem; + +while ((elem =rhashtable_walk_next (iter))) { +if (IS_ERR (elem)) { +if (PTR_ERR (elem) == -EAGAIN ) +continue ; +return NULL ; + } +return elem; + } + +return NULL ; +} +static void rhtab_map_free_internal_structs (struct bpf_map *map) { + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhashtable_iter iter; +struct rhtab_elem *elem; + +if (!bpf_map_has_internal_structs (map)) +return ; + +/* +* An element can be processed twice if rhashtable resized concurrently. +* Special structs freeing handles duplicate cancel_and_free. +*/ +rhashtable_walk_enter (&rhtab->ht, &iter); +rhashtable_walk_start (&iter); + +for (elem =rhtab_iter_next (&iter); elem; elem =rhtab_iter_next (&iter)) +bpf_map_free_internal_structs (map,rhtab_elem_value (elem, map->key_size)); + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); }static int rhtab_map_get_next_key (struct bpf_map *map,void *key,void *next_key) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhashtable_iter iter; +struct rhtab_elem *elem; +bool key_found; +int ret = -ENOENT ; + +/* +* Hold RCU across enter_from + walk_start to prevent the +* element cached by enter_from from being freed before +* walk_start re-acquires RCU. +*/ +guard (rcu)(); +rhashtable_walk_enter_from (&rhtab->ht, &iter, key, rhtab->params); + key_found = key && iter.p; +rhashtable_walk_start (&iter); + + elem =rhtab_iter_next (&iter); +if (elem) { +memcpy (next_key, elem->data, map->key_size); + ret =0 ; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +if (ret ==0 || key_found) +return ret; + +/* Key was not found restart from the beginning */ +rhashtable_walk_enter (&rhtab->ht, &iter); +rhashtable_walk_start (&iter); + + elem =rhtab_iter_next (&iter); +if (elem) { +memcpy (next_key, elem->data, map->key_size); + ret =0 ; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); +return ret; }static void rhtab_map_seq_show_elem (struct bpf_map *map,void *key,struct seq_file *m)
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 05/18] bpf: Implement get_next_key and free_internal_structs for resizable hashtab
Quoted 92 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Implement
rhtab_map_get_next_key()andrhtab_map_free_internal_structs()of the BPF resizable hashtable. Both are only called from syscall, so it's safe to use rhashtable walk API that uses spinlocks internally.Signed-off-by Mykyta Yatsenko <[email protected]>--- kernel/bpf/hashtab.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 77 insertions(+), 1 deletion(-)kernel/bpf/hashtab.c +66
-1@@ -2921,13 +2921,89 @@ static int rhtab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)return insn - insn_buf; } +/* Helper to get next element, handling -EAGAIN during resize */ +static struct rhtab_elem *rhtab_iter_next (struct rhashtable_iter *iter) +{ +struct rhtab_elem *elem; + +while ((elem =rhashtable_walk_next (iter))) { +if (IS_ERR (elem)) { +if (PTR_ERR (elem) == -EAGAIN ) +continue ; +return NULL ; + } +return elem; + } + +return NULL ; +} +static void rhtab_map_free_internal_structs (struct bpf_map *map) { + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhashtable_iter iter; +struct rhtab_elem *elem; + +if (!bpf_map_has_internal_structs (map)) +return ; + +/* +* An element can be processed twice if rhashtable resized concurrently. +* Special structs freeing handles duplicate cancel_and_free. +*/ +rhashtable_walk_enter (&rhtab->ht, &iter); +rhashtable_walk_start (&iter); + +for (elem =rhtab_iter_next (&iter); elem; elem =rhtab_iter_next (&iter)) +bpf_map_free_internal_structs (map,rhtab_elem_value (elem, map->key_size)); + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); }static int rhtab_map_get_next_key (struct bpf_map *map,void *key,void *next_key) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhashtable_iter iter; +struct rhtab_elem *elem; +bool key_found; +int ret = -ENOENT ; + +/* +* Hold RCU across enter_from + walk_start to prevent the +* element cached by enter_from from being freed before +* walk_start re-acquires RCU. +*/ +guard (rcu)(); +rhashtable_walk_enter_from (&rhtab->ht, &iter, key, rhtab->params); + key_found = key && iter.p; +rhashtable_walk_start (&iter); + + elem =rhtab_iter_next (&iter); +if (elem) { +memcpy (next_key, elem->data, map->key_size); + ret =0 ; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +if (ret ==0 || key_found) +return ret; + +/* Key was not found restart from the beginning */ +rhashtable_walk_enter (&rhtab->ht, &iter);
kernel/bpf/hashtab.c static int rhtab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) · line 3005
Quoted 10 lines
kernel/bpf/hashtab.c +10
-0+rhashtable_walk_start (&iter); + + elem =rhtab_iter_next (&iter); +if (elem) { +memcpy (next_key, elem->data, map->key_size); + ret =0 ; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter);
Nit: The two attempts are partly identical, can you try to roll them together and use a goto to retry? Or do you think this will be too messy?
Otherwise:
Quoted 4 lines
kernel/bpf/hashtab.c +1
-0+return ret; }static void rhtab_map_seq_show_elem (struct bpf_map *map,void *key,struct seq_file *m)
Re: [PATCH RFC bpf-next v2 05/18] bpf: Implement get_next_key and free_internal_structs for resizable hashtab
Quoted 98 lines · Emil Tsalapatis
Quoted 97 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Implement
rhtab_map_get_next_key()andrhtab_map_free_internal_structs()of the BPF resizable hashtable. Both are only called from syscall, so it's safe to use rhashtable walk API that uses spinlocks internally.Signed-off-by Mykyta Yatsenko <[email protected]>--- kernel/bpf/hashtab.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 77 insertions(+), 1 deletion(-)kernel/bpf/hashtab.c +71
-1@@ -2921,13 +2921,89 @@ static int rhtab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)return insn - insn_buf; } +/* Helper to get next element, handling -EAGAIN during resize */ +static struct rhtab_elem *rhtab_iter_next (struct rhashtable_iter *iter) +{ +struct rhtab_elem *elem; + +while ((elem =rhashtable_walk_next (iter))) { +if (IS_ERR (elem)) { +if (PTR_ERR (elem) == -EAGAIN ) +continue ; +return NULL ; + } +return elem; + } + +return NULL ; +} +static void rhtab_map_free_internal_structs (struct bpf_map *map) { + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhashtable_iter iter; +struct rhtab_elem *elem; + +if (!bpf_map_has_internal_structs (map)) +return ; + +/* +* An element can be processed twice if rhashtable resized concurrently. +* Special structs freeing handles duplicate cancel_and_free. +*/ +rhashtable_walk_enter (&rhtab->ht, &iter); +rhashtable_walk_start (&iter); + +for (elem =rhtab_iter_next (&iter); elem; elem =rhtab_iter_next (&iter)) +bpf_map_free_internal_structs (map,rhtab_elem_value (elem, map->key_size)); + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); }static int rhtab_map_get_next_key (struct bpf_map *map,void *key,void *next_key) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhashtable_iter iter; +struct rhtab_elem *elem; +bool key_found; +int ret = -ENOENT ; + +/* +* Hold RCU across enter_from + walk_start to prevent the +* element cached by enter_from from being freed before +* walk_start re-acquires RCU. +*/ +guard (rcu)(); +rhashtable_walk_enter_from (&rhtab->ht, &iter, key, rhtab->params); + key_found = key && iter.p; +rhashtable_walk_start (&iter); + + elem =rhtab_iter_next (&iter); +if (elem) { +memcpy (next_key, elem->data, map->key_size); + ret =0 ; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +if (ret ==0 || key_found) +return ret; + +/* Key was not found restart from the beginning */ +rhashtable_walk_enter (&rhtab->ht, &iter); +rhashtable_walk_start (&iter); + + elem =rhtab_iter_next (&iter); +if (elem) { +memcpy (next_key, elem->data, map->key_size);
Quoted 9 lines
kernel/bpf/hashtab.c static int rhtab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) · line 2989
Quoted 5 lines
kernel/bpf/hashtab.c +5
-0+ ret =0 ; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter);Nit: The two attempts are partly identical, can you try to roll them together and use a goto to retry? Or do you think this will be too messy?
It felt nicer just to write this code sequentially without any gotos or loops. No strong opinion here.
Quoted 9 lines
Otherwise:
Reviewed-by Emil Tsalapatis <[email protected]>Quoted 4 lines
kernel/bpf/hashtab.c +1
-0+return ret; }static void rhtab_map_seq_show_elem (struct bpf_map *map,void *key,struct seq_file *m)
RFC PATCH v2 6/18 bpf: Implement bpf_each_rhash_elem() using walk API
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
rhashtable walk API takes spin_lock(&ht->lock) in start/stop, making it unsafe in NMI and hard IRQ contexts. Guard with !in_task() rather than open-coding raw RCU iteration that would need to handle resize races manually.
--- kernel/bpf/hashtab.c | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-)
kernel/bpf/hashtab.c +34 -1
@@ -3013,7 +3013,40 @@ static void rhtab_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_fstatic long bpf_each_rhash_elem (struct bpf_map *map,bpf_callback_t callback_fn,void *callback_ctx,u64 flags) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhashtable_iter iter; +struct rhtab_elem *elem; +int num_elems =0 ; +u64 ret =0 ; + +if (flags !=0 ) +return -EINVAL ; + +/* +* The rhashtable walk API uses spin_lock(&ht->lock) in rhashtable_walk_start/stop, +* which is not safe in NMI or soft/hard IRQ context. +*/ +if (!in_task ()) +return -EOPNOTSUPP ; + +rhashtable_walk_enter (&rhtab->ht, &iter); +rhashtable_walk_start (&iter); + +for (elem =rhtab_iter_next (&iter); elem; + elem =rhtab_iter_next (&iter)) { + num_elems++; + ret =callback_fn ((u64 )(long )map, + (u64 )(long )elem->data, + (u64 )(long )rhtab_elem_value (elem, map->key_size), + (u64 )(long )callback_ctx,0 ); +if (ret) +break ; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +return num_elems; }static u64 rhtab_map_mem_usage (const struct bpf_map *map)
Signature · 1 line
2.52.0
Emil Tsalapatis
reviewerRe: [PATCH RFC bpf-next v2 06/18] bpf: Implement bpf_each_rhash_elem() using walk API
Quoted 26 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
rhashtable walk API takes
spin_lock(&ht->lock)in start/stop, making it unsafe in NMI and hard IRQ contexts. Guard with !in_task() rather than open-coding raw RCU iteration that would need to handle resize races manually.Signed-off-by Mykyta Yatsenko <[email protected]>--- kernel/bpf/hashtab.c | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-)kernel/bpf/hashtab.c +5
-1@@ -3013,7 +3013,40 @@ static void rhtab_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_fstatic long bpf_each_rhash_elem (struct bpf_map *map,bpf_callback_t callback_fn,void *callback_ctx,u64 flags) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhashtable_iter iter; +struct rhtab_elem *elem; +int num_elems =0 ; +u64 ret =0 ;
kernel/bpf/hashtab.c static void rhtab_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_f · line 3030
Quoted 10 lines
kernel/bpf/hashtab.c +10
-0+ +if (flags !=0 ) +return -EINVAL ; + +/* +* The rhashtable walk API uses spin_lock(&ht->lock) in rhashtable_walk_start/stop, +* which is not safe in NMI or soft/hard IRQ context. +*/ +if (!in_task ()) +return -EOPNOTSUPP ;
Use in_nmi()/in_hardirq()/in_softirq() instead?
kernel/bpf/hashtab.c static void rhtab_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_f · line 3041
Quoted 11 lines
kernel/bpf/hashtab.c +11
-0+ +rhashtable_walk_enter (&rhtab->ht, &iter); +rhashtable_walk_start (&iter); + +for (elem =rhtab_iter_next (&iter); elem; + elem =rhtab_iter_next (&iter)) { + num_elems++; + ret =callback_fn ((u64 )(long )map, + (u64 )(long )elem->data, + (u64 )(long )rhtab_elem_value (elem, map->key_size), + (u64 )(long )callback_ctx,0 );
AFAICT this callback is impossible to be sleepable which is why we're able to call it under RCU, can we note this here in a comment?
Quoted 11 lines
kernel/bpf/hashtab.c +8
-0+if (ret) +break ; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +return num_elems; }static u64 rhtab_map_mem_usage (const struct bpf_map *map)
Re: [PATCH RFC bpf-next v2 06/18] bpf: Implement bpf_each_rhash_elem() using walk API
Quoted 40 lines · Emil Tsalapatis
Quoted 26 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
rhashtable walk API takes
spin_lock(&ht->lock)in start/stop, making it unsafe in NMI and hard IRQ contexts. Guard with !in_task() rather than open-coding raw RCU iteration that would need to handle resize races manually.Signed-off-by Mykyta Yatsenko <[email protected]>--- kernel/bpf/hashtab.c | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-)kernel/bpf/hashtab.c +5
-1@@ -3013,7 +3013,40 @@ static void rhtab_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_fstatic long bpf_each_rhash_elem (struct bpf_map *map,bpf_callback_t callback_fn,void *callback_ctx,u64 flags) { -return -EOPNOTSUPP ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +struct rhashtable_iter iter; +struct rhtab_elem *elem; +int num_elems =0 ; +u64 ret =0 ;kernel/bpf/hashtab.c static void rhtab_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_f · line 3030
Quoted 10 lines
kernel/bpf/hashtab.c +10
-0+ +if (flags !=0 ) +return -EINVAL ; + +/* +* The rhashtable walk API uses spin_lock(&ht->lock) in rhashtable_walk_start/stop, +* which is not safe in NMI or soft/hard IRQ context. +*/ +if (!in_task ()) +return -EOPNOTSUPP ;Use in_nmi()/in_hardirq()/in_softirq() instead?
Quoted 15 lines
kernel/bpf/hashtab.c static void rhtab_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_f · line 3041
Quoted 11 lines
kernel/bpf/hashtab.c +11
-0+ +rhashtable_walk_enter (&rhtab->ht, &iter); +rhashtable_walk_start (&iter); + +for (elem =rhtab_iter_next (&iter); elem; + elem =rhtab_iter_next (&iter)) { + num_elems++; + ret =callback_fn ((u64 )(long )map, + (u64 )(long )elem->data, + (u64 )(long )rhtab_elem_value (elem, map->key_size), + (u64 )(long )callback_ctx,0 );AFAICT this callback is impossible to be sleepable which is why we're able to call it under RCU, can we note this here in a comment?
Thanks for raising this concern, it looks like the callback can be sleepable, but the same issue can be seen in existing htab.
Quoted 12 lines
Quoted 11 lines
kernel/bpf/hashtab.c +8
-0+if (ret) +break ; + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +return num_elems; }static u64 rhtab_map_mem_usage (const struct bpf_map *map)
RFC PATCH v2 7/18 bpf: Implement batch ops for resizable hashtab
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Add batch operations for BPF_MAP_TYPE_RHASH.
Batch operations:
* rhtab_map_lookup_batch: Bulk lookup of elements by bucket
* rhtab_map_lookup_and_delete_batch: Atomic bulk lookup and delete
The batch implementation uses rhashtable_walk_enter_from() to resume iteration from the last collected key. When the buffer fills, the last key becomes the cursor for the next batch call.
Also implements rhtab_map_mem_usage() to report memory consumption.
--- kernel/bpf/hashtab.c | 137 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 134 insertions(+), 3 deletions(-)
kernel/bpf/hashtab.c +134 -3
@@ -3051,19 +3051,150 @@ static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,static u64 rhtab_map_mem_usage (const struct bpf_map *map) { -return 0 ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +u64 num_entries; + + num_entries =atomic_read (&rhtab->ht.nelems); +return sizeof (struct bpf_rhtab ) + rhtab->elem_size * num_entries; +} + +static int __rhtab_map_lookup_and_delete_batch (struct bpf_map *map, +const union bpf_attr *attr, +union bpf_attr __user *uattr, +bool do_delete) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +void __user *uvalues =u64_to_user_ptr (attr->batch.values); +void __user *ukeys =u64_to_user_ptr (attr->batch.keys); +void __user *ubatch =u64_to_user_ptr (attr->batch.in_batch); +void *buf =NULL , *keys =NULL , *values =NULL , *dst_key, *dst_val; +struct rhtab_elem **del_elems =NULL ; +u32 max_count, total, key_size, value_size, i; +struct rhashtable_iter iter; +struct rhtab_elem *elem; +u64 elem_map_flags, map_flags; +int ret =0 ; + + elem_map_flags = attr->batch.elem_flags; +if ((elem_map_flags & ~BPF_F_LOCK ) || + ((elem_map_flags &BPF_F_LOCK ) && + !btf_record_has_field (map->record,BPF_SPIN_LOCK ))) +return -EINVAL ; + + map_flags = attr->batch.flags; +if (map_flags) +return -EINVAL ; + + max_count = attr->batch.count; +if (!max_count) +return 0 ; + +if (put_user (0 , &uattr->batch.count)) +return -EFAULT ; + + key_size = map->key_size; + value_size = map->value_size; + + keys =kvmalloc_array (max_count, key_size,GFP_USER | __GFP_NOWARN); + values =kvmalloc_array (max_count, value_size,GFP_USER | __GFP_NOWARN); +if (do_delete) + del_elems =kvmalloc_array (max_count,sizeof (void *), +GFP_USER | __GFP_NOWARN); + +if (!keys || !values || (do_delete && !del_elems)) { + ret = -ENOMEM ; + goto free; + } + +/* +* Use the last key from the previous batch as cursor. +* enter_from positions at that key's bucket, walk_next +* returns the successor in O(1). +* First call (ubatch == NULL): starts from bucket 0. +*/ +if (ubatch) { + buf =kmalloc (key_size,GFP_USER | __GFP_NOWARN); +if (!buf) { + ret = -ENOMEM ; + goto free; + } +if (copy_from_user (buf, ubatch, key_size)) { + ret = -EFAULT ; + goto free; + } + } + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&rhtab->ht, &iter, buf, rhtab->params); +rhashtable_walk_start (&iter); + } + + dst_key = keys; + dst_val = values; + total =0 ; + +while (total < max_count) { + elem =rhtab_iter_next (&iter); +if (!elem) +break ; + +memcpy (dst_key, elem->data, key_size); +rhtab_read_elem_value (map, dst_val, elem, elem_map_flags); +check_and_init_map_value (map, dst_val); + +if (do_delete) + del_elems[total] = elem; + + dst_key += key_size; + dst_val += value_size; + total++; + } + +if (do_delete) { +for (i =0 ; i < total; i++) +rhtab_delete_elem (rhtab, del_elems[i]); + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +if (total ==0 ) { + ret = -ENOENT ; + goto free; + } + +/* Signal end of table when we collected fewer than requested */ +if (total < max_count) + ret = -ENOENT ; + +/* Write last key as cursor for the next batch call */ +if (copy_to_user (ukeys, keys, total * key_size) || +copy_to_user (uvalues, values, total * value_size) || +put_user (total, &uattr->batch.count) || +copy_to_user (u64_to_user_ptr (attr->batch.out_batch), + dst_key - key_size, key_size)) { + ret = -EFAULT ; + goto free; + } + +free: +kfree (buf); +kvfree (keys); +kvfree (values); +kvfree (del_elems); +return ret; }static int rhtab_map_lookup_batch (struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr) { -return 0 ; +return __rhtab_map_lookup_and_delete_batch (map, attr, uattr, false); }static int rhtab_map_lookup_and_delete_batch (struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr) { -return 0 ; +return __rhtab_map_lookup_and_delete_batch (map, attr, uattr, true); }struct bpf_iter_seq_rhash_map_info {
Signature · 1 line
2.52.0
Emil Tsalapatis
reviewerRe: [PATCH RFC bpf-next v2 07/18] bpf: Implement batch ops for resizable hashtab
Quoted 92 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Add batch operations for
BPF_MAP_TYPE_RHASH.Batch operations:
*rhtab_map_lookup_batch: Bulk lookup of elements by bucket
*rhtab_map_lookup_and_delete_batch: Atomic bulk lookup and deleteThe batch implementation uses
rhashtable_walk_enter_from()to resume iteration from the last collected key. When the buffer fills, the last key becomes the cursor for the next batch call.Also implements
rhtab_map_mem_usage()to report memory consumption.Signed-off-by Mykyta Yatsenko <[email protected]>--- kernel/bpf/hashtab.c | 137 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 134 insertions(+), 3 deletions(-)kernel/bpf/hashtab.c +64
-1@@ -3051,19 +3051,150 @@ static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,static u64 rhtab_map_mem_usage (const struct bpf_map *map) { -return 0 ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +u64 num_entries; + + num_entries =atomic_read (&rhtab->ht.nelems); +return sizeof (struct bpf_rhtab ) + rhtab->elem_size * num_entries; +} + +static int __rhtab_map_lookup_and_delete_batch (struct bpf_map *map, +const union bpf_attr *attr, +union bpf_attr __user *uattr, +bool do_delete) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +void __user *uvalues =u64_to_user_ptr (attr->batch.values); +void __user *ukeys =u64_to_user_ptr (attr->batch.keys); +void __user *ubatch =u64_to_user_ptr (attr->batch.in_batch); +void *buf =NULL , *keys =NULL , *values =NULL , *dst_key, *dst_val; +struct rhtab_elem **del_elems =NULL ; +u32 max_count, total, key_size, value_size, i; +struct rhashtable_iter iter; +struct rhtab_elem *elem; +u64 elem_map_flags, map_flags; +int ret =0 ; + + elem_map_flags = attr->batch.elem_flags; +if ((elem_map_flags & ~BPF_F_LOCK ) || + ((elem_map_flags &BPF_F_LOCK ) && + !btf_record_has_field (map->record,BPF_SPIN_LOCK ))) +return -EINVAL ; + + map_flags = attr->batch.flags; +if (map_flags) +return -EINVAL ; + + max_count = attr->batch.count; +if (!max_count) +return 0 ; + +if (put_user (0 , &uattr->batch.count)) +return -EFAULT ; + + key_size = map->key_size; + value_size = map->value_size; + + keys =kvmalloc_array (max_count, key_size,GFP_USER | __GFP_NOWARN); + values =kvmalloc_array (max_count, value_size,GFP_USER | __GFP_NOWARN); +if (do_delete) + del_elems =kvmalloc_array (max_count,sizeof (void *), +GFP_USER | __GFP_NOWARN); + +if (!keys || !values || (do_delete && !del_elems)) { + ret = -ENOMEM ; + goto free; + } + +/* +* Use the last key from the previous batch as cursor. +* enter_from positions at that key's bucket, walk_next +* returns the successor in O(1). +* First call (ubatch == NULL): starts from bucket 0. +*/ +if (ubatch) { + buf =kmalloc (key_size,GFP_USER | __GFP_NOWARN); +if (!buf) {
kernel/bpf/hashtab.c static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn, · line 3127
Quoted 10 lines
kernel/bpf/hashtab.c +10
-0+ ret = -ENOMEM ; + goto free; + } +if (copy_from_user (buf, ubatch, key_size)) { + ret = -EFAULT ; + goto free; + } + } + +scoped_guard (rcu) {
AFAICT this guard makes sure the RCU critical section extends from the beginning of rhashtable_walk_enter_from all the way to walk_stop(), is that correct?
Quoted 61 lines
kernel/bpf/hashtab.c +58
-0+rhashtable_walk_enter_from (&rhtab->ht, &iter, buf, rhtab->params); +rhashtable_walk_start (&iter); + } + + dst_key = keys; + dst_val = values; + total =0 ; + +while (total < max_count) { + elem =rhtab_iter_next (&iter); +if (!elem) +break ; + +memcpy (dst_key, elem->data, key_size); +rhtab_read_elem_value (map, dst_val, elem, elem_map_flags); +check_and_init_map_value (map, dst_val); + +if (do_delete) + del_elems[total] = elem; + + dst_key += key_size; + dst_val += value_size; + total++; + } + +if (do_delete) { +for (i =0 ; i < total; i++) +rhtab_delete_elem (rhtab, del_elems[i]); + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +if (total ==0 ) { + ret = -ENOENT ; + goto free; + } + +/* Signal end of table when we collected fewer than requested */ +if (total < max_count) + ret = -ENOENT ; + +/* Write last key as cursor for the next batch call */ +if (copy_to_user (ukeys, keys, total * key_size) || +copy_to_user (uvalues, values, total * value_size) || +put_user (total, &uattr->batch.count) || +copy_to_user (u64_to_user_ptr (attr->batch.out_batch), + dst_key - key_size, key_size)) { + ret = -EFAULT ; + goto free; + } + +free: +kfree (buf); +kvfree (keys); +kvfree (values); +kvfree (del_elems); +return ret; } static int rhtab_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr,
kernel/bpf/hashtab.c static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn, · line 3066
Quoted 10 lines
kernel/bpf/hashtab.c +1
-2union bpf_attr __user *uattr) { -return 0 ; +return __rhtab_map_lookup_and_delete_batch (map, attr, uattr, false); }static int rhtab_map_lookup_and_delete_batch (struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr) { -return 0 ;
Shouldn't these have been -EINVAL or -ENOSUPP in previous patches?
Quoted 4 lines
kernel/bpf/hashtab.c +1
-0+return __rhtab_map_lookup_and_delete_batch (map, attr, uattr, true); }struct bpf_iter_seq_rhash_map_info {
Re: [PATCH RFC bpf-next v2 07/18] bpf: Implement batch ops for resizable hashtab
Quoted 99 lines · Emil Tsalapatis
Quoted 98 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Add batch operations for
BPF_MAP_TYPE_RHASH.Batch operations:
*rhtab_map_lookup_batch: Bulk lookup of elements by bucket
*rhtab_map_lookup_and_delete_batch: Atomic bulk lookup and deleteThe batch implementation uses
rhashtable_walk_enter_from()to resume iteration from the last collected key. When the buffer fills, the last key becomes the cursor for the next batch call.Also implements
rhtab_map_mem_usage()to report memory consumption.Signed-off-by Mykyta Yatsenko <[email protected]>--- kernel/bpf/hashtab.c | 137 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 134 insertions(+), 3 deletions(-)kernel/bpf/hashtab.c +70
-1@@ -3051,19 +3051,150 @@ static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,static u64 rhtab_map_mem_usage (const struct bpf_map *map) { -return 0 ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +u64 num_entries; + + num_entries =atomic_read (&rhtab->ht.nelems); +return sizeof (struct bpf_rhtab ) + rhtab->elem_size * num_entries; +} + +static int __rhtab_map_lookup_and_delete_batch (struct bpf_map *map, +const union bpf_attr *attr, +union bpf_attr __user *uattr, +bool do_delete) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +void __user *uvalues =u64_to_user_ptr (attr->batch.values); +void __user *ukeys =u64_to_user_ptr (attr->batch.keys); +void __user *ubatch =u64_to_user_ptr (attr->batch.in_batch); +void *buf =NULL , *keys =NULL , *values =NULL , *dst_key, *dst_val; +struct rhtab_elem **del_elems =NULL ; +u32 max_count, total, key_size, value_size, i; +struct rhashtable_iter iter; +struct rhtab_elem *elem; +u64 elem_map_flags, map_flags; +int ret =0 ; + + elem_map_flags = attr->batch.elem_flags; +if ((elem_map_flags & ~BPF_F_LOCK ) || + ((elem_map_flags &BPF_F_LOCK ) && + !btf_record_has_field (map->record,BPF_SPIN_LOCK ))) +return -EINVAL ; + + map_flags = attr->batch.flags; +if (map_flags) +return -EINVAL ; + + max_count = attr->batch.count; +if (!max_count) +return 0 ; + +if (put_user (0 , &uattr->batch.count)) +return -EFAULT ; + + key_size = map->key_size; + value_size = map->value_size; + + keys =kvmalloc_array (max_count, key_size,GFP_USER | __GFP_NOWARN); + values =kvmalloc_array (max_count, value_size,GFP_USER | __GFP_NOWARN); +if (do_delete) + del_elems =kvmalloc_array (max_count,sizeof (void *), +GFP_USER | __GFP_NOWARN); + +if (!keys || !values || (do_delete && !del_elems)) { + ret = -ENOMEM ; + goto free; + } + +/* +* Use the last key from the previous batch as cursor. +* enter_from positions at that key's bucket, walk_next +* returns the successor in O(1). +* First call (ubatch == NULL): starts from bucket 0. +*/ +if (ubatch) { + buf =kmalloc (key_size,GFP_USER | __GFP_NOWARN); +if (!buf) { + ret = -ENOMEM ; + goto free; + } +if (copy_from_user (buf, ubatch, key_size)) { + ret = -EFAULT ; + goto free;
Quoted 9 lines
kernel/bpf/hashtab.c static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn, · line 3127
Quoted 4 lines
kernel/bpf/hashtab.c +4
-0+ } + } + +scoped_guard (rcu) {AFAICT this guard makes sure the RCU critical section extends from the beginning of
rhashtable_walk_enter_fromall the way towalk_stop(), is that correct?
This guard is to make sure that when rhashtable_walk_enter_from() initializes iterator, the element which it initialised with is not freed. rhashtable_walk_start() calls rcu lock as well, that's why I can end guard right after rhashtable_walk_start().
Quoted 78 lines
Quoted 61 lines
kernel/bpf/hashtab.c +58
-0+rhashtable_walk_enter_from (&rhtab->ht, &iter, buf, rhtab->params); +rhashtable_walk_start (&iter); + } + + dst_key = keys; + dst_val = values; + total =0 ; + +while (total < max_count) { + elem =rhtab_iter_next (&iter); +if (!elem) +break ; + +memcpy (dst_key, elem->data, key_size); +rhtab_read_elem_value (map, dst_val, elem, elem_map_flags); +check_and_init_map_value (map, dst_val); + +if (do_delete) + del_elems[total] = elem; + + dst_key += key_size; + dst_val += value_size; + total++; + } + +if (do_delete) { +for (i =0 ; i < total; i++) +rhtab_delete_elem (rhtab, del_elems[i]); + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +if (total ==0 ) { + ret = -ENOENT ; + goto free; + } + +/* Signal end of table when we collected fewer than requested */ +if (total < max_count) + ret = -ENOENT ; + +/* Write last key as cursor for the next batch call */ +if (copy_to_user (ukeys, keys, total * key_size) || +copy_to_user (uvalues, values, total * value_size) || +put_user (total, &uattr->batch.count) || +copy_to_user (u64_to_user_ptr (attr->batch.out_batch), + dst_key - key_size, key_size)) { + ret = -EFAULT ; + goto free; + } + +free: +kfree (buf); +kvfree (keys); +kvfree (values); +kvfree (del_elems); +return ret; } static int rhtab_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr,kernel/bpf/hashtab.c static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn, · line 3066
Quoted 10 lines
kernel/bpf/hashtab.c +1
-2union bpf_attr __user *uattr) { -return 0 ; +return __rhtab_map_lookup_and_delete_batch (map, attr, uattr, false); }static int rhtab_map_lookup_and_delete_batch (struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr) { -return 0 ;Shouldn't these have been
-EINVALor-ENOSUPPin previous patches?Quoted 4 lines
kernel/bpf/hashtab.c +1
-0+return __rhtab_map_lookup_and_delete_batch (map, attr, uattr, true); }struct bpf_iter_seq_rhash_map_info {
Re: [PATCH RFC bpf-next v2 07/18] bpf: Implement batch ops for resizable hashtab
Quoted 112 lines · Mykyta Yatsenko
Quoted 99 lines · Emil Tsalapatis
Quoted 98 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Add batch operations for
BPF_MAP_TYPE_RHASH.Batch operations:
*rhtab_map_lookup_batch: Bulk lookup of elements by bucket
*rhtab_map_lookup_and_delete_batch: Atomic bulk lookup and deleteThe batch implementation uses
rhashtable_walk_enter_from()to resume iteration from the last collected key. When the buffer fills, the last key becomes the cursor for the next batch call.Also implements
rhtab_map_mem_usage()to report memory consumption.Signed-off-by Mykyta Yatsenko <[email protected]>--- kernel/bpf/hashtab.c | 137 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 134 insertions(+), 3 deletions(-)kernel/bpf/hashtab.c +70
-1@@ -3051,19 +3051,150 @@ static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,static u64 rhtab_map_mem_usage (const struct bpf_map *map) { -return 0 ; + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +u64 num_entries; + + num_entries =atomic_read (&rhtab->ht.nelems); +return sizeof (struct bpf_rhtab ) + rhtab->elem_size * num_entries; +} + +static int __rhtab_map_lookup_and_delete_batch (struct bpf_map *map, +const union bpf_attr *attr, +union bpf_attr __user *uattr, +bool do_delete) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); +void __user *uvalues =u64_to_user_ptr (attr->batch.values); +void __user *ukeys =u64_to_user_ptr (attr->batch.keys); +void __user *ubatch =u64_to_user_ptr (attr->batch.in_batch); +void *buf =NULL , *keys =NULL , *values =NULL , *dst_key, *dst_val; +struct rhtab_elem **del_elems =NULL ; +u32 max_count, total, key_size, value_size, i; +struct rhashtable_iter iter; +struct rhtab_elem *elem; +u64 elem_map_flags, map_flags; +int ret =0 ; + + elem_map_flags = attr->batch.elem_flags; +if ((elem_map_flags & ~BPF_F_LOCK ) || + ((elem_map_flags &BPF_F_LOCK ) && + !btf_record_has_field (map->record,BPF_SPIN_LOCK ))) +return -EINVAL ; + + map_flags = attr->batch.flags; +if (map_flags) +return -EINVAL ; + + max_count = attr->batch.count; +if (!max_count) +return 0 ; + +if (put_user (0 , &uattr->batch.count)) +return -EFAULT ; + + key_size = map->key_size; + value_size = map->value_size; + + keys =kvmalloc_array (max_count, key_size,GFP_USER | __GFP_NOWARN); + values =kvmalloc_array (max_count, value_size,GFP_USER | __GFP_NOWARN); +if (do_delete) + del_elems =kvmalloc_array (max_count,sizeof (void *), +GFP_USER | __GFP_NOWARN); + +if (!keys || !values || (do_delete && !del_elems)) { + ret = -ENOMEM ; + goto free; + } + +/* +* Use the last key from the previous batch as cursor. +* enter_from positions at that key's bucket, walk_next +* returns the successor in O(1). +* First call (ubatch == NULL): starts from bucket 0. +*/ +if (ubatch) { + buf =kmalloc (key_size,GFP_USER | __GFP_NOWARN); +if (!buf) { + ret = -ENOMEM ; + goto free; + } +if (copy_from_user (buf, ubatch, key_size)) { + ret = -EFAULT ; + goto free;Quoted 9 lines
kernel/bpf/hashtab.c static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn, · line 3127
Quoted 4 lines
kernel/bpf/hashtab.c +4
-0+ } + } + +scoped_guard (rcu) {AFAICT this guard makes sure the RCU critical section extends from the beginning of
rhashtable_walk_enter_fromall the way towalk_stop(), is that correct?
Quoted 5 lines
This guard is to make sure that when
rhashtable_walk_enter_from()initializes iterator, the element which it initialised with is not freed.rhashtable_walk_start()calls rcu lock as well, that's why I can end guard right afterrhashtable_walk_start().
Sounds good, thanks.
Quoted 78 lines
Quoted 78 lines
Quoted 61 lines
kernel/bpf/hashtab.c +58
-0+rhashtable_walk_enter_from (&rhtab->ht, &iter, buf, rhtab->params); +rhashtable_walk_start (&iter); + } + + dst_key = keys; + dst_val = values; + total =0 ; + +while (total < max_count) { + elem =rhtab_iter_next (&iter); +if (!elem) +break ; + +memcpy (dst_key, elem->data, key_size); +rhtab_read_elem_value (map, dst_val, elem, elem_map_flags); +check_and_init_map_value (map, dst_val); + +if (do_delete) + del_elems[total] = elem; + + dst_key += key_size; + dst_val += value_size; + total++; + } + +if (do_delete) { +for (i =0 ; i < total; i++) +rhtab_delete_elem (rhtab, del_elems[i]); + } + +rhashtable_walk_stop (&iter); +rhashtable_walk_exit (&iter); + +if (total ==0 ) { + ret = -ENOENT ; + goto free; + } + +/* Signal end of table when we collected fewer than requested */ +if (total < max_count) + ret = -ENOENT ; + +/* Write last key as cursor for the next batch call */ +if (copy_to_user (ukeys, keys, total * key_size) || +copy_to_user (uvalues, values, total * value_size) || +put_user (total, &uattr->batch.count) || +copy_to_user (u64_to_user_ptr (attr->batch.out_batch), + dst_key - key_size, key_size)) { + ret = -EFAULT ; + goto free; + } + +free: +kfree (buf); +kvfree (keys); +kvfree (values); +kvfree (del_elems); +return ret; } static int rhtab_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr,kernel/bpf/hashtab.c static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn, · line 3066
Quoted 10 lines
kernel/bpf/hashtab.c +1
-2union bpf_attr __user *uattr) { -return 0 ; +return __rhtab_map_lookup_and_delete_batch (map, attr, uattr, false); }static int rhtab_map_lookup_and_delete_batch (struct bpf_map *map,const union bpf_attr *attr,union bpf_attr __user *uattr) { -return 0 ;Shouldn't these have been
-EINVALor-ENOSUPPin previous patches?Quoted 4 lines
kernel/bpf/hashtab.c +1
-0+return __rhtab_map_lookup_and_delete_batch (map, attr, uattr, true); }struct bpf_iter_seq_rhash_map_info {
RFC PATCH v2 8/18 bpf: Implement iterator APIs for resizable hashtab
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Wire up seq_file BPF iterator for BPF_MAP_TYPE_RHASH so that bpf_iter and bpftool map dump work with resizable hash maps.
Use rhashtable_walk_enter_from() with a saved last_key to resume iteration across read() calls without linear skip from the beginning on each seq_start.
Also implement rhtab_map_seq_show_elem() for bpftool map dump in non-iterator mode.
--- kernel/bpf/hashtab.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 94 insertions(+), 4 deletions(-)
kernel/bpf/hashtab.c +94 -4
@@ -3008,6 +3008,19 @@ static int rhtab_map_get_next_key(struct bpf_map *map, void *key, void *next_keystatic void rhtab_map_seq_show_elem (struct bpf_map *map,void *key,struct seq_file *m) { +void *value; + +/* Guarantee that hashtab value is not freed */ +guard (rcu)(); + + value =rhtab_map_lookup_elem (map, key); +if (!value) +return ; + +btf_type_seq_show (map->btf, map->btf_key_type_id, key, m); +seq_puts (m,": " ); +btf_type_seq_show (map->btf, map->btf_value_type_id, value, m); +seq_putc (m,'\n' ); } static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,
@@ -3201,36 +3214,113 @@ struct bpf_iter_seq_rhash_map_info {struct bpf_map *map;struct bpf_rhtab *rhtab;struct rhashtable_iter iter; -u32 skip_elems; +void *last_key;bool iter_active; };static void *bpf_rhash_map_seq_start (struct seq_file *seq,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem; +void *key = *pos >0 ? info->last_key :NULL ; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&info->rhtab->ht, &info->iter, + key, info->rhtab->params); +rhashtable_walk_start (&info->iter); + } + info->iter_active = true; + + elem =rhtab_iter_next (&info->iter); +if (!elem) +return NULL ; +/* +* if *pos is not 0, previously iteration failed on this elem, +* so we are restarting it. That's why no need to increment *pos. +*/ +if (*pos ==0 ) + ++*pos; +return elem; }static void *bpf_rhash_map_seq_next (struct seq_file *seq,void *v,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem = v; + +/* Save current key for O(1) resume in next seq_start */ +memcpy (info->last_key, elem->data, info->map->key_size); + + ++*pos; + +return rhtab_iter_next (&info->iter); +} + +static int __bpf_rhash_map_seq_show (struct seq_file *seq, +struct rhtab_elem *elem) +{ +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct bpf_iter__bpf_map_elem ctx = {}; +struct bpf_iter_meta meta; +struct bpf_prog *prog; +int ret =0 ; + + meta.seq = seq; + prog =bpf_iter_get_info (&meta, elem ==NULL ); +if (prog) { + ctx.meta = &meta; + ctx.map = info->map; +if (elem) { + ctx.key = elem->data; + ctx.value =rhtab_elem_value (elem, info->map->key_size); + } + ret =bpf_iter_run_prog (prog, &ctx); + } + +return ret; }static int bpf_rhash_map_seq_show (struct seq_file *seq,void *v) { -return 0 ; +return __bpf_rhash_map_seq_show (seq, v); }static void bpf_rhash_map_seq_stop (struct seq_file *seq,void *v) { +struct bpf_iter_seq_rhash_map_info *info = seq->private; + +if (!v) + (void )__bpf_rhash_map_seq_show (seq,NULL ); + +if (info->iter_active) { +rhashtable_walk_stop (&info->iter); +rhashtable_walk_exit (&info->iter); + info->iter_active = false; + } }static int bpf_iter_init_rhash_map (void *priv_data,struct bpf_iter_aux_info *aux) { +struct bpf_iter_seq_rhash_map_info *info = priv_data; +struct bpf_map *map = aux->map; + + info->last_key =kmalloc (map->key_size,GFP_USER ); +if (!info->last_key) +return -ENOMEM ; + +bpf_map_inc_with_uref (map); + info->map = map; + info->rhtab = container_of(map, struct bpf_rhtab, map); + info->iter_active = false;return 0 ; }static void bpf_iter_fini_rhash_map (void *priv_data) { +struct bpf_iter_seq_rhash_map_info *info = priv_data; + +kfree (info->last_key); +bpf_map_put_with_uref (info->map); }static const struct seq_operations bpf_rhash_map_seq_ops = {
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab
Quoted 5 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Wire up
seq_fileBPF iterator forBPF_MAP_TYPE_RHASHso thatbpf_iterand bpftool map dump work with resizable hash maps.
Quoted 8 lines
Use
rhashtable_walk_enter_from()with a savedlast_keyto resume iteration acrossread()calls without linear skip from the beginning on eachseq_start.Also implement
rhtab_map_seq_show_elem()for bpftool map dump in non-iterator mode.Signed-off-by Mykyta Yatsenko <[email protected]>
Quoted 29 lines
--- kernel/bpf/hashtab.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 94 insertions(+), 4 deletions(-)kernel/bpf/hashtab.c +13
-0@@ -3008,6 +3008,19 @@ static int rhtab_map_get_next_key(struct bpf_map *map, void *key, void *next_keystatic void rhtab_map_seq_show_elem (struct bpf_map *map,void *key,struct seq_file *m) { +void *value; + +/* Guarantee that hashtab value is not freed */ +guard (rcu)(); + + value =rhtab_map_lookup_elem (map, key); +if (!value) +return ; + +btf_type_seq_show (map->btf, map->btf_key_type_id, key, m); +seq_puts (m,": " ); +btf_type_seq_show (map->btf, map->btf_value_type_id, value, m); +seq_putc (m,'\n' ); } static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3217
Quoted 5 lines
kernel/bpf/hashtab.c +1
-1@@ -3201,36 +3214,113 @@ struct bpf_iter_seq_rhash_map_info {struct bpf_map *map;struct bpf_rhtab *rhtab;struct rhashtable_iter iter; -u32 skip_elems; +void *last_key;
Nit: Could we avoid adding skip_elems to this in the first place since it's never used?
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3220
Quoted 3 lines
kernel/bpf/hashtab.c +0
-0bool iter_active; };
Question: Would it make sense/be worth annotating the seq functions with __acquires/__releases(RCU)?
Quoted 109 lines
kernel/bpf/hashtab.c +80
-3static void *bpf_rhash_map_seq_start (struct seq_file *seq,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem; +void *key = *pos >0 ? info->last_key :NULL ; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&info->rhtab->ht, &info->iter, + key, info->rhtab->params); +rhashtable_walk_start (&info->iter); + } + info->iter_active = true; + + elem =rhtab_iter_next (&info->iter); +if (!elem) +return NULL ; +/* +* if *pos is not 0, previously iteration failed on this elem, +* so we are restarting it. That's why no need to increment *pos. +*/ +if (*pos ==0 ) + ++*pos; +return elem; }static void *bpf_rhash_map_seq_next (struct seq_file *seq,void *v,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem = v; + +/* Save current key for O(1) resume in next seq_start */ +memcpy (info->last_key, elem->data, info->map->key_size); + + ++*pos; + +return rhtab_iter_next (&info->iter); +} + +static int __bpf_rhash_map_seq_show (struct seq_file *seq, +struct rhtab_elem *elem) +{ +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct bpf_iter__bpf_map_elem ctx = {}; +struct bpf_iter_meta meta; +struct bpf_prog *prog; +int ret =0 ; + + meta.seq = seq; + prog =bpf_iter_get_info (&meta, elem ==NULL ); +if (prog) { + ctx.meta = &meta; + ctx.map = info->map; +if (elem) { + ctx.key = elem->data; + ctx.value =rhtab_elem_value (elem, info->map->key_size); + } + ret =bpf_iter_run_prog (prog, &ctx); + } + +return ret; }static int bpf_rhash_map_seq_show (struct seq_file *seq,void *v) { -return 0 ; +return __bpf_rhash_map_seq_show (seq, v); }static void bpf_rhash_map_seq_stop (struct seq_file *seq,void *v) { +struct bpf_iter_seq_rhash_map_info *info = seq->private; + +if (!v) + (void )__bpf_rhash_map_seq_show (seq,NULL ); + +if (info->iter_active) { +rhashtable_walk_stop (&info->iter); +rhashtable_walk_exit (&info->iter); + info->iter_active = false; + } }static int bpf_iter_init_rhash_map (void *priv_data,struct bpf_iter_aux_info *aux) { +struct bpf_iter_seq_rhash_map_info *info = priv_data; +struct bpf_map *map = aux->map; + + info->last_key =kmalloc (map->key_size,GFP_USER ); +if (!info->last_key) +return -ENOMEM ; + +bpf_map_inc_with_uref (map); + info->map = map; + info->rhtab = container_of(map, struct bpf_rhtab, map); + info->iter_active = false;return 0 ; }static void bpf_iter_fini_rhash_map (void *priv_data) { +struct bpf_iter_seq_rhash_map_info *info = priv_data; + +kfree (info->last_key); +bpf_map_put_with_uref (info->map); }static const struct seq_operations bpf_rhash_map_seq_ops = {
Re: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab
Quoted 44 lines · Emil Tsalapatis
Quoted 5 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Wire up
seq_fileBPF iterator forBPF_MAP_TYPE_RHASHso thatbpf_iterand bpftool map dump work with resizable hash maps.Quoted 8 lines
Use
rhashtable_walk_enter_from()with a savedlast_keyto resume iteration acrossread()calls without linear skip from the beginning on eachseq_start.Also implement
rhtab_map_seq_show_elem()for bpftool map dump in non-iterator mode.Signed-off-by Mykyta Yatsenko <[email protected]>Reviewed-by Emil Tsalapatis <[email protected]>Quoted 27 lines
--- kernel/bpf/hashtab.c | 98 +++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 94 insertions(+), 4 deletions(-)kernel/bpf/hashtab.c +13
-0@@ -3008,6 +3008,19 @@ static int rhtab_map_get_next_key(struct bpf_map *map, void *key, void *next_keystatic void rhtab_map_seq_show_elem (struct bpf_map *map,void *key,struct seq_file *m) { +void *value; + +/* Guarantee that hashtab value is not freed */ +guard (rcu)(); + + value =rhtab_map_lookup_elem (map, key); +if (!value) +return ; + +btf_type_seq_show (map->btf, map->btf_key_type_id, key, m); +seq_puts (m,": " ); +btf_type_seq_show (map->btf, map->btf_value_type_id, value, m); +seq_putc (m,'\n' ); }
Quoted 11 lines
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3217
Quoted 7 lines
kernel/bpf/hashtab.c +1
-1static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn,@@ -3201,36 +3214,113 @@ struct bpf_iter_seq_rhash_map_info {struct bpf_map *map;struct bpf_rhtab *rhtab;struct rhashtable_iter iter; -u32 skip_elems; +void *last_key;Nit: Could we avoid adding
skip_elemsto this in the first place since it's never used?
Definitely yes, thanks for noticing.
Quoted 7 lines
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3220
Quoted 3 lines
kernel/bpf/hashtab.c +0
-0bool iter_active; };Question: Would it make sense/be worth annotating the seq functions with __acquires/__releases(RCU)?
I guess it won't hurt.
Quoted 110 lines
Quoted 109 lines
kernel/bpf/hashtab.c +80
-3static void *bpf_rhash_map_seq_start (struct seq_file *seq,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem; +void *key = *pos >0 ? info->last_key :NULL ; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&info->rhtab->ht, &info->iter, + key, info->rhtab->params); +rhashtable_walk_start (&info->iter); + } + info->iter_active = true; + + elem =rhtab_iter_next (&info->iter); +if (!elem) +return NULL ; +/* +* if *pos is not 0, previously iteration failed on this elem, +* so we are restarting it. That's why no need to increment *pos. +*/ +if (*pos ==0 ) + ++*pos; +return elem; }static void *bpf_rhash_map_seq_next (struct seq_file *seq,void *v,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem = v; + +/* Save current key for O(1) resume in next seq_start */ +memcpy (info->last_key, elem->data, info->map->key_size); + + ++*pos; + +return rhtab_iter_next (&info->iter); +} + +static int __bpf_rhash_map_seq_show (struct seq_file *seq, +struct rhtab_elem *elem) +{ +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct bpf_iter__bpf_map_elem ctx = {}; +struct bpf_iter_meta meta; +struct bpf_prog *prog; +int ret =0 ; + + meta.seq = seq; + prog =bpf_iter_get_info (&meta, elem ==NULL ); +if (prog) { + ctx.meta = &meta; + ctx.map = info->map; +if (elem) { + ctx.key = elem->data; + ctx.value =rhtab_elem_value (elem, info->map->key_size); + } + ret =bpf_iter_run_prog (prog, &ctx); + } + +return ret; }static int bpf_rhash_map_seq_show (struct seq_file *seq,void *v) { -return 0 ; +return __bpf_rhash_map_seq_show (seq, v); }static void bpf_rhash_map_seq_stop (struct seq_file *seq,void *v) { +struct bpf_iter_seq_rhash_map_info *info = seq->private; + +if (!v) + (void )__bpf_rhash_map_seq_show (seq,NULL ); + +if (info->iter_active) { +rhashtable_walk_stop (&info->iter); +rhashtable_walk_exit (&info->iter); + info->iter_active = false; + } }static int bpf_iter_init_rhash_map (void *priv_data,struct bpf_iter_aux_info *aux) { +struct bpf_iter_seq_rhash_map_info *info = priv_data; +struct bpf_map *map = aux->map; + + info->last_key =kmalloc (map->key_size,GFP_USER ); +if (!info->last_key) +return -ENOMEM ; + +bpf_map_inc_with_uref (map); + info->map = map; + info->rhtab = container_of(map, struct bpf_rhtab, map); + info->iter_active = false;return 0 ; }static void bpf_iter_fini_rhash_map (void *priv_data) { +struct bpf_iter_seq_rhash_map_info *info = priv_data; + +kfree (info->last_key); +bpf_map_put_with_uref (info->map); }static const struct seq_operations bpf_rhash_map_seq_ops = {
[email protected]
AI reviewRe: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab
In reply to Mykyta YatsenkoThank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider: - [High] Uninitialized memory read in `last_key` when `seq_show` overflows. - [High]…
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [High] Uninitialized memory read in last_key when seq_show overflows.
- [High] rhashtable_walk_enter_from resets iterator on deleted cursor key, causing O(N^2) complexity and infinite loops.
- [Medium] Missing __GFP_NOWARN flag in user-controlled kmalloc for map->key_size can lead to OOM splats. --
--- Patch [8]: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab --- commit 226ce1988038cf4876ff0a72b5ae8e5ebc263151
Author: Mykyta Yatsenko <[email protected]>
bpf: Implement iterator APIs for resizable hashtab
Wire up seq_file BPF iterator for BPF_MAP_TYPE_RHASH so that bpf_iter and bpftool map dump work with resizable hash maps.
Quoted 4 lines
kernel/bpf/hashtab.c +0
-0
[ ... ]
Quoted 9 lines
kernel/bpf/hashtab.c +1
-1@@ -3205,36 +3218,113 @@ struct bpf_iter_seq_rhash_map_info {struct bpf_map *map;struct bpf_rhtab *rhtab;struct rhashtable_iter iter; -u32 skip_elems; +void *last_key;bool iter_active; };
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3233
Quoted 10 lines
kernel/bpf/hashtab.c +7
-1static void *bpf_rhash_map_seq_start (struct seq_file *seq,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem; +void *key = *pos >0 ? info->last_key :NULL ; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&info->rhtab->ht, &info->iter, + key, info->rhtab->params);
[Severity: High]
Will this silently restart iteration from bucket 0 if the cursor key is deleted?
rhashtable_walk_enter_from() looks up the provided cursor key to resume iteration. If the key is missing, it returns early and leaves the iterator at bucket 0 (iter->slot = 0).
In __rhtab_map_lookup_and_delete_batch(), the batch operation deletes elements and returns the last deleted key to userspace. On the next batch syscall, the user passes this deleted key back as the cursor. Since the key no longer exists, rhashtable_walk_enter_from() resets the iterator to 0.
The inner loop then executes while (total < max_count) holding rcu_read_lock(), rescanning all previously emptied buckets from the beginning of the table.
For lookup_batch and seq_file iterators, does this yield massive duplicate outputs to userspace and enormous RCU stall times?
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3242
Quoted 13 lines
kernel/bpf/hashtab.c +13
-0+rhashtable_walk_start (&info->iter); + } + info->iter_active = true; + + elem =rhtab_iter_next (&info->iter); +if (!elem) +return NULL ; +/* +* if *pos is not 0, previously iteration failed on this elem, +* so we are restarting it. That's why no need to increment *pos. +*/ +if (*pos ==0 ) + ++*pos;
[Severity: High]
Does this pass uninitialized memory as a hash key if seq_show() output overflows?
When reading a BPF iterator, seq_read_iter() calls bpf_rhash_map_seq_start(), which increments *pos from 0 to 1 and returns the first element.
If the output of seq_show() for this element exceeds the initial seq_file buffer, the buffer overflows. The sequence machinery reallocates a larger buffer and calls seq_start() again.
Since *pos is now 1, the code executes key = info->last_key. However, last_key is only populated in seq_next(), which hasn't been called yet. Thus, last_key remains uninitialized from its kmalloc(..., GFP_USER) allocation.
Quoted 2 lines
kernel/bpf/hashtab.c +1
-0+return elem; }
[ ... ]
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3307
Quoted 6 lines
static int
bpf_iter_init_rhash_map(void *priv_data, struct bpf_iter_aux_info *aux){kernel/bpf/hashtab.c +4
-0+struct bpf_iter_seq_rhash_map_info *info = priv_data; +struct bpf_map *map = aux->map; + + info->last_key =kmalloc (map->key_size,GFP_USER );
[Severity: Medium]
Does this need __GFP_NOWARN?
Since BPF hash map key sizes can be extremely large, requesting large contiguous memory blocks without __GFP_NOWARN can fail loudly under memory fragmentation and trigger high-order page allocation warnings.
Quoted 9 lines
kernel/bpf/hashtab.c +7
-0+if (!info->last_key) +return -ENOMEM ; + +bpf_map_inc_with_uref (map); + info->map = map; + info->rhtab = container_of(map, struct bpf_rhtab, map); + info->iter_active = false;return 0 ; }
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=8
Re: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab
Is it really a good use of tokens for sashiko to review old patches that have either landed or were significantly changed since (and probably got a bunch of new revisions sent), or just plain forgotten by now?
Did something regress recently? I'm not sure this has happened before until recently...
-- Andrii
Quoted 122 lines · On Thu, Aug 13, 2026 at 4:59 PM <[email protected]> wrote:
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [High] Uninitialized memory read inlast_keywhenseq_showoverflows.
- [High]rhashtable_walk_enter_fromresets iterator on deleted cursor key, causing O(N^2) complexity and infinite loops.
- [Medium] Missing__GFP_NOWARNflag in user-controlled kmalloc formap->key_sizecan lead to OOM splats. ----- Patch [8]: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab --- commit
226ce1988038cf4876ff0a72b5ae8e5ebc263151
Author: Mykyta Yatsenko <[email protected]>bpf: Implement iterator APIs for resizable hashtab
Wire up
seq_fileBPF iterator forBPF_MAP_TYPE_RHASHso thatbpf_iterand bpftool map dump work with resizable hash maps.Quoted 4 lines
kernel/bpf/hashtab.c +0
-0[ ... ]
Quoted 9 lines
kernel/bpf/hashtab.c +1
-1@@ -3205,36 +3218,113 @@ struct bpf_iter_seq_rhash_map_info {struct bpf_map *map;struct bpf_rhtab *rhtab;struct rhashtable_iter iter; -u32 skip_elems; +void *last_key;bool iter_active; };kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3233
Quoted 10 lines
kernel/bpf/hashtab.c +7
-1static void *bpf_rhash_map_seq_start (struct seq_file *seq,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem; +void *key = *pos >0 ? info->last_key :NULL ; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&info->rhtab->ht, &info->iter, + key, info->rhtab->params);[Severity: High]
Will this silently restart iteration from bucket 0 if the cursor key is deleted?
rhashtable_walk_enter_from()looks up the provided cursor key to resume iteration. If the key is missing, it returns early and leaves the iterator at bucket 0 (iter->slot= 0).In
__rhtab_map_lookup_and_delete_batch(), the batch operation deletes elements and returns the last deleted key to userspace. On the next batch syscall, the user passes this deleted key back as the cursor. Since the key no longer exists,rhashtable_walk_enter_from()resets the iterator to 0.The inner loop then executes while (total <
max_count) holdingrcu_read_lock(), rescanning all previously emptied buckets from the beginning of the table.For
lookup_batchandseq_fileiterators, does this yield massive duplicate outputs to userspace and enormous RCU stall times?kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3242
Quoted 13 lines
kernel/bpf/hashtab.c +13
-0+rhashtable_walk_start (&info->iter); + } + info->iter_active = true; + + elem =rhtab_iter_next (&info->iter); +if (!elem) +return NULL ; +/* +* if *pos is not 0, previously iteration failed on this elem, +* so we are restarting it. That's why no need to increment *pos. +*/ +if (*pos ==0 ) + ++*pos;[Severity: High]
Does this pass uninitialized memory as a hash key ifseq_show()output overflows?When reading a BPF iterator,
seq_read_iter()callsbpf_rhash_map_seq_start(), which increments *pos from 0 to 1 and returns the first element.If the output of
seq_show()for this element exceeds the initialseq_filebuffer, the buffer overflows. The sequence machinery reallocates a larger buffer and callsseq_start()again.Since *pos is now 1, the code executes key =
info->last_key. However,last_keyis only populated inseq_next(), which hasn't been called yet. Thus,last_keyremains uninitialized from itskmalloc(..., GFP_USER)allocation.Quoted 2 lines
kernel/bpf/hashtab.c +1
-0+return elem; }[ ... ]
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3307
Quoted 6 lines
static int
bpf_iter_init_rhash_map(void *priv_data, struct bpf_iter_aux_info *aux){kernel/bpf/hashtab.c +4
-0+struct bpf_iter_seq_rhash_map_info *info = priv_data; +struct bpf_map *map = aux->map; + + info->last_key =kmalloc (map->key_size,GFP_USER );[Severity: Medium]
Does this need__GFP_NOWARN?Since BPF hash map key sizes can be extremely large, requesting large contiguous memory blocks without
__GFP_NOWARNcan fail loudly under memory fragmentation and trigger high-order page allocation warnings.kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3316
Quoted 9 lines
kernel/bpf/hashtab.c +7
-0+if (!info->last_key) +return -ENOMEM ; + +bpf_map_inc_with_uref (map); + info->map = map; + info->rhtab = container_of(map, struct bpf_rhtab, map); + info->iter_active = false;return 0 ; }--
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=8
Re: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab
Quoted 10 lines · Andrii Nakryiko
Is it really a good use of tokens for sashiko to review old patches that have either landed or were significantly changed since (and probably got a bunch of new revisions sent), or just plain forgotten by now?
Did something regress recently? I'm not sure this has happened before until recently...
Ooops, it’s probably a recent regression I had which blocked sashiko reviews for few hours, so I had to restart some patch(set) semi-manually. Likely this one accidentally got into this group. Should be a one time off though.
Thanks for reporting!
Quoted 126 lines
-- Andrii
Quoted 123 lines · On Thu, Aug 13, 2026 at 4:59 PM <[email protected]> wrote:
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [High] Uninitialized memory read inlast_keywhenseq_showoverflows.
- [High]rhashtable_walk_enter_fromresets iterator on deleted cursor key, causing O(N^2) complexity and infinite loops.
- [Medium] Missing__GFP_NOWARNflag in user-controlled kmalloc formap->key_sizecan lead to OOM splats. ----- Patch [8]: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab --- commit
226ce1988038cf4876ff0a72b5ae8e5ebc263151
Author: Mykyta Yatsenko <[email protected]>bpf: Implement iterator APIs for resizable hashtab
Wire up
seq_fileBPF iterator forBPF_MAP_TYPE_RHASHso thatbpf_iterand bpftool map dump work with resizable hash maps.Quoted 4 lines
kernel/bpf/hashtab.c +0
-0[ ... ]
Quoted 9 lines
kernel/bpf/hashtab.c +1
-1@@ -3205,36 +3218,113 @@ struct bpf_iter_seq_rhash_map_info {struct bpf_map *map;struct bpf_rhtab *rhtab;struct rhashtable_iter iter; -u32 skip_elems; +void *last_key;bool iter_active; };kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3233
Quoted 10 lines
kernel/bpf/hashtab.c +7
-1static void *bpf_rhash_map_seq_start (struct seq_file *seq,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem; +void *key = *pos >0 ? info->last_key :NULL ; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&info->rhtab->ht, &info->iter, + key, info->rhtab->params);[Severity: High]
Will this silently restart iteration from bucket 0 if the cursor key is deleted?
rhashtable_walk_enter_from()looks up the provided cursor key to resume iteration. If the key is missing, it returns early and leaves the iterator at bucket 0 (iter->slot= 0).In
__rhtab_map_lookup_and_delete_batch(), the batch operation deletes elements and returns the last deleted key to userspace. On the next batch syscall, the user passes this deleted key back as the cursor. Since the key no longer exists,rhashtable_walk_enter_from()resets the iterator to 0.The inner loop then executes while (total <
max_count) holdingrcu_read_lock(), rescanning all previously emptied buckets from the beginning of the table.For
lookup_batchandseq_fileiterators, does this yield massive duplicate outputs to userspace and enormous RCU stall times?kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3242
Quoted 13 lines
kernel/bpf/hashtab.c +13
-0+rhashtable_walk_start (&info->iter); + } + info->iter_active = true; + + elem =rhtab_iter_next (&info->iter); +if (!elem) +return NULL ; +/* +* if *pos is not 0, previously iteration failed on this elem, +* so we are restarting it. That's why no need to increment *pos. +*/ +if (*pos ==0 ) + ++*pos;[Severity: High]
Does this pass uninitialized memory as a hash key ifseq_show()output overflows?When reading a BPF iterator,
seq_read_iter()callsbpf_rhash_map_seq_start(), which increments *pos from 0 to 1 and returns the first element.If the output of
seq_show()for this element exceeds the initialseq_filebuffer, the buffer overflows. The sequence machinery reallocates a larger buffer and callsseq_start()again.Since *pos is now 1, the code executes key =
info->last_key. However,last_keyis only populated inseq_next(), which hasn't been called yet. Thus,last_keyremains uninitialized from itskmalloc(..., GFP_USER)allocation.Quoted 2 lines
kernel/bpf/hashtab.c +1
-0+return elem; }[ ... ]
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3307
Quoted 6 lines
static int
bpf_iter_init_rhash_map(void *priv_data, struct bpf_iter_aux_info *aux){kernel/bpf/hashtab.c +4
-0+struct bpf_iter_seq_rhash_map_info *info = priv_data; +struct bpf_map *map = aux->map; + + info->last_key =kmalloc (map->key_size,GFP_USER );[Severity: Medium]
Does this need__GFP_NOWARN?Since BPF hash map key sizes can be extremely large, requesting large contiguous memory blocks without
__GFP_NOWARNcan fail loudly under memory fragmentation and trigger high-order page allocation warnings.Quoted 9 lines
kernel/bpf/hashtab.c +7
-0+if (!info->last_key) +return -ENOMEM ; + +bpf_map_inc_with_uref (map); + info->map = map; + info->rhtab = container_of(map, struct bpf_rhtab, map); + info->iter_active = false;return 0 ;}
--
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=8
Re: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab
Quoted 9 lines · Roman Gushchin
Quoted 9 lines · Andrii Nakryiko
Is it really a good use of tokens for sashiko to review old patches that have either landed or were significantly changed since (and probably got a bunch of new revisions sent), or just plain forgotten by now?
Quoted 6 lines
Quoted 2 lines
Did something regress recently? I'm not sure this has happened before until recently...
Ooops, it’s probably a recent regression I had which blocked sashiko reviews for few hours, so I had to restart some patch(set) semi-manually. Likely this one accidentally got into this group. Should be a one time off though.
It's not just this patch, we've had quite a bunch of sashiko reviews for months-old patches in the last few days. Just wanted to raise awareness as this doesn't seem to be intentional.
But ok, let's hope this is a one-time glitch :)
Quoted 130 lines
Thanks for reporting!
Quoted 126 lines
-- Andrii
Quoted 123 lines · On Thu, Aug 13, 2026 at 4:59 PM <[email protected]> wrote:
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [High] Uninitialized memory read inlast_keywhenseq_showoverflows.
- [High]rhashtable_walk_enter_fromresets iterator on deleted cursor key, causing O(N^2) complexity and infinite loops.
- [Medium] Missing__GFP_NOWARNflag in user-controlled kmalloc formap->key_sizecan lead to OOM splats. ----- Patch [8]: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab --- commit
226ce1988038cf4876ff0a72b5ae8e5ebc263151
Author: Mykyta Yatsenko <[email protected]>bpf: Implement iterator APIs for resizable hashtab
Wire up
seq_fileBPF iterator forBPF_MAP_TYPE_RHASHso thatbpf_iterand bpftool map dump work with resizable hash maps.Quoted 4 lines
kernel/bpf/hashtab.c +0
-0[ ... ]
Quoted 9 lines
kernel/bpf/hashtab.c +1
-1@@ -3205,36 +3218,113 @@ struct bpf_iter_seq_rhash_map_info {struct bpf_map *map;struct bpf_rhtab *rhtab;struct rhashtable_iter iter; -u32 skip_elems; +void *last_key;bool iter_active; };kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3233
Quoted 10 lines
kernel/bpf/hashtab.c +7
-1static void *bpf_rhash_map_seq_start (struct seq_file *seq,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem; +void *key = *pos >0 ? info->last_key :NULL ; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&info->rhtab->ht, &info->iter, + key, info->rhtab->params);[Severity: High]
Will this silently restart iteration from bucket 0 if the cursor key is deleted?
rhashtable_walk_enter_from()looks up the provided cursor key to resume iteration. If the key is missing, it returns early and leaves the iterator at bucket 0 (iter->slot= 0).In
__rhtab_map_lookup_and_delete_batch(), the batch operation deletes elements and returns the last deleted key to userspace. On the next batch syscall, the user passes this deleted key back as the cursor. Since the key no longer exists,rhashtable_walk_enter_from()resets the iterator to 0.The inner loop then executes while (total <
max_count) holdingrcu_read_lock(), rescanning all previously emptied buckets from the beginning of the table.For
lookup_batchandseq_fileiterators, does this yield massive duplicate outputs to userspace and enormous RCU stall times?kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3242
Quoted 13 lines
kernel/bpf/hashtab.c +13
-0+rhashtable_walk_start (&info->iter); + } + info->iter_active = true; + + elem =rhtab_iter_next (&info->iter); +if (!elem) +return NULL ; +/* +* if *pos is not 0, previously iteration failed on this elem, +* so we are restarting it. That's why no need to increment *pos. +*/ +if (*pos ==0 ) + ++*pos;[Severity: High]
Does this pass uninitialized memory as a hash key ifseq_show()output overflows?When reading a BPF iterator,
seq_read_iter()callsbpf_rhash_map_seq_start(), which increments *pos from 0 to 1 and returns the first element.If the output of
seq_show()for this element exceeds the initialseq_filebuffer, the buffer overflows. The sequence machinery reallocates a larger buffer and callsseq_start()again.Since *pos is now 1, the code executes key =
info->last_key. However,last_keyis only populated inseq_next(), which hasn't been called yet. Thus,last_keyremains uninitialized from itskmalloc(..., GFP_USER)allocation.Quoted 2 lines
kernel/bpf/hashtab.c +1
-0+return elem; }[ ... ]
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3307
Quoted 6 lines
static int
bpf_iter_init_rhash_map(void *priv_data, struct bpf_iter_aux_info *aux){kernel/bpf/hashtab.c +4
-0+struct bpf_iter_seq_rhash_map_info *info = priv_data; +struct bpf_map *map = aux->map; + + info->last_key =kmalloc (map->key_size,GFP_USER );[Severity: Medium]
Does this need__GFP_NOWARN?Since BPF hash map key sizes can be extremely large, requesting large contiguous memory blocks without
__GFP_NOWARNcan fail loudly under memory fragmentation and trigger high-order page allocation warnings.Quoted 9 lines
kernel/bpf/hashtab.c +7
-0+if (!info->last_key) +return -ENOMEM ; + +bpf_map_inc_with_uref (map); + info->map = map; + info->rhtab = container_of(map, struct bpf_rhtab, map); + info->iter_active = false;return 0 ;}
--
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=8
Re: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab
Quoted 21 lines · Andrii Nakryiko
Quoted 9 lines · Roman Gushchin
Quoted 9 lines
Quoted 3 lines · Andrii Nakryiko
Is it really a good use of tokens for sashiko to review old patches that have either landed or were significantly changed since (and probably got a bunch of new revisions sent), or just plain forgotten by now?
Quoted 6 lines
Quoted 2 lines
Did something regress recently? I'm not sure this has happened before until recently...
Ooops, it’s probably a recent regression I had which blocked sashiko reviews for few hours, so I had to restart some patch(set) semi-manually. Likely this one accidentally got into this group. Should be a one time off though.
Quoted 5 lines
It's not just this patch, we've had quite a bunch of sashiko reviews for months-old patches in the last few days. Just wanted to raise awareness as this doesn't seem to be intentional.
But ok, let's hope this is a one-time glitch :)
It should not happen anymore, they all should have been sent yesterday, whatever the number was. If you see any new coming, please, let me know.
Thanks
Quoted 131 lines
Quoted 131 lines
Thanks for reporting!
Quoted 126 lines
-- Andrii
Quoted 123 lines · On Thu, Aug 13, 2026 at 4:59 PM <[email protected]> wrote:
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [High] Uninitialized memory read inlast_keywhenseq_showoverflows.
- [High]rhashtable_walk_enter_fromresets iterator on deleted cursor key, causing O(N^2) complexity and infinite loops.
- [Medium] Missing__GFP_NOWARNflag in user-controlled kmalloc formap->key_sizecan lead to OOM splats. ----- Patch [8]: [PATCH RFC bpf-next v2 08/18] bpf: Implement iterator APIs for resizable hashtab --- commit
226ce1988038cf4876ff0a72b5ae8e5ebc263151
Author: Mykyta Yatsenko <[email protected]>bpf: Implement iterator APIs for resizable hashtab
Wire up
seq_fileBPF iterator forBPF_MAP_TYPE_RHASHso thatbpf_iterand bpftool map dump work with resizable hash maps.Quoted 4 lines
kernel/bpf/hashtab.c +0
-0[ ... ]
Quoted 9 lines
kernel/bpf/hashtab.c +1
-1@@ -3205,36 +3218,113 @@ struct bpf_iter_seq_rhash_map_info {struct bpf_map *map;struct bpf_rhtab *rhtab;struct rhashtable_iter iter; -u32 skip_elems; +void *last_key;bool iter_active; };kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3233
Quoted 10 lines
kernel/bpf/hashtab.c +7
-1static void *bpf_rhash_map_seq_start (struct seq_file *seq,loff_t *pos) { -return NULL ; +struct bpf_iter_seq_rhash_map_info *info = seq->private; +struct rhtab_elem *elem; +void *key = *pos >0 ? info->last_key :NULL ; + +scoped_guard (rcu) { +rhashtable_walk_enter_from (&info->rhtab->ht, &info->iter, + key, info->rhtab->params);[Severity: High]
Will this silently restart iteration from bucket 0 if the cursor key is deleted?
rhashtable_walk_enter_from()looks up the provided cursor key to resume iteration. If the key is missing, it returns early and leaves the iterator at bucket 0 (iter->slot= 0).In
__rhtab_map_lookup_and_delete_batch(), the batch operation deletes elements and returns the last deleted key to userspace. On the next batch syscall, the user passes this deleted key back as the cursor. Since the key no longer exists,rhashtable_walk_enter_from()resets the iterator to 0.The inner loop then executes while (total <
max_count) holdingrcu_read_lock(), rescanning all previously emptied buckets from the beginning of the table.For
lookup_batchandseq_fileiterators, does this yield massive duplicate outputs to userspace and enormous RCU stall times?kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3242
Quoted 13 lines
kernel/bpf/hashtab.c +13
-0+rhashtable_walk_start (&info->iter); + } + info->iter_active = true; + + elem =rhtab_iter_next (&info->iter); +if (!elem) +return NULL ; +/* +* if *pos is not 0, previously iteration failed on this elem, +* so we are restarting it. That's why no need to increment *pos. +*/ +if (*pos ==0 ) + ++*pos;[Severity: High]
Does this pass uninitialized memory as a hash key ifseq_show()output overflows?When reading a BPF iterator,
seq_read_iter()callsbpf_rhash_map_seq_start(), which increments *pos from 0 to 1 and returns the first element.If the output of
seq_show()for this element exceeds the initialseq_filebuffer, the buffer overflows. The sequence machinery reallocates a larger buffer and callsseq_start()again.Since *pos is now 1, the code executes key =
info->last_key. However,last_keyis only populated inseq_next(), which hasn't been called yet. Thus,last_keyremains uninitialized from itskmalloc(..., GFP_USER)allocation.Quoted 2 lines
kernel/bpf/hashtab.c +1
-0+return elem; }[ ... ]
kernel/bpf/hashtab.c struct bpf_iter_seq_rhash_map_info { · line 3307
Quoted 6 lines
static int
bpf_iter_init_rhash_map(void *priv_data, struct bpf_iter_aux_info *aux){kernel/bpf/hashtab.c +4
-0+struct bpf_iter_seq_rhash_map_info *info = priv_data; +struct bpf_map *map = aux->map; + + info->last_key =kmalloc (map->key_size,GFP_USER );[Severity: Medium]
Does this need__GFP_NOWARN?Since BPF hash map key sizes can be extremely large, requesting large contiguous memory blocks without
__GFP_NOWARNcan fail loudly under memory fragmentation and trigger high-order page allocation warnings.Quoted 9 lines
kernel/bpf/hashtab.c +7
-0+if (!info->last_key) +return -ENOMEM ; + +bpf_map_inc_with_uref (map); + info->map = map; + info->rhtab = container_of(map, struct bpf_rhtab, map); + info->iter_active = false;return 0 ;}
--
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=8
RFC PATCH v2 9/18 bpf: Implement alloc and free for resizable hashtab
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Initialize rhashtable with bpf_mem_alloc element cache. Require BPF_F_NO_PREALLOC. Limit max_entries to 2^31. Free elements via rhashtable_free_and_destroy() callback to handle internal structs.
--- kernel/bpf/hashtab.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 60 insertions(+), 2 deletions(-)
kernel/bpf/hashtab.c +60 -2
@@ -2762,16 +2762,74 @@ static inline void *rhtab_elem_value(struct rhtab_elem *l, u32 key_size)static struct bpf_map *rhtab_map_alloc (union bpf_attr *attr) { -return ERR_PTR (-EOPNOTSUPP ); +struct bpf_rhtab *rhtab; +int err =0 ; + + rhtab =bpf_map_area_alloc (sizeof (*rhtab),NUMA_NO_NODE ); +if (!rhtab) +return ERR_PTR (-ENOMEM ); + +bpf_map_init_from_attr (&rhtab->map, attr); + +if (rhtab->map.max_entries >1UL <<31 ) { + err = -E2BIG ; + goto free_rhtab; + } + + rhtab->elem_size =sizeof (struct rhtab_elem ) +round_up (rhtab->map.key_size,8 ) + +round_up (rhtab->map.value_size,8 ); + + rhtab->params.head_offset = offsetof(struct rhtab_elem , node); + rhtab->params.key_offset = offsetof(struct rhtab_elem , data); + rhtab->params.key_len = rhtab->map.key_size; + + err =rhashtable_init (&rhtab->ht, &rhtab->params); +if (err) + goto free_rhtab; + +/* Set max_elems after rhashtable_init() since init zeroes the struct */ + rhtab->ht.max_elems = rhtab->map.max_entries; + + err =bpf_mem_alloc_init (&rhtab->ma, rhtab->elem_size, false); +if (err) + goto destroy_rhtab; + +return &rhtab->map; + +destroy_rhtab: +rhashtable_destroy (&rhtab->ht); +free_rhtab: +bpf_map_area_free (rhtab); +return ERR_PTR (err); }static int rhtab_map_alloc_check (union bpf_attr *attr) { -return -EOPNOTSUPP ; +if (!(attr->map_flags &BPF_F_NO_PREALLOC )) +return -EINVAL ; + +if (attr->map_flags &BPF_F_ZERO_SEED ) +return -EINVAL ; + +return htab_map_alloc_check (attr); +} + +static void rhtab_free_elem (void *ptr,void *arg) +{ +struct bpf_rhtab *rhtab = arg; +struct rhtab_elem *elem = ptr; + +bpf_map_free_internal_structs (&rhtab->map,rhtab_elem_value (elem, rhtab->map.key_size)); +bpf_mem_cache_free_rcu (&rhtab->ma, elem); }static void rhtab_map_free (struct bpf_map *map) { + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); + +rhashtable_free_and_destroy (&rhtab->ht, rhtab_free_elem, rhtab); +bpf_mem_alloc_destroy (&rhtab->ma); +bpf_map_area_free (rhtab); }static void *rhtab_lookup_elem (struct bpf_map *map,void *key)
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 09/18] bpf: Implement alloc and free for resizable hashtab
Quoted 17 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Initialize rhashtable with
bpf_mem_allocelement cache. RequireBPF_F_NO_PREALLOC. Limitmax_entriesto 2^31. Free elements viarhashtable_free_and_destroy()callback to handle internal structs.Signed-off-by Mykyta Yatsenko <[email protected]>--- kernel/bpf/hashtab.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 60 insertions(+), 2 deletions(-)kernel/bpf/hashtab.c +0
-0
kernel/bpf/hashtab.c static inline void *rhtab_elem_value(struct rhtab_elem *l, u32 key_size) · line 2765
Quoted 5 lines
kernel/bpf/hashtab.c +1
-1@@ -2762,16 +2762,74 @@ static inline void *rhtab_elem_value(struct rhtab_elem *l, u32 key_size)static struct bpf_map *rhtab_map_alloc (union bpf_attr *attr) { -return ERR_PTR (-EOPNOTSUPP ); +struct bpf_rhtab *rhtab;
patches 6,7,8 are ok as step-by-step,
but this one should be squashed with 1-3
RFC PATCH v2 10/18 bpf: Allow timers, workqueues and task_work in resizable hashtab
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Without this, users needing deferred callbacks in a dynamically-sized map have no option — fixed-size htab is the only map supporting these field types. Resizable hashtab should offer the same capability.
Properly clean up BTF record fields on element delete and map teardown by wiring up bpf_obj_free_fields through a memory allocator destructor, matching the pattern used by htab for non-prealloc maps.
--- kernel/bpf/hashtab.c | 53 +++++++++++++++++++++++++++++++++++++++++----------- kernel/bpf/syscall.c | 1 + 2 files changed, 43 insertions(+), 11 deletions(-)
kernel/bpf/hashtab.c +42 -11
@@ -501,28 +501,26 @@ static void htab_dtor_ctx_free(void *ctx)kfree (ctx); } -static int htab_set_dtor (struct bpf_htab *htab,void (*dtor)(void *,void *)) +static int bpf_ma_set_dtor (struct bpf_map *map,struct bpf_mem_alloc *ma, +void (*dtor)(void *,void *)) { -u32 key_size = htab->map.key_size; -struct bpf_mem_alloc *ma;struct htab_btf_record *hrec;int err;/* No need for dtors. */ -if (IS_ERR_OR_NULL (htab->map.record)) +if (IS_ERR_OR_NULL (map->record))return 0 ; hrec =kzalloc (sizeof (*hrec),GFP_KERNEL );if (!hrec)return -ENOMEM ; - hrec->key_size = key_size; - hrec->record =btf_record_dup (htab->map.record); + hrec->key_size = map->key_size; + hrec->record =btf_record_dup (map->record);if (IS_ERR (hrec->record)) { err =PTR_ERR (hrec->record);kfree (hrec);return err; } - ma =htab_is_percpu (htab) ? &htab->pcpu_ma : &htab->ma;bpf_mem_alloc_set_dtor (ma, dtor, htab_dtor_ctx_free, hrec);return 0 ; }
@@ -539,9 +537,9 @@ static int htab_map_check_btf(struct bpf_map *map, const struct btf *btf,* populated in htab_map_alloc(), so it will always appear as NULL. */ if (htab_is_percpu (htab)) -return htab_set_dtor (htab, htab_pcpu_mem_dtor); +return bpf_ma_set_dtor (map, &htab->pcpu_ma, htab_pcpu_mem_dtor);else -return htab_set_dtor (htab, htab_mem_dtor); +return bpf_ma_set_dtor (map, &htab->ma, htab_mem_dtor); }static struct bpf_map *htab_map_alloc (union bpf_attr *attr)
@@ -2814,12 +2812,43 @@ static int rhtab_map_alloc_check(union bpf_attr *attr)return htab_map_alloc_check (attr); } +static void rhtab_check_and_free_fields (struct bpf_rhtab *rhtab, +struct rhtab_elem *elem) +{ +if (IS_ERR_OR_NULL (rhtab->map.record)) +return ; + +bpf_obj_free_fields (rhtab->map.record, +rhtab_elem_value (elem, rhtab->map.key_size)); +} + +static void rhtab_mem_dtor (void *obj,void *ctx) +{ +struct htab_btf_record *hrec = ctx; +struct rhtab_elem *elem = obj; + +if (IS_ERR_OR_NULL (hrec->record)) +return ; + +bpf_obj_free_fields (hrec->record, +rhtab_elem_value (elem, hrec->key_size)); +} + +static int rhtab_map_check_btf (struct bpf_map *map,const struct btf *btf, +const struct btf_type *key_type, +const struct btf_type *value_type) +{ + struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); + +return bpf_ma_set_dtor (map, &rhtab->ma, rhtab_mem_dtor); +} +static void rhtab_free_elem (void *ptr,void *arg) {struct bpf_rhtab *rhtab = arg;struct rhtab_elem *elem = ptr; -bpf_map_free_internal_structs (&rhtab->map,rhtab_elem_value (elem, rhtab->map.key_size)); +rhtab_check_and_free_fields (rhtab, elem);bpf_mem_cache_free_rcu (&rhtab->ma, elem); }
@@ -2857,7 +2886,7 @@ static int rhtab_delete_elem(struct bpf_rhtab *rhtab, struct rhtab_elem *elem)if (err)return err; -bpf_map_free_internal_structs (&rhtab->map,rhtab_elem_value (elem, rhtab->map.key_size)); +rhtab_check_and_free_fields (rhtab, elem);bpf_mem_cache_free_rcu (&rhtab->ma, elem);return 0 ; }
@@ -2951,6 +2980,7 @@ static long rhtab_map_update_elem(struct bpf_map *map, void *key, void *value, umemcpy (elem->data, key, map->key_size);copy_map_value (map,rhtab_elem_value (elem, map->key_size), value); +check_and_init_map_value (map,rhtab_elem_value (elem, map->key_size)); tmp =rhashtable_lookup_get_insert_fast (&rhtab->ht, &elem->node, rhtab->params);if (tmp) {
@@ -3403,6 +3433,7 @@ const struct bpf_map_ops rhtab_map_ops = { .map_free = rhtab_map_free, .map_get_next_key = rhtab_map_get_next_key, .map_release_uref = rhtab_map_free_internal_structs, + .map_check_btf = rhtab_map_check_btf, .map_lookup_elem = rhtab_map_lookup_elem, .map_lookup_and_delete_elem = rhtab_map_lookup_and_delete_elem, .map_update_elem = rhtab_map_update_elem,
kernel/bpf/syscall.c +1 -0
@@ -1302,6 +1302,7 @@ static int map_check_btf(struct bpf_map *map, struct bpf_token *token,case BPF_WORKQUEUE :case BPF_TASK_WORK :if (map->map_type !=BPF_MAP_TYPE_HASH && + map->map_type !=BPF_MAP_TYPE_RHASH && map->map_type !=BPF_MAP_TYPE_LRU_HASH && map->map_type !=BPF_MAP_TYPE_ARRAY ) { ret = -EOPNOTSUPP ;
Signature · 1 line
2.52.0
RFC PATCH v2 11/18 libbpf: Support resizable hashtable
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Add BPF_MAP_TYPE_RHASH to libbpf's map type name table and feature probing so that libbpf-based tools can create and identify resizable hash maps.
--- tools/lib/bpf/libbpf.c | 1 + tools/lib/bpf/libbpf_probes.c | 3 +++ 2 files changed, 4 insertions(+)
tools/lib/bpf/libbpf.c +1 -0
@@ -192,6 +192,7 @@ static const char * const map_type_name[] = { [BPF_MAP_TYPE_CGRP_STORAGE] = "cgrp_storage", [BPF_MAP_TYPE_ARENA] = "arena", [BPF_MAP_TYPE_INSN_ARRAY] = "insn_array", + [BPF_MAP_TYPE_RHASH] = "rhash", };static const char *const prog_type_name[] = {
tools/lib/bpf/libbpf_probes.c +3 -0
@@ -309,6 +309,9 @@ static int probe_map_create(enum bpf_map_type map_type) value_size =sizeof (__u64); opts.map_flags =BPF_F_NO_PREALLOC ;break ; +case BPF_MAP_TYPE_RHASH : + opts.map_flags =BPF_F_NO_PREALLOC ; +break ;case BPF_MAP_TYPE_CGROUP_STORAGE :case BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE : key_size =sizeof (struct bpf_cgroup_storage_key );
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 11/18] libbpf: Support resizable hashtable
Quoted 7 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Add
BPF_MAP_TYPE_RHASHto libbpf's map type name table and feature probing so that libbpf-based tools can create and identify resizable hash maps.Signed-off-by Mykyta Yatsenko <[email protected]>
Quoted 31 lines
--- tools/lib/bpf/libbpf.c | 1 + tools/lib/bpf/libbpf_probes.c | 3 +++ 2 files changed, 4 insertions(+)tools/lib/bpf/libbpf.c +1
-0@@ -192,6 +192,7 @@ static const char * const map_type_name[] = { [BPF_MAP_TYPE_CGRP_STORAGE] = "cgrp_storage", [BPF_MAP_TYPE_ARENA] = "arena", [BPF_MAP_TYPE_INSN_ARRAY] = "insn_array", + [BPF_MAP_TYPE_RHASH] = "rhash", };static const char *const prog_type_name[] = {tools/lib/bpf/libbpf_probes.c +3
-0@@ -309,6 +309,9 @@ static int probe_map_create(enum bpf_map_type map_type) value_size =sizeof (__u64); opts.map_flags =BPF_F_NO_PREALLOC ;break ; +case BPF_MAP_TYPE_RHASH : + opts.map_flags =BPF_F_NO_PREALLOC ; +break ;case BPF_MAP_TYPE_CGROUP_STORAGE :case BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE : key_size =sizeof (struct bpf_cgroup_storage_key );
RFC PATCH v2 12/18 selftests/bpf: Add basic tests for resizable hash map
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Test basic map operations (lookup, update, delete) for BPF_MAP_TYPE_RHASH including boundary conditions like duplicate key insertion and deletion of nonexistent keys.
--- tools/testing/selftests/bpf/prog_tests/rhash.c | 64 +++++++ tools/testing/selftests/bpf/progs/rhash.c | 242 +++++++++++++++++++++++++ 2 files changed, 306 insertions(+)
tools/testing/selftests/bpf/prog_tests/rhash.c new file +64 -0
@@ -0,0 +1,64 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */ +#include <test_progs.h> +#include <string.h> +#include <stdio.h> +#include "rhash.skel.h" +#include <linux/bpf.h> +#include <linux/perf_event.h> +#include <sys/syscall.h> + +static void rhash_run (const char *prog_name) +{ +struct rhash *skel; +struct bpf_program *prog; +LIBBPF_OPTS (bpf_test_run_opts, opts); +int err; + + skel =rhash__open (); +if (!ASSERT_OK_PTR (skel,"rhash__open" )) +return ; + + prog =bpf_object__find_program_by_name (skel->obj, prog_name); +if (!ASSERT_OK_PTR (prog,"bpf_object__find_program_by_name" )) + goto cleanup; +bpf_program__set_autoload (prog, true); + + err =rhash__load (skel); +if (!ASSERT_OK (err,"skel_load" )) + goto cleanup; + + err =bpf_prog_test_run_opts (bpf_program__fd (prog), &opts); +if (!ASSERT_OK (err,"prog run" )) + goto cleanup; + +if (!ASSERT_OK (skel->bss->err,"bss->err" )) + goto cleanup; + +cleanup: +rhash__destroy (skel); +} + +void test_rhash (void ) +{ +if (test__start_subtest ("test_rhash_lookup_update" )) +rhash_run ("test_rhash_lookup_update" ); + +if (test__start_subtest ("test_rhash_update_delete" )) +rhash_run ("test_rhash_update_delete" ); + +if (test__start_subtest ("test_rhash_update_elements" )) +rhash_run ("test_rhash_update_elements" ); + +if (test__start_subtest ("test_rhash_update_exist" )) +rhash_run ("test_rhash_update_exist" ); + +if (test__start_subtest ("test_rhash_update_any" )) +rhash_run ("test_rhash_update_any" ); + +if (test__start_subtest ("test_rhash_noexist_duplicate" )) +rhash_run ("test_rhash_noexist_duplicate" ); + +if (test__start_subtest ("test_rhash_delete_nonexistent" )) +rhash_run ("test_rhash_delete_nonexistent" ); +}
tools/testing/selftests/bpf/progs/rhash.c new file +242 -0
242 lines not on this page · raw message
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 12/18] selftests/bpf: Add basic tests for resizable hash map
Quoted 19 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Test basic map operations (lookup, update, delete) for
BPF_MAP_TYPE_RHASHincluding boundary conditions like duplicate key insertion and deletion of nonexistent keys.Signed-off-by Mykyta Yatsenko <[email protected]>--- tools/testing/selftests/bpf/prog_tests/rhash.c | 64 +++++++ tools/testing/selftests/bpf/progs/rhash.c | 242 +++++++++++++++++++++++++ 2 files changed, 306 insertions(+)tools/testing/selftests/bpf/prog_tests/rhash.c new file +0
-0
tools/testing/selftests/bpf/prog_tests/rhash.c line 2
Quoted 2 lines
tools/testing/selftests/bpf/prog_tests/rhash.c new file +2
-0@@ -0,0 +1,64 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Meta Platforms, Inc. and affiliates. */
year what?
RFC PATCH v2 13/18 selftests/bpf: Support resizable hashtab in test_maps
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Parameterize existing htab tests (test_hashmap, test_hashmap_sizes, test_hashmap_walk, htab_map_batch_ops) by map type so they run against BPF_MAP_TYPE_RHASH as well. Relax ordering and exact-count assertions where rhashtable resize makes them non-deterministic.
--- .../selftests/bpf/map_tests/htab_map_batch_ops.c | 22 +++- tools/testing/selftests/bpf/test_maps.c | 127 ++++++++++++++++----- 2 files changed, 114 insertions(+), 35 deletions(-)
tools/testing/selftests/bpf/map_tests/htab_map_batch_ops.c +17 -5
@@ -74,10 +74,11 @@ static void map_batch_verify(int *visited, __u32 max_entries, } } -void __test_map_lookup_and_delete_batch (bool is_pcpu) +void __test_map_lookup_and_delete_batch (enum bpf_map_type map_type) {__u32 batch, count, total, total_success; typedef BPF_DECLARE_PERCPU(int, value); +bool is_pcpu = (map_type ==BPF_MAP_TYPE_PERCPU_HASH );int map_fd, *keys, *visited, key;const __u32 max_entries =10 ;value pcpu_values[max_entries];
@@ -88,9 +89,13 @@ void __test_map_lookup_and_delete_batch(bool is_pcpu) .elem_flags = 0, .flags = 0, ); +struct bpf_map_create_opts map_opts = { + .sz =sizeof (map_opts), + .map_flags = (map_type ==BPF_MAP_TYPE_RHASH ) ?BPF_F_NO_PREALLOC :0 , + }; - map_fd =bpf_map_create (is_pcpu ?BPF_MAP_TYPE_PERCPU_HASH :BPF_MAP_TYPE_HASH , -"hash_map" ,sizeof (int ),sizeof (int ), max_entries,NULL ); + map_fd =bpf_map_create (map_type,"hash_map" ,sizeof (int ),sizeof (int ), + max_entries, &map_opts);CHECK (map_fd ==-1 ,"bpf_map_create()" ,"error:%s\n" ,strerror (errno));
@@ -261,13 +266,19 @@ void __test_map_lookup_and_delete_batch(bool is_pcpu)void htab_map_batch_ops (void ) { -__test_map_lookup_and_delete_batch (false); +__test_map_lookup_and_delete_batch (BPF_MAP_TYPE_HASH );printf ("test_%s:PASS\n" , __func__); }void htab_percpu_map_batch_ops (void ) { -__test_map_lookup_and_delete_batch (true); +__test_map_lookup_and_delete_batch (BPF_MAP_TYPE_PERCPU_HASH ); +printf ("test_%s:PASS\n" , __func__); +} + +void rhtab_map_batch_ops (void ) +{ +__test_map_lookup_and_delete_batch (BPF_MAP_TYPE_RHASH );printf ("test_%s:PASS\n" , __func__); }
@@ -275,4 +286,5 @@ void test_htab_map_batch_ops(void) {htab_map_batch_ops ();htab_percpu_map_batch_ops (); +rhtab_map_batch_ops (); }
tools/testing/selftests/bpf/test_maps.c +97 -30
273 lines not on this page · raw message
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 13/18] selftests/bpf: Support resizable hashtab in test_maps
Quoted 8 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Parameterize existing htab tests (
test_hashmap,test_hashmap_sizes,test_hashmap_walk,htab_map_batch_ops) by map type so they run againstBPF_MAP_TYPE_RHASHas well. Relax ordering and exact-count assertions where rhashtable resize makes them non-deterministic.
Quoted 5 lines
Signed-off-by Mykyta Yatsenko <[email protected]>--- .../selftests/bpf/map_tests/htab_map_batch_ops.c | 22 +++- tools/testing/selftests/bpf/test_maps.c | 127 ++++++++++++++++----- 2 files changed, 114 insertions(+), 35 deletions(-)
drop test_maps changes. It's quite obsolete. We probably should delete it.
RFC PATCH v2 14/18 selftests/bpf: Resizable hashtab BPF_F_LOCK tests
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Add tests validating resizable hash map handles BPF_F_LOCK flag as expected.
--- tools/testing/selftests/bpf/prog_tests/rhash.c | 99 ++++++++++++++++++++++++++ tools/testing/selftests/bpf/progs/rhash.c | 35 +++++++++ 2 files changed, 134 insertions(+)
tools/testing/selftests/bpf/prog_tests/rhash.c +99 -0
@@ -7,6 +7,7 @@#include <linux/bpf.h> #include <linux/perf_event.h> #include <sys/syscall.h> +#include <network_helpers.h> static void rhash_run (const char *prog_name) {
@@ -39,6 +40,100 @@ static void rhash_run(const char *prog_name)rhash__destroy (skel); } +struct lock_thread_args { +int prog_fd; +int map_fd; +}; + +struct lock_elem { +struct bpf_spin_lock lock; +int var[16 ]; +}; + +static void *spin_lock_thread (void *arg) +{ +struct lock_thread_args *args = arg; +LIBBPF_OPTS (bpf_test_run_opts, topts, + .data_in = &pkt_v4, + .data_size_in = sizeof(pkt_v4), + .repeat = 10000, + ); +int err; + + err =bpf_prog_test_run_opts (args->prog_fd, &topts); +if (err || topts.retval) +return (void *)1 ; + +return (void *)0 ; +} + +static void *parallel_map_access (void *arg) +{ +struct lock_thread_args *args = arg; +int i, j, key =0 ; +int err; +struct lock_elem val; + +for (i =0 ; i <10000 ; i++) { + err =bpf_map_lookup_elem_flags (args->map_fd, &key, &val,BPF_F_LOCK ); +if (err) +return (void *)1 ; +if (val.lock.val) +return (void *)1 ; +for (j =1 ; j <16 ; j++) { +if (val.var[j] != val.var[0 ]) +return (void *)1 ; + } + } + +return (void *)0 ; +} + +static void rhash_spin_lock_test (void ) +{ +struct lock_thread_args args; +struct rhash *skel; +struct lock_elem val = {}; +pthread_t thread_id[4 ]; +int err, key =0 , i; +void *ret; + + skel =rhash__open_and_load (); +if (!ASSERT_OK_PTR (skel,"rhash__open_and_load" )) +return ; + + args.prog_fd =bpf_program__fd (skel->progs.test_rhash_spin_lock); + args.map_fd =bpf_map__fd (skel->maps.rhmap_lock); + +/* Insert initial element with BPF_F_LOCK */ + err =bpf_map_update_elem (args.map_fd, &key, &val,BPF_F_LOCK ); +if (!ASSERT_OK (err,"initial update" )) + goto cleanup; + +/* Spawn 2 threads running BPF program (uses bpf_spin_lock) */ +for (i =0 ; i <2 ; i++) +if (!ASSERT_OK (pthread_create (&thread_id[i],NULL , + &spin_lock_thread, &args), +"pthread_create spin_lock" )) + goto cleanup; + +/* Spawn 2 threads doing parallel map access with BPF_F_LOCK */ +for (i =2 ; i <4 ; i++) +if (!ASSERT_OK (pthread_create (&thread_id[i],NULL , + ¶llel_map_access, &args), +"pthread_create parallel_map_access" )) + goto cleanup; + +/* Wait for all threads */ +for (i =0 ; i <4 ; i++) +if (!ASSERT_OK (pthread_join (thread_id[i], &ret),"pthread_join" ) || + !ASSERT_OK ((long )ret,"thread ret" )) + goto cleanup; + +cleanup: +rhash__destroy (skel); +} +void test_rhash (void ) {if (test__start_subtest ("test_rhash_lookup_update" ))
@@ -61,4 +156,8 @@ void test_rhash(void)if (test__start_subtest ("test_rhash_delete_nonexistent" ))rhash_run ("test_rhash_delete_nonexistent" ); + +if (test__start_subtest ("test_rhash_spin_lock" )) +rhash_spin_lock_test (); } +
tools/testing/selftests/bpf/progs/rhash.c +35 -0
@@ -240,3 +240,38 @@ int test_rhash_delete_nonexistent(void *ctx) err =0 ;return 0 ; } + +#define VAR_NUM 16 + +struct lock_elem { +struct bpf_spin_lock lock; +int var[VAR_NUM ]; +}; + +struct { + __uint(type, BPF_MAP_TYPE_RHASH); + __uint(map_flags, BPF_F_NO_PREALLOC); + __uint(max_entries, 1); + __type(key, __u32); + __type(value, struct lock_elem); +} rhmap_lock SEC(".maps"); + +SEC("cgroup/skb") +int test_rhash_spin_lock (struct __sk_buff *skb) +{ +struct lock_elem *val; +int rnd =bpf_get_prandom_u32 (); +int key =0 , i; + + val =bpf_map_lookup_elem (&rhmap_lock, &key); +if (!val) +return 1 ; + +/* spin_lock in resizable hash map */ +bpf_spin_lock (&val->lock); +for (i =0 ; i <VAR_NUM ; i++) + val->var[i] = rnd; +bpf_spin_unlock (&val->lock); + +return 0 ; +}
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 14/18] selftests/bpf: Resizable hashtab BPF_F_LOCK tests
Quoted 11 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Add tests validating resizable hash map handles
BPF_F_LOCKflag as expected.Signed-off-by Mykyta Yatsenko <[email protected]>--- tools/testing/selftests/bpf/prog_tests/rhash.c | 99 ++++++++++++++++++++++++++ tools/testing/selftests/bpf/progs/rhash.c | 35 +++++++++ 2 files changed, 134 insertions(+)
drop this patch completely. Yes, we know spinlock works.
RFC PATCH v2 15/18 selftests/bpf: Add stress tests for resizable hash get_next_key
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Test get_next_key behavior under concurrent modification:
* Resize test: verify all elements visited after resize trigger
* Stress test: concurrent iterators and modifiers to detect races
--- tools/testing/selftests/bpf/prog_tests/rhash.c | 181 +++++++++++++++++++++++++ tools/testing/selftests/bpf/progs/rhash.c | 8 ++ 2 files changed, 189 insertions(+)
tools/testing/selftests/bpf/prog_tests/rhash.c +181 -0
@@ -134,6 +134,181 @@ static void rhash_spin_lock_test(void)rhash__destroy (skel); } +struct iter_thread_args { +int map_fd; +int stop; +int error; +}; + +static void *get_next_key_thread (void *arg) +{ +struct iter_thread_args *args = arg; +int key, next_key; +int i =0 ; + +for (i =0 ; i <1000 ; i++) { +if (READ_ONCE (args->stop)) +break ; + +if (bpf_map_get_next_key (args->map_fd,NULL , &next_key) !=0 ) { +WRITE_ONCE (args->error,1 ); +continue ; + } + + key = next_key; +while (bpf_map_get_next_key (args->map_fd, &key, &next_key) ==0 ) + key = next_key; + } + +return (void *)0 ; +} + +static void *modifier_thread (void *arg) +{ +struct iter_thread_args *args = arg; +int key, value; +int i; + +for (i =0 ; i <10000 ; i++) { +if (READ_ONCE (args->stop)) +break ; + + key = i; + value = i; +if (bpf_map_update_elem (args->map_fd, &key, &value,BPF_ANY )) +WRITE_ONCE (args->error,1 ); + } + +return (void *)0 ; +} + +static void rhash_get_next_key_stress_test (void ) +{ +struct iter_thread_args args = {}; +struct rhash *skel; +pthread_t iter_threads[2 ]; +pthread_t mod_threads[2 ]; +int key, value; +int err, i; +void *ret; + + skel =rhash__open_and_load (); +if (!ASSERT_OK_PTR (skel,"rhash__open_and_load" )) +return ; + + args.map_fd =bpf_map__fd (skel->maps.rhmap_iter); + args.stop =0 ; + args.error =0 ; + +/* Pre-populate map */ +for (i =0 ; i <50 ; i++) { + key = i; + value = i; + err =bpf_map_update_elem (args.map_fd, &key, &value,BPF_NOEXIST ); +if (!ASSERT_OK (err,"initial insert" )) + goto cleanup; + } + +/* Iterator threads */ +for (i =0 ; i <2 ; i++) +if (!ASSERT_OK (pthread_create (&iter_threads[i],NULL , + &get_next_key_thread, &args), +"pthread_create iter" )) + goto cleanup; + +/* Modifier threads */ +for (i =0 ; i <2 ; i++) +if (!ASSERT_OK (pthread_create (&mod_threads[i],NULL , + &modifier_thread, &args), +"pthread_create mod" )) + goto cleanup; + +/* Wait for modifier threads to finish */ +for (i =0 ; i <2 ; i++) +pthread_join (mod_threads[i], &ret); + +/* Signal iterator threads to stop */ +WRITE_ONCE (args.stop,1 ); + +/* Wait for iterator threads */ +for (i =0 ; i <2 ; i++) +if (!ASSERT_OK (pthread_join (iter_threads[i], &ret),"pthread_join iter" ) || + !ASSERT_OK ((long )ret,"iter thread ret" )) + goto cleanup; + +ASSERT_EQ (args.error,0 ,"no infinite loop" ); + +cleanup: +rhash__destroy (skel); +} + +static void iterate_all (int map_fd,int num_elems) +{ +int *visited, key, next_key, i, err; + + visited =calloc (num_elems,sizeof (int )); +if (!ASSERT_TRUE (visited,"calloc" )) +return ; +memset (visited,0 , num_elems *sizeof (int )); + +for (err =bpf_map_get_next_key (map_fd,NULL , &next_key); err ==0 ; + err =bpf_map_get_next_key (map_fd, &key, &next_key)) { + key = next_key; +if (ASSERT_TRUE (key >=0 && key < num_elems,"key valid" )) + visited[key] +=1 ; + } + +for (i =0 ; i < num_elems; i++) +ASSERT_EQ (visited[i],1 ,"element visited" ); + +free (visited); +} + +static void rhash_get_next_key_resize_test (void ) +{ +struct rhash *skel; +int key, next_key, value; +int map_fd; +int err, i; + + skel =rhash__open_and_load (); +if (!ASSERT_OK_PTR (skel,"rhash__open_and_load" )) +return ; + + map_fd =bpf_map__fd (skel->maps.rhmap_iter); + +/* Phase 1: small table, no resize - verify completeness */ +for (i =0 ; i <4 ; i++) { + key = i; + value = i; + err =bpf_map_update_elem (map_fd, &key, &value,BPF_NOEXIST ); +if (!ASSERT_OK (err,"insert small" )) + goto cleanup; + } +iterate_all (map_fd,4 ); + +/* Phase 2: trigger resize by inserting more elements */ +for (i =4 ; i <100 ; i++) { + key = i; + value = i; + err =bpf_map_update_elem (map_fd, &key, &value,BPF_NOEXIST ); +if (!ASSERT_OK (err,"insert resize" )) + goto cleanup; + +/* Full iteration during resize - verify all code paths are safe */ +for (err =bpf_map_get_next_key (map_fd,NULL , &next_key); err ==0 ; + err =bpf_map_get_next_key (map_fd, &key, &next_key)) { + key = next_key; + } + } + +/* Phase 3: after resize settled - verify completeness */ +iterate_all (map_fd,100 ); + +cleanup: +rhash__destroy (skel); +} +void test_rhash (void ) {if (test__start_subtest ("test_rhash_lookup_update" ))
@@ -159,5 +334,11 @@ void test_rhash(void)if (test__start_subtest ("test_rhash_spin_lock" ))rhash_spin_lock_test (); + +if (test__start_subtest ("test_rhash_get_next_key_resize" )) +rhash_get_next_key_resize_test (); + +if (test__start_subtest ("test_rhash_get_next_key_stress" )) +rhash_get_next_key_stress_test (); }
tools/testing/selftests/bpf/progs/rhash.c +8 -0
@@ -256,6 +256,14 @@ struct { __type(value, struct lock_elem); } rhmap_lock SEC(".maps"); +struct { + __uint(type, BPF_MAP_TYPE_RHASH); + __uint(map_flags, BPF_F_NO_PREALLOC); + __uint(max_entries, 65536); + __type(key, int); + __type(value, int); +} rhmap_iter SEC(".maps"); + SEC("cgroup/skb")int test_rhash_spin_lock (struct __sk_buff *skb) {
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 15/18] selftests/bpf: Add stress tests for resizable hash get_next_key
Quoted 7 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Test
get_next_keybehavior under concurrent modification:
* Resize test: verify all elements visited after resize trigger
* Stress test: concurrent iterators and modifiers to detect races
Quoted 5 lines
Signed-off-by Mykyta Yatsenko <[email protected]>--- tools/testing/selftests/bpf/prog_tests/rhash.c | 181 +++++++++++++++++++++++++ tools/testing/selftests/bpf/progs/rhash.c | 8 ++ 2 files changed, 189 insertions(+)
I don't like this either. It's a test of rhashtable internals. If you really feel like testing it, it shouldn't be in selftests/bpf
RFC PATCH v2 16/18 selftests/bpf: Add BPF iterator tests for resizable hash map
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Test BPF iterator functionality for BPF_MAP_TYPE_RHASH:
* Basic iteration verifying all elements are visited
* Overflow test triggering seq_file restart, validating correct
resume behavior via skip_elems tracking
--- tools/testing/selftests/bpf/prog_tests/rhash.c | 160 ++++++++++++++++++++- .../selftests/bpf/progs/bpf_iter_bpf_rhash_map.c | 75 ++++++++++ 2 files changed, 234 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/prog_tests/rhash.c +159 -1
@@ -4,6 +4,7 @@#include <string.h> #include <stdio.h> #include "rhash.skel.h" +#include "bpf_iter_bpf_rhash_map.skel.h" #include <linux/bpf.h> #include <linux/perf_event.h> #include <sys/syscall.h>
@@ -309,6 +310,158 @@ static void rhash_get_next_key_resize_test(void)rhash__destroy (skel); } +static void rhash_iter_test (void ) +{ +DECLARE_LIBBPF_OPTS (bpf_iter_attach_opts, opts); +struct bpf_iter_bpf_rhash_map *skel; +int err, i, len, map_fd, iter_fd; +union bpf_iter_link_info linfo; +u32 expected_key_sum =0 , key; +struct bpf_link *link; +u64 val =0 ; +char buf[64 ]; + + skel =bpf_iter_bpf_rhash_map__open (); +if (!ASSERT_OK_PTR (skel,"bpf_iter_bpf_rhash_map__open" )) +return ; + + err =bpf_iter_bpf_rhash_map__load (skel); +if (!ASSERT_OK (err,"bpf_iter_bpf_rhash_map__load" )) + goto out; + + map_fd =bpf_map__fd (skel->maps.rhashmap); + +/* Populate map with test data */ +for (i =0 ; i <64 ; i++) { + key = i +1 ; + expected_key_sum += key; + + err =bpf_map_update_elem (map_fd, &key, &val,BPF_NOEXIST ); +if (!ASSERT_OK (err,"map_update" )) + goto out; + } + +memset (&linfo,0 ,sizeof (linfo)); + linfo.map.map_fd = map_fd; + opts.link_info = &linfo; + opts.link_info_len =sizeof (linfo); + + link =bpf_program__attach_iter (skel->progs.dump_bpf_rhash_map, &opts); +if (!ASSERT_OK_PTR (link,"attach_iter" )) + goto out; + + iter_fd =bpf_iter_create (bpf_link__fd (link)); +if (!ASSERT_GE (iter_fd,0 ,"create_iter" )) + goto free_link; + +do { + len =read (iter_fd, buf,sizeof (buf)); + }while (len >0 ); + +ASSERT_EQ (skel->bss->key_sum, expected_key_sum,"key_sum" ); +ASSERT_EQ (skel->bss->elem_count,64 ,"elem_count" ); + +close (iter_fd); + +free_link: +bpf_link__destroy (link); +out: +bpf_iter_bpf_rhash_map__destroy (skel); +} + +/* +* Test seq_file overflow handling for BPF iterator over resizable hashmap. +* +* The BPF program writes print_count * 8 bytes per element, configured so +* that a single element's output nearly fills the seq_file buffer (8 pages). +* With multiple elements, the buffer overflows mid-element, triggering +* seq_file's restart mechanism: it discards the partial output, enlarges or +* flushes the buffer, and re-invokes the BPF program starting from the +* element that caused the overflow. +* +* Insert few elements to avoid triggering rhashtable resize, then verify: +* - All elements are seen (unique_elem_count == num_elems) +* - Overflow occurred (total_visits > unique_elem_count) +* - Output is consistent (each chunk of print_count u64s has the same value) +*/ +static void rhash_iter_overflow_test (void ) +{ +DECLARE_LIBBPF_OPTS (bpf_iter_attach_opts, opts); +struct bpf_iter_bpf_rhash_map *skel; +u32 total_read_len, expected_read_len, write_len, num_elems =4 ; +int err, i, j, len, map_fd, iter_fd; +union bpf_iter_link_info linfo; +struct bpf_link *link; +char *buf; + + skel =bpf_iter_bpf_rhash_map__open (); +if (!ASSERT_OK_PTR (skel,"bpf_iter_bpf_rhash_map__open" )) +return ; + + write_len =sysconf (_SC_PAGE_SIZE) *8 ; + skel->bss->print_count = (write_len -8 ) /8 ; + expected_read_len = num_elems * (write_len -8 ); + + err =bpf_iter_bpf_rhash_map__load (skel); +if (!ASSERT_OK (err,"bpf_iter_bpf_rhash_map__load" )) + goto out; + + map_fd =bpf_map__fd (skel->maps.rhashmap); + +for (i =0 ; i < num_elems; i++) { +__u64 val = i; + + err =bpf_map_update_elem (map_fd, &i, &val,BPF_NOEXIST ); +if (!ASSERT_OK (err,"map_update" )) + goto out; + } + +memset (&linfo,0 ,sizeof (linfo)); + linfo.map.map_fd = map_fd; + opts.link_info = &linfo; + opts.link_info_len =sizeof (linfo); + + link =bpf_program__attach_iter (skel->progs.dump_bpf_rhash_map_overflow, &opts); +if (!ASSERT_OK_PTR (link,"attach_iter" )) + goto out; + + iter_fd =bpf_iter_create (bpf_link__fd (link)); +if (!ASSERT_GE (iter_fd,0 ,"create_iter" )) + goto free_link; + + buf =malloc (expected_read_len); +if (!ASSERT_OK_PTR (buf,"malloc" )) + goto close_iter; + + total_read_len =0 ; +while ((len =read (iter_fd, buf + total_read_len, + expected_read_len - total_read_len)) >0 ) + total_read_len += len; + +ASSERT_OK (len,"len" ); +ASSERT_EQ (total_read_len, expected_read_len,"total_read_len" ); +ASSERT_EQ (skel->bss->unique_elem_count, num_elems,"unique_elem_count" ); +ASSERT_GT (skel->bss->total_visits, skel->bss->unique_elem_count, +"overflow_occurred" ); + +/* Verify each output chunk is internally consistent */ +for (i =0 ; i < num_elems; i++) { +__u64 *val = ((__u64 *)buf) + i * skel->bss->print_count; + +ASSERT_LT (val[0 ], num_elems,"value_in_range" ); +for (j =1 ; j < skel->bss->print_count; j++) +ASSERT_EQ (val[j], val[0 ],"consistent_value" ); + } + +free (buf); +close_iter: +close (iter_fd); +free_link: +bpf_link__destroy (link); +out: +bpf_iter_bpf_rhash_map__destroy (skel); +} +void test_rhash (void ) {if (test__start_subtest ("test_rhash_lookup_update" ))
@@ -340,5 +493,10 @@ void test_rhash(void)if (test__start_subtest ("test_rhash_get_next_key_stress" ))rhash_get_next_key_stress_test (); -} +if (test__start_subtest ("test_rhash_iter" )) +rhash_iter_test (); + +if (test__start_subtest ("test_rhash_iter_overflow" )) +rhash_iter_overflow_test (); +}
tools/testing/selftests/bpf/progs/bpf_iter_bpf_rhash_map.c new file +75 -0
75 lines not on this page · raw message
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 16/18] selftests/bpf: Add BPF iterator tests for resizable hash map
Quoted 8 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Test BPF iterator functionality for
BPF_MAP_TYPE_RHASH:
* Basic iteration verifying all elements are visited
* Overflow test triggeringseq_filerestart, validating correct
resume behavior viaskip_elemstracking
Quoted 5 lines
Signed-off-by Mykyta Yatsenko <[email protected]>--- tools/testing/selftests/bpf/prog_tests/rhash.c | 160 ++++++++++++++++++++- .../selftests/bpf/progs/bpf_iter_bpf_rhash_map.c | 75 ++++++++++ 2 files changed, 234 insertions(+), 1 deletion(-)
too much code for little test coverage.
RFC PATCH v2 17/18 bpftool: Add rhash map documentation
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Make bpftool documentation aware of the resizable hash map.
--- tools/bpf/bpftool/Documentation/bpftool-map.rst | 2 +- tools/bpf/bpftool/map.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-)
tools/bpf/bpftool/Documentation/bpftool-map.rst +1 -1
@@ -56,7 +56,7 @@ MAP COMMANDS | | **cgroup_storage** | **reuseport_sockarray** | **percpu_cgroup_storage** | | **queue** | **stack** | **sk_storage** | **struct_ops** | **ringbuf** | **inode_storage** | | **task_storage** | **bloom_filter** | **user_ringbuf** | **cgrp_storage** | **arena** -| | **insn_array** } +| | **insn_array** | **rhash** } DESCRIPTION ===========
tools/bpf/bpftool/map.c +1 -1
@@ -1478,7 +1478,7 @@ static int do_help(int argc, char **argv)" cgroup_storage | reuseport_sockarray | percpu_cgroup_storage |\n" " queue | stack | sk_storage | struct_ops | ringbuf | inode_storage |\n" " task_storage | bloom_filter | user_ringbuf | cgrp_storage | arena |\n" -" insn_array }\n" +" insn_array | rhash }\n" " " HELP_SPEC_OPTIONS " |\n" " {-f|--bpffs} | {-n|--nomount} }\n" "",
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 17/18] bpftool: Add rhash map documentation
Quoted 5 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Make bpftool documentation aware of the resizable hash map.
Signed-off-by Mykyta Yatsenko <[email protected]>
Quoted 31 lines
--- tools/bpf/bpftool/Documentation/bpftool-map.rst | 2 +- tools/bpf/bpftool/map.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-)tools/bpf/bpftool/Documentation/bpftool-map.rst +1
-1@@ -56,7 +56,7 @@ MAP COMMANDS | | **cgroup_storage** | **reuseport_sockarray** | **percpu_cgroup_storage** | | **queue** | **stack** | **sk_storage** | **struct_ops** | **ringbuf** | **inode_storage** | | **task_storage** | **bloom_filter** | **user_ringbuf** | **cgrp_storage** | **arena** -| | **insn_array** } +| | **insn_array** | **rhash** } DESCRIPTION ===========tools/bpf/bpftool/map.c +1
-1@@ -1478,7 +1478,7 @@ static int do_help(int argc, char **argv)" cgroup_storage | reuseport_sockarray | percpu_cgroup_storage |\n" " queue | stack | sk_storage | struct_ops | ringbuf | inode_storage |\n" " task_storage | bloom_filter | user_ringbuf | cgrp_storage | arena |\n" -" insn_array }\n" +" insn_array | rhash }\n" " " HELP_SPEC_OPTIONS " |\n" " {-f|--bpffs} | {-n|--nomount} }\n" "",
RFC PATCH v2 18/18 selftests/bpf: Add resizable hashmap to benchmarks
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Support resizable hashmap in BPF map benchmarks.
Results:
$ sudo ./bench -w3 -d10 -a bpf-rhashmap-full-update 0:hash_map_full_perf 21641414 events per sec
$ sudo ./bench -w3 -d10 -a bpf-hashmap-full-update 0:hash_map_full_perf 4392758 events per sec
$ sudo ./bench -w3 -d10 -a -p8 htab-mem --use-case overwrite --value-size 8 Iter 0 (302.834us): per-prod-op 62.85k/s, memory usage 2.70MiB Iter 1 (-44.810us): per-prod-op 62.81k/s, memory usage 2.70MiB Iter 2 (-45.821us): per-prod-op 62.81k/s, memory usage 2.70MiB Iter 3 (-63.658us): per-prod-op 62.92k/s, memory usage 2.70MiB Iter 4 ( 32.887us): per-prod-op 62.85k/s, memory usage 2.70MiB Iter 5 (-76.948us): per-prod-op 62.75k/s, memory usage 2.70MiB Iter 6 (157.235us): per-prod-op 63.01k/s, memory usage 2.70MiB Iter 7 (-118.761us): per-prod-op 62.85k/s, memory usage 2.70MiB Iter 8 (127.139us): per-prod-op 62.92k/s, memory usage 2.70MiB Iter 9 (-169.908us): per-prod-op 62.99k/s, memory usage 2.70MiB Iter 10 (101.962us): per-prod-op 62.97k/s, memory usage 2.70MiB Iter 11 (-64.330us): per-prod-op 63.05k/s, memory usage 2.70MiB Iter 12 (-20.543us): per-prod-op 62.86k/s, memory usage 2.70MiB Iter 13 ( 55.382us): per-prod-op 62.95k/s, memory usage 2.70MiB Summary: per-prod-op 62.92 ± 0.09k/s, memory usage 2.70 ± 0.00MiB, peak memory usage 2.96MiB
$ sudo ./bench -w3 -d10 -a -p8 rhtab-mem --use-case overwrite --value-size 8 Iter 0 (316.805us): per-prod-op 96.40k/s, memory usage 2.71MiB Iter 1 (-35.225us): per-prod-op 96.54k/s, memory usage 2.71MiB Iter 2 (-12.431us): per-prod-op 96.54k/s, memory usage 2.71MiB Iter 3 (-56.537us): per-prod-op 96.58k/s, memory usage 2.71MiB Iter 4 ( 27.108us): per-prod-op 96.62k/s, memory usage 2.71MiB Iter 5 (-52.491us): per-prod-op 96.57k/s, memory usage 2.71MiB Iter 6 ( -2.777us): per-prod-op 96.52k/s, memory usage 2.71MiB Iter 7 (108.963us): per-prod-op 96.45k/s, memory usage 2.71MiB Iter 8 (-61.575us): per-prod-op 96.48k/s, memory usage 2.71MiB Iter 9 (-21.595us): per-prod-op 96.14k/s, memory usage 2.71MiB Iter 10 ( 3.243us): per-prod-op 96.36k/s, memory usage 2.71MiB Iter 11 ( 3.102us): per-prod-op 94.70k/s, memory usage 2.71MiB Iter 12 (109.102us): per-prod-op 95.77k/s, memory usage 2.71MiB Iter 13 ( 16.153us): per-prod-op 95.91k/s, memory usage 2.71MiB Summary: per-prod-op 96.19 ± 0.57k/s, memory usage 2.71 ± 0.00MiB, peak memory usage 2.71MiB
sudo ./bench -w3 -d10 -a bpf-hashmap-lookup --key_size 4\
--max_entries 1000 --nr_entries 500 --nr_loops 1000000
cpu00: lookup 28.603M ± 0.536M events/sec (approximated from 32 samples of ~34ms)
sudo ./bench -w3 -d10 -a bpf-rhashmap-lookup --key_size 4\
--max_entries 1000 --nr_entries 500 --nr_loops 1000000
cpu00: lookup 27.340M ± 0.864M events/sec (approximated from 32 samples of ~36ms)
--- tools/testing/selftests/bpf/bench.c | 6 ++++ .../bpf/benchs/bench_bpf_hashmap_full_update.c | 34 +++++++++++++++++++-- .../bpf/benchs/bench_bpf_hashmap_lookup.c | 31 +++++++++++++++++-- .../testing/selftests/bpf/benchs/bench_htab_mem.c | 35 ++++++++++++++++++++-- 4 files changed, 100 insertions(+), 6 deletions(-)
tools/testing/selftests/bpf/bench.c +6 -0
@@ -558,13 +558,16 @@ extern const struct bench bench_bpf_loop;extern const struct bench bench_strncmp_no_helper;extern const struct bench bench_strncmp_helper;extern const struct bench bench_bpf_hashmap_full_update; +extern const struct bench bench_bpf_rhashmap_full_update;extern const struct bench bench_local_storage_cache_seq_get;extern const struct bench bench_local_storage_cache_interleaved_get;extern const struct bench bench_local_storage_cache_hashmap_control;extern const struct bench bench_local_storage_tasks_trace;extern const struct bench bench_bpf_hashmap_lookup; +extern const struct bench bench_bpf_rhashmap_lookup;extern const struct bench bench_local_storage_create;extern const struct bench bench_htab_mem; +extern const struct bench bench_rhtab_mem;extern const struct bench bench_crypto_encrypt;extern const struct bench bench_crypto_decrypt;extern const struct bench bench_sockmap;
@@ -636,13 +639,16 @@ static const struct bench *benchs[] = { &bench_strncmp_no_helper, &bench_strncmp_helper, &bench_bpf_hashmap_full_update, + &bench_bpf_rhashmap_full_update, &bench_local_storage_cache_seq_get, &bench_local_storage_cache_interleaved_get, &bench_local_storage_cache_hashmap_control, &bench_local_storage_tasks_trace, &bench_bpf_hashmap_lookup, + &bench_bpf_rhashmap_lookup, &bench_local_storage_create, &bench_htab_mem, + &bench_rhtab_mem, &bench_crypto_encrypt, &bench_crypto_decrypt, &bench_sockmap,
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_full_update.c +32 -2
@@ -34,19 +34,29 @@ static void measure(struct bench_res *res) { } -static void setup (void ) +static void hashmap_full_update_setup (enum bpf_map_type map_type) {struct bpf_link *link;int map_fd, i, max_entries;setup_libbpf (); - ctx.skel =bpf_hashmap_full_update_bench__open_and_load (); + ctx.skel =bpf_hashmap_full_update_bench__open ();if (!ctx.skel) {fprintf (stderr,"failed to open skeleton\n" );exit (1 ); } +bpf_map__set_type (ctx.skel->maps.hash_map_bench, map_type); +if (map_type ==BPF_MAP_TYPE_RHASH ) +bpf_map__set_map_flags (ctx.skel->maps.hash_map_bench, +BPF_F_NO_PREALLOC ); + +if (bpf_hashmap_full_update_bench__load (ctx.skel)) { +fprintf (stderr,"failed to load skeleton\n" ); +exit (1 ); + } + ctx.skel->bss->nr_loops =MAX_LOOP_NUM ; link =bpf_program__attach (ctx.skel->progs.benchmark);
@@ -62,6 +72,16 @@ static void setup(void)bpf_map_update_elem (map_fd, &i, &i,BPF_ANY ); } +static void setup (void ) +{ +hashmap_full_update_setup (BPF_MAP_TYPE_HASH ); +} + +static void rhash_setup (void ) +{ +hashmap_full_update_setup (BPF_MAP_TYPE_RHASH ); +} +static void hashmap_report_final (struct bench_res res[],int res_cnt) {unsigned int nr_cpus =bpf_num_possible_cpus ();
@@ -87,3 +107,13 @@ const struct bench bench_bpf_hashmap_full_update = { .report_progress = NULL, .report_final = hashmap_report_final, }; + +const struct bench bench_bpf_rhashmap_full_update = { + .name ="bpf-rhashmap-full-update" , + .validate = validate, + .setup = rhash_setup, + .producer_thread = producer, + .measure = measure, + .report_progress =NULL , + .report_final = hashmap_report_final, +};
tools/testing/selftests/bpf/benchs/bench_bpf_hashmap_lookup.c +29 -2
@@ -148,9 +148,10 @@ static inline void patch_key(u32 i, u32 *key)/* the rest of key is random */ } -static void setup (void ) +static void hashmap_lookup_setup (enum bpf_map_type map_type) {struct bpf_link *link; +__u32 map_flags;int map_fd;int ret;int i;
@@ -163,10 +164,15 @@ static void setup(void)exit (1 ); } + map_flags = args.map_flags; +if (map_type ==BPF_MAP_TYPE_RHASH ) + map_flags |=BPF_F_NO_PREALLOC ; + +bpf_map__set_type (ctx.skel->maps.hash_map_bench, map_type);bpf_map__set_max_entries (ctx.skel->maps.hash_map_bench, args.max_entries);bpf_map__set_key_size (ctx.skel->maps.hash_map_bench, args.key_size);bpf_map__set_value_size (ctx.skel->maps.hash_map_bench,8 ); -bpf_map__set_map_flags (ctx.skel->maps.hash_map_bench, args.map_flags); +bpf_map__set_map_flags (ctx.skel->maps.hash_map_bench, map_flags); ctx.skel->bss->nr_entries = args.nr_entries; ctx.skel->bss->nr_loops = args.nr_loops / args.nr_entries;
@@ -197,6 +203,16 @@ static void setup(void) } } +static void setup (void ) +{ +hashmap_lookup_setup (BPF_MAP_TYPE_HASH ); +} + +static void rhash_setup (void ) +{ +hashmap_lookup_setup (BPF_MAP_TYPE_RHASH ); +} +static inline double events_from_time (u64 time) {if (time)
@@ -275,3 +291,14 @@ const struct bench bench_bpf_hashmap_lookup = { .report_progress = NULL, .report_final = hashmap_report_final, }; + +const struct bench bench_bpf_rhashmap_lookup = { + .name ="bpf-rhashmap-lookup" , + .argp = &bench_hashmap_lookup_argp, + .validate = validate, + .setup = rhash_setup, + .producer_thread = producer, + .measure = measure, + .report_progress =NULL , + .report_final = hashmap_report_final, +};
tools/testing/selftests/bpf/benchs/bench_htab_mem.c +33 -2
@@ -152,7 +152,7 @@ static const struct htab_mem_use_case *htab_mem_find_use_case_or_exit(const charexit (1 ); } -static void htab_mem_setup (void ) +static void htab_mem_setup_impl (enum bpf_map_type map_type) {struct bpf_map *map;const char **names;
@@ -178,10 +178,11 @@ static void htab_mem_setup(void) } map = ctx.skel->maps.htab; +bpf_map__set_type (map, map_type);bpf_map__set_value_size (map, args.value_size);/* Ensure that different CPUs can operate on different subset */ bpf_map__set_max_entries (map,MAX (8192 ,64 * env.nr_cpus)); -if (args.preallocated) +if (map_type !=BPF_MAP_TYPE_RHASH && args.preallocated)bpf_map__set_map_flags (map,bpf_map__map_flags (map) & ~BPF_F_NO_PREALLOC ); names = ctx.uc->progs;
@@ -220,6 +221,16 @@ static void htab_mem_setup(void)exit (1 ); } +static void htab_mem_setup (void ) +{ +htab_mem_setup_impl (BPF_MAP_TYPE_HASH ); +} + +static void rhtab_mem_setup (void ) +{ +htab_mem_setup_impl (BPF_MAP_TYPE_RHASH ); +} +static void htab_mem_add_fn (pthread_barrier_t *notify) {while (true) {
@@ -338,6 +349,15 @@ static void htab_mem_report_final(struct bench_res res[], int res_cnt)cleanup_cgroup_environment (); } +static void rhtab_mem_validate (void ) +{ +if (args.preallocated) { +fprintf (stderr,"rhash map does not support preallocation\n" ); +exit (1 ); + } +htab_mem_validate (); +} +const struct bench bench_htab_mem = { .name ="htab-mem" , .argp = &bench_htab_mem_argp,
@@ -348,3 +368,14 @@ const struct bench bench_htab_mem = { .report_progress = htab_mem_report_progress, .report_final = htab_mem_report_final, }; + +const struct bench bench_rhtab_mem = { + .name ="rhtab-mem" , + .argp = &bench_htab_mem_argp, + .validate = rhtab_mem_validate, + .setup = rhtab_mem_setup, + .producer_thread = htab_mem_producer, + .measure = htab_mem_measure, + .report_progress = htab_mem_report_progress, + .report_final = htab_mem_report_final, +};
Signature · 1 line
2.52.0
Re: [PATCH RFC bpf-next v2 18/18] selftests/bpf: Add resizable hashmap to benchmarks
Quoted 12 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
Support resizable hashmap in BPF map benchmarks.
Results:
$ sudo ./bench -w3 -d10 -a bpf-rhashmap-full-update 0:hash_map_full_perf 21641414 events per sec$ sudo ./bench -w3 -d10 -a bpf-hashmap-full-update 0:hash_map_full_perf 4392758 events per sec
Quoted 15 lines
$ sudo ./bench -w3 -d10 -a -p8 htab-mem --use-case overwrite --value-size 8 Iter 0 (302.834us): per-prod-op 62.85k/s, memory usage 2.70MiB Iter 1 (-44.810us): per-prod-op 62.81k/s, memory usage 2.70MiB Iter 2 (-45.821us): per-prod-op 62.81k/s, memory usage 2.70MiB Iter 3 (-63.658us): per-prod-op 62.92k/s, memory usage 2.70MiB Iter 4 ( 32.887us): per-prod-op 62.85k/s, memory usage 2.70MiB Iter 5 (-76.948us): per-prod-op 62.75k/s, memory usage 2.70MiB Iter 6 (157.235us): per-prod-op 63.01k/s, memory usage 2.70MiB Iter 7 (-118.761us): per-prod-op 62.85k/s, memory usage 2.70MiB Iter 8 (127.139us): per-prod-op 62.92k/s, memory usage 2.70MiB Iter 9 (-169.908us): per-prod-op 62.99k/s, memory usage 2.70MiB Iter 10 (101.962us): per-prod-op 62.97k/s, memory usage 2.70MiB Iter 11 (-64.330us): per-prod-op 63.05k/s, memory usage 2.70MiB Iter 12 (-20.543us): per-prod-op 62.86k/s, memory usage 2.70MiB Iter 13 ( 55.382us): per-prod-op 62.95k/s, memory usage 2.70MiB
No need to list them all. 2 or 3 is enough.
Quoted 19 lines
Summary: per-prod-op 62.92 ± 0.09k/s, memory usage 2.70 ± 0.00MiB, peak memory usage 2.96MiB
$ sudo ./bench -w3 -d10 -a -p8 rhtab-mem --use-case overwrite --value-size 8 Iter 0 (316.805us): per-prod-op 96.40k/s, memory usage 2.71MiB Iter 1 (-35.225us): per-prod-op 96.54k/s, memory usage 2.71MiB Iter 2 (-12.431us): per-prod-op 96.54k/s, memory usage 2.71MiB Iter 3 (-56.537us): per-prod-op 96.58k/s, memory usage 2.71MiB Iter 4 ( 27.108us): per-prod-op 96.62k/s, memory usage 2.71MiB Iter 5 (-52.491us): per-prod-op 96.57k/s, memory usage 2.71MiB Iter 6 ( -2.777us): per-prod-op 96.52k/s, memory usage 2.71MiB Iter 7 (108.963us): per-prod-op 96.45k/s, memory usage 2.71MiB Iter 8 (-61.575us): per-prod-op 96.48k/s, memory usage 2.71MiB Iter 9 (-21.595us): per-prod-op 96.14k/s, memory usage 2.71MiB Iter 10 ( 3.243us): per-prod-op 96.36k/s, memory usage 2.71MiB Iter 11 ( 3.102us): per-prod-op 94.70k/s, memory usage 2.71MiB Iter 12 (109.102us): per-prod-op 95.77k/s, memory usage 2.71MiB Iter 13 ( 16.153us): per-prod-op 95.91k/s, memory usage 2.71MiB Summary: per-prod-op 96.19 ± 0.57k/s, memory usage 2.71 ± 0.00MiB, peak memory usage 2.71MiB
Quoted 7 lines
sudo ./bench -w3 -d10 -a bpf-hashmap-lookup --key_size 4\
--max_entries 1000 --nr_entries 500 --nr_loops 1000000
cpu00: lookup 28.603M ± 0.536M events/sec (approximated from 32 samples of ~34ms)sudo ./bench -w3 -d10 -a bpf-rhashmap-lookup --key_size 4\
--max_entries 1000 --nr_entries 500 --nr_loops 1000000
cpu00: lookup 27.340M ± 0.864M events/sec (approximated from 32 samples of ~36ms)
What about other key sizes? That would be more useful info. size 8 especially.
and different entries.
Think of holistic benchmark. Everything that one might need from a hashtable.
key_size=4, 500 entries... is ... ok. fine. but not something anyone can use to make a decision whether bpf_rhash should be used or not by a user with its own use case pattern.
Quoted 3 lines · Mykyta Yatsenko
Benchmarks and s390 tests depend on the
https://lore.kernel.org/linux-crypto/[email protected]/
Is it going into this merge window?
Please include all perf numbers right in the cover letter.
Quoted 8 lines · Alexei Starovoitov
Quoted 3 lines · Mykyta Yatsenko
Benchmarks and s390 tests depend on the
https://lore.kernel.org/linux-crypto/[email protected]/Is it going into this merge window?
It should, the patch has been applied to linux-crypto on 7-Mar. I realized it also fixes a bug only after that, so no fixes tag on the patch.
Quoted 1 line
Please include all perf numbers right in the cover letter.
Herbert Xu
maintainerQuoted 2 lines · Mykyta Yatsenko
rhashtable: Add
rhashtable_walk_enter_from()
Rhashtable walking is strongly discouraged because there is no way to provide a consistent walk on a hash table that can be resized or rehashed during the walk.
So the question is why do you need to be able to walk through the hash table, and do you need consistency guarantees such as walking through every entry once and once only?
Cheers,
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Quoted 5 lines · Herbert Xu
Quoted 2 lines · Mykyta Yatsenko
rhashtable: Add
rhashtable_walk_enter_from()
Quoted 7 lines
Rhashtable walking is strongly discouraged because there is no way to provide a consistent walk on a hash table that can be resized or rehashed during the walk.
So the question is why do you need to be able to walk through the hash table, and do you need consistency guarantees such as walking through every entry once and once only?
No need for such guarantees. It's best-effort only.
If the walk skips entries it's fine.
As long as it terminates eventually it's good.
Nothing grabs the locks, so elements are added/deleted in parallel.
Herbert Xu
maintainerQuoted 4 lines · Alexei Starovoitov
No need for such guarantees. It's best-effort only. If the walk skips entries it's fine.
As long as it terminates eventually it's good.
There is no guarantee that this walk will terminate (unless you finish it in one go). In a pathological scenario, after each walk attempt, the hash table could be rehashed such that the entry that you're resuming from gets moved back to bucket 0.
More practically, the walk is essentially useless if you encounter a rehash/resize event before calling rhashtable_walk_enter_from, because half of the hash table could be missed because the entry got moved near the end.
I think a better interface is to detect such a rehash/resize event and then fail the rhashtable_walk_enter_from call.
Cheers,
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Quoted 11 lines · Herbert Xu
Quoted 4 lines · Alexei Starovoitov
No need for such guarantees. It's best-effort only. If the walk skips entries it's fine.
As long as it terminates eventually it's good.There is no guarantee that this walk will terminate (unless you finish it in one go). In a pathological scenario, after each walk attempt, the hash table could be rehashed such that the entry that you're resuming from gets moved back to bucket 0.
Quoted 7 lines
More practically, the walk is essentially useless if you encounter a rehash/resize event before calling
rhashtable_walk_enter_from, because half of the hash table could be missed because the entry got moved near the end.I think a better interface is to detect such a rehash/resize event and then fail the
rhashtable_walk_enter_fromcall.
that's certainly a cleaner interface. the user can retry if resize occurs.
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Herbert Xu
Quoted 4 lines · Alexei Starovoitov
No need for such guarantees. It's best-effort only. If the walk skips entries it's fine.
As long as it terminates eventually it's good.There is no guarantee that this walk will terminate (unless you finish it in one go). In a pathological scenario, after each walk attempt, the hash table could be rehashed such that the entry that you're resuming from gets moved back to bucket 0.
More practically, the walk is essentially useless if you encounter a rehash/resize event before calling
rhashtable_walk_enter_from, because half of the hash table could be missed because the entry got moved near the end.
Quoted 6 lines
Quoted 2 lines
I think a better interface is to detect such a rehash/resize event and then fail the
rhashtable_walk_enter_fromcall.that's certainly a cleaner interface. the user can retry if resize occurs.
There is a problem though is the get_next_key interface:
int get_next_key(struct bpf_map *map, void *key, void *next_key)
we cant store any metadata (table address) to check if rehash took place. Am I missing any way out of it?
Quoted 27 lines · Mykyta Yatsenko
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Herbert Xu
Quoted 4 lines · Alexei Starovoitov
No need for such guarantees. It's best-effort only. If the walk skips entries it's fine.
As long as it terminates eventually it's good.There is no guarantee that this walk will terminate (unless you finish it in one go). In a pathological scenario, after each walk attempt, the hash table could be rehashed such that the entry that you're resuming from gets moved back to bucket 0.
More practically, the walk is essentially useless if you encounter a rehash/resize event before calling
rhashtable_walk_enter_from, because half of the hash table could be missed because the entry got moved near the end.Quoted 6 lines
Quoted 2 lines
I think a better interface is to detect such a rehash/resize event and then fail the
rhashtable_walk_enter_fromcall.that's certainly a cleaner interface. the user can retry if resize occurs.
Quoted 6 lines
There is a problem though is the
get_next_keyinterface:int
get_next_key(struct bpf_map *map, void *key, void *next_key)we cant store any metadata (table address) to check if rehash took place. Am I missing any way out of it?
Why store anything?rhashtable_walk_start_check() already returns -EAGAIN if resize happened. Propagate it as error from get_next_key() ?
Quoted 31 lines · Alexei Starovoitov
Quoted 29 lines · Mykyta Yatsenko
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Herbert Xu
Quoted 4 lines · Alexei Starovoitov
No need for such guarantees. It's best-effort only. If the walk skips entries it's fine.
As long as it terminates eventually it's good.There is no guarantee that this walk will terminate (unless you finish it in one go). In a pathological scenario, after each walk attempt, the hash table could be rehashed such that the entry that you're resuming from gets moved back to bucket 0.
More practically, the walk is essentially useless if you encounter a rehash/resize event before calling
rhashtable_walk_enter_from, because half of the hash table could be missed because the entry got moved near the end.Quoted 6 lines
Quoted 2 lines
I think a better interface is to detect such a rehash/resize event and then fail the
rhashtable_walk_enter_fromcall.that's certainly a cleaner interface. the user can retry if resize occurs.
There is a problem though is the
get_next_keyinterface:
Quoted 8 lines
Quoted 4 lines
int
get_next_key(struct bpf_map *map, void *key, void *next_key)we cant store any metadata (table address) to check if rehash took place. Am I missing any way out of it?
Why store anything?
rhashtable_walk_start_check()already returns-EAGAINif resize happened. Propagate it as error fromget_next_key()?
Do we care if a resize happened between two separate get_next_key()?
get_next_key(a) → b
← rehash happens here
get_next_key(b) → c
The second call has no way to know that a rehash occurred. Because each call to get_next_key() initializes/destroys a new walker and only active walker can detect rehash took place.
Herbert Xu
maintainerQuoted 4 lines · Mykyta Yatsenko
There is a problem though is the
get_next_keyinterface:int
get_next_key(struct bpf_map *map, void *key, void *next_key)
Any chance of changing the interface?
If not then perhaps a better solution is to use a linked list in conjunction with rhashtable. It'll cost a little bit of extra memory, but really provides you with the ideal solution for what you're trying to do.
Cheers,
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Quoted 6 lines · Herbert Xu
Quoted 4 lines · Mykyta Yatsenko
There is a problem though is the
get_next_keyinterface:int
get_next_key(struct bpf_map *map, void *key, void *next_key)
Quoted 8 lines
Any chance of changing the interface?
If not then perhaps a better solution is to use a linked list in conjunction with rhashtable. It'll cost a little bit of extra memory, but really provides you with the ideal solution for what you're trying to do.
Cheers,
Changing interface is practically not possible - this comes from the bpf syscall.
Linked list solution: we probably can't afford it performance-wise, it's not worth it to pay for the linked list maintenance in insert/delete operations, to make traversals work well.
Herbert Xu
maintainerQuoted 6 lines · Mykyta Yatsenko
Changing interface is practically not possible - this comes from the bpf syscall.
Linked list solution: we probably can't afford it performance-wise, it's not worth it to pay for the linked list maintenance in insert/delete operations, to make traversals work well.
What performance penalty? The linked list is just a pair of pointers.
Memory-wise it'll be two extra pointers per node.
Cheers,
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Quoted 8 lines · Herbert Xu
Quoted 6 lines · Mykyta Yatsenko
Changing interface is practically not possible - this comes from the bpf syscall.
Linked list solution: we probably can't afford it performance-wise, it's not worth it to pay for the linked list maintenance in insert/delete operations, to make traversals work well.
Quoted 5 lines
What performance penalty? The linked list is just a pair of pointers.
Memory-wise it'll be two extra pointers per node.
Cheers,
I'm concerned about pointer chasing, when we inserting a new element to the list or removing existing, we'll need to update pointers of the neighboring elements. It'll be nice to measure it, of course, let me try to prototype it.
Quoted 13 lines · Mykyta Yatsenko
Quoted 10 lines · Herbert Xu
Quoted 6 lines · Mykyta Yatsenko
Changing interface is practically not possible - this comes from the bpf syscall.
Linked list solution: we probably can't afford it performance-wise, it's not worth it to pay for the linked list maintenance in insert/delete operations, to make traversals work well.What performance penalty? The linked list is just a pair of pointers.
Quoted 8 lines
Quoted 3 lines
Memory-wise it'll be two extra pointers per node.
Cheers,
I'm concerned about pointer chasing, when we inserting a new element to the list or removing existing, we'll need to update pointers of the neighboring elements. It'll be nice to measure it, of course, let me try to prototype it.
hold on. let's not overcomplicate things.
We only need to notice that resize happened, right?
In such case just ad generation counter and let resize increment it. If it changed in our iterator -> ERESTARTSYS.
EAGAIN doesn't quite fit, since it implies that immediate operation can be retried, while here the iterator need to be destroyed and recreated.
Quoted 23 lines · Alexei Starovoitov
Quoted 13 lines · Mykyta Yatsenko
Quoted 10 lines · Herbert Xu
Quoted 6 lines · Mykyta Yatsenko
Changing interface is practically not possible - this comes from the bpf syscall.
Linked list solution: we probably can't afford it performance-wise, it's not worth it to pay for the linked list maintenance in insert/delete operations, to make traversals work well.What performance penalty? The linked list is just a pair of pointers.
Quoted 8 lines
Quoted 3 lines
Memory-wise it'll be two extra pointers per node.
Cheers,
I'm concerned about pointer chasing, when we inserting a new element to the list or removing existing, we'll need to update pointers of the neighboring elements. It'll be nice to measure it, of course, let me try to prototype it.
Quoted 6 lines
hold on. let's not overcomplicate things.
We only need to notice that resize happened, right?
In such case just ad generation counter and let resize increment it. If it changed in our iterator -> ERESTARTSYS.
EAGAIN doesn't quite fit, since it implies that immediate operation can be retried, while here the iterator need to be destroyed and recreated.
I think that won't work with get_next_key() because we don't know what generation previous key was read (in API we just get prev_key and return next key).
Quoted 34 lines · Mykyta Yatsenko
Quoted 23 lines · Alexei Starovoitov
Quoted 13 lines · Mykyta Yatsenko
Quoted 10 lines · Herbert Xu
Quoted 6 lines · Mykyta Yatsenko
Changing interface is practically not possible - this comes from the bpf syscall.
Linked list solution: we probably can't afford it performance-wise, it's not worth it to pay for the linked list maintenance in insert/delete operations, to make traversals work well.What performance penalty? The linked list is just a pair of pointers.
Quoted 8 lines
Quoted 3 lines
Memory-wise it'll be two extra pointers per node.
Cheers,
I'm concerned about pointer chasing, when we inserting a new element to the list or removing existing, we'll need to update pointers of the neighboring elements. It'll be nice to measure it, of course, let me try to prototype it.
Quoted 6 lines
hold on. let's not overcomplicate things.
We only need to notice that resize happened, right?
In such case just ad generation counter and let resize increment it. If it changed in our iterator -> ERESTARTSYS.
EAGAIN doesn't quite fit, since it implies that immediate operation can be retried, while here the iterator need to be destroyed and recreated.
Quoted 3 lines
I think that won't work with
get_next_key()because we don't know what generation previous key was read (in API we just getprev_keyand return next key).
The first one starts with key==NULL.
Quoted 36 lines · Alexei Starovoitov
Quoted 34 lines · Mykyta Yatsenko
Quoted 29 lines · Alexei Starovoitov
Quoted 13 lines · Mykyta Yatsenko
Quoted 10 lines · Herbert Xu
Quoted 6 lines · Mykyta Yatsenko
Changing interface is practically not possible - this comes from the bpf syscall.
Linked list solution: we probably can't afford it performance-wise, it's not worth it to pay for the linked list maintenance in insert/delete operations, to make traversals work well.What performance penalty? The linked list is just a pair of pointers.
Quoted 8 lines
Quoted 3 lines
Memory-wise it'll be two extra pointers per node.
Cheers,
I'm concerned about pointer chasing, when we inserting a new element to the list or removing existing, we'll need to update pointers of the neighboring elements. It'll be nice to measure it, of course, let me try to prototype it.
hold on. let's not overcomplicate things.
We only need to notice that resize happened, right?
In such case just ad generation counter and let resize increment it. If it changed in our iterator -> ERESTARTSYS.
EAGAIN doesn't quite fit, since it implies that immediate operation can be retried, while here the iterator need to be destroyed and recreated.
Quoted 5 lines
Quoted 3 lines
I think that won't work with
get_next_key()because we don't know what generation previous key was read (in API we just getprev_keyand return next key).The first one starts with key==NULL.
If we iterate entire map in one go, we can detect resize, agreed. But if user just randomly calls bpf_map_get_next_key(), we cannot really detect resizes, because we don't even know when iteration started - it may not even be an iteration, but just an odd bpf_map_get_next_key(). I think we can handle resizes next way:
- map_get_next_key(): leave as is, can't detect resize or even if
resize matters.
- map_for_each_callback(), iter_seq_info(): error out if resize takes
place mid iteration.
- batch ops: store generation counter in the bpf_attr, so on resuming,
we can detect if there was resize.
Quoted 46 lines · Mykyta Yatsenko
Quoted 36 lines · Alexei Starovoitov
Quoted 34 lines · Mykyta Yatsenko
Quoted 29 lines · Alexei Starovoitov
Quoted 13 lines · Mykyta Yatsenko
Quoted 10 lines · Herbert Xu
Quoted 6 lines · Mykyta Yatsenko
Changing interface is practically not possible - this comes from the bpf syscall.
Linked list solution: we probably can't afford it performance-wise, it's not worth it to pay for the linked list maintenance in insert/delete operations, to make traversals work well.What performance penalty? The linked list is just a pair of pointers.
Quoted 8 lines
Quoted 3 lines
Memory-wise it'll be two extra pointers per node.
Cheers,
I'm concerned about pointer chasing, when we inserting a new element to the list or removing existing, we'll need to update pointers of the neighboring elements. It'll be nice to measure it, of course, let me try to prototype it.
hold on. let's not overcomplicate things.
We only need to notice that resize happened, right?
In such case just ad generation counter and let resize increment it. If it changed in our iterator -> ERESTARTSYS.
EAGAIN doesn't quite fit, since it implies that immediate operation can be retried, while here the iterator need to be destroyed and recreated.Quoted 5 lines
Quoted 3 lines
I think that won't work with
get_next_key()because we don't know what generation previous key was read (in API we just getprev_keyand return next key).The first one starts with key==NULL.
Quoted 7 lines
If we iterate entire map in one go, we can detect resize, agreed. But if user just randomly calls
bpf_map_get_next_key(), we cannot really detect resizes, because we don't even know when iteration started - it may not even be an iteration, but just an oddbpf_map_get_next_key(). I think we can handle resizes next way:
-map_get_next_key(): leave as is, can't detect resize or even if
resize matters.
exactly. My understanding of the thread is that resize problematic only for the whole map walk, since it may keep revisiting elements potentially forever. Since get_next_key() is a loop through user space. It's not an issue.
Quoted 2 lines
-
map_for_each_callback(),iter_seq_info(): error out if resize takes
place mid iteration.
right. here it would be good to prevent looping for a long time.
Quoted 2 lines
- batch ops: store generation counter in the
bpf_attr, so on resuming,
we can detect if there was resize.
I wouldn't bother. It's the same category as get_next_key(). It loops through user space. We already have this "infinite loop" issue with this api with a normal hash map. If bpf prog deletes an unlucky 'prev' element the while(get_next_key) loop will restart from the first.