Dentry cache
[akaros.git] / Documentation / vfs.txt
index 5a9d86a..569753f 100644 (file)
@@ -116,7 +116,9 @@ don't have all of the same fields yet, and may be doing things slightly
 differently, but the basics are the same.  Together, the page_maps and the
 functions to manipulate them make up the Page Cache.  Every page frame that is
 in a page mapping can be traced back to its page_map, via pointers in the struct
-page.
+page.  Note the page_mapping is tracked twice for a file, the f_mapping and the
+i_mapping.  We really only need the i_mapping, but this saves a couple cache
+misses.  Might go away later.
 
 As a side note, Linux's "address_space" has a great example of the power of
 their linked lists.  Their struct has a private_list head.  Due to their list
@@ -136,8 +138,246 @@ the "address space" of the device, mapping from (file,index) -> page_frame.
 Still, calling it an address space just confuses things with the virtual memory
 address space.
 
-One of the reasons pages can be in the map without valid data is due to
+One of the reasons pages can be in the map without up-to-date data is due to
 concurrency issues and outstanding I/O requests.  When the page is first being
 filled up, the mapping exists but the data hasn't been brought in yet.  Other
 processes can be trying to access the same block/page/byte, and they need to
 block but to not try and schedule the operation.  
+
+So here's how a typical page fault (__handle_page_fault(), either on demand or
+populated) works on an mmap'd file at a high level.
+1. PF is on a virt address -> translated by the vm_region to a file/offset (page).
+1b. Weird permission issues?  See below!
+2. Look it up in the page_map.
+3. If the page is already there, and up-to-date, then great.  Skip to 6.  If
+there is one, but it's not up to date, skip to 5.
+4. If there is no page, get a free page, tie it (bidirectionally) to the inode
+in the page_map.
+5. Now there is a page, but it is not up to date, so call readpage().  This will
+usually block.
+6. Map that page (which has the current contents) into the address space of the
+calling process (with the appropriate permissions, RO (MAP_PRIVATE, CoW), or
+RW (MAP_SHARED).
+Below: Now if in step 1 you had a permissions issue, such as a RW fault on a CoW
+MAP_PRIVATE, you'll have to notice the type of error and the type of memory
+region, then go through a separate path: get a new page, copy the contents, and
+change the mapping.  Note, the page backing that mapping is not backed by the
+file - it's just sitting around in the virtual memory of the process.
+
+Also, if we want to use the PG_DIRTY flag, we'll need mark the regions as RO
+until we write fault, at which point we dirty the page and change it to RW.
+
+We could have multiple threads trying to fill a page in the page cache at once.
+This is handled in file_load_page().  All threads check the page cache.  If two
+threads try to add it to the page cache, only one will succeed, and the page
+will be locked (PG_LOCKED).  The one who succeeds will readpage().  The one that
+didn't will be like any other thread that is checking the page cache - it will
+see a page is there, and will check it the page is up to date.  If it isn't, it
+will try to lock the page so it can do the IO, with a few extra checks in case
+the page had been removed or was filled in while it slept.
+
+A big aspect of this is the use of lock_page() to block.  If the page is locked,
+you block until it is unlocked.  (implementation and other issues still
+pending).  Even the caller of readpage will lock after submitting the IO
+request.  This will cause the caller to sleep until the IO is done.  When the IO
+is done, that interrupt handler/thread will mark the page as up-to-date, and
+unlock the page, which will wake up any of the waiters.  The caller of
+readpage() may not be the first to wake up either.  This all means the IO system
+needs to know about marking pages as up-to-date and unlocking them.  This
+currently (Jul10) is just sitting in KFS, but can be done later either directly
+or with a callback made by
+whoever starts the IO.
+
+A note on refcnting.  When a page is added to the page cache, that's a stored
+reference.  When you lookup a page in the page cache, you get a refcnt'd
+reference back.  When you pull a page from the page cache, you also get a
+refcnt'd reference back - specifically it is the ref that was in the page map.
+
+Files with Holes
+--------------------------
+If a file has a hole, we'll still try to look up the page in the page cache.
+When that doesn't happen, we'll create and add a page, then call readpage().
+Readpage will realize there is no page on disk/backing store for that part of
+the file (since it was a hole) and just memset the page to 0.  In the future, we
+can consider getting a CoW 0-page, but that's a bit premature and a bookkeeping
+pain.
+
+This also applies to trying to write to a block beyond the EOF.  If the request
+hits the page cache and readpage(), it's because it was already checked and
+cleared in another part of the VFS, such as in generic_file_write().
+
+Kref, Dentries, Inodes, and Files (or "I don't see why it's like X, but..."
+--------------------------
+There are multiple dentries pointing to an inode.  The dentries are (or will be)
+cached too, but that is irrelevant.  The dentries pin the inodes in memory.
+However, files pin inodes in memory (or they did) briefly.  After running around
+in circles a bit, I asked, why doesn't the file pin the dentry instead of the
+inode?  The answer: it is supposed to.  Linux does that, and I didn't because
+pinning the inode made more sense at the time.
+
+The heart of the issue is about understanding what files are and how they
+relate to the rest of the VFS.  A 'file' in the OS is a structure to track an
+open FS-disk-file, which is managed by the inode.  Given this, it makes sense
+that a dentry (which is a name on a path) would be pinned by the corresponding
+inode, and the file would pin the inode.  It doesn't, but it is believable.  In
+reality, there are many names (dentries) for a given disk file, and the OS file
+that you open corresponds to *one* of those names, and thus a dentry, and not to
+the inode/specific file.  You need to go through the dentry to pin the inode.
+
+In short, it's not: file -> inode -> dentry -> parent_dentry -> ...
+It's file -> dentry -> parent_dentry ->
+             |-> inode      |-> parent_inode
+Another dentry and file (both OS and disk) can point to the same inode.  If you
+don't do it this way, you can't pin up past the multi-dentry-point in the inode,
+and your system doesn't really make sense.
+
+So here is how it works: files pin dentries.  Dentries can pin other dentries,
+on up the directory hierarchy.  Independently of the files, dentries pin their
+inode.  There are many dentries per inode (or can be).  Since each dentry
+doesn't know if it is the last dentry to decref the inode, we use a kref on
+i_kref.  The inodes are storing references to the dentries, but they are the
+kref "internal" / weak references.  Even if we did decref them, we don't trigger
+anything with it.
+
+The moral of the story is that if you don't fully understand something, you are
+not in as good of a position to recommend changes or criticize as if you did
+your homework.  Not that you can't, just that you should 'do your homework.'
+
+Musings on path_lookup()
+--------------------------
+Things can get tricky with path lookup, especially with ., .., and symlinks.
+When doing a LOOKUP_PARENT on a . or .., we give the parent of whatever the path
+would have resolved too.  So /dir1/dir2/dir3/.'s parent is dir2.
+/dir1/dir2/dir3/..'s parent is dir1.  I don't think Linux does this (note the
+parent lookup is for internal kernel stuff, like when you want to edit
+metadata).  When you try to make a . or .. file, you should get some sort of
+error anyways.  We'll see how this works out.
+
+Symlinks can be a bit tricky.  We handle ours a bit differently too, especially
+regarding PARENT lookups.  Ultimately, you can do the same things in ROS that
+you can do in Linux - if you try to create a file that is a dangling symlink,
+you'll correctly create the destination file.  We handle this in
+link_path_walk().  It will return the PARENT of whatever you would resolve to -
+instead of trying to handle this in do_file_open() (which I think linux does).
+
+Also, our handling of symlinks differs a bit from linux.  Eventually, it has
+become clear we're going to need to manually port ext2, and we do some things
+differently in our core VFS already.  Might as well do more thing differently -
+like getting rid of follow_link and put_link from the FS specific sections.  Our
+FSs just need to know how to return a char* for a symname - and not do any of
+the actual link following.  Or any of the other stuff they do.  We'll see if
+that turns out to be an issue or not...
+
+Unlinking and other Link Stuff
+-------------------------
+Unlinking is just disconnecting a dentry-inode pair from the directory tree, and
+decreasing the inode's i_nlink.  Nothing else happens yet, since we need to keep
+the FS-file (controlled by the dentry/inode) so long as any OS-files have it
+open.  They have it opened via open or mmap - any way that there is a reference
+to a file, which then pins the dentry and inode.  When the OS-files close,
+eventually the dentry's refcnt hits 0.  When it does, it normally would be up
+for caching, but we can check nlinks and just drop it.  When that happens, it
+releases the inode, which will see its nlinks is 0.  That will trigger the
+underlying FS to clear out the FS-file.
+
+For directories, you can only have one hardlink to a directory - meaning you are
+only in the directory tree in one place.  However, all of your children can get
+to you by going '../'.  We'll count these as hardlinks too.  This means that
+every child increments its parent-dir's nlink.  This is the on-disk links, not
+to be confused with the dentry->d_parent and kref() business that goes on for
+the in-memory objects.  A directory cannot be removed if nlinks > 1.  If it is
+1, then you can rmdir it, which will set its nlinks to 0.  Then its inode's
+storage space will get freed when it is deleted, like any other inode.  In
+theory.
+
+Inodes: drop? delete? dealloc?
+--------------------------
+Inodes exist both in memory and on disk, but in different manners.  When a file
+(F_WHATEVER, could be DIR) exists in an FS, it'll have an inode on disk.  When
+it is time to delete that file, we call _delete_inode().  When we want to free
+the memory associated with an in-memory (VFS) inode, we call _dealloc_inode().
+
+What about drop_inode?  For now, we don't use it.  We have inode_release() in
+the VFS.  If we need an FS specific one (like for ext2), or have FS-specific
+work that needs to be done in inode_release(), we'll use it later.
+
+Either way, inode_release() is called when we no longer use the in-memory inode.
+If there are no hard links, it will delete the inode.  Either way, it will just
+free the in-memory inode (after deleting the disc version).
+
+Example: I want to unlink (rm) a file.  There are two cases: the file is already
+open (with a dentry and the inode in memory) or the file is not.  Both cases are
+handled the same way!  In either case, we eventually call do_lookup on the item
+in question, getting both a dentry and its inode read in.  (We read it in for a
+couple reasons: convenient to check the type, and we need to manipulate the
+nlink).  If a process has the file open, or even if it is sitting in the cache,
+we will get the same inode (from the inode cache, might not be implemented yet).
+When we decref the dentry and it is done, it will decref the inode.  This
+dentry's final decref will be deferred until any open files are closed.  Note,
+this requires a working dentry/inode-cache - otherwise we'll have multiple
+copies of the same FS/disk-inode (and possibly dentry).  Anyway, when this is
+done, the release function will delete the inode, then dealloc it.
+
+Another example:  We simply close a file.  When that happens, we decref the
+dentry, which decrefs the inode.  It may remain cached for a bit - not a big
+deal.  When it is finally removed, nlinks is positive, so the inode's in memory
+copy is written back (if it was dirty) and the structure is deallocated.
+
+Side notes: dentry cached inodes should be removed after their lookup in unlink.
+Also, since multiple dentries point to the same inode, it's not enough to just
+cache dentries - we need to be able to find inodes too so that we get the one
+inode regardless of which dentry we use (which may be uncached).
+
+Dentry and Inode Caches
+--------------------------
+The dentry caches dentry lookups - we need the parent and a hash of the name to
+do a lookup.  The dcache consists of a hash table for the lookups, as well as an
+extra list of entries that are unused (their kref is 0).  The dcache also caches
+negative entries - entries that were wrong.  This still speeds up future
+requests.  Most uses of the system just need to use dcache_get and dcache put.
+Not all of this is implemented yet.
+
+The inode cache is similar, though we can't just have the inodes hang off the
+dentry cache (more than one dentry points to the same inode).  We don't need to
+worry about unused lists or anything like that - once the kref hits 0, we're
+done and we can rip it out of the hash.
+
+Both hashes hang off the superblock, with concurrent access protected by locks
+in the SB.
+
+The dentry cache is the weirdest of them all - for normal entries, its key and
+value are the same thing.  The actual hashing of a dentry is done by the qstr
+value, and to determine equality, we need to compare parents (compared to the
+inode cache, where the only thing that matters is the i_ino).  Put another way,
+we need elements of the whole dentry to get a unique key (d_parent and d_name).
+
+As stated above, the dcache also caches negative entries.  This is to prevent a
+lookup on disk.  These negative entries are in the dcache and on the LRU list
+(their refcnt is 0, the are not USED).  When we dcache_get, we don't bother with
+returning the actual dentry (after increffing) and then decref it again.
+Instead, we just return the negative result (via the query dentry,
+incidentally).
+
+Freeing of dentries happens in one of two ways: call __dentry_free() directly,
+which is appropriate when you have the only copy (like in do_lookup()), or it
+will get freed when the dcache gets reaped (the LRU entries are freed).  When it
+is decref'd, it simply goes into a state where it is ready to be reaped, but
+kept around for future lookups - most usages throughout the vfs can just decref
+when they are done using it.
+
+One complication is cached negative dentries.  These are only referenced once
+(in the dcache), so they can get __dentry_free()d directly.  This gets tricky
+with rmdir and unlink.  Initially, those functions marked the dentry as negative
+and unused, and would let them stay in the dcache (returning negative results on
+future lookups).  The problem with this is that now the dcache could have a
+negative dentry that was a real, formerly used dentry - one with a refcnt that
+needs to be decref'd and released.  
+
+There are two solutions: one is to change the dcache to not assume that negative
+entries are unreferenced (which also means on the LRU).  The other is to just
+remove the dentry from the dcache on rmdir/unlink.  It won't be negative - and
+that won't matter, since it is un-lookup-able.  And it will die nicely when it
+gets decref'd.  All we'll do is add a DENTRY_DYING flag, and dentry_release()
+will avoid LRU and unusing it.  The dcache can continue to assume that negative
+entries are unused/LRU/dentry_freeable/ref==0, and not worry about calling
+kref_put().