Crate ringal

RingAl - A High-Performance Ring Allocator

RingAl is a blazing-fast ring allocator optimized for short-lived buffer allocations. It uses a circular allocation pattern, which grants low-cost allocations as long as allocations are ephemeral. Long-lived allocations can degrade performance by clogging the allocator.

Key Features

1. Preallocation Strategy: Establish a fixed-size backing store of N bytes.
2. Efficient Small Buffer Management: Allocate smaller buffers efficiently within the preallocated store.
3. Thread-Safe Operations: Buffers can be safely shared across threads, offering clone optimizations similar to Arc.
4. Timely Buffer Deallocation: Buffers should be dropped before the allocator wraps around to reuse the same memory, ensuring optimal recycling.

RingAl focuses on efficient memory management with a dynamic memory pool that evolves its backing store using something called guard sequences. Guard sequences are usually exclusively owned by allocator when they are not locked (i.e. not guarding the allocation), and when they do become locked, the memory region (single usize) backing the guard sequence, is only accessed using Atomic operations. This allows for one thread (the owner of buffer) to release the guard (write to guard sequence), when the buffer is no longer in use and the other thread, where allocator is running, to perform synchronized check of whether guard sequence have been released.

The design allows for safe multi-threaded access: one thread can write while one other can read. If a buffer is still occupied after allocator wraps around, the allocation attempt just returns None, prompting a retry.

Note: RingAl itself isn’t Sync, so it cannot be accessed from multiple threads concurrently. Instead, using thread-local storage is encouraged.

Allocation Strategies

• Exact Fit: Perfectly matches the requested and available sizes.
• Oversized Guards: Splits larger regions to fit the requested size, potentially causing fragmentation.
• Undersized Guards: Merges smaller regions to accommodate requests, aiding in defragmentation.
• Capacity Constraints: Fails if the backing store cannot satisfy the request, signaling with None.

Optional Features

1. tls (Thread-Local Storage): Enables allocation requests without explicitly passing the allocator. It uses RefCell for thread-local data, offering convenience at a minor performance cost.
2. drop (Early Deallocation): Allows the allocator to deallocate its resources upon request. If activated, it employs a Drop implementation that ensures no memory leaks by blocking until all buffers are released.

Usage Examples

Extendable Buffer

let mut allocator = RingAl::new(1024);
let mut buffer = allocator.extendable(64).unwrap();
let msg = b"hello world, this message is longer than allocated capacity...";
let size = buffer.write(msg).unwrap();
let fixed = buffer.finalize();
assert_eq!(fixed.as_ref(), msg);
assert_eq!(fixed.len(), size);

Fixed Buffer

let mut allocator = RingAl::new(1024);
let mut buffer = allocator.fixed(256).unwrap();
let size = buffer.write(b"hello world, short message").unwrap();
assert_eq!(buffer.len(), size);
assert!(buffer.spare() >= 256 - size);

Multi-threaded Environment

let mut allocator = RingAl::new(1024);
let (tx, rx) = channel();
let mut buffer = allocator.fixed(64).unwrap();
let _ = buffer.write(b"message to another thread").unwrap();
let handle = std::thread::spawn(move || {
    let buffer: FixedBufMut = rx.recv().unwrap();
    let readonly = buffer.freeze();
    for _ in 0..16 {
        let msg: FixedBuf = readonly.clone();
        let msg_str = std::str::from_utf8(&msg[..]).unwrap();
        println!("{msg_str}");
    }
});
tx.send(buffer);
handle.join().unwrap();

Generic buffers

struct MyType {
    field1: usize,
    field2: u128
}
let mut buffer = allocator.generic::<MyType>(16).unwrap();
buffer.push(MyType { field1: 42, field2: 43 });
assert_eq!(buffer.len(), 1);
let t = buffer.pop().unwrap();
assert_eq!(t.field1, 42);
assert_eq!(t.field2, 43);

Thread Local Storage

// init the thread local allocator, should be called just once, any thread
// spawned afterwards, will have access to their own instance of the allocator
ringal!(@init, 1024);
// allocate fixed buffer
let mut fixed = ringal!(@fixed, 64).unwrap();
let _ = fixed.write(b"hello world!").unwrap();
// allocate extendable buffer, and pass a callback to operate on it
// this approach is necessary as ExtBuf contains reference to thread local storage,
// and LocalKey doesn't allow any references to exist outside of access callback
let fixed = ringal!{@ext, 64, |mut extendable| {
    let _ = extendable.write(b"hello world!").unwrap();
    // it's ok to return FixedBuf(Mut) from callback
    extendable.finalize()
}}.unwrap();
println!("bytes written: {}", fixed.len());

Safety Considerations

While unsafe code is used for performance reasons, the public API is designed to be safe. Significant efforts have been made to ensure no undefined behavior occurs, offering a safe experience for end-users.

Structs

ExtBuf

Extendable buffer. It dynamically grows to accomodate any extra data beyond the current capacity, given that there’s still some capacity available to allocator itself. Contains a reference to allocator, thus it effectively locks the allocator, and prevents any further allocations while any instance of this type exist. After the necessary data is written, the buffer should be finalized in order to release allocator lock and make the underlying buffer Send

FixedBuf

Immutable and cheaply cloneable buffer

FixedBufMut

Fixed length (not growable) mutable buffer

GenericBufMut

Mutable fixed buffer, which is generic over its elements T, with Vec<T> like API

RingAl

Ring Allocator, see crate level documentation on features and usage