Subject: Re: LWLock deadlock in brinRevmapDesummarizeRange

From: Alvaro Herrera <[email-masked]>
Date: Wed, 22 Feb 2023 15:41:12 +0100

On 2023-Feb-22, Tomas Vondra wrote:

> > ... and in there, I wrote that we would first write the brin tuple in
> > the regular page, unlock that, and then lock the revmap for the update,
> > without holding lock on the data page.  I don't remember why we do it
> > differently now, but maybe the fix is just to release the regular page
> > lock before locking the revmap page?  One very important change is that
> > in previous versions the revmap used a separate fork, and we had to
> > introduce an "evacuation protocol" when we integrated the revmap into
> > the main fork, which may have changed the locking considerations.
> 
> What would happen if two processes built the summary concurrently? How
> would they find the other tuple, so that we don't end up with two BRIN
> tuples for the same range?

Well, the revmap can only keep track of one tuple per range; if two
processes build summary tuples, and each tries to insert its tuple in a
regular page, that part may succeed; but then only one of them is going
to successfully register the summary tuple in the revmap: when the other
goes to do the same, it would find that a CTID is already present.

... Looking at the code (brinSetHeapBlockItemptr), I think what happens
here is that the second process would overwrite the TID with its own.
Not sure if it would work to see whether the item is empty and bail out
if it's not.

But in any case, it seems to me that the update of the regular page is
pretty much independent of the update of the revmap.

> > Another point: to desummarize a range, just unlinking the entry from
> > revmap should suffice, from the POV of other index scanners.  Maybe we
> > can simplify the whole procedure to: lock revmap, remove entry, remember
> > page number, unlock revmap; lock regular page, delete entry, unlock.
> > Then there are no two locks held at the same time during desummarize.
> 
> Perhaps, as long as it doesn't confuse anything else.

Well, I don't have the details fresh in mind, but I think it shouldn't,
because the only way to reach a regular tuple is coming from the revmap;
and we reuse "items" (lines) in a regular page only when they are
empty (so vacuuming should also be OK).

> > This comes from v16:
> 
> I don't follow - what do you mean by v16? I don't see anything like that
> anywhere in the repository.

I meant the minmax-proposal file in patch v16, the one that I linked to.

-- 
Álvaro Herrera         PostgreSQL Developer  —  https://www.EnterpriseDB.com/
"You're _really_ hosed if the person doing the hiring doesn't understand
relational systems: you end up with a whole raft of programmers, none of
whom has had a Date with the clue stick."              (Andrew Sullivan)

---

From: Arseniy Mukhin <[email-masked]>
Date: Wed, 2 Apr 2025 22:50:01 +0300

Hello Tomas and Alvaro,

Came across this old thread while searching for information about brin,
and decided to try to fix it.

 > Not sure if it would work to see whether the item is empty and bail out

AFAIS it's impossible to have two processes summarizing or desummarizing 
ranges simultaneously,
because you need ShareUpdateExclusiveLock to do it. Usual inserts / 
updates can't lead
to summarization, they affects only those ranges that are summarized 
already.

 > empty (so vacuuming should also be OK).

I think it would work, but there's one thing to handle in this case:
You may have a concurrent update that moved the index tuple to another 
reg page and wants to update
the revmap page with a new pointer. This may happen after the revmap 
entry is deleted,
so you can have kind of lost update. But this seems to be easy to detect:
when you try to delete the index tuple, you'll see an unused item.
This means that a concurrent update moved index tuple and updated revmap 
page and you need to retry the desummarization.

Also if you don't hold locks on both revmap page and regular pages, you 
will have
to split wal record and rework recovery for desummarization. And 
probably in case of crash between revmap update
and regular page update you can have dangling index tuple, so it seems 
that having one wal record for update simplifies
recovery.

I think there is a straightforward way to implement desummarization and 
fix the deadlock.
Desummarization is actually very similar to usual update, so we can just 
use update flow
(like brininsert or second part of summarize_range where you need to 
merge summary with placeholder tuple):
- lock revmap page
- save pointer to the index tuple
- unlock revmap page
- lock regular page
- check if pointer is still valid (blkno is as expected, NORMAL tuple etc.)
   if we see that pointer is not valid anymore -> unlock reg page + retry
- lock revmap page
- update reg page and revmap page

First five steps have been implemented already in 
brinGetTupleForHeapBlock, so we can use it (like every update actually 
do, if I see correctly).

Please find the attached patch implementing the above idea.

I tried Tomas's stress tests with applied patch and didn't have deadlocks.

