KHO map
Subsystems (6)
Pratyush Yadav
maintainercover 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
Pratyush Yadav
maintainerRFC PATCH 1/5 kho: add KHOSER_CLEAR_PTR()
From: "Pratyush Yadav (Google)" <[email protected]>
Add a helper to reset a KHO serialized pointer to NULL, as a counterpart to KHOSER_STORE_PTR().
--- include/linux/kho/abi/kexec_handover.h | 5 +++++ 1 file changed, 5 insertions(+)
include/linux/kho/abi/kexec_handover.h +5 -0
@@ -132,6 +132,11 @@ (dest).phys =virt_to_phys (v); \ }) +#define KHOSER_CLEAR_PTR (dest) \ + ({ \ + (dest).phys = 0; \ + }) +/* Loads the stored physical address back to a pointer. */ #define KHOSER_LOAD_PTR (src) \ ({ \
Signature · 1 line
2.56.0.611.g1030f0b940-goog
Pratyush Yadav
maintainerRFC PATCH 2/5 kho: build KHO objects into a single kho.o
In reply to Pratyush YadavFrom: "Pratyush Yadav (Google)" <[email protected]>
kho_block.o is part of the KHO infrastructure, but is currently built as part of luo.o, which ties it to CONFIG_LIVEUPDATE.
Group all KHO objects into a composite kho.o, built for CONFIG_KEXEC_HANDOVER, the same way the LUO objects are grouped into luo.o. This also gives a single place to add new KHO objects.
--- kernel/liveupdate/Makefile | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-)
kernel/liveupdate/Makefile +8 -4
@@ -1,13 +1,17 @@ # SPDX-License-Identifier: GPL-2.0 +kho-y := \ + kexec_handover.o \ + kho_block.o + +kho-$(CONFIG_KEXEC_HANDOVER_DEBUGFS) += kexec_handover_debugfs.o + +obj-$(CONFIG_KEXEC_HANDOVER) += kho.o + luo-y := \ - kho_block.o \ luo_core.o \ luo_file.o \ luo_flb.o \ luo_session.o -obj-$(CONFIG_KEXEC_HANDOVER) += kexec_handover.o -obj-$(CONFIG_KEXEC_HANDOVER_DEBUGFS) += kexec_handover_debugfs.o - obj-$(CONFIG_LIVEUPDATE) += luo.o
Signature · 1 line
2.56.0.611.g1030f0b940-goog
Pasha Tatashin
maintainerRe: [RFC PATCH 2/5] kho: build KHO objects into a single kho.o
Quoted 30 lines · Pratyush Yadav
From: "Pratyush Yadav (Google)" <[email protected]>
kho_block.o is part of the KHO infrastructure, but is currently built as part of luo.o, which ties it to
CONFIG_LIVEUPDATE.Group all KHO objects into a composite kho.o, built for
CONFIG_KEXEC_HANDOVER, the same way the LUO objects are grouped into luo.o. This also gives a single place to add new KHO objects.Signed-off-by Pratyush Yadav (Google) <[email protected]>--- kernel/liveupdate/Makefile | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-)kernel/liveupdate/Makefile +8
-0@@ -1,13 +1,17 @@ # SPDX-License-Identifier: GPL-2.0 +kho-y := \ + kexec_handover.o \ + kho_block.o + +kho-$(CONFIG_KEXEC_HANDOVER_DEBUGFS) += kexec_handover_debugfs.o + +obj-$(CONFIG_KEXEC_HANDOVER) += kho.o + luo-y := \
kernel/liveupdate/Makefile line 17
Quoted 10 lines
kernel/liveupdate/Makefile +0
-4- kho_block.o \ luo_core.o \ luo_file.o \ luo_flb.o \ luo_session.o -obj-$(CONFIG_KEXEC_HANDOVER) += kexec_handover.o -obj-$(CONFIG_KEXEC_HANDOVER_DEBUGFS) += kexec_handover_debugfs.o - obj-$(CONFIG_LIVEUPDATE) += luo.o
Please send it as a separate patch. I have the same change included as part of the kho-ro series, but let's fix it outside of both series instead as a standalone fix. Also, maybe rename kexec_handover_debugfs.c to kho_debugfs.c and kexec_handover.c to kho_core.c for consistency, now that they are not shared with the rest of the kexec_* files in kernel/*?
Signature · 1 line
Pasha
Pratyush Yadav
maintainerRe: [RFC PATCH 2/5] kho: build KHO objects into a single kho.o
Quoted 37 lines · Pasha Tatashin
Quoted 36 lines · Pratyush Yadav
From: "Pratyush Yadav (Google)" <[email protected]>
kho_block.o is part of the KHO infrastructure, but is currently built as part of luo.o, which ties it to
CONFIG_LIVEUPDATE.Group all KHO objects into a composite kho.o, built for
CONFIG_KEXEC_HANDOVER, the same way the LUO objects are grouped into luo.o. This also gives a single place to add new KHO objects.Signed-off-by Pratyush Yadav (Google) <[email protected]>--- kernel/liveupdate/Makefile | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-)kernel/liveupdate/Makefile +8
-1@@ -1,13 +1,17 @@ # SPDX-License-Identifier: GPL-2.0 +kho-y := \ + kexec_handover.o \ + kho_block.o + +kho-$(CONFIG_KEXEC_HANDOVER_DEBUGFS) += kexec_handover_debugfs.o + +obj-$(CONFIG_KEXEC_HANDOVER) += kho.o + luo-y := \ - kho_block.o \ luo_core.o \ luo_file.o \ luo_flb.o \ luo_session.o
Quoted 10 lines
kernel/liveupdate/Makefile line 17
Quoted 4 lines
kernel/liveupdate/Makefile +0
-3-obj-$(CONFIG_KEXEC_HANDOVER) += kexec_handover.o -obj-$(CONFIG_KEXEC_HANDOVER_DEBUGFS) += kexec_handover_debugfs.o - obj-$(CONFIG_LIVEUPDATE) += luo.oPlease send it as a separate patch. I have the same change included as part of the kho-ro series, but let's fix it outside of both series instead as a standalone fix. Also, maybe rename
kexec_handover_debugfs.ctokho_debugfs.candkexec_handover.ctokho_core.cfor consistency, now that they are not shared with the rest of the kexec_* files inkernel/*?
Sure, makes sense. I have a few other misc cleanups in mind like re-organizing some of the KHO headers. I can do that all in a single "misc cleanups" series.
Signature · 2 lines
Regards, Pratyush Yadav
Pratyush Yadav
maintainerRFC PATCH 3/5 kho: add KHO map
In reply to Pratyush YadavFrom: "Pratyush Yadav (Google)" <[email protected]>
The KHO map is a sparse map from integer keys to u64 values that can be preserved via KHO. Internally, it is a radix tree of fixed depth with one page per node. The tree has a depth of 6 nodes, so it can support keys up to 54 bits wide. Each node points to a lower node, with the lowest node, the leaf, holds the value.
The map can be used to preserve a sparse key-value map. One example is the index -> folio map in a memfd.
The map is initialized via kho_map_init(), and cleaned up via kho_map_destroy(). kho_map_{get,set,clear}() are used to set the entries in the map, and kho_map_for_each() and kho_map_for_each_from() are used for traversal.
kho_map_{preserve,restore}() are used for KHO preservation and restoration. The map is unpreserved at the start. Once it is preserved, a subsequent kho_map_set() that needs a new node will auto-preserve the node. kho_map_restore() returns a unpreserved map.
The map does not currently free unused nodes. Nodes are freed (and unpreserved) upon kho_map_destroy().
The map does not have any locks, so accesses must be serialized by callers.
--- Documentation/core-api/kho/abi.rst | 5 + Documentation/core-api/kho/index.rst | 12 + include/linux/kho/abi/map.h | 94 +++++ include/linux/kho_map.h | 77 ++++ kernel/liveupdate/Makefile | 3 +- kernel/liveupdate/kho_map.c | 514 +++++++++++++++++++++++++++ 6 files changed, 704 insertions(+), 1 deletion(-) 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
Documentation/core-api/kho/abi.rst +5 -0
@@ -33,6 +33,11 @@ KHO serialization block ABI .. kernel-doc:: include/linux/kho/abi/block.h +KHO map ABI +=========== + +.. kernel-doc:: include/linux/kho/abi/map.h + See Also ========
Documentation/core-api/kho/index.rst +12 -0
@@ -94,6 +94,18 @@ KHO Serialization Blocks API .. kernel-doc:: kernel/liveupdate/kho_block.c :internal: +KHO map +======= + +.. kernel-doc:: kernel/liveupdate/kho_map.c + :doc: KHO map + +.. kernel-doc:: include/linux/kho_map.h + :identifiers: kho_map kho_map_clear kho_map_for_each_from kho_map_for_each + +.. kernel-doc:: kernel/liveupdate/kho_map.c + :internal: + See Also ========
include/linux/kho/abi/map.h new file +94 -0
94 lines not on this page · raw message
include/linux/kho_map.h new file +77 -0
77 lines not on this page · raw message
kernel/liveupdate/Makefile +2 -1
@@ -2,7 +2,8 @@ kho-y := \ kexec_handover.o \ - kho_block.o + kho_block.o \ + kho_map.o kho-$(CONFIG_KEXEC_HANDOVER_DEBUGFS) += kexec_handover_debugfs.o
kernel/liveupdate/kho_map.c new file +514 -0
514 lines not on this page · raw message
Signature · 1 line
2.56.0.611.g1030f0b940-goog
Pratyush Yadav
maintainerRFC PATCH 4/5 kho: test: add KHO map test
In reply to Pratyush YadavFrom: "Pratyush Yadav (Google)" <[email protected]>
Add a test for the KHO map, built together with test_kho under CONFIG_TEST_KEXEC_HANDOVER.
In the first kernel, the test runs functional checks of the API, each on a fresh map. Every check runs twice: once on an unpreserved map and once on a map preserved right after kho_map_init(), so both the plain and the preserve-on-alloc/unpreserve-on-destroy paths are covered.
The checks use different keys to test boundary conditions, and exercise lookups, iteration, overwriting and clearing entries, and destroying and re-initializing a map.
The test then builds a map and hands it over. It preserves the map after adding half of the keys, so the handed-over map has nodes preserved both by kho_map_preserve() walking the existing tree and by kho_map_set() preserving new nodes on allocation.
After kexec, the next kernel restores the map and verifies its contents, and makes sure modification of the tree still works.
Also teach the KHO vmtest.sh to check for the KHO map test result.
--- lib/Kconfig.debug | 4 + lib/Makefile | 2 +- lib/test_kho_map.c | 575 ++++++++++++++++++++++++++ tools/testing/selftests/kho/vmtest.sh | 2 + 4 files changed, 582 insertions(+), 1 deletion(-) create mode 100644 lib/test_kho_map.c
lib/Kconfig.debug +4 -0
@@ -3442,6 +3442,10 @@ config TEST_KEXEC_HANDOVER the first kernel and restores and verifies the data on the boot of kexec'ed kernel. + It also tests the KHO map: the first kernel runs functional checks + and builds and preserves a tree, and the kexec'ed kernel restores, + modifies and destroys it. + For detailed documentation about KHO, see Documentation/core-api/kho. To run the test run:
lib/Makefile +1 -1
@@ -105,7 +105,7 @@ obj-$(CONFIG_TEST_HMM) += test_hmm.o obj-$(CONFIG_TEST_FREE_PAGES) += test_free_pages.o obj-$(CONFIG_TEST_REF_TRACKER) += test_ref_tracker.o obj-$(CONFIG_TEST_OBJPOOL) += test_objpool.o -obj-$(CONFIG_TEST_KEXEC_HANDOVER) += test_kho.o +obj-$(CONFIG_TEST_KEXEC_HANDOVER) += test_kho.o test_kho_map.o obj-$(CONFIG_TEST_FPU) += test_fpu.o test_fpu-y := test_fpu_glue.o test_fpu_impl.o
lib/test_kho_map.c new file +575 -0
575 lines not on this page · raw message
tools/testing/selftests/kho/vmtest.sh +2 -0
@@ -119,6 +119,8 @@ function run_qemu() { -initrd "$initrd" grep "KHO restore succeeded" "$serial" &> /dev/null || fail "KHO failed" + grep "KHO map restore succeeded" "$serial" &> /dev/null || \ + fail "KHO map failed" } function target_to_arch() {
Signature · 1 line
2.56.0.611.g1030f0b940-goog
Pratyush Yadav
maintainerRFC PATCH 5/5 mm/memfd_luo: use KHO map for tracking folios
In reply to Pratyush YadavFrom: "Pratyush Yadav (Google)" <[email protected]>
Currently the folios of the memfd are tracked in a vmalloc-ed array. Each entry takes 16 bytes. 8 bytes for the index and another 8 for the folio info. This is inefficient for memfds with order 0 folios. Updating the map after preservation is also impractical. This makes supporting sparse memfds more difficult.
Use a KHO map to track the folios instead. The key is the index of the folio in the file, so it no longer needs to be stored in the entry, and each entry shrinks to a single u64 holding the PFN and the folio flags.
struct memfd_luo_ser now embeds struct kho_map_ser in place of the folios array and nr_folios. This changes the ABI, so bump the compatible string to "memfd-v3".
--- include/linux/kho/abi/memfd.h | 39 +++-- mm/memfd_luo.c | 292 +++++++++++++++------------------- 2 files changed, 151 insertions(+), 180 deletions(-)
include/linux/kho/abi/memfd.h +24 -15
@@ -11,8 +11,11 @@#ifndef _LINUX_KHO_ABI_MEMFD_H#define _LINUX_KHO_ABI_MEMFD_H +#include <linux/bits.h> +#include <linux/build_bug.h> #include <linux/types.h> #include <linux/kho/abi/kexec_handover.h> +#include <linux/kho/abi/map.h> /** * DOC: memfd Live Update ABI
@@ -23,6 +26,10 @@* The state is serialized into a packed structure `struct memfd_luo_ser` * which is handed over to the next kernel via the KHO mechanism. * +* The folios of the file are stored in a KHO map. The value at a folio index +* is a ``union memfd_luo_folio_ser``. A value of 0 means there is no folio at +* that offset. +* * This interface is a contract. Any modification to the structure layout * constitutes a breaking change. Such changes require incrementing the * version number in the MEMFD_LUO_FH_COMPATIBLE string.
@@ -45,16 +52,21 @@#define MEMFD_LUO_FOLIO_UPTODATE BIT(1)/** -* struct memfd_luo_folio_ser - Serialized state of a single folio. -* @pfn: The page frame number of the folio. -* @flags: Flags to describe the state of the folio. -* @index: The page offset (pgoff_t) of the folio within the original file. +* union memfd_luo_folio_ser - Serialized state of a single folio. +* @val: The raw value stored in the KHO map. +* @pfn: The page frame number of the folio. +* @flags: Flags to describe the state of the folio. */ -struct memfd_luo_folio_ser { -u64 pfn:52 ; -u64 flags:12 ; -u64 index; -} __packed; +union memfd_luo_folio_ser { +u64 val; +struct { +u64 pfn:52 ; +u64 flags:12 ; + }; +}; + +/* It must fit into a KHO map entry. */ +static_assert (sizeof (union memfd_luo_folio_ser ) ==sizeof (u64));/* * The set of seals this version supports preserving. If support for any new
@@ -74,20 +86,17 @@ struct memfd_luo_folio_ser {* @seals: The seals present on the memfd. The seals are uABI so it is safe * to directly use them in the ABI. * @flags: Flags for the file. Unused flag bits must be set to 0. -* @nr_folios: Number of folios in the folios array. -* @folios: KHO vmalloc descriptor pointing to the array of -* struct memfd_luo_folio_ser. +* @folios: Folios in the file. */ struct memfd_luo_ser {u64 pos;u64 size;u32 seals;u32 flags; -u64 nr_folios; -struct kho_vmalloc folios; +struct kho_map_ser folios; } __packed;/* The compatibility string for memfd file handler */ -#define MEMFD_LUO_FH_COMPATIBLE "memfd-v2" +#define MEMFD_LUO_FH_COMPATIBLE "memfd-v3"#endif /* _LINUX_KHO_ABI_MEMFD_H */
mm/memfd_luo.c +127 -165
497 lines not on this page · raw message
Signature · 1 line
2.56.0.611.g1030f0b940-goog
Pasha Tatashin
maintainerQuoted 31 lines
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_memfdpreservation.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.
Quoted 7 lines
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.
Let's fix it, see below.
Quoted 4 lines
- 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.
I would not worry about this. If versioning lands first, this series can be updated then; if this series lands first, Tarun will update his series.
Quoted 3 lines
- Dynamic depth support: Currently the depth is static, so it can only support keys up to 54 bits wide. Adding support for multiple depth
Let's allow keys to cover the full 64-bit space from day 1, and make values 63-bit (like XArray), using bit 0 to distinguish a child node pointer from a leaf value.
By making it generic from the beginning, we won't need to worry about ABI churn for these features later. Instead of caller-chosen depth, the tree should grow (and shrink?) dynamically bottom-up based on the widest key.
Plus, with bit 0 tagging leaf values, 2M entries can be stored directly at L1 and 1G at L2 (on 4K pages). Even for huge memfds, the pgoff space is much smaller than 64 bits, so in practice the tree stays tiny in depth.
Signature · 1 line
Pasha
Pratyush Yadav
maintainerQuoted 42 lines · Pasha Tatashin
Quoted 31 lines
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_memfdpreservation.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.
Quoted 7 lines
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.
Let's fix it, see below.
Quoted 1 line
Quoted 7 lines
Quoted 3 lines
- 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.
I would not worry about this. If versioning lands first, this series can be updated then; if this series lands first, Tarun will update his series.
Sure, fair enough.
Quoted 11 lines
Quoted 4 lines
- Dynamic depth support: Currently the depth is static, so it can only support keys up to 54 bits wide. Adding support for multiple depth
Let's allow keys to cover the full 64-bit space from day 1, and make values 63-bit (like XArray), using bit 0 to distinguish a child node pointer from a leaf value.
By making it generic from the beginning, we won't need to worry about ABI churn for these features later.
Right, that makes sense. I didn't want to over-complicate things, but you have a point. Taking the ABI complexity up-front is better than the churn later down the line.
Quoted 7 lines
Instead of caller-chosen depth, the tree should grow (and shrink?) dynamically bottom-up based on the widest key.
Plus, with bit 0 tagging leaf values, 2M entries can be stored directly at L1 and 1G at L2 (on 4K pages). Even for huge memfds, the pgoff space is much smaller than 64 bits, so in practice the tree stays tiny in depth.
I think it is a good idea to allow dynamic depth in the ABI, but I am not sure if we should deal with the automatic resizing just yet. How about we start with making callers specify the depth (max index/pgoff) up-front for now? The ABI stays the same, so we can add support for dynamic resizing later if needed.
The reason for this is to keep things simpler to begin with. That said, I don't have a _strong_ opinion about this, so if you insist, I can add dynamic resizing from the get go.
Signature · 2 lines
Regards, Pratyush Yadav
Pratyush Yadav
maintainerQuoted 1 line · Pratyush Yadav
On Mon, Nov 16 2026, Pasha Tatashin wrote:
[...]
Quoted 14 lines
Quoted 7 lines
Instead of caller-chosen depth, the tree should grow (and shrink?) dynamically bottom-up based on the widest key.
Plus, with bit 0 tagging leaf values, 2M entries can be stored directly at L1 and 1G at L2 (on 4K pages). Even for huge memfds, the pgoff space is much smaller than 64 bits, so in practice the tree stays tiny in depth.
I think it is a good idea to allow dynamic depth in the ABI, but I am not sure if we should deal with the automatic resizing just yet. How about we start with making callers specify the depth (max index/pgoff) up-front for now? The ABI stays the same, so we can add support for dynamic resizing later if needed.
Quoted 3 lines
The reason for this is to keep things simpler to begin with. That said, I don't have a _strong_ opinion about this, so if you insist, I can add dynamic resizing from the get go.
I take this back. I went and looked at how xarray does it, and it is pretty elegant. I thought some sort of rebalancing would be needed, but all that is needed is to add a level above the root tree, and demote it to a subtree. Similarly, for pruning, the subtree at index 0 can be promoted if all other slots of the root are free.
So I'll add dynamic sizing and reparenting logic in v2.
Signature · 2 lines
Regards, Pratyush Yadav
Pasha Tatashin
maintainerQuoted 22 lines · Pratyush Yadav
Quoted 1 line · Pratyush Yadav
On Mon, Nov 16 2026, Pasha Tatashin wrote:
[...]
Quoted 14 lines
Quoted 7 lines
Instead of caller-chosen depth, the tree should grow (and shrink?) dynamically bottom-up based on the widest key.
Plus, with bit 0 tagging leaf values, 2M entries can be stored directly at L1 and 1G at L2 (on 4K pages). Even for huge memfds, the pgoff space is much smaller than 64 bits, so in practice the tree stays tiny in depth.
I think it is a good idea to allow dynamic depth in the ABI, but I am not sure if we should deal with the automatic resizing just yet. How about we start with making callers specify the depth (max index/pgoff) up-front for now? The ABI stays the same, so we can add support for dynamic resizing later if needed.
Quoted 3 lines
The reason for this is to keep things simpler to begin with. That said, I don't have a _strong_ opinion about this, so if you insist, I can add dynamic resizing from the get go.
Quoted 7 lines
I take this back. I went and looked at how xarray does it, and it is pretty elegant. I thought some sort of rebalancing would be needed, but all that is needed is to add a level above the root tree, and demote it to a subtree. Similarly, for pruning, the subtree at index 0 can be promoted if all other slots of the root are free.
So I'll add dynamic sizing and reparenting logic in v2.
I agree; let's implement this properly from the start. Growing from the bottom up is the right approach. I am not sure whether support for shrinking is needed, so that can be added later.
Signature · 1 line
Pasha
Hi Pratyush,
Quoted 4 lines · Pratyush Yadav
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.
That only holds for order-0 folios though. A leaf covers 512 indices, so a populated memfd needs one leaf page for every 2M of file whatever the folio size, while the array needs 16 bytes per folio. Per 2M of file, that works out as:
folio size array map map/array
4K (o0) 8K 4K 0.5x
8K (o1) 4K 4K 1x
16K (o2) 2K 4K 2x
64K (o4) 512 4K 8x
2M (o9) 16 4K 256xQuoted 5 lines
- 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.
Since patch 5 makes things worse for memfds with large folios, I agree with Pasha that this needs fixing before memfd switches over. Storing PMD-sized entries at L1 fixes the 2M case, but mTHP sizes between 4K and 2M would still take a full leaf for every 2M of file. Do you expect mTHP-backed memfds to be preserved? If so, it's probably worth handling them in the format before it becomes ABI.
Thanks!
Chris
Pratyush Yadav
maintainerHi Chris,
Quoted 13 lines · Chris Down
Hi Pratyush,
Quoted 4 lines · Pratyush Yadav
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.
That only holds for order-0 folios though. A leaf covers 512 indices, so a populated memfd needs one leaf page for every 2M of file whatever the folio size, while the array needs 16 bytes per folio. Per 2M of file, that works out as:
Quoted 6 lines
folio size array map map/array
4K (o0) 8K 4K 0.5x
8K (o1) 4K 4K 1x
16K (o2) 2K 4K 2x
64K (o4) 512 4K 8x
2M (o9) 16 4K 256xRight.
Quoted 9 lines
Quoted 6 lines
- 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.
Since patch 5 makes things worse for memfds with large folios, I agree with Pasha that this needs fixing before memfd switches over. Storing
Right, I agree as well.
Quoted 4 lines
PMD-sized entries at L1 fixes the 2M case, but mTHP sizes between 4K and 2M would still take a full leaf for every 2M of file. Do you expect mTHP-backed memfds to be preserved? If so, it's probably worth handling them in the format before it becomes ABI.
mTHP will still work, it will just be less space efficient than 2M THPs. Even then, the overhead is around 2M for every 1G, which is roughly 0.2%. Even then, I don't think that is too bad. If you want to be more space efficient, use 2M THPs, or hugetlb[*]. I think that is a fair tradeoff. Using larger page sizes also makes KHO more efficient.
We _can_ make mTHPs fairly efficient, but that comes at the cost of a more complicated ABI. For example, we can have a per-order KHO map in the memfd, and shift the keys by the order. That should improve the density. We could also do some other tricks like the shifted key encoding scheme that KHO preserved memory map uses (see kho_encode_radix_key()) to improve density.
So unless someone can explain why mTHP memfds are important to optimize for, I'd say mTHP users can either take the 0.2% preservation overhead, or use 2M THPs.
[*] I sent an RFC for that some time ago, but it's been blocked on
pending infrastructure rework like extended bootmem. I plan to send out a refreshed version soon.
Signature · 2 lines
Regards, Pratyush Yadav