[patch 0/3] Dentry support for Slab Fragmentation Reduction

[patch 0/3] Dentry support for Slab Fragmentation Reduction

[Christoph Lameter]

This is basically a repost of the 2 patches that were dropped because
they caused oopses plus a fixup patch.

The reason for the failures was that commit
4a0962abd187df29b7d1378b2f372a55667d54c04a0962abd187df29b7d1378b2f372a55667d54c0
(back in February) was clobbered by a later
commit. As a result the dentry objects did not have consistent object
state on free which did not allow accurate object state determination.

The first patch fixes the dentry code so that there is a consistent object
state on free again.

---

[patch 1/3] dentries: Always use list_del_init() when removing a dentry from the lru

[Christoph Lameter]

[-- Attachment #1: consitent --]
[-- Type: text/plain, Size: 2831 bytes --]

The patch restores what commit 4a0962abd187df29b7d1378b2f372a55667d54c0
already implemented. The feature was subsequently clobbered by
commit da3bbdd4632c0171406b2677e31494afa5bde2f8

Before this patch some execution path use list_del() instead of
list_del_init() which results in inconsitencies in the state of d_lru
when the object is freed.

The performance of list_del_init() and list_del() is the same.
So lets just have one dentry removal function named dentry_lru_del() that always
does a list_del_init().

The result of this patch is that dentry->d_lru is now always empty when a
dentry is freed. The dentry defragmentation patch depends on a defined state
of a dentry on free.

Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

Index: linux-next/fs/dcache.c
===================================================================
--- linux-next.orig/fs/dcache.c	2008-08-25 15:44:58.000000000 -0500
+++ linux-next/fs/dcache.c	2008-08-25 15:45:59.000000000 -0500
@@ -141,15 +141,6 @@
 static void dentry_lru_del(struct dentry *dentry)
 {
 	if (!list_empty(&dentry->d_lru)) {
-		list_del(&dentry->d_lru);
-		dentry->d_sb->s_nr_dentry_unused--;
-		dentry_stat.nr_unused--;
-	}
-}
-
-static void dentry_lru_del_init(struct dentry *dentry)
-{
-	if (likely(!list_empty(&dentry->d_lru))) {
 		list_del_init(&dentry->d_lru);
 		dentry->d_sb->s_nr_dentry_unused--;
 		dentry_stat.nr_unused--;
@@ -316,7 +307,7 @@
 static inline struct dentry * __dget_locked(struct dentry *dentry)
 {
 	atomic_inc(&dentry->d_count);
-	dentry_lru_del_init(dentry);
+	dentry_lru_del(dentry);
 	return dentry;
 }
 
@@ -432,7 +423,7 @@
 
 		if (dentry->d_op && dentry->d_op->d_delete)
 			dentry->d_op->d_delete(dentry);
-		dentry_lru_del_init(dentry);
+		dentry_lru_del(dentry);
 		__d_drop(dentry);
 		dentry = d_kill(dentry);
 		spin_lock(&dcache_lock);
@@ -492,7 +483,7 @@
 	}
 	while (!list_empty(&tmp)) {
 		dentry = list_entry(tmp.prev, struct dentry, d_lru);
-		dentry_lru_del_init(dentry);
+		dentry_lru_del(dentry);
 		spin_lock(&dentry->d_lock);
 		/*
 		 * We found an inuse dentry which was not removed from
@@ -621,7 +612,7 @@
 
 	/* detach this root from the system */
 	spin_lock(&dcache_lock);
-	dentry_lru_del_init(dentry);
+	dentry_lru_del(dentry);
 	__d_drop(dentry);
 	spin_unlock(&dcache_lock);
 
@@ -635,7 +626,7 @@
 			spin_lock(&dcache_lock);
 			list_for_each_entry(loop, &dentry->d_subdirs,
 					    d_u.d_child) {
-				dentry_lru_del_init(loop);
+				dentry_lru_del(loop);
 				__d_drop(loop);
 				cond_resched_lock(&dcache_lock);
 			}
@@ -817,7 +808,7 @@
 		struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
 		next = tmp->next;
 
-		dentry_lru_del_init(dentry);
+		dentry_lru_del(dentry);
 		/* 
 		 * move only zero ref count dentries to the end 
 		 * of the unused list for prune_dcache

-- 

Re: [patch 1/3] dentries: Always use list_del_init() when removing a dentry from the lru

[Pekka Enberg]

Christoph Lameter wrote:
> The patch restores what commit 4a0962abd187df29b7d1378b2f372a55667d54c0
> already implemented. The feature was subsequently clobbered by
> commit da3bbdd4632c0171406b2677e31494afa5bde2f8
> 
> Before this patch some execution path use list_del() instead of
> list_del_init() which results in inconsitencies in the state of d_lru
> when the object is freed.
> 
> The performance of list_del_init() and list_del() is the same.
> So lets just have one dentry removal function named dentry_lru_del() that always
> does a list_del_init().
> 
> The result of this patch is that dentry->d_lru is now always empty when a
> dentry is freed. The dentry defragmentation patch depends on a defined state
> of a dentry on free.
> 
> Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

Applied, thanks!

[patch 2/3] dentries: Add constructor

[Christoph Lameter]

[-- Attachment #1: 0031-dentries-Add-constructor.patch --]
[-- Type: text/plain, Size: 2159 bytes --]

In order to support defragmentation on the dentry cache we need to have
a determined object state at all times. Without a constructor the object
would have a random state after allocation.

So provide a constructor.

Cc: Alexander Viro <viro@ftp.linux.org.uk>
Cc: Christoph Hellwig <hch@infradead.org>
Reviewed-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Christoph Lameter <clameter@sgi.com>
Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

---
 fs/dcache.c |   26 ++++++++++++++------------
 1 file changed, 14 insertions(+), 12 deletions(-)

Index: linux-next/fs/dcache.c
===================================================================
--- linux-next.orig/fs/dcache.c	2008-08-25 15:54:27.000000000 -0500
+++ linux-next/fs/dcache.c	2008-08-25 15:55:10.000000000 -0500
@@ -890,6 +890,16 @@
 	.seeks = DEFAULT_SEEKS,
 };
 
+static void dcache_ctor(void *p)
+{
+	struct dentry *dentry = p;
+
+	spin_lock_init(&dentry->d_lock);
+	dentry->d_inode = NULL;
+	INIT_LIST_HEAD(&dentry->d_lru);
+	INIT_LIST_HEAD(&dentry->d_alias);
+}
+
 /**
  * d_alloc	-	allocate a dcache entry
  * @parent: parent of entry to allocate
@@ -927,8 +937,6 @@
 
 	atomic_set(&dentry->d_count, 1);
 	dentry->d_flags = DCACHE_UNHASHED;
-	spin_lock_init(&dentry->d_lock);
-	dentry->d_inode = NULL;
 	dentry->d_parent = NULL;
 	dentry->d_sb = NULL;
 	dentry->d_op = NULL;
@@ -938,9 +946,7 @@
 	dentry->d_cookie = NULL;
 #endif
 	INIT_HLIST_NODE(&dentry->d_hash);
-	INIT_LIST_HEAD(&dentry->d_lru);
 	INIT_LIST_HEAD(&dentry->d_subdirs);
-	INIT_LIST_HEAD(&dentry->d_alias);
 
 	if (parent) {
 		dentry->d_parent = dget(parent);
@@ -2268,14 +2274,10 @@
 {
 	int loop;
 
-	/* 
-	 * A constructor could be added for stable state like the lists,
-	 * but it is probably not worth it because of the cache nature
-	 * of the dcache. 
-	 */
-	dentry_cache = KMEM_CACHE(dentry,
-		SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_MEM_SPREAD);
-	
+	dentry_cache = kmem_cache_create("dentry_cache", sizeof(struct dentry),
+		0, SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_MEM_SPREAD,
+		dcache_ctor);
+
 	register_shrinker(&dcache_shrinker);
 
 	/* Hash may have been set up in dcache_init_early */

-- 

Re: [patch 2/3] dentries: Add constructor

[Pekka Enberg]

Christoph Lameter wrote:
> In order to support defragmentation on the dentry cache we need to have
> a determined object state at all times. Without a constructor the object
> would have a random state after allocation.
> 
> So provide a constructor.

Applied, thanks!

[patch 3/3] dentries: dentry defragmentation

[Christoph Lameter]

[-- Attachment #1: 0032-dentries-dentry-defragmentation.patch --]
[-- Type: text/plain, Size: 4095 bytes --]

The dentry pruning for unused entries works in a straightforward way. It
could be made more aggressive if one would actually move dentries instead
of just reclaiming them.

Cc: Alexander Viro <viro@ftp.linux.org.uk>
Cc: Christoph Hellwig <hch@infradead.org>
Reviewed-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Christoph Lameter <clameter@sgi.com>
Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

---
 fs/dcache.c |  101 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 100 insertions(+), 1 deletion(-)

Index: linux-next/fs/dcache.c
===================================================================
--- linux-next.orig/fs/dcache.c	2008-08-25 15:55:24.000000000 -0500
+++ linux-next/fs/dcache.c	2008-08-25 15:59:46.000000000 -0500
@@ -32,6 +32,7 @@
 #include <linux/seqlock.h>
 #include <linux/swap.h>
 #include <linux/bootmem.h>
+#include <linux/backing-dev.h>
 #include "internal.h"
 
 
@@ -163,7 +164,10 @@
 
 	list_del(&dentry->d_u.d_child);
 	dentry_stat.nr_dentry--;	/* For d_free, below */
-	/*drops the locks, at that point nobody can reach this dentry */
+	/*
+	 * drops the locks, at that point nobody (aside from defrag)
+	 * can reach this dentry
+	 */
 	dentry_iput(dentry);
 	parent = dentry->d_parent;
 	d_free(dentry);
@@ -2270,6 +2274,100 @@
 		INIT_HLIST_HEAD(&dentry_hashtable[loop]);
 }
 
+/*
+ * The slab allocator is holding off frees. We can safely examine
+ * the object without the danger of it vanishing from under us.
+ */
+static void *get_dentries(struct kmem_cache *s, int nr, void **v)
+{
+	struct dentry *dentry;
+	int i;
+
+	spin_lock(&dcache_lock);
+	for (i = 0; i < nr; i++) {
+		dentry = v[i];
+
+		/*
+		 * Three sorts of dentries cannot be reclaimed:
+		 *
+		 * 1. dentries that are in the process of being allocated
+		 *    or being freed. In that case the dentry is neither
+		 *    on the LRU nor hashed.
+		 *
+		 * 2. Fake hashed entries as used for anonymous dentries
+		 *    and pipe I/O. The fake hashed entries have d_flags
+		 *    set to indicate a hashed entry. However, the
+		 *    d_hash field indicates that the entry is not hashed.
+		 *
+		 * 3. dentries that have a backing store that is not
+		 *    writable. This is true for tmpsfs and other in
+		 *    memory filesystems. Removing dentries from them
+		 *    would loose dentries for good.
+		 */
+		if ((d_unhashed(dentry) && list_empty(&dentry->d_lru)) ||
+		   (!d_unhashed(dentry) && hlist_unhashed(&dentry->d_hash)) ||
+		   (dentry->d_inode &&
+		   !mapping_cap_writeback_dirty(dentry->d_inode->i_mapping)))
+			/* Ignore this dentry */
+			v[i] = NULL;
+		else
+			/* dget_locked will remove the dentry from the LRU */
+			dget_locked(dentry);
+	}
+	spin_unlock(&dcache_lock);
+	return NULL;
+}
+
+/*
+ * Slab has dropped all the locks. Get rid of the refcount obtained
+ * earlier and also free the object.
+ */
+static void kick_dentries(struct kmem_cache *s,
+				int nr, void **v, void *private)
+{
+	struct dentry *dentry;
+	int i;
+
+	/*
+	 * First invalidate the dentries without holding the dcache lock
+	 */
+	for (i = 0; i < nr; i++) {
+		dentry = v[i];
+
+		if (dentry)
+			d_invalidate(dentry);
+	}
+
+	/*
+	 * If we are the last one holding a reference then the dentries can
+	 * be freed. We need the dcache_lock.
+	 */
+	spin_lock(&dcache_lock);
+	for (i = 0; i < nr; i++) {
+		dentry = v[i];
+		if (!dentry)
+			continue;
+
+		spin_lock(&dentry->d_lock);
+		if (atomic_read(&dentry->d_count) > 1) {
+			spin_unlock(&dentry->d_lock);
+			spin_unlock(&dcache_lock);
+			dput(dentry);
+			spin_lock(&dcache_lock);
+			continue;
+		}
+
+		prune_one_dentry(dentry);
+	}
+	spin_unlock(&dcache_lock);
+
+	/*
+	 * dentries are freed using RCU so we need to wait until RCU
+	 * operations are complete.
+	 */
+	synchronize_rcu();
+}
+
 static void __init dcache_init(void)
 {
 	int loop;
@@ -2279,6 +2377,7 @@
 		dcache_ctor);
 
 	register_shrinker(&dcache_shrinker);
+	kmem_cache_setup_defrag(dentry_cache, get_dentries, kick_dentries);
 
 	/* Hash may have been set up in dcache_init_early */
 	if (!hashdist)

-- 

Re: [patch 3/3] dentries: dentry defragmentation

[Pekka Enberg]

Christoph Lameter wrote:
> The dentry pruning for unused entries works in a straightforward way. It
> could be made more aggressive if one would actually move dentries instead
> of just reclaiming them.
> 
> Cc: Alexander Viro <viro@ftp.linux.org.uk>
> Cc: Christoph Hellwig <hch@infradead.org>
> Reviewed-by: Rik van Riel <riel@redhat.com>
> Signed-off-by: Christoph Lameter <clameter@sgi.com>
> Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

Applied, thanks!

Re: [patch 3/3] dentries: dentry defragmentation

[Nick Piggin]

This doesn't come with any numbers or test cases or results?

On Tuesday 26 August 2008 07:20, Christoph Lameter wrote:
> The dentry pruning for unused entries works in a straightforward way. It
> could be made more aggressive if one would actually move dentries instead
> of just reclaiming them.
>
> Cc: Alexander Viro <viro@ftp.linux.org.uk>
> Cc: Christoph Hellwig <hch@infradead.org>
> Reviewed-by: Rik van Riel <riel@redhat.com>
> Signed-off-by: Christoph Lameter <clameter@sgi.com>
> Signed-off-by: Christoph Lameter <cl@linux-foundation.org>
>
> ---
>  fs/dcache.c |  101
> +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file
> changed, 100 insertions(+), 1 deletion(-)
>
> Index: linux-next/fs/dcache.c
> ===================================================================
> --- linux-next.orig/fs/dcache.c	2008-08-25 15:55:24.000000000 -0500
> +++ linux-next/fs/dcache.c	2008-08-25 15:59:46.000000000 -0500
> @@ -32,6 +32,7 @@
>  #include <linux/seqlock.h>
>  #include <linux/swap.h>
>  #include <linux/bootmem.h>
> +#include <linux/backing-dev.h>
>  #include "internal.h"
>
>
> @@ -163,7 +164,10 @@
>
>  	list_del(&dentry->d_u.d_child);
>  	dentry_stat.nr_dentry--;	/* For d_free, below */
> -	/*drops the locks, at that point nobody can reach this dentry */
> +	/*
> +	 * drops the locks, at that point nobody (aside from defrag)
> +	 * can reach this dentry
> +	 */
>  	dentry_iput(dentry);
>  	parent = dentry->d_parent;
>  	d_free(dentry);
> @@ -2270,6 +2274,100 @@
>  		INIT_HLIST_HEAD(&dentry_hashtable[loop]);
>  }
>
> +/*
> + * The slab allocator is holding off frees. We can safely examine
> + * the object without the danger of it vanishing from under us.
> + */
> +static void *get_dentries(struct kmem_cache *s, int nr, void **v)
> +{
> +	struct dentry *dentry;
> +	int i;
> +
> +	spin_lock(&dcache_lock);
> +	for (i = 0; i < nr; i++) {
> +		dentry = v[i];
> +
> +		/*
> +		 * Three sorts of dentries cannot be reclaimed:
> +		 *
> +		 * 1. dentries that are in the process of being allocated
> +		 *    or being freed. In that case the dentry is neither
> +		 *    on the LRU nor hashed.
> +		 *
> +		 * 2. Fake hashed entries as used for anonymous dentries
> +		 *    and pipe I/O. The fake hashed entries have d_flags
> +		 *    set to indicate a hashed entry. However, the
> +		 *    d_hash field indicates that the entry is not hashed.
> +		 *
> +		 * 3. dentries that have a backing store that is not
> +		 *    writable. This is true for tmpsfs and other in
> +		 *    memory filesystems. Removing dentries from them
> +		 *    would loose dentries for good.
> +		 */
> +		if ((d_unhashed(dentry) && list_empty(&dentry->d_lru)) ||
> +		   (!d_unhashed(dentry) && hlist_unhashed(&dentry->d_hash)) ||
> +		   (dentry->d_inode &&
> +		   !mapping_cap_writeback_dirty(dentry->d_inode->i_mapping)))
> +			/* Ignore this dentry */
> +			v[i] = NULL;
> +		else
> +			/* dget_locked will remove the dentry from the LRU */
> +			dget_locked(dentry);
> +	}
> +	spin_unlock(&dcache_lock);
> +	return NULL;
> +}
> +
> +/*
> + * Slab has dropped all the locks. Get rid of the refcount obtained
> + * earlier and also free the object.
> + */
> +static void kick_dentries(struct kmem_cache *s,
> +				int nr, void **v, void *private)
> +{
> +	struct dentry *dentry;
> +	int i;
> +
> +	/*
> +	 * First invalidate the dentries without holding the dcache lock
> +	 */
> +	for (i = 0; i < nr; i++) {
> +		dentry = v[i];
> +
> +		if (dentry)
> +			d_invalidate(dentry);
> +	}
> +
> +	/*
> +	 * If we are the last one holding a reference then the dentries can
> +	 * be freed. We need the dcache_lock.
> +	 */
> +	spin_lock(&dcache_lock);
> +	for (i = 0; i < nr; i++) {
> +		dentry = v[i];
> +		if (!dentry)
> +			continue;
> +
> +		spin_lock(&dentry->d_lock);
> +		if (atomic_read(&dentry->d_count) > 1) {
> +			spin_unlock(&dentry->d_lock);
> +			spin_unlock(&dcache_lock);
> +			dput(dentry);
> +			spin_lock(&dcache_lock);
> +			continue;
> +		}
> +
> +		prune_one_dentry(dentry);
> +	}
> +	spin_unlock(&dcache_lock);
> +
> +	/*
> +	 * dentries are freed using RCU so we need to wait until RCU
> +	 * operations are complete.
> +	 */
> +	synchronize_rcu();
> +}
> +
>  static void __init dcache_init(void)
>  {
>  	int loop;
> @@ -2279,6 +2377,7 @@
>  		dcache_ctor);
>
>  	register_shrinker(&dcache_shrinker);
> +	kmem_cache_setup_defrag(dentry_cache, get_dentries, kick_dentries);
>
>  	/* Hash may have been set up in dcache_init_early */
>  	if (!hashdist)