COMP 2355 Introduction to Systems Programming, Winter 2009

General Information

Prerequisites

The prerequisites for this class are a good understanding of imperative and object-oriented programming in Java. The prerequisites for this class include a good understanding of basic programming constructs, such as branches (if, switch), loops (for, while, do), exceptions (throw, catch), functions, objects, classes, packages, primitive types (int, float, boolean), arrays, arithmetic expressions and boolean operations as provided by COMP 1671, COMP 1672 and COMP 2370.
Computer organization is a parallel prerequisite; if possible students should register for both this course and COMP 2691. You must have a good understanding of basic data structures such as arrays, lists, sets, trees, graphs and hash-tables.

This is a class on systems programming with focus on the C programming language and UNIX APIs. There will be programming assignments designed to make you use various Debian GNU/Linux system APIs. Programming assignments involve writing code in C or C++. You cannot do these assignments easily on a Microsoft system. You can either install a free GNU/Linux system on your own machine(s) or use the Debian GNU/Linux lab in John Greene Hall.

Lecture Hours and Location

Mondays and Wednesdays, 10-12am in John Greene Hall 216.
In order to get a door code for the Computer Lab in John Greene Hall 216 please visit the labcode webpage. The code is updated on weekly basis.

Office Hours

Christian Grothoff - JGH 214

Monday, Wednesday 1pm-5pm and by appointment.

Taylor Phillips - CS Annex

Tuesday, Thursday 1pm-2:30pm and by appointment.

Textbooks and Syllabus

UNIX Systems Programming by David A. Curry, O'Reilly.
The C Programming Language by Brian Kernighan and Dennis Ritchie.
The C++ Programming Language by Bjarne Stroustrup.
The GNU C Library Manual.
"Version Control with Subversion", on-line book (no need to buy a copy). You must know how to use subversion as a developer (not as an administrator) in order to submit your assignments. Use this book as a reference if you encounter problems. Basic knowledge of chapters 1-3 should be sufficient.

Specific topics that will be covered:

• Datatypes in C
• The C preprocessor
• Linking and loading
• System V APIs
• Pointers
• C development and build systems
• Input-output in C
• Process management
• Higher order fun
• Terminal programming
• C++ namespaces, classes, templates, operators
• C++ STL
• Buffer overflows and memory corruption

Assignments and Grading

There will be individual assignments where you will need to implement various C or C++ programs. Some of the projects maybe declared to be team projects. All programming assignments must be turned in for grading by a certain deadline, late submissions will result in zero points.
Students are encouraged to discuss the materials, homework, and projects together. However, all programs must be done individually. Academic dishonesty includes, but is not limited to: plagiarism, cheating in exams, unauthorized collaboration and falsifying academic records. Violation of any of these may result in a grade penalty on assignments, an "F" in the course, dismissal from an academic unit, revocation of admission, suspension from the University as well as being roasted over a slow fire.
Generally, all assignments are due before class on the date specified with the assignment. Exceptions to this rule (allowing later submission) may be announced in class.
This class will not have a midterm or final exam. Instead, quizzes about the material of the previous lecture(s) will be given during class. You are expected to fully understand the material of each lecture before the next lecture. Missing a quiz without prior arrangements will result in getting zero points for the quiz. There will not be any make-up quizzes.

The different kinds of assignments are weighted as follows:

There are theoretically a total of 100 Pts possible Grades will be given as follows:

Software

You will need various applications for the class, all of which are freely available for various operating systems. Personally, I'm using Debian GNU/Linux unstable. If you have any problems installing the software, you can always use the department's HP lab which has all of the necessary software installed. Here is a list of the software programs that you will need (possibly incomplete):

gcc

The GNU Compiler Collection

(x)emacs

Editor

Subversion

Version control system

GNU autotools

C/C++ build system

Submission of Assignments

Each student will get access to a subversion repository. Assignments must be committed to that repository by the respective deadline. Students are encouraged to use the repository for version control while still working on the assignment. Only the last version commited before the deadline will be used for grading.
In order to access your subversion repository, you must first request an account by either putting your UNIX logon onto the paper I pass around in the first lecture or by contacting our system administrator (mention the course name and number). Once your account has been created, you should do an initial check out:

    $ svn checkout https://svn.cs.du.edu/courses/comp2355/w2009/$USER
    $ cd $USER
    

    $ mkdir p1
    $ svn add p1
    $ svn commit -m "comment"
    

Additional assignments for COMP 3354

Students who take the course at the 3000-level are expected to do some additional assignments. The following assignment is the suggestion, you are free to discuss an alternative project with the instructor.

Suggested Assignment for COMP 3354

Implement (and test) the build-in CMS pipeline stages BETWEEN, CHOP and COMBINE for GNU/Linux. You can implement ELASTIC for bonus points. Meet with the TA or your instructor to discuss how to address differences between the CMS and GNU/Linux environments.

Schedule

Note that existing assignments maybe updated at anytime. Please check the webpage frequently for updates. Feedback is welcome.

