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