Dentry cache
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 10 Sep 2010 23:58:20 +0000 (16:58 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:53 +0000 (17:35 -0700)
This is pretty hefty, and shows some of the issues associated with the
'cached kref'.

Documentation/kref.txt
Documentation/vfs.txt
kern/include/kref.h
kern/include/vfs.h
kern/src/ext2fs.c
kern/src/kfs.c
kern/src/monitor.c
kern/src/vfs.c

index 2b61bcb..81fd564 100644 (file)
@@ -34,9 +34,9 @@ kref_get_not_zero().  You must have an internal reference for this.  And to
 protect that *internal* reference, you often need to lock or otherwise sync
 around the source of that internal reference (usually a list-like structure
 (LLS)), unless that ref is otherwise protected from concurrent freeing.
-4. If you plan to reincarnate an object (make its refcnt go from 0 to 1), you
+4. If you plan to ressurect an object (make its refcnt go from 0 to 1), you
 need to use some other form of sync between the final freeing and the
-reincarnation.
+resurrection.
 
 We differ from Linux in a few of ways.  We have a kref_get_not_zero(), which
 they talk about in some of their documents, to be a bit more clear about getting
@@ -47,7 +47,7 @@ put the release function in the kref, which is what Linux used to do.  We do it
 to cut down on the number of places the function pointer is writen, since I
 expect those to change a lot as subsystems use krefs.  Finally, we only use
 krefs to trigger an object's release function, which might not free them
-forever.  They can be "reincarnated" back to having an external reference.  You
+forever.  They can be "ressurectd" back to having an external reference.  You
 can do similar things in Linux, but it's not clear (to me) how separate that
 idea is from a kref.
 
@@ -112,7 +112,7 @@ to seq counters and grace periods, discussed below).  This is the same issue,
 regardless of whether the internal reference is using another kref or if it uses
 some other scheme (like lock the object and check its state).
 
-Reincarnating an object after it hit 0
+Resurrecting an object after it hit 0
 ----------------------------
 So when we hit 0, we might not be completely done with the object.  This is part
 of the "kcref" (c == cached) design pattern the Linux guys talk about.  The main
@@ -134,14 +134,29 @@ which then the cache reader gets instead of failing at trying to get the
 original object.  The kref refcount only helps when the refcount goes from 1 to
 0, and on triggering the followup/release action.
 
-For now, we'll do the same thing in those situations, but may do something else
-that is similar (spinlock and seq-ctr per object), but first more digressions...
+To ressurect, we can't just do:
+       if (!kref_refcnt(&dentry->d_kref))
+               kref_init(&dentry->d_kref, dentry_release, 1);
+       else
+               kref_get(&dentry->d_kref, 1);
+
+There is a race on reading the refcnt and mucking with it.  If it is
+concurrently going from 1 -> 0, and we read 0, it is okay.  We still up it to 1.
+However, if we go from 1 -> 0 and read 1, we'll panic when we try to kref_get a
+0'd kref.  Also, doing this would be dangerous going from 0 -> 1 if other code
+would ressurect (which it does not!).  The solution is to use a kref_get that
+doesn't care about 0 (__kref_get()).
+
+Elsewhere in this documentation, we talk about kref_get_not_zero().  That one
+will try and fail gracefully (used by pid2proc()).  kref_get() will fail on
+zero.  __kref_get() will not fail on zero and will blindly increment, which is
+what we want. 
 
 Trickiness with lockless data structures:
 ----------------------------
 Ideally, we want concurrent access to the dentry cache (or whatever cache has
-krefd objects that we want to reincarnate).  Perhaps this is with CAS on linked
-lists, or locks per hash bucket.  Since we need to prevent the reincarnation of
+krefd objects that we want to ressurect).  Perhaps this is with CAS on linked
+lists, or locks per hash bucket.  Since we need to prevent the resurrection of
 objects from proceeding while another thread could be trying to remove them, we
 need some sync between readers and writers.  Both threads in the scenario we've
 been talking about are going to be writers for the object, though from the
@@ -229,17 +244,18 @@ it needs to try again.  "Safe" means not accessing freed memory - hence the
 grace periods on slab-freed pages.
 
 Kreffing works because we have a known, synchronous initialization point where
