COMS W4118: Operating Systems I

Homework 4

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

All written problems in this assignment are to be done alone, while the programming assignment is a group assignment. Submit the written and programming assignments separately using the instructions on the homeworks page. Periodically check back on the course page for any errata or updates to submission instructions.

Written Assignment (48 pts)

Exercise numbers X.Y refer to the exercise problem Y in Chapter X in the course textbook, Operating Systems Concepts 9e. Each problem is worth 8 points. Make your answers concise. You'll lose points for verbosity. Your written assignment directory should contain a single ASCII file called hw2.txt with your solutions and a completed teammate evaluation form for the programming assignment.

Group Programming Assignment: Simple Shared Memory (60 pts + 25 points extra credit)

In this programming assignment, we'll be working with the Android kernel again using the same emulator environment you constructed for Homework 2 using these Android installation instructions. In your checked out git repository, make sure you checkout the hw4 branch before starting work on this assignment using git checkout hw4.

As the deliverable, you will be required to submit a kernel patch and diff against the hw4_clean tag in your git repo. The patch shows us all commits you have made to the kernel during development, while the diff reflects only your latest code. To produce the patch and diff files, make sure you've committed all your changes, and then go to the root of the kernel tree and type git format-patch hw4_clean.. --stdout > groupN_hw4.patch where N is your group number. This command should create a single groupN_hw4.patch file to submit. Similarly, use the command git diff hw4_clean.. > groupN_hw4.diff to create a single diff file to submit. In addition to these files, you should also include all user mode test programs: .c, .h, Makefile files, the executable files for your test programs, and a README file documenting your files and code that explains any way in which your solution differs from what was assigned, and any assumptions you made. In addition, you are required to also fill out and include this cover sheet to indicate whether your code has any problems or not, and what attempts you have made to fix them.

The usual coding instructions apply. All code must be written in C and a Makefile must be provided with a default target that compiles all user-mode programs. When using gcc, the -Wall switch must be used to display warnings. In addition, you must check your kernel diff against the Linux coding guidelines using the scripts/checkpatch.pl groupN_hw4.diff command in the kernel tree. You can find a tutorial on how to use checkpatch and general kernel hacking tips here. Before submitting, make sure you remove any files produced during compilation (.o files, executable).

Description

We've studied many different IPC mechanisms during the course, and in this assignment, we're going to implement one of the most efficient ones: a simple shared memory system called ssmem. You will be implementing syscalls for creating a new shared memory region, attaching an existing ssmem region into a process's address space, and detaching a mapped region from the address space. You will test your implementation using two test programs: a producer-consumer pipeline and a simple RPC implementation.

We will support up to a fixed number (1024) of ssmem regions systemwide, and each region is to be identified by an id between 0 and 1023 that is unique across the system. Once a new ssmem region has been created at a particular id, other processes (or threads) should be able to attach to it using this id. A process may attach the same region multiple times at different virtual addresses, and once created, an ssmem region should survive as long as some process has mapped it in its address space - even if the process that created the ssmem region terminates. When the last process mapping the ssmem segment detaches it or terminates, the ssmem region should be destroyed.

Deliverables

