| Message ID | 20230711035444.526-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> [230710 23:55]: > Make mas_validate_gaps() check whether the offset in the metadata points > to the largest gap. By the way, simplify this function. > > Add the verification that gaps beyond the node limit are zero. > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com> > --- > lib/maple_tree.c | 78 ++++++++++++++++++++++++++---------------------- > 1 file changed, 42 insertions(+), 36 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 6a8982146338..a5776fab1875 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)); > - int i; > + unsigned long *pivots = ma_pivots(node, mt); > + unsigned 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,59 @@ 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 > i) { > + 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); > + } > + > + MT_BUG_ON(mas->tree, !gaps); > + for (i++ ; i < mt_slot_count(mte); i++) { > + if (gaps[i] != 0) { > + pr_err("gap %p[%u] beyond node limit != 0\n", > + node, i); > + MT_BUG_ON(mas->tree, 1); > + } > + } > + } > + > if (mte_is_root(mte)) > return; > > @@ -7059,10 +7067,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 >
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6a8982146338..a5776fab1875 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)); - int i; + unsigned long *pivots = ma_pivots(node, mt); + unsigned 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,59 @@ 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 > i) { + 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); + } + + MT_BUG_ON(mas->tree, !gaps); + for (i++ ; i < mt_slot_count(mte); i++) { + if (gaps[i] != 0) { + pr_err("gap %p[%u] beyond node limit != 0\n", + node, i); + MT_BUG_ON(mas->tree, 1); + } + } + } + if (mte_is_root(mte)) return; @@ -7059,10 +7067,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. Add the verification that gaps beyond the node limit are zero. Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com> --- lib/maple_tree.c | 78 ++++++++++++++++++++++++++---------------------- 1 file changed, 42 insertions(+), 36 deletions(-)