src/runtime/symtab.go

   1 // Copyright 2014 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 runtime
   6
   7 import "unsafe"
   8
   9 // NOTE: Func does not expose the actual unexported fields, because we return *Func
  10 // values to users, and we want to keep them from being able to overwrite the data
  11 // with (say) *f = Func{}.
  12 // All code operating on a *Func must call raw to get the *_func instead.
  13
  14 // A Func represents a Go function in the running binary.
  15 type Func struct {
  16         opaque struct{} // unexported field to disallow conversions
  17 }
  18
  19 func (f *Func) raw() *_func {
  20         return (*_func)(unsafe.Pointer(f))
  21 }
  22
  23 // funcdata.h
  24 const (
  25         _PCDATA_StackMapIndex       = 0
  26         _FUNCDATA_ArgsPointerMaps   = 0
  27         _FUNCDATA_LocalsPointerMaps = 1
  28         _ArgsSizeUnknown            = -0x80000000
  29 )
  30
  31 // moduledata records information about the layout of the executable
  32 // image. It is written by the linker. Any changes here must be
  33 // matched changes to the code in cmd/internal/ld/symtab.go:symtab.
  34 // moduledata is stored in read-only memory; none of the pointers here
  35 // are visible to the garbage collector.
  36 type moduledata struct {
  37         pclntable    []byte
  38         ftab         []functab
  39         filetab      []uint32
  40         findfunctab  uintptr
  41         minpc, maxpc uintptr
  42
  43         text, etext           uintptr
  44         noptrdata, enoptrdata uintptr
  45         data, edata           uintptr
  46         bss, ebss             uintptr
  47         noptrbss, enoptrbss   uintptr
  48         end, gcdata, gcbss    uintptr
  49
  50         typelinks []*_type
  51
  52         modulename   string
  53         modulehashes []modulehash
  54
  55         gcdatamask, gcbssmask bitvector
  56
  57         next *moduledata
  58 }
  59
  60 // For each shared library a module links against, the linker creates an entry in the
  61 // moduledata.modulehashes slice containing the name of the module, the abi hash seen
  62 // at link time and a pointer to the runtime abi hash. These are checked in
  63 // moduledataverify1 below.
  64 type modulehash struct {
  65         modulename   string
  66         linktimehash string
  67         runtimehash  *string
  68 }
  69
  70 var firstmoduledata moduledata  // linker symbol
  71 var lastmoduledatap *moduledata // linker symbol
  72
  73 type functab struct {
  74         entry   uintptr
  75         funcoff uintptr
  76 }
  77
  78 const minfunc = 16                 // minimum function size
  79 const pcbucketsize = 256 * minfunc // size of bucket in the pc->func lookup table
  80
  81 // findfunctab is an array of these structures.
  82 // Each bucket represents 4096 bytes of the text segment.
  83 // Each subbucket represents 256 bytes of the text segment.
  84 // To find a function given a pc, locate the bucket and subbucket for
  85 // that pc.  Add together the idx and subbucket value to obtain a
  86 // function index.  Then scan the functab array starting at that
  87 // index to find the target function.
  88 // This table uses 20 bytes for every 4096 bytes of code, or ~0.5% overhead.
  89 type findfuncbucket struct {
  90         idx        uint32
  91         subbuckets [16]byte
  92 }
  93
  94 func moduledataverify() {
  95         for datap := &firstmoduledata; datap != nil; datap = datap.next {
  96                 moduledataverify1(datap)
  97         }
  98 }
  99
 100 const debugPcln = false
 101
 102 func moduledataverify1(datap *moduledata) {
 103         // See golang.org/s/go12symtab for header: 0xfffffffb,
 104         // two zero bytes, a byte giving the PC quantum,
 105         // and a byte giving the pointer width in bytes.
 106         pcln := *(**[8]byte)(unsafe.Pointer(&datap.pclntable))
 107         pcln32 := *(**[2]uint32)(unsafe.Pointer(&datap.pclntable))
 108         if pcln32[0] != 0xfffffffb || pcln[4] != 0 || pcln[5] != 0 || pcln[6] != _PCQuantum || pcln[7] != ptrSize {
 109                 println("runtime: function symbol table header:", hex(pcln32[0]), hex(pcln[4]), hex(pcln[5]), hex(pcln[6]), hex(pcln[7]))
 110                 throw("invalid function symbol table\n")
 111         }
 112
 113         // ftab is lookup table for function by program counter.
 114         nftab := len(datap.ftab) - 1
 115         var pcCache pcvalueCache
 116         for i := 0; i < nftab; i++ {
 117                 // NOTE: ftab[nftab].entry is legal; it is the address beyond the final function.
 118                 if datap.ftab[i].entry > datap.ftab[i+1].entry {
 119                         f1 := (*_func)(unsafe.Pointer(&datap.pclntable[datap.ftab[i].funcoff]))
 120                         f2 := (*_func)(unsafe.Pointer(&datap.pclntable[datap.ftab[i+1].funcoff]))
 121                         f2name := "end"
 122                         if i+1 < nftab {
 123                                 f2name = funcname(f2)
 124                         }
 125                         println("function symbol table not sorted by program counter:", hex(datap.ftab[i].entry), funcname(f1), ">", hex(datap.ftab[i+1].entry), f2name)
 126                         for j := 0; j <= i; j++ {
 127                                 print("\t", hex(datap.ftab[j].entry), " ", funcname((*_func)(unsafe.Pointer(&datap.pclntable[datap.ftab[j].funcoff]))), "\n")
 128                         }
 129                         throw("invalid runtime symbol table")
 130                 }
 131
 132                 if debugPcln || nftab-i < 5 {
 133                         // Check a PC near but not at the very end.
 134                         // The very end might be just padding that is not covered by the tables.
 135                         // No architecture rounds function entries to more than 16 bytes,
 136                         // but if one came along we'd need to subtract more here.
 137                         // But don't use the next PC if it corresponds to a foreign object chunk
 138                         // (no pcln table, f2.pcln == 0). That chunk might have an alignment
 139                         // more than 16 bytes.
 140                         f := (*_func)(unsafe.Pointer(&datap.pclntable[datap.ftab[i].funcoff]))
 141                         end := f.entry
 142                         if i+1 < nftab {
 143                                 f2 := (*_func)(unsafe.Pointer(&datap.pclntable[datap.ftab[i+1].funcoff]))
 144                                 if f2.pcln != 0 {
 145                                         end = f2.entry - 16
 146                                         if end < f.entry {
 147                                                 end = f.entry
 148                                         }
 149                                 }
 150                         }
 151                         pcvalue(f, f.pcfile, end, &pcCache, true)
 152                         pcvalue(f, f.pcln, end, &pcCache, true)
 153                         pcvalue(f, f.pcsp, end, &pcCache, true)
 154                 }
 155         }
 156
 157         if datap.minpc != datap.ftab[0].entry ||
 158                 datap.maxpc != datap.ftab[nftab].entry {
 159                 throw("minpc or maxpc invalid")
 160         }
 161
 162         for _, modulehash := range datap.modulehashes {
 163                 if modulehash.linktimehash != *modulehash.runtimehash {
 164                         println("abi mismatch detected between", datap.modulename, "and", modulehash.modulename)
 165                         throw("abi mismatch")
 166                 }
 167         }
 168 }
 169
 170 // FuncForPC returns a *Func describing the function that contains the
 171 // given program counter address, or else nil.
 172 func FuncForPC(pc uintptr) *Func {
 173         return (*Func)(unsafe.Pointer(findfunc(pc)))
 174 }
 175
 176 // Name returns the name of the function.
 177 func (f *Func) Name() string {
 178         return funcname(f.raw())
 179 }
 180
 181 // Entry returns the entry address of the function.
 182 func (f *Func) Entry() uintptr {
 183         return f.raw().entry
 184 }
 185
 186 // FileLine returns the file name and line number of the
 187 // source code corresponding to the program counter pc.
 188 // The result will not be accurate if pc is not a program
 189 // counter within f.
 190 func (f *Func) FileLine(pc uintptr) (file string, line int) {
 191         // Pass strict=false here, because anyone can call this function,
 192         // and they might just be wrong about targetpc belonging to f.
 193         file, line32 := funcline1(f.raw(), pc, false)
 194         return file, int(line32)
 195 }
 196
 197 func findmoduledatap(pc uintptr) *moduledata {
 198         for datap := &firstmoduledata; datap != nil; datap = datap.next {
 199                 if datap.minpc <= pc && pc <= datap.maxpc {
 200                         return datap
 201                 }
 202         }
 203         return nil
 204 }
 205
 206 func findfunc(pc uintptr) *_func {
 207         datap := findmoduledatap(pc)
 208         if datap == nil {
 209                 return nil
 210         }
 211         const nsub = uintptr(len(findfuncbucket{}.subbuckets))
 212
 213         x := pc - datap.minpc
 214         b := x / pcbucketsize
 215         i := x % pcbucketsize / (pcbucketsize / nsub)
 216
 217         ffb := (*findfuncbucket)(add(unsafe.Pointer(datap.findfunctab), b*unsafe.Sizeof(findfuncbucket{})))
 218         idx := ffb.idx + uint32(ffb.subbuckets[i])
 219         if pc < datap.ftab[idx].entry {
 220                 throw("findfunc: bad findfunctab entry")
 221         }
 222
 223         // linear search to find func with pc >= entry.
 224         for datap.ftab[idx+1].entry <= pc {
 225                 idx++
 226         }
 227         return (*_func)(unsafe.Pointer(&datap.pclntable[datap.ftab[idx].funcoff]))
 228 }
 229
 230 type pcvalueCache struct {
 231         entries [16]pcvalueCacheEnt
 232 }
 233
 234 type pcvalueCacheEnt struct {
 235         // targetpc and off together are the key of this cache entry.
 236         targetpc uintptr
 237         off      int32
 238         // val is the value of this cached pcvalue entry.
 239         val int32
 240 }
 241
 242 func pcvalue(f *_func, off int32, targetpc uintptr, cache *pcvalueCache, strict bool) int32 {
 243         if off == 0 {
 244                 return -1
 245         }
 246
 247         // Check the cache. This speeds up walks of deep stacks, which
 248         // tend to have the same recursive functions over and over.
 249         //
 250         // This cache is small enough that full associativity is
 251         // cheaper than doing the hashing for a less associative
 252         // cache.
 253         if cache != nil {
 254                 for _, ent := range cache.entries {
 255                         // We check off first because we're more
 256                         // likely to have multiple entries with
 257                         // different offsets for the same targetpc
 258                         // than the other way around, so we'll usually
 259                         // fail in the first clause.
 260                         if ent.off == off && ent.targetpc == targetpc {
 261                                 return ent.val
 262                         }
 263                 }
 264         }
 265
 266         datap := findmoduledatap(f.entry) // inefficient
 267         if datap == nil {
 268                 if strict && panicking == 0 {
 269                         print("runtime: no module data for ", hex(f.entry), "\n")
 270                         throw("no module data")
 271                 }
 272                 return -1
 273         }
 274         p := datap.pclntable[off:]
 275         pc := f.entry
 276         val := int32(-1)
 277         for {
 278                 var ok bool
 279                 p, ok = step(p, &pc, &val, pc == f.entry)
 280                 if !ok {
 281                         break
 282                 }
 283                 if targetpc < pc {
 284                         // Replace a random entry in the cache. Random
 285                         // replacement prevents a performance cliff if
 286                         // a recursive stack's cycle is slightly
 287                         // larger than the cache.
 288                         if cache != nil {
 289                                 ci := fastrand1() % uint32(len(cache.entries))
 290                                 cache.entries[ci] = pcvalueCacheEnt{
 291                                         targetpc: targetpc,
 292                                         off:      off,
 293                                         val:      val,
 294                                 }
 295                         }
 296
 297                         return val
 298                 }
 299         }
 300
 301         // If there was a table, it should have covered all program counters.
 302         // If not, something is wrong.
 303         if panicking != 0 || !strict {
 304                 return -1
 305         }
 306
 307         print("runtime: invalid pc-encoded table f=", funcname(f), " pc=", hex(pc), " targetpc=", hex(targetpc), " tab=", p, "\n")
 308
 309         p = datap.pclntable[off:]
 310         pc = f.entry
 311         val = -1
 312         for {
 313                 var ok bool
 314                 p, ok = step(p, &pc, &val, pc == f.entry)
 315                 if !ok {
 316                         break
 317                 }
 318                 print("\tvalue=", val, " until pc=", hex(pc), "\n")
 319         }
 320
 321         throw("invalid runtime symbol table")
 322         return -1
 323 }
 324
 325 func cfuncname(f *_func) *byte {
 326         if f == nil || f.nameoff == 0 {
 327                 return nil
 328         }
 329         datap := findmoduledatap(f.entry) // inefficient
 330         if datap == nil {
 331                 return nil
 332         }
 333         return &datap.pclntable[f.nameoff]
 334 }
 335
 336 func funcname(f *_func) string {
 337         return gostringnocopy(cfuncname(f))
 338 }
 339
 340 func funcline1(f *_func, targetpc uintptr, strict bool) (file string, line int32) {
 341         datap := findmoduledatap(f.entry) // inefficient
 342         if datap == nil {
 343                 return "?", 0
 344         }
 345         fileno := int(pcvalue(f, f.pcfile, targetpc, nil, strict))
 346         line = pcvalue(f, f.pcln, targetpc, nil, strict)
 347         if fileno == -1 || line == -1 || fileno >= len(datap.filetab) {
 348                 // print("looking for ", hex(targetpc), " in ", funcname(f), " got file=", fileno, " line=", lineno, "\n")
 349                 return "?", 0
 350         }
 351         file = gostringnocopy(&datap.pclntable[datap.filetab[fileno]])
 352         return
 353 }
 354
 355 func funcline(f *_func, targetpc uintptr) (file string, line int32) {
 356         return funcline1(f, targetpc, true)
 357 }
 358
 359 func funcspdelta(f *_func, targetpc uintptr, cache *pcvalueCache) int32 {
 360         x := pcvalue(f, f.pcsp, targetpc, cache, true)
 361         if x&(ptrSize-1) != 0 {
 362                 print("invalid spdelta ", funcname(f), " ", hex(f.entry), " ", hex(targetpc), " ", hex(f.pcsp), " ", x, "\n")
 363         }
 364         return x
 365 }
 366
 367 func pcdatavalue(f *_func, table int32, targetpc uintptr, cache *pcvalueCache) int32 {
 368         if table < 0 || table >= f.npcdata {
 369                 return -1
 370         }
 371         off := *(*int32)(add(unsafe.Pointer(&f.nfuncdata), unsafe.Sizeof(f.nfuncdata)+uintptr(table)*4))
 372         return pcvalue(f, off, targetpc, cache, true)
 373 }
 374
 375 func funcdata(f *_func, i int32) unsafe.Pointer {
 376         if i < 0 || i >= f.nfuncdata {
 377                 return nil
 378         }
 379         p := add(unsafe.Pointer(&f.nfuncdata), unsafe.Sizeof(f.nfuncdata)+uintptr(f.npcdata)*4)
 380         if ptrSize == 8 && uintptr(p)&4 != 0 {
 381                 if uintptr(unsafe.Pointer(f))&4 != 0 {
 382                         println("runtime: misaligned func", f)
 383                 }
 384                 p = add(p, 4)
 385         }
 386         return *(*unsafe.Pointer)(add(p, uintptr(i)*ptrSize))
 387 }
 388
 389 // step advances to the next pc, value pair in the encoded table.
 390 func step(p []byte, pc *uintptr, val *int32, first bool) (newp []byte, ok bool) {
 391         p, uvdelta := readvarint(p)
 392         if uvdelta == 0 && !first {
 393                 return nil, false
 394         }
 395         if uvdelta&1 != 0 {
 396                 uvdelta = ^(uvdelta >> 1)
 397         } else {
 398                 uvdelta >>= 1
 399         }
 400         vdelta := int32(uvdelta)
 401         p, pcdelta := readvarint(p)
 402         *pc += uintptr(pcdelta * _PCQuantum)
 403         *val += vdelta
 404         return p, true
 405 }
 406
 407 // readvarint reads a varint from p.
 408 func readvarint(p []byte) (newp []byte, val uint32) {
 409         var v, shift uint32
 410         for {
 411                 b := p[0]
 412                 p = p[1:]
 413                 v |= (uint32(b) & 0x7F) << shift
 414                 if b&0x80 == 0 {
 415                         break
 416                 }
 417                 shift += 7
 418         }
 419         return p, v
 420 }
 421
 422 type stackmap struct {
 423         n        int32   // number of bitmaps
 424         nbit     int32   // number of bits in each bitmap
 425         bytedata [1]byte // bitmaps, each starting on a 32-bit boundary
 426 }
 427
 428 //go:nowritebarrier
 429 func stackmapdata(stkmap *stackmap, n int32) bitvector {
 430         if n < 0 || n >= stkmap.n {
 431                 throw("stackmapdata: index out of range")
 432         }
 433         return bitvector{stkmap.nbit, (*byte)(add(unsafe.Pointer(&stkmap.bytedata), uintptr(n*((stkmap.nbit+31)/32*4))))}
 434 }