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 located in the linux-2.6.35-cm/scripts directory within your repository. Points will be deducted for non-compliance!
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 get your development environment configured, please see this page: Development Guide.
The kernel programming for this assignment will be done using a Google
Android Developer Phone 1, ADP1,
(CVN students may complete this assignments using the emulator). The Android
platform can run on many different architectures, but the specific platform we
will be targetting is the ARM CPU family. The Google ADP1 phones use an ARMv6
CPU (specifically, ARM1136) which is embedded in a Qualcomm System-On-a-Chip
processor called the MSM 7201a (which actually incorporates the cellular
baseband processor, and the application processor).
Because the target CPU is (most likely) 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 previous homeworks.
The programming portion of the assignment is 70 points.
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 starts the GPS sensor, and updates the kernel with the GPS location.
The new system call number should be 366, 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.
On the Android platform, GPS sensor data decoding is done in user space in the libhardware_legacy.so library. This library provides an interface structure which allows the user to initialize, start and stop the GPS navigtaion / decoding. In your homework git repository you will find a template daemon project in the userspace/src/gpsd directory that properly links against the hardware library, and has all necessary include paths properly configured. Use the library interface found in userspace/inc/hardware_legacy/gps.h to start up and interact with the GPS sensor. Retrieve a GpsInterface pointer from the library using the gps_get_interface() function which is a generic way of accessing the GPS interface that will work on both the device and the emulator.
IMPORTANT!:For the daemon to work on you need to disable the use of location services from other programs by going to Menu -> Settings -> Location and Security Settings -> Un-check "Use GPS satellites" then reboot your emulator (e.g. using adb reboot).
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 linux-2.6.35-cm/fs/ directory for all the file system code, and in the linux-2.6.35-cm/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 linux-2.6.35-cm/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
misc/mke2fs.c file to match the new physical layout. Compile
the tool set using:
w4118@osvm:~/hmwk6/userspace/src/e2fsprogs$ autoconf
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 367 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 ADP1 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 the qemu emulator console to manually set GPS coordinates. Obtain an emulator console: telnet localhost 5554, then use the geo command. See this page for documentation. (feel free to be creative with your forced GPS coordinates!)
ADP1 device users should be aware that the GPS sensor will only function outside. It may be advisable to use the provided terminal emulator on your phone (DevTools → Terminal Emulator) - be sure to set permissions on your ext2 file system properly to allow the terminal user to create files!
HINT: It can be hard to obtain a GPS fix on the G1 devices without cell phone connection. There are three things you can do to aleviate this: (1) Make sure the compass driver is enabled in the kernel by selecting the CONFIG_SENSORS_AKM8976 option is set in the kernel. (2) Follow the instructions in the Development Guide. for installing the WiFi kernel module on the device and connect to a WiFi network (remember to use the full absolute kernel path when building the kernel module). (3) Set the time on the phone to be correct.
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 can be obtained here and you run it like this:
./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 into the log file.
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 printed 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 logfile of the walk you take with the solution as part of your GIT repositories.
CVN students can input the values in the emulator of a walk they would like to take somewhere in the world.
Kernel Hacking: