User Tools

Site Tools



Student: Bingzheng Wu
Mentor: Jorrit N. Herder
SVN branch name: src.20090525.r4372.wu


Extend MINIX 3's memory grant model in order to benefit from paging.


At this point, we have two subprojects in mind that we want to complete by the mid-term evaluation.

  • First, you should complete the homework assignment, that is, continue implementing the copy-on-write page-mapping optimization for safe copies.
  • Second, we would like to use memory grants to set up a memory mapping based on shared pages. This should be very easy once you have completed the first part and know how to set up memory mappings.

Test Plan and Evaluation

Once the above infrastructure is in place, you should test it by using the memory mappings in the INET server–ethernet driver and/or FS server–sata driver protocol, rather than using safe copies all the time. Hopefully, you'll be able to find performance (higher throughput or, more likely, better CPU utilization) improvements.

Schedule and Deliverables

We want to complete all this, including code cleanup and testing, etc. by the mid-term evaluation point. I have some ideas for the second half of GSOC (also dealing with VM extensions for MINIX), but I think it's good to focus on this part of the work first.

Weekly Status

Week 1

5.22 - 5.29

Receive a homework during the application phase. It's to implement copy-on-write page-mapping optimization for safe copies, using VM. I only implemented part of that homework because I encountered a problem:

For the mapping, I want to make 2 phys_regions in source and destiny process point to the same phys_block, to share it. However, the field which means the phys_block's offset to the @vaddr in vir_region is in phys_block, as @offset, but not in phys_region. As a result, if 2 phys_regions point to the same phys_block, the phys_block should has the same offset to the @vaddr. It's almost impossible in this task!

I think it's better to move the @refcount from phys_block to phys_region. But this is a huge change, which will cause changing much existing code. So I have to wait Ben to make the decision to go on.

I only read code about VM this week to get more familiar with it.

Week 2

5.30 - 6.7

Merge Ben's modification on the problem I mentioned in the report last week.

Adjust the code in homework phase, but have not finished.

Week 3

6.8 - 6.14

Port the code in homework. But it still need debug.

I wrote the test program to test the safecopy.

Week 4

6.15 - 6.21

The safe-copy works! This is the first task before mid-term evaluation.

  1. There was only 1 type of VM request, which is CHECK if the memory range has been mapped by physical memory. So first I added another type, MAP. [kernel/proc.h, lib/syslib/sys_vmctl.c:sys_vmctl_get_memreq()]
  2. In safecopy(), if the map conditions are all satisfied, call the MAP VM request. [kernel/system/do_safecopy.c]
  3. In page fault handler, check if the request is MAP: [servers/vm/map_mem.c]
    • Check whether the memory range in source process has been mapped by physical memory. This is the same demand with the CHECK VM request, so here we call its handler directly, map_handle_memory().
    • Do some prepare work for mapping. First, if there is a physical region which crosses the begin or end point in the request range, in source process, split it into 2 physical regions, by the begin or end point. For the destiny process, do the same thing. But what's more, since we will map the physical blocks, which belongs to source process, on to the destiny process later, so we need to delete the physical blocks in the demand range.
    • Now do the mapping. Map the physical blocks, which belongs to source process, on to the destiny process. Then update the page tables, both are READ-ONLY, for copy-on-write.

Week 5

6.22 - 6.28

Refine the test program, and do a simple test on QEMU. The result maybe not precise, but it shows something.

The result is so bad, that using MAP to copy is more that 10 times than regular data copy.

  • size: in byte, hex
  • time: get by read_tsc, decimal
  • The items marked by * uses mapping. Others uses regular data copy.
size 8 10 20 40 80 100 200 400 800 1000* 2000* 4000*
time 104496 103272 103280 105432 104144 103992 106040 126296 112936 1887376 1394456 1376136

According to the result, we can see that the key reason is not data size. The time changes little from size 8 to size 800.

I think the reason is that, in most situations, the virtual range, which will be copied data to, in source process, has been mapped by physical memory. So the regular copy just data copy. But if using mapping, it has to communicate with VM, which is a big overhead.

Another problem is that, if the virtual range in source process has been mapped by physical memory (as mentioned before), using mapping will first unmap these physical memory, and then map the destiny process's memory. But if later, one of the 2 processes(src or dest) writes the memory, it will have to map memory again and copy the data (copy on write). I think this will happen in all probability. At least more possible than fork(), which is always followed by exec(). So, finally, we do the data copy. What's more, we did some needless map and unmap.

So, my idea is that, using map to do the data copy is not good, especially in Minix, in which the VM is an independent server, and kernel has to communicate with it by messages.