-we kref_init() the refcount to 1.  We can't do that easily when reincarnating or
+we kref_init() the refcount to 1.  We can't do that easily when resurrecting or
 even kref_get_not_zero() because another thread may be trying to permanently
 free the object.
 
-The difference between kref_get_not_zero() and reincarnation is that
+The difference between kref_get_not_zero() and resurrection is that
 get_not_zero() is trying to get an external reference and the object's release
-method has not been called.  Reincarnation is when we've already hit 0,
+method has not been called (or it has, and we should fail since our source is a
+weak/internal reference source).  Resurrection is when we've already hit 0,
 release()d, and now want to reuse that object.  For concrete examples:
 get_not_zero() works when getting a file off the superblock file list - it only
 should work if the file is still in the system and not about to be removed from
-the list.  Reincarnation is for objects that don't get freed when they lose
+the list.  Resurrection is for objects that don't get freed when they lose
 their external references, such as dentries (they get put on the dentry cache).
 On a cache hit for an unreferenced dentry, we'll need to change its state and
 reinit its refcount.  Next time it is kref_put()d to 0, it'll rerun its
index d6507b0..569753f 100644 (file)
@@ -327,3 +327,57 @@ 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().
index 1817a6d..5bfc89e 100644 (file)
@@ -39,9 +39,9 @@ static void kref_init(struct kref *kref, void (*release)(struct kref *kref),
        kref->release = release;
 }
 
-static struct kref *kref_get(struct kref *kref, unsigned int inc)
+/* Will blindly incref */
+static struct kref *__kref_get(struct kref *kref, unsigned int inc)
 {
-       assert(atomic_read(&kref->refcount));
        atomic_add(&kref->refcount, inc);
        return kref;
 }
@@ -54,6 +54,14 @@ static struct kref *kref_get_not_zero(struct kref *kref, unsigned int inc)
        else return 0;
 }
 