Class 1: Introduction (1/5/2009)

Material from the textbook

Version Control with Subversion, Chapters 1-3
The GNU C Library, Chapter 1.2

Lecture

Slides

Useful links

Subversion

Assignments

1. Hello World! Due: Class 3 (1 pt), Implement "Hello World" and submit the source code in the P1 directory. Test your submission with this script: P1/driver_p1.sh

Class 2: Datatypes and Control Flow in C (1/7/2009)

Material from the textbook

The C Programming Language, Chapters 2 and 3

Lecture

Slides, typedef, Operators

Class 3: C Preprocessor, Compiler, Linker, Loader and Debugger (1/12/2009)

Material from the textbook

The GNU C Library, Chapter 1.3; The C Programming Language, Chapters 4 and A12

Lecture

Slides

Assignment

For your "Hello World" implementation, submit the C code after pre-processing, the assembly code and the compiled but not yet linked object file.
Run your application in gdb, stopping it in main. What is stored in argv[0]? Change the value to some other string using gdb. What is the effect of that kind of change (on GNU/Linux in particular)? (Hint: play around with ps and top).
Use gdb to find the call to the operating system that ultimately results in the printing of the "Hello world!" message. Which assembly instruction is the final instruction executed before the message is printed? What does the call stack look like at that point?
Provide a text file with the commands entered into gdb and the respective outputs as proof. Submit your code and text in a directory called P2. Due: Class 5 (2 pts).

Class 4: Arrays (1/14/2009)

Material from the textbook

The GNU C Library, Chapter 4.1, 4.2, 5.1-5.5, 5.7 and A.2; The C Programming Language, Chapter 5 and 6 (except 5.4, 5.11, 5.12)

Lecture

Slides

Assignment

Create an array with 10 million 32-bit unsigned integers in memory. Then implement a sorting algorithm based on bucket sort to sort the array in linear time. Submit your code in a directory called P3. Due: Class 6 (5 pts).

Class 5: Fundamental System V APIs (1/21/2009)

Lecture

Slides

Useful links

varargs

Material from the textbook

The GNU C Library, Chapters 11-14 (except 12.6, 12.20, 12.21, 12.22, 13.10, 13.15, 13.16, 14.10); The C Programming Language; Chapter 7 and 8

Assignment

You are to implement a tool that will show for each process the amount of memory it is using. Scan the /proc directory to find all active processes. The name of the binary of each process is the file pointed to by the symbolic link in /proc/PID/exe. You can find information about the memory usage of each process in /proc/PID/maps. Note that segments belonging to the same file that are marked r-xp or r--p can be shared between processes. If the same map is shared between n processes only 1/n-th of its size should be considered to be used by each of the n processes.
Your output should list on seperate lines the binary names of all active processes, followed by a space followed by the thus computed space consumption in bytes. Submit your code in a directory called P4. Due: Class 7 (5 pts).

Class 6: Pointers (1/26/2009)

Material from the textbook

The C Programming Language; Chapter 5.4

Lecture

Slides

Assignment

What is the output of the following code snippet?

            long ** p;
            printf("%u %u %u %u\n", 
                   p - &p[1], 
                   (int) ((long)&p[1] - (long) p), 
                   *p - p[0], 
                   *p+1 - p[0]);
          

Justify your answer in detail, discussing all possibilities. Submit your answer as a textfile to subversion. Submit your textfile in a directory called P5. Due: Class 7 (2 pts).

Class 7: The GNU C Build System (1/28/2009)

Material from the textbook

Learning the GNU development tools, GNU autoconf, automake and libtool

Lecture

Slides

Assignment

Implement a shared library that provides a function int expr_compute(const char * expr, int * result) which takes a simple expression containing addition and subtraction operations over simple integers (for example, "1 + 2 - 3"). The function should store the result of the computation in *result and return -1. If the expression contains a syntactic error, the function should return the offset in the expression with the syntax error.
Use the GNU C build system to build the library as well as at least two binaries containing testcases. The binaries should not be installed by make install and instead should be compiled and run by make check. Running make install should install the library and its C header file in the appropriate locations. Submit your code in a directory called P6. Due: Class 9 (6 pts).

Class 8: Symbols and Attributes (2/2/2009)

Material from the textbook

Program Library HOWTO, GNU binutils (ld, nm, etc), The GNU C Library, Chapter 25; The C Programming Language, Chapters A10 and A11

Lecture

Slides

Class 9: Profiling and Optimizing C Code (2/4/2009)

Material from the textbook

The GNU C Library, Chapter 21

Lecture

Slides

Assignment

Implement a program that computes the exact number of prime numbers up to a given 35-bit number (which is passed in as the first argument to your code). You can assume that you have about 2 GB of memory. Make your implementation as fast as possible. All implementations will be compared and the fastest (correct) implementation will get 100 percent of the points, the second fastest 90 percent, and so on. Your submission must include a proper build system. Submit your code in a directory called P7. Due: Class 10 (4 pts).

Helpful links

How many primes are there?

