[gostls13.git] / src / debug / gosym / pclntab.go

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

/*
 * Line tables
 */

package gosym

import (
        "bytes"
        "encoding/binary"
        "sort"
        "sync"
)

// version of the pclntab
type version int

const (
        verUnknown version = iota
        ver11
        ver12
        ver116
        ver118
)

// 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

        // This mutex is used to keep parsing of pclntab synchronous.
        mu sync.Mutex

        // Contains the version of the pclntab section.
        version version

        // Go 1.2/1.16/1.18 state
        binary      binary.ByteOrder
        quantum     uint32
        ptrsize     uint32
        textStart   uint64 // address of runtime.text symbol (1.18+)
        funcnametab []byte
        cutab       []byte
        funcdata    []byte
        functab     []byte
        nfunctab    uint32
        filetab     []byte
        pctab       []byte // points to the pctables.
        nfiletab    uint32
        funcNames   map[uint32]string // cache the function names
        strings     map[uint32]string // interned substrings of Data, keyed by offset
        // fileMap varies depending on the version of the object file.
        // For ver12, it maps the name to the index in the file table.
        // For ver116, it maps the name to the offset in filetab.
        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.
//
// Deprecated: 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.
//
// Deprecated: 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, funcNames: make(map[uint32]string), strings: make(map[uint32]string)}
}

// 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.parsePclnTab()
        return t.version >= ver12
}

const (
        go12magic  = 0xfffffffb
        go116magic = 0xfffffffa
        go118magic = 0xfffffff0
)

// 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)
}

// parsePclnTab parses the pclntab, setting the version.
func (t *LineTable) parsePclnTab() {
        t.mu.Lock()
        defer t.mu.Unlock()
        if t.version != verUnknown {
                return
        }

        // Note that during this function, setting the version is the last thing we do.
        // If we set the version too early, and parsing failed (likely as a panic on
        // slice lookups), we'd have a mistaken version.
        //
        // Error paths through this code will default the version to 1.1.
        t.version = ver11

        if !disableRecover {
                defer func() {
                        // If we panic parsing, assume it's a Go 1.1 pclntab.
                        recover()
                }()
        }

        // Check header: 4-byte magic, two zeros, pc quantum, pointer size.
        if len(t.Data) < 16 || t.Data[4] != 0 || t.Data[5] != 0 ||
                (t.Data[6] != 1 && t.Data[6] != 2 && t.Data[6] != 4) || // pc quantum
                (t.Data[7] != 4 && t.Data[7] != 8) { // pointer size
                return
        }

        var possibleVersion version
        leMagic := binary.LittleEndian.Uint32(t.Data)
        beMagic := binary.BigEndian.Uint32(t.Data)
        switch {
        case leMagic == go12magic:
                t.binary, possibleVersion = binary.LittleEndian, ver12
        case beMagic == go12magic:
                t.binary, possibleVersion = binary.BigEndian, ver12
        case leMagic == go116magic:
                t.binary, possibleVersion = binary.LittleEndian, ver116
        case beMagic == go116magic:
                t.binary, possibleVersion = binary.BigEndian, ver116
        case leMagic == go118magic:
                t.binary, possibleVersion = binary.LittleEndian, ver118
        case beMagic == go118magic:
                t.binary, possibleVersion = binary.BigEndian, ver118
        default:
                return
        }
        t.version = possibleVersion

        // quantum and ptrSize are the same between 1.2, 1.16, and 1.18
        t.quantum = uint32(t.Data[6])
        t.ptrsize = uint32(t.Data[7])

        offset := func(word uint32) uint64 {
                return t.uintptr(t.Data[8+word*t.ptrsize:])
        }
        data := func(word uint32) []byte {
                return t.Data[offset(word):]
        }

        switch possibleVersion {
        case ver118:
                t.nfunctab = uint32(offset(0))
                t.nfiletab = uint32(offset(1))
                t.textStart = t.PC // use the start PC instead of reading from the table, which may be unrelocated
                t.funcnametab = data(3)
                t.cutab = data(4)
                t.filetab = data(5)
                t.pctab = data(6)
                t.funcdata = data(7)
                t.functab = data(7)
                functabsize := (int(t.nfunctab)*2 + 1) * t.functabFieldSize()
                t.functab = t.functab[:functabsize]
        case ver116:
                t.nfunctab = uint32(offset(0))
                t.nfiletab = uint32(offset(1))
                t.funcnametab = data(2)
                t.cutab = data(3)
                t.filetab = data(4)
                t.pctab = data(5)
                t.funcdata = data(6)
                t.functab = data(6)
                functabsize := (int(t.nfunctab)*2 + 1) * t.functabFieldSize()
                t.functab = t.functab[:functabsize]
        case ver12:
                t.nfunctab = uint32(t.uintptr(t.Data[8:]))
                t.funcdata = t.Data
                t.funcnametab = t.Data
                t.functab = t.Data[8+t.ptrsize:]
                t.pctab = t.Data
                functabsize := (int(t.nfunctab)*2 + 1) * t.functabFieldSize()
                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]
        default:
                panic("unreachable")
        }
}

