kho: make boot time huge page allocation work nicely with KHO

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO radix tree is a data structure that can track the presence or absence of an arbitrary key, with nothing inherently tied to KHO memory preservation tracking. This was one of the design goals of the radix tree. This was done to enable it to be re-used by other users of KHO.

Despite that, the radix tree APIs are very closely tied to KHO memory preservation tracking. Adding a key is done by kho_radix_add_page(), which encodes it as a page tracking operation and takes in PFN and order. kho_radix_del_page() does the same. These functions encode the key internally that goes into the radix tree. kho_radix_walk_tree() does the same by baking the PFN and order into the callback arguments.

Generalize the APIs by taking the key directly and doing the encoding at the callers. Rename the functions to kho_radix_add_key() and kho_radix_del_key(). In practice, this removes a line each from the functions and moves the encoding function call to the callers. Similarly, update kho_radix_tree_walk_callback_t to take the key directly.

To keep the naming convention clearer, rename kho_radix_{encode,decode}_key() to kho_{encode,decode}_radix_key().

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     | 18 +++----
 kernel/liveupdate/kexec_handover.c | 76 ++++++++++++++----------------
 2 files changed, 42 insertions(+), 52 deletions(-)

include/linux/kho_radix_tree.h +6 -12

index 84e918b96e53..f368f3b9f923 100644
@@ -34,30 +34,24 @@ struct kho_radix_tree {
 	struct mutex lock; /* protects the tree's structure and root pointer */
 };
 
-typedef int (*kho_radix_tree_walk_callback_t)(phys_addr_t phys,
-					      unsigned int order);
+typedef int (*kho_radix_tree_walk_callback_t)(unsigned long key);
 
 #ifdef CONFIG_KEXEC_HANDOVER
 
-int kho_radix_add_page(struct kho_radix_tree *tree, unsigned long pfn,
-		       unsigned int order);
-
-void kho_radix_del_page(struct kho_radix_tree *tree, unsigned long pfn,
-			unsigned int order);
-
+int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key);
+void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key);
 int kho_radix_walk_tree(struct kho_radix_tree *tree,
 			kho_radix_tree_walk_callback_t cb);
 
 #else  /* #ifdef CONFIG_KEXEC_HANDOVER */
 
-static inline int kho_radix_add_page(struct kho_radix_tree *tree, long pfn,
-				     unsigned int order)
+static inline int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key)
 {
 	return -EOPNOTSUPP;
 }
 
-static inline void kho_radix_del_page(struct kho_radix_tree *tree,
-				      unsigned long pfn, unsigned int order) { }
+static inline void kho_radix_del_key(struct kho_radix_tree *tree,
+				     unsigned long key) { }
 
 static inline int kho_radix_walk_tree(struct kho_radix_tree *tree,
 				      kho_radix_tree_walk_callback_t cb)

kernel/liveupdate/kexec_handover.c +36 -40

index 33fcf848ef95..ba568d34c5b4 100644
@@ -85,7 +85,7 @@ static struct kho_out kho_out = {
 };
 
 /**
- * kho_radix_encode_key - Encodes a physical address and order into a radix key.
+ * kho_encode_radix_key - Encodes a physical address and order into a radix key.
  * @phys: The physical address of the page.
  * @order: The order of the page.
  *

@@ -95,7 +95,7 @@ static struct kho_out kho_out = {
  *
  * Return: The encoded unsigned long radix key.
  */
-static unsigned long kho_radix_encode_key(phys_addr_t phys, unsigned int order)
+static unsigned long kho_encode_radix_key(phys_addr_t phys, unsigned int order)
 {
 	/* Order bits part */
 	unsigned long h = 1UL << (KHO_ORDER_0_LOG2 - order);

@@ -106,17 +106,17 @@ static unsigned long kho_radix_encode_key(phys_addr_t phys, unsigned int order)
 }
 
 /**
- * kho_radix_decode_key - Decodes a radix key back into a physical address and order.
+ * kho_decode_radix_key - Decodes a radix key back into a physical address and order.
  * @key: The unsigned long key to decode.
  * @order: An output parameter, a pointer to an unsigned int where the decoded
  *         page order will be stored.
  *
- * This function reverses the encoding performed by kho_radix_encode_key(),
+ * This function reverses the encoding performed by kho_encode_radix_key(),
  * extracting the original physical address and page order from a given key.
  *
  * Return: The decoded physical address.
  */