Class 10: Function Pointers and Closures (2/9/2009)

Material from the textbook

The GNU C Library, Chapter 9; The C Programming Language, Chapters 5.11 and 5.12, Nested Functions in GNU C

Lecture

Slides

Assignment

Implement a version of the UNIX sort command, including support for the -b and -f and -r command-line options. You can use any function in the System V API. Use indent -nut SOURCE.c to format your code. All implementations will be compared and the shortest (in terms of number of characters of C source code) correct implementation will get full points, the second shortest 90 points, and so on. Note that actual performance of the sorting operation will not be considered. Incomplete implementations will be considered faulty and earn zero points. Your submission must include a proper build system. Submit your code in a directory called P8. Due: Class 12 (4 pts). Hint: You do not need to implement any sorting algorithm!

Class 11: Signals (2/11/2009)

Material from the textbook

The GNU C Library, Chapter 24

Lecture

Slides

Class 12: Process Management (2/16/2009)

Material from the textbook

The GNU C Library, Chapters 15, 23 and 26

Lecture

Slides

Assignment

Implement a program to start Java applications. Your program should take as its first argument the desired process name that should be shown by the UNIX top command. The other arguments should be the arguments passed to java. Provide a proper build system using the autotools and handle all possible errors. Fail gracefully if the java VM is not found in the current PATH. Submit your code in a directory called P9. Due: Class 13 (2 pts). Hint: Study the exec system call very carefully.

Class 13: Terminal Programming (2/18/2009)

Material from the textbook

The GNU C Library, Chapter 17 and 27

Lecture

Slides

Assignment

Implement a UNIX shell with support for process invocation (15 percent), pipes and redirection of stdin, stdout and stderr (20 percent), backgrounding of processes (15 percent), variables (10 percent), single and double quotation (10 percent), file-name expansion with star, tilde and question mark (10 percent), command-line editing (backspace, delete, arrow left and right, tab completion, 10 percent) and command history (10 percent).
In order to simplify your parsing of the input, you can assume that commands, arguments and the special tokens "|;&<>" are all always separated by spaces from each other. Variables and quotation should work just like in GNU bash.
You can either use the GNU readline library (suggested) or write your own low-level terminal driver (much harder). You should also read the man pages for glob, wordexp and fnmatch. You are allowed to use the code snippets from the GNU libc manual for a shell for this assignment. You still need to acknowledge in your code if you use external parts (and note where you got them from).
You are free to do this project in teams of two students (please submit requests for the creation of group accounts in subversion to the system administrator). Your submission must include a proper build system. Submit your code in a group directory USER1-USER2-shell where USER1 and USER2 are the members of your group. If you submit individually, use P10. Due: Class 16 (14 pts).

Class 14: Introduction to C++ (2/23/2009)

Material from the textbook

The C++ Programming Language, Part I and Chapter 14

Useful Links

C++ Exceptions FAQ

Lecture

Slides

Class 15: C++ classes (2/25/2009)

Material from the textbook

The C++ Programming Language, Chapters 10 and 12

Useful Links

C++ Destructor FAQ, Smart Pointers

Lecture

Slides

Class 16: C++ templates and C++ operator overloading (3/2/2009)

Lecture

Slides

Material from the textbook

The C++ Programming Language, Chapters 11 and 13

Assignment

Implement a matrix library with support for sparse and dense matrices. The API should support addition, subtraction, scalar multiplication and division and matrix multiplication. You should make intensive use of operator overloading ([], *, +, etc.) and inheritance (have a base class for the shared API between dense and sparse matrices). You are encouraged to use the STL (vector might be particularly useful). Your library should work with various number types including integers, floats and complex numbers (use templates). You are encouraged to add additional operations as needed.
Using the library (you do not have to write a build system to literally create a library, but you must have two or three generic classes), implement an application that performs Gaussian elimination. The main application should read input of the following format (all numbers being of type double for this particular application):

n
m11 m12 ... m1n
m21 m22 ... m2n
... ... ... ...
mn1 mn2 mn3 mnn
y1
y2
...
yn

Where the equation to solve is mx = y. The program should output the solution for x in the same format as the input of y. If the system has no solution, the output should be No solution.. If your program is started with the option -s you should internally use your sparse matrix representation (the input format will not change). Your submission must include a proper build system. Submit your code using a directory called P11. Due: Class 19 (10 pts).

Class 17: C++ Standard Template Library (3/4/2009)

Lecture

Slides

Material from the textbook

The C++ Programming Language, Part III

Class 18: Buffer Overflows and Memory Corruption (3/9/2009)

Lecture

Slides

Assignment

Find and fix all (potential) cases of buffer overflows or other forms of memory corruption in this piece of code. Due: Class 20 (5 pts).

Class 19: Concurrent Programming (3/11/2009)

Lecture

Slides

Class 20: Final (3/12/2009)

Grades

Grades will be e-mailed to the e-mail address given with the request for creating the subversion account. For how to interpret the e-mailed grades please ask in class or during office hours.