lock free dirstate

[Robert Collins]

On Mon, 2009-09-28 at 08:57 -0500, John Arbash Meinel wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Robert Collins wrote:
> > I plan to do an experiment this week on an OSLock free dirstate - this
> > should work more robustly on NFS, AFP etc. I've tagged the bugs that
> > stood out as being fixed by this as 'dirstate2' in launchpad.
> > 
> > The design I plan to use is the one that I've spoken about before:
> >  - write a collection of dirstate files named by hash (like we do
> > in .bzr/repository)
> >  - have old dirstate files attempt to rm but handle them being open by
> > other processes by leaving them behind
> >  - have a near-atomic pointer file in the root that is updated by the
> > standard foo.tmp, mv foo foo.old, mv foo.tmp foo, rm foo.old code
> 
> ^- Presumably you don't need to 'mv foo foo.old' on POSIX platforms?

Actually you do - the mv gives you a choke point to differentiate
between 'stat cache write' and 'real write', and let the stat cache
writer rollback. More details:

+class IndirectedDirState(AbstractDirState):
+    """DirState implemented using an indirection pointer and hash-named files.
+
+    Unlike DirState, IndirectedDirState is nearly atomic on the file system.
+    The base name of the dirstate specifies a directory containing a 'current'
+    file, and many content files named with their hash. Updates to
+    IndirectedDirState are very robust and do not lock out other readers.
+
+    Disk layout
+    -----------
+    basepath/
+      format = "bzr IndirectDirstate 1"
+      current = "MD5hash...\n". If missing then there will be one HASH.old
+        file which has the value current had if the read had started earlier,
+        and may be used.
+      MD5HASH.old = temp file used while replacing current. May only ever be
+        one - it is created by renaming current.
+      MD5HASH = a dirstate state file
+      MD5HASH.current = a candidate replacement for current, about to be
+        moved into place.
+
+    The 'current' file contains a hash which is the current actual dirstate
+    to read. Updates have two forms - stat cache updates (when a logical
+    read lock is in place), and semantic updates - when a write lock is in 
+    place. Updates write a new current file '$hash.current', move the 'current'
+    file to '$hash.old', and then move '$hash.current' to 'current', finally
+    removing '$hash.old'. If the Update is a stat cache update, a check is
+    done after moving 'current' to '$hash.old' - if the old hash is not the
+    hash that was meant to be replaced, then some other task has updated the
+    dirstate (and may have done more than a stat cache update). When this is
+    detected, '$hash.old' is moved back to 'current', and the stat cache
+    update discarded. Updaters are not permitted to write directly to 'current'
+    or to rename a '$hash.current' file to 'current' unless they currently
+    have '$hash.old'.
+    After successfully updating 'current', the old state contained in the
+    content file named in '$hash.old' should be removed. If the removal
+    errors due to other processing holding the file open, the errors can be
+    removed.
+    Finally, when closing a dirstate state file, 'current' should be checked,
+    and if it is different to the dirstate file that was read initially, an
+    attempt to remove that dirstate file should be made - last one out close
+    the doors.
+
+    When reading an IndirectedDirState, check for a format file to determine
+    if the dirstate is a known format. If there is no current file, it is
+    either in-progress or an interrupted update has occured. Readers should
+    look for *.old to get the last-written dirstate, and read that instead.
+    Concurrency concerns here mean that by the time .old is processed current
+    may have been updated and the old state file removed, so a short loop is
+    recommended. 
+    """

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20090929/c22c2bd3/attachment.pgp