Law of Exclusivity/memory safety question

Yes, I have no doubt; and those copies are exactly the ones I mentioned as a concern in the post opening this thread. I'm trying to get a handle on whether we have any reason for the compiler to actually (not theoretically) make those copies, and whether we can reasonably lock down that behavior if not.

In addition I believe the copies/moves @Andrew_Trick sees are those to/from registers.

Of course, I have already stated I'm not sure because I don't see any in the code I posted, but I assume by “source-level” copy, he means a copy that is visible in the source, e.g. as pass-by-value to a call, return-by-value, or as an assignment. That interpretation is supported by this quote:

I do want to point out that we have publicly stated that the inout-to-pointer conversion for a module-scope variable will always produce the same address. I can't remember if we've made the same guarantee about static variables, and we've (Apple Swift people have) explicitly said it's not a safe assumption for class instance variables (even known-stored ones), locals, or struct stored properties (relative to the base value, which will be one of the other things mentioned). I don't actually know if anyone's asked about inout yet!

A trivial case where it would happen for self is if self is passed in registers, which would be a valid implementation strategy for mutating functions (but not one the compiler currently uses, as far as I know). In that case it seems plausible for the compiler to put self on the stack for the inout-to-pointer conversion, then take it back off afterwards, and not necessarily use the same slot next time.


But this thread isn't exactly asking about the current behavior; it's about the "language" making more guarantees. It is a trade-off to insist inout parameters have stable addresses because that's (potentially) something that applies all the way down a call stack—it would rule out pass-in/pass-out (or callee-preserved-register-based) inout ABIs. We may not care, though.

I do want to note that "inout parameters have stable addresses" does not automatically imply that "stored properties of inout parameters or var locals have stable address". Both seem useful and potentially necessary for the guarantees Dave wants. (Is that correct?)

That would also pretty much only leaves (known-stored) class instance variables as "storage without a stable address guarantee". Is there a benefit to that exception?

2 Likes

OK, fair enough; I keep forgetting that ABI lockdown only applies to Apple platforms, and only outside the OS. It's reasonable to think that an inout Int would be passed by copy-out/copy-back in some future ABI. You don't even need to involve registers for that to happen, although without them it wouldn't be a very good optimization. For those following along, I wasn't worried about registers in the sense that @Dante-Broggi mentioned because IIUC the current ABIs pass all inouts by pointer, and things only get promoted to registers as an optimization where all the code is visible, leaving the compiler in a position to make the guarantee I was asking for.

But this thread isn't exactly asking about the current behavior; it's about the "language" making more guarantees. It is a trade-off to insist inout parameters have stable addresses because that's (potentially) something that applies all the way down a call stack—it would rule out pass-in/pass-out (or callee-preserved-register-based) inout ABIs. We may not care, though.

I do want to note that " inout parameters have stable addresses" does not automatically imply that "stored properties of inout parameters or var locals have stable address". Both seem useful and potentially necessary for the guarantees Dave wants. (Is that correct?)

I think so? I guess I should soften my earlier statement a little—I shouldn't prematurely insist that we need the compiler to act the way people expect C to act. We'll know better exactly what kinds of guarantees are needed once we get more experience with move-only types and C++ interop. I feel a bit more strongly, though, that asking programmers to routinely invert control using a coroutine, just to get a stable address, is probably not a tenable programming model.

3 Likes

I think we could guarantee "no user-visible implicit copies" of inouts. I'm worried that we have a different definition of implicit copies. This isn't relevant for correctness, but I see two explicit copies of the key-value pair in one statement from your code:

var (p, kv) = unsafeMoveMap(destroying: &self) { $0.tuple }

Unless I'm mistaken the .tuple getter returns a copy of the newly constructed tuple, and assignment into kv copies that tuple into an lvalue.

The "proper" way to acquire a stable pointer in Swift is the way that the language was designed to support from the outset, has simple well-defined rules, has been consistently communicated to developers and can be enforced by the compiler in most cases.

I'm not defending the programming model; improvements to that are welcome. Let's just be clear that adding conditions for address stability complicates the language, add allowing pointers to escape their scope under those specific conditions makes it significantly more difficult to diagnose undefined behavior. That has to be a worthwhile tradeoff.

3 Likes

