The goal here is more "reinvent the wheel for learning" rather than "find production level binding."
Is there a tutorial somewhere on implementing a b-tree with 4k page aligned nodes in Rust ?
This seems like the type of thing that will involve lots of unsafe operations and I am curious to see the idiomatic way to do it in Rust.
This is my fault for not being clearer in the original requirement. I'm looking for something that can be the backing for a kv store, so I'm looking for something where we:
(1) mmap a file
(2) create the b-tree / b+-tree nodes on page aligned boundaries
I'm not (yet) convinced anything using Rust's Vec allows that level of control.
You are on the right track. Get some memory via mmap and then raw pointers …
At some point you probably want to turn it into references and slices to let the borrowchecker help you.
Writing an allocator (what you are doing) is fundamentally unsafe.
I suspect this will end up with C-style b-tree written in Rust, i.e. *const u8 and *mut u8 everywhere. I'm hoping someone has figured out a "more rust" way to do this.
I think the simplest way would be that each node owns a page and its children.
That way you only need to make sure your unsafe code allocates and de-allocates correctly. All other B-Tree code can then be in safe rust.
You can use #[align(4096)] to force a struct definition to always be placed on a 4k page boundary. Once you’ve done that, there’s a good chance (but no guarantee) that pointer manipulation of these structures will be implemented inside the kernel by updating the virtual memory table instead of copying bytes around.
If every node is placed on a different memory page, won't you get terrible performance when traversing the tree or are you dealing with data that is inherently large enough to fill more than half a page per node, that it makes sense to choose an alignment like that?
BTrees generally pack several items per node with a large branching factor. They’re designed specifically for hybrid storage systems (like virtual memory) with blocks that are slow to fetch but have fast random access once loaded. The struct definition would contain an array of child elements, presumably sized to almost fill a 4k-page.
This is interesting. Howsever, I believe we need it to be "page aligned inside the mmaped file", not merely page-mapped. This seems somethig hard to guarantee unless we are decoupjling the "malloc" from the "init" of the struct. (Perhaps there is a nice way to do this in Rust, I am not (yet) familiar with it.)
Right, you’ll need to check the alignment of the pointer you get from mmap, and possibly wrap it in MaybeUninit until you know things are ok. Once that all checks out, you can treat the whole thing as an &mut [MyPageType].
Also, since your page struct is the same size as a page table entry, whenever Rust does a move or other memcopy, the kernel can implement that as a page table write instead of copying bytes around in physical memory.
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.