VRB – Virtual Ring Buffer | Hacker News Reader

VRB – Virtual Ring Buffer

vrb.sourceforge.net

57 pointsingve15 comments

For a similar end result (a circular buffer from which all returned ranges are contiguous) but without OS support for mmap()ing, there's also Bip Buffers[0]. I did an implementation in C [1] designed to be used for zero-copy IPC over shared memory (by way of having a structure with a flexible array member for the actual data).

[0]: http://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-...

[1]: https://github.com/wrl/wwrl/blob/master/src/bip_buffer.c

Thanks for that. (Very long winded article though; you can skip to the diagrams.) Actually, bip buffers are so simple, I feel as if I've just learnt about linked lists for the first time!

This has additional restrictions:

  * (Maximum) item size must be known in advance, and
  * Buffer items must be smaller than half the buffer size, and
  * If items are not suitably sized, buffer fragmentation may result

There are also some cases where the padded size requirement may exceed available non-wrapped space with bip vs VRB or similar. Anyway, most OS support mmap(2) today :).

You're right on the second point and the third, though I reckon the fragmentation isn't appreciably worse than in a regular wrap-around circular buffer. Same goes for the first point. I'm keen to see examples where bip buffers exhibit particular issues relative to circular/ring buffers, however, and if you've got any then please send them along.

The chief use-case for my bip buffer implementation is using a shared memory segment for inter-process communication, and adding mmap() for address mirroring on top of that just seems like a can of worms I'm not particularly interested in opening.

Thx for posting this - I have seen the other techniques, but never seen bip-buffers. Very cool

(2006)

The basic premise is to mmap() the same physical memory twice in a row (in virtual address space). Then you can always point to a contiguous chunk of memory to reference a given object in your queue.

There should be (is there?) an OS designed around zero copy principles. I want to get packets from the network delivered into a block of memory, and then all subsequent parsing and reading occurs on that memory, with OS provided framing and fine grained policy determining how things are interpreted by userspace.

Something like the memory trick used in this virtual ring buffer but far more powerful.

> I want to get packets from the network delivered into a block of memory, and then all subsequent parsing and reading occurs on that memory, with OS provided framing and fine grained policy determining how things are interpreted by userspace.

well, as others have pointed out, dpdk / netmap are a couple of choices available for bypassing the kernel network stack completely, and get stuff directly into userland. once things are there, you can do all protocol specific parsing etc.

this essentially implies that what you 'see' in memory are mmap'ped ring buffers, not the so called PDU's that you are looking for. the number of protocol-stacks available in userland is, however, to the best of my knowledge, quite limited.

for example, there are couple of folks exploring the option of exporting linux-kernel's networking stack as a library under the N.U.S.E (networking in user space) project. details available here: http://people.netfilter.org/pablo/netdev0.1/papers/Library-O... (https://github.com/libos-nuse/net-next-nuse),

if you have a very specific application in mind that you want to tackle e.g. let's say acting as a transparent proxy, forwarding l2 etc. then things are kind of doable. implementing a generic very high performance stacks (where 2-3 cache-misses will wipe out your timing budgets) is kind of hard, imho...

See Intel's DPDK and Tilera's mPIPE.

You can't really do this with TCP though, without changing the hardware. Most modern network adapters support only a scatter/gather list mechanism for receiving/sending packets, but this doesn't work for receiving TCP payloads into contiguous locations, since TCP's data model is a byte stream.

With UDP and SCTP you can do full zero-copy just fine.

An option is to expose the the fragmented packets to the application and let it handle it. For some applications, application levels packets are rarely fragmented in the tcp stream so 0 copy handling of the incoming tcp stream is possible and fall back once in a while to a compacting copy is an option.

A bigger problem is that on the send side you can't reuse the a 0 copy buffer until the remote ack has arrived for that tcp segment which complicates the interface between the application and the tcp stack.

Apart from very purpose specific OSes I don't think anything is designed around it. But there's a lot of work done to enable it on current systems. Linux for example has sendfile(), splice(), socket options for packet mmap (https://www.kernel.org/doc/Documentation/networking/packet_m...), COW on a lot of filesystems (which means zero-copy file copy), etc.

Sometimes you have to do a bit more work to achieve the zero-copy behaviour, but it's available is many cases.

I wouldn't say it's "designed around" it, but FreeBSD's netmap(4) is pretty similar to what you're talking about.

What happens when two apps wanna do different things with that same packet?

Then a copy is made and written to instead. Or maybe the original is unchanged but both apps write to a different place. Additionally, any unchanged fields could be inherited prototypically from the original datum.

You (necessarily) lose zero-copy when the dataflow isn't one-input-one-output.

More detailed explanation plus more in the comments: https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff...

Reply on news.ycombinator.com