It's a start. I don't think it's enough, though:

  • We need to cover moves, or the compiler could expect to implicitly move it from deinitialized memory after I've already deinitialized it by explicitly moving from it.
  • Even outlawing “user visible” implicit copies and moves isn't enough, because that only requires the compiler to present a temporary copy at the same address each time the address is taken, but again doesn't prevent the compiler from treating that memory as initialized after I've explicitly moved from it.
  • “User visible” somewhat begs the question because it depends what you're allowed to observe and what you're allowed to assume it means. Is converting &x to an UnsafePointer “observing the address of x?” I don't think we've established that.

I'm worried that we have a different definition of implicit copies. This isn't relevant for correctness, but I see two explicit copies of the key-value pair in one statement from your code:

var (p, kv) = unsafeMoveMap(destroying: &self) { $0.tuple }

Unless I'm mistaken the .tuple getter returns a copy of the newly constructed tuple, and assignment into kv copies that tuple into an lvalue.

I sure hope that those are moves at worst; ideally they'd be eliminated by mandatory RVO. Regardless, if they are moves or even copies, I agree that they are explicit, i.e. visible in the source. I assume that's what you mean by source-level?

The "proper" way to acquire a stable pointer in Swift is the way that the language was designed to support from the outset, has simple well-defined rules, has been consistently communicated to developers and can be enforced by the compiler in most cases .

Sure. Neither of these hypothetical and unimplemented approaches was in the language design from the outset nor have they been communicated to developers. I don't see how one can be considered more “proper.”

I'm not defending the programming model; improvements to that are welcome. Let's just be clear that adding conditions for address stability complicates the language,

It complicates the technical definition of the language (which I'll note we don't have). It simplifies the mental model for users.

add allowing pointers to escape their scope under those specific conditions makes it significantly more difficult to diagnose undefined behavior. That has to be a worthwhile tradeoff.

OK, so nothing prevents pointers from escaping their guaranteed scope of validity today and being stored in globals, which I would think already demands a fairly complex dynamic system to diagnose UB without false positives. How would extending the scope of validity for some pointers make the job harder?

withUnsafePointer doesn't just produce a pointer; it also bounds the time when that accesses can be made through that pointer. Making the code you've written work would in general require the implementation to be maximally conservative about memory analysis for any variable whose address might be taken and escaped as a pointer, which essentially means any variable with any abstract uses at all. That is essentially the world that C and C++ compilers have always lived in, but Swift aims to do better.

The fact that withUnsafePointer and other closure-based scoping APIs don't compose reasonably with features like yield is a problem that demands a general solution. We should not sacrifice basic goals of the system to work around it in the short term.

5 Likes

Thanks, John. I understand the principles you're going for here and they make sense.

About the specifics, though, I have some questions. Can you clarify what you mean by “memory analysis?” When you say “the implementation” are you talking about the regular compiler or a special purpose UB detector? Also, what's an “abstract use?”

Any optimization or analysis that tries to reason about what's currently stored in a memory location. For example:

  store %value to %location
  apply %functionWithUnknownSideEffects()
  %load = load %location     // Is this always the same as %value?

or

  %load1 = load %location
  apply %functionWithUnknownSideEffects()
  %load2 = load %location     // Is this always the same as %load1?

I primarily mean the compiler. We do not want the compiler to be forced to treat all abstract uses as "escapes" through which memory can be accessed later.

A use that isn't concrete. :) It's any use that we can't fully reason about. For example, if a variable is passed inout to a call, we can't in general know exactly how it'll be used there — maybe it'll be read, maybe it'll be assigned to, maybe it'll be completely ignored. That does block the optimizer some. But we do know that it won't be "escaped", such that we'd have to worry that arbitrary code long after the call might still be accessing the variable. In C and C++, you do have to worry about that — and since C++ relies heavily on abstraction, and it's common to pass things by reference (especially with this, but also just const & / && arguments), this can be a significant optimization problem for C++ code.

7 Likes

Continuing the discussion from Law of Exclusivity/memory safety question:

I was using "source-level copy" and "explicit copy" interchangeably.

Yes, I think it's reasonable to consider expressions source-level moves, not copies, as long the expression only produces and consumes rvalues, but I'm not the expert. In particular, passing an rvalue to an owned call argument could always considered be a move.

So, we can say there are no source-level copies here, only one move:

