Dentry cache
[akaros.git] / Documentation / vfs.txt
index 4d1ee48..569753f 100644 (file)
@@ -205,3 +205,179 @@ 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().