Linux Documentation
 help / color / mirror / Atom feed
From: Pratyush Yadav <pratyush@kernel.org>
To: Mike Rapoport <rppt@kernel.org>,
	Pasha Tatashin <pasha.tatashin@soleen.com>,
	Pratyush Yadav <pratyush@kernel.org>,
	Alexander Graf <graf@amazon.com>,
	Jonathan Corbet <corbet@lwn.net>,
	Shuah Khan <skhan@linuxfoundation.org>,
	Randy Dunlap <rdunlap@infradead.org>,
	Andrew Morton <akpm@linux-foundation.org>,
	Tarun Sahu <tarunsahu@google.com>,
	David Matlack <dmatlack@google.com>,
	Samiullah Khawaja <skhawaja@google.com>
Cc: kexec@lists.infradead.org, linux-mm@kvack.org,
	linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org,
	linux-kselftest@vger.kernel.org
Subject: [RFC PATCH 3/5] kho: add KHO map
Date: Mon, 16 Nov 2026 14:40:08 +0100	[thread overview]
Message-ID: <20261116134013.1636689-4-pratyush@kernel.org> (raw)
In-Reply-To: <20261116134013.1636689-1-pratyush@kernel.org>

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


  parent reply	other threads:[~2026-11-16 13:40 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
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 [this message]
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

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20261116134013.1636689-4-pratyush@kernel.org \
    --to=pratyush@kernel.org \
    --cc=akpm@linux-foundation.org \
    --cc=corbet@lwn.net \
    --cc=dmatlack@google.com \
    --cc=graf@amazon.com \
    --cc=kexec@lists.infradead.org \
    --cc=linux-doc@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-kselftest@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=pasha.tatashin@soleen.com \
    --cc=rdunlap@infradead.org \
    --cc=rppt@kernel.org \
    --cc=skhan@linuxfoundation.org \
    --cc=skhawaja@google.com \
    --cc=tarunsahu@google.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox