[PATCH] LockAcquireExtended improvement

Hi,

On 2023-11-28 20:52:31 +0800, Jingxian Li wrote:

postgres=*# lock table test in exclusive mode ;

T4

Case 1:

postgres=*# lock table test in share row exclusive mode nowait;

ERROR:  could not obtain lock on relation "test"               

--------------------------------------------

Case 2:

postgres=*# lock table test in share row exclusive mode;

LOCK TABLE

 

At T4 moment in session A, (case 1) when executing SQL “lock table test in share row exclusive mode nowait;”, an error occurs with message “could not obtain lock on relation test";However, (case 2) when executing the SQL above without nowait, lock can be obtained successfully.

Digging into the source code, I find that in case 2 the lock was obtained in
the function ProcSleep instead of LockAcquireExtended. Due to nowait logic
processed before WaitOnLock->ProcSleep, acquiring lock failed in case
1. Can any changes be made so that the act of such lock granted occurs
before WaitOnLock?

I don't think that'd make sense - lock reordering is done to prevent deadlocks
and is quite expensive. Why should NOWAIT incur that cost?

 

Providing a more universal case:

Transaction A already holds an n-mode lock on table test. If then transaction A requests an m-mode lock on table Test, m and n have the following constraints:

(lockMethodTable->conflictTab[n] & lockMethodTable->conflictTab[m]) == lockMethodTable->conflictTab[m]

Obviously, in this case, m<=n.

Should the m-mode lock be granted before WaitOnLock?

&nbsp;

In the case of m=n (i.e. we already hold the lock), the m-mode lock is
immediately granted in the LocalLock path, without the need of lock conflict
check.

Sure - it'd not help anybody to wait for a lock we already hold - in fact it'd
create a lot of deadlocks.

Based on the facts above, can we obtain a weaker lock (m<n) on the same
object within the same transaction without doing lock conflict check?

Perhaps. There's no inherent "lock strength" ordering for all locks though.

Greetings,

Andres Freund

Hi Andres, Thanks for your quick reply!

On 2023/11/29 0:51, Andres Freund wrote:

Hi,

On 2023-11-28 20:52:31 +0800, Jingxian Li wrote:

postgres=*# lock table test in exclusive mode ;

T4

Case 1:

postgres=*# lock table test in share row exclusive mode nowait;

ERROR: &nbsp;could not obtain lock on relation "test"

--------------------------------------------

Case 2:

postgres=*# lock table test in share row exclusive mode;

LOCK TABLE

At T4 moment in session A, (case 1) when executing SQL “lock table test in share row exclusive mode nowait;”, an error occurs with message “could not obtain lock on relation test";However, (case 2) when executing the SQL above without nowait, lock can be obtained successfully.

Digging into the source code, I find that in case 2 the lock was obtained in
the function ProcSleep instead of LockAcquireExtended. Due to nowait logic
processed before WaitOnLock-&gt;ProcSleep, acquiring lock failed in case
1. Can any changes be made so that the act of such lock granted occurs
before WaitOnLock?

I don't think that'd make sense - lock reordering is done to prevent deadlocks
and is quite expensive. Why should NOWAIT incur that cost?

Providing a more universal case:

Transaction A already holds an n-mode lock on table test. If then transaction A requests an m-mode lock on table Test, m and n have the following constraints:

(lockMethodTable-&gt;conflictTab[n] &amp; lockMethodTable-&gt;conflictTab[m]) == lockMethodTable-&gt;conflictTab[m]

Obviously, in this case, m<=n.

Should the m-mode lock be granted before WaitOnLock?

In the case of m=n (i.e. we already hold the lock), the m-mode lock is
immediately granted in the LocalLock path, without the need of lock conflict
check.

Sure - it'd not help anybody to wait for a lock we already hold - in fact it'd
create a lot of deadlocks.

Based on the facts above, can we obtain a weaker lock (m<n) on the same
object within the same transaction without doing lock conflict check?

Perhaps. There's no inherent "lock strength" ordering for all locks though.

