Linux-mm Archive on lore.kernel.org
 help / color / mirror / Atom feed
* [RFC PATCH 0/5] KHO map
@ 2026-11-16 13:40 Pratyush Yadav
  2026-11-16 13:40 ` [RFC PATCH 1/5] kho: add KHOSER_CLEAR_PTR() Pratyush Yadav
                   ` (4 more replies)
  0 siblings, 5 replies; 6+ messages in thread
From: Pratyush Yadav @ 2026-11-16 13:40 UTC (permalink / raw)
  To: Mike Rapoport, Pasha Tatashin, Pratyush Yadav, Alexander Graf,
	Jonathan Corbet, Shuah Khan, Randy Dunlap, Andrew Morton,
	Tarun Sahu, David Matlack, Samiullah Khawaja
  Cc: kexec, linux-mm, linux-doc, linux-kernel, linux-kselftest

From: "Pratyush Yadav (Google)" <pratyush@kernel.org>

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/20261103172251.2348370-1-pratyush@kernel.org/
[1] https://lore.kernel.org/kexec/20261110175855.2437084-1-pratyush@kernel.org/

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
-- 
2.56.0.611.g1030f0b940-goog



^ permalink raw reply	[flat|nested] 6+ messages in thread

* [RFC PATCH 1/5] kho: add KHOSER_CLEAR_PTR()
  2026-11-16 13:40 [RFC PATCH 0/5] KHO map Pratyush Yadav
@ 2026-11-16 13:40 ` Pratyush Yadav
  2026-11-16 13:40 ` [RFC PATCH 2/5] kho: build KHO objects into a single kho.o Pratyush Yadav
                   ` (3 subsequent siblings)
  4 siblings, 0 replies; 6+ messages in thread
From: Pratyush Yadav @ 2026-11-16 13:40 UTC (permalink / raw)
  To: Mike Rapoport, Pasha Tatashin, Pratyush Yadav, Alexander Graf,
	Jonathan Corbet, Shuah Khan, Randy Dunlap, Andrew Morton,
	Tarun Sahu, David Matlack, Samiullah Khawaja
  Cc: kexec, linux-mm, linux-doc, linux-kernel, linux-kselftest

From: "Pratyush Yadav (Google)" <pratyush@kernel.org>

Add a helper to reset a KHO serialized pointer to NULL, as a counterpart
to KHOSER_STORE_PTR().

Signed-off-by: Pratyush Yadav (Google) <pratyush@kernel.org>
---
 include/linux/kho/abi/kexec_handover.h | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/include/linux/kho/abi/kexec_handover.h b/include/linux/kho/abi/kexec_handover.h
index 2f4fb9c639421..5fe9c5e10ac89 100644
--- a/include/linux/kho/abi/kexec_handover.h
+++ b/include/linux/kho/abi/kexec_handover.h
@@ -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)						\
 	({                                                                   \
-- 
2.56.0.611.g1030f0b940-goog



^ permalink raw reply related	[flat|nested] 6+ messages in thread

* [RFC PATCH 2/5] kho: build KHO objects into a single kho.o
  2026-11-16 13:40 [RFC PATCH 0/5] KHO map Pratyush Yadav
  2026-11-16 13:40 ` [RFC PATCH 1/5] kho: add KHOSER_CLEAR_PTR() Pratyush Yadav
@ 2026-11-16 13:40 ` Pratyush Yadav
  2026-11-16 13:40 ` [RFC PATCH 3/5] kho: add KHO map Pratyush Yadav
                   ` (2 subsequent siblings)
  4 siblings, 0 replies; 6+ messages in thread
From: Pratyush Yadav @ 2026-11-16 13:40 UTC (permalink / raw)
  To: Mike Rapoport, Pasha Tatashin, Pratyush Yadav, Alexander Graf,
	Jonathan Corbet, Shuah Khan, Randy Dunlap, Andrew Morton,
	Tarun Sahu, David Matlack, Samiullah Khawaja
  Cc: kexec, linux-mm, linux-doc, linux-kernel, linux-kselftest

From: "Pratyush Yadav (Google)" <pratyush@kernel.org>

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) <pratyush@kernel.org>
---
 kernel/liveupdate/Makefile | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/kernel/liveupdate/Makefile b/kernel/liveupdate/Makefile
index d9f4694625567..bc679905ce3f2 100644
--- a/kernel/liveupdate/Makefile
+++ b/kernel/liveupdate/Makefile
@@ -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
-- 
2.56.0.611.g1030f0b940-goog



^ permalink raw reply related	[flat|nested] 6+ messages in thread

* [RFC PATCH 3/5] kho: add KHO map
  2026-11-16 13:40 [RFC PATCH 0/5] KHO map Pratyush Yadav
  2026-11-16 13:40 ` [RFC PATCH 1/5] kho: add KHOSER_CLEAR_PTR() Pratyush Yadav
  2026-11-16 13:40 ` [RFC PATCH 2/5] kho: build KHO objects into a single kho.o Pratyush Yadav
@ 2026-11-16 13:40 ` Pratyush Yadav
  2026-11-16 13:40 ` [RFC PATCH 4/5] kho: test: add KHO map test Pratyush Yadav
  2026-11-16 13:40 ` [RFC PATCH 5/5] mm/memfd_luo: use KHO map for tracking folios Pratyush Yadav
  4 siblings, 0 replies; 6+ messages in thread
From: Pratyush Yadav @ 2026-11-16 13:40 UTC (permalink / raw)
  To: Mike Rapoport, Pasha Tatashin, Pratyush Yadav, Alexander Graf,
	Jonathan Corbet, Shuah Khan, Randy Dunlap, Andrew Morton,
	Tarun Sahu, David Matlack, Samiullah Khawaja
  Cc: kexec, linux-mm, linux-doc, linux-kernel, linux-kselftest

From: "Pratyush Yadav (Google)" <pratyush@kernel.org>

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.

Signed-off-by: Pratyush Yadav (Google) <pratyush@kernel.org>
---
 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

diff --git a/Documentation/core-api/kho/abi.rst b/Documentation/core-api/kho/abi.rst
index edeb5b3119638..2d56d3089d65b 100644
--- a/Documentation/core-api/kho/abi.rst
+++ b/Documentation/core-api/kho/abi.rst
@@ -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
 ========
 
diff --git a/Documentation/core-api/kho/index.rst b/Documentation/core-api/kho/index.rst
index e78a2bbe2be1d..36cbfd3656306 100644
--- a/Documentation/core-api/kho/index.rst
+++ b/Documentation/core-api/kho/index.rst
@@ -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
 ========
 
