Skip to contentSkip to conversation

bpf: introduce timeout hash map

PATCH Superseded Cong Wang 1 participant 5 messages Jan 17, 2021 – Jan 18, 2021

Subsystems (6)

v4 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Cong Wang

author
#0 lore raw

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

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.

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           | 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
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 c001766adcbc..9c9d8c194b39 100644
@@ -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
index c3bb03c8371f..2df15535895a 100644
@@ -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
index c001766adcbc..ac6ddfd7bddc 100644
@@ -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
author
#2 lore raw
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!

author
#3 lore raw

PATCH v4 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 | 47 +++++++++++++++++++++++++
 1 file changed, 47 insertions(+)
tools/testing/selftests/bpf/test_maps.c +47 -0
index 51adc42b2b40..5e443d76512b 100644
@@ -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
author
#4 lore raw

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