Also there is a another way how issue can be reproduced:
apply deadlock-sleep.patch (it just adds 15 sec sleep in brin_doupdate 
and few logs)
execute deadlock.sql
execute deadlock2.sql from another client (there are 15 seconds to do it 
while first process is sleeping).

Best regards,
Arseniy Mukhin

From 31a8a558b845cda6b1ec1d18829e0f7ff0ec350d Mon Sep 17 00:00:00 2001
From: Arseniy Mukhin <[email-masked]>
Date: Wed, 2 Apr 2025 21:55:24 +0300
Subject: [PATCH] brin desummarization deadlock

---
 src/backend/access/brin/brin.c        |  8 +--
 src/backend/access/brin/brin_revmap.c | 71 ++++++++++++---------------
 src/include/access/brin_revmap.h      |  2 +-
 3 files changed, 33 insertions(+), 48 deletions(-)

diff --git a/src/backend/access/brin/brin.c b/src/backend/access/brin/brin.c
index 01e1db7f856..c52677534ed 100644
--- a/src/backend/access/brin/brin.c
+++ b/src/backend/access/brin/brin.c
@@ -1496,7 +1496,6 @@ brin_desummarize_range(PG_FUNCTION_ARGS)
 	Oid			heapoid;
 	Relation	heapRel;
 	Relation	indexRel;
