| // Copyright 2017 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package gocore |
| |
| import ( |
| "math/bits" |
| "sort" |
| "strings" |
| |
| "golang.org/x/debug/core" |
| ) |
| |
| // An Object represents a single reachable object in the Go heap. |
| // Unreachable (garbage) objects are not represented as Objects. |
| type Object core.Address |
| |
| // markObjects finds all the live objects in the heap and marks them |
| // in the p.heapInfo mark fields. |
| func (p *Process) markObjects() { |
| ptrSize := p.proc.PtrSize() |
| |
| // number of live objects found so far |
| n := 0 |
| // total size of live objects |
| var live int64 |
| |
| var q []Object |
| |
| // 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 |
| // 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. |
| h = p.findHeapInfo(x) |
| // Find mark bit |
| b := uint64(x) % heapInfoSize / 8 |
| if h.mark&(uint64(1)<<b) != 0 { // already found |
| return |
| } |
| h.mark |= uint64(1) << b |
| n++ |
| live += h.size |
| q = append(q, Object(x)) |
| } |
| |
| // Start with scanning all the roots. |
| // Note that we don't just use the DWARF roots, just in case DWARF isn't complete. |
| // Instead we use exactly what the runtime uses. |
| |
| // Goroutine roots |
| for _, g := range p.goroutines { |
| for _, f := range g.frames { |
| for a := range f.Live { |
| add(p.proc.ReadPtr(a)) |
| } |
| } |
| } |
| |
| // Global roots |
| for _, m := range p.modules { |
| for _, s := range [2]string{"data", "bss"} { |
| min := core.Address(m.r.Field(s).Uintptr()) |
| max := core.Address(m.r.Field("e" + s).Uintptr()) |
| gc := m.r.Field("gc" + s + "mask").Field("bytedata").Address() |
| num := max.Sub(min) / ptrSize |
| for i := int64(0); i < num; i++ { |
| if p.proc.ReadUint8(gc.Add(i/8))>>uint(i%8)&1 != 0 { |
| add(p.proc.ReadPtr(min.Add(i * ptrSize))) |
| } |
| } |
| } |
| } |
| |
| // Finalizers |
| for _, r := range p.globals { |
| if !strings.HasPrefix(r.Name, "finalizer for ") { |
| continue |
| } |
| for _, f := range r.Type.Fields { |
| if f.Type.Kind == KindPtr { |
| add(p.proc.ReadPtr(r.Addr.Add(f.Off))) |
| } |
| } |
| } |
| |
| // Expand root set to all reachable objects. |
| for len(q) > 0 { |
| x := q[len(q)-1] |
| q = q[:len(q)-1] |
| |
| // Scan object for pointers. |
| size := p.Size(x) |
| for i := int64(0); i < size; i += ptrSize { |
| a := core.Address(x).Add(i) |
| if p.isPtrFromHeap(a) { |
| add(p.proc.ReadPtr(a)) |
| } |
| } |
| } |
| |
| 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 |
| } |
| |
| // Update stats to include the live/garbage distinction. |
| alloc := p.Stats().Child("heap").Child("in use spans").Child("alloc") |
| alloc.Children = []*Stats{ |
| &Stats{"live", live, nil}, |
| &Stats{"garbage", alloc.Size - live, nil}, |
| } |
| } |
| |
| // 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 |
| } |
| |
| // 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) |
| } |
| for _, m := range p.modules { |
| for _, s := range [2]string{"data", "bss"} { |
| min := core.Address(m.r.Field(s).Uintptr()) |
| max := core.Address(m.r.Field("e" + s).Uintptr()) |
| if a < min || a >= max { |
| continue |
| } |
| gc := m.r.Field("gc" + s + "mask").Field("bytedata").Address() |
| i := a.Sub(min) |
| return p.proc.ReadUint8(gc.Add(i/8))>>uint(i%8) != 0 |
| } |
| } |
| // Everywhere else can't be a pointer. At least, not a pointer into the Go heap. |
| // TODO: stacks? |
| // TODO: finalizers? |
| return false |
| } |
| |
| // FindObject finds the object containing a. Returns that object and the offset within |
| // that object to which a points. |
| // Returns 0,0 if a doesn't point to a live heap object. |
| 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 { |
| // Not in Go heap, or in a span |
| // that doesn't hold Go objects (freed, stacks, ...) |
| return 0, 0 |
| } |
| 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 { |
| return 0, 0 |
| } |
| return Object(x), a.Sub(x) |
| } |
| |
| func (p *Process) findObjectIndex(a core.Address) (int, int64) { |
| x, off := p.FindObject(a) |
| if x == 0 { |
| return -1, 0 |
| } |
| h := p.findHeapInfo(core.Address(x)) |
| 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 |
| } |
| } |
| } |
| } |
| |
| // ForEachRoot calls fn with each garbage collection root. |
| // If fn returns false, ForEachRoot returns immediately. |
| func (p *Process) ForEachRoot(fn func(r *Root) bool) { |
| for _, r := range p.globals { |
| if !fn(r) { |
| return |
| } |
| } |
| for _, g := range p.goroutines { |
| for _, f := range g.frames { |
| for _, r := range f.roots { |
| if !fn(r) { |
| return |
| } |
| } |
| } |
| } |
| } |
| |
| // Addr returns the starting address of x. |
| func (p *Process) Addr(x Object) core.Address { |
| return core.Address(x) |
| } |
| |
| // Size returns the size of x in bytes. |
| func (p *Process) Size(x Object) int64 { |
| return p.findHeapInfo(core.Address(x)).size |
| } |
| |
| // Type returns the type and repeat count for the object x. |
| // x contains at least repeat copies of the returned type. |
| // FlagTypes must have been passed to Core when p was constructed. |
| func (p *Process) Type(x Object) (*Type, int64) { |
| i, _ := p.findObjectIndex(core.Address(x)) |
| return p.types[i].t, p.types[i].r |
| } |
| |
| // ForEachPtr calls fn for all heap pointers it finds in x. |
| // It calls fn with: |
| // the offset of the pointer slot in x |
| // the pointed-to object y |
| // the offset in y where the pointer points. |
| // If fn returns false, ForEachPtr returns immediately. |
| // For an edge from an object to its finalizer, the first argument |
| // passed to fn will be -1. (TODO: implement) |
| func (p *Process) ForEachPtr(x Object, fn func(int64, Object, int64) bool) { |
| size := p.Size(x) |
| for i := int64(0); i < size; i += p.proc.PtrSize() { |
| a := core.Address(x).Add(i) |
| if !p.isPtrFromHeap(a) { |
| continue |
| } |
| ptr := p.proc.ReadPtr(a) |
| y, off := p.FindObject(ptr) |
| if y != 0 { |
| if !fn(i, y, off) { |
| return |
| } |
| } |
| } |
| } |
| |
| // ForEachRootPtr behaves like ForEachPtr but it starts with a Root instead of an Object. |
| func (p *Process) ForEachRootPtr(r *Root, fn func(int64, Object, int64) bool) { |
| edges1(p, r, 0, r.Type, fn) |
| } |
| |
| // edges1 calls fn for the edges found in an object of type t living at offset off in the root r. |
| // If fn returns false, return immediately with false. |
| func edges1(p *Process, r *Root, off int64, t *Type, fn func(int64, Object, int64) bool) bool { |
| switch t.Kind { |
| case KindBool, KindInt, KindUint, KindFloat, KindComplex: |
| // no edges here |
| case KindIface, KindEface: |
| // The first word is a type or itab. |
| // Itabs are never in the heap. |
| // Types might be, though. |
| a := r.Addr.Add(off) |
| if r.Frame == nil || r.Frame.Live[a] { |
| dst, off2 := p.FindObject(p.proc.ReadPtr(a)) |
| if dst != 0 { |
| if !fn(off, dst, off2) { |
| return false |
| } |
| } |
| } |
| // Treat second word like a pointer. |
| off += p.proc.PtrSize() |
| fallthrough |
| case KindPtr, KindString, KindSlice, KindFunc: |
| a := r.Addr.Add(off) |
| if r.Frame == nil || r.Frame.Live[a] { |
| dst, off2 := p.FindObject(p.proc.ReadPtr(a)) |
| if dst != 0 { |
| if !fn(off, dst, off2) { |
| return false |
| } |
| } |
| } |
| case KindArray: |
| s := t.Elem.Size |
| for i := int64(0); i < t.Count; i++ { |
| if !edges1(p, r, off+i*s, t.Elem, fn) { |
| return false |
| } |
| } |
| case KindStruct: |
| for _, f := range t.Fields { |
| if !edges1(p, r, off+f.Off, f.Type, fn) { |
| return false |
| } |
| } |
| } |
| return true |
| } |
| |
| const heapInfoSize = 512 |
| |
| // Information for heapInfoSize bytes of heap. |
| type heapInfo struct { |
| 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 |
| } |
| |
| // 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 { |
| return nil |
| } |
| i := a.Sub(p.arenaStart) / heapInfoSize |
| return &p.heapInfo[i] |
| } |