Re: [PATCH] Per-superblock unused dentry LRU lists.

[Balbir Singh <balbir@in.ibm.com>]

On Wed, May 24, 2006 at 11:24:12AM +1000, David Chinner wrote:
> 
> As originally described in:
> 
> http://marc.theaimsgroup.com/?l=linux-kernel&m=114491661527656&w=2
> 
> shrink_dcache_sb() becomes a severe bottleneck when the unused dentry
> list becomes long and mounts and unmounts occur frequently on the
> machine.
> 
> My initial attempt to solve the problem using per-node LRUs
> (http://marc.theaimsgroup.com/?l=linux-kernel&m=114537118504917&w=2)
> fell apart under the complexity of locking required. This approach can
> probably be made to work in the long term, but we need a robust fix 
> for now....
> 
> The patch attached below is based on the suggestion made by Andrew
> Morton here:
> 
> http://marc.theaimsgroup.com/?l=linux-fsdevel&m=114499224412427&w=2
> 
> This approach does not change any of the locking required, so avoids
> the locking problems of the per-node lru implementation.
> 
> I've attempted to make reclaim fair by keeping track of the last superblock
> we pruned, and starting from the next on in the list each time.
> 
> Signed-off-by: Dave Chinner <dgc@sgi.com>
> 
> ---
> The patch has been stress tested on single and multiple filesystems,
> using dbench, postmark and parallel create/unlink load tests. It has also
> been running on the problem server since last Saturday which currently
> has ~11 million cached dentries, and a dentry_cache slab size of ~27 million
> objects.

I like the patch already :)

<snip>

> +static void
> +dentry_lru_add(struct dentry *dentry)
> +{
> +	list_add(&dentry->d_lru, &dentry->d_sb->s_dentry_lru);
> +	dentry_stat.nr_unused++;
> +}
> +
> +static void
> +dentry_lru_add_tail(struct dentry *dentry)
> +{
> +	list_add_tail(&dentry->d_lru, &dentry->d_sb->s_dentry_lru);
> +	dentry_stat.nr_unused++;
> +}
> +
> +static void
> +dentry_lru_del(struct dentry *dentry)
> +{
> +	if (!list_empty(&dentry->d_lru)) {
> +		list_del(&dentry->d_lru);
> +		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_stat.nr_unused--;
> +	}
> +}
> +

I wonder if there should be per-sb count of number of used dentries. This
will help us while unmounting. Instead of passing count as NULL, the number
of dentries in the super block can be passed. May be we should have
per-dentry stats along with global statistics.

<snip>

>  
> +/*
> + * Shrink the dentry LRU on æ given superblock.
> + */
> +static void
> +__shrink_dcache_sb(struct super_block *sb, int *count, int flags)
> +{
> +	struct dentry *dentry;
> +	int cnt = (count == NULL) ? -1 : *count;

This code seems hacky. Some comments please. Negative counters are generally
not good IMHO. This can be avoided by per-sb dentry stats (please see
the comment above)

> +
> +	spin_lock(&dcache_lock);
> +	while (!list_empty(&sb->s_dentry_lru) && cnt--) {
> +		dentry = list_entry(sb->s_dentry_lru.prev,
> +					struct dentry, d_lru);
> +		dentry_lru_del_init(dentry);
> +		BUG_ON(dentry->d_sb != sb);
> +		prefetch(sb->s_dentry_lru.prev);
> +
> +		spin_lock(&dentry->d_lock);
> +		/*
> +		 * We found an inuse dentry which was not removed from
> +		 * the LRU because of laziness during lookup.  Do not free
> +		 * it - just keep it off the LRU list.
> +		 */
> +		if (atomic_read(&dentry->d_count)) {
> +			spin_unlock(&dentry->d_lock);
> +			continue;
> +		}
> +		/* If the dentry matches the flags passed in, don't free it.
> +		 * clear the flags and put it back on the LRU */

The comment does not follow coding style conventions. What do these flags
typically contain - DCACHE_REFERENCED? Could you clean up this comment
please.

> +		if (flags && (dentry->d_flags & flags)) {
> +			dentry->d_flags &= ~flags;
> +			dentry_lru_add(dentry);
> +			spin_unlock(&dentry->d_lock);
> +			continue;
> +		}
> +		prune_one_dentry(dentry);
> +	}
> +	spin_unlock(&dcache_lock);
> +	if (count)
> +		*count = cnt;
> +}
> +
>  /**
>   * prune_dcache - shrink the dcache
>   * @count: number of entries to try and free
> @@ -392,42 +456,44 @@ static inline void prune_one_dentry(stru
>   
>  static void prune_dcache(int count)
>  {
> -	spin_lock(&dcache_lock);
> -	for (; count ; count--) {
> -		struct dentry *dentry;
> -		struct list_head *tmp;
> -
> -		cond_resched_lock(&dcache_lock);
> +	struct super_block *sb;
> +	static struct super_block *sb_hand = NULL;
> +	int work_done = 0;
> +
> +	spin_lock(&sb_lock);
> +	if (sb_hand == NULL)
> +		sb_hand = sb_entry(super_blocks.next);
> +restart:
> +	list_for_each_entry(sb, &super_blocks, s_list) {
> +		if (sb != sb_hand)
> +			continue;
> +		/* Found the next superblock to work on.
> +		 * Move the hand forwards so that parallel
> +		 * pruners will work on a different sb */
> +		work_done++;
> +		sb_hand = sb_entry(sb->s_list.next);
> +		sb->s_count++;
> +		spin_unlock(&sb_lock);
> +
> +		/* we don't take the s_umount lock here because
> +		 * because we can be called already holding a
> +		 * write lock on a superblock */

