Safe element ownership for lifetime-restricted buffer types

The Swift standard library currently provides some buffer types: UnsafeBufferPointer and so on. Other than being well-typed about the elements they store, these types are essentially completely unsafe: not only do they not represent ownership of the underlying memory, they also don't provide any static information about the ownership of the values stored in that memory; in fact, there might not even be any values in that memory because it could be totally uninitialized (or partially uninitialized! there are no restrictions). The user is completely in charge of not letting the code run off into the Land of Undefined Behavior.

A lot of the recent ownership work in Swift (e.g. SE-0366, SE-0377 and SE-0390) has been partially in service of enabling the creation of high-performance safe buffer types. As part of that, I was recently talking with the folks leading that effort (@Andrew_Trick in particular), and these notes kind of fell out of that conversation. I've cleaned them a little bit in an effort to organize my thoughts; I thought they'd be useful to put somewhere public.

I put this in the Standard Library category because it's really about principles of design around certain ownership features, although several of those ownership features are yet to be added to the core language.


Background

Lifetime-restricted types

First, this conversation is focused on "non-allocated" buffers, where the type does not represent ownership of the memory for the buffer itself. To be safe, these buffer values have be lifetime-restricted: there's some sort of definable scope that they aren't allow to escape. This is a new general feature that will need to be introduced to Swift, corresponding roughly to what Rust calls a lifetime-qualified type ('a qualifiers). It's a key idea of lifetime-restricted types that you can derive new values from them with strictly tighter scopes, and then we can assume that those values can no longer be used when those tighter scopes are complete.

For example, if inout was a first-class type in Swift, it would be lifetime-restricted: you can only ever form inout bindings to a particular variable temporarily. Given an inout struct value, you can form an inout binding to a property of that struct, and it's important for exclusivity that you cannot access the original struct during this time; this is a nested lifetime restriction coupled with a use restriction from exclusivity. When that binding goes out of scope, there are no further uses of it, and you can safely access the original struct again. Lifetime-restricted types allow us to apply this kind of logic to types in general, which as we'll see is an important tool for very specific situations like these buffers.

The working name for these non-allocated buffer types is buffer views. Types that represent owned-allocation buffers are also interesting, but they're a little bit easier to handle in some ways because of how tracking the buffer ownership narrows the range of possible designs. We also expect that algorithms working with buffers will generally want to be written using unallocated buffers so that they don't needlessly restrict where the buffer memory comes from.

Value ownership

Second, across the entire language, we can identify five kinds of value ownership that are useful to consider here:

  • uninitialized ownership represents that you've got access to some uninitialized memory and the right to use it for whatever purpose you'd like, as long as you leave it uninitialized when you're done. For example, if you allocate some memory, you naturally have uninitialized ownership of the contents of that memory: there are no values there at start, and when you go to deallocate it, there better not be any values left there or they'll be leaked. To be safe, uninitialized ownership needs to be exclusive because any effort to actually initialize and use part of the buffer needs to be exclusive.
  • initializing ownership represents an obligation to initialize memory with a value. For example, a function has initializing ownership of its return value. To be safe, this must be exclusive because overlapping attempts to initialize the same memory necessarily have UB (and will massively complicate any attempt to manage the ownership of the resulting values).
  • consuming ownership represents an obligation to consume a value, leaving the memory it's in uninitialized. For example, a function generally has consuming ownership of the contents of its local variables. To be safe, this must be exclusive because overlapping attempts to consume the same value necessarily have UB (unless the values are known to be trivial to destroy).
  • mutating ownership represents the opportunity to change a value. The memory can be temporarily left uninitialized, but it must be initialized again by the time that this ownership is given up. For example, a function has mutating ownership of its inout arguments; it can also acquire mutating ownership of a mutable stored property of a class or (if stored in mutable storage) a struct. To be safe, mutating ownership must be exclusive because overlapping accesses to the same memory necessarily have UB.
  • borrowing ownership represents the opportunity to use a value without changing it. The memory must be initialized when acquiring this ownership and cannot change in any way while having this ownership. For example, a function generally acquires only borrowing ownership of a stored property when it reads from it. Borrowing ownership has to be exclusive of any other kind of ownership, but multiple contexts can have borrowing ownership of the same value at once.

Several of these kinds of ownership are not normally exposed in Swift, which statically restricts the use of uninitialized memory in the interests of memory safety. However, a low-level buffer type pretty much has to expose them, because otherwise initialization would always need to be tied intimately to allocation.

Element status in buffer views

For buffer views to be safe, on top of enforcing lifetime restrictions on the buffer view value itself, we need to track two things about the elements:

  • which elements of the buffer are initialized
  • what ownership do we have of each initialized element

Now, we could have a single buffer view type that does this all dynamically. For example, we could have an operation that asks for mutating ownership of an element, and that operation could check some dynamic side-table to verify that the element is initialized and then do some dynamic exclusivity test to catch any overlapping attempts to the element. That would be pretty expensive, though: we'd have to actually allocate and initialize that side-table, as well as doing all of the dynamic bookkeeping for the exclusivity check. We'd really like both of those to be handled statically, and ideally they would be handled by the normal language rules and not require all sorts of type-specific logic in the compiler. To do that, we need the information we have about an individual buffer view to reliably inform us about the elements and, ultimately, guarantee that any operations on them following the appropriate ownership rules above.

Exclusivity of element operations

One of the most important pieces of that is exclusivity. The general ownership rules above tell us that most of the operations on elements need to be exclusive to be safe. In order to guarantee that without dynamic checks, we need a static precondition that these operations cannot be performed on the same element. The simple way to do that is to have those operations require exclusive access to a buffer view value and then prevent multiple usable buffer view values from referring to the same element simultaneously.

The first half of that means that all operations that initialize, mutate, or consume elements must be mutating or consuming operations on a buffer view. nonmutating methods on buffer views, or ordinary functions that borrow a buffer view as an argument, do not have exclusive access to the view and cannot be allowed to do these operations. This mostly means that the implementation needs to declare the primitive operations correctly as requiring the right kind of exclusivity; since the operations will probably be implemented with unsafe buffers behind the scenes, there won't be anything forcing this to be done properly, but it's vital for correctness.

The second half of that means we must be very careful to only create disjoint buffer views that these operations can be simultaneously performed on. For example, if we have an API that creates a slice of a mutable buffer view, we need to prevent use of the original buffer view for as long as that slice is usable. This could be done by making the API a mutating function that provides the slice to a callback and makes sure the slice is lifetime-restricted to the duration of that callback. Alternatively, we can allow the slice to be returned from a mutating method as long as we maintain enough structure to reflect its dependency on the original buffer view and maintain the read-write access to that view associated with the mutating method call for as long as the slice is usable. This latter idea comes with important caveats; see later in this post.

Initialization state

The simple way to handle the is-initialized bit is to make the initialization state a static precondition on a buffer type. That means that we at least need two different buffer view types, one for working with uninitialized buffers and one for working with initialized buffers.

The uninitialized buffer type will represent uninitialized ownership of the buffer, which means that it will be expected to leave the buffer fully uninitialized before its scope ends. So any operations on that type which create initialized sub-ranges will need to produce strictly lifetime-restricted buffer views for those ranges: we have to be done with them (and have destroyed all their elements) before we can be done with the original buffer. This type either needs to be non-copyable or we need to prevent any copies from being used simultaneously, which is essentially the same thing. It can have consuming operations, but only to produce new buffers that maintain the same uninitialized ownership of the elements, e.g. to split the buffer into non-overlapping slices.

If we want to make a safe version of APIs such as Array.init(unsafeUninitializedCapacity:initializingWith:), we will probably also want an initializing buffer view type that dynamically tracks the length of the initialized prefix. This would also need to be a non-copyable type, and unlike most of the other buffer view types, it can't support any consuming operations to slice it up — those would be incompatible with tracking the initialized prefix length and propagating it back to the original caller (e.g. Array.init).

Any other primary buffer view types would have a static precondition that all the elements in them are initialized.

Initialized views

There are two main ways we could design initialized buffer views. One would be to treat these views like simple aggregates of the elements:

  • if we have consuming ownership of the view, we have consuming ownership of the elements
  • if we have mutating ownership of the view, we have mutating ownership of the elements
  • if we have borrowing ownership of the view, we have borrowing ownership of the elements

If we did that, we'd only need a single initialized buffer view type. However, this would pretty severely restrict how you could work with views, especially immutable views. For example, you wouldn't be able to write a parser that to maintained a var remainingData: BufferView<UInt8> variable during the parse: this variable would represent consuming ownership of the entire buffer, and therefore the right to arbitrarily write to any element. Usually we want such a parser to accept the restriction of working with immutable data.

The other option is to separate the ownership of elements from the ownership of buffer views. They can't be completely separated, because we still need to use value ownership in order to establish exclusivity for the exclusive operations on elements, as discussed above. But we can encode the ownership of elements into the buffer view type name, so that we can have a high level of ownership of a buffer view value without implying a higher level of ownership of the elements. That means we need at least three types for initialized buffer views: one for consuming ownership of the elements, one for mutating ownership, and one for borrowing ownership.

The consuming buffer view type must be a non-copyable type with a deinit that destroys all of the elements in the view. Elements can be individually consumed with a consuming or mutating operation, leaving behind a view (if applicable) that no longer includes those elements. Similarly, new consuming buffer views can be sliced off with a consuming or mutating operation as long as this always creates disjoint views. If there are clients that require elements to be random-access consumed, that would require a new type that dynamically tracks which elements have already been destroyed; that overhead shouldn't be forced on all clients. It can also have operations to create mutating or borrowing buffer views.

The mutating buffer view type is like the uninitialized buffer view type in that it either needs to be non-copyable or we need some sort of novel restriction that prevents the original buffer view value from being used while the derived one is available, which is essentially tantamount to being non-copyable. It can have slicing operations to split it into disjoint mutating views, as well as operations to create mutating or borrowing views.

The borrowing buffer view type can be copyable as long as copies have the same lifetime restriction as the original.

Caveats on deriving buffer views

There are two API designs for deriving buffer views. One of them provides the derived views to a callback, which is very clear about the value dependency and likely nestedness of lifetime restrictions, but also has significant compositional problems and can lead to a "pyramid of doom". The alternative is to return the derived views, but this is problematic because the return value may still be dependent on the base value, depending on the derivation operation:

  • A borrowing buffer view can be copied, so it can also be sliced to create new borrowing buffer views without any limitations other than preserving the original lifetime restriction.
  • The non-borrowing buffer views can be consumed to produce one or more new buffer views without leaving any dependency on the original. The new buffer views must have the same lifetime restriction as the original view and must maintain compatible ownership of its elements. For example, a consuming buffer view cannot be consumed to produce a mutating buffer view because the obligation to destroy the elements would be lost. It would be okay to consume a mutating buffer view to produce a non-mutating buffer view, though, as long as the caller is comfortable with this being irrevocable.
  • Similarly, the non-borrowing buffer views can have mutating operations that produce slices as long as those slices have the same lifetime restriction, maintain compatible ownership of any elements they contain, and are disjoint from the (modified) original view.
  • Otherwise, the produced views must be exclusive with the original view for as long as they're still being used. For example, there can be a borrowing operation on a mutating buffer view to produce a borrowing buffer view, but the borrow of the mutating buffer view needs to last as long as the resulting view is alive.

This last point would require new basic language support in Swift where we recognize that certain function calls can return values that depend on self (or some other argument) and so extend the duration of any accesses associated with that argument to cover some scope relating to the return value. It seems reasonable to me to align this with the general rules for l-value access, which are well-established and reasonably predictable (if sometimes a little subtle). That would imply that, e.g., dependent return values passed as call arguments would have a lifetime scope associated with the exact duration of that call, just like an inout argument would, and any storage access associated with producing that return value would be extended to cover that exact scope. If the return value is used to initialize a local variable, the accesses would cover the scope of that variable. But this would have some strong inherent limits around things like conditionally-evaluated expressions (e.g. in an autoclosure or the ternary operator ? :) and non-immediate initialization, and for predictability we would probably apply those restrictions broadly instead of trying to "make it work" for cases that could theoretically be supported. For example, you would not be able to write:

  var buffer: BufferView<Int>
  buffer = myMutableBuffer.immutableView

because in the general case we would not be able to extend the duration of the access to myMutableBuffer to cover the full scope of buffer. (Consider that this assignment could be within an if or that there could be a defer that uses buffer between these two statements.)

21 Likes

It is my understanding that some use-cases for that array initializer involve placing elements into the buffer in a way that does not sequentially fill the buffer from beginning to end.

A trivial example would be initializing an array from a heap, but in reverse order so the buffer is filled from back to front.

A more complex example would be radix sort, which counts how many elements fall into each bucket, then places each element into the next open slot in its bucket. The buckets are subranges of the overall buffer, so that buffer gets filled in a non-sequential order. At the end, the buffer is fully initialized, but during the process there is no such thing as “the initialized prefix”.

Should use-cases like this be supported, and if so how?

1 Like

In the general case of that, you’d need a type that tracked a bitset of which elements were initialized and then asserted that you’d filled in a dense prefix. Really, though, I think you’d just fall back on an unsafe buffer type.

5 Likes

Why word "View" is used in BufferView ?
Is it a part of some User Interface ?

All the names here are placeholders. This post is really about the underlying ownership concepts, it’s not a detailed pitch (and I wouldn’t be the right person to pitch it anyway — I’m not driving any of this work).

1 Like

More generally, even though we want to reduce the reliance on "unsafe hatches", we are not removing them. Some of the cases you describe may still require unsafe code, but we hope to make it so that you need less unsafe code, more clearly circumscribed, and more easily auditable.

3 Likes

I don’t understand this example; why wouldn’t the parser just declare let remainingData: BufferView<UInt8>. Is it because the parser will need to take incrementally smaller slices? If so, could we combine existing syntax, e.g. var remainingData: borrowing BufferView<UInt8> to imply that only borrowing operations are allowed but the type itself can change?

Well, we could do that, but it’s not actually as small as you might think. The RHS of an assignment into that can’t start any new accesses and make them have the lifetime of the original variable we’re assigning into, so it would have to be derived directly from the current value or something like that. To allow that to even be expressed, we’d need to have a concept of a function that can return a borrowed value. And you’d have to do the assignment yourself every time, because we don’t have a concept of an inout (borrowing Self) parameter and probably don’t want to add one.

1 Like

Not sure if this is doable or helpful to consider in this discussion: could atomicity piggyback on the exclusivity?

I've recently tried to make a lock-free shared write/read buffer by encoding both slice/lease ranges in one UInt64 spin lock, but that still requires serializing memory access to the whole buffer (i.e., not just .relaxed ordering for the spin lock with lease state). So the goals of sharing arbitrary portions of the buffer seem to conflict with atomicity.

It would be nice if the initiation and destruction of your proposed buffer view/slice/range's could translate to serialized happens-before/after relationships for that view (perhaps assuming underlying value types), but I don't imagine the language semantics/lifetime bounds of these restricted buffers could be gated by something like a user-supplied spin-lock loop.

Perhaps more useful would be to wrap this use-case directly in an extended lifecycle, where completed mutating/producing views are passed to non-mutating consumers in a happens-before relationship, and similarly view elements are eligible for mutation after all consumer view lifecycles end.

Consumers can only get views shaped by producers, and a producer can only claim elements after all consumers complete, so the scheme has limitations, but they're not fatal. The implementation could spin or it might have to lock, depending on the size of the metadata for the buffer views, but only on the metadata instead of the whole buffer.

Could language exclusivity make concurrency work here without a buffer-wide lock because we know when readers/writers are no longer operating?

Exclusivity is only defined and enforced within a single thread. (It's a common misconception to think otherwise.) Exclusivity can play a role in preventing a mutable object from being shared across threads. But if you do need to share a mutable object across threads, then you need to abandon exclusivity and use concurrency primitives to establish happens-before.

That isn’t quite how I’d put it. Exclusivity is a language rule that always applies, including across threads. There are some cases where the language can statically ensure that the program follows exclusivity; in other cases, such as mutable global variables, mutable class properties, and unsafe pointers, it is not feasible to check exclusivity statically, but the programmer is still responsible for following it.

Swift makes a best-effort attempt to dynamically check that the programmer is doing that correctly for all of the non-unsafe-pointer cases. That dynamic checking doesn’t work across threads (unless you’re using Thread Sanitizer, I think). But that doesn’t mean exclusivity doesn’t apply across threads, it means that the compiler does incomplete checking for pragmatic reasons.

A program that correctly isolates all mutable memory (with Sendable checking) should have exclusivity fully enforced either statically or dynamically except for unsafe pointers.

1 Like

With that said:

This should be feasible soon, but it doesn’t come directly from exclusivity.

If this were an ordinary data structure, both reads and writes would require exclusive access to it: a “read” is actually a mutating operation because it slides the read window forward. You can’t have a producer and a consumer operating on the same ordinary structure at once without violating exclusivity.

With that said, it is possible in general to make a lock-free concurrent buffer, and we want them to be expressible in Swift. The way I expect lock-free atomics to be surfaced in Swift is as special types where all the operations are non-exclusive, even atomic modifications. It would therefore not be an exclusivity violation to do multiple such operations on them concurrently. For a concurrent channel, you would use such a type internally; your external API would be two “endpoint” types, one for producers and one for consumers. If you make those endpoints non-copyable, you can be assured that you won’t have multiple contexts with separate copies of the same endpoint. If you then make the produce/consume operations on the endpoints mutating, normal exclusivity will guarantee that only one produce or consume call can be happening at once, which should let you use a very efficient lock-free algorithm.

Regardless, that kind of concurrent buffer is necessarily a very different structure from what we’re talking about here.

1 Like

Yes, it's good to clarify that programs can bypass Sendable checking and be race-free, but still have undefined behavior because they violate exclusivity. The point is that exclusivity doesn't provide any safety across threads so isn't helpful as an implementation short-cut.

1 Like