bpf: introduce timeout hash map
Subsystems (6)
v4 cover bpf: introduce timeout hash map
From: Cong Wang <[email protected]>
This patchset introduces a new eBPF hash map whose elements have timeouts. Patch 1 is the implementation of timeout map, patch 2 adds some test cases for timeout map in test_maps, and patch 3 adds a test case in map ptr test.
Please check each patch description for more details.
---
v4: merge gc_work into gc_idle_work to avoid a nasty race condition
fix a potential use-after-free
add one more test case
improve comments and update changelog
v3: move gc list from bucket to elem
reuse lru_node in struct htab_elem
drop patches which are no longer necessary
fix delete path
add a test case for delete path
add parallel test cases
change timeout to ms
drop batch ops
v2: fix hashmap ptr test
add a test case in map ptr test
factor out htab_timeout_map_alloc()
Cong Wang (3):
bpf: introduce timeout hash map selftests/bpf: add test cases for bpf timeout map selftests/bpf: add timeout map check in map_ptr tests
include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 5 +- kernel/bpf/hashtab.c | 239 +++++++++++++++++- kernel/bpf/syscall.c | 3 +- tools/include/uapi/linux/bpf.h | 1 + .../selftests/bpf/progs/map_ptr_kern.c | 20 ++ tools/testing/selftests/bpf/test_maps.c | 47 ++++ 7 files changed, 307 insertions(+), 9 deletions(-)
Signature · 1 line
2.25.1
PATCH v4 1/3 bpf: introduce timeout hash map
From: Cong Wang <[email protected]>
This borrows the idea from conntrack and will be used for conntrack in ebpf too. Each element in a timeout map has a user-specified timeout in msecs, after it expires it will be automatically removed from the map. Cilium already does the same thing, it uses a regular map or LRU map to track connections and has its own GC in user-space. This does not scale well when we have millions of connections, as each removal needs a syscall. Even if we could batch the operations, it still needs to copy a lot of data between kernel and user space.
There are two cases to consider here:
1. When the timeout map is idle, i.e. no one updates or accesses it, we rely on the delayed work to scan the whole hash table and remove these expired. The delayed work is scheduled every 1 sec when idle, which is also what conntrack uses. It is fine to scan the whole table as we do not actually remove elements during this scan, instead we simply queue them to the lockless list and defer all the removals to the next schedule.
2. When the timeout map is actively accessed, we could reach expired elements before the idle work automatically scans them, we can simply skip them and schedule the delayed work immediately to do the actual removals. We have to avoid taking locks on fast path.
The timeout of an element can be set or updated via bpf_map_update_elem() and we reuse the upper 32-bit of the 64-bit flag for the timeout value, as there are only a few bits are used currently. Note, a zero timeout means to expire immediately.
To avoid adding memory overhead to regular map, we have to reuse some field in struct htab_elem, that is, lru_node. Otherwise we would have to rewrite a lot of code.
For now, batch ops is not supported, we can add it later if needed.
--- include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 5 +- kernel/bpf/hashtab.c | 239 ++++++++++++++++++++++++++++++++- kernel/bpf/syscall.c | 3 +- tools/include/uapi/linux/bpf.h | 1 + 5 files changed, 240 insertions(+), 9 deletions(-)
include/linux/bpf_types.h +1 -0
@@ -125,6 +125,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_STACK, stack_map_ops) BPF_MAP_TYPE(BPF_MAP_TYPE_STRUCT_OPS, bpf_struct_ops_map_ops)#endif BPF_MAP_TYPE(BPF_MAP_TYPE_RINGBUF, ringbuf_map_ops) +BPF_MAP_TYPE(BPF_MAP_TYPE_TIMEOUT_HASH, htab_timeout_map_ops) BPF_LINK_TYPE(BPF_LINK_TYPE_RAW_TRACEPOINT, raw_tracepoint)BPF_LINK_TYPE (BPF_LINK_TYPE_TRACING , tracing)
include/uapi/linux/bpf.h +4 -1
@@ -164,6 +164,7 @@ enum bpf_map_type {BPF_MAP_TYPE_RINGBUF ,BPF_MAP_TYPE_INODE_STORAGE ,BPF_MAP_TYPE_TASK_STORAGE , + BPF_MAP_TYPE_TIMEOUT_HASH, };/* Note that tracing related programs such as
@@ -399,7 +400,9 @@ enum bpf_link_type {*/ #define BPF_PSEUDO_CALL 1 -/* flags for BPF_MAP_UPDATE_ELEM command */ +/* flags for BPF_MAP_UPDATE_ELEM command, upper 32 bits are timeout for +* BPF_MAP_TYPE_TIMEOUT_HASH (in milliseconds). +*/ enum {BPF_ANY =0 ,/* create new element or update existing */ BPF_NOEXIST =1 ,/* create new element if it didn't exist */
kernel/bpf/hashtab.c +232 -7
360 lines not on this page · raw message
kernel/bpf/syscall.c +2 -1
@@ -777,7 +777,8 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf, map->map_type !=BPF_MAP_TYPE_CGROUP_STORAGE && map->map_type !=BPF_MAP_TYPE_SK_STORAGE && map->map_type !=BPF_MAP_TYPE_INODE_STORAGE && - map->map_type != BPF_MAP_TYPE_TASK_STORAGE) + map->map_type !=BPF_MAP_TYPE_TASK_STORAGE && + map->map_type != BPF_MAP_TYPE_TIMEOUT_HASH) return -ENOTSUPP;if (map->spin_lock_off +sizeof (struct bpf_spin_lock ) > map->value_size) {
tools/include/uapi/linux/bpf.h +1 -0
@@ -164,6 +164,7 @@ enum bpf_map_type {BPF_MAP_TYPE_RINGBUF ,BPF_MAP_TYPE_INODE_STORAGE ,BPF_MAP_TYPE_TASK_STORAGE , + BPF_MAP_TYPE_TIMEOUT_HASH, };/* Note that tracing related programs such as
Signature · 1 line
2.25.1
Quoted 18 lines · Cong Wang
kernel/bpf/hashtab.c +18
-0+static void htab_gc (struct work_struct *work) +{ +struct htab_elem *e, *tmp; +struct llist_node *lhead; +struct bpf_htab *htab; +int i, count; + + htab = container_of(work, struct bpf_htab, gc_work.work); + lhead =llist_del_all (&htab->gc_list); + +llist_for_each_entry_safe (e, tmp, lhead, gc_node) { +unsigned long flags; +struct bucket *b; +u32 hash; + + hash = e->hash; + b =__select_bucket (htab, hash); +if (htab_lock_bucket (htab, b, hash, &flags))
kernel/bpf/hashtab.c const struct bpf_map_ops htab_of_maps_map_ops = { · line 2290
Quoted 10 lines
kernel/bpf/hashtab.c +10
-0+continue ; +hlist_nulls_del_rcu (&e->hash_node); +atomic_set (&e->pending,0 ); +free_htab_elem (htab, e); +htab_unlock_bucket (htab, b, hash, flags); + +cond_resched (); + } + +for (count =0 , i =0 ; i < htab->n_buckets; i++) {
I just realized a followup fix is not folded into this patch, I actually added a timestamp check here to avoid scanning the whole table more frequently than once per second. It is clearly my mistake to miss it when formatting this patchset.
I will send v5 after waiting for other feedback.
Thanks!
PATCH v4 2/3 selftests/bpf: add test cases for bpf timeout map
In reply to Cong WangFrom: Cong Wang <[email protected]>
Add some test cases in test_maps.c for timeout map, which focus on testing timeout.
--- tools/testing/selftests/bpf/test_maps.c | 47 +++++++++++++++++++++++++ 1 file changed, 47 insertions(+)
tools/testing/selftests/bpf/test_maps.c +47 -0
@@ -639,6 +639,52 @@ static void test_stackmap(unsigned int task, void *data)close (fd); } +static void test_timeout_map (unsigned int task,void *data) +{ +int val1 =1 , val2 =2 , val3 =3 ; +int key1 =1 , key2 =2 , key3 =3 ; +int fd; + + fd =bpf_create_map (BPF_MAP_TYPE_TIMEOUT_HASH ,sizeof (int ),sizeof (int ), +3 , map_flags); +if (fd <0 ) { +printf ("Failed to create timeout map '%s'!\n" ,strerror (errno)); +exit (1 ); + } + +/* Timeout after 1 secs */ +assert (bpf_map_update_elem (fd, &key1, &val1, (u64 )1000 <<32 ) ==0 ); +/* Timeout after 2 secs */ +assert (bpf_map_update_elem (fd, &key2, &val2, (u64 )2000 <<32 ) ==0 ); +/* Timeout after 10 secs */ +assert (bpf_map_update_elem (fd, &key3, &val3, (u64 )10000 <<32 ) ==0 ); + +sleep (1 ); +assert (bpf_map_lookup_elem (fd, &key1, &val1) !=0 ); + val2 =0 ; +assert (bpf_map_lookup_elem (fd, &key2, &val2) ==0 && val2 ==2 ); + +sleep (1 ); +assert (bpf_map_lookup_elem (fd, &key1, &val1) !=0 ); +assert (bpf_map_lookup_elem (fd, &key2, &val2) !=0 ); + +/* Modify timeout to expire it earlier */ + val3 =0 ; +assert (bpf_map_lookup_elem (fd, &key3, &val3) ==0 && val3 ==3 ); +assert (bpf_map_update_elem (fd, &key3, &val3, (u64 )1000 <<32 ) ==0 ); +sleep (1 ); +assert (bpf_map_lookup_elem (fd, &key3, &val3) !=0 ); + +/* Add one elem expired immediately and try to delete this expired */ +assert (bpf_map_update_elem (fd, &key3, &val3,0 ) ==0 ); +assert (bpf_map_delete_elem (fd, &key3) ==-1 && errno ==ENOENT ); + +/* Add one elem and let the map removal clean up */ +assert (bpf_map_update_elem (fd, &key3, &val3, (u64 )10000 <<32 ) ==0 ); + +close (fd); +} +#include <sys/ioctl.h> #include <arpa/inet.h> #include <sys/select.h>
@@ -1305,6 +1351,7 @@ static void test_map_stress(void)run_parallel (100 , test_arraymap,NULL );run_parallel (100 , test_arraymap_percpu,NULL ); +run_parallel (100 , test_timeout_map,NULL ); }#define TASKS 1024
Signature · 1 line
2.25.1
PATCH v4 3/3 selftests/bpf: add timeout map check in map_ptr tests
In reply to Cong WangFrom: Cong Wang <[email protected]>
Similar to regular hashmap test.
--- .../selftests/bpf/progs/map_ptr_kern.c | 20 +++++++++++++++++++ 1 file changed, 20 insertions(+)
tools/testing/selftests/bpf/progs/map_ptr_kern.c +20 -0
@@ -648,6 +648,25 @@ static inline int check_ringbuf(void)return 1 ; } +struct { + __uint(type, BPF_MAP_TYPE_TIMEOUT_HASH); + __uint(max_entries, MAX_ENTRIES); + __type(key, __u32); + __type(value, __u32); +} m_timeout SEC(".maps"); + +static inline int check_timeout_hash (void ) +{ +struct bpf_htab *timeout_hash = (struct bpf_htab *)&m_timeout; +struct bpf_map *map = (struct bpf_map *)&m_timeout; + +VERIFY (check_default (&timeout_hash->map, map)); +VERIFY (timeout_hash->n_buckets ==MAX_ENTRIES ); +VERIFY (timeout_hash->elem_size ==64 ); + +return 1 ; +} + SEC("cgroup_skb/egress")int cg_skb (void *ctx) {
@@ -679,6 +698,7 @@ int cg_skb(void *ctx)VERIFY_TYPE (BPF_MAP_TYPE_SK_STORAGE , check_sk_storage);VERIFY_TYPE (BPF_MAP_TYPE_DEVMAP_HASH , check_devmap_hash);VERIFY_TYPE (BPF_MAP_TYPE_RINGBUF , check_ringbuf); +VERIFY_TYPE (BPF_MAP_TYPE_TIMEOUT_HASH , check_timeout_hash);return 1 ; }
Signature · 1 line
2.25.1