From: Oleksii Kliukin <alexk@hintbits.com>
Content-Type: multipart/mixed;
	boundary="Apple-Mail=_2BE0587A-291C-44B7-A91D-C04EEBEBDE50"
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.8\))
Subject: upgrades in row-level locks can deadlock
Message-Id: <B9C9D7CD-EB94-4635-91B6-E558ACEC0EC3@hintbits.com>
Date: Wed, 22 May 2019 17:27:15 +0200
Cc: Chris Travers <chris.travers@adjust.com>
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Precedence: bulk


--Apple-Mail=_2BE0587A-291C-44B7-A91D-C04EEBEBDE50
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8


Hello,

I have recently observed a deadlock on one of our production servers =
related
to locking only a single row in a job table. There were two functions =
involved
in the deadlock, the first one acquires a =E2=80=9Cfor key share=E2=80=9D =
lock on the row that
represents the job it works on and subsequently updates it with the =
job=E2=80=99s end
time (we need multiple jobs to be operating on a single row =
concurrently,
that=E2=80=99s why there is a "for key share" lock). The other function =
starts by
acquiring the =E2=80=9Cfor update=E2=80=9D lock on the job row and then =
performs actions that
should not be run in parallel with other jobs.

The deadlock can be easily reproduced with the following statements. The
queries run against a table job (id integer primary key, name text) with =
a
single row of (1,'a'))

X1: select id from job where name =3D 'a' for key share;
Y: select id from job where name =3D 'a' for update; -- starts waiting =
for X1
X2: select id from job where name =3D 'a' for key share;
X1: update job set name =3D 'b' where id =3D 1;
X2: update job set name =3D 'c' where id =3D 1; -- starts waiting for X1
X1: rollback;

At this point, Y is terminated by the deadlock detector:

"deadlock detected",
Process 53937 waits for ShareLock on transaction 488; blocked by process =
53953.
Process 53953 waits for ExclusiveLock on tuple (0,1) of relation 16386 =
of database 12931;
blocked by process 53937.
Process 53937: select id from job where name =3D 'a' for update;
Process 53953: update job set name =3D 'c' where id =3D 1;",

The deadlock is between X2 and Y. Y waits for X2 to finish, as X2 holds =
a "key
share" lock, incompatible with "for update" that Y attempts to acquire. =
On the
other hand, X2 needs to acquire the row lock to perform the update, and =
that
is a two-phase process: first, get the tuple lock and then wait for
conflicting transactions to finish, releasing the tuple lock afterward. =
X2
tries to acquire the tuple lock, but it is owned by Y. PostgreSQL =
detects the
deadlock and terminates Y.

Such a deadlock only occurs when three or more sessions locking the same =
row
are present and the lock is upgraded in at least one session. With only =
two
sessions the upgrade does not go through the lock manager, as there are =
no
conflicts with locks stored in the tuple.=20

That gave me an idea on how to change PostgreSQL to avoid deadlocking =
under
the condition above. When detecting the lock upgrade from the multixact, =
we
can avoid acquiring the tuple lock; however, we should still wait for =
the
mutlixact members that hold conflicting locks, to avoid acquiring =
incompatible
ones.

The patch is attached. I had to tweak heap_update and heap_delete =
alongside
the heap_lock_tuple, as they acquire row locks as well. I am not very =
happy
with overloading DoesMultiXactIdConflict with another function to check =
if
current transaction id is among the multixact members, perhaps it is =
worth to
have a separate function for this. We can figure this out if we agree =
this is
the problem that needs to be solved and on the solution. The other =
possible
objection is related to the statement from README.tuplock that we need =
to go
through the lock manager to avoid starving waiting exclusive-lockers. =
Since
this patch omits the tuple lock only when the lock upgrade happens, it =
does
limit the starvation condition to the cases when the lock compatible =
with the
one the waiting process asks for is acquired first and then gets =
upgraded to
the incompatible one. Since under present conditions the same operation =
will
likely deadlock and cancel the exclusive waiter altogether, I don't see =
this
as a strong objection.

