* Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [230710 05:44]:
>
>
> 在 2023/7/7 22:45, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [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@xxxxxxxxxxxxx>
> > > ---
> > > 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@xxxxxxxxxxxxxxxxxxx
> > > https://lists.infradead.org/mailman/listinfo/maple-tree
