Skip to contentSkip to conversation

uptr KV store

RFC PATCH In review Amery Hung 2 participants 6 messages Apr 4, 2025

Subsystems (4)
lore
Share & tools
lore

Amery Hung

author
#0 lore raw

v2 cover uptr KV store

* Overview *

The uptr KV store implements a key-value store based on existing bpf features with one small change to the bpf verifier code. A motivation of this work is to make rolling out a new bpf program with changes to map value layouts easier. Currently, there is not a simple and easy way to do it. One may try to create a new map that has the new map value layout, copy old values into the new one, and then starts the new program. However, this process is not trivial to automate. uptr KV store provides an alternative to this. By replacing a structure in a map with the use of KV store with multiple key-value pairs, changing map layout becomes just adding/deleting key-value pairs. In addition, by maintaining a manifest of key-value pairs, the roll out process can be more easily automated.

* Design & implementation *

- User space and bpf API

The uptr KV store provides basic user space and bpf APIs (get/set/ delete). In addition, there are APIs for managing space that are only provided to the user space. It is assume that all keys are known before deploying a bpf program. To use it, the user space program first needs to initialize the KV store by calling kv_store_init() with a list of key-value pairs, or initializes all key-value pairs using kv_store_set(). Then, the bpf program and user space program can start using the KV store. When rolling out a new bpf program, user space program can update the KV store with the updated list of key-value pairs by calling kv_store_update(). It will delete keys no longer exist, set new keys and update values. The example can be found in patch 4.

- Single global map lookup in KV store bpf API

A use case of the KV store is to store per-task attributes (e.g., an experiment flag, the priority of the task, etc.). While the KV store is not intended to be used as part of the data path, making it performant is a design goal so that it can be use in bpf programs sitting in some relatively hot paths. To achieve this, a key is to keep map lookups as little as possible. The current implementation only requires one task local storage lookup during one program invocation. Then, get/set/delete only involves memory accesses in the uptr regions in the task local storage.

The uptr KV store mainly consists of two uptr regions, metadata and data. The metadata is an array of metadata indexed by key, where each metadata contains the page index and page offset and the size of the key-value pair. The data region are pages allocated on-demand for storing values, and one page is allocated initially.

If using string key is desired, the metadata can be moved to a bpf hashmap indexed with string keys. However, this will add one hashmap lookup to every basic KV store operation.

- 1K max int keys; 1B - 4KB value

The KV store is indexed by integer keys and the maximum number of keys supported is 1K. This is limited by the maximum number of metadata as shown below that can be stored in a 4KB uptr metadata array. The largest size of a value is also bound to 4KB for the same reason.

  struct kv_store_meta {
        __u32 page_off:12;
        __u32 size:12;
        __u32 init:1;
  }

- Growable storage backed by uptr

To be able to accommodate future storage space needed for new key-value pairs or temporarily storing old and new key-value pairs at the same time during transition, the KV store is growable. This is possible as the KV store leverages uptr, which can be allocated in user space on demand.

- Variable-size data copy with dynptr

get/set involves copying variable-size data between uptr region and stack. Since llvm does not support emitting bytecode for memcpy with variable size, byte-by-byte copy in a for loop needs to be used. This can be improved by using dynptr. Please refer to the patch 1 for details.

Changelog:
v1 -> v2
- Miscellaneous bug fixes
- Fix workarounds in bpf APIs
- Reduce 8 x 4K data pages to just one to save lookup time
- Only use dynptr for reading/writing value size other than 1, 4, 8
- Introduce kv_pairs, a list of key-value pairs, for initializing and updating kv_store
- Allocate just enough memory for metadata/data if kv_pairs is provided. Otherwise, create a 16-key, 256-byte value storage kv_store
- Change the second example to show how to manage kv_store from the user space

Amery Hung (4):
bpf: Allow creating dynptr from uptr
selftests/bpf: Implement basic uptr KV store selftests/bpf: Test basic uptr KV store APIs from user space and bpf selftests/bpf: Test updating KV store layout when rolling out new prog

 include/uapi/linux/bpf.h                      |   4 +-
 kernel/bpf/verifier.c                         |   3 +-
 .../bpf/prog_tests/test_uptr_kv_store.c       | 259 ++++++++++++++
 .../selftests/bpf/prog_tests/uptr_kv_store.c  | 329 ++++++++++++++++++
 .../selftests/bpf/prog_tests/uptr_kv_store.h  | 103 ++++++
 .../selftests/bpf/progs/test_uptr_kv_store.c  |  44 +++
 .../bpf/progs/test_uptr_kv_store_v1.c         |  44 +++
 .../selftests/bpf/progs/uptr_kv_store.h       | 127 +++++++
 .../selftests/bpf/test_uptr_kv_store_common.h |  22 ++
 .../selftests/bpf/uptr_kv_store_common.h      |  37 ++
 10 files changed, 970 insertions(+), 2 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/test_uptr_kv_store.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/uptr_kv_store.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/uptr_kv_store.h
 create mode 100644 tools/testing/selftests/bpf/progs/test_uptr_kv_store.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_uptr_kv_store_v1.c
 create mode 100644 tools/testing/selftests/bpf/progs/uptr_kv_store.h
 create mode 100644 tools/testing/selftests/bpf/test_uptr_kv_store_common.h
 create mode 100644 tools/testing/selftests/bpf/uptr_kv_store_common.h
Signature · 1 line
2.47.1
author
#1 lore raw

