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