lock free dirstate - prototype

[Martin Pool]

2009/9/29 Robert Collins <robertc at robertcollins.net>:
> On Tue, 2009-09-29 at 14:25 +0100, Martin Pool wrote:
>
>> Creating and manipulating directories is reportedly pretty slow on
>> Windows (and maybe other places) so it would be worth avoiding any
>> unnecessary lockdir-type io.  I'd rather look at taking any useful
>> features from lockdir into the core format of this.  For instance,
>> it's probably not safe to rely on any particular behaviour for
>> rename('newfile', 'file') but you can do a directory-renaming dance.
>
> Yup, thats why I haven't so far.
>
>> However, presumably we do need a semantic wt lock - how would that fit in?
>
> The semantic lock is still needed, and for CLI use we aim for one
> lock-unlock regardless. We can't reuse that for stat cache updates
> trivially [layers] but we could look at taking that separate lock out as
> a way to do locking on the dirstate contents when doing mutations. That
> would completely preclude mutating when someone has a write lock [not a
> bad thing :P] but would also lead to write operations like 'commit'
> being potentially blocked by 'bzr st', if we managed the lock lifetime
> wrongly. Its worth thinking about : the hard work is done (refactoring
> dirstate to use multiple files).
>
>> >  - how to deal with two writers with the same new content / ABA state
>> > transitions combining with slow-readers that delete what they think is
>> > unlinked content, but actually has been relinked. I'm thinking that slow
>> > readers need to acquire the current file ownership before they unlink
>> > anything.  Two writers with the same new content is harder; one will win
>> > renaming current, and one rolling back will delete the others content. I
>> > think we need some randomness/uniqueness in either the filename or the
>> > content. (e.g. put a pid in there).
>>
>> I'm not sure I understand.  I don't think readers should unlink files
>> - do they really need to.  And won't simultaneously writers be blocked
>> out by the exclusive semantic lock?
>
> Unlinking of files - on win32 a reader prevents unlinking of a file that
> its reading. That means we have to unlink at some arbitrary later time
> than the point where the file stopped being logically interesting.

I think accumulating a bounded amount of garbage until the next
semantic write would be ok.  Except in very contrived circumstances
this should be just one copy of the state, and even then it won't
happen every time.

> concurrent writers: semantic writers and mutexed out by the tree write
> lock. stat cache updaters are not, but their changes are discarded if a
> semantic writer has an update. So if you run 'bzr st' twice, at the same
> time, you'll have two stat cache updaters, each with the same new
> dirstate. You could have one semantic writer and one stat cache updater
> with the same changes. Anyhow, assuming two stat cache updaters:
> They then both write
> 12345
> 12345.current
> they both attempt
> mv current 12345.check
> writer A wins, and may go on to complete the transaction, or may
> rollback if a semantic update had occured [busy system hey :)]
> writer B loses and may either spinlock or rollback(because its only a
> stat cache update)
>
> What happens next is the problem. If A inserts 12345 (by renaming
> 12345.current -> current) and B rollsback, B will remove 12345 and
> 12345.current. Now, today in my code B doesn't rollback, it just queues
> to complete and then when it acquires current it finds that
> 12345.current is missing and will error out without taking further
> actions. This will leave the system needing recovery, but its still well
> defined.
>
> I'd like to avoid these conditions altogether.
>
>> >> Does this write a whole new copy on each update, or incremental files?
>> >
>> > Full copy. Theres a bug of stuff we /can/ do in a new tree format; I've
>> > picked a single conceptual bug which has many ramifications and tried to
>> > solve that. Some other ones I've not put any coding effort into are:
>> >  - write less on partial updates
>> >  - only store the left most parent
>> >  - persist an id2path map
>>
>> and, for me, getting away from any need to write on logical read
>> operations would be great.
>
> We can do that if we stop using a stat cache, but doing so seems to
> imply that 'touch iso; bzr st; bzr st' will be a very slow process the
> second time.

.. assuming that the iso is added and otherwise unchanged.

It seems like a somewhat contrived case.  I guess we don't want to be
any slower than we have to be, even for cases which seem unlikely, but
on the other hand keeping the hashcache up to date really does have a
performance cost, and writing from logical reads is a source of bugs
or complexity.

It also tends to make us do more work than we have to for operations like

  echo foo >>iso
  bzr st
  echo bar >>iso
  bzr st

This particular case may have been squashed, but the hashcache
approach makes it likely we'll read and hash the whole file, and write
the whole dirstate, on each operation, quite unnecessarily.  To me
this is much more common than just touching a dirstate file.

-- 
Martin <http://launchpad.net/~mbp/>