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()
465 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
466 mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */ in check_new_node()
467 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
468 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1); in check_new_node()
469 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
470 mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 2); /* Request */ in check_new_node()
471 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
472 mas.status = ma_start; in check_new_node()
473 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 2); in check_new_node()
474 mas_destroy(&mas); in check_new_node()
476 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
477 mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 1); /* Request */ in check_new_node()
478 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
479 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 1); in check_new_node()
480 mas.node = MA_ERROR(-ENOMEM); in check_new_node()
481 mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 3 + 2); /* Request */ in check_new_node()
482 mas_nomem(&mas, GFP_KERNEL); /* Fill request */ in check_new_node()
483 mas.status = ma_start; in check_new_node()
484 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 3 + 2); in check_new_node()
485 mas_destroy(&mas); in check_new_node()
844 static inline void mas_node_walk(struct ma_state *mas, struct maple_node *node, in mas_node_walk() argument
856 (*range_max) = (*range_min) = mas->index; in mas_node_walk()
860 mas->offset = mas->index = mas->min; in mas_node_walk()
870 prev = mas->min; in mas_node_walk()
871 index = mas->index; in mas_node_walk()
890 max = mas->max; in mas_node_walk()
894 mas->offset = offset; in mas_node_walk()
899 mas->max = max; in mas_node_walk()
900 mas->min = prev; in mas_node_walk()
916 static inline bool mas_descend_walk(struct ma_state *mas, in mas_descend_walk() argument
923 next = mas->node; in mas_descend_walk()
927 mas_node_walk(mas, node, type, range_min, range_max); in mas_descend_walk()
928 next = mas_slot(mas, ma_slots(node, type), mas->offset); in mas_descend_walk()
936 mas->node = next; in mas_descend_walk()
951 static inline bool mas_tree_walk(struct ma_state *mas, unsigned long *range_min, in mas_tree_walk() argument
958 mas_start(mas); in mas_tree_walk()
959 if (mas_is_none(mas)) in mas_tree_walk()
962 if (mas_is_ptr(mas)) { in mas_tree_walk()
964 if (!mas->index) in mas_tree_walk()
970 ret = mas_descend_walk(mas, range_min, range_max); in mas_tree_walk()
971 if (unlikely(mte_dead_node(mas->node))) { in mas_tree_walk()
972 mas->status = ma_start; in mas_tree_walk()
976 mas->end = mas_data_end(mas); in mas_tree_walk()
980 mas->offset = MAPLE_NODE_SLOTS; in mas_tree_walk()
984 static inline void *mas_range_load(struct ma_state *mas, in mas_range_load() argument
989 unsigned long index = mas->index; in mas_range_load()
991 if (mas_is_none(mas) || mas_is_paused(mas)) in mas_range_load()
992 mas->status = ma_start; in mas_range_load()
994 if (mas_tree_walk(mas, range_min, range_max)) in mas_range_load()
995 if (unlikely(mas->status == ma_root)) in mas_range_load()
996 return mas_root(mas); in mas_range_load()
998 if (likely(mas->offset != MAPLE_NODE_SLOTS)) in mas_range_load()
999 entry = mas_get_slot(mas, mas->offset); in mas_range_load()
1001 if (mas_is_active(mas) && mte_dead_node(mas->node)) { in mas_range_load()
1002 mas_set(mas, index); in mas_range_load()
1019 MA_STATE(mas, mt, 0, 0); in check_erase2_testset()
1120 mas_reset(&mas); in check_erase2_testset()
1121 mas.index = 0; in check_erase2_testset()
1123 mas_for_each(&mas, foo, ULONG_MAX) { in check_erase2_testset()
1125 if (addr == mas.index) { in check_erase2_testset()
1126 mt_dump(mas.tree, mt_dump_hex); in check_erase2_testset()
1128 mas.index, mas.last); in check_erase2_testset()
1131 addr = mas.index; in check_erase2_testset()
1135 pr_err("mas: %lu -> %p\n", mas.index, foo); in check_erase2_testset()
1149 MT_BUG_ON(mt, mtree_load(mas.tree, 0) != NULL); in check_erase2_testset()
33927 MA_STATE(mas, mt, 0, 0); in check_erase2_sets()
33949 mas_for_each(&mas, entry, ULONG_MAX) { in check_erase2_sets()
33989 mas_reset(&mas); in check_erase2_sets()
33993 mas_empty_area_rev(&mas, 12288, 140014592737280, 0x2000); in check_erase2_sets()
33994 MT_BUG_ON(mt, mas.last != 140014592573439); in check_erase2_sets()
33997 mas_reset(&mas); in check_erase2_sets()
33998 mas.tree = mt; in check_erase2_sets()
34000 mas.index = 0; in check_erase2_sets()
34004 mas_for_each(&mas, entry, ULONG_MAX) { in check_erase2_sets()
34012 mas_reset(&mas); in check_erase2_sets()
34017 mas_empty_area_rev(&mas, 0, 140373518663680, 4096); in check_erase2_sets()
34032 mas_reset(&mas); in check_erase2_sets()
34036 mas_empty_area_rev(&mas, 4096, 139921865637888, 0x6000); in check_erase2_sets()
34037 MT_BUG_ON(mt, mas.last != 139921865547775); in check_erase2_sets()
34047 mas_reset(&mas); in check_erase2_sets()
34051 mas_empty_area_rev(&mas, 4096, 139953197334528, 0x1000); in check_erase2_sets()
34052 MT_BUG_ON(mt, mas.last != 139953197322239); in check_erase2_sets()
34063 mas_reset(&mas); in check_erase2_sets()
34067 mas_empty_area_rev(&mas, 4096, 140222972858368, 2215936); in check_erase2_sets()
34068 MT_BUG_ON(mt, mas.last != 140222968475647); in check_erase2_sets()
34081 mas_reset(&mas); in check_erase2_sets()
34085 mas.index = 140656779083776; in check_erase2_sets()
34086 entry = mas_find(&mas, ULONG_MAX); in check_erase2_sets()
34088 entry = mas_prev(&mas, 0); in check_erase2_sets()
34150 mas_reset(&mas); in check_erase2_sets()
34154 mas_empty_area_rev(&mas, 4096, 140109042671616, 409600); in check_erase2_sets()
34155 MT_BUG_ON(mt, mas.last != 140109040959487); in check_erase2_sets()
34162 mas_reset(&mas); in check_erase2_sets()
34172 mas_reset(&mas); in check_erase2_sets()
34176 mas_empty_area_rev(&mas, 4096, 139918413357056, 2097152); in check_erase2_sets()
34178 mas.index = (mas.last + 1 - 2097152 - 0) & (~2093056); in check_erase2_sets()
34179 MT_BUG_ON(mt, mas.index != 139918401601536); in check_erase2_sets()
34188 mas_reset(&mas); in check_erase2_sets()
34201 mas_reset(&mas); in check_erase2_sets()
34214 mas_reset(&mas); in check_erase2_sets()
34223 mas_reset(&mas); in check_erase2_sets()
34243 mas_reset(&mas); in check_erase2_sets()
34247 mas_empty_area_rev(&mas, 4096, 140583656296448, 134217728); in check_erase2_sets()
34248 MT_BUG_ON(mt, mas.last != 140583003750399); in check_erase2_sets()
34258 mas_reset(&mas); in check_erase2_sets()
34268 mas_reset(&mas); in check_erase2_sets()
34278 mas_reset(&mas); in check_erase2_sets()
34286 mas_reset(&mas); in check_erase2_sets()
34294 mas_reset(&mas); in check_erase2_sets()
34302 mas_reset(&mas); in check_erase2_sets()
34309 mas_reset(&mas); in check_erase2_sets()
34316 mas_reset(&mas); in check_erase2_sets()
34325 mas_reset(&mas); in check_erase2_sets()
34329 mas_empty_area_rev(&mas, 4096, 4052029440, 28672); in check_erase2_sets()
34330 MT_BUG_ON(mt, mas.last != 4041211903); in check_erase2_sets()
34337 mas_reset(&mas); in check_erase2_sets()
34382 MA_STATE(mas, test->mt, 0, 0); in rcu_reader_fwd()
34391 mas_set(&mas, test->index[index]); in rcu_reader_fwd()
34392 mas_for_each(&mas, entry, test->last[index + 9]) { in rcu_reader_fwd()
34404 if (mas.index == alt_start) { in rcu_reader_fwd()
34419 if (mas.index == r_start) { in rcu_reader_fwd()
34422 } else if (mas.index == alt_start) { in rcu_reader_fwd()
34430 RCU_MT_BUG_ON(test, mas.index != r_start); in rcu_reader_fwd()
34431 RCU_MT_BUG_ON(test, mas.last != r_end); in rcu_reader_fwd()
34447 printk("!!%lu-%lu -> %p not %p or %p\n", mas.index, mas.last, entry, expected, alt); in rcu_reader_fwd()
34470 printk("!!%lu-%lu -> %p not %p\n", mas.index, mas.last, entry, expected); in rcu_reader_fwd()
34492 MA_STATE(mas, test->mt, 0, 0); in rcu_reader_rev()
34502 mas_set(&mas, test->index[index + i]); in rcu_reader_rev()
34510 entry = mas_prev(&mas, test->index[index]); in rcu_reader_rev()
34517 if (mas.index == alt_start) { in rcu_reader_rev()
34533 if (mas.index == r_start) { in rcu_reader_rev()
34537 } else if (mas.index == alt_start) { in rcu_reader_rev()
34551 if (mas.index != r_start) { in rcu_reader_rev()
34556 mas.index, mas.last, entry, in rcu_reader_rev()
34560 RCU_MT_BUG_ON(test, mas.index != r_start); in rcu_reader_rev()
34561 RCU_MT_BUG_ON(test, mas.last != r_end); in rcu_reader_rev()
34596 mas.index, mas.last, entry, in rcu_reader_rev()
34604 printk("%lu-%lu %p != %p\n", mas.index, in rcu_reader_rev()
34605 mas.last, entry, expected); in rcu_reader_rev()
34921 MA_STATE(mas, test->mt, test->range_start, test->range_start); in rcu_loop()
34932 mas_for_each(&mas, entry, test->range_end) { in rcu_loop()
34934 expected = xa_mk_value(mas.index ? mas.index / 10 : 0); in rcu_loop()
34937 if (mas.index < test->index || mas.index > test->last) { in rcu_loop()
34940 mas.index, mas.last, entry, expected); in rcu_loop()
34955 mas_set(&mas, test->range_start); in rcu_loop()
34998 MA_STATE(mas, test->mt, test->index, test->index); in rcu_slot_store_reader()
35004 mas_walk(&mas); in rcu_slot_store_reader()
35006 RCU_MT_BUG_ON(test, (test->index - mas.index) != in rcu_slot_store_reader()
35007 (mas.last - test->last)); in rcu_slot_store_reader()
35363 static void mas_dfs_preorder(struct ma_state *mas) in mas_dfs_preorder() argument
35370 if (mas->status == ma_start) { in mas_dfs_preorder()
35371 mas_start(mas); in mas_dfs_preorder()
35375 if (mte_is_leaf(mas->node) && mte_is_root(mas->node)) in mas_dfs_preorder()
35379 end = mas_data_end(mas); in mas_dfs_preorder()
35380 if (mte_is_leaf(mas->node) || in mas_dfs_preorder()
35382 if (mte_is_root(mas->node)) in mas_dfs_preorder()
35385 slot = mte_parent_slot(mas->node) + 1; in mas_dfs_preorder()
35386 mas_ascend(mas); in mas_dfs_preorder()
35390 prev = mas->node; in mas_dfs_preorder()
35391 mas->node = mas_get_slot(mas, slot); in mas_dfs_preorder()
35392 if (!mas->node || slot > end) { in mas_dfs_preorder()
35396 mas->node = prev; in mas_dfs_preorder()
35397 slot = mte_parent_slot(mas->node) + 1; in mas_dfs_preorder()
35398 mas_ascend(mas); in mas_dfs_preorder()
35402 mas->max = mas_safe_pivot(mas, pivots, slot, mte_node_type(prev)); in mas_dfs_preorder()
35403 mas->min = mas_safe_min(mas, pivots, slot); in mas_dfs_preorder()
35407 mas->status = ma_none; in mas_dfs_preorder()
35415 MA_STATE(mas, mt, 0, 0); in check_dfs_preorder()
35425 mas_dfs_preorder(&mas); in check_dfs_preorder()
35426 } while (!mas_is_none(&mas)); in check_dfs_preorder()
35431 mas_reset(&mas); in check_dfs_preorder()
35439 mas_dfs_preorder(&mas); in check_dfs_preorder()
35440 } while (!mas_is_none(&mas)); in check_dfs_preorder()
35446 mas_reset(&mas); in check_dfs_preorder()
35451 mas_dfs_preorder(&mas); in check_dfs_preorder()
35452 } while (!mas_is_none(&mas)); in check_dfs_preorder()
35458 mas_reset(&mas); in check_dfs_preorder()
35461 mas_expected_entries(&mas, max); in check_dfs_preorder()
35463 mas.index = mas.last = count; in check_dfs_preorder()
35464 mas_store(&mas, xa_mk_value(count)); in check_dfs_preorder()
35465 MT_BUG_ON(mt, mas_is_err(&mas)); in check_dfs_preorder()
35467 mas_destroy(&mas); in check_dfs_preorder()
35486 MA_STATE(mas, mt, 10, 20); in check_prealloc()
35493 mas_set_range(&mas, 470, 500); in check_prealloc()
35494 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35495 allocated = mas_allocated(&mas); in check_prealloc()
35496 height = mas_mt_height(&mas); in check_prealloc()
35499 mas_destroy(&mas); in check_prealloc()
35500 allocated = mas_allocated(&mas); in check_prealloc()
35503 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35504 allocated = mas_allocated(&mas); in check_prealloc()
35505 height = mas_mt_height(&mas); in check_prealloc()
35508 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35509 mas_destroy(&mas); in check_prealloc()
35510 allocated = mas_allocated(&mas); in check_prealloc()
35514 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35515 allocated = mas_allocated(&mas); in check_prealloc()
35516 height = mas_mt_height(&mas); in check_prealloc()
35518 mn = mas_pop_node(&mas); in check_prealloc()
35519 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35522 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35523 mas_destroy(&mas); in check_prealloc()
35524 allocated = mas_allocated(&mas); in check_prealloc()
35527 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35528 allocated = mas_allocated(&mas); in check_prealloc()
35529 height = mas_mt_height(&mas); in check_prealloc()
35531 mn = mas_pop_node(&mas); in check_prealloc()
35532 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35533 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35534 mas_destroy(&mas); in check_prealloc()
35535 allocated = mas_allocated(&mas); 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()
35542 height = mas_mt_height(&mas); in check_prealloc()
35544 mn = mas_pop_node(&mas); in check_prealloc()
35545 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1); in check_prealloc()
35546 mas_push_node(&mas, mn); in check_prealloc()
35547 MT_BUG_ON(mt, mas_allocated(&mas) != allocated); in check_prealloc()
35548 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35549 mas_destroy(&mas); in check_prealloc()
35550 allocated = mas_allocated(&mas); in check_prealloc()
35553 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35554 allocated = mas_allocated(&mas); in check_prealloc()
35555 height = mas_mt_height(&mas); in check_prealloc()
35557 mas_store_prealloc(&mas, ptr); in check_prealloc()
35558 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35561 mas_set_range(&mas, 6, 9); in check_prealloc()
35562 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35563 allocated = mas_allocated(&mas); in check_prealloc()
35565 mas_store_prealloc(&mas, ptr); in check_prealloc()
35566 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35568 mas_set_range(&mas, 6, 10); in check_prealloc()
35569 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35570 allocated = mas_allocated(&mas); in check_prealloc()
35571 height = mas_mt_height(&mas); in check_prealloc()
35573 mas_store_prealloc(&mas, ptr); in check_prealloc()
35574 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35577 mas_set_range(&mas, 54, 54); in check_prealloc()
35578 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35579 allocated = mas_allocated(&mas); in check_prealloc()
35580 height = mas_mt_height(&mas); in check_prealloc()
35582 mas_store_prealloc(&mas, ptr); in check_prealloc()
35583 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35586 mas_set_range(&mas, 1, 100); in check_prealloc()
35587 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0); in check_prealloc()
35588 allocated = mas_allocated(&mas); in check_prealloc()
35589 height = mas_mt_height(&mas); in check_prealloc()
35591 mas_destroy(&mas); in check_prealloc()
35595 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0); in check_prealloc()
35596 allocated = mas_allocated(&mas); in check_prealloc()
35597 height = mas_mt_height(&mas); in check_prealloc()
35600 mas_store_prealloc(&mas, ptr); in check_prealloc()
35601 MT_BUG_ON(mt, mas_allocated(&mas) != 0); in check_prealloc()
35602 mas_set_range(&mas, 0, 200); in check_prealloc()
35604 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0); in check_prealloc()
35605 allocated = mas_allocated(&mas); in check_prealloc()
35606 height = mas_mt_height(&mas); in check_prealloc()
35615 MA_STATE(mas, mt, 1200, 2380); in check_spanning_write()
35621 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35622 mas_set(&mas, 1205); in check_spanning_write()
35623 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35631 mas_set_range(&mas, 9, 50006); /* Will expand to 0 - ULONG_MAX */ in check_spanning_write()
35632 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35633 mas_set(&mas, 1205); in check_spanning_write()
35634 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35644 mas_set_range(&mas, 0, 12900); /* Spans more than 2 levels */ in check_spanning_write()
35646 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35647 mas_set(&mas, 1205); in check_spanning_write()
35648 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35657 mas_set_range(&mas, 0, 300); in check_spanning_write()
35659 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35660 mas_set(&mas, 15); in check_spanning_write()
35661 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35670 mas_set_range(&mas, 0, 12865); in check_spanning_write()
35672 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35673 mas_set(&mas, 15); in check_spanning_write()
35674 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35683 mas_set_range(&mas, 90, 13665); in check_spanning_write()
35685 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35686 mas_set(&mas, 95); in check_spanning_write()
35687 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35696 mas_set_range(&mas, 46805, 49995); in check_spanning_write()
35698 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35699 mas_set(&mas, 46815); in check_spanning_write()
35700 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35712 mas_set_range(&mas, 32395, 49995); in check_spanning_write()
35714 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35715 mas_set(&mas, 46815); in check_spanning_write()
35716 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35727 mas_set_range(&mas, 38875, 43190); in check_spanning_write()
35729 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35730 mas_set(&mas, 38900); in check_spanning_write()
35731 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35740 mas_set(&mas, 47606); in check_spanning_write()
35741 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); in check_spanning_write()
35742 mas_set(&mas, 47607); in check_spanning_write()
35743 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); in check_spanning_write()
35744 mas_set(&mas, 47608); in check_spanning_write()
35745 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); in check_spanning_write()
35746 mas_set(&mas, 47609); in check_spanning_write()
35747 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL); in check_spanning_write()
35749 mas_ascend(&mas); in check_spanning_write()
35750 MT_BUG_ON(mt, (mas_data_end(&mas)) != mt_slot_count(mas.node) - 1); in check_spanning_write()
35751 mas_set_range(&mas, 11516, 48940); in check_spanning_write()
35752 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35760 mas_set_range(&mas, 43200, 49999); in check_spanning_write()
35762 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35763 mas_set(&mas, 43200); in check_spanning_write()
35764 MT_BUG_ON(mt, mas_walk(&mas) != NULL); in check_spanning_write()
35773 mas_set_range(&mas, 76, 875); in check_spanning_write()
35774 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_spanning_write()
35784 MA_STATE(mas, mt, 959, 959); in check_null_expand()
35789 mas_lock(&mas); in check_null_expand()
35790 mas_walk(&mas); in check_null_expand()
35791 data_end = mas_data_end(&mas); in check_null_expand()
35792 mas_set_range(&mas, 959, 963); in check_null_expand()
35793 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_null_expand()
35795 MT_BUG_ON(mt, data_end != mas_data_end(&mas)); in check_null_expand()
35798 mas_set(&mas, 880); in check_null_expand()
35799 mas_walk(&mas); in check_null_expand()
35800 data_end = mas_data_end(&mas); in check_null_expand()
35801 mas_set_range(&mas, 884, 887); in check_null_expand()
35802 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_null_expand()
35806 MT_BUG_ON(mt, data_end != mas_data_end(&mas)); in check_null_expand()
35810 mas_set(&mas, 890); in check_null_expand()
35811 mas_walk(&mas); in check_null_expand()
35812 data_end = mas_data_end(&mas); in check_null_expand()
35813 mas_set_range(&mas, 900, 905); in check_null_expand()
35814 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_null_expand()
35820 MT_BUG_ON(mt, data_end - 2 != mas_data_end(&mas)); in check_null_expand()
35824 mas_set(&mas, 800); in check_null_expand()
35825 mas_walk(&mas); in check_null_expand()
35826 data_end = mas_data_end(&mas); in check_null_expand()
35827 mas_set_range(&mas, 810, 825); in check_null_expand()
35828 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_null_expand()
35834 MT_BUG_ON(mt, data_end - 4 != mas_data_end(&mas)); in check_null_expand()
35836 mas_unlock(&mas); in check_null_expand()
36020 static __init void mas_subtree_max_range(struct ma_state *mas) in mas_subtree_max_range() argument
36022 unsigned long limit = mas->max; in mas_subtree_max_range()
36023 MA_STATE(newmas, mas->tree, 0, 0); in mas_subtree_max_range()
36026 mas_for_each(mas, entry, limit) { in mas_subtree_max_range()
36027 if (mas->last - mas->index >= in mas_subtree_max_range()
36029 newmas = *mas; in mas_subtree_max_range()
36033 *mas = newmas; in mas_subtree_max_range()
36049 MA_STATE(mas, mt, 0, 0); in build_full_tree()
36060 mas_set(&mas, 0); in build_full_tree()
36062 mas.max = ULONG_MAX; in build_full_tree()
36067 mas_dfs_preorder(&mas); in build_full_tree()
36068 if (mas_is_none(&mas)) in build_full_tree()
36071 type = mte_node_type(mas.node); in build_full_tree()
36072 if (mas_data_end(&mas) + 1 < mt_slots[type]) { in build_full_tree()
36073 mas_set(&mas, mas.min); in build_full_tree()
36078 mas_subtree_max_range(&mas); in build_full_tree()
36079 step = mas.last - mas.index; in build_full_tree()
36086 mas.last = mas.index + step; in build_full_tree()
36087 mas_store_gfp(&mas, xa_mk_value(5), in build_full_tree()
36255 MA_STATE(mas, mt, 6, 10); in writer2()
36257 mtree_lock(mas.tree); in writer2()
36258 mas_store(&mas, xa_mk_value(0xC)); in writer2()
36259 mas_destroy(&mas); in writer2()
36260 mtree_unlock(mas.tree); in writer2()
36274 MA_STATE(mas, mt, 0, 5); in check_nomem_writer_race()
36288 mas_erase(&mas); in check_nomem_writer_race()
36298 mas_set_range(&mas, 0, 5); in check_nomem_writer_race()
36300 mas_store_gfp(&mas, NULL, GFP_KERNEL); in check_nomem_writer_race()
36316 MA_STATE(mas, mt, 0, 0); in check_vma_modification()
36320 __mas_set_range(&mas, 0x7fffffffe000, 0x7ffffffff000 - 1); in check_vma_modification()
36321 mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL); in check_vma_modification()
36322 mas_store_prealloc(&mas, xa_mk_value(1)); in check_vma_modification()
36325 mas_prev_range(&mas, 0); in check_vma_modification()
36327 __mas_set_range(&mas, 0x7ffde4ca1000, 0x7ffffffff000 - 1); in check_vma_modification()
36328 mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL); in check_vma_modification()
36329 mas_store_prealloc(&mas, xa_mk_value(1)); in check_vma_modification()
36332 __mas_set_range(&mas, 0x7ffde4ca2000, 0x7ffffffff000 - 1); in check_vma_modification()
36333 mas_preallocate(&mas, NULL, GFP_KERNEL); in check_vma_modification()
36334 mas_store_prealloc(&mas, NULL); in check_vma_modification()
36337 mas_destroy(&mas); in check_vma_modification()
36348 MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX); in check_bulk_rebalance()
36356 mas_expected_entries(&mas, max); in check_bulk_rebalance()
36357 mas_erase(&mas); in check_bulk_rebalance()
36358 MT_BUG_ON(mt, mas.store_type == wr_rebalance); in check_bulk_rebalance()
36359 } while (mas_prev(&mas, 0) != NULL); in check_bulk_rebalance()
36361 mas_destroy(&mas); in check_bulk_rebalance()
36457 static unsigned long get_last_index(struct ma_state *mas) in get_last_index() argument
36459 struct maple_node *node = mas_mn(mas); in get_last_index()
36460 enum maple_type mt = mte_node_type(mas->node); in get_last_index()
36462 unsigned long last_index = mas_data_end(mas); in get_last_index()
36477 MA_STATE(mas, &tree, 0, 0); in test_spanning_store_regression()
36487 mas_reset(&mas); in test_spanning_store_regression()
36488 mas_start(&mas); in test_spanning_store_regression()
36489 mas_descend(&mas); in test_spanning_store_regression()
36490 mas_descend(&mas); in test_spanning_store_regression()
36512 unsigned long tmp = get_last_index(&mas); in test_spanning_store_regression()
36514 if (mas_next_sibling(&mas)) { in test_spanning_store_regression()
36516 to = mas.max; in test_spanning_store_regression()
36525 mas_set_range(&mas, from, to); in test_spanning_store_regression()
36526 mas_store_gfp(&mas, xa_mk_value(0xdead), GFP_KERNEL); in test_spanning_store_regression()