RFC PATCH v2 1/4 bpf: Allow creating dynptr from uptr

Currently, bpf_dynptr_from_mem() only allows creating dynptr from local memory of reg type PTR_TO_MAP_VALUE, specifically ringbuf. This patch futher supports PTR_TO_MEM as a valid source of data.

For a reg to be PTR_TO_MEM in the verifier:
- read map value with special field BPF_UPTR
- ld_imm64 kfunc (MEM_RDONLY)
- ld_imm64 other non-struct ksyms (MEM_RDONLY)
- return from helper with RET_PTR_TO_MEM: ringbuf_reserve (MEM_RINGBUF) and dynptr_from_data
- return from helper with RET_PTR_TO_MEM_OR_BTF_ID: this_cpu_ptr, per_cpu_ptr and the return type is not struct (both MEM_RDONLY)
- return from special kfunc: dynptr_slice (MEM_RDONLY), dynptr_slice_rdwr
- return from non-special kfunc that returns non-struct pointer:
hid_bpf_get_data
- global subprogram argument

Since this patch only allows PTR_TO_MEM without any flags, only uptr, global subprog argument, non-special kfunc that returns non-struct ptr, return of bpf_dynptr_slice_rdwr() and bpf_dynptr_data() will be allowed additionally.

The last two cases will allow creating dynptr from dynptr data. More plumbing in the verifier needs to be done before this patch to make sure the source dynptr is valid when creating a dynptr from it.

---
 include/uapi/linux/bpf.h | 4 +++-
 kernel/bpf/verifier.c    | 3 ++-
 2 files changed, 5 insertions(+), 2 deletions(-)
include/uapi/linux/bpf.h +3 -1
index 661de2444965..12d916664b1d 100644
@@ -5566,7 +5566,9 @@ union bpf_attr {
  *	Description
  *		Get a dynptr to local memory *data*.
  *
- *		*data* must be a ptr to a map value.
+ *		*data* must be a ptr to valid local memory such as a map value, a uptr,
+ *		a null-checked non-void pointer pass to a global subprogram, and allocated
+ *		memory returned by a kfunc such as hid_bpf_get_data(),
  *		The maximum *size* supported is DYNPTR_MAX_SIZE.
  *		*flags* is currently unused.
  *	Return
kernel/bpf/verifier.c +2 -1
index 8ad7338e726b..d1e1841f632b 100644
@@ -11378,7 +11378,8 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 		}
 		break;
 	case BPF_FUNC_dynptr_from_mem:
