[Pitch 2] Safe loading of values from `RawSpan`

Evolution Pitches
61

Values with bit patterns that the compiler (and optimizer) can universally assume will never ever exist. For example, a non-optional RawPointer whose bit pattern is all zeroes, or a three-valued enum whose discriminator is equal to 4. These are values that the compiler assumes will never be stored in memory that is bound to a particular type. It doesn’t include values that the compiler is fine with but the standard library might assert on. (@_semantics blurs that line.)

It’s clear to me now that this pitch is working toward a larger concept of safety, but I did not understand that from the initial pitch or the naming choices. It sounds like FullyInhabited is trying to name the set of types which, for all possible bit patterns, cannot be combined with any non-@unsafe stdlib API to produce a memory safety issue. Assuming that’s accurate, it’s quite narrower than I believe most would understand it to mean.

Is it at all likely that a third party will ever be able to write a type that satisfies the definition of FullyInhabited being used in this pitch? Would that hint at FullyInhabited being the currency type of a larger ecosystem of “fully usable under strict memory safety” types? If so, should the name so readily lend itself to a sensible interpretation in a vacuum? And is a type as bedrock as Int really so universally “safe” as to be labeled as such by conformance to FullyInhabited?

1 Like
62

In essence, the difference between your view of FullyInhabited and mine is just who has the authority to declare that some bit pattern is legal or not. I think Swift developers should be able to, you think only the Swift compiler can.

Making it the sole authority of the compiler is needlessly restrictive and locks us out of useful improvements in the future. For instance, given this struct (which is not FullyInhabited, as far as I’m concerned):

struct Foo {
    let count: Int

    init(count: Int) {
        precondition(count >= 0)
        self.count = count
    }

    func isValid(index: Int) -> Bool {
        0..<count ~= index
    }
}

you could imagine a world where the compiler sees that precondition and can optimize away the 0 <= count check (as always true) that 0..<count implies, since it is impossible to create a Foo whose count is less than 0. (This is hand-wavy and probably not exactly how this should be implemented, and it’s not a pitch, but hopefully it brings the point across that developers can collaborate with the compiler to open optimization avenues by proving that certain values are impossible.)

Is it at all likely that a third party will ever be able to write a type that satisfies the definition of FullyInhabited being used in this pitch?

Yes? De facto, most structs with a synthesized memberwise initializer and fields that are all FullyInhabited can be themselves, with at most modest changes (such as reordering fields or creating fields to explicitly inhabit padding). To start, this includes all RawRepresentable where RawValue: FullyInhabited types. This can also include almost anything that you would send over a process boundary, such as network addresses, IPC parameters, things that go in shared memory, shader structures, etc.

Would that hint at FullyInhabited being the currency type of a larger ecosystem of “fully usable under strict memory safety” types?

No, this can’t be a goal. Types that are not BitwiseCopyable can never be FullyInhabited. This includes ~Escapable and ~Copyable types, which are foundational to safe and fast Swift code. This also includes all reference types and structs that hold references, including Array and Dictionary.

And is a type as bedrock as Int really so universally “safe” as to be labeled as such by conformance to FullyInhabited?

Yes. I think that in all cases where using the bad integer leads to a memory safety bug, we would blame the user of that integer for doing insufficient validation.

1 Like
63

The disconnect probably comes from the fact that we have (internal) documentation that uses "inhabited" and derived terms in a "compiler knows this" sense. For example, the documentation for type layout talks about "extra inhabitants" being used to pack enum cases. I don't expect external Swift developers to be deeply familiar with these documents, but I would expect it of some large subset of Swift Evolution contributors.

I wouldn't object to expressing the concept of "fully inhabited" (in the sense you're using) as a protocol like BitwiseCopyable that can be inferred by the compiler or explicitly applied by a developer. That seems like a proposal that needs to come before this one though, as it is somewhat orthogonal to API for loading values but a clear definition of the concept is a necessity for this API to work.

1 Like
64

What about in the same file, like Sendable? I would hate to lose this spelling in particular:

struct Foo { ... }

#if compiler(>=6.4)
extension Foo: FullyInhabited {}
#endif
5 Likes
65

Yes. Any tuple or inline array of FullyInhabited types is FullyInhabited in every sense that has been discussed. (In particular, e.g. any homogenous tuple or inline array of stdlib integer or floating-point types¹ is FullyInhabited.)

