Week 13.b
CS 5600
04/05 2023

1. last time
2. Directories
3. fs5600 (Lab5)
   A. fs5600 disk
   B. data structures
   C. interfaces
--------------------------------------

1. last time

  - fs, three main functionalities

  - file mapping
                     inode
     <file, offset> -------> disk block addr

  - Unix inode: 
    -- a disk data structure
    -- metadata + an imbalanced tree (nodes are disk blocks)

  * Notes about inodes:

    --stored in a fixed-size array

    --Size of array fixed when disk is initialized; can't be changed
      [why? easier for fs to find inodes,
            and fewer disk accesses (better performance!)]

    --Multiple inodes in a disk block
      (which is not the case for your Lab5)

    --Question: how many files can the following toy-fs has?
        sizeof(inode) = 128B
        sizeof(block) = 512B
        toy-fs uses 1000 blocks to store inodes

       [answer:
         the number of inodes (hence files) is
           (521B / 128B) * 1000 = 4000
       ]

       -- use "$ df -i ~" to see how many inodes you can use.

    --inode lives in known location, originally at one side of disk,
    now lives in pieces across disk (helps keep metadata close
    to data)

    --The index of an inode in the inode array is called an
    ***i-number***

    --Internally, the OS refers to files by i-number

    --When a file is opened, the inode brought in memory

    --Written back when modified and file closed or time elapses


