Re: [PATCH 19/29] refs: don't dereference on rename

Michael Haggerty [off-list ref] writes:

quoted

Could you explain s/sha1/NULL/ here in the proposed log message?

Good question.

Passing sha1 to delete_ref() doesn't add any safety, because the same
sha1 was just read a moment before, and it is not used for anything
else.

"... and it is guaranteed that no other process in the meantime
wanted to update the ref we are trying to delete because it wants to
see the ref with its updated value." is something I expected to see
at the end.

So the check only protects us from a concurrent update to
newrefname between the call to read_ref_full() and the call to
delete_ref(). But such a race is indistinguishable from the case that a
modification to newrefname happens just before the call to
read_ref_full(), which would have the same outcome as the new code.

In other words, when a transaction that contains a deletion of a ref
races with another one that updates the ref, the latter transaction
may come after the former one, but the ref may not survive in the
end result and can be left deleted?

Puzzled...

On 04/29/2016 10:53 AM, Junio C Hamano wrote:

Michael Haggerty [off-list ref] writes:

quoted

quoted

Could you explain s/sha1/NULL/ here in the proposed log message?

Good question.

Passing sha1 to delete_ref() doesn't add any safety, because the same
sha1 was just read a moment before, and it is not used for anything
else.

"... and it is guaranteed that no other process in the meantime
wanted to update the ref we are trying to delete because it wants to
see the ref with its updated value." is something I expected to see
at the end.

quoted

So the check only protects us from a concurrent update to
newrefname between the call to read_ref_full() and the call to
delete_ref(). But such a race is indistinguishable from the case that a
modification to newrefname happens just before the call to
read_ref_full(), which would have the same outcome as the new code.

In other words, when a transaction that contains a deletion of a ref
races with another one that updates the ref, the latter transaction
may come after the former one, but the ref may not survive in the
end result and can be left deleted?

Puzzled...

Remember, we're talking about rename_ref() only, not reference deletion
in general. rename_ref() is not very robust anyway--it doesn't happen in
a single transaction, and it is vulnerable to being defeated by
simultaneous reference updates by other processes. It *does* wrap the
deletion of newrefname in a transaction; the only question is whether an
old_sha1 is supplied to that transaction.

So, suppose that newrefname starts at value A, and there are two updates
running simultaneously:

1. An update of reference newrefname from A -> B

2. A rename of reference oldrefname to newrefname, which includes
   a. read_ref_full("newrefname") and
   b. delete_ref("newrefname").

It is not possible for (1) to happen after (2b) because the former's
check of the old value of newrefname would fail. So there are two
possible interleavings:

* 1, 2a, 2b
* 2a, 1, 2b

With the new code, both of these interleavings end up with newrefname
deleted.

With the old code, the second interleaving would fail.

But the only difference is the relative order of the read-only operation
(2a), whose SHA-1 result is never used. So neither process actually
cares which of those two interleavings occurred, and it is legitimate to
treat them the same.

Note that the first transaction *did* successfully set newrefname to
value B in both cases and indeed knows for sure that the update was
successful. It's just that newrefname was deleted immediately afterwards.

Michael

On Fri, Apr 29, 2016 at 12:57:29PM +0200, Michael Haggerty wrote:

Remember, we're talking about rename_ref() only, not reference deletion
in general. rename_ref() is not very robust anyway--it doesn't happen in
a single transaction, and it is vulnerable to being defeated by
simultaneous reference updates by other processes. It *does* wrap the
deletion of newrefname in a transaction; the only question is whether an
old_sha1 is supplied to that transaction.

So, suppose that newrefname starts at value A, and there are two updates
running simultaneously:

1. An update of reference newrefname from A -> B

2. A rename of reference oldrefname to newrefname, which includes
   a. read_ref_full("newrefname") and
   b. delete_ref("newrefname").

I wondered at first if you meant "oldrefname" in 2b. That is, a rename
would involve writing to "newrefname" and then deleting "oldrefname",
and not doing the old_sha1 and normal locking on the deletion of
oldrefname would be bad (in case somebody else updated it while we were
operating).

