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 static void multiorder_check(unsigned long index, int order) 24 { 25 unsigned long i; 26 unsigned long min = index & ~((1UL << order) - 1); 27 unsigned long max = min + (1UL << order); 28 void **slot; 29 struct item *item2 = item_create(min, order); 30 RADIX_TREE(tree, GFP_KERNEL); 31 32 printv(2, "Multiorder index %ld, order %d\n", index, order); 33 34 assert(item_insert_order(&tree, index, order) == 0); 35 36 for (i = min; i < max; i++) { 37 struct item *item = item_lookup(&tree, i); 38 assert(item != 0); 39 assert(item->index == index); 40 } 41 for (i = 0; i < min; i++) 42 item_check_absent(&tree, i); 43 for (i = max; i < 2*max; i++) 44 item_check_absent(&tree, i); 45 for (i = min; i < max; i++) 46 assert(radix_tree_insert(&tree, i, item2) == -EEXIST); 47 48 slot = radix_tree_lookup_slot(&tree, index); 49 free(*slot); 50 radix_tree_replace_slot(&tree, slot, item2); 51 for (i = min; i < max; i++) { 52 struct item *item = item_lookup(&tree, i); 53 assert(item != 0); 54 assert(item->index == min); 55 } 56 57 assert(item_delete(&tree, min) != 0); 58 59 for (i = 0; i < 2*max; i++) 60 item_check_absent(&tree, i); 61 } 62 63 void multiorder_iteration(void) 64 { 65 RADIX_TREE(tree, GFP_KERNEL); 66 struct radix_tree_iter iter; 67 void **slot; 68 int i, j, err; 69 70 printv(1, "Multiorder iteration test\n"); 71 72 #define NUM_ENTRIES 11 73 int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128}; 74 int order[NUM_ENTRIES] = {1, 1, 2, 3, 4, 1, 0, 1, 3, 0, 7}; 75 76 for (i = 0; i < NUM_ENTRIES; i++) { 77 err = item_insert_order(&tree, index[i], order[i]); 78 assert(!err); 79 } 80 81 for (j = 0; j < 256; j++) { 82 for (i = 0; i < NUM_ENTRIES; i++) 83 if (j <= (index[i] | ((1 << order[i]) - 1))) 84 break; 85 86 radix_tree_for_each_slot(slot, &tree, &iter, j) { 87 int height = order[i] / RADIX_TREE_MAP_SHIFT; 88 int shift = height * RADIX_TREE_MAP_SHIFT; 89 unsigned long mask = (1UL << order[i]) - 1; 90 struct item *item = *slot; 91 92 assert((iter.index | mask) == (index[i] | mask)); 93 assert(iter.shift == shift); 94 assert(!radix_tree_is_internal_node(item)); 95 assert((item->index | mask) == (index[i] | mask)); 96 assert(item->order == order[i]); 97 i++; 98 } 99 } 100 101 item_kill_tree(&tree); 102 } 103 104 void multiorder_tagged_iteration(void) 105 { 106 RADIX_TREE(tree, GFP_KERNEL); 107 struct radix_tree_iter iter; 108 void **slot; 109 int i, j; 110 111 printv(1, "Multiorder tagged iteration test\n"); 112 113 #define MT_NUM_ENTRIES 9 114 int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128}; 115 int order[MT_NUM_ENTRIES] = {1, 0, 2, 4, 3, 1, 3, 0, 7}; 116 117 #define TAG_ENTRIES 7 118 int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128}; 119 120 for (i = 0; i < MT_NUM_ENTRIES; i++) 121 assert(!item_insert_order(&tree, index[i], order[i])); 122 123 assert(!radix_tree_tagged(&tree, 1)); 124 125 for (i = 0; i < TAG_ENTRIES; i++) 126 assert(radix_tree_tag_set(&tree, tag_index[i], 1)); 127 128 for (j = 0; j < 256; j++) { 129 int k; 130 131 for (i = 0; i < TAG_ENTRIES; i++) { 132 for (k = i; index[k] < tag_index[i]; k++) 133 ; 134 if (j <= (index[k] | ((1 << order[k]) - 1))) 135 break; 136 } 137 138 radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) { 139 unsigned long mask; 140 struct item *item = *slot; 141 for (k = i; index[k] < tag_index[i]; k++) 142 ; 143 mask = (1UL << order[k]) - 1; 144 145 assert((iter.index | mask) == (tag_index[i] | mask)); 146 assert(!radix_tree_is_internal_node(item)); 147 assert((item->index | mask) == (tag_index[i] | mask)); 148 assert(item->order == order[k]); 149 i++; 150 } 151 } 152 153 assert(tag_tagged_items(&tree, 0, ~0UL, TAG_ENTRIES, XA_MARK_1, 154 XA_MARK_2) == TAG_ENTRIES); 155 156 for (j = 0; j < 256; j++) { 157 int mask, k; 158 159 for (i = 0; i < TAG_ENTRIES; i++) { 160 for (k = i; index[k] < tag_index[i]; k++) 161 ; 162 if (j <= (index[k] | ((1 << order[k]) - 1))) 163 break; 164 } 165 166 radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) { 167 struct item *item = *slot; 168 for (k = i; index[k] < tag_index[i]; k++) 169 ; 170 mask = (1 << order[k]) - 1; 171 172 assert((iter.index | mask) == (tag_index[i] | mask)); 173 assert(!radix_tree_is_internal_node(item)); 174 assert((item->index | mask) == (tag_index[i] | mask)); 175 assert(item->order == order[k]); 176 i++; 177 } 178 } 179 180 assert(tag_tagged_items(&tree, 1, ~0UL, MT_NUM_ENTRIES * 2, XA_MARK_1, 181 XA_MARK_0) == TAG_ENTRIES); 182 i = 0; 183 radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) { 184 assert(iter.index == tag_index[i]); 185 i++; 186 } 187 188 item_kill_tree(&tree); 189 } 190 191 bool stop_iteration = false; 192 193 static void *creator_func(void *ptr) 194 { 195 /* 'order' is set up to ensure we have sibling entries */ 196 unsigned int order = RADIX_TREE_MAP_SHIFT - 1; 197 struct radix_tree_root *tree = ptr; 198 int i; 199 200 for (i = 0; i < 10000; i++) { 201 item_insert_order(tree, 0, order); 202 item_delete_rcu(tree, 0); 203 } 204 205 stop_iteration = true; 206 return NULL; 207 } 208 209 static void *iterator_func(void *ptr) 210 { 211 struct radix_tree_root *tree = ptr; 212 struct radix_tree_iter iter; 213 struct item *item; 214 void **slot; 215 216 while (!stop_iteration) { 217 rcu_read_lock(); 218 radix_tree_for_each_slot(slot, tree, &iter, 0) { 219 item = radix_tree_deref_slot(slot); 220 221 if (!item) 222 continue; 223 if (radix_tree_deref_retry(item)) { 224 slot = radix_tree_iter_retry(&iter); 225 continue; 226 } 227 228 item_sanity(item, iter.index); 229 } 230 rcu_read_unlock(); 231 } 232 return NULL; 233 } 234 235 static void multiorder_iteration_race(void) 236 { 237 const int num_threads = sysconf(_SC_NPROCESSORS_ONLN); 238 pthread_t worker_thread[num_threads]; 239 RADIX_TREE(tree, GFP_KERNEL); 240 int i; 241 242 pthread_create(&worker_thread[0], NULL, &creator_func, &tree); 243 for (i = 1; i < num_threads; i++) 244 pthread_create(&worker_thread[i], NULL, &iterator_func, &tree); 245 246 for (i = 0; i < num_threads; i++) 247 pthread_join(worker_thread[i], NULL); 248 249 item_kill_tree(&tree); 250 } 251 252 void multiorder_checks(void) 253 { 254 int i; 255 256 for (i = 0; i < 20; i++) { 257 multiorder_check(200, i); 258 multiorder_check(0, i); 259 multiorder_check((1UL << i) + 1, i); 260 } 261 262 multiorder_iteration(); 263 multiorder_tagged_iteration(); 264 multiorder_iteration_race(); 265 266 radix_tree_cpu_dead(0); 267 } 268 269 int __weak main(void) 270 { 271 radix_tree_init(); 272 multiorder_checks(); 273 return 0; 274 } 275