[JGIT PATCH (RESEND) 0/4] Fix race condition on loading pack files

[JGIT PATCH (RESEND) 0/4] Fix race condition on loading pack files

[Shawn O. Pearce]

I had sent this series while you were on vacation, so I assume it
just got lost in the shuffle and am resending.

This series tries to fix a "racy git" problem when reading pack
files in a repository; its possible that the directory is modified,
read and modified again in the same filesystem timestamp, resulting
in the reader not noticing the second modification.  This may cause
a reader to lose access to objects on disk.

Shawn O. Pearce (4):
  Avoid unnecessary stat when scanning packs in the objects directory
  Make ObjectDirectory last modified time atomically updated with list
  Don't create new pack lists if the directory hasn't changed
  Fix racy condition when a repository is repacked

 .../src/org/spearce/jgit/lib/ObjectDirectory.java  |  235 ++++++++++++-------
 1 files changed, 148 insertions(+), 87 deletions(-)

[JGIT PATCH (RESEND) 1/4] Avoid unnecessary stat when scanning packs in the objects directory

[Shawn O. Pearce]

We only care that the pack name exists in the directory at this stage
of processing.  Performing a isFile() test against the pack file name
is likely to be slower than checking an in-memory HashSet, since the
OS call has to actually check the inode to determine whether or not
the name is a file, or some other node type.  Since we already have
forced the OS to give us a complete listing of the paths, its just
faster to consult that existing list.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/ObjectDirectory.java  |   49 +++++++++++--------
 1 files changed, 28 insertions(+), 21 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
index 7cc459c..4419f9c 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
@@ -41,14 +41,16 @@
 import java.io.File;
 import java.io.FileNotFoundException;
 import java.io.FileReader;
-import java.io.FilenameFilter;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.concurrent.atomic.AtomicReference;
 
 import org.spearce.jgit.errors.PackMismatchException;
