Skip to contentSkip to conversation

kho: fix KHO_TREE_MAX_DEPTH for non-4KB page sizes

PATCH Applied George Guo 4 participants 7 messages May 9 – May 16

Subsystems (3)
lore
Share & tools
lore

George Guo

author
#0 lore raw

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

From: George Guo <[email protected]>

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")
---
 include/linux/kho/abi/kexec_handover.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/kho/abi/kexec_handover.h +1 -1
index 7e847a2339b0..db9bda6dd310 100644
@@ -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,
 };
 
Signature · 1 line
2.25.1
maintainer Applied
#1 lore raw

From: Mike Rapoport (Microsoft) <[email protected]>

Quoted 11 lines · George Guo

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.

maintainer
#2 lore raw
In reply to George Guo
Quoted 8 lines · George Guo

From: George Guo <[email protected]>

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.

Quoted 15 lines

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.

Quoted 4 lines

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.

Quoted 21 lines
Fixes 3f2ad90060f6 ("kho: adopt radix tree for preserved memory tracking")
---
 include/linux/kho/abi/kexec_handover.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/kho/abi/kexec_handover.h +1 -1
index 7e847a2339b0..db9bda6dd310 100644
@@ -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,
 };
Signature · 2 lines
Regards,
Pratyush Yadav
maintainer
#3 lore raw
Quoted 6 lines · Pratyush Yadav
Quoted 4 lines · George Guo

From: George Guo <[email protected]>

KHO_TREE_MAX_DEPTH is calculated as:

Quoted 8 lines
Quoted 4 lines

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 ...

Quoted 3 lines

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.

Quoted 3 lines
Signature · 2 lines
Regards,
Pratyush Yadav
Signature · 2 lines
Sincerely yours,
Mike.
author
#4 lore raw
In reply to Pratyush Yadav

Sorry for the late reply.

Quoted 2 lines · Pratyush Yadav

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.

Quoted 4 lines

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 */

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!
maintainer
#5 lore raw
Quoted 10 lines · George Guo

Sorry for the late reply.

Quoted 2 lines · Pratyush Yadav

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.

I massaged the changelog and reapplied this to the liveupdate tree:

https://git.kernel.org/liveupdate/c/d13dfb48dfa3

Signature · 2 lines
Sincerely yours,
Mike.
maintainer Reviewed-by on v1 1/1
#6 lore raw
In reply to George Guo
Quoted 28 lines · George Guo

From: George Guo <[email protected]>

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.

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

The patch fixes 16K support on ARM64.

Pasha