[RFC v1 2/9] kho: split radix tree headers out of kexec_handover.h
Pasha Tatashin
pasha.tatashin at soleen.com
Thu Jun 4 20:32:28 PDT 2026
Split the radix tree tracker-related ABI definitions and header
declarations out of the monolithic kexec_handover.h header into a
dedicated header file (radix_tree.h).
Additionally, rename kho_radix_tree.h to kho/radix_tree.h, organizing it
within the existing kho directory structure as more KHO data structures
are introduced.
This is a pure code movement patch; no logic or functional changes are
introduced.
Signed-off-by: Pasha Tatashin <pasha.tatashin at soleen.com>
---
Documentation/core-api/kho/abi.rst | 3 +-
Documentation/core-api/kho/index.rst | 2 +-
include/linux/kho/abi/kexec_handover.h | 114 ---------------
include/linux/kho/abi/radix_tree.h | 131 ++++++++++++++++++
.../{kho_radix_tree.h => kho/radix_tree.h} | 5 +-
kernel/liveupdate/kexec_handover.c | 2 +-
kernel/liveupdate/kho_radix.c | 2 +-
7 files changed, 137 insertions(+), 122 deletions(-)
create mode 100644 include/linux/kho/abi/radix_tree.h
rename include/linux/{kho_radix_tree.h => kho/radix_tree.h} (96%)
diff --git a/Documentation/core-api/kho/abi.rst b/Documentation/core-api/kho/abi.rst
index edeb5b311963..da5c6636bb17 100644
--- a/Documentation/core-api/kho/abi.rst
+++ b/Documentation/core-api/kho/abi.rst
@@ -25,8 +25,7 @@ memblock preservation ABI
KHO persistent memory tracker ABI
=================================
-.. kernel-doc:: include/linux/kho/abi/kexec_handover.h
- :doc: KHO persistent memory tracker
+.. kernel-doc:: include/linux/kho/abi/radix_tree.h
KHO serialization block ABI
===========================
diff --git a/Documentation/core-api/kho/index.rst b/Documentation/core-api/kho/index.rst
index a9892c671ec3..f69367d217cf 100644
--- a/Documentation/core-api/kho/index.rst
+++ b/Documentation/core-api/kho/index.rst
@@ -74,7 +74,7 @@ the next KHO, because kexec can overwrite even the original kernel.
Kexec Handover Radix Tree
=========================
-.. kernel-doc:: include/linux/kho_radix_tree.h
+.. kernel-doc:: include/linux/kho/radix_tree.h
:doc: Kexec Handover Radix Tree
Public API
diff --git a/include/linux/kho/abi/kexec_handover.h b/include/linux/kho/abi/kexec_handover.h
index 5e2eb8519bda..99e4a53d4e35 100644
--- a/include/linux/kho/abi/kexec_handover.h
+++ b/include/linux/kho/abi/kexec_handover.h
@@ -4,15 +4,10 @@
* Copyright (C) 2023 Alexander Graf <graf at amazon.com>
* Copyright (C) 2025 Microsoft Corporation, Mike Rapoport <rppt at kernel.org>
* Copyright (C) 2025 Google LLC, Changyuan Lyu <changyuanl at google.com>
- * Copyright (C) 2025 Google LLC, Jason Miu <jasonmiu at google.com>
*/
#ifndef _LINUX_KHO_ABI_KEXEC_HANDOVER_H
#define _LINUX_KHO_ABI_KEXEC_HANDOVER_H
-
-#include <linux/bits.h>
-#include <linux/log2.h>
-#include <linux/math.h>
#include <linux/types.h>
#include <asm/page.h>
@@ -177,113 +172,4 @@ struct kho_vmalloc {
unsigned short order;
};
-/**
- * DOC: KHO persistent memory tracker
- *
- * KHO tracks preserved memory using a radix tree data structure. Each node of
- * the tree is exactly a single page. The leaf nodes are bitmaps where each set
- * bit is a preserved page of any order. The intermediate nodes are tables of
- * physical addresses that point to a lower level node.
- *
- * The tree hierarchy is shown below::
- *
- * root
- * +-------------------+
- * | Level 5 | (struct kho_radix_node)
- * +-------------------+
- * |
- * v
- * +-------------------+
- * | Level 4 | (struct kho_radix_node)
- * +-------------------+
- * |
- * | ... (intermediate levels)
- * |
- * v
- * +-------------------+
- * | Level 0 | (struct kho_radix_leaf)
- * +-------------------+
- *
- * The tree is traversed using a key that encodes the page's physical address
- * (pa) and its order into a single unsigned long value. The encoded key value
- * is composed of two parts: the 'order bit' in the upper part and the
- * 'shifted physical address' in the lower part.::
- *
- * +------------+-----------------------------+--------------------------+
- * | Page Order | Order Bit | Shifted Physical Address |
- * +------------+-----------------------------+--------------------------+
- * | 0 | ...000100 ... (at bit 52) | pa >> (PAGE_SHIFT + 0) |
- * | 1 | ...000010 ... (at bit 51) | pa >> (PAGE_SHIFT + 1) |
- * | 2 | ...000001 ... (at bit 50) | pa >> (PAGE_SHIFT + 2) |
- * | ... | ... | ... |
- * +------------+-----------------------------+--------------------------+
- *
- * Shifted Physical Address:
- * The 'shifted physical address' is the physical address normalized for its
- * order. It effectively represents the PFN shifted right by the order.
- *
- * Order Bit:
- * The 'order bit' encodes the page order by setting a single bit at a
- * specific position. The position of this bit itself represents the order.
- *
- * For instance, on a 64-bit system with 4KB pages (PAGE_SHIFT = 12), the
- * maximum range for the shifted physical address (for order 0) is 52 bits
- * (64 - 12). This address occupies bits [0-51]. For order 0, the order bit is
- * set at position 52.
- *
- * The following diagram illustrates how the encoded key value is split into
- * indices for the tree levels, with PAGE_SIZE of 4KB::
- *
- * 63:60 59:51 50:42 41:33 32:24 23:15 14:0
- * +---------+--------+--------+--------+--------+--------+-----------------+
- * | 0 | Lv 5 | Lv 4 | Lv 3 | Lv 2 | Lv 1 | Lv 0 (bitmap) |
- * +---------+--------+--------+--------+--------+--------+-----------------+
- *
- * The radix tree stores pages of all orders in a single 6-level hierarchy. It
- * efficiently shares higher tree levels, especially due to common zero top
- * address bits, allowing a single, efficient algorithm to manage all
- * pages. This bitmap approach also offers memory efficiency; for example, a
- * 512KB bitmap can cover a 16GB memory range for 0-order pages with PAGE_SIZE =
- * 4KB.
- *
- * The data structures defined here are part of the KHO ABI. Any modification
- * to these structures that breaks backward compatibility must be accompanied by
- * an update to the "compatible" string. This ensures that a newer kernel can
- * correctly interpret the data passed by an older kernel.
- */
-
-/*
- * Defines constants for the KHO radix tree structure, used to track preserved
- * memory. These constants govern the indexing, sizing, and depth of the tree.
- */
-enum kho_radix_consts {
- /*
- * The bit position of the order bit (and also the length of the
- * shifted physical address) for an order-0 page.
- */
- KHO_ORDER_0_LOG2 = 64 - PAGE_SHIFT,
-
- /* Size of the table in kho_radix_node, in log2 */
- KHO_TABLE_SIZE_LOG2 = const_ilog2(PAGE_SIZE / sizeof(phys_addr_t)),
-
- /* Number of bits in the kho_radix_leaf bitmap, in log2 */
- KHO_BITMAP_SIZE_LOG2 = PAGE_SHIFT + const_ilog2(BITS_PER_BYTE),
-
- /*
- * The total tree depth is the number of intermediate levels
- * and 1 bitmap level.
- */
- KHO_TREE_MAX_DEPTH =
- DIV_ROUND_UP(KHO_ORDER_0_LOG2 - KHO_BITMAP_SIZE_LOG2 + 1,
- KHO_TABLE_SIZE_LOG2) + 1,
-};
-
-struct kho_radix_node {
- u64 table[1 << KHO_TABLE_SIZE_LOG2];
-};
-
-struct kho_radix_leaf {
- DECLARE_BITMAP(bitmap, 1 << KHO_BITMAP_SIZE_LOG2);
-};
-
#endif /* _LINUX_KHO_ABI_KEXEC_HANDOVER_H */
diff --git a/include/linux/kho/abi/radix_tree.h b/include/linux/kho/abi/radix_tree.h
new file mode 100644
index 000000000000..f4cc5c02f37a
--- /dev/null
+++ b/include/linux/kho/abi/radix_tree.h
@@ -0,0 +1,131 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Copyright (C) 2025 Google LLC, Jason Miu <jasonmiu at google.com>
+ * Copyright (C) 2026 Pasha Tatashin <pasha.tatashin at soleen.com>
+ */
+
+#ifndef _LINUX_KHO_ABI_RADIX_TREE_H
+#define _LINUX_KHO_ABI_RADIX_TREE_H
+
+#include <linux/types.h>
+#include <asm/page.h>
+
+/**
+ * DOC: KHO persistent memory tracker
+ *
+ * Subsystems using the KHO persistent memory tracker rely on the stable
+ * Application Binary Interface defined below to pass serialized state from a
+ * pre-update kernel to a post-update kernel.
+ *
+ * This interface is a contract. Any modification to the structure fields,
+ * compatible strings, or the layout of the serialization structures defined
+ * here constitutes a breaking change. Such changes require incrementing the
+ * version number in the `KHO_FDT_COMPATIBLE` string to prevent a new kernel
+ * from misinterpreting data from an old kernel.
+ *
+ * Changes are allowed provided the compatibility version is incremented;
+ * however, backward/forward compatibility is only guaranteed for kernels
+ * supporting the same ABI version.
+ *
+ * KHO tracks preserved memory using a radix tree data structure. Each node of
+ * the tree is exactly a single page. The leaf nodes are bitmaps where each set
+ * bit is a preserved page of any order. The intermediate nodes are tables of
+ * physical addresses that point to a lower level node.
+ *
+ * The tree hierarchy is shown below::
+ *
+ * root
+ * +-------------------+
+ * | Level 5 | (struct kho_radix_node)
+ * +-------------------+
+ * |
+ * v
+ * +-------------------+
+ * | Level 4 | (struct kho_radix_node)
+ * +-------------------+
+ * |
+ * | ... (intermediate levels)
+ * |
+ * v
+ * +-------------------+
+ * | Level 0 | (struct kho_radix_leaf)
+ * +-------------------+
+ *
+ * The tree is traversed using a key that encodes the page's physical address
+ * (pa) and its order into a single unsigned long value. The encoded key value
+ * is composed of two parts: the 'order bit' in the upper part and the
+ * 'shifted physical address' in the lower part.::
+ *
+ * +------------+-----------------------------+--------------------------+
+ * | Page Order | Order Bit | Shifted Physical Address |
+ * +------------+-----------------------------+--------------------------+
+ * | 0 | ...000100 ... (at bit 52) | pa >> (PAGE_SHIFT + 0) |
+ * | 1 | ...000010 ... (at bit 51) | pa >> (PAGE_SHIFT + 1) |
+ * | 2 | ...000001 ... (at bit 50) | pa >> (PAGE_SHIFT + 2) |
+ * | ... | ... | ... |
+ * +------------+-----------------------------+--------------------------+
+ *
+ * Shifted Physical Address:
+ * The 'shifted physical address' is the physical address normalized for its
+ * order. It effectively represents the PFN shifted right by the order.
+ *
+ * Order Bit:
+ * The 'order bit' encodes the page order by setting a single bit at a
+ * specific position. The position of this bit itself represents the order.
+ *
+ * For instance, on a 64-bit system with 4KB pages (PAGE_SHIFT = 12), the
+ * maximum range for the shifted physical address (for order 0) is 52 bits
+ * (64 - 12). This address occupies bits [0-51]. For order 0, the order bit is
+ * set at position 52.
+ *
+ * The following diagram illustrates how the encoded key value is split into
+ * indices for the tree levels, with PAGE_SIZE of 4KB::
+ *
+ * 63:60 59:51 50:42 41:33 32:24 23:15 14:0
+ * +---------+--------+--------+--------+--------+--------+-----------------+
+ * | 0 | Lv 5 | Lv 4 | Lv 3 | Lv 2 | Lv 1 | Lv 0 (bitmap) |
+ * +---------+--------+--------+--------+--------+--------+-----------------+
+ *
+ * The radix tree stores pages of all orders in a single 6-level hierarchy. It
+ * efficiently shares higher tree levels, especially due to common zero top
+ * address bits, allowing a single, efficient algorithm to manage all
+ * pages. This bitmap approach also offers memory efficiency; for example, a
+ * 512KB bitmap can cover a 16GB memory range for 0-order pages with PAGE_SIZE =
+ * 4KB.
+ */
+
+/*
+ * Defines constants for the KHO radix tree structure, used to track preserved
+ * memory. These constants govern the indexing, sizing, and depth of the tree.
+ */
+enum kho_radix_consts {
+ /*
+ * The bit position of the order bit (and also the length of the
+ * shifted physical address) for an order-0 page.
+ */
+ KHO_ORDER_0_LOG2 = 64 - PAGE_SHIFT,
+
+ /* Size of the table in kho_radix_node, in log2 */
+ KHO_TABLE_SIZE_LOG2 = const_ilog2(PAGE_SIZE / sizeof(phys_addr_t)),
+
+ /* Number of bits in the kho_radix_leaf bitmap, in log2 */
+ KHO_BITMAP_SIZE_LOG2 = PAGE_SHIFT + const_ilog2(BITS_PER_BYTE),
+
+ /*
+ * The total tree depth is the number of intermediate levels
+ * and 1 bitmap level.
+ */
+ KHO_TREE_MAX_DEPTH =
+ DIV_ROUND_UP(KHO_ORDER_0_LOG2 - KHO_BITMAP_SIZE_LOG2 + 1,
+ KHO_TABLE_SIZE_LOG2) + 1,
+};
+
+struct kho_radix_node {
+ u64 table[1 << KHO_TABLE_SIZE_LOG2];
+};
+
+struct kho_radix_leaf {
+ DECLARE_BITMAP(bitmap, 1 << KHO_BITMAP_SIZE_LOG2);
+};
+
+#endif /* _LINUX_KHO_ABI_RADIX_TREE_H */
diff --git a/include/linux/kho_radix_tree.h b/include/linux/kho/radix_tree.h
similarity index 96%
rename from include/linux/kho_radix_tree.h
rename to include/linux/kho/radix_tree.h
index 84e918b96e53..1e337e73deba 100644
--- a/include/linux/kho_radix_tree.h
+++ b/include/linux/kho/radix_tree.h
@@ -5,6 +5,7 @@
#include <linux/err.h>
#include <linux/errno.h>
+#include <linux/kho/abi/radix_tree.h>
#include <linux/mutex_types.h>
#include <linux/types.h>
@@ -24,11 +25,9 @@
* Client code is responsible for allocating the root node of the tree,
* initializing the mutex lock, and managing its lifecycle. It must use the
* tree data structures defined in the KHO ABI,
- * `include/linux/kho/abi/kexec_handover.h`.
+ * `include/linux/kho/abi/radix_tree.h`.
*/
-struct kho_radix_node;
-
struct kho_radix_tree {
struct kho_radix_node *root;
struct mutex lock; /* protects the tree's structure and root pointer */
diff --git a/kernel/liveupdate/kexec_handover.c b/kernel/liveupdate/kexec_handover.c
index 041efff7ca11..4a3d6a54a17f 100644
--- a/kernel/liveupdate/kexec_handover.c
+++ b/kernel/liveupdate/kexec_handover.c
@@ -16,7 +16,7 @@
#include <linux/kasan.h>
#include <linux/kexec.h>
#include <linux/kexec_handover.h>
-#include <linux/kho_radix_tree.h>
+#include <linux/kho/radix_tree.h>
#include <linux/utsname.h>
#include <linux/kho/abi/kexec_handover.h>
#include <linux/kho/abi/kexec_metadata.h>
diff --git a/kernel/liveupdate/kho_radix.c b/kernel/liveupdate/kho_radix.c
index c836783a1376..f48088847264 100644
--- a/kernel/liveupdate/kho_radix.c
+++ b/kernel/liveupdate/kho_radix.c
@@ -11,7 +11,7 @@
#include <linux/io.h>
#include <linux/kernel.h>
#include <linux/kho/abi/kexec_handover.h>
-#include <linux/kho_radix_tree.h>
+#include <linux/kho/radix_tree.h>
#include <linux/mm.h>
#include <linux/mutex.h>
#include <linux/types.h>
--
2.53.0
More information about the kexec
mailing list