+/* Will panic on zero */
+static struct kref *kref_get(struct kref *kref, unsigned int inc)
+{
+       kref = kref_get_not_zero(kref, inc);
+       assert(kref);
+       return kref;
+}
+
 /* Returns True if we hit 0 and executed 'release', False otherwise */
 static bool kref_put(struct kref *kref)
 {
index d770c0e..c64613a 100644 (file)
@@ -19,6 +19,7 @@
 #include <kref.h>
 #include <timing.h>
 #include <radix.h>
+#include <hashtable.h>
 #include <blockdev.h>
 
 /* ghetto preprocessor hacks (since proc includes vfs) */
@@ -158,8 +159,13 @@ struct super_block {
        struct inode_tailq                      s_inodes;               /* all inodes */
        struct inode_tailq                      s_dirty_i;              /* dirty inodes */
        struct io_wb_tailq                      s_io_wb;                /* writebacks */
-       struct dentry_slist                     s_anon_d;               /* anonymous dentries */
        struct file_tailq                       s_files;                /* assigned files */
+       struct dentry_tailq                     s_lru_d;                /* unused dentries (in dcache)*/
+       spinlock_t                                      s_lru_lock;
+       struct hashtable                        *s_dcache;              /* dentry cache */
+       spinlock_t                                      s_dcache_lock;
+       struct hashtable                        *s_icache;              /* inode cache */
+       spinlock_t                                      s_icache_lock;
        struct block_device                     *s_bdev;
        TAILQ_ENTRY(super_block)        s_instances;    /* list of sbs of this fs type*/
        char                                            s_name[32];
@@ -244,6 +250,12 @@ struct inode_operations {
 };
 
 #define DNAME_INLINE_LEN 32
+
+/* Dentry flags.  All negatives are also unused. */
+#define DENTRY_USED                    0x01    /* has a kref > 0 */
+#define DENTRY_NEGATIVE                0x02    /* cache of a failed lookup */
+#define DENTRY_DYING           0x04    /* should be freed on release */
+
 /* Dentry: in memory object, corresponding to an element of a path.  E.g. /,
  * usr, bin, and vim are all dentries.  All have inodes.  Vim happens to be a
  * file instead of a directory.
@@ -267,8 +279,6 @@ struct dentry {
        struct vfsmount                         *d_mounted_fs;  /* fs mounted here */
        struct dentry                           *d_parent;
        struct qstr                                     d_name;                 /* pts to iname and holds hash*/
-       SLIST_ENTRY(dentry)                     d_hash;                 /* link for the dcache */
-       struct dentry_slist                     d_bucket;               /* hash bucket of this dentry */
        char                                            d_iname[DNAME_INLINE_LEN];
        void                                            *d_fs_info;
 };
@@ -409,10 +419,6 @@ extern struct sb_tailq super_blocks;                       /* list of all sbs */
 extern spinlock_t super_blocks_lock;
 extern struct fs_type_tailq file_systems;              /* lock this if it's dynamic */
 extern struct namespace default_ns;
-// TODO: should have a dentry_htable or something.  we have the structs built
-// in to the dentry right now (linux style).
-extern struct dentry_slist dcache;
-extern spinlock_t dcache_lock;
 
 /* Slab caches for common objects */
 extern struct kmem_cache *dentry_kcache;
@@ -436,9 +442,12 @@ void init_sb(struct super_block *sb, struct vfsmount *vmnt,
 /* Dentry Functions */
 struct dentry *get_dentry(struct super_block *sb, struct dentry *parent,
                           char *name);
-void dcache_put(struct dentry *dentry);
 void dentry_release(struct kref *kref);
+void __dentry_free(struct dentry *dentry);
 struct dentry *lookup_dentry(char *path, int flags);
+struct dentry *dcache_get(struct super_block *sb, struct dentry *what_i_want);
+void dcache_put(struct super_block *sb, struct dentry *key_val);
+struct dentry *dcache_remove(struct super_block *sb, struct dentry *key);
 
 /* Inode Functions */
 struct inode *get_inode(struct dentry *dentry);
index 9c157c3..ba092b1 100644 (file)
@@ -537,9 +537,8 @@ I_AM_HERE;
 
 /* Searches the directory for the filename in the dentry, filling in the dentry
  * with the FS specific info of this file.  If it succeeds, it will pass back
- * the *dentry you should use.  If this fails, it will return 0 and will take
- * the ref to the dentry for you.  Either way, you shouldn't use the ref you
- * passed in anymore.
+ * the *dentry you should use (which might be the same as the one you passed in).
+ * If this fails, it will return 0, but not free the memory of "dentry."
  *
  * Callers, make sure you alloc and fill out the name parts of the dentry.  We
  * don't currently use the ND.  Might remove it in the future.  */
@@ -575,7 +574,6 @@ struct dentry *ext2_lookup(struct inode *dir, struct dentry *dentry,
                dir_i = (void*)dir_i + dir_i->dir_reclen;
        }
        printd("EXT2: Not Found, %s\n", dentry->d_name.name);   
-       kref_put(&dentry->d_kref);
        kfree(dir_buf);
        return 0;
 }
index 09570a6..f40149d 100644 (file)
@@ -304,9 +304,9 @@ int kfs_create(struct inode *dir, struct dentry *dentry, int mode,
 
 /* Searches the directory for the filename in the dentry, filling in the dentry
  * with the FS specific info of this file.  If it succeeds, it will pass back
- * the *dentry you should use.  If this fails, it will return 0 and will take
- * the ref to the dentry for you.  Either way, you shouldn't use the ref you
- * passed in anymore.  Still, there are issues with refcnting with this.
+ * the *dentry you should use.  If this fails, it will return 0.  It will NOT
+ * take your dentry ref (it used to).  It probably will not be the same dentry
+ * you passed in.  This is ugly.
  *
  * Callers, make sure you alloc and fill out the name parts of the dentry, and
  * an initialized nameidata. TODO: not sure why we need an ND.  Don't use it in
@@ -328,8 +328,7 @@ struct dentry *kfs_lookup(struct inode *dir, struct dentry *dentry,
        TAILQ_FOREACH(d_i, &dir_dent->d_subdirs, d_subdirs_link) {
                if (!strcmp(d_i->d_name.name, dentry->d_name.name)) {
                        /* since this dentry is already in memory (that's how KFS works), we
-                        * can free the one that came in and return the real one */
-                       kref_put(&dentry->d_kref);
+                        * just return the real one (with another refcnt) */
                        kref_get(&d_i->d_kref, 1);
                        return d_i;
                }
@@ -337,16 +336,12 @@ struct dentry *kfs_lookup(struct inode *dir, struct dentry *dentry,
        TAILQ_FOREACH(d_i, &k_i_info->children, d_subdirs_link) {
                if (!strcmp(d_i->d_name.name, dentry->d_name.name)) {
                        /* since this dentry is already in memory (that's how KFS works), we
-                        * can free the one that came in and return the real one */
-                       kref_put(&dentry->d_kref);
+                        * just return the real one (with another refcnt) */
                        kref_get(&d_i->d_kref, 1);
                        return d_i;
                }
        }
-       /* no match, consider caching the negative result, freeing the
-        * dentry, etc */
        printd("Not Found %s!!\n", dentry->d_name.name);
-       kref_put(&dentry->d_kref);
        return 0;
 }
 
@@ -811,7 +806,8 @@ static int __add_kfs_entry(struct dentry *parent, char *path,
                       parent->d_name.name, c_bhdr->c_filestart, c_bhdr->c_filesize);
                /* Init the dentry for this path */
                dentry = get_dentry(parent->d_sb, parent, path);
-               dcache_put(dentry);                     /* TODO: should set a d_flag too */
+               // want to test the regular/natural dentry caching paths
+               //dcache_put(dentry->d_sb, dentry);
                /* build the inode */
                switch (c_bhdr->c_mode & CPIO_FILE_MASK) {
                        case (CPIO_DIRECTORY):
index 89ced88..e560a7c 100644 (file)
@@ -772,6 +772,7 @@ int mon_fs(int argc, char *NTS *NT COUNT(argc) argv, trapframe_t *tf)
                printk("Usage: fs OPTION\n");
                printk("\topen: show all open files\n");
                printk("\tinodes: show all inodes\n");
+               printk("\tdentries [LRU]: show all dentries (dcache), optional LRU\n");
                printk("\tls DIR: print the dir tree starting with DIR\n");
                printk("\tpid: proc PID's fs crap placeholder\n");
                return 1;
@@ -800,6 +801,30 @@ int mon_fs(int argc, char *NTS *NT COUNT(argc) argv, trapframe_t *tf)
                                               kref_refcnt(&dentry->d_kref));
                        }
                }
