Storage & File systems

Question 1

What’s better to use FD or filename?

Answer 1

FD versions are more secure in some sense
• Because association of FD to underlying file is immutable
– Once an FD exists, it will always point to the same file

• Whereas association between file & its name is mutable

• Using names might lead to TOCTTOU (time of check to time of use)
races

Question 2

What are the 6 types of POSIX files?

Answer 2

– Regular file
– Directory
– Symbolic link (= shortcut), a.k.a. soft link
– FIFO (named pipe)
– Socket
– Device file

Question 3

What is Access control list (ACL)?

Answer 3

Most OSes/filesystems support some form of ACLs
– Many groups/users can be associated with a file
– Each group/user can be associated with the 3 attributes (r/w/x)
– Or more, finer attributes (“can delete”, “can rename”, etc.)

CON: not part of POSIX

Question 4

Is there a difference between a filename and filepath in UNIX?

Answer 4

No, filename = filepath = path

Question 5

Is the file and filename the same thing in UNIX?

Answer 5

No.
– In fact, the name is not even part of the file’s metadata
– A file can have many names, which appear in unrelated places in the
filesystem hierarchy
– Creating another name => creating another “hard link”

Question 6

Can we have hard links to directories?

Answer 6

– Hard links to directories are usually disallowed & unsupported by the
filesystem (though POSIX does allow directory hard links)
– => Acyclic graph (no circles)

Still, all filesystems that adhere to POSIX provide at least
some support to directory hard links
– Due to the special directory names “.” and “..”
– What’s the minimum number of hard links for directory?
• 2 (due to “.”)
– What’s the maximum?
• Depends on how many subdirectories nest in it (due to “..”)

Question 7

What’s the difference between a hardlink and a soft link?

Answer 7

Unlike hard links
– Which point to the actual underlying file object
• Symlinks (“shortcuts” in Windows terms)
– Point to a name of a “target” file (their content is typically this name)
– They’re not counted in the file’s ref count
– They can be “broken” / “dangling” (point to a nonexistent path)
– They can refer to a directory (unlike hard links in most cases)
– They can refer to files outside of the filesystem / mount point
(whereas hard links must point to files within the same filesystem)

Question 8

What does the unlink function removes?

Answer 8

Will remove the symlink, not the target file

Question 9

What’s the inode?

Answer 9

The OS data structure that represents the file
nternally, file names “point” to inodes
• This inode is determined via the path-resolution algorithm

The inode contains all the metadata of the file

Question 10

What’s a directory file?

Answer 10

A simple flat file comprised of directory entries (dirents).

Question 11

Where is the name of the file stored?

Answer 11

In the directory file, not the inode.

Question 12

Do symlinks have there own inode?

Answer 12

POSIX doesn’t specify whether a symlink should have an
inode.

But filesystems often define an inode per symlink, it then points to the files “real” inode, or if the name is to long then to a data block where a pointer to the “real” inode lays.

Question 13

What is the lower bound for the time complexity of Path resolution process?

Answer 13

n. Because finding each individual directory component

along the path may also be a linear process

Question 14

What’s the block/sector size in VSFS?

Answer 14

4kB.

Question 15

What is the layout of VSFS?

Answer 15

0 block = superblock
1 block = inode bitmap
2 block = data blocks bitmap
blocks 3 - 7 = Inode table
blocks 8 - 63 = Data blocks

Question 16

What is the superblock?

Answer 16

Contains information about the particular filesystem

Location of the superblock (of any FS) must be well-known

Question 17

What’s a disk partition?

Answer 17

Partition = contiguous disjoint part of the disk that can host a filesystem

Question 18

Given inumber (=index of inode in table), how can we find inode block?

Answer 18

