Source file src/pkg/debug/gosym/symtab.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	// Package gosym implements access to the Go symbol
     6	// and line number tables embedded in Go binaries generated
     7	// by the gc compilers.
     8	package gosym
     9	
    10	// The table format is a variant of the format used in Plan 9's a.out
    11	// format, documented at http://plan9.bell-labs.com/magic/man2html/6/a.out.
    12	// The best reference for the differences between the Plan 9 format
    13	// and the Go format is the runtime source, specifically ../../runtime/symtab.c.
    14	
    15	import (
    16		"encoding/binary"
    17		"fmt"
    18		"strconv"
    19		"strings"
    20	)
    21	
    22	/*
    23	 * Symbols
    24	 */
    25	
    26	// A Sym represents a single symbol table entry.
    27	type Sym struct {
    28		Value  uint64
    29		Type   byte
    30		Name   string
    31		GoType uint64
    32		// If this symbol if a function symbol, the corresponding Func
    33		Func *Func
    34	}
    35	
    36	// Static returns whether this symbol is static (not visible outside its file).
    37	func (s *Sym) Static() bool { return s.Type >= 'a' }
    38	
    39	// PackageName returns the package part of the symbol name,
    40	// or the empty string if there is none.
    41	func (s *Sym) PackageName() string {
    42		if i := strings.Index(s.Name, "."); i != -1 {
    43			return s.Name[0:i]
    44		}
    45		return ""
    46	}
    47	
    48	// ReceiverName returns the receiver type name of this symbol,
    49	// or the empty string if there is none.
    50	func (s *Sym) ReceiverName() string {
    51		l := strings.Index(s.Name, ".")
    52		r := strings.LastIndex(s.Name, ".")
    53		if l == -1 || r == -1 || l == r {
    54			return ""
    55		}
    56		return s.Name[l+1 : r]
    57	}
    58	
    59	// BaseName returns the symbol name without the package or receiver name.
    60	func (s *Sym) BaseName() string {
    61		if i := strings.LastIndex(s.Name, "."); i != -1 {
    62			return s.Name[i+1:]
    63		}
    64		return s.Name
    65	}
    66	
    67	// A Func collects information about a single function.
    68	type Func struct {
    69		Entry uint64
    70		*Sym
    71		End       uint64
    72		Params    []*Sym
    73		Locals    []*Sym
    74		FrameSize int
    75		LineTable *LineTable
    76		Obj       *Obj
    77	}
    78	
    79	// An Obj represents a single object file.
    80	type Obj struct {
    81		Funcs []Func
    82		Paths []Sym
    83	}
    84	
    85	/*
    86	 * Symbol tables
    87	 */
    88	
    89	// Table represents a Go symbol table.  It stores all of the
    90	// symbols decoded from the program and provides methods to translate
    91	// between symbols, names, and addresses.
    92	type Table struct {
    93		Syms  []Sym
    94		Funcs []Func
    95		Files map[string]*Obj
    96		Objs  []Obj
    97		//	textEnd uint64;
    98	}
    99	
   100	type sym struct {
   101		value  uint32
   102		gotype uint32
   103		typ    byte
   104		name   []byte
   105	}
   106	
   107	func walksymtab(data []byte, fn func(sym) error) error {
   108		var s sym
   109		p := data
   110		for len(p) >= 6 {
   111			s.value = binary.BigEndian.Uint32(p[0:4])
   112			typ := p[4]
   113			if typ&0x80 == 0 {
   114				return &DecodingError{len(data) - len(p) + 4, "bad symbol type", typ}
   115			}
   116			typ &^= 0x80
   117			s.typ = typ
   118			p = p[5:]
   119			var i int
   120			var nnul int
   121			for i = 0; i < len(p); i++ {
   122				if p[i] == 0 {
   123					nnul = 1
   124					break
   125				}
   126			}
   127			switch typ {
   128			case 'z', 'Z':
   129				p = p[i+nnul:]
   130				for i = 0; i+2 <= len(p); i += 2 {
   131					if p[i] == 0 && p[i+1] == 0 {
   132						nnul = 2
   133						break
   134					}
   135				}
   136			}
   137			if i+nnul+4 > len(p) {
   138				return &DecodingError{len(data), "unexpected EOF", nil}
   139			}
   140			s.name = p[0:i]
   141			i += nnul
   142			s.gotype = binary.BigEndian.Uint32(p[i : i+4])
   143			p = p[i+4:]
   144			fn(s)
   145		}
   146		return nil
   147	}
   148	
   149	// NewTable decodes the Go symbol table in data,
   150	// returning an in-memory representation.
   151	func NewTable(symtab []byte, pcln *LineTable) (*Table, error) {
   152		var n int
   153		err := walksymtab(symtab, func(s sym) error {
   154			n++
   155			return nil
   156		})
   157		if err != nil {
   158			return nil, err
   159		}
   160	
   161		var t Table
   162		fname := make(map[uint16]string)
   163		t.Syms = make([]Sym, 0, n)
   164		nf := 0
   165		nz := 0
   166		lasttyp := uint8(0)
   167		err = walksymtab(symtab, func(s sym) error {
   168			n := len(t.Syms)
   169			t.Syms = t.Syms[0 : n+1]
   170			ts := &t.Syms[n]
   171			ts.Type = s.typ
   172			ts.Value = uint64(s.value)
   173			ts.GoType = uint64(s.gotype)
   174			switch s.typ {
   175			default:
   176				// rewrite name to use . instead of · (c2 b7)
   177				w := 0
   178				b := s.name
   179				for i := 0; i < len(b); i++ {
   180					if b[i] == 0xc2 && i+1 < len(b) && b[i+1] == 0xb7 {
   181						i++
   182						b[i] = '.'
   183					}
   184					b[w] = b[i]
   185					w++
   186				}
   187				ts.Name = string(s.name[0:w])
   188			case 'z', 'Z':
   189				if lasttyp != 'z' && lasttyp != 'Z' {
   190					nz++
   191				}
   192				for i := 0; i < len(s.name); i += 2 {
   193					eltIdx := binary.BigEndian.Uint16(s.name[i : i+2])
   194					elt, ok := fname[eltIdx]
   195					if !ok {
   196						return &DecodingError{-1, "bad filename code", eltIdx}
   197					}
   198					if n := len(ts.Name); n > 0 && ts.Name[n-1] != '/' {
   199						ts.Name += "/"
   200					}
   201					ts.Name += elt
   202				}
   203			}
   204			switch s.typ {
   205			case 'T', 't', 'L', 'l':
   206				nf++
   207			case 'f':
   208				fname[uint16(s.value)] = ts.Name
   209			}
   210			lasttyp = s.typ
   211			return nil
   212		})
   213		if err != nil {
   214			return nil, err
   215		}
   216	
   217		t.Funcs = make([]Func, 0, nf)
   218		t.Objs = make([]Obj, 0, nz)
   219		t.Files = make(map[string]*Obj)
   220	
   221		// Count text symbols and attach frame sizes, parameters, and
   222		// locals to them.  Also, find object file boundaries.
   223		var obj *Obj
   224		lastf := 0
   225		for i := 0; i < len(t.Syms); i++ {
   226			sym := &t.Syms[i]
   227			switch sym.Type {
   228			case 'Z', 'z': // path symbol
   229				// Finish the current object
   230				if obj != nil {
   231					obj.Funcs = t.Funcs[lastf:]
   232				}
   233				lastf = len(t.Funcs)
   234	
   235				// Start new object
   236				n := len(t.Objs)
   237				t.Objs = t.Objs[0 : n+1]
   238				obj = &t.Objs[n]
   239	
   240				// Count & copy path symbols
   241				var end int
   242				for end = i + 1; end < len(t.Syms); end++ {
   243					if c := t.Syms[end].Type; c != 'Z' && c != 'z' {
   244						break
   245					}
   246				}
   247				obj.Paths = t.Syms[i:end]
   248				i = end - 1 // loop will i++
   249	
   250				// Record file names
   251				depth := 0
   252				for j := range obj.Paths {
   253					s := &obj.Paths[j]
   254					if s.Name == "" {
   255						depth--
   256					} else {
   257						if depth == 0 {
   258							t.Files[s.Name] = obj
   259						}
   260						depth++
   261					}
   262				}
   263	
   264			case 'T', 't', 'L', 'l': // text symbol
   265				if n := len(t.Funcs); n > 0 {
   266					t.Funcs[n-1].End = sym.Value
   267				}
   268				if sym.Name == "etext" {
   269					continue
   270				}
   271	
   272				// Count parameter and local (auto) syms
   273				var np, na int
   274				var end int
   275			countloop:
   276				for end = i + 1; end < len(t.Syms); end++ {
   277					switch t.Syms[end].Type {
   278					case 'T', 't', 'L', 'l', 'Z', 'z':
   279						break countloop
   280					case 'p':
   281						np++
   282					case 'a':
   283						na++
   284					}
   285				}
   286	
   287				// Fill in the function symbol
   288				n := len(t.Funcs)
   289				t.Funcs = t.Funcs[0 : n+1]
   290				fn := &t.Funcs[n]
   291				sym.Func = fn
   292				fn.Params = make([]*Sym, 0, np)
   293				fn.Locals = make([]*Sym, 0, na)
   294				fn.Sym = sym
   295				fn.Entry = sym.Value
   296				fn.Obj = obj
   297				if pcln != nil {
   298					fn.LineTable = pcln.slice(fn.Entry)
   299					pcln = fn.LineTable
   300				}
   301				for j := i; j < end; j++ {
   302					s := &t.Syms[j]
   303					switch s.Type {
   304					case 'm':
   305						fn.FrameSize = int(s.Value)
   306					case 'p':
   307						n := len(fn.Params)
   308						fn.Params = fn.Params[0 : n+1]
   309						fn.Params[n] = s
   310					case 'a':
   311						n := len(fn.Locals)
   312						fn.Locals = fn.Locals[0 : n+1]
   313						fn.Locals[n] = s
   314					}
   315				}
   316				i = end - 1 // loop will i++
   317			}
   318		}
   319		if obj != nil {
   320			obj.Funcs = t.Funcs[lastf:]
   321		}
   322		return &t, nil
   323	}
   324	
   325	// PCToFunc returns the function containing the program counter pc,
   326	// or nil if there is no such function.
   327	func (t *Table) PCToFunc(pc uint64) *Func {
   328		funcs := t.Funcs
   329		for len(funcs) > 0 {
   330			m := len(funcs) / 2
   331			fn := &funcs[m]
   332			switch {
   333			case pc < fn.Entry:
   334				funcs = funcs[0:m]
   335			case fn.Entry <= pc && pc < fn.End:
   336				return fn
   337			default:
   338				funcs = funcs[m+1:]
   339			}
   340		}
   341		return nil
   342	}
   343	
   344	// PCToLine looks up line number information for a program counter.
   345	// If there is no information, it returns fn == nil.
   346	func (t *Table) PCToLine(pc uint64) (file string, line int, fn *Func) {
   347		if fn = t.PCToFunc(pc); fn == nil {
   348			return
   349		}
   350		file, line = fn.Obj.lineFromAline(fn.LineTable.PCToLine(pc))
   351		return
   352	}
   353	
   354	// LineToPC looks up the first program counter on the given line in
   355	// the named file.  Returns UnknownPathError or UnknownLineError if
   356	// there is an error looking up this line.
   357	func (t *Table) LineToPC(file string, line int) (pc uint64, fn *Func, err error) {
   358		obj, ok := t.Files[file]
   359		if !ok {
   360			return 0, nil, UnknownFileError(file)
   361		}
   362		abs, err := obj.alineFromLine(file, line)
   363		if err != nil {
   364			return
   365		}
   366		for i := range obj.Funcs {
   367			f := &obj.Funcs[i]
   368			pc := f.LineTable.LineToPC(abs, f.End)
   369			if pc != 0 {
   370				return pc, f, nil
   371			}
   372		}
   373		return 0, nil, &UnknownLineError{file, line}
   374	}
   375	
   376	// LookupSym returns the text, data, or bss symbol with the given name,
   377	// or nil if no such symbol is found.
   378	func (t *Table) LookupSym(name string) *Sym {
   379		// TODO(austin) Maybe make a map
   380		for i := range t.Syms {
   381			s := &t.Syms[i]
   382			switch s.Type {
   383			case 'T', 't', 'L', 'l', 'D', 'd', 'B', 'b':
   384				if s.Name == name {
   385					return s
   386				}
   387			}
   388		}
   389		return nil
   390	}
   391	
   392	// LookupFunc returns the text, data, or bss symbol with the given name,
   393	// or nil if no such symbol is found.
   394	func (t *Table) LookupFunc(name string) *Func {
   395		for i := range t.Funcs {
   396			f := &t.Funcs[i]
   397			if f.Sym.Name == name {
   398				return f
   399			}
   400		}
   401		return nil
   402	}
   403	
   404	// SymByAddr returns the text, data, or bss symbol starting at the given address.
   405	// TODO(rsc): Allow lookup by any address within the symbol.
   406	func (t *Table) SymByAddr(addr uint64) *Sym {
   407		// TODO(austin) Maybe make a map
   408		for i := range t.Syms {
   409			s := &t.Syms[i]
   410			switch s.Type {
   411			case 'T', 't', 'L', 'l', 'D', 'd', 'B', 'b':
   412				if s.Value == addr {
   413					return s
   414				}
   415			}
   416		}
   417		return nil
   418	}
   419	
   420	/*
   421	 * Object files
   422	 */
   423	
   424	func (o *Obj) lineFromAline(aline int) (string, int) {
   425		type stackEnt struct {
   426			path   string
   427			start  int
   428			offset int
   429			prev   *stackEnt
   430		}
   431	
   432		noPath := &stackEnt{"", 0, 0, nil}
   433		tos := noPath
   434	
   435		// TODO(austin) I have no idea how 'Z' symbols work, except
   436		// that they pop the stack.
   437	pathloop:
   438		for _, s := range o.Paths {
   439			val := int(s.Value)
   440			switch {
   441			case val > aline:
   442				break pathloop
   443	
   444			case val == 1:
   445				// Start a new stack
   446				tos = &stackEnt{s.Name, val, 0, noPath}
   447	
   448			case s.Name == "":
   449				// Pop
   450				if tos == noPath {
   451					return "<malformed symbol table>", 0
   452				}
   453				tos.prev.offset += val - tos.start
   454				tos = tos.prev
   455	
   456			default:
   457				// Push
   458				tos = &stackEnt{s.Name, val, 0, tos}
   459			}
   460		}
   461	
   462		if tos == noPath {
   463			return "", 0
   464		}
   465		return tos.path, aline - tos.start - tos.offset + 1
   466	}
   467	
   468	func (o *Obj) alineFromLine(path string, line int) (int, error) {
   469		if line < 1 {
   470			return 0, &UnknownLineError{path, line}
   471		}
   472	
   473		for i, s := range o.Paths {
   474			// Find this path
   475			if s.Name != path {
   476				continue
   477			}
   478	
   479			// Find this line at this stack level
   480			depth := 0
   481			var incstart int
   482			line += int(s.Value)
   483		pathloop:
   484			for _, s := range o.Paths[i:] {
   485				val := int(s.Value)
   486				switch {
   487				case depth == 1 && val >= line:
   488					return line - 1, nil
   489	
   490				case s.Name == "":
   491					depth--
   492					if depth == 0 {
   493						break pathloop
   494					} else if depth == 1 {
   495						line += val - incstart
   496					}
   497	
   498				default:
   499					if depth == 1 {
   500						incstart = val
   501					}
   502					depth++
   503				}
   504			}
   505			return 0, &UnknownLineError{path, line}
   506		}
   507		return 0, UnknownFileError(path)
   508	}
   509	
   510	/*
   511	 * Errors
   512	 */
   513	
   514	// UnknownFileError represents a failure to find the specific file in
   515	// the symbol table.
   516	type UnknownFileError string
   517	
   518	func (e UnknownFileError) Error() string { return "unknown file: " + string(e) }
   519	
   520	// UnknownLineError represents a failure to map a line to a program
   521	// counter, either because the line is beyond the bounds of the file
   522	// or because there is no code on the given line.
   523	type UnknownLineError struct {
   524		File string
   525		Line int
   526	}
   527	
   528	func (e *UnknownLineError) Error() string {
   529		return "no code at " + e.File + ":" + strconv.Itoa(e.Line)
   530	}
   531	
   532	// DecodingError represents an error during the decoding of
   533	// the symbol table.
   534	type DecodingError struct {
   535		off int
   536		msg string
   537		val interface{}
   538	}
   539	
   540	func (e *DecodingError) Error() string {
   541		msg := e.msg
   542		if e.val != nil {
   543			msg += fmt.Sprintf(" '%v'", e.val)
   544		}
   545		msg += fmt.Sprintf(" at byte %#x", e.off)
   546		return msg
   547	}