3 from collections import defaultdict
10 Adapted from networkx: http://networkx.github.io/
11 Represents a directed graph. Edges can store (key, value) attributes.
15 # Map of node -> set of nodes
16 self.adjacency_map = {}
17 # Map of (node1, node2) -> map string -> arbitrary attribute
18 # This will not be copied in subgraph()
19 self.attributes_map = {}
21 def neighbors(self, node):
22 return self.adjacency_map.get(node, set())
26 for node, neighbors in self.adjacency_map.items():
27 for neighbor in neighbors:
28 edges.append((node, neighbor))
32 return self.adjacency_map.keys()
34 def attributes(self, node1, node2):
35 return self.attributes_map[(node1, node2)]
37 def add_edge(self, node1, node2, **kwargs):
38 if node1 not in self.adjacency_map:
39 self.adjacency_map[node1] = set()
40 if node2 not in self.adjacency_map:
41 self.adjacency_map[node2] = set()
42 self.adjacency_map[node1].add(node2)
43 self.attributes_map[(node1, node2)] = kwargs
45 def remove_node(self, node):
46 self.adjacency_map.pop(node, None)
47 for _, neighbors in self.adjacency_map.items():
48 neighbors.discard(node)
50 def subgraph(self, nodes):
53 for neighbor in self.neighbors(node):
55 graph.add_edge(node, neighbor)
58 def node_link_data(self):
60 Returns the graph as a dictionary in a format that can be
71 # Do one pass to build a map of node -> position in nodes
73 for node in self.adjacency_map.keys():
74 node_to_number[node] = len(data['nodes'])
75 data['nodes'].append({'id': node})
77 # Do another pass to build the link information
78 for node, neighbors in self.adjacency_map.items():
79 for neighbor in neighbors:
80 link = self.attributes_map[(node, neighbor)].copy()
81 link['source'] = node_to_number[node]
82 link['target'] = node_to_number[neighbor]
83 data['links'].append(link)
87 def strongly_connected_components(G): # noqa: C901
89 Adapted from networkx: http://networkx.github.io/
95 comp : generator of sets
96 A generator of sets of nodes, one for each strongly connected
103 i = 0 # Preorder counter
104 for source in G.nodes():
105 if source not in scc_found:
109 if v not in preorder:
113 v_nbrs = G.neighbors(v)
115 if w not in preorder:
120 lowlink[v] = preorder[v]
122 if w not in scc_found:
123 if preorder[w] > preorder[v]:
124 lowlink[v] = min([lowlink[v], lowlink[w]])
126 lowlink[v] = min([lowlink[v], preorder[w]])
128 if lowlink[v] == preorder[v]:
132 scc_queue and preorder[scc_queue[-1]] > preorder[v]
142 def simple_cycles(G): # noqa: C901
144 Adapted from networkx: http://networkx.github.io/
150 cycle_generator: generator
151 A generator that produces elementary cycles of the graph.
152 Each cycle is represented by a list of nodes along the cycle.
155 def _unblock(thisnode, blocked, B):
156 stack = set([thisnode])
161 stack.update(B[node])
164 # Johnson's algorithm requires some ordering of the nodes.
165 # We assign the arbitrary ordering given by the strongly connected comps
166 # There is no need to track the ordering as each node removed as processed.
167 # save the actual graph so we can mutate it here
168 # We only take the edges because we do not want to
169 # copy edge and node attributes here.
170 subG = G.subgraph(G.nodes())
171 sccs = list(strongly_connected_components(subG))
174 # order of scc determines ordering of nodes
175 startnode = scc.pop()
176 # Processing node runs 'circuit' routine from recursive version
178 blocked = set() # vertex: blocked from search?
179 closed = set() # nodes involved in a cycle
180 blocked.add(startnode)
181 B = defaultdict(set) # graph portions that yield no elementary circuit
182 stack = [(startnode, list(subG.neighbors(startnode)))]
184 thisnode, nbrs = stack[-1]
186 nextnode = nbrs.pop()
187 if nextnode == startnode:
190 elif nextnode not in blocked:
191 path.append(nextnode)
192 stack.append((nextnode, list(subG.neighbors(nextnode))))
193 closed.discard(nextnode)
194 blocked.add(nextnode)
196 # done with nextnode... look for more neighbors
197 if not nbrs: # no more nbrs
198 if thisnode in closed:
199 _unblock(thisnode, blocked, B)
201 for nbr in subG.neighbors(thisnode):
202 if thisnode not in B[nbr]:
206 # done processing this node
207 subG.remove_node(startnode)
208 H = subG.subgraph(scc) # make smaller to avoid work in SCC routine
209 sccs.extend(list(strongly_connected_components(H)))
212 def find_cycle(graph):
214 Looks for a cycle in the graph. If found, returns the first cycle.
215 If nodes a1, a2, ..., an are in a cycle, then this returns:
216 [(a1,a2), (a2,a3), ... (an-1,an), (an, a1)]
217 Otherwise returns an empty list.
219 cycles = list(simple_cycles(graph))
222 nodes.append(nodes[0])
225 for node in nodes[1:]:
226 edges.append((prev, node))
233 def print_cycle(graph, lwp_to_thread_id, cycle):
234 '''Prints the threads and mutexes involved in the deadlock.'''
237 'Thread %d (LWP %d) is waiting on mutex (0x%016x) held by '
238 'Thread %d (LWP %d)' % (
239 lwp_to_thread_id[m], m, graph.attributes(m, n)['mutex'],
240 lwp_to_thread_id[n], n
245 def get_thread_info():
248 - map of LWP -> thread ID
249 - set of blocked threads LWP
252 lwp_to_thread_id = {}
254 # Set of threads blocked on mutexes
255 blocked_threads = set()
257 output = gdb.execute('info threads', from_tty=False, to_string=True)
258 lines = output.strip().split('\n')[1:]
259 regex = re.compile(r'[\s\*]*(\d+).*Thread.*\(LWP (\d+)\).*')
261 thread_id = int(regex.match(line).group(1))
262 thread_lwp = int(regex.match(line).group(2))
263 lwp_to_thread_id[thread_lwp] = thread_id
264 if '__lll_lock_wait' in line:
265 blocked_threads.add(thread_lwp)
267 return (lwp_to_thread_id, blocked_threads)
270 def get_mutex_owner_and_address(lwp_to_thread_id, thread_lwp):
272 Finds the thread holding the mutex that this thread is blocked on.
273 Returns a pair of (lwp of thread owning mutex, mutex address),
274 or (None, None) if not found.
276 # Go up the stack to the pthread_mutex_lock frame
278 'thread %d' % lwp_to_thread_id[thread_lwp],
282 gdb.execute('frame 1', from_tty=False, to_string=True)
284 # Get the owner of the mutex by inspecting the internal
285 # fields of the mutex.
287 mutex_info = gdb.parse_and_eval('mutex').dereference()
288 mutex_owner_lwp = int(mutex_info['__data']['__owner'])
289 return (mutex_owner_lwp, int(mutex_info.address))
294 class Deadlock(gdb.Command):
295 '''Detects deadlocks'''
298 super(Deadlock, self).__init__('deadlock', gdb.COMMAND_NONE)
300 def invoke(self, arg, from_tty):
301 '''Prints the threads and mutexes in a deadlock, if it exists.'''
302 lwp_to_thread_id, blocked_threads = get_thread_info()
304 # Nodes represent threads. Edge (A,B) exists if thread A
305 # is waiting on a mutex held by thread B.
308 # Go through all the blocked threads and see which threads
309 # they are blocked on, and build the thread wait graph.
310 for thread_lwp in blocked_threads:
311 mutex_owner_lwp, mutex_address = get_mutex_owner_and_address(
312 lwp_to_thread_id, thread_lwp
314 if mutex_owner_lwp and mutex_address:
315 graph.add_edge(thread_lwp, mutex_owner_lwp,
318 # A deadlock exists if there is a cycle in the graph.
319 cycle = find_cycle(graph)
321 print('Found deadlock!')
322 print_cycle(graph, lwp_to_thread_id, cycle)
325 'No deadlock detected. '
326 'Do you have debug symbols installed?'
331 # instantiate the Deadlock command
333 print('Type "deadlock" to detect deadlocks.')
337 return 'Detect deadlocks'
340 if __name__ == '__main__':