I also noticed that there is no inherent "lock strength" orderingfor all locks.
So I use the following method in the code to determine the strength of the lock:
if (m<n &&(lockMethodTable->conflictTab[n] &
lockMethodTable->conflictTab[m]) == lockMethodTable->conflictTab[m])
then we can say that m-mode lock is weaker than n-mode lock.

Transaction A already holds an n-mode lock on table test,
that is, there is no locks held conflicting with the n-mode lock on table test,
If then transaction A requests an m-mode lock on table test,
as n's confilctTab covers m, it can be concluded that
there are no locks conflicting with the requested m-mode lock.

Greetings,

Andres Freund

With regards,

Jingxian Li

On Tue, 28 Nov 2023 at 18:23, Jingxian Li <aqktjcm@qq.com> wrote:

Hi hackers,

I found a problem when doing the test shown below:

Time

Session A

Session B

T1

postgres=# create table test(a int);

CREATE TABLE

postgres=# insert into test values (1);

INSERT 0 1

T2

postgres=# begin;

BEGIN

postgres=*# lock table test in access exclusive mode ;

LOCK TABLE

T3

postgres=# begin;

BEGIN

postgres=*# lock table test in exclusive mode ;

T4

Case 1:

postgres=*# lock table test in share row exclusive mode nowait;

ERROR: could not obtain lock on relation "test"

--------------------------------------------

Case 2:

postgres=*# lock table test in share row exclusive mode;

LOCK TABLE

At T4 moment in session A, (case 1) when executing SQL “lock table test in share row exclusive mode nowait;”, an error occurs with message “could not obtain lock on relation test";However, (case 2) when executing the SQL above without nowait, lock can be obtained successfully.

Digging into the source code, I find that in case 2 the lock was obtained in the function ProcSleep instead of LockAcquireExtended. Due to nowait logic processed before WaitOnLock->ProcSleep, acquiring lock failed in case 1. Can any changes be made so that the act of such lock granted occurs before WaitOnLock?

Providing a more universal case:

Transaction A already holds an n-mode lock on table test. If then transaction A requests an m-mode lock on table Test, m and n have the following constraints:

(lockMethodTable->conflictTab[n] & lockMethodTable->conflictTab[m]) == lockMethodTable->conflictTab[m]

Obviously, in this case, m<=n.

Should the m-mode lock be granted before WaitOnLock?

In the case of m=n (i.e. we already hold the lock), the m-mode lock is immediately granted in the LocalLock path, without the need of lock conflict check.

Based on the facts above, can we obtain a weaker lock (m<n) on the same object within the same transaction without doing lock conflict check?

Since m=n works, m<n should certainly work too.

I am attaching a patch here with which the problem in case 1 fixed.

I did not see any test added for this, should we add a test case for this?

Regards,
Vignesh

Hello Jingxian Li!

I agree with you that this behavior seems surprising. I don't think
it's quite a bug, more of a limitation. However, I think it would be
nice to fix it if we can find a good way to do that.

On Wed, Nov 29, 2023 at 10:43 PM Jingxian Li <aqktjcm@qq.com> wrote:

Transaction A already holds an n-mode lock on table test,
that is, there is no locks held conflicting with the n-mode lock on table test,
If then transaction A requests an m-mode lock on table test,
as n's confilctTab covers m, it can be concluded that
there are no locks conflicting with the requested m-mode lock.

This algorithm seems correct to me, but I think Andres is right to be
concerned about overhead. You're proposing to inject a call to
CheckLocalLockConflictTabCover() into the main code path of
LockAcquireExtended(), so practically every lock acquisition will pay
the cost of that function. And that function is not particularly
cheap: every call to LockHeldByMe is a hash table lookup. That sounds
pretty painful. If we could incur the overhead of this only when we
knew for certain that we would otherwise have to fail, that would be
more palatable, but doing it on every non-fastpath heavyweight lock
acquisition seems way too expensive.

