Implement a Simple File System
Operating Systems
1 Introduction
In this assignment, you are expected to design and implement a simple file system (SFS) that can be mounted by the user under a directory in the user’s machine.
2 Some specifications to simplify your life The SFS introduces many limitations such as restricted filename lengths, no user concept, no protection among files, no support for concurrent access, etc. You could introduce additional restrictions in your design. However, such restrictions should be reasonable to not oversimplify the implementation and should be documented in your submission. Even with the said restrictions, the file system you are implementing is highly use able for embedded applications.
The following are the restrictions you will put on your code:
• Max file name of 16 characters.
• Max extension name of 3 characters. So in total your file name can have 20 characters (16 charactersfor name, 1 character for the “.” period, and finally 3 characters for the extension such as “txt”)
• Single level directory, so there will not be subdirectories (only a single root directory)
• You will implement an inode system
• You will implement bit map to keep track of free data blocks and find a free data block before
increasing the size of a file
• The size of one data block is 1024 bytes
• The maximum number of data blocks on the disk is 1024
3 About the supporting files
We will provide you with supporting files that include the code structure of solving the assignment. You will edit the C files we give you. We also provide you with test files to test your code. The test code will call functions inside your C file. You are freeto implement as many helper functions and other C files as you wish.
3.1 Emulated disk
Your file system is implemented over an emulated disk system, which is provided to you. The following is aschematic that illustrates the overall concept of the mountable simple file system.
The gray colored modules in the above schematic are provided by the Linux OS. The blue colored moduleswill be given to you. You are expected to implement the yellow colored module.
The disk emulator given to you provides a constant-cost disk (CCdisk). This CCdisk is a “virtual” diskspace that is separate from your computer disk space. It can be considered as an array of sectors (blocks offixed size). You can randomly access any given sector for reading or writing. The CCdisk is implementedas a file on the actual file system. Therefore, the data you store in the CCdisk is persistent across programinvocations.
To mimic the real disk, the CCdisk is divided into sectors of fixed size. For example, we can split thespace into 1024 byte sectors. The number of sectors times the size of a sector gives the total size of the disk.
In addition to holding the actual file and directory data, we need to store auxiliary data (meta data) thatdescribes the files and directories in the disk. Thestructure and number of bytes spent on meta data storage depends on the file system design, which is theconcern in this assignment.
3.2 API for the assignment
As mentioned earlier, the test files we will give you will be calling your C file functions. This means your Cfile will be an API for the test files. We will give you the API function names and you will have to fill them.
The following are the API functions you will implement:
Listing 1: Function names for your C code
The following table describes how these functions are supposed to behave
| Function | Explanation |
| mksfs(int fresh) | Formats the virtual disk implemented by the disk emulator and creates an instance of the simple file system on top of it. The mksfs() has a fresh flag to signal that the file system should be created from scratch. If flag is false, the file system is opened from the disk. The support for persistence is important so you can reuse existing data or create a new file system. |
| sfs getnextfilename(char *fname) | Copies the name of the next file in the directory intofname and returns non zero if there is a new file. Once all the files have been returned, this function returns 0. So, you should be able to use this function to loop through the directory. In implementing this function, you need to ensure that the function remembers thecurrent position in the directory at each call. Remember we have a single-level directory. |
| sfs getfilesize(char *path) | Returns the size of a given file. |
| sfs fopen(char *name) | Opens a file and returns the index that correspondsto the newly opened file in the file descriptor table. If the file does not exist, it creates a new file and sets its size to 0. If the file does exists, the file is opened in append mode (i.e., set the file pointer to the end of the file). |
| sfs fclose(int fileID) | Closes a file. This means you will remove the entryfrom the open file descriptor table. |
| sfs fwrite(int fileID, char *buf, int length) | Writes the given number of bytes of buffered data in buf into the open file, starting from the current filepointer. This in effect could increase the size of the file by the given number of bytes (it may not increase the file size by the number of bytes written if the write pointer is located at a location other than the end of the file). |
| sfs fread(int fileID, char *buf, int length) | Reads bytes of data into buf starting from the currentfile pointer. |
| sfs fseek(int fileID, int loc) | Moves the read/write pointer (a single pointer in SFS)to the given location. |
| sfs remove(char *file) | Removes the file from the directory entry, releases the file allocation table entries and releases the data blocks used by the file, so that they can be used by new files in the future. |
A file system is somewhat different from other OS components because it maintains data structures inmemory as well as disk. The disk data structures are important to manage the space in disk and allocateand de-allocate the disk space. Also, the disk data structures indicate where a file is allocated. Thisinformation is necessary to access the file. The following is what each function will be doing.
4 About inode
On-disk data structures of the file system include a super block, the root directory, free block list, and inodetable. The figure below shows a schematic of the on-disk organization of SFS.
Figure 1: superblock
The super block defines the file system geometry. It is also the first block in SFS. So the super block needs tohave some form of identification to inform the program what type of file system format is followed for storingthe data. The figure below shows the proposed structure for the super block. We expect your file system toimplement these features, but some modifications are acceptable provided they are well documented. Eachfield in the figure is 4 bytes long. For instance, the magic number field is 4 bytes long. With a 1024-bytelong block , we can see that there will plenty of unused space in the super block.
Figure 2: Super block structure
A file or directory in SFS is defined by an inode. Remember we simplified the SFS by just having a singleroot directory (no subdirectories). This root directory is pointed to by an inode, which is pointed to by thesuper block. The inode structure we use here is slightly simplified too. It does not have the double andtriple indirect pointers. It has direct and single indirect pointers. With the inode all the meta information(size, mode, ownership) can be associated with the inode. So, the directory entry can be pretty simple. Thefigure below shows the simplified inode structure.
Figure 3: inode structure
We are suggesting the inode structure shown above to maintain a similarity to the UNIX file system. However,the simplification made to the SFS inode makes it impossible to read or write the SFS using UNIX softwareor vice-versa.
The directory is a mapping table to convert the file name to the inode. Remember a file name can have anextension too. You limit the extension to 3 characters max. A directory entry is a structure that containstwo fields (at least): inode and file name. You could add other fields (if you find necessary). Remember the inode also has some attributes such as mode, etc. Depending on the number of entries you havein the directory, the directory could be spanning across multiple blocks in the disk. The inodepointing to the root directory is stored in the super block so we know how to access the root directory. We assume that the SFS root directory would not grow larger than the max file size we could accommodate in SFS.
In addition to the on-disk data structures, we need a set of in-memory data structures to implement the filesystem. The in-memory data structures improve the performance of the file system by caching the on diskinformation in memory. Two data structures should be used in this assignment: directory table and inodecache. The directory table keeps a copy of the directory block in memory. Don’t make the simplification oflimiting the root directory to a single block (this would severely restrict the size of the disk by limiting thenumber of files in disk). Instead, you could either read the whole directory into the memory or have a cache
for the currently used directory block. The later one could be hard to get right.
When you want to create, delete, read, or write a file, first operation is to find the appropriate directory entry. Therefore, directory table is a highly accessed data structure and is a good candidate to keep inmemory. Another data structure to cache in the memory is the free block list. In your assignment you willuse bit map.
The figure below shows the in-memory data structure and how it connects to the other components. Weneed at least a table that combines the open file descriptor tables (the per-process one and system-wide one)in a UNIX-like operating system.
Figure 4: In-memory data structure
When a file is opened we create an entry in this table. The index of the newly created entry is the filedescriptor that is returned by the file opening activity. That is the return value of the sfs fopen() isprecisely this index.
The entry created in the file descriptor table has at least two pieces of important information: inodenumber and a read/write pointer. The inode number is the one that corresponds to the file. Rememberjust like there is an inode for the root directory, there is one inode associated with each file. When a file isopened, that inode number is recorded in this table entry. The read/write pointer is also set according tothe file system operating rule. For instance, in this assignment (SFS), you are going to set the read/writepointer to the end of the file at open so that data written into the file will be appended to the file.
In SFS, sfs fseek() is a direct way of setting the read/write pointer value. The interesting problem youcould be faced with is what to do when you perform a read or write after setting the read/write pointer.Specifically, if we have a single pointer then sfs fread() would also advance the write pointer, and similarly,the sfs fwrite() would advance the read pointer as well. We can simplify the complexity and let it be thatway. You could opt to implement the SFS with two independent read and write pointers as well. In thatcase, the sfs fseek() needs to have a parameter to specify whether the read, write, or both pointers shouldbe moved by the seek operation.
As shown in the figure above, we have in-memory data structures and on-disk data structures in a filesystem. The in-memory data structures are activated as soon as the file system is up and running and theyare updated every time a file system operation is carried out. While designing and implementing a givenfile system operation you need to think of the actions that should be carried out on the in-memory and ondisk data structures. In addition to the Open File Descriptor Table, we have variety of different caches forinodes, disk blocks and the root directory. Your design could implement all of them or some of them. Filesystem performance is not a concern for this assignment correct operation is what we need.
5 Suggested steps for your code
5.1 Creating a file
- Allocate and initialize an inode. You need to somehow remember the state of the inode table to knowwhich and inode could be allocated for the newly created file. Simply remembering the last inode usedis not correct because as you delete files, some inodes in the middle of the table will become unusedand available for reuse.
• Write the mapping between the inode and file name in the root directory. You could simply updatethe memory and disk copies.
• When no disk data block allocated set the file size to 0. This can also open the file for transactions(read and write). Note that the SFS API does not have a separate create() call. So you can do thisactivity as part of the open() call.5.2 Writing to a file
• Allocate disk blocks (mark them as allocated in your free block list).
• Modify the file’s inode to point to these blocks.
• Write the data the user gives to these blocks.
• Flush all modifications to disk.
• Note that all writes to disk are at block sizes. If you are writing few bytes into a file, this might
actually end up writing a block to next. So if you are writing to an existing file, it is important youread the last block and set the write pointer to the end of file. The bytes you want to write goes tothe end of the previous bytes that are already part of the file. After you have written the bytes, youflush the block to the disk.
5.3 Seek on a file
• Modify the read and write pointers in memory. There is nothing to be done on disk.
disk_emu.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include “disk_emu.h”
FILE* fp = NULL;
double L, p;
double r;
int BLOCK_SIZE, MAX_BLOCK, MAX_RETRY, lru;
/*———————————————————-*/
/*Close the disk file filled when you don’t need it anymore. */
/*———————————————————-*/
int close_disk()
{
if(NULL != fp)
{
fclose(fp);
}
return 0;
}
/*—————————————*/
/*Initializes a disk file filled with 0’s*/
/*—————————————*/
int init_fresh_disk(char *filename, int block_size, int num_blocks)
{
int i, j;
/*Set up latency at 0.02 second*/
L = 00000.f;
/*Set up failure at 10%*/
p = -1.f;
/*Set up max retry attempts after failure to 3*/
MAX_RETRY = 3;
BLOCK_SIZE = block_size;
MAX_BLOCK = num_blocks;
/*Initializes the random number generator*/
srand((unsigned int)(time( 0 )) );
/*Creates a new file*/
fp = fopen (filename, “w+b”);
if (fp == NULL)
{
printf(“Could not create new disk file %s\n\n”, filename);
return -1;
}
/*Fills the file with 0’s to its given size*/
for (i = 0; i < MAX_BLOCK; i++)
{
for (j = 0; j < BLOCK_SIZE; j++)
{
fputc(0, fp);
}
}
return 0;
}
/*—————————-*/
/*Initializes an existing disk*/
/*—————————-*/
int init_disk(char *filename, int block_size, int num_blocks)
{
/*Set up latency at 0.02 second*/
L = 00000.f;
/*Set up failure at 10%*/
p = -1.f;
/*Set up max retry attempts after failure to 3*/
MAX_RETRY = 3;
BLOCK_SIZE = block_size;
MAX_BLOCK = num_blocks;
/*Initializes the random number generator*/
srand((unsigned int)(time( 0 )) );
/*Opens a file*/
fp = fopen (filename, “r+b”);
if (fp == NULL)
{
printf(“Could not open %s\n\n”, filename);
return -1;
}
return 0;
}
/*——————————————————————-*/
/*Reads a series of blocks from the disk into the buffer */
/*——————————————————————-*/
int read_blocks(int start_address, int nblocks, void *buffer)
{
int i, j, e, s;
e = 0;
s = 0;
/*Sets up a temporary buffer*/
void* blockRead = (void*) malloc(BLOCK_SIZE);
/*Checks that the data requested is within the range of addresses of the disk*/
if (start_address + nblocks > MAX_BLOCK)
{
printf(“out of bound error %d\n”, start_address);
return -1;
}
/*Goto the data requested from the disk*/
fseek(fp, start_address * BLOCK_SIZE, SEEK_SET);
/*For every block requested*/
for (i = 0; i < nblocks; ++i)
{
/*Pause until the latency duration is elapsed*/
// usleep(L);
s++;
fread(blockRead, BLOCK_SIZE, 1, fp);
for (j = 0; j < BLOCK_SIZE; j++)
{
memcpy(buffer+(i*BLOCK_SIZE), blockRead, BLOCK_SIZE);
}
}
free(blockRead);
/*If no failure return the number of blocks read, else return the negative number of failures*/
if (e == 0)
return s;
else
return e;
}
/*——————————————————————*/
/*Writes a series of blocks to the disk from the buffer */
/*——————————————————————*/
int write_blocks(int start_address, int nblocks, void *buffer)
{
int i, e, s;
e = 0;
s = 0;
void* blockWrite = (void*) malloc(BLOCK_SIZE);
/*Checks that the data requested is within the range of addresses of the disk*/
if (start_address + nblocks > MAX_BLOCK)
{
printf(“out of bound error\n”);
return -1;
}
/*Goto where the data is to be written on the disk*/
fseek(fp, start_address * BLOCK_SIZE, SEEK_SET);
/*For every block requested*/
for (i = 0; i < nblocks; ++i)
{
/*Pause until the latency duration is elapsed*/
usleep(L);
memcpy(blockWrite, buffer+(i*BLOCK_SIZE), BLOCK_SIZE);
fwrite(blockWrite, BLOCK_SIZE, 1, fp);
fflush(fp);
s++;
}
free(blockWrite);
/*If no failure return the number of blocks written, else return the negative number of failures*/
if (e == 0)
return s;
else
return e;
}
disk_emu.h
int init_fresh_disk(char *filename, int block_size, int num_blocks);
int init_disk(char *filename, int block_size, int num_blocks);
int read_blocks(int start_address, int nblocks, void *buffer);
int write_blocks(int start_address, int nblocks, void *buffer);
int close_disk();
fuse_wrappers.c
#define FUSE_USE_VERSION 30
#include <fuse.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <dirent.h>
#include <errno.h>
#include <sys/time.h>
#include “disk_emu.h”
#include “sfs_api.h”
static int fuse_getattr(const char *path, struct stat *stbuf)
{
int res = 0;
int size;
memset(stbuf, 0, sizeof(struct stat));
if (strcmp(path, “/”) == 0) {
stbuf->st_mode = S_IFDIR | 0755;
stbuf->st_nlink = 2;
} else if((size = sfs_getfilesize(path)) != -1) {
stbuf->st_mode = S_IFREG | 0666;
stbuf->st_nlink = 1;
stbuf->st_size = size;
} else
res = -ENOENT;
return res;
}
static int fuse_readdir(const char *path, void *buf, fuse_fill_dir_t filler,
off_t offset, struct fuse_file_info *fi)
{
char file_name[MAXFILENAME];
if (strcmp(path, “/”) != 0)
return -ENOENT;
filler(buf, “.”, NULL, 0);
filler(buf, “..”, NULL, 0);
while(sfs_getnextfilename(file_name)) {
filler(buf, &file_name[1], NULL, 0);
}
return 0;
}
static int fuse_unlink(const char *path)
{
int res;
char filename[MAXFILENAME];
strcpy(filename, path);
res = sfs_remove(filename);
if (res == -1)
return -errno;
return 0;
}
static int fuse_open(const char *path, struct fuse_file_info *fi)
{
int res;
char filename[MAXFILENAME];
strcpy(filename, path);
res = sfs_fopen(filename);
if (res == -1)
return -errno;
sfs_fclose(res);
return 0;
}
static int fuse_read(const char *path, char *buf, size_t size, off_t offset,
struct fuse_file_info *fi)
{
int fd;
int res;
char filename[MAXFILENAME];
strcpy(filename, path);
fd = sfs_fopen(filename);
if (fd == -1)
return -errno;
if(sfs_fseek(fd, offset) == -1)
return -errno;
res = sfs_fread(fd, buf, size);
if (res == -1)
return -errno;
sfs_fclose(fd);
return res;
}
static int fuse_write(const char *path, const char *buf, size_t size,
off_t offset, struct fuse_file_info *fi)
{
int fd;
int res;
char filename[MAXFILENAME];
strcpy(filename, path);
fd = sfs_fopen(filename);
if (fd == -1)
return -errno;
if(sfs_fseek(fd, offset) == -1)
return -errno;
res = sfs_fwrite(fd, buf, size);
if (res == -1)
return -errno;
sfs_fclose(fd);
return res;
}
static int fuse_truncate(const char *path, off_t size)
{
char filename[MAXFILENAME];
int fd;
strcpy(filename, path);
fd = sfs_remove(filename);
if (fd == -1)
return -errno;
fd = sfs_fopen(filename);
sfs_fclose(fd);
return 0;
}
static int fuse_access(const char *path, int mask)
{
return 0;
}
static int fuse_mknod(const char *path, mode_t mode, dev_t rdev)
{
return 0;
}
static int fuse_create (const char *path, mode_t mode, struct fuse_file_info *fp)
{
char filename[MAXFILENAME];
int fd;
strcpy(filename, path);
fd = sfs_fopen(filename);
sfs_fclose(fd);
return 0;
}
static struct fuse_operations xmp_oper = {
.getattr = fuse_getattr,
.readdir = fuse_readdir,
.mknod = fuse_mknod,
.unlink = fuse_unlink,
.truncate = fuse_truncate,
.open = fuse_open,
.read = fuse_read,
.write = fuse_write,
.access = fuse_access,
.create = fuse_create,
};
int main(int argc, char *argv[])
{
mksfs(1);
return fuse_main(argc, argv, &xmp_oper, NULL);
}
sfs_api.c
#include “sfs_api.h”
#include “bitmap.h”
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fuse.h>
#include <strings.h>
#include “disk_emu.h”
#define LASTNAME_FIRSTNAME_DISK “sfs_disk.disk”
#define NUM_BLOCKS 1024 //maximum number of data blocks on the disk.
#define BITMAP_ROW_SIZE (NUM_BLOCKS/8) // this essentially mimcs the number of rows we have in the bitmap. we will have 128 rows.
/* macros */
#define FREE_BIT(_data, _which_bit) \
_data = _data | (1 << _which_bit)
#define USE_BIT(_data, _which_bit) \
_data = _data & ~(1 << _which_bit)
//initialize all bits to high
uint8_t free_bit_map[BITMAP_ROW_SIZE] = { [0 … BITMAP_ROW_SIZE – 1] = UINT8_MAX };
void mksfs(int fresh) {
}
int sfs_getnextfilename(char *fname){
}
int sfs_getfilesize(const char* path){
}
int sfs_fopen(char *name){
}
int sfs_fclose(int fileID) {
}
int sfs_fread(int fileID, char *buf, int length) {
}
int sfs_fwrite(int fileID, const char *buf, int length) {
}
int sfs_fseek(int fileID, int loc) {
}
int sfs_remove(char *file) {
}
sfs_api.h
#ifndef _INCLUDE_SFS_API_H_
#define _INCLUDE_SFS_API_H_
#include <stdint.h>
#define MAX_FILE_NAME 20
#define MAX_EXTENSION_NAME 3
typedef struct superblock_t{
uint64_t magic;
uint64_t block_size;
uint64_t fs_size;
uint64_t inode_table_len;
uint64_t root_dir_inode;
} superblock_t;
typedef struct inode_t {
unsigned int mode;
unsigned int link_cnt;
unsigned int uid;
unsigned int gid;
unsigned int size;
unsigned int data_ptrs[12];
unsigned int indirectPointer; // points to a data block that points to other data blocks (Single indirect)
} inode_t;
/*
* inodeIndex which inode this entry describes
* inode pointer towards the inode in the inode table
*rwptr where in the file to start
*/
typedef struct file_descriptor {
uint64_t inodeIndex;
inode_t* inode; //
uint64_t rwptr;
} file_descriptor;
typedef struct directory_entry{
int num; // represents the inode number of the entery.
char name[MAX_FILE_NAME]; // represents the name of the entery.
}directory_entry;
void mksfs(int fresh);
int sfs_getnextfilename(char *fname);
int sfs_getfilesize(const char* path);
int sfs_fopen(char *name);
int sfs_fclose(int fileID);
int sfs_fread(int fileID, char *buf, int length);
int sfs_fwrite(int fileID, const char *buf, int length);
int sfs_fseek(int fileID, int loc);
int sfs_remove(char *file);
#endif //_INCLUDE_SFS_API_H_
sfs_test.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “sfs_api.h”
/* The maximum file name length. We assume that filenames can contain
* upper-case letters and periods (‘.’) characters. Feel free to
* change this if your implementation differs.
*/
#define MAX_FNAME_LENGTH 20 /* Assume at most 20 characters (16.3) */
/* The maximum number of files to attempt to open or create. NOTE: we
* do not _require_ that you support this many files. This is just to
* test the behavior of your code.
*/
#define MAX_FD 100
/* The maximum number of bytes we’ll try to write to a file. If you
* support much shorter or larger files for some reason, feel free to
* reduce this value.
*/
#define MAX_BYTES 30000 /* Maximum file size I’ll try to create */
#define MIN_BYTES 10000 /* Minimum file size */
/* Just a random test string.
*/
static char test_str[] = “The quick brown fox jumps over the lazy dog.\n”;
/* rand_name() – return a randomly-generated, but legal, file name.
*
* This function creates a filename of the form xxxxxxxx.xxx, where
* each ‘x’ is a random upper-case letter (A-Z). Feel free to modify
* this function if your implementation requires shorter filenames, or
* supports longer or different file name conventions.
*
* The return value is a pointer to the new string, which may be
* released by a call to free() when you are done using the string.
*/
char *rand_name()
{
char fname[MAX_FNAME_LENGTH];
int i;
for (i = 0; i < MAX_FNAME_LENGTH; i++) {
if (i != 16) {
fname[i] = ‘A’ + (rand() % 26);
}
else {
fname[i] = ‘.’;
}
}
fname[i] = ‘\0’;
return (strdup(fname));
}
/* The main testing program
*/
int
main(int argc, char **argv)
{
int i, j, k;
int chunksize;
int readsize;
char *buffer;
char fixedbuf[1024];
int fds[MAX_FD];
char *names[MAX_FD];
int filesize[MAX_FD];
int nopen; /* Number of files simultaneously open */
int ncreate; /* Number of files created in directory */
int error_count = 0;
int tmp;
mksfs(1); /* Initialize the file system. */
/* First we open two files and attempt to write data to them.
*/
for (i = 0; i < 2; i++) {
names[i] = rand_name();
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
fprintf(stderr, “ERROR: creating first test file %s\n”, names[i]);
error_count++;
}
tmp = sfs_fopen(names[i]);
if (tmp >= 0 && tmp != fds[i]) {
fprintf(stderr, “ERROR: file %s was opened twice\n”, names[i]);
error_count++;
}
filesize[i] = (rand() % (MAX_BYTES-MIN_BYTES)) + MIN_BYTES;
}
for (i = 0; i < 2; i++) {
for (j = i + 1; j < 2; j++) {
if (fds[i] == fds[j]) {
fprintf(stderr, “Warning: the file descriptors probably shouldn’t be the same?\n”);
}
}
}
printf(“Two files created with zero length:\n”);
for (i = 0; i < 2; i++) {
for (j = 0; j < filesize[i]; j += chunksize) {
if ((filesize[i] – j) < 10) {
chunksize = filesize[i] – j;
}
else {
chunksize = (rand() % (filesize[i] – j)) + 1;
}
if ((buffer = malloc(chunksize)) == NULL) {
fprintf(stderr, “ABORT: Out of memory!\n”);
exit(-1);
}
for (k = 0; k < chunksize; k++) {
buffer[k] = (char) (j+k);
}
tmp = sfs_fwrite(fds[i], buffer, chunksize);
if (tmp != chunksize) {
fprintf(stderr, “ERROR: Tried to write %d bytes, but wrote %d\n”,
chunksize, tmp);
error_count++;
}
free(buffer);
}
}
if (sfs_fclose(fds[1]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[1]);
error_count++;
}
/* Sneaky attempt to close already closed file handle. */
if (sfs_fclose(fds[1]) == 0) {
fprintf(stderr, “ERROR: close of stale handle %d succeeded\n”, fds[1]);
error_count++;
}
printf(“File %s now has length %d and %s now has length %d:\n”,
names[0], filesize[0], names[1], filesize[1]);
/* Just to be cruel – attempt to read from a closed file handle.
*/
if (sfs_fread(fds[1], fixedbuf, sizeof(fixedbuf)) > 0) {
fprintf(stderr, “ERROR: read from a closed file handle?\n”);
error_count++;
}
fds[1] = sfs_fopen(names[1]);
sfs_fseek(fds[0], 0);
sfs_fseek(fds[1], 0);
for (i = 0; i < 2; i++) {
for (j = 0; j < filesize[i]; j += chunksize) {
if ((filesize[i] – j) < 10) {
chunksize = filesize[i] – j;
}
else {
chunksize = (rand() % (filesize[i] – j)) + 1;
}
if ((buffer = malloc(chunksize)) == NULL) {
fprintf(stderr, “ABORT: Out of memory!\n”);
exit(-1);
}
readsize = sfs_fread(fds[i], buffer, chunksize);
if (readsize != chunksize) {
fprintf(stderr, “ERROR: Requested %d bytes, read %d\n”, chunksize, readsize);
readsize = chunksize;
}
for (k = 0; k < readsize; k++) {
if (buffer[k] != (char)(j+k)) {
fprintf(stderr, “ERROR: data error at offset %d in file %s (%d,%d)\n”,
j+k, names[i], buffer[k], (char)(j+k));
error_count++;
break;
}
}
free(buffer);
}
}
for (i = 0; i < 2; i++) {
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: closing file %s\n”, names[i]);
error_count++;
}
}
/* Now try to close the files. Don’t
* care about the return codes, really, but just want to make sure
* this doesn’t cause a problem.
*/
for (i = 0; i < 2; i++) {
if (sfs_fclose(fds[i]) == 0) {
fprintf(stderr, “Warning: closing already closed file %s\n”, names[i]);
}
}
/* Now just try to open up a bunch of files.
*/
ncreate = 0;
for (i = 0; i < MAX_FD; i++) {
names[i] = rand_name();
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
break;
}
sfs_fclose(fds[i]);
ncreate++;
}
printf(“Created %d files in the root directory\n”, ncreate);
nopen = 0;
for (i = 0; i < ncreate; i++) {
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
break;
}
nopen++;
}
printf(“Simultaneously opened %d files\n”, nopen);
for (i = 0; i < nopen; i++) {
tmp = sfs_fwrite(fds[i], test_str, strlen(test_str));
if (tmp != strlen(test_str)) {
fprintf(stderr, “ERROR: Tried to write %d, returned %d\n”,
(int)strlen(test_str), tmp);
error_count++;
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
/* Re-open in reverse order */
for (i = nopen-1; i >= 0; i–) {
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
fprintf(stderr, “ERROR: can’t re-open file %s\n”, names[i]);
}
}
/* Now test the file contents.
*/
for (i = 0; i < nopen; i++) {
sfs_fseek(fds[i], 0);
}
for (j = 0; j < strlen(test_str); j++) {
for (i = 0; i < nopen; i++) {
char ch;
if (sfs_fread(fds[i], &ch, 1) != 1) {
fprintf(stderr, “ERROR: Failed to read 1 character\n”);
error_count++;
}
if (ch != test_str[j]) {
fprintf(stderr, “ERROR: Read wrong byte from %s at %d (%d,%d)\n”,
names[i], j, ch, test_str[j]);
error_count++;
break;
}
}
}
/* Now close all of the open file handles.
*/
for (i = 0; i < nopen; i++) {
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
/* Now we try to re-initialize the system.
*/
mksfs(0);
for (i = 0; i < nopen; i++) {
fds[i] = sfs_fopen(names[i]);
sfs_fseek(fds[i], 0);
if (fds[i] >= 0) {
readsize = sfs_fread(fds[i], fixedbuf, sizeof(fixedbuf));
if (readsize != strlen(test_str)) {
fprintf(stderr, “ERROR: Read wrong number of bytes\n”);
error_count++;
}
for (j = 0; j < strlen(test_str); j++) {
if (test_str[j] != fixedbuf[j]) {
fprintf(stderr, “ERROR: Wrong byte in %s at %d (%d,%d)\n”,
names[i], j, fixedbuf[j], test_str[j]);
printf(“%d\n”, fixedbuf[1]);
error_count++;
break;
}
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
}
printf(“Trying to fill up the disk with repeated writes to %s.\n”, names[0]);
printf(“(This may take a while).\n”);
/* Now try opening the first file, and just write a huge bunch of junk.
* This is just to try to fill up the disk, to see what happens.
*/
fds[0] = sfs_fopen(names[0]);
if (fds[0] >= 0) {
for (i = 0; i < 100000; i++) {
int x;
if ((i % 100) == 0) {
fprintf(stderr, “%d\r”, i);
}
memset(fixedbuf, (char)i, sizeof(fixedbuf));
x = sfs_fwrite(fds[0], fixedbuf, sizeof(fixedbuf));
if (x != sizeof(fixedbuf)) {
/* Sooner or later, this write should fail. The only thing is that
* it should fail gracefully, without any catastrophic errors.
*/
printf(“Write failed after %d iterations.\n”, i);
printf(“If the emulated disk contains just over %d bytes, this is OK\n”,
(i * (int)sizeof(fixedbuf)));
break;
}
}
sfs_fclose(fds[0]);
}
else {
fprintf(stderr, “ERROR: re-opening file %s\n”, names[0]);
}
/* Now, having filled up the disk, try one more time to read the
* contents of the files we created.
*/
for (i = 0; i < nopen; i++) {
fds[i] = sfs_fopen(names[i]);
sfs_fseek(fds[i], 0);
if (fds[i] >= 0) {
readsize = sfs_fread(fds[i], fixedbuf, sizeof(fixedbuf));
if (readsize < strlen(test_str)) {
fprintf(stderr, “ERROR: Read wrong number of bytes\n”);
error_count++;
}
for (j = 0; j < strlen(test_str); j++) {
if (test_str[j] != fixedbuf[j]) {
fprintf(stderr, “ERROR: Wrong byte in %s at position %d (%d,%d)\n”,
names[i], j, fixedbuf[j], test_str[j]);
error_count++;
break;
}
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
}
fprintf(stderr, “Test program exiting with %d errors\n”, error_count);
return (error_count);
}
sfs_test2.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “sfs_api.h”
/* The maximum file name length. We assume that filenames can contain
* upper-case letters and periods (‘.’) characters. Feel free to
* change this if your implementation differs.
*/
#define MAX_FNAME_LENGTH 20 /* Assume at most 20 characters (16.3) */
/* The maximum number of files to attempt to open or create. NOTE: we
* do not _require_ that you support this many files. This is just to
* test the behavior of your code.
*/
#define MAX_FD 100
/* The maximum number of bytes we’ll try to write to a file. If you
* support much shorter or larger files for some reason, feel free to
* reduce this value.
*/
#define MAX_BYTES 30000 /* Maximum file size I’ll try to create */
#define MIN_BYTES 10000 /* Minimum file size */
/* Just a random test string.
*/
static char test_str[] = “The quick brown fox jumps over the lazy dog.\n”;
/* rand_name() – return a randomly-generated, but legal, file name.
*
* This function creates a filename of the form xxxxxxxx.xxx, where
* each ‘x’ is a random upper-case letter (A-Z). Feel free to modify
* this function if your implementation requires shorter filenames, or
* supports longer or different file name conventions.
*
* The return value is a pointer to the new string, which may be
* released by a call to free() when you are done using the string.
*/
char *rand_name()
{
char fname[MAX_FNAME_LENGTH];
int i;
for (i = 0; i < MAX_FNAME_LENGTH; i++) {
if (i != 16) {
fname[i] = ‘A’ + (rand() % 26);
}
else {
fname[i] = ‘.’;
}
}
fname[i] = ‘\0’;
return (strdup(fname));
}
/* The main testing program
*/
int
main(int argc, char **argv)
{
int i, j, k;
int chunksize;
int readsize;
char *buffer;
char fixedbuf[1024];
int fds[MAX_FD];
char *names[MAX_FD];
int filesize[MAX_FD];
int nopen; /* Number of files simultaneously open */
int ncreate; /* Number of files created in directory */
int error_count = 0;
int tmp;
mksfs(1); /* Initialize the file system. */
/* First we open two files and attempt to write data to them.
*/
{
char fname[MAX_FNAME_LENGTH+10];
int i;
for (i = 0; i < MAX_FNAME_LENGTH+10; i++) {
if (i != 8) {
fname[i] = ‘A’ + (rand() % 26);
}
else {
fname[i] = ‘.’;
}
}
fname[i] = ‘\0’;
int derp = sfs_fopen(fname);
if (derp >= 0) {
fprintf(stderr, “ERROR: creating file with too long name\n”);
error_count++;
}
}
for (i = 0; i < 2; i++) {
names[i] = rand_name();
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
fprintf(stderr, “ERROR: creating first test file %s\n”, names[i]);
error_count++;
}
tmp = sfs_fopen(names[i]);
if (tmp >= 0 && tmp != fds[i]) {
fprintf(stderr, “ERROR: file %s was opened twice\n”, names[i]);
error_count++;
}
filesize[i] = (rand() % (MAX_BYTES-MIN_BYTES)) + MIN_BYTES;
}
for (i = 0; i < 2; i++) {
for (j = i + 1; j < 2; j++) {
if (fds[i] == fds[j]) {
fprintf(stderr, “Warning: the file descriptors probably shouldn’t be the same?\n”);
}
}
}
printf(“Two files created with zero length:\n”);
for (i = 0; i < 2; i++) {
for (j = 0; j < filesize[i]; j += chunksize) {
if ((filesize[i] – j) < 10) {
chunksize = filesize[i] – j;
}
else {
chunksize = (rand() % (filesize[i] – j)) + 1;
}
if ((buffer = malloc(chunksize)) == NULL) {
fprintf(stderr, “ABORT: Out of memory!\n”);
exit(-1);
}
for (k = 0; k < chunksize; k++) {
buffer[k] = (char) (j+k);
}
tmp = sfs_fwrite(fds[i], buffer, chunksize);
if (tmp != chunksize) {
fprintf(stderr, “ERROR: Tried to write %d bytes, but wrote %d\n”,
chunksize, tmp);
error_count++;
}
free(buffer);
}
int tmp = sfs_getfilesize(names[i]);
if (filesize[i] != tmp) {
fprintf(stderr, “ERROR: mismatch file size %d, %d\n”, filesize[i], tmp);
error_count++;
}
}
if (sfs_fclose(fds[1]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[1]);
error_count++;
}
/* Sneaky attempt to close already closed file handle. */
if (sfs_fclose(fds[1]) == 0) {
fprintf(stderr, “ERROR: close of stale handle %d succeeded\n”, fds[1]);
error_count++;
}
printf(“File %s now has length %d and %s now has length %d:\n”,
names[0], filesize[0], names[1], filesize[1]);
/* Just to be cruel – attempt to read from a closed file handle.
*/
if (sfs_fread(fds[1], fixedbuf, sizeof(fixedbuf)) > 0) {
fprintf(stderr, “ERROR: read from a closed file handle?\n”);
error_count++;
}
fds[1] = sfs_fopen(names[1]);
sfs_fseek(fds[0], 0);
sfs_fseek(fds[1], 0);
for (i = 0; i < 2; i++) {
for (j = 0; j < filesize[i]; j += chunksize) {
if ((filesize[i] – j) < 10) {
chunksize = filesize[i] – j;
}
else {
chunksize = (rand() % (filesize[i] – j)) + 1;
}
if ((buffer = malloc(chunksize)) == NULL) {
fprintf(stderr, “ABORT: Out of memory!\n”);
exit(-1);
}
readsize = sfs_fread(fds[i], buffer, chunksize);
if (readsize != chunksize) {
fprintf(stderr, “ERROR: Requested %d bytes, read %d\n”, chunksize, readsize);
readsize = chunksize;
}
for (k = 0; k < readsize; k++) {
if (buffer[k] != (char)(j+k)) {
fprintf(stderr, “ERROR: data error at offset %d in file %s (%d,%d)\n”,
j+k, names[i], buffer[k], (char)(j+k));
error_count++;
break;
}
}
free(buffer);
}
}
for (i = 0; i < 2; i++) {
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: closing file %s\n”, names[i]);
error_count++;
}
}
/* Now try to close the files. Don’t
* care about the return codes, really, but just want to make sure
* this doesn’t cause a problem.
*/
for (i = 0; i < 2; i++) {
if (sfs_fclose(fds[i]) == 0) {
fprintf(stderr, “Warning: closing already closed file %s\n”, names[i]);
}
}
sfs_remove(names[0]);
sfs_remove(names[1]);
/* Now just try to open up a bunch of files.
*/
ncreate = 0;
for (i = 0; i < MAX_FD; i++) {
names[i] = rand_name();
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
break;
}
sfs_fclose(fds[i]);
ncreate++;
}
printf(“Created %d files in the root directory\n”, ncreate);
nopen = 0;
for (i = 0; i < ncreate; i++) {
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
break;
}
nopen++;
}
printf(“Simultaneously opened %d files\n”, nopen);
for (i = 0; i < nopen; i++) {
tmp = sfs_fwrite(fds[i], test_str, strlen(test_str));
if (tmp != strlen(test_str)) {
fprintf(stderr, “ERROR: Tried to write %d, returned %d\n”,
(int)strlen(test_str), tmp);
error_count++;
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
/* Re-open in reverse order */
for (i = nopen-1; i >= 0; i–) {
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
fprintf(stderr, “ERROR: can’t re-open file %s\n”, names[i]);
}
}
/* Now test the file contents.
*/
for (i = 0; i < nopen; i++) {
sfs_fseek(fds[i], 0);
}
for (j = 0; j < strlen(test_str); j++) {
for (i = 0; i < nopen; i++) {
char ch;
if (sfs_fread(fds[i], &ch, 1) != 1) {
fprintf(stderr, “ERROR: Failed to read 1 character\n”);
error_count++;
}
if (ch != test_str[j]) {
fprintf(stderr, “ERROR: Read wrong byte from %s at %d (%d,%d)\n”,
names[i], j, ch, test_str[j]);
error_count++;
break;
}
}
}
/* Now close all of the open file handles.
*/
for (i = 0; i < nopen; i++) {
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
/* Now we try to re-initialize the system.
*/
mksfs(0);
for (i = 0; i < nopen; i++) {
fds[i] = sfs_fopen(names[i]);
sfs_fseek(fds[i], 0);
if (fds[i] >= 0) {
readsize = sfs_fread(fds[i], fixedbuf, sizeof(fixedbuf));
if (readsize != strlen(test_str)) {
fprintf(stderr, “ERROR: Read wrong number of bytes\n”);
error_count++;
}
for (j = 0; j < strlen(test_str); j++) {
if (test_str[j] != fixedbuf[j]) {
fprintf(stderr, “ERROR: Wrong byte in %s at %d (%d,%d)\n”,
names[i], j, fixedbuf[j], test_str[j]);
printf(“%d\n”, fixedbuf[1]);
error_count++;
break;
}
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
}
printf(“Trying to fill up the disk with repeated writes to %s.\n”, names[0]);
printf(“(This may take a while).\n”);
/* Now try opening the first file, and just write a huge bunch of junk.
* This is just to try to fill up the disk, to see what happens.
*/
fds[0] = sfs_fopen(names[0]);
if (fds[0] >= 0) {
for (i = 0; i < 100000; i++) {
int x;
if ((i % 100) == 0) {
fprintf(stderr, “%d\r”, i);
}
memset(fixedbuf, (char)i, sizeof(fixedbuf));
x = sfs_fwrite(fds[0], fixedbuf, sizeof(fixedbuf));
if (x != sizeof(fixedbuf)) {
/* Sooner or later, this write should fail. The only thing is that
* it should fail gracefully, without any catastrophic errors.
*/
printf(“Write failed after %d iterations.\n”, i);
printf(“If the emulated disk contains just over %d bytes, this is OK\n”,
(i * (int)sizeof(fixedbuf)));
break;
}
}
sfs_fclose(fds[0]);
}
else {
fprintf(stderr, “ERROR: re-opening file %s\n”, names[0]);
}
printf(“Directory listing\n”);
char *filename = (char *)malloc(MAX_FNAME_LENGTH);
int max = 0;
while (sfs_getnextfilename(filename)) {
if (strcmp(filename, names[max]) != 0) {
printf(“ERROR misnamed file %d: %s %s\n”, max, filename, names[max]);
error_count++;
}
max++;
}
/* Now, having filled up the disk, try one more time to read the
* contents of the files we created.
*/
for (i = 0; i < nopen; i++) {
fds[i] = sfs_fopen(names[i]);
sfs_fseek(fds[i], 0);
if (fds[i] >= 0) {
readsize = sfs_fread(fds[i], fixedbuf, sizeof(fixedbuf));
if (readsize < strlen(test_str)) {
fprintf(stderr, “ERROR: Read wrong number of bytes\n”);
error_count++;
}
for (j = 0; j < strlen(test_str); j++) {
if (test_str[j] != fixedbuf[j]) {
fprintf(stderr, “ERROR: Wrong byte in %s at position %d (%d,%d)\n”,
names[i], j, fixedbuf[j], test_str[j]);
error_count++;
break;
}
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
}
for (i = 0; i < max; i++) {
sfs_remove(names[i]);
}
if (sfs_getnextfilename(filename)) {
fprintf(stderr, “ERROR: should be empty dir\n”);
error_count++;
}
fprintf(stderr, “Test program exiting with %d errors\n”, error_count);
return (error_count);
}
Solution
constants.h
/*
* constants.h
*
* Created on: Nov 17, 2017
* Author: thanh
*/
#ifndef CONSTANTS_H_
#define CONSTANTS_H_
#include <stddef.h>
#define FILE_NAME_LENGTH 16
#define TOTAL_FILE_NAME_LENGTH 20
#define FILE_EXTENSION_LENGTH 3
#define I_NODE_COUNT 100
#define FILE_DESCRIPTOR_TABLE_SIZE 16
#define BLOCKS_PER_I_NODE 12
// Constants related to disk stuff
#define SB_MAGIC 0xAABB0005
#define DISK_BLOCK_SIZE 512
#define DISK_BLOCK_COUNT 2048
#define FILE_SYSTEM_NAME “sfs_disk.disk”
// Disk indices of structures
#define SUPER_BLOCK_INDEX 0 // 1 block large
#define I_NODE_TABLE_BLOCK_INDEX 1 // 16 blocks large
#define DIRECTORIES_BLOCK_INDEX 17 // 8 blocks large
#define FREE_BITMAP_BLOCK_INDEX 25 // 4 bytes large
#define DATA_BLOCK_TABLE_INDEX 30
/*
* Dynamic
*/
static int const INDIRECT_BLOCK_POINTER_SIZE = DISK_BLOCK_SIZE / sizeof(int);
int bytesToBlockCount(size_t bytes) {
int output = bytes / DISK_BLOCK_SIZE;
if (bytes % DISK_BLOCK_SIZE != 0) {
output++;
}
return output;
}
#endif /* CONSTANTS_H_ */
disk_emu.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>
#include “disk_emu.h”
FILE* fp = NULL;
double L, p;
double r;
int BLOCK_SIZE, MAX_BLOCK, MAX_RETRY, lru;
/*———————————————————-*/
/*Close the disk file filled when you don’t need it anymore. */
/*———————————————————-*/
int close_disk()
{
if(NULL != fp)
{
fclose(fp);
}
return 0;
}
/*—————————————*/
/*Initializes a disk file filled with 0’s*/
/*—————————————*/
int init_fresh_disk(char *filename, int block_size, int num_blocks)
{
int i, j;
/*Set up latency at 0.02 second*/
L = 00000.f;
/*Set up failure at 10%*/
p = -1.f;
/*Set up max retry attempts after failure to 3*/
MAX_RETRY = 3;
BLOCK_SIZE = block_size;
MAX_BLOCK = num_blocks;
/*Initializes the random number generator*/
srand((unsigned int)(time( 0 )) );
/*Creates a new file*/
fp = fopen (filename, “w+b”);
if (fp == NULL)
{
printf(“Could not create new disk file %s\n\n”, filename);
return -1;
}
/*Fills the file with 0’s to its given size*/
for (i = 0; i < MAX_BLOCK; i++)
{
for (j = 0; j < BLOCK_SIZE; j++)
{
fputc(0, fp);
}
}
return 0;
}
/*—————————-*/
/*Initializes an existing disk*/
/*—————————-*/
int init_disk(char *filename, int block_size, int num_blocks)
{
/*Set up latency at 0.02 second*/
L = 00000.f;
/*Set up failure at 10%*/
p = -1.f;
/*Set up max retry attempts after failure to 3*/
MAX_RETRY = 3;
BLOCK_SIZE = block_size;
MAX_BLOCK = num_blocks;
/*Initializes the random number generator*/
srand((unsigned int)(time( 0 )) );
/*Opens a file*/
fp = fopen (filename, “r+b”);
if (fp == NULL)
{
printf(“Could not open %s\n\n”, filename);
return -1;
}
return 0;
}
/*——————————————————————-*/
/*Reads a series of blocks from the disk into the buffer */
/*——————————————————————-*/
int read_blocks(int start_address, int nblocks, void *buffer)
{
int i, j, e, s;
e = 0;
s = 0;
/*Sets up a temporary buffer*/
void* blockRead = (void*) malloc(BLOCK_SIZE);
/*Checks that the data requested is within the range of addresses of the disk*/
if (start_address + nblocks > MAX_BLOCK)
{
printf(“out of bound error %d\n”, start_address);
return -1;
}
/*Goto the data requested from the disk*/
fseek(fp, start_address * BLOCK_SIZE, SEEK_SET);
/*For every block requested*/
for (i = 0; i < nblocks; ++i)
{
/*Pause until the latency duration is elapsed*/
// usleep(L);
s++;
fread(blockRead, BLOCK_SIZE, 1, fp);
for (j = 0; j < BLOCK_SIZE; j++)
{
memcpy(buffer+(i*BLOCK_SIZE), blockRead, BLOCK_SIZE);
}
}
free(blockRead);
/*If no failure return the number of blocks read, else return the negative number of failures*/
if (e == 0)
return s;
else
return e;
}
/*——————————————————————*/
/*Writes a series of blocks to the disk from the buffer */
/*——————————————————————*/
int write_blocks(int start_address, int nblocks, void *buffer)
{
int i, e, s;
e = 0;
s = 0;
void* blockWrite = (void*) malloc(BLOCK_SIZE);
/*Checks that the data requested is within the range of addresses of the disk*/
if (start_address + nblocks > MAX_BLOCK)
{
printf(“out of bound error\n”);
return -1;
}
/*Goto where the data is to be written on the disk*/
fseek(fp, start_address * BLOCK_SIZE, SEEK_SET);
/*For every block requested*/
for (i = 0; i < nblocks; ++i)
{
/*Pause until the latency duration is elapsed*/
usleep(L);
memcpy(blockWrite, buffer+(i*BLOCK_SIZE), BLOCK_SIZE);
fwrite(blockWrite, BLOCK_SIZE, 1, fp);
fflush(fp);
s++;
}
free(blockWrite);
/*If no failure return the number of blocks written, else return the negative number of failures*/
if (e == 0)
return s;
else
return e;
}
disk_emu.h
int init_fresh_disk(char *filename, int block_size, int num_blocks);
int init_disk(char *filename, int block_size, int num_blocks);
int read_blocks(int start_address, int nblocks, void *buffer);
int write_blocks(int start_address, int nblocks, void *buffer);
int close_disk();
fuse_wrappers.c
#define FUSE_USE_VERSION 30
#include <fuse.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <dirent.h>
#include <errno.h>
#include <sys/time.h>
#include “disk_emu.h”
#include “sfs_api.h”
static int fuse_getattr(const char *path, struct stat *stbuf)
{
int res = 0;
int size;
memset(stbuf, 0, sizeof(struct stat));
if (strcmp(path, “/”) == 0) {
stbuf->st_mode = S_IFDIR | 0755;
stbuf->st_nlink = 2;
} else if((size = sfs_getfilesize(path)) != -1) {
stbuf->st_mode = S_IFREG | 0666;
stbuf->st_nlink = 1;
stbuf->st_size = size;
} else
res = -ENOENT;
return res;
}
static int fuse_readdir(const char *path, void *buf, fuse_fill_dir_t filler,
off_t offset, struct fuse_file_info *fi)
{
char file_name[MAXFILENAME];
if (strcmp(path, “/”) != 0)
return -ENOENT;
filler(buf, “.”, NULL, 0);
filler(buf, “..”, NULL, 0);
while(sfs_getnextfilename(file_name)) {
filler(buf, &file_name[1], NULL, 0);
}
return 0;
}
static int fuse_unlink(const char *path)
{
int res;
char filename[MAXFILENAME];
strcpy(filename, path);
res = sfs_remove(filename);
if (res == -1)
return -errno;
return 0;
}
static int fuse_open(const char *path, struct fuse_file_info *fi)
{
int res;
char filename[MAXFILENAME];
strcpy(filename, path);
res = sfs_fopen(filename);
if (res == -1)
return -errno;
sfs_fclose(res);
return 0;
}
static int fuse_read(const char *path, char *buf, size_t size, off_t offset,
struct fuse_file_info *fi)
{
int fd;
int res;
char filename[MAXFILENAME];
strcpy(filename, path);
fd = sfs_fopen(filename);
if (fd == -1)
return -errno;
if(sfs_fseek(fd, offset) == -1)
return -errno;
res = sfs_fread(fd, buf, size);
if (res == -1)
return -errno;
sfs_fclose(fd);
return res;
}
static int fuse_write(const char *path, const char *buf, size_t size,
off_t offset, struct fuse_file_info *fi)
{
int fd;
int res;
char filename[MAXFILENAME];
strcpy(filename, path);
fd = sfs_fopen(filename);
if (fd == -1)
return -errno;
if(sfs_fseek(fd, offset) == -1)
return -errno;
res = sfs_fwrite(fd, buf, size);
if (res == -1)
return -errno;
sfs_fclose(fd);
return res;
}
static int fuse_truncate(const char *path, off_t size)
{
char filename[MAXFILENAME];
int fd;
strcpy(filename, path);
fd = sfs_remove(filename);
if (fd == -1)
return -errno;
fd = sfs_fopen(filename);
sfs_fclose(fd);
return 0;
}
static int fuse_access(const char *path, int mask)
{
return 0;
}
static int fuse_mknod(const char *path, mode_t mode, dev_t rdev)
{
return 0;
}
static int fuse_create (const char *path, mode_t mode, struct fuse_file_info *fp)
{
char filename[MAXFILENAME];
int fd;
strcpy(filename, path);
fd = sfs_fopen(filename);
sfs_fclose(fd);
return 0;
}
static struct fuse_operations xmp_oper = {
.getattr = fuse_getattr,
.readdir = fuse_readdir,
.mknod = fuse_mknod,
.unlink = fuse_unlink,
.truncate = fuse_truncate,
.open = fuse_open,
.read = fuse_read,
.write = fuse_write,
.access = fuse_access,
.create = fuse_create,
};
int main(int argc, char *argv[])
{
mksfs(1);
return fuse_main(argc, argv, &xmp_oper, NULL);
}
sfs_api.c
#include “sfs_api.h”
//#include “bitmap.h”
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fuse.h>
#include <strings.h>
#include “disk_emu.h”
#include “constants.h”
#include “data_structure/super_block.h”
#include “data_structure/file_descriptor_table.h”
#include “data_structure/free_bitmap.h”
#include “data_structure/directory_cache.h”
#include “data_structure/indirect_block_pointer.h”
#include “data_structure/i_node_table.h”
#include “helpers/disk_access.h”
#define NUM_BLOCKS 1024 //maximum number of data blocks on the disk.
#define BITMAP_ROW_SIZE (NUM_BLOCKS/8) // this essentially mimcs the number of rows we have in the bitmap. we will have 128 rows.
/* macros */
#define FREE_BIT(_data, _which_bit) \
_data = _data | (1 << _which_bit)
#define USE_BIT(_data, _which_bit) \
_data = _data & ~(1 << _which_bit)
//initialize all bits to high
uint8_t free_bit_map[BITMAP_ROW_SIZE] = { [0 … BITMAP_ROW_SIZE – 1] = UINT8_MAX };
DirectoryCache* directoryCache = NULL;
FileDescriptorTable* fileDescriptorTable = NULL;
INodeTable* iNodeTable = NULL;
FreeBitMap* freeBitMap = NULL;
void allocate_necessary_memory()
{
if (!fileDescriptorTable)
{
fileDescriptorTable = malloc(sizeof(FileDescriptorTable));
}
memset(fileDescriptorTable, ‘\0’, sizeof(FileDescriptorTable));
if (!directoryCache)
{
directoryCache = malloc(sizeof(DirectoryCache));
}
memset(directoryCache, ‘\0’, sizeof(DirectoryCache));
if (!iNodeTable)
{
iNodeTable = malloc(sizeof(INodeTable));
}
memset(iNodeTable, ‘\0’, sizeof(INodeTable));
if (!freeBitMap)
{
freeBitMap = malloc(sizeof(FreeBitMap));
}
memset(freeBitMap, ‘\0’, sizeof(FreeBitMap));
// Make sure the iNodeTable is reset
INodeTable_reset(iNodeTable);
}
/**
* creates the file system
*/
void mksfs(int fresh)
{
// Allocate the local file system
allocate_necessary_memory();
//Implement mksfs here
if (fresh)
{
// We need to construct the file system from scratch
// Delete the disk file, if it exists
remove(FILE_SYSTEM_NAME);
// Initialize a new fresh disk
init_fresh_disk(FILE_SYSTEM_NAME, DISK_BLOCK_SIZE, DISK_BLOCK_COUNT);
// Write superblock to disk
SuperBlock sb = { };
sb.magic = SB_MAGIC;
sb.block_size = 512;
sb.file_system_size = DISK_BLOCK_COUNT;
sb.i_node_table_length = I_NODE_COUNT;
sb.root_directory_i_node = 0;
write_blocks(SUPER_BLOCK_INDEX, 1, &sb);
// Write the rest of the stuff to disk
save_local_file_system_to_disk(freeBitMap, iNodeTable, directoryCache);
} else
{
// File system already exists on disk, so we need to load it from the disk.
// Initialize an existing disk
init_disk(FILE_SYSTEM_NAME, DISK_BLOCK_SIZE, DISK_BLOCK_COUNT);
// Copy iNodes into local memory
load_i_node_cache_from_disk(iNodeTable);
// Copy directory cache into memory
load_directory_cache_from_disk(directoryCache);
// Copy the free bit map into memory
load_free_bitmap_from_disk(freeBitMap);
}
return;
}
/**
* copies the name of the next file in the directory into fname
* and returns non zero if there is a new file. Once all the files
* have been returned, this function returns 0.
*/
int sfs_getnextfilename(char *fname)
{
int index;
for (index = directoryCache->readIndex; index < I_NODE_COUNT; index++)
{
if (!DirectoryCache_isOpen(*directoryCache, index))
{
// Copy the
strcpy(fname, directoryCache->directory[index].name);
// Increase the index for next time
directoryCache->readIndex++;
return 1;
}
}
directoryCache->readIndex = 0;
return 0;
}
/**
* get the size of the given file
*/
int sfs_getfilesize(const char* path)
{
// Loop through the directory cache and check the names
int i;
for (i = 0; i < I_NODE_COUNT; i++)
{
if (strcmp(directoryCache->directory[i].name, path) == 0)
{
// It’s the same name, so figure out the file size
int iNodeIndex = directoryCache->directory[i].i_node_index;
return iNodeTable->i_node[iNodeIndex].size;
}
}
// There is none, so return error
return -1;
}
/**
* opens the given file
*/
int sfs_fopen(char *name)
{
// Check that the name is valid
if (isFileNameValid(name) == -1)
{
return -1;
}
int directoryIndex = DirectoryCache_getNameIndex(directoryCache, name);
if (directoryIndex == -1)
{
if (INodeTable_getOpenIndex(*iNodeTable) == -1 || FileDescriptorTable_getOpenIndex(*fileDescriptorTable) == -1)
{
// There are no open iNodes, so we can’t procede!
printf(“INodeTable or FileDescriptorTable full!\n”);
return -1;
}
// The directory doesn’t exist, so we will create it
directoryIndex = DirectoryCache_getOpenIndex(*directoryCache);
if (directoryIndex == -1)
{
printf(“Directory index full!\n”);
// No more directories
return -1;
}
DirectoryCache_markClosed(directoryCache, directoryIndex);
// Copy the name
strcpy(directoryCache->directory[directoryIndex].name, name);
directoryCache->directory[directoryIndex].i_node_index = -1;
}
// Configure the iNode if Necessary
int iNodeIndex = directoryCache->directory[directoryIndex].i_node_index;
if (iNodeIndex == -1)
{
iNodeIndex = INodeTable_getOpenIndex(*iNodeTable);
if (iNodeIndex == -1)
{
// No more iNodes
return -1;
}
INodeTable_markClosed(iNodeTable, iNodeIndex);
INode_new(&iNodeTable->i_node[iNodeIndex]);
directoryCache->directory[directoryIndex].i_node_index = iNodeIndex;
}
// Configure the FD table
int fdIndex = FileDescriptorTable_getIndexOfInode(*fileDescriptorTable, iNodeIndex);
if (fdIndex == -1)
{
// Get a new fd table index
fdIndex = FileDescriptorTable_getOpenIndex(*fileDescriptorTable);
if (fdIndex == -1)
{
printf(“FD index full!\n”);
// No more file descriptors
return -1;
}
FileDescriptorTable_markInUse(fileDescriptorTable, fdIndex);
// Point to the iNode
fileDescriptorTable->fd[fdIndex].i_node_number = iNodeIndex;
// Open in append mode
fileDescriptorTable->fd[fdIndex].read_write_pointer = iNodeTable->i_node[iNodeIndex].size;
} else
{
// If we don’t do this, then the 0 index gets messed up!
FileDescriptorTable_markInUse(fileDescriptorTable, fdIndex);
}
return fdIndex;
}
/**
* closes the given file
*/
int sfs_fclose(int fileID)
{
if (fileID < 0)
{
printf(“Invalid FileID!\n”);
return -1;
}
// Error if already closed
if (FileDescriptorTable_isNotInUse(*fileDescriptorTable, fileID))
{
return -1;
}
// Mark spot empty on fd table
FileDescriptorTable_markNotInUse(fileDescriptorTable, fileID);
// Remove data from FD table
fileDescriptorTable->fd[fileID].read_write_pointer = 0;
fileDescriptorTable->fd[fileID].i_node_number = 0;
// Success!
return 0;
}
/**
* read characters from disk into buf
*/
int sfs_fread(int fileID, char *buf, int length)
{
// // Return if file is closed
if (FileDescriptorTable_isNotInUse(*fileDescriptorTable, fileID))
{
printf(“File %d is closed. Cannot read…\n”, fileID);
return 0;
}
FileDescriptor* fd = &fileDescriptorTable->fd[fileID];
INode iNode = iNodeTable->i_node[fd->i_node_number];
// Output is the total data that we’have read…
int output = 0;
int amountLeftToRead;
if ((fd->read_write_pointer + length + 1) > iNode.size)
{
// Read what’s left of the file
amountLeftToRead = iNode.size – fd->read_write_pointer;
} else
{
// Read the whole file
amountLeftToRead = length;
}
// We might have to access the indirect block
IndirectBlockPointer indirectBlockPointer = { };
// Make sure this block is empty
if (iNode.ind_pointer > -1)
{
read_data_block(iNode.ind_pointer, &indirectBlockPointer);
}
// Allocate an empty block
void* data = malloc(DISK_BLOCK_SIZE);
memset(data, ‘\0’, DISK_BLOCK_SIZE);
while (amountLeftToRead > 0)
{
int currentBlockIndex = fd->read_write_pointer / DISK_BLOCK_SIZE;
int startingIndexOfBlock = fd->read_write_pointer % DISK_BLOCK_SIZE;
int amountToRead;
if (amountLeftToRead > (DISK_BLOCK_SIZE – startingIndexOfBlock))
{
amountToRead = DISK_BLOCK_SIZE – startingIndexOfBlock;
} else
{
amountToRead = amountLeftToRead;
}
// Empty the data buffer
memset(data, ‘\0’, DISK_BLOCK_SIZE);
// Read data from the correct source
if (isIndexInIndirectBlock(currentBlockIndex))
{
read_data_block(indirectBlockPointer.block[indirectBlockIndex(currentBlockIndex)], data);
} else
{
// Read direct from iNode
read_data_block(iNode.pointer[currentBlockIndex], data);
}
// Copy the desired amount of memory into the output buffer
memcpy(buf, data + startingIndexOfBlock, (size_t) amountToRead);
// Advance the rw pointer
fd->read_write_pointer += amountToRead;
// Record how much has been read and how much less there is to read now
output += amountToRead;
amountLeftToRead -= amountToRead;
// Increment the buffer for the next loop
buf += amountToRead;
}
// Free the data block
free(data);
return output;
}
/**
* write buf characters into disk
*/
int sfs_fwrite(int fileID, const char *buf, int length)
{
// Get the iNode of the desired file
FileDescriptor* fileDescriptor = &fileDescriptorTable->fd[fileID];
INode* fileINode = &iNodeTable->i_node[fileDescriptor->i_node_number];
// Keep track of how much we have written, and how much we must write
int totalBytesWritten = 0;
int totalAmountLeftToWrite = length;
// We might have to access the indirect block
IndirectBlockPointer indirectBlock = { };
// Create an empty buffer
void* newBuffer = malloc(DISK_BLOCK_SIZE);
memset(newBuffer, ‘\0’, DISK_BLOCK_SIZE);
/*
* Set up the indirect block
*/
// Initialize indirect buffer if necessary
if (totalAmountLeftToWrite > 0 && fileINode->ind_pointer <= 0)
{
// Create an index for the ind pointer
fileINode->ind_pointer = FreeBitMap_getFreeBit(*freeBitMap);
if (fileINode->ind_pointer < 0)
{
// No space left!
return -1;
}
// mark the bit unfree
FreeBitMap_markBitUnfree(freeBitMap, fileINode->ind_pointer);
} else
{
// There already is an ind pointer, so we load from disk
read_data_block(fileINode->ind_pointer, &indirectBlock);
}
// Begin write
while (totalAmountLeftToWrite > 0)
{
// Empty the contents of newBuffer
memset(newBuffer, ‘\0’, DISK_BLOCK_SIZE);
int currentBlockIndex = fileDescriptor->read_write_pointer / DISK_BLOCK_SIZE;
int startingIndexOfBlock = fileDescriptor->read_write_pointer % DISK_BLOCK_SIZE;
int amountToWrite;
if (totalAmountLeftToWrite > (DISK_BLOCK_SIZE – startingIndexOfBlock))
{
amountToWrite = DISK_BLOCK_SIZE – startingIndexOfBlock;
} else
{
amountToWrite = totalAmountLeftToWrite;
}
/*
* Handle getting the disk index for the data
*/
int blockIsNew = 0;
int diskIndex;
if (isIndexInIndirectBlock(currentBlockIndex))
{
// We are using the indirect block
diskIndex = indirectBlock.block[indirectBlockIndex(currentBlockIndex)];
if (diskIndex <= 0)
{
blockIsNew = 1;
// Get a new bitmap index
diskIndex = FreeBitMap_getFreeBit(*freeBitMap);
if (diskIndex == -1)
{
// Disk is full!
break;
}
// Mark it unfree
FreeBitMap_markBitUnfree(freeBitMap, diskIndex);
// Save it to the indirect block
indirectBlock.block[indirectBlockIndex(currentBlockIndex)] = diskIndex;
}
} else
{
// We are using the iNode Directly
diskIndex = fileINode->pointer[currentBlockIndex];
if (diskIndex < 0)
{
blockIsNew = 1;
// Get a new bitmap index
diskIndex = FreeBitMap_getFreeBit(*freeBitMap);
if (diskIndex == -1)
{
// Disk is full!
break;
}
// Mark it unfree
FreeBitMap_markBitUnfree(freeBitMap, diskIndex);
fileINode->pointer[currentBlockIndex] = diskIndex;
}
}
// If the block is already partially full, then we need to load the old data
if (!blockIsNew)
{
read_data_block(diskIndex, newBuffer);
}
// Copy the desired amount of data onto it
memcpy(newBuffer + startingIndexOfBlock, buf, (size_t) amountToWrite);
write_data_block(diskIndex, newBuffer);
// Save how much we have written to the file pointer
fileDescriptor->read_write_pointer += amountToWrite;
// Track how much we have written. This will be returned to user
totalBytesWritten += amountToWrite;
totalAmountLeftToWrite -= amountToWrite;
// Increment the buffer
buf += amountToWrite;
// Record file size change
if (fileDescriptor->read_write_pointer > fileINode->size)
{
fileINode->size = fileDescriptor->read_write_pointer;
}
}
// Write the data block to disk
if (fileINode->ind_pointer > -1)
{
write_data_block(fileINode->ind_pointer, &indirectBlock);
}
// Free the new buffer
free(newBuffer);
// Save our cached version of the file system
save_local_file_system_to_disk(freeBitMap, iNodeTable, directoryCache);
return totalBytesWritten;
}
/**
* seek to the location from beginning
*/
int sfs_fseek(int fileID, int loc)
{
fileDescriptorTable->fd[fileID].read_write_pointer = loc;
return 0;
}
/**
* removes a file from the filesystem
*/
int sfs_remove(char *file)
{
// First, grab the iNode and delete it’s data blocks from memory
int directoryIndex = DirectoryCache_getNameIndex(directoryCache, file);
if (directoryIndex == -1)
{
// Can’t delete a non-existing file
return -1;
}
int iNodeIndex = directoryCache->directory[directoryIndex].i_node_index;
INode iNode = iNodeTable->i_node[iNodeIndex];
int i;
for (i = 0; i < BLOCKS_PER_I_NODE; i++)
{
if (iNode.pointer[i] > -1)
{
// Erase the block from the disk
erase_data_block(iNode.pointer[i]);
// Mark block free
FreeBitMap_markBitFree(freeBitMap, iNode.pointer[i]);
}
}
if (iNode.ind_pointer > -1)
{
// Delete the blocks from the indirect pointer
IndirectBlockPointer indirectPointer = { };
read_data_block(iNode.ind_pointer, &indirectPointer);
// Delete the indirectly pointed blocks
for (i = 0; i < INDIRECT_BLOCK_POINTER_SIZE; i++)
{
if (indirectPointer.block[i] > 0 && indirectPointer.block[i] < DISK_BLOCK_COUNT)
{
// Erase the block from the disk
erase_data_block(indirectPointer.block[i]);
// Mark block free
FreeBitMap_markBitFree(freeBitMap, indirectPointer.block[i]);
}
}
}
// Delete the iNode
INodeTable_deleteINode(iNodeTable, iNodeIndex);
// Delete the directory object
DirectoryCache_deleteIndex(directoryCache, directoryIndex);
// Save our cached version of the file system
save_local_file_system_to_disk(freeBitMap, iNodeTable, directoryCache);
return 0;
}
sfs_api.h
#ifndef _INCLUDE_SFS_API_H_
#define _INCLUDE_SFS_API_H_
#include <stdint.h>
#define MAXFILENAME 20
#define MAX_EXTENSION_NAME 3
void mksfs(int fresh);
int sfs_getnextfilename(char *fname);
int sfs_getfilesize(const char* path);
int sfs_fopen(char *name);
int sfs_fclose(int fileID);
int sfs_fread(int fileID, char *buf, int length);
int sfs_fwrite(int fileID, const char *buf, int length);
int sfs_fseek(int fileID, int loc);
int sfs_remove(char *file);
#endif //_INCLUDE_SFS_API_H_
sfs_test.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “sfs_api.h”
/* The maximum file name length. We assume that filenames can contain
* upper-case letters and periods (‘.’) characters. Feel free to
* change this if your implementation differs.
*/
#define MAX_FNAME_LENGTH 20 /* Assume at most 20 characters (16.3) */
/* The maximum number of files to attempt to open or create. NOTE: we
* do not _require_ that you support this many files. This is just to
* test the behavior of your code.
*/
#define MAX_FD 100
/* The maximum number of bytes we’ll try to write to a file. If you
* support much shorter or larger files for some reason, feel free to
* reduce this value.
*/
#define MAX_BYTES 30000 /* Maximum file size I’ll try to create */
#define MIN_BYTES 10000 /* Minimum file size */
/* Just a random test string.
*/
static char test_str[] = “The quick brown fox jumps over the lazy dog.\n”;
/* rand_name() – return a randomly-generated, but legal, file name.
*
* This function creates a filename of the form xxxxxxxx.xxx, where
* each ‘x’ is a random upper-case letter (A-Z). Feel free to modify
* this function if your implementation requires shorter filenames, or
* supports longer or different file name conventions.
*
* The return value is a pointer to the new string, which may be
* released by a call to free() when you are done using the string.
*/
char *rand_name()
{
char fname[MAX_FNAME_LENGTH];
int i;
for (i = 0; i < MAX_FNAME_LENGTH; i++) {
if (i != 16) {
fname[i] = ‘A’ + (rand() % 26);
}
else {
fname[i] = ‘.’;
}
}
fname[i] = ‘\0’;
return (strdup(fname));
}
/* The main testing program
*/
int
main(int argc, char **argv)
{
int i, j, k;
int chunksize;
int readsize;
char *buffer;
char fixedbuf[1024];
int fds[MAX_FD];
char *names[MAX_FD];
int filesize[MAX_FD];
int nopen; /* Number of files simultaneously open */
int ncreate; /* Number of files created in directory */
int error_count = 0;
int tmp;
mksfs(1); /* Initialize the file system. */
/* First we open two files and attempt to write data to them.
*/
for (i = 0; i < 2; i++) {
names[i] = rand_name();
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
fprintf(stderr, “ERROR: creating first test file %s\n”, names[i]);
error_count++;
}
tmp = sfs_fopen(names[i]);
if (tmp >= 0 && tmp != fds[i]) {
fprintf(stderr, “ERROR: file %s was opened twice\n”, names[i]);
error_count++;
}
filesize[i] = (rand() % (MAX_BYTES-MIN_BYTES)) + MIN_BYTES;
}
for (i = 0; i < 2; i++) {
for (j = i + 1; j < 2; j++) {
if (fds[i] == fds[j]) {
fprintf(stderr, “Warning: the file descriptors probably shouldn’t be the same?\n”);
}
}
}
printf(“Two files created with zero length:\n”);
for (i = 0; i < 2; i++) {
for (j = 0; j < filesize[i]; j += chunksize) {
if ((filesize[i] – j) < 10) {
chunksize = filesize[i] – j;
}
else {
chunksize = (rand() % (filesize[i] – j)) + 1;
}
if ((buffer = malloc(chunksize)) == NULL) {
fprintf(stderr, “ABORT: Out of memory!\n”);
exit(-1);
}
for (k = 0; k < chunksize; k++) {
buffer[k] = (char) (j+k);
}
tmp = sfs_fwrite(fds[i], buffer, chunksize);
if (tmp != chunksize) {
fprintf(stderr, “ERROR: Tried to write %d bytes, but wrote %d\n”,
chunksize, tmp);
error_count++;
}
free(buffer);
}
}
if (sfs_fclose(fds[1]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[1]);
error_count++;
}
/* Sneaky attempt to close already closed file handle. */
if (sfs_fclose(fds[1]) == 0) {
fprintf(stderr, “ERROR: close of stale handle %d succeeded\n”, fds[1]);
error_count++;
}
printf(“File %s now has length %d and %s now has length %d:\n”,
names[0], filesize[0], names[1], filesize[1]);
/* Just to be cruel – attempt to read from a closed file handle.
*/
if (sfs_fread(fds[1], fixedbuf, sizeof(fixedbuf)) > 0) {
fprintf(stderr, “ERROR: read from a closed file handle?\n”);
error_count++;
}
fds[1] = sfs_fopen(names[1]);
sfs_fseek(fds[0], 0);
sfs_fseek(fds[1], 0);
for (i = 0; i < 2; i++) {
for (j = 0; j < filesize[i]; j += chunksize) {
if ((filesize[i] – j) < 10) {
chunksize = filesize[i] – j;
}
else {
chunksize = (rand() % (filesize[i] – j)) + 1;
}
if ((buffer = malloc(chunksize)) == NULL) {
fprintf(stderr, “ABORT: Out of memory!\n”);
exit(-1);
}
readsize = sfs_fread(fds[i], buffer, chunksize);
if (readsize != chunksize) {
fprintf(stderr, “ERROR: Requested %d bytes, read %d\n”, chunksize, readsize);
readsize = chunksize;
}
for (k = 0; k < readsize; k++) {
if (buffer[k] != (char)(j+k)) {
fprintf(stderr, “ERROR: data error at offset %d in file %s (%d,%d)\n”,
j+k, names[i], buffer[k], (char)(j+k));
error_count++;
break;
}
}
free(buffer);
}
}
for (i = 0; i < 2; i++) {
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: closing file %s\n”, names[i]);
error_count++;
}
}
/* Now try to close the files. Don’t
* care about the return codes, really, but just want to make sure
* this doesn’t cause a problem.
*/
for (i = 0; i < 2; i++) {
if (sfs_fclose(fds[i]) == 0) {
fprintf(stderr, “Warning: closing already closed file %s\n”, names[i]);
}
}
/* Now just try to open up a bunch of files.
*/
ncreate = 0;
for (i = 0; i < MAX_FD; i++) {
names[i] = rand_name();
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
break;
}
sfs_fclose(fds[i]);
ncreate++;
}
printf(“Created %d files in the root directory\n”, ncreate);
nopen = 0;
for (i = 0; i < ncreate; i++) {
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
break;
}
nopen++;
}
printf(“Simultaneously opened %d files\n”, nopen);
for (i = 0; i < nopen; i++) {
tmp = sfs_fwrite(fds[i], test_str, strlen(test_str));
if (tmp != strlen(test_str)) {
fprintf(stderr, “ERROR: Tried to write %d, returned %d\n”,
(int)strlen(test_str), tmp);
error_count++;
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
/* Re-open in reverse order */
for (i = nopen-1; i >= 0; i–) {
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
fprintf(stderr, “ERROR: can’t re-open file %s\n”, names[i]);
}
}
/* Now test the file contents.
*/
for (i = 0; i < nopen; i++) {
sfs_fseek(fds[i], 0);
}
for (j = 0; j < strlen(test_str); j++) {
for (i = 0; i < nopen; i++) {
char ch;
if (sfs_fread(fds[i], &ch, 1) != 1) {
fprintf(stderr, “ERROR: Failed to read 1 character\n”);
error_count++;
}
if (ch != test_str[j]) {
fprintf(stderr, “ERROR: Read wrong byte from %s at %d (%d,%d)\n”,
names[i], j, ch, test_str[j]);
error_count++;
break;
}
}
}
/* Now close all of the open file handles.
*/
for (i = 0; i < nopen; i++) {
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
/* Now we try to re-initialize the system.
*/
mksfs(0);
for (i = 0; i < nopen; i++) {
fds[i] = sfs_fopen(names[i]);
sfs_fseek(fds[i], 0);
if (fds[i] >= 0) {
readsize = sfs_fread(fds[i], fixedbuf, sizeof(fixedbuf));
if (readsize != strlen(test_str)) {
fprintf(stderr, “ERROR: Read wrong number of bytes\n”);
error_count++;
}
for (j = 0; j < strlen(test_str); j++) {
if (test_str[j] != fixedbuf[j]) {
fprintf(stderr, “ERROR: Wrong byte in %s at %d (%d,%d)\n”,
names[i], j, fixedbuf[j], test_str[j]);
printf(“%d\n”, fixedbuf[1]);
error_count++;
break;
}
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
}
printf(“Trying to fill up the disk with repeated writes to %s.\n”, names[0]);
printf(“(This may take a while).\n”);
/* Now try opening the first file, and just write a huge bunch of junk.
* This is just to try to fill up the disk, to see what happens.
*/
fds[0] = sfs_fopen(names[0]);
if (fds[0] >= 0) {
for (i = 0; i < 100000; i++) {
int x;
if ((i % 100) == 0) {
fprintf(stderr, “%d\r”, i);
}
memset(fixedbuf, (char)i, sizeof(fixedbuf));
x = sfs_fwrite(fds[0], fixedbuf, sizeof(fixedbuf));
if (x != sizeof(fixedbuf)) {
/* Sooner or later, this write should fail. The only thing is that
* it should fail gracefully, without any catastrophic errors.
*/
printf(“Write failed after %d iterations.\n”, i);
printf(“If the emulated disk contains just over %d bytes, this is OK\n”,
(i * (int)sizeof(fixedbuf)));
break;
}
}
sfs_fclose(fds[0]);
}
else {
fprintf(stderr, “ERROR: re-opening file %s\n”, names[0]);
}
/* Now, having filled up the disk, try one more time to read the
* contents of the files we created.
*/
for (i = 0; i < nopen; i++) {
fds[i] = sfs_fopen(names[i]);
sfs_fseek(fds[i], 0);
if (fds[i] >= 0) {
readsize = sfs_fread(fds[i], fixedbuf, sizeof(fixedbuf));
if (readsize < strlen(test_str)) {
fprintf(stderr, “ERROR: Read wrong number of bytes\n”);
error_count++;
}
for (j = 0; j < strlen(test_str); j++) {
if (test_str[j] != fixedbuf[j]) {
fprintf(stderr, “ERROR: Wrong byte in %s at position %d (%d,%d)\n”,
names[i], j, fixedbuf[j], test_str[j]);
error_count++;
break;
}
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
}
fprintf(stderr, “Test program exiting with %d errors\n”, error_count);
return (error_count);
}
sfs_test2.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “sfs_api.h”
/* The maximum file name length. We assume that filenames can contain
* upper-case letters and periods (‘.’) characters. Feel free to
* change this if your implementation differs.
*/
#define MAX_FNAME_LENGTH 20 /* Assume at most 20 characters (16.3) */
/* The maximum number of files to attempt to open or create. NOTE: we
* do not _require_ that you support this many files. This is just to
* test the behavior of your code.
*/
#define MAX_FD 100
/* The maximum number of bytes we’ll try to write to a file. If you
* support much shorter or larger files for some reason, feel free to
* reduce this value.
*/
#define MAX_BYTES 30000 /* Maximum file size I’ll try to create */
#define MIN_BYTES 10000 /* Minimum file size */
/* Just a random test string.
*/
static char test_str[] = “The quick brown fox jumps over the lazy dog.\n”;
/* rand_name() – return a randomly-generated, but legal, file name.
*
* This function creates a filename of the form xxxxxxxx.xxx, where
* each ‘x’ is a random upper-case letter (A-Z). Feel free to modify
* this function if your implementation requires shorter filenames, or
* supports longer or different file name conventions.
*
* The return value is a pointer to the new string, which may be
* released by a call to free() when you are done using the string.
*/
char *rand_name()
{
char fname[MAX_FNAME_LENGTH];
int i;
for (i = 0; i < MAX_FNAME_LENGTH; i++) {
if (i != 16) {
fname[i] = ‘A’ + (rand() % 26);
}
else {
fname[i] = ‘.’;
}
}
fname[i] = ‘\0’;
return (strdup(fname));
}
/* The main testing program
*/
int
main(int argc, char **argv)
{
int i, j, k;
int chunksize;
int readsize;
char *buffer;
char fixedbuf[1024];
int fds[MAX_FD];
char *names[MAX_FD];
int filesize[MAX_FD];
int nopen; /* Number of files simultaneously open */
int ncreate; /* Number of files created in directory */
int error_count = 0;
int tmp;
mksfs(1); /* Initialize the file system. */
/* First we open two files and attempt to write data to them.
*/
{
char fname[MAX_FNAME_LENGTH+10];
int i;
for (i = 0; i < MAX_FNAME_LENGTH+10; i++) {
if (i != 8) {
fname[i] = ‘A’ + (rand() % 26);
}
else {
fname[i] = ‘.’;
}
}
fname[i] = ‘\0’;
int derp = sfs_fopen(fname);
if (derp >= 0) {
fprintf(stderr, “ERROR: creating file with too long name\n”);
error_count++;
}
}
for (i = 0; i < 2; i++) {
names[i] = rand_name();
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
fprintf(stderr, “ERROR: creating first test file %s\n”, names[i]);
error_count++;
}
tmp = sfs_fopen(names[i]);
if (tmp >= 0 && tmp != fds[i]) {
fprintf(stderr, “ERROR: file %s was opened twice\n”, names[i]);
error_count++;
}
filesize[i] = (rand() % (MAX_BYTES-MIN_BYTES)) + MIN_BYTES;
}
for (i = 0; i < 2; i++) {
for (j = i + 1; j < 2; j++) {
if (fds[i] == fds[j]) {
fprintf(stderr, “Warning: the file descriptors probably shouldn’t be the same?\n”);
}
}
}
printf(“Two files created with zero length:\n”);
for (i = 0; i < 2; i++) {
for (j = 0; j < filesize[i]; j += chunksize) {
if ((filesize[i] – j) < 10) {
chunksize = filesize[i] – j;
}
else {
chunksize = (rand() % (filesize[i] – j)) + 1;
}
if ((buffer = malloc(chunksize)) == NULL) {
fprintf(stderr, “ABORT: Out of memory!\n”);
exit(-1);
}
for (k = 0; k < chunksize; k++) {
buffer[k] = (char) (j+k);
}
tmp = sfs_fwrite(fds[i], buffer, chunksize);
if (tmp != chunksize) {
fprintf(stderr, “ERROR: Tried to write %d bytes, but wrote %d\n”,
chunksize, tmp);
error_count++;
}
free(buffer);
}
int tmp = sfs_getfilesize(names[i]);
if (filesize[i] != tmp) {
fprintf(stderr, “ERROR: mismatch file size %d, %d\n”, filesize[i], tmp);
error_count++;
}
}
if (sfs_fclose(fds[1]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[1]);
error_count++;
}
/* Sneaky attempt to close already closed file handle. */
if (sfs_fclose(fds[1]) == 0) {
fprintf(stderr, “ERROR: close of stale handle %d succeeded\n”, fds[1]);
error_count++;
}
printf(“File %s now has length %d and %s now has length %d:\n”,
names[0], filesize[0], names[1], filesize[1]);
/* Just to be cruel – attempt to read from a closed file handle.
*/
if (sfs_fread(fds[1], fixedbuf, sizeof(fixedbuf)) > 0) {
fprintf(stderr, “ERROR: read from a closed file handle?\n”);
error_count++;
}
fds[1] = sfs_fopen(names[1]);
sfs_fseek(fds[0], 0);
sfs_fseek(fds[1], 0);
for (i = 0; i < 2; i++) {
for (j = 0; j < filesize[i]; j += chunksize) {
if ((filesize[i] – j) < 10) {
chunksize = filesize[i] – j;
}
else {
chunksize = (rand() % (filesize[i] – j)) + 1;
}
if ((buffer = malloc(chunksize)) == NULL) {
fprintf(stderr, “ABORT: Out of memory!\n”);
exit(-1);
}
readsize = sfs_fread(fds[i], buffer, chunksize);
if (readsize != chunksize) {
fprintf(stderr, “ERROR: Requested %d bytes, read %d\n”, chunksize, readsize);
readsize = chunksize;
}
for (k = 0; k < readsize; k++) {
if (buffer[k] != (char)(j+k)) {
fprintf(stderr, “ERROR: data error at offset %d in file %s (%d,%d)\n”,
j+k, names[i], buffer[k], (char)(j+k));
error_count++;
break;
}
}
free(buffer);
}
}
for (i = 0; i < 2; i++) {
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: closing file %s\n”, names[i]);
error_count++;
}
}
/* Now try to close the files. Don’t
* care about the return codes, really, but just want to make sure
* this doesn’t cause a problem.
*/
for (i = 0; i < 2; i++) {
if (sfs_fclose(fds[i]) == 0) {
fprintf(stderr, “Warning: closing already closed file %s\n”, names[i]);
}
}
sfs_remove(names[0]);
sfs_remove(names[1]);
/* Now just try to open up a bunch of files.
*/
ncreate = 0;
for (i = 0; i < MAX_FD; i++) {
names[i] = rand_name();
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
break;
}
sfs_fclose(fds[i]);
ncreate++;
}
printf(“Created %d files in the root directory\n”, ncreate);
nopen = 0;
for (i = 0; i < ncreate; i++) {
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
break;
}
nopen++;
}
printf(“Simultaneously opened %d files\n”, nopen);
for (i = 0; i < nopen; i++) {
tmp = sfs_fwrite(fds[i], test_str, strlen(test_str));
if (tmp != strlen(test_str)) {
fprintf(stderr, “ERROR: Tried to write %d, returned %d\n”,
(int)strlen(test_str), tmp);
error_count++;
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
/* Re-open in reverse order */
for (i = nopen-1; i >= 0; i–) {
fds[i] = sfs_fopen(names[i]);
if (fds[i] < 0) {
fprintf(stderr, “ERROR: can’t re-open file %s\n”, names[i]);
}
}
/* Now test the file contents.
*/
for (i = 0; i < nopen; i++) {
sfs_fseek(fds[i], 0);
}
for (j = 0; j < strlen(test_str); j++) {
for (i = 0; i < nopen; i++) {
char ch;
if (sfs_fread(fds[i], &ch, 1) != 1) {
fprintf(stderr, “ERROR: Failed to read 1 character\n”);
error_count++;
}
if (ch != test_str[j]) {
fprintf(stderr, “ERROR: Read wrong byte from %s at %d (%d,%d)\n”,
names[i], j, ch, test_str[j]);
error_count++;
break;
}
}
}
/* Now close all of the open file handles.
*/
for (i = 0; i < nopen; i++) {
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
/* Now we try to re-initialize the system.
*/
mksfs(0);
for (i = 0; i < nopen; i++) {
fds[i] = sfs_fopen(names[i]);
sfs_fseek(fds[i], 0);
if (fds[i] >= 0) {
readsize = sfs_fread(fds[i], fixedbuf, sizeof(fixedbuf));
if (readsize != strlen(test_str)) {
fprintf(stderr, “ERROR: Read wrong number of bytes\n”);
error_count++;
}
for (j = 0; j < strlen(test_str); j++) {
if (test_str[j] != fixedbuf[j]) {
fprintf(stderr, “ERROR: Wrong byte in %s at %d (%d,%d)\n”,
names[i], j, fixedbuf[j], test_str[j]);
printf(“%d\n”, fixedbuf[1]);
error_count++;
break;
}
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
}
printf(“Trying to fill up the disk with repeated writes to %s.\n”, names[0]);
printf(“(This may take a while).\n”);
/* Now try opening the first file, and just write a huge bunch of junk.
* This is just to try to fill up the disk, to see what happens.
*/
fds[0] = sfs_fopen(names[0]);
if (fds[0] >= 0) {
for (i = 0; i < 100000; i++) {
int x;
if ((i % 100) == 0) {
fprintf(stderr, “%d\r”, i);
}
memset(fixedbuf, (char)i, sizeof(fixedbuf));
x = sfs_fwrite(fds[0], fixedbuf, sizeof(fixedbuf));
if (x != sizeof(fixedbuf)) {
/* Sooner or later, this write should fail. The only thing is that
* it should fail gracefully, without any catastrophic errors.
*/
printf(“Write failed after %d iterations.\n”, i);
printf(“If the emulated disk contains just over %d bytes, this is OK\n”,
(i * (int)sizeof(fixedbuf)));
break;
}
}
sfs_fclose(fds[0]);
}
else {
fprintf(stderr, “ERROR: re-opening file %s\n”, names[0]);
}
printf(“Directory listing\n”);
char *filename = (char *)malloc(MAX_FNAME_LENGTH);
int max = 0;
while (sfs_getnextfilename(filename)) {
if (strcmp(filename, names[max]) != 0) {
printf(“ERROR misnamed file %d: %s %s\n”, max, filename, names[max]);
error_count++;
}
max++;
}
/* Now, having filled up the disk, try one more time to read the
* contents of the files we created.
*/
for (i = 0; i < nopen; i++) {
fds[i] = sfs_fopen(names[i]);
sfs_fseek(fds[i], 0);
if (fds[i] >= 0) {
readsize = sfs_fread(fds[i], fixedbuf, sizeof(fixedbuf));
if (readsize < strlen(test_str)) {
fprintf(stderr, “ERROR: Read wrong number of bytes\n”);
error_count++;
}
for (j = 0; j < strlen(test_str); j++) {
if (test_str[j] != fixedbuf[j]) {
fprintf(stderr, “ERROR: Wrong byte in %s at position %d (%d,%d)\n”,
names[i], j, fixedbuf[j], test_str[j]);
error_count++;
break;
}
}
if (sfs_fclose(fds[i]) != 0) {
fprintf(stderr, “ERROR: close of handle %d failed\n”, fds[i]);
error_count++;
}
}
}
for (i = 0; i < max; i++) {
sfs_remove(names[i]);
}
if (sfs_getnextfilename(filename)) {
fprintf(stderr, “ERROR: should be empty dir\n”);
error_count++;
}
fprintf(stderr, “Test program exiting with %d errors\n”, error_count);
return (error_count);
}
directory.h
/*
* directory.h
*
* Created on: Nov 17, 2017
*/
#ifndef DATA_STRUCTURE_DIRECTORY_H_
#define DATA_STRUCTURE_DIRECTORY_H_
#include “../constants.h”
#include “i_node.h”
typedef struct directory
{
char name[TOTAL_FILE_NAME_LENGTH + 1];
int i_node_index;
} Directory;
int isFileNameValid(char* name)
{
// Check main part of name
int i = 0;
while (name[i] != ‘.’)
{
if (i >= FILE_NAME_LENGTH)
{
return -1;
}
i++;
}
// We hit the period, so advance
int j = 0;
while (name[i + 1 + j] != ‘\0’)
{
if (j >= FILE_EXTENSION_LENGTH)
{
return -1;
}
j++;
}
return 1;
}
#endif /* DATA_STRUCTURE_DIRECTORY_H_ */
directory_cache.h
/*
* directory_cache.h
*
* Created on: Nov 17, 2017
*/
#ifndef DATA_STRUCTURE_DIRECTORY_CACHE_H_
#define DATA_STRUCTURE_DIRECTORY_CACHE_H_
#include <string.h>
#include <stdio.h>
#include “directory.h”
typedef struct directory_cache
{
Directory directory[I_NODE_COUNT];
char open[I_NODE_COUNT]; // Char uses fewer bits than int
int readIndex;
} DirectoryCache;
void DirectoryCache_markOpen(DirectoryCache* table, int fileId)
{
table->open[fileId] = 0;
}
void DirectoryCache_markClosed(DirectoryCache* table, int fileId)
{
table->open[fileId] = 1;
}
int DirectoryCache_isOpen(DirectoryCache table, int fileId)
{
return table.open[fileId] == 0;
}
int DirectoryCache_getOpenIndex(DirectoryCache table)
{
int i;
for (i = 0; i < I_NODE_COUNT; i++)
{
if (DirectoryCache_isOpen(table, table.readIndex + i % I_NODE_COUNT))
{
return i;
}
}
// No spot open… error
return -1;
}
void DirectoryCache_deleteIndex(DirectoryCache* cache, int index)
{
// Mark it open
DirectoryCache_markOpen(cache, index);
// Delete the data
cache->directory[index].i_node_index = 0;
strcpy(cache->directory[index].name, “”);
// Advance the readindex if possible
if (cache->readIndex == index)
{
cache->readIndex = (cache->readIndex + 1) % I_NODE_COUNT;
}
}
int DirectoryCache_getNameIndex(DirectoryCache* cache, char *name)
{
int i;
for (i = 0; i < I_NODE_COUNT; i++)
{
if (strcmp(cache->directory[i].name, name) == 0)
{
return i;
}
}
return -1;
}
void DirectoryCache_print(DirectoryCache cache)
{
int i;
for (i = 0; i < I_NODE_COUNT; i++)
{
printf(“Directory: {name: \”%s\”, i_node_index: %d } open: %d\n”, cache.directory[i].name, cache.directory[i].i_node_index,
DirectoryCache_isOpen(cache, i));
}
}
#endif /* DATA_STRUCTURE_DIRECTORY_CACHE_H_ */
file_descriptor.h
/*
* file_descriptor.h
*
* Created on: Nov 17, 2017
*/
#ifndef DATA_STRUCTURE_FILE_DESCRIPTOR_H_
#define DATA_STRUCTURE_FILE_DESCRIPTOR_H_
/*
* i_node_number which inode this entry describes
*read_write_pointer where in the file to start
*/
typedef struct file_descriptor {
int i_node_number; // Corresponds to the file
int read_write_pointer; // A data data number
} FileDescriptor;
#endif /* DATA_STRUCTURE_FILE_DESCRIPTOR_H_ */
file_descriptor_table.h
/*
* file_descriptor_table.h
*
* Created on: Nov 17, 2017
*/
#ifndef DATA_STRUCTURE_FILE_DESCRIPTOR_TABLE_H_
#define DATA_STRUCTURE_FILE_DESCRIPTOR_TABLE_H_
#include <stdio.h>
#include “file_descriptor.h”
#include “../constants.h”
typedef struct file_descriptor_table
{
FileDescriptor fd[FILE_DESCRIPTOR_TABLE_SIZE];
int in_use[FILE_DESCRIPTOR_TABLE_SIZE];
} FileDescriptorTable;
void FileDescriptorTable_markNotInUse(FileDescriptorTable *table, int fileId)
{
table->in_use[fileId] = 0;
}
void FileDescriptorTable_markInUse(FileDescriptorTable *table, int fileId)
{
table->in_use[fileId] = 1;
}
int FileDescriptorTable_isNotInUse(FileDescriptorTable table, int fileId)
{
return table.in_use[fileId] == 0;
}
int FileDescriptorTable_getOpenIndex(FileDescriptorTable table)
{
int i;
for (i = 0; i < FILE_DESCRIPTOR_TABLE_SIZE; i++)
{
if (FileDescriptorTable_isNotInUse(table, i))
{
return i;
}
}
// No spot in_use… error
return -1;
}
int FileDescriptorTable_getIndexOfInode(FileDescriptorTable table, int iNodeIndex)
{
int i;
for (i = 0; i < FILE_DESCRIPTOR_TABLE_SIZE; i++)
{
if (table.fd[i].i_node_number == iNodeIndex)
{
return i;
}
}
// Error
return -1;
}
void FileDescriptorTable_print(FileDescriptorTable table)
{
int i;
for (i = 0; i < FILE_DESCRIPTOR_TABLE_SIZE; i++)
{
printf(“FileDescriptor: {i_node_number: %d, read_write_pointer: %d}, not_in_use: %d\n”, table.fd[i].i_node_number, table.fd[i].read_write_pointer,
FileDescriptorTable_isNotInUse(table, i));
}
}
#endif /* DATA_STRUCTURE_FILE_DESCRIPTOR_TABLE_H_ */
free_bitmap.h
/*
* free_bitmap.h
*
* Created on: Nov 17, 2017
*/
#ifndef DATA_STRUCTURE_FREE_BITMAP_H_
#define DATA_STRUCTURE_FREE_BITMAP_H_
#include <stdio.h>
#include “../constants.h”
typedef struct free_bitmap
{
char bit[DISK_BLOCK_COUNT – DATA_BLOCK_TABLE_INDEX];
} FreeBitMap;
/**
* Mark a particular index as unfree
*/
void FreeBitMap_markBitUnfree(FreeBitMap* map, int index)
{
map->bit[index] = 1;
}
/**
* Mark a particular index as free
*/
void FreeBitMap_markBitFree(FreeBitMap* map, int index)
{
map->bit[index] = 0;
}
/**
* Check if particular index is free
*/
int FreeBitMap_isBitFree(FreeBitMap map, int index)
{
return map.bit[index] == 0;
}
/**
* Get the first free index
*/
int FreeBitMap_getFreeBit(FreeBitMap map)
{
int i;
for (i = 0; i < (DISK_BLOCK_COUNT – DATA_BLOCK_TABLE_INDEX); i++)
{
if (FreeBitMap_isBitFree(map, i))
{
return i;
}
}
return -1;
}
void FreeBitMap_print(FreeBitMap bitMap)
{
printf(“Free Bitmap {\n”);
int i;
for (i = 0; i < (DISK_BLOCK_COUNT – DATA_BLOCK_TABLE_INDEX); i++)
{
printf(“(%d, free: %d),\n”, i, FreeBitMap_isBitFree(bitMap, i));
}
printf(“}\n”);
}
#endif /* DATA_STRUCTURE_FREE_BITMAP_H_ */
i_node.h
/*
* i_node.h
*
* Created on: Nov 17, 2017
*/
#ifndef DATA_STRUCTURE_I_NODE_H_
#define DATA_STRUCTURE_I_NODE_H_
#include <stdio.h>
#include “../constants.h”
typedef struct i_node
{
int mode;
int link_cnt;
int uid;
int gid;
int size;
int ind_pointer;
int pointer[BLOCKS_PER_I_NODE];
} INode;
void INode_copy(INode* dest, INode* source)
{
// Copy all the data
dest->size = source->size;
dest->gid = source->gid;
dest->uid = source->uid;
dest->ind_pointer = source->ind_pointer;
dest->link_cnt = source->link_cnt;
dest->mode = source->mode;
// Copy the data pointers
int j;
for (j = 0; j < BLOCKS_PER_I_NODE; j++)
{
dest->pointer[j] = source->pointer[j];
}
}
void INode_new(INode* iNode)
{
iNode->size = 0;
iNode->gid = 0;
iNode->uid = 0;
iNode->ind_pointer = -1; // Initialize to -1 so that we know that there isn’t one
iNode->link_cnt = 0;
iNode->mode = 0;
int j;
for (j = 0; j < BLOCKS_PER_I_NODE; j++)
{
iNode->pointer[j] = -1;
}
}
void INode_print(INode iNode)
{
printf(“INode {\n”);
printf(” mode: %d\n”, iNode.mode);
printf(” link_cnt: %d\n”, iNode.link_cnt);
printf(” uid: %d\n”, iNode.uid);
printf(” gid: %d\n”, iNode.gid);
printf(” size: %d\n”, iNode.size);
printf(” ind_pointer: %d\n”, iNode.ind_pointer);
int i;
for (i = 0; i < BLOCKS_PER_I_NODE; i++)
{
printf(” pointer %d: %d\n”, i, iNode.pointer[i]);
}
printf(“}\n”);
}
#endif /* DATA_STRUCTURE_I_NODE_H_ */
i_node_table.h
/*
* i_node_table.h
*
* Created on: Nov 17, 2017
*/
#ifndef DATA_STRUCTURE_I_NODE_TABLE_H_
#define DATA_STRUCTURE_I_NODE_TABLE_H_
#include “i_node.h”
#include “../constants.h”
typedef struct i_node_table
{
INode i_node[I_NODE_COUNT];
int open[I_NODE_COUNT];
} INodeTable;
void INodeTable_markOpen(INodeTable* table, int fileId)
{
table->open[fileId] = 0;
}
void INodeTable_markClosed(INodeTable* table, int fileId)
{
table->open[fileId] = 1;
}
int INodeTable_isOpen(INodeTable table, int fileId)
{
return table.open[fileId] == 0;
}
int INodeTable_getOpenIndex(INodeTable table)
{
int i;
for (i = 0; i < I_NODE_COUNT; i++)
{
if (INodeTable_isOpen(table, i))
{
return i;
}
}
// No spot open… error
return -1;
}
void INodeTable_deleteINode(INodeTable* table, int index)
{
// Mark the spot open
INodeTable_isOpen(*table, index);
// Clear the data
INode_new(&table->i_node[index]);
}
void INodeTable_reset(INodeTable* table)
{
int i;
for (i = 0; i < I_NODE_COUNT; i++)
{
INodeTable_deleteINode(table, i);
}
}
#endif /* DATA_STRUCTURE_I_NODE_TABLE_H_ */
indirect_block_pointer.h
/*
* indirect_block_pointer.h
*
* Created on: Nov 17, 2017
*/
#ifndef DATA_STRUCTURE_INDIRECT_BLOCK_POINTER_H_
#define DATA_STRUCTURE_INDIRECT_BLOCK_POINTER_H_
#include <stdio.h>
#include “../constants.h”
typedef struct indirect_block_pointer
{
int block[DISK_BLOCK_SIZE / sizeof(int)];
} IndirectBlockPointer;
int indirectBlockIndex(int pointerIndex)
{
return pointerIndex – BLOCKS_PER_I_NODE;
}
int isIndexInIndirectBlock(int pointerIndex)
{
return pointerIndex >= BLOCKS_PER_I_NODE;
}
void IndirectBlockPointer_print(IndirectBlockPointer block)
{
printf(“IdirectBlockPointer {\n”);
int i;
for (i = 0; i < (DISK_BLOCK_SIZE / sizeof(int)); i++)
{
printf(“[%d = %d\n”, i, block.block[i]);
}
printf(“}\n”);
}
#endif /* DATA_STRUCTURE_INDIRECT_BLOCK_POINTER_H_ */
super_block.h
/*
* super_block.h
*
* Created on: Nov 17, 2017
* Author: Tan Nguyen
*/
#ifndef DATA_STRUCTURE_SUPER_BLOCK_H_
#define DATA_STRUCTURE_SUPER_BLOCK_H_
typedef struct super_block
{
int magic;
int block_size;
int file_system_size;
int i_node_table_length;
int root_directory_i_node;
} SuperBlock;
#endif /* DATA_STRUCTURE_SUPER_BLOCK_H_ */
disk_access.h
/*
* disk_access.h
*
* Created on: Nov 17, 2017
* Author: Tan Nguyen
*/
#ifndef HELPERS_DISK_ACCESS_H_
#define HELPERS_DISK_ACCESS_H_
#include <stdlib.h>
#include <string.h>
#include “../data_structure/i_node.h”
#include “../constants.h”
#include “../disk_emu.h”
#include “../data_structure/free_bitmap.h”
#include “../data_structure/i_node_table.h”
#include “../data_structure/directory_cache.h”
void read_data_block(int index, void* buffer)
{
read_blocks(DATA_BLOCK_TABLE_INDEX + index, 1, buffer);
}
void write_data_block(int index, void* buffer)
{
write_blocks(DATA_BLOCK_TABLE_INDEX + index, 1, buffer);
}
/**
* Fill a disk block with empty space.
*/
void erase_data_block(int index)
{
void* empty = malloc(DISK_BLOCK_SIZE);
memset(empty, ‘\0’, DISK_BLOCK_SIZE);
write_data_block(index, empty);
free(empty);
}
/**
* Write arbitrarily large data to the disk from a particulal index
*/
void write_data_blocks(void* data, int startingIndex, size_t size)
{
int numBlocks = bytesToBlockCount(size);
//printf(“Writing %d bytes to %d blocks.\n”, size, numBlocks);
// Make a blank copy of the correct number of blocks
void* dataGoingToDisk = malloc((size_t) numBlocks * DISK_BLOCK_SIZE);
memset(dataGoingToDisk, ‘\0’, (size_t) numBlocks * DISK_BLOCK_SIZE);
// Copy the incoming data to the temp copy
memcpy(dataGoingToDisk, data, size);
// Write the temp copy to the disk
write_blocks(startingIndex, numBlocks, dataGoingToDisk);
// Free the temp copy
free(dataGoingToDisk);
}
void read_data_blocks(void* buffer, size_t size, int diskIndex)
{
int numblocks = bytesToBlockCount(size);
void* temp = malloc((size_t) numblocks * DISK_BLOCK_SIZE);
memset(temp, ‘\0’, (size_t) numblocks * DISK_BLOCK_SIZE);
// Copy the disk block to the temp memory
read_blocks(diskIndex, numblocks, temp);
// Copy the desired amount off of temp to output
memcpy(buffer, temp, size);
free(temp);
}
/**
* Save the free bitmap to disk
*/
void load_free_bitmap_from_disk(FreeBitMap* bitMap)
{
read_data_blocks(bitMap, sizeof(FreeBitMap), FREE_BITMAP_BLOCK_INDEX);
}
void load_i_node_cache_from_disk(INodeTable* iNodeTable)
{
read_data_blocks(iNodeTable, sizeof(INodeTable), I_NODE_TABLE_BLOCK_INDEX);
}
void load_directory_cache_from_disk(DirectoryCache* directoryCache)
{
read_data_blocks(directoryCache, sizeof(DirectoryCache), DIRECTORIES_BLOCK_INDEX);
}
void save_local_file_system_to_disk(FreeBitMap* bitmap, INodeTable* iNodeTable, DirectoryCache* directoryCache1)
{
//printf(“Saving local filesystem to disk.\n”);
write_data_blocks(bitmap, FREE_BITMAP_BLOCK_INDEX, sizeof(FreeBitMap));
write_data_blocks(iNodeTable, I_NODE_TABLE_BLOCK_INDEX, sizeof(INodeTable));
write_data_blocks(directoryCache1, DIRECTORIES_BLOCK_INDEX, sizeof(DirectoryCache));
}
#endif /* HELPERS_DISK_ACCESS_H_ */