// 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.
        if !disableRecover {
                defer func() {
                        recover()
                }()
        }

        ft := t.funcTab()
        funcs := make([]Func, ft.Count())
        syms := make([]Sym, len(funcs))
        for i := range funcs {
                f := &funcs[i]
                f.Entry = ft.pc(i)
                f.End = ft.pc(i + 1)
                info := t.funcData(uint32(i))
                f.LineTable = t
                f.FrameSize = int(info.deferreturn())
                syms[i] = Sym{
                        Value:  f.Entry,
                        Type:   'T',
                        Name:   t.funcName(info.nameoff()),
                        GoType: 0,
                        Func:   f,
                }
                f.Sym = &syms[i]
        }
        return funcs
}

// findFunc returns the funcData corresponding to the given program counter.
func (t *LineTable) findFunc(pc uint64) funcData {
        ft := t.funcTab()
        if pc < ft.pc(0) || pc >= ft.pc(ft.Count()) {
                return funcData{}
        }
        idx := sort.Search(int(t.nfunctab), func(i int) bool {
                return ft.pc(i) > pc
        })
        idx--
        return t.funcData(uint32(idx))
}

// 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
}

// funcName returns the name of the function found at off.
func (t *LineTable) funcName(off uint32) string {
        if s, ok := t.funcNames[off]; ok {
                return s
        }
        i := bytes.IndexByte(t.funcnametab[off:], 0)
        s := string(t.funcnametab[off : off+uint32(i)])
        t.funcNames[off] = s
        return s
}

// stringFrom returns a Go string found at off from a position.
func (t *LineTable) stringFrom(arr []byte, off uint32) string {
        if s, ok := t.strings[off]; ok {
                return s
        }
        i := bytes.IndexByte(arr[off:], 0)
        s := string(arr[off : off+uint32(i)])
        t.strings[off] = s
        return s
}

// string returns a Go string found at off.
func (t *LineTable) string(off uint32) string {
        return t.stringFrom(t.funcdata, off)
}

// functabFieldSize returns the size in bytes of a single functab field.
func (t *LineTable) functabFieldSize() int {
        if t.version >= ver118 {
                return 4
        }
        return int(t.ptrsize)
}

// funcTab returns t's funcTab.
func (t *LineTable) funcTab() funcTab {
        return funcTab{LineTable: t, sz: t.functabFieldSize()}
}

// funcTab is memory corresponding to a slice of functab structs, followed by an invalid PC.
// A functab struct is a PC and a func offset.
type funcTab struct {
        *LineTable
        sz int // cached result of t.functabFieldSize
}

// Count returns the number of func entries in f.
func (f funcTab) Count() int {
        return int(f.nfunctab)
}

// pc returns the PC of the i'th func in f.
func (f funcTab) pc(i int) uint64 {
        u := f.uint(f.functab[2*i*f.sz:])
        if f.version >= ver118 {
                u += f.textStart
        }
        return u
}

// funcOff returns the funcdata offset of the i'th func in f.
func (f funcTab) funcOff(i int) uint64 {
        return f.uint(f.functab[(2*i+1)*f.sz:])
}

// uint returns the uint stored at b.
func (f funcTab) uint(b []byte) uint64 {
        if f.sz == 4 {
                return uint64(f.binary.Uint32(b))
        }
        return f.binary.Uint64(b)
}

// funcData is memory corresponding to an _func struct.
type funcData struct {
        t    *LineTable // LineTable this data is a part of
        data []byte     // raw memory for the function
}

// funcData returns the ith funcData in t.functab.
func (t *LineTable) funcData(i uint32) funcData {
        data := t.funcdata[t.funcTab().funcOff(int(i)):]
        return funcData{t: t, data: data}
}

// IsZero reports whether f is the zero value.
func (f funcData) IsZero() bool {
        return f.t == nil && f.data == nil
}

