UTSA CS 3733 Operating Systems Assignment 1 Fall 2001

CS 3733 Operating Systems, Fall 2001 Assignment 1

Due Monday, September 17, 2001

Assignment 0 has 4 parts.

Introduction
Peer-to-peer communication often relies on a central database for keeping information to be shared. If you are looking for a (non-copyrighted) song to download from the internet, you might query a server that keeps track of where that song is available for download. This assignment explores a simple way of storing this information. You will write a very simple database for storing string keys (which you can think of as names of songs) and information corresponding to that key (which you can think of as specifying a machine on the network containing that song).

In this assignment you will be using pointers, allocating and freeing memory, and manipulating pieces of data of arbitrary size. Many OS system calls must perform similar operations and this exercise is a warmup to test your programming and debugging skills. The assignment has been designed to test your skill at preventing buffer overflows, unassigned pointers and memory leaks. The routines developed in this assignment may also be used in a later assignment in which data is moved between machines.

It is assumed that you are familiar with separate compilation and the use of make. If not, be sure to read the appropriate sections from Appendix A of PUP.

Create a directory called assign1 under your CS 3733 directory, for this assignment. You must keep the source code for this assignment at least until you have received your final grade for this course.

No source line should be longer than 80 characters and no program in this assignment should generate an output line longer than 80 characters. Do not add any options to lint in the makefile.

Part 0: Downloading the files
Make a part0 subdirectory of assign1 and copy all of the files from /usr/local/courses/cs3733/fall2001/assign1 into your part0 directory. You should have a makefile, an include file, and two source files. The file datalib.c describes the library functions that you will be generating for this assignment. It contains the function printdata and has stubs for each the the public (external linkage) files that you need to create. Do not modify printdata, the typedefs, NAMESIZE or the definition of data_start. The file datatest.c is a skeleton for a program you will use for testing the library routines. Modify datatest.c so that it outputs your name instead of mine. Run make lint on these files and make sure the only warnings generated are ones you understand and that can be ignored. Then compile the programs by running make. Save the output in running lint in a file called part0.lint and the output of datatest in a file called part0.out. Look at the data structures and data types defined in datalib.c and make sure you understand what they are supposed to do.

Part 1: The First routine
Create a subdirectory of your assign1 directory called part1. Copy all of your files from part0 into this directory. Do not modify any of the files in the part0 directory. In part1, write the routine addentry as described in the file datalib.c. Use make lint and remove any errors or warnings that should not be there. Save the output of make lint in a file called part1.lint. Compile with make and run the program. Save your output in a file called part1.out in this directory. Once you have this working, do not modify any of the files in this directory.

Part 2: Finish writing the program and test it.
Make a part2 directory under assign1 and copy all of the files from the part1 directory into part2. Do not modify the files in the part1 directory unless you have found that there are bugs in your addentry function there. In the part2 write the rest of the routines in datalib.c and modify datatest.c so that all of the routines are tested as completely as possible. Save the results of make lint in a file called part2.lint. Run datatest and save the result in a file called part2.out in this directory. Write a commentary about what tests are run in datatest and put this in a text file called testing.txt.

Part 3: Run my test suite.
Make a part3 directory under assign1 and copy only your datalib.o file from your part2 directory. Copy the files from /usr/local/courses/cs3733/fall2001/assign1/testing into your part3 directory and execute make. This will produce an executable called datatester.

Run this program and put the output in part3.out. You can do this with
datatester >& part3.out

Look at the output generated. If there are any warnings, you should try to eliminate them by fixing your datalib.c file.

Remember ...

This assignment should be done without collaboration. You may ask others for help with understanding the general idea of the assignment, but you must write all of the code yourself. Do not look at the source code generated by other students and do not show your source code to other students. Come to me for help if you need it. Send me email if you cannot find me in my office. Do not wait until the last minute to start this assignment. Little help will be available if you come to me right before it is due and you have made little progress.

Advice

Some time in your life you will delete a file that you didn't want to delete. This typically happens after you have just gotten something to work. Every once in a while, tar up your assign1 directory and store the tar file in a safe place. Use a different filename each time you do this. A simple way to do this is with the saveit script in /usr/local/courses/cs3733/fall2001. Copy this script into your assign1 directory and execute it every once in a while. You might want to modify the destination directory and the file name.

Think About

Think about the following when doing this assignment. You may discuss these items with others in the class.

You must use the data structures defined in the typedefs in datalib.
The database will consist of a linked list for linkentry_t items with the first entry pointed to by data_start.
You must not modify the printdata function in any of the parts of this assignment. This function must work with your implementation of the database.
The get_data_start program is for grading purposes only and should remain commented out until Part 3.
When an error occurs, the library routines must clean up any unused memory. The library routines (except for printdata) do not do any I/O. The main program is responsible for informing the user of errors.
When you create a new entry you must allocate space for the entry and also the key. Copy the key string into newly allocated space.
The calling program should only be allowed to change items in the database by calling the functions in datalib.
The only public functions in datalib are the ones you got from Part 0, but you may add any functions with internal linkage that you need.
When you delete an entry, you must free both the entry and the key.
You must make sure your program does not have memory leaks.
When your library routines return with an error, do not assume that errno has been set.
The key and the hostname are treated differently. The key is of arbitrary length but the hostname is limited in size.

You must be able to answer the following questions. You may get any help you need to find the answers.

What would happen if after a successful add_entry call, the calling program modified the string it passed as a key?
What would happen if after a successful add_entry call, the calling program modified the string it passed as a host name?
Suppose add_entry just used the pointer to the key rather than creating new space and copying the key. How could the calling program corrupt the database?
How did you test that your program does not have any memory leaks?
getdata and findentry are passed buffers in which to store the strings to be returned. These strings are copied into buffers supplied to the calling program. An alternative would be to return pointers to these strings inside the database. Give at least two reasons for not doing it this other way.
findentry handles length errors for host and key differently. If the host does not fit, it is considered a fatal error (-1 is returned) while if the key dies not fit, part of the key is copied and no error is generated. Why is it done this way?
The file datalib.h contains prototypes of the functions in datalib.c but the typedefs used in datalib.c are not in this file. Why is that?

Handing in the program
Print out the cover page and fill in the page numbers of the various parts of the assignment. Include all of the documents indicated on the cover page. Use a single staple in the upper left corner to attached to cover page to your output. Hand everything in at the begining of class on the due date.