Re: BUG #17255: Server crashes in index_delete_sort_cmp() due to race condition with vacuum

Hi,

On 2021-11-09 19:07:02 -0800, Peter Geoghegan wrote:
> diff --git a/src/backend/access/heap/pruneheap.c b/src/backend/access/heap/pruneheap.c
> index c7331d810..31fa4d2a3 100644
> --- a/src/backend/access/heap/pruneheap.c
> +++ b/src/backend/access/heap/pruneheap.c
> @@ -31,6 +31,7 @@
> typedef struct
> {
> Relation rel;
> + BlockNumber targetblkno;

It's a good optimization to remove the reundant BufferGetBlockNumber(), but
perhaps it's worth committing that separately?

> @@ -256,10 +260,8 @@ heap_page_prune(Relation relation, Buffer buffer,
> offnum <= maxoff;
> offnum = OffsetNumberNext(offnum))
> {
> - ItemId itemid;
> -
> /* Ignore items already processed as part of an earlier chain */
> - if (prstate.marked[offnum])
> + if (prstate.fromvalidchain[offnum])
> continue;
>
> /*

ISTM that we should now call heap_prune_chain() only for the start of actual
chains (i.e. redirect or non-hot tuple).

I think it'd be good to have a comment above the loop explaining that we're
just iterating over chains starting at a non-HOT element.

> @@ -269,15 +271,29 @@ heap_page_prune(Relation relation, Buffer buffer,
> if (off_loc)
> *off_loc = offnum;
>
> - /* Nothing to do if slot is empty or already dead */
> - itemid = PageGetItemId(page, offnum);
> - if (!ItemIdIsUsed(itemid) || ItemIdIsDead(itemid))
> - continue;
> -
> /* Process this item or chain of items */
> ndeleted += heap_prune_chain(buffer, offnum, &prstate);
> }

Why did you move this into heap_prune_chain()?

> + /*
> + * Scan the page again, processing any heap-only tuples that we now know
> + * are not part of any valid HOT chain
> + */
> + for (offnum = FirstOffsetNumber;
> + offnum <= maxoff;
> + offnum = OffsetNumberNext(offnum))
> + {
> + /* Ignore items already processed as part of a known valid chain */
> + if (prstate.fromvalidchain[offnum])
> + continue;
> +
> + if (off_loc)
> + *off_loc = offnum;
> +
> + /* Process this disconnected heap-only tuple */
> + ndeleted += heap_prune_heaponly(buffer, offnum, &prstate);
> + }
> +
> /* Clear the offset information once we have processed the given page. */
> if (off_loc)
> *off_loc = InvalidOffsetNumber;
> @@ -383,19 +399,8 @@ heap_page_prune(Relation relation, Buffer buffer,
> pgstat_update_heap_dead_tuples(relation, ndeleted - prstate.ndead);
>
> /*
> - * XXX Should we update the FSM information of this page ?
> - *
> - * There are two schools of thought here. We may not want to update FSM
> - * information so that the page is not used for unrelated UPDATEs/INSERTs
> - * and any free space in this page will remain available for further
> - * UPDATEs in *this* page, thus improving chances for doing HOT updates.
> - *
> - * But for a large table and where a page does not receive further UPDATEs
> - * for a long time, we might waste this space by not updating the FSM
> - * information. The relation may get extended and fragmented further.
> - *
> - * One possibility is to leave "fillfactor" worth of space in this page
> - * and update FSM with the remaining space.
> + * Don't update the FSM information on this page. We leave it up to our
> + * caller to decide what to do about that.
> */

I don't think this should be part of the commit?

> offnum = rootoffnum;
> + nchain = 0;

> /* while not end of the chain */
> for (;;)
> {
> ItemId lp;
> - bool tupdead,
> - recent_dead;
> + HeapTupleHeader htup;
> + HeapTupleData tup;
> + bool tupdead;
>
> /* Sanity check (pure paranoia) */
> if (offnum < FirstOffsetNumber)
> @@ -601,15 +603,11 @@ heap_prune_chain(Buffer buffer, OffsetNumber rootoffnum, PruneState *prstate)
> break;
>
> /* If item is already processed, stop --- it must not be same chain */
> - if (prstate->marked[offnum])
> + if (nchain != 0 && prstate->fromvalidchain[offnum])
> break;

I think we should make it an error to reach the same tuple multiple ways. It's
not *quite* as trivial as making this an assert/error though, as we can only
raise an error after checking that the xmin/xmax thing passes.

> /*
> * If we are looking at the redirected root line pointer, jump to the
> * first normal tuple in the chain. If we find a redirect somewhere
> @@ -619,42 +617,63 @@ heap_prune_chain(Buffer buffer, OffsetNumber rootoffnum, PruneState *prstate)
> {
> if (nchain > 0)
> break; /* not at start of chain */
> + Assert(rootisredirect);
> chainitems[nchain++] = offnum;
> offnum = ItemIdGetRedirect(rootlp);
> continue;
> }

Why are we handling this inside the loop?

> - /*
> - * Likewise, a dead line pointer can't be part of the chain. (We
> - * already eliminated the case of dead root tuple outside this
> - * function.)
> - */
> - if (ItemIdIsDead(lp))
> + /* LP_UNUSED or LP_DEAD items obviously not part of the chain */
> + if (!ItemIdIsUsed(lp) || ItemIdIsDead(lp))
> + {
> + /*
> + * XXX What if we just came from root item, which is a plain heap
> + * tuple? Do we need assert that notices when we reach an LP_DEAD
> + * or LP_UNUSED item having started from such a root item?
> + */
> + Assert(!rootisredirect || nchain > 1);

I don't think we can assert that. It's perfectly possible to have a non-hot
update chain where the following element can be vacuumed, but the preceding
element can't (e.g. when the updater has an older xid that prevents it from
being pruned).

> chainitems[nchain++] = offnum;
> + prstate->fromvalidchain[offnum] = true;
>
> /*
> * Check tuple's visibility status.
> */
> - tupdead = recent_dead = false;
> + tupdead = false;
>
> switch (heap_prune_satisfies_vacuum(prstate, &tup, buffer))
> {
> @@ -663,7 +682,6 @@ heap_prune_chain(Buffer buffer, OffsetNumber rootoffnum, PruneState *prstate)
> break;
>
> case HEAPTUPLE_RECENTLY_DEAD:
> - recent_dead = true;
>
> /*
> * This tuple may soon become DEAD. Update the hint field so
> @@ -679,6 +697,7 @@ heap_prune_chain(Buffer buffer, OffsetNumber rootoffnum, PruneState *prstate)
> * This tuple may soon become DEAD. Update the hint field so
> * that the page is reconsidered for pruning in future.
> */
> + Assert(!tupdead);
> heap_prune_record_prunable(prstate,
> HeapTupleHeaderGetUpdateXid(htup));
> break;

> @@ -692,6 +711,7 @@ heap_prune_chain(Buffer buffer, OffsetNumber rootoffnum, PruneState *prstate)
> * But we don't. See related decisions about when to mark the
> * page prunable in heapam.c.
> */
> + Assert(!tupdead);
> break;
>
> default:

I don't understand these new assert? We just set tupdead to false above?

> @@ -700,11 +720,18 @@ heap_prune_chain(Buffer buffer, OffsetNumber rootoffnum, PruneState *prstate)
> }
>
> /*
> - * Remember the last DEAD tuple seen. We will advance past
> - * RECENTLY_DEAD tuples just in case there's a DEAD one after them;
> - * but we can't advance past anything else. We have to make sure that
> - * we don't miss any DEAD tuples, since DEAD tuples that still have
> - * tuple storage after pruning will confuse VACUUM.
> + * Remember the last DEAD tuple seen from this HOT chain.
> + *
> + * We expect to sometimes find a RECENTLY_DEAD tuple after a DEAD
> + * tuple. When this happens, the RECENTLY_DEAD tuple will be treated
> + * as if it was DEAD all along. Manage that now.

I now actually wonder why this is correct. There's another comment about it:

> We also prune any RECENTLY_DEAD tuples preceding a DEAD tuple.
> * This is OK because a RECENTLY_DEAD tuple preceding a DEAD tuple is really

But that doesn't justify very much.

What prevents the scenario that some other backend e.g. has a snapshot with
xmin=xmax=RECENTLY_DEAD-row. If the RECENTLY_DEAD row has an xid that is later
than the DEAD row, this afaict would make it perfectly legal to prune the DEAD
row, but *not* the RECENTLY_DEAD one.

> + * We're not just interested in DEAD and RECENTLY_DEAD tuples. We
> + * need to traverse each and every HOT chain exhaustively, in order to
> + * determine which heap-only tuples are part of a valid HOT chain.
> + * Heap-only tuples that cannot be located like this must not be part
> + * of a valid HOT chain. They are therefore processed during our
> + * second pass over the page.
> */
> if (tupdead)
> {

This comment can't really be understood without the historical behaviour of
the function.

> +static int
> +heap_prune_heaponly(Buffer buffer, OffsetNumber offnum, PruneState *prstate)
> +{
> + Page dp = (Page) BufferGetPage(buffer);
> + ItemId lp;
> + HeapTupleHeader htup;
> + HeapTupleData tup;
> + HTSV_Result res;
> +
> + lp = PageGetItemId(dp, offnum);
> + Assert(ItemIdIsNormal(lp));
> + htup = (HeapTupleHeader) PageGetItem(dp, lp);
> +
> + /*
> + * Caller must make sure that the tuple at 'offnum' is in fact a heap-only
> + * tuple that is disconnected from its HOT chain (i.e. isn't reachable
> + * through a HOT traversal that starts at any plausible-looking root item
> + * on the page).
> + */
> + Assert(!prstate->fromvalidchain[offnum]);
> + Assert(HeapTupleHeaderIsHeapOnly(htup));
> +
> + /*
> + * We expect that disconnected heap-only tuples must be from aborted
> + * transactions. Any RECENTLY_DEAD tuples we see here are really DEAD,
> + * but the heap_prune_satisfies_vacuum test is too coarse to detect it.
> + */
> + tup.t_len = ItemIdGetLength(lp);
> + tup.t_tableOid = RelationGetRelid(prstate->rel);
> + tup.t_data = htup;
> + ItemPointerSet(&(tup.t_self), prstate->targetblkno, offnum);
> + res = heap_prune_satisfies_vacuum(prstate, &tup, buffer);
> + if (res == HEAPTUPLE_DEAD || res == HEAPTUPLE_RECENTLY_DEAD)
> + {
> + heap_prune_record_unused(prstate, offnum);
> + HeapTupleHeaderAdvanceLatestRemovedXid(htup,
> + &prstate->latestRemovedXid);
> + }
> + else
> + Assert(false);
> +
> + /*
> + * Should always be DEAD. A DEAD heap-only tuple is always counted in
> + * top-level ndeleted counter for pruning operation.
> + */
> + return 1;
> +}

It seems weird to have the if (res == HEAPTUPLE_DEAD ..) branch, but then to
unconditionally return 1.

I'm not actually sure the Assert is unreachable. I can imagine cases where
we'd see e.g. DELETE/INSERT_IN_PROGRESS due to a concurrent subtransaction
abort or such.

Greetings,

Andres Freund