[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

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

[Mike Rapoport]

On Mon, May 11, 2026 at 12:40:01PM +0200, Pratyush Yadav wrote:
> 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?

arm64 can have 16k pages, but ...
 
> 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.
 
... as it looks like your math is correct, I'm going to drop the patch for
now.

> -- 
> Regards,
> Pratyush Yadav

-- 
Sincerely yours,
Mike.

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

[George Guo]

Sorry for the late reply.

On Mon, May 11 2026, Pratyush Yadav wrote:

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

Yes, we are adding KHO support for LoongArch (16KB page size). The
LoongArch patches are being prepared separately. This fix is a
prerequisite.

> Maybe I don't understand the math so well, but I can't see the problem.
> ...
> level = 4, s = 50, idx = 1
> What am I missing?

The issue is that all three operations start the traversal at
KHO_TREE_MAX_DEPTH - 1, not KHO_TREE_MAX_DEPTH:

  kho_radix_add_page()  line 180: for (i = KHO_TREE_MAX_DEPTH - 1; i > 0; i--)
  kho_radix_del_page()  line 255: for (i = KHO_TREE_MAX_DEPTH - 1; i > 0; i--)
  kho_radix_walk_tree() line 356: __kho_radix_walk_tree(..., KHO_TREE_MAX_DEPTH - 1, ...)

So with depth=4 the effective top level is 3, not 4.

phys_to_page() of that address faults in kho_preserved_memory_reserve().

This is confirmed by a kernel panic on 7.1-rc3 LoongArch (16KB pages)
without the fix. With depth=5 the top level is 4 (shift=50):

  (key >> 50) % 2048 = 1   /* order bit correctly captured */

Signed-off-by: George Guo <guodongtai@kylinos.cn>

Panic log on 7.1-rc3 LoongArch (16KB pages) without the fix:

[    0.000000] CPU 0 Unable to handle kernel paging request at virtual address 00003d3ffe000028, era == 90000000c162f10c, ra == 90000000c162f0f8
[    0.000000] Oops[#1]:
...
[    0.000000] Call Trace:
[    0.000000] [<90000000c162f10c>] kho_preserved_memory_reserve+0xc4/0xe8
[    0.000000] [<90000000c0129f88>] __kho_radix_walk_tree+0xf0/0x138
[    0.000000] [<90000000c0129f10>] __kho_radix_walk_tree+0x78/0x138
[    0.000000] [<90000000c012b730>] kho_radix_walk_tree+0x88/0xe8
[    0.000000] [<90000000c162f874>] kho_memory_init+0x220/0x4e4
[    0.000000] [<90000000c1639b38>] mm_core_init+0x168/0x1a0
[    0.000000] [<90000000c1620d50>] start_kernel+0x5c4/0x778
[    0.000000] Kernel panic - not syncing: Attempted to kill the idle task!