| Message ID | 20230707101057.29326-7-zhangpeng.00@bytedance.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Improve the validation for maple tree and some cleanup | expand |
* Peng Zhang <zhangpeng.00@bytedance.com> [230707 06:11]: > Instead of using mas_first_entry() to find the leftmost leaf, use a > simple loop instead. Remove an unneeded check for root node. To make > the error message more accurate, check pivots first and then slots, > because checking slots depend on the node limit pivot to break the loop. > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> > --- > lib/maple_tree.c | 21 +++++++++++---------- > 1 file changed, 11 insertions(+), 10 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index e84a042b6d84..3aede7deaa26 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -7260,21 +7260,22 @@ void mt_validate(struct maple_tree *mt) > if (!mas_searchable(&mas)) > goto done; > > - mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node)); > + while (!mte_is_leaf(mas.node)) > + mas_descend(&mas); > + > while (!mas_is_none(&mas)) { > MAS_WARN_ON(&mas, mte_dead_node(mas.node)); > - if (!mte_is_root(mas.node)) { > - end = mas_data_end(&mas); > - if (MAS_WARN_ON(&mas, > - (end < mt_min_slot_count(mas.node)) && > - (mas.max != ULONG_MAX))) { > - pr_err("Invalid size %u of %p\n", end, > - mas_mn(&mas)); > - } > + end = mas_data_end(&mas); > + if (MAS_WARN_ON(&mas, > + (end < mt_min_slot_count(mas.node)) && > + (mas.max != ULONG_MAX))) { This line can be reformatted now that it is not as nested. > + pr_err("Invalid size %u of %p\n", end, > + mas_mn(&mas)); Ditto here. > } > + > mas_validate_parent_slot(&mas); > - mas_validate_child_slot(&mas); > mas_validate_limits(&mas); > + mas_validate_child_slot(&mas); > if (mt_is_alloc(mt)) > mas_validate_gaps(&mas); > mas_dfs_postorder(&mas, ULONG_MAX); > -- > 2.20.1 > >
在 2023/7/7 23:02, Liam R. Howlett 写道: > * Peng Zhang <zhangpeng.00@bytedance.com> [230707 06:11]: >> Instead of using mas_first_entry() to find the leftmost leaf, use a >> simple loop instead. Remove an unneeded check for root node. To make >> the error message more accurate, check pivots first and then slots, >> because checking slots depend on the node limit pivot to break the loop. >> >> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> >> --- >> lib/maple_tree.c | 21 +++++++++++---------- >> 1 file changed, 11 insertions(+), 10 deletions(-) >> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> index e84a042b6d84..3aede7deaa26 100644 >> --- a/lib/maple_tree.c >> +++ b/lib/maple_tree.c >> @@ -7260,21 +7260,22 @@ void mt_validate(struct maple_tree *mt) >> if (!mas_searchable(&mas)) >> goto done; >> >> - mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node)); >> + while (!mte_is_leaf(mas.node)) >> + mas_descend(&mas); >> + >> while (!mas_is_none(&mas)) { >> MAS_WARN_ON(&mas, mte_dead_node(mas.node)); >> - if (!mte_is_root(mas.node)) { >> - end = mas_data_end(&mas); >> - if (MAS_WARN_ON(&mas, >> - (end < mt_min_slot_count(mas.node)) && >> - (mas.max != ULONG_MAX))) { >> - pr_err("Invalid size %u of %p\n", end, >> - mas_mn(&mas)); >> - } >> + end = mas_data_end(&mas); >> + if (MAS_WARN_ON(&mas, >> + (end < mt_min_slot_count(mas.node)) && >> + (mas.max != ULONG_MAX))) { > > This line can be reformatted now that it is not as nested. > >> + pr_err("Invalid size %u of %p\n", end, >> + mas_mn(&mas)); > > Ditto here. Thanks, I'll reformat it. > >> } >> + >> mas_validate_parent_slot(&mas); >> - mas_validate_child_slot(&mas); >> mas_validate_limits(&mas); >> + mas_validate_child_slot(&mas); >> if (mt_is_alloc(mt)) >> mas_validate_gaps(&mas); >> mas_dfs_postorder(&mas, ULONG_MAX); >> -- >> 2.20.1 >> >>
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index e84a042b6d84..3aede7deaa26 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7260,21 +7260,22 @@ void mt_validate(struct maple_tree *mt) if (!mas_searchable(&mas)) goto done; - mas_first_entry(&mas, mas_mn(&mas), ULONG_MAX, mte_node_type(mas.node)); + while (!mte_is_leaf(mas.node)) + mas_descend(&mas); + while (!mas_is_none(&mas)) { MAS_WARN_ON(&mas, mte_dead_node(mas.node)); - if (!mte_is_root(mas.node)) { - end = mas_data_end(&mas); - if (MAS_WARN_ON(&mas, - (end < mt_min_slot_count(mas.node)) && - (mas.max != ULONG_MAX))) { - pr_err("Invalid size %u of %p\n", end, - mas_mn(&mas)); - } + end = mas_data_end(&mas); + if (MAS_WARN_ON(&mas, + (end < mt_min_slot_count(mas.node)) && + (mas.max != ULONG_MAX))) { + pr_err("Invalid size %u of %p\n", end, + mas_mn(&mas)); } + mas_validate_parent_slot(&mas); - mas_validate_child_slot(&mas); mas_validate_limits(&mas); + mas_validate_child_slot(&mas); if (mt_is_alloc(mt)) mas_validate_gaps(&mas); mas_dfs_postorder(&mas, ULONG_MAX);
Instead of using mas_first_entry() to find the leftmost leaf, use a simple loop instead. Remove an unneeded check for root node. To make the error message more accurate, check pivots first and then slots, because checking slots depend on the node limit pivot to break the loop. Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> --- lib/maple_tree.c | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-)