-		if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
+		if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE &&
+		    regs[BPF_REG_1].type != PTR_TO_MEM) {
 			verbose(env, "Unsupported reg type %s for bpf_dynptr_from_mem data\n",
 				reg_type_str(env, regs[BPF_REG_1].type));
 			return -EACCES;
Signature · 1 line
2.47.1
author
#2 lore raw

RFC PATCH v2 2/4 selftests/bpf: Implement basic uptr KV store

In reply to Amery Hung

The uptr KV store is a dynamically resizable key-value store that aims to make rolling out bpf programs with map value layout changes easier by hiding the layout from bpf program. It is built on top of existing bpf features with both user space and bpf API. To support usage in bpf programs on hot paths, only simple APIs such as get/set/delete are provided in bpf, and space managing API are available in user space API.

To use uptr KV store, the user space program first needs to call kv_store_init() to allocate memory and setup uptrs in the task_local_storage of a given process. It will return a pointer to "struct kv_store" on success, which will be used as a token to access the KV store in other APIs. Secondly, it needs to initialize all key-value pairs with kv_store_set(). Then, both bpf and user space program can start their normal operation.

In the bpf program, the API is designed to minimize map lookups. Therefore, the bpf program needs to first lookup the task_local_storage. Then, all bpf APIs will take the map value as the first argument, and these APIs do not need additional map lookups.

A simple way of using KV store to allow easy bpf program rollout is to use multiple key-value pairs where the values are primitive datatypes instead of a structure. This way, adding/deleting fields are just setting/deleting key-value pairs. The user will not need to worry about how to copy old map data into a new map with different layout. A more detailed example can be found in patch 4.

At the core of the KV store are metadata and data. To access the value stored in the data, the metadata is first queried using an integer key. The metadata is an array of metadata containing the offset and size of the values. Both metadata and data are stored in uptr regions in the task_local_storage.

Note that, it is also possible to support string keys by replacing the backing storage of metadata with an hashmap. However, the additional map lookup per get/set/delete will incur higher performance overhead.

---
 .../selftests/bpf/prog_tests/uptr_kv_store.c  | 329 ++++++++++++++++++
 .../selftests/bpf/prog_tests/uptr_kv_store.h  | 103 ++++++
 .../selftests/bpf/progs/uptr_kv_store.h       | 127 +++++++
 .../selftests/bpf/uptr_kv_store_common.h      |  37 ++
 4 files changed, 596 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/uptr_kv_store.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/uptr_kv_store.h
 create mode 100644 tools/testing/selftests/bpf/progs/uptr_kv_store.h
 create mode 100644 tools/testing/selftests/bpf/uptr_kv_store_common.h
tools/testing/selftests/bpf/prog_tests/uptr_kv_store.c new file +329 -0
new file mode 100644
index 000000000000..53b38ffacd93
@@ -0,0 +1,329 @@
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <sys/mman.h>
+#include <linux/err.h>
+#include <bpf/bpf.h>
+#include <bpf/libbpf.h>
+
+#include "task_local_storage_helpers.h"
+#include "uptr_kv_store.h"
+
+struct kv_store {
+	int map_fd;
+	int task_fd;
+	char *map_pin_path;
+	struct kv_store_data_map_value map_val;
+};
+
+static struct kv_store_meta *kvs_store_get_meta(struct kv_store *kvs, int key)
+{
+	return key < kvs->map_val.metas_cnt ? &kvs->map_val.metas->meta[key] : NULL;
+}
+
+static int kv_store_grow_metas(struct kv_store *kvs, int new_metas_cnt)
+{
+	int err, metas_cnt;
+	void *new_metas;
+
+	new_metas = mremap(kvs->map_val.metas,
+			   sizeof(struct kv_store_meta) * kvs->map_val.metas_cnt,
+			   sizeof(struct kv_store_meta) * new_metas_cnt, 0);
+
+	if (new_metas == MAP_FAILED || new_metas != kvs->map_val.metas)
+		return -EFAULT;
+
+	metas_cnt = kvs->map_val.metas_cnt;
+	kvs->map_val.metas_cnt = new_metas_cnt;
+	err = bpf_map_update_elem(kvs->map_fd, &kvs->task_fd, &kvs->map_val, 0);
+	if (err) {
+		kvs->map_val.metas_cnt = metas_cnt;
+		return err;
+	}
+	return 0;
+}
+
+static int kv_store_grow_page(struct kv_store *kvs, int new_page_size)
+{
+	int err, page_size;
+	void *new_page;
+
+	new_page = mremap(kvs->map_val.page, kvs->map_val.page_size,
+			  new_page_size, 0);
+
+	if (new_page == MAP_FAILED || new_page != kvs->map_val.page)
+		return -EFAULT;
+
+	page_size = kvs->map_val.page_size;
+	kvs->map_val.page_size = new_page_size;
+	err = bpf_map_update_elem(kvs->map_fd, &kvs->task_fd, &kvs->map_val, 0);
+	if (err) {
+		kvs->map_val.page_size = page_size;
+		return err;
+	}
+	return 0;
+}
+
+void kv_store_close(struct kv_store *kvs)
+{
+	munmap(kvs->map_val.metas, sizeof(struct kv_store_meta) * kvs->map_val.metas_cnt);
+	munmap(kvs->map_val.page, kvs->map_val.page_size);
+
+	if (kvs->map_pin_path)
+		unlink(kvs->map_pin_path);
+
+	free(kvs);
+}
+
+struct kv_store *kv_store_init(int pid, struct bpf_map *data_map, const char *pin_path,
+			       struct kv_pairs *kvp)
+{
+	struct kv_store *kvs;
+	int i, err;
+	size_t metas_cnt = 0, data_size = 0;
+
+	kvs = calloc(1, sizeof(*kvs));
+	if (!kvs) {
+		errno = -ENOMEM;
+		return NULL;
+	}
+
+	if (kvp) {
+		for (i = 0; i < kvp->array_cnt; i++) {
+			if (kvp->array[i].size > KVS_MAX_VAL_SIZE ||
+			    kvp->array[i].size + data_size > PAGE_SIZE)
+				continue;
+			metas_cnt = metas_cnt > kvp->array[i].key ? metas_cnt : kvp->array[i].key + 1;
+			data_size += kvp->array[i].size;
+		}
+	} else {
+		metas_cnt = 16;
+		data_size = 256;
+	}
+
+	kvs->map_val.metas_cnt = metas_cnt;
+	kvs->map_val.metas = mmap(NULL, metas_cnt * sizeof(struct kv_store_meta),
+				  PROT_READ | PROT_WRITE,
+				  MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+	if (kvs->map_val.metas == MAP_FAILED) {
+		errno = -ENOMEM;
+		return NULL;
+	}
+
+	kvs->map_val.page_size = data_size;
+	kvs->map_val.page = mmap(NULL, data_size,
+				 PROT_READ | PROT_WRITE,
+				 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+	if (kvs->map_val.page == MAP_FAILED) {
+		munmap(kvs->map_val.metas, sizeof(struct kv_store_metas));
+		errno = -ENOMEM;
+		goto err;
+	}
+
+	kvs->map_fd = bpf_map__fd(data_map);
+	if (!kvs->map_fd) {
+		errno = -ENOENT;
+		goto err;
+	}
+
+	kvs->task_fd = sys_pidfd_open(pid, 0);
+	if (!kvs->task_fd) {
+		errno = -ESRCH;
+		goto err;
+	}
+
+	err = bpf_map_update_elem(kvs->map_fd, &kvs->task_fd, &kvs->map_val, 0);
+	if (err) {
+		errno = err;
+		goto err;
+	}
+
+	kvs->map_pin_path = strdup(pin_path);
+	if (!kvs->map_pin_path)
+		goto err;
+
+	err = bpf_map__pin(data_map, kvs->map_pin_path);
+	if (err) {
+		errno = err;
+		goto err;
+	}
+
+	if (kvp) {
+		data_size = 0;
+		for (i = 0; i < kvp->array_cnt; i++) {
+			struct kv_store_meta *meta;
+
+			meta = &kvs->map_val.metas->meta[kvp->array[i].key];
+
+			if (kvp->array[i].size > KVS_MAX_VAL_SIZE ||
+			    kvp->array[i].size + data_size > PAGE_SIZE)
+				continue;
+
+			if (kvp->array[i].val) {
+				memcpy(kvs->map_val.page->data + data_size,
+				       kvp->array[i].val,
+				       kvp->array[i].size);
+			}
+
+			meta->page_off = data_size;
+			meta->size = kvp->array[i].size;
+			meta->init = 1;
+
+			data_size += kvp->array[i].size;
+		}
+	}
+
+	return kvs;
+err:
+	kv_store_close(kvs);
+	return NULL;
+}
+
+int kv_store_reuse(struct kv_store *kvs, struct bpf_map *data_map)
+{
+	return bpf_map__reuse_fd(data_map, kvs->map_fd);
+}
+
+static int comp_kv_pair(const void *kv1, const void *kv2)
+{
+	return ((const struct kv_pair *)kv1)->key -
+	       ((const struct kv_pair *)kv2)->key;
+}
+
+int __kv_store_set(struct kv_store *kvs, int key, void *val, unsigned int val_size);
+
+void kv_store_update(struct kv_store *kvs, struct kv_pairs *kvp)
+{
+	int i = 0, j = 0;
+
+	qsort(kvp->array, kvp->array_cnt, sizeof(struct kv_pair), comp_kv_pair);
+
+	/* for key = [0, max kvp key], delete unused key-value pairs and add new ones */
+	while (j < kvp->array_cnt) {
+		if (i < kvp->array[j].key) {
+			if (kvs->map_val.metas->meta[i].init)
+				kv_store_delete(kvs, i);
+			i++;
+			continue;
+		}
+
+		if (kvs->map_val.metas->meta[i].init &&
+		    kvs->map_val.metas->meta[i].size != kvp->array[j].size)
+			kv_store_delete(kvs, i);
+
+		if (kvs->map_val.metas->meta[i].size != kvp->array[j].size ||
+		    kvp->array[j].val)
+			__kv_store_set(kvs, kvp->array[j].key, kvp->array[j].val,
+				       kvp->array[j].size);
+		i++;
+		j++;
+	}
+	/* for key = [max kvp key + 1, max kvs key], delete unused key-value pairs */
+	for (; i < kvs->map_val.metas_cnt; i++)
+		if (kvs->map_val.metas->meta[i].init)
+			kv_store_delete(kvs, i);
+}
+
+void *kv_store_get(struct kv_store *kvs, int key)
+{
+	struct kv_store_meta *meta;
+
+	meta = kvs_store_get_meta(kvs, key);
+	if (!meta || !meta->init)
+		return NULL;
+
+	return kvs->map_val.page->data + meta->page_off;
+}
+
+static int comp_meta(const void *m1, const void *m2)
+{
+	const struct kv_store_meta *meta1 = (const struct kv_store_meta *)m1;
+	const struct kv_store_meta *meta2 = (const struct kv_store_meta *)m2;
+
+	return (meta1->page_off + meta1->init ? 0 : PAGE_SIZE) -
+	       (meta2->page_off + meta2->init ? 0 : PAGE_SIZE);
+}
+
+static int kv_store_find_next_slot(struct kv_store *kvs, int size, struct kv_store_meta *meta)
+{
+	struct kv_store_meta metas[KVS_MAX_VAL_ENTRIES];
+	int i, err, off = 0;
+
+	if (size > KVS_MAX_VAL_SIZE)
+		return -E2BIG;
+
+	memcpy(metas, kvs->map_val.metas, sizeof(struct kv_store_meta) * kvs->map_val.metas_cnt);
+
+	qsort(metas, kvs->map_val.metas_cnt, sizeof(struct kv_store_meta), comp_meta);
+
+	for (i = 0; i < kvs->map_val.metas_cnt; i++) {
+		if (metas[i].page_off - off >= size || !metas[i].init)
+			break;
+		off = metas[i].page_off + metas[i].size;
+	}
+
+	if (size + off > PAGE_SIZE)
+		return -ENOSPC;
+
+	if (size + off > kvs->map_val.page_size) {
+		err = kv_store_grow_page(kvs, size + off);
+		if (err)
+			return err;
+	}
+
+	meta->page_off = off;
+	meta->size = size;
+	return 0;
+}
+
+int __kv_store_set(struct kv_store *kvs, int key, void *val, unsigned int val_size)
+{
+	struct kv_store_meta *meta;
+	int err;
+
+	if (key >= kvs->map_val.metas_cnt && key < KVS_MAX_VAL_ENTRIES) {
+		err = kv_store_grow_metas(kvs, key + 1);
+		if (err)
+			return err;
+	}
+
+	meta = kvs_store_get_meta(kvs, key);
+	if (!meta)
+		return -ENOENT;
+
+	if (!meta->init) {
+		err = kv_store_find_next_slot(kvs, val_size, meta);
+		if (err)
+			return err;
+	}
+
+	val_size = val_size < meta->size ? val_size : meta->size;
+	if (val)
+		memcpy(kvs->map_val.page->data + meta->page_off, val, val_size);
+	else
+		memset(kvs->map_val.page->data + meta->page_off, 0, val_size);
+
+	meta->init = 1;
+	return 0;
+}
+
+int kv_store_set(struct kv_store *kvs, int key, void *val, unsigned int val_size)
+{
+	if (!val)
+		return -EINVAL;
+
+	return __kv_store_set(kvs, key, val, val_size);
+}
+
+void kv_store_delete(struct kv_store *kvs, int key)
+{
+	struct kv_store_meta *meta;
+
+	meta = kvs_store_get_meta(kvs, key);
+	if (!meta)
+		return;
+
+	memset(kvs->map_val.page->data + meta->page_off, 0, meta->size);
+	memset(meta, 0, sizeof(*meta));
+}
tools/testing/selftests/bpf/prog_tests/uptr_kv_store.h new file +103 -0

103 lines not on this page · raw message

tools/testing/selftests/bpf/progs/uptr_kv_store.h new file +127 -0

127 lines not on this page · raw message

tools/testing/selftests/bpf/uptr_kv_store_common.h new file +37 -0
new file mode 100644
index 000000000000..2f1f04e523d4
@@ -0,0 +1,37 @@
+#ifndef _UPTR_KV_STORE_COMMON_H
+#define _UPTR_KV_STORE_COMMON_H
+
+#define PAGE_SIZE		4096
+#define KVS_MAX_VAL_SIZE	PAGE_SIZE
+#define KVS_MAX_VAL_ENTRIES	1024
+
+#ifdef __BPF__
+struct kv_store_page *dummy_page;
+struct kv_store_metas *dummy_metas;
+#else
+#define __uptr
+#define __kptr
+#endif
+
+struct kv_store_meta {
+	__u32 page_off:12;
+	__u32 size:12;
+	__u32 init:1;
+};
+
+struct kv_store_metas {
+	struct kv_store_meta meta[KVS_MAX_VAL_ENTRIES];
+};
+
+struct kv_store_data_map_value {
+	struct kv_store_metas __uptr *metas;
+	struct kv_store_page __uptr *page;
+	u16 metas_cnt;
+	u16 page_size;
+};
+
+struct kv_store_page {
+	char data[KVS_MAX_VAL_SIZE];
+};
+
+#endif
Signature · 1 line
2.47.1
author
#3 lore raw

RFC PATCH v2 3/4 selftests/bpf: Test basic uptr KV store APIs from user space and bpf

In reply to Amery Hung

Make sure both user space and bpf programs can correctly manipulate the KV store. In the first loop, for each key, we first try to get the value, this should fail as it is not yet initialized. Then, we set the value as the key. In the second loop, for each key, a bpf program is triggered to get the value, and then set a new value. In the final loop, we get the value again in the user space and make sure they are the updated value.

---
 .../bpf/prog_tests/test_uptr_kv_store.c       | 75 +++++++++++++++++++
 .../selftests/bpf/progs/test_uptr_kv_store.c  | 37 +++++++++
 .../selftests/bpf/test_uptr_kv_store_common.h |  9 +++
 3 files changed, 121 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/test_uptr_kv_store.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_uptr_kv_store.c
 create mode 100644 tools/testing/selftests/bpf/test_uptr_kv_store_common.h
tools/testing/selftests/bpf/prog_tests/test_uptr_kv_store.c new file +75 -0
new file mode 100644
index 000000000000..c61b44ba8639
@@ -0,0 +1,75 @@
+#include <test_progs.h>
+
+#include "uptr_kv_store.h"
+#include "test_uptr_kv_store_common.h"
+#include "test_uptr_kv_store.skel.h"
+
+static void test_uptr_kv_store_basic(void)
+{
+	int err, i, pid, zero = 0, *int_val_p, max_int_entries;
+	struct test_uptr_kv_store *skel;
+	struct kv_store *kvs = NULL;
+
+	skel = test_uptr_kv_store__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "skel_open_and_load"))
+		return;
+
+	skel->bss->target_pid = -1;
+	err = test_uptr_kv_store__attach(skel);
+	if (!ASSERT_OK(err, "skel_attach"))
+		return;
+
+	kvs = kv_store_init(getpid(), skel->maps.data_map, "/sys/fs/bpf/kv_store_data_map", NULL);
+	if (!ASSERT_OK_PTR(kvs, "kv_store_init"))
+		return;
+
+	max_int_entries = KVS_MAX_VAL_ENTRIES;
+
+	err = kv_store_set(kvs, 0, &zero, KVS_MAX_VAL_SIZE + 1);
+	ASSERT_EQ(err, -E2BIG, "kv_store_set(kvs, 0, &zero, 4097)");
+
+	err = kv_store_set(kvs, max_int_entries, &zero, sizeof(int));
+	ASSERT_EQ(err, -ENOENT, "kv_store_set(kvs, 1024, &zero, 4)");
+
+	for (i = 0; i < max_int_entries; i++) {
+		int_val_p = kv_store_get(kvs, i);
+		if (!ASSERT_ERR_PTR(int_val_p, "kv_store_get(kvs, i)"))
+			goto out;
+
+		err = kv_store_set(kvs, i, &i, sizeof(i));
+		if (!ASSERT_OK(err, "kv_store_set(kvs, i)"))
+			goto out;
+	}
+
+	pid = sys_gettid();
+	skel->bss->target_pid = pid;
+	for (i = 0; i < max_int_entries; i++) {
+		skel->bss->test_key = i;
+		skel->bss->test_op = KVS_INT_GET;
+		sys_gettid();
+		ASSERT_EQ(skel->bss->test_int_val, i, "bpf:value[i]");
+
+		skel->bss->test_int_val += 1;
+		skel->bss->test_op = KVS_INT_SET;
+		sys_gettid();
+		skel->bss->test_int_val = 0;
+	}
+	skel->bss->target_pid = -1;
+
+	for (i = 0; i < max_int_entries; i++) {
+		int_val_p = kv_store_get(kvs, i);
+		if (!ASSERT_OK_PTR(int_val_p, "kv_store_get(kvs, i)"))
+			goto out;
+
+		ASSERT_EQ(*int_val_p, i + 1, "userspace:value[i]");
+	}
+
+out:
+	kv_store_close(kvs);
+}
+
+void test_uptr_kv_store(void)
+{
+	if (test__start_subtest("uptr_kv_store_basic"))
+		test_uptr_kv_store_basic();
+}
tools/testing/selftests/bpf/progs/test_uptr_kv_store.c new file +37 -0
new file mode 100644
index 000000000000..bc58269b1ab2
@@ -0,0 +1,37 @@
+#include <vmlinux.h>
+#include <bpf/bpf_helpers.h>
+
+#include "uptr_kv_store.h"
+#include "test_uptr_kv_store_common.h"
+
+pid_t target_pid = 0;
+int test_op;
+int test_key;
+int test_int_val;
+
+SEC("tp_btf/sys_enter")
+int on_enter(__u64 *ctx)
+{
+	struct kv_store_data_map_value *data;
+	struct task_struct *task;
+
+	task = bpf_get_current_task_btf();
+	if (task->pid != target_pid)
+		return 0;
+
+	data = bpf_task_storage_get(&data_map, task, 0, 0);
+
+	switch (test_op) {
+	case KVS_INT_SET:
+		kv_store_set(data, test_key, &test_int_val, 4);
+		break;
+	case KVS_INT_GET:
+		kv_store_get(data, test_key, &test_int_val, 4);
+		break;
+	}
+
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";
+
tools/testing/selftests/bpf/test_uptr_kv_store_common.h new file +9 -0
new file mode 100644
index 000000000000..056d744c5d74
@@ -0,0 +1,9 @@
+#ifndef _TEST_UPTR_KV_STORE_COMMON_H
+#define _TEST_UPTR_KV_STORE_COMMON_H
+
+enum test_kvs_op {
+	KVS_INT_GET,
+	KVS_INT_SET,
+};
+
+#endif
Signature · 1 line
2.47.1
author
#4 lore raw

RFC PATCH v2 4/4 selftests/bpf: Test updating KV store layout when rolling out new prog

In reply to Amery Hung

This example shows how user space manages a KV store by maintain a manifest of key-value pairs. The user space program should know all key- value pairs used in the bpf program before attaching the program and keeps them in a struct kv_pairs. Inside kv_pairs::array, each element is a struct kv_pair. It comprises the key, the size of the value and optionally the initial value.

When first creating a kv_store object, kv_pairs can be used to initialized its content via kv_store_init(). If not provided, a 16-key, 256-byte value storage KV store will be created and the user space program will use kv_store_set() to initialize it.

When rolling out a new bpf program, the user space program will need to tell libbpf to reuse the task local storage map used to back the KV store by calling kv_store_reuse(). Then, it will update the kv_pairs and call kv_store_update() to update the KV store. Keys no longer exist in kv_pairs will be deleted. Keys that exists but whose value sizes change will also be deleted, and then a new key-value pair associated with the same key will be created. Finally, new key-value pairs are added. When updating key-value pairs, if kv_pair::val is not NULL, the value will be set to the value provided. Otherwise, the value will be zero initialized if the key-value pair is newly added, or it will remain what it is if the key-value pair already exists.

---
 .../bpf/prog_tests/test_uptr_kv_store.c       | 184 ++++++++++++++++++
 .../selftests/bpf/progs/test_uptr_kv_store.c  |   7 +
 .../bpf/progs/test_uptr_kv_store_v1.c         |  44 +++++
 .../selftests/bpf/test_uptr_kv_store_common.h |  13 ++
 4 files changed, 248 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/test_uptr_kv_store_v1.c
tools/testing/selftests/bpf/prog_tests/test_uptr_kv_store.c +184 -0
index c61b44ba8639..42c7000de14e 100644
@@ -3,6 +3,7 @@
 #include "uptr_kv_store.h"
 #include "test_uptr_kv_store_common.h"
 #include "test_uptr_kv_store.skel.h"
+#include "test_uptr_kv_store_v1.skel.h"
 
 static void test_uptr_kv_store_basic(void)
 {
@@ -68,8 +69,191 @@ static void test_uptr_kv_store_basic(void)
 	kv_store_close(kvs);
 }
 
+static void test_uptr_kv_store_update(void)
+{
+	struct test_struct val2 = {.a = 1, .b = 2};
+	struct kv_pair kvp_array[5] = {
+		{.key = 0, .val = NULL, .size = sizeof(int)},
+		{.key = 1, .val = NULL, .size = sizeof(int)},
+		{.key = 2, .val = &val2, .size = sizeof(struct test_struct)},
+		{.key = 3, .val = NULL, .size = sizeof(struct test_struct)},
+		{.key = 4, .val = NULL, .size = sizeof(int)},
+	};
+	struct test_struct_v1 val2_v1 = {.a = 3, .b = 4, .c = 5};
+	int val4 = 1234;
+	struct kv_pair kvp_array_v1[5] = {
+		{.key = 0, .val = NULL, .size = sizeof(int)},
+		{.key = 2, .val = &val2_v1, .size = sizeof(struct test_struct_v1)},
+		{.key = 4, .val = &val4, .size = sizeof(int)},
+		{.key = 6, .val = NULL, .size = sizeof(struct test_struct_v1)},
+		{.key = 8, .val = NULL, .size = sizeof(int)},
+	};
+	struct test_uptr_kv_store_v1 *skel_v1;
+	struct test_uptr_kv_store *skel;
+	struct kv_pairs *kvp, *kvp_v1;
+	struct kv_store *kvs = NULL;
+	int err, pid, val;
+	void *val_p;
+
+	kvp = malloc(sizeof(struct kv_pairs) + sizeof(struct kv_pair) * 5);
+	if (!ASSERT_OK_PTR(kvp, "malloc kvp"))
+		goto out;
+	kvp->array_cnt = 5;
+	memcpy(&kvp->array, &kvp_array, sizeof(struct kv_pair) * 5);
+
+	kvp_v1 = malloc(sizeof(struct kv_pairs) + sizeof(struct kv_pair) * 5);
+	if (!ASSERT_OK_PTR(kvp_v1, "malloc kvp_v1"))
+		goto out;
+	kvp_v1->array_cnt = 5;
+	memcpy(&kvp_v1->array, &kvp_array_v1, sizeof(struct kv_pair) * 5);
+
+	/* Rollout the initial version */
+	skel = test_uptr_kv_store__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "skel_open_and_load"))
+		return;
+
+	pid = sys_gettid();
+	kvs = kv_store_init(pid, skel->maps.data_map, "/sys/fs/bpf/kv_store_data_map", kvp);
+	if (!ASSERT_OK_PTR(kvs, "kv_store_init"))
+		goto out;
+
+	skel->bss->target_pid = -1;
+	err = test_uptr_kv_store__attach(skel);
+	if (!ASSERT_OK(err, "skel_attach"))
+		return;
+
+	/* Check if the KV store is initialized correctly */
+	val_p = kv_store_get(kvs, 0);
+	if (!ASSERT_OK_PTR(val_p, "kv_store_get(kvs, 0)"))
+		goto out;
+	ASSERT_EQ(*(int *)val_p, 0, "value[0]");
+
+	val_p = kv_store_get(kvs, 1);
+	if (!ASSERT_OK_PTR(val_p, "kv_store_get(kvs, 1)"))
+		goto out;
+	ASSERT_EQ(*(int *)val_p, 0, "value[1]");
+
+	val_p = kv_store_get(kvs, 2);
+	if (!ASSERT_OK_PTR(val_p, "kv_store_get(kvs, 2)"))
+		goto out;
+	ASSERT_EQ(((struct test_struct *)val_p)->a, 1, "value[2].a");
+	ASSERT_EQ(((struct test_struct *)val_p)->b, 2, "value[2].b");
+
+	val_p = kv_store_get(kvs, 3);
+	if (!ASSERT_OK_PTR(val_p, "kv_store_get(kvs, 3)"))
+		goto out;
+	ASSERT_EQ(*(int *)val_p, 0, "value[3]");
+
+	val_p = kv_store_get(kvs, 4);
+	if (!ASSERT_OK_PTR(val_p, "kv_store_get(kvs, 4)"))
+		goto out;
+	ASSERT_EQ(*(int *)val_p, 0, "value[4] = 0");
+
+	/* Make sure bpf prog see the same thing */
+	skel->bss->target_pid = pid;
+	skel->bss->test_key = 2;
+	skel->bss->test_op = KVS_STRUCT_GET;
+	sys_gettid();
+	ASSERT_EQ(skel->bss->test_struct_val.a, 1, "bpf:value[2].a");
+	ASSERT_EQ(skel->bss->test_struct_val.b, 2, "bpf:value[2].b");
+	skel->bss->target_pid = -1;
+
+	/* Change some key-value pairs */
+	val = 1;
+	kv_store_set(kvs, 0, &val, sizeof(val));
+
+	/* Reuse the KV store and rollout v1 program */
+	skel_v1 = test_uptr_kv_store_v1__open();
+	if (!ASSERT_OK_PTR(skel, "skel_open v1"))
+		goto out;
+
+	kv_store_reuse(kvs, skel_v1->maps.data_map);
+
+	kv_store_update(kvs, kvp_v1);
+
+	err = test_uptr_kv_store_v1__load(skel_v1);
+	if (!ASSERT_OK(err, "skel_load v1"))
+		goto out;
+
+	skel_v1->bss->target_pid = -1;
+	err = test_uptr_kv_store_v1__attach(skel_v1);
+	if (!ASSERT_OK(err, "skel_attach v1"))
+		goto out;
+
+	/* Check if the KV store is updated correctly */
+	/* value[0] already exists and should not be zero initialized again */
+	val_p = kv_store_get(kvs, 0);
+	if (!ASSERT_OK_PTR(val_p, "kv_store_get(kvs, 0)"))
+		goto out;
+	ASSERT_EQ(*(int *)val_p, 1, "value[0]");
+
+	/* value[1] was deleted */
+	val_p = kv_store_get(kvs, 1);
+	ASSERT_ERR_PTR(val_p, "kv_store_get(kvs, 1)");
+
+	/* value[2] was deleted and a new value[2] of a different type was set */
+	val_p = kv_store_get(kvs, 2);
+	if (!ASSERT_OK_PTR(val_p, "kv_store_get(kvs, 2)"))
+		goto out;
+	ASSERT_EQ(((struct test_struct_v1 *)val_p)->a, 3, "value[2].a");
+	ASSERT_EQ(((struct test_struct_v1 *)val_p)->b, 4, "value[2].b");
+	ASSERT_EQ(((struct test_struct_v1 *)val_p)->c, 5, "value[2].c");
+
+	/* value[3] was be deleted */
+	val_p = kv_store_get(kvs, 3);
+	ASSERT_ERR_PTR(val_p, "kv_store_get(kvs, 3)");
+
+	/* value[4] was updated to a new integer value */
+	val_p = kv_store_get(kvs, 4);
+	if (!ASSERT_OK_PTR(val_p, "kv_store_get(kvs, 4)"))
+		goto out;
+	ASSERT_EQ(*(int *)val_p, 1234, "value[4]");
+
+	/* value[5] was never set */
+	val_p = kv_store_get(kvs, 5);
+	ASSERT_ERR_PTR(val_p, "kv_store_get(kvs, 5)");
+
+	/* value[6] of struct test_struct_v1 type was newly set */
+	val_p = kv_store_get(kvs, 6);
+	if (!ASSERT_OK_PTR(val_p, "kv_store_get(kvs, 6)"))
+		goto out;
+	ASSERT_EQ(((struct test_struct_v1 *)val_p)->a, 0, "value[6].a");
+	ASSERT_EQ(((struct test_struct_v1 *)val_p)->b, 0, "value[6].b");
+	ASSERT_EQ(((struct test_struct_v1 *)val_p)->c, 0, "value[6].c");
+
+	/* value[7] was never set */
+	val_p = kv_store_get(kvs, 7);
+	ASSERT_ERR_PTR(val_p, "kv_store_get(kvs, 7)");
+
+	/* value[8] of int type was newly set */
+	val_p = kv_store_get(kvs, 8);
+	if (!ASSERT_OK_PTR(val_p, "kv_store_get(kvs, 8)"))
+		goto out;
+	ASSERT_EQ(*(int *)val_p, 0, "value[8]");
+
+	/* Make sure bpf prog see the same thing */
+	skel_v1->bss->target_pid = pid;
+	skel_v1->bss->test_key = 2;
+	skel_v1->bss->test_op = KVS_STRUCT_GET;
+	sys_gettid();
+	ASSERT_EQ(skel_v1->bss->test_struct_val.a, 3, "bpf:value[2].a");
+	ASSERT_EQ(skel_v1->bss->test_struct_val.b, 4, "bpf:value[2].b");
+	ASSERT_EQ(skel_v1->bss->test_struct_val.c, 5, "bpf:value[2].c");
+	skel_v1->bss->target_pid = -1;
+
+out:
+	if (kvp)
+		free(kvp);
+	if (kvp_v1)
+		free(kvp_v1);
+	if (kvs)
+		kv_store_close(kvs);
+}
+
 void test_uptr_kv_store(void)
 {
 	if (test__start_subtest("uptr_kv_store_basic"))
 		test_uptr_kv_store_basic();
+	if (test__start_subtest("uptr_kv_store_update"))
+		test_uptr_kv_store_update();
 }