func bar(x: __owned AnyObject)

bar(foo()) // move

While there is one source-level copy here:

var x = foo() // move
bar(x)        // copy

And one source-level copy here:

func bar(x: __owned AnyObject) {
  bar(x)      // copy
}

I'm sure we'll also want some guaranteed level of copy elimination by the optimizer under certain conditions, which we haven't specified yet. Then we could rely on elimination of lvalue copies in the two cases above:

var x = foo() // move
bar(x)        // optimized move
// x never escapes or has its address taken

and

func bar(x: __owned AnyObject) {
  bar(x)      // optimized move
}

These optimizations should even be mandatory (-Onone), but it's a bit tricky because we currently preserve debug markers after the last use.

In addition to source-level moves and copies, the compiler is allowed to implicitly move or copy values. Those implicit move/copies may be user visible in at least two ways

  • address stability (via pointer operations)

  • CoW storage copies (performance)

We should eventually specify conditions under which those effects cannot be observed. For example, we might decide that inout argument's address is stable for the duration of the argument scope. That would then limit the compiler's ability to optimize inout argument passing via registers for non-ABI methods, as @jrose mentioned. The compiler would first need to prove that the inout argument's address is never observed.

As a counter-example of something we are not likely to restrict, taking the address of the same variable at different program points will not be guaranteed to produce the same address:

var t = ...
modifiesT(&t) // may observe an object at address A
modifiesT(&t) // may observe an object at address B

or

var t = ...
withUnsafePointer(to: &t) { ... } // may observe address A
withUnsafePointer(to: &t) { ... } // may observe address B

@jrose pointed out the exception for module-scoped variables. It's unlikely we would make an exception for generically types local variables. This is where special type restrictions or programmer annotations could be a useful tool.

What about CoW storage copies? I mentioned above that we could evertually guarantee no compiler-generated (implicit) copies and guarantee some forms of copy optimization. But this won't be something we do in general for arbitrary variables that have generic copyable types (the default unconstrained generic type). When a variable neither escapes, nor has its address taken, the compiler only models the values that the variable refers to--it immediately throws away the lvalue information:

var t: T = foo()
if (z) {
  t = b      // source-level copy
}
use(t)

If z is true, then t = b is a source-level copy. But if z is false, we still can't guarantee that t won't be copied. The compiler's representation looks more like this:

use(z ? foo() : b)

The compiler will eventually need to generate a temporary, requiring an implicit copy. The compiler has lost information about where the source-level copies were, so it is difficult to make an absolute guarantee about implicit copies of copyable types.

For non-copyable types, the compiler's internal representation will be able to guarantee no copies through all stages of compilation. As before, we could add other type restrictions or programmer annotations to either prevent or diagnose unwanted copies.

You are using coroutines as a mechanism to avoid CoW copies, running into the fact that they're only partially designed, working around that by a escaping pointer from the its well-defined scope, then deciding that you need some language guarantees to legitimize your horrible hack. The link between address stability and your original problem is tenuous.

There are two uncontroversial language features that directly solve your problems and have nothing to do with address stability:

  • generalized coroutines

  • the move operator

That said, I agree it would be helpful to specify the conditions under which implicit moves/copies cannot be observed, in addition to specifying the conditions for guaranteed copy optimization. I just don't know that it's an easier problem than adding the above language features. First, there's no going back from any restrictions we put in place. And it's not good enough to declare some rules for the compiler without a robust representation, underlying mechanisms, and verification to support those guarantees--no one knows everything that goes on in the compiler, and it changes all the time. We could declare the intention to follow some rules and gradually work toward that.

7 Likes

Of course we agree on that! I guess I thought that bounding the valid lifetime of the pointee to the lifetime of the root inout access to it would be limited enough.

So that just means “a use the details of which aren't visible to the compiler at the use site?” I'm sure you've been using “abstract” that way since the beginning but I guess it never sank in for me :stuck_out_tongue_winking_eye:

Starting from the middle…

Whew! Unsparing, but I have to admit that's totally fair. Okay, I'll stop pursuing those guarantees and start thinking about how to integrate coroutines with the rest of the language; it's a problem I'm going to need to solve anyway…

Check.

For completeness: I guess that passing any value to a guaranteed call parameter is a copy iff the value is a [stored property of] a class instance or a global?

