Idiomatic Way to Implement Buffer Pool

help
1

Hi, I'm implementing a buffer pool manager. A long time ago I did this in C and now that I am trying it in Rust I am hitting some snags. Note that I'm just working on a single-threaded version for now and will tackle thread safety later.

  1. A buffer pool manager usually allocates a large contiguous buffer of memory upon startup and re-uses that buffer. How do I allocate a contiguous block of memory in Rust? I would assume Vec<Vec<u8>> won't be contiguous because the size of the inner vec can't be known at the time of memory allocation. So I think it must be a slice
type Pool<const NUM_FRAMES: usize, const PAGE_SIZE: usize> = [[u8; PAGE_SIZE]; NUM_FRAMES];

Is this idiomatic? It feels annoying carrying these consts around everywhere.

  1. I believe callers of this API should be borrowing not owning the page so it can be re-used.
pub fn get_page(&'static mut self,  page_id: u64) -> PageRef<NUM_FRAMES, PAGE_SIZE>  {
...

struct PageRef<const NUM_FRAMES: usize, const PAGE_SIZE: usize> {
    pool: &'static mut BufferPool<NUM_FRAMES, PAGE_SIZE>,
    page: &'static [u8],
    page_id: u64,
}

This starts to introduce a lot of lifetimes. I think the BufferPool and all of its pages should be static because they will exist for as long as the process is running but in PageRef I'm determining the lifetime of the borrows of those values, not the values themselves. So what should they be? And if the borrows of pool and page are static, what happens when PageRef is dropped?

  1. The buffer pool has some metadata it updates upon a caller finishing with a page. It seems most idiomatic to implement this in the drop function
impl<'a, const NUM_FRAMES: usize, const PAGE_SIZE: usize> Drop for PageRef<'a, NUM_FRAMES, PAGE_SIZE> {
    fn drop(&mut self) {
        let metadata = self.pool.page_table.get_mut(&self.page_id).expect("page_id not in pool");
        metadata.pins -= 1;
        
        if metadata.pins == 0 {
            self.pool.free_frames.push_back(metadata.frame_index);
            self.pool.page_table.remove(&self.page_id);
        }
    }
}

so I have to return a mutable reference in PageRef but now I have a immutable borrow and a mutable borrow. Is it even possible to return a mutable reference to self? I'm a bit stuck

error[E0502]: cannot borrow `*self` as mutable because it is also borrowed as immutable
  --> src/main.rs:40:80
   |
40 |         return PageRef{ page: &self.pool[metadata.frame_index], page_id, pool: self }; 
   |                               --------------------------------                 ^^^^ mutable borrow occurs here
   |                               |
   |                               immutable borrow occurs here
   |                               this usage requires that `self.pool[_]` is borrowed for `'static`

Any help would be appreciated. Thank you

Playground link

2
  • If you plan to manage it via borrowing, then allocate using Vec<u8> (but see below for why borrowing is probably not a good plan).
  • If you plan to manage it by something that looks like your page_table — numbers that indicate what is used and what is free — then you need to avoid using Vec or borrowing; allocate your memory using std::alloc::alloc(), and manipulate it using raw pointer operations up until the point where you let the user read and write it.

This is probably not true. References/borrows are generally not appropriate for the outputs of a memory allocator (which is the kind of thing you are trying to write), unless the usage of that memory is strictly scoped to a stack frame, and provided by the allocator to a callback (in which case you can use non-'static lifetimes). That's a reasonable kind of thing to write, but probably not what you're actually writing.

What you want to do, most of the time, is transfer ownership of the page. That is, you write a type like Box, which

  • does not have a lifetime (unless the BufferPool as a whole might be dropped, in which case it must have a lifetime of a shared borrow of the pool)
  • dereferences to [u8] or some other type
  • when dropped, returns the memory to the pool

It might or might not be that the way this is implemented is that at startup the BufferPool constructs a bunch of &'static mut [u8]s (say, via allocating and then splitting a Vec<u8>) and then hands them out, and your Box-like returns them to the pool on drop via channels. Or, the Box-like might contain a raw pointer.

Either way, the key is that the Box-like allocation object logically has exclusive ownership of the memory in use, and returns that ownership to the allocator when it is dropped. (Note that “ownership” is not a thing that solely exists in the language itself; it’s an agreement about who is responsible for some data.)

This cannot be correct, regardless of the rest of your design.

  • &mut is an exclusive reference. By having &'static mut here, you're saying nobody else can access the BufferPool, forever, so there can only be one PageRef ever in the program.
  • &'static [u8] is freely copiable, so once it exists, deallocation is prohibited.
  • &'static [u8] does not permit mutation of the data.
  • If the [u8] is borrowed from the BufferPool, then these two references cannot exist simultaneously. This is what your “error[E0502]: cannot borrow *self as mutable because it is also borrowed as immutable” is indicating.
2 Likes
3

I was under impression that BufferPool is an essential part of the Rust runtime. But I never look in the Rust runtime. Thank you for discovering that the functionality is missed in the Rust runtime.

4

A note about building your own memory manager… Alignment is import. For example, buffers for Windows API calls are supposed to be 16 byte aligned. The storage for Vec is only guaranteed to have the alignment of the stored datatype. For u8 that would be a mere one byte alignment. You or the user of your memory manager would be responsible for getting that up to 16 bytes.

1 Like