patch-2.1.45 linux/fs/dcache.c

Next file: linux/fs/devices.c
Previous file: linux/fs/buffer.c
Back to the patch index
Back to the overall index

diff -u --recursive --new-file v2.1.44/linux/fs/dcache.c linux/fs/dcache.c
@@ -16,25 +16,8 @@
 #include <linux/string.h>
 #include <linux/mm.h>
 #include <linux/fs.h>
-#include <linux/dalloc.h>
-#include <linux/dlists.h>
 #include <linux/malloc.h>
 
-/* this should be removed after the beta phase */
-/*#define DEBUG*/
-/*#undef DEBUG*/
-/*#define DEBUG_DDIR_COUNT*/
-
-void printpath(struct dentry * entry);
-
-DEF_INSERT(alias,struct dentry,d_next,d_prev)
-DEF_REMOVE(alias,struct dentry,d_next,d_prev)
-
-DEF_INSERT(hash,struct dentry,d_hash_next,d_hash_prev)
-DEF_REMOVE(hash,struct dentry,d_hash_next,d_hash_prev)
-
-struct dentry * the_root = NULL;
-
 /*
  * This is the single most critical data structure when it comes
  * to the dcache: the hashtable for lookups. Somebody should try
@@ -46,286 +29,255 @@
 #define D_HASHBITS     10
 #define D_HASHSIZE     (1UL << D_HASHBITS)
 #define D_HASHMASK     (D_HASHSIZE-1)
-struct dentry * dentry_hashtable[D_HASHSIZE];
-
-static inline unsigned long dentry_hash(struct dentry *dir, int name_hash)
-{
-	unsigned long hash = name_hash + (unsigned long) dir;
-	hash = hash ^ (hash >> D_HASHBITS) ^ (hash >> D_HASHBITS*2);
-	return hash & D_HASHMASK;
-}
-
-unsigned long name_cache_init(unsigned long mem_start, unsigned long mem_end)
-{
-	return mem_start;
-}
-
-#ifdef DEBUG
-/* throw this away after the beta phase */
-/*************************************************************************/
-extern void xcheck(char * txt, struct inode * p);
-
-static int x_alloc = 0;
-static int x_freed = 0;
-static int x_free = 0;
 
-static void * tst[20000];
-static int cnt = 0;
+static struct list_head dentry_hashtable[D_HASHSIZE];
+static LIST_HEAD(dentry_unused);
 
-static void ins(void* ptr)
+void d_free(struct dentry *dentry)
 {
-	extern int inodes_stat;
-	tst[cnt++] = ptr;
-        if(cnt % 1000 == 0)
-		printk("------%d allocated: %d: %d %d %d\n", inodes_stat, cnt,
-		       x_alloc, x_freed, x_free);
-	if (cnt>=20000) panic("stop");
+	kfree(dentry->d_name.name);
+	kfree(dentry);
 }
 
