CS 3113 Fall 18

Logo

This is the web page for Operation Systems at the University of Oklahoma.

View the Project on GitHub oudalab/cs3113fa18

Introduction to Operating Systems

Project 3: File System Implementation (Directory Structures)

CS 3113, Fall 2018, Project 3, Due 11/08/2018 @11:45pm

Hard disks organize data into fixed-sized blocks. When one wants to fetch a particular byte, the entire block in which that byte lives must be fetched. Likewise, when a single byte must be changed, the entire block is first read into memory, the byte is changed and then the entire block is written back to the disk.

However, as application-level programmers, we prefer to think in terms of the file system abstraction: a file is a sequence of bytes of some arbitrary length. It is convenient to program with this abstraction in mind: we would like to be able to read a subsequence of the bytes from a file or write a new subsequence of bytes (either overwriting existing bytes in the file, or appending onto the file itself). During these processes, we prefer not to think in terms of which blocks on the hard disk that are bytes are coming from or going to. In addition, the file system abstraction also provides us with a convenient and logical way of finding files. Specifically, we use directories and subdirectories, along with specific names within a directory that map to specific files.

For projects 3 and 4, you will implement a miniature file system, OUFS, that makes the connection between disk blocks and the file system abstraction. We will use a real file on our Linux systems as a model of the disk. This virtual disk will be accessed one block at a time (it will be opened in r/w mode and we will use lseek() to move between the blocks).

We provide the virtual disk implementation, as well as the file system data structure and a few other components. Your job in project 3 is to implement a hierarchical directory structure. In project 4, you will add files (with content!) to the file system. Specifically, as part of project 3, you will:

  1. Format the virtual disk with an initial file system. This initial file system will contain a root directory with “.” and “..” already initialized.
  2. Provide an API of “system calls” (we won’t actually be doing traps). These include functionality such as reading/writing inodes, creating/deleting directories and listing the contents of a directory.
  3. Provide a set of shell-executable programs that allow a user manipulate and view your virtual file system. We will be executing your programs from the bash shell directly (not your project2 shell). [Don’t worry, we will come back to it in project 4.]
  4. Provide a set of helper functions that make your API easier to implement.

Remember to read this specification in full. Please post questions in the Project 3 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 disk formatting test by Thursday, November 1st @ 11:45pm (one week early), then you can earn up to 25 bonus points.

Checklist

Below, is an implementation checklist for your convenience.

Supporting Materials

Application Programs:

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

Supporting functions: Again, these are up to you. Here are what some of ours do:

Submission

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

Virtual Disk API

The header file for the virtual disk is shown below. Both it and the C implementation are provided (link below). This API allows one to open/close a file to be used as a virtual disk. The disk is separated into 128 blocks of 256 bytes each.

Once the virtual disk is opened, there are two operations that can be performed: read a specific block from the disk and write data to a specific block on the disk. Note that these read and write operations are always done in terms of the block size (256 bytes). Blocks are addressed 0 … N_BLOCKS_IN_DISK-1 (127).

#ifndef VDISK_H

#include <sys/types.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <stdio.h>

typedef unsigned short BLOCK_REFERENCE;

// Size of block in bytes
#define BLOCK_SIZE 256

// Total number of blocks on the virtual disk
#define N_BLOCKS_IN_DISK 128

int vdisk_disk_open(char *virtual_disk_name);
int vdisk_disk_close();
int vdisk_read_block(BLOCK_REFERENCE block_ref, void *block);
int vdisk_write_block(BLOCK_REFERENCE block_ref, void *block);

#endif

File System Structure

Our virtual disk contains a total of 128 blocks. Most blocks are available for storage of file or directory data. However, several blocks are reserved for special functions: there is one master block, a set of blocks for storing inodes and the remaining blocks are used to store information about files and directories

Block 0: master block.

This block contains both an inode allocation table and a block allocation table.

Blocks 1 … N_INODE_BLOCKS: Inode storage.

Inodes represent an entity on the disk (either a file or a directory). There are N_INODES represented in the virtual disk, indexed using 0 … N_INODES-1.

In OUFS, an inode includes:

