linux-kernel - Re: Purpose of maple_node objects to be its size aligned

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]

Message-ID: <81b61c42-3c2b-bce3-d667-b45478d5fccd@quicinc.com>
Date: Tue, 23 Jan 2024 20:10:07 +0530
From: Charan Teja Kalla <quic_charante@...cinc.com>
To: Matthew Wilcox <willy@...radead.org>, Vlastimil Babka <vbabka@...e.cz>
CC: <Liam.Howlett@...cle.com>, "linux-mm@...ck.org" <linux-mm@...ck.org>,
        LKML
	<linux-kernel@...r.kernel.org>
Subject: Re: Purpose of maple_node objects to be its size aligned

Thanks Matthew!!

On 1/23/2024 6:56 PM, Matthew Wilcox wrote:
>> I am just curious about the purpose of maple node slab objects to be its
>> size aligned, but I can understand why they need to be cache aligned.
> Because we encode various information in the bottom few bits of the
> maple node pointer.
> 
> /*
>  * The Maple Tree squeezes various bits in at various points which aren't
>  * necessarily obvious.  Usually, this is done by observing that pointers are
>  * N-byte aligned and thus the bottom log_2(N) bits are available for use.  We
>  * don't use the high bits of pointers to store additional information because
>  * we don't know what bits are unused on any given architecture.
>  *
>  * Nodes are 256 bytes in size and are also aligned to 256 bytes, giving us 8
>  * low bits for our own purposes.  Nodes are currently of 4 types:
>  * 1. Single pointer (Range is 0-0)
>  * 2. Non-leaf Allocation Range nodes
>  * 3. Non-leaf Range nodes
>  * 4. Leaf Range nodes All nodes consist of a number of node slots,
>  *    pivots, and a parent pointer.
>  */
> 

I got it. Looks like I need to revisit the maple tree documentation
before asking such questions.

> That seems like a very badly implemented patch.  Rather than make all
> objects left & right redzone, we should simply insert a redzone at
> the beginning of the slab.  ie
> 
> 0	redzone
> 256	node
> 512	redzone
> 768	node
> 1024	redzone
> 1280	node
> [...]
> 3072	redzone
> 3382	node
> 3584	redzone
> 3840	wasted space
> 
This seems to work when only redzone is enabled?

I think it will again 768b aligned if any other debug option enabled,
say U. It is:
(size aligned red zone + maple node +  right red zone (size of (void*))
+ alloc/free track).

My understanding to have both left and right red zone is:
                /*
                 * Add some empty padding so that __we can catch
                 * overwrites from earlier objects rather than let
                 * tracking information or the free pointer be
                 * corrupted if a user writes before the start
                 * of the object__.
                 */

When all the debug options enabled, the slab object will roughly look
like below:

Left red zone | object | right red zone | free pointer | alloc/free
track | padding

> Instead of getting only five nodes per 4kB page, we'd get seven; about
> a 30% reduction in memory usage.
> 
> Slab redzoning is not a feature people turn on often, so I'm not
> surprised nobody's noticed before now.

+Vlastimil. The patch in discussion is d86bd1bece6f ("mm/slub: support
left redzone").

Thanks,
Charan