Lecture 32: File system

implementation in xv6
Mythili Vutukuru
IIT Bombay
https://www.cse.iitb.ac.in/~mythili/os/
 Disk layout
• Disk in xv6 is formatted to contain superblock, log (for crash recovery),
inode blocks (multiple inodes packed per block), bitmap (indicating which
data blocks are free), actual data blocks
• Disk inode contains block numbers of direct blocks and one indirect block
• Directory is special file: data blocks contain directory entries, mapping file
names of files in the directory to corresponding inode numbers
• Link count of inode = number of directory entries pointing to a file inode

2
 In-memory data structures (1)
• Every open file has a struct file
associated with it
– Pointer to inode or pipe structure
• All struct files stored in fixed size array
called file table (ftable)
• File descriptor array of a process contains
pointers to struct files in the file table
• Two processes P and Q open same file,
will use two struct file entries in file table
– Points to same inode
– Read and write independently at
different offsets
• P forks child C, both file descriptors will
point to same struct file (ref is increased)
– Offsets are shared
• Reference count of struct file is number
of file descriptors that point to it
3
 In-memory data structures (2)
• Struct file points to in-memory inode
structure of an open file (pipe
structure for pipes)
• In-memory inode is almost copy of
disk inode, stored in memory for
open files
• All in-memory inodes stored in fixed
size array called inode cache (icache)
• Reference count of in-memory inode
is number of pointers from file table
entries, current working directory of
process etc.
– Different from link count
– A file is cleaned up on disk only when
both ref count and link count are
zero

4
 Inode functions (1)
• Function ialloc() allocates free inode from disk by
looking over disk inodes and finding a free one for a file
• Function iget() returns a reference counted pointer to
in-memory inode in icache, to use in struct file etc
– Non-exclusive pointer, information inside inode structure
may not be up to date
– Pointer released by iput()
• Function ilock() locks the inode for use by a process,
and updates its information from disk if needed
– Unlocked by iunlock()
• Function iupdate() propagates changes from in-
memory inode to on-disk inode

5
Inode functions (2)
• Inode has pointers to file
datablocks
• Function bmap returns the
address of n-th block of file
– If direct block, read from inode
– If indirect block, read indirect
block first and then return block
number from it
• Function can allocate data blocks
too: if n-th data block of file not
present, allocates new block on
disk, writes it to inode, and
returns address
• Functions readi/writei are used
to read/write file data at given
offset, call bmap to find
corresponding data block

6
 Directory functions
• Directory lookup: read directory entries from the data blocks of directory.
If file name matches, return pointer to inode from icache
• Linking a file to a directory: check file with the same name does not exist,
and add the mapping from file name to inode number to directory

7
 Creating a file (if it doesn’t exist)
• Locate the inode of parent
directory by walking the
filepath from root (lookup
root inode, find inode
number of next element of
pathname in inode data
blocks, and repeat)
• Lookup filename in parent
directory. If file already
exists, return its inode
• If file doesn’t exist, allocate
a new inode for it, lock it,
initialize it
• If new file is a directory, add
entries for “.” and “..”
• If new file is a regular file,
link it to its parent directory

8
System call: open
• Get arguments: filename,
mode
• Create file (if specified) and
get a pointer to its inode
• Allocate new struct file in
ftable, and new file
descriptor entry in struct
proc of process pointing to
the struct file in ftable
• Return index of new entry
in file descriptor array of
process
• Note the begin_op and
end_op for transactions
9
 System call: link
• Link an existing file from
another directory with a
new name (hard linking)
• Get pointer to file inode by
walking the old filename
• Update link count in inode
• Get pointer to inode of
new directory, and link old
inode from parent
directory in new name

10
 System call: file read
• Other system calls follow same
pattern
• For example, file read:
– Get arguments (file descriptor
number, buffer to read into,
number of bytes to read)
– Fetch inode pointer from struct file
and perform read on inode (or pipe
if file descriptor pointed to pipe)
– Function readi uses the function
“bmap” to get the block
corresponding to n-th byte and
reads from it
– Offset in struct file updated

11
 Summary
• On disk: inodes, data blocks, free bitmap (and log)
• In-memory: file descriptor array (points to) struct file in file
table array (points to) in-memory inode in inode cache
• Directory is a special file, where data blocks contain
directory entries (filenames and corresponding inode
numbers)
• System calls related to files extract arguments, perform
various operations on in-memory and on-disk data
structures
• Updates to disk happen via the buffer cache
– Changes to all blocks in a system call are wrapped in a
transaction and logged for atomicity

12