m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Guenter Roeck]

Hi,

a few days ago, m68k boot tests in linux-next started to crash.
I bisected the problem to commit 'xarray: Replace exceptional entries'.
Bisect and crash logs are attached below.

My apologies for the noise if this has already been reported and/or
addressed.

Guenter

---
# bad: [2e6381681ec48ed6dd455473a657d8a393518aa6] Add linux-next specific files for 20180622
# good: [ce397d215ccd07b8ae3f71db689aedb85d56ab40] Linux 4.18-rc1
git bisect start 'HEAD' 'v4.18-rc1'
# good: [07b762f7baf30aaa93d35f36ff367d4b36632059] Merge remote-tracking branch 'spi-nor/spi-nor/next'
git bisect good 07b762f7baf30aaa93d35f36ff367d4b36632059
# good: [c61d3dfe9381fc4b72541fd7698951b290d2a776] Merge remote-tracking branch 'tip/auto-latest'
git bisect good c61d3dfe9381fc4b72541fd7698951b290d2a776
# good: [a92ae111eb9e0f6f05f1173cf91c20fccda1a833] Merge remote-tracking branch 'scsi-mkp/for-next'
git bisect good a92ae111eb9e0f6f05f1173cf91c20fccda1a833
# bad: [1aa90eab1a14860f0d128ad67edf7b0381fa44e8] Merge remote-tracking branch 'xarray/xarray'
git bisect bad 1aa90eab1a14860f0d128ad67edf7b0381fa44e8
# good: [22ca6bc3dfd805a53f303fa5362fcc19e9c52565] Merge remote-tracking branch 'nvdimm/libnvdimm-for-next'
git bisect good 22ca6bc3dfd805a53f303fa5362fcc19e9c52565
# bad: [932116ce98f3d2ddf3e9eb243eebd62ebddebee9] mm: Convert page migration to XArray
git bisect bad 932116ce98f3d2ddf3e9eb243eebd62ebddebee9
# bad: [68fd9dcd423f49c4c916c0f222f12193f0c1655d] page cache: Rearrange address_space
git bisect bad 68fd9dcd423f49c4c916c0f222f12193f0c1655d
# bad: [8c0feb14b49670ea363ccef3f42165df64a5852e] xarray: Add XArray tags
git bisect bad 8c0feb14b49670ea363ccef3f42165df64a5852e
# bad: [88f2e731264b03319b9d0475ceadd0cc1d1dcefb] xarray: Change definition of sibling entries
git bisect bad 88f2e731264b03319b9d0475ceadd0cc1d1dcefb
# good: [0826cef09f48e767ad7416d1047fe4726addc49d] radix tree test suite: Enable ubsan
git bisect good 0826cef09f48e767ad7416d1047fe4726addc49d
# bad: [087ba81049d32c762831ae58de0b00fd6467ee8e] xarray: Replace exceptional entries
git bisect bad 087ba81049d32c762831ae58de0b00fd6467ee8e
# good: [8255ddef2101b02a1dc63461121903e25ed82873] dax: Fix use of zero page
git bisect good 8255ddef2101b02a1dc63461121903e25ed82873
# first bad commit: [087ba81049d32c762831ae58de0b00fd6467ee8e] xarray: Replace exceptional entries

---
...
SCSI subsystem initialized
------------[ cut here ]------------
WARNING: CPU: 0 PID: 1 at lib/idr.c:42 idr_alloc_u32+0x44/0xe8
Modules linked in:
CPU: 0 PID: 1 Comm: swapper Not tainted 4.18.0-rc1-next-20180622-mac #1
Stack from 0781fe3c:
        0781fe3c 0036d51c 000180d6 ffffffea 00000000 0036dfe6 00000020 000020e8
        003abf1c 0036dfe6 0001816a 0036d51f 0000002a 002b50e4 00000009 00000000
        00000000 00340ae9 002b50e4 0036d51f 0000002a 00000010 0036dfee 00000000
        00000010 0036dfe6 003f7518 0781feb8 00000000 00000078 002f7f6a 002b51e4
        003abf1c 0036dfe6 0781fed4 00000010 006000c0 07800100 00000010 0781ff8c
        00247160 003abf1c 0036dfe6 00000010 00000011 006000c0 00000078 00000005
Call Trace: [<000180d6>] __warn+0xc0/0xc2
 [<000020e8>] do_one_initcall+0x0/0x140
 [<0001816a>] warn_slowpath_null+0x26/0x2c
 [<002b50e4>] idr_alloc_u32+0x44/0xe8
 [<002b50e4>] idr_alloc_u32+0x44/0xe8
 [<002b51e4>] idr_alloc+0x5c/0x76
 [<00247160>] genl_register_family+0x14c/0x54c
 [<000020e8>] do_one_initcall+0x0/0x140
 [<003f0f02>] genl_init+0x0/0x34
 [<003f0ce6>] bpf_lwt_init+0x10/0x14
 [<003f0f0e>] genl_init+0xc/0x34
 [<00002142>] do_one_initcall+0x5a/0x140
 [<00029828>] parse_args+0x0/0x202
 [<000020e8>] do_one_initcall+0x0/0x140
 [<002bf6c4>] strcpy+0x0/0x1c
 [<00040004>] timekeeping_resume+0x280/0x2cc
 [<003df1e6>] kernel_init_freeable+0x176/0x190
 [<002bf6c4>] strcpy+0x0/0x1c
 [<003df1fc>] kernel_init_freeable+0x18c/0x190
 [<003f0f02>] genl_init+0x0/0x34
 [<002c4b66>] kernel_init+0x0/0xd2
 [<002c4b6e>] kernel_init+0x8/0xd2
 [<002c4b66>] kernel_init+0x0/0xd2
 [<000028e0>] ret_from_kernel_thread+0xc/0x14
---[ end trace 62c263e59debfdfe ]---
Kernel panic - not syncing: GENL: Cannot register controller: -22

