Struct CircularBuffer 

pub struct CircularBuffer { /* private fields */ }

The circular buffer inspired by FASTER’s ring buffer. It acts mostly like a variable length buffer pool, except that evicting entires are handled by the callback.

Getting this to be correct is quite challenging, especially that we need to support concurrent allocation/deallocation/eviction, and we don’t want a big lock on everything.

Implementations

impl CircularBuffer

pub fn new( capacity: usize, copy_on_access_percent: f64, min_record_size: usize, max_record_size: usize, leaf_page_size: usize, max_fence_len: usize, pre_alloc_ptr: Option<*mut u8>, cache_only: bool, ) -> Self

Create a new circular buffer with the given capacity, the capacity has to be a power of two and large enough to hold at least one leaf page.

TODO: I don’t like the fact that we require users to set cache capacity to be power of two just because it is easy to do modulo. We should actually investigate how much performance is actually gained by requiring power of two.

TODO: I don’t think we should ever expose the copy_on_access_percent to user, it is an internal implementation detail.

use bf_tree::circular_buffer::CircularBuffer;
let buffer = CircularBuffer::new(4096 * 2, 0.1, 64, 1952, 4096, 32, None, false);

pub fn get_metrics(&self) -> CircularBufferMetrics

Returns the metrics of CircularBuffer. Note that this is a very slow, exclusive operation, it essentially stops all other operations, so use it with caution.

You should only use it for debugging and testing.

pub fn alloc( &self, size: usize, ) -> Result<CircularBufferPtr<'_>, CircularBufferError>

Allocate a piece of memory from the circular buffer, returns a guard that will panic if not used.

Ignores alignment, always align to 8 Returns None if we have no free space, which caller needs to call CircularBuffer::evict_one or CircularBuffer::evict_n.

use bf_tree::circular_buffer::CircularBuffer;
let mut buffer = CircularBuffer::new(4096 * 2, 0.1, 64, 1952, 4096, 32, None, false);

let allocated = buffer.alloc(128);
let ptr = allocated.unwrap().as_ptr();

let v = unsafe { buffer.acquire_exclusive_dealloc_handle(ptr).unwrap() };
buffer.dealloc(v); // dealloc is mandatory before buffer being dropped.

pub fn ptr_is_copy_on_access(&self, ptr: *mut u8) -> bool

Returns whether the pointer is inside copy-on-access region. Useful to detect if the ptr is about to be evicted.

If a ptr is close to head, it is copy on access. If a ptr is close to tail, it is inplace updatable.

pub fn dealloc(&self, ptr: TombstoneHandle)

Deallocates the given address. Deallocate is mandatory before the buffer being dropped.

It panics if the ptr is already dealloced, so double free is not allowed.

use bf_tree::circular_buffer::CircularBuffer;
let mut buffer = CircularBuffer::new(4096 * 2, 0.1, 64, 1952, 4096, 32, None, false);

let allocated = buffer.alloc(128);
let ptr = allocated.unwrap().as_ptr();

let v = unsafe{ buffer.acquire_exclusive_dealloc_handle(ptr).unwrap() };
buffer.dealloc(v); // dealloc is mandatory before buffer being dropped.

pub unsafe fn check_ptr_is_ready(ptr: *mut u8)

Check if the ptr is accessible.

Safety

The ptr must be allocated by this buffer.

pub unsafe fn acquire_exclusive_dealloc_handle( &self, ptr: *mut u8, ) -> Result<TombstoneHandle, CircularBufferError>

Set the ptr’s state to be tombstoning, no future access is allowed, no concurrent tombstoning is allowed. This is the required call before you can deallocate the ptr.

Returns the handle that you can use to deallocate the ptr. Or Err if contention happened.

This call is necessary because two concurrent threads can deallocating the same ptr at the same time:

1. thread A deallocates the ptr normally,
2. thread B deallocates the ptr by calling evict_n

This causes contention and unnecessary complexity to handle the race. It is possible for user to coordinate the two threads, but I feel like it is better to handle it in the library. I’m not 100% sure this is the best way to do it. If you are reading this, it’s a good time to revisit the design.

Some other thoughts: This is essentially a x-lock, whoever wins gets to deallocate/evict. Why not directly expose a locking API? While it is possible, I don’t like it because we will have too many places to lock. In a complex system like bf-tree, the more place to lock, the higher mental burden to the maintainer. I want bf-tree to be simple to maintain.

The next question is: if we don’t want so many places to lock, why do we have to lock here? Why not directly expose the raw bare minimal API, and let users to coordinate the locking? Readers of this comment should think carefully and consider it as a refactoring opportunity.

The very high level question here is: what is the safest and efficient interface of a circular buffer that serves our use case?

Safety

The ptr must be allocated by this buffer.

pub fn evict_n<T>( &self, n: usize, callback: T, ) -> Result<u32, CircularBufferError>

where T: FnMut(TombstoneHandle) -> Result<TombstoneHandle, TombstoneHandle>,

Evict n items from the buffer, calling callback on each item, and returning (elements that is evicted from callback, the number of bytes the head advanced). This is necessary when the buffer is full, i.e., failed to allocate a new item.

The call back is called on each item. The input handle gives excluesive access to the item, i.e., no other thread can deallocate/evict it. If you failed to evict the item, return Err, and eviction will release the handle and restart the eviction again.

use bf_tree::circular_buffer::CircularBuffer;
let mut buffer = CircularBuffer::new(1024 * 2, 0.1, 64, 256, 1024, 32, None, true);

for _i in 0..7 {
    let alloc = buffer.alloc(256).unwrap();
    unsafe { *alloc.as_ptr() = 42 };
    drop(alloc);
}

let not_allocated = buffer.alloc(400);
assert!(not_allocated.is_err());
drop(not_allocated);

buffer.evict_n(
    usize::MAX,
    |h| {
        let ptr = h.as_ptr();
        assert_eq!(unsafe { *ptr }, 42);
        Ok(h)
    },
);

let allocated = buffer.alloc(400).unwrap();
let ptr = allocated.as_ptr();
drop(allocated);
let v = unsafe { buffer.acquire_exclusive_dealloc_handle(ptr).unwrap() };
buffer.dealloc(v);

pub fn drain<T>(&self, callback: T)

where T: FnMut(TombstoneHandle) -> Result<TombstoneHandle, TombstoneHandle>,

Drain the buffer, calling the callback on each item.

pub fn evict_one<T>(&self, callback: &mut T) -> Option<u32>

where T: FnMut(TombstoneHandle) -> Result<TombstoneHandle, TombstoneHandle>,

Evict one element from the buffer, it never fails. Returns the number of bytes the head advanced. Return None if the buffer is empty.

This is a complex function, the design goal is to not holding a lock while waiting for IO. This is two step process: (1) take the lock and make the reservation: bump the evicting address (2) evict the data, potentially long running IO call. (3) finish the reservation: bump the head address to the evicting address

Trait Implementations

impl Debug for CircularBuffer

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Drop for CircularBuffer

fn drop(&mut self)

Executes the destructor for this type.