Introduction to Operating Systems

Project 4: File System Implementation (Representing Files)

CS 3113, Fall 2018, Project 4, Due 11/29/2018 @11:45pm

You now have experience at mapping directory structures onto fixed-sized blocks of bytes on a disk. For this project, we will expand your implementation to allow for the creation of, writing to reading from and deletion of files.

The OUFS data structure is identical to that of project 3. However, you will make use of some of the new components. Specifically, you will:

1. Create files in the file system
2. Read data from existing files
3. Write data to files
4. Remove files
5. Create hard links to existing files

Remember to read this specification in full. Please post questions in the Project 4 Talk discussion board. For private questions, email cs3113@googlegroups.com.

---

Grading Criteria

Overall score

Task	Percent
Makefile: provides ‘all’ and ‘clean’	10%
Documentation: Proper functional-level and inline documentation. README is thorough and complete.	40%
Correctness: This will be assessed by giving your code a range of inputs and matching the expected output.	50%
Total	100%

This project is worth a total of 250 points. In order to receive all points, you must turn in a correct and correctly documented solution by the deadline. Solutions turned in up to 24 hours late will receive a late penalty.

Your final correctness score will be as follows:

correctness = max(correctness at deadline, correctness within 24 hours - 25 points)

Bonus

If you pass our ztouch test by Thursday, November 15th @ 11:45pm (two weeks early), then you can earn up to 50 bonus points.

---

Check-list

Below, is an implementation check-list for your convenience.

Supporting Materials

• Makefile
• README

Application Programs from Project 3:

• zformat: format the virtual disk
• zinspect: examine individual blocks on the virtual disk
• zfilez: list the contents of a specified directory or list the specified file
• zmkdir: create a specified directory
• zrmdir: remove a specified directory

New Application Programs:

• ztouch: create a file if it does not already exist
• zcreate: open a specified file for writing and write any bytes received from STDIN to the file (terminating when the STDIN end-of-file has been received)
• zappend: open a specified file for appending and write any bytes received from STDIN to the file (terminating when the STDIN end-of-file has been received)
• zmore: copy the contents of a file to STDOUT
• zremove: remove a specified file from its parent directory. This acts like the Linux rm command
• zlink: link an existing file to a new parent directory and local file name. This acts like the Linux ln command

API: The design of your API is up to you. We gave our API prototypes in project 3 (you may use them or you may not). But, your API will have some of the following functionality:

• Open a specified file
• Close a specified file
• Write bytes to a file
• Read bytes from a file
• Remove a file
• Link a file

Submission

Your code, executables, makefile and README must all be on your instance in the /projects/4/ directory. Please note that this location is NOT under your home directory. You must also submit your code as project4.tar.gz in Canvas.

---

OU File System Data Structure

The relevant pats of the file system data structure are as follows. Note that you must not make any changes to this structure.

oufs.h (partial):

/**********************************************************************/
// Data block: storage for file contents (project 4!)
typedef struct data_block_s
{
  unsigned char data[BLOCK_SIZE];
} DATA_BLOCK;


/**********************************************************************/
// Inode Types
#define IT_NONE 'N'
#define IT_DIRECTORY 'D'
#define IT_FILE 'F'

// Single inode
typedef struct inode_s
{
  // IT_NONE, IT_DIRECTORY, IT_FILE
  char type;

  // Number of directories references to this inode
  unsigned char n_references;

  // Contents.  UNALLOCATED_BLOCK means that this entry is not used
  BLOCK_REFERENCE data[BLOCKS_PER_INODE];

  // File: size in bytes; Directory: number of directory entries (including . and ..)
  unsigned int size;
} INODE;


/**********************************************************************/
// Representing files (project 4!)

typedef struct oufile_s
{
  INODE_REFERENCE inode_reference;
  char mode;
  int offset;
} OUFILE;

Data Structure Notes

• The DATA_BLOCK structure is very useful for capturing the bytes that are contained within a file.
• Inodes:
  • Inodes that represent files must indicate the type IT_FILE - n_references for an allocated inode will be 1 on creation, but can grow to be more with linking
  • A file may use up to BLOCKS_PER_INODE blocks to store its data. Note that a file may not be allocated a data block unless there is at least one byte to store in the block.
  • size represents the file size in bytes
• OUFILE behaves like a combination of the FILE structure in stdio and the kernel open file table:
  • Stores the inode of the open file
  • Stores the mode that the file was opened as (“r”, “w”, or “a” only)
  • Tracks the current byte offset (the next byte to read or write in the file stream)
  • Note that oufs_fopen() is the only place in your project to use malloc(). All other data structures should be allocated on the stack

---

Executables and API

Although we describe the executables and the API together, your executable programs will generally be fairly short (only a main() function).

ztouch

Shell command:

./ztouch <name>

Behavior:

• It is an error if name is not specified
• It is an error if the parent of the specified file does not exist
• It is an error if the specified file is actually a directory
• If the specified file does not exist, then it is created with zero length (i.e., no data blocks are allocated to the file)
• If the file already exists, then it is unchanged and there is no error

