FS

Question 1

what’s read-modify-write?

Answer 1

read in a sector, modify the byte, write it back

Question 2

tradeoff of a sector?

Answer 2

+ sector writes are always completed
- larger atomic units have to be created by the OS

Question 3

what’s location transparency?

Answer 3

the ability to access data w/o knowing its location

Question 4

FS working intuitions

Answer 4

FS performance dominated by # of FS accesses
transfer time is negligible compared to seek time + rotational delay

Question 5

tradeoffs of contiguous allocation

Answer 5

+ simple, fast access, sequential and random
- external fragmentation

Question 6

tradeoffs of linked files

Answer 6

+ easy dynamic growth, sequential access, no fragmentation
- non-contiguous blocks = bad access times
- bad random access
- pointers take up space

Question 7

FAT benefits

Answer 7

cache entire FAT, cheap compared to disk access when pointer chasing
space overhead trivial
must duplicate to protect against errors

Question 8

indexed files tradeoffs

Answer 8

+ sequential, random easy
- mapping table requires large chunk of contiguous space

Question 9

multilevel indexed files

Answer 9

+ solves space issues of indexed files
+ small files are fast, large max file size
- worst case 3 FS accesses (di -> i -> b)
- 13 block file = big space overhead
- metadata and data are strewn across disk

Question 10

what are hard links?

Answer 10

a refcount of pointers to an inode

Question 11

what are soft links?

Answer 11

like a directory: inode has special symlink bit set, file contents are name of target

Question 12

what does the superblock store?

Answer 12

block size, # of blocks, max # of files, pointer to head of free list/bitmap, information necessary to locate an inode given its inumber

Question 13

issues with old file system?

Answer 13

• 512B block size too small
• poor clustering of related objects

Question 14

how FFS fixes block size?

Answer 14

4KiB min, increases bandwidth
eliminate internal fragmentation with fragments

Question 15

how FFS fixes clustering?

Answer 15

cylinder groups
- data blocks of a file in same CG
- inode and data in same CG
- inodes of a directory in same CG

Question 16

how FFS bitmap improves free list?

Answer 16

easier to find contiguous blocks
smaller, keep entire bitmap in RAM

Question 17

tradeoff of the FFS bitmap?

Answer 17

time to find a free block increases with fewer free blocks

Question 18

how FFS deals with bitmap tradeoff?

Answer 18

trade space, always keep about 10% of disk free, scattered across disk
only root can allocate blocks once 100% full

Question 19

how can FS summary info be wrong?

Answer 19

corrupt inodes
fields in inodes are wrong
directories are bad

Question 20

corrupt inodes

Answer 20

not a simple crash
- bad block numbers, block used in more than one place

Question 21

fields in inodes wrong

Answer 21

count # of directory entries to verify link count, if no entries but count /= 0, move to lost and found
make sure size and used data counts match blocks

Question 22

directories may be bad

Answer 22

. and .. must be valid, file names must be unique
all directories must be reachable

Question 23

ordered updates

Answer 23

don’t point to garbage
- never write ptr before initializing struct it points to
- never reuse resource before nullifying all ptrs to it
- never clear last ptr to live resource before setting new one

Question 24

block aging

Answer 24

block that always has dependency will never get written back

Question 25

soft updates

Answer 25

track dependencies, temporarily roll back changes that can't yet be committed to disk

Question 26

soft update struct for each update field/pointer

Answer 26

- old - new - list of updates this update depends on

Question 27

dependencies better handled by postponing

Answer 27

freeing a block, mark block free in bitmap after the block ptr is cleared on disk

Question 28

operations requiring soft updates

Answer 28

1. block allocation 2. block deallocation 3. link addition 4. link removal

Question 29

block allocation

Answer 29

block ptr -> bitmap, data block

Question 30

block deallocation

Answer 30

bitmap -> block ptr

Question 31

link addition

Answer 31

directory entry -> bitmap, inode

Question 32

link removal

Answer 32

bitmap, inode -> directory entry

Question 33

limitations of soft updates

Answer 33

very specific to FFS (could not easily apply to XFS) metadata updates may proceed out of order (e.g. make A, B only B exists after crash) need slow background fsck to reclaim space

Question 34

limitations of journaling

Answer 34

disk write for every metadata operation (soft update create-delete might have no IO) contention for end of log on multi-processor fsync must sync other operations' metadata to log

Question 35

what's journaling?

Answer 35

use write-ahead log reserve portion of disk for log write any metadata operation first after crash, replay log

Question 36

finding oldest relevant log entry?

Answer 36

checkpoints - once all records up to N have been processed and blocks stably committed to disk - record N to disk in reserved checkpoint location/checkpoint log - never need to go back before most recent checkpoint

Question 37

allocation group sizes

Answer 37

0.5 - 4 GB

Question 38

AGs unlike CGs

Answer 38

too large to minimize seek times no fixed # of inodes per AG

Question 39

advantages of AGs

Answer 39

parallelize alloc of blocks/inodes on multiprocessor (have independent locking of different free space structs) can use 32bit block ptrs within AGs, making data structures smaller

Question 40

B+ trees

Answer 40

all kv pairs are in leaves leaves connected in doubly linked list all operations logn

Question 41

delayed allocation

Answer 41

write syscall only affects buffer cache assign disk space only when buffers flushed

Question 42

advantages of delayed allocation

Answer 42

short-lived files never need disk space allocation mmapped files often written to RAM in random order, but will be written to disk mostly contiguously write clustering: find other stuff nearby to write to disk

Question 43

fsync

Answer 43

syscall to flush file changes to disk must also flush dir/parent entries

Question 44

unmount

Answer 44

flush all changes to disk on shutdown some buffers must be flushed multiple times to be clean due to deps

Question 45

unlink

Answer 45

syscall returns even if inode/indirect block not cached deps created faster than blocks written cap # deps to avoid exhausting memory

Question 46

soft updates fsck

Answer 46

split fsck into foreground and background parts

Question 47

foreground fsck

Answer 47

must be done before remounting FS need each CG summary info to make sense recompute free block/inode counts from bitmaps leaves FS consistent, might leak space

Question 48

background fsck

Answer 48

does traditional fsck operations after mounting, to recuperate free space can be using FS while doing this must be done in foreground after media failure

Question 49

fsck vs soft updates fsck

Answer 49

may have many inodes w/ non-zero link counts

Question 50

how are free blocks tracked in XFS?

Answer 50

two B+ trees 1. start # -> # free blocks 2. # free blocks -> start #