Revised Patch to allow multiple table locks in "Unison"

The problem with this patch is that it doesn't always lock the tables in
the order supplied by the user, leading to possible deadlock. My guess
is that you need to try locking A, B, C and if B hangs, I think you need
to sleep on B, and when you get it, release the lock on B and try A, B,
C again. I know this is a pain and could fail multiple times, but I
think we have to do it this ay.

Here is the revised patch to allow the syntax:

LOCK a,b,c;

It uses the method I described as the "new" method in a previous
message.

Neil

--
Neil Padgett
Red Hat Canada Ltd. E-Mail: npadgett@redhat.com
2323 Yonge Street, Suite #300,
Toronto, ON M4P 2C9

Index: src/backend/commands/command.c
===================================================================
RCS file:
/home/projects/pgsql/cvsroot/pgsql/src/backend/commands/command.c,v
retrieving revision 1.136
diff -c -p -r1.136 command.c
*** src/backend/commands/command.c	2001/07/16 05:06:57	1.136
--- src/backend/commands/command.c	2001/07/26 00:02:24
*************** needs_toast_table(Relation rel)
*** 1994,2019 ****
void
LockTableCommand(LockStmt *lockstmt)
{
! 	Relation	rel;
! 	int			aclresult;

! rel = heap_openr(lockstmt->relname, NoLock);

! if (rel->rd_rel->relkind != RELKIND_RELATION)
! elog(ERROR, "LOCK TABLE: %s is not a table", lockstmt->relname);

! if (lockstmt->mode == AccessShareLock)
! aclresult = pg_aclcheck(lockstmt->relname, GetUserId(), ACL_SELECT);
! else
! aclresult = pg_aclcheck(lockstmt->relname, GetUserId(),
! ACL_UPDATE | ACL_DELETE);

! if (aclresult != ACLCHECK_OK)
! elog(ERROR, "LOCK TABLE: permission denied");

! LockRelation(rel, lockstmt->mode);

! heap_close(rel, NoLock); /* close rel, keep lock */
}

--- 1994,2170 ----
void
LockTableCommand(LockStmt *lockstmt)
{
! 	int         relCnt;

! relCnt = length(lockstmt -> rellist);

! /* Handle a single relation lock specially to avoid overhead on
likely the
! most common case */

! if(relCnt == 1)
! {

! /* Locking a single table */

! Relation rel;
! int aclresult;
! char *relname;

! relname = strVal(lfirst(lockstmt->rellist));
!
! freeList(lockstmt->rellist);
!
! rel = heap_openr(relname, NoLock);
!
! if (rel->rd_rel->relkind != RELKIND_RELATION)
! elog(ERROR, "LOCK TABLE: %s is not a table", relname);
!
! if (lockstmt->mode == AccessShareLock)
! aclresult = pg_aclcheck(relname, GetUserId(),
! ACL_SELECT);
! else
! aclresult = pg_aclcheck(relname, GetUserId(),
! ACL_UPDATE | ACL_DELETE);
!
! if (aclresult != ACLCHECK_OK)
! elog(ERROR, "LOCK TABLE: permission denied");
!
! LockRelation(rel, lockstmt->mode);
!
! pfree(relname);
!
! heap_close(rel, NoLock); /* close rel, keep lock */
! }
! else
! {
! List *p;
! Relation *relationArray;
! Relation *pRel;
! Relation *blockingLockTarget;
! bool allLocked = false;
!
! /* Locking multiple tables */
!
! /* Create an array of relations */
!
! relationArray = palloc(relCnt * sizeof(Relation));
! blockingLockTarget = relationArray;
!
! pRel = relationArray;
!
! /* Iterate over the list and populate the relation array */
!
! foreach(p, lockstmt->rellist)
! {
! char *relname = strVal(lfirst(p));
! int aclresult;
!
! *pRel = heap_openr(relname, NoLock);
!
! if ((*pRel)->rd_rel->relkind != RELKIND_RELATION)
! elog(ERROR, "LOCK TABLE: %s is not a table",
! relname);
!
! if (lockstmt->mode == AccessShareLock)
! aclresult = pg_aclcheck(relname, GetUserId(),
! ACL_SELECT);
! else
! aclresult = pg_aclcheck(relname, GetUserId(),
! ACL_UPDATE | ACL_DELETE);
!
! if (aclresult != ACLCHECK_OK)
! elog(ERROR, "LOCK TABLE: permission denied");
!
! pRel++;
! pfree(relname);
! }
!
! /* Now acquire locks on all the relations */
!
! while(!allLocked)
! {
!
! allLocked = true;
!
! /* Lock the blocking lock target (initially the first lock
! in the user's list */
!
! LockRelation(*blockingLockTarget, lockstmt->mode);
!
! /* Lock is now obtained on the lock target, now grab locks in a
! non-blocking way on the rest of the list */
!
! for(pRel = blockingLockTarget + 1;
! pRel < relationArray + relCnt;
! pRel++)
! {
! if(!ConditionalLockRelation(*pRel, lockstmt->mode))
! {
! Relation *pRelUnlock;
!
! /* Flag that all relations were not successfully
! locked */
!
! allLocked = false;
!
! /* A lock wasn't obtained, so unlock all others */
!
! for(pRelUnlock = blockingLockTarget;
! pRelUnlock < pRel;
! pRelUnlock++)
! UnlockRelation(*pRelUnlock, lockstmt->mode);
!
! /* Next time, do our blocking lock on the contended lock */
!
! blockingLockTarget = pRel;
!
! /* Now break out and try again */
!
! break;
! }
! }
!
! /* Now, lock anything before the blocking lock target in the lock
! target array, if we were successful in getting locks on
! everything after and including the blocking target */
!
! if(allLocked)
! {
! for(pRel = relationArray;
! pRel < blockingLockTarget;
! pRel++)
! {
! if(!ConditionalLockRelation(*pRel, lockstmt->mode))
! {
! Relation *pRelUnlock;
!
! /* Flag that all relations were not successfully
! locked */
!
! allLocked = false;
!
! /* Lock wasn't obtained, so unlock all others */
!
! for(pRelUnlock = relationArray;
! pRelUnlock < pRel;
! pRelUnlock++)
! UnlockRelation(*pRelUnlock, lockstmt->mode);
!
! /* Next time, do our blocking lock on the contended
! lock */
!
! blockingLockTarget = pRel;
!
! /* Now break out and try again */
!
! break;
! }
! }
! }
! }
!
! pfree(relationArray);
! }
}

