Use the same ordering/locking in delete() as C git

Following the examples of cgit, lock packed-refs *before* checking for
existance of refs in it [1] and *keep the lock* until the loose ref (if
any) is removed [2]. The packed-refs lock is kept even when no
packed-refs update is required [3] so that somebody else doesn't pack a
reference that we are trying to delete.

This fixes a concurrency issue that happens on projects with a
substantial amount of refs(>~500k) where packing takes long enough for a
ref deletion to be triggered half way through it. Not locking the
packed-refs file before checking if the refs exists is not safe, as it
opens up situations where loose refs are repacked in memory and locked
on disk, but before the lock is released and packed-refs is flushed to
disk, a ref is deleted.

As packed-refs was NOT locked while checking wether a ref existed in it,
the current content on disk was read, which was about to be overwritten
and did not contain the ref about to be deleted. As the delete doesn't
see the ref in the current, on-disk, version of packed refs, it skips
processing altogether and moves on, correctly, deleting only the
associated loose ref and leaving the packed one behind.

Once the new packed-refs, containing the ref that was just deleted, was
commited to disk, the ref would come back to life.

Therefore, the packed-refs needs to be locked before checking if it
contains a ref or not in the same way the C implementation of Git does
at [1].

There are tradeoffs, though, in this decision, which will reduce the
parallelism of deleting loose refs and performing the refs repacking,
which happens very often in certain JGit implementations like Gerrit
Code Review. Before this change, repacking of refs and removal of loose
refs unrelated to the in-flight repacking was possible without involving
any locking; after this change, all loose refs removals have to wait for
the packing of refs to be completed, even though the repacking and the
refs removals were completely unrelated and their namespaces disjoint.
See more details on the test's performance results and the associated
tradeoffs in the Issue jgit-152.

NOTE: This delete ref locking logic was incorrect regardless of how the
packing of the refs is implemented. Making decisions if the pack
transaction is needed or not on an unlocked resource is racy and also
flagged as bug at [1].

[1]https://github.com/git/git/blob/master/refs/packed-backend.c#L1590
[2]https://github.com/git/git/blob/master/refs/files-backend.c#L3261
[3]https://github.com/git/git/blob/master/refs/files-backend.c#L2943

Bug: jgit-152
Change-Id: I158ec837904617c5fdf667e295ae667b2f037945

1 files changed, 32 insertions, 26 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java
index 8e57bf9f2f..321584b56b 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/RefDirectory.java
@@ -678,41 +678,47 @@ public class RefDirectory extends RefDatabase {
 		}
 		String name = dst.getName();
 
-		// Write the packed-refs file using an atomic update. We might
-		// wind up reading it twice, before and after the lock, to ensure
-		// we don't miss an edit made externally.
-		PackedRefList packed = getPackedRefs();
-		if (packed.contains(name)) {
-			inProcessPackedRefsLock.lock();
+		// Get and keep the packed-refs lock while updating packed-refs and
+		// removing any loose ref
+		inProcessPackedRefsLock.lock();
+		try {
+			LockFile lck = lockPackedRefsOrThrow();
 			try {
-				LockFile lck = lockPackedRefsOrThrow();
-				try {
+				// Write the packed-refs file using an atomic update. We might
+				// wind up reading it twice, before and after checking if the
+				// ref to delete is included or not, to ensure
+				// we don't rely on a PackedRefList that is a result of in-memory
+				// or NFS caching.
+				PackedRefList packed = getPackedRefs();
+				if (packed.contains(name)) {
+					// Force update our packed-refs snapshot before writing
 					packed = refreshPackedRefs();
 					int idx = packed.find(name);
 					if (0 <= idx) {
 						commitPackedRefs(lck, packed.remove(idx), packed, true);
 					}
-				} finally {
-					lck.unlock();
 				}
-			} finally {
-				inProcessPackedRefsLock.unlock();
-			}
-		}
 
-		RefList<LooseRef> curLoose, newLoose;
-		do {
-			curLoose = looseRefs.get();
-			int idx = curLoose.find(name);
-			if (idx < 0)
-				break;
-			newLoose = curLoose.remove(idx);
-		} while (!looseRefs.compareAndSet(curLoose, newLoose));
+				RefList<LooseRef> curLoose, newLoose;
+				do {
+					curLoose = looseRefs.get();
+					int idx = curLoose.find(name);
+					if (idx < 0) {
+						break;
+					}
+					newLoose = curLoose.remove(idx);
+				} while (!looseRefs.compareAndSet(curLoose, newLoose));
 
-		int levels = levelsIn(name) - 2;
-		delete(logFor(name), levels);
-		if (dst.getStorage().isLoose()) {
-			deleteAndUnlock(fileFor(name), levels, update);
+				int levels = levelsIn(name) - 2;
+				delete(logFor(name), levels);
+				if (dst.getStorage().isLoose()) {
+					deleteAndUnlock(fileFor(name), levels, update);
+				}
+			} finally {
+				lck.unlock();
+			}
+		} finally {
+			inProcessPackedRefsLock.unlock();
 		}
 
 		modCnt.incrementAndGet();