CPU: 0 PID: 1 Comm: swapper Tainted: G        W         4.18.0-rc1-next-20180622-mac #1
Stack from 0781fef0:
        0781fef0 0036d51c 00018216 00000078 00000005 0055a040 00000000 003f0f02
        003ff868 003f7518 0781ff8c 003f0f34 0036849f ffffffea 00002142 00000078
        00000005 0055a040 00029828 000020e8 00000000 003f7538 003ff868 00000000
        003f7534 00000004 003f7518 002bf6c4 00040004 0055a052 0055a05a 003df1e6
        0033e814 0055a040 0038fd64 00000078 00000004 00000004 00000000 002bf6c4
        003df1fc 003f0f02 00000000 0781774c 0000000f 00000000 00000000 002c4b66
Call Trace: [<00018216>] panic+0xa6/0x230
 [<003f0f02>] genl_init+0x0/0x34
 [<003f0f34>] genl_init+0x32/0x34
 [<00002142>] do_one_initcall+0x5a/0x140
 [<00029828>] parse_args+0x0/0x202
 [<000020e8>] do_one_initcall+0x0/0x140
 [<002bf6c4>] strcpy+0x0/0x1c
 [<00040004>] timekeeping_resume+0x280/0x2cc
 [<003df1e6>] kernel_init_freeable+0x176/0x190
 [<002bf6c4>] strcpy+0x0/0x1c
 [<003df1fc>] kernel_init_freeable+0x18c/0x190
 [<003f0f02>] genl_init+0x0/0x34
 [<002c4b66>] kernel_init+0x0/0xd2
 [<002c4b6e>] kernel_init+0x8/0xd2
 [<002c4b66>] kernel_init+0x0/0xd2
 [<000028e0>] ret_from_kernel_thread+0xc/0x14
---[ end Kernel panic - not syncing: GENL: Cannot register controller: -22

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Matthew Wilcox]

On Fri, Jun 22, 2018 at 11:42:46AM -0700, Guenter Roeck wrote:
> Hi,
> 
> a few days ago, m68k boot tests in linux-next started to crash.
> I bisected the problem to commit 'xarray: Replace exceptional entries'.
> Bisect and crash logs are attached below.

Thank you!  I was afraid something like this might happen.  

> ------------[ cut here ]------------
> WARNING: CPU: 0 PID: 1 at lib/idr.c:42 idr_alloc_u32+0x44/0xe8

Line 42 is:

        if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
                return -EINVAL;

The pointer passed in to idr_alloc() is not 4-byte aligned; it's aligned
to a 2 byte boundary.  I'm having a little trouble seeing who it is that's
passing in what pointer ...

> Call Trace: [<000180d6>] __warn+0xc0/0xc2
>  [<000020e8>] do_one_initcall+0x0/0x140
>  [<0001816a>] warn_slowpath_null+0x26/0x2c
>  [<002b50e4>] idr_alloc_u32+0x44/0xe8
>  [<002b50e4>] idr_alloc_u32+0x44/0xe8
>  [<002b51e4>] idr_alloc+0x5c/0x76
>  [<00247160>] genl_register_family+0x14c/0x54c

It makes sense to here (other than idr_alloc being listed twice)

>  [<000020e8>] do_one_initcall+0x0/0x140
>  [<003f0f02>] genl_init+0x0/0x34

Assuming this is right, that would imply that genl_ctrl is not 4-byte
aligned.  Is that true?  I'm not familiar with the m68k alignment rules,
but it has a lot of 4-byte sized quantities in the struct, so I would
assume it's 4-byte aligned.

>  [<003f0ce6>] bpf_lwt_init+0x10/0x14

I don't think this is the caller.

>  [<003f0f0e>] genl_init+0xc/0x34
>  [<00002142>] do_one_initcall+0x5a/0x140
>  [<00029828>] parse_args+0x0/0x202
>  [<000020e8>] do_one_initcall+0x0/0x140
>  [<002bf6c4>] strcpy+0x0/0x1c
>  [<00040004>] timekeeping_resume+0x280/0x2cc
>  [<003df1e6>] kernel_init_freeable+0x176/0x190
>  [<002bf6c4>] strcpy+0x0/0x1c
>  [<003df1fc>] kernel_init_freeable+0x18c/0x190
>  [<003f0f02>] genl_init+0x0/0x34
>  [<002c4b66>] kernel_init+0x0/0xd2
>  [<002c4b6e>] kernel_init+0x8/0xd2
>  [<002c4b66>] kernel_init+0x0/0xd2
>  [<000028e0>] ret_from_kernel_thread+0xc/0x14
> ---[ end trace 62c263e59debfdfe ]---
> Kernel panic - not syncing: GENL: Cannot register controller: -22

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Guenter Roeck]

On Fri, Jun 22, 2018 at 02:05:19PM -0700, Matthew Wilcox wrote:
> On Fri, Jun 22, 2018 at 11:42:46AM -0700, Guenter Roeck wrote:
> > Hi,
> > 
> > a few days ago, m68k boot tests in linux-next started to crash.
> > I bisected the problem to commit 'xarray: Replace exceptional entries'.
> > Bisect and crash logs are attached below.
> 
> Thank you!  I was afraid something like this might happen.  
> 
> > ------------[ cut here ]------------
> > WARNING: CPU: 0 PID: 1 at lib/idr.c:42 idr_alloc_u32+0x44/0xe8
> 
> Line 42 is:
> 
>         if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
>                 return -EINVAL;
> 
> The pointer passed in to idr_alloc() is not 4-byte aligned; it's aligned
> to a 2 byte boundary.  I'm having a little trouble seeing who it is that's
> passing in what pointer ...
> 
> > Call Trace: [<000180d6>] __warn+0xc0/0xc2
> >  [<000020e8>] do_one_initcall+0x0/0x140
> >  [<0001816a>] warn_slowpath_null+0x26/0x2c
> >  [<002b50e4>] idr_alloc_u32+0x44/0xe8
> >  [<002b50e4>] idr_alloc_u32+0x44/0xe8
> >  [<002b51e4>] idr_alloc+0x5c/0x76
> >  [<00247160>] genl_register_family+0x14c/0x54c
> 
> It makes sense to here (other than idr_alloc being listed twice)
> 
> >  [<000020e8>] do_one_initcall+0x0/0x140
> >  [<003f0f02>] genl_init+0x0/0x34
> 
> Assuming this is right, that would imply that genl_ctrl is not 4-byte
> aligned.  Is that true?  I'm not familiar with the m68k alignment rules,
> but it has a lot of 4-byte sized quantities in the struct, so I would
> assume it's 4-byte aligned.
> 
> >  [<003f0ce6>] bpf_lwt_init+0x10/0x14
> 
> I don't think this is the caller.
> 

