lkml.org 
[lkml]   [1997]   [Nov]   [1]   [last100]   RSS Feed
Views: [more markup]  [less markup]  [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
DateSat, 01 Nov 1997 15:30:37 -0500
FromBill Hawes <>
Subjectupdated dcache/inode management for 2.1.61
I've made some further refinements to the dcache and inode management
code, mostly to limit the accumulation of excessive negative dentries.
The code now uses an explicit time stamp rather than relying on inode
atime, as I need to determine times for all dentries.

I've included some comparative tests against 2.0.31 in the table below. 
In general the results are comparable -- 2.0.31 is a little faster on
repeats of greps, but has trouble switching to a different source tree.

Note particularly that 2.1.61 is much faster for cases where all of the
inodes are in memory (e.g. 2nd rep of file find, 3rd rep of man pages). 
This shows the potential speed improvements made possible by the dentry
layer.

Operation		2.1.61		2.0.31
Grep 2.1.60 sources	24.81		24.85
			07.75		06.81
			05.15		03.29

File find X11R6		04.58		06.67
			00.22		01.39

File find 2.1.59	06.16		09.01
			00.44		02.08

Grep 2.1.60 again	15.73		05.29
			07.87		02.89
			04.93		02.81

Grep 2.1.59		24.36		25.25
			14.55		18.28
			08.03		15.84

Grep /usr/man		09.93		09.58
			03.75		01.49
			00.68		01.24

Also note that the much-maligned "d_alloc pruning dcache" message is now
disabled.

Regards,
Bill--- linux-2.1.61/include/linux/dcache.h.old	Fri Oct 31 00:26:08 1997
+++ linux-2.1.61/include/linux/dcache.h	Fri Oct 31 10:55:58 1997
@@ -61,6 +61,7 @@
 	unsigned long d_time;		/* used by d_revalidate */
 	struct dentry_operations  *d_op;
 	struct super_block * d_sb;	/* The root of the dentry tree */
+	unsigned long d_reftime;	/* last time referenced */
 };
 
 struct dentry_operations {
--- linux-2.1.61/fs/dcache.c.old	Fri Oct 31 00:26:07 1997
+++ linux-2.1.61/fs/dcache.c	Sat Nov  1 15:11:45 1997
@@ -97,9 +97,10 @@
 			goto out;
 	}
 
-	if (!list_empty(&dentry->d_lru))
+	if (!list_empty(&dentry->d_lru)) {
 		dentry_stat.nr_unused--;
-	list_del(&dentry->d_lru);
+		list_del(&dentry->d_lru);
+	}
 	if (list_empty(&dentry->d_hash)) {
 		struct inode *inode = dentry->d_inode;
 		struct dentry * parent;
@@ -116,6 +117,11 @@
 	}
 	list_add(&dentry->d_lru, &dentry_unused);
 	dentry_stat.nr_unused++;
+	/*
+	 * Update the timestamp
+	 */
+	dentry->d_reftime = jiffies;
+
 out:
 	if (count >= 0) {
 		dentry->d_count = count;
@@ -150,27 +156,31 @@
 }
 
 /*
- * Selects 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.
+ * 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 count, int page_count)
+int select_dcache(int inode_count, int page_count)
 {
-	struct list_head *tail = &dentry_unused;
-	struct list_head *next = dentry_unused.prev;
-	int forward = 0, young = 0, depth = dentry_stat.nr_unused >> 1;
-	int found = 0, pages = 0;
+	struct list_head *next, *tail = &dentry_unused;
+	int found = 0, forward = 0, young = 8;
+	int depth = dentry_stat.nr_unused >> 1;
+	unsigned long min_value = 0, max_value = 4;
 
-#ifdef DCACHE_DEBUG
-printk("select_dcache: %d unused, count=%d, pages=%d\n",
-dentry_stat.nr_unused, count, page_count);
-#endif
+	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;
+		unsigned long value = 0;	
 
 		next = tmp->prev;
 		if (forward)
@@ -182,56 +192,57 @@
 			continue;
 		}
 		/*
-		 * Select dentries based on the page cache count ...
-		 * should factor in number of uses as well.
-		 */
-		if (inode) {
-			if (inode->i_state)
-				continue;
-			value = inode->i_nrpages;	
-		}
-		/*
-		 * Consider various exemptions ...
+		 * Check the dentry's age to see whether to change direction.
 		 */
