1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Regression3
4 * Description:
5 * Helper radix_tree_iter_retry resets next_index to the current index.
6 * In following radix_tree_next_slot current chunk size becomes zero.
7 * This isn't checked and it tries to dereference null pointer in slot.
8 *
9 * Helper radix_tree_iter_resume reset slot to NULL and next_index to index + 1,
10 * for tagger iteraction it also must reset cached tags in iterator to abort
11 * next radix_tree_next_slot and go to slow-path into radix_tree_next_chunk.
12 *
13 * Running:
14 * This test should run to completion immediately. The above bug would
15 * cause it to segfault.
16 *
17 * Upstream commit:
18 * Not yet
19 */
20#include <linux/kernel.h>
21#include <linux/gfp.h>
22#include <linux/slab.h>
23#include <linux/radix-tree.h>
24#include <stdlib.h>
25#include <stdio.h>
26
27#include "regression.h"
28
29void regression3_test(void)
30{
31	RADIX_TREE(root, GFP_KERNEL);
32	void *ptr0 = (void *)4ul;
33	void *ptr = (void *)8ul;
34	struct radix_tree_iter iter;
35	void **slot;
36	bool first;
37
38	printv(1, "running regression test 3 (should take milliseconds)\n");
39
40	radix_tree_insert(&root, 0, ptr0);
41	radix_tree_tag_set(&root, 0, 0);
42
43	first = true;
44	radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
45		printv(2, "tagged %ld %p\n", iter.index, *slot);
46		if (first) {
47			radix_tree_insert(&root, 1, ptr);
48			radix_tree_tag_set(&root, 1, 0);
49			first = false;
50		}
51		if (radix_tree_deref_retry(*slot)) {
52			printv(2, "retry at %ld\n", iter.index);
53			slot = radix_tree_iter_retry(&iter);
54			continue;
55		}
56	}
57	radix_tree_delete(&root, 1);
58
59	first = true;
60	radix_tree_for_each_slot(slot, &root, &iter, 0) {
61		printv(2, "slot %ld %p\n", iter.index, *slot);
62		if (first) {
63			radix_tree_insert(&root, 1, ptr);
64			first = false;
65		}
66		if (radix_tree_deref_retry(*slot)) {
67			printv(2, "retry at %ld\n", iter.index);
68			slot = radix_tree_iter_retry(&iter);
69			continue;
70		}
71	}
72
73	radix_tree_for_each_slot(slot, &root, &iter, 0) {
74		printv(2, "slot %ld %p\n", iter.index, *slot);
75		if (!iter.index) {
76			printv(2, "next at %ld\n", iter.index);
77			slot = radix_tree_iter_resume(slot, &iter);
78		}
79	}
80
81	radix_tree_tag_set(&root, 0, 0);
82	radix_tree_tag_set(&root, 1, 0);
83	radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
84		printv(2, "tagged %ld %p\n", iter.index, *slot);
85		if (!iter.index) {
86			printv(2, "next at %ld\n", iter.index);
87			slot = radix_tree_iter_resume(slot, &iter);
88		}
89	}
90
91	radix_tree_delete(&root, 0);
92	radix_tree_delete(&root, 1);
93
94	printv(1, "regression test 3 passed\n");
95}
96