Any third-party type, then, that wraps a single value or homogenous tuple or inline array of FullyInhabited types and does not introduce its own semantic invariants that limit the set of permitted values can also be FullyInhabited. (There are lots of other ways to produce a valid conformance; this is sufficient, but not necessary, and simply illustrates that’s is absolutely possible for user-defined types to conform).

¹ Other than Float80, which I will now go back to studiously ignoring.

1 Like
66

This is incorrect. Range (as implemented in Swift) has an invariant that lowerBound <= upperBound. This invariant is checked by all safe API that produces a Range. Any bit pattern that does not satisfy this constraint is not a valid Range value.

3 Likes
67

And to make it completely clear as to why it matters for Range and bounds-checking: full bounds-checking with a range of indices involves 3 comparisons: startIndex <= lowerBound, lowerBound <= upperBound, upperBound <= endIndex. The stdlib checks the middle one at Range creation. This doesn’t matter when you use a Range value only once, but if you re-use it you get to not repeat the middle calculation. This is a small optimization, but worth it because there is a large amount of bounds-checking. On the other hand, if you pass an invalid Range, you can indeed cause an out-of-bounds access.

4 Likes
68

Could you show an example of that?

Am I breaking invariants / triggering UB in this code?

struct A: CustomStringConvertible {
    var a: UInt8
    /* padding */
    var b: UInt16
    public var description: String {
        "A(a: \(String(format: "0x%02hhx", a)), b: \(String(format: "0x%04hx", b)))"
    }
}

struct B: CustomStringConvertible {
    var a: UInt16
    var b: UInt16
    public var description: String {
        "B(a: \(String(format: "0x%04hx", a)), b: \(String(format: "0x%04hx", b)))"
    }
}

let (al, bl) = (MemoryLayout<A>.self, MemoryLayout<A>.self)
precondition(al.size == 4 && al.size == bl.size && al.stride == 4 && al.stride == bl.stride && al.alignment == 2 && al.alignment == bl.alignment)

var b = B(a: 0x1234, b: 0x5678)
var a = unsafeBitCast(b, to: A.self)
print(a) // A(a: 0x34, b: 0x5678), perhaps 12 is in the padding now
a = A(a: 0x12, b: 0x3456)
b = unsafeBitCast(a, to: B.self)
print(b) // B(a: 0x0012, b: 0x3456) - luckily got 00 in the high order byte of B.a

Understandably in the last line I could get random garbage in B.a coming from A's padding, but is that (per se) triggering UB or breaking invariants?

69

The unsafety would come about if you made a decision based on the value of the padding byte.

func f() -> (B, Bool) {
  let b = unsafeBitCast(A(a: 0x12, b:0x3456), to: B.self)
  return (b, b.a <= 0xff)
}
// The optimizer could quite reasonably always return true,
// but it's not necessarily the case that that byte is actually initialized.

var (b, blank) = f()
if blank {
  let l = withUnsafeBytes(of: &b) { strlen($0.baseAddress) }
  // l is not necessarily 1, could easily read past the end of the allocation.
}
70

That I could use withUnsafeBytes in an unsafe manner - sure, but I could do that unrelated to padding bytes (whether they happen to be initialised or not), just pass some arbitrary wrong index $0.baseAddress[12345] = whatever.

Let me rephrase:

  1. I could use unsafe API like unsafeBitCast to get uninitialised garbage value.
  2. if I use that garbage value later on "safely" – I will not trigger memory safety violations.
  3. if I use that garbage value later on "unsafely" – I could violate memory safety, but that I could do without step (1), just passing a "safely" generated wrong number which will be out of bounds for unsafe API.

So what does it change, if instead of unsafe unsafeBitCast in (1) I will be using a "safe" API like RawSpan and be able generating uninitialised garbage number through it (i.e. if that was allowed to use it for types with padding)?

Perhaps I am missing something obvious here...

71

I’m just using unsafe stuff to illustrate the underlying mechanism. If we label the wrong thing as “safe”, then the same mechanism of action could become accessible in code that is advertised as safe. We need to avoid that.

1 Like
72

UInt8.random() is safe... How is the uninitialised garbage byte in the padding of a struct is not safe? What's the difference?

