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 | |
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 | |
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, index: i, p); |
89 | } |
90 | radix_tree_tag_set(&mt_tree, index: 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, batch: 1, |
96 | PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE); |
97 | |
98 | /* 2. */ |
99 | p = page_alloc(); |
100 | radix_tree_insert(&mt_tree, index: max_slots, p); |
101 | |
102 | /* 3. */ |
103 | radix_tree_tag_clear(&mt_tree, index: 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, results: (void ***)pages, first_index: start, max_items: 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 | |