-static phys_addr_t kho_radix_decode_key(unsigned long key, unsigned int *order)
+static phys_addr_t kho_decode_radix_key(unsigned long key, unsigned int *order)
 {
 	unsigned int order_bit = fls64(key);
 	phys_addr_t phys;

@@ -144,24 +144,21 @@ static unsigned long kho_radix_get_table_index(unsigned long key,
 }
 
 /**
- * kho_radix_add_page - Marks a page as preserved in the radix tree.
+ * kho_radix_add_key - Add a key to the radix tree.
  * @tree: The KHO radix tree.
- * @pfn: The page frame number of the page to preserve.
- * @order: The order of the page.
+ * @key: The key to add.
  *
- * This function traverses the radix tree based on the key derived from @pfn
- * and @order. It sets the corresponding bit in the leaf bitmap to mark the
- * page for preservation. If intermediate nodes do not exist along the path,
- * they are allocated and added to the tree.
+ * This function traverses the radix tree based on the key provided. It sets the
+ * corresponding bit in the leaf bitmap to mark the key as present. If
+ * intermediate nodes do not exist along the path, they are allocated and added
+ * to the tree.
  *
  * Return: 0 on success, or a negative error code on failure.
  */
-int kho_radix_add_page(struct kho_radix_tree *tree,
-		       unsigned long pfn, unsigned int order)
+int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key)
 {
 	/* Newly allocated nodes for error cleanup */
 	struct kho_radix_node *intermediate_nodes[KHO_TREE_MAX_DEPTH] = { 0 };
-	unsigned long key = kho_radix_encode_key(PFN_PHYS(pfn), order);
 	struct kho_radix_node *anchor_node = NULL;
 	struct kho_radix_node *node = tree->root;
 	struct kho_radix_node *new_node;

@@ -224,22 +221,19 @@ int kho_radix_add_page(struct kho_radix_tree *tree,
 
 	return err;
 }
-EXPORT_SYMBOL_GPL(kho_radix_add_page);
+EXPORT_SYMBOL_GPL(kho_radix_add_key);
 
 /**
- * kho_radix_del_page - Removes a page's preservation status from the radix tree.
+ * kho_radix_del_key - Removes the key from the radix tree.
  * @tree: The KHO radix tree.
- * @pfn: The page frame number of the page to unpreserve.
- * @order: The order of the page.
+ * @key: The key to remove.
  *
  * This function traverses the radix tree and clears the bit corresponding to
- * the page, effectively removing its "preserved" status. It does not free
- * the tree's intermediate nodes, even if they become empty.
+ * the key, effectively removing it from the tree. It does not free the tree's
+ * intermediate nodes, even if they become empty.
  */
-void kho_radix_del_page(struct kho_radix_tree *tree, unsigned long pfn,
-			unsigned int order)
+void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key)
 {
-	unsigned long key = kho_radix_encode_key(PFN_PHYS(pfn), order);
 	struct kho_radix_node *node = tree->root;
 	struct kho_radix_leaf *leaf;
 	unsigned int i, idx;

@@ -270,21 +264,18 @@ void kho_radix_del_page(struct kho_radix_tree *tree, unsigned long pfn,
 	idx = kho_radix_get_bitmap_index(key);
 	__clear_bit(idx, leaf->bitmap);
 }
-EXPORT_SYMBOL_GPL(kho_radix_del_page);
+EXPORT_SYMBOL_GPL(kho_radix_del_key);
 
 static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf,
 			       unsigned long key,
 			       kho_radix_tree_walk_callback_t cb)
 {
 	unsigned long *bitmap = (unsigned long *)leaf;
-	unsigned int order;
-	phys_addr_t phys;
 	unsigned int i;
 	int err;
 
 	for_each_set_bit(i, bitmap, PAGE_SIZE * BITS_PER_BYTE) {
-		phys = kho_radix_decode_key(key | i, &order);
-		err = cb(phys, order);
+		err = cb(key | i);
 		if (err)
 			return err;
 	}

@@ -332,15 +323,14 @@ static int __kho_radix_walk_tree(struct kho_radix_node *root,
 }
 
 /**
- * kho_radix_walk_tree - Traverses the radix tree and calls a callback for each preserved page.
+ * kho_radix_walk_tree - Traverses the radix tree and calls a callback for each key.
  * @tree: A pointer to the KHO radix tree to walk.
  * @cb: A callback function of type kho_radix_tree_walk_callback_t that will be
- *      invoked for each preserved page found in the tree. The callback receives
- *      the physical address and order of the preserved page.
+ *      invoked for each key in the tree.
  *
  * This function walks the radix tree, searching from the specified top level
- * down to the lowest level (level 0). For each preserved page found, it invokes
- * the provided callback, passing the page's physical address and order.
+ * down to the lowest level (level 0). For each key found, it invokes the
+ * provided callback.
  *
  * Return: 0 if the walk completed the specified tree, or the non-zero return
  *         value from the callback that stopped the walk.

@@ -365,7 +355,8 @@ static void __kho_unpreserve(struct kho_radix_tree *tree,
 	while (pfn < end_pfn) {
 		order = min(count_trailing_zeros(pfn), ilog2(end_pfn - pfn));
 
-		kho_radix_del_page(tree, pfn, order);
+		kho_radix_del_key(tree, kho_encode_radix_key(PFN_PHYS(pfn),
+							     order));
 
 		pfn += 1 << order;
 	}

@@ -498,13 +489,16 @@ static struct page *__init kho_get_preserved_page(phys_addr_t phys,
 	return pfn_to_page(pfn);
 }
 
-static int __init kho_preserved_memory_reserve(phys_addr_t phys,
-					       unsigned int order)
+static int __init kho_preserved_memory_reserve(unsigned long key)
 {
 	union kho_page_info info;
 	struct page *page;
+	unsigned int order;
+	phys_addr_t phys;
 	u64 sz;
 
+	phys = kho_decode_radix_key(key, &order);
+
 	sz = 1 << (order + PAGE_SHIFT);
 	page = kho_get_preserved_page(phys, order);
 

@@ -858,7 +852,8 @@ int kho_preserve_folio(struct folio *folio)
 	if (WARN_ON(kho_scratch_overlap(pfn << PAGE_SHIFT, PAGE_SIZE << order)))
 		return -EINVAL;
 
-	return kho_radix_add_page(tree, pfn, order);
+	return kho_radix_add_key(tree, kho_encode_radix_key(PFN_PHYS(pfn),
+							    order));
 }
 EXPORT_SYMBOL_GPL(kho_preserve_folio);
 

@@ -876,7 +871,7 @@ void kho_unpreserve_folio(struct folio *folio)
 	const unsigned long pfn = folio_pfn(folio);
 	const unsigned int order = folio_order(folio);
 
-	kho_radix_del_page(tree, pfn, order);
+	kho_radix_del_key(tree, kho_encode_radix_key(PFN_PHYS(pfn), order));
 }
 EXPORT_SYMBOL_GPL(kho_unpreserve_folio);
 

@@ -916,7 +911,8 @@ int kho_preserve_pages(struct page *page, unsigned long nr_pages)
 		while (pfn_to_nid(pfn) != pfn_to_nid(pfn + (1UL << order) - 1))
 			order--;
 
-		err = kho_radix_add_page(tree, pfn, order);
+		err = kho_radix_add_key(tree, kho_encode_radix_key(PFN_PHYS(pfn),
+								   order));
 		if (err) {
 			failed_pfn = pfn;
 			break;

Signature · 1 line

2.54.0.545.g6539524ca2-goog

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO radix tree is a data structure that can track the presence or absence of an arbitrary key, with nothing inherently tied to KHO memory preservation tracking. This was one of the design goals of the radix tree. This was done to enable it to be re-used by other users of KHO.

+ * kho_radix_add_key - Add a key to the radix tree.
* @tree: The KHO radix tree.
+ * @key: The key to add.
*
+ * This function traverses the radix tree based on the key provided. It sets the
+ * corresponding bit in the leaf bitmap to mark the key as present. If
+ * intermediate nodes do not exist along the path, they are allocated and added
+ * to the tree.

Quoted 6 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO radix tree is a data structure that can track the presence or absence of an arbitrary key, with nothing inherently tied to KHO memory preservation tracking. This was one of the design goals of the radix tree. This was done to enable it to be re-used by other users of KHO.

"Arbitrary key": Not quite the complete 64-bits, rather 64 - PAGE_SIZE, correct?

Quoted 9 lines

+ * kho_radix_add_key - Add a key to the radix tree.
* @tree: The KHO radix tree.
+ * @key: The key to add.
*
+ * This function traverses the radix tree based on the key provided. It sets the
+ * corresponding bit in the leaf bitmap to mark the key as present. If
+ * intermediate nodes do not exist along the path, they are allocated and added
+ * to the tree.

Consider adding a note on the key-width limitation.

Quoted 10 lines · Jork Loeser

Quoted 6 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO radix tree is a data structure that can track the presence or absence of an arbitrary key, with nothing inherently tied to KHO memory preservation tracking. This was one of the design goals of the radix tree. This was done to enable it to be re-used by other users of KHO.

"Arbitrary key": Not quite the complete 64-bits, rather 64 - PAGE_SIZE,

correct?

Right, 64 - PAGE_SHIFT.

Quoted 6 lines

Quoted 6 lines

+ * kho_radix_add_key - Add a key to the radix tree.
* @tree: The KHO radix tree.
+ * @key: The key to add.
*
+ * This function traverses the radix tree based on the key provided.

It sets the

Quoted 2 lines

Quoted 2 lines

+ * corresponding bit in the leaf bitmap to mark the key as present. If
+ * intermediate nodes do not exist along the path, they are allocated

and added

Quoted 3 lines

Quoted 1 line

+ * to the tree.

Consider adding a note on the key-width limitation.

I think adding a runtime check would also be a good idea here.

--
Regards,
Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO radix tree is a data structure that can track the presence or absence of an arbitrary key, with nothing inherently tied to KHO memory preservation tracking. This was one of the design goals of the radix tree. This was done to enable it to be re-used by other users of KHO.

Despite that, the radix tree APIs are very closely tied to KHO memory preservation tracking. Adding a key is done by kho_radix_add_page(), which encodes it as a page tracking operation and takes in PFN and order. kho_radix_del_page() does the same. These functions encode the key internally that goes into the radix tree. kho_radix_walk_tree() does the same by baking the PFN and order into the callback arguments.

Generalize the APIs by taking the key directly and doing the encoding at the callers. Rename the functions to kho_radix_add_key() and kho_radix_del_key(). In practice, this removes a line each from the functions and moves the encoding function call to the callers. Similarly, update kho_radix_tree_walk_callback_t to take the key directly.

To keep the naming convention clearer, rename kho_radix_{encode,decode}_key() to kho_{encode,decode}_radix_key().

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     | 18 +++----
 kernel/liveupdate/kexec_handover.c | 76 ++++++++++++++----------------
 2 files changed, 42 insertions(+), 52 deletions(-)

include/linux/kho_radix_tree.h +0 -0

index 84e918b96e53..f368f3b9f923 100644

include/linux/kho_radix_tree.h +0 -0

  * @phys: The physical address of the page.
  * @order: The order of the page.
  *

include/linux/kho_radix_tree.h +1 -1

@@ -144,24 +144,21 @@ static unsigned long kho_radix_get_table_index(unsigned long key,
 }
 
 /**
- * kho_radix_add_page - Marks a page as preserved in the radix tree.
+ * kho_radix_add_key - Add a key to the radix tree.

include/linux/kho_radix_tree.h +3 -0

+ * corresponding bit in the leaf bitmap to mark the key as present. If
+ * intermediate nodes do not exist along the path, they are allocated and added
+ * to the tree.
  *
  * Return: 0 on success, or a negative error code on failure.
  */

Quoted 37 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO radix tree is a data structure that can track the presence or absence of an arbitrary key, with nothing inherently tied to KHO memory preservation tracking. This was one of the design goals of the radix tree. This was done to enable it to be re-used by other users of KHO.

Despite that, the radix tree APIs are very closely tied to KHO memory preservation tracking. Adding a key is done by kho_radix_add_page(), which encodes it as a page tracking operation and takes in PFN and order. kho_radix_del_page() does the same. These functions encode the key internally that goes into the radix tree. kho_radix_walk_tree() does the same by baking the PFN and order into the callback arguments.

Generalize the APIs by taking the key directly and doing the encoding at the callers. Rename the functions to kho_radix_add_key() and kho_radix_del_key(). In practice, this removes a line each from the functions and moves the encoding function call to the callers. Similarly, update kho_radix_tree_walk_callback_t to take the key directly.

To keep the naming convention clearer, rename kho_radix_{encode,decode}_key() to kho_{encode,decode}_radix_key().

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     | 18 +++----
 kernel/liveupdate/kexec_handover.c | 76 ++++++++++++++----------------
 2 files changed, 42 insertions(+), 52 deletions(-)

include/linux/kho_radix_tree.h +0 -0

index 84e918b96e53..f368f3b9f923 100644
@@ -85,7 +85,7 @@ static struct kho_out kho_out = {
 };
 

include/linux/kho_radix_tree.h static struct kho_out kho_out = { · line 88

Quoted 3 lines

include/linux/kho_radix_tree.h +1 -1

 /**
- * kho_radix_encode_key - Encodes a physical address and order into a radix key.
+ * kho_encode_radix_key - Encodes a physical address and order into a radix key.

Let's keep kho_radix_ prefix for namespasing please. This is the common practice these days.

Quoted 4 lines

include/linux/kho_radix_tree.h +0 -0

  * @phys: The physical address of the page.
  * @order: The order of the page.
  *

...

Quoted 3 lines

include/linux/kho_radix_tree.h +0 -0

@@ -144,24 +144,21 @@ static unsigned long kho_radix_get_table_index(unsigned long key,
 }
 

include/linux/kho_radix_tree.h static unsigned long kho_radix_get_table_index(unsigned long key, · line 151

Quoted 13 lines

include/linux/kho_radix_tree.h +3 -7

 /**
- * kho_radix_add_page - Marks a page as preserved in the radix tree.
+ * kho_radix_add_key - Add a key to the radix tree.
  * @tree: The KHO radix tree.
- * @pfn: The page frame number of the page to preserve.
- * @order: The order of the page.
+ * @key: The key to add.
  *
- * This function traverses the radix tree based on the key derived from @pfn
- * and @order. It sets the corresponding bit in the leaf bitmap to mark the
- * page for preservation. If intermediate nodes do not exist along the path,
- * they are allocated and added to the tree.
+ * This function traverses the radix tree based on the key provided. It sets the

Nit: @key here and in
the comments below.

Quoted 7 lines

include/linux/kho_radix_tree.h +3 -0

+ * corresponding bit in the leaf bitmap to mark the key as present. If
+ * intermediate nodes do not exist along the path, they are allocated and added
+ * to the tree.
  *
  * Return: 0 on success, or a negative error code on failure.
  */

Quoted 38 lines · Mike Rapoport

Quoted 37 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO radix tree is a data structure that can track the presence or absence of an arbitrary key, with nothing inherently tied to KHO memory preservation tracking. This was one of the design goals of the radix tree. This was done to enable it to be re-used by other users of KHO.

Despite that, the radix tree APIs are very closely tied to KHO memory preservation tracking. Adding a key is done by kho_radix_add_page(), which encodes it as a page tracking operation and takes in PFN and order. kho_radix_del_page() does the same. These functions encode the key internally that goes into the radix tree. kho_radix_walk_tree() does the same by baking the PFN and order into the callback arguments.

Generalize the APIs by taking the key directly and doing the encoding at the callers. Rename the functions to kho_radix_add_key() and kho_radix_del_key(). In practice, this removes a line each from the functions and moves the encoding function call to the callers. Similarly, update kho_radix_tree_walk_callback_t to take the key directly.

To keep the naming convention clearer, rename kho_radix_{encode,decode}_key() to kho_{encode,decode}_radix_key().

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     | 18 +++----
 kernel/liveupdate/kexec_handover.c | 76 ++++++++++++++----------------
 2 files changed, 42 insertions(+), 52 deletions(-)

include/linux/kho_radix_tree.h +0 -0

index 84e918b96e53..f368f3b9f923 100644
@@ -85,7 +85,7 @@ static struct kho_out kho_out = {
 };
 

Quoted 6 lines

include/linux/kho_radix_tree.h static struct kho_out kho_out = { · line 88

Quoted 3 lines

include/linux/kho_radix_tree.h +1 -1

 /**
- * kho_radix_encode_key - Encodes a physical address and order into a radix key.
+ * kho_encode_radix_key - Encodes a physical address and order into a radix key.

Let's keep kho_radix_ prefix for namespasing please. This is the common practice these days.

I am keeping the namespacing, just moving it out of the "kho_radix" namespace to "kho" namespace. The mental model is that this function has nothing to do with the radix tree. It is just something KHO uses for one of its radix tree, so it should live in the "kho" namespace not "kho_radix".

Does that make sense? I can add this explanation to the commit message as well.

Signature · 2 lines

Regards,
Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

This allows other functions to also use the radix tree. While at it, also use kho_get_mem_map_phys() instead of duplicating the code to get the radix tree root from the FDT.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 kernel/liveupdate/kexec_handover.c | 27 ++++++++-------------------
 1 file changed, 8 insertions(+), 19 deletions(-)

kernel/liveupdate/kexec_handover.c +1 -9

index ba568d34c5b4..5758dc6fab5d 100644
@@ -1294,6 +1294,7 @@ struct kho_in {
 	char previous_release[__NEW_UTS_LEN + 1];
 	u32 kexec_count;
 	struct kho_debugfs dbg;
+	struct kho_radix_tree radix_tree;
 };
 
 static struct kho_in kho_in = {

@@ -1373,24 +1374,10 @@ EXPORT_SYMBOL_GPL(kho_retrieve_subtree);
 
 static int __init kho_mem_retrieve(const void *fdt)
 {
-	struct kho_radix_tree tree;
-	const phys_addr_t *mem;
-	int len;
-
-	/* Retrieve the KHO radix tree from passed-in FDT. */
-	mem = fdt_getprop(fdt, 0, KHO_FDT_MEMORY_MAP_PROP_NAME, &len);
-
-	if (!mem || len != sizeof(*mem)) {
-		pr_err("failed to get preserved KHO memory tree\n");

kernel/liveupdate/kexec_handover.c +3 -0

+	mutex_init(&kho_in.radix_tree.lock);
+	return kho_radix_walk_tree(&kho_in.radix_tree,
+				   kho_preserved_memory_reserve);
 }
 
 static __init int kho_out_fdt_setup(void)

kernel/liveupdate/kexec_handover.c +1 -0

+		}
 	} else {
 		kho_reserve_scratch();
 	}

Signature · 1 line

2.54.0.545.g6539524ca2-goog

Quoted 41 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

This allows other functions to also use the radix tree. While at it, also use kho_get_mem_map_phys() instead of duplicating the code to get the radix tree root from the FDT.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 kernel/liveupdate/kexec_handover.c | 27 ++++++++-------------------
 1 file changed, 8 insertions(+), 19 deletions(-)

kernel/liveupdate/kexec_handover.c +1 -14

index ba568d34c5b4..5758dc6fab5d 100644
@@ -1294,6 +1294,7 @@ struct kho_in {
 	char previous_release[__NEW_UTS_LEN + 1];
 	u32 kexec_count;
 	struct kho_debugfs dbg;
+	struct kho_radix_tree radix_tree;
 };
 
 static struct kho_in kho_in = {

@@ -1373,24 +1374,10 @@ EXPORT_SYMBOL_GPL(kho_retrieve_subtree);
 
 static int __init kho_mem_retrieve(const void *fdt)
 {
-	struct kho_radix_tree tree;
-	const phys_addr_t *mem;
-	int len;
-
-	/* Retrieve the KHO radix tree from passed-in FDT. */
-	mem = fdt_getprop(fdt, 0, KHO_FDT_MEMORY_MAP_PROP_NAME, &len);
-
-	if (!mem || len != sizeof(*mem)) {
-		pr_err("failed to get preserved KHO memory tree\n");
-		return -ENOENT;
-	}
-
-	if (!*mem)
-		return -EINVAL;

kernel/liveupdate/kexec_handover.c EXPORT_SYMBOL_GPL(kho_retrieve_subtree); · line 1377

Quoted 5 lines

kernel/liveupdate/kexec_handover.c +1 -4

-
-	tree.root = phys_to_virt(*mem);
-	mutex_init(&tree.lock);
-	return kho_radix_walk_tree(&tree, kho_preserved_memory_reserve);
+	kho_in.radix_tree.root = phys_to_virt(kho_get_mem_map_phys(fdt));

Do we really want to remove an explicit check for 0 and get a WARN() in kho_radix_walk_tree()?

Quoted 11 lines

kernel/liveupdate/kexec_handover.c +3 -0

+	mutex_init(&kho_in.radix_tree.lock);
+	return kho_radix_walk_tree(&kho_in.radix_tree,
+				   kho_preserved_memory_reserve);
 }
 
 static __init int kho_out_fdt_setup(void)

@@ -1597,8 +1584,10 @@ void __init kho_memory_init(void)
 	if (kho_in.scratch_phys) {
 		kho_scratch = phys_to_virt(kho_in.scratch_phys);
 

kernel/liveupdate/kexec_handover.c void __init kho_memory_init(void) · line 1589

Quoted 4 lines

kernel/liveupdate/kexec_handover.c +2 -1

-		if (kho_mem_retrieve(kho_get_fdt()))
+		if (kho_mem_retrieve(kho_get_fdt())) {
 			kho_in.fdt_phys = 0;
+			kho_in.radix_tree.root = NULL;

I'd make kho_mem_retrieve() void and put these there.

Quoted 8 lines

kernel/liveupdate/kexec_handover.c +1 -0

+		}
 	} else {
 		kho_reserve_scratch();
 	}

Signature · 1 line

2.54.0.545.g6539524ca2-goog

Quoted 42 lines · Mike Rapoport

Quoted 41 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

This allows other functions to also use the radix tree. While at it, also use kho_get_mem_map_phys() instead of duplicating the code to get the radix tree root from the FDT.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 kernel/liveupdate/kexec_handover.c | 27 ++++++++-------------------
 1 file changed, 8 insertions(+), 19 deletions(-)

kernel/liveupdate/kexec_handover.c +1 -14

index ba568d34c5b4..5758dc6fab5d 100644
@@ -1294,6 +1294,7 @@ struct kho_in {
 	char previous_release[__NEW_UTS_LEN + 1];
 	u32 kexec_count;
 	struct kho_debugfs dbg;
+	struct kho_radix_tree radix_tree;
 };
 
 static struct kho_in kho_in = {

@@ -1373,24 +1374,10 @@ EXPORT_SYMBOL_GPL(kho_retrieve_subtree);
 
 static int __init kho_mem_retrieve(const void *fdt)
 {
-	struct kho_radix_tree tree;
-	const phys_addr_t *mem;
-	int len;
-
-	/* Retrieve the KHO radix tree from passed-in FDT. */
-	mem = fdt_getprop(fdt, 0, KHO_FDT_MEMORY_MAP_PROP_NAME, &len);
-
-	if (!mem || len != sizeof(*mem)) {
-		pr_err("failed to get preserved KHO memory tree\n");
-		return -ENOENT;
-	}
-
-	if (!*mem)
-		return -EINVAL;

Quoted 8 lines

kernel/liveupdate/kexec_handover.c EXPORT_SYMBOL_GPL(kho_retrieve_subtree); · line 1377

Quoted 5 lines

kernel/liveupdate/kexec_handover.c +1 -4

-
-	tree.root = phys_to_virt(*mem);
-	mutex_init(&tree.lock);
-	return kho_radix_walk_tree(&tree, kho_preserved_memory_reserve);
+	kho_in.radix_tree.root = phys_to_virt(kho_get_mem_map_phys(fdt));

Do we really want to remove an explicit check for 0 and get a WARN() in kho_radix_walk_tree()?

If mem_map_phys is 0 then kho_populate() never sets kho_in.scratch_phys and thus kho_mem_retrieve() never gets called. So here it will never be 0, and if it is, a WARN() is certainly warranted.

Perhaps I should add a comment since this isn't so obvious?

Quoted 11 lines

Quoted 11 lines

kernel/liveupdate/kexec_handover.c +3 -0

+	mutex_init(&kho_in.radix_tree.lock);
+	return kho_radix_walk_tree(&kho_in.radix_tree,
+				   kho_preserved_memory_reserve);
 }
 
 static __init int kho_out_fdt_setup(void)

@@ -1597,8 +1584,10 @@ void __init kho_memory_init(void)
 	if (kho_in.scratch_phys) {
 		kho_scratch = phys_to_virt(kho_in.scratch_phys);
 

Quoted 6 lines

kernel/liveupdate/kexec_handover.c void __init kho_memory_init(void) · line 1589

Quoted 4 lines

kernel/liveupdate/kexec_handover.c +2 -1

-		if (kho_mem_retrieve(kho_get_fdt()))
+		if (kho_mem_retrieve(kho_get_fdt())) {
 			kho_in.fdt_phys = 0;
+			kho_in.radix_tree.root = NULL;

I'd make kho_mem_retrieve() void and put these there.

Sure, will do.

Quoted 8 lines

Quoted 8 lines

kernel/liveupdate/kexec_handover.c +1 -0

+		}
 	} else {
 		kho_reserve_scratch();
 	}

Signature · 1 line

2.54.0.545.g6539524ca2-goog

Signature · 2 lines

Regards,
Pratyush Yadav

Quoted 42 lines · Mike Rapoport

Quoted 41 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

This allows other functions to also use the radix tree. While at it, also use kho_get_mem_map_phys() instead of duplicating the code to get the radix tree root from the FDT.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 kernel/liveupdate/kexec_handover.c | 27 ++++++++-------------------
 1 file changed, 8 insertions(+), 19 deletions(-)

kernel/liveupdate/kexec_handover.c +1 -14

index ba568d34c5b4..5758dc6fab5d 100644
@@ -1294,6 +1294,7 @@ struct kho_in {
 	char previous_release[__NEW_UTS_LEN + 1];
 	u32 kexec_count;
 	struct kho_debugfs dbg;
+	struct kho_radix_tree radix_tree;
 };
 
 static struct kho_in kho_in = {

@@ -1373,24 +1374,10 @@ EXPORT_SYMBOL_GPL(kho_retrieve_subtree);
 
 static int __init kho_mem_retrieve(const void *fdt)
 {
-	struct kho_radix_tree tree;
-	const phys_addr_t *mem;
-	int len;
-
-	/* Retrieve the KHO radix tree from passed-in FDT. */
-	mem = fdt_getprop(fdt, 0, KHO_FDT_MEMORY_MAP_PROP_NAME, &len);
-
-	if (!mem || len != sizeof(*mem)) {
-		pr_err("failed to get preserved KHO memory tree\n");
-		return -ENOENT;
-	}
-
-	if (!*mem)
-		return -EINVAL;

Quoted 8 lines

kernel/liveupdate/kexec_handover.c EXPORT_SYMBOL_GPL(kho_retrieve_subtree); · line 1377

Quoted 5 lines

kernel/liveupdate/kexec_handover.c +1 -4

-
-	tree.root = phys_to_virt(*mem);
-	mutex_init(&tree.lock);
-	return kho_radix_walk_tree(&tree, kho_preserved_memory_reserve);
+	kho_in.radix_tree.root = phys_to_virt(kho_get_mem_map_phys(fdt));

Do we really want to remove an explicit check for 0 and get a WARN() in kho_radix_walk_tree()?

If mem_map_phys is 0 then kho_populate() never sets kho_in.scratch_phys and thus kho_mem_retrieve() never gets called. So here it will never be 0, and if it is, a WARN() is certainly warranted.

Perhaps I should add a comment since this isn't so obvious?

Quoted 11 lines

Quoted 11 lines

kernel/liveupdate/kexec_handover.c +3 -0

+	mutex_init(&kho_in.radix_tree.lock);
+	return kho_radix_walk_tree(&kho_in.radix_tree,
+				   kho_preserved_memory_reserve);
 }
 
 static __init int kho_out_fdt_setup(void)

@@ -1597,8 +1584,10 @@ void __init kho_memory_init(void)
 	if (kho_in.scratch_phys) {
 		kho_scratch = phys_to_virt(kho_in.scratch_phys);
 

Quoted 6 lines

kernel/liveupdate/kexec_handover.c void __init kho_memory_init(void) · line 1589

Quoted 4 lines

kernel/liveupdate/kexec_handover.c +2 -1

-		if (kho_mem_retrieve(kho_get_fdt()))
+		if (kho_mem_retrieve(kho_get_fdt())) {
 			kho_in.fdt_phys = 0;
+			kho_in.radix_tree.root = NULL;

I'd make kho_mem_retrieve() void and put these there.

Sure, will do.

Quoted 9 lines

Quoted 9 lines

kernel/liveupdate/kexec_handover.c +1 -0

+		}
 	} else {
 		kho_reserve_scratch();
 	}

Signature · 1 line

2.54.0.545.g6539524ca2-goog

Signature · 2 lines

Regards,
Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

A future commit will add more callbacks for the KHO radix tree. Add a struct for collecting the callbacks.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     | 15 ++++++++++++---
 kernel/liveupdate/kexec_handover.c | 29 ++++++++++++++++-------------
 2 files changed, 28 insertions(+), 16 deletions(-)

include/linux/kho_radix_tree.h +12 -3

index f368f3b9f923..030da6399d28 100644
@@ -34,14 +34,23 @@ struct kho_radix_tree {
 	struct mutex lock; /* protects the tree's structure and root pointer */
 };
 
-typedef int (*kho_radix_tree_walk_callback_t)(unsigned long key);
+/**
+ * struct kho_radix_walk_cb - Callbacks for KHO radix tree walk.
+ * @key:      Called on each present key in the radix tree.
+ *
+ * For each callback, a return value of 0 continues the walk and a non-zero
+ * return value is directly returned to the caller.
+ */
+struct kho_radix_walk_cb {
+	int (*key)(unsigned long key);
+};
 
 #ifdef CONFIG_KEXEC_HANDOVER
 
 int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key);
 void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key);
 int kho_radix_walk_tree(struct kho_radix_tree *tree,
-			kho_radix_tree_walk_callback_t cb);
+			const struct kho_radix_walk_cb *cb);
 
 #else  /* #ifdef CONFIG_KEXEC_HANDOVER */
 

@@ -54,7 +63,7 @@ static inline void kho_radix_del_key(struct kho_radix_tree *tree,
 				     unsigned long key) { }
 
 static inline int kho_radix_walk_tree(struct kho_radix_tree *tree,
-				      kho_radix_tree_walk_callback_t cb)
+				      const struct kho_radix_walk_cb *cb)
 {
 	return -EOPNOTSUPP;
 }

