File System Implementation

1 40 File System ImplementationIn this chapter, we introduce a simple file System Implementation , knownasvsfs(theVery Simple File System ). This file System is a simplifiedversion of a typical UNIX file System and thus serves to introduce someof the basic on-disk structures, access methods, and various policies thatyou will find in many file systems file System is pure software; unlike our development of CPU andmemory virtualization, we will not be adding hardware featuresto makesome aspect of the file System work better (though we will want to pay at-tention to device characteristics to make sure the file systemworks well).

2 Because of the great flexibility we have in building a file System , manydifferent ones have been built, literally from AFS (the AndrewFile Sys-tem) [H+88] to ZFS (Sun s Zettabyte File System ) [B07]. All of these filesystems have different data structures and do some things better or worsethan their peers. Thus, the way we will be learning about file systems isthrough case studies: first, a simple file System (vsfs) in thischapter tointroduce most concepts, and then a series of studies of real file systemsto understand how they can differ in : HOWTOIMPLEMENTA SIMPLEFILESYSTEMHow can we build a simple file System ? What structures are neededon the disk?

3 What do they need to track? How are they accessed? The Way To ThinkTo think about file systems, we usually suggest thinking about twodifferent aspects of them; if you understand both of these aspects, youprobably understand how the file System basically first is thedata structuresof the file System . In other words, whattypes of on-disk structures are utilized by the file System to organize itsdata and metadata? The first file systems we ll see (including vsfs below)employ simple structures, like arrays of blocks or other objects, whereas12 FILESYSTEMIMPLEMENTATIONASIDE: MENTALMODELSOFFILESYSTEMSAs we ve discussed before, mental models are what you are really tryingto develop when learning about systems.

4 For file systems, your mentalmodel should eventually include answers to questions like: what on-diskstructures store the file System s data and metadata? What happens whena process opens a file? Which on-disk structures are accessed during aread or write? By working on and improving your mental model, youdevelop an abstract understanding of what is going on, instead of justtrying to understand the specifics of some file- System code (though thatis also useful, of course!).more sophisticated file systems, like SGI s XFS, use more complicatedtree-based structures [S+96].The second aspect of a file System is itsaccess methods.

5 How doesit map the calls made by a process, such asopen(),read(),write(),etc., onto its structures? Which structures are read during the executionof a particular System call? Which are written? How efficientlyare all ofthese steps performed?If you understand the data structures and access methods of a filesys-tem, you have developed a good mental model of how it truly works, akey part of the systems mindset. Try to work on developing your mentalmodel as we delve into our first Overall OrganizationWe now develop the overall on-disk organization of the data struc-tures of the vsfs file System . The first thing we ll need to do is divide thedisk intoblocks; simple file systems use just one block size, and that sexactly what we ll do here.

6 Let s choose a commonly-used size of 4 , our view of the disk partition where we re building our file sys-tem is simple: a series of blocks, each of size 4 KB. The blocks are ad-dressed from 0 toN 1, in a partition of sizeN4-KB blocks. Assume wehave a really small disk, with just 64 blocks:07815162324313239404748555663 Let s now think about what we need to store in these blocks to builda file System . Of course, the first thing that comes to mind is fact, most of the space in any file System is (and should be) s call the region of the disk we use for user data thedata region, and,OPERATINGSYSTEMS[ ] for simplicity, reserve a fixed portion of the disk for these blocks,say the last 56 of 64 blocks on the disk:07D8 DDDDDDD15D16 DDDDDDD23D24 DDDDDDD31D32 DDDDDDD39D40 DDDDDDD47D48 DDDDDDD55D56 DDDDDDD63 Data RegionData RegionAs we learned about (a little) last chapter, the file System hasto trackinformation about each file.

7 This information is a key piece ofmetadata,and tracks things like which data blocks (in the data region) comprise afile, the size of the file, its owner and access rights, access andmodifytimes, and other similar kinds of information. To store this information,file systems usually have a structure called aninode(we ll read moreabout inodes below).To accommodate inodes, we ll need to reserve some space on the diskfor them as well. Let s call this portion of the disk theinode table, whichsimply holds an array of on-disk inodes. Thus, our on-disk image nowlooks like this picture, assuming that we use 5 of our 64 blocks for inodes(denoted by I s in the diagram):0 IIIII7D8 DDDDDDD15D16 DDDDDDD23D24 DDDDDDD31D32 DDDDDDD39D40 DDDDDDD47D48 DDDDDDD55D56 DDDDDDD63 Data RegionData RegionInodesWe should note here that inodes are typically not that big, for example128 or 256 bytes.

8 Assuming 256 bytes per inode, a 4-KB block can hold 16inodes, and our file System above contains 80 total inodes. In our simplefile System , built on a tiny 64-block partition, this number represents themaximum number of files we can have in our file System ; however, donote that the same file System , built on a larger disk, could simply allocatea larger inode table and thus accommodate more file System thus far has data blocks (D), and inodes (I), but afewthings are still missing. One primary component that is still needed, asyou might have guessed, is some way to track whether inodes or datablocks are free or allocated.

9 Suchallocation structuresare thus a requisiteelement in any file allocation-tracking methods are possible, of course. For exam-ple, we could use afree listthat points to the first free block, which thenpoints to the next free block, and so forth. We instead choose a simple andpopular structure known as abitmap, one for the data region (thedatabitmap), and one for the inode table (theinode bitmap). A bitmap is ac 2008 20, ARPACI-DUSSEAUTHREEEASYPIECES4 FILESYSTEMIMPLEMENTATION simple structure: each bit is used to indicate whether the correspondingobject/block is free (0) or in-use (1). And thus our new on-disk layout,with an inode bitmap (i) and a data bitmap (d):0idIIIII7D8 DDDDDDD15D16 DDDDDDD23D24 DDDDDDD31D32 DDDDDDD39D40 DDDDDDD47D48 DDDDDDD55D56 DDDDDDD63 Data RegionData RegionInodesYou may notice that it is a bit of overkill to use an entire 4-KB blockforthese bitmaps; such a bitmap can track whether 32K objects areallocated,and yet we only have 80 inodes and 56 data blocks.

10 However, we just usean entire 4-KB block for each of these bitmaps for careful reader ( , the reader who is still awake) may have no-ticed there is one block left in the design of the on-disk structure of ourvery simple file System . We reserve this for thesuperblock, denoted byan S in the diagram below. The superblock contains information aboutthis particular file System , including, for example, how many inodes anddata blocks are in the file System (80 and 56, respectively in this instance),where the inode table begins (block 3), and so forth. It will likely alsoinclude a magic number of some kind to identify the file System type (inthis case, vsfs).