FileSystem

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
2. Group ID
3. Last modified time
4. Last accessed time
5. Count of hard links
6. Type of file (Plain, directory, symbolic link, character device, block device or socket)
7. 15 Pointers
   1. First twelve point to Direct Blocks or Data Blocks.

   2. Pointer 13 points to a single indirect block of pointers or a block of pointers to Direct Blocks One level of indirection

   3. Pointer 14 points to a double indirect block of pointers or a block of pointers to single indirect blocks Second level of indirection

   4. 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