Diff for "FileSystem"

Differences between revisions 3 and 4

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

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:

User ID
Group ID
Last modified time
Last accessed time
Count of hard links
Type of file (Plain, directory, symbolic link, character device, block device or socket)
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     =      49152
Single Indirect Block = 1K*4K     =    4194304
Double Indirect Block = 1K*1K*4K  = 4294967296
                                    ----------
                                    4299210725

Since log2(4299210725) > 32, we got it covered and we 
don't need triple indirection.

Back to ComputerTerms

-  ⇤ ← Revision 3 as of 2004-03-31 17:50:16 → 
  Size: 1319
  Editor: yakko
  Comment:
+   ← Revision 4 as of 2004-03-31 18:22:06 → ⇥
  Size: 2590
  Editor: yakko
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 34:
+== Inodes ==
-Line 35:
+Line 36:
+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     =      49152
Single Indirect Block = 1K*4K     =    4194304
Double Indirect Block = 1K*1K*4K  = 4294967296
                                    ----------
                                    4299210725

Since log2(4299210725) > 32, we got it covered and we 
don't need triple indirection.
}}}