STRUCTURE FILE SYSTEM

The file system structure is the most basic level of organization in an operating system. Almost all of the ways an operating system interacts with its users, applications, and security model are dependent upon the way it organizes files on storage devices. Providing a common file system structure ensures users and programs are able to access and write files.

FAT16
This is the 16-bit version of the FAT file system. The 16-bit part describes the way units are allocated on the drive. The FAT16 file system uses a 16-bit number to identify each allocation unit (called cluster), and this gives it a total of 65.536 clusters. The size of each cluster is defined in the boot sector of the volume (volume = partition). The File System ID number usually associated with FAT16 volumes are 04h and 06h. The first is used on volumes with less than 65536 sectors (typical this is on drives less than 32 Mb in size), and the latter one is used on volumes with more than 65536 sectors.

The first sector (boot sector) contain information which is used to calculate the sizes and locations of the other regions. The boot sector also contain code to boot the operating system installed on the volume. The data region is split up into logical blocks called clusters. Each of these clusters has an accompanying entry in the FAT region. The cluster specific entry can either contain a value of the next cluster which contain data from the file, or a so called End-of-file value which means that there are no more clusters which contain data from the file. The root directory and its sub-directories contain filename, dates, attribute flags and starting cluster information about the filesystem objects.

FAT32

The first step to reading the FAT32 filesystem is the read its first sector, called the Volume ID. The Volume ID is read using the LBA Begin address found from the partition table. From this sector, you will extract information that tells you everything you need to know about the physical layout of the FAT32 filesystem.

Microsoft's specification lists many variables, and the FAT32 Volume ID is slightly different than the older ones used for FAT16 and FAT12. Fortunately, most of the information is not needed for simple code. Only four variables are required, and three others should be checked to make sure they have the expected values.

After checking the three fields to make sure the filesystem is using 512 byte sectors, 2 FATs, and has a correct signature, you may want to "boil down" these variables read from the MBR and Volume ID into just four simple numbers that are needed for accessing the FAT32 filesystem. Here are simple formulas in C syntax:

(unsigned long)fat_begin_lba = Partition_LBA_Begin + Number_of_Reserved_Sectors;

(unsigned long)cluster_begin_lba = Partition_LBA_Begin + Number_of_Reserved_Sectors + (Number_of_FATs * Sectors_Per_FAT);

(unsigned char)sectors_per_cluster = BPB_SecPerClus;

(unsigned long)root_dir_first_cluster = BPB_RootClus;

As you can see, most of the information is needed only to learn the location of the first cluster and the FAT. You will need to remember the size of the clusters and where the root directory is located, but the other information is usually not needed (at least for simply reading files).

If you compare these formulas to the ones in Microsoft's specification, you should notice two differences. They lack "Root Dir Sectors", because FAT32 stores the root directory the same way as files and subdirectories, so RootDirSectors is always zero with FAT32. For FAT16 and FAT12, this extra step is needed to compute the special space allocated for the root directory.

Microsoft's formulas do not show the "Partition_LBA_Begin" term. Their formulas are all relative to the beginning of the filesystem, which they don't explicitly state very well. You must add the "Partition_LBA_Begin" term found from the MBR to compute correct LBA addresses for the IDE interface, because to the drive the MBR is at zero, not the Volume ID. Not adding Partition_LBA_Begin is one of the most common errors most developers make, so especially if you are using Microsoft's spec, do not forget to add this for correct LBA addressing.

The rest of this page will usually refer to "fat_begin_lba", "cluster_begin_lba", "sectors_per_cluster", and "root_dir_first_cluster", rather than the individual fields from the MBR and Volume ID, because it is easiest to compute these numbers when starting up and then you no longer need all the details from the MBR and Volume ID. 

NTFS

Let's start with the common facts. The NTFS partition theoretically can be almost of any size. The limit certainly exists but I shall not point at it as it will be more than enough for the next hundreds of years of computer technology development at any growth rates. What about practice? Almost the same way. The maximum size of the partition NTFS at the moment is limited only by the hard disks sizes. NT4 probably will have some problems at the attempt of installation on the partition if any of its parts steps back more than on 8 GBytes from the disk physical beginning but this problem concerns only the load partition.

The way of NT4.0 installation on the empty disk is rather original and can lead to incorrect thoughts about NTFS possibilities. If you point the installation program that you wish to format disk in NTFS, maximum size which it will offer you will be only 4 GBytes. Why it is so little if NTFS partition size actually is unlimited? The answer is that installation section simply does not know this file system. The installation program formats this disk in usual FAT which maximum size in NT is 4 GByte (with usage of not absolutely standard huge cluster 64 KByte) NT is installed on this FAT. And during the first operating system load (in the installation phase) the fast partition conversion to NTFS is effected so that user notice nothing except the strange "limiting" on the NTFS size at the installation time.

