Skip to content

Commit b75fcf9

Browse files
bmomjianbmomjian
committed
Complete TODO item:
* -HOLDER/HOLDERTAB rename to PROCLOCK/PROCLOCKTAG
1 parent 9737704 commit b75fcf9

File tree

6 files changed

+200
-194
lines changed

6 files changed

+200
-194
lines changed

‎src/backend/storage/lmgr/README

Lines changed: 112 additions & 106 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
$Header: /cvsroot/pgsql/src/backend/storage/lmgr/README,v 1.10 2002/04/15 23:46:13 momjian Exp $
1+
$Header: /cvsroot/pgsql/src/backend/storage/lmgr/README,v 1.11 2002/07/19 00:17:40 momjian Exp $
22

33

44
LOCKING OVERVIEW
@@ -7,48 +7,50 @@ Postgres uses three types of interprocess locks:
77

88
* Spinlocks. These are intended for *very* short-term locks. If a lock
99
is to be held more than a few dozen instructions, or across any sort of
10-
kernel call (or even a call to a nontrivial subroutine), don't use a spinlock.
11-
Spinlocks are primarily used as infrastructure for lightweight locks.
12-
They are implemented using a hardware atomic-test-and-set instruction,
13-
if available. Waiting processes busy-loop until they can get the lock.
14-
There is no provision for deadlock detection, automatic release on error,
15-
or any other nicety. There is a timeout if the lock cannot be gotten after
16-
a minute or so (which is approximately forever in comparison to the intended
17-
lock hold time, so this is certainly an error condition).
18-
19-
* Lightweight locks (LWLocks). These locks are typically used to interlock
20-
access to datastructures in shared memory. LWLocks support both exclusive
21-
and shared lock modes (for read/write and read-only access to a shared object).
22-
There is no provision for deadlock detection, but the LWLock manager will
23-
automatically release held LWLocks during elog() recovery, so it is safe to
24-
raise an error while holding LWLocks. Obtaining or releasing an LWLock is
25-
quite fast (a few dozen instructions) when there is no contention for the
26-
lock. When a process has to wait for an LWLock, it blocks on a SysV semaphore
27-
so as to not consume CPU time. Waiting processes will be granted the lock
28-
in arrival order. There is no timeout.
29-
30-
* Regular locks (a/k/a heavyweight locks). The regular lock manager supports
31-
a variety of lock modes with table-driven semantics, and it has full deadlock
32-
detection and automatic release at transaction end. Regular locks should be
33-
used for all user-driven lock requests.
34-
35-
Acquisition of either a spinlock or a lightweight lock causes query cancel
36-
and die() interrupts to be held off until all such locks are released.
37-
No such restriction exists for regular locks, however. Also note that we
38-
can accept query cancel and die() interrupts while waiting for a regular
39-
lock, but we will not accept them while waiting for spinlocks or LW locks.
40-
It is therefore not a good idea to use LW locks when the wait time might
41-
exceed a few seconds.
10+
kernel call (or even a call to a nontrivial subroutine), don't use a
11+
spinlock. Spinlocks are primarily used as infrastructure for lightweight
12+
locks. They are implemented using a hardware atomic-test-and-set
13+
instruction, if available. Waiting processes busy-loop until they can
14+
get the lock. There is no provision for deadlock detection, automatic
15+
release on error, or any other nicety. There is a timeout if the lock
16+
cannot be gotten after a minute or so (which is approximately forever in
17+
comparison to the intended lock hold time, so this is certainly an error
18+
condition).
19+
20+
* Lightweight locks (LWLocks). These locks are typically used to
21+
interlock access to datastructures in shared memory. LWLocks support
22+
both exclusive and shared lock modes (for read/write and read-only
23+
access to a shared object). There is no provision for deadlock
24+
detection, but the LWLock manager will automatically release held
25+
LWLocks during elog() recovery, so it is safe to raise an error while
26+
holding LWLocks. Obtaining or releasing an LWLock is quite fast (a few
27+
dozen instructions) when there is no contention for the lock. When a
28+
process has to wait for an LWLock, it blocks on a SysV semaphore so as
29+
to not consume CPU time. Waiting processes will be granted the lock in
30+
arrival order. There is no timeout.
31+
32+
* Regular locks (a/k/a heavyweight locks). The regular lock manager
33+
supports a variety of lock modes with table-driven semantics, and it has
34+
full deadlock detection and automatic release at transaction end.
35+
Regular locks should be used for all user-driven lock requests.
36+
37+
Acquisition of either a spinlock or a lightweight lock causes query
38+
cancel and die() interrupts to be held off until all such locks are
39+
released. No such restriction exists for regular locks, however. Also
40+
note that we can accept query cancel and die() interrupts while waiting
41+
for a regular lock, but we will not accept them while waiting for
42+
spinlocks or LW locks. It is therefore not a good idea to use LW locks
43+
when the wait time might exceed a few seconds.
4244

