LLFree: Scalable and Optionally-Persistent Page-Frame Allocation

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

Abstract

Within the operating-system’s memory-management subsystem, the page-frame allocator is the most fundamental component. It administers the physical-memory frames, which are required to populate the page-table tree. Although the appearance of heterogeneous, nonvolatile, and huge memories has drastically changed the memory hierarchy, we still manage our physical memory with the seminal methods from the 1960s.

With this paper, we argue that it is time to revisit the design of page-frame allocators. We demonstrate that the Linux frame allocator not only scales poorly on multi-core systems, but it also comes with a high memory overhead, suffers from huge-frame fragmentation, and uses scattered data structures that hinder its usage as a persistent-memory allocator. With LLFree, we provide a new lock- and log-free allocator design that scales well, has a small memory footprint, and is readily applicable to nonvolatile memory. LLFree uses cache-friendly data structures and exhibits antifragmentation behavior without inducing additional performance overheads. Compared to the Linux frame allocator, LLFree reduces the allocation time for concurrent 4 KiB allocations by up to 88 percent and for 2 MiB allocations by up to 98 percent. For memory compaction, LLFree decreases the number of required page movements by 64 percent.

• Slides

Source Code

The source code of the LLFree allocator, the modified Linux kernel, and the benchmarks can be found on GitHub (tag = atc23-artifact-eval).

Artifact

To obtain the raw data of the evaluation results and the necessary programs and scripts to reproduce the experiments and analyses of the paper, please refer to the artifact documentation in our benchmark repository. The paper also contains an artifact appendix with further details.