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

[Matthew Wilcox <willy@infradead.org>]

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));
+       }
+}