Skip to content

Commit 66ee620

Browse files
author
Matthew Wilcox
committed
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>
1 parent 3d0186b commit 66ee620

File tree

3 files changed

+78
-10
lines changed

3 files changed

+78
-10
lines changed

‎lib/idr.c

Lines changed: 0 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -39,8 +39,6 @@ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
3939
unsigned int base = idr->idr_base;
4040
unsigned int id = *nextid;
4141

42-
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
43-
return -EINVAL;
4442
if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR)))
4543
idr->idr_rt.gfp_mask |= IDR_RT_MARKER;
4644

@@ -295,8 +293,6 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
295293
void __rcu **slot = NULL;
296294
void *entry;
297295

298-
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
299-
return ERR_PTR(-EINVAL);
300296
id -= idr->idr_base;
301297

302298
entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);

‎lib/radix-tree.c

Lines changed: 15 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -703,6 +703,14 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root,
703703
if (!radix_tree_is_internal_node(child) && node->shift)
704704
break;
705705

706+
/*
707+
* For an IDR, we must not shrink entry 0 into the root in
708+
* case somebody calls idr_replace() with a pointer that
709+
* appears to be an internal entry
710+
*/
711+
if (!node->shift && is_idr(root))
712+
break;
713+
706714
if (radix_tree_is_internal_node(child))
707715
entry_to_node(child)->parent = NULL;
708716

@@ -875,8 +883,8 @@ static void radix_tree_free_nodes(struct radix_tree_node *node)
875883

876884
for (;;) {
877885
void *entry = rcu_dereference_raw(child->slots[offset]);
878-
if (radix_tree_is_internal_node(entry) &&
879-
!is_sibling_entry(child, entry)) {
886+
if (radix_tree_is_internal_node(entry) && child->shift &&
887+
!is_sibling_entry(child, entry)) {
880888
child = entry_to_node(entry);
881889
offset = 0;
882890
continue;
@@ -1049,6 +1057,8 @@ void *__radix_tree_lookup(const struct radix_tree_root *root,
10491057
parent = entry_to_node(node);
10501058
offset = radix_tree_descend(parent, &node, index);
10511059
slot = parent->slots + offset;
1060+
if (parent->shift == 0)
1061+
break;
10521062
}
10531063

10541064
if (nodep)
@@ -1123,9 +1133,6 @@ static inline void replace_sibling_entries(struct radix_tree_node *node,
11231133
static void replace_slot(void __rcu **slot, void *item,
11241134
struct radix_tree_node *node, int count, int exceptional)
11251135
{
1126-
if (WARN_ON_ONCE(radix_tree_is_internal_node(item)))
1127-
return;
1128-
11291136
if (node && (count || exceptional)) {
11301137
node->count += count;
11311138
node->exceptional += exceptional;
@@ -1784,7 +1791,7 @@ void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
17841791
goto restart;
17851792
if (child == RADIX_TREE_RETRY)
17861793
break;
1787-
} while (radix_tree_is_internal_node(child));
1794+
} while (node->shift && radix_tree_is_internal_node(child));
17881795

17891796
/* Update the iterator state */
17901797
iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
@@ -2150,6 +2157,8 @@ void __rcu **idr_get_free(struct radix_tree_root *root,
21502157
shift = error;
21512158
child = rcu_dereference_raw(root->rnode);
21522159
}
2160+
if (start == 0 && shift == 0)
2161+
shift = RADIX_TREE_MAP_SHIFT;
21532162

21542163
while (shift) {
21552164
shift -= RADIX_TREE_MAP_SHIFT;

‎tools/testing/radix-tree/idr-test.c

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -227,6 +227,66 @@ void idr_u32_test(int base)
227227
idr_u32_test1(&idr, 0xffffffff);
228228
}
229229

230+
static void idr_align_test(struct idr *idr)
231+
{
232+
char name[] = "Motorola 68000";
233+
int i, id;
234+
void *entry;
235+
236+
for (i = 0; i < 9; i++) {
237+
BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i);
238+
idr_for_each_entry(idr, entry, id);
239+
}
240+
idr_destroy(idr);
241+
242+
for (i = 1; i < 10; i++) {
243+
BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 1);
244+
idr_for_each_entry(idr, entry, id);
245+
}
246+
idr_destroy(idr);
247+
248+
for (i = 2; i < 11; i++) {
249+
BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 2);
250+
idr_for_each_entry(idr, entry, id);
251+
}
252+
idr_destroy(idr);
253+
254+
for (i = 3; i < 12; i++) {
255+
BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 3);
256+
idr_for_each_entry(idr, entry, id);
257+
}
258+
idr_destroy(idr);
259+
260+
for (i = 0; i < 8; i++) {
261+
BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
262+
BUG_ON(idr_alloc(idr, &name[i + 1], 0, 0, GFP_KERNEL) != 1);
263+
idr_for_each_entry(idr, entry, id);
264+
idr_remove(idr, 1);
265+
idr_for_each_entry(idr, entry, id);
266+
idr_remove(idr, 0);
267+
BUG_ON(!idr_is_empty(idr));
268+
}
269+
270+
for (i = 0; i < 8; i++) {
271+
BUG_ON(idr_alloc(idr, NULL, 0, 0, GFP_KERNEL) != 0);
272+
idr_for_each_entry(idr, entry, id);
273+
idr_replace(idr, &name[i], 0);
274+
idr_for_each_entry(idr, entry, id);
275+
BUG_ON(idr_find(idr, 0) != &name[i]);
276+
idr_remove(idr, 0);
277+
}
278+
279+
for (i = 0; i < 8; i++) {
280+
BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
281+
BUG_ON(idr_alloc(idr, NULL, 0, 0, GFP_KERNEL) != 1);
282+
idr_remove(idr, 1);
283+
idr_for_each_entry(idr, entry, id);
284+
idr_replace(idr, &name[i + 1], 0);
285+
idr_for_each_entry(idr, entry, id);
286+
idr_remove(idr, 0);
287+
}
288+
}
289+
230290
void idr_checks(void)
231291
{
232292
unsigned long i;
@@ -307,6 +367,7 @@ void idr_checks(void)
307367
idr_u32_test(4);
308368
idr_u32_test(1);
309369
idr_u32_test(0);
370+
idr_align_test(&idr);
310371
}
311372

312373
#define module_init(x)
@@ -341,6 +402,7 @@ void ida_check_nomem(void)
341402
*/
342403
void ida_check_conv_user(void)
343404
{
405+
#if 0
344406
DEFINE_IDA(ida);
345407
unsigned long i;
346408

@@ -358,6 +420,7 @@ void ida_check_conv_user(void)
358420
IDA_BUG_ON(&ida, id != i);
359421
}
360422
ida_destroy(&ida);
423+
#endif
361424
}
362425

363426
void ida_check_random(void)

0 commit comments

Comments
 (0)