Re: OfflineImap 3.0

[John Goerzen <jgoerzen@xxxxxxxxxxxx>]

dLux,

Your algorithm is not entirely race-proof either.  To wit:

On Mon, Jul 15, 2002 at 07:21:50PM +0200, dLux wrote:

> | gets marked answered, treashed, or whatnot).  We can try to reduce the
> | window for a race to occur but cannot ever completely eliminate it.  Though

> My algorithm works the following way (one-way algorithm):
> 
> - Generates a file-list in the source directory (it is analogue to your
>   IMAP-folder browsing).
> - Then compare the mail-list with the stored one and calculate the
>   differences. The result will be 3 different list:
>   - New files
>   - Renamed or moved files
>   - Deleted files

This is very simimlar to the way OfflineIMAP uses the LocalStatus, although
OfflineIMAP achieves a bidirectional sync.

> - We store the three different transaction list to disk, if the following
>   steps fail, we can restart them later.

Why bother?  Couldn't you just restart the sync?

> - We store the filelist which is generated at the first step, this list
>   will be used in the next run in the second step.
> - Try to copy the new files into the other side. If it fails because the
>   source file is not found, then it means that someone renamed or
>   deleted the file. We don't care it, because it will be synchronized in
>   the next run. If the file already exists in the target place, then we
>   don't do copying.

You've still got a race unless both filesystems are local.  In that case,
you can use open with O_EXCL to force failure to open if the target exists. 
This behavior is not reliable across NFS or a network, however.  And if both
filesystems are local, why not use cp -r?

> - Try to delete the deleted files in the other side. If it fails, then
>   we find a similar email with different flags and remove that (although
>   I am not 100% sure that we want to do it). If we can't find the file
>   to delete, we ignore it.

This "finding" process also involves a race condition.  Between the time you
call opendir()/readdir() until the time you call unlink() there is time for
another process to unlink it first.  This is a race condition also present
in OfflineIMAP.  I don't think there is any way at all to deal with it; we
can minimize the effects by pushing the responsibility onto the next sync.

> - Try to rename the file in the other side too. If it fails, then we
>   simply ignore it.
> - We remove the transaction list.
> 
> This is a ONE-WAY sync, but it can be repeated simply by replacing the
> source and the target.

If by "repeated" you mean "used to sync mail bidirectionally", no, that is
not correct.  If new mail arrives at both folders between a sync, you will
LOSE (yes, lose) mail at one end or the other

> As you can see, the two phases can be completely different. If you do
> this algorithm with proper Maildir handling (new files are created in
> the "tmp" directory, then moved into the "cur" if it arrived fully).

OfflineIMAP already implements proper Maildir handling.  That is not really
an issue, though.

> There is no potential race condition if you do the algorithm like this,
> at least it does not cause data loss or improper behaviour.

There are race conditions (see above).  OfflineIMAP has had zero bugs since
version 1.0.0 that have caused data loss for anyone; please don't imply
otherwise.  In fact, OfflineIMAP is doing the same as what you suggest
(defering actions till the next sync when races creep up) in many instances,
so I'm not sure what the problem here is :-)

> == Whip me. Beat me. Make me maintain AIX ==

Yeow :-)

-- 
John Goerzen <jgoerzen@xxxxxxxxxxxx>    GPG: 0x8A1D9A1F    www.complete.org