Index: src/backend/nodes/copyfuncs.c
===================================================================
RCS file:
/home/projects/pgsql/cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v
retrieving revision 1.148
diff -c -p -r1.148 copyfuncs.c
*** src/backend/nodes/copyfuncs.c	2001/07/16 19:07:37	1.148
--- src/backend/nodes/copyfuncs.c	2001/07/26 00:02:24
*************** _copyLockStmt(LockStmt *from)
*** 2425,2432 ****
{
LockStmt   *newnode = makeNode(LockStmt);

! if (from->relname)
! newnode->relname = pstrdup(from->relname);
newnode->mode = from->mode;

return newnode;
--- 2425,2432 ----
{
LockStmt   *newnode = makeNode(LockStmt);

! Node_Copy(from, newnode, rellist);
!
newnode->mode = from->mode;

return newnode;
Index: src/backend/nodes/equalfuncs.c
===================================================================
RCS file:
/home/projects/pgsql/cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v
retrieving revision 1.96
diff -c -p -r1.96 equalfuncs.c
*** src/backend/nodes/equalfuncs.c	2001/07/16 19:07:38	1.96
--- src/backend/nodes/equalfuncs.c	2001/07/26 00:02:24
*************** _equalDropUserStmt(DropUserStmt *a, Drop
*** 1283,1289 ****
static bool
_equalLockStmt(LockStmt *a, LockStmt *b)
{
! 	if (!equalstr(a->relname, b->relname))
return false;
if (a->mode != b->mode)
return false;
--- 1283,1289 ----
static bool
_equalLockStmt(LockStmt *a, LockStmt *b)
{
! 	if (!equal(a->rellist, b->rellist))
return false;
if (a->mode != b->mode)
return false;
Index: src/backend/parser/gram.y
===================================================================
RCS file: /home/projects/pgsql/cvsroot/pgsql/src/backend/parser/gram.y,v
retrieving revision 2.238
diff -c -p -r2.238 gram.y
*** src/backend/parser/gram.y	2001/07/16 19:07:40	2.238
--- src/backend/parser/gram.y	2001/07/26 00:02:25
*************** DeleteStmt:  DELETE FROM relation_expr w
*** 3280,3290 ****
}
;

! LockStmt: LOCK_P opt_table relation_name opt_lock
{
LockStmt *n = makeNode(LockStmt);

! 					n->relname = $3;
n->mode = $4;
$$ = (Node *)n;
}
--- 3280,3290 ----
}
;

! LockStmt: LOCK_P opt_table relation_name_list opt_lock
{
LockStmt *n = makeNode(LockStmt);

! 					n->rellist = $3;
n->mode = $4;
$$ = (Node *)n;
}
Index: src/include/nodes/parsenodes.h
===================================================================
RCS file:
/home/projects/pgsql/cvsroot/pgsql/src/include/nodes/parsenodes.h,v
retrieving revision 1.136
diff -c -p -r1.136 parsenodes.h
*** src/include/nodes/parsenodes.h	2001/07/16 19:07:40	1.136
--- src/include/nodes/parsenodes.h	2001/07/26 00:02:26
*************** typedef struct VariableResetStmt
*** 760,766 ****
typedef struct LockStmt
{
NodeTag		type;
! 	char	   *relname;		/* relation to lock */
int			mode;			/* lock mode */
} LockStmt;

--- 760,766 ----
typedef struct LockStmt
{
NodeTag		type;
! 	List	   *rellist;		/* relation to lock */
int			mode;			/* lock mode */
} LockStmt;

Index: src/interfaces/ecpg/preproc/preproc.y
===================================================================
RCS file:
/home/projects/pgsql/cvsroot/pgsql/src/interfaces/ecpg/preproc/preproc.y,v
retrieving revision 1.146
diff -c -p -r1.146 preproc.y
*** src/interfaces/ecpg/preproc/preproc.y	2001/07/16 05:07:00	1.146
--- src/interfaces/ecpg/preproc/preproc.y	2001/07/26 00:02:27
*************** DeleteStmt:  DELETE FROM relation_expr w
*** 2421,2427 ****
}
;

! LockStmt:  LOCK_P opt_table relation_name opt_lock
{
$$ = cat_str(4, make_str("lock"), $2, $3, $4);
}
--- 2421,2427 ----
}
;

! LockStmt: LOCK_P opt_table relation_name_list opt_lock
{
$$ = cat_str(4, make_str("lock"), $2, $3, $4);
}

---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://www.postgresql.org/search.mpl

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Bruce Momjian wrote:

The problem with this patch is that it doesn't always lock the tables in
the order supplied by the user, leading to possible deadlock. My guess
is that you need to try locking A, B, C and if B hangs, I think you need
to sleep on B, and when you get it, release the lock on B and try A, B,
C again. I know this is a pain and could fail multiple times, but I
think we have to do it this ay.

Deadlocks are not possible with this patch. The four conditions needed
for deadlock are (according to Operating Systems: Internals and Design
Principles, 4th Ed. by W. Stallings):

1. Mutual exclusion: Only one process may use a resource at a time.
2. Hold and wait: A process may hold allocated resources while awaiting
assignment of others.
3. No preemption: No resources can be forcibly removed from a process
holding it.
4. Circular wait: A closed chain of processes exists, such that each
process holds at least one resource needed by the next process in the
chain.

For deadlock prevention one needs only to prevent the existence of
at least one of the four conditions.

The patch code never holds any of requested locks, while waiting for a
locked relation to become free. If a lock on all tables in the lock list
cannot be acquired at once, it backs off and releases all locks.

Stallings writes about preventing condition 3: "This condition can be
prevented in several ways. [. . .] [One way is to require that,] if a
process holding certain resources is denied a further request, that
process must release its original resources and, if necessary, request
them again together with the additional resources."

This is exactly what the patch does. Observe that if one lock is not
available, the patch releases all locks so far acquired, and then
acquires
the locks again. Hence, condition 3 is prevented, and so deadlock is
prevented.

Neil

p.s. Is this mailing list always this slow?

--
Neil Padgett
Red Hat Canada Ltd. E-Mail: npadgett@redhat.com
2323 Yonge Street, Suite #300,
Toronto, ON M4P 2C9

Bruce Momjian wrote:

The problem with this patch is that it doesn't always lock the tables in
the order supplied by the user, leading to possible deadlock. My guess
is that you need to try locking A, B, C and if B hangs, I think you need
to sleep on B, and when you get it, release the lock on B and try A, B,
C again. I know this is a pain and could fail multiple times, but I
think we have to do it this ay.

Deadlocks are not possible with this patch. The four conditions needed
for deadlock are (according to Operating Systems: Internals and Design
Principles, 4th Ed. by W. Stallings):

...

The patch code never holds any of requested locks, while waiting for a
locked relation to become free. If a lock on all tables in the lock list
cannot be acquired at once, it backs off and releases all locks.

Stallings writes about preventing condition 3: "This condition can be
prevented in several ways. [. . .] [One way is to require that,] if a
process holding certain resources is denied a further request, that
process must release its original resources and, if necessary, request
them again together with the additional resources."

This is exactly what the patch does. Observe that if one lock is not
available, the patch releases all locks so far acquired, and then
acquires
the locks again. Hence, condition 3 is prevented, and so deadlock is
prevented.

Excellent point. I had not considered the fact that you don't hang
waiting for the other locks; you just release them all and try again.

Looks like a great patch, and it seems better than the OID patch in many
ways.

p.s. Is this mailing list always this slow?

Not sure. I have gotten patches stuck in the patches queue recently.
Not sure on the cause. Marc may know.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Your patch has been added to the PostgreSQL unapplied patches list at:

http://candle.pha.pa.us/cgi-bin/pgpatches

I will try to apply it within the next 48 hours.

Bruce Momjian wrote:

The problem with this patch is that it doesn't always lock the tables in
the order supplied by the user, leading to possible deadlock. My guess
is that you need to try locking A, B, C and if B hangs, I think you need
to sleep on B, and when you get it, release the lock on B and try A, B,
C again. I know this is a pain and could fail multiple times, but I
think we have to do it this ay.

Deadlocks are not possible with this patch. The four conditions needed
for deadlock are (according to Operating Systems: Internals and Design
Principles, 4th Ed. by W. Stallings):

1. Mutual exclusion: Only one process may use a resource at a time.
2. Hold and wait: A process may hold allocated resources while awaiting
assignment of others.
3. No preemption: No resources can be forcibly removed from a process
holding it.
4. Circular wait: A closed chain of processes exists, such that each
process holds at least one resource needed by the next process in the
chain.

For deadlock prevention one needs only to prevent the existence of
at least one of the four conditions.

The patch code never holds any of requested locks, while waiting for a
locked relation to become free. If a lock on all tables in the lock list
cannot be acquired at once, it backs off and releases all locks.

Stallings writes about preventing condition 3: "This condition can be
prevented in several ways. [. . .] [One way is to require that,] if a
process holding certain resources is denied a further request, that
process must release its original resources and, if necessary, request
them again together with the additional resources."

This is exactly what the patch does. Observe that if one lock is not
available, the patch releases all locks so far acquired, and then
acquires
the locks again. Hence, condition 3 is prevented, and so deadlock is
prevented.

Neil

p.s. Is this mailing list always this slow?

--
Neil Padgett
Red Hat Canada Ltd. E-Mail: npadgett@redhat.com
2323 Yonge Street, Suite #300,
Toronto, ON M4P 2C9

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Bruce Momjian wrote:

Bruce Momjian wrote:

[snip]

Deadlocks are not possible with this patch. The four conditions needed
for deadlock are (according to Operating Systems: Internals and Design
Principles, 4th Ed. by W. Stallings):

...

The patch code never holds any of requested locks, while waiting for a
locked relation to become free. If a lock on all tables in the lock list
cannot be acquired at once, it backs off and releases all locks.

Stallings writes about preventing condition 3: "This condition can be
prevented in several ways. [. . .] [One way is to require that,] if a
process holding certain resources is denied a further request, that
process must release its original resources and, if necessary, request
them again together with the additional resources."

This is exactly what the patch does. Observe that if one lock is not
available, the patch releases all locks so far acquired, and then
acquires
the locks again. Hence, condition 3 is prevented, and so deadlock is
prevented.

Excellent point. I had not considered the fact that you don't hang
waiting for the other locks; you just release them all and try again.

I have a question.
What will happen when the second table is locked for a long time
though the first table isn't locked ?

regards,
Hiroshi Ioue

On Mon, 30 Jul 2001, Hiroshi Inoue wrote:

I have a question.
What will happen when the second table is locked for a long time
though the first table isn't locked ?

Consider the case:

LOCK a,b;

Assume a is free (i.e. not locked), but b is busy (i.e. locked).

First the system will do a blocking lock attempt on a, which will return
immediately, since a was free. Table a is now locked. Now, the system will
try a non-blocking lock on b. But, b is busy so the lock attempt will fail
immediately (since the lock attempt was non-blocking). So, the system will
back off, and the lock on a is released.

Next, a blocking lock attempt will be made on b. (Since it was busy last
time, we want to wait for it to become free.) The lock call will block
until b becomes free. At that time, the lock attempt will return, and b
will be locked. Then, a non-blocking lock attempt will be made on table a.
(Recall that we don't have a lock on it, since we released it during
back-off earlier.) Assuming a is still free, it will be locked and the
LOCK command will complete. Otherwise, if a is busy, the lock attempt will
then restart with a blocking lock attempt on a. The procedure will
continue until all tables are free to lock.

In summary, no locks are held while waiting for tables to become free --
in essence, the tables are locked all at once, once all tables in the
LOCK statement are free.

Neil

--
Neil Padgett
Red Hat Canada Ltd. E-Mail: npadgett@redhat.com
2323 Yonge Street, Suite #300,
Toronto, ON M4P 2C9

On Mon, 30 Jul 2001, Hiroshi Inoue wrote:

I have a question.
What will happen when the second table is locked for a long time
though the first table isn't locked ?

Consider the case:

LOCK a,b;

Assume a is free (i.e. not locked), but b is busy (i.e. locked).

First the system will do a blocking lock attempt on a, which will return
immediately, since a was free. Table a is now locked. Now, the system will
try a non-blocking lock on b. But, b is busy so the lock attempt will fail
immediately (since the lock attempt was non-blocking). So, the system will
back off, and the lock on a is released.

Next, a blocking lock attempt will be made on b. (Since it was busy last
time, we want to wait for it to become free.) The lock call will block
until b becomes free. At that time, the lock attempt will return, and b
will be locked. Then, a non-blocking lock attempt will be made on table a.
(Recall that we don't have a lock on it, since we released it during
back-off earlier.) Assuming a is still free, it will be locked and the
LOCK command will complete. Otherwise, if a is busy, the lock attempt will
then restart with a blocking lock attempt on a. The procedure will
continue until all tables are free to lock.

In summary, no locks are held while waiting for tables to become free --
in essence, the tables are locked all at once, once all tables in the
LOCK statement are free.

The more I think about it the more I like it. I never would have
thought of the idea myself.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Stallings writes about preventing condition 3: "This condition can be
prevented in several ways. [. . .] [One way is to require that,] if a
process holding certain resources is denied a further request, that
process must release its original resources and, if necessary, request
them again together with the additional resources."

This is exactly what the patch does.

No, that is not what it does. Note that Stallings specifies that the
failed requestor must release ALL previously held resources. That is
not feasible in Postgres; some of the locks may be held due to previous
commands in the same transaction. Consider this scenario:

Process 1 Process 2

LOCK a; LOCK b;
... ...
LOCK b,c; LOCK a,c;

The second LOCK statements cannot release the locks already held,
therefore this is a deadlock. While that's no worse than we had
before, I believe that your patch introduces a possibility of
undetected deadlock. Consider this:

Process 1 Process 2

LOCK a,b; LOCK b,a;

A possible interleaving of execution is: 1 acquires lock a, 2 acquires
b, 1 tries to acquire b and fails, 2 tries to acquire a and fails,
1 releases a, 2 releases b, 1 acquires b, 2 acquires a, 1 tries to
acquire a and fails, etc etc. It's implausible that this condition
would persist in perfect lockstep for very long on a uniprocessor
machine ... but not so implausible if you have dual CPUs, each running
one of the two processes at exactly the same speed.

I haven't quite managed to work out a full scenario, but I think it is
possible that the combination of these two effects could result in an
indefinite, never-detected deadlock --- without implausible assumptions
about process speed. It'd probably take three or more processes
contending for several locks, but it seems possible to construct a
failure scenario.

I think that the only safe way to do something like this is to teach
the lock manager itself about multiple simultaneous requests.

regards, tom lane

Neil Padgett wrote:

On Mon, 30 Jul 2001, Hiroshi Inoue wrote:

I have a question.
What will happen when the second table is locked for a long time
though the first table isn't locked ?

Consider the case:

LOCK a,b;

Assume a is free (i.e. not locked), but b is busy (i.e. locked).

First the system will do a blocking lock attempt on a, which will return
immediately, since a was free. Table a is now locked. Now, the system will
try a non-blocking lock on b. But, b is busy so the lock attempt will fail
immediately (since the lock attempt was non-blocking). So, the system will
back off, and the lock on a is released.

Next, a blocking lock attempt will be made on b. (Since it was busy last
time, we want to wait for it to become free.) The lock call will block
until b becomes free. At that time, the lock attempt will return, and b
will be locked. Then, a non-blocking lock attempt will be made on table a.

Is it paranoid to worry about the followings ?

1) Concurrent 'lock table a, b;' and 'lock table b, a;'
could last forever in theory ?
2) 'Lock table a,b' could hardly acquire the lock when
both the table a and b are very frequently accessed.

