All non-programming, written problems in this assignment are to be done by yourself. Group collaboration is permitted only on the kernel programming problems. All homework submissions (both individual and group) are to be made via Git. Git repository access will use the same public/private key-pair you used for previous homeworks (see these Git instructions).
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/hmwk6.git
(replace UNI with your own UNI). This repository will
be accessible only by you.
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/hmwk6.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. One important thing to remember is to pull any changes into your local repository before trying to push any commits to the class server. Some useful screen casts / tutorials can be found on gitcasts.com.
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. Please follow the Linux kernel coding style.
Hint(1): use the checkpatch.pl script to ensure your code conforms to this standard. Points will be deducted for non-compliance!
It's a good idea to clone your repository after your final push (but before the deadline) and test the cloned code to be sure it behaves as expected and that there are no missing files.
All kernel programming assignments in this year's class are done on the Android operating system and targeting the ARM architecture.
The kernel programming for this assignment will be done using a
Nexus 7 tablet. The Android
platform can run on many different architectures, but the specific platform we
will be targeting is the ARM CPU family. The Nexus 7 tablets use an ARMv7
quad-core CPU which is embedded in the Nvidia Tegra 3 SoC.
Because the target CPU is different from the CPU running in your
personal computer, you will have to cross-compile any software, including
the linux kernel, to run on the different platform. You should use the same
virtual machine
you used for homeworks 2 through 5.
A key feature of modern mobile devices is the availability of various forms of physical sensor input such as accelerometer / orientation input, compass / directional input, and GPS / location input. In particular, mobile computing is increasingly taking advantage of location information to do things like geo-tag photos, provide turn-by-turn directions, locate friends / family, find restaurants, etc. Many of these "location aware" applications use the location information in an application specifc way, and the code which uses this data must be re-written every time a new "location aware" application is developed.
In this homework, you will develop a new kernel mechanism for embedding GPS location information into the filesystem, so that this information can be used by any application. Please review Chapters 13 (The Virtual Filesystem) in your Linux Kernel Development book.
Write a new system call which updates the kernel with the device's current location then write a user space daemon called gpsd which reads the GPS sensor values from a file produced by a custom Android application. The daemon should then update the kernel with the GPS location.
The new system call number should be 376, and the prototype should be:
int set_gps_location(struct gps_location __user *loc);Where struct gps_location should be defined as:
struct gps_location {
double latitude;
double longitude;
float accuracy; /* in meters */
};
Only a system administrator should be able to set the GPS location. All GPS related functions should be put in kernel/gps.c and include/linux/gps.h.
In your homework git
repository you will find a template daemon project in the
userspace/src/gpsd directory that properly links against the
C library and has all necessary include paths properly configured.
A custom Android application, GPSLocator.apk, has been
provided in the userspace directory. This application
will access the GPS on your device and write the values of latitude, longitude,
and accuracy (in that order) to your screen and to the file /data/media/gps_location.txt.
The three values are separated by a newline, note that accuracy
is of type float and not double. In your daemon, read the values written to that file and
set the GPS location in the kernel using your system call. You should read the values once
every second.
To install GPSLocator.apk (device only, this will not work for the emulator) run this command under your userspace directory in your VM:
adb install GPSLocator.apk
The application can then be accessed by going to the menu on your device
Not required: In case of the emulator or when debugging you can feed in fake GPS values from your gps
daemon to the kernel (Hint: you can create an array of gps_location structs that include
predefined gps values and simply round robin through the array to test in the emulator).
IMPORTANT!: For the application to work on the device you need to enable the use of location services by going to Menu -> Settings -> Location Access and enabling all three options
Modify the Linux inode operations interface to include GPS location manipulation functionality, then implement the new operations in the ext2 file system.
To modify the inode operations interface, add the following two function pointers to the struct inode_operations structure in include/linux/fs.h:
int (*set_gps_location)(struct inode *); int (*get_gps_location)(struct inode *, struct gps_location *);
You only need to implement this GPS location feature for the ext2 file system. You should update a file's GPS coordinates whenever the file is created or modified. Look in the android-tegra-3.1/fs/ directory for all the file system code, and in the android-tegra-3.1/fs/ext2/ directory for ext2 specific code. You will need to change the physical representation of an inode on disk by adding the following four fields in order to the end of the appropriate ext2 structure:
i_latitude (64-bits) i_longitude (64-bits) i_accuracy (32-bits) i_coord_age (32-bits)
HINT: You will need to pay close attention to endian-ness of the fields you add to the ext2 physical inode structure. This data is intended to be read by both big and little endian CPUs. Also note that the kernel does not have any floating point or double precision support.
Because you are changing the physical representation of the ext2 inode structure, the resulting file system is not technically ext2 anymore. Therefore, you will need to change the EXT2 magic super block number in android-tegra-3.1/include/linux/magic.h to be 0xEF54.
Now that you have modified the ext2 file system's physical representation on disk, you
will also need to modify the user space tool which creates such a file system. In your
git repository you will find the ext2 file system utilities in the
userspace/src/e2fsprogs/ directory. Modify the appropriate
file(s) in lib/ext2fs/ and the to match the new physical layout. Compile
the tool set using:
w4118@osvm:~/hmwk6/userspace/src/e2fsprogs$ ./configure
w4118@osvm:~/hmwk6/userspace/src/e2fsprogs$ make
The tool you will be most interested in is misc/mke2fs. This tool should now create an ext2 file system with your custom modifications. You will use this tool on your VM or host linux machine in Problem 3 to test the geo-tagged file system
Create a modified ext2 file system using the mke2fs program from Problem 2, and write a user space utility named file_loc which will output a file's embedded location information including the GPS coordinates, the data age and a Google Maps link.
In order to retrieve a file's location information, write a new system call numbered 377 with the following prototype:
int get_gps_location(const char __user *pathname, struct gps_location __user *loc);
On success, the system call should return the i_coord_age value of the inode associated with the path. The get_gps_location system call should be successful only if the file is readable by the current user. It should return -1 on failure setting an appropriate error code which must include ENODEV if no GPS coordinates are embedded in the file.
The user space utility, file_loc, should take exactly one argument which is the path to a file or directory. It should then print out the GPS coordinates / accuracy and data age of the specified file or directory, and also format a Google Maps URL which can be pasted into a web browser to view the location.
In order to use this utility, you will need to create a modified ext2 file system using
the mke2fs utility you modified in Problem 2.
Create the ext2 file system on your VM or linux host using the loop back device:
w4118@osvm:~/hmwk6$ dd if=/dev/zero of=hmwk6.fs bs=1M count=1
w4118@osvm:~/hmwk6$ sudo losetup /dev/loop0 hmwk6.fs
w4118@osvm:~/hmwk6$ sudo ./userspace/src/e2fsprogs/misc/mke2fs -I 256 -L w4118.hmwk6 /dev/loop0
w4118@osvm:~/hmwk6$ sudo losetup -d /dev/loop0
The file hmwk6.fs should now contain a modified ext2 file
system. Before using the file on your emulator or the device, you will probably
need to setup a couple of symlinks in the /dev/ directory
in order to properly mount/umount a file system contained in a regular file
(this is referred to as "loopback" mode which allows the kernel to interact with
a regular file as a block device). By default, Android puts all the loop back
device files in /dev/block/, but the mount utilities
look for these files in /dev/. Run the following series of
commands on either the emulator or the device to fix the problem (you will have
to do this every time you reboot, so wrapping it in a shell script may be userful):
w4118@osvm:~$ adb shell ln -s /dev/block/loop0 /dev/loop0
w4118@osvm:~$ adb shell ln -s /dev/block/loop1 /dev/loop1
w4118@osvm:~$ adb shell ln -s /dev/block/loop2 /dev/loop2
w4118@osvm:~$ adb shell ln -s /dev/block/loop3 /dev/loop3
w4118@osvm:~$ adb shell ln -s /dev/block/loop4 /dev/loop4
w4118@osvm:~$ adb shell ln -s /dev/block/loop5 /dev/loop5
w4118@osvm:~$ adb shell ln -s /dev/block/loop6 /dev/loop6
w4118@osvm:~$ adb shell ln -s /dev/block/loop7 /dev/loop7
You can now push the file to either your device or your emulator and mount it:
w4118@osvm:~/hmwk6$ adb push hmwk6.fs /data/misc/hmwk6.fs
w4118@osvm:~/hmwk6$ adb shell
# mkdir /data/misc/hmwk6
# mount -o loop -t ext2 /data/misc/hmwk6.fs /data/misc/hmwk6
You can now create files and directories in /data/misc/hmwk6 which should be geo-tagged.
You need to include the hmwk6.fs file in you final git
repository submission, and the filesystem must contain at least 1 directory and
2 files all of which must have unique GPS coordinates. Show the output of
file_loc in your README when called on each of the files /
directories you create. NOTE: be sure to un-mount the filesystem before
pulling the file off of the device/emulator, otherwise you risk corruption:
w4118@osvm:~/hmwk6$ adb shell umount /data/misc/hmwk6
w4118@osvm:~/hmwk6$ adb pull /data/misc/hmwk6.fs
Emulator users can use fake GPS coordinates. Make sure you include those coordinates in your README file (feel free to be creative with your forced GPS coordinates!)
HINT: If you run into trouble using loop back devices, the losetup utility has been cross-compiled and provided to you in your git repository: userspace/bin/losetup. You can push this binary to the emulator/device and use the -h option for a description of the different operations it can perform.
HINT: Wait until your emulator and device is fully booted before mounting the loopback device. Otherwise you may receive errors from the losetup utility.
Instead of demo'ing your homework assignment we encourage you to take a recreational walk - with your GPS enabled device of course.
We have created a binary for you that should run on both the device and the emulator.
The binary is provided in your git repository: userspace/bin/walk_tool. To run the binary, push to the emulator or device, and use the command:
./walk_toolIt will dump the location every 20th second until ~30 minutes has passed (max number of waypoints Google allows) and also write the track of the waypoints (accessible URL) into the log file. The coordinates along with accuracy are also written to an automatically created file: log_file_coords
Yielding a result like this:
Google Static Maps Link
You can also send the process a signal and it will stop before the 20-30 minutes. The gps coordinates will be appended to the URL while the tool is running. You may need to change the zoom parameter in the query string if you take a really long walk.
Please submit the log_file and log_file_coords of the walk you take with the solution as part of your GIT repositories.
Kernel Hacking: