cmd/gc, runtime: treat slices and strings like pointers in garbage collection

Before, a slice with cap=0 or a string with len=0 might have its
base pointer pointing beyond the actual slice/string data into
the next block. The collector had to ignore slices and strings with
cap=0 in order to avoid misinterpreting the base pointer.

Now, a slice with cap=0 or a string with len=0 still has a base
pointer pointing into the actual slice/string data, no matter what.
The collector can now always scan the pointer, which means
strings and slices are no longer special.

Fixes #8404.

LGTM=khr, josharian
R=josharian, khr, dvyukov
CC=golang-codereviews
https://golang.org/cl/112570044

7 files changed, 58 insertions, 99 deletions

diff --git a/src/pkg/runtime/gcinfo_test.go b/src/pkg/runtime/gcinfo_test.go
index 16764c9487..88f6703f97 100644
--- a/src/pkg/runtime/gcinfo_test.go
+++ b/src/pkg/runtime/gcinfo_test.go
@@ -14,7 +14,7 @@ import (
 func TestGCInfo(t *testing.T) {
 	verifyGCInfo(t, "bss ScalarPtr", &bssScalarPtr, nonStackInfo(infoScalarPtr))
 	verifyGCInfo(t, "bss PtrScalar", &bssPtrScalar, nonStackInfo(infoPtrScalar))
-	verifyGCInfo(t, "bss Complex", &bssComplex, nonStackInfo(infoComplex()))
+	verifyGCInfo(t, "bss BigStruct", &bssBigStruct, nonStackInfo(infoBigStruct()))
 	verifyGCInfo(t, "bss string", &bssString, nonStackInfo(infoString))
 	verifyGCInfo(t, "bss slice", &bssSlice, nonStackInfo(infoSlice))
 	verifyGCInfo(t, "bss eface", &bssEface, nonStackInfo(infoEface))
@@ -22,7 +22,7 @@ func TestGCInfo(t *testing.T) {
 
 	verifyGCInfo(t, "data ScalarPtr", &dataScalarPtr, nonStackInfo(infoScalarPtr))
 	verifyGCInfo(t, "data PtrScalar", &dataPtrScalar, nonStackInfo(infoPtrScalar))
-	verifyGCInfo(t, "data Complex", &dataComplex, nonStackInfo(infoComplex()))
+	verifyGCInfo(t, "data BigStruct", &dataBigStruct, nonStackInfo(infoBigStruct()))
 	verifyGCInfo(t, "data string", &dataString, nonStackInfo(infoString))
 	verifyGCInfo(t, "data slice", &dataSlice, nonStackInfo(infoSlice))
 	verifyGCInfo(t, "data eface", &dataEface, nonStackInfo(infoEface))
@@ -30,7 +30,7 @@ func TestGCInfo(t *testing.T) {
 
 	verifyGCInfo(t, "stack ScalarPtr", new(ScalarPtr), infoScalarPtr)
 	verifyGCInfo(t, "stack PtrScalar", new(PtrScalar), infoPtrScalar)
-	verifyGCInfo(t, "stack Complex", new(Complex), infoComplex())
+	verifyGCInfo(t, "stack BigStruct", new(BigStruct), infoBigStruct())
 	verifyGCInfo(t, "stack string", new(string), infoString)
 	verifyGCInfo(t, "stack slice", new([]string), infoSlice)
 	verifyGCInfo(t, "stack eface", new(interface{}), infoEface)
@@ -39,7 +39,7 @@ func TestGCInfo(t *testing.T) {
 	for i := 0; i < 10; i++ {
 		verifyGCInfo(t, "heap ScalarPtr", escape(new(ScalarPtr)), nonStackInfo(infoScalarPtr))
 		verifyGCInfo(t, "heap PtrScalar", escape(new(PtrScalar)), nonStackInfo(infoPtrScalar))
-		verifyGCInfo(t, "heap Complex", escape(new(Complex)), nonStackInfo(infoComplex()))
+		verifyGCInfo(t, "heap BigStruct", escape(new(BigStruct)), nonStackInfo(infoBigStruct()))
 		verifyGCInfo(t, "heap string", escape(new(string)), nonStackInfo(infoString))
 		verifyGCInfo(t, "heap eface", escape(new(interface{})), nonStackInfo(infoEface))
 		verifyGCInfo(t, "heap iface", escape(new(Iface)), nonStackInfo(infoIface))
@@ -88,8 +88,8 @@ const (
 )
 
 const (
-	BitsString = iota
-	BitsSlice
+	BitsString = iota // unused
+	BitsSlice         // unused
 	BitsIface
 	BitsEface
 )
@@ -116,7 +116,7 @@ type PtrScalar struct {
 
 var infoPtrScalar = []byte{BitsPointer, BitsScalar, BitsPointer, BitsScalar, BitsPointer, BitsScalar}
 
-type Complex struct {
+type BigStruct struct {
 	q *int
 	w byte
 	e [17]byte
@@ -127,27 +127,31 @@ type Complex struct {
 	i string
 }
 
-func infoComplex() []byte {
+func infoBigStruct() []byte {
 	switch runtime.GOARCH {
 	case "386", "arm":
 		return []byte{
-			BitsPointer, BitsScalar, BitsScalar, BitsScalar,
-			BitsScalar, BitsScalar, BitsMultiWord, BitsSlice,
-			BitsDead, BitsScalar, BitsScalar, BitsScalar,
-			BitsScalar, BitsMultiWord, BitsString,
+			BitsPointer,                                                // q *int
+			BitsScalar, BitsScalar, BitsScalar, BitsScalar, BitsScalar, // w byte; e [17]byte
+			BitsPointer, BitsDead, BitsDead, // r []byte
+			BitsScalar, BitsScalar, BitsScalar, BitsScalar, // t int; y uint16; u uint64
+			BitsPointer, BitsDead, // i string
 		}
 	case "amd64":
 		return []byte{
-			BitsPointer, BitsScalar, BitsScalar, BitsScalar,
-			BitsMultiWord, BitsSlice, BitsDead, BitsScalar,
-			BitsScalar, BitsScalar, BitsMultiWord, BitsString,
+			BitsPointer,                        // q *int
+			BitsScalar, BitsScalar, BitsScalar, // w byte; e [17]byte
+			BitsPointer, BitsDead, BitsDead, // r []byte
+			BitsScalar, BitsScalar, BitsScalar, // t int; y uint16; u uint64
+			BitsPointer, BitsDead, // i string
 		}
 	case "amd64p32":
 		return []byte{
-			BitsPointer, BitsScalar, BitsScalar, BitsScalar,
-			BitsScalar, BitsScalar, BitsMultiWord, BitsSlice,
-			BitsDead, BitsScalar, BitsScalar, BitsDead,
-			BitsScalar, BitsScalar, BitsMultiWord, BitsString,
+			BitsPointer,                                                // q *int
+			BitsScalar, BitsScalar, BitsScalar, BitsScalar, BitsScalar, // w byte; e [17]byte
+			BitsPointer, BitsDead, BitsDead, // r []byte
+			BitsScalar, BitsScalar, BitsDead, BitsScalar, BitsScalar, // t int; y uint16; u uint64
+			BitsPointer, BitsDead, // i string
 		}
 	default:
 		panic("unknown arch")
@@ -167,7 +171,7 @@ var (
 	// BSS
 	bssScalarPtr ScalarPtr
 	bssPtrScalar PtrScalar
-	bssComplex   Complex
+	bssBigStruct BigStruct
 	bssString    string
 	bssSlice     []string
 	bssEface     interface{}
@@ -176,14 +180,14 @@ var (
 	// DATA
 	dataScalarPtr             = ScalarPtr{q: 1}
 	dataPtrScalar             = PtrScalar{w: 1}
-	dataComplex               = Complex{w: 1}
+	dataBigStruct             = BigStruct{w: 1}
 	dataString                = "foo"
 	dataSlice                 = []string{"foo"}
 	dataEface     interface{} = 42
 	dataIface     Iface       = IfaceImpl(42)
 
-	infoString = []byte{BitsMultiWord, BitsString}
-	infoSlice  = []byte{BitsMultiWord, BitsSlice, BitsDead}
+	infoString = []byte{BitsPointer, BitsDead}
+	infoSlice  = []byte{BitsPointer, BitsDead, BitsDead}
 	infoEface  = []byte{BitsMultiWord, BitsEface}
 	infoIface  = []byte{BitsMultiWord, BitsIface}
 )
diff --git a/src/pkg/runtime/heapdump.c b/src/pkg/runtime/heapdump.c
index 1a38087c8d..61f6fc2d95 100644
--- a/src/pkg/runtime/heapdump.c
+++ b/src/pkg/runtime/heapdump.c
@@ -260,16 +260,8 @@ dumpbv(BitVector *bv, uintptr offset)
 			break;
 		case BitsMultiWord:
 			switch(bv->data[(i+BitsPerPointer)/32] >> (i+BitsPerPointer)%32 & 3) {
-			case BitsString:
-				dumpint(FieldKindString);
-				dumpint(offset + i / BitsPerPointer * PtrSize);
-				i += BitsPerPointer;
-				break;
-			case BitsSlice:
-				dumpint(FieldKindSlice);
-				dumpint(offset + i / BitsPerPointer * PtrSize);
-				i += 2 * BitsPerPointer;
-				break;
+			default:
+				runtime·throw("unexpected garbage collection bits");
 			case BitsIface:
 				dumpint(FieldKindIface);
 				dumpint(offset + i / BitsPerPointer * PtrSize);
@@ -495,13 +487,13 @@ dumproots(void)
 	dumpint(TagData);
 	dumpint((uintptr)data);
 	dumpmemrange(data, edata - data);
-	dumpfields((BitVector){(edata - data)*8, (uint32*)runtime·gcdatamask});
+	dumpfields(runtime·gcdatamask);
 
 	// bss segment
 	dumpint(TagBss);
 	dumpint((uintptr)bss);
 	dumpmemrange(bss, ebss - bss);
-	dumpfields((BitVector){(ebss - bss)*8, (uint32*)runtime·gcbssmask});
+	dumpfields(runtime·gcdatamask);
 
 	// MSpan.types
 	allspans = runtime·mheap.allspans;
@@ -802,13 +794,11 @@ dumpbvtypes(BitVector *bv, byte *base)
 		if((bv->data[i/32] >> i%32 & 3) != BitsMultiWord)
 			continue;
 		switch(bv->data[(i+BitsPerPointer)/32] >> (i+BitsPerPointer)%32 & 3) {
-		case BitsString:
+		default:
+			runtime·throw("unexpected garbage collection bits");
 		case BitsIface:
 			i += BitsPerPointer;
 			break;
-		case BitsSlice:
-			i += 2 * BitsPerPointer;
-			break;
 		case BitsEface:
 			dumptype(*(Type**)(base + i / BitsPerPointer * PtrSize));
 			i += BitsPerPointer;
diff --git a/src/pkg/runtime/malloc.h b/src/pkg/runtime/malloc.h
index f5a2b2a42d..eafabb364a 100644
--- a/src/pkg/runtime/malloc.h
+++ b/src/pkg/runtime/malloc.h
@@ -303,7 +303,6 @@ extern	int8	runtime·size_to_class8[1024/8 + 1];
 extern	int8	runtime·size_to_class128[(MaxSmallSize-1024)/128 + 1];
 extern	void	runtime·InitSizes(void);
 
-
 typedef struct MCacheList MCacheList;
 struct MCacheList
 {
@@ -581,6 +580,9 @@ struct StackMap
 // (the index is encoded in PCDATA_StackMapIndex).
 BitVector	runtime·stackmapdata(StackMap *stackmap, int32 n);
 
+extern	BitVector	runtime·gcdatamask;
+extern	BitVector	runtime·gcbssmask;
+
 // defined in mgc0.go
 void	runtime·gc_m_ptr(Eface*);
 void	runtime·gc_g_ptr(Eface*);
diff --git a/src/pkg/runtime/mgc0.c b/src/pkg/runtime/mgc0.c
index d931e31525..db89f6036f 100644
--- a/src/pkg/runtime/mgc0.c
+++ b/src/pkg/runtime/mgc0.c
@@ -172,8 +172,8 @@ static FinBlock	*finc;		// cache of free blocks
 static FinBlock	*allfin;	// list of all blocks
 bool	runtime·fingwait;
 bool	runtime·fingwake;
-byte*	runtime·gcdatamask;
-byte*	runtime·gcbssmask;
+BitVector	runtime·gcdatamask;
+BitVector	runtime·gcbssmask;
 
 static Lock	gclock;
 
@@ -187,7 +187,7 @@ static void	gchelperstart(void);
 static void	flushallmcaches(void);
 static bool	scanframe(Stkframe *frame, void *unused);
 static void	scanstack(G *gp);
-static byte*	unrollglobgcprog(byte *prog, uintptr size);
+static BitVector	unrollglobgcprog(byte *prog, uintptr size);
 
 static FuncVal runfinqv = {runfinq};
 static FuncVal bgsweepv = {bgsweep};
@@ -221,8 +221,6 @@ scanblock(byte *b, uintptr n, byte *ptrmask)
 	uintptr i, nobj, size, idx, x, off, scanbufpos;
 	intptr ncached;
 	Workbuf *wbuf;
-	String *str;
-	Slice *slice;
 	Iface *iface;
 	Eface *eface;
 	Type *typ;
@@ -346,6 +344,10 @@ scanblock(byte *b, uintptr n, byte *ptrmask)
 				obj = *(byte**)(b+i);
 				goto markobj;
 			}
+
+			// With those three out of the way, must be multi-word.
+			if(bits != BitsMultiWord)
+				runtime·throw("unexpected garbage collection bits");
 			// Find the next pair of bits.
 			if(ptrmask == nil) {
 				if(ncached <= 0) {
@@ -358,22 +360,8 @@ scanblock(byte *b, uintptr n, byte *ptrmask)
 				bits = (ptrmask[((i+PtrSize)/PtrSize)/4]>>((((i+PtrSize)/PtrSize)%4)*BitsPerPointer))&BitsMask;
 
 			switch(bits) {
-			case BitsString:
-				str = (String*)(b+i);
-				if(str->len > 0)
-					obj = str->str;
-				break;
-			case BitsSlice:
-				slice = (Slice*)(b+i);
-				if(Debug && slice->cap < slice->len) {
-					g->m->traceback = 2;
-					runtime·printf("bad slice in object %p: %p/%p/%p\n",
-						b, slice->array, slice->len, slice->cap);
-					runtime·throw("bad slice in heap object");
-				}
-				if(slice->cap > 0)
-					obj = slice->array;
-				break;
+			default:
+				runtime·throw("unexpected garbage collection bits");
 			case BitsIface:
 				iface = (Iface*)(b+i);
 				if(iface->tab != nil) {
@@ -392,21 +380,9 @@ scanblock(byte *b, uintptr n, byte *ptrmask)
 				break;
 			}
 
-			if(bits == BitsSlice) {
-				i += 2*PtrSize;
-				if(ncached == 2)
-					ncached = 0;
-				else if(ptrmask == nil) {
-					// Refill cache and consume one quadruple.
-					cached = *--ptrbitp;
-					cached >>= gcBits;
-					ncached = 1;
-				}
-			} else {
-				i += PtrSize;
-				cached >>= gcBits;
-				ncached--;
-			}
+			i += PtrSize;
+			cached >>= gcBits;
+			ncached--;
 
 		markobj:
 			// At this point we have extracted the next potential pointer.
@@ -513,11 +489,11 @@ markroot(ParFor *desc, uint32 i)
 	// Note: if you add a case here, please also update heapdump.c:dumproots.
 	switch(i) {
 	case RootData:
-		scanblock(data, edata - data, runtime·gcdatamask);
+		scanblock(data, edata - data, (byte*)runtime·gcdatamask.data);
 		break;
 
 	case RootBss:
-		scanblock(bss, ebss - bss, runtime·gcbssmask);
+		scanblock(bss, ebss - bss, (byte*)runtime·gcbssmask.data);
 		break;
 
 	case RootFinalizers:
@@ -1852,7 +1828,7 @@ unrollgcprog1(byte *mask, byte *prog, uintptr *ppos, bool inplace, bool sparse)
 }
 
 // Unrolls GC program prog for data/bss, returns dense GC mask.
-static byte*
+static BitVector
 unrollglobgcprog(byte *prog, uintptr size)
 {
 	byte *mask;
@@ -1872,7 +1848,7 @@ unrollglobgcprog(byte *prog, uintptr size)
 		runtime·throw("unrollglobgcprog: program does not end with insEnd");
 	if(mask[masksize] != 0xa1)
 		runtime·throw("unrollglobgcprog: overflow");
-	return mask;
+	return (BitVector){masksize*8, (uint32*)mask};
 }
 
 void
@@ -2062,7 +2038,7 @@ runtime·getgcmask(byte *p, Type *t, byte **mask, uintptr *len)
 		*mask = runtime·mallocgc(*len, nil, 0);
 		for(i = 0; i < n; i += PtrSize) {
 			off = (p+i-data)/PtrSize;
-			bits = (runtime·gcdatamask[off/PointersPerByte] >> ((off%PointersPerByte)*BitsPerPointer))&BitsMask;
+			bits = (((byte*)runtime·gcdatamask.data)[off/PointersPerByte] >> ((off%PointersPerByte)*BitsPerPointer))&BitsMask;
 			(*mask)[i/PtrSize] = bits;
 		}
 		return;
@@ -2074,7 +2050,7 @@ runtime·getgcmask(byte *p, Type *t, byte **mask, uintptr *len)
 		*mask = runtime·mallocgc(*len, nil, 0);
 		for(i = 0; i < n; i += PtrSize) {
 			off = (p+i-bss)/PtrSize;
-			bits = (runtime·gcbssmask[off/PointersPerByte] >> ((off%PointersPerByte)*BitsPerPointer))&BitsMask;
+			bits = (((byte*)runtime·gcbssmask.data)[off/PointersPerByte] >> ((off%PointersPerByte)*BitsPerPointer))&BitsMask;
 			(*mask)[i/PtrSize] = bits;
 		}
 		return;
diff --git a/src/pkg/runtime/mgc0.h b/src/pkg/runtime/mgc0.h
index a7292effd3..d04b5cab8f 100644
--- a/src/pkg/runtime/mgc0.h
+++ b/src/pkg/runtime/mgc0.h
@@ -50,8 +50,8 @@ enum {
 	BitsMultiWord	= 3,
 	// BitsMultiWord will be set for the first word of a multi-word item.
 	// When it is set, one of the following will be set for the second word.
-	BitsString	= 0,
-	BitsSlice	= 1,
+	// NOT USED ANYMORE: BitsString	= 0,
+	// NOT USED ANYMORE: BitsSlice	= 1,
 	BitsIface	= 2,
 	BitsEface	= 3,
 
diff --git a/src/pkg/runtime/runtime.h b/src/pkg/runtime/runtime.h
index df2999bbd9..4f63fdf718 100644
--- a/src/pkg/runtime/runtime.h
+++ b/src/pkg/runtime/runtime.h
@@ -762,8 +762,6 @@ extern	uint32	runtime·cpuid_ecx;
 extern	uint32	runtime·cpuid_edx;
 extern	DebugVars	runtime·debug;
 extern	uintptr	runtime·maxstacksize;
-extern	byte*	runtime·gcdatamask;
-extern	byte*	runtime·gcbssmask;
 extern	Note	runtime·signote;
 
 /*
diff --git a/src/pkg/runtime/stack.c b/src/pkg/runtime/stack.c
index fc11d98c9b..61205bd478 100644
--- a/src/pkg/runtime/stack.c
+++ b/src/pkg/runtime/stack.c
@@ -592,19 +592,8 @@ adjustpointers(byte **scanp, BitVector *bv, AdjustInfo *adjinfo, Func *f)
 			break;
 		case BitsMultiWord:
 			switch(bv->data[(i+1) / (32 / BitsPerPointer)] >> ((i+1) * BitsPerPointer & 31) & 3) {
-			case BitsString:
-				// string referents are never on the stack, never need to be adjusted
-				i++; // skip len
-				break;
-			case BitsSlice:
-				p = scanp[i];
-				if(minp <= p && p < maxp) {
-					if(StackDebug >= 3)
-						runtime·printf("adjust slice %p\n", p);
-					scanp[i] = p + delta;
-				}
-				i += 2; // skip len, cap
-				break;
+			default:
+				runtime·throw("unexpected garbage collection bits");
 			case BitsEface:
 				t = (Type*)scanp[i];
 				if(t != nil && ((t->kind & KindDirectIface) == 0 || (t->kind & KindNoPointers) == 0)) {