regards,
Hiroshi Inoue

First the system will do a blocking lock attempt on a, which will return
immediately, since a was free. Table a is now locked. Now, the system will
try a non-blocking lock on b. But, b is busy so the lock attempt will fail
immediately (since the lock attempt was non-blocking). So, the system will
back off, and the lock on a is released.

Next, a blocking lock attempt will be made on b. (Since it was busy last
time, we want to wait for it to become free.) The lock call will block
until b becomes free. At that time, the lock attempt will return, and b
will be locked. Then, a non-blocking lock attempt will be made on table a.

Is it paranoid to worry about the followings ?

1) Concurrent 'lock table a, b;' and 'lock table b, a;'
could last forever in theory ?
2) 'Lock table a,b' could hardly acquire the lock when
both the table a and b are very frequently accessed.

Well, we do tell people to lock things in the same order. If they did
this with two lock statements, they would cause a deadlock. In this
case, they could grab their first lock at the same time, fail on the
second, and wait on the second, get it, fail on the first, and go all
over again. However, they would have to stay synchronized to do this.
If one got out of step it would stop.

Actually, with this new code, we could go back to locking in oid order,
which would eliminate the problem. However, I prefer to do things in
the order specified, at least on the first lock try.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Bruce Momjian <pgman@candle.pha.pa.us> writes:

