f0c415b77fa6af7acca4bb280c712fade2b3c708
[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().
208
209 Kref, Dentries, Inodes, and Files (or "I don't see why it's like X, but..."
210 --------------------------
211 There are multiple dentries pointing to an inode.  The dentries are (or will be)
212 cached too, but that is irrelevant.  The dentries pin the inodes in memory.
213 However, files pin inodes in memory (or they did) briefly.  After running around
214 in circles a bit, I asked, why doesn't the file pin the dentry instead of the
215 inode?  The answer: it is supposed to.  Linux does that, and I didn't because
216 pinning the inode made more sense at the time.
217
218 The heart of the issue is about understanding what files are and how they
219 relate to the rest of the VFS.  A 'file' in the OS is a structure to track an
220 open FS-disk-file, which is managed by the inode.  Given this, it makes sense
221 that a dentry (which is a name on a path) would be pinned by the corresponding
222 inode, and the file would pin the inode.  It doesn't, but it is believable.  In
223 reality, there are many names (dentries) for a given disk file, and the OS file
224 that you open corresponds to *one* of those names, and thus a dentry, and not to
225 the inode/specific file.  You need to go through the dentry to pin the inode.
226
227 In short, it's not: file -> inode -> dentry -> parent_dentry -> ...
228 It's file -> dentry -> parent_dentry ->
229              |-> inode      |-> parent_inode
230 Another dentry and file (both OS and disk) can point to the same inode.  If you
231 don't do it this way, you can't pin up past the multi-dentry-point in the inode,
232 and your system doesn't really make sense.
233
234 So here is how it works: files pin dentries.  Dentries can pin other dentries,
235 on up the directory hierarchy.  Independently of the files, dentries pin their
236 inode.  There are many dentries per inode (or can be).  Since each dentry
237 doesn't know if it is the last dentry to decref the inode, we use a kref on
238 i_kref.  The inodes are storing references to the dentries, but they are the
239 kref "internal" / weak references.  Even if we did decref them, we don't trigger
240 anything with it.
241
242 The moral of the story is that if you don't fully understand something, you are
243 not in as good of a position to recommend changes or criticize as if you did
244 your homework.  Not that you can't, just that you should 'do your homework.'
245
246 Musings on path_lookup()
247 --------------------------
248 Things can get tricky with path lookup, especially with ., .., and symlinks.
249 When doing a LOOKUP_PARENT on a . or .., we give the parent of whatever the path
250 would have resolved too.  So /dir1/dir2/dir3/.'s parent is dir2.
251 /dir1/dir2/dir3/..'s parent is dir1.  I don't think Linux does this (note the
252 parent lookup is for internal kernel stuff, like when you want to edit
253 metadata).  When you try to make a . or .. file, you should get some sort of
254 error anyways.  We'll see how this works out.
255
256 Symlinks can be a bit tricky.  We handle ours a bit differently too, especially
257 regarding PARENT lookups.  Ultimately, you can do the same things in ROS that
258 you can do in Linux - if you try to create a file that is a dangling symlink,
259 you'll correctly create the destination file.  We handle this in
260 link_path_walk().  It will return the PARENT of whatever you would resolve to -
261 instead of trying to handle this in do_file_open() (which I think linux does).
262
263 Also, our handling of symlinks differs a bit from linux.  Eventually, it has
264 become clear we're going to need to manually port ext2, and we do some things
265 differently in our core VFS already.  Might as well do more thing differently -
266 like getting rid of follow_link and put_link from the FS specific sections.  Our
267 FSs just need to know how to return a char* for a symname - and not do any of
268 the actual link following.  Or any of the other stuff they do.  We'll see if
269 that turns out to be an issue or not...
270
271 Unlinking and other Link Stuff
272 -------------------------
273 Unlinking is just disconnecting a dentry-inode pair from the directory tree, and
274 decreasing the inode's i_nlink.  Nothing else happens yet, since we need to keep
275 the FS-file (controlled by the dentry/inode) so long as any OS-files have it
276 open.  They have it opened via open or mmap - any way that there is a reference
277 to a file, which then pins the dentry and inode.  When the OS-files close,
278 eventually the dentry's refcnt hits 0.  When it does, it normally would be up
279 for caching, but we can check nlinks and just drop it.  When that happens, it
280 releases the inode, which will see its nlinks is 0.  That will trigger the
281 underlying FS to clear out the FS-file.
282
283 For directories, you can only have one hardlink to a directory - meaning you are
284 only in the directory tree in one place.  However, all of your children can get
285 to you by going '../'.  We'll count these as hardlinks too.  This means that
286 every child increments its parent-dir's nlink.  This is the on-disk links, not
287 to be confused with the dentry->d_parent and kref() business that goes on for
288 the in-memory objects.  A directory cannot be removed if nlinks > 1.  If it is
289 1, then you can rmdir it, which will set its nlinks to 0.  Then its inode's
290 storage space will get freed when it is deleted, like any other inode.  In
291 theory.
292
293 Inodes: drop? delete? dealloc?
294 --------------------------
295 Inodes exist both in memory and on disk, but in different manners.  When a file
296 (F_WHATEVER, could be DIR) exists in an FS, it'll have an inode on disk.  When
297 it is time to delete that file, we call _delete_inode().  When we want to free
298 the memory associated with an in-memory (VFS) inode, we call _dealloc_inode().
299
300 What about drop_inode?  For now, we don't use it.  We have inode_release() in
301 the VFS.  If we need an FS specific one (like for ext2), or have FS-specific
302 work that needs to be done in inode_release(), we'll use it later.
303
304 Either way, inode_release() is called when we no longer use the in-memory inode.
305 If there are no hard links, it will delete the inode.  Either way, it will just
306 free the in-memory inode (after deleting the disc version).
307
308 Example: I want to unlink (rm) a file.  There are two cases: the file is already
309 open (with a dentry and the inode in memory) or the file is not.  Both cases are
310 handled the same way!  In either case, we eventually call do_lookup on the item
311 in question, getting both a dentry and its inode read in.  (We read it in for a
312 couple reasons: convenient to check the type, and we need to manipulate the
313 nlink).  If a process has the file open, or even if it is sitting in the cache,
314 we will get the same inode (from the inode cache, might not be implemented yet).
315 When we decref the dentry and it is done, it will decref the inode.  This
316 dentry's final decref will be deferred until any open files are closed.  Note,
317 this requires a working dentry/inode-cache - otherwise we'll have multiple
318 copies of the same FS/disk-inode (and possibly dentry).  Anyway, when this is
319 done, the release function will delete the inode, then dealloc it.
320
321 Another example:  We simply close a file.  When that happens, we decref the
322 dentry, which decrefs the inode.  It may remain cached for a bit - not a big
323 deal.  When it is finally removed, nlinks is positive, so the inode's in memory
324 copy is written back (if it was dirty) and the structure is deallocated.
325
326 Side notes: dentry cached inodes should be removed after their lookup in unlink.
327 Also, since multiple dentries point to the same inode, it's not enough to just
328 cache dentries - we need to be able to find inodes too so that we get the one
329 inode regardless of which dentry we use (which may be uncached).
330
331 Dentry and Inode Caches
332 --------------------------
333 The dentry caches dentry lookups - we need the parent and a hash of the name to
334 do a lookup.  The dcache consists of a hash table for the lookups, as well as an
335 extra list of entries that are unused (their kref is 0).  The dcache also caches
336 negative entries - entries that were wrong.  This still speeds up future
337 requests.  Most uses of the system just need to use dcache_get and dcache put.
338 Not all of this is implemented yet.
339
340 The inode cache is similar, though we can't just have the inodes hang off the
341 dentry cache (more than one dentry points to the same inode).  We don't need to
342 worry about unused lists or anything like that - once the kref hits 0, we're
343 done and we can rip it out of the hash.
344
345 Both hashes hang off the superblock, with concurrent access protected by locks
346 in the SB.
347
348 The dentry cache is the weirdest of them all - for normal entries, its key and
349 value are the same thing.  The actual hashing of a dentry is done by the qstr
350 value, and to determine equality, we need to compare parents (compared to the
351 inode cache, where the only thing that matters is the i_ino).  Put another way,
352 we need elements of the whole dentry to get a unique key (d_parent and d_name).
353
354 As stated above, the dcache also caches negative entries.  This is to prevent a
355 lookup on disk.  These negative entries are in the dcache and on the LRU list
356 (their refcnt is 0, the are not USED).  When we dcache_get, we don't bother with
357 returning the actual dentry (after increffing) and then decref it again.
358 Instead, we just return the negative result (via the query dentry,
359 incidentally).
360
361 Freeing of dentries happens in one of two ways: call __dentry_free() directly,
362 which is appropriate when you have the only copy (like in do_lookup()), or it
363 will get freed when the dcache gets reaped (the LRU entries are freed).  When it
364 is decref'd, it simply goes into a state where it is ready to be reaped, but
365 kept around for future lookups - most usages throughout the vfs can just decref
366 when they are done using it.
367
368 One complication is cached negative dentries.  These are only referenced once
369 (in the dcache), so they can get __dentry_free()d directly.  This gets tricky
370 with rmdir and unlink.  Initially, those functions marked the dentry as negative
371 and unused, and would let them stay in the dcache (returning negative results on
372 future lookups).  The problem with this is that now the dcache could have a
373 negative dentry that was a real, formerly used dentry - one with a refcnt that
374 needs to be decref'd and released.  
375
376 There are two solutions: one is to change the dcache to not assume that negative
377 entries are unreferenced (which also means on the LRU).  The other is to just
378 remove the dentry from the dcache on rmdir/unlink.  It won't be negative - and
379 that won't matter, since it is un-lookup-able.  And it will die nicely when it
380 gets decref'd.  All we'll do is add a DENTRY_DYING flag, and dentry_release()
381 will avoid LRU and unusing it.  The dcache can continue to assume that negative
382 entries are unused/LRU/dentry_freeable/ref==0, and not worry about calling
383 kref_put().
384
385 X: Buffer Cache, Page Cache, Buffer Heads, WTH?
386 -------------------------------
387 X.1: Page vs Buffer Cache
388 --------------------
389 So we discussed the page cache, but as described, it does not satisfy all of
390 our disk caching needs.  Traditionally, there would also be a 'buffer cache.'
391 Buffers usually refer to memory used to hold data from the disk (or network).
392 I can think of a couple different ways someone could think of the buffer
393 cache, and to understand them, we first need to understand what we need to be
394 caching.
395
396 There are two main types of FS data: file data and metadata.  This metadata
397 is FS-specific data accessed by the VFS to get to a file's contents.  For
398 example, the superblock, inodes, inode indirect blocks, and to a certain
399 extent the directory's contents are all metadata.  There isn't an FS file (not
400 to be confused with an OS file) that corresponds to this data, but it needs to
401 be read in and cached.  Furthermore, this cache needs to be managed and
402 written back when dirty.
403
404 A very simple buffer cache would include anything *ever* read from disk.  It
405 would then get copied into the page cache in PGSIZE chunks for the page cache.
406 This would suck, since we now have two or three copies.
407
408 Another buffer cache would be to cache only the disk blocks needed for
409 metadata.  I think this is what Linux did before it unified its buffer and
410 page caches (implied in UTLK).  The main issue with this is that you have two
411 different systems for managing essentially similar data - we only want to deal
412 with flushing, syncing, and writebacks of one subsystem, not in multiple
413 different systems.
414
415 The solution is to use the page cache to cache the metadata block operations.
416 We do this by having the block device be mapped in PGSIZE chunks through its
417 own struct page_mapping (a.k.a. struct address_space in Linux).  This way,
418 both files and the block device are mapped in PGSIZE chunks via the same
419 page_mapping structure, and will be managed by the same code.
420
421 X.2: Mapping Blockdev Data vs File Data
422 --------------------
423 An important distinction between file data (as managed by an inode) and the
424 bdev is that PGSIZE chunks of data for the bdev *must* be made of contiguous
425 disk blocks.  Ideally, file data is also contiguous/sequential, but that is
426 not always the case - hence the need for the inode's block pointers.  This
427 means that the chunk at the bottom of the page_mapping radix tree is a page,
428 and on that page there may be several buffers, holding the data of
429 nonsequential disk blocks - but that not all pages are like this.  The bdev
430 pages are made up of sequential blocks due to the very nature of what we are
431 mapping; there's no inode abstraction in between.
432
433 There are a couple ways we could handle this.  We adopt the Linux approach of
434 using something called a buffer head (BH), which describes the mapping from
435 in-memory buffer to block device / block number.  These are slab-allocated,
436 and exist for each buffer of a page.  The page itself points to the first of
437 its BHs, all of which exist in a LL.  The maximum number of them is determined
438 by PGSIZE / blocksize.  Whenever there is a page in the page cache (meaning, in
439 a page_mapping), that is up to date, it will have a BH.
440
441 Another way would be to not have BHs at all, and just figure out (at
442 operation-time) what the n blocks on disk are for any given page, and submit
443 the IO operations for those blocks.  The BHs serve as a cache of that info.
444 They also serve as a location to store data about the mapping, such as whether
445 it is dirty or not, whether the data is up to date or not (has it been read
446 in), etc.  The caching ought to be rather beneficial, since it means we do not
447 need to access the disk-inode and indirect blocks whenever we want to perform
448 an operation (which may be frequent - imagine the periodic writeback of an
449 mmap'd file undergoing writes).  The per-buffer dirty tracking will also help:
450 no need to write unrelated blocks if only one is edited (though this will not
451 help with mmap(), since we don't usually know which part of the page is
452 written).
453
454 X.4: Do we always need BHs?
455 ------------------
456 But what about those pages made up of contiguous blocks?  We don't have a
457 bunch of independent, non-sequential blocks that we need to map.  Do we need a
458 bunch of BHs for that?  Do we need any?  It really seems excessive to break it
459 up into separate buffers for no reason.  At the other extreme, we could get by
460 without having a BH at all, though this gets back to the other issue of
461 caching.  What we do (or will do) is have one BH for the entire page of
462 contiguous blocks.  If the page is a "buffer page," in Linux terms (meaning it
463 has separate buffers), it will have n BHs in a LL.  Either way, we'll always
464 have the mapping handy.  We wouldn't need to re-verify the contiguous nature of
465 the blocks anyways, since the fact that the page was up to date and didn't need
466 a BH would mean it was contiguous.  Further benefits to using the one BH
467 include: 1) we are likely to make BHs be the unit of IO *submission*, and having
468 one handy will simplify that code. 2) some code paths within the VFS may get BHs
469 as a return value, which they can then dirty.  Always having a BH makes this
470 easier (no need to find out if it's a buffer page, then decide how to dirty it).
471
472 Another compliation with this is certain code will want a block in the middle
473 of a page (very common for metadata).  That code will get the BH for the
474 entire page back.  It will need to determine the starting block and then the
475 offset of the block it wants.  Note, this usage of the BHs is finding the
476 buffer corresponding to a block number.  The BH is a bidirectional mapping
477 between buffers and blockdev:blocknum.  These calculations are a minor
478 complication, but easy enough to do, and will probably be worth it.  The
479 tradeoff is against having multiple BHs, which would mean multiple block IO
480 requests for writing a single page (and writing the whole page may be a common
481 operation).
482
483 X.3: What about opening a blockdev?
484 --------------------
485 All of this means we are using the page cache to cache metadata blocks from
486 the block device.  But what about the other blocks?  Those are "file" blocks,
487 which are in the page mapping of the inode.  But what about when the block
488 device is opened as if it was a file?  And then if we were to access the file
489 blocks in this manner?  Yeah, that would screw things up - you will get
490 inconsistencies, under the current plan.  There is one easy way to avoid this:
491 don't open a bdev file if a file system is mounted on top of it.  If you do,
492 don't be surprised about inconsistencies.  Ideally, the FS will never leave
493 the actual disk in an inconsistent state, but the bdev's page cache could read
494 things at different times and get some weird results.  Just don't do this (for
495 now - not like I plan to make this possible any time soon).
496
497 Could we use the same buffers for both the blockdev-file page mapping and the
498 inode-file page mapping?  No - because the inode-file has the inode
499 indirection in between, which means a PGSIZE chunk of the file might not be
500 contiguous (as mentioned above).
501
502 We could have tried to avoid this bdev file problem by having the page mapping
503 radix trees point to a set of BHs that describes that page worth of buffers,
504 so that the bdev and an inode pointing to the same data will use the same
505 buffers and BHs.  That won't work, since the files buffers/blocks aren't in
506 the same order as they are on disk within a page.  Instead, we'd need to have
507 the page mapping go down to the FS's blocksize granularity, not to PGSIZE, so
508 that we could have independent leaves point to wherever they want.  This would
509 push the specific block device's blocksize into the VFS (which I don't like).
510
511 But the blocksize-infecting-the-VFS alone isn't too bad.  The real issue is
512 what is at the end of the page mapping.  Is it a page or a buffer/BH?  We want
513 pages for two related reasons: higher levels of the kernel's IO systems deal
514 with pages:
515 1. mmap().  Good old mmap() requires at least a page of contiguous block
516 buffers, so that the physical page frame can be mapped directly into a
517 process's address space.
518 2. Fast IO.  We want to use page remapping for fast IO.  This means that IO
519 has to be in PGSIZE chunks - not blocksize chunks.
520
521 x.4: Managing Dirty Buffers
522 --------------------
523 Many (some/all?) of the block functions will return a BH to describe the
524 mapping.  One reason for doing this (mentioned above) is to allow the caller
525 to manage if a buffer is dirty or not.  The tracking of dirty pages is done by
526 the page cache.  The dirtying is done by the caller; it can simply mark the BH
527 dirty and forget about it.  The writeback is handled usually by the page cache
528 or is triggered by an FS event.  Eventually, we'll have a kernel thread that
529 periodically writes dirty buffers back to disk.  Processes can also do this by
530 calling fsync.  FSs themselves will trigger syncs of metadata.  This will come
531 from having dirty SBs and inodes in the VFS.
532
533 Note, the issue of whether or not we pin metadata blocks, such as the inode's
534 indirect blocks (or other related blocks), in the page cache is independent of
535 all these issues.  If they are not cached / pinned, we would just have to
536 block and reread the inode's structures back into memory and proceed (for
537 instance, we'd do this when identifying blocks for a page mapping on a file
538 read).  The reason we wouldn't want to pin them is to save memory.
539
540 x.5: Reference Counting BHs and Pages
541 --------------------
542 So we talk about passing around BHs, both when submitting IO ops and when
543 returning from things like read_block() (note: this may return pages, not
544 BHs).  However, we do not kref or reference count BHs in any way.  Instead, we
545 kref pages.  We do this (for now) for a couple reasons:
546 1) Pages are the unit of memory management in the kernel.  Higher levels of
547 the kernel will pin/incref the page (such as in an mmap()).
548 2) BHs hang off of a page, but exist only to be expressive about the
549 management of the buffers on the page.  It's not like how a file hangs off a
550 dentry, where the dentry doesn't know (or care) about the file.
551 3) We already refcount pages.  While we could do the same for the BHs, it is a
552 bit redundant.  Any place that would be kreffing the BH can just kref the
553 whole page.
554
555 When a page is in the page cache, we give it one kref.  Whenever a function or
556 subsystem is using one of these pages (IO, using the data, etc), there needs
557 to be a kref.  When it is time to remove the page from the page mapping, the
558 code needs to remove it from the radix tree, then kref_put it.  When the final
559 user is done with it (ideally, there is none, but we need to handle the case)
560 the release function will clean up the page - including freeing its BHs.
561
562 This does suck in that we could be removing an item from the page cache while
563 it is being used, violating some LRU policy.  The actual decision to remove it
564 should use those policies (when possible); the kreffing is simply to avoid
565 issues from race conditions.  (A reader starts using a page right before it is
566 ripped from the mapping).
567
568 One issue with this is that dirty pages/buffers will need to be written back.
569 If someone tries to read while the page is removed from the page_mapping, but
570 before it is written back, they could get an old version if the read happens
571 before the write.  This is only an issue if the page is dirty.  One option
572 would be to writeback the page/buffer, then later remove it from the page
573 cache when it is read.  There's issues with concurrent writers, though if that
574 happens, we probably don't really want to remove it (it was LRU).  Note this
575 is an issue regardless of whether or not BHs are refcounted.
576
577 Also note that writeback of pages will happen regardless of eviction plans
578 (fsync, every n sec, etc).
579
580 This refcounting pattern is very similar to unlinking, where you can continue
581 to access a file once it is removed from the directory.  The difference here
582 is that future requests will get the same object (the page), unlike in the FS,
583 where you get ENOENT.  The page mapping is a cache, and you need to get the
584 same old data that was in there before the eviction.
585
586 A final issue is when the VFS aggressively pins blockdev (metadata)
587 pages/buffers.  Ideally, we'd like to be able to expel pages/buffers even if
588 they are refcnt'd.  The subsystems will always want to keep stuff in RAM.
589 This also/especially applies to mmap().  One solution would be to keep them in
590 RAM, but have the BH keep track of who is holding its reference.  Then we
591 could unmap the page, which would need to get read back in on its next access.
592 We'd need (or ought to have) some sort of callbacks.  This will get solved
593 later when we deal with unmapping mmap'd files.