From 18e9db306b52d2b49c78d0558d51f4a04cca1764 Mon Sep 17 00:00:00 2001 From: Dave Borowitz Date: Thu, 14 Jul 2016 11:40:55 -0400 Subject: [PATCH] Invalidate DfsObjDatabase pack list when refs are updated Currently, there is a race where a user of a DfsRepository in a single thread may get unexpected MissingObjectExceptions trying to look up an object that appears as the current value of a ref: 1. Thread A scans packs before scanning refs, for example by reading an object by SHA-1. 2. Thread B flushes an object and updates a ref to point to that object. 3. Thread A looks up the ref updated in (2). Since it is scanning refs for the first time, it sees the new object SHA-1. 4. Thread A tries to read the object it found in (3), using the cached pack list it got from (1). The object appears missing. Allow implementations to work around this by marking the object database's current pack list as "dirty." A dirty pack list means that DfsReader will rescan packs and try again if a requested object is missing. Implementations should mark objects as dirty any time the ref database reads or scans refs that might be newer than a previously cached pack list. Change-Id: I06c722b20c859ed1475628ec6a2f6d3d6d580700 --- .../internal/storage/dfs/DfsObjDatabase.java | 61 +++++++- .../jgit/internal/storage/dfs/DfsReader.java | 146 ++++++++++++++---- .../storage/dfs/InMemoryRepository.java | 1 + 3 files changed, 168 insertions(+), 40 deletions(-) diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsObjDatabase.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsObjDatabase.java index 3f45859ac7..b28519b16a 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsObjDatabase.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsObjDatabase.java @@ -61,7 +61,17 @@ import org.eclipse.jgit.lib.ObjectReader; /** Manages objects stored in {@link DfsPackFile} on a storage system. */ public abstract class DfsObjDatabase extends ObjectDatabase { - private static final PackList NO_PACKS = new PackList(new DfsPackFile[0]); + private static final PackList NO_PACKS = new PackList(new DfsPackFile[0]) { + @Override + boolean dirty() { + return true; + } + + @Override + void markDirty() { + // Always dirty. + } + }; /** Sources for a pack file. */ public static enum PackSource { @@ -173,7 +183,11 @@ public abstract class DfsObjDatabase extends ObjectDatabase { * the pack list cannot be initialized. */ public DfsPackFile[] getPacks() throws IOException { - return scanPacks(NO_PACKS).packs; + return getPackList().packs; + } + + PackList getPackList() throws IOException { + return scanPacks(NO_PACKS); } /** @return repository owning this object database. */ @@ -363,11 +377,11 @@ public abstract class DfsObjDatabase extends ObjectDatabase { DfsPackFile[] packs = new DfsPackFile[1 + o.packs.length]; packs[0] = newPack; System.arraycopy(o.packs, 0, packs, 1, o.packs.length); - n = new PackList(packs); + n = new PackListImpl(packs); } while (!packList.compareAndSet(o, n)); } - private PackList scanPacks(final PackList original) throws IOException { + PackList scanPacks(final PackList original) throws IOException { PackList o, n; synchronized (packList) { do { @@ -408,10 +422,10 @@ public abstract class DfsObjDatabase extends ObjectDatabase { for (DfsPackFile p : forReuse.values()) p.close(); if (list.isEmpty()) - return new PackList(NO_PACKS.packs); + return new PackListImpl(NO_PACKS.packs); if (!foundNew) return old; - return new PackList(list.toArray(new DfsPackFile[list.size()])); + return new PackListImpl(list.toArray(new DfsPackFile[list.size()])); } private static Map reuseMap(PackList old) { @@ -446,6 +460,17 @@ public abstract class DfsObjDatabase extends ObjectDatabase { packList.set(NO_PACKS); } + /** + * Mark object database as dirty. + *

