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, 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 } 124