Actually, with this new code, we could go back to locking in oid order,
which would eliminate the problem.

No it wouldn't. If anything, locking in a *randomized* order would be
the best bet. But I have no confidence in this approach, anyway.

regards, tom lane

Tom Lane wrote:

Stallings writes about preventing condition 3: "This condition can be
prevented in several ways. [. . .] [One way is to require that,] if a
process holding certain resources is denied a further request, that
process must release its original resources and, if necessary, request
them again together with the additional resources."

This is exactly what the patch does.

No, that is not what it does. Note that Stallings specifies that the
failed requestor must release ALL previously held resources. That is
not feasible in Postgres; some of the locks may be held due to previous
commands in the same transaction. Consider this scenario:

Process 1 Process 2

LOCK a; LOCK b;
... ...
LOCK b,c; LOCK a,c;

The second LOCK statements cannot release the locks already held,
therefore this is a deadlock.

But that is a programmer's error. He/she is acquiring the locks in
reversed order. The fact that the second lock request is in a multiple
lock is not much different from doing it with a single lock like in:

Process 1 Process 2

LOCK a; LOCK b;
... ...
LOCK b; LOCK a;

I guess you've mentioned this scenario because of the undetected
deadlock
concerns, right?

While that's no worse than we had
before, I believe that your patch introduces a possibility of
undetected deadlock. Consider this:

