Slide #1.

Z502 File System Contains: Disk Structure Description System Calls Layout on the disk Allocation on the disk August, 2018 Rev 4.50 1
More slides like this


Slide #2.

Z502 Disk Structure There are many ways to lay out data on a disk. In this project, it’s possible to let you, the student, develop your own style of structure and information on the disk. I’ve decided to instead give you a structure and methodology. There are three reasons I’d like to go in that direction. 1) Giving you a structure makes your job easier – you don’t need to develop something from scratch. 2) What I’m giving you is a structure that represents what you might find on a real disk – you’ll learn by understanding this format. 3) I’ve developed a DiskCheck() that will execute on the structure you have placed on a disk. The Z502 hardware outputs a file that let’s you see where things are actually placed on your disk. In addition, it allows me to be assured that you’ve coded correctly. 2
More slides like this


Slide #3.

Z502 File Structure Root directory named “root” (Inode = 0) Block 0 RootDir Location Swap Location Bitmap Location Index Location Bitmap Swap Contiguous Space Contiguous Space Index Block Index Location Index Location Index Location Index Location Directory (Inode = ?) Index Location File (Inode = ?) Index Location Directory (Inode = ?) Index Location File (Inode = ?) Index Location
More slides like this


Slide #4.

Z502 Disk Structure FORMAT(DiskID, &ErrorReturned); OPEN_DIR(DiskID, "root", &ErrorReturned); CREATE_DIR("Test10", &ErrorReturned); CREATE_FILE("file1", &ErrorReturned); CREATE_FILE("file2", &ErrorReturned); OPEN_DIR(-1, "Test10", &ErrorReturned); CREATE_FILE("file1", &ErrorReturned); These are the system calls in test10 // // // // // // Make root the current directory Create directory Test10 under root Create file file1 under root Create file file2 under root Make test10 the current directory Make file1 under Test10 Block 0 Directory: root Directory: Test10 File: file1 File: file2 File: file1 4
More slides like this


Slide #5.

Z502 Disk Structure Here’s that same picture again Block 0: Contains a pointer to root, directory size 1; pointer to swap; pointer to bitmap Directory: root, Swap Area Bitmap Contains location of directory index Index: (8 ptrs) Ptr to Test10 Ptr to file1 Ptr to file2 Directory: Test10 Index: (8 ptrs) Ptr to file1 0 0 0 0 0 0 0 0 0 File: file1 0 0 0 0 In this example, all directories and files have index level = 1. 0 File: file1 0 0 0 0 File: file2 0 Index: Index: Index: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0
More slides like this


Slide #6.

Z502 File Structure Root directory named “root” (Inode = 0) Block 0 RootDir Location Swap Location Bitmap Location Index Location Bitmap Swap Contiguous Space Contiguous Space Index Block Index Location Index Location Index Location Index Location Directory (Inode = ?) Index Location File (Inode = ?) Index Location Directory (Inode = ?) Index Location File (Inode = ?) Index Location
More slides like this


Slide #7.

Sector 0 Z502 Disk Structure Definition Of Sector 0: This is the first block on a disk. It is produced when you do a software Format of the disk. It defines various segments of the disk necessary for successful operation. Byte Bytes Offset in Field Field 0 1 Disk ID 1 1 Bitmap Size 2 1 RootDir Size 3 1 Swap Size 4 2 6 8 10 12 15 2 2 2 3 1 Description The number you have given to the disk. It will be easiest if you assign the same number as the hardware uses, but it’s your choice. How large is the bitmap. You can determine your own size. The size will be 4 X BitmapSize So if this field contains a 3, then 4 X 3 = 12 and 12 blocks will be assigned to the bitmap. How large is the Root Directory Header. You can determine your own size. The size will be RootDirSize So if this field contains a 1, then 1 block will be assigned to the Root Directory Header. Note that the total size of a directory is determine by the number of indices, subdirectories and files that are in that directory. This field is only to specify the header size. How large is the Swap Space. You can determine your own size. The size will be 4 X SwapSize So if this field contains a 2, then 4 X 2 = 8 and 8 blocks will be assigned to the Swap Directory. Disk Length This is the number of sectors you are using on the disk. Note Byte 5 is Most Significant Byte, Byte 4 is Least Significant Byte Bitmap Location The starting sector number where the bitmap is located. Note Byte 7 is MSB, Byte 6 is LSB Swap Location The starting sector number where the Swap Space is located. Note Byte 9 is MSB, Byte 8 is LSB Root Dir Location The starting sector number where the Root Directory is located. Note Byte 11 is MSB, Byte 10 is LSB RESERVED For this release, these bytes must be set to ‘\0’. Revision For this release, this byte must be set to 1. 7
More slides like this


