From e80ceb449737ba57547e153e81ef4dd6ac1b5ae6 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 30 Jun 2020 21:32:52 -0400 Subject: [PATCH] maple_tree: wip. Combine mas_extend_null in mas_store and mas_spanning_store. Pass: 13130626 Run:13130627 Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 162 ++++++++++++++++++++++-------------------- lib/test_maple_tree.c | 3 +- 2 files changed, 88 insertions(+), 77 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f069560b9945..962058aeffad 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1128,8 +1128,11 @@ static inline unsigned char _mas_data_end(const struct ma_state *mas, { int slot = 0; unsigned long piv = mas->min, prev_piv = mas->min; + //printk("starting %lu %lu\n", piv, prev_piv); + //printk(" min %lu max %lu\n", mas->min, mas->max); for (; slot < mt_slot_count(mas->node); slot++) { piv = _mas_get_safe_pivot(mas, slot, type); + //printk(" %u %lu\n", slot, piv); if (piv >= mas->max) break; @@ -1432,6 +1435,7 @@ static inline void _mas_replace(struct ma_state *mas, bool free, bool push, if (mte_is_root(mas->node)) { printk("It's root\n"); + printk("New height will be %d\n", mas->depth); prev = mas->tree->ma_root; } else { enum maple_type ptype = mas_parent_enum(mas, mas->node); @@ -1512,20 +1516,22 @@ static inline struct maple_enode *mas_check_split_parent(struct ma_state *mas, if (mte_parent(entry) != mas_mn(mas)) return NULL; + mas_set_slot(mas, slot); return entry; } static inline struct maple_enode *mas_find_l_split(struct ma_state *mas) { unsigned char i, end = mas_data_end(mas); - struct maple_enode *en; + printk("data end of %p was %u\n", mas_mn(mas), end); + struct maple_enode *en = NULL; for (i = 0; i <= end; i++) { printk("%s: Checking %p[%i]\n", __func__, mas_mn(mas), i); if ((en = mas_check_split_parent(mas, i))) - return en; + break; } - return NULL; + return en; } static inline struct maple_enode *mas_find_r_split(struct ma_state *mas) @@ -1667,10 +1673,10 @@ static inline void mas_descend_adopt(struct ma_state *mas) * then set the correct parent in all of of the parent's children. */ while (!mte_is_leaf(l_mas.node)) { - //printk("start of l %p is %p\n", mas_mn(&l_mas), l_mas.node); - //printk("start of r %p is %p\n", mas_mn(&r_mas), r_mas.node); + printk("start of l %p is %p\n", mas_mn(&l_mas), l_mas.node); + printk("start of r %p is %p\n", mas_mn(&r_mas), r_mas.node); if (!(l_enode = mas_find_l_split(&l_mas))) { - //printk("\tChecking right\n"); + printk("\tChecking right\n"); mas_adopt_children(&l_mas, l_mas.node); mas_dup_state(&l_mas, &r_mas); if (!(l_enode = mas_find_l_split(&l_mas))) { @@ -1679,28 +1685,28 @@ static inline void mas_descend_adopt(struct ma_state *mas) } } - //printk("%d New node is %p\n", __LINE__, mte_to_node(l_enode)); + printk("%d New node is %p\n", __LINE__, mte_to_node(l_enode)); if (!(r_enode = mas_find_r_split(&r_mas))) { - //printk("\tChecking left\n"); + printk("\tChecking left\n"); mas_adopt_children(&r_mas, r_mas.node); mas_dup_state(&r_mas, &l_mas); r_enode = mas_find_r_split(&r_mas); } - //printk("%d New node is %p\n", __LINE__, mte_to_node(r_enode)); + printk("%d New node is %p\n", __LINE__, mte_to_node(r_enode)); - //printk("Adopt children of l %p\n", mas_mn(&l_mas)); + printk("Adopt children of l %p\n", mas_mn(&l_mas)); mas_adopt_children(&l_mas, l_mas.node); if (r_mas.node != l_mas.node) { - //printk("Adopt children of r %p\n", mas_mn(&r_mas)); + printk("Adopt children of r %p\n", mas_mn(&r_mas)); mas_adopt_children(&r_mas, r_mas.node); } - l_mas.node = l_enode; - r_mas.node = r_enode; + mas_descend(&l_mas); + mas_descend(&r_mas); - //printk("%d New node is %p\n", __LINE__, mas_mn(&l_mas)); - //printk("%d New node is %p\n", __LINE__, mas_mn(&r_mas)); - //printk("\n"); + printk("%d New node is %p\n", __LINE__, mas_mn(&l_mas)); + printk("%d New node is %p\n", __LINE__, mas_mn(&r_mas)); + printk("\n"); } } @@ -2049,7 +2055,6 @@ static inline int mas_combine_separate(struct ma_state *mas, printk("%s: %d New root? %u\n", __func__, __LINE__, b_end); mas_dup_state(orig_l_mas, orig_r_mas); - mas->depth = orig_l_mas->depth; b_end--; break; } @@ -2075,6 +2080,7 @@ static inline int mas_combine_separate(struct ma_state *mas, l_mas.node = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), mte_node_type(orig_l_mas->node)); + orig_l_mas->depth++; printk("All done making replacement at %p\n", mas_mn(&l_mas)); mab_mas_cp(b_node, 0, b_end, &l_mas, 0); @@ -2096,6 +2102,7 @@ static inline int mas_combine_separate(struct ma_state *mas, } orig_l_mas->node = l_mas.node; + mas->depth = orig_l_mas->depth; return b_end; } @@ -2152,7 +2159,7 @@ new_root_node: // Set up mas for insertion. mas_set_node_dead(mas); - mas->node = l_mas.node; + mas_dup_state(mas, &l_mas); smp_wmb(); // FIXME: Mark modified nodes as dead. @@ -2227,6 +2234,7 @@ static inline int mas_split(struct ma_state *mas, type = maple_arange_64; else type = maple_range_64; + mas->depth = height; } /* Only a single node is used here, could be root. * Big_node should just fit in a single node. @@ -2392,7 +2400,7 @@ static inline int mas_split(struct ma_state *mas, if (mt_is_alloc(mas->tree)) mas_update_gap(mas, false); - mt_dump(mas->tree); + //mt_dump(mas->tree); printk("Start at %p\n", mas_mn(mas)); mas_descend_adopt(mas); return 1; @@ -2714,7 +2722,51 @@ static inline void mas_move_slot(struct ma_state *mas, unsigned char slot, mas_zero_to_end(mas, slot); } +static inline unsigned char mas_extend_null( struct ma_state *l_mas, + struct ma_state *r_mas) +{ + unsigned char l_slot = mas_get_slot(l_mas); + unsigned char r_slot = mas_get_slot(r_mas); + unsigned char cp_r_slot = r_slot; + void *content = mas_get_rcu_slot(l_mas, l_slot); + unsigned long range_max = mas_get_safe_pivot(r_mas, r_slot); + unsigned long range_min = l_mas->min; + + if (l_slot) + range_min = mas_get_safe_pivot(l_mas, l_slot - 1) + 1; + + if (!content) + l_mas->index = range_min; + + if ((l_mas->index == range_min) && + l_slot && !mas_get_rcu_slot(l_mas, l_slot - 1)) { + if (l_slot > 1) + l_mas->index = mas_get_safe_pivot(l_mas, l_slot - 2) + 1; + else + l_mas->index = l_mas->min; + mas_set_slot(l_mas, l_slot - 1); + } + + if (!mas_get_rcu_slot(r_mas, r_slot)) { + if (r_mas->last < range_max) + r_mas->last = range_max; + cp_r_slot++; + } + + if (r_mas->last == range_max && + r_mas->last < r_mas->max && !mas_get_rcu_slot(r_mas, r_slot + 1)) { + r_mas->last = mas_get_safe_pivot(r_mas, r_slot + 1); + cp_r_slot++; + } + + if (r_slot && !r_mas->last) + r_mas->last = r_mas->max; + + if (l_mas != r_mas) + mas_set_slot(r_mas, cp_r_slot); + return r_slot; +} static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, unsigned long *range_max); /* Private @@ -2729,7 +2781,6 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) { unsigned long range_min, range_max; unsigned char b_end = 0; // big_node end. - unsigned char l_slot, r_slot; unsigned char count = 0; struct maple_big_node b_node; int node_cnt = 0; @@ -2767,43 +2818,18 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) mas_set_slot(&r_mas, 0); __mas_walk(&r_mas, &range_min, &range_max); r_mas.last = r_mas.index = mas->last; - r_slot = mas_get_slot(&r_mas); - printk("r_slot is %u\n", r_slot); - - if (!entry) { - /* Check if there is a null in the next slot on the right */ - if (!mas_get_rcu_slot(&r_mas, r_slot)) { - mas->last = mas_get_safe_pivot(&r_mas, r_slot); - if (!mas->last) - mas->last = mas->max; - r_slot++; - } - if (range_max == r_mas.max) - printk("NULL could be in the next node?\n"); - } - r_mas.last = r_mas.index = mas->last; - mas_set_slot(&r_mas, r_slot); + mt_dump(mas->tree); // Set up left side. mas_set_slot(&l_mas, 0); __mas_walk(&l_mas, &range_min, &range_max); - l_slot = mas_get_slot(&l_mas); + if (!entry) { - /* Check if there is a null in the previous slot on the left */ - if (!l_slot) { - mas->index = mas->min; - } else if (!mas_get_rcu_slot(&l_mas, l_slot - 1)) { - if (l_slot > 1) - mas->index = mte_get_pivot(l_mas.node, l_slot - 2) + 1; - else - mas->index = mas->min; - l_slot--; - } + mas_extend_null(&l_mas, &r_mas); + mas->index = l_mas.index; + mas->last = l_mas.last = r_mas.index = r_mas.last; + mas_set_slot(mas, mas_get_slot(&l_mas)); } - l_mas.last = mas->last; - l_mas.index = mas->index; - mas_set_slot(&l_mas, l_slot); - printk("%s: final range is %lu-%lu at slot %u\n", __func__, mas->index, mas->last, mas_get_slot(&l_mas)); @@ -2811,7 +2837,7 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) // Copy l_mas and store the value in b_node. b_end = mas_store_b_node(&l_mas, &b_node, entry); // Copy r_mas into b_node. - b_end = mas_mab_cp(&r_mas, r_slot, mas_data_end(&r_mas), + b_end = mas_mab_cp(&r_mas, mas_get_slot(&r_mas), mas_data_end(&r_mas), &b_node, b_end + 1); // Stop spanning searches by searching for just index. l_mas.index = l_mas.last = mas->index; @@ -2834,7 +2860,7 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) // Set up mas for insertion. mas_set_node_dead(mas); - mas->node = l_mas.node; + mas_dup_state(mas, &l_mas); smp_wmb(); // FIXME: Mark modified nodes as dead. @@ -2847,7 +2873,7 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) if (mte_is_leaf(mas->node)) return 1; - mt_dump(mas->tree); + //mt_dump(mas->tree); mas_descend_adopt(mas); @@ -2873,7 +2899,7 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite printk("\nStart: %s %d store %lu-%lu %p\n", __func__, __LINE__, mas->index, mas->last, entry); - mt_dump(mas->tree); + //mt_dump(mas->tree); if (mas_start(mas) || (mas_is_none(mas) || mas->node == MAS_ROOT)) ret = ma_root_ptr(mas, entry, content, overwrite); @@ -2914,27 +2940,11 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite } /* Expand store of NULL, if necessary */ + if (!entry) { - if (!content) { - mas->index = r_min; - if (mas->last < r_max) - mas->last = r_max; - } - if ((r_max != mas->max) && !mas_get_rcu_slot(mas, slot + 1)) { - printk("rcu slot %u is %p\n", slot + 1, mas_get_rcu_slot(mas, slot+1)); - mas->last = mas_get_safe_pivot(mas, slot + 1); - if (!mas->last) - mas->last = mas->max; - r_max = mas->last; - } - if (slot && !mas_get_rcu_slot(mas, slot - 1)) { - if (slot > 1) - mas->index = mte_get_pivot(mas->node, slot - 2) + 1; - else - mas->index = mas->min; - r_min = mas->index; - mas_set_slot(mas, --slot); - } + mt_dump(mas->tree); + mas_extend_null(mas, mas); + slot = mas_get_slot(mas); printk("store is now %lu-%lu at slot %u\n", mas->index, mas->last, mas_get_slot(mas)); } @@ -2978,7 +2988,7 @@ done: return NULL; - mt_dump(mas->tree); + //mt_dump(mas->tree); return content; } void *mas_store(struct ma_state *mas, void *entry) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index da4b81fe9d54..92011b3fe462 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -29686,6 +29686,7 @@ ERASE, 140612699410432, 140612707799039, void *ptr = NULL; MA_STATE(mas, mt, 0, 0); +// goto skip; mt_set_non_kernel(3); check_erase2_testset(mt, set, ARRAY_SIZE(set)); mtree_destroy(mt); @@ -29774,7 +29775,7 @@ ERASE, 140612699410432, 140612707799039, mas_get_unmapped_area_rev(&mas, 0, 140373518663680, 4096); rcu_read_unlock(); mtree_destroy(mt); - +//skip: mtree_init(mt, MAPLE_ALLOC_RANGE); check_erase2_testset(mt, set14, ARRAY_SIZE(set14)); rcu_barrier(); -- 2.50.1