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@xxxxxxxxxxxxxx/ > > 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
