Memory Layout of mixed types

help
1

Hi everyone,

I'm trying to implement a data structure of consecutive ring-buffers. Each ring buffer consists of a head and tail index, and a variable number of elements T. At any point in time, all ring-buffers contain the same capacity of elements.

I want the ring-buffers to sit consecutively in contiguous memory. So it should look something like this in memory: [ {head, tail}, MaybeUninit<T>, MaybeUninit<T>, MaybeUninit<T>, MaybeUninit<T>, {head, tail}, MaybeUninit<T>, MaybeUninit<T>, MaybeUninit<T>, MaybeUninit<T>, ... ]. You could reason about this as a mixed-type vector, but I'm not sure if that's helpful.

I'm reaching out because I'm stumped on how to implement this data structure in Rust. I'm not sure how to do it safely, and also not sure how to do it unsafely.

Does anyone have any pointers or advice? If I were to do it unsafely, would I just go about doing it the way I would do it in C? If there are reference implementations in the wild of something similar, I would love to take a look.

I understand I can trivially implement this as a Vec<{head, tail, Vec<T>}>, but I need to eliminate the pointers (Vec<T>) to cut down on cache misses. I've also implemented a version like this: { offsets: Vec<{head, tail}>, data: Vec<T>}, but we want the head and tail indexes to be co-located with their relevant data for cache locality. I'm currently benchmarking the two previous implementations to check these assumptions.

If I recall C correctly, I would need the following to be successful:

  • pointer to allocated memory region
  • size of memory region
  • size of head and tail indexes
  • size of data T
  • number of elements T per ring-buffer

I could then use pointer arithmetic to access any individual ring-buffer in the region.

Thank you for reading all of this, I really appreciate it. I'm also happy to provide further explanations for my requirements.

2

If the capacity may be a compile-time constant, then you want

Vec<(usize, usize, [MaybeUninit<T>; N])>

(or a struct containing the same data as that tuple). If the capacity should vary, then you're going to have to do some unsafe work to calculate offsets manually, but you can express each buffer as a

#[repr(C)]
struct Buffer<T> {
    head: usize,
    tail: usize,
    elements: [MaybeUninit<T>],   // slice, not array!
}

and construct pointers or references to that type by using ptr::slice_from_raw_parts[_mut] and casting the type of the pointer afterward. (In the future, that could be done more cleanly with the ptr_metadata unstable feature.)

Largely, but you should use Layout as much as you can, rather than pure pointer arithmetic which doesn't know you're trying to lay out a data structure. And remember that when you return a reference (not a raw pointer) you need to make sure you obey the reference rules (e.g. don't produce aliasing &muts).

6 Likes
3

I think this approach is likely the most viable for me. Thank you!

I'll try it and update the channel with results!

1 Like
4

I've written a working example of my use case laying out these unsized ring-buffers consecutively in memory, but I feel it's hacky and not likely to be the best approach in terms of code cleanliness and performance.

Here's a list of things I do currently that stand out to me as areas of improvement:

  • Allocating and storing a *mut u8 via Vec and casting to fat pointers later
  • Multiple derefs of the same unchanged pointer
  • Not handling drop behavior - how should this be done?

My working example can be found at this playground.

I wanted to note that this thread was especially helpful in understanding the basic approach.

If someone could look this over and give their advice, I would really appreciate it!

5

This is okay if you're doing it right, but you're doing it wrong — the Vec and its allocation is freed as soon as it's created. You need to “forget” the Vec instead of discarding it. The cleanest way to do this currently available is to wrap the Vec in a mem::ManuallyDrop before taking the pointer.

Miri instantly detects this. You should always test unsafe data structure code under Miri. (It's available under the Tools menu in the Playground, or you can run it locally too.)

There are many ways to do this, including:

  • Drain your collection: whatever operation you have for removing elements, call that repeatedly until no elements remain. This has the advantage of needing no new unsafe code, but it may be slower.

  • Inside a impl Drop for ConsecutiveRingBuffers, construct slice pointers to the entire contents of each ring buffer (this may require two each depending on the state of the buffer), then call ptr::drop_in_place() on each one. You can have a look at how VecDeque does it.

2 Likes
6

You’re allocating the buffer via Vec<u8>, which has alignment 1. usize (and likely also T) has a larger alignment requirement than this, so it’s UB to generate & or &mut references to pretty much anything inside the buffer right now. You’ve basically got two routes to fix this:

  • Use ptr::read_unaligned everywhere instead of generating references
  • Change your allocation strategy to be alignment-aware

Edit: I updated your code to hopefully fix the alignment issues, but there’s still a missing Drop implementation for RingBuffer<T>. Miri doesn’t complain anymore, but this isn’t really my area of expertise— There may still be something quite wrong.

2 Likes
7

Thank you both for your help and advice!

@2e71828 your playground link was really helpful, I would have been lost without it. Thanks again!

8

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.