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