Process 1 Process 2

LOCK a,b; LOCK b,a;

A possible interleaving of execution is: 1 acquires lock a, 2 acquires
b, 1 tries to acquire b and fails, 2 tries to acquire a and fails,
1 releases a, 2 releases b, 1 acquires b, 2 acquires a, 1 tries to
acquire a and fails, etc etc. It's implausible that this condition
would persist in perfect lockstep for very long on a uniprocessor
machine ... but not so implausible if you have dual CPUs, each running
one of the two processes at exactly the same speed.

I haven't quite managed to work out a full scenario, but I think it is
possible that the combination of these two effects could result in an
indefinite, never-detected deadlock --- without implausible assumptions
about process speed.

I believe the undetected deadlock is not possible. To get the multiple
lock statement involved in the deadlock scenario, at least one of the
locks
desired must have been acquired (in a separate statement) by the other
process.

The key property of the algorithm that prevents the undetected deadlocks
is
that it waits on the last failed-to-acquire lock.

As the algorithm waits on the last non-obtained lock and restarts
from there (in a circular fashion), it will eventually reach the lock
that
the other process has and then stop for good (thus allowing the deadlock
detection to see it).

Even if the algorithm started always from the first specified lock and
then
got in the lockstep mode you've described, the (potential) deadlock
would
not be detected because it had not happened yet. It will only happen
when
the 2nd situation you've described ceases to exist and the crossed locks
are
attempted. But them the processes are really stopped and the deadlock
can be detected.

