Unix Filesystem Organization

``Old'' (Original) file system

In the original Unix file system, Unix divided physical disks into logical disks called partitions. Each partition is a standalone file system. We will use the term ``file system'' when referring to a single partition.

Each disk device is given its own major device number, and each partition has an associated minor device number which the device driver uses to access the raw file system.

The major/minor device number combination serves as a handle into the device switch table. That is, the major number acts as an index, and the minor number is passed as an argument to the driver routines so that they can recognize the specific instance of a device.

Each filesystem contains:

1.
a boot block located in the first few sectors of a file system. The boot block contains the initial bootstrap program used to load the operating system.

Typically, the first sector contains a bootstrap program that reads in a larger bootstrap program from the next few sectors, and so forth.

2.
a super block describes the state of the file system: the total size of the partition, the block size, pointers to a list of free blocks, the inode number of the root directory, magic number, etc.

3.
a linear array of inodes (short for ``index nodes''). There is a one to one mapping of files to inodes and vice versa. An inode is identified by its ``inode number'', which contains the information needed to find the inode itself on the disk

Thus, while users think of files in terms of file names, Unix thinks of files in terms of inodes.

4.
data blocks blocks containing the actual contents of files

---------------------------------------------------------------
|          |           | | | | | | | |        |  |  |  |      |
| B. B.    | S. B.     | Inodes  | | | ...    |  Data Blocks  |
|          |           | | | | | | | |        |  |  |  |      |
---------------------------------------------------------------

An inode is the ``handle'' to a file and contains the following information:

An integral number of inodes fits in a single data block.

Information the inode does not contain:

Example

Look at /cs/bin/

< wpi /cs/bin 1 >ls -l
total 192
drwx------   2 mvoorhis csadmin     4096 Jan 16  2001 archives/
-rws--x---   1 root     771        32768 Jan 18  1999 csquotamgr*
-rwx------   1 csadmin  csadmin      162 Jan 12  1998 genQuota*
-rwx------   1 csadmin  csadmin       46 Feb 16  1998 generic*
drwxrwx---   2 mvoorhis csadmin     4096 Oct 29 10:23 gredStuff/
-rwx------   1 mvoorhis 1067         672 Jan 20  2000 list1*
-rwx------   1 mvoorhis 1067         859 Jan 20  2000 list2*
-rwx------   1 csadmin  646          140 Jan 10  2000 reclaim*
-rwxrwx---   1 csadmin  csadmin     1635 Sep 26  1995 stp_create_system.pl*
-rwxrwxr-x   1 csadmin  csadmin      725 Sep 26  1995 stp_default_system.pl*
-rw-rw-r--   1 csadmin  csadmin      114 Feb 10  1995 stp_setup
drwx------  14 mvoorhis csadmin     4096 Oct 30 14:57 tDir/
-rwsr-xr-x   1 mvoorhis 1067      114688 Nov  8 10:10 turnin*
drwxr-xr-x   2 root     771         4096 May 26  1999 utility/

Internally, Unix stores directories in files. The file type (of the inode) is marked ``directory'', and the file contains pairs of name/inode numbers.

For example, when a user issues open(``/etc/passwd'', ...) the kernel performs the following operations:

1.
because the file name is a full path name, find the inode of the root directory (found in superblock) and search the corresponding file for the entry ``etc''
2.
when the entry ``etc'' is found, fetch its corresponding inode and check that it is of type directory
3.
scan the file associated with ``/etc'' looking for ``passwd''
4.
finally, fetch the inode associated with passwd's directory entry, verify that it is a regular file, and start accessing the file.

Note: What would the system do when opening ``/dev/tty01''?

Eventually, the system would find the inode corresponding to the device, and note that its file type was ``special''. Thus, it would extract the major/minor device number pair from the length field of the inode, and use the device number as an index into the device switch table.

Getwd()

How to get string of current directory? Have only the inode of the current directory.

get current inode
while (inode != root inode) {
    get inode of parent from ..
    search parent's directory file to match our inode number

Where should a file's data blocks be physically located?

The Unix file system allocates data blocks (blocks that contain a file's contents) one at a time from a pool of free blocks. Unix uses 4K blocks. Moreover, a file's blocks are scattered randomly within the physical disk.

Inodes include pointers to the data blocks. Each inode contains 15 pointers:

-------------------------------
| | | | | | | | | | | | | | | |
-------------------------------
 | | | | | | | | | | | | | | |--------------------------
      data blocks        | |-----------|               |
                         |             |               |
                       -----         -----           -----
                       |   |         |   |           |   |
                       -----         -----           -----
                        |||           |||             |||
                        data         -----           -----
                                     |   |           |   |
                                     -----           -----
                                      |||             |||
                                      data           -----
                                                     |   |
                                                     -----
                                                      |||
                                                      data
with 4K blocks:
direct 12x4K = 48K
indirect 1024x4K = 4MB
double indirect 1024x1024x4K = 4GB
triple indirect 1024x1024x1024x4K = 4TB

Advantages:

Disadvantages:

The Berkeley Fast File System

The Berkeley Fast File System used the following principles to improve the performance (and reliability) of the file system:

A data structure within each cylinder group contains status information about the blocks stored within that group:

1.
a bit map of blocks and fragments indicates which blocks and fragments are free
2.
a list of inodes within the cylinder group (why?)
3.
duplicate copy of the superblock (stored on a different platter for each cylinder group. why?)

When allocating space, the fast file system uses a global policy to determine where to place new directories and files. For example:

The fast file system also uses a local policy to allocate blocks at the lower levels. For instance:

The new file system increased the throughput to as much as 30% of the raw bandwidth.

Linux ext2fs

The 2nd extended file system. Same standard file system as Unix.

Similar to the Berkeley fast file system, but does not use fragments. Rather it uses smaller block sizes (1K, but can be 2K or 4K).

Tries to cluster disk blocks so that a single I/O request can read multiple blocks.

Modern disk technologies pack sectors onto disks at different densities--Linux uses variable size block groups (like cylinder groups in BSD FFS).

Allocation:

Also has a proc file system to allow access to process information through the file system interface.

Also supports other file systems such as FAT and NTFS.

File Mounting

When the system initially boots, the only file system Unix knows about is the root partition from which the system was booted. A special system call:

mount(special, path_name, options)
mounts the filesystem given by special at the point path_name in the root filesystem, thus allowing multiple file systems to be merged into a single global tree.

Internally, the kernel maintains a mount table that keeps information about the mounted file systems. Each entry in the table contains:

As the kernel is translating a path name, it consults the mount table as needed.

In Memory Data Structures

The kernel maintains a system-wide file table that describes open files. Each entry in the file table contains:

Finally, each process maintains a user file table that describes the files opened by the process. Entries in the user file table point to the system-wide file table.

Thus, a process can have its own private read/write mark (the default when a file is initially opened), or it can share a read/write mark (as is the case when a new process is created via fork).

Caching

Unix relies heavily on caching to improve performance. It keeps in memory: