Programming Project #4

CMPS 111, Fall 2008

Assigned: Thurs Nov 20
Due: Fri Dec 5th, at 11:59 PM

Remember: your project must be turned in online.

Purpose

The main goal for this project is to learn about the UNIX file system and implement signatures for data blocks of files in MINIX so that we can verify their integrity when reading them back from disk. You must implement:

A 4 byte signature for every block of a file. Blocks are 4KB. (A file with n 4KB blocks would have up to n signatures, but we will only create signatures for the first 1024 blocks (4MB) of the file.)
These signatures will be contained in a signature block stored on disk. A signature block is a single data block that contains many 4 byte signatures. The signatures are indexed 1:1 with each 4KB block of the file. i.e. signature[0] on the signature block corresponds to the first 4KB of the file. signature[1] on the signature block corresponds to the second 4KB of the file, this follows through the first 1024 blocks of the file. (1024 * 4KB = 4MB)
Modify MINIX so that the unused section (previously unused/reserved for triple indirect block pointer) of the inode is used to implement our signatures: it should act like a direct block pointer and point to the signature block. It should look something like this. Our signature block should be allocated as a data block, not an indirect block.
Modify the create/write function to include allocating the signature block, computing the signature, and storing it.
Modify the read function to compute the signature of a data block and compare it with the stored signature before returning it to the user; and return error on mismatch.
Signatures will be implemented using the sticky bit: if the sticky bit for the file is turned on, use signatures, else do not.

As with the previous project, you will experiment with operating system kernels, and to do work in such a way that may very well crash the (simulated) computer. You'll get experience with modifying a kernel, and may end up with an OS that doesn't work, so you'll learn how to manage multiple kernels, at least one of which works.

You should also read over the general project information page before you start this project. In them, you will find information about MINIX 3 as well as general guidelines and hints for projects in this class.

Details

The goal of this assignment is to give you additional experience in modifying MINIX 3 and to gain some familiarity with file systems, system calls, inodes, and integrity checking. As with earlier programs, you won't have to write too much code, but it'll be critical to understand where the code goes. Obviously, most (if not all) of your code will go into the fs server in MINIX, so that's a good place to start looking. You should read the handout (from section 5.6.4 and 5.7.4 in "The MINIX BOOK") which contains information about MINIX inodes and the file buffer cache, reading/writing files, including writing dirty blocks. The handout is in Professor Long's box outside his office if you didnt get one in class. Keep in mind that your MINIX is Version 3, which uses the same inodes as Version 2, so you will use the code for the V2 inodes. You will have dirty inodes sometimes, if you allocate the signature block: inodes also have a dirty bit flag. Inodes are described in servers/fs/inode.h.

New blocks are allocated in servers/fs/write.c. The default file system block size in MINIX is 4KB. The actual reading and writing of file blocks happens in servers/fs/read.c in rw_chunk(), that is where you should probably start. The inode will be modified so that the last entry (unused/triple indirect block) will now point to the signature block. The signature block is simply a data block which contains up to 1024 4byte signatures. See the slides from Nov 18, page 53 for the typical inode structure.

The signature you will compute is just a simple 4 byte XOR, starting with the first 4 bytes, XORing with each successive 4 bytes through the end of the block. If a file has 5 blocks, they will each have a signature. This is to verify the integrity of each data block you read back. The signature code should be something simple like this:

for each block of file:
signature = compute_signature(buf_ptr_to_this_block)
(Note that block_size is an available parameter, as used in rw_chunk.)

compute_signature(block_ptr):
int signature = 0
int buf[]
*buf = block_ptr
for i=0 to 1024:
signature = signature XOR b[i]
return signature

Enabling signatures for a file should be done by setting the sticky bit (01000 in octal). In order to enable this, you'll need to modify the ALL_MODES constant in minix/const.h to be 0007777. Once this has been done (and the kernel recompiled), you can use chmod to set the sticky bit and enable signatures for a file. To make things easier, you should only change the sticky bit on a file after it has been created if it has zero bytes. (This will prevent you from having to read in all of the previously existing data blocks, compute signatures, and write them.)

Some definitions:
Signature block: a single disk block, composed of many 4 byte signatures, each of which represents 4k of the file.

Some SIZES:
1 signature = 4 bytes.
1 signature block = 1024 signatures * 4 bytes each = 4KB

You need to zero out all bits in the signature block when initially allocated so that it is empty, then put your data in there. This is to preserve the XOR property. So, when you first create a file with signatures, you need to write signatures for possibly all blocks in the file, even the holes, therefore all of the signatures should all be set to zero initially.

