Skip to contentSkip to conversation

Make KHO Stateless

PATCH Superseded Jason Miu 5 participants 13 messages Oct 20, 2025 – Oct 29, 2025

Subsystems (7)

v2 of 9 Superseded Latest is v9 →

lore
Share & tools
lore

Jason Miu

author
#0 lore raw

v2 cover Make KHO Stateless

This series transitions KHO from an xarray-based metadata tracking system with serialization to using a radix tree data structure that can be passed directly to the next kernel.

The key motivations for this change are to:
- Eliminate the need for data serialization before kexec.
- Remove the former KHO state machine by deprecating the finalize and abort states.
- Pass preservation metadata more directly to the next kernel via the FDT.

The new approach uses a radix tree to mark preserved pages. A page's physical address and its order are encoded into a single value. The tree is composed of multiple levels of page-sized tables, with leaf nodes being bitmap tables where each set bit represents a preserved page. The physical address of the radix tree's root is passed in the FDT, allowing the next kernel to reconstruct the preserved memory map.

The series includes the following changes:

1. kho: Adopt KHO radix tree data structures: Replaces the xarray-based tracker with the new radix tree implementation and removes the serialization/finalization code, thereby eliminating the KHO finalize and abort states.
2. memblock: Remove KHO notifier usage: Decouples the memblock subsystem from the KHO notifier system, switching it to use direct KHO API calls and adjusting KHO FDT completion timing. KHO selftest is also updated along with the APIs change.
3. kho: Remove notifier system infrastructure: Removes the now-unused notifier infrastructure from the KHO core.

---
Changes in v2:
- The radix tree now uses 0-based level numbering (previously 1-based).
- Added a new public API: kho_remove_subtree() for clients to remove an FDT subtree.
- The output FDT is now protected by a mutex.
- FDT properties have been moved to a new header: include/linux/live_update/abi/kexec_handover.h.
- The KHO selftest has been updated.

---
Jason Miu (3):
kho: Adopt KHO radix tree data structures
memblock: kho: Remove KHO notifier usage
kho: Remove notifier system infrastructure

 include/linux/kexec_handover.h                |  42 +-
 .../linux/live_update/abi/kexec_handover.h    |  10 +
 kernel/kexec_handover.c                       | 869 +++++++++---------
 lib/test_kho.c                                |  28 +-
 mm/memblock.c                                 |  45 +-
 tools/testing/selftests/kho/init.c            |  19 -
 6 files changed, 464 insertions(+), 549 deletions(-)
 create mode 100644 include/linux/live_update/abi/kexec_handover.h
Signature · 1 line
2.51.0.858.gf9c4a03a3a-goog
author
#1 lore raw

PATCH v2 1/3 kho: Adopt KHO radix tree data structures

Introduce a radix tree data structure for tracking preserved memory pages in KHO, which will replace the current xarray-based implementation.

The primary motivation for this change is to eliminate the need for serialization. By marking preserved pages directly in the new KHO radix tree and passing them to the next kernel, the entire serialization process can be removed. This ultimately allows for the removal of the KHO finalize and abort states, simplifying the overall design.

The preserved page physical address and its order are encoded in to a value. The KHO radix tree has multiple level of nodes where each node is a table contining a descriptor to the next level of nodes. The encoded value get split and stored its parts along the tree traversal. The tree traversal ends with the kho_bitmap_table, where each bit represents a single preserved page.

Instead of serializing the memory map, the first kernel store the KHO radix tree root in the FDT. This KHO radix tree root is passed to the second kernel after kexec, hence elimitated the KHO finalize and abort states.

The second kernel walks the passed-in KHO radix tree from its root. It restores the memory pages and their orders by decoding the value stored in the KHO radix tree.

This architectural shift to using a shared radix tree structure simplifies the KHO design and eliminates the overhead of serializing and deserializing the preserved memory map.

---
 MAINTAINERS                                   |   2 +
 include/linux/kexec_handover.h                |  23 +-
 .../linux/live_update/abi/kexec_handover.h    |  10 +
 kernel/kexec_handover.c                       | 861 +++++++++---------
 4 files changed, 458 insertions(+), 438 deletions(-)
 create mode 100644 include/linux/live_update/abi/kexec_handover.h
MAINTAINERS +2 -0
index 7ab92f471cb8..046a333ba0d3 100644
@@ -13550,12 +13550,14 @@ KEXEC HANDOVER (KHO)
 M:	Alexander Graf <[email protected]>
 M:	Mike Rapoport <[email protected]>
 M:	Changyuan Lyu <[email protected]>
+M:	Jason Miu <[email protected]>
 L:	[email protected]
 L:	[email protected]
 S:	Maintained
 F:	Documentation/admin-guide/mm/kho.rst
 F:	Documentation/core-api/kho/*
 F:	include/linux/kexec_handover.h
+F:	include/linux/live_update/abi/kexec_handover.h
 F:	kernel/kexec_handover.c
 F:	tools/testing/selftests/kho/
 
include/linux/kexec_handover.h +6 -17
index 348844cffb13..bc2f9e060a79 100644
@@ -19,23 +19,6 @@ enum kho_event {
 struct folio;
 struct notifier_block;
 
-#define DECLARE_KHOSER_PTR(name, type) \
-	union {                        \
-		phys_addr_t phys;      \
-		type ptr;              \
-	} name
-#define KHOSER_STORE_PTR(dest, val)               \
-	({                                        \
-		typeof(val) v = val;              \
-		typecheck(typeof((dest).ptr), v); \
-		(dest).phys = virt_to_phys(v);    \
-	})
-#define KHOSER_LOAD_PTR(src)                                                 \
-	({                                                                   \
-		typeof(src) s = src;                                         \
-		(typeof((s).ptr))((s).phys ? phys_to_virt((s).phys) : NULL); \
-	})
-
 struct kho_serialization;
 
 #ifdef CONFIG_KEXEC_HANDOVER
@@ -45,6 +28,7 @@ int kho_preserve_folio(struct folio *folio);
 int kho_preserve_phys(phys_addr_t phys, size_t size);
 struct folio *kho_restore_folio(phys_addr_t phys);
 int kho_add_subtree(struct kho_serialization *ser, const char *name, void *fdt);
+int kho_remove_subtree(const char *name);
 int kho_retrieve_subtree(const char *name, phys_addr_t *phys);
 
 int register_kho_notifier(struct notifier_block *nb);
@@ -86,6 +70,11 @@ static inline int kho_retrieve_subtree(const char *name, phys_addr_t *phys)
 	return -EOPNOTSUPP;
 }
 
+static inline int kho_remove_subtree(const char *name)
+{
+	return -EOPNOTSUPP;
+}
+
 static inline int register_kho_notifier(struct notifier_block *nb)
 {
 	return -EOPNOTSUPP;
include/linux/live_update/abi/kexec_handover.h new file +10 -0
new file mode 100644
index 000000000000..3154e5c33851
@@ -0,0 +1,10 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef _ABI__KEXEC_HANDOVER_H
+#define _ABI__KEXEC_HANDOVER_H
+
+#define KHO_FDT_COMPATIBLE "kho-v2"
+#define PROP_PRESERVED_PAGE_RADIX_TREE "preserved-page-radix-tree"
+#define PROP_SUB_FDT "fdt"
+
+#endif
kernel/kexec_handover.c +440 -421

1,043 lines not on this page · raw message

Signature · 1 line
2.51.0.858.gf9c4a03a3a-goog
#2 lore raw

Re: [PATCH v2 1/3] kho: Adopt KHO radix tree data structures

include/linux/live_update/abi/kexec_handover.h

Quoted 2 lines · Jason Miu
include/linux/live_update/abi/kexec_handover.h new file +0 -0
new file mode 100644

The need for this directory also came up in Vipin's VFIO series [1], so let's align on a directory we can all use.

Should we s/live_update/liveupdate/ to align with the file/directory naming convention Pasha is using in LUO (no underscore)? [2]

Otherwise, LGTM.

[1] https://lore.kernel.org/kvm/[email protected]/
[2] https://lore.kernel.org/lkml/[email protected]/

author
#3 lore raw

Re: [PATCH v2 1/3] kho: Adopt KHO radix tree data structures

Quoted 8 lines · David Matlack

include/linux/live_update/abi/kexec_handover.h

Quoted 2 lines · Jason Miu
include/linux/live_update/abi/kexec_handover.h new file +0 -0
new file mode 100644

The need for this directory also came up in Vipin's VFIO series [1], so let's align on a directory we can all use.

Quoted 7 lines

Should we s/live_update/liveupdate/ to align with the file/directory naming convention Pasha is using in LUO (no underscore)? [2]

Otherwise, LGTM.

[1] https://lore.kernel.org/kvm/[email protected]/
[2] https://lore.kernel.org/lkml/[email protected]/

Thanks for the suggestion. Yes, let's follow the convention in LUO [1]. Will use "include/linux/liveupdate/abi/kexec_handover.h" in this patch and share the "include/linux/liveupdate/abi/" path for liveupdate components.

[1] https://lore.kernel.org/lkml/[email protected]/

--
Jason Miu

#4 lore raw

Re: [PATCH v2 1/3] kho: Adopt KHO radix tree data structures

In reply to Jason Miu
Quoted 24 lines · Jason Miu

- * Keep track of memory that is to be preserved across KHO.
+ * The KHO radix tree tracks preserved memory pages. It is a hierarchical
+ * structure that starts with a single root kho_radix_tree. This single
+ * tree stores pages of all orders.
+ *
+ * This is achieved by encoding the page's physical address and its order into
+ * a single unsigned long value. This encoded value is then used to traverse
+ * the tree.
+ *
+ * The tree hierarchy is shown below:
+ *
+ * kho_radix_tree_root
+ * +-------------------+
+ * | Level 5 | (struct kho_radix_tree)
+ * +-------------------+
+ * |
+ * v
+ * +-------------------+
+ * | Level 4 | (struct kho_radix_tree)
+ * +-------------------+

+ *   |
+ *   | ... (intermediate levels)
+ *   |
+ *   v
Quoted 9 lines

+ * +-------------------+
+ * | Level 0 | (struct kho_bitmap_table)
+ * +-------------------+
*
- * The serializing side uses two levels of xarrays to manage chunks of per-order
- * 512 byte bitmaps. For instance if PAGE_SIZE = 4096, the entire 1G order of a
- * 1TB system would fit inside a single 512 byte bitmap. For order 0 allocations
- * each bitmap will cover 16M of address space. Thus, for 16G of memory at most
- * 512K of bitmap memory will be needed for order 0.

I think it is valuable to preserve this justification for bitmaps. There was a lot of debate over bitmaps vs ranges and this is the advantage of bitmaps. It is a bit subtle..

Quoted 28 lines

+/*
+ * The KHO radix tree tracks preserved pages by encoding a page's physical
+ * address (pa) and its order into a single unsigned long value. This value
+ * is then used to traverse the tree. The encoded value is composed of two
+ * parts: the 'order bits' in the upper part and the 'page offset' in the
+ * lower part.
+ *
+ * <-- Higher Bits ------------------------------------ Lower Bits -->

+ *  +--------------------------+-----------------------------------------+
+ *  |        Order Bits        |               Page Offset               |
+ *  +--------------------------+-----------------------------------------+
+ *  | ... 0 0 1 0 0 ...        | pa >> (PAGE_SHIFT + order)              |
+ *  +--------------------------+-----------------------------------------+

+ * ^
+ * |
+ * This single '1' bit's position
+ * uniquely identifies the 'order'.
+ *
+ *
+ * Page Offset:
+ * The 'page offset' is the physical address normalized for its order. It
+ * effectively represents the page offset for the given order.
+ *
+ * Order Bits:
+ * The 'order bits' encode 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

Quoted 8 lines

+ * maximum range for a page offset (for order 0) is 52 bits (64 - 12). This
+ * offset occupies bits [0-51]. For order 0, the order bit is set at
+ * position 52.
+ *
+ * As the order increases, the number of bits required for the 'page offset'
+ * decreases. For example, order 1 requires one less bit for its page
+ * offset. This allows its order bit to be set at position 51,
+ * i.e. shifting right, without conflicting with the page offset bits.

This description is correct, but the diagram is misleading. Maybe like this:

 *  |0| ... 0 0 0 1          | pa >> (PAGE_SHIFT + 0)              |
 *  |1| ... 0 0 0 0 1        | pa >> (PAGE_SHIFT + 1)              |
 *  |2| ... 0 0 0 0 0 1      | pa >> (PAGE_SHIFT + 2)              |

[..]

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 148

Quoted 12 lines

+ *
+ * This design stores pages of all sizes (orders) in a single 6-level table. It
+ * efficiently shares lower table levels, especially due to common zero top
+ * address bits, allowing a single, efficient algorithm to manage all pages.
+ */

