summaryrefslogtreecommitdiffstats
path: root/src/runtime/pprof/map.go
blob: 7c75872351383012fc506d8c40596f04290dccdf (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// 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 pprof

import "unsafe"

// A profMap is a map from (stack, tag) to mapEntry.
// It grows without bound, but that's assumed to be OK.
type profMap struct {
	hash    map[uintptr]*profMapEntry
	all     *profMapEntry
	last    *profMapEntry
	free    []profMapEntry
	freeStk []uintptr
}

// A profMapEntry is a single entry in the profMap.
type profMapEntry struct {
	nextHash *profMapEntry // next in hash list
	nextAll  *profMapEntry // next in list of all entries
	stk      []uintptr
	tag      unsafe.Pointer
	count    int64
}

func (m *profMap) lookup(stk []uint64, tag unsafe.Pointer) *profMapEntry {
	// Compute hash of (stk, tag).
	h := uintptr(0)
	for _, x := range stk {
		h = h<<8 | (h >> (8 * (unsafe.Sizeof(h) - 1)))
		h += uintptr(x) * 41
	}
	h = h<<8 | (h >> (8 * (unsafe.Sizeof(h) - 1)))
	h += uintptr(tag) * 41

	// Find entry if present.
	var last *profMapEntry
Search:
	for e := m.hash[h]; e != nil; last, e = e, e.nextHash {
		if len(e.stk) != len(stk) || e.tag != tag {
			continue
		}
		for j := range stk {
			if e.stk[j] != uintptr(stk[j]) {
				continue Search
			}
		}
		// Move to front.
		if last != nil {
			last.nextHash = e.nextHash
			e.nextHash = m.hash[h]
			m.hash[h] = e
		}
		return e
	}

	// Add new entry.
	if len(m.free) < 1 {
		m.free = make([]profMapEntry, 128)
	}
	e := &m.free[0]
	m.free = m.free[1:]
	e.nextHash = m.hash[h]
	e.tag = tag

	if len(m.freeStk) < len(stk) {
		m.freeStk = make([]uintptr, 1024)
	}
	// Limit cap to prevent append from clobbering freeStk.
	e.stk = m.freeStk[:len(stk):len(stk)]
	m.freeStk = m.freeStk[len(stk):]

	for j := range stk {
		e.stk[j] = uintptr(stk[j])
	}
	if m.hash == nil {
		m.hash = make(map[uintptr]*profMapEntry)
	}
	m.hash[h] = e
	if m.all == nil {
		m.all = e
		m.last = e
	} else {
		m.last.nextAll = e
		m.last = e
	}
	return e
}