Systems Programming (Semester 1, 2012)

Assignment 1 for Systems Programming

This is your first assignment for Systems Programming, Semester 1, 2012

The purpose of this assignment is to get familiar with system level programming. The assignment consists of a programming task and a number of exercises that will be made available incrementally as milestones (so check this web page regularly to make sure you won't miss out on your next milestone!) Milestones are due every week and need to be submitted in or before the lab they are due in. You will only get marks for a milestone if you hand in the milestone before its deadline. See below below for the milestones and deadlines.

To submit a milestone, you need to commit everything that belongs to the solution into your Subversion repository on dwarf.ict.griffith.edu.au and tag it accordingly (i.e. milestone1 for the first milestone, milestone2 for the second milestone, etc.).

Please note that this is an individual assignment! Everything you hand in must be your original work (e.g. you cannot hand in any material created by anyone else, done as group work, or downloaded from the internet)!

Programming Task

The task for this assignment is to create (in stages), a number of small command line programs in C. For more details, see the milestones below.

All programs need to be tested and debugged before submission! Make sure that the final program behaves exactly as specified.

The overall program and all modules and functions need to be accompanied by source code documentation, a description of how to use the program, and a test report.

Milestones and Deadlines

Week 1, 28 February 2012 (5 marks)

Subversion Repository

Log into dwarf.ict.griffith.edu.au (dwarf) using ssh, putty, or another ssh client, to create a Subversion Repository for Systems Programming and the first assignment: set up the .spsvn-2012 repository in your home directory using the 

svn_setup sp

command on dwarf.

You can now check out the (empty) working directory for assignment 1 on your workstation or on dwarf using, e.g.:

svn checkout file://$HOME/.spsvn-2012/ass1/trunk a1

This will create an a1 directory that you can create your assignment 1 files in. Don't forget to add each file that belongs to your assignment (e.g. using svn add file), then commit all changes (using svn commit).

To get marks for the repository, you need to create a milestone1 tag for your final milestone submission using (on one single line):

svn copy file://$HOME/.spsvn-2012/ass1/trunk file://$HOME/.spsvn-2012/ass1/tags/milestone1 -m "log message"

Make sure you only perform the last step above after you have completed all the steps below and want your assignment marked!

Hello World

Create a Hello World program hello.c that compiles without warning when using

clang -Wall -o hello hello.c

Add your program to the repository using svn add hello.c and commit it after every change using svn commit -m "log message" (replace log message with a text that descripts the changes you have made).

Makefile

Create a Makefile that compiles your program so that you can run it from the command line using ./hello (followed by enter).

Add your Makefile to the repository using svn add Makefile and commit it after every change using svn commit -m "log message" (again, replace log message with a descriptive log message).

A Simple cat Command

The objective of this milestone is to get familiar with basic input/output (I/O) by implementing a simple cat command. What is cat? Use man cat on dwarf to find out! No options need to be implemented for this milestone and it is sufficient for this week for the program to read from standard input (stdin) and write to standard output (stdout). However, you should design your program so that it can easily be extended to allow other options for the cat command as described in the manpage!

Makefile Update

All the milestones for this assighment should reside in the same (ass1) folder in the repository. Therefore, you need to add an all target to your Makefile that compiles all milestones. For this week, this will be hello and cat.

Commit your Makefile changes to the repository!

Week 2, 6 March 2012 (8 marks)

Options for cat

Add some options to your cat program that correspond to the ones described in the Linux manpage for cat. The options that need to be implemented for this milestone (see below) are -n to display line numbers and -E to display a dollar sign (`$') at the end of each line. Further options need to be implemented later!

Specifying Files on the Command Line

In addition to reading from stdin, allow any number of files to be specified on the command line that are read from sequentially and printed to stdout sequentially (if no file is specified, read from stdin as before). When numbering lines in multiple files using -n, make sure that line numbers start with 1 again for each new file!

Modularity

As your program gets bigger, split the code into multiple functions (a good rule of thumb is that a function should never be longer than about 25 to 50 lines of code). Use your best judgement of which code should go into which functions! Make sure this and all subsequent milestones are sufficiently modular!

Testing

Test every change with different input! Make sure your program behaves exactly as the original system cat command (for the options you need to implement). An easy way is to re-direct stdout to a file for both your own and the system cat and then compare the two files using diff, e.g.: 

	  cat some_options > system_output
	./cat some_options > my_output
	diff -u system_output my_output

If the diff comes up empty, then there is no difference between the two files.

Don't forget to use the svn copy command to submit all your files as milestone2!

Week 3, 13 March 2012 (10 marks)

A more advanced cat Command

The objective of this milestone is to get familiar with string processing and low-level memory manipulation by improving the cat command from the previous milestone. The additional options that need to be implemented for this milestone (see below) are -b, -s, -t, and -v, and -e.

Preparation

Continue on from last week's version of the program. Make sure you work on a checked out copy of the trunk, not the milestone tag you submitted last week!

Implementation Steps

Use small steps similar to last week to improve your cat program and make sure you test and commit each step. Keep refactoring your code in this and subsequent milestones (i.e. split the code into multiple functions once they get too complicated). Here is a recommendation for implementation steps (for hints, see the hints section at the bottom of this assignment!):

  1. Implement the -b option to number non-blank output lines, starting at 1.
  2. Commit the previous step to the repository!
  3. Implement the -s option to squeeze multiple adjacent empty lines into one.
  4. Commit the previous step to the repository!
  5. Implement the -v option to visibly display non-printing characters (e.g. ^X for Control-X).
  6. Commit the previous step to the repository!
  7. Implement the -t option, behaving the same as -v, but also displaying tab characters as ^I.
  8. Commit the previous step to the repository!
  9. Implement the -e option that combines the effects of last week's -E option with the effects of -v.
  10. Commit the previous step to the repository!

Make sure your program keeps behaving exactly as the original cat system command and keep making sure that you properly catch and handle errors!

Don't forget to use the svn copy command to submit all your files as milestone3!

Week 4, 20 March 2012 (10 marks)

A Simple CLI

Now that you are familiar with basic input and output, your task for this milestone is to implement a simple command line interface (CLI). The shell on dwarf (bash) that interprets the commands you type, is an example for a very powerful command line interface. Your shell does not have to be as powerful, but it should ultimately be able to execute arbitrary commands entered by the user.

Preparation

Don't forget that all the milestones for this assighment need to reside in the same (ass1) folder in the repository. Therefore, you need to create a shell target in your Makefile and add it to your all target.

Commit your Makefile changes to the repository!

Implementation Steps

As with the previous milestone, implement your milestone in small steps and don't forget to test and commit every single step! As always, don't forget to create separate functions for parts that have different functionality! Implementation steps for your CLI are:

  1. Create a simple program that (in a loop) reads individual lines from stdin (and, for debugging purposes prints each line to stdout). You can use a fixed size buffer (80 characters minimum size) to read one line, but make sure your buffer does not overflow (see the hints below).
  2. Commit the previous step to the repository!
  3. Implement a simple, internal exit command that exits the CLI. I.e., when the user types exit (followed by enter), your program should exit with a status of EXIT_SUCCESS.
  4. Commit the previous step to the repository!
  5. Execute arbitrary commands entered by the user (other than exit) by using the system() function. (Also remove the debug output of each entered line if you haven't already done so.)
  6. Commit the previous step to the repository!
  7. Add a README text file to the repository (if you haven't already done so for the previous milestone). Add a Milestone 2 heading to your README that briefly explains how your program works.
  8. Commit the README to the repository!
  9. Replace the system(command) call in your program with
    execvp(command, argv)
  10. Commit the previous step to the repository!
  11. Explain the differences you can notice between using the system() and the above execvp() invocation in your README file. Explain the reasons for these differences (the first sentence in the DESCRIPTION of execvp() should give you the vital hint).
  12. Commit the README to the repository!
  13. Create a my_system() function that behaves like system(), but uses execvp() to execute the external command. For that purpose, you need to create a new process that executes the external command (see the hints below). You need to block (wait for that process to finish) before the my_system() function returns! It is very important that you properly wait for every child process. Orphaned child processes stay around forever as zombie processes, or at least until you manually remove them! If the number of processes (including zombies) exceeds your quota, you will no longer be able to log into dwarf or otherwise create new processes!
  14. Commit the previous step to the repository!
  15. Allow commands to be run in the background (without waiting for them) if they are terminated with an & (ampersand) character. Remove the & character before passing the command line to execvp() (you can assume that the & character, if given, is the last character on the line). E.g. ls & should run the ls command in the background! To avoid zombies, you can ignore the SIGCHLD signal before you fork your child process for this milestone!
  16. Commit the previous step to the repository!

Don't forget to use the svn copy command to submit all your files as milestone4!

Week 5, 27 March 2012 (9 marks)

A Mini Shell

The goal for this milestone is to handle basic shell functionality from within your own program.

Preparation

No special preparation is needed, as you will be expanding the shell program from the previoius milestone. Make sure you have submitted the previous milestone to the repository before you start, though!

Implementation Steps

As with the previous milestone, implement your milestone in small steps and don't forget to test and commit every single step! As always, don't forget to create separate functions for parts that have different functionality! Implementation steps for your enhanced shell are:

  1. Implement an internal cd directory command that allows you to change your current working directory. Explain in your README why calling the existing cd shell command (through system() or execvp() from the child process) won't work (see the hints below).
  2. Commit the previous step to the repository!
  3. Make sure that only the base name of the program is used in the argument array, not the full execution path (keep in mind that the program to execute needs to be passed twice, first using the full execution path, and second by calling the basename() function for what you pass as argv[0]). You can limit the total number of arguments to a fixed maximum (16 parameters or more), but input with more parameters needs to be detected and treated properly! For more information, see the hints below!
  4. Commit the previous step to the repository!
  5. Add the ability to handle program names and parameters that contain white space: everything in between two double quote (") characters needs to be treated as one word! E.g. "./hello world" should be treated as the name of one program called hello world (in the current directory) rather than a program called hello with one parameter world.
  6. Commit the previous step to the repository!
  7. Allow the sequence \" (a backslash followed by a quote) to represent a single quote within a word. E.g. "./hello \"world\"" should represent a program in the current directory called hello "world" (including the quotes).
  8. Commit the previous step to the repository!
  9. Allow stdout to be re-directed to a file by using (in place of any parameter) the sequence > filename, i.e. the greater than sign followed by zero or more white spaces, followed by a file name to re-direct to. Allow double quotes around the file name (as described in the previous step) for the file name to contain white spaces. Allow double quotes around the greater than sign to pass a literal > as a program parameter instead of re-directing.
  10. Commit the previous step to the repository!
  11. Allow stdin to be re-directed from a file by using (in place of any parameter) the sequence < filename, i.e. the less than sign followed by zero or more white spaces, followed by a file name to re-direct from. Allow double quotes around the file name (as described above) for the file name to contain white spaces. Allow double quotes around the less than sign to pass a literal < as a program parameter instead of re-directing.
  12. Commit the previous step to the repository!
  13. Allow multiple programs to be executed by separating them using semi-colon ; characters. Wait for a program to finish before starting the next, unless that program was started in the background using the ampersand & character (in which case you should start the subsequent program straight away). E.g. echo "starting ls:" ; ls ; echo "done." should print starting ls: then run the ls command and then print done.
  14. Commit the previous step to the repository!
  15. Allow mixing of background and foreground processes by writing and installing a proper signal handler function (see the hints below)!
  16. Commit the previous step to the repository!
  17. Like the real shell (bash), when running a background process, print the process number (that you count) and its process ID when the background process starts and ends. The output should show the background process number in square brackets, followed by the process ID. When the process is finished, this should be followed by the word Done. I.e. for the first background process, print 
    	[1] 1234
    and when the process finishes, print 
    	[1] 1234 Done
  18. Commit the final step to the repository!

Don't forget to use the svn copy command to submit all your files as milestone5!

Week 6, 3 April 2012 (8 marks)

Using Pipes

The standard shell allows programs to be chained up through pipes. This way the output of one program can be used as the input into the next program. For example, executing /bin/ls | /usr/bin/sort -r will list the content of the current directory in reverse alphabetical order.

How does the shell achieve the above behavour? It runs the /bin/ls command in the background and re-directs its standard output into a pipe. The pipe is then fed into the /usr/bin/sort program: its standard input is re-directed from the pipe.

What is a pipe? A pipe is a mechanism that lets one process send data to another through normal file system functions such as read() and write() (and all the higher level functions on top of that, e.g. fgets(), fprintf(), etc.). A pipe does not actually create a file on disk, but is provided as an inter-process communication mechanism by the Operating System and treated like a virtual file. Any data written into the writing end of the pipe can be read from the reading end (e.g. by another process).

Running Scripts

Most shells allow running scripts by redirecting input from a file. E.g. if you enter the command source somefile.sh this will cause the shell to read and execute the commands from the file somefile.sh before transferring control back to standard input.

Command Line Editing

Modern shells have more comfortable command line editing. For example, they allow the cursor keys to be used to go back and forth through command history and for editing within the current line. Most shells also allow command completion using the TAB key.

For this, the terminal allows setting raw mode through the tcsetattr() function. However, reading and interpreting raw keystrokes through interpreting the termincal capabilities (termcap) can be cumbersome. A simpler way is to use the readline() library that comes with most POSIX Operating systems.

Implementation Steps

  1. Allow the vertical bar | character to be used to separate multiple programs (instead of the semicolon), in which case stdout of the previous program should be directed into a pipe that is fed into stdin of the subsequent program (see the hints below!).
  2. Commit the previous step to the repository!
  3. Add a source command with a file name parameter, causing your shell to read commands from that file and then return control back to standard input.
  4. Commit the previous step to the repository!
  5. Add readline() support so users can use the cursor keys to browse history and edit commands they enter. Make sure you only use readline() when reading from standard input (but not while commands are read from a file using your source command)!
  6. Commit the previous step to the repository!

Use the svn copy command to submit all your files (including everything from the previous milestones as well) as milestone6!

Bonus Marks

A maximum of 20 bonus marks may be awarded for features that significantly go beyond the requirements of this assignment (e.g. allowing command completion by searching the PATH environment variable so that the user can press the TAB key, adding an internal if command that allows you to conditionally execute a command based on the exit status of a previous command , etc.). While these bonus marks cannot take you past the maximum 50 marks (25 %) for the assignment, they can make up for any marks you lost elsewhere in this assignment.

If you want to go for bonus marks, please put documentation of what you did that you think deserves bonus points into a file called BONUS

Some Hints

Hints for Milestone 1 (and later milestones)

Reading Input Characters
The fgetc() function can be used to read characters from arbitrary input streams (you can use fgetc(stdin) to read from stdin). Be aware that fgetc() returns an int (not a char!) that will contain the value EOF if you reach the end of a file.
EOF on Standard Input
Under Linux, you can press Control-D to signal EOF.
Writing Output Characters
The fputc() writes a character to an output stream.

Hints for Milestone 2 (and later milestones)

Opening Files
You can use fopen() to open a file stream (for reading or writing with the functions above). Don't forget error checking! You also need to call fclose() to close any streams you opened using fopen()!
Getting Options
To parse command line options, use the getopt() function.

Hints for Milestone 3 (and later milestones)

Printing Control Characters
Keep in mind that characters are just integer numbers, so, for example, if you add 1 to the character 'A', you get 'B'. Control characters incidentially start at the beginning of the character set, i.e. ^A is ASCII code 1, ^B is 2, ^C is 3, etc. (you can verify this if you look at an ASCII table such as this one.)

Hints for Milestone 4 (and later milestones)

Reading a Single Line
The fgets() function reads a single line (up to the size given) into a fixed-size buffer.
Creating a new Process
The fork() function creates a new process. The peculiarity of fork() is that it returns twice: once for the parent process, and once for the newly created child process. The return value of fork() lets you distinguish between the two cases (see the manual page for details).
Waiting for a Child Process
The wait() system call allows you to wait for any child process to finish. If you want to wait for a specific child process (as identified by its Process ID, pid), you can use the The waitpid() system call. In both cases, the exit status of the child can be retrieved by using the WEXITSTATUS(status) macro on the status returned by wait() or waitpid().
Killing Zombie Processes
To see all your processes, run the ps x command on dwarf. Processes marked with Z are zombie processes. Note the Process ID (PID) number, then use kill -9 PID to kill the process with the given PID.
Ignoring the SIGCHLD Signal
To ignore the SIGCHLD (and avoid having to wait for a child process), you can use the signal() function, e.g.: 
	signal(SIGCHLD, SIG_IGN);	// ignore child signal

Hints for Milestone 5 (and later milestones)

Changing the Working Directory
The chdir() function allows to change the working directory of the current process. While newly created children inherit the working directory from the parent, changing the working directory of the parent afterwards won't affect children that have been created previously. Similarly, changing the working directory in a child process won't have any effect on the parent process!
Getting the Base Name
The base name of a file is the name of the file, stripped off its full path and is returned by the basename() function. E.g. basename("/bin/ls") will just return "ls".
Dynamically passing arguments
The execvp() function is not very suited for dynamically creating and passing an argument list. Better create an argument array (an array of char * yourself and pass that to the execvp() function. Note that the array must be terminated with a NULL pointer!
Re-directing stdin and stdout
Both stdin and stdout can be re-directed to a different file using the freopen() function. Be sure to use this after fork() (and before execvp()) so that only the program you want to execute (the child process) is affected by the re-direction, not the parent process!
Installing a Signal Handler
The signal() function allows you to specify a function that should be called whenever a particular signal (such as SIGCHLD) arrives. The function must be declared as taking an int and not returning anything (void). To handle SIGCHLD, this function needs to loop and collect the return status of any child that has terminated. This can be achieved passing the WNOHANG option to the wait3() function.

Hints for Milestone 6

Creating Pipes
A(n unnamed) pipe can be created using the pipe() system call. This system call fills in an array of two integers with the file descriptors for the corresponding pipe. The first integer is the file descriptor for reading from the pipe (the reading end of the pipe), while the second integer is the file descriptor for writing data into the pipe (the writing end of the pipe). These file descripts will be inherited by child processes when fork() is called. It is important that each process closes the end of the pipe that it does not use (e.g. the writing process should close the reading end and vice versa). See the PipeExample code for a simple example.
Re-directing stdio to and from Pipes
You can re-direct stdout and stdin to and from a pipe using dup2(). The dup2() function takes two file descriptors (ints) and copies the first file descriptor over the second. This way, you can copy the file descriptor you received from pipe() to STDIN_FILENO (for stdin) or STDOUT_FILENO (for stdout).
Using readline()
Read the readline user manual on the info system for a comprehensive guide on how to use history and command line completion. You can also find a readline example on the Course Content page.
Searching the PATH (Bonus Marks)
Shells use the PATH environment variable to store the default locations they search for executable programs. E.g. an echo $PATH in your standard shell (bash) will show you your current search path. In C, you can use getenv("PATH") to return a string that contains the current search path. The search path consists of a number of path components (directories) that are separated by a colon (:). You can, for example, use the strtok() function repeatedly to separate out each path component. To check if a command (such as ls) resides within a given directory, you can either open() that command (for reading) and then immediately close() it, or you can use the stat() function.

Online Help

Latest Announcements

03/04/2012
Assignment 2 is now available!
27/02/2012
Assignment 1 is now available!
25/02/2012
Please note that labs start in week 1

Back to top