From 0578c2bb94ce443530e3d54b0d9e97613a44802f Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 14 Jan 2020 11:22:21 -0500 Subject: [PATCH] maple_tree: cleanup Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 348 +++++------------------------------------------ 1 file changed, 34 insertions(+), 314 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 367fc5b0cccb..19946237dd87 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -827,8 +827,6 @@ static inline void mas_ascend(struct ma_state *mas) unsigned long max = 0, min = ULONG_MAX; bool set_max = false, set_min = false; - //mt_dump(mas->tree); - //printk("ascending from %p\n", mas_mn(mas)); p_enode = mt_mk_node(mte_parent(mas->node), mas_parent_enum(mas, mas->node)); @@ -841,7 +839,6 @@ static inline void mas_ascend(struct ma_state *mas) if (mte_is_root(a_enode)) { a_node = mte_to_node(a_enode); - //printk("parent is root\n"); goto no_parent; } @@ -852,24 +849,18 @@ ascend: a_slot = mte_parent_slot(mas->node); a_enode = mt_mk_node(a_node, a_type); - //printk("a_slot = %u %s %s %u\n", a_slot, set_min ? "yes" : "no", - // set_max ? "yes" : "no", mt_pivots[a_type]); if (!set_min && a_slot) { set_min = true; min = mte_get_pivot(a_enode, a_slot - 1) + 1; - //printk("Using min from %p[%u] %lu\n", a_node, a_slot-1, min); } if (!set_max && a_slot < mt_pivots[a_type]) { set_max = true; - //printk("Getting pivot %u from %p\n", a_slot, a_enode); max = mte_get_pivot(a_enode, a_slot); - //printk("Using max from %p[%u] %lu\n", a_node, a_slot, max); } no_parent: if (_ma_is_root(a_node)) { - //printk("%s: hit root %p\n", __func__, a_node); if (!set_min) min = 0; if (!set_max) @@ -884,7 +875,6 @@ no_parent: mas->max = max; mas->min = min; mas->node = p_enode; - //printk("%p %lu-%lu\n", mas_mn(mas), mas->min, mas->max); return; } @@ -930,7 +920,6 @@ static inline struct maple_node *mas_next_alloc(struct ma_state *ms) return NULL; cnt = mas_get_alloc_cnt(ms); -// printk("%s: TAKE %d\n", __func__, cnt); mn = mas_get_alloc(ms); if (cnt == 1) { ms->alloc = NULL; @@ -954,10 +943,8 @@ static inline void mas_push_node(struct ma_state *mas, struct maple_enode *used) struct maple_node *node = mas_get_alloc(mas); int cnt; -// printk("%s: PUSH %p\n", __func__, used); memset(reuse, 0, sizeof(*reuse)); cnt = mas_get_alloc_cnt(mas); -// printk("%s: cnt %d\n", __func__, cnt); if (cnt == 0) { mas->alloc = reuse; } else if (cnt <= 15) { @@ -971,7 +958,6 @@ static inline void mas_push_node(struct ma_state *mas, struct maple_enode *used) smn->slot[cnt % 15] = reuse; } cnt = mas_get_alloc_cnt(mas); -// printk("%s: cnt %d\n", __func__, cnt); BUG_ON(!mas_get_alloc_cnt(mas)); } @@ -1157,8 +1143,6 @@ static inline unsigned char mas_data_end(const struct ma_state *mas, (*coalesce) = 0; break; } -// printk("data end with counted nulls %p\n", mas_mn(mas)); -// printk("%u %u %u\n", slot, (*coalesce), counted_null); (*coalesce) = (*coalesce) - counted_null + 1; slot -= counted_null; } @@ -1180,15 +1164,12 @@ static inline unsigned char mas_data_end(const struct ma_state *mas, counted_null = 0; } - if (piv == mas->max) { -// printk("max hit %lu\n", mas->max); + if (piv == mas->max) break; - } prev_piv = piv; } -// printk("last piv %lu slot %u coalesce %u\n", piv, slot, *coalesce); *last_piv = piv; return slot; } @@ -1214,7 +1195,6 @@ static inline struct maple_node *mas_switch_nodes(struct ma_state *cp, unsigned long piv) { left->max = piv; -// printk("going to use %lu as max\n", left->max); right->min = piv + 1; mas_dup_state(cp, right); return mas_mn(right); @@ -1224,15 +1204,12 @@ static inline void mas_ma_cp_store(struct maple_node *mn, enum maple_type type, unsigned char slot, unsigned long piv, void *entry, bool flush) { - printk("%s: set %p[%u] -> %p\n", __func__, mn, slot, entry); ma_set_rcu_slot(mn, slot, type, entry); if (flush) wmb(); // data needs to exist before pivot for readers - if (slot < mt_pivots[type]) { - printk("%s: set %p[%u] piv %lu\n", __func__, mn, slot, piv); + if (slot < mt_pivots[type]) ma_set_pivot(mn, slot, type, piv); - } } static inline unsigned char mas_cp_calc_split(struct ma_state *mas, @@ -1243,12 +1220,12 @@ static inline unsigned char mas_cp_calc_split(struct ma_state *mas, unsigned long range = mas->max - mas->min; unsigned long half; unsigned long piv = 0; - if (mas_type == maple_arange_64) { + if (mas_type == maple_arange_64) max = 3; - printk("arange split\n"); - } + if (mas->min == 0) max = 7; + half = max / 2; if (ma_is_leaf(mas_type)) { if (range <= 8) @@ -1271,13 +1248,12 @@ static inline unsigned char mas_cp_calc_split(struct ma_state *mas, } } else - return half; + return half; done: if (ret < max && (append || piv == ULONG_MAX)) ret++; return ret; - } static inline unsigned long mas_leaf_max_gap(struct ma_state *mas); static inline void mas_ma_update_gap(struct ma_state *mas, @@ -1287,7 +1263,6 @@ static inline void mas_ma_update_gap(struct ma_state *mas, unsigned char slot, unsigned long *max_gap, void *loop_entry) { unsigned long gap = piv - written_piv; - printk("%s\n", __func__); if (!ma_is_leaf(mn_type)) {// non-leaf have gaps already. gap = ma_get_gap(mas_mn(mas), src_slot, mas_type); @@ -1297,7 +1272,6 @@ static inline void mas_ma_update_gap(struct ma_state *mas, if (gap > (*max_gap)) (*max_gap) = gap; - printk("\tCalc gap %lu max %lu\n", gap, *max_gap); } /* @@ -1349,6 +1323,7 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, mas->min, }; + MA_STATE(cp, mas->tree, mas->index, mas->last); if (dst_start) @@ -1358,10 +1333,8 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, attempt_insert = true; - if (right) { + if (right) split = mas_cp_calc_split(mas, mas_type, append); - printk("Using split of %d\n", split); - } if (left) { mas_dup_state(&cp, left); @@ -1372,7 +1345,6 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, mn_type = mte_node_type(cp.node); p_slot = mte_parent_slot(left->node); parent = mte_parent(left->node); - printk("parent %p of %p\n", parent, mas->node); mas_type = mas_parent_enum(mas, left->node); } @@ -1380,8 +1352,6 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, piv[2] = mas->max; if (append) { // start at a given slot, so append there. - printk("append\n"); - //mt_dump(mas->tree); mas_dup_state(&cp, mas); src_slot = entry_cnt; slot = dst_start; @@ -1393,9 +1363,7 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, if (slot) written_piv = ma_get_pivot(mn, slot, mn_type); - printk("slot %u written %lu src_slot %u\n", slot, written_piv, src_slot); if (mn == mas_mn(&cp)) { // src and dst are the same. - printk("src == dst\n"); if (existing || (!slot && written_piv < cp.index)) { src_slot++; slot++; @@ -1405,15 +1373,11 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, } else if (existing && written_piv != cp.index) { slot++; entry_cnt = -1; - printk("Existing\n"); } else { src_slot++; entry_cnt = 0; } - - printk("slot %u written %lu src_slot %u\n", slot, written_piv, src_slot); - appending = true; prev_piv = written_piv; attempt_insert = true; @@ -1421,14 +1385,11 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, max_gap = mas_leaf_max_gap(mas); } - printk("slot is %u\n", slot); do { int i = 2; // Default to just writing the pivot. int j = 3; // Loop limit. - printk("src slot %u entry_cnt %d slot %u\n", src_slot, entry_cnt, slot); if (entry_cnt < 0) { - printk("Setting to appending mode\n"); appending = true; existing = NULL; piv[2] = mas->max; @@ -1437,27 +1398,22 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, if (!piv[2] && src_slot) piv[2] = mas->max; existing = mte_get_rcu_slot(mas->node, src_slot); - printk("getting %p[%u] (%lu->%p)\n", mas_mn(mas), - src_slot, piv[2], existing); } - - - if (!appending) { if (mt_will_coalesce(existing)) { - printk("coalesce\n"); if (prev_null) { - if (slot && slot - 1 < mt_pivots[mas_type]) { - printk("Overwrite piv %u\n", slot - 1); - ma_set_pivot(mn, slot - 1, mas_type, - piv[2]); + if (slot && + slot - 1 < mt_pivots[mas_type]) { + ma_set_pivot(mn, slot - 1, + mas_type, piv[2]); written_piv = piv[2]; } if (update_gaps) { - mas_ma_update_gap(mas, mas_type, mn, mn_type, - piv[2], written_piv, src_slot, - slot, &max_gap, NULL); + mas_ma_update_gap(mas, mas_type, + mn, mn_type, piv[2], + written_piv, src_slot, + slot, &max_gap, NULL); } } goto skip_src_slot; @@ -1474,19 +1430,16 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, if (ma_is_leaf(mn_type) && (append || (attempt_insert && cp.index <= piv[2]))) { i = 0; - printk("Written piv %lu\n", written_piv); if (written_piv == cp.index - 1) { i = 1; // previous pivot matches exactly. } else if (!src_slot && written_piv == cp.index) i = 1; - printk("piv2 %lu <= last %lu\n", piv[2], cp.last); if (appending) j--; else if (!appending && (piv[2] <= cp.last)) j--; // skip last pivot. - printk("piv array %u-%u\n", i, j); attempt_insert = false; } @@ -1495,11 +1448,6 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, void *loop_entry = existing; bool wmb = false; - if (!loop_entry && !ma_is_leaf(mn_type)) - { - printk("BUG Here\n"); - } - printk("write array %d %lu to %u entry_cnt %d\n", i, piv[i], slot, entry_cnt); if (i == 1) loop_entry = entry; @@ -1537,10 +1485,8 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, if ((right) && (cp.node != right->node) && (slot > split)) { ret = slot; - if (update_gaps) { - printk("Write gap %p[%u] -> %lu\n", parent, p_slot, max_gap); + if (update_gaps) parent->ma64.gap[p_slot] = max_gap; - } mn = mas_switch_nodes(&cp, left, right, piv[i]); @@ -1560,7 +1506,6 @@ skip_src_slot: else if (!right) ret = slot - 1; - printk("Done\n"); return ret; } @@ -1703,7 +1648,6 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) if (!pend && i) pend = mas->max; gap = pend - pstart + 1; - printk("%d gap %lu %lu-%lu\n", i, gap, pend, pstart); if (!mt_is_empty(mte_get_rcu_slot(mas->node, i))) goto next; @@ -1926,35 +1870,25 @@ static inline unsigned long _mas_copy(struct ma_state *mas, struct ma_cp *cp, dloc <= cp->dst_end) { void *entry; - printk("%u to %u\n", sloc, dloc); - if (prev_piv >= mas->max) { - printk("%d %u %lu >= %lu\n", __LINE__, sloc, prev_piv, mas->max); + if (prev_piv >= mas->max) break; - } - if (sloc < pivot_cnt) { + if (sloc < pivot_cnt) piv = mte_get_pivot(cp->src, sloc); - printk("%d\n", __LINE__); - } - else { - printk("%d\n", __LINE__); + else piv = mas->max; - } if (sloc && !piv) break; entry = mte_get_rcu_slot(cp->src, sloc); if (mt_will_coalesce(entry)) { - printk("%d\n", __LINE__); - printk("slot %u will coalesce\n", sloc); if (!sloc) { - printk("HERE!\n"); entry = NULL; if (dloc) { void *p_entry = mte_get_rcu_slot(cp->dst, - dloc - 1); + dloc - 1); if (!p_entry) { mte_set_pivot(cp->dst, dloc - 1, piv); @@ -1971,29 +1905,21 @@ static inline unsigned long _mas_copy(struct ma_state *mas, struct ma_cp *cp, // Last entry. if (dloc && (piv == mas->max || !piv)) { - printk("%d\n", __LINE__); if (!mte_get_rcu_slot(cp->dst, dloc -1) && - mt_is_empty(entry)) { + mt_is_empty(entry)) { mte_set_pivot(cp->dst, dloc -1, 0); - printk("%d\n", __LINE__); break; } } - if (piv < cp->start_piv) { - printk("start_piv ski\n"); + if (piv < cp->start_piv) goto next_src_slot; - } - if (sloc && piv == prev_piv) { - printk("skip slot\n"); + if (sloc && piv == prev_piv) goto next_src_slot; - } - if (dloc < pivot_cnt) { - printk("dloc\n"); + if (dloc < pivot_cnt) mte_set_pivot(cp->dst, dloc, piv); - } if (dtype == maple_arange_64) mte_cp_gap(cp->dst, dloc, cp->src, sloc); @@ -2046,8 +1972,6 @@ static inline void _mas_replace(struct ma_state *mas, bool free, bool push) struct maple_enode *prev; unsigned char slot = 0; - if (push) - printk("%s: PUSH\n", __func__); if (mte_is_root(mas->node)) { prev = mas->tree->ma_root; } else { @@ -2179,7 +2103,6 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, MA_STATE(left, mas->tree, mas->index, mas->last); MA_STATE(right , mas->tree, mas->index, mas->last); - printk("%s %p\n", __func__, mas_mn(mas)); type = mte_node_type(mas->node); if (mte_is_root(mas->node)) { old_parent = full; @@ -2196,9 +2119,6 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, mas_dup_state(&parent, mas); mas_ascend(&parent); old_parent = parent.node; - printk("%s mas %p parent %p max %lu\n", __func__, mas_mn(mas), - mas_mn(&parent), parent.max); - ptype = mte_node_type(parent.node); p_end = mas_data_end(&parent, ptype, &last_pivot, &coalesce); if (p_end - coalesce >= mt_slots[ptype] - 1) { @@ -2209,8 +2129,6 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, if (mas_is_err(mas)) return 0; - printk("Parent split returned\n"); - mt_dump(mas->tree); mas_dup_state(&parent, mas); if (split < p_slot) p_slot -= split; @@ -2219,20 +2137,12 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, mas_set_slot(&parent, p_slot); } ptype = mte_node_type(parent.node); - printk("end of node %p\n", mas_mn(&parent)); p_end = mas_data_end(&parent, ptype, &last_pivot, &coalesce); mas_dup_state(mas, &parent); mas_set_slot(mas, p_slot); - printk("%s mas %p parent %p max %lu\n", __func__, mas_mn(mas), - mas_mn(&parent), parent.max); mas_descend(mas); - printk("%s mas %p parent %p max %lu\n", __func__, mas_mn(mas), - mas_mn(&parent), parent.max); } - printk("%s mas %p parent %p max %lu\n", __func__, mas_mn(mas), - mas_mn(&parent), parent.max); - mas_node_cnt(mas, 3); if (mas_is_err(mas)) return 0; @@ -2269,7 +2179,6 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, cp.src_start = p_slot + 1; cp.src_end = p_end; cp.dst_start += skip; - printk("copy %p[%u-%u] up to %lu\n", mte_to_node(cp.src), cp.src_start,cp.src_end, right.max); _mas_copy(&parent, &cp, right.max); } } @@ -2291,7 +2200,6 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, mas_dup_state(mas, &parent); // Replace the parent node & free the old parent. - printk("%s replace in tree\n", __func__); _mas_replace(mas, active, true); if (mt_is_alloc(mas->tree) && !mte_is_root(mas->node)) { @@ -2318,7 +2226,6 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, // Free the full node, this may have happened in _mas_replace if (old_parent != full) { - printk("Push node %p %s\n", mas_mn(mas), active ? "no" : "yes"); if (!active) mas_push_node(mas, full); else @@ -2420,19 +2327,15 @@ static inline int _mas_add_slot_cnt(struct ma_state *mas, int req_slots = 0; end = mas_data_end(mas, mte_node_type(mas->node), &last_piv, &coalesce); - printk("end of %p %u %u %lu\n", mas_mn(mas), end, coalesce, last_piv); if (max == mas->max && min == mas->min) return end - coalesce; // overwriting a single entry. - if (min < mas->index) { + if (min < mas->index) req_slots++; //slot needed at start. - printk("slot at start\n"); - } if (max > mas->last) { req_slots++; // slot needed at end. - printk("slot at end %lu > %lu\n", max, mas->last); } else { // walk back through the slots until we get to the insert // slot checking where we fit. @@ -2445,24 +2348,16 @@ static inline int _mas_add_slot_cnt(struct ma_state *mas, break; end_slot--; } - printk("end slot = %u\n", end_slot); } - if (mte_is_dense(mas->node)) return req_slots; - do { - printk("last entry shit %d\n", end); last_entry = mte_get_rcu_slot(mas->node, end); } while (mt_will_coalesce(last_entry) && --end); - printk("End is now %d\n", end); req_slots = req_slots + end - coalesce; - - printk("req slots %d\n", req_slots); - // Check if it's safe to use the slot without a pivot. // max of the slot == max of the node. // max of the tree is being set. @@ -2473,7 +2368,6 @@ static inline int _mas_add_slot_cnt(struct ma_state *mas, if (!last_entry) // nothing at the last slot. return req_slots; - printk("req slots returned as %d\n", req_slots+1); return req_slots + 1; } static inline int __mas_add(struct ma_state *mas, void *entry, @@ -2488,14 +2382,13 @@ static inline int __mas_add(struct ma_state *mas, void *entry, MA_STATE(cp, mas->tree, mas->index, mas->last); if (append) { - printk("Appending.\n"); mn = mas_mn(mas); // Appending means writing to the source. } else if (active) { cp.node = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), mas_type); mn = mas_mn(&cp); } else { - printk("Inactive\n"); + memset(&space, 0, sizeof(struct maple_node)); mn = &space; cp.node = NULL; } @@ -2562,7 +2455,6 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, // Allocation failed, so rebuild the tree. } - printk("%s: here %d\n", __func__, __LINE__); old_end = mas_data_end(mas, this_type, &last_piv, &coalesce); if (slot > slot_cnt) // search returned MAPLE_NODE_SLOTS slot = old_end + 1; @@ -2571,31 +2463,24 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, if (mas_get_slot(mas) > slot_cnt) max = mas->max; - printk("Landed %p[%u] max %lu mas_max %lu\n", mas_mn(mas), mas_get_slot(mas), max, - mas->max); if (slot <= old_end) contents = mte_get_rcu_slot(mas->node, slot); - printk("%s: here %d\n", __func__, __LINE__); // Check early failures. if (!overwrite) { if (mas->last > max) { // spans range. - printk("%s: here %d %lu %lu\n", __func__, __LINE__, mas->last, max); mas_set_err(mas, -ERANGE); return 0; } if (!mt_is_empty(contents)) { - printk("%s: here %d\n", __func__, __LINE__); mas_set_err(mas, -EBUSY); return 0; } } - printk("%s: here %d\n", __func__, __LINE__); // At this point, the we can perform the add. // spans node means we will replace the tree. - printk("mas: l %lu max %lu\n", mas->last, mas->max); if (mas->last > mas->max) return mas_replace_tree(mas, entry); @@ -2605,7 +2490,6 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, // the tree. mas_reset(mas); mas_first_node(mas, ULONG_MAX); - printk("Using first node %p\n", mas_mn(mas)); return mas_replace_tree(mas, entry); } @@ -2617,11 +2501,7 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, ret = 1; goto complete; } - - printk("Adding %lu-%lu\n", mas->index, mas->last); new_end = _mas_add_slot_cnt(mas, slot, min, max) - coalesce; - printk("%s: %p new_end %u slot_cnt %u\n", __func__, mas_mn(mas), - new_end, slot_cnt); if (new_end > slot_cnt) { mas_split(mas, slot, active, old_end, entry); if (mas_is_err(mas)) { @@ -2631,16 +2511,11 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, } if (active) { - printk("%s %p\n", __func__, mas); - printk("Active and needs a node\n"); mas_node_cnt(mas, 1); - if (mas_is_err(mas)) { - printk("Failed\n"); + if (mas_is_err(mas)) return 0; - } } prev_enode = mas->node; - printk("slot %u old_end %u\n", slot, old_end); if (slot > old_end && !coalesce) append = true; @@ -2648,8 +2523,9 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, complete: - if (prev_enode != mas->node) + if (prev_enode != mas->node) { _mas_replace(mas, active, true); + } update_gap: @@ -2677,7 +2553,6 @@ static inline int _mas_insert(struct ma_state *mas, void *entry, unsigned char slot, bool active) { mas_set_slot(mas, slot); - printk("%s %u -> %p\n", __func__, slot, entry); return _mas_add(mas, entry, false, active); } @@ -2702,7 +2577,7 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) // FIXME: When task_size / page_size -1 works, check to ensure we are // not inserting above this. - __mas_add(mas, entry, slot++, false, true); + __mas_add(mas, entry, slot++, false, false); if (mas_is_err(mas)) return; @@ -2717,7 +2592,7 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) // FIXME: mas->index = TASK_SIZE / PAGE_SIZE - 1; mas->index = 0x2000000000000UL; mas->last = mt_max[mt]; - __mas_add(mas, XA_ZERO_ENTRY, slot, false, true); + __mas_add(mas, XA_ZERO_ENTRY, slot, false, false); if (mas_is_err(mas)) return; } @@ -3264,7 +3139,6 @@ static inline void* _mas_prev(struct ma_state *mas, unsigned long limit) mas->last = max; slot = mas_get_slot(mas); - printk("%s: slot %u\n", __func__, slot); if (slot) mas->index = mas_get_safe_pivot(mas, slot - 1) + 1; else @@ -3300,63 +3174,6 @@ void *mas_prev(struct ma_state *mas, unsigned long min) } EXPORT_SYMBOL_GPL(mas_prev); -static inline int mas_coalesce_node(struct ma_state *mas, unsigned char end, - unsigned char coalesce, bool replace) -{ - mas_partial_copy(mas, mt_slot_count(mas->node)); - if (mas_is_err(mas)) - return 0; - if (replace) - mas_replace(mas); - return ma_hard_data(end, coalesce); -} - -static inline void mas_coalesce_pivots(struct ma_state *mas, int slot, - enum maple_type type, bool skip) -{ - - unsigned long piv_val = _mas_get_safe_pivot(mas, slot, type); - unsigned char pivot_cnt = mt_pivots[type]; - - while ((slot < pivot_cnt - 1)) { - unsigned long this_pivot = mte_get_pivot(mas->node, slot + 1); - - if (!this_pivot) // end of node. - break; - - // There is data for this pivot. - if (!mt_is_empty(mte_get_rcu_slot(mas->node, slot + 1))) - break; - - // empty slot above the erase. - piv_val = this_pivot; - slot++; - } - - - /* Walk down and set all the previous pivots with NULLs to piv_val */ - while (--slot >= 0) { - void *entry = mte_get_rcu_slot(mas->node, slot); - - if (!mt_is_empty(entry)) - break; - - if (skip) - mte_set_rcu_slot(mas->node, slot, XA_SKIP_ENTRY); - - mte_set_pivot(mas->node, slot, piv_val); - } - -} -static inline void mas_coalesce_empty(struct ma_state *mas, - struct maple_enode *eparent, unsigned char p_slot, - enum maple_type p_type) -{ - mte_set_rcu_slot(eparent, p_slot, XA_DELETED_ENTRY); - mas_set_slot(mas, p_slot); - mas_coalesce_pivots(mas, p_slot, p_type, false); -} - /** Private * */ @@ -3437,7 +3254,6 @@ static inline int mas_cp_append(struct ma_state *mas, struct ma_state *src, { enum maple_type mas_type = mte_node_type(mas->node); int slot = 0; - printk("count = %u\n", count); MA_STATE(dst, mas->tree, mas->index, mas->last); mas_dup_state(&dst, mas); @@ -3447,24 +3263,18 @@ static inline int mas_cp_append(struct ma_state *mas, struct ma_state *src, while (slot <= count ) { void *entry = mte_get_rcu_slot(src->node, slot); dst.last = mas_get_safe_pivot(src, slot); - printk("range %lu-%lu\n", dst.index, dst.last); if (mt_is_empty(entry) && dst.last != ULONG_MAX) goto next; src->index = dst.index; src->last = dst.last; - printk("Appending %p[%u] to %p[%u]\n", mas_mn(src), slot, - mas_mn(&dst), dst_cnt); - dst_cnt = mas_ma_cp(src, 0, &dst, NULL, mas_mn(&dst), mas_type, dst.min, slot, entry, dst_cnt); next: dst.index = dst.last+1; - printk("update dst to %lu\n", dst.index); slot++; } - printk("Just left while with %u\n", slot); if (retry) { mte_set_pivot(p_mas->node, mte_parent_slot(mas->node), mas_get_safe_pivot(src, slot)); @@ -3490,44 +3300,33 @@ static inline bool mas_coalesce(struct ma_state *mas, unsigned char l_end_slot, { struct maple_node *mn; bool ret = false; - printk("%s: %p + %p\n", __func__, mas_mn(mas), mas_mn(r_mas)); MA_STATE(dst, mas->tree, mas->index, mas->last); // it is possible that all of the right node can be appended to the // left if (total_slots + 1 - l_end_slot < mt_slots[l_type] - l_end_slot) { - printk("append to %p[%u] from %p\n", mas_mn(mas), l_end_slot, - mas_mn(r_mas)); -// mas->max = r_mas->max; mas_cp_append(mas, r_mas, p_mas, l_end_slot, r_end_slot, false); mte_set_rcu_slot(p_mas->node, mte_parent_slot(r_mas->node), XA_SKIP_ENTRY); mte_free(r_mas->node); - printk("coalesce complete\n"); goto done; } mas_node_cnt(mas, 1); // Try to allocate. if (mas_is_err(mas)) { - printk("%s: Allocation failure\n", __func__); // Allocation failed, we could try to append as much // as possible here? return false; } - printk("New node\n"); mn = mas_next_alloc(mas); mas_dup_state(&dst, mas); mn->parent = mas_mn(mas)->parent; dst.node = mt_mk_node(mn, l_type); -// cp->dst = mas->node; -// mas_copy(mas, cp); l_end_slot = mas_cp_append(&dst, mas, p_mas, 0, l_end_slot, false); - printk("l_node_end is now %u\n", l_end_slot); if (!l_end_slot && !mte_get_pivot(dst.node, 0)) { mte_set_pivot(dst.node, 0, mas->max); - printk("set first pivot to %lu\n", mas->max); l_end_slot++; } mas->node = dst.node; @@ -3564,9 +3363,7 @@ static inline void mas_rebalance(struct ma_state *mas) MA_STATE(r_mas, mas->tree, mas->index, mas->last); // right state MA_STATE(p_mas, mas->tree, mas->index, mas->last); // parent state MA_CP(cp, mas->node, NULL, 0, 0); - mt_dump(mas->tree); start: - printk("%s: Starting with %p\n", __func__, mas_mn(mas)); free = false; this_enode = mas->node; l_type = mte_node_type(mas->node); @@ -3577,20 +3374,10 @@ start: mas_ascend(&p_mas); p_slot = mte_parent_slot(mas->node); l_end_slot = mas_data_end(mas, l_type, &l_end_piv, &l_coalesce); - printk("hard data is %u\n", ma_hard_data(l_end_slot, l_coalesce)); if (!try_anyways && - (ma_hard_data(l_end_slot, l_coalesce) >= mt_min_slots[l_type])) { - printk("Done this\n"); + (ma_hard_data(l_end_slot, l_coalesce) >= mt_min_slots[l_type])) return; // Everything's perfectly all right now. - } -#if 0 - else if (ma_hard_data(l_end_slot, l_coalesce == 1)) { - printk("Empty node %p\n", mas_mn(mas)); - mte_set_rcu_slot(p_mas.node, p_slot, XA_DELETED_ENTRY); - mte_free(mas->node); - goto done; - } -#endif + try_anyways = false; // Make sure there is a right node. @@ -3598,19 +3385,15 @@ start: mas_set_slot(&r_mas, p_slot + 1); if (!mas_next_nentry(&r_mas, ULONG_MAX, &r_end_piv)) { // Right-most node coalescing. - printk("Right most\n"); mas_dup_state(&r_mas, &p_mas); - printk("reset to node is %p\n", mas_mn(&r_mas)); mas_set_slot(&r_mas, p_slot); if (!mas_prev_nentry(&r_mas, 0, &r_end_piv)) { // Single entry in the parent. - printk("Single entry?\n"); if (l_end_slot < l_coalesce) { // Single entry is empty. free = true; } else if (l_end_slot == l_coalesce && mas->max == ULONG_MAX) { // Possible single entry of null for // ULONG_MAX. - printk("ulong max check needed\n"); BUG_ON(1); free = true; } @@ -3621,14 +3404,11 @@ start: goto done; } mas_descend(&r_mas); - printk("prev slot is %p\n", mas_mn(&r_mas)); mas_dup_state(mas, &r_mas); - printk("Forcing next one, coalesce prev.\n"); try_anyways = true; // Force a rebalance/coalesce of these nodes. goto start; // restart with new left. } mas_descend(&r_mas); - printk("Right node is %p\n", mas_mn(&r_mas)); // We have a left and a right, check if they can be coalesced. r_type = mte_node_type(r_mas.node); // not for racing. @@ -3658,12 +3438,10 @@ start: mas_node_cnt(mas, 1); // Try to allocate. if (mas_is_err(mas)) { - printk("%s: Allocation failure\n", __func__); // Allocation failed, we could try to append as much // as possible here? return; } - printk("new node\n"); free = true; // free this_enode after the operation. mas->node = mt_mk_node(mas_next_alloc(mas), l_type); @@ -3676,7 +3454,6 @@ start: mas_cp_append(mas, &r_mas, &p_mas, l_end_slot, copy_count, true); if (total_slots <= mt_slots[l_type]) { - printk("Use skip entry\n"); mte_set_rcu_slot(p_mas.node, mte_parent_slot(r_mas.node), XA_SKIP_ENTRY); mte_free(r_mas.node); @@ -3687,7 +3464,6 @@ done: mte_adopt_children(mas->node); if (free) mas_replace(mas); - mt_dump(mas->tree); // Check parent for rebalancing. mas_dup_state(mas, &p_mas); goto start; @@ -4131,11 +3907,9 @@ void *mas_find(struct ma_state *mas, unsigned long max) while (mas_search_cont(mas, index, max, entry)) { entry = _mas_next(mas, max, &index); - printk("%s: %ld -> %p\n", __func__, mas->index, entry); if (mt_is_empty(entry)) entry = NULL; } - printk("%s: %ld -> %p\n", __func__, mas->index, entry); if (entry) mas->index = index; @@ -4204,11 +3978,9 @@ void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max, } rcu_read_unlock(); - if (entry) *index = mas.last + 1; - return entry; } EXPORT_SYMBOL(mt_find); @@ -4230,7 +4002,6 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry, return 0; node_cnt += 3; // Room for an extra split. - //printk("Using node count %d for %lu-%lu\n", node_cnt, mas->index, mas->last); mas_node_cnt(mas, node_cnt); if (mas_is_err(mas)) return 0; @@ -4246,13 +4017,11 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry, new_mas.alloc = mas->alloc; mas->alloc = NULL; - //printk("\tCopy left\n"); // Copy left side mas_reset(mas); mas->index = 0; mas->last = 0; mas_for_each(mas, entry, new_index - 1) { - //printk("\tLeft for each\n"); new_mas.index = mas->index; new_mas.last = mas_get_safe_pivot(mas, mas_get_slot(mas)); if (entry == XA_DELETED_ENTRY) @@ -4261,16 +4030,11 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry, if (mas_is_err(&new_mas)) { goto error; } - //printk("node count is %u\n", mas_get_alloc_cnt(&new_mas)); - //mt_dump(new_mas.tree); } - //printk("Done\n"); - //printk("new_mas node %p\n", mas_mn(&new_mas)); // Insert the new value. new_mas.index = new_index; new_mas.last = new_last; - //printk("\tinsert new entry.. %p %lu %lu\n", mas_mn(&new_mas), new_mas.index, new_mas.last); ma_inactive_insert(&new_mas, new_entry); if (mas_is_err(&new_mas)) goto error; @@ -4299,33 +4063,25 @@ static inline int mas_build_replacement(struct ma_state *mas, void *new_entry, { new_mas.index = r_index; new_mas.last = r_last; - printk("!!Inserting %lu-%lu -> %p\n", r_index, r_last, entry); ma_inactive_insert(&new_mas, entry); if (mas_is_err(&new_mas)) goto error; } } - printk("\tCopy right from %p\n", mas->node); - //mt_dump(mas->tree); mas_for_each(mas, entry, ULONG_MAX) { if (mas->index < new_index) continue; new_mas.index = mas->index; new_mas.last = mas_get_safe_pivot(mas, mas_get_slot(mas)); - // printk("\tInsert %lu-%lu => %p\n", new_mas.index, new_mas.last, entry); ma_inactive_insert(&new_mas, entry); if (mas_is_err(&new_mas)) goto error; - //mt_dump(new_mas.tree); } skip_right: - mt_dump(mas->tree); - printk("Done rebuild due to %lu-%lu\n", new_index, new_last); - mt_dump(new_mas.tree); last = mas->tree->ma_root; mas->node = new_tree.ma_root; _mas_replace(mas, false, false); @@ -4336,10 +4092,8 @@ skip_right: return node_cnt; error: - printk("Error on adding %lu\n",new_mas.index); if (new_mas.tree) mte_destroy_walk(new_mas.tree->ma_root); - mt_dump(mas->tree); BUG_ON(1); return 0; } @@ -4360,18 +4114,14 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) // Create a new tree. MA_STATE(r_mas, mas->tree, mas->last + 1, mas->last + 1); - printk("%s\n", __func__); - mt_dump(mas->tree); // Count the slots that will be used in the node we landed. slot_cnt = 3 + mas_get_slot(mas); // 3 is the max a new entry can create. // Count the nodes that are currently used to the left. mas_set_slot(mas, mte_parent_slot(mas->node)); - printk("Starting left at %p[%u]\n", mas_mn(mas), mas_get_slot(mas)); while (!mas_is_none(mas)) { last = mas->node; mas_prev_node(mas, 0); - printk("prev node %p[%u]\n", mas_mn(mas), mas_get_slot(mas)); leaves++; } // Set mas->node to a valid node. @@ -4379,7 +4129,6 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) // Walk down to the right side of the tree. _mas_walk(&r_mas); - printk("Starting right at %p[%u]\n", mas_mn(&r_mas), mas_get_slot(&r_mas)); // Add the slots to the right of where the search landed. if (mas_get_slot(&r_mas) == MAPLE_NODE_SLOTS) { r_mas.node = MAS_NONE; @@ -4403,7 +4152,6 @@ skip_r_count: if (slot_cnt > mt_slot_count(mas->node)) leaves++; - printk("%d leaves\n", leaves); node_cnt = 1; // Root node. and room to split. while (leaves) { // add the number of nodes at each level. node_cnt += leaves; @@ -4466,13 +4214,11 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size) * found the gap. (return, slot != MAPLE_NODE_SLOTS) */ while (!mas_is_err(mas) && !_mas_awalk(mas, size)) { - printk("%s: %p[%u]\n", __func__, mas_mn(mas), mas_get_slot(mas)); if (last == mas->node) mas_skip_node(mas); else last = mas->node; } - printk("%s: return %p[%u]\n", __func__, mas_mn(mas), mas_get_slot(mas)); } static inline int ma_root_ptr(struct ma_state *mas, void *entry, @@ -4485,7 +4231,6 @@ static inline int ma_root_ptr(struct ma_state *mas, void *entry, if (mas->tree->ma_root && mas->last == 0) goto exists; - printk("%s\n", __func__); if (mas->last != 0) mas_root_expand(mas, entry); else if (((unsigned long) (entry) & 3) == 2) @@ -4562,7 +4307,6 @@ static int mas_fill_gap(struct ma_state *mas, void *entry, unsigned char slot, mas->min = mas_get_safe_pivot(mas, pslot - 1) + 1; mas->node = mn; - printk("%s %d\n", __func__, __LINE__); _mas_insert(mas, entry, slot, true); return 0; } @@ -4659,7 +4403,6 @@ static inline int mas_alloc(struct ma_state *mas, void *entry, mas_start(mas); if (mas_is_none(mas) || mas_is_ptr(mas)) { - printk("%s\n", __func__); mas_root_expand(mas, entry); if (mas_is_err(mas)) return xa_err(mas->node); @@ -4677,7 +4420,6 @@ static inline int mas_alloc(struct ma_state *mas, void *entry, slot = mas_get_slot(mas); if (slot == MAPLE_NODE_SLOTS) goto no_gap; - printk("%s: found %p[%u]\n", __func__, mas_mn(mas), slot); // At this point, mas->node points to the right node and we have a // slot that has a sufficient gap. @@ -4715,7 +4457,6 @@ static inline int mas_rev_alloc(struct ma_state *mas, void *entry, } if (mas_is_ptr(mas)) { - printk("%s\n", __func__); mas_root_expand(mas, entry); if (!mas->index) return mte_get_pivot(mas->node, 0); @@ -4851,7 +4592,6 @@ static inline bool mas_skip_node(struct ma_state *mas) */ static inline void *mas_erase(struct ma_state *mas) { - enum maple_type type; int slot; void *entry = NULL; @@ -4866,18 +4606,11 @@ static inline void *mas_erase(struct ma_state *mas) if (slot == MAPLE_NODE_SLOTS) return NULL; - type = mte_node_type(mas->node); entry = mte_get_rcu_slot(mas->node, slot); - printk("%s: %lu return %p[%u] -> %p now to zero.\n", __func__, - mas->index, mas_mn(mas), slot, entry); mte_update_rcu_slot(mas->node, slot, XA_DELETED_ENTRY); // dense nodes only need to set a single value. -// if (!ma_is_dense(type)) -// mas_coalesce_pivots(mas, slot, type, false); mas_rebalance(mas); - printk("%s: %lu return %p[%u] -> %p\n", __func__, - mas->index, mas_mn(mas), slot, entry); return entry; } @@ -5063,7 +4796,6 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index) MA_STATE(mas, mt, index, index); - printk("%s: erase %lu\n", __func__, index); mtree_lock(mt); entry = mas_erase(&mas); mtree_unlock(mt); @@ -5307,8 +5039,6 @@ void mas_validate_gaps(struct ma_state *mas) if (mt_is_empty(mte_get_rcu_slot(mas->node, i))) BUG_ON(gap != p_end - p_start + 1); else { - printk("gap %lu p_end %lu p_start %lu\n", gap, p_end, p_start); - printk("Gap %p[%u] != %lu\n", mas_mn(mas), i, p_end - p_start+1); BUG_ON(gap >= p_end - p_start + 1); } } @@ -5328,11 +5058,6 @@ counted: p_slot = mte_parent_slot(mas->node); p_mn = mte_parent(mte); MT_BUG_ON(mas->tree, max_gap > mas->max); - if (ma_get_gap(p_mn, p_slot, mas_parent_enum(mas, mte)) != - max_gap) { - printk("get_gap %p[%u] != gap in %p of %lu\n", p_mn, p_slot, - mas_mn(mas), max_gap); - } MT_BUG_ON(mas->tree, ma_get_gap(p_mn, p_slot, mas_parent_enum(mas, mte)) != max_gap); @@ -5352,11 +5077,6 @@ void mas_validate_limits(struct ma_state *mas) unsigned long piv = mas_get_safe_pivot(mas, i); if (!piv) break; - printk("Checking %p[%u] %lu %lu\n", mas_mn(mas), i, mas->min, mas->max); - if (piv > mas->max) { - printk("piv fails %lu\n", piv); - mt_dump(mas->tree); - } BUG_ON(piv < mas->min); BUG_ON(piv > mas->max); } -- 2.50.1