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);
}
/*
--
To unsubscribe from this list: send the line "unsubscribe linux-m68k" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
