spec: clarify how unsafe.Pointers may be used to determine offsets between addresses

[kortschak]

For background see discussion at https://groups.google.com/d/topic/golang-nuts/Uet5p_3JhZs/discussion

Currently it is possible to determine the offset between two values' addresses by finding the difference between uintptrs converted from unsafe.Pointer values. This is the only way to be able to determine whether two slices overlap in memory since the advent of three index slicing and the only way to determine in less than linear time whether blocked sparse slices overlap (relevant for views in constructed 2D slices for e.g. BLAS operations). In the event that a moving GC is implemented this may no longer be safe; if a GC move occurs between taking the conversion to uintptr of address of the first and second values, the offset may be incorrect. Note that the GC move does not otherwise invalidate the offset between overlapping slices or falsely result in non-overlapping being construed as overlapping.

[minux]

it's probably make sense to introduce a unsafe.Overlap (or runtime.Overlap) function to determine if two slices overlap. Allowing subtraction of unsafe.Pointer (after converted to uintptr), might give the user false impression that there is a fixed distance between two pointers (i.e. pointers don't move)

[kortschak]

unsafe.Offset(a, b) int would be more generalisable - I don't want to just be able to determine whether slices overlap, but also determine if strided blocks within the slice overlap. This requires an offset and a pair of lengths (and element size) - the latter which I can already get by other means.

[kortschak]

To add a data point to this. We now implement strided block overlap detection in github.com/gonum/matrix/mat64, documentation here and detection implementation here. This is done essentially as described in the original discussion, both with unsafe for environments that allow that and via reflect for those that don't.

I don't see a constant time implementation that can be achieved without access to an offset call.

[mdempsky]

Something like below seems like it should be safe even under a moving GC.

// Overlap returns whether there exist i and j such that
// a[i*stride] and b[j*stride] address the same variable.
func overlap(a, b []float64, stride uintptr) bool {
    an, bn := uintptr(len(a)), uintptr(len(b))
    if an == 0 || bn == 0 {
        // Degenerate case; empty slices can't overlap.
        return false
    }

    // Keep as unsafe.Pointer for safety under moving GC.
    ap, bp := unsafe.Pointer(&a[0]), unsafe.Pointer(&b[0])

    // If a and b are entirely disjoint, there can't be any overlap.
    if uintptr(bp) - uintptr(ap) >= 8 * an && uintptr(ap) - uintptr(bp) >= 8 * bn {
        return false
    }

    // There is *some* overlap, so ap and bp must point into the same variable,
    // which means we can assume a stable offset between them.
    offset := uintptr(bp) - uintptr(ap)

    // ap and bp must be aligned modulo the stride.
    return offset % (stride * 8) == 0
}

[kortschak]

That does not do what the linked code does. We want to return whether there is an i,j and x,y such that a[i + jstride] and b[x + ystride] address the same variable when the indices are constrained such that they index a subset of the possible blocks that may be described with the given stride over the slices. However it does suggest a possible solution.

// offset returns the number of float64 values b[0] is after a[0].
func offset(a, b []float64) int {
    a0 := unsafe.Pointer(&a[0])
    b0 := unsafe.Pointer(&b[0])

    if a0 == b0 {
        return 0
    }
    if uintptr(a0) < uintptr(b0) {
        return int((uintptr(b0) - uintptr(a0)) / unsafe.Sizeof(float64(0)))
    }
    return -int((uintptr(a0) - uintptr(b0)) / unsafe.Sizeof(float64(0)))
}

and the family friendly version (this one is more tenuous since it depends on values passed back from a reflect call):

// offset returns the number of float64 values b[0] is after a[0].
func offset(a, b []float64) int {
    va0 := reflect.ValueOf(a).Index(0)
    vb0 := reflect.ValueOf(b).Index(0)

    if va0.UnsafeAddr() == vb0.UnsafeAddr() {
        return 0
    }
    if vb0.UnsafeAddr() < va0.UnsafeAddr() {
        return int((vb0.UnsafeAddr() - va0.UnsafeAddr()) / sizeOfFloat64)
    }
    return -int((va0.UnsafeAddr() - vb0.UnsafeAddr()) / sizeOfFloat64)
}

