by Leonard Ritter, May 3rd 2024
As part of bootstrapping the next iteration of the Scopes compiler, which, until now, oriented itself heavily along LLVM and C semantics, the author tackled the general issue of operating on memory, specifically solving longstanding usability issues that C programmers should be intimately familiar with, which increase cognitive load and make programming in C a never-ending nightmare. These issues are:
- There are at least three kinds of pointers which all use the same type but need to be treated differently: global, stack and heap.
- Rules of memory ownership and sharing are all informally specified, and difficult to enforce in a heterogeneous environment.
- Stack allocations may lead to stack overflow.
- Stack pointers may escape functions, leading to dangling pointers.
- Heap memory will leak if not freed manually.
- Heap memory may accidentally be freed twice, leading to dangling pointers.
- Attempting to free a stack or global pointer is an error.
- Attempting to free a heap pointer is an error if the pointer isn't object-aligned.
- Pointer arithmetic is unbounded, leading to dangling pointers.
- Memory writes may partially overwrite pointer addresses, leading to dangling pointers.
- Invalidating dangling pointers is impossible without the use of an Address Sanitizer.
- Data in memory is indistinguishable from pointers, preventing content-agnostic relocation, copying, serialization, hashing and deallocation.
- Sharing memory concurrently is difficult and error-prone.
- Pointer addresses are exposed to the application programmer, leading to security vulnerabilities.
Rust, Go and Swift have already made significant strides in solving these issues, but the author's goal was to create a solution that is compatible with C semantics, while still providing a clean abstraction over memory management.
The solution is called Arcmem, originally short for "Atomic Reference Counted Memory", but could also be understood as "Architectural Memory Management" or "Archivable memory". Arcmem augments pointer operations with new elidible bookkeeping rules for the compiler, introduces strong and weak referencing (here called hard and soft arcpointers), prescribes a heap layout which dictates the pointer format, and provides a set of library functions which replace and extend the existing C memory API in a backwards compatible way.
Programs compiled with arcmem semantics are fully compatible with the existing C ABI and can be linked with existing C libraries.
The arcmem heap constitutes a singular memory abstraction that replaces all regular C heap, stack and global allocations, taking advantage of the fact that C pointers are of a single type, and codifying this property for good.
The heap consists of two parts: the bin table and the pool (a single contiguous memory reserve). The pool is split into 32 bins of 2^37 bytes each, where bin n exclusively manages objects of size S <= 2^(A+n). The root table manages the freelist and currently used capacity of each bin. Because all objects within a bin use the same stride, the bin's allocator can be implemented as a simple array allocator with support for unused slots, removing much of a compacting allocator's complexity and fixing any theoretical issues of heap fragmentation, at the cost of a clearly bounded overhead O < S + ceil(S/64) + 16 for allocations of size S smaller than the virtual memory system's page size.
Each allocated object consists of the requested free memory, a pointer bitmap and a header, in this order.
The pointer bitmap is of size ceil(S/64) and encodes for each aligned uint64 within the object's memory whether it is raw data (0), or a pointer (1). This pointer should be treated as opaque data; it must be a hard or soft arcpointer, an archandler, or any other valid non-relocatable pointer to data outside the arcmem heap. All arcpointers and archandlers contained within an object must be tagged. The tagging of classic non-relocatable pointers outside the arcmem is undefined.
object_header_t is a 16 byte management structure stored at the end of each allocation, consisting of an atomic int32 hard pointer count, an atomic uint32 value of which 21 bits are used for a "version" counter by soft pointers, and 11 bits remain unused, as well as a uint64 field that encodes the originally requested size of the object, and which doubles as a temporary pointer to be used for chaining during free operations.
Alternatively, headers and bitmaps may be stored within separate mirroring pools (as the arithmetic to convert from pool pointer to header or bitmap address requires no memory reads either way), allowing pointers to cover the entire exp2 range of the object, but this makes it harder to detect stray writes past the allocated region, and requires threads operating on neighboring allocations to synchronize their bitmap operations within single bytes. Which approach is better is still an object of research.
A valid arcpointer p either carries the special value null or has an address within the pool's range. Due to the specified layout, bits 37 to 42 happen to both encode the conservative size of the object as p{37:42} = ceil(log2(S)) - A, as well as the number of least significant bits of the pointer that may be altered by an arithmetic operation (minus the tailing header size).
This clearly bounds the range of an arcpointer and turns it into an iterator. Both pointer bitmap and header addresses can be computed from an arcpointer's address, allowing an arcpointer to hold an object from any offset. This does away with the commonly applied restriction of reference counting forcing pointers to observe object granularity, and complicating and bloating data structures in the process.
Arcpointers are either hard or soft. Hard arcpointers are used to reference objects that must be kept in memory, and as such, the hard reference count stored in the object header is incremented and decremented when a hard arcpointer is assigned, duplicated or released. When the reference count reaches zero, the object is deallocated, and the reference count on hard arcpointers that it holds decreased in turn.
Soft arcpointers, on the other hand, are used to reference objects weakly. They are stored in a C-incompatible format that needs to be "upgraded" to a hard arcpointer before they become usable. Soft arcpointers can be recognized by their bit 63 being set. Bits 42 to 63 encode the version of the object for which the soft arcpointer was crafted.
A soft arcpointer is "upgraded" by an atomic compare-and-swap operation simultaneously performed on both the object's hard pointer count and version counter, and if successful, a reference has been granted and the soft arcpointer is transformed into a hard arcpointer.
A soft arcpointer is only valid as long as the version counter in the object's header is equal to the version encoded in the soft arcpointer. After the version counter has been incremented, any attempt to upgrade it will fail, preventing a pointer dangle. The version counter is always incremented when the hard pointer count of an object drops to zero, allowing the allocation to be reused immediately. In addition, users may use object versioning to implement their own mutation-related invalidation abstractions.
to be continued