debug/gocore: handle 1.11 sparse heaps Go 1.11 changed (will change?) the Go heap. Instead of a single arena, there will be potentially multiple arenas. Change the way we do address->object lookups to handle multiple, not necessarily near each other, arenas. The major change is to Use a page table instead of an array to keep HeapInfo structures. Also move ptr/nonptr bits into HeapInfo, as they are recorded differently in 1.11. It's a bit tricky because a heapInfo needs different numbers of ptr/nonptr bits for 32 and 64 bit inferiors. I'll add a 1.11 test when 1.11 ships. A tip-compiled test passes with this CL, but I don't want to check that in. Change-Id: I5b32fc4aaa88db137a23df2b4592eaba8a3f1fcc Reviewed-on: https://go-review.googlesource.com/100059 Reviewed-by: Austin Clements <austin@google.com>
diff --git a/gocore/dominator.go b/gocore/dominator.go index 375fd86..59fac42 100644 --- a/gocore/dominator.go +++ b/gocore/dominator.go
@@ -35,6 +35,9 @@ type ltDom struct { p *Process + // mapping from object ID to object + objs []Object + // number -> name vertices []vName @@ -55,6 +58,11 @@ } type dominators struct { + p *Process + + // mapping from object ID to object + objs []Object + // name -> dominator name idom []vName @@ -68,7 +76,7 @@ func (p *Process) calculateDominators() *dominators { lt := runLT(p) - d := dominators{idom: lt.idom} + d := dominators{p: p, idom: lt.idom, objs: lt.objs} lt = ltDom{} d.reverse() @@ -83,6 +91,7 @@ p: p, nRoots: len(p.rootIdx), nVertices: nVertices, + objs: make([]Object, p.nObj), vertices: make([]vName, nVertices), parents: make([]vName, nVertices), semis: make([]vNumber, nVertices), @@ -112,6 +121,14 @@ parentName vName } + // Initialize objs for mapping from object index back to Object. + i := 0 + d.p.ForEachObject(func(x Object) bool { + d.objs[i] = x + i++ + return true + }) + // Add roots to the work stack, essentially pretending to visit // the pseudo-root, numbering it 0. d.semis[pseudoRoot] = 0 @@ -145,7 +162,7 @@ return true } - root, object := findVertexByName(d.p, item.name) + root, object := d.findVertexByName(item.name) if root != nil { d.p.ForEachRootPtr(root, visitChild) } else { @@ -156,14 +173,23 @@ } // findVertexByName returns the root/object named by n, or nil,0 for the pseudo-root. -func findVertexByName(p *Process, n vName) (*Root, Object) { +func (d *ltDom) findVertexByName(n vName) (*Root, Object) { if n == 0 { return nil, 0 } - if int(n) < len(p.rootIdx)+1 { - return p.rootIdx[n-1], 0 + if int(n) < len(d.p.rootIdx)+1 { + return d.p.rootIdx[n-1], 0 } - return nil, p.findObjectFromIndex(int(n) - len(p.rootIdx) - 1) + return nil, d.objs[int(n)-len(d.p.rootIdx)-1] +} +func (d *dominators) findVertexByName(n vName) (*Root, Object) { + if n == 0 { + return nil, 0 + } + if int(n) < len(d.p.rootIdx)+1 { + return d.p.rootIdx[n-1], 0 + } + return nil, d.objs[int(n)-len(d.p.rootIdx)-1] } // calculate runs the main part of LT. @@ -188,7 +214,7 @@ } // Step 2. Compute the semidominators of all nodes. - root, obj := findVertexByName(d.p, w) + root, obj := d.findVertexByName(w) // This loop never visits the pseudo-root. if root != nil { u := d.eval(pseudoRoot) @@ -337,7 +363,7 @@ work = work[:len(work)-1] - root, obj := findVertexByName(p, item.v) + root, obj := d.findVertexByName(item.v) var size int64 switch { case item.v == pseudoRoot: @@ -358,7 +384,7 @@ fmt.Fprintf(w, "digraph %s {\nrankdir=\"LR\"\n", "dominators") for number, name := range d.vertices { var label string - root, obj := findVertexByName(d.p, name) + root, obj := d.findVertexByName(name) switch { case name == 0:
diff --git a/gocore/dominator_test.go b/gocore/dominator_test.go index 2f70902..f3360b0 100644 --- a/gocore/dominator_test.go +++ b/gocore/dominator_test.go
@@ -134,7 +134,7 @@ pRoot.idom = nil getVertex := func(n vName) *sanityVertex { - r, o := findVertexByName(d.p, n) + r, o := d.findVertexByName(n) switch { case n == pseudoRoot: return &pRoot
diff --git a/gocore/gocore_test.go b/gocore/gocore_test.go index d59e598..8d4206d 100644 --- a/gocore/gocore_test.go +++ b/gocore/gocore_test.go
@@ -5,6 +5,7 @@ package gocore import ( + "fmt" "reflect" "testing" @@ -29,6 +30,21 @@ return p } +func loadExampleVersion(t *testing.T, version string) *Process { + if version == "1.9" { + version = "" + } + c, err := core.Core(fmt.Sprintf("testdata/core%s", version), "testdata") + if err != nil { + t.Fatalf("can't load test core file: %s", err) + } + p, err := Core(c, FlagTypes|FlagReverse) + if err != nil { + t.Fatalf("can't parse Go core: %s", err) + } + return p +} + func TestObjects(t *testing.T) { p := loadExample(t) n := 0 @@ -41,18 +57,6 @@ } } -func TestObjectIndexes(t *testing.T) { - p := loadExample(t) - p.ForEachObject(func(x Object) bool { - idx, _ := p.findObjectIndex(p.Addr(x)) - got := p.findObjectFromIndex(idx) - if x != got { - t.Errorf("findObjectFromIndex(%v) = %#x, want %#x", idx, got, x) - } - return true - }) -} - func TestRoots(t *testing.T) { p := loadExample(t) n := 0 @@ -187,3 +191,7 @@ } } } + +func TestVersions(t *testing.T) { + loadExampleVersion(t, "1.10") +}
diff --git a/gocore/object.go b/gocore/object.go index 61d66de..debf0ca 100644 --- a/gocore/object.go +++ b/gocore/object.go
@@ -6,7 +6,6 @@ import ( "math/bits" - "sort" "strings" "golang.org/x/debug/core" @@ -31,13 +30,13 @@ // Function to call when we find a new pointer. add := func(x core.Address) { h := p.findHeapInfo(x) - if h == nil || h.base == 0 { // not in heap or not in a valid span + if h == nil { // not in heap or not in a valid span // Invalid spans can happen with intra-stack pointers. return } // Round down to object start. x = h.base.Add(x.Sub(h.base) / h.size * h.size) - // Object start may map to a different info. Reload. + // Object start may map to a different info. Reload heap info. h = p.findHeapInfo(x) // Find mark bit b := uint64(x) % heapInfoSize / 8 @@ -108,10 +107,17 @@ p.nObj = n // Initialize firstIdx fields in the heapInfo, for fast object index lookups. - for i := len(p.heapInfo) - 1; i >= 0; i-- { - h := &p.heapInfo[i] - n -= bits.OnesCount64(h.mark) - h.firstIdx = n + n = 0 + p.ForEachObject(func(x Object) bool { + h := p.findHeapInfo(p.Addr(x)) + if h.firstIdx == -1 { + h.firstIdx = n + } + n++ + return true + }) + if n != p.nObj { + panic("object count wrong") } // Update stats to include the live/garbage distinction. @@ -125,19 +131,14 @@ // isPtrFromHeap reports whether the inferior at address a contains a pointer. // a must be somewhere in the heap. func (p *Process) isPtrFromHeap(a core.Address) bool { - // Convert arena offset in words to bitmap offset in bits. - off := a.Sub(p.arenaStart) - off >>= p.proc.LogPtrSize() - - // Find bit in bitmap. It goes backwards from the end. - // Each byte contains pointer/nonpointer bits for 4 words in its low nybble. - return p.proc.ReadUint8(p.bitmapEnd.Add(-(off>>2)-1))>>uint(off&3)&1 != 0 + return p.findHeapInfo(a).IsPtr(a, p.proc.PtrSize()) } // IsPtr reports whether the inferior at address a contains a pointer. func (p *Process) IsPtr(a core.Address) bool { - if a >= p.arenaStart && a < p.arenaUsed { - return p.isPtrFromHeap(a) + h := p.findHeapInfo(a) + if h != nil { + return h.IsPtr(a, p.proc.PtrSize()) } for _, m := range p.modules { for _, s := range [2]string{"data", "bss"} { @@ -163,7 +164,7 @@ func (p *Process) FindObject(a core.Address) (Object, int64) { // Round down to the start of an object. h := p.findHeapInfo(a) - if h == nil || h.size == 0 { + if h == nil { // Not in Go heap, or in a span // that doesn't hold Go objects (freed, stacks, ...) return 0, 0 @@ -171,7 +172,7 @@ x := h.base.Add(a.Sub(h.base) / h.size * h.size) // Check if object is marked. h = p.findHeapInfo(x) - if h.mark>>(uint64(x)%heapInfoSize/8)&1 == 0 { + if h.mark>>(uint64(x)%heapInfoSize/8)&1 == 0 { // free or garbage return 0, 0 } return Object(x), a.Sub(x) @@ -186,40 +187,21 @@ return h.firstIdx + bits.OnesCount64(h.mark&(uint64(1)<<(uint64(x)%heapInfoSize/8)-1)), off } -func (p *Process) findObjectFromIndex(idx int) Object { - // Find the first heapInfo after the index we want, then go one back, - // so that we skip over empty chunks. - hIdx := sort.Search(len(p.heapInfo), func(k int) bool { - return p.heapInfo[k].firstIdx > idx - }) - if hIdx > 0 { - hIdx-- - } - h := p.heapInfo[hIdx] - gap := idx - h.firstIdx + 1 - // TODO: use math/bits somehow? - for offset := core.Address(0); offset < heapInfoSize; offset += 8 { - if h.mark>>(offset/8)&1 == 1 { - gap-- - } - if gap == 0 { - // Can't use heapInfo.base: it's the start of the *span*, not the heapInfo. - return Object(p.arenaStart + core.Address(hIdx*heapInfoSize) + offset) - } - } - panic("Overran heap info looking for live objects") -} - // ForEachObject calls fn with each object in the Go heap. // If fn returns false, ForEachObject returns immediately. func (p *Process) ForEachObject(fn func(x Object) bool) { - for i := 0; i < len(p.heapInfo); i++ { - m := p.heapInfo[i].mark - for m != 0 { - j := bits.TrailingZeros64(m) - m &= m - 1 - if !fn(Object(p.arenaStart.Add(int64(i)*heapInfoSize + int64(j)*8))) { - return + for _, k := range p.pages { + pt := p.pageTable[k] + for i := range pt { + h := &pt[i] + m := h.mark + for m != 0 { + j := bits.TrailingZeros64(m) + m &= m - 1 + x := Object(k)*pageTableSize*heapInfoSize + Object(i)*heapInfoSize + Object(j)*8 + if !fn(x) { + return + } } } } @@ -348,15 +330,69 @@ base core.Address // start of the span containing this heap region size int64 // size of objects in the span mark uint64 // 64 mark bits, one for every 8 bytes - firstIdx int // the index of the first object that starts in or after this region + firstIdx int // the index of the first object that starts in this region, or -1 if none + // For 64-bit inferiors, ptr[0] contains 64 pointer bits, one + // for every 8 bytes. On 32-bit inferiors, ptr contains 128 + // pointer bits, one for every 4 bytes. + ptr [2]uint64 } +func (h *heapInfo) IsPtr(a core.Address, ptrSize int64) bool { + if ptrSize == 8 { + i := uint(a%heapInfoSize) / 8 + return h.ptr[0]>>i&1 != 0 + } + i := a % heapInfoSize / 4 + return h.ptr[i/64]>>(i%64)&1 != 0 +} + +// setHeapPtr records that the memory at heap address a contains a pointer. +func (p *Process) setHeapPtr(a core.Address) { + h := p.allocHeapInfo(a) + if p.proc.PtrSize() == 8 { + i := uint(a%heapInfoSize) / 8 + h.ptr[0] |= uint64(1) << i + return + } + i := a % heapInfoSize / 4 + h.ptr[i/64] |= uint64(1) << (i % 64) +} + +// Heap info structures cover 9 bits of address. +// A page table entry covers 20 bits of address (1MB). +const pageTableSize = 1 << 11 + +type pageTableEntry [pageTableSize]heapInfo + // findHeapInfo finds the heapInfo structure for a. // Returns nil if a is not a heap address. func (p *Process) findHeapInfo(a core.Address) *heapInfo { - if a < p.arenaStart || a >= p.arenaUsed { + k := a / heapInfoSize / pageTableSize + i := a / heapInfoSize % pageTableSize + t := p.pageTable[k] + if t == nil { return nil } - i := a.Sub(p.arenaStart) / heapInfoSize - return &p.heapInfo[i] + h := &t[i] + if h.base == 0 { + return nil + } + return h +} + +// Same as findHeapInfo, but allocates the heapInfo if it +// hasn't been allocated yet. +func (p *Process) allocHeapInfo(a core.Address) *heapInfo { + k := a / heapInfoSize / pageTableSize + i := a / heapInfoSize % pageTableSize + t := p.pageTable[k] + if t == nil { + t = new(pageTableEntry) + for j := 0; j < pageTableSize; j++ { + t[j].firstIdx = -1 + } + p.pageTable[k] = t + p.pages = append(p.pages, k) + } + return &t[i] }
diff --git a/gocore/process.go b/gocore/process.go index de034c8..d618566 100644 --- a/gocore/process.go +++ b/gocore/process.go
@@ -16,12 +16,11 @@ type Process struct { proc *core.Process - arenaStart core.Address - arenaUsed core.Address - bitmapEnd core.Address - // data structure for fast object finding - heapInfo []heapInfo + // The key to these maps is the object address divided by + // pageTableSize * heapInfoSize. + pageTable map[core.Address]*pageTableEntry + pages []core.Address // deterministic ordering of keys of pageTable // number of live objects nObj int @@ -168,7 +167,7 @@ // Read all the data that depend on runtime globals. p.buildVersion = p.rtGlobals["buildVersion"].String() p.readModules() - p.readSpans() + p.readHeap() p.readGs() p.readStackVars() // needs to be after readGs. p.markObjects() // needs to be after readGlobals, readStackVars. @@ -182,21 +181,108 @@ return p, nil } -func (p *Process) readSpans() { +type arena struct { + heapMin core.Address + heapMax core.Address + + bitmapMin core.Address + bitmapMax core.Address + + spanTableMin core.Address + spanTableMax core.Address +} + +func (p *Process) readHeap() { + ptrSize := p.proc.PtrSize() + logPtrSize := p.proc.LogPtrSize() + p.pageTable = map[core.Address]*pageTableEntry{} mheap := p.rtGlobals["mheap_"] + var arenas []arena - spanTableStart := mheap.Field("spans").SlicePtr().Address() - spanTableEnd := spanTableStart.Add(mheap.Field("spans").SliceCap() * p.proc.PtrSize()) - arenaStart := core.Address(mheap.Field("arena_start").Uintptr()) - arenaUsed := core.Address(mheap.Field("arena_used").Uintptr()) - arenaEnd := core.Address(mheap.Field("arena_end").Uintptr()) - bitmapEnd := core.Address(mheap.Field("bitmap").Uintptr()) - bitmapStart := bitmapEnd.Add(-int64(mheap.Field("bitmap_mapped").Uintptr())) + if mheap.HasField("spans") { + // go 1.9 or 1.10. There is a single arena. + arenaStart := core.Address(mheap.Field("arena_start").Uintptr()) + arenaUsed := core.Address(mheap.Field("arena_used").Uintptr()) + arenaEnd := core.Address(mheap.Field("arena_end").Uintptr()) + bitmapEnd := core.Address(mheap.Field("bitmap").Uintptr()) + bitmapStart := bitmapEnd.Add(-int64(mheap.Field("bitmap_mapped").Uintptr())) + spanTableStart := mheap.Field("spans").SlicePtr().Address() + spanTableEnd := spanTableStart.Add(mheap.Field("spans").SliceCap() * ptrSize) + arenas = append(arenas, arena{ + heapMin: arenaStart, + heapMax: arenaEnd, + bitmapMin: bitmapStart, + bitmapMax: bitmapEnd, + spanTableMin: spanTableStart, + spanTableMax: spanTableEnd, + }) - p.arenaStart = arenaStart - p.arenaUsed = arenaUsed - p.bitmapEnd = bitmapEnd + // Copy pointer bits to heap info. + // Note that the pointer bits are stored backwards. + for a := arenaStart; a < arenaUsed; a = a.Add(ptrSize) { + off := a.Sub(arenaStart) >> logPtrSize + if p.proc.ReadUint8(bitmapEnd.Add(-(off>>2)-1))>>uint(off&3)&1 != 0 { + p.setHeapPtr(a) + } + } + } else { + // go 1.11+. Has multiple arenas. + arenaSize := p.rtConstants["heapArenaBytes"] + if arenaSize%heapInfoSize != 0 { + panic("arenaSize not a multiple of heapInfoSize") + } + arenaBaseOffset := p.rtConstants["arenaBaseOffset"] + if ptrSize == 4 && arenaBaseOffset != 0 { + panic("arenaBaseOffset must be 0 for 32-bit inferior") + } + level1Table := mheap.Field("arenas") + level1size := level1Table.ArrayLen() + for level1 := int64(0); level1 < level1size; level1++ { + ptr := level1Table.ArrayIndex(level1) + if ptr.Address() == 0 { + continue + } + level2table := ptr.Deref() + level2size := level2table.ArrayLen() + for level2 := int64(0); level2 < level2size; level2++ { + ptr = level2table.ArrayIndex(level2) + if ptr.Address() == 0 { + continue + } + a := ptr.Deref() + min := core.Address(arenaSize*(level2+level1*level2size) - arenaBaseOffset) + max := min.Add(arenaSize) + bitmap := a.Field("bitmap") + spans := a.Field("spans") + + arenas = append(arenas, arena{ + heapMin: min, + heapMax: max, + bitmapMin: bitmap.a, + bitmapMax: bitmap.a.Add(bitmap.ArrayLen()), + spanTableMin: spans.a, + spanTableMax: spans.a.Add(spans.ArrayLen() * ptrSize), + }) + + // Copy out ptr/nonptr bits + n := bitmap.ArrayLen() + for i := int64(0); i < n; i++ { + m := bitmap.ArrayIndex(i).Uint8() + for j := int64(0); j < 8; j++ { + if m>>uint(j)&1 != 0 { + p.setHeapPtr(min.Add((i*8 + j) * ptrSize)) + } + } + } + } + } + } + + p.readSpans(mheap, arenas) +} + +func (p *Process) readSpans(mheap region, arenas []arena) { var all int64 var text int64 var readOnly int64 @@ -228,9 +314,11 @@ size -= b.Sub(a) } } - attribute(spanTableStart, spanTableEnd, &spanTable) - attribute(arenaStart, arenaEnd, &heap) - attribute(bitmapStart, bitmapEnd, &bitmap) + for _, a := range arenas { + attribute(a.heapMin, a.heapMax, &heap) + attribute(a.bitmapMin, a.bitmapMax, &bitmap) + attribute(a.spanTableMin, a.spanTableMax, &spanTable) + } // Any other anonymous mapping is bss. // TODO: how to distinguish original bss from anonymous mmap? bss += size @@ -250,7 +338,6 @@ if pageSize%heapInfoSize != 0 { panic(fmt.Sprintf("page size not a multiple of %d", heapInfoSize)) } - p.heapInfo = make([]heapInfo, (p.arenaUsed-p.arenaStart)/heapInfoSize) allspans := mheap.Field("allspans") var allSpanSize int64 var freeSpanSize int64 @@ -294,8 +381,12 @@ } } spanRoundSize += spanSize - n*elemSize + + // initialize heap info records for all inuse spans. for a := min; a < max; a += heapInfoSize { - p.heapInfo[(a.Sub(p.arenaStart))/heapInfoSize] = heapInfo{base: min, size: elemSize, firstIdx: -1} + h := p.allocHeapInfo(a) + h.base = min + h.size = elemSize } // Process special records.
diff --git a/gocore/region.go b/gocore/region.go index b0fdc79..cc78518 100644 --- a/gocore/region.go +++ b/gocore/region.go
@@ -157,3 +157,25 @@ } return region{p: r.p, a: r.a.Add(finfo.Off), typ: finfo.Type} } + +func (r region) HasField(f string) bool { + finfo := r.typ.field(f) + return finfo != nil +} + +func (r region) ArrayLen() int64 { + if r.typ.Kind != KindArray { + panic("can't ArrayLen a non-array") + } + return r.typ.Count +} + +func (r region) ArrayIndex(i int64) region { + if r.typ.Kind != KindArray { + panic("can't ArrayIndex a non-array") + } + if i < 0 || i >= r.typ.Count { + panic("array index out of bounds") + } + return region{p: r.p, a: r.a.Add(i * r.typ.Elem.Size), typ: r.typ.Elem} +}
diff --git a/gocore/testdata/README b/gocore/testdata/README index 11d9761..2cf240c 100644 --- a/gocore/testdata/README +++ b/gocore/testdata/README
@@ -12,3 +12,5 @@ path. The executable was at /tmp/test, so that path is reproduced here so the core dump reader can find the executable using this testdata directory as the base directory. + +core1.10 is produced in the same way, except using go1.10.0.
diff --git a/gocore/testdata/core1.10 b/gocore/testdata/core1.10 new file mode 100644 index 0000000..903c176 --- /dev/null +++ b/gocore/testdata/core1.10 Binary files differ
diff --git a/gocore/testdata/tmp/test1.10 b/gocore/testdata/tmp/test1.10 new file mode 100755 index 0000000..6839de6 --- /dev/null +++ b/gocore/testdata/tmp/test1.10 Binary files differ