1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Regression2
4  * Description:
5  * Toshiyuki Okajima describes the following radix-tree bug:
6  *
7  * In the following case, we can get a hangup on
8  *   radix_radix_tree_gang_lookup_tag_slot.
9  *
10  * 0.  The radix tree contains RADIX_TREE_MAP_SIZE items. And the tag of
11  *     a certain item has PAGECACHE_TAG_DIRTY.
12  * 1.  radix_tree_range_tag_if_tagged(, start, end, , PAGECACHE_TAG_DIRTY,
13  *     PAGECACHE_TAG_TOWRITE) is called to add PAGECACHE_TAG_TOWRITE tag
14  *     for the tag which has PAGECACHE_TAG_DIRTY. However, there is no tag with
15  *     PAGECACHE_TAG_DIRTY within the range from start to end. As the result,
16  *     There is no tag with PAGECACHE_TAG_TOWRITE but the root tag has
17  *     PAGECACHE_TAG_TOWRITE.
18  * 2.  An item is added into the radix tree and then the level of it is
19  *     extended into 2 from 1. At that time, the new radix tree node succeeds
20  *     the tag status of the root tag. Therefore the tag of the new radix tree
21  *     node has PAGECACHE_TAG_TOWRITE but there is not slot with
22  *     PAGECACHE_TAG_TOWRITE tag in the child node of the new radix tree node.
23  * 3.  The tag of a certain item is cleared with PAGECACHE_TAG_DIRTY.
24  * 4.  All items within the index range from 0 to RADIX_TREE_MAP_SIZE - 1 are
25  *     released. (Only the item which index is RADIX_TREE_MAP_SIZE exist in the
26  *     radix tree.) As the result, the slot of the radix tree node is NULL but
27  *     the tag which corresponds to the slot has PAGECACHE_TAG_TOWRITE.
28  * 5.  radix_tree_gang_lookup_tag_slot(PAGECACHE_TAG_TOWRITE) calls
29  *     __lookup_tag. __lookup_tag returns with 0. And __lookup_tag doesn't
30  *     change the index that is the input and output parameter. Because the 1st
31  *     slot of the radix tree node is NULL, but the tag which corresponds to
32  *     the slot has PAGECACHE_TAG_TOWRITE.
33  *     Therefore radix_tree_gang_lookup_tag_slot tries to get some items by
34  *     calling __lookup_tag, but it cannot get any items forever.
35  *
36  * The fix is to change that radix_tree_tag_if_tagged doesn't tag the root tag
37  * if it doesn't set any tags within the specified range.
38  *
39  * Running:
40  * This test should run to completion immediately. The above bug would cause it
41  * to hang indefinitely.
42  *
43  * Upstream commit:
44  * Not yet
45  */
46 #include <linux/kernel.h>
47 #include <linux/gfp.h>
48 #include <linux/slab.h>
49 #include <linux/radix-tree.h>
50 #include <stdlib.h>
51 #include <stdio.h>
52 
53 #include "regression.h"
54 #include "test.h"
55 
56 #define PAGECACHE_TAG_DIRTY     XA_MARK_0
57 #define PAGECACHE_TAG_WRITEBACK XA_MARK_1
58 #define PAGECACHE_TAG_TOWRITE   XA_MARK_2
59 
60 static RADIX_TREE(mt_tree, GFP_KERNEL);
61 unsigned long page_count = 0;
62 
63 struct page {
64 	unsigned long index;
65 };
66 
page_alloc(void)67 static struct page *page_alloc(void)
68 {
69 	struct page *p;
70 	p = malloc(sizeof(struct page));
71 	p->index = page_count++;
72 
73 	return p;
74 }
75 
regression2_test(void)76 void regression2_test(void)
77 {
78 	int i;
79 	struct page *p;
80 	int max_slots = RADIX_TREE_MAP_SIZE;
81 	unsigned long int start, end;
82 	struct page *pages[1];
83 
84 	printv(1, "running regression test 2 (should take milliseconds)\n");
85 	/* 0. */
86 	for (i = 0; i <= max_slots - 1; i++) {
87 		p = page_alloc();
88 		radix_tree_insert(&mt_tree, i, p);
89 	}
90 	radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
91 
92 	/* 1. */
93 	start = 0;
94 	end = max_slots - 2;
95 	tag_tagged_items(&mt_tree, start, end, 1,
96 				PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE);
97 
98 	/* 2. */
99 	p = page_alloc();
100 	radix_tree_insert(&mt_tree, max_slots, p);
101 
102 	/* 3. */
103 	radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
104 
105 	/* 4. */
106 	for (i = max_slots - 1; i >= 0; i--)
107 		free(radix_tree_delete(&mt_tree, i));
108 
109 	/* 5. */
110 	// NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot
111 	//       can return.
112 	start = 1;
113 	end = max_slots - 2;
114 	radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end,
115 		PAGECACHE_TAG_TOWRITE);
116 
117 	/* We remove all the remained nodes */
118 	free(radix_tree_delete(&mt_tree, max_slots));
119 
120 	BUG_ON(!radix_tree_empty(&mt_tree));
121 
122 	printv(1, "regression test 2, done\n");
123 }
124