stacksize.go raw
1 // Package stacksize tries to determine the call graph for ELF binaries and
2 // tries to parse stack size information from DWARF call frame information.
3 package stacksize
4
5 import (
6 "debug/elf"
7 "encoding/binary"
8 "errors"
9 "fmt"
10 "os"
11 "sort"
12 )
13
14 // set to true to print information useful for debugging
15 const debugPrint = false
16
17 // SizeType indicates whether a stack or frame size could be determined and if
18 // not, why.
19 type SizeType uint8
20
21 // Results after trying to determine the stack size of a function in the call
22 // graph. The goal is to find a maximum (bounded) stack size, but sometimes this
23 // is not possible for some reasons such as recursion or indirect calls.
24 const (
25 Undefined SizeType = iota // not yet calculated
26 Unknown // child has unknown stack size
27 Bounded // stack size is fixed at compile time (no recursion etc)
28 Recursive
29 IndirectCall
30 )
31
32 func (s SizeType) String() string {
33 switch s {
34 case Undefined:
35 return "undefined"
36 case Unknown:
37 return "unknown"
38 case Bounded:
39 return "bounded"
40 case Recursive:
41 return "recursive"
42 case IndirectCall:
43 return "indirect call"
44 default:
45 return "<?>"
46 }
47 }
48
49 // CallNode is a node in the call graph (that is, a function). Because this is
50 // determined after linking, there may be multiple names for a single function
51 // (due to aliases). It is also possible multiple functions have the same name
52 // (but are in fact different), for example for static functions in C.
53 type CallNode struct {
54 Names []string
55 Address uint64 // address at which the function is linked (without T bit on ARM)
56 Size uint64 // symbol size, in bytes
57 Children []*CallNode // functions this function calls
58 FrameSize uint64 // frame size, if FrameSizeType is Bounded
59 FrameSizeType SizeType // can be Undefined or Bounded
60 stackSize uint64
61 stackSizeType SizeType
62 missingFrameInfo *CallNode // the child function that is the cause for not being able to determine the stack size
63 }
64
65 func (n *CallNode) String() string {
66 if n == nil {
67 return "<nil>"
68 }
69 return n.Names[0]
70 }
71
72 // CallGraph parses the ELF file and reads DWARF call frame information to
73 // determine frame sizes for each function, as far as that's possible. Because
74 // at this point it is not possible to determine indirect calls, a list of
75 // indirect function calling functions needs to be supplied separately.
76 //
77 // This function does not attempt to determine the stack size for functions.
78 // This is done by calling StackSize on a function in the call graph.
79 func CallGraph(f *elf.File, callsIndirectFunction []string) (map[string][]*CallNode, error) {
80 // Sanity check that there is exactly one symbol table.
81 // Multiple symbol tables are possible, but aren't yet supported below.
82 numSymbolTables := 0
83 for _, section := range f.Sections {
84 if section.Type == elf.SHT_SYMTAB {
85 numSymbolTables++
86 }
87 }
88 if numSymbolTables != 1 {
89 return nil, fmt.Errorf("expected exactly one symbol table, got %d", numSymbolTables)
90 }
91
92 // Collect all symbols in the executable.
93 symbols := make(map[uint64]*CallNode)
94 symbolList := make([]*CallNode, 0)
95 symbolNames := make(map[string][]*CallNode)
96 elfSymbols, err := f.Symbols()
97 if err != nil {
98 return nil, err
99 }
100 for _, elfSymbol := range elfSymbols {
101 if elf.ST_TYPE(elfSymbol.Info) != elf.STT_FUNC {
102 continue
103 }
104 address := elfSymbol.Value
105 if f.Machine == elf.EM_ARM {
106 address = address &^ 1
107 }
108 var node *CallNode
109 if n, ok := symbols[address]; ok {
110 // Existing symbol.
111 if n.Size != elfSymbol.Size {
112 return nil, fmt.Errorf("symbol at 0x%x has inconsistent size (%d for %s and %d for %s)", address, n.Size, n.Names[0], elfSymbol.Size, elfSymbol.Name)
113 }
114 node = n
115 node.Names = append(node.Names, elfSymbol.Name)
116 } else {
117 // New symbol.
118 node = &CallNode{
119 Names: []string{elfSymbol.Name},
120 Address: address,
121 Size: elfSymbol.Size,
122 }
123 symbols[address] = node
124 symbolList = append(symbolList, node)
125 }
126 symbolNames[elfSymbol.Name] = append(symbolNames[elfSymbol.Name], node)
127 }
128
129 // Sort symbols by address, for binary searching.
130 sort.Slice(symbolList, func(i, j int) bool {
131 return symbolList[i].Address < symbolList[j].Address
132 })
133
134 // Load relocations and construct the call graph.
135 for _, section := range f.Sections {
136 if section.Type != elf.SHT_REL {
137 continue
138 }
139 if section.Entsize != 8 {
140 // Assume ELF32, this should be fixed.
141 return nil, fmt.Errorf("only ELF32 is supported at this time")
142 }
143 data, err := section.Data()
144 if err != nil {
145 return nil, err
146 }
147 for i := uint64(0); i < section.Size/section.Entsize; i++ {
148 offset := binary.LittleEndian.Uint32(data[i*section.Entsize:])
149 info := binary.LittleEndian.Uint32(data[i*section.Entsize+4:])
150 if elf.R_SYM32(info) == 0 {
151 continue
152 }
153 elfSymbol := elfSymbols[elf.R_SYM32(info)-1]
154 if elf.ST_TYPE(elfSymbol.Info) != elf.STT_FUNC {
155 continue
156 }
157 address := elfSymbol.Value
158 if f.Machine == elf.EM_ARM {
159 address = address &^ 1
160 }
161 childSym := symbols[address]
162 switch f.Machine {
163 case elf.EM_ARM:
164 relocType := elf.R_ARM(elf.R_TYPE32(info))
165 parentSym := findSymbol(symbolList, uint64(offset))
166 if debugPrint {
167 fmt.Fprintf(os.Stderr, "found relocation %-24s at %s (0x%x) to %s (0x%x)\n", relocType, parentSym, offset, childSym, childSym.Address)
168 }
169 isCall := true
170 switch relocType {
171 case elf.R_ARM_THM_PC22: // actually R_ARM_THM_CALL
172 // used for bl calls
173 case elf.R_ARM_THM_JUMP24:
174 // used for b.w jumps
175 isCall = parentSym != childSym
176 case elf.R_ARM_THM_JUMP11:
177 // used for b.n jumps
178 isCall = parentSym != childSym
179 case elf.R_ARM_THM_MOVW_ABS_NC, elf.R_ARM_THM_MOVT_ABS:
180 // used for getting a function pointer
181 isCall = false
182 case elf.R_ARM_ABS32:
183 // when compiling with -Oz (minsize), used for calling
184 isCall = true
185 default:
186 return nil, fmt.Errorf("unknown relocation: %s", relocType)
187 }
188 if isCall {
189 if parentSym != nil {
190 parentSym.Children = append(parentSym.Children, childSym)
191 }
192 }
193 default:
194 return nil, fmt.Errorf("unknown architecture: %s", f.Machine)
195 }
196 }
197 }
198
199 // Set fixed frame size information, depending on the architecture.
200 switch f.Machine {
201 case elf.EM_ARM:
202 knownFrameSizes := map[string]uint64{
203 // implemented with assembly in compiler-rt
204 "__aeabi_idivmod": 3 * 4, // 3 registers on thumb1 but 1 register on thumb2
205 "__aeabi_uidivmod": 3 * 4, // 3 registers on thumb1 but 1 register on thumb2
206 "__aeabi_ldivmod": 2 * 4,
207 "__aeabi_uldivmod": 2 * 4,
208 "__aeabi_memclr": 2 * 4, // 2 registers on thumb1
209 "__aeabi_memset": 2 * 4, // 2 registers on thumb1
210 "__aeabi_memcmp": 2 * 4, // 2 registers on thumb1
211 "__aeabi_memcpy": 2 * 4, // 2 registers on thumb1
212 "__aeabi_memmove": 2 * 4, // 2 registers on thumb1
213 "__aeabi_dcmpeq": 2 * 4,
214 "__aeabi_dcmplt": 2 * 4,
215 "__aeabi_dcmple": 2 * 4,
216 "__aeabi_dcmpge": 2 * 4,
217 "__aeabi_dcmpgt": 2 * 4,
218 "__aeabi_fcmpeq": 2 * 4,
219 "__aeabi_fcmplt": 2 * 4,
220 "__aeabi_fcmple": 2 * 4,
221 "__aeabi_fcmpge": 2 * 4,
222 "__aeabi_fcmpgt": 2 * 4,
223 }
224 for name, size := range knownFrameSizes {
225 if sym, ok := symbolNames[name]; ok {
226 if len(sym) > 1 {
227 return nil, fmt.Errorf("expected zero or one occurrence of the symbol %s, found %d", name, len(sym))
228 }
229 sym[0].FrameSize = size
230 sym[0].FrameSizeType = Bounded
231 }
232 }
233 }
234
235 // Mark functions that do indirect calls (which cannot be determined
236 // directly from ELF/DWARF information).
237 for _, name := range callsIndirectFunction {
238 for _, fn := range symbolNames[name] {
239 fn.stackSizeType = IndirectCall
240 fn.missingFrameInfo = fn
241 }
242 }
243
244 // Read the .debug_frame section.
245 section := f.Section(".debug_frame")
246 if section == nil {
247 return nil, errors.New("no .debug_frame section present, binary was compiled without debug information")
248 }
249 data, err := section.Data()
250 if err != nil {
251 return nil, fmt.Errorf("could not read .debug_frame section: %w", err)
252 }
253 err = parseFrames(f, data, symbols)
254 if err != nil {
255 return nil, err
256 }
257
258 return symbolNames, nil
259 }
260
261 // findSymbol determines in which symbol the given address lies.
262 func findSymbol(symbolList []*CallNode, address uint64) *CallNode {
263 // TODO: binary search
264 for _, sym := range symbolList {
265 if address >= sym.Address && address < sym.Address+sym.Size {
266 return sym
267 }
268 }
269 return nil
270 }
271
272 // StackSize tries to determine the stack size of the given call graph node. It
273 // returns the maximum stack size, whether this size can be known at compile
274 // time and the call node responsible for failing to determine the maximum stack
275 // usage. The stack size is only valid if sizeType is Bounded.
276 func (node *CallNode) StackSize() (uint64, SizeType, *CallNode) {
277 if node.stackSizeType == Undefined {
278 node.determineStackSize(make(map[*CallNode]struct{}))
279 }
280 return node.stackSize, node.stackSizeType, node.missingFrameInfo
281 }
282
283 // determineStackSize tries to determine the maximum stack size for this
284 // function, recursively.
285 func (node *CallNode) determineStackSize(parents map[*CallNode]struct{}) {
286 if _, ok := parents[node]; ok {
287 // The function calls itself (directly or indirectly).
288 node.stackSizeType = Recursive
289 node.missingFrameInfo = node
290 return
291 }
292 parents[node] = struct{}{}
293 defer func() {
294 delete(parents, node)
295 }()
296 switch node.FrameSizeType {
297 case Bounded:
298 // Determine the stack size recursively.
299 childMaxStackSize := uint64(0)
300 for _, child := range node.Children {
301 if child.stackSizeType == Undefined {
302 child.determineStackSize(parents)
303 }
304 switch child.stackSizeType {
305 case Bounded:
306 if child.stackSize > childMaxStackSize {
307 childMaxStackSize = child.stackSize
308 }
309 case Unknown, Recursive, IndirectCall:
310 node.stackSizeType = child.stackSizeType
311 node.missingFrameInfo = child.missingFrameInfo
312 return
313 default:
314 panic("unknown child stack size type")
315 }
316 }
317 node.stackSize = node.FrameSize + childMaxStackSize
318 node.stackSizeType = Bounded
319 case Undefined:
320 node.stackSizeType = Unknown
321 node.missingFrameInfo = node
322 default:
323 panic("unknown frame size type") // unreachable
324 }
325 }
326