summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMatthew Wilcox <willy@infradead.org>2018-06-25 06:56:50 -0400
committerMatthew Wilcox <willy@infradead.org>2018-09-29 22:47:48 -0400
commit66ee620f06f99d72475db6eb638559ba608c7dee (patch)
tree6014376eae1f939a364350975337301cfb10dbb5
parent3d0186bb068e6cc6c23dc1d2f0b1cf64894c40ea (diff)
downloadlinux-66ee620f06f99d72475db6eb638559ba608c7dee.tar.gz
linux-66ee620f06f99d72475db6eb638559ba608c7dee.tar.bz2
linux-66ee620f06f99d72475db6eb638559ba608c7dee.zip
idr: Permit any valid kernel pointer to be stored
An upcoming change to the encoding of internal entries will set the bottom two bits to 0b10. Unfortunately, m68k only aligns some data structures to 2 bytes, so the IDR will interpret them as internal entries and things will go badly wrong. Change the radix tree so that it stops either when the node indicates that it's the bottom of the tree (shift == 0) or when the entry is not an internal entry. This means we cannot insert an arbitrary kernel pointer as a multiorder entry, but the IDR does not permit multiorder entries. Annoyingly, this means the IDR can no longer take advantage of the radix tree's ability to store a single entry at offset 0 without allocating memory. A pointer which is 2-byte aligned cannot be stored directly in the root as it would be indistinguishable from a node, so we must allocate a node in order to store a 2-byte pointer at index 0. The idr_replace() function does not take a GFP flags argument, so cannot allocate memory. If a user inserts a 4-byte aligned pointer at index 0 and then replaces it with a 2-byte aligned pointer, we must be able to store it. Arbitrary pointer values are still not permitted; pointers of the form 2 + (i * 4) for values of i between 0 and 1023 are reserved for the implementation. These are not valid kernel pointers as they would point into the zero page. This change does cause a runtime memory consumption regression for the IDA. I will recover that later. Signed-off-by: Matthew Wilcox <willy@infradead.org> Tested-by: Guenter Roeck <linux@roeck-us.net>
-rw-r--r--lib/idr.c4
-rw-r--r--lib/radix-tree.c21
-rw-r--r--tools/testing/radix-tree/idr-test.c63
3 files changed, 78 insertions, 10 deletions
diff --git a/lib/idr.c b/lib/idr.c
index fab2fd5bc326..729e381e23b4 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.gfp_mask & ROOT_IS_IDR)))
idr->idr_rt.gfp_mask |= 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 bc03ecc4dfd2..a904a8ddd174 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -703,6 +703,14 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root,
if (!radix_tree_is_internal_node(child) && node->shift)
break;
+ /*
+ * For an IDR, we must not shrink entry 0 into the root in
+ * case somebody calls idr_replace() with a pointer that
+ * appears to be an internal entry
+ */
+ if (!node->shift && is_idr(root))
+ break;
+
if (radix_tree_is_internal_node(child))
entry_to_node(child)->parent = NULL;
@@ -875,8 +883,8 @@ static void radix_tree_free_nodes(struct radix_tree_node *node)
for (;;) {
void *entry = rcu_dereference_raw(child->slots[offset]);
- if (radix_tree_is_internal_node(entry) &&
- !is_sibling_entry(child, entry)) {
+ if (radix_tree_is_internal_node(entry) && child->shift &&
+ !is_sibling_entry(child, entry)) {
child = entry_to_node(entry);
offset = 0;
continue;
@@ -1049,6 +1057,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)
@@ -1123,9 +1133,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 exceptional)
{
- if (WARN_ON_ONCE(radix_tree_is_internal_node(item)))
- return;
-
if (node && (count || exceptional)) {
node->count += count;
node->exceptional += exceptional;
@@ -1784,7 +1791,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);
@@ -2150,6 +2157,8 @@ void __rcu **idr_get_free(struct radix_tree_root *root,
shift = error;
child = rcu_dereference_raw(root->rnode);
}
+ if (start == 0 && shift == 0)
+ shift = RADIX_TREE_MAP_SHIFT;
while (shift) {
shift -= RADIX_TREE_MAP_SHIFT;
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 321ba92c70d2..f620c831a4b5 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);
}
#define module_init(x)
@@ -341,6 +402,7 @@ void ida_check_nomem(void)
*/
void ida_check_conv_user(void)
{
+#if 0
DEFINE_IDA(ida);
unsigned long i;
@@ -358,6 +420,7 @@ void ida_check_conv_user(void)
IDA_BUG_ON(&ida, id != i);
}
ida_destroy(&ida);
+#endif
}
void ida_check_random(void)