Here is the culprit:

genl_register_family(0x36dd7a) registering VFS_DQUOT
------------[ cut here ]------------
WARNING: CPU: 0 PID: 1 at lib/idr.c:42 idr_alloc_u32+0x44/0xe8

It may be odd that fs/quota/netlink.c:quota_genl_family is not word
aligned, but on the other side I don't think there is a rule that
the function parameter to genl_register_family() - or the second
parameter of idr_alloc() - must be word aligned. Am I missing
something ? After all, it could be a pointer to the nth element
of a string, or the caller could on purpose allocate IDRs for
(ptr), (ptr + 1), and so on.

Thanks,
Guenter

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Matthew Wilcox]

On Fri, Jun 22, 2018 at 03:33:35PM -0700, Guenter Roeck wrote:
> On Fri, Jun 22, 2018 at 02:05:19PM -0700, Matthew Wilcox wrote:
> > On Fri, Jun 22, 2018 at 11:42:46AM -0700, Guenter Roeck wrote:
> > > Hi,
> > > 
> > > a few days ago, m68k boot tests in linux-next started to crash.
> > > I bisected the problem to commit 'xarray: Replace exceptional entries'.
> > > Bisect and crash logs are attached below.
> > 
> > Thank you!  I was afraid something like this might happen.  
> > 
> > > ------------[ cut here ]------------
> > > WARNING: CPU: 0 PID: 1 at lib/idr.c:42 idr_alloc_u32+0x44/0xe8
> > 
> > Line 42 is:
> > 
> >         if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
> >                 return -EINVAL;
> > 
> > The pointer passed in to idr_alloc() is not 4-byte aligned; it's aligned
> > to a 2 byte boundary.  I'm having a little trouble seeing who it is that's
> > passing in what pointer ...
> > 
> > > Call Trace: [<000180d6>] __warn+0xc0/0xc2
> > >  [<000020e8>] do_one_initcall+0x0/0x140
> > >  [<0001816a>] warn_slowpath_null+0x26/0x2c
> > >  [<002b50e4>] idr_alloc_u32+0x44/0xe8
> > >  [<002b50e4>] idr_alloc_u32+0x44/0xe8
> > >  [<002b51e4>] idr_alloc+0x5c/0x76
> > >  [<00247160>] genl_register_family+0x14c/0x54c
> > 
> > It makes sense to here (other than idr_alloc being listed twice)
> > 
> > >  [<000020e8>] do_one_initcall+0x0/0x140
> > >  [<003f0f02>] genl_init+0x0/0x34
> > 
> > Assuming this is right, that would imply that genl_ctrl is not 4-byte
> > aligned.  Is that true?  I'm not familiar with the m68k alignment rules,
> > but it has a lot of 4-byte sized quantities in the struct, so I would
> > assume it's 4-byte aligned.
> > 
> > >  [<003f0ce6>] bpf_lwt_init+0x10/0x14
> > 
> > I don't think this is the caller.
> > 
> 
> Here is the culprit:
> 
> genl_register_family(0x36dd7a) registering VFS_DQUOT
> ------------[ cut here ]------------
> WARNING: CPU: 0 PID: 1 at lib/idr.c:42 idr_alloc_u32+0x44/0xe8
> 
> It may be odd that fs/quota/netlink.c:quota_genl_family is not word
> aligned, but on the other side I don't think there is a rule that
> the function parameter to genl_register_family() - or the second
> parameter of idr_alloc() - must be word aligned. Am I missing
> something ? After all, it could be a pointer to the nth element
> of a string, or the caller could on purpose allocate IDRs for
> (ptr), (ptr + 1), and so on.

There actually is a rule that pointers passed to the IDR be aligned.
It might not be written down anywhere ;-)  And I'm quite happy to lift
that restriction; after all I don't want to force everybody to decorate
definitions with __aligned(4).

I'll see what I can do to fix it.  I'm actually on holiday this week,
so a fix may be delayed.

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Guenter Roeck]

On 06/23/2018 12:46 AM, Matthew Wilcox wrote:

>>
>> Here is the culprit:
>>
>> genl_register_family(0x36dd7a) registering VFS_DQUOT
>> ------------[ cut here ]------------
>> WARNING: CPU: 0 PID: 1 at lib/idr.c:42 idr_alloc_u32+0x44/0xe8
>>
>> It may be odd that fs/quota/netlink.c:quota_genl_family is not word
>> aligned, but on the other side I don't think there is a rule that
>> the function parameter to genl_register_family() - or the second
>> parameter of idr_alloc() - must be word aligned. Am I missing
>> something ? After all, it could be a pointer to the nth element
>> of a string, or the caller could on purpose allocate IDRs for
>> (ptr), (ptr + 1), and so on.
> 
> There actually is a rule that pointers passed to the IDR be aligned.
> It might not be written down anywhere ;-)  And I'm quite happy to lift
> that restriction; after all I don't want to force everybody to decorate
> definitions with __aligned(4).
> 

I am not sure if that is really correct, or at least I was unable to
find such a restriction documented or even mentioned anywhere. It is
true for radix trees, but even there the restriction used to be "even".
This was changed to "word aligned" with commit 3bcadd6fa6c4f, and the
offending commit here moves the "INTERNAL" bit from position 0 to 1.
This is quite a subtle change that was introduced over time. I'd be
not surprised if there are other more severe problems lurking in
the radix tree code and/or its users because of that.

Either case, I think the check for radix_tree_is_internal_node() in
idr_alloc_u32() is wrong. If anything, it should be radix_tree_exception().
If that was the case, the problem (and maybe other similar problems)
would have been found with commit 3bcadd6fa6c4f, not only now.

Guenter

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Geert Uytterhoeven]

Hi all,