kernel/liveupdate/kexec_handover.c +2 -3

index 5758dc6fab5d..4a5d1b47799c 100644
@@ -266,16 +266,18 @@ void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key)
 }
 EXPORT_SYMBOL_GPL(kho_radix_del_key);
 
-static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf,
-			       unsigned long key,
-			       kho_radix_tree_walk_callback_t cb)
+static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf, unsigned long key,
+			       const struct kho_radix_walk_cb *cb)
 {

kernel/liveupdate/kexec_handover.c +0 -0

 		if (err)
 			return err;
 	}

Quoted 7 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

A future commit will add more callbacks for the KHO radix tree. Add a struct for collecting the callbacks.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---

Quoted 16 lines

kernel/liveupdate/kexec_handover.c +2 -3

@@ -266,16 +266,18 @@ void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key)
 }
 EXPORT_SYMBOL_GPL(kho_radix_del_key);
 
-static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf,
-			       unsigned long key,
-			       kho_radix_tree_walk_callback_t cb)
+static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf, unsigned long key,
+			       const struct kho_radix_walk_cb *cb)
 {
 	unsigned long *bitmap = (unsigned long *)leaf;
 	unsigned int i;
 	int err;
 

kernel/liveupdate/kexec_handover.c void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key) · line 280

Quoted 6 lines

