introduce runtime safety for dangling stack pointers

[andrewrk]

I didn't see anywhere this was clearly written up so here it is.

It's not possible to catch use-after-free of stack memory at compile-time (#5725) because it can be equated to the halting problem. I'll leave that proof as an exercise for the reader.

So, we catch it at runtime, in safe build modes.

Step 1, do escape analysis. Only stack locals which have pointers captured which might outlive their scope are subject to these safety checks.

Step 2, introduce an API for heap-allocating memory, like this:

extern fn safe_alloc(size: usize, alignment: u8) ?[*]u8;
extern fn safe_free(ptr: [*]u8, size: usize, alignment: u8, rbp: usize) void;

These would default to using a slimmed down version of std.heap.DebugAllocator - one that avoids reuse of memory addresses, but does not capture stack traces. Perhaps this would be implemented in compiler_rt so that it could be optimized and be compiled without these safety checks, which would otherwise be recursive.

The subset of stack values which have possibly escaped pointers would then be allocated this way. As an optimization, if there were multiple escaped values in the stack frame, they could be allocated together and freed together.

The allocation function could fail, so the stack slots would still be reserved for such case. Stack base address is passed to safe_free so that it can ignore such fallback pointers.

Heap-allocating instead of stack-allocating is obviously significantly slower, so that's why it's important for Step 1 to work well, in order to make Step 2 rare.

So then, when a dangling stack pointer is used, it either segfaults, or its bytes have been memset to the 0xaa pattern, making it very likely to immediately trigger a crash. Even if it does not trigger a crash, however, it is still memory safe in the sense that the memory does not alias any other allocations, making it easier to debug in Debug mode, and avoiding a certain class of bugs in ReleaseSafe mode.

[Rexicon226]

I'm curious if memory tagging extensions, such as Arm MTE or CHERI, could fit into this design idea.

Instead of slow heap allocations, they'd instead stay as stack allocations but we'd tag them on reference (the neat part is that we don't need to tag all of them, as tagging can be a bit slower) and it would segfault on its own once something tried to load it from outside the frame and the tag mismatched. That result seems consistent with your sentence here:

So then, when a dangling stack pointer is used, it either segfaults

This also makes me think that these allocations should take the place of AIR instructions instead of Sema inserting function calls, similar to *_safe, and it would allow the backend to choose the correct way of lowering it. (alloc_safe for example).

I also wonder how LLVM's support for MTE would fit in here, I am not familiar with how it works. Maybe it's just based on lifetime tags 🤔 . We'd probably need self-hosted backends to take full advantage of it.

[BrainBlasted]

It's not possible to catch use-after-free of stack memory at compile-time (#5725) because it can be equated to the halting problem. I'll leave that proof as an exercise for the reader.

I think I can understand that it might be appreciably hard in cases where we're storing a pointer to a local on something that will outlive it:

const Point = struct {
    x: i32,
    y: i32,
};

const MetaPoint = struct {
    name: []const u8,
    point: *const Point,

    fn init(name: []const u8, x: i32, y: i32) !MetaPoint {
        // Whether we've simply forgotten or we're new to systems programming, we've not allocated this on the heap
        const point = Point{ .x = x, .y = y };

        // The compiler wants a pointer, so we give it a pointer to make it quiet...
        return MetaPoint{ .name = name, .point = &point };
    }
};

pub fn main() !void {
    const x = 10;
    const y = 20;

    const meta = try MetaPoint.init("Origin", x, y);

    const stdout = std.io.getStdOut().writer();
    // Oh no!
    try stdout.print("Point {s}: {{ x: {d}, y: {d} }}\n", .{ meta.name, meta.point.x, meta.point.y });
}

But I'm not sure I understand why this simple case could not be caught by the compiler:

const Point = struct {
    x: i32,
    y: i32,
};

const MetaPoint = struct {
    name: []const u8,
    point: Point,

    fn init(name: []const u8, x: i32, y: i32) *MetaPoint {
        const point = Point{ .x = x, .y = y };
        var meta = MetaPoint{ .name = name, .point = point };
        // We create a local and return a pointer to it.
        return &meta;
    }
};

pub fn main() !void {
    const x = 10;
    const y = 20;

    const meta = MetaPoint.init("Origin", x, y);
    
    // The UB may not present itself initially, but the memory can get overwritten
    // unexpectedly.
    _ = MetaPoint.init("Trample", 32, 32);

    const stdout = std.io.getStdOut().writer();
    // And so unexpected behavior happens here:
    try stdout.print("Point {s}: {{ x: {d}, y: {d} }}\n", .{ meta.name, meta.point.x, meta.point.y });
}

The equivalent mistake in C is caught by clang, GCC, and MSVC (though with a compiler warning instead of a hard error). What makes this case difficult to catch for the Zig compiler?

[mnemnion]

@BrainBlasted, it's not a question of statically catching some misuse of stack memory, but rather a question of statically catching every misuse of stack memory. The latter isn't possible, the former clearly is.

@andrewrk's proposal is to catch every case at runtime, and my early impression of it is that it would succeed at that. The escape analysis will be pessimistic: the answer must be either "cannot escape", "does escape", or "might escape", and the latter two are instrumented.

How much effort should be put into statically detecting escape, and what the language should do about it, is a complex question, but more relevantly from the #23528 perspective, it's a separate question as well.

The Ziggit thread where I found the link to this issue goes over some of those considerations in more detail, for the interested.

[kerosina]

This would be very helpful for newcomers from languages with a GC or automatic memory management (e.g. Rust), and, as one, I've been bit by this a couple times.