blob: 5d2fa28cdca35533fda6b59b54c50904d1247470 [file] [log] [blame]
Matthew Wilcox1366c372016-03-17 14:21:45 -07001/*
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
65static RADIX_TREE(mt_tree, GFP_KERNEL);
66unsigned long page_count = 0;
67
68struct page {
69 unsigned long index;
70};
71
72static 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
81void 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}