Even aside from overhead, the approach the patch takes doesn't seem
quite right to me. As you noted, ProcSleep() has logic to jump the
queue if adding ourselves at the end would inevitably result in
deadlock, which is why your test case doesn't need to wait until
deadlock_timeout for the lock acquisition to succeed. But because that
logic happens in ProcSleep(), it's not reached in the NOWAIT case,
which means that it doesn't help any more once NOWAIT is specified. I
think that the right way to fix the problem would be to reach that
check even in the NOWAIT case, which could be done either by hoisting
some of the logic in ProcSleep() up into LockAcquireExtended(), or by
pushing the nowait flag down into ProcSleep() so that we can fail only
if we're definitely going to sleep. The former seems more elegant in
theory, but the latter looks easier to implement, at least at first
glance.

But the patch as proposed instead invents a new way of making the test
case work, not leveraging the existing logic and, I suspect, not
matching the behavior in all cases.

I also agree with Vignesh that a test case would be a good idea. It
would need to be an isolation test, since the regular regression
tester isn't powerful enough for this (at least, I don't see how to
make it work).

I hope that this input is helpful to you.

--
Robert Haas
EDB: http://www.enterprisedb.com

Hello Robert,

Thank you for your advice. It is very helpful to me.

On 2024/1/16 3:07, Robert Haas wrote:

Hello Jingxian Li!

I agree with you that this behavior seems surprising. I don't think
it's quite a bug, more of a limitation. However, I think it would be
nice to fix it if we can find a good way to do that.

On Wed, Nov 29, 2023 at 10:43 PM Jingxian Li <aqktjcm@qq.com> wrote:

Transaction A already holds an n-mode lock on table test,
that is, there is no locks held conflicting with the n-mode lock on table test,
If then transaction A requests an m-mode lock on table test,
as n's confilctTab covers m, it can be concluded that
there are no locks conflicting with the requested m-mode lock.

This algorithm seems correct to me, but I think Andres is right to be
concerned about overhead. You're proposing to inject a call to
CheckLocalLockConflictTabCover() into the main code path of
LockAcquireExtended(), so practically every lock acquisition will pay
the cost of that function. And that function is not particularly
cheap: every call to LockHeldByMe is a hash table lookup. That sounds
pretty painful. If we could incur the overhead of this only when we
knew for certain that we would otherwise have to fail, that would be
more palatable, but doing it on every non-fastpath heavyweight lock
acquisition seems way too expensive.

Even aside from overhead, the approach the patch takes doesn't seem
quite right to me. As you noted, ProcSleep() has logic to jump the
queue if adding ourselves at the end would inevitably result in
deadlock, which is why your test case doesn't need to wait until
deadlock_timeout for the lock acquisition to succeed. But because that
logic happens in ProcSleep(), it's not reached in the NOWAIT case,
which means that it doesn't help any more once NOWAIT is specified. I
think that the right way to fix the problem would be to reach that
check even in the NOWAIT case, which could be done either by hoisting
some of the logic in ProcSleep() up into LockAcquireExtended(), or by
pushing the nowait flag down into ProcSleep() so that we can fail only
if we're definitely going to sleep. The former seems more elegant in
theory, but the latter looks easier to implement, at least at first
glance.

According to what you said, I resubmitted a patch which splits the ProcSleep
logic into two parts, the former is responsible for inserting self to
WaitQueue,
the latter is responsible for deadlock detection and processing, and the
former part is directly called by LockAcquireExtended before nowait fails.
In this way the nowait case can also benefit from adjusting the insertion
order of WaitQueue.

But the patch as proposed instead invents a new way of making the test
case work, not leveraging the existing logic and, I suspect, not
matching the behavior in all cases.

I also agree with Vignesh that a test case would be a good idea. It
would need to be an isolation test, since the regular regression
tester isn't powerful enough for this (at least, I don't see how to
make it work).

A test case was also added in the dir src/test/isolation.

Jingxian Li

On Thu, Feb 1, 2024 at 2:16 AM Jingxian Li <aqktjcm@qq.com> wrote:

According to what you said, I resubmitted a patch which splits the ProcSleep
logic into two parts, the former is responsible for inserting self to
WaitQueue,
the latter is responsible for deadlock detection and processing, and the
former part is directly called by LockAcquireExtended before nowait fails.
In this way the nowait case can also benefit from adjusting the insertion
order of WaitQueue.

