Preface#

As mentioned in the README, the motivation for this project came after stumbling across this section on the Wikipedia article for ring/circular buffers:

A circular-buffer implementation may be optimized by mapping the underlying buffer to two contiguous regions of virtual memory. (Naturally, the underlying buffer‘s length must then equal some multiple of the system’s page size.) Reading from and writing to the circular buffer may then be carried out with greater efficiency by means of direct memory access; those accesses which fall beyond the end of the first virtual-memory region will automatically wrap around to the beginning of the underlying buffer. When the read offset is advanced into the second virtual-memory region, both offsets—read and write—are decremented by the length of the underlying buffer.

However, as the README already goes over how the project came to be and how it’s structured, this post will illustrate the mechanism that underpins this specific implementation.

Introduction#

There are few key concepts needed to understand how this works, so I’ll go over them for those unfamiliar with them in order to keep this post as accessible as possible.

Virtual vs. Physical Address Space#

Very succintly, the physical address space is that used by the operating system to directly address the raw memory. However, unless writing code for an actual kernel, the notion of a “memory address” strictly refers to a virtual memory address, and not a physical one.

The important thing to know is that each running program has its own virtual address space, which the operating system keeps track of, and then translates to the actual physical location of the requested memory.

That is to say, two different running programs could have access to same physical memory, and despite that have wholly different addresses being used to refer to it. As such, each running program only has knowledge of its own address space, with the specifics of its inner workings abstracted away, being entirely unaware of the address spaces of any other running programs, akin to completely separate universes (to borrow a poor metaphor).

Memory Mapping#

As opposed to “regular” memory allocation, where one requests memory from the system through functions such as malloc or new, a memory mapping is a more granular way of allocating, or merely mapping a section of the virtual address space to a “memory object” (such as a regular file, a shared block of memory, anonymous system memory—effectively resulting in a regular allocation—or even a device, basically anything one can reasonably read from and/or write to that the operating system can address, although such specifics are outside the scope of this post).

More interestingly, it allows one to request an arbitrary section of the virtual address space, not allowed by other memory allocation methods.

Ring Buffer#

Simply put a ring, or circular buffer, is a data structure characterized by how, as opposed to a traditional buffer, with a well-defined beginning and end, it wraps around back to its beginning, effectively abstracting away bounds-checking, which allows it to be treated as one continuous strip of memory, which makes certain algorithms simpler to implement.

Beginni0ng1h2ast3h098es4a17me5t26opo6l345ogy7as89End

The Brass Tacks#

When it comes down to it, it’s very simple to created a memory-mapped ring buffer.

Taking the following code from the *nix portion of the implementation,

// (1)
int fd = memfd_create(ANONYMOUS_FILENAME, MFD_CLOEXEC);
const int _ = ftruncate(fd, size);
static_cast<void>(_);

// (2)
void *const shm = mmap(nullptr, size * 2zu, PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0l);

// (3)
mmap(shm, size, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_FIXED, fd, 0l);
mmap(static_cast<char*>(shm) + size, size, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_FIXED, fd, 0l);

the logic is as follows:

  1. An anonymous file is created in RAM, and subsequently set to the requested size;
  2. The program requests an unused region of the address space with a length double that of the requested size;
  3. Both halves of the requested section of the address space are mapped to the anonymous file.

To further break it down:

In step one, an anonymous file—in other words, a file that behaves like a regular file but lives in RAM—is created, and a handle (think of it like a file ID) is returned, and immediately truncated to the desired size.

Afterwards, in step two, as mentioned above, mmap returns a rgion of the virtual address space with the specified size is reserved for use.

Note: Neither of the above steps have allocated any memory: memfd_create created the anonymous file, ftruncated altered its metadata to reflect the specified size, and mmap reserved a region of the available virtual address space. When all is said and done, allocation should only occur when the memory is first written to. Additionally the latter step requests the region with the PROT_NONE flag, guaranteeing that it cannot be accessed through that mapping, and, therefore, won’t result in any allocations.

Finally, in step three, the mapping in step two is replaced with two new mappings—one for each half— and this time not to anonymous memory, but to the file created earlier in step one.

Now the reason for this is that we first secure an unused, contiguous region of memory that we can then safely replace in chunks without worry. Had step two been skipped we would be dealing with two big problems:

  1. As the implementation requires two contiguous regions of memory, step three requires that an address is given for the mapping through the use of the MAP_FIXED flag (which has the side-effect of replacing any previous mappings at that address, to our advantage). However, without step two, there would be no way of knowing where or how big any free regions of the virtual address space were.
  2. Even if by some miracle, or simply for the sake of the argument, we had a way of specifying an address that fit those criteria, there would be no guarantee that, between the first and second calls to mmap in step three, some other thread wouldn’t have “snatched”, either partially or totally, the following region of memory.

Step two is therefore imperative in order to guarantee that the region is reserved until it can be remapped by the last two mmap calls.

A Simple Visualization#

To better understand how the above procedure manipulates the address spaces, the diagram below compares how both virtual and physical memory is affected, alongside a (very) simplified translation table between the two.

0x8000ViMratpupaeld1M2emA3o0lrxl4y8o0c5A0aV00dAt6ixxder88rd7t00eu00s8a0Asl..M9..SaVAA..ppidd00aprddxxcetrr88eduee00ass01lss930tTxor8aP0Pnh001hsyxx4yls??sai??itc??cia00aol..ln..A..Pd00h0dxxyxr??s?e??i?s??c?s99a01l2MeA3mlol4royc5aAt6dedd7re8s0sx9?S?p?aAce

Conclusion#

As stated in the repository README, there are still a few kinks to iron out when it comes to this project, namely error-handling, among others. As such, I’ll update this post with further developments whenever I get to them.

What I Learned (Am Learning?)#

  • Duck typing (somehow never messed around with it before)
  • Compiling into Shared Object (on Linux) and Dynamically Linked Library (on Windows) and everything that entails
  • Virtual memory management (anonymous files, tmpfs, memory mapping, etc.)