sector = (inodeStartAddr + (inumber x sizeof(inode_t)) / blockSize

Question 19

How is Multi-level index (in the classic Unix FS) implemented?

Answer 19

• 12 pointers in inode point directly to data blocks
• Single-indirect pointer points to a block completely comprised of pointers to data blocks
• Double-indirect
• Triple-indirect

sum = 15 pointers, giving a total coverage of 4TB. (assuming each pointer is 4B).

Question 20

Do the indirect pointer blocks included in the file size?

Answer 20

No.

Question 21

What’s an extent?

Answer 21

• Extent = contiguous area comprised of
  variable number of blocks
  – inode saves a list of (pointer, size) pairs

Question 22

Describe FAT layout

Answer 22

– One table for all files
– One table entry for every disk block
– -1 (0xFFFF) marks “the end”
– Directory file: content of each entry points to start of file

Question 23

Is the FAT table copied to memory?

Answer 23

FAT (table) is copied to (cached in) memory
– But of course must also be saved on disk
– Solves random access problem of file pointers

Question 24

Describe the pros and cons of FAT.

Answer 24

Pros
– Simple to implement:
• File append, free block allocation management, easy allocation
– No external fragmentation
– Fast random access since table is in memory (for block pointers, not
necessarily for the blocks themselves)

Cons
– File contiguity can be lost (this is why extents were invented)
– Table can be huge
• 32 GB (disk) / 4KB (block) = 2^5 x 2^30 / 2^12 = 2^23 = 8 M
• Assuming 4B pointer, this means 32 MB table

Question 25

What’s RAID 0, pros and cons?

Answer 25

Non-redundant disk array
– Files striped evenly across N ≥ 2 disks

Pros
– High read/write throughput
- Faster aggregated seek time, that is
Cause we can do things concurrently.

Con
– Any disk failure results in data loss

Question 26

What’s RAID 1, pros and cons?

Answer 26

• Mirrored disks
– Files are striped across half the disks
– Data written to 2 places: data disk & mirror disk

Pros
– On failure, can immediately use surviving disk
– Read performance: similar to RAID 0 (can read concurrently as well) Write is twice slower.

Cons
– Wastes half the capacity

Question 27

What’s RAID 4, pros and cons?

Answer 27

• Use parity disks
– Each block (= multiple of sector) on the parity disk is a parity function
(=xor) of the corresponding blocks on all the N-1 other disks

• Failure => “degraded read”
– Read remaining disks plus parity
disk to compute missing data

• Pros
– In terms of capacity, less wasteful than RAID-1 (wastes only 1/N)
– Read performance similar to RAID-0, Write need to update parity block.
(although we don’t really need to read the old value first, just write).

Question 28

What’s RAID 5, pros and cons?

Answer 28

• Similar to RAID-4, but uses block interleaved distributed parity
– Distribute parity info across all disks

• Pros
– Like RAID-4, but better because
it eliminates the hot spot disk
– E.g., when performing two small
writes in RAID-4
• They must be serialized
– Not necessarily so in RAID-5
• => better performance

Question 29

What’s RAID 6, pros and cons?

Answer 29

• Extends RAID-5 by adding an additional “parity” block
– Ap and Aq must be independent of each other, algebraically speaking

• Pros & cons relative to RAID-5
– Can withstand 2 disk failures (2 equations, can find 2 variables)
– But wastes 2/N rather than 1/N of the capacity

Question 30

What’s RAID 2&3, pros and cons?

Answer 30

Like RAID-4

– But in bit and byte resolution, respectively

Question 31

What does the RAID n+k means?

Answer 31

• n blocks of regular data

* k blocks that provide redundancy

Question 32

מהם המטמונים שלינוקס שומרת בהקשר של מערכות קבצים?

Answer 32

1. מטמון הדפים (page cache) – עבור המידע של איזור הנתונים.
2. מטמון inodes – עבור המידע של טבלת ה-inodes.
3. מטמונים נוספים עבור ה-bitmaps או מבני נתונים אחרים של מערכת הקבצים.

Question 33

מה המבנה של תיקיות בFAT?

Answer 33

תיקיות הן קבצים רגילים המכילים רשימה של רשומות שבכל אחת יש את השדות:
filename, metadata, starting block
כל רשומה מכילה את המטאדאטה שלה לכן הinode כאילו מוטמה בתוך הרשומה.

Question 34

האם FAT תומכת בקישורים קשים?

Answer 34

לא. כי המטאדאטה של הקובץ שמור ברשומה של התיקיה.