I don't have time for a full review of this patch right now
unfortunately, but just looking at it quickly:

- It will be helpful if you write a clear commit message. If it gets
committed, there is a high chance the committer will rewrite your
message, but in the meantime it will help understanding.

- The comment for InsertSelfIntoWaitQueue needs improvement. It is
only one line. And it says "Insert self into queue if dontWait is
false" but then someone will wonder why the function would ever be
called with dontWait = true.

- Between the comments and the commit message, the division of
responsibilities between InsertSelfIntoWaitQueue and ProcSleep needs
to be clearly explained. Right now I don't think it is.

--
Robert Haas
EDB: http://www.enterprisedb.com

Hello Robert,

On 2024/2/2 5:05, Robert Haas wrote:

On Thu, Feb 1, 2024 at 2:16 AM Jingxian Li <aqktjcm@qq.com> wrote:

According to what you said, I resubmitted a patch which splits the ProcSleep
logic into two parts, the former is responsible for inserting self to
WaitQueue,
the latter is responsible for deadlock detection and processing, and the
former part is directly called by LockAcquireExtended before nowait fails.
In this way the nowait case can also benefit from adjusting the insertion
order of WaitQueue.

I don't have time for a full review of this patch right now
unfortunately, but just looking at it quickly:

- It will be helpful if you write a clear commit message. If it gets
committed, there is a high chance the committer will rewrite your
message, but in the meantime it will help understanding.

- The comment for InsertSelfIntoWaitQueue needs improvement. It is
only one line. And it says "Insert self into queue if dontWait is
false" but then someone will wonder why the function would ever be
called with dontWait = true.

- Between the comments and the commit message, the division of
responsibilities between InsertSelfIntoWaitQueue and ProcSleep needs
to be clearly explained. Right now I don't think it is.

Based on your comments above, I improve the commit message and comment for
InsertSelfIntoWaitQueue in new patch.

--
Jingxian Li

Hello Robert,

On 2024/2/2 5:05, Robert Haas wrote:

On Thu, Feb 1, 2024 at 2:16 AM Jingxian Li <aqktjcm@qq.com> wrote:

According to what you said, I resubmitted a patch which splits the ProcSleep
logic into two parts, the former is responsible for inserting self to
WaitQueue,
the latter is responsible for deadlock detection and processing, and the
former part is directly called by LockAcquireExtended before nowait fails.
In this way the nowait case can also benefit from adjusting the insertion
order of WaitQueue.

I don't have time for a full review of this patch right now
unfortunately, but just looking at it quickly:

- It will be helpful if you write a clear commit message. If it gets
committed, there is a high chance the committer will rewrite your
message, but in the meantime it will help understanding.

- The comment for InsertSelfIntoWaitQueue needs improvement. It is
only one line. And it says "Insert self into queue if dontWait is
false" but then someone will wonder why the function would ever be
called with dontWait = true.

- Between the comments and the commit message, the division of
responsibilities between InsertSelfIntoWaitQueue and ProcSleep needs
to be clearly explained. Right now I don't think it is.

Based on your comments above, I improve the commit message and comment for
InsertSelfIntoWaitQueue in new patch.

--
Jingxian Li

On Thu, Feb 8, 2024 at 5:28 AM Jingxian Li <aqktjcm@qq.com> wrote:

Based on your comments above, I improve the commit message and comment for
InsertSelfIntoWaitQueue in new patch.

Well, I had a look at this patch today, and even after reading the new
commit message, I couldn't really convince myself that it was correct.
It may well be entirely correct, but I simply find it hard to tell. It
would help if the comments had been adjusted a bit more, e.g.

/* Skip the wait and just
grant myself the lock. */
- GrantLock(lock, proclock, lockmode);
- GrantAwaitedLock();
return PROC_WAIT_STATUS_OK;

Surely this is not an acceptable change. The comments says "and just
grant myself the lock" but the code no longer does that.