On Sat, Jun 23, 2018 at 12:33 AM Guenter Roeck <linux@roeck-us.net> wrote:
> On Fri, Jun 22, 2018 at 02:05:19PM -0700, Matthew Wilcox wrote:
> > On Fri, Jun 22, 2018 at 11:42:46AM -0700, Guenter Roeck wrote:
> > > a few days ago, m68k boot tests in linux-next started to crash.
> > > I bisected the problem to commit 'xarray: Replace exceptional entries'.
> > > Bisect and crash logs are attached below.
> >
> > Thank you!  I was afraid something like this might happen.
> >
> > > ------------[ cut here ]------------
> > > WARNING: CPU: 0 PID: 1 at lib/idr.c:42 idr_alloc_u32+0x44/0xe8
> >
> > Line 42 is:
> >
> >         if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
> >                 return -EINVAL;
> >
> > The pointer passed in to idr_alloc() is not 4-byte aligned; it's aligned
> > to a 2 byte boundary.  I'm having a little trouble seeing who it is that's
> > passing in what pointer ...
> >
> > > Call Trace: [<000180d6>] __warn+0xc0/0xc2
> > >  [<000020e8>] do_one_initcall+0x0/0x140
> > >  [<0001816a>] warn_slowpath_null+0x26/0x2c
> > >  [<002b50e4>] idr_alloc_u32+0x44/0xe8
> > >  [<002b50e4>] idr_alloc_u32+0x44/0xe8
> > >  [<002b51e4>] idr_alloc+0x5c/0x76
> > >  [<00247160>] genl_register_family+0x14c/0x54c
> >
> > It makes sense to here (other than idr_alloc being listed twice)
> >
> > >  [<000020e8>] do_one_initcall+0x0/0x140
> > >  [<003f0f02>] genl_init+0x0/0x34
> >
> > Assuming this is right, that would imply that genl_ctrl is not 4-byte
> > aligned.  Is that true?  I'm not familiar with the m68k alignment rules,
> > but it has a lot of 4-byte sized quantities in the struct, so I would
> > assume it's 4-byte aligned.
> >
> > >  [<003f0ce6>] bpf_lwt_init+0x10/0x14
> >
> > I don't think this is the caller.
> >
>
> Here is the culprit:
>
> genl_register_family(0x36dd7a) registering VFS_DQUOT
> ------------[ cut here ]------------
> WARNING: CPU: 0 PID: 1 at lib/idr.c:42 idr_alloc_u32+0x44/0xe8
>
> It may be odd that fs/quota/netlink.c:quota_genl_family is not word
> aligned, but on the other side I don't think there is a rule that

On m68k (and a few other architectures), the alignment of int and larger
integral types is 2 bytes.

> the function parameter to genl_register_family() - or the second
> parameter of idr_alloc() - must be word aligned. Am I missing
> something ? After all, it could be a pointer to the nth element
> of a string, or the caller could on purpose allocate IDRs for
> (ptr), (ptr + 1), and so on.

Good point.

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: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Matthew Wilcox]

On Sat, Jun 23, 2018 at 09:43:41AM -0700, Guenter Roeck wrote:
> On 06/23/2018 12:46 AM, Matthew Wilcox wrote:
> > There actually is a rule that pointers passed to the IDR be aligned.
> > It might not be written down anywhere ;-)  And I'm quite happy to lift
> > that restriction; after all I don't want to force everybody to decorate
> > definitions with __aligned(4).
> 
> I am not sure if that is really correct, or at least I was unable to
> find such a restriction documented or even mentioned anywhere. It is
> true for radix trees, but even there the restriction used to be "even".
> This was changed to "word aligned" with commit 3bcadd6fa6c4f, and the
> offending commit here moves the "INTERNAL" bit from position 0 to 1.
> This is quite a subtle change that was introduced over time. I'd be
> not surprised if there are other more severe problems lurking in
> the radix tree code and/or its users because of that.
> 
> Either case, I think the check for radix_tree_is_internal_node() in
> idr_alloc_u32() is wrong. If anything, it should be radix_tree_exception().
> If that was the case, the problem (and maybe other similar problems)
> would have been found with commit 3bcadd6fa6c4f, not only now.

Oh, but we want people to be able to store exceptional entries as well
as pointers.  So this was the right solution at the time.  Now that I'm
trying to expand the range of exceptional entries, it's time to make all
(*) values storable in the IDR.

(*) Still not all.  The radix tree/IDR/XArray reserve some values for
its own use.  Various values below 4096 and above -4095, for example.

Here's the test-case I'm currently working on:

+static void idr_align_test(struct idr *idr)
+{
+       char name[] = "Motorola 68000";
+       int i;
+
+       for (i = 0; i < 9; i++)
+               BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i);
+       idr_destroy(idr);
+
+       for (i = 1; i < 10; i++)
+               BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 1);
+       idr_destroy(idr);
+
+       for (i = 2; i < 11; i++)
+               BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 2);
+       idr_destroy(idr);
+
+       for (i = 3; i < 12; i++)
+               BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 3);
+       idr_destroy(idr);
+
+       for (i = 0; i < 8; i++) {
+               BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
+               BUG_ON(idr_alloc(idr, &name[i + 1], 0, 0, GFP_KERNEL) != 1);
+               idr_remove(idr, 1);
+               idr_remove(idr, 0);
+               BUG_ON(!idr_is_empty(idr));
+       }
+}

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Matthew Wilcox]

On Fri, Jun 22, 2018 at 03:33:35PM -0700, Guenter Roeck wrote:
> It may be odd that fs/quota/netlink.c:quota_genl_family is not word
> aligned, but on the other side I don't think there is a rule that
> the function parameter to genl_register_family() - or the second
> parameter of idr_alloc() - must be word aligned. Am I missing
> something ? After all, it could be a pointer to the nth element
> of a string, or the caller could on purpose allocate IDRs for
> (ptr), (ptr + 1), and so on.

This is probably going to cure the problem for you (apply on top
of the existing radix tree / IDR changes).

