Skip to content
New issue

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

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

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
Closed

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

rsc opened this issue Jul 21, 2014 · 7 comments
Milestone

Comments

@rsc
Copy link
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
@rsc
Copy link
Contributor Author

rsc commented Jul 22, 2014

Comment 1:

issue #8404 is the equivalent problem for interfaces.

@rsc
Copy link
Contributor Author

rsc commented Jul 22, 2014

Comment 2:

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

@gopherbot
Copy link

Comment 3:

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

@randall77
Copy link
Contributor

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.

@dvyukov
Copy link
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.

@rsc
Copy link
Contributor Author

rsc commented Aug 25, 2014

Comment 6:

This issue was closed by revision 613383c.

Status changed to Fixed.

@dvyukov
Copy link
Member

dvyukov commented Sep 11, 2014

Comment 7:

Issue #8262 has been merged into this issue.

@rsc rsc added fixed labels Sep 11, 2014
@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
@golang golang locked and limited conversation to collaborators Jun 25, 2016
wheatman pushed a commit to wheatman/go-akaros that referenced this issue Jun 25, 2018
…llection

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 golang#8404.

LGTM=khr, josharian
R=josharian, khr, dvyukov
CC=golang-codereviews
https://golang.org/cl/112570044
wheatman pushed a commit to wheatman/go-akaros that referenced this issue Jul 9, 2018
…llection

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 golang#8404.

LGTM=khr, josharian
R=josharian, khr, dvyukov
CC=golang-codereviews
https://golang.org/cl/112570044
@rsc rsc removed their assignment Jun 23, 2022
This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

4 participants