But instead of just complaining, I decided to try writing a version of
the patch that seemed acceptable to me. Here it is. I took a different
approach than you. Instead of splitting up ProcSleep(), I just passed
down the dontWait flag to WaitOnLock() and ProcSleep(). In
LockAcquireExtended(), I moved the existing code that handles giving
up in the don't-wait case from before the call to ProcSleep() to
afterward. As far as I can see, the major way this could be wrong is
if calling ProcSleep() with dontWait = true and having it fail to
acquire the lock changes the state in some way that makes the cleanup
code that I moved incorrect. I don't *think* that's the case, but I
might be wrong.

What do you think of this version?

--
Robert Haas
EDB: http://www.enterprisedb.com

Hello Robert,
On 2024/3/8 1:02, Robert Haas wrote:

But instead of just complaining, I decided to try writing a version of
the patch that seemed acceptable to me. Here it is. I took a different
approach than you. Instead of splitting up ProcSleep(), I just passed
down the dontWait flag to WaitOnLock() and ProcSleep(). In
LockAcquireExtended(), I moved the existing code that handles giving
up in the don't-wait case from before the call to ProcSleep() to
afterward. As far as I can see, the major way this could be wrong is
if calling ProcSleep() with dontWait = true and having it fail to
acquire the lock changes the state in some way that makes the cleanup
code that I moved incorrect. I don't *think* that's the case, but I
might be wrong.

What do you think of this version?

Your version changes less code than mine by pushing the nowait flag down
into ProcSleep(). This looks fine in general, except for a little advice,
which I don't think there is necessary to add 'waiting' suffix to the
process name in function WaitOnLock with dontwait being true, as follows:

--- a/src/backend/storage/lmgr/lock.c
+++ b/src/backend/storage/lmgr/lock.c
@@ -1801,8 +1801,12 @@ WaitOnLock(LOCALLOCK *locallock, ResourceOwner owner, bool dontWait)
 	LOCK_PRINT("WaitOnLock: sleeping on lock",
 			   locallock->lock, locallock->tag.mode);

-	/* adjust the process title to indicate that it's waiting */
-	set_ps_display_suffix("waiting");
+	if (!dontWait)
+	{
+		/* adjust the process title to indicate that it's waiting */
+		set_ps_display_suffix("waiting");			
+	}
+

awaitedLock = locallock;
awaitedOwner = owner;
@@ -1855,9 +1859,12 @@ WaitOnLock(LOCALLOCK *locallock, ResourceOwner owner, bool dontWait)
{
/* In this path, awaitedLock remains set until LockErrorCleanup */

-		/* reset ps display to remove the suffix */
-		set_ps_display_remove_suffix();
-
+		if (!dontWait)
+		{
+			/* reset ps display to remove the suffix */
+			set_ps_display_remove_suffix();
+		}
+	
 		/* and propagate the error */
 		PG_RE_THROW();
 	}
@@ -1865,8 +1872,11 @@ WaitOnLock(LOCALLOCK *locallock, ResourceOwner owner, bool dontWait)

awaitedLock = NULL;

-	/* reset ps display to remove the suffix */
-	set_ps_display_remove_suffix();
+	if (!dontWait)
+	{
+		/* reset ps display to remove the suffix */
+		set_ps_display_remove_suffix();
+	}

LOCK_PRINT("WaitOnLock: wakeup on lock",
locallock->lock, locallock->tag.mode);

--
Jingxian Li

On Mon, Mar 11, 2024 at 11:11 PM Jingxian Li <aqktjcm@qq.com> wrote:

Your version changes less code than mine by pushing the nowait flag down
into ProcSleep(). This looks fine in general, except for a little advice,
which I don't think there is necessary to add 'waiting' suffix to the
process name in function WaitOnLock with dontwait being true, as follows:

That could be done, but in my opinion it's not necessary. The waiting
suffix will appear only very briefly, and probably only in relatively
rare cases. It doesn't seem worth adding code to avoid it.

--
Robert Haas
EDB: http://www.enterprisedb.com

On Tue, Mar 12, 2024 at 9:33 AM Robert Haas <robertmhaas@gmail.com> wrote:

On Mon, Mar 11, 2024 at 11:11 PM Jingxian Li <aqktjcm@qq.com> wrote:

