internal/runtime/maps: proper capacity hint handling

When given a hint size, set the initial capacity large enough to avoid
requiring growth in the average case.

When not given a hint (or given 0), don't allocate anything at all.

For #54766.

Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap
Change-Id: I8844fc652b8d2d4e5136cd56f7e78999a07fe381
Reviewed-on: https://go-review.googlesource.com/c/go/+/616457
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Keith Randall <khr@google.com>
Auto-Submit: Michael Pratt <mpratt@google.com>

4 files changed, 30 insertions, 70 deletions

diff --git a/src/runtime/alg.go b/src/runtime/alg.go
index 14ac7e8df3..07c115f74d 100644
--- a/src/runtime/alg.go
+++ b/src/runtime/alg.go
@@ -256,11 +256,6 @@ func mapKeyError(t *maptype, p unsafe.Pointer) error {
 	return mapKeyError2(t.Key, p)
 }
 
-//go:linkname maps_mapKeyError internal/runtime/maps.mapKeyError
-func maps_mapKeyError(t *maptype, p unsafe.Pointer) error {
-	return mapKeyError(t, p)
-}
-
 func mapKeyError2(t *_type, p unsafe.Pointer) error {
 	if t.TFlag&abi.TFlagRegularMemory != 0 {
 		return nil
diff --git a/src/runtime/crash_test.go b/src/runtime/crash_test.go
index 52d33b8f58..268ddb59c9 100644
--- a/src/runtime/crash_test.go
+++ b/src/runtime/crash_test.go
@@ -622,7 +622,10 @@ func TestConcurrentMapWrites(t *testing.T) {
 	testenv.MustHaveGoRun(t)
 	output := runTestProg(t, "testprog", "concurrentMapWrites")
 	want := "fatal error: concurrent map writes\n"
-	if !strings.HasPrefix(output, want) {
+	// Concurrent writes can corrupt the map in a way that we
+	// detect with a separate throw.
+	want2 := "fatal error: small map with no empty slot (concurrent map writes?)\n"
+	if !strings.HasPrefix(output, want) && !strings.HasPrefix(output, want2) {
 		t.Fatalf("output does not start with %q:\n%s", want, output)
 	}
 }
@@ -633,7 +636,10 @@ func TestConcurrentMapReadWrite(t *testing.T) {
 	testenv.MustHaveGoRun(t)
 	output := runTestProg(t, "testprog", "concurrentMapReadWrite")
 	want := "fatal error: concurrent map read and map write\n"
-	if !strings.HasPrefix(output, want) {
+	// Concurrent writes can corrupt the map in a way that we
+	// detect with a separate throw.
+	want2 := "fatal error: small map with no empty slot (concurrent map writes?)\n"
+	if !strings.HasPrefix(output, want) && !strings.HasPrefix(output, want2) {
 		t.Fatalf("output does not start with %q:\n%s", want, output)
 	}
 }
@@ -644,7 +650,10 @@ func TestConcurrentMapIterateWrite(t *testing.T) {
 	testenv.MustHaveGoRun(t)
 	output := runTestProg(t, "testprog", "concurrentMapIterateWrite")
 	want := "fatal error: concurrent map iteration and map write\n"
-	if !strings.HasPrefix(output, want) {
+	// Concurrent writes can corrupt the map in a way that we
+	// detect with a separate throw.
+	want2 := "fatal error: small map with no empty slot (concurrent map writes?)\n"
+	if !strings.HasPrefix(output, want) && !strings.HasPrefix(output, want2) {
 		t.Fatalf("output does not start with %q:\n%s", want, output)
 	}
 }
@@ -667,7 +676,10 @@ func TestConcurrentMapWritesIssue69447(t *testing.T) {
 			continue
 		}
 		want := "fatal error: concurrent map writes\n"
-		if !strings.HasPrefix(output, want) {
+		// Concurrent writes can corrupt the map in a way that we
+		// detect with a separate throw.
+		want2 := "fatal error: small map with no empty slot (concurrent map writes?)\n"
+		if !strings.HasPrefix(output, want) && !strings.HasPrefix(output, want2) {
 			t.Fatalf("output does not start with %q:\n%s", want, output)
 		}
 	}
diff --git a/src/runtime/map_swiss.go b/src/runtime/map_swiss.go
index 9556690a06..42b964da24 100644
--- a/src/runtime/map_swiss.go
+++ b/src/runtime/map_swiss.go
@@ -9,7 +9,6 @@ package runtime
 import (
 	"internal/abi"
 	"internal/runtime/maps"
-	"internal/runtime/math"
 	"internal/runtime/sys"
 	"unsafe"
 )
@@ -25,6 +24,11 @@ type maptype = abi.SwissMapType
 //go:linkname maps_errNilAssign internal/runtime/maps.errNilAssign
 var maps_errNilAssign error = plainError("assignment to entry in nil map")
 
+//go:linkname maps_mapKeyError internal/runtime/maps.mapKeyError
+func maps_mapKeyError(t *abi.SwissMapType, p unsafe.Pointer) error {
+	return mapKeyError(t, p)
+}
+
 func makemap64(t *abi.SwissMapType, hint int64, m *maps.Map) *maps.Map {
 	if int64(int(hint)) != hint {
 		hint = 0
@@ -39,63 +43,18 @@ func makemap_small() *maps.Map {
 	panic("unimplemented")
 }
 
-// checkHint verifies that hint is reasonable, adjusting as necessary.
-func checkHint(t *abi.SwissMapType, hint int) uint64 {
-	if hint <= 0 {
-		return 0
-	}
-
-	capacity := uint64(hint)
-
-	// Ensure a groups allocation for a capacity this high doesn't exceed
-	// the maximum allocation size.
-	//
-	// TODO(prattmic): Once we split tables, a large hint will result in
-	// splitting the tables up front, which will use smaller individual
-	// allocations.
-	//
-	// TODO(prattmic): This logic is largely duplicated from maps.newTable
-	// / maps.(*table).reset.
-	capacity, overflow := alignUpPow2(capacity)
-	if !overflow {
-		groupCount := capacity / abi.SwissMapGroupSlots
-		mem, overflow := math.MulUintptr(uintptr(groupCount), t.Group.Size_)
-		if overflow || mem > maxAlloc {
-			return 0
-		}
-	} else {
-		return 0
-	}
-
-	return capacity
-}
-
 // makemap implements Go map creation for make(map[k]v, hint).
 // If the compiler has determined that the map or the first bucket
 // can be created on the stack, h and/or bucket may be non-nil.
 // If h != nil, the map can be created directly in h.
 // If h.buckets != nil, bucket pointed to can be used as the first bucket.
 func makemap(t *abi.SwissMapType, hint int, m *maps.Map) *maps.Map {
-	capacity := checkHint(t, hint)
+	if hint < 0 {
+		hint = 0
+	}
 
 	// TODO: use existing m
-	return maps.NewMap(t, capacity)
-}
-
-// alignUpPow2 rounds n up to the next power of 2.
-//
-// Returns true if round up causes overflow.
-//
-// TODO(prattmic): deduplicate from internal/runtime/maps.
-func alignUpPow2(n uint64) (uint64, bool) {
-	if n == 0 {
-		return 0, false
-	}
-	v := (uint64(1) << sys.Len64(n-1))
-	if v == 0 {
-		return 0, true
-	}
-	return v, false
+	return maps.NewMap(t, uintptr(hint), maxAlloc)
 }
 
 // mapaccess1 returns a pointer to h[key].  Never returns nil, instead
@@ -176,13 +135,6 @@ func mapdelete(t *abi.SwissMapType, m *maps.Map, key unsafe.Pointer) {
 		asanread(key, t.Key.Size_)
 	}
 
-	if m == nil || m.Used() == 0 {
-		if err := mapKeyError(t, key); err != nil {
-			panic(err) // see issue 23734
-		}
-		return
-	}
-
 	m.Delete(t, key)
 }
 
@@ -219,10 +171,6 @@ func mapclear(t *abi.SwissMapType, m *maps.Map) {
 		racewritepc(unsafe.Pointer(m), callerpc, pc)
 	}
 
-	if m == nil || m.Used() == 0 {
-		return
-	}
-
 	m.Clear(t)
 }
 
diff --git a/src/runtime/panic.go b/src/runtime/panic.go
index f97f1c6a66..e66f5ae942 100644
--- a/src/runtime/panic.go
+++ b/src/runtime/panic.go
@@ -1043,6 +1043,11 @@ func fips_fatal(s string) {
 	fatal(s)
 }
 
+//go:linkname maps_fatal internal/runtime/maps.fatal
+func maps_fatal(s string) {
+	fatal(s)
+}
+
 // throw triggers a fatal error that dumps a stack trace and exits.
 //
 // throw should be used for runtime-internal fatal errors where Go itself,