4345
The rest of this README file discusses the regular lock manager in detail.
4446

4547

4648
LOCK DATA STRUCTURES
4749

4850
There are two fundamental lock structures: the per-lockable-object LOCK
49-
struct, and the per-lock-holder HOLDER struct. A LOCK object exists
51+
struct, and the per-lock-holder PROCLOCK struct. A LOCK object exists
5052
for each lockable object that currently has locks held or requested on it.
51-
A HOLDER struct exists for each transaction that is holding or requesting
53+
A PROCLOCK struct exists for each transaction that is holding or requesting
5254
lock(s) on each LOCK object.
5355

5456
Lock methods describe the overall locking behavior. Currently there are
@@ -102,9 +104,9 @@ waitMask -
102104
is 1 if and only if requested[i] > granted[i].
103105

104106
lockHolders -
105-
This is a shared memory queue of all the HOLDER structs associated with
106-
the lock object. Note that both granted and waiting HOLDERs are in this
107-
list (indeed, the same HOLDER might have some already-granted locks and
107+
This is a shared memory queue of all the PROCLOCK structs associated with
108+
the lock object. Note that both granted and waiting PROCLOCKs are in this
109+
list (indeed, the same PROCLOCK might have some already-granted locks and
108110
be waiting for more!).
109111

110112
waitProcs -
@@ -144,22 +146,22 @@ zero, the lock object is no longer needed and can be freed.
144146

145147
---------------------------------------------------------------------------
146148

147-
The lock manager's HOLDER objects contain:
149+
The lock manager's PROCLOCK objects contain:
148150

149151
tag -
150152
The key fields that are used for hashing entries in the shared memory
151-
holder hash table. This is declared as a separate struct to ensure that
153+
PROCLOCK hash table. This is declared as a separate struct to ensure that
152154
we always zero out the correct number of bytes.
153155

154156
tag.lock
155-
SHMEM offset of the LOCK object this holder is for.
157+
SHMEM offset of the LOCK object this PROCLOCK is for.
156158

157159
tag.proc
158-
SHMEM offset of PROC of backend process that owns this holder.
160+
SHMEM offset of PROC of backend process that owns this PROCLOCK.
159161

160162
tag.xid
161-
XID of transaction this holder is for, or InvalidTransactionId
162-
if the holder is for session-level locking.
163+
XID of transaction this PROCLOCK is for, or InvalidTransactionId
164+
if the PROCLOCK is for session-level locking.
163165

164166
Note that this structure will support multiple transactions running
165167
concurrently in one backend, which may be handy if we someday decide
@@ -169,18 +171,18 @@ tag -
169171
transaction operations like VACUUM.
170172

171173
holding -
172-
The number of successfully acquired locks of each type for this holder.
174+
The number of successfully acquired locks of each type for this PROCLOCK.
173175
This should be <= the corresponding granted[] value of the lock object!
174176

175177
nHolding -
176178
Sum of the holding[] array.
177179

178180
lockLink -
179-
List link for shared memory queue of all the HOLDER objects for the
181+
List link for shared memory queue of all the PROCLOCK objects for the
180182
same LOCK.
181183

182184
procLink -
183-
List link for shared memory queue of all the HOLDER objects for the
185+
List link for shared memory queue of all the PROCLOCK objects for the
184186
same backend.
185187

186188
---------------------------------------------------------------------------
@@ -193,47 +195,48 @@ fairly standard in essence, but there are many special considerations
193195
needed to deal with Postgres' generalized locking model.
194196

195197
A key design consideration is that we want to make routine operations
196-
(lock grant and release) run quickly when there is no deadlock, and avoid
197-
the overhead of deadlock handling as much as possible. We do this using
198-
an "optimistic waiting" approach: if a process cannot acquire the lock
199-
it wants immediately, it goes to sleep without any deadlock check. But
200-
it also sets a delay timer, with a delay of DeadlockTimeout milliseconds
201-
(typically set to one second). If the delay expires before the process is
202-
granted the lock it wants, it runs the deadlock detection/breaking code.
203-
Normally this code will determine that there is no deadlock condition,
204-
and then the process will go back to sleep and wait quietly until it is
205-
granted the lock. But if a deadlock condition does exist, it will be
206-
resolved, usually by aborting the detecting process' transaction. In this
207-
way, we avoid deadlock handling overhead whenever the wait time for a lock
208-
is less than DeadlockTimeout, while not imposing an unreasonable delay of
209-
detection when there is an error.
198+
(lock grant and release) run quickly when there is no deadlock, and
199+
avoid the overhead of deadlock handling as much as possible. We do this
200+
using an "optimistic waiting" approach: if a process cannot acquire the
201+
lock it wants immediately, it goes to sleep without any deadlock check.
202+
But it also sets a delay timer, with a delay of DeadlockTimeout
203+
milliseconds (typically set to one second). If the delay expires before
204+
the process is granted the lock it wants, it runs the deadlock
205+
detection/breaking code. Normally this code will determine that there is
206+
no deadlock condition, and then the process will go back to sleep and
207+
wait quietly until it is granted the lock. But if a deadlock condition
208+
does exist, it will be resolved, usually by aborting the detecting
209+
process' transaction. In this way, we avoid deadlock handling overhead
210+
whenever the wait time for a lock is less than DeadlockTimeout, while
211+
not imposing an unreasonable delay of detection when there is an error.
210212

211213
Lock acquisition (routines LockAcquire and ProcSleep) follows these rules:
212214

213-
1. A lock request is granted immediately if it does not conflict with any
214-
existing or waiting lock request, or if the process already holds an
215+
1. A lock request is granted immediately if it does not conflict with
216+
any existing or waiting lock request, or if the process already holds an
215217
instance of the same lock type (eg, there's no penalty to acquire a read
216-
lock twice). Note that a process never conflicts with itself, eg one can
217-
obtain read lock when one already holds exclusive lock.
218-
219-
2. Otherwise the process joins the lock's wait queue. Normally it will be
220-
added to the end of the queue, but there is an exception: if the process
221-
already holds locks on this same lockable object that conflict with the
222-
request of any pending waiter, then the process will be inserted in the
223-
wait queue just ahead of the first such waiter. (If we did not make this
224-
check, the deadlock detection code would adjust the queue order to resolve
225-
the conflict, but it's relatively cheap to make the check in ProcSleep and
226-
avoid a deadlock timeout delay in this case.) Note special case when
227-
inserting before the end of the queue: if the process's request does not
228-
conflict with any existing lock nor any waiting request before its insertion
229-
point, then go ahead and grant the lock without waiting.
218+
lock twice). Note that a process never conflicts with itself, eg one
219+
can obtain read lock when one already holds exclusive lock.
220+
221+
2. Otherwise the process joins the lock's wait queue. Normally it will
222+
be added to the end of the queue, but there is an exception: if the
223+
process already holds locks on this same lockable object that conflict
224+
with the request of any pending waiter, then the process will be
225+
inserted in the wait queue just ahead of the first such waiter. (If we
226+
did not make this check, the deadlock detection code would adjust the
227+
queue order to resolve the conflict, but it's relatively cheap to make
228+
the check in ProcSleep and avoid a deadlock timeout delay in this case.)
229+
Note special case when inserting before the end of the queue: if the
230+
process's request does not conflict with any existing lock nor any
231+
waiting request before its insertion point, then go ahead and grant the
232+
lock without waiting.
230233