-#if 0
-static inline int search(void* ptr)
+/*
+ * dput()
+ *
+ * This is complicated by the fact that we do not want to put
+ * dentries that are no longer on any hash chain on the unused
+ * list: we'd much rather just get rid of them immediately.
+ *
+ * However, that implies that we have to traverse the dentry
+ * tree upwards to the parents which might _also_ now be
+ * scheduled for deletion (it may have been only waiting for
+ * its last child to go away).
+ *
+ * This tail recursion is done by hand as we don't want to depend
+ * on the compiler to always get this right (gcc generally doesn't).
+ * Real recursion would eat up our stack space.
+ */
+void dput(struct dentry *dentry)
 {
-	int i;
-	for(i = cnt-1; i>=0; i--)
-		if (tst[i] == ptr)
-			return i;
-	return -1;
-}
-
-#define TST(n,x) if(search(x)<0) printk("%s bad ptr %p line %d\n", n, x, __LINE__)
-#else
-#define TST(n,x) /*nothing*/
-#endif
-
-void LOG(char * txt, struct dentry * entry)
-{
-	static int count = 0;
-	if (entry) {
-		TST(txt,entry);
-	}
-	if (count) {
-		count--;
-		printk("%s: entry=%p\n", txt, entry);
+	if (dentry) {
+		int count;
+repeat:
+		count = dentry->d_count-1;
+		if (count < 0) {
+			printk("Negative d_count (%d) for %s/%s\n",
+				count,
+				dentry->d_parent->d_name.name,
+				dentry->d_name.name);
+			*(int *)0 = 0;
+		}
+		dentry->d_count = count;
+		if (!count) {
+			list_del(&dentry->d_lru);
+			if (list_empty(&dentry->d_hash)) {
+				struct inode *inode = dentry->d_inode;
+				struct dentry * parent;
+				if (inode) {
+					list_del(&dentry->d_alias);
+					iput(inode);
+				}
+				parent = dentry->d_parent;
+				d_free(dentry);
+				if (dentry == parent)
+					return;
+				dentry = parent;
+				goto repeat;
+			}
+			list_add(&dentry->d_lru, &dentry_unused);
+		}
 	}
 }
 
-#ifdef DEBUG_DDIR_COUNT
-void recursive_test(struct dentry * entry)
-{
-}
-#else
-#define recursive_test(e) /*nothing*/
-#endif
-#else
-#define TST(n,x) /*nothing*/
-#define LOG(n,x) /*nothing*/
-#define xcheck(t,i) /*nothing*/
-#define recursive_test(e) /*nothing*/
-/*****************************************************************************/
-#endif
-
-void printpath(struct dentry * entry)
-{
-	if (!IS_ROOT(entry))
-		printpath(entry->d_parent);
-	printk("/%s", entry->d_name.name);
-}
-
-void d_free(struct dentry *dentry)
+/*
+ * Shrink the dcache. This is done when we need
+ * more memory, or simply when we need to unmount
+ * something (at which point we need to unuse
+ * all dentries).
+ */
+void shrink_dcache(void)
 {
-	if (dentry) {
-		kfree(dentry->d_name.name);
-		kfree(dentry);
+	for (;;) {
+		struct dentry *dentry;
+		struct list_head *tmp = dentry_unused.prev;
+
+		if (tmp == &dentry_unused)
+			break;
+		list_del(tmp);
+		INIT_LIST_HEAD(tmp);
+		dentry = list_entry(tmp, struct dentry, d_lru);
+		if (!dentry->d_count) {
+			struct dentry * parent;
+
+			list_del(&dentry->d_hash);
+			if (dentry->d_inode) {
+				struct inode * inode = dentry->d_inode;
+
+				list_del(&dentry->d_alias);
+				dentry->d_inode = NULL;
+				iput(inode);
+			}
+			parent = dentry->d_parent;
+			d_free(dentry);
+			dput(parent);
+		}
 	}
 }
 
 #define NAME_ALLOC_LEN(len)	((len+16) & ~15)
 
-struct dentry * d_alloc(struct dentry * parent, struct qstr *name, int isdir)
+struct dentry * d_alloc(struct dentry * parent, const struct qstr *name)
 {
-	char *str;
-	struct dentry *res;
+	char * str;
+	struct dentry *dentry;
 
-	res = kmalloc(sizeof(struct dentry), GFP_KERNEL);
-	if (!res)
+	dentry = kmalloc(sizeof(struct dentry), GFP_KERNEL);
+	if (!dentry)
 		return NULL;
 
 	str = kmalloc(NAME_ALLOC_LEN(name->len), GFP_KERNEL);
 	if (!str) {
-		kfree(res);
+		kfree(dentry);
 		return NULL;
 	}
-	
+
 	memcpy(str, name->name, name->len);
 	str[name->len] = 0;
 
-	memset(res, 0, sizeof(struct dentry));
-
-	res->d_parent = parent;
-	res->d_mounts = res;
-	res->d_covers = res;
-	res->d_flag = isdir ? D_DIR : 0;
-
-	res->d_name.name = str;
-	res->d_name.len = name->len;
-	res->d_name.hash = name->hash;
-
-#ifdef DEBUG
-	x_alloc++;
-#endif
-	return res;
+	dentry->d_count = 0;
+	dentry->d_flags = 0;
+	dentry->d_inode = NULL;
+	dentry->d_parent = parent;
+	dentry->d_mounts = dentry;
+	dentry->d_covers = dentry;
+	INIT_LIST_HEAD(&dentry->d_hash);
+	INIT_LIST_HEAD(&dentry->d_alias);
+	INIT_LIST_HEAD(&dentry->d_lru);
+
+	dentry->d_name.name = str;
+	dentry->d_name.len = name->len;
+	dentry->d_name.hash = name->hash;
+	dentry->d_revalidate = NULL;
+	return dentry;
 }
 
-extern blocking struct dentry * d_alloc_root(struct inode * root_inode, struct dentry *old_root)
+/*
+ * Fill in inode information in the entry.
+ *
+ * This turns negative dentries into productive full members
+ * of society.
+ *
+ * NOTE! This assumes that the inode count has been incremented
+ * (or otherwise set) by the caller to indicate that it is now
+ * in use by the dcache..
+ */
+void d_instantiate(struct dentry *entry, struct inode * inode)
 {
-	struct dentry *res;
-	struct qstr name = { "/", 1, 0 };	/* dummy qstr */
+	if (inode)
+		list_add(&entry->d_alias, &inode->i_dentry);
 
-	if (!root_inode)
-		return NULL;
-	res = d_alloc(NULL, &name, 1);
-	LOG("d_alloc_root", res);
-	res->d_parent = res;
-	d_instantiate(res, root_inode, D_DIR);
-	return res;
+	entry->d_inode = inode;
 }
 
-static inline struct dentry ** d_base_qstr(struct dentry * parent, struct qstr * s)
+struct dentry * d_alloc_root(struct inode * root_inode, struct dentry *old_root)
 {
-	return dentry_hashtable + dentry_hash(parent, s->hash);
-}
+	struct dentry *res = NULL;
 
-static inline struct dentry ** d_base_entry(struct dentry * pdir, struct dentry * entry)
-{
-	return d_base_qstr(pdir, &entry->d_name);
+	if (root_inode) {
+		res = d_alloc(NULL, &(const struct qstr) { "/", 1, 0 });
+		res->d_parent = res;
+		res->d_count = 1;
+		d_instantiate(res, root_inode);
+	}
+	return res;
 }
 
-
-static /*inline*/ blocking void _d_remove_from_parent(struct dentry * entry,
-						      struct dentry * parent)
+static inline struct list_head * d_hash(struct dentry * parent, unsigned long hash)
 {
-	if (entry->d_flag & D_HASHED) {
-		struct dentry ** base = d_base_entry(parent, entry);
-
-		remove_hash(base, entry);
-		entry->d_flag &= ~D_HASHED;
-	}
+	hash += (unsigned long) parent;
+	hash = hash ^ (hash >> D_HASHBITS) ^ (hash >> D_HASHBITS*2);
+	return dentry_hashtable + (hash & D_HASHMASK);
 }
 
-static inline struct dentry * __dlookup(struct dentry * base, struct dentry * parent, struct qstr * name)
+static inline struct dentry * __dlookup(struct list_head *head, struct dentry * parent, struct qstr * name)
 {
-	if (base) {
-		struct dentry * tmp = base;
-		int len = name->len;
-		int hash = name->hash;
-		const unsigned char *str = name->name;
-
-		do {
-			if (tmp->d_name.hash == hash		&&
-			    tmp->d_name.len == len		&&
-			    tmp->d_parent == parent		&&
-			   !(tmp->d_flag & D_DUPLICATE)		&&
-			   !memcmp(tmp->d_name.name, str, len))
-				return tmp;
-			tmp = tmp->d_hash_next;
-		} while(tmp != base);
+	struct list_head *tmp = head->next;
+	int len = name->len;
+	int hash = name->hash;
+	const unsigned char *str = name->name;
+
+	while (tmp != head) {
+		struct dentry * dentry = list_entry(tmp, struct dentry, d_hash);
+
+		tmp = tmp->next;
+		if (dentry->d_name.hash != hash)
+			continue;
+		if (dentry->d_name.len != len)
+			continue;
+		if (dentry->d_parent != parent)
+			continue;
+		if (memcmp(dentry->d_name.name, str, len))
+			continue;
+		return dentry;
 	}
 	return NULL;
 }
 
 struct dentry * d_lookup(struct dentry * dir, struct qstr * name)
 {
-	struct dentry ** base = d_base_qstr(dir, name);
-
-	return __dlookup(*base, dir, name);
+	return __dlookup(d_hash(dir, name->hash), dir, name);
 }
 
-static /*inline*/ blocking void _d_insert_to_parent(struct dentry * entry,
-						    struct dentry * parent,
-						    struct inode * inode,
-						    int flags)
+static inline void d_insert_to_parent(struct dentry * entry, struct dentry * parent)
 {
-	struct dentry ** base;
-
-	base = d_base_qstr(parent, &entry->d_name);
-	if (entry->d_flag & D_HASHED) {
-		printk("VFS: dcache entry is already hashed\n");
-		return;
-	}
-	insert_hash(base, entry);
-	entry->d_flag |= D_HASHED;
+	list_add(&entry->d_hash, d_hash(dget(parent), entry->d_name.hash));
 }
 
-/*
- * Fill in inode information in the entry.
- *
- * This turns negative dentries into productive full members
- * of society.
- *
- * NOTE! This assumes that the inode count has been incremented
- * (or otherwise set) by the caller to indicate that it is now
- * in use by the dcache..
- */
-void d_instantiate(struct dentry *entry, struct inode * inode, int flags)
+static inline void d_remove_from_parent(struct dentry * dentry, struct dentry * parent)
 {
-	entry->d_flag = (entry->d_flag & ~D_NEGATIVE) | flags;
-
-	if (inode && !(flags & D_NEGATIVE)) {
-		if (entry->d_flag & D_DIR) {
-			if (inode->i_dentry) {
-				printk("VFS: creating dcache directory alias\n");
-				return;
-			}
-		}
-		insert_alias(&inode->i_dentry, entry);
-	}
-
-	entry->d_inode = inode;
+	list_del(&dentry->d_hash);
+	dput(parent);
 }
 
+
 /*
- * Remove the inode from the dentry.. This removes
- * it from the parent hashes but otherwise leaves it
- * around - it may be a "zombie", part of a path
- * that is still in use...
+ * When a file is deleted, we have two options:
+ * - turn this dentry into a negative dentry
+ * - unhash this dentry and free it.
  *
- * "The Night of the Living Dead IV - the Dentry"
+ * Usually, we want to just turn this into
+ * a negative dentry, but if anybody else is
+ * currently using the dentry or the inode
+ * we can't do that and we fall back on removing
+ * it from the hash queues and waiting for
+ * it to be deleted later when it has no users
  */
 void d_delete(struct dentry * dentry)
 {
-	struct inode * inode = dentry->d_inode;
+	/*
+	 * Are we the only user?
+	 */
+	if (dentry->d_count == 1) {
+		struct inode * inode = dentry->d_inode;
 
-	_d_remove_from_parent(dentry, dentry->d_parent);
-	if (inode) {
-		remove_alias(&inode->i_dentry, dentry);
 		dentry->d_inode = NULL;
+		list_del(&dentry->d_alias);
 		iput(inode);
+		return;
 	}
+
+	/*
+	 * If not, just drop the dentry and let dput
+	 * pick up the tab..
+	 */
+	d_drop(dentry);
 }
 
-blocking void d_add(struct dentry * entry, struct inode * inode, int flags)
+void d_add(struct dentry * entry, struct inode * inode)
 {
-	struct dentry * parent = entry->d_parent;
-
-#ifdef DEBUG
-	if (inode)
-		xcheck("d_add", inode);
-	if (IS_ROOT(entry)) {
-		printk("VFS: d_add for root dentry ");
-		printpath(entry);
-		printk(" -> ");
-		printk("\n");
-		return;
-	}
-	if (!parent)
-		panic("d_add with parent==NULL");
-	LOG("d_add", entry);
-#endif
-        if(entry->d_flag & D_HASHED)
-		printk("VFS: d_add of already added dcache entry\n");
-
-	_d_insert_to_parent(entry, parent, inode, flags);
-	d_instantiate(entry, inode, flags);
+	d_insert_to_parent(entry, entry->d_parent);
+	d_instantiate(entry, inode);
 }
 
 static inline void alloc_new_name(struct dentry * entry, struct qstr *newname)
@@ -347,47 +299,18 @@
 	entry->d_name.hash = hash;
 }
 
-static inline void d_remove_old_parent(struct dentry * entry)
+void d_move(struct dentry * dentry, struct dentry * newdir, struct qstr * newname)
 {
-	struct dentry * parent;
-	struct inode * inode;
-
-	parent = entry->d_parent;
-	inode = entry->d_inode;
-	_d_remove_from_parent(entry, parent);
-}
-
-static inline void d_add_new_parent(struct dentry * entry, struct dentry * parent)
-{
-	struct inode * inode;
-
-	entry->d_parent = parent;
-	inode = entry->d_inode;
-
-	_d_insert_to_parent(entry, parent, inode, entry->d_flag);
-}
-
-
-blocking void d_move(struct dentry * entry, struct dentry * newdir, struct qstr * newname)
-{
-	struct inode * inode;
-	int flags;
-
-	if (!entry)
+	if (!dentry)
 		return;
-	inode = entry->d_inode;
-	flags = entry->d_flag;
-	if (!inode) {
-		printk("VFS: moving negative dcache entry\n");
-	}
 
-	if (flags & D_ZOMBIE) {
-		printk("VFS: moving zombie entry\n");
-	}
+	if (!dentry->d_inode)
+		printk("VFS: moving negative dcache entry\n");
 
-	d_remove_old_parent(entry);
-	alloc_new_name(entry, newname);
-	d_add_new_parent(entry, newdir);
+	d_remove_from_parent(dentry, dentry->d_parent);
+	alloc_new_name(dentry, newname);
+	dentry->d_parent = newdir;
+	d_insert_to_parent(dentry, newdir);
 }
 
 int d_path(struct dentry * entry, struct dentry * chroot, char * buf)
@@ -406,4 +329,17 @@
 		memcpy(buf, entry->d_name.name, entry->d_name.len);
 		return len + entry->d_name.len;
 	}
+}
+
+void dcache_init(void)
+{
+	int i;
+	struct list_head *d = dentry_hashtable;
+
+	i = D_HASHSIZE;
+	do {
+		INIT_LIST_HEAD(d);
+		d++;
+		i--;
+	} while (i);
 }
FUNET's LINUX-ADM group, linux-adm@nic.funet.fi
TCL-scripts by Sam Shen, slshen@lbl.gov