Cheers,
Oleksii


--Apple-Mail=_2BE0587A-291C-44B7-A91D-C04EEBEBDE50
Content-Disposition: attachment;
	filename=deadlock_on_row_lock_upgrades_v1.diff
Content-Type: application/octet-stream;
	x-unix-mode=0644;
	name="deadlock_on_row_lock_upgrades_v1.diff"
Content-Transfer-Encoding: 7bit

diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c
index 19d2c529d8..0454896151 100644
--- a/src/backend/access/heap/heapam.c
+++ b/src/backend/access/heap/heapam.c
@@ -95,7 +95,7 @@ static void GetMultiXactIdHintBits(MultiXactId multi, uint16 *new_infomask,
 static TransactionId MultiXactIdGetUpdateXid(TransactionId xmax,
 						uint16 t_infomask);
 static bool DoesMultiXactIdConflict(MultiXactId multi, uint16 infomask,
-						LockTupleMode lockmode);
+						LockTupleMode lockmode, bool *has_current_xid);
 static void MultiXactIdWait(MultiXactId multi, MultiXactStatus status, uint16 infomask,
 				Relation rel, ItemPointer ctid, XLTW_Oper oper,
 				int *remaining);
@@ -2556,15 +2556,22 @@ l1:
 		 */
 		if (infomask & HEAP_XMAX_IS_MULTI)
 		{
+			bool has_current_xid = false;
 			/* wait for multixact */
 			if (DoesMultiXactIdConflict((MultiXactId) xwait, infomask,
-										LockTupleExclusive))
+										LockTupleExclusive, &has_current_xid))
 			{
 				LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
 
-				/* acquire tuple lock, if necessary */
-				heap_acquire_tuplock(relation, &(tp.t_self), LockTupleExclusive,
-									 LockWaitBlock, &have_tuple_lock);
+				/*
+				 * Acquire the lock, if necessary. Avoid acquiring it when
+				 * getting the stronger lock while holding a weaker one to
+				 * prevent deadlocks with other lockers that already have
+				 * a tuple lock and waiting for our transaction to finish.
+				 */
+				if (!has_current_xid)
+					heap_acquire_tuplock(relation, &(tp.t_self), LockTupleExclusive,
+										 LockWaitBlock, &have_tuple_lock);
 
 				/* wait for multixact */
 				MultiXactIdWait((MultiXactId) xwait, MultiXactStatusUpdate, infomask,
@@ -3135,15 +3142,23 @@ l2:
 		{
 			TransactionId update_xact;
 			int			remain;
+			bool 		has_current_xid = false;
 
 			if (DoesMultiXactIdConflict((MultiXactId) xwait, infomask,
-										*lockmode))
+										*lockmode, &has_current_xid))
 			{
 				LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
 
-				/* acquire tuple lock, if necessary */
-				heap_acquire_tuplock(relation, &(oldtup.t_self), *lockmode,
-									 LockWaitBlock, &have_tuple_lock);
+				/*
+				 * Acquire the lock, if necessary. Avoid acquiring it when
+				 * getting the stronger lock while holding a weaker one to
+				 * prevent deadlocks with other lockers that already have
+				 * a tuple lock and waiting for our transaction to finish.
+				 */
+
+				if (!has_current_xid)
+					heap_acquire_tuplock(relation, &(oldtup.t_self), *lockmode,
+										 LockWaitBlock, &have_tuple_lock);
 
 				/* wait for multixact */
 				MultiXactIdWait((MultiXactId) xwait, mxact_status, infomask,
@@ -4037,6 +4052,7 @@ l3:
 		uint16		infomask;
 		uint16		infomask2;
 		bool		require_sleep;
+		bool		skip_tuple_lock;
 		ItemPointerData t_ctid;
 
 		/* must copy state data before unlocking buffer */
@@ -4062,6 +4078,7 @@ l3:
 		if (first_time)
 		{
 			first_time = false;
+			skip_tuple_lock = false;
 
 			if (infomask & HEAP_XMAX_IS_MULTI)
 			{
@@ -4090,6 +4107,21 @@ l3:
 						result = TM_Ok;
 						goto out_unlocked;
 					}
+					else
+					{
+						/*
+						 * Avoid acquiring the tuple level lock.
+						 *
+						 * Otherwise, when promoting a weaker lock, we may
+						 * deadlock with another potential locker that has
+						 * acquired a conflicting row lock and waits for our
+						 * transaction to finish.
+						 *
+						 * Note that we will wait for the multixact
+						 * if required to avoid acquiring conflicting locks.
+						 */
+						skip_tuple_lock = true;
+					}
 				}
 
 				if (members)
@@ -4244,7 +4276,7 @@ l3:
 			if (infomask & HEAP_XMAX_IS_MULTI)
 			{
 				if (!DoesMultiXactIdConflict((MultiXactId) xwait, infomask,
-											 mode))
+											 mode, NULL))
 				{
 					/*
 					 * No conflict, but if the xmax changed under us in the
@@ -4327,7 +4359,8 @@ l3:
 			 * this arranges that we stay at the head of the line while
 			 * rechecking tuple state.
 			 */
-			if (!heap_acquire_tuplock(relation, tid, mode, wait_policy,
+			if (!skip_tuple_lock &&
+				!heap_acquire_tuplock(relation, tid, mode, wait_policy,
 									  &have_tuple_lock))
 			{
 				/*
@@ -6525,16 +6558,21 @@ HeapTupleGetUpdateXid(HeapTupleHeader tuple)
  * tuple lock of the given strength?
  *
  * The passed infomask pairs up with the given multixact in the tuple header.
+ * has_current_xid is set when not-NULL if the given multixact contains current
+ * transaction.
  */
 static bool
 DoesMultiXactIdConflict(MultiXactId multi, uint16 infomask,
-						LockTupleMode lockmode)
+						LockTupleMode lockmode, bool *has_current_xid)
 {
 	int			nmembers;
 	MultiXactMember *members;
 	bool		result = false;
 	LOCKMODE	wanted = tupleLockExtraInfo[lockmode].hwlock;
 
+	if (has_current_xid != NULL)
+		*has_current_xid = false;
+
 	if (HEAP_LOCKED_UPGRADED(infomask))
 		return false;
 
@@ -6549,15 +6587,24 @@ DoesMultiXactIdConflict(MultiXactId multi, uint16 infomask,
 			TransactionId memxid;
 			LOCKMODE	memlockmode;
 
-			memlockmode = LOCKMODE_from_mxstatus(members[i].status);
+			if (result && (has_current_xid == NULL || *has_current_xid))
+				break;
 
-			/* ignore members that don't conflict with the lock we want */
-			if (!DoLockModesConflict(memlockmode, wanted))
-				continue;
+			memlockmode = LOCKMODE_from_mxstatus(members[i].status);
 
 			/* ignore members from current xact */
 			memxid = members[i].xid;
 			if (TransactionIdIsCurrentTransactionId(memxid))
+			{
+				if (has_current_xid != NULL)
+					*has_current_xid = true;
+				continue;
+			}
+			else if (result)
+				continue;
+
+			/* ignore members that don't conflict with the lock we want */
+			if (!DoLockModesConflict(memlockmode, wanted))
 				continue;
 
 			if (ISUPDATE_from_mxstatus(members[i].status))
@@ -6576,10 +6623,11 @@ DoesMultiXactIdConflict(MultiXactId multi, uint16 infomask,
 			/*
 			 * Whatever remains are either live lockers that conflict with our
 			 * wanted lock, and updaters that are not aborted.  Those conflict
-			 * with what we want, so return true.
+			 * with what we want. Return true on the next loop iteration unless
+			 * we need to look for the current transaction among the multixact
+			 * members.
 			 */
 			result = true;
-			break;
 		}
 		pfree(members);
 	}

--Apple-Mail=_2BE0587A-291C-44B7-A91D-C04EEBEBDE50
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=us-ascii


--Apple-Mail=_2BE0587A-291C-44B7-A91D-C04EEBEBDE50--