--
Fernando Nasser
Red Hat Canada Ltd. E-Mail: fnasser@redhat.com
2323 Yonge Street, Suite #300
Toronto, Ontario M4P 2C9

Hiroshi Inoue wrote:

Is it paranoid to worry about the followings ?

1) Concurrent 'lock table a, b;' and 'lock table b, a;'
could last forever in theory ?

You would need a very evil timeslice duration on a single processor, but
it
could happen on a dual processor. However, the two processes would have
to
be synchronized in a very narrow window of instructions, the schedulers
in
both machines would have to be precisely synchronized and absolutely no
interruption (that is not common to both machines) could never occur.
Even a keyboard press will break the enchantment.

I guess it is what we call "unstable equilibrium", possible in theory
but
never happens in practice except for an infinitesimal amount of time.
It is trying to make an egg stand on one end or something like that
(without breaking the egg, of course :-) ).

2) 'Lock table a,b' could hardly acquire the lock when
both the table a and b are very frequently accessed.

Yes, multiple locks with the back off is less aggressive than obtaining
and holding the locks (with individual lock commands).

--
Fernando Nasser
Red Hat Canada Ltd. E-Mail: fnasser@redhat.com
2323 Yonge Street, Suite #300
Toronto, Ontario M4P 2C9

Bruce Momjian <pgman@candle.pha.pa.us> writes:

