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.

Related Publications

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]

×

BibTex Entry

@inproceedings{wrenger:23:atc,
location = {Boston, MA},
author = {Wrenger, Lars and Rommel, Florian and Halbuer, Alexander and Dietrich, Christian and Lohmann, Daniel},
booktitle = {2023 USENIX Annual Technical Conference (USENIX '23)},
entrysubtype = {Conference},
isbn = {978-1-939133-35-9},
month = {jul},
pages = {897–914},
publisher = {USENIX Association},
title = {{LLFree}: Scalable and {Optionally-Persistent} {Page-Frame} Allocation},
url = {https://www.usenix.org/conference/atc23/presentation/wrenger},
year = {2023},
}

Close

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.

---

 

Typ

Bachelorarbeit

---

 

Status

abgeschlossen

---

 

Supervisors

Lars Wrenger
Daniel Lohmann

---

 

Project

ParPerOS

---

 

Bearbeiter

Helge Misfeldt (abgegeben: 18. Aug 2023)