internal/runtime/maps: small maps point directly to a group

If the map contains 8 or fewer entries, it is wasteful to have a
directory that points to a table that points to a group.

Add a special case that replaces the directory with a direct pointer to
a group.

We could theoretically do similar for single table maps (no directory,
just point directly to a table), but that is left for later.

For #54766.

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

3 files changed, 90 insertions, 15 deletions

diff --git a/src/runtime/map_swiss_test.go b/src/runtime/map_swiss_test.go
index 93b1fd430f..536e5eec32 100644
--- a/src/runtime/map_swiss_test.go
+++ b/src/runtime/map_swiss_test.go
@@ -18,8 +18,8 @@ import (
 func TestHmapSize(t *testing.T) {
 	// The structure of Map is defined in internal/runtime/maps/map.go
 	// and in cmd/compile/internal/reflectdata/map_swiss.go and must be in sync.
-	// The size of Map should be 64 bytes on 64 bit and 40 bytes on 32 bit platforms.
-	wantSize := uintptr(6*goarch.PtrSize + 2*8)
+	// The size of Map should be 56 bytes on 64 bit and 36 bytes on 32 bit platforms.
+	wantSize := uintptr(2*8 + 5*goarch.PtrSize)
 	gotSize := unsafe.Sizeof(maps.Map{})
 	if gotSize != wantSize {
 		t.Errorf("sizeof(maps.Map{})==%d, want %d", gotSize, wantSize)
diff --git a/src/runtime/runtime-gdb.py b/src/runtime/runtime-gdb.py
index b0c96e594f..6d99515176 100644
--- a/src/runtime/runtime-gdb.py
+++ b/src/runtime/runtime-gdb.py
@@ -170,9 +170,81 @@ class MapTypePrinter:
 		SwissMapGroupSlots = 8 # see internal/abi:SwissMapGroupSlots
 
 		cnt = 0
-		directory = SliceValue(self.val['directory'])
-		for table in directory:
+		# Yield keys and elements in group.
+		# group is a value of type *group[K,V]
+		def group_slots(group):
+			ctrl = group['ctrl']
+
+			for i in xrange(SwissMapGroupSlots):
+				c = (ctrl >> (8*i)) & 0xff
+				if (c & 0x80) != 0:
+					# Empty or deleted
+					continue
+
+				# Full
+				yield str(cnt), group['slots'][i]['key']
+				yield str(cnt+1), group['slots'][i]['elem']
+
+		# The linker DWARF generation
+		# (cmd/link/internal/ld.(*dwctxt).synthesizemaptypesSwiss) records
+		# dirPtr as a **table[K,V], but it may actually be two different types:
+		#
+		# For "full size" maps (dirLen > 0), dirPtr is actually a pointer to
+		# variable length array *[dirLen]*table[K,V]. In other words, dirPtr +
+		# dirLen are a deconstructed slice []*table[K,V].
+		#
+		# For "small" maps (dirLen <= 0), dirPtr is a pointer directly to a
+		# single group *group[K,V] containing the map slots.
+		#
+		# N.B. array() takes an _inclusive_ upper bound.
+
+		# table[K,V]
+		table_type = self.val['dirPtr'].type.target().target()
+
+		if self.val['dirLen'] <= 0:
+			# Small map
+
+			# We need to find the group type we'll cast to. Since dirPtr isn't
+			# actually **table[K,V], we can't use the nice API of
+			# obj['field'].type, as that actually wants to dereference obj.
+			# Instead, search only via the type API.
+			ptr_group_type = None
+			for tf in table_type.fields():
+				if tf.name != 'groups':
+					continue
+				groups_type = tf.type
+				for gf in groups_type.fields():
+					if gf.name != 'data':
+						continue
+					# *group[K,V]
+					ptr_group_type = gf.type
+
+			if ptr_group_type is None:
+				raise TypeError("unable to find table[K,V].groups.data")
+
+			# group = (*group[K,V])(dirPtr)
+			group = self.val['dirPtr'].cast(ptr_group_type)
+
+			yield from group_slots(group)
+
+			return
+
+		# Full size map.
+
+		# *table[K,V]
+		ptr_table_type = table_type.pointer()
+		# [dirLen]*table[K,V]
+		array_ptr_table_type = ptr_table_type.array(self.val['dirLen']-1)
+		# *[dirLen]*table[K,V]
+		ptr_array_ptr_table_type = array_ptr_table_type.pointer()
+		# tables = (*[dirLen]*table[K,V])(dirPtr)
+		tables = self.val['dirPtr'].cast(ptr_array_ptr_table_type)
+
+		cnt = 0
+		for t in xrange(self.val['dirLen']):
+			table = tables[t]
 			table = table.dereference()
+
 			groups = table['groups']['data']
 			length = table['groups']['lengthMask'] + 1
 
@@ -195,17 +267,7 @@ class MapTypePrinter:
 
 			for i in xrange(length):
 				group = groups[i]
-				ctrl = group['ctrl']
-
-				for i in xrange(SwissMapGroupSlots):
-					c = (ctrl >> (8*i)) & 0xff
-					if (c & 0x80) != 0:
-						# Empty or deleted
-						continue
-
-					# Full
-					yield str(cnt), group['slots'][i]['key']
-					yield str(cnt+1), group['slots'][i]['elem']
+				yield from group_slots(group)
 
 
 	def old_map_children(self):
diff --git a/src/runtime/runtime-gdb_test.go b/src/runtime/runtime-gdb_test.go
index ec878bb045..9c54d68949 100644
--- a/src/runtime/runtime-gdb_test.go
+++ b/src/runtime/runtime-gdb_test.go
@@ -157,7 +157,10 @@ var helloSource = `
 import "fmt"
 import "runtime"
 var gslice []string
+// TODO(prattmic): Stack allocated maps initialized inline appear "optimized out" in GDB.
+var smallmapvar map[string]string
 func main() {
+	smallmapvar = make(map[string]string)
 	mapvar := make(map[string]string, ` + strconv.FormatInt(abi.OldMapBucketCount+9, 10) + `)
 	slicemap := make(map[string][]string,` + strconv.FormatInt(abi.OldMapBucketCount+3, 10) + `)
     chanint := make(chan int, 10)
@@ -166,6 +169,7 @@ func main() {
 	chanint <- 11
     chanstr <- "spongepants"
     chanstr <- "squarebob"
+	smallmapvar["abc"] = "def"
 	mapvar["abc"] = "def"
 	mapvar["ghi"] = "jkl"
 	slicemap["a"] = []string{"b","c","d"}
@@ -179,6 +183,7 @@ func main() {
 	_ = ptrvar // set breakpoint here
 	gslice = slicevar
 	fmt.Printf("%v, %v, %v\n", slicemap, <-chanint, <-chanstr)
+	runtime.KeepAlive(smallmapvar)
 	runtime.KeepAlive(mapvar)
 }  // END_OF_PROGRAM
 `
@@ -294,6 +299,9 @@ func testGdbPython(t *testing.T, cgo bool) {
 		"-ex", "echo BEGIN info goroutines\n",
 		"-ex", "info goroutines",
 		"-ex", "echo END\n",
+		"-ex", "echo BEGIN print smallmapvar\n",
+		"-ex", "print smallmapvar",
+		"-ex", "echo END\n",
 		"-ex", "echo BEGIN print mapvar\n",
 		"-ex", "print mapvar",
 		"-ex", "echo END\n",
@@ -346,6 +354,11 @@ func testGdbPython(t *testing.T, cgo bool) {
 		t.Fatalf("info goroutines failed: %s", bl)
 	}
 
+	printSmallMapvarRe := regexp.MustCompile(`^\$[0-9]+ = map\[string\]string = {\[(0x[0-9a-f]+\s+)?"abc"\] = (0x[0-9a-f]+\s+)?"def"}$`)
+	if bl := blocks["print smallmapvar"]; !printSmallMapvarRe.MatchString(bl) {
+		t.Fatalf("print smallmapvar failed: %s", bl)
+	}
+
 	printMapvarRe1 := regexp.MustCompile(`^\$[0-9]+ = map\[string\]string = {\[(0x[0-9a-f]+\s+)?"abc"\] = (0x[0-9a-f]+\s+)?"def", \[(0x[0-9a-f]+\s+)?"ghi"\] = (0x[0-9a-f]+\s+)?"jkl"}$`)
 	printMapvarRe2 := regexp.MustCompile(`^\$[0-9]+ = map\[string\]string = {\[(0x[0-9a-f]+\s+)?"ghi"\] = (0x[0-9a-f]+\s+)?"jkl", \[(0x[0-9a-f]+\s+)?"abc"\] = (0x[0-9a-f]+\s+)?"def"}$`)
 	if bl := blocks["print mapvar"]; !printMapvarRe1.MatchString(bl) &&