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

[der Mouse <mouse%Rodents.Montreal.QC.CA@localhost>]

> Sketch of the proof follows:

> [...]

I'm not sure I understand what you're trying to prove.  But, based on
your sketch, it appears to be something like "interleaving
lookups-and-operation sequences will produce the same semantics as one
operation occurring entirely before the other".  However, I have a
counterexample to that.

Initial state:

/ directory, inum 2
/foo directory, inum 3
/foo/a symlink to da, inum 4
/foo/b symlink to db, inum 5
/foo/c directory, inum 6
/foo/da directory, inum 7
/foo/db empty directory, inum 8
/foo/da/sub directory, inum 9
/foo/da/sub/x symlink to /foo/b/sub/y, inum 10
/foo/da/sub/y symlink to /foo/c/sub/z, inum 11
/foo/c/sub directory, inum 12
/foo/c/sub/z plain file, inum 13

Consider two operations racing: (1) look up /foo/a/sub/x for plain-file
open; (2) rename("/foo/a","/foo/b").  If (1) happens either completely
before (2) or completely after (2), it fails, showing ENOENT at one
stage or another.  But if we interleave them like so

(1) lookup foo in 2, giving 3, rest-of-path a/sub/x
(1) lookup a in 3, giving 4, rest-of-path sub/x
(1) follow symlink, rest-of-path da/sub/x
(1) lookup da in 3, giving 7, rest-of-path sub/x
(1) lookup sub in 7, giving 9, rest-of-path x
(2) happens here, in its entirety
(a is now nonexistent, and b is inum 4, in 3)
(1) lookup x in 9, giving 10, end of path
(1) follow symlink, rest-of-path /foo/b/sub/y
(1) lookup foo in 2, giving 3, rest-of-path b/sub/y
(1) lookup b in 3, giving 4, rest-of-path sub/y
(1) follow symlink, rest-of-path da/sub/y
(1) lookup da in 3, giving 7, rest-of-path sub/y
(1) lookup sub in 7, giving 9, rest-of-path y
(1) lookup y in 9, giving 11, end of path
(1) follow symlink, rest-of-path /foo/c/sub/z
(1) lookup foo in 2, giving 3, rest-of-path c/sub/z
(1) lookup c in 3, giving 6, rest-of-path sub/z
(1) lookup sub in 6, giving 12, rest-of-path z
(1) lookup z in 12, giving 13 -> success

This makes it quite clear to me that interleaving operations does not
necessarily produce a result equivalent to one operation occurring
before the other.  (I make no pretense that the above example is
actually *useful*; it is intended as a counterexample to the result I
read you as trying to prove, nothing more.)

The point of sub is to get locks moved down far enough that the rename
doesn't run into anything currently locked.  sub could equally well be
sub1/sub2/sub3/sub4/.../subN, however many levels are needed, but that
bloats the trace in this email. :)

So, I've probably misunderstood something....

/~\ The ASCII                           der Mouse
\ / Ribbon Campaign
 X  Against HTML               mouse%rodents.montreal.qc.ca@localhost
/ \ Email!           7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B