If I understand clearly, this prevents use-after-free and double-free? Thus, the program can still fail on a memory access when the expected and actual generations don't match? In this regard, this seems less "safe" than reference counting, tracing garbage collector, or borrow checking?
...wouldn't that also be prevented by the generation-check even if there is no single-ownership? Because once the referenced item is destroyed (and thus bumping that "memory slot's" generation counter) that item reference becomes invalid because the generation no longer matches, so the next attempt to release the item with that same reference should also fail?
One nice property of generational-indices is that they can be shared without compromising memory safety. As soon as the item is destroyed, all shared references in the wild automatically become invalid. But I guess single-ownership still makes a lot of sense for thread-safety :)
EDIT: oh, borrow checking.
How would it even stop use-after-free and double-free?
The "check" function accesses the allocation because it needs the generation number of the allocation. So basically, the reference needs to access the allocation to check if it can access the allocation. Right.
(That doesn't work of course, because if the allocation was freed, access to the allocation and so its generation number is undefined).
This seems obvious so maybe I am missing something big here?
Or something entirely different is meant or targeted here with "memory safety".
> so its generation number is undefined
With e.g. a random C compiler and a random malloc, that's true. But why couldn't the language and runtime cooperate to ensure it is defined?
For example deallocation can write a predictable value to that slot, which is never used as a legit generation index. The memory allocator can make sure that a memory address that ever contained a generation can never contain anything else than generation ids for the entire runtime of the program (e.g. by ensuring that for a given page, all objects are the same size and the allocations are aligned to that size). The language can make sure that nothing else can get written to such a memory address by enforcing bounds checks.
We have a future improvement planned here too: for unrelated reasons (to support generation pre-checking) the random generational references implementation will soon not even unmap any virtual address space, instead remapping it to a central page, so we won't even get any segmentation faults, just assertion failures.
We created two newer approaches since then, which let any memory be reused for any purpose:
* Random generational references, where it's fine if generations overlap with other data.
* Side-table generations, which is slower but we keep the generations in a side-table. It's can be seen in old 0.1 versions as the "resilient-v2" mode, and I plan on resurrecting it for unrelated reasons.
The former will be the default, and the latter we'll be adding back in as an option. Hope that helps!
Also, the blog post talks about 'generational indices', not pointers. This seems to indicate that items of the same type (or at least same size) are grouped into arrays (and since it's an index anyway, the metadata could be stored in one or multiple separate arrays at the same index).
PS: I already linked it elsewhere, but here's how the same can be achieved without language/compiler support (at least it's the same general idea): https://floooh.github.io/2018/06/17/handles-vs-pointers.html
The big step forward by Vale is that the compiler can elide most of the 'dangling checks' on memory accesses, the method outlined in the blog post requires a few rules-of-thumb the coder must follow when using a pointer that's been looked up from a generational-index.
void __check(GenerationalReference genRef) {
uint64_t currentGeneration = *(uint64_t*)((char*)genRef.alloc - 8);
assert(genRef.rememberedGeneration == currentGeneration);
}