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