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