Re: [PATCH v2] rbtree: remove unneeded explicit alignment in struct rb_node

[Mete Polat <metepolat2000@gmail.com>]

On Mon, Aug 09, 2021 at 02:25:35PM +0200, Geert Uytterhoeven wrote:
> Hi Mete,
> 
> On Fri, Aug 6, 2021 at 5:22 PM Mete Polat <metepolat2000@gmail.com> wrote:
> > Commit e977145aeaad ("[RBTREE] Add explicit alignment to sizeof(long) for
> > struct rb_node.") adds an explicit alignment to the struct rb_node due to
> > some speciality of the CRIS architecture.
> >
> > The support for the CRIS architecture was removed with commit c690eddc2f3b
> > ("CRIS: Drop support for the CRIS port")
> >
> > So, remove this now unneeded explicit alignment in struct rb_node as well.
> >
> > This basically reverts commit e977145aeaad ("[RBTREE] Add explicit
> > alignment to sizeof(long) for struct rb_node.").
> >
> > The rbtree node color is stored in the LSB of '__rb_parent_color'.
> > Only mask the first bit in '__rb_parent()', otherwise it modifies the
> > node's parent address on m68k.
> >
> > Reported-by: Randy Dunlap <rdunlap@infradead.org>
> > Reported-by: Mete Polat <metepolat2000@gmail.com>
> > Signed-off-by: Lukas Bulwahn <lukas.bulwahn@gmail.com>
> > Signed-off-by: Mete Polat <metepolat2000@gmail.com>
> > ---
> > I have tested it on x86, but not on m68k. Can you ack that Geert?
> 
> Unfortunately not.  Just booting on ARAnyM gives:
> 
> Unable to handle kernel access at virtual address 84abc227
> Oops: 00000000
> Modules linked in:
> PC: [<b45b0005>] 0xb45b0005
> SR: 2700  SP: fc24ede1  a2: 01322b40
> d0: b45aff7c    d1: 00002708    d2: 00000000    d3: 0033a6a4
> d4: 00000005    d5: 95847357    a0: b45b0005    a1: 000f4240
> Process sh (pid: 402, task=672891a8)
> Frame format=7 eff addr=b45b0005 ssw=0546 faddr=b45b0005
> wb 1 stat/addr/data: 0000 00000000 00000000
> wb 2 stat/addr/data: 0000 00000000 00000000
> wb 3 stat/addr/data: 0000 b45b0005 00000000
> push data: 00000000 00000000 00000000 00000000
> Stack from 0131debc:
>         0004ddf4 0122e0a4 0122e0a4 00477c26 00000000 00000000 00000005 95847357
>         00002708 0004558e 0033ab30 00000002 01003180 0047273c 0131df88 0033a6a4
>         00477c3a 00477c24 0004dfee 00000005 95847357 00002708 0000000f 00000001
>         9915a000 0000000d 0004d430 01322b40 00000001 00002604 00000000 00006e50
>         00000001 00000000 0004560c 0000000d 00000000 00000000 efc3aa78 efc3aa78
>         c0158c0c 8009ff68 0047273c efc3aa64 c01537a8 0131df8c 000456b6 0047273c
> Call Trace: [<0004ddf4>] __hrtimer_run_queues.constprop.0+0xba/0x144
>  [<00002708>] calibrate_delay+0xd6/0x18a
>  [<0004558e>] __irq_wake_thread+0x0/0x40
>  [<0033ab30>] printk+0x0/0x18
>  [<0033a6a4>] warn_slowpath_fmt+0x0/0x62
>  [<0004dfee>] hrtimer_run_queues+0xb4/0xc0
>  [<00002708>] calibrate_delay+0xd6/0x18a
>  [<0004d430>] update_process_times+0x38/0x8c
>  [<00002604>] wait_for_initramfs+0x30/0x58
>  [<00006e50>] mfp_timer_c_handler+0x2c/0x3c
>  [<0004560c>] __handle_irq_event_percpu+0x3e/0xcc
>  [<000456b6>] handle_irq_event_percpu+0x1c/0x52
>  [<0004570a>] handle_irq_event+0x1e/0x30
>  [<00047aa2>] handle_simple_irq+0x4a/0x4e
>  [<00045062>] handle_irq_desc+0x1e/0x28
>  [<00002cac>] do_IRQ+0x20/0x32
>  [<00002bcc>] user_irqvec_fixup+0xc/0x14
>  [<0010c00b>] mb_cache_create+0x47/0xdc
> 
> Code: dde0 dde0 dde0 dde0 dde0 dde0 dde0 dde0 Bad PC value.
> Disabling lock debugging due to kernel taint
> Kernel panic - not syncing: Aiee, killing interrupt handler!
> ---[ end Kernel panic - not syncing: Aiee, killing interrupt handler! ]---
> 
> > --- a/include/linux/rbtree.h
> > +++ b/include/linux/rbtree.h
> > @@ -25,8 +25,7 @@ struct rb_node {
> >         unsigned long  __rb_parent_color;
> >         struct rb_node *rb_right;
> >         struct rb_node *rb_left;
> > -} __attribute__((aligned(sizeof(long))));
> > -    /* The alignment might seem pointless, but allegedly CRIS needs it */
> > +};
> >
> >  struct rb_root {
> >         struct rb_node *rb_node;
> > diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h
> > index d1c53e9d8c75..94b6a0f4499e 100644
> > --- a/include/linux/rbtree_augmented.h
> > +++ b/include/linux/rbtree_augmented.h
> > @@ -145,7 +145,7 @@ RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,                                            \
> >  #define        RB_RED          0
> >  #define        RB_BLACK        1
> >
> > -#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
> > +#define __rb_parent(pc)    ((struct rb_node *)(pc & ~1))
> 
> Are you sure you can do this, i.e. that nothing else relies on the
> alignment to (at least) 4 bytes?

I am quite sure that the RBT algorithm itself only relies on the LSB,
but I am unsure yet if RCU requires this natural alignment as Peter
mentioned.

> 
> There is another definition of rb_parent().  If I make a similar change there:
> 
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -31,7 +31,7 @@ struct rb_root {
>         struct rb_node *rb_node;
>  };
> 
> -#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
> +#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~1))
> 
>  #define RB_ROOT        (struct rb_root) { NULL, }
>  #define        rb_entry(ptr, type, member) container_of(ptr, type, member)
> 
> the system boots on ARAnyM, but I prefer to be a bit cautious...

Ah yes I forgot that the same makro is also defined in the other header
file as well; and similary in some other locations:

./scripts/gdb/linux/rbtree.py:
parent = gdb.Value(node['__rb_parent_color'] & ~3)
./tools/include/linux/rbtree.h:
#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))


> 
> Gr{oetje,eeting}s,
> 
>                         Geert
> 
> -- 
> Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org
> 
> In personal conversations with technical people, I call myself a hacker. But
> when I'm talking to journalists I just say "programmer" or something like that.
>                                 -- Linus Torvalds