map.go

Documentation: runtime/pprof

		 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