I realised when I was reviewing the patch that it's no good; if you
call idr_replace() with a radix_tree_is_internal_node(), then you'll
still get a crash.  I'm going to have to disable the optimisation of
shrinking the tree all the way into the head for the IDR.  But this
will probably get m68k working again.

diff --git a/lib/idr.c b/lib/idr.c
index 58b88f5eb672..51ee0c6170d1 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -38,17 +38,24 @@ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
 	void __rcu **slot;
 	unsigned int base = idr->idr_base;
 	unsigned int id = *nextid;
+	bool advanced = false;
 
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
-		return -EINVAL;
 	if (WARN_ON_ONCE(!(idr->idr_rt.xa_flags & ROOT_IS_IDR)))
 		idr->idr_rt.xa_flags |= IDR_RT_MARKER;
 
 	id = (id < base) ? 0 : id - base;
+	if (id == 0 && radix_tree_is_internal_node(ptr) && idr_is_empty(idr)) {
+		advanced = true;
+		id = 1;
+	}
 	radix_tree_iter_init(&iter, id);
 	slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);
 	if (IS_ERR(slot))
 		return PTR_ERR(slot);
+	if (advanced) {
+		iter.index = 0;
+		slot--;
+	}
 
 	*nextid = iter.index + base;
 	/* there is a memory barrier inside radix_tree_iter_replace() */
@@ -295,8 +302,6 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
 	void __rcu **slot = NULL;
 	void *entry;
 
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
-		return ERR_PTR(-EINVAL);
 	id -= idr->idr_base;
 
 	entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 101f1c28e1b6..b0bd105a365d 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -562,11 +562,14 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
 		child = rcu_dereference_raw(node->slots[0]);
 		if (!child)
 			break;
-		if (!radix_tree_is_internal_node(child) && node->shift)
+		if (!radix_tree_is_internal_node(child))
 			break;
 
-		if (radix_tree_is_internal_node(child))
+		if (radix_tree_is_internal_node(child)) {
+			if (!node->shift)
+				break;
 			entry_to_node(child)->parent = NULL;
+		}
 
 		/*
 		 * We don't need rcu_assign_pointer(), since we are simply
@@ -733,7 +736,7 @@ static void radix_tree_free_nodes(struct radix_tree_node *node)
 
 	for (;;) {
 		void *entry = rcu_dereference_raw(child->slots[offset]);
-		if (xa_is_node(entry)) {
+		if (xa_is_node(entry) && child->shift) {
 			child = entry_to_node(entry);
 			offset = 0;
 			continue;
@@ -904,6 +907,8 @@ void *__radix_tree_lookup(const struct radix_tree_root *root,
 		parent = entry_to_node(node);
 		offset = radix_tree_descend(parent, &node, index);
 		slot = parent->slots + offset;
+		if (parent->shift == 0)
+			break;
 	}
 
 	if (nodep)
@@ -977,9 +982,6 @@ static inline void replace_sibling_entries(struct radix_tree_node *node,
 static void replace_slot(void __rcu **slot, void *item,
 		struct radix_tree_node *node, int count, int values)
 {
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(item)))
-		return;
-
 	if (node && (count || values)) {
 		node->count += count;
 		node->nr_values += values;
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 46fc2f1142c3..e494f1d24687 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -227,6 +227,43 @@ void idr_u32_test(int base)
 	idr_u32_test1(&idr, 0xffffffff);
 }
 
+static void idr_align_test(struct idr *idr)
+{
+	char name[] = "Motorola 68000";
+	int i;
+
+	for (i = 0; i < 9; i++)
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i);
+	idr_destroy(idr);
+
+	for (i = 1; i < 10; i++)
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 1);
+	idr_destroy(idr);
+
+	for (i = 2; i < 11; i++)
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 2);
+	idr_destroy(idr);
+
+	for (i = 3; i < 12; i++)
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 3);
+	idr_destroy(idr);
+
+	for (i = 0; i < 8; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
+		BUG_ON(idr_alloc(idr, &name[i + 1], 0, 0, GFP_KERNEL) != 1);
+		idr_remove(idr, 1);
+		idr_remove(idr, 0);
+		BUG_ON(!idr_is_empty(idr));
+	}
+
+	for (i = 0; i < 8; i++) {
+		BUG_ON(idr_alloc(idr, NULL, 0, 0, GFP_KERNEL) != 0);
+		idr_replace(idr, &name[i], 0);
+		BUG_ON(idr_find(idr, 0) != &name[i]);
+		idr_remove(idr, 0);
+	}
+}
+
 void idr_checks(void)
 {
 	unsigned long i;
@@ -307,6 +344,7 @@ void idr_checks(void)
 	idr_u32_test(4);
 	idr_u32_test(1);
 	idr_u32_test(0);
+	idr_align_test(&idr);
 }
 
 /*

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Guenter Roeck]

On 06/23/2018 06:17 PM, Matthew Wilcox wrote:
> On Fri, Jun 22, 2018 at 03:33:35PM -0700, Guenter Roeck wrote:
>> It may be odd that fs/quota/netlink.c:quota_genl_family is not word
>> aligned, but on the other side I don't think there is a rule that
>> the function parameter to genl_register_family() - or the second
>> parameter of idr_alloc() - must be word aligned. Am I missing
>> something ? After all, it could be a pointer to the nth element
>> of a string, or the caller could on purpose allocate IDRs for
>> (ptr), (ptr + 1), and so on.
> 
> This is probably going to cure the problem for you (apply on top
> of the existing radix tree / IDR changes).
> 
> I realised when I was reviewing the patch that it's no good; if you
> call idr_replace() with a radix_tree_is_internal_node(), then you'll
> still get a crash.  I'm going to have to disable the optimisation of
> shrinking the tree all the way into the head for the IDR.  But this
> will probably get m68k working again.
> 

It doesn't crash anymore, but there is still a backtrace.

------------[ cut here ]------------
WARNING: CPU: 0 PID: 1 at lib/idr.c:250 idr_get_next+0x62/0x82
Modules linked in:
CPU: 0 PID: 1 Comm: swapper Not tainted 4.18.0-rc1-next-20180622-mac-00001-g6731a81057be-dirty #1
Stack from 07c19e28:
         07c19e28 0036d5b2 000180d6 00000000 0036e0d6 0055a040 00000000 000020e8
         07c19eb0 002b5326 0001816a 0036d5b5 000000fa 002b5388 00000009 00000000
         00000000 00340b1d 002b5388 0036d5b5 000000fa 00000401 0036e0d6 80000000
         00000000 00036fa0 0036ddc0 07c19eb0 00246164 003abf1c 07c19eb0 00036fa0
         0036e0ce 07c19f8c 00000011 00246f04 0036e0d6 003abf34 00000400 00000006
         0055a040 00000000 000020e8 00000000 00036fa0 003ff8e0 003f751c 07c19f8c
Call Trace: [<000180d6>] __warn+0xc0/0xc2
  [<000020e8>] do_one_initcall+0x0/0x140
  [<002b5326>] idr_get_next+0x0/0x82
  [<0001816a>] warn_slowpath_null+0x26/0x2c
  [<002b5388>] idr_get_next+0x62/0x82
  [<002b5388>] idr_get_next+0x62/0x82
  [<00036fa0>] printk+0x0/0x18
  [<00246164>] genl_family_find_byname+0x1c/0x4c
  [<00036fa0>] printk+0x0/0x18
  [<00246f04>] genl_register_family+0x74/0x55c
  [<000020e8>] do_one_initcall+0x0/0x140

Guenter

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Matthew Wilcox]

On Sat, Jun 23, 2018 at 07:52:35PM -0700, Guenter Roeck wrote:
> On 06/23/2018 06:17 PM, Matthew Wilcox wrote:
> > On Fri, Jun 22, 2018 at 03:33:35PM -0700, Guenter Roeck wrote:
> > > It may be odd that fs/quota/netlink.c:quota_genl_family is not word
> > > aligned, but on the other side I don't think there is a rule that
> > > the function parameter to genl_register_family() - or the second
> > > parameter of idr_alloc() - must be word aligned. Am I missing
> > > something ? After all, it could be a pointer to the nth element
> > > of a string, or the caller could on purpose allocate IDRs for
> > > (ptr), (ptr + 1), and so on.
> > 
> > This is probably going to cure the problem for you (apply on top
> > of the existing radix tree / IDR changes).
> > 
> > I realised when I was reviewing the patch that it's no good; if you
> > call idr_replace() with a radix_tree_is_internal_node(), then you'll
> > still get a crash.  I'm going to have to disable the optimisation of
> > shrinking the tree all the way into the head for the IDR.  But this
> > will probably get m68k working again.
> > 
> 
> It doesn't crash anymore, but there is still a backtrace.

Oof.  Thank you!  Updated patch (still doesn't fix idr_replace, but does
fix the idr_for_each() problem, at least according to the tests I added
to the test-suite.

diff --git a/lib/idr.c b/lib/idr.c
index 58b88f5eb672..51ee0c6170d1 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -38,17 +38,24 @@ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
 	void __rcu **slot;
 	unsigned int base = idr->idr_base;
 	unsigned int id = *nextid;
+	bool advanced = false;
 
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
-		return -EINVAL;
 	if (WARN_ON_ONCE(!(idr->idr_rt.xa_flags & ROOT_IS_IDR)))
 		idr->idr_rt.xa_flags |= IDR_RT_MARKER;
 
 	id = (id < base) ? 0 : id - base;
+	if (id == 0 && radix_tree_is_internal_node(ptr) && idr_is_empty(idr)) {
+		advanced = true;
+		id = 1;
+	}
 	radix_tree_iter_init(&iter, id);
 	slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);
 	if (IS_ERR(slot))
 		return PTR_ERR(slot);
+	if (advanced) {
+		iter.index = 0;
+		slot--;
+	}
 
 	*nextid = iter.index + base;
 	/* there is a memory barrier inside radix_tree_iter_replace() */
