Week 2.a
CS7670
09/12 2022
https://naizhengtan.github.io/22fall/


0. Admin
1. UNIX fs
2. file and inode
3. directory
4. fs interface
5. NEU File System (Lab1)
6. challenge: learned fs5600

---

0. Admin

  -- Why roll back to sequential labs?

  -- Team up?
     --Group A: Daniel, Matthew
     --Group B: Brent, Will, Han

  -- Lab1 challenge
     (brainstorm in the end if time allows)
     --Group A: learned-fs5600 proposal on the Monday after next (09/26)

  -- mini-survey
     [ask if everyone is comfortable with C]
     [ask if everyone is familiar with virtual memory? ask %cr3]

1. UNIX fs

 -- What is a file system?
    What we talk about when we talk about fs?

    Q: think of how you're using file system everyday?
       give one functionality of fs.

    [for example, store data:
      download & store paper pdf; will be there after reboot.]

 -- what does a FS do?

    1. provide persistence (don't go away ... ever)

    2. give a way to "name" a set of bytes on the disk (files)

    3. give a way to map from human-friendly-names to "names" (directories)


-- in "UNIX Implementation" Sec4, first two paragraphs

   Q: What is a file?
      (1D array of bytes)

   Q: What are directories?
      (files that users cannot write)

   Q: What is a UNIX file system?
      (a disk data structure)

   Q: What is the canonical view of a disk?
      (an array of 512B blocks)

   [draw a graph of
       fs -+--> file -+--> disk
           +--> dir  -+        ]

-- "canonical disk"
  [draw the disk]

  the four regions of fs:
    first block: booting
    second block: super block
    some blocks: a list of inode (64B); i-number
    remaining: storage blocks


  Q: how does UNIX fs manages free blocks?
  free space maintained by a linked list:
     - block in this list points to the next block in the list
     - the remaining space of the block contains up to 50 addr of free disk blocks

  [Q: what is max size of a disk addr?
   A: a block is 512B; one block can have at most 51 addr;
      size(addr) <= 512B/51 ~= 10B = 80 bits
      (later we saw it is 4B.)
  ]

   Q: can you imagine how to run block allocation?
    [this is in fact not that easy]

2. file and inode

   [draw inode]

   i-node (a file) has 13 addresses
     - 10 for direct pointers
     - 1 for indirect pointer
       (contains 128 direct pointers)
           [now we see that addr = 512/128 = 4B = 32 bits]
     - 1 for double-indirect pointer
     - 1 for triple-indirect pointer

   What are "disk address"?
      disk address is 48-bit with the release of ATA-6 (2003).
      check also LBA (logical block addressing) for current disks:
        https://en.wikipedia.org/wiki/Logical_block_addressing

   [Q: what the max size of a file?
    A: (10 + 128 + 128^2 + 128^3) * 512B
       = 1082201088 B
       ~= 1GB
   ]

   [Q: 1082201088 vs. 1082201087 (in the paper); WHY?]

3. directory

  What is the purpose of dirs?
   human-friendly way to locate a file

  [draw /home/cheng/lab1/fs5600.h in a tree structure]

  How to know what files are contained in a dir "/home/"?

  ** entry is (name, i-number)
      entry (16B), name (14B), i-number(2B=16-bits)

    [Q: how many files can UNIX fs has?
     A: the number that can be represented by i-number: 2^(16)~=65.5k]

  dir root: i-number=2

  ** Unix fs allows an arbitrary, directed graph of directories with regular
  files linked in arbitrary places in this graph.

    [Q: why this is chaotic?
     draw a DAG (with diamonds) and a tree for dirs;
     draw files beneath.]

  "later systems were restricted to a directory tree"---how to understand this?
    -- no hard-link for dirs
    -- soft-link ("ln -s") can do this
       (soft-link is in fact a specialized file)

  [skipped]
  "it is also easy... and check the consistency of the file system."
    while...later, people found that crash consistency is pretty hard.

  a myth: buffer cache vs. page cache
  [checkout:
      Chuck Silvers. "UBC: An Efficient Unified I/O and Memory Caching
      Subsystem for NetBSD", ATC'00]

  path walking: converting a path name into an i-node table entry


4. fs interfaces

  Now, take a look at the POSIX fs APIs:
    fd = open(path, mode)
    stat = read(fd, &mem, size)
    stat = write(fd, mem, size)
    offset = lseek(fd, offset, whence)

  **DISCUSSION
    compared with key-value APIs:
     value = read(key)
     stat = write(key, value)

  [Q: can you see the difference?
      an implicit "I/O pointer", or "stateful vs. stateless"]

  Example: [an example of the "confusing I/O pointer"]
     fd = open(...)
     pid = fork()
     ... // what about this fd's I/O pointer for parent and child process?


  ** Mount file systems

  What is a fs, again?
   (a disk data structure:
      a tree where nodes are inodes;
      leaf nodes are files;
      intermediate nodes are dirs.)

    a root -> trace a bunch of blocks
      on some storage device

    buy a new disk, build a file system

    "mount" it to the existing dir hierarchy

    "mount table" try "df -h"


5. NEU File System (Lab1)

  [skipped; next time]

6. Challenge: learned fs5600

  -- what we have:
     The current fs5600 is access pattern agnostic—no matter what application
     uses fs5600, the fs operations work exactly the same.

  -- opportunities:
     (a) data layout
     (b) access pattern
      ** anything else?

  -- what can we do?
  -- how can we do it?