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