NBBS: A Non-Blocking Buddy System

This repository contains NBBS, a lock-free back-end allocator that adheres to the buddy system specification.

It also keeps several benchmarks and modules to evaluate NBBS and the Linux Kernel Buddy System.

The code targets x86_64 architectures equipped with Linux.

---

Buddy Allocators

Here, you can find several buddy system allocators. In particular:

• 1lvl-nb: this is the classical NBBS implementation discussed in several papers [Cluster'18, CCGrid'19];
• 4lvl-nb: this is the memory optimized version of our NBBS allocator (16x compress ratio);
• the spin-locked version of the above-mentioned allocators (1lvl-sl and 4lvl-sl).

You can configure the allocator by setting the following macro at compile time:

• MIN_ALLOCABLE_BYTES
• MAX_ALLOCABLE_BYTES
• NUM_LEVELS

---

The Benchmark Suite

We provide several benchmarks to evaluate NBBS and other back-end allocators. The benchmarks are built to run also on kernel side, so you can even evaluate the Linux-Kernel buddy system.

Description

• Linux scalability: each thread makes a burst of allocations followed by a burst of memory release operations.
• Thread test: it operates like linux scalability, but the length of bursts is divided by the number of threads.
• Costant occupancy: each thread pre-allocates blocks of different order and makes a burst of allocations followed by a burst of memory release operations.
• Cached allocation: each thread repeatedly allocates and releases an individual memory buffer.

In order to run the benchmark to evaluate the Linux Buddy System (kernel-sl), you need to mount the kernel-bd-api module.

Instructions

• Compile just typing make
• In each benchmark folder you will find one executable for each allocator. Run them by typing ./TB_<bench_name>-<allocator> <num_of_threads> <mem_size>

---

Contacts

For further information about NBBS allocators, please send an email to:

marotta at diag dot uniroma1 dot it

---

Authors

Current:

• Romolo Marotta
• Mauro Ianni
• Alessandro Pellegrini
• Francesco Quaglia

Former:

• Andrea Scarselli