Re: HOT chain validation in verify_heapam()

Hi,

To start with: I think this is an extremely helpful and important
feature. Both for checking production systems and for finding problems during
development.

> From 08fe01f5073c0a850541265494bb4a875bec7d3f Mon Sep 17 00:00:00 2001
> From: Himanshu Upadhyaya <himanshu(dot)upadhyaya(at)enterprisedb(dot)com>
> Date: Fri, 30 Sep 2022 17:44:56 +0530
> Subject: [PATCH v6] Implement HOT chain validation in verify_heapam()
>
> Himanshu Upadhyaya, reviewed by Robert Haas, Aleksander Alekseev
>
> Discussion: https://postgr.es/m/CAPF61jBBR2-iE-EmN_9v0hcQEfyz_17e5Lbb0%2Bu2%3D9ukA9sWmQ%40mail.gmail.com
> ---
> contrib/amcheck/verify_heapam.c | 207 ++++++++++++++++++++++
> src/bin/pg_amcheck/t/004_verify_heapam.pl | 192 ++++++++++++++++++--
> 2 files changed, 388 insertions(+), 11 deletions(-)
>
> diff --git a/contrib/amcheck/verify_heapam.c b/contrib/amcheck/verify_heapam.c
> index c875f3e5a2..007f7b2f37 100644
> --- a/contrib/amcheck/verify_heapam.c
> +++ b/contrib/amcheck/verify_heapam.c
> @@ -399,6 +399,9 @@ verify_heapam(PG_FUNCTION_ARGS)
> for (ctx.blkno = first_block; ctx.blkno <= last_block; ctx.blkno++)
> {
> OffsetNumber maxoff;
> + OffsetNumber predecessor[MaxOffsetNumber] = {0};
> + OffsetNumber successor[MaxOffsetNumber] = {0};
> + bool lp_valid[MaxOffsetNumber] = {false};
>
> CHECK_FOR_INTERRUPTS();
>
> @@ -433,6 +436,8 @@ verify_heapam(PG_FUNCTION_ARGS)
> for (ctx.offnum = FirstOffsetNumber; ctx.offnum <= maxoff;
> ctx.offnum = OffsetNumberNext(ctx.offnum))
> {
> + OffsetNumber nextoffnum;
> +
> ctx.itemid = PageGetItemId(ctx.page, ctx.offnum);
>
> /* Skip over unused/dead line pointers */
> @@ -469,6 +474,13 @@ verify_heapam(PG_FUNCTION_ARGS)
> report_corruption(&ctx,
> psprintf("line pointer redirection to unused item at offset %u",
> (unsigned) rdoffnum));
> +
> + /*
> + * make entry in successor array, redirected tuple will be
> + * validated at the time when we loop over successor array
> + */
> + successor[ctx.offnum] = rdoffnum;
> + lp_valid[ctx.offnum] = true;
> continue;
> }
>
> @@ -504,9 +516,197 @@ verify_heapam(PG_FUNCTION_ARGS)
> /* It should be safe to examine the tuple's header, at least */
> ctx.tuphdr = (HeapTupleHeader) PageGetItem(ctx.page, ctx.itemid);
> ctx.natts = HeapTupleHeaderGetNatts(ctx.tuphdr);
> + lp_valid[ctx.offnum] = true;
>
> /* Ok, ready to check this next tuple */
> check_tuple(&ctx);
> +
> + /*
> + * Add the data to the successor array if next updated tuple is in
> + * the same page. It will be used later to generate the
> + * predecessor array.
> + *
> + * We need to access the tuple's header to populate the
> + * predecessor array. However the tuple is not necessarily sanity
> + * checked yet so delaying construction of predecessor array until
> + * all tuples are sanity checked.
> + */
> + nextoffnum = ItemPointerGetOffsetNumber(&(ctx.tuphdr)->t_ctid);
> + if (ItemPointerGetBlockNumber(&(ctx.tuphdr)->t_ctid) == ctx.blkno &&
> + nextoffnum != ctx.offnum)
> + {
> + successor[ctx.offnum] = nextoffnum;
> + }

I don't really understand this logic - why can't we populate the predecessor
array, if we can construct a successor entry?

> + }
> +
> + /*
> + * Loop over offset and populate predecessor array from all entries
> + * that are present in successor array.
> + */
> + ctx.attnum = -1;
> + for (ctx.offnum = FirstOffsetNumber; ctx.offnum <= maxoff;
> + ctx.offnum = OffsetNumberNext(ctx.offnum))
> + {
> + ItemId curr_lp;
> + ItemId next_lp;
> + HeapTupleHeader curr_htup;
> + HeapTupleHeader next_htup;
> + TransactionId curr_xmax;
> + TransactionId next_xmin;
> +
> + OffsetNumber nextoffnum = successor[ctx.offnum];
> +
> + curr_lp = PageGetItemId(ctx.page, ctx.offnum);

Why do we get the item when nextoffnum is 0?

> + if (nextoffnum == 0 || !lp_valid[ctx.offnum] || !lp_valid[nextoffnum])
> + {
> + /*
> + * This is either the last updated tuple in the chain or a
> + * corruption raised for this tuple.
> + */

"or a corruption raised" isn't quite right grammatically.

> + continue;
> + }
> + if (ItemIdIsRedirected(curr_lp))
> + {
> + next_lp = PageGetItemId(ctx.page, nextoffnum);
> + if (ItemIdIsRedirected(next_lp))
> + {
> + report_corruption(&ctx,
> + psprintf("redirected line pointer pointing to another redirected line pointer at offset %u",
> + (unsigned) nextoffnum));
> + continue;
> + }
> + next_htup = (HeapTupleHeader) PageGetItem(ctx.page, next_lp);
> + if (!HeapTupleHeaderIsHeapOnly(next_htup))
> + {
> + report_corruption(&ctx,
> + psprintf("redirected tuple at line pointer offset %u is not heap only tuple",
> + (unsigned) nextoffnum));
> + }
> + if ((next_htup->t_infomask & HEAP_UPDATED) == 0)
> + {
> + report_corruption(&ctx,
> + psprintf("redirected tuple at line pointer offset %u is not heap updated tuple",
> + (unsigned) nextoffnum));
> + }
> + continue;
> + }
> +
> + /*
> + * Add a line pointer offset to the predecessor array if xmax is
> + * matching with xmin of next tuple (reaching via its t_ctid).
> + * Prior to PostgreSQL 9.4, we actually changed the xmin to
> + * FrozenTransactionId

I'm doubtful it's a good idea to try to validate the 9.4 case. The likelihood
of getting that right seems low and I don't see us gaining much by even trying.

> so we must add offset to predecessor
> + * array(irrespective of xmax-xmin matching) if updated tuple xmin
> + * is frozen, so that we can later do validation related to frozen
> + * xmin. Raise corruption if we have two tuples having the same
> + * predecessor.
> + * We add the offset to the predecessor array irrespective of the
> + * transaction (t_xmin) status. We will do validation related to
> + * the transaction status (and also all other validations) when we
> + * loop over the predecessor array.
> + */
> + curr_htup = (HeapTupleHeader) PageGetItem(ctx.page, curr_lp);
> + curr_xmax = HeapTupleHeaderGetUpdateXid(curr_htup);
> + next_lp = PageGetItemId(ctx.page, nextoffnum);
> + next_htup = (HeapTupleHeader) PageGetItem(ctx.page, next_lp);
> + next_xmin = HeapTupleHeaderGetXmin(next_htup);
> + if (TransactionIdIsValid(curr_xmax) &&
> + (TransactionIdEquals(curr_xmax, next_xmin) ||
> + next_xmin == FrozenTransactionId))
> + {
> + if (predecessor[nextoffnum] != 0)
> + {
> + report_corruption(&ctx,
> + psprintf("updated version at offset %u is also the updated version of tuple at offset %u",
> + (unsigned) nextoffnum, (unsigned) predecessor[nextoffnum]));
> + continue;

I doubt it is correct to enter this path with next_xmin ==
FrozenTransactionId. This is following a ctid chain that we normally wouldn't
follow, because it doesn't satisfy the t_self->xmax == t_ctid->xmin condition.

I don't immediately see what prevents the frozen tuple being from an entirely
different HOT chain than the two tuples pointing to it.

> + }
> +
> + /* Loop over offsets and validate the data in the predecessor array. */
> + for (OffsetNumber currentoffnum = FirstOffsetNumber; currentoffnum <= maxoff;
> + currentoffnum = OffsetNumberNext(currentoffnum))
> + {
> + HeapTupleHeader pred_htup;
> + HeapTupleHeader curr_htup;
> + TransactionId pred_xmin;
> + TransactionId curr_xmin;
> + ItemId pred_lp;
> + ItemId curr_lp;
> +
> + ctx.offnum = predecessor[currentoffnum];
> + ctx.attnum = -1;
> +
> + if (ctx.offnum == 0)
> + {
> + /*
> + * Either the root of the chain or an xmin-aborted tuple from
> + * an abandoned portion of the HOT chain.
> + */

Hm - couldn't we check that the tuple could conceivably be at the root of a
chain? I.e. isn't HEAP_HOT_UPDATED? Or alternatively has an aborted xmin?

> + continue;
> + }
> +
> + curr_lp = PageGetItemId(ctx.page, currentoffnum);
> + curr_htup = (HeapTupleHeader) PageGetItem(ctx.page, curr_lp);
> + curr_xmin = HeapTupleHeaderGetXmin(curr_htup);
> +
> + ctx.itemid = pred_lp = PageGetItemId(ctx.page, ctx.offnum);
> + pred_htup = (HeapTupleHeader) PageGetItem(ctx.page, pred_lp);
> + pred_xmin = HeapTupleHeaderGetXmin(pred_htup);
> +
> + /*
> + * If the predecessor's xmin is aborted or in progress, the
> + * current tuples xmin should be aborted or in progress
> + * respectively. Also both xmin's must be equal.
> + */
> + if (!TransactionIdEquals(pred_xmin, curr_xmin) &&
> + !TransactionIdDidCommit(pred_xmin))
> + {
> + report_corruption(&ctx,
> + psprintf("tuple with uncommitted xmin %u was updated to produce a tuple at offset %u with differing xmin %u",
> + (unsigned) pred_xmin, (unsigned) currentoffnum, (unsigned) curr_xmin));

Is this necessarily true? What about a tuple that was inserted in a
subtransaction and then updated in another subtransaction of the same toplevel
transaction?

> + }
> +
> + /*
> + * If the predecessor's xmin is not frozen, then current tuple's
> + * shouldn't be either.
> + */
> + if (pred_xmin != FrozenTransactionId && curr_xmin == FrozenTransactionId)
> + {
> + report_corruption(&ctx,
> + psprintf("unfrozen tuple was updated to produce a tuple at offset %u which is frozen",
> + (unsigned) currentoffnum));
> + }

Can't we have a an update chain that is e.g.
xmin 10, xmax 5 -> xmin 5, xmax invalid

and a vacuum cutoff of 7? That'd preent the first tuple from being removed,
but would allow 5 to be frozen.

I think there were recent patches proposing we don't freeze in that case, but
we'll having done that in the past....

Greetings,

Andres Freund