Programming Assignment P1: C Programming Warm-up

Deadline:

See course calendar.

Educational Objectives:

This assignment is intended as a warm-up for the assignments that will come later, but it also intended to introduce you to a number of concepts and skills. You will make a set of specified modifications to a simple discrete-event simulation program. This program was a partial solution to one of the COP 4610 assignments another term, and may (no promise) be used as the bare-bones basis for your last progamming project this term. The main changes you will make will be replace the ad hoc linked list structures by uses of the circular linked list structure used in the Linux kernel, based on struct list_head. The other change will be to correct an error in one of the functions that handles command-line arguments. The main effort should be reading and understanding the existing code, and then working through any misunderstandings. You will also be expected to verify that your code compiles and works the same on both Linux and Solaris systems.

• Review the Unix command line interface, makefiles, and the C programming language.
• If you have only used C++ before, learn to "step down" to C. There are quite a few features in C that you will need to use in this course which are typically not learned in C++ courses. These incude the C libraries and macros.
• Learn list.h one of the data structures that is most widely used in the Linux kernel. This may be your only taste of real kernel programming this term, but it is probably the single most critical file to understand if you want to read the Linux kernel code. It is a tour de force in the use of C macros, as well as an example of what is arguably the single most useful linked list data structure ever invented, heavily used on OS kernels since long before Linux.
• Become familiar with the concept of discrete event simulation, as applied to some of the basic functions of an operating system. Simulation is an important technique in operating systems performance modeling, as well as other areas of research.
• Become aware of coding for source-code portability and security, and at least one of the C-language pitfalls that lead to the dreaded buffer-overflow vulnerability.
• Become familiar with multi-file programs, and linking of separately compiled object files, you have not done this before.
• Become familiar with the incremental development and debugging approach.
• Practice reading code.
• Practice checking out your code on more than one sytem, and turning in an assignment.
• Become familiar with the C-language API for command-line arguments, if you were not already.

Deliverables:

Tasks:

1. On one of the linprog systems, create a working directory, P1, and copy into it the file ~baker/opsys/assign/P1/P1.tgz.
2. Use tar -xzvpf P1.tgz to extract the necessary files.
3. Enter the shell command make. This should make two subdirectories, Linux and SunOS, each containing some symbolic links, and then compile the programs sim and testrand in the Linux subdirectory. In general, which directory the compilation is done in will depend on whether you are running on a Linux (linprog.cs.fsu.edu) or a Solaris (program.cs.fsu.edu) system). For example, on a Linux system, you may see the following:

   baker@linprog3.cs.fsu.edu: make
         make[1]: Entering directory `/home/faculty/baker/courses/cop4610.S15/assign/P1/test/Linux'
         make[1]: Leaving directory `/home/faculty/baker/courses/cop4610.S15/assign/P1/test/Linux'
         make[1]: Entering directory `/home/faculty/baker/courses/cop4610.S15/assign/P1/test/SunOS'
         make[1]: Leaving directory `/home/faculty/baker/courses/cop4610.S15/assign/P1/test/SunOS'
         make[1]: Entering directory `/home/faculty/baker/courses/cop4610.S15/assign/P1/test/Linux'
         gcc -Wall -Wextra -pedantic -DDEBUG   -c -o random.o random.c
         gcc -Wall -Wextra -pedantic -DDEBUG -o testrand testrand.c random.o -lm
         gcc -Wall -Wextra -pedantic -DDEBUG -o testargs testargs.c random.o -lm
         gcc -Wall -Wextra -pedantic -DDEBUG   -c -o simulator_old.o simulator_old.c
         gcc -Wall -Wextra -pedantic -DDEBUG   -c -o events_old.o events_old.c
         gcc -Wall -Wextra -pedantic -DDEBUG -o sim_old sim.c simulator_old.o events_old.o random.o -lm
         gcc -Wall -Wextra -pedantic -DDEBUG   -c -o simulator.o simulator.c
         gcc -Wall -Wextra -pedantic -DDEBUG   -c -o events.o events.c
         events.c: In function 'queue_dump':
         events.c:89: warning: ISO C forbids braced-groups within expressions
         events.c:89: warning: value computed is not used
         events.c:89: warning: ISO C forbids braced-groups within expressions
         events.c:89: warning: value computed is not used
         events.c: In function 'dispatch':
         events.c:103: warning: ISO C forbids braced-groups within expressions
         events.c:105: warning: ISO C forbids braced-groups within expressions
         gcc -Wall -Wextra -pedantic -DDEBUG -o sim sim.c simulator.o events.o random.o -lm
         make[1]: Leaving directory `/home/faculty/baker/courses/cop4610.S15/assign/P1/test/Linux'

