on issues of recursive monitoring and races therein

Robert Love <rml novell com> · Mon, 04 Oct 2004 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 