code review 112570044: cmd/gc, runtime: treat slices and strings like pointers...

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 issue 8404.

[rsc, 2014-07-22 04:08:52]

Hello josharian@gmail.com, khr (cc: golang-codereviews@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go/

[rsc, 2014-07-22 04:15:48]

I don't know why ADDPTR was used in one case but not the other here. I
didn't use it. It looks like it can be deleted. Josh?

[josharian, 2014-07-22 17:05:50]

> I don't know why ADDPTR was used in one case but not the other here. I
> didn't use it. It looks like it can be deleted. Josh?

Yes, please delete it!

base is a uintptr. src is a tptr. The compiler (correctly) rejects pointer
arithmetic with ADD, so adding an offset to src directly is not possible. Prior
to CL 91850043, to work around this, src's type was changed to tuintptr in order
to add; this broke registerization. This CL solves the problem a much better
way: Simply copy src into base, thus enabling arithmetic on it.

More comments on this CL to come, but they may be delayed due to OSCON
activities; apologies.

[josharian, 2014-07-22 18:04:05]

> The plan is to disallow slice representations in which the base pointer points
outside the underlying array.

make([]T, 0) and reflect.{MakeSlice,Slice,Slice3} appear not to be handled yet.
Empty slices and strings can also be created through []byte/[]rune/string
conversions -- haven't thought yet about whether those need new treatment.

More to come.

[rsc, 2014-07-22 18:31:11]

On Tue, Jul 22, 2014 at 2:04 PM, <josharian@gmail.com> wrote:

> The plan is to disallow slice representations in which the base
>>
> pointer points outside the underlying array.
>
> make([]T, 0) and reflect.{MakeSlice,Slice,Slice3} appear not to be
> handled yet. Empty slices and strings can also be created through
> []byte/[]rune/string conversions -- haven't thought yet about whether
> those need new treatment.
>

Slices created empty are fine. They all use a special base pointer that is
valid for the purposes of this discussion (&runtime.zerobase). It is only
the empty slice at the end of a non-empty slice that is the problem, so
it's only the slice operator (explicit or implicit) that needs to change.
Conversions are just allocations - they're fine.

reflect.MakeSlice is okay. reflect.Slice and reflect.Slice3 do need to
change.

Russ

[josharian, 2014-07-22 19:05:51]

Here's before and after generated code (6g) for

func f() {
	a := make([]byte, 10)
	b := a[3:5]
	_ = b
}

BEFORE

"".f t=1 size=112 value=0 args=0 locals=0x50
	000000 00000 (slice.go:3)	TEXT	"".f+0(SB),$80-0
	000000 00000 (slice.go:3)	MOVQ	(TLS),CX
	0x0009 00009 (slice.go:3)	CMPQ	SP,(CX)
	0x000c 00012 (slice.go:3)	JHI	,21
	0x000e 00014 (slice.go:3)	CALL	,runtime.morestack00_noctxt(SB)
	0x0013 00019 (slice.go:3)	JMP	,0
	0x0015 00021 (slice.go:3)	SUBQ	$80,SP
	0x0019 00025
(slice.go:3)	FUNCDATA	$2,gclocals·3280bececceccd33cb74587feedb1f9f+0(SB)
	0x0019 00025
(slice.go:3)	FUNCDATA	$3,gclocals·f883d3996c76325fd1714d4e3de9fa33+0(SB)
	0x0019 00025 (slice.go:4)	LEAQ	"".autotmp_0000+22(SP),DI
	0x001e 00030 (slice.go:4)	MOVL	$0,AX
	0x0020 00032 (slice.go:4)	STOSQ	,
	0x0022 00034 (slice.go:4)	STOSB	,
	0x0023 00035 (slice.go:4)	STOSB	,
	0x0024 00036 (slice.go:4)	LEAQ	"".autotmp_0000+22(SP),BX
	0x0029 00041 (slice.go:4)	CMPQ	BX,$0
	0x002d 00045 (slice.go:4)	JEQ	$1,102
	0x002f 00047 (slice.go:4)	MOVQ	$10,AX
	0x0036 00054 (slice.go:5)	CMPQ	AX,$5
	0x003a 00058 (slice.go:5)	JCS	$0,95
	0x003c 00060 (slice.go:5)	ADDQ	$3,BX
	0x0040 00064 (slice.go:5)	MOVQ	BX,"".b+32(SP)
	0x0045 00069 (slice.go:5)	MOVQ	$2,"".b+40(SP)
	0x004e 00078 (slice.go:5)	MOVQ	AX,BX
	0x0051 00081 (slice.go:5)	SUBQ	$3,BX
	0x0055 00085 (slice.go:5)	MOVQ	BX,"".b+48(SP)
	0x005a 00090 (slice.go:7)	ADDQ	$80,SP
	0x005e 00094 (slice.go:7)	RET	,
	0x005f 00095 (slice.go:5)	PCDATA	$0,$0
	0x005f 00095 (slice.go:5)	PCDATA	$1,$0
	0x005f 00095 (slice.go:5)	CALL	,runtime.panicslice(SB)
	0x0064 00100 (slice.go:5)	UNDEF	,
	0x0066 00102 (slice.go:4)	MOVL	AX,(BX)
	0x0068 00104 (slice.go:4)	JMP	,47

AFTER

"".f t=1 size=128 value=0 args=0 locals=0x40
	000000 00000 (slice.go:3)	TEXT	"".f+0(SB),$64-0
	000000 00000 (slice.go:3)	MOVQ	(TLS),CX
	0x0009 00009 (slice.go:3)	CMPQ	SP,(CX)
	0x000c 00012 (slice.go:3)	JHI	,21
	0x000e 00014 (slice.go:3)	CALL	,runtime.morestack00_noctxt(SB)
	0x0013 00019 (slice.go:3)	JMP	,0
	0x0015 00021 (slice.go:3)	SUBQ	$64,SP
	0x0019 00025
(slice.go:3)	FUNCDATA	$2,gclocals·3280bececceccd33cb74587feedb1f9f+0(SB)
	0x0019 00025
(slice.go:3)	FUNCDATA	$3,gclocals·0528ab8f76149a707fd2f0025c2178a3+0(SB)
	0x0019 00025 (slice.go:4)	LEAQ	"".autotmp_0000+30(SP),DI
	0x001e 00030 (slice.go:4)	MOVL	$0,AX
	0x0020 00032 (slice.go:4)	STOSQ	,
	0x0022 00034 (slice.go:4)	STOSB	,
	0x0023 00035 (slice.go:4)	STOSB	,
	0x0024 00036 (slice.go:4)	LEAQ	"".autotmp_0000+30(SP),BX
	0x0029 00041 (slice.go:4)	CMPQ	BX,$0
	0x002d 00045 (slice.go:4)	JEQ	$1,118
	0x002f 00047 (slice.go:4)	NOP	,
	0x002f 00047 (slice.go:4)	MOVQ	$10,BP
	0x0036 00054 (slice.go:4)	MOVQ	$10,CX
	0x003d 00061 (slice.go:5)	CMPQ	CX,$5
	0x0041 00065 (slice.go:5)	JCS	$0,111
	0x0043 00067 (slice.go:5)	MOVQ	BX,AX
	0x0046 00070 (slice.go:5)	MOVQ	$2,DX
	0x004d 00077 (slice.go:5)	SUBQ	$3,CX
	0x0051 00081 (slice.go:5)	CMPQ	CX,$0
	0x0055 00085 (slice.go:5)	JEQ	$0,91
	0x0057 00087 (slice.go:5)	ADDQ	$3,AX
	0x005b 00091 (slice.go:5)	MOVQ	AX,"".b+40(SP)
	0x0060 00096 (slice.go:5)	MOVQ	DX,"".b+48(SP)
	0x0065 00101 (slice.go:5)	MOVQ	CX,"".b+56(SP)
	0x006a 00106 (slice.go:7)	ADDQ	$64,SP
	0x006e 00110 (slice.go:7)	RET	,
	0x006f 00111 (slice.go:5)	PCDATA	$0,$0
	0x006f 00111 (slice.go:5)	PCDATA	$1,$0
	0x006f 00111 (slice.go:5)	CALL	,runtime.panicslice(SB)
	0x0074 00116 (slice.go:5)	UNDEF	,
	0x0076 00118 (slice.go:4)	MOVL	AX,(BX)
	0x0078 00120 (slice.go:4)	JMP	,47

I haven't poked at it much, but it looks like the optimizer is afraid of the
JMP. Note that the after version has a dead MOV

	0x002f 00047 (slice.go:4)	MOVQ	$10,BP

and a copy propagation(?) gets missed

	0x0046 00070 (slice.go:5)	MOVQ	$2,DX
	// ... JMP ...
	0x0060 00096 (slice.go:5)	MOVQ	DX,"".b+48(SP)

Could we use a conditional move instead of a JMP? (Would that help?)

[josharian, 2014-07-23 01:45:43]

On 2014/07/22 18:31:11, rsc wrote:
> On Tue, Jul 22, 2014 at 2:04 PM, <mailto:josharian@gmail.com> wrote:
> 
> > The plan is to disallow slice representations in which the base
> >>
> > pointer points outside the underlying array.
> >
> > make([]T, 0) and reflect.{MakeSlice,Slice,Slice3} appear not to be
> > handled yet. Empty slices and strings can also be created through
> > []byte/[]rune/string conversions -- haven't thought yet about whether
> > those need new treatment.
> >
> 
> Slices created empty are fine. They all use a special base pointer that is
> valid for the purposes of this discussion (&runtime.zerobase). It is only
> the empty slice at the end of a non-empty slice that is the problem, so
> it's only the slice operator (explicit or implicit) that needs to change.
> Conversions are just allocations - they're fine.

Ah, I see; thanks. For future readers who might be confused in the same way I
was, conversion allocations are fine for the same reason the make([]T, 0)
allocation is fine. They both go through runtime·mallocgc, which begins:

	if(size == 0) {
		// All 0-length allocations use this pointer.
		// The language does not require the allocations to
		// have distinct values.
		return &runtime·zerobase;
	}

And actually, at the moment, []byte("") returns a slice with capacity 8, so it's
only string([]byte{}) that relies on &runtime·zerobase.


That's it from me for now on this CL. Thanks for your patience.

-josh

[rsc, 2014-07-23 02:50:49]

Hello josharian@gmail.com, khr@golang.org (cc:
golang-codereviews@googlegroups.com),

Please take another look.

[josharian, 2014-07-23 18:37:13]

I remain concerned that introducing a JMP as part of every slice will end up
preventing lots of peephole optimizations. (Sorry if I buried the lede on this
in my comment earlier.)

https://codereview.appspot.com/112570044/diff/80001/src/cmd/gc/subr.c
File src/cmd/gc/subr.c (right):

https://codereview.appspot.com/112570044/diff/80001/src/cmd/gc/subr.c#newcode663
src/cmd/gc/subr.c:663: if(bad == T)
Looks like the cases got inverted here:

if(bad == T)
	mtype = key->etype;
else
	mtype = bad->etype;

This currently causes ./make.bash to fail.

https://codereview.appspot.com/112570044/diff/80001/src/pkg/reflect/value.go
File src/pkg/reflect/value.go (right):

https://codereview.appspot.com/112570044/diff/80001/src/pkg/reflect/value.go#...
src/pkg/reflect/value.go:1793: s.Data = unsafe.Pointer(uintptr(base) +
uintptr(i)*typ.elem.Size())
This line can now be deleted.

[khr, 2014-07-23 22:53:21]

LGTM, with josharian's comments fixed.

[josharian, 2014-07-24 16:51:25]

If you want to get this in today before you go, I'll look at tweaking the
generated code later; it's not a blocker.

LGTM after the two minor fixes


On Wednesday, July 23, 2014, <khr@golang.org> wrote:

> LGTM, with josharian's comments fixed.
>
>
> https://codereview.appspot.com/112570044/
>

[josharian, 2014-07-30 19:28:31]

> If you want to get this in today before you go, I'll look at tweaking the
> generated code later; it's not a blocker.

I dug at this a bit, and I'm not sure it's worth the effort right now. I've
moved discussion of this to issue 8448.

[rsc, 2014-08-25 18:10:33]

I refreshed this CL and will submit it shortly. I had to reapply some of
the changes in mgc0.c since Dmitriy rewrote it all while the CL was
pending. There was a bug in the heapdump that I had to fix too (the data
segment bitmap was the same size as the data segment).

Normally I'd wait for a re-review, but if I do that I am afraid that the
underlying code will have been completely rewritten again when I 'hg sync'.
I hope the runtime churn stops soon.

I will look into the jump/optimizer interaction separately.

Thanks.
Russ

[rsc, 2014-08-25 18:11:28]

Can someone tell me the difference between BitsScalar and BitsDead? I don't
believe the liveness analysis distinguishes these, and it doesn't really
make sense in the heap (except for struct field padding?) so I don't
understand why the GC info distinguishes them.

Why do we have both?

Thanks.
Russ

[dvyukov, 2014-08-25 18:31:35]

BitsScalar and BitsDead are used in stacks. If the word contains at
least one live scalar var, then it is marked as BitsScalar. If the
word contains no live vars, then it is BitsDead.
Heap type info does not use BitsDead. All BitsDead are replaced with
BitsScalar.
However, runtime uses BitsDead in GC bitmap to mark objects as noscan
or indicate end of object.

On Mon, Aug 25, 2014 at 10:11 PM, Russ Cox <rsc@golang.org> wrote:
> Can someone tell me the difference between BitsScalar and BitsDead? I don't
> believe the liveness analysis distinguishes these, and it doesn't really
> make sense in the heap (except for struct field padding?) so I don't
> understand why the GC info distinguishes them.
>
> Why do we have both?
>
> Thanks.
> Russ
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-codereviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-codereviews+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[rsc, 2014-08-25 18:38:23]

*** Submitted as https://code.google.com/p/go/source/detail?r=caab29a25f68 ***

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 issue 8404.

LGTM=khr, josharian
R=josharian, khr, dvyukov
CC=golang-codereviews
https://codereview.appspot.com/112570044

[rsc, 2014-08-25 18:44:00]

I chatted with Dmitriy a bit about BitsScalar and BitsDead.

The liveness analysis ignores stack variables that do not contain pointers.
It does track structs with both pointers and scalars in them. There is a
debug mode that poisons things marked BitsDead during stack copying. That
mode only applies to the tracked area of the stack, so it is important to
use BitsScalar, not BitsDead, in that place.

We may get down to 1 bit per word for the stack bitmaps (live pointer vs
other), in which case BitsScalar and BitsDead would merge and that debug
mode would go away.

Russ

[dvyukov, 2014-08-25 18:59:05]

On Mon, Aug 25, 2014 at 10:43 PM, Russ Cox <rsc@golang.org> wrote:
> I chatted with Dmitriy a bit about BitsScalar and BitsDead.
>
> The liveness analysis ignores stack variables that do not contain pointers.
> It does track structs with both pointers and scalars in them. There is a
> debug mode that poisons things marked BitsDead during stack copying. That
> mode only applies to the tracked area of the stack, so it is important to
> use BitsScalar, not BitsDead, in that place.
>
> We may get down to 1 bit per word for the stack bitmaps (live pointer vs
> other), in which case BitsScalar and BitsDead would merge and that debug
> mode would go away.


I've checked runtime code, the debugging mode has gone already.

[rsc, 2014-08-25 19:11:11]

I think the debug mode is still there.

case BitsDead:
if(runtime·debug.gcdead)
scanp[i] = (byte*)PoisonStack;
break;

[dvyukov, 2014-08-25 19:20:31]

ah, it's already copy-pasted from mgc0.c :)

On Mon, Aug 25, 2014 at 11:11 PM, Russ Cox <rsc@golang.org> wrote:
> I think the debug mode is still there.
>
> case BitsDead:
> if(runtime·debug.gcdead)
> scanp[i] = (byte*)PoisonStack;
> break;
>
>

[gobot, 2014-08-25 21:46:12]

This CL appears to have broken the darwin-386 builder.
See http://build.golang.org/log/a6467e911eebd309380add098e6d63ba831c9cf1

[dvyukov, 2014-09-01 08:27:19]

there is something wrong with this change, it increases GC pause by 10-20%
http://build.golang.org/perfdetail?commit=caab29a25f686946a383ec31d2ea6408265...


On Tue, Aug 26, 2014 at 1:46 AM,  <gobot@golang.org> wrote:
> This CL appears to have broken the darwin-386 builder.
> See http://build.golang.org/log/a6467e911eebd309380add098e6d63ba831c9cf1
>
> https://codereview.appspot.com/112570044/

[rsc, 2014-09-01 13:48:14]

On Mon, Sep 1, 2014 at 4:26 AM, Dmitry Vyukov <dvyukov@google.com> wrote:

> there is something wrong with this change, it increases GC pause by 10-20%
>
>
http://build.golang.org/perfdetail?commit=caab29a25f686946a383ec31d2ea6408265...


Thanks for noticing. Please file an issue.

Russ