All of lore.kernel.org
 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: 14+ 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 20:13   ` Pasha Tatashin
2026-11-17 10:41     ` 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
2026-11-16 22:45 ` [RFC PATCH 0/5] KHO map Pasha Tatashin
2026-11-17 12:26   ` Pratyush Yadav
2026-11-17 15:35     ` Pratyush Yadav
2026-11-17 16:05       ` Pasha Tatashin
2026-11-17 10:10 ` Chris Down
2026-11-17 12:19   ` 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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.