kernel/kexec_handover.c +7 -0
+enum kho_radix_consts {
+	/* The bit position of a 0-order page, only supports 64bits system */
+	ORDER_0_LG2 = 64 - PAGE_SHIFT,
+	/* Bit number used for each level of tables */
+	TABLE_SIZE_LG2 = const_ilog2(PAGE_SIZE / sizeof(phys_addr_t)),
+	/* Bit number used for lowest level of bitmaps */
+	BITMAP_SIZE_LG2 = PAGE_SHIFT + const_ilog2(BITS_PER_BYTE),

"bit number" is a bit confusing when using a lg2 terms..

/* Size of the table in kho_radix_tree, in lg2 */ TABLE_SIZE_LG2 = const_ilog2(PAGE_SIZE / sizeof(phys_addr_t))

/* Number of bits in the kho_bitmap_table, in lg2 */ BITMAP_SIZE_LG2 = const_ilog2(BITS_PER_BYTE * PAGE_SIZE)

Then use the constants in the structs:

struct kho_radix_tree {
       phys_addr_t table[1 << TABLE_SIZE_LG2];
};
struct kho_bitmap_table {
       unsigned long bitmaps[(1 << BITMAP_SIZE_LG2) / BITS_PER_LONG];
};

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 169

Quoted 5 lines
kernel/kexec_handover.c +4 -1
-struct khoser_mem_chunk;
+static inline phys_addr_t kho_radix_tree_desc(struct kho_radix_tree *va)
+{
+	return (phys_addr_t)virt_to_phys(va);
+}

virt_to_phys already returns phys_addr_t ?

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 174

Quoted 4 lines
kernel/kexec_handover.c +4 -0
+static inline struct kho_radix_tree *kho_radix_tree(phys_addr_t desc)
+{
+	return (struct kho_radix_tree *)(phys_to_virt(desc));
+}

phys_to_virt returns void *, no need for a cast

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 221

Quoted 6 lines
kernel/kexec_handover.c +6 -0
+static int kho_radix_set_bitmap(struct kho_bitmap_table *bit_tlb,
+				unsigned long offset)
+{
+	if (!bit_tlb ||
+	    offset >= PAGE_SIZE * BITS_PER_BYTE)
+		return -EINVAL;

WARN_ON ? These are assertions aren't they?

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 303

Quoted 12 lines
kernel/kexec_handover.c +12 -0
+static int kho_radix_walk_trees(struct kho_radix_tree *root, unsigned int level,
+				unsigned long start,
+				kho_radix_tree_walk_callback_t cb)
+{
+	struct kho_radix_tree *next_tree;
+	struct kho_bitmap_table *bitmap_table;
+	unsigned long encoded, i;
+	unsigned int level_shift;
+	int err = 0;
+
+	for (i = 0; i < PAGE_SIZE / sizeof(phys_addr_t); i++) {
+		if (root->table[i]) {

if (!root->table[i])
continue

Remove a level of indentation here

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 344

Quoted 7 lines
kernel/kexec_handover.c +7 -0
+static int __kho_preserve_order(unsigned long pfn, unsigned int order)
+{
+	unsigned long pa = PFN_PHYS(pfn);
+
+	might_sleep();
+
+	return kho_radix_preserve_page(pa, order);

might_sleep should be in kho_radix_preserve_page() ? The might should be placed around if statements that might avoid a sleep, and that is not in this function.

Quoted 10 lines

static void __init kho_mem_deserialize(const void *fdt) {

kernel/kexec_handover.c +3 -0
+	struct kho_radix_tree *tree_root;
 	const phys_addr_t *mem;
 	int len;
 
+	/* Retrieve the KHO radix tree from passed-in FDT. */
+	mem = fdt_getprop(fdt, 0, PROP_PRESERVED_PAGE_RADIX_TREE, &len);
 
 	if (!mem || len != sizeof(*mem)) {

kernel/kexec_handover.c struct folio *kho_restore_folio(phys_addr_t phys) · line 427

Quoted 10 lines
kernel/kexec_handover.c +6 -0
+		pr_err("failed to get preserved KHO memory tree\n");
 		return;
 	}
 
+	tree_root = *mem ?
+		(struct kho_radix_tree *)phys_to_virt(*mem) :
+		NULL;
 
+	if (!tree_root)
+		return;

Seems weird?

if (!*mem)
return;

tree_root = phys_to_virt(*mem) kho_radix_walk_trees(tree_root, TREE_MAX_DEPTH - 1, 0,

			     kho_radix_walk_trees_memblock_callback);

This is prettty good now, IMHO

Jason

author
#5 lore raw

Re: [PATCH v2 1/3] kho: Adopt KHO radix tree data structures

Quoted 36 lines · Jason Gunthorpe
Quoted 24 lines · Jason Miu

- * Keep track of memory that is to be preserved across KHO.
+ * The KHO radix tree tracks preserved memory pages. It is a hierarchical
+ * structure that starts with a single root kho_radix_tree. This single
+ * tree stores pages of all orders.
+ *
+ * This is achieved by encoding the page's physical address and its order into
+ * a single unsigned long value. This encoded value is then used to traverse
+ * the tree.
+ *
+ * The tree hierarchy is shown below:
+ *
+ * kho_radix_tree_root
+ * +-------------------+
+ * | Level 5 | (struct kho_radix_tree)
+ * +-------------------+
+ * |
+ * v
+ * +-------------------+
+ * | Level 4 | (struct kho_radix_tree)
+ * +-------------------+

+ *   |
+ *   | ... (intermediate levels)
+ *   |
+ *   v
Quoted 9 lines

+ * +-------------------+
+ * | Level 0 | (struct kho_bitmap_table)
+ * +-------------------+
*
- * The serializing side uses two levels of xarrays to manage chunks of per-order
- * 512 byte bitmaps. For instance if PAGE_SIZE = 4096, the entire 1G order of a
- * 1TB system would fit inside a single 512 byte bitmap. For order 0 allocations
- * each bitmap will cover 16M of address space. Thus, for 16G of memory at most
- * 512K of bitmap memory will be needed for order 0.

Quoted 3 lines

I think it is valuable to preserve this justification for bitmaps. There was a lot of debate over bitmaps vs ranges and this is the advantage of bitmaps. It is a bit subtle..

Sure, I will update the description about using the bitmap, along with the new values.

Quoted 37 lines
Quoted 28 lines

+/*
+ * The KHO radix tree tracks preserved pages by encoding a page's physical
+ * address (pa) and its order into a single unsigned long value. This value
+ * is then used to traverse the tree. The encoded value is composed of two
+ * parts: the 'order bits' in the upper part and the 'page offset' in the
+ * lower part.
+ *
+ * <-- Higher Bits ------------------------------------ Lower Bits -->

+ *  +--------------------------+-----------------------------------------+
+ *  |        Order Bits        |               Page Offset               |
+ *  +--------------------------+-----------------------------------------+
+ *  | ... 0 0 1 0 0 ...        | pa >> (PAGE_SHIFT + order)              |
+ *  +--------------------------+-----------------------------------------+

+ * ^
+ * |
+ * This single '1' bit's position
+ * uniquely identifies the 'order'.
+ *
+ *
+ * Page Offset:
+ * The 'page offset' is the physical address normalized for its order. It
+ * effectively represents the page offset for the given order.
+ *
+ * Order Bits:
+ * The 'order bits' encode 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

Quoted 8 lines

+ * maximum range for a page offset (for order 0) is 52 bits (64 - 12). This
+ * offset occupies bits [0-51]. For order 0, the order bit is set at
+ * position 52.
+ *
+ * As the order increases, the number of bits required for the 'page offset'
+ * decreases. For example, order 1 requires one less bit for its page
+ * offset. This allows its order bit to be set at position 51,
+ * i.e. shifting right, without conflicting with the page offset bits.

Quoted 7 lines

This description is correct, but the diagram is misleading. Maybe like this:

 *  |0| ... 0 0 0 1          | pa >> (PAGE_SHIFT + 0)              |
 *  |1| ... 0 0 0 0 1        | pa >> (PAGE_SHIFT + 1)              |
 *  |2| ... 0 0 0 0 0 1      | pa >> (PAGE_SHIFT + 2)              |

[..]

I see, giving new examples makes the order bit positions more clearer.

Quoted 39 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 148

Quoted 13 lines

+ *
+ * This design stores pages of all sizes (orders) in a single 6-level table. It
+ * efficiently shares lower table levels, especially due to common zero top
+ * address bits, allowing a single, efficient algorithm to manage all pages.
+ */

kernel/kexec_handover.c +7 -0
+enum kho_radix_consts {
+     /* The bit position of a 0-order page, only supports 64bits system */
+     ORDER_0_LG2 = 64 - PAGE_SHIFT,
+     /* Bit number used for each level of tables */
+     TABLE_SIZE_LG2 = const_ilog2(PAGE_SIZE / sizeof(phys_addr_t)),
+     /* Bit number used for lowest level of bitmaps */
+     BITMAP_SIZE_LG2 = PAGE_SHIFT + const_ilog2(BITS_PER_BYTE),

"bit number" is a bit confusing when using a lg2 terms..

/* Size of the table in kho_radix_tree, in lg2 */ TABLE_SIZE_LG2 = const_ilog2(PAGE_SIZE / sizeof(phys_addr_t))

/* Number of bits in the kho_bitmap_table, in lg2 */ BITMAP_SIZE_LG2 = const_ilog2(BITS_PER_BYTE * PAGE_SIZE)

Then use the constants in the structs:

struct kho_radix_tree {
       phys_addr_t table[1 << TABLE_SIZE_LG2];
};
struct kho_bitmap_table {
       unsigned long bitmaps[(1 << BITMAP_SIZE_LG2) / BITS_PER_LONG];
};

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 169

Quoted 5 lines
kernel/kexec_handover.c +4 -1
-struct khoser_mem_chunk;
+static inline phys_addr_t kho_radix_tree_desc(struct kho_radix_tree *va)
+{
+     return (phys_addr_t)virt_to_phys(va);
+}

virt_to_phys already returns phys_addr_t ?

Quoted 7 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 174

Quoted 4 lines
kernel/kexec_handover.c +4 -0
+static inline struct kho_radix_tree *kho_radix_tree(phys_addr_t desc)
+{
+     return (struct kho_radix_tree *)(phys_to_virt(desc));
+}

phys_to_virt returns void *, no need for a cast

Yup, will update the types in both functions.

Quoted 8 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 221

Quoted 6 lines
kernel/kexec_handover.c +6 -0
+static int kho_radix_set_bitmap(struct kho_bitmap_table *bit_tlb,
+                             unsigned long offset)
+{
+     if (!bit_tlb ||
+         offset >= PAGE_SIZE * BITS_PER_BYTE)
+             return -EINVAL;

WARN_ON ? These are assertions aren't they?

Yes, will add an assertion here. Or should we use "BUG_ON"? As if this error happened something is quite wrong and I do not think it is recoverable.

Quoted 20 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 303

Quoted 13 lines
kernel/kexec_handover.c +12 -0
+static int kho_radix_walk_trees(struct kho_radix_tree *root, unsigned int level,
+                             unsigned long start,
+                             kho_radix_tree_walk_callback_t cb)
+{
+     struct kho_radix_tree *next_tree;
+     struct kho_bitmap_table *bitmap_table;
+     unsigned long encoded, i;
+     unsigned int level_shift;
+     int err = 0;
+
+     for (i = 0; i < PAGE_SIZE / sizeof(phys_addr_t); i++) {
+             if (root->table[i]) {

if (!root->table[i])
continue

Remove a level of indentation here

Quoted 12 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 344

Quoted 7 lines
kernel/kexec_handover.c +7 -0
+static int __kho_preserve_order(unsigned long pfn, unsigned int order)
+{
+     unsigned long pa = PFN_PHYS(pfn);
+
+     might_sleep();
+
+     return kho_radix_preserve_page(pa, order);

might_sleep should be in kho_radix_preserve_page() ? The might should be placed around if statements that might avoid a sleep, and that is not in this function.

I got another feedback that we can merge the kho_radix_preserve_page() __kho_preserve_order(), so the might_sleep() will be in the if statements.

Quoted 21 lines
Quoted 10 lines

static void __init kho_mem_deserialize(const void *fdt) {

kernel/kexec_handover.c +3 -0
+     struct kho_radix_tree *tree_root;
      const phys_addr_t *mem;
      int len;
 
+     /* Retrieve the KHO radix tree from passed-in FDT. */
+     mem = fdt_getprop(fdt, 0, PROP_PRESERVED_PAGE_RADIX_TREE, &len);
 
      if (!mem || len != sizeof(*mem)) {

kernel/kexec_handover.c struct folio *kho_restore_folio(phys_addr_t phys) · line 427

Quoted 10 lines
kernel/kexec_handover.c +6 -0
+             pr_err("failed to get preserved KHO memory tree\n");
              return;
      }
 
+     tree_root = *mem ?
+             (struct kho_radix_tree *)phys_to_virt(*mem) :
+             NULL;
 
+     if (!tree_root)
+             return;
Quoted 9 lines

Seems weird?

if (!*mem)
return;

tree_root = phys_to_virt(*mem) kho_radix_walk_trees(tree_root, TREE_MAX_DEPTH - 1, 0,

                             kho_radix_walk_trees_memblock_callback);

Yup, this looks more natural, my mind was thinking to check tree_root.

Quoted 4 lines

This is prettty good now, IMHO

Jason

#6 lore raw

Re: [PATCH v2 1/3] kho: Adopt KHO radix tree data structures

In reply to Jason Miu

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 179

Quoted 4 lines · Jason Miu
kernel/kexec_handover.c +3 -0
+static struct kho_radix_tree *kho_alloc_radix_tree(void)
 {
+	return (struct kho_radix_tree *)get_zeroed_page(GFP_KERNEL);
+}

I was reading the thread over here:

https://lore.kernel.org/all/[email protected]/

And I guess this stuff should just use
kzalloc(sizeof(struct kho_radix_tree), GFP_KERNEL);

Jason

maintainer
#7 lore raw

Re: [PATCH v2 1/3] kho: Adopt KHO radix tree data structures

Quoted 10 lines · Jason Gunthorpe

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 179

Quoted 4 lines · Jason Miu
kernel/kexec_handover.c +3 -0
+static struct kho_radix_tree *kho_alloc_radix_tree(void)
 {
+     return (struct kho_radix_tree *)get_zeroed_page(GFP_KERNEL);
+}

I was reading the thread over here:

Quoted 4 lines

https://lore.kernel.org/all/[email protected]/

And I guess this stuff should just use
kzalloc(sizeof(struct kho_radix_tree), GFP_KERNEL);

kzalloc() uses slab, which in turn may use kfence objects, and kfence can allocate memory from KHO scratch area, leading to memory corruptions. Let's not use slab allocator for KHO preserved and metadata memory, it is not a good choice.

Pasha

#8 lore raw

Re: [PATCH v2 1/3] kho: Adopt KHO radix tree data structures

Quoted 13 lines · Pasha Tatashin
Quoted 12 lines · Jason Gunthorpe

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 179

Quoted 4 lines · Jason Miu
kernel/kexec_handover.c +3 -0
+static struct kho_radix_tree *kho_alloc_radix_tree(void)
 {
+     return (struct kho_radix_tree *)get_zeroed_page(GFP_KERNEL);
+}

I was reading the thread over here:

https://lore.kernel.org/all/[email protected]/

Quoted 7 lines
Quoted 2 lines

And I guess this stuff should just use
kzalloc(sizeof(struct kho_radix_tree), GFP_KERNEL);

kzalloc() uses slab, which in turn may use kfence objects, and kfence can allocate memory from KHO scratch area, leading to memory corruptions. Let's not use slab allocator for KHO preserved and metadata memory, it is not a good choice.

That sounds like a nasty subtle problem to have :(

Really should provide a kho allocator API to document these needs!

Jason

maintainer
#9 lore raw

Re: [PATCH v2 1/3] kho: Adopt KHO radix tree data structures

In reply to Jason Miu
Quoted 45 lines · Jason Miu

Introduce a radix tree data structure for tracking preserved memory pages in KHO, which will replace the current xarray-based implementation.

The primary motivation for this change is to eliminate the need for serialization. By marking preserved pages directly in the new KHO radix tree and passing them to the next kernel, the entire serialization process can be removed. This ultimately allows for the removal of the KHO finalize and abort states, simplifying the overall design.

The preserved page physical address and its order are encoded in to a value. The KHO radix tree has multiple level of nodes where each node is a table contining a descriptor to the next level of nodes. The encoded value get split and stored its parts along the tree traversal. The tree traversal ends with the kho_bitmap_table, where each bit represents a single preserved page.

Instead of serializing the memory map, the first kernel store the KHO radix tree root in the FDT. This KHO radix tree root is passed to the second kernel after kexec, hence elimitated the KHO finalize and abort states.

The second kernel walks the passed-in KHO radix tree from its root. It restores the memory pages and their orders by decoding the value stored in the KHO radix tree.

This architectural shift to using a shared radix tree structure simplifies the KHO design and eliminates the overhead of serializing and deserializing the preserved memory map.

---
 MAINTAINERS                                   |   2 +
 include/linux/kexec_handover.h                |  23 +-
 .../linux/live_update/abi/kexec_handover.h    |  10 +
 kernel/kexec_handover.c                       | 861 +++++++++---------
 4 files changed, 458 insertions(+), 438 deletions(-)
 create mode 100644 include/linux/live_update/abi/kexec_handover.h
include/linux/kexec_handover.h +0 -0
index 348844cffb13..bc2f9e060a79 100644

include/linux/kexec_handover.h int kho_preserve_folio(struct folio *folio); · line 31

Quoted 4 lines
include/linux/kexec_handover.h +1 -0
@@ -45,6 +28,7 @@ int kho_preserve_folio(struct folio *folio);
 int kho_preserve_phys(phys_addr_t phys, size_t size);
 struct folio *kho_restore_folio(phys_addr_t phys);
 int kho_add_subtree(struct kho_serialization *ser, const char *name, void *fdt);
+int kho_remove_subtree(const char *name);

This change seems unrelated.

include/linux/kexec_handover.h static inline int kho_retrieve_subtree(const char *name, phys_addr_t *phys) · line 77

Quoted 12 lines
include/linux/kexec_handover.h +5 -0
 int kho_retrieve_subtree(const char *name, phys_addr_t *phys);
 
 int register_kho_notifier(struct notifier_block *nb);
@@ -86,6 +70,11 @@ static inline int kho_retrieve_subtree(const char *name, phys_addr_t *phys)
 	return -EOPNOTSUPP;
 }
 
+static inline int kho_remove_subtree(const char *name)
+{
+	return -EOPNOTSUPP;
+}
+

Ditto.

Quoted 9 lines
include/linux/kexec_handover.h +0 -0
 static inline int register_kho_notifier(struct notifier_block *nb)
 {
 	return -EOPNOTSUPP;
include/linux/live_update/abi/kexec_handover.h new file +0 -0
new file mode 100644
index 000000000000..3154e5c33851

include/linux/live_update/abi/kexec_handover.h line 7

Quoted 7 lines
include/linux/live_update/abi/kexec_handover.h new file +7 -0
@@ -0,0 +1,10 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef _ABI__KEXEC_HANDOVER_H
+#define _ABI__KEXEC_HANDOVER_H
+
+#define KHO_FDT_COMPATIBLE "kho-v2"
+#define PROP_PRESERVED_PAGE_RADIX_TREE "preserved-page-radix-tree"

The property describes the preserved memory, it's not important if it's a radix tree, a linked list or whatever else, so I don't think page-radix-tree is a good name.

IMHO we can keep the preserved-memory-map name because version bump ensures we won't attempt to parse v1 data structure.

Quoted 8 lines
include/linux/live_update/abi/kexec_handover.h new file +3 -0
+#define PROP_SUB_FDT "fdt"
+
+#endif
kernel/kexec_handover.c +0 -0
index ecd1ac210dbd..2fc5975690a7 100644

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 50

Quoted 7 lines
kernel/kexec_handover.c +2 -1
@@ -46,143 +45,305 @@ static int __init kho_parse_enable(char *p)
 }
 early_param("kho", kho_parse_enable);
 
+typedef int (*kho_radix_tree_walk_callback_t)(unsigned long encoded);
+
 /*
- * Keep track of memory that is to be preserved across KHO.

Please leave this sentence.

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 53

Quoted 3 lines
kernel/kexec_handover.c +3 -0
+ * The KHO radix tree tracks preserved memory pages. It is a hierarchical
+ * structure that starts with a single root `kho_radix_tree`. This single
+ * tree stores pages of all orders.

I'd combine this comment and the comment above declaration of enum kho_radix_consts into something like this:

/*
* KHO tracks preserved memory using a radix tree data structure. Each node of
* the tree is PAGE_SIZE and it is PAGE_SIZE aligned.
*
* The leaf nodes of the tree are bitmaps where each set bit represents a
* single preserved page. The intermediate and root nodes of the tree are
* tables of physical addresses that point to a lower level node:
*
* kho_radix_tree_root
* +-------------------+
* | Level 5 | (struct kho_radix_tree)
* +-------------------+
* |
* v
* +-------------------+
* | Level 4 | (struct kho_radix_tree)
* +-------------------+

 *   |
 *   | ... (intermediate levels)
 *   |
 *   v
 * +-------------------+
 * |      Level 0      | (struct kho_bitmap_table)
 * +-------------------+
 *
 * The physical address of the preserved page and its order are encoded into a
 * single unsigned long value where higher bits represent the order and the
 * lower bits represent the page offset:
 *
 *   <-- Higher Bits ------------------------------------ Lower Bits -->
 *  +--------------------------+-----------------------------------------+
 *  |        Order Bits        |               Page Offset               |
 *  +--------------------------+-----------------------------------------+
 *  |0| ... 0 0 0 1            | pa >> (PAGE_SHIFT + 0)                  |
 *  |1| ... 0 0 0 0 1            | pa >> (PAGE_SHIFT + 1)                |
 *  |2| ... 0 0 0 0 0 1            | pa >> (PAGE_SHIFT + 2)              |
 *  +------------------------------+-------------------------------------+

* ^
* |
* This single '1' bit's position uniquely identifies the 'order'. *
* Page Offset:
* The 'page offset' is the physical address normalized for its order. It
* effectively represents the page offset for the given order.
*
* Order Bits:
* The 'order bits' encode 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 a page offset (for order 0) is 52 bits (64 - 12). This
* offset occupies bits [0-51]. For order 0, the order bit is set at
* position 52.
*
* As the order increases, the number of bits required for the 'page offset'
* decreases. For example, order 1 requires one less bit for its page
* offset. This allows its order bit to be set at position 51,
* i.e. shifting right, without conflicting with the page offset bits. *
* Bitfields in this encoded value are used as indices into the tables for
* upper levels and as bitmap index for the lowest level.
*
* The following diagram illustrates how the encoded 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) |
* +---------+--------+--------+--------+--------+--------+-----------------+ *
* This design stores pages of all sizes (orders) in a single 6-level table.
* It efficiently shares lower table levels, especially due to common zero top
* address bits, allowing a single, efficient algorithm to manage all pages. *
* < a paragraph about memory consumption >
*/

Quoted 4 lines
kernel/kexec_handover.c +4 -0
+ *
+ * This is achieved by encoding the page's physical address and its order into
+ * a single `unsigned long` value. This encoded value is then used to traverse
+ * the tree.

...

Quoted 7 lines

+ * Each kho_radix_tree (Levels 1-5) and kho_bitmap_table (Level 0) is
+ * PAGE_SIZE. Each entry in a kho_radix_tree is a descriptor (a physical
+ * address) pointing to the next level node. For Level 1 kho_radix_tree
+ * nodes, these descriptors point to a kho_bitmap_table. The final
+ * kho_bitmap_table is a bitmap where each set bit represents a single
+ * preserved page.
*/

Please add an empty line between description and the declaration.

Quoted 1 line

+struct kho_radix_tree {

I think the name should reflect that this data structure is for tracking memory in KHO. Otherwise it reads like a generic data structure that can be used with KHO, like kho_array Pratyush proposed a while ago.

Maybe struct kho_mem_radix_tree? Or even drop the 'radix', I don't think it's really important here.

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 98

Quoted 9 lines
kernel/kexec_handover.c +4 -4
+	phys_addr_t table[PAGE_SIZE / sizeof(phys_addr_t)];
+};
 
-#define PRESERVE_BITS (512 * 8)
-
-struct kho_mem_phys_bits {
-	DECLARE_BITMAP(preserve, PRESERVE_BITS);
+struct kho_bitmap_table {
+	unsigned long bitmaps[PAGE_SIZE / sizeof(unsigned long)];

What's wrong with kho_mem_phys_bits and DECLARE_BITMAP? Simply adjust PRESERVE_BITS to match PAGE_SIZE.

Quoted 5 lines

};

kernel/kexec_handover.c +2 -1
-struct kho_mem_phys {
+/*
+ * The KHO radix tree tracks preserved pages by encoding a page's physical

...

Quoted 3 lines

+ * address bits, allowing a single, efficient algorithm to manage all pages.
+ */
+enum kho_radix_consts {

I think this should be declared before the structs, so that there will be one long description before the enum, structs and code.

Quoted 19 lines
kernel/kexec_handover.c +10 -5
+	/* The bit position of a 0-order page, only supports 64bits system */
+	ORDER_0_LG2 = 64 - PAGE_SHIFT,
+	/* Bit number used for each level of tables */
+	TABLE_SIZE_LG2 = const_ilog2(PAGE_SIZE / sizeof(phys_addr_t)),
+	/* Bit number used for lowest level of bitmaps */
+	BITMAP_SIZE_LG2 = PAGE_SHIFT + const_ilog2(BITS_PER_BYTE),
 	/*
-	 * Points to kho_mem_phys_bits, a sparse bitmap array. Each bit is sized
-	 * to order.
+	 * The total tree depth is the number of intermediate levels
+	 * and 1 bitmap level.
 	 */
-	struct xarray phys_bits;
+	TREE_MAX_DEPTH = DIV_ROUND_UP(ORDER_0_LG2 - BITMAP_SIZE_LG2,
+				      TABLE_SIZE_LG2) + 1,
 };
 
-struct kho_mem_track {
-	/* Points to kho_mem_phys, each order gets its own bitmap tree */

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 164

Quoted 10 lines
kernel/kexec_handover.c +8 -2
-	struct xarray orders;
-};
+/*
+ * `kho_radix_tree_root` points to a page thats serves as the root of the
+ * KHO radix tree. This page is allocated during KHO module initialization.
+ * Its physical address is written to the FDT and passed to the next kernel
+ * during kexec.
+ */
+static struct kho_radix_tree *kho_radix_tree_root;
+static DECLARE_RWSEM(kho_radix_tree_root_sem);

I believe it's clearer to have struct kho_mem_track containing the pointer to root and the semaphore, e.g.

struct kho_mem_track {
	struct kho_mem_tree *root;
	struct rw_semaphore sem;
};

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 166

Quoted 2 lines
kernel/kexec_handover.c +1 -1
-struct khoser_mem_chunk;
+static inline phys_addr_t kho_radix_tree_desc(struct kho_radix_tree *va)

I think kho_mem_tree is a better prefix than kho_radix.

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 171

Quoted 13 lines
kernel/kexec_handover.c +4 -8
+{
+	return (phys_addr_t)virt_to_phys(va);
+}
 
-struct kho_serialization {
-	struct page *fdt;
-	struct list_head fdt_list;
-	struct dentry *sub_fdt_dir;
-	struct kho_mem_track track;
-	/* First chunk of serialized preserved memory map */
-	struct khoser_mem_chunk *preserved_mem_map;
-};
+static inline struct kho_radix_tree *kho_radix_tree(phys_addr_t desc)

This is not really a 'desc', this is a plain physical address, i.e. 'pa'. It's probably will be clearer to just use phys_to_virt() and virt_to_phys() directly rather than introduce these wrappers.

Quoted 5 lines
kernel/kexec_handover.c +3 -1
+{
+	return (struct kho_radix_tree *)(phys_to_virt(desc));
+}
 
-static void *xa_load_or_alloc(struct xarray *xa, unsigned long index, size_t sz)

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 181

Quoted 10 lines
kernel/kexec_handover.c +4 -4
+static struct kho_radix_tree *kho_alloc_radix_tree(void)
 {
-	void *elm, *res;
+	return (struct kho_radix_tree *)get_zeroed_page(GFP_KERNEL);
+}
 
-	elm = xa_load(xa, index);
-	if (elm)
-		return elm;
+static unsigned long kho_radix_encode(phys_addr_t pa, unsigned int order)

This name is really cryptic. Encode to what? Can't say I have great ideas, but this name should reflect that physical address and order are encoded into combined index into the tree.

Maybe _encode_indices()?

Quoted 6 lines
kernel/kexec_handover.c +5 -0
+{
+	/* Order bits part */
+	unsigned long h = 1UL << (ORDER_0_LG2 - order);
+	/* Page offset part */
+	unsigned long l = pa >> (PAGE_SHIFT + order);
 

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 191

Quoted 10 lines
kernel/kexec_handover.c +3 -6
-	elm = kzalloc(sz, GFP_KERNEL);
-	if (!elm)
-		return ERR_PTR(-ENOMEM);
+	return h | l;
+}
 
-	res = xa_cmpxchg(xa, index, NULL, elm, GFP_KERNEL);
-	if (xa_is_err(res))
-		res = ERR_PTR(xa_err(res));
+static phys_addr_t kho_radix_decode(unsigned long encoded, unsigned int *order)

The same here. Maybe

_decode_indices(unsigned long indices, unsigned int *order)

Quoted 10 lines
kernel/kexec_handover.c +5 -4
+{
+	unsigned int order_bit = fls64(encoded);
+	phys_addr_t pa;
 
-	if (res) {
-		kfree(elm);
-		return res;
-	}
+	/* order_bit is numbered starting at 1 from fls64 */
+	*order = ORDER_0_LG2 - order_bit + 1;

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 204

Quoted 10 lines
kernel/kexec_handover.c +4 -3
+	/* The order is discarded by the shift */
+	pa = encoded << (PAGE_SHIFT + *order);
 
-	return elm;
+	return pa;
 }
 
-static void __kho_unpreserve(struct kho_mem_track *track, unsigned long pfn,
-			     unsigned long end_pfn)
+static unsigned long kho_radix_get_index(unsigned long encoded,

I don't like 'encoded' here and below as well.

Quoted 16 lines
kernel/kexec_handover.c +4 -10
+					 unsigned int level)
 {
-	struct kho_mem_phys_bits *bits;
-	struct kho_mem_phys *physxa;
-
-	while (pfn < end_pfn) {
-		const unsigned int order =
-			min(count_trailing_zeros(pfn), ilog2(end_pfn - pfn));
-		const unsigned long pfn_high = pfn >> order;
+	int s;
 
-		physxa = xa_load(&track->orders, order);
-		if (!physxa)
-			continue;
+	if (level == 0)
+		return encoded % (1 << BITMAP_SIZE_LG2);

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 216

Quoted 10 lines
kernel/kexec_handover.c +4 -4
 
-		bits = xa_load(&physxa->phys_bits, pfn_high / PRESERVE_BITS);
-		if (!bits)
-			continue;
+	s = ((level - 1) * TABLE_SIZE_LG2) + BITMAP_SIZE_LG2;
+	return (encoded >> s) % (1 << TABLE_SIZE_LG2);
+}
 
-		clear_bit(pfn_high % PRESERVE_BITS, bits->preserve);
+static int kho_radix_set_bitmap(struct kho_bitmap_table *bit_tlb,

^ bitmap

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 220

Quoted 4 lines
kernel/kexec_handover.c +4 -0
+				unsigned long offset)
+{
+	if (!bit_tlb ||
+	    offset >= PAGE_SIZE * BITS_PER_BYTE)

No need for two lines here

Quoted 7 lines
kernel/kexec_handover.c +3 -2
+		return -EINVAL;
 
-		pfn += 1 << order;
-	}
+	__set_bit(offset, bit_tlb->bitmaps);
+	return 0;
 }

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 230

Quoted 10 lines
kernel/kexec_handover.c +3 -5
 
-static int __kho_preserve_order(struct kho_mem_track *track, unsigned long pfn,
-				unsigned int order)
+static int kho_radix_preserve_page(phys_addr_t pa, unsigned int order)
 {
-	struct kho_mem_phys_bits *bits;
-	struct kho_mem_phys *physxa, *new_physxa;
-	const unsigned long pfn_high = pfn >> order;
+	unsigned long encoded = kho_radix_encode(pa, order);
+	struct kho_radix_tree *current_tree, *new_tree;

current_ is excessive IMHO and 'node' seems to be a better name for a tree iterator:

	struct kho_radix_tree *node;

is fine, the new_tree can be declared in the scope that uses it.

kernel/kexec_handover.c

Quoted 1 line
kernel/kexec_handover.c +1 -0
+	struct kho_bitmap_table *bitmap_table;

_table is excessive on both the type name and variable name

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 232

Quoted 1 line
kernel/kexec_handover.c +1 -0
+	unsigned int tree_level = TREE_MAX_DEPTH - 1;

Just 'level' is enough.

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 233

Quoted 1 line
kernel/kexec_handover.c +1 -0
+	unsigned int err = 0;

err is signed.

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 238

Quoted 9 lines
kernel/kexec_handover.c +3 -4
+	unsigned int i, idx;
 
-	might_sleep();
+	down_write(&kho_radix_tree_root_sem);
 
-	physxa = xa_load(&track->orders, order);
-	if (!physxa) {
-		int err;
+	if (!kho_radix_tree_root) {

Isn't this an assert?
Also I don't see concurrency for accessing the root, the assertion can be outside the lock.

Quoted 13 lines
kernel/kexec_handover.c +5 -6
+		err = -EINVAL;
+		goto out;
+	}
 
-		new_physxa = kzalloc(sizeof(*physxa), GFP_KERNEL);
-		if (!new_physxa)
-			return -ENOMEM;
+	current_tree = kho_radix_tree_root;
 
-		xa_init(&new_physxa->phys_bits);
-		physxa = xa_cmpxchg(&track->orders, order, NULL, new_physxa,
-				    GFP_KERNEL);
+	/* Go from high levels to low levels */

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 251

Quoted 10 lines
kernel/kexec_handover.c +5 -4
+	for (i = tree_level; i >= 0; i--) {
+		idx = kho_radix_get_index(encoded, i);
 
-		err = xa_err(physxa);
-		if (err || physxa) {
-			xa_destroy(&new_physxa->phys_bits);
-			kfree(new_physxa);
+		if (i == 0) {
+			bitmap_table = (struct kho_bitmap_table *)current_tree;
+			err = kho_radix_set_bitmap(bitmap_table, idx);

I'd consider making the loop until 'i > 0' and putting this outside the loop.

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 254

Quoted 3 lines
kernel/kexec_handover.c +3 -0
+			goto out;
+		}
+
		if (node->table[idx]) {
			node = kho_radix_tree(node->table[idx]);
			continue;
		}

and reduce the indentation for allocating a new table.

Quoted 36 lines
kernel/kexec_handover.c +24 -7
+		if (!current_tree->table[idx]) {
+			new_tree = kho_alloc_radix_tree();
+			if (!new_tree) {
+				err = -ENOMEM;
+				goto out;
+			}
 
-			if (err)
-				return err;
+			current_tree->table[idx] =
+				kho_radix_tree_desc(new_tree);
+			current_tree = new_tree;
 		} else {
-			physxa = new_physxa;
+			current_tree = kho_radix_tree(current_tree->table[idx]);
 		}
 	}
 
-	bits = xa_load_or_alloc(&physxa->phys_bits, pfn_high / PRESERVE_BITS,
-				sizeof(*bits));
-	if (IS_ERR(bits))
-		return PTR_ERR(bits);
+out:
+	up_write(&kho_radix_tree_root_sem);
+	return err;
+}
+
+static int kho_radix_walk_bitmaps(struct kho_bitmap_table *bit_tlb,
+				  unsigned long encoded,
+				  kho_radix_tree_walk_callback_t cb)
+{
+	unsigned long *bitmap = (unsigned long *)bit_tlb;
+	unsigned int i;
+	int err = 0;
+
+	for_each_set_bit(i, bitmap, PAGE_SIZE * BITS_PER_BYTE) {

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 292

Quoted 10 lines
kernel/kexec_handover.c +8 -1
+		err = cb(encoded | i);
+		if (err)
+			return err;
+	}
 
-	set_bit(pfn_high % PRESERVE_BITS, bits->preserve);
+	return 0;
+}
+
+static int kho_radix_walk_trees(struct kho_radix_tree *root, unsigned int level,

static int kho_radix_walk_tree(struct kho_radix_tree *parent, ...

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 296

Quoted 4 lines
kernel/kexec_handover.c +4 -0
+				unsigned long start,
+				kho_radix_tree_walk_callback_t cb)
+{
+	struct kho_radix_tree *next_tree;
	struct kho_radix_tree *node;

kernel/kexec_handover.c

Quoted 1 line
kernel/kexec_handover.c +1 -0
+	struct kho_bitmap_table *bitmap_table;
                                ^ bitmap;

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 299

Quoted 2 lines
kernel/kexec_handover.c +2 -0
+	unsigned long encoded, i;
+	unsigned int level_shift;

This can move to the scope where it's used and 'shift' would be enough.

Quoted 1 line
kernel/kexec_handover.c +1 -0
+	int err = 0;

...

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 344

Quoted 7 lines
kernel/kexec_handover.c +7 -0
+static int __kho_preserve_order(unsigned long pfn, unsigned int order)
+{
+	unsigned long pa = PFN_PHYS(pfn);
+
+	might_sleep();
+
+	return kho_radix_preserve_page(pa, order);

I don't think that __kho_preserve_order() wrapper is useful, just rename kho_radix_preserve_page to __kho_preserve_order()

Quoted 8 lines
kernel/kexec_handover.c +2 -0
+}
+
 /* almost as free_reserved_page(), just don't free the page */
 static void kho_restore_page(struct page *page, unsigned int order)
 {
@@ -224,152 +385,49 @@ struct folio *kho_restore_folio(phys_addr_t phys)
 }
 EXPORT_SYMBOL_GPL(kho_restore_folio);

...

kernel/kexec_handover.c struct folio *kho_restore_folio(phys_addr_t phys) · line 388

Quoted 2 lines
kernel/kexec_handover.c +1 -1
-static int kho_mem_serialize(struct kho_serialization *ser)
+static int __init kho_radix_walk_trees_memblock_callback(unsigned long encoded)

I wonder if we expect other callbacks for tree traversal?
For now there's only one case when we traverse the tree, so it seems simpler to just merge the code here into kho_radix_walk_bitmaps() and rename kho_radix_walk_trees() and kho_radix_walk_bitmaps() to reflect that they are reserving the preserved memory.

Quoted 7 lines

{

kernel/kexec_handover.c +5 -0
+	unsigned int order;
+	unsigned long pa;
+	struct page *page;
+	int sz;
 
+	pa = kho_radix_decode(encoded, &order);

kernel/kexec_handover.c struct folio *kho_restore_folio(phys_addr_t phys) · line 408

Quoted 10 lines
kernel/kexec_handover.c +6 -0
+	sz = 1 << (order + PAGE_SHIFT);
+	page = phys_to_page(pa);
 
+	/* Reserve the memory preserved in KHO radix tree in memblock */
+	memblock_reserve(pa, sz);
+	memblock_reserved_mark_noinit(pa, sz);
+	page->private = order;
 }
 
 static void __init kho_mem_deserialize(const void *fdt)

Well, it's not deserialize anymore.

kernel/kexec_handover.c static int kho_debugfs_fdt_add(struct list_head *list, struct dentry *dir, · line 658

Quoted 4 lines

{

kernel/kexec_handover.c +0 -0
@@ -599,6 +657,35 @@ static int kho_debugfs_fdt_add(struct list_head *list, struct dentry *dir,
 	return 0;
 }

It seems that a lot of the changes below are not related to changing the mechanism for tracking the preserved memory.

I'm stopping here.

Signature · 2 lines
Sincerely yours,
Mike.
author
#10 lore raw

Re: [PATCH v2 1/3] kho: Adopt KHO radix tree data structures

Hi Mike,

Thank you very much for providing your comments.

Quoted 42 lines · Mike Rapoport
Quoted 40 lines · Jason Miu

Introduce a radix tree data structure for tracking preserved memory pages in KHO, which will replace the current xarray-based implementation.

The primary motivation for this change is to eliminate the need for serialization. By marking preserved pages directly in the new KHO radix tree and passing them to the next kernel, the entire serialization process can be removed. This ultimately allows for the removal of the KHO finalize and abort states, simplifying the overall design.

The preserved page physical address and its order are encoded in to a value. The KHO radix tree has multiple level of nodes where each node is a table contining a descriptor to the next level of nodes. The encoded value get split and stored its parts along the tree traversal. The tree traversal ends with the kho_bitmap_table, where each bit represents a single preserved page.

Instead of serializing the memory map, the first kernel store the KHO radix tree root in the FDT. This KHO radix tree root is passed to the second kernel after kexec, hence elimitated the KHO finalize and abort states.

The second kernel walks the passed-in KHO radix tree from its root. It restores the memory pages and their orders by decoding the value stored in the KHO radix tree.

This architectural shift to using a shared radix tree structure simplifies the KHO design and eliminates the overhead of serializing and deserializing the preserved memory map.

---
 MAINTAINERS                                   |   2 +
 include/linux/kexec_handover.h                |  23 +-
 .../linux/live_update/abi/kexec_handover.h    |  10 +
 kernel/kexec_handover.c                       | 861 +++++++++---------
 4 files changed, 458 insertions(+), 438 deletions(-)
 create mode 100644 include/linux/live_update/abi/kexec_handover.h
Quoted 11 lines

include/linux/kexec_handover.h int kho_preserve_folio(struct folio *folio); · line 31

Quoted 9 lines
include/linux/kexec_handover.h +1 -0
index 348844cffb13..bc2f9e060a79 100644
@@ -45,6 +28,7 @@ int kho_preserve_folio(struct folio *folio);
 int kho_preserve_phys(phys_addr_t phys, size_t size);
 struct folio *kho_restore_folio(phys_addr_t phys);
 int kho_add_subtree(struct kho_serialization *ser, const char *name, void *fdt);
+int kho_remove_subtree(const char *name);

This change seems unrelated.

I want to add the "kho_remove_subtree()" as a counterpart of the "kho_add_subtree()". You are right that "kho_remove_subtree()" is not very related to this radix tree data struct change. Do you prefer I split this kho_remove_subtree() change as another patch in this series, or do you prefer another independent patch series? (I like the latter option more personally)

Quoted 37 lines

include/linux/kexec_handover.h static inline int kho_retrieve_subtree(const char *name, phys_addr_t *phys) · line 77

Quoted 13 lines
include/linux/kexec_handover.h +5 -0
 int kho_retrieve_subtree(const char *name, phys_addr_t *phys);
 
 int register_kho_notifier(struct notifier_block *nb);
@@ -86,6 +70,11 @@ static inline int kho_retrieve_subtree(const char *name, phys_addr_t *phys)
      return -EOPNOTSUPP;
 }
 
+static inline int kho_remove_subtree(const char *name)
+{
+     return -EOPNOTSUPP;
+}
+

Ditto.

Quoted 9 lines
include/linux/kexec_handover.h +0 -0
 static inline int register_kho_notifier(struct notifier_block *nb)
 {
      return -EOPNOTSUPP;
include/linux/live_update/abi/kexec_handover.h new file +0 -0
new file mode 100644
index 000000000000..3154e5c33851

include/linux/live_update/abi/kexec_handover.h line 7

Quoted 7 lines
include/linux/live_update/abi/kexec_handover.h new file +7 -0
@@ -0,0 +1,10 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+#ifndef _ABI__KEXEC_HANDOVER_H
+#define _ABI__KEXEC_HANDOVER_H
+
+#define KHO_FDT_COMPATIBLE "kho-v2"
+#define PROP_PRESERVED_PAGE_RADIX_TREE "preserved-page-radix-tree"

The property describes the preserved memory, it's not important if it's a radix tree, a linked list or whatever else, so I don't think page-radix-tree is a good name.

Quoted 3 lines

IMHO we can keep the preserved-memory-map name because version bump ensures we won't attempt to parse v1 data structure.

Sure, I can just keep the preserved-memory-map name.

Quoted 18 lines
Quoted 8 lines
include/linux/live_update/abi/kexec_handover.h new file +3 -0
+#define PROP_SUB_FDT "fdt"
+
+#endif
kernel/kexec_handover.c +0 -0
index ecd1ac210dbd..2fc5975690a7 100644

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 50

Quoted 7 lines
kernel/kexec_handover.c +2 -1
@@ -46,143 +45,305 @@ static int __init kho_parse_enable(char *p)
 }
 early_param("kho", kho_parse_enable);
 
+typedef int (*kho_radix_tree_walk_callback_t)(unsigned long encoded);
+
 /*
- * Keep track of memory that is to be preserved across KHO.

Please leave this sentence.

Quoted 7 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 53

Quoted 3 lines
kernel/kexec_handover.c +3 -0
+ * The KHO radix tree tracks preserved memory pages. It is a hierarchical
+ * structure that starts with a single root `kho_radix_tree`. This single
+ * tree stores pages of all orders.

I'd combine this comment and the comment above declaration of enum kho_radix_consts into something like this:

Yes, I will move the kho_radix_consts up so its comment will be combined and stay close to the comment of kho_radix_tree.

Quoted 94 lines

/*
* KHO tracks preserved memory using a radix tree data structure. Each node of
* the tree is PAGE_SIZE and it is PAGE_SIZE aligned.
*
* The leaf nodes of the tree are bitmaps where each set bit represents a
* single preserved page. The intermediate and root nodes of the tree are
* tables of physical addresses that point to a lower level node:
*
* kho_radix_tree_root
* +-------------------+
* | Level 5 | (struct kho_radix_tree)
* +-------------------+
* |
* v
* +-------------------+
* | Level 4 | (struct kho_radix_tree)
* +-------------------+

 *   |
 *   | ... (intermediate levels)
 *   |
 *   v
 * +-------------------+
 * |      Level 0      | (struct kho_bitmap_table)
 * +-------------------+
 *
 * The physical address of the preserved page and its order are encoded into a
 * single unsigned long value where higher bits represent the order and the
 * lower bits represent the page offset:
 *
 *   <-- Higher Bits ------------------------------------ Lower Bits -->
 *  +--------------------------+-----------------------------------------+
 *  |        Order Bits        |               Page Offset               |
 *  +--------------------------+-----------------------------------------+
 *  |0| ... 0 0 0 1            | pa >> (PAGE_SHIFT + 0)                  |
 *  |1| ... 0 0 0 0 1            | pa >> (PAGE_SHIFT + 1)                |
 *  |2| ... 0 0 0 0 0 1            | pa >> (PAGE_SHIFT + 2)              |
 *  +------------------------------+-------------------------------------+

* ^
* |
* This single '1' bit's position uniquely identifies the 'order'. *
* Page Offset:
* The 'page offset' is the physical address normalized for its order. It
* effectively represents the page offset for the given order.
*
* Order Bits:
* The 'order bits' encode 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 a page offset (for order 0) is 52 bits (64 - 12). This
* offset occupies bits [0-51]. For order 0, the order bit is set at
* position 52.
*
* As the order increases, the number of bits required for the 'page offset'
* decreases. For example, order 1 requires one less bit for its page
* offset. This allows its order bit to be set at position 51,
* i.e. shifting right, without conflicting with the page offset bits. *
* Bitfields in this encoded value are used as indices into the tables for
* upper levels and as bitmap index for the lowest level.
*
* The following diagram illustrates how the encoded 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) |
* +---------+--------+--------+--------+--------+--------+-----------------+ *
* This design stores pages of all sizes (orders) in a single 6-level table.
* It efficiently shares lower table levels, especially due to common zero top
* address bits, allowing a single, efficient algorithm to manage all pages. *
* < a paragraph about memory consumption >
*/

Quoted 4 lines
kernel/kexec_handover.c +4 -0
+ *
+ * This is achieved by encoding the page's physical address and its order into
+ * a single `unsigned long` value. This encoded value is then used to traverse
+ * the tree.

...

Quoted 7 lines

+ * Each kho_radix_tree (Levels 1-5) and kho_bitmap_table (Level 0) is
+ * PAGE_SIZE. Each entry in a kho_radix_tree is a descriptor (a physical
+ * address) pointing to the next level node. For Level 1 kho_radix_tree
+ * nodes, these descriptors point to a kho_bitmap_table. The final
+ * kho_bitmap_table is a bitmap where each set bit represents a single
+ * preserved page.
*/

Please add an empty line between description and the declaration.

Quoted 9 lines
Quoted 1 line

+struct kho_radix_tree {

I think the name should reflect that this data structure is for tracking memory in KHO. Otherwise it reads like a generic data structure that can be used with KHO, like kho_array Pratyush proposed a while ago.

Maybe struct kho_mem_radix_tree? Or even drop the 'radix', I don't think it's really important here.

I use the 'radix' here as we need a step to convert the page address to a radix tree key. I agree that kho_mem_radix_tree sounds better.

Quoted 13 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 98

Quoted 9 lines
kernel/kexec_handover.c +4 -4
+     phys_addr_t table[PAGE_SIZE / sizeof(phys_addr_t)];
+};
 
-#define PRESERVE_BITS (512 * 8)
-
-struct kho_mem_phys_bits {
-     DECLARE_BITMAP(preserve, PRESERVE_BITS);
+struct kho_bitmap_table {
+     unsigned long bitmaps[PAGE_SIZE / sizeof(unsigned long)];

What's wrong with kho_mem_phys_bits and DECLARE_BITMAP? Simply adjust PRESERVE_BITS to match PAGE_SIZE.

I used kho_bitmap_table as I wanted to highlight it as a patch of bitmap that has to be in the size of PAGE_SIZE. I found the original kho_mem_phys_bits harder to understand as a bit in this bitmap is referring to one memory page. I can update it as

#define PRESERVE_PAGE_BITS (PAGE_SIZE * 8)

struct kho_bitmap {
    DECLARE_BITMAP(preserve_page, PRESERVE_PAGE_BITS);
};

what do you think?

Quoted 8 lines
Quoted 5 lines

};

kernel/kexec_handover.c +2 -1
-struct kho_mem_phys {
+/*
+ * The KHO radix tree tracks preserved pages by encoding a page's physical

...

Quoted 7 lines
Quoted 3 lines

+ * address bits, allowing a single, efficient algorithm to manage all pages.
+ */
+enum kho_radix_consts {

I think this should be declared before the structs, so that there will be one long description before the enum, structs and code.

yes, will move this enum up.

Quoted 33 lines
Quoted 19 lines
kernel/kexec_handover.c +10 -5
+     /* The bit position of a 0-order page, only supports 64bits system */
+     ORDER_0_LG2 = 64 - PAGE_SHIFT,
+     /* Bit number used for each level of tables */
+     TABLE_SIZE_LG2 = const_ilog2(PAGE_SIZE / sizeof(phys_addr_t)),
+     /* Bit number used for lowest level of bitmaps */
+     BITMAP_SIZE_LG2 = PAGE_SHIFT + const_ilog2(BITS_PER_BYTE),
      /*
-      * Points to kho_mem_phys_bits, a sparse bitmap array. Each bit is sized
-      * to order.
+      * The total tree depth is the number of intermediate levels
+      * and 1 bitmap level.
       */
-     struct xarray phys_bits;
+     TREE_MAX_DEPTH = DIV_ROUND_UP(ORDER_0_LG2 - BITMAP_SIZE_LG2,
+                                   TABLE_SIZE_LG2) + 1,
 };
 
-struct kho_mem_track {
-     /* Points to kho_mem_phys, each order gets its own bitmap tree */

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 164

Quoted 10 lines
kernel/kexec_handover.c +8 -2
-     struct xarray orders;
-};
+/*
+ * `kho_radix_tree_root` points to a page thats serves as the root of the
+ * KHO radix tree. This page is allocated during KHO module initialization.
+ * Its physical address is written to the FDT and passed to the next kernel
+ * during kexec.
+ */
+static struct kho_radix_tree *kho_radix_tree_root;
+static DECLARE_RWSEM(kho_radix_tree_root_sem);

I believe it's clearer to have struct kho_mem_track containing the pointer to root and the semaphore, e.g.

Quoted 5 lines
struct kho_mem_track {
        struct kho_mem_tree *root;
        struct rw_semaphore sem;
};

Sure.

Quoted 4 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 166

Quoted 2 lines
kernel/kexec_handover.c +1 -1
-struct khoser_mem_chunk;
+static inline phys_addr_t kho_radix_tree_desc(struct kho_radix_tree *va)

I think kho_mem_tree is a better prefix than kho_radix.

As above, I tend to use kho_mem_radix_tree.

Quoted 5 lines
Quoted 5 lines
kernel/kexec_handover.c +3 -0
+{
+     return (phys_addr_t)virt_to_phys(va);
+}
Quoted 13 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 171

Quoted 9 lines
kernel/kexec_handover.c +1 -8
-struct kho_serialization {
-     struct page *fdt;
-     struct list_head fdt_list;
-     struct dentry *sub_fdt_dir;
-     struct kho_mem_track track;
-     /* First chunk of serialized preserved memory map */
-     struct khoser_mem_chunk *preserved_mem_map;
-};
+static inline struct kho_radix_tree *kho_radix_tree(phys_addr_t desc)

This is not really a 'desc', this is a plain physical address, i.e. 'pa'. It's probably will be clearer to just use phys_to_virt() and virt_to_phys() directly rather than introduce these wrappers.

We had some previous discussions that using helper functions for converting between the va and pa. But I agree with what you said that "this is not ready a desc". How about "kho_radix_tree(phys_addr_t node_pa)", to align with the variable name of the tree iterator below?

Quoted 21 lines
Quoted 6 lines
kernel/kexec_handover.c +3 -1
+{
+     return (struct kho_radix_tree *)(phys_to_virt(desc));
+}
 
-static void *xa_load_or_alloc(struct xarray *xa, unsigned long index, size_t sz)

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 181

Quoted 10 lines
kernel/kexec_handover.c +4 -4
+static struct kho_radix_tree *kho_alloc_radix_tree(void)
 {
-     void *elm, *res;
+     return (struct kho_radix_tree *)get_zeroed_page(GFP_KERNEL);
+}
 
-     elm = xa_load(xa, index);
-     if (elm)
-             return elm;
+static unsigned long kho_radix_encode(phys_addr_t pa, unsigned int order)

This name is really cryptic. Encode to what? Can't say I have great ideas, but this name should reflect that physical address and order are encoded into combined index into the tree.

Quoted 1 line

Maybe _encode_indices()?

As the "indices" can also refer to an entry of the table in a KHO mem radix tree node. We are actually encoding a radix tree key, so may be kho_radix_encode_key() ?

Quoted 39 lines
Quoted 7 lines
kernel/kexec_handover.c +5 -0
+{
+     /* Order bits part */
+     unsigned long h = 1UL << (ORDER_0_LG2 - order);
+     /* Page offset part */
+     unsigned long l = pa >> (PAGE_SHIFT + order);
 

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 191

Quoted 10 lines
kernel/kexec_handover.c +3 -6
-     elm = kzalloc(sz, GFP_KERNEL);
-     if (!elm)
-             return ERR_PTR(-ENOMEM);
+     return h | l;
+}
 
-     res = xa_cmpxchg(xa, index, NULL, elm, GFP_KERNEL);
-     if (xa_is_err(res))
-             res = ERR_PTR(xa_err(res));
+static phys_addr_t kho_radix_decode(unsigned long encoded, unsigned int *order)

The same here. Maybe

_decode_indices(unsigned long indices, unsigned int *order)

Quoted 17 lines
kernel/kexec_handover.c +8 -5
+{
+     unsigned int order_bit = fls64(encoded);
+     phys_addr_t pa;
 
-     if (res) {
-             kfree(elm);
-             return res;
-     }
+     /* order_bit is numbered starting at 1 from fls64 */
+     *order = ORDER_0_LG2 - order_bit + 1;
+     /* The order is discarded by the shift */
+     pa = encoded << (PAGE_SHIFT + *order);
 
-     return elm;
+     return pa;
 }
Quoted 6 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 204

Quoted 3 lines
kernel/kexec_handover.c +1 -2
-static void __kho_unpreserve(struct kho_mem_track *track, unsigned long pfn,
-                          unsigned long end_pfn)
+static unsigned long kho_radix_get_index(unsigned long encoded,

I don't like 'encoded' here and below as well.

If we agree with the name above, I think we can use "kho_radix_get_index(unsigned long radix_key" here.

Quoted 24 lines
Quoted 24 lines
kernel/kexec_handover.c +7 -13
+                                      unsigned int level)
 {
-     struct kho_mem_phys_bits *bits;
-     struct kho_mem_phys *physxa;
-
-     while (pfn < end_pfn) {
-             const unsigned int order =
-                     min(count_trailing_zeros(pfn), ilog2(end_pfn - pfn));
-             const unsigned long pfn_high = pfn >> order;
+     int s;
 
-             physxa = xa_load(&track->orders, order);
-             if (!physxa)
-                     continue;
+     if (level == 0)
+             return encoded % (1 << BITMAP_SIZE_LG2);
 
-             bits = xa_load(&physxa->phys_bits, pfn_high / PRESERVE_BITS);
-             if (!bits)
-                     continue;
+     s = ((level - 1) * TABLE_SIZE_LG2) + BITMAP_SIZE_LG2;
+     return (encoded >> s) % (1 << TABLE_SIZE_LG2);
+}
Quoted 4 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 216

Quoted 2 lines
kernel/kexec_handover.c +1 -1
-             clear_bit(pfn_high % PRESERVE_BITS, bits->preserve);
+static int kho_radix_set_bitmap(struct kho_bitmap_table *bit_tlb,

^ bitmap

Yes, let's just call it struct kho_bitmap.

Quoted 50 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 220

Quoted 5 lines
kernel/kexec_handover.c +4 -0
+                             unsigned long offset)
+{
+     if (!bit_tlb ||
+         offset >= PAGE_SIZE * BITS_PER_BYTE)

No need for two lines here

Quoted 7 lines
kernel/kexec_handover.c +3 -2
+             return -EINVAL;
 
-             pfn += 1 << order;
-     }
+     __set_bit(offset, bit_tlb->bitmaps);
+     return 0;
 }

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 230

Quoted 10 lines
kernel/kexec_handover.c +3 -5
 
-static int __kho_preserve_order(struct kho_mem_track *track, unsigned long pfn,
-                             unsigned int order)
+static int kho_radix_preserve_page(phys_addr_t pa, unsigned int order)
 {
-     struct kho_mem_phys_bits *bits;
-     struct kho_mem_phys *physxa, *new_physxa;
-     const unsigned long pfn_high = pfn >> order;
+     unsigned long encoded = kho_radix_encode(pa, order);
+     struct kho_radix_tree *current_tree, *new_tree;

current_ is excessive IMHO and 'node' seems to be a better name for a tree iterator:

        struct kho_radix_tree *node;

is fine, the new_tree can be declared in the scope that uses it.

Quoted 1 line

+ struct kho_bitmap_table *bitmap_table;

_table is excessive on both the type name and variable name

Quoted 1 line

+ unsigned int tree_level = TREE_MAX_DEPTH - 1;

Just 'level' is enough.

Quoted 1 line

+ unsigned int err = 0;

err is signed.

Quoted 5 lines
kernel/kexec_handover.c +2 -1
+     unsigned int i, idx;
 
-     might_sleep();
+     down_write(&kho_radix_tree_root_sem);
Quoted 9 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 238

Quoted 4 lines
kernel/kexec_handover.c +1 -3
-     physxa = xa_load(&track->orders, order);
-     if (!physxa) {
-             int err;
+     if (!kho_radix_tree_root) {

Isn't this an assert?
Also I don't see concurrency for accessing the root, the assertion can be outside the lock.

Yes, I will add a WARN_ON here.

Quoted 107 lines
Quoted 13 lines
kernel/kexec_handover.c +5 -6
+             err = -EINVAL;
+             goto out;
+     }
 
-             new_physxa = kzalloc(sizeof(*physxa), GFP_KERNEL);
-             if (!new_physxa)
-                     return -ENOMEM;
+     current_tree = kho_radix_tree_root;
 
-             xa_init(&new_physxa->phys_bits);
-             physxa = xa_cmpxchg(&track->orders, order, NULL, new_physxa,
-                                 GFP_KERNEL);
+     /* Go from high levels to low levels */

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 251

Quoted 10 lines
kernel/kexec_handover.c +5 -4
+     for (i = tree_level; i >= 0; i--) {
+             idx = kho_radix_get_index(encoded, i);
 
-             err = xa_err(physxa);
-             if (err || physxa) {
-                     xa_destroy(&new_physxa->phys_bits);
-                     kfree(new_physxa);
+             if (i == 0) {
+                     bitmap_table = (struct kho_bitmap_table *)current_tree;
+                     err = kho_radix_set_bitmap(bitmap_table, idx);

I'd consider making the loop until 'i > 0' and putting this outside the loop.

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 254

Quoted 3 lines
kernel/kexec_handover.c +3 -0
+                     goto out;
+             }
+
                if (node->table[idx]) {
                        node = kho_radix_tree(node->table[idx]);
                        continue;
                }

and reduce the indentation for allocating a new table.

Quoted 36 lines
kernel/kexec_handover.c +24 -7
+             if (!current_tree->table[idx]) {
+                     new_tree = kho_alloc_radix_tree();
+                     if (!new_tree) {
+                             err = -ENOMEM;
+                             goto out;
+                     }
 
-                     if (err)
-                             return err;
+                     current_tree->table[idx] =
+                             kho_radix_tree_desc(new_tree);
+                     current_tree = new_tree;
              } else {
-                     physxa = new_physxa;
+                     current_tree = kho_radix_tree(current_tree->table[idx]);
              }
      }
 
-     bits = xa_load_or_alloc(&physxa->phys_bits, pfn_high / PRESERVE_BITS,
-                             sizeof(*bits));
-     if (IS_ERR(bits))
-             return PTR_ERR(bits);
+out:
+     up_write(&kho_radix_tree_root_sem);
+     return err;
+}
+
+static int kho_radix_walk_bitmaps(struct kho_bitmap_table *bit_tlb,
+                               unsigned long encoded,
+                               kho_radix_tree_walk_callback_t cb)
+{
+     unsigned long *bitmap = (unsigned long *)bit_tlb;
+     unsigned int i;
+     int err = 0;
+
+     for_each_set_bit(i, bitmap, PAGE_SIZE * BITS_PER_BYTE) {

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 292

Quoted 10 lines
kernel/kexec_handover.c +8 -1
+             err = cb(encoded | i);
+             if (err)
+                     return err;
+     }
 
-     set_bit(pfn_high % PRESERVE_BITS, bits->preserve);
+     return 0;
+}
+
+static int kho_radix_walk_trees(struct kho_radix_tree *root, unsigned int level,

static int kho_radix_walk_tree(struct kho_radix_tree *parent, ...

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 296

Quoted 4 lines
kernel/kexec_handover.c +4 -0
+                             unsigned long start,
+                             kho_radix_tree_walk_callback_t cb)
+{
+     struct kho_radix_tree *next_tree;
        struct kho_radix_tree *node;
Quoted 1 line

+ struct kho_bitmap_table *bitmap_table;

                                ^ bitmap;

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 299

Quoted 2 lines
kernel/kexec_handover.c +2 -0
+     unsigned long encoded, i;
+     unsigned int level_shift;

This can move to the scope where it's used and 'shift' would be enough.

Quoted 1 line

+ int err = 0;

...

Quoted 10 lines

kernel/kexec_handover.c static int __init kho_parse_enable(char *p) · line 344

Quoted 7 lines
kernel/kexec_handover.c +7 -0
+static int __kho_preserve_order(unsigned long pfn, unsigned int order)
+{
+     unsigned long pa = PFN_PHYS(pfn);
+
+     might_sleep();
+
+     return kho_radix_preserve_page(pa, order);

I don't think that __kho_preserve_order() wrapper is useful, just rename kho_radix_preserve_page to __kho_preserve_order()

Will merge both.

Quoted 12 lines
Quoted 9 lines
kernel/kexec_handover.c +2 -0
+}
+
 /* almost as free_reserved_page(), just don't free the page */
 static void kho_restore_page(struct page *page, unsigned int order)
 {
@@ -224,152 +385,49 @@ struct folio *kho_restore_folio(phys_addr_t phys)
 }
 EXPORT_SYMBOL_GPL(kho_restore_folio);

...

Quoted 9 lines

kernel/kexec_handover.c struct folio *kho_restore_folio(phys_addr_t phys) · line 388

Quoted 2 lines
kernel/kexec_handover.c +1 -1
-static int kho_mem_serialize(struct kho_serialization *ser)
+static int __init kho_radix_walk_trees_memblock_callback(unsigned long encoded)

I wonder if we expect other callbacks for tree traversal?
For now there's only one case when we traverse the tree, so it seems simpler to just merge the code here into kho_radix_walk_bitmaps() and rename kho_radix_walk_trees() and kho_radix_walk_bitmaps() to reflect that they are reserving the preserved memory.

Currently only kho_radix_walk_trees_memblock_callback() is used in tree walking, but having a callback in the tree walking helps for debugging the KHO mem tree. I can imagine that we can have different build options for different callbacks. If there is no big objection, I tend to keep the callback.

Quoted 16 lines
Quoted 16 lines

{

kernel/kexec_handover.c +11 -0
+     unsigned int order;
+     unsigned long pa;
+     struct page *page;
+     int sz;
 
+     pa = kho_radix_decode(encoded, &order);
+     sz = 1 << (order + PAGE_SHIFT);
+     page = phys_to_page(pa);
 
+     /* Reserve the memory preserved in KHO radix tree in memblock */
+     memblock_reserve(pa, sz);
+     memblock_reserved_mark_noinit(pa, sz);
+     page->private = order;
 }
Quoted 3 lines
Quoted 1 line

static void __init kho_mem_deserialize(const void *fdt)

Well, it's not deserialize anymore.

Yeah, I did think about this name too... How about kho_mem_retrieve() ?

Quoted 9 lines

kernel/kexec_handover.c static int kho_debugfs_fdt_add(struct list_head *list, struct dentry *dir, · line 658

Quoted 5 lines

{

kernel/kexec_handover.c +0 -0
@@ -599,6 +657,35 @@ static int kho_debugfs_fdt_add(struct list_head *list, struct dentry *dir,
      return 0;
 }

It seems that a lot of the changes below are not related to changing the mechanism for tracking the preserved memory.

Quoted 5 lines

I'm stopping here.

--
Sincerely yours,
Mike.

Thanks again, Mike.

author
#11 lore raw

PATCH v2 2/3 memblock: kho: Remove KHO notifier usage

In reply to Jason Miu

Remove the KHO notifier registration and callbacks from the memblock subsystem. These notifiers were tied to the former KHO finalize and abort events, which are no longer used.

Memblock now preserves its reserve_mem regions and registers its metadata by calling kho_preserve_phys(), kho_preserve_folio(), and kho_add_subtree() directly within its initialization function.

KHO selftest is also updated with this deprecation of notifier.

---
 include/linux/kexec_handover.h     |  5 ++--
 kernel/kexec_handover.c            |  3 +-
 lib/test_kho.c                     | 28 ++++---------------
 mm/memblock.c                      | 45 +++++++-----------------------
 tools/testing/selftests/kho/init.c | 19 -------------
 5 files changed, 18 insertions(+), 82 deletions(-)
include/linux/kexec_handover.h +2 -3
index bc2f9e060a79..1f2ca09519a1 100644
@@ -27,7 +27,7 @@ bool kho_is_enabled(void);
 int kho_preserve_folio(struct folio *folio);
 int kho_preserve_phys(phys_addr_t phys, size_t size);
 struct folio *kho_restore_folio(phys_addr_t phys);
-int kho_add_subtree(struct kho_serialization *ser, const char *name, void *fdt);
+int kho_add_subtree(const char *name, void *fdt);
 int kho_remove_subtree(const char *name);
 int kho_retrieve_subtree(const char *name, phys_addr_t *phys);
 
@@ -59,8 +59,7 @@ static inline struct folio *kho_restore_folio(phys_addr_t phys)
 	return NULL;
 }
 
-static inline int kho_add_subtree(struct kho_serialization *ser,
-				  const char *name, void *fdt)
+static inline int kho_add_subtree(const char *name, void *fdt)
 {
 	return -EOPNOTSUPP;
 }
kernel/kexec_handover.c +1 -2
index 2fc5975690a7..1138b16fa546 100644
@@ -688,7 +688,6 @@ static struct kho_out kho_out = {
 
 /**
  * kho_add_subtree - record the physical address of a sub FDT in KHO root tree.
- * @ser: serialization control object passed by KHO notifiers.
  * @name: name of the sub tree.
  * @fdt: the sub tree blob.
  *
@@ -701,7 +700,7 @@ static struct kho_out kho_out = {
  *
  * Return: 0 on success, error code on failure
  */
-int kho_add_subtree(struct kho_serialization *ser, const char *name, void *fdt)
+int kho_add_subtree(const char *name, void *fdt)
 {
 	void *root_fdt = page_to_virt(kho_out.ser.fdt);
 	u64 phys = (u64)virt_to_phys(fdt);
lib/test_kho.c +5 -23
index c2eb899c3b45..e4307587a713 100644
@@ -38,33 +38,16 @@ struct kho_test_state {
 
 static struct kho_test_state kho_test_state;
 
-static int kho_test_notifier(struct notifier_block *self, unsigned long cmd,
-			     void *v)
+static int kho_test_preserve(void)
 {
-	struct kho_test_state *state = &kho_test_state;
-	struct kho_serialization *ser = v;
 	int err = 0;
 
-	switch (cmd) {
-	case KEXEC_KHO_ABORT:
-		return NOTIFY_DONE;
-	case KEXEC_KHO_FINALIZE:
-		/* Handled below */
-		break;
-	default:
-		return NOTIFY_BAD;
-	}
-
-	err |= kho_preserve_folio(state->fdt);
-	err |= kho_add_subtree(ser, KHO_TEST_FDT, folio_address(state->fdt));
+	err |= kho_preserve_folio(kho_test_state.fdt);
+	err |= kho_add_subtree(KHO_TEST_FDT, folio_address(kho_test_state.fdt));
 
-	return err ? NOTIFY_BAD : NOTIFY_DONE;
+	return err;
 }
 
-static struct notifier_block kho_test_nb = {
-	.notifier_call = kho_test_notifier,
-};
-
 static int kho_test_save_data(struct kho_test_state *state, void *fdt)
 {
 	phys_addr_t *folios_info __free(kvfree) = NULL;
@@ -191,7 +174,7 @@ static int kho_test_save(void)
 	if (err)
 		return err;
 
-	return register_kho_notifier(&kho_test_nb);
+	return kho_test_preserve();
 }
 
 static int kho_test_restore_data(const void *fdt, int node)
@@ -295,7 +278,6 @@ static void kho_test_cleanup(void)
 
 static void __exit kho_test_exit(void)
 {
-	unregister_kho_notifier(&kho_test_nb);
 	kho_test_cleanup();
 }
 module_exit(kho_test_exit);
mm/memblock.c +10 -35

63 lines not on this page · raw message

tools/testing/selftests/kho/init.c +0 -19
index 8034e24c6bf6..211d6bda8961 100644
@@ -27,22 +27,6 @@ static int mount_filesystems(void)
 	return mount("proc", "/proc", "proc", 0, NULL);
 }
 
-static int kho_enable(void)
-{
-	const char enable[] = "1";
-	int fd;
-
-	fd = open(KHO_FINILIZE, O_RDWR);
-	if (fd < 0)
-		return -1;
-
-	if (write(fd, enable, sizeof(enable)) != sizeof(enable))
-		return 1;
-
-	close(fd);
-	return 0;
-}
-
 static long kexec_file_load(int kernel_fd, int initrd_fd,
 			    unsigned long cmdline_len, const char *cmdline,
 			    unsigned long flags)
@@ -83,9 +67,6 @@ int main(int argc, char *argv[])
 	if (mount_filesystems())
 		goto err_reboot;
 
-	if (kho_enable())
-		goto err_reboot;
-
 	if (kexec_load())
 		goto err_reboot;
 
Signature · 1 line
2.51.0.858.gf9c4a03a3a-goog
author
#12 lore raw

PATCH v2 3/3 kho: Remove notifier system infrastructure

In reply to Jason Miu

Eliminate the core KHO notifier API
functions (register_kho_notifier, unregister_kho_notifier), the kho_event enum, and the notifier chain head from KHO internal structures.

This infrastructure was used to support the now-removed finalize and abort states and is no longer required. Client subsystems now interact with KHO through direct API calls.

---
 include/linux/kexec_handover.h | 22 ----------------------
 kernel/kexec_handover.c        | 15 ---------------
 2 files changed, 37 deletions(-)
include/linux/kexec_handover.h +0 -22
index 1f2ca09519a1..d345f301c57b 100644
@@ -10,16 +10,7 @@ struct kho_scratch {
 	phys_addr_t size;
 };
 
-/* KHO Notifier index */
-enum kho_event {
-	KEXEC_KHO_FINALIZE = 0,
-	KEXEC_KHO_ABORT = 1,
-};
-
 struct folio;
-struct notifier_block;
-
-struct kho_serialization;
 
 #ifdef CONFIG_KEXEC_HANDOVER
 bool kho_is_enabled(void);
@@ -31,9 +22,6 @@ int kho_add_subtree(const char *name, void *fdt);
 int kho_remove_subtree(const char *name);
 int kho_retrieve_subtree(const char *name, phys_addr_t *phys);
 
-int register_kho_notifier(struct notifier_block *nb);
-int unregister_kho_notifier(struct notifier_block *nb);
-
 void kho_memory_init(void);
 
 void kho_populate(phys_addr_t fdt_phys, u64 fdt_len, phys_addr_t scratch_phys,
@@ -74,16 +62,6 @@ static inline int kho_remove_subtree(const char *name)
 	return -EOPNOTSUPP;
 }
 
-static inline int register_kho_notifier(struct notifier_block *nb)
-{
-	return -EOPNOTSUPP;
-}
-
-static inline int unregister_kho_notifier(struct notifier_block *nb)
-{
-	return -EOPNOTSUPP;
-}
-
 static inline void kho_memory_init(void)
 {
 }
kernel/kexec_handover.c +0 -15
index 1138b16fa546..325b83a609fc 100644
@@ -17,7 +17,6 @@
 #include <linux/list.h>
 #include <linux/log2.h>
 #include <linux/memblock.h>
-#include <linux/notifier.h>
 #include <linux/page-isolation.h>
 #include <linux/rwsem.h>
 #include <linux/live_update/abi/kexec_handover.h>
@@ -674,13 +673,11 @@ static int kho_debugfs_fdt_remove(struct list_head *list, const char *name)
 }
 
 struct kho_out {
-	struct blocking_notifier_head chain_head;
 	struct dentry *dir;
 	struct kho_serialization ser;
 };
 
 static struct kho_out kho_out = {
-	.chain_head = BLOCKING_NOTIFIER_INIT(kho_out.chain_head),
 	.ser = {
 		.fdt_list = LIST_HEAD_INIT(kho_out.ser.fdt_list),
 	},
@@ -787,18 +784,6 @@ int kho_remove_subtree(const char *name)
 }
 EXPORT_SYMBOL_GPL(kho_remove_subtree);
 
-int register_kho_notifier(struct notifier_block *nb)
-{
-	return blocking_notifier_chain_register(&kho_out.chain_head, nb);
-}
-EXPORT_SYMBOL_GPL(register_kho_notifier);
-
-int unregister_kho_notifier(struct notifier_block *nb)
-{
-	return blocking_notifier_chain_unregister(&kho_out.chain_head, nb);
-}
-EXPORT_SYMBOL_GPL(unregister_kho_notifier);
-
 /**
  * kho_preserve_folio - preserve a folio across kexec.
  * @folio: folio to preserve.
Signature · 1 line
2.51.0.858.gf9c4a03a3a-goog