From d8f97a646a64e5886891547bf21031d0296c5c79 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 2 Mar 2020 13:31:17 -0500 Subject: [PATCH] maple_tree: Add support for combining gaps. When gaps touch but are not in the same node, move them to the right node. This allows for searches to find the desired gap. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 230 ++++++++++++---- lib/test_maple_tree.c | 615 ++++++------------------------------------ 2 files changed, 257 insertions(+), 588 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index d448bcb69bce..d6eaeac816b0 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -893,6 +893,47 @@ restart: } mte_set_pivot(safe_mas.node, slot, val); } + +/** Private + * mas_shift_pivot() - Shift a pivot from one node to the next. + * @left - the left node with mas slot set to the pivot location. + * @right - the right node with mas slot set to the pivot location. + * + * This exists when moving gaps across many levels of a tree. Basically, walk + * backwards until the nodes meet and set the pivots accordingly. + * + * Special cases for XA_SKIP_ENTRY is needed. + */ +static inline void mas_shift_pivot(struct ma_state *curr, + struct ma_state *next, unsigned long piv) +{ + unsigned char l_p_slot; // left parent slot. + unsigned char r_p_slot; // right parent slot. + + MA_STATE(left, curr->tree, curr->index, curr->last); + MA_STATE(right, next->tree, next->index, next->last); + + mas_dup_state(&left, curr); + mas_dup_state(&right, next); + do { + // Ends with NULL side + l_p_slot = mte_parent_slot(left.node); + mas_set_slot(&left, l_p_slot); + mas_ascend(&left); + + // Starts with NULL side + r_p_slot = mte_parent_slot(right.node); + mas_set_slot(&right, r_p_slot); + mas_ascend(&right); + + mas_set_safe_pivot(&left, l_p_slot, piv); + if (left.node == right.node) + break; + + mas_set_slot(&left, l_p_slot); + mas_set_slot(&right, r_p_slot); + } while (left.node != right.node); +} /* mas_get_prev_pivot() - Return the previous pivot. * * Mainly for extracting the previous pivot in the case of slot = 0. @@ -2148,7 +2189,78 @@ static inline enum maple_type mas_determine_type(struct ma_state *mas, return mt; } +/** Private + * mas_may_move_gap() - May move the gap to the proceeding node. + */ +static inline void mas_may_move_gap(struct ma_state *mas) +{ + + unsigned long last_piv; + unsigned char coalesce; + unsigned char end; + unsigned char slot = mas_get_slot(mas); + void *entry = NULL; + + // node that starts with NULL + MA_STATE(next, mas->tree, mas->index, mas->last); + // node that ends with NULL + MA_STATE(curr, mas->tree, mas->index, mas->last); + + if (mte_is_root(mas->node)) + return; + + mas_dup_state(&next, mas); + mas_dup_state(&curr, mas); + end = mas_data_end(&curr, mte_node_type(curr.node), &last_piv, + &coalesce); + if (end != slot) { + mas_prev(&curr, 0); + if (curr.node == mas->node) // prev value not in prev node. + return; + } + + if (mas_is_none(&curr)) + return; + + end = mas_data_end(&curr, mte_node_type(curr.node), &last_piv, + &coalesce); + entry = mas_get_rcu_slot(&curr, end); + if (entry && !xa_is_deleted(entry)) + return; + + if (curr.node == mas->node) { + mas_next(&next, ULONG_MAX); + if (mas_is_none(&next)) + return; + + if (!mt_is_empty(mas_get_rcu_slot(&next, 0))) + return; + } + while (end && (!entry || xa_is_deleted(entry))) + entry = mas_get_rcu_slot(&curr, --end); + + last_piv = mas_get_safe_pivot(&curr, end); + + // At this point, mas->node is the one with end slot = NULL + // check.node starts with NULL. + if (end < mt_pivot_count(curr.node) - 1) + mte_set_pivot(curr.node, end + 1, 0); + + if (curr.node == mas->node) + mas->max = last_piv; + else + mas->min = last_piv + 1; + + mas_shift_pivot(&curr, &next, last_piv); + next.min = last_piv + 1; + curr.max = last_piv; + + if (mt_is_alloc(mas->tree)) { + mas_update_gap(&curr, false); + mas_update_gap(&next, false); + } +} static inline int mas_add(struct ma_state *mas, void *entry, bool overwrite, bool active); @@ -2166,8 +2278,7 @@ static inline int _mas_add_dense(struct ma_state *mas, void *entry, // FIXME: Check entire range, not what we would insert this time. if (!overwrite) { do { - if (_mte_get_rcu_slot(mas->node, min++, this_type, - mas->tree)) + if (mas_get_rcu_slot(mas, min++)) return 0; } while (min < max); } @@ -2275,73 +2386,72 @@ static inline int __mas_add(struct ma_state *mas, void *entry, unsigned char coalesce; unsigned char data_end = mas_data_end(mas, mas_type, &wr_pivot, &coalesce); + unsigned char slot = mas_get_slot(mas); + unsigned char end_slot = slot; + unsigned long src_max = mas->max; + unsigned long piv, prev_piv = mas->min - 1; + void *existing_entry = NULL; int ret = 0; + MA_STATE(cp, mas->tree, mas->index, mas->last); - if (append) { + /* Append only if we are appending AND the slot is truly empty. + * If it's delete, skip, etc, then RCU requires a new node. + */ + if (append && !mas_get_rcu_slot(mas, data_end + 1)) { mas_set_slot(mas, data_end + 1); mas_append_entry(mas, entry); - } else { - unsigned char slot = mas_get_slot(mas); - unsigned char end_slot = slot; - unsigned long src_max = mas->max; - unsigned long piv, prev_piv = mas->min - 1; - void *existing_entry = NULL; + return ret; + } - MA_STATE(cp, mas->tree, mas->index, mas->last); - mas_dup_state(&cp, mas); + mas_dup_state(&cp, mas); - if (slot) - prev_piv = mte_get_pivot(mas->node, slot - 1); - - if (active) { - cp.node = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), - mas_type); - mn = mas_mn(mas); - } else { - // Note cp.node == mas->node here. - mn = &space; - memcpy(mn, mas_mn(mas), sizeof(struct maple_node)); - memset(mas_mn(&cp), 0, sizeof(struct maple_node)); - } - mas_mn(&cp)->parent = mn->parent; - if (prev_piv == mas->index - 1) { - if (slot) // slot - 1 will translate to slot - 1 + 1. - end_slot = _mas_append(&cp, mn, mas_type, - src_max, 0, slot - 1); - } else { - end_slot = _mas_append(&cp, mn, mas_type, src_max, 0, slot); - if (end_slot < mt_pivot_count(cp.node)) - mte_set_pivot(cp.node, end_slot, mas->index - 1); - } + if (slot) + prev_piv = mte_get_pivot(mas->node, slot - 1); - mas_set_slot(&cp, end_slot); - end_slot = mas_append_entry(&cp, entry) + 1; + if (active) { + cp.node = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), + mas_type); + mn = mas_mn(mas); + } else { + // Note cp.node == mas->node here. + mn = &space; + memcpy(mn, mas_mn(mas), sizeof(struct maple_node)); + memset(mas_mn(&cp), 0, sizeof(struct maple_node)); + } + mas_mn(&cp)->parent = mn->parent; + if (prev_piv == mas->index - 1) { + if (slot) // slot - 1 will translate to slot - 1 + 1. + end_slot = _mas_append(&cp, mn, mas_type, src_max, 0, + slot - 1); + } else { + end_slot = _mas_append(&cp, mn, mas_type, src_max, 0, slot); + if (end_slot < mt_pivot_count(cp.node)) + mte_set_pivot(cp.node, end_slot, mas->index - 1); + } - // Partial slot overwrite - slot = mas_skip_overwritten(mas, data_end, slot); - if (slot >= mt_slot_count(mas->node)) - goto done; // potential spanning add. + mas_set_slot(&cp, end_slot); + end_slot = mas_append_entry(&cp, entry) + 1; - mas_get_range(mas, slot, &prev_piv, &piv); + // Partial slot overwrite + slot = mas_skip_overwritten(mas, data_end, slot); + if (slot >= mt_slot_count(mas->node)) + goto done; // potential spanning add. - existing_entry = mas_get_rcu_sanitized(mas, slot); - if (prev_piv <= mas->last && piv > mas->last) { - mte_set_rcu_slot(cp.node, end_slot, existing_entry); - mas_set_safe_pivot(&cp, end_slot++, piv); - cp.max = piv; - slot++; - } + mas_get_range(mas, slot, &prev_piv, &piv); + existing_entry = mas_get_rcu_sanitized(mas, slot); + if (prev_piv <= mas->last && piv > mas->last) { + mte_set_rcu_slot(cp.node, end_slot, existing_entry); + mas_set_safe_pivot(&cp, end_slot++, piv); + cp.max = piv; + slot++; + } + if (slot <= data_end && cp.max < mas->max) + _mas_append(&cp, mn, mas_type, src_max, slot, data_end); - if (slot <= data_end && cp.max < mas->max) { - _mas_append(&cp, mn, mas_type, src_max, slot, - data_end); - } done: - if (active) - mas->node = cp.node; - - } + if (active) + mas->node = cp.node; return ret; } @@ -2525,6 +2635,7 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, active); if (!ret) return ret; + old_end = 0; // fixme. goto update_gap; } @@ -2611,8 +2722,11 @@ complete: ret = mas_spanning_add(mas, entry, spans_node); update_gap: - if (mt_is_alloc(mas->tree)) + if (mt_is_alloc(mas->tree)) { mas_update_gap(mas, false); + if (!entry && (slot >= old_end || !slot)) + mas_may_move_gap(mas); + } return ret; } @@ -3599,7 +3713,6 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) switch (type) { case maple_leaf_64: start = i; - do { void *entry = NULL; @@ -4752,6 +4865,7 @@ static inline void *mas_erase(struct ma_state *mas) // dense nodes only need to set a single value. mas_rebalance(mas); + mas_may_move_gap(mas); return entry; } diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 695cd392acbc..8352a04e8c41 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -10601,521 +10601,6 @@ STORE, 140656836775936, 140656836780031, STORE, 140656787476480, 140656791920639, ERASE, 140656774639616, 140656779083775, }; - unsigned long set20[] = { -STORE, 140737488347136, 140737488351231, -STORE, 140733986955264, 140737488351231, -SNULL, 140733986959359, 140737488351231, -STORE, 140733986955264, 140733986959359, -STORE, 140733986824192, 140733986959359, -STORE, 94410716639232, 94410717106175, -SNULL, 94410717057023, 94410717106175, -STORE, 94410716639232, 94410717057023, -STORE, 94410717057024, 94410717106175, -ERASE, 94410717057024, 94410717106175, -STORE, 94410717057024, 94410717106175, -STORE, 140557326688256, 140557328941055, -SNULL, 140557326831615, 140557328941055, -STORE, 140557326688256, 140557326831615, -STORE, 140557326831616, 140557328941055, -ERASE, 140557326831616, 140557328941055, -STORE, 140557328928768, 140557328936959, -STORE, 140557328936960, 140557328941055, -STORE, 140733987811328, 140733987815423, -STORE, 140733987799040, 140733987811327, -STORE, 140557328924672, 140557328928767, -STORE, 140557328916480, 140557328924671, -STORE, 140557324554240, 140557326688255, -SNULL, 140557324554240, 140557324582911, -STORE, 140557324582912, 140557326688255, -STORE, 140557324554240, 140557324582911, -SNULL, 140557326680063, 140557326688255, -STORE, 140557324582912, 140557326680063, -STORE, 140557326680064, 140557326688255, -ERASE, 140557326680064, 140557326688255, -STORE, 140557326680064, 140557326688255, -STORE, 140557322170368, 140557324554239, -SNULL, 140557322170368, 140557322436607, -STORE, 140557322436608, 140557324554239, -STORE, 140557322170368, 140557322436607, -SNULL, 140557324529663, 140557324554239, -STORE, 140557322436608, 140557324529663, -STORE, 140557324529664, 140557324554239, -SNULL, 140557324529664, 140557324550143, -STORE, 140557324550144, 140557324554239, -STORE, 140557324529664, 140557324550143, -ERASE, 140557324529664, 140557324550143, -STORE, 140557324529664, 140557324550143, -ERASE, 140557324550144, 140557324554239, -STORE, 140557324550144, 140557324554239, -STORE, 140557319979008, 140557322170367, -SNULL, 140557319979008, 140557320069119, -STORE, 140557320069120, 140557322170367, -STORE, 140557319979008, 140557320069119, -SNULL, 140557322162175, 140557322170367, -STORE, 140557320069120, 140557322162175, -STORE, 140557322162176, 140557322170367, -ERASE, 140557322162176, 140557322170367, -STORE, 140557322162176, 140557322170367, -STORE, 140557317718016, 140557319979007, -SNULL, 140557317718016, 140557317869567, -STORE, 140557317869568, 140557319979007, -STORE, 140557317718016, 140557317869567, -SNULL, 140557319962623, 140557319979007, -STORE, 140557317869568, 140557319962623, -STORE, 140557319962624, 140557319979007, -SNULL, 140557319962624, 140557319970815, -STORE, 140557319970816, 140557319979007, -STORE, 140557319962624, 140557319970815, -ERASE, 140557319962624, 140557319970815, -STORE, 140557319962624, 140557319970815, -ERASE, 140557319970816, 140557319979007, -STORE, 140557319970816, 140557319979007, -STORE, 140557315588096, 140557317718015, -SNULL, 140557315588096, 140557315616767, -STORE, 140557315616768, 140557317718015, -STORE, 140557315588096, 140557315616767, -SNULL, 140557317709823, 140557317718015, -STORE, 140557315616768, 140557317709823, -STORE, 140557317709824, 140557317718015, -ERASE, 140557317709824, 140557317718015, -STORE, 140557317709824, 140557317718015, -STORE, 140557313372160, 140557315588095, -SNULL, 140557313372160, 140557313470463, -STORE, 140557313470464, 140557315588095, -STORE, 140557313372160, 140557313470463, -SNULL, 140557315563519, 140557315588095, -STORE, 140557313470464, 140557315563519, -STORE, 140557315563520, 140557315588095, -SNULL, 140557315563520, 140557315571711, -STORE, 140557315571712, 140557315588095, -STORE, 140557315563520, 140557315571711, -ERASE, 140557315563520, 140557315571711, -STORE, 140557315563520, 140557315571711, -ERASE, 140557315571712, 140557315588095, -STORE, 140557315571712, 140557315588095, -STORE, 140557328908288, 140557328924671, -STORE, 140557309575168, 140557313372159, -SNULL, 140557309575168, 140557311234047, -STORE, 140557311234048, 140557313372159, -STORE, 140557309575168, 140557311234047, -SNULL, 140557313331199, 140557313372159, -STORE, 140557311234048, 140557313331199, -STORE, 140557313331200, 140557313372159, -SNULL, 140557313331200, 140557313355775, -STORE, 140557313355776, 140557313372159, -STORE, 140557313331200, 140557313355775, -ERASE, 140557313331200, 140557313355775, -STORE, 140557313331200, 140557313355775, -ERASE, 140557313355776, 140557313372159, -STORE, 140557313355776, 140557313372159, -STORE, 140557307457536, 140557309575167, -SNULL, 140557307457536, 140557307473919, -STORE, 140557307473920, 140557309575167, -STORE, 140557307457536, 140557307473919, -SNULL, 140557309566975, 140557309575167, -STORE, 140557307473920, 140557309566975, -STORE, 140557309566976, 140557309575167, -ERASE, 140557309566976, 140557309575167, -STORE, 140557309566976, 140557309575167, -STORE, 140557305339904, 140557307457535, -SNULL, 140557305339904, 140557305356287, -STORE, 140557305356288, 140557307457535, -STORE, 140557305339904, 140557305356287, -SNULL, 140557307449343, 140557307457535, -STORE, 140557305356288, 140557307449343, -STORE, 140557307449344, 140557307457535, -ERASE, 140557307449344, 140557307457535, -STORE, 140557307449344, 140557307457535, -STORE, 140557302771712, 140557305339903, -SNULL, 140557302771712, 140557303238655, -STORE, 140557303238656, 140557305339903, -STORE, 140557302771712, 140557303238655, -SNULL, 140557305331711, 140557305339903, -STORE, 140557303238656, 140557305331711, -STORE, 140557305331712, 140557305339903, -ERASE, 140557305331712, 140557305339903, -STORE, 140557305331712, 140557305339903, -STORE, 140557300658176, 140557302771711, -SNULL, 140557300658176, 140557300670463, -STORE, 140557300670464, 140557302771711, -STORE, 140557300658176, 140557300670463, -SNULL, 140557302763519, 140557302771711, -STORE, 140557300670464, 140557302763519, -STORE, 140557302763520, 140557302771711, -ERASE, 140557302763520, 140557302771711, -STORE, 140557302763520, 140557302771711, -STORE, 140557328900096, 140557328924671, -STORE, 140557328887808, 140557328924671, -SNULL, 140557313347583, 140557313355775, -STORE, 140557313331200, 140557313347583, -STORE, 140557313347584, 140557313355775, -SNULL, 140557302767615, 140557302771711, -STORE, 140557302763520, 140557302767615, -STORE, 140557302767616, 140557302771711, -SNULL, 140557315567615, 140557315571711, -STORE, 140557315563520, 140557315567615, -STORE, 140557315567616, 140557315571711, -SNULL, 140557305335807, 140557305339903, -STORE, 140557305331712, 140557305335807, -STORE, 140557305335808, 140557305339903, -SNULL, 140557307453439, 140557307457535, -STORE, 140557307449344, 140557307453439, -STORE, 140557307453440, 140557307457535, -SNULL, 140557309571071, 140557309575167, -STORE, 140557309566976, 140557309571071, -STORE, 140557309571072, 140557309575167, -SNULL, 140557317713919, 140557317718015, -STORE, 140557317709824, 140557317713919, -STORE, 140557317713920, 140557317718015, -SNULL, 140557319966719, 140557319970815, -STORE, 140557319962624, 140557319966719, -STORE, 140557319966720, 140557319970815, -SNULL, 140557322166271, 140557322170367, -STORE, 140557322162176, 140557322166271, -STORE, 140557322166272, 140557322170367, -SNULL, 140557324546047, 140557324550143, -STORE, 140557324529664, 140557324546047, -STORE, 140557324546048, 140557324550143, -SNULL, 140557326684159, 140557326688255, -STORE, 140557326680064, 140557326684159, -STORE, 140557326684160, 140557326688255, -SNULL, 94410717102079, 94410717106175, -STORE, 94410717057024, 94410717102079, -STORE, 94410717102080, 94410717106175, -SNULL, 140557328932863, 140557328936959, -STORE, 140557328928768, 140557328932863, -STORE, 140557328932864, 140557328936959, -ERASE, 140557328924672, 140557328928767, -STORE, 94410726526976, 94410726662143, -STORE, 140737488347136, 140737488351231, -STORE, 140727481659392, 140737488351231, -SNULL, 140727481663487, 140737488351231, -STORE, 140727481659392, 140727481663487, -STORE, 140727481528320, 140727481663487, -STORE, 94301767393280, 94301769547775, -SNULL, 94301767446527, 94301769547775, -STORE, 94301767393280, 94301767446527, -STORE, 94301767446528, 94301769547775, -ERASE, 94301767446528, 94301769547775, -STORE, 94301769539584, 94301769547775, -STORE, 140365555687424, 140365557940223, -SNULL, 140365555830783, 140365557940223, -STORE, 140365555687424, 140365555830783, -STORE, 140365555830784, 140365557940223, -ERASE, 140365555830784, 140365557940223, -STORE, 140365557927936, 140365557936127, -STORE, 140365557936128, 140365557940223, -STORE, 140727482724352, 140727482728447, -STORE, 140727482712064, 140727482724351, -STORE, 140365557903360, 140365557927935, -STORE, 140365557895168, 140365557903359, -STORE, 140365551890432, 140365555687423, -SNULL, 140365551890432, 140365553549311, -STORE, 140365553549312, 140365555687423, -STORE, 140365551890432, 140365553549311, -SNULL, 140365555646463, 140365555687423, -STORE, 140365553549312, 140365555646463, -STORE, 140365555646464, 140365555687423, -SNULL, 140365555646464, 140365555671039, -STORE, 140365555671040, 140365555687423, -STORE, 140365555646464, 140365555671039, -ERASE, 140365555646464, 140365555671039, -STORE, 140365555646464, 140365555671039, -ERASE, 140365555671040, 140365555687423, -STORE, 140365555671040, 140365555687423, -SNULL, 140365555662847, 140365555671039, -STORE, 140365555646464, 140365555662847, -STORE, 140365555662848, 140365555671039, -SNULL, 94301769543679, 94301769547775, -STORE, 94301769539584, 94301769543679, -STORE, 94301769543680, 94301769547775, -SNULL, 140365557932031, 140365557936127, -STORE, 140365557927936, 140365557932031, -STORE, 140365557932032, 140365557936127, -ERASE, 140365557903360, 140365557927935, -STORE, 94301792006144, 94301792141311, -STORE, 140737488347136, 140737488351231, -STORE, 140734780747776, 140737488351231, -SNULL, 140734780751871, 140737488351231, -STORE, 140734780747776, 140734780751871, -STORE, 140734780616704, 140734780751871, -STORE, 94557838819328, 94557841571839, -SNULL, 94557839429631, 94557841571839, -STORE, 94557838819328, 94557839429631, -STORE, 94557839429632, 94557841571839, -ERASE, 94557839429632, 94557841571839, -STORE, 94557841526784, 94557841567743, -STORE, 94557841567744, 94557841571839, -STORE, 140503043223552, 140503045476351, -SNULL, 140503043366911, 140503045476351, -STORE, 140503043223552, 140503043366911, -STORE, 140503043366912, 140503045476351, -ERASE, 140503043366912, 140503045476351, -STORE, 140503045464064, 140503045472255, -STORE, 140503045472256, 140503045476351, -STORE, 140734780923904, 140734780927999, -STORE, 140734780911616, 140734780923903, -STORE, 140503045439488, 140503045464063, -STORE, 140503045431296, 140503045439487, -STORE, 140503041019904, 140503043223551, -SNULL, 140503041019904, 140503041122303, -STORE, 140503041122304, 140503043223551, -STORE, 140503041019904, 140503041122303, -SNULL, 140503043215359, 140503043223551, -STORE, 140503041122304, 140503043215359, -STORE, 140503043215360, 140503043223551, -ERASE, 140503043215360, 140503043223551, -STORE, 140503043215360, 140503043223551, -STORE, 140503038803968, 140503041019903, -SNULL, 140503038803968, 140503038902271, -STORE, 140503038902272, 140503041019903, -STORE, 140503038803968, 140503038902271, -SNULL, 140503040995327, 140503041019903, -STORE, 140503038902272, 140503040995327, -STORE, 140503040995328, 140503041019903, -SNULL, 140503040995328, 140503041003519, -STORE, 140503041003520, 140503041019903, -STORE, 140503040995328, 140503041003519, -ERASE, 140503040995328, 140503041003519, -STORE, 140503040995328, 140503041003519, -ERASE, 140503041003520, 140503041019903, -STORE, 140503041003520, 140503041019903, -STORE, 140503036690432, 140503038803967, -SNULL, 140503036690432, 140503036702719, -STORE, 140503036702720, 140503038803967, -STORE, 140503036690432, 140503036702719, -SNULL, 140503038795775, 140503038803967, -STORE, 140503036702720, 140503038795775, -STORE, 140503038795776, 140503038803967, -ERASE, 140503038795776, 140503038803967, -STORE, 140503038795776, 140503038803967, -STORE, 140503034560512, 140503036690431, -SNULL, 140503034560512, 140503034589183, -STORE, 140503034589184, 140503036690431, -STORE, 140503034560512, 140503034589183, -SNULL, 140503036682239, 140503036690431, -STORE, 140503034589184, 140503036682239, -STORE, 140503036682240, 140503036690431, -ERASE, 140503036682240, 140503036690431, -STORE, 140503036682240, 140503036690431, -STORE, 140503032446976, 140503034560511, -SNULL, 140503032446976, 140503032459263, -STORE, 140503032459264, 140503034560511, -STORE, 140503032446976, 140503032459263, -SNULL, 140503034552319, 140503034560511, -STORE, 140503032459264, 140503034552319, -STORE, 140503034552320, 140503034560511, -ERASE, 140503034552320, 140503034560511, -STORE, 140503034552320, 140503034560511, -STORE, 140503030308864, 140503032446975, -SNULL, 140503030308864, 140503030345727, -STORE, 140503030345728, 140503032446975, -STORE, 140503030308864, 140503030345727, -SNULL, 140503032438783, 140503032446975, -STORE, 140503030345728, 140503032438783, -STORE, 140503032438784, 140503032446975, -ERASE, 140503032438784, 140503032446975, -STORE, 140503032438784, 140503032446975, -STORE, 140503045423104, 140503045439487, -STORE, 140503028191232, 140503030308863, -SNULL, 140503028191232, 140503028207615, -STORE, 140503028207616, 140503030308863, -STORE, 140503028191232, 140503028207615, -SNULL, 140503030300671, 140503030308863, -STORE, 140503028207616, 140503030300671, -STORE, 140503030300672, 140503030308863, -ERASE, 140503030300672, 140503030308863, -STORE, 140503030300672, 140503030308863, -STORE, 140503026073600, 140503028191231, -SNULL, 140503026073600, 140503026089983, -STORE, 140503026089984, 140503028191231, -STORE, 140503026073600, 140503026089983, -SNULL, 140503028183039, 140503028191231, -STORE, 140503026089984, 140503028183039, -STORE, 140503028183040, 140503028191231, -ERASE, 140503028183040, 140503028191231, -STORE, 140503028183040, 140503028191231, -STORE, 140503022276608, 140503026073599, -SNULL, 140503022276608, 140503023935487, -STORE, 140503023935488, 140503026073599, -STORE, 140503022276608, 140503023935487, -SNULL, 140503026032639, 140503026073599, -STORE, 140503023935488, 140503026032639, -STORE, 140503026032640, 140503026073599, -SNULL, 140503026032640, 140503026057215, -STORE, 140503026057216, 140503026073599, -STORE, 140503026032640, 140503026057215, -ERASE, 140503026032640, 140503026057215, -STORE, 140503026032640, 140503026057215, -ERASE, 140503026057216, 140503026073599, -STORE, 140503026057216, 140503026073599, -STORE, 140503045414912, 140503045439487, -SNULL, 140503026049023, 140503026057215, -STORE, 140503026032640, 140503026049023, -STORE, 140503026049024, 140503026057215, -SNULL, 140503028187135, 140503028191231, -STORE, 140503028183040, 140503028187135, -STORE, 140503028187136, 140503028191231, -SNULL, 140503030304767, 140503030308863, -STORE, 140503030300672, 140503030304767, -STORE, 140503030304768, 140503030308863, -SNULL, 140503032442879, 140503032446975, -STORE, 140503032438784, 140503032442879, -STORE, 140503032442880, 140503032446975, -SNULL, 140503034556415, 140503034560511, -STORE, 140503034552320, 140503034556415, -STORE, 140503034556416, 140503034560511, -SNULL, 140503040999423, 140503041003519, -STORE, 140503040995328, 140503040999423, -STORE, 140503040999424, 140503041003519, -SNULL, 140503036686335, 140503036690431, -STORE, 140503036682240, 140503036686335, -STORE, 140503036686336, 140503036690431, -SNULL, 140503038799871, 140503038803967, -STORE, 140503038795776, 140503038799871, -STORE, 140503038799872, 140503038803967, -SNULL, 140503043219455, 140503043223551, -STORE, 140503043215360, 140503043219455, -STORE, 140503043219456, 140503043223551, -SNULL, 94557841539071, 94557841567743, -STORE, 94557841526784, 94557841539071, -STORE, 94557841539072, 94557841567743, -SNULL, 140503045468159, 140503045472255, -STORE, 140503045464064, 140503045468159, -STORE, 140503045468160, 140503045472255, -ERASE, 140503045439488, 140503045464063, -STORE, 94557855555584, 94557855694847, -STORE, 140503020154880, 140503022276607, -SNULL, 140503020154880, 140503020175359, -STORE, 140503020175360, 140503022276607, -STORE, 140503020154880, 140503020175359, -SNULL, 140503022268415, 140503022276607, -STORE, 140503020175360, 140503022268415, -STORE, 140503022268416, 140503022276607, -ERASE, 140503022268416, 140503022276607, -STORE, 140503022268416, 140503022276607, -SNULL, 140503022272511, 140503022276607, -STORE, 140503022268416, 140503022272511, -STORE, 140503022272512, 140503022276607, -STORE, 140503045439488, 140503045464063, -STORE, 140503017984000, 140503020154879, -SNULL, 140503017984000, 140503018024959, -STORE, 140503018024960, 140503020154879, -STORE, 140503017984000, 140503018024959, -SNULL, 140503020122111, 140503020154879, -STORE, 140503018024960, 140503020122111, -STORE, 140503020122112, 140503020154879, -SNULL, 140503020122112, 140503020130303, -STORE, 140503020130304, 140503020154879, -STORE, 140503020122112, 140503020130303, -ERASE, 140503020122112, 140503020130303, -STORE, 140503020122112, 140503020130303, -ERASE, 140503020130304, 140503020154879, -STORE, 140503020130304, 140503020154879, -SNULL, 140503020126207, 140503020130303, -STORE, 140503020122112, 140503020126207, -STORE, 140503020126208, 140503020130303, -ERASE, 140503045439488, 140503045464063, -STORE, 140503015854080, 140503017983999, -SNULL, 140503015854080, 140503015882751, -STORE, 140503015882752, 140503017983999, -STORE, 140503015854080, 140503015882751, -SNULL, 140503017975807, 140503017983999, -STORE, 140503015882752, 140503017975807, -STORE, 140503017975808, 140503017983999, -ERASE, 140503017975808, 140503017983999, -STORE, 140503017975808, 140503017983999, -SNULL, 140503017979903, 140503017983999, -STORE, 140503017975808, 140503017979903, -STORE, 140503017979904, 140503017983999, -STORE, 140503013736448, 140503015854079, -SNULL, 140503013736448, 140503013752831, -STORE, 140503013752832, 140503015854079, -STORE, 140503013736448, 140503013752831, -SNULL, 140503015845887, 140503015854079, -STORE, 140503013752832, 140503015845887, -STORE, 140503015845888, 140503015854079, -ERASE, 140503015845888, 140503015854079, -STORE, 140503015845888, 140503015854079, -SNULL, 140503015849983, 140503015854079, -STORE, 140503015845888, 140503015849983, -STORE, 140503015849984, 140503015854079, -STORE, 140503045439488, 140503045464063, -STORE, 140503011606528, 140503013736447, -SNULL, 140503011606528, 140503011635199, -STORE, 140503011635200, 140503013736447, -STORE, 140503011606528, 140503011635199, -SNULL, 140503013728255, 140503013736447, -STORE, 140503011635200, 140503013728255, -STORE, 140503013728256, 140503013736447, -ERASE, 140503013728256, 140503013736447, -STORE, 140503013728256, 140503013736447, -STORE, 140503009411072, 140503011606527, -SNULL, 140503009411072, 140503009492991, -STORE, 140503009492992, 140503011606527, -STORE, 140503009411072, 140503009492991, -SNULL, 140503011590143, 140503011606527, -STORE, 140503009492992, 140503011590143, -STORE, 140503011590144, 140503011606527, -SNULL, 140503011590144, 140503011598335, -STORE, 140503011598336, 140503011606527, -STORE, 140503011590144, 140503011598335, -ERASE, 140503011590144, 140503011598335, -STORE, 140503011590144, 140503011598335, -ERASE, 140503011598336, 140503011606527, -STORE, 140503011598336, 140503011606527, -SNULL, 140503011594239, 140503011598335, -STORE, 140503011590144, 140503011594239, -STORE, 140503011594240, 140503011598335, -SNULL, 140503013732351, 140503013736447, -STORE, 140503013728256, 140503013732351, -STORE, 140503013732352, 140503013736447, -ERASE, 140503045439488, 140503045464063, -STORE, 140503045439488, 140503045464063, -STORE, 140503007264768, 140503009411071, -SNULL, 140503007264768, 140503007309823, -STORE, 140503007309824, 140503009411071, -STORE, 140503007264768, 140503007309823, -SNULL, 140503009402879, 140503009411071, -STORE, 140503007309824, 140503009402879, -STORE, 140503009402880, 140503009411071, -ERASE, 140503009402880, 140503009411071, -STORE, 140503009402880, 140503009411071, -SNULL, 140503009406975, 140503009411071, -STORE, 140503009402880, 140503009406975, -STORE, 140503009406976, 140503009411071, -ERASE, 140503045439488, 140503045464063, -STORE, 140503045459968, 140503045464063, -ERASE, 140503045459968, 140503045464063, -STORE, 140503045459968, 140503045464063, -ERASE, 140503045459968, 140503045464063, -STORE, 94557855555584, 94557855838207, -SNULL, 94557855805439, 94557855838207, -STORE, 94557855555584, 94557855805439, -STORE, 94557855805440, 94557855838207, -ERASE, 94557855805440, 94557855838207, -STORE, 140503044612096, 140503045439487, -STORE, 140503003066368, 140503007264767, -SNULL, 140503003070463, 140503007264767, -STORE, 140503003066368, 140503003070463, -STORE, 140503003070464, 140503007264767, -STORE, 140502998867968, 140503003066367, -STORE, 140502864650240, 140502998867967, -SNULL, 140502864650240, 140502875766783, -STORE, 140502875766784, 140502998867967, -STORE, 140502864650240, 140502875766783, -ERASE, 140502864650240, 140502875766783, -SNULL, 140502998872063, 140503003066367, -STORE, 140502998867968, 140502998872063, -STORE, 140502998872064, 140503003066367, -SNULL, 140502942875647, 140502998867967, -STORE, 140502875766784, 140502942875647, -STORE, 140502942875648, 140502998867967, -ERASE, 140502942875648, 140502998867967, -SNULL, 140502875910143, 140502942875647, -STORE, 140502875766784, 140502875910143, -STORE, 140502875910144, 140502942875647, - }; int cnt = 0; MA_STATE(mas, mt, 0, 0); @@ -11271,19 +10756,6 @@ STORE, 140502875910144, 140502942875647, entry = mas_prev(&mas, 0); MT_BUG_ON(mt, entry != xa_mk_value(140656766251008)); mtree_destroy(mt); - - /* set20 found a bug in an add that spanned the node boundaries but - * sill required the node to be split. - */ - mt_set_non_kernel(99); - mas_reset(&mas); - mtree_init(mt, MAPLE_ALLOC_RANGE); - check_erase2_testset(mt, set20, ARRAY_SIZE(set20)); - rcu_barrier(); - mas_get_unmapped_area_rev(&mas, 4096, 140503045476352, 134217728); - MT_BUG_ON(mt, mas.index != 140502741549056); - mtree_destroy(mt); - } static noinline void check_alloc_rev_range(struct maple_tree *mt) @@ -11687,6 +11159,85 @@ static noinline void check_prev_entry(struct maple_tree *mt) mtree_destroy(mt); } +static noinline void check_gap_combining(struct maple_tree *mt) +{ + struct maple_enode *mn1, *mn2; + void *entry; + unsigned long index = 86; + + MA_STATE(mas, mt, index, index); + + MT_BUG_ON(mt, !mtree_empty(mt)); + check_seq(mt, 100, false); // create 100 singletons. + + mtree_test_erase(mt, 88); + mtree_test_erase(mt, 87); + + rcu_read_lock(); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(index)); + mn1 = mas.node; + entry = mas_next(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(index + 3)); + mn2 = mas.node; + MT_BUG_ON(mt, mn1 == mn2); + + // At this point, there is a gap of 2 in either 1 or 2 nodes. Find a + // gap of size 2 from 100 down to 50. + mas_reset(&mas); + MT_BUG_ON(mt, mas_get_unmapped_area_rev(&mas, 50, 100, 2)); + MT_BUG_ON(mt, mas.index != 87); + rcu_read_unlock(); + + mtree_test_erase(mt, 38); + mtree_test_erase(mt, 39); + mtree_test_erase(mt, 40); + index = 37; + + rcu_read_lock(); + mas.index = index; + mas.last = index; + mas_reset(&mas); + entry = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(index)); + mn1 = mas.node; + entry = mas_next(&mas, ULONG_MAX); + MT_BUG_ON(mt, entry != xa_mk_value(index + 4)); + mn2 = mas.node; + MT_BUG_ON(mt, mn1 == mn2); + + // At this point, there is a gap of 2 in either 1 or 2 nodes. Find a + // gap of size 2 from 100 down to 50. + mas_reset(&mas); + MT_BUG_ON(mt, mas_get_unmapped_area_rev(&mas, 20, 50, 3)); + MT_BUG_ON(mt, mas.index != 38); + rcu_read_unlock(); + + mtree_store(mt, 79, NULL, GFP_KERNEL); + mtree_store(mt, 80, NULL, GFP_KERNEL); + + mas_reset(&mas); + rcu_read_lock(); + MT_BUG_ON(mt, mas_get_unmapped_area_rev(&mas, 76, 81, 2)); + MT_BUG_ON(mt, mas.index != 79); + rcu_read_unlock(); + + mtree_destroy(mt); + mtree_init(mt, MAPLE_ALLOC_RANGE); + check_seq(mt, 2000, false); + mtree_test_erase(mt, 1792); + mtree_test_erase(mt, 1791); + + mas_reset(&mas); + rcu_read_lock(); + MT_BUG_ON(mt, mas_get_unmapped_area_rev(&mas, 1700, 1800, 2)); + MT_BUG_ON(mt, mas.index != 1791); + rcu_read_unlock(); + mtree_destroy(mt); + +} + + static DEFINE_MTREE(tree); static int maple_tree_seed(void) @@ -11848,10 +11399,14 @@ static int maple_tree_seed(void) mtree_init(&tree, 0); check_erase2_sets(&tree); mtree_destroy(&tree); - rcu_barrier(); + mtree_init(&tree, MAPLE_ALLOC_RANGE); + check_gap_combining(&tree); + mtree_destroy(&tree); + + rcu_barrier(); pr_info("maple_tree: %u of %u tests passed\n", maple_tree_tests_passed, - maple_tree_tests_run); + maple_tree_tests_run); return (maple_tree_tests_run == maple_tree_tests_passed) ? 0 : -EINVAL; } -- 2.50.1