Program Assignment 2COMP310/ECSE 427, Fall 2013IntroductionA file system (FS) is one of the most important components of an operating system. There is awide variety of file system implementations in use, from traditionally disk-based ones such asNTFS, FAT32, ext2, ext3 to network-based and distributed ones (e.g. Google File System). In thisassignment, you are expected to implement a Simple File System (SFS). This assignmentintroduces basic ideas about a file system such as disk layout, file descriptors, directories, inodesand how to implement basic file operations such as seeking, reading, writing, etc. SFS issimplified from real file systems and contains the following feature: Max length for file and directory names Single-level directory Opened files are both readable and writableSpecificationsInterfaces int mksfs();Initialize the file system layout on the diskvoid sfs_print_info();Print the information about the SFSint sfs_mkdir(char *dirname);Create a directoryint sfs_rmdir(char *dirname);Delete a directory (and all its containing files)int sfs_lsdir();List all directoriesint sfs_open(char *name);Open a file. Create one if not existedint sfs_close(int fd);Close the fileint sfs_ls();List all the files in the file systemint sfs_write(int fd, char *buf, int len);Write to the fileint sfs_read(int fd, char *buf, int len);Read from the fileint sfs_remove(char *name);Delete a fileint sfs_eof(int fd);Check if we reach EOF (End-Of-File) You may find these functions familiar as they provide similar headers as those found in thestandard C library (fopen, fclose, fwrite, fread, feof, etc). Also you can find more detaileddescription of the functionality of these interfaces in “fs.c”.LayoutSFS operates on a block disk. Each block is numbered by block id (4bytes, of type u32), startingfrom zero. The following graph depicts how SFS uses each block.Superblock(only one) Freemap block Freemap block Data block Data blocknfreemap_blocks……nblocks……Block id: 0 1 nfreemap_blocks nfreemap_blocks+1 A super block is the first block (with block_id=0). It contains all the basic informationabout SFS, including how following blocks are organized. Freemap blocks store the bitmap identifying which block on the disk is usable to SFS. Data blocks can be either an inode that describes a file, a directory block that describesa directory, a file content block that stores a fraction of file content, or a frame blockthat indexes content blocks.The (only) super block gives important parameters about the SFS. nblocks tells the total numberof blocks that can be used by SFS. nfreemap_blocks tells how many blocks are used as freemapblocks. For a valid SFS layout, the number of data blocks = nblocks – nfreemap_blocks –1(superblock).Freemap (bitmap) and block managementThe SFS should know which block is used so that when the user creates a new file, SFS canallocate free blocks to accommodate its data. Freemap is the mechanism for this. This graphshows the case of three freemap blocks:Superblock(only one) Freemap block Freemap block Freemap block Data block Data block1 1 1 1 0 0 0 0……nfreemap_blocks==3 (for example)……Interpret as a bit array(bitmap):nblocksnblocks bitsnfreemap_blocks * BLOCK_SIZE * 8 bitsThe freemap blocks can be interpreted as a bit array, where each bit indicates if itscorresponding block id is used. For example, the first bit in the freemap is always 1, indicatingthat the block with block_id==0 (superblock) is used. In the case we have three freemap blocks,the second, third and fourth bits are also set to 1, indicating those freemap blocks themselvesare used. In such sense, the freemap is self-describing. More details can be found here:http://en.wikipedia.org/wiki/Free_space_bitmap.Note: If we use one bit for each block, we need nblocks bits to manage all disk blocks. In suchcase, the freemap should be large enough to hold nblocks bits, i.e., nfreemap_blocks *BLOCK_SIZE * 8 >= nblocks (each byte has 8 bits).DirectoryA directory block is a kind of data blocks that describes a directory, which contains the block idsof its containing files.…Superblock…root_dirnext_dirThe directory blockfor root dirinode1inode2…The directory blockfor second dirdirnamenext_dir=0inode1inode2…dirnameEach directory block describes one directory. Directory blocks are organized as a linked list. Theblock id for the first directory block is found in the superblock. The second one can be foundfollowing the next_dir field of the first one. The last directory block has a next_dir==0. The restspace of a directory stores the name of the directory and the block ids of inodes (containingfiles).For simplicity, the linked list never shrinks. If a file gets deleted, the corresponding inode entryin a directory block will be changed to zero, indicating that this entry can be reused next time afile is created. When a file is created, SFS first scans through the linked list to find entry withzero value. If there is a zero entry, the entry will be used. Otherwise, SFS grows the linked list tohold more entries.FileInodeAn Inode is the data structure that the file system uses to describe a file. Typically a file has a listof attributes (such as name, size, date, etc). An inode is essentially a data block, which containsthe file attributes and provides index to frame and content blocks. The below figuredemonstrates how a file is stored/indexed on the disk:Next frameEntryEntrysize=450First_frame“filename1”Next frame=0EntryEntry“hello world!” “it’s comp310”EntryDirectory block Inodenext_dirinode1inode2…Frame FrameContent block Content blockAs shown, a directory block indexes inodes. An inode indexes frames. A frame indexes contentblocks. An inode contains file information, such as size and name. And most importantly, it hasthe block_id for the first frame of the file. Frame blocks are also organized as a linked list (similar to that seen in directory blocks).The entries in a frame block contain the block ids of content blocks. Each content block stores a fraction of the file content. In this example, the content ofthe file is “hello world! It’s comp310”, which is split and stored in two content blocks.We use frames along with content blocks to enable very large files. A file may grow in size astime goes by. So it is not practical to allocate continuous blocks for a file. To allow dynamicgrowing files, a frame is used to index non-continuous content blocks. In some cases, when thefile is very large, one frame may not be enough. So the linked list structure helps.To simplify the implementation, every time you need to expand the size of a file, you alwaysallocate a “full frame”. For example, assume the block size is 12 bytes and a block id is 4 bytes.So one frame can index two content blocks. Initially the file is empty. First, the user writes 7 bytes to the file. SFS allocates two content blocks (C1 and C2) anda full frame indexing these two content blocks (F->C1, C2). In such case, we have twocontent blocks which make a capacity of 24 bytes. Next, the 7 bytes data is written inthe first content block (C1). Second, user again writes 14 bytes. The first 5 bytes will be stored in C1 and theremaining 9 bytes go to C2. In this operation, no new frame/content blocks areallocated. Next time if user writes exceed the capacity, we again allocate a full frame.This pre-allocation mechanism explains why there are “size” and “size on disk” when you checkthe property of a file on Windows. “size” normally represents the actual length of the contentwhile the “size on disk” indicates the capacity of the file.Read/writeRead/write operation is the most important operations on a file. In a nutshell, read operationsneed to retrieve the content from scattered content blocks. We define a helper function calledsfs_get_file_content() to get the block ids of content blocks within a given range. In the belowgraph, we give a detailed example.For example, the file has 10 non-consecutive content blocks. We want to read 85 bytes startingfrom the 17th byte, which span 8 content blocks. First, sfs_get_file_content() returns the block ids of the grey content blocks in the graph.The sfs_get_file_content() hides the facts that content blocks are indexed by a linked listof frames . Then we iterate through these blocks and copy the content. The first iteration will copy7 bytes starting from the 5th byte in the first grey block… Three variables arerecommended to control the loop.Block:12bytes17 102offset:remaining:to_copy:5 85 70 78 120 66 120541204212030120 18 120 6 6Opened filesWhen an on-disk file is opened, we use an in-memory file descriptor (fd) to keep the state of thefile. Note that a file descriptor is created in the memory when the file is opened and freed fromthe memory when the file is closed. A file descriptor never stays on the disk. These are the fieldsin a file descriptor: The cursor identifies the position (inside the file content) of the file operations. Forexample, when we open a file, the cursor is zero, meaning that our read/writeoperations will be performed from the very beginning of the file. Next if we read fivebytes, the cursor will move forward to 5. The user can also use sfs_seek() to manipulatethe cursor. The inode id of the file. Whenever SFS needs to do read/write or retrieve the size/nameof the file, it needs to go for the inode.All file descriptors are kept in a file descriptor table. So, when a file is opened, user gets a filedescriptor number (fd) indexing the file descriptor in the table.TestingBuild with and without assignment 1Along with this document, seven source code files are distributed: fs.c, ext.c, exta1.c, ext.h, fs.h,test.c, Makefile, a1/. You are only allow to modify fs.c. Follow the guidelines in the source codefile. We provide a correct and simplified version of assignment 1 to allow you to focus onassignment 2 first. You can type “make” to build the program and run the executable “sfs” totest your implementations.When you get everything ready, you are required to use the code from your own firstassignment. Put your assignment 1 code in a1/ and type “make witha1” to build the programwith assignment 1.Test casesWe have 10 test cases. Each case examines a set of interfaces and helper functions. Test casesare arranged in the recommended implementation sequence, i.e., case 2 is dependent on case 1.For each test case, we list the functions to be implemented: TestcasePointsHelper functionsInterfaces15sfs_mkfs(), sfs_print_info()215sfs_alloc_block(), sfs_free_block(),sfs_flush_freemap(), sfs_find_dir()sfs_mkdir(), sfs_rmdir()310sfs_open(), sfs_close(), sfs_remove(),sfs_ls()415sfs_get_file_content()sfs_write(), sfs_read()55sfs_resize_file()sfs_seek()65feof()75overwrite815sfs_resize_file()write to expand size910complicated sfs_seek()1015large file (multiple frames) HandinIf you can make PA2 work PA1, please put your PA1 files under a1/ and handin both. In this case,you will be tested by “make witha1”. Otherwise, please leave a1/ empty and test with “make”.In both cases, you’ll get an executable named sfs, which runs through all test cases.
