1 /* 2 * multiorder.c: Multi-order radix tree entry testing 3 * Copyright (c) 2016 Intel Corporation 4 * Author: Ross Zwisler <ross.zwisler@linux.intel.com> 5 * Author: Matthew Wilcox <matthew.r.wilcox@intel.com> 6 * 7 * This program is free software; you can redistribute it and/or modify it 8 * under the terms and conditions of the GNU General Public License, 9 * version 2, as published by the Free Software Foundation. 10 * 11 * This program is distributed in the hope it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 14 * more details. 15 */ 16 #include <linux/radix-tree.h> 17 #include <linux/slab.h> 18 #include <linux/errno.h> 19 #include <pthread.h> 20 21 #include "test.h" 22 23 void multiorder_iteration(void) 24 { 25 RADIX_TREE(tree, GFP_KERNEL); 26 struct radix_tree_iter iter; 27 void **slot; 28 int i, j, err; 29 30 printv(1, "Multiorder iteration test\n"); 31 32 #define NUM_ENTRIES 11 33 int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128}; 34 int order[NUM_ENTRIES] = {1, 1, 2, 3, 4, 1, 0, 1, 3, 0, 7}; 35 36 for (i = 0; i < NUM_ENTRIES; i++) { 37 err = item_insert_order(&tree, index[i], order[i]); 38 assert(!err); 39 } 40 41 for (j = 0; j < 256; j++) { 42 for (i = 0; i < NUM_ENTRIES; i++) 43 if (j <= (index[i] | ((1 << order[i]) - 1))) 44 break; 45 46 radix_tree_for_each_slot(slot, &tree, &iter, j) { 47 int height = order[i] / RADIX_TREE_MAP_SHIFT; 48 int shift = height * RADIX_TREE_MAP_SHIFT; 49 unsigned long mask = (1UL << order[i]) - 1; 50 struct item *item = *slot; 51 52 assert((iter.index | mask) == (index[i] | mask)); 53 assert(iter.shift == shift); 54 assert(!radix_tree_is_internal_node(item)); 55 assert((item->index | mask) == (index[i] | mask)); 56 assert(item->order == order[i]); 57 i++; 58 } 59 } 60 61 item_kill_tree(&tree); 62 } 63 64 void multiorder_tagged_iteration(void) 65 { 66 RADIX_TREE(tree, GFP_KERNEL); 67 struct radix_tree_iter iter; 68 void **slot; 69 int i, j; 70 71 printv(1, "Multiorder tagged iteration test\n"); 72 73 #define MT_NUM_ENTRIES 9 74 int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128}; 75 int order[MT_NUM_ENTRIES] = {1, 0, 2, 4, 3, 1, 3, 0, 7}; 76 77 #define TAG_ENTRIES 7 78 int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128}; 79 80 for (i = 0; i < MT_NUM_ENTRIES; i++) 81 assert(!item_insert_order(&tree, index[i], order[i])); 82 83 assert(!radix_tree_tagged(&tree, 1)); 84 85 for (i = 0; i < TAG_ENTRIES; i++) 86 assert(radix_tree_tag_set(&tree, tag_index[i], 1)); 87 88 for (j = 0; j < 256; j++) { 89 int k; 90 91 for (i = 0; i < TAG_ENTRIES; i++) { 92 for (k = i; index[k] < tag_index[i]; k++) 93 ; 94 if (j <= (index[k] | ((1 << order[k]) - 1))) 95 break; 96 } 97 98 radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) { 99 unsigned long mask; 100 struct item *item = *slot; 101 for (k = i; index[k] < tag_index[i]; k++) 102 ; 103 mask = (1UL << order[k]) - 1; 104 105 assert((iter.index | mask) == (tag_index[i] | mask)); 106 assert(!radix_tree_is_internal_node(item)); 107 assert((item->index | mask) == (tag_index[i] | mask)); 108 assert(item->order == order[k]); 109 i++; 110 } 111 } 112 113 assert(tag_tagged_items(&tree, 0, ~0UL, TAG_ENTRIES, XA_MARK_1, 114 XA_MARK_2) == TAG_ENTRIES); 115 116 for (j = 0; j < 256; j++) { 117 int mask, k; 118 119 for (i = 0; i < TAG_ENTRIES; i++) { 120 for (k = i; index[k] < tag_index[i]; k++) 121 ; 122 if (j <= (index[k] | ((1 << order[k]) - 1))) 123 break; 124 } 125 126 radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) { 127 struct item *item = *slot; 128 for (k = i; index[k] < tag_index[i]; k++) 129 ; 130 mask = (1 << order[k]) - 1; 131 132 assert((iter.index | mask) == (tag_index[i] | mask)); 133 assert(!radix_tree_is_internal_node(item)); 134 assert((item->index | mask) == (tag_index[i] | mask)); 135 assert(item->order == order[k]); 136 i++; 137 } 138 } 139 140 assert(tag_tagged_items(&tree, 1, ~0UL, MT_NUM_ENTRIES * 2, XA_MARK_1, 141 XA_MARK_0) == TAG_ENTRIES); 142 i = 0; 143 radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) { 144 assert(iter.index == tag_index[i]); 145 i++; 146 } 147 148 item_kill_tree(&tree); 149 } 150 151 bool stop_iteration = false; 152 153 static void *creator_func(void *ptr) 154 { 155 /* 'order' is set up to ensure we have sibling entries */ 156 unsigned int order = RADIX_TREE_MAP_SHIFT - 1; 157 struct radix_tree_root *tree = ptr; 158 int i; 159 160 for (i = 0; i < 10000; i++) { 161 item_insert_order(tree, 0, order); 162 item_delete_rcu(tree, 0); 163 } 164 165 stop_iteration = true; 166 return NULL; 167 } 168 169 static void *iterator_func(void *ptr) 170 { 171 struct radix_tree_root *tree = ptr; 172 struct radix_tree_iter iter; 173 struct item *item; 174 void **slot; 175 176 while (!stop_iteration) { 177 rcu_read_lock(); 178 radix_tree_for_each_slot(slot, tree, &iter, 0) { 179 item = radix_tree_deref_slot(slot); 180 181 if (!item) 182 continue; 183 if (radix_tree_deref_retry(item)) { 184 slot = radix_tree_iter_retry(&iter); 185 continue; 186 } 187 188 item_sanity(item, iter.index); 189 } 190 rcu_read_unlock(); 191 } 192 return NULL; 193 } 194 195 static void multiorder_iteration_race(void) 196 { 197 const int num_threads = sysconf(_SC_NPROCESSORS_ONLN); 198 pthread_t worker_thread[num_threads]; 199 RADIX_TREE(tree, GFP_KERNEL); 200 int i; 201 202 pthread_create(&worker_thread[0], NULL, &creator_func, &tree); 203 for (i = 1; i < num_threads; i++) 204 pthread_create(&worker_thread[i], NULL, &iterator_func, &tree); 205 206 for (i = 0; i < num_threads; i++) 207 pthread_join(worker_thread[i], NULL); 208 209 item_kill_tree(&tree); 210 } 211 212 void multiorder_checks(void) 213 { 214 multiorder_iteration(); 215 multiorder_tagged_iteration(); 216 multiorder_iteration_race(); 217 218 radix_tree_cpu_dead(0); 219 } 220 221 int __weak main(void) 222 { 223 radix_tree_init(); 224 multiorder_checks(); 225 return 0; 226 } 227