{"thread":{"id":"32426","subject":"[PATCH] refs: do not use cached refs in repack_without_ref","startedAt":"2012-12-21T08:04:49Z","lastAt":"2013-01-22T04:31:03Z","messageCount":23,"participants":["Jeff King","Michael Haggerty","Martin Fick","Junio C Hamano","Pyeron, Jason J CTR (US)","Drew Northup"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"205319","messageId":"20121221080449.GA21741@sigill.intra.peff.net","threadId":"32426","inReplyTo":null,"subject":"[PATCH] refs: do not use cached refs in repack_without_ref","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-21T08:04:49Z","receivedAt":"2012-12-21T08:04:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we delete a ref that is packed, we rewrite the whole\npacked-refs file and simply omit the ref that no longer\nexists. However, we base the rewrite on whatever happens to\nbe in our refs cache, not what is necessarily on disk. That\nopens us up to a race condition if another process is\nsimultaneously packing the refs, as we will overwrite their\nnewly-made pack-refs file with our potentially stale data,\nlosing commits.\n\nYou can demonstrate the race like this:\n\n  # setup some repositories\n  git init --bare parent &&\n  (cd parent && git config core.logallrefupdates true) &&\n  git clone parent child &&\n  (cd child && git commit --allow-empty -m base)\n\n  # in one terminal, repack the refs repeatedly\n  cd parent &&\n  while true; do\n\tgit pack-refs --all\n  done\n\n  # in another terminal, simultaneously push updates to\n  # master, and create and delete an unrelated ref\n  cd child &&\n  while true; do\n\tgit push origin HEAD:newbranch &&\n\tgit commit --allow-empty -m foo\n\tus=`git rev-parse master` &&\n\tgit push origin master &&\n\tgit push origin :newbranch &&\n\tthem=`git --git-dir=../parent rev-parse master` &&\n\tif test \"$them\" != \"$us\"; then\n\t\techo >&2 \"$them\" != \"$us\"\n\t\texit 1\n\tfi\n  done\n\nIn many cases the two processes will conflict over locking\nthe packed-refs file, and the deletion of newbranch will\nsimply fail.  But eventually you will hit the race, which\nhappens like this:\n\n  1. We push a new commit to master. It is already packed\n     (from the looping pack-refs call). We write the new\n     value (let us call it B) to $GIT_DIR/refs/heads/master,\n     but the old value (call it A) remains in the\n     packed-refs file.\n\n  2. We push the deletion of newbranch, spawning a\n     receive-pack process. Receive-pack advertises all refs\n     to the client, causing it to iterate over each ref; it\n     caches the packed refs in memory, which points at the\n     stale value A.\n\n  3. Meanwhile, a separate pack-refs process is running. It\n     runs to completion, updating the packed-refs file to\n     point master at B, and deleting $GIT_DIR/refs/heads/master\n     which also pointed at B.\n\n  4. Back in the receive-pack process, we get the\n     instruction to delete :newbranch. We take a lock on\n     packed-refs (which works, as the other pack-refs\n     process has already finished). We then rewrite the\n     contents using the cached refs, which contain the stale\n     value A.\n\nThe resulting packed-refs file points master once again at\nA. The loose ref which would override it to point at B was\ndeleted (rightfully) in step 3. As a result, master now\npoints at A. The only trace that B ever existed in the\nparent is in the reflog: the final entry will show master\nmoving from A to B, even though the ref still points at A\n(so you can detect this race after the fact, because the\nnext reflog entry will move from A to C).\n\nWe can fix this by invalidating the packed-refs cache after\nwe have taken the lock. This means that we will re-read the\npacked-refs file, and since we have the lock, we will be\nsure that what we read will be atomically up-to-date when we\nwrite (it may be out of date with respect to loose refs, but\nthat is OK, as loose refs take precedence).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nWe actually see this in practice on GitHub, though it is relatively\nrare (I've been chasing reports for a while, and in a very busy repo, it\ncan happen every couple of weeks; this is probably due to the fact that\nwe run \"git gc\" very frequently).\n\nThere are a few other interesting races in this code that this does not\nfix:\n\n  1. We check to see whether the ref is packed based on the cached data.\n     That means that in the following sequence:\n\n       a. receive-pack starts, caches packed refs; master is not packed\n\n       b. meanwhile, pack-refs runs and packs master\n\n       c. receive-pack deletes the loose ref for master (which might be\n          a no-op if the pack-refs from (b) got there first). It checks\n          its cached packed-refs and sees that there is nothing to\n          delete.\n\n     We end up leaving the entry in packed-refs. In other words, the\n     deletion does not actually delete anything, but it still returns\n     success.\n\n     We could fix this by scanning the list of packed refs only after\n     we've acquired the lock. The downside is that this would increase\n     lock contention on packed-refs.lock. Right now, two deletions may\n     conflict if they are deletions of packed refs. With this change,\n     any two deletions might conflict, packed or not.\n\n     If we work under the assumption that deletions are relatively rare,\n     this is probably OK. And if you tend to keep your refs packed, it\n     would not make any difference. It would have an impact on repos\n     which do not pack refs, and which have frequent simultaneous\n     deletions.\n\n  2. The delete_ref function first deletes the loose ref, then rewrites\n     the packed-refs file. This means that for a moment, the ref may\n     appear to have rewound to whatever was in the packed-refs file, and\n     the reader has no way of knowing.\n\n     This is not a huge deal, but I think it could be fixed by swapping\n     the ordering. However, I think that would open us up to the reverse\n     race from above: we delete from packed-refs, then before we delete\n     the loose ref, a pack-refs process repacks it. Our deletion looks\n     successful, but the ref remains afterwards.\n\nI fixed just the race I did because it does not (as far as I can tell)\nhave any downsides. And it is way more severe (the other ones are \"a\ndeleted ref might come back\", whereas the fixed one will actually lose\ncommits).\n\n refs.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git a/refs.c b/refs.c\nindex 6cec1c8..541fec2 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1744,7 +1744,8 @@ static int repack_without_ref(const char *refname)\n static int repack_without_ref(const char *refname)\n {\n \tstruct repack_without_ref_sb data;\n-\tstruct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));\n+\tstruct ref_cache *refs = get_ref_cache(NULL);\n+\tstruct ref_dir *packed = get_packed_refs(refs);\n \tif (find_ref(packed, refname) == NULL)\n \t\treturn 0;\n \tdata.refname = refname;\n@@ -1753,6 +1754,8 @@ static int repack_without_ref(const char *refname)\n \t\tunable_to_lock_error(git_path(\"packed-refs\"), errno);\n \t\treturn error(\"cannot delete '%s' from packed refs\", refname);\n \t}\n+\tclear_packed_ref_cache(refs);\n+\tpacked = get_packed_refs(refs);\n \tdo_for_each_ref_in_dir(packed, 0, \"\", repack_without_ref_fn, 0, 0, &data);\n \treturn commit_lock_file(&packlock);\n }\n-- \n1.8.1.rc2.6.g05591da\n"},{"id":"205490","messageId":"50DAB447.8000101@alum.mit.edu","threadId":"32426","inReplyTo":"20121221080449.GA21741@sigill.intra.peff.net","subject":"Re: [PATCH] refs: do not use cached refs in repack_without_ref","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-12-26T08:24:39Z","receivedAt":"2012-12-26T08:24:39Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 12/21/2012 09:04 AM, Jeff King wrote:\n> When we delete a ref that is packed, we rewrite the whole\n> packed-refs file and simply omit the ref that no longer\n> exists. However, we base the rewrite on whatever happens to\n> be in our refs cache, not what is necessarily on disk. That\n> opens us up to a race condition if another process is\n> simultaneously packing the refs, as we will overwrite their\n> newly-made pack-refs file with our potentially stale data,\n> losing commits.\n> [...]\n> \n> There are a few other interesting races in this code that this does not\n> fix:\n> \n>   1. We check to see whether the ref is packed based on the cached data.\n>      That means that in the following sequence:\n> \n>        a. receive-pack starts, caches packed refs; master is not packed\n> \n>        b. meanwhile, pack-refs runs and packs master\n> \n>        c. receive-pack deletes the loose ref for master (which might be\n>           a no-op if the pack-refs from (b) got there first). It checks\n>           its cached packed-refs and sees that there is nothing to\n>           delete.\n> \n>      We end up leaving the entry in packed-refs. In other words, the\n>      deletion does not actually delete anything, but it still returns\n>      success.\n> \n>      We could fix this by scanning the list of packed refs only after\n>      we've acquired the lock. The downside is that this would increase\n>      lock contention on packed-refs.lock. Right now, two deletions may\n>      conflict if they are deletions of packed refs. With this change,\n>      any two deletions might conflict, packed or not.\n> \n>      If we work under the assumption that deletions are relatively rare,\n>      this is probably OK. And if you tend to keep your refs packed, it\n>      would not make any difference. It would have an impact on repos\n>      which do not pack refs, and which have frequent simultaneous\n>      deletions.\n> \n>   2. The delete_ref function first deletes the loose ref, then rewrites\n>      the packed-refs file. This means that for a moment, the ref may\n>      appear to have rewound to whatever was in the packed-refs file, and\n>      the reader has no way of knowing.\n> \n>      This is not a huge deal, but I think it could be fixed by swapping\n>      the ordering. However, I think that would open us up to the reverse\n>      race from above: we delete from packed-refs, then before we delete\n>      the loose ref, a pack-refs process repacks it. Our deletion looks\n>      successful, but the ref remains afterwards.\n\nI'm sorry to take so long to respond to this patch.  Thank you for\ntracking down this bug and for your careful analysis.\n\nI think your patch is correct and should fix the first race condition\nthat you described.  But I think the continued existence of the other\nrace conditions is an indication of a fundamental problem with the\nreference locking policy--independent of the in-RAM reference cache.\n\nThe tacit assumption of the current locking policy is that changes to\nthe packed-refs file are not critical for correctness, because loose\nreferences take precedence over it anyway.  This is true for adding and\nmodifying references.  But it is not true for deleting references,\nbecause there is no way for a deletion to be represented as a loose\nreference in a way that takes precedence over the packed-refs file\n(i.e., there is no way for a loose reference to say \"I am deleted,\nregardless of what packed-refs says\").  Thus the race conditions for\ndeleting references, whether via delete_ref() or via pack_refs() with\n--prune.\n\nThe current algorithms for deleting references are:\n\n* Delete reference foo:\n\n  1. Acquire the lock $GIT_DIR/refs/heads/foo.lock\n\n  2. Unlink $GIT_DIR/refs/heads/foo\n\n  3. repack_without_ref():\n\n     a. Acquire the lock $GIT_DIR/packed-refs.lock\n\n     b. Write the packed-refs without the \"foo\" reference to\n        $GIT_DIR/packed-refs.lock\n\n     c. Rename $GIT_DIR/packed-refs.lock to $GIT_DIR/packed-refs\n\n  4. Release lock $GIT_DIR/refs/heads/foo.lock\n\n* Pack references:\n\n  1. Acquire lock $GIT_DIR/packed-refs.lock\n\n  2. for_each_ref() call handle_one_ref():\n\n     a. Write ref and its SHA1 to $GIT_DIR/packed-refs.lock\n\n     b. Possibly record ref and its SHA1 in the refs_to_prune list.\n\n  3. Commit $GIT_DIR/packed-refs\n\n  4. prune_refs(): for each ref in the ref_to_prune list, call\n     prune_ref():\n\n     a. Lock the reference using lock_ref_sha1(), verifying that the\n        recorded SHA1 is still valid.  If it is, unlink the loose\n        reference file then free the lock; otherwise leave the loose\n        reference file untouched.\n\nThere is a problem if two processes try to delete a reference at the\nsame time, or if one process tries to delete a reference at the same\ntime as another process is trying to pack the references.  The reason is\nthat there is no \"transaction\" that spans both the rewriting of the\npacked-refs file and also the deletion of the loose-ref files, and\ntherefore it is possible for conflicting changes to be made in the two\nlocations.\n\nI think that all of the problems would be fixed if a lock would be held\non the packed-refs file during the whole process of deleting any\nreference; i.e., change the algorithms to:\n\n* Delete reference foo:\n\n  1. Acquire the lock $GIT_DIR/packed-refs.lock (regardless of whether\n     \"foo\" is a packed ref)\n\n  2. Write to $GIT_DIR/packed-refs.new a version of the packed-refs\n     file that omits \"foo\"\n\n  3. Atomically replace $GIT_DIR/packed-refs with\n     $GIT_DIR/packed-refs.new (but without relinquishing the lock\n     $GIT_DIR/packed-refs.lock)\n\n  4. Delete loose ref for \"foo\":\n\n     a. Acquire the lock $GIT_DIR/refs/heads/foo.lock\n\n     b. Unlink $GIT_DIR/refs/heads/foo if it is unchanged.  If it is\n        changed, leave it untouched.  If it is deleted, that is OK too.\n\n     c. Release lock $GIT_DIR/refs/heads/foo.lock\n\n  5. Release lock $GIT_DIR/packed-refs.lock (without changing\n     $GIT_DIR/packed-refs again)\n\n* Pack references:\n\n  1. Acquire lock $GIT_DIR/packed-refs.lock\n\n  2. for_each_ref() call handle_one_ref():\n\n     a. Write ref and its SHA1 to $GIT_DIR/packed-refs.new\n\n     b. Possibly record ref and its SHA1 in the refs_to_prune list.\n\n  3. Atomically replace $GIT_DIR/packed-refs with\n     $GIT_DIR/packed-refs.new (but without relinquishing the lock\n     $GIT_DIR/packed-refs.lock)\n\n  4. prune_refs(): for each ref in the ref_to_prune list, call\n     prune_ref():\n\n     a. Lock the loose reference using lock_ref_sha1(), verifying that\n        the recorded SHA1 is still valid\n\n     b. If it is, unlink the loose reference file (otherwise, leave\n        it untouched)\n\n     c. Release the lock on the loose reference\n\n  5. Release lock $GIT_DIR/packed-refs.lock (without changing\n     $GIT_DIR/packed-refs again)\n\nIt is important that after step (3) in either of the above algorithms,\nthe new packed-refs file has been switched \"live\" even though there is\nno way to guarantee that it holds the correct values for all references.\n This is OK, because (a) references that have been added or changed will\nbe represented by loose references that take precedence over the stale\nreferences in the packed-refs file; (b) no references can have been\ndeleted while the packed-refs file was being rewritten, because\nreference deletion is serialized via the lock on the packed-refs file.\nIf one of the later steps fails, it is OK to leave this version of the\npacked-refs file active.\n\nThe proposed algorithms will have to hold the lock on packed-refs for\nmuch longer; in the case of packed-refs, the lock has to be held for the\nwhole time that all of the loose references are being deleted.\nEffectively it is being used to prevent other processes from deleting\nreferences while it is working because that would make the just-written\npacked-refs file invalid.\n\nI would appreciate a critique of my analysis.  Even if you agree, I\nthink it would be OK to apply Peff's patch to fix up the most pressing\nproblem, then implement the more complete solution later.\n\nBy the way, this is something that I would be happy to add to my to-do\nlist, but it could take a while for me to get to it because of a lack of\ntime and because I'm still busy with two other biggish git-related\nprojects (git-multimail [1] and a git merging helper [2]).\n\nMichael\n\n[1] https://github.com/mhagger/git-multimail\n\n[2] A fun project that I haven't yet mentioned on the list\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"205567","messageId":"201212271611.52203.mfick@codeaurora.org","threadId":"32426","inReplyTo":"50DAB447.8000101@alum.mit.edu","subject":"Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-12-27T23:11:51Z","receivedAt":"2012-12-27T23:11:51Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Wednesday, December 26, 2012 01:24:39 am Michael Haggerty \nwrote:\n> ... lots of discussion about ref locking...\n\nIt concerns me that git uses any locking at all, even for \nrefs since it has the potential to leave around stale locks. \n\nFor a single user repo this is not a big deal, the lock can \nalways be cleaned up manually (and it is a rare occurrence).  \nHowever, in a multi user server environment, possibly even \nfrom multiple hosts over a shared filesystem such as NFS, \nstale locks could lead to serious downtime and risky recovery \n(since it is currently hard to figure out if a lock really is \nstale).  Even though stale locks are probably rare even today \nin the larger shared repo case, as git scales to even larger \nshared repositories, this will eventually become more of a \nproblem *1.  Naturally, this has me thinking that git should \npossibly consider moving towards a lockless design for refs \nin the long term.\n\nI realize this is hard and that git needs to support many \ndifferent filesystems with different semantics.  I had an idea I \nthink may be close to a functional lockless design for loose \nrefs (one piece at a time) that I thought I should propose, \njust to get the ball rolling, even if it is just going to be \nfound to be flawed (I realize that history suggests that such \nschemes usually are).  I hope that it does not make use of \nany semantics which are not currently expected from git of \nfilesystems.  I think it relies only on the ability to rename \na file atomically, and the ability to scan the contents of a \ndirectory reliably to detect the \"ordered\" existence of files.\n\nMy idea is based on using filenames to store sha1s instead of \nfile contents.  To do this, the sha1 one of a ref would be \nstored in a file in a directory named after the loose ref.  I \nbelieve this would then make it possible to have lockless \natomic ref updates by renaming the file.\n\nTo more fully illustrate the idea, imagine that any file \n(except for the null file) in the directory will represent the \nvalue of the ref with its name, then the following \ntransitions can represent atomic state changes to a refs \nvalue and existence:\n\n1) To update the value from a known value to a new value \natomically, simply rename the file to the new value.  This \noperation should only succeed if the file exists and is still \nnamed old value before the rename.  This should even be \nfaster than today's approach, especially on remote filesystems \nsince it would require only 1 round trip in the success case \ninstead of 3!\n\n2) To delete the ref, simply delete the filename representing \nthe current value of the ref.  This ensures that you are \ndeleting the ref from a specific value.  I am not sure if git \nneeds to be able to delete refs without knowing their values?  \nIf so, this would require reading the value and looping until \nthe delete succeeds, this may be a bit slow for a constantly \nupdated ref, but likely a rare situation (and not likely \nworse than trying to acquire the ref-lock today).  Overall, \nthis again would likely be faster than today's approach.\n\n3) To create a ref, it must be renamed from the null file (sha \n0000...) to the new value just as if it were being updated \nfrom any other value, but there is one extra condition: \nbefore renaming the null file, a full directory scan must be \ndone to ensure that the null file is the only file in the \ndirectory (this condition exists because creating the \ndirectory and null file cannot be atomic unless the filesystem \nsupports atomic directory renames, an expectation git does \nnot currently make).  I am not sure how this compares to \ntoday's approach, but including the setup costs (described \nbelow), I suspect it is slower.\n\nWhile this outlines the state changes, some additional \noperations may be needed to setup some starting conditions \nand to clean things up. But these operations could/should be \nperformed by any process/thread and would not cause any state \nchanges to the ref existence or value.  For example, when \ncreating a ref, the ref directory would need to be created \nand the null file needs to be created.  Whenever a null file is \ndetected in the directory at the same time as another file, it \nshould be deleted.   Whenever the directory is empty, it may \nbe deleted (perhaps after a grace period to reduce retries \nduring ref creation unless the process just deleted the ref).\n\nI don't know how this new scheme could be made to work with \nthe current scheme, it seems like perhaps new git releases \ncould be made to understand both the old and the new, and a \nconfig option could be used to tell it which method to write \nnew refs with.  Since in this new scheme ref directory names \nwould conflict with old ref filenames, this would likely \nprevent both schemes from erroneously being used \nsimultaneously (so they shouldn't corrupt each other), except \nfor the fact that refs can be nested in directories which \nconfuses things a bit.  I am not sure what a good solution to \nthis is?\n\nWhat did I miss, where are my flaws?  Does anyone else share \nmy concern for stale locks?  How could we similarly eliminate \nlocks for the packed-refs file?\n\n-Martin\n\n\n*1 We have been concerned with stale locks in the Gerrit \ncommunity when trying to design atomic cross repository \nupdates.  Of course, while a lockless solution eliminates \nstale locks, it might make it impossible to do atomic cross \nrepository updates since all of our solutions so far need \nlocks. :(\n"},{"id":"205589","messageId":"201212280750.14695.mfick@codeaurora.org","threadId":"32426","inReplyTo":"201212271611.52203.mfick@codeaurora.org","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-12-28T14:50:14Z","receivedAt":"2012-12-28T14:50:14Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Thursday, December 27, 2012 04:11:51 pm Martin Fick wrote:\n> On Wednesday, December 26, 2012 01:24:39 am Michael\n> Haggerty\n> \n> wrote:\n> > ... lots of discussion about ref locking...\n> \n> It concerns me that git uses any locking at all, even for\n> refs since it has the potential to leave around stale\n> locks.\n> \n> For a single user repo this is not a big deal, the lock\n> can always be cleaned up manually (and it is a rare\n> occurrence). However, in a multi user server environment,\n> possibly even from multiple hosts over a shared\n> filesystem such as NFS, stale locks could lead to serious\n> downtime and risky recovery (since it is currently hard\n> to figure out if a lock really is stale).  Even though\n> stale locks are probably rare even today in the larger\n> shared repo case, as git scales to even larger shared\n> repositories, this will eventually become more of a\n> problem *1.  Naturally, this has me thinking that git\n> should possibly consider moving towards a lockless design\n> for refs in the long term.\n> \n> I realize this is hard and that git needs to support many\n> different filesystems with different semantics.  I had an\n> idea I think may be close to a functional lockless design\n> for loose refs (one piece at a time) that I thought I\n> should propose, just to get the ball rolling, even if it\n> is just going to be found to be flawed (I realize that\n> history suggests that such schemes usually are).  I hope\n> that it does not make use of any semantics which are not\n> currently expected from git of filesystems.  I think it\n> relies only on the ability to rename a file atomically,\n> and the ability to scan the contents of a directory\n> reliably to detect the \"ordered\" existence of files.\n> \n> My idea is based on using filenames to store sha1s instead\n> of file contents.  To do this, the sha1 one of a ref\n> would be stored in a file in a directory named after the\n> loose ref.  I believe this would then make it possible to\n> have lockless atomic ref updates by renaming the file.\n> \n> To more fully illustrate the idea, imagine that any file\n> (except for the null file) in the directory will represent\n> the value of the ref with its name, then the following\n> transitions can represent atomic state changes to a refs\n> value and existence:\n> \n> 1) To update the value from a known value to a new value\n> atomically, simply rename the file to the new value.  This\n> operation should only succeed if the file exists and is\n> still named old value before the rename.  This should\n> even be faster than today's approach, especially on\n> remote filesystems since it would require only 1 round\n> trip in the success case instead of 3!\n> \n> 2) To delete the ref, simply delete the filename\n> representing the current value of the ref.  This ensures\n> that you are deleting the ref from a specific value.  I\n> am not sure if git needs to be able to delete refs\n> without knowing their values? If so, this would require\n> reading the value and looping until the delete succeeds,\n> this may be a bit slow for a constantly updated ref, but\n> likely a rare situation (and not likely worse than trying\n> to acquire the ref-lock today).  Overall, this again\n> would likely be faster than today's approach.\n> \n> 3) To create a ref, it must be renamed from the null file\n> (sha 0000...) to the new value just as if it were being\n> updated from any other value, but there is one extra\n> condition: before renaming the null file, a full\n> directory scan must be done to ensure that the null file\n> is the only file in the directory (this condition exists\n> because creating the directory and null file cannot be\n> atomic unless the filesystem supports atomic directory\n> renames, an expectation git does not currently make).  I\n> am not sure how this compares to today's approach, but\n> including the setup costs (described below), I suspect it\n> is slower.\n> \n> While this outlines the state changes, some additional\n> operations may be needed to setup some starting conditions\n> and to clean things up. But these operations could/should\n> be performed by any process/thread and would not cause\n> any state changes to the ref existence or value.  For\n> example, when creating a ref, the ref directory would\n> need to be created and the null file needs to be created.\n>  Whenever a null file is detected in the directory at the\n> same time as another file, it should be deleted.  \n> Whenever the directory is empty, it may be deleted\n> (perhaps after a grace period to reduce retries during\n> ref creation unless the process just deleted the ref).\n> \n> I don't know how this new scheme could be made to work\n> with the current scheme, it seems like perhaps new git\n> releases could be made to understand both the old and the\n> new, and a config option could be used to tell it which\n> method to write new refs with.  Since in this new scheme\n> ref directory names would conflict with old ref\n> filenames, this would likely prevent both schemes from\n> erroneously being used\n> simultaneously (so they shouldn't corrupt each other),\n> except for the fact that refs can be nested in\n> directories which confuses things a bit.  I am not sure\n> what a good solution to this is?\n> \n> What did I miss, where are my flaws?  Does anyone else\n> share my concern for stale locks?  How could we similarly\n> eliminate locks for the packed-refs file?\n> \n> -Martin\n> \n> \n> *1 We have been concerned with stale locks in the Gerrit\n> community when trying to design atomic cross repository\n> updates.  Of course, while a lockless solution eliminates\n> stale locks, it might make it impossible to do atomic\n> cross repository updates since all of our solutions so\n> far need locks. :(\n\nHmm, actually I believe that with a small modification to the \nsemantics described here it would be possible to make multi \nrepo/branch commits work.   Simply allow the ref filename to \nbe locked by a transaction by appending the transaction ID to \nthe filename.  So if transaction 123 wants to lock master \nwhich points currently to abcde, then it will move \nmaster/abcde to master/abcde_123.  If transaction 123 is \ndesigned so that any process can commit/complete/abort it \nwithout requiring any locks which can go stale, then this ref \nlock will never go stale either (easy as long as it writes \nall its proposed updates somewhere upfront and has atomic \nsemantics for starting, committing and aborting).  On commit, \nthe ref lock gets updated to its new value: master/newsha and \non abort it gets unlocked: master/abcde.\n\nShawn talked about adding multi repo/branch transaction \nsemantics to jgit, this might be something that git wants to \nsupport also at some point?\n\n-Martin\n"},{"id":"205593","messageId":"7vlicijepv.fsf@alter.siamese.dyndns.org","threadId":"32426","inReplyTo":"201212271611.52203.mfick@codeaurora.org","subject":"Re: Lockless Refs?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-12-28T16:58:36Z","receivedAt":"2012-12-28T16:58:36Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Fick <mfick@codeaurora.org> writes:\n\n> 3) To create a ref, it must be renamed from the null file (sha \n> 0000...) to the new value just as if it were being updated \n> from any other value, but there is one extra condition: \n> before renaming the null file, a full directory scan must be \n> done to ensure that the null file is the only file in the \n> directory...\n\nWhile you are scanning this directory to make sure it is empty, I am\ncontemplating to create the same ref with a different value.  You\nfinished checking but haven't created the null. I have also scanned,\ncreated the null and renamed it to my value.  Now you try to create\nthe null, succeed, and then rename.  We won't know which of the two\nnon-null values are valid, but worse yet, I think one of them should\nhave failed in the first place.\n\nSounds like we would need some form of locking around here.  Is your\ngoal \"no locks\", or \"less locks\"?\n\n> I don't know how this new scheme could be made to work with \n> the current scheme,...\n\nIt is much more important to know if/why yours is better than the\ncurrent scheme in the first place.  Without an analysis on how the\nnew scheme interacts with the packed refs and gives better\nbehaviour, that is kinda difficult.\n\nI think transition plans can wait until that is done.  If it is not\neven marginally better, we do not have to worry about transitioning\nat all.  If it is only marginally better, the transition has to be\ndesigned to be no impact to the existing repositories.  If it is\nvastly better, we might be able to afford a flag day.\n"},{"id":"205594","messageId":"7vhan6jdx3.fsf@alter.siamese.dyndns.org","threadId":"32426","inReplyTo":"201212280750.14695.mfick@codeaurora.org","subject":"Re: Lockless Refs?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-12-28T17:15:52Z","receivedAt":"2012-12-28T17:15:52Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Fick <mfick@codeaurora.org> writes:\n\n> Hmm, actually I believe that with a small modification to the \n> semantics described here it would be possible to make multi \n> repo/branch commits work....\n>\n> Shawn talked about adding multi repo/branch transaction \n> semantics to jgit, this might be something that git wants to \n> support also at some point?\n\nShawn may have talked about it and you may have listened to it, but\nothers wouldn't have any idea what kind of \"multi repo/branch\ntransaction\" you are talking about.  Is it about \"I want to push\nthis ref to that repo and push this other ref to that other repo\",\nin what situation will it be used/useful, what are the failure\nmodes, what are failure tolerances by the expected use cases, ...?\n\nCare to explain?\n"},{"id":"205627","messageId":"201212281807.23533.mfick@codeaurora.org","threadId":"32426","inReplyTo":"7vlicijepv.fsf@alter.siamese.dyndns.org","subject":"Re: Lockless Refs?","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-12-29T01:07:23Z","receivedAt":"2012-12-29T01:07:23Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Friday, December 28, 2012 09:58:36 am Junio C Hamano \nwrote:\n> Martin Fick <mfick@codeaurora.org> writes:\n> > 3) To create a ref, it must be renamed from the null\n> > file (sha 0000...) to the new value just as if it were\n> > being updated from any other value, but there is one\n> > extra condition: before renaming the null file, a full\n> > directory scan must be done to ensure that the null\n> > file is the only file in the directory...\n> \n> While you are scanning this directory to make sure it is\n> empty, \n\nThe objective is not to scan for an empty dir, but to scan \nfor the existence of only the null file.\n\n> I am contemplating to create the same ref with a\n> different value.  You finished checking but haven't\n> created the null.\n\nThe scan needs to happen after creating the null, not before, \nso I don't believe the rest of the scenario below is possible \nthen?\n\n> I have also scanned, created the null\n> and renamed it to my value.  Now you try to create the\n> null, succeed, and then rename.  We won't know which of\n> the two non-null values are valid, but worse yet, I think\n> one of them should have failed in the first place.\n\n\n\n> Sounds like we would need some form of locking around\n> here.  Is your goal \"no locks\", or \"less locks\"?\n(answered below)\n\n> > I don't know how this new scheme could be made to work\n> > with the current scheme,...\n> \n> It is much more important to know if/why yours is better\n> than the current scheme in the first place.  \n\nThe goal is: \"no locks which do not have a clearly defined \nreliable recovery procedure\".\n\nStale locks without a reliable recovery procedure will lead \nto stolen locks.  At this point it is only a matter of luck \nwhether this leads to data loss or not.  So I do hope to \nconvince people first that the current scheme is bad, not that \nmy scheme is better!  My scheme was proposed to get people \nthinking that we may not have to use locks to get reliable \nupdates.\n\n\n> Without an\n> analysis on how the new scheme interacts with the packed\n> refs and gives better behaviour, that is kinda difficult.\n\nFair enough. I will attempt this if the basic idea seems at \nleast sane?  I do hope that eventually the packed-refs piece \nand its locking will be reconsidered also; as Michael pointed \nout it has issues already.  So, I am hoping to get people \nthinking more about lockless approaches to all the pieces. I \nthink I have some solutions to some of the other pieces also, \nbut I don't want to overwhelm the discussion all at once \n(especially if my first piece is shown to be flawed, or if no \none has any interest in eliminating the current locks?)\n\n \n> I think transition plans can wait until that is done.  If\n> it is not even marginally better, we do not have to worry\n> about transitioning at all.  If it is only marginally\n> better, the transition has to be designed to be no impact\n> to the existing repositories.  If it is vastly better, we\n> might be able to afford a flag day.\n\nOK, makes sense, I jumped the gun a bit,\n\n-Martin\n"},{"id":"205639","messageId":"20121229071630.GA15408@sigill.intra.peff.net","threadId":"32426","inReplyTo":"50DAB447.8000101@alum.mit.edu","subject":"Re: [PATCH] refs: do not use cached refs in repack_without_ref","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-29T07:16:30Z","receivedAt":"2012-12-29T07:16:30Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 26, 2012 at 09:24:39AM +0100, Michael Haggerty wrote:\n\n> I'm sorry to take so long to respond to this patch.  Thank you for\n> tracking down this bug and for your careful analysis.\n> \n> I think your patch is correct and should fix the first race condition\n> that you described.\n\nThanks for checking it over. I almost cc'd you, as I know you have been\nworking on ref caching. But I think that the problem is much older, as\nwe always cached the packed-refs list in memory.\n\n> But I think the continued existence of the other race conditions is an\n> indication of a fundamental problem with the reference locking\n> policy--independent of the in-RAM reference cache.\n> \n> The tacit assumption of the current locking policy is that changes to\n> the packed-refs file are not critical for correctness, because loose\n> references take precedence over it anyway.  This is true for adding and\n> modifying references.  But it is not true for deleting references,\n> because there is no way for a deletion to be represented as a loose\n> reference in a way that takes precedence over the packed-refs file\n> (i.e., there is no way for a loose reference to say \"I am deleted,\n> regardless of what packed-refs says\").  Thus the race conditions for\n> deleting references, whether via delete_ref() or via pack_refs() with\n> --prune.\n\nYeah. It would be much nicer if we could just write the null sha1 or a\nsimilar sentinel into the loose ref for \"I am deleted\". The problem\n(besides backwards compatibility) is the usual D/F conflict. I cannot\ndelete \"refs/heads/foo\" and then create \"refs/heads/foo/bar\" if the old\nref file is in the way.\n\n> There is a problem if two processes try to delete a reference at the\n> same time, or if one process tries to delete a reference at the same\n> time as another process is trying to pack the references.  The reason is\n> that there is no \"transaction\" that spans both the rewriting of the\n> packed-refs file and also the deletion of the loose-ref files, and\n> therefore it is possible for conflicting changes to be made in the two\n> locations.\n\nJust to be clear, are you talking about the races I wrote about in my\nother email? Or are there other races? I didn't (and still don't) see\nany actual on-disk data loss races. Just ones where a reader may get an\nold, packed value (which is still bad, but is less bad than one where a\nwrite is lost).\n\n> I think that all of the problems would be fixed if a lock would be held\n> on the packed-refs file during the whole process of deleting any\n> reference; i.e., change the algorithms to:\n\nYeah, I looked at that, too. In fact, before I had correctly analyzed\nthe problem, I thought that doing so would solve the problem I was\nseeing (which I noticed was wrong when it did not pass my tests :) ).\n\n>From your description, I think you realize this, but I want to point out\nfor other readers: just updating the pack_refs side to call prune_refs\nunder the lock would create a deadlock with a simultaneous delete (which\ntakes the individual ref lock first, then the packed-refs lock). Of\ncourse, I do not think git is capable of deadlock, as we typically just\ndie() instead of blocking on a lock. So maybe it does not matter so\nmuch. :)\n\n> * Delete reference foo:\n> \n>   1. Acquire the lock $GIT_DIR/packed-refs.lock (regardless of whether\n>      \"foo\" is a packed ref)\n\nThis suffers from the same problem I mentioned in my earlier email: we\ncreate lock contention on packed-refs.lock when there are two\nsimultaneous deletes, even when the refs aren't packed. That might be an\nacceptable tradeoff, though. It's only for deletion, not for update,\nwhich is presumably rare. And it has to happen anyway when both refs are\npacked.\n\n>   2. Write to $GIT_DIR/packed-refs.new a version of the packed-refs\n>      file that omits \"foo\"\n> [...]\n\nAll of the further steps make sense. By deleting from packed-refs first,\nwe eliminate the read race-condition I mentioned in my earlier email.\nThe only downside is the possible increased lock contention on\npacked-refs.lock.  I'm very tempted to go this route. It's better to be\ncorrect and sometimes die on lock contention than to sometimes give the\nwrong answer.\n\n> I would appreciate a critique of my analysis.  Even if you agree, I\n> think it would be OK to apply Peff's patch to fix up the most pressing\n> problem, then implement the more complete solution later.\n\nI think your analysis is correct, modulo the issue I mentioned. And I\nagree that my patch is a good interim, as it fixes the worst case\n(losing writes).\n\n-Peff\n"},{"id":"205641","messageId":"20121229081021.GC15408@sigill.intra.peff.net","threadId":"32426","inReplyTo":"201212271611.52203.mfick@codeaurora.org","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-29T08:10:21Z","receivedAt":"2012-12-29T08:10:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 27, 2012 at 04:11:51PM -0700, Martin Fick wrote:\n\n> For a single user repo this is not a big deal, the lock can \n> always be cleaned up manually (and it is a rare occurrence).  \n> However, in a multi user server environment, possibly even \n> from multiple hosts over a shared filesystem such as NFS, \n> stale locks could lead to serious downtime and risky recovery \n> (since it is currently hard to figure out if a lock really is \n> stale).  Even though stale locks are probably rare even today \n> in the larger shared repo case, as git scales to even larger \n> shared repositories, this will eventually become more of a \n> problem *1.  Naturally, this has me thinking that git should \n> possibly consider moving towards a lockless design for refs \n> in the long term.\n\nFWIW, I am involved in cleaning up stale locks for a very large git\nhosting site. It actually happens surprisingly little. I think it is\nmostly because git holds actual locks for a very short period of time\n(just enough to check that the value is unchanged from when we started a\nlengthy operation, and then atomically write the new value).\n\nSo I agree it would be cool (and maybe open up new realms of\nscalability) for git to be lockless, but in my experience, this isn't\nthat pressing a problem (and any solutions are not going to be backwards\ncompatible, so there is going to be a high deployment cost).\n\n> My idea is based on using filenames to store sha1s instead of \n> file contents.  To do this, the sha1 one of a ref would be \n> stored in a file in a directory named after the loose ref.  I \n> believe this would then make it possible to have lockless \n> atomic ref updates by renaming the file.\n> \n> To more fully illustrate the idea, imagine that any file \n> (except for the null file) in the directory will represent the \n> value of the ref with its name, then the following \n> transitions can represent atomic state changes to a refs \n> value and existence:\n\nHmm. So basically you are relying on atomic rename() to move the value\naround within a directory, rather than using write to move it around\nwithin a file. Atomic rename is usually something we have on local\nfilesystems (and I think we rely on it elsewhere). Though I would not be\nsurprised if it is not atomic on all networked filesystems (though it is\non NFS, at least).\n\n> 1) To update the value from a known value to a new value \n> atomically, simply rename the file to the new value.  This \n> operation should only succeed if the file exists and is still \n> named old value before the rename.  This should even be \n> faster than today's approach, especially on remote filesystems \n> since it would require only 1 round trip in the success case \n> instead of 3!\n\nOK. Makes sense.\n\n> 2) To delete the ref, simply delete the filename representing \n> the current value of the ref.  This ensures that you are \n> deleting the ref from a specific value.  I am not sure if git \n> needs to be able to delete refs without knowing their values?  \n> If so, this would require reading the value and looping until \n> the delete succeeds, this may be a bit slow for a constantly \n> updated ref, but likely a rare situation (and not likely \n> worse than trying to acquire the ref-lock today).  Overall, \n> this again would likely be faster than today's approach.\n\nWe do sometimes delete without knowing the value. In most cases we would\nnot want to do this, but for some \"force\"-type commands, we do. You\nwould actually have the same problem with updating above, as we\nsometimes update with the intent to overwrite whatever is there.\n\n> 3) To create a ref, it must be renamed from the null file (sha \n> 0000...) to the new value just as if it were being updated \n> from any other value, but there is one extra condition: \n> before renaming the null file, a full directory scan must be \n> done to ensure that the null file is the only file in the \n> directory (this condition exists because creating the \n> directory and null file cannot be atomic unless the filesystem \n> supports atomic directory renames, an expectation git does \n> not currently make).  I am not sure how this compares to \n> today's approach, but including the setup costs (described \n> below), I suspect it is slower.\n\nHmm. mkdir is atomic. So wouldn't it be sufficient to just mkdir and\ncreate the correct sha1 file?  A simultaneous creator would fail on the\nmkdir and abort. A simultaneous reader might see the directory, but it\nwould either see it as empty, or with the correct file. In the former\ncase, it would treat that the same as if the directory did not exist.\n\nSpeaking of which, you did not cover reading at all, but it would have\nto be:\n\n  dh = opendir(ref);\n  if (!dh) {\n          if (errno == ENOENT)\n                  return 0; /* no such ref */\n          else\n                  return error(\"couldn't read ref\");\n  }\n\n  while ((ent = readdir(dh)) {\n          if (ent->d_name[0] == '.')\n                  /*\n                   * skip \".\" and \"..\", and leave room for annotating \n                   * refs via dot-files\n                   */\n                   continue;\n          /* otherwise, we found it */\n          if (get_sha1_hex(ent->d_name, sha1) < 0)\n                  return error(\"weird junk in ref dir?\");\n          return 1; /* found it */\n  }\n  return 0; /* did not contain an entry; ref being created? Retry? */\n\n\nIs readdir actually atomic with respect to directory updates? That is,\nif I am calling readdir() and somebody else is renaming, what do I get?\nPOSIX says:\n\n   If a file is removed from or added to the directory after the most\n   recent call to opendir() or rewinddir(), whether a subsequent call to\n   readdir() returns an entry for that file is unspecified.\n\nIf I get one or the other file (that is, the old name or the new one),\nit is OK. It does not matter which, as it is a race whether I see the\nold value or the new one during an update. But according to POSIX, it is\npossible that I may see neither.\n\nI suppose we could rewinddir() and retry. We might hit the race again\n(if somebody else is updating quickly), but realistically, this will\nhappen very infrequently, and we can just keep trying until we win the\nrace and get a valid read.\n\n> I don't know how this new scheme could be made to work with \n> the current scheme, it seems like perhaps new git releases \n> could be made to understand both the old and the new, and a \n> config option could be used to tell it which method to write \n> new refs with.  Since in this new scheme ref directory names \n> would conflict with old ref filenames, this would likely \n> prevent both schemes from erroneously being used \n> simultaneously (so they shouldn't corrupt each other), except \n> for the fact that refs can be nested in directories which \n> confuses things a bit.  I am not sure what a good solution to \n> this is?\n\nI think you would need to bump core.repositoryformatversion, and just\nnever let old versions of git access the repository directly. Not the\nend of the world, but it certainly increases deployment effort. If we\nwere going to do that, it would probably make sense to think about\nsolving the D/F conflict issues at the same time (i.e., start calling\n\"refs/heads/foo\" in the filesystem \"refs.d/heads.d/foo.ref\" so that it\ncannot conflict with \"refs.d/heads.d/foo.d/bar.ref\").\n\n-Peff\n"},{"id":"205642","messageId":"20121229081200.GD15408@sigill.intra.peff.net","threadId":"32426","inReplyTo":"201212280750.14695.mfick@codeaurora.org","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-29T08:12:00Z","receivedAt":"2012-12-29T08:12:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 28, 2012 at 07:50:14AM -0700, Martin Fick wrote:\n\n> Hmm, actually I believe that with a small modification to the \n> semantics described here it would be possible to make multi \n> repo/branch commits work.   Simply allow the ref filename to \n> be locked by a transaction by appending the transaction ID to \n> the filename.  So if transaction 123 wants to lock master \n> which points currently to abcde, then it will move \n> master/abcde to master/abcde_123.  If transaction 123 is \n> designed so that any process can commit/complete/abort it \n> without requiring any locks which can go stale, then this ref \n> lock will never go stale either (easy as long as it writes \n> all its proposed updates somewhere upfront and has atomic \n> semantics for starting, committing and aborting).  On commit, \n> the ref lock gets updated to its new value: master/newsha and \n> on abort it gets unlocked: master/abcde.\n\nHmm. I thought our goal was to avoid locks? Isn't this just locking by\nanother name?\n\nI guess your point is to have no locks in the \"normal\" case, and have\nlocked transactions as an optional add-on?\n\n-Peff\n"},{"id":"205643","messageId":"20121229081657.GE15408@sigill.intra.peff.net","threadId":"32426","inReplyTo":"7vhan6jdx3.fsf@alter.siamese.dyndns.org","subject":"Re: Lockless Refs?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-12-29T08:16:57Z","receivedAt":"2012-12-29T08:16:57Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 28, 2012 at 09:15:52AM -0800, Junio C Hamano wrote:\n\n> Martin Fick <mfick@codeaurora.org> writes:\n> \n> > Hmm, actually I believe that with a small modification to the \n> > semantics described here it would be possible to make multi \n> > repo/branch commits work....\n> >\n> > Shawn talked about adding multi repo/branch transaction \n> > semantics to jgit, this might be something that git wants to \n> > support also at some point?\n> \n> Shawn may have talked about it and you may have listened to it, but\n> others wouldn't have any idea what kind of \"multi repo/branch\n> transaction\" you are talking about.  Is it about \"I want to push\n> this ref to that repo and push this other ref to that other repo\",\n> in what situation will it be used/useful, what are the failure\n> modes, what are failure tolerances by the expected use cases, ...?\n> \n> Care to explain?\n\nI cannot speak for Martin, but I am assuming the point is to atomically\nupdate 2 (or more) refs on the same repo. That is, if I have a branch\n\"refs/heads/foo\" and a ref pointing to meta-information (say, notes\nabout commits in foo, in \"refs/notes/meta/foo\"), I would want to \"git\npush\" them, and only update them if _both_ will succeed, and otherwise\nfail and update nothing.\n\nI think Shawn mentioned this at the last GitTogether as a stumbling\nblock for pushing more of Gerrit's meta-information as refs over the git\nprotocol. But I might be mis-remembering.\n\n-Peff\n"},{"id":"205661","messageId":"30efc2de-237f-4f46-9748-fa9c12e3e1be@email.android.com","threadId":"32426","inReplyTo":"20121229081657.GE15408@sigill.intra.peff.net","subject":"Re: Lockless Refs?","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-12-29T21:15:50Z","receivedAt":"2012-12-29T21:15:50Z","isPatch":false,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"\n\nJeff King <peff@peff.net> wrote:\n\n>On Fri, Dec 28, 2012 at 09:15:52AM -0800, Junio C Hamano wrote:\n>\n>> Martin Fick <mfick@codeaurora.org> writes:\n>> \n>> > Hmm, actually I believe that with a small modification to the \n>> > semantics described here it would be possible to make multi \n>> > repo/branch commits work....\n>> >\n>> > Shawn talked about adding multi repo/branch transaction \n>> > semantics to jgit, this might be something that git wants to \n>> > support also at some point?\n>> \n>> Shawn may have talked about it and you may have listened to it, but\n>> others wouldn't have any idea what kind of \"multi repo/branch\n>> transaction\" you are talking about.  Is it about \"I want to push\n>> this ref to that repo and push this other ref to that other repo\",\n>> in what situation will it be used/useful, what are the failure\n>> modes, what are failure tolerances by the expected use cases, ...?\n>> \n>> Care to explain?\n>\n>I cannot speak for Martin, but I am assuming the point is to atomically\n>update 2 (or more) refs on the same repo. That is, if I have a branch\n>\"refs/heads/foo\" and a ref pointing to meta-information (say, notes\n>about commits in foo, in \"refs/notes/meta/foo\"), I would want to \"git\n>push\" them, and only update them if _both_ will succeed, and otherwise\n>fail and update nothing.\n\nMy use case was cross repo/branch dependencies in Gerrit (which do not yet exist). Users want to be able to define several changes (destined for different project/branches) which can only be merged together.  If one change cannot be merged, the others should fail too.  The solutions we can think of generally need to hold ref locks while acquiring more ref locks, this drastically increases the opportunities for stale locks over the simple \"lock, check, update, unlock\" mode which git locks are currently used for.\n\nI was perhaps making too big of a leap to assume that there would be other non Gerrit uses cases for this?  I assumed that other git projects which are spread across several git repos would need this? But maybe this simply wouldn't be practical with other git server solutions?\n\n-Martin\n\nEmployee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum\n"},{"id":"205662","messageId":"befe9a89-8f71-437e-ad33-c4dc4ee90507@email.android.com","threadId":"32426","inReplyTo":"20121229081200.GD15408@sigill.intra.peff.net","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-12-29T21:29:55Z","receivedAt":"2012-12-29T21:29:55Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"Jeff King <peff@peff.net> wrote:\n\n>On Fri, Dec 28, 2012 at 07:50:14AM -0700, Martin Fick wrote:\n>\n>> Hmm, actually I believe that with a small modification to the \n>> semantics described here it would be possible to make multi \n>> repo/branch commits work.   Simply allow the ref filename to \n>> be locked by a transaction by appending the transaction ID to \n>> the filename.  So if transaction 123 wants to lock master \n>> which points currently to abcde, then it will move \n>> master/abcde to master/abcde_123.  If transaction 123 is \n>> designed so that any process can commit/complete/abort it \n>> without requiring any locks which can go stale, then this ref \n>> lock will never go stale either (easy as long as it writes \n>> all its proposed updates somewhere upfront and has atomic \n>> semantics for starting, committing and aborting).  On commit, \n>> the ref lock gets updated to its new value: master/newsha and \n>> on abort it gets unlocked: master/abcde.\n>\n>Hmm. I thought our goal was to avoid locks? Isn't this just locking by\n>another name?\n\nIt is a lock, but it is a lock with an owner: the transaction.  If the transaction has reliable recovery semantics, then the lock will be recoverable also.  This is possible if we have lock ownership (the transaction) which does not exist today for the ref locks.  With good lock ownership we gain the ability to reliably delete locks for a specific owner without the risk of deleting the lock when held by another owner (putting the owner in the filename is \"good\", while putting the owner in the filecontents is not).   Lastly, for reliable recovery of stale locks we need the ability to determine when an owner has abandoned a lock.  I believe that the transaction semantics laid out below give this.\n\n\n>I guess your point is to have no locks in the \"normal\" case, and have\n>locked transactions as an optional add-on?\n\nBasically.  If we design the transaction into the git semantics we could ensure that it is recoverable and we should not need to expose these reflocks outside of the transaction APIs.\n\nTo illustrate a simple transaction approach (borrowing some of Shawn's ideas), we could designate a directory to hold transaction files *1.  To prepare a transaction: write a list of repo:ref:oldvalue:newvalue to a file named id.new (in a stable sorted order based on repo:ref to prevent deadlocks).  This is not a state change and thus this file could be deleted by any process at anytime (preferably after a long grace period).\n\nIf file renames are atomic on the filesystem holding the transaction files then 1, 2, 3 below will be atomic state changes.  It does not matter who performs state transitions 2 or 3.  It does not matter who implements the work following any of the 3 transitions, many processes could attempt the work in parallel (so could a human).\n \n1) To start the transaction, rename the id.new file to id.  If the rename fails, start over if desired/still possible.  On success, ref locks for each entry should be acquired in listed order (to prevent deadlocks), using transaction id and oldvalue.  It is never legal to unlock a ref in this state (because a block could cause the unlock to be delayed until the commit phase).  However, it is legal for any process to transition to abort at any time from this state, perhaps because of a failure to acquire a lock (held by another transaction), and definitely if a ref has changed (is no longer oldvalue).\n\n2) To abort the transaction, rename the id file to id.abort.  This should only ever fail if commit was achieved first.  Once in this state, any process may/should unlock any ref locks belonging to this transaction id.  Once all refs are unlocked, id.abort may be deleted (it could be deleted earlier, but then cleanup will take longer).\n\n3) To commit the transaction, rename the file to id.commit.  This should only ever fail if abort was achieved first. This transition should never be done until every listed ref is locked by the current transaction id.  Once in this phase, all refs may/should be moved to their new values and unlocked by any process. Once all refs are unlocked, id.commit may be deleted. \n\nSince any process attempting any of the work in these transactions could block at any time for an indefinite amount of time, these processes may wake after the transaction is aborted or comitted and the transaction files are cleaned up.  I believe that in these cases the only actions which could succeed by these waking processes is the ref locking action.  All such abandoned ref locks may/should be unlocked by any process.  This last rule means that no transaction ids should ever be reused,\n\n-Martin\n\n\n*1 We may want to adapt the simple model illustrated above to use git mechanisms such as refs to hold transaction info instead of files in a directory, and git submodule files to hold the list of refs to update.  \n\nEmployee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum\n"},{"id":"205663","messageId":"029f9379-a284-40e6-b4b9-529bd82d6e3e@email.android.com","threadId":"32426","inReplyTo":"20121229081021.GC15408@sigill.intra.peff.net","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-12-29T22:18:49Z","receivedAt":"2012-12-29T22:18:49Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"Jeff King <peff@peff.net> wrote:\n\n>On Thu, Dec 27, 2012 at 04:11:51PM -0700, Martin Fick wrote:\n>> My idea is based on using filenames to store sha1s instead of \n>> file contents.  To do this, the sha1 one of a ref would be \n>> stored in a file in a directory named after the loose ref.  I \n>> believe this would then make it possible to have lockless \n>> atomic ref updates by renaming the file.\n>> \n>> To more fully illustrate the idea, imagine that any file \n>> (except for the null file) in the directory will represent the \n>> value of the ref with its name, then the following \n>> transitions can represent atomic state changes to a refs \n>> value and existence:\n>\n>Hmm. So basically you are relying on atomic rename() to move the value\n>around within a directory, rather than using write to move it around\n>within a file. Atomic rename is usually something we have on local\n>filesystems (and I think we rely on it elsewhere). Though I would not\n>be\n>surprised if it is not atomic on all networked filesystems (though it\n>is\n>on NFS, at least).\n\nYes.  I assume this is OK because doesn't git already rely on atomic renames?  For example to rename the new packed-refs file to unlock it?\n\n...\n\n>> 3) To create a ref, it must be renamed from the null file (sha \n>> 0000...) to the new value just as if it were being updated \n>> from any other value, but there is one extra condition: \n>> before renaming the null file, a full directory scan must be \n>> done to ensure that the null file is the only file in the \n>> directory (this condition exists because creating the \n>> directory and null file cannot be atomic unless the filesystem \n>> supports atomic directory renames, an expectation git does \n>> not currently make).  I am not sure how this compares to \n>> today's approach, but including the setup costs (described \n>> below), I suspect it is slower.\n>\n>Hmm. mkdir is atomic. So wouldn't it be sufficient to just mkdir and\n>create the correct sha1 file?\n\nBut then a process could mkdir and die leaving a stale empty dir with no reliable recovery mechanism.\n\n\nUnfortunately, I think I see another flaw though! :( I should have known that I cannot separate an important check from its state transitioning action.  The following could happen:\n\n A does mkdir\n A creates null file\n A checks dir -> no other files \n B checks dir -> no other files\n A renames null file to abcd\n C creates second null file \n B renames second null file to defg\n\nOne way to fix this is to rely on directory renames, but I believe this is something git does not want to require of every FS? If we did, we could Change #3 to be:\n\n3) To create a ref, it must be renamed from the null file (sha 0000...) to the new value just as if it were being updated from any other value. (No more scan)\n\nThen, with reliable directory renames, a process could do what you suggested to a temporary directory, mkdir + create null file, then rename the temporary dir to refname.  This would prevent duplicate null files.  With a grace period, the temporary dirs could be cleaned up in case a process dies before the rename.  This is your approach with reliable recovery.\n\n\n>> I don't know how this new scheme could be made to work with \n>> the current scheme, it seems like perhaps new git releases \n>> could be made to understand both the old and the new, and a \n>> config option could be used to tell it which method to write \n>> new refs with.  Since in this new scheme ref directory names \n>> would conflict with old ref filenames, this would likely \n>> prevent both schemes from erroneously being used \n>> simultaneously (so they shouldn't corrupt each other), except \n>> for the fact that refs can be nested in directories which \n>> confuses things a bit.  I am not sure what a good solution to \n>> this is?\n>\n>I think you would need to bump core.repositoryformatversion, and just\n>never let old versions of git access the repository directly. Not the\n>end of the world, but it certainly increases deployment effort. If we\n>were going to do that, it would probably make sense to think about\n>solving the D/F conflict issues at the same time (i.e., start calling\n>\"refs/heads/foo\" in the filesystem \"refs.d/heads.d/foo.ref\" so that it\n>cannot conflict with \"refs.d/heads.d/foo.d/bar.ref\").\n\nWouldn't you want to use a non legal ref character instead of dot? And without locks, we free up more of the ref namespace too I think? (Refs could end in \".lock\")\n\n-Martin\n\nEmployee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum\n"},{"id":"205679","messageId":"201212301003.19802.mfick@codeaurora.org","threadId":"32426","inReplyTo":"029f9379-a284-40e6-b4b9-529bd82d6e3e@email.android.com","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-12-30T17:03:19Z","receivedAt":"2012-12-30T17:03:19Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Saturday, December 29, 2012 03:18:49 pm Martin Fick wrote:\n> Jeff King <peff@peff.net> wrote:\n> >On Thu, Dec 27, 2012 at 04:11:51PM -0700, Martin Fick \nwrote:\n> >> My idea is based on using filenames to store sha1s\n> >> instead of file contents.  To do this, the sha1 one of\n> >> a ref would be stored in a file in a directory named\n> >> after the loose ref.  I believe this would then make\n> >> it possible to have lockless atomic ref updates by\n> >> renaming the file.\n> >> \n> >> To more fully illustrate the idea, imagine that any\n> >> file (except for the null file) in the directory will\n> >> represent the value of the ref with its name, then the\n> >> following transitions can represent atomic state\n> >> changes to a refs\n> >\n> >> value and existence:\n> >Hmm. So basically you are relying on atomic rename() to\n> >move the value around within a directory, rather than\n> >using write to move it around within a file. Atomic\n> >rename is usually something we have on local filesystems\n> >(and I think we rely on it elsewhere). Though I would\n> >not be\n> >surprised if it is not atomic on all networked\n> >filesystems (though it is\n> >on NFS, at least).\n> \n> Yes.  I assume this is OK because doesn't git already rely\n> on atomic renames?  For example to rename the new\n> packed-refs file to unlock it?\n> \n> ...\n> \n> >> 3) To create a ref, it must be renamed from the null\n> >> file (sha 0000...) to the new value just as if it were\n> >> being updated from any other value, but there is one\n> >> extra condition: before renaming the null file, a full\n> >> directory scan must be done to ensure that the null\n> >> file is the only file in the directory (this condition\n> >> exists because creating the directory and null file\n> >> cannot be atomic unless the filesystem supports atomic\n> >> directory renames, an expectation git does not\n> >> currently make).  I am not sure how this compares to\n> >> today's approach, but including the setup costs\n> >> (described below), I suspect it is slower.\n> >\n> >Hmm. mkdir is atomic. So wouldn't it be sufficient to\n> >just mkdir and create the correct sha1 file?\n> \n> But then a process could mkdir and die leaving a stale\n> empty dir with no reliable recovery mechanism.\n> \n> \n> Unfortunately, I think I see another flaw though! :( I\n> should have known that I cannot separate an important\n> check from its state transitioning action.  The following\n> could happen:\n> \n>  A does mkdir\n>  A creates null file\n>  A checks dir -> no other files\n>  B checks dir -> no other files\n>  A renames null file to abcd\n>  C creates second null file\n>  B renames second null file to defg\n> \n> One way to fix this is to rely on directory renames, but I\n> believe this is something git does not want to require of\n> every FS? If we did, we could Change #3 to be:\n> \n> 3) To create a ref, it must be renamed from the null file\n> (sha 0000...) to the new value just as if it were being\n> updated from any other value. (No more scan)\n> \n> Then, with reliable directory renames, a process could do\n> what you suggested to a temporary directory, mkdir +\n> create null file, then rename the temporary dir to\n> refname.  This would prevent duplicate null files.  With\n> a grace period, the temporary dirs could be cleaned up in\n> case a process dies before the rename.  This is your\n> approach with reliable recovery.\n\nThe whole null file can go away if we use directory renames.  \nMake #3:\n\n3) To create a ref, create a temporary directory containing a \nfile named after the sha1 of the ref to be created and rename \nthe directory to the name of the ref to create.  If the \nrename fails, the create fails.  If the rename succeeds, the \ncreate succeeds.\n\nWith a grace period, the temporary dirs could be cleaned up \nin case a process dies before the rename,\n\n-Martin\n"},{"id":"205694","messageId":"201212310330.53835.mfick@codeaurora.org","threadId":"32426","inReplyTo":"201212271611.52203.mfick@codeaurora.org","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2012-12-31T10:30:53Z","receivedAt":"2012-12-31T10:30:53Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Thursday, December 27, 2012 04:11:51 pm Martin Fick wrote:\n> It concerns me that git uses any locking at all, even for\n> refs since it has the potential to leave around stale\n> locks.\n> ...\n> [a previous not so great attempt to fix this]\n> ...\n\nI may have finally figured out a working loose ref update \nmechanism which I think can avoid stale locks.  Unfortunately \nit requires atomic directory renames and universally unique \nidentifiers (uuids).  These may be no-go criteria?  But I \nfigure it is worth at least exploring this idea because of the \npotential benefits?\n\nThe general approach is to setup a transaction and either \ncommit or abort it.  A transaction can be setup by renaming \nan appropriately setup directory to the \"ref.lock\" name.  If \nthe rename succeeds, the transaction is begun.  Any actor can \nabort the transaction (up until it is committed) by simply \ndeleting the \"ref.lock\" directory, so it is not at risk of \ngoing stale.  However, once the actor who sets up the \ntransaction commits it, deleting the \"ref.lock\" directory \nsimply aids in cleaning it up for the next transaction \n(instead of aborting it).\n\nOne important piece of the transaction is the use of uuids.  \nThe uuids provide a mechanism to tie the atomic commit pieces \nto the transactions and thus to prevent long sleeping process \nfrom inadvertently performing actions which could be out of \ndate when they wake finally up.  In each case, the atomic \ncommit piece is the renaming of a file.   For the create and \nupdate pieces, a file is renamed from the \"ref.lock\" dir to \nthe \"ref\" file resulting in an update to the sha for the ref.  \nHowever, in the delete case, the \"ref\" file is instead renamed \nto end up in the \"ref.lock\" directory resulting in a delete \nof the ref.  This scheme does not affect the way refs are read \ntoday,\n\nTo prepare for a transaction, an actor first generates a uuid \n(an exercise I will delay for now).  Next, a tmp directory \nnamed after the uuid is generated in the parent directory for \nthe ref to be updated, perhaps something like:  \".lock_uuid\".  \nIn this directory is places either a file or a directory named \nafter the uuid, something like: \".lock_uuid/,uuid\".  In the \ncase of a create or an update, the new sha is written to this \nfile.  In the case of a delete, it is a directory.  \n\nOnce the tmp directory is setup, the initiating actor \nattempts to start the transaction by renaming the tmp \ndirectory to \"ref.lock\".  If the rename fails, the update \nfails. If the rename succeeds, the actor can then attempt to \ncommit the transaction (before another actor aborts it). \n\nIn the case of a create, the actor verifies that \"ref\" does \nnot currently exist, and then renames the now named \n\"ref.lock/uuid\" file to \"ref\". On success, the ref was \ncreated.\n\nIn the case of an update, the actor verifies that \"ref\" \ncurrently contains the old sha, and then also renames the now \nnamed \"ref.lock/uuid\" file to \"ref\". On success, the ref was \nupdated.\n\nIn the case of a delete, the actor may verify that \"ref\" \ncurrently contains the sha to \"prune\" if it needs to, and \nthen renames the \"ref\" file to \"ref.lock/uuid/delete\". On \nsuccess, the ref was deleted.\n\nWhether successful or not, the actor may now simply delete \nthe \"ref.lock\" directory, clearing the way for a new \ntransaction.  Any other actor may delete this directory at \nany time also, likely either on conflict (if they are \nattempting to initiate a transaction), or after a grace \nperiod just to cleanup the FS.  Any actor may also safely \ncleanup the tmp directories, preferably also after a grace \nperiod.\n\nOne neat part about this scheme is that I believe it would be \nbackwards compatible with the current locking mechanism since \nthe transaction directory will simply appear to be a lock to \nolder clients.  And the old lock file should continue to lock \nout these newer transactions.\n\nDue to this backwards compatibility, I believe that this \ncould be incrementally employed today without affecting very \nmuch.  It could be deployed in place of any updates which \nonly hold ref.locks to update the loose ref.  So for example \nI think it could replace step 4a below from Michael \nHaggerty's description of today's loose ref pruning during \nref packing:\n\n> * Pack references:\n...\n> 4. prune_refs(): for each ref in the ref_to_prune list,\n> call  prune_ref():\n>\n>     a. Lock the reference using lock_ref_sha1(), \n>     verifying that the recorded SHA1 is still valid.  If it\n>     is, unlink the loose reference file then free the lock;\n>     otherwise leave the loose reference file untouched.\n\nI think it would also therefore be able to replace the loose \nref locking in Michael's new ref-packing scheme as well as \nthe locking in Michael's new ref deletion scheme (again steps \n4):\n\n> * Delete reference foo:\n...\n>   4. Delete loose ref for \"foo\":\n> \n>      a. Acquire the lock $GIT_DIR/refs/heads/foo.lock\n> \n>      b. Unlink $GIT_DIR/refs/heads/foo if it is unchanged.\n>  If it is changed, leave it untouched.  If it is deleted,\n> that is OK too.\n> \n>      c. Release lock $GIT_DIR/refs/heads/foo.lock\n\n...\n> * Pack references:\n...\n>   4. prune_refs(): for each ref in the ref_to_prune list,\n> call prune_ref():\n> \n>      a. Lock the loose reference using lock_ref_sha1(),\n> verifying that the recorded SHA1 is still valid\n> \n>      b. If it is, unlink the loose reference file\n> (otherwise, leave it untouched)\n> \n>      c. Release the lock on the loose reference\n\nTo be honest, I suspect I missed something obvious because \nthis seems almost too simple to work.  I am ashamed that it \ntook me so long to come up with (of course, I will be even \nmore ashamed :( when it is shown to be flawed!)  This scheme \nalso feels extensible. if there are no obvious flaws in it, I \nwill try to post solutions for ref packing and for multiple \nrepository/ref transactions also soon.\n\nI welcome any comments/criticisms,\n\n-Martin\n"},{"id":"205961","messageId":"201301031652.44982.mfick@codeaurora.org","threadId":"32426","inReplyTo":"201212310330.53835.mfick@codeaurora.org","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-01-03T23:52:44Z","receivedAt":"2013-01-03T23:52:44Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"Any thoughts on this idea?  Is it flawed?  I am trying to \nwrite it up in a more formal generalized manner and was \nhoping to get at least one \"it seems sane\" before I do.\n\nThanks,\n\n-Martin\n\nOn Monday, December 31, 2012 03:30:53 am Martin Fick wrote:\n> On Thursday, December 27, 2012 04:11:51 pm Martin Fick \nwrote:\n> > It concerns me that git uses any locking at all, even\n> > for refs since it has the potential to leave around\n> > stale locks.\n> > ...\n> > [a previous not so great attempt to fix this]\n> > ...\n> \n> I may have finally figured out a working loose ref update\n> mechanism which I think can avoid stale locks. \n> Unfortunately it requires atomic directory renames and\n> universally unique identifiers (uuids).  These may be\n> no-go criteria?  But I figure it is worth at least\n> exploring this idea because of the potential benefits?\n> \n> The general approach is to setup a transaction and either\n> commit or abort it.  A transaction can be setup by\n> renaming an appropriately setup directory to the\n> \"ref.lock\" name.  If the rename succeeds, the transaction\n> is begun.  Any actor can abort the transaction (up until\n> it is committed) by simply deleting the \"ref.lock\"\n> directory, so it is not at risk of going stale.  However,\n> once the actor who sets up the transaction commits it,\n> deleting the \"ref.lock\" directory simply aids in cleaning\n> it up for the next transaction (instead of aborting it).\n> \n> One important piece of the transaction is the use of\n> uuids. The uuids provide a mechanism to tie the atomic\n> commit pieces to the transactions and thus to prevent\n> long sleeping process from inadvertently performing\n> actions which could be out of date when they wake finally\n> up.  In each case, the atomic commit piece is the\n> renaming of a file.   For the create and update pieces, a\n> file is renamed from the \"ref.lock\" dir to the \"ref\" file\n> resulting in an update to the sha for the ref. However,\n> in the delete case, the \"ref\" file is instead renamed to\n> end up in the \"ref.lock\" directory resulting in a delete\n> of the ref.  This scheme does not affect the way refs are\n> read today,\n> \n> To prepare for a transaction, an actor first generates a\n> uuid (an exercise I will delay for now).  Next, a tmp\n> directory named after the uuid is generated in the parent\n> directory for the ref to be updated, perhaps something\n> like:  \".lock_uuid\". In this directory is places either a\n> file or a directory named after the uuid, something like:\n> \".lock_uuid/,uuid\".  In the case of a create or an\n> update, the new sha is written to this file.  In the case\n> of a delete, it is a directory.\n> \n> Once the tmp directory is setup, the initiating actor\n> attempts to start the transaction by renaming the tmp\n> directory to \"ref.lock\".  If the rename fails, the update\n> fails. If the rename succeeds, the actor can then attempt\n> to commit the transaction (before another actor aborts\n> it).\n> \n> In the case of a create, the actor verifies that \"ref\"\n> does not currently exist, and then renames the now named\n> \"ref.lock/uuid\" file to \"ref\". On success, the ref was\n> created.\n> \n> In the case of an update, the actor verifies that \"ref\"\n> currently contains the old sha, and then also renames the\n> now named \"ref.lock/uuid\" file to \"ref\". On success, the\n> ref was updated.\n> \n> In the case of a delete, the actor may verify that \"ref\"\n> currently contains the sha to \"prune\" if it needs to, and\n> then renames the \"ref\" file to \"ref.lock/uuid/delete\". On\n> success, the ref was deleted.\n> \n> Whether successful or not, the actor may now simply delete\n> the \"ref.lock\" directory, clearing the way for a new\n> transaction.  Any other actor may delete this directory at\n> any time also, likely either on conflict (if they are\n> attempting to initiate a transaction), or after a grace\n> period just to cleanup the FS.  Any actor may also safely\n> cleanup the tmp directories, preferably also after a grace\n> period.\n> \n> One neat part about this scheme is that I believe it would\n> be backwards compatible with the current locking\n> mechanism since the transaction directory will simply\n> appear to be a lock to older clients.  And the old lock\n> file should continue to lock out these newer\n> transactions.\n> \n> Due to this backwards compatibility, I believe that this\n> could be incrementally employed today without affecting\n> very much.  It could be deployed in place of any updates\n> which only hold ref.locks to update the loose ref.  So\n> for example I think it could replace step 4a below from\n> Michael Haggerty's description of today's loose ref\n> pruning during\n> \n> ref packing:\n> > * Pack references:\n> ...\n> \n> > 4. prune_refs(): for each ref in the ref_to_prune list,\n> > \n> > call  prune_ref():\n> >     a. Lock the reference using lock_ref_sha1(),\n> >     verifying that the recorded SHA1 is still valid.  If\n> >     it is, unlink the loose reference file then free\n> >     the lock; otherwise leave the loose reference file\n> >     untouched.\n> \n> I think it would also therefore be able to replace the\n> loose ref locking in Michael's new ref-packing scheme as\n> well as the locking in Michael's new ref deletion scheme\n> (again steps\n> \n> 4):\n> > * Delete reference foo:\n> ...\n> \n> >   4. Delete loose ref for \"foo\":\n> >      a. Acquire the lock $GIT_DIR/refs/heads/foo.lock\n> >      \n> >      b. Unlink $GIT_DIR/refs/heads/foo if it is\n> >      unchanged.\n> >  \n> >  If it is changed, leave it untouched.  If it is\n> >  deleted,\n> > \n> > that is OK too.\n> > \n> >      c. Release lock $GIT_DIR/refs/heads/foo.lock\n> \n> ...\n> \n> > * Pack references:\n> ...\n> \n> >   4. prune_refs(): for each ref in the ref_to_prune\n> >   list,\n> > \n> > call prune_ref():\n> >      a. Lock the loose reference using lock_ref_sha1(),\n> > \n> > verifying that the recorded SHA1 is still valid\n> > \n> >      b. If it is, unlink the loose reference file\n> > \n> > (otherwise, leave it untouched)\n> > \n> >      c. Release the lock on the loose reference\n> \n> To be honest, I suspect I missed something obvious because\n> this seems almost too simple to work.  I am ashamed that\n> it took me so long to come up with (of course, I will be\n> even more ashamed :( when it is shown to be flawed!) \n> This scheme also feels extensible. if there are no\n> obvious flaws in it, I will try to post solutions for ref\n> packing and for multiple repository/ref transactions also\n> soon.\n> \n> I welcome any comments/criticisms,\n> \n> -Martin\n> --\n> To unsubscribe from this list: send the line \"unsubscribe\n> git\" in the body of a message to\n> majordomo@vger.kernel.org More majordomo info at \n> http://vger.kernel.org/majordomo-info.html\n"},{"id":"205971","messageId":"871B6C10EBEFE342A772D1159D1320853A011469@umechphj.easf.csd.disa.mil","threadId":"32426","inReplyTo":"201301031652.44982.mfick@codeaurora.org","subject":"RE: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Pyeron, Jason J CTR (US)","fromEmail":"jason.j.pyeron.ctr@mail.mil","sentAt":"2013-01-04T17:52:43Z","receivedAt":"2013-01-04T17:52:43Z","isPatch":true,"sender":{"key":"jason.j.pyeron.ctr@mail.mil","avatar":null},"body":"> From: Martin Fick\n> Sent: Thursday, January 03, 2013 6:53 PM\n> \n> Any thoughts on this idea?  Is it flawed?  I am trying to\n> write it up in a more formal generalized manner and was\n> hoping to get at least one \"it seems sane\" before I do.\n\nIf you are assuming that atomic renames, etc. are available, then you should identify a test case and a degrade operation path when it is not available.\n\n> \n> Thanks,\n> \n> -Martin\n> \n> On Monday, December 31, 2012 03:30:53 am Martin Fick wrote:\n> > On Thursday, December 27, 2012 04:11:51 pm Martin Fick\n> wrote:\n> > > It concerns me that git uses any locking at all, even\n> > > for refs since it has the potential to leave around\n> > > stale locks.\n> > > ...\n> > > [a previous not so great attempt to fix this]\n> > > ...\n> >\n> > I may have finally figured out a working loose ref update\n> > mechanism which I think can avoid stale locks.\n> > Unfortunately it requires atomic directory renames and\n> > universally unique identifiers (uuids).  These may be\n> > no-go criteria?  But I figure it is worth at least\n> > exploring this idea because of the potential benefits?\n> >\n> > The general approach is to setup a transaction and either\n> > commit or abort it.  A transaction can be setup by\n> > renaming an appropriately setup directory to the\n> > \"ref.lock\" name.  If the rename succeeds, the transaction\n> > is begun.  Any actor can abort the transaction (up until\n> > it is committed) by simply deleting the \"ref.lock\"\n> > directory, so it is not at risk of going stale.  However,\n> > once the actor who sets up the transaction commits it,\n> > deleting the \"ref.lock\" directory simply aids in cleaning\n> > it up for the next transaction (instead of aborting it).\n> >\n> > One important piece of the transaction is the use of\n> > uuids. The uuids provide a mechanism to tie the atomic\n> > commit pieces to the transactions and thus to prevent\n> > long sleeping process from inadvertently performing\n> > actions which could be out of date when they wake finally\n> > up.  In each case, the atomic commit piece is the\n> > renaming of a file.   For the create and update pieces, a\n> > file is renamed from the \"ref.lock\" dir to the \"ref\" file\n> > resulting in an update to the sha for the ref. However,\n> > in the delete case, the \"ref\" file is instead renamed to\n> > end up in the \"ref.lock\" directory resulting in a delete\n> > of the ref.  This scheme does not affect the way refs are\n> > read today,\n> >\n> > To prepare for a transaction, an actor first generates a\n> > uuid (an exercise I will delay for now).  Next, a tmp\n> > directory named after the uuid is generated in the parent\n> > directory for the ref to be updated, perhaps something\n> > like:  \".lock_uuid\". In this directory is places either a\n> > file or a directory named after the uuid, something like:\n> > \".lock_uuid/,uuid\".  In the case of a create or an\n> > update, the new sha is written to this file.  In the case\n> > of a delete, it is a directory.\n> >\n> > Once the tmp directory is setup, the initiating actor\n> > attempts to start the transaction by renaming the tmp\n> > directory to \"ref.lock\".  If the rename fails, the update\n> > fails. If the rename succeeds, the actor can then attempt\n> > to commit the transaction (before another actor aborts\n> > it).\n> >\n> > In the case of a create, the actor verifies that \"ref\"\n> > does not currently exist, and then renames the now named\n> > \"ref.lock/uuid\" file to \"ref\". On success, the ref was\n> > created.\n> >\n> > In the case of an update, the actor verifies that \"ref\"\n> > currently contains the old sha, and then also renames the\n> > now named \"ref.lock/uuid\" file to \"ref\". On success, the\n> > ref was updated.\n> >\n> > In the case of a delete, the actor may verify that \"ref\"\n> > currently contains the sha to \"prune\" if it needs to, and\n> > then renames the \"ref\" file to \"ref.lock/uuid/delete\". On\n> > success, the ref was deleted.\n> >\n> > Whether successful or not, the actor may now simply delete\n> > the \"ref.lock\" directory, clearing the way for a new\n> > transaction.  Any other actor may delete this directory at\n> > any time also, likely either on conflict (if they are\n> > attempting to initiate a transaction), or after a grace\n> > period just to cleanup the FS.  Any actor may also safely\n> > cleanup the tmp directories, preferably also after a grace\n> > period.\n> >\n> > One neat part about this scheme is that I believe it would\n> > be backwards compatible with the current locking\n> > mechanism since the transaction directory will simply\n> > appear to be a lock to older clients.  And the old lock\n> > file should continue to lock out these newer\n> > transactions.\n> >\n> > Due to this backwards compatibility, I believe that this\n> > could be incrementally employed today without affecting\n> > very much.  It could be deployed in place of any updates\n> > which only hold ref.locks to update the loose ref.  So\n> > for example I think it could replace step 4a below from\n> > Michael Haggerty's description of today's loose ref\n> > pruning during\n> >\n> > ref packing:\n> > > * Pack references:\n> > ...\n> >\n> > > 4. prune_refs(): for each ref in the ref_to_prune list,\n> > >\n> > > call  prune_ref():\n> > >     a. Lock the reference using lock_ref_sha1(),\n> > >     verifying that the recorded SHA1 is still valid.  If\n> > >     it is, unlink the loose reference file then free\n> > >     the lock; otherwise leave the loose reference file\n> > >     untouched.\n> >\n> > I think it would also therefore be able to replace the\n> > loose ref locking in Michael's new ref-packing scheme as\n> > well as the locking in Michael's new ref deletion scheme\n> > (again steps\n> >\n> > 4):\n> > > * Delete reference foo:\n> > ...\n> >\n> > >   4. Delete loose ref for \"foo\":\n> > >      a. Acquire the lock $GIT_DIR/refs/heads/foo.lock\n> > >\n> > >      b. Unlink $GIT_DIR/refs/heads/foo if it is\n> > >      unchanged.\n> > >\n> > >  If it is changed, leave it untouched.  If it is\n> > >  deleted,\n> > >\n> > > that is OK too.\n> > >\n> > >      c. Release lock $GIT_DIR/refs/heads/foo.lock\n> >\n> > ...\n> >\n> > > * Pack references:\n> > ...\n> >\n> > >   4. prune_refs(): for each ref in the ref_to_prune\n> > >   list,\n> > >\n> > > call prune_ref():\n> > >      a. Lock the loose reference using lock_ref_sha1(),\n> > >\n> > > verifying that the recorded SHA1 is still valid\n> > >\n> > >      b. If it is, unlink the loose reference file\n> > >\n> > > (otherwise, leave it untouched)\n> > >\n> > >      c. Release the lock on the loose reference\n> >\n> > To be honest, I suspect I missed something obvious because\n> > this seems almost too simple to work.  I am ashamed that\n> > it took me so long to come up with (of course, I will be\n> > even more ashamed :( when it is shown to be flawed!)\n> > This scheme also feels extensible. if there are no\n> > obvious flaws in it, I will try to post solutions for ref\n> > packing and for multiple repository/ref transactions also\n> > soon.\n> >\n> > I welcome any comments/criticisms,\n> >\n> > -Martin\n> > --\n> > To unsubscribe from this list: send the line \"unsubscribe\n> > git\" in the body of a message to\n> > majordomo@vger.kernel.org More majordomo info at\n> > http://vger.kernel.org/majordomo-info.html\n> --\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at  http://vger.kernel.org/majordomo-info.html\n"},{"id":"205972","messageId":"201301041101.02756.mfick@codeaurora.org","threadId":"32426","inReplyTo":"871B6C10EBEFE342A772D1159D1320853A011469@umechphj.easf.csd.disa.mil","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-01-04T18:01:02Z","receivedAt":"2013-01-04T18:01:02Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Friday, January 04, 2013 10:52:43 am Pyeron, Jason J \nCTR (US) wrote:\n> > From: Martin Fick\n> > Sent: Thursday, January 03, 2013 6:53 PM\n> > \n> > Any thoughts on this idea?  Is it flawed?  I am \ntrying\n> > to write it up in a more formal generalized manner \nand\n> > was hoping to get at least one \"it seems sane\" \nbefore\n> > I do.\n> \n> If you are assuming that atomic renames, etc. are\n> available, then you should identify a test case and a\n> degrade operation path when it is not available.\n\nThanks, sound reasonable.  Where you thinking a runtime \ntest case that would be run before every transaction?  I \nwas anticipating a per repo config option called \nsomething like \"core.locks = recoverable\" that would be \nneeded to turn them on?  I was thinking that this was \nsomething that server sites could test in advance on \ntheir repos and then enable it for them.  Maybe a git-\nlock tool with a --test-recoverable option?\n\n-Martin\n\n\n> > \n> > On Monday, December 31, 2012 03:30:53 am Martin Fick \nwrote:\n> > > On Thursday, December 27, 2012 04:11:51 pm Martin\n> > > Fick\n> > \n> > wrote:\n> > > > It concerns me that git uses any locking at all,\n> > > > even for refs since it has the potential to \nleave\n> > > > around stale locks.\n> > > > ...\n> > > > [a previous not so great attempt to fix this]\n> > > > ...\n> > > \n> > > I may have finally figured out a working loose ref\n> > > update mechanism which I think can avoid stale\n> > > locks. Unfortunately it requires atomic directory\n> > > renames and universally unique identifiers \n(uuids). \n> > > These may be no-go criteria?  But I figure it is\n> > > worth at least exploring this idea because of the\n> > > potential benefits?\n> > > \n> > > The general approach is to setup a transaction and\n> > > either commit or abort it.  A transaction can be\n> > > setup by renaming an appropriately setup directory\n> > > to the \"ref.lock\" name.  If the rename succeeds, \nthe\n> > > transaction is begun.  Any actor can abort the\n> > > transaction (up until it is committed) by simply\n> > > deleting the \"ref.lock\" directory, so it is not at\n> > > risk of going stale.  However, once the actor who\n> > > sets up the transaction commits it, deleting the\n> > > \"ref.lock\" directory simply aids in cleaning it up\n> > > for the next transaction (instead of aborting it).\n> > > \n> > > One important piece of the transaction is the use \nof\n> > > uuids. The uuids provide a mechanism to tie the\n> > > atomic commit pieces to the transactions and thus \nto\n> > > prevent long sleeping process from inadvertently\n> > > performing actions which could be out of date when\n> > > they wake finally up.  In each case, the atomic\n> > > commit piece is the renaming of a file.   For the\n> > > create and update pieces, a file is renamed from \nthe\n> > > \"ref.lock\" dir to the \"ref\" file resulting in an\n> > > update to the sha for the ref. However, in the\n> > > delete case, the \"ref\" file is instead renamed to\n> > > end up in the \"ref.lock\" directory resulting in a\n> > > delete of the ref.  This scheme does not affect \nthe\n> > > way refs are read today,\n> > > \n> > > To prepare for a transaction, an actor first\n> > > generates a uuid (an exercise I will delay for \nnow).\n> > >  Next, a tmp directory named after the uuid is\n> > > generated in the parent directory for the ref to \nbe\n> > > updated, perhaps something like:  \".lock_uuid\". In\n> > > this directory is places either a file or a\n> > > directory named after the uuid, something like:\n> > > \".lock_uuid/,uuid\".  In the case of a create or an\n> > > update, the new sha is written to this file.  In \nthe\n> > > case of a delete, it is a directory.\n> > > \n> > > Once the tmp directory is setup, the initiating \nactor\n> > > attempts to start the transaction by renaming the \ntmp\n> > > directory to \"ref.lock\".  If the rename fails, the\n> > > update fails. If the rename succeeds, the actor \ncan\n> > > then attempt to commit the transaction (before\n> > > another actor aborts it).\n> > > \n> > > In the case of a create, the actor verifies that\n> > > \"ref\" does not currently exist, and then renames \nthe\n> > > now named \"ref.lock/uuid\" file to \"ref\". On \nsuccess,\n> > > the ref was created.\n> > > \n> > > In the case of an update, the actor verifies that\n> > > \"ref\" currently contains the old sha, and then \nalso\n> > > renames the now named \"ref.lock/uuid\" file to \n\"ref\".\n> > > On success, the ref was updated.\n> > > \n> > > In the case of a delete, the actor may verify that\n> > > \"ref\" currently contains the sha to \"prune\" if it\n> > > needs to, and then renames the \"ref\" file to\n> > > \"ref.lock/uuid/delete\". On success, the ref was\n> > > deleted.\n> > > \n> > > Whether successful or not, the actor may now \nsimply\n> > > delete the \"ref.lock\" directory, clearing the way\n> > > for a new transaction.  Any other actor may delete\n> > > this directory at any time also, likely either on\n> > > conflict (if they are attempting to initiate a\n> > > transaction), or after a grace period just to\n> > > cleanup the FS.  Any actor may also safely cleanup\n> > > the tmp directories, preferably also after a grace\n> > > period.\n> > > \n> > > One neat part about this scheme is that I believe \nit\n> > > would be backwards compatible with the current\n> > > locking mechanism since the transaction directory\n> > > will simply appear to be a lock to older clients. \n> > > And the old lock file should continue to lock out\n> > > these newer transactions.\n> > > \n> > > Due to this backwards compatibility, I believe \nthat\n> > > this could be incrementally employed today without\n> > > affecting very much.  It could be deployed in \nplace\n> > > of any updates which only hold ref.locks to update\n> > > the loose ref.  So for example I think it could\n> > > replace step 4a below from Michael Haggerty's\n> > > description of today's loose ref pruning during\n> > > \n> > > ref packing:\n> > > > * Pack references:\n> > > ...\n> > > \n> > > > 4. prune_refs(): for each ref in the \nref_to_prune\n> > > > list,\n> > > > \n> > > > call  prune_ref():\n> > > >     a. Lock the reference using lock_ref_sha1(),\n> > > >     verifying that the recorded SHA1 is still\n> > > >     valid.  If it is, unlink the loose reference\n> > > >     file then free the lock; otherwise leave the\n> > > >     loose reference file untouched.\n> > > \n> > > I think it would also therefore be able to replace\n> > > the loose ref locking in Michael's new ref-packing\n> > > scheme as well as the locking in Michael's new ref\n> > > deletion scheme (again steps\n> > > \n> > > 4):\n> > > > * Delete reference foo:\n> > > ...\n> > > \n> > > >   4. Delete loose ref for \"foo\":\n> > > >      a. Acquire the lock\n> > > >      $GIT_DIR/refs/heads/foo.lock\n> > > >      \n> > > >      b. Unlink $GIT_DIR/refs/heads/foo if it is\n> > > >      unchanged.\n> > > >  \n> > > >  If it is changed, leave it untouched.  If it is\n> > > >  deleted,\n> > > > \n> > > > that is OK too.\n> > > > \n> > > >      c. Release lock \n$GIT_DIR/refs/heads/foo.lock\n> > > \n> > > ...\n> > > \n> > > > * Pack references:\n> > > ...\n> > > \n> > > >   4. prune_refs(): for each ref in the \nref_to_prune\n> > > >   list,\n> > > > \n> > > > call prune_ref():\n> > > >      a. Lock the loose reference using\n> > > >      lock_ref_sha1(),\n> > > > \n> > > > verifying that the recorded SHA1 is still valid\n> > > > \n> > > >      b. If it is, unlink the loose reference \nfile\n> > > > \n> > > > (otherwise, leave it untouched)\n> > > > \n> > > >      c. Release the lock on the loose reference\n> > > \n> > > To be honest, I suspect I missed something obvious\n> > > because this seems almost too simple to work.  I \nam\n> > > ashamed that it took me so long to come up with \n(of\n> > > course, I will be even more ashamed :( when it is\n> > > shown to be flawed!) This scheme also feels\n> > > extensible. if there are no obvious flaws in it, I\n> > > will try to post solutions for ref packing and for\n> > > multiple repository/ref transactions also soon.\n> > > \n> > > I welcome any comments/criticisms,\n> > > \n> > > -Martin\n> > > --\n> > > To unsubscribe from this list: send the line\n> > > \"unsubscribe git\" in the body of a message to\n> > > majordomo@vger.kernel.org More majordomo info at\n> > > http://vger.kernel.org/majordomo-info.html\n> > \n> > --\n> > To unsubscribe from this list: send the line\n> > \"unsubscribe git\" in the body of a message to\n> > majordomo@vger.kernel.org More majordomo info at \n> > http://vger.kernel.org/majordomo-info.html\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n"},{"id":"205981","messageId":"7vip7ctz7j.fsf@alter.siamese.dyndns.org","threadId":"32426","inReplyTo":"201301031652.44982.mfick@codeaurora.org","subject":"Re: Lockless Refs?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-01-04T21:28:32Z","receivedAt":"2013-01-04T21:28:32Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Fick <mfick@codeaurora.org> writes:\n\n> Any thoughts on this idea?  Is it flawed?  I am trying to \n> write it up in a more formal generalized manner and was \n> hoping to get at least one \"it seems sane\" before I do.\n\nThe general impression I have been getting was that this isn't even\nworth the effort and the resulting complexity of the code, given\nPeff's observations earlier in the thread that ref update conflicts\nand leftover locks are reasonably rare in practice.  But perhaps I\nhas been mis-reading the discussion.\n\nI also have this suspicion that if you really want to shoot for\nmulti-repository transactions in an massively scaled repository\nhosting environment, you would rather want to not rely on hacks\nbased on filesystem semantics, but instead want to RPC with a\ndedicated \"ref management service\" that knows the transaction\nsemantics you want, but that could become a much larger change.\n\nI dunno.\n"},{"id":"206035","messageId":"20130105161215.GA24900@sigill.intra.peff.net","threadId":"32426","inReplyTo":"201212310330.53835.mfick@codeaurora.org","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-01-05T16:12:15Z","receivedAt":"2013-01-05T16:12:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Dec 31, 2012 at 03:30:53AM -0700, Martin Fick wrote:\n\n> The general approach is to setup a transaction and either \n> commit or abort it.  A transaction can be setup by renaming \n> an appropriately setup directory to the \"ref.lock\" name.  If \n> the rename succeeds, the transaction is begun.  Any actor can \n> abort the transaction (up until it is committed) by simply \n> deleting the \"ref.lock\" directory, so it is not at risk of \n> going stale.\n\nDeleting a directory is not atomic, as you first have to remove the\ncontents, putting it into a potentially inconsistent state. I'll assume\nyou deal with that later...\n\n> One important piece of the transaction is the use of uuids.  \n> The uuids provide a mechanism to tie the atomic commit pieces \n> to the transactions and thus to prevent long sleeping process \n> from inadvertently performing actions which could be out of \n> date when they wake finally up.\n\nHas this been a problem for you in practice? Avoiding this is one of the\nreasons that git does not take out long locks; instead, it takes the\nlock only at the moment it is ready to write, and aborts if it has been\nupdated since the longer-term operation began. This has its own problems\n(you might do a lot of work only to have your operation aborted), but I\nam not sure that your proposal improves on that.\n\nYour proposal does sound like it could potentially improve robustness\nwhen killing stale transactions (i.e., you know that the transaction\noriginator will never wake up and think it still has the lock). But\nagain, is that a problem in practice? Git typically holds ref locks for\na few syscalls. If you are conservative about leaving potentially stale\nlocks in place (e.g., give them a few minutes to complete before\nassuming they are now bogus), you will not run into that problem.\n\nThe more conservative you are about treating a lock as stale, of course,\nthe less performant you will be in the face of stale locks. But since\nthey're the exception, that isn't a big problem in practice (at least it\nhas not been for me).\n\n> In each case, the atomic \n> commit piece is the renaming of a file.   For the create and \n> update pieces, a file is renamed from the \"ref.lock\" dir to \n> the \"ref\" file resulting in an update to the sha for the ref.\n\nI think we've had problems with cross-directory renames on some\nfilesystems, but I don't recall the details. I know that Coda does not\nlike cross-directory links, but cross-directory renames are OK (and in\nfact we fall back to the latter when the former does not work).\n\nAh, here we go: 5723fe7 (Avoid cross-directory renames and linking on\nobject creation, 2008-06-14). Looks like NFS is the culprit.\n\n> In the case of a delete, the actor may verify that \"ref\" \n> currently contains the sha to \"prune\" if it needs to, and \n> then renames the \"ref\" file to \"ref.lock/uuid/delete\". On \n> success, the ref was deleted.\n> \n> Whether successful or not, the actor may now simply delete \n> the \"ref.lock\" directory, clearing the way for a new \n> transaction.  Any other actor may delete this directory at \n> any time also, likely either on conflict (if they are \n> attempting to initiate a transaction), or after a grace \n> period just to cleanup the FS.  Any actor may also safely \n> cleanup the tmp directories, preferably also after a grace \n> period.\n\nHmm. So what happens to the \"delete\" file when the ref.lock directory is\nbeing deleted? Presumably deleting the ref.lock directory means doing it\nrecursively (which is non-atomic). But then why are we keeping the\ndelete file at all, if we're just about to remove it?\n\nWhat happens if another process wants to cancel a transaction that is\npartially done? That is, the ref.lock directory is created, but it\ncontains the uuid subdir? It sounds like it's OK to just delete from it,\nand the original process will then fail at its rename?\n\n> One neat part about this scheme is that I believe it would be \n> backwards compatible with the current locking mechanism since \n> the transaction directory will simply appear to be a lock to \n> older clients.  And the old lock file should continue to lock \n> out these newer transactions.\n\nYeah, I don't see anything that would prevent that. The current code\nonly cares about open(\"$ref.lock\", O_EXCL). But that should be correct\nand atomic with respect to the renamed directories. You are depending on\natomic directory renames. Those aren't used anywhere yet in git, as far\nas I know. So that may run into problems (but there's no reason this\nsystem couldn't be optional for filesystems that are more abled, and\nother systems could fall back to the straight-file locking).\n\n\nSo in response to your question, no, I don't see any real showstoppers\nhere. And unlike the \"all refs are files in a directory\" scheme, it's\nconfined to writing, which solves the readdir() atomicity questions I\nhad there.\n\nI still can't say I'm super excited about it, just because it seems like\na solution in search of a problem that I have not experienced myself.\nBut if it's solving a problem for you, I don't want to discourage you\nfrom pursuing it.\n\n> To be honest, I suspect I missed something obvious because \n> this seems almost too simple to work.  I am ashamed that it \n> took me so long to come up with (of course, I will be even \n> more ashamed :( when it is shown to be flawed!)  This scheme \n> also feels extensible. if there are no obvious flaws in it, I \n> will try to post solutions for ref packing and for multiple \n> repository/ref transactions also soon.\n\nFixing the minor remaining races on ref packing would be nice, but I do\nnot think those are a problem of the on-disk lock representation. The\nreason they are not fixed now is from an attempt to keep lock contention\nlow between unrelated updates (something which we should probably give\nup on in favor of correctness; but that is orthogonal to whether we do\nit with the existing file locks or with a new system).\n\nA much stronger fix for that would be to record deletes in the loose ref\nstorage so that we don't have to update the packed-refs file as often\n(because it is inherently a lock bottleneck, and because it is wasteful\nwhen you have a very large number of refs). But that means dealing with\ndirectory/file conflicts between deleted and existing branches, which is\na pain.\n\n-Peff\n"},{"id":"206242","messageId":"201301071114.22526.mfick@codeaurora.org","threadId":"32426","inReplyTo":"201301071109.12086.mfick@codeaurora.org","subject":"Re: [PATCH] refs: do not use cached refs in repack_without_ref","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-01-07T18:14:22Z","receivedAt":"2013-01-07T18:14:22Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"...[Sorry about the previous HTML reposts]\n\nJeff King <peff@peff.net> wrote:\n>On Mon, Dec 31, 2012 at 03:30:53AM -0700, Martin Fick \nwrote:\n>\n>> The general approach is to setup a transaction and\n>> either commit or abort it. A transaction can be setup\n>> by renaming an appropriately setup directory to the\n>> \"ref.lock\" name. If the rename succeeds, the\n>> transaction is begun. Any actor can abort the\n>> transaction (up until it is committed) by simply\n>> deleting the \"ref.lock\" directory, so it is not at\n>> risk of going stale.\n>\n> Deleting a directory is not atomic, as you first have\n> to remove the contents, putting it into a potentially\n> inconsistent state. I'll assume you deal with that\n> later...\n\nRight, these simple single file transactions have at \nbest 1 important file/directory in them, once deleted \nthe transaction is aborted (can no longer complete).  \nHowever to support multi file transactions, a better \napproach is likely to rename the uuid directory to have \na .delete extension before deleting stuff in it.\n\n\n> > One important piece of the transaction is the use\n> > of uuids. The uuids provide a mechanism to tie the\n> > atomic commit pieces to the transactions and thus to\n> > prevent long sleeping process from inadvertently\n> > performing actions which could be out of date when\n> > they wake finally up.\n> >\n>Has this been a problem for you in practice?\n\nNo, but as you say, we don't currently hold locks for \nvery long. I anticipate it being a problem in a \nclustered environment when transactions start spanning \nrepos from java processes, with insane amounts of RAM, \nwhich can sometimes have unpredictable indeterminately \nlong java GC cycles at inopportune times.. It would seem \nshort sighted if Gerrit at least did not assume this \nwill be a problem.\n\nBut, deletes today in git are not so short and Michael's \nfixes may make things worse? But, as you point out, that \nshould perhaps be solved a different way.\n\n\n> Avoiding this is one of the reasons that git does not\n> take out long locks; instead, it takes the lock only\n> at the moment it is ready to write, and aborts if it\n> has been updated since the longer-term operation\n> began. This has its own problems (you might do a lot\n> of work only to have your operation aborted), but I\n> am not sure that your proposal improves on that.\n\nIt does not, it might increase this.\n\n\n> Git typically holds ref locks for a few syscalls. If\n> you are conservative about leaving potentially stale\n> locks in place (e.g., give them a few minutes to\n> complete before assuming they are now bogus), you will\n> not run into that problem.\n\nIn a distributed environment even a few minutes might \nnot be enough, processes could be on a remote server \nwith a temporarily split network, that could cause \ndelays longer than your typical local expectations.\n\nBut there is also the other piece of this problem, how \ndo you detect stale locks? How long will it be stale \nuntil a user figures it out and reports it? How many \nother users will simply have failed pushes and wonder \nwhy without reporting them?\n\n\n> > In each case, the atomic commit piece is the\n> > renaming of a file. For the create and update\n> > pieces, a file is renamed from the \"ref.lock\" \n> > dir to the \"ref\" file resulting in an update to \n> > the sha for the ref.\n>\n> I think we've had problems with cross-directory\n> renames on some filesystems, but I don't recall the\n> details. I know that Coda does not like \n> cross-directory links, but cross-directory renames \n> are OK (and in fact we fall back to the latter when\n> the former does not work).\n>\n> Ah, here we go: 5723fe7 (Avoid cross-directory renames\n> and linking on object creation, 2008-06-14). Looks\n> like NFS is the culprit.\n\nIf the renames fail we can fall back to regular file \nlocking, the hard part to detect and deal with would be \nif the renames don't fail but become copies/mkdirs.\n\n\n>> In the case of a delete, the actor may verify that\n>> \"ref\" currently contains the sha to \"prune\" if it\n>> needs to, and then renames the \"ref\" file to\n>> \"ref.lock/uuid/delete\". On success, the ref was\n>> deleted.\n>>\n>> Whether successful or not, the actor may now simply\n>> delete the \"ref.lock\" directory, clearing the way for\n>> a new transaction. Any other actor may delete this\n>> directory at any time also, likely either on conflict\n>> (if they are attempting to initiate a transaction),\n>> or after a grace period just to cleanup the FS. Any\n>> actor may also safely cleanup the tmp directories,\n>> preferably also after a grace period.\n>\n> Hmm. So what happens to the \"delete\" file when the\n> ref.lock directory is being deleted? Presumably\n> deleting the ref.lock directory means doing it\n> recursively (which is non-atomic). But then why are \n> we keeping the delete file at all, if we're just about\n> to remove it?\n\nWe are not trying to keep it, but we need to ensure that \nour transaction has not yet been aborted: the rename \ndoes this.  If we just deleted the file, we may sleep \nand another transaction may abort our transaction and \ncomplete before we wake up and actually delete the file. \nBut by using a rename we tie the delete atomically to \nthe transaction, it cannot succeed if our transaction \nwas aborted during a sleep since the directory we are \nrenaming the file into would be gone! This is sort of \nthe magic piece that makes the whole scheme special, \nsafe deletes tend to be the hardest part.\n\n\n>What happens if another process wants to cancel a\n> transaction that is partially done? That is, the\n> ref.lock directory is created, but it contains the\n> uuid subdir? It sounds like it's OK to just delete\n> from it, and the original process will then fail at\n> its rename?\n\nYes, exactly.  But again, it might be better to cause a \nrename of the uuid dir before deleting it.\n\n\n>> One neat part about this scheme is that I believe it\n>> would be backwards compatible with the current\n>> locking mechanism since the transaction directory\n>> will simply appear to be a lock to older clients. \n>> And the old lock file should continue to lock\n>> out these newer transactions.\n>\n>Yeah, I don't see anything that would prevent that. \n> The current code only cares about open(\"$ref.lock\",\n> O_EXCL). But that should be correct and atomic with\n> respect to the renamed directories. You are depending\n> on atomic directory renames. Those aren't used\n> anywhere yet in git, as far as I know. So that may run\n> into problems (but there's no reason this system\n> couldn't be optional for filesystems that are more\n> abled, and other systems could fall back to the\n> straight-file locking).\n\nRight.\n\n\n> So in response to your question, no, I don't see any\n> real showstoppers here. \n\nAlright, cool, thanks for the review and analysis, I \nappreciate it.\n\n\n> And unlike the \"all refs are files in a directory\"\n> scheme, it's confined to writing, which solves the\n> readdir() atomicity questions I had there.\n\n\nRight, I couldn't see a way around those, I think it was \ninherently flawed.\n\n\n> I still can't say I'm super excited about it, just\n> because it seems like a solution in search of a\n> problem that I have not experienced myself.\n\nIt might be.  But at least a solution is out there now. \nIf time indicates that it is needed, I feel better \nknowing there is a solution. \n\nMurphy has a way of making unlikely problems real \nannoyances in automated distributed environments. The \nproblem is not usually one real annoying problem, those \nget fixed. The problem we deal mostly with is 1000 \ninfrequent problems, all different, but they add up to a \nsystem which needs constant maintenance. And the \nmaintenance is hard since each problem is different, the \nanalysis is difficult and requires expertise.\n\n\n> Fixing the minor remaining races on ref packing would\n> be nice, but I do not think those are a problem of the\n> on-disk lock representation. The reason they are not\n> fixed now is from an attempt to keep lock contention\n> low between unrelated updates (something which we\n> should probably give up on in favor of correctness;\n> but that is orthogonal to whether we do it with the\n> existing file locks or with a new system).\n\nAgreed.\n\n\n>A much stronger fix for that would be to record deletes\n> in the loose ref storage so that we don't have to\n> update the packed-refs file as often (because it is\n> inherently a lock bottleneck, and because it is\n> wasteful when you have a very large number of refs).\n> But that means dealing with directory/file conflicts\n> between deleted and existing branches, which is a\n> pain.\n\nMakes sense.\n\nThanks again for your thoughts,\n\n-Martin\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n"},{"id":"207469","messageId":"CAM9Z-nmJb3LGO3wLxPYhwc+7Cyw7J8q1E_PppNYQSmXKQ2ieQQ@mail.gmail.com","threadId":"32426","inReplyTo":"20130105161215.GA24900@sigill.intra.peff.net","subject":"Re: Lockless Refs? (Was [PATCH] refs: do not use cached refs in repack_without_ref)","fromName":"Drew Northup","fromEmail":"n1xim.email@gmail.com","sentAt":"2013-01-22T04:31:03Z","receivedAt":"2013-01-22T04:31:03Z","isPatch":true,"sender":{"key":"n1xim.email@gmail.com","avatar":null},"body":"On Sat, Jan 5, 2013 at 11:12 AM, Jeff King <peff@peff.net> wrote:\n> On Mon, Dec 31, 2012 at 03:30:53AM -0700, Martin Fick wrote:\n>\n>> The general approach is to setup a transaction and either\n>> commit or abort it.  A transaction can be setup by renaming\n>> an appropriately setup directory to the \"ref.lock\" name.  If\n>> the rename succeeds, the transaction is begun.  Any actor can\n>> abort the transaction (up until it is committed) by simply\n>> deleting the \"ref.lock\" directory, so it is not at risk of\n>> going stale.\n>\n> Deleting a directory is not atomic, as you first have to remove the\n> contents, putting it into a potentially inconsistent state. I'll assume\n> you deal with that later...\n\nI know I'm a bit late to the dance here, but FWIW the apparent atomicy\n(odd conjugation there) of directory deletion depends largely upon the\nfilesystem and VFS api in use. It is not unheard of that a delete\noperation actually consist of moving the reference to the item's own\nallocation marker into a \"trashcan\" to be cleaned up after later.\nIn other words, I'd not advise planning on directory deletes always\nbeing atomic nor always not being atomic.\n\n-- \n-Drew Northup\n--------------------------------------------------------------\n\"As opposed to vegetable or mineral error?\"\n-John Pescatore, SANS NewsBites Vol. 12 Num. 59\n"}]}