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
--
2.47.1
