Imported Upstream version 1.4upstream/1.4

1 files changed, 453 insertions, 0 deletions

diff --git a/src/debug/gosym/pclntab.go b/src/debug/gosym/pclntab.go
new file mode 100644
index 000000000..6620aefb0
--- /dev/null
+++ b/src/debug/gosym/pclntab.go
@@ -0,0 +1,453 @@
+// 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 (
+	"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) {
+	defer func() {
+		if recover() != nil {
+			line = -1
+		}
+	}()
+
+	f := t.findFunc(pc)
+	if f == nil {
+		return -1
+	}
+	entry := t.uintptr(f)
+	linetab := t.binary.Uint32(f[t.ptrsize+5*4:])
+	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
+	}
+}