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