patch-2.2.14 linux/fs/dcache.c

• Lines: 317
• Date: Tue Jan 4 10:12:23 2000
• Orig file: v2.2.13/linux/fs/dcache.c
• Orig date: Sun Apr 25 23:17:56 1999

diff -u --recursive --new-file v2.2.13/linux/fs/dcache.c linux/fs/dcache.c
@@ -22,6 +22,7 @@
 #include <linux/init.h>
 
 #include <asm/uaccess.h>
+#include <asm/cache.h>
 
 #define DCACHE_PARANOIA 1
 /* #define DCACHE_DEBUG 1 */
@@ -41,11 +42,12 @@
  * This hash-function tries to avoid losing too many bits of hash
  * information, yet avoid using a prime hash-size or similar.
  */
-#define D_HASHBITS     10
-#define D_HASHSIZE     (1UL << D_HASHBITS)
-#define D_HASHMASK     (D_HASHSIZE-1)
+#define D_HASHBITS     d_hash_shift
+#define D_HASHMASK     d_hash_mask
 
-static struct list_head dentry_hashtable[D_HASHSIZE];
+static unsigned int d_hash_mask;
+static unsigned int d_hash_shift;
+static struct list_head *dentry_hashtable;
 static LIST_HEAD(dentry_unused);
 
 struct {
@@ -69,18 +71,23 @@
  * Release the dentry's inode, using the fileystem
  * d_iput() operation if defined.
  */
-static inline void dentry_iput(struct dentry * dentry)
+static inline int dentry_iput(struct dentry * dentry)
 {
 	struct inode *inode = dentry->d_inode;
+	int ret = 0;
+
 	if (inode) {
 		dentry->d_inode = NULL;
 		list_del(&dentry->d_alias);
 		INIT_LIST_HEAD(&dentry->d_alias);
+		ret = inode->i_count == 1;
 		if (dentry->d_op && dentry->d_op->d_iput)
 			dentry->d_op->d_iput(dentry, inode);
 		else
 			iput(inode);
 	}
+
+	return ret;
 }
 
 /*
@@ -168,6 +175,11 @@
 int d_invalidate(struct dentry * dentry)
 {
 	/*
+	 * If it's already been dropped, return OK.
+	 */
+	if (list_empty(&dentry->d_hash))
+		return 0;
+	/*
 	 * Check whether to do a partial shrink_dcache
 	 * to get rid of unused child entries.
 	 */
@@ -195,86 +207,24 @@
 }
 
 /*
- * Select less valuable dentries to be pruned when we need
- * inodes or memory. The selected dentries are moved to the
- * old end of the list where prune_dcache() can find them.
- * 
- * Negative dentries are included in the selection so that
- * they don't accumulate at the end of the list. The count
- * returned is the total number of dentries selected, which
- * may be much larger than the requested number of inodes.
- */
-int select_dcache(int inode_count, int page_count)
-{
-	struct list_head *next, *tail = &dentry_unused;
-	int found = 0;
-	int depth = dentry_stat.nr_unused >> 1;
-	unsigned long max_value = 4;
-
-	if (page_count)
-		max_value = -1;
-
-	next = tail->prev;
-	while (next != &dentry_unused && depth--) {
-		struct list_head *tmp = next;
-		struct dentry *dentry = list_entry(tmp, struct dentry, d_lru);
-		struct inode *inode = dentry->d_inode;
-		unsigned long value = 0;	
-
-		next = tmp->prev;
-		if (dentry->d_count) {
-			dentry_stat.nr_unused--;
-			list_del(tmp);
-			INIT_LIST_HEAD(tmp);
-			continue;
-		}
-
-		/*
-		 * Select dentries based on the page cache count ...
-		 * should factor in number of uses as well. We take
-		 * all negative dentries so that they don't accumulate.
-		 * (We skip inodes that aren't immediately available.)
-		 */
-		if (inode) {
-			value = inode->i_nrpages;	
-			if (value >= max_value)
-				continue;
-			if (inode->i_state || inode->i_count > 1)
-				continue;
-		}
-
-		/*
-		 * Move the selected dentries behind the tail.
-		 */
-		if (tmp != tail->prev) {
-			list_del(tmp);
-			list_add(tmp, tail->prev);
-		}
-		tail = tmp;
-		found++;
-		if (inode && --inode_count <= 0)
-			break;
-		if (page_count && (page_count -= value) <= 0)
-			break;
-	}
-	return found;
-}
-
-/*
  * Throw away a dentry - free the inode, dput the parent.
  * This requires that the LRU list has already been
  * removed.
  */
-static inline void prune_one_dentry(struct dentry * dentry)
+static inline int prune_one_dentry(struct dentry * dentry)
 {
 	struct dentry * parent;
+	int ret;
 
 	list_del(&dentry->d_hash);
 	list_del(&dentry->d_child);
-	dentry_iput(dentry);
+	ret = dentry_iput(dentry);
 	parent = dentry->d_parent;
 	d_free(dentry);
-	dput(parent);
+	if (parent != dentry)
+		dput(parent);
+
+	return ret;
 }
 
 /*
@@ -282,9 +232,21 @@
  * more memory, or simply when we need to unmount
  * something (at which point we need to unuse
  * all dentries).
+ *
+ * If you don't want a limit on the number of
+ * inodes that will be released then call
+ * with i_nr = -1.
+ *
+ * If you don't want a limit on the number of
+ * dentries that will be released then call
+ * with d_nr = 0.
+ *
+ * Returns the number of inodes released.
  */
