linux-kernel - Re: [PATCH v6 08/71] Maple Tree: Add new data structure

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Tue, 1 Mar 2022 03:01:14 +0100
From:   Vasily Gorbik <gor@...ux.ibm.com>
To:     Liam Howlett <liam.howlett@...cle.com>
Cc:     "maple-tree@...ts.infradead.org" <maple-tree@...ts.infradead.org>,
        "linux-mm@...ck.org" <linux-mm@...ck.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Heiko Carstens <hca@...ux.ibm.com>,
        Alexander Gordeev <agordeev@...ux.ibm.com>
Subject: Re: [PATCH v6 08/71] Maple Tree: Add new data structure

On Mon, Feb 28, 2022 at 02:36:40PM +0000, Liam Howlett wrote:
> * Vasily Gorbik <gor@...ux.ibm.com> [220226 20:12]:
> > there is an endianness issue with maple_metadata. This is broken on
> > all big endian architectures. Tests are crashing. See potential fixup
> > below. Feel free to apply it or fix the issue in your own way. This does
> > not resolve all the issues with the patch series though.
> 
> The endianness isn't what's causing the issues.  The slots hold a
> pointer.  Either we can use the entire slot or none of the slot
> space.  You are just moving the metatdata around in the last slot.

Fair, it is either or, but shouldn't maple_metadata->end be aligned with
MAPLE_NODE_MASK?

> You may have been confused about my comment, which I believe is
> outdated, that talks about maple_arange_64, not maple_range_64.  I added
> maple_range_64 metadata and use the previous pivot to see if the slot
> contains data or not. If piv[14] == 0 or mas->max means we can use the
> slot for metadata.

This condition is not present in mas_dead_leaves() where we potentially
iterate over all 16 slots, simply checking that we have a "valid" node pointer
with:

entry & ~MAPLE_NODE_MASK != 0

This doesn't work on big endian without the fix.

maple_tree(0x121eaa0) flags 8, height 2 root 0x61a00004c316
0-18446744073709551615: node 0x61a00004c300 depth 0 type 2 parent 0x121eaa1 contents: 0x61a00002710c 14 0x61a00002a10c 29 0x61a00002d10c 44 0x61a00003070c
59 0x61a00003370c 74 0x61a00003670c 89 0x61a00003970c 104 0x61a00003c70c 119 0x61a00003f70c 134 0x61a00004270c 149 0x61a00004570c 164 0x61a00004870c
179 0x61a00004b70c 194 0x61a00004cf0c 203 0x61a00004c90c 18446744073709551615 0xe00000000000000
										^^^^^^^^^^^^^^^

==564249==ERROR: AddressSanitizer: SEGV on unknown address 0xe00000000000000 (pc 0x00000100ce72 bp 0x61a00004c300 sp 0x03fffe87de00 T0)
==564249==The signal is caused by a UNKNOWN memory access.
    #0 0x100ce72 in mte_set_node_dead ../../../lib/maple_tree.c:294
    #1 0x100ce72 in mas_dead_leaves ../../../lib/maple_tree.c:5381
    #2 0x100ce72 in mt_destroy_walk ../../../lib/maple_tree.c:5496
    #3 0x1069af3 in mte_destroy_walk ../../../lib/maple_tree.c:5543
    #4 0x1069af3 in __mt_destroy ../../../lib/maple_tree.c:6279
    #5 0x1069b77 in mtree_destroy ../../../lib/maple_tree.c:6294
    #6 0x106cf19 in check_dfs_preorder ../../../lib/test_maple_tree.c:35732
    #7 0x106d011 in maple_tree_seed ../../../lib/test_maple_tree.c:37188
    #8 0x1073ef9 in maple_tree_tests /devel/src/kernel/tools/testing/radix-tree/maple.c:47
    #9 0x1073f1f in main /devel/src/kernel/tools/testing/radix-tree/maple.c:54
    #10 0x3ffa1833731 in __libc_start_call_main (/lib64/libc.so.6+0x33731)
    #11 0x3ffa183380d in __libc_start_main@@GLIBC_2.34 (/lib64/libc.so.6+0x3380d)
    #12 0x1001d99  (/devel/src/kernel/tools/testing/radix-tree/maple+0x1001d99)