You can use trylock. Please see the patches in -mm to fix the umount
race.

> +		if (!list_empty(&sb->s_dentry_lru))
> +			__shrink_dcache_sb(sb, &count, DCACHE_REFERENCED);
>  
> -		tmp = dentry_unused.prev;
> -		if (tmp == &dentry_unused)
> +		spin_lock(&sb_lock);
> +		if (__put_super_and_need_restart(sb) && count)
> +			goto restart;

Comment please.

> +		if (count <= 0)
>  			break;
> -		list_del_init(tmp);
> -		prefetch(dentry_unused.prev);
> - 		dentry_stat.nr_unused--;
> -		dentry = list_entry(tmp, struct dentry, d_lru);
> -
> - 		spin_lock(&dentry->d_lock);
> -		/*
> -		 * We found an inuse dentry which was not removed from
> -		 * dentry_unused because of laziness during lookup.  Do not free
> -		 * it - just keep it off the dentry_unused list.
> -		 */
> - 		if (atomic_read(&dentry->d_count)) {
> - 			spin_unlock(&dentry->d_lock);
> -			continue;
> -		}
> -		/* If the dentry was recently referenced, don't free it. */
> -		if (dentry->d_flags & DCACHE_REFERENCED) {
> -			dentry->d_flags &= ~DCACHE_REFERENCED;
> - 			list_add(&dentry->d_lru, &dentry_unused);
> - 			dentry_stat.nr_unused++;
> - 			spin_unlock(&dentry->d_lock);
> -			continue;
> -		}
> -		prune_one_dentry(dentry);
>  	}
> -	spin_unlock(&dcache_lock);
> +	if (!work_done) {
> +		/* sb_hand is stale. Start and the beginning of the
> +		 * list again. */

Please fix the comment style

> +		sb_hand = sb_entry(super_blocks.next);
> +		goto restart;
> +	}
> +	spin_unlock(&sb_lock);
>  }
>  
>  /*
> @@ -454,41 +520,7 @@ static void prune_dcache(int count)
>  
>  void shrink_dcache_sb(struct super_block * sb)
>  {
> -	struct list_head *tmp, *next;
> -	struct dentry *dentry;
> -
> -	/*
> -	 * Pass one ... move the dentries for the specified
> -	 * superblock to the most recent end of the unused list.
> -	 */
> -	spin_lock(&dcache_lock);
> -	list_for_each_safe(tmp, next, &dentry_unused) {
> -		dentry = list_entry(tmp, struct dentry, d_lru);
> -		if (dentry->d_sb != sb)
> -			continue;
> -		list_del(tmp);
> -		list_add(tmp, &dentry_unused);
> -	}
> -
> -	/*
> -	 * Pass two ... free the dentries for this superblock.
> -	 */
> -repeat:
> -	list_for_each_safe(tmp, next, &dentry_unused) {
> -		dentry = list_entry(tmp, struct dentry, d_lru);
> -		if (dentry->d_sb != sb)
> -			continue;
> -		dentry_stat.nr_unused--;
> -		list_del_init(tmp);
> -		spin_lock(&dentry->d_lock);
> -		if (atomic_read(&dentry->d_count)) {
> -			spin_unlock(&dentry->d_lock);
> -			continue;
> -		}
> -		prune_one_dentry(dentry);
> -		goto repeat;
> -	}
> -	spin_unlock(&dcache_lock);
> +	__shrink_dcache_sb(sb, NULL, 0);
>  }
>  
>  /*
> @@ -572,17 +604,13 @@ resume:
>  		struct dentry *dentry = list_entry(tmp, struct dentry, d_u.d_child);
>  		next = tmp->next;
>  
> -		if (!list_empty(&dentry->d_lru)) {
> -			dentry_stat.nr_unused--;
> -			list_del_init(&dentry->d_lru);
> -		}
> +		dentry_lru_del_init(dentry);
>  		/* 
>  		 * move only zero ref count dentries to the end 
>  		 * of the unused list for prune_dcache
>  		 */
>  		if (!atomic_read(&dentry->d_count)) {
> -			list_add(&dentry->d_lru, dentry_unused.prev);
> -			dentry_stat.nr_unused++;
> +			dentry_lru_add_tail(dentry);
>  			found++;
>  		}

This should not be required with per super-block dentries. The only
reason, I think we moved dentries to the tail is to club all entries
from the sb together (to free them all at once).

>  
> @@ -657,18 +685,14 @@ void shrink_dcache_anon(struct hlist_hea
>  		spin_lock(&dcache_lock);
>  		hlist_for_each(lp, head) {
>  			struct dentry *this = hlist_entry(lp, struct dentry, d_hash);
> -			if (!list_empty(&this->d_lru)) {
> -				dentry_stat.nr_unused--;
> -				list_del_init(&this->d_lru);
> -			}
>  
> +			dentry_lru_del_init(this);
>  			/* 
>  			 * move only zero ref count dentries to the end 
>  			 * of the unused list for prune_dcache
>  			 */
>  			if (!atomic_read(&this->d_count)) {
> -				list_add_tail(&this->d_lru, &dentry_unused);
> -				dentry_stat.nr_unused++;
> +				dentry_lru_add_tail(this);
>  				found++;
>  			}
>  		}

This might still be required. Do you want to split out the anonymous dcache
entries as well? I am not sure what their superblock points to.




	Balbir Singh,
	Linux Technology Center,
	IBM Software Labs
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/