+       } else if (!strcmp(argv[1], "dentries")) {
+               printk("Dentry Cache:\n----------------------------\n");
+               TAILQ_FOREACH(sb, &super_blocks, s_list) {
+                       printk("Superblock for %s\n", sb->s_name);
+                       if (hashtable_count(sb->s_dcache)) {
+                               hashtable_itr_t *dcache_i = hashtable_iterator(sb->s_dcache);
+                               printk("DENTRY     FLAGS      REFCNT NAME\n");
+                               printk("--------------------------------\n");
+                               do {
+                                       struct dentry *d_i = hashtable_iterator_value(dcache_i);
+                                       printk("%08p %08p %02d     %s\n", d_i, d_i->d_flags,
+                                              kref_refcnt(&d_i->d_kref), d_i->d_name.name);
+                               } while (hashtable_iterator_advance(dcache_i));
+                       }
+               }
+               if (argv[2]) {
+                       printk("LRU lists:\n");
+                       TAILQ_FOREACH(sb, &super_blocks, s_list) {
+                               printk("Superblock for %s\n", sb->s_name);
+                               TAILQ_FOREACH(dentry, &sb->s_lru_d, d_lru)
+                                       printk("Dentry: %08p, Name: %s\n", dentry,
+                                              dentry->d_name.name);
+                       }
+               }
        } else if (!strcmp(argv[1], "ls")) {
                if (argc != 3) {
                        printk("Give me a dir.\n");
index 119ae65..96f9417 100644 (file)
@@ -21,9 +21,6 @@ struct sb_tailq super_blocks = TAILQ_HEAD_INITIALIZER(super_blocks);
 spinlock_t super_blocks_lock = SPINLOCK_INITIALIZER;
 struct fs_type_tailq file_systems = TAILQ_HEAD_INITIALIZER(file_systems);
 struct namespace default_ns;
-// TODO: temp dcache, holds all dentries ever for now
-struct dentry_slist dcache = SLIST_HEAD_INITIALIZER(dcache);
-spinlock_t dcache_lock = SPINLOCK_INITIALIZER;
 
 struct kmem_cache *dentry_kcache; // not to be confused with the dcache
 struct kmem_cache *inode_kcache;
@@ -131,22 +128,46 @@ char *file_name(struct file *file)
        return file->f_dentry->d_name.name;
 }
 
-/* Some issues with this, coupled closely to fs_lookup.  This assumes that
- * negative dentries are not returned (might differ from linux) */
+/* Some issues with this, coupled closely to fs_lookup.
+ *
+ * Note the use of __dentry_free, instead of kref_put.  In those cases, we don't
+ * want to treat it like a kref and we have the only reference to it, so it is
+ * okay to do this.  It makes dentry_release() easier too. */
 static struct dentry *do_lookup(struct dentry *parent, char *name)
 {
-       struct dentry *dentry;
-       /* TODO: look up in the dentry cache first */
-       dentry = get_dentry(parent->d_sb, parent, name);
-       dentry = parent->d_inode->i_op->lookup(parent->d_inode, dentry, 0);
-       /* insert in dentry cache */
+       struct dentry *result, *query;
+       query = get_dentry(parent->d_sb, parent, name);
+       result = dcache_get(parent->d_sb, query); 
+       if (result) {
+               __dentry_free(query);
+               return result;
+       }
+       /* No result, check for negative */
+       if (query->d_flags & DENTRY_NEGATIVE) {
+               __dentry_free(query);
+               return 0;
+       }
+       /* not in the dcache at all, need to consult the FS */
+       result = parent->d_inode->i_op->lookup(parent->d_inode, query, 0);
+       if (!result) {
+               query->d_flags |= DENTRY_NEGATIVE;
+               dcache_put(parent->d_sb, query);
+               kref_put(&query->d_kref);
+               return 0;
+       }
+       dcache_put(parent->d_sb, result);
+       /* This is because KFS doesn't return the same dentry, but ext2 does.  this
+        * is ugly and needs to be fixed. (TODO) */
+       if (result != query)
+               __dentry_free(query);
+
        /* TODO: if the following are done by us, how do we know the i_ino?
         * also need to handle inodes that are already read in!  For now, we're
         * going to have the FS handle it in it's lookup() method: 
         * - get a new inode
         * - read in the inode
         * - put in the inode cache */
-       return dentry;
+       return result;
 }
 
 /* Update ND such that it represents having followed dentry.  IAW the nd
@@ -488,6 +509,25 @@ out:
 
 /* Superblock functions */
 
+/* Dentry "hash" function for the hash table to use.  Since we already have the
+ * hash in the qstr, we don't need to rehash.  Also, note we'll be using the
+ * dentry in question as both the key and the value. */
+static size_t __dcache_hash(void *k)
+{
+       return (size_t)((struct dentry*)k)->d_name.hash;
+}
+
+/* Dentry cache hashtable equality function.  This means we need to pass in some
+ * minimal dentry when doing a lookup. */
+static ssize_t __dcache_eq(void *k1, void *k2)
+{
+       if (((struct dentry*)k1)->d_parent != ((struct dentry*)k2)->d_parent)
+               return 0;
+       /* TODO: use the FS-specific string comparison */
+       return !strcmp(((struct dentry*)k1)->d_name.name,
+                      ((struct dentry*)k2)->d_name.name);
+}
+
 /* Helper to alloc and initialize a generic superblock.  This handles all the
  * VFS related things, like lists.  Each FS will need to handle its own things
  * in it's *_get_sb(), usually involving reading off the disc. */
@@ -500,8 +540,13 @@ struct super_block *get_sb(void)
        TAILQ_INIT(&sb->s_inodes);
        TAILQ_INIT(&sb->s_dirty_i);
        TAILQ_INIT(&sb->s_io_wb);
-       SLIST_INIT(&sb->s_anon_d);
+       TAILQ_INIT(&sb->s_lru_d);
        TAILQ_INIT(&sb->s_files);
+       sb->s_dcache = create_hashtable(100, __dcache_hash, __dcache_eq);
+       sb->s_icache = create_hashtable(100, __generic_hash, __generic_eq);
+       spinlock_init(&sb->s_lru_lock);
+       spinlock_init(&sb->s_dcache_lock);
+       spinlock_init(&sb->s_icache_lock);
        sb->s_fs_info = 0; // can override somewhere else
        return sb;
 }
