This is a fairly nice introduction to memory allocation and the syscalls used to implement a memory allocator in a typical Unix userspace.
A nice addition would be a discussion of the binary buddy allocation scheme, which is a fairly simple and elegant algorithm, which is used in some real physical memory allocators (eg Linux). The algorithm is featured in volume 1 of Knuth’s Art of Computer Programming, if someone is interested.
Unfortunately, binary buddy allocation has degenerate fragmentation behavior that's pretty easy to trip on. Hence segregated size classes in most modern allocators.
Segregated size classes are also a performance choice. They burn some address space (which is why we don’t use them on the CHERIoT allocator, which is designed for heaps that are typically under 1MiB) but make allocation very fast. Snmalloc’s fast path is 12 x86 instructions: map from size to size class, pop front element from linked list, branch if list is empty to a slow path that allocates a new chunk for the size class and initialises the linked list.
They also make it easy to have segregated metadata. If each page (or larger chunk) is full of fixed-size things, then you can look up the size of an object by looking up the chunk metadata (some structure indexed by the high bits of the pointer) and you can find the start (and end) of the object with some simple pointer masking. In snmalloc, we use this to provide cheap bounds checks for heap objects (including versions of memcpy that do bounds checks on source and destination if they are heap objects). This mitigation alone blocks a large chunk of arbitrary-code-execution CVEs.
[OP] thasso | a day ago
This is a fairly nice introduction to memory allocation and the syscalls used to implement a memory allocator in a typical Unix userspace.
A nice addition would be a discussion of the binary buddy allocation scheme, which is a fairly simple and elegant algorithm, which is used in some real physical memory allocators (eg Linux). The algorithm is featured in volume 1 of Knuth’s Art of Computer Programming, if someone is interested.
je | 23 hours ago
Unfortunately, binary buddy allocation has degenerate fragmentation behavior that's pretty easy to trip on. Hence segregated size classes in most modern allocators.
david_chisnall | 5 hours ago
Segregated size classes are also a performance choice. They burn some address space (which is why we don’t use them on the CHERIoT allocator, which is designed for heaps that are typically under 1MiB) but make allocation very fast. Snmalloc’s fast path is 12 x86 instructions: map from size to size class, pop front element from linked list, branch if list is empty to a slow path that allocates a new chunk for the size class and initialises the linked list.
They also make it easy to have segregated metadata. If each page (or larger chunk) is full of fixed-size things, then you can look up the size of an object by looking up the chunk metadata (some structure indexed by the high bits of the pointer) and you can find the start (and end) of the object with some simple pointer masking. In snmalloc, we use this to provide cheap bounds checks for heap objects (including versions of memcpy that do bounds checks on source and destination if they are heap objects). This mitigation alone blocks a large chunk of arbitrary-code-execution CVEs.