kernel/liveupdate/kexec_handover.c +4 -1

+	if (!cb->key)
+		return 0;
+
 	for_each_set_bit(i, bitmap, PAGE_SIZE * BITS_PER_BYTE) {
-		err = cb(key | i);
+		err = cb->key(key | i);

key(key) reads weird :)
Can't say I have a good name, maybe key_action()?

Quoted 4 lines

kernel/liveupdate/kexec_handover.c +0 -0

 		if (err)
 			return err;
 	}

Quoted 8 lines · Mike Rapoport

Quoted 7 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

A future commit will add more callbacks for the KHO radix tree. Add a struct for collecting the callbacks.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---

[...]

Quoted 16 lines

Quoted 16 lines

kernel/liveupdate/kexec_handover.c +2 -3

@@ -266,16 +266,18 @@ void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key)
 }
 EXPORT_SYMBOL_GPL(kho_radix_del_key);
 
-static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf,
-			       unsigned long key,
-			       kho_radix_tree_walk_callback_t cb)
+static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf, unsigned long key,
+			       const struct kho_radix_walk_cb *cb)
 {
 	unsigned long *bitmap = (unsigned long *)leaf;
 	unsigned int i;
 	int err;
 

Quoted 9 lines

kernel/liveupdate/kexec_handover.c void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key) · line 280

Quoted 6 lines

kernel/liveupdate/kexec_handover.c +4 -1

+	if (!cb->key)
+		return 0;
+
 	for_each_set_bit(i, bitmap, PAGE_SIZE * BITS_PER_BYTE) {
-		err = cb(key | i);
+		err = cb->key(key | i);

key(key) reads weird :)
Can't say I have a good name, maybe key_action()?

I thought the context of it being under a callback struct would make it more obvious. I don't like key_action() much better TBH, but I don't have a strong opinion. Perhaps Pasha can suggest a 3rd option and we pick on randomly ;-)

Quoted 4 lines

Quoted 4 lines

kernel/liveupdate/kexec_handover.c +0 -0

 		if (err)
 			return err;
 	}

Signature · 2 lines

Regards,
Pratyush Yadav

Quoted 37 lines · Pratyush Yadav

Quoted 8 lines · Mike Rapoport

Quoted 7 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

A future commit will add more callbacks for the KHO radix tree. Add a struct for collecting the callbacks.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---

[...]

Quoted 25 lines

Quoted 12 lines

kernel/liveupdate/kexec_handover.c +2 -3

@@ -266,16 +266,18 @@ void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key)
 }
 EXPORT_SYMBOL_GPL(kho_radix_del_key);
 
-static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf,
-			       unsigned long key,
-			       kho_radix_tree_walk_callback_t cb)
+static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf, unsigned long key,
+			       const struct kho_radix_walk_cb *cb)
 {

kernel/liveupdate/kexec_handover.c void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key) · line 280

Quoted 10 lines

kernel/liveupdate/kexec_handover.c +4 -1

 	unsigned long *bitmap = (unsigned long *)leaf;
 	unsigned int i;
 	int err;
 
+	if (!cb->key)
+		return 0;
+
 	for_each_set_bit(i, bitmap, PAGE_SIZE * BITS_PER_BYTE) {
-		err = cb(key | i);
+		err = cb->key(key | i);

key(key) reads weird :)
Can't say I have a good name, maybe key_action()?

Quoted 4 lines

I thought the context of it being under a callback struct would make it more obvious. I don't like key_action() much better TBH, but I don't have a strong opinion. Perhaps Pasha can suggest a 3rd option and we pick on randomly ;-)

Another option I thought is to call them ->leaf() and ->node().

Quoted 38 lines · Mike Rapoport

Quoted 37 lines · Pratyush Yadav

Quoted 8 lines · Mike Rapoport

Quoted 7 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

A future commit will add more callbacks for the KHO radix tree. Add a struct for collecting the callbacks.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---

[...]

Quoted 25 lines

Quoted 12 lines

kernel/liveupdate/kexec_handover.c +2 -3

@@ -266,16 +266,18 @@ void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key)
 }
 EXPORT_SYMBOL_GPL(kho_radix_del_key);
 
