22. File System Data Structures Flashcards
What is an inode?
The inode is a data structure in a Unix-style file system that describes a filesystem object such as a file or a directory.
Each inode stores the attributes and disk block location(s) of the object’s data.
Filesystem object attributes may include metadata (times of last change, access, modification), as well as owner and permission data.
What information is contained in an ext4 inode?
Location of the file data blocks (contents)
Permissions, including user, read/write/exec bits, etc
Timestamps including creation, access, content modification, attribute modification, and delete times
These inodes are named and located by number
How does the system translate an inode number into an inode structure?
All inodes are created at format time at well-known locations
What are the consequences of placing inode structures at well-known locations?
inodes may not be located near file contents. ext4 creates multiple blocks of inodes within the drive to reduce seek times between inodes and data.
Fixed number of inodes for the file system. Can run otu of inodes before we run out of data blocks! ext4 creates approximately one inode per 16 KB of data blocks, but this can be configured at format time
What is a directory in ext4?
Simply a special file the contents of which map inode numbers to relative names.
Aside: You can’t modify these in the typical way, using say vim.
What must open(“/etc/default/keyboard”) translate “/etc/default/keyboard” to?
An inode number
How does open(“/etc/default/keyboard”) translate “/etc/default/keyboard”?
- Get inode number for root directory (this is usually a fixed agreed-on inode number, like 2)
- Open the directory with inode number 2. Look for “etc”. Find “etc” with inode number 393218
- Open the directory with inode number 393247
- Open the directory with inode number 393247. Look for “keyboard”. Find keyboard with inode number 394692
- Open the file with inode number 394692
How do we retrieve and modify data blocks using read/write(filehandle, 345)?
read/write(filehandle, 345) must translate 345 to a data block within the open file to determine what data block to modify
There are multiple ways of doing this. Linked list, flat array, and multilevel indexing are three ways.
Describe the linked list solution to translating an offset to a data block within the open file to determine what data block to modify (read/write).
Organize data blocks into a linked list.
The inode contains a pointer to the first data block.
Each data block contains a pointer to the previous and next data block
Pros: Simple and only a small amount of information needed in inode
Cons. Offset lookups are slow (O(n)) in the size of the file. Also, we have to store the “link” within each data block, which slightly reduces the number of available bytes in each block.
Describe the flat array solution to translating an offset to a data block within the open file to determine what data block to modify (read/write).
Store all data blocks in the inode in a single array allocate at file creation time
Pros: Simple and offset look ups are fast (O(1))
Cons: Small file size fixed at startup. Also, large portion of array may be unused
Describe the multilevel index solution to translating an offset to a data block within the open file to determine what data block to modify (read/write).
Observation: most files are small, but some can get very large.
Have the inode store:
-some pointers to blocks, which we refer to as direct blocks
- some pointers to blocks containing pointers to blocks, which we refer to as indirect blocks
- some pointeres to blocks containing pointers to blocks containing pointers to blocks, which we refer to as doubly indirect blocks
- etc…
Pros: Index scales with the size of the file. Offset look ups are still fairly fast.
Cons: Small files stay small, but big files can get extremely large.
See visualization at bottom of File System Data Structures notes
