Loading...
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
60static RADIX_TREE(mt_tree, GFP_KERNEL);
61unsigned long page_count = 0;
62
63struct page {
64 unsigned long index;
65};
66
67static 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
76void 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}
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
60static RADIX_TREE(mt_tree, GFP_KERNEL);
61unsigned long page_count = 0;
62
63struct page {
64 unsigned long index;
65};
66
67static 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
76void 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}