Ext3 Filesystem
Introduction
Common file system on linx
z Introduced in 2001
z Supports max file size of 16 GB to 2 TB
z Max filesystem size can be from 2 TB to 32
TB
z Maximum 32000 sbdirectories under a
directory
z Options for block size from 1 KB to 4 KB
z
Block Groups
z
Disk is partitioned into equal sized block
groups
z
z
Same number of inodes per block group
Same number of data blocks per block group
Each block group has data blocks and inodes
stored in adjacent tracks
z
z
z
Flies allocated within a single block group usually
Inodes and data blocks are close together
Reduces average seek time
Partition Layout
Superblock
z
located 1024 bytes from the start of the file system
and is 1024 bytes in size.
Back up copies are typically stored in the first file
data block of each block group
z
Only the one in block group 0 is looked at usually
Contains a description of the basic size and shape of this
file system.
Some Superblock Fields
z
z
z
z
z
z
z
z
Block group no. of group storing the superblock
Block size
Total no. of blocks
No. of free blocks
No. of inodes
Total [Link] free inodes
First inode (for /)
Many others, its a long list
The Ext3 Group Descriptor
z
z
One Group Descriptor data structure for every block group
All the group descriptors for all of the Block Groups are
duplicated in each Block Group in case of file system
corruption.
The Group Descriptor contains the following:
Blocks Bitmap : block number of block allocation bitmap
Inode Bitmap : block number of Inode allocation bitmap
Inode Table : The block number of the starting block for the
Inode table for this Block Group.
Free blocks count : number of data blocks free in the Group
Free Inodes count : number of Inodes free in the Group
Used directory count : number of inodes allocated to
directories
Bitmaps
z The
block bitmap manages the allocation status of the
blocks in the group
z The inode bitmap manages the allocation status of the
inodes in the group
z Both bitmaps must fit into one block each
z
Fixes the maximum no. of blocks in a block group as 8 times
the block size in bytes
Inodes
zInode
z
Tables:
Inode table contains the inodes that describe the files in the
group
zInodes:
z
Each inode corresponds to one file, and it stores files primary
metadata, such as files size, ownership, and temporal
information.
Inode is typically 128 bytes in size and is allocated to each
file and directory
12 direct links, one single, one double, and one triple indirect
link
Ext2 inode
Some inode fields
z
z
z
z
z
z
z
z
z
z
File type
Access rights
File length
Time of last file access
Time of last change of inode
Time of last change of file
Hard links counter
Number of data blocks
Pointers to data blocks
Access control lists
Directories
z An
Ext3 directory is just like a regular file except it has a
special type value.
z The content of directories is a list of directory entry data
structure, which describes file/subdirectory name and inode
address.
z The length of directory entry varies from 1 to 255 bytes.
z Fields in the directory entry:
z Inode: inode no. of file/directory
z Name length: the length of the file name
z Record length: the length of this directory entry
z
Tells where to start the next structure
File type
z Name: file/subdirectory name
z
Indexing and Directories
When Ext3 wants to delete a directory entry, it just increases the record
length of the previous entry to the end to deleted entry.
Allocating inodes
z If
a new inode is for a non-directory file, Ext3 allocates
an inode in the same block group as the parent
directory.
z If that group has no free inode or block,
z
z If
Quadratic search: search in block groups i mod (n), i+1 mod
(n), i + 1 + 2 mod (n), i + 1 + 2 + 4 mod (n)
quadratic search fails, Ext3 uses exhaustive linear
search to find a free inode
z If
a new inode is for a directory, Ext2 tries to place it in
a group that has not been used much.
z Using total number of free inodes and blocks in the
superblock, Ext3 calculates the average free inodes
and blocks per group.
z Ext3 searches each of the group and uses the first one
whose free inodes and blocks are less than the
average.
z If the pervious search fails, the group with the smallest
number of directories is used.
Allocating Data Blocks
zFirst
z
Goal
Get the new block near the last block allocated to the
file
zPreallocation
allocates a number of contiguous
blocks (usually 8) even if only one block is asked
for
z
Preallocated blocks are freed when the file is closed, or
when a write operation is not sequential with respect to
write operations that triggered the preallocation
Every allocation request has a goal block
z
If the current block and previously allocated block
have consecutive file block no., goal = logical block no.
of previous block + 1
z
Tries to keep consecutive file blocks adjacent on disk
Else, if at least one preallocated block earlier, goal =
that block
Else, goal = first block in the block group with the files
inode
Aim: allocate a physical block = goal block
z
z
If the goal block is not free, try the next one
If not available, search all block groups starting
from the one containing the goal block
z
z
Look for a group of 8 adjacent free blocks
If not, look for one
Indexing and Directories
zDirectory
z
entry allocation:
Ext2 starts at the beginning of the directory and examines
each directory entry.
Calculate the actual record length and compare with the
record length field.
If they are different, Ext2 can insert the new directory entry at
the end of the current entry.
Else, Ext2 appends the new entry to the end of the entry list.
Memory data Structures
z
Superblock and Group Descriptors are
always cached
Bitmaps (block and inode) and inode and
data blocks are cached dynamically as
needed when the corresponding object is in
use
z
Page cache mitigates some of the problem of
reading from disk
Main change in Ext3 over Ext2 add
journaling support for recovery
Not to be discussed today