zcreate / zappend

Shell commands:

./zcreate <name>
./zappend <name>

Behavior:

• It is an error if a file is not specified
• It is an error if the parent does not exist
• It is an error if a directory is specified
• zcreate opens the specified file for writing. If the file already exists, then, as part of opening process, it is truncated to length zero (with no data blocks allocated to the file)
• zappend opens the specified file for appending
• Both accept inputs from STDIN. These bytes are written to the specified OUFS file. This process is complete when no more space is left to store new bytes or the STDIN end-of-file is reached

zmore

Shell command:

./zmore <name>

Behavior:

• It is an error if the file does not exist
• It is an error if a directory is specified
• Opens the name file; reads the bytes, writing them to STDOUT; when the end of the file is reached, it closes the OUFS file

zremove

Shell command:

./zremove <name>

Behavior:

• It is an error if the file does not exist
• It is an error if a directory is specified
• Removes the entry from the parent’s directory block and decrements the n_references value in the child’s inode
• If n_references is then zero, then the inode and all associated data blocks are deallocated (their bits are set to zero in the allocation tables)

zlink

Shell command:

./zlink <existing> <new_name>

Behavior:

• It is an error if existing does not exist
• It is an error if existing is not a file
• It is an error if new_name exists (as either a file or a directory)
• It is an error if the parent of new_name does not exist
• If no errors, then adds a directory entry to the parent of new_name that references the already existing existing inode. The child’s inode n_references variable is incremented
  • Note: it is an error if there is no space for the new directory entry in the parent of new_name

---

API notes

oufs_fopen()

OUFILE* oufs_fopen(char *cwd, char *path, char *mode);

• cwd is a string containing the current working directory. It is safe to assume that this will always have a / at the beginning of the string.
• path is a string containing either an absolute or relative path to a file. If the latter, then cwd is prepended
• mode is one of:
  • “r’: open for reading; offset is set to zero
  • “w”: open for writing: offset is set to zero. If data blocks were already assigned to an existing file, then they are immediately deallocated
  • “a”: open for appending: offset is set to the size of the file
• return is either a populated OUFILE structure (persistently allocated) or NULL if an error.

oufs_fwrite()

int oufs_fwrite(OUFILE *fp, unsigned char * buf, int len);

Behaves like the POSIX fwrite():

• Adds len bytes in the buffer to the file specified in fp
• Returns the number of bytes written
• Allocates new data blocks, as necessary
• Stops adding bytes when the last byte in the last available data block is written
• Writes to a full file result in zero being returned

oufs_fread()

int oufs_fread(OUFILE *fp, unsigned char * buf, int len);

Behaves like the POSIX fread():

• Reads len bytes from the file specified by fp starting from the current file offset into the specified buffer (buf)
• Returns the number of bytes read
• If the offset is equal to the length of the file, then returns zero

Other notes:

• Only the necessary data blocks are allocated to a file inode (i.e., they must store at least one byte of data). A file of length zero has zero blocks allocated to it; a file of length 1, 15 or 256 has one block allocated to it; a file of length 257, 300 or 512 has two blocks allocated to it
• All errors and debugging output must be printed to STDERR
• We will not have a case in which a file open for writing or appending in which the offset and the size are different
• project4_tests.tar.gz

---

Example Interaction

Below is an example interaction.

$ ./zformat
$ ./zfilez
./
../
$ echo foo bar baz | ./zappend a.txt
$ ./zfilez
./
../
a.txt
$ ./zmore a.txt
foo bar baz
$ ./zinspect -inode 1
Inode: 1
Type: F
Block 0: 10
Block 1: 65535
Block 2: 65535
Block 3: 65535
Block 4: 65535
Block 5: 65535
Block 6: 65535
Block 7: 65535
Block 8: 65535
Block 9: 65535
Block 10: 65535
Block 11: 65535
Block 12: 65535
Block 13: 65535
Block 14: 65535
Size: 12
$ ./zcreate zformat.c < zformat.c
$ ./zmore a.txt
foo bar baz
$ ./zfilez
./
../
a.txt
zformat.c
$ ./zmore zformat.c
#include <stdio.h>
#include "oufs_lib.h"

int main(int argc, char** argv) {
  // Fetch the key environment vars
  char cwd[MAX_PATH_LENGTH];
  char disk_name[MAX_PATH_LENGTH];
  oufs_get_environment(cwd, disk_name);

  oufs_format_disk(disk_name);

  return(0);
}
$ ./zinspect -inode 2
Inode: 2
Type: F
Block 0: 11
Block 1: 12
Block 2: 65535
Block 3: 65535
Block 4: 65535
Block 5: 65535
Block 6: 65535
Block 7: 65535
Block 8: 65535
Block 9: 65535
Block 10: 65535
Block 11: 65535
Block 12: 65535
Block 13: 65535
Block 14: 65535
Size: 264
$ ./zremove a.txt
$ ./zfilez
./
../
zformat.c
$ ./zinspect -dblock 9
Directory at block 9:
Entry 0: name=".", inode=0
Entry 1: name="..", inode=0
Entry 3: name="zformat.c", inode=2
$ ./zinspect -master
Inode table:
05
00
00
00
00
00
00
Block table:
ff
1b
00
00
00
00
00
00
00
00
00
00
00
00
00
00