These are then used in the functions also linked above.

Note that it is OK for our use case for the offset to be used after a possible GC move since if a and b are part of the same allocation they move together and so the offset remains valid, and if they are not, an offset cannot become indicative of an overlap. The potential race in the sign condition is troubling though.

[RLH]

There are certainly whole classes of concurrent GC algorithms for which
this will not work. GC's using a variation of a Brooks' pointer, such as
proposed for the Red Hat LLVM based GC as well as Sapphire style
collectors. Currently Go does not use these techniques.

On Sat, Nov 28, 2015 at 4:17 AM, Dan Kortschak notifications@github.com
wrote:

That does not do what the linked code does. We want to return whether
there is an i,j and x,y such that a[i + j_stride] and b[x + y_stride]
address the same variable. However it does suggest a possible solution.

// offset returns the number of float64 values b[0] is after a[0].
func offset(a, b []float64) int {
a0 := unsafe.Pointer(&a[0])
b0 := unsafe.Pointer(&b[0])

if a0 == b0 {
    return 0
}
if uintptr(a0) < uintptr(b0) {
    return int((uintptr(b0) - uintptr(a0)) / unsafe.Sizeof(float64(0)))
}
return -int((uintptr(a0) - uintptr(b0)) / unsafe.Sizeof(float64(0)))

}

and the family friendly version (this on is more tenuous since it depends
on values passed back from a reflect call):

// offset returns the number of float64 values b[0] is after a[0].
func offset(a, b []float64) int {
va0 := reflect.ValueOf(a).Index(0)
vb0 := reflect.ValueOf(b).Index(0)

if va0.UnsafeAddr() == vb0.UnsafeAddr() {
    return 0
}
if va0.UnsafeAddr() < vb0.UnsafeAddr() {
    return int((vb0.UnsafeAddr() - va0.UnsafeAddr()) / sizeOfFloat64)
}
return -int((va0.UnsafeAddr() - vb0.UnsafeAddr()) / sizeOfFloat64)

}

These are then used in the functions also linked above.

Note that it is OK for our use case for the offset to be used after a
possible GC move since if a and b are part of the same allocation they move
together and so the offset remains valid, and if they are not, an offset
cannot become indicative of an overlap.

—
Reply to this email directly or view it on GitHub
#12445 (comment).

[kortschak]

There are certainly whole classes of concurrent GC algorithms for which this will not work.

This is true if the GC algorithms are considered in isolation from the language's promises about behaviour. This issue aims to address that.

Currently there seems to be a de facto promise* see discussion in #7192 and #8994 that use of converted unsafe.Pointers is atomic wrt the GC if the use is in a single expression. This is how the unsafe.Pointer->uintptr happens in the code above, with the exception of the condition which troubles me.

* Not a promise.

Currently Go does not use these techniques.

This is understood; hence the comments in the linked code. The issue for us is that introduction of GC behaviour that breaks this code without a work around to obtain an offset will break gonum/matrix/mat64 behaviour. We use unsafe for the normal case and we don't expect Go1 coverage for that, but we also use the reflect equivalent for environments that disallow unsafe.

[mdempsky]

@RLH Sorry, when you say "for which this will not work", what are you referring to by "this"? E.g., would the overlap function I wrote above (setting aside momentarily that it doesn't address @kortschak's actual use case) not be safe under some of those GC implementations?

The Go spec says "For struct s with field f: uintptr(unsafe.Pointer(&s)) + unsafe.Offsetof(s.f) == uintptr(unsafe.Pointer(&s.f))". I've generally extrapolated from this that within a single expression, pointers when converted to uintptr must represent a consistent view of memory, as otherwise the equality wouldn't necessarily hold. Also that other uintptr expressions like uintptr(unsafe.Pointer(&s.f)) - uintptr(unsafe.Pointer(&s)) == unsafe.Offsetof(s.f) and uintptr(unsafe.Pointer(&s.f)) >= uintptr(unsafe.Pointer(&s)) would be valid and guaranteed to evaluate to true.

