Black Lives Matter. Support the Equal Justice Initiative.

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

View as plain text