-	bool		done;
 
 	if (RecoveryInProgress())
 		ereport(ERROR,
@@ -1555,12 +1554,7 @@ brin_desummarize_range(PG_FUNCTION_ARGS)
 	/* see gin_clean_pending_list() */
 	if (indexRel->rd_index->indisvalid)
 	{
-		/* the revmap does the hard work */
-		do
-		{
-			done = brinRevmapDesummarizeRange(indexRel, heapBlk);
-		}
-		while (!done);
+		brinRevmapDesummarizeRange(indexRel, heapBlk);
 	}
 	else
 		ereport(DEBUG1,
diff --git a/src/backend/access/brin/brin_revmap.c b/src/backend/access/brin/brin_revmap.c
index 4e380ecc710..d3ef03d34ae 100644
--- a/src/backend/access/brin/brin_revmap.c
+++ b/src/backend/access/brin/brin_revmap.c
@@ -316,10 +316,8 @@ brinGetTupleForHeapBlock(BrinRevmap *revmap, BlockNumber heapBlk,
  * Delete an index tuple, marking a page range as unsummarized.
  *
  * Index must be locked in ShareUpdateExclusiveLock mode.
- *
- * Return false if caller should retry.
  */
-bool
+void
 brinRevmapDesummarizeRange(Relation idxrel, BlockNumber heapBlk)
 {
 	BrinRevmap *revmap;
@@ -327,26 +325,37 @@ brinRevmapDesummarizeRange(Relation idxrel, BlockNumber heapBlk)
 	RevmapContents *contents;
 	ItemPointerData *iptr;
 	ItemPointerData invalidIptr;
-	BlockNumber revmapBlk;
 	Buffer		revmapBuf;
-	Buffer		regBuf;
+	Buffer		regBuf = InvalidBuffer;
 	Page		revmapPg;
 	Page		regPg;
 	OffsetNumber revmapOffset;
 	OffsetNumber regOffset;
-	ItemId		lp;
+	BrinTuple  *btup;
+	Size		size;
 
 	revmap = brinRevmapInitialize(idxrel, &pagesPerRange);
 
-	revmapBlk = revmap_get_blkno(revmap, heapBlk);
-	if (!BlockNumberIsValid(revmapBlk))
+	/* Try to get index tuple for the target block number */
+	btup = brinGetTupleForHeapBlock(revmap, heapBlk, &regBuf, &regOffset, &size, BUFFER_LOCK_EXCLUSIVE);
+
+	/* If range is not summarized, release resources and we are done */
+	if (!btup)
 	{
-		/* revmap page doesn't exist: range not summarized, we're done */
+		if (BufferIsValid(regBuf))
+		{
+			ReleaseBuffer(regBuf);
+		}
 		brinRevmapTerminate(revmap);
-		return true;
+
+		return;
 	}
 
-	/* Lock the revmap page, obtain the index tuple pointer from it */
+	/*
+	 * We know that range is summarized (or it's a dangling placeholder), and
+	 * we have the regular page with the index tuple locked exclusively. Now
+	 * lock the revmap page with pointer to our index tuple
+	 */
 	revmapBuf = brinLockRevmapPageForUpdate(revmap, heapBlk);
 	revmapPg = BufferGetPage(revmapBuf);
 	revmapOffset = HEAPBLK_TO_REVMAP_INDEX(revmap->rm_pagesPerRange, heapBlk);
@@ -355,38 +364,22 @@ brinRevmapDesummarizeRange(Relation idxrel, BlockNumber heapBlk)
 	iptr = contents->rm_tids;
 	iptr += revmapOffset;
 
-	if (!ItemPointerIsValid(iptr))
-	{
-		/* no index tuple: range not summarized, we're done */
-		LockBuffer(revmapBuf, BUFFER_LOCK_UNLOCK);
-		brinRevmapTerminate(revmap);
-		return true;
-	}
-
-	regBuf = ReadBuffer(idxrel, ItemPointerGetBlockNumber(iptr));
-	LockBuffer(regBuf, BUFFER_LOCK_EXCLUSIVE);
-	regPg = BufferGetPage(regBuf);
-
-	/* if this is no longer a regular page, tell caller to start over */
-	if (!BRIN_IS_REGULAR_PAGE(regPg))
+	/*
+	 * No concurrent updates for the range are possible as any update should
+	 * lock regular page first, and we already hold the lock. We know that
+	 * index tuple for the range exists, so revmap item pointer couldn't be
+	 * invalid and should point to index tuple btup.
+	 */
+	if (!ItemPointerIsValid(iptr) ||
+		ItemPointerGetBlockNumber(iptr) != BufferGetBlockNumber(regBuf) ||
+		ItemPointerGetOffsetNumber(iptr) != regOffset)
 	{
-		LockBuffer(revmapBuf, BUFFER_LOCK_UNLOCK);
-		LockBuffer(regBuf, BUFFER_LOCK_UNLOCK);
-		brinRevmapTerminate(revmap);
-		return false;
-	}
-
-	regOffset = ItemPointerGetOffsetNumber(iptr);
-	if (regOffset > PageGetMaxOffsetNumber(regPg))
 		ereport(ERROR,
 				(errcode(ERRCODE_INDEX_CORRUPTED),
 				 errmsg("corrupted BRIN index: inconsistent range map")));
+	}
 
-	lp = PageGetItemId(regPg, regOffset);
-	if (!ItemIdIsUsed(lp))
-		ereport(ERROR,
-				(errcode(ERRCODE_INDEX_CORRUPTED),
-				 errmsg("corrupted BRIN index: inconsistent range map")));
+	regPg = BufferGetPage(regBuf);
 
 	/*
 	 * Placeholder tuples only appear during unfinished summarization, and we
@@ -429,8 +422,6 @@ brinRevmapDesummarizeRange(Relation idxrel, BlockNumber heapBlk)
 	UnlockReleaseBuffer(regBuf);
 	LockBuffer(revmapBuf, BUFFER_LOCK_UNLOCK);
 	brinRevmapTerminate(revmap);
-
-	return true;
 }
 
 /*
diff --git a/src/include/access/brin_revmap.h b/src/include/access/brin_revmap.h
index b88473c9860..322109e903d 100644
--- a/src/include/access/brin_revmap.h
+++ b/src/include/access/brin_revmap.h
@@ -36,6 +36,6 @@ extern void brinSetHeapBlockItemptr(Buffer buf, BlockNumber pagesPerRange,
 extern BrinTuple *brinGetTupleForHeapBlock(BrinRevmap *revmap,
 										   BlockNumber heapBlk, Buffer *buf, OffsetNumber *off,
 										   Size *size, int mode);
-extern bool brinRevmapDesummarizeRange(Relation idxrel, BlockNumber heapBlk);
+extern void brinRevmapDesummarizeRange(Relation idxrel, BlockNumber heapBlk);
 
 #endif							/* BRIN_REVMAP_H */
-- 
2.43.0

diff --git a/src/backend/access/brin/brin_pageops.c b/src/backend/access/brin/brin_pageops.c
index 6d8dd1512d6..9c3ad1f0bab 100644
--- a/src/backend/access/brin/brin_pageops.c
+++ b/src/backend/access/brin/brin_pageops.c
@@ -237,8 +237,11 @@ brin_doupdate(Relation idxrel, BlockNumber pagesPerRange,
 		OffsetNumber newoff;
 		Size		freespace = 0;
 
+        elog(DEBUG1, "sleep while update");
+        sleep(15);
+        elog(DEBUG1, "Try to revmap for update reg page - update");
 		revmapbuf = brinLockRevmapPageForUpdate(revmap, heapBlk);
-
+        elog(DEBUG1, "Try to revmap for update reg page - update");
 		START_CRIT_SECTION();
 
 		/*