deadlock Namespace Reference

Classes
class	Deadlock
class	DiGraph
class	MutexType

Functions
def	strongly_connected_components (G)
def	simple_cycles (G)
def	find_cycle (graph)
def	get_stacktrace (thread_id)
def	is_thread_blocked_with_frame (thread_id, top_line, expected_top_line, expected_frame)
def	print_cycle (graph, lwp_to_thread_id, cycle)
def	get_thread_info ()
def	get_pthread_mutex_t_owner_and_address (lwp_to_thread_id, thread_lwp)
def	get_pthread_rwlock_t_owner_and_address (lwp_to_thread_id, thread_lwp)
def	load ()
def	info ()

Function Documentation

def deadlock.find_cycle

(

graph

)

Looks for a cycle in the graph. If found, returns the first cycle.
If nodes a1, a2, ..., an are in a cycle, then this returns:
    [(a1,a2), (a2,a3), ... (an-1,an), (an, a1)]
Otherwise returns an empty list.

Definition at line 213 of file deadlock.py.

References bm.list, and simple_cycles().

Referenced by deadlock.Deadlock.invoke().

def find_cycle(graph):
    '''
    Looks for a cycle in the graph. If found, returns the first cycle.
    If nodes a1, a2, ..., an are in a cycle, then this returns:
        [(a1,a2), (a2,a3), ... (an-1,an), (an, a1)]
    Otherwise returns an empty list.
    '''
    cycles = list(simple_cycles(graph))
    if cycles:
        nodes = cycles[0]
        nodes.append(nodes[0])
        edges = []
        prev = nodes[0]
        for node in nodes[1:]:
            edges.append((prev, node))
            prev = node
        return edges
    else:
        return []

def deadlock.get_pthread_mutex_t_owner_and_address	(		lwp_to_thread_id,
			thread_lwp
	)

Finds the thread holding the mutex that this thread is blocked on.
Returns a pair of (lwp of thread owning mutex, mutex address),
or (None, None) if not found.

Definition at line 342 of file deadlock.py.

References folly::gen.dereference.

def get_pthread_mutex_t_owner_and_address(lwp_to_thread_id, thread_lwp):
    '''
    Finds the thread holding the mutex that this thread is blocked on.
    Returns a pair of (lwp of thread owning mutex, mutex address),
    or (None, None) if not found.
    '''
    # Go up the stack to the pthread_mutex_lock frame
    gdb.execute(
        'thread %d' % lwp_to_thread_id[thread_lwp],
        from_tty=False,
        to_string=True
    )
    gdb.execute('frame 1', from_tty=False, to_string=True)

    # Get the owner of the mutex by inspecting the internal
    # fields of the mutex.
    try:
        mutex_info = gdb.parse_and_eval('mutex').dereference()
        mutex_owner_lwp = int(mutex_info['__data']['__owner'])
        return (mutex_owner_lwp, int(mutex_info.address))
    except gdb.error:
        return (None, None)

def deadlock.get_pthread_rwlock_t_owner_and_address	(		lwp_to_thread_id,
			thread_lwp
	)

If the thread is waiting on a write-locked pthread_rwlock_t, this will
return the pair of:
    (lwp of thread that is write-owning the mutex, mutex address)
or (None, None) if not found, or if the mutex is read-locked.

Definition at line 366 of file deadlock.py.

References folly::gen.dereference.

def get_pthread_rwlock_t_owner_and_address(lwp_to_thread_id, thread_lwp):
    '''
    If the thread is waiting on a write-locked pthread_rwlock_t, this will
    return the pair of:
        (lwp of thread that is write-owning the mutex, mutex address)
    or (None, None) if not found, or if the mutex is read-locked.
    '''
    # Go up the stack to the pthread_rwlock_{rd|wr}lock frame
    gdb.execute(
        'thread %d' % lwp_to_thread_id[thread_lwp],
        from_tty=False,
        to_string=True
    )
    gdb.execute('frame 2', from_tty=False, to_string=True)

    # Get the owner of the mutex by inspecting the internal
    # fields of the mutex.
    try:
        rwlock_info = gdb.parse_and_eval('rwlock').dereference()
        rwlock_owner_lwp = int(rwlock_info['__data']['__writer'])
        # We can only track the owner if it is currently write-locked.
        # If it is not write-locked or if it is currently read-locked,
        # possibly by multiple threads, we cannot find the owner.
        if rwlock_owner_lwp != 0:
            return (rwlock_owner_lwp, int(rwlock_info.address))
        else:
            return (None, None)
    except gdb.error:
        return (None, None)

def deadlock.get_stacktrace

(

thread_id

)

Returns the stack trace for the thread id as a list of strings.

Definition at line 234 of file deadlock.py.

References is_thread_blocked_with_frame(), and folly::gen.split().

Referenced by is_thread_blocked_with_frame().

def get_stacktrace(thread_id):
    '''
    Returns the stack trace for the thread id as a list of strings.
    '''
    gdb.execute('thread %d' % thread_id, from_tty=False, to_string=True)
    output = gdb.execute('bt', from_tty=False, to_string=True)
    stacktrace_lines = output.strip().split('\n')
    return stacktrace_lines