If those aren't safe extrapolations, perhaps the spec should be revised to only guarantee unsafe.Pointer(uintptr(unsafe.Pointer(&s)) + unsafe.Offsetof(s.f)) == unsafe.Pointer(&s.f).

[kortschak]

@mdempsky I think this is #8994.

[mdempsky]

@kortschak They're certainly very related. But my impression is #8994 is about the rules for how you can safely convert unsafe.Pointer to uintptr and back, whereas this issue seems to be more about which arithmetic laws still hold after converting unsafe.Pointer to uintptr. E.g., the overlap/offset functions being discussed above don't care about convert uintptr back to unsafe.Pointer.

[kortschak]

Yes, that's true, though I think that once the rules for the other issue are settled that defines what happens here.

[RLH]

Let me try again. Various concurrent moving collectors including those
using a Brooks' barrier as well as the Sapphire algorithm rely on the fact
that two different bit pattern can be used to represent the same (pointer
to an) object. One bit pattern may refer to the "old" version of the object
and another to the "new" version of the object. Depending on the algorithm
a read and/or write barrier is used to ensure that values returned from the
object are consistent. The literature explains how the algorithms
extinguish the "old" version by replacing them with "new" version and what
invariants the read and write barriers need to maintain to ensure object
identity, consistency, completeness, and termination.

This creates implementation issues around the implementation of == which
doesn't dereference the pointer and thus fall outside the barriers used
when the object is dereferenced. This == problem was first noted and solved
in the original Brooks paper as well as being noted, referenced, and solved
in the Sapphire paper. It is important to note that in at least the
Sapphire algorithm the implementation of == is the only place where reads
of (pointers to) objects require special consideration. Go's spec allows
for such an implementation.

The single example found in the unsafe part of the spec seems to extend the
semantics of == to include calls to unsafe.Pointer in the same ==
expression where the compiler can statically determine that the arguments
passed to unsafe.Pointer refer to the same object and eliminate one of the
calls using CSE. The unsafe.Offset call can be replaced with known static
offset to a field within a struct. I would be surprised if the compiler
doesn't already do this. I believe that this extension of == semantics is
tractable and object identity can be maintained.

The examples provided in this thread use unsafe.Pointer in different
statements and then expect the returned bits to be comparable. This is
unsafe though it works in current implementation.

In summary, the statement that "Something like below seems like it should
be safe even under a moving GC." is not true for at least two well known
concurrent copying collectors.

More to the point is that both #7192
#7192 and #8994
#8994 have resisted changing the spec.
What has changed since those decisions? Changing the stable spec is a very
high bar, particularly when the change will alter fundamental concepts like
object identity that GC algorithms have wrestled with for decades.

On Sat, Nov 28, 2015 at 9:32 PM, Dan Kortschak notifications@github.com
wrote:

Yes, that's true, though I think that once the rules for the other issue
are settled that defines what happens here.

—
Reply to this email directly or view it on GitHub
#12445 (comment).

[mdempsky]

@RLH Thanks. I understand the idea that under a moving GC that a single "pointer value" (in the Go spec/language sense) might at a given time have multiple bit patterns at the machine implementation level, and so this complicates the implementation of Go pointer equality.

However, we seem to have different interpretations of the spec's uintptr(unsafe.Pointer(&s)) + unsafe.Offsetof(s.f) == uintptr(unsafe.Pointer(&s.f)) guarantee (which I'll emphasize again is currently written using integer equality, not pointer equality). It sounds like you interpret the guarantee is precisely worded and only holds when &s and &s.f are all locally visible to the compiler so it can be satisfied via CSE optimizations, whereas I've instead interpreted it generalizes to examples like this (even assuming no inlining/cross-package compiler optimizations):

package pkg

import "unsafe"

type S struct { E, F int }

func Func(p, q unsafe.Pointer) bool {
    return uintptr(p) + unsafe.Offsetof(S{}.F) == uintptr(q)
}

.

package main

import (
    "unsafe"
    "./pkg"
)

func main() {
    var s pkg.S
    if !pkg.Func(unsafe.Pointer(&s), unsafe.Pointer(&s.F)) {
        panic("spec violation")
    }
}

So at the very least I think it's worth deciding/clarifying which interpretation of the spec is intended.