A single inode block contains an array of inode structures (INODES_PER_BLOCK of them) .

Blocks N_INODE_BLOCKS+1 … N_BLOCKS-1: data storage

Data are stored in these blocks in two ways:

OU File System Data Structure

The full file system data structure is as follows. Note that you must not make any changes to this structure.

oufs.h:

/*******
 * Low-level file system definitions
 *
 * DO NOT CHANGE THIS DATA STRUCTURE
 *
 * CS 3113
 *
 * 
 */

// Only evaluate these definitions once, even if included multiple times
#ifndef FILE_STRUCTS_H
#define FILE_STRUCTS_H

#include <string.h>
#include <limits.h>
#include "vdisk.h"

// Implementation of min operator
#define MIN(a, b) (((a) > (b)) ? (b) : (a))

/**********************************************************************/
/*
File system layout onto disk blocks:

Block 0: Master block
Blocks 1 ... N_INODE_BLOCKS: inodes
Blocks N_INODE_BLOCKS+1 ... N_BLOCKS_ON_DISK-1: data for files and directories
   (Block N_BLOCKS+1 is allocated for the root directory)
*/

/**********************************************************************/
// Basic types and sizes
// Chosen carefully so that all block types pack nicely into a full block

// An index that refers to an inode
typedef unsigned short INODE_REFERENCE;
// Value used as an index when it does not refer to an inode
#define UNALLOCATED_INODE (USHRT_MAX-1)

// Value used as an index when it does not refer to a block
#define UNALLOCATED_BLOCK USHRT_MAX

// Number of inode blocks on the virtual disk
#define N_INODE_BLOCKS 8

// The block on the virtual disk containing the root directory
#define ROOT_DIRECTORY_BLOCK (N_INODE_BLOCKS + 1)

// Size of file/directory name
#define FILE_NAME_SIZE (16 - sizeof(INODE_REFERENCE))

// Number of data block references in an inode.  Just big enough to fit a reasonable
//  number of inodes into a single block
#define BLOCKS_PER_INODE (16-1)

/**********************************************************************/
// 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;

// Number of inodes stored in each block
#define INODES_PER_BLOCK (BLOCK_SIZE/sizeof(INODE))

// Total number of inodes in the file system
#define N_INODES (INODES_PER_BLOCK * N_INODE_BLOCKS)

// Block of inodes
typedef struct inode_block_s
{
  INODE inode[INODES_PER_BLOCK];
} INODE_BLOCK;


/**********************************************************************/
// Block 0
#define MASTER_BLOCK_REFERENCE 0

typedef struct master_block_s
{
  // 8 inodes per byte: One inode per bit: 1 = allocated, 0 = free
  // The first inode is byte 0, bit 0
  unsigned char inode_allocated_flag[N_INODES >> 3];

  // 8 data blocks per byte: One block per bit: 1 = allocated, 0 = free
  // Block 0 (the master block) is byte 0, bit 0
  unsigned char block_allocated_flag[N_BLOCKS_IN_DISK >> 3];
} MASTER_BLOCK;

/**********************************************************************/
// Single directory element
typedef struct directory_entry_s
{
  // Name of file/directory
  char name[FILE_NAME_SIZE];

  // UNALLOCATED_INODE if this directory entry is non-existent
  INODE_REFERENCE inode_reference;

} DIRECTORY_ENTRY;

// Number of directory entries stored in one data block
#define DIRECTORY_ENTRIES_PER_BLOCK (BLOCK_SIZE / sizeof(DIRECTORY_ENTRY))

// Directory block
typedef struct directory_block_s
{
  DIRECTORY_ENTRY entry[DIRECTORY_ENTRIES_PER_BLOCK];
} DIRECTORY_BLOCK;

/**********************************************************************/
// All-encompassing structure for a disk block
// The union says that all 4 of these elements occupy overlapping bytes in 
//  memory (hence, a block will only be one of these 4 at any given time)
typedef union block_u
{
  DATA_BLOCK data;
  MASTER_BLOCK master;
  INODE_BLOCK inodes;
  DIRECTORY_BLOCK directory;
} BLOCK;


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

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