4. Try to read and understand all the code in the directory P1 You should ask questions about any parts you don't understand, in the Blackboard Discussion Board forum for this assignment, well before the program is due. Also try to understand the associated makefile, but if you don't understand all of it right now, that is OK. You will have time to learn more about makefiles as the term goes on.
5. Modify the code of the files events.c and simulator.c to replace one of the ad hoc list structures with type struct list_head and the corresponding list_* functions and macros from list.h. When you have completed the changes, it should work exactly as it did before your changes.

   There are three list structures that you can/need to modify:

   • The field struct process *next_in_list in events.c,
     a circular singly linked list.
   • The field struct handler_pair * next in simulator.c,
     a null-terminated singly linked list.
   • The fields event_queue_link_t next and event_queue_link_t prev in simulator.c,
     a null-terminated doubly linked list.

   You will need to change all the lists to doubly linked circular lists, to fit the model of "list.h". You should be able to use macros and functions from "list.h", directly, for most of the operations, resulting in a net reduction in the code of the files you are modifying. The one place you will need to "roll your own" algorithm is in the function simulator_schedule, where a node is inserted into a list that is used as a priority queue, ordered by increasing event time, and ordered with equal event times by event kind.

   See how I already replaced one of the four original list structures, by comparing the files events.c against events_old.c. (I have also created a back-up copy of simulator.c, called simulator_old.c, but there are not yet any modifications.) Leave the "_old.c" files unchanged.

   Some important aspects to keep in mind:

   • Lists are linked through struct list_head objects, which normally are contained as a field of an object of another struct type, which we call the container type.
   • The links point bewteen the embedded struct list_head objects. The macro container_of() is used to get the address of the container object, if one knows: (1) the address of the struct list_head object; (2) the type of container struct type; (3) the name of the field corresponding to the struct list_head object.
   • You need to be careful about which macro parameters expect a pointer to a struct list_head, and which expect a pointer to the containing struct type.
   • Don't be confused by the term "list_head" in the type name. Each list has a true list header, which is of the same type as the nodes used to link elements of the list. The first real element is the successor of the list header, and the last real element is the predecessor of the list header. An empty list is a header node that points to itself.
   • The true header node can be an isolated struct list_head object, but it is often easier to make a object of the container type, whose embedded struct list_head serves as the true list header. In this way iterators that work on the container type can be applied to the list. That is what I did in events.c with the idle_process.

   The following diagram may be helpful in understanding the list structure and the macro container_of(), also known as list_entry(). The diagram is incomplete in not showing how the list is circular. The blue arrow corresponding to New->list.next might be directly equal to &P->list, or point to another node in a chain that eventually gets back to P->list. Similarly, the orange arrow corresponding to P->list->prev should eventually lead back to New->list.

   

   There is a little bit of explanation of Linux kernel lists on pages 99-101 of the text, but for more detailed explanation I'd recommend on the of the tutorials listed under References below.

   Some typical C programming errors to look out for:

   • Failure to initialize pointers, including list headers.
   • Ending calls to iterator macros (like for statements) with ";", which effectively iterates on the null statement.
   • Mixing up struct list_head pointers and pointers to container objects
   • Mixing up object and their addresses (confusion over when & and * are needed).
   • ... maybe some more examples here, as students report bugs ...
6. Modify the comments in the file(s) you changed to:
   • Include in the header comment your name, the course, your section, and the date of your changes.
   • Update the body comments to reflect the changes you have made.
7. Compile the modified code, using make. By default, it will make three programs: sim, sim_old, and testrand, in one of the two subdirectories Linux and SunOS (depending on the OS you are using). You can ignore testrand, except as an example of a unit test program. The program sim_oldis for comparison. The code you have modifed should only affect sim. Correct any defects that show up in compilation.
8. Test your code to make sure the program sim still works, by executing ./Linux/sim or ./SunOS/sim. Correct any defects that show up in your testing.
9. Now switch to the other operating system (to Solaris if you were working on Linux before, or vice versa) and repeat the testing as above, correcting any problems that show up. Then, if you make any changes, switch back to the other operating system and repeat, until you are sure your program works correctly on both systems.
10. Repeat the above steps until the only list structures left are those from list.h, or until you have reached the deadline for this assignment and must turn it in.
11. When you have completed the above, look at the program command_check_args(), in random.c. You will see comments to the effect that it has at least one serious coding error. It is one of the errors that I warn against in my notes on robust coding - see point 7. If you compile and run the program testargs (another example of a unit test program) you will see that this function has several defects and failure modes. If you comment out the call that causes a segmentation error fault, it will go on and fail again on the next call. Your assignment is to (at least) correct the error related to point 7 in the notes, and add a comment to the file header explaining what you changed and why. If you can correct some of the other defects, consider it a challenge.

    I appreciate that some of the vulnerabilities trace back to the parameters, but please don't change the header file! The submit script only copies random.c, simulator.c, and events.c, so if you rely on changes to any other files your submission will fail when we attempt to compile and test it.

