Week 11.b
CS 5600
11/19 2021

On the board
------------

1. Last time
2. Files, continued
3. Directories
4. fs5600 (Lab4)
   A. fs5600 disk
   B. data structures
   C. interfaces

-------------------------------------------

1. Last time

   --SSD

   --fs, three goals
     (i) persistance
     (ii) name data => file
     (iii) locate data => directory

   --file
     --ways to access file: sequential and random
     --three types of file organization
       --extent based
       --linked based
       --indexed file


2. Files, continued

    --Unix inode:

        [draw on board]

        permisssions
        times for file access, file modification, and inode-change
        link count (# directories containing file)
        ptr 1  --> data block
        ptr 2  --> data block
        ptr 3  --> data block
        .....
        ptr 11  --> indirect block 
                      ptr --> 
                      ptr --> 
                      ptr --> 
                      ptr -->
                      ptr -->
        ptr 12 --> indirect block
        ptr 13 --> double indirect block
        ptr 14 --> triple indirect block

    This is just a tree.

    Question: why is this tree intentionally imbalanced?

        (Answer: optimize for short files. each level of this tree
        requires a disk seek...)

    Pluses/minuses:

    +: Simple, easy to build, fast access to small files

    +: Maximum file length can be enormous, with
       multiple levels of indirection 

    -: worst case # of accesses pretty bad

    -: worst case overhead (such as 11 block file) pretty bad

    -: Because you allocate blocks by taking them off unordered
       freelist, metadata and data get strewn across disk


    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

    [skipped in class]
    --Question: how many files can the following fsXXX has?
        sizeof(inode) = 128B
        sizeof(block) = 512B
        fsXXX 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.

    --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


3. 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)

    --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
          ]


4. CS5600 File System (Lab4)

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

  - a simplified 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 week11.a, panel 1]

  B. important data structures

    ** superblock
      [see handout week11.a, panel 2]

    ** 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 week11.a, panel 2]

      -- 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
        [see handout]

        [draw on board as well]

      --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)

      |<-- 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?

     [answer:
      one fs_dirent is 32B (see handout week11.a)
      A file is maximum of 4076KB.
      So there can be 127 * 1024 files,
        or roughly 128K (~= 4MB/32B)
     ]

     -- fs5600 only supports using 1 data block,
        meaning 128 files at maximum.

  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
      ]

    ** fs_write - write to a file

      --how? for example, "write("/a/file", buf, len, offset)" (pseudocode)
        [answer:
          1. path walk to find the file's inode
          2. allocate blocks if needed (len+offset > size)
          3. find offset's block
          4. write len bytes to the file
        ]

        Question: can you think of any metadata to update?
        [answer:
          - mtime
          - size
        ]

    ** fs_create - create a new (empty) file

      --how? for example, "create("/a/file", mode)" (pseudocode)
       [answer:
            1. path walk to get the inode of the parent folder ("/a/")
            2. allocate a block as "file"'s inode
            3. add "file" to "/a/"
       ]

      --Question: how many "block_write()" do you think will happen in a "fs_create"?
      [answer: at least 4 times:
        - 1 to bitmap (for allocating new blocks)
        - 1 to parent dir inode (metadata update, mtime)
        - 1 to parent dir data block (adding "file")
        - 1 to the "file"'s inode

        - and likely 1 data block to file's inode
      ]