maple_tree: current split may result in deficient node
Subsystems (3)
cover maple_tree: current split may result in deficient node
Here are 4 patches related to correctly split node.
Patch 1: adjust the calculation of split
Patch 2: add a test case to check deficient split
Patch 3: the min value for mab_calc_split() seems not correct Patch 4: during validation, we skip right most node on each level
Wei Yang (4):
maple_tree: current split may result in deficient node
maple_tree: add a test check deficient node
maple_tree: use the correct min to calculate split
maple_tree: only root node could be deficient
lib/maple_tree.c | 8 ++++---- lib/test_maple_tree.c | 28 ++++++++++++++++++++++++++++ 2 files changed, 32 insertions(+), 4 deletions(-)
Signature · 1 line
2.34.1
PATCH 1/4 maple_tree: current split may result in deficient node
Current split would result in deficient node in rare case.
For example:
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE)
for (count = 0; count < 10; count++) {
mas_set(&mas, count);
mas_store(&mas, xa_mk_value(count));
}
for (count = 20; count < 39; count++) {
mas_set(&mas, count);
mas_store(&mas, xa_mk_value(count));
}
for (count = 10; count < 12; count++) {
mas_set(&mas, count);
mas_store(&mas, xa_mk_value(count));
}
mt_validate(mt);The validation would report deficient node.
The reason is we don't leave enough room for the right node.
The deficient check is (end < mt_min_slot[]), which means a node must have at least (mt_min_slot[] + 1) number of data. The right node's index range is [split + 1, b_end], which means the number of data in right node is (b_end - (split + 1) + 1) = (b_end - split).
Then the check between the number of data and (mt_min_slot[] + 1) is (b_end - split) > (mt_min_slot[] + 1), which leads to (b_end - split - 1) > (mt_min_slot[]).
--- lib/maple_tree.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
lib/maple_tree.c +2 -2
@@ -1831,7 +1831,7 @@ static inline int mab_no_null_split(struct maple_big_node *b_node,* still be sufficient, then increment the split on NULL. */ if ((split < slot_count -1 ) && - (b_node->b_end - split) > (mt_min_slots[b_node->type])) + (b_node->b_end - split -1 ) > (mt_min_slots[b_node->type])) split++;else split--;
@@ -1896,7 +1896,7 @@ static inline int mab_calc_split(struct ma_state *mas,*/ while ((split < slot_count -1 ) && ((bn->pivot[split] - min) < slot_count -1 ) && - (b_end - split > slot_min)) + (b_end - split -1 > slot_min)) split++; }
Signature · 1 line
2.34.1
Quoted 21 lines · Wei Yang
Current split would result in deficient node in rare case.
For example:
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE) for (count = 0; count < 10; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); } for (count = 20; count < 39; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); } for (count = 10; count < 12; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); } mt_validate(mt);
Quoted 1 line
The validation would report deficient node.
I think you can explain it better than this?
If we fill a left node with the right node being already full, the split of the left node will result in the new middle node being insufficient.
Quoted 2 lines
The reason is we don't leave enough room for the right node.
The reason is we don't leave enough data for the node on the right of the split. The node on the right has too much room from what I see?
Quoted 9 lines
The deficient check is (end < mt_min_slot[]), which means a node must have at least (mt_min_slot[] + 1) number of data. The right node's index range is [split + 1,
b_end], which means the number of data in right node is (b_end- (split + 1) + 1) = (b_end- split).Then the check between the number of data and (mt_min_slot[] + 1) is (
b_end- split) > (mt_min_slot[] + 1), which leads to (b_end- split - 1) > (mt_min_slot[]).
Don't state the code, it's stated below.
I am still concerned about jitter that this patch set may cause.
Quoted 34 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)lib/maple_tree.c +2
-2@@ -1831,7 +1831,7 @@ static inline int mab_no_null_split(struct maple_big_node *b_node,* still be sufficient, then increment the split on NULL. */ if ((split < slot_count -1 ) && - (b_node->b_end - split) > (mt_min_slots[b_node->type])) + (b_node->b_end - split -1 ) > (mt_min_slots[b_node->type])) split++;else split--;@@ -1896,7 +1896,7 @@ static inline int mab_calc_split(struct ma_state *mas,*/ while ((split < slot_count -1 ) && ((bn->pivot[split] - min) < slot_count -1 ) && - (b_end - split > slot_min)) + (b_end - split -1 > slot_min)) split++; }Signature · 1 line
2.34.1
Quoted 22 lines · Liam R. Howlett
Quoted 21 lines · Wei Yang
Current split would result in deficient node in rare case.
For example:
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE) for (count = 0; count < 10; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); } for (count = 20; count < 39; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); } for (count = 10; count < 12; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); } mt_validate(mt);
Quoted 7 lines
Quoted 1 line
The validation would report deficient node.
I think you can explain it better than this?
If we fill a left node with the right node being already full, the split of the left node will result in the new middle node being insufficient.
Thanks, I will put the explanation later.
Quoted 6 lines
Quoted 2 lines
The reason is we don't leave enough room for the right node.
The reason is we don't leave enough data for the node on the right of the split. The node on the right has too much room from what I see?
Too much room? Or too much empty room?
I may missed here.
Quoted 11 lines
Quoted 9 lines
The deficient check is (end < mt_min_slot[]), which means a node must have at least (mt_min_slot[] + 1) number of data. The right node's index range is [split + 1,
b_end], which means the number of data in right node is (b_end- (split + 1) + 1) = (b_end- split).Then the check between the number of data and (mt_min_slot[] + 1) is (
b_end- split) > (mt_min_slot[] + 1), which leads to (b_end- split - 1) > (mt_min_slot[]).Don't state the code, it's stated below.
Sure, will remote this part.
Quoted 2 lines
I am still concerned about jitter that this patch set may cause.
Per my understanding, a jitter is a removal which cause a deficient node which is just created from a split, right?
Quoted 35 lines
Quoted 35 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)lib/maple_tree.c +2
-2@@ -1831,7 +1831,7 @@ static inline int mab_no_null_split(struct maple_big_node *b_node,* still be sufficient, then increment the split on NULL. */ if ((split < slot_count -1 ) && - (b_node->b_end - split) > (mt_min_slots[b_node->type])) + (b_node->b_end - split -1 ) > (mt_min_slots[b_node->type])) split++;else split--;@@ -1896,7 +1896,7 @@ static inline int mab_calc_split(struct ma_state *mas,*/ while ((split < slot_count -1 ) && ((bn->pivot[split] - min) < slot_count -1 ) && - (b_end - split > slot_min)) + (b_end - split -1 > slot_min)) split++; }Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me
Quoted 1 line · Liam R. Howlett
* Wei Yang <[email protected]> [241019 22:46]:
[...]
Quoted 5 lines
Don't state the code, it's stated below.
I am still concerned about jitter that this patch set may cause.
If my understanding is correct, the change here won't cause worse jitter.
Below is the dump result when this case happens.
Let's name those nodes: n1, n2, n3.
maple_tree(0x5611079e1680) flags 9, height 2 root 0x615000001c1e
0-18446744073709551615: node 0x615000001c00 depth 0 type 3 parent 0x5611079e1681 contents: 0 8 18446744073709551577 0 0 0 0 0 0 0 | 02 02| 0x61500000210c 10 0x615000001f0c 23 0x61500000120c 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil)
0-10: node 0x615000002100 depth 1 type 1 parent 0x615000001c06 contents: 0x1 0 0x3 1 0x5 2 0x7 3 0x9 4 0xb 5 0xd 6 0xf 7 0x11 8 0x13 9 0x15 10 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0xa
0: value 0 (0x0) [0x1]
1: value 1 (0x1) [0x3]
2: value 2 (0x2) [0x5]
3: value 3 (0x3) [0x7]
4: value 4 (0x4) [0x9]
5: value 5 (0x5) [0xb]
6: value 6 (0x6) [0xd]
7: value 7 (0x7) [0xf]
8: value 8 (0x8) [0x11]
9: value 9 (0x9) [0x13]
10: value 10 (0xa) [0x15]
11-23: node 0x615000001f00 depth 1 type 1 parent 0x615000001c0e contents: 0x17 11 (nil) 19 0x29 20 0x2b 21 0x2d 22 0x2f 23 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x5
11: value 11 (0xb) [0x17]
12-19: (nil)
20: value 20 (0x14) [0x29]
21: value 21 (0x15) [0x2b]
22: value 22 (0x16) [0x2d]
23: value 23 (0x17) [0x2f]
24-18446744073709551615: node 0x615000001200 depth 1 type 1 parent 0x615000001c16 contents: 0x31 24 0x33 25 0x35 26 0x37 27 0x39 28 0x3b 29 0x3d 30 0x3f 31 0x41 32 0x43 33 0x45 34 0x47 35 0x49 36 0x4b 37 0x4d 38 (nil)
24: value 24 (0x18) [0x31]
25: value 25 (0x19) [0x33]
26: value 26 (0x1a) [0x35]
27: value 27 (0x1b) [0x37]
28: value 28 (0x1c) [0x39]
29: value 29 (0x1d) [0x3b]
30: value 30 (0x1e) [0x3d]
31: value 31 (0x1f) [0x3f]
32: value 32 (0x20) [0x41]
33: value 33 (0x21) [0x43]
34: value 34 (0x22) [0x45]
35: value 35 (0x23) [0x47]
36: value 36 (0x24) [0x49]
37: value 37 (0x25) [0x4b]
38: value 38 (0x26) [0x4d]
39-18446744073709551615: (nil)Since n2 is already deficient, removal a data from n2 would need rebalance, which is a jitter if my understanding is correct.
After this change, removal a data from n2 would also result in a deficient node. So this is not worse than current behavior.
Do you have other cases in concern?
Signature · 2 lines
Wei Yang Help you, Help me
Quoted 53 lines · Wei Yang
Quoted 1 line · Liam R. Howlett
* Wei Yang <[email protected]> [241019 22:46]:
[...]
Quoted 5 lines
Don't state the code, it's stated below.
I am still concerned about jitter that this patch set may cause.
If my understanding is correct, the change here won't cause worse jitter.
Below is the dump result when this case happens.
Let's name those nodes: n1, n2, n3.
maple_tree(0x5611079e1680)flags 9, height 2 root0x615000001c1e
0-18446744073709551615: node0x615000001c00depth 0 type 3 parent0x5611079e1681contents: 0 8 18446744073709551577 0 0 0 0 0 0 0 | 02 02|0x61500000210c100x615000001f0c230x61500000120c18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil)
0-10: node0x615000002100depth 1 type 1 parent0x615000001c06contents:0x100x310x520x730x940xb50xd60xf70x1180x1390x1510 (nil) 0 (nil) 0 (nil) 0 (nil) 00xa0: value 0 (0x0) [0x1] 1: value 1 (0x1) [0x3] 2: value 2 (0x2) [0x5] 3: value 3 (0x3) [0x7] 4: value 4 (0x4) [0x9] 5: value 5 (0x5) [0xb] 6: value 6 (0x6) [0xd] 7: value 7 (0x7) [0xf] 8: value 8 (0x8) [0x11] 9: value 9 (0x9) [0x13] 10: value 10 (0xa) [0x15] 11-23: node 0x615000001f00 depth 1 type 1 parent 0x615000001c0e contents: 0x17 11 (nil) 19 0x29 20 0x2b 21 0x2d 22 0x2f 23 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x5 11: value 11 (0xb) [0x17] 12-19: (nil) 20: value 20 (0x14) [0x29] 21: value 21 (0x15) [0x2b] 22: value 22 (0x16) [0x2d] 23: value 23 (0x17) [0x2f] 24-18446744073709551615: node 0x615000001200 depth 1 type 1 parent 0x615000001c16 contents: 0x31 24 0x33 25 0x35 26 0x37 27 0x39 28 0x3b 29 0x3d 30 0x3f 31 0x41 32 0x43 33 0x45 34 0x47 35 0x49 36 0x4b 37 0x4d 38 (nil) 24: value 24 (0x18) [0x31] 25: value 25 (0x19) [0x33] 26: value 26 (0x1a) [0x35] 27: value 27 (0x1b) [0x37] 28: value 28 (0x1c) [0x39] 29: value 29 (0x1d) [0x3b] 30: value 30 (0x1e) [0x3d] 31: value 31 (0x1f) [0x3f] 32: value 32 (0x20) [0x41] 33: value 33 (0x21) [0x43] 34: value 34 (0x22) [0x45] 35: value 35 (0x23) [0x47] 36: value 36 (0x24) [0x49] 37: value 37 (0x25) [0x4b] 38: value 38 (0x26) [0x4d] 39-18446744073709551615: (nil)
Quoted 7 lines
Since n2 is already deficient, removal a data from n2 would need rebalance, which is a jitter if my understanding is correct.
After this change, removal a data from n2 would also result in a deficient node. So this is not worse than current behavior.
Do you have other cases in concern?
My concern comes when we have a node with 16 entries, then add one then delete one, then add one, then delete one, then add one, then delete one...
I am not worried that you fixed the insufficient node, I am worried that the splitting and rebalancing target will become too strict and cause us to allocate nodes over and over - this can be even worse if it causes a tree expansion/contraction further up.
There are a few benchmarks that do this more than it happens in the real world, but it is still important to handle this case for real world cases.
Thanks,
Liam
PATCH 2/4 maple_tree: add a test check deficient node
In reply to Wei YangAdd a test to assert when resulting a deficient node on splitting.
We can achieve this by build a tree with two nodes. With the left node with consecutive data from 0 and leave some room for the final insert to locate in left node. And the right node a full node to force the split happens on the left node.
Another simple way to trigger this is to inserting from 0 to 16 till the first split happens. The new right node is deficient. But current validation skip the right node. This will be fixed in next patch.
--- lib/test_maple_tree.c | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+)
lib/test_maple_tree.c +28 -0
@@ -1563,6 +1563,30 @@ static noinline void __init check_root_expand(struct maple_tree *mt)mas_unlock (&mas); } +static noinline void __init check_deficient_node(struct maple_tree *mt) +{ +MA_STATE (mas, mt,0 ,0 ); +int count; + +mas_lock (&mas); +for (count =0 ; count <10 ; count++) { +mas_set (&mas, count); +mas_store_gfp (&mas,xa_mk_value (count),GFP_KERNEL ); + } + +for (count =20 ; count <39 ; count++) { +mas_set (&mas, count); +mas_store_gfp (&mas,xa_mk_value (count),GFP_KERNEL ); + } + +for (count =10 ; count <12 ; count++) { +mas_set (&mas, count); +mas_store_gfp (&mas,xa_mk_value (count),GFP_KERNEL ); + } +mas_unlock (&mas); +mt_validate (mt); +} + static noinline void __init check_gap_combining(struct maple_tree *mt) {struct maple_enode *mn1, *mn2;
@@ -3804,6 +3828,10 @@ static int __init maple_tree_seed(void)check_root_expand (&tree);mtree_destroy (&tree); +mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE ); +check_deficient_node (&tree); +mtree_destroy (&tree); +mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE );check_iteration (&tree);mtree_destroy (&tree);
Signature · 1 line
2.34.1
PATCH 3/4 maple_tree: use the correct min to calculate split
In reply to Wei YangThe check in mab_calc_split() is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min.
First we may encounter a pivot[split] smaller than min. For example:
mt_init_flags(mt, 0);
for (count = 0; count <= 240; count++) {
mas_set(&mas, count);
mas_store(&mas, xa_mk_value(count));
}On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min).
Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect.
Since we are now calculating the split of mas->node, we should use the mas->min instead of prev_l_mas.min.
--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/maple_tree.c +1 -1
@@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)if (mas_push_data (mas, height, &mast, false))break ; - split =mab_calc_split (mas, b_node, &mid_split, prev_l_mas.min); + split =mab_calc_split (mas, b_node, &mid_split, mas->min);mast_split_data (&mast, mas, split);/* * Usually correct, mab_mas_cp in the above call overwrites
Signature · 1 line
2.34.1
Re: [PATCH 3/4] maple_tree: use the correct min to calculate split
Quoted 5 lines · Wei Yang
The check in
mab_calc_split()is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min.First we may encounter a pivot[split] smaller than min. For example:
Quoted 8 lines
mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); }On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min).
This is fine.
There is an open work item to make it more accurate at higher levels, but it's not a problem as it is.
Each level upwards needs a better 'minimum span', meaning that the node should have at least mas.min - mas.min + level * something.
It works today for leaves, somewhat.
Quoted 3 lines
Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect.
No, it is set to 0. Not initialized would cause random data loss.
See MA_STATE() in the header.
Quoted 3 lines
Since we are now calculating the split of
mas->node, we should use themas->mininstead of prev_l_mas.min.
This sounds reasonable, but considering what this number is used for, I don't see how it is working as well as it is today. I will need to look deeper into this.
Quoted 25 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/maple_tree.c +1
-1@@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)if (mas_push_data (mas, height, &mast, false))break ; - split =mab_calc_split (mas, b_node, &mid_split, prev_l_mas.min); + split =mab_calc_split (mas, b_node, &mid_split, mas->min);mast_split_data (&mast, mas, split);/* * Usually correct, mab_mas_cp in the above call overwrites Signature · 1 line
2.34.1
Re: [PATCH 3/4] maple_tree: use the correct min to calculate split
Quoted 34 lines · Liam R. Howlett
Quoted 5 lines · Wei Yang
The check in
mab_calc_split()is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min.First we may encounter a pivot[split] smaller than min. For example:
Quoted 8 lines
mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); }On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min).
This is fine.
There is an open work item to make it more accurate at higher levels, but it's not a problem as it is.
Each level upwards needs a better 'minimum span', meaning that the node should have at least mas.min - mas.min + level * something.
It works today for leaves, somewhat.
Quoted 3 lines
Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect.
No, it is set to 0. Not initialized would cause random data loss.
See
MA_STATE()in the header.Quoted 1 line
Quoted 6 lines
Quoted 2 lines
Since we are now calculating the split of
mas->node, we should use themas->mininstead of prev_l_mas.min.This sounds reasonable, but considering what this number is used for, I don't see how it is working as well as it is today. I will need to look deeper into this.
On examination of what is happening here, the only way this makes a difference during the testcases is if we have a node with 16 entries, we'll put 8 in the left today and 9 in the left after this change.
This only matters if the range is less than the slot count, so the real world implications of the change will be negligible, if anything.
I honestly think I'm trying to be too smart here, especially at the leaves. We should just set mid_split = 0; in that complex statement and drop the min argument all together. It hasn't made a difference besides the number of instructions executed.
Quoted 26 lines
Quoted 26 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/maple_tree.c +1
-1@@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)if (mas_push_data (mas, height, &mast, false))break ; - split =mab_calc_split (mas, b_node, &mid_split, prev_l_mas.min); + split =mab_calc_split (mas, b_node, &mid_split, mas->min);mast_split_data (&mast, mas, split);/* * Usually correct, mab_mas_cp in the above call overwrites Signature · 1 line
2.34.1
Re: [PATCH 3/4] maple_tree: use the correct min to calculate split
Quoted 47 lines · Liam R. Howlett
Quoted 34 lines · Liam R. Howlett
Quoted 5 lines · Wei Yang
The check in
mab_calc_split()is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min.First we may encounter a pivot[split] smaller than min. For example:
Quoted 8 lines
mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); }On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min).
This is fine.
There is an open work item to make it more accurate at higher levels, but it's not a problem as it is.
Each level upwards needs a better 'minimum span', meaning that the node should have at least mas.min - mas.min + level * something.
It works today for leaves, somewhat.
Quoted 3 lines
Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect.
No, it is set to 0. Not initialized would cause random data loss.
See
MA_STATE()in the header.Quoted 1 line
Quoted 6 lines
Quoted 2 lines
Since we are now calculating the split of
mas->node, we should use themas->mininstead of prev_l_mas.min.This sounds reasonable, but considering what this number is used for, I don't see how it is working as well as it is today. I will need to look deeper into this.
On examination of what is happening here, the only way this makes a difference during the testcases is if we have a node with 16 entries, we'll put 8 in the left today and 9 in the left after this change.
Quoted 8 lines
This only matters if the range is less than the slot count, so the real world implications of the change will be negligible, if anything.
I honestly think I'm trying to be too smart here, especially at the leaves. We should just set
mid_split= 0; in that complex statement and drop the min argument all together. It hasn't made a difference besides the number of instructions executed.
This looks good to me. And it looks we won't face jitter problem after this.
I need to take a through look.
Quoted 26 lines
Quoted 26 lines
Quoted 26 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/maple_tree.c +1
-1@@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)if (mas_push_data (mas, height, &mast, false))break ; - split =mab_calc_split (mas, b_node, &mid_split, prev_l_mas.min); + split =mab_calc_split (mas, b_node, &mid_split, mas->min);mast_split_data (&mast, mas, split);/* * Usually correct, mab_mas_cp in the above call overwrites Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me
Re: [PATCH 3/4] maple_tree: use the correct min to calculate split
In reply to Liam R. HowlettQuoted 43 lines · Liam R. Howlett
Quoted 34 lines · Liam R. Howlett
Quoted 5 lines · Wei Yang
The check in
mab_calc_split()is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min.First we may encounter a pivot[split] smaller than min. For example:
Quoted 8 lines
mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); }On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min).
This is fine.
There is an open work item to make it more accurate at higher levels, but it's not a problem as it is.
Each level upwards needs a better 'minimum span', meaning that the node should have at least mas.min - mas.min + level * something.
It works today for leaves, somewhat.
Quoted 3 lines
Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect.
No, it is set to 0. Not initialized would cause random data loss.
See
MA_STATE()in the header.Quoted 1 line
Quoted 6 lines
Quoted 2 lines
Since we are now calculating the split of
mas->node, we should use themas->mininstead of prev_l_mas.min.This sounds reasonable, but considering what this number is used for, I don't see how it is working as well as it is today. I will need to look deeper into this.
Quoted 7 lines
On examination of what is happening here, the only way this makes a difference during the testcases is if we have a node with 16 entries, we'll put 8 in the left today and 9 in the left after this change.
This only matters if the range is less than the slot count, so the real world implications of the change will be negligible, if anything.
Yes, maybe it only effect when there are all singleton.
Quoted 5 lines
I honestly think I'm trying to be too smart here, especially at the leaves. We should just set
mid_split= 0; in that complex statement and drop the min argument all together. It hasn't made a difference besides the number of instructions executed.
I have tried to remove those lines, so we got split = b_end / 2 and mid_split = 0. Tests all passed and kernel runs. (I guess in the real world, it behaves the same, since (bn->pivot[split] - min) is always bigger than 15.)
Since we call mab_calc_split() when b_end >= slot_count == 16, it means we get split == 16/2 == 8. So the new left|right node has data 9|8, this is friendly to jitter problem.
Quoted 26 lines
Quoted 26 lines
Quoted 26 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/maple_tree.c +1
-1@@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)if (mas_push_data (mas, height, &mast, false))break ; - split =mab_calc_split (mas, b_node, &mid_split, prev_l_mas.min); + split =mab_calc_split (mas, b_node, &mid_split, mas->min);mast_split_data (&mast, mas, split);/* * Usually correct, mab_mas_cp in the above call overwrites Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me
Re: [PATCH 3/4] maple_tree: use the correct min to calculate split
In reply to Liam R. HowlettQuoted 15 lines · Liam R. Howlett
Quoted 5 lines · Wei Yang
The check in
mab_calc_split()is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min.First we may encounter a pivot[split] smaller than min. For example:
Quoted 8 lines
mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); }On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min).
Quoted 7 lines
This is fine.
There is an open work item to make it more accurate at higher levels, but it's not a problem as it is.
Each level upwards needs a better 'minimum span', meaning that the node should have at least mas.min - mas.min + level * something.
Don't follow this.
First, I guess it is mas.max - mas.min?
Then there is sth related to level. But I don't see level is used for calculation. Would you mind sharing more your original thought?
Quoted 3 lines
It works today for leaves, somewhat.
To me it works by coincidence.
The condition check is:
(bn->pivot[split] - min) < (slot_count - 1)
while slot_count is a constent, 16 for leaf node.
And we always pass 0 as min, the condition for leaf is:
bn->pivot[split] < 15
For the mmap world, per my understanding, we won't expect an address is smaller than 15.
Quoted 8 lines
Quoted 3 lines
Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect.
No, it is set to 0. Not initialized would cause random data loss.
See
MA_STATE()in the header.
Right, I want to say not initialized to the value we want.
Will be more careful next time.
Quoted 33 lines
Quoted 3 lines
Since we are now calculating the split of
mas->node, we should use themas->mininstead of prev_l_mas.min.This sounds reasonable, but considering what this number is used for, I don't see how it is working as well as it is today. I will need to look deeper into this.
Quoted 25 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/maple_tree.c +1
-1@@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)if (mas_push_data (mas, height, &mast, false))break ; - split =mab_calc_split (mas, b_node, &mid_split, prev_l_mas.min); + split =mab_calc_split (mas, b_node, &mid_split, mas->min);mast_split_data (&mast, mas, split);/* * Usually correct, mab_mas_cp in the above call overwrites Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me
Re: [PATCH 3/4] maple_tree: use the correct min to calculate split
Quoted 21 lines · Wei Yang
Quoted 20 lines · Liam R. Howlett
Quoted 5 lines · Wei Yang
The check in
mab_calc_split()is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min.First we may encounter a pivot[split] smaller than min. For example:
Quoted 8 lines
mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); }On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min).
This is fine.
There is an open work item to make it more accurate at higher levels, but it's not a problem as it is.
Quoted 7 lines
Quoted 2 lines
Each level upwards needs a better 'minimum span', meaning that the node should have at least mas.min - mas.min + level * something.
Don't follow this.
First, I guess it is mas.max - mas.min?
No, the idea is that we could do better if we could keep the data more densely packed.
If we have singletons (all range of 1), and we have 10,000 singletons, then a parent node with 0 - 128 and a sibling of 129-257 makes no sense, there is nothing that can be inserting into the parents last two slots
- we can't split singletons smaller so we should have done a better job at splitting.
If you think of how this grows today, we split then rebalance until the left node is full and we have to split again. This could be better optimised to avoid multiple rebalances by doing something to push more data to the left based on the span of the children and the nodes. But we'd want to keep enough so some modifications to each node doesn't cause a rebalance in the opposite direction.
So a minimum span of parent nodes one level up from the leaves would be 16 * 10 = 160, so when we split we can push more to the left to try and get to 160 while keeping the right node sufficient. The math of the span would change based on how far up the tree we go, but would be easier to maintain.
I'd probably still want to split it 50/50 the first time, but it might make sense to push more on the next rebalance. so 10 => 6|5, 6|10 => 9|5, but maybe it's not worth the effort. I'm starting to think so, considering it's been ineffective to date. There is a chance that the active area gets moved to the more-full node and ends up splitting sooner anyways..
All of this will probably change when dense nodes come anyways.
Quoted 8 lines
Then there is sth related to level. But I don't see level is used for calculation. Would you mind sharing more your original thought?
Quoted 3 lines
It works today for leaves, somewhat.
To me it works by coincidence.
Seems like it.
Quoted 5 lines
The condition check is:
(bn->pivot[split] - min) < (
slot_count- 1)
Quoted 8 lines
while
slot_countis a constent, 16 for leaf node.And we always pass 0 as min, the condition for leaf is:
bn->pivot[split] < 15
For the mmap world, per my understanding, we won't expect an address is smaller than 15.
There are other users, but I think we should just drop this attempt at fancy stuff.
Quoted 51 lines
Quoted 9 lines
Quoted 4 lines
Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect.
No, it is set to 0. Not initialized would cause random data loss.
See
MA_STATE()in the header.Right, I want to say not initialized to the value we want.
Will be more careful next time.
Quoted 33 lines
Quoted 3 lines
Since we are now calculating the split of
mas->node, we should use themas->mininstead of prev_l_mas.min.This sounds reasonable, but considering what this number is used for, I don't see how it is working as well as it is today. I will need to look deeper into this.
Quoted 25 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/maple_tree.c +1
-1@@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)if (mas_push_data (mas, height, &mast, false))break ; - split =mab_calc_split (mas, b_node, &mid_split, prev_l_mas.min); + split =mab_calc_split (mas, b_node, &mid_split, mas->min);mast_split_data (&mast, mas, split);/* * Usually correct, mab_mas_cp in the above call overwrites Signature · 1 line
2.34.1Signature · 2 lines
Wei Yang Help you, Help me
Re: [PATCH 3/4] maple_tree: use the correct min to calculate split
Quoted 81 lines · Liam R. Howlett
Quoted 21 lines · Wei Yang
Quoted 20 lines · Liam R. Howlett
Quoted 5 lines · Wei Yang
The check in
mab_calc_split()is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min.First we may encounter a pivot[split] smaller than min. For example:
Quoted 8 lines
mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); }On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min).
This is fine.
There is an open work item to make it more accurate at higher levels, but it's not a problem as it is.
Quoted 7 lines
Quoted 2 lines
Each level upwards needs a better 'minimum span', meaning that the node should have at least mas.min - mas.min + level * something.
Don't follow this.
First, I guess it is mas.max - mas.min?
No, the idea is that we could do better if we could keep the data more densely packed.
If we have singletons (all range of 1), and we have 10,000 singletons, then a parent node with 0 - 128 and a sibling of 129-257 makes no sense, there is nothing that can be inserting into the parents last two slots
- we can't split singletons smaller so we should have done a better job at splitting.If you think of how this grows today, we split then rebalance until the left node is full and we have to split again. This could be better optimised to avoid multiple rebalances by doing something to push more data to the left based on the span of the children and the nodes. But we'd want to keep enough so some modifications to each node doesn't cause a rebalance in the opposite direction.
So a minimum span of parent nodes one level up from the leaves would be 16 * 10 = 160, so when we split we can push more to the left to try and get to 160 while keeping the right node sufficient. The math of the span would change based on how far up the tree we go, but would be easier to maintain.
I'd probably still want to split it 50/50 the first time, but it might make sense to push more on the next rebalance. so 10 => 6|5, 6|10 => 9|5, but maybe it's not worth the effort. I'm starting to think so, considering it's been ineffective to date. There is a chance that the active area gets moved to the more-full node and ends up splitting sooner anyways..
All of this will probably change when dense nodes come anyways.
Quoted 8 lines
Then there is sth related to level. But I don't see level is used for calculation. Would you mind sharing more your original thought?
Quoted 3 lines
It works today for leaves, somewhat.
To me it works by coincidence.
Seems like it.
Quoted 9 lines
The condition check is:
(bn->pivot[split] - min) < (
slot_count- 1)while
slot_countis a constent, 16 for leaf node.And we always pass 0 as min, the condition for leaf is:
Quoted 8 lines
Quoted 4 lines
bn->pivot[split] < 15
For the mmap world, per my understanding, we won't expect an address is smaller than 15.
There are other users, but I think we should just drop this attempt at fancy stuff.
You mean "set mid_split = 0 and drop the min argument all together" mentioned in another mail?
Quoted 51 lines
Quoted 51 lines
Quoted 9 lines
Quoted 4 lines
Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect.
No, it is set to 0. Not initialized would cause random data loss.
See
MA_STATE()in the header.Right, I want to say not initialized to the value we want.
Will be more careful next time.
Quoted 33 lines
Quoted 3 lines
Since we are now calculating the split of
mas->node, we should use themas->mininstead of prev_l_mas.min.This sounds reasonable, but considering what this number is used for, I don't see how it is working as well as it is today. I will need to look deeper into this.
Quoted 25 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/maple_tree.c +1
-1@@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)if (mas_push_data (mas, height, &mast, false))break ; - split =mab_calc_split (mas, b_node, &mid_split, prev_l_mas.min); + split =mab_calc_split (mas, b_node, &mid_split, mas->min);mast_split_data (&mast, mas, split);/* * Usually correct, mab_mas_cp in the above call overwrites Signature · 1 line
2.34.1Signature · 2 lines
Wei Yang Help you, Help me
Signature · 2 lines
Wei Yang Help you, Help me
Re: [PATCH 3/4] maple_tree: use the correct min to calculate split
Quoted 87 lines · Wei Yang
Quoted 86 lines · Liam R. Howlett
Quoted 21 lines · Wei Yang
Quoted 20 lines · Liam R. Howlett
Quoted 5 lines · Wei Yang
The check in
mab_calc_split()is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min.First we may encounter a pivot[split] smaller than min. For example:
Quoted 8 lines
mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); }On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min).
This is fine.
There is an open work item to make it more accurate at higher levels, but it's not a problem as it is.
Quoted 7 lines
Quoted 2 lines
Each level upwards needs a better 'minimum span', meaning that the node should have at least mas.min - mas.min + level * something.
Don't follow this.
First, I guess it is mas.max - mas.min?
No, the idea is that we could do better if we could keep the data more densely packed.
If we have singletons (all range of 1), and we have 10,000 singletons, then a parent node with 0 - 128 and a sibling of 129-257 makes no sense, there is nothing that can be inserting into the parents last two slots
- we can't split singletons smaller so we should have done a better job at splitting.If you think of how this grows today, we split then rebalance until the left node is full and we have to split again. This could be better optimised to avoid multiple rebalances by doing something to push more data to the left based on the span of the children and the nodes. But we'd want to keep enough so some modifications to each node doesn't cause a rebalance in the opposite direction.
So a minimum span of parent nodes one level up from the leaves would be 16 * 10 = 160, so when we split we can push more to the left to try and get to 160 while keeping the right node sufficient. The math of the span would change based on how far up the tree we go, but would be easier to maintain.
I'd probably still want to split it 50/50 the first time, but it might make sense to push more on the next rebalance. so 10 => 6|5, 6|10 => 9|5, but maybe it's not worth the effort. I'm starting to think so, considering it's been ineffective to date. There is a chance that the active area gets moved to the more-full node and ends up splitting sooner anyways..
All of this will probably change when dense nodes come anyways.
Quoted 8 lines
Then there is sth related to level. But I don't see level is used for calculation. Would you mind sharing more your original thought?
Quoted 3 lines
It works today for leaves, somewhat.
To me it works by coincidence.
Seems like it.
Quoted 13 lines
The condition check is:
(bn->pivot[split] - min) < (
slot_count- 1)while
slot_countis a constent, 16 for leaf node.And we always pass 0 as min, the condition for leaf is:
bn->pivot[split] < 15
For the mmap world, per my understanding, we won't expect an address is smaller than 15.
Quoted 6 lines
Quoted 3 lines
There are other users, but I think we should just drop this attempt at fancy stuff.
You mean "set
mid_split= 0 and drop the min argument all together" mentioned in another mail?
Yes, please. The more I think about this, the more I think we're wasting time trying to predict the future. And, although fun, it usually doesn't work out.
Quoted 56 lines
Quoted 52 lines
Quoted 52 lines
Quoted 10 lines
Quoted 5 lines
Second prev_l_mas.min is not initialized for the first iteration. This means on splitting leaf node, this value is mostly taking no effect.
No, it is set to 0. Not initialized would cause random data loss.
See
MA_STATE()in the header.Right, I want to say not initialized to the value we want.
Will be more careful next time.
Quoted 33 lines
Quoted 3 lines
Since we are now calculating the split of
mas->node, we should use themas->mininstead of prev_l_mas.min.This sounds reasonable, but considering what this number is used for, I don't see how it is working as well as it is today. I will need to look deeper into this.
Quoted 25 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/maple_tree.c +1
-1@@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)if (mas_push_data (mas, height, &mast, false))break ; - split =mab_calc_split (mas, b_node, &mid_split, prev_l_mas.min); + split =mab_calc_split (mas, b_node, &mid_split, mas->min);mast_split_data (&mast, mas, split);/* * Usually correct, mab_mas_cp in the above call overwrites Signature · 1 line
2.34.1Signature · 2 lines
Wei Yang Help you, Help meSignature · 2 lines
Wei Yang Help you, Help me
Re: [PATCH 3/4] maple_tree: use the correct min to calculate split
Quoted 92 lines · Liam R. Howlett
Quoted 91 lines · Wei Yang
Quoted 89 lines · Liam R. Howlett
Quoted 21 lines · Wei Yang
Quoted 20 lines · Liam R. Howlett
Quoted 5 lines · Wei Yang
The check in
mab_calc_split()is to make sure the gap between [0, split] won't be too small. But we don't pass the correct min.First we may encounter a pivot[split] smaller than min. For example:
Quoted 8 lines
mt_init_flags(mt, 0); for (count = 0; count <= 240; count++) { mas_set(&mas, count); mas_store(&mas, xa_mk_value(count)); }On splitting root for storing 240, the pivot[split] is smaller than min. This result a huge (pivot[split] - min).
This is fine.
There is an open work item to make it more accurate at higher levels, but it's not a problem as it is.
Quoted 7 lines
Quoted 2 lines
Each level upwards needs a better 'minimum span', meaning that the node should have at least mas.min - mas.min + level * something.
Don't follow this.
First, I guess it is mas.max - mas.min?
No, the idea is that we could do better if we could keep the data more densely packed.
If we have singletons (all range of 1), and we have 10,000 singletons, then a parent node with 0 - 128 and a sibling of 129-257 makes no sense, there is nothing that can be inserting into the parents last two slots
- we can't split singletons smaller so we should have done a better job at splitting.If you think of how this grows today, we split then rebalance until the left node is full and we have to split again. This could be better optimised to avoid multiple rebalances by doing something to push more data to the left based on the span of the children and the nodes. But we'd want to keep enough so some modifications to each node doesn't cause a rebalance in the opposite direction.
So a minimum span of parent nodes one level up from the leaves would be 16 * 10 = 160, so when we split we can push more to the left to try and get to 160 while keeping the right node sufficient. The math of the span would change based on how far up the tree we go, but would be easier to maintain.
I'd probably still want to split it 50/50 the first time, but it might make sense to push more on the next rebalance. so 10 => 6|5, 6|10 => 9|5, but maybe it's not worth the effort. I'm starting to think so, considering it's been ineffective to date. There is a chance that the active area gets moved to the more-full node and ends up splitting sooner anyways..
All of this will probably change when dense nodes come anyways.
Quoted 8 lines
Then there is sth related to level. But I don't see level is used for calculation. Would you mind sharing more your original thought?
Quoted 3 lines
It works today for leaves, somewhat.
To me it works by coincidence.
Seems like it.
Quoted 5 lines
The condition check is:
(bn->pivot[split] - min) < (
slot_count- 1)Quoted 8 lines
while
slot_countis a constent, 16 for leaf node.And we always pass 0 as min, the condition for leaf is:
bn->pivot[split] < 15
For the mmap world, per my understanding, we won't expect an address is smaller than 15.
There are other users, but I think we should just drop this attempt at fancy stuff.
Quoted 7 lines
Quoted 2 lines
You mean "set
mid_split= 0 and drop the min argument all together" mentioned in another mail?Yes, please. The more I think about this, the more I think we're wasting time trying to predict the future. And, although fun, it usually doesn't work out.
Agree, will prepare another version with this.
Thanks
Signature · 2 lines
Wei Yang Help you, Help me
PATCH 4/4 maple_tree: only root node could be deficient
In reply to Wei YangEach level's right most node could have (max == ULONG_MAX).
Only root node could be deficient.
--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/maple_tree.c +1 -1
@@ -7610,7 +7610,7 @@ void mt_validate(struct maple_tree *mt)MAS_WARN_ON (&mas,mte_dead_node (mas.node)); end =mas_data_end (&mas);if (MAS_WARN_ON (&mas, (end <mt_min_slot_count (mas.node)) && - (mas.max !=ULONG_MAX ))) { + (!mte_is_root (mas.node)))) {pr_err ("Invalid size %u of %p\n" , end,mas_mn (&mas)); }
Signature · 1 line
2.34.1
Re: [PATCH 4/4] maple_tree: only root node could be deficient
Quoted 1 line · Wei Yang
Each level's right most node could have (max ==
ULONG_MAX).
I think each levels right most node MUST have max == ULONX_MAX.
Quoted 2 lines
Only root node could be deficient.
No, root node deficient is defined as having 1 entry. Only the root node may be below the minimum data threshold.
Quoted 25 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)lib/maple_tree.c +1
-1@@ -7610,7 +7610,7 @@ void mt_validate(struct maple_tree *mt)MAS_WARN_ON (&mas,mte_dead_node (mas.node)); end =mas_data_end (&mas);if (MAS_WARN_ON (&mas, (end <mt_min_slot_count (mas.node)) && - (mas.max !=ULONG_MAX ))) { + (!mte_is_root (mas.node)))) {pr_err ("Invalid size %u of %p\n" , end,mas_mn (&mas)); }Signature · 1 line
2.34.1
Re: [PATCH 4/4] maple_tree: only root node could be deficient
Quoted 5 lines · Liam R. Howlett
Quoted 1 line · Wei Yang
Each level's right most node could have (max ==
ULONG_MAX).I think each levels right most node MUST have max ==
ULONX_MAX.
Yes, I should be more accurate.
Will adjust the message.
Quoted 6 lines
Quoted 2 lines
Only root node could be deficient.
No, root node deficient is defined as having 1 entry. Only the root node may be below the minimum data threshold.
Thanks, would rephrase it to
"Only the root node may be below the minimum data threshold.".
Quoted 9 lines
Quoted 9 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
Quoted 10 lines
lib/maple_tree.c void mt_validate(struct maple_tree *mt) · line 7613
Quoted 10 lines
lib/maple_tree.c +1
-1@@ -7610,7 +7610,7 @@ void mt_validate(struct maple_tree *mt)MAS_WARN_ON (&mas,mte_dead_node (mas.node)); end =mas_data_end (&mas);if (MAS_WARN_ON (&mas, (end <mt_min_slot_count (mas.node)) && - (mas.max !=ULONG_MAX ))) { + (!mte_is_root (mas.node)))) {
The change here looks good?
Quoted 1 line
lib/maple_tree.c void mt_validate(struct maple_tree *mt) · line 7614
Quoted 1 line
lib/maple_tree.c +0
-0pr_err ("Invalid size %u of %p\n" , end,mas_mn (&mas));
BTW, this patch could apply on top of current mm-unstable, since this line is changed. Will rebase it in next spin.
Quoted 5 lines
Quoted 5 lines
lib/maple_tree.c +0
-0}Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me
Quoted 1 line · Wei Yang
Here are 4 patches related to correctly split node.
So I haven't worked through your last bunch of patches and I had not fully responded to v3 before v4 came out.
These things take time to go through because you are changing fiddly things that may break things or cause regressions, but you keep sending a new series while another is in flight.
Quoted 2 lines
Patch 1: adjust the calculation of split
Split calculations exist with +/-1 to avoid jitter, but I will have to look at this in minute detail.
If you screw this up, then we may lose data.
Quoted 17 lines
Patch 2: add a test case to check deficient split
Patch 3: the min value formab_calc_split()seems not correct Patch 4: during validation, we skip right most node on each levelWei Yang (4):
maple_tree: current split may result in deficient node
maple_tree: add a test check deficient node
maple_tree: use the correct min to calculate split
maple_tree: only root node could be deficientlib/maple_tree.c | 8 ++++---- lib/test_maple_tree.c | 28 ++++++++++++++++++++++++++++ 2 files changed, 32 insertions(+), 4 deletions(-)Signature · 1 line
2.34.1
Quoted 6 lines · Liam R. Howlett
Quoted 1 line · Wei Yang
Here are 4 patches related to correctly split node.
So I haven't worked through your last bunch of patches and I had not fully responded to v3 before v4 came out.
Sorry, I thought you have finished v3.
I will check with you in later work.
Quoted 4 lines
These things take time to go through because you are changing fiddly things that may break things or cause regressions, but you keep sending a new series while another is in flight.
Thanks for you time on reviewing these. This really took efforts.
I will keep those in turn later. Is this what you preferred?
Quoted 25 lines
Quoted 2 lines
Patch 1: adjust the calculation of split
Split calculations exist with +/-1 to avoid jitter, but I will have to look at this in minute detail.
If you screw this up, then we may lose data.
Quoted 17 lines
Patch 2: add a test case to check deficient split
Patch 3: the min value formab_calc_split()seems not correct Patch 4: during validation, we skip right most node on each levelWei Yang (4):
maple_tree: current split may result in deficient node
maple_tree: add a test check deficient node
maple_tree: use the correct min to calculate split
maple_tree: only root node could be deficientlib/maple_tree.c | 8 ++++---- lib/test_maple_tree.c | 28 ++++++++++++++++++++++++++++ 2 files changed, 32 insertions(+), 4 deletions(-)Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me