-static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf,
-			       unsigned long key,
-			       kho_radix_tree_walk_callback_t cb)
+static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf, unsigned long key,
+			       const struct kho_radix_walk_cb *cb)
 {

kernel/liveupdate/kexec_handover.c void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key) · line 280

Quoted 10 lines

kernel/liveupdate/kexec_handover.c +4 -1

 	unsigned long *bitmap = (unsigned long *)leaf;
 	unsigned int i;
 	int err;
 
+	if (!cb->key)
+		return 0;
+
 	for_each_set_bit(i, bitmap, PAGE_SIZE * BITS_PER_BYTE) {
-		err = cb(key | i);
+		err = cb->key(key | i);

key(key) reads weird :)
Can't say I have a good name, maybe key_action()?

Quoted 6 lines

Quoted 4 lines

I thought the context of it being under a callback struct would make it more obvious. I don't like key_action() much better TBH, but I don't have a strong opinion. Perhaps Pasha can suggest a 3rd option and we pick on randomly ;-)

Another option I thought is to call them ->leaf() and ->node().

This one sounds nice. Will use it in v2.

Signature · 3 lines

-- 
Regards,
Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO memory preservation radix tree does not mark the table pages themselves as scratch. This is done to avoid a circular dependency where preserving a page can lead of allocating other preserved pages. This means any walker looking for free ranges of memory outside of scratch areas will ignore the table

Add a table callback that is invoked for each table page. The callback

is given the physical address of the table page.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     |  3 +++
 kernel/liveupdate/kexec_handover.c | 12 ++++++++++++
 2 files changed, 15 insertions(+)

include/linux/kho_radix_tree.h +0 -0

index 030da6399d28..fe7151d89361 100644
@@ -37,12 +37,15 @@ struct kho_radix_tree {
 /**
  * struct kho_radix_walk_cb - Callbacks for KHO radix tree walk.

include/linux/kho_radix_tree.h +0 -0

 };
 

Quoted 8 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO memory preservation radix tree does not mark the table pages themselves as scratch. This is done to avoid a circular dependency where preserving a page can lead of allocating other preserved pages. This means any walker looking for free ranges of memory outside of scratch areas will ignore the table

Quoted 1 line

Add a table callback that is invoked for each table page. The callback

A sentence why a table callback helps would be nice here :)

Quoted 20 lines

is given the physical address of the table page.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     |  3 +++
 kernel/liveupdate/kexec_handover.c | 12 ++++++++++++
 2 files changed, 15 insertions(+)

include/linux/kho_radix_tree.h +2 -0

index 030da6399d28..fe7151d89361 100644
@@ -37,12 +37,15 @@ struct kho_radix_tree {
 /**
  * struct kho_radix_walk_cb - Callbacks for KHO radix tree walk.
  * @key:      Called on each present key in the radix tree.
+ * @table:    Called on each table of the radix tree itself. Receives the
+ *            physical address of the page containing the table.
  *

include/linux/kho_radix_tree.h struct kho_radix_tree { · line 48

Quoted 6 lines

include/linux/kho_radix_tree.h +1 -0

  * For each callback, a return value of 0 continues the walk and a non-zero
  * return value is directly returned to the caller.
  */
 struct kho_radix_walk_cb {
 	int (*key)(unsigned long key);
+	int (*table)(phys_addr_t phys);

Naming is hard ;-)

Quoted 3 lines

include/linux/kho_radix_tree.h +0 -0

 };
 

Quoted 9 lines · Mike Rapoport

Quoted 8 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO memory preservation radix tree does not mark the table pages themselves as scratch. This is done to avoid a circular dependency where preserving a page can lead of allocating other preserved pages. This means any walker looking for free ranges of memory outside of scratch areas will ignore the table

Quoted 3 lines

Quoted 1 line

Add a table callback that is invoked for each table page. The callback

A sentence why a table callback helps would be nice here :)

The main reason is that a later patch will create a radix tree for short use and will need to destroy it afterwards.

Will add that here.

Quoted 4 lines

Quoted 4 lines

is given the physical address of the table page.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

From: "Pratyush Yadav (Google)" <[email protected]>

Add an opaque data pointer argument to kho_radix_walk_cb_t. This can be used for callers to pass extra information to the callback.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     |  8 ++++----
 kernel/liveupdate/kexec_handover.c | 24 +++++++++++++-----------
 2 files changed, 17 insertions(+), 15 deletions(-)

Quoted 4 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

Add an opaque data pointer argument to kho_radix_walk_cb_t. This can be used for callers to pass extra information to the callback.

Nit: ^by IMHO

From: "Pratyush Yadav (Google)" <[email protected]>

Add an opaque data pointer argument to kho_radix_walk_cb_t. This can be used for callers to pass extra information to the callback.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     |  8 ++++----
 kernel/liveupdate/kexec_handover.c | 24 +++++++++++++-----------
 2 files changed, 17 insertions(+), 15 deletions(-)

include/linux/kho_radix_tree.h +4 -4

index fe7151d89361..6c0f7d82716b 100644
@@ -44,8 +44,8 @@ struct kho_radix_tree {
  * return value is directly returned to the caller.
  */
 struct kho_radix_walk_cb {
-	int (*key)(unsigned long key);
-	int (*table)(phys_addr_t phys);
+	int (*key)(unsigned long key, void *data);
+	int (*table)(phys_addr_t phys, void *data);
 };
 
 #ifdef CONFIG_KEXEC_HANDOVER

@@ -53,7 +53,7 @@ struct kho_radix_walk_cb {
 int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key);
 void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key);
 int kho_radix_walk_tree(struct kho_radix_tree *tree,
-			const struct kho_radix_walk_cb *cb);
+			const struct kho_radix_walk_cb *cb, void *data);
 
 #else  /* #ifdef CONFIG_KEXEC_HANDOVER */
 

@@ -66,7 +66,7 @@ static inline void kho_radix_del_key(struct kho_radix_tree *tree,
 				     unsigned long key) { }
 
 static inline int kho_radix_walk_tree(struct kho_radix_tree *tree,
-				      const struct kho_radix_walk_cb *cb)
+				      const struct kho_radix_walk_cb *cb, void *data)
 {
 	return -EOPNOTSUPP;
 }

kernel/liveupdate/kexec_handover.c +13 -11

index 94ca831b41c9..d0a4f78eccfe 100644
@@ -267,14 +267,14 @@ void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key)
 EXPORT_SYMBOL_GPL(kho_radix_del_key);
 
 static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf, unsigned long key,
