1 /* 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 #define PAGECACHE_TAG_DIRTY 0 55 #define PAGECACHE_TAG_WRITEBACK 1 56 #define PAGECACHE_TAG_TOWRITE 2 57 58 static RADIX_TREE(mt_tree, GFP_KERNEL); 59 unsigned long page_count = 0; 60 61 struct page { 62 unsigned long index; 63 }; 64 65 static struct page *page_alloc(void) 66 { 67 struct page *p; 68 p = malloc(sizeof(struct page)); 69 p->index = page_count++; 70 71 return p; 72 } 73 74 void regression2_test(void) 75 { 76 int i; 77 struct page *p; 78 int max_slots = RADIX_TREE_MAP_SIZE; 79 unsigned long int start, end; 80 struct page *pages[1]; 81 82 printf("running regression test 2 (should take milliseconds)\n"); 83 /* 0. */ 84 for (i = 0; i <= max_slots - 1; i++) { 85 p = page_alloc(); 86 radix_tree_insert(&mt_tree, i, p); 87 } 88 radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY); 89 90 /* 1. */ 91 start = 0; 92 end = max_slots - 2; 93 radix_tree_range_tag_if_tagged(&mt_tree, &start, end, 1, 94 PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE); 95 96 /* 2. */ 97 p = page_alloc(); 98 radix_tree_insert(&mt_tree, max_slots, p); 99 100 /* 3. */ 101 radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY); 102 103 /* 4. */ 104 for (i = max_slots - 1; i >= 0; i--) 105 radix_tree_delete(&mt_tree, i); 106 107 /* 5. */ 108 // NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot 109 // can return. 110 start = 1; 111 end = max_slots - 2; 112 radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end, 113 PAGECACHE_TAG_TOWRITE); 114 115 /* We remove all the remained nodes */ 116 radix_tree_delete(&mt_tree, max_slots); 117 118 printf("regression test 2, done\n"); 119 } 120