generic_file_write() and file holes
[akaros.git] / Documentation / vfs.txt
1 Unorganized Notes on the Virtual File System
2 -------------------------------------
3 Our VFS is built similarly to Linux's, mostly because I'd like to have somewhat
4 easy integration with ext2 (or at the very least have our own FS that can
5 integrate into Linux easily).
6
7 There are four main objects in a filesystem: superblock, inode, dentry, and a
8 file.  
9         - Superblock: Specific instance of a mounted filesystem.  All
10           synchronization is done with the one spinlock.
11         - Inode: represents a specific file
12         - Dentry: in memory object, corresponding to an element of a path.  E.g. /,
13           usr, bin, and vim are all dentries.  All have inodes.  Vim happens to be a
14           file instead of a directory.
15         - File: represents a file opened by a process.
16
17 So far, dentries are the most complicated, so here are some notes about them.
18 These are probably self-consistent, but may be a bit old (or just wrong) because
19 I wrote them as I put the VFS together:
20
21 A dentry is just a connection between a part of a path and an inode.  We just
22 want to walk from dentry to dentry, asking each to find the next part in the
23 path.  When you hit a dentry that's not the end of the desired path, you ask its
24 inode for the next dentry by using it's operation (lookup).
25
26 lookup() takes the inode of the directory (or 0 for the root) and a dentry
27 (already allocated, with the d_name and i_name filled in), and it will find the
28 correct inode for the given dentry, as well as filling out any specific FS
29 things in the dentry (like d_ops).  It will return 0 on failure, or the dentry
30 pointer passed in on success.  Somehow the nameidata bit will be used too.  This
31 will probably change a bit...  Note that lookup() needs to read the actual
32 directory file and also lookup the inode off the disc, which means it will
33 block.
34
35 When the next dentry is a mountpoint, (e.g. /mnt/cdrom), when you ask mnt for
36 cdrom, lookup() will parse it's file (a directory) and see 'cdrom' there as a child
37 entry.  Then it will return cdrom's dentry, like always.
38
39 But since cdrom was a mountpoint, (which you can see from the d_mount_point),
40 you need to walk through the structures a bit to get the dentry of the FS rooted
41 at that mountpoint to keep walking.  The VFS can handle that, so lookup()
42 doesn't need to worry about it.
43
44 Why are there two dentries associated with a vfsmount?  Normally, a dentry for a
45 directory points to an inode that contains its members.  When a FS is mounted
46 over it, we don't want to destroy that.  Instead, we mark it as a mountpoint,
47 and when following, we walk into the next FS.  The mountpoint is the dentry in
48 the parent mount (using the parent mount's FS superblock), and the root is the
49 dentry of the mounted FS, using the FS superblock of the mounted FS.
50
51 Sometimes lookup() will not be called at all.  We want to look for present
52 dentries first (ones that exist in memory already, including all of those with a
53 refcnt).  So we can look in the cache (currently just an SLIST, but will
54 eventually be a hash table).  When hitting in the cache (hashed by dentry name,
55 and probably the parent dir), we need to verify that the dentry's parent is our
56 own (handled by the VFS code).  All vfsmount dentries will be in the cache,
57 since they all have a refcnt (the vfsmount struct points to them).
58
59 Dentries for / and pwd and whatnot have a refcnt (pointed to by fs_struct,
60 vfsmounts, etc).  Anything with a pointer to it has a refcnt, so it never goes
61 away.  So if we have an inode in memory, it's entire dentry path is cached,
62 (just follow the parent pointers back).  Note that when a dentry's refcnt hits
63 0, we do *not* deallocate (like we do with many other structures).  It will just
64 be on the LRU list in the dcache system.  Likewise, every dentry points to its
65 inode, which pins that inode in memory.
66
67 Other refcnts: just about everything has a refcnt, and we need to be careful
68 about when we want to use them and dealloc.  Some things would be a pain in the
69 ass, like with the super_block refcnt.  Every dentry has a ref to the SB, but
70 changing that ref every time we add or remove a dentry will probably be an
71 unnecessary penalty if we can ensure all dentries of that FS are gone before
72 removing the superblock through another mechanism.  We'll see.  Mostly, this
73 just means we need to think about what we really want from a refcnt, and whether
74 or not we want the kref / process style refcnting.
75
76 Mounting:
77 -------------------------------------------
78 When you mount, you need to read in the super block and connect the relevant
79 data structures together.  The SB is connected to the vfsmount, which is
80 connected to the dentry of the mount point and the dentry of the root of the FS.
81 This means when mounting the FS, we need to create the dentry for "/", which
82 means we also need the inode, which needs to be read_inode()'d in.  Actually, we
83 might not need to read the inode in right away - we might be able to get away
84 with reading them in on-demand.
85
86 All of this means that for every mount point, the SB, vfsmount, dentry, and
87 inode are in memory.  Due to the way dentries link, every dentry and inode back
88 up to the real root are all in memory too.  Having a mount point is like having
89 a process working in that directory - the chain back up is pinned.
90
91 d_subdirs:
92 -------------------------------------------
93 Tracking the links between objects can be tricky.  One pain is d_subdirs. Linux
94 only tracks subdirectories.  We also do this.  I think the reason they do it is
95 since you should be using the dcache to cache lookups, and not scan the linked
96 list of children of a dentry for a specific file.  Though it is handy to know
97 all of your *directory* children.  In KFS, we also track all children in a list.
98 This is to make our lookups work - instead of having an actual directory file
99 with name->ino mappings.
100
101 KFS and metadata pinning:
102 -------------------------------------------
103 KFS pins all metadata ("all paths pinned").  This means that from the root mnt
104 down to the lowest inode, all dentries and corresponding inodes are pinned in
105 memory from creation time.   Yeah, this means we have chunks of metadata for
106 files we aren't using sitting around in RAM.  We also have the *files* sitting
107 around in RAM too.  Not that concerned, for now.  Plus, I don't want to reparse
108 the CPIO backing store to figure out inode fields, directory names, etc.
109
110 Page Cache:
111 -------------------------------------------
112 Every object that has pages, like an inode or the swap (or even direct block
113 devices) has a page_map tracking which of its pages are currently in memory.
114 This is called a struct address_space in linux, which is a confusing name.  We
115 don't have all of the same fields yet, and may be doing things slightly
116 differently, but the basics are the same.  Together, the page_maps and the
117 functions to manipulate them make up the Page Cache.  Every page frame that is
118 in a page mapping can be traced back to its page_map, via pointers in the struct
119 page.  Note the page_mapping is tracked twice for a file, the f_mapping and the
120 i_mapping.  We really only need the i_mapping, but this saves a couple cache
121 misses.  Might go away later.
122
123 As a side note, Linux's "address_space" has a great example of the power of
124 their linked lists.  Their struct has a private_list head.  Due to their list
125 implementation, they are able to have a generic list head for a list of any
126 type (it's a struct list_head), and don't need to declare in a generic object
127 (like the page_map) a specific list type (that would get used by specific
128 FS's).
129
130 Just because a page is in a page_map, it doesn't mean it actually has the
131 data from the disc in it.  It just means that there is a physical frame
132 dedicated/mapped to be a page_map's holder for a specific page of an object
133 (usually a file on disc).  readpage() is called to fill that page in with what
134 it is supposed to have from its backing store.
135
136 This interpretation makes the meaning of "address space" make more sense.  It's
137 the "address space" of the device, mapping from (file,index) -> page_frame.
138 Still, calling it an address space just confuses things with the virtual memory
139 address space.
140
141 One of the reasons pages can be in the map without up-to-date data is due to
142 concurrency issues and outstanding I/O requests.  When the page is first being
143 filled up, the mapping exists but the data hasn't been brought in yet.  Other
144 processes can be trying to access the same block/page/byte, and they need to
145 block but to not try and schedule the operation.  
146
147 So here's how a typical page fault (__handle_page_fault(), either on demand or
148 populated) works on an mmap'd file at a high level.
149 1. PF is on a virt address -> translated by the vm_region to a file/offset (page).
150 1b. Weird permission issues?  See below!
151 2. Look it up in the page_map.
152 3. If the page is already there, and up-to-date, then great.  Skip to 6.  If
153 there is one, but it's not up to date, skip to 5.
154 4. If there is no page, get a free page, tie it (bidirectionally) to the inode
155 in the page_map.
156 5. Now there is a page, but it is not up to date, so call readpage().  This will
157 usually block.
158 6. Map that page (which has the current contents) into the address space of the
159 calling process (with the appropriate permissions, RO (MAP_PRIVATE, CoW), or
160 RW (MAP_SHARED).
161 Below: Now if in step 1 you had a permissions issue, such as a RW fault on a CoW
162 MAP_PRIVATE, you'll have to notice the type of error and the type of memory
163 region, then go through a separate path: get a new page, copy the contents, and
164 change the mapping.  Note, the page backing that mapping is not backed by the
165 file - it's just sitting around in the virtual memory of the process.
166
167 Also, if we want to use the PG_DIRTY flag, we'll need mark the regions as RO
168 until we write fault, at which point we dirty the page and change it to RW.
169
170 We could have multiple threads trying to fill a page in the page cache at once.
171 This is handled in file_load_page().  All threads check the page cache.  If two
172 threads try to add it to the page cache, only one will succeed, and the page
173 will be locked (PG_LOCKED).  The one who succeeds will readpage().  The one that
174 didn't will be like any other thread that is checking the page cache - it will
175 see a page is there, and will check it the page is up to date.  If it isn't, it
176 will try to lock the page so it can do the IO, with a few extra checks in case
177 the page had been removed or was filled in while it slept.
178
179 A big aspect of this is the use of lock_page() to block.  If the page is locked,
180 you block until it is unlocked.  (implementation and other issues still
181 pending).  Even the caller of readpage will lock after submitting the IO
182 request.  This will cause the caller to sleep until the IO is done.  When the IO
183 is done, that interrupt handler/thread will mark the page as up-to-date, and
184 unlock the page, which will wake up any of the waiters.  The caller of
185 readpage() may not be the first to wake up either.  This all means the IO system
186 needs to know about marking pages as up-to-date and unlocking them.  This
187 currently (Jul10) is just sitting in KFS, but can be done later either directly
188 or with a callback made by
189 whoever starts the IO.
190
191 A note on refcnting.  When a page is added to the page cache, that's a stored
192 reference.  When you lookup a page in the page cache, you get a refcnt'd
193 reference back.  When you pull a page from the page cache, you also get a
194 refcnt'd reference back - specifically it is the ref that was in the page map.
195
196 Files with Holes
197 --------------------------
198 If a file has a hole, we'll still try to look up the page in the page cache.
199 When that doesn't happen, we'll create and add a page, then call readpage().
200 Readpage will realize there is no page on disk/backing store for that part of
201 the file (since it was a hole) and just memset the page to 0.  In the future, we
202 can consider getting a CoW 0-page, but that's a bit premature and a bookkeeping
203 pain.
204
205 This also applies to trying to write to a block beyond the EOF.  If the request
206 hits the page cache and readpage(), it's because it was already checked and
207 cleared in another part of the VFS, such as in generic_file_write().