LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Michel Lespinasse <michel@lespinasse.org>
To: Mete Polat <metepolat2000@gmail.com>
Cc: Davidlohr Bueso <dbueso@suse.de>, Arnd Bergmann <arnd@arndb.de>,
	Lukas Bulwahn <lukas.bulwahn@gmail.com>,
	Michel Lespinasse <michel@lespinasse.org>,
	Andrew Morton <akpm@linux-foundation.org>,
	Jesper Nilsson <jesper@jni.nu>,
	David Woodhouse <dwmw2@infradead.org>,
	Ingo Molnar <mingo@kernel.org>,
	Peter Zijlstra <peterz@infradead.org>,
	Randy Dunlap <rdunlap@infradead.org>,
	kernel-janitors@vger.kernel.org,
	Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
	Geert Uytterhoeven <geert@linux-m68k.org>
Subject: Re: [PATCH] rbtree: remove unneeded explicit alignment in struct rb_node
Date: Fri, 6 Aug 2021 01:52:45 -0700	[thread overview]
Message-ID: <20210806085245.GB14650@lespinasse.org> (raw)
In-Reply-To: <YQwd2puXiSiUWEE1@precision>

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

  reply	other threads:[~2021-08-06  8:59 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-08-05 13:32 Lukas Bulwahn
2021-08-05 14:02 ` Arnd Bergmann
2021-08-05 14:14   ` Lukas Bulwahn
2021-08-05 15:02   ` Davidlohr Bueso
2021-08-05 15:10     ` Peter Zijlstra
2021-08-05 17:20     ` Mete Polat
2021-08-06  8:52       ` Michel Lespinasse [this message]
2021-08-06 11:57         ` Peter Zijlstra
2021-08-10 22:46   ` Jesper Nilsson

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20210806085245.GB14650@lespinasse.org \
    --to=michel@lespinasse.org \
    --cc=akpm@linux-foundation.org \
    --cc=arnd@arndb.de \
    --cc=dbueso@suse.de \
    --cc=dwmw2@infradead.org \
    --cc=geert@linux-m68k.org \
    --cc=jesper@jni.nu \
    --cc=kernel-janitors@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=lukas.bulwahn@gmail.com \
    --cc=metepolat2000@gmail.com \
    --cc=mingo@kernel.org \
    --cc=peterz@infradead.org \
    --cc=rdunlap@infradead.org \
    --subject='Re: [PATCH] rbtree: remove unneeded explicit alignment in struct rb_node' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).