Introduction to Filesystems

Tom Kelliher, CS42

Nov. 18, 1996

File Concept

1. What is a file?

2. What does it abstract?

3. Does the OS know a file's type?

File Baggage

From /usr/include/ufs/ufs/dinode.h:

#define  NDADDR   12       /* Direct addresses in inode. */
#define  NIADDR   3        /* Indirect addresses in inode. */

struct dinode {
   u_short     di_mode; /*   0: IFMT and permissions. */
   short    di_nlink;   /*   2: File link count. */
   union {
      u_short  oldids[2];  /*   4: Ffs: old user and group ids. */
      ino_t inumber; /*   4: Lfs: inode number. */
   } di_u;
   u_quad_t di_size; /*   8: File byte count. */
   struct timespec   di_atime;   /*  16: Last access time. */
   struct timespec   di_mtime;   /*  24: Last modified time. */
   struct timespec   di_ctime;   /*  32: Last inode change time. */
   daddr_t     di_db[NDADDR]; /*  40: Direct disk blocks. */
   daddr_t     di_ib[NIADDR]; /*  88: Indirect disk blocks. */
   u_long      di_flags;   /* 100: Status flags (chflags). */
   u_long      di_blocks;  /* 104: Blocks actually held. */
   long     di_gen;     /* 108: Generation number. */
   u_long      di_uid;     /* 112: File owner. */
   u_long      di_gid;     /* 116: File group. */
   long     di_spare[2];   /* 120: Reserved; currently unused */
};

• Size of an inode: 128 bytes.

• Missing: file type. Magic numbers. Gleaning the type of an executable.

File Operations

1. Open, close, sequential read, sequential write, seek, truncate.

2. Is this a sufficient set?

Open Files Bookkeeping

1. Per-process open file table:
   1. Index is fd.

   2. Pointer into system open file table.

   3. Shared on fork.

2. System open file table:
   1. Current file offset.

   2. Pointer to in-memory inode entry.

   3. Several entries may point to same inode.

3. Active inode table:
   1. Entries hashed on i-number, dev-number.

   2. open() searches about 5 entries.

   3. Active references count.

To be cached and re-used:

1. In-memory inode entries. LRU replacement.

2. Disk blocks. LRU, FREE, EMPTY lists.

3. Name-to-i-number mappings. namei():

   for each path component
      find inode of directory
      start reading data blocks (directory entries)
      for each directory entry
         found desired component?
   

   Excessive time spent in namei()

File Structure, Access

Structures:

1. Unstructured: sequence of bytes.

2. Structured:
   1. Fixed-length records.

   2. Variable-length records.

Access:

1. Sequential. Easy in all cases.

2. Direct. I.e., seeks. Seeking to a particular variable-length record.

3. Indexed and friends. Size of index file.

Directory Structure

Imposing order on the morass.

File naming restrictions: structure of a directory file.

Unix directory entries:

1. Single-level directory. Ugh. Aliasing problems between users.

2. Two-level directory. Single directory per user. IBM minidisks. Still aliasing problems. Sharing?

3. Tree-structured directory. Sub-directory sharing.

4. Acyclic-graph-structured directory.

5. Why cycles are bad. Why hard-links don't point to directories and sym-links can.

1. Dearth of drive letters in DOS.

2. Search paths:

   /home1/kelliher/Util /home1/kelliher/Util/I386 /usr/local/bin /bin
   /usr/bin /usr/X11/bin /usr/contrib/bin /usr/contrib/texmf/bin /sbin
   /usr/sbin /keystone/bin /keystone/decstation-ultrix/bin
   

3. cdpath

Protection

Types:

1. File: read, write, execute. (Append, delete.)

2. Directory: read, write, search.

Implementation:

1. With each file: a ``who and how'' list.

2. With each user: a ``what and how'' list.

3. Stereotyping users: owner, group, world.