+ * Used when the caller knows that new data might have been written to the + * repository that could invalidate open readers, for example if refs are + * newly scanned. + */ + protected void markDirty() { + packList.get().markDirty(); + } + @Override public void close() { // PackList packs = packList.get(); @@ -456,12 +481,34 @@ public abstract class DfsObjDatabase extends ObjectDatabase { // p.close(); } - private static final class PackList { + static abstract class PackList { /** All known packs, sorted. */ final DfsPackFile[] packs; PackList(final DfsPackFile[] packs) { this.packs = packs; } + + abstract boolean dirty(); + + abstract void markDirty(); + } + + private static final class PackListImpl extends PackList { + private volatile boolean dirty; + + PackListImpl(DfsPackFile[] packs) { + super(packs); + } + + @Override + boolean dirty() { + return dirty; + } + + @Override + void markDirty() { + dirty = true; + } } } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java index 66421e2a88..cc2f350034 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReader.java @@ -53,6 +53,7 @@ import java.util.Collections; import java.util.Comparator; import java.util.HashSet; import java.util.Iterator; +import java.util.LinkedList; import java.util.List; import java.util.Set; import java.util.zip.DataFormatException; @@ -62,6 +63,7 @@ import org.eclipse.jgit.errors.IncorrectObjectTypeException; import org.eclipse.jgit.errors.MissingObjectException; import org.eclipse.jgit.errors.StoredObjectRepresentationNotAvailableException; import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackList; import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl; import org.eclipse.jgit.internal.storage.file.PackBitmapIndex; import org.eclipse.jgit.internal.storage.file.PackIndex; @@ -91,6 +93,8 @@ import org.eclipse.jgit.util.BlockList; * reader is not thread safe. */ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs { + private static final int MAX_RESOLVE_MATCHES = 256; + /** Temporary buffer large enough for at least one raw object id. */ final byte[] tempId = new byte[OBJECT_ID_LENGTH]; @@ -163,14 +167,25 @@ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs { return Collections.singleton(id.toObjectId()); boolean noGarbage = avoidUnreachable; HashSet matches = new HashSet(4); - for (DfsPackFile pack : db.getPacks()) { - if (noGarbage && pack.isGarbage()) + PackList packList = db.getPackList(); + resolveImpl(packList, id, noGarbage, matches); + if (matches.size() < MAX_RESOLVE_MATCHES && packList.dirty()) { + resolveImpl(db.scanPacks(packList), id, noGarbage, matches); + } + return matches; + } + + private void resolveImpl(PackList packList, AbbreviatedObjectId id, + boolean noGarbage, HashSet matches) throws IOException { + for (DfsPackFile pack : packList.packs) { + if (noGarbage && pack.isGarbage()) { continue; - pack.resolve(this, matches, id, 256); - if (256 <= matches.size()) + } + pack.resolve(this, matches, id, MAX_RESOLVE_MATCHES); + if (matches.size() >= MAX_RESOLVE_MATCHES) { break; + } } - return matches; } @Override @@ -178,7 +193,18 @@ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs { if (last != null && last.hasObject(this, objectId)) return true; boolean noGarbage = avoidUnreachable; - for (DfsPackFile pack : db.getPacks()) { + PackList packList = db.getPackList(); + if (hasImpl(packList, objectId, noGarbage)) { + return true; + } else if (packList.dirty()) { + return hasImpl(db.scanPacks(packList), objectId, noGarbage); + } + return false; + } + + private boolean hasImpl(PackList packList, AnyObjectId objectId, + boolean noGarbage) throws IOException { + for (DfsPackFile pack : packList.packs) { if (pack == last || (noGarbage && pack.isGarbage())) continue; if (pack.hasObject(this, objectId)) { @@ -193,19 +219,22 @@ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs { public ObjectLoader open(AnyObjectId objectId, int typeHint) throws MissingObjectException, IncorrectObjectTypeException, IOException { + ObjectLoader ldr; if (last != null) { - ObjectLoader ldr = last.get(this, objectId); + ldr = last.get(this, objectId); if (ldr != null) return ldr; } + PackList packList = db.getPackList(); boolean noGarbage = avoidUnreachable; - for (DfsPackFile pack : db.getPacks()) { - if (pack == last || (noGarbage && pack.isGarbage())) - continue; - ObjectLoader ldr = pack.get(this, objectId); + ldr = openImpl(packList, objectId, noGarbage); + if (ldr != null) { + return ldr; + } + if (packList.dirty()) { + ldr = openImpl(db.scanPacks(packList), objectId, noGarbage); if (ldr != null) { - last = pack; return ldr; } } @@ -216,6 +245,21 @@ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs { throw new MissingObjectException(objectId.copy(), typeHint); } + private ObjectLoader openImpl(PackList packList, AnyObjectId objectId, + boolean noGarbage) throws IOException { + for (DfsPackFile pack : packList.packs) { + if (pack == last || (noGarbage && pack.isGarbage())) { + continue; + } + ObjectLoader ldr = pack.get(this, objectId); + if (ldr != null) { + last = pack; + return ldr; + } + } + return null; + } + @Override public Set getShallowCommits() { return Collections.emptySet(); @@ -253,39 +297,58 @@ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs { private Iterable> findAll( Iterable objectIds) throws IOException { - ArrayList> r = new ArrayList>(); - DfsPackFile[] packList = db.getPacks(); - if (packList.length == 0) { - for (T t : objectIds) - r.add(new FoundObject(t)); - return r; + Collection pending = new LinkedList<>(); + for (T id : objectIds) { + pending.add(id); } + PackList packList = db.getPackList(); + List> r = new ArrayList<>(); + findAllImpl(packList, pending, r); + if (!pending.isEmpty() && packList.dirty()) { + findAllImpl(db.scanPacks(packList), pending, r); + } + for (T t : pending) { + r.add(new FoundObject(t)); + } + Collections.sort(r, FOUND_OBJECT_SORT); + return r; + } + + private void findAllImpl(PackList packList, + Collection pending, List> r) { + DfsPackFile[] packs = packList.packs; + if (packs.length == 0) { + return; + } int lastIdx = 0; - DfsPackFile lastPack = packList[lastIdx]; + DfsPackFile lastPack = packs[lastIdx]; boolean noGarbage = avoidUnreachable; - OBJECT_SCAN: for (T t : objectIds) { + OBJECT_SCAN: for (Iterator it = pending.iterator(); it.hasNext();) { + T t = it.next(); try { long p = lastPack.findOffset(this, t); if (0 < p) { r.add(new FoundObject(t, lastIdx, lastPack, p)); + it.remove(); continue; } } catch (IOException e) { // Fall though and try to examine other packs. } - for (int i = 0; i < packList.length; i++) { + for (int i = 0; i < packs.length; i++) { if (i == lastIdx) continue; - DfsPackFile pack = packList[i]; + DfsPackFile pack = packs[i]; if (noGarbage && pack.isGarbage()) continue; try { long p = pack.findOffset(this, t); if (0 < p) { r.add(new FoundObject(t, i, pack, p)); + it.remove(); lastIdx = i; lastPack = pack; continue OBJECT_SCAN; @@ -294,13 +357,9 @@ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs { // Examine other packs. } } - - r.add(new FoundObject(t)); } - Collections.sort(r, FOUND_OBJECT_SORT); last = lastPack; - return r; } @Override @@ -418,26 +477,45 @@ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs { IOException { if (last != null) { long sz = last.getObjectSize(this, objectId); - if (0 <= sz) + if (0 <= sz) { return sz; + } } - for (DfsPackFile pack : db.getPacks()) { - if (pack == last) - continue; - long sz = pack.getObjectSize(this, objectId); + PackList packList = db.getPackList(); + long sz = getObjectSizeImpl(packList, objectId); + if (0 <= sz) { + return sz; + } + if (packList.dirty()) { + sz = getObjectSizeImpl(packList, objectId); if (0 <= sz) { - last = pack; return sz; } } - if (typeHint == OBJ_ANY) + if (typeHint == OBJ_ANY) { throw new MissingObjectException(objectId.copy(), JGitText.get().unknownObjectType2); + } throw new MissingObjectException(objectId.copy(), typeHint); } + private long getObjectSizeImpl(PackList packList, AnyObjectId objectId) + throws IOException { + for (DfsPackFile pack : packList.packs) { + if (pack == last) { + continue; + } + long sz = pack.getObjectSize(this, objectId); + if (0 <= sz) { + last = pack; + return sz; + } + } + return -1; + } + public DfsObjectToPack newObjectToPack(AnyObjectId objectId, int type) { return new DfsObjectToPack(objectId, type); } @@ -451,6 +529,8 @@ public final class DfsReader extends ObjectReader implements ObjectReuseAsIs { public void selectObjectRepresentation(PackWriter packer, ProgressMonitor monitor, Iterable objects) throws IOException, MissingObjectException { + // Don't check dirty bit on PackList; assume ObjectToPacks all came from the + // current list. for (DfsPackFile pack : db.getPacks()) { List tmp = findAllFromPack(pack, objects); if (tmp.isEmpty()) diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java index de18eadb22..5765399f6d 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java @@ -310,6 +310,7 @@ public class InMemoryRepository extends DfsRepository { } ids.sort(); sym.sort(); + objdb.markDirty(); return new RefCache(ids.toRefList(), sym.toRefList()); } -- 2.39.5