I'd only expect those last two to copy if there's another use of x after the call to bar. I see you're treating that as an optimization, below.

I'm pretty sure any use of x after the call to bar, regardless of whether x escapes, guarantees that there's a copy of x for the call to bar, no?

These optimizations should even be mandatory (-Onone)

Yesplease. Whether to think of them as optimizations or just as “how codegen works” as I did is admittedly above my pay grade, but it occurred to me that because of DI we already do analysis somewhat like this before the optimizer kicks in and it might make a big difference to what I think of as “real optimization” passes to have it sorted out.

but it's a bit tricky because we currently preserve debug markers after the last use.

Forgive my utter ignorance, but what's a debug marker?

Yep. Just so long as they're not the conditions I was asking for :wink:

That… was exactly what I was asking for I think?
:thinking:

As a counter-example of something we are not likely to restrict, taking the address of the same variable at different program points will not be guaranteed to produce the same address:

I… think I wasn't asking for that.

I'd like that to depend on whether b might be accessed after the last line. There's not enough context to tell from this code, but I'll assume it's a global for the purposes of this discussion; that would force it to be a copy.

But if z is false, we still can't guarantee that t won't be copied.

Again, context is missing, so I can't tell, but it seems obvious that t will be copied if it is used after the last line and use takes its parameter as __owned.

Sorry, I must be missing something. Why can't it be a move?

The compiler has lost information about where the source-level copies were, so it is difficult to make an absolute guarantee about implicit copies of copyable types.

I don't think we should make guarantees in terms of a relationship to source-level copies; all we need to do is expose the rules by which we determine that a copy may be needed. I guess this is part of why I don't want to think of moving from the point of last use as an optimization.

Remember that I've let go of address stability in the general case; this means the compiler can implicitly move all it wants.

For non-copyable types, the compiler's internal representation will be able to guarantee no copies through all stages of compilation. As before, we could add other type restrictions or programmer annotations to either prevent or diagnose unwanted copies.

Sure, we could. The programmer will already have lots of explicit control: they can make the type move-only and add copy() method. IMO it would be a terrible shame if we can't guarantee minimal copying behaviors for ordinary copyable types like Array.

Well, I hope they solve my problems, and in the case of move, I'm in a position to make sure it does. I can't say I know enough about what “generalized coroutines” means yet to see that it definitely provides a good answer.

I agree it would be helpful to specify the conditions under which implicit moves/copies cannot be observed, in addition to specifying the conditions for guaranteed copy optimization. I just don't know that it's an easier problem than adding the above language features.

I think observability of move is much more of an expert-level concern than observability of copy, and while it's obviously going to be important to have a way to achieve address stability across a yield, I'm not nearly as worried about making that sort of thing ergonomic.

First, there's no going back from any restrictions we put in place. And it's not good enough to declare some rules for the compiler without a robust representation, underlying mechanisms, and verification to support those guarantees--no one knows everything that goes on in the compiler, and it changes all the time. We could declare the intention to follow some rules and gradually work toward that.

Super. I realize none of this stuff can be achieved in a day. Thanks for taking the time to discuss it.

1 Like

The idea I've been noodling with for how to make these scoped operations compose better is to introduce a feature targeted for them, which I would call a using func, designed to work in tandem with a using statement at the use site.

So you could declare something like this:

extension Array {
  // This is a yield-once coroutine, like read/modify.
  // Given the opportunity, I think we'd use a slightly different ABI for it, though.
  mutating using func unsafeMutableBuffer() -> UnsafeMutableBufferPointer<Element> {
    yield ...
  }
}

and then use it like this:

extension Array {
  mutable func fidgetInPlace() {
    using buffer = self.unsafeMutableBuffer()

    // The coroutine call to unsafeMutableBuffer() doesn't complete
    // until `buffer` goes out of scope (which also means that `self`
    // is being accessed exclusively for all that time)
  }
}

