Skip to contentSkip to conversation

bpf: introduce timeout map

PATCH Superseded Cong Wang 1 participant 4 messages Dec 22, 2020

Subsystems (6)

v3 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Cong Wang

author
#0 lore raw

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
author
#1 lore raw

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.

Cc Andrii Nakryiko <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Daniel Borkmann <[email protected]>
Cc Dongdong Wang <[email protected]>
---
 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
index 99f7fd657d87..00a3b17b6af2 100644
@@ -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
index 77d7c1bb2923..88507e6aaddd 100644
@@ -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
index 287be337d5f6..9ebd2e380a57 100644
@@ -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
index 77d7c1bb2923..29f5d0b5147a 100644
@@ -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
author
#2 lore raw

PATCH v3 2/3 selftests/bpf: add test cases for bpf timeout map

In reply to Cong Wang

From: Cong Wang <[email protected]>

Add some test cases in test_maps.c for timeout map, which focus on testing timeout.

Cc Alexei Starovoitov <[email protected]>
Cc Daniel Borkmann <[email protected]>
Cc Dongdong Wang <[email protected]>
---
 tools/testing/selftests/bpf/test_maps.c | 46 +++++++++++++++++++++++++
 1 file changed, 46 insertions(+)
tools/testing/selftests/bpf/test_maps.c +46 -0
index 0ad3e6305ff0..19c7c0f64a5d 100644
@@ -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
author
#3 lore raw

PATCH v3 3/3 selftests/bpf: add timeout map check in map_ptr tests

In reply to Cong Wang

From: Cong Wang <[email protected]>

Similar to regular hashmap test.

Cc Alexei Starovoitov <[email protected]>
Cc Daniel Borkmann <[email protected]>
Cc Dongdong Wang <[email protected]>
---
 .../selftests/bpf/progs/map_ptr_kern.c        | 20 +++++++++++++++++++
 1 file changed, 20 insertions(+)
tools/testing/selftests/bpf/progs/map_ptr_kern.c +20 -0
index d8850bc6a9f1..424a9e76c93f 100644
@@ -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