linux-kernel - Re: [PATCH] rbtree: remove unneeded explicit alignment in struct rb

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 for Android: free password hash cracker in your pocket

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

Message-ID: <20210806085245.GB14650@lespinasse.org>
Date:   Fri, 6 Aug 2021 01:52:45 -0700
From:   Michel Lespinasse <michel@...pinasse.org>
To:     Mete Polat <metepolat2000@...il.com>
Cc:     Davidlohr Bueso <dbueso@...e.de>, Arnd Bergmann <arnd@...db.de>,
        Lukas Bulwahn <lukas.bulwahn@...il.com>,
        Michel Lespinasse <michel@...pinasse.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Jesper Nilsson <jesper@....nu>,
        David Woodhouse <dwmw2@...radead.org>,
        Ingo Molnar <mingo@...nel.org>,
        Peter Zijlstra <peterz@...radead.org>,
        Randy Dunlap <rdunlap@...radead.org>,
        kernel-janitors@...r.kernel.org,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        Geert Uytterhoeven <geert@...ux-m68k.org>
Subject: Re: [PATCH] rbtree: remove unneeded explicit alignment in struct
 rb_node

On Thu, Aug 05, 2021 at 07:20:26PM +0200, Mete Polat wrote:
> On Thu, Aug 05, 2021 at 08:02:28AM -0700, Davidlohr Bueso wrote:
> > On 2021-08-05 07:02, Arnd Bergmann wrote:
> > > The revert would appear to change the alignment to 16 bits instead
> > > of 32 bits on m68k as well (not 8 bits as on cris), but I don't know if
> > > that
> > > can cause problems there.
> > 
> > Yeah I tried this a while back and it broke m68k, so it was a no go:
> > 
> > https://lore.kernel.org/lkml/CAMuHMdXeZvJ0X6Ah2CpLRoQJm+YhxAWBt-rUpxoyfOLTcHp+0g@mail.gmail.com/
> 
> The problem is that the field '__rb_parent_color' in struct rb_node is
> storing the color AND the pointer to the parent node at the same time.
> The color is stored in the least significant bit which is fine when
> rb_node is at least 16-bit aligned. I guess, it does not work on m68k
> because the makro
> 
> #define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
> 
> used to retrieve the parent pointer zeros the first two bits, not only
> the first one.
> 
> Maybe the effiency to store this one color bit in another field was
> required in the early days but I think moving the color to a seperate
> field is really the better way to go. It also makes reasoning about the
> algorithm easier.
> 
> I will create a patch.

I think moving the color to a separate word would be costly, both in space
(growing the struct rb_node) and in time. Feel free to try it, but I would
expect the rbtree performance tests to regress significantly.

__rb_parent() could probably be modified - it only needs to mask one bit,
I'm not sure why it masks two.

As to what would happen on 68k... hard to say, but I expect it should
be fine (if the compiler cared for the structs to be aligned, it
should do it on its own). Still, not sure how to test that either.

-- 
Michel "walken" Lespinasse