231234
When a lock is released, the lock release routine (ProcLockWakeup) scans
232235
the lock object's wait queue. Each waiter is awoken if (a) its request
233236
does not conflict with already-granted locks, and (b) its request does
234237
not conflict with the requests of prior un-wakable waiters. Rule (b)
235-
ensures that conflicting requests are granted in order of arrival.
236-
There are cases where a later waiter must be allowed to go in front of
238+
ensures that conflicting requests are granted in order of arrival. There
239+
are cases where a later waiter must be allowed to go in front of
237240
conflicting earlier waiters to avoid deadlock, but it is not
238241
ProcLockWakeup's responsibility to recognize these cases; instead, the
239242
deadlock detection code will re-order the wait queue when necessary.
@@ -242,35 +245,36 @@ To perform deadlock checking, we use the standard method of viewing the
242245
various processes as nodes in a directed graph (the waits-for graph or
243246
WFG). There is a graph edge leading from process A to process B if A
244247
waits for B, ie, A is waiting for some lock and B holds a conflicting
245-
lock. There is a deadlock condition if and only if the WFG contains
246-
a cycle. We detect cycles by searching outward along waits-for edges
247-
to see if we return to our starting point. There are three possible
248+
lock. There is a deadlock condition if and only if the WFG contains a
249+
cycle. We detect cycles by searching outward along waits-for edges to
250+
see if we return to our starting point. There are three possible
248251
outcomes:
249252

