1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
// Copyright 2024 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package maps implements Go's builtin map type.
package maps
import (
"internal/abi"
"unsafe"
)
const debugLog = false
func (t *table) checkInvariants(typ *abi.SwissMapType, m *Map) {
if !debugLog {
return
}
// For every non-empty slot, verify we can retrieve the key using Get.
// Count the number of used and deleted slots.
var used uint16
var deleted uint16
var empty uint16
for i := uint64(0); i <= t.groups.lengthMask; i++ {
g := t.groups.group(typ, i)
for j := uintptr(0); j < abi.SwissMapGroupSlots; j++ {
c := g.ctrls().get(j)
switch {
case c == ctrlDeleted:
deleted++
case c == ctrlEmpty:
empty++
default:
used++
key := g.key(typ, j)
if typ.IndirectKey() {
key = *((*unsafe.Pointer)(key))
}
// Can't lookup keys that don't compare equal
// to themselves (e.g., NaN).
if !typ.Key.Equal(key, key) {
continue
}
if _, ok := t.Get(typ, m, key); !ok {
hash := typ.Hasher(key, m.seed)
print("invariant failed: slot(", i, "/", j, "): key ")
dump(key, typ.Key.Size_)
print(" not found [hash=", hash, ", h2=", h2(hash), " h1=", h1(hash), "]\n")
t.Print(typ, m)
panic("invariant failed: slot: key not found")
}
}
}
}
if used != t.used {
print("invariant failed: found ", used, " used slots, but used count is ", t.used, "\n")
t.Print(typ, m)
panic("invariant failed: found mismatched used slot count")
}
growthLeft := (t.capacity*maxAvgGroupLoad)/abi.SwissMapGroupSlots - t.used - deleted
if growthLeft != t.growthLeft {
print("invariant failed: found ", t.growthLeft, " growthLeft, but expected ", growthLeft, "\n")
t.Print(typ, m)
panic("invariant failed: found mismatched growthLeft")
}
if deleted != t.tombstones() {
print("invariant failed: found ", deleted, " tombstones, but expected ", t.tombstones(), "\n")
t.Print(typ, m)
panic("invariant failed: found mismatched tombstones")
}
if empty == 0 {
print("invariant failed: found no empty slots (violates probe invariant)\n")
t.Print(typ, m)
panic("invariant failed: found no empty slots (violates probe invariant)")
}
}
func (t *table) Print(typ *abi.SwissMapType, m *Map) {
print(`table{
index: `, t.index, `
localDepth: `, t.localDepth, `
capacity: `, t.capacity, `
used: `, t.used, `
growthLeft: `, t.growthLeft, `
groups:
`)
for i := uint64(0); i <= t.groups.lengthMask; i++ {
print("\t\tgroup ", i, "\n")
g := t.groups.group(typ, i)
ctrls := g.ctrls()
for j := uintptr(0); j < abi.SwissMapGroupSlots; j++ {
print("\t\t\tslot ", j, "\n")
c := ctrls.get(j)
print("\t\t\t\tctrl ", c)
switch c {
case ctrlEmpty:
print(" (empty)\n")
case ctrlDeleted:
print(" (deleted)\n")
default:
print("\n")
}
print("\t\t\t\tkey ")
dump(g.key(typ, j), typ.Key.Size_)
println("")
print("\t\t\t\telem ")
dump(g.elem(typ, j), typ.Elem.Size_)
println("")
}
}
}
// TODO(prattmic): not in hex because print doesn't have a way to print in hex
// outside the runtime.
func dump(ptr unsafe.Pointer, size uintptr) {
for size > 0 {
print(*(*byte)(ptr), " ")
ptr = unsafe.Pointer(uintptr(ptr) + 1)
size--
}
}
|
