https://wheybags.com/blog/cow.html


Tom Mason

  * About
  * Blog
  * Projects
  * Contact

[website_co]  


Recursive COW pages in userspace

- 15th July 2023

[cowtools]

One fine evening, I was walking home after work when I was struck by
an idea. It was one of those ideas which, once it lodges itself in my
brain, simply refuses to leave until my curiosity has been satisfied.
This is that idea:

You could use SIGSEGV to implement COW memory pages in userspace.

What does COW mean?

COW stands for Copy On Write. Modern OSes will give you "pages" of
memory (chunks of a predefined size) when you ask them to allocate
space for your data. Unix-like OSes famously use copy on write pages
to implement fork(2). The process is cloned when you call fork, so
naturally you'd need to copy all the memory that program is using
into the clone right?

Well, that would be fantastically wasteful. You need to spend all
those cycles copying data, and double your memory footprint. It turns
out, pretty often when you call fork you don't need a lot of the data
in memory in the original process. Often you might never modify some
of the memory, only read it. This is where COW comes in. You can
create a cloned process which actually shares memory with the
original process. Doesn't that mean that you'd introduce all sorts of
race conditions when the two processes read and write the same memory
though? Well, through the magic of virtual memory, the OS can detect
when you actually write to the duplicated memory, and delay the copy
until just before that point. This way you only pay the price for
copying the memory you actually use.

What is virtual memory tho

Virtual memory is a feature of most modern processors that adds a
layer of indirection between the CPU and RAM. You have your physical
RAM, with a range of addresses, let's say for example you have 10
bytes of ram numbered 0-9. When your program asks for the memory at
address 7, it doesn't just look up the data at physical address 7,
but instead it first consults the page table. The page table is a
data structure maintained by your OS that maps your programs pointers
(which are in virtual address space) to the physical address space of
your real memory.

So you might have a page table mapping that says "map virtual
addresses 5-9 to physical addresses 0-4". This would mean your lookup
for the data at virtual address 7 would end up reading the physical
memory at address 2. The OS maintains these page tables, but the CPU
has special hardware to use them, so the hardware and software work
in tandem to keep the whole arrangement working. The greatest thing
about this system, is it allows your OS to isolate different programs
from each other, by keeping a separate page table for each process.
This means that one buggy program can't overwrite the memory owned by
another process, because it just has no way to refer to it, those
pages are not mapped in its page table. It is also the foundation of
pretty much all sandboxing and local security measures.

Side note, this is also (one possible reason) why calloc is preferred
over malloc + memset(0). calloc can give you a COW reference to a
read only zero page, repeated N times, and only actually bother
zeroing some real memory when you try to write on top of it.

Normally COW memory pages are something that the OS can do in special
situations (like when you call fork(2)), but are not available to a
user space programmer as a general tool. I think that is sad, because
there are some fun applications for it. When I worked on factorio, a
community member sent us a patch which allowed dedicated servers to
save the game and continue running the game simultaneously by forking
and doing the save in a second process. There were problems with it
(and it only worked on linux, because windows, where most of our
players were, lacked a fork system call), but the idea stuck in my
head ever since as something fundamentally cool.

[cowmag]

Not that kind of cow pages

A quick primer on how an OS would implement COW pages: First we set
up the page table for the two virtual addresses (the original and the
clone) to read only, and save some metadata somewhere inside the
kernel to keep track of our intention to make these pages COW clones.
All is well until userspace tries to write to one of them. As the
page is set to read-only, this triggers a page fault, and an OS
interrupt gets called (inside the kernel). We consult our magic
metadata, and we see that the page is set up for COW.

Next, we:

  * allocate a new physical page
  * copy the data from the old physical page into the new physical
    one
  * replace the mapping for the virtual page to point at our new
    physical page, mapped as read-write
  * update the other virtual mapping to the old physical page to be
    read-write, as it is now the only reference to that page

We can then branch back into userspace, and retry the memory access.
It will succeed, because the mapping is now read-write, and the
userspace program continues like nothing happened.

Now, here's the interesting part: if the page you faulted on was not
set up in the metadata as a COW page, then the OS will initiate
whatever invalid memory access system it uses to communicate the
error to userspace, eg sending SIGSEGV on *nix, or an SEH exception
on windows.

[cowlevel]

Unrelated cow pic

So, what's to stop us from catching that SIGSEGV or SEH exception,
and using it to implement the whole system described above, but in
userspace? Turns out, nothing. You can totally do that. Here's my
naive implementation. It's windows-only, but there's (probably)
nothing to stop you from doing the same on linux or MacOS. In fact, I
even went further, and I allow recursive COW copies. This means you
can allocate some pages, modify them, allocate a COW copy, modify
that, and then make a COW copy of the copy. This all works pretty
much as expected. The only limitation is that each "generation" can
have only one child. There's no inherent reason it has to be that way
though, it was just easier to implement.

So, how did I implement this? Well, first we need to set up a page
fault handler. On windows, this is done with
SetUnhandledExceptionFilter. This function takes a pointer to a
function, which it will call when an unhandled exception occurs. When
I allocate I save some metadata in a global variable, and in the
unhandled exception filter I inspect the error code (compare to
STATUS_ACCESS_VIOLATION) and address, and if it all matches up I
update the pages and metadata.

I allocate physical memory using a global anonymous file mapping
(like mmap on *nix). I allocate virtual memory using VirtualAlloc2,
which allows me to reserve virtual memory space without allocating
physical pages by passing MEM_RESERVE | MEM_RESERVE_PLACEHOLDER. I
can then map physical pages from the file mapping into the virtual
memory space using calls to MapViewOfFile3, which allows you to pass
it a virtual address to map at. So with these few functions together,
you get everything you need!

Now I know what you're thinking...

"This all sounds like a super sketchy thing to do. You're messing
with the invalid memory access handler, so there's all sorts of
opportunities for things to go spectacularly wrong. I suspect there's
some horrible performance gotchas in there. Also I looked at your
code and it's extremely naive and doesn't really handle errors
properly."

Yes. You are correct. You should not use this. But I had a lot of fun
making it. You're welcome.

***

Blog index
Subscribe via RSS, Email or twitter.