Re: Q. hlist_bl_add_head_rcu() in d_alloc_parallel()

["J. R. Okajima" <hooanon05g@gmail.com>]

Al Viro:
> How would processB get past d_wait_lookup()?  It would have to have

By the first d_unhashed() test in the loop, processB doesn't reach
d_wait_lookup().

Here is a more detailed scenario I am considering.
- two processes try opening the same file
- the both enter lookup_open() and the hlist_bl_lock protected loop in
  d_alloc_parallel()

processA (the winner of hlist_bl_lock)
d_alloc_parallel()
+ new = d_alloc()
+ rcu_read_lock()
+ dentry = __d_lookup_rcu()
  NULL
+ hlist_bl_lock()		--- (BL0)
+ test parent's i_dir_seq	--- (DS1)
+ rcu_read_unlock()
+ hlist_bl_for_each_entry(d_u.d_in_lookup_hash)
  not found
+ new->d_flags |= DCACHE_PAR_LOOKUP
+ new->d_wait = wq
+ hlist_bl_add_head_rcu(new->d_u.d_in_lookup_hash)
+ hlist_bl_unlock()		--- (BL1)
+ return new
--> a new dentry is added into in-lookup hash.

And then
processA
->atomic_open or ->lookup
+ __d_add()
  + spin_lock(d_lock)
  + update parent's i_dir_seq	--- (DS2)
  + __d_lookup_done()
    + hlist_bl_lock()		--- (BL2)
    + dentry->d_flags &= ~DCACHE_PAR_LOOKUP
    + __hlist_bl_del(d_u.d_in_lookup_hash)
    + hlist_bl_unlock()		--- (BL3)
  + _d_rehash()
    + hlist_bl_lock()		--- (BL4)
    + hlist_bl_add_head_rcu(d_hash)
    + hlist_bl_unlock()
  + spin_unlock(d_lock)
--> the new dentry is moved from in-lookup to primary hash.


Between (BL1) and (BL2) in processA flow, processB may acquire
hlist_bl_lock() which was blocked at (BL0), and it may happen even
before processA's (DS2).
In this case, processB will return an unexpectedly duplicated dentry
because DS1 test will be passed and the loop body will be skipped by
d_unhashed() test before d_wait_lookup().
It is after (BL4) when d_unhashed() turns FALSE.

processB
d_alloc_parallel()
+ hlist_bl_lock()
+ test parent's i_dir_seq
  passed if processA doesn't reach (DS2) yet.
+ rcu_read_unlock()
+ hlist_bl_for_each_entry(d_u.d_in_lookup_hash)
  dentry found but skips because
	if (d_unhashed(dentry))
		continue;
  before d_wait_lookup().
+ new->d_flags |= DCACHE_PAR_LOOKUP
+ new->d_wait = wq
+ hlist_bl_add_head_rcu(new->d_u.d_in_lookup_hash)
+ hlist_bl_unlock()
+ return new
--> another same named dentry is added into in-lookup hash.


On the other hand, in case of processB acquires hlist_bl_lock() between
(BL3) and (BL4) in processA's flow, processB will detect the parent's
i_dir_seq is modified and 'goto retry'. It is good.

Finally the race condition I am afraid is
- processB aqcuires BL0 between processA's BL1 and BL2.
  and
- processB tests DS1 before processA's DS2.


J. R. Okajima