bpf: introduce timeout map
Subsystems (6)
v3 cover bpf: introduce timeout map
From: Cong Wang <[email protected]>
This patchset introduces a new bpf hash map which has timeout. 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.
---
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 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 | 252 +++++++++++++++++- 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 | 46 ++++ 7 files changed, 319 insertions(+), 9 deletions(-)
Signature · 1 line
2.25.1
PATCH v3 1/3 bpf: introduce timeout 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 idle work to scan the whole hash table and remove these expired. The idle work is scheduled every 1 sec, which is also what conntrack uses.
2. When the timeout map is actively accessed, we could reach expired elements before the idle work kicks in, we can simply skip them and schedule another work to do the actual removal work. Thusly we avoid taking locks on fast path.
The timeout of each 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. For now, batch ops is not supported, we can add it later iff needed.
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.
--- include/linux/bpf_types.h | 1 + include/uapi/linux/bpf.h | 5 +- kernel/bpf/hashtab.c | 252 ++++++++++++++++++++++++++++++++- kernel/bpf/syscall.c | 3 +- tools/include/uapi/linux/bpf.h | 1 + 5 files changed, 253 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
@@ -158,6 +158,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
@@ -393,7 +394,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 +245 -7
373 lines not on this page · raw message
kernel/bpf/syscall.c +2 -1
@@ -778,7 +778,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
@@ -158,6 +158,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
PATCH v3 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 | 46 +++++++++++++++++++++++++ 1 file changed, 46 insertions(+)
tools/testing/selftests/bpf/test_maps.c +46 -0
@@ -639,6 +639,49 @@ 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 ); + +close (fd); +} +#include <sys/ioctl.h> #include <arpa/inet.h> #include <sys/select.h>
@@ -1305,6 +1348,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
@@ -1752,6 +1796,8 @@ static void run_all_tests(void)test_stackmap (0 ,NULL );test_map_in_map (); + +test_timeout_map (0 ,NULL ); }#define DEFINE_TEST (name) extern void test_##name(void);
Signature · 1 line
2.25.1
PATCH v3 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