Skip to contentSkip to conversation

uptr KV store

RFC PATCH Superseded Amery Hung 2 participants 8 messages Mar 20, 2025 – Mar 28, 2025

Subsystems (4)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Amery Hung

author
#0 lore raw

cover uptr KV store

Hi all,

I'd like to discuss uptr KV store in LSFMMBPF'25. This is just an RFC and the code definitely needs more work, but I hope it delivers the high level idea.

* 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 and be easily automated.

* Design & implementation *

- User space and bpf API

The uptr KV store provides basic user space and bpf API (get/put/ 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() and initializes all key-value pairs using kv_store_put(). Then, the bpf program and user space program can start using the KV store.

- Single global map lookup in KV store bpf API

Making the KV store performant enough for use in bpf programs on the hot paths is one of the design goal. 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/ put/delete only involves memory accesses in the uptr regions in the 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_idx:3;
        __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. The current implementation supports 8 pages, but this maybe chanaged if it is too big or small.

- Variable-size data copy with dynptr

get/put 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.

* Todo *

- Allocate smaller chunks of memory and grow on demand

Amery Hung (4):
bpf: Allow creating dynptr from uptr
selftests/bpf: Implement basic uptr KV store selftests/bpf: Test basic uptr KV store operations from user space and
bpf
selftests/bpf: Test changing KV store value layout

 include/uapi/linux/bpf.h                      |   4 +-
 kernel/bpf/verifier.c                         |   3 +-
 .../bpf/prog_tests/test_uptr_kv_store.c       | 154 ++++++++++
 .../selftests/bpf/prog_tests/uptr_kv_store.c  | 282 ++++++++++++++++++
 .../selftests/bpf/prog_tests/uptr_kv_store.h  |  22 ++
 .../selftests/bpf/progs/test_uptr_kv_store.c  |  46 +++
 .../bpf/progs/test_uptr_kv_store_v1.c         |  46 +++
 .../selftests/bpf/progs/uptr_kv_store.h       | 120 ++++++++
 .../selftests/bpf/test_uptr_kv_store_common.h |  22 ++
 .../selftests/bpf/uptr_kv_store_common.h      |  47 +++
 10 files changed, 744 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 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

Since this patch only allows PTR_TO_MEM without any flags, so 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 will allow creating dynptr from dynptr data. Will they create any problem?

---
 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 beac5cdf2d2c..2b1335fa1173 100644
@@ -5562,7 +5562,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 22c4edc8695c..d22310d1642c 100644
@@ -11307,7 +11307,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
#2 lore raw

Re: [RFC PATCH 1/4] bpf: Allow creating dynptr from uptr

Quoted 17 lines · Amery Hung

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

Quoted 7 lines

Since this patch only allows PTR_TO_MEM without any flags, so 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 will allow creating dynptr from dynptr data. Will they create any problem?

Yes, I think so. You need to make sure that dynptr you created from that PTR_TO_MEM is invalidated if that memory "goes away". E.g., for ringbuf case:

void *r = bpf_ringbuf_reserve(..., 100);

struct dynptr d;
bpf_dynptr_from_mem(r, 100, 0, &d);

void *p = bpf_dynptr_data(&d, 0, 100);
if (!p) return 0; /* can't happen */

bpf_ringbuf_submit(r, 0);

*(char *)p = '\0'; /* bad things happen */

Do you handle that situation? With PTR_TO_MAP_VALUE "bad things" can't happen even if value is actually deleted/reused (besides overwriting some other element's value, which we can do without dynptrs anyways), because that memory won't go away due to RCU and it doesn't contain any information important for correctness (ringbuf data area does have it).

Quoted 39 lines
---
 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 beac5cdf2d2c..2b1335fa1173 100644
@@ -5562,7 +5562,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 -2
index 22c4edc8695c..d22310d1642c 100644
@@ -11307,7 +11307,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;
--

2.47.1

author
#3 lore raw

Re: [RFC PATCH 1/4] bpf: Allow creating dynptr from uptr

Quoted 27 lines · Andrii Nakryiko
Quoted 17 lines · Amery Hung

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

Quoted 7 lines

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

The last two will allow creating dynptr from dynptr data. Will they create any problem?

Quoted 9 lines

Yes, I think so. You need to make sure that dynptr you created from that PTR_TO_MEM is invalidated if that memory "goes away". E.g., for ringbuf case:

