Source file src/pkg/debug/gosym/pclntab.go

     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		"sync"
    15	)
    16	
    17	// A LineTable is a data structure mapping program counters to line numbers.
    18	//
    19	// In Go 1.1 and earlier, each function (represented by a Func) had its own LineTable,
    20	// and the line number corresponded to a numbering of all source lines in the
    21	// program, across all files. That absolute line number would then have to be
    22	// converted separately to a file name and line number within the file.
    23	//
    24	// In Go 1.2, the format of the data changed so that there is a single LineTable
    25	// for the entire program, shared by all Funcs, and there are no absolute line
    26	// numbers, just line numbers within specific files.
    27	//
    28	// For the most part, LineTable's methods should be treated as an internal
    29	// detail of the package; callers should use the methods on Table instead.
    30	type LineTable struct {
    31		Data []byte
    32		PC   uint64
    33		Line int
    34	
    35		// Go 1.2 state
    36		mu       sync.Mutex
    37		go12     int // is this in Go 1.2 format? -1 no, 0 unknown, 1 yes
    38		binary   binary.ByteOrder
    39		quantum  uint32
    40		ptrsize  uint32
    41		functab  []byte
    42		nfunctab uint32
    43		filetab  []byte
    44		nfiletab uint32
    45		fileMap  map[string]uint32
    46		strings  map[uint32]string // interned substrings of Data, keyed by offset
    47	}
    48	
    49	// NOTE(rsc): This is wrong for GOARCH=arm, which uses a quantum of 4,
    50	// but we have no idea whether we're using arm or not. This only
    51	// matters in the old (pre-Go 1.2) symbol table format, so it's not worth
    52	// fixing.
    53	const oldQuantum = 1
    54	
    55	func (t *LineTable) parse(targetPC uint64, targetLine int) (b []byte, pc uint64, line int) {
    56		// The PC/line table can be thought of as a sequence of
    57		//  <pc update>* <line update>
    58		// batches. Each update batch results in a (pc, line) pair,
    59		// where line applies to every PC from pc up to but not
    60		// including the pc of the next pair.
    61		//
    62		// Here we process each update individually, which simplifies
    63		// the code, but makes the corner cases more confusing.
    64		b, pc, line = t.Data, t.PC, t.Line
    65		for pc <= targetPC && line != targetLine && len(b) > 0 {
    66			code := b[0]
    67			b = b[1:]
    68			switch {
    69			case code == 0:
    70				if len(b) < 4 {
    71					b = b[0:0]
    72					break
    73				}
    74				val := binary.BigEndian.Uint32(b)
    75				b = b[4:]
    76				line += int(val)
    77			case code <= 64:
    78				line += int(code)
    79			case code <= 128:
    80				line -= int(code - 64)
    81			default:
    82				pc += oldQuantum * uint64(code-128)
    83				continue
    84			}
    85			pc += oldQuantum
    86		}
    87		return b, pc, line
    88	}
    89	
    90	func (t *LineTable) slice(pc uint64) *LineTable {
    91		data, pc, line := t.parse(pc, -1)
    92		return &LineTable{Data: data, PC: pc, Line: line}
    93	}
    94	
    95	// PCToLine returns the line number for the given program counter.
    96	//
    97	// Deprecated: Use Table's PCToLine method instead.
    98	func (t *LineTable) PCToLine(pc uint64) int {
    99		if t.isGo12() {
   100			return t.go12PCToLine(pc)
   101		}
   102		_, _, line := t.parse(pc, -1)
   103		return line
   104	}
   105	
   106	// LineToPC returns the program counter for the given line number,
   107	// considering only program counters before maxpc.
   108	//
   109	// Deprecated: Use Table's LineToPC method instead.
   110	func (t *LineTable) LineToPC(line int, maxpc uint64) uint64 {
   111		if t.isGo12() {
   112			return 0
   113		}
   114		_, pc, line1 := t.parse(maxpc, line)
   115		if line1 != line {
   116			return 0
   117		}
   118		// Subtract quantum from PC to account for post-line increment
   119		return pc - oldQuantum
   120	}
   121	
   122	// NewLineTable returns a new PC/line table
   123	// corresponding to the encoded data.
   124	// Text must be the start address of the
   125	// corresponding text segment.
   126	func NewLineTable(data []byte, text uint64) *LineTable {
   127		return &LineTable{Data: data, PC: text, Line: 0, strings: make(map[uint32]string)}
   128	}
   129	
   130	// Go 1.2 symbol table format.
   131	// See golang.org/s/go12symtab.
   132	//
   133	// A general note about the methods here: rather than try to avoid
   134	// index out of bounds errors, we trust Go to detect them, and then
   135	// we recover from the panics and treat them as indicative of a malformed
   136	// or incomplete table.
   137	//
   138	// The methods called by symtab.go, which begin with "go12" prefixes,
   139	// are expected to have that recovery logic.
   140	
   141	// isGo12 reports whether this is a Go 1.2 (or later) symbol table.
   142	func (t *LineTable) isGo12() bool {
   143		t.go12Init()
   144		return t.go12 == 1
   145	}
   146	
   147	const go12magic = 0xfffffffb
   148	
   149	// uintptr returns the pointer-sized value encoded at b.
   150	// The pointer size is dictated by the table being read.
   151	func (t *LineTable) uintptr(b []byte) uint64 {
   152		if t.ptrsize == 4 {
   153			return uint64(t.binary.Uint32(b))
   154		}
   155		return t.binary.Uint64(b)
   156	}
   157	
   158	// go12init initializes the Go 1.2 metadata if t is a Go 1.2 symbol table.
   159	func (t *LineTable) go12Init() {
   160		t.mu.Lock()
   161		defer t.mu.Unlock()
   162		if t.go12 != 0 {
   163			return
   164		}
   165	
   166		defer func() {
   167			// If we panic parsing, assume it's not a Go 1.2 symbol table.
   168			recover()
   169		}()
   170	
   171		// Check header: 4-byte magic, two zeros, pc quantum, pointer size.
   172		t.go12 = -1 // not Go 1.2 until proven otherwise
   173		if len(t.Data) < 16 || t.Data[4] != 0 || t.Data[5] != 0 ||
   174			(t.Data[6] != 1 && t.Data[6] != 2 && t.Data[6] != 4) || // pc quantum
   175			(t.Data[7] != 4 && t.Data[7] != 8) { // pointer size
   176			return
   177		}
   178	
   179		switch uint32(go12magic) {
   180		case binary.LittleEndian.Uint32(t.Data):
   181			t.binary = binary.LittleEndian
   182		case binary.BigEndian.Uint32(t.Data):
   183			t.binary = binary.BigEndian
   184		default:
   185			return
   186		}
   187	
   188		t.quantum = uint32(t.Data[6])
   189		t.ptrsize = uint32(t.Data[7])
   190	
   191		t.nfunctab = uint32(t.uintptr(t.Data[8:]))
   192		t.functab = t.Data[8+t.ptrsize:]
   193		functabsize := t.nfunctab*2*t.ptrsize + t.ptrsize
   194		fileoff := t.binary.Uint32(t.functab[functabsize:])
   195		t.functab = t.functab[:functabsize]
   196		t.filetab = t.Data[fileoff:]
   197		t.nfiletab = t.binary.Uint32(t.filetab)
   198		t.filetab = t.filetab[:t.nfiletab*4]
   199	
   200		t.go12 = 1 // so far so good
   201	}
   202	
   203	// go12Funcs returns a slice of Funcs derived from the Go 1.2 pcln table.
   204	func (t *LineTable) go12Funcs() []Func {
   205		// Assume it is malformed and return nil on error.
   206		defer func() {
   207			recover()
   208		}()
   209	
   210		n := len(t.functab) / int(t.ptrsize) / 2
   211		funcs := make([]Func, n)
   212		for i := range funcs {
   213			f := &funcs[i]
   214			f.Entry = t.uintptr(t.functab[2*i*int(t.ptrsize):])
   215			f.End = t.uintptr(t.functab[(2*i+2)*int(t.ptrsize):])
   216			info := t.Data[t.uintptr(t.functab[(2*i+1)*int(t.ptrsize):]):]
   217			f.LineTable = t
   218			f.FrameSize = int(t.binary.Uint32(info[t.ptrsize+2*4:]))
   219			f.Sym = &Sym{
   220				Value:  f.Entry,
   221				Type:   'T',
   222				Name:   t.string(t.binary.Uint32(info[t.ptrsize:])),
   223				GoType: 0,
   224				Func:   f,
   225			}
   226		}
   227		return funcs
   228	}
   229	
   230	// findFunc returns the func corresponding to the given program counter.
   231	func (t *LineTable) findFunc(pc uint64) []byte {
   232		if pc < t.uintptr(t.functab) || pc >= t.uintptr(t.functab[len(t.functab)-int(t.ptrsize):]) {
   233			return nil
   234		}
   235	
   236		// The function table is a list of 2*nfunctab+1 uintptrs,
   237		// alternating program counters and offsets to func structures.
   238		f := t.functab
   239		nf := t.nfunctab
   240		for nf > 0 {
   241			m := nf / 2
   242			fm := f[2*t.ptrsize*m:]
   243			if t.uintptr(fm) <= pc && pc < t.uintptr(fm[2*t.ptrsize:]) {
   244				return t.Data[t.uintptr(fm[t.ptrsize:]):]
   245			} else if pc < t.uintptr(fm) {
   246				nf = m
   247			} else {
   248				f = f[(m+1)*2*t.ptrsize:]
   249				nf -= m + 1
   250			}
   251		}
   252		return nil
   253	}
   254	
   255	// readvarint reads, removes, and returns a varint from *pp.
   256	func (t *LineTable) readvarint(pp *[]byte) uint32 {
   257		var v, shift uint32
   258		p := *pp
   259		for shift = 0; ; shift += 7 {
   260			b := p[0]
   261			p = p[1:]
   262			v |= (uint32(b) & 0x7F) << shift
   263			if b&0x80 == 0 {
   264				break
   265			}
   266		}
   267		*pp = p
   268		return v
   269	}
   270	
   271	// string returns a Go string found at off.
   272	func (t *LineTable) string(off uint32) string {
   273		if s, ok := t.strings[off]; ok {
   274			return s
   275		}
   276		i := bytes.IndexByte(t.Data[off:], 0)
   277		s := string(t.Data[off : off+uint32(i)])
   278		t.strings[off] = s
   279		return s
   280	}
   281	
   282	// step advances to the next pc, value pair in the encoded table.
   283	func (t *LineTable) step(p *[]byte, pc *uint64, val *int32, first bool) bool {
   284		uvdelta := t.readvarint(p)
   285		if uvdelta == 0 && !first {
   286			return false
   287		}
   288		if uvdelta&1 != 0 {
   289			uvdelta = ^(uvdelta >> 1)
   290		} else {
   291			uvdelta >>= 1
   292		}
   293		vdelta := int32(uvdelta)
   294		pcdelta := t.readvarint(p) * t.quantum
   295		*pc += uint64(pcdelta)
   296		*val += vdelta
   297		return true
   298	}
   299	
   300	// pcvalue reports the value associated with the target pc.
   301	// off is the offset to the beginning of the pc-value table,
   302	// and entry is the start PC for the corresponding function.
   303	func (t *LineTable) pcvalue(off uint32, entry, targetpc uint64) int32 {
   304		p := t.Data[off:]
   305	
   306		val := int32(-1)
   307		pc := entry
   308		for t.step(&p, &pc, &val, pc == entry) {
   309			if targetpc < pc {
   310				return val
   311			}
   312		}
   313		return -1
   314	}
   315	
   316	// findFileLine scans one function in the binary looking for a
   317	// program counter in the given file on the given line.
   318	// It does so by running the pc-value tables mapping program counter
   319	// to file number. Since most functions come from a single file, these
   320	// are usually short and quick to scan. If a file match is found, then the
   321	// code goes to the expense of looking for a simultaneous line number match.
   322	func (t *LineTable) findFileLine(entry uint64, filetab, linetab uint32, filenum, line int32) uint64 {
   323		if filetab == 0 || linetab == 0 {
   324			return 0
   325		}
   326	
   327		fp := t.Data[filetab:]
   328		fl := t.Data[linetab:]
   329		fileVal := int32(-1)
   330		filePC := entry
   331		lineVal := int32(-1)
   332		linePC := entry
   333		fileStartPC := filePC
   334		for t.step(&fp, &filePC, &fileVal, filePC == entry) {
   335			if fileVal == filenum && fileStartPC < filePC {
   336				// fileVal is in effect starting at fileStartPC up to
   337				// but not including filePC, and it's the file we want.
   338				// Run the PC table looking for a matching line number
   339				// or until we reach filePC.
   340				lineStartPC := linePC
   341				for linePC < filePC && t.step(&fl, &linePC, &lineVal, linePC == entry) {
   342					// lineVal is in effect until linePC, and lineStartPC < filePC.
   343					if lineVal == line {
   344						if fileStartPC <= lineStartPC {
   345							return lineStartPC
   346						}
   347						if fileStartPC < linePC {
   348							return fileStartPC
   349						}
   350					}
   351					lineStartPC = linePC
   352				}
   353			}
   354			fileStartPC = filePC
   355		}
   356		return 0
   357	}
   358	
   359	// go12PCToLine maps program counter to line number for the Go 1.2 pcln table.
   360	func (t *LineTable) go12PCToLine(pc uint64) (line int) {
   361		defer func() {
   362			if recover() != nil {
   363				line = -1
   364			}
   365		}()
   366	
   367		f := t.findFunc(pc)
   368		if f == nil {
   369			return -1
   370		}
   371		entry := t.uintptr(f)
   372		linetab := t.binary.Uint32(f[t.ptrsize+5*4:])
   373		return int(t.pcvalue(linetab, entry, pc))
   374	}
   375	
   376	// go12PCToFile maps program counter to file name for the Go 1.2 pcln table.
   377	func (t *LineTable) go12PCToFile(pc uint64) (file string) {
   378		defer func() {
   379			if recover() != nil {
   380				file = ""
   381			}
   382		}()
   383	
   384		f := t.findFunc(pc)
   385		if f == nil {
   386			return ""
   387		}
   388		entry := t.uintptr(f)
   389		filetab := t.binary.Uint32(f[t.ptrsize+4*4:])
   390		fno := t.pcvalue(filetab, entry, pc)
   391		if fno <= 0 {
   392			return ""
   393		}
   394		return t.string(t.binary.Uint32(t.filetab[4*fno:]))
   395	}
   396	
   397	// go12LineToPC maps a (file, line) pair to a program counter for the Go 1.2 pcln table.
   398	func (t *LineTable) go12LineToPC(file string, line int) (pc uint64) {
   399		defer func() {
   400			if recover() != nil {
   401				pc = 0
   402			}
   403		}()
   404	
   405		t.initFileMap()
   406		filenum := t.fileMap[file]
   407		if filenum == 0 {
   408			return 0
   409		}
   410	
   411		// Scan all functions.
   412		// If this turns out to be a bottleneck, we could build a map[int32][]int32
   413		// mapping file number to a list of functions with code from that file.
   414		for i := uint32(0); i < t.nfunctab; i++ {
   415			f := t.Data[t.uintptr(t.functab[2*t.ptrsize*i+t.ptrsize:]):]
   416			entry := t.uintptr(f)
   417			filetab := t.binary.Uint32(f[t.ptrsize+4*4:])
   418			linetab := t.binary.Uint32(f[t.ptrsize+5*4:])
   419			pc := t.findFileLine(entry, filetab, linetab, int32(filenum), int32(line))
   420			if pc != 0 {
   421				return pc
   422			}
   423		}
   424		return 0
   425	}
   426	
   427	// initFileMap initializes the map from file name to file number.
   428	func (t *LineTable) initFileMap() {
   429		t.mu.Lock()
   430		defer t.mu.Unlock()
   431	
   432		if t.fileMap != nil {
   433			return
   434		}
   435		m := make(map[string]uint32)
   436	
   437		for i := uint32(1); i < t.nfiletab; i++ {
   438			s := t.string(t.binary.Uint32(t.filetab[4*i:]))
   439			m[s] = i
   440		}
   441		t.fileMap = m
   442	}
   443	
   444	// go12MapFiles adds to m a key for every file in the Go 1.2 LineTable.
   445	// Every key maps to obj. That's not a very interesting map, but it provides
   446	// a way for callers to obtain the list of files in the program.
   447	func (t *LineTable) go12MapFiles(m map[string]*Obj, obj *Obj) {
   448		defer func() {
   449			recover()
   450		}()
   451	
   452		t.initFileMap()
   453		for file := range t.fileMap {
   454			m[file] = obj
   455		}
   456	}
   457	

View as plain text