[Pitch] Aliased Span and Ref types

Evolution Pitches
1

Hi all,

I've written a proposal to introduce a family of Aliased*Span and Aliased*Ref types that provide the memory safety guarantees of the Span and Ref family of types, but with looser requirements around exclusivity, making them suitable for shared memory and interoperability with other languages.

There's a lot of deep Law of Exclusivity and pointer-aliasing stuff in this proposal, but the APIs themselves are fairly straightforward mirrors of the *Span and *Ref types, albeit with small critical tweaks to account for aliasing of the referenced memory. Here is the full proposal: swift-evolution/proposals/nnnn-aliased-spans.md at aliased-spans · DougGregor/swift-evolution · GitHub

Doug

11 Likes
2

++100. I need it yesterday!

1 Like
3

I can definitely see the need for where this is coming from, but one aspect that I don't think is discussed much in this proposal that I think is fairly important here is the impact on library authors and general/"currency" APIs. In Foundation, for example, we've been looking at adding APIs that use spans as currency types for contiguous memory (for example, you might want an API that writes bytes to a file to take a RawSpan as input instead of a Data or a Collection<UInt8>). The span types are a great fit because they were a "lowest common denominator" (a single-ish type that can be created cheaply from many storage types) and did not suffer the performance drawbacks of unspecialized generics. However with the new aliased types, I'm uncertain whether library authors should now be accepting the aliased types in addition/instead of the non-aliased span types for cases where exclusivity is not required. If not (if library authors continue using Spans except some cases where aliased types are required), without a safe way to convert between the types (by definition) I'm worried that we'll be putting ourselves into a position where clients will be stuck bearing the burden of the friction between APIs that use the different categories. You discussed this a bit in the implications on adoption section, but I'm curious if you have more detailed thoughts on how best to balance client friction vs. library author confusion/effort by creating a second category of span currency types.

13 Likes
4

Am I missing something? How can this be safe?

var string = "Hello"
// let's share it
let stringRef = AliasedMutableRef(&string)
// let's modify it in parallel
await withDiscardingTaskGroup { group in
    for i in 0..<100 {
        group.addTask {
            // AliasedMutableRef<String> is Copyable (always)
            // and Sendable (because String is)

            // += would do the same, but want to call out we use get & set
            stringRef.value = stringRef.value + "\(i)"

            // the `get` can tear against parallel `set` since
            // String stores count & flags separate to its buffer

            // the `set` can break in many ways including
            // being very wrong about `isKnownUniquelyReferenced`
            // for the buffer
        }
    }
}

Even if you restricted AliasedMutableRef.Element to Bitwisecopyable it still wouldn't be safe, since writes might be nonatomic & could tear in semantically-meaningful ways. I guess this is where Rust's division of Send and Sync would help, but I don't see a way out in Swift?

5

Note that even UnsafeMutablePointer does not use get/set and mutates values in-place today.

Non-mutating access of pointee behaves differently, depending on the context. If Pointee is required to beCopyable it does return a copy. However, if the access is in a generic context and Pointee is not required to be Copyable then Unsafe(Mutable)Pointer does not copy the value, even if it is later specialized with a Copyable type.

6

The aliased types would only be safe assuming that the copy operations of values will not re-entrantly access the value again, leading to a conflicting access. This is currently (mostly) fine, because types can't have custom copy operations in Swift (however, they can in imported C++ types). However, it does close the door for safely adding custom copy operations to types in Swift in the future, unless those custom copy operations have special restrictions preventing them from re-entrantly accessing aliased values.

7

My guidance here would be to use the (non-aliased) span types for APIs. The performance advantages of the stronger exclusivity model of the span types are important for the Swift ecosystem as a whole, and the span types fit wonderfully in that ecosystem.

I think it's fine to have friction when dealing with something like shared memory, because there's a lot you need to think about there already and it's fairly specialized code. For dealing with C APIs, I see no other way forward: layering exclusivity on C is not really possible at scale, and pessimizing the performance of the Swift ecosystem as a whole to reduce friction with C has the wrong trade-offs.

Once we figure out what the guidance should be, I'll capture the result in that section.

Thanks for pushing on this area---it's something that concerns me with the introduction of these aliased types, even though I know we need them, and I want our guidance to be clear.

Doug

3 Likes
8

Ah, thanks for pointing this out. I think the answer might well be that these types are never Sendable. The use of get/set rather than any kind of borrowing only helps with the non-parallel case.

I suppose we could invent some kind of protocol for "atomic updates" or "non-tearing updates" or similar, because as you note, BitwiseCopyable is not even sufficient. Range is the simplest case to describe here, because it's easy to break the lower <= upper invariant if there is tearing.