tools/testing/selftests/bpf/progs/test_uptr_kv_store.c +7 -0
index bc58269b1ab2..763a71722152 100644
@@ -8,6 +8,7 @@ pid_t target_pid = 0;
 int test_op;
 int test_key;
 int test_int_val;
+struct test_struct test_struct_val;
 
 SEC("tp_btf/sys_enter")
 int on_enter(__u64 *ctx)
@@ -28,6 +29,12 @@ int on_enter(__u64 *ctx)
 	case KVS_INT_GET:
 		kv_store_get(data, test_key, &test_int_val, 4);
 		break;
+	case KVS_STRUCT_SET:
+		kv_store_set(data, test_key, &test_struct_val, sizeof(test_struct_val));
+		break;
+	case KVS_STRUCT_GET:
+		kv_store_get(data, test_key, &test_struct_val, sizeof(test_struct_val));
+		break;
 	}
 
 	return 0;
tools/testing/selftests/bpf/progs/test_uptr_kv_store_v1.c new file +44 -0

44 lines not on this page · raw message

tools/testing/selftests/bpf/test_uptr_kv_store_common.h +13 -0
index 056d744c5d74..fa8e77d6ad9a 100644
@@ -4,6 +4,19 @@
 enum test_kvs_op {
 	KVS_INT_GET,
 	KVS_INT_SET,
+	KVS_STRUCT_GET,
+	KVS_STRUCT_SET,
+};
+
+struct test_struct {
+	int a;
+	int b;
+};
+
+struct test_struct_v1 {
+	int a;
+	int b;
+	int c;
 };
 
 #endif
Signature · 1 line
2.47.1
#5 lore raw
In reply to Amery Hung
Quoted 14 lines · Amery Hung

Changelog:
v1 -> v2
- Miscellaneous bug fixes
- Fix workarounds in bpf APIs
- Reduce 8 x 4K data pages to just one to save lookup time
- Only use dynptr for reading/writing value size other than 1, 4, 8
- Introduce kv_pairs, a list of key-value pairs, for initializing and updating kv_store
- Allocate just enough memory for metadata/data if kv_pairs is provided. Otherwise, create a 16-key, 256-byte value storage kv_store
- Change the second example to show how to manage kv_store from the user space

Hmm.
As we discussed at lsfmm the patch 1 is still wrong.

The rest is imo no go. If sched-ext people want to kill their performance this way it's their call. I still think it's a wrong path to take.

Quoted 2 lines

make rolling out a new bpf program with changes to map value layouts easier

That was brought up at lsfmm as well.
The approach doesn't actually do what it claims.

The idea of patch 1 is salvagable with extra work on the verifier side. The rest is not.