1
src/backend/storage/lmgr/README
6
Postgres uses four types of interprocess locks:
8
* Spinlocks. These are intended for *very* short-term locks. If a lock
9
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
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
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.
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.
37
* SIReadLock predicate locks. See separate README-SSI file for details.
39
Acquisition of either a spinlock or a lightweight lock causes query
40
cancel and die() interrupts to be held off until all such locks are
41
released. No such restriction exists for regular locks, however. Also
42
note that we can accept query cancel and die() interrupts while waiting
43
for a regular lock, but we will not accept them while waiting for
44
spinlocks or LW locks. It is therefore not a good idea to use LW locks
45
when the wait time might exceed a few seconds.
47
The rest of this README file discusses the regular lock manager in detail.
53
Lock methods describe the overall locking behavior. Currently there are
54
two lock methods: DEFAULT and USER.
56
Lock modes describe the type of the lock (read/write or shared/exclusive).
57
In principle, each lock method can have its own set of lock modes with
58
different conflict rules, but currently DEFAULT and USER methods use
59
identical lock mode sets. See src/tools/backend/index.html and
60
src/include/storage/lock.h for more details. (Lock modes are also called
61
lock types in some places in the code and documentation.)
63
There are two fundamental lock structures in shared memory: the
64
per-lockable-object LOCK struct, and the per-lock-and-requestor PROCLOCK
65
struct. A LOCK object exists for each lockable object that currently has
66
locks held or requested on it. A PROCLOCK struct exists for each backend
67
that is holding or requesting lock(s) on each LOCK object.
69
In addition to these, each backend maintains an unshared LOCALLOCK structure
70
for each lockable object and lock mode that it is currently holding or
71
requesting. The shared lock structures only allow a single lock grant to
72
be made per lockable object/lock mode/backend. Internally to a backend,
73
however, the same lock may be requested and perhaps released multiple times
74
in a transaction, and it can also be held both transactionally and session-
75
wide. The internal request counts are held in LOCALLOCK so that the shared
76
data structures need not be accessed to alter them.
78
---------------------------------------------------------------------------
80
The lock manager's LOCK objects contain:
83
The key fields that are used for hashing locks in the shared memory
84
lock hash table. The contents of the tag essentially define an
85
individual lockable object. See include/storage/lock.h for details
86
about the supported types of lockable objects. This is declared as
87
a separate struct to ensure that we always zero out the correct number
88
of bytes. It is critical that any alignment-padding bytes the compiler
89
might insert in the struct be zeroed out, else the hash computation
90
will be random. (Currently, we are careful to define struct LOCKTAG
91
so that there are no padding bytes.)
94
This bitmask indicates what types of locks are currently held on the
95
given lockable object. It is used (against the lock table's conflict
96
table) to determine if a new lock request will conflict with existing
97
lock types held. Conflicts are determined by bitwise AND operations
98
between the grantMask and the conflict table entry for the requested
99
lock type. Bit i of grantMask is 1 if and only if granted[i] > 0.
102
This bitmask shows the types of locks being waited for. Bit i of waitMask
103
is 1 if and only if requested[i] > granted[i].
106
This is a shared memory queue of all the PROCLOCK structs associated with
107
the lock object. Note that both granted and waiting PROCLOCKs are in this
108
list (indeed, the same PROCLOCK might have some already-granted locks and
109
be waiting for more!).
112
This is a shared memory queue of all PGPROC structures corresponding to
113
backends that are waiting (sleeping) until another backend releases this
114
lock. The process structure holds the information needed to determine
115
if it should be woken up when the lock is released.
118
Keeps a count of how many times this lock has been attempted to be
119
acquired. The count includes attempts by processes which were put
120
to sleep due to conflicts. It also counts the same backend twice
121
if, for example, a backend process first acquires a read and then
122
acquires a write. (But multiple acquisitions of the same lock/lock mode
123
within a backend are not multiply counted here; they are recorded
124
only in the backend's LOCALLOCK structure.)
127
Keeps a count of how many locks of each type have been attempted. Only
128
elements 1 through MAX_LOCKMODES-1 are used as they correspond to the lock
129
type defined constants. Summing the values of requested[] should come out
133
Keeps count of how many times this lock has been successfully acquired.
134
This count does not include attempts that are waiting due to conflicts.
135
Otherwise the counting rules are the same as for nRequested.
138
Keeps count of how many locks of each type are currently held. Once again
139
only elements 1 through MAX_LOCKMODES-1 are used (0 is not). Also, like
140
requested[], summing the values of granted[] should total to the value
143
We should always have 0 <= nGranted <= nRequested, and
144
0 <= granted[i] <= requested[i] for each i. When all the request counts
145
go to zero, the LOCK object is no longer needed and can be freed.
147
---------------------------------------------------------------------------
149
The lock manager's PROCLOCK objects contain:
152
The key fields that are used for hashing entries in the shared memory
153
PROCLOCK hash table. This is declared as a separate struct to ensure that
154
we always zero out the correct number of bytes. It is critical that any
155
alignment-padding bytes the compiler might insert in the struct be zeroed
156
out, else the hash computation will be random. (Currently, we are careful
157
to define struct PROCLOCKTAG so that there are no padding bytes.)
160
Pointer to the shared LOCK object this PROCLOCK is for.
163
Pointer to the PGPROC of backend process that owns this PROCLOCK.
165
Note: it's OK to use pointers here because a PROCLOCK never outlives
166
either its lock or its proc. The tag is therefore unique for as long
167
as it needs to be, even though the same tag values might mean something
171
A bitmask for the lock modes successfully acquired by this PROCLOCK.
172
This should be a subset of the LOCK object's grantMask, and also a
173
subset of the PGPROC object's heldLocks mask (if the PGPROC is
174
currently waiting for another lock mode on this lock).
177
A bitmask for the lock modes due to be released during LockReleaseAll.
178
This must be a subset of the holdMask. Note that it is modified without
179
taking the partition LWLock, and therefore it is unsafe for any
180
backend except the one owning the PROCLOCK to examine/change it.
183
List link for shared memory queue of all the PROCLOCK objects for the
187
List link for shared memory queue of all the PROCLOCK objects for the
190
---------------------------------------------------------------------------
193
Lock Manager Internal Locking
194
-----------------------------
196
Before PostgreSQL 8.2, all of the shared-memory data structures used by
197
the lock manager were protected by a single LWLock, the LockMgrLock;
198
any operation involving these data structures had to exclusively lock
199
LockMgrLock. Not too surprisingly, this became a contention bottleneck.
200
To reduce contention, the lock manager's data structures have been split
201
into multiple "partitions", each protected by an independent LWLock.
202
Most operations only need to lock the single partition they are working in.
203
Here are the details:
205
* Each possible lock is assigned to one partition according to a hash of
206
its LOCKTAG value. The partition's LWLock is considered to protect all the
207
LOCK objects of that partition as well as their subsidiary PROCLOCKs.
209
* The shared-memory hash tables for LOCKs and PROCLOCKs are organized
210
so that different partitions use different hash chains, and thus there
211
is no conflict in working with objects in different partitions. This
212
is supported directly by dynahash.c's "partitioned table" mechanism
213
for the LOCK table: we need only ensure that the partition number is
214
taken from the low-order bits of the dynahash hash value for the LOCKTAG.
215
To make it work for PROCLOCKs, we have to ensure that a PROCLOCK's hash
216
value has the same low-order bits as its associated LOCK. This requires
217
a specialized hash function (see proclock_hash).
219
* Formerly, each PGPROC had a single list of PROCLOCKs belonging to it.
220
This has now been split into per-partition lists, so that access to a
221
particular PROCLOCK list can be protected by the associated partition's
222
LWLock. (This is not strictly necessary at the moment, because at this
223
writing a PGPROC's PROCLOCK list is only accessed by the owning backend
224
anyway. But it seems forward-looking to maintain a convention for how
225
other backends could access it. In any case LockReleaseAll needs to be
226
able to quickly determine which partition each LOCK belongs to, and
227
for the currently contemplated number of partitions, this way takes less
228
shared memory than explicitly storing a partition number in LOCK structs
231
* The other lock-related fields of a PGPROC are only interesting when
232
the PGPROC is waiting for a lock, so we consider that they are protected
233
by the partition LWLock of the awaited lock.
235
For normal lock acquisition and release, it is sufficient to lock the
236
partition containing the desired lock. Deadlock checking needs to touch
237
multiple partitions in general; for simplicity, we just make it lock all
238
the partitions in partition-number order. (To prevent LWLock deadlock,
239
we establish the rule that any backend needing to lock more than one
240
partition at once must lock them in partition-number order.) It's
241
possible that deadlock checking could be done without touching every
242
partition in typical cases, but since in a properly functioning system
243
deadlock checking should not occur often enough to be performance-critical,
244
trying to make this work does not seem a productive use of effort.
246
A backend's internal LOCALLOCK hash table is not partitioned. We do store
247
a copy of the locktag hash code in LOCALLOCK table entries, from which the
248
partition number can be computed, but this is a straight speed-for-space
249
tradeoff: we could instead recalculate the partition number from the LOCKTAG
253
The Deadlock Detection Algorithm
254
--------------------------------
256
Since we allow user transactions to request locks in any order, deadlock
257
is possible. We use a deadlock detection/breaking algorithm that is
258
fairly standard in essence, but there are many special considerations
259
needed to deal with Postgres' generalized locking model.
261
A key design consideration is that we want to make routine operations
262
(lock grant and release) run quickly when there is no deadlock, and
263
avoid the overhead of deadlock handling as much as possible. We do this
264
using an "optimistic waiting" approach: if a process cannot acquire the
265
lock it wants immediately, it goes to sleep without any deadlock check.
266
But it also sets a delay timer, with a delay of DeadlockTimeout
267
milliseconds (typically set to one second). If the delay expires before
268
the process is granted the lock it wants, it runs the deadlock
269
detection/breaking code. Normally this code will determine that there is
270
no deadlock condition, and then the process will go back to sleep and
271
wait quietly until it is granted the lock. But if a deadlock condition
272
does exist, it will be resolved, usually by aborting the detecting
273
process' transaction. In this way, we avoid deadlock handling overhead
274
whenever the wait time for a lock is less than DeadlockTimeout, while
275
not imposing an unreasonable delay of detection when there is an error.
277
Lock acquisition (routines LockAcquire and ProcSleep) follows these rules:
279
1. A lock request is granted immediately if it does not conflict with
280
any existing or waiting lock request, or if the process already holds an
281
instance of the same lock type (eg, there's no penalty to acquire a read
282
lock twice). Note that a process never conflicts with itself, eg one
283
can obtain read lock when one already holds exclusive lock.
285
2. Otherwise the process joins the lock's wait queue. Normally it will
286
be added to the end of the queue, but there is an exception: if the
287
process already holds locks on this same lockable object that conflict
288
with the request of any pending waiter, then the process will be
289
inserted in the wait queue just ahead of the first such waiter. (If we
290
did not make this check, the deadlock detection code would adjust the
291
queue order to resolve the conflict, but it's relatively cheap to make
292
the check in ProcSleep and avoid a deadlock timeout delay in this case.)
293
Note special case when inserting before the end of the queue: if the
294
process's request does not conflict with any existing lock nor any
295
waiting request before its insertion point, then go ahead and grant the
296
lock without waiting.
298
When a lock is released, the lock release routine (ProcLockWakeup) scans
299
the lock object's wait queue. Each waiter is awoken if (a) its request
300
does not conflict with already-granted locks, and (b) its request does
301
not conflict with the requests of prior un-wakable waiters. Rule (b)
302
ensures that conflicting requests are granted in order of arrival. There
303
are cases where a later waiter must be allowed to go in front of
304
conflicting earlier waiters to avoid deadlock, but it is not
305
ProcLockWakeup's responsibility to recognize these cases; instead, the
306
deadlock detection code will re-order the wait queue when necessary.
308
To perform deadlock checking, we use the standard method of viewing the
309
various processes as nodes in a directed graph (the waits-for graph or
310
WFG). There is a graph edge leading from process A to process B if A
311
waits for B, ie, A is waiting for some lock and B holds a conflicting
312
lock. There is a deadlock condition if and only if the WFG contains a
313
cycle. We detect cycles by searching outward along waits-for edges to
314
see if we return to our starting point. There are three possible
317
1. All outgoing paths terminate at a running process (which has no
320
2. A deadlock is detected by looping back to the start point. We
321
resolve such a deadlock by canceling the start point's lock request and
322
reporting an error in that transaction, which normally leads to
323
transaction abort and release of that transaction's held locks. Note
324
that it's sufficient to cancel one request to remove the cycle; we don't
325
need to kill all the transactions involved.
327
3. Some path(s) loop back to a node other than the start point. This
328
indicates a deadlock, but one that does not involve our starting
329
process. We ignore this condition on the grounds that resolving such a
330
deadlock is the responsibility of the processes involved --- killing our
331
start- point process would not resolve the deadlock. So, cases 1 and 3
332
both report "no deadlock".
334
Postgres' situation is a little more complex than the standard discussion
335
of deadlock detection, for two reasons:
337
1. A process can be waiting for more than one other process, since there
338
might be multiple PROCLOCKs of (non-conflicting) lock types that all
339
conflict with the waiter's request. This creates no real difficulty
340
however; we simply need to be prepared to trace more than one outgoing
343
2. If a process A is behind a process B in some lock's wait queue, and
344
their requested locks conflict, then we must say that A waits for B, since
345
ProcLockWakeup will never awaken A before B. This creates additional
346
edges in the WFG. We call these "soft" edges, as opposed to the "hard"
347
edges induced by locks already held. Note that if B already holds any
348
locks conflicting with A's request, then their relationship is a hard edge
351
A "soft" block, or wait-priority block, has the same potential for
352
inducing deadlock as a hard block. However, we may be able to resolve
353
a soft block without aborting the transactions involved: we can instead
354
rearrange the order of the wait queue. This rearrangement reverses the
355
direction of the soft edge between two processes with conflicting requests
356
whose queue order is reversed. If we can find a rearrangement that
357
eliminates a cycle without creating new ones, then we can avoid an abort.
358
Checking for such possible rearrangements is the trickiest part of the
361
The workhorse of the deadlock detector is a routine FindLockCycle() which
362
is given a starting point process (which must be a waiting process).
363
It recursively scans outward across waits-for edges as discussed above.
364
If it finds no cycle involving the start point, it returns "false".
365
(As discussed above, we can ignore cycles not involving the start point.)
366
When such a cycle is found, FindLockCycle() returns "true", and as it
367
unwinds it also builds a list of any "soft" edges involved in the cycle.
368
If the resulting list is empty then there is a hard deadlock and the
369
configuration cannot succeed. However, if the list is not empty, then
370
reversing any one of the listed edges through wait-queue rearrangement
371
will eliminate that cycle. Since such a reversal might create cycles
372
elsewhere, we may need to try every possibility. Therefore, we need to
373
be able to invoke FindLockCycle() on hypothetical configurations (wait
374
orders) as well as the current real order.
376
The easiest way to handle this seems to be to have a lookaside table that
377
shows the proposed new queue order for each wait queue that we are
378
considering rearranging. This table is checked by FindLockCycle, and it
379
believes the proposed queue order rather than the real order for each lock
380
that has an entry in the lookaside table.
382
We build a proposed new queue order by doing a "topological sort" of the
383
existing entries. Each soft edge that we are currently considering
384
reversing creates a property of the partial order that the topological sort
385
has to enforce. We must use a sort method that preserves the input
386
ordering as much as possible, so as not to gratuitously break arrival
387
order for processes not involved in a deadlock. (This is not true of the
388
tsort method shown in Knuth, for example, but it's easily done by a simple
389
doubly-nested-loop method that emits the first legal candidate at each
390
step. Fortunately, we don't need a highly efficient sort algorithm, since
391
the number of partial order constraints is not likely to be large.) Note
392
that failure of the topological sort tells us we have conflicting ordering
393
constraints, and therefore that the last-added soft edge reversal
394
conflicts with a prior edge reversal. We need to detect this case to
395
avoid an infinite loop in the case where no possible rearrangement will
396
work: otherwise, we might try a reversal, find that it still leads to
397
a cycle, then try to un-reverse the reversal while trying to get rid of
398
that cycle, etc etc. Topological sort failure tells us the un-reversal
399
is not a legitimate move in this context.
401
So, the basic step in our rearrangement method is to take a list of
402
soft edges in a cycle (as returned by FindLockCycle()) and successively
403
try the reversal of each one as a topological-sort constraint added to
404
whatever constraints we are already considering. We recursively search
405
through all such sets of constraints to see if any one eliminates all
406
the deadlock cycles at once. Although this might seem impossibly
407
inefficient, it shouldn't be a big problem in practice, because there
408
will normally be very few, and not very large, deadlock cycles --- if
409
any at all. So the combinatorial inefficiency isn't going to hurt us.
410
Besides, it's better to spend some time to guarantee that we've checked
411
all possible escape routes than to abort a transaction when we didn't
414
Each edge reversal constraint can be viewed as requesting that the waiting
415
process A be moved to before the blocking process B in the wait queue they
416
are both in. This action will reverse the desired soft edge, as well as
417
any other soft edges between A and other processes it is advanced over.
418
No other edges will be affected (note this is actually a constraint on our
419
topological sort method to not re-order the queue more than necessary.)
420
Therefore, we can be sure we have not created any new deadlock cycles if
421
neither FindLockCycle(A) nor FindLockCycle(B) discovers any cycle. Given
422
the above-defined behavior of FindLockCycle, each of these searches is
423
necessary as well as sufficient, since FindLockCycle starting at the
424
original start point will not complain about cycles that include A or B
425
but not the original start point.
427
In short then, a proposed rearrangement of the wait queue(s) is determined
428
by one or more broken soft edges A->B, fully specified by the output of
429
topological sorts of each wait queue involved, and then tested by invoking
430
FindLockCycle() starting at the original start point as well as each of
431
the mentioned processes (A's and B's). If none of the tests detect a
432
cycle, then we have a valid configuration and can implement it by
433
reordering the wait queues per the sort outputs (and then applying
434
ProcLockWakeup on each reordered queue, in case a waiter has become wakable).
435
If any test detects a soft cycle, we can try to resolve it by adding each
436
soft link in that cycle, in turn, to the proposed rearrangement list.
437
This is repeated recursively until we either find a workable rearrangement
438
or determine that none exists. In the latter case, the outer level
439
resolves the deadlock by aborting the original start-point transaction.
441
The particular order in which rearrangements are tried depends on the
442
order FindLockCycle() happens to scan in, so if there are multiple
443
workable rearrangements of the wait queues, then it is unspecified which
444
one will be chosen. What's more important is that we guarantee to try
445
every queue rearrangement that could lead to success. (For example,
446
if we have A before B before C and the needed order constraints are
447
C before A and B before C, we would first discover that A before C
448
doesn't work and try the rearrangement C before A before B. This would
449
eventually lead to the discovery of the additional constraint B before C.)
456
1. It is easily proven that no deadlock will be missed due to our
457
asynchronous invocation of deadlock checking. A deadlock cycle in the WFG
458
is formed when the last edge in the cycle is added; therefore the last
459
process in the cycle to wait (the one from which that edge is outgoing) is
460
certain to detect and resolve the cycle when it later runs CheckDeadLock.
461
This holds even if that edge addition created multiple cycles; the process
462
may indeed abort without ever noticing those additional cycles, but we
463
don't particularly care. The only other possible creation of deadlocks is
464
during deadlock resolution's rearrangement of wait queues, and we already
465
saw that that algorithm will prove that it creates no new deadlocks before
466
it attempts to actually execute any rearrangement.
468
2. It is not certain that a deadlock will be resolved by aborting the
469
last-to-wait process. If earlier waiters in the cycle have not yet run
470
CheckDeadLock, then the first one to do so will be the victim.
472
3. No live (wakable) process can be missed by ProcLockWakeup, since it
473
examines every member of the wait queue (this was not true in the 7.0
474
implementation, BTW). Therefore, if ProcLockWakeup is always invoked
475
after a lock is released or a wait queue is rearranged, there can be no
476
failure to wake a wakable process. One should also note that
477
LockWaitCancel (abort a waiter due to outside factors) must run
478
ProcLockWakeup, in case the canceled waiter was soft-blocking other
481
4. We can minimize excess rearrangement-trial work by being careful to
482
scan the wait queue from the front when looking for soft edges. For
483
example, if we have queue order A,B,C and C has deadlock conflicts with
484
both A and B, we want to generate the "C before A" constraint first,
485
rather than wasting time with "C before B", which won't move C far
486
enough up. So we look for soft edges outgoing from C starting at the
487
front of the wait queue.
489
5. The working data structures needed by the deadlock detection code can
490
be limited to numbers of entries computed from MaxBackends. Therefore,
491
we can allocate the worst-case space needed during backend startup. This
492
seems a safer approach than trying to allocate workspace on the fly; we
493
don't want to risk having the deadlock detector run out of memory, else
494
we really have no guarantees at all that deadlock will be detected.
496
6. We abuse the deadlock detector to implement autovacuum cancellation.
497
When we run the detector and we find that there's an autovacuum worker
498
involved in the waits-for graph, we store a pointer to its PGPROC, and
499
return a special return code (unless a hard deadlock has been detected).
500
The caller can then send a cancellation signal. This implements the
501
principle that autovacuum has a low locking priority (eg it must not block
507
User locks are handled totally on the application side as long term
508
cooperative locks which may extend beyond the normal transaction boundaries.
509
Their purpose is to indicate to an application that someone is `working'
510
on an item. So it is possible to put an user lock on a tuple's oid,
511
retrieve the tuple, work on it for an hour and then update it and remove
512
the lock. While the lock is active other clients can still read and write
513
the tuple but they can be aware that it has been locked at the application
516
User locks and normal locks are completely orthogonal and they don't
517
interfere with each other.
519
There are two types of user locks: session level and transaction level.
520
Session level user locks are not released at transaction end. They must
521
be released explicitly by the application --- but they are released
522
automatically when a backend terminates. On the other hand, transaction
523
level user locks are released automatically at the end of the transaction
524
as like as other normal locks.
526
Locking during Hot Standby
527
--------------------------
529
The Startup process is the only backend that can make changes during
530
recovery, all other backends are read only. As a result the Startup
531
process does not acquire locks on relations or objects except when the lock
532
level is AccessExclusiveLock.
534
Regular backends are only allowed to take locks on relations or objects
535
at RowExclusiveLock or lower. This ensures that they do not conflict with
536
each other or with the Startup process, unless AccessExclusiveLocks are
537
requested by one of the backends.
539
Deadlocks involving AccessExclusiveLocks are not possible, so we need
540
not be concerned that a user initiated deadlock can prevent recovery from
543
AccessExclusiveLocks on the primary or master node generate WAL records
544
that are then applied by the Startup process. Locks are released at end
545
of transaction just as they are in normal processing. These locks are
546
held by the Startup process, acting as a proxy for the backends that
547
originally acquired these locks. Again, these locks cannot conflict with
548
one another, so the Startup process cannot deadlock itself either.
added
removed
src/backend/storage/lmgr/README