Here are the procedures you need to implement for read and write:
READS:
1. Get the data block as normal
2. Check the sticky bit; if signature needed: read in the signature block and extract correct signature.

3. Compute the signature from the data block

4. Compare your two signatures, and return FAIL if mismatch (return a -1 and set errno)

WRITES:
1. Given a data block, check the sticky bit; compute the signature if needed
2. Read in the signature block so you can update it, or if none exist: allocate it, and set the dirty bit in the inode if needed.
3. Insert the signature into the correct place in the signature block, and set the signature block's dirty bit

Delete a file:
We must check if the sticky bit is set, if so, follow the signature block pointer in the inode to locate and free the signature block.

Updating a file:
Is the same procedure as WRITE: update the signatures for only the blocks you write.

TESTING:
You need to consider a testing strategy to verify your signatures work. One way to do this is:
1. Create an empty file
2. Turn the sticky bit on. (chmod +t)
3. Write some data in the file, save it. It should get updated and create signatures when you write it to disk this time since the sticky bit is turned on.
4. Turn the sticky bit off. (chmod -t)
5. Change some data in your file, save it
6. Turn the sticky bit on. (chmod +t)
7. Open your file to read: you should get an error message since new data was written and the signature was not updated, therefore old signatures should not match.

Deliverables

You must hand in a compressed tar file of your project directory, including your design document. You must do a "make clean" before creating the tar file. In addition, you should include a README file to explain anything unusual to the teaching assistant. Your code and other associated files must be included with the Makefile and a README; the TA will copy them to his MINIX installation and compile and run them there. Do not submit object files, assembler files, or executables. Every file in the tar file that could be generated automatically by the compiler or assembler will result in a 5 point deduction from your programming assignment grade.

Your design document should be called design.txt (if plain ASCII text, with a maximum line length of 75 characters) or design.pdf (if in Adobe PDF), and should reside in the project directory with the rest of your code. Formats other than plain text or PDF are not acceptable; please convert other formats (MS Word, LaTeX, HTML, etc.) to PDF. Your design document should describe the design of your assignment in enough detail that a knowledgeable programmer could duplicate your work. This includes descriptions of the data structures you use, all non-trivial algorithms and formulas, and a description of each function including its purpose, inputs, outputs, and assumptions it makes about the inputs or outputs. A sample design document is available on the course web page. By now should be able to write a suitable testing section about how you tested your code, some specfic cases you tested, and their expected output/behavior observed. You only need to provide 2 or more simple examples, enough to show that you thought about a way to verify some of your code and checked it. This should also help you with your design, as it requires you to think of normal and edge cases to check.

Hints

START EARLY! You should start with your design, and check it over with the course staff.
Experiment! You're running in an emulated system you can't crash the whole computer (and if you can, let us know...).
You may want to edit your code outside of MINIX (using your favorite text editor) and copy it into MINIX to compile and run it. This has several advantages:
- Crashes in MINIX don't harm your source code (by not writing changes to disk, perhaps).
- Most OSes have better editors than what's available in MINIX.
START EARLY!
Look over the operating system code before writing your design document (not to mention your code!). Leverage existing code as much as possible, and modify as little as possible.
For this assignment, you should write fewer than 200 lines of kernel code.
rw_chunk in fs/read.c is the code that actually reads (or writes) data in a file.
Did we mention that you should START EARLY!

We assume that you are already familiar with makefiles and debugging techniques from earlier classes such as CMPS 101 or from the sections held the first week of class. If not, this will be a considerably more difficult project because you will have to learn to use these tools as well.

This project doesn't require a lot of coding (typically fewer than 200 lines of code), but does require that you understand how to use MINIX and how to use basic system calls. You're encouraged to go to the class discussion section or talk with the course staff during office hours to get help if you need it.

You should do your design first, before writing your code. To do this, experiment with the existing shell template (if you like), inserting debugging print statements if it'll help. It may be more "fun" to just start coding without a design, but it'll also result in spending more time than you need to on the project.

IMPORTANT: As with all of the projects this quarter, the key to success is starting early. You can always take a break if you finish early, but it's impossible to complete a 20 hour project in the remaining 12 hours before it's due...

Project groups

You may do this project with a project partner of your choice. However, you can't switch partners if you already had a partner for Project #2. If you choose to work with a partner (and we encourage it), you both receive the same grade for the project. One of you should turn in a single file called partner.txt with the name and CATS account of your partner. The other partner should turn in files as above. Please make sure that both partners' names and accounts appear on all project files.

Last updated 25 Nov 2008 by Darrell Long or perhaps by Jeff LeFevre