That's correct; it's using an unsafeMutableAddress accessor to vend a pointer directly.

I don't think this is true? Non-mutating access to an unsafe pointer uses the unsafeAddress addressor, which vends the address directly. Copies might happen when needed, but they're not guaranteed by anything I can see.

This holds now, for sure, but isn't this a necessary condition for any copy operation, even if we were to add custom ones in the future?

Doug

9

Perhaps SE-0525's FullyInhabited is strict enough for Sendable to be safe?

10

It's fairly contrived, but note that re-entrant code (via callbacks) can also violate exclusivity invariants even if it can't actually race updates.

11

That states that every bit pattern is a valid instance, so even tearing does not introduce a safety problem. Nice catch!

On a variable or when there's a borrow-like accessor, that's true. But get/set accessors don't really have exclusivity invariants in that way. You call the getter, perform whatever operations you want on the local value, then call the setter with the result. Re-entrant code can mean that you have weird nesting, but it doesn't violate exclusivity.

Doug

3 Likes
12

Ah, whoops, right. I was thinking about get/set operations on a mutably borrowed value, which can end up borrowing the root across the get and set, but these types always have a nonmutating set and so the root access is always instantaneous (or discontiguous, for get-modify-set-style writeback). Which you even said already. Sorry for the noise!

1 Like
13

At some point, we will probably need types analogous to Rust's *Cell family of types, which would serve a related purpose in allowing for storage rather than referencing of a value that can be modified outside of the static exclusivity rules. A safe, non-dynamically-tracked Cell's API would look similar to what's described here for similar reasons, requiring access to the value only through get and set, and disallowing sending among threads:

struct Cell<T: Copyable>: ~Copyable, ~Sendable {
  var value: T { borrowing get; borrowing set }
}

If we add the Cell storage type, then you can get the aliasable-reference behavior with Ref<Cell<T>> and Span<Cell<T>>, without introducing new dedicated span types. Perhaps the aliasable-reference case comes up often enough that those dedicated types are nicer enough to use to pay for the redundancy, and the non-mutable AliasedSpan/AliasedRef can, like C const*, provide some advisory hinting as to whether a reference should be written through or not.

7 Likes
14

Thanks Doug. This is a large addition, so I'll probably have more comments later, but so far:

Is there a way to create an Aliased* from an AliasedMutable*?

