Filesystem Implementation

Tom Kelliher, CS42

Nov. 22, 1996

For Monday: Chapter 13, Protection.

Filesystem Organization

Layered design:

1. Raw devices: floppies, Hard disks (IDE, SCSI, ...), CD-ROM, ...

2. Device drivers.

3. Block I/O system.

4. Filesystem.

5. Applications.

Design Strategies

1. Part of kernel; privileged, trusted code.

2. User-level task; unprivileged, untrusted. User-replaceable

Filesystem Data Structures

1. Block cache.

2. Directory entry table (information for finding a file's blocks).

3. System open file table (current position within file)

4. Process open file table.

5. Free list.

Consider: open, read, write (delayed disk updates).

Mounting a Filesystem

1. Disk, partition.

2. DOS format.

3. Does the OS automatically see the filesystem?

4. Filesystem tree: hierarchical mounts:

   keystone:~
   % mount
   /dev/wd0a on / (local)
   /dev/wd0h on /home1 (NFS exported, local, with quotas)
   /dev/sd0g on /home2 (NFS exported, local, with quotas)
   /dev/sd0h on /usr (NFS exported, local)
   mfs:84 on /tmp (asynchronous, local)
   

5. Filesystem trees: drive letters.

Disk Block Allocation Methods

Sector, block correspondence:

1. Sector: 512 bytes.

2. Original sector pointer (FAT) in DOS: 12 bits. Maximum disk size?

3. ``Improved'' sector pointer: 16 bits. Max disk size?

4. How do we use DOS with a 1 GB disk?

Contiguous Allocation

1. All blocks of file are allocated in one contiguous group.

2. Initial placement: best-, worst- first-fit.

3. Pre-declaration of maximum size. Wrong guess?

4. External, internal fragmentation. Compaction.

5. Overhead? Sequential-access files? Direct-access files? Reliability? Performance?

Linked Allocation

1. Blocks of file may be scattered over disk.

2. Each data block contains a pointer to the next data block.

3. Fragmentation?

4. Pointer overhead. Clustering blocks.

5. Sequential-access files? Direct-access files? Reliability?

DOS FAT

Table of block, next block pairs at beginning of partition. Redundancy.

Indexed Allocation

1. Collect all block pointers into an index table.

2. Pointer overhead. Unix's solution

3. Very large files and multiple index blocks. How are they linked?

4. Sequential-access files? Direct-access files? Reliability?

Free Space Management

1. Bit vector.

2. Free list. A block on the free list contains a pointer to the next block, etc.

   Variations:

   1. Grouping. A free list block contains multiple pointers.

   2. Counting. Free list blocks are ``clustered.''

Directory Implementation

1. List.

2. Sorted list.

3. Hashed.

Performance

1. LRU replacement from block cache.

2. Free-behind, read-ahead for sequential access.

3. AI for predicting head movements.

Filesystem Integrity

1. Maintain consistency at all costs by updating data structures before data.

2. Lazy writes from block cache. Update and sync.

3. Inconsistencies caught by fsck at start-up:
   1. Unreferenced inodes.

   2. Link counts in inodes too large.

   3. Missing blocks in the free map.

   4. Blocks in the free map also in files.

   5. Counts in the super-block wrong.