Forget Borrow Checkers: C3 Solved Memory Lifetimes With Scopes
17 points by clerno
17 points by clerno
This is a weird post. It’s aware enough of borrow checking to call it out in the post, but then also somehow not aware enough of it to know this doesn’t address the problem of getting memory lifetimes correct.
Presumably you’re thinking of a pointer to an object from an inner pool being held by one from an outer pool? That’s still safe if accessing the pointer leads to program termination (not that I know c3 guarantees that).
Freed pool memory will be completely overwritten in Safe mode, so it’s fairly straightforward to detect.
That’s the default behaviour of free() on macOS - that’s not even a debug mode behaviour.
The problem with use after free is not leaking old data (I mean it is, but that’s much less exploitable), it is using a pointer to an object after the object has died and the memory has been reused for a different (potentially unrelated type) object.
When a vulnerability is reported as a “use after free” it is seldom reuse as the same object type. In browser attacks it’s often “I have a dangling pointer to something that is an attacker read/writable (by design) object type being reused as an internal object of a completely unrelated type (maybe something with function pointers, maybe an object containing permission info, etc).
When responding to such attacks it’s preferable to just leak memory if resolving the lifetime cleanly can’t be done in an immediate response update.
It’s likely to lead to an exploitable vulnerability when the memory previously used by the inner pool is reused for some other purpose.
Indeed, once you release memory it matters little what you did to it beforehand, because whatever value it once was may now be different. Of course how likely you are to run into such cases depends heavily on the allocator in use, but at the end of the day you’re depending on undefined behavior.
you’re depending on undefined behavior.
Unless the allocator is type-aware and guarantees type stability :) Type confusion is easier to solve than UAF or leakage.
We know the C3 temp allocator is not type stable just from the description in the article.
Even if memory is type stable, use-after-free can lead to undefined behaviour. It easily break data structure invariants (such as causing incorrect buffer lengths) and/or cause data races, which are often exploitable vulnerabilities.
“Forget malloc: C3 introduces Arenas” might be a better title here. Rust’s “borrowing” isn’t mentioned in the article.
I’m not understanding how this would replace the borrow checker, is there something preventing me from returning a pointer to an allocation in the pool?
fn int* returning_a_bad_pointer() {
@pool() {
return mem::tnew(int);
};
}
This article is really weird - I cannot work out what this is solving? As far as I can tell it is a trivial example of an arena allocator, which is a common enough idiom that it has a name (an arena allocator). It dismissed RAIi as needing “classes” but RAII types are how you would just ensure your arena is release upon leaving a scope in C++, or equivalently a defer{} block. All RAII and defer{} are being used for is to permit custom scope exit behavior.
Now on to “solving” lifetimes.
I just don’t under this claim? As far as I can make out this does nothing to resolve that?
It reads like the belief is that lifetimes are about avoiding leaks when that is very much not the case (strictly speaking it is, but let’s be clear if people are discussing Lifetimes(tm) today, they’re not concerned about leaks). Fundamentally even C++ doesn’t struggle with leaks anymore - consistent RAII types make it pretty easy to avoid, and for other cases arena allocators work (better yet such allocators don’t need to be lexically scoped).
The major problem rust style lifetimes resolve, or true automatic GC, or reference counting is not leaking (indeed a common GC strategy in big iron is to simply never release memory). It is continuing to hold references to memory after the lifetime of the contained object has ended.
That is what becomes exploitable.
From this post I don’t see anything that would prevent me from literally writing something to the effect of
return mem::tnew(type);
At a type system/language level - this exact case would be easily detectable of course, but in a safe language would not be possible without heuristic rules on the source.
It’s possible I’m missing something but as far as I can make out the language cannot prevent me assigning a tnew() allocation to a field in an unescorted object?
If that’s not correct I’d love to know how it models the lifetimes - a post about how that works would be much more interesting than a post about the API.
The major problem rust style lifetimes resolve, or true automatic GC, or reference counting is not leaking (indeed a common GC strategy in big iron is to simply never release memory).
I vaguely remember hearing about someone’s sudo reimplementation that does that because you can’t use-after-free if you never free.
return mem::tnew(Foo); is completely safe in itself.
The problem (which I think is what you want the answer to) is what happens when it crosses a temp pool boundary:
int* iptr;
@pool()
{
iptr = mem::tnew(int);
*iptr = 123;
};
... using *iptr ...
Now this is possible to do (at the moment no static analysis will prevent you), and this is the same problem as if you would have done this in C++
Foo *foo_ptr;
{
Foo y {};
foo_ptr = &y;
}
... using *foo_ptr ...
In the C3 case that memory pointed to will be scratched out: you’ll get 0xAAAAAAAA if you dereference it, but it’s still valid (unless you run with –sanitize=address)
Could this be improved? Yes, in particular on platforms with virtual memory.
Right, this is a bug in C++ that C3 is not solving here, and solving the general problem of an allocation from a temp pool escaping is not obviously any easier here for you than it is for C or C++.
Clearing/scrubbing/zeroing memory on deallocation does not fix anything here. The default darwin system allocators already zero on free - not even as a debug option, but as the default behavior (at least on arm).
The problem with dangling pointers is not leaking the content of memory, it is the subsequent concurrent use of a single location in memory through unrelated pointers.
What you have here is a direct syntax for a language provided arena allocator. Sure that makes it easier to not leak, but from a memory safety point of view, leaking allocations is always safer than allowing a dangling pointer to remain accessible. Notionally it’s equivalent to @autorelease { ... } in objc (or the equivalent in swift) in that it it’s a syntax that inserts a barrier over a specific lifetime, and it has the same problems that you have here, e.g
id foo() {
@autorelease {
return [[[SomeType alloc] init] autorelease]; // lifetime is bound to the contained autorelease pool so the returned object is nominally dead
}
}
This is semantically identical to
@pool()
{
iptr = mem::tnew(int);
*iptr = 123;
};
Objective-C’s autorelease system exists to support more or less exactly the same use case of tnew() - “temporaries” get freed automatically. The only difference is because autorelease is built on refcounting it is possible for a receiver to actually take ownership of the object so leaving the autorelease scope does not end the object lifetime if there are other owners.
That said we can see this is “obviously preventable”
But lets add indirection, assume some functions exist like this - I’m intentionally using still objc here specifically because the lifetime semantics of autorelease and autorelease pools are identical to your pool allocators:
// C3
Foo* doThing1() { return mem::new(Foo); }
Foo* doThing2() { return mem::tnew(Foo); }
// ObjC equivalent
Foo* doThing1() { return [[Foo alloc] init]; }
Foo* doThing2() { return [[[Foo alloc] init] autorelease]; }
now a function using these:
Foo *someRootFunction(Foo*(*fptr)()) {
@pool() or @autorelease {
return fptr();
}
}
You cannot static analyze your way out of this general problem - you need to have a way to model the lifetime of object references such that errors that allow dangling pointers to remain accessible are not possible.
Debug allocators are not a solution for language safety: all major C and C++ projects do testing and fuzzing with an array of debug allocators.
Clearing/scrubbing memory is not a solution either, because the problem is not what data is left in the object when it is freed, but what data is in the object when it is accessed in future through the dead pointer.
Page table shenanigans don’t fix this either, because your only way to prevent the dead pointers to old pool allocations from being exploitable is to make every part of the pool consist of some multiple of pages (not individual objects), and then when a pool scope ends, release the physical memory for that set of allocations and leak the address space.
That’s not as bad as leaking physical memory, but you’ll be leaking at least a page of address space every time you enter and exit any @pool.
I want to be clear: things like pool allocators, and language support that makes managing temporary allocations easier are not bad.
But they do not do anything to solve lifetimes. They are not a memory safety feature.
I said in other comments in this thread: from a safety point of view, leaking is superior to anything that permits dangling references.
is completely safe in itself.
Perhaps just semantics, but I think it can be a useful tool for thought:
Nothing is “safe in itself”. Things can only be safe or unsafe in some given context. Things in isolation aren’t safe or unsafe, they just are.
In this oontext, the commenter seemed to think that returning a mem::tnew object out of a function was creating a dangling pointer. It doesn’t.
how does it not create a dangling pointer – that’s what you have not explained anywhere, and what I’m missing.
As far as I can tell:
@pool() { return mem::tnew(..); }
seems to be a dangling pointer?
Yes it is. If you deliberately return something out a pool where it’s allocated you will have a bad time as that pointer’s data will get overwritten but it’s still possible to write to, unless you use –sanitize=address.
It’s a point of improvement to add an attribute to be able to check more of this at compile time.
So to summarize: C3 uses a novel approach with a stackable temp allocator which allows many uses of ARC, GC and moves to be solved without heap allocation, and without tracking the memory.
It doesn’t solve ALL uses of a borrow checker, just like the borrow checker doesn’t solve all the problems a GC does, but it solves enough to be immensely useful.
Similarly, the stackable temp allocator removes the need for virtually all temporary allocations in a C context, reducing heap allocations to only be used in cases where the lifetime is indeterminate.
soooooo your title is clickbait enough that you’re forced to clarify?
This is somewhat contrarian opinion, but clickbait titles are totally ok! Sometimes an article can be summarized nicely in a short phrase (P = NP), but sometimes it just can’t. “The Man Who Laughs” is such a clickbait! And, well, it is a sad truth that the title is what often determines whether the reader clicks on the link or not. So, imo, totally fine to be whimsical, provocative, and fun-poking in the title.
But there are no (strict) length constraints on the article itself. The more clickbaity the title is, the more thorough explanation of your actual claim you owe to your readers, in the article itself, and not in the surrounding discussion.
is it also ok to feel like my time is wasted by blog posts or news articles that aren’t about what they say they’re about and decide to not waste my time in the future reading from places that do that
that’s a bit like saying the pictures of a product are what determine whether someone buys it so it’s fine to use pictures of a better product as long as you send the buyer lots of accurate pictures after you have their money
My usual recommendation for e.g. new speakers (who are prone to this, they want to make an awesome entry on stage): The hotter your take, the more you should work on backing it up properly.
That is particularly a problem if you want to lean into subjects that are a little bit out of your field.
C3 uses a novel approach with a stackable temp allocator which allows many uses of ARC, GC and moves to be solved without heap allocation, and without tracking the memory.
Which is know for decades as an arena allocation…
Yes! But usually with an arena allocator you need:
This is what the C3 temp allocator helps solving over a manual Arena solution.
@autoreleasepool in ObjC has done that.
You’ve got a nice solution, but you’re overselling the novelty and how much it solves.
It doesn’t solve ALL uses of a borrow checker
It’s so far off, that I think it’s a misunderstanding of what the borrow checker does.
You’re talking about preventing memory leaks, but the borrow checker doesn’t even handle freeing of memory. It’s literally for everything else other than allocations and freeing.
Borrow checker prevents having dangling pointers with two essential properties: it’s a correctness guarantee, and it’s done fully at compile-time. You can’t prevent dangling pointers. You can only opportunistically mitigate some of the misuses. You have usability improvement that indirectly leads to correctness improvements, but it’s not a guarantee, and you don’t catch mistakes at compile time.
This is a substantial difference. It’s like “Forget Non-Nullable Types. C3 Solved Nullability with assert(!ptr)”.
Borrow checker also strictly controls mutable vs shared access (pointer aliasing), which catches classes of errors like iterator invalidation. You have absolutely nothing for it.
Reminds me of nested pools in APR
When pools follow a strict stack discipline, they can have a simpler API like glibc obstack. Exim has a similar pool allocator that can free everything after a particular point.
In a less C-brained context there’s the MLKit’s region-based memory management which uses a static analysis to determine where to allocate objects in a stack of regions that corresponds to the dynamic call stack.
This C3 allocator seems very 1990s to me.
The work on stack allocation in OxCaml is exploring this area while keeping a GC.
From memory MLKits region based MM had some interesting corner cases.
Note that C3 temp allocations can be done out of order correctly, so this is fine:
So that’s the advantage over just a stack allocator.
It’s not complicated stuff, but the novel thing is that it works throughout the stdlib.
Everybody talking about how arenas aren’t equivalent to borrow checking, nobody talking about the garbage collection slander.
So how does this handle returning a pointer to temporary memory? Or passing the pointer to different threads?
The technique for returning a pointer to temp memory from a pool, is to allocate it on the parent temp allocator:
Allocator old_mem = tmem;
@pool()
{
String temp = string::tformat("%s", 1); // on the current temp allocator.
return temp.copy(old_mem); // Copy it to the outer temp allocator
}; // temp is freed, but the copy is valid, it follows the old_mem's lifetime.
OK but is this actually enforced in any way, or does it come down to the usual C mantra of “just don’t write unsafe code”? Unless this is somehow enforced it doesn’t solve memory lifetimes at all.
Does C3 prevent you from just returning temp?
If not memory lifetimes are not “solved” (or more specifically, this particularly simple issue is not solved and solving it would still not solve lifetimes in general).
It seems like the title is making bold claims, but the article doesn’t attempt to prove them.
Edit: it seems you’re the author, no? If so you should’ve selected that option when submitting the story to make the relationship clear.
I did not write the article no, a contributor did. I am the author of the C3 language though.
There is no preventing X from doing Y no. Just things like cleaning out memory, so that dangling pointers do not lead to valid data. C3 has a bit of static analysis, and potentially more can be tracked through annotations.
But a limitation is that it should work seamlessly with C, and so things that cannot have a representation in C is out of scope.
I don’t mind clickbaity titles to catch people’s interests, but if you are allowed to return dangling pointers it definitely doesn’t replace borrow chcecking. Whole point of Rust is that you don’t have to worry about memory safety while you are writing safe Rust.
Shots fired! I’d love to hear from zig and rust users.
This deserves a blog post, but there’s this whole genera of posts that goes:
I found a much simpler solution to memory safety than borrow checking!
This is how you can avoid memory leaks
But leaking memory is safe behavior! RAII vs defer vs arenas is mostly irrelevant for memory safety. While leaking memory is not good, it’s not a safety issue, it won’t disclose your password or allow arbitrary code execution (and it’s not like Rust prevents memory leaks to the same extent it prevents memory unsafety).
The central memory safety counter example, the hardest case to solve, doesn’t have anything to do with heap allocation. This is the thing:
const std = @import("std");
const E = union(enum) {
a: u64,
b: *const u64,
};
pub fn main() void {
var x: u64 = 92;
var e: E = .{ .b = &x };
const xpp: *const *const u64 = switch (e) {
.a => unreachable,
.b => |*p| p,
};
e = .{ .a = 42 };
const x_huh: u64 = xpp.*.*;
std.debug.print("{}\n", .{x_huh});
}
$ zig run main.zig
Segmentation fault at address 0x2a
/Users/matklad/p/tb/main.zig:16:5: 0x100456cc0 in main (main)
const x_huh: u64 = xpp.*.*;
^
/Users/matklad/p/tb/work/zig/lib/std/start.zig:651:22: 0x100456bbf in main (main)
root.main();
^
???:?:?: 0x18d1aab97 in ??? (???)
???:?:?: 0x0 in ??? (???)
fish: Job 1, './work/zig/zig run main.zig' terminated by signal SIGABRT (Abort)
enum E<'a> {
A(u64),
B(&'a u64),
}
pub fn main() {
let x: u64 = 92;
let mut e: E = E::B(&x);
let xpp: &&u64 = match &e {
E::A(_) => unreachable!(),
E::B(y) => y,
};
e = E::A(42);
let x_huh: u64 = **xpp;
println!("{x_huh}");
}
$ rustc main.rs --error-format=short
main.rs:13:5: warning: value assigned to `e` is never read
main.rs:13:5: error[E0506]: cannot assign to `e` because it is borrowed: `e` is assigned to here but it was already borrowed
error: aborting due to 1 previous error; 1 warning emitted
So, if an article doesn’t cover examples like the above, I remain extremely skeptical about memory safety claims (while still trying to learn new patterns and what not)
It’s a great example, I can’t think of how to make it safe without pretty aggressive tactics:
While these are both legal for the compiler to do without breaking zig language semantics, they come with some pretty obvious downsides. That said, I could see there being something like -faggressive-safety-checks which might be handy in a pinch.
The example can be made more bullet-proof by making it an extern union because that type has a well-defined memory layout, meaning the compiler’s ability to detect illegal behavior is limited - not even these aggressive ideas are allowed by the language.
To be completely honest I’m not sure what I’m looking at here :)
Yeah, Rust syntax is not the prettiest, here’s an Ada version for readability:
https://www.enyo.de/fw/notes/ada-type-safety.html
This example is tricky, but it’s worth studying the code somewhat closely, as it is a distillation of why Rust’s shared XOR mutable is desirable.
We have an enum (a sum type) which holds an integer or a pointer. One of defining characteristics of systems programming languages is that they allow pointers to interior parts of larger objects. So the program (both in zig and in Rust) creates a pointer-holding enum variant, and then creates a pointer to that pointer stored in a variant.
What we do next is that we overwrite the entire enum with a different variant. So, the memory that was storing the pointer now stores garbage. So, our pointer to the pointer is now invalid!
Rust detects this at compile time, Zig doesn’t.
To be completely honest I’m not sure what I’m looking at here
Yeah, Rust syntax is not the prettiest <…>
FWIW, out of the two snippets you presented, the Zig one is definitely more inscrutable.
Well, the blog post doesn’t talk about memory safety but memory lifetimes, so I wonder a bit where this is coming from.
If I read that right, you’re editing a tagged enum through the pointer to circumvent safety? That has nothing to do with the blog post, which is about memory management.
In a C3 context it’s not really applicable since there are no tagged enums yet. But if you do this:
union Foo
{
ulong a;
ulong* b;
}
fn int main()
{
ulong x = 92;
Foo e = { .b = &x };
ulong** xpp = &e.b;
e = { .a = 42 };
io::printn(**xpp);
return 0;
}
You get:
ERROR: 'Unaligned access: ptr % 8 = 2, use @unaligned_load / @unaligned_store for unaligned access.'
in std.core.builtin.panicf (/c3c/lib/std/core/builtin.c3:196) [test]
in main (/c3c/resources/testfragments/debugstuff.c3:18) [test]
in start (source unavailable) [/usr/lib/dyld]
Program interrupted by signal 5.
And if you update 42 to 48:
ERROR: 'Out of bounds memory access.'
in std.core.builtin.sig_segmentation_fault (c3c/lib/std/core/builtin.c3:817) [test]
in _sigtramp (source unavailable) [/usr/lib/system/libsystem_platform.dylib]
in start (source unavailable) [/usr/lib/dyld]
in start (source unavailable) [/usr/lib/dyld]
Program interrupted by signal 5.
We’ll try to improve this even more.
so I wonder a bit where this is coming from.
The post title speaks about solving memory lifetimes without borrow checker. This is an example where rust borrow checker uses lifetime analysis to prevent UB.
The 'a is a lifetime, and it is instrumental in compiler being able to reject the code.
It can be argued that the “lifetime” terminology used by Rust is a bit idiosyncratic, and doesn’t match “common sense” definition of the lifetime, but, if you put borrow checker and lifetime next to each other, you gotta use Rust definition, or be very explicit about using a different one!
Yes, I’ve certainly learned that lesson!
First of all: I like the blog post and the approach. It encodes a common pattern that people could build (but rarely do) into something that is accessible and didactically easier to explain. I wish that was more the focus of the discussion.
Sadly, after reading it multiple times, and as a recommendation for the future, it falls into a beginner trap: it wants to compare more to other approaches and distracts the reader (and later commenters) in the process. It would be much better to have a straight-forward blog post that says “C3 has the best implementation of arena allocation, this is how we improve upon the state of the art (and this is how you can still break it, but this could be improved in the future”.
Well, the blog post doesn’t talk about memory safety but memory lifetimes, so I wonder a bit where this is coming from.
(other comment already touches on this, but I want to be a bit more explicit here) In Rust, the primary purpose of borrow checking and lifetime management is static memory safety, not leak prevention. I expect most of the disconnect in the comments here is because the article is essentially going “Forgot X, we solved Y with Z” except X & Y’s entire existence is largely tied to a completely unrelated problem than what Z actually does.