Skip to content

RFC KHO map

Pratyush Yadav kexec linux-doc linux-kselftest linux-mm lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest5 patches 8 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/5kho: add KHOSER_CLEAR_PTR()include/linux/kho/abi/kexec_handover.h+5 -00 replies
2/5kho: build KHO objects into a single kho.okernel/liveupdate/Makefile+8 -42 replies
3/5kho: add KHO mapDocumentation/core-api/kho/abi.rst Documentation/core-api/kho/index.rst include/linux/kho/abi/map.h +3 more+704 -10 replies
4/5kho: test: add KHO map testlib/Kconfig.debug lib/Makefile lib/test_kho_map.c +1 more+582 -10 replies
5/5mm/memfd_luo: use KHO map for tracking foliosinclude/linux/kho/abi/memfd.h mm/memfd_luo.c+151 -1800 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [RFC PATCH 0/5] KHO map

From: "Pratyush Yadav (Google)" <[email protected]>

Hi,

This series introduces the KHO map. It is a sparse map from integer keys to u64 values. It is implemented as a radix tree of fixed depth. Currently the tree depth is 6, so it can support keys up to 54 bits wide.

The main user of the map is memfd. Currently memfd uses a vmalloc buffer that has a pair of {index,pfn} to track the folios in the file. That uses 16 bytes per page. The KHO map uses only 8 bytes per page with some overhead. So for a 1 GiB memfd, it uses roughly half the memory.

In addition, it is a more versatile data structure. For example, it allows for adding or removing pages from a memfd after preserve more efficiently than the vmalloc array.

Post-LPC 2026, the plan is for KHO to maintain backwards compatibility as much as possible. So this data structure allows the serialization format to be more flexible to future changes. It can also be used by the upcoming HugeTLB and guest_memfd preservation.

I have talked about this as "KHO xarray" before, but I think using "xarray" is just going to confuse everyone since it isn't really a xarray, and the API works a fair bit differently. So I renamed it to "KHO map".

This series isn't complete yet, but it is in fairly good shape so I want to share it to get some early feedback.

Things that are missing and planned in the future:

- Multi-index entry support: currently, while the map is very efficient with 4k folios, it is horribly inefficient with 2M folios. Each folio in the memfd takes up a full page to track. Multi-index entry support can fix this by tracking entries that cover a whole page in the previous level, similar to page tables.

- LUO versioning support: LUO versioning headers are still in discussion. This data structure should use them for future extensibility. I am mainly waiting for things to settle down there.

- Dynamic depth support: Currently the depth is static, so it can only support keys up to 54 bits wide. Adding support for multiple depth levels based on what the caller needs can improve efficiency and flexibility. I likely will only add support for this in the ABI and leave the actual implementation for later when we have a real use case.

This series is based on a couple of memfd patches I sent earlier [0][1].

[0] https://lore.kernel.org/kexec/[email protected]/
[1] https://lore.kernel.org/kexec/[email protected]/

Regards,
Pratyush Yadav

Pratyush Yadav (Google) (5):
kho: add KHOSER_CLEAR_PTR()
kho: build KHO objects into a single kho.o
kho: add KHO map
kho: test: add KHO map test
mm/memfd_luo: use KHO map for tracking folios

 Documentation/core-api/kho/abi.rst     |   5 +
 Documentation/core-api/kho/index.rst   |  12 +
 include/linux/kho/abi/kexec_handover.h |   5 +
 include/linux/kho/abi/map.h            |  94 ++++
 include/linux/kho/abi/memfd.h          |  39 +-
 include/linux/kho_map.h                |  77 ++++
 kernel/liveupdate/Makefile             |  13 +-
 kernel/liveupdate/kho_map.c            | 514 ++++++++++++++++++++++
 lib/Kconfig.debug                      |   4 +
 lib/Makefile                           |   2 +-
 lib/test_kho_map.c                     | 575 +++++++++++++++++++++++++
 mm/memfd_luo.c                         | 292 ++++++-------
 tools/testing/selftests/kho/vmtest.sh  |   2 +
 13 files changed, 1449 insertions(+), 185 deletions(-)
 create mode 100644 include/linux/kho/abi/map.h
 create mode 100644 include/linux/kho_map.h
 create mode 100644 kernel/liveupdate/kho_map.c
 create mode 100644 lib/test_kho_map.c

base-commit: a0dc8eddbfdb6dd9c5c2b70eb66ab49cb1978425
prerequisite-patch-id: dc555295a2263ea9482ab393c50296636ab1e84f
prerequisite-patch-id: b0c8f9caeb6fd99a352692083e4d2e9255f13d02
prerequisite-patch-id: af8beaebdb1687c349732dc4a7773f7baa4a2c17

Signature · 1 line
2.56.0.611.g1030f0b940-goog