From: Ralf Jung <post@ralfj.de>
Date: Tue, 18 Jul 2017 20:34:32 +0000 (-0700)
Subject: refactor: reorder examples and validation sections
X-Git-Url: https://git.ralfj.de/web.git/commitdiff_plain/78aa53554dc5c4be58333e9481e28c5f09c6a9fc

refactor: reorder examples and validation sections
---

diff --git a/personal/_posts/2017-07-17-types-as-contracts.md b/personal/_posts/2017-07-17-types-as-contracts.md
index 4d791f2..1227641 100644
--- a/personal/_posts/2017-07-17-types-as-contracts.md
+++ b/personal/_posts/2017-07-17-types-as-contracts.md
@@ -89,8 +89,9 @@ The reason I am giving concrete types here is just to make the specification mor
 When a lock is acquired, we record which stack frame is the owner of this lock (starting at 0 for `main`, and counting up).
 Now, on every read access, we check whether there is a write lock of this location held *by another function*.
 If yes, the access is UB.
-Furthermore, write accesses and acquiring a write lock are UB if there is a read lock held *or* if there is a write lock held by another function.
-Finally, acquiring a read lock is UB if there is a write lock held by anyone, including the function requesting a read lock.
+Furthermore, write accesses are UB if there is a read lock held *or* if there is a write lock held by another function.
+Finally, acquiring a lock makes sure that the new lock is not in conflict with existing locks:
+Acquiring a read lock is UB if there is a write lock held by anyone, including the function requesting a read lock; and acquiring a write lock is UB is there is any lock held by anyone.
 
 Locks are typically released automatically when they expire.
 To this end, the function acquiring a lock can optionally specify the *lifetime* of the lock.
@@ -106,62 +107,13 @@ This means the lock is temporarily released, but meant to be reacquired later.
 To this end, the `LockInfo` is removed from the location's `locks` and put into a `HashMap<Lifetime, (Location, LockInfo)>` which is stored somewhere separately from the program's memory.
 When the `EndRegion` corresponding to the given lifetime is reached, the lock is reacquired and put back into the `locks` of the given location.
 
-### 2.2 Validation
+### 2.2 Examples
 
-With the lock mechanism established, we can now look at the core of the proposal:  Validating the contract described by a type.
-This is done by a new MIR statement, `Validate`, which takes two arguments:  An *operation* (which we will discuss shortly), and a list of `(Lvalue, Ty)` pairs defining which lvalues is supposed to be validated at which type.
-Crucially, this is a non-erased type -- all the lifetime information must be present.
-
-The most important validation operation is *acquire validation*.
-As the name indicates, this is about acquiring the appropriate locks.
-It also otherwise makes sure that values are valid at the given type, e.g., references have to be non-NULL and aligned.
-
-The core of acquire validation is an operation with a signature roughly like this:
-{% highlight rust %}
-fn acquire_validate(lval: Lvalue, ty: Ty, mutbl: Mutability, lft: Option<Lifetime>)
-{% endhighlight %}
-Why are mutability and lifetime showing up here?
-The reason is that reference types have a "transitive" effect down the type hierarchy: `&T` makes everything reachable through this reference read-only, even if `T` involves `&mut`.
-Similarly, in case of nested references, it is the *outermost* reference that defines the lifetime for which access through this pointer is granted.
-(The compiler makes sure that inner references always have longer lifetimes than outer references.)
-
-`acquire_validate` recursively traverses the type hierarchy.
-When it encounters a primitive type like `i32`, it acquires a lock of `size_of::<ty>` many locations starting at `lval` for lifetime `lft` -- this will be a write or read lock depending on whether `mutbl` says this data is mutable or not.[^2]
-In other words, memory is locked "at the leaves" of the type structure, rather than locking immediately when we see a reference type.
-We will come back later to why this is necessary.
-Validation also makes sure that the value stored in memory is valid at the given type.
-For a `u32`, this just amounts to checking that the memory is properly initialized.
-
-[^2]: For simplicity, we pretend lvalues are just locations in memory.  Actually, lvalues can also refer to variables not in memory (like non-addressable stack locals), but these do not need to be locked.  Furthermore, lvalues for unsized types carry the additional information stored in a fat pointer, i.e., a length (for slices) or a vtable (for trait objects); this is handled appropriately when validating the respective types.
-
-For compound types like tuples, `struct` or `enum`, validation proceeds recursively on the fields.
-In particular, the enum discriminant is checked to be in-range (in particular, this empty enums always invalid).
-However, because the recursive validation will only lock memory that's actually covered by a field, we also have to acquire the appropriate lock for padding bytes and the enum discriminant here.
-
-Finally, at a reference type, two things happen.
-First, the reference itself is stored in memory somewhere; this memory has to be locked just like the validation of `i32` locks the memory used to store the integer.
-The reference is also checked to be non-NULL and properly aligned for the type it points to.
-Furthermore, validation proceeds recursively after *dereferencing* the reference.
-Crucially, the `mutbl` and `lft` for this recursive call are taking the reference type into account:
-If `lft` was `None` and this reference's lifetime ends within the function (i.e., there is a corresponding `EndRegion` somewhere), it is now set to the reference's lifetime.
-If `mutbl` was mutable, it becomes immutable when following a shared reference.
-
-There are two other validation operations besides acquire validation: release validation, and suspend validation.
-These serve to release the appropriate locks before handing references to foreign code, and to handle the operation of taking a reference.
-(Bear with me for just a little longer, we will see examples of this soon.)
-Suspend validation takes an additional parameter, namely the lifetime for which locks are to be suspended.
-Both operations recursively follow the type just like acquire validation, and for all memory they visit, they release/suspend *write* locks.
-Read locks are not touched, which corresponds to the fact that shared references are `Copy` and hence never "given up":
-Shared references always remain usable until their lifetime expires, at which point the read lock is released automatically.
-
-Validation statements are emitted during MIR construction in the following places:
-- At the beginning of the function, we perform acquire validation of the arguments.
-- When taking a reference, we suspend the referee for the reference lifetime and acquire the referent.
-- When calling another function, we release the arguments and acquire the return value.
-
-### 2.3 Examples
-
-After all this rather dry theory, let us look at some examples demonstrating how validation works, and how it enables optimizations.
+With the lock mechanism established, we can now perform type validation in MIR.
+To this end, we add a new `Validate` statement to the language.
+This statement takes a list of `(Lvalue, Ty)` pairs to be validated, and a *validation operation*.
+The operation can be *acquire*, *suspend (for a lifetime)* or *release*, indicating whether memory locks are acquired, suspended, or released.
+Before explaining type validation in general, let us look at some examples.
 
 #### Validating function arguments
 
