CS 111 Scribe Notes

Lec 12: File System Design and Implementation

 

File System – A data structure on disk that provides an abstraction of a collection of files

* On Unix, a regular file is a string of bytes

 

A simple file system (File is a contiguous region on disk)

 

Directory entry contains (a bit saying “in use”)

            File descriptors- name

                                                - location

                                                - size è current and allocated

Free space = what’s not in a file

Strengths

      +          Its simplicity allows it to run fast, especially for sequential access to 1 file

Weaknesses

-                     Files can’t easily grow, are fixed in size

-                     Limit on number of files, due to a fixed limit on directory size

-                     No sub-directories or levels of indirection

-                     Contains a lot of external fragmentation

 

FAT (File Allocation Table)~late 1970’s

First block is the boot sector.

Second block is the superblock, which contains

• Version #
• Size of the File System
• The amount of used space
• Location of root

Third block is the FAT, which is represented as an array of block numbers that each contain an integer value:

·        -1 à  block is free

·        0   à  block is at the end of file (EOF)

·        N  à  block contains a pointer to the next block, block number N

Directory in FAT: file name(11 bytes), size, first block number

Internal Fragmentation:  < 4 KiB per file

External Fragmentation:   0

 

Strengths:

     +          easy to grow files, data location is not fixed

     +          eliminates all external fragmentation

Weaknesses

-                     slow access: in worst case, O(N) accesses per block for a file of N blocks

 

Traditional Unix/BSD File System (cerca 1982)

 

Symbolic Links

Absolute vs. Relative file names

File names

File name components (everything in between /, e.g. /user/cs111/)

Inodes + access

Directories

---------------------------------------------------------file system line

Partitions

Blocks (8 KiB)

Sectors (512 bytes)

Sidebar:

            How to Delete a File system safely

1)                  $ rm music

Removes the file named music.  Normally done by zeroing out all of the data.  May seem to delete file, but the deleted data is still stored in a buffer and can be recovered.

2)                  $ shred music

Shreds the file named music.  Command writes over the data in the file randomly, and then deletes the data.  Harder to recover the shredded data, but location where data was shredded can be easily found.

3)                  $ shred /dev/sda1

Shreds the contents of the entire disk.  Runs extremely slowly, and can be stopped by cutting the power, but will successfully permanently delete all data, making it unrecoverable.

===============================================================

 

Typical BSD/Unix File System Layout

First block is the boot sector.

Second block is the superblock, which contains;

• Version #
• Size of regions
• Timestamps

Third block is the free-block bitmap, which contains an array of bits, with each bit representing a different data block.  1 means the block is in use, 0 means the block is free.

After the free-block bitmap are the inode blocks.\

 

First inode represents the root directory, inodes are indexed by inode number

Inode entry: size, type, owner, group, permissions, link count, time stamps

 

Modern file systems use fancier data structures, like B+ trees for examples

 

We want:

• Seeks to be fast
• Inodes to be small, fixed in size
• Large files, so we can hold a lot of data

 

Possible solutions:

1)                  Linked lists (but as we saw with the FAT, seeks would then be slow)

2)                  Large files (but this would require large inodes)

3)                  Small inodes (but this would cause small files, in which we couldn’t store much data)

 

The size of a file is represented by the inodes

            = 32 GiB + 16 MiB + 80 KiB

 

Internal Fragmentation

            For a 1-byte file = 8191 bytes (in data) + 44 bytes (in inode)

            80 KiB + 1-byte file = 8191 bytes + 44 bytes + 8188 bytes (in indirect block)

 

Limitations of File System

            ~ 32 GB/file

 

            If using 32-bit pointers (standard), 13 bit/block

                        2³² * 2¹³ bytes in file system

                                    = 2⁴⁵ = 16 TiB

           

            If using 64-bit pointers

            +  increase in file size (can point to more data)

            -  decreases the number of blocks & efficiency (need more space to hold pointers)

 

Directory Entry: name (14 bytes), inode number (2 bytes)

 

Linux ext3v2 directory entry:

Specifications:

• 32-bit inode #
• 16-bit directory entry length
• 8-bit namelength
• 8-bit file type(cache for what appears in inode, purely for performance)

Features:

• Directories can be bigger than a block (8192 bytes)
• Typically don’t span block boundaries
• O(N) time to access a file in a directory containing N files
• Many fancier file systems use an index in the directory

Inode Properties:

• 1 inode per file
• Inode does not tell you the file’s name or the file’s parent directory

 

We want:

• Renaming to be easy (1 disk write in common case)
• Hard links – multiple names for some file

 

Unix File System