linux-kernel - Re: [PATCH v2 1/2] maple_tree: Fix mas_skip

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] [day] [month] [year] [list]

Date:   Wed, 8 Mar 2023 09:49:05 +0100
From:   Snild Dolkow <snild@...y.com>
To:     "Liam R. Howlett" <Liam.Howlett@...cle.com>,
        maple-tree@...ts.infradead.org, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org,
        Andrew Morton <akpm@...ux-foundation.org>,
        Stable@...r.kernel.org, zhangpeng.00@...edance.com
Subject: Re: [PATCH v2 1/2] maple_tree: Fix mas_skip_node() end slot detection

On 2023-03-07 19:02, Liam R. Howlett wrote:
> mas_skip_node() is used to move the maple state to the node with a
> higher limit.  It does this by walking up the tree and increasing the
> slot count.  Since slot count may not be able to be increased, it may
> need to walk up multiple times to find room to walk right to a higher
> limit node.  The limit of slots that was being used was the node limit
> and not the last location of data in the node.  This would cause the
> maple state to be shifted outside actual data and enter an error state,
> thus returning -EBUSY.
> 
> The result of the incorrect error state means that mas_awalk() would
> return an error instead of finding the allocation space.
> 
> The fix is to use mas_data_end() in mas_skip_node() to detect the nodes
> data end point and continue walking the tree up until it is safe to move
> to a node with a higher limit.
> 
> The walk up the tree also sets the maple state limits so remove the
> buggy code from mas_skip_node().  Setting the limits had the unfortunate
> side effect of triggering another bug if the parent node was full and
> the there was no suitable gap in the second last child, but room in the
> next child.
> 
> mas_skip_node() may also be passed a maple state in an error state from
> mas_anode_descend() when no allocations are available.  Return on such
> an error state immediately.
> 
> Reported-by: Snild Dolkow <snild@...y.com>
> Link: https://lore.kernel.org/linux-mm/cb8dc31a-fef2-1d09-f133-e9f7b9f9e77a@sony.com/
> Cc: <Stable@...r.kernel.org>
> Cc: Peng Zhang <zhangpeng.00@...edance.com>
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> Signed-off-by: Liam R. Howlett <Liam.Howlett@...cle.com>

With the same method as in 
https://lore.kernel.org/lkml/6f674f9e-9f32-dabb-60be-0e757e145b14@sony.com/, 
1000 runs all pass:

linux$ egrep -o 'Failed|Success' qemu.log | sort | uniq -c
    1000 Success

If you want it:

Tested-by: Snild Dolkow <snild@...y.com>

//Snild