From 910f3e4e36c9c2e6a9f6f74fb7475290c4681e87 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 3 Jan 2020 15:39:17 -0500 Subject: [PATCH] maple_tree: WIP, fixed mas_awalk for full nodes and fill nodes, still hosed at 78381 Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 119 +++++++++++++++++++++++++++--------------- lib/test_maple_tree.c | 10 ++++ 2 files changed, 87 insertions(+), 42 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 18fbebaf3038..ed6663a0e7f4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -877,6 +877,7 @@ 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; @@ -900,8 +901,10 @@ 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) { @@ -914,6 +917,9 @@ static inline void mas_push_node(struct ma_state *mas, struct maple_enode *used) smn = node->slot[(cnt/15) - 1]; 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)); } static inline void mas_node_node(struct ma_state *ms, gfp_t gfp) @@ -1174,33 +1180,48 @@ static inline void mas_ma_cp_store(struct maple_node *mn, } static inline unsigned char mas_cp_calc_split(struct ma_state *mas, - enum maple_type mas_type) + enum maple_type mas_type, bool append) { - unsigned char ret = 7; + unsigned char max = 7, ret = 7; unsigned char slot; unsigned long range = mas->max - mas->min; unsigned long half; + unsigned long piv = 0; if (mas_type == maple_arange_64) { - ret = 3; + max = 3; printk("arange split\n"); } - half = ret / 2; + if (mas->min == 0) + max = 7; + half = max / 2; if (ma_is_leaf(mas_type)) { if (range <= 8) return ret; for (slot = 0; slot <= mt_pivots[mas_type]; slot++) { - unsigned long piv = mas_get_safe_pivot(mas, slot); + piv = mas_get_safe_pivot(mas, slot); if (!piv) return ret; range = piv - mas->min; - if (range >= 8) - return slot > half ? slot : half; + if (range >= 8) { + if (slot > half) + ret = slot; + else + ret = half; + goto done; + } + } - } - return half; + } else + 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, @@ -1266,7 +1287,7 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, attempt_insert = true; - split = mas_cp_calc_split(mas, mas_type); + split = mas_cp_calc_split(mas, mas_type, append); printk("Using split of %d\n", split); if (left) { @@ -1890,6 +1911,8 @@ 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 { @@ -2021,6 +2044,7 @@ 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\n", __func__); type = mte_node_type(mas->node); if (mte_is_root(mas->node)) { old_parent = full; @@ -2119,6 +2143,7 @@ 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)) { @@ -2145,13 +2170,13 @@ 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 mte_free(full); } - return split; } @@ -2259,19 +2284,20 @@ static inline int _mas_add_slot_cnt(struct ma_state *mas, if (max > mas->last) { req_slots++; // slot needed at end. - printk("slot at end\n"); + printk("slot at end %lu > %lu\n", max, mas->last); } else { - printk("wtf\n"); + // walk back through the slots until we get to the insert + // slot checking where we fit. unsigned char end_slot = end; while (end_slot > slot) { unsigned long piv = mas_get_safe_pivot(mas, end_slot); - if (mas->last <= piv) { - if (mas->last < piv) - req_slots++; + if (mas->last < piv) + req_slots++; + if (mas->last <= piv) break; - } end_slot--; } + printk("end slot = %u\n", end_slot); } @@ -2283,20 +2309,22 @@ static inline int _mas_add_slot_cnt(struct ma_state *mas, 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 = end - coalesce + 1; + req_slots = req_slots + end - coalesce; + if (mas->index != min) + req_slots++; - // can't reuse last null. - if (req_slots >= mt_slot_count(mas->node) - 1) { - if (last_entry) - return req_slots + 1; - else if (mas->last == ULONG_MAX) - return req_slots; - else if (mas->max == ULONG_MAX) - return req_slots + 1; - } + printk("req slots %d\n", req_slots); + + // Check if it's safe to use the slot without a pivot. + if (max == mas->max) // max of the slot == max of the node. + return req_slots; - return req_slots; + if (!last_entry) // nothing at the last slot. + return req_slots; + + return req_slots + 1; } static inline int __mas_add(struct ma_state *mas, void *entry, int entry_cnt, bool active, bool append) @@ -2413,7 +2441,9 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, printk("Adding %lu-%lu\n", mas->index, mas->last); new_end = _mas_add_slot_cnt(mas, slot, min, max); - printk("%p new_end %u slot_cnt %u\n", mas_mn(mas), new_end, slot_cnt); + mt_dump(mas->tree); + 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)) { @@ -3775,14 +3805,16 @@ static inline bool _mas_awalk(struct ma_state *mas, unsigned long size) next: min = pivot + 1; } + if (!found) + goto ascend; // leaf exhausted. break; default: pivot = 0; i = mas_get_slot(mas); - for (; i < pivot_cnt; i++) { + for (; i <= pivot_cnt; i++) { unsigned long this_gap; - pivot = _mte_get_pivot(mas->node, i, type); + pivot = _mas_get_safe_pivot(mas, i, type); if (i && !pivot) goto ascend; @@ -3790,7 +3822,7 @@ next: if (size <= this_gap) { if (mas->index <= pivot) { max = pivot; - break; + goto descend; } } @@ -3800,12 +3832,7 @@ next: return true; } } - - // Final slot. - if ((i == pivot_cnt - 1) && (mas->index > pivot)) { - if (size > mte_get_gap(mas->node, ++i)) - goto ascend; - } + goto ascend; // exhausted internal node. break; @@ -3816,6 +3843,7 @@ next: break; } +descend: if (!ma_is_leaf(type)) { //descend struct maple_enode *next; @@ -4120,6 +4148,8 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) MA_STATE(r_mas, mas->tree, mas->last + 1, mas->last + 1); MA_STATE(l_mas, mas->tree, 0, 0); + 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. @@ -4159,13 +4189,13 @@ skip_r_count: leaves++; printk("%d leaves\n", leaves); - node_cnt = 1; // Root node. + node_cnt = 2; // Root node. while (leaves) { // add the number of nodes at each level. node_cnt += leaves; leaves /= mt_slots[p_type]; } - printk("Using node count %d\n", node_cnt); + 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; @@ -4184,8 +4214,10 @@ skip_r_count: new_mas.index = l_mas.index; new_mas.last = l_mas.index; ma_inactive_insert(&new_mas, entry); - if (mas_is_err(&new_mas)) + if (mas_is_err(&new_mas)) { + mt_dump(new_mas.tree); BUG_ON(1); + } } // Insert the new value. @@ -4223,7 +4255,7 @@ skip_right: last = mas->tree->ma_root; mas->node = new_tree.ma_root; _mas_replace(mas, false, false); - mas->node = 0; + mas->node = MAS_START; mas->alloc = new_mas.alloc; mte_destroy_walk(last); @@ -4283,11 +4315,13 @@ 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, @@ -4492,6 +4526,7 @@ 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. diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index b0790bb9bdf0..81a86e6e6b87 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -61,6 +61,9 @@ static noinline void check_mtree_alloc_range(struct maple_tree *mt, MT_BUG_ON(mt, ret != eret); if (ret) return; + if (result != expected) { + printk("Result is %lu\n", result); + } MT_BUG_ON(mt, result != expected); } @@ -350,6 +353,7 @@ static noinline void check_lb_not_empty(struct maple_tree *mt) i = huge; while (i > 4096) { + mt_dump(mt); check_insert(mt, i, (void *) i); for (j = huge; j >= i; j /= 2) { check_load(mt, j-1, NULL); @@ -1924,6 +1928,12 @@ static noinline void check_alloc_range(struct maple_tree *mt) mas_reset(&mas); } for (i = 0; i < req_range_cnt; i += 5) { + mt_dump(mt); + printk("\tTest %d: %lu-%lu size %lu expected %lu\n", i/5, + req_range[i] >> 12, + req_range[i + 1] >> 12, + req_range[i + 2] >> 12, + req_range[i + 3] >> 12); check_mtree_alloc_range(mt, req_range[i] >> 12, // start req_range[i+1] >> 12, // end -- 2.50.1