internal/abi,runtime: refactor map constants into one place

Previously TryBot-tested with bucket bits = 4.
Also tested locally with bucket bits = 5.
This makes it much easier to change the size of map
buckets, and hopefully provides pointers to all the
code that in some way depends on details of map layout.

Change-Id: I9f6669d1eadd02f182d0bc3f959dc5f385fa1683
Reviewed-on: https://go-review.googlesource.com/c/go/+/462115
TryBot-Result: Gopher Robot <gobot@golang.org>
Run-TryBot: David Chase <drchase@google.com>
Reviewed-by: Austin Clements <austin@google.com>

4 files changed, 44 insertions, 16 deletions

diff --git a/src/runtime/map.go b/src/runtime/map.go
index f546ce8609..6179c1e371 100644
--- a/src/runtime/map.go
+++ b/src/runtime/map.go
@@ -63,20 +63,21 @@ import (
 
 const (
 	// Maximum number of key/elem pairs a bucket can hold.
-	bucketCntBits = 3
-	bucketCnt     = 1 << bucketCntBits
+	bucketCntBits = abi.MapBucketCountBits
+	bucketCnt     = abi.MapBucketCount
 
-	// Maximum average load of a bucket that triggers growth is 6.5.
+	// Maximum average load of a bucket that triggers growth is bucketCnt*13/16 (about 80% full)
+	// Because of minimum alignment rules, bucketCnt is known to be at least 8.
 	// Represent as loadFactorNum/loadFactorDen, to allow integer math.
-	loadFactorNum = 13
 	loadFactorDen = 2
+	loadFactorNum = (bucketCnt * 13 / 16) * loadFactorDen
 
 	// Maximum key or elem size to keep inline (instead of mallocing per element).
 	// Must fit in a uint8.
 	// Fast versions cannot handle big elems - the cutoff size for
 	// fast versions in cmd/compile/internal/gc/walk.go must be at most this elem.
-	maxKeySize  = 128
-	maxElemSize = 128
+	maxKeySize  = abi.MapMaxKeyBytes
+	maxElemSize = abi.MapMaxElemBytes
 
 	// data offset should be the size of the bmap struct, but needs to be
 	// aligned correctly. For amd64p32 this means 64-bit alignment
diff --git a/src/runtime/map_test.go b/src/runtime/map_test.go
index 4afbae6bc4..3675106d9c 100644
--- a/src/runtime/map_test.go
+++ b/src/runtime/map_test.go
@@ -6,6 +6,7 @@ package runtime_test
 
 import (
 	"fmt"
+	"internal/abi"
 	"internal/goarch"
 	"math"
 	"reflect"
@@ -506,7 +507,12 @@ func TestMapNanGrowIterator(t *testing.T) {
 }
 
 func TestMapIterOrder(t *testing.T) {
-	for _, n := range [...]int{3, 7, 9, 15} {
+	sizes := []int{3, 7, 9, 15}
+	if abi.MapBucketCountBits >= 5 {
+		// it gets flaky (often only one iteration order) at size 3 when abi.MapBucketCountBits >=5.
+		t.Fatalf("This test becomes flaky if abi.MapBucketCountBits(=%d) is 5 or larger", abi.MapBucketCountBits)
+	}
+	for _, n := range sizes {
 		for i := 0; i < 1000; i++ {
 			// Make m be {0: true, 1: true, ..., n-1: true}.
 			m := make(map[int]bool)
@@ -673,6 +679,17 @@ func TestIgnoreBogusMapHint(t *testing.T) {
 	}
 }
 
+const bs = abi.MapBucketCount
+
+// belowOverflow should be a pretty-full pair of buckets;
+// atOverflow is 1/8 bs larger = 13/8 buckets or two buckets
+// that are 13/16 full each, which is the overflow boundary.
+// Adding one to that should ensure overflow to the next higher size.
+const (
+	belowOverflow = bs * 3 / 2           // 1.5 bs = 2 buckets @ 75%
+	atOverflow    = belowOverflow + bs/8 // 2 buckets at 13/16 fill.
+)
+
 var mapBucketTests = [...]struct {
 	n        int // n is the number of map elements
 	noescape int // number of expected buckets for non-escaping map
@@ -682,11 +699,16 @@ var mapBucketTests = [...]struct {
 	{-1, 1, 1},
 	{0, 1, 1},
 	{1, 1, 1},
-	{8, 1, 1},
-	{9, 2, 2},
-	{13, 2, 2},
-	{14, 4, 4},
-	{26, 4, 4},
+	{bs, 1, 1},
+	{bs + 1, 2, 2},
+	{belowOverflow, 2, 2},  // 1.5 bs = 2 buckets @ 75%
+	{atOverflow + 1, 4, 4}, // 13/8 bs + 1 == overflow to 4
+
+	{2 * belowOverflow, 4, 4}, // 3 bs = 4 buckets @75%
+	{2*atOverflow + 1, 8, 8},  // 13/4 bs + 1 = overflow to 8
+
+	{4 * belowOverflow, 8, 8},  // 6 bs = 8 buckets @ 75%
+	{4*atOverflow + 1, 16, 16}, // 13/2 bs + 1 = overflow to 16
 }
 
 func TestMapBuckets(t *testing.T) {
diff --git a/src/runtime/runtime-gdb.py b/src/runtime/runtime-gdb.py
index c4462de851..62859a5659 100644
--- a/src/runtime/runtime-gdb.py
+++ b/src/runtime/runtime-gdb.py
@@ -160,6 +160,7 @@ class MapTypePrinter:
 		return str(self.val.type)
 
 	def children(self):
+		MapBucketCount = 8 # see internal/abi.go:MapBucketCount
 		B = self.val['B']
 		buckets = self.val['buckets']
 		oldbuckets = self.val['oldbuckets']
@@ -178,7 +179,7 @@ class MapTypePrinter:
 					bp = oldbp
 			while bp:
 				b = bp.dereference()
-				for i in xrange(8):
+				for i in xrange(MapBucketCount):
 					if b['tophash'][i] != 0:
 						k = b['keys'][i]
 						v = b['values'][i]
diff --git a/src/runtime/runtime-gdb_test.go b/src/runtime/runtime-gdb_test.go
index 4e7c22762a..a45654d085 100644
--- a/src/runtime/runtime-gdb_test.go
+++ b/src/runtime/runtime-gdb_test.go
@@ -8,6 +8,7 @@ import (
 	"bytes"
 	"flag"
 	"fmt"
+	"internal/abi"
 	"internal/testenv"
 	"os"
 	"os/exec"
@@ -114,13 +115,16 @@ func checkCleanBacktrace(t *testing.T, backtrace string) {
 	// TODO(mundaym): check for unknown frames (e.g. "??").
 }
 
-const helloSource = `
+// NOTE: the maps below are allocated larger than abi.MapBucketCount
+// to ensure that they are not "optimized out".
+
+var helloSource = `
 import "fmt"
 import "runtime"
 var gslice []string
 func main() {
-	mapvar := make(map[string]string, 13)
-	slicemap := make(map[string][]string,11)
+	mapvar := make(map[string]string, ` + strconv.FormatInt(abi.MapBucketCount+9, 10) + `)
+	slicemap := make(map[string][]string,` + strconv.FormatInt(abi.MapBucketCount+3, 10) + `)
     chanint := make(chan int, 10)
     chanstr := make(chan string, 10)
     chanint <- 99