TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * deadlock.c
4 : * POSTGRES deadlock detection code
5 : *
6 : * See src/backend/storage/lmgr/README for a description of the deadlock
7 : * detection and resolution algorithms.
8 : *
9 : *
10 : * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
11 : * Portions Copyright (c) 1994, Regents of the University of California
12 : *
13 : *
14 : * IDENTIFICATION
15 : * src/backend/storage/lmgr/deadlock.c
16 : *
17 : * Interface:
18 : *
19 : * DeadLockCheck()
20 : * DeadLockReport()
21 : * RememberSimpleDeadLock()
22 : * InitDeadLockChecking()
23 : *
24 : *-------------------------------------------------------------------------
25 : */
26 : #include "postgres.h"
27 :
28 : #include "miscadmin.h"
29 : #include "pg_trace.h"
30 : #include "pgstat.h"
31 : #include "storage/lmgr.h"
32 : #include "storage/proc.h"
33 : #include "utils/memutils.h"
34 :
35 :
36 : /*
37 : * One edge in the waits-for graph.
38 : *
39 : * waiter and blocker may or may not be members of a lock group, but if either
40 : * is, it will be the leader rather than any other member of the lock group.
41 : * The group leaders act as representatives of the whole group even though
42 : * those particular processes need not be waiting at all. There will be at
43 : * least one member of the waiter's lock group on the wait queue for the given
44 : * lock, maybe more.
45 : */
46 : typedef struct
47 : {
48 : PGPROC *waiter; /* the leader of the waiting lock group */
49 : PGPROC *blocker; /* the leader of the group it is waiting for */
50 : LOCK *lock; /* the lock being waited for */
51 : int pred; /* workspace for TopoSort */
52 : int link; /* workspace for TopoSort */
53 : } EDGE;
54 :
55 : /* One potential reordering of a lock's wait queue */
56 : typedef struct
57 : {
58 : LOCK *lock; /* the lock whose wait queue is described */
59 : PGPROC **procs; /* array of PGPROC *'s in new wait order */
60 : int nProcs;
61 : } WAIT_ORDER;
62 :
63 : /*
64 : * Information saved about each edge in a detected deadlock cycle. This
65 : * is used to print a diagnostic message upon failure.
66 : *
67 : * Note: because we want to examine this info after releasing the lock
68 : * manager's partition locks, we can't just store LOCK and PGPROC pointers;
69 : * we must extract out all the info we want to be able to print.
70 : */
71 : typedef struct
72 : {
73 : LOCKTAG locktag; /* ID of awaited lock object */
74 : LOCKMODE lockmode; /* type of lock we're waiting for */
75 : int pid; /* PID of blocked backend */
76 : } DEADLOCK_INFO;
77 :
78 :
79 : static bool DeadLockCheckRecurse(PGPROC *proc);
80 : static int TestConfiguration(PGPROC *startProc);
81 : static bool FindLockCycle(PGPROC *checkProc,
82 : EDGE *softEdges, int *nSoftEdges);
83 : static bool FindLockCycleRecurse(PGPROC *checkProc, int depth,
84 : EDGE *softEdges, int *nSoftEdges);
85 : static bool FindLockCycleRecurseMember(PGPROC *checkProc,
86 : PGPROC *checkProcLeader,
87 : int depth, EDGE *softEdges, int *nSoftEdges);
88 : static bool ExpandConstraints(EDGE *constraints, int nConstraints);
89 : static bool TopoSort(LOCK *lock, EDGE *constraints, int nConstraints,
90 : PGPROC **ordering);
91 :
92 : #ifdef DEBUG_DEADLOCK
93 : static void PrintLockQueue(LOCK *lock, const char *info);
94 : #endif
95 :
96 :
97 : /*
98 : * Working space for the deadlock detector
99 : */
100 :
101 : /* Workspace for FindLockCycle */
102 : static PGPROC **visitedProcs; /* Array of visited procs */
103 : static int nVisitedProcs;
104 :
105 : /* Workspace for TopoSort */
106 : static PGPROC **topoProcs; /* Array of not-yet-output procs */
107 : static int *beforeConstraints; /* Counts of remaining before-constraints */
108 : static int *afterConstraints; /* List head for after-constraints */
109 :
110 : /* Output area for ExpandConstraints */
111 : static WAIT_ORDER *waitOrders; /* Array of proposed queue rearrangements */
112 : static int nWaitOrders;
113 : static PGPROC **waitOrderProcs; /* Space for waitOrders queue contents */
114 :
115 : /* Current list of constraints being considered */
116 : static EDGE *curConstraints;
117 : static int nCurConstraints;
118 : static int maxCurConstraints;
119 :
120 : /* Storage space for results from FindLockCycle */
121 : static EDGE *possibleConstraints;
122 : static int nPossibleConstraints;
123 : static int maxPossibleConstraints;
124 : static DEADLOCK_INFO *deadlockDetails;
125 : static int nDeadlockDetails;
126 :
127 : /* PGPROC pointer of any blocking autovacuum worker found */
128 : static PGPROC *blocking_autovacuum_proc = NULL;
129 :
130 :
131 : /*
132 : * InitDeadLockChecking -- initialize deadlock checker during backend startup
133 : *
134 : * This does per-backend initialization of the deadlock checker; primarily,
135 : * allocation of working memory for DeadLockCheck. We do this per-backend
136 : * since there's no percentage in making the kernel do copy-on-write
137 : * inheritance of workspace from the postmaster. We want to allocate the
138 : * space at startup because (a) the deadlock checker might be invoked when
139 : * there's no free memory left, and (b) the checker is normally run inside a
140 : * signal handler, which is a very dangerous place to invoke palloc from.
141 : */
142 : void
143 CBC 11510 : InitDeadLockChecking(void)
144 : {
145 : MemoryContext oldcxt;
146 :
147 : /* Make sure allocations are permanent */
148 11510 : oldcxt = MemoryContextSwitchTo(TopMemoryContext);
149 :
150 : /*
151 : * FindLockCycle needs at most MaxBackends entries in visitedProcs[] and
152 : * deadlockDetails[].
153 : */
154 11510 : visitedProcs = (PGPROC **) palloc(MaxBackends * sizeof(PGPROC *));
155 11510 : deadlockDetails = (DEADLOCK_INFO *) palloc(MaxBackends * sizeof(DEADLOCK_INFO));
156 :
157 : /*
158 : * TopoSort needs to consider at most MaxBackends wait-queue entries, and
159 : * it needn't run concurrently with FindLockCycle.
160 : */
161 11510 : topoProcs = visitedProcs; /* re-use this space */
162 11510 : beforeConstraints = (int *) palloc(MaxBackends * sizeof(int));
163 11510 : afterConstraints = (int *) palloc(MaxBackends * sizeof(int));
164 :
165 : /*
166 : * We need to consider rearranging at most MaxBackends/2 wait queues
167 : * (since it takes at least two waiters in a queue to create a soft edge),
168 : * and the expanded form of the wait queues can't involve more than
169 : * MaxBackends total waiters.
170 : */
171 11510 : waitOrders = (WAIT_ORDER *)
172 11510 : palloc((MaxBackends / 2) * sizeof(WAIT_ORDER));
173 11510 : waitOrderProcs = (PGPROC **) palloc(MaxBackends * sizeof(PGPROC *));
174 :
175 : /*
176 : * Allow at most MaxBackends distinct constraints in a configuration. (Is
177 : * this enough? In practice it seems it should be, but I don't quite see
178 : * how to prove it. If we run out, we might fail to find a workable wait
179 : * queue rearrangement even though one exists.) NOTE that this number
180 : * limits the maximum recursion depth of DeadLockCheckRecurse. Making it
181 : * really big might potentially allow a stack-overflow problem.
182 : */
183 11510 : maxCurConstraints = MaxBackends;
184 11510 : curConstraints = (EDGE *) palloc(maxCurConstraints * sizeof(EDGE));
185 :
186 : /*
187 : * Allow up to 3*MaxBackends constraints to be saved without having to
188 : * re-run TestConfiguration. (This is probably more than enough, but we
189 : * can survive if we run low on space by doing excess runs of
190 : * TestConfiguration to re-compute constraint lists each time needed.) The
191 : * last MaxBackends entries in possibleConstraints[] are reserved as
192 : * output workspace for FindLockCycle.
193 : */
194 11510 : maxPossibleConstraints = MaxBackends * 4;
195 11510 : possibleConstraints =
196 11510 : (EDGE *) palloc(maxPossibleConstraints * sizeof(EDGE));
197 :
198 11510 : MemoryContextSwitchTo(oldcxt);
199 11510 : }
200 :
201 : /*
202 : * DeadLockCheck -- Checks for deadlocks for a given process
203 : *
204 : * This code looks for deadlocks involving the given process. If any
205 : * are found, it tries to rearrange lock wait queues to resolve the
206 : * deadlock. If resolution is impossible, return DS_HARD_DEADLOCK ---
207 : * the caller is then expected to abort the given proc's transaction.
208 : *
209 : * Caller must already have locked all partitions of the lock tables.
210 : *
211 : * On failure, deadlock details are recorded in deadlockDetails[] for
212 : * subsequent printing by DeadLockReport(). That activity is separate
213 : * because (a) we don't want to do it while holding all those LWLocks,
214 : * and (b) we are typically invoked inside a signal handler.
215 : */
216 : DeadLockState
217 26 : DeadLockCheck(PGPROC *proc)
218 : {
219 ECB : /* Initialize to "no constraints" */
220 GIC 26 : nCurConstraints = 0;
221 26 : nPossibleConstraints = 0;
222 CBC 26 : nWaitOrders = 0;
223 :
224 : /* Initialize to not blocked by an autovacuum worker */
225 26 : blocking_autovacuum_proc = NULL;
226 :
227 : /* Search for deadlocks and possible fixes */
228 GIC 26 : if (DeadLockCheckRecurse(proc))
229 : {
230 : /*
231 : * Call FindLockCycle one more time, to record the correct
232 : * deadlockDetails[] for the basic state with no rearrangements.
233 : */
234 : int nSoftEdges;
235 ECB :
236 : TRACE_POSTGRESQL_DEADLOCK_FOUND();
237 EUB :
238 GIC 4 : nWaitOrders = 0;
239 CBC 4 : if (!FindLockCycle(proc, possibleConstraints, &nSoftEdges))
240 UIC 0 : elog(FATAL, "deadlock seems to have disappeared");
241 :
242 GIC 4 : return DS_HARD_DEADLOCK; /* cannot find a non-deadlocked state */
243 ECB : }
244 :
245 : /* Apply any needed rearrangements of wait queues */
246 GNC 25 : for (int i = 0; i < nWaitOrders; i++)
247 ECB : {
248 CBC 3 : LOCK *lock = waitOrders[i].lock;
249 GIC 3 : PGPROC **procs = waitOrders[i].procs;
250 CBC 3 : int nProcs = waitOrders[i].nProcs;
251 GNC 3 : dclist_head *waitQueue = &lock->waitProcs;
252 :
253 3 : Assert(nProcs == dclist_count(waitQueue));
254 :
255 : #ifdef DEBUG_DEADLOCK
256 : PrintLockQueue(lock, "DeadLockCheck:");
257 ECB : #endif
258 :
259 : /* Reset the queue and re-add procs in the desired order */
260 GNC 3 : dclist_init(waitQueue);
261 12 : for (int j = 0; j < nProcs; j++)
262 9 : dclist_push_tail(waitQueue, &procs[j]->links);
263 ECB :
264 : #ifdef DEBUG_DEADLOCK
265 : PrintLockQueue(lock, "rearranged to:");
266 : #endif
267 :
268 : /* See if any waiters for the lock can be woken up now */
269 CBC 3 : ProcLockWakeup(GetLocksMethodTable(lock), lock);
270 EUB : }
271 :
272 ECB : /* Return code tells caller if we had to escape a deadlock or not */
273 GIC 22 : if (nWaitOrders > 0)
274 3 : return DS_SOFT_DEADLOCK;
275 19 : else if (blocking_autovacuum_proc != NULL)
276 UIC 0 : return DS_BLOCKED_BY_AUTOVACUUM;
277 : else
278 GIC 19 : return DS_NO_DEADLOCK;
279 : }
280 :
281 EUB : /*
282 : * Return the PGPROC of the autovacuum that's blocking a process.
283 : *
284 : * We reset the saved pointer as soon as we pass it back.
285 : */
286 : PGPROC *
287 UIC 0 : GetBlockingAutoVacuumPgproc(void)
288 EUB : {
289 : PGPROC *ptr;
290 :
291 UIC 0 : ptr = blocking_autovacuum_proc;
292 0 : blocking_autovacuum_proc = NULL;
293 :
294 0 : return ptr;
295 : }
296 :
297 : /*
298 : * DeadLockCheckRecurse -- recursively search for valid orderings
299 : *
300 : * curConstraints[] holds the current set of constraints being considered
301 : * by an outer level of recursion. Add to this each possible solution
302 : * constraint for any cycle detected at this level.
303 ECB : *
304 : * Returns true if no solution exists. Returns false if a deadlock-free
305 : * state is attainable, in which case waitOrders[] shows the required
306 : * rearrangements of lock wait queues (if any).
307 : */
308 : static bool
309 GIC 29 : DeadLockCheckRecurse(PGPROC *proc)
310 ECB : {
311 : int nEdges;
312 : int oldPossibleConstraints;
313 : bool savedList;
314 : int i;
315 :
316 GBC 29 : nEdges = TestConfiguration(proc);
317 CBC 29 : if (nEdges < 0)
318 4 : return true; /* hard deadlock --- no solution */
319 GIC 25 : if (nEdges == 0)
320 22 : return false; /* good configuration found */
321 CBC 3 : if (nCurConstraints >= maxCurConstraints)
322 LBC 0 : return true; /* out of room for active constraints? */
323 GIC 3 : oldPossibleConstraints = nPossibleConstraints;
324 3 : if (nPossibleConstraints + nEdges + MaxBackends <= maxPossibleConstraints)
325 : {
326 : /* We can save the edge list in possibleConstraints[] */
327 GBC 3 : nPossibleConstraints += nEdges;
328 GIC 3 : savedList = true;
329 : }
330 : else
331 : {
332 : /* Not room; will need to regenerate the edges on-the-fly */
333 LBC 0 : savedList = false;
334 : }
335 ECB :
336 : /*
337 : * Try each available soft edge as an addition to the configuration.
338 EUB : */
339 GBC 3 : for (i = 0; i < nEdges; i++)
340 : {
341 CBC 3 : if (!savedList && i > 0)
342 ECB : {
343 : /* Regenerate the list of possible added constraints */
344 LBC 0 : if (nEdges != TestConfiguration(proc))
345 0 : elog(FATAL, "inconsistent results during deadlock check");
346 : }
347 GBC 3 : curConstraints[nCurConstraints] =
348 GIC 3 : possibleConstraints[oldPossibleConstraints + i];
349 GBC 3 : nCurConstraints++;
350 3 : if (!DeadLockCheckRecurse(proc))
351 GIC 3 : return false; /* found a valid solution! */
352 : /* give up on that added constraint, try again */
353 UIC 0 : nCurConstraints--;
354 : }
355 0 : nPossibleConstraints = oldPossibleConstraints;
356 0 : return true; /* no solution found */
357 : }
358 :
359 :
360 : /*--------------------
361 : * Test a configuration (current set of constraints) for validity.
362 : *
363 : * Returns:
364 : * 0: the configuration is good (no deadlocks)
365 : * -1: the configuration has a hard deadlock or is not self-consistent
366 : * >0: the configuration has one or more soft deadlocks
367 : *
368 : * In the soft-deadlock case, one of the soft cycles is chosen arbitrarily
369 ECB : * and a list of its soft edges is returned beginning at
370 : * possibleConstraints+nPossibleConstraints. The return value is the
371 : * number of soft edges.
372 : *--------------------
373 : */
374 : static int
375 GIC 29 : TestConfiguration(PGPROC *startProc)
376 : {
377 29 : int softFound = 0;
378 29 : EDGE *softEdges = possibleConstraints + nPossibleConstraints;
379 ECB : int nSoftEdges;
380 EUB : int i;
381 :
382 : /*
383 : * Make sure we have room for FindLockCycle's output.
384 : */
385 GIC 29 : if (nPossibleConstraints + MaxBackends > maxPossibleConstraints)
386 LBC 0 : return -1;
387 EUB :
388 : /*
389 : * Expand current constraint set into wait orderings. Fail if the
390 : * constraint set is not self-consistent.
391 : */
392 GIC 29 : if (!ExpandConstraints(curConstraints, nCurConstraints))
393 UIC 0 : return -1;
394 ECB :
395 : /*
396 : * Check for cycles involving startProc or any of the procs mentioned in
397 : * constraints. We check startProc last because if it has a soft cycle
398 EUB : * still to be dealt with, we want to deal with that first.
399 : */
400 GBC 32 : for (i = 0; i < nCurConstraints; i++)
401 : {
402 CBC 3 : if (FindLockCycle(curConstraints[i].waiter, softEdges, &nSoftEdges))
403 : {
404 UBC 0 : if (nSoftEdges == 0)
405 0 : return -1; /* hard deadlock detected */
406 0 : softFound = nSoftEdges;
407 : }
408 GIC 3 : if (FindLockCycle(curConstraints[i].blocker, softEdges, &nSoftEdges))
409 ECB : {
410 UIC 0 : if (nSoftEdges == 0)
411 LBC 0 : return -1; /* hard deadlock detected */
412 0 : softFound = nSoftEdges;
413 ECB : }
414 : }
415 CBC 29 : if (FindLockCycle(startProc, softEdges, &nSoftEdges))
416 : {
417 GIC 7 : if (nSoftEdges == 0)
418 4 : return -1; /* hard deadlock detected */
419 3 : softFound = nSoftEdges;
420 : }
421 25 : return softFound;
422 : }
423 :
424 :
425 : /*
426 : * FindLockCycle -- basic check for deadlock cycles
427 : *
428 : * Scan outward from the given proc to see if there is a cycle in the
429 : * waits-for graph that includes this proc. Return true if a cycle
430 : * is found, else false. If a cycle is found, we return a list of
431 : * the "soft edges", if any, included in the cycle. These edges could
432 : * potentially be eliminated by rearranging wait queues. We also fill
433 : * deadlockDetails[] with information about the detected cycle; this info
434 : * is not used by the deadlock algorithm itself, only to print a useful
435 : * message after failing.
436 : *
437 ECB : * Since we need to be able to check hypothetical configurations that would
438 : * exist after wait queue rearrangement, the routine pays attention to the
439 : * table of hypothetical queue orders in waitOrders[]. These orders will
440 : * be believed in preference to the actual ordering seen in the locktable.
441 : */
442 : static bool
443 CBC 39 : FindLockCycle(PGPROC *checkProc,
444 ECB : EDGE *softEdges, /* output argument */
445 : int *nSoftEdges) /* output argument */
446 : {
447 GIC 39 : nVisitedProcs = 0;
448 CBC 39 : nDeadlockDetails = 0;
449 GIC 39 : *nSoftEdges = 0;
450 39 : return FindLockCycleRecurse(checkProc, 0, softEdges, nSoftEdges);
451 : }
452 :
453 : static bool
454 119 : FindLockCycleRecurse(PGPROC *checkProc,
455 : int depth,
456 : EDGE *softEdges, /* output argument */
457 : int *nSoftEdges) /* output argument */
458 : {
459 : int i;
460 ECB : dlist_iter iter;
461 :
462 : /*
463 : * If this process is a lock group member, check the leader instead. (Note
464 : * that we might be the leader, in which case this is a no-op.)
465 : */
466 CBC 119 : if (checkProc->lockGroupLeader != NULL)
467 GIC 25 : checkProc = checkProc->lockGroupLeader;
468 ECB :
469 : /*
470 : * Have we already seen this proc?
471 : */
472 GIC 259 : for (i = 0; i < nVisitedProcs; i++)
473 : {
474 157 : if (visitedProcs[i] == checkProc)
475 : {
476 : /* If we return to starting point, we have a deadlock cycle */
477 CBC 17 : if (i == 0)
478 ECB : {
479 : /*
480 : * record total length of cycle --- outer levels will now fill
481 : * deadlockDetails[]
482 : */
483 GIC 11 : Assert(depth <= MaxBackends);
484 11 : nDeadlockDetails = depth;
485 :
486 11 : return true;
487 ECB : }
488 :
489 : /*
490 : * Otherwise, we have a cycle but it does not include the start
491 : * point, so say "no deadlock".
492 : */
493 GIC 6 : return false;
494 : }
495 : }
496 : /* Mark proc as seen */
497 102 : Assert(nVisitedProcs < MaxBackends);
498 CBC 102 : visitedProcs[nVisitedProcs++] = checkProc;
499 ECB :
500 : /*
501 : * If the process is waiting, there is an outgoing waits-for edge to each
502 : * process that blocks it.
503 : */
504 GIC 171 : if (checkProc->links.next != NULL && checkProc->waitLock != NULL &&
505 69 : FindLockCycleRecurseMember(checkProc, checkProc, depth, softEdges,
506 : nSoftEdges))
507 37 : return true;
508 :
509 : /*
510 ECB : * If the process is not waiting, there could still be outgoing waits-for
511 : * edges if it is part of a lock group, because other members of the lock
512 : * group might be waiting even though this process is not. (Given lock
513 : * groups {A1, A2} and {B1, B2}, if A1 waits for B1 and B2 waits for A2,
514 : * that is a deadlock even neither of B1 and A2 are waiting for anything.)
515 : */
516 CBC 109 : dlist_foreach(iter, &checkProc->lockGroupMembers)
517 ECB : {
518 : PGPROC *memberProc;
519 :
520 CBC 48 : memberProc = dlist_container(PGPROC, lockGroupLink, iter.cur);
521 :
522 GIC 48 : if (memberProc->links.next != NULL && memberProc->waitLock != NULL &&
523 CBC 21 : memberProc != checkProc &&
524 GIC 21 : FindLockCycleRecurseMember(memberProc, checkProc, depth, softEdges,
525 : nSoftEdges))
526 4 : return true;
527 ECB : }
528 :
529 GIC 61 : return false;
530 : }
531 :
532 : static bool
533 90 : FindLockCycleRecurseMember(PGPROC *checkProc,
534 ECB : PGPROC *checkProcLeader,
535 : int depth,
536 : EDGE *softEdges, /* output argument */
537 : int *nSoftEdges) /* output argument */
538 : {
539 : PGPROC *proc;
540 GIC 90 : LOCK *lock = checkProc->waitLock;
541 : dlist_iter proclock_iter;
542 : LockMethod lockMethodTable;
543 : int conflictMask;
544 ECB : int i;
545 : int numLockModes,
546 EUB : lm;
547 :
548 ECB : /*
549 : * The relation extension or page lock can never participate in actual
550 : * deadlock cycle. See Asserts in LockAcquireExtended. So, there is no
551 : * advantage in checking wait edges from them.
552 : */
553 GIC 90 : if (LOCK_LOCKTAG(*lock) == LOCKTAG_RELATION_EXTEND ||
554 90 : (LOCK_LOCKTAG(*lock) == LOCKTAG_PAGE))
555 UIC 0 : return false;
556 ECB :
557 GIC 90 : lockMethodTable = GetLocksMethodTable(lock);
558 CBC 90 : numLockModes = lockMethodTable->numLockModes;
559 GIC 90 : conflictMask = lockMethodTable->conflictTab[checkProc->waitLockMode];
560 :
561 ECB : /*
562 : * Scan for procs that already hold conflicting locks. These are "hard"
563 : * edges in the waits-for graph.
564 : */
565 GNC 267 : dlist_foreach(proclock_iter, &lock->procLocks)
566 : {
567 213 : PROCLOCK *proclock = dlist_container(PROCLOCK, lockLink, proclock_iter.cur);
568 : PGPROC *leader;
569 ECB :
570 GIC 213 : proc = proclock->tag.myProc;
571 213 : leader = proc->lockGroupLeader == NULL ? proc : proc->lockGroupLeader;
572 :
573 ECB : /* A proc never blocks itself or any other lock group member */
574 GIC 213 : if (leader != checkProcLeader)
575 ECB : {
576 CBC 1075 : for (lm = 1; lm <= numLockModes; lm++)
577 ECB : {
578 GIC 1002 : if ((proclock->holdMask & LOCKBIT_ON(lm)) &&
579 ECB : (conflictMask & LOCKBIT_ON(lm)))
580 : {
581 : /* This proc hard-blocks checkProc */
582 GIC 64 : if (FindLockCycleRecurse(proc, depth + 1,
583 : softEdges, nSoftEdges))
584 : {
585 : /* fill deadlockDetails[] */
586 36 : DEADLOCK_INFO *info = &deadlockDetails[depth];
587 :
588 36 : info->locktag = lock->tag;
589 36 : info->lockmode = checkProc->waitLockMode;
590 36 : info->pid = checkProc->pid;
591 :
592 36 : return true;
593 : }
594 :
595 : /*
596 : * No deadlock here, but see if this proc is an autovacuum
597 : * that is directly hard-blocking our own proc. If so,
598 : * report it so that the caller can send a cancel signal
599 : * to it, if appropriate. If there's more than one such
600 : * proc, it's indeterminate which one will be reported.
601 : *
602 : * We don't touch autovacuums that are indirectly blocking
603 : * us; it's up to the direct blockee to take action. This
604 ECB : * rule simplifies understanding the behavior and ensures
605 : * that an autovacuum won't be canceled with less than
606 EUB : * deadlock_timeout grace period.
607 : *
608 : * Note we read statusFlags without any locking. This is
609 ECB : * OK only for checking the PROC_IS_AUTOVACUUM flag,
610 : * because that flag is set at process start and never
611 : * reset. There is logic elsewhere to avoid canceling an
612 : * autovacuum that is working to prevent XID wraparound
613 : * problems (which needs to read a different statusFlags
614 : * bit), but we don't do that here to avoid grabbing
615 : * ProcArrayLock.
616 : */
617 GIC 28 : if (checkProc == MyProc &&
618 18 : proc->statusFlags & PROC_IS_AUTOVACUUM)
619 UIC 0 : blocking_autovacuum_proc = proc;
620 :
621 : /* We're done looking at this proclock */
622 GIC 28 : break;
623 : }
624 ECB : }
625 : }
626 : }
627 :
628 : /*
629 : * Scan for procs that are ahead of this one in the lock's wait queue.
630 : * Those that have conflicting requests soft-block this one. This must be
631 : * done after the hard-block search, since if another proc both hard- and
632 : * soft-blocks this one, we want to call it a hard edge.
633 : *
634 : * If there is a proposed re-ordering of the lock's wait order, use that
635 : * rather than the current wait order.
636 : */
637 CBC 63 : for (i = 0; i < nWaitOrders; i++)
638 ECB : {
639 GIC 27 : if (waitOrders[i].lock == lock)
640 18 : break;
641 : }
642 :
643 54 : if (i < nWaitOrders)
644 : {
645 : /* Use the given hypothetical wait queue order */
646 18 : PGPROC **procs = waitOrders[i].procs;
647 GNC 18 : int queue_size = waitOrders[i].nProcs;
648 ECB :
649 GIC 23 : for (i = 0; i < queue_size; i++)
650 : {
651 ECB : PGPROC *leader;
652 :
653 GIC 23 : proc = procs[i];
654 CBC 23 : leader = proc->lockGroupLeader == NULL ? proc :
655 : proc->lockGroupLeader;
656 :
657 : /*
658 EUB : * TopoSort will always return an ordering with group members
659 : * adjacent to each other in the wait queue (see comments
660 : * therein). So, as soon as we reach a process in the same lock
661 : * group as checkProc, we know we've found all the conflicts that
662 : * precede any member of the lock group lead by checkProcLeader.
663 : */
664 GIC 23 : if (leader == checkProcLeader)
665 18 : break;
666 :
667 EUB : /* Is there a conflict with this guy's request? */
668 GBC 5 : if ((LOCKBIT_ON(proc->waitLockMode) & conflictMask) != 0)
669 EUB : {
670 : /* This proc soft-blocks checkProc */
671 GBC 5 : if (FindLockCycleRecurse(proc, depth + 1,
672 EUB : softEdges, nSoftEdges))
673 : {
674 : /* fill deadlockDetails[] */
675 UIC 0 : DEADLOCK_INFO *info = &deadlockDetails[depth];
676 :
677 0 : info->locktag = lock->tag;
678 0 : info->lockmode = checkProc->waitLockMode;
679 LBC 0 : info->pid = checkProc->pid;
680 :
681 : /*
682 : * Add this edge to the list of soft edges in the cycle
683 : */
684 0 : Assert(*nSoftEdges < MaxBackends);
685 UIC 0 : softEdges[*nSoftEdges].waiter = checkProcLeader;
686 0 : softEdges[*nSoftEdges].blocker = leader;
687 0 : softEdges[*nSoftEdges].lock = lock;
688 0 : (*nSoftEdges)++;
689 0 : return true;
690 : }
691 : }
692 : }
693 ECB : }
694 : else
695 : {
696 GIC 36 : PGPROC *lastGroupMember = NULL;
697 : dlist_iter proc_iter;
698 : dclist_head *waitQueue;
699 ECB :
700 : /* Use the true lock wait queue order */
701 GNC 36 : waitQueue = &lock->waitProcs;
702 :
703 ECB : /*
704 : * Find the last member of the lock group that is present in the wait
705 : * queue. Anything after this is not a soft lock conflict. If group
706 : * locking is not in use, then we know immediately which process we're
707 : * looking for, but otherwise we've got to search the wait queue to
708 : * find the last process actually present.
709 : */
710 GIC 36 : if (checkProc->lockGroupLeader == NULL)
711 27 : lastGroupMember = checkProc;
712 ECB : else
713 : {
714 GNC 32 : dclist_foreach(proc_iter, waitQueue)
715 : {
716 23 : proc = dlist_container(PGPROC, links, proc_iter.cur);
717 :
718 CBC 23 : if (proc->lockGroupLeader == checkProcLeader)
719 GIC 13 : lastGroupMember = proc;
720 : }
721 CBC 9 : Assert(lastGroupMember != NULL);
722 ECB : }
723 :
724 : /*
725 : * OK, now rescan (or scan) the queue to identify the soft conflicts.
726 : */
727 GNC 47 : dclist_foreach(proc_iter, waitQueue)
728 : {
729 : PGPROC *leader;
730 :
731 47 : proc = dlist_container(PGPROC, links, proc_iter.cur);
732 :
733 CBC 47 : leader = proc->lockGroupLeader == NULL ? proc :
734 : proc->lockGroupLeader;
735 ECB :
736 : /* Done when we reach the target proc */
737 CBC 47 : if (proc == lastGroupMember)
738 GIC 31 : break;
739 :
740 : /* Is there a conflict with this guy's request? */
741 16 : if ((LOCKBIT_ON(proc->waitLockMode) & conflictMask) != 0 &&
742 ECB : leader != checkProcLeader)
743 : {
744 : /* This proc soft-blocks checkProc */
745 CBC 11 : if (FindLockCycleRecurse(proc, depth + 1,
746 ECB : softEdges, nSoftEdges))
747 : {
748 : /* fill deadlockDetails[] */
749 GIC 5 : DEADLOCK_INFO *info = &deadlockDetails[depth];
750 :
751 5 : info->locktag = lock->tag;
752 5 : info->lockmode = checkProc->waitLockMode;
753 5 : info->pid = checkProc->pid;
754 :
755 : /*
756 ECB : * Add this edge to the list of soft edges in the cycle
757 : */
758 GIC 5 : Assert(*nSoftEdges < MaxBackends);
759 5 : softEdges[*nSoftEdges].waiter = checkProcLeader;
760 5 : softEdges[*nSoftEdges].blocker = leader;
761 5 : softEdges[*nSoftEdges].lock = lock;
762 5 : (*nSoftEdges)++;
763 5 : return true;
764 : }
765 : }
766 : }
767 : }
768 :
769 : /*
770 ECB : * No conflict detected here.
771 : */
772 GIC 49 : return false;
773 ECB : }
774 :
775 :
776 : /*
777 : * ExpandConstraints -- expand a list of constraints into a set of
778 : * specific new orderings for affected wait queues
779 : *
780 : * Input is a list of soft edges to be reversed. The output is a list
781 : * of nWaitOrders WAIT_ORDER structs in waitOrders[], with PGPROC array
782 : * workspace in waitOrderProcs[].
783 : *
784 : * Returns true if able to build an ordering that satisfies all the
785 : * constraints, false if not (there are contradictory constraints).
786 : */
787 : static bool
788 GIC 29 : ExpandConstraints(EDGE *constraints,
789 ECB : int nConstraints)
790 : {
791 GBC 29 : int nWaitOrderProcs = 0;
792 EUB : int i,
793 : j;
794 ECB :
795 GBC 29 : nWaitOrders = 0;
796 :
797 ECB : /*
798 : * Scan constraint list backwards. This is because the last-added
799 : * constraint is the only one that could fail, and so we want to test it
800 : * for inconsistency first.
801 : */
802 GIC 32 : for (i = nConstraints; --i >= 0;)
803 : {
804 3 : LOCK *lock = constraints[i].lock;
805 :
806 : /* Did we already make a list for this lock? */
807 CBC 3 : for (j = nWaitOrders; --j >= 0;)
808 ECB : {
809 UBC 0 : if (waitOrders[j].lock == lock)
810 LBC 0 : break;
811 : }
812 CBC 3 : if (j >= 0)
813 UIC 0 : continue;
814 : /* No, so allocate a new list */
815 GIC 3 : waitOrders[nWaitOrders].lock = lock;
816 3 : waitOrders[nWaitOrders].procs = waitOrderProcs + nWaitOrderProcs;
817 GNC 3 : waitOrders[nWaitOrders].nProcs = dclist_count(&lock->waitProcs);
818 3 : nWaitOrderProcs += dclist_count(&lock->waitProcs);
819 GIC 3 : Assert(nWaitOrderProcs <= MaxBackends);
820 :
821 : /*
822 : * Do the topo sort. TopoSort need not examine constraints after this
823 : * one, since they must be for different locks.
824 : */
825 3 : if (!TopoSort(lock, constraints, i + 1,
826 3 : waitOrders[nWaitOrders].procs))
827 UIC 0 : return false;
828 GIC 3 : nWaitOrders++;
829 : }
830 29 : return true;
831 : }
832 :
833 :
834 : /*
835 : * TopoSort -- topological sort of a wait queue
836 : *
837 : * Generate a re-ordering of a lock's wait queue that satisfies given
838 : * constraints about certain procs preceding others. (Each such constraint
839 : * is a fact of a partial ordering.) Minimize rearrangement of the queue
840 : * not needed to achieve the partial ordering.
841 : *
842 ECB : * This is a lot simpler and slower than, for example, the topological sort
843 : * algorithm shown in Knuth's Volume 1. However, Knuth's method doesn't
844 : * try to minimize the damage to the existing order. In practice we are
845 : * not likely to be working with more than a few constraints, so the apparent
846 : * slowness of the algorithm won't really matter.
847 : *
848 : * The initial queue ordering is taken directly from the lock's wait queue.
849 : * The output is an array of PGPROC pointers, of length equal to the lock's
850 : * wait queue length (the caller is responsible for providing this space).
851 : * The partial order is specified by an array of EDGE structs. Each EDGE
852 : * is one that we need to reverse, therefore the "waiter" must appear before
853 : * the "blocker" in the output array. The EDGE array may well contain
854 : * edges associated with other locks; these should be ignored.
855 : *
856 : * Returns true if able to build an ordering that satisfies all the
857 : * constraints, false if not (there are contradictory constraints).
858 : */
859 : static bool
860 CBC 3 : TopoSort(LOCK *lock,
861 : EDGE *constraints,
862 ECB : int nConstraints,
863 : PGPROC **ordering) /* output argument */
864 : {
865 GNC 3 : dclist_head *waitQueue = &lock->waitProcs;
866 3 : int queue_size = dclist_count(waitQueue);
867 : PGPROC *proc;
868 : int i,
869 : j,
870 : jj,
871 : k,
872 : kk,
873 : last;
874 : dlist_iter proc_iter;
875 :
876 : /* First, fill topoProcs[] array with the procs in their current order */
877 3 : i = 0;
878 12 : dclist_foreach(proc_iter, waitQueue)
879 : {
880 9 : proc = dlist_container(PGPROC, links, proc_iter.cur);
881 9 : topoProcs[i++] = proc;
882 : }
883 3 : Assert(i == queue_size);
884 :
885 : /*
886 : * Scan the constraints, and for each proc in the array, generate a count
887 : * of the number of constraints that say it must be before something else,
888 : * plus a list of the constraints that say it must be after something
889 ECB : * else. The count for the j'th proc is stored in beforeConstraints[j],
890 : * and the head of its list in afterConstraints[j]. Each constraint
891 : * stores its list link in constraints[i].link (note any constraint will
892 : * be in just one list). The array index for the before-proc of the i'th
893 : * constraint is remembered in constraints[i].pred.
894 : *
895 : * Note that it's not necessarily the case that every constraint affects
896 : * this particular wait queue. Prior to group locking, a process could be
897 : * waiting for at most one lock. But a lock group can be waiting for
898 : * zero, one, or multiple locks. Since topoProcs[] is an array of the
899 : * processes actually waiting, while constraints[] is an array of group
900 : * leaders, we've got to scan through topoProcs[] for each constraint,
901 : * checking whether both a waiter and a blocker for that group are
902 : * present. If so, the constraint is relevant to this wait queue; if not,
903 : * it isn't.
904 : */
905 GIC 6 : MemSet(beforeConstraints, 0, queue_size * sizeof(int));
906 6 : MemSet(afterConstraints, 0, queue_size * sizeof(int));
907 CBC 6 : for (i = 0; i < nConstraints; i++)
908 ECB : {
909 : /*
910 : * Find a representative process that is on the lock queue and part of
911 : * the waiting lock group. This may or may not be the leader, which
912 : * may or may not be waiting at all. If there are any other processes
913 : * in the same lock group on the queue, set their number of
914 : * beforeConstraints to -1 to indicate that they should be emitted
915 : * with their groupmates rather than considered separately.
916 : *
917 : * In this loop and the similar one just below, it's critical that we
918 : * consistently select the same representative member of any one lock
919 : * group, so that all the constraints are associated with the same
920 : * proc, and the -1's are only associated with not-representative
921 : * members. We select the last one in the topoProcs array.
922 : */
923 GIC 3 : proc = constraints[i].waiter;
924 3 : Assert(proc != NULL);
925 3 : jj = -1;
926 12 : for (j = queue_size; --j >= 0;)
927 : {
928 CBC 9 : PGPROC *waiter = topoProcs[j];
929 EUB :
930 GIC 9 : if (waiter == proc || waiter->lockGroupLeader == proc)
931 : {
932 5 : Assert(waiter->waitLock == lock);
933 5 : if (jj == -1)
934 3 : jj = j;
935 : else
936 ECB : {
937 CBC 2 : Assert(beforeConstraints[j] <= 0);
938 2 : beforeConstraints[j] = -1;
939 ECB : }
940 : }
941 : }
942 :
943 : /* If no matching waiter, constraint is not relevant to this lock. */
944 GIC 3 : if (jj < 0)
945 LBC 0 : continue;
946 ECB :
947 : /*
948 : * Similarly, find a representative process that is on the lock queue
949 : * and waiting for the blocking lock group. Again, this could be the
950 EUB : * leader but does not need to be.
951 : */
952 GIC 3 : proc = constraints[i].blocker;
953 3 : Assert(proc != NULL);
954 3 : kk = -1;
955 12 : for (k = queue_size; --k >= 0;)
956 : {
957 CBC 9 : PGPROC *blocker = topoProcs[k];
958 EUB :
959 GIC 9 : if (blocker == proc || blocker->lockGroupLeader == proc)
960 ECB : {
961 CBC 3 : Assert(blocker->waitLock == lock);
962 GIC 3 : if (kk == -1)
963 CBC 3 : kk = k;
964 ECB : else
965 : {
966 UIC 0 : Assert(beforeConstraints[k] <= 0);
967 0 : beforeConstraints[k] = -1;
968 : }
969 : }
970 : }
971 :
972 : /* If no matching blocker, constraint is not relevant to this lock. */
973 GIC 3 : if (kk < 0)
974 UIC 0 : continue;
975 :
976 GIC 3 : Assert(beforeConstraints[jj] >= 0);
977 3 : beforeConstraints[jj]++; /* waiter must come before */
978 : /* add this constraint to list of after-constraints for blocker */
979 CBC 3 : constraints[i].pred = jj;
980 3 : constraints[i].link = afterConstraints[kk];
981 GIC 3 : afterConstraints[kk] = i + 1;
982 : }
983 ECB :
984 : /*--------------------
985 : * Now scan the topoProcs array backwards. At each step, output the
986 : * last proc that has no remaining before-constraints plus any other
987 EUB : * members of the same lock group; then decrease the beforeConstraints
988 ECB : * count of each of the procs it was constrained against.
989 : * i = index of ordering[] entry we want to output this time
990 : * j = search index for topoProcs[]
991 : * k = temp for scanning constraint list for proc j
992 : * last = last non-null index in topoProcs (avoid redundant searches)
993 : *--------------------
994 : */
995 CBC 3 : last = queue_size - 1;
996 GBC 10 : for (i = queue_size - 1; i >= 0;)
997 : {
998 : int c;
999 GIC 7 : int nmatches = 0;
1000 :
1001 : /* Find next candidate to output */
1002 7 : while (topoProcs[last] == NULL)
1003 UIC 0 : last--;
1004 GIC 14 : for (j = last; j >= 0; j--)
1005 : {
1006 14 : if (topoProcs[j] != NULL && beforeConstraints[j] == 0)
1007 CBC 7 : break;
1008 ECB : }
1009 :
1010 : /* If no available candidate, topological sort fails */
1011 CBC 7 : if (j < 0)
1012 UIC 0 : return false;
1013 ECB :
1014 : /*
1015 : * Output everything in the lock group. There's no point in
1016 : * outputting an ordering where members of the same lock group are not
1017 : * consecutive on the wait queue: if some other waiter is between two
1018 : * requests that belong to the same group, then either it conflicts
1019 : * with both of them and is certainly not a solution; or it conflicts
1020 : * with at most one of them and is thus isomorphic to an ordering
1021 : * where the group members are consecutive.
1022 : */
1023 GIC 7 : proc = topoProcs[j];
1024 7 : if (proc->lockGroupLeader != NULL)
1025 CBC 2 : proc = proc->lockGroupLeader;
1026 7 : Assert(proc != NULL);
1027 GIC 28 : for (c = 0; c <= last; ++c)
1028 : {
1029 21 : if (topoProcs[c] == proc || (topoProcs[c] != NULL &&
1030 CBC 11 : topoProcs[c]->lockGroupLeader == proc))
1031 : {
1032 GIC 9 : ordering[i - nmatches] = topoProcs[c];
1033 9 : topoProcs[c] = NULL;
1034 9 : ++nmatches;
1035 : }
1036 : }
1037 7 : Assert(nmatches > 0);
1038 7 : i -= nmatches;
1039 :
1040 : /* Update beforeConstraints counts of its predecessors */
1041 10 : for (k = afterConstraints[j]; k > 0; k = constraints[k - 1].link)
1042 3 : beforeConstraints[constraints[k - 1].pred]--;
1043 : }
1044 :
1045 : /* Done */
1046 3 : return true;
1047 : }
1048 :
1049 : #ifdef DEBUG_DEADLOCK
1050 : static void
1051 : PrintLockQueue(LOCK *lock, const char *info)
1052 : {
1053 : dclist_head *waitQueue = &lock->waitProcs;
1054 : dlist_iter proc_iter;
1055 ECB :
1056 : printf("%s lock %p queue ", info, lock);
1057 :
1058 : dclist_foreach(proc_iter, waitQueue)
1059 : {
1060 : PGPROC *proc = dlist_container(PGPROC, links, proc_iter.cur);
1061 :
1062 : printf(" %d", proc->pid);
1063 : }
1064 : printf("\n");
1065 : fflush(stdout);
1066 : }
1067 : #endif
1068 :
1069 : /*
1070 : * Report a detected deadlock, with available details.
1071 : */
1072 : void
1073 GIC 5 : DeadLockReport(void)
1074 ECB : {
1075 : StringInfoData clientbuf; /* errdetail for client */
1076 : StringInfoData logbuf; /* errdetail for server log */
1077 : StringInfoData locktagbuf;
1078 : int i;
1079 :
1080 CBC 5 : initStringInfo(&clientbuf);
1081 GIC 5 : initStringInfo(&logbuf);
1082 CBC 5 : initStringInfo(&locktagbuf);
1083 :
1084 ECB : /* Generate the "waits for" lines sent to the client */
1085 CBC 22 : for (i = 0; i < nDeadlockDetails; i++)
1086 : {
1087 17 : DEADLOCK_INFO *info = &deadlockDetails[i];
1088 ECB : int nextpid;
1089 :
1090 : /* The last proc waits for the first one... */
1091 GIC 17 : if (i < nDeadlockDetails - 1)
1092 12 : nextpid = info[1].pid;
1093 : else
1094 5 : nextpid = deadlockDetails[0].pid;
1095 :
1096 : /* reset locktagbuf to hold next object description */
1097 CBC 17 : resetStringInfo(&locktagbuf);
1098 :
1099 GIC 17 : DescribeLockTag(&locktagbuf, &info->locktag);
1100 ECB :
1101 GIC 17 : if (i > 0)
1102 CBC 12 : appendStringInfoChar(&clientbuf, '\n');
1103 :
1104 34 : appendStringInfo(&clientbuf,
1105 GIC 17 : _("Process %d waits for %s on %s; blocked by process %d."),
1106 ECB : info->pid,
1107 CBC 17 : GetLockmodeName(info->locktag.locktag_lockmethodid,
1108 : info->lockmode),
1109 : locktagbuf.data,
1110 : nextpid);
1111 : }
1112 ECB :
1113 : /* Duplicate all the above for the server ... */
1114 CBC 5 : appendBinaryStringInfo(&logbuf, clientbuf.data, clientbuf.len);
1115 :
1116 : /* ... and add info about query strings */
1117 GIC 22 : for (i = 0; i < nDeadlockDetails; i++)
1118 : {
1119 17 : DEADLOCK_INFO *info = &deadlockDetails[i];
1120 :
1121 17 : appendStringInfoChar(&logbuf, '\n');
1122 :
1123 17 : appendStringInfo(&logbuf,
1124 17 : _("Process %d: %s"),
1125 : info->pid,
1126 : pgstat_get_backend_current_activity(info->pid, false));
1127 : }
1128 ECB :
1129 GIC 5 : pgstat_report_deadlock();
1130 :
1131 5 : ereport(ERROR,
1132 : (errcode(ERRCODE_T_R_DEADLOCK_DETECTED),
1133 ECB : errmsg("deadlock detected"),
1134 : errdetail_internal("%s", clientbuf.data),
1135 : errdetail_log("%s", logbuf.data),
1136 : errhint("See server log for query details.")));
1137 : }
1138 :
1139 : /*
1140 : * RememberSimpleDeadLock: set up info for DeadLockReport when ProcSleep
1141 : * detects a trivial (two-way) deadlock. proc1 wants to block for lockmode
1142 : * on lock, but proc2 is already waiting and would be blocked by proc1.
1143 : */
1144 : void
1145 GIC 1 : RememberSimpleDeadLock(PGPROC *proc1,
1146 : LOCKMODE lockmode,
1147 : LOCK *lock,
1148 : PGPROC *proc2)
1149 : {
1150 1 : DEADLOCK_INFO *info = &deadlockDetails[0];
1151 :
1152 1 : info->locktag = lock->tag;
1153 1 : info->lockmode = lockmode;
1154 1 : info->pid = proc1->pid;
1155 1 : info++;
1156 1 : info->locktag = proc2->waitLock->tag;
1157 1 : info->lockmode = proc2->waitLockMode;
1158 1 : info->pid = proc2->pid;
1159 1 : nDeadlockDetails = 2;
1160 1 : }
|