-void prune_dcache(int count)
+int prune_dcache(int d_nr, int i_nr)
 {
+	int __i_nr = i_nr;
+
 	for (;;) {
 		struct dentry *dentry;
 		struct list_head *tmp = dentry_unused.prev;
@@ -296,11 +258,15 @@
 		INIT_LIST_HEAD(tmp);
 		dentry = list_entry(tmp, struct dentry, d_lru);
 		if (!dentry->d_count) {
-			prune_one_dentry(dentry);
-			if (!--count)
+			i_nr -= prune_one_dentry(dentry);
+			if (!i_nr)
+				break;
+			if (!--d_nr)
 				break;
 		}
 	}
+
+	return __i_nr - i_nr;
 }
 
 /*
@@ -396,6 +362,43 @@
 }
 
 /*
+ * Search for at least 1 mount point in the dentry's subdirs.
+ * We descend to the next level whenever the d_subdirs
+ * list is non-empty and continue searching.
+ */
+int have_submounts(struct dentry *parent)
+{
+	struct dentry *this_parent = parent;
+	struct list_head *next;
+
+	if (parent->d_mounts != parent)
+		return 1;
+repeat:
+	next = this_parent->d_subdirs.next;
+resume:
+	while (next != &this_parent->d_subdirs) {
+		struct list_head *tmp = next;
+		struct dentry *dentry = list_entry(tmp, struct dentry, d_child);		next = tmp->next;
+		/* Have we found a mount point ? */
+		if (dentry->d_mounts != dentry)
+			return 1;
+		if (!list_empty(&dentry->d_subdirs)) {
+			this_parent = dentry;
+			goto repeat;
+		}
+	}
+	/*
+	 * All done at this level ... ascend and resume the search.
+	 */
+	if (this_parent != parent) {
+		next = this_parent->d_child.next;
+		this_parent = this_parent->d_parent;
+		goto resume;
+	}
+	return 0; /* No mount points found in tree */
+}
+
+/*
  * Search the dentry child list for the specified parent,
  * and move any unused dentries to the end of the unused
  * list for prune_dcache(). We descend to the next level
@@ -455,7 +458,7 @@
 	int found;
 
 	while ((found = select_parent(parent)) != 0)
-		prune_dcache(found);
+		prune_dcache(found, -1);
 }
 
 /*
@@ -475,7 +478,7 @@
 		int count = 0;
 		if (priority)
 			count = dentry_stat.nr_unused / priority;
-		prune_dcache(count);
+		prune_dcache(count, -1);
 	}
 }
 
@@ -563,7 +566,7 @@
 
 static inline struct list_head * d_hash(struct dentry * parent, unsigned long hash)
 {
-	hash += (unsigned long) parent;
+	hash += (unsigned long) parent / L1_CACHE_BYTES;
 	hash = hash ^ (hash >> D_HASHBITS) ^ (hash >> D_HASHBITS*2);
 	return dentry_hashtable + (hash & D_HASHMASK);
 }
@@ -902,8 +905,10 @@
 
 void __init dcache_init(void)
 {
-	int i;
-	struct list_head *d = dentry_hashtable;
+	int i, order;
+	struct list_head *d;
+	unsigned int nr_hash;
+	unsigned long memory_size;
 
 	/* 
 	 * A constructor could be added for stable state like the lists,
@@ -921,7 +926,34 @@
 	if (!dentry_cache)
 		panic("Cannot create dentry cache");
 
-	i = D_HASHSIZE;
+	memory_size = num_physpages << PAGE_SHIFT;
+	memory_size >>= 13;
+	memory_size *= 2 * sizeof(void *);
+	for (order = 0; ((1UL << order) << PAGE_SHIFT) < memory_size; order++);
+
+	do {
+		unsigned long tmp;
+
+		nr_hash = (1UL << order) * PAGE_SIZE /
+			sizeof(struct list_head);
+		d_hash_mask = (nr_hash - 1);
+
+		tmp = nr_hash;
+		d_hash_shift = 0;
+		while((tmp >>= 1UL) != 0UL)
+			d_hash_shift++;
+
+		dentry_hashtable = (struct list_head *)
+			__get_free_pages(GFP_ATOMIC, order);
+	} while(dentry_hashtable == NULL && --order >= 0);
+	printk("Dentry hash table entries: %d (order %d, %ldk)\n",
+	       nr_hash, order, (1UL<<order) * PAGE_SIZE / 1024);
+
+	if (!dentry_hashtable)
+		panic("Failed to allocate dcache hash table\n");
+
+	d = dentry_hashtable;
+	i = nr_hash;
 	do {
 		INIT_LIST_HEAD(d);
 		d++;