73

The compiler can make optimization decisions based on whether it thinks a value is initialized or not. If it is not, it can make an arbitrary decision not based on the value in memory. That is one of the things meant by “undefined behaviour”. The arbitrary decision situation is what I tried to illustrate above.

2 Likes
74

UInt8.random() produces an unspecified initialized value; two loads of that value will produce the same result.

Two loads (in LLVM IR, not machine loads) from the same byte of padding or otherwise uninitialized memory do not necessarily produce the same value. The result of a load from uninitialized memory in IR is undef, and LLVM may transform one undef into an arbitrary value and turn another load into another value or produce an actual (machine) load instruction observing the value in memory. This will result in the same byte of an ostensibly non-mutable buffer producing two different values, which pretty easily leads to invariants being violated.

I get the impression that you’re trying to reason about language semantics based on “what the hardware will do”; this is the same mistake that trips people up when they think about C and C++ undefined behavior and argue that it should “just do what the hardware does”. The abstract machine of language semantics defines what is and isn’t possible, not the hardware.

5 Likes
75

I'd love to see this in action! Is it possible?

let x: UInt8 = // uninitialized
let a = x < 128
// .... what do I do here for IR to change its mind?
let b = x >= 128
precondition(a != b) // want to see this failing

Attempt to force this UB in pseudocode:

let x: UInt8 = // uninitialized

let a = x < 128
if a {
	// some complicated code that IR wants to avoid dealing with
} else {
    // nothing here, easy path, IR wants to choose this
}

// perhaps in another file to give it extra chance

let b = x >= 128
if b {
	// some complicated code that IR wants to avoid dealing with
} else {
    // nothing here, easy path, IR wants to choose this
}

precondition(a != b) // want to see this trap

What do I do to make it real?

76

This is already hard to do in any case because you’re asking the Unpredictable Machine to produce a predictable outcome. Here’s a C example that Works On My Machine, which is probably as good as it can get:

// clang -ftrivial-auto-var-init=uninitialized -O3 -o test test.c
#include <stdio.h>

int main() {
	int x;
	printf("%i\n", x);
	printf("%i\n", 123);
	printf("%i\n", x);
}

This prints “1797845312, 123, 123” (with the first number changing at random if I execute it multiple times).

8 Likes
77

I think this is a footgun easily avoided.

Since this is a safety concern, if the compiler can't validate conformance is safe, then users shouldn't be able to declare it.

If we desperately need the ability to declare it without compiler checks, it should have to be spelled @unchecked FullyInhabited.

1 Like
78

I've pushed an update to add an "alternatives considered" item that describes what may be a better design:

Separating the FullyInhabited protocol into separate ConvertibleToRawBytes and ConvertibleFromRawBytes protocols.

As described previously, FullyInhabited is a stronger constraint than is needed to prevent uninitialized bytes when initializing memory. The minimal constraint would simply be the absence of padding; this could be called ConvertibleToRawBytes. Similarly, FullyInhabited is a stronger constraint than is needed to exclude unsafety when loading bytes from a RawSpan instance. The minimal constraint would be similar to FullyInhabited, but would allow for padding bytes; this could be called ConvertibleFromRawBytes. Types that conform to both would meet the requirements of FullyInhabited as described here.

typealias FullyInhabited = ConvertibleToRawBytes & ConvertibleFromRawBytes

Separating FullyInhabited in this manner would make the system more flexible, at the cost of some simplicity. It would allow us to define a safe bitcast operation:

func bitCast<A,B>(_ original: consuming A, to: B.self) -> B
	where A: ConvertibleToRawBytes, B: ConvertibleFromRawBytes

This design would get us closer to the ideal than the version of FullyInhabited we’ve been discussing.

5 Likes
79

As much as I like the aim of this proposal with respect to RawSpan, I do not at all like all the gaps it leaves when connected to different ABIs, padding bytes etc. It feels like it’ll end ip being a fragile tool, unless it can only be conformed to by the stdlib. Maybe a “sealed protocol” if those existed.

1 Like
80

As long as the compiler enforces the "no-padding" and "all members are also fully-inhabited" constraints, there's really no gaps. This is especially true for the typealias FullyInhabited = ConvertibleToRawBytes & ConvertibleFromRawBytes version.