1import re
2
3RANGE_START=0x3ffe0000
4RANGE_END=0x40000000
5
6kaddr_cap_regex = re.compile(r"^(0x[0-9a-f]+){(.*)}$")
7cap_regex = \
8re.compile(r"^left=(?P<leftval>0x[0-9a-f]+),right=(?P<rightval>0x[0-9a-f]+),end=(?P<end>0x[0-9a-f]+),end_root=(?P<end_root>\d+),level=(?P<level>\d+),address=(?P<address>0x[0-9a-f]+),size=(?P<size>0x[0-9a-f]+),type=(?P<type>\d+),remote_rels=(?P<rcopies>\d)(?P<rancs>\d)(?P<rdescs>\d),extra=(?P<extra>.*)$")
9typemap = {
10 45:"ObjType_IPI",
11 44:"ObjType_KernelControlBlock",
12 43:"ObjType_PerfMon",
13 42:"ObjType_ID",
14 41:"ObjType_Notify_IPI",
15 40:"ObjType_Notify_RCK",
16 39:"ObjType_IO",
17 38:"ObjType_IRQSrc",
18 37:"ObjType_IRQDest",
19 36:"ObjType_IRQTable",
20 35:"ObjType_VNode_AARCH64_l3_Mapping",
21 34:"ObjType_VNode_AARCH64_l3",
22 33:"ObjType_VNode_AARCH64_l2_Mapping",
23 32:"ObjType_VNode_AARCH64_l2",
24 31:"ObjType_VNode_AARCH64_l1_Mapping",
25 30:"ObjType_VNode_AARCH64_l1",
26 29:"ObjType_VNode_ARM_l2_Mapping",
27 28:"ObjType_VNode_ARM_l2",
28 27:"ObjType_VNode_ARM_l1_Mapping",
29 26:"ObjType_VNode_ARM_l1",
30 25:"ObjType_VNode_x86_32_ptable_Mapping",
31 24:"ObjType_VNode_x86_32_ptable",
32 23:"ObjType_VNode_x86_32_pdir_Mapping",
33 22:"ObjType_VNode_x86_32_pdir",
34 21:"ObjType_VNode_x86_32_pdpt_Mapping",
35 20:"ObjType_VNode_x86_32_pdpt",
36 19:"ObjType_VNode_x86_64_ptable_Mapping",
37 18:"ObjType_VNode_x86_64_ptable",
38 17:"ObjType_VNode_x86_64_pdir_Mapping",
39 16:"ObjType_VNode_x86_64_pdir",
40 15:"ObjType_VNode_x86_64_pdpt_Mapping",
41 14:"ObjType_VNode_x86_64_pdpt",
42 13:"ObjType_VNode_x86_64_pml4_Mapping",
43 12:"ObjType_VNode_x86_64_pml4",
44 11:"ObjType_Kernel",
45 10:"ObjType_DevFrame_Mapping",
46 9 :"ObjType_DevFrame",
47 8 :"ObjType_Frame_Mapping",
48 7 :"ObjType_Frame",
49 6 :"ObjType_EndPoint",
50 5 :"ObjType_Dispatcher",
51 4 :"ObjType_FCNode",
52 3 :"ObjType_CNode",
53 2 :"ObjType_RAM",
54 1 :"ObjType_PhysAddr",
55 0 :"ObjType_Null",
56 }
57
58class Capability(object):
59    """Representation of a MDB node"""
60    def __init__(self, capstring):
61        capmatch = cap_regex.match(capstring)
62        for key, value in capmatch.groupdict().items():
63            val = value
64            if key != "extra":
65                val = int(value, 0)
66            setattr(self, key, val)
67
68        self.parent = None
69        self.leftcap = None
70        self.rightcap = None
71        self.nodeid = -1
72
73    def __str__(self):
74        return "{address=0x%x, size=0x%x, type=%s, left=0x%x, right=0x%x}" % \
75                (self.address, self.size, typemap[self.type], self.leftval, self.rightval)
76
77    def set_parent(self, parentcap):
78        self.parent = parentcap
79
80    def set_left(self, leftcap):
81        self.leftcap = leftcap
82
83    def set_right(self, rightcap):
84        self.rightcap = rightcap
85
86    def set_nodeid(self, nodeid):
87        self.nodeid = nodeid
88
89def parse_file(fname):
90    # nodes is map of kernel addr to cap
91    nodes = {}
92    with open(fname, 'r') as f:
93        for l in f:
94            l = l.strip()
95            match = kaddr_cap_regex.match(l)
96            kaddr, cap = match.groups()
97            nodes[int(kaddr, 0)] = Capability(cap)
98    return nodes
99
100def build_tree(nodedict):
101    for kaddr,cap in nodedict.items():
102        left = cap.leftval
103        right = cap.rightval
104        if left != 0:
105            leftcap = nodedict[left]
106            leftcap.set_parent(cap)
107        else:
108            leftcap = None
109        if right != 0:
110            rightcap = nodedict[right]
111            rightcap.set_parent(cap)
112        else:
113            rightcap = None
114
115        cap.set_left(leftcap)
116        cap.set_right(rightcap)
117
118    root = None
119    for kaddr,cap in nodedict.items():
120        if cap.parent is None:
121            root = cap
122
123    return root
124
125def write_tree(root, outfh):
126    mynodeid = root.nodeid
127    if root.leftcap is not None:
128        leftid = root.leftcap.nodeid
129        outfh.write("  n%d -- n%d\n" % (mynodeid, leftid))
130        write_tree(root.leftcap, outfh)
131    if root.rightcap is not None:
132        rightid=  root.rightcap.nodeid
133        outfh.write("  n%d -- n%d\n" % (mynodeid, rightid))
134        write_tree(root.rightcap, outfh)
135
136def write_dot_file(nodedict, treeroot, outfname):
137    nodeid = 0
138    with open(outfname, "w") as f:
139        f.write("graph mdb {\n")
140        # generate nodes
141        f.write("  // list of all nodes\n")
142        for kaddr,cap in nodedict.items():
143            color = "black"
144            cstart = cap.address
145            cend = cap.address + cap.size
146            if cstart >= RANGE_START and cend <= RANGE_END:
147                # cap completely in target range
148                print "cap inside target range"
149                color = "red"
150            elif cend >= RANGE_START and cend <= RANGE_END:
151                # cap ends in target range
152                print "cap ends inside target range"
153                color = "blue"
154            elif cstart >= RANGE_START and cstart <= RANGE_END:
155                # cap starts in target range
156                print "cap starts inside target range"
157                color = "green"
158            f.write("  n%d [label=\"0x%x--0x%x [%d]\",color=\"%s\"];\n" % \
159                    (nodeid, cap.address,cap.address + cap.size, cap.type, color))
160            cap.set_nodeid(nodeid)
161            nodeid += 1
162
163        f.write("  // Tree\n")
164        write_tree(treeroot, f)
165        f.write("}\n")
166
167
168
169if __name__ == "__main__":
170    import sys
171    if len(sys.argv) < 2:
172        print "usage %s mdb_dump.txt [output.dot]" % sys.argv[0]
173        sys.exit(1)
174
175    nodes = parse_file(sys.argv[1])
176    treeroot = build_tree(nodes)
177
178    outf = "output.dot"
179    if len(sys.argv) >= 3:
180        outf = sys.argv[2]
181    write_dot_file(nodes, treeroot, outf)
182
183    sys.exit(0)
184