// SPDX-License-Identifier: GPL-2.0-only/* * kexec_handover.c - kexec handover metadata processing * Copyright (C) 2023 Alexander Graf <graf@amazon.com> * Copyright (C) 2025 Microsoft Corporation, Mike Rapoport <rppt@kernel.org> * Copyright (C) 2025 Google LLC, Changyuan Lyu <changyuanl@google.com> * Copyright (C) 2025 Pasha Tatashin <pasha.tatashin@soleen.com> * Copyright (C) 2026 Google LLC, Jason Miu <jasonmiu@google.com> */ #define pr_fmt(fmt) "KHO: " fmt #include <linux/cleanup.h>#include <linux/cma.h>#include <linux/kmemleak.h>#include <linux/count_zeros.h>#include <linux/kasan.h>#include <linux/kexec.h>#include <linux/kexec_handover.h>#include <linux/kho_radix_tree.h>#include <linux/utsname.h>#include <linux/kho/abi/kexec_handover.h>#include <linux/kho/abi/kexec_metadata.h>#include <linux/libfdt.h>#include <linux/list.h>#include <linux/memblock.h>#include <linux/page-isolation.h>#include <linux/unaligned.h>#include <linux/vmalloc.h> #include <asm/early_ioremap.h> /* * KHO is tightly coupled with mm init and needs access to some of mm * internal APIs. */#include "../../mm/mm_init.h"#include "../../mm/vmalloc.h"#include "../kexec_internal.h"#include "kexec_handover_internal.h" /* * This is the minimal alignment required by deferred struct page init. * deferred_init_memmap_chunk frees memory to the buddy allocator, which looks * at the neighboring pages (up to MAX_PAGE_ORDER) to merge them. * If KHO scratch is not aligned to that value, buddy can access uninitialized * struct pages, which can cause a crash. */#define SCRATCH_ALIGNMENT_BYTES (PAGE_SIZE * MAX_ORDER_NR_PAGES)static_assert(SCRATCH_ALIGNMENT_BYTES >= CMA_MIN_ALIGNMENT_BYTES); /* The magic token for preserved pages */#define KHO_PAGE_MAGIC 0x4b484f50U /* ASCII for 'KHOP' */ /* * KHO uses page->private, which is an unsigned long, to store page metadata. * Use it to store both the magic and the order. */union kho_page_info {	unsigned long page_private;	struct {		unsigned int order;		unsigned int magic;	};}; static_assert(sizeof(union kho_page_info) == sizeof(((struct page *)0)->private)); static bool kho_enable __ro_after_init = IS_ENABLED(CONFIG_KEXEC_HANDOVER_ENABLE_DEFAULT); bool kho_is_enabled(void){	return kho_enable;}EXPORT_SYMBOL_GPL(kho_is_enabled); static int __init kho_parse_enable(char *p){	return kstrtobool(p, &kho_enable);}early_param("kho", kho_parse_enable); struct kho_out {	void *fdt;	struct mutex lock; /* protects KHO FDT */ 	struct kho_radix_tree radix_tree;	struct kho_debugfs dbg;}; static struct kho_out kho_out = {	.lock = __MUTEX_INITIALIZER(kho_out.lock),	.radix_tree = {		.lock = __MUTEX_INITIALIZER(kho_out.radix_tree.lock),	},}; struct kho_in {	phys_addr_t fdt_phys;	phys_addr_t scratch_phys;	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 = {}; static const void *kho_get_fdt(void){	return kho_in.fdt_phys ? phys_to_virt(kho_in.fdt_phys) : NULL;} /** * 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. * * This function combines a page's physical address and its order into a * single unsigned long, which is used as a key for all radix tree * operations. * * Return: The encoded unsigned long radix key. */static unsigned long kho_encode_radix_key(phys_addr_t phys, unsigned int order){	/* The physical address is encoded by shifting the PFN by its order. */	unsigned long shift = PAGE_SHIFT + order;	/* Order bit goes right before the shifted PFN. */	unsigned long h = 1UL << (64 - shift);	/* Shifted PFN. */	unsigned long l = phys >> shift; 	return h | l;} /** * 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_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_decode_radix_key(unsigned long key, unsigned int *order){	/* fls64() indexes starting from 1. */	unsigned int order_bit = fls64(key) - 1;	phys_addr_t phys; 	/* order bit goes right before the shifted PFN. */	*order = 64 - (PAGE_SHIFT + order_bit);	/* The order bit is discarded by the shift */	phys = key << (PAGE_SHIFT + *order); 	return phys;} static unsigned long kho_radix_get_bitmap_index(unsigned long key){	return key % (1 << KHO_BITMAP_SIZE_LOG2);} static unsigned long kho_radix_get_table_index(unsigned long key,					       unsigned int level){	int s; 	s = ((level - 1) * KHO_TABLE_SIZE_LOG2) + KHO_BITMAP_SIZE_LOG2;	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. * @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. * * NOTE: Currently only keys of width up to %KHO_RADIX_KEY_WIDTH are supported. * This limit only exists because current users of the radix tree don't use more * than that. Changing the maximum width requires changing the tree depth, which * needs bumping the ABI version. * * Return: 0 on success, or a negative error code on failure. */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 };	struct kho_radix_node *anchor_node = NULL;	struct kho_radix_node *node = tree->root;	struct kho_radix_node *new_node;	unsigned int i, idx, anchor_idx;	struct kho_radix_leaf *leaf;	int err = 0; 	if (WARN_ON_ONCE(!tree->root))		return -EINVAL; 	if (unlikely(fls64(key) > KHO_RADIX_KEY_WIDTH))		return -ERANGE; 	might_sleep(); 	guard(mutex)(&tree->lock); 	/* Go from high levels to low levels */	for (i = KHO_TREE_MAX_DEPTH - 1; i > 0; i--) {		idx = kho_radix_get_table_index(key, i); 		if (node->table[idx]) {			node = phys_to_virt(node->table[idx]);			continue;		} 		/* Next node is empty, create a new node for it */		new_node = kho_radix_alloc_node();		if (!new_node) {			err = -ENOMEM;			goto err_free_nodes;		} 		node->table[idx] = virt_to_phys(new_node); 		/*		 * Capture the node where the new branch starts for cleanup		 * if allocation fails.		 */		if (!anchor_node) {			anchor_node = node;			anchor_idx = idx;		}		intermediate_nodes[i] = new_node; 		node = new_node;	} 	/* Handle the leaf level bitmap (level 0) */	idx = kho_radix_get_bitmap_index(key);	leaf = (struct kho_radix_leaf *)node;	__set_bit(idx, leaf->bitmap); 	return 0; err_free_nodes:	for (i = KHO_TREE_MAX_DEPTH - 1; i > 0; i--) {		if (intermediate_nodes[i])			kho_radix_free_node(intermediate_nodes[i]);	}	if (anchor_node)		anchor_node->table[anchor_idx] = 0; 	return err;}EXPORT_SYMBOL_GPL(kho_radix_add_key); /** * kho_radix_del_key - Removes the key from the radix tree. * @tree: The KHO radix tree. * @key: The key to remove. * * This function traverses the radix tree and clears the bit corresponding to * 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_key(struct kho_radix_tree *tree, unsigned long key){	struct kho_radix_node *node = tree->root;	struct kho_radix_leaf *leaf;	unsigned int i, idx; 	if (WARN_ON_ONCE(!tree->root))		return; 	/* Keys wider than KHO_RADIX_KEY_WIDTH are not allowed to be added. */	if (unlikely(fls64(key) > KHO_RADIX_KEY_WIDTH))		return; 	might_sleep(); 	guard(mutex)(&tree->lock); 	/* Go from high levels to low levels */	for (i = KHO_TREE_MAX_DEPTH - 1; i > 0; i--) {		idx = kho_radix_get_table_index(key, i); 		/*		 * Attempting to delete a page that has not been preserved,		 * return with a warning.		 */		if (WARN_ON(!node->table[idx]))			return; 		node = phys_to_virt(node->table[idx]);	} 	/* Handle the leaf level bitmap (level 0) */	leaf = (struct kho_radix_leaf *)node;	idx = kho_radix_get_bitmap_index(key);	__clear_bit(idx, leaf->bitmap);}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_init_tree - initialize the radix tree. * @tree:   the tree to initialize. * @root:   root table of the radix tree. * * Initialize the radix tree with the given root node. If root is %NULL, an * empty root table is allocated. If root is not %NULL, it is the caller's * responsibility to make sure the root is valid and in the correct format. * * Return: 0 on success, -errno on failure. */int kho_radix_init_tree(struct kho_radix_tree *tree, struct kho_radix_node *root){	if (!root)		root = kho_radix_alloc_node();	if (!root)		return -ENOMEM; 	tree->root = root;	mutex_init(&tree->lock);	return 0;}EXPORT_SYMBOL_GPL(kho_radix_init_tree); /** * 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);	tree->root = NULL;}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){	unsigned long *bitmap = (unsigned long *)leaf;	unsigned int i;	int err; 	if (cb->node) {		err = cb->node(virt_to_phys(leaf), data);		if (err)			return err;	} 	if (!cb->leaf)		return 0; 	for_each_set_bit(i, bitmap, PAGE_SIZE * BITS_PER_BYTE) {		err = cb->leaf(key | i, data);		if (err)			return err;	} 	return 0;} static int __kho_radix_walk_tree(struct kho_radix_node *root,				 unsigned int level, unsigned long start,				 const struct kho_radix_walk_cb *cb, void *data){	struct kho_radix_node *node;	struct kho_radix_leaf *leaf;	unsigned long key, i;	unsigned int shift;	int err; 	if (cb->node) {		err = cb->node(virt_to_phys(root), data);		if (err)			return err;	} 	for (i = 0; i < PAGE_SIZE / sizeof(phys_addr_t); i++) {		if (!root->table[i])			continue; 		shift = ((level - 1) * KHO_TABLE_SIZE_LOG2) +			KHO_BITMAP_SIZE_LOG2;		key = start | (i << shift); 		node = phys_to_virt(root->table[i]); 		if (level == 1) {			/*			 * we are at level 1,			 * node is pointing to the level 0 bitmap.			 */			leaf = (struct kho_radix_leaf *)node;			err = kho_radix_walk_leaf(leaf, key, cb, data);		} else {			err  = __kho_radix_walk_tree(node, level - 1,						     key, cb, data);		} 		if (err)			return err;	} 	return 0;} /** * 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. * * Return: 0 if the walk completed the specified tree, or the non-zero return *         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, 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,				     data);}EXPORT_SYMBOL_GPL(kho_radix_walk_tree); /* For physically contiguous 0-order pages. */static void kho_init_pages(struct page *page, unsigned long nr_pages){	for (unsigned long i = 0; i < nr_pages; i++) {		set_page_count(page + i, 1);		/* Clear each page's codetag to avoid accounting mismatch. */		clear_page_tag_ref(page + i);	}} static void kho_init_folio(struct page *page, unsigned int order){	unsigned long nr_pages = (1 << order); 	/* Head page gets refcount of 1. */

Lines 1–500 of 2098. Load more