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
--------------BB932D7A9A5ED2B6BA13EF25
Content-Type: text/plain; charset=us-ascii; name="dcache_61-patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="dcache_61-patch"
--- 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) {
--------------BB932D7A9A5ED2B6BA13EF25--