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>

1 files changed, 115 insertions, 188 deletions

diff --git a/src/cmd/compile/internal/reflectdata/map_swiss.go b/src/cmd/compile/internal/reflectdata/map_swiss.go
index 4fed93517e..2525c0cf2c 100644
--- a/src/cmd/compile/internal/reflectdata/map_swiss.go
+++ b/src/cmd/compile/internal/reflectdata/map_swiss.go
@@ -6,7 +6,6 @@ package reflectdata
 
 import (
 	"internal/abi"
-
 	"cmd/compile/internal/base"
 	"cmd/compile/internal/ir"
 	"cmd/compile/internal/rttype"
@@ -16,161 +15,100 @@ import (
 	"cmd/internal/src"
 )
 
-// SwissMapBucketType makes the map bucket type given the type of the map.
-func SwissMapBucketType(t *types.Type) *types.Type {
-	// Builds a type representing a Bucket structure for
-	// the given map type. This type is not visible to users -
-	// we include only enough information to generate a correct GC
-	// program for it.
-	// Make sure this stays in sync with runtime/map.go.
-	//
-	//	A "bucket" is a "struct" {
-	//	      tophash [abi.SwissMapBucketCount]uint8
-	//	      keys [abi.SwissMapBucketCount]keyType
-	//	      elems [abi.SwissMapBucketCount]elemType
-	//	      overflow *bucket
-	//	    }
-	if t.MapType().SwissBucket != nil {
-		return t.MapType().SwissBucket
+// SwissMapGroupType makes the map slot group type given the type of the map.
+func SwissMapGroupType(t *types.Type) *types.Type {
+	if t.MapType().SwissGroup != nil {
+		return t.MapType().SwissGroup
 	}
 
-	keytype := t.Key()
-	elemtype := t.Elem()
-	types.CalcSize(keytype)
-	types.CalcSize(elemtype)
-	if keytype.Size() > abi.SwissMapMaxKeyBytes {
-		keytype = types.NewPtr(keytype)
-	}
-	if elemtype.Size() > abi.SwissMapMaxElemBytes {
-		elemtype = types.NewPtr(elemtype)
+	// Builds a type representing a group structure for the given map type.
+	// This type is not visible to users, we include it so we can generate
+	// a correct GC program for it.
+	//
+	// Make sure this stays in sync with internal/runtime/maps/group.go.
+	//
+	// type group struct {
+	//     ctrl uint64
+	//     slots [abi.SwissMapGroupSlots]struct {
+	//         key  keyType
+	//         elem elemType
+	//     }
+	// }
+	slotFields := []*types.Field{
+		makefield("key", t.Key()),
+		makefield("typ", t.Elem()),
 	}
+	slot := types.NewStruct(slotFields)
+	slot.SetNoalg(true)
 
-	field := make([]*types.Field, 0, 5)
-
-	// The first field is: uint8 topbits[BUCKETSIZE].
-	arr := types.NewArray(types.Types[types.TUINT8], abi.SwissMapBucketCount)
-	field = append(field, makefield("topbits", arr))
-
-	arr = types.NewArray(keytype, abi.SwissMapBucketCount)
-	arr.SetNoalg(true)
-	keys := makefield("keys", arr)
-	field = append(field, keys)
+	slotArr := types.NewArray(slot, abi.SwissMapGroupSlots)
+	slotArr.SetNoalg(true)
 
-	arr = types.NewArray(elemtype, abi.SwissMapBucketCount)
-	arr.SetNoalg(true)
-	elems := makefield("elems", arr)
-	field = append(field, elems)
-
-	// If keys and elems have no pointers, the map implementation
-	// can keep a list of overflow pointers on the side so that
-	// buckets can be marked as having no pointers.
-	// Arrange for the bucket to have no pointers by changing
-	// the type of the overflow field to uintptr in this case.
-	// See comment on hmap.overflow in runtime/map.go.
-	otyp := types.Types[types.TUNSAFEPTR]
-	if !elemtype.HasPointers() && !keytype.HasPointers() {
-		otyp = types.Types[types.TUINTPTR]
+	fields := []*types.Field{
+		makefield("ctrl", types.Types[types.TUINT64]),
+		makefield("slots", slotArr),
 	}
-	overflow := makefield("overflow", otyp)
-	field = append(field, overflow)
 
-	// link up fields
-	bucket := types.NewStruct(field[:])
-	bucket.SetNoalg(true)
-	types.CalcSize(bucket)
+	group := types.NewStruct(fields)
+	group.SetNoalg(true)
+	types.CalcSize(group)
 
 	// Check invariants that map code depends on.
 	if !types.IsComparable(t.Key()) {
 		base.Fatalf("unsupported map key type for %v", t)
 	}
-	if abi.SwissMapBucketCount < 8 {
-		base.Fatalf("bucket size %d too small for proper alignment %d", abi.SwissMapBucketCount, 8)
-	}
-	if uint8(keytype.Alignment()) > abi.SwissMapBucketCount {
-		base.Fatalf("key align too big for %v", t)
-	}
-	if uint8(elemtype.Alignment()) > abi.SwissMapBucketCount {
-		base.Fatalf("elem align %d too big for %v, BUCKETSIZE=%d", elemtype.Alignment(), t, abi.SwissMapBucketCount)
-	}
-	if keytype.Size() > abi.SwissMapMaxKeyBytes {
-		base.Fatalf("key size too large for %v", t)
-	}
-	if elemtype.Size() > abi.SwissMapMaxElemBytes {
-		base.Fatalf("elem size too large for %v", t)
-	}
-	if t.Key().Size() > abi.SwissMapMaxKeyBytes && !keytype.IsPtr() {
-		base.Fatalf("key indirect incorrect for %v", t)
-	}
-	if t.Elem().Size() > abi.SwissMapMaxElemBytes && !elemtype.IsPtr() {
-		base.Fatalf("elem indirect incorrect for %v", t)
-	}
-	if keytype.Size()%keytype.Alignment() != 0 {
-		base.Fatalf("key size not a multiple of key align for %v", t)
-	}
-	if elemtype.Size()%elemtype.Alignment() != 0 {
-		base.Fatalf("elem size not a multiple of elem align for %v", t)
-	}
-	if uint8(bucket.Alignment())%uint8(keytype.Alignment()) != 0 {
-		base.Fatalf("bucket align not multiple of key align %v", t)
-	}
-	if uint8(bucket.Alignment())%uint8(elemtype.Alignment()) != 0 {
-		base.Fatalf("bucket align not multiple of elem align %v", t)
+	if group.Size() <= 8 {
+		// internal/runtime/maps creates pointers to slots, even if
+		// both key and elem are size zero. In this case, each slot is
+		// size 0, but group should still reserve a word of padding at
+		// the end to ensure pointers are valid.
+		base.Fatalf("bad group size for %v", t)
 	}
-	if keys.Offset%keytype.Alignment() != 0 {
-		base.Fatalf("bad alignment of keys in bmap for %v", t)
-	}
-	if elems.Offset%elemtype.Alignment() != 0 {
-		base.Fatalf("bad alignment of elems in bmap for %v", t)
-	}
-
-	// Double-check that overflow field is final memory in struct,
-	// with no padding at end.
-	if overflow.Offset != bucket.Size()-int64(types.PtrSize) {
-		base.Fatalf("bad offset of overflow in bmap for %v, overflow.Offset=%d, bucket.Size()-int64(types.PtrSize)=%d",
-			t, overflow.Offset, bucket.Size()-int64(types.PtrSize))
-	}
-
-	t.MapType().SwissBucket = bucket
 
-	bucket.StructType().Map = t
-	return bucket
+	t.MapType().SwissGroup = group
+	group.StructType().Map = t
+	return group
 }
 
 var swissHmapType *types.Type
 
-// SwissMapType returns a type interchangeable with runtime.hmap.
-// Make sure this stays in sync with runtime/map.go.
+// SwissMapType returns a type interchangeable with internal/runtime/maps.Map.
+// Make sure this stays in sync with internal/runtime/maps/map.go.
 func SwissMapType() *types.Type {
 	if swissHmapType != nil {
 		return swissHmapType
 	}
 
 	// build a struct:
-	// type hmap struct {
-	//    count      int
-	//    flags      uint8
-	//    B          uint8
-	//    noverflow  uint16
-	//    hash0      uint32
-	//    buckets    unsafe.Pointer
-	//    oldbuckets unsafe.Pointer
-	//    nevacuate  uintptr
-	//    extra      unsafe.Pointer // *mapextra
+	// type table struct {
+	//     used uint64
+	//     typ  unsafe.Pointer // *abi.SwissMapType
+	//     seed uintptr
+	//
+	//     // From groups.
+	//     groups_typ        unsafe.Pointer // *abi.SwissMapType
+	//     groups_data       unsafe.Pointer
+	//     groups_lengthMask uint64
+	//
+	//     capacity   uint64
+	//     growthLeft uint64
+	//
+	//     clearSeq uint64
 	// }
-	// must match runtime/map.go:hmap.
+	// must match internal/runtime/maps/map.go:Map.
 	fields := []*types.Field{
-		makefield("count", types.Types[types.TINT]),
-		makefield("flags", types.Types[types.TUINT8]),
-		makefield("B", types.Types[types.TUINT8]),
-		makefield("noverflow", types.Types[types.TUINT16]),
-		makefield("hash0", types.Types[types.TUINT32]),      // Used in walk.go for OMAKEMAP.
-		makefield("buckets", types.Types[types.TUNSAFEPTR]), // Used in walk.go for OMAKEMAP.
-		makefield("oldbuckets", types.Types[types.TUNSAFEPTR]),
-		makefield("nevacuate", types.Types[types.TUINTPTR]),
-		makefield("extra", types.Types[types.TUNSAFEPTR]),
+		makefield("used", types.Types[types.TUINT64]),
+		makefield("typ", types.Types[types.TUNSAFEPTR]),
+		makefield("seed", types.Types[types.TUINTPTR]),
+		makefield("groups_typ", types.Types[types.TUNSAFEPTR]),
+		makefield("groups_data", types.Types[types.TUNSAFEPTR]),
+		makefield("groups_lengthMask", types.Types[types.TUINT64]),
+		makefield("capacity", types.Types[types.TUINT64]),
+		makefield("growthLeft", types.Types[types.TUINT64]),
+		makefield("clearSeq", types.Types[types.TUINT64]),
 	}
 
-	n := ir.NewDeclNameAt(src.NoXPos, ir.OTYPE, ir.Pkgs.Runtime.Lookup("hmap"))
+	n := ir.NewDeclNameAt(src.NoXPos, ir.OTYPE, ir.Pkgs.InternalMaps.Lookup("table"))
 	hmap := types.NewNamed(n)
 	n.SetType(hmap)
 	n.SetTypecheck(1)
@@ -178,10 +116,10 @@ func SwissMapType() *types.Type {
 	hmap.SetUnderlying(types.NewStruct(fields))
 	types.CalcSize(hmap)
 
-	// The size of hmap should be 48 bytes on 64 bit
-	// and 28 bytes on 32 bit platforms.
-	if size := int64(8 + 5*types.PtrSize); hmap.Size() != size {
-		base.Fatalf("hmap size not correct: got %d, want %d", hmap.Size(), size)
+	// The size of Map should be 64 bytes on 64 bit
+	// and 48 bytes on 32 bit platforms.
+	if size := int64(5*8 + 4*types.PtrSize); hmap.Size() != size {
+		base.Fatalf("internal/runtime/maps.Map size not correct: got %d, want %d", hmap.Size(), size)
 	}
 
 	swissHmapType = hmap
@@ -200,52 +138,54 @@ func SwissMapIterType() *types.Type {
 	hmap := SwissMapType()
 
 	// build a struct:
-	// type hiter struct {
-	//    key         unsafe.Pointer // *Key
-	//    elem        unsafe.Pointer // *Elem
-	//    t           unsafe.Pointer // *SwissMapType
-	//    h           *hmap
-	//    buckets     unsafe.Pointer
-	//    bptr        unsafe.Pointer // *bmap
-	//    overflow    unsafe.Pointer // *[]*bmap
-	//    oldoverflow unsafe.Pointer // *[]*bmap
-	//    startBucket uintptr
-	//    offset      uint8
-	//    wrapped     bool
-	//    B           uint8
-	//    i           uint8
-	//    bucket      uintptr
-	//    checkBucket uintptr
+	// type Iter struct {
+	//    key      unsafe.Pointer // *Key
+	//    elem     unsafe.Pointer // *Elem
+	//    typ      unsafe.Pointer // *SwissMapType
+	//    m        *Map
+	//
+	//    // From groups.
+	//    groups_typ        unsafe.Pointer // *abi.SwissMapType
+	//    groups_data       unsafe.Pointer
+	//    groups_lengthMask uint64
+	//
+	//    clearSeq uint64
+	//
+	//    offset   uint64
+	//    groupIdx uint64
+	//    slotIdx  uint32
+	//
+	//    // 4 bytes of padding on 64-bit arches.
 	// }
-	// must match runtime/map.go:hiter.
+	// must match internal/runtime/maps/table.go:Iter.
 	fields := []*types.Field{
 		makefield("key", types.Types[types.TUNSAFEPTR]),  // Used in range.go for TMAP.
 		makefield("elem", types.Types[types.TUNSAFEPTR]), // Used in range.go for TMAP.
-		makefield("t", types.Types[types.TUNSAFEPTR]),
-		makefield("h", types.NewPtr(hmap)),
-		makefield("buckets", types.Types[types.TUNSAFEPTR]),
-		makefield("bptr", types.Types[types.TUNSAFEPTR]),
-		makefield("overflow", types.Types[types.TUNSAFEPTR]),
-		makefield("oldoverflow", types.Types[types.TUNSAFEPTR]),
-		makefield("startBucket", types.Types[types.TUINTPTR]),
-		makefield("offset", types.Types[types.TUINT8]),
-		makefield("wrapped", types.Types[types.TBOOL]),
-		makefield("B", types.Types[types.TUINT8]),
-		makefield("i", types.Types[types.TUINT8]),
-		makefield("bucket", types.Types[types.TUINTPTR]),
-		makefield("checkBucket", types.Types[types.TUINTPTR]),
+		makefield("typ", types.Types[types.TUNSAFEPTR]),
+		makefield("m", types.NewPtr(hmap)),
+		makefield("groups_typ", types.Types[types.TUNSAFEPTR]),
+		makefield("groups_data", types.Types[types.TUNSAFEPTR]),
+		makefield("groups_lengthMask", types.Types[types.TUINT64]),
+		makefield("clearSeq", types.Types[types.TUINT64]),
+		makefield("offset", types.Types[types.TUINT64]),
+		makefield("groupIdx", types.Types[types.TUINT64]),
+		makefield("slotIdx", types.Types[types.TUINT32]),
 	}
 
 	// build iterator struct hswissing the above fields
-	n := ir.NewDeclNameAt(src.NoXPos, ir.OTYPE, ir.Pkgs.Runtime.Lookup("hiter"))
+	n := ir.NewDeclNameAt(src.NoXPos, ir.OTYPE, ir.Pkgs.InternalMaps.Lookup("Iter"))
 	hiter := types.NewNamed(n)
 	n.SetType(hiter)
 	n.SetTypecheck(1)
 
 	hiter.SetUnderlying(types.NewStruct(fields))
 	types.CalcSize(hiter)
-	if hiter.Size() != int64(12*types.PtrSize) {
-		base.Fatalf("hash_iter size not correct %d %d", hiter.Size(), 12*types.PtrSize)
+	want := 6*types.PtrSize + 4*8 + 1*4
+	if types.PtrSize == 8 {
+		want += 4 // tailing padding
+	}
+	if hiter.Size() != int64(want) {
+		base.Fatalf("hash_iter size not correct %d %d", hiter.Size(), want)
 	}
 
 	swissHiterType = hiter
@@ -254,40 +194,27 @@ func SwissMapIterType() *types.Type {
 
 func writeSwissMapType(t *types.Type, lsym *obj.LSym, c rttype.Cursor) {
 	// internal/abi.SwissMapType
+	gtyp := SwissMapGroupType(t)
 	s1 := writeType(t.Key())
 	s2 := writeType(t.Elem())
-	s3 := writeType(SwissMapBucketType(t))
+	s3 := writeType(gtyp)
 	hasher := genhash(t.Key())
 
+	slotTyp := gtyp.Field(1).Type.Elem()
+	elemOff := slotTyp.Field(1).Offset
+
 	c.Field("Key").WritePtr(s1)
 	c.Field("Elem").WritePtr(s2)
-	c.Field("Bucket").WritePtr(s3)
+	c.Field("Group").WritePtr(s3)
 	c.Field("Hasher").WritePtr(hasher)
+	c.Field("SlotSize").WriteUintptr(uint64(slotTyp.Size()))
+	c.Field("ElemOff").WriteUintptr(uint64(elemOff))
 	var flags uint32
-	// Note: flags must match maptype accessors in ../../../../runtime/type.go
-	// and maptype builder in ../../../../reflect/type.go:MapOf.
-	if t.Key().Size() > abi.SwissMapMaxKeyBytes {
-		c.Field("KeySize").WriteUint8(uint8(types.PtrSize))
-		flags |= 1 // indirect key
-	} else {
-		c.Field("KeySize").WriteUint8(uint8(t.Key().Size()))
-	}
-
-	if t.Elem().Size() > abi.SwissMapMaxElemBytes {
-		c.Field("ValueSize").WriteUint8(uint8(types.PtrSize))
-		flags |= 2 // indirect value
-	} else {
-		c.Field("ValueSize").WriteUint8(uint8(t.Elem().Size()))
-	}
-	c.Field("BucketSize").WriteUint16(uint16(SwissMapBucketType(t).Size()))
-	if types.IsReflexive(t.Key()) {
-		flags |= 4 // reflexive key
-	}
 	if needkeyupdate(t.Key()) {
-		flags |= 8 // need key update
+		flags |= abi.SwissMapNeedKeyUpdate
 	}
 	if hashMightPanic(t.Key()) {
-		flags |= 16 // hash might panic
+		flags |= abi.SwissMapHashMightPanic
 	}
 	c.Field("Flags").WriteUint32(flags)