5 ms·

Interesting alternative idea I thought of just now: a data structure that works like VecDeque (a circular buffer) but uses mmap to map two views onto the same p

Interesting alternative idea I thought of just now: a data structure that works like VecDeque (a circular buffer) but uses mmap to map two views onto the same pages right after one another. That would ensure that the entire array can be accessed in a consecutive fashion, no matter where it gets split, without any copying. The downside is that reallocation would be really slow, involving multiple syscalls, and the minimum size of the array would be 4kB or more, depending on the page size.

duped 2y ago
I've seen this trick used around, where it really shines is when you want to prepare/commit a range of the ring buffer when interfacing with something that wants a contiguous chunk as an arg, using the mmap hack lets you pass any pointer into the ring buffer without needing to split it to handle the wraparound case. There are a few blog posts out there about it, eg https://lo.calho.st/posts/black-magic-buffer/ https://lo.calho.st/posts/black-magic-buffer/. One data structure that works around the limitations is the bip buffer: https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The.... In that article the author talks about the mmap trick.
- pcwalton 2y ago
  Oh, I see, it's actually on Wikipedia [1]. I figured I wasn't the first one to invent the idea :) [1]: https://en.wikipedia.org/wiki/Circular_buffer#Optimization https://en.wikipedia.org/wiki/Circular_buffer#Optimization
- scottlamb 2y ago
  I don't think the bip buffer solves a real problem. Let's say I'm using it as a read buffer. > The upshot of all of this is that on average, the buffer always has the maximal amount of free space available to be used, while not requiring any data copying or reallocation to free up space at the end of the buffer. ... Another possibility which was brought up in the bulletin board (and the person who brought it up shall remain nameless, if just because they... erm... are nameless) was that of just splitting the calls across wraps. Well, this is one way of working around the wrapping problem, but it has the unfortunate side-effect that as your buffer fills, the amount of free space which you pass out to any calls always decreases to 1 byte at the minimum - even if you've got another 128kb of free space at the beginning of your buffer, at the end of it, you're still going to have to deal with ever shrinking block sizes. So it maximizes the contiguous free bytes. I feel like the author just never knew about readv? Passing a couple iovecs completely solves this problem in a much better way. What seems far more valuable for the used space to be contiguous, as parsing APIs often expect this. bip buffers don't offer that, right? Now let's say I'm using it as a write buffer. I've never had the problem of needing it to be contiguous on either side. On the input side, I could imagine some application API that really wants to write into a contiguous buffer, but it hasn't been my experience. On the output side, there's writev.