diff --git a/include/linux/kho/abi/map.h b/include/linux/kho/abi/map.h
new file mode 100644
index 0000000000000..ebcedaf94b6f5
--- /dev/null
+++ b/include/linux/kho/abi/map.h
@@ -0,0 +1,94 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright (c) 2026, Google LLC.
+ * Pratyush Yadav <pratyush@kernel.org>
+ */
+
+#ifndef _LINUX_KHO_ABI_MAP_H
+#define _LINUX_KHO_ABI_MAP_H
+
+#include <linux/kho/abi/kexec_handover.h>
+#include <linux/log2.h>
+#include <linux/math.h>
+
+#include <asm/page.h>
+
+/**
+ * DOC: KHO map ABI
+ *
+ * The ABI defined below is used for passing a KHO map from one kernel to the
+ * next.
+ *
+ * - ``struct kho_map_ser`` holds the physical address of the root node, or
+ *   0 for an empty tree.
+ * - The tree always has %KHO_MAP_DEPTH levels. Level
+ *   ``KHO_MAP_DEPTH - 1`` is the root and level 0 holds the leaves.
+ * - Every node and leaf is a single page, preserved as an order 0 folio.
+ * - A key is at most %KHO_MAP_KEY_WIDTH bits wide. It is split into
+ *   %KHO_MAP_TBL_SHIFT bit indices, one per level, with the most
+ *   significant bits indexing the root and the least significant bits
+ *   indexing the leaf.
+ * - Intermediate nodes (``struct kho_map_node_ser``) hold the physical
+ *   addresses of the nodes one level below, or 0 for none.
+ * - Leaves (&struct kho_map_leaf_ser) hold the values, where 0 means there
+ *   is no entry.
+ *
+ * The KHO map has no version of its own. Any change to this layout,
+ * including to %KHO_MAP_KEY_WIDTH, is a breaking change for every user that
+ * hands over a KHO map, and requires bumping their ABI versions.
+ */
+
+/**
+ * enum kho_map_consts - Constants describing the KHO map layout.
+ * @KHO_MAP_KEY_WIDTH: Maximum width of a key, in bits.
+ * @KHO_MAP_TBL_ENTRIES: Number of entries in a node or leaf.
+ * @KHO_MAP_TBL_SHIFT: Number of key bits used as the index at each level.
+ * @KHO_MAP_TBL_MASK: Mask for the index at each level.
+ * @KHO_MAP_DEPTH: Number of levels in the tree.
+ */
+enum kho_map_consts {
+	/* TODO: support dynamic width? */
+	/* Adds up to a depth of 6. */
+	KHO_MAP_KEY_WIDTH = 54,
+
+	KHO_MAP_TBL_ENTRIES = PAGE_SIZE / sizeof(u64),
+	KHO_MAP_TBL_SHIFT = const_ilog2(KHO_MAP_TBL_ENTRIES),
+	/* KHO_MAP_TBL_ENTRIES is a power of 2. */
+	KHO_MAP_TBL_MASK = KHO_MAP_TBL_ENTRIES - 1,
+
+	KHO_MAP_DEPTH = DIV_ROUND_UP(KHO_MAP_KEY_WIDTH, KHO_MAP_TBL_SHIFT),
+};
+
+/*
+ * An intermediate node of a KHO map. @table holds the physical addresses of
+ * the nodes one level below, or 0 for none, indexed by the bits of the key for
+ * this level.
+ *
+ * Not kernel-doc, since kernel-doc can't parse DECLARE_KHOSER_PTR() members.
+ */
+struct kho_map_node_ser {
+	DECLARE_KHOSER_PTR(table, struct kho_map_node_ser *)[1 << KHO_MAP_TBL_SHIFT];
+};
+
+/**
+ * struct kho_map_leaf_ser - A leaf of a KHO map.
+ * @values: Values of the entries, or 0 for no entry. Indexed by the lowest
+ *          %KHO_MAP_TBL_SHIFT bits of the key.
+ */
+struct kho_map_leaf_ser {
+	u64 values[KHO_MAP_TBL_ENTRIES];
+};
+
+/*
+ * The serialized form of a KHO map. @root holds the physical address of the
+ * root node, or 0 for an empty tree. Users embed this in their own serialized
+ * state to hand the tree over.
+ *
+ * Not kernel-doc, since kernel-doc can't parse DECLARE_KHOSER_PTR() members.
+ */
+struct kho_map_ser {
+	/* TODO: capability flag header */
+	DECLARE_KHOSER_PTR(root, struct kho_map_node_ser *);
+};
+
+#endif /* _LINUX_KHO_ABI_MAP_H */
diff --git a/include/linux/kho_map.h b/include/linux/kho_map.h
new file mode 100644
index 0000000000000..a61fb6a054341
--- /dev/null
+++ b/include/linux/kho_map.h
@@ -0,0 +1,77 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright (c) 2026, Google LLC.
+ * Pratyush Yadav <pratyush@kernel.org>
+ */
+
+#ifndef _LINUX_KHO_MAP_H
+#define _LINUX_KHO_MAP_H
+
+#include <linux/kho/abi/map.h>
+#include <linux/mutex_types.h>
+
+/**
+ * struct kho_map - A KHO map.
+ * @ser: The serialized form of the tree. This is what gets handed over.
+ * @preserved: The nodes of the tree are preserved with KHO. Set by
+ *             kho_map_preserve().
+ *
+ * Runtime handle of a KHO map. It is not handed over, only @ser is. This is
+ * what all the kho_map_*() functions operate on.
+ */
+struct kho_map {
+	struct kho_map_ser *ser;
+	bool preserved;
+};
+
+void kho_map_init(struct kho_map *map, struct kho_map_ser *ser);
+void kho_map_destroy(struct kho_map *map);
+int kho_map_restore(struct kho_map *map, struct kho_map_ser *ser);
+int kho_map_preserve(struct kho_map *map);
+
+int kho_map_set(struct kho_map *map, u64 key, u64 value);
+u64 kho_map_get(struct kho_map *map, u64 key);
+
+/**
+ * kho_map_clear() - Remove an entry from a KHO map.
+ * @map: The KHO map.
+ * @key: Key of the entry to remove.
+ *
+ * Same as storing 0 with kho_map_set(). Never allocates memory and can't fail.
+ * Keys that are out of range, or not present, are ignored. Nodes that become
+ * empty are freed.
+ */
+static inline void kho_map_clear(struct kho_map *map, u64 key)
+{
+	/* Storing 0 never allocates and can't fail. */
+	kho_map_set(map, key, 0);
+}
+
+u64 kho_map_next(struct kho_map *map, u64 key, u64 *value);
+
+/**
+ * kho_map_for_each_from() - Iterate over entries of a KHO map from a key.
+ * @map: The KHO map.
+ * @key: u64 variable that holds the key of the current entry.
+ * @value: u64 variable that holds the value of the current entry.
+ * @start: Key to start iterating from.
+ *
+ * Visits the entries with keys greater than or equal to @start, in increasing
+ * order of keys.
+ */
+#define kho_map_for_each_from(map, key, value, start)				\
+	for ((key) = kho_map_next(map, start, &(value)); (key) != U64_MAX;	\
+	     (key) = kho_map_next(map, (key) + 1, &(value)))
+
+/**
+ * kho_map_for_each() - Iterate over all entries of a KHO map.
+ * @map: The KHO map.
+ * @key: u64 variable that holds the key of the current entry.
+ * @value: u64 variable that holds the value of the current entry.
+ *
+ * Visits the entries in increasing order of keys.
+ */
+#define kho_map_for_each(map, key, value)					\
+	kho_map_for_each_from(map, key, value, 0)
+
+#endif /* _LINUX_KHO_MAP_H */
diff --git a/kernel/liveupdate/Makefile b/kernel/liveupdate/Makefile
index bc679905ce3f2..95fee902f9360 100644
--- a/kernel/liveupdate/Makefile
+++ b/kernel/liveupdate/Makefile
@@ -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
 
