Structure and Implementation of UFS Filesystem
        ==============================================
         Niraj Kumar <niraj17@iitbombay.org>, Dec. 2003
  
!!!! Note : This is still work-in-progress.


UFS On-disk structure
=====================

The whole disk :
    ---------------------------------
    |                               |
    --------------------------------

The whole disk with fdisk partitons:

    ----------------------------------------------------
   |     |     |   |-----------------------------------|
   |  1  |  2  | 3 | 5  | 6  | 7  |  ...  |           ||
   |     |     |   |-----------------------------------|
   -----------------------------------------------------

   Note : Parttion number 4 is extended partition , which contains
          partition number 5,6, etc .



Note :
1) fdisk partitions are called 'slice' in BSD world .
2) Within these slice , you may create a "BSD disklabel" .
This actions divides slice into so called 'BSD partitions' (in BSD terms).

There are 8 partition slots in a basic BSD disklabel, 
but not all of them are created equal. 
The slots are labeled with letters, starting with a. 
The first four have special meaning by convention. 
The a partition contains to the root file system. It also contains the disklabel itself, 
which is possible since the UFS superblock only starts at 8K into the partition.
 The b partition is used for swap space. 
The c partition slot refers to the whole disk (or slice, if applicable),
 but has the type set to Unused (0). 
Finally, the d partition slot is completely unused. 
The remaining slots are used for additional file systems, e.g. /usr or /var

3) UFS superblock only starts at 8K into the partition

4) UFS filesystem is divided into 'Cylinder groups' .
Of primary interest is the fact that multiple superblocks are made during the
mkfs procedure.
One of the replicas is stored in each cylinder group, offset by a certain
amount.
For multiple platter disk drives, the offsets are calculated so that a
superblock appears on each platter of the drive. 
If the first platter is lost, an alternate superblock can be retrieved. 
For platters other than the top one in a pack, the leading blocks 
created by the offsets are reclaimed for data storage.

Kept with the superblock is a summary information block. This block is not
replicated but is grouped together with the first superblock, normally in
cylinder group 0. This summary block record changes that take place as the
filesystem is used and lists the number of inodes, directories, fragments, and
blocks within the filesystem.


   Cylinder                  Cylinder              Cylinder
   Group 0                   Group 1               Group 2
  -------------           ----------------      -----------------
  | Bootblock |          | Offset        |      |  Offset        |
  |  (8k)     |          | (data blocks) |      |  (Data Blocks) |
  |-----------            ----------------      |                |
  | Super Block|          | Super Block  |      |----------------|
  |-------------          ----------------      | Super block    |
  |Cylinder   |           | Cylinder     |      |--------------- |
  |Group Map  |           | group Map    |      |  Cylinder      |
  |------------           ---------------       |  Group Map     |
  | Inodes    |           | Inodes       |      | ------------   |
  ------------            ---------------       | Inodes         |
  |           |           |              |      |--------------- |
  | Data blocks|          | Data Blocks  |      | Data Blocks    |
  |           |           |              |      |                |
  ------------            ---------------       -----------------
 

Another feature of ufs is the ``cylinder group map.'' This is a block of data
found in each cylinder group that records the block usage within the cylinder.
This information is kept directly following the superblock copy for that
cylinder group.

Another feature is the "fragment" size, and comes from UFS historically. UFS
has a "block" size and a "fragment" size.  "fundamental" means "the
unit in which the disk addresses are computed" and for UFS can be 512
or 1K.  blocks are 4K or 8K, and are used when files get larger and
it is more efficient to allocate in larger units.  But their addresses
kept on disk are still in terms of the fragment size...

The reason for the two sizes had to do with the Berkeley Fast File System,
which is known now as UFS.  It is more efficient for I/O and allocation on
large files to use larger block sizes.  It is a waste of space for smaller
files to use large block sizes.  So UFS uses small units (fragments) for
small files and as a file grows it starts allocating in larger units
(blocks).


UFS Implementation in Linux
============================

(fs/ufs/super.c)
static struct file_system_type ufs_fs_type = {
        .owner          = THIS_MODULE,
        .name           = "ufs",
        .get_sb         = ufs_get_sb,
        .kill_sb        = kill_block_super,
        .fs_flags       = FS_REQUIRES_DEV,
};



1) Reading the super_block :
  This is done by function ufs_get_sb , which in turn calls get_sb_bdev (fs/super.c) .
 It also passes the function ufs_fill_super as a parameter which is used
inside get_sb_bdev to fill the actual super_block.

Location of super block : ???  (8k from the begining of device)

ufs super_block size varies depending upon the type :
Type   super_block_size
44bsd   1536
sun     2048
sunx86  2048


------------------------------------------------------------
(fs/ufs/super.c)
static struct super_operations ufs_super_ops = {
        .alloc_inode    = ufs_alloc_inode,
        .destroy_inode  = ufs_destroy_inode,
        .read_inode     = ufs_read_inode,
        .write_inode    = ufs_write_inode,
        .delete_inode   = ufs_delete_inode,
        .put_super      = ufs_put_super,
        .write_super    = ufs_write_super,
        .statfs         = ufs_statfs,
        .remount_fs     = ufs_remount,
};