-			       const struct kho_radix_walk_cb *cb)
+			       const struct kho_radix_walk_cb *cb, void *data)
 {
 	unsigned long *bitmap = (unsigned long *)leaf;
 	unsigned int i;
 	int err;
 
 	if (cb->table) {
-		err = cb->table(virt_to_phys(leaf));
+		err = cb->table(virt_to_phys(leaf), data);
 		if (err)
 			return err;
 	}

@@ -283,7 +283,7 @@ static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf, unsigned long key,
 		return 0;
 
 	for_each_set_bit(i, bitmap, PAGE_SIZE * BITS_PER_BYTE) {
-		err = cb->key(key | i);
+		err = cb->key(key | i, data);
 		if (err)
 			return err;
 	}

@@ -293,7 +293,7 @@ static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf, unsigned long key,
 
 static int __kho_radix_walk_tree(struct kho_radix_node *root,
 				 unsigned int level, unsigned long start,
-				 const struct kho_radix_walk_cb *cb)
+				 const struct kho_radix_walk_cb *cb, void *data)
 {
 	struct kho_radix_node *node;
 	struct kho_radix_leaf *leaf;

@@ -302,7 +302,7 @@ static int __kho_radix_walk_tree(struct kho_radix_node *root,
 	int err;
 
 	if (cb->table) {
-		err = cb->table(virt_to_phys(root));
+		err = cb->table(virt_to_phys(root), data);
 		if (err)
 			return err;
 	}

@@ -323,10 +323,10 @@ static int __kho_radix_walk_tree(struct kho_radix_node *root,
 			 * node is pointing to the level 0 bitmap.
 			 */
 			leaf = (struct kho_radix_leaf *)node;
-			err = kho_radix_walk_leaf(leaf, key, cb);
+			err = kho_radix_walk_leaf(leaf, key, cb, data);
 		} else {
 			err  = __kho_radix_walk_tree(node, level - 1,
-						     key, cb);
+						     key, cb, data);
 		}
 
 		if (err)

@@ -340,6 +340,7 @@ static int __kho_radix_walk_tree(struct kho_radix_node *root,
  * kho_radix_walk_tree - Traverses the radix tree and calls a callback for each key.
  * @tree: A pointer to the KHO radix tree to walk.
  * @cb:   Set of callbacks to be invoked during the tree walk.
+ * @data: Opaque data pointer passed to each callback in @cb.
  *
  * This function walks the radix tree, searching from the top level down to the
  * lowest level (level 0), invoking the appropriate callbacks.

@@ -348,14 +349,15 @@ static int __kho_radix_walk_tree(struct kho_radix_node *root,
  *         value from the callback that stopped the walk.
  */
 int kho_radix_walk_tree(struct kho_radix_tree *tree,
-			const struct kho_radix_walk_cb *cb)
+			const struct kho_radix_walk_cb *cb, void *data)
 {
 	if (WARN_ON_ONCE(!tree->root))
 		return -EINVAL;
 
 	guard(mutex)(&tree->lock);
 
-	return __kho_radix_walk_tree(tree->root, KHO_TREE_MAX_DEPTH - 1, 0, cb);
+	return __kho_radix_walk_tree(tree->root, KHO_TREE_MAX_DEPTH - 1, 0, cb,
+				     data);
 }
 EXPORT_SYMBOL_GPL(kho_radix_walk_tree);
 

@@ -501,7 +503,7 @@ static struct page *__init kho_get_preserved_page(phys_addr_t phys,
 	return pfn_to_page(pfn);
 }
 
-static int __init kho_preserved_memory_reserve(unsigned long key)
+static int __init kho_preserved_memory_reserve(unsigned long key, void *data)
 {
 	union kho_page_info info;
 	struct page *page;

@@ -1392,7 +1394,7 @@ static int __init kho_mem_retrieve(const void *fdt)
 
 	kho_in.radix_tree.root = phys_to_virt(kho_get_mem_map_phys(fdt));
 	mutex_init(&kho_in.radix_tree.lock);
-	return kho_radix_walk_tree(&kho_in.radix_tree, &cb);
+	return kho_radix_walk_tree(&kho_in.radix_tree, &cb, NULL);
 }
 
 static __init int kho_out_fdt_setup(void)

Signature · 1 line

2.54.0.545.g6539524ca2-goog

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO radix tree allocates memory for table pages from the buddy allocator using get_zeroed_page(). This is not available in early boot when memblock is still active.

Using the radix tree in early boot is useful for KHO to track metadata about its memory. One such example is for tracking free blocks for memory allocation when scratch runs out of space. This feature will be added in the following commits.

Add kho_radix_{alloc,free}_node() which allocate and free the table pages. They use slab_is_available() to decide which allocator to use. While slab_is_available() indicates availability of the slab allocator, it gets initialized right before buddy so it serves the same practical

purpose.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 kernel/liveupdate/kexec_handover.c | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

Quoted 11 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO radix tree allocates memory for table pages from the buddy allocator using get_zeroed_page(). This is not available in early boot when memblock is still active.

Using the radix tree in early boot is useful for KHO to track metadata about its memory. One such example is for tracking free blocks for memory allocation when scratch runs out of space. This feature will be added in the following commits.

Quoted 4 lines

Add kho_radix_{alloc,free}_node() which allocate and free the table pages. They use slab_is_available() to decide which allocator to use. While slab_is_available() indicates availability of the slab allocator, it gets initialized right before buddy so it serves the same practical

^ after?

Quoted 7 lines

purpose.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 kernel/liveupdate/kexec_handover.c | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

From: "Pratyush Yadav (Google)" <[email protected]>

The KHO radix tree allocates memory for table pages from the buddy allocator using get_zeroed_page(). This is not available in early boot when memblock is still active.

Using the radix tree in early boot is useful for KHO to track metadata about its memory. One such example is for tracking free blocks for memory allocation when scratch runs out of space. This feature will be added in the following commits.

Add kho_radix_{alloc,free}_node() which allocate and free the table pages. They use slab_is_available() to decide which allocator to use. While slab_is_available() indicates availability of the slab allocator, it gets initialized right before buddy so it serves the same practical purpose.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 kernel/liveupdate/kexec_handover.c | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

kernel/liveupdate/kexec_handover.c +22 -2

index d0a4f78eccfe..47f7c4a2865e 100644
@@ -143,6 +143,26 @@ static unsigned long kho_radix_get_table_index(unsigned long key,
 	return (key >> s) % (1 << KHO_TABLE_SIZE_LOG2);
 }
 
+static void __ref *kho_radix_alloc_node(void)
+{
+	struct kho_radix_node *node;
+
+	if (slab_is_available())
+		node = (struct kho_radix_node *)get_zeroed_page(GFP_KERNEL);
+	else
+		node = memblock_alloc(PAGE_SIZE, PAGE_SIZE);
+
+	return node;
+}
+
+static void __ref kho_radix_free_node(struct kho_radix_node *node)
+{
+	if (slab_is_available())
+		free_page((unsigned long)node);
+	else
+		memblock_free(node, PAGE_SIZE);
+}
+
 /**
  * kho_radix_add_key - Add a key to the radix tree.
  * @tree: The KHO radix tree.

@@ -183,7 +203,7 @@ int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key)
 		}
 
 		/* Next node is empty, create a new node for it */
-		new_node = (struct kho_radix_node *)get_zeroed_page(GFP_KERNEL);
+		new_node = kho_radix_alloc_node();
 		if (!new_node) {
 			err = -ENOMEM;
 			goto err_free_nodes;

@@ -214,7 +234,7 @@ int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key)
 err_free_nodes:
 	for (i = KHO_TREE_MAX_DEPTH - 1; i > 0; i--) {
 		if (intermediate_nodes[i])
-			free_page((unsigned long)intermediate_nodes[i]);
+			kho_radix_free_node(intermediate_nodes[i]);
 	}
 	if (anchor_node)
 		anchor_node->table[anchor_idx] = 0;

Signature · 1 line

2.54.0.545.g6539524ca2-goog

From: "Pratyush Yadav (Google)" <[email protected]>

Add kho_radix_destroy_tree() which allows destroying the radix tree and freeing all its pages.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     |  3 +++
 kernel/liveupdate/kexec_handover.c | 34 ++++++++++++++++++++++++++++++
 2 files changed, 37 insertions(+)

From: "Pratyush Yadav (Google)" <[email protected]>

Add kho_radix_destroy_tree() which allows destroying the radix tree and freeing all its pages.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     |  3 +++
 kernel/liveupdate/kexec_handover.c | 34 ++++++++++++++++++++++++++++++
 2 files changed, 37 insertions(+)

include/linux/kho_radix_tree.h +3 -0

index 6c0f7d82716b..617395a6647a 100644
@@ -54,6 +54,7 @@ int kho_radix_add_key(struct kho_radix_tree *tree, unsigned long key);
 void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key);
 int kho_radix_walk_tree(struct kho_radix_tree *tree,
 			const struct kho_radix_walk_cb *cb, void *data);
+void kho_radix_destroy_tree(struct kho_radix_tree *tree);
 
 #else  /* #ifdef CONFIG_KEXEC_HANDOVER */
 

@@ -71,6 +72,8 @@ static inline int kho_radix_walk_tree(struct kho_radix_tree *tree,
 	return -EOPNOTSUPP;
 }
 
+static inline void kho_radix_destroy_tree(struct kho_radix_tree *tree) { }
+
 #endif /* #ifdef CONFIG_KEXEC_HANDOVER */
 
 #endif	/* _LINUX_KHO_RADIX_TREE_H */

kernel/liveupdate/kexec_handover.c +34 -0

index 47f7c4a2865e..29479534f65d 100644
@@ -286,6 +286,40 @@ void kho_radix_del_key(struct kho_radix_tree *tree, unsigned long key)
 }
 EXPORT_SYMBOL_GPL(kho_radix_del_key);
 