@@ -180,12 +132,11 @@ Let us now see what happens when `x` and `y` alias.
 I mentioned above that we want this case to be UB, because we want to be able to reorder the two stores.
 Indeed, it will turn out that the validation describes above triggers UB here.
 
-There are no references taken and no other function is called, so the only validation that happens is acquiring the arguments at the beginning of the function.
-This validates our contract with the caller.
-`x` is of reference type, so validation will first acquire the write lock for the memory used to store `x` itself (that's somewhere on the stack).
-Next, it will follow the reference and recursively validate whatever `*x` is valid at type `i32`.
-In the recursive call, the `lft` will still be `None` because the lifetime of the reference outlives the function call.
+We perform acquire validation of the arguments immediately after a function is called.
+This validates the function's contract with the caller.
+`x` is of reference type, so validation will follow the reference and recursively validate whatever `*x` is valid at type `i32`.
 The recursive call then acquires the write lock for `*x` and checks that memory is initialized.
+The lock is acquired for the entire duration of the function call, based on the fact that the lifetime of the reference outlives the function.
 This completes validating `x`.
 Validation of `y` proceeds exactly the same way.
 In particular, validation will acquire a write lock for `*y`.
@@ -220,10 +171,11 @@ And indeed, the validation rules make it so that it is UB for `fun` to access `y
 Furthermore, we want to eliminate the load from `x` at the end, and instead re-use `x_val`, arguing that since `x` is a shared reference, it is UB for `nop` to change its value.
 
 In the beginning of `example`, during acquire validation, we acquire the read lock for `*x` and the write lock for `*y` and `*z`.
-The release validation before calling `fun` releases all write locks covered by `x` and `z`.
-For `x`, this doesn't actually do anything, but the write lock on `z` is released here.
+When we pass a mutable reference to `fun`, we explicitly acknowledge that `fun` has the right to modify this memory.
+This means that we have to *release* any write locks that we may hold on `x` or `z`, which is done by performing release validation on all function arguments.
+For `x`, this doesn't actually do anything as we only hold a read lock, but the write lock on `z` is released here.
 (We assume there is no implicit reborrowing of `z` going on here. The curly braces make it so that `z` is moved, not borrowed, to `fun`.)
-So, when `fun` is called, we hold the read lock for `x` and the write lock for `y`.
+So, when `fun` is called, we still hold the read lock for `x` and the write lock for `y`.
 Consequently, if `fun` were to access `y` or write to `x`, we know that's UB -- so we can rely on this not to happen and perform our desired optimizations.
 
 Notice that this optimization is extremely hard to perform e.g. in C, because to know that `fun` cannot access `y`, the compiler needs to do whole-program alias analysis -- a notoriously hard problem.
@@ -232,9 +184,9 @@ In contrast, Rust's type system allows us to perform such optimizations intra-pr
 #### Validating taking a reference
 
 In the last example, we deliberately *moved* `z` to `fun` to side-step any discussions about borrowing.
-However, typically, you would actually *reborrow* `z`, leading to additional validation calls around the operation that takes a reference.
-We will look at that case now.
-Let us also say that `fun` actually returns a reference with the same lifetime as `z`.
+However, typically, you would actually *reborrow* `z`.
+As we will see in this example, to properly model transferring ownership of (re)borrowed memory to other functions, we will perform suspend and acquired validation around the operation that takes a reference.
+To better demonstrate this, let us also say that `fun` actually returns a reference with the same lifetime as `z`.
 Overall, our code now looks like this (with all reborrowing being explicit):
 {% highlight rust %}
 // Defined elsewhere: fn fun<'z>(x: &i32, z: &'z mut (i32, i32)) -> &'z mut i32  { ... }
@@ -268,6 +220,7 @@ When `z` gets reborrowed to be passed to `fun` with lifetime `'inner`, we *suspe
 This models the fact that, no matter what we do with the newly created reference, we know that when `'inner` ends, we get our exclusive access back.
 After the suspension, we don't hold a lock any more for what is now `*z_for_fun`, so we immediately acquire a write lock again.
 However, following the type of `z_for_fun`, we will acquire this lock only for lifetime `'inner`.
+For this to work, validation needs to know the *non-erased type* of the lvalues -- all the lifetime information must be present, so we can acquire the lock for the right lifetime.
 (Suspending and then acquiring the write lock may sound somewhat redundant.
 However, notice that, if we were to take a shared reference, we would now acquire a read lock rather than a write lock.
 Furthermore, even here, the overall effect is far from a no-op: The suspended lock will stay around even if the reacquired lock is released.  In fact, this is exactly what happens next.)
@@ -275,7 +228,7 @@ Furthermore, even here, the overall effect is far from a no-op: The suspended lo
 Next, we call `fun`.
 At this point, we release our write lock on `*z_for_fun` again, as usual when passing a mutable reference to a function.
 (The acquire-release of `z_for_fun` is indeed redundant here, but notice that the two validation statements arise from two separate MIR operations:  taking a reference and calling a function.
-These operations just happen to occur just after one another here.)
+These operations just happen to occur immediately after one another here.)
 However, the suspended lock of `*z` stays around -- so while we gave up control of `z` (aka `z_for_fun`) for lifetime `'inner`, we still know that we will get control back when `'inner` ends!
 `fun` is now free to do whatever it wants, as long as it does not violate our still-existing write lock of `*y` and the read lock of `*x`.
 