void *r = bpf_ringbuf_reserve(..., 100);

struct dynptr d;
bpf_dynptr_from_mem(r, 100, 0, &d);

^ This will fail during verification because "r" will be PTR_TO_MEM | MEM_RINGBUF.

Only five of the listed PTR_TO_MEM cases will be allowed with this patch additionally: uptr, global subprog argument, hid_bpf_get_data, bpf_dynptr_ptr_data and bpf_dynptr_slice_rdwr. For the former three, the memory seems to be valid all the time. For the last two, IIUC, bpf_dynptr_data or bpf_dynptr_slice_rdwr should be valid if null checks pass. I am just so not sure about the nested situation (i.e., creating another dynptr from data behind a dynptr).

Thanks,
Amery

Quoted 56 lines

void *p = bpf_dynptr_data(&d, 0, 100);
if (!p) return 0; /* can't happen */

bpf_ringbuf_submit(r, 0);

*(char *)p = '\0'; /* bad things happen */

Do you handle that situation? With PTR_TO_MAP_VALUE "bad things" can't happen even if value is actually deleted/reused (besides overwriting some other element's value, which we can do without dynptrs anyways), because that memory won't go away due to RCU and it doesn't contain any information important for correctness (ringbuf data area does have it).

Quoted 39 lines
---
 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 beac5cdf2d2c..2b1335fa1173 100644
@@ -5562,7 +5562,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 -2
index 22c4edc8695c..d22310d1642c 100644
@@ -11307,7 +11307,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;
--

2.47.1

#4 lore raw

Re: [RFC PATCH 1/4] bpf: Allow creating dynptr from uptr

Quoted 34 lines · Amery Hung
Quoted 31 lines · Andrii Nakryiko
Quoted 17 lines · Amery Hung

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

Quoted 7 lines

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

The last two will allow creating dynptr from dynptr data. Will they create any problem?

Yes, I think so. You need to make sure that dynptr you created from that PTR_TO_MEM is invalidated if that memory "goes away". E.g., for ringbuf case:

Quoted 8 lines
Quoted 5 lines

void *r = bpf_ringbuf_reserve(..., 100);

struct dynptr d;
bpf_dynptr_from_mem(r, 100, 0, &d);

^ This will fail during verification because "r" will be PTR_TO_MEM | MEM_RINGBUF.

We discussed all this at LSFMMBPF2025, but for those who follow and didn't attend, we can just slightly modify the example by adding one extra bpf_dynptr_slice() constructed from r:

void *r = bpf_ringbuf_reserve(..., 100);
void *m = bpf_dynpt_slice(&r, ...);
if (!m) return 0; /* shouldn't happen */

struct dynptr d;
bpf_dynptr_from_mem(m, 100, 0, &d);

void *p = bpf_dynptr_data(&d, 0, 100);
if (!p) return 0; /* can't happen */

bpf_ringbuf_submit(r, 0);

*(char *)p = '\0'; /* bad things happen */

And we can keep building this long chain of dependencies. So we'd need to take all that into account and propagate invalidation across entire tree of dependencies between dynptrs and slices.

Quoted 68 lines

Only five of the listed PTR_TO_MEM cases will be allowed with this patch additionally: uptr, global subprog argument, hid_bpf_get_data, bpf_dynptr_ptr_data and bpf_dynptr_slice_rdwr. For the former three, the memory seems to be valid all the time. For the last two, IIUC, bpf_dynptr_data or bpf_dynptr_slice_rdwr should be valid if null checks pass. I am just so not sure about the nested situation (i.e., creating another dynptr from data behind a dynptr).

Thanks,
Amery

Quoted 56 lines

void *p = bpf_dynptr_data(&d, 0, 100);
if (!p) return 0; /* can't happen */

bpf_ringbuf_submit(r, 0);

*(char *)p = '\0'; /* bad things happen */

Do you handle that situation? With PTR_TO_MAP_VALUE "bad things" can't happen even if value is actually deleted/reused (besides overwriting some other element's value, which we can do without dynptrs anyways), because that memory won't go away due to RCU and it doesn't contain any information important for correctness (ringbuf data area does have it).

Quoted 39 lines
---
 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 beac5cdf2d2c..2b1335fa1173 100644
@@ -5562,7 +5562,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 -2
index 22c4edc8695c..d22310d1642c 100644
@@ -11307,7 +11307,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;
--

