From 66162d15c57466d99a41ddc108ba9dbce9a28d34 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 20 Feb 2020 11:28:50 -0500 Subject: [PATCH] maple_tree: Fix append_entry for NULL appending, fix append for retry entries, fix split appending on coalesce. Add some testcases for the above fixes. Also fix an off-by-one error in spanning_add. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 75 ++++++--- lib/test_maple_tree.c | 349 +++++++++++++++++++++++++++++++++++++++--- 2 files changed, 380 insertions(+), 44 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 5bac86acd76f..31f1608adf0c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1222,38 +1222,44 @@ static inline void mas_get_range(struct ma_state *mas, unsigned char slot, if ((*min) == 1) // empty node. *min = mas->min; } +/* mas_append_entry() - Append an entry to the target slot or overwrite a + * porting of the last slot. + */ static inline unsigned char mas_append_entry(struct ma_state *mas, void *entry) { unsigned long wr_pivot = mas->min ? mas->min - 1 : 0; unsigned char coalesce, dst_slot = mas_get_slot(mas); - bool prev_null = false; if (!mte_get_rcu_slot(mas->node, 0) && !mte_get_pivot(mas->node, 0)) dst_slot = 0; // empty node. - else if (dst_slot > mt_slot_count(mas->node)) + else if (dst_slot > mt_slot_count(mas->node)) { // Should not happen. dst_slot = mas_data_end(mas, mte_node_type(mas->node), - &wr_pivot, &coalesce) + 1; // slot not set. - else if (dst_slot) // near-full node append. + &wr_pivot, &coalesce); // slot not set.} + } else if (dst_slot) wr_pivot = mas_get_safe_pivot(mas, dst_slot - 1); - if (dst_slot && !mte_get_rcu_slot(mas->node, dst_slot - 1)) - prev_null = true; - - if (mas->index && mas->index == wr_pivot) - dst_slot--; - else if (entry && mas->index && mas->index - 1 != wr_pivot) { - if (prev_null && dst_slot) + if (dst_slot && mas->index < wr_pivot) { + mas_set_safe_pivot(mas, dst_slot - 1, mas->index - 1); + } else if (entry && mas->index && (mas->index - 1 != wr_pivot)) { + if (dst_slot && !mte_get_rcu_slot(mas->node, dst_slot - 1)) dst_slot--; mte_set_rcu_slot(mas->node, dst_slot, NULL); mas_set_safe_pivot(mas, dst_slot++, mas->index - 1); + } else if (!entry) { // appending NULL value. + if (mte_get_rcu_slot(mas->node, dst_slot)) { + mas_set_safe_pivot(mas, dst_slot, mas->index - 1); + dst_slot++; + } } + mte_set_rcu_slot(mas->node, dst_slot, entry); mas_set_safe_pivot(mas, dst_slot, mas->last); mas->max = mas->last; return dst_slot; } + static inline unsigned char _mas_append(struct ma_state *mas, struct maple_node *smn, enum maple_type stype, unsigned long src_max, @@ -1266,6 +1272,7 @@ static inline unsigned char _mas_append(struct ma_state *mas, bool prev_null = false; void *src_data = NULL; + // Find last slot in the dst. while (dst_slot < mt_slot_count(mas->node)) { unsigned long this_piv; @@ -1292,6 +1299,7 @@ static inline unsigned char _mas_append(struct ma_state *mas, dst_slot++; } + // Append data from src. src_data = ma_get_rcu_slot(smn, src_start, stype); for (src_slot = src_start; src_slot <= src_end; src_slot++) { bool next_dst = true; @@ -1309,6 +1317,9 @@ static inline unsigned char _mas_append(struct ma_state *mas, continue; if (!src_data || mt_will_coalesce(src_data)) { + if (src_piv < mas->min && xa_is_retry(src_data)) + continue; + src_data = NULL; if (prev_null && dst_slot) { mte_set_pivot(mas->node, dst_slot - 1, src_piv); @@ -1424,7 +1435,7 @@ static void mas_split_may_switch_dst(struct ma_state **dst_mas, } } -static void mas_append_split_data(struct ma_state *left, +static unsigned char mas_append_split_data(struct ma_state *left, struct ma_state *right, struct ma_state *src, unsigned char split, unsigned char start, unsigned char end, unsigned char slot, void *entry) @@ -1440,9 +1451,13 @@ static void mas_append_split_data(struct ma_state *left, dst_slot = slot - split - 1; if (mte_get_pivot(dst->node, dst_slot)) dst_slot++; + + while ((mte_get_pivot(src->node, start) < dst->min) && + (start < end)) + start++; } - if (dst_slot != 0) { + if (dst_slot) { mas_append(dst, src, start, slot - 1); dst->max = mte_get_pivot(dst->node, slot - 1); } @@ -1484,10 +1499,12 @@ static void mas_append_split_data(struct ma_state *left, if (slot <= end && dst->max < src->max) { mas_append(dst, src, slot, end); dst->max = mas_get_safe_pivot(src, end); + slot = end + 1; } done: if (left == dst) right->min = dst->max + 1; + return slot; } @@ -1509,9 +1526,9 @@ static inline unsigned char mas_append_split(struct ma_state *dst1, goto not_a_leaf; if (slot <= split) { // going into the left one, at least a little. - mas_append_split_data(dst1, dst2, src, split, 0, + slot = mas_append_split_data(dst1, dst2, src, split, 0, split, slot, entry); - mas_append(dst2, src, split + 1, data_end); + mas_append(dst2, src, slot, data_end); } else { // going into the right. mas_append(dst1, src, 0, split); mas_append_split_data(NULL, dst2, src, split, split + 1, @@ -2284,9 +2301,10 @@ static inline int __mas_add(struct ma_state *mas, void *entry, _mas_append(&cp, mn, mas_type, src_max, 0, slot - 1); } else { - _mas_append(&cp, mn, mas_type, src_max, 0, slot); - mte_set_pivot(cp.node, slot, mas->index - 1); - mas_set_slot(&cp, slot + 1); + 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); + mas_set_slot(&cp, end_slot); } end_slot = mas_append_entry(&cp, entry) + 1; @@ -2305,6 +2323,7 @@ static inline int __mas_add(struct ma_state *mas, void *entry, cp.max = piv; slot++; } + if (slot <= data_end && cp.max < mas->max) { _mas_append(&cp, mn, mas_type, src_max, slot, data_end); @@ -2372,10 +2391,10 @@ static inline int mas_spanning_add(struct ma_state *mas, void *entry, mas_set_slot(&p_mas, p_slot); // for pivot changes in parent. mas_dup_state(&r_mas, mas); // point to the start node. - while (!mas_is_none(&r_mas) && r_mas.max <= r_mas.last) { + while (!mas_is_none(&r_mas) && r_mas.max <= r_mas.last + 1) { mas_dup_state(&tmp, &r_mas); mas_next_node(&r_mas, r_mas.last); - if (r_mas.max <= r_mas.last) { + if (r_mas.max <= r_mas.last + 1) { struct maple_enode *enode = r_mas.node; i = mte_parent_slot(enode); @@ -3571,6 +3590,7 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) switch (type) { case maple_leaf_64: max = _mas_get_safe_pivot(mas, i, type); + start = i; do { void *entry = NULL; @@ -3605,8 +3625,6 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) if (this_gap >= size) { /* within range and large enough */ if (mas->last - min + 1 < size) { - printk("Skip: %lu - %lu < %lu\n", - mas->last, min, size); /* It is possible that the gap is * sufficient and within range, but * the size does not fit within the @@ -5237,6 +5255,7 @@ void mas_validate_parent_slot(struct ma_state *mas) void mas_validate_limits(struct ma_state *mas) { int i; + unsigned long prev_piv = 0; if (mte_is_root(mas->node)) return; // all limits are fine here. @@ -5246,6 +5265,17 @@ void mas_validate_limits(struct ma_state *mas) if (!piv) break; + + if (prev_piv > piv) { + void *entry = mte_get_rcu_slot(mas->node, i); + if (!mt_will_coalesce(entry)) { + pr_err(MA_PTR"[%u] %lu < %lu\n", mas_mn(mas), i, + piv, prev_piv); + mt_dump(mas->tree); + MT_BUG_ON(mas->tree, piv < prev_piv); + } + } + if (piv < mas->min) { void *entry = mte_get_rcu_slot(mas->node, i); @@ -5262,6 +5292,7 @@ void mas_validate_limits(struct ma_state *mas) mas->max); MT_BUG_ON(mas->tree, piv > mas->max); } + prev_piv = piv; } } diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 3144371cda11..c4b601907687 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -75,7 +75,6 @@ static noinline void check_mtree_alloc_rrange(struct maple_tree *mt, ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end, GFP_KERNEL); - printk("ret = %d result %lu\n", ret, result); MT_BUG_ON(mt, ret != eret); if (ret) return; @@ -872,7 +871,14 @@ static noinline void check_erase_testset(struct maple_tree *mt) #define erase_check_store_range(mt, a, i, ptr) mtree_test_store_range(mt, \ a[(i)], a[(i + 1)] - 1, ptr) #define STORE 1 -#define ERASE 2 +#define SNULL 2 +#define ERASE 3 +#define ec_type_str(x) \ + ( ((x) == STORE) ? \ + "STORE" : \ + (((x) == SNULL) ? \ + "SNULL" : "ERASE") \ + ) #define check_erase2_debug 0 void *mas_next(struct ma_state *mas, unsigned long max); static noinline void check_erase2_testset(struct maple_tree *mt, @@ -888,12 +894,13 @@ static noinline void check_erase2_testset(struct maple_tree *mt, for (int i = 0; i < size; i += 3) { unsigned long s_min, s_max; unsigned long e_min, e_max; + void *value = NULL; MA_STATE(mas_start, mt, set[i+1], set[i+1]); MA_STATE(mas_end, mt, set[i+2]-1, set[i+2]-1); mt_set_non_kernel(127); #if check_erase2_debug - pr_warn("%s: %d %s %lu - %lu\n", __func__, i, - set[i] == STORE ? "store" : "erase", + pr_err("%s: %d %s %lu - %lu\n", __func__, i, + ec_type_str(set[i]), set[i+1], set[i+2]-1); #endif @@ -901,7 +908,14 @@ static noinline void check_erase2_testset(struct maple_tree *mt, e_entry = mas_range_load(&mas_end, &e_min, &e_max, false); switch(set[i]) { + case SNULL: + if ((s_min == set[i+1]) && (s_max == set[i+2]-1)) + entry_cnt--; + + erase_check_store_range(mt, set, i + 1, value); + break; case STORE: + value = xa_mk_value(set[i + 1]); if ((s_min == e_min) && (s_max == e_max)) { if (!entry_cnt) entry_cnt++; @@ -938,8 +952,7 @@ static noinline void check_erase2_testset(struct maple_tree *mt, entry_cnt = entry_cnt - cnt + 1; } - erase_check_store_range(mt, set, i + 1, - xa_mk_value(set[i+1])); + erase_check_store_range(mt, set, i + 1, value); break; case ERASE: check_erase(mt, set[i+1], xa_mk_value(set[i+1])); @@ -948,22 +961,23 @@ static noinline void check_erase2_testset(struct maple_tree *mt, } mt_validate(mt); #if check_erase2_debug - pr_warn("Done\n"); + mt_dump(mt); + pr_err("Done\n"); #endif check = 0; addr = 0; mt_for_each(mt, foo, addr, ULONG_MAX) { -#if check_erase2_debug - pr_warn("mt: %lu -> %p\n", addr+1, foo); +#if check_erase2_debug > 1 + pr_err("mt: %lu -> %p\n", addr+1, foo); #endif check++; if (check > entry_cnt) break; } -#if check_erase2_debug - pr_warn("mt_for_each %d and cnt %d\n", check, entry_cnt); +#if check_erase2_debug > 1 + pr_err("mt_for_each %d and cnt %d\n", check, entry_cnt); #endif MT_BUG_ON(mt, check != entry_cnt); @@ -975,16 +989,16 @@ static noinline void check_erase2_testset(struct maple_tree *mt, mas_for_each(&mas, foo, ULONG_MAX) { if (mas_retry(&mas, foo)) continue; -#if check_erase2_debug - pr_warn("mas: %lu -> %p\n", addr+1, foo); +#if check_erase2_debug > 1 + pr_err("mas: %lu -> %p\n", addr+1, foo); #endif check++; if (check > entry_cnt) break; } rcu_read_unlock(); -#if check_erase2_debug - pr_warn("mas_for_each %d and cnt %d\n", check, entry_cnt); +#if check_erase2_debug > 1 + pr_err("mas_for_each %d and cnt %d\n", check, entry_cnt); #endif MT_BUG_ON(mt, check != entry_cnt); @@ -9432,6 +9446,290 @@ STORE, 140373518684160, 140373518688256,//: ffffa2e7b05fec00 STORE, 140373518688256, 140373518692352,//: ffffa2e7bfbdcd80 STORE, 140373518692352, 140373518696448,//: ffffa2e7b0749e40 }; + unsigned long set14[] = { +STORE, 140737488347136, 140737488351231, +STORE, 140731667996672, 140737488351231, +SNULL, 140731668000767, 140737488351231, +STORE, 140731667996672, 140731668000767, +STORE, 140731667865600, 140731668000767, +STORE, 94077521272832, 94077521313791, +SNULL, 94077521301503, 94077521313791, +STORE, 94077521272832, 94077521301503, +STORE, 94077521301504, 94077521313791, +ERASE, 94077521301504, 94077521313791, +STORE, 94077521305600, 94077521313791, +STORE, 139826134630400, 139826136883199, +SNULL, 139826134773759, 139826136883199, +STORE, 139826134630400, 139826134773759, +STORE, 139826134773760, 139826136883199, +ERASE, 139826134773760, 139826136883199, +STORE, 139826136870912, 139826136879103, +STORE, 139826136879104, 139826136883199, +STORE, 140731668013056, 140731668017151, +STORE, 140731668000768, 140731668013055, +STORE, 139826136862720, 139826136870911, +STORE, 139826132406272, 139826134630399, +SNULL, 139826134056959, 139826134630399, +STORE, 139826132406272, 139826134056959, +STORE, 139826134056960, 139826134630399, +SNULL, 139826134056960, 139826134626303, +STORE, 139826134626304, 139826134630399, +STORE, 139826134056960, 139826134626303, +ERASE, 139826134056960, 139826134626303, +STORE, 139826134056960, 139826134626303, +ERASE, 139826134626304, 139826134630399, +STORE, 139826134626304, 139826134630399, +STORE, 139826136842240, 139826136862719, +STORE, 139826130022400, 139826132406271, +SNULL, 139826130022400, 139826130288639, +STORE, 139826130288640, 139826132406271, +STORE, 139826130022400, 139826130288639, +SNULL, 139826132381695, 139826132406271, +STORE, 139826130288640, 139826132381695, +STORE, 139826132381696, 139826132406271, +SNULL, 139826132381696, 139826132402175, +STORE, 139826132402176, 139826132406271, +STORE, 139826132381696, 139826132402175, +ERASE, 139826132381696, 139826132402175, +STORE, 139826132381696, 139826132402175, +ERASE, 139826132402176, 139826132406271, +STORE, 139826132402176, 139826132406271, +STORE, 139826127806464, 139826130022399, +SNULL, 139826127806464, 139826127904767, +STORE, 139826127904768, 139826130022399, +STORE, 139826127806464, 139826127904767, +SNULL, 139826129997823, 139826130022399, +STORE, 139826127904768, 139826129997823, +STORE, 139826129997824, 139826130022399, +SNULL, 139826129997824, 139826130006015, +STORE, 139826130006016, 139826130022399, +STORE, 139826129997824, 139826130006015, +ERASE, 139826129997824, 139826130006015, +STORE, 139826129997824, 139826130006015, +ERASE, 139826130006016, 139826130022399, +STORE, 139826130006016, 139826130022399, +STORE, 139826124009472, 139826127806463, +SNULL, 139826124009472, 139826125668351, +STORE, 139826125668352, 139826127806463, +STORE, 139826124009472, 139826125668351, +SNULL, 139826127765503, 139826127806463, +STORE, 139826125668352, 139826127765503, +STORE, 139826127765504, 139826127806463, +SNULL, 139826127765504, 139826127790079, +STORE, 139826127790080, 139826127806463, +STORE, 139826127765504, 139826127790079, +ERASE, 139826127765504, 139826127790079, +STORE, 139826127765504, 139826127790079, +ERASE, 139826127790080, 139826127806463, +STORE, 139826127790080, 139826127806463, +STORE, 139826121748480, 139826124009471, +SNULL, 139826121748480, 139826121900031, +STORE, 139826121900032, 139826124009471, +STORE, 139826121748480, 139826121900031, +SNULL, 139826123993087, 139826124009471, +STORE, 139826121900032, 139826123993087, +STORE, 139826123993088, 139826124009471, +SNULL, 139826123993088, 139826124001279, +STORE, 139826124001280, 139826124009471, +STORE, 139826123993088, 139826124001279, +ERASE, 139826123993088, 139826124001279, +STORE, 139826123993088, 139826124001279, +ERASE, 139826124001280, 139826124009471, +STORE, 139826124001280, 139826124009471, +STORE, 139826119626752, 139826121748479, +SNULL, 139826119626752, 139826119643135, +STORE, 139826119643136, 139826121748479, +STORE, 139826119626752, 139826119643135, +SNULL, 139826121740287, 139826121748479, +STORE, 139826119643136, 139826121740287, +STORE, 139826121740288, 139826121748479, +ERASE, 139826121740288, 139826121748479, +STORE, 139826121740288, 139826121748479, +STORE, 139826136834048, 139826136842239, +STORE, 139826117496832, 139826119626751, +SNULL, 139826117496832, 139826117525503, +STORE, 139826117525504, 139826119626751, +STORE, 139826117496832, 139826117525503, +SNULL, 139826119618559, 139826119626751, +STORE, 139826117525504, 139826119618559, +STORE, 139826119618560, 139826119626751, +ERASE, 139826119618560, 139826119626751, +STORE, 139826119618560, 139826119626751, +STORE, 139826115244032, 139826117496831, +SNULL, 139826115244032, 139826115395583, +STORE, 139826115395584, 139826117496831, +STORE, 139826115244032, 139826115395583, +SNULL, 139826117488639, 139826117496831, +STORE, 139826115395584, 139826117488639, +STORE, 139826117488640, 139826117496831, +ERASE, 139826117488640, 139826117496831, +STORE, 139826117488640, 139826117496831, +STORE, 139826113073152, 139826115244031, +SNULL, 139826113073152, 139826113142783, +STORE, 139826113142784, 139826115244031, +STORE, 139826113073152, 139826113142783, +SNULL, 139826115235839, 139826115244031, +STORE, 139826113142784, 139826115235839, +STORE, 139826115235840, 139826115244031, +ERASE, 139826115235840, 139826115244031, +STORE, 139826115235840, 139826115244031, +STORE, 139826109861888, 139826113073151, +SNULL, 139826109861888, 139826110939135, +STORE, 139826110939136, 139826113073151, +STORE, 139826109861888, 139826110939135, +SNULL, 139826113036287, 139826113073151, +STORE, 139826110939136, 139826113036287, +STORE, 139826113036288, 139826113073151, +ERASE, 139826113036288, 139826113073151, +STORE, 139826113036288, 139826113073151, +STORE, 139826107727872, 139826109861887, +SNULL, 139826107727872, 139826107756543, +STORE, 139826107756544, 139826109861887, +STORE, 139826107727872, 139826107756543, +SNULL, 139826109853695, 139826109861887, +STORE, 139826107756544, 139826109853695, +STORE, 139826109853696, 139826109861887, +ERASE, 139826109853696, 139826109861887, +STORE, 139826109853696, 139826109861887, +STORE, 139826105417728, 139826107727871, +SNULL, 139826105417728, 139826105622527, +STORE, 139826105622528, 139826107727871, +STORE, 139826105417728, 139826105622527, +SNULL, 139826107719679, 139826107727871, +STORE, 139826105622528, 139826107719679, +STORE, 139826107719680, 139826107727871, +ERASE, 139826107719680, 139826107727871, +STORE, 139826107719680, 139826107727871, +STORE, 139826136825856, 139826136842239, +STORE, 139826103033856, 139826105417727, +SNULL, 139826103033856, 139826103226367, +STORE, 139826103226368, 139826105417727, +STORE, 139826103033856, 139826103226367, +SNULL, 139826105319423, 139826105417727, +STORE, 139826103226368, 139826105319423, +STORE, 139826105319424, 139826105417727, +ERASE, 139826105319424, 139826105417727, +STORE, 139826105319424, 139826105417727, +STORE, 139826100916224, 139826103033855, +SNULL, 139826100916224, 139826100932607, +STORE, 139826100932608, 139826103033855, +STORE, 139826100916224, 139826100932607, +SNULL, 139826103025663, 139826103033855, +STORE, 139826100932608, 139826103025663, +STORE, 139826103025664, 139826103033855, +ERASE, 139826103025664, 139826103033855, +STORE, 139826103025664, 139826103033855, +STORE, 139826098348032, 139826100916223, +SNULL, 139826098348032, 139826098814975, +STORE, 139826098814976, 139826100916223, +STORE, 139826098348032, 139826098814975, +SNULL, 139826100908031, 139826100916223, +STORE, 139826098814976, 139826100908031, +STORE, 139826100908032, 139826100916223, +ERASE, 139826100908032, 139826100916223, +STORE, 139826100908032, 139826100916223, +STORE, 139826096234496, 139826098348031, +SNULL, 139826096234496, 139826096246783, +STORE, 139826096246784, 139826098348031, +STORE, 139826096234496, 139826096246783, +SNULL, 139826098339839, 139826098348031, +STORE, 139826096246784, 139826098339839, +STORE, 139826098339840, 139826098348031, +ERASE, 139826098339840, 139826098348031, +STORE, 139826098339840, 139826098348031, +STORE, 139826094055424, 139826096234495, +SNULL, 139826094055424, 139826094133247, +STORE, 139826094133248, 139826096234495, +STORE, 139826094055424, 139826094133247, +SNULL, 139826096226303, 139826096234495, +STORE, 139826094133248, 139826096226303, +STORE, 139826096226304, 139826096234495, +ERASE, 139826096226304, 139826096234495, +STORE, 139826096226304, 139826096234495, +STORE, 139826136817664, 139826136842239, +STORE, 139826091937792, 139826094055423, +SNULL, 139826091937792, 139826091954175, +STORE, 139826091954176, 139826094055423, +STORE, 139826091937792, 139826091954175, +SNULL, 139826094047231, 139826094055423, +STORE, 139826091954176, 139826094047231, +STORE, 139826094047232, 139826094055423, +ERASE, 139826094047232, 139826094055423, +STORE, 139826094047232, 139826094055423, +STORE, 139826136809472, 139826136842239, +SNULL, 139826127781887, 139826127790079, +STORE, 139826127765504, 139826127781887, +STORE, 139826127781888, 139826127790079, +SNULL, 139826094051327, 139826094055423, +STORE, 139826094047232, 139826094051327, +STORE, 139826094051328, 139826094055423, +SNULL, 139826096230399, 139826096234495, +STORE, 139826096226304, 139826096230399, +STORE, 139826096230400, 139826096234495, +SNULL, 139826098343935, 139826098348031, +STORE, 139826098339840, 139826098343935, +STORE, 139826098343936, 139826098348031, +SNULL, 139826130001919, 139826130006015, +STORE, 139826129997824, 139826130001919, +STORE, 139826130001920, 139826130006015, +SNULL, 139826100912127, 139826100916223, +STORE, 139826100908032, 139826100912127, +STORE, 139826100912128, 139826100916223, +SNULL, 139826103029759, 139826103033855, +STORE, 139826103025664, 139826103029759, +STORE, 139826103029760, 139826103033855, +SNULL, 139826105413631, 139826105417727, +STORE, 139826105319424, 139826105413631, +STORE, 139826105413632, 139826105417727, +SNULL, 139826107723775, 139826107727871, +STORE, 139826107719680, 139826107723775, +STORE, 139826107723776, 139826107727871, +SNULL, 139826109857791, 139826109861887, +STORE, 139826109853696, 139826109857791, +STORE, 139826109857792, 139826109861887, +SNULL, 139826113044479, 139826113073151, +STORE, 139826113036288, 139826113044479, +STORE, 139826113044480, 139826113073151, +SNULL, 139826115239935, 139826115244031, +STORE, 139826115235840, 139826115239935, +STORE, 139826115239936, 139826115244031, +SNULL, 139826117492735, 139826117496831, +STORE, 139826117488640, 139826117492735, +STORE, 139826117492736, 139826117496831, +SNULL, 139826119622655, 139826119626751, +STORE, 139826119618560, 139826119622655, +STORE, 139826119622656, 139826119626751, +SNULL, 139826121744383, 139826121748479, +STORE, 139826121740288, 139826121744383, +STORE, 139826121744384, 139826121748479, +SNULL, 139826123997183, 139826124001279, +STORE, 139826123993088, 139826123997183, +STORE, 139826123997184, 139826124001279, +SNULL, 139826132398079, 139826132402175, +STORE, 139826132381696, 139826132398079, +STORE, 139826132398080, 139826132402175, +SNULL, 139826134622207, 139826134626303, +STORE, 139826134056960, 139826134622207, +STORE, 139826134622208, 139826134626303, +SNULL, 94077521309695, 94077521313791, +STORE, 94077521305600, 94077521309695, +STORE, 94077521309696, 94077521313791, +SNULL, 139826136875007, 139826136879103, +STORE, 139826136870912, 139826136875007, +STORE, 139826136875008, 139826136879103, +ERASE, 139826136842240, 139826136862719, +STORE, 94077554049024, 94077554184191, +STORE, 139826136543232, 139826136842239, +STORE, 139826136276992, 139826136842239, +STORE, 139826136010752, 139826136842239, +STORE, 139826135744512, 139826136842239, +SNULL, 139826136543231, 139826136842239, +STORE, 139826135744512, 139826136543231, +STORE, 139826136543232, 139826136842239, +SNULL, 139826136543232, 139826136809471, +STORE, 139826136809472, 139826136842239, +STORE, 139826136543232, 139826136809471, + }; int cnt = 0; mt_set_non_kernel(3); @@ -9522,8 +9820,11 @@ STORE, 140373518692352, 140373518696448,//: ffffa2e7b0749e40 rcu_read_lock(); mas_get_unmapped_area_rev(&mas, 0, 140373518663680, 4096); rcu_read_unlock(); - printk("index = %lu - %lu\n", mas.index, mas.last); - mt_dump(mt); + mtree_destroy(mt); + + mtree_init(mt, MAPLE_ALLOC_RANGE); + check_erase2_testset(mt, set14, ARRAY_SIZE(set14)); + rcu_barrier(); mtree_destroy(mt); } @@ -9642,15 +9943,17 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt) for (i = 0; i < ARRAY_SIZE(holes); i += 3) { + /* pr_debug("Search from %lu-%lu for gap %lu should be at %lu\n", min, holes[i+1]>>12, holes[i+2]>>12, holes[i] >> 12); + */ MT_BUG_ON(mt, mas_get_unmapped_area_rev(&mas, min, holes[i+1] >> 12, holes[i+2] >> 12)); - printk("Found %lu %lu\n", mas.index, mas.last); - printk("gap %lu %lu\n", (holes[i] >> 12), - (holes[i+1] >> 12)); + //printk("Found %lu %lu\n", mas.index, mas.last); + //printk("gap %lu %lu\n", (holes[i] >> 12), + // (holes[i+1] >> 12)); MT_BUG_ON(mt, mas.last + 1 != (holes[i+1] >> 12)); MT_BUG_ON(mt, mas.index != (holes[i+1] >> 12) - (holes[i+2] >> 12)); min = holes[i+1] >> 12; @@ -9658,11 +9961,13 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt) } for (i = 0; i < req_range_cnt; i += 5) { + /* pr_debug("\tRequest between %lu-%lu size %lu, should get %lu\n", req_range[i] >> 12, (req_range[i + 1] >> 12) - 1, req_range[i+2] >> 12, req_range[i+3] >> 12); + */ check_mtree_alloc_rrange(mt, req_range[i] >> 12, // start req_range[i+1] >> 12, // end @@ -9803,13 +10108,13 @@ static noinline void check_alloc_range(struct maple_tree *mt) mas_reset(&mas); } for (i = 0; i < req_range_cnt; i += 5) { - /* +#if 0 pr_debug("\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); - */ +#endif check_mtree_alloc_range(mt, req_range[i] >> 12, // start req_range[i+1] >> 12, // end -- 2.50.1