[PATCH 1/1] kho: fix KHO_TREE_MAX_DEPTH for non-4KB page sizes

[PATCH 1/1] kho: fix KHO_TREE_MAX_DEPTH for non-4KB page sizes

[George Guo]

From: George Guo <guodongtai@kylinos.cn>

KHO_TREE_MAX_DEPTH is calculated as:

  DIV_ROUND_UP(KHO_ORDER_0_LOG2 - KHO_BITMAP_SIZE_LOG2,
               KHO_TABLE_SIZE_LOG2) + 1

For systems with 16KB pages (e.g. LoongArch), this gives a depth of 4,
with the top-level shift at bit 39.  The order-0 bit sits at bit 50
(KHO_ORDER_0_LOG2 = 64 - PAGE_SHIFT = 50).  When inserting or reading
a key, the index extracted at the top level is:

  (1 << 50) >> 39 = 2048

2048 is exactly the table size (PAGE_SIZE / sizeof(phys_addr_t) = 2048
for 16KB pages), so it wraps to 0, aliasing the order bit to index 0
and losing it silently.

On the second kernel, kho_radix_decode_key() sees a key without the
order bit, calls fls64() on the wrong bit, computes a wrong order and
thus a garbage physical address. phys_to_page() of that address faults
in kho_preserved_memory_reserve(), causing a kernel panic early in boot.

Fix by adding +1 to the DIV_ROUND_UP numerator so the formula accounts
for the order bit itself, giving depth 5 for 16KB pages. The top-level
shift becomes 50, and (1 << 50) >> 50 = 1, which is nonzero and
unambiguous. For 4KB and 64KB page sizes the depth is unchanged.

Fixes: 3f2ad90060f6 ("kho: adopt radix tree for preserved memory tracking")

Tested-by: Kexin Liu <liukexin@kylinos.cn>
Signed-off-by: George Guo <guodongtai@kylinos.cn>
---
 include/linux/kho/abi/kexec_handover.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/linux/kho/abi/kexec_handover.h b/include/linux/kho/abi/kexec_handover.h
index 7e847a2339b0..db9bda6dd310 100644
--- a/include/linux/kho/abi/kexec_handover.h
+++ b/include/linux/kho/abi/kexec_handover.h
@@ -274,7 +274,7 @@ enum kho_radix_consts {
 	 * and 1 bitmap level.
 	 */
 	KHO_TREE_MAX_DEPTH =
-		DIV_ROUND_UP(KHO_ORDER_0_LOG2 - KHO_BITMAP_SIZE_LOG2,
+		DIV_ROUND_UP(KHO_ORDER_0_LOG2 - KHO_BITMAP_SIZE_LOG2 + 1,
 			     KHO_TABLE_SIZE_LOG2) + 1,
 };
 
-- 
2.25.1

Re: [PATCH 1/1] kho: fix KHO_TREE_MAX_DEPTH for non-4KB page sizes

[Mike Rapoport]

From: Mike Rapoport (Microsoft) <rppt@kernel.org>

On Sat, 09 May 2026 10:44:15 +0800, George Guo wrote:
> KHO_TREE_MAX_DEPTH is calculated as:
> 
>   DIV_ROUND_UP(KHO_ORDER_0_LOG2 - KHO_BITMAP_SIZE_LOG2,
>                KHO_TABLE_SIZE_LOG2) + 1
> 
> For systems with 16KB pages (e.g. LoongArch), this gives a depth of 4,
> with the top-level shift at bit 39.  The order-0 bit sits at bit 50
> (KHO_ORDER_0_LOG2 = 64 - PAGE_SHIFT = 50).  When inserting or reading
> a key, the index extracted at the top level is:
> 
> [...]

Applied to fixes branch of liveupdate/linux.git tree, thanks!

[1/1] kho: fix KHO_TREE_MAX_DEPTH for non-4KB page sizes
      commit: eaf3933ec58da601cf0008afbcca7cf5433321e8

tree: https://git.kernel.org/pub/scm/linux/kernel/git/liveupdate/linux
branch: fixes

--
Sincerely yours,
Mike.

Re: [PATCH 1/1] kho: fix KHO_TREE_MAX_DEPTH for non-4KB page sizes

[Pratyush Yadav]

On Sat, May 09 2026, George Guo wrote:

> From: George Guo <guodongtai@kylinos.cn>
>
> KHO_TREE_MAX_DEPTH is calculated as:
>
>   DIV_ROUND_UP(KHO_ORDER_0_LOG2 - KHO_BITMAP_SIZE_LOG2,
>                KHO_TABLE_SIZE_LOG2) + 1
>
> For systems with 16KB pages (e.g. LoongArch), this gives a depth of 4,

As of now, we only support KHO on x86 and arm64. Support for other
architectures is not there. Are you working on supporting it for
LoongArch? What is your use case?

Without LoongArch supporting KHO, this remains a purely theoretical fix.

> with the top-level shift at bit 39.  The order-0 bit sits at bit 50
> (KHO_ORDER_0_LOG2 = 64 - PAGE_SHIFT = 50).  When inserting or reading
> a key, the index extracted at the top level is:
>
>   (1 << 50) >> 39 = 2048
>
> 2048 is exactly the table size (PAGE_SIZE / sizeof(phys_addr_t) = 2048
> for 16KB pages), so it wraps to 0, aliasing the order bit to index 0
> and losing it silently.
>
> On the second kernel, kho_radix_decode_key() sees a key without the
> order bit, calls fls64() on the wrong bit, computes a wrong order and
> thus a garbage physical address. phys_to_page() of that address faults
> in kho_preserved_memory_reserve(), causing a kernel panic early in boot.
>
> Fix by adding +1 to the DIV_ROUND_UP numerator so the formula accounts
> for the order bit itself, giving depth 5 for 16KB pages. The top-level
> shift becomes 50, and (1 << 50) >> 50 = 1, which is nonzero and
> unambiguous. For 4KB and 64KB page sizes the depth is unchanged.

Maybe I don't understand the math so well, but I can't see the problem.
Here's what I did in my calculator (the lines starting with the = are
the result of the previous statement):

