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 9package gosym 10 11import ( 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. 29type 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. 51const oldQuantum = 1 52 53func (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 88func (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. 95func (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. 106func (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. 122func 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. 138func (t *LineTable) isGo12() bool { 139 t.go12Init() 140 return t.go12 == 1 141} 142 143const go12magic = 0xfffffffb 144 145// uintptr returns the pointer-sized value encoded at b. 146// The pointer size is dictated by the table being read. 147func (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. 155func (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. 200func (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. 227func (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. 252func (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. 268func (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. 277func (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. 297func (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. 316func (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. 354func (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. 371func (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. 392func (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. 422func (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. 441func (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