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

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

[Mete Polat]

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?

 include/linux/rbtree.h           | 3 +--
 include/linux/rbtree_augmented.h | 2 +-
 2 files changed, 2 insertions(+), 3 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index d31ecaf4fdd3..e9390be1ba67 100644
--- 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))
 
 #define __rb_color(pc)     ((pc) & 1)
 #define __rb_is_black(pc)  __rb_color(pc)
-- 
2.32.0

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

[Peter Zijlstra]

On Fri, Aug 06, 2021 at 05:22:08PM +0200, Mete Polat 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.

I still don't believe for a second this will actually work. We rely on
rcu_assign_pointer() and rcu_dereference() to work on the
rb_{left,right} members, and I don't think any architecture can provide
single copy atomic loads and stores that are not naturally aligned (eg.
when they straddle a cache or page boundary).

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

[Mete Polat]

On Fri, Aug 06, 2021 at 07:44:57PM +0200, Peter Zijlstra wrote:
> On Fri, Aug 06, 2021 at 05:22:08PM +0200, Mete Polat 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.
> 
> I still don't believe for a second this will actually work. We rely on
> rcu_assign_pointer() and rcu_dereference() to work on the
> rb_{left,right} members, and I don't think any architecture can provide
> single copy atomic loads and stores that are not naturally aligned (eg.
> when they straddle a cache or page boundary).
> 

I guess I am misunderstanding something here, but isn't that then a
problem that all rcu pointers in any struct would face, independent of
an 'aligned' struct attribute? As long as allocators do not place a
small struct as rb_node over page boundaries and the rcu pointers itself
are aligned we should be fine, aren't we? I am not sure if any of the
SL*B allocators is doing that though.

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

[Geert Uytterhoeven]

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?

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...

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

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

[Mete Polat]

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