1
v,ok := m[key] ==> mapaccess2()
2
v := m[key] ==> mapaccess1()

1
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
2
  // 一些运行时处理，这里省略
3
  someRuntimeProcess()
4
  if h == nil || h.count == 0 {
5
    if t.hashMightPanic() {
6
      t.hasher(key, 0) // see issue 23734
7
    }
8
    return unsafe.Pointer(&zeroVal[0])
9
  }
10
  if h.flags&hashWriting != 0 {
11
    fatal("concurrent map read and map write")
12
  }
13
  hash := t.hasher(key, uintptr(h.hash0))
14
  m := bucketMask(h.B)
15
  b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
16

17
  if c := h.oldbuckets; c != nil {
18
    if !h.sameSizeGrow() {
19
      // There used to be half as many buckets; mask down one more power of two.
20
      m >>= 1
21
    }
22
    oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
23
    if !evacuated(oldb) {
24
      b = oldb
25
    }
26
  }
27
  top := tophash(hash)
28
bucketloop:
29
  for ; b != nil; b = b.overflow(t) {
30
    for i := uintptr(0); i < bucketCnt; i++ {
31
      if b.tophash[i] != top {
32
        if b.tophash[i] == emptyRest {
33
          break bucketloop
34
        }
35
        continue
36
      }
37
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
38
      if t.indirectkey() {
39
        k = *((*unsafe.Pointer)(k))
40
      }
41
      if t.key.equal(key, k) {
42
        e := add(
43
          unsafe.Pointer(b),
44
          dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize),
45
        )
46
        if t.indirectelem() {
47
          e = *((*unsafe.Pointer)(e))
48
        }
49
        return e
50
      }
51
    }
52
  }
53
  return unsafe.Pointer(&zeroVal[0])
54
}

1
// Like mapaccess, but allocates a slot for the key if it is not present in the map.
2
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
3
  someRuntimeProcess()
4
  if h.flags&hashWriting != 0 {
5
    fatal("concurrent map writes")
6
  }
7
  hash := t.hasher(key, uintptr(h.hash0))
8

9
  // Set hashWriting after calling t.hasher, since t.hasher may panic,
10
  // in which case we have not actually done a write.
11
  h.flags ^= hashWriting
12

13
  if h.buckets == nil {
14
    h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
15
  }
16

17
again:
18
  bucket := hash & bucketMask(h.B)
19
  if h.growing() {
20
    growWork(t, h, bucket)
21
  }
22
  b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
23
  top := tophash(hash)
24

25
  var inserti *uint8
26
  var insertk unsafe.Pointer
27
  var elem unsafe.Pointer
28
bucketloop:
29
  for {
30
    for i := uintptr(0); i < bucketCnt; i++ {
31
      if b.tophash[i] != top {
32
        if isEmpty(b.tophash[i]) && inserti == nil {
33
          inserti = &b.tophash[i]
34
          insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
35
          elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
36
        }
37
        if b.tophash[i] == emptyRest {
38
          break bucketloop
39
        }
40
        continue
41
      }
42
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
43
      if t.indirectkey() {
44
        k = *((*unsafe.Pointer)(k))
45
      }
46
      if !t.key.equal(key, k) {
47
        continue
48
      }
49
      // already have a mapping for key. Update it.
50
      if t.needkeyupdate() {
51
        typedmemmove(t.key, k, key)
52
      }
53
      elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
54
      goto done
55
    }
56
    ovf := b.overflow(t)
57
    if ovf == nil {
58
      break
59
    }
60
    b = ovf
61
  }
62

63
  // Did not find mapping for key. Allocate new cell & add entry.
64

65
  // If we hit the max load factor or we have too many overflow buckets,
66
  // and we're not already in the middle of growing, start growing.
67
  if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
68
    hashGrow(t, h)
69
    goto again // Growing the table invalidates everything, so try again
70
  }
71

72
  if inserti == nil {
73
    // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
74
    newb := h.newoverflow(t, b)
75
    inserti = &newb.tophash[0]
76
    insertk = add(unsafe.Pointer(newb), dataOffset)
77
    elem = add(insertk, bucketCnt*uintptr(t.keysize))
78
  }
79

80
  // store new key/elem at insert position
81
  if t.indirectkey() {
82
    kmem := newobject(t.key)
83
    *(*unsafe.Pointer)(insertk) = kmem
84
    insertk = kmem
85
  }
