ailrun/osfall2016

snu os fall 2016

Project 2: Rotation Lock

OS Fall 2016

DUE: 2016.10.31 Monday at 8:59pm KST

This project is to be done in your assigned teams. If you don't change your teams, you and your team will continue your work on the same repository you worked on for Project 1. Those repositories are accessible to all members of each team, and all team members of a team are expected to commit (local) and push (update the server) changes / contributions to the repository equally.

You should make a new base branch named proj2 for Project 2 and work in sub branches. All team members should make at least five commits to the team's Git repository. The point is to make incremental changes and use an iterative development cycle. Your final codes and README file have to be committed into the base branch of the project for submission. Follow the Linux kernel coding style and check your commits with the scripts/checkpatch.pl script included in the Linux kernel. Errors from the script in your submission will cause a deduction of points.

The kernel programming for this assignment will be done using your Tizen-based TM1 devices.

1. A user-space daemon to pass device rotation into the kernel

   On the Tizen platform, device orientation can be accessed via an on-board orientation sensor device. However, TM1 does not have one. A Tizen device detects its orientation in the three dimensions, but we will use rotation (one-dimensional orientation) here to simplify the project. Furthermore, we provide a fake daemon that updates rotations, called rotd, for you to save time. :-)

   The daemon we provide updates the rotation value in the sequence of 0, 30, 60, ... 330, 0, ... in a fixed frequency (e.g., 2 seconds). The daemon passes the fake values to kernel using the following system call and type.

   /*
    * sets current device rotation in the kernel.
    * syscall number 384 (you may want to check this number!)
    */
   int set_rotation(struct dev_rotation *rot);
   
   struct dev_rotation {
   	int degree;		/* 0 <= degree < 360 */
   }; 
   

   You should write set_rotation system call by yourself, which updates the rotation information in the kernel. All rotation related functions should be placed in kernel/rotation.c, and in include/linux/rotation.h.

2. (45 pts.) Rotation-based reader/writer locks

   Design and implement a new kernel synchronization primitive that will provide reader-write locks based on device rotation. Reader-writer locks work by allowing several readers to grab the lock at the same time, but only a single writer can grab the lock at any time. You should make sure not to starve writers: If readers hold a lock and a writer wants to take the lock, no more readers can take the lock.

   A lock is defined by a range of the rotation of the device. For example, if a writer grabs the lock for the degree ranging from 30 to 60, then readers cannot grab any locks in that area, but readers can grab a lock when the degree is between 180 and 210.

   If a process wants to grab a lock (either read or write lock) for an area, which does not cover the current physical device rotation, the process should block until the device is rotated into that area.

   A user space process can hold the lock as long as it wishes, and either eventually gives it up voluntarily or is forced to give it up when the process dies. While locks are only obtained when the device is in the corresponding rotation, locks can be released irrespective of the rotation.

   When the device rotation is updated in the kernel, the processes that are waiting to grab a lock on an area entered by the new rotation should be allowed to grab the lock (making sure readers and writers don't grab the lock at the same time. If no processes are waiting for the particular rotation when it is updated in the kernel, then the operation has no effect. The API for this synchronization mechanism is the following set of new system calls which you will implement:

   /* Take a read/or write lock using the given rotation range
    * returning 0 on success, -1 on failure.
    * system call numbers 385 and 386
    */
    int rotlock_read(struct rotation_range *rot);
    int rotlock_write(struct rotation_range *rot);
   
   /* Release a read/or write lock using the given rotation range
    * returning 0 on success, -1 on failure.
    * system call numbers 387 and 388 */
   int rotunlock_read(struct rotation_range *rot);
   int rotunlock_write(struct rotation_range *rot);
   
   /*
    * Defines rotation range. The ranges give the "width" of
    * the range. If the degree_range value is 0, it is not considered
    * as defining the range (ignored).
    */
   struct rotation_range {
   	struct dev_rotation rot;  /* device rotation */
   	unsigned int degree_range;		/* lock range = rot.degree ± degree_range */
   	/* rot.degree - degree_range <= LOCK RANGE <= rot.degree + degree_range */
   };
   

   You should modify the set_rotation system call to handle processes blocking on a lock that covers the new rotation. You should choose to allow either all blocked readers to take the lock or a single blocked writer to take the lock. When a lock is taken by one or multiple processes, the processes are unblocked and return to user space. Your strategy to select either readers or a writer should consider consider fairness as a criteria.

   If there are no processes waiting on the event, then nothing happens. Modify the return value of the system call such that it returns -1 on error, and the total number of processes awoken on success (0 or more)

   You should begin by thinking carefully about the data structures that you will need to solve this problem. Your system will need to support having multiple processes blocking on different areas at the same time, so you will probably need a set of area descriptor data structures, each of which identifies an event. Those data structures will need to be put in a list from which your code can find the appropriate area descriptor corresponding to the area that you need. Space for the area descriptors should be dynamically allocated, most likely using the kernel functions kmalloc() and kfree().

   You should not make any assumptions about whether the system is a uniprocessor or multiprocessor system. Be sure to properly synchronize access to your data structures. Moreover, be sure to select the appropriate synchronization primitives such that they are both correct and efficient, in this order. For instance, you should prefer a spinlock over a semaphore if-and-only-if you don't plan to sleep while holding it.

   You can choose to work at the level of wait queues using either the associated low-level routines such as add_wait_queue(), remove_wait_queue(), or the higher-level routines such as prepare_to_wait(), finish_wait(). You can find code examples both in the book (pages 58 - 61 of Linux Kernel Development) and in the kernel. If you prefer to use functions such as interruptible_sleep_on() and sleep_on(), then plan carefully because they can be racy in certain circumstances.

   HINT: a useful method to guarantee the validity of a data structure in the presence of concurrent create, access and delete operations, is to maintain a reference count for the object. Then, the object should only be freed by the last user. The file system, for example, keeps a reference count for inodes: when a process opens a file the reference count of the inode is incremented. Thus if another process deletes the file, the inode remains valid in the system (despite invisible) because its count is positive. The count is decremented when the process closes the corresponding file descriptor, and if it reaches zero then the inode is freed. A reference count must be protected against concurrent access, either using explicit synchronization or using atomic types (see atomic_t in Chapter 10 of the Linux Kernel Development book).

   You should properly handle any errors that may occur and report meaningful error codes e.g. -ENOMEM in the event a memory allocation fails. As always, you are encouraged to look for existing kernel code that performs similar tasks and follow the coventions and practices it provides.

3. (10 pts.) Write two C programs to test the system.

   Determining the prime factors of a large number can be useful if, for example, you want to break an encryption system. Your device is just a computer like any other computer, so you may want to use your device for this purpose. However, you do not want your device to be calculating prime numbers when you are holding it and doing things with it. You only want it to calculate when the current degree is in a specific range (0 <= degree <= 180).

   Your programs consist of a data source program (selector) and a calculator program (trial) that calculates the prime number factorization of source data. We details a specification of your programs in the following:

   • selector: A program accepts a starting integer as the only argument. When running, first, your program must take the write lock for when the device is positioned at 0 <= degree <= 180. After then, it writes the integer from the argument to a file called integer in the current working directory. When the integer has been written, the write lock must be released and re-acquired before writing the last integer + 1 to the same file (overwriting the content of the file). Your program should run until terminated using ctrl+c by the user. Before releasing the write lock, you should output the integer to standard out.
   • trial: When running, a program will acquire a read lock when the device is in a certain rotation. After taking the lock, it will open the file called integer in the current working directory and calculate the prime number factorization of the integer and write the result to the standard output. When done, it will close the file and release the read lock. This program calculates the factorization using the naive Trial Division method.

Each calculator program should prepend the output number with the name of the method used (ie. selector or trial).

First, run the selector and then run two trials. Verify that your rotation lock works well by making sure that no more numbers are output to the screen when the device rotation is outside of the trial's designated rotation range.

Extra Information for Fun Although TM1 doesn't have a orientation sensor, you can take a look at how sensor APIs work by trying out its accelerometer. If you are interested in exploring the sensor, refer to API document and tutorial. We provide this Makefile to compile the program that uses the sensor API.