1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 5 /*
6 * Line tables
7 */
8 9 package gosym
10 11 import (
12 "bytes"
13 "encoding/binary"
14 "sort"
15 "sync"
16 )
17 18 // version of the pclntab
19 type version int
20 21 const (
22 verUnknown version = iota
23 ver11
24 ver12
25 ver116
26 ver118
27 ver120
28 )
29 30 // A LineTable is a data structure mapping program counters to line numbers.
31 //
32 // In Go 1.1 and earlier, each function (represented by a [Func]) had its own LineTable,
33 // and the line number corresponded to a numbering of all source lines in the
34 // program, across all files. That absolute line number would then have to be
35 // converted separately to a file name and line number within the file.
36 //
37 // In Go 1.2, the format of the data changed so that there is a single LineTable
38 // for the entire program, shared by all Funcs, and there are no absolute line
39 // numbers, just line numbers within specific files.
40 //
41 // For the most part, LineTable's methods should be treated as an internal
42 // detail of the package; callers should use the methods on [Table] instead.
43 type LineTable struct {
44 Data []byte
45 PC uint64
46 Line int
47 48 // This mutex is used to keep parsing of pclntab synchronous.
49 mu sync.Mutex
50 51 // Contains the version of the pclntab section.
52 version version
53 54 // Go 1.2/1.16/1.18 state
55 binary binary.ByteOrder
56 quantum uint32
57 ptrsize uint32
58 textStart uint64 // address of runtime.text symbol (1.18+)
59 funcnametab []byte
60 cutab []byte
61 funcdata []byte
62 functab []byte
63 nfunctab uint32
64 filetab []byte
65 pctab []byte // points to the pctables.
66 nfiletab uint32
67 funcNames map[uint32]string // cache the function names
68 strings map[uint32]string // interned substrings of Data, keyed by offset
69 // fileMap varies depending on the version of the object file.
70 // For ver12, it maps the name to the index in the file table.
71 // For ver116, it maps the name to the offset in filetab.
72 fileMap map[string]uint32
73 }
74 75 // NOTE(rsc): This is wrong for GOARCH=arm, which uses a quantum of 4,
76 // but we have no idea whether we're using arm or not. This only
77 // matters in the old (pre-Go 1.2) symbol table format, so it's not worth
78 // fixing.
79 const oldQuantum = 1
80 81 func (t *LineTable) parse(targetPC uint64, targetLine int) (b []byte, pc uint64, line int) {
82 // The PC/line table can be thought of as a sequence of
83 // <pc update>* <line update>
84 // batches. Each update batch results in a (pc, line) pair,
85 // where line applies to every PC from pc up to but not
86 // including the pc of the next pair.
87 //
88 // Here we process each update individually, which simplifies
89 // the code, but makes the corner cases more confusing.
90 b, pc, line = t.Data, t.PC, t.Line
91 for pc <= targetPC && line != targetLine && len(b) > 0 {
92 code := b[0]
93 b = b[1:]
94 switch {
95 case code == 0:
96 if len(b) < 4 {
97 b = b[0:0]
98 break
99 }
100 val := binary.BigEndian.Uint32(b)
101 b = b[4:]
102 line += int(val)
103 case code <= 64:
104 line += int(code)
105 case code <= 128:
106 line -= int(code - 64)
107 default:
108 pc += oldQuantum * uint64(code-128)
109 continue
110 }
111 pc += oldQuantum
112 }
113 return b, pc, line
114 }
115 116 func (t *LineTable) slice(pc uint64) *LineTable {
117 data, pc, line := t.parse(pc, -1)
118 return &LineTable{Data: data, PC: pc, Line: line}
119 }
120 121 // PCToLine returns the line number for the given program counter.
122 //
123 // Deprecated: Use Table's PCToLine method instead.
124 func (t *LineTable) PCToLine(pc uint64) int {
125 if t.isGo12() {
126 return t.go12PCToLine(pc)
127 }
128 _, _, line := t.parse(pc, -1)
129 return line
130 }
131 132 // LineToPC returns the program counter for the given line number,
133 // considering only program counters before maxpc.
134 //
135 // Deprecated: Use Table's LineToPC method instead.
136 func (t *LineTable) LineToPC(line int, maxpc uint64) uint64 {
137 if t.isGo12() {
138 return 0
139 }
140 _, pc, line1 := t.parse(maxpc, line)
141 if line1 != line {
142 return 0
143 }
144 // Subtract quantum from PC to account for post-line increment
145 return pc - oldQuantum
146 }
147 148 // NewLineTable returns a new PC/line table
149 // corresponding to the encoded data.
150 // Text must be the start address of the
151 // corresponding text segment, with the exact
152 // value stored in the 'runtime.text' symbol.
153 // This value may differ from the start
154 // address of the text segment if
155 // binary was built with cgo enabled.
156 func NewLineTable(data []byte, text uint64) *LineTable {
157 return &LineTable{Data: data, PC: text, Line: 0, funcNames: map[uint32]string{}, strings: map[uint32]string{}}
158 }
159 160 // Go 1.2 symbol table format.
161 // See golang.org/s/go12symtab.
162 //
163 // A general note about the methods here: rather than try to avoid
164 // index out of bounds errors, we trust Go to detect them, and then
165 // we recover from the panics and treat them as indicative of a malformed
166 // or incomplete table.
167 //
168 // The methods called by symtab.go, which begin with "go12" prefixes,
169 // are expected to have that recovery logic.
170 171 // isGo12 reports whether this is a Go 1.2 (or later) symbol table.
172 func (t *LineTable) isGo12() bool {
173 t.parsePclnTab()
174 return t.version >= ver12
175 }
176 177 const (
178 go12magic = 0xfffffffb
179 go116magic = 0xfffffffa
180 go118magic = 0xfffffff0
181 go120magic = 0xfffffff1
182 )
183 184 // uintptr returns the pointer-sized value encoded at b.
185 // The pointer size is dictated by the table being read.
186 func (t *LineTable) uintptr(b []byte) uint64 {
187 if t.ptrsize == 4 {
188 return uint64(t.binary.Uint32(b))
189 }
190 return t.binary.Uint64(b)
191 }
192 193 // parsePclnTab parses the pclntab, setting the version.
194 func (t *LineTable) parsePclnTab() {
195 t.mu.Lock()
196 defer t.mu.Unlock()
197 if t.version != verUnknown {
198 return
199 }
200 201 // Note that during this function, setting the version is the last thing we do.
202 // If we set the version too early, and parsing failed (likely as a panic on
203 // slice lookups), we'd have a mistaken version.
204 //
205 // Error paths through this code will default the version to 1.1.
206 t.version = ver11
207 208 if !disableRecover {
209 defer func() {
210 // If we panic parsing, assume it's a Go 1.1 pclntab.
211 recover()
212 }()
213 }
214 215 // Check header: 4-byte magic, two zeros, pc quantum, pointer size.
216 if len(t.Data) < 16 || t.Data[4] != 0 || t.Data[5] != 0 ||
217 (t.Data[6] != 1 && t.Data[6] != 2 && t.Data[6] != 4) || // pc quantum
218 (t.Data[7] != 4 && t.Data[7] != 8) { // pointer size
219 return
220 }
221 222 var possibleVersion version
223 leMagic := binary.LittleEndian.Uint32(t.Data)
224 beMagic := binary.BigEndian.Uint32(t.Data)
225 switch {
226 case leMagic == go12magic:
227 t.binary, possibleVersion = binary.LittleEndian, ver12
228 case beMagic == go12magic:
229 t.binary, possibleVersion = binary.BigEndian, ver12
230 case leMagic == go116magic:
231 t.binary, possibleVersion = binary.LittleEndian, ver116
232 case beMagic == go116magic:
233 t.binary, possibleVersion = binary.BigEndian, ver116
234 case leMagic == go118magic:
235 t.binary, possibleVersion = binary.LittleEndian, ver118
236 case beMagic == go118magic:
237 t.binary, possibleVersion = binary.BigEndian, ver118
238 case leMagic == go120magic:
239 t.binary, possibleVersion = binary.LittleEndian, ver120
240 case beMagic == go120magic:
241 t.binary, possibleVersion = binary.BigEndian, ver120
242 default:
243 return
244 }
245 t.version = possibleVersion
246 247 // quantum and ptrSize are the same between 1.2, 1.16, and 1.18
248 t.quantum = uint32(t.Data[6])
249 t.ptrsize = uint32(t.Data[7])
250 251 offset := func(word uint32) uint64 {
252 return t.uintptr(t.Data[8+word*t.ptrsize:])
253 }
254 data := func(word uint32) []byte {
255 return t.Data[offset(word):]
256 }
257 258 switch possibleVersion {
259 case ver118, ver120:
260 t.nfunctab = uint32(offset(0))
261 t.nfiletab = uint32(offset(1))
262 t.textStart = t.PC // use the start PC instead of reading from the table, which may be unrelocated
263 t.funcnametab = data(3)
264 t.cutab = data(4)
265 t.filetab = data(5)
266 t.pctab = data(6)
267 t.funcdata = data(7)
268 t.functab = data(7)
269 functabsize := (int(t.nfunctab)*2 + 1) * t.functabFieldSize()
270 t.functab = t.functab[:functabsize]
271 case ver116:
272 t.nfunctab = uint32(offset(0))
273 t.nfiletab = uint32(offset(1))
274 t.funcnametab = data(2)
275 t.cutab = data(3)
276 t.filetab = data(4)
277 t.pctab = data(5)
278 t.funcdata = data(6)
279 t.functab = data(6)
280 functabsize := (int(t.nfunctab)*2 + 1) * t.functabFieldSize()
281 t.functab = t.functab[:functabsize]
282 case ver12:
283 t.nfunctab = uint32(t.uintptr(t.Data[8:]))
284 t.funcdata = t.Data
285 t.funcnametab = t.Data
286 t.functab = t.Data[8+t.ptrsize:]
287 t.pctab = t.Data
288 functabsize := (int(t.nfunctab)*2 + 1) * t.functabFieldSize()
289 fileoff := t.binary.Uint32(t.functab[functabsize:])
290 t.functab = t.functab[:functabsize]
291 t.filetab = t.Data[fileoff:]
292 t.nfiletab = t.binary.Uint32(t.filetab)
293 t.filetab = t.filetab[:t.nfiletab*4]
294 default:
295 panic("unreachable")
296 }
297 }
298 299 // go12Funcs returns a slice of Funcs derived from the Go 1.2+ pcln table.
300 func (t *LineTable) go12Funcs() []Func {
301 // Assume it is malformed and return nil on error.
302 if !disableRecover {
303 defer func() {
304 recover()
305 }()
306 }
307 308 ft := t.funcTab()
309 funcs := []Func{:ft.Count()}
310 syms := []Sym{:len(funcs)}
311 for i := range funcs {
312 f := &funcs[i]
313 f.Entry = ft.pc(i)
314 f.End = ft.pc(i + 1)
315 info := t.funcData(uint32(i))
316 f.LineTable = t
317 f.FrameSize = int(info.deferreturn())
318 syms[i] = Sym{
319 Value: f.Entry,
320 Type: 'T',
321 Name: t.funcName(info.nameOff()),
322 GoType: 0,
323 Func: f,
324 goVersion: t.version,
325 }
326 f.Sym = &syms[i]
327 }
328 return funcs
329 }
330 331 // findFunc returns the funcData corresponding to the given program counter.
332 func (t *LineTable) findFunc(pc uint64) funcData {
333 ft := t.funcTab()
334 if pc < ft.pc(0) || pc >= ft.pc(ft.Count()) {
335 return funcData{}
336 }
337 idx := sort.Search(int(t.nfunctab), func(i int) bool {
338 return ft.pc(i) > pc
339 })
340 idx--
341 return t.funcData(uint32(idx))
342 }
343 344 // readvarint reads, removes, and returns a varint from *pp.
345 func (t *LineTable) readvarint(pp *[]byte) uint32 {
346 var v, shift uint32
347 p := *pp
348 for shift = 0; ; shift += 7 {
349 b := p[0]
350 p = p[1:]
351 v |= (uint32(b) & 0x7F) << shift
352 if b&0x80 == 0 {
353 break
354 }
355 }
356 *pp = p
357 return v
358 }
359 360 // funcName returns the name of the function found at off.
361 func (t *LineTable) funcName(off uint32) string {
362 if s, ok := t.funcNames[off]; ok {
363 return s
364 }
365 i := bytes.IndexByte(t.funcnametab[off:], 0)
366 s := string(t.funcnametab[off : off+uint32(i)])
367 t.funcNames[off] = s
368 return s
369 }
370 371 // stringFrom returns a Go string found at off from a position.
372 func (t *LineTable) stringFrom(arr []byte, off uint32) string {
373 if s, ok := t.strings[off]; ok {
374 return s
375 }
376 i := bytes.IndexByte(arr[off:], 0)
377 s := string(arr[off : off+uint32(i)])
378 t.strings[off] = s
379 return s
380 }
381 382 // string returns a Go string found at off.
383 func (t *LineTable) string(off uint32) string {
384 return t.stringFrom(t.funcdata, off)
385 }
386 387 // functabFieldSize returns the size in bytes of a single functab field.
388 func (t *LineTable) functabFieldSize() int {
389 if t.version >= ver118 {
390 return 4
391 }
392 return int(t.ptrsize)
393 }
394 395 // funcTab returns t's funcTab.
396 func (t *LineTable) funcTab() funcTab {
397 return funcTab{LineTable: t, sz: t.functabFieldSize()}
398 }
399 400 // funcTab is memory corresponding to a slice of functab structs, followed by an invalid PC.
401 // A functab struct is a PC and a func offset.
402 type funcTab struct {
403 *LineTable
404 sz int // cached result of t.functabFieldSize
405 }
406 407 // Count returns the number of func entries in f.
408 func (f funcTab) Count() int {
409 return int(f.nfunctab)
410 }
411 412 // pc returns the PC of the i'th func in f.
413 func (f funcTab) pc(i int) uint64 {
414 u := f.uint(f.functab[2*i*f.sz:])
415 if f.version >= ver118 {
416 u += f.textStart
417 }
418 return u
419 }
420 421 // funcOff returns the funcdata offset of the i'th func in f.
422 func (f funcTab) funcOff(i int) uint64 {
423 return f.uint(f.functab[(2*i+1)*f.sz:])
424 }
425 426 // uint returns the uint stored at b.
427 func (f funcTab) uint(b []byte) uint64 {
428 if f.sz == 4 {
429 return uint64(f.binary.Uint32(b))
430 }
431 return f.binary.Uint64(b)
432 }
433 434 // funcData is memory corresponding to an _func struct.
435 type funcData struct {
436 t *LineTable // LineTable this data is a part of
437 data []byte // raw memory for the function
438 }
439 440 // funcData returns the ith funcData in t.functab.
441 func (t *LineTable) funcData(i uint32) funcData {
442 data := t.funcdata[t.funcTab().funcOff(int(i)):]
443 return funcData{t: t, data: data}
444 }
445 446 // IsZero reports whether f is the zero value.
447 func (f funcData) IsZero() bool {
448 return f.t == nil && f.data == nil
449 }
450 451 // entryPC returns the func's entry PC.
452 func (f *funcData) entryPC() uint64 {
453 // In Go 1.18, the first field of _func changed
454 // from a uintptr entry PC to a uint32 entry offset.
455 if f.t.version >= ver118 {
456 // TODO: support multiple text sections.
457 // See runtime/symtab.go:(*moduledata).textAddr.
458 return uint64(f.t.binary.Uint32(f.data)) + f.t.textStart
459 }
460 return f.t.uintptr(f.data)
461 }
462 463 func (f funcData) nameOff() uint32 { return f.field(1) }
464 func (f funcData) deferreturn() uint32 { return f.field(3) }
465 func (f funcData) pcfile() uint32 { return f.field(5) }
466 func (f funcData) pcln() uint32 { return f.field(6) }
467 func (f funcData) cuOffset() uint32 { return f.field(8) }
468 469 // field returns the nth field of the _func struct.
470 // It panics if n == 0 or n > 9; for n == 0, call f.entryPC.
471 // Most callers should use a named field accessor (just above).
472 func (f funcData) field(n uint32) uint32 {
473 if n == 0 || n > 9 {
474 panic("bad funcdata field")
475 }
476 // In Go 1.18, the first field of _func changed
477 // from a uintptr entry PC to a uint32 entry offset.
478 sz0 := f.t.ptrsize
479 if f.t.version >= ver118 {
480 sz0 = 4
481 }
482 off := sz0 + (n-1)*4 // subsequent fields are 4 bytes each
483 data := f.data[off:]
484 return f.t.binary.Uint32(data)
485 }
486 487 // step advances to the next pc, value pair in the encoded table.
488 func (t *LineTable) step(p *[]byte, pc *uint64, val *int32, first bool) bool {
489 uvdelta := t.readvarint(p)
490 if uvdelta == 0 && !first {
491 return false
492 }
493 if uvdelta&1 != 0 {
494 uvdelta = ^(uvdelta >> 1)
495 } else {
496 uvdelta >>= 1
497 }
498 vdelta := int32(uvdelta)
499 pcdelta := t.readvarint(p) * t.quantum
500 *pc += uint64(pcdelta)
501 *val += vdelta
502 return true
503 }
504 505 // pcvalue reports the value associated with the target pc.
506 // off is the offset to the beginning of the pc-value table,
507 // and entry is the start PC for the corresponding function.
508 func (t *LineTable) pcvalue(off uint32, entry, targetpc uint64) int32 {
509 p := t.pctab[off:]
510 511 val := int32(-1)
512 pc := entry
513 for t.step(&p, &pc, &val, pc == entry) {
514 if targetpc < pc {
515 return val
516 }
517 }
518 return -1
519 }
520 521 // findFileLine scans one function in the binary looking for a
522 // program counter in the given file on the given line.
523 // It does so by running the pc-value tables mapping program counter
524 // to file number. Since most functions come from a single file, these
525 // are usually short and quick to scan. If a file match is found, then the
526 // code goes to the expense of looking for a simultaneous line number match.
527 func (t *LineTable) findFileLine(entry uint64, filetab, linetab uint32, filenum, line int32, cutab []byte) uint64 {
528 if filetab == 0 || linetab == 0 {
529 return 0
530 }
531 532 fp := t.pctab[filetab:]
533 fl := t.pctab[linetab:]
534 fileVal := int32(-1)
535 filePC := entry
536 lineVal := int32(-1)
537 linePC := entry
538 fileStartPC := filePC
539 for t.step(&fp, &filePC, &fileVal, filePC == entry) {
540 fileIndex := fileVal
541 if t.version == ver116 || t.version == ver118 || t.version == ver120 {
542 fileIndex = int32(t.binary.Uint32(cutab[fileVal*4:]))
543 }
544 if fileIndex == filenum && fileStartPC < filePC {
545 // fileIndex is in effect starting at fileStartPC up to
546 // but not including filePC, and it's the file we want.
547 // Run the PC table looking for a matching line number
548 // or until we reach filePC.
549 lineStartPC := linePC
550 for linePC < filePC && t.step(&fl, &linePC, &lineVal, linePC == entry) {
551 // lineVal is in effect until linePC, and lineStartPC < filePC.
552 if lineVal == line {
553 if fileStartPC <= lineStartPC {
554 return lineStartPC
555 }
556 if fileStartPC < linePC {
557 return fileStartPC
558 }
559 }
560 lineStartPC = linePC
561 }
562 }
563 fileStartPC = filePC
564 }
565 return 0
566 }
567 568 // go12PCToLine maps program counter to line number for the Go 1.2+ pcln table.
569 func (t *LineTable) go12PCToLine(pc uint64) (line int) {
570 defer func() {
571 if !disableRecover && recover() != nil {
572 line = -1
573 }
574 }()
575 576 f := t.findFunc(pc)
577 if f.IsZero() {
578 return -1
579 }
580 entry := f.entryPC()
581 linetab := f.pcln()
582 return int(t.pcvalue(linetab, entry, pc))
583 }
584 585 // go12PCToFile maps program counter to file name for the Go 1.2+ pcln table.
586 func (t *LineTable) go12PCToFile(pc uint64) (file string) {
587 defer func() {
588 if !disableRecover && recover() != nil {
589 file = ""
590 }
591 }()
592 593 f := t.findFunc(pc)
594 if f.IsZero() {
595 return ""
596 }
597 entry := f.entryPC()
598 filetab := f.pcfile()
599 fno := t.pcvalue(filetab, entry, pc)
600 if t.version == ver12 {
601 if fno <= 0 {
602 return ""
603 }
604 return t.string(t.binary.Uint32(t.filetab[4*fno:]))
605 }
606 // Go ≥ 1.16
607 if fno < 0 { // 0 is valid for ≥ 1.16
608 return ""
609 }
610 cuoff := f.cuOffset()
611 if fnoff := t.binary.Uint32(t.cutab[(cuoff+uint32(fno))*4:]); fnoff != ^uint32(0) {
612 return t.stringFrom(t.filetab, fnoff)
613 }
614 return ""
615 }
616 617 // go12LineToPC maps a (file, line) pair to a program counter for the Go 1.2+ pcln table.
618 func (t *LineTable) go12LineToPC(file string, line int) (pc uint64) {
619 defer func() {
620 if !disableRecover && recover() != nil {
621 pc = 0
622 }
623 }()
624 625 t.initFileMap()
626 filenum, ok := t.fileMap[file]
627 if !ok {
628 return 0
629 }
630 631 // Scan all functions.
632 // If this turns out to be a bottleneck, we could build a map[int32][]int32
633 // mapping file number to a list of functions with code from that file.
634 var cutab []byte
635 for i := uint32(0); i < t.nfunctab; i++ {
636 f := t.funcData(i)
637 entry := f.entryPC()
638 filetab := f.pcfile()
639 linetab := f.pcln()
640 if t.version == ver116 || t.version == ver118 || t.version == ver120 {
641 if f.cuOffset() == ^uint32(0) {
642 // skip functions without compilation unit (not real function, or linker generated)
643 continue
644 }
645 cutab = t.cutab[f.cuOffset()*4:]
646 }
647 pc := t.findFileLine(entry, filetab, linetab, int32(filenum), int32(line), cutab)
648 if pc != 0 {
649 return pc
650 }
651 }
652 return 0
653 }
654 655 // initFileMap initializes the map from file name to file number.
656 func (t *LineTable) initFileMap() {
657 t.mu.Lock()
658 defer t.mu.Unlock()
659 660 if t.fileMap != nil {
661 return
662 }
663 m := map[string]uint32{}
664 665 if t.version == ver12 {
666 for i := uint32(1); i < t.nfiletab; i++ {
667 s := t.string(t.binary.Uint32(t.filetab[4*i:]))
668 m[s] = i
669 }
670 } else {
671 var pos uint32
672 for i := uint32(0); i < t.nfiletab; i++ {
673 s := t.stringFrom(t.filetab, pos)
674 m[s] = pos
675 pos += uint32(len(s) + 1)
676 }
677 }
678 t.fileMap = m
679 }
680 681 // go12MapFiles adds to m a key for every file in the Go 1.2 LineTable.
682 // Every key maps to obj. That's not a very interesting map, but it provides
683 // a way for callers to obtain the list of files in the program.
684 func (t *LineTable) go12MapFiles(m map[string]*Obj, obj *Obj) {
685 if !disableRecover {
686 defer func() {
687 recover()
688 }()
689 }
690 691 t.initFileMap()
692 for file := range t.fileMap {
693 m[file] = obj
694 }
695 }
696 697 // disableRecover causes this package not to swallow panics.
698 // This is useful when making changes.
699 const disableRecover = false
700