+static void __kho_radix_destroy_tree(struct kho_radix_node *root,
+				     unsigned int level)
+{
+	unsigned long i;
+
+	if (level == 0) {
+		kho_radix_free_node(root);
+		return;
+	}
+
+	for (i = 0; i < PAGE_SIZE / sizeof(phys_addr_t); i++) {
+		if (root->table[i])
+			__kho_radix_destroy_tree(phys_to_virt(root->table[i]),
+						 level - 1);
+	}
+
+	kho_radix_free_node(root);
+}
+
+/**
+ * kho_radix_destroy_tree - Destroy the radix tree
+ * @tree: The radix tree to destroy
+ *
+ * Walk @tree and free all its nodes.
+ */
+void kho_radix_destroy_tree(struct kho_radix_tree *tree)
+{
+	if (!tree->root)
+		return;
+
+	__kho_radix_destroy_tree(tree->root, KHO_TREE_MAX_DEPTH - 1);
+}
+EXPORT_SYMBOL_GPL(kho_radix_destroy_tree);
+
 static int kho_radix_walk_leaf(struct kho_radix_leaf *leaf, unsigned long key,
 			       const struct kho_radix_walk_cb *cb, void *data)
 {

Signature · 1 line

2.54.0.545.g6539524ca2-goog

Quoted 10 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

Add kho_radix_destroy_tree() which allows destroying the radix tree and freeing all its pages.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kho_radix_tree.h     |  3 +++
 kernel/liveupdate/kexec_handover.c | 34 ++++++++++++++++++++++++++++++
 2 files changed, 37 insertions(+)

Generally, in Linux, recursion is avoided due to statically sized kernel stacks. However, here we are bound by a relatively shallow KHO tree, and kho_radix_walk_tree() is already recursive, so I think it is alright. We just need to be mindful of local variable usage (frame sizes) within these recursive functions.

Reviewed-by Pasha Tatashin <[email protected]>

From: "Pratyush Yadav (Google)" <[email protected]>

Move the initialization logic of the radix tree into kho_radix_init_tree() instead of having users open-code it. Makes the boundaries cleaner and reduces code duplication when a new user of the radix tree will be added in a future commit.

Quoted 6 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

Move the initialization logic of the radix tree into kho_radix_init_tree() instead of having users open-code it. Makes the boundaries cleaner and reduces code duplication when a new user of the radix tree will be added in a future commit.

Consider using kho_radix_init_tree() in kho_init() as well. This will also remove the kzalloc() one-off use. Similar for kho_radix_destroy_tree().

From: "Pratyush Yadav (Google)" <[email protected]>

In the upcoming commits, the KHO will learn how to discover free blocks of memory by walking the KHO radix tree. It will then mark those regions as scratch to allow memory allocation in case scratch runs low.

To differentiate the extended scratch areas from the main scratch areas, introduce MEMBLOCK_KHO_SCRATCH_EXT. Use it when choosing memblock flags for allocations during scratch-only. Teach should_skip_region() to check for both flags before deciding if the region should be skipped.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---

Notes:
Checkpatch complains about no space after MEMBLOCK_KHO_SCRATCH_EXT in the declaration, but doing so makes it nicely align with all the other numbers. Mike, if you'd like I can add some whitespace.

 include/linux/memblock.h | 10 ++++++++++
 mm/memblock.c            | 41 ++++++++++++++++++++++++++++++++++------
 2 files changed, 45 insertions(+), 6 deletions(-)

Quoted 10 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

In the upcoming commits, the KHO will learn how to discover free blocks of memory by walking the KHO radix tree. It will then mark those regions as scratch to allow memory allocation in case scratch runs low.

To differentiate the extended scratch areas from the main scratch areas, introduce MEMBLOCK_KHO_SCRATCH_EXT. Use it when choosing memblock flags for allocations during scratch-only. Teach should_skip_region() to check for both flags before deciding if the region should be skipped.

Why there's a need to differentiate SCRATCH and SCRATCH_EXT? SCRATCH (I still hate the name) means "memory memblock can safely use for the allocations". Initially this memory comes from the reservations in the first kernel, but if the second kernel can find more memory to extend it, why that additional memory should be treated differently?

Quoted 12 lines

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---

Notes:
Checkpatch complains about no space after MEMBLOCK_KHO_SCRATCH_EXT in the declaration, but doing so makes it nicely align with all the other numbers. Mike, if you'd like I can add some whitespace.

 include/linux/memblock.h | 10 ++++++++++
 mm/memblock.c            | 41 ++++++++++++++++++++++++++++++++++------
 2 files changed, 45 insertions(+), 6 deletions(-)

Quoted 7 lines · Mike Rapoport

Quoted 6 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

In the upcoming commits, the KHO will learn how to discover free blocks of memory by walking the KHO radix tree. It will then mark those regions as scratch to allow memory allocation in case scratch runs low.

Quoted 7 lines

Quoted 4 lines

To differentiate the extended scratch areas from the main scratch areas, introduce MEMBLOCK_KHO_SCRATCH_EXT. Use it when choosing memblock flags for allocations during scratch-only. Teach should_skip_region() to check for both flags before deciding if the region should be skipped.

Why there's a need to differentiate SCRATCH and SCRATCH_EXT? SCRATCH (I still hate the name) means "memory memblock can safely use for

Quoted 3 lines

the allocations". Initially this memory comes from the reservations in the first kernel, but if the second kernel can find more memory to extend it, why that additional memory should be treated differently?

Two reasons:

1. We mark SCRATCH as MIGRATE_CMA. We don't want to do that for SCRATCH_EXT since this memory can be used for non-movable allocations.

2. Gigantic (1G) huge pages can not be allocated from scratch. They can be preserved memory and thus should not be allocated from SCRATCH. See patch 12 that does allocations for gigantic huge pages only from SCRATCH_EXT.

I will add this in the commit message for the next version.

Naming is hard, so if you have any better names I'm all ears :-)

Quoted 13 lines

Quoted 13 lines

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---

Notes:
Checkpatch complains about no space after MEMBLOCK_KHO_SCRATCH_EXT in the declaration, but doing so makes it nicely align with all the other numbers. Mike, if you'd like I can add some whitespace.

 include/linux/memblock.h | 10 ++++++++++
 mm/memblock.c            | 41 ++++++++++++++++++++++++++++++++++------
 2 files changed, 45 insertions(+), 6 deletions(-)

Signature · 2 lines

Regards,
Pratyush Yadav

Quoted 9 lines · Pratyush Yadav

Quoted 7 lines · Mike Rapoport

Quoted 6 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

In the upcoming commits, the KHO will learn how to discover free blocks of memory by walking the KHO radix tree. It will then mark those regions as scratch to allow memory allocation in case scratch runs low.

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

To differentiate the extended scratch areas from the main scratch areas, introduce MEMBLOCK_KHO_SCRATCH_EXT. Use it when choosing memblock flags for allocations during scratch-only. Teach should_skip_region() to check for both flags before deciding if the region should be skipped.

Why there's a need to differentiate SCRATCH and SCRATCH_EXT? SCRATCH (I still hate the name) means "memory memblock can safely use for

+1000

I also strongly dislike this name and mentioned it in another thread earlier today.

If we ever decide to s/scratch/something-else/ globally, that should be a separate cleanup effort. However, since we are introducing a brand new flag here, we can discuss a better name for the _ext portion to avoid overloading the "scratch" concept.

Quoted 10 lines

Quoted 3 lines

the allocations". Initially this memory comes from the reservations in the first kernel, but if the second kernel can find more memory to extend it, why that additional memory should be treated differently?

Two reasons:

1. We mark SCRATCH as MIGRATE_CMA. We don't want to do that for SCRATCH_EXT since this memory can be used for non-movable allocations.

Quoted 8 lines

2. Gigantic (1G) huge pages can not be allocated from scratch. They can be preserved memory and thus should not be allocated from SCRATCH. See patch 12 that does allocations for gigantic huge pages only from SCRATCH_EXT.

I will add this in the commit message for the next version.

Naming is hard, so if you have any better names I'm all ears :-)

IMO, this scratch_ext is not "scratch" in the traditional KHO sense at all. The traditional KHO scratch is what is passed from kernel to kernel and is guaranteed to contain zero preserved memory. This new memory is not passed from kernel to kernel and can contain preserved memory at runtime. It's essentially just memory that we identify as currently unpreserved and release early to the system.

If we want to keep the naming aligned with the existing codebase for now:
MEMBLOCK_KHO_SCRATCH -> original scratch
MEMBLOCK_KHO_UNPRESERVED -> for the new memory (instead of SCRATCH_EXT)

Alternatively, if we do want to tackle the global rename of "scratch" later:
MEMBLOCK_KHO_BOOTSTRAP -> for the original scratch
MEMBLOCK_KHO_UNPRESERVED -> for this new dynamic memory

What do you think?

Pasha

Quoted 54 lines · Pasha Tatashin

Quoted 9 lines · Pratyush Yadav

Quoted 7 lines · Mike Rapoport

Quoted 6 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

In the upcoming commits, the KHO will learn how to discover free blocks of memory by walking the KHO radix tree. It will then mark those regions as scratch to allow memory allocation in case scratch runs low.

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

To differentiate the extended scratch areas from the main scratch areas, introduce MEMBLOCK_KHO_SCRATCH_EXT. Use it when choosing memblock flags for allocations during scratch-only. Teach should_skip_region() to check for both flags before deciding if the region should be skipped.

Why there's a need to differentiate SCRATCH and SCRATCH_EXT? SCRATCH (I still hate the name) means "memory memblock can safely use for

+1000

I also strongly dislike this name and mentioned it in another thread earlier today.

If we ever decide to s/scratch/something-else/ globally, that should be a separate cleanup effort. However, since we are introducing a brand new flag here, we can discuss a better name for the _ext portion to avoid overloading the "scratch" concept.

Quoted 10 lines

Quoted 3 lines

the allocations". Initially this memory comes from the reservations in the first kernel, but if the second kernel can find more memory to extend it, why that additional memory should be treated differently?

Two reasons:

1. We mark SCRATCH as MIGRATE_CMA. We don't want to do that for SCRATCH_EXT since this memory can be used for non-movable allocations.

Quoted 8 lines

2. Gigantic (1G) huge pages can not be allocated from scratch. They can be preserved memory and thus should not be allocated from SCRATCH. See patch 12 that does allocations for gigantic huge pages only from SCRATCH_EXT.

I will add this in the commit message for the next version.

Naming is hard, so if you have any better names I'm all ears :-)

IMO, this scratch_ext is not "scratch" in the traditional KHO sense at all. The traditional KHO scratch is what is passed from kernel to kernel and is guaranteed to contain zero preserved memory. This new memory is not passed from kernel to kernel and can contain preserved memory at runtime. It's essentially just memory that we identify as currently unpreserved and release early to the system.

Quoted 3 lines

If we want to keep the naming aligned with the existing codebase for now:
MEMBLOCK_KHO_SCRATCH -> original scratch
MEMBLOCK_KHO_UNPRESERVED -> for the new memory (instead of SCRATCH_EXT)

UNPRESERVED sounds good to me. I will use that for the next revision unless Mike objects.

Quoted 3 lines

Alternatively, if we do want to tackle the global rename of "scratch" later:
MEMBLOCK_KHO_BOOTSTRAP -> for the original scratch
MEMBLOCK_KHO_UNPRESERVED -> for this new dynamic memory

Or perhaps BOOTMEM? I suppose either of the two are somewhat better than scratch.

Anyway, can we please do the SCRATCH rename as a separate series? I

would like this series to not get muddled in the naming discussion. I will use UNPRESERVED for the new concept in v2 though.

Signature · 2 lines

Regards,
Pratyush Yadav

Quoted 56 lines · Pratyush Yadav

Quoted 54 lines · Pasha Tatashin

Quoted 9 lines · Pratyush Yadav

Quoted 7 lines · Mike Rapoport

Quoted 6 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

In the upcoming commits, the KHO will learn how to discover free blocks of memory by walking the KHO radix tree. It will then mark those regions as scratch to allow memory allocation in case scratch runs low.

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

To differentiate the extended scratch areas from the main scratch areas, introduce MEMBLOCK_KHO_SCRATCH_EXT. Use it when choosing memblock flags for allocations during scratch-only. Teach should_skip_region() to check for both flags before deciding if the region should be skipped.

Why there's a need to differentiate SCRATCH and SCRATCH_EXT? SCRATCH (I still hate the name) means "memory memblock can safely use for

+1000

I also strongly dislike this name and mentioned it in another thread earlier today.

If we ever decide to s/scratch/something-else/ globally, that should be a separate cleanup effort. However, since we are introducing a brand new flag here, we can discuss a better name for the _ext portion to avoid overloading the "scratch" concept.

Quoted 10 lines

Quoted 3 lines

the allocations". Initially this memory comes from the reservations in the first kernel, but if the second kernel can find more memory to extend it, why that additional memory should be treated differently?

Two reasons:

1. We mark SCRATCH as MIGRATE_CMA. We don't want to do that for SCRATCH_EXT since this memory can be used for non-movable allocations.

Quoted 8 lines

2. Gigantic (1G) huge pages can not be allocated from scratch. They can be preserved memory and thus should not be allocated from SCRATCH. See patch 12 that does allocations for gigantic huge pages only from SCRATCH_EXT.

I will add this in the commit message for the next version.

Naming is hard, so if you have any better names I'm all ears :-)

IMO, this scratch_ext is not "scratch" in the traditional KHO sense at all. The traditional KHO scratch is what is passed from kernel to kernel and is guaranteed to contain zero preserved memory. This new memory is not passed from kernel to kernel and can contain preserved memory at runtime. It's essentially just memory that we identify as currently unpreserved and release early to the system.

Quoted 6 lines

Quoted 3 lines

If we want to keep the naming aligned with the existing codebase for now:
MEMBLOCK_KHO_SCRATCH -> original scratch
MEMBLOCK_KHO_UNPRESERVED -> for the new memory (instead of SCRATCH_EXT)

UNPRESERVED sounds good to me. I will use that for the next revision unless Mike objects.

Can we make it shorter? ;-)

