Filesystem Quick Review The Tempo 32 Operating System Filesystem is object with methods for managing named collections of data Methods usually called open close read write etc Semantics unique to each type Part 9 System Call Implementation The Tempo Filesystem Naming conventions File sharing Size limitations Creation deletion rules Protection Reliability Efficiency Performance Etc 1 2 Tempo Filesystem Filesystem Calls Review Tree structured filesystem similar to UNIX e g two file types regular and directory Files are identified by a path that consists of zero or more names separated by names are limited to 15 chars ex abcdefghijklmno X3 c No concept yet of a working directory so no concept yet of a relative path Maximum file size is 70 656 bytes currently There is no concept of a username or date and time associated with files No facility for mounting drives or partitions open path mode opens the file at path returning a file descriptor creat path creates a new file at path open for writing read fd buff count reads count bytes from fd into buff write fd buff count writes count bytes to fd from buff seek fd offset start positions file fd so next I O is at start begin current end offset mkdir path make a directory at path close fd close open file fd remove path delete or mark for deletion the file at path stat path buf fstat fd buf get file path or fd metainformation rename oldname newname rename a file opencon void open console for I O setconmode fd mode set console mode raw or cooked 3 4 Tempo Filesystem Basics Superblock Format The disk contains the superblock which identifies the type of filesystem its size and the logical block number LBN of the first unused block also contains the root directory entry a linked list of unused disk blocks with the head pointer in the superblock directory blocks containing directory entries data blocks executables data etc 5 char fsident 8 fsys1 0 unsigned nblocks blocks in filesystem unsigned freeblk first free disk block struct dirent rootde root directory entry char rsvd 432 unused 6 1 Directory Entry Format Sytem Wide Open File Cache unsigned char dflag Every open file in the system is recorded in an entry of the fdesc array defined in kernel fs c There are NFDESC entries in this array each of which is of type struct FDESC defined in h types h If multiple processes have the same file open there is only one entry in the fdesc array for the file This guarantees that changes to the file s directory entry will be recorded in only one place 0x00 unused entry 0x01 regular file 0x02 directory char fname 15 file name padded with 0 unsigned fsize file size in bytes always a multiple of 512 for directories unsigned dir 10 block nums of first 10 blocks unsigned indir block num of blk with 128 additional block pointers 7 struct FDESC struct FDESC Per Process Open File Info system wide one entry per open file int nrefs 8 ref count unsigned int flags unsigned int blockno block containing dir entry unsigned int offset blockno offset of dir entry struct dirent de in core directory entry The flags entry can contain any or all of these bits FDE DIRTY the directory entry has changed since it was read from disk FDE RMPEND removal is pending for the file Each process in the process table entry has an array fd in which entries for its open files are recorded Each of these entries of type struct FD defined in h types h gives how the file was opened read write etc the index in the system wide fdesc array of file information the offset in the file where the next read write will take place FDE LOCKED the entry is locked by a process performing an operation 9 Per Process Information Process P1 0 FileX System wide Open File Information 10 Blk 0 fdesc array Superblock Root Dir Data for FileA 0 Entry for file X nrefs 1 1 FileY 2 Unused Entry for file A nrefs 1 FileB 3 File Z Unused nrefs 0 Empty Entry for file Y nrefs 2 FileD Process P2 0 FileY 1 FileA 2 3 FileC FileB FileA DirX Process P3 FileZ 1 FileZ 2 Unused 3 Unused Free Data for FileB 1 Free Data for FileD 0 nrefs 1 Entry for file Z nrefs 3 Data for FileD 9 Entry for file C nrefs 1 Indirs for FileD Unused nrefs 0 Free Data for FileB 0 Entry for file B Data for FileD 10 Data for FileD 11 FileX 0 A Small Filesystem Relation between per process open file entries and the fdesc array entries Note that process P3 has FileZ open twice 11 FileY Empty DirF FileZ The root directory contains FileA 512 bytes FileB between 513 and 1024 bytes FileD between 5121 and 5632 bytes DirX Directory DirX contains FileX FileY DirF and FileZ 12 2 Block Size Observations 1 Block Size Observations 2 Each block in the current filesystem is just one sector 512 bytes A file can have at most 138 total blocks Changing the block size to 4K bytes 8 sectors would give 1034 blocks 10 direct blocks 10 direct pointers 128 indirect blocks 1 block of 4 byte pointers Thus the maximum file size is 138 512 70 656 bytes The average wasted space in a regular file is half a block or 256 bytes 10 direct blocks 1024 indirect blocks 4096 4 1024 The maximum file size is now 1034 4096 4 235 264 bytes The average wasted space in a regular file increases to 2048 bytes 13 14 Blk 0 Following a Path Superblock Root Dir Free Data for FileA 0 FileA Many file operations require locating its directory entry For example to locate file DirX FileY we must FileB Empty FileD DirX Parse the path to obtain its components Search the blocks of the root directory for DirX Search the blocks of DirX for FileY Data for FileB 0 Free Data for FileB 1 Free Data for FileD 0 Data for FileD 9 Indirs for FileD Data for FileD 10 Data for FileD 11 FileX Each search operation has to sequentially read the blocks of the directory being examined FileY Empty DirF FileZ Opening DirX FileY Step 1 Read first block of root directory the superblock is always in memory 15 Blk 0 Blk 0 Superblock Root Dir FileB Empty FileD DirX Free Data for FileB 1 FileB Empty Free FileD Data for FileD 0 DirX Data for FileD 9 Data for FileD 10 FileY Empty DirF Data for FileB 0 Free Data for FileB 1 Free Data for FileD 0 Data for FileD 9 Indirs for FileD Data for FileD 11 FileX Free Data for FileA 0 FileA Data for FileB 0 Indirs for FileD Superblock Root Dir Free Data for FileA 0 FileA 16 Data for FileD 10 Data for FileD 11 Opening DirX FileY FileX Step 2 Check 1st entry of root directory for DirX Empty FileY DirF FileZ FileZ Opening DirX FileY Step 3 Check 2nd entry of …