forked from go-delve/delve
-
Notifications
You must be signed in to change notification settings - Fork 0
/
state_machine.go
403 lines (354 loc) · 9.31 KB
/
state_machine.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
package line
import (
"bytes"
"encoding/binary"
"errors"
"fmt"
"github.com/derekparker/delve/pkg/dwarf/util"
)
type Location struct {
File string
Line int
Address uint64
Delta int
}
type StateMachine struct {
dbl *DebugLineInfo
file string
line int
address uint64
column uint
isStmt bool
basicBlock bool
endSeq bool
lastWasStandard bool
lastDelta int
// valid is true if the current value of the state machine is the address of
// an instruction (using the terminology used by DWARF spec the current
// value of the state machine should be appended to the matrix representing
// the compilation unit)
valid bool
started bool
buf *bytes.Buffer // remaining instructions
opcodes []opcodefn
definedFiles []*FileEntry // files defined with DW_LINE_define_file
lastAddress uint64
lastFile string
lastLine int
}
type opcodefn func(*StateMachine, *bytes.Buffer)
// Special opcodes
const (
DW_LNS_copy = 1
DW_LNS_advance_pc = 2
DW_LNS_advance_line = 3
DW_LNS_set_file = 4
DW_LNS_set_column = 5
DW_LNS_negate_stmt = 6
DW_LNS_set_basic_block = 7
DW_LNS_const_add_pc = 8
DW_LNS_fixed_advance_pc = 9
)
// Extended opcodes
const (
DW_LINE_end_sequence = 1
DW_LINE_set_address = 2
DW_LINE_define_file = 3
)
var standardopcodes = map[byte]opcodefn{
DW_LNS_copy: copyfn,
DW_LNS_advance_pc: advancepc,
DW_LNS_advance_line: advanceline,
DW_LNS_set_file: setfile,
DW_LNS_set_column: setcolumn,
DW_LNS_negate_stmt: negatestmt,
DW_LNS_set_basic_block: setbasicblock,
DW_LNS_const_add_pc: constaddpc,
DW_LNS_fixed_advance_pc: fixedadvancepc,
}
var extendedopcodes = map[byte]opcodefn{
DW_LINE_end_sequence: endsequence,
DW_LINE_set_address: setaddress,
DW_LINE_define_file: definefile,
}
func newStateMachine(dbl *DebugLineInfo, instructions []byte) *StateMachine {
opcodes := make([]opcodefn, len(standardopcodes)+1)
opcodes[0] = execExtendedOpcode
for op := range standardopcodes {
opcodes[op] = standardopcodes[op]
}
return &StateMachine{dbl: dbl, file: dbl.FileNames[0].Path, line: 1, buf: bytes.NewBuffer(instructions), opcodes: opcodes}
}
// Returns all PCs for a given file/line. Useful for loops where the 'for' line
// could be split amongst 2 PCs.
func (lineInfo *DebugLineInfo) AllPCsForFileLine(f string, l int) (pcs []uint64) {
if lineInfo == nil {
return nil
}
var (
foundFile bool
lastAddr uint64
sm = newStateMachine(lineInfo, lineInfo.Instructions)
)
for {
if err := sm.next(); err != nil {
break
}
if foundFile && sm.file != f {
return
}
if sm.line == l && sm.file == f && sm.address != lastAddr {
foundFile = true
if sm.valid {
pcs = append(pcs, sm.address)
}
line := sm.line
// Keep going until we're on a different line. We only care about
// when a line comes back around (i.e. for loop) so get to next line,
// and try to find the line we care about again.
for {
if err := sm.next(); err != nil {
break
}
if line < sm.line {
break
}
}
}
}
return
}
var NoSourceError = errors.New("no source available")
func (lineInfo *DebugLineInfo) AllPCsBetween(begin, end uint64) ([]uint64, error) {
if lineInfo == nil {
return nil, NoSourceError
}
var (
pcs []uint64
lastaddr uint64
sm = newStateMachine(lineInfo, lineInfo.Instructions)
)
for {
if err := sm.next(); err != nil {
break
}
if !sm.valid {
continue
}
if sm.address > end {
break
}
if sm.address >= begin && sm.address > lastaddr {
lastaddr = sm.address
pcs = append(pcs, sm.address)
}
}
return pcs, nil
}
// copy returns a copy of this state machine, running the returned state
// machine will not affect sm.
func (sm *StateMachine) copy() *StateMachine {
var r StateMachine
r = *sm
r.buf = bytes.NewBuffer(sm.buf.Bytes())
return &r
}
// PCToLine returns the filename and line number associated with pc.
// If pc isn't found inside lineInfo's table it will return the filename and
// line number associated with the closest PC address preceding pc.
// basePC will be used for caching, it's normally the entry point for the
// function containing pc.
func (lineInfo *DebugLineInfo) PCToLine(basePC, pc uint64) (string, int) {
if lineInfo == nil {
return "", 0
}
if basePC > pc {
panic(fmt.Errorf("basePC after pc %#x %#x", basePC, pc))
}
var sm *StateMachine
if basePC == 0 {
sm = newStateMachine(lineInfo, lineInfo.Instructions)
} else {
// Try to use the last state machine that we used for this function, if
// there isn't one or it's already past pc try to clone the cached state
// machine stopped at the entry point of the function.
// As a last resort start from the start of the debug_line section.
sm = lineInfo.lastMachineCache[basePC]
if sm == nil || sm.lastAddress > pc {
sm = lineInfo.stateMachineCache[basePC]
if sm == nil {
sm = newStateMachine(lineInfo, lineInfo.Instructions)
sm.PCToLine(basePC)
lineInfo.stateMachineCache[basePC] = sm
}
sm = sm.copy()
lineInfo.lastMachineCache[basePC] = sm
}
}
file, line, _ := sm.PCToLine(pc)
return file, line
}
func (sm *StateMachine) PCToLine(pc uint64) (string, int, bool) {
if !sm.started {
if err := sm.next(); err != nil {
return "", 0, false
}
}
if sm.lastAddress > pc {
return "", 0, false
}
for {
if sm.valid {
if sm.address > pc {
return sm.lastFile, sm.lastLine, true
}
if sm.address == pc {
return sm.file, sm.line, true
}
}
if err := sm.next(); err != nil {
break
}
}
if sm.valid {
return sm.file, sm.line, true
}
return "", 0, false
}
// LineToPC returns the first PC address associated with filename:lineno.
func (lineInfo *DebugLineInfo) LineToPC(filename string, lineno int) uint64 {
if lineInfo == nil {
return 0
}
var (
foundFile bool
sm = newStateMachine(lineInfo, lineInfo.Instructions)
)
for {
if err := sm.next(); err != nil {
break
}
if foundFile && sm.file != filename {
break
}
if sm.line == lineno && sm.file == filename {
foundFile = true
if sm.valid {
return sm.address
}
}
}
return 0
}
func (sm *StateMachine) next() error {
sm.started = true
if sm.valid {
sm.lastAddress, sm.lastFile, sm.lastLine = sm.address, sm.file, sm.line
}
if sm.endSeq {
sm.endSeq = false
sm.file = sm.dbl.FileNames[0].Path
sm.line = 1
sm.column = 0
sm.isStmt = false
sm.basicBlock = false
}
b, err := sm.buf.ReadByte()
if err != nil {
return err
}
if int(b) < len(sm.opcodes) {
sm.lastWasStandard = b != 0
sm.valid = false
sm.opcodes[b](sm, sm.buf)
} else if b < sm.dbl.Prologue.OpcodeBase {
// unimplemented standard opcode, read the number of arguments specified
// in the prologue and do nothing with them
opnum := sm.dbl.Prologue.StdOpLengths[b-1]
for i := 0; i < int(opnum); i++ {
util.DecodeSLEB128(sm.buf)
}
} else {
execSpecialOpcode(sm, b)
}
return nil
}
func execSpecialOpcode(sm *StateMachine, instr byte) {
var (
opcode = uint8(instr)
decoded = opcode - sm.dbl.Prologue.OpcodeBase
)
if sm.dbl.Prologue.InitialIsStmt == uint8(1) {
sm.isStmt = true
}
sm.lastDelta = int(sm.dbl.Prologue.LineBase + int8(decoded%sm.dbl.Prologue.LineRange))
sm.line += sm.lastDelta
sm.address += uint64(decoded/sm.dbl.Prologue.LineRange) * uint64(sm.dbl.Prologue.MinInstrLength)
sm.basicBlock = false
sm.lastWasStandard = false
sm.valid = true
}
func execExtendedOpcode(sm *StateMachine, buf *bytes.Buffer) {
_, _ = util.DecodeULEB128(buf)
b, _ := buf.ReadByte()
if fn, ok := extendedopcodes[b]; ok {
fn(sm, buf)
}
}
func copyfn(sm *StateMachine, buf *bytes.Buffer) {
sm.basicBlock = false
sm.valid = true
}
func advancepc(sm *StateMachine, buf *bytes.Buffer) {
addr, _ := util.DecodeULEB128(buf)
sm.address += addr * uint64(sm.dbl.Prologue.MinInstrLength)
}
func advanceline(sm *StateMachine, buf *bytes.Buffer) {
line, _ := util.DecodeSLEB128(buf)
sm.line += int(line)
sm.lastDelta = int(line)
}
func setfile(sm *StateMachine, buf *bytes.Buffer) {
i, _ := util.DecodeULEB128(buf)
if i-1 < uint64(len(sm.dbl.FileNames)) {
sm.file = sm.dbl.FileNames[i-1].Path
} else {
j := (i - 1) - uint64(len(sm.dbl.FileNames))
if j < uint64(len(sm.definedFiles)) {
sm.file = sm.definedFiles[j].Path
} else {
sm.file = ""
}
}
}
func setcolumn(sm *StateMachine, buf *bytes.Buffer) {
c, _ := util.DecodeULEB128(buf)
sm.column = uint(c)
}
func negatestmt(sm *StateMachine, buf *bytes.Buffer) {
sm.isStmt = !sm.isStmt
}
func setbasicblock(sm *StateMachine, buf *bytes.Buffer) {
sm.basicBlock = true
}
func constaddpc(sm *StateMachine, buf *bytes.Buffer) {
sm.address += uint64((255-sm.dbl.Prologue.OpcodeBase)/sm.dbl.Prologue.LineRange) * uint64(sm.dbl.Prologue.MinInstrLength)
}
func fixedadvancepc(sm *StateMachine, buf *bytes.Buffer) {
var operand uint16
binary.Read(buf, binary.LittleEndian, &operand)
sm.address += uint64(operand)
}
func endsequence(sm *StateMachine, buf *bytes.Buffer) {
sm.endSeq = true
sm.valid = true
}
func setaddress(sm *StateMachine, buf *bytes.Buffer) {
var addr uint64
binary.Read(buf, binary.LittleEndian, &addr)
sm.address = addr
}
func definefile(sm *StateMachine, buf *bytes.Buffer) {
entry := readFileEntry(sm.dbl, sm.buf, false)
sm.definedFiles = append(sm.definedFiles, entry)
}