diff --git a/kernel/liveupdate/kho_map.c b/kernel/liveupdate/kho_map.c
new file mode 100644
index 0000000000000..947dad2a04ddb
--- /dev/null
+++ b/kernel/liveupdate/kho_map.c
@@ -0,0 +1,514 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * Copyright (c) 2026, Google LLC.
+ * Pratyush Yadav <pratyush@kernel.org>
+ */
+
+/**
+ * DOC: KHO map
+ *
+ * A KHO map is a sparse mapping from integer keys (at most %KHO_MAP_KEY_WIDTH
+ * wide) to non-zero u64 values, kept in memory that can be preserved with KHO.
+ *
+ * Internally it is a radix tree of fixed depth, with one page per node.
+ *
+ * A tree has two parts. ``struct kho_map_ser`` is its serialized form,
+ * which points to the root node. To hand a tree over, embed its
+ * ``struct kho_map_ser`` in the serialized payload. ``struct kho_map`` is
+ * the runtime handle of the tree. It points to the ``struct kho_map_ser``
+ * and is what all kho_map_*() functions operate on.
+ *
+ * A tree starts out unpreserved. kho_map_preserve() preserves every node of the
+ * tree with KHO. From then on, nodes are preserved as soon as they are
+ * allocated, so the tree is ready to be handed over at any point.
+ * kho_map_destroy() frees the nodes, and unpreserves them if needed. A tree is
+ * restored with kho_map_restore(), and comes out unpreserved.
+ *
+ * There is no internal locking. Callers must serialize all accesses to the map.
+ */
+
+#include <linux/io.h>
+#include <linux/mm.h>
+#include <linux/kexec_handover.h>
+#include <linux/kho/abi/map.h>
+#include <linux/kho_map.h>
+
+/**
+ * kho_map_init() - Initialize an empty KHO map.
+ * @map: The KHO map.
+ * @ser: The serialized form of the tree. Can be handed over to the next kernel
+ *       once the tree is populated.
+ *
+ * Any previous contents of @ser are discarded. @ser must stay around for as
+ * long as @map is used.
+ */
+void kho_map_init(struct kho_map *map, struct kho_map_ser *ser)
+{
+	map->ser = ser;
+	map->preserved = false;
+	KHOSER_CLEAR_PTR(ser->root);
+}
+
+static unsigned int kho_map_node_idx(u64 key, unsigned int level)
+{
+	return (key >> (level * KHO_MAP_TBL_SHIFT)) & KHO_MAP_TBL_MASK;
+}
+
+static struct kho_map_node_ser *kho_map_alloc_node(struct kho_map *map)
+{
+	struct folio *folio = folio_alloc(GFP_KERNEL | __GFP_ZERO, 0);
+
+	if (!folio)
+		return NULL;
+
+	if (map->preserved && kho_preserve_folio(folio)) {
+		folio_put(folio);
+		return NULL;
+	}
+
+	return folio_address(folio);
+}
+
+static void kho_map_free_node(struct kho_map *map, void *node)
+{
+	struct folio *folio = virt_to_folio(node);
+
+	if (map->preserved)
+		kho_unpreserve_folio(folio);
+	folio_put(folio);
+}
+
+static int kho_map_restore_folio(void *node)
+{
+	struct folio *folio = kho_restore_folio(virt_to_phys(node));
+
+	if (!folio)
+		return -EINVAL;
+
+	if (WARN_ON_ONCE(folio_order(folio))) {
+		folio_put(folio);
+		return -EINVAL;
+	}
+
+	return 0;
+}
+
+static void __kho_map_destroy_node(struct kho_map *map,
+				   struct kho_map_node_ser *node,
+				   unsigned int level)
+{
+	unsigned int i;
+
+	/* Level 0 nodes are leaves and hold values, not pointers. */
+	if (level == 0) {
+		kho_map_free_node(map, node);
+		return;
+	}
+
+	for (i = 0; i < KHO_MAP_TBL_ENTRIES; i++) {
+		struct kho_map_node_ser *next = KHOSER_LOAD_PTR(node->table[i]);
+
+		if (next)
+			__kho_map_destroy_node(map, next, level - 1);
+	}
+
+	kho_map_free_node(map, node);
+}
+
+/**
+ * kho_map_destroy() - Free all nodes of a KHO map.
+ * @map: The KHO map.
+ *
+ * Frees every node, leaving an empty tree behind that can be used again. If
+ * the tree is preserved, the nodes are unpreserved first.
+ *
+ * Post-KHO, this can only be called after kho_map_restore().
+ */
+void kho_map_destroy(struct kho_map *map)
+{
+	struct kho_map_node_ser *root = KHOSER_LOAD_PTR(map->ser->root);
+
+	if (!root)
+		return;
+
+	__kho_map_destroy_node(map, root, KHO_MAP_DEPTH - 1);
+	KHOSER_CLEAR_PTR(map->ser->root);
+}
+
+/* Unpreserve @node and everything below it. */
+static void __kho_map_unpreserve_node(struct kho_map_node_ser *node,
+				      unsigned int level)
+{
+	unsigned int i;
+
+	/* Level 0 nodes are leaves and hold values, not pointers. */
+	for (i = 0; level && i < KHO_MAP_TBL_ENTRIES; i++) {
+		struct kho_map_node_ser *next = KHOSER_LOAD_PTR(node->table[i]);
+
+		if (next)
+			__kho_map_unpreserve_node(next, level - 1);
+	}
+
+	kho_unpreserve_folio(virt_to_folio(node));
+}
+
+/*
+ * Preserve @node and everything below it. On failure, everything that was
+ * preserved is unpreserved again.
+ */
+static int __kho_map_preserve_node(struct kho_map_node_ser *node,
+				   unsigned int level)
+{
+	unsigned int i, j;
+	int err;
+
+	err = kho_preserve_folio(virt_to_folio(node));
+	if (err)
+		return err;
+
+	/* Level 0 nodes are leaves and hold values, not pointers. */
+	if (level == 0)
+		return 0;
+
+	for (i = 0; i < KHO_MAP_TBL_ENTRIES; i++) {
+		struct kho_map_node_ser *next = KHOSER_LOAD_PTR(node->table[i]);
+
+		if (!next)
+			continue;
+
+		err = __kho_map_preserve_node(next, level - 1);
+		if (err)
+			goto err_unpreserve;
+	}
+
+	return 0;
+
+err_unpreserve:
+	/* next has already unpreserved itself, undo the entries before it. */
+	for (j = 0; j < i; j++) {
+		struct kho_map_node_ser *next = KHOSER_LOAD_PTR(node->table[j]);
+
+		if (next)
+			__kho_map_unpreserve_node(next, level - 1);
+	}
+	kho_unpreserve_folio(virt_to_folio(node));
+	return err;
+}
+
+/**
+ * kho_map_preserve() - Preserve a KHO map.
+ * @map: The KHO map.
+ *
+ * Preserves every node of the tree with KHO, and marks the tree as preserved,
+ * so that nodes allocated from now on are preserved as well. Afterwards the
+ * tree can be handed over to the next kernel at any point, by handing over its
+ * &struct kho_map_ser. Preserving a tree that is already preserved does
+ * nothing.
+ *
+ * There is no way to unpreserve the tree short of kho_map_destroy().
+ *
+ * Context: Can sleep.
+ * Return: 0 on success, -errno on failure. On failure the tree is left
+ * unpreserved.
+ */
+int kho_map_preserve(struct kho_map *map)
+{
+	struct kho_map_node_ser *root = KHOSER_LOAD_PTR(map->ser->root);
+	int err;
+
+	if (map->preserved)
+		return 0;
+
+	if (root) {
+		err = __kho_map_preserve_node(root, KHO_MAP_DEPTH - 1);
+		if (err)
+			return err;
+	}
+
+	map->preserved = true;
+	return 0;
+}
+
+/*
+ * Restore @node and everything below it.
+ *
+ * On failure, everything that was restored is freed again and the caller must
+ * drop its reference to @node. Nodes that could not be restored are leaked.
+ */
+static int __kho_map_restore_node(struct kho_map *map,
+				  struct kho_map_node_ser *node,
+				  unsigned int level)
+{
+	unsigned int i, j;
+	int err;
+
+	err = kho_map_restore_folio(node);
+	if (err)
+		return err;
+
+	/* Level 0 nodes are leaves and hold values, not pointers. */
+	if (level == 0)
+		return 0;
+
+	for (i = 0; i < KHO_MAP_TBL_ENTRIES; i++) {
+		struct kho_map_node_ser *next = KHOSER_LOAD_PTR(node->table[i]);
+
+		if (!next)
+			continue;
+
+		err = __kho_map_restore_node(map, next, level - 1);
+		if (err)
+			goto err_destroy;
+	}
+
+	return 0;
+
+err_destroy:
+	/*
+	 * next has already freed itself, and the entries after it were never
+	 * restored. Cut them all off, then free what is left.
+	 */
+	for (j = i; j < KHO_MAP_TBL_ENTRIES; j++)
+		KHOSER_CLEAR_PTR(node->table[j]);
+	__kho_map_destroy_node(map, node, level);
+	return err;
+}
+
+/**
+ * kho_map_restore() - Restore KHO map.
+ * @map: The KHO map to set up.
+ * @ser: The serialized form of the tree, handed over by the previous kernel.
+ *
+ * Restores every node of the tree in @ser, and sets up @map to refer to it.
+ * Afterwards @map can be used with all other kho_map_*() functions, exactly
+ * like a tree built in this kernel. @ser must stay around for as long as @map
+ * is used.
+ *
+ * The restored tree is unpreserved, so it is not handed over to the next kernel
+ * again unless kho_map_preserve() is called on it.
+ *
+ * Return: 0 on success, or -errno on failure. On failure the tree is destroyed,
+ * and nodes that could not be restored are leaked. @map is still set up and
+ * refers to an empty tree.
+ */
+int kho_map_restore(struct kho_map *map, struct kho_map_ser *ser)
+{
+	struct kho_map_node_ser *root = KHOSER_LOAD_PTR(ser->root);
+	int err;
+
+	map->ser = ser;
+	map->preserved = false;
+
+	if (!root)
+		return 0;
+
+	err = __kho_map_restore_node(map, root, KHO_MAP_DEPTH - 1);
+	if (err)
+		KHOSER_CLEAR_PTR(map->ser->root);
+
+	return err;
+}
+
+/*
+ * Free the empty nodes on the path to @key, going up from @level. @path[i] is
+ * the node at level i on the path. Stops at the first node that is not empty,
+ * since the nodes above it then aren't empty either.
+ */
+static void kho_map_prune(struct kho_map *map,
+			  struct kho_map_node_ser *path[KHO_MAP_DEPTH],
+			  u64 key, unsigned int level)
+{
+	for (unsigned int i = level; i < KHO_MAP_DEPTH; i++) {
+		if (memchr_inv(path[i], 0, PAGE_SIZE))
+			return;
+
+		/* Unlink the node before freeing it. */
+		if (i == KHO_MAP_DEPTH - 1)
+			KHOSER_CLEAR_PTR(map->ser->root);
+		else
+			KHOSER_CLEAR_PTR(path[i + 1]->table[kho_map_node_idx(key, i + 1)]);
+
+		kho_map_free_node(map, path[i]);
+	}
+}
+
+/**
+ * kho_map_set() - Store a value in a KHO map.
+ * @map: The KHO map.
+ * @key: Key of the entry. At most %KHO_MAP_KEY_WIDTH bits wide.
+ * @value: Value to store.
+ *
+ * Adds an entry, or replaces the value of an existing one.
+ *
+ * A value of 0 means the entry is not present, so storing 0 removes the entry.
+ * Removing never allocates nodes and can't fail for keys in range. Nodes that
+ * become empty are freed.
+ *
+ * Context: Can sleep when @value is not 0.
+ * Return: 0 on success, -errno on failure.
+ */
+int kho_map_set(struct kho_map *map, u64 key, u64 value)
+{
+	struct kho_map_node_ser *root = KHOSER_LOAD_PTR(map->ser->root), *node;
+	struct kho_map_node_ser *path[KHO_MAP_DEPTH] = {};
+	struct kho_map_leaf_ser *leaf;
+	unsigned int i, idx;
+
+	if (unlikely(fls64(key) > KHO_MAP_KEY_WIDTH))
+		return -ERANGE;
+
+	if (!root) {
+		/* No tree, so the entry is already clear. */
+		if (!value)
+			return 0;
+
+		root = kho_map_alloc_node(map);
+		if (!root)
+			return -ENOMEM;
+
+		KHOSER_STORE_PTR(map->ser->root, root);
+	}
+
+	node = root;
+
+	for (i = KHO_MAP_DEPTH - 1; i > 0; i--) {
+		struct kho_map_node_ser *next;
+
+		path[i] = node;
+		idx = kho_map_node_idx(key, i);
+
+		next = KHOSER_LOAD_PTR(node->table[idx]);
+		/* Node already exists, go down to the next level. */
+		if (next) {
+			node = next;
+			continue;
+		}
+
+		/* No node on the path, so the entry is already clear. */
+		if (!value)
+			return 0;
+
+		next = kho_map_alloc_node(map);
+		if (!next) {
+			kho_map_prune(map, path, key, i);
+			return -ENOMEM;
+		}
+
+		KHOSER_STORE_PTR(node->table[idx], next);
+		node = next;
+	}
+
+	/* node now points to the leaf node. */
+	path[0] = node;
+	leaf = (struct kho_map_leaf_ser *)node;
+	idx = kho_map_node_idx(key, 0);
+	leaf->values[idx] = value;
+
+	/* If clearing the key made the leaf empty, prune it. */
+	if (!value)
+		kho_map_prune(map, path, key, 0);
+
+	return 0;
+}
+
+/**
+ * kho_map_get() - Look up a value in a KHO map.
+ * @map: The KHO map.
+ * @key: Key of the entry.
+ *
+ * Return: The value of the entry, or 0 if there is no entry for @key or it is
+ * out of range.
+ */
+u64 kho_map_get(struct kho_map *map, u64 key)
+{
+	struct kho_map_node_ser *node = KHOSER_LOAD_PTR(map->ser->root);
+	struct kho_map_leaf_ser *leaf;
+	unsigned int i;
+
+	if (unlikely(fls64(key) > KHO_MAP_KEY_WIDTH))
+		return 0;
+
+	for (i = KHO_MAP_DEPTH - 1; node && i > 0; i--)
+		node = KHOSER_LOAD_PTR(node->table[kho_map_node_idx(key, i)]);
+
+	if (!node)
+		return 0;
+
+	leaf = (struct kho_map_leaf_ser *)node;
+	return leaf->values[kho_map_node_idx(key, 0)];
+}
+
+static u64 __kho_map_next_leaf(struct kho_map_leaf_ser *leaf, u64 key, u64 *value)
+{
+	unsigned int i, idx;
+
+	idx = kho_map_node_idx(key, 0);
+
+	for (i = idx; i < KHO_MAP_TBL_ENTRIES; i++) {
+		if (!leaf->values[i])
+			continue;
+
+		key = (key & ~KHO_MAP_TBL_MASK) | i;
+		*value = leaf->values[i];
+		return key;
+	}
+
+	return U64_MAX;
+}
+
+static u64 __kho_map_next_node(struct kho_map_node_ser *node, u64 key, u64 *value,
+			       unsigned int level)
+{
+	/* Number of keys covered by a single entry at this level. */
+	u64 span = 1UL << (level * KHO_MAP_TBL_SHIFT);
+	unsigned int i;
+	u64 found;
+
+	/*
+	 * The first entry is searched starting from key. Every following
+	 * entry is searched from the first key of the subnode.
+	 */
+	for (i = kho_map_node_idx(key, level); i < KHO_MAP_TBL_ENTRIES;
+	     i++, key = round_down(key, span) + span) {
+		struct kho_map_node_ser *next;
+
+		next = KHOSER_LOAD_PTR(node->table[i]);
+		if (!next)
+			continue;
+
+		if (level == 1)
+			found = __kho_map_next_leaf((struct kho_map_leaf_ser *)next, key, value);
+		else
+			found = __kho_map_next_node(next, key, value, level - 1);
+
+		if (found != U64_MAX)
+			return found;
+	}
+
+	return U64_MAX;
+}
+
+/**
+ * kho_map_next() - Find the next entry in a KHO map.
+ * @map: The KHO map.
+ * @key: Key to start searching from.
+ * @value: Set to the value of the entry found. Left alone if none is found.
+ *
+ * Finds the entry with the smallest key that is greater than or equal to @key.
+ *
+ * Return: The key of the entry found, or %U64_MAX if there is none. %U64_MAX
+ * is never a valid key, since it is wider than %KHO_MAP_KEY_WIDTH.
+ */
+u64 kho_map_next(struct kho_map *map, u64 key, u64 *value)
+{
+	struct kho_map_node_ser *root = KHOSER_LOAD_PTR(map->ser->root);
+
+	if (unlikely(!root))
+		return U64_MAX;
+
+	if (unlikely(fls64(key) > KHO_MAP_KEY_WIDTH))
+		return U64_MAX;
+
+	return __kho_map_next_node(root, key, value, KHO_MAP_DEPTH - 1);
+}
-- 
2.56.0.611.g1030f0b940-goog