#endif

Implementation

Most of your work will be dedicated to developing the API for your file system. While there are several executable programs that you will need to implement, because the API is shared across them, the executables tend to be relatively short functions (e.g., responsible for initializing things and checking command-line arguments.

File System API

Here is our API definition. As discussed earlier, you may chose to use this or not.

oufs_lib.h:

#ifndef OUFS_LIB
#define OUFS_LIB
#include "oufs.h"

#define MAX_PATH_LENGTH 200

// PROVIDED
void oufs_get_environment(char *cwd, char *disk_name);

// PROJECT 3
int oufs_format_disk(char  *virtual_disk_name);
int oufs_read_inode_by_reference(INODE_REFERENCE i, INODE *inode);
int oufs_write_inode_by_reference(INODE_REFERENCE i, INODE *inode);
int oufs_find_file(char *cwd,
                   char * path,
                   INODE_REFERENCE *parent,
                   INODE_REFERENCE *child, 
                   char *local_name);
int oufs_mkdir(char *cwd, char *path);
int oufs_list(char *cwd, char *path);
int oufs_rmdir(char *cwd, char *path);

// Helper functions in oufs_lib_support.c
void oufs_clean_directory_block(INODE_REFERENCE self,
                                INODE_REFERENCE parent,
                                BLOCK *block);
void oufs_clean_directory_entry(DIRECTORY_ENTRY *entry);
BLOCK_REFERENCE oufs_allocate_new_block();

// Helper functions to be provided
int oufs_find_open_bit(unsigned char value);

// PROJECT 4 ONLY
OUFILE* oufs_fopen(char *cwd, char *path, char *mode);
void oufs_fclose(OUFILE *fp);
int oufs_fwrite(OUFILE *fp, unsigned char * buf, int len);
int oufs_fread(OUFILE *fp, unsigned char * buf, int len);
int oufs_remove(char *cwd, char *path);
int oufs_link(char *cwd, char *path_src, char *path_dst);

#endif

Environment Variables

We use two environment variables to provide important context to the executables:

We provide a function that reads these two environment variables and fills in reasonable default values if they do not exist.

Executables and API

Although we describe the executables and the API together, your executable programs will generally be fairly short (only a main() function). For example, zformat.c will fetch the key environment variables and then call the API function that performs the formatting (this is where the hard work is done).

zformat

Creates and format the virtual disk

Shell command:

./zformat

Process:

zfilez

Shell command:

./zfilez [<name>]

In this notation, name is optional.

Behavior:

Output specifics:

zmkdir

Shell command:

./zmkdir <name>

Behavior:

zrmdir

Shell command:

./zrmdir <name>

Behavior:

Example Interaction

Below is an example interaction. Things to watch for: 1) changes in the allocation table configuration as the commands are executed, and 2) responses to the commands themselves.

$ ./zformat
$ ./zinspect -master
Inode table:
01
00
00
00
00
00
00
Block table:
ff
03
00
00
00
00
00
00
00
00
00
00
00
00
00
00
$ ./zfilez
./
../
$ ./zmkdir foo
$ ./zfilez
./
../
foo/
$ ./zinspect -master
Inode table:
03
00
00
00
00
00
00
Block table:
ff
07
00
00
00
00
00
00
00
00
00
00
00
00
00
00
$ ./zmkdir foo
foo already exists
$ ./zmkdir
Usage: zmkdir <dirname>
$ ./zmkdir foo bar
Usage: zmkdir <dirname>
$ ./zmkdir foo/bar
$ ./zfilez
./
../
foo/
$ ./zfilez foo
./
../
bar/
$ ./zrmdir foo
Directory not empty
$ ./zrmdir foo/bar
$ ./zrmdir foo
$ ./zfilez
./
../
$ ./zinspect -master
Inode table:
01
00
00
00
00
00
00
Block table:
ff
03
00
00
00
00
00
00
00
00
00
00
00
00
00
00
$

Hints

Support Files

Addenda

2018-10-25

2018-10-29

2018-11-02

2018-11-05

2018-11-06

2018-11-07

2018-11-08

2018-11-11

Back to Project List