@@ -295,8 +302,6 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
 	void __rcu **slot = NULL;
 	void *entry;
 
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
-		return ERR_PTR(-EINVAL);
 	id -= idr->idr_base;
 
 	entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 101f1c28e1b6..15f34de929f5 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -562,11 +562,14 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
 		child = rcu_dereference_raw(node->slots[0]);
 		if (!child)
 			break;
-		if (!radix_tree_is_internal_node(child) && node->shift)
+		if (!radix_tree_is_internal_node(child))
 			break;
 
-		if (radix_tree_is_internal_node(child))
+		if (radix_tree_is_internal_node(child)) {
+			if (!node->shift)
+				break;
 			entry_to_node(child)->parent = NULL;
+		}
 
 		/*
 		 * We don't need rcu_assign_pointer(), since we are simply
@@ -733,7 +736,7 @@ static void radix_tree_free_nodes(struct radix_tree_node *node)
 
 	for (;;) {
 		void *entry = rcu_dereference_raw(child->slots[offset]);
-		if (xa_is_node(entry)) {
+		if (xa_is_node(entry) && child->shift) {
 			child = entry_to_node(entry);
 			offset = 0;
 			continue;
@@ -904,6 +907,8 @@ void *__radix_tree_lookup(const struct radix_tree_root *root,
 		parent = entry_to_node(node);
 		offset = radix_tree_descend(parent, &node, index);
 		slot = parent->slots + offset;
+		if (parent->shift == 0)
+			break;
 	}
 
 	if (nodep)
@@ -977,9 +982,6 @@ static inline void replace_sibling_entries(struct radix_tree_node *node,
 static void replace_slot(void __rcu **slot, void *item,
 		struct radix_tree_node *node, int count, int values)
 {
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(item)))
-		return;
-
 	if (node && (count || values)) {
 		node->count += count;
 		node->nr_values += values;
@@ -1486,7 +1488,7 @@ void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
 			goto restart;
 		if (child == RADIX_TREE_RETRY)
 			break;
-	} while (radix_tree_is_internal_node(child));
+	} while (node->shift && radix_tree_is_internal_node(child));
 
 	/* Update the iterator state */
 	iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 46fc2f1142c3..ec7e8f2fb0ec 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -227,6 +227,56 @@ void idr_u32_test(int base)
 	idr_u32_test1(&idr, 0xffffffff);
 }
 
