Re: lock coupling (was: Re: Cleaning up namei)

[David Holland <dholland-tech%netbsd.org@localhost>]

On Thu, Mar 20, 2008 at 02:30:03AM -0400, der Mouse wrote:
 > >> I'm not sure I understand what you're trying to prove.
 > > That no-lock-coupling is no worse (in terms of possible consistency
 > > violations) than lock-coupling, except perhaps for a couple corner
 > > cases of limited concern, and particularly so for lookups other than
 > > the final step or two before performing a "real" operation.
 > 
 > Hm.
 > 
 > As I understand lock coupling, it means (in this context) that, as you
 > walk a path, you hold each directory vnode locked until you have not
 > only looked up but also locked the next.  That is, you always hold at
 > least one lock and sometimes hold two locks.  No-lock-coupling, then,
 > means that you hold either zero or one lock for a path walk, except for
 > a few special cases such as DELETE lookup leaves.  (All of those are
 > not counting the shared lock implicit in holding a reference to a
 > vnode.)
 > 
 > Are those accurate?  I've been thinking about locking and haven't come
 > to any definite conclusions, but would like to make sure we're talking
 > about the same thing.

Yes.

(CREATE leaves as well as DELETE, plus also RENAME - basically, any of
the operations that modify the directory that contains or will contain
the file that's being looked up. These need to lock the last two
elements of the path rather than just the last one, and they must hold
both locks until the operation is complete. But this is still
basically the same as what you said.)

 > > [...exampels of locking issues...]
 > 
 > > I think it likely that a similar example can be cooked up for vnodes,
 > > but at the moment I don't feel inclined to prepare it.  Consider it
 > > an exercise for the reader. :-)
 > 
 > I think it probably requires either .. or symlinks, though.  

Yes, because we only write to objects found at the end of a lookup
path. To get a serialization conflict you need one process to be both
strictly before and strictly after another. Reads are commutative with
other reads, so only writes create ordering requirements. Getting a
conflict thus requires two objects where one process reads and the
other writes; therefore, since each stops after writing, they must be
going in opposite directions. Which you can do either via .. or via
jumping to /.

Or, alternatively, you can conflict with a call that looks up two
different paths but is still supposed to be atomic, like link().

 > >> So, I've probably misunderstood something....
 > > Nah, just the context... that's a pretty good counterexample,
 > > actually.  It's just one for something I wasn't trying to prove. :-)
 > 
 > So, I would say, what I misunderstood is what it was you were trying to
 > prove. :)

Right.

-- 
David A. Holland
dholland%netbsd.org@localhost