Re: m68k boot failure in -next bisected to 'xarray: Replace exceptional entries'
From: Matthew Wilcox
Date: Sun Jun 24 2018 - 19:40:01 EST
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
}
/*