+static void idr_align_test(struct idr *idr)
+{
+	char name[] = "Motorola 68000";
+	int i, id;
+	void *entry;
+
+	for (i = 0; i < 9; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i);
+		idr_for_each_entry(idr, entry, id);
+	}
+	idr_destroy(idr);
+
+	for (i = 1; i < 10; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 1);
+		idr_for_each_entry(idr, entry, id);
+	}
+	idr_destroy(idr);
+
+	for (i = 2; i < 11; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 2);
+		idr_for_each_entry(idr, entry, id);
+	}
+	idr_destroy(idr);
+
+	for (i = 3; i < 12; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 3);
+		idr_for_each_entry(idr, entry, id);
+	}
+	idr_destroy(idr);
+
+	for (i = 0; i < 8; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
+		BUG_ON(idr_alloc(idr, &name[i + 1], 0, 0, GFP_KERNEL) != 1);
+		idr_for_each_entry(idr, entry, id);
+		idr_remove(idr, 1);
+		idr_for_each_entry(idr, entry, id);
+		idr_remove(idr, 0);
+		BUG_ON(!idr_is_empty(idr));
+	}
+
+	for (i = 0; i < 8; i++) {
+		BUG_ON(idr_alloc(idr, NULL, 0, 0, GFP_KERNEL) != 0);
+		idr_for_each_entry(idr, entry, id);
+		idr_replace(idr, &name[i], 0);
+		idr_for_each_entry(idr, entry, id);
+		BUG_ON(idr_find(idr, 0) != &name[i]);
+		idr_remove(idr, 0);
+	}
+}
+
 void idr_checks(void)
 {
 	unsigned long i;
@@ -307,6 +357,7 @@ void idr_checks(void)
 	idr_u32_test(4);
 	idr_u32_test(1);
 	idr_u32_test(0);
+	idr_align_test(&idr);
 }
 
 /*

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Guenter Roeck]

On 06/23/2018 08:26 PM, Matthew Wilcox wrote:
> On Sat, Jun 23, 2018 at 07:52:35PM -0700, Guenter Roeck wrote:
>> On 06/23/2018 06:17 PM, Matthew Wilcox wrote:
>>> On Fri, Jun 22, 2018 at 03:33:35PM -0700, Guenter Roeck wrote:
>>>> It may be odd that fs/quota/netlink.c:quota_genl_family is not word
>>>> aligned, but on the other side I don't think there is a rule that
>>>> the function parameter to genl_register_family() - or the second
>>>> parameter of idr_alloc() - must be word aligned. Am I missing
>>>> something ? After all, it could be a pointer to the nth element
>>>> of a string, or the caller could on purpose allocate IDRs for
>>>> (ptr), (ptr + 1), and so on.
>>>
>>> This is probably going to cure the problem for you (apply on top
>>> of the existing radix tree / IDR changes).
>>>
>>> I realised when I was reviewing the patch that it's no good; if you
>>> call idr_replace() with a radix_tree_is_internal_node(), then you'll
>>> still get a crash.  I'm going to have to disable the optimisation of
>>> shrinking the tree all the way into the head for the IDR.  But this
>>> will probably get m68k working again.
>>>
>>
>> It doesn't crash anymore, but there is still a backtrace.
> 
> Oof.  Thank you!  Updated patch (still doesn't fix idr_replace, but does
> fix the idr_for_each() problem, at least according to the tests I added
> to the test-suite.
> 

Yes, that is much better:

Build reference: next-20180622-1-g023ad92e94da

Building mcf5208evb:m5208:m5208evb_defconfig:initrd ... running .... passed
Building q800:m68040:mac_defconfig:initrd ... running .... passed
Building q800:m68040:mac_defconfig:rootfs ... running .... passed

Guenter

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Matthew Wilcox]

On Sat, Jun 23, 2018 at 09:01:37PM -0700, Guenter Roeck wrote:
> Yes, that is much better:
> 
> Build reference: next-20180622-1-g023ad92e94da
> 
> Building mcf5208evb:m5208:m5208evb_defconfig:initrd ... running .... passed
> Building q800:m68040:mac_defconfig:initrd ... running .... passed
> Building q800:m68040:mac_defconfig:rootfs ... running .... passed

great!  Here's a version which fixes idr_replace() too.

diff --git a/lib/idr.c b/lib/idr.c
index 58b88f5eb672..f16a95cbc527 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -39,8 +39,6 @@ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
 	unsigned int base = idr->idr_base;
 	unsigned int id = *nextid;
 
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
-		return -EINVAL;
 	if (WARN_ON_ONCE(!(idr->idr_rt.xa_flags & ROOT_IS_IDR)))
 		idr->idr_rt.xa_flags |= IDR_RT_MARKER;
 
@@ -295,8 +293,6 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
 	void __rcu **slot = NULL;
 	void *entry;
 
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
-		return ERR_PTR(-EINVAL);
 	id -= idr->idr_base;
 
 	entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 101f1c28e1b6..22fecea283d8 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -564,6 +564,8 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
 			break;
 		if (!radix_tree_is_internal_node(child) && node->shift)
 			break;
+		if (!node->shift && is_idr(root))
+			break;
 
 		if (radix_tree_is_internal_node(child))
 			entry_to_node(child)->parent = NULL;
@@ -733,7 +735,7 @@ static void radix_tree_free_nodes(struct radix_tree_node *node)
 
 	for (;;) {
 		void *entry = rcu_dereference_raw(child->slots[offset]);
-		if (xa_is_node(entry)) {
+		if (xa_is_node(entry) && child->shift) {
 			child = entry_to_node(entry);
 			offset = 0;
 			continue;
@@ -904,6 +906,8 @@ void *__radix_tree_lookup(const struct radix_tree_root *root,
 		parent = entry_to_node(node);
 		offset = radix_tree_descend(parent, &node, index);
 		slot = parent->slots + offset;
+		if (parent->shift == 0)
+			break;
 	}
 
 	if (nodep)
@@ -977,9 +981,6 @@ static inline void replace_sibling_entries(struct radix_tree_node *node,
 static void replace_slot(void __rcu **slot, void *item,
 		struct radix_tree_node *node, int count, int values)
 {
-	if (WARN_ON_ONCE(radix_tree_is_internal_node(item)))
-		return;
-
 	if (node && (count || values)) {
 		node->count += count;
 		node->nr_values += values;
@@ -1486,7 +1487,7 @@ void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
 			goto restart;
 		if (child == RADIX_TREE_RETRY)
 			break;
-	} while (radix_tree_is_internal_node(child));
+	} while (node->shift && radix_tree_is_internal_node(child));
 
 	/* Update the iterator state */
 	iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