// entryPC returns the func's entry PC.
func (f *funcData) entryPC() uint64 {
        // In Go 1.18, the first field of _func changed
        // from a uintptr entry PC to a uint32 entry offset.
        if f.t.version >= ver118 {
                // TODO: support multiple text sections.
                // See runtime/symtab.go:(*moduledata).textAddr.
                return uint64(f.t.binary.Uint32(f.data)) + f.t.textStart
        }
        return f.t.uintptr(f.data)
}

func (f funcData) nameoff() uint32     { return f.field(1) }
func (f funcData) deferreturn() uint32 { return f.field(3) }
func (f funcData) pcfile() uint32      { return f.field(5) }
func (f funcData) pcln() uint32        { return f.field(6) }
func (f funcData) cuOffset() uint32    { return f.field(8) }

// field returns the nth field of the _func struct.
// It panics if n == 0 or n > 9; for n == 0, call f.entryPC.
// Most callers should use a named field accessor (just above).
func (f funcData) field(n uint32) uint32 {
        if n == 0 || n > 9 {
                panic("bad funcdata field")
        }
        // In Go 1.18, the first field of _func changed
        // from a uintptr entry PC to a uint32 entry offset.
        sz0 := f.t.ptrsize
        if f.t.version >= ver118 {
                sz0 = 4
        }
        off := sz0 + (n-1)*4 // subsequent fields are 4 bytes each
        data := f.data[off:]
        return f.t.binary.Uint32(data)
}

// 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 {
        p := t.pctab[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, cutab []byte) uint64 {
        if filetab == 0 || linetab == 0 {
                return 0
        }

        fp := t.pctab[filetab:]
        fl := t.pctab[linetab:]
        fileVal := int32(-1)
        filePC := entry
        lineVal := int32(-1)
        linePC := entry
        fileStartPC := filePC
        for t.step(&fp, &filePC, &fileVal, filePC == entry) {
                fileIndex := fileVal
                if t.version == ver116 || t.version == ver118 {
                        fileIndex = int32(t.binary.Uint32(cutab[fileVal*4:]))
                }
                if fileIndex == filenum && fileStartPC < filePC {
                        // fileIndex 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) {
        defer func() {
                if !disableRecover && recover() != nil {
                        line = -1
                }
        }()

        f := t.findFunc(pc)
        if f.IsZero() {
                return -1
        }
        entry := f.entryPC()
        linetab := f.pcln()
        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 !disableRecover && recover() != nil {
                        file = ""
                }
        }()

        f := t.findFunc(pc)
        if f.IsZero() {
                return ""
        }
        entry := f.entryPC()
        filetab := f.pcfile()
        fno := t.pcvalue(filetab, entry, pc)
        if t.version == ver12 {
                if fno <= 0 {
                        return ""
                }
                return t.string(t.binary.Uint32(t.filetab[4*fno:]))
        }
        // Go ≥ 1.16
        if fno < 0 { // 0 is valid for ≥ 1.16
                return ""
        }
        cuoff := f.cuOffset()
        if fnoff := t.binary.Uint32(t.cutab[(cuoff+uint32(fno))*4:]); fnoff != ^uint32(0) {
                return t.stringFrom(t.filetab, fnoff)
        }
        return ""
}

// 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 !disableRecover && recover() != nil {
                        pc = 0
                }
        }()

        t.initFileMap()
        filenum, ok := t.fileMap[file]
        if !ok {
                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.
        var cutab []byte
        for i := uint32(0); i < t.nfunctab; i++ {
                f := t.funcData(i)
                entry := f.entryPC()
                filetab := f.pcfile()
                linetab := f.pcln()
                if t.version == ver116 || t.version == ver118 {
                        if f.cuOffset() == ^uint32(0) {
                                // skip functions without compilation unit (not real function, or linker generated)
                                continue
                        }
                        cutab = t.cutab[f.cuOffset()*4:]
                }
                pc := t.findFileLine(entry, filetab, linetab, int32(filenum), int32(line), cutab)
                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)

        if t.version == ver12 {
                for i := uint32(1); i < t.nfiletab; i++ {
                        s := t.string(t.binary.Uint32(t.filetab[4*i:]))
                        m[s] = i
                }
        } else {
                var pos uint32
                for i := uint32(0); i < t.nfiletab; i++ {
                        s := t.stringFrom(t.filetab, pos)
                        m[s] = pos
                        pos += uint32(len(s) + 1)
                }
        }
        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) {
        if !disableRecover {
                defer func() {
                        recover()
                }()
        }

        t.initFileMap()
        for file := range t.fileMap {
                m[file] = obj
        }
}

// disableRecover causes this package not to swallow panics.
// This is useful when making changes.
const disableRecover = false