Back to ComputerTerms Terms: * data blocks * block sizes max ratio 8:1 * Allocation Example * fragment recopying problem * inodes * direct blocks and indirect blocks, single, double and triple indirection * directories, hard links and symbolic links * mapping a file descriptor to an inode See Also DiskStructures == Data Blocks == Data blocks contain whatever the user put into them. There are two sizes in Free BSD, one '''large block size (LBS)''' and '''smaller fragment size (SFS)'''. {{{ LBS = n x SFS LBS > SFS n = LBS:SFS <= 8:1. }}} '''Allocation Example''' Suppose that LBS=8K and SFS=2K. Given a file of 18,000 bytes we would allocate {{{ 2 8K blocks + 1 2K block = 16384 + 2048 = 18,432 bytes. }}} When a file is being created and we insert 1K into it a fragment would be allocated. If we then continued later and added 2K, two fragments would be allocated and we would have to copy the first fragment. This can happen several times until we have copied the original fragment 7 times. Free BSD tries to avoid this by allocating a second fragment directly after the first one, but this can not always take place. This problem is known as the '''Fragment recopying problem'''. == Inodes == Inodes Contain: 1. User ID 1. Group ID 1. Last modified time 1. Last accessed time 1. Count of hard links 1. Type of file (Plain, directory, symbolic link, character device, block device or socket) 1. 15 Pointers 1. First twelve point to Direct Blocks or Data Blocks. 1. Pointer 13 points to a single indirect block of pointers or a block of pointers to Direct Blocks '''One level of indirection''' 1. Pointer 14 points to a double indirect block of pointers or a block of pointers to single indirect blocks '''Second level of indirection''' 1. Pointer 15 points to a triple indirect block of pointers or a block of pointers to double indirect blocks '''Triple level of indirection ''This level is not needed or used!'' ''' The minimum block size in Free BSD is 4K. File offset is a ''signed 32-bit'' number. So if we have 8K blocks, an inode can have {{{ Direct Block = 12*4K = 49,152 Single Indirect Block = 1K*4K = 4,194,304 Double Indirect Block = 1K*1K*4K = 4,294,967,296 ------------- 4,299,210,752 Since log2(4299210752) > 32, we got it covered and we don't need triple indirection. }}} In addition because we used signed numbers for file offset, we really only need to allocate 2 GB or 2^32-1 == Directories Hard Links and Symbolic Links == Directories are just a special type of file. * Always contain . and .. * Directory contents are in blocks just like file data * Each '''entry contains''' * length of the entry * File Name * Inode number * If the inode pointed to is a directory type, then it is a subdirectory Paths to subdirectories are searched linearly in a predictable fashion (guess the simplest way and you got it right). The only issue is when the path contains a symbolic or hard link. Since hard links point to the actual file or directory they can be traversed exactly like a normal subdirectory. Symbolic links have to be resolved and the path traversal restarted. '''To avoid infinite loops, the number of symbolic links in a path is limited to 8'''. == Mapping a File Descripter to an Inode == https://www.scotnpatti.com/unl/images/filesystemcontrolblocks.jpg File System Control Blocks When a user process opens a file, it requires a SystemCall because we don't let user processes muck up the FileSystem and/or we don't want to write file system functionality into every program. A '''file descriptor''' is returned to the user process which is uesed to index the table of open files for that process. An entry in table of open files contains a pointer to the file-structure. When a file is opened a file-structure table is allocated to point to the inode (or in-memory cache of the inode list). The reason for all this indirection is partially abstracting the user process from the underlying disk access and also because ''multiple users may open the same file''. Since the user can not make direct calls to the file, but must make system calls (of read, write, lseek etc.), the OS must also keep track of where each user is currently reading or writing in the file. This is the users offset in the file. If the file descriptor (user process) indexed an array of inode pointers instead of file pointers, the current offset would have to be kept in the inode itself. Since there is only one of these for a file, this means we could not have multiple users accessing the same file! The '''in-core (in-memory) copy and the inode on disk are different'''. The in-core copy has a fiew extra fields such as: ''count of haw many file structures are pointing at it''. When this count goes to zero, the entry is no longer needed and may be reclaimed and reused. Back to ComputerTerms