Slide #8.

Z502 Disk Structure Bit clarification Suppose we are given the requirement as shown on the previous page: The starting sector number where the bitmap is located. Note Byte 7 is MSB, Byte 6 is LSB Location of bitmap sector 1, 128, 256, 4096, resulting bit pattern 00000001 00000000 10000000 00000000 00000000 00000001 00000000 00010000 check disk would say "xx xx xx xx xx xx 01 00 xx .." "xx xx xx xx xx xx 80 00 xx .." "xx xx xx xx xx xx 00 01 xx .." "xx xx xx xx xx xx 00 10 xx .." Note how the endedness is used here. 8
More slides like this


Slide #9.

Z502 Disk Structure Bitmap The function of the bitmap is as follows: There is one bit assigned for each sector on the disk. If that bit is set, then the sector is in use; if that bit is clear, then that sector is unused. The bitmap requires a number of sectors on the disk for its own storage. So IF you had a bitmap showing ONLY Sector 0 in use, it would be represented by “10000000,00000000,00000000, . . .”, and if you were to print out that bitmap, it would look like 80 00 00 00 . . . 9
More slides like this


Slide #10.

Z502 Disk Structure Bitmap The function of the bitmap is as follows: There is one bit assigned for each sector on the disk. If that bit is set, then the sector is in use; if that bit is clear, then that sector is unused. The bitmap requires a number of sectors on the disk for its own storage. So IF you had a bitmap showing ONLY Sector 0 in use, it would be represented by “10000000,00000000,00000000, . . .”, and if you were to print out that bitmap, it would look like 80 00 00 00 . . . 10
More slides like this


Slide #11.

Z502 Disk Structure Header For Directory or File Every File or Directory has a Header Block. This contains the essential information for that entity. Among the items associated with this Block is a pointer to an index. This index points to the DATA for this file or to the Files and Directories within a directory. Details about these fields are given in the following slides. Byte Bytes in Offset Field Field Description 0 1 Inode A unique ID for this file or directory. This Inode is unique across all disks on the entire system. This means there are NOT TWO identical Inodes on the Z502. The ASCII text representing the name. Only letters and numbers are allowed in names. Note that this can be 7 characters so MAY not have a delimiter. The field is left justified so that Byte2 contains the first character of the name. Unused characters in the name contain “\0”. 1 7 Name 8 3 Creation Time Contains the time at which the file/directory was created. This is the time of creation as found by asking the hardware for the time. Byte 9 is the MSB and Byte 11 is the LSB. 11 1 File Description See the format of the Description Field below 12 2 Index Location 14 2 File Size The sector number where the Index Sector containing the sector numbers for this file is located. Note Byte 13 is MSB, Byte 12 is LSB The number of bytes occupied by the data portion of this file. It’s necessary to allocate sectors to hold the entire data portion of the file, but the last sector need not be totally filled. Byte 15 is MSB, Byte 14 is LSB 11
More slides like this


Slide #12.

Z502 Disk Structure Header For Directory or File Further explanation of the Fields in a Header: File Description Field Bits Representation Description 0 0000000X If set, this structure is a directory. If clear, this structure is a file. 1-2 00000XX0 The index level of the file – and must contain either a 0, 1, 2, or 3. 3-7 XXXXX000 Contains the parent Inode of this file or directory. XXXXX = 31 for the ROOT directory. File Size Field This represents the number of bytes occupied by a file. File data can only be stored on the disk in multiples of PGSIZE bytes – however, that doesn’t mean all those bytes are real data. A file may have a length of 17 bytes, for instance, so that it would store 16 bytes in the first data block, and one byte in the second data block. For a directory header, this field is undefined and should be set to zero. 12
More slides like this


Slide #13.

Z502 Disk Structure Header For Directory or File Further explanation of the Fields in a Header: Index Level Index Level Description 0 The location “Data Index” points to a single block. This means that, if this is a directory, that directory contains only a single file or a single subdirectory. If this is a file, it means that file contains only a single data block. 1 The location “Data Index” points to a First Level Index. For a directory, the entries in that index in turn point to a directory or file header. For a file, the entries in that index in turn point to data belonging to that file. An unused index element, not pointing to a file or directory must be set to 0. 2 The location “Data Index” points to a Second Level Index. Each of the entries in this second level index point to a First Level Index which act as described above. Again, unused elements must contain a 0. 3 The location “Data Index” points to a Third Level Index. Each of the entries in this third level index point to a Second Level Index which act as described above. Again, unused elements must contain a 0. 13
More slides like this


