Re: Q. hlist_bl_add_head_rcu() in d_alloc_parallel()

[Al Viro <viro@ZenIV.linux.org.uk>]

On Fri, Jun 17, 2016 at 11:16:14PM +0100, Al Viro wrote:

> We are *NOT* modifying the primary hash in d_alloc_parallel().  At all.
> With respect to the primary hash it's a pure reader.  And in-lookup hash
> is only accessed under hlist_bl_lock() on its chains - no RCU accesses to
> that one.

Note that if d_alloc_parallel() finds a matching dentry in the in-lookup hash,
it does *NOT* return it until it has left in-lookup hash and had been moved
to the primary one.

That's what d_wait_lookup() call is about; we wait for whoever had added it
into in-lookup hash to be done with it.  Then we check if it's been transferred
into the primary hash (with the same name and parent).  If it has been,
we treat it as if we'd found it in the primary hash in the first place -
it's not an in-lookup one anymore.  If it hasn't, we repeat the whole thing
from scratch, starting with primary hash lookup.

The *only* case when we return an in-lookup dentry is when we had allocated
it, found no matches either in primary or in-lookup hashes and inserted it
into in-lookup hash.  What happens is an optimized variant of this:

	new = new dentry instance
retry:
	fetch the value of ->i_dir_seq
	look for match in primary
	if found - drop what we'd allocated and return what we'd found
	lock the chain in in-lookup hash
	check if ->i_dir_seq has changed
	if it has changed
		unlock the chain
		goto retry
	look for match in in-lookup hash
	if found
		unlock the chain
		wait for the match to cease being in-lookup
		drop the match
		goto retry	[see below]
	insert new into in-lookup hash
	unlock the chain
	return new

The difference between that and actual d_alloc_parallel() is a simple
optimisation in the last goto retry - the one after waiting for match
to leave in-lookup hash.  Pseudocode above would rescan the primary hash;
very often it would end up finding the same dentry we'd just been waiting
for.  So if our match is hashed and still has the same name and parent we
can return it without bothering with primary hash lookup.  It is common
enough to be worth doing, but it's just an optimisation - behaviour is
the same as if we'd followed d_wait_lookup() with unconditional
        spin_unlock(&dentry->d_lock);
        dput(dentry);
        goto retry;

The only difference is that we don't bother with drop/search in primary/find
and grab the same match in a very common case.