Further Instructions:

• If you get error messages from the compiler for lines in which there are macro calls, you can use the "-E" option with the compiler to view a fully expanded version of the file, showing how the macro was expanded. For example:

  gcc -E events.c >& events.x
  

  You can then use a text editor to view the file events.x, and search for the context of the macro call that is causing the problem. (You will not see the macro name, unless the macro is undefined, since the macro call should have been replaced by the macro body.) If you have trouble finding the error in a long line of expanded macro text, there is a hack you can use to help locate it. Try pasting the expanded macro text in place of the macro call, with line breaks inserted, and then recompiling (without the "-E"). Once you have used the line number reported by the compiler for the error to identify the problem, you replace the pasted code by the original macro call.

• If you get other error messages, especially those complaining about "->" not being allowed, there is a good chance that you are mixing up addresses (pointers) with objects, or using "->" where "." is needed. Take a look at the declaration of the macro or function to see what kind of parameter is expected. You may need to add or remove a "&" from an argument, or replace "->" by ".".
• If you get the warning message "warning: Clock skew detected. Your build may be incomplete." from make, that is because the clocks on the two machines you are using are not synchronized closely enough. First, send e-mail to "system@cs.fsu.edu" telling which machines you are using and complaining that the clocks need synchronization. Then, to work around the problem, do "make clean" and then do "make" again.
• Don't forget to add comments to the code, giving at least your name, the course for which you did the work, and the date you made the changes, and delete any comments that no longer apply, because of the changes. Add any other comments that would be needed to bring the program up to the standard specified for this course.
• Do not leave in any commented-out code, or any output code that you added for debugging. The only changes in the code should be the minimal ones necessary to replace the original linked structures by uses of struct list head.
• The makefile calls the gcc compiler with options -Wall -Wextra -pedantic. This will cause the compiler to check your code more carefully for errors. The Linux kernel writers are more concerned about performance than portability, and have accepted that Linux will be dependent on the Gnu C compiler (gcc), so in the file ">list.h" they have used some extensions to the C language that are not portable. As a consequence if you compile with the "-ansi" option you will several error and warning messages, because of non-standard gcc-specific language extensions, including the typeof() construct. So, we compile with only the flags "-Wall -pedantic". With these flags, the code will compile but you will still see a few warning messages from extensions used in the macros, like in the example provided above.

  One warning message comes from the macro "container_of", which declares a local temporary constant inside braces. The use of such braces in side a for-loop specification is a gcc language extension. The second message comes from the calls to the "prefetch" macro inside the "loop_for_each_entry" macro, which result in expressions whose value is discarded. That is normally not a good thing, so you get a warning.

  I would normally require that your code compile with no warnings, since there is no practical way to achieve that using these Linux kernel macros I decided that for this one assignment it would be better to eliminate the "-ansi" and relax the "no warnings" rule. However, the two messages mentioned above, about braced-groups and unused values, are the only ones you should see.

• Remember not to modify any files other than the three deliverable files, for the reason explained above.

References:

• On-line explanations of the Linux list.h list structure macros, e.g.
  • https://isis.poly.edu/kulesh/stuff/src/klist/
  • http://kernelnewbies.org/FAQ/LinkedLists
• Course notes on C programming style and secure C programming, linked from the Supplemental Notes page
• Any good book on the C programming language, such as Kernighan & Ritchie The C Programming Language, Second Edition (ANSI C)

Submission:

First read the Study Guide section on Submitting Assignments, for general instructions.

1. Log into shell.cs.fsu.edu
2. cd to the directory P1 where you have your working solution, and make certain the versions of the files you want to submit are in that directory.
3. Execute the shell script submitP1.sh using the Bourne shell, by entering sh submitP1.sh or by setting the permission bits to executable and entering ./submitP1.sh. If it works correctly, you should see a successful completion message, and later receive two e-mail confirmations, including one with a copy of what you submitted. For this first assignment, the script also does a few sanity checks, to make sure you are executing it in the right directory. In particular, it will check that the deliverable files exist in the local directory, and that executable versions of sim existin in both the Linux and SunOS subdirectories.

Assessment:

Review the general Grading Criteria for Programming Assignments section of the Study Guide.

You can expect to have your score on this assignment reduced if your code does not adhere to the instructions above.

For a minumum passing score (70) you must replace at least one of the three existing list structures listed under step 4 above with the ones from list.h. Your score will be higher if you successfully replace more of the list structures with those from list.h and correct at least the one bug in command_check_args().