folly/experimental/gdb/deadlock.py

   1 #!/usr/bin/env python3
   2
   3 from collections import defaultdict
   4 import gdb
   5 import re
   6
   7
   8 class DiGraph(object):
   9     '''
  10     Adapted from networkx: http://networkx.github.io/
  11     Represents a directed graph. Edges can store (key, value) attributes.
  12     '''
  13
  14     def __init__(self):
  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 = {}
  20
  21     def neighbors(self, node):
  22         return self.adjacency_map.get(node, set())
  23
  24     def edges(self):
  25         edges = []
  26         for node, neighbors in self.adjacency_map.items():
  27             for neighbor in neighbors:
  28                 edges.append((node, neighbor))
  29         return edges
  30
  31     def nodes(self):
  32         return self.adjacency_map.keys()
  33
  34     def attributes(self, node1, node2):
  35         return self.attributes_map[(node1, node2)]
  36
  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
  44
  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)
  49
  50     def subgraph(self, nodes):
  51         graph = DiGraph()
  52         for node in nodes:
  53             for neighbor in self.neighbors(node):
  54                 if neighbor in nodes:
  55                     graph.add_edge(node, neighbor)
  56         return graph
  57
  58     def node_link_data(self):
  59         '''
  60         Returns the graph as a dictionary in a format that can be
  61         serialized.
  62         '''
  63         data = {
  64             'directed': True,
  65             'multigraph': False,
  66             'graph': {},
  67             'links': [],
  68             'nodes': [],
  69         }
  70
  71         # Do one pass to build a map of node -> position in nodes
  72         node_to_number = {}
  73         for node in self.adjacency_map.keys():
  74             node_to_number[node] = len(data['nodes'])
  75             data['nodes'].append({'id': node})
  76
  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)
  84         return data
  85
  86
  87 def strongly_connected_components(G):  # noqa: C901
  88     '''
  89     Adapted from networkx: http://networkx.github.io/
  90     Parameters
  91     ----------
  92     G : DiGraph
  93     Returns
  94     -------
  95     comp : generator of sets
  96         A generator of sets of nodes, one for each strongly connected
  97         component of G.
  98     '''
  99     preorder = {}
 100     lowlink = {}
 101     scc_found = {}
 102     scc_queue = []
 103     i = 0  # Preorder counter
 104     for source in G.nodes():
 105         if source not in scc_found:
 106             queue = [source]
 107             while queue:
 108                 v = queue[-1]
 109                 if v not in preorder:
 110                     i = i + 1
 111                     preorder[v] = i
 112                 done = 1
 113                 v_nbrs = G.neighbors(v)
 114                 for w in v_nbrs:
 115                     if w not in preorder:
 116                         queue.append(w)
 117                         done = 0
 118                         break
 119                 if done == 1:
 120                     lowlink[v] = preorder[v]
 121                     for w in v_nbrs:
 122                         if w not in scc_found:
 123                             if preorder[w] > preorder[v]:
 124                                 lowlink[v] = min([lowlink[v], lowlink[w]])
 125                             else:
 126                                 lowlink[v] = min([lowlink[v], preorder[w]])
 127                     queue.pop()
 128                     if lowlink[v] == preorder[v]:
 129                         scc_found[v] = True
 130                         scc = {v}
 131                         while (
 132                             scc_queue and preorder[scc_queue[-1]] > preorder[v]
 133                         ):
 134                             k = scc_queue.pop()
 135                             scc_found[k] = True
 136                             scc.add(k)
 137                         yield scc
 138                     else:
 139                         scc_queue.append(v)
 140
 141
 142 def simple_cycles(G):  # noqa: C901
 143     '''
 144     Adapted from networkx: http://networkx.github.io/
 145     Parameters
 146     ----------
 147     G : DiGraph
 148     Returns
 149     -------
 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.
 153     '''
 154
 155     def _unblock(thisnode, blocked, B):
 156         stack = set([thisnode])
 157         while stack:
 158             node = stack.pop()
 159             if node in blocked:
 160                 blocked.remove(node)
 161                 stack.update(B[node])
 162                 B[node].clear()
 163
 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))
 172     while sccs:
 173         scc = sccs.pop()
 174         # order of scc determines ordering of nodes
 175         startnode = scc.pop()
 176         # Processing node runs 'circuit' routine from recursive version
 177         path = [startnode]
 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)))]
 183         while stack:
 184             thisnode, nbrs = stack[-1]
 185             if nbrs:
 186                 nextnode = nbrs.pop()
 187                 if nextnode == startnode:
 188                     yield path[:]
 189                     closed.update(path)
 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)
 195                     continue
 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)
 200                 else:
 201                     for nbr in subG.neighbors(thisnode):
 202                         if thisnode not in B[nbr]:
 203                             B[nbr].add(thisnode)
 204                 stack.pop()
 205                 path.pop()
 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)))
 210
 211
 212 def find_cycle(graph):
 213     '''
 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.
 218     '''
 219     cycles = list(simple_cycles(graph))
 220     if cycles:
 221         nodes = cycles[0]
 222         nodes.append(nodes[0])
 223         edges = []
 224         prev = nodes[0]
 225         for node in nodes[1:]:
 226             edges.append((prev, node))
 227             prev = node
 228         return edges
 229     else:
 230         return []
 231
 232
 233 def print_cycle(graph, lwp_to_thread_id, cycle):
 234     '''Prints the threads and mutexes involved in the deadlock.'''
 235     for (m, n) in cycle:
 236         print(
 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
 241             )
 242         )
 243
 244
 245 def get_thread_info():
 246     '''
 247     Returns a pair of:
 248     - map of LWP -> thread ID
 249     - set of blocked threads LWP
 250     '''
 251     # LWP -> thread ID
 252     lwp_to_thread_id = {}
 253
 254     # Set of threads blocked on mutexes
 255     blocked_threads = set()
 256
 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+)\).*')
 260     for line in lines:
 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)
 266
 267     return (lwp_to_thread_id, blocked_threads)
 268
 269
 270 def get_mutex_owner_and_address(lwp_to_thread_id, thread_lwp):
 271     '''
 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.
 275     '''
 276     # Go up the stack to the pthread_mutex_lock frame
 277     gdb.execute(
 278         'thread %d' % lwp_to_thread_id[thread_lwp],
 279         from_tty=False,
 280         to_string=True
 281     )
 282     gdb.execute('frame 1', from_tty=False, to_string=True)
 283
 284     # Get the owner of the mutex by inspecting the internal
 285     # fields of the mutex.
 286     try:
 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))
 290     except gdb.error:
 291         return (None, None)
 292
 293
 294 class Deadlock(gdb.Command):
 295     '''Detects deadlocks'''
 296
 297     def __init__(self):
 298         super(Deadlock, self).__init__('deadlock', gdb.COMMAND_NONE)
 299
 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()
 303
 304         # Nodes represent threads. Edge (A,B) exists if thread A
 305         # is waiting on a mutex held by thread B.
 306         graph = DiGraph()
 307
 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
 313             )
 314             if mutex_owner_lwp and mutex_address:
 315                 graph.add_edge(thread_lwp, mutex_owner_lwp,
 316                                mutex=mutex_address)
 317
 318         # A deadlock exists if there is a cycle in the graph.
 319         cycle = find_cycle(graph)
 320         if cycle:
 321             print('Found deadlock!')
 322             print_cycle(graph, lwp_to_thread_id, cycle)
 323         else:
 324             print(
 325                 'No deadlock detected. '
 326                 'Do you have debug symbols installed?'
 327             )
 328
 329
 330 def load():
 331     # instantiate the Deadlock command
 332     Deadlock()
 333     print('Type "deadlock" to detect deadlocks.')
 334
 335
 336 def info():
 337     return 'Detect deadlocks'
 338
 339
 340 if __name__ == '__main__':
 341     load()