Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
1366c37e MW |
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" | |
268f42de | 54 | #include "test.h" |
1366c37e | 55 | |
372266ba MW |
56 | #define PAGECACHE_TAG_DIRTY XA_MARK_0 |
57 | #define PAGECACHE_TAG_WRITEBACK XA_MARK_1 | |
58 | #define PAGECACHE_TAG_TOWRITE XA_MARK_2 | |
1366c37e MW |
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 | ||
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 | ||
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 | ||
73bc029b | 84 | printv(1, "running regression test 2 (should take milliseconds)\n"); |
1366c37e MW |
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; | |
372266ba | 95 | tag_tagged_items(&mt_tree, start, end, 1, |
1366c37e MW |
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--) | |
6da0396c | 107 | free(radix_tree_delete(&mt_tree, i)); |
1366c37e MW |
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 */ | |
6da0396c MW |
118 | free(radix_tree_delete(&mt_tree, max_slots)); |
119 | ||
120 | BUG_ON(!radix_tree_empty(&mt_tree)); | |
1366c37e | 121 | |
73bc029b | 122 | printv(1, "regression test 2, done\n"); |
1366c37e | 123 | } |