AliasedMutableSpan's mutating methods are actually non-mutating, but most of MutableSpan's mutating members are not changing the shape of the MutableSpan either. I thought the superseding reason would be that in the Atomics proposal, we found that "var" means "participates in exclusivity checks" and we don't want that here, but this isn't referenced in the proposal here. Is that still accurate?

  @safe
  func withUnsafeBufferPointer<E: Error, Result: ~Copyable>(

I understand the argument that AliasedSpan.withUnsafeBufferPointer is "safe" because the unsafety belongs on the pointer you get in the closure, which already exists. For AliasedSpan.withUnsafeBytes, I don't think that the argument holds. In the following code:

var strings = ["a", "b", "c"]
let x = string.span.aliased.withUnsafeBytes {
    let bytes = unsafe $0.bytes
    return bytes.load(atByteOffset: 0, as: Int.self)
}

I believe it's understood that UnsafeRawBufferPointer.bytes is safe under the assumption that you don't escape the original pointer and promise no mutable aliases. We don't need to be concerned with whether the buffer pointer was created over a range of CopyableFromRawBytes elements because that's the problem of whoever created the unsafe raw buffer pointer: it's the last chance the author had to verify this is OK, and that piece of code should be flagged as needing extra scrutiny. However, the piece of code which does that is withUnsafeBytes, and it is @safe.

I'm not sure if/how this is applied to spans and other types already. Unless I missed something, the rules for whether it's OK that these functions is @safe were never discussed.

I am pretty sure it's a pitch oversight that AliasedMutableSpan's unchecked subscript is not @unsafe:

extension AliasedMutableSpan {
  subscript(_ position: Index) -> Element { 
    get 
    nonmutating set 
  }
  subscript(unchecked position: Index) -> Element {
    get
    nonmutating set
  }
}

As noted in the Proposed Solution section, the subscripts for AliasedSpan use get accessors rather than borrow accessors to force the caller to copy the result.

This is correct, but I think it's missing some discussion: my understanding is that a copying accessor does not require a copy, it only requires that the result is semantically equivalent to a copy after the compiler is done optimizing. This raises several questions for me:

  • If the optimizer sees two consecutive loads of the same index, can they be combined? I think the answer is: probably? Aliased* appear intended to be memory-safe in the face of race conditions, which does not require ordering memory accesses on multiple threads in any specific way (which is fine for Aliased* since Sendable conformance is gated behind FullyInhabited–also, side note, that's pretty neat).
  • If the optimizer sees two adjacent accesses, can it combine them into one? I think the answer is "yes", again because Aliased* doesn't try to order memory accesses in any specific way and it also doesn't try to be the right type for MMIO regions. (This is a little hypothetical at this time because my experience is that LLVM is unable to do that.)
  • If the optimizer needs to stash a value it loaded from an Aliased*, instead of spilling to the stack and reload from there, can it choose to reload from the Aliased*? It definitely cannot.

I'd like to make sure this has been considered and the parts where we put hard "cannot" constraints are verified to generate code that will never lead to these outcomes.

15

This is correct, but it's worth noting that we will likely introduce volatile operations on Aliased* at some point in the future, and for those operations the answer to this question would be "no".

1 Like
16

I don't necessarily disagree with you, however this does feel similar to the guidance we originally received about typed throws. Originally, we thought that it would only be used in specialized circumstances where you need it, but since it's become increasingly problematic when library authors don't use it because every client that needs it hits that source of friction without any reasonable way to resolve it. I'm still a little wary we'll end up in the sam situation here, especially for core libraries like Foundation.

Sounds good, thanks - I think having clear documentation would help here (if we can come up with an agreed upon, consistent answer :sweat_smile: )

1 Like
17

The composability of this solution is appealing! Let's try to suss out where the major differences would be:

  • Access to a particular value in a Span<Cell<T>> will be something like span[i].value, which is annoying but not that bad. We might end up adding some API to the Span and Ref family of types to make a Span<Cell<T>> behave more like a Span<T>, although that might end up being some dicey overloading.

  • AliasedRawSpan doesn't have a counterpart; the closest thing is Span<Cell<UInt8>>. Ditto for AliasedMutableRawSpan. This introduces a little weirdness for C interoperability and void *.

  • MutableSpan<Cell<T>> is more restricted than AliasedMutableSpan<T>, because it is noncopyable. That might be fine.

  • We could make this Cell<T> type Sendable when the T is both Sendable and FullyInhabited, which matches the model in my proposal.

  • We have to go think about whether this composition actually gets the right semantics on access. We will have borrows of Cell<T> instances from a Ref or Span that don't follow exclusivity, and we're fixing that up by not providing physical access to the storage inside them. I don't know if that's good enough or whether we'll need to invent an annotation to go on Cell to make that work.

  • Volatile<T> follows naturally if this does work, which is nice.

    Doug

3 Likes
18

From the composability angle, I wonder if we could have a protocol over Cell, Volatile, and similar semantic wrappers over their respective value properties. That would then allow Span and Ref over these wrapper types to behave more transparently over all of them. (I was about to throw Atomic in there too, though Atomic brings additional complications with ordering that are best left explicit IMO.)

That's a good point. Span<Cell<UInt8>> could morally serve as the basis of an AliasedMutableRawSpan, since that's basically saying that you have a reference to a slab of independently arbitrarily-mutable bytes, but the natural API surface is sufficiently different that perhaps the Aliased*RawSpans still make sense as their own types wrapping it.

Cell is like Atomic in that it allows for mutation without exclusive access, so Span<Cell<T>> is already effectively AliasedMutableSpan<T>, and you wouldn't need MutableSpan<Cell<T>> except to indicate that you (temporarily perhaps) have exclusive access to the Cell. That exclusive access could be useful in some situations because you could take advantage of it to safely turn a MutableSpan<Cell<T>> into a MutableSpan<T> and perform non-instantaneous accesses on the memory, or use it as a Sendable value within the exclusivity scope.

Cell's implementation should be able to use the same underlying mechanism we used for Atomic to allocate inline storage with minimal presupposed semantics imposed on it. In Rust land, all of these things are built on top of an UnsafeCell<T> type, which allocates inline storage that's opaque to the compiler but leaves it to the developer to hold it right by not exposing overlapping borrows that violate exclusivity. Atomic does this by only exposing access to the memory through atomic intrinsics that are well-defined in the face of concurrent access, and the safe Cell<T> does it by gating access to the storage through only full-value-copying get/set operations on a single thread.

4 Likes
19

It seems potentially problematic to me that instead of having attributes or modifiers of a smaller number of types, we have an increasingly large number of very specific types that, only by name, essentially modify less specific ones („stringly typed“ in a more abstract sense).

This is like NSMutableArray vs NSArray etc - but there they were „at least“ subclasses of one another.

It seems like we’re heading towards a direction where library authors will have to think very long and hard about what kind of currency types they accept, rather than the dream of protocol-oriented generic programming as we were initially sold on.

6 Likes