CSCE 313 Lecture 13

« previous | Thursday, March 1, 2012 | next »

File System Organization

Highest level: Partition

• Partitions can be made on a single disk or across multiple disks
• Directory and files are then stored in the partitions

Organize directory to find file quickly, group files by properties, naming (same name for multiple files, multiple names for same file)

Directory Structure

Single-Level

Directory is vector of links to files.

• Limited Filename length
• not multi-user friendly.

Two-Level

Master directory for users that points to user directory for each user's file that points to files

• Path names required to identify unique files.
• Where are system files?

Tree-Structured Directories

Almost traditional structure for UNIX and Linux machines.

• current directory
• complete and relative file paths
• search paths for $PATH variable.

Generalized Tree Structure

Same as above, but offers links so same file appears in multiple directories.

• links (referencing affects file to which it is linked)
• consistency, deletion, and privileges to create/access links

char * getcwd(char * buf, size_t size); Gets the current working directory (full path)

Logical View of File Management

1. User
2. File structure (Accessed by directory management and access control)
3. Records (accessed by an access method)
4. Physical blocks in memory
5. Physical blocks on disk

UNIX Implementation: inodes

An inode stores the following information:

• Size (in bytes)
• Owner UID and GID
• Relevant times (created, accessed, modified)
• link and block counts
• permissions
• "Multilevel allocation table" to actual file content

The Multilevel allocation table is a collection of blocks that point to relevant locations of file pieces on disk.

• Direct: block in MAT to block on disk
• Single indirect: block to another collection of blocks that point to blocks on disk.
• Double inderect, Triple indirect (yada yada)

inode size is fixed, so the MAT is limited in size.

Every system has a block size ($b$) Each index is $n$ bytes (a pointer is $p=1$ bytes) Largest file sizes:

• Direct: $nb$
• $n=\alpha +\beta$, where $\alpha$ direct and $\beta$ indirect: $\alpha b+\beta \cdot b\cdot b$
• $n=\alpha +\beta +\gamma$, where $\alpha$ direct, $\beta$ indirect, and $\gamma$ double indirect: $\alpha b+\beta \cdot b\cdot b+\gamma \cdot b^{2}\cdot b$
• In general, for $n_{0}$, $n_{1}$, $n_{2}$, ..., $n_{k}$ indirection levels (where $n_{0}$ is direct), the maximum size is $\sum _{i=0}^{k}bn_{i}\left({\frac {8b}{p}}\right)^{i}$

Note: filenames are not stored in inode. The names are stored in a directory file that contains the file name and the inode number of the associated file. There are two reasons for this:

1. Same inode can have multiple links on disk
2. Consistent inode block size.

Links

The link counter in inode only counts hard links.

To delete files, use unlink(char * path);. Once link counter reaches 0, the inode is removed.

Symbolic links do not update inode link counter, but it creates a new inode that stores the path of the actual file that it's referencing.

Note: ln [-s] original link creates links. Use -s for symbolic