| #!/usr/bin/env python |
| # Script that tries to find how much stack space each function in an |
| # object is using. |
| # |
| # Copyright (C) 2008-2015 Kevin O'Connor <kevin@koconnor.net> |
| # |
| # This file may be distributed under the terms of the GNU GPLv3 license. |
| |
| # Usage: |
| # objdump -m i386 -M i8086 -M suffix -d out/rom16.o | scripts/checkstack.py |
| |
| import sys |
| import re |
| |
| # Functions that change stacks |
| STACKHOP = ['stack_hop', 'stack_hop_back'] |
| # List of functions we can assume are never called. |
| #IGNORE = ['panic', '__dprintf'] |
| IGNORE = ['panic'] |
| |
| OUTPUTDESC = """ |
| #funcname1[preamble_stack_usage,max_usage_with_callers]: |
| # insn_addr:called_function [usage_at_call_point+caller_preamble,total_usage] |
| # |
| #funcname2[p,m,max_usage_to_yield_point]: |
| # insn_addr:called_function [u+c,t,usage_to_yield_point] |
| """ |
| |
| class function: |
| def __init__(self, funcaddr, funcname): |
| self.funcaddr = funcaddr |
| self.funcname = funcname |
| self.basic_stack_usage = 0 |
| self.max_stack_usage = None |
| self.yield_usage = -1 |
| self.max_yield_usage = None |
| self.total_calls = 0 |
| # called_funcs = [(insnaddr, calladdr, stackusage), ...] |
| self.called_funcs = [] |
| self.subfuncs = {} |
| # Update function info with a found "yield" point. |
| def noteYield(self, stackusage): |
| if self.yield_usage < stackusage: |
| self.yield_usage = stackusage |
| # Update function info with a found "call" point. |
| def noteCall(self, insnaddr, calladdr, stackusage): |
| if (calladdr, stackusage) in self.subfuncs: |
| # Already noted a nearly identical call - ignore this one. |
| return |
| self.called_funcs.append((insnaddr, calladdr, stackusage)) |
| self.subfuncs[(calladdr, stackusage)] = 1 |
| |
| # Find out maximum stack usage for a function |
| def calcmaxstack(info, funcs): |
| if info.max_stack_usage is not None: |
| return |
| info.max_stack_usage = max_stack_usage = info.basic_stack_usage |
| info.max_yield_usage = max_yield_usage = info.yield_usage |
| total_calls = 0 |
| seenbefore = {} |
| # Find max of all nested calls. |
| for insnaddr, calladdr, usage in info.called_funcs: |
| callinfo = funcs.get(calladdr) |
| if callinfo is None: |
| continue |
| calcmaxstack(callinfo, funcs) |
| if callinfo.funcname not in seenbefore: |
| seenbefore[callinfo.funcname] = 1 |
| total_calls += callinfo.total_calls + 1 |
| funcnameroot = callinfo.funcname.split('.')[0] |
| if funcnameroot in IGNORE: |
| # This called function is ignored - don't contribute it to |
| # the max stack. |
| continue |
| totusage = usage + callinfo.max_stack_usage |
| totyieldusage = usage + callinfo.max_yield_usage |
| if funcnameroot in STACKHOP: |
| # Don't count children of this function |
| totusage = totyieldusage = usage |
| if totusage > max_stack_usage: |
| max_stack_usage = totusage |
| if callinfo.max_yield_usage >= 0 and totyieldusage > max_yield_usage: |
| max_yield_usage = totyieldusage |
| info.max_stack_usage = max_stack_usage |
| info.max_yield_usage = max_yield_usage |
| info.total_calls = total_calls |
| |
| # Try to arrange output so that functions that call each other are |
| # near each other. |
| def orderfuncs(funcaddrs, availfuncs): |
| l = [(availfuncs[funcaddr].total_calls |
| , availfuncs[funcaddr].funcname, funcaddr) |
| for funcaddr in funcaddrs if funcaddr in availfuncs] |
| l.sort() |
| l.reverse() |
| out = [] |
| while l: |
| count, name, funcaddr = l.pop(0) |
| info = availfuncs.get(funcaddr) |
| if info is None: |
| continue |
| calladdrs = [calls[1] for calls in info.called_funcs] |
| del availfuncs[funcaddr] |
| out = out + orderfuncs(calladdrs, availfuncs) + [info] |
| return out |
| |
| hex_s = r'[0-9a-f]+' |
| re_func = re.compile(r'^(?P<funcaddr>' + hex_s + r') <(?P<func>.*)>:$') |
| re_asm = re.compile( |
| r'^[ ]*(?P<insnaddr>' + hex_s |
| + r'):\t.*\t(addr32 )?(?P<insn>.+?)[ ]*((?P<calladdr>' + hex_s |
| + r') <(?P<ref>.*)>)?$') |
| re_usestack = re.compile( |
| r'^(push[f]?[lw])|(sub.* [$](?P<num>0x' + hex_s + r'),%esp)$') |
| |
| def main(): |
| unknownfunc = function(None, "<unknown>") |
| indirectfunc = function(-1, '<indirect>') |
| unknownfunc.max_stack_usage = indirectfunc.max_stack_usage = 0 |
| unknownfunc.max_yield_usage = indirectfunc.max_yield_usage = -1 |
| funcs = {-1: indirectfunc} |
| cur = None |
| atstart = 0 |
| stackusage = 0 |
| |
| # Parse input lines |
| for line in sys.stdin.readlines(): |
| m = re_func.match(line) |
| if m is not None: |
| # Found function |
| funcaddr = int(m.group('funcaddr'), 16) |
| funcs[funcaddr] = cur = function(funcaddr, m.group('func')) |
| stackusage = 0 |
| atstart = 1 |
| continue |
| m = re_asm.match(line) |
| if m is None: |
| #print("other", repr(line)) |
| continue |
| insn = m.group('insn') |
| |
| im = re_usestack.match(insn) |
| if im is not None: |
| if insn.startswith('pushl') or insn.startswith('pushfl'): |
| stackusage += 4 |
| continue |
| elif insn.startswith('pushw') or insn.startswith('pushfw'): |
| stackusage += 2 |
| continue |
| stackusage += int(im.group('num'), 16) |
| |
| if atstart: |
| if '%esp' in insn or insn.startswith('leal'): |
| # Still part of initial header |
| continue |
| if not stackusage and ( |
| insn.startswith('test') or insn.startswith('cmp') |
| or insn.startswith('j')): |
| # There may be conditional checks prior to stack frame |
| continue |
| cur.basic_stack_usage = stackusage |
| atstart = 0 |
| |
| insnaddr = m.group('insnaddr') |
| calladdr = m.group('calladdr') |
| if calladdr is None: |
| if insn.startswith('lcallw'): |
| cur.noteCall(insnaddr, -1, stackusage + 4) |
| cur.noteYield(stackusage + 4) |
| elif insn.startswith('int'): |
| cur.noteCall(insnaddr, -1, stackusage + 6) |
| cur.noteYield(stackusage + 6) |
| elif insn.startswith('sti'): |
| cur.noteYield(stackusage) |
| else: |
| # misc instruction |
| continue |
| else: |
| # Jump or call insn |
| calladdr = int(calladdr, 16) |
| ref = m.group('ref') |
| if '+' in ref: |
| # Inter-function jump. |
| pass |
| elif insn.startswith('j'): |
| # Tail call |
| cur.noteCall(insnaddr, calladdr, 0) |
| elif insn.startswith('calll'): |
| cur.noteCall(insnaddr, calladdr, stackusage + 4) |
| elif insn.startswith('callw'): |
| cur.noteCall(insnaddr, calladdr, stackusage + 2) |
| else: |
| print("unknown call", ref) |
| cur.noteCall(insnaddr, calladdr, stackusage) |
| # Reset stack usage to preamble usage |
| stackusage = cur.basic_stack_usage |
| |
| # Calculate maxstackusage |
| for info in funcs.values(): |
| calcmaxstack(info, funcs) |
| |
| # Sort functions for output |
| funcinfos = orderfuncs(funcs.keys(), funcs.copy()) |
| |
| # Show all functions |
| print(OUTPUTDESC) |
| for info in funcinfos: |
| if info.max_stack_usage == 0 and info.max_yield_usage < 0: |
| continue |
| yieldstr = "" |
| if info.max_yield_usage >= 0: |
| yieldstr = ",%d" % info.max_yield_usage |
| print("\n%s[%d,%d%s]:" % (info.funcname, info.basic_stack_usage |
| , info.max_stack_usage, yieldstr)) |
| for insnaddr, calladdr, stackusage in info.called_funcs: |
| callinfo = funcs.get(calladdr, unknownfunc) |
| yieldstr = "" |
| if callinfo.max_yield_usage >= 0: |
| yieldstr = ",%d" % (stackusage + callinfo.max_yield_usage) |
| print(" %04s:%-40s [%d+%d,%d%s]" % ( |
| insnaddr, callinfo.funcname, stackusage |
| , callinfo.basic_stack_usage |
| , stackusage+callinfo.max_stack_usage, yieldstr)) |
| |
| if __name__ == '__main__': |
| main() |
