Age Owner Branch data 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-2026, 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 "storage/procnumber.h"
34 : : #include "utils/memutils.h"
35 : :
36 : :
37 : : /*
38 : : * One edge in the waits-for graph.
39 : : *
40 : : * waiter and blocker may or may not be members of a lock group, but if either
41 : : * is, it will be the leader rather than any other member of the lock group.
42 : : * The group leaders act as representatives of the whole group even though
43 : : * those particular processes need not be waiting at all. There will be at
44 : : * least one member of the waiter's lock group on the wait queue for the given
45 : : * lock, maybe more.
46 : : */
47 : : typedef struct
48 : : {
49 : : PGPROC *waiter; /* the leader of the waiting lock group */
50 : : PGPROC *blocker; /* the leader of the group it is waiting for */
51 : : LOCK *lock; /* the lock being waited for */
52 : : int pred; /* workspace for TopoSort */
53 : : int link; /* workspace for TopoSort */
54 : : } EDGE;
55 : :
56 : : /* One potential reordering of a lock's wait queue */
57 : : typedef struct
58 : : {
59 : : LOCK *lock; /* the lock whose wait queue is described */
60 : : PGPROC **procs; /* array of PGPROC *'s in new wait order */
61 : : int nProcs;
62 : : } WAIT_ORDER;
63 : :
64 : : /*
65 : : * Information saved about each edge in a detected deadlock cycle. This
66 : : * is used to print a diagnostic message upon failure.
67 : : *
68 : : * Note: because we want to examine this info after releasing the lock
69 : : * manager's partition locks, we can't just store LOCK and PGPROC pointers;
70 : : * we must extract out all the info we want to be able to print.
71 : : */
72 : : typedef struct
73 : : {
74 : : LOCKTAG locktag; /* ID of awaited lock object */
75 : : LOCKMODE lockmode; /* type of lock we're waiting for */
76 : : int pid; /* PID of blocked backend */
77 : : } DEADLOCK_INFO;
78 : :
79 : :
80 : : static bool DeadLockCheckRecurse(PGPROC *proc);
81 : : static int TestConfiguration(PGPROC *startProc);
82 : : static bool FindLockCycle(PGPROC *checkProc,
83 : : EDGE *softEdges, int *nSoftEdges);
84 : : static bool FindLockCycleRecurse(PGPROC *checkProc, int depth,
85 : : EDGE *softEdges, int *nSoftEdges);
86 : : static bool FindLockCycleRecurseMember(PGPROC *checkProc,
87 : : PGPROC *checkProcLeader,
88 : : int depth, EDGE *softEdges, int *nSoftEdges);
89 : : static bool ExpandConstraints(EDGE *constraints, int nConstraints);
90 : : static bool TopoSort(LOCK *lock, EDGE *constraints, int nConstraints,
91 : : PGPROC **ordering);
92 : :
93 : : #ifdef DEBUG_DEADLOCK
94 : : static void PrintLockQueue(LOCK *lock, const char *info);
95 : : #endif
96 : :
97 : :
98 : : /*
99 : : * Working space for the deadlock detector
100 : : */
101 : :
102 : : /* Workspace for FindLockCycle */
103 : : static PGPROC **visitedProcs; /* Array of visited procs */
104 : : static int nVisitedProcs;
105 : :
106 : : /* Workspace for TopoSort */
107 : : static PGPROC **topoProcs; /* Array of not-yet-output procs */
108 : : static int *beforeConstraints; /* Counts of remaining before-constraints */
109 : : static int *afterConstraints; /* List head for after-constraints */
110 : :
111 : : /* Output area for ExpandConstraints */
112 : : static WAIT_ORDER *waitOrders; /* Array of proposed queue rearrangements */
113 : : static int nWaitOrders;
114 : : static PGPROC **waitOrderProcs; /* Space for waitOrders queue contents */
115 : :
116 : : /* Current list of constraints being considered */
117 : : static EDGE *curConstraints;
118 : : static int nCurConstraints;
119 : : static int maxCurConstraints;
120 : :
121 : : /* Storage space for results from FindLockCycle */
122 : : static EDGE *possibleConstraints;
123 : : static int nPossibleConstraints;
124 : : static int maxPossibleConstraints;
125 : : static DEADLOCK_INFO *deadlockDetails;
126 : : static int nDeadlockDetails;
127 : :
128 : : /* PGPROC pointer of any blocking autovacuum worker found */
129 : : static PGPROC *blocking_autovacuum_proc = NULL;
130 : :
131 : :
132 : : /*
133 : : * InitDeadLockChecking -- initialize deadlock checker during backend startup
134 : : *
135 : : * This does per-backend initialization of the deadlock checker; primarily,
136 : : * allocation of working memory for DeadLockCheck. We do this per-backend
137 : : * since there's no percentage in making the kernel do copy-on-write
138 : : * inheritance of workspace from the postmaster. We allocate the space at
139 : : * startup because the deadlock checker is run with all the partitions of the
140 : : * lock table locked, and we want to keep that section as short as possible.
141 : : */
142 : : void
9345 tgl@sss.pgh.pa.us 143 :CBC 18970 : InitDeadLockChecking(void)
144 : : {
145 : : MemoryContext oldcxt;
146 : :
147 : : /* Make sure allocations are permanent */
148 : 18970 : oldcxt = MemoryContextSwitchTo(TopMemoryContext);
149 : :
150 : : /*
151 : : * FindLockCycle needs at most MaxBackends entries in visitedProcs[] and
152 : : * deadlockDetails[].
153 : : */
10 michael@paquier.xyz 154 :GNC 18970 : visitedProcs = palloc_array(PGPROC *, MaxBackends);
155 : 18970 : deadlockDetails = palloc_array(DEADLOCK_INFO, MaxBackends);
156 : :
157 : : /*
158 : : * TopoSort needs to consider at most MaxBackends wait-queue entries, and
159 : : * it needn't run concurrently with FindLockCycle.
160 : : */
9345 tgl@sss.pgh.pa.us 161 :CBC 18970 : topoProcs = visitedProcs; /* re-use this space */
10 michael@paquier.xyz 162 :GNC 18970 : beforeConstraints = palloc_array(int, MaxBackends);
163 : 18970 : afterConstraints = palloc_array(int, MaxBackends);
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 : 18970 : waitOrders = palloc_array(WAIT_ORDER, MaxBackends / 2);
172 : 18970 : waitOrderProcs = palloc_array(PGPROC *, MaxBackends);
173 : :
174 : : /*
175 : : * Allow at most MaxBackends distinct constraints in a configuration. (Is
176 : : * this enough? In practice it seems it should be, but I don't quite see
177 : : * how to prove it. If we run out, we might fail to find a workable wait
178 : : * queue rearrangement even though one exists.) NOTE that this number
179 : : * limits the maximum recursion depth of DeadLockCheckRecurse. Making it
180 : : * really big might potentially allow a stack-overflow problem.
181 : : */
1598 rhaas@postgresql.org 182 :CBC 18970 : maxCurConstraints = MaxBackends;
10 michael@paquier.xyz 183 :GNC 18970 : curConstraints = palloc_array(EDGE, maxCurConstraints);
184 : :
185 : : /*
186 : : * Allow up to 3*MaxBackends constraints to be saved without having to
187 : : * re-run TestConfiguration. (This is probably more than enough, but we
188 : : * can survive if we run low on space by doing excess runs of
189 : : * TestConfiguration to re-compute constraint lists each time needed.) The
190 : : * last MaxBackends entries in possibleConstraints[] are reserved as
191 : : * output workspace for FindLockCycle.
192 : : */
193 : : {
194 : : StaticAssertDecl(MAX_BACKENDS_BITS <= (32 - 3),
195 : : "MAX_BACKENDS_BITS too big for * 4");
192 peter@eisentraut.org 196 :CBC 18970 : maxPossibleConstraints = MaxBackends * 4;
10 michael@paquier.xyz 197 :GNC 18970 : possibleConstraints = palloc_array(EDGE, maxPossibleConstraints);
198 : : }
199 : :
9345 tgl@sss.pgh.pa.us 200 :CBC 18970 : MemoryContextSwitchTo(oldcxt);
201 : 18970 : }
202 : :
203 : : /*
204 : : * DeadLockCheck -- Checks for deadlocks for a given process
205 : : *
206 : : * This code looks for deadlocks involving the given process. If any
207 : : * are found, it tries to rearrange lock wait queues to resolve the
208 : : * deadlock. If resolution is impossible, return DS_HARD_DEADLOCK ---
209 : : * the caller is then expected to abort the given proc's transaction.
210 : : *
211 : : * Caller must already have locked all partitions of the lock tables.
212 : : *
213 : : * On failure, deadlock details are recorded in deadlockDetails[] for
214 : : * subsequent printing by DeadLockReport(). That activity is separate
215 : : * because we don't want to do it while holding all those LWLocks.
216 : : */
217 : : DeadLockState
8843 JanWieck@Yahoo.com 218 : 57 : DeadLockCheck(PGPROC *proc)
219 : : {
220 : : /* Initialize to "no constraints" */
9345 tgl@sss.pgh.pa.us 221 : 57 : nCurConstraints = 0;
222 : 57 : nPossibleConstraints = 0;
223 : 57 : nWaitOrders = 0;
224 : :
225 : : /* Initialize to not blocked by an autovacuum worker */
6880 alvherre@alvh.no-ip. 226 : 57 : blocking_autovacuum_proc = NULL;
227 : :
228 : : /* Search for deadlocks and possible fixes */
9345 tgl@sss.pgh.pa.us 229 [ + + ]: 57 : if (DeadLockCheckRecurse(proc))
230 : : {
231 : : /*
232 : : * Call FindLockCycle one more time, to record the correct
233 : : * deadlockDetails[] for the basic state with no rearrangements.
234 : : */
235 : : int nSoftEdges;
236 : :
237 : : TRACE_POSTGRESQL_DEADLOCK_FOUND();
238 : :
8624 239 : 5 : nWaitOrders = 0;
240 [ - + ]: 5 : if (!FindLockCycle(proc, possibleConstraints, &nSoftEdges))
8435 tgl@sss.pgh.pa.us 241 [ # # ]:UBC 0 : elog(FATAL, "deadlock seems to have disappeared");
242 : :
7117 bruce@momjian.us 243 :CBC 5 : return DS_HARD_DEADLOCK; /* cannot find a non-deadlocked state */
244 : : }
245 : :
246 : : /* Apply any needed rearrangements of wait queues */
1317 andres@anarazel.de 247 [ + + ]: 55 : for (int i = 0; i < nWaitOrders; i++)
248 : : {
9289 bruce@momjian.us 249 : 3 : LOCK *lock = waitOrders[i].lock;
8843 JanWieck@Yahoo.com 250 : 3 : PGPROC **procs = waitOrders[i].procs;
9289 bruce@momjian.us 251 : 3 : int nProcs = waitOrders[i].nProcs;
1317 andres@anarazel.de 252 : 3 : dclist_head *waitQueue = &lock->waitProcs;
253 : :
254 [ - + ]: 3 : Assert(nProcs == dclist_count(waitQueue));
255 : :
256 : : #ifdef DEBUG_DEADLOCK
257 : : PrintLockQueue(lock, "DeadLockCheck:");
258 : : #endif
259 : :
260 : : /* Reset the queue and re-add procs in the desired order */
261 : 3 : dclist_init(waitQueue);
262 [ + + ]: 12 : for (int j = 0; j < nProcs; j++)
188 heikki.linnakangas@i 263 : 9 : dclist_push_tail(waitQueue, &procs[j]->waitLink);
264 : :
265 : : #ifdef DEBUG_DEADLOCK
266 : : PrintLockQueue(lock, "rearranged to:");
267 : : #endif
268 : :
269 : : /* See if any waiters for the lock can be woken up now */
9345 tgl@sss.pgh.pa.us 270 : 3 : ProcLockWakeup(GetLocksMethodTable(lock), lock);
271 : : }
272 : :
273 : : /* Return code tells caller if we had to escape a deadlock or not */
7117 bruce@momjian.us 274 [ + + ]: 52 : if (nWaitOrders > 0)
275 : 3 : return DS_SOFT_DEADLOCK;
6880 alvherre@alvh.no-ip. 276 [ - + ]: 49 : else if (blocking_autovacuum_proc != NULL)
6880 alvherre@alvh.no-ip. 277 :LBC (2) : return DS_BLOCKED_BY_AUTOVACUUM;
278 : : else
7009 tgl@sss.pgh.pa.us 279 :CBC 49 : return DS_NO_DEADLOCK;
280 : : }
281 : :
282 : : /*
283 : : * Return the PGPROC of the autovacuum that's blocking a process.
284 : : *
285 : : * We reset the saved pointer as soon as we pass it back.
286 : : */
287 : : PGPROC *
6880 alvherre@alvh.no-ip. 288 :LBC (2) : GetBlockingAutoVacuumPgproc(void)
289 : : {
290 : : PGPROC *ptr;
291 : :
292 : (2) : ptr = blocking_autovacuum_proc;
293 : (2) : blocking_autovacuum_proc = NULL;
294 : :
295 : (2) : return ptr;
296 : : }
297 : :
298 : : /*
299 : : * DeadLockCheckRecurse -- recursively search for valid orderings
300 : : *
301 : : * curConstraints[] holds the current set of constraints being considered
302 : : * by an outer level of recursion. Add to this each possible solution
303 : : * constraint for any cycle detected at this level.
304 : : *
305 : : * Returns true if no solution exists. Returns false if a deadlock-free
306 : : * state is attainable, in which case waitOrders[] shows the required
307 : : * rearrangements of lock wait queues (if any).
308 : : */
309 : : static bool
8843 JanWieck@Yahoo.com 310 :CBC 60 : DeadLockCheckRecurse(PGPROC *proc)
311 : : {
312 : : int nEdges;
313 : : int oldPossibleConstraints;
314 : : bool savedList;
315 : : int i;
316 : :
9345 tgl@sss.pgh.pa.us 317 : 60 : nEdges = TestConfiguration(proc);
318 [ + + ]: 60 : if (nEdges < 0)
319 : 5 : return true; /* hard deadlock --- no solution */
320 [ + + ]: 55 : if (nEdges == 0)
321 : 52 : return false; /* good configuration found */
322 [ - + ]: 3 : if (nCurConstraints >= maxCurConstraints)
9345 tgl@sss.pgh.pa.us 323 :UBC 0 : return true; /* out of room for active constraints? */
9345 tgl@sss.pgh.pa.us 324 :CBC 3 : oldPossibleConstraints = nPossibleConstraints;
1598 rhaas@postgresql.org 325 [ + - ]: 3 : if (nPossibleConstraints + nEdges + MaxBackends <= maxPossibleConstraints)
326 : : {
327 : : /* We can save the edge list in possibleConstraints[] */
9345 tgl@sss.pgh.pa.us 328 : 3 : nPossibleConstraints += nEdges;
329 : 3 : savedList = true;
330 : : }
331 : : else
332 : : {
333 : : /* Not room; will need to regenerate the edges on-the-fly */
9345 tgl@sss.pgh.pa.us 334 :UBC 0 : savedList = false;
335 : : }
336 : :
337 : : /*
338 : : * Try each available soft edge as an addition to the configuration.
339 : : */
9345 tgl@sss.pgh.pa.us 340 [ + - ]:CBC 3 : for (i = 0; i < nEdges; i++)
341 : : {
342 [ - + - - ]: 3 : if (!savedList && i > 0)
343 : : {
344 : : /* Regenerate the list of possible added constraints */
9345 tgl@sss.pgh.pa.us 345 [ # # ]:UBC 0 : if (nEdges != TestConfiguration(proc))
8435 346 [ # # ]: 0 : elog(FATAL, "inconsistent results during deadlock check");
347 : : }
9345 tgl@sss.pgh.pa.us 348 :CBC 3 : curConstraints[nCurConstraints] =
9289 bruce@momjian.us 349 : 3 : possibleConstraints[oldPossibleConstraints + i];
9345 tgl@sss.pgh.pa.us 350 : 3 : nCurConstraints++;
351 [ + - ]: 3 : if (!DeadLockCheckRecurse(proc))
352 : 3 : return false; /* found a valid solution! */
353 : : /* give up on that added constraint, try again */
9345 tgl@sss.pgh.pa.us 354 :UBC 0 : nCurConstraints--;
355 : : }
356 : 0 : nPossibleConstraints = oldPossibleConstraints;
357 : 0 : return true; /* no solution found */
358 : : }
359 : :
360 : :
361 : : /*--------------------
362 : : * Test a configuration (current set of constraints) for validity.
363 : : *
364 : : * Returns:
365 : : * 0: the configuration is good (no deadlocks)
366 : : * -1: the configuration has a hard deadlock or is not self-consistent
367 : : * >0: the configuration has one or more soft deadlocks
368 : : *
369 : : * In the soft-deadlock case, one of the soft cycles is chosen arbitrarily
370 : : * and a list of its soft edges is returned beginning at
371 : : * possibleConstraints+nPossibleConstraints. The return value is the
372 : : * number of soft edges.
373 : : *--------------------
374 : : */
375 : : static int
8843 JanWieck@Yahoo.com 376 :CBC 60 : TestConfiguration(PGPROC *startProc)
377 : : {
9289 bruce@momjian.us 378 : 60 : int softFound = 0;
379 : 60 : EDGE *softEdges = possibleConstraints + nPossibleConstraints;
380 : : int nSoftEdges;
381 : : int i;
382 : :
383 : : /*
384 : : * Make sure we have room for FindLockCycle's output.
385 : : */
1598 rhaas@postgresql.org 386 [ - + ]: 60 : if (nPossibleConstraints + MaxBackends > maxPossibleConstraints)
9345 tgl@sss.pgh.pa.us 387 :UBC 0 : return -1;
388 : :
389 : : /*
390 : : * Expand current constraint set into wait orderings. Fail if the
391 : : * constraint set is not self-consistent.
392 : : */
9345 tgl@sss.pgh.pa.us 393 [ - + ]:CBC 60 : if (!ExpandConstraints(curConstraints, nCurConstraints))
9345 tgl@sss.pgh.pa.us 394 :UBC 0 : return -1;
395 : :
396 : : /*
397 : : * Check for cycles involving startProc or any of the procs mentioned in
398 : : * constraints. We check startProc last because if it has a soft cycle
399 : : * still to be dealt with, we want to deal with that first.
400 : : */
9345 tgl@sss.pgh.pa.us 401 [ + + ]:CBC 63 : for (i = 0; i < nCurConstraints; i++)
402 : : {
403 [ - + ]: 3 : if (FindLockCycle(curConstraints[i].waiter, softEdges, &nSoftEdges))
404 : : {
9345 tgl@sss.pgh.pa.us 405 [ # # ]:UBC 0 : if (nSoftEdges == 0)
406 : 0 : return -1; /* hard deadlock detected */
407 : 0 : softFound = nSoftEdges;
408 : : }
9345 tgl@sss.pgh.pa.us 409 [ - + ]:CBC 3 : if (FindLockCycle(curConstraints[i].blocker, softEdges, &nSoftEdges))
410 : : {
9345 tgl@sss.pgh.pa.us 411 [ # # ]:UBC 0 : if (nSoftEdges == 0)
412 : 0 : return -1; /* hard deadlock detected */
413 : 0 : softFound = nSoftEdges;
414 : : }
415 : : }
9345 tgl@sss.pgh.pa.us 416 [ + + ]:CBC 60 : if (FindLockCycle(startProc, softEdges, &nSoftEdges))
417 : : {
418 [ + + ]: 8 : if (nSoftEdges == 0)
419 : 5 : return -1; /* hard deadlock detected */
420 : 3 : softFound = nSoftEdges;
421 : : }
422 : 55 : return softFound;
423 : : }
424 : :
425 : :
426 : : /*
427 : : * FindLockCycle -- basic check for deadlock cycles
428 : : *
429 : : * Scan outward from the given proc to see if there is a cycle in the
430 : : * waits-for graph that includes this proc. Return true if a cycle
431 : : * is found, else false. If a cycle is found, we return a list of
432 : : * the "soft edges", if any, included in the cycle. These edges could
433 : : * potentially be eliminated by rearranging wait queues. We also fill
434 : : * deadlockDetails[] with information about the detected cycle; this info
435 : : * is not used by the deadlock algorithm itself, only to print a useful
436 : : * message after failing.
437 : : *
438 : : * Since we need to be able to check hypothetical configurations that would
439 : : * exist after wait queue rearrangement, the routine pays attention to the
440 : : * table of hypothetical queue orders in waitOrders[]. These orders will
441 : : * be believed in preference to the actual ordering seen in the locktable.
442 : : */
443 : : static bool
8843 JanWieck@Yahoo.com 444 : 71 : FindLockCycle(PGPROC *checkProc,
445 : : EDGE *softEdges, /* output argument */
446 : : int *nSoftEdges) /* output argument */
447 : : {
9345 tgl@sss.pgh.pa.us 448 : 71 : nVisitedProcs = 0;
8624 449 : 71 : nDeadlockDetails = 0;
9345 450 : 71 : *nSoftEdges = 0;
8624 451 : 71 : return FindLockCycleRecurse(checkProc, 0, softEdges, nSoftEdges);
452 : : }
453 : :
454 : : static bool
8843 JanWieck@Yahoo.com 455 : 186 : FindLockCycleRecurse(PGPROC *checkProc,
456 : : int depth,
457 : : EDGE *softEdges, /* output argument */
458 : : int *nSoftEdges) /* output argument */
459 : : {
460 : : int i;
461 : : dlist_iter iter;
462 : :
463 : : /*
464 : : * If this process is a lock group member, check the leader instead. (Note
465 : : * that we might be the leader, in which case this is a no-op.)
466 : : */
3854 rhaas@postgresql.org 467 [ + + ]: 186 : if (checkProc->lockGroupLeader != NULL)
468 : 28 : checkProc = checkProc->lockGroupLeader;
469 : :
470 : : /*
471 : : * Have we already seen this proc?
472 : : */
9345 tgl@sss.pgh.pa.us 473 [ + + ]: 360 : for (i = 0; i < nVisitedProcs; i++)
474 : : {
475 [ + + ]: 193 : if (visitedProcs[i] == checkProc)
476 : : {
477 : : /* If we return to starting point, we have a deadlock cycle */
478 [ + + ]: 19 : if (i == 0)
479 : : {
480 : : /*
481 : : * record total length of cycle --- outer levels will now fill
482 : : * deadlockDetails[]
483 : : */
1598 rhaas@postgresql.org 484 [ - + ]: 13 : Assert(depth <= MaxBackends);
8624 tgl@sss.pgh.pa.us 485 : 13 : nDeadlockDetails = depth;
486 : :
9345 487 : 13 : return true;
488 : : }
489 : :
490 : : /*
491 : : * Otherwise, we have a cycle but it does not include the start
492 : : * point, so say "no deadlock".
493 : : */
494 : 6 : return false;
495 : : }
496 : : }
497 : : /* Mark proc as seen */
1598 rhaas@postgresql.org 498 [ - + ]: 167 : Assert(nVisitedProcs < MaxBackends);
9345 tgl@sss.pgh.pa.us 499 : 167 : visitedProcs[nVisitedProcs++] = checkProc;
500 : :
501 : : /*
502 : : * If the process is waiting, there is an outgoing waits-for edge to each
503 : : * process that blocks it.
504 : : */
188 heikki.linnakangas@i 505 [ + + + + ]: 271 : if (!dlist_node_is_detached(&checkProc->waitLink) &&
3854 rhaas@postgresql.org 506 : 104 : FindLockCycleRecurseMember(checkProc, checkProc, depth, softEdges,
507 : : nSoftEdges))
508 : 41 : return true;
509 : :
510 : : /*
511 : : * If the process is not waiting, there could still be outgoing waits-for
512 : : * edges if it is part of a lock group, because other members of the lock
513 : : * group might be waiting even though this process is not. (Given lock
514 : : * groups {A1, A2} and {B1, B2}, if A1 waits for B1 and B2 waits for A2,
515 : : * that is a deadlock even neither of B1 and A2 are waiting for anything.)
516 : : */
517 [ + - + + ]: 175 : dlist_foreach(iter, &checkProc->lockGroupMembers)
518 : : {
519 : : PGPROC *memberProc;
520 : :
521 : 53 : memberProc = dlist_container(PGPROC, lockGroupLink, iter.cur);
522 : :
188 heikki.linnakangas@i 523 [ + + + - : 53 : if (!dlist_node_is_detached(&memberProc->waitLink) && memberProc->waitLock != NULL &&
+ - ]
3854 rhaas@postgresql.org 524 [ + + ]: 21 : memberProc != checkProc &&
3354 tgl@sss.pgh.pa.us 525 : 21 : FindLockCycleRecurseMember(memberProc, checkProc, depth, softEdges,
526 : : nSoftEdges))
3854 rhaas@postgresql.org 527 : 4 : return true;
528 : : }
529 : :
530 : 122 : return false;
531 : : }
532 : :
533 : : static bool
534 : 125 : FindLockCycleRecurseMember(PGPROC *checkProc,
535 : : PGPROC *checkProcLeader,
536 : : int depth,
537 : : EDGE *softEdges, /* output argument */
538 : : int *nSoftEdges) /* output argument */
539 : : {
540 : : PGPROC *proc;
541 : 125 : LOCK *lock = checkProc->waitLock;
542 : : dlist_iter proclock_iter;
543 : : LockMethod lockMethodTable;
544 : : int conflictMask;
545 : : int i;
546 : : int numLockModes,
547 : : lm;
548 : :
549 : : /*
550 : : * The relation extension lock can never participate in actual deadlock
551 : : * cycle. See Assert in LockAcquireExtended. So, there is no advantage
552 : : * in checking wait edges from it.
553 : : */
1148 akapila@postgresql.o 554 [ - + ]: 125 : if (LOCK_LOCKTAG(*lock) == LOCKTAG_RELATION_EXTEND)
2351 akapila@postgresql.o 555 :UBC 0 : return false;
556 : :
9345 tgl@sss.pgh.pa.us 557 :CBC 125 : lockMethodTable = GetLocksMethodTable(lock);
8806 bruce@momjian.us 558 : 125 : numLockModes = lockMethodTable->numLockModes;
559 : 125 : conflictMask = lockMethodTable->conflictTab[checkProc->waitLockMode];
560 : :
561 : : /*
562 : : * Scan for procs that already hold conflicting locks. These are "hard"
563 : : * edges in the waits-for graph.
564 : : */
1317 andres@anarazel.de 565 [ + - + + ]: 367 : dlist_foreach(proclock_iter, &lock->procLocks)
566 : : {
567 : 282 : PROCLOCK *proclock = dlist_container(PROCLOCK, lockLink, proclock_iter.cur);
568 : : PGPROC *leader;
569 : :
7340 tgl@sss.pgh.pa.us 570 : 282 : proc = proclock->tag.myProc;
3854 rhaas@postgresql.org 571 [ + + ]: 282 : leader = proc->lockGroupLeader == NULL ? proc : proc->lockGroupLeader;
572 : :
573 : : /* A proc never blocks itself or any other lock group member */
574 [ + + ]: 282 : if (leader != checkProcLeader)
575 : : {
9345 tgl@sss.pgh.pa.us 576 [ + + ]: 1324 : for (lm = 1; lm <= numLockModes; lm++)
577 : : {
8035 578 [ + + + + ]: 1248 : if ((proclock->holdMask & LOCKBIT_ON(lm)) &&
579 : : (conflictMask & LOCKBIT_ON(lm)))
580 : : {
581 : : /* This proc hard-blocks checkProc */
8424 bruce@momjian.us 582 [ + + ]: 99 : if (FindLockCycleRecurse(proc, depth + 1,
583 : : softEdges, nSoftEdges))
584 : : {
585 : : /* fill deadlockDetails[] */
586 : 40 : DEADLOCK_INFO *info = &deadlockDetails[depth];
587 : :
8624 tgl@sss.pgh.pa.us 588 : 40 : info->locktag = lock->tag;
589 : 40 : info->lockmode = checkProc->waitLockMode;
590 : 40 : info->pid = checkProc->pid;
591 : :
9345 592 : 40 : 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 : : * rule simplifies understanding the behavior and ensures
605 : : * that an autovacuum won't be canceled with less than
606 : : * deadlock_timeout grace period.
607 : : *
608 : : * Note we read statusFlags without any locking. This is
609 : : * 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 : : */
5145 617 [ + + ]: 59 : if (checkProc == MyProc &&
2110 alvherre@alvh.no-ip. 618 [ - + ]: 48 : proc->statusFlags & PROC_IS_AUTOVACUUM)
5145 tgl@sss.pgh.pa.us 619 :LBC (2) : blocking_autovacuum_proc = proc;
620 : :
621 : : /* We're done looking at this proclock */
9345 tgl@sss.pgh.pa.us 622 :CBC 59 : break;
623 : : }
624 : : }
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 [ + + ]: 94 : for (i = 0; i < nWaitOrders; i++)
638 : : {
639 [ + + ]: 27 : if (waitOrders[i].lock == lock)
640 : 18 : break;
641 : : }
642 : :
643 [ + + ]: 85 : if (i < nWaitOrders)
644 : : {
645 : : /* Use the given hypothetical wait queue order */
8843 JanWieck@Yahoo.com 646 : 18 : PGPROC **procs = waitOrders[i].procs;
1317 andres@anarazel.de 647 : 18 : int queue_size = waitOrders[i].nProcs;
648 : :
9345 tgl@sss.pgh.pa.us 649 [ + - ]: 23 : for (i = 0; i < queue_size; i++)
650 : : {
651 : : PGPROC *leader;
652 : :
653 : 23 : proc = procs[i];
3854 rhaas@postgresql.org 654 [ + + ]: 23 : leader = proc->lockGroupLeader == NULL ? proc :
655 : : proc->lockGroupLeader;
656 : :
657 : : /*
658 : : * 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 [ + + ]: 23 : if (leader == checkProcLeader)
9345 tgl@sss.pgh.pa.us 665 : 18 : break;
666 : :
667 : : /* Is there a conflict with this guy's request? */
3986 rhaas@postgresql.org 668 [ + - ]: 5 : if ((LOCKBIT_ON(proc->waitLockMode) & conflictMask) != 0)
669 : : {
670 : : /* This proc soft-blocks checkProc */
8424 bruce@momjian.us 671 [ - + ]: 5 : if (FindLockCycleRecurse(proc, depth + 1,
672 : : softEdges, nSoftEdges))
673 : : {
674 : : /* fill deadlockDetails[] */
8424 bruce@momjian.us 675 :UBC 0 : DEADLOCK_INFO *info = &deadlockDetails[depth];
676 : :
8624 tgl@sss.pgh.pa.us 677 : 0 : info->locktag = lock->tag;
678 : 0 : info->lockmode = checkProc->waitLockMode;
679 : 0 : info->pid = checkProc->pid;
680 : :
681 : : /*
682 : : * Add this edge to the list of soft edges in the cycle
683 : : */
1598 rhaas@postgresql.org 684 [ # # ]: 0 : Assert(*nSoftEdges < MaxBackends);
3854 685 : 0 : softEdges[*nSoftEdges].waiter = checkProcLeader;
686 : 0 : softEdges[*nSoftEdges].blocker = leader;
687 : 0 : softEdges[*nSoftEdges].lock = lock;
9345 tgl@sss.pgh.pa.us 688 : 0 : (*nSoftEdges)++;
689 : 0 : return true;
690 : : }
691 : : }
692 : : }
693 : : }
694 : : else
695 : : {
3854 rhaas@postgresql.org 696 :CBC 67 : PGPROC *lastGroupMember = NULL;
697 : : dlist_iter proc_iter;
698 : : dclist_head *waitQueue;
699 : :
700 : : /* Use the true lock wait queue order */
1317 andres@anarazel.de 701 : 67 : waitQueue = &lock->waitProcs;
702 : :
703 : : /*
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 : : */
3854 rhaas@postgresql.org 710 [ + + ]: 67 : if (checkProc->lockGroupLeader == NULL)
711 : 58 : lastGroupMember = checkProc;
712 : : else
713 : : {
1317 andres@anarazel.de 714 [ + - + + ]: 32 : dclist_foreach(proc_iter, waitQueue)
715 : : {
188 heikki.linnakangas@i 716 : 23 : proc = dlist_container(PGPROC, waitLink, proc_iter.cur);
717 : :
3854 rhaas@postgresql.org 718 [ + + ]: 23 : if (proc->lockGroupLeader == checkProcLeader)
719 : 13 : lastGroupMember = proc;
720 : : }
721 [ - + ]: 9 : Assert(lastGroupMember != NULL);
722 : : }
723 : :
724 : : /*
725 : : * OK, now rescan (or scan) the queue to identify the soft conflicts.
726 : : */
1317 andres@anarazel.de 727 [ + - + - ]: 80 : dclist_foreach(proc_iter, waitQueue)
728 : : {
729 : : PGPROC *leader;
730 : :
188 heikki.linnakangas@i 731 : 80 : proc = dlist_container(PGPROC, waitLink, proc_iter.cur);
732 : :
3854 rhaas@postgresql.org 733 [ + + ]: 80 : leader = proc->lockGroupLeader == NULL ? proc :
734 : : proc->lockGroupLeader;
735 : :
736 : : /* Done when we reach the target proc */
737 [ + + ]: 80 : if (proc == lastGroupMember)
9345 tgl@sss.pgh.pa.us 738 : 62 : break;
739 : :
740 : : /* Is there a conflict with this guy's request? */
3854 rhaas@postgresql.org 741 [ + + + - ]: 18 : if ((LOCKBIT_ON(proc->waitLockMode) & conflictMask) != 0 &&
742 : : leader != checkProcLeader)
743 : : {
744 : : /* This proc soft-blocks checkProc */
8424 bruce@momjian.us 745 [ + + ]: 11 : if (FindLockCycleRecurse(proc, depth + 1,
746 : : softEdges, nSoftEdges))
747 : : {
748 : : /* fill deadlockDetails[] */
749 : 5 : DEADLOCK_INFO *info = &deadlockDetails[depth];
750 : :
8624 tgl@sss.pgh.pa.us 751 : 5 : info->locktag = lock->tag;
752 : 5 : info->lockmode = checkProc->waitLockMode;
753 : 5 : info->pid = checkProc->pid;
754 : :
755 : : /*
756 : : * Add this edge to the list of soft edges in the cycle
757 : : */
1598 rhaas@postgresql.org 758 [ - + ]: 5 : Assert(*nSoftEdges < MaxBackends);
3854 759 : 5 : softEdges[*nSoftEdges].waiter = checkProcLeader;
760 : 5 : softEdges[*nSoftEdges].blocker = leader;
761 : 5 : softEdges[*nSoftEdges].lock = lock;
9345 tgl@sss.pgh.pa.us 762 : 5 : (*nSoftEdges)++;
763 : 5 : return true;
764 : : }
765 : : }
766 : : }
767 : : }
768 : :
769 : : /*
770 : : * No conflict detected here.
771 : : */
772 : 80 : return false;
773 : : }
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 : 60 : ExpandConstraints(EDGE *constraints,
789 : : int nConstraints)
790 : : {
791 : 60 : int nWaitOrderProcs = 0;
792 : : int i,
793 : : j;
794 : :
795 : 60 : nWaitOrders = 0;
796 : :
797 : : /*
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 : : */
9289 bruce@momjian.us 802 [ + + ]: 63 : for (i = nConstraints; --i >= 0;)
803 : : {
3854 rhaas@postgresql.org 804 : 3 : LOCK *lock = constraints[i].lock;
805 : :
806 : : /* Did we already make a list for this lock? */
9289 bruce@momjian.us 807 [ - + ]: 3 : for (j = nWaitOrders; --j >= 0;)
808 : : {
9345 tgl@sss.pgh.pa.us 809 [ # # ]:UBC 0 : if (waitOrders[j].lock == lock)
810 : 0 : break;
811 : : }
9345 tgl@sss.pgh.pa.us 812 [ - + ]:CBC 3 : if (j >= 0)
9345 tgl@sss.pgh.pa.us 813 :UBC 0 : continue;
814 : : /* No, so allocate a new list */
9345 tgl@sss.pgh.pa.us 815 :CBC 3 : waitOrders[nWaitOrders].lock = lock;
816 : 3 : waitOrders[nWaitOrders].procs = waitOrderProcs + nWaitOrderProcs;
1317 andres@anarazel.de 817 : 3 : waitOrders[nWaitOrders].nProcs = dclist_count(&lock->waitProcs);
818 : 3 : nWaitOrderProcs += dclist_count(&lock->waitProcs);
1598 rhaas@postgresql.org 819 [ - + ]: 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 : : */
9289 bruce@momjian.us 825 [ - + ]: 3 : if (!TopoSort(lock, constraints, i + 1,
9345 tgl@sss.pgh.pa.us 826 : 3 : waitOrders[nWaitOrders].procs))
9345 tgl@sss.pgh.pa.us 827 :UBC 0 : return false;
9345 tgl@sss.pgh.pa.us 828 :CBC 3 : nWaitOrders++;
829 : : }
830 : 60 : 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 : : * 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 : 3 : TopoSort(LOCK *lock,
861 : : EDGE *constraints,
862 : : int nConstraints,
863 : : PGPROC **ordering) /* output argument */
864 : : {
1317 andres@anarazel.de 865 : 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 : : {
188 heikki.linnakangas@i 880 : 9 : proc = dlist_container(PGPROC, waitLink, proc_iter.cur);
1317 andres@anarazel.de 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 : : * 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 : : */
9345 tgl@sss.pgh.pa.us 905 [ + - + + : 6 : MemSet(beforeConstraints, 0, queue_size * sizeof(int));
+ - + - +
+ ]
906 [ + - + + : 6 : MemSet(afterConstraints, 0, queue_size * sizeof(int));
+ - + - +
+ ]
907 [ + + ]: 6 : for (i = 0; i < nConstraints; i++)
908 : : {
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 : 3 : proc = constraints[i].waiter;
3854 rhaas@postgresql.org 924 [ - + ]: 3 : Assert(proc != NULL);
925 : 3 : jj = -1;
9289 bruce@momjian.us 926 [ + + ]: 12 : for (j = queue_size; --j >= 0;)
927 : : {
3854 rhaas@postgresql.org 928 : 9 : PGPROC *waiter = topoProcs[j];
929 : :
930 [ + + + + ]: 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 : : {
937 [ - + ]: 2 : Assert(beforeConstraints[j] <= 0);
938 : 2 : beforeConstraints[j] = -1;
939 : : }
940 : : }
941 : : }
942 : :
943 : : /* If no matching waiter, constraint is not relevant to this lock. */
944 [ - + ]: 3 : if (jj < 0)
3854 rhaas@postgresql.org 945 :UBC 0 : continue;
946 : :
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 : : * leader but does not need to be.
951 : : */
9345 tgl@sss.pgh.pa.us 952 :CBC 3 : proc = constraints[i].blocker;
3854 rhaas@postgresql.org 953 [ - + ]: 3 : Assert(proc != NULL);
954 : 3 : kk = -1;
9289 bruce@momjian.us 955 [ + + ]: 12 : for (k = queue_size; --k >= 0;)
956 : : {
3854 rhaas@postgresql.org 957 : 9 : PGPROC *blocker = topoProcs[k];
958 : :
959 [ + + + + ]: 9 : if (blocker == proc || blocker->lockGroupLeader == proc)
960 : : {
961 [ - + ]: 3 : Assert(blocker->waitLock == lock);
962 [ + - ]: 3 : if (kk == -1)
963 : 3 : kk = k;
964 : : else
965 : : {
3854 rhaas@postgresql.org 966 [ # # ]:UBC 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. */
3854 rhaas@postgresql.org 973 [ - + ]:CBC 3 : if (kk < 0)
3854 rhaas@postgresql.org 974 :UBC 0 : continue;
975 : :
2586 tgl@sss.pgh.pa.us 976 [ - + ]:CBC 3 : Assert(beforeConstraints[jj] >= 0);
3854 rhaas@postgresql.org 977 : 3 : beforeConstraints[jj]++; /* waiter must come before */
978 : : /* add this constraint to list of after-constraints for blocker */
979 : 3 : constraints[i].pred = jj;
980 : 3 : constraints[i].link = afterConstraints[kk];
981 : 3 : afterConstraints[kk] = i + 1;
982 : : }
983 : :
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 : : * members of the same lock group; then decrease the beforeConstraints
988 : : * 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 : : */
9289 bruce@momjian.us 995 : 3 : last = queue_size - 1;
3854 rhaas@postgresql.org 996 [ + + ]: 10 : for (i = queue_size - 1; i >= 0;)
997 : : {
998 : : int c;
999 : 7 : int nmatches = 0;
1000 : :
1001 : : /* Find next candidate to output */
9345 tgl@sss.pgh.pa.us 1002 [ - + ]: 7 : while (topoProcs[last] == NULL)
9345 tgl@sss.pgh.pa.us 1003 :UBC 0 : last--;
9345 tgl@sss.pgh.pa.us 1004 [ + - ]:CBC 14 : for (j = last; j >= 0; j--)
1005 : : {
1006 [ + + + + ]: 14 : if (topoProcs[j] != NULL && beforeConstraints[j] == 0)
1007 : 7 : break;
1008 : : }
1009 : :
1010 : : /* If no available candidate, topological sort fails */
1011 [ - + ]: 7 : if (j < 0)
9345 tgl@sss.pgh.pa.us 1012 :UBC 0 : return false;
1013 : :
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 : : */
3854 rhaas@postgresql.org 1023 :CBC 7 : proc = topoProcs[j];
1024 [ + + ]: 7 : if (proc->lockGroupLeader != NULL)
1025 : 2 : proc = proc->lockGroupLeader;
1026 [ - + ]: 7 : Assert(proc != NULL);
1027 [ + + ]: 28 : for (c = 0; c <= last; ++c)
1028 : : {
1029 [ + + + + ]: 21 : if (topoProcs[c] == proc || (topoProcs[c] != NULL &&
3354 tgl@sss.pgh.pa.us 1030 [ + + ]: 11 : topoProcs[c]->lockGroupLeader == proc))
1031 : : {
3854 rhaas@postgresql.org 1032 : 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 */
9289 bruce@momjian.us 1041 [ + + ]: 10 : for (k = afterConstraints[j]; k > 0; k = constraints[k - 1].link)
1042 : 3 : beforeConstraints[constraints[k - 1].pred]--;
1043 : : }
1044 : :
1045 : : /* Done */
9345 tgl@sss.pgh.pa.us 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 : :
1056 : : printf("%s lock %p queue ", info, lock);
1057 : :
1058 : : dclist_foreach(proc_iter, waitQueue)
1059 : : {
1060 : : PGPROC *proc = dlist_container(PGPROC, waitLink, 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
8624 1073 : 6 : DeadLockReport(void)
1074 : : {
1075 : : StringInfoData clientbuf; /* errdetail for client */
1076 : : StringInfoData logbuf; /* errdetail for server log */
1077 : : StringInfoData locktagbuf;
1078 : : int i;
1079 : :
6730 1080 : 6 : initStringInfo(&clientbuf);
1081 : 6 : initStringInfo(&logbuf);
6733 1082 : 6 : initStringInfo(&locktagbuf);
1083 : :
1084 : : /* Generate the "waits for" lines sent to the client */
8624 1085 [ + + ]: 25 : for (i = 0; i < nDeadlockDetails; i++)
1086 : : {
8424 bruce@momjian.us 1087 : 19 : DEADLOCK_INFO *info = &deadlockDetails[i];
1088 : : int nextpid;
1089 : :
1090 : : /* The last proc waits for the first one... */
1091 [ + + ]: 19 : if (i < nDeadlockDetails - 1)
8624 tgl@sss.pgh.pa.us 1092 : 13 : nextpid = info[1].pid;
1093 : : else
1094 : 6 : nextpid = deadlockDetails[0].pid;
1095 : :
1096 : : /* reset locktagbuf to hold next object description */
6733 1097 : 19 : resetStringInfo(&locktagbuf);
1098 : :
1099 : 19 : DescribeLockTag(&locktagbuf, &info->locktag);
1100 : :
1101 [ + + ]: 19 : if (i > 0)
6730 1102 : 13 : appendStringInfoChar(&clientbuf, '\n');
1103 : :
1104 : 38 : appendStringInfo(&clientbuf,
3354 1105 : 19 : _("Process %d waits for %s on %s; blocked by process %d."),
1106 : : info->pid,
7566 1107 : 19 : GetLockmodeName(info->locktag.locktag_lockmethodid,
1108 : : info->lockmode),
1109 : : locktagbuf.data,
1110 : : nextpid);
1111 : : }
1112 : :
1113 : : /* Duplicate all the above for the server ... */
2592 drowley@postgresql.o 1114 : 6 : appendBinaryStringInfo(&logbuf, clientbuf.data, clientbuf.len);
1115 : :
1116 : : /* ... and add info about query strings */
6730 tgl@sss.pgh.pa.us 1117 [ + + ]: 25 : for (i = 0; i < nDeadlockDetails; i++)
1118 : : {
1119 : 19 : DEADLOCK_INFO *info = &deadlockDetails[i];
1120 : :
1121 : 19 : appendStringInfoChar(&logbuf, '\n');
1122 : :
1123 : 19 : appendStringInfo(&logbuf,
6733 1124 : 19 : _("Process %d: %s"),
1125 : : info->pid,
1126 : : pgstat_get_backend_current_activity(info->pid, false));
1127 : : }
1128 : :
5327 magnus@hagander.net 1129 : 6 : pgstat_report_deadlock();
1130 : :
8435 tgl@sss.pgh.pa.us 1131 [ + - ]: 6 : ereport(ERROR,
1132 : : (errcode(ERRCODE_T_R_DEADLOCK_DETECTED),
1133 : : 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
8624 1145 : 1 : RememberSimpleDeadLock(PGPROC *proc1,
1146 : : LOCKMODE lockmode,
1147 : : LOCK *lock,
1148 : : PGPROC *proc2)
1149 : : {
8424 bruce@momjian.us 1150 : 1 : DEADLOCK_INFO *info = &deadlockDetails[0];
1151 : :
8624 tgl@sss.pgh.pa.us 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 : }
|
