Source file src/debug/gosym/pclntab.go

Documentation: debug/gosym

     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