Assessment Solution

$35.00

Description

In this assessment, you will implement a simple file system that allows you to manage files and directories in a virtual inmemory disk. The file system is to be based on simplified concepts of a File Allocation Table (FAT). Your implementation will allow the creation of files and directories within this virtual hard disk and the performance of simple read and write operations on files.

Your task is to implement interface functions for creating files and directories and for reading and writing operations. For this assessment, the virtual disk will be simulated by an array of memory blocks, where each block is a fixed array of bytes. Each block has a block number (from 0 to MAXBLOCKS1). The allocation of a new block to a file is recorded in the FAT. The FAT is a table (an array of integers) of size MAXBLOCKS that acts as a kind of block directory for the complete disk content: it contains an entry for each block and records whether this block is allocated to a file or unused. The FAT itself is also stored on this virtual disk at a particular location.

Files may occupy one or more disk blocks and this allocation is noncontiguous any block of the disk may be allocated to a file. A disk usually becomes more fragmented over time, the more files are deleted and added. When a file is opened for read, we want to be able to read the blocks of a file from start to end in the correct order. The FAT records the correct sequence of blocks comprising a file in the form of a “block chain”: the number stored in one array entry in the FAT may be some index of another array entry the next block number in the chain or ENDOFCHAIN (this block is the last block of the file), or UNUSED (block on disk is free). We assume: ENDOFCHAIN == 0 and UNUSED ==1. When reading a file, we first have to look into the FAT to read one block after the other into memory, following such a block chain in the FAT.

For this assessment, we assume that the virtual disk consists of an array of 1024 blocks (MAXBLOCKS),

where each block is an array of 1024 bytes (BLOCKSIZE). A block can be either (a) file data (an array of

1024 bytes), (b) directory data (a set of directory entries, as much as can fit within 1024 bytes), or (c) the FAT itself containing information about used and unused blocks. As there are 1024 disk blocks, the FAT has to have 1024 entries. For this assessment, we assume that a FAT entry is a short integer (2 bytes).

Two files are provided for this assessment: You will find the files filesys.c and filesys.h containing data structures and basic functions you may use in your implementation. The two basic functions that are directly interacting with the virtual disk are writeblock() and readblock(). All other functions (those you have to implement) are using these two functions for reading from and writing to the virtual disk.

The virtual disk has the following layout:

block 0 is reserved and can contain any information about the whole file system on the disk (e.g.

volume name etc.); block 0 is left free, because the number 0 has a special meaning in the FAT (it is ENDOFCHAIN == 0). However, you can put arbitrary information into these first 1024 bytes on your virtual disk, such as the name of the disk etc.

