/ W4118 Fall 2011 - Homework 2

Homework 2

W4118 Fall 2011

UPDATED Tuesday 09/20/2011 at 6:49pm EST

DUE: Monday 10/03/2011 at 11:59pm EST

Individual Written Problems:

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/hmwk2.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.

Exercise numbers refer to the course textbook, Operating System Concepts Essentials. Each problem is worth 5 points.

  1. Explain the difference between an interrupt and a trap.
  2. Exercise 2.18
  3. Exercise 3.8. Construct the process tree for your Android system.
  4. On all current computers, at least part of the interrupt handlers are written in assembly language. Why?
  5. Read the Linux source code and construct a state diagram to represent the relevant states that a process may be in at any given time. For each state, give the exact name used for the state in the source code.
  6. Describe what happens in the Linux kernel when a fork system call occurs. Be sure to list the important procedures that are called and explain the function of each. You can model your answer according to this example:

    The system call calls into this main function.
    The main function is called with the following parameters (explain their role): ...
    The main functioc performs the following important actions (explain each major setep involved):
  7. Describe what happens in the Linux kernel when a process exits and which main causes there are for it to exit. You should specifically mention when the reference counters for the task_struct is decremented, how other users of the dying process' task_struct can be guaranteed to validly access the data structure, and finally when and where the task_struct is finally freed. Your response should include a description of other important events that take place when a process exits and should follow the format from question 6.
  8. Write the C code for a new Linux 2.6.35 system call getstate() that takes no arguments and returns the process running state of the current process. The system call should be numbered 223. Your system call should work on a 32-bit x86 machine. For any files that you need to modify, indicate which lines in those files need to be changed by referring to the line numbers given by the Linux source code navigator for the 2.6.35 kernel. You should create a new kernel function sys_getstate() that performs the actual work for returning the running state.

Group Programming Problems:

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/hmwk2.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 checkpatch.pl script. 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. This assignment will be done using the Android emulator only. For more information on how to get your development environment configured, please see this page: Development Guide.

The VM you can use for this (and the remaining) homeworks can be downloaded from here.

If you want to be able to issue commands like 'adb' or 'emulator' without having to type the path, please change this entry in the ~/.bashrc file inside the vm from:
export ANDROID_SDK=~/android-sdk-os.f2010 to: export ANDROID_SDK=~/android-sdk-os.f2011 or alternatively re-download the VM (the image has been updated).

  1. (5 pts.) Create an Android Virtual Device (AVD), and install a custom 2.6.35 kernel in it.
    Decompress, and untar the Android SDK in the home directory on the VM: tar xjf android-sdk-os.f2011.tar.bz2
    cd android-sdk-os.f2011/platforms
    tar xjf android-os.f2011.tar.bz2     The appropriate tools directory has already been added to your path, so you should be able to run the Android SDK manager (assuming you have setup X11 display forwarding properly) using the android command.

    Once your AVD is setup, you can start it from the GUI to make sure it boots.
    NOTE: initial device rotation seems somewhat quirky in this version of the emulator. Use the Ctrl-F11 key sequence to "rotate" the emulator a couple of time to get the GUI state to sync.

    Once the emulator is running, it's time to build a custom kernel. The kernel source is located in your team's git repository in the linux-2.6.35-cm directory, and an appropriate ARM cross-compiler has been installed in the VM, and resides in the w4118 user's path. A default kernel configuration has been provided in the linux-msm-2.6.35 directory, so building the kernel should be as easy as: make ARCH=arm CROSS_COMPILE=arm-none-linux-gnueabi- (the trailing dash is necessary). Modifications to the default configuration can be done using: make ARCH=arm CROSS_COMPILE=arm-none-linux-gnueabi- menuconfig
    What's going on here?
    You are cross-compiling the linux kernel to run on a machine whose CPU architecture is different from the machine on which you are compiling. The ARCH=arm variable passed to make tells the build system to use ARM specific platform/CPU code. The CROSS_COMPILE make variable tells the build system to use compiler / linker tools whose names are prefixed by the value of the variable (check - you should have a program named arm-none-linux-gnueabi-gcc in your path). You may want to shorten the amount of typing you do to start a compile / config by setting these variables in your ~/.bashrc file: export ARCH=arm
    export CROSS_COMPILE=arm-none-linux-gnueabi-     This allows you to simply type make in the root of the kernel directory instead of constantly providing all the make variables.

    The final kernel image (after compilation) is output to arch/arm/boot/zImage. This file is the one you will be using to boot the emulator.

    Boot the Android emulator with your custom kernel using the emulator command: emulator -avd NameOfYourAVD -kernel arch/arm/boot/zImage -ramdisk ~/android-sdk-os.f2011/platforms/android-os.f2011/images/ramdisk.img -show-kernel
    You might want to make a shell alias for that command as well.
  2. (40 pts.) Write a new system call in Linux
    You have learned that a process is a program in execution. Processes are generally isolated from each other, for instance, one process cannot read the memory from another process. However, from time to time, there is a need for one process to talk to another process. A simple example of this is a pipe often used in the Linux command line, for instance ls -l | more. A general term for this phenomena is called Inter Process Communication (IPC). IPC can be implemented in many ways using for instance pipes, shared memory, sockets, message passing, and more.

    Android uses IPC much more extensively than traditional desktop and server OSes. In fact, Android has its own IPC implementation called Binder. Binder is a transaction based IPC and Remote Procedure Call (RPC) subsystem, which is for instance used when a process wants to draw content on the screen, since the screen is controlled by an Android system process called the SurfaceFlinger.

    You are going to write two new system calls to record Binder messages and show how processes in Android communicate:
    long binder_rec(pid_t pid, int state);
