Attachment 156240 Details for Bug 241780 – new autofs_analyze

new autofs_analyze

autofs_analyze (text/plain), 4.40 KB, created by Anders Blomdell on 2007-06-05 16:31:34 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Anders Blomdell

Created: 2007-06-05 16:31:34 UTC

Size: 4.40 KB

patch

obsolete

>#!/usr/bin/python
>
>import sets
>import sys
>import re
>
>class Chain(object):
>    def __init__(self, thread, chain):
>        self.thread = thread
>        self.chain = chain
>        self.desc = []
>
>    def add_desc(self, desc):
>        self.desc.append(desc)
>
>    def __repr__(self):
>        return "(%s)" % "|".join(self.chain)
>        
>class Thread(object):
>    def __init__(self, id):
>        self.id = id
>        self.chain = []
>
>    def add(self, chain):
>        c = Chain(self, chain)
>        self.chain.append(c)
>        return c
>
>    def __repr__(self):
>        result = "Thread(%s)" % self.id
>        return result
>    
>
>def extract(f):
>    # Get all unique lock sequences
>    result = {}
>    unique = {}
>    description = {}
>    chain = None
>    thread = None
>    for l in f:
>        if not l.startswith('#'):
>            # Strip newline, spaces and trailing |
>            l = l.strip().replace(' ', '')[0:-1] 
>            try:
>                unique[l] += 1
>                thread = None
>                chain = None
>            except:
>                unique[l] = 1
>                m = re.match("([^:]+):(.*)", l)
>                t_id = m.group(1)
>                lock_id = m.group(2).split('|')
>                if len(lock_id) == 1:
>                    # Lock chains of length 1 can't deadlock
>                    continue
>                try:
>                    thread = result[t_id]
>                except:
>                    result[t_id] = Thread(t_id)
>                    thread = result[t_id]
>                chain = thread.add(lock_id)
>
>        elif chain:
>            chain.add_desc(l[1:].strip().split('|'))
>
>    return result.values()
>
>def need_join(a, b):
>    if not a[-1] in b[1:]:
>        # Since last element of a not in b, no deadlock can occur
>        return False
>    while len(a) and len(b) and a[-1] == b[-1]:
>        # Remove common tails
>        a = a[0:-1]
>        b = b[0:-1]
>    if not sets.Set(a) & sets.Set(b):
>        # Union of prefixes are empty
>        return False
>    
>    result = False
>    expect = 0
>    for x in a:
>        try:
>            if b.index(x) < expect:
>                # Locking in reverse order, deadlock will occur!
>                result = True
>            expect = b.index(x) + 1
>        except:
>            # Deadlock might occur, will be checked after join
>            result = True
>    return result
>    
>def do_join2(all_threads, mutex, thread, seq):
>    for m in mutex:
>        if mutex.count(m) > 1:
>            # Deadlock!!
>            return [(mutex, seq)]
>    
>    # Traverse threads not already joined
>    result = []
>    for t in [x for x in all_threads if not x in thread]:
>        for c in t.chain:
>            if need_join(mutex, c.chain):
>                # Add all resources possibly held by other thread to result
>                chain = mutex + c.chain[0:c.chain.index(mutex[-1])]
>                result.extend(do_join2(all_threads, chain,
>                                       thread + [t], seq + [c]))
>    return result
>            
>def do_join(all_threads):
>    seen = {}
>    result = []
>    for t in all_threads:
>        for c in t.chain:
>            for mutex,seq in do_join2(all_threads, c.chain, [t], [c]):
>                try:
>                    seen[tuple(mutex)] += 1
>                except:
>                    seen[tuple(mutex)] = 1
>                    result.append((mutex,seq))
>                
>    return result
>            
>if __name__ == "__main__":
>    all_threads = extract(open(sys.argv[1]))
>    possible = do_join(all_threads)
>
>    for mutex,c in possible:
>        print mutex
>        width = []
>        for cc in c:
>            for i in range(len(cc.chain)):
>                try:
>                    width[i] = max(width[i], 0)
>                except:
>                    width.append(0)
>                width[i] = max(width[i],
>                               len(cc.chain[i]),
>                               len(cc.desc[0][i]),
>                               len(cc.desc[1][i]))
>                               
>            print cc.thread.id,":"
>            print("  "),
>            for i in range(len(cc.chain)):
>                print ("%%-%ds" % width[i]) % cc.chain[i],
>            print
>            print("  "),
>            for i in range(len(cc.chain)):
>                print ("%%-%ds" % width[i]) % cc.desc[0][i],
>            print
>            print("  "),
>            for i in range(len(cc.chain)):
>                print ("%%-%ds" % width[i]) % cc.desc[1][i],
>            print
>        print
>

Actions: View

Attachments on bug 241780: 155705 | 155783 | 155790 | 155792 | 156053 | 156069 | 156089 | 156232 | 156238 | 156240 | 156433 | 156437