block 1 and 2 will be occupied by the FAT (we need 2 blocks, because each entry is a short integer, occupying 2 bytes of disk space, and with 1024 entries in the FAT it needs 2048 bytes, which are 2 blocks of disk space

block 3 is the root directory: a directory block has special structure, containing a list of directory

entries

The rest of the virtual disk, blocks 4 1023, are either data or directory blocks.

Your task is to extend filesys.c with additional interface functions (as outlined below). Also, implement a test program called shell.c that calls functions you have implemented. The files filesys.h and filesys.c are provided to give you the C structures needed for the implementation. You can also create your own C structures to complete the assessment. Don’t hesitate to extend or change structures in filesys.h, if you see a need for that in order to support your implementation (you may have to add additional parameters to the file descriptor MyFILE to record additional information, e.g. about the location of a file in the file system etc.).

The complete public interface of the file system for this virtual disk is the following (for each assessment

step, you have to implement some of them):

void format()

creates the initial structure on the virtual disk, writing the FAT and the root directory into the

virtual disk

MyFILE * myfopen ( const char * filename, const car * mode ) ;

Opens a file on the virtual disk and manages a buffer for it of size BLOCKSIZE, mode may be

either r for readonly or w for read/write/append (default w)

void myfclose ( MyFILE * stream )

closes the file, writes out any blocks not written to disk

int myfgetc ( MyFILE * stream )

Returns the next byte of the open file, or EOF (EOF == 1)

void myfputc ( int b, MyFILE * stream )

Writes a byte to the file. Depending on the write policy, either writes the disk block containing

the written byte to disk, or waits until block is full

void mymkdir ( const char * path )

this function will create a new directory, using path, e.g. mymkdir (“/first/second/third”) creates directory third” in parent dir second”, which is a subdir of directory first, and first is a sub directory of the root directory

void myrmdir ( const char * path )

this function removes an existing directory, using path, e.g. myrmdir (“/first/second/third”) removes directory third” in parent dir second”, which is a subdir of directory first, and first is a sub directory of the root directory

void mychdir ( const char * path )

this function will change into an existing directory, using path, e.g. mkdir (“/first/second/third”) creates directory third” in parent dir “second”, which is a subdir of directory first, and first is a sub directory of the root directory

void myremove ( const char * path )

this function removes an existing file, using path, e.g. myremove (“/first/second/third/testfile.txt)

char ** mylistdir (const char * path)

this function lists the content of a directory and returns a list of strings, where the last element

is NULL

Assessment Requirements

CGS D3-D1

Task

Implement the function format() to create a structure for the virtual disk. Format has to create the FAT

and the root directory. Write a test program containing the main() function, and call it “shell.c.

Your test program shell.c should perform the following three actions:

call format() to format the virtual disk

transfer the following text into block 0: “CS3026 Operating Systems Assessment

write the virtual disk to a file (call it virtualdiskD3_D1).

Include any header files required, such as filesys.h, in your test program shell.c (do NOT include any .c

files!!).

Use the unix command “hexdump” to see what the file contains: hexdump –C virtualdiskD3_D1.

In the downloaded file CS3026_Assessment.zip, you will find the file “virtualdisk” that shows a layout of the virtual disk as acceptable for CGS D3D1. You must demonstrate that your implementation produces the same or a similar layout (your implementation may differ), with the FAT and entries within the FAT recognizable. It is expected that the hexdump only shows the information written back into the virtual disk and no other clutter. This requires that the virtual disk is properly initialized when formatted().

Additional Information:

Please also read section How to start your Project for additional information and how to implement

the format() function.

Submission for CGS D3D1

In order to achieve at least a D3, your submission must include a make file for building your solution and your solution also must correctly include the required header files. Please describe your implementation in detail in your report: for each statement in function format(), provide an explanation in your report about its purpose. Provide detailed explanations how to run the submission. Provide an explanation

what the result of such an execution is: include a hexdump of the virtual disk into the report and provide

explanations for it.

Submit a test program, called shell.c, as well as filesys.c, filesys.h, a file virtualdiskD3_D1 and a Makefile

that allows your program to be compiled (put files into a directory CGS_D3_D1).

CGS C3-C1

Task

Implement the following interface functions:

myfopen(),

myfputc(),

myfgetc() and

myfclose().

It is assumed that there is only a root directory and that all files are created there.

Extend your test program shell.c with the following steps:

create a file testfile.txt in your virtual disk: call myfopen ( testfile.txt, w ) to open this file

write a text of size 4kb (4096 bytes) to this file, using the function myfputc():

o in shell.c, create a char array of 4 * BLOCKSIZE, fill it with text and then write it to the

virtual file with myfputc()

close the file with myfclose()

write the complete virtual disk to a file virtualdiskC3_C1”

test myfgetc():

o open the file again on your virtual harddisk

o read out its content with myfgetc() (you may read until the function returns EOF) and,

at the same time, print it to the screen

o write the content to a real file on your real hard disk and call it testfileC3_C1_copy.txt

In order to create a recognizable pattern in your hexdump for testfile.txt, you may loop through the alphabet over and over again, until the array of size 4*BLOCKSIZE is filled(remember how a string literal “ABCDEFGHIJKLMNOPQRSTUVWXWZ” can be indexed).

Use the unix command hexdump to check the content of your virtual disk:

o hexdump –C virtualdiskC3_C1

Redirect the output of your shell program into a file traceC3_C1.txt

o ./shell > traceC3_C1.txt

Submission

For a CGS C3, submit shell.c, filesys.c, filesys.h, the files virtualdiskC3_C1, testfileC3_C1_copy.txt, traceC3_C1.txt and a Makefile that allows your program to be compiled. Put files into a separate directory CGS_C3_C1. In order to achieve a CGS C1, the virtual disk should not show any clutter, only the information you write into it, it has to show the block chain in the FAT for the created file and the content of the file, and in your report, you have to provide detailed comments about the implementation of the required functions (explain it by walking the reader through the implemented statements and provide comments for each of them).

Parts missing in your solution may reduce the CGS mark. Try to get with your implementation as far as

possible.

Explanation

When a file is created or opened, a file descriptor has to be created (see filesys.h):

typedef struct filedescriptor {

int pos ; // byte within a block char mode[3] ;

Byte writing ; fatentry_t blockno ; diskblock_t buffer ;

} MyFILE ;

This file descriptor can hold one disk block with “diskblock_t buffer. Read and write operations access this buffer. The attribute “pos” points to the byte in this buffer that is read or written. If read operations go beyond the current buffer content, the next buffer according to the block chain in the FAT has to be loaded. If the buffer becomes full due to write operations, the current buffer has to be written out to disk and a new disk block has to be allocated to the open file this is done by simply finding the next entry in the FAT with value UNUSED and extending the block chain in the FAT. When the file is closed with fclose(), its length has to be written into the directory entry of this file (situated in the root directory, block 3).

Find the FAT (at 0x400) and the block for the root directory in the hexdump (it starts at 0xc00):

00000400 00 00 02 00 00 00 00 00 05 00 06 00 07 00 08 00 |…………….|

00000410 00 00 ff ff ff ff ff ff ff ff ff ff ff ff ff ff |…………….|

00000420 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff |…………….|

*

00000c00 01 00 00 00 01 00 00 00 00 00 00 00 00 00 00 00 |…………….|

00000c10 00 00 00 00 00 00 00 00 00 00 00 00 04 00 74 65 |…………..te|

00000c20 73 74 66 69 6c 65 2e 74 78 74 00 00 00 00 00 00 |stfile.txt……|

00000c30 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |…………….|

As illustrated, the file ‘testfile.txt’ was opened for write on the virtual disk, which created it in the root directory (block no 3, starting at 0xc00), and the content of file ‘testfile.txt’ starts at block no 4. There should be a block chain visible in the FAT table: at 0x400, entry 04 contains 05 00, entry 05 contains 06

00 etc. (please note that the order of bytes is reversed, you see 05 00, and not 00 05). At location 0xc00,

the block of the root directory starts. The first two bytes, set to 01 00’, indicate that this is a dirblock.

Please note: text strings always have a \0 at the end. C functions such a strcpy() etc. will scan a text string as long as they haven’t found the \0’. For example, the parameter mode of function myfopen() is a character array of 3 elements, because it can hold a mode string that can be one or two characters long and has\0 as its last character.

Indicating Endof-File: the last block of a file may not be filled completely. How can we indicate where the file ends? You have to store the length of the file in the directory entry. When using myfgetc (), it has to be calculated whether all bytes of the files have been read by checking the amount of chars read

against the file size stored in the directory entry. If the last byte of the file has been read, then at the next call of fgetc(), the function has to return EOF (EOF may already be a macro contained in one of the system header files you include in your program). Therefore, when you close your file with myfclose(), you have to update the directory entry with the new file size (number of bytes added to the file).

CGS B3-B1

Task

Add a directory hierarchy to your virtualdisk that allows the creation of subdirectories. Implement the

following interface functions:

mymkdir( char * path) that creates a new directory

char ** mylistdir (char * path) that lists the content of a directory

Extend your test program shell.c with the following test steps:

create a directory “/myfirstdir/myseconddir/mythirddir in the virtual disk

call mylistdir(“/myfirstdir/myseconddir): print out the list of strings returned by this function

write out virtual disk to virtualdiskB3_B1_a”

create a file “/myfirstdir/myseconddir/testfile.txt in the virtual disk

call mylistdir(“/myfirstdir/myseconddir): print out the list of strings returned by this function

write out virtual disk to “virtualdiskB3_B1_b”

Redirect the output of your shell program into a file traceB3_B1.txt

o ./shell > traceB3_B1.txt

Submission

For a CGS B3, submit shell.c, filesys.c, filesys.h, the files virtualdiskB3_B1_a, virtualdiskB3_B1_b, traceB3_B1.txt and a Makefile that allows your program to be compiled. Put files into a separate directory CGS_B3_B1. For a CGS B1, the virtual disk should not show any clutter, only the information you write into it, and in your report, you have to provide detailed comments about the implementation of the required functions (explain it by walking the reader through the most important implemented statements and and explain their purpose). Parts missing in your solution may reduce the CGS mark. Try to get with your implementation as far as possible.

Explanation

A directory can be specified absolute or relative to another directory:

absolute: /mydirectory

relative: mydirectory

A directory may be specified with a path:

absolute: /firstlevel/secondlevel/mydirectory

relative: “somelevel/somelevelbeneath/mydirectory

In order to create the directory mydirectory”, all the subdirectories specified in the path must exist. If you call mymkdir ( “/firstlevel/secondlevel/mydirectory” ) in your test program shell.c, then the directory hierarchy consisting of Root->firstlevel->secondlevel must exist, before you can create mydirectory” in the parent directory secondlevel. If these directories don’t exist, they have to be created.

Use strtok_r() from the C standard library to tokenize a path string ( look up its usage ). If you experience a segmentation fault during running the program, remember that pointers have to point to allocated memory and that string literals are allocated in the segment ‘.rodata and cannot be manipulated.

CGS A5-A1

Task

Implement the following interface functions:

mychdir( char * path), using the global variable currentDir as specified in filesys.c: a change

into a directory will change the variable currentDir

myremove( char * path) removes a file; the path can be absolute or relative

myrmdir( char * path) removes a directory, if it is empty; the path can be absolute or relative

Change how directories are created:

add two default entries (as we are used to under Unix etc.):

o the directory entry . points to the directory itself

o the directory entry .. points to the parent directory

allow the creation of a directory relative to the current directory

Change how files are created:

the function myfopen() can be called using an absolute or relative path in the filename, if the

directories specified in the path do not exist, then they have to be created

Demonstrate with your test program shell.c that creating and deleting files and directories works and that results are visible in the hexdumps of the virtual disk. Save intermediate results. You may follow the following steps:

create a directory “/firstdir/seconddir in the virtual disk

call myfopen( “/firstdir/seconddir/testfile1.txt )

you may write something into the file

close the file

call mylistdir(“/firstdir/seconddir): print out the list of strings returned by this function

change to directory “/firstdir/seconddir

call mylistdir(“/firstdir/seconddir/” ) or mylistdir(.) to list the current dir, print out the list of

strings returned by this function

call myfopen( testfile2.txt, w )

you may write something into the file

close the file

create directory thirddir

call myfopen( thirddir/testfile3.txt, w )

you may write something into the file

close the file

write out virtual disk to virtualdiskA5_A1_a”

call myremove( testfile1.txt )

call myremove( testfile2.txt )

write out virtual disk to virtualdiskA5_A1_b”

call mychdir (thirddir)

call myremove( testfile3.txt”)

write out virtual disk to virtualdiskA5_A1_c”

call mychdir( “/firstdir/seconddir) or mychdir(..)

call myremdir( thirddir