250253
1. All outgoing paths terminate at a running process (which has no
251254
outgoing edge).
252255

253-
2. A deadlock is detected by looping back to the start point. We resolve
254-
such a deadlock by canceling the start point's lock request and reporting
255-
an error in that transaction, which normally leads to transaction abort
256-
and release of that transaction's held locks. Note that it's sufficient
257-
to cancel one request to remove the cycle; we don't need to kill all the
258-
transactions involved.
256+
2. A deadlock is detected by looping back to the start point. We
257+
resolve such a deadlock by canceling the start point's lock request and
258+
reporting an error in that transaction, which normally leads to
259+
transaction abort and release of that transaction's held locks. Note
260+
that it's sufficient to cancel one request to remove the cycle; we don't
261+
need to kill all the transactions involved.
259262

260263
3. Some path(s) loop back to a node other than the start point. This
261-
indicates a deadlock, but one that does not involve our starting process.
262-
We ignore this condition on the grounds that resolving such a deadlock
263-
is the responsibility of the processes involved --- killing our start-
264-
point process would not resolve the deadlock. So, cases 1 and 3 both
265-
report "no deadlock".
264+
indicates a deadlock, but one that does not involve our starting
265+
process. We ignore this condition on the grounds that resolving such a
266+
deadlock is the responsibility of the processes involved --- killing our
267+
start- point process would not resolve the deadlock. So, cases 1 and 3
268+
both report "no deadlock".
266269

267270
Postgres' situation is a little more complex than the standard discussion
268271
of deadlock detection, for two reasons:
269272

270273
1. A process can be waiting for more than one other process, since there
271-
might be multiple holders of (non-conflicting) lock types that all conflict
272-
with the waiter's request. This creates no real difficulty however; we
273-
simply need to be prepared to trace more than one outgoing edge.
274+
might be multiple PROCLOCKs of (non-conflicting) lock types that all
275+
conflict with the waiter's request. This creates no real difficulty
276+
however; we simply need to be prepared to trace more than one outgoing
277+
edge.
274278

