I've put together a new implementation of a shrink_dcache_parent()
routine that's more than twice as fast as the first attempt. The
increased efficiency is made possible by using the d_reftime field (as
added by my dcache management patch) as a marker for the selected child
dentries. This avoids having to check parentage twice.
The code also tracks the latest dentry not selected in the first pass,
and relies on the time ordering of the unused dentries so that it can
stop scanning early. This should speed up the most common case of
trimming a few dentries from one directory.
The recent problems uncovered in nfs and msdos fs due to unpruned child
dentries have made it more important that we have a prune_child_dentry
operation, even if it's not optimally efficient. I think this patch is
a reasonable approach given the current data structures, and if things
change in the future we can just replace it.
Regards,
Bill
--------------FAB5EE05C2C2C796550CBCF6
Content-Type: text/plain; charset=us-ascii; name="dcache_sdp61-patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="dcache_sdp61-patch"
--- fs/dcache.c.old Fri Oct 31 00:26:07 1997
+++ fs/dcache.c Mon Nov 3 14:48:03 1997
@@ -338,6 +349,120 @@
}
/*
+ * Check whether a dentry is a child of the parent.
+ */
+static int d_is_child(struct dentry * dentry, struct dentry * parent)
+{
+ int is_child = 1;
+ for ( ;; ) {
+ if (dentry == parent)
+ break;
+ if (dentry != dentry->d_parent) {
+ dentry = dentry->d_parent;
+ continue;
+ }
+ is_child = 0;
+ break;
+ }
+ return is_child;
+}
+
+/*
+ * Prune the dcache to remove children of the parent dentry.
+ * The super block provides a quick no-go parenthood test.
+ *
+ * This implementation is similar to shrink_dcache_sb, but
+ * marks selected dentries to avoid repeating the costly
+ * parenthood test. In addition, it tracks the most recently
+ * unused dentry _not_ selected, to allow early termination.
+ *
+ * Subtle note: any dentries renamed to _become_ children of
+ * this parent after the selection pass will have d_reftime
+ * equal or later than max_time. (If they're on the unused
+ * list at all.)
+ */
+void shrink_dcache_parent(struct dentry * parent)
+{
+ struct list_head *tmp, *next;
+ struct super_block *sb = parent->d_sb;
+ struct dentry *dentry;
+ unsigned long max_time = 0;
+ int found = 0;
+
+ /*
+ * Pass one ... move the dentries for the specified
+ * parent to the most recent end of the unused list,
+ * and mark them with a special value in d_reftime.
+ */
+ next = dentry_unused.next;
+ while (next != &dentry_unused) {
+ tmp = next;
+ next = tmp->next;
+ dentry = list_entry(tmp, struct dentry, d_lru);
+ if (dentry->d_sb != sb)
+ continue;
+ if (dentry->d_count)
+ continue;
+ if (!d_is_child(dentry, parent)) {
+ if (dentry->d_reftime > max_time)
+ max_time = dentry->d_reftime;
+ continue;
+ }
+ /*
+ * Mark the dentry with a special value in d_reftime.
+ */
+ dentry->d_reftime = 0;
+ list_del(tmp);
+ list_add(tmp, &dentry_unused);
+ found++;
+ }
+#ifdef DCACHE_DEBUG
+printk("shrink_dcache_parent: %s/%s found %d, max=%lu\n",
+parent->d_parent->d_name.name, parent->d_name.name, found, max_time);
+#endif
+ if (!found)
+ goto out;
+
+ /*
+ * Pass two ... free the dentries for this parent.
+ * We don't need to retest dentries marked with the
+ * special time or those earlier than max_time.
+ */
+repeat:
+ next = dentry_unused.next;
+ while (next != &dentry_unused) {
+ tmp = next;
+ next = tmp->next;
+ dentry = list_entry(tmp, struct dentry, d_lru);
+ if (dentry->d_sb != sb)
+ continue;
+ if (dentry->d_count)
+ continue;
+ /*
+ * If d_reftime is non-zero, we have to check parenthood.
+ * But if it's strictly earlier than max_time, we're done.
+ */
+ if (dentry->d_reftime != 0) {
+ if (dentry->d_reftime < max_time) {
+#ifdef DCACHE_DEBUG
+printk("shrink_dcache_parent: %s/%s time %lu < %lu\n",
+dentry->d_parent->d_name.name,dentry->d_name.name,dentry->d_reftime,max_time);
+#endif
+ break;
+ }
+ if (!d_is_child(dentry, parent))
+ continue;
+ }
+ dentry_stat.nr_unused--;
+ list_del(tmp);
+ INIT_LIST_HEAD(tmp);
+ prune_one_dentry(dentry);
+ goto repeat;
+ }
+out:
+ return;
+}
+/*
* This is called from do_try_to_free_page() to indicate
* that we should reduce the dcache and inode cache memory.
*/
--------------FAB5EE05C2C2C796550CBCF6--