Re: [PATCH 7/5] Optimise d_find_alias()

[Matthew Wilcox <matthew@wil.cx>]

On Fri, Mar 03, 2006 at 03:45:52AM -0800, Andrew Morton wrote:
> David Howells <dhowells@redhat.com> wrote:
> >  struct dentry * d_find_alias(struct inode *inode)
> >   {
> >  -	struct dentry *de;
> >  -	spin_lock(&dcache_lock);
> >  -	de = __d_find_alias(inode, 0);
> >  -	spin_unlock(&dcache_lock);
> >  +	struct dentry *de = NULL;
> >  +	if (!list_empty(&inode->i_dentry)) {
> >  +		spin_lock(&dcache_lock);
> >  +		de = __d_find_alias(inode, 0);
> >  +		spin_unlock(&dcache_lock);
> >  +	}
> >   	return de;
> >   }
> 
> How can we get away without a barrier?

We'd have to be synchronised higher up in order to care, I think.

The condition we're testing is !list_empty(&inode->i_dentry)
which will presumably be optimised by the compiler into
inode->i_dentry.next != &inode->i_dentry -- IOW determined by a single
load.

Both false negatives and false positives are interesting, so we're
concerned with any write from another CPU that changes inode->i_dentry.next 
d_instantiate() looks like a good candidate for analysing races.

CPU1				CPU2

d_instantiate()
spin_lock(&dcache_lock);
				
				d_find_alias()
				if (!list_empty(&inode->i_dentry)) {
list_add(&entry->d_alias, &inode->i_dentry);
spin_unlock(&dcache_lock);
					spin_lock(&dcache_lock);
					__d_find_alias()
					spin_unlock(&dcache_lock);
				}

I don't see how putting a barrier in helps determine whether the
list_add is before or after the load for list_empty.  So I think it's
a  benign race.  If it returns NULL, it's the same as the case where
d_instantiate() is called after __d_find_alias() returns.  If
list_empty() is false, grabbing the dcache_lock means we'll find the
list really is empty after all.

So it's not a correctness thing, it's a question of how many times we
lose the race, and what the performance penalty is for doing so (and what
the performance penalty is for ensuring we lose the race less often).
And I don't know the answer to that.