def deadlock.get_thread_info

(

)

Returns a pair of:
- map of LWP -> thread ID
- map of blocked threads LWP -> potential mutex type

Definition at line 313 of file deadlock.py.

References group, and folly::gen.split().

Referenced by deadlock.Deadlock.invoke().

def get_thread_info():
    '''
    Returns a pair of:
    - map of LWP -> thread ID
    - map of blocked threads LWP -> potential mutex type
    '''
    # LWP -> thread ID
    lwp_to_thread_id = {}

    # LWP -> potential mutex type it is blocked on
    blocked_threads = {}

    output = gdb.execute('info threads', from_tty=False, to_string=True)
    lines = output.strip().split('\n')[1:]
    regex = re.compile(r'[\s\*]*(\d+).*Thread.*\(LWP (\d+)\).*')
    for line in lines:
        try:
            thread_id = int(regex.match(line).group(1))
            thread_lwp = int(regex.match(line).group(2))
            lwp_to_thread_id[thread_lwp] = thread_id
            mutex_type = MutexType.get_mutex_type(thread_id, line)
            if mutex_type:
                blocked_threads[thread_lwp] = mutex_type
        except Exception:
            continue

    return (lwp_to_thread_id, blocked_threads)

def deadlock.info

(

)

Definition at line 447 of file deadlock.py.

References load().

Referenced by folly::NestedCommandLineApp.addCommand(), fizz::KeyDerivationImpl< Hash >.blankHash(), folly::EventBaseManager.clearEventBase(), folly::IOBuf.cloneOneAsValue(), fizz::server::AeadTokenCipher< AeadType, HkdfType >.createAead(), folly::IOBuf.decrementRefcount(), folly::AsyncServerSocket.dispatchError(), folly::AsyncServerSocket.dispatchSocket(), folly::NestedCommandLineApp.displayHelp(), folly::NestedCommandLineApp.doRun(), dummy(), duration_to_ts(), folly::IOBuf.freeExtBuffer(), folly::exception_tracer.getCurrentExceptions(), folly::EventBaseManager.getEventBase(), folly::EventBaseManager.getExistingEventBase(), wangle::FilePoller.getFileModData(), folly::IOBuf.IOBuf(), folly.logLevelToString(), folly::IOBuf.markExternallySharedOne(), folly::AsyncServerSocket.nextCallback(), folly::exception_tracer.operator<<(), folly::IOBuf.packFlagsAndSharedInfo(), folly::fibers::StackCache.protectedPages(), folly::Subprocess.readChildErrorPipe(), folly::AsyncServerSocket.removeAcceptCallback(), folly::IOBuf.reserveSlow(), folly::EventBaseManager.setEventBase(), folly::IOBuf.setSharedInfo(), folly.stringToLogLevel(), TEST(), TEST_F(), and fizz::test.TEST_P().

def info():
    return 'Detect deadlocks'

def deadlock.is_thread_blocked_with_frame	(		thread_id,
			top_line,
			expected_top_line,
			expected_frame
	)

Returns True if we found expected_top_line in top_line, and
we found the expected_frame in the thread's stack trace.

Definition at line 246 of file deadlock.py.

References folly::gen.any(), and get_stacktrace().

Referenced by deadlock.MutexType.get_mutex_type(), and get_stacktrace().

):
    '''
    Returns True if we found expected_top_line in top_line, and
    we found the expected_frame in the thread's stack trace.
    '''
    if expected_top_line not in top_line:
        return False
    stacktrace_lines = get_stacktrace(thread_id)
    return any(expected_frame in line for line in stacktrace_lines)

def deadlock.load

(

)

Definition at line 441 of file deadlock.py.