o11c 2y ago
For C++, that's only valid for some subset of types, which currently can't be expressed with type traits. "Address-free" has a close enough definition in the context of atomics. Trivially moveable types are probably sufficient (at least, I can't construct a case where being trivially copyable is needed), but not necessary; there are many things a special member function can do without caring about the address. In practice, the main problem is that you can't use private mappings (which are the default and for good reason); you have to use shared mapping, which are very finicky to set up and cause infelicities with `fork`. [This does make me wonder how reflinks/`copy_file_range` interact with `mmap` and the page cache.] Really, you should just fix all your APIs to take an `iovec` array.
- eru 2y ago
  > In practice, the main problem is that you can't use private mappings (which are the default and for good reason); you have to use shared mapping, which are very finicky to set up and cause infelicities with `fork`. [This does make me wonder how reflinks/`copy_file_range` interact with `mmap` and the page cache.] Yet another reason fork was never a good design choice.
  - fc417fc802 2y ago
    Is fork really the problem in this scenario?
    - eru 2y ago
      I don't think it's the main problem here, but it's just another point where the fork/exec model shows its problems.
      - fc417fc802 2y ago
        What would you replace fork with? I don't get it. Isn't the desired improvement here to how the kernel handles the lifetime of mappings? It seems orthogonal to me.
- 2y ago
yxhuvud 2y ago
So essentially pushing the work to the TLB? Well, if there are people building moving GCs that manage to retain stable pointers that way, why not use it for a circular buffer as well. > The downside is that reallocation would be really slow, involving multiple syscalls, Scaling ring buffers up and down in size is not very performant anyhow, as a bunch of the elements in it tend to need to be copied.
leiroigh 2y ago
The main problem with that is that it doesn't play nice with most languages. Consider int foo(int* ptr) { int x = ptr[1<<16]; *ptr += 1; return x + ptr[1<<16]; } Compilers/languages/specs tend to decide that `ptr` and `ptr + (1<<16)` cannot alias, and this can be compiled into e.g. foo(int*): mov eax, dword ptr [rdi + 262144] inc dword ptr [rdi] add eax, eax ret which gives undesired results if `ptr` and `ptr + (1<<16)` happen to be mapped to the same physical address. This is also pretty shit to debug/test -- some day, somebody will enable LTO for an easy performance win on release builds, and bad code with a security vuln gets shipped.
- scottlamb 2y ago
  I don't think that's a fundamental problem. In say Rust (with its famously strict aliasing requirements), you obviously need some level of unsafe. You certainly want to ensure you don't hand out `&mut [T]` references that alias each other or any `&[T]` references according to either virtual or physical addresses, but that seems totally possible. I would represent the ring buffer with a raw pointer and length. Then for callers I'd construct `&[T]` and `&mut [T]` regions as needed that are never more than the full (unmirrored) length and thus never include the same byte twice. There are several existing Rust crates for the mirrored buffer that (though I haven't looked into their implementations recently to verify) presumably do this: slice-deque, vmcircbuf, magic-ring-buffer, vmap. I do think though there are some downsides to this approach that may or may not be deal-breakers: * Platform dependence. Each of the crates I mention has a fair bit of platform-specific `unsafe` code that only supports userspace on a few fixed OSs. They fundamentally can't work on microcontrollers with no MMU; I don't think WASM has this kind of flexibility either. * Either setting up each buffer is a bit expensive (several system calls + faulting each page) or you have to do some free-listing on your own to mitigate. You can't just rely on the standard memory allocator to do it for you. Coincidentally just like last week I was saying freelisting is super easy for video frames where you have a nice bound on number of things in the list and a fixed size, but if you're freelisting these at the library level or something you might need to be more general. * Buffer size constraints. Needs to be a multiple of the page size; some applications might want smaller buffers. * Relatedly, extra TLB pressure, which is significant in many applications' performance. Not just because you have the same region mapped twice. Also that the buffer size constraints mentioned above make it likely you won't use huge pages, so on e.g. x86-64 you might use 4 KiB pages rather than 2 MiB (additional factor of 512x) or 1 GiB (additional factor of 262144x) as the memory allocator would help you do if they could be stuffed into the same huge page as other allocations.
gpderetta 2y ago
This is normally called a magic ring buffer, and it is a relatively well known pattern. Very useful for queues when you need to support variable size elements and need to interoperate with code that can't handle split objects.

duped 2y ago

I've seen this trick used around, where it really shines is when you want to prepare/commit a range of the ring buffer when interfacing with something that wants a contiguous chunk as an arg, using the mmap hack lets you pass any pointer into the ring buffer without needing to split it to handle the wraparound case. There are a few blog posts out there about it, eg https://lo.calho.st/posts/black-magic-buffer/ https://lo.calho.st/posts/black-magic-buffer/. One data structure that works around the limitations is the bip buffer: https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The.... In that article the author talks about the mmap trick.

pcwalton 2y ago
Oh, I see, it's actually on Wikipedia [1]. I figured I wasn't the first one to invent the idea :) [1]: https://en.wikipedia.org/wiki/Circular_buffer#Optimization https://en.wikipedia.org/wiki/Circular_buffer#Optimization
scottlamb 2y ago
I don't think the bip buffer solves a real problem. Let's say I'm using it as a read buffer. > The upshot of all of this is that on average, the buffer always has the maximal amount of free space available to be used, while not requiring any data copying or reallocation to free up space at the end of the buffer. ... Another possibility which was brought up in the bulletin board (and the person who brought it up shall remain nameless, if just because they... erm... are nameless) was that of just splitting the calls across wraps. Well, this is one way of working around the wrapping problem, but it has the unfortunate side-effect that as your buffer fills, the amount of free space which you pass out to any calls always decreases to 1 byte at the minimum - even if you've got another 128kb of free space at the beginning of your buffer, at the end of it, you're still going to have to deal with ever shrinking block sizes. So it maximizes the contiguous free bytes. I feel like the author just never knew about readv? Passing a couple iovecs completely solves this problem in a much better way. What seems far more valuable for the used space to be contiguous, as parsing APIs often expect this. bip buffers don't offer that, right? Now let's say I'm using it as a write buffer. I've never had the problem of needing it to be contiguous on either side. On the input side, I could imagine some application API that really wants to write into a contiguous buffer, but it hasn't been my experience. On the output side, there's writev.

o11c 2y ago

For C++, that's only valid for some subset of types, which currently can't be expressed with type traits. "Address-free" has a close enough definition in the context of atomics. Trivially moveable types are probably sufficient (at least, I can't construct a case where being trivially copyable is needed), but not necessary; there are many things a special member function can do without caring about the address. In practice, the main problem is that you can't use private mappings (which are the default and for good reason); you have to use shared mapping, which are very finicky to set up and cause infelicities with `fork`. [This does make me wonder how reflinks/`copy_file_range` interact with `mmap` and the page cache.] Really, you should just fix all your APIs to take an `iovec` array.

eru 2y ago
> In practice, the main problem is that you can't use private mappings (which are the default and for good reason); you have to use shared mapping, which are very finicky to set up and cause infelicities with `fork`. [This does make me wonder how reflinks/`copy_file_range` interact with `mmap` and the page cache.] Yet another reason fork was never a good design choice.
- fc417fc802 2y ago
  Is fork really the problem in this scenario?
  - eru 2y ago
    I don't think it's the main problem here, but it's just another point where the fork/exec model shows its problems.
    - fc417fc802 2y ago
      What would you replace fork with? I don't get it. Isn't the desired improvement here to how the kernel handles the lifetime of mappings? It seems orthogonal to me.
2y ago

yxhuvud 2y ago

So essentially pushing the work to the TLB? Well, if there are people building moving GCs that manage to retain stable pointers that way, why not use it for a circular buffer as well. > The downside is that reallocation would be really slow, involving multiple syscalls, Scaling ring buffers up and down in size is not very performant anyhow, as a bunch of the elements in it tend to need to be copied.

leiroigh 2y ago

The main problem with that is that it doesn't play nice with most languages. Consider int foo(int* ptr) { int x = ptr[1<<16]; *ptr += 1; return x + ptr[1<<16]; } Compilers/languages/specs tend to decide that `ptr` and `ptr + (1<<16)` cannot alias, and this can be compiled into e.g. foo(int*): mov eax, dword ptr [rdi + 262144] inc dword ptr [rdi] add eax, eax ret which gives undesired results if `ptr` and `ptr + (1<<16)` happen to be mapped to the same physical address. This is also pretty shit to debug/test -- some day, somebody will enable LTO for an easy performance win on release builds, and bad code with a security vuln gets shipped.

scottlamb 2y ago
I don't think that's a fundamental problem. In say Rust (with its famously strict aliasing requirements), you obviously need some level of unsafe. You certainly want to ensure you don't hand out `&mut [T]` references that alias each other or any `&[T]` references according to either virtual or physical addresses, but that seems totally possible. I would represent the ring buffer with a raw pointer and length. Then for callers I'd construct `&[T]` and `&mut [T]` regions as needed that are never more than the full (unmirrored) length and thus never include the same byte twice. There are several existing Rust crates for the mirrored buffer that (though I haven't looked into their implementations recently to verify) presumably do this: slice-deque, vmcircbuf, magic-ring-buffer, vmap. I do think though there are some downsides to this approach that may or may not be deal-breakers: * Platform dependence. Each of the crates I mention has a fair bit of platform-specific `unsafe` code that only supports userspace on a few fixed OSs. They fundamentally can't work on microcontrollers with no MMU; I don't think WASM has this kind of flexibility either. * Either setting up each buffer is a bit expensive (several system calls + faulting each page) or you have to do some free-listing on your own to mitigate. You can't just rely on the standard memory allocator to do it for you. Coincidentally just like last week I was saying freelisting is super easy for video frames where you have a nice bound on number of things in the list and a fixed size, but if you're freelisting these at the library level or something you might need to be more general. * Buffer size constraints. Needs to be a multiple of the page size; some applications might want smaller buffers. * Relatedly, extra TLB pressure, which is significant in many applications' performance. Not just because you have the same region mapped twice. Also that the buffer size constraints mentioned above make it likely you won't use huge pages, so on e.g. x86-64 you might use 4 KiB pages rather than 2 MiB (additional factor of 512x) or 1 GiB (additional factor of 262144x) as the memory allocator would help you do if they could be stuffed into the same huge page as other allocations.

gpderetta 2y ago

This is normally called a magic ring buffer, and it is a relatively well known pattern. Very useful for queues when you need to support variable size elements and need to interoperate with code that can't handle split objects.