UNPRESERVED makes sense, although I'd love to completely remove KHO_ notion and make the name reflect how it's used by memblock. I was toying with PREFERRED instead of SCRATCH, but it didn't feel right enough. With two of them that surely won't work :)

Quoted 7 lines

Quoted 4 lines

Alternatively, if we do want to tackle the global rename of "scratch" later:
MEMBLOCK_KHO_BOOTSTRAP -> for the original scratch
MEMBLOCK_KHO_UNPRESERVED -> for this new dynamic memory

Or perhaps BOOTMEM? I suppose either of the two are somewhat better than scratch.

Well, if we have BOOTMEM_HVO, we can have BOOTMEM_KHO as well :)

Quoted 1 line

Anyway, can we please do the SCRATCH rename as a separate series? I

Sure. We can continue bikeshedding in parallel.

Quoted 2 lines

would like this series to not get muddled in the naming discussion. I will use UNPRESERVED for the new concept in v2 though.

That might warrant v3 even if everything else is perfect :)

Quoted 8 lines · Mike Rapoport

Quoted 7 lines

Quoted 4 lines

If we want to keep the naming aligned with the existing codebase for now:
MEMBLOCK_KHO_SCRATCH -> original scratch
MEMBLOCK_KHO_UNPRESERVED -> for the new memory (instead of SCRATCH_EXT)

UNPRESERVED sounds good to me. I will use that for the next revision unless Mike objects.

Quoted 6 lines

Can we make it shorter? ;-)

UNPRESERVED makes sense, although I'd love to completely remove KHO_ notion and make the name reflect how it's used by memblock. I was toying with PREFERRED instead of SCRATCH, but it didn't feel right enough. With two of them that surely won't work :)

I don't think you really can remove KHO_ notion. These memory regions only make sense on a KHO boot, and won't exist otherwise. And PREFERRED sounds like a suggestion/priority hint, not a hard limit. "With KHO boot, you can _only_ use PREFERRED memory", doesn't sound right...

I think MEMBLOCK_KHO_BOOTMEM for scratch and MEMBLOCK_KHO_NOPRESERVE (which I think is a tiny bit better than UNPRESERVED) for scratch_ext are my top picks. To make it shorter, perhaps MEMBLOCK_KHO_NOPRSRV, in similar fashion to RSRV_KERN?

Quoted 4 lines

Quoted 2 lines

would like this series to not get muddled in the naming discussion. I will use UNPRESERVED for the new concept in v2 though.

That might warrant v3 even if everything else is perfect :)

I can live with that. As long as we can agree on the easy part (the code), I don't mind doing another version for the hard part (the naming) ;-)

Signature · 2 lines

Regards,
Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

Methodology
===========

Introduce extended scratch areas. These areas are discovered at boot by walking the preserved memory radix tree and looking for free blocks of memory. They then marked as scratch to allow allocations from them. This makes KHO more resilient to memory pressure and allows supporting huge page preservation.

Since the preserved memory radix tree mixes both physical address and order into a single key, and does not track table pages, it is difficult to identify free areas from it directly. Walk the tree and digest it down into another radix tree. The latter tracks blocks of KHO_EXT_SHIFT (1 GiB as of now) granularity. Then walk the digested tree and mark the areas between the present keys as scratch.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kexec_handover.h     |   1 +
 kernel/liveupdate/kexec_handover.c | 148 +++++++++++++++++++++++++----
 mm/mm_init.c                       |   1 +
 3 files changed, 133 insertions(+), 17 deletions(-)

kernel/liveupdate/kexec_handover.c +0 -0

index 1a04e089f779..c2b843a5fb28 100644

Quoted 33 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

Methodology
===========

Introduce extended scratch areas. These areas are discovered at boot by walking the preserved memory radix tree and looking for free blocks of memory. They then marked as scratch to allow allocations from them. This makes KHO more resilient to memory pressure and allows supporting huge page preservation.

Since the preserved memory radix tree mixes both physical address and order into a single key, and does not track table pages, it is difficult to identify free areas from it directly. Walk the tree and digest it down into another radix tree. The latter tracks blocks of KHO_EXT_SHIFT (1 GiB as of now) granularity. Then walk the digested tree and mark the areas between the present keys as scratch.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 include/linux/kexec_handover.h     |   1 +
 kernel/liveupdate/kexec_handover.c | 148 +++++++++++++++++++++++++----
 mm/mm_init.c                       |   1 +
 3 files changed, 133 insertions(+), 17 deletions(-)

kernel/liveupdate/kexec_handover.c +0 -0

index 1a04e089f779..c2b843a5fb28 100644
@@ -840,6 +857,120 @@ static void __init kho_reserve_scratch(void)
 	kho_enable = false;
 }
 

kernel/liveupdate/kexec_handover.c static void __init kho_reserve_scratch(void) · line 860

Quoted 1 line

kernel/liveupdate/kexec_handover.c +1 -0

+#define KHO_EXT_SHIFT 30 /* 1 GiB */

arm64 does not necessarily use 1G gigantic pages and worse, it can have 2 gigantic hstates.

I think this should take into account what actual gigantic page sizes are in use for the general case.

From: "Pratyush Yadav (Google)" <[email protected]>

There are currently 3 callers of kho_get_mem_map_phys(). Two of them, kho_mem_retrieve() and kho_extend_scratch() need the virtual address. The third, kho_populate() doesn't care. Make things simpler by directly returning the virtual address. Rename kho_get_mem_map_phys() to kho_get_mem_map() to accurately reflect what it returns.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 kernel/liveupdate/kexec_handover.c | 28 +++++++++++++++-------------
 1 file changed, 15 insertions(+), 13 deletions(-)

Quoted 7 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

There are currently 3 callers of kho_get_mem_map_phys(). Two of them, kho_mem_retrieve() and kho_extend_scratch() need the virtual address. The third, kho_populate() doesn't care. Make things simpler by directly returning the virtual address. Rename kho_get_mem_map_phys() to kho_get_mem_map() to accurately reflect what it returns.

This should be moved earlier, before replacing open-coded get_mem_map() with a call to kho_get_mem_map_phys().

Quoted 5 lines

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 kernel/liveupdate/kexec_handover.c | 28 +++++++++++++++-------------
 1 file changed, 15 insertions(+), 13 deletions(-)

Quoted 9 lines · Mike Rapoport

Quoted 7 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

There are currently 3 callers of kho_get_mem_map_phys(). Two of them, kho_mem_retrieve() and kho_extend_scratch() need the virtual address. The third, kho_populate() doesn't care. Make things simpler by directly returning the virtual address. Rename kho_get_mem_map_phys() to kho_get_mem_map() to accurately reflect what it returns.

Quoted 2 lines

This should be moved earlier, before replacing open-coded get_mem_map() with a call to kho_get_mem_map_phys().

Do you mean move it before patch 2 "kho: store incoming radix tree in kho_in"?

I can do that. I did it this way to show a clear need for this function, but I don't mind doing it as a preparatory step.

Quoted 5 lines

Quoted 5 lines

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---
 kernel/liveupdate/kexec_handover.c | 28 +++++++++++++++-------------
 1 file changed, 15 insertions(+), 13 deletions(-)

Signature · 2 lines

Regards,
Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

Gigantic page allocation is somewhat broken currently when KHO is used.

Firstly, they break KHO scratch size accounting. RSRV_KERN is used to track how much memory is reserved for use by the kernel. Since alloc_bootmem() calls the memblock_alloc*() APIs, the hugepages allocated also get marked as RSRV_KERN.

Allocations marked RSRV_KERN are used by KHO to calculate how much scratch space it should reserve to make sure the next kernel has enough memory to boot when it is in scratch-only phase. Counting hugepages in

that blows up scratch size, and can lead to the scratch allocation failing, making KHO unusable. This will show up when huge pages make up more than 50% of the system, which is a fairly common use case.

Secondly, while not supported right now, huge pages are user memory and can be preserved via KHO. The scratch spaces should not have any preserved memory. Allocating hugepages from scratch (on a KHO boot) can lead to them being un-preservable.

Introduce memblock_alloc_nid_user(). This does two things: first, it instructs __memblock_alloc_range_nid() to not use scratch areas to fulfill allocation. If KHO is in scratch-only mode, allocations will only be made from extended scratch areas. Second, it removes RSRV_KERN from the allocation to make sure it doesn't mess up scratch size accounting.

To reduce duplication, introduce __memblock_alloc_range_nid() which does exactly what memblock_alloc_range_nid() used to do, but takes the flags from its caller. Then make memblock_alloc_range_nid() a wrapper to it. This lets memblock_alloc_nid_user() re-use most of the logic without causing churn to update all callers of memblock_alloc_range_nid() and adding yet another argument to it.

Signed-off-by Pratyush Yadav (Google) <[email protected]>

---

Notes:
Checkpatch complains here about the alignment of arguments of memblock_alloc_range_nid() with open parentheses. That can be ignored since the code already was mis-aligned, and for good reason.

 include/linux/memblock.h |   4 ++
 mm/hugetlb.c             |  19 ++----
 mm/memblock.c            | 138 ++++++++++++++++++++++++++++++---------
 3 files changed, 116 insertions(+), 45 deletions(-)

Hi Pratyush,

Quoted 8 lines · Pratyush Yadav

From: "Pratyush Yadav (Google)" <[email protected]>

Gigantic page allocation is somewhat broken currently when KHO is used.

Firstly, they break KHO scratch size accounting. RSRV_KERN is used to track how much memory is reserved for use by the kernel. Since alloc_bootmem() calls the memblock_alloc*() APIs, the hugepages allocated also get marked as RSRV_KERN.

The intended semantics of RSRV_KERN was to distinguish memory reserved because it's in use by firmware from the memory reserved or allocated by the kernel. It does not have to be directly used by the kernel, some of PG_Reserved memory is mapped to user-space and it's not only hugetlb. There are zero pages, VDSO and maybe something else, I don't remember.

Quoted 3 lines

Allocations marked RSRV_KERN are used by KHO to calculate how much scratch space it should reserve to make sure the next kernel has enough memory to boot when it is in scratch-only phase. Counting hugepages in

The size of RSRV_KERN allocations is also used in memblock_estimated_nr_free_pages() that's currently used by set_max_threads() to set several rlimits and by s390 to allocate colored zero pages. Excluding hugetlb from that will skew the calculations there.