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