Crate ringal

Source
Expand description

RingAl - Efficient Ring Allocator for Short-lived Buffers

RingAl is a highly efficient ring allocator designed specifically for the allocation of short-lived buffers. The allocator operates in a circular manner, which allows for fast and inexpensive buffer allocations, provided they are ephemeral in nature. It is crucial that these allocations are short-lived; otherwise, the allocator may become clogged with long-lived allocations, rendering it inefficient.

§Primary Use Case:

  1. Preallocation: Establish a backing store of size N bytes.
  2. Small Buffer Allocation: Allocate buffers from the backing store, where M < N.
  3. Buffer Utilization: Use the allocated buffer across threads if necessary. Buffers can be cloned efficiently, akin to using an Arc.
  4. Timely Deallocation: Ensure buffers are dropped before the allocator cycles back to the same memory region.
  5. Recycled Storage: Upon buffer deallocation, the backing store becomes available for subsequent allocations.

RingAl library focuses on a robust and versatile memory management system, through the use of dynamic and self descriptive backing store. This system is engineered to accommodate a wide range of allocation requirements through the use of guard sequences. These guard sequences are capable of adjusting dynamically to different allocation conditions by being created, modified, and removed as necessary. The system effectively manages these memory guards using a single usize head pointer.

The design is structured to ensure both safe and efficient multithreaded buffer operations. It grants exclusive write access to one thread while allowing another thread to read simultaneously. Although this design does inevitably lead to race conditions, particularly when the writing thread releases the buffer, without proper synchronization with reading or allocating thread, these issues are addressed through a method of optimistic availability checks. If the allocating thread finds a buffer in use, it returns None, indicating to the caller to retry the operation. This method avoids the need for expensive atomic synchronization by relying on eventual consistency, which is suitable for the use cases of this allocator.

It is important to note that this allocator is not marked as Sync, which restricts its concurrent use across multiple threads. All allocation actions require &mut self, inherently preventing the allocator from being enclosed within an Arc. Using locks around the allocator is not recommended as it can greatly reduce performance; instead, it is advisable to use thread-local storage.

§Guard sequence insights:

Each guard encodes:

  1. A flag indicating whether the guarded memory region is in use.
  2. The address of the next guard in the backing store.

§Allocation Scenarios:

When an allocation request is made, RingAl assesses the current guard, which can result in one of four scenarios:

  1. Exact Fit: The requested size matches the guarded region. The guard is marked as occupied, the pointer shifts to the next guard, and the buffer is returned.
  2. Oversized Guard: The guarded region exceeds the requested size. The region is split, a new guard is established for the remainder, and the buffer of the requested size is returned. This can lead to fragmentation.
  3. Undersized Guard: The guarded region is smaller than required. The allocator proceeds to merge subsequent regions until the requested size is met, effectively defragmenting the storage. Only the initial guard persists.
  4. Insufficient Capacity: Even after merging, the accumulated buffer is insufficient. The allocation fails, returning None.
   allocator
      |
      v
-----------------------------------------------------------------------------------
| head canary | N bytes | guard1 | L bytes | guard2 | M bytes | ... | tail canary |
-----------------------------------------------------------------------------------
     |                    ^   |              ^   |              ^ |          ^
     |                    |   |              |   |              | |          |
     ----------------------   ----------------   ---------------- ------------
     ^                                                                       |
     |                                                                       |
     -------------------------------------------------------------------------

Note: Head and Tail canaries are standard guard sequences that persist, with the Tail canary perpetually pointing to the Head, forming a circular (ring) structure.

§Features

  1. Dynamic Fragmentation and Defragmentation: Facilitates variable-size allocations through adaptive backing store management.
  2. Extendable Buffers: Allow dynamic reallocations akin to Vec<u8>, typically inexpensive due to minimal pointer arithmetic and no data copy. Such reallocations may fail if capacity limits are reached.
  3. Fixed-Size Buffers: Unexpandable but more efficient due to simpler design, with safe cross-thread transportation. They make storage available upon deallocation.
  4. Read-Only Buffers: Fixed-size buffers that are easily cloneable and distributable across multiple threads. These involve an additional heap allocation for a reference counter and should be avoided unless necessary to prevent overhead.