Slide #14.

Z502 Disk Structure Header For Directory or File Index Sector – showing the layout of disk sectors for a single level index Byte Offset Bytes in Field Description 0 2 Holds the sector number for a block in the file, a directory header, or 0 2 2 Holds the sector number for a block in the file, a directory header, or 0 4 2 Holds the sector number for a block in the file, a directory header, or 0 6 2 Holds the sector number for a block in the file, a directory header, or 0 8 2 Holds the sector number for a block in the file, a directory header, or 0 10 2 Holds the sector number for a block in the file, a directory header, or 0 12 2 Holds the sector number for a block in the file, a directory header, or 0 14 2 Holds the sector number for a block in the file, a directory header, or 0 Locations not pointing to a sector must be set to 0. The two bytes for each sector number obey the rules on Slide 8. So a pointer to Sector 128. would look like 10000000 00000000. Byte 0 = 80x, Byte 1 = 0x. 14
More slides like this


Slide #15.

Z502 Disk Structure Example of File Index Structure An example for a file having only one data block (alternative 1). File Header Field Value File / Dir File Index Level 0 Index Location Data Block File Size (Bytes) <= 16 15
More slides like this


Slide #16.

Z502 Disk Structure Example of File Index Structure An example for a file having only one data block (alternative 2). File Header Field Value File / Dir File Index Level 1 Index Location File Size (Bytes) <= 16 Index Offset 0 2 4 6 8 10 12 14 Value 0 0 0 0 0 0 0 Data Block 16
More slides like this


Slide #17.

Z502 Disk Structure Example of File Index Structure An example for a file having only one data block (alternative 3). File Header Field Value File / Dir File Index Level 2 Index Location File Size (Bytes) <= 16 Index Offset 0 2 4 6 8 10 12 14 Value 0 0 0 0 0 0 0 Index Offset 0 2 4 6 8 10 12 14 Value Data Block 0 0 0 0 0 0 0 17
More slides like this


Slide #18.

Z502 Disk Structure Example of File Index Structure An example for a file having only one data block (alternative 4). File Header Field Value File / Dir File Index Level 3 Index Location File Size (Bytes) <= 16 The Index Level shows the number of index blocks that must be Accessed before reaching Data Blocks. Index Offset 0 2 4 6 8 10 12 14 Value 0 0 0 0 0 0 0 Index Offset 0 2 4 6 8 10 12 14 Value 0 0 0 0 0 0 0 Index Offset 0 2 4 6 8 10 12 14 Value Data Block 0 0 0 0 0 0 0 18
More slides like this


Slide #19.

Z502 Disk Structure Example of File Index Structure An example for a file having only two data block. (there are many other alternatives) File Header Field Value File / Dir File Index Level 1 Index Location File Size (Bytes) >16, < 32 Index Offset 0 2 4 6 8 10 12 14 Value Data Block 0 0 0 0 0 0 Data Block 19
More slides like this


Slide #20.

Z502 Disk Structure Example of File Index Structure An INCORRECT example for a file having only two data block File Header Field Value File / Dir File Index Level 1 Index Location File Size (Bytes) >16, < 32 Index Offset 0 2 4 6 8 10 12 14 Value 0 0 0 0 0 0 Data Block Index Offset 0 2 4 6 8 10 12 14 THIS IS NOT CORRECT. All Data Blocks for a file must traverse the same number of index blocks. Value Data Block 0 0 0 0 0 0 20
More slides like this


Slide #21.

Z502 Disk Structure Example of File Index Structure An example for a file having nine data blocks. (there are many other alternatives) Index File Header Field Value File / Dir File Index Level 2 Index Location File Size (Bytes) > 8 * 16, < 9 * 16 16 is the number of data bytes in a Data Block Offset Index Offset 0 2 4 6 8 10 12 14 Value 0 0 0 0 0 0 0 2 4 6 8 10 12 14 Value 0 0 0 0 0 0 Data Block Data Block Data Block Data Block Data Block Data Block Index Offset 0 2 4 6 8 10 12 14 Value 0 0 0 0 0 0 Data Block Data Block Data Block While this is technically a legal disk layout, how do you know how to find, say the seventh block, without walking through all the index blocks. 21
More slides like this


