Source file src/runtime/pprof/map.go

     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	

View as plain text