§Optional Crate Features (Cargo)

  1. tls (Thread-Local Storage): This feature enables advanced functionalities related to thread-local storage within the allocator. By activating tls, developers can initiate allocation requests from any point in the codebase, thereby eliminating the cumbersome need to pass the allocator instance explicitly. This enhancement streamlines code ergonomics, albeit with a slight performance trade-off due to the utilization of RefCell for managing thread-local data.
  2. drop (Allocator Deallocation): Typically, the allocator is designed to remain active for the duration of the application’s execution. However, in scenarios where early deallocation of the allocator and its associated resources is required, activating the drop feature is essential. This feature implements a tailored Drop mechanism that blocks (by busy wating) the executing thread until all associated allocations are conclusively released, subsequently deallocating the underlying storage. It is critical to ensure allocations do not extend significantly beyond the intended drop point. Failure to enable this feature will result in a memory leak upon attempting to drop the allocator.

§Usage examples

§Extendable buffer

let mut allocator = RingAl::new(1024); // Create an allocator with initial size
let mut buffer = allocator.extendable(64).unwrap();
// the slice length exceeds preallocated capacity of 64
let msg = b"hello world, this message is longer than allocated capacity, but buffer will
grow as needed during the write, provided that allocator still has necessary capacity";
// but we're still able to write the entire message, as the buffer grows dynamically
let size = buffer.write(msg).unwrap();
// until the ExtBuf is finalized or dropped no further allocations are possible
let fixed = buffer.finalize();
assert_eq!(fixed.as_ref(), msg);
assert_eq!(fixed.len(), size);

§Fixed buffer

let mut allocator = RingAl::new(1024); // Create an allocator with initial size
let mut buffer = allocator.fixed(256).unwrap();
let size = buffer.write(b"hello world, this message is relatively short").unwrap();
// we have written some some bytes
assert_eq!(buffer.len(), size);
// but we still have some capacity left for more writes if necessary
assert!(buffer.spare() >= 256 - size);

§Multi-threaded environment


let mut allocator = RingAl::new(1024); // Create an allocator with initial size
let (tx, rx) = channel();
let mut buffer = allocator.fixed(64).unwrap();
let _ = buffer.write(b"this a message to other thread").unwrap();
// send the buffer to another thread
let handle = std::thread::spawn(move || {
    let buffer: FixedBufMut = rx.recv().unwrap();
    // from another thread, freeze the buffer, making it readonly
    let readonly = buffer.freeze();
    let mut handles = Vec::with_capacity(16);
    for i in 0..16 {
        let (tx, rx) = channel();
        // send the clones (cheap) of readonly buffer to more threads
        let h = std::thread::spawn(move || {
            let msg: FixedBuf = rx.recv().unwrap();
            let msg = std::str::from_utf8(&msg[..]).unwrap();
            println!("{i}. {msg}");
        });
        tx.send(readonly.clone());
        handles.push(h);
    }
    for h in handles {
        h.join();
    }
});
tx.send(buffer);
handle.join();

§Thread Local Storage

ringal!(@init, 1024);
// allocate fixed buffer
let mut fixed = ringal!(@fixed, 64).unwrap();
let _ = fixed.write(b"hello world!").unwrap();
// allocate extendable buffer and write some data to it
ringal!{@ext, 64, |mut extendable| {
    let _ = extendable.write(b"hello world!").unwrap();
    extendable.finalize()
}};

§Dependencies

The crate is designed without any external dependencies, and only relies on standard library

§Planned features

  • Allocation of buffers with generic types

§Safety

This library is the epitome of cautious engineering! Well, that’s what we’d love to claim, but the truth is it’s peppered with unsafe blocks. At times, it seems like the code is channeling its inner C spirit, with raw pointer operations lurking around every corner. But in all seriousness, considerable effort has been devoted to ensuring that the safe API exposed by this crate is truly safe for users and doesn’t invite any unwelcome Undefined Behaviors or other nefarious calamities. Proceed with confidence…

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
  • RingAl
    Ring Allocator, see crate level documentation on features and usage