@@ -1789,6 +1790,8 @@ void __rcu **idr_get_free(struct radix_tree_root *root,
 		shift = error;
 		child = rcu_dereference_raw(root->xa_head);
 	}
+	if (start == 0 && shift == 0)
+		shift = RADIX_TREE_MAP_SHIFT;
 
 	while (shift) {
 		shift -= RADIX_TREE_MAP_SHIFT;
diff --git a/lib/xarray.c b/lib/xarray.c
index 8dddad5b237c..f549ee744cc6 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -1719,15 +1719,19 @@ void xa_dump_entry(const void *entry, unsigned long index, unsigned long shift)
 	xa_dump_index(index, shift);
 
 	if (xa_is_node(entry)) {
-		unsigned long i;
-		struct xa_node *node = xa_to_node(entry);
-		xa_dump_node(node);
-		for (i = 0; i < XA_CHUNK_SIZE; i++)
-			xa_dump_entry(node->slots[i],
+		if (shift == 0) {
+			pr_cont("%px\n", entry);
+		} else {
+			unsigned long i;
+			struct xa_node *node = xa_to_node(entry);
+			xa_dump_node(node);
+			for (i = 0; i < XA_CHUNK_SIZE; i++)
+				xa_dump_entry(node->slots[i],
 				      index + (i << node->shift), node->shift);
+		}
 	} else if (xa_is_value(entry))
-		pr_cont("value %ld (0x%lx)\n", xa_to_value(entry),
-							xa_to_value(entry));
+		pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry),
+						xa_to_value(entry), entry);
 	else if (!xa_is_internal(entry))
 		pr_cont("%px\n", entry);
 	else if (xa_is_retry(entry))
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 46fc2f1142c3..67d851d31e26 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -227,6 +227,66 @@ void idr_u32_test(int base)
 	idr_u32_test1(&idr, 0xffffffff);
 }
 
+static void idr_align_test(struct idr *idr)
+{
+	char name[] = "Motorola 68000";
+	int i, id;
+	void *entry;
+
+	for (i = 0; i < 9; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i);
+		idr_for_each_entry(idr, entry, id);
+	}
+	idr_destroy(idr);
+
+	for (i = 1; i < 10; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 1);
+		idr_for_each_entry(idr, entry, id);
+	}
+	idr_destroy(idr);
+
+	for (i = 2; i < 11; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 2);
+		idr_for_each_entry(idr, entry, id);
+	}
+	idr_destroy(idr);
+
+	for (i = 3; i < 12; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 3);
+		idr_for_each_entry(idr, entry, id);
+	}
+	idr_destroy(idr);
+
+	for (i = 0; i < 8; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
+		BUG_ON(idr_alloc(idr, &name[i + 1], 0, 0, GFP_KERNEL) != 1);
+		idr_for_each_entry(idr, entry, id);
+		idr_remove(idr, 1);
+		idr_for_each_entry(idr, entry, id);
+		idr_remove(idr, 0);
+		BUG_ON(!idr_is_empty(idr));
+	}
+
+	for (i = 0; i < 8; i++) {
+		BUG_ON(idr_alloc(idr, NULL, 0, 0, GFP_KERNEL) != 0);
+		idr_for_each_entry(idr, entry, id);
+		idr_replace(idr, &name[i], 0);
+		idr_for_each_entry(idr, entry, id);
+		BUG_ON(idr_find(idr, 0) != &name[i]);
+		idr_remove(idr, 0);
+	}
+
+	for (i = 0; i < 8; i++) {
+		BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
+		BUG_ON(idr_alloc(idr, NULL, 0, 0, GFP_KERNEL) != 1);
+		idr_remove(idr, 1);
+		idr_for_each_entry(idr, entry, id);
+		idr_replace(idr, &name[i + 1], 0);
+		idr_for_each_entry(idr, entry, id);
+		idr_remove(idr, 0);
+	}
+}
+
 void idr_checks(void)
 {
 	unsigned long i;
@@ -307,6 +367,7 @@ void idr_checks(void)
 	idr_u32_test(4);
 	idr_u32_test(1);
 	idr_u32_test(0);
+	idr_align_test(&idr);
 }
 
 /*
@@ -396,6 +457,7 @@ void ida_check_conv(void)
 	}
 	assert(ida_is_empty(&ida));
 
+#if 0
 	radix_tree_cpu_dead(1);
 	for (i = 0; i < 1000000; i++) {
 		int err = ida_get_new(&ida, &id);
@@ -410,6 +472,7 @@ void ida_check_conv(void)
 		assert(id == i);
 	}
 	ida_destroy(&ida);
+#endif
 }
 
 /*

Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'

[Guenter Roeck]

On 06/24/2018 04:39 PM, Matthew Wilcox wrote:
> On Sat, Jun 23, 2018 at 09:01:37PM -0700, Guenter Roeck wrote:
>> Yes, that is much better:
>>
>> Build reference: next-20180622-1-g023ad92e94da
>>
>> Building mcf5208evb:m5208:m5208evb_defconfig:initrd ... running .... passed
>> Building q800:m68040:mac_defconfig:initrd ... running .... passed
>> Building q800:m68040:mac_defconfig:rootfs ... running .... passed
> 
> great!  Here's a version which fixes idr_replace() too.
> 

Still passes:

Build reference: next-20180622-1-g374388bcb967

Building mcf5208evb:m5208:m5208evb_defconfig:initrd ... running .... passed
Building q800:m68040:mac_defconfig:initrd ... running .... passed
Building q800:m68040:mac_defconfig:rootfs ... running .... passed

Guenter