Lines Matching refs:mas
66 static int get_alloc_node_count(struct ma_state *mas) in get_alloc_node_count() argument
69 struct maple_alloc *node = mas->alloc; in get_alloc_node_count()
80 static void check_mas_alloc_node_count(struct ma_state *mas) in check_mas_alloc_node_count() argument
82 mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 1, GFP_KERNEL); in check_mas_alloc_node_count()
83 mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 3, GFP_KERNEL); in check_mas_alloc_node_count()
84 MT_BUG_ON(mas->tree, get_alloc_node_count(mas) != mas->alloc->total); in check_mas_alloc_node_count()
85 mas_destroy(mas); in check_mas_alloc_node_count()
100 MA_STATE(mas, mt, 0, 0); in check_new_node()
102 check_mas_alloc_node_count(&mas); in check_new_node()
108 mas_node_count(&mas, 3); in check_new_node()
110 MT_BUG_ON(mt, mas_alloc_req(&mas) != 3); in check_new_node()
112 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM)); in check_new_node()
113 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
115 MT_BUG_ON(mt, mas_allocated(&mas) != 3); in check_new_node()
116 mn = mas_pop_node(&mas); in check_new_node()
119 MT_BUG_ON(mt, mas.alloc == NULL); in check_new_node()
120 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL); in check_new_node()
121 mas_push_node(&mas, mn); in check_new_node()
122 mas_reset(&mas); in check_new_node()
123 mas_destroy(&mas); in check_new_node()
130 mas_set_alloc_req(&mas, 1); in check_new_node()
132 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1); in check_new_node()
133 mas_set_err(&mas, -ENOMEM); in check_new_node()
135 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
137 mn = mas_pop_node(&mas); in check_new_node()
142 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
146 mas.status = ma_start; in check_new_node()
147 mas_destroy(&mas); in check_new_node()
149 mas_node_count(&mas, 3); in check_new_node()
151 mas_nomem(&mas, GFP_KERNEL); in check_new_node()
153 MT_BUG_ON(mt, mas_allocated(&mas) != 3); in check_new_node()
155 MT_BUG_ON(mt, mas_alloc_req(&mas) != 0); in check_new_node()
157 MT_BUG_ON(mt, mas.alloc == NULL); in check_new_node()
158 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL); in check_new_node()
159 MT_BUG_ON(mt, mas.alloc->slot[1] == NULL); in check_new_node()
161 MT_BUG_ON(mt, mas_allocated(&mas) != 3); in check_new_node()
163 mas_reset(&mas); in check_new_node()
164 mas_destroy(&mas); in check_new_node()
167 mas_set_alloc_req(&mas, 1); in check_new_node()
168 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1); in check_new_node()
169 mas_set_err(&mas, -ENOMEM); in check_new_node()
171 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
172 MT_BUG_ON(mt, mas_allocated(&mas) != 1); in check_new_node()
174 mn = mas_pop_node(&mas); in check_new_node()
176 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
180 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
181 mas_push_node(&mas, mn); in check_new_node()
182 MT_BUG_ON(mt, mas_allocated(&mas) != 1); in check_new_node()
183 MT_BUG_ON(mt, mas.alloc->node_count); in check_new_node()
185 mas_set_alloc_req(&mas, 2); /* request 2 more. */ in check_new_node()
186 MT_BUG_ON(mt, mas_alloc_req(&mas) != 2); in check_new_node()
187 mas_set_err(&mas, -ENOMEM); in check_new_node()
188 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
189 MT_BUG_ON(mt, mas_allocated(&mas) != 3); in check_new_node()
190 MT_BUG_ON(mt, mas.alloc == NULL); in check_new_node()
191 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL); in check_new_node()
192 MT_BUG_ON(mt, mas.alloc->slot[1] == NULL); in check_new_node()
194 mn = mas_pop_node(&mas); in check_new_node()
195 MT_BUG_ON(mt, mas_allocated(&mas) != i); in check_new_node()
203 mas_set_alloc_req(&mas, total); /* request 2 more. */ in check_new_node()
204 MT_BUG_ON(mt, mas_alloc_req(&mas) != total); in check_new_node()
205 mas_set_err(&mas, -ENOMEM); in check_new_node()
206 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
226 MT_BUG_ON(mt, mas.alloc->node_count != e); in check_new_node()
227 mn = mas_pop_node(&mas); in check_new_node()
229 MT_BUG_ON(mt, mas_allocated(&mas) != i - 1); in check_new_node()
237 mas_set_alloc_req(&mas, i); in check_new_node()
238 mas_set_err(&mas, -ENOMEM); in check_new_node()
239 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
241 mn = mas_pop_node(&mas); in check_new_node()
242 MT_BUG_ON(mt, mas_allocated(&mas) != j - 1); in check_new_node()
245 mas_push_node(&mas, mn); in check_new_node()
246 MT_BUG_ON(mt, mas_allocated(&mas) != j); in check_new_node()
247 mn = mas_pop_node(&mas); in check_new_node()
249 MT_BUG_ON(mt, mas_allocated(&mas) != j - 1); in check_new_node()
253 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
255 mas_set_alloc_req(&mas, i); in check_new_node()
256 mas_set_err(&mas, -ENOMEM); in check_new_node()
257 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
259 MT_BUG_ON(mt, mas_allocated(&mas) != i - j); in check_new_node()
260 nodes[j] = mas_pop_node(&mas); in check_new_node()
261 MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1); in check_new_node()
266 mas_push_node(&mas, nodes[j]); in check_new_node()
267 MT_BUG_ON(mt, mas_allocated(&mas) != i - j); in check_new_node()
269 MT_BUG_ON(mt, mas_allocated(&mas) != i); in check_new_node()
271 MT_BUG_ON(mt, mas_allocated(&mas) != i - j); in check_new_node()
272 mn = mas_pop_node(&mas); in check_new_node()
276 MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1); in check_new_node()
278 mas_reset(&mas); in check_new_node()
279 MT_BUG_ON(mt, mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
280 mas_destroy(&mas); in check_new_node()
286 mas_node_count(&mas, total); in check_new_node()
288 mas_nomem(&mas, GFP_KERNEL); in check_new_node()
289 MT_BUG_ON(mt, !mas.alloc); in check_new_node()
291 smn = mas.alloc; in check_new_node()
301 MT_BUG_ON(mt, mas_allocated(&mas) != total); in check_new_node()
302 mas_reset(&mas); in check_new_node()
303 mas_destroy(&mas); /* Free. */ in check_new_node()
305 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
307 mas_node_count(&mas, i); /* Request */ in check_new_node()
308 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
309 MT_BUG_ON(mt, mas_allocated(&mas) != i); /* check request filled */ in check_new_node()
311 mn = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
317 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
322 mas_node_count(&mas, i); /* Request */ in check_new_node()
323 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
324 MT_BUG_ON(mt, mas_allocated(&mas) != i); /* check request filled */ in check_new_node()
326 mn = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
332 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
347 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
348 mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */ in check_new_node()
349 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM)); in check_new_node()
350 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
351 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1); in check_new_node()
352 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS); in check_new_node()
354 mn = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
357 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS); in check_new_node()
358 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS - 1); in check_new_node()
360 mas_push_node(&mas, mn); in check_new_node()
361 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1); in check_new_node()
362 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS); in check_new_node()
365 mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 2); /* Request */ in check_new_node()
366 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1); in check_new_node()
367 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM)); in check_new_node()
368 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); in check_new_node()
369 MT_BUG_ON(mt, mas_alloc_req(&mas)); in check_new_node()
370 MT_BUG_ON(mt, mas.alloc->node_count != 1); in check_new_node()
371 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2); in check_new_node()
372 mn = mas_pop_node(&mas); in check_new_node()
374 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1); in check_new_node()
375 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS); in check_new_node()
376 mas_push_node(&mas, mn); in check_new_node()
377 MT_BUG_ON(mt, mas.alloc->node_count != 1); in check_new_node()
378 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2); in check_new_node()
379 mn = mas_pop_node(&mas); in check_new_node()
384 mn = mas_pop_node(&mas); in check_new_node()
389 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_new_node()
393 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
394 mas_node_count(&mas, i); /* Request */ in check_new_node()
395 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
396 mn = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
397 mas_push_node(&mas, mn); /* put it back */ in check_new_node()
398 mas_destroy(&mas); in check_new_node()
400 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
401 mas_node_count(&mas, i); /* Request */ in check_new_node()
402 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
403 mn = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
404 mn2 = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
405 mas_push_node(&mas, mn); /* put them back */ in check_new_node()
406 mas_push_node(&mas, mn2); in check_new_node()
407 mas_destroy(&mas); in check_new_node()
409 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
410 mas_node_count(&mas, i); /* Request */ in check_new_node()
411 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
412 mn = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
413 mn2 = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
414 mn3 = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
415 mas_push_node(&mas, mn); /* put them back */ in check_new_node()
416 mas_push_node(&mas, mn2); in check_new_node()
417 mas_push_node(&mas, mn3); in check_new_node()
418 mas_destroy(&mas); in check_new_node()
420 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
421 mas_node_count(&mas, i); /* Request */ in check_new_node()
422 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
423 mn = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
426 mas_destroy(&mas); in check_new_node()
428 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
429 mas_node_count(&mas, i); /* Request */ in check_new_node()
430 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
431 mn = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
434 mn = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
437 mn = mas_pop_node(&mas); /* get the next node. */ in check_new_node()
440 mas_destroy(&mas); in check_new_node()
443 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
444 mas_node_count(&mas, 5); /* Request */ in check_new_node()
445 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
446 MT_BUG_ON(mt, mas_allocated(&mas) != 5); in check_new_node()
447 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
448 mas_node_count(&mas, 10); /* Request */ in check_new_node()
449 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
450 mas.status = ma_start; in check_new_node()
451 MT_BUG_ON(mt, mas_allocated(&mas) != 10); in check_new_node()
452 mas_destroy(&mas); in check_new_node()
454 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
455 mas_node_count(&mas, MAPLE_ALLOC_SLOTS - 1); /* Request */ in check_new_node()
456 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
457 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS - 1); in check_new_node()
458 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
459 mas_node_count(&mas, 10 + MAPLE_ALLOC_SLOTS - 1); /* Request */ in check_new_node()
460 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
461 mas.status = ma_start; in check_new_node()
462 MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1); in check_new_node()
463 mas_destroy(&mas); in check_new_node()
822 static inline void mas_node_walk(struct ma_state *mas, struct maple_node *node, in mas_node_walk() argument
834 (*range_max) = (*range_min) = mas->index; in mas_node_walk()
838 mas->offset = mas->index = mas->min; in mas_node_walk()
848 prev = mas->min; in mas_node_walk()
849 index = mas->index; in mas_node_walk()
868 max = mas->max; in mas_node_walk()
872 mas->offset = offset; in mas_node_walk()
877 mas->max = max; in mas_node_walk()
878 mas->min = prev; in mas_node_walk()
894 static inline bool mas_descend_walk(struct ma_state *mas, in mas_descend_walk() argument
901 next = mas->node; in mas_descend_walk()
905 mas_node_walk(mas, node, type, range_min, range_max); in mas_descend_walk()
906 next = mas_slot(mas, ma_slots(node, type), mas->offset); in mas_descend_walk()
914 mas->node = next; in mas_descend_walk()
929 static inline bool mas_tree_walk(struct ma_state *mas, unsigned long *range_min, in mas_tree_walk() argument
936 mas_start(mas); in mas_tree_walk()
937 if (mas_is_none(mas)) in mas_tree_walk()
940 if (mas_is_ptr(mas)) { in mas_tree_walk()
942 if (!mas->index) in mas_tree_walk()
948 ret = mas_descend_walk(mas, range_min, range_max); in mas_tree_walk()
949 if (unlikely(mte_dead_node(mas->node))) { in mas_tree_walk()
950 mas->status = ma_start; in mas_tree_walk()
954 mas->end = mas_data_end(mas); in mas_tree_walk()
958 mas->offset = MAPLE_NODE_SLOTS; in mas_tree_walk()
962 static inline void *mas_range_load(struct ma_state *mas, in mas_range_load() argument
967 unsigned long index = mas->index; in mas_range_load()
969 if (mas_is_none(mas) || mas_is_paused(mas)) in mas_range_load()
970 mas->status = ma_start; in mas_range_load()
972 if (mas_tree_walk(mas, range_min, range_max)) in mas_range_load()
973 if (unlikely(mas->status == ma_root)) in mas_range_load()
974 return mas_root(mas); in mas_range_load()
976 if (likely(mas->offset != MAPLE_NODE_SLOTS)) in mas_range_load()
977 entry = mas_get_slot(mas, mas->offset); in mas_range_load()
979 if (mas_is_active(mas) && mte_dead_node(mas->node)) { in mas_range_load()
980 mas_set(mas, index); in mas_range_load()
997 MA_STATE(mas, mt, 0, 0); in check_erase2_testset()
1098 mas_reset(&mas); in check_erase2_testset()
1099 mas.index = 0; in check_erase2_testset()
1101 mas_for_each(&mas, foo, ULONG_MAX) { in check_erase2_testset()
1103 if (addr == mas.index) { in check_erase2_testset()
1104 mt_dump(mas.tree, mt_dump_hex); in check_erase2_testset()
1106 mas.index, mas.last); in check_erase2_testset()
1109 addr = mas.index; in check_erase2_testset()
1113 pr_err("mas: %lu -> %p\n", mas.index, foo); in check_erase2_testset()
1127 MT_BUG_ON(mt, mtree_load(mas.tree, 0) != NULL); in check_erase2_testset()
33905 MA_STATE(mas, mt, 0, 0); in check_erase2_sets()
33927 mas_for_each(&mas, entry, ULONG_MAX) { in check_erase2_sets()
33967 mas_reset(&mas); in check_erase2_sets()
33971 mas_empty_area_rev(&mas, 12288, 140014592737280, 0x2000); in check_erase2_sets()
33972 MT_BUG_ON(mt, mas.last != 140014592573439); in check_erase2_sets()
33975 mas_reset(&mas); in check_erase2_sets()
33976 mas.tree = mt; in check_erase2_sets()
33978 mas.index = 0; in check_erase2_sets()
33982 mas_for_each(&mas, entry, ULONG_MAX) { in check_erase2_sets()
33990 mas_reset(&mas); in check_erase2_sets()
33995 mas_empty_area_rev(&mas, 0, 140373518663680, 4096); in check_erase2_sets()
34010 mas_reset(&mas); in check_erase2_sets()
34014 mas_empty_area_rev(&mas, 4096, 139921865637888, 0x6000); in check_erase2_sets()
34015 MT_BUG_ON(mt, mas.last != 139921865547775); in check_erase2_sets()
34025 mas_reset(&mas); in check_erase2_sets()
34029 mas_empty_area_rev(&mas, 4096, 139953197334528, 0x1000); in check_erase2_sets()
34030 MT_BUG_ON(mt, mas.last != 139953197322239); in check_erase2_sets()
34041 mas_reset(&mas); in check_erase2_sets()
34045 mas_empty_area_rev(&mas, 4096, 140222972858368, 2215936); in check_erase2_sets()
34046 MT_BUG_ON(mt, mas.last != 140222968475647); in check_erase2_sets()
34059 mas_reset(&mas); in check_erase2_sets()
34063 mas.index = 140656779083776; in check_erase2_sets()
34064 entry = mas_find(&mas, ULONG_MAX); in check_erase2_sets()
34066 entry = mas_prev(&mas, 0); in check_erase2_sets()
34128 mas_reset(&mas); in check_erase2_sets()
34132 mas_empty_area_rev(&mas, 4096, 140109042671616, 409600); in check_erase2_sets()
34133 MT_BUG_ON(mt, mas.last != 140109040959487); in check_erase2_sets()
34140 mas_reset(&mas); in check_erase2_sets()
34150 mas_reset(&mas); in check_erase2_sets()
34154 mas_empty_area_rev(&mas, 4096, 139918413357056, 2097152); in check_erase2_sets()
34156 mas.index = (mas.last + 1 - 2097152 - 0) & (~2093056); in check_erase2_sets()
34157 MT_BUG_ON(mt, mas.index != 139918401601536); in check_erase2_sets()
34166 mas_reset(&mas); in check_erase2_sets()
34179 mas_reset(&mas); in check_erase2_sets()
34192 mas_reset(&mas); in check_erase2_sets()
34201 mas_reset(&mas); in check_erase2_sets()
34221 mas_reset(&mas); in check_erase2_sets()
34225 mas_empty_area_rev(&mas, 4096, 140583656296448, 134217728); in check_erase2_sets()
34226 MT_BUG_ON(mt, mas.last != 140583003750399); in check_erase2_sets()
34236 mas_reset(&mas); in check_erase2_sets()
34246 mas_reset(&mas); in check_erase2_sets()
34256 mas_reset(&mas); in check_erase2_sets()
34264 mas_reset(&mas); in check_erase2_sets()
34272 mas_reset(&mas); in check_erase2_sets()
34280 mas_reset(&mas); in check_erase2_sets()
34287 mas_reset(&mas); in check_erase2_sets()
34294 mas_reset(&mas); in check_erase2_sets()
34303 mas_reset(&mas); in check_erase2_sets()
34307 mas_empty_area_rev(&mas, 4096, 4052029440, 28672); in check_erase2_sets()
34308 MT_BUG_ON(mt, mas.last != 4041211903); in check_erase2_sets()
34315 mas_reset(&mas); in check_erase2_sets()
34360 MA_STATE(mas, test->mt, 0, 0); in rcu_reader_fwd()
34369 mas_set(&mas, test->index[index]); in rcu_reader_fwd()
34370 mas_for_each(&mas, entry, test->last[index + 9]) { in rcu_reader_fwd()
34382 if (mas.index == alt_start) { in rcu_reader_fwd()
34397 if (mas.index == r_start) { in rcu_reader_fwd()
34400 } else if (mas.index == alt_start) { in rcu_reader_fwd()
34408 RCU_MT_BUG_ON(test, mas.index != r_start); in rcu_reader_fwd()
34409 RCU_MT_BUG_ON(test, mas.last != r_end); in rcu_reader_fwd()
34425 printk("!!%lu-%lu -> %p not %p or %p\n", mas.index, mas.last, entry, expected, alt); in rcu_reader_fwd()
34448 printk("!!%lu-%lu -> %p not %p\n", mas.index, mas.last, entry, expected); in rcu_reader_fwd()
34470 MA_STATE(mas, test->mt, 0, 0); in rcu_reader_rev()
34480 mas_set(&mas, test->index[index + i]); in rcu_reader_rev()
34488 entry = mas_prev(&mas, test->index[index]); in rcu_reader_rev()
34495 if (mas.index == alt_start) { in rcu_reader_rev()
34511 if (mas.index == r_start) { in rcu_reader_rev()
34515 } else if (mas.index == alt_start) { in rcu_reader_rev()
34529 if (mas.index != r_start) { in rcu_reader_rev()
34534 mas.index, mas.last, entry, in rcu_reader_rev()
34538 RCU_MT_BUG_ON(test, mas.index != r_start); in rcu_reader_rev()
34539 RCU_MT_BUG_ON(test, mas.last != r_end); in rcu_reader_rev()
34574 mas.index, mas.last, entry, in rcu_reader_rev()
34582 printk("%lu-%lu %p != %p\n", mas.index, in rcu_reader_rev()
34583 mas.last, entry, expected); in rcu_reader_rev()
34899 MA_STATE(mas, test->mt, test->range_start, test->range_start); in rcu_loop()
34910 mas_for_each(&mas, entry, test->range_end) { in rcu_loop()
34912 expected = xa_mk_value(mas.index ? mas.index / 10 : 0); in rcu_loop()
34915 if (mas.index < test->index || mas.index > test->last) { in rcu_loop()
34918 mas.index, mas.last, entry, expected); in rcu_loop()
34933 mas_set(&mas, test->range_start); in rcu_loop()
34976 MA_STATE(mas, test->mt, test->index, test->index); in rcu_slot_store_reader()
34982 mas_walk(&mas); in rcu_slot_store_reader()
34984 RCU_MT_BUG_ON(test, (test->index - mas.index) != in rcu_slot_store_reader()
34985 (mas.last - test->last)); in rcu_slot_store_reader()
35341 static void mas_dfs_preorder(struct ma_state *mas) in mas_dfs_preorder() argument
35348 if (mas->status == ma_start) { in mas_dfs_preorder()
35349 mas_start(mas); in mas_dfs_preorder()
35353 if (mte_is_leaf(mas->node) && mte_is_root(mas->node)) in mas_dfs_preorder()
35357 end = mas_data_end(mas); in mas_dfs_preorder()
35358 if (mte_is_leaf(mas->node) || in mas_dfs_preorder()
35360 if (mte_is_root(mas->node)) in mas_dfs_preorder()
35363 slot = mte_parent_slot(mas->node) + 1; in mas_dfs_preorder()
35364 mas_ascend(mas); in mas_dfs_preorder()
35368 prev = mas->node; in mas_dfs_preorder()
35369 mas->node = mas_get_slot(mas, slot); in mas_dfs_preorder()
35370 if (!mas->node || slot > end) { in mas_dfs_preorder()
35374 mas->node = prev; in mas_dfs_preorder()
35375 slot = mte_parent_slot(mas->node) + 1; in mas_dfs_preorder()
35376 mas_ascend(mas); in mas_dfs_preorder()
35380 mas->max = mas_safe_pivot(mas, pivots, slot, mte_node_type(prev)); in mas_dfs_preorder()
35381 mas->min = mas_safe_min(mas, pivots, slot); in mas_dfs_preorder()
35385 mas->status = ma_none; in mas_dfs_preorder()
35393 MA_STATE(mas, mt, 0, 0); in check_dfs_preorder()
35403 mas_dfs_preorder(&mas); in check_dfs_preorder()
35404 } while (!mas_is_none(&mas)); in check_dfs_preorder()
35409 mas_reset(&mas); in check_dfs_preorder()
35417 mas_dfs_preorder(&mas); in check_dfs_preorder()
35418 } while (!mas_is_none(&mas)); in check_dfs_preorder()
35424 mas_reset(&mas); in check_dfs_preorder()
35429 mas_dfs_preorder(&mas); in check_dfs_preorder()
35430 } while (!mas_is_none(&mas)); in check_dfs_preorder()
35436 mas_reset(&mas); in check_dfs_preorder()
35439 mas_expected_entries(&mas, max); in check_dfs_preorder()
35441 mas.index = mas.last = count; in check_dfs_preorder()
35442 mas_store(&mas, xa_mk_value(count)); in check_dfs_preorder()
35443 MT_BUG_ON(mt, mas_is_err(&mas)); in check_dfs_preorder()
35445 mas_destroy(&mas); in check_dfs_preorder()
35464 MA_STATE(mas, mt, 10, 20); in check_prealloc()
35471 mas_set_range(&mas, 470, 500); in check_prealloc()
35472 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35473 allocated = mas_allocated(&mas); in check_prealloc()
35474 height = mas_mt_height(&mas); in check_prealloc()
35477 mas_destroy(&mas); in check_prealloc()
35478 allocated = mas_allocated(&mas); in check_prealloc()
35481 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35482 allocated = mas_allocated(&mas); in check_prealloc()
35483 height = mas_mt_height(&mas); in check_prealloc()
35486 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35487 mas_destroy(&mas); in check_prealloc()
35488 allocated = mas_allocated(&mas); in check_prealloc()
35492 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35493 allocated = mas_allocated(&mas); in check_prealloc()
35494 height = mas_mt_height(&mas); in check_prealloc()
35496 mn = mas_pop_node(&mas); in check_prealloc()
35497 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35500 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35501 mas_destroy(&mas); in check_prealloc()
35502 allocated = mas_allocated(&mas); in check_prealloc()
35505 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35506 allocated = mas_allocated(&mas); in check_prealloc()
35507 height = mas_mt_height(&mas); in check_prealloc()
35509 mn = mas_pop_node(&mas); in check_prealloc()
35510 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35511 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35512 mas_destroy(&mas); in check_prealloc()
35513 allocated = mas_allocated(&mas); in check_prealloc()
35518 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35519 allocated = mas_allocated(&mas); in check_prealloc()
35520 height = mas_mt_height(&mas); in check_prealloc()
35522 mn = mas_pop_node(&mas); in check_prealloc()
35523 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35524 mas_push_node(&mas, mn); in check_prealloc()
35525 MT_BUG_ON(mt, mas_allocated(&mas) != allocated); in check_prealloc()
35526 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35527 mas_destroy(&mas); in check_prealloc()
35528 allocated = mas_allocated(&mas); in check_prealloc()
35531 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35532 allocated = mas_allocated(&mas); in check_prealloc()
35533 height = mas_mt_height(&mas); in check_prealloc()
35535 mas_store_prealloc(&mas, ptr); in check_prealloc()
35536 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35539 mas_set_range(&mas, 6, 9); in check_prealloc()
35540 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35541 allocated = mas_allocated(&mas); in check_prealloc()
35543 mas_store_prealloc(&mas, ptr); in check_prealloc()
35544 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35546 mas_set_range(&mas, 6, 10); in check_prealloc()
35547 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35548 allocated = mas_allocated(&mas); in check_prealloc()
35549 height = mas_mt_height(&mas); in check_prealloc()
35551 mas_store_prealloc(&mas, ptr); in check_prealloc()
35552 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35555 mas_set_range(&mas, 54, 54); in check_prealloc()
35556 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35557 allocated = mas_allocated(&mas); in check_prealloc()
35558 height = mas_mt_height(&mas); in check_prealloc()
35560 mas_store_prealloc(&mas, ptr); in check_prealloc()
35561 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35564 mas_set_range(&mas, 1, 100); in check_prealloc()
35565 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0); in check_prealloc()
35566 allocated = mas_allocated(&mas); in check_prealloc()
35567 height = mas_mt_height(&mas); in check_prealloc()
35569 mas_destroy(&mas); in check_prealloc()
35573 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35574 allocated = mas_allocated(&mas); in check_prealloc()
35575 height = mas_mt_height(&mas); in check_prealloc()
35578 mas_store_prealloc(&mas, ptr); in check_prealloc()
35579 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35580 mas_set_range(&mas, 0, 200); in check_prealloc()
35582 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0); in check_prealloc()
35583 allocated = mas_allocated(&mas); in check_prealloc()
35584 height = mas_mt_height(&mas); in check_prealloc()
35593 MA_STATE(mas, mt, 1200, 2380); in check_spanning_write()
35599 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35600 mas_set(&mas, 1205); in check_spanning_write()
35601 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35609 mas_set_range(&mas, 9, 50006); /* Will expand to 0 - ULONG_MAX */ in check_spanning_write()
35610 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35611 mas_set(&mas, 1205); in check_spanning_write()
35612 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35622 mas_set_range(&mas, 0, 12900); /* Spans more than 2 levels */ in check_spanning_write()
35624 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35625 mas_set(&mas, 1205); in check_spanning_write()
35626 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35635 mas_set_range(&mas, 0, 300); in check_spanning_write()
35637 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35638 mas_set(&mas, 15); in check_spanning_write()
35639 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35648 mas_set_range(&mas, 0, 12865); in check_spanning_write()
35650 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35651 mas_set(&mas, 15); in check_spanning_write()
35652 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35661 mas_set_range(&mas, 90, 13665); in check_spanning_write()
35663 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35664 mas_set(&mas, 95); in check_spanning_write()
35665 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35674 mas_set_range(&mas, 46805, 49995); in check_spanning_write()
35676 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35677 mas_set(&mas, 46815); in check_spanning_write()
35678 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35690 mas_set_range(&mas, 32395, 49995); in check_spanning_write()
35692 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35693 mas_set(&mas, 46815); in check_spanning_write()
35694 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35705 mas_set_range(&mas, 38875, 43190); in check_spanning_write()
35707 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35708 mas_set(&mas, 38900); in check_spanning_write()
35709 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35718 mas_set(&mas, 47606); in check_spanning_write()
35719 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); in check_spanning_write()
35720 mas_set(&mas, 47607); in check_spanning_write()
35721 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); in check_spanning_write()
35722 mas_set(&mas, 47608); in check_spanning_write()
35723 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); in check_spanning_write()
35724 mas_set(&mas, 47609); in check_spanning_write()
35725 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); in check_spanning_write()
35727 mas_ascend(&mas); in check_spanning_write()
35728 MT_BUG_ON(mt, (mas_data_end(&mas)) != mt_slot_count(mas.node) - 1); in check_spanning_write()
35729 mas_set_range(&mas, 11516, 48940); in check_spanning_write()
35730 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35738 mas_set_range(&mas, 43200, 49999); in check_spanning_write()
35740 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35741 mas_set(&mas, 43200); in check_spanning_write()
35742 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35751 mas_set_range(&mas, 76, 875); in check_spanning_write()
35752 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35762 MA_STATE(mas, mt, 959, 959); in check_null_expand()
35767 mas_lock(&mas); in check_null_expand()
35768 mas_walk(&mas); in check_null_expand()
35769 data_end = mas_data_end(&mas); in check_null_expand()
35770 mas_set_range(&mas, 959, 963); in check_null_expand()
35771 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_null_expand()
35773 MT_BUG_ON(mt, data_end != mas_data_end(&mas)); in check_null_expand()
35776 mas_set(&mas, 880); in check_null_expand()
35777 mas_walk(&mas); in check_null_expand()
35778 data_end = mas_data_end(&mas); in check_null_expand()
35779 mas_set_range(&mas, 884, 887); in check_null_expand()
35780 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_null_expand()
35784 MT_BUG_ON(mt, data_end != mas_data_end(&mas)); in check_null_expand()
35788 mas_set(&mas, 890); in check_null_expand()
35789 mas_walk(&mas); in check_null_expand()
35790 data_end = mas_data_end(&mas); in check_null_expand()
35791 mas_set_range(&mas, 900, 905); in check_null_expand()
35792 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_null_expand()
35798 MT_BUG_ON(mt, data_end - 2 != mas_data_end(&mas)); in check_null_expand()
35802 mas_set(&mas, 800); in check_null_expand()
35803 mas_walk(&mas); in check_null_expand()
35804 data_end = mas_data_end(&mas); in check_null_expand()
35805 mas_set_range(&mas, 810, 825); in check_null_expand()
35806 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_null_expand()
35812 MT_BUG_ON(mt, data_end - 4 != mas_data_end(&mas)); in check_null_expand()
35814 mas_unlock(&mas); in check_null_expand()
35998 static __init void mas_subtree_max_range(struct ma_state *mas) in mas_subtree_max_range() argument
36000 unsigned long limit = mas->max; in mas_subtree_max_range()
36001 MA_STATE(newmas, mas->tree, 0, 0); in mas_subtree_max_range()
36004 mas_for_each(mas, entry, limit) { in mas_subtree_max_range()
36005 if (mas->last - mas->index >= in mas_subtree_max_range()
36007 newmas = *mas; in mas_subtree_max_range()
36011 *mas = newmas; in mas_subtree_max_range()
36027 MA_STATE(mas, mt, 0, 0); in build_full_tree()
36038 mas_set(&mas, 0); in build_full_tree()
36040 mas.max = ULONG_MAX; in build_full_tree()
36045 mas_dfs_preorder(&mas); in build_full_tree()
36046 if (mas_is_none(&mas)) in build_full_tree()
36049 type = mte_node_type(mas.node); in build_full_tree()
36050 if (mas_data_end(&mas) + 1 < mt_slots[type]) { in build_full_tree()
36051 mas_set(&mas, mas.min); in build_full_tree()
36056 mas_subtree_max_range(&mas); in build_full_tree()
36057 step = mas.last - mas.index; in build_full_tree()
36064 mas.last = mas.index + step; in build_full_tree()
36065 mas_store_gfp(&mas, xa_mk_value(5), in build_full_tree()
36233 MA_STATE(mas, mt, 6, 10); in writer2()
36235 mtree_lock(mas.tree); in writer2()
36236 mas_store(&mas, xa_mk_value(0xC)); in writer2()
36237 mas_destroy(&mas); in writer2()
36238 mtree_unlock(mas.tree); in writer2()
36252 MA_STATE(mas, mt, 0, 5); in check_nomem_writer_race()
36266 mas_erase(&mas); in check_nomem_writer_race()
36276 mas_set_range(&mas, 0, 5); in check_nomem_writer_race()
36278 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_nomem_writer_race()
36294 MA_STATE(mas, mt, 0, 0); in check_vma_modification()
36298 __mas_set_range(&mas, 0x7fffffffe000, 0x7ffffffff000 - 1); in check_vma_modification()
36299 mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL); in check_vma_modification()
36300 mas_store_prealloc(&mas, xa_mk_value(1)); in check_vma_modification()
36303 mas_prev_range(&mas, 0); in check_vma_modification()
36305 __mas_set_range(&mas, 0x7ffde4ca1000, 0x7ffffffff000 - 1); in check_vma_modification()
36306 mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL); in check_vma_modification()
36307 mas_store_prealloc(&mas, xa_mk_value(1)); in check_vma_modification()
36310 __mas_set_range(&mas, 0x7ffde4ca2000, 0x7ffffffff000 - 1); in check_vma_modification()
36311 mas_preallocate(&mas, NULL, GFP_KERNEL); in check_vma_modification()
36312 mas_store_prealloc(&mas, NULL); in check_vma_modification()
36315 mas_destroy(&mas); in check_vma_modification()
36326 MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); in check_bulk_rebalance()
36334 mas_expected_entries(&mas, max); in check_bulk_rebalance()
36335 mas_erase(&mas); in check_bulk_rebalance()
36336 MT_BUG_ON(mt, mas.store_type == wr_rebalance); in check_bulk_rebalance()
36337 } while (mas_prev(&mas, 0) != NULL); in check_bulk_rebalance()
36339 mas_destroy(&mas); in check_bulk_rebalance()
36435 static unsigned long get_last_index(struct ma_state *mas) in get_last_index() argument
36437 struct maple_node *node = mas_mn(mas); in get_last_index()
36438 enum maple_type mt = mte_node_type(mas->node); in get_last_index()
36440 unsigned long last_index = mas_data_end(mas); in get_last_index()
36455 MA_STATE(mas, &tree, 0, 0); in test_spanning_store_regression()
36465 mas_reset(&mas); in test_spanning_store_regression()
36466 mas_start(&mas); in test_spanning_store_regression()
36467 mas_descend(&mas); in test_spanning_store_regression()
36468 mas_descend(&mas); in test_spanning_store_regression()
36490 unsigned long tmp = get_last_index(&mas); in test_spanning_store_regression()
36492 if (mas_next_sibling(&mas)) { in test_spanning_store_regression()
36494 to = mas.max; in test_spanning_store_regression()
36503 mas_set_range(&mas, from, to); in test_spanning_store_regression()
36504 mas_store_gfp(&mas, xa_mk_value(0xdead), GFP_KERNEL); in test_spanning_store_regression()