^ permalink raw reply related	[flat|nested] 6+ messages in thread

* [RFC PATCH 4/5] kho: test: add KHO map test
  2026-11-16 13:40 [RFC PATCH 0/5] KHO map Pratyush Yadav
                   ` (2 preceding siblings ...)
  2026-11-16 13:40 ` [RFC PATCH 3/5] kho: add KHO map Pratyush Yadav
@ 2026-11-16 13:40 ` Pratyush Yadav
  2026-11-16 13:40 ` [RFC PATCH 5/5] mm/memfd_luo: use KHO map for tracking folios Pratyush Yadav
  4 siblings, 0 replies; 6+ messages in thread
From: Pratyush Yadav @ 2026-11-16 13:40 UTC (permalink / raw)
  To: Mike Rapoport, Pasha Tatashin, Pratyush Yadav, Alexander Graf,
	Jonathan Corbet, Shuah Khan, Randy Dunlap, Andrew Morton,
	Tarun Sahu, David Matlack, Samiullah Khawaja
  Cc: kexec, linux-mm, linux-doc, linux-kernel, linux-kselftest

From: "Pratyush Yadav (Google)" <pratyush@kernel.org>

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.

Signed-off-by: Pratyush Yadav (Google) <pratyush@kernel.org>
---
 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

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 2d22638ec13a6..39e65b8a5290a 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -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:
diff --git a/lib/Makefile b/lib/Makefile
index a2afe954805cb..d3ab3f239e3ac 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -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
diff --git a/lib/test_kho_map.c b/lib/test_kho_map.c
new file mode 100644
index 0000000000000..16db26e380d50
--- /dev/null
+++ b/lib/test_kho_map.c
@@ -0,0 +1,575 @@
+// SPDX-License-Identifier: GPL-2.0
+
+/*
+ * Copyright (c) 2026, Google LLC.
+ * Pratyush Yadav <pratyush@kernel.org>
+ *
+ * Test for the KHO map. The first kernel runs basic tests on scratch trees,
+ * both unpreserved and preserved, then builds a tree and hands it over. The
+ * next kernel restores it, and checks its contents, and that it can then be
+ * modified and torn down like a locally built tree.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <linux/bits.h>
+#include <linux/err.h>
+#include <linux/init.h>
+#include <linux/io.h>
+#include <linux/kexec_handover.h>
+#include <linux/kho_map.h>
+#include <linux/mm.h>
+#include <linux/printk.h>
+#include <linux/sort.h>
+
+#define KHO_MAP_TEST_NAME	"kho_map_test"
+#define KHO_MAP_TEST_MAGIC	0x4b484f4d	/* KHOM */
+#define KHO_MAP_TEST_MAX_KEYS	32
+#define KHO_MAP_TEST_KEY_MAX	(BIT_ULL(KHO_MAP_KEY_WIDTH) - 1)
+
+struct kho_map_test_ser {
+	u64 magic;
+	struct kho_map_ser map_ser;
+};
+
+/* Never 0 for valid keys, so every generated key is present. */
+static u64 kho_map_test_value(u64 key)
+{
+	return ~key;
+}
+
+/*
+ * Fill @keys with sorted keys that sit on the boundaries of every level. With
+ * span being the number of keys covered by one entry at level l:
+ *
+ * - span - 1 and span are adjacent keys whose paths split at level l (last key
+ *   of entry 0, first key of entry 1). Walking from one to the other has to
+ *   cross a subtree boundary at exactly that level.
+ * - span * 3 + 5 skips the empty entry 2 at level l and lands on index 5 in the
+ *   leaf. This makes sure iteration correctly skips over empty subtrees and
+ *   leaves.
+ *
+ * Finally, also add the largest valid key to test the path that takes the last
+ * entry of each level.
+ *
+ * Return: number of keys.
+ */
+static unsigned int __init kho_map_test_gen_keys(u64 *keys)
+{
+	unsigned int l, n = 0;
+
+	for (l = 0; l < KHO_MAP_DEPTH; l++) {
+		u64 span = BIT_ULL(l * KHO_MAP_TBL_SHIFT);
+
+		keys[n++] = span - 1;
+		keys[n++] = span;
+		if (span * 3 + 5 < KHO_MAP_TEST_KEY_MAX)
+			keys[n++] = span * 3 + 5;
+	}
+	keys[n++] = KHO_MAP_TEST_KEY_MAX;
+
+	return n;
+}
+
+/*
+ * A key under entry 2 of the root and entry 7 of the leaf. None of the keys
+ * generated by kho_map_test_gen_keys() use it. So setting it needs a whole new
+ * path of nodes.
+ */
+static u64 __init kho_map_test_new_key(void)
+{
+	return BIT_ULL((KHO_MAP_DEPTH - 1) * KHO_MAP_TBL_SHIFT) * 2 + 7;
+}
+
+/* Check that @map has exactly @keys, in order, with the expected values. */
+static int __init kho_map_test_verify(struct kho_map *map, const u64 *keys,
+				      unsigned int n)
+{
+	unsigned int i = 0;
+	u64 key, value;
+
+	kho_map_for_each(map, key, value) {
+		if (i >= n) {
+			pr_err("unexpected key %#llx\n", key);
+			return -EINVAL;
+		}
+
+		if (key != keys[i] || value != kho_map_test_value(keys[i])) {
+			pr_err("entry %u: got %#llx = %#llx, expected %#llx = %#llx\n",
+			       i, key, value, keys[i], kho_map_test_value(keys[i]));
+			return -EINVAL;
+		}
+
+		/* Direct lookups must agree with iteration. */
+		if (kho_map_get(map, key) != value) {
+			pr_err("entry %u: kho_map_get(%#llx) = %#llx, expected %#llx\n",
+			       i, key, kho_map_get(map, key), value);
+			return -EINVAL;
+		}
+
+		i++;
+	}
+
+	if (i != n) {
+		pr_err("found %u keys, expected %u\n", i, n);
+		return -EINVAL;
+	}
+
+	return 0;
+}
+
+#define KHO_MAP_ASSERT_EQ(a, b)						\
+	do {								\
+		u64 __a = (a), __b = (b);				\
+									\
+		if (__a != __b) {					\
+			pr_err("%s:%d: %s == %#llx, expected %s == %#llx\n", \
+			       __func__, __LINE__, #a, __a, #b, __b);	\
+			return -EINVAL;					\
+		}							\
+	} while (0)
+
+static int __init kho_map_test_populate(struct kho_map *map, const u64 *keys,
+					unsigned int n)
+{
+	unsigned int i;
+
+	for (i = 0; i < n; i++)
+		KHO_MAP_ASSERT_EQ(kho_map_set(map, keys[i],
+					      kho_map_test_value(keys[i])), 0);
+
+	return 0;
+}
+
+static unsigned long __init
+__kho_map_test_count_nodes(struct kho_map_node_ser *node, unsigned int level)
+{
+	unsigned long count = 1;
+	unsigned int i;
+
+	if (level == 0)
+		return count;
+
+	for (i = 0; i < KHO_MAP_TBL_ENTRIES; i++) {
+		struct kho_map_node_ser *next = KHOSER_LOAD_PTR(node->table[i]);
+
+		if (next)
+			count += __kho_map_test_count_nodes(next, level - 1);
+	}
+
+	return count;
+}
+
+/* Number of nodes (including leaves) currently allocated for @map. */
+static unsigned long __init kho_map_test_count_nodes(struct kho_map *map)
+{
+	struct kho_map_node_ser *root = KHOSER_LOAD_PTR(map->ser->root);
+
+	if (!root)
+		return 0;
+
+	return __kho_map_test_count_nodes(root, KHO_MAP_DEPTH - 1);
+}
+
+/* An empty tree has no entries, and clearing a key in it allocates nothing. */
+static int __init kho_map_test_empty(struct kho_map *map)
+{
+	u64 value;
+
+	KHO_MAP_ASSERT_EQ(kho_map_next(map, 0, &value), U64_MAX);
+
+	kho_map_clear(map, 5);
+	KHO_MAP_ASSERT_EQ(kho_map_test_count_nodes(map), 0);
+
+	return 0;
+}
+
+/*
+ * A single key can be found again with its value, by lookup and by iteration,
+ * neighbouring keys have no entry, and it takes exactly one node per level.
+ */
+static int __init kho_map_test_set_get(struct kho_map *map)
+{
+	u64 value = 0;
+
+	KHO_MAP_ASSERT_EQ(kho_map_get(map, 42), 0);
+	KHO_MAP_ASSERT_EQ(kho_map_set(map, 42, 0xdead), 0);
+
+	KHO_MAP_ASSERT_EQ(kho_map_get(map, 42), 0xdead);
+	KHO_MAP_ASSERT_EQ(kho_map_get(map, 41), 0);
+	KHO_MAP_ASSERT_EQ(kho_map_get(map, 43), 0);
+
+	KHO_MAP_ASSERT_EQ(kho_map_next(map, 0, &value), 42);
+	KHO_MAP_ASSERT_EQ(value, 0xdead);
+	KHO_MAP_ASSERT_EQ(kho_map_next(map, 43, &value), U64_MAX);
+
+	/* A single key needs exactly one node per level. */
+	KHO_MAP_ASSERT_EQ(kho_map_test_count_nodes(map), KHO_MAP_DEPTH);
+
+	return 0;
+}
+
+/*
+ * The smallest and largest valid keys work, keys past the maximum are rejected
+ * by kho_map_set() and ignored by kho_map_clear(), kho_map_get() and
+ * kho_map_next().
+ */
+static int __init kho_map_test_key_range(struct kho_map *map)
+{
+	u64 value = 0;
+
+	KHO_MAP_ASSERT_EQ(kho_map_set(map, 0, 1), 0);
+	KHO_MAP_ASSERT_EQ(kho_map_set(map, KHO_MAP_TEST_KEY_MAX, 2), 0);
+	KHO_MAP_ASSERT_EQ(kho_map_set(map, KHO_MAP_TEST_KEY_MAX + 1, 3), -ERANGE);
+
+	/* Out of range clear is ignored. */
+	kho_map_clear(map, KHO_MAP_TEST_KEY_MAX + 1);
+
+	KHO_MAP_ASSERT_EQ(kho_map_get(map, 0), 1);
+	KHO_MAP_ASSERT_EQ(kho_map_get(map, KHO_MAP_TEST_KEY_MAX), 2);
+	KHO_MAP_ASSERT_EQ(kho_map_get(map, KHO_MAP_TEST_KEY_MAX + 1), 0);
+
+	KHO_MAP_ASSERT_EQ(kho_map_next(map, 0, &value), 0);
+	KHO_MAP_ASSERT_EQ(value, 1);
+	KHO_MAP_ASSERT_EQ(kho_map_next(map, 1, &value), KHO_MAP_TEST_KEY_MAX);
+	KHO_MAP_ASSERT_EQ(value, 2);
+	KHO_MAP_ASSERT_EQ(kho_map_next(map, KHO_MAP_TEST_KEY_MAX + 1, &value),
+			  U64_MAX);
+
+	return 0;
+}
+
+/*
+ * kho_map_for_each() returns keys on the boundaries of every level in sorted
+ * order, regardless of insertion order.
+ */
+static int __init kho_map_test_order_all_levels(struct kho_map *map)
+{
+	u64 keys[KHO_MAP_TEST_MAX_KEYS];
+	unsigned int n, i;
+
+	n = kho_map_test_gen_keys(keys);
+
+	/* Insert in reverse, so the order can only come from the tree. */
+	for (i = n; i > 0; i--)
+		KHO_MAP_ASSERT_EQ(kho_map_set(map, keys[i - 1],
+					      kho_map_test_value(keys[i - 1])), 0);
+
+	return kho_map_test_verify(map, keys, n);
+}
+
+/*
+ * kho_map_next() finds a key when started exactly on it, and when started just
+ * after it, skips the empty range up to the next key, across subtree
+ * boundaries at every level.
+ */
+static int __init kho_map_test_next_from_middle(struct kho_map *map)
+{
+	u64 keys[KHO_MAP_TEST_MAX_KEYS];
+	unsigned int n, i;
+	u64 value;
+	int err;
+
+	n = kho_map_test_gen_keys(keys);
+	err = kho_map_test_populate(map, keys, n);
+	if (err)
+		return err;
+
+	for (i = 0; i < n; i++) {
+		u64 next = i + 1 < n ? keys[i + 1] : U64_MAX;
+
+		KHO_MAP_ASSERT_EQ(kho_map_next(map, keys[i], &value), keys[i]);
+		/* Skips over everything up to the next key. */
+		KHO_MAP_ASSERT_EQ(kho_map_next(map, keys[i] + 1, &value), next);
+	}
+
+	return 0;
+}
+
+/*
+ * Setting an existing key replaces its value, and clearing a key (even twice)
+ * removes it. Clearing frees the nodes that become empty, and only those.
+ */
+static int __init kho_map_test_overwrite_clear(struct kho_map *map)
+{
+	u64 value = 0;
+
+	/* Set the same key multiple times. */
+	KHO_MAP_ASSERT_EQ(kho_map_set(map, 10, 1), 0);
+	KHO_MAP_ASSERT_EQ(kho_map_set(map, 10, 2), 0);
+	KHO_MAP_ASSERT_EQ(kho_map_next(map, 0, &value), 10);
+	KHO_MAP_ASSERT_EQ(value, 2);
+
+	/* Add a key in the next leaf so it shares every node except the leaf. */
+	KHO_MAP_ASSERT_EQ(kho_map_set(map, 10 + KHO_MAP_TBL_ENTRIES, 3), 0);
+	KHO_MAP_ASSERT_EQ(kho_map_test_count_nodes(map), KHO_MAP_DEPTH + 1);
+
+	/* Clearing it frees its leaf, but not the shared nodes. */
+	kho_map_clear(map, 10 + KHO_MAP_TBL_ENTRIES);
+	KHO_MAP_ASSERT_EQ(kho_map_test_count_nodes(map), KHO_MAP_DEPTH);
+	KHO_MAP_ASSERT_EQ(kho_map_get(map, 10), 2);
+
+	/* A leaf that still has entries is not freed. */
+	KHO_MAP_ASSERT_EQ(kho_map_set(map, 11, 4), 0);
+	kho_map_clear(map, 11);
+	KHO_MAP_ASSERT_EQ(kho_map_test_count_nodes(map), KHO_MAP_DEPTH);
+
+	kho_map_clear(map, 10);
+	/* Clearing twice is fine. */
+	kho_map_clear(map, 10);
+
+	KHO_MAP_ASSERT_EQ(kho_map_next(map, 0, &value), U64_MAX);
+	KHO_MAP_ASSERT_EQ(kho_map_get(map, 10), 0);
+
+	/* The last entry is gone, so the whole tree is freed. */
+	KHO_MAP_ASSERT_EQ(kho_map_test_count_nodes(map), 0);
+
+	/* The tree can be populated again after it was emptied. */
+	KHO_MAP_ASSERT_EQ(kho_map_set(map, 10, 5), 0);
+	KHO_MAP_ASSERT_EQ(kho_map_get(map, 10), 5);
+	KHO_MAP_ASSERT_EQ(kho_map_test_count_nodes(map), KHO_MAP_DEPTH);
+
+	return 0;
+}
+
+/*
+ * kho_map_destroy() frees every node, after which the tree can be initialized
+ * again with kho_map_init(), populated and used like a new one.
+ */
+static int __init kho_map_test_destroy_reuse(struct kho_map *map)
+{
+	bool preserved = map->preserved;
+	u64 keys[KHO_MAP_TEST_MAX_KEYS];
+	unsigned int n;
+	u64 value;
+	int err;
+
+	n = kho_map_test_gen_keys(keys);
+	err = kho_map_test_populate(map, keys, n);
+	if (err)
+		return err;
+
+	kho_map_destroy(map);
+
+	/* Re-initialize, and preserve again if the harness preserved it. */
+	kho_map_init(map, map->ser);
+	if (preserved) {
+		err = kho_map_preserve(map);
+		if (err)
+			return err;
+	}
+
+	KHO_MAP_ASSERT_EQ(kho_map_test_count_nodes(map), 0);
+	KHO_MAP_ASSERT_EQ(kho_map_next(map, 0, &value), U64_MAX);
+
+	err = kho_map_test_populate(map, keys, n);
+	if (err)
+		return err;
+
+	return kho_map_test_verify(map, keys, n);
+}
+
+#define KHO_MAP_TEST(name)	{ #name, kho_map_test_##name }
+
+struct kho_map_test {
+	const char *name;
+	int (*fn)(struct kho_map *map);
+};
+
+static const struct kho_map_test kho_map_tests[] __initconst = {
+	KHO_MAP_TEST(empty),
+	KHO_MAP_TEST(set_get),
+	KHO_MAP_TEST(key_range),
+	KHO_MAP_TEST(order_all_levels),
+	KHO_MAP_TEST(next_from_middle),
+	KHO_MAP_TEST(overwrite_clear),
+	KHO_MAP_TEST(destroy_reuse),
+};
+
+/*
+ * Run the tests that only need the current kernel, each on a fresh tree. With
+ * @preserve, the tree is preserved before the test runs, so nodes get preserved
+ * on allocation and unpreserved on destruction.
+ */
+static int __init kho_map_test_basic(bool preserve)
+{
+	unsigned int i;
+	int err;
+
+	for (i = 0; i < ARRAY_SIZE(kho_map_tests); i++) {
+		struct kho_map_ser map_ser;
+		struct kho_map map;
+
+		kho_map_init(&map, &map_ser);
+		err = preserve ? kho_map_preserve(&map) : 0;
+		if (!err)
+			err = kho_map_tests[i].fn(&map);
+		kho_map_destroy(&map);
+
+		if (err) {
+			pr_err("test %s (%spreserved) failed: %d\n",
+			       kho_map_tests[i].name, preserve ? "" : "un", err);
+			return err;
+		}
+	}
+
+	return 0;
+}
+
+static int __init kho_map_test_save(void)
+{
+	u64 keys[KHO_MAP_TEST_MAX_KEYS];
+	struct kho_map_test_ser *ser;
+	struct kho_map map;
+	unsigned int n, i;
+	int err;
+
+	ser = kho_alloc_preserve(sizeof(*ser));
+	if (IS_ERR(ser))
+		return PTR_ERR(ser);
+
+	ser->magic = KHO_MAP_TEST_MAGIC;
+	kho_map_init(&map, &ser->map_ser);
+
+	/*
+	 * Add half the keys before preserving the tree and half after, so both
+	 * kho_map_preserve() walking existing nodes and nodes preserved on
+	 * allocation are exercised. The next kernel can only restore the tree
+	 * if every node got preserved.
+	 */
+	n = kho_map_test_gen_keys(keys);
+	for (i = 0; i < n; i++) {
+		if (i == n / 2) {
+			err = kho_map_preserve(&map);
+			if (err)
+				goto err_destroy;
+		}
+
+		err = kho_map_set(&map, keys[i], kho_map_test_value(keys[i]));
+		if (err)
+			goto err_destroy;
+	}
+
+	err = kho_map_test_verify(&map, keys, n);
+	if (err)
+		goto err_destroy;
+
+	err = kho_add_subtree(KHO_MAP_TEST_NAME, ser, sizeof(*ser));
+	if (err)
+		goto err_destroy;
+
+	return 0;
+
+err_destroy:
+	kho_map_destroy(&map);
+	kho_unpreserve_free(ser);
+	return err;
+}
+
+static int __init kho_map_test_cmp_key(const void *a, const void *b)
+{
+	return cmp_int(*(const u64 *)a, *(const u64 *)b);
+}
+
+static int __init kho_map_test_restore(phys_addr_t phys)
+{
+	struct kho_map_test_ser *ser = phys_to_virt(phys);
+	u64 keys[KHO_MAP_TEST_MAX_KEYS];
+	u64 new_key = kho_map_test_new_key();
+	struct kho_map map;
+	struct folio *folio;
+	unsigned int n;
+	int err;
+
+	if (ser->magic != KHO_MAP_TEST_MAGIC)
+		return -EINVAL;
+
+	n = kho_map_test_gen_keys(keys);
+
+	folio = kho_restore_folio(phys);
+	if (!folio)
+		return -EINVAL;
+
+	err = kho_map_restore(&map, &ser->map_ser);
+	if (err)
+		goto out_put;
+
+	err = kho_map_test_verify(&map, keys, n);
+	if (err)
+		goto out_destroy;
+
+	/*
+	 * Restored nodes must behave like normal: add a key on a new path and
+	 * clear an existing one. The restored tree is unpreserved, so the new
+	 * nodes are not preserved.
+	 */
+	err = kho_map_set(&map, new_key, kho_map_test_value(new_key));
+	if (err)
+		goto out_destroy;
+	kho_map_clear(&map, keys[0]);
+
+	/* keys[0] is gone and new_key took its place. */
+	keys[0] = new_key;
+	/* kho_map_test_verify() expects sorted keys. */
+	sort(keys, n, sizeof(*keys), kho_map_test_cmp_key, NULL);
+
+	err = kho_map_test_verify(&map, keys, n);
+	if (err)
+		goto out_destroy;
+
+	/*
+	 * A restored tree can be preserved again, which preserves both restored
+	 * and new nodes, and kho_map_destroy() then unpreserves them.
+	 */
+	err = kho_map_preserve(&map);
+
+out_destroy:
+	kho_map_destroy(&map);
+out_put:
+	folio_put(folio);
+	return err;
+}
+
+static int __init kho_map_test_init(void)
+{
+	phys_addr_t phys;
+	int err;
+
+	if (!kho_is_enabled())
+		return 0;
+
+	err = kho_retrieve_subtree(KHO_MAP_TEST_NAME, &phys, NULL);
+	if (!err) {
+		err = kho_map_test_restore(phys);
+		if (err)
+			pr_err("KHO map restore failed: %d\n", err);
+		else
+			pr_info("KHO map restore succeeded\n");
+
+		return err;
+	}
+
+	if (err != -ENOENT) {
+		pr_warn("failed to retrieve %s: %d\n", KHO_MAP_TEST_NAME, err);
+		return err;
+	}
+
+	/*
+	 * Run basic tests first. If they fail, no point in doing a handover
+	 * test.
+	 */
+	err = kho_map_test_basic(false);
+	if (!err)
+		err = kho_map_test_basic(true);
+	if (err) {
+		pr_err("KHO map basic tests failed: %d\n", err);
+		return err;
+	}
+
+	err = kho_map_test_save();
+	if (err)
+		pr_err("KHO map save failed: %d\n", err);
+
+	return err;
+}
+late_initcall(kho_map_test_init);
diff --git a/tools/testing/selftests/kho/vmtest.sh b/tools/testing/selftests/kho/vmtest.sh
index 1e86ffcc3a79e..03a1a1f55299f 100755
--- a/tools/testing/selftests/kho/vmtest.sh
+++ b/tools/testing/selftests/kho/vmtest.sh
@@ -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() {
-- 
2.56.0.611.g1030f0b940-goog



^ permalink raw reply related	[flat|nested] 6+ messages in thread

* [RFC PATCH 5/5] mm/memfd_luo: use KHO map for tracking folios
  2026-11-16 13:40 [RFC PATCH 0/5] KHO map Pratyush Yadav
                   ` (3 preceding siblings ...)
  2026-11-16 13:40 ` [RFC PATCH 4/5] kho: test: add KHO map test Pratyush Yadav
@ 2026-11-16 13:40 ` Pratyush Yadav
  4 siblings, 0 replies; 6+ messages in thread
From: Pratyush Yadav @ 2026-11-16 13:40 UTC (permalink / raw)
  To: Mike Rapoport, Pasha Tatashin, Pratyush Yadav, Alexander Graf,
	Jonathan Corbet, Shuah Khan, Randy Dunlap, Andrew Morton,
	Tarun Sahu, David Matlack, Samiullah Khawaja
  Cc: kexec, linux-mm, linux-doc, linux-kernel, linux-kselftest

From: "Pratyush Yadav (Google)" <pratyush@kernel.org>

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".

Signed-off-by: Pratyush Yadav (Google) <pratyush@kernel.org>
---
 include/linux/kho/abi/memfd.h |  39 +++--
 mm/memfd_luo.c                | 292 +++++++++++++++-------------------
 2 files changed, 151 insertions(+), 180 deletions(-)

diff --git a/include/linux/kho/abi/memfd.h b/include/linux/kho/abi/memfd.h
index 08b10fea2afc8..b17ada3af7abb 100644
--- a/include/linux/kho/abi/memfd.h
+++ b/include/linux/kho/abi/memfd.h
@@ -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 */
diff --git a/mm/memfd_luo.c b/mm/memfd_luo.c
index 50dbbda47ad3c..26cdb41f40532 100644
--- a/mm/memfd_luo.c
+++ b/mm/memfd_luo.c
@@ -84,31 +84,25 @@
 #include <linux/io.h>
 #include <linux/kexec_handover.h>
 #include <linux/kho/abi/memfd.h>
+#include <linux/kho_map.h>
 #include <linux/liveupdate.h>
 #include <linux/migrate.h>
 #include <linux/sched/mm.h>
 #include <linux/sched/signal.h>
 #include <linux/shmem_fs.h>
 #include <linux/swap.h>
-#include <linux/vmalloc.h>
 #include <linux/memfd.h>
 #include <uapi/linux/memfd.h>
 
 #include "internal.h"
 
-static void memfd_luo_put_folios(const struct memfd_luo_folio_ser *folios_ser,
-				 u64 nr_folios)
+static void memfd_luo_put_folios(struct kho_map *map)
 {
-	u64 i;
+	union memfd_luo_folio_ser entry;
+	u64 index;
 
-	for (i = 0; i < nr_folios; i++) {
-		const struct memfd_luo_folio_ser *pfolio = &folios_ser[i];
-		struct folio *folio;
-
-		if (!pfolio->pfn)
-			continue;
-
-		folio = pfn_folio(pfolio->pfn);
+	kho_map_for_each(map, index, entry.val) {
+		struct folio *folio = pfn_folio(entry.pfn);
 
 		kho_unpreserve_folio(folio);
 		folio_put(folio);
@@ -190,9 +184,9 @@ static int memfd_luo_get_folio(struct inode *inode, pgoff_t index,
 	return 0;
 }
 
-static int memfd_luo_preserve_folio(struct folio *folio,
-				    struct memfd_luo_folio_ser *pfolio)
+static int memfd_luo_preserve_folio(struct folio *folio, struct kho_map *map)
 {
+	union memfd_luo_folio_ser entry = {};
 	int err;
 
 	err = kho_preserve_folio(folio);
@@ -210,7 +204,7 @@ static int memfd_luo_preserve_folio(struct folio *folio,
 	 * might still be a mapping of the file at freeze().
 	 *
 	 * To see why this is a problem, say a folio is clean at
-	 * preserve, but gets dirtied later. The pfolio flags will mark
+	 * preserve, but gets dirtied later. The preserved flags will mark
 	 * it as clean. After retrieve, the next kernel might try to
 	 * reclaim this folio under memory pressure, losing user data.
 	 *
@@ -220,46 +214,31 @@ static int memfd_luo_preserve_folio(struct folio *folio,
 	 */
 	folio_mark_dirty(folio);
 
-	pfolio->pfn = folio_pfn(folio);
-	pfolio->flags = MEMFD_LUO_FOLIO_DIRTY | MEMFD_LUO_FOLIO_UPTODATE;
-	pfolio->index = folio->index;
+	entry.pfn = folio_pfn(folio);
+	entry.flags = MEMFD_LUO_FOLIO_DIRTY | MEMFD_LUO_FOLIO_UPTODATE;
+	err = kho_map_set(map, folio->index, entry.val);
+	if (err) {
+		kho_unpreserve_folio(folio);
+		return err;
+	}
 
 	return 0;
 }
 
-static int memfd_luo_preserve_folios(struct file *file,
-				     struct kho_vmalloc *kho_vmalloc,
-				     struct memfd_luo_folio_ser **out_folios_ser,
-				     u64 *nr_foliosp)
+static int memfd_luo_preserve_folios(struct file *file, struct kho_map *map)
 {
-	struct memfd_luo_folio_ser *folios_ser, *shrunk;
 	struct inode *inode = file_inode(file);
-	u64 nr_folios = 0, max_folios;
 	unsigned int pin_flags;
 	pgoff_t index = 0, end;
 	int err;
 	loff_t size;
 
 	size = i_size_read(inode);
-	/*
-	 * If the file has zero size, then the folios and nr_folios properties
-	 * are not set.
-	 */
-	if (!size) {
-		*nr_foliosp = 0;
-		*out_folios_ser = NULL;
+	/* If the file has zero size, then the folios map is left empty. */
+	if (!size)
 		return 0;
-	}
 
-	/*
-	 * Guess the number of folios based on inode size. Real number might end
-	 * up being smaller if there are higher order folios.
-	 */
 	end = DIV_ROUND_UP_ULL(size, PAGE_SIZE);
-	max_folios = end;
-	folios_ser = vmalloc_array(max_folios, sizeof(*folios_ser));
-	if (!folios_ser)
-		return -ENOMEM;
 
 	/*
 	 * The folios are held until the next kernel, so keep newly allocated
@@ -281,75 +260,41 @@ static int memfd_luo_preserve_folios(struct file *file,
 			goto err_restore;
 		}
 
-		if (WARN_ON_ONCE(nr_folios >= max_folios)) {
-			err = -EINVAL;
-			goto err_restore;
-		}
-
 		err = memfd_luo_get_folio(inode, index, &folio);
 		if (err)
 			goto err_restore;
 
-		err = memfd_luo_preserve_folio(folio, &folios_ser[nr_folios]);
+		err = memfd_luo_preserve_folio(folio, map);
 		index = folio_next_index(folio);
 		folio_unlock(folio);
 		if (err) {
 			folio_put(folio);
 			goto err_restore;
 		}
-		nr_folios++;
 	}
 	memalloc_pin_restore(pin_flags);
 
-	/*
-	 * Free the unused tail so it doesn't get preserved. If vrealloc fails,
-	 * the folios_ser is still valid.
-	 */
-	shrunk = vrealloc(folios_ser, array_size(nr_folios, sizeof(*folios_ser)),
-			  GFP_KERNEL);
-	if (shrunk)
-		folios_ser = shrunk;
-
-	err = kho_preserve_vmalloc(folios_ser, kho_vmalloc);
-	if (err)
-		goto err_put;
-
-	*nr_foliosp = nr_folios;
-	*out_folios_ser = folios_ser;
-
-	/*
-	 * Note: folios_ser is purposely not freed here. It is preserved
-	 * memory (via KHO). In the 'unpreserve' path, we use the vmap pointer
-	 * that is passed via private_data.
-	 */
 	return 0;
 
 err_restore:
 	memalloc_pin_restore(pin_flags);
-err_put:
-	memfd_luo_put_folios(folios_ser, nr_folios);
-	vfree(folios_ser);
+	memfd_luo_put_folios(map);
+	kho_map_destroy(map);
 	return err;
 }
 
-static void memfd_luo_unpreserve_folios(struct kho_vmalloc *kho_vmalloc,
-					struct memfd_luo_folio_ser *folios_ser,
-					u64 nr_folios)
+static void memfd_luo_unpreserve_folios(struct kho_map *map)
 {
-	if (!nr_folios)
-		return;
-
-	kho_unpreserve_vmalloc(kho_vmalloc);
-	memfd_luo_put_folios(folios_ser, nr_folios);
-	vfree(folios_ser);
+	memfd_luo_put_folios(map);
+	kho_map_destroy(map);
 }
 
 static int memfd_luo_preserve(struct liveupdate_file_op_args *args)
 {
 	struct inode *inode = file_inode(args->file);
-	struct memfd_luo_folio_ser *folios_ser;
 	struct memfd_luo_ser *ser;
-	u64 nr_folios, inode_size;
+	struct kho_map *folios;
+	u64 inode_size;
 	int err = 0, seals;
 
 	inode_lock(inode);
@@ -380,19 +325,38 @@ static int memfd_luo_preserve(struct liveupdate_file_op_args *args)
 	ser->size = inode_size;
 	ser->seals = seals;
 
-	err = memfd_luo_preserve_folios(args->file, &ser->folios,
-					&folios_ser, &nr_folios);
-	if (err)
+	/*
+	 * The runtime handle of the folios map is needed until unpreserve(),
+	 * so keep it in private_data.
+	 */
+	folios = kmalloc_obj(*folios);
+	if (!folios) {
+		err = -ENOMEM;
 		goto err_free_ser;
+	}
+
+	kho_map_init(folios, &ser->folios);
+	/*
+	 * Preserve the empty tree right away, so every node allocated for the
+	 * tree is auto-preserved.
+	 */
+	err = kho_map_preserve(folios);
+	if (err)
+		goto err_free_folios;
+
+	err = memfd_luo_preserve_folios(args->file, folios);
+	if (err)
+		goto err_free_folios;
 
-	ser->nr_folios = nr_folios;
 	inode_unlock(inode);
 
-	args->private_data = folios_ser;
 	args->serialized_data = virt_to_phys(ser);
+	args->private_data = folios;
 
 	return 0;
 
+err_free_folios:
+	kfree(folios);
 err_free_ser:
 	kho_unpreserve_free(ser);
 err_unlock:
@@ -432,27 +396,26 @@ static void memfd_luo_unpreserve(struct liveupdate_file_op_args *args)
 
 	ser = phys_to_virt(args->serialized_data);
 
-	memfd_luo_unpreserve_folios(&ser->folios, args->private_data,
-				    ser->nr_folios);
+	memfd_luo_unpreserve_folios(args->private_data);
+	kfree(args->private_data);
 
 	kho_unpreserve_free(ser);
 	inode_unlock(inode);
 }
 
-static void memfd_luo_discard_folios(const struct memfd_luo_folio_ser *folios_ser,
-				     u64 nr_folios)
+/*
+ * Restore and free all folios in @map with keys starting from @start. @map must
+ * already be restored.
+ */
+static void memfd_luo_discard_folios(struct kho_map *map, u64 start)
 {
-	u64 i;
+	union memfd_luo_folio_ser entry;
+	u64 index;
 
-	for (i = 0; i < nr_folios; i++) {
-		const struct memfd_luo_folio_ser *pfolio = &folios_ser[i];
+	kho_map_for_each_from(map, index, entry.val, start) {
+		phys_addr_t phys = PFN_PHYS(entry.pfn);
 		struct folio *folio;
-		phys_addr_t phys;
 
-		if (!pfolio->pfn)
-			continue;
-
-		phys = PFN_PHYS(pfolio->pfn);
 		folio = kho_restore_folio(phys);
 		if (!folio) {
 			pr_warn_ratelimited("Unable to restore folio at physical address: %llx\n",
@@ -464,22 +427,25 @@ static void memfd_luo_discard_folios(const struct memfd_luo_folio_ser *folios_se
 	}
 }
 
-/* Drop the references retrieve() holds on the folios added to the file. */
-static void
-memfd_luo_put_retrieved_folios(const struct memfd_luo_folio_ser *folios_ser,
-			       u64 nr_folios)
+/*
+ * Drop the references retrieve() holds on the folios added to the file, i.e.
+ * the folios in @map with keys below @end.
+ */
+static void memfd_luo_put_retrieved_folios(struct kho_map *map, u64 end)
 {
-	for (u64 i = 0; i < nr_folios; i++) {
-		const struct memfd_luo_folio_ser *pfolio = &folios_ser[i];
+	union memfd_luo_folio_ser entry;
+	u64 index;
 
-		if (pfolio->pfn)
-			folio_put(pfn_folio(pfolio->pfn));
+	kho_map_for_each(map, index, entry.val) {
+		if (index >= end)
+			break;
+
+		folio_put(pfn_folio(entry.pfn));
 	}
 }
 
 static void memfd_luo_finish(struct liveupdate_file_op_args *args)
 {
-	struct memfd_luo_folio_ser *folios_ser;
 	struct memfd_luo_ser *ser;
 
 	/* If retrieve failed, it already cleaned up everything it could. */
@@ -496,48 +462,51 @@ static void memfd_luo_finish(struct liveupdate_file_op_args *args)
 		 * file so it can be used normally.
 		 */
 		struct inode *inode = file_inode(args->file);
-
-		folios_ser = args->private_data;
+		struct kho_map *retrieved = args->private_data;
 
 		inode_lock(inode);
-		memfd_luo_put_retrieved_folios(folios_ser, ser->nr_folios);
+		memfd_luo_put_retrieved_folios(retrieved, U64_MAX);
 		shmem_freeze(inode, false);
 		inode_unlock(inode);
 
-		vfree(folios_ser);
-	} else if (args->retrieve_status == 0 && ser->nr_folios) {
+		kho_map_destroy(retrieved);
+		kfree(retrieved);
+	} else {
 		/* Retrieve was not called, discard the preserved folios. */
-		folios_ser = kho_restore_vmalloc(&ser->folios);
-		if (folios_ser) {
-			memfd_luo_discard_folios(folios_ser, ser->nr_folios);
-			vfree(folios_ser);
+		struct kho_map folios;
+
+		if (kho_map_restore(&folios, &ser->folios)) {
+			pr_warn("Unable to restore folios map\n");
+			goto out;
 		}
+
+		memfd_luo_discard_folios(&folios, 0);
+		kho_map_destroy(&folios);
 	}
 
+out:
 	kho_restore_free(ser);
 }
 
-static int memfd_luo_retrieve_folios(struct file *file,
-				     struct memfd_luo_folio_ser *folios_ser,
-				     u64 nr_folios)
+/*
+ * Add the folios in @folios to @file. @folios must already be restored. On
+ * success, a reference is kept on each added folio, which is dropped in
+ * finish(). On failure, everything is cleaned up except @folios itself.
+ */
+static int memfd_luo_retrieve_folios(struct file *file, struct kho_map *folios)
 {
 	struct inode *inode = file_inode(file);
 	struct address_space *mapping = inode->i_mapping;
-	struct folio *folio;
 	long npages, nr_added_pages = 0;
+	union memfd_luo_folio_ser entry;
+	struct folio *folio;
 	int err = -EIO;
-	long i;
+	u64 index;
 
-	for (i = 0; i < nr_folios; i++) {
-		const struct memfd_luo_folio_ser *pfolio = &folios_ser[i];
-		phys_addr_t phys;
-		u64 index;
-		int flags;
+	kho_map_for_each(folios, index, entry.val) {
+		phys_addr_t phys = PFN_PHYS(entry.pfn);
+		unsigned long flags = entry.flags;
 
-		if (!pfolio->pfn)
-			continue;
-
-		phys = PFN_PHYS(pfolio->pfn);
 		folio = kho_restore_folio(phys);
 		if (!folio) {
 			pr_err("Unable to restore folio at physical address: %llx\n",
@@ -545,8 +514,6 @@ static int memfd_luo_retrieve_folios(struct file *file,
 			err = -EIO;
 			goto put_folios;
 		}
-		index = pfolio->index;
-		flags = pfolio->flags;
 
 		/* Set up the folio for insertion. */
 		__folio_set_locked(folio);
@@ -554,16 +521,16 @@ static int memfd_luo_retrieve_folios(struct file *file,
 
 		err = mem_cgroup_charge(folio, NULL, mapping_gfp_mask(mapping));
 		if (err) {
-			pr_err("shmem: failed to charge folio index %ld: %d\n",
-			       i, err);
+			pr_err("shmem: failed to charge folio index %llu: %d\n",
+			       index, err);
 			goto unlock_folio;
 		}
 
 		err = shmem_add_to_page_cache(folio, mapping, index, NULL,
 					      mapping_gfp_mask(mapping));
 		if (err) {
-			pr_err("shmem: failed to add to page cache folio index %ld: %d\n",
-			       i, err);
+			pr_err("shmem: failed to add to page cache folio index %llu: %d\n",
+			       index, err);
 			goto unlock_folio;
 		}
 
@@ -575,8 +542,8 @@ static int memfd_luo_retrieve_folios(struct file *file,
 		npages = folio_nr_pages(folio);
 		err = shmem_inode_acct_blocks(inode, npages);
 		if (err) {
-			pr_err("shmem: failed to account folio index %ld(%ld pages): %d\n",
-			       i, npages, err);
+			pr_err("shmem: failed to account folio index %llu(%ld pages): %d\n",
+			       index, npages, err);
 			goto remove_from_cache;
 		}
 
@@ -603,21 +570,10 @@ static int memfd_luo_retrieve_folios(struct file *file,
 	 * Drop the references held on the folios already added to the file.
 	 * The folios themselves will be freed when the file is freed.
 	 */
-	memfd_luo_put_retrieved_folios(folios_ser, i);
+	memfd_luo_put_retrieved_folios(folios, index);
 
 	/* Free the ones not added yet here. */
-	for (long j = i + 1; j < nr_folios; j++) {
-		const struct memfd_luo_folio_ser *pfolio = &folios_ser[j];
-		phys_addr_t phys;
-
-		if (!pfolio->pfn)
-			continue;
-
-		phys = PFN_PHYS(pfolio->pfn);
-		folio = kho_restore_folio(phys);
-		if (folio)
-			folio_put(folio);
-	}
+	memfd_luo_discard_folios(folios, index + 1);
 
 	shmem_recalc_inode(inode, nr_added_pages, 0);
 
@@ -626,8 +582,8 @@ static int memfd_luo_retrieve_folios(struct file *file,
 
 static int memfd_luo_retrieve(struct liveupdate_file_op_args *args)
 {
-	struct memfd_luo_folio_ser *folios_ser = NULL;
 	struct memfd_luo_ser *ser;
+	struct kho_map *folios;
 	struct file *file;
 	int err;
 
@@ -672,25 +628,31 @@ static int memfd_luo_retrieve(struct liveupdate_file_op_args *args)
 	shmem_freeze(file_inode(file), true);
 	inode_unlock(file_inode(file));
 
-	if (ser->nr_folios) {
-		folios_ser = kho_restore_vmalloc(&ser->folios);
-		if (!folios_ser) {
-			err = -EINVAL;
-			goto put_file;
-		}
+	folios = kmalloc_obj(*folios);
+	if (!folios) {
+		err = -ENOMEM;
+		goto put_file;
+	}
 
-		err = memfd_luo_retrieve_folios(file, folios_ser, ser->nr_folios);
-		if (err)
-			goto free_folios_ser;
+	err = kho_map_restore(folios, &ser->folios);
+	if (err) {
+		pr_err("failed to restore folios map: %pe\n", ERR_PTR(err));
+		goto free_folios;
 	}
 
+	err = memfd_luo_retrieve_folios(file, folios);
+	if (err)
+		goto destroy_folios;
+
 	args->file = file;
-	args->private_data = folios_ser;
+	args->private_data = folios;
 
 	return 0;
 
-free_folios_ser:
-	vfree(folios_ser);
+destroy_folios:
+	kho_map_destroy(folios);
+free_folios:
+	kfree(folios);
 put_file:
 	fput(file);
 free_ser:
-- 
2.56.0.611.g1030f0b940-goog



^ permalink raw reply related	[flat|nested] 6+ messages in thread

end of thread, other threads:[~2026-11-16 13:40 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-16 13:40 [RFC PATCH 0/5] KHO map Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 1/5] kho: add KHOSER_CLEAR_PTR() Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 2/5] kho: build KHO objects into a single kho.o Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 3/5] kho: add KHO map Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 4/5] kho: test: add KHO map test Pratyush Yadav
2026-11-16 13:40 ` [RFC PATCH 5/5] mm/memfd_luo: use KHO map for tracking folios Pratyush Yadav

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox