fork problems about TLB and refcount

[Donglei]

Hi everyone. I have started my os for a while, you have helped me a lot through I just search and read.
Today, I started to think about fork. there are two problems I can't get out.

1. When fork a task, the whole vm of parent(caller of fork) needs to marked as readonly(must?). This will cause TLB invalidation. The more writable pages the more TLB invalidation. Except .rodata and .text section, the whole vm needs INVLPG. Since I have seen TLB flush is evil many times, I wander is there a better way to avoid TLB invalidation?


2. With fork, there are some physical frames shared between many tasks. I added a refcount for each physical frame to simplify this situation. But it seems not efficient. Suppose task A use 32MB physical memory. There will be 8192 frames to increment refcount. I realy can not image unix only use 60 asm code to implement fork.

I hope I have describe my problems clearly with my poor English.
Thanks.

[gerryg400]

1. When fork a task, the whole vm of parent(caller of fork) needs to marked as readonly(must?). This will cause TLB invalidation. The more writable pages the more TLB invalidation. Except .rodata and .text section, the whole vm needs INVLPG. Since I have seen TLB flush is evil many times, I wander is there a better way to avoid TLB invalidation?

Yes, the whole address space needs to be marked RO. It may be possible to save some time by marking higher level pages RO but this would add to complexity. I just mark all the pages RO and reload the cr3. Remember to consider SMP here. I haven't spent much time in my OS on optimisation yet.

2. With fork, there are some physical frames shared between many tasks. I added a refcount for each physical frame to simplify this situation. But it seems not efficient. Suppose task A use 32MB physical memory. There will be 8192 frames to increment refcount. I realy can not image unix only use 60 asm code to implement fork.

I suggest you group pages together and have a reference count for the group. e.g. a reference count for .text, another for .data.

[Donglei]

Yes, the whole address space needs to be marked RO. It may be possible to save some time by marking higher level pages RO but this would add to complexity. I just mark all the pages RO and reload the cr3. Remember to consider SMP here. I haven't spent much time in my OS on optimisation yet.

Thanks for you reply. Maybe its too earlier to think efficiency too much. I should make it work first.

I suggest you group pages together and have a reference count for the group. e.g. a reference count for .text, another for .data.

How to group pages in .text as maybe some pages have 3 ref, some pages have 2 ref. The worst case is each page in .text have a unique refcount.

[gerryg400]

I suggest you group pages together and have a reference count for the group. e.g. a reference count for .text, another for .data.

How to group pages in .text as maybe some pages have 3 ref, some pages have 2 ref. The worst case is each page in .text have a unique refcount.

How would it happen that some pages have more refs than others? It could happen in the data segment if the heap grows before the fork(), but even then some groups of pages will have the same refcount. In the beginning all pages will have refcount of one. After each fork() the refcnt of every page increases by 1. So all refcnts will be 2. The way they become different is if the user allocates a new block. The new block will have refcnt 1 so all those pages can be grouped together. If the user does something weird like allocating 1 page, then fork(), then allocate another page, then fork() etc. you may have a problem.

[Donglei]

Hi

How would it happen that some pages have more refs than others?

Suppose task A allocate some memory, and fork a new task(B). When A or B want to modify some pages, these pages needs copy-on-write (decrement refcount). then B fork a new task(C). Still some pages need modified and then decrement refcount. So, it doesn't have to allocate new mem.

edit: yes, this problem is related to data segment (not .text).

[Velko]

Yes, the whole address space needs to be marked RO. It may be possible to save some time by marking higher level pages RO but this would add to complexity. I just mark all the pages RO and reload the cr3.

Marking higher level paging structs RO reduces complexity of fork() itself, but adds more of it elsewhere. Fork() becomes straightforward: (assuming i368 paging) set all userspace PDEs to RO, copy everything to new PD, reload CR3.

You may want to run child process first, to avoid pointless TLB flushes (it be will scheduled to run soon anyway).

But now you also need to refcount Page Tables, clone them (and make contents RO first) in CoW handler, pay attention to refcount and CoW status when freeing pages, etc.

It may take some to wrap your mind around it, but it is great improvement on efficiency.

[gerryg400]

Hi

How would it happen that some pages have more refs than others?

Suppose task A allocate some memory, and fork a new task(B). When A or B want to modify some pages, these pages needs copy-on-write (decrement refcount). then B fork a new task(C). Still some pages need modified and then decrement refcount. So, it doesn't have to allocate new mem.

edit: yes, this problem is related to data segment (not .text).

I use a method similar to that in one of the BSD OSs. It uses chains of shadow objects that contains lists of pages that have diverged since the last fork(). There are no reference counts in the pages themselves. Have you seen this method?

Section 5.1 in this document explains a little. https://www.usenix.org/legacy/event/use ... cranor.pdf

http://www.ico.aha.ru/h/The_Design_and_ ... v1sec5.htm is also worth reading.