The second extended file system also implements I-nodes. Each file on the disk is associated with one I-node. An I-node contains information on the file such as its creation date and time, its permission, and pointers to the files location on disk. The most important feature of an I-node is the pointers it contains. This principal is detailed by Appleton (1997, p.3) who tells us that an I-node has 15 pointers. The first thirteen point directly to blocks of data on the disk. However, if the file is larger than this then the 14th pointer can be used which points firstly to an indirect block, which then points directly to files thus allowing it another 13 blocks. The 15th pointer is a double indirect pointer and points to many indirect blocks all pointing directly to data. This allows a file to be millions of blocks. This is best illustrated with a diagram as shown below.
Another feature of Ext2FS is that it uses bitmaps to track free blocks. A bitmap is an array of bits that refers to a block in the partition. Each bit holds data about the block it points to. A ‘1’ for example would mean the block is being use whilst a ‘0’ would indicate a free block.
To offer a more ‘user-tailored’ file system, Ext2FS allows the selection of the logical block size when first creating the file system. Larger block sizes mean faster seek times due to the fewer amounts of reads needing to be made but also decreases disk space as only around half the space in the last block of a file is used. Using smaller block sizes increases free space but also means greater seek times.
Journal file systems
We will now move on to discuss Journal file systems. These are considered to be the future of file systems in Linux. Described by Florido (2000, p. 5) the principal is that a Journal allows the file system to quickly recover after a system crash. They implement database recovery technology rather than using older, slower file system methods. The need arose because when the system writes to a cache to temporarily store data, if the system crashes before it writes this to disk then there are inconsistencies in the system. In file systems using older techniques the system would have to scan the entire partition to recover the system. This is acceptable on machines with small drives, but on servers or machines with hundreds of gigabytes of data it can take a long time.
The journal works by using transactions. These transactions must satisfy the rules known as ACID (Atomicity, Consistency, Isolation, and Durability). Atomicity implies ‘operations belonging to a single transaction…’ must be ‘completed without errors or cancelled, producing no changes.’ Florido (2000, p. 5)
This treats the transactions as though they cannot be partially executed. A log is held containing the operations content before execution. If the execution is interrupted then the system can search the log and load the systems state before the crash took place. This reduces system recovery time immensely. All of the following file systems take advantage of the journal.
Ext3FS
Ext3 is short for extended files system version 3. This is the standard Linux file system and is essentially ext2 with journaling. It offers the core features used in its predecessor whilst providing the advantages of the modern journal technology. This allows for improved reliability and shorter recovery times. The main selling point of Ext3FS is that it offers backwards compatibility for people who still rely on old file systems such as Ext2FS. The advantage to keeping Ext2FS’ core design is that you can switch form Ext3FS back to Ext2FS and vice versa by mounting the new file system without the need for a disk format. The main features of the Ext3FS are covered in the Ext2FS section of this document.
XFS
XFS is again a journal file system. Rather than using I-nodes and bitmaps, the XFS implements a tree structure called B+Tree short for balanced tree. The B+Tree uses internal I-nodes and leaf I-nodes. Florido (2000, p. 3-4) explains that an internal I-node points to other internal nodes or leaf node. The leaf node is the final pointer and thus points directly to the file being accessed. Each I-node contains a key that contains information about the information within the tree. The XFS uses multiple trees to map the system.
XFS also takes advantage of extents. An extent is a set of blocks consisting of a beginning, extent size, and offset. The beginning is the block address where the extent begins, the size is the size of the extent (measured in blocks), and the offset is where the first block of the extent begins within the file i.e. does it begin at the start of the file or part of the way through the file. This removes the need for a bitmap and having a bit for every block. Information is stored about a set of blocks and so conserves space and increases access times. An extent usually works in conjunction with the B+Tree and so an extent may be pointed to by an I-node.
JFS
Developed by IBM for use in their enterprise servers, JFS is short for journal file system. JFS implements a modified version of the B+Tree. Rather than using extents to track free space, JFS uses bitmaps. The bitmaps are 32 bit with each bit representing the status of the block it points to. Whilst JFS uses old bitmap techniques to track free space, it relies heavily on extents to address file blocks. JFS doesn’t fix space for I-nodes when the file system is installed; instead it changes the space as required by the system. This means that disk usage is much more efficient. This is explained in greater detail by Best (2002, p. 4).
ReiserFS
ReiserFS is an independent file system created by Hans Reiser. The latest version available is Reiser4, which offers some improvements in stability and performance over previous versions. ReiserFS is a Journal files system and as such takes advantage of the recovery system available to journal file systems. ReiserFS offers a third generation Btree known as the B*Tree. Florido (2000, p. 10-11) goes on to explain that the mapping used in this file system differs from that of the B+Tree in that there is a single tree that contains sub trees rather than having lots of B+Trees.
This gives the file system an increase in performance when accessing files. ResiserFS has had support for extents since version 4 but before that made use of the bitmap based free-block system. The extent system gives ReiserFS the same advantages of the other file systems mention above. It offers a fast search through a set of block rather than searching individual nodes as detailed by Namesys.com (chapter 3.3.2).
Comparison of the file systems
Now I have described a selection of files systems available for Linux, this section will compare and contrast them. FAT32 and its predecessors are generally used with Windows with Linux providing support mainly to encourage integration between the two operating systems. Because of this I will leave FAT32 out of this comparison.
Since the advantages of using Journal file systems have already been made clear we will use Ext3FS as our basis with which to compare the other file systems. This is because Ext2FS and its journal brother Ext3FS are by far the most popular file systems in Linux.
The table below summarises support offered by each file system.
Firstly we will compare Ext3FS with XFS. As mentioned beforeExt3FS use I-nodes to access files. On large partitions this method can mean that many I-nodes have to be accessed before reaching the file. This can cause slower seek times on systems with large disk drives. Comparing this method with the B+Tree method used in the XFS we can see that the XFS seems to have the advantage. The B+Tree method involves searching whole blocks rather than individual pointers. This method involves fewer disk seeks and is more consistent due to the balanced nature of the B+tree.
Another technology XFS takes advantage of is Extents. If we consider the Old style Bitmaps used in Ext3FS. The bitmap contains a bit for every block on the partition. This means that as the partition size grows, so does the bitmap to cater for the increased number of bits as detailed by Florido (2000, p. 7). This causes a performance decrease searching the bitmap on systems with large partitions. In newer file systems such as XFS, extents are used instead of bitmaps. Extents improve on Bitmaps because they point to a set of blocks rather than just a single block. The advantage to using extents is that they save space, as they don’t hold a bit for every block. This method also reduces access time because the system doesn’t have to search every block. XFS offers all of the future technologies and is very useful for servers with large disk partitions. Many of its features won’t benefit the personal user much, although with larger disks being welcomed by home users the need for a file system like XFS is obvious.
Let us move on to compare XFS with JFS. JFS uses a modified version of the B+Tree used in XFS. JFS uses a system where internal I-nodes in the B+Tree point to bitmaps when locating free space. It does not fully support extents and instead uses them solely for the purpose of addressing blocks. This somewhat limits the functionality of the B+Tree. XFS offers greater speed and space management features by fully incorporating extents into its use of the B+Tree. JFS is a ‘mid-road’ file system offering some new features whilst sticking with older, trusted methods. This file system is really for Enterprise level servers and is developed with IBM’s customer base in mind.
With XFS firmly leading the way in system enhancing features, let us compare it with ReiserFS. ReiserFS uses the third generation of B+Tree known as B*Tree. This method doesn’t incorporate multiple Trees but instead uses a main tree with sub trees stemming from it. This gives the file system a greater level of complexity but also decreases access times making it the fastest file system available for Linux as detailed here (). ReiserFS is perhaps one of the most technologically evolving file systems. It implements the advanced B*Tree and has released support for extents in version 4. With distributions such as SUSE using ReiserFS as its standard file system it seems that home users are craving some enterprise level features available from more advanced file systems
Conclusion
Whilst I have not covered all of the file systems, I have covered the ‘main-stream’ file systems available for Linux. Linux is an operating system that is available in many ‘flavours’. It is intended to be tailored towards individual users by offering an unprecedented amount of flexibility. This flexibility also reaches to the file system. All of the file systems I have reviewed for Linux are based on a group of people ideas as to how a file system should operate. Linux is about finding a file system that suits your needs. Ext3FS is clearly holding onto its predecessor’s features too much and without the adoption of new techniques file systems like XFS and ReiserFS will quickly become take its place as standard for the home user. For the time being however, Ext3FS is still the preferred file system for home users. It offers enough support for large drives to be viable and its journal capabilities enable it to recover quickly from crashes.
References
, 29 October 2003
Appleton, R. (1997). ‘A Non-Technical Look Inside the EXT2 File System’. Linux Gazette (no. 21), 2-3.
Florido, J. L. S. (2000). ‘Journal File Systems’. Linux Gazette (no. 55), 2-10.
, 2 November 2003
Best, S. (2002). ‘JFS for Linux’, Free Software Magazine (Feb 2002 issue)
, 30 October 2003
Bibliography
Ellis, S. and Raithel, J. (1994). ‘Getting Started with XFS Filesystems’. Silicon Graphics (Doc No. 007-2549-001)
http://support.microsoft.com/default.aspx?scid=http://support.microsoft.com:80/support/kb/articles/q154/9/97.asp&NoWebContent=1, 2 November 2003
, 26 October 2003
Muller, G. (1999). ‘A Visual Introduction to Linux’, Philips Research (version 2.2)
