The Lo(ck|g)-free allocator, short LLFree, is a new cache-optimized, highly-parallel and optionally-persistent page frame allocator. It uses atomic instructions provided by the CPU instead of locks or logging. Its state is self-contained and very dense, consisting of a bitfield with a bit for every page and index data structures above the bitfield that speed up the search for free pages. The whole state of the allocator fits into a small, contiguous memory area, which could be shared between privilege levels, e.g., hypervisor and VM.

This topic aims to do exactly this: share the LLFree allocator between VM and hypervisor to implement a fast memory ballooning algorithm. Memory ballooning is a technique that is used to steal free memory from a VM to give it to another VM that needs it. Because VMs usually do not use all their memory, servers commonly hand out more memory in total to VMs than they have (memory over-commitment). This necessitates a fast algorithm to steal and redistribute memory between VMs. Currently, most memory over-commitment techniques require costly hypervisor-VM calls. Due to its atomicity, LLFree would not need these calls, making it a lot faster.


USENIX Conference A Distinguished Artifact Award
LLFree: Scalable and Optionally-Persistent Page-Frame Allocation
Lars Wrenger, Florian Rommel, Alexander Halbuer, Christian Dietrich, Daniel Lohmann2023 USENIX Annual Technical Conference (USENIX '23)USENIX Association2023Distinguished Artifact Award.
PDF Details Slides [BibTex]

Previous Work

LLC: DeRUSTing the Lo(ck|g)-Free Allocator for a C-Based OS Integration

Porting the LLFree concept from Rust to C, to simplify the integration into C-based OSs.



Lars Wrenger
Daniel Lohmann


Helge Misfeldt (abgegeben: 18. Aug 2023)