86
  if t.indirectelem() {
87
    vmem := newobject(t.elem)
88
    *(*unsafe.Pointer)(elem) = vmem
89
  }
90
  typedmemmove(t.key, insertk, key)
91
  *inserti = top
92
  h.count++
93

94
done:
95
  if h.flags&hashWriting == 0 {
96
    fatal("concurrent map writes")
97
  }
98
  h.flags &^= hashWriting
99
  if t.indirectelem() {
100
    elem = *((*unsafe.Pointer)(elem))
101
  }
102
  return elem
103
}

1
func hashGrow(t *maptype, h *hmap) {
2
  // If we've hit the load factor, get bigger.
3
  // Otherwise, there are too many overflow buckets,
4
  // so keep the same number of buckets and "grow" laterally.
5
  bigger := uint8(1)
6
  if !overLoadFactor(h.count+1, h.B) {
7
    bigger = 0
8
    h.flags |= sameSizeGrow
9
  }
10
  oldbuckets := h.buckets
11
  newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
12

13
  flags := h.flags &^ (iterator | oldIterator)
14
  if h.flags&iterator != 0 {
15
    flags |= oldIterator
16
  }
17
  // commit the grow (atomic wrt gc)
18
  h.B += bigger
19
  h.flags = flags
20
  h.oldbuckets = oldbuckets
21
  h.buckets = newbuckets
22
  h.nevacuate = 0
23
  h.noverflow = 0
24

25
  if h.extra != nil && h.extra.overflow != nil {
26
    // Promote current overflow buckets to the old generation.
27
    if h.extra.oldoverflow != nil {
28
      throw("oldoverflow is not nil")
29
    }
30
    h.extra.oldoverflow = h.extra.overflow
31
    h.extra.overflow = nil
32
  }
33
  if nextOverflow != nil {
34
    if h.extra == nil {
35
      h.extra = new(mapextra)
36
    }
37
    h.extra.nextOverflow = nextOverflow
38
  }
39
}

1
func growWork(t *maptype, h *hmap, bucket uintptr) {
2
  // make sure we evacuate the oldbucket corresponding
3
  // to the bucket we're about to use
4
  evacuate(t, h, bucket&h.oldbucketmask())
5

6
  // evacuate one more oldbucket to make progress on growing
7
  if h.growing() {
8
    evacuate(t, h, h.nevacuate)
9
  }
10
}

1
// evacDst is an evacuation destination.
2
type evacDst struct {
3
  b *bmap          // current destination bucket
4
  i int            // key/elem index into b
5
  k unsafe.Pointer // pointer to current key storage
6
  e unsafe.Pointer // pointer to current elem storage
7
}
8
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
9
  b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
10
  newbit := h.noldbuckets()
11
  if !evacuated(b) {
12
    // xy contains the x and y (low and high) evacuation destinations.
13
    var xy [2]evacDst
14
    x := &xy[0]
15
    x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
16
    x.k = add(unsafe.Pointer(x.b), dataOffset)
17
    x.e = add(x.k, bucketCnt*uintptr(t.keysize))
18

19
    if !h.sameSizeGrow() {
20
      // Only calculate y pointers if we're growing bigger.
21
      // Otherwise GC can see bad pointers.
22
      y := &xy[1]
23
      y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
24
      y.k = add(unsafe.Pointer(y.b), dataOffset)
25
      y.e = add(y.k, bucketCnt*uintptr(t.keysize))
26
    }
27

28
    for ; b != nil; b = b.overflow(t) {
29
      k := add(unsafe.Pointer(b), dataOffset)
30
      e := add(k, bucketCnt*uintptr(t.keysize))
31
      for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
32
        top := b.tophash[i]
33
        if isEmpty(top) {
34
          b.tophash[i] = evacuatedEmpty
35
          continue
36
        }
37
        if top < minTopHash {
38
          throw("bad map state")
39
        }
40
        k2 := k
41
        if t.indirectkey() {
42
          k2 = *((*unsafe.Pointer)(k2))
43
        }
44
        var useY uint8
45
        if !h.sameSizeGrow() {
46
          // Compute hash to make our evacuation decision (whether we need
47
          // to send this key/elem to bucket x or bucket y).
48
          hash := t.hasher(k2, uintptr(h.hash0))
49
          if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
50
            // If key != key (NaNs), then the hash could be (and probably
51
            // will be) entirely different from the old hash. Moreover,
52
            // it isn't reproducible. Reproducibility is required in the
53
            // presence of iterators, as our evacuation decision must
54
            // match whatever decision the iterator made.
55
            // Fortunately, we have the freedom to send these keys either
56
            // way. Also, tophash is meaningless for these kinds of keys.
57
            // We let the low bit of tophash drive the evacuation decision.
58
            // We recompute a new random tophash for the next level so
59
            // these keys will get evenly distributed across all buckets
60
            // after multiple grows.
61
            useY = top & 1
62
            top = tophash(hash)
63
          } else {
64
            if hash&newbit != 0 {
65
              useY = 1
66
            }
67
          }
68
        }
69

70
        if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
71
          throw("bad evacuatedN")
72
        }