@@ -299,12 +252,71 @@ In other words, as the lifetime of the reborrow from `z` expires, we release all
 When we come to the write to `*y`, we know that this write is redundant because (a) we held the write lock for `*y` all the time, so nobody else could have written to it without triggering UB, and (b) we know `z_inner` does not alias with `y` (or else we would already have UB), so we ourselves have not written to `*y` either.
 Hence, we may optimize away the write.
 
-### 2.4 `UnsafeCell`
+### 2.3 Validation
+
+The examples should already give you a good idea of what `Validate` does.
+It is time to look at this statement in some more depth.
+Remember that it takes a validation operation and a list of lvalue-type pairs as arguments.
+The most important validation operation is *acquire validation*.
+As the name indicates, this is about acquiring the appropriate locks.
+It also otherwise makes sure that values are valid at the given type, e.g., references have to be non-NULL and aligned.
+
+The core of acquire validation is an operation with a signature roughly like this:
+{% highlight rust %}
+fn acquire_validate(lval: Lvalue, ty: Ty, mutbl: Mutability, lft: Option<Lifetime>)
+{% endhighlight %}
+Why are mutability and lifetime showing up here?
+The reason is that reference types have a "transitive" effect down the type hierarchy: `&T` makes everything reachable through this reference read-only, even if `T` involves `&mut`.
+Similarly, in case of nested references, it is the *outermost* reference that defines the lifetime for which access through this pointer is granted.
+(The compiler makes sure that inner references always have longer lifetimes than outer references.)
+
+As we have seen in the examples, `acquire_validate` recursively traverses the type hierarchy.
+When it encounters a primitive type like `i32`, it acquires a lock of `size_of::<ty>` many locations starting at `lval` for lifetime `lft` -- this will be a write or read lock depending on whether `mutbl` says this data is mutable or not.[^2]
+In other words, memory is locked "at the leaves" of the type structure, rather than locking immediately when we see a reference type.
+We will come back later to why this is necessary.
+Validation also makes sure that the value stored in memory is valid at the given type.
+For a `u32`, this just amounts to checking that the memory is properly initialized.
+
+[^2]: For simplicity, we pretend lvalues are just locations in memory.  Actually, lvalues can also refer to variables not in memory (like non-addressable stack locals), but these do not need to be locked.  Furthermore, lvalues for unsized types carry the additional information stored in a fat pointer, i.e., a length (for slices) or a vtable (for trait objects); this is handled appropriately when validating the respective types.
+
+For compound types like tuples, `struct` or `enum`, validation proceeds recursively on the fields.
+In particular, the enum discriminant is checked to be in-range (in particular, nothing can pass validation at an empty enum type).
+However, because the recursive validation will only lock memory that's actually covered by a field, we also have to acquire the appropriate lock for padding bytes and the enum discriminant here.
+
+Finally, at a reference type, two things happen.
+First, the reference itself is stored in memory somewhere; this memory has to be locked just like the validation of `i32` locks the memory used to store the integer.
+The reference is also checked to be non-NULL and properly aligned for the type it points to.
+Furthermore, validation proceeds recursively after *dereferencing* the reference.
+Crucially, the `mutbl` and `lft` for this recursive call are taking the reference type into account:
+If `lft` was `None` and this reference's lifetime ends within the function (i.e., there is a corresponding `EndRegion` somewhere), it is now set to the reference's lifetime.
+If `mutbl` was mutable, it becomes immutable when following a shared reference.
+
+Acquire validation is performed at the beginning of every function (acquiring the function arguments) and upon returning from another function (acquiring the return value).
+These are the places when we rely on other functions providing valid data to us.
 