2.47.1

author
#5 lore raw

RFC PATCH 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/put/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_put(). 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 API will take the map value as the first argument, and these API do not incur 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 adding/deleting keys without moving data. The following is an example of how this would work.

user space: kv_store_init()
user space: kv_store_put({key1, key2, key3})

prog_v1: kv_store_get/put({key1, key2, key3})

user space: kv_store_delete{key1}
user space: kv_store_add{key4}
user space: kv_store_set_map_reuse(prog_v2.data_map)

prog_v2: kv_store_get/put({key2, key3, key4})

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 API may suggest higher performance overhead.

---
 .../selftests/bpf/prog_tests/uptr_kv_store.c  | 282 ++++++++++++++++++
 .../selftests/bpf/prog_tests/uptr_kv_store.h  |  22 ++
 .../selftests/bpf/progs/uptr_kv_store.h       | 120 ++++++++
 .../selftests/bpf/uptr_kv_store_common.h      |  47 +++
 4 files changed, 471 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 +282 -0
new file mode 100644
index 000000000000..18328b1d5a9a
@@ -0,0 +1,282 @@
+#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 data_map_fd;
+	int task_fd;
+	int page_cnt;
+	char *data_map_pin_path;
+	struct kv_store_data_map_value data;
+};
+
+static struct kv_store_page *__kv_store_add_page(struct kv_store *kvs)
+{
+	struct kv_store_page *p;
+
+	if (kvs->page_cnt > KVS_MAX_PAGE_ENTRIES)
+		return ERR_PTR(-ENOSPC);
+
+	p = mmap(NULL, sizeof(struct kv_store_page), PROT_READ | PROT_WRITE,
+		 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+	if (p == MAP_FAILED)
+		return ERR_PTR(-ENOMEM);
+
+	kvs->data.pages[kvs->page_cnt].page = p;
+	kvs->page_cnt++;
+
+	return p;
+}
+
+static void __kv_store_del_page(struct kv_store *kvs)
+{
+	struct kv_store_page *p;
+
+	p = kvs->data.pages[kvs->page_cnt - 1].page;
+	kvs->data.pages[kvs->page_cnt - 1].page = NULL;
+	kvs->page_cnt--;
+	munmap(p, sizeof(*p));
+}
+
+static struct kv_store_meta *kvs_store_get_meta(struct kv_store *kvs, int key)
+{
+	return key < KVS_MAX_VAL_ENTRIES ? &kvs->data.metas->meta[key] : NULL;
+}
+
+void kv_store_close(struct kv_store *kvs)
+{
+	int i;
+
+	munmap(kvs->data.metas, sizeof(struct kv_store_metas));
+
+	for (i = 0; i < kvs->page_cnt; i++)
+		__kv_store_del_page(kvs);
+
+	if (kvs->data_map_pin_path)
+		unlink(kvs->data_map_pin_path);
+
+	free(kvs);
+}
+
+struct kv_store *kv_store_init(int pid, struct bpf_map *data_map, const char *pin_path)
+{
+	struct kv_store_page *p;
+	struct kv_store *kvs;
+	int err;
+
+	kvs = calloc(1, sizeof(*kvs));
+	if (!kvs) {
+		errno = -ENOMEM;
+		return NULL;
+	}
+
+	kvs->data.metas = mmap(NULL, sizeof(struct kv_store_page),
+			       PROT_READ | PROT_WRITE,
+			       MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+	if (kvs->data.metas == MAP_FAILED) {
+		errno = -ENOMEM;
+		return NULL;
+	}
+
+	p = __kv_store_add_page(kvs);
+	if (IS_ERR(p)) {
+		errno = PTR_ERR(p);
+		goto err;
+	}
+
+	kvs->data_map_fd = bpf_map__fd(data_map);
+	if (!kvs->data_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->data_map_fd, &kvs->task_fd, &kvs->data, 0);
+	if (err) {
+		errno = err;
+		goto err;
+	}
+
+	kvs->data_map_pin_path = strdup(pin_path);
+	if (!kvs->data_map_pin_path)
+		goto err;
+
+	err = bpf_map__pin(data_map, kvs->data_map_pin_path);
+	if (err) {
+		errno = err;
+		goto err;
+	}
+
+	return kvs;
+err:
+	kv_store_close(kvs);
+	return NULL;
+}
+
+int kv_store_data_map_set_reuse(struct kv_store *kvs, struct bpf_map *data_map)
+{
+	return bpf_map__reuse_fd(data_map, kvs->data_map_fd);
+}
+
+void *kv_store_get(struct kv_store *kvs, int key)
+{
+	struct kv_store_meta *meta;
+	struct kv_store_page *p;
+
+	meta = kvs_store_get_meta(kvs, key);
+	if (!meta || !meta->init)
+		return NULL;
+
+	p = kvs->data.pages[meta->page_idx].page;
+
+	return p->data + meta->page_off;
+}
+
+static int linear_off(const struct kv_store_meta *meta)
+{
+	if (!meta->init)
+		return KVS_MAX_PAGE_ENTRIES * KVS_MAX_VAL_SIZE;
+
+	return meta->page_idx * KVS_MAX_VAL_SIZE + meta->page_off;
+}
+
+static int comp_meta(const void *m1, const void *m2)
+{
+	struct kv_store_meta *meta1 = (struct kv_store_meta *)m1;
+	struct kv_store_meta *meta2 = (struct kv_store_meta *)m2;
+	int off1, off2;
+
+	off1 = linear_off(meta1);
+	off2 = linear_off(meta2);
+
+	if (off1 > off2)
+		return 1;
+	else if (off1 < off2)
+		return -1;
+	else
+		return 0;
+}
+
+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, next_off = 0;
+	struct kv_store_page *p;
+
+	memcpy(metas, kvs->data.metas, sizeof(struct kv_store_meta) * KVS_MAX_VAL_ENTRIES);
+
+	qsort(metas, KVS_MAX_VAL_ENTRIES, sizeof(struct kv_store_meta), comp_meta);
+
+	for (i = 0; i < KVS_MAX_VAL_ENTRIES; i++) {
+		off = linear_off(&metas[i]);
+		if (off - next_off >= size &&
+		    next_off / PAGE_SIZE == (next_off + size - 1) / PAGE_SIZE) {
+			break;
+		}
+		next_off = off + metas[i].size;
+	}
+
+	meta->page_idx = next_off / PAGE_SIZE;
+	meta->page_off = next_off % PAGE_SIZE;
+	meta->size = size;
+
+	if (meta->page_idx >= kvs->page_cnt) {
+		p = __kv_store_add_page(kvs);
+		if (!p)
+			return -ENOMEM;
+
+		err = bpf_map_update_elem(kvs->data_map_fd, &kvs->task_fd, &kvs->data, 0);
+		if (err) {
+			__kv_store_del_page(kvs);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+int kv_store_put(struct kv_store *kvs, int key, void *val, unsigned int val_size)
+{
+	struct kv_store_meta *meta;
+	struct kv_store_page *p;
+	int err;
+
+	meta = kvs_store_get_meta(kvs, key);
+	if (!meta)
+		return -ENOENT;
+
+	if (!meta->init) {
+		if (val_size > KVS_MAX_VAL_SIZE)
+			return -E2BIG;
+
+		err = kv_store_find_next_slot(kvs, val_size, meta);
+		if (err)
+			return err;
+	}
+
+	p = kvs->data.pages[meta->page_idx].page;
+	val_size = val_size < meta->size ? val_size : meta->size;
+	memcpy((char *)p->data + meta->page_off, val, val_size);
+	meta->init = 1;
+	return 0;
+}
+
+void kv_store_delete(struct kv_store *kvs, int key)
+{
+	struct kv_store_meta *meta;
+	struct kv_store_page *p;
+
+	meta = kvs_store_get_meta(kvs, key);
+	if (!meta)
+		return;
+
+	p = kvs->data.pages[meta->page_idx].page;
+	memset(p->data + meta->page_off, 0, meta->size);
+	memset(meta, 0, sizeof(*meta));
+}
+
+int kv_store_update_value_size(struct kv_store *kvs, int key, unsigned int val_size)
+{
+	struct kv_store_meta *meta, new_meta;
+	struct kv_store_page *old_p, *new_p;
+	int err;
+
+	if (val_size > KVS_MAX_VAL_SIZE)
+		return -E2BIG;
+
+	meta = kvs_store_get_meta(kvs, key);
+	if (!meta || !meta->init)
+		return -ENOENT;
+
+	if (val_size <= meta->size) {
+		meta->size = val_size;
+		return 0;
+	}
+
+	err = kv_store_find_next_slot(kvs, val_size, &new_meta);
+	if (err)
+		return -ENOSPC;
+
+	old_p = kvs->data.pages[meta->page_idx].page;
+	new_p = kvs->data.pages[new_meta.page_idx].page;
+
+	memcpy(new_p->data + new_meta.page_off,
+	       old_p->data + meta->page_off, meta->size);
+
+	return 0;
+}
tools/testing/selftests/bpf/prog_tests/uptr_kv_store.h new file +22 -0
new file mode 100644
index 000000000000..a1da3e6e2de3
@@ -0,0 +1,22 @@
+#ifndef _UPTR_KV_STORE_H
+#define _UPTR_KV_STORE_H
+
+#include "uptr_kv_store_common.h"
+
+struct kv_store;
+
+void kv_store_close(struct kv_store *kvs);
+
+struct kv_store *kv_store_init(int pid, struct bpf_map *data_map, const char *pin_path);
+
+int kv_store_data_map_set_reuse(struct kv_store *kvs, struct bpf_map *data_map);
+
+void *kv_store_get(struct kv_store *kvs, int key);
+
+int kv_store_put(struct kv_store *kvs, int key, void *val, unsigned int val_size);
+
+void kv_store_delete(struct kv_store *kvs, int key);
+
+int kv_store_update_value_size(struct kv_store *kvs, int key, unsigned int val_size);
+
+#endif
tools/testing/selftests/bpf/progs/uptr_kv_store.h new file +120 -0

120 lines not on this page · raw message

tools/testing/selftests/bpf/uptr_kv_store_common.h new file +47 -0

47 lines not on this page · raw message

Signature · 1 line
2.47.1
author
#6 lore raw

RFC PATCH 3/4 selftests/bpf: Test basic uptr KV store operations 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 put the value as the key. In the second loop, for each key, a bpf program is triggered to get the value, and then put a new value. In the final loop, we get the value again in the user space and make sure they are the new value.

---
 .../bpf/prog_tests/test_uptr_kv_store.c       | 77 +++++++++++++++++++
 .../selftests/bpf/progs/test_uptr_kv_store.c  | 37 +++++++++
 .../selftests/bpf/test_uptr_kv_store_common.h |  9 +++
 3 files changed, 123 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 +77 -0
new file mode 100644
index 000000000000..2075b8e47972
@@ -0,0 +1,77 @@
+#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, int_val, *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");
+	if (!ASSERT_OK_PTR(kvs, "kv_store_init"))
+		return;
+
+	max_int_entries = KVS_MAX_VAL_ENTRIES;
+
+	err = kv_store_update_value_size(kvs, 0, KVS_MAX_VAL_SIZE);
+	ASSERT_ERR(err, "kv_store_update_value_size");
+
+	err = kv_store_put(kvs, 0, &int_val, KVS_MAX_VAL_SIZE + 1);
+	ASSERT_ERR(err, "kv_store_put");
+
+	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 int_val"))
+			goto out;
+
+		err = kv_store_put(kvs, i, &i, sizeof(i));
+		if (!ASSERT_OK(err, "kv_store_put int_val"))
+			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: check int_val[i] = i");
+
+		skel->bss->test_int_val += 1;
+		skel->bss->test_op = KVS_INT_PUT;
+		sys_gettid();
+	}
+	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 int_val"))
+			goto out;
+
+		ASSERT_EQ(*int_val_p, i + 1, "user space: check int_val[i] == i + 1");
+	}
+
+	err = kv_store_put(kvs, max_int_entries, &int_val, sizeof(int));
+	ASSERT_EQ(err, -ENOENT, "kv_store_put int_val");
+
+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..b358cb7fb616
@@ -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_PUT:
+		kv_store_put(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..ff7d010ed08f
@@ -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_PUT,
+};
+
+#endif
Signature · 1 line
2.47.1
author
#7 lore raw

RFC PATCH 4/4 selftests/bpf: Test changing KV store value layout

In reply to Amery Hung

While it is not the most ideal way I imagine how the KV store to be used. The test tries to show upgrading a bpf program with a change in the definition of a structure. If using a structure for the value, while adding a new member is easy, it is less clear how removing or changing member layout would work.

---
 .../bpf/prog_tests/test_uptr_kv_store.c       | 77 +++++++++++++++++++
 .../selftests/bpf/progs/test_uptr_kv_store.c  |  9 +++
 .../bpf/progs/test_uptr_kv_store_v1.c         | 46 +++++++++++
 .../selftests/bpf/test_uptr_kv_store_common.h | 13 ++++
 4 files changed, 145 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 +77 -0
index 2075b8e47972..2e86bb08b26e 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)
 {
@@ -70,8 +71,84 @@ static void test_uptr_kv_store_basic(void)
 	kv_store_close(kvs);
 }
 
+static void test_uptr_kv_store_change_value(void)
+{
+	int err, pid;
+	struct test_uptr_kv_store_v1 *skel_v1;
+	struct test_uptr_kv_store *skel;
+	struct test_struct_v1 val_v1;
+	struct test_struct val, *val_p;
+	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;
+
+	pid = sys_gettid();
+	kvs = kv_store_init(pid, skel->maps.data_map, "/sys/fs/bpf/kv_store_data_map");
+
+	/* update key 0 to test_struct in user space */
+	val.a = 1;
+	val.b = 2;
+	err = kv_store_put(kvs, 0, &val, sizeof(val));
+	ASSERT_OK(err, "kv_store_put struct val");
+	val_p = kv_store_get(kvs, 0);
+	ASSERT_OK_PTR(val_p, "kv_store_get struct val");
+	ASSERT_EQ(val_p->a, val.a, "user space: check get val.a == put val.a");
+	ASSERT_EQ(val_p->b, val.b, "user space: check get val.b == put val.b");
+
+	/* lookup test_struct at key 0 in test_uptr_kv_store */
+	skel->bss->test_key = 0;
+	skel->bss->test_op = KVS_STRUCT_GET;
+	skel->bss->target_pid = pid;
+	sys_gettid();
+	skel->bss->target_pid = -1;
+	ASSERT_EQ(skel->bss->test_struct_val.a, val.a, "bpf: check get val.a == put val.a");
+	ASSERT_EQ(skel->bss->test_struct_val.b, val.b, "bpf: check get val.b == put val.b");
+
+	/* add a new field to test_struct */
+	err = kv_store_update_value_size(kvs, 0, sizeof(val_v1));
+	ASSERT_OK(err, "kv_store_update_value_size");
+
+	/* rollout a new version */
+	skel_v1 = test_uptr_kv_store_v1__open();
+	if (!ASSERT_OK_PTR(skel, "skel_open v1"))
+		goto out;
+
+	kv_store_data_map_set_reuse(kvs, skel_v1->maps.data_map);
+
+	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;
+
+	/* lookup struct_key_0 in test_uptr_kv_store */
+	skel_v1->bss->test_key = 0;
+	skel_v1->bss->test_op = KVS_STRUCT_GET;
+	skel_v1->bss->target_pid = pid;
+	sys_gettid();
+	skel_v1->bss->target_pid = -1;
+
+	ASSERT_EQ(skel_v1->bss->test_struct_val.a, val.a, "bpf: check get val_v1.a == put val.a");
+	ASSERT_EQ(skel_v1->bss->test_struct_val.b, val.b, "bpf: check get val_v1.b == put val.b");
+
+out:
+	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_change_value"))
+		test_uptr_kv_store_change_value();
 }
tools/testing/selftests/bpf/progs/test_uptr_kv_store.c +9 -0
index b358cb7fb616..2ed993ab4b01 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,14 @@ int on_enter(__u64 *ctx)
 	case KVS_INT_GET:
 		kv_store_get(data, test_key, &test_int_val, 4);
 		break;
+	case KVS_STRUCT_PUT:
+		kv_store_put(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 +46 -0

46 lines not on this page · raw message

tools/testing/selftests/bpf/test_uptr_kv_store_common.h +13 -0
index ff7d010ed08f..db91e862789f 100644
@@ -4,6 +4,19 @@
 enum test_kvs_op {
 	KVS_INT_GET,
 	KVS_INT_PUT,
+	KVS_STRUCT_GET,
+	KVS_STRUCT_PUT,
+};
+
+struct test_struct {
+	int a;
+	int b;
+};
+
+struct test_struct_v1 {
+	int a;
+	int b;
+	int c;
 };
 
 #endif
Signature · 1 line
2.47.1