73

74
        b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
75
        dst := &xy[useY]                 // evacuation destination
76

77
        if dst.i == bucketCnt {
78
          dst.b = h.newoverflow(t, dst.b)
79
          dst.i = 0
80
          dst.k = add(unsafe.Pointer(dst.b), dataOffset)
81
          dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
82
        }
83
        dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
84
        if t.indirectkey() {
85
          *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
86
        } else {
87
          typedmemmove(t.key, dst.k, k) // copy elem
88
        }
89
        if t.indirectelem() {
90
          *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
91
        } else {
92
          typedmemmove(t.elem, dst.e, e)
93
        }
94
        dst.i++
95
        // These updates might push these pointers past the end of the
96
        // key or elem arrays.  That's ok, as we have the overflow pointer
97
        // at the end of the bucket to protect against pointing past the
98
        // end of the bucket.
99
        dst.k = add(dst.k, uintptr(t.keysize))
100
        dst.e = add(dst.e, uintptr(t.elemsize))
101
      }
102
    }
103
    // Unlink the overflow buckets & clear key/elem to help GC.
104
    if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
105
      b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
106
      // Preserve b.tophash because the evacuation
107
      // state is maintained there.
108
      ptr := add(b, dataOffset)
109
      n := uintptr(t.bucketsize) - dataOffset
110
      memclrHasPointers(ptr, n)
111
    }
112
  }
113

114
  if oldbucket == h.nevacuate {
115
    advanceEvacuationMark(h, t, newbit)
116
  }
117
}

1
//go:linkname runtime_mapaccess2 runtime.mapaccess2
2
func runtime_mapaccess2(typ *abi.MapType, m *Map, key unsafe.Pointer) (unsafe.Pointer, bool) {
3
  // ...
4

5
  if m == nil || m.Used() == 0 {
6
    if err := mapKeyError(typ, key); err != nil {
7
      panic(err) // see issue 23734
8
    }
9
    return unsafe.Pointer(&zeroVal[0]), false
10
  }
11

12
  if m.writing != 0 {
13
    fatal("concurrent map read and map write")
14
  }
15

16
  hash := typ.Hasher(key, m.seed)
17

18
  // small table case
19
  if m.dirLen == 0 {
20
    _, elem, ok := m.getWithKeySmall(typ, hash, key)
21
    if !ok {
22
      return unsafe.Pointer(&zeroVal[0]), false
23
    }
24
    return elem, true
25
  }
26

27
  // Select table.
28
  idx := m.directoryIndex(hash)
29
  t := m.directoryAt(idx)
30

31
  // Probe table.
32
  seq := makeProbeSeq(h1(hash), t.groups.lengthMask)
33
  h2Hash := h2(hash)
34
  for ; ; seq = seq.next() {
35
    g := t.groups.group(typ, seq.offset)
36

37
    match := g.ctrls().matchH2(h2Hash)
38

39
    for match != 0 {
40
      i := match.first()
41

42
      slotKey := g.key(typ, i)
43
      slotKeyOrig := slotKey
44
      if typ.IndirectKey() {
45
        slotKey = *((*unsafe.Pointer)(slotKey))
46
      }
47
      if typ.Key.Equal(key, slotKey) {
48
        slotElem := unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
49
        if typ.IndirectElem() {
50
          slotElem = *((*unsafe.Pointer)(slotElem))
51
        }
52
        return slotElem, true
53
      }
54
      match = match.removeFirst()
55
    }
56

57
    match = g.ctrls().matchEmpty()
58
    if match != 0 {
59
      // Finding an empty slot means we've reached the end of
60
      // the probe sequence.
61
      return unsafe.Pointer(&zeroVal[0]), false
62
    }
63
  }
64
}