@@ -549,7 +594,7 @@ void init_sb(struct super_block *sb, struct vfsmount *vmnt,
        /* insert the dentry into the dentry cache.  when's the earliest we can?
         * when's the earliest we should?  what about concurrent accesses to the
         * same dentry?  should be locking the dentry... */
-       dcache_put(d_root); // TODO: should set a d_flag too
+       dcache_put(sb, d_root);
        kref_put(&inode->i_kref);               /* give up the ref from get_inode() */
 }
 
@@ -588,9 +633,8 @@ struct dentry *get_dentry(struct super_block *sb, struct dentry *parent,
                dentry->d_op = parent->d_op;    /* d_op set in init_sb for parentless */
        }
        dentry->d_parent = parent;
-       dentry->d_flags = 0;                            /* related to its dcache state */
+       dentry->d_flags = DENTRY_USED;
        dentry->d_fs_info = 0;
-       SLIST_INIT(&dentry->d_bucket);
        if (name_len < DNAME_INLINE_LEN) {
                strncpy(dentry->d_iname, name, name_len);
                dentry->d_iname[name_len] = '\0';
@@ -607,31 +651,56 @@ struct dentry *get_dentry(struct super_block *sb, struct dentry *parent,
        return dentry;
 }
 
-/* Adds a dentry to the dcache. */
-void dcache_put(struct dentry *dentry)
+/* Called when the dentry is unreferenced (after kref == 0).  This works closely
+ * with the resurrection in dcache_get().
+ *
+ * The dentry is still in the dcache, but needs to be un-USED and added to the
+ * LRU dentry list.  Even dentries that were used in a failed lookup need to be
+ * cached - they ought to be the negative dentries.  Note that all dentries have
+ * parents, even negative ones (it is needed to find it in the dcache). */
+void dentry_release(struct kref *kref)
 {
-#if 0 /* pending a more thorough review of the dcache */
-       /* TODO: should set a d_flag too */
-       spin_lock(&dcache_lock);
-       SLIST_INSERT_HEAD(&dcache, dentry, d_hash);
-       spin_unlock(&dcache_lock);
-#endif
+       struct dentry *dentry = container_of(kref, struct dentry, d_kref);
+
+       printd("'Releasing' dentry %08p: %s\n", dentry, dentry->d_name.name);
+       /* DYING dentries (recently unlinked / rmdir'd) just get freed */
+       if (dentry->d_flags & DENTRY_DYING) {
+               __dentry_free(dentry);
+               return;
+       }
+       /* This lock ensures the USED state and the TAILQ membership is in sync.
+        * Also used to check the refcnt, though that might not be necessary. */
+       spin_lock(&dentry->d_lock);
+       /* While locked, we need to double check the kref, in case someone already
+        * reup'd it.  Re-up? you're crazy!  Reee-up, you're outta yo mind! */
+       if (!kref_refcnt(&dentry->d_kref)) {
+               /* and make sure it wasn't USED, then UNUSED again */
+               /* TODO: think about issues with this */
+               if (dentry->d_flags & DENTRY_USED) {
+                       dentry->d_flags &= ~DENTRY_USED;
+                       spin_lock(&dentry->d_sb->s_lru_lock);
+                       TAILQ_INSERT_TAIL(&dentry->d_sb->s_lru_d, dentry, d_lru);
+                       spin_unlock(&dentry->d_sb->s_lru_lock);
+               } else {
+                       warn("This should be rare.  Tell brho this happened.");
+               }
+       }
+       spin_unlock(&dentry->d_lock);
 }
 
-/* Cleans up the dentry (after ref == 0).  We still may want it, and this is
- * where we should add it to the dentry cache.  (TODO).  For now, we do nothing,
- * since we don't have a dcache.  Also, if i_nlink == 0, never cache it.
- * 
+/* Called when we really dealloc and get rid of a dentry (like when it is
+ * removed from the dcache, either for memory or correctness reasons)
+ *
  * This has to handle two types of dentries: full ones (ones that had been used)
  * and ones that had been just for lookups - hence the check for d_inode.
  *
  * Note that dentries pin and kref their inodes.  When all the dentries are
  * gone, we want the inode to be released via kref.  The inode has internal /
  * weak references to the dentry, which are not refcounted. */
-void dentry_release(struct kref *kref)
+void __dentry_free(struct dentry *dentry)
 {
-       struct dentry *dentry = container_of(kref, struct dentry, d_kref);
-       printd("Freeing dentry %08p: %s\n", dentry, dentry->d_name.name);
+       if (dentry->d_inode)
+               printk("Freeing dentry %08p: %s\n", dentry, dentry->d_name.name);
        assert(dentry->d_op);   /* catch bugs.  a while back, some lacked d_op */
        dentry->d_op->d_release(dentry);
        /* TODO: check/test the boundaries on this. */
@@ -670,6 +739,93 @@ struct dentry *lookup_dentry(char *path, int flags)
        return dentry;
 }
 
+/* Get a dentry from the dcache.  At a minimum, we need the name hash and parent
+ * in what_i_want, though most uses will probably be from a get_dentry() call.
+ * We pass in the SB in the off chance that we don't want to use a get'd dentry.
+ *
+ * The unusual variable name (instead of just "key" or something) is named after
+ * ex-SPC Castro's porn folder.  Caller deals with the memory for what_i_want.
+ *
+ * If the dentry is negative, we don't return the actual result - instead, we
+ * set the negative flag in 'what i want'.  The reason is we don't want to
+ * kref_get() and then immediately put (causing dentry_release()).  This also
+ * means that dentry_release() should never get someone who wasn't USED (barring
+ * the race, which it handles).  And we don't need to ever have a dentry set as
+ * USED and NEGATIVE (which is always wrong, but would be needed for a cleaner
+ * dentry_release()).
+ *
+ * This is where we do the "kref resurrection" - we are returning a kref'd
+ * object, even if it wasn't kref'd before.  This means the dcache does NOT hold
+ * krefs (it is a weak/internal ref), but it is a source of kref generation.  We
+ * sync up with the possible freeing of the dentry by locking the table.  See
+ * Doc/kref for more info. */
+struct dentry *dcache_get(struct super_block *sb, struct dentry *what_i_want)
+{
+       struct dentry *found;
+       /* This lock protects the hash, as well as ensures the returned object
+        * doesn't get deleted/freed out from under us */
+       spin_lock(&sb->s_dcache_lock);
+       found = hashtable_search(sb->s_dcache, what_i_want);
+       if (found) {
+               if (found->d_flags & DENTRY_NEGATIVE) {
+                       what_i_want->d_flags |= DENTRY_NEGATIVE;
+                       spin_unlock(&sb->s_dcache_lock);
+                       return 0;
+               }
+               spin_lock(&found->d_lock);
+               __kref_get(&found->d_kref, 1);  /* prob could be done outside the lock*/
+               /* If we're here (after kreffing) and it is not USED, we are the one who
+                * should resurrect */
+               if (!(found->d_flags & DENTRY_USED)) {
+                       found->d_flags |= DENTRY_USED;
+                       spin_lock(&sb->s_lru_lock);
+                       TAILQ_REMOVE(&sb->s_lru_d, found, d_lru);
+                       spin_unlock(&sb->s_lru_lock);
+               }
+               spin_unlock(&found->d_lock);
+       }
+       spin_unlock(&sb->s_dcache_lock);
+       return found;
+}
+
+/* Adds a dentry to the dcache.  Note the *dentry is both the key and the value.
+ * If the value was already in there (which can happen iff it was negative), for
+ * now we'll remove it and put the new one in there. */
+void dcache_put(struct super_block *sb, struct dentry *key_val)
+{
+       struct dentry *old;
+       int retval;
+       spin_lock(&sb->s_dcache_lock);
+       old = hashtable_remove(sb->s_dcache, key_val);
+       if (old) {
+               assert(old->d_flags & DENTRY_NEGATIVE);
+               assert(!(old->d_flags & DENTRY_USED));
+               assert(!kref_refcnt(&old->d_kref));
+               spin_lock(&sb->s_lru_lock);
+               TAILQ_REMOVE(&sb->s_lru_d, old, d_lru);
+               spin_unlock(&sb->s_lru_lock);
+               __dentry_free(old);
+       }
+       /* this returns 0 on failure (TODO: Fix this ghetto shit) */
+       retval = hashtable_insert(sb->s_dcache, key_val, key_val);
+       assert(retval);
+       spin_unlock(&sb->s_dcache_lock);
+}
+
+/* Will remove and return the dentry.  Caller deallocs the key, but the retval
+ * won't have a reference.  * Returns 0 if it wasn't found.  Callers can't
+ * assume much - they should not use the reference they *get back*, (if they
+ * already had one for key, they can use that).  There may be other users out
+ * there. */
+struct dentry *dcache_remove(struct super_block *sb, struct dentry *key)
+{
+       struct dentry *retval;
+       spin_lock(&sb->s_dcache_lock);
+       retval = hashtable_remove(sb->s_dcache, key);
+       spin_unlock(&sb->s_dcache_lock);
+       return retval;
+}
+
 /* Inode Functions */
 
 /* Creates and initializes a new inode.  Generic fields are filled in.
@@ -1059,7 +1215,7 @@ struct file *do_file_open(char *path, int flags, int mode)
                 * but we apply it immediately. */
                if (create_file(parent_i, file_d, mode))        /* sets errno */
                        goto out_file_d;
-               dcache_put(file_d);
+               dcache_put(file_d->d_sb, file_d);
        } else {        /* something already exists */
                /* this can happen due to concurrent access, but needs to be thought
                 * through */
@@ -1117,7 +1273,7 @@ int do_symlink(char *path, const char *symname, int mode)
        parent_i = nd->dentry->d_inode;
        if (create_symlink(parent_i, sym_d, symname, mode))
                goto out_sym_d;
-       dcache_put(sym_d);
+       dcache_put(sym_d->d_sb, sym_d);
        retval = 0;                             /* Note the fall through to the exit paths */
 out_sym_d:
        kref_put(&sym_d->d_kref);
@@ -1183,7 +1339,7 @@ int do_link(char *old_path, char *new_path)
        link_d->d_inode = inode;
        inode->i_nlink++;
        TAILQ_INSERT_TAIL(&inode->i_dentry, link_d, d_alias);   /* weak ref */
-       dcache_put(link_d);
+       dcache_put(link_d->d_sb, link_d);
        retval = 0;                             /* Note the fall through to the exit paths */
 out_both_ds:
        kref_put(&old_d->d_kref);
@@ -1228,9 +1384,11 @@ int do_unlink(char *path)
                set_errno(-error);
                goto out_dentry;
        }
