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