COMS W4118: Operating Systems I

Homework 4 Hints and Clarifications

Homework 4 is due Monday 4/15 Friday 4/19 at 12:01 AM ET.

1. For the ssmpipe test program in Part II, you may make the simplifying assumption that the name for each reader is unique, and an integer from 0...MAX_READERS-1 (0..7). If you make this assumption, make sure your test program exits with an error for any name that is not in that range. If you still cannot come up with a solution, you may use semaphores to synchronize #include , but you will loose 5 points.

2. Some people have asked me whether it is acceptable to allocate all the physical memory for a ssmem segment at once as a contiguous block. While it simplifies your task somewhat, it is not an ideal solution because it does not allocate memory on demand. Furthermore, this solution will have no chance of working with the swap subsystem. So, you may use this approach, but expect to loose a few points (no more than 10).

3. When implementing your custom page fault handler, it is not sufficient to return a new struct page * and leave the installation of PTEs to the calling code. Read and understand the code that calls the custom page fault handler (__do_fault in memory.c). You will realize that it handles anonymous unshared pages or shared pages that are backed by a file correctly, but not anonymous shared pages. This is because the kernel has no such thing, and we're really creating a new class of page.

   So, you will either have to modify the function __do_fault to handle anonymous shared pages, or preferably, install the PTE mapping into the page table yourself from your custom page fault handler. If you choose to go the later route (which I would suggest), return VM_FAULT_NOPAGE in the custom page fault handler so that __do_fault won't do anything further for your newly installed page. Use the __do_fault function as a guide for the kinds of things you have to do to install a new PTE.

   In particular when installing a new PTE, you will have to think about locking. As I mentioned in class, a lot of kernel code has gotten away from using the page_table_lock spinlock directly in favor of something called split locks (essentially per-page locks that are invoked in a finely granular way). Use the get_locked_pte call to get a pointer to a properly locked pte. Alternatively, you may avoid using page table locks altogether if you can ensure that any code that manipulates the PTE entries corresponding to your custom VMA is serialized some other way (through some another lock/semaphore, for example).

4. Make sure you manipulate reference counts properly. In particular struct page * has two ref counts: a) _count tracks the total number of references to the page, and b) _mapcount which tracks the number of address spaces that have mapped that page into their page tables. So, if you acquire a pointer to a page to insert into a PTE, both reference counts should be incremented (either by you directly, or by a helper function). If you wish, your ssmem subsystem may also hold an additional _count reference to each page (using the get_page and put_page functions). Finally, the LRU swapping subsystem also maintains a reference count on each page using the _count variable. So, typically, the value of _count should be atleast 1 more than the value of _mapcount.

5. When manipulating the entries in a struct page, make sure you acquire a lock to the page using lock_page (and page_unlock_page). Note this lock is different from mlock and munlock which you have to use to make your pages unevictable by the swapping subsystem.

6. Use the pgoff value provided to your custom fault handler (through vm_fault) with caution if you use it at all. Its value may not be what you expect.

Testing your Swapping Implementation

1. First, you need to enable swap on the emulator (Android turns swap off by default). The tools to do this aren't included with the default Android distro. So, get a precompiled version of busybox from here. Download the busybox-i686 binary because our emulator runs x86. This will be a self contained binary.

2. Before starting the emulator, edit the avd settings (android avd) and enable the "SDCard" option to create a sdcard of size greater than the RAM of your device (e.g., 768MB if your RAM Is 512MB). Making the swap larger than RAM is important for what's to come.

3. Start the emulator and push the busybox-i686 binary to the emulator: adb push busybox-i686 /data/busybox and adb shell chmod 777 /data/busybox

4. Open an adb shell and create a swap partition on the sdcard using the following:

   • adb shell
   • cd /data
   • ./busybox fdisk /dev/block/mmcblk0 (this is the new sdcard you created)
   • In fdisk, use m to see help. You need to do the following:
     • o (create new partition table)
     • n (add a new partition the full size of the disk)
     • t (change the type of the partition to Linux swap: type 82)
     • w (write partition table to disk)
   • At this point, you should see a /dev/block/mmcblk0p1 partition. Create the swap using: ./busybox mkswap /dev/block/mmcblk0p1

5. Turn swapping on (you need to do this every time you boot the phone) ./busybox swapon /dev/block/mmcblk0p1. You can verify that swapping is on using: cat /proc/meminfo. You can turn swap off by using ./busybox swapoff /dev/block/mmcblk0p1.

6. Now, you're ready to test swapping of your ssmem segment. Write a test program that does the following in a loop: allocates a new 2MB ssmem segment, and writes a counter to each 4K page of this segment. Keep doing this until you run out of memory (ssmem_attach returns -ENOMEM). Print how much memory you were able to allocate. Then loop through all the memory you allocated, and verify the contents you wrote into them.

   Do the above with and without swap turned on. If your swapping implementation is working, you should be able to allocate more memory (roughly the size of the swap partition more) with swapping turned on. Making the size of swap larger than RAM ensures that the OS cant fill the swap space by simply swapping out other memory besides your ssmem segments.