cmd/geth, mobile: add memsize to pprof server (#16532)

* cmd/geth, mobile: add memsize to pprof server

This is a temporary change, to be reverted before the next release.

* cmd/geth: fix variable name

9 files changed, 792 insertions, 0 deletions

diff --git a/vendor/github.com/fjl/memsize/LICENSE b/vendor/github.com/fjl/memsize/LICENSE
new file mode 100644
index 000000000..8b8045641
--- /dev/null
+++ b/vendor/github.com/fjl/memsize/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2018 Felix Lange
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/vendor/github.com/fjl/memsize/bitmap.go b/vendor/github.com/fjl/memsize/bitmap.go
new file mode 100644
index 000000000..47799ea8d
--- /dev/null
+++ b/vendor/github.com/fjl/memsize/bitmap.go
@@ -0,0 +1,119 @@
+package memsize
+
+import (
+	"math/bits"
+)
+
+const (
+	uintptrBits  = 32 << (uint64(^uintptr(0)) >> 63)
+	uintptrBytes = uintptrBits / 8
+	bmBlockRange = 1 * 1024 * 1024 // bytes covered by bmBlock
+	bmBlockWords = bmBlockRange / uintptrBits
+)
+
+// bitmap is a sparse bitmap.
+type bitmap struct {
+	blocks map[uintptr]*bmBlock
+}
+
+func newBitmap() *bitmap {
+	return &bitmap{make(map[uintptr]*bmBlock)}
+}
+
+// markRange sets n consecutive bits starting at addr.
+func (b *bitmap) markRange(addr, n uintptr) {
+	for end := addr + n; addr < end; {
+		block, baddr := b.block(addr)
+		for i := baddr; i < bmBlockRange && addr < end; i++ {
+			block.mark(i)
+			addr++
+		}
+	}
+}
+
+// isMarked returns the value of the bit at the given address.
+func (b *bitmap) isMarked(addr uintptr) bool {
+	block, baddr := b.block(addr)
+	return block.isMarked(baddr)
+}
+
+// countRange returns the number of set bits in the range (addr,addr+n).
+func (b *bitmap) countRange(addr, n uintptr) uintptr {
+	c := uintptr(0)
+	for end := addr + n; addr < end; {
+		block, baddr := b.block(addr)
+		bend := uintptr(bmBlockRange - 1)
+		if baddr+(end-addr) < bmBlockRange {
+			bend = baddr + (end - addr)
+		}
+		c += uintptr(block.count(baddr, bend))
+		// Move addr to next block.
+		addr += bmBlockRange - baddr
+	}
+	return c
+}
+
+// block finds the block corresponding to the given memory address.
+// It also returns the block's starting address.
+func (b *bitmap) block(addr uintptr) (*bmBlock, uintptr) {
+	index := addr / bmBlockRange
+	block := b.blocks[index]
+	if block == nil {
+		block = new(bmBlock)
+		b.blocks[index] = block
+	}
+	return block, addr % bmBlockRange
+}
+
+// size returns the sum of the byte sizes of all blocks.
+func (b *bitmap) size() uintptr {
+	return uintptr(len(b.blocks)) * bmBlockWords * uintptrBytes
+}
+
+// utilization returns the mean percentage of one bits across all blocks.
+func (b *bitmap) utilization() float32 {
+	var avg float32
+	for _, block := range b.blocks {
+		avg += float32(block.count(0, bmBlockRange-1)) / float32(bmBlockRange)
+	}
+	return avg / float32(len(b.blocks))
+}
+
+// bmBlock is a bitmap block.
+type bmBlock [bmBlockWords]uintptr
+
+// mark sets the i'th bit to one.
+func (b *bmBlock) mark(i uintptr) {
+	b[i/uintptrBits] |= 1 << (i % uintptrBits)
+}
+
+// isMarked returns the value of the i'th bit.
+func (b *bmBlock) isMarked(i uintptr) bool {
+	return (b[i/uintptrBits] & (1 << (i % uintptrBits))) != 0
+}
+
+// count returns the number of set bits in the range (start,end).
+func (b *bmBlock) count(start, end uintptr) (count int) {
+	br := b[start/uintptrBits : end/uintptrBits+1]
+	for i, w := range br {
+		if i == 0 {
+			w &= blockmask(start)
+		}
+		if i == len(br)-1 {
+			w &^= blockmask(end)
+		}
+		count += onesCountPtr(w)
+	}
+	return count
+}
+
+func blockmask(x uintptr) uintptr {
+	return ^uintptr(0) << (x % uintptrBits)
+}
+
+func onesCountPtr(x uintptr) int {
+	if uintptrBits == 64 {
+		return bits.OnesCount64(uint64(x))
+	}
+	return bits.OnesCount32(uint32(x))
+}
diff --git a/vendor/github.com/fjl/memsize/doc.go b/vendor/github.com/fjl/memsize/doc.go
new file mode 100644
index 000000000..640cfba5e
--- /dev/null
+++ b/vendor/github.com/fjl/memsize/doc.go
@@ -0,0 +1,16 @@
+/*
+Package memsize computes the size of your object graph.
+
+So you made a spiffy algorithm and it works really well, but geez it's using
+way too much memory. Where did it all go? memsize to the rescue!
+
+To get started, find a value that references all your objects and scan it.
+This traverses the graph, counting sizes per type.
+
+    sizes := memsize.Scan(myValue)
+    fmt.Println(sizes.Total)
+
+memsize can handle cycles just fine and tracks both private and public struct fields.
+Unfortunately function closures cannot be inspected in any way.
+*/
+package memsize
diff --git a/vendor/github.com/fjl/memsize/memsize.go b/vendor/github.com/fjl/memsize/memsize.go
new file mode 100644
index 000000000..2664e87c4
--- /dev/null
+++ b/vendor/github.com/fjl/memsize/memsize.go
@@ -0,0 +1,243 @@
+package memsize
+
+import (
+	"bytes"
+	"fmt"
+	"reflect"
+	"sort"
+	"strings"
+	"text/tabwriter"
+	"unsafe"
+)
+
+// Scan traverses all objects reachable from v and counts how much memory
+// is used per type. The value must be a non-nil pointer to any value.
+func Scan(v interface{}) Sizes {
+	rv := reflect.ValueOf(v)
+	if rv.Kind() != reflect.Ptr || rv.IsNil() {
+		panic("value to scan must be non-nil pointer")
+	}
+
+	stopTheWorld("memsize scan")
+	defer startTheWorld()
+
+	ctx := newContext()
+	ctx.scan(invalidAddr, rv, false)
+	ctx.s.BitmapSize = ctx.seen.size()
+	ctx.s.BitmapUtilization = ctx.seen.utilization()
+	return *ctx.s
+}
+
+// Sizes is the result of a scan.
+type Sizes struct {
+	Total  uintptr
+	ByType map[reflect.Type]*TypeSize
+	// Internal stats (for debugging)
+	BitmapSize        uintptr
+	BitmapUtilization float32
+}
+
+type TypeSize struct {
+	Total uintptr
+	Count uintptr
+}
+
+func newSizes() *Sizes {
+	return &Sizes{ByType: make(map[reflect.Type]*TypeSize)}
+}
+
+// Report returns a human-readable report.
+func (s Sizes) Report() string {
+	type typLine struct {
+		name  string
+		count uintptr
+		total uintptr
+	}
+	tab := []typLine{{"ALL", 0, s.Total}}
+	for _, typ := range s.ByType {
+		tab[0].count += typ.Count
+	}
+	maxname := 0
+	for typ, s := range s.ByType {
+		line := typLine{typ.String(), s.Count, s.Total}
+		tab = append(tab, line)
+		if len(line.name) > maxname {
+			maxname = len(line.name)
+		}
+	}
+	sort.Slice(tab, func(i, j int) bool { return tab[i].total > tab[j].total })
+
+	buf := new(bytes.Buffer)
+	w := tabwriter.NewWriter(buf, 0, 0, 0, ' ', tabwriter.AlignRight)
+	for _, line := range tab {
+		namespace := strings.Repeat(" ", maxname-len(line.name))
+		fmt.Fprintf(w, "%s%s\t  %v\t  %s\t\n", line.name, namespace, line.count, HumanSize(line.total))
+	}
+	w.Flush()
+	return buf.String()
+}
+
+// addValue is called during scan and adds the memory of given object.
+func (s *Sizes) addValue(v reflect.Value, size uintptr) {
+	s.Total += size
+	rs := s.ByType[v.Type()]
+	if rs == nil {
+		rs = new(TypeSize)
+		s.ByType[v.Type()] = rs
+	}
+	rs.Total += size
+	rs.Count++
+}
+
+type context struct {
+	// We track previously scanned objects to prevent infinite loops
+	// when scanning cycles and to prevent counting objects more than once.
+	seen *bitmap
+	tc   typCache
+	s    *Sizes
+}
+
+func newContext() *context {
+	return &context{seen: newBitmap(), tc: make(typCache), s: newSizes()}
+}
+
+// scan walks all objects below v, determining their size. All scan* functions return the
+// amount of 'extra' memory (e.g. slice data) that is referenced by the object.
+func (c *context) scan(addr address, v reflect.Value, add bool) (extraSize uintptr) {
+	size := v.Type().Size()
+	var marked uintptr
+	if addr.valid() {
+		marked = c.seen.countRange(uintptr(addr), size)
+		if marked == size {
+			return 0 // Skip if we have already seen the whole object.
+		}
+		c.seen.markRange(uintptr(addr), size)
+	}
+	// fmt.Printf("%v: %v ⮑ (marked %d)\n", addr, v.Type(), marked)
+	if c.tc.needScan(v.Type()) {
+		extraSize = c.scanContent(addr, v)
+	}
+	// fmt.Printf("%v: %v %d (add %v, size %d, marked %d, extra %d)\n", addr, v.Type(), size+extraSize, add, v.Type().Size(), marked, extraSize)
+	if add {
+		size -= marked
+		size += extraSize
+		c.s.addValue(v, size)
+	}
+	return extraSize
+}
+
+func (c *context) scanContent(addr address, v reflect.Value) uintptr {
+	switch v.Kind() {
+	case reflect.Array:
+		return c.scanArray(addr, v)
+	case reflect.Chan:
+		return c.scanChan(v)
+	case reflect.Func:
+		// can't do anything here
+		return 0
+	case reflect.Interface:
+		return c.scanInterface(v)
+	case reflect.Map:
+		return c.scanMap(v)
+	case reflect.Ptr:
+		if !v.IsNil() {
+			c.scan(address(v.Pointer()), v.Elem(), true)
+		}
+		return 0
+	case reflect.Slice:
+		return c.scanSlice(v)
+	case reflect.String:
+		return uintptr(v.Len())
+	case reflect.Struct:
+		return c.scanStruct(addr, v)
+	default:
+		unhandledKind(v.Kind())
+		return 0
+	}
+}
+
+func (c *context) scanChan(v reflect.Value) uintptr {
+	etyp := v.Type().Elem()
+	extra := uintptr(0)
+	if c.tc.needScan(etyp) {
+		// Scan the channel buffer. This is unsafe but doesn't race because
+		// the world is stopped during scan.
+		hchan := unsafe.Pointer(v.Pointer())
+		for i := uint(0); i < uint(v.Cap()); i++ {
+			addr := chanbuf(hchan, i)
+			elem := reflect.NewAt(etyp, addr).Elem()
+			extra += c.scanContent(address(addr), elem)
+		}
+	}
+	return uintptr(v.Cap())*etyp.Size() + extra
+}
+
+func (c *context) scanStruct(base address, v reflect.Value) uintptr {
+	extra := uintptr(0)
+	for i := 0; i < v.NumField(); i++ {
+		f := v.Type().Field(i)
+		if c.tc.needScan(f.Type) {
+			addr := base.addOffset(f.Offset)
+			extra += c.scanContent(addr, v.Field(i))
+		}
+	}
+	return extra
+}
+
+func (c *context) scanArray(addr address, v reflect.Value) uintptr {
+	esize := v.Type().Elem().Size()
+	extra := uintptr(0)
+	for i := 0; i < v.Len(); i++ {
+		extra += c.scanContent(addr, v.Index(i))
+		addr = addr.addOffset(esize)
+	}
+	return extra
+}
+
+func (c *context) scanSlice(v reflect.Value) uintptr {
+	slice := v.Slice(0, v.Cap())
+	esize := slice.Type().Elem().Size()
+	base := slice.Pointer()
+	// Add size of the unscanned portion of the backing array to extra.
+	blen := uintptr(slice.Len()) * esize
+	marked := c.seen.countRange(base, blen)
+	extra := blen - marked
+	c.seen.markRange(uintptr(base), blen)
+	if c.tc.needScan(slice.Type().Elem()) {
+		// Elements may contain pointers, scan them individually.
+		addr := address(base)
+		for i := 0; i < slice.Len(); i++ {
+			extra += c.scanContent(addr, slice.Index(i))
+			addr = addr.addOffset(esize)
+		}
+	}
+	return extra
+}
+
+func (c *context) scanMap(v reflect.Value) uintptr {
+	var (
+		typ   = v.Type()
+		len   = uintptr(v.Len())
+		extra = uintptr(0)
+	)
+	if c.tc.needScan(typ.Key()) || c.tc.needScan(typ.Elem()) {
+		for _, k := range v.MapKeys() {
+			extra += c.scan(invalidAddr, k, false)
+			extra += c.scan(invalidAddr, v.MapIndex(k), false)
+		}
+	}
+	return len*typ.Key().Size() + len*typ.Elem().Size() + extra
+}
+
+func (c *context) scanInterface(v reflect.Value) uintptr {
+	elem := v.Elem()
+	if !elem.IsValid() {
+		return 0 // nil interface
+	}
+	c.scan(invalidAddr, elem, false)
+	if !c.tc.isPointer(elem.Type()) {
+		// Account for non-pointer size of the value.
+		return elem.Type().Size()
+	}
+	return 0
+}
diff --git a/vendor/github.com/fjl/memsize/memsizeui/template.go b/vendor/github.com/fjl/memsize/memsizeui/template.go
new file mode 100644
index 000000000..b60fe6ba5
--- /dev/null
+++ b/vendor/github.com/fjl/memsize/memsizeui/template.go
@@ -0,0 +1,106 @@
+package memsizeui
+
+import (
+	"html/template"
+	"strconv"
+	"sync"
+
+	"github.com/fjl/memsize"
+)
+
+var (
+	base         *template.Template // the "base" template
+	baseInitOnce sync.Once
+)
+
+func baseInit() {
+	base = template.Must(template.New("base").Parse(`<!DOCTYPE html>
+<html>
+	<head>
+		<meta charset="UTF-8">
+		<title>memsize</title>
+		<style>
+		body {
+			 font-family: sans-serif;
+		}
+		button, .button {
+			 display: inline-block;
+			 font-weight: bold;
+			 color: black;
+			 text-decoration: none;
+			 font-size: inherit;
+			 padding: 3pt;
+			 margin: 3pt;
+			 background-color: #eee;
+			 border: 1px solid #999;
+			 border-radius: 2pt;
+		}
+		form.inline {
+			display: inline-block;
+		}
+		</style>
+	</head>
+	<body>
+		{{template "content" .}}
+	</body>
+</html>`))
+
+	base.Funcs(template.FuncMap{
+		"quote":     strconv.Quote,
+		"humansize": memsize.HumanSize,
+	})
+
+	template.Must(base.New("rootbuttons").Parse(`
+<a class="button" href="{{$.Link ""}}">Overview</a>
+{{- range $root := .Roots -}}
+<form class="inline" method="POST" action="{{$.Link "scan?root=" $root}}">
+	<button type="submit">Scan {{quote $root}}</button>
+</form>
+{{- end -}}`))
+}
+
+func contentTemplate(source string) *template.Template {
+	baseInitOnce.Do(baseInit)
+	t := template.Must(base.Clone())
+	template.Must(t.New("content").Parse(source))
+	return t
+}
+
+var rootTemplate = contentTemplate(`
+<h1>Memsize</h1>
+{{template "rootbuttons" .}}
+<hr/>
+<h3>Reports</h3>
+<ul>
+	{{range .Reports}}
+		<li><a href="{{printf "%d" | $.Link "report/"}}">{{quote .RootName}} @ {{.Date}}</a></li>
+	{{else}}
+		No reports yet, hit a scan button to create one.
+	{{end}}
+</ul>
+`)
+
+var notFoundTemplate = contentTemplate(`
+<h1>{{.Data}}</h1>
+{{template "rootbuttons" .}}
+`)
+
+var reportTemplate = contentTemplate(`
+{{- $report := .Data -}}
+<h1>Memsize Report {{$report.ID}}</h1>
+<form method="POST" action="{{$.Link "scan?root=" $report.RootName}}">
+	<a class="button" href="{{$.Link ""}}">Overview</a>
+	<button type="submit">Scan Again</button>
+</form>
+<pre>
+Root: {{quote $report.RootName}}
+Date: {{$report.Date}}
+Duration: {{$report.Duration}}
+Bitmap Size: {{$report.Sizes.BitmapSize | humansize}}
+Bitmap Utilization: {{$report.Sizes.BitmapUtilization}}
+</pre>
+<hr/>
+<pre>
+{{$report.Sizes.Report}}
+</pre>
+`)
diff --git a/vendor/github.com/fjl/memsize/memsizeui/ui.go b/vendor/github.com/fjl/memsize/memsizeui/ui.go
new file mode 100644
index 000000000..c48fc53f7
--- /dev/null
+++ b/vendor/github.com/fjl/memsize/memsizeui/ui.go
@@ -0,0 +1,153 @@
+package memsizeui
+
+import (
+	"bytes"
+	"fmt"
+	"html/template"
+	"net/http"
+	"reflect"
+	"sort"
+	"strings"
+	"sync"
+	"time"
+
+	"github.com/fjl/memsize"
+)
+
+type Handler struct {
+	init     sync.Once
+	mux      http.ServeMux
+	mu       sync.Mutex
+	reports  map[int]Report
+	roots    map[string]interface{}
+	reportID int
+}
+
+type Report struct {
+	ID       int
+	Date     time.Time
+	Duration time.Duration
+	RootName string
+	Sizes    memsize.Sizes
+}
+
+type templateInfo struct {
+	Roots     []string
+	Reports   map[int]Report
+	PathDepth int
+	Data      interface{}
+}
+
+func (ti *templateInfo) Link(path ...string) string {
+	prefix := strings.Repeat("../", ti.PathDepth)
+	return prefix + strings.Join(path, "")
+}
+
+func (h *Handler) Add(name string, v interface{}) {
+	rv := reflect.ValueOf(v)
+	if rv.Kind() != reflect.Ptr || rv.IsNil() {
+		panic("root must be non-nil pointer")
+	}
+	h.mu.Lock()
+	if h.roots == nil {
+		h.roots = make(map[string]interface{})
+	}
+	h.roots[name] = v
+	h.mu.Unlock()
+}
+
+func (h *Handler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
+	h.init.Do(func() {
+		h.reports = make(map[int]Report)
+		h.mux.HandleFunc("/", h.handleRoot)
+		h.mux.HandleFunc("/scan", h.handleScan)
+		h.mux.HandleFunc("/report/", h.handleReport)
+	})
+	h.mux.ServeHTTP(w, r)
+}
+
+func (h *Handler) templateInfo(r *http.Request, data interface{}) *templateInfo {
+	h.mu.Lock()
+	roots := make([]string, 0, len(h.roots))
+	for name := range h.roots {
+		roots = append(roots, name)
+	}
+	h.mu.Unlock()
+	sort.Strings(roots)
+
+	return &templateInfo{
+		Roots:     roots,
+		Reports:   h.reports,
+		PathDepth: strings.Count(r.URL.Path, "/") - 1,
+		Data:      data,
+	}
+}
+
+func (h *Handler) handleRoot(w http.ResponseWriter, r *http.Request) {
+	if r.URL.Path != "/" {
+		http.NotFound(w, r)
+		return
+	}
+	serveHTML(w, rootTemplate, http.StatusOK, h.templateInfo(r, nil))
+}
+
+func (h *Handler) handleScan(w http.ResponseWriter, r *http.Request) {
+	if r.Method != http.MethodPost {
+		http.Error(w, "invalid HTTP method, want POST", http.StatusMethodNotAllowed)
+		return
+	}
+	ti := h.templateInfo(r, "Unknown root")
+	id, ok := h.scan(r.URL.Query().Get("root"))
+	if !ok {
+		serveHTML(w, notFoundTemplate, http.StatusNotFound, ti)
+		return
+	}
+	w.Header().Add("Location", ti.Link(fmt.Sprintf("report/%d", id)))
+	w.WriteHeader(http.StatusSeeOther)
+}
+
+func (h *Handler) handleReport(w http.ResponseWriter, r *http.Request) {
+	var id int
+	fmt.Sscan(strings.TrimPrefix(r.URL.Path, "/report/"), &id)
+	h.mu.Lock()
+	report, ok := h.reports[id]
+	h.mu.Unlock()
+
+	if !ok {
+		serveHTML(w, notFoundTemplate, http.StatusNotFound, h.templateInfo(r, "Report not found"))
+	} else {
+		serveHTML(w, reportTemplate, http.StatusOK, h.templateInfo(r, report))
+	}
+}
+
+func (h *Handler) scan(root string) (int, bool) {
+	h.mu.Lock()
+	defer h.mu.Unlock()
+
+	val, ok := h.roots[root]
+	if !ok {
+		return 0, false
+	}
+	id := h.reportID
+	start := time.Now()
+	sizes := memsize.Scan(val)
+	h.reports[id] = Report{
+		ID:       id,
+		RootName: root,
+		Date:     start.Truncate(1 * time.Second),
+		Duration: time.Since(start),
+		Sizes:    sizes,
+	}
+	h.reportID++
+	return id, true
+}
+
+func serveHTML(w http.ResponseWriter, tpl *template.Template, status int, ti *templateInfo) {
+	w.Header().Set("content-type", "text/html")
+	var buf bytes.Buffer
+	if err := tpl.Execute(&buf, ti); err != nil {
+		http.Error(w, err.Error(), http.StatusInternalServerError)
+		return
+	}
+	buf.WriteTo(w)
+}
diff --git a/vendor/github.com/fjl/memsize/runtimefunc.go b/vendor/github.com/fjl/memsize/runtimefunc.go
new file mode 100644
index 000000000..912a3e768
--- /dev/null
+++ b/vendor/github.com/fjl/memsize/runtimefunc.go
@@ -0,0 +1,14 @@
+package memsize
+
+import "unsafe"
+
+var _ = unsafe.Pointer(nil)
+
+//go:linkname stopTheWorld runtime.stopTheWorld
+func stopTheWorld(reason string)
+
+//go:linkname startTheWorld runtime.startTheWorld
+func startTheWorld()
+
+//go:linkname chanbuf runtime.chanbuf
+func chanbuf(ch unsafe.Pointer, i uint) unsafe.Pointer
diff --git a/vendor/github.com/fjl/memsize/runtimefunc.s b/vendor/github.com/fjl/memsize/runtimefunc.s
new file mode 100644
index 000000000..a091e2fa7
--- /dev/null
+++ b/vendor/github.com/fjl/memsize/runtimefunc.s
@@ -0,0 +1 @@
+// This file is required to make stub function declarations work.
diff --git a/vendor/github.com/fjl/memsize/type.go b/vendor/github.com/fjl/memsize/type.go
new file mode 100644
index 000000000..5d6f59e9f
--- /dev/null
+++ b/vendor/github.com/fjl/memsize/type.go
@@ -0,0 +1,119 @@
+package memsize
+
+import (
+	"fmt"
+	"reflect"
+)
+
+// address is a memory location.
+//
+// Code dealing with uintptr is oblivious to the zero address.
+// Code dealing with address is not: it treats the zero address
+// as invalid. Offsetting an invalid address doesn't do anything.
+//
+// This distinction is useful because there are objects that we can't
+// get the pointer to.
+type address uintptr
+
+const invalidAddr = address(0)
+
+func (a address) valid() bool {
+	return a != 0
+}
+
+func (a address) addOffset(off uintptr) address {
+	if !a.valid() {
+		return invalidAddr
+	}
+	return a + address(off)
+}
+
+func (a address) String() string {
+	if uintptrBits == 32 {
+		return fmt.Sprintf("%#0.8x", uintptr(a))
+	}
+	return fmt.Sprintf("%#0.16x", uintptr(a))
+}
+
+type typCache map[reflect.Type]typInfo
+
+type typInfo struct {
+	isPointer bool
+	needScan  bool
+}
+
+// isPointer returns true for pointer-ish values. The notion of
+// pointer includes everything but plain values, i.e. slices, maps
+// channels, interfaces are 'pointer', too.
+func (tc *typCache) isPointer(typ reflect.Type) bool {
+	return tc.info(typ).isPointer
+}
+
+// needScan reports whether a value of the type needs to be scanned
+// recursively because it may contain pointers.
+func (tc *typCache) needScan(typ reflect.Type) bool {
+	return tc.info(typ).needScan
+}
+
+func (tc *typCache) info(typ reflect.Type) typInfo {
+	info, found := (*tc)[typ]
+	switch {
+	case found:
+		return info
+	case isPointer(typ):
+		info = typInfo{true, true}
+	default:
+		info = typInfo{false, tc.checkNeedScan(typ)}
+	}
+	(*tc)[typ] = info
+	return info
+}
+
+func (tc *typCache) checkNeedScan(typ reflect.Type) bool {
+	switch k := typ.Kind(); k {
+	case reflect.Struct:
+		// Structs don't need scan if none of their fields need it.
+		for i := 0; i < typ.NumField(); i++ {
+			if tc.needScan(typ.Field(i).Type) {
+				return true
+			}
+		}
+	case reflect.Array:
+		// Arrays don't need scan if their element type doesn't.
+		return tc.needScan(typ.Elem())
+	}
+	return false
+}
+
+func isPointer(typ reflect.Type) bool {
+	k := typ.Kind()
+	switch {
+	case k <= reflect.Complex128:
+		return false
+	case k == reflect.Array:
+		return false
+	case k >= reflect.Chan && k <= reflect.String:
+		return true
+	case k == reflect.Struct || k == reflect.UnsafePointer:
+		return false
+	default:
+		unhandledKind(k)
+		return false
+	}
+}
+
+func unhandledKind(k reflect.Kind) {
+	panic("unhandled kind " + k.String())
+}
+
+// HumanSize formats the given number of bytes as a readable string.
+func HumanSize(bytes uintptr) string {
+	switch {
+	case bytes < 1024:
+		return fmt.Sprintf("%d B", bytes)
+	case bytes < 1024*1024:
+		return fmt.Sprintf("%.3f KB", float64(bytes)/1024)
+	default:
+		return fmt.Sprintf("%.3f MB", float64(bytes)/1024/1024)
+	}
+}