275279
2. If a process A is behind a process B in some lock's wait queue, and
276280
their requested locks conflict, then we must say that A waits for B, since
@@ -409,16 +413,18 @@ LockWaitCancel (abort a waiter due to outside factors) must run
409413
ProcLockWakeup, in case the canceled waiter was soft-blocking other
410414
waiters.
411415

412-
4. We can minimize excess rearrangement-trial work by being careful to scan
413-
the wait queue from the front when looking for soft edges. For example,
414-
if we have queue order A,B,C and C has deadlock conflicts with both A and B,
415-
we want to generate the "C before A" constraint first, rather than wasting
416-
time with "C before B", which won't move C far enough up. So we look for
417-
soft edges outgoing from C starting at the front of the wait queue.
416+
4. We can minimize excess rearrangement-trial work by being careful to
417+
scan the wait queue from the front when looking for soft edges. For
418+
example, if we have queue order A,B,C and C has deadlock conflicts with
419+
both A and B, we want to generate the "C before A" constraint first,
420+
rather than wasting time with "C before B", which won't move C far
421+
enough up. So we look for soft edges outgoing from C starting at the
422+
front of the wait queue.
418423

419424
5. The working data structures needed by the deadlock detection code can
420425
be limited to numbers of entries computed from MaxBackends. Therefore,
421-
we can allocate the worst-case space needed during backend startup.
422-
This seems a safer approach than trying to allocate workspace on the fly;
423-
we don't want to risk having the deadlock detector run out of memory,
424-
else we really have no guarantees at all that deadlock will be detected.
426+
we can allocate the worst-case space needed during backend startup. This
427+
seems a safer approach than trying to allocate workspace on the fly; we
428+
don't want to risk having the deadlock detector run out of memory, else
429+
we really have no guarantees at all that deadlock will be detected.
430+

‎src/backend/storage/lmgr/deadlock.c

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212
*
1313
*
1414
* IDENTIFICATION
15-
* $Header: /cvsroot/pgsql/src/backend/storage/lmgr/deadlock.c,v 1.11 2002/07/18 23:06:19 momjian Exp $
15+
* $Header: /cvsroot/pgsql/src/backend/storage/lmgr/deadlock.c,v 1.12 2002/07/19 00:17:40 momjian Exp $
1616
*
1717
* Interface:
1818
*
@@ -377,7 +377,7 @@ FindLockCycleRecurse(PGPROC *checkProc,
377377
{
378378
PGPROC *proc;
379379
LOCK *lock;
380-
HOLDER *holder;
380+
PROCLOCK *holder;
381381
SHM_QUEUE *lockHolders;
382382
LOCKMETHODTABLE *lockMethodTable;
383383
PROC_QUEUE *waitQueue;
@@ -427,8 +427,8 @@ FindLockCycleRecurse(PGPROC *checkProc,
427427
*/
428428
lockHolders = &(lock->lockHolders);
429429

430-
holder = (HOLDER *) SHMQueueNext(lockHolders, lockHolders,
431-
offsetof(HOLDER, lockLink));
430+
holder = (PROCLOCK *) SHMQueueNext(lockHolders, lockHolders,
431+
offsetof(PROCLOCK, lockLink));
432432

433433
while (holder)
434434
{
@@ -451,8 +451,8 @@ FindLockCycleRecurse(PGPROC *checkProc,
451451
}
452452
}
453453

454-
holder = (HOLDER *) SHMQueueNext(lockHolders, &holder->lockLink,
455-
offsetof(HOLDER, lockLink));
454+
holder = (PROCLOCK *) SHMQueueNext(lockHolders, &holder->lockLink,
455+
offsetof(PROCLOCK, lockLink));
456456
}
457457

458458
/*

0 commit comments

Comments
 (0)