all: wire up swisstable maps

Use the new SwissTable-based map in internal/runtime/maps as the basis
for the runtime map when GOEXPERIMENT=swissmap.

Integration is complete enough to pass all.bash. Notable missing
features:

* Race integration / concurrent write detection
* Stack-allocated maps
* Specialized "fast" map variants
* Indirect key / elem

For #54766.

Cq-Include-Trybots: luci.golang.try:gotip-linux-ppc64_power10,gotip-linux-amd64-longtest-swissmap
Change-Id: Ie97b656b6d8e05c0403311ae08fef9f51756a639
Reviewed-on: https://go-review.googlesource.com/c/go/+/594596
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

8 files changed, 91 insertions, 85 deletions

diff --git a/src/internal/runtime/maps/export_noswiss_test.go b/src/internal/runtime/maps/export_noswiss_test.go
new file mode 100644
index 0000000000..32d6d13412
--- /dev/null
+++ b/src/internal/runtime/maps/export_noswiss_test.go
@@ -0,0 +1,50 @@
+// 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.
+
+//go:build !goexperiment.swissmap
+
+// This file allows non-GOEXPERIMENT=swissmap builds (i.e., old map builds) to
+// construct a swissmap table for running the tests in this package.
+
+package maps
+
+import (
+	"internal/abi"
+	"unsafe"
+)
+
+type instantiatedGroup[K comparable, V any] struct {
+	ctrls ctrlGroup
+	slots [abi.SwissMapGroupSlots]instantiatedSlot[K, V]
+}
+
+type instantiatedSlot[K comparable, V any] struct {
+	key  K
+	elem V
+}
+
+func NewTestTable[K comparable, V any](length uint64) *table {
+	var m map[K]V
+	mTyp := abi.TypeOf(m)
+	omt := (*abi.OldMapType)(unsafe.Pointer(mTyp))
+
+	var grp instantiatedGroup[K, V]
+	var slot instantiatedSlot[K, V]
+
+	mt := &abi.SwissMapType{
+		Key:      omt.Key,
+		Elem:     omt.Elem,
+		Group:    abi.TypeOf(grp),
+		Hasher:   omt.Hasher,
+		SlotSize: unsafe.Sizeof(slot),
+		ElemOff:  unsafe.Offsetof(slot.elem),
+	}
+	if omt.NeedKeyUpdate() {
+		mt.Flags |= abi.SwissMapNeedKeyUpdate
+	}
+	if omt.HashMightPanic() {
+		mt.Flags |= abi.SwissMapHashMightPanic
+	}
+	return newTable(mt, length)
+}
diff --git a/src/internal/runtime/maps/export_swiss_test.go b/src/internal/runtime/maps/export_swiss_test.go
new file mode 100644
index 0000000000..9a123240d5
--- /dev/null
+++ b/src/internal/runtime/maps/export_swiss_test.go
@@ -0,0 +1,19 @@
+// 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.
+
+//go:build goexperiment.swissmap
+
+package maps
+
+import (
+	"internal/abi"
+	"unsafe"
+)
+
+func NewTestTable[K comparable, V any](length uint64) *table {
+	var m map[K]V
+	mTyp := abi.TypeOf(m)
+	mt := (*abi.SwissMapType)(unsafe.Pointer(mTyp))
+	return newTable(mt, length)
+}
diff --git a/src/internal/runtime/maps/export_test.go b/src/internal/runtime/maps/export_test.go
index e2512d332a..2856a7314e 100644
--- a/src/internal/runtime/maps/export_test.go
+++ b/src/internal/runtime/maps/export_test.go
@@ -6,7 +6,6 @@ package maps
 
 import (
 	"internal/abi"
-	sabi "internal/runtime/maps/internal/abi"
 	"unsafe"
 )
 
@@ -16,41 +15,16 @@ const DebugLog = debugLog
 
 var AlignUpPow2 = alignUpPow2
 