1. Part I (50 points): Design a ssmem (simple shared memory) facility that is implemented in the mm/ssmem.c file, and which exports the following two system calls.

     #define SSMEM_MAX    1024
     
     #define SSMEM_FLAG_CREATE 0x1
     #define SSMEM_FLAG_WRITE  0x2
     #define SSMEM_FLAG_EXEC   0x4
   
     /* Syscall 333. Map an existing ssmem segment identified by
      * id (0..SSMEM_MAX-1) into the caller's address space. The flags
      * argument is a bitmask containing one or more of
      * SSMEM_FLAG_CREATE, SSMEM_FLAG_WRITE, and SSMEM_FLAG_EXEC.    
      * If the ssmem segment does not exist and SSMEM_FLAG_CREATE
      * is specified, a new ssmem segment must be created at that id.
      * The length field is only valid when creating a new ssmem segment,
      * and specifies its length in bytes. The flags argument specifies
      * the access permissions (writable/executable) with which the ssmem
      * segment is to be mapped into the caller's address space. These
      * permissions may be different for each process that maps the
      * segment.
      *
      * On success, return a pointer to the ssmem segment. On failure,
      * return (void*)-ENOMEM if the memory cannot be allocated, -EINVAL
      * if the supplied id or length is invalid, and -EADDRNOTAVAIL if
      * an ssmem segment at a particular id doesn't exist and
      * SSMEM_CREATE is not specified. 
      * /
      void *ssmem_attach(int id, int flags, size_t length);
   
     /* Syscall 334. Unmap a shared memory segment mapped at the
      * address specified in the addr argument. If the current process
      * is the last one mapping the ssmem segment, the segment should
      * be destroyed and the id released.
      *
      * Return 0 on success, and -EFAULT if the addr is invalid or
      * does not point to a ssmem segment.
      */
     int ssmem_detach(void *addr);
     

   Assumptions: you may make the following assumptions.

   1. Irrespective of the length parameter, ssmem will always be allocated in multiples of the page size.
   2. You do not have to support swapping of ssmem pages to disk. You may (must) lock ssmem physical pages in memory.

   Solution outline: This assignment requires a fairly comprehensive understanding of almost all Android memory subsystems: virtual memory areas (mm/mmap.c), the paging subsystem (mm/memory.c), reverse mapping (rmap.c) subsystem, and their interactions with the swapping subsystem (mm/vmscan.c). Although we have covered these subsystems in class, the following points outline a possible approach to implementing this assignment:

   1. Learn the roles of the page table, vm area structures (vmas), the process memory map (mmap), and the anon_vma reverse map. A process's memory data structures can be accessed through the task_struct->mm member structure of type mm_struct. This structure is defined in include/linux/mm_types.h.

   2. Maintain an array that stores per-ssmem segment data including the length, the number of mappers, a list of mappers (reverse map), a list of physical pages allocated to the ssmem segment. This information should be task independent and created/deleted when the ssmem segment is created/deleted.

   3. When attaching a ssmem segment into a process address space, create a new vma (virtual memory area struct) object that represents that particular ssmem segment mapping. Thus, each ssmem_attach invocation should create a new vma even if the same process has already mapped another instance of the ssmem segment in its address space. See struct vm_area_struct in include/linux/mm.h. The file mm/mmap.c contains several helper functions and code examples of how to work with vmas. See the do_mmap function in particular.

   4. Your special vma will need flags to be set appropriately to reflect the vma's shared status and the write/execute flags the user passes in the ssmem_attach call. The vma will also need to register it's own page fault handler through the vm_operations_struct in include/linux/mm.h. Because the page table entries representing the ssmem segment will initially be empty, they will result in page faults when accessed by a process. Your page fault handler will be responsible for mapping the right (shared) physical page into the process's PTE (page table entry). If the fault is the first time any process has tried to access the page, it will have to be allocated. If you need to store the identity of your ssmem data along with the vma so that the page fault handler can access it, you may use the vm_area_struct->vm_private_data field in the vma.

   5. You will need some technique to keep track of which physical page corresponds to each virtual page in the ssmem segment. There are several ways to do this. You may use a single process as a "master process", and use its virtual to physical mapping as a reference whenever another process needs to map a virtual address. However, you will need to create a new master if the current master dies. Alternatively, you may map a newly allocated physical page into the page tables associated with every mapping (vma) that maps the ssmem segment. However, the easiest option is to keep a mapping in your per-ssmem data structure itself. This option does not work if we need ssmem segments to be swappable to disk because the swapper could use a different physical page after it swaps out a page and swaps it back in. This is why we do not require you to support swapping.

   6. Whenever a process detaches a ssmem segment, remove the corresponding vma mapping from the process. vma mappings will also be removed by the kernel when a process is terminated. If this was the last vma mapping for this ssmem segment, then clear the entry corresponding to the ssmem from the ssmem table. To do this, you can register a callback that will be called by the kernel when your ssmem vmas are destroyed. Do so through a vm_operations_struct->close entry in your vma. Note that when detaching a ssmem map, you must unlock all the pinned pages (see unlock_memory_pages_all), and remove the page table and tlb entries associated with that map (see mm/mmap.c/unmap_region). Use the function mm/mmap.c/do_munmap as an example of what to do when unmapping.

   7. Even if we do not support swapping, we should maintain a reverse mapping that lets the kernel identify all the VMAs that have potentially mapped a particular physical page and track the page's reference count. You can do this through an anon_vma data structure and functions in mm/rmap.c. In particular, see the page_add_anon_rmap, anon_vma_link, and anon_vma_prepare functions.

   8. Use proper locking techniques to synchronize access to any shared data structures (mmap, page tables, ssmem data structures). The mmap is protected by a rw-semaphore task_struct->mm->mmap_sem, while its page tables are protected by a spinlock task_struct->mm->page_table_lock. You will need your own locks for ssmem data structures. Remember - do not use spinlocks if your code may sleep while holding it (e.g., to allocate user memory).

