internal/runtime/maps: initial swiss table map implementation

Add a new package that will contain a new "Swiss Table"
(https://abseil.io/about/design/swisstables) map implementation, which
is intended to eventually replace the existing runtime map
implementation.

This implementation is based on the fabulous
github.com/cockroachdb/swiss package contributed by Peter Mattis.

This CL adds an hash map implementation. It supports all the core
operations, but does not have incremental growth.

For #54766.

Change-Id: I52cf371448c3817d471ddb1f5a78f3513565db41
Reviewed-on: https://go-review.googlesource.com/c/go/+/582415
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
Auto-Submit: Michael Pratt <mpratt@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Michael Knyszek <mknyszek@google.com>

3 files changed, 20 insertions, 0 deletions

diff --git a/src/runtime/malloc.go b/src/runtime/malloc.go
index a35f806aa3..7076ced453 100644
--- a/src/runtime/malloc.go
+++ b/src/runtime/malloc.go
@@ -1450,6 +1450,11 @@ func reflect_unsafe_NewArray(typ *_type, n int) unsafe.Pointer {
 	return newarray(typ, n)
 }
 
+//go:linkname maps_newarray internal/runtime/maps.newarray
+func maps_newarray(typ *_type, n int) unsafe.Pointer {
+	return newarray(typ, n)
+}
+
 func profilealloc(mp *m, x unsafe.Pointer, size uintptr) {
 	c := getMCache(mp)
 	if c == nil {
diff --git a/src/runtime/mbarrier.go b/src/runtime/mbarrier.go
index 054d493f35..dd99bf3a6a 100644
--- a/src/runtime/mbarrier.go
+++ b/src/runtime/mbarrier.go
@@ -244,6 +244,11 @@ func reflectlite_typedmemmove(typ *_type, dst, src unsafe.Pointer) {
 	reflect_typedmemmove(typ, dst, src)
 }
 
+//go:linkname maps_typedmemmove internal/runtime/maps.typedmemmove
+func maps_typedmemmove(typ *_type, dst, src unsafe.Pointer) {
+	typedmemmove(typ, dst, src)
+}
+
 // reflectcallmove is invoked by reflectcall to copy the return values
 // out of the stack and into the heap, invoking the necessary write
 // barriers. dst, src, and size describe the return value area to
@@ -389,6 +394,11 @@ func reflect_typedmemclr(typ *_type, ptr unsafe.Pointer) {
 	typedmemclr(typ, ptr)
 }
 
+//go:linkname maps_typedmemclr internal/runtime/maps.typedmemclr
+func maps_typedmemclr(typ *_type, ptr unsafe.Pointer) {
+	typedmemclr(typ, ptr)
+}
+
 //go:linkname reflect_typedmemclrpartial reflect.typedmemclrpartial
 func reflect_typedmemclrpartial(typ *_type, ptr unsafe.Pointer, off, size uintptr) {
 	if writeBarrier.enabled && typ.Pointers() {
diff --git a/src/runtime/rand.go b/src/runtime/rand.go
index 2e44858ee2..0d1d2fe5ba 100644
--- a/src/runtime/rand.go
+++ b/src/runtime/rand.go
@@ -177,6 +177,11 @@ func rand() uint64 {
 	}
 }
 
+//go:linkname maps_rand internal/runtime/maps.rand
+func maps_rand() uint64 {
+	return rand()
+}
+
 // mrandinit initializes the random state of an m.
 func mrandinit(mp *m) {
 	var seed [4]uint64