Re: on issues of recursive monitoring and races therein

[Robert Love <rml novell com>]

On Mon, 2004-10-04 at 00:48 -0400, Robert Love wrote:

> A proof is left as an exercise to the reader.

Proof.

For the sake of contradiction, assume not.  Namely, assume that a system
using the Love-Trowbridge algorithm has a directory, call it bar, such
that bar is not monitored by Beagle but is a child of a recursively
monitored path.

Assume bar is at any arbitrary location in the file system, call it
foo/baz/bar.  Then bar was either (i) created before scanning began or
(ii) created after scanning began.

Case (i) is trivially impossible since if bar existed in the tree prior
to the scan, it would of been read by a directory read in Step 3.

If case (ii), then foo was either (a) created prior to the scanning
reaching a depth of baz or (b) created after the scanning reached a
depth of baz. (Without trivializing the problem, we can assume that
there is no "concurrent" creation and consider that case along with case
(b)).

Case (a) is trivially impossible since the directory read in Step 3
would yield bar.

In case (b), a watch on baz has already been created, since by
definition we have already reached a depth of baz (if one contends that
perhaps a watch, for whatever reason, has not yet been created, then
case (a) eventually holds).  But then the creation of bar results in a
CREATE_SUBDIR event on baz with filename=bar and a watch can be added.
So this case is also impossible.

This exhausts all possible cases.  It is impossible for there to be
neither a watch on a directory's parent directory and also to have a
readdir() on a directory's parent not yield said directory.

Consequently, in a system using Love-Trowbridge, there exists no
unwatched directory within a recursively monitored tree. ■