| // Copyright 2018 Google Inc. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| /* |
| * Line tables |
| */ |
| |
| package gosym |
| |
| import ( |
| "encoding/binary" |
| "sync" |
| ) |
| |
| // A LineTable is a data structure mapping program counters to line numbers. |
| // |
| // In Go 1.1 and earlier, each function (represented by a Func) had its own LineTable, |
| // and the line number corresponded to a numbering of all source lines in the |
| // program, across all files. That absolute line number would then have to be |
| // converted separately to a file name and line number within the file. |
| // |
| // In Go 1.2, the format of the data changed so that there is a single LineTable |
| // for the entire program, shared by all Funcs, and there are no absolute line |
| // numbers, just line numbers within specific files. |
| // |
| // For the most part, LineTable's methods should be treated as an internal |
| // detail of the package; callers should use the methods on Table instead. |
| type LineTable struct { |
| Data []byte |
| PC uint64 |
| Line int |
| |
| // Go 1.2 state |
| mu sync.Mutex |
| go12 int // is this in Go 1.2 format? -1 no, 0 unknown, 1 yes |
| binary binary.ByteOrder |
| quantum uint32 |
| ptrsize uint32 |
| functab []byte |
| nfunctab uint32 |
| filetab []byte |
| nfiletab uint32 |
| fileMap map[string]uint32 |
| } |
| |
| // NOTE(rsc): This is wrong for GOARCH=arm, which uses a quantum of 4, |
| // but we have no idea whether we're using arm or not. This only |
| // matters in the old (pre-Go 1.2) symbol table format, so it's not worth |
| // fixing. |
| const oldQuantum = 1 |
| |
| func (t *LineTable) parse(targetPC uint64, targetLine int) (b []byte, pc uint64, line int) { |
| // The PC/line table can be thought of as a sequence of |
| // <pc update>* <line update> |
| // batches. Each update batch results in a (pc, line) pair, |
| // where line applies to every PC from pc up to but not |
| // including the pc of the next pair. |
| // |
| // Here we process each update individually, which simplifies |
| // the code, but makes the corner cases more confusing. |
| b, pc, line = t.Data, t.PC, t.Line |
| for pc <= targetPC && line != targetLine && len(b) > 0 { |
| code := b[0] |
| b = b[1:] |
| switch { |
| case code == 0: |
| if len(b) < 4 { |
| b = b[0:0] |
| break |
| } |
| val := binary.BigEndian.Uint32(b) |
| b = b[4:] |
| line += int(val) |
| case code <= 64: |
| line += int(code) |
| case code <= 128: |
| line -= int(code - 64) |
| default: |
| pc += oldQuantum * uint64(code-128) |
| continue |
| } |
| pc += oldQuantum |
| } |
| return b, pc, line |
| } |
| |
| func (t *LineTable) slice(pc uint64) *LineTable { |
| data, pc, line := t.parse(pc, -1) |
| return &LineTable{Data: data, PC: pc, Line: line} |
| } |
| |
| // PCToLine returns the line number for the given program counter. |
| // Callers should use Table's PCToLine method instead. |
| func (t *LineTable) PCToLine(pc uint64) int { |
| if t.isGo12() { |
| return t.go12PCToLine(pc) |
| } |
| _, _, line := t.parse(pc, -1) |
| return line |
| } |
| |
| // LineToPC returns the program counter for the given line number, |
| // considering only program counters before maxpc. |
| // Callers should use Table's LineToPC method instead. |
| func (t *LineTable) LineToPC(line int, maxpc uint64) uint64 { |
| if t.isGo12() { |
| return 0 |
| } |
| _, pc, line1 := t.parse(maxpc, line) |
| if line1 != line { |
| return 0 |
| } |
| // Subtract quantum from PC to account for post-line increment |
| return pc - oldQuantum |
| } |
| |
| // NewLineTable returns a new PC/line table |
| // corresponding to the encoded data. |
| // Text must be the start address of the |
| // corresponding text segment. |
| func NewLineTable(data []byte, text uint64) *LineTable { |
| return &LineTable{Data: data, PC: text, Line: 0} |
| } |
| |
| // Go 1.2 symbol table format. |
| // See golang.org/s/go12symtab. |
| // |
| // A general note about the methods here: rather than try to avoid |
| // index out of bounds errors, we trust Go to detect them, and then |
| // we recover from the panics and treat them as indicative of a malformed |
| // or incomplete table. |
| // |
| // The methods called by symtab.go, which begin with "go12" prefixes, |
| // are expected to have that recovery logic. |
| |
| // isGo12 reports whether this is a Go 1.2 (or later) symbol table. |
| func (t *LineTable) isGo12() bool { |
| t.go12Init() |
| return t.go12 == 1 |
| } |
| |
| const go12magic = 0xfffffffb |
| |
| // uintptr returns the pointer-sized value encoded at b. |
| // The pointer size is dictated by the table being read. |
| func (t *LineTable) uintptr(b []byte) uint64 { |
| if t.ptrsize == 4 { |
| return uint64(t.binary.Uint32(b)) |
| } |
| return t.binary.Uint64(b) |
| } |
| |
| // go12init initializes the Go 1.2 metadata if t is a Go 1.2 symbol table. |
| func (t *LineTable) go12Init() { |
| t.mu.Lock() |
| defer t.mu.Unlock() |
| if t.go12 != 0 { |
| return |
| } |
| |
| defer func() { |
| // If we panic parsing, assume it's not a Go 1.2 symbol table. |
| recover() |
| }() |
| |
| // Check header: 4-byte magic, two zeros, pc quantum, pointer size. |
| t.go12 = -1 // not Go 1.2 until proven otherwise |
| if len(t.Data) < 16 || t.Data[4] != 0 || t.Data[5] != 0 || |
| (t.Data[6] != 1 && t.Data[6] != 4) || // pc quantum |
| (t.Data[7] != 4 && t.Data[7] != 8) { // pointer size |
| return |
| } |
| |
| switch uint32(go12magic) { |
| case binary.LittleEndian.Uint32(t.Data): |
| t.binary = binary.LittleEndian |
| case binary.BigEndian.Uint32(t.Data): |
| t.binary = binary.BigEndian |
| default: |
| return |
| } |
| |
| t.quantum = uint32(t.Data[6]) |
| t.ptrsize = uint32(t.Data[7]) |
| |
| t.nfunctab = uint32(t.uintptr(t.Data[8:])) |
| t.functab = t.Data[8+t.ptrsize:] |
| functabsize := t.nfunctab*2*t.ptrsize + t.ptrsize |
| fileoff := t.binary.Uint32(t.functab[functabsize:]) |
| t.functab = t.functab[:functabsize] |
| t.filetab = t.Data[fileoff:] |
| t.nfiletab = t.binary.Uint32(t.filetab) |
| t.filetab = t.filetab[:t.nfiletab*4] |
| |
| t.go12 = 1 // so far so good |
| } |
| |
| // go12Funcs returns a slice of Funcs derived from the Go 1.2 pcln table. |
| func (t *LineTable) go12Funcs() []Func { |
| // Assume it is malformed and return nil on error. |
| defer func() { |
| recover() |
| }() |
| |
| n := len(t.functab) / int(t.ptrsize) / 2 |
| funcs := make([]Func, n) |
| for i := range funcs { |
| f := &funcs[i] |
| f.Entry = uint64(t.uintptr(t.functab[2*i*int(t.ptrsize):])) |
| f.End = uint64(t.uintptr(t.functab[(2*i+2)*int(t.ptrsize):])) |
| info := t.Data[t.uintptr(t.functab[(2*i+1)*int(t.ptrsize):]):] |
| f.LineTable = t |
| f.FrameSize = int(t.binary.Uint32(info[t.ptrsize+2*4:])) |
| f.Sym = &Sym{ |
| Value: f.Entry, |
| Type: 'T', |
| Name: t.string(t.binary.Uint32(info[t.ptrsize:])), |
| GoType: 0, |
| Func: f, |
| } |
| } |
| return funcs |
| } |
| |
| // findFunc returns the func corresponding to the given program counter. |
| func (t *LineTable) findFunc(pc uint64) []byte { |
| if pc < t.uintptr(t.functab) || pc >= t.uintptr(t.functab[len(t.functab)-int(t.ptrsize):]) { |
| return nil |
| } |
| |
| // The function table is a list of 2*nfunctab+1 uintptrs, |
| // alternating program counters and offsets to func structures. |
| f := t.functab |
| nf := t.nfunctab |
| for nf > 0 { |
| m := nf / 2 |
| fm := f[2*t.ptrsize*m:] |
| if t.uintptr(fm) <= pc && pc < t.uintptr(fm[2*t.ptrsize:]) { |
| return t.Data[t.uintptr(fm[t.ptrsize:]):] |
| } else if pc < t.uintptr(fm) { |
| nf = m |
| } else { |
| f = f[(m+1)*2*t.ptrsize:] |
| nf -= m + 1 |
| } |
| } |
| return nil |
| } |
| |
| // readvarint reads, removes, and returns a varint from *pp. |
| func (t *LineTable) readvarint(pp *[]byte) uint32 { |
| var v, shift uint32 |
| p := *pp |
| for shift = 0; ; shift += 7 { |
| b := p[0] |
| p = p[1:] |
| v |= (uint32(b) & 0x7F) << shift |
| if b&0x80 == 0 { |
| break |
| } |
| } |
| *pp = p |
| return v |
| } |
| |
| // string returns a Go string found at off. |
| func (t *LineTable) string(off uint32) string { |
| for i := off; ; i++ { |
| if t.Data[i] == 0 { |
| return string(t.Data[off:i]) |
| } |
| } |
| } |
| |
| // step advances to the next pc, value pair in the encoded table. |
| func (t *LineTable) step(p *[]byte, pc *uint64, val *int32, first bool) bool { |
| uvdelta := t.readvarint(p) |
| if uvdelta == 0 && !first { |
| return false |
| } |
| if uvdelta&1 != 0 { |
| uvdelta = ^(uvdelta >> 1) |
| } else { |
| uvdelta >>= 1 |
| } |
| vdelta := int32(uvdelta) |
| pcdelta := t.readvarint(p) * t.quantum |
| *pc += uint64(pcdelta) |
| *val += vdelta |
| return true |
| } |
| |
| // pcvalue reports the value associated with the target pc. |
| // off is the offset to the beginning of the pc-value table, |
| // and entry is the start PC for the corresponding function. |
| func (t *LineTable) pcvalue(off uint32, entry, targetpc uint64) int32 { |
| if off == 0 { |
| return -1 |
| } |
| p := t.Data[off:] |
| |
| val := int32(-1) |
| pc := entry |
| for t.step(&p, &pc, &val, pc == entry) { |
| if targetpc < pc { |
| return val |
| } |
| } |
| return -1 |
| } |
| |
| // findFileLine scans one function in the binary looking for a |
| // program counter in the given file on the given line. |
| // It does so by running the pc-value tables mapping program counter |
| // to file number. Since most functions come from a single file, these |
| // are usually short and quick to scan. If a file match is found, then the |
| // code goes to the expense of looking for a simultaneous line number match. |
| func (t *LineTable) findFileLine(entry uint64, filetab, linetab uint32, filenum, line int32) uint64 { |
| if filetab == 0 || linetab == 0 { |
| return 0 |
| } |
| |
| fp := t.Data[filetab:] |
| fl := t.Data[linetab:] |
| fileVal := int32(-1) |
| filePC := entry |
| lineVal := int32(-1) |
| linePC := entry |
| fileStartPC := filePC |
| for t.step(&fp, &filePC, &fileVal, filePC == entry) { |
| if fileVal == filenum && fileStartPC < filePC { |
| // fileVal is in effect starting at fileStartPC up to |
| // but not including filePC, and it's the file we want. |
| // Run the PC table looking for a matching line number |
| // or until we reach filePC. |
| lineStartPC := linePC |
| for linePC < filePC && t.step(&fl, &linePC, &lineVal, linePC == entry) { |
| // lineVal is in effect until linePC, and lineStartPC < filePC. |
| if lineVal == line { |
| if fileStartPC <= lineStartPC { |
| return lineStartPC |
| } |
| if fileStartPC < linePC { |
| return fileStartPC |
| } |
| } |
| lineStartPC = linePC |
| } |
| } |
| fileStartPC = filePC |
| } |
| return 0 |
| } |
| |
| // go12PCToLine maps program counter to line number for the Go 1.2 pcln table. |
| func (t *LineTable) go12PCToLine(pc uint64) (line int) { |
| return t.go12PCToVal(pc, t.ptrsize+5*4) |
| } |
| |
| // go12PCToSPAdj maps program counter to Stack Pointer adjustment for the Go 1.2 pcln table. |
| func (t *LineTable) go12PCToSPAdj(pc uint64) (spadj int) { |
| return t.go12PCToVal(pc, t.ptrsize+3*4) |
| } |
| |
| func (t *LineTable) go12PCToVal(pc uint64, fOffset uint32) (val int) { |
| defer func() { |
| if recover() != nil { |
| val = -1 |
| } |
| }() |
| |
| f := t.findFunc(pc) |
| if f == nil { |
| return -1 |
| } |
| entry := t.uintptr(f) |
| linetab := t.binary.Uint32(f[fOffset:]) |
| return int(t.pcvalue(linetab, entry, pc)) |
| } |
| |
| // go12PCToFile maps program counter to file name for the Go 1.2 pcln table. |
| func (t *LineTable) go12PCToFile(pc uint64) (file string) { |
| defer func() { |
| if recover() != nil { |
| file = "" |
| } |
| }() |
| |
| f := t.findFunc(pc) |
| if f == nil { |
| return "" |
| } |
| entry := t.uintptr(f) |
| filetab := t.binary.Uint32(f[t.ptrsize+4*4:]) |
| fno := t.pcvalue(filetab, entry, pc) |
| if fno <= 0 { |
| return "" |
| } |
| return t.string(t.binary.Uint32(t.filetab[4*fno:])) |
| } |
| |
| // go12LineToPC maps a (file, line) pair to a program counter for the Go 1.2 pcln table. |
| func (t *LineTable) go12LineToPC(file string, line int) (pc uint64) { |
| defer func() { |
| if recover() != nil { |
| pc = 0 |
| } |
| }() |
| |
| t.initFileMap() |
| filenum := t.fileMap[file] |
| if filenum == 0 { |
| return 0 |
| } |
| |
| // Scan all functions. |
| // If this turns out to be a bottleneck, we could build a map[int32][]int32 |
| // mapping file number to a list of functions with code from that file. |
| for i := uint32(0); i < t.nfunctab; i++ { |
| f := t.Data[t.uintptr(t.functab[2*t.ptrsize*i+t.ptrsize:]):] |
| entry := t.uintptr(f) |
| filetab := t.binary.Uint32(f[t.ptrsize+4*4:]) |
| linetab := t.binary.Uint32(f[t.ptrsize+5*4:]) |
| pc := t.findFileLine(entry, filetab, linetab, int32(filenum), int32(line)) |
| if pc != 0 { |
| return pc |
| } |
| } |
| return 0 |
| } |
| |
| // initFileMap initializes the map from file name to file number. |
| func (t *LineTable) initFileMap() { |
| t.mu.Lock() |
| defer t.mu.Unlock() |
| |
| if t.fileMap != nil { |
| return |
| } |
| m := make(map[string]uint32) |
| |
| for i := uint32(1); i < t.nfiletab; i++ { |
| s := t.string(t.binary.Uint32(t.filetab[4*i:])) |
| m[s] = i |
| } |
| t.fileMap = m |
| } |
| |
| // go12MapFiles adds to m a key for every file in the Go 1.2 LineTable. |
| // Every key maps to obj. That's not a very interesting map, but it provides |
| // a way for callers to obtain the list of files in the program. |
| func (t *LineTable) go12MapFiles(m map[string]*Obj, obj *Obj) { |
| defer func() { |
| recover() |
| }() |
| |
| t.initFileMap() |
| for file := range t.fileMap { |
| m[file] = obj |
| } |
| } |