2. Part II (10 points): Write a producer-consumer test program to test your ssmem implementation.

   • Write a program called ssmpipe <name> <ssmem_id> <type> that accepts three arguments. name is the name of the producer/consumer instance. ssmem_id is a number between 0..1023 that identifies the ssmem segment to use. type is either the string writer or reader that indicates the type of this instance.

     Each instance should create (or attach to) a ssmem segment of size 8k (2 pages) divided into logical "slots" of 1024 bytes each. Writers should accept lines of input from the standard input, and write them to a slot in the ssmem segment after prefixing their name to the input line, e.g., "writername says: line". Readers should read slots from the ssmem segment and write it to their stdout after prefixing their name, e.g., "readername: writername says: line". You may truncate the lines if needed so that they fit in a single 1024 byte slot.

     You need to ensure that your readers and writers are synchronized. Readers should read slots only after the writer has finished writing to them. When the writer exhausts all its slots, it should wrap-around and reuse the slots, but only if all the readers have finished reading that slot (else it sleeps and periodically checks after every 1 sec if the readers are done). You may not use any additional synchronization primitives provided by the kernel. Hint: use atomic updates and make local copies - x86 architecture guarantees that simple assignments (x=y) are always atomic. To make this requirement easier, you may assume that there is at-most one writer, and up to 8 readers, but make sure the writer doesn't need to assume that all 8 readers are present. You may use slot 0 in the ssmem segment to store any synchronization related variables.

     Sample output for your programs is shown below:

         $ ssmpipe 1 1 reader
         $ ssmpipe 2 1 reader
         $ ssmpipe 1 1 writer
         hello, world!
         reader1: writer1 says hello, world!
         reader2: writer1 says hello, world!
         

3. Part III: Extra Credit (10 points): Does your implementation support swapping of ssmem memory pages to disk? Describe why or why not. In particular focus on a) how does the swapper identify all the ssmem mappings associated with a physical page it wants to page to disk? and b) what happens if a new process wants to attach an existing ssmem segment but some of its physical pages are paged to disk? If your implementation does not support swapping, what changes would you need to make to support it? Be as specific as possible.

   Note: if your implementation already supports swapping, then you get an automatic 25 point credit (instead of the 10 point extra credit above).

Error Handling

Check the return values of all functions utilizing system resources. Do not blithely assume all requests for memory will succeed and all writes to a file will occur correctly. Your code should handle errors properly. Many failed function calls should not be fatal to a program. Typically, a system call will return -1 in the case of an error (malloc will return NULL). If a function call sets the errno variable (see the function's man page to find out if it does), you should use the result of strerror(errno) as part of your error message. As far as system calls are concerned, you will want to use one of the mechanisms described in Reporting Errors or Error Reporting.