-type instantiatedGroup[K comparable, V any] struct {
-	ctrls ctrlGroup
-	slots [sabi.SwissMapGroupSlots]instantiatedSlot[K, V]
-}
-
-type instantiatedSlot[K comparable, V any] struct {
-	key  K
-	elem V
+func (t *table) Type() *abi.SwissMapType {
+	return t.typ
 }
 
-func NewTestTable[K comparable, V any](length uint64) *table {
-	var m map[K]V
-	mTyp := abi.TypeOf(m)
-	omt := (*abi.OldMapType)(unsafe.Pointer(mTyp))
-
-	var grp instantiatedGroup[K, V]
-	var slot instantiatedSlot[K, V]
-
-	mt := &sabi.SwissMapType{
-		Key:      omt.Key,
-		Elem:     omt.Elem,
-		Group:    abi.TypeOf(grp),
-		Hasher:   omt.Hasher,
-		SlotSize: unsafe.Sizeof(slot),
-		ElemOff:  unsafe.Offsetof(slot.elem),
-	}
-	if omt.NeedKeyUpdate() {
-		mt.Flags |= sabi.SwissMapNeedKeyUpdate
-	}
-	if omt.HashMightPanic() {
-		mt.Flags |= sabi.SwissMapHashMightPanic
-	}
-	return newTable(mt, length)
+// Returns the start address of the groups array.
+func (t *table) GroupsStart() unsafe.Pointer {
+	return t.groups.data
 }
 
-func (t *table) Type() *sabi.SwissMapType {
-	return t.typ
+// Returns the length of the groups array.
+func (t *table) GroupsLength() uintptr {
+	return uintptr(t.groups.lengthMask + 1)
 }
diff --git a/src/internal/runtime/maps/group.go b/src/internal/runtime/maps/group.go
index 822e3773ea..e03ed98c94 100644
--- a/src/internal/runtime/maps/group.go
+++ b/src/internal/runtime/maps/group.go
@@ -5,8 +5,8 @@
 package maps
 
 import (
+	"internal/abi"
 	"internal/goarch"
-	"internal/runtime/maps/internal/abi"
 	"internal/runtime/sys"
 	"unsafe"
 )
diff --git a/src/internal/runtime/maps/internal/abi/map_swiss.go b/src/internal/runtime/maps/internal/abi/map_swiss.go
deleted file mode 100644
index caa08274e1..0000000000
--- a/src/internal/runtime/maps/internal/abi/map_swiss.go
+++ /dev/null
@@ -1,44 +0,0 @@
-// Copyright 2023 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 abi is a temporary copy of the swissmap abi. It will be eliminated
-// once swissmaps are integrated into the runtime.
-package abi
-
-import (
-	"internal/abi"
-	"unsafe"
-)
-
-// Map constants common to several packages
-// runtime/runtime-gdb.py:MapTypePrinter contains its own copy
-const (
-	// Number of slots in a group.
-	SwissMapGroupSlots = 8
-)
-
-type SwissMapType struct {
-	abi.Type
-	Key   *abi.Type
-	Elem  *abi.Type
-	Group *abi.Type // internal type representing a slot group
-	// function for hashing keys (ptr to key, seed) -> hash
-	Hasher     func(unsafe.Pointer, uintptr) uintptr
-	SlotSize   uintptr // size of key/elem slot
-	ElemOff    uintptr // offset of elem in key/elem slot
-	Flags      uint32
-}
-
-// Flag values
-const (
-	SwissMapNeedKeyUpdate = 1 << iota
-	SwissMapHashMightPanic
-)
-
-func (mt *SwissMapType) NeedKeyUpdate() bool { // true if we need to update key on an overwrite
-	return mt.Flags&SwissMapNeedKeyUpdate != 0
-}
-func (mt *SwissMapType) HashMightPanic() bool { // true if hash function might panic
-	return mt.Flags&SwissMapHashMightPanic != 0
-}
diff --git a/src/internal/runtime/maps/map_test.go b/src/internal/runtime/maps/map_test.go
index 53b4a62071..d11535657b 100644
--- a/src/internal/runtime/maps/map_test.go
+++ b/src/internal/runtime/maps/map_test.go
@@ -6,8 +6,8 @@ package maps_test
 
 import (
 	"fmt"
+	"internal/abi"
 	"internal/runtime/maps"
-	"internal/runtime/maps/internal/abi"
 	"math"
 	"testing"
 	"unsafe"
@@ -444,4 +444,11 @@ func TestTableZeroSizeSlot(t *testing.T) {
 	if gotElem != elem {
 		t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
 	}
+
+	start := tab.GroupsStart()
+	length := tab.GroupsLength()
+	end := unsafe.Pointer(uintptr(start) + length*tab.Type().Group.Size() - 1) // inclusive to ensure we have a valid pointer
+	if uintptr(got) < uintptr(start) || uintptr(got) > uintptr(end) {
+		t.Errorf("elem address outside groups allocation; got %p want [%p, %p]", got, start, end)
+	}
 }
diff --git a/src/internal/runtime/maps/table.go b/src/internal/runtime/maps/table.go
index 3516b92fba..2c13be8468 100644
--- a/src/internal/runtime/maps/table.go
+++ b/src/internal/runtime/maps/table.go
@@ -6,7 +6,7 @@
 package maps
 
 import (
-	"internal/runtime/maps/internal/abi"
+	"internal/abi"
 	"unsafe"
 )
 
diff --git a/src/internal/runtime/maps/table_debug.go b/src/internal/runtime/maps/table_debug.go
index 7170fb68fe..b800858e55 100644
--- a/src/internal/runtime/maps/table_debug.go
+++ b/src/internal/runtime/maps/table_debug.go
@@ -6,7 +6,7 @@
 package maps
 
 import (
-	sabi "internal/runtime/maps/internal/abi"
+	"internal/abi"
 	"unsafe"
 )
 
@@ -24,7 +24,7 @@ func (t *table) checkInvariants() {
 	var empty uint64
 	for i := uint64(0); i <= t.groups.lengthMask; i++ {
 		g := t.groups.group(i)
-		for j := uint32(0); j < sabi.SwissMapGroupSlots; j++ {
+		for j := uint32(0); j < abi.SwissMapGroupSlots; j++ {
 			c := g.ctrls().get(j)
 			switch {
 			case c == ctrlDeleted:
@@ -60,7 +60,7 @@ func (t *table) checkInvariants() {
 		panic("invariant failed: found mismatched used slot count")
 	}
 
-	growthLeft := (t.capacity*maxAvgGroupLoad)/sabi.SwissMapGroupSlots - t.used - deleted
+	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()
@@ -93,7 +93,7 @@ func (t *table) Print() {
 
 		g := t.groups.group(i)
 		ctrls := g.ctrls()
-		for j := uint32(0); j < sabi.SwissMapGroupSlots; j++ {
+		for j := uint32(0); j < abi.SwissMapGroupSlots; j++ {
 			print("\t\t\tslot ", j, "\n")
 
 			c := ctrls.get(j)