OSDev.org

I want to create the fork() syscall using copy-on-write, but I'm having trouble coming up with a reasonable solution. I understand the concept of copy-on-write, but I do not know how to appropriately clean up resources when they've finished. I can imagine two situations that make COW a problem that doesn't have a straight-forward solution:

- Process A forks into B. B modifies a variable, triggering a COW, but Process A still has that page marked read-only, so if A modifies it, another copy will be made. Now there are three physical pages: the original before forking, A's written copy, and B's written copy. The original page will be orphaned and cause 4 KB of memory to be leaked. How can this be avoided?
- Process A forks into B. Process A terminates. I can't free its memory because B is still using some of it. Reference counting would partially solve this, but then if Process B forks after modifying some pages, it becomes a mess.

How do you implement fork() without causing memory leaks? Am I missing something? This seems way too complicated...

Reference count and index of COW-able pages to the rescue.

- Process A forks into B. B modifies a variable, triggering a COW, but Process A still has that page marked read-only, so if A modifies it, another copy will be made. Now there are three physical pages: the original before forking, A's written copy, and B's written copy. The original page will be orphaned and cause 4 KB of memory to be leaked. How can this be avoided?

When forking you either add page to index with refcount of 2 or increase refcount if page is already there. When COW is triggered you decrease refcount. If it approaches zero, you simply re-map page as RW and remove it from index. Create a copy otherwise.

- Process A forks into B. Process A terminates. I can't free its memory because B is still using some of it. Reference counting would partially solve this, but then if Process B forks after modifying some pages, it becomes a mess.

If process B has modified a page, it's already private to B. And refcount for original page from A has decreased to 1. If B forks into B and C, pages will be shared between them, but that has nothing to do with original page from A.

Thanks for your reply. So it seems the only way to do COW is to keep a reference count of each physical page.

Velko wrote:If B forks into B and C, pages will be shared between them, but that has nothing to do with original page from A.

Now, this is the part that I am also stuck on. How does this not have anything to do with the original page from A? If process A forks into process
A and B, then both modify the tenth page in their address space, then all except the tenth page is shared. If process B then forks into process
B and C, and both again modify the tenth page, then none of the processes share the tenth page, but all three processes share pages 1-9, unless
I'm just arbitrarily duplicating pages simply because the process has forked more than once.

My issue with this is that I can't seem to wrap my brain around an efficient method for keeping track of this without traversing a rather large
list of core structures' parents and checking each one for where this damned page came from when, say, process C has forked again and process D
modifies a page that none of the others since A have modified.

EDIT: [PS] Sorry for the bump. =p

Now, this is the part that I am also stuck on. How does this not have anything to do with the original page from A? If process A forks into process
A and B, then both modify the tenth page in their address space, then all except the tenth page is shared. If process B then forks into process
B and C, and both again modify the tenth page, then none of the processes share the tenth page, but all three processes share pages 1-9, unless
I'm just arbitrarily duplicating pages simply because the process has forked more than once.

The reference count for pages 1-9 would be increased by one. For page 10 of process B, you'd do the same as you did for page 10 of process A when it first forked.

Basically, you'd end up with a reference count for 3 for pages 1-9, which are all CoW, page 10 of process A would not be CoW and wouldn't need to be counted, and page 10 of process B/C would be CoW with a reference count for 2.

Also, when you decrement the reference count down, check to see how many counts it has, and if it's now only 'shared' by 1 process (meaning not shared), then you can set that page to no longer be CoW in that 1 process, and then you should be able to get rid of the reference count for that page until it's CoW'ed again.

inx wrote: My issue with this is that I can't seem to wrap my brain around an efficient method for keeping track of this without traversing a rather large
list of core structures' parents and checking each one for where this damned page came from when, say, process C has forked again and process D
modifies a page that none of the others since A have modified.

That was my original problem, too. I was thinking of COW as if it could be handled completely within page tables and process structures. What I've learned from these posts and a little more searching is that each physical page must have a reference count. I was hoping for some kind of solution within the paging manager and process structure, but that wouldn't be possible.

@Kitsune: Thanks for the breakdown. I understood this, but having you state it the way you did made me reevaluate from another angle, and it's clear now.
@manonthemoon: Thank you, I hadn't thought of putting it further down the stack. Thankfully, with the way my abstractions are set up, I can implement this in my physical MM without any
API changes.
W00t, off to end my ~4 month procrastination streak.

Kitsune wrote:Also, when you decrement the reference count down, check to see how many counts it has, and if it's now only 'shared' by 1 process (meaning not shared), then you can set that page to no longer be CoW in that 1 process, and then you should be able to get rid of the reference count for that page until it's CoW'ed again.

True. Still, you have no (cheap) way of knowing to which process it belongs. IMHO it's easier to leave it as is and handle removal when Page Fault fires again.

manonthemoon wrote:What I've learned from these posts and a little more searching is that each physical page must have a reference count.

Not necessarily. I see no point in refcounting in-kernel pages or process private pages. You might want to extend that infrastructure in another direction through. If in addition to reference count you keep a pointer to function and some additional meta-data, other paging features (say, lazy loading) will nicely fit in there as well.