As well as any other system NTFS divides all useful place into clusters -- data blocks used at a time. NTFS supports almost all sizes of clusters -- from 512 bytes up to 64 KBytes. The 4 KBytes cluster is considered to be some standard. NTFS doesn't have any anomalies of cluster structure and I have nothing to say about it.

NTFS disk is symbolically divided into two parts. The first 12% of the disk are assigned to so-called MFT area -- the space which MFT metafile grows into. Any data recording into this area is impossible. The MFT-area is always kept empty not to let the most important service file (MFT) be fragmented at growth. The rest 88% of the disks represent usual space for files storage.

Disk free space however includes all physically free space -- free pieces of MFT-area are included there too. The mechanism of MFT-area usage is like this: when files already cannot be recorded in usual space, MFT-area is simply reduced (in operating systems current versions -twice) clearing the space for recording files. At clearing the usual area, MFT can be extended again. Thus it is possible for usual files to remain in this area and it is normal. The system tried to keep it free but failed. The metafile MFT all the same can be fragmented though it would be undesirable.

EXT2

The physical structure of Ext2 filesystems has been strongly influenced by the layout of the BSD filesystem. A filesystem is made up of block groups. Block groups are analogous to BSD FFS's cylinder groups. However, block groups are not tied to the physical layout of the blocks on the disk, since modern drives tend to be optimized for sequential access and hide their physical geometry to the operating system.

,---------+---------+---------+---------+---------,
| Boot    | Block   | Block   |   ...   | Block   |
| sector  | group 1 | group 2 |         | group n |
`---------+---------+---------+---------+---------'

Each block group contains a redundant copy of crucial filesystem control informations (superblock and the filesystem descriptors) and also contains a part of the filesystem (a block bitmap, an inode bitmap, a piece of the inode table, and data blocks). The structure of a block group is represented in this table:

,---------+---------+---------+---------+---------+---------,
| Super   | FS      | Block   | Inode   | Inode   | Data    |
| block   | desc.   | bitmap  | bitmap  | table   | blocks  |
`---------+---------+---------+---------+---------+---------'

Using block groups is a big win in terms of reliability: since the control structures are replicated in each block group, it is easy to recover from a filesystem where the superblock has been corrupted. This structure also helps to get good performances: by reducing the distance between the inode table and the data blocks, it is possible to reduce the disk head seeks during I/O on files.
In Ext2fs, directories are managed as linked lists of variable length entries. Each entry contains the inode number, the entry length, the file name and its length. By using variable length entries, it is possible to implement long file names without wasting disk space in directories.

 

EXT3

Ext3 file system is the development of the earlier ext2 file system,
by adding journaling feature. Ext3 became the most popular file system in Linux, and usually the default choice for a new installation.
Such as ReiserFS, Ext3 also uses block structure. Block size the same throughout the file system, depending on the size of the file system, however,
The default rates are among the 1024 or 4096 bytes. 1024 The first byte of the ext3 file system is always in use. If there is in the file system boot kernel, then bytes will contain the boot information.
Superblock on ext3 file system stores general information such as name, size, and the data is used when the last time. Ext3 file system has only one primary superblock, although it could be his backup copy can also be stored along the file system.

 

Ext3 file system to put metadata file in a data structure called inodes. Inodes are stored in special blocks called inode tables. Standard length of an inode is 256 bytes. Each inode structure can accommodate up to twelve direct pointers, which are associated with the addresses of the block file system where the first twelve blocks of a file is placed. If the file is too large to be put on the first twelve blocks (usually 12 KB or 48 KB), then the pointer will be used to single, double, and triple indirect pointer blocks. A single indirect block pointer is the address of the file system that consists of all direct pointer. Next, double and triple indirect block pointer points to the file system that contains single and double pointer iDirect.

 

The blocks on ext3 compiled into block groups. Block groups are described in a block or block group named "the group descriptor table", which always follows the superblock or a copy of the superblock.
Each block group contains two bitmap blocks, one for blocks and the other for the inode. Each bit in the bitmap block indicates the status of one of the blocks or inodes in the group is whether allocated or unallocated. Block and the inode associated in older version of a content file or a file is deleted. Blocks that have not been allocated is represented by "0", while containing the content of a file or metadata, and are used by the file system is represented by "1".