on issues of recursive monitoring and races therein



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





[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]