Your version changes less code than mine by pushing the nowait flag down
into ProcSleep(). This looks fine in general, except for a little advice,
which I don't think there is necessary to add 'waiting' suffix to the
process name in function WaitOnLock with dontwait being true, as follows:

That could be done, but in my opinion it's not necessary. The waiting
suffix will appear only very briefly, and probably only in relatively
rare cases. It doesn't seem worth adding code to avoid it.

Seeing no further discussion, I have committed my version of this
patch, with your test case.

Thanks for pursuing this improvement!

--
Robert Haas
EDB: http://www.enterprisedb.com

On Thu, Mar 14, 2024 at 1:15 PM Robert Haas <robertmhaas@gmail.com> wrote:

Seeing no further discussion, I have committed my version of this
patch, with your test case.

This comment on ProcSleep() seems to have the values of dontWait
backward (double negatives are tricky):

* Result: PROC_WAIT_STATUS_OK if we acquired the lock,
PROC_WAIT_STATUS_ERROR
* if not (if dontWait = true, this is a deadlock; if dontWait = false, we
* would have had to wait).

Also there's a minor typo in a comment in LockAcquireExtended():

* Check the proclock entry status. If dontWait = true, this is an
* expected case; otherwise, it will open happen if something in the
* ipc communication doesn't work correctly.

"open" should be "only".

On Tue, Mar 26, 2024 at 7:14 PM Will Mortensen <will@extrahop.com> wrote:

This comment on ProcSleep() seems to have the values of dontWait
backward (double negatives are tricky):

* Result: PROC_WAIT_STATUS_OK if we acquired the lock,
PROC_WAIT_STATUS_ERROR
* if not (if dontWait = true, this is a deadlock; if dontWait = false, we
* would have had to wait).

Also there's a minor typo in a comment in LockAcquireExtended():

* Check the proclock entry status. If dontWait = true, this is an
* expected case; otherwise, it will open happen if something in the
* ipc communication doesn't work correctly.

"open" should be "only".

Here's a patch fixing those typos.

On 2024/5/18 14:38, Will Mortensen wrote:

On Tue, Mar 26, 2024 at 7:14 PM Will Mortensen <will@extrahop.com> wrote:

This comment on ProcSleep() seems to have the values of dontWait
backward (double negatives are tricky):

* Result: PROC_WAIT_STATUS_OK if we acquired the lock,
PROC_WAIT_STATUS_ERROR
* if not (if dontWait = true, this is a deadlock; if dontWait = false, we
* would have had to wait).

Also there's a minor typo in a comment in LockAcquireExtended():

* Check the proclock entry status. If dontWait = true, this is an
* expected case; otherwise, it will open happen if something in the
* ipc communication doesn't work correctly.

"open" should be "only".

Here's a patch fixing those typos.

Nice catch! The patch looks good to me.

--
Jingxian Li

On Fri, May 17, 2024 at 11:38:35PM -0700, Will Mortensen wrote:

On Tue, Mar 26, 2024 at 7:14 PM Will Mortensen <will@extrahop.com> wrote:

This comment on ProcSleep() seems to have the values of dontWait
backward (double negatives are tricky):

* Result: PROC_WAIT_STATUS_OK if we acquired the lock,
PROC_WAIT_STATUS_ERROR
* if not (if dontWait = true, this is a deadlock; if dontWait = false, we
* would have had to wait).

Also there's a minor typo in a comment in LockAcquireExtended():

* Check the proclock entry status. If dontWait = true, this is an
* expected case; otherwise, it will open happen if something in the
* ipc communication doesn't work correctly.

"open" should be "only".

Here's a patch fixing those typos.

Perhaps, this, err.. Should not have been named "dontWait" but
"doWait" ;)

Anyway, this goes way back in time and it is deep in the stack
(LockAcquireExtended, etc.) so it is too late to change: the patch
should be OK as it is.
--
Michael

On Sat, May 18, 2024 at 05:10:38PM +0800, Jingxian Li wrote:

Nice catch! The patch looks good to me.

And fixed that as well.
--
Michael

Thanks! :-)