-This concludes the examples.
-I hope you now have an idea of how memory locks and validation affect the execution when "bad" references are passed around, and how they validate the assumptions we need to make for optimizations that reorder memory accesses.
+There are two other validation operations besides acquire validation: release validation, and suspend validation.
+Both operations recursively follow the type just like acquire validation, and for all memory they visit, they release/suspend *write* locks.
+Read locks are not touched, which corresponds to the fact that shared references are `Copy` and hence never "given up":
+Shared references always remain usable until their lifetime expires, at which point the read lock is released automatically.
 
-One topic that did not come up yet is interior mutability.
+Release validation occurs before calling a function, when the function arguments are released.
+This grants the functions write access to memory that we are explicitly passing along.
+
+Suspend validation occurs before taking a reference, using the lifetime of the new reference.
+This encodes the fact that when the lifetime ends (and hence the lock is being reacquired), we are the exclusive owner of this memory again.
+
+**Update**: It has been pointed out to me that another way for values to flow back into a function is through mutable references. Good catch! I will need to extend the validation machinery to also perform acquire validation when a write lock is reacquired. **/Update**
+
+To summarize, validation statements are emitted during MIR construction in the following places:
+- At the beginning of the function, we perform acquire validation of the arguments.
+- When taking a reference, we suspend the referee for the reference lifetime and acquire the referent.
+- When calling another function, we release the arguments and acquire the return value.
+
+
+### 2.4 `UnsafeCell`
+
+I hope you now have an idea of how memory locks and validation enforce the assumptions that are encoded in Rust's types.
+One topic that needs special treatment in this context is interior mutability.
 If a function takes an `x: &Cell<i32>`, following the rules above, it will acquire a read lock of `*x` for the duration of the function call, making `*x` immutable.
 Clearly, we do not want to do that -- calling `x.set` *will* actually mutate `*x`, and mutating through a shared reference is exactly the point of using `Cell`!
 
@@ -406,4 +418,6 @@ Other areas of future work include `static` variables and the `NonZero` type.
 Nevertheless, my hope is that the general approach of a contract-like, type-driven validation mechanism ends up being useful.
 So, keep the comments flowing -- and safe hacking.
 
+**Update**: I did some refactoring of the post, reordering sections 2.2 and 2.3 to hopefully make it all flow better. Thanks for all the helpful feedback!
+
 #### Footnotes