Lo(ck|g)-free Memory Compaction for Persistent Page Allocators in Linux

In ParPerOS, we examine new OS-level memory management abstractions for new memory technologies. These include for example traditional volatile DRAM and new persistent, non-volatile RAM. The latter keeps its data when the system looses power, similar to a SSD. This persistence property provides several new opportunities for the design of performant and reliable systems.

However, non-volatile memory also poses a number of new challanges for operating systems. In particular, the management of this memory also has to be crash consistent so that this memory can be recovered after a power loss. We currently research a new page allocator for persistent memory. This allocator is lock- and log-free. Both techniques are used to synchronize concurrent access to data and prevent race conditions. However, they do not perform well on persistent memory and systems with many CPU cores. Instead, the allocator relies on specific atomic CPU instructions to synchronize (and persist) parallel updates. The idea is to jump between valid states so that the system can crash at any time without corrupting the allocator's data.

A common problem for allocators is memory fragmentation. Fragmentation can occur if an allocator manages different sized chunks (in our case, between 1 and 1024 pages). Depending on how the memory is allocated, these allocations could be spread out over the memory area, so that only small holes of free memory are left. These holes might be too small for larger allocation, even if combined enough free memory is avaliable. In this case, the allocator is fragmented and has to be manually defragmented. The allocated pages must be moved to other locations to create larger holes to satisfy large allocations. This is called memory compaction. Several memory compaction algorithms have been researched that minimize the number of pages that have to be moved to clear large contiguous chunks.

The goal of this thesis is to research and possibly invent new memory compactions algorithms and implement them for the new lo(ck|g)-free allocator. These algorithms should then be compared against each other on different metrics, like performance, the number of moved pages and the number of cleared large chunks.

The allocator is implemented using the Rust programming language and is beeing integrated in to the Linux Kernel, replacing the current buddy allocator. Therefore, a comparison against the current memory compaction algorithm of the Linux buddy allocator might be interesting.


Further Information