1// Copyright 2017 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
5package pprof
6
7import "unsafe"
8
9// A profMap is a map from (stack, tag) to mapEntry.
10// It grows without bound, but that's assumed to be OK.
11type profMap struct {
12	hash    map[uintptr]*profMapEntry
13	all     *profMapEntry
14	last    *profMapEntry
15	free    []profMapEntry
16	freeStk []uintptr
17}
18
19// A profMapEntry is a single entry in the profMap.
20type profMapEntry struct {
21	nextHash *profMapEntry // next in hash list
22	nextAll  *profMapEntry // next in list of all entries
23	stk      []uintptr
24	tag      unsafe.Pointer
25	count    int64
26}
27
28func (m *profMap) lookup(stk []uint64, tag unsafe.Pointer) *profMapEntry {
29	// Compute hash of (stk, tag).
30	h := uintptr(0)
31	for _, x := range stk {
32		h = h<<8 | (h >> (8 * (unsafe.Sizeof(h) - 1)))
33		h += uintptr(x) * 41
34	}
35	h = h<<8 | (h >> (8 * (unsafe.Sizeof(h) - 1)))
36	h += uintptr(tag) * 41
37
38	// Find entry if present.
39	var last *profMapEntry
40Search:
41	for e := m.hash[h]; e != nil; last, e = e, e.nextHash {
42		if len(e.stk) != len(stk) || e.tag != tag {
43			continue
44		}
45		for j := range stk {
46			if e.stk[j] != uintptr(stk[j]) {
47				continue Search
48			}
49		}
50		// Move to front.
51		if last != nil {
52			last.nextHash = e.nextHash
53			e.nextHash = m.hash[h]
54			m.hash[h] = e
55		}
56		return e
57	}
58
59	// Add new entry.
60	if len(m.free) < 1 {
61		m.free = make([]profMapEntry, 128)
62	}
63	e := &m.free[0]
64	m.free = m.free[1:]
65	e.nextHash = m.hash[h]
66	e.tag = tag
67
68	if len(m.freeStk) < len(stk) {
69		m.freeStk = make([]uintptr, 1024)
70	}
71	// Limit cap to prevent append from clobbering freeStk.
72	e.stk = m.freeStk[:len(stk):len(stk)]
73	m.freeStk = m.freeStk[len(stk):]
74
75	for j := range stk {
76		e.stk[j] = uintptr(stk[j])
77	}
78	if m.hash == nil {
79		m.hash = make(map[uintptr]*profMapEntry)
80	}
81	m.hash[h] = e
82	if m.all == nil {
83		m.all = e
84		m.last = e
85	} else {
86		m.last.nextAll = e
87		m.last = e
88	}
89	return e
90}
91