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 main methods for recording locks in shared memory. The primary
64 mechanism uses two main structures: the per-lockable-object LOCK struct, and
65 the per-lock-and-requestor PROCLOCK struct. A LOCK object exists for each
66 lockable object that currently has locks held or requested on it. A PROCLOCK
67 struct exists for each backend that is holding or requesting lock(s) on each
70 There is also a special "fast path" mechanism which backends may use to
71 record a limited number of locks with very specific characteristics: they must
72 use the DEFAULT lockmethod; they must represent a lock on a database relation
73 (not a shared relation), they must be a "weak" lock which is unlikely to
74 conflict (AccessShareLock, RowShareLock, or RowExclusiveLock); and the system
75 must be able to quickly verify that no conflicting locks could possibly be
76 present. See "Fast Path Locking", below, for more details.
78 Each backend also maintains an unshared LOCALLOCK structure for each lockable
79 object and lock mode that it is currently holding or requesting. The shared
80 lock structures only allow a single lock grant to be made per lockable
81 object/lock mode/backend. Internally to a backend, however, the same lock may
82 be requested and perhaps released multiple times in a transaction, and it can
83 also be held both transactionally and session-wide. The internal request
84 counts are held in LOCALLOCK so that the shared data structures need not be
85 accessed to alter them.
87 ---------------------------------------------------------------------------
89 The lock manager's LOCK objects contain:
92 The key fields that are used for hashing locks in the shared memory
93 lock hash table. The contents of the tag essentially define an
94 individual lockable object. See include/storage/lock.h for details
95 about the supported types of lockable objects. This is declared as
96 a separate struct to ensure that we always zero out the correct number
97 of bytes. It is critical that any alignment-padding bytes the compiler
98 might insert in the struct be zeroed out, else the hash computation
99 will be random. (Currently, we are careful to define struct LOCKTAG
100 so that there are no padding bytes.)
103 This bitmask indicates what types of locks are currently held on the
104 given lockable object. It is used (against the lock table's conflict
105 table) to determine if a new lock request will conflict with existing
106 lock types held. Conflicts are determined by bitwise AND operations
107 between the grantMask and the conflict table entry for the requested
108 lock type. Bit i of grantMask is 1 if and only if granted[i] > 0.
111 This bitmask shows the types of locks being waited for. Bit i of waitMask
112 is 1 if and only if requested[i] > granted[i].
115 This is a shared memory queue of all the PROCLOCK structs associated with
116 the lock object. Note that both granted and waiting PROCLOCKs are in this
117 list (indeed, the same PROCLOCK might have some already-granted locks and
118 be waiting for more!).
121 This is a shared memory queue of all PGPROC structures corresponding to
122 backends that are waiting (sleeping) until another backend releases this
123 lock. The process structure holds the information needed to determine
124 if it should be woken up when the lock is released.
127 Keeps a count of how many times this lock has been attempted to be
128 acquired. The count includes attempts by processes which were put
129 to sleep due to conflicts. It also counts the same backend twice
130 if, for example, a backend process first acquires a read and then
131 acquires a write. (But multiple acquisitions of the same lock/lock mode
132 within a backend are not multiply counted here; they are recorded
133 only in the backend's LOCALLOCK structure.)
136 Keeps a count of how many locks of each type have been attempted. Only
137 elements 1 through MAX_LOCKMODES-1 are used as they correspond to the lock
138 type defined constants. Summing the values of requested[] should come out
142 Keeps count of how many times this lock has been successfully acquired.
143 This count does not include attempts that are waiting due to conflicts.
144 Otherwise the counting rules are the same as for nRequested.
147 Keeps count of how many locks of each type are currently held. Once again
148 only elements 1 through MAX_LOCKMODES-1 are used (0 is not). Also, like
149 requested[], summing the values of granted[] should total to the value
152 We should always have 0 <= nGranted <= nRequested, and
153 0 <= granted[i] <= requested[i] for each i. When all the request counts
154 go to zero, the LOCK object is no longer needed and can be freed.
156 ---------------------------------------------------------------------------
158 The lock manager's PROCLOCK objects contain:
161 The key fields that are used for hashing entries in the shared memory
162 PROCLOCK hash table. This is declared as a separate struct to ensure that
163 we always zero out the correct number of bytes. It is critical that any
164 alignment-padding bytes the compiler might insert in the struct be zeroed
165 out, else the hash computation will be random. (Currently, we are careful
166 to define struct PROCLOCKTAG so that there are no padding bytes.)
169 Pointer to the shared LOCK object this PROCLOCK is for.
172 Pointer to the PGPROC of backend process that owns this PROCLOCK.
174 Note: it's OK to use pointers here because a PROCLOCK never outlives
175 either its lock or its proc. The tag is therefore unique for as long
176 as it needs to be, even though the same tag values might mean something
180 A bitmask for the lock modes successfully acquired by this PROCLOCK.
181 This should be a subset of the LOCK object's grantMask, and also a
182 subset of the PGPROC object's heldLocks mask (if the PGPROC is
183 currently waiting for another lock mode on this lock).
186 A bitmask for the lock modes due to be released during LockReleaseAll.
187 This must be a subset of the holdMask. Note that it is modified without
188 taking the partition LWLock, and therefore it is unsafe for any
189 backend except the one owning the PROCLOCK to examine/change it.
192 List link for shared memory queue of all the PROCLOCK objects for the
196 List link for shared memory queue of all the PROCLOCK objects for the
199 ---------------------------------------------------------------------------
202 Lock Manager Internal Locking
203 -----------------------------
205 Before PostgreSQL 8.2, all of the shared-memory data structures used by
206 the lock manager were protected by a single LWLock, the LockMgrLock;
207 any operation involving these data structures had to exclusively lock
208 LockMgrLock. Not too surprisingly, this became a contention bottleneck.
209 To reduce contention, the lock manager's data structures have been split
210 into multiple "partitions", each protected by an independent LWLock.
211 Most operations only need to lock the single partition they are working in.
212 Here are the details:
214 * Each possible lock is assigned to one partition according to a hash of
215 its LOCKTAG value. The partition's LWLock is considered to protect all the
216 LOCK objects of that partition as well as their subsidiary PROCLOCKs.
218 * The shared-memory hash tables for LOCKs and PROCLOCKs are organized
219 so that different partitions use different hash chains, and thus there
220 is no conflict in working with objects in different partitions. This
221 is supported directly by dynahash.c's "partitioned table" mechanism
222 for the LOCK table: we need only ensure that the partition number is
223 taken from the low-order bits of the dynahash hash value for the LOCKTAG.
224 To make it work for PROCLOCKs, we have to ensure that a PROCLOCK's hash
225 value has the same low-order bits as its associated LOCK. This requires
226 a specialized hash function (see proclock_hash).
228 * Formerly, each PGPROC had a single list of PROCLOCKs belonging to it.
229 This has now been split into per-partition lists, so that access to a
230 particular PROCLOCK list can be protected by the associated partition's
231 LWLock. (This is not strictly necessary at the moment, because at this
232 writing a PGPROC's PROCLOCK list is only accessed by the owning backend
233 anyway. But it seems forward-looking to maintain a convention for how
234 other backends could access it. In any case LockReleaseAll needs to be
235 able to quickly determine which partition each LOCK belongs to, and
236 for the currently contemplated number of partitions, this way takes less
237 shared memory than explicitly storing a partition number in LOCK structs
240 * The other lock-related fields of a PGPROC are only interesting when
241 the PGPROC is waiting for a lock, so we consider that they are protected
242 by the partition LWLock of the awaited lock.
244 For normal lock acquisition and release, it is sufficient to lock the
245 partition containing the desired lock. Deadlock checking needs to touch
246 multiple partitions in general; for simplicity, we just make it lock all
247 the partitions in partition-number order. (To prevent LWLock deadlock,
248 we establish the rule that any backend needing to lock more than one
249 partition at once must lock them in partition-number order.) It's
250 possible that deadlock checking could be done without touching every
251 partition in typical cases, but since in a properly functioning system
252 deadlock checking should not occur often enough to be performance-critical,
253 trying to make this work does not seem a productive use of effort.
255 A backend's internal LOCALLOCK hash table is not partitioned. We do store
256 a copy of the locktag hash code in LOCALLOCK table entries, from which the
257 partition number can be computed, but this is a straight speed-for-space
258 tradeoff: we could instead recalculate the partition number from the LOCKTAG
265 Fast path locking is a special purpose mechanism designed to reduce the
266 overhead of taking and releasing certain types of locks which are taken
267 and released very frequently but rarely conflict. Currently, this includes
268 two categories of locks:
270 (1) Weak relation locks. SELECT, INSERT, UPDATE, and DELETE must acquire a
271 lock on every relation they operate on, as well as various system catalogs
272 that can be used internally. Many DML operations can proceed in parallel
273 against the same table at the same time; only DDL operations such as
274 CLUSTER, ALTER TABLE, or DROP -- or explicit user action such as LOCK TABLE
275 -- will create lock conflicts with the "weak" locks (AccessShareLock,
276 RowShareLock, RowExclusiveLock) acquired by DML operations.
278 (2) VXID locks. Every transaction takes a lock on its own virtual
279 transaction ID. Currently, the only operations that wait for these locks
280 are CREATE INDEX CONCURRENTLY and Hot Standby (in the case of a conflict),
281 so most VXID locks are taken and released by the owner without anyone else
284 The primary locking mechanism does not cope well with this workload. Even
285 though the lock manager locks are partitioned, the locktag for any given
286 relation still falls in one, and only one, partition. Thus, if many short
287 queries are accessing the same relation, the lock manager partition lock for
288 that partition becomes a contention bottleneck. This effect is measurable
289 even on 2-core servers, and becomes very pronounced as core count increases.
291 To alleviate this bottleneck, beginning in PostgreSQL 9.2, each backend is
292 permitted to record a limited number of locks on unshared relations in an
293 array within its PGPROC structure, rather than using the primary lock table.
294 This mechanism can only be used when the locker can verify that no conflicting
295 locks can possibly exist.
297 A key point of this algorithm is that it must be possible to verify the
298 absence of possibly conflicting locks without fighting over a shared LWLock or
299 spinlock. Otherwise, this effort would simply move the contention bottleneck
300 from one place to another. We accomplish this using an array of 1024 integer
301 counters, which are in effect a 1024-way partitioning of the lock space. Each
302 counter records the number of "strong" locks (that is, ShareLock,
303 ShareRowExclusiveLock, ExclusiveLock, and AccessExclusiveLock) on unshared
304 relations that fall into that partition. When this counter is non-zero, the
305 fast path mechanism may not be used for relation locks in that partition. A
306 strong locker bumps the counter and then scans each per-backend array for
307 matching fast-path locks; any which are found must be transferred to the
308 primary lock table before attempting to acquire the lock, to ensure proper
309 lock conflict and deadlock detection.
311 On an SMP system, we must guarantee proper memory synchronization. Here we
312 rely on the fact that LWLock acquisition acts as a memory sequence point: if
313 A performs a store, A and B both acquire an LWLock in either order, and B
314 then performs a load on the same memory location, it is guaranteed to see
315 A's store. In this case, each backend's fast-path lock queue is protected
316 by an LWLock. A backend wishing to acquire a fast-path lock grabs this
317 LWLock before examining FastPathStrongRelationLocks to check for the presence of
318 a conflicting strong lock. And the backend attempting to acquire a strong
319 lock, because it must transfer any matching weak locks taken via the fast-path
320 mechanism to the shared lock table, will acquire every LWLock protecting
321 a backend fast-path queue in turn. So, if we examine FastPathStrongRelationLocks
322 and see a zero, then either the value is truly zero, or if it is a stale value,
323 the strong locker has yet to acquire the per-backend LWLock we now hold (or,
324 indeed, even the first per-backend LWLock) and will notice any weak lock we
327 Fast-path VXID locks do not use the FastPathStrongRelationLocks table. The
328 first lock taken on a VXID is always the ExclusiveLock taken by its owner. Any
329 subsequent lockers are share lockers waiting for the VXID to terminate.
330 Indeed, the only reason VXID locks use the lock manager at all (rather than
331 waiting for the VXID to terminate via some other method) is for deadlock
332 detection. Thus, the initial VXID lock can *always* be taken via the fast
333 path without checking for conflicts. Any subsequent locker must check
334 whether the lock has been transferred to the main lock table, and if not,
335 do so. The backend owning the VXID must be careful to clean up any entry
336 made in the main lock table at end of transaction.
339 The Deadlock Detection Algorithm
340 --------------------------------
342 Since we allow user transactions to request locks in any order, deadlock
343 is possible. We use a deadlock detection/breaking algorithm that is
344 fairly standard in essence, but there are many special considerations
345 needed to deal with Postgres' generalized locking model.
347 A key design consideration is that we want to make routine operations
348 (lock grant and release) run quickly when there is no deadlock, and
349 avoid the overhead of deadlock handling as much as possible. We do this
350 using an "optimistic waiting" approach: if a process cannot acquire the
351 lock it wants immediately, it goes to sleep without any deadlock check.
352 But it also sets a delay timer, with a delay of DeadlockTimeout
353 milliseconds (typically set to one second). If the delay expires before
354 the process is granted the lock it wants, it runs the deadlock
355 detection/breaking code. Normally this code will determine that there is
356 no deadlock condition, and then the process will go back to sleep and
357 wait quietly until it is granted the lock. But if a deadlock condition
358 does exist, it will be resolved, usually by aborting the detecting
359 process' transaction. In this way, we avoid deadlock handling overhead
360 whenever the wait time for a lock is less than DeadlockTimeout, while
361 not imposing an unreasonable delay of detection when there is an error.
363 Lock acquisition (routines LockAcquire and ProcSleep) follows these rules:
365 1. A lock request is granted immediately if it does not conflict with
366 any existing or waiting lock request, or if the process already holds an
367 instance of the same lock type (eg, there's no penalty to acquire a read
368 lock twice). Note that a process never conflicts with itself, eg one
369 can obtain read lock when one already holds exclusive lock.
371 2. Otherwise the process joins the lock's wait queue. Normally it will
372 be added to the end of the queue, but there is an exception: if the
373 process already holds locks on this same lockable object that conflict
374 with the request of any pending waiter, then the process will be
375 inserted in the wait queue just ahead of the first such waiter. (If we
376 did not make this check, the deadlock detection code would adjust the
377 queue order to resolve the conflict, but it's relatively cheap to make
378 the check in ProcSleep and avoid a deadlock timeout delay in this case.)
379 Note special case when inserting before the end of the queue: if the
380 process's request does not conflict with any existing lock nor any
381 waiting request before its insertion point, then go ahead and grant the
382 lock without waiting.
384 When a lock is released, the lock release routine (ProcLockWakeup) scans
385 the lock object's wait queue. Each waiter is awoken if (a) its request
386 does not conflict with already-granted locks, and (b) its request does
387 not conflict with the requests of prior un-wakable waiters. Rule (b)
388 ensures that conflicting requests are granted in order of arrival. There
389 are cases where a later waiter must be allowed to go in front of
390 conflicting earlier waiters to avoid deadlock, but it is not
391 ProcLockWakeup's responsibility to recognize these cases; instead, the
392 deadlock detection code will re-order the wait queue when necessary.
394 To perform deadlock checking, we use the standard method of viewing the
395 various processes as nodes in a directed graph (the waits-for graph or
396 WFG). There is a graph edge leading from process A to process B if A
397 waits for B, ie, A is waiting for some lock and B holds a conflicting
398 lock. There is a deadlock condition if and only if the WFG contains a
399 cycle. We detect cycles by searching outward along waits-for edges to
400 see if we return to our starting point. There are three possible
403 1. All outgoing paths terminate at a running process (which has no
406 2. A deadlock is detected by looping back to the start point. We
407 resolve such a deadlock by canceling the start point's lock request and
408 reporting an error in that transaction, which normally leads to
409 transaction abort and release of that transaction's held locks. Note
410 that it's sufficient to cancel one request to remove the cycle; we don't
411 need to kill all the transactions involved.
413 3. Some path(s) loop back to a node other than the start point. This
414 indicates a deadlock, but one that does not involve our starting
415 process. We ignore this condition on the grounds that resolving such a
416 deadlock is the responsibility of the processes involved --- killing our
417 start- point process would not resolve the deadlock. So, cases 1 and 3
418 both report "no deadlock".
420 Postgres' situation is a little more complex than the standard discussion
421 of deadlock detection, for two reasons:
423 1. A process can be waiting for more than one other process, since there
424 might be multiple PROCLOCKs of (non-conflicting) lock types that all
425 conflict with the waiter's request. This creates no real difficulty
426 however; we simply need to be prepared to trace more than one outgoing
429 2. If a process A is behind a process B in some lock's wait queue, and
430 their requested locks conflict, then we must say that A waits for B, since
431 ProcLockWakeup will never awaken A before B. This creates additional
432 edges in the WFG. We call these "soft" edges, as opposed to the "hard"
433 edges induced by locks already held. Note that if B already holds any
434 locks conflicting with A's request, then their relationship is a hard edge
437 A "soft" block, or wait-priority block, has the same potential for
438 inducing deadlock as a hard block. However, we may be able to resolve
439 a soft block without aborting the transactions involved: we can instead
440 rearrange the order of the wait queue. This rearrangement reverses the
441 direction of the soft edge between two processes with conflicting requests
442 whose queue order is reversed. If we can find a rearrangement that
443 eliminates a cycle without creating new ones, then we can avoid an abort.
444 Checking for such possible rearrangements is the trickiest part of the
447 The workhorse of the deadlock detector is a routine FindLockCycle() which
448 is given a starting point process (which must be a waiting process).
449 It recursively scans outward across waits-for edges as discussed above.
450 If it finds no cycle involving the start point, it returns "false".
451 (As discussed above, we can ignore cycles not involving the start point.)
452 When such a cycle is found, FindLockCycle() returns "true", and as it
453 unwinds it also builds a list of any "soft" edges involved in the cycle.
454 If the resulting list is empty then there is a hard deadlock and the
455 configuration cannot succeed. However, if the list is not empty, then
456 reversing any one of the listed edges through wait-queue rearrangement
457 will eliminate that cycle. Since such a reversal might create cycles
458 elsewhere, we may need to try every possibility. Therefore, we need to
459 be able to invoke FindLockCycle() on hypothetical configurations (wait
460 orders) as well as the current real order.
462 The easiest way to handle this seems to be to have a lookaside table that
463 shows the proposed new queue order for each wait queue that we are
464 considering rearranging. This table is checked by FindLockCycle, and it
465 believes the proposed queue order rather than the real order for each lock
466 that has an entry in the lookaside table.
468 We build a proposed new queue order by doing a "topological sort" of the
469 existing entries. Each soft edge that we are currently considering
470 reversing creates a property of the partial order that the topological sort
471 has to enforce. We must use a sort method that preserves the input
472 ordering as much as possible, so as not to gratuitously break arrival
473 order for processes not involved in a deadlock. (This is not true of the
474 tsort method shown in Knuth, for example, but it's easily done by a simple
475 doubly-nested-loop method that emits the first legal candidate at each
476 step. Fortunately, we don't need a highly efficient sort algorithm, since
477 the number of partial order constraints is not likely to be large.) Note
478 that failure of the topological sort tells us we have conflicting ordering
479 constraints, and therefore that the last-added soft edge reversal
480 conflicts with a prior edge reversal. We need to detect this case to
481 avoid an infinite loop in the case where no possible rearrangement will
482 work: otherwise, we might try a reversal, find that it still leads to
483 a cycle, then try to un-reverse the reversal while trying to get rid of
484 that cycle, etc etc. Topological sort failure tells us the un-reversal
485 is not a legitimate move in this context.
487 So, the basic step in our rearrangement method is to take a list of
488 soft edges in a cycle (as returned by FindLockCycle()) and successively
489 try the reversal of each one as a topological-sort constraint added to
490 whatever constraints we are already considering. We recursively search
491 through all such sets of constraints to see if any one eliminates all
492 the deadlock cycles at once. Although this might seem impossibly
493 inefficient, it shouldn't be a big problem in practice, because there
494 will normally be very few, and not very large, deadlock cycles --- if
495 any at all. So the combinatorial inefficiency isn't going to hurt us.
496 Besides, it's better to spend some time to guarantee that we've checked
497 all possible escape routes than to abort a transaction when we didn't
500 Each edge reversal constraint can be viewed as requesting that the waiting
501 process A be moved to before the blocking process B in the wait queue they
502 are both in. This action will reverse the desired soft edge, as well as
503 any other soft edges between A and other processes it is advanced over.
504 No other edges will be affected (note this is actually a constraint on our
505 topological sort method to not re-order the queue more than necessary.)
506 Therefore, we can be sure we have not created any new deadlock cycles if
507 neither FindLockCycle(A) nor FindLockCycle(B) discovers any cycle. Given
508 the above-defined behavior of FindLockCycle, each of these searches is
509 necessary as well as sufficient, since FindLockCycle starting at the
510 original start point will not complain about cycles that include A or B
511 but not the original start point.
513 In short then, a proposed rearrangement of the wait queue(s) is determined
514 by one or more broken soft edges A->B, fully specified by the output of
515 topological sorts of each wait queue involved, and then tested by invoking
516 FindLockCycle() starting at the original start point as well as each of
517 the mentioned processes (A's and B's). If none of the tests detect a
518 cycle, then we have a valid configuration and can implement it by
519 reordering the wait queues per the sort outputs (and then applying
520 ProcLockWakeup on each reordered queue, in case a waiter has become wakable).
521 If any test detects a soft cycle, we can try to resolve it by adding each
522 soft link in that cycle, in turn, to the proposed rearrangement list.
523 This is repeated recursively until we either find a workable rearrangement
524 or determine that none exists. In the latter case, the outer level
525 resolves the deadlock by aborting the original start-point transaction.
527 The particular order in which rearrangements are tried depends on the
528 order FindLockCycle() happens to scan in, so if there are multiple
529 workable rearrangements of the wait queues, then it is unspecified which
530 one will be chosen. What's more important is that we guarantee to try
531 every queue rearrangement that could lead to success. (For example,
532 if we have A before B before C and the needed order constraints are
533 C before A and B before C, we would first discover that A before C
534 doesn't work and try the rearrangement C before A before B. This would
535 eventually lead to the discovery of the additional constraint B before C.)
542 1. It is easily proven that no deadlock will be missed due to our
543 asynchronous invocation of deadlock checking. A deadlock cycle in the WFG
544 is formed when the last edge in the cycle is added; therefore the last
545 process in the cycle to wait (the one from which that edge is outgoing) is
546 certain to detect and resolve the cycle when it later runs CheckDeadLock.
547 This holds even if that edge addition created multiple cycles; the process
548 may indeed abort without ever noticing those additional cycles, but we
549 don't particularly care. The only other possible creation of deadlocks is
550 during deadlock resolution's rearrangement of wait queues, and we already
551 saw that that algorithm will prove that it creates no new deadlocks before
552 it attempts to actually execute any rearrangement.
554 2. It is not certain that a deadlock will be resolved by aborting the
555 last-to-wait process. If earlier waiters in the cycle have not yet run
556 CheckDeadLock, then the first one to do so will be the victim.
558 3. No live (wakable) process can be missed by ProcLockWakeup, since it
559 examines every member of the wait queue (this was not true in the 7.0
560 implementation, BTW). Therefore, if ProcLockWakeup is always invoked
561 after a lock is released or a wait queue is rearranged, there can be no
562 failure to wake a wakable process. One should also note that
563 LockErrorCleanup (abort a waiter due to outside factors) must run
564 ProcLockWakeup, in case the canceled waiter was soft-blocking other
567 4. We can minimize excess rearrangement-trial work by being careful to
568 scan the wait queue from the front when looking for soft edges. For
569 example, if we have queue order A,B,C and C has deadlock conflicts with
570 both A and B, we want to generate the "C before A" constraint first,
571 rather than wasting time with "C before B", which won't move C far
572 enough up. So we look for soft edges outgoing from C starting at the
573 front of the wait queue.
575 5. The working data structures needed by the deadlock detection code can
576 be limited to numbers of entries computed from MaxBackends. Therefore,
577 we can allocate the worst-case space needed during backend startup. This
578 seems a safer approach than trying to allocate workspace on the fly; we
579 don't want to risk having the deadlock detector run out of memory, else
580 we really have no guarantees at all that deadlock will be detected.
582 6. We abuse the deadlock detector to implement autovacuum cancellation.
583 When we run the detector and we find that there's an autovacuum worker
584 involved in the waits-for graph, we store a pointer to its PGPROC, and
585 return a special return code (unless a hard deadlock has been detected).
586 The caller can then send a cancellation signal. This implements the
587 principle that autovacuum has a low locking priority (eg it must not block
590 User Locks (Advisory Locks)
591 ---------------------------
593 User locks are handled totally on the application side as long term
594 cooperative locks which may extend beyond the normal transaction boundaries.
595 Their purpose is to indicate to an application that someone is `working'
596 on an item. So it is possible to put an user lock on a tuple's oid,
597 retrieve the tuple, work on it for an hour and then update it and remove
598 the lock. While the lock is active other clients can still read and write
599 the tuple but they can be aware that it has been locked at the application
602 User locks and normal locks are completely orthogonal and they don't
603 interfere with each other.
605 User locks can be acquired either at session level or transaction level.
606 A session-level lock request is not automatically released at transaction
607 end, but must be explicitly released by the application. (However, any
608 remaining locks are always released at session end.) Transaction-level
609 user lock requests behave the same as normal lock requests, in that they
610 are released at transaction end and do not need explicit unlocking.
612 Locking during Hot Standby
613 --------------------------
615 The Startup process is the only backend that can make changes during
616 recovery, all other backends are read only. As a result the Startup
617 process does not acquire locks on relations or objects except when the lock
618 level is AccessExclusiveLock.
620 Regular backends are only allowed to take locks on relations or objects
621 at RowExclusiveLock or lower. This ensures that they do not conflict with
622 each other or with the Startup process, unless AccessExclusiveLocks are
623 requested by one of the backends.
625 Deadlocks involving AccessExclusiveLocks are not possible, so we need
626 not be concerned that a user initiated deadlock can prevent recovery from
629 AccessExclusiveLocks on the primary or master node generate WAL records
630 that are then applied by the Startup process. Locks are released at end
631 of transaction just as they are in normal processing. These locks are
632 held by the Startup process, acting as a proxy for the backends that
633 originally acquired these locks. Again, these locks cannot conflict with
634 one another, so the Startup process cannot deadlock itself either.