long binder_stats(pid_t pid, struct binder_stats *stats,
                  void *buf, size_t *size);
    You should define struct binder_stats as:
    struct binder_peer {
	uid_t uid;		/* UID of the communicating process */
	pid_t pid;		/* PID of the communicating process */
	char comm[16];		/* Name of communicating process */
};

struct binder_stats {
	char comm[16];		/* Name of recorded process */
	unsigned int nr_trans;	/* Total number of Binder transactions */
	unsigned int bytes;	/* Total number of bytes transferred */
};

    The binder_rec function takes the pid of the process for which to either enable or disable recording of Binder transactions. The state parameter should be 0 to disable recording and 1 to enable recording. All other values should return an error. On success, the functions should return 0. When recording is disabled, any of the recorded data in the kernel should be cleared and freed to avoid memory leaks.

    You can assume that none of the two system calls are executed at the same time.

    The binder_stats function provides the caller with the recorded Binder statistics. The functions takes the pid of the process for which to retrieve data, a pointer to a buffer buf of size size. A size less than sizeof(struct binder_peer) should return an error and a NULL pointer for the buffer should return an error. The system call should copy struct binder_peer consecutively to buf. On success, the function should return the number of bytes copied to the buffer in size and the return value of the function should be the number of struct binder_peers entries recorded, regardless of how many could be returned in the buffer.

    For both functions, passing an invalid pid should return an error.

    You should use the valid Linux kernel error codes as return values on errors:

    Each system call must be assigned a number. Your system calla should be assigned the numbers 223 and 366.

    The Binder code is contained in a specific kernel driver and is rather complicated and inaccessible. Therefore, we have prepared function for you in kernel/ipc_rec.c:
    void binder_trans_notify(int from_proc, int to_proc, int data_size)                              
{
       	...
}
    This function will be called on each binder transaction and it's your job to fill it in and create the necessary kernel data structures.

    Please give some thought to the data types you use. For instance, if an integer variable should never take negative values, declare it as unsigned to avoid strange overflow errors in your kernel code.

    HINT: In order to learn about system calls, you may find it helpful to search the linux kernel for other system calls and see how they are defined. You can use the Linux Cross-Reference (LXR) to investigate different system calls already defined. The files kernel/sched.c and kernel/timer.c should provide good reference points for defining your system call.

    HINT: You should not try to create your own linked list method  for the data structures inside the kernel, but use the existing infrastructure. See include/linux/list.h and look for other places in the kernel where lists are used for examples on how to use them (there are many such places). Also, the course materials contain information about linked lists in the kernel.

    HINT: When getting the uid of a process, you can simply follow the cred field.
  3. (5 pts.) Test your new system call Write a simple C program binder_info which can start/stop recording Binder transactions for a set of existing Android processes and also print recorded data. The program should take the following input arguments:
    binder_info <start|stop|print> pid0 [pid1 pid2 ...] ie., to start recording a process with pid 433, you would write: binder_info start 433 and to display the recorded data for the process you would write binder_info print 433

    The program should output data in the following format (where the second column is the uid of peers):
    > binder_info print 82
system_server (82):	1752 bytes	90 transactions
		system_server		82	1000
		putmethod.latin		148	10017
		m.android.phone		158	1001
		...
    you should also somehow indicate if not all peers could be printed.

    Compiling for the Android Emulator:
    You will have to cross-compile your test program to run under the emulator. Fortunately this is straight-forward so long as you use static linking. Compile your code with the ARM toolchain installed on your emulator. For single-file projects this is: arm-none-linux-gnueabi-gcc -static -o prog_name src_file.c.
    For more complex projects (or even the single file) you can use the following minimal Makefile: 
    # Set this to the name of your program
TARGET = output_name

# Edit this variable to point to all
# of your sources files (make sure
# to put a complete relative path)
SOURCES = mysrc1.c \
          mysrc2.c

# -----------------------------------------------
# 
# Don't touch things below here unless
# you know what you're doing :-)
# 
OBJECTS = $(SOURCES:%.c=%.c.o)
INCLUDE = -I.
CFLAGS = -g -O2 -Wall $(INCLUDE) -static
LDFLAGS = -static
CC = arm-none-linux-gnueabi-gcc
LD = arm-none-linux-gnueabi-gcc

default: $(SOURCES) $(TARGET)

$(TARGET): $(OBJECTS)
	@echo [Arm-LD] $@
	@$(LD) $(LDFLAGS) $(OBJECTS) -o $@

%.c.o: %.c
	@echo [Arm-CC] $<...
	@$(CC) -c $(CFLAGS) $< -o $@

clean: .PHONY
	@echo [CLEAN]
	@rm -f $(OBJECTS) $(TARGET)

.PHONY:

    A good (although minimal) reference on compiling / debugging command line programs for Android can be found here.

    See the Development Guide on how to install and run on the emulator.
  4. (10 pts.) Reason about Android IPC
    1. Set the program to record IPC for the zygote process and start some new applications. Is the zygote doing IPC? If not, what could be the role of zygote?
    2. Set the program to record IPC for a number of applications and use the applications while you're recording IPC. Is there some set of common processes that all applications seem to communicate with? Why could that be?
    3. Calculate the average size of a Binder message. What does the size of the Binder messages tell you about the type of IPC messages being passed through Binder. Which other IPC mechanism may be a better choice for sharing very large amounts of data between applications?
    4. The kernel configs you are using for this assignment configures the kernel to be non-preemptive. You are also running on a non-SMP system. What problems (if any) could there be with running this solution on an SMP system or on a preemptive kernel?
    5. What could happen if you run the binder_rec system call with state = 0 and the binder_stats system call at the same time?