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  	// 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
View as plain text