2. Directories

    --Problem: "Spend all day generating data, come back the next
    morning, want to use it."  F. Corbato, on why files/dirs
    invented.

    [skip history if no time:

      --Approach 0: Have users remember where on disk their files are

      --like remembering your social security or bank account #

      --yuck. (people want human-friendly names.)

      --So use directories to map names to file blocks, somehow

      --But what is in directory?

      --A short history of directories

      --Approach 1: Single directory for entire system

          --Put directory at known location on disk

          --Directory contains <name,inumber> pairs

          --If one user uses a name, no one else can

          --"Many ancient personal computers work this way"
          [I heard this as an anecdote; never saw one myself...]

      --Approach 2: Single directory for each user

          --Still clumsy, and "ls" on 10,000 files is a real pain
          --(But some oldtimers still work this way)

      --Approach 3: Hierarchical name spaces. 

          --Allow directory to map names to files ***or other dirs***

          --File system forms a tree (or graph, if links allowed)

          --Large name spaces tend to be hierarchical

          --examples: IP addresses, domain names, scoping in
          programming languages, etc.

          --more generally, the concept of hierarchy is everywhere
          in computer systems
    ]

    --Hierarchial Unix

      --used since CTSS (1960s), and Unix picked it up and used it
      nicely

      --structure like:
        [draw: 
                      "/"
           bin/     dev/     tmp/    usr/
         ls, grep    ...
        ]

    --directories stored on disk just like regular files

        --here's the data in a directory file; this data can be in the
        *data blocks* of the directory or else in the inode of the
        directory.

          [<name, inode#>]
           <bin, 1021>
           <dev, 1001>
           <sbin, 2011>
           ....

        --i-node for directory contains a special flag bit

        --only special users can write directory files

    --key point: i-number might reference another directory

        --this neatly turns the FS into a hierarchical tree, with
        almost no work

    --bootstrapping: where do you start looking?

        --root dir always inode #2 (0 and 1 reserved)

        --and, voila, we have a namespace!

    --special names: "/", ".", ".."

    --given those names, we need only two operations to navigate the
    entire name space:

        --"cd name": (change context to directory "name")
        --"ls": (list all names in current directory)

    --example:

                /a/foo.c
                /b/c/essay.txt

            what does the file system look like?

            [ i0 ... i7 || [block ] [ block ] [block ] .....]

        [Draw picture]

      [an argument that hierarchical fs is no longer relevant:
        Margo Seltzer, Nicholas Murphy. Hierarchical File Systems are Dead. HotOS'09

       but...we're still using them in 2023...
      ]

    * links:

        --hard link: multiple dir entries point to same inode; inode
        contains refcount

        "$ ln /tmp/a /tmp/b": creates a synonym ("b") for file ("a")

          --how do we avoid cycles in the graph? (answer: can't
          hard link to directories).

        --soft link: synonym for a *name*

        "$ln -s /tmp/a /tmp/sb":

          --creates a new inode (sb), not just a new directory entry

          --new inode has "sym link" bit set

          --contents of that new file:

              "/tmp/a"

        --Question: what will happen:
          "$ rm /tmp/a; cat /tmp/b; cat /tmp/sb"?

          [answer: try it yourself]

        --Question: can I create soft-link cycles?
          [answer: yes you can. Try:
             $ mkdir /tmp/a; mkdir /tmp/b
             $ ln -s /tmp/a /tmp/b/a
             $ ln -s /tmp/b /tmp/a/b
          ]


3. CS5600 File System (Lab5)

  [this is an (almost) duplication of the Lab5 instructions.]

  - a Unix-like fs
    -- with many simplifications
    -- for example, dirs are no deeper than 10

  A. fs5600 disk 

    - an abstract disk
      (the overall system format)

      -- a block is 4KB

     +-------+--------+----------+------------------------+
     | super | block  | root dir |     data blocks ...    |
     | block | bitmap |   inode  |                        |
     +-------+--------+----------+------------------------+
    block     0        1         2          3 ...

    - talk to the disk?
      -- read or write one or multiple blocks

      [see handout]

  B. important data structures

    ** superblock
      [see handout]

    ** block bitmap
      -- tells fs5600 which blocks are free
      -- one bit represents one block

      --QUESTION: what's the maximum size of a fs5600?
      [answer: 128MB = 4096 * 8 * 4KB]

    ** file and inode

      [see handout]

      -- metadata
        [or stat, see full file metadata: https://pubs.opengroup.org/onlinepubs/7908799/xsh/sysstat.h.html]

        -- uid, gid: user and group of this file
        -- mode (see below)
        -- ctime: changed time, time of last status (metadata) change
        -- mtime: modified time, time of last data modification
        (fs5600 skips the access time in Unix)
        -- size: file size in bytes

      -- ptrs

        [draw on board]

      --Question: what's the maximum size of a file?
      [answer:
        number of ptrs = (4KB - 20B) / 4B = 1019
        file size = 1019 * 4KB = 4076KB ~= 4MB
      ]

    ** mode (uint32_t)
     [see handout]

      |<-- S_IFMT --->|           |<-- user ->|<- group ->|<- world ->|
      +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
      | F | D |   |   |   |   |   | R | W | X | R | W | X | R | W | X |
      +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

      -- R: read
      -- W: write
      -- X: execute

      -- F bit: 0100000 (the 16th bit from right)
      -- D bit: 0040000 (the 15th bit from right)

   ** directory

     -- recall that directory is used to map name to #inode

     [see handout]
     [draw on board as well]

     --Question: how many files can appear in one directory?
       fs5600 only supports using 1 data block (our choice).

     [answer:
      one fs_dirent is 32B (see handout)
      one data block is 4KB.
      fs5600 chooses to use only 1 data block for dir,
      so the max files in one dir is 4KB/32B=128.
     ]

  C. interface


    ** path walk

       int inum = path2inum(char *pat);

       --how? for example, "/a/b/c/file"
       [answer:
         1. split path to tokens: ["a", "b", "c", "file"]
         2. starting from root dir (block 2)
         3. find "a" in "/" (block 2)
         4. get "a"'s inode
         5. get "b" in "/a/"
         6. ...
       ]

    ** fs_read - read data from a file

      --how? for example, "read("/a/file", buf, len, offset)" (pseudocode)
      [answer:
        1. path walk to find the file's inode
        2. find offset's block
           (all data blocks compose a linear space)
        3. read len bytes
      ]

      [start from here next time]