ECS 150: Operating systems
Directories
© Sam King, 2024
Based on material from Joël Porquet-Lupine
Roadmap
Today: Directory implementation
Monday: Bringing it all together: Case study with FFS
Next week we’ll talk about APIs
Following week:
Reads that cross disk boundaries. Copy data from two disk blocks into one buffer
buffer
pos = 5000, copy size = 4096, block size = 4096
Calculate which inode.direct entry to use
buffer
19
6
8
Inode.direct array
idx=1
pos = 5000, copy size = 4096, block size = 4096
idx = floor(pos / block size)
Read the disk block for idx=1
buffer
19
6
8
Inode.direct array
idx=1
block
disk
readDiskBlock blockNum=6
pos = 5000, copy size = 4096, block size = 4096
Copy the data from the disk block to the beginning of the buffer
buffer
19
6
8
Inode.direct array
idx=1
block
disk
readDiskBlock blockNum=6
4096-offset
offset
offset = pos % block size
pos = 5000, copy size = 4096, block size = 4096
Find the next disk block we need to read to fill in the rest of the buffer
buffer
19
6
8
Inode.direct array
idx=2
pos = 5000, copy size = 4096, block size = 4096
Reads the next block from disk
buffer
19
6
8
Inode.direct array
idx=2
block
disk
readDiskBlock blockNum=19
pos = 5000, copy size = 4096, block size = 4096
Copy the data from the beginning of the block to the end of the buffer
buffer
19
6
8
Inode.direct array
idx=2
block
disk
readDiskBlock blockNum=19
pos = 5000, copy size = 4096, block size = 4096
Assume a.txt fileSize == 3*4096, implement write
inodeNum = lookup(0, “a.txt”)
write(inodeNum, buffer, 1, 5000)
Assume you have an inodeTable that is an array with all of your inodes and ignore error checking
Break into groups and sketch a solution
typedef struct {
int type;
int size; // in bytes
int direct[DIRECT_PTRS];
} inode_t;
Sketch of the solution
// ignore error checking
int write(int inodeNum, void *buffer, int sizeInBytes=1,
int posInBytes=5000) {
// Figure out which entry in our inode.direct to lookup the disk block.
// Convert bytes to blocks and get the disk block number.
// Read the block of data from the disk
// Copy from buffer to the block
// Write the block back to disk
}
Writing beyond the end of the file might require allocating new disk blocks
When can you write data without allocating a new block?
Design considerations: Workload
File size and storage space
Design considerations: Workload
File size and storage space
Most files are small
Large files account for most of the storage
Design considerations: Workload
How many files does “Chrome” open if you click on it and close it right away?
Design considerations: Workload
Design considerations: Workload
File access pattern and usage
File systems are all about data structures and algorithms
Data structures
Directories
File metadata (i.e., inode)
Index structure
Free space map
Directories
A directory is simply a file
Only directly accessible by OS
to use LocalFileSystem::read
a.img from Project 4
xxd output, showing the directory entries for /a/b
a.img from Project 4
c.txt name and file (inode) number
a.img from Project 4
You can also see “.” and “..” preceding c.txt
Directory implementation: Linear layout
.
830
..
158
music
320
work
219
foo.txt
871
free
-
free
-
free
-
Pro: Simple
Con: Linear scan to find an entry
Con: Deleting an entry will cause you to rewrite all data
Directory implementation: Linear layout
.
830
..
158
music
320
work
219
foo.txt
871
free
-1
free
-1
free
-1
Pro: Simple
Con: Linear scan to find an entry
Con: Managing data when deleting can be some work
Directory implementation: Trees
Tree of entries
E.g., XFS and NTFS
Pro: Fast file lookup O(log n)
Con: Complex implementation