Actually, with this new code, we could go back to locking in oid order,
which would eliminate the problem.

No it wouldn't. If anything, locking in a *randomized* order would be
the best bet. But I have no confidence in this approach, anyway.

I am looking for a way to get this in there without munging the lock
code, which is already quite complex. What about doing some sort of
small sleep after we reset back to the beginning of the table list.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

The second LOCK statements cannot release the locks already held,
therefore this is a deadlock.

But that is a programmer's error. He/she is acquiring the locks in
reversed order. The fact that the second lock request is in a multiple
lock is not much different from doing it with a single lock like in:

Process 1 Process 2

LOCK a; LOCK b;
... ...
LOCK b; LOCK a;

I guess you've mentioned this scenario because of the undetected
deadlock
concerns, right?

I guess so. The above would issue a deadlock error message, while the
LOCK a,b would just spin around.

While that's no worse than we had
before, I believe that your patch introduces a possibility of
undetected deadlock. Consider this:

Process 1 Process 2

LOCK a,b; LOCK b,a;

A possible interleaving of execution is: 1 acquires lock a, 2 acquires
b, 1 tries to acquire b and fails, 2 tries to acquire a and fails,
1 releases a, 2 releases b, 1 acquires b, 2 acquires a, 1 tries to
acquire a and fails, etc etc. It's implausible that this condition
would persist in perfect lockstep for very long on a uniprocessor
machine ... but not so implausible if you have dual CPUs, each running
one of the two processes at exactly the same speed.

I haven't quite managed to work out a full scenario, but I think it is
possible that the combination of these two effects could result in an
indefinite, never-detected deadlock --- without implausible assumptions
about process speed.

I believe the undetected deadlock is not possible. To get the multiple
lock statement involved in the deadlock scenario, at least one of the
locks
desired must have been acquired (in a separate statement) by the other
process.

The key property of the algorithm that prevents the undetected deadlocks
is
that it waits on the last failed-to-acquire lock.

As the algorithm waits on the last non-obtained lock and restarts
from there (in a circular fashion), it will eventually reach the lock
that
the other process has and then stop for good (thus allowing the deadlock
detection to see it).