Issues that come to mind:

  • It would make more sense for unsafeMutableBuffer to be a property. That would mean we'd have to have using vars and using subscripts, though. Would they have to be read-only? using statements as described above don't communicate whether the access is supposed to be a mutation or not.

  • It would be nice to use the results of using funcs directly in expressions. There's a natural "scope" to something like a call argument, where the using func would complete immediately after the call. Does that generalize acceptably? Is it too prone to creating dangling uses of the value in practice?

  • Should using statements force (or allow) the access to be explicitly scoped, like

    using x = foo {
      body(x)
    }
    

    In the braceless approach, to explicitly scope the using you'd have to wrap it in a do {} block.

    For what it's worth, the ownership manifesto suggests having some sort of endScope directive that can end the scope of any declaration. (In the manifesto, this is used to immediately end local "ephemeral" bindings like borrow and inout; using would be another, similar need.)

2 Likes

Have you thought about using with? Consider:

with inout x = valueWithAccessor {
  ... do stuff ...
} // inout ends here.

Just reads nicely to me. I think about it like an if statement without a condition check just a bind.

Also, one thing that I do not understand is why in your example do you need to mark the function with using as well? In my mind with 'inout', 'borrow', 'let' and a using/with we would never need to mark the function since we could bind /any/ value, no?

How is that not just a regular var/subscript?

seems like, syntactically,

let buffer: inout = self.unsafeMutableBuffer
...

Makes more sense as a way to keep an inout access "active" beyond a single expression.

The UnsafeMutableBufferPointer that unsafeMutableBuffer produces is an r-value, not an l-value; you can't mutate the pointer itself. (But what you're describing is exactly the ephemeral inout binding from the ownership manifesto, except it was spelled with inout as an introducer there.)

As a keyword alternative to using? Yeah, I think that's viable.

We need some way to mark that this is semantically a coroutine that produces a value by yielding (and then later resuming) rather than simply returning. I suppose that if all these functions produced inout or borrowed values, we could have that be indicated purely by a marker in the type, but I think that would be rather subtle, and more importantly I don't think it's true that we want these functions to only be able to produce inout or borrowed values.

Oh, so this is like a value yield-ed from _read, except that the yield doesn't complete until the lifetime of buffer ends?

That's sort of reminiscent of the way C++ extends the lifetimes of temporaries bound to references (if you think of the yield continuation being run by the temporary's destructor).

It sounds like you're saying there should be a using marker in both the yielding code and the yielded-to code; is that right?

Well, you could yield something inout from one of these like _modify does, but you wouldn't have to, and unsafeMutableBuffer presumably wouldn't want to. So, yes, it would be quite like _read.

However, _read always yields a borrowed value, whereas this could yield an owned value. That doesn't make a difference for a trivial type like UnsafeMutableBufferPointer, of course, but it would affect performance for a non-trivial type, and (eventually) it would affect semantics for a move-only type.

The function has to be marked as special somehow, yeah. On the caller side, I feel that a local declaration that starts one of these scopes should be clear that there's something special about the scope, that it's not just a normal let. But maybe that doesn't have to be explicit if you scope the use within a single statement, like you just immediately pass the yielded value as an argument to a call (and therefore the coroutine call is scoped immediately around the call).

Okay, but notwithstanding what you say next…

That doesn't make a difference for a trivial type like UnsafeMutableBufferPointer , of course, but it would affect performance for a non-trivial type, and (eventually) it would affect semantics for a move-only type.

…I don't see a point in that. An owned value is what's returned by any ordinary call or property access, and if you want to give it a name and keep it alive during a scope you can use an ordinary let binding. I guess the difference would be that the yield-once coroutine effectively allows one to attach a cleanup (continuation) action for the scope of the owned value? Do you have a use-case for that—one that isn't better covered by the fact that move-only types will have destructors?

I was thinking of these things as properties and subscripts, which need no special markings to support a yield. I can imagine wanting function call syntax for yield-once accesses, but am not sure why functions would need a special marking if properties and subscripts don't.

Properties and subscript accessors do need a special marking in order to yield: you have to be defining one of the two special accessors that yield instead of returning. You cannot yield in an ordinary func or getter.

We really don't want to just make an unsafeBuffer property that's treated completely normally in the language. The scoping is critically important, and if it's an ordinary property — even if it's implemented with a coroutine accessor like _read or _modify — the language is not going to understand that it needs to be doing things within the scope, as opposed to just copying the value and exiting the coroutine as soon as possible.

Hmm. That's a fair point: since the goal of this feature would be to say that the value should only be used within the scope, it's not clear why it would ever be useful to provide an owned value that the program could move away and use later. Maybe the return should be implicitly borrowed if not inout.

2 Likes