-       /* TODO: rip dentry from the inode cache */
-       kref_put(&dentry->d_parent->d_kref);
-       dentry->d_parent = 0;           /* so we don't double-decref it later */
+       /* Now that our parent doesn't track us, we need to make sure we aren't
+        * findable via the dentry cache.  DYING, so we will be freed in
+        * dentry_release() */
+       dentry->d_flags |= DENTRY_DYING;
+       dcache_remove(dentry->d_sb, dentry);
        dentry->d_inode->i_nlink--;     /* TODO: race here, esp with a decref */
        /* At this point, the dentry is unlinked from the FS, and the inode has one
         * less link.  When the in-memory objects (dentry, inode) are going to be
@@ -1307,7 +1465,7 @@ int do_mkdir(char *path, int mode)
        parent_i = nd->dentry->d_inode;
        if (create_dir(parent_i, dentry, mode))
                goto out_dentry;
-       dcache_put(dentry);
+       dcache_put(dentry->d_sb, dentry);
        retval = 0;                             /* Note the fall through to the exit paths */
 out_dentry:
        kref_put(&dentry->d_kref);
@@ -1352,6 +1510,11 @@ int do_rmdir(char *path)
                set_errno(-error);
                goto out_dentry;
        }
+       /* Now that our parent doesn't track us, we need to make sure we aren't
+        * findable via the dentry cache.  DYING, so we will be freed in
+        * dentry_release() */
+       dentry->d_flags |= DENTRY_DYING;
+       dcache_remove(dentry->d_sb, dentry);
        /* Decref ourselves, so inode_release() knows we are done */
        dentry->d_inode->i_nlink--;
        TAILQ_REMOVE(&nd->dentry->d_subdirs, dentry, d_subdirs_link);