But reading the patch again, that's not what's going on. You're talking
just about the case where we force-overwrite an existing newrefname, and
delete it first to do so. But what I don't understand is:

  1. Why do we read_ref_full() at all? Since it is not done under lock
     anyway, it is useless for helping with race conditions, and I think
     that is what you are arguing (that we should just be deleting
     regardless). But then why not just call delete_ref(), and handle
     the ENOENT case as a noop (which closes another race if somebody
     deletes it between your 2a and 2b).

  2. Why delete it at all? The point is to overwrite, so I guess it is
     trying to make room. But we could just rename the loose ref file
     and reflog overtop the old, couldn't we?

Or am I totally misreading the purpose of this code?

-Peff

On 04/29/2016 02:12 PM, Jeff King wrote:

On Fri, Apr 29, 2016 at 12:57:29PM +0200, Michael Haggerty wrote:

quoted

Remember, we're talking about rename_ref() only, not reference deletion
in general. rename_ref() is not very robust anyway--it doesn't happen in
a single transaction, and it is vulnerable to being defeated by
simultaneous reference updates by other processes. It *does* wrap the
deletion of newrefname in a transaction; the only question is whether an
old_sha1 is supplied to that transaction.

So, suppose that newrefname starts at value A, and there are two updates
running simultaneously:

1. An update of reference newrefname from A -> B

2. A rename of reference oldrefname to newrefname, which includes
   a. read_ref_full("newrefname") and
   b. delete_ref("newrefname").

I wondered at first if you meant "oldrefname" in 2b. That is, a rename
would involve writing to "newrefname" and then deleting "oldrefname",
and not doing the old_sha1 and normal locking on the deletion of
oldrefname would be bad (in case somebody else updated it while we were
operating).

But reading the patch again, that's not what's going on. You're talking
just about the case where we force-overwrite an existing newrefname, and
delete it first to do so. But what I don't understand is:

It's beyond the ambition of this patch to fix this old rename_ref()
code, but...

  1. Why do we read_ref_full() at all? Since it is not done under lock
     anyway, it is useless for helping with race conditions, and I think
     that is what you are arguing (that we should just be deleting
     regardless). But then why not just call delete_ref(), and handle
     the ENOENT case as a noop (which closes another race if somebody
     deletes it between your 2a and 2b).

I thought about that too, and agree it would be an improvement. But it's
not quite so trivial. The ENOENT doesn't make it out of delete_ref()
(which does a full-fledged ref_transaction internally). The error is
only reported via "strbuf *err".

  2. Why delete it at all? The point is to overwrite, so I guess it is
     trying to make room. But we could just rename the loose ref file
     and reflog overtop the old, couldn't we?

Or am I totally misreading the purpose of this code?

I wouldn't want to just rename the files, because (1) I think it is
better to use the existing ref_transaction code, and (2) that wouldn't
work if there is a D/F conflict between the old and new reference names,
which the existing code handles (though honestly I'm skeptical that it
comes up a lot).

It would be more plausible to use ref_transaction_update() to write
oldrefname's *value* on top of newrefname without actually moving the
file. oldrefname could even be deleted in the same transaction, if you
were willing to stop supporting old/new refnames that D/F conflict with
each other. But we also want to move the reflog, and that should be done
while the newrefname lock and (contrary to the current code) also the
oldrefname lock are held. There's currently no way to slip an arbitrary
action like that into the middle of a transaction.

If I had lots of time and interest to work on this, I think the best
approach would be to add a ref_transaction_rename(), which takes an old
and a new reference name as arguments, and adds a whole rename operation
(including of the reflog) to a transaction. This could probably be
implemented by adding one ref_update() and one ref_delete(), and using
the parent_update pointer that is introduced later to link the two so
that ref_transaction_commit() knows to move the reflog too.

If you were willing to punt on D/F conflicts, you would be done. If not,
then it would be better to teach ref_transaction_commit() to deal with
D/F conflicts in the general case rather than using special-purpose code
in rename_ref().

Then rename_ref() could be omitted from the vtable entirely.

Michael

On Fri, Apr 29, 2016 at 03:55:00PM +0200, Michael Haggerty wrote:

It's beyond the ambition of this patch to fix this old rename_ref()
code, but...
[...]

Thanks for the explanation. That all makes sense to me, and I can
definitely live with "historical warts that aren't worth touching in
this series" as the verdict.

-Peff