-		if (!page_count) {
-			if (!inode)
-				continue;
-			if (value >= 3)
-				continue;
-		} else if (!forward) {
-			if (inode) {
-				int age = CURRENT_TIME - inode->i_atime;
-				if (age < dentry_stat.age_limit) {
-					if (++young > 8) {
-						forward = 1;
-						next = dentry_unused.next;
+		if (!forward) {
+			int age = (jiffies - dentry->d_reftime) / HZ;
+			if (age < dentry_stat.age_limit) {
+				if (!--young) {
+					forward = 1;
+					next = dentry_unused.next;
+					/*
+		 			 * Update the limits -- we don't want
+					 * files with too few or too many pages.
+					 */
+ 					if (page_count) {
+						min_value = 3;
+						max_value = 15;
+					}
 #ifdef DCACHE_DEBUG
-printk("select_dcache: age=%d, pages=%d, scanning forward\n", age, pages);
+printk("select_dcache: %s/%s age=%d, scanning forward\n",
+dentry->d_parent->d_name.name, dentry->d_name.name, age);
 #endif
-					}
-					continue;
 				}
+				continue;
 			}
-		} else {
-			/*
-			 * If we're scanning from the front, don't take
-			 * files with only a trivial amount of memory.
-			 */
-			if (value < 3 || value > 15)
+		} 
+
+		/*
+		 * 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 || value < min_value)
+				continue;
+			if (inode->i_state || inode->i_count > 1)
 				continue;
 		}
+
 		/*
-		 * Move the dentry behind the tail
+		 * Move the selected dentries behind the tail.
 		 */
 		if (tmp != tail->prev) {
 			list_del(tmp);
 			list_add(tmp, tail->prev);
 		}
 		tail = tmp;
-		pages += value;
-		if (++found >= count)
+		found++;
+		if (inode && --inode_count <= 0)
 			break;
-		if (page_count && pages >= page_count)
+		if (page_count && (page_count -= value) <= 0)
 			break;
 	}
 	return found;
@@ -364,7 +375,7 @@
 		if (goal) {
 			if (goal > 50)
 				goal = 50;
-			count = select_dcache(128, goal);
+			count = select_dcache(32, goal);
 #ifdef DCACHE_DEBUG
 printk("check_dcache_memory: goal=%d, count=%d\n", goal, count);
 #endif
@@ -387,7 +398,7 @@
 	 * Prune the dcache if there are too many unused dentries.
 	 */
 	if (dentry_stat.nr_unused > 3*(nr_inodes >> 1)) {
-#ifdef DCACHE_PARANOIA
+#ifdef DCACHE_DEBUG
 printk("d_alloc: %d unused, pruning dcache\n", dentry_stat.nr_unused);
 #endif
 		prune_dcache(8);
--- linux-2.1.61/fs/inode.c.old	Fri Oct 31 00:25:17 1997
+++ linux-2.1.61/fs/inode.c	Fri Oct 31 09:35:25 1997
@@ -358,33 +384,30 @@
  */
 static void try_to_free_inodes(int goal)
 {
-	int retried = 0, found;
+	int retry = 1, found;
 
 	/*
 	 * Check whether to preshrink the dcache ...
 	 */
-	if (inodes_stat.preshrink) {
-		spin_unlock(&inode_lock);
-		select_dcache(goal, 0);
-		prune_dcache(goal);
-		spin_lock(&inode_lock);
-	}
+	if (inodes_stat.preshrink)
+		goto preshrink;
 
-repeat:
-	found = free_inodes(goal);
-
-	/*
-	 * If we didn't free any inodes, do a limited
-	 * pruning of the dcache to help the next time.
-	 */
-	if (!found) {
+	retry = 0;
+	do {
+		if (free_inodes(goal))
+			break;
+		/*
+		 * If we didn't free any inodes, do a limited
+		 * pruning of the dcache to help the next time.
+		 */
+	preshrink:
 		spin_unlock(&inode_lock);
-		select_dcache(goal, 0);
-		prune_dcache(goal);
+		found = select_dcache(goal, 0);
+		if (found < goal)
+			found = goal;
+		prune_dcache(found);
 		spin_lock(&inode_lock);
-		if (inodes_stat.preshrink && !retried++)
-			goto repeat;
-	}
+	} while (retry--);
 }
 
 /*
@@ -440,11 +463,11 @@
 	 * If the allocation failed, do an extensive pruning of 
 	 * the dcache and then try again to free some inodes.
 	 */
-	prune_dcache(128);
+	prune_dcache(inodes_stat.nr_inodes >> 2);
 	inodes_stat.preshrink = 1;
 
 	spin_lock(&inode_lock);
-	free_inodes(128);
+	free_inodes(inodes_stat.nr_inodes >> 2);
 	{
 		struct list_head *tmp = inode_unused.next;
 		if (tmp != &inode_unused) {
\
 
 \ /
  Last update: 2005-03-22 13:40    [from the cache]
©2003-2008