...
Run Format

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

View as plain text