on issues of recursive monitoring and races therein

Robert Love <rml novell com> · 2004年10月04日 00:48:09 -0400

Trow, et al.
Been thinking about eliminating the risk of races with recursive
monitoring in Beagle.
I have now convinced myself that current inotify behavior is capable of
providing sufficient synchronization to prevent any races during the
initial recursive scan of a directory tree--that is, a scan from /foo on
down can always complete without missing any directories.
It is all in the ordering that Beagle should employ in the initial
scanning.
I humbly present the Love-Trowbridge (Lovebridge?) recursive directory
scanning algorithm:
 Step 1. Start at initial directory foo. Add watch.

 Step 2. Setup handlers for watch created in Step 1.
 Specifically, ensure that a directory created
 in foo will result in a handled CREATE_SUBDIR
 event.

 Step 3. Read the contents of foo.

 Step 4. For each subdirectory of foo read in step 3, repeat
 step 1.

 Step 5. For any CREATE_SUBDIR event on bar, if a watch is
 not yet created on bar, repeat step 1 on bar.
This will add a watch to foo and all of its children. Any newly created
directories should be caught in Step 5 and added, preventing any race.
The key is the ordering of Step 1 & 2 versus Step 3. Reading the
contents of the directory _after_ we add the watch assures that any
newly created directory is caught in Step 5.
For reasons of performance, one would want to implement Step 4 so as to
perform a breadth-first traversal of the directory tree.
A proof is left as an exercise to the reader.
Please show me my flawed logic.
Best,
	Robert Love