Slide #22.

Z502 Disk Structure Example of Directory Index Structure An example for a directory having two File or Directory header blocks. (there are many other alternatives) File Header Field Value File / Dir Directory Index Level 1 Offset Index Location File Size (Bytes) Index 0 0 2 4 6 8 10 12 14 Value Directory or File Header 0 0 0 0 0 0 Directory or File Header 22
More slides like this


Slide #23.

File System Calls FORMAT Usage of FORMAT INT32 DiskID; INT32 ErrorReturned; FORMAT (DiskID, &ErrorReturned); Causes the disk with ID DiskID to be formatted by the Operating System. The following operations are accomplished: 1. Sector 0 on the disk is given the structure described previously. 2. A structure for the root directory (with name “root” has been defined and placed on the disk at the Sector pointed at within Sector 0. 3. The bitmap has been defined on the disk, being placed at the location pointed at within Sector 0. 4. The Swap Area is defined and placed on the disk at the location pointed to by Sector 0. 5. All of these auxiliary structures, the bitmap, root directory, and swap area are properly initialized. The only possible error here is if the DiskID is not in the legal range. 23
More slides like this


Slide #24.

File System Calls CHECK_DISK Usage of CHECK_DISK INT32 DiskID; INT32 ErrorReturned; CHECK_DISK (DiskID, &ErrorReturned); This System call causes the Operating System to call a Hardware Function that writes out the contests of the disk into a file named “CheckDiskData.” You are able to print out this file to observe the contents of the disk. In addition, you can run the program CheckDisk against this file in order to determine if the structure on the disk is correctly managed according to the specification. The only possible error for the Check_Disk call is if the DiskID is not in the legal range. 24
More slides like this


Slide #25.

File System Calls OPEN_DIR Usage of OPEN_DIR INT32 DiskID_OR_Minus1; char *DirectoryName; INT32 ErrorReturned; OPEN_DIR (DiskID_OR_Minus1, DirectoryName, &ErrorReturned); This System call causes the Operating System to open a directory on the specified disk. This directory may or may not already exist. If it does NOT already exist, it is created. The directory you have open is defined as your “Current Directory”. You can only use this call to open a directory which is a parent or child directory of your Current Directory. To move to a parent directory, you can use a Filename of “..”. You can only have one directory open at a time. Once you have established the Current Directory, you no longer need to explicitly specify the DiskID – this is because further OPEN_DIR calls work from the established Current Directory. You should use a value of “-1” in this case. This call is a precursor to opening or creating new directories and files. The new entities can only be created in the current directory. Possible errors for the CURRENT_DIRECTORY include: DiskID is not in the legal range. There is no room on the disk for the newly created directory. If the DirectoryName is specified as “..” and the present directory is “root”. 25
More slides like this


Slide #26.

File System Calls Notes about Current Directory The Current Directory is a property of a PROCESS. For instance, two processes could have the same disk open (though only one of those processes would have formatted the disk.) Then each of those processes could have their Current Directory at a different place on the disk and each of them could then operate independently of the other. In the same way, a process could not, in this architecture, be operating on two disks without closing one of them first. 26
More slides like this


Slide #27.

File System Calls CREATE_DIR Usage of CREATE_DIR char * DirectoryName; INT32 ErrorReturned; CREATE_DIR (DirectoryName, &ErrorReturned); This System call causes the Operating System to create a directory of the specified name as a subdirectory of the Current Directory. The result of this call is to create a Directory. It does NOT open that directory. Possible errors for the CREATE_DIR call include: DirectoryName already exists in the current directory. There is no space remaining on the disk. If the DirectoryName contains illegal characters or more than the allowable number of characters for a name. 27
More slides like this


Slide #28.

File System Calls CREATE_FILE Usage of CREATE_FILE char * FileName; INT32 ErrorReturned; CREATE_FILE (FileName, &ErrorReturned); This System call causes the Operating System to create a file of the specified name in the Current Directory. The result of this call is to create a File. It does NOT open that File. Possible errors for the CREATE_FILE call include: FileName already exists in the current directory. There is no space remaining on the disk. If the FileName contains illegal characters or more than the allowable number of characters for a name. 28
More slides like this


Slide #29.

File System Calls OPEN_FILE Usage of OPEN_FILE INT32 Inode; char * FileName; INT32 ErrorReturned; OPEN_FILE (FileName, &Inode, &ErrorReturned); This System call causes the Operating System to open a file of the specified name in the Current Directory. The result of this call is to open a File. If the specified file does not exist, it is created and then opened. When a file is open, this allows further operations on the file. Possible errors for the OPEN_FILE call include: There is no space remaining on the disk (in the case where the file must be created.) If the FileName contains illegal characters or more than the allowable number of characters for a name. 29
More slides like this


Slide #30.

File System Calls WRITE_FILE Usage of WRITE_FILE INT32 Inode; INT32 FileLogicalBlock char WriteBuffer[] INT32 ErrorReturned; WRITE_FILE (Inode, FileLogicalBlock, WriteBuffer, &ErrorReturned); This System call causes the Operating System to write a block of data to the disk, and associate that data with a logical block number in the file associated with Inode. The Operating System does NOT return control to the user program until it is known that the disk has been written to; in other words, this data is not cached. Possible errors for the WRITE_FILE call include: The Inode that was input does not belong to an opened file. The FileLogicalBlock is negative or is larger than is supported by the file system. There is no space remaining on the disk. 30
More slides like this


Slide #31.

File System Calls READ_FILE Usage of READ_FILE INT32 Inode; INT32 FileLogicalBlock char ReadBuffer[] INT32 ErrorReturned; READ_FILE (Inode, FileLogicalBlock, ReadBuffer, &ErrorReturned); This System call causes the Operating System to read a block of data from the disk, and at a location associated with a logical block number of the file associated with Inode. The Operating System does NOT return control to the user program until it is known that the disk has been read from. At the time control is returned to the user program, the O.S. has transferred data to the user-defined buffer. If the FileLogicalBlock is a location on the disk that has not previously been written to, a buffer containing all nulls is returned. Possible errors for the READ_FILE call include: The Inode that was input does not belong to an opened file. The FileLogicalBlock is negative or is larger than is supported by the file system. There is no space remaining on the disk. 31
More slides like this


Slide #32.

File System Calls CLOSE_FILE Usage of CLOSE_FILE INT32 Inode; INT32 ErrorReturned; CLOSE_FILE(Inode, &ErrorReturned); This System call causes the Operating System to Close the file. This ensures that all data and metadata has been written to the disk. So, in addition to the DATA that may have previously been written, all indices associated with files, and all bitmap information is now also written to the disk. Possible errors for the CLOSE_FILE call include: The Inode that was input does not belong to an opened file. 32
More slides like this


Slide #33.

File System Calls DELETE_FILE Usage of DELETE_FILE char * FileName; INT32 ErrorReturned; DELETE_FILE (FileName, &ErrorReturned); This System call causes the Operating System to delete a file of the specified name in the Current Directory. The result of this call is to delete the specified File. Possible errors for the DELETE_FILE call include: FileName does not exist in the current directory. If the FileName contains illegal characters or more than the allowable number of characters for a name. 33
More slides like this


Slide #34.

File System Calls DIR_CONTENTS Usage of DIR_CONTENTS INT32 ErrorReturned; DIR_CONTENTS ( &ErrorReturned ); This System call causes the Operating System to print information about the directories and files in the Current Directory. The format for this output is as follows (it’s essentially all the information in the Directory/File header). Fields include: Inode, Filename, D/F, Creation Time, Number of Bytes in File. If you were to execute this System Call on the directory “root” resulting from Test10, you would get the following output. Contents of Directory root: Inode, Filename, D/F, Creation Time, File Size 1 Test10 D 123 -2 file1 F 145 0 3 file2 F 155 0 Possible errors for the DIR_CONTENTS call include: There is not currently a directory that has been opened and so there is no Current Directory. 34
More slides like this


Slide #35.

Layout and Allocation on the Disk One of the things you’ll need to decide in your implementation of your OS502 file system is where to place items on the disk. You care about this because you would like to minimize the seek distance used by your file system for performance reasons. You have two ways to implement your decision: 1) In Block 0, where do you place the root directory, swap space, and bitmap? 2) As you allocate directories and their indices, and files and their indices and data, how do you cluster or not cluster that information? All this is your decision. What is the most efficient way to allocate blocks? You will do this from the bitmap – the bitmap is initially defined to contain as occupied, only the blocks allocated during formatting. After that, you get to use the bitmap any way you want to allocate blocks for use in Inodes, indices, and data. 35
More slides like this