table_debug.go

     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
View as plain text