First, define all the constants:

    PAGE_SHIFT = 14
    = 14

    KHO_ORDER_0_LOG2 = 64 − PAGE_SHIFT
    = 50

    KHO_TABLE_SIZE_LOG2  = log(2; (1 << PAGE_SHIFT) / 8)
    = 11

    KHO_BITMAP_SIZE_LOG2 = PAGE_SHIFT + 3
    = 17

    KHO_TREE_MAX_DEPTH = ((KHO_ORDER_0_LOG2 − KHO_BITMAP_SIZE_LOG2) / KHO_TABLE_SIZE_LOG2) + 1
    = 4

Then let's assume the highest possible physical address (52-bit
addressing) and order 0:

    phys = 0xffffffffff000
    = 4503599627366400

    order = 0
    = 0

This makes the key:

    key = (1 << (KHO_ORDER_0_LOG2 − order)) | (phys >> (PAGE_SHIFT + order))
    = 1126174784749567

For higher orders the numerical value of the key will be smaller so this
is the highest possible key.

Then do what kho_radix_get_table_index() does to get the index on level
4:

    level = 4
    = 4

    s = ((level − 1) × KHO_TABLE_SIZE_LOG2) + KHO_BITMAP_SIZE_LOG2
    = 50

    idx = mod((key >> s); (1 << KHO_TABLE_SIZE_LOG2))
    = 1

If we do get a 5th level, the index would be:

    level = 5
    = 5

    s = ((level − 1) × KHO_TABLE_SIZE_LOG2) + KHO_BITMAP_SIZE_LOG2
    = 61

    idx = mod((key >> s); (1 << KHO_TABLE_SIZE_LOG2))
    = 0

So based on this, looks to me that the 5th level table won't ever go
above index 0 and the 4th level is enough to represent all possible
keys.

What am I missing?

Also, Jason, can you please help review this? You understand the math of
the radix tree the best I reckon.

>
> Fixes: 3f2ad90060f6 ("kho: adopt radix tree for preserved memory tracking")
>
> Tested-by: Kexin Liu <liukexin@kylinos.cn>
> Signed-off-by: George Guo <guodongtai@kylinos.cn>
> ---
>  include/linux/kho/abi/kexec_handover.h | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/include/linux/kho/abi/kexec_handover.h b/include/linux/kho/abi/kexec_handover.h
> index 7e847a2339b0..db9bda6dd310 100644
> --- a/include/linux/kho/abi/kexec_handover.h
> +++ b/include/linux/kho/abi/kexec_handover.h
> @@ -274,7 +274,7 @@ enum kho_radix_consts {
>  	 * and 1 bitmap level.
>  	 */
>  	KHO_TREE_MAX_DEPTH =
> -		DIV_ROUND_UP(KHO_ORDER_0_LOG2 - KHO_BITMAP_SIZE_LOG2,
> +		DIV_ROUND_UP(KHO_ORDER_0_LOG2 - KHO_BITMAP_SIZE_LOG2 + 1,
>  			     KHO_TABLE_SIZE_LOG2) + 1,
>  };

-- 
Regards,
Pratyush Yadav