Example Interaction 2

$ ./zformat
$ ./zappend zformat.c < zformat.c
$ ./zfilez
./
../
zformat.c
$ ./zmkdir project4
$ ./zmkdir project4/src
$ ./zfilez project4/src
./
../
$ ./zinspect -master
Inode table:
0f
00
00
00
00
00
00
Block table:
ff
3f
00
00
00
00
00
00
00
00
00
00
00
00
00
00
$ ./zlink foo project4/src/bar
Source not found
$ ./zlink zformat.c project4/src/zformat2.c
$ ./zfilez project4/src
./
../
zformat2.c
$ ./zfilez project4/src/zformat2.c
zformat2.c
$ ./zinspect -master
Inode table:
0f
00
00
00
00
00
00
Block table:
ff
3f
00
00
00
00
00
00
00
00
00
00
00
00
00
00
$ ./zmore project4/src
Not a file.
$ ./zmore project4/src/zformat2.c
#include <stdio.h>
#include "oufs_lib.h"

int main(int argc, char** argv) {
  // Fetch the key environment vars
  char cwd[MAX_PATH_LENGTH];
  char disk_name[MAX_PATH_LENGTH];
  oufs_get_environment(cwd, disk_name);

  oufs_format_disk(disk_name);

  return(0);
}
$ ./zremove zformat.c
$ ./zfilez
./
../
project4/
$ ./zinspect -master
Inode table:
0f
00
00
00
00
00
00
Block table:
ff
3f
00
00
00
00
00
00
00
00
00
00
00
00
00
00
$ ./zcat project4/src/zformat2.c
bash: ./zcat: No such file or directory
$ ./zmore project4/src/zformat2.c
#include <stdio.h>
#include "oufs_lib.h"

int main(int argc, char** argv) {
  // Fetch the key environment vars
  char cwd[MAX_PATH_LENGTH];
  char disk_name[MAX_PATH_LENGTH];
  oufs_get_environment(cwd, disk_name);

  oufs_format_disk(disk_name);

  return(0);
}
$ ./zremove project4/src/zformat2.c
$ ./zinspect -master
Inode table:
0d
00
00
00
00
00
00
Block table:
ff
33
00
00
00
00
00
00
00
00
00
00
00
00
00
00

Hints

• Do not cache disk blocks in memory. All system calls should complete all of their operations on the virtual disk before returning
• Add debugging code. We used a DEBUG macro to indicate whether we were in debugging mode or not. If set to 1, then many fprintf()s to STDERR are called to show what is happening internally. By making this a macro, it is easy to turn it off at compile time.
• Implement and test incrementally. Get opening and closing working first before working on file contents.

Addenda

2018-11-04

• The zcat command has been changed to zmore (zcat is an existing Linux program)
• Added one more interaction example

2018-11-06

• Added an extended inode option to zinspect (-inodee). Code: zinspect.c. This has also been updated in project3_parts.tar.gz. Make sure you install and compile this new version on your instance

2018-11-07

• Available bonus points increased to 50.

2018-11-13

• Fixed the link to for the project 4 tests project4_tests.tar.gz.
• Goodies from project 3: oufs_more_support.c

2018-11-15

• Added more project 3 tests to project3_parts.tar.gz project3_tests.tar.gz
• The bonus deadline has been extended to Friday, November 16th @11:45pm.

• oufs_fclose(): The job of the STDIO fclose() function is to clean up the resources that have been allocated to the open file (including the open file table) and to push cached data out to the disk. Because OUFS does not cache any data (any “system call” leaves the vdisk in a completely consistent state), oufs_fclose() is left to only clean up the OUFS data structure (i.e., it needs to free the memory).

• oufs_fopen(): return is either a populated OUFILE structure (persistently allocated) or NULL if an error.

2018-11-22

• Added data structure cartoon: project4-example.pdf

2018-11-27

• I have seen a couple of implementations where string operations are being used to manipulate the contents of the files in our file system (e.g., using strcat() to copy data into a data block during an oufs_fwrite()). This is problematic in that the string operators are designed for strings only, and a byte value of zero has a special meaning with strings (it is the string terminator). Instead, you should be working at a lower level: copying the bytes one at a time directly, or using memcpy(). And, yes, we will be testing with binary data.

• The echo Linux program appends a newline onto the end of the thing that it is echoing. This newline should be preserved when you are zappend’ing or zcreat’ing (i.e., you don’t have to do anything special with this case).

2018-11-28

• Refreshing a point made in project 3: command line file names can be longer than what will fit in the directory block. These should be truncated as they are stored in the directory block.

---

Back to Project List