Even if the algorithm started always from the first specified lock and
then
got in the lockstep mode you've described, the (potential) deadlock
would
not be detected because it had not happened yet. It will only happen
when
the 2nd situation you've described ceases to exist and the crossed locks
are
attempted. But them the processes are really stopped and the deadlock
can be detected.

The unusual case here is that deadlock is not checked on request, but
only after waiting on the lock for a while. This is because deadlock
detection is an expensive operation. In fact, you don't want deadlock
detection in this case because LOCK a,b could be evaluated as a,b or b,a
and you don't want it to fail randomly with deadlock messages.

I certainly would like to find a solution to this that makes everyone
comfortable.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

On Mon, 30 Jul 2001, Bruce Momjian wrote:

Bruce Momjian <pgman@candle.pha.pa.us> writes:

Actually, with this new code, we could go back to locking in oid order,
which would eliminate the problem.

No it wouldn't. If anything, locking in a *randomized* order would be
the best bet. But I have no confidence in this approach, anyway.

I am looking for a way to get this in there without munging the lock
code, which is already quite complex. What about doing some sort of
small sleep after we reset back to the beginning of the table list.

It seems to me that we already have a small sleep in place. After all, in
order to acquite a lock, the shared memory area has to be accessed. So,
the contenders for a lock both have to go through a spin lock. So, if we
have the two "stuck" processes as in Tom's example, one will win at
acquiring the spin lock and the other will have to wait. So, they become
desynchronized, regardless of how many CPUs or what memory architecture
you have.

Neil

--
Neil Padgett
Red Hat Canada Ltd. E-Mail: npadgett@redhat.com
2323 Yonge Street, Suite #300,
Toronto, ON M4P 2C9

On Mon, 30 Jul 2001, Bruce Momjian wrote:

Bruce Momjian <pgman@candle.pha.pa.us> writes:

Actually, with this new code, we could go back to locking in oid order,
which would eliminate the problem.

No it wouldn't. If anything, locking in a *randomized* order would be
the best bet. But I have no confidence in this approach, anyway.

I am looking for a way to get this in there without munging the lock
code, which is already quite complex. What about doing some sort of
small sleep after we reset back to the beginning of the table list.

It seems to me that we already have a small sleep in place. After all, in
order to acquite a lock, the shared memory area has to be accessed. So,
the contenders for a lock both have to go through a spin lock. So, if we
have the two "stuck" processes as in Tom's example, one will win at
acquiring the spin lock and the other will have to wait. So, they become
desynchronized, regardless of how many CPUs or what memory architecture
you have.

I see your point now, that they can't synchronize because they have to
go through the same semaphore and therefore get out of sync. Do they
get out of sync enough for one to get the lock while the other is not
holding it, or do the locks actually keep them in sync? I don't know
the answer.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Bruce Momjian wrote:

The unusual case here is that deadlock is not checked on request, but
only after waiting on the lock for a while. This is because deadlock
detection is an expensive operation.

But that is what happens. If one of the locks is not obtained, the
algorithm does wait on that lock (after releasing the other locks).
In the case of a deadlock (tom's scenario #1) it would wait forever,
but the deadlock detection will find it in there and break it.

In fact, you don't want deadlock
detection in this case because LOCK a,b could be evaluated as a,b or b,a
and you don't want it to fail randomly with deadlock messages.

It does not change the deadlock scenario at all. It is still determined
by the resources in a previous (independent) LOCK statement and the ones
on
this LOCK statement (being it multiple or not) to be crossed.

And deadlock failures will be intermittent anyway. A potential deadlock
condition may or may not happen each time depending on the interleaving
of
execution of the two processes.

--
Fernando Nasser
Red Hat Canada Ltd. E-Mail: fnasser@redhat.com
2323 Yonge Street, Suite #300
Toronto, Ontario M4P 2C9

Bruce Momjian wrote:

The unusual case here is that deadlock is not checked on request, but
only after waiting on the lock for a while. This is because deadlock
detection is an expensive operation.

But that is what happens. If one of the locks is not obtained, the
algorithm does wait on that lock (after releasing the other locks).
In the case of a deadlock (tom's scenario #1) it would wait forever,
but the deadlock detection will find it in there and break it.

OK, I thought you were talking about the LOCK a,b case, not the other
case where we had a previous LOCK statement. Sorry.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026