Referenced by folly::SharedMutexImpl< true >.applyDeferredReaders(), folly::AtomicHashMap< int64_t, int64_t >.begin(), folly::Bits< T, Traits >.count(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >.erase(), non_atomic< T >.exchange(), folly::PicoSpinLock< uintptr_t >.getData(), info(), folly::Bits< T, Traits >.innerGet(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >.insertInternal(), folly::MicroSpinLock.lock(), non_atomic< T >.operator T(), non_atomic< T >.operator+=(), runMultiBitTest64(), runMultiBitTest8(), runSignedMultiBitTest8(), runSimpleTest64(), runSimpleTest8(), folly::Bits< T, Traits >.test(), folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::Buckets.unlink_and_reclaim_nodes(), folly::MicroSpinLock.unlock(), and folly::detail::ThreadCachedInts< Tag >::Integer.~Integer().

def load():
    # instantiate the Deadlock command
    Deadlock()
    print('Type "deadlock" to detect deadlocks.')

def deadlock.print_cycle	(		graph,
			lwp_to_thread_id,
			cycle
	)

Prints the threads and mutexes involved in the deadlock.

Definition at line 300 of file deadlock.py.

Referenced by deadlock.Deadlock.invoke().

def print_cycle(graph, lwp_to_thread_id, cycle):
    '''Prints the threads and mutexes involved in the deadlock.'''
    for (m, n) in cycle:
        print(
            'Thread %d (LWP %d) is waiting on %s (0x%016x) held by '
            'Thread %d (LWP %d)' % (
                lwp_to_thread_id[m], m,
                graph.attributes(m, n)['mutex_type'].value,
                graph.attributes(m, n)['mutex'], lwp_to_thread_id[n], n
            )
        )

def deadlock.simple_cycles

(

G

)

Adapted from networkx: http://networkx.github.io/
Parameters
----------
G : DiGraph
Returns
-------
cycle_generator: generator
   A generator that produces elementary cycles of the graph.
   Each cycle is represented by a list of nodes along the cycle.

Definition at line 143 of file deadlock.py.

References add, bm.list, and strongly_connected_components().

Referenced by find_cycle().

def simple_cycles(G):  # noqa: C901
    '''
    Adapted from networkx: http://networkx.github.io/
    Parameters
    ----------
    G : DiGraph
    Returns
    -------
    cycle_generator: generator
       A generator that produces elementary cycles of the graph.
       Each cycle is represented by a list of nodes along the cycle.
    '''

    def _unblock(thisnode, blocked, B):
        stack = set([thisnode])
        while stack:
            node = stack.pop()
            if node in blocked:
                blocked.remove(node)
                stack.update(B[node])
                B[node].clear()

    # Johnson's algorithm requires some ordering of the nodes.
    # We assign the arbitrary ordering given by the strongly connected comps
    # There is no need to track the ordering as each node removed as processed.
    # save the actual graph so we can mutate it here
    # We only take the edges because we do not want to
    # copy edge and node attributes here.
    subG = G.subgraph(G.nodes())
    sccs = list(strongly_connected_components(subG))
    while sccs:
        scc = sccs.pop()
        # order of scc determines ordering of nodes
        startnode = scc.pop()
        # Processing node runs 'circuit' routine from recursive version
        path = [startnode]
        blocked = set()  # vertex: blocked from search?
        closed = set()  # nodes involved in a cycle
        blocked.add(startnode)
        B = defaultdict(set)  # graph portions that yield no elementary circuit
        stack = [(startnode, list(subG.neighbors(startnode)))]
        while stack:
            thisnode, nbrs = stack[-1]
            if nbrs:
                nextnode = nbrs.pop()
                if nextnode == startnode:
                    yield path[:]
                    closed.update(path)
                elif nextnode not in blocked:
                    path.append(nextnode)
                    stack.append((nextnode, list(subG.neighbors(nextnode))))
                    closed.discard(nextnode)
                    blocked.add(nextnode)
                    continue
            # done with nextnode... look for more neighbors
            if not nbrs:  # no more nbrs
                if thisnode in closed:
                    _unblock(thisnode, blocked, B)
                else:
                    for nbr in subG.neighbors(thisnode):
                        if thisnode not in B[nbr]:
                            B[nbr].add(thisnode)
                stack.pop()
                path.pop()
        # done processing this node
        subG.remove_node(startnode)
        H = subG.subgraph(scc)  # make smaller to avoid work in SCC routine
        sccs.extend(list(strongly_connected_components(H)))

def deadlock.strongly_connected_components

(

G

)

Adapted from networkx: http://networkx.github.io/
Parameters
----------
G : DiGraph
Returns
-------
comp : generator of sets
    A generator of sets of nodes, one for each strongly connected
    component of G.

Definition at line 88 of file deadlock.py.

References min.

Referenced by simple_cycles().

def strongly_connected_components(G):  # noqa: C901
    '''
    Adapted from networkx: http://networkx.github.io/
    Parameters
    ----------
    G : DiGraph
    Returns
    -------
    comp : generator of sets
        A generator of sets of nodes, one for each strongly connected
        component of G.
    '''
    preorder = {}
    lowlink = {}
    scc_found = {}
    scc_queue = []
    i = 0  # Preorder counter
    for source in G.nodes():
        if source not in scc_found:
            queue = [source]
            while queue:
                v = queue[-1]
                if v not in preorder:
                    i = i + 1
                    preorder[v] = i
                done = 1
                v_nbrs = G.neighbors(v)
                for w in v_nbrs:
                    if w not in preorder:
                        queue.append(w)
                        done = 0
                        break
                if done == 1:
                    lowlink[v] = preorder[v]
                    for w in v_nbrs:
                        if w not in scc_found:
                            if preorder[w] > preorder[v]:
                                lowlink[v] = min([lowlink[v], lowlink[w]])
                            else:
                                lowlink[v] = min([lowlink[v], preorder[w]])
                    queue.pop()
                    if lowlink[v] == preorder[v]:
                        scc_found[v] = True
                        scc = {v}
                        while (
                            scc_queue and preorder[scc_queue[-1]] > preorder[v]
                        ):
                            k = scc_queue.pop()
                            scc_found[k] = True
                            scc.add(k)
                        yield scc
                    else:
                        scc_queue.append(v)