Lines Matching defs:mas
66 static int get_alloc_node_count(struct ma_state *mas)
69 struct maple_alloc *node = mas->alloc;
80 static void check_mas_alloc_node_count(struct ma_state *mas)
82 mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 1, GFP_KERNEL);
83 mas_node_count_gfp(mas, MAPLE_ALLOC_SLOTS + 3, GFP_KERNEL);
84 MT_BUG_ON(mas->tree, get_alloc_node_count(mas) != mas->alloc->total);
85 mas_destroy(mas);
100 MA_STATE(mas, mt, 0, 0);
102 check_mas_alloc_node_count(&mas);
108 mas_node_count(&mas, 3);
110 MT_BUG_ON(mt, mas_alloc_req(&mas) != 3);
112 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM));
113 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
115 MT_BUG_ON(mt, mas_allocated(&mas) != 3);
116 mn = mas_pop_node(&mas);
119 MT_BUG_ON(mt, mas.alloc == NULL);
120 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
121 mas_push_node(&mas, mn);
122 mas_reset(&mas);
123 mas_destroy(&mas);
130 mas_set_alloc_req(&mas, 1);
132 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1);
133 mas_set_err(&mas, -ENOMEM);
135 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
137 mn = mas_pop_node(&mas);
142 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
146 mas.status = ma_start;
147 mas_destroy(&mas);
149 mas_node_count(&mas, 3);
151 mas_nomem(&mas, GFP_KERNEL);
153 MT_BUG_ON(mt, mas_allocated(&mas) != 3);
155 MT_BUG_ON(mt, mas_alloc_req(&mas) != 0);
157 MT_BUG_ON(mt, mas.alloc == NULL);
158 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
159 MT_BUG_ON(mt, mas.alloc->slot[1] == NULL);
161 MT_BUG_ON(mt, mas_allocated(&mas) != 3);
163 mas_reset(&mas);
164 mas_destroy(&mas);
167 mas_set_alloc_req(&mas, 1);
168 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1);
169 mas_set_err(&mas, -ENOMEM);
171 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
172 MT_BUG_ON(mt, mas_allocated(&mas) != 1);
174 mn = mas_pop_node(&mas);
176 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
180 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
181 mas_push_node(&mas, mn);
182 MT_BUG_ON(mt, mas_allocated(&mas) != 1);
183 MT_BUG_ON(mt, mas.alloc->node_count);
185 mas_set_alloc_req(&mas, 2); /* request 2 more. */
186 MT_BUG_ON(mt, mas_alloc_req(&mas) != 2);
187 mas_set_err(&mas, -ENOMEM);
188 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
189 MT_BUG_ON(mt, mas_allocated(&mas) != 3);
190 MT_BUG_ON(mt, mas.alloc == NULL);
191 MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
192 MT_BUG_ON(mt, mas.alloc->slot[1] == NULL);
194 mn = mas_pop_node(&mas);
195 MT_BUG_ON(mt, mas_allocated(&mas) != i);
203 mas_set_alloc_req(&mas, total); /* request 2 more. */
204 MT_BUG_ON(mt, mas_alloc_req(&mas) != total);
205 mas_set_err(&mas, -ENOMEM);
206 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
226 MT_BUG_ON(mt, mas.alloc->node_count != e);
227 mn = mas_pop_node(&mas);
229 MT_BUG_ON(mt, mas_allocated(&mas) != i - 1);
237 mas_set_alloc_req(&mas, i);
238 mas_set_err(&mas, -ENOMEM);
239 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
241 mn = mas_pop_node(&mas);
242 MT_BUG_ON(mt, mas_allocated(&mas) != j - 1);
245 mas_push_node(&mas, mn);
246 MT_BUG_ON(mt, mas_allocated(&mas) != j);
247 mn = mas_pop_node(&mas);
249 MT_BUG_ON(mt, mas_allocated(&mas) != j - 1);
253 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
255 mas_set_alloc_req(&mas, i);
256 mas_set_err(&mas, -ENOMEM);
257 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
259 MT_BUG_ON(mt, mas_allocated(&mas) != i - j);
260 nodes[j] = mas_pop_node(&mas);
261 MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1);
266 mas_push_node(&mas, nodes[j]);
267 MT_BUG_ON(mt, mas_allocated(&mas) != i - j);
269 MT_BUG_ON(mt, mas_allocated(&mas) != i);
271 MT_BUG_ON(mt, mas_allocated(&mas) != i - j);
272 mn = mas_pop_node(&mas);
276 MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1);
278 mas_reset(&mas);
279 MT_BUG_ON(mt, mas_nomem(&mas, GFP_KERNEL));
280 mas_destroy(&mas);
286 mas_node_count(&mas, total);
288 mas_nomem(&mas, GFP_KERNEL);
289 MT_BUG_ON(mt, !mas.alloc);
291 smn = mas.alloc;
301 MT_BUG_ON(mt, mas_allocated(&mas) != total);
302 mas_reset(&mas);
303 mas_destroy(&mas); /* Free. */
305 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
307 mas_node_count(&mas, i); /* Request */
308 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
309 MT_BUG_ON(mt, mas_allocated(&mas) != i); /* check request filled */
311 mn = mas_pop_node(&mas); /* get the next node. */
317 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
322 mas_node_count(&mas, i); /* Request */
323 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
324 MT_BUG_ON(mt, mas_allocated(&mas) != i); /* check request filled */
326 mn = mas_pop_node(&mas); /* get the next node. */
332 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
347 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
348 mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */
349 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM));
350 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
351 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
352 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS);
354 mn = mas_pop_node(&mas); /* get the next node. */
357 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS);
358 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS - 1);
360 mas_push_node(&mas, mn);
361 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
362 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS);
365 mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 2); /* Request */
366 MT_BUG_ON(mt, mas_alloc_req(&mas) != 1);
367 MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM));
368 MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
369 MT_BUG_ON(mt, mas_alloc_req(&mas));
370 MT_BUG_ON(mt, mas.alloc->node_count != 1);
371 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2);
372 mn = mas_pop_node(&mas);
374 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
375 MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS);
376 mas_push_node(&mas, mn);
377 MT_BUG_ON(mt, mas.alloc->node_count != 1);
378 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2);
379 mn = mas_pop_node(&mas);
384 mn = mas_pop_node(&mas);
389 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
393 mas.node = MA_ERROR(-ENOMEM);
394 mas_node_count(&mas, i); /* Request */
395 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
396 mn = mas_pop_node(&mas); /* get the next node. */
397 mas_push_node(&mas, mn); /* put it back */
398 mas_destroy(&mas);
400 mas.node = MA_ERROR(-ENOMEM);
401 mas_node_count(&mas, i); /* Request */
402 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
403 mn = mas_pop_node(&mas); /* get the next node. */
404 mn2 = mas_pop_node(&mas); /* get the next node. */
405 mas_push_node(&mas, mn); /* put them back */
406 mas_push_node(&mas, mn2);
407 mas_destroy(&mas);
409 mas.node = MA_ERROR(-ENOMEM);
410 mas_node_count(&mas, i); /* Request */
411 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
412 mn = mas_pop_node(&mas); /* get the next node. */
413 mn2 = mas_pop_node(&mas); /* get the next node. */
414 mn3 = mas_pop_node(&mas); /* get the next node. */
415 mas_push_node(&mas, mn); /* put them back */
416 mas_push_node(&mas, mn2);
417 mas_push_node(&mas, mn3);
418 mas_destroy(&mas);
420 mas.node = MA_ERROR(-ENOMEM);
421 mas_node_count(&mas, i); /* Request */
422 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
423 mn = mas_pop_node(&mas); /* get the next node. */
426 mas_destroy(&mas);
428 mas.node = MA_ERROR(-ENOMEM);
429 mas_node_count(&mas, i); /* Request */
430 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
431 mn = mas_pop_node(&mas); /* get the next node. */
434 mn = mas_pop_node(&mas); /* get the next node. */
437 mn = mas_pop_node(&mas); /* get the next node. */
440 mas_destroy(&mas);
443 mas.node = MA_ERROR(-ENOMEM);
444 mas_node_count(&mas, 5); /* Request */
445 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
446 MT_BUG_ON(mt, mas_allocated(&mas) != 5);
447 mas.node = MA_ERROR(-ENOMEM);
448 mas_node_count(&mas, 10); /* Request */
449 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
450 mas.status = ma_start;
451 MT_BUG_ON(mt, mas_allocated(&mas) != 10);
452 mas_destroy(&mas);
454 mas.node = MA_ERROR(-ENOMEM);
455 mas_node_count(&mas, MAPLE_ALLOC_SLOTS - 1); /* Request */
456 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
457 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS - 1);
458 mas.node = MA_ERROR(-ENOMEM);
459 mas_node_count(&mas, 10 + MAPLE_ALLOC_SLOTS - 1); /* Request */
460 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
461 mas.status = ma_start;
462 MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1);
463 mas_destroy(&mas);
465 mas.node = MA_ERROR(-ENOMEM);
466 mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */
467 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
468 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
469 mas.node = MA_ERROR(-ENOMEM);
470 mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 2); /* Request */
471 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
472 mas.status = ma_start;
473 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 2);
474 mas_destroy(&mas);
476 mas.node = MA_ERROR(-ENOMEM);
477 mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 1); /* Request */
478 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
479 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 1);
480 mas.node = MA_ERROR(-ENOMEM);
481 mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 3 + 2); /* Request */
482 mas_nomem(&mas, GFP_KERNEL); /* Fill request */
483 mas.status = ma_start;
484 MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 3 + 2);
485 mas_destroy(&mas);
836 * @mas: The maple state
844 static inline void mas_node_walk(struct ma_state *mas, struct maple_node *node,
856 (*range_max) = (*range_min) = mas->index;
860 mas->offset = mas->index = mas->min;
870 prev = mas->min;
871 index = mas->index;
890 max = mas->max;
894 mas->offset = offset;
899 mas->max = max;
900 mas->min = prev;
905 * mas_descend_walk(): Locates a value and sets the mas->node and slot
908 * @mas: The maple state
912 * Check mas->node is still valid on return of any value.
916 static inline bool mas_descend_walk(struct ma_state *mas,
923 next = mas->node;
927 mas_node_walk(mas, node, type, range_min, range_max);
928 next = mas_slot(mas, ma_slots(node, type), mas->offset);
936 mas->node = next;
942 * mas_tree_walk() - Walk to @mas->index and set the range values.
943 * @mas: The maple state.
947 * Ranges are only valid if there is a valid entry at @mas->index.
951 static inline bool mas_tree_walk(struct ma_state *mas, unsigned long *range_min,
958 mas_start(mas);
959 if (mas_is_none(mas))
962 if (mas_is_ptr(mas)) {
964 if (!mas->index)
970 ret = mas_descend_walk(mas, range_min, range_max);
971 if (unlikely(mte_dead_node(mas->node))) {
972 mas->status = ma_start;
976 mas->end = mas_data_end(mas);
980 mas->offset = MAPLE_NODE_SLOTS;
984 static inline void *mas_range_load(struct ma_state *mas,
989 unsigned long index = mas->index;
991 if (mas_is_none(mas) || mas_is_paused(mas))
992 mas->status = ma_start;
994 if (mas_tree_walk(mas, range_min, range_max))
995 if (unlikely(mas->status == ma_root))
996 return mas_root(mas);
998 if (likely(mas->offset != MAPLE_NODE_SLOTS))
999 entry = mas_get_slot(mas, mas->offset);
1001 if (mas_is_active(mas) && mte_dead_node(mas->node)) {
1002 mas_set(mas, index);
1019 MA_STATE(mas, mt, 0, 0);
1120 mas_reset(&mas);
1121 mas.index = 0;
1123 mas_for_each(&mas, foo, ULONG_MAX) {
1125 if (addr == mas.index) {
1126 mt_dump(mas.tree, mt_dump_hex);
1128 mas.index, mas.last);
1131 addr = mas.index;
1135 pr_err("mas: %lu -> %p\n", mas.index, foo);
1149 MT_BUG_ON(mt, mtree_load(mas.tree, 0) != NULL);
33897 * mmap: mas.min 4041154560 max 4041191423 mas.last 4041191423
33898 * mmap: mas.index 4041162752 align mask 0 offset 0
33927 MA_STATE(mas, mt, 0, 0);
33949 mas_for_each(&mas, entry, ULONG_MAX) {
33989 mas_reset(&mas);
33993 mas_empty_area_rev(&mas, 12288, 140014592737280, 0x2000);
33994 MT_BUG_ON(mt, mas.last != 140014592573439);
33997 mas_reset(&mas);
33998 mas.tree = mt;
34000 mas.index = 0;
34004 mas_for_each(&mas, entry, ULONG_MAX) {
34012 mas_reset(&mas);
34017 mas_empty_area_rev(&mas, 0, 140373518663680, 4096);
34032 mas_reset(&mas);
34036 mas_empty_area_rev(&mas, 4096, 139921865637888, 0x6000);
34037 MT_BUG_ON(mt, mas.last != 139921865547775);
34047 mas_reset(&mas);
34051 mas_empty_area_rev(&mas, 4096, 139953197334528, 0x1000);
34052 MT_BUG_ON(mt, mas.last != 139953197322239);
34053 /* MT_BUG_ON(mt, mas.index != 139953197318144); */
34063 mas_reset(&mas);
34067 mas_empty_area_rev(&mas, 4096, 140222972858368, 2215936);
34068 MT_BUG_ON(mt, mas.last != 140222968475647);
34069 /*MT_BUG_ON(mt, mas.index != 140222966259712); */
34081 mas_reset(&mas);
34085 mas.index = 140656779083776;
34086 entry = mas_find(&mas, ULONG_MAX);
34088 entry = mas_prev(&mas, 0);
34150 mas_reset(&mas);
34154 mas_empty_area_rev(&mas, 4096, 140109042671616, 409600);
34155 MT_BUG_ON(mt, mas.last != 140109040959487);
34162 mas_reset(&mas);
34172 mas_reset(&mas);
34176 mas_empty_area_rev(&mas, 4096, 139918413357056, 2097152);
34178 mas.index = (mas.last + 1 - 2097152 - 0) & (~2093056);
34179 MT_BUG_ON(mt, mas.index != 139918401601536);
34188 mas_reset(&mas);
34201 mas_reset(&mas);
34214 mas_reset(&mas);
34223 mas_reset(&mas);
34235 * mmap: mas.min 94133881868288 max 140582961786879 mas.last 140582961786879
34236 * mmap: mas.index 140582827569152 align mask 0 offset 0
34243 mas_reset(&mas);
34247 mas_empty_area_rev(&mas, 4096, 140583656296448, 134217728);
34248 MT_BUG_ON(mt, mas.last != 140583003750399);
34258 mas_reset(&mas);
34268 mas_reset(&mas);
34278 mas_reset(&mas);
34286 mas_reset(&mas);
34294 mas_reset(&mas);
34302 mas_reset(&mas);
34309 mas_reset(&mas);
34316 mas_reset(&mas);
34325 mas_reset(&mas);
34329 mas_empty_area_rev(&mas, 4096, 4052029440, 28672);
34330 MT_BUG_ON(mt, mas.last != 4041211903);
34337 mas_reset(&mas);
34382 MA_STATE(mas, test->mt, 0, 0);
34391 mas_set(&mas, test->index[index]);
34392 mas_for_each(&mas, entry, test->last[index + 9]) {
34404 if (mas.index == alt_start) {
34419 if (mas.index == r_start) {
34422 } else if (mas.index == alt_start) {
34430 RCU_MT_BUG_ON(test, mas.index != r_start);
34431 RCU_MT_BUG_ON(test, mas.last != r_end);
34447 printk("!!%lu-%lu -> %p not %p or %p\n", mas.index, mas.last, entry, expected, alt);
34470 printk("!!%lu-%lu -> %p not %p\n", mas.index, mas.last, entry, expected);
34492 MA_STATE(mas, test->mt, 0, 0);
34502 mas_set(&mas, test->index[index + i]);
34510 entry = mas_prev(&mas, test->index[index]);
34517 if (mas.index == alt_start) {
34533 if (mas.index == r_start) {
34537 } else if (mas.index == alt_start) {
34551 if (mas.index != r_start) {
34556 mas.index, mas.last, entry,
34560 RCU_MT_BUG_ON(test, mas.index != r_start);
34561 RCU_MT_BUG_ON(test, mas.last != r_end);
34596 mas.index, mas.last, entry,
34604 printk("%lu-%lu %p != %p\n", mas.index,
34605 mas.last, entry, expected);
34921 MA_STATE(mas, test->mt, test->range_start, test->range_start);
34932 mas_for_each(&mas, entry, test->range_end) {
34934 expected = xa_mk_value(mas.index ? mas.index / 10 : 0);
34937 if (mas.index < test->index || mas.index > test->last) {
34940 mas.index, mas.last, entry, expected);
34955 mas_set(&mas, test->range_start);
34998 MA_STATE(mas, test->mt, test->index, test->index);
35004 mas_walk(&mas);
35006 RCU_MT_BUG_ON(test, (test->index - mas.index) !=
35007 (mas.last - test->last));
35364 static void mas_dfs_preorder(struct ma_state *mas)
35371 if (mas->status == ma_start) {
35372 mas_start(mas);
35376 if (mte_is_leaf(mas->node) && mte_is_root(mas->node))
35380 end = mas_data_end(mas);
35381 if (mte_is_leaf(mas->node) ||
35383 if (mte_is_root(mas->node))
35386 slot = mte_parent_slot(mas->node) + 1;
35387 mas_ascend(mas);
35391 prev = mas->node;
35392 mas->node = mas_get_slot(mas, slot);
35393 if (!mas->node || slot > end) {
35397 mas->node = prev;
35398 slot = mte_parent_slot(mas->node) + 1;
35399 mas_ascend(mas);
35403 mas->max = mas_safe_pivot(mas, pivots, slot, mte_node_type(prev));
35404 mas->min = mas_safe_min(mas, pivots, slot);
35408 mas->status = ma_none;
35416 MA_STATE(mas, mt, 0, 0);
35426 mas_dfs_preorder(&mas);
35427 } while (!mas_is_none(&mas));
35432 mas_reset(&mas);
35440 mas_dfs_preorder(&mas);
35441 } while (!mas_is_none(&mas));
35447 mas_reset(&mas);
35452 mas_dfs_preorder(&mas);
35453 } while (!mas_is_none(&mas));
35459 mas_reset(&mas);
35462 mas_expected_entries(&mas, max);
35464 mas.index = mas.last = count;
35465 mas_store(&mas, xa_mk_value(count));
35466 MT_BUG_ON(mt, mas_is_err(&mas));
35468 mas_destroy(&mas);
35482 struct ma_state *mas = wr_mas->mas;
35491 mas_reset(mas);
35492 mas_start(mas);
35493 if (!xa_is_node(mas_root(mas)))
35496 type = mte_node_type(mas->node);
35499 mas_node_walk(mas, mte_to_node(mas->node), type, &min, &max);
35500 offset = mas->offset;
35501 mas->end = mas_data_end(mas);
35502 pivots = ma_pivots(mte_to_node(mas->node), type);
35506 min = pivots[mas->offset - 1];
35507 if (offset < mas->end)
35508 max = pivots[mas->offset];
35510 wr_mas->r_max = offset < mas->end ? pivots[offset] : mas->max;
35516 if (mas->end < mt_slot_count(mas->node) - 1)
35517 vacant_height = mas->depth + 1;
35519 mas_descend(mas);
35520 type = mte_node_type(mas->node);
35521 mas->depth++;
35536 MA_STATE(mas, mt, 10, 20);
35537 MA_WR_STATE(wr_mas, &mas, ptr);
35544 mas_set_range(&mas, 470, 500);
35545 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35546 allocated = mas_allocated(&mas);
35547 height = mas_mt_height(&mas);
35551 mas_destroy(&mas);
35552 allocated = mas_allocated(&mas);
35555 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35556 allocated = mas_allocated(&mas);
35557 height = mas_mt_height(&mas);
35561 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35562 mas_destroy(&mas);
35563 allocated = mas_allocated(&mas);
35567 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35568 allocated = mas_allocated(&mas);
35569 height = mas_mt_height(&mas);
35572 mn = mas_pop_node(&mas);
35573 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
35576 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35577 mas_destroy(&mas);
35578 allocated = mas_allocated(&mas);
35581 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35582 allocated = mas_allocated(&mas);
35583 height = mas_mt_height(&mas);
35586 mn = mas_pop_node(&mas);
35587 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
35588 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35589 mas_destroy(&mas);
35590 allocated = mas_allocated(&mas);
35595 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35596 allocated = mas_allocated(&mas);
35597 height = mas_mt_height(&mas);
35600 mn = mas_pop_node(&mas);
35601 MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
35602 mas_push_node(&mas, mn);
35603 MT_BUG_ON(mt, mas_allocated(&mas) != allocated);
35604 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35605 mas_destroy(&mas);
35606 allocated = mas_allocated(&mas);
35609 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35610 allocated = mas_allocated(&mas);
35611 height = mas_mt_height(&mas);
35614 mas_store_prealloc(&mas, ptr);
35615 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
35618 mas_set_range(&mas, 6, 9);
35619 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35620 allocated = mas_allocated(&mas);
35622 mas_store_prealloc(&mas, ptr);
35623 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
35625 mas_set_range(&mas, 6, 10);
35626 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35627 allocated = mas_allocated(&mas);
35628 height = mas_mt_height(&mas);
35630 mas_store_prealloc(&mas, ptr);
35631 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
35634 mas_set_range(&mas, 54, 54);
35635 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35636 allocated = mas_allocated(&mas);
35637 height = mas_mt_height(&mas);
35640 mas_store_prealloc(&mas, ptr);
35641 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
35644 mas_set_range(&mas, 1, 100);
35645 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
35646 allocated = mas_allocated(&mas);
35647 height = mas_mt_height(&mas);
35649 mas_destroy(&mas);
35653 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35654 allocated = mas_allocated(&mas);
35655 height = mas_mt_height(&mas);
35664 mas_store_prealloc(&mas, ptr);
35665 MT_BUG_ON(mt, mas_allocated(&mas) != 0);
35666 mas_set_range(&mas, 0, 200);
35668 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
35669 allocated = mas_allocated(&mas);
35670 height = mas_mt_height(&mas);
35675 mas_set_range(&mas, 800, 805); /* Slot store, should be 0 allocations */
35676 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35677 allocated = mas_allocated(&mas);
35679 mas.last = 809; /* Node store */
35680 MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
35681 allocated = mas_allocated(&mas);
35683 mas_store_prealloc(&mas, ptr);
35691 MA_STATE(mas, mt, 1200, 2380);
35697 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35698 mas_set(&mas, 1205);
35699 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35707 mas_set_range(&mas, 9, 50006); /* Will expand to 0 - ULONG_MAX */
35708 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35709 mas_set(&mas, 1205);
35710 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35720 mas_set_range(&mas, 0, 12900); /* Spans more than 2 levels */
35722 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35723 mas_set(&mas, 1205);
35724 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35733 mas_set_range(&mas, 0, 300);
35735 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35736 mas_set(&mas, 15);
35737 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35746 mas_set_range(&mas, 0, 12865);
35748 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35749 mas_set(&mas, 15);
35750 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35759 mas_set_range(&mas, 90, 13665);
35761 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35762 mas_set(&mas, 95);
35763 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35772 mas_set_range(&mas, 46805, 49995);
35774 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35775 mas_set(&mas, 46815);
35776 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35788 mas_set_range(&mas, 32395, 49995);
35790 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35791 mas_set(&mas, 46815);
35792 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35803 mas_set_range(&mas, 38875, 43190);
35805 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35806 mas_set(&mas, 38900);
35807 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35816 mas_set(&mas, 47606);
35817 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL);
35818 mas_set(&mas, 47607);
35819 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL);
35820 mas_set(&mas, 47608);
35821 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL);
35822 mas_set(&mas, 47609);
35823 mas_store_gfp(&mas, check_spanning_write, GFP_KERNEL);
35825 mas_ascend(&mas);
35826 MT_BUG_ON(mt, (mas_data_end(&mas)) != mt_slot_count(mas.node) - 1);
35827 mas_set_range(&mas, 11516, 48940);
35828 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35836 mas_set_range(&mas, 43200, 49999);
35838 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35839 mas_set(&mas, 43200);
35840 MT_BUG_ON(mt, mas_walk(&mas) != NULL);
35849 mas_set_range(&mas, 76, 875);
35850 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35860 MA_STATE(mas, mt, 959, 959);
35865 mas_lock(&mas);
35866 mas_walk(&mas);
35867 data_end = mas_data_end(&mas);
35868 mas_set_range(&mas, 959, 963);
35869 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35871 MT_BUG_ON(mt, data_end != mas_data_end(&mas));
35874 mas_set(&mas, 880);
35875 mas_walk(&mas);
35876 data_end = mas_data_end(&mas);
35877 mas_set_range(&mas, 884, 887);
35878 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35882 MT_BUG_ON(mt, data_end != mas_data_end(&mas));
35886 mas_set(&mas, 890);
35887 mas_walk(&mas);
35888 data_end = mas_data_end(&mas);
35889 mas_set_range(&mas, 900, 905);
35890 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35896 MT_BUG_ON(mt, data_end - 2 != mas_data_end(&mas));
35900 mas_set(&mas, 800);
35901 mas_walk(&mas);
35902 data_end = mas_data_end(&mas);
35903 mas_set_range(&mas, 810, 825);
35904 mas_store_gfp(&mas, NULL, GFP_KERNEL);
35910 MT_BUG_ON(mt, data_end - 4 != mas_data_end(&mas));
35912 mas_unlock(&mas);
36077 pr_err("mas->min, mas->max do not match.\n");
36096 static __init void mas_subtree_max_range(struct ma_state *mas)
36098 unsigned long limit = mas->max;
36099 MA_STATE(newmas, mas->tree, 0, 0);
36102 mas_for_each(mas, entry, limit) {
36103 if (mas->last - mas->index >=
36105 newmas = *mas;
36109 *mas = newmas;
36125 MA_STATE(mas, mt, 0, 0);
36136 mas_set(&mas, 0);
36138 mas.max = ULONG_MAX;
36143 mas_dfs_preorder(&mas);
36144 if (mas_is_none(&mas))
36147 type = mte_node_type(mas.node);
36148 if (mas_data_end(&mas) + 1 < mt_slots[type]) {
36149 mas_set(&mas, mas.min);
36154 mas_subtree_max_range(&mas);
36155 step = mas.last - mas.index;
36162 mas.last = mas.index + step;
36163 mas_store_gfp(&mas, xa_mk_value(5),
36330 MA_STATE(mas, mt, 0, 0);
36331 mas_lock(&mas);
36333 mas_store_gfp(&mas, xa_mk_value(index), GFP_KERNEL);
36334 mas_set(&mas, ++index);
36336 mas_set_range(&mas, 90, 140);
36337 mas_store_gfp(&mas, xa_mk_value(index), GFP_KERNEL);
36338 MT_BUG_ON(mt, mas_mt_height(&mas) != 2);
36339 mas_unlock(&mas);
36350 MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX);
36360 mas_erase(&mas);
36361 } while (mas_prev(&mas, 0) != NULL);
36370 MA_STATE(mas, mt, 6, 10);
36372 mtree_lock(mas.tree);
36373 mas_store(&mas, xa_mk_value(0xC));
36374 mas_destroy(&mas);
36375 mtree_unlock(mas.tree);
36389 MA_STATE(mas, mt, 0, 5);
36403 mas_erase(&mas);
36413 mas_set_range(&mas, 0, 5);
36415 mas_store_gfp(&mas, NULL, GFP_KERNEL);
36431 MA_STATE(mas, mt, 0, 0);
36435 __mas_set_range(&mas, 0x7fffffffe000, 0x7ffffffff000 - 1);
36436 mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL);
36437 mas_store_prealloc(&mas, xa_mk_value(1));
36440 mas_prev_range(&mas, 0);
36442 __mas_set_range(&mas, 0x7ffde4ca1000, 0x7ffffffff000 - 1);
36443 mas_preallocate(&mas, xa_mk_value(1), GFP_KERNEL);
36444 mas_store_prealloc(&mas, xa_mk_value(1));
36447 __mas_set_range(&mas, 0x7ffde4ca2000, 0x7ffffffff000 - 1);
36448 mas_preallocate(&mas, NULL, GFP_KERNEL);
36449 mas_store_prealloc(&mas, NULL);
36452 mas_destroy(&mas);
36463 MA_STATE(mas, mt, ULONG_MAX, ULONG_MAX);
36471 mas_expected_entries(&mas, max);
36472 mas_erase(&mas);
36473 MT_BUG_ON(mt, mas.store_type == wr_rebalance);
36474 } while (mas_prev(&mas, 0) != NULL);
36476 mas_destroy(&mas);
36580 static unsigned long get_last_index(struct ma_state *mas)
36582 struct maple_node *node = mas_mn(mas);
36583 enum maple_type mt = mte_node_type(mas->node);
36585 unsigned long last_index = mas_data_end(mas);
36600 MA_STATE(mas, &tree, 0, 0);
36610 mas_reset(&mas);
36611 mas_start(&mas);
36612 mas_descend(&mas);
36613 mas_descend(&mas);
36635 unsigned long tmp = get_last_index(&mas);
36637 if (mas_next_sibling(&mas)) {
36639 to = mas.max;
36648 mas_set_range(&mas, from, to);
36649 mas_store_gfp(&mas, xa_mk_value(0xdead), GFP_KERNEL);