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 5 package pprof 6 7 import "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. 11 type 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. 20 type 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 28 func (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 40 Search: 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 e.stk = m.freeStk[:len(stk)] 72 m.freeStk = m.freeStk[len(stk):] 73 74 for j := range stk { 75 e.stk[j] = uintptr(stk[j]) 76 } 77 if m.hash == nil { 78 m.hash = make(map[uintptr]*profMapEntry) 79 } 80 m.hash[h] = e 81 if m.all == nil { 82 m.all = e 83 m.last = e 84 } else { 85 m.last.nextAll = e 86 m.last = e 87 } 88 return e 89 } 90