But the shared memory using map based on grant table maybe a good idea.

Week 6

6.29 - 7.5

Implemente the SAFEMAP.

It's very similar with using map to do datacopy. The only difference is that:

  • MAP for datacopy, VM updates the PTEs in page tables of both source and destiny processes read-only(RO), for copy-on-write(COW).
  • SAFEMAP, VM updates the PTEs by MAP flag, which maybe either read-write(RW) or RO. For the RO map, when a page fault(#PF) caused by writing a RO page, the #PF handler has to check whether is COW or RO MAP.

I am going to implement the revoke-map and un-map in the next week.

Week 7

7.6 - 7.10


7.1 libsys

Wrap sys_safemap, sys_saferevmap and sys_safeunmap in library calls.

7.2 kernel

SAFEMAP, accepts arguments: grantor endpoint, grant_id and offset in grant table, requester's virtual address(segment+offset), and map type(RO or RW). After checking the permit and validity, send request to VM. The request is very same with the one used in copy-on-write(COW) mapping, a few weeks ago. Besides, for supporting the revocation, keep the mapping information in a global table.

SAFEREVMAP and SAFEUNMAP, both un-map the mapped memory. The difference is that, the former is invoked by grantor, by grant-id; while the later is invoked by requestor, by virtual address. When receiving these request, kernel searchs in mapping-information table, and sends un-map request to VM, if any.

7.3 VM

MAP, VM handles it almost the same with the COW mapping before.

UNMAP, VM explicitly copies the shared memory, such that the both the grantor and requester have a private, non-shared copy of the physical pages. There's another way: setting the shared pages as COW-shared, so the explicit copy will be done when the pages are written. But this is ineffective for some reasons.

7.4 #PF

By now, VM assumes that all pages in user space are writable. So if there's a page read-only, it must be COW.

But now, the situation changes. Because the program may call safemap() readonly, so there will be some pages readonly, but not for COW. So if a #PF caused by a program writing a read-only page, VM has to check whether it's COW or read-only MAP, before handle the page fault.

Unfortunately, since the mapping information(that global table, mentioned above) is saved in kernel (because it has to contain the 'grant_id'), so we can't use this table to distinguish the COW or read-only MAP. A better way is that, add a member 'share_flag' in struct phys_block, which show whether this phys_block is shared as COW or read-only MAP.

7.5 MAP + COW

However, if we add 'share_flag', what should we do, if a page(or phys_block) is shared by 2 processes as MAP, and also shared by other 2 processes as COW? In fact, even if we don't add 'share_flag', we still have to face this problem.

Let PA, PB and PC denote for 3 processes. The problem is that: if first, PA and PB share a page as MAP, read-write; and then PB forks PC, so PC and PB share the same page as COW. The page in PB's page table is read-only, for COW. But in PA's page table, it's still read-write. So the PA can write this page, while PC doesn't expect that and can't detect it.

There is also problem that if MAP a page which has been shared as COW already.

My solution is: avoid this case.

  • If MAP a page which has been shared as COW already (detected by share_flag, mentioned above), first copy this page, and then do the MAP.
  • When copy a process [servers/vm/regions.c : map_proc_copy()], which will cause COW-share, if a page has been shared as MAP already (by share_flag), then we do real copy, but not COW-share. Besides, when call map_writept() to update page table, if a phys_block is shared as SMAP, don't update it's PTEs in page table.
7.6 Test

I tested all cases:

  • SAFEMAP a page which has been shared as COW
  • COW a page which has been shared as SAFEMAP.

Week 8

7.13 - 7.19

Did nothing.

Week 9

7.20 - 7.26

From this week, I begin to the part III of GSoC, to extend data store(DS) server.

DS just store some memory range. What I am going to add is that, store some memory range by mapping. As a result,

  • we can get a real-time view of the change of memory;
  • we can make snapshot anytime.

I re-wrote DS mostly, added some new APIs for mapping-store, and changed some old ones. Fortunately, the old APIs that I changed was not used now in Minix3, so it doesn't need to change other code.

I have not tested all of the new DS, which is the task in next week.

Week 10

7.27 - 7.31

DS now supports 5 types: U32(unsigned int), STRING (string that shorter that 16-chars), MEM(memory range), MAP(mapped memory range), and LABEL(as name server).

Add new APIs for these 5 types.

TODO: test!

Week 11-12

8.3 - 8.16

Holiday :)

Week 13

8.17 - 8.18

Test the DataStore Server.

Document the GSoC.

soc/2009/memorygrants.txt · Last modified: 2014/11/11 17:15 (external edit)