| Message ID | 20230707101057.29326-4-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]: > Make mas_validate_gaps() check whether the offset in the metadata points > to the largest gap. By the way, simplify this function. > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> > --- > lib/maple_tree.c | 68 +++++++++++++++++++++++------------------------- > 1 file changed, 33 insertions(+), 35 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 6a8982146338..1fe8b6a787dd 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -6983,15 +6983,16 @@ EXPORT_SYMBOL_GPL(mt_dump); > static void mas_validate_gaps(struct ma_state *mas) > { > struct maple_enode *mte = mas->node; > - struct maple_node *p_mn; > + struct maple_node *p_mn, *node = mte_to_node(mte); > + enum maple_type mt = mte_node_type(mas->node); > unsigned long gap = 0, max_gap = 0; > unsigned long p_end, p_start = mas->min; > - unsigned char p_slot; > + unsigned char p_slot, offset; > unsigned long *gaps = NULL; > - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte)); > + unsigned long *pivots = ma_pivots(node, mt); > int i; > > - if (ma_is_dense(mte_node_type(mte))) { > + if (ma_is_dense(mt)) { > for (i = 0; i < mt_slot_count(mte); i++) { > if (mas_get_slot(mas, i)) { > if (gap > max_gap) > @@ -7004,52 +7005,51 @@ static void mas_validate_gaps(struct ma_state *mas) > goto counted; > } > > - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte)); > + gaps = ma_gaps(node, mt); > for (i = 0; i < mt_slot_count(mte); i++) { > - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte)); > + p_end = mas_logical_pivot(mas, pivots, i, mt); > > if (!gaps) { > - if (mas_get_slot(mas, i)) { > - gap = 0; > - goto not_empty; > - } > - > - gap += p_end - p_start + 1; > + if (!mas_get_slot(mas, i)) > + gap = p_end - p_start + 1; > } else { > void *entry = mas_get_slot(mas, i); > > gap = gaps[i]; > - if (!entry) { > - if (gap != p_end - p_start + 1) { > - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n", > - mas_mn(mas), i, > - mas_get_slot(mas, i), gap, > - p_end, p_start); > - mt_dump(mas->tree, mt_dump_hex); > - > - MT_BUG_ON(mas->tree, > - gap != p_end - p_start + 1); > - } > - } else { > - if (gap > p_end - p_start + 1) { > - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", > - mas_mn(mas), i, gap, p_end, p_start, > - p_end - p_start + 1); > - MT_BUG_ON(mas->tree, > - gap > p_end - p_start + 1); > - } > + MT_BUG_ON(mas->tree, !entry); > + > + if (gap > p_end - p_start + 1) { > + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", > + mas_mn(mas), i, gap, p_end, p_start, > + p_end - p_start + 1); > + MT_BUG_ON(mas->tree, > + gap > p_end - p_start + 1); Your change above points out that we are not verifying all gaps are zero in non-leaf nodes after p_end >= mas->max. If we don't have a 'no gap' indicator then this may be an issue, or maybe it already is an issue? > } > } > > if (gap > max_gap) > max_gap = gap; > -not_empty: > + > p_start = p_end + 1; > if (p_end >= mas->max) > break; > } > > counted: > + if (mt == maple_arange_64) { We could loop through the remainder of the gaps here pretty easily. > + offset = ma_meta_gap(node, mt); > + if (offset > mt_slots[mt]) { > + pr_err("gap offset %p[%u] is invalid\n", node, offset); > + MT_BUG_ON(mas->tree, 1); > + } > + > + if (gaps[offset] != max_gap) { > + pr_err("gap %p[%u] is not the largest gap %lu\n", > + node, offset, max_gap); > + MT_BUG_ON(mas->tree, 1); > + } > + } > + > if (mte_is_root(mte)) > return; > > @@ -7059,10 +7059,8 @@ static void mas_validate_gaps(struct ma_state *mas) > if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { > pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap); > mt_dump(mas->tree, mt_dump_hex); > + MT_BUG_ON(mas->tree, 1); > } > - > - MT_BUG_ON(mas->tree, > - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap); > } > > static void mas_validate_parent_slot(struct ma_state *mas) > -- > 2.20.1 > > > -- > maple-tree mailing list > maple-tree@lists.infradead.org > https://lists.infradead.org/mailman/listinfo/maple-tree
在 2023/7/7 22:45, Liam R. Howlett 写道: > * Peng Zhang <zhangpeng.00@bytedance.com> [230707 06:11]: >> Make mas_validate_gaps() check whether the offset in the metadata points >> to the largest gap. By the way, simplify this function. >> >> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> >> --- >> lib/maple_tree.c | 68 +++++++++++++++++++++++------------------------- >> 1 file changed, 33 insertions(+), 35 deletions(-) >> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> index 6a8982146338..1fe8b6a787dd 100644 >> --- a/lib/maple_tree.c >> +++ b/lib/maple_tree.c >> @@ -6983,15 +6983,16 @@ EXPORT_SYMBOL_GPL(mt_dump); >> static void mas_validate_gaps(struct ma_state *mas) >> { >> struct maple_enode *mte = mas->node; >> - struct maple_node *p_mn; >> + struct maple_node *p_mn, *node = mte_to_node(mte); >> + enum maple_type mt = mte_node_type(mas->node); >> unsigned long gap = 0, max_gap = 0; >> unsigned long p_end, p_start = mas->min; >> - unsigned char p_slot; >> + unsigned char p_slot, offset; >> unsigned long *gaps = NULL; >> - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte)); >> + unsigned long *pivots = ma_pivots(node, mt); >> int i; >> >> - if (ma_is_dense(mte_node_type(mte))) { >> + if (ma_is_dense(mt)) { >> for (i = 0; i < mt_slot_count(mte); i++) { >> if (mas_get_slot(mas, i)) { >> if (gap > max_gap) >> @@ -7004,52 +7005,51 @@ static void mas_validate_gaps(struct ma_state *mas) >> goto counted; >> } >> >> - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte)); >> + gaps = ma_gaps(node, mt); >> for (i = 0; i < mt_slot_count(mte); i++) { >> - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte)); >> + p_end = mas_logical_pivot(mas, pivots, i, mt); >> >> if (!gaps) { >> - if (mas_get_slot(mas, i)) { >> - gap = 0; >> - goto not_empty; >> - } >> - >> - gap += p_end - p_start + 1; >> + if (!mas_get_slot(mas, i)) >> + gap = p_end - p_start + 1; >> } else { >> void *entry = mas_get_slot(mas, i); >> >> gap = gaps[i]; >> - if (!entry) { >> - if (gap != p_end - p_start + 1) { >> - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n", >> - mas_mn(mas), i, >> - mas_get_slot(mas, i), gap, >> - p_end, p_start); >> - mt_dump(mas->tree, mt_dump_hex); >> - >> - MT_BUG_ON(mas->tree, >> - gap != p_end - p_start + 1); >> - } >> - } else { >> - if (gap > p_end - p_start + 1) { >> - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", >> - mas_mn(mas), i, gap, p_end, p_start, >> - p_end - p_start + 1); >> - MT_BUG_ON(mas->tree, >> - gap > p_end - p_start + 1); >> - } >> + MT_BUG_ON(mas->tree, !entry); >> + >> + if (gap > p_end - p_start + 1) { >> + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", >> + mas_mn(mas), i, gap, p_end, p_start, >> + p_end - p_start + 1); >> + MT_BUG_ON(mas->tree, >> + gap > p_end - p_start + 1); > > Your change above points out that we are not verifying all gaps are zero > in non-leaf nodes after p_end >= mas->max. If we don't have a 'no gap' > indicator then this may be an issue, or maybe it already is an issue? If we don't have a 'no gap' indicator, why is there an issue? Are you worried that meta_gap is wrongly pointing to the gap after the node limit? If so we can verify that meta_gap points to a gap within the node limit. > >> } >> } >> >> if (gap > max_gap) >> max_gap = gap; >> -not_empty: >> + >> p_start = p_end + 1; >> if (p_end >= mas->max) >> break; >> } >> >> counted: >> + if (mt == maple_arange_64) { > > We could loop through the remainder of the gaps here pretty easily. In this way, it can be verified that the gaps after the node limit are 0. > >> + offset = ma_meta_gap(node, mt); >> + if (offset > mt_slots[mt]) { >> + pr_err("gap offset %p[%u] is invalid\n", node, offset); >> + MT_BUG_ON(mas->tree, 1); >> + } >> + >> + if (gaps[offset] != max_gap) { >> + pr_err("gap %p[%u] is not the largest gap %lu\n", >> + node, offset, max_gap); >> + MT_BUG_ON(mas->tree, 1); >> + } >> + } >> + >> if (mte_is_root(mte)) >> return; >> >> @@ -7059,10 +7059,8 @@ static void mas_validate_gaps(struct ma_state *mas) >> if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { >> pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap); >> mt_dump(mas->tree, mt_dump_hex); >> + MT_BUG_ON(mas->tree, 1); >> } >> - >> - MT_BUG_ON(mas->tree, >> - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap); >> } >> >> static void mas_validate_parent_slot(struct ma_state *mas) >> -- >> 2.20.1 >> >> >> -- >> maple-tree mailing list >> maple-tree@lists.infradead.org >> https://lists.infradead.org/mailman/listinfo/maple-tree
* Peng Zhang <zhangpeng.00@bytedance.com> [230710 05:44]: > > > 在 2023/7/7 22:45, Liam R. Howlett 写道: > > * Peng Zhang <zhangpeng.00@bytedance.com> [230707 06:11]: > > > Make mas_validate_gaps() check whether the offset in the metadata points > > > to the largest gap. By the way, simplify this function. > > > > > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> > > > --- > > > lib/maple_tree.c | 68 +++++++++++++++++++++++------------------------- > > > 1 file changed, 33 insertions(+), 35 deletions(-) > > > > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > > > index 6a8982146338..1fe8b6a787dd 100644 > > > --- a/lib/maple_tree.c > > > +++ b/lib/maple_tree.c > > > @@ -6983,15 +6983,16 @@ EXPORT_SYMBOL_GPL(mt_dump); > > > static void mas_validate_gaps(struct ma_state *mas) > > > { > > > struct maple_enode *mte = mas->node; > > > - struct maple_node *p_mn; > > > + struct maple_node *p_mn, *node = mte_to_node(mte); > > > + enum maple_type mt = mte_node_type(mas->node); > > > unsigned long gap = 0, max_gap = 0; > > > unsigned long p_end, p_start = mas->min; > > > - unsigned char p_slot; > > > + unsigned char p_slot, offset; > > > unsigned long *gaps = NULL; > > > - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte)); > > > + unsigned long *pivots = ma_pivots(node, mt); > > > int i; > > > - if (ma_is_dense(mte_node_type(mte))) { > > > + if (ma_is_dense(mt)) { > > > for (i = 0; i < mt_slot_count(mte); i++) { > > > if (mas_get_slot(mas, i)) { > > > if (gap > max_gap) > > > @@ -7004,52 +7005,51 @@ static void mas_validate_gaps(struct ma_state *mas) > > > goto counted; > > > } > > > - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte)); > > > + gaps = ma_gaps(node, mt); > > > for (i = 0; i < mt_slot_count(mte); i++) { > > > - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte)); > > > + p_end = mas_logical_pivot(mas, pivots, i, mt); > > > if (!gaps) { > > > - if (mas_get_slot(mas, i)) { > > > - gap = 0; > > > - goto not_empty; > > > - } > > > - > > > - gap += p_end - p_start + 1; > > > + if (!mas_get_slot(mas, i)) > > > + gap = p_end - p_start + 1; > > > } else { > > > void *entry = mas_get_slot(mas, i); > > > gap = gaps[i]; > > > - if (!entry) { > > > - if (gap != p_end - p_start + 1) { > > > - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n", > > > - mas_mn(mas), i, > > > - mas_get_slot(mas, i), gap, > > > - p_end, p_start); > > > - mt_dump(mas->tree, mt_dump_hex); > > > - > > > - MT_BUG_ON(mas->tree, > > > - gap != p_end - p_start + 1); > > > - } > > > - } else { > > > - if (gap > p_end - p_start + 1) { > > > - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", > > > - mas_mn(mas), i, gap, p_end, p_start, > > > - p_end - p_start + 1); > > > - MT_BUG_ON(mas->tree, > > > - gap > p_end - p_start + 1); > > > - } > > > + MT_BUG_ON(mas->tree, !entry); > > > + > > > + if (gap > p_end - p_start + 1) { > > > + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", > > > + mas_mn(mas), i, gap, p_end, p_start, > > > + p_end - p_start + 1); > > > + MT_BUG_ON(mas->tree, > > > + gap > p_end - p_start + 1); > > > > Your change above points out that we are not verifying all gaps are zero > > in non-leaf nodes after p_end >= mas->max. If we don't have a 'no gap' > > indicator then this may be an issue, or maybe it already is an issue? > If we don't have a 'no gap' indicator, why is there an issue? Are you > worried that meta_gap is wrongly pointing to the gap after the node > limit? If so we can verify that meta_gap points to a gap within the node > limit. I'm saying we aren't checking that gaps beyond the node limit are zero. I wasn't concerned about the meta_gap pointing beyond the node limit, but it would probably be a good check too. > > > > > } > > > } > > > if (gap > max_gap) > > > max_gap = gap; > > > -not_empty: > > > + > > > p_start = p_end + 1; > > > if (p_end >= mas->max) > > > break; > > > } > > > counted: > > > + if (mt == maple_arange_64) { > > > > We could loop through the remainder of the gaps here pretty easily. > In this way, it can be verified that the gaps after the node limit are > 0. Yes, I think that's a good idea. I don't believe we have a check for this anywhere. > > > > > > + offset = ma_meta_gap(node, mt); > > > + if (offset > mt_slots[mt]) { > > > + pr_err("gap offset %p[%u] is invalid\n", node, offset); > > > + MT_BUG_ON(mas->tree, 1); > > > + } > > > + > > > + if (gaps[offset] != max_gap) { > > > + pr_err("gap %p[%u] is not the largest gap %lu\n", > > > + node, offset, max_gap); > > > + MT_BUG_ON(mas->tree, 1); > > > + } > > > + } > > > + > > > if (mte_is_root(mte)) > > > return; > > > @@ -7059,10 +7059,8 @@ static void mas_validate_gaps(struct ma_state *mas) > > > if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { > > > pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap); > > > mt_dump(mas->tree, mt_dump_hex); > > > + MT_BUG_ON(mas->tree, 1); > > > } > > > - > > > - MT_BUG_ON(mas->tree, > > > - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap); > > > } > > > static void mas_validate_parent_slot(struct ma_state *mas) > > > -- > > > 2.20.1 > > > > > > > > > -- > > > maple-tree mailing list > > > maple-tree@lists.infradead.org > > > https://lists.infradead.org/mailman/listinfo/maple-tree
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6a8982146338..1fe8b6a787dd 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -6983,15 +6983,16 @@ EXPORT_SYMBOL_GPL(mt_dump); static void mas_validate_gaps(struct ma_state *mas) { struct maple_enode *mte = mas->node; - struct maple_node *p_mn; + struct maple_node *p_mn, *node = mte_to_node(mte); + enum maple_type mt = mte_node_type(mas->node); unsigned long gap = 0, max_gap = 0; unsigned long p_end, p_start = mas->min; - unsigned char p_slot; + unsigned char p_slot, offset; unsigned long *gaps = NULL; - unsigned long *pivots = ma_pivots(mte_to_node(mte), mte_node_type(mte)); + unsigned long *pivots = ma_pivots(node, mt); int i; - if (ma_is_dense(mte_node_type(mte))) { + if (ma_is_dense(mt)) { for (i = 0; i < mt_slot_count(mte); i++) { if (mas_get_slot(mas, i)) { if (gap > max_gap) @@ -7004,52 +7005,51 @@ static void mas_validate_gaps(struct ma_state *mas) goto counted; } - gaps = ma_gaps(mte_to_node(mte), mte_node_type(mte)); + gaps = ma_gaps(node, mt); for (i = 0; i < mt_slot_count(mte); i++) { - p_end = mas_logical_pivot(mas, pivots, i, mte_node_type(mte)); + p_end = mas_logical_pivot(mas, pivots, i, mt); if (!gaps) { - if (mas_get_slot(mas, i)) { - gap = 0; - goto not_empty; - } - - gap += p_end - p_start + 1; + if (!mas_get_slot(mas, i)) + gap = p_end - p_start + 1; } else { void *entry = mas_get_slot(mas, i); gap = gaps[i]; - if (!entry) { - if (gap != p_end - p_start + 1) { - pr_err("%p[%u] -> %p %lu != %lu - %lu + 1\n", - mas_mn(mas), i, - mas_get_slot(mas, i), gap, - p_end, p_start); - mt_dump(mas->tree, mt_dump_hex); - - MT_BUG_ON(mas->tree, - gap != p_end - p_start + 1); - } - } else { - if (gap > p_end - p_start + 1) { - pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", - mas_mn(mas), i, gap, p_end, p_start, - p_end - p_start + 1); - MT_BUG_ON(mas->tree, - gap > p_end - p_start + 1); - } + MT_BUG_ON(mas->tree, !entry); + + if (gap > p_end - p_start + 1) { + pr_err("%p[%u] %lu >= %lu - %lu + 1 (%lu)\n", + mas_mn(mas), i, gap, p_end, p_start, + p_end - p_start + 1); + MT_BUG_ON(mas->tree, + gap > p_end - p_start + 1); } } if (gap > max_gap) max_gap = gap; -not_empty: + p_start = p_end + 1; if (p_end >= mas->max) break; } counted: + if (mt == maple_arange_64) { + offset = ma_meta_gap(node, mt); + if (offset > mt_slots[mt]) { + pr_err("gap offset %p[%u] is invalid\n", node, offset); + MT_BUG_ON(mas->tree, 1); + } + + if (gaps[offset] != max_gap) { + pr_err("gap %p[%u] is not the largest gap %lu\n", + node, offset, max_gap); + MT_BUG_ON(mas->tree, 1); + } + } + if (mte_is_root(mte)) return; @@ -7059,10 +7059,8 @@ static void mas_validate_gaps(struct ma_state *mas) if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { pr_err("gap %p[%u] != %lu\n", p_mn, p_slot, max_gap); mt_dump(mas->tree, mt_dump_hex); + MT_BUG_ON(mas->tree, 1); } - - MT_BUG_ON(mas->tree, - ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap); } static void mas_validate_parent_slot(struct ma_state *mas)
Make mas_validate_gaps() check whether the offset in the metadata points to the largest gap. By the way, simplify this function. Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> --- lib/maple_tree.c | 68 +++++++++++++++++++++++------------------------- 1 file changed, 33 insertions(+), 35 deletions(-)