libgo/go/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 }