@@ -339,11 +341,23 @@ private static boolean inList(final PackFile[] list, final PackFile pack) {
 
 	private PackFile[] scanPacksImpl(final PackFile[] old) {
 		final Map<String, PackFile> forReuse = reuseMap(old);
-		final String[] idxList = listPackIdx();
-		final List<PackFile> list = new ArrayList<PackFile>(idxList.length);
-		for (final String indexName : idxList) {
+		final Set<String> names = listPackDirectory();
+		final List<PackFile> list = new ArrayList<PackFile>(names.size() >> 2);
+		for (final String indexName : names) {
+			// Must match "pack-[0-9a-f]{40}.idx" to be an index.
+			//
+			if (indexName.length() != 49 || !indexName.endsWith(".idx"))
+				continue;
+
 			final String base = indexName.substring(0, indexName.length() - 4);
 			final String packName = base + ".pack";
+			if (!names.contains(packName)) {
+				// Sometimes C Git's HTTP fetch transport leaves a
+				// .idx file behind and does not download the .pack.
+				// We have to skip over such useless indexes.
+				//
+				continue;
+			}
 
 			final PackFile oldPack = forReuse.remove(packName);
 			if (oldPack != null) {
@@ -352,14 +366,6 @@ private static boolean inList(final PackFile[] list, final PackFile pack) {
 			}
 
 			final File packFile = new File(packDirectory, packName);
-			if (!packFile.isFile()) {
-				// Sometimes C Git's HTTP fetch transport leaves a
-				// .idx file behind and does not download the .pack.
-				// We have to skip over such useless indexes.
-				//
-				continue;
-			}
-
 			final File idxFile = new File(packDirectory, indexName);
 			list.add(new PackFile(idxFile, packFile));
 		}
@@ -401,16 +407,17 @@ private static boolean inList(final PackFile[] list, final PackFile pack) {
 		return forReuse;
 	}
 
-	private String[] listPackIdx() {
+	private Set<String> listPackDirectory() {
 		packDirectoryLastModified = packDirectory.lastModified();
-		final String[] idxList = packDirectory.list(new FilenameFilter() {
-			public boolean accept(final File baseDir, final String n) {
-				// Must match "pack-[0-9a-f]{40}.idx" to be an index.
-				return n.length() == 49 && n.endsWith(".idx")
-						&& n.startsWith("pack-");
-			}
-		});
-		return idxList != null ? idxList : new String[0];
+		final String[] nameList = packDirectory.list();
+		if (nameList == null)
+			return Collections.emptySet();
+		final Set<String> nameSet = new HashSet<String>(nameList.length << 1);
+		for (final String name : nameList) {
+			if (name.startsWith("pack-"))
+				nameSet.add(name);
+		}
+		return nameSet;
 	}
 
 	@Override
-- 
1.6.4.225.gb589e

[JGIT PATCH (RESEND) 2/4] Make ObjectDirectory last modified time atomically updated with list

[Shawn O. Pearce]

By moving the last modified time and the PackFile[] into the same
object and using that object as the atomic access unit we ensure
that the two values change atomically for all readers.

This refactoring step prepares the code so we can later fix a race
condition where the objects directory is modified multiple times in
the same filesystem clock window, but a reader scanned the directory
during that same clock window.

A nice cleanup performed here is to eliminate the null pointer value
from the packList reference field.  Instead of getting a null we
get NO_PACKS, which uses an "impossible" last modified time of -1,
forcing any caller to scan the directory the first time a pack
is required.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/ObjectDirectory.java  |  126 ++++++++++----------
 1 files changed, 63 insertions(+), 63 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
index 4419f9c..5b28207 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
@@ -66,7 +66,7 @@
  * {@link PackFile}s.
  */
 public class ObjectDirectory extends ObjectDatabase {
-	private static final PackFile[] NO_PACKS = {};
+	private static final PackList NO_PACKS = new PackList(-1, new PackFile[0]);
 
 	private final File objects;
 
@@ -76,9 +76,7 @@
 
 	private final File alternatesFile;
 
-	private final AtomicReference<PackFile[]> packList;
-
-	private volatile long packDirectoryLastModified;
+	private final AtomicReference<PackList> packList;
 
 	/**
 	 * Initialize a reference to an on-disk object directory.
@@ -91,8 +89,7 @@ public ObjectDirectory(final File dir) {
 		infoDirectory = new File(objects, "info");
 		packDirectory = new File(objects, "pack");
 		alternatesFile = new File(infoDirectory, "alternates");
-
-		packList = new AtomicReference<PackFile[]>();
+		packList = new AtomicReference<PackList>(NO_PACKS);
 	}
 
 	/**
@@ -116,13 +113,10 @@ public void create() throws IOException {
 
 	@Override
 	public void closeSelf() {
-		PackFile[] packs = packList.get();
-		if (packs != null) {
-			packList.set(null);
-			for (final PackFile p : packs) {
-				p.close();
-			}
-		}
+		final PackList packs = packList.get();
+		packList.set(NO_PACKS);
+		for (final PackFile p : packs.packs)
+			p.close();
 	}
 
 	/**
@@ -176,7 +170,7 @@ public String toString() {
 
 	@Override
 	protected boolean hasObject1(final AnyObjectId objectId) {
-		for (final PackFile p : packs()) {
+		for (final PackFile p : packList.get().packs) {
 			try {
 				if (p.hasObject(objectId)) {
 					return true;
@@ -196,9 +190,9 @@ protected boolean hasObject1(final AnyObjectId objectId) {
 	@Override
 	protected ObjectLoader openObject1(final WindowCursor curs,
 			final AnyObjectId objectId) throws IOException {
-		PackFile[] pList = packs();
+		PackList pList = packList.get();
 		SEARCH: for (;;) {
-			for (final PackFile p : pList) {
+			for (final PackFile p : pList.packs) {
 				try {
 					final PackedObjectLoader ldr = p.get(curs, objectId);
 					if (ldr != null) {
@@ -224,9 +218,9 @@ protected ObjectLoader openObject1(final WindowCursor curs,
 	void openObjectInAllPacks1(final Collection<PackedObjectLoader> out,
 			final WindowCursor curs, final AnyObjectId objectId)
 			throws IOException {
-		PackFile[] pList = packs();
+		PackList pList = packList.get();
 		SEARCH: for (;;) {
-			for (final PackFile p : pList) {
+			for (final PackFile p : pList.packs) {
 				try {
 					final PackedObjectLoader ldr = p.get(curs, objectId);
 					if (ldr != null) {
@@ -265,8 +259,8 @@ protected ObjectLoader openObject2(final WindowCursor curs,
 
 	@Override
 	protected boolean tryAgain1() {
-		final PackFile[] old = packList.get();
-		if (packDirectoryLastModified < packDirectory.lastModified()) {
+		final PackList old = packList.get();
+		if (old.tryAgain(packDirectory.lastModified())) {
 			scanPacks(old);
 			return true;
 		}
@@ -274,57 +268,46 @@ protected boolean tryAgain1() {
 	}
 
 	private void insertPack(final PackFile pf) {
-		PackFile[] o, n;
+		PackList o, n;
 		do {
-			o = packs();
-			n = new PackFile[1 + o.length];
-			n[0] = pf;
-			System.arraycopy(o, 0, n, 1, o.length);
+			o = packList.get();
+			final PackFile[] oldList = o.packs;
+			final PackFile[] newList = new PackFile[1 + oldList.length];
+			newList[0] = pf;
+			System.arraycopy(oldList, 0, newList, 1, oldList.length);
+			n = new PackList(o.lastModified, newList);
 		} while (!packList.compareAndSet(o, n));
 	}
 
 	private void removePack(final PackFile deadPack) {
-		PackFile[] o, n;
+		PackList o, n;
 		do {
 			o = packList.get();
-			if (o == null || !inList(o, deadPack)) {
-				break;
 
-			} else if (o.length == 1) {
-				n = NO_PACKS;
+			final PackFile[] oldList = o.packs;
+			final int j = indexOf(oldList, deadPack);
+			if (j < 0)
+				break;
 
-			} else {
-				n = new PackFile[o.length - 1];
-				int j = 0;
-				for (final PackFile p : o) {
-					if (p != deadPack) {
-						n[j++] = p;
-					}
-				}
-			}
+			final PackFile[] newList = new PackFile[oldList.length - 1];
+			System.arraycopy(oldList, 0, newList, 0, j);
+			System.arraycopy(oldList, j + 1, newList, j, newList.length - j);
+			n = new PackList(o.lastModified, newList);
 		} while (!packList.compareAndSet(o, n));
 		deadPack.close();
 	}
 
-	private static boolean inList(final PackFile[] list, final PackFile pack) {
-		for (final PackFile p : list) {
-			if (p == pack) {
-				return true;
-			}
+	private static int indexOf(final PackFile[] list, final PackFile pack) {
+		for (int i = 0; i < list.length; i++) {
+			if (list[i] == pack)
+				return i;
 		}
-		return false;
-	}
-
-	private PackFile[] packs() {
-		PackFile[] r = packList.get();
-		if (r == null)
-			r = scanPacks(null);
-		return r;
+		return -1;
 	}
 
-	private PackFile[] scanPacks(final PackFile[] original) {
+	private PackList scanPacks(final PackList original) {
 		synchronized (packList) {
-			PackFile[] o, n;
+			PackList o, n;
 			do {
 				o = packList.get();
 				if (o != original) {
@@ -333,14 +316,15 @@ private static boolean inList(final PackFile[] list, final PackFile pack) {
 					//
 					return o;
 				}
-				n = scanPacksImpl(o != null ? o : NO_PACKS);
+				n = scanPacksImpl(o);
 			} while (!packList.compareAndSet(o, n));
 			return n;
 		}
 	}
 
-	private PackFile[] scanPacksImpl(final PackFile[] old) {
+	private PackList scanPacksImpl(final PackList old) {
 		final Map<String, PackFile> forReuse = reuseMap(old);
+		final long lastModified = packDirectory.lastModified();
 		final Set<String> names = listPackDirectory();
 		final List<PackFile> list = new ArrayList<PackFile>(names.size() >> 2);
 		for (final String indexName : names) {
@@ -374,17 +358,17 @@ private static boolean inList(final PackFile[] list, final PackFile pack) {
 			p.close();
 		}
 
-		if (list.isEmpty()) {
-			return NO_PACKS;
-		}
+		if (list.isEmpty())
+			return new PackList(lastModified, NO_PACKS.packs);
+
 		final PackFile[] r = list.toArray(new PackFile[list.size()]);
 		Arrays.sort(r, PackFile.SORT);
-		return r;
+		return new PackList(lastModified, r);
 	}
 
-	private static Map<String, PackFile> reuseMap(final PackFile[] old) {
+	private static Map<String, PackFile> reuseMap(final PackList old) {
 		final Map<String, PackFile> forReuse = new HashMap<String, PackFile>();
-		for (final PackFile p : old) {
+		for (final PackFile p : old.packs) {
 			if (p.invalid()) {
 				// The pack instance is corrupted, and cannot be safely used
 				// again. Do not include it in our reuse map.
@@ -408,7 +392,6 @@ private static boolean inList(final PackFile[] list, final PackFile pack) {
 	}
 
 	private Set<String> listPackDirectory() {
-		packDirectoryLastModified = packDirectory.lastModified();
 		final String[] nameList = packDirectory.list();
 		if (nameList == null)
 			return Collections.emptySet();
@@ -454,4 +437,21 @@ private ObjectDatabase openAlternate(final String location)
 		}
 		return new ObjectDirectory(objdir);
 	}
+
+	private static final class PackList {
+		/** Last modification time of {@link ObjectDirectory#packDirectory}. */
+		final long lastModified;
+
+		/** All known packs, sorted by {@link PackFile#SORT}. */
+		final PackFile[] packs;
+
+		PackList(final long lastModified, final PackFile[] packs) {
+			this.lastModified = lastModified;
+			this.packs = packs;
+		}
+
+		boolean tryAgain(final long currLastModified) {
+			return lastModified < currLastModified;
+		}
+	}
 }
-- 
1.6.4.225.gb589e

[JGIT PATCH (RESEND) 3/4] Don't create new pack lists if the directory hasn't changed

[Shawn O. Pearce]

If we scan the directory and it hasn't changed since the last time we
scanned it, there is no reason to build a new PackList and update the
volatile reference.  This just generates unnecessary garbage and may
make it more difficult to detect an unmodified directory.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/ObjectDirectory.java  |   18 ++++++++++++++----
 1 files changed, 14 insertions(+), 4 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
index 5b28207..0bb3c01 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
@@ -260,10 +260,8 @@ protected ObjectLoader openObject2(final WindowCursor curs,
 	@Override
 	protected boolean tryAgain1() {
 		final PackList old = packList.get();
-		if (old.tryAgain(packDirectory.lastModified())) {
-			scanPacks(old);
-			return true;
-		}
+		if (old.tryAgain(packDirectory.lastModified()))
+			return old != scanPacks(old);
 		return false;
 	}
 
@@ -317,6 +315,8 @@ private PackList scanPacks(final PackList original) {
 					return o;
 				}
 				n = scanPacksImpl(o);
+				if (n == o)
+					return n;
 			} while (!packList.compareAndSet(o, n));
 			return n;
 		}
@@ -327,6 +327,7 @@ private PackList scanPacksImpl(final PackList old) {
 		final long lastModified = packDirectory.lastModified();
 		final Set<String> names = listPackDirectory();
 		final List<PackFile> list = new ArrayList<PackFile>(names.size() >> 2);
+		boolean foundNew = false;
 		for (final String indexName : names) {
 			// Must match "pack-[0-9a-f]{40}.idx" to be an index.
 			//
@@ -352,8 +353,17 @@ private PackList scanPacksImpl(final PackList old) {
 			final File packFile = new File(packDirectory, packName);
 			final File idxFile = new File(packDirectory, indexName);
 			list.add(new PackFile(idxFile, packFile));
+			foundNew = true;
 		}
 
+		// If we did not discover any new files, the modification time was not
+		// changed, and we did not remove any files, then the set of files is
+		// the same as the set we were given. Instead of building a new object
+		// return the same collection.
+		//
+		if (!foundNew && lastModified == old.lastModified && forReuse.isEmpty())
+			return old;
+
 		for (final PackFile p : forReuse.values()) {
 			p.close();
 		}
-- 
1.6.4.225.gb589e

[JGIT PATCH (RESEND) 4/4] Fix racy condition when a repository is repacked

[Shawn O. Pearce]

If the filesystem clock granularity is sufficiently large enough it
is possible for a repacking program such as `git repack` to change
the same directory more than once within the same modification time.

If JGit were to scan the directory between changes in the same
clock step it will never see the later edits, because the directory
modification time has not changed.

Instead we now keep track of the last time we read the directory.
If an object cannot be found on disk and the pack directory's last
modified time is less than 2 minutes since the last time we read
the directory's contents, we scan it again looking for changes.

Worst case scenario, JGit will list the pack directory once for
each requested missing object, until the directory has aged at
least 2 minutes.  Most repositories modify this directory only a
few times a week, so this is not an undue burden on the host.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/ObjectDirectory.java  |   60 +++++++++++++++++---
 1 files changed, 52 insertions(+), 8 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
index 0bb3c01..859824d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectDirectory.java
@@ -66,7 +66,7 @@
  * {@link PackFile}s.
  */
 public class ObjectDirectory extends ObjectDatabase {
-	private static final PackList NO_PACKS = new PackList(-1, new PackFile[0]);
+	private static final PackList NO_PACKS = new PackList(-1, -1, new PackFile[0]);
 
 	private final File objects;
 
@@ -273,7 +273,7 @@ private void insertPack(final PackFile pf) {
 			final PackFile[] newList = new PackFile[1 + oldList.length];
 			newList[0] = pf;
 			System.arraycopy(oldList, 0, newList, 1, oldList.length);
-			n = new PackList(o.lastModified, newList);
+			n = new PackList(o.lastRead, o.lastModified, newList);
 		} while (!packList.compareAndSet(o, n));
 	}
 
@@ -290,7 +290,7 @@ private void removePack(final PackFile deadPack) {
 			final PackFile[] newList = new PackFile[oldList.length - 1];
 			System.arraycopy(oldList, 0, newList, 0, j);
 			System.arraycopy(oldList, j + 1, newList, j, newList.length - j);
-			n = new PackList(o.lastModified, newList);
+			n = new PackList(o.lastRead, o.lastModified, newList);
 		} while (!packList.compareAndSet(o, n));
 		deadPack.close();
 	}
@@ -324,6 +324,7 @@ private PackList scanPacks(final PackList original) {
 
 	private PackList scanPacksImpl(final PackList old) {
 		final Map<String, PackFile> forReuse = reuseMap(old);
+		final long lastRead = System.currentTimeMillis();
 		final long lastModified = packDirectory.lastModified();
 		final Set<String> names = listPackDirectory();
 		final List<PackFile> list = new ArrayList<PackFile>(names.size() >> 2);
@@ -362,18 +363,18 @@ private PackList scanPacksImpl(final PackList old) {
 		// return the same collection.
 		//
 		if (!foundNew && lastModified == old.lastModified && forReuse.isEmpty())
-			return old;
+			return old.updateLastRead(lastRead);
 
 		for (final PackFile p : forReuse.values()) {
 			p.close();
 		}
 
 		if (list.isEmpty())
-			return new PackList(lastModified, NO_PACKS.packs);
+			return new PackList(lastRead, lastModified, NO_PACKS.packs);
 
 		final PackFile[] r = list.toArray(new PackFile[list.size()]);
 		Arrays.sort(r, PackFile.SORT);
-		return new PackList(lastModified, r);
+		return new PackList(lastRead, lastModified, r);
 	}
 
 	private static Map<String, PackFile> reuseMap(final PackList old) {
@@ -449,19 +450,62 @@ private ObjectDatabase openAlternate(final String location)
 	}
 
 	private static final class PackList {
+		/** Last wall-clock time the directory was read. */
+		volatile long lastRead;
+
 		/** Last modification time of {@link ObjectDirectory#packDirectory}. */
 		final long lastModified;
 
 		/** All known packs, sorted by {@link PackFile#SORT}. */
 		final PackFile[] packs;
 
-		PackList(final long lastModified, final PackFile[] packs) {
+		private boolean cannotBeRacilyClean;
+
+		PackList(final long lastRead, final long lastModified,
+				final PackFile[] packs) {
+			this.lastRead = lastRead;
 			this.lastModified = lastModified;
 			this.packs = packs;
+			this.cannotBeRacilyClean = notRacyClean(lastRead);
+		}
+
+		private boolean notRacyClean(final long read) {
+			return read - lastModified > 2 * 60 * 1000L;
+		}
+
+		PackList updateLastRead(final long now) {
+			if (notRacyClean(now))
+				cannotBeRacilyClean = true;
+			lastRead = now;
+			return this;
 		}
 
 		boolean tryAgain(final long currLastModified) {
-			return lastModified < currLastModified;
+			// Any difference indicates the directory was modified.
+			//
+			if (lastModified != currLastModified)
+				return true;
+
+			// We have already determined the last read was far enough
+			// after the last modification that any new modifications
+			// are certain to change the last modified time.
+			//
+			if (cannotBeRacilyClean)
+				return false;
+
+			if (notRacyClean(lastRead)) {
+				// Our last read should have marked cannotBeRacilyClean,
+				// but this thread may not have seen the change. The read
+				// of the volatile field lastRead should have fixed that.
+				//
+				return false;
+			}
+
+			// We last read this directory too close to its last observed
+			// modification time. We may have missed a modification. Scan
+			// the directory again, to ensure we still see the same state.
+			//
+			return true;
 		}
 	}
 }
-- 
1.6.4.225.gb589e