How does the OS track Reference Counters in Copy-on-Write forks?

Question

I'm trying to modify xv6-riscv to perform a copy-on-write mapping when executing fork(), but I'm struggling to determine a concise way to manage the copy-on-write pages.

Most sources I can find online suggest to keep reference counter of how many processes currently are able to read from a given copy-on-write page, storing the counter in the PTE. Only pages with a reference count of 1 may be written to, otherwise you must copy the page and decrement the reference count.

However, it's not clear to me how you would actually implement this. The PTE is of a fixed size, and the vast majority of bits, especially in RISCV, are reserved for other purposes, so storing the number of references in the actual PTE feels impractical, especially if the process calls fork() many times.

Furthermore, how would you synchronize this information across page tables? Each process gets their own PTE for a given physical page. Updating the reference count on the current process's PTE for a physical page will not give any information to the other processes.

My idea was to create a sort of page table tree which would dynamically grow as processes fork() and shrink as processes call exec() or kill(), but this doesn't seem to be mentioned anywhere, and it's pretty convoluted, incurring O( number of procs sharing COW page ) access time on writes to copy-on-write pages, so I wanted to explore simpler options.

Answer 1

In a typical modern operating system, there are three data structures which represent the state of memory. Also note I'm going to use Unix-ish terms for these; Windows has much the same concepts but may use different terms.

1. The page tables are the CPU's view of virtual memory. There is usually no "room" in a page table entry (PTE from now on) to store anything when the page is valid.
2. The virtual memory map is the OS's view of virtual memory. You can think of this as a list of segments which represent a range of virtual memory, what it corresponds to (e.g. anonymous memory, some section of a mapped file), and its semantics (e.g. zero fill, copy on write).
3. The core map is the OS's view of physical memory. The Unix v6 core map was very simple; it was just a bitmap, with one bit denoting if a page frame was used or free. Today, an array of structures, one per page frame, allocated at boot time is a common implementation.

If a page of virtual memory is not resident in core, then it doesn't really "need" a representation that is distinct from the segment that it belongs to. The virtual memory map can record sharing information.

If page is resident in core, the information about sharing can be stored in the core map, or in a structure available from the core map.

The core map entry structure should be small, since there is one per page frame. For kernels implemented in C, judicious use of union is very common. A typical core map entry might information such as:

• A word representing the type of memory (e.g. free, page cache, kernel allocated, memory-mapped I/O area, ROM) and associated flags (e.g. whether or not it is shared, or perhaps some concurrency protection).
• The previous/next pointers of a doubly-linked list. This might, for example, represent the free list if the page frame is free, or an LRU cache (for "page out" purposes) if it is part of the page cache.
• An integer (perhaps an atomic integer) representing the number of address spaces that the page is used by.
• If the page frame is singly-mapped, the address space and offset that this page frame belongs to. Otherwise, if the page frame is shared, this space could be used to point to an auxiliary structure which represents a list of mappings.

xv6 doesn't have support for any of this, since its physical and virtual memory management is very simple for teaching purposes. As well as not supporting shared segments, it also doesn't support memory-mapped files or swap. It doesn't even seem to have a page fault handler, as far as I can tell. Rather, xv6 manages physical memory as a free list.

I can't tell you how you should implement this, but I would start with implementing a core map and reworking the kernel allocation system to use it, then iterate on that.