Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Already on GitHub? Sign in to your account

cmd/gc: make slice/string updates atomic wrt garbage collector #8404

Closed
rsc opened this Issue Jul 21, 2014 · 7 comments

Comments

Projects
None yet
4 participants
Contributor

rsc commented Jul 21, 2014

Today garbage collection treats slices and strings as multiword objects: if cap == 0
(define cap=len for strings), the object base pointer is ignored, because it might point
just beyond the end of the underlying array. Both base pointer and cap must be consulted
to understand the slice/string.

When we move to a concurrent garbage collector that effectively races with the other
goroutines, slice and string updates made by an ordinary goroutine must be seen
atomically by the concurrent collector. It must not be possible for the collector to
observe a half-updated slice or string.

(The same general problem applies to interface representations, but the solution will be
different, so they are a separate issue, not yet filed.)

The plan is to disallow slice representations in which the base pointer points outside
the underlying array. Given that restriction, the garbage collector only needs to read
the base pointer, not the cap. Reducing the data read to a single word makes updates
atomic wrt the garbage collector.

A slice with cap 0 only has one valid operation that exposes the base pointer: testing
for nil. As long as we preserve that 

var x []byte
x[0:] == nil

and

var x = make([]byte, 10)
x[10:] != nil

we have considerable flexibility in the choice of actual base pointer.

The initial option we discussed is to have the slice operation check if it has computed
cap 0 for a non-nil base ptr, and if so change base to 1.

A better option appears to be to drop the addition entirely. That is, normally x[i:]
produces the slice {x+i*width, len(x)-i, cap(x)-i}. If cap(x)-i == 0, it can omit the
+i*width and produce {x, len(x)-i, cap(x)-i} = {x, 0, 0}. The result will be correctly
nil or non-nil matching whether x was nil/non-nil. 

The trick of dropping +i*width avoids having an "else" body after the cap=0
operation. The cap=0 path just jumps over a few instructions in the standard path.

Effectively, this rewrite implements x[i:] where cap(x)-i == 0 as x[0:0:0]. I believe
this implementation, although surprising, is legal.

I have an implementation that needs some more tests. Once this is done, the current bit
patterns in mgc0.c for string and slice change from 

    BitsMultiword BitsString => BitsPointer BitsScalar
    BitsMultiword BitsSlice BitsScalar => BitsPointer BitsScalar BitsScalar
Contributor

rsc commented Jul 22, 2014

Comment 1:

issue #8404 is the equivalent problem for interfaces.
Contributor

rsc commented Jul 22, 2014

Comment 2:

No, this is issue #8404. issue #8405 is the equivalent problem for interfaces.

Comment 3:

CL https://golang.org/cl/112570044 mentions this issue.
Contributor

randall77 commented Jul 22, 2014

Comment 4:

This fix does have the downside that slices or strings of size 0 keep the referenced
object alive.  Before they didn't.
It's probably a minor downside but worth remembering.
Member

dvyukov commented Jul 22, 2014

Comment 5:

Nice solution with leaving pointer the same.
I agree that keeping the underlying array in memory is sub-ideal. But even if it works
today, from user perspective it's non obvious that "x = x[1:]" releases the object. So
the advice to users is to use "x = nil" to release the object, which is explicit and
works reliably.
Contributor

rsc commented Aug 25, 2014

Comment 6:

This issue was closed by revision 613383c.

Status changed to Fixed.

Member

dvyukov commented Sep 11, 2014

Comment 7:

Issue #8262 has been merged into this issue.

@rsc rsc self-assigned this Sep 11, 2014

@rsc rsc added this to the Go1.4 milestone Apr 14, 2015

@rsc rsc removed the release-go1.4 label Apr 14, 2015

@gopherbot gopherbot locked and limited conversation to collaborators Jun 25, 2016

This issue was closed.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.