Salvaging Allocator
A patented real-time storage allocator that is free from internal fragmentation and delivers high alignment.

Why Salvaging Allocator?

Binary Buddy allocation, which is attributed to Harry Markowitz, and was first described by Kenneth C. Knowlton in 1965, is a widely used technique for allocating and deallocating memory in systems and devices that contain storage that requires dynamic allocation and deallocation. However, the algorithm of the Binary Buddy allocation only able to allocate and deallocate blocks whose size is power of 2 (2, 4, 8, 16, ...); hence, the difference between the amount of storage requested and the nearest larger power of 2 become wasted. This form of waste causes internal fragmentation as the unused storage is internal to the block the allocator returns for a request, so it is unavailable to service other requests.

Salvaging Allocator modifies the original Binary Buddy allocator while objects on the freelist have binary size, as in the original. When requested to allocate an object of block size (N bytes) where N is not a power of 2 (in the below example is 9), the algorithm first obtains a binary block B of the smallest size that can accomodate N, then splits B into one N-sized object (which is returned to the caller), and smaller binary fragments whose sizes sum exactly to the leftover space within B.

This splitting is done right-to-left, with bigger fragments at the right (higher addresses) and smaller fragments at the left (lower addresses). These binary fragments are put on the freelists where they are available for subsequent allocation. In order to prevent them from being merged with (part of) the N-byte object, they are marked as having a maximum permissible size equal to their actual size when they are first created. They may be subsequently split further but they cannot be merged to a larger size until their maximum permissible size is changed.

When an object is released, it is similarly decomposed into binary fragments, and each of these fragments put onto the freelists and merged with free buddies. This time the decomposition works from right to left but with smaller binary fragments at the right and larger ones at the left.

When freeing an object, if its buddy is to its right (at a higher address) and is not free, then the buddy's maximum permissible size is set to the freed object's maximum permissible size. This indicates that when the buddy is subsequently freed, it may be merged to a higher size. This strategy is sufficient to guarantee that all released objects will be coalesced with their buddies regardless of the order in which they are deallocated.

Alignment Property of Salvaging Allocator

The alignment in the Salvaging Allocator fully benefits from the original Binary Buddy allocator, meaning a memory address (a) of data is aligned when (a) is a multiple of power of 2 bytes. And when the lowest k bits of address are 0, the memory address is aligned on the 2k boundary.

The alignment increases the system’s performance during data access and all storage devices benefit from aligned addresses. Virtually all storage devices and memory systems read and write large blocks using aligned addresses. The Salvaging Allocator performs remarkably by naturally forcing all allocations to lie on aligned addresses.

REAL-TIME Allocator

In a real-time allocator, the worst-case execution time for memory allocation and deallocation is guaranteed to be greater than a fixed time.

Detecting Memory Leaks

The algorithm also permits a very lightweight test for full release of storage (no memory leaks) at program shutdown (or any point at which all objects should be released). By counting the number of blocks returned by OS malloc, verifying that this number of blocks is on the freelist and each one is at full size, we can safely conclude that there is no leaked storage. There is essentially no overhead during allocation and deallocation needed to support this; only the count of calls to OS malloc is required beyond the information stored in the blocks and freelists.

Overall, Salvaging Allocator provides a real-time allocator that supports arbitrary request sizes, high alignment, and internal fragmentation bounded by a constant, with the same time and space bounds as the original Binary Buddy allocator.

The Salvaging Allocator is patented. See US Patent 10,606,741 and Google Patents. It is made available under a hybrid end-user license agreement: either the GPLAv3 or a standard commercial license.

Explore Performance Tests