The Git repository you will use for the individual, written portion
of this assignment can cloned using: git clone
gitosis@os1.cs.columbia.edu:UNI/hmwk3.git (replace UNI with your own UNI). This repository will be
accessible only by you, and you will use the same SSH public/private
key-pair used for Homework 1.
Group programming problems are to be done in your assigned groups.
The Git repository your entire group will use to submit the group
programming problems can be cloned using: git clone
gitosis@os1.cs.columbia.edu:TEAM/hmwk3.git
(Replace TEAM with the name of your team,
e.g. team1). This repository will be
accessible to all members of your team, and all team members are
expected to commit (local) and push (update the server) changes /
contributions to the repository equally. You should become familiar
with team-based shared repository Git commands such as git-pull, git-merge, git-fetch. You can see the documentation for these
by writing $ man git-pull etc. You may need
to install the git-doc package first (e.g. $ apt-get install git-doc.
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. 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.
All kernel programming assignments in this year's class are done on
the Android operating and targeting the ARM architecture. For more
information on how to use adb and aliasing refer to Homework 2. Use
"adb -e" for emulator commands and "adb -d" to direct the commands to
the device. If you run in to a read-only disk error then type "adb remount"
add -e or -d accordingly.
You can use Homework 2's VM for this assignment which can be
downloaded from here.
NOTE:Your Nexus 7 must be unlocked. First, enable USB debugging by going to "Settings" then "Developer Options" on your Nexus 7 device. Make sure you check the "USB debugging" option. Your VM should be connected to your Nexus 7 USB device (go to settings on your VMware product and connect to your USB device). Next, unlock your Nexus 7 device by booting in to "fastboot" mode and then typing "fastboot oem unlock" in your VM. Follow the instructions on your Nexus 7 screen. Finally, boot in to fastboot mode again. Unlocking is a one-time process.
On the Android platform, device orientation is accessed via an on-board "digital compass" device (Asahi Kasei AK8975) You are to write a daemon process, called orientd, which polls the compass and updates the devices orientation in the kernel using the system call interface below:
/*
* sets current device orientation in the kernel.
* syscall number 376
*/
int set_orientation(struct dev_orientation *orient);
struct dev_orientation {
int azimuth; /* angle between the magnetic north
and the Y axis, around the Z axis
(0<=azimuth<360)
0=North, 90=East, 180=South, 270=West */
int pitch; /* rotation around the X-axis: -180<=pitch<=180 */
int roll; /* rotation around Y-axis: +Y == -roll,
-90<=roll<=90 */
};
Design and implement a new kernel synchronization primitive that will provides reader-write locks based on device orientation. Reader-writer locks works 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 the 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 orientation of the device. For example, if a writer grabs the lock for when the pitch is +-5 and the roll is +- 5 for all value of the azimuth, then readers cannot grab any locks in that area, but readers can grab a lock when the pitch is between 80 and 100, and when the roll is between between 20 and 30, for all values of azimuth (given no writer has grabbed a lock covering that area).
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 orientation, locks can be released irrespective of the rotation.
When the device orientation is updated in the kernel (see Problem 2), the processes that are waiting to grab a lock on an area entered by the new orientation 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 orientation 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 orientation range
* returning 0 on success, -1 on failure.
* system call numbers 377 and 378
*/
int orientlock_read(struct orientation_range *orient);
int orientlock_write(struct orientation_range *orient);
/* Release a read/or write lock using the given orientation range
* returning 0 on success, -1 on failure.
* system call numbers 379 and 380 */
int orientunlock_read(struct orientation_range *orient);
int orientunlock_write(struct orientation_range *orient);
/*
* Defines orientation range. The ranges give the "width" of
* the range. If one of the range values is 0, it is not considered
* as defining the range (ignored).
*/
struct orientation_range {
struct dev_orientation orient; /* device orientation */
unsigned int azimuth_range; /* +/- degrees around Z-axis */
unsigned int pitch_range; /* +/- degrees around X-axis */
unsigned int roll_range; /* +/- degrees around Y-axis */
};
You should modify the set_orientation system call written in Problem 2 to handle processes blocking on a lock that covers the new orientation. 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 (albeit 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.
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 don't 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 lying on a table face down.
HINT: The device is lying face up, when the pitch is around 0 and roll is around 0, for all values of azimuth. The device is lying face down, when the pitch is around 180 and the roll is around 0, for all values of azimuth. Remember that the values can also be negative and that -178 for the pitch is equivalent to 182.
Your programs are going to do the following:
Verify by moving turning device face up and make sure no more numbers are output to the screen. Also make sure that the two calculating processes at no time are working on different numbers.
adb -d push system/lib/libsensorservice.so /system/lib/
adb -d shell setprop persist.sensorservice.enable 0
adb -d reboot