DfsObjDatabase.java
/*
* Copyright (C) 2011, Google Inc. and others
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Distribution License v. 1.0 which is available at
* https://www.eclipse.org/org/documents/edl-v10.php.
*
* SPDX-License-Identifier: BSD-3-Clause
*/
package org.eclipse.jgit.internal.storage.dfs;
import static java.util.stream.Collectors.joining;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
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.eclipse.jgit.internal.storage.pack.PackExt;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.ObjectDatabase;
import org.eclipse.jgit.lib.ObjectInserter;
import org.eclipse.jgit.lib.ObjectReader;
/**
* Manages objects stored in
* {@link org.eclipse.jgit.internal.storage.dfs.DfsPackFile} on a storage
* system.
*/
public abstract class DfsObjDatabase extends ObjectDatabase {
private static final PackList NO_PACKS = new PackList(
new DfsPackFile[0],
new DfsReftable[0]) {
@Override
boolean dirty() {
return true;
}
@Override
void clearDirty() {
// Always dirty.
}
@Override
public void markDirty() {
// Always dirty.
}
};
/**
* Sources for a pack file.
* <p>
* <strong>Note:</strong> When sorting packs by source, do not use the default
* comparator based on {@link Enum#compareTo}. Prefer {@link
* #DEFAULT_COMPARATOR} or your own {@link ComparatorBuilder}.
*/
public enum PackSource {
/** The pack is created by ObjectInserter due to local activity. */
INSERT,
/**
* The pack is created by PackParser due to a network event.
* <p>
* A received pack can be from either a push into the repository, or a
* fetch into the repository, the direction doesn't matter. A received
* pack was built by the remote Git implementation and may not match the
* storage layout preferred by this version. Received packs are likely
* to be either compacted or garbage collected in the future.
*/
RECEIVE,
/**
* The pack was created by compacting multiple packs together.
* <p>
* Packs created by compacting multiple packs together aren't nearly as
* efficient as a fully garbage collected repository, but may save disk
* space by reducing redundant copies of base objects.
*
* @see DfsPackCompactor
*/
COMPACT,
/**
* Pack was created by Git garbage collection by this implementation.
* <p>
* This source is only used by the {@link DfsGarbageCollector} when it
* builds a pack file by traversing the object graph and copying all
* reachable objects into a new pack stream.
*
* @see DfsGarbageCollector
*/
GC,
/** Created from non-heads by {@link DfsGarbageCollector}. */
GC_REST,
/**
* Pack was created by Git garbage collection.
* <p>
* This pack contains only unreachable garbage that was found during the
* last GC pass. It is retained in a new pack until it is safe to prune
* these objects from the repository.
*/
UNREACHABLE_GARBAGE;
/**
* Default comparator for sources.
* <p>
* Sorts generally newer, smaller types such as {@code INSERT} and {@code
* RECEIVE} earlier; older, larger types such as {@code GC} later; and
* {@code UNREACHABLE_GARBAGE} at the end.
*/
public static final Comparator<PackSource> DEFAULT_COMPARATOR =
new ComparatorBuilder()
.add(INSERT, RECEIVE)
.add(COMPACT)
.add(GC)
.add(GC_REST)
.add(UNREACHABLE_GARBAGE)
.build();
/**
* Builder for describing {@link PackSource} ordering where some values are
* explicitly considered equal to others.
*/
public static class ComparatorBuilder {
private final Map<PackSource, Integer> ranks = new HashMap<>();
private int counter;
/**
* Add a collection of sources that should sort as equal.
* <p>
* Sources in the input will sort after sources listed in previous calls
* to this method.
*
* @param sources
* sources in this equivalence class.
* @return this.
*/
public ComparatorBuilder add(PackSource... sources) {
for (PackSource s : sources) {
ranks.put(s, Integer.valueOf(counter));
}
counter++;
return this;
}
/**
* Build the comparator.
*
* @return new comparator instance.
* @throws IllegalArgumentException
* not all {@link PackSource} instances were explicitly assigned
* an equivalence class.
*/
public Comparator<PackSource> build() {
return new PackSourceComparator(ranks);
}
}
private static class PackSourceComparator implements Comparator<PackSource> {
private final Map<PackSource, Integer> ranks;
private PackSourceComparator(Map<PackSource, Integer> ranks) {
if (!ranks.keySet().equals(
new HashSet<>(Arrays.asList(PackSource.values())))) {
throw new IllegalArgumentException();
}
this.ranks = new HashMap<>(ranks);
}
@Override
public int compare(PackSource a, PackSource b) {
return ranks.get(a).compareTo(ranks.get(b));
}
@Override
public String toString() {
return Arrays.stream(PackSource.values())
.map(s -> s + "=" + ranks.get(s)) //$NON-NLS-1$
.collect(joining(", ", getClass().getSimpleName() + "{", "}")); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
}
}
}
private final AtomicReference<PackList> packList;
private final DfsRepository repository;
private DfsReaderOptions readerOptions;
private Comparator<DfsPackDescription> packComparator;
/**
* Initialize an object database for our repository.
*
* @param repository
* repository owning this object database.
* @param options
* how readers should access the object database.
*/
protected DfsObjDatabase(DfsRepository repository,
DfsReaderOptions options) {
this.repository = repository;
this.packList = new AtomicReference<>(NO_PACKS);
this.readerOptions = options;
this.packComparator = DfsPackDescription.objectLookupComparator();
}
/**
* Get configured reader options, such as read-ahead.
*
* @return configured reader options, such as read-ahead.
*/
public DfsReaderOptions getReaderOptions() {
return readerOptions;
}
/**
* Set the comparator used when searching for objects across packs.
* <p>
* An optimal comparator will find more objects without having to load large
* idx files from storage only to find that they don't contain the object.
* See {@link DfsPackDescription#objectLookupComparator()} for the default
* heuristics.
*
* @param packComparator
* comparator.
*/
public void setPackComparator(Comparator<DfsPackDescription> packComparator) {
this.packComparator = packComparator;
}
/** {@inheritDoc} */
@Override
public DfsReader newReader() {
return new DfsReader(this);
}
/** {@inheritDoc} */
@Override
public ObjectInserter newInserter() {
return new DfsInserter(this);
}
/**
* Scan and list all available pack files in the repository.
*
* @return list of available packs. The returned array is shared with the
* implementation and must not be modified by the caller.
* @throws java.io.IOException
* the pack list cannot be initialized.
*/
public DfsPackFile[] getPacks() throws IOException {
return getPackList().packs;
}
/**
* Scan and list all available reftable files in the repository.
*
* @return list of available reftables. The returned array is shared with
* the implementation and must not be modified by the caller.
* @throws java.io.IOException
* the pack list cannot be initialized.
*/
public DfsReftable[] getReftables() throws IOException {
return getPackList().reftables;
}
/**
* Scan and list all available pack files in the repository.
*
* @return list of available packs, with some additional metadata. The
* returned array is shared with the implementation and must not be
* modified by the caller.
* @throws java.io.IOException
* the pack list cannot be initialized.
*/
public PackList getPackList() throws IOException {
return scanPacks(NO_PACKS);
}
/**
* Get repository owning this object database.
*
* @return repository owning this object database.
*/
protected DfsRepository getRepository() {
return repository;
}
/**
* List currently known pack files in the repository, without scanning.
*
* @return list of available packs. The returned array is shared with the
* implementation and must not be modified by the caller.
*/
public DfsPackFile[] getCurrentPacks() {
return getCurrentPackList().packs;
}
/**
* List currently known reftable files in the repository, without scanning.
*
* @return list of available reftables. The returned array is shared with
* the implementation and must not be modified by the caller.
*/
public DfsReftable[] getCurrentReftables() {
return getCurrentPackList().reftables;
}
/**
* List currently known pack files in the repository, without scanning.
*
* @return list of available packs, with some additional metadata. The
* returned array is shared with the implementation and must not be
* modified by the caller.
*/
public PackList getCurrentPackList() {
return packList.get();
}
/**
* Does the requested object exist in this database?
* <p>
* This differs from ObjectDatabase's implementation in that we can selectively
* ignore unreachable (garbage) objects.
*
* @param objectId
* identity of the object to test for existence of.
* @param avoidUnreachableObjects
* if true, ignore objects that are unreachable.
* @return true if the specified object is stored in this database.
* @throws java.io.IOException
* the object store cannot be accessed.
*/
public boolean has(AnyObjectId objectId, boolean avoidUnreachableObjects)
throws IOException {
try (ObjectReader or = newReader()) {
or.setAvoidUnreachableObjects(avoidUnreachableObjects);
return or.has(objectId);
}
}
/**
* Generate a new unique name for a pack file.
*
* @param source
* where the pack stream is created.
* @return a unique name for the pack file. Must not collide with any other
* pack file name in the same DFS.
* @throws java.io.IOException
* a new unique pack description cannot be generated.
*/
protected abstract DfsPackDescription newPack(PackSource source)
throws IOException;
/**
* Generate a new unique name for a pack file.
*
* <p>
* Default implementation of this method would be equivalent to
* {@code newPack(source).setEstimatedPackSize(estimatedPackSize)}. But the
* clients can override this method to use the given
* {@code estomatedPackSize} value more efficiently in the process of
* creating a new
* {@link org.eclipse.jgit.internal.storage.dfs.DfsPackDescription} object.
*
* @param source
* where the pack stream is created.
* @param estimatedPackSize
* the estimated size of the pack.
* @return a unique name for the pack file. Must not collide with any other
* pack file name in the same DFS.
* @throws java.io.IOException
* a new unique pack description cannot be generated.
*/
protected DfsPackDescription newPack(PackSource source,
long estimatedPackSize) throws IOException {
DfsPackDescription pack = newPack(source);
pack.setEstimatedPackSize(estimatedPackSize);
return pack;
}
/**
* Commit a pack and index pair that was written to the DFS.
* <p>
* Committing the pack/index pair makes them visible to readers. The JGit
* DFS code always writes the pack, then the index. This allows a simple
* commit process to do nothing if readers always look for both files to
* exist and the DFS performs atomic creation of the file (e.g. stream to a
* temporary file and rename to target on close).
* <p>
* During pack compaction or GC the new pack file may be replacing other
* older files. Implementations should remove those older files (if any) as
* part of the commit of the new file.
* <p>
* This method is a trivial wrapper around
* {@link #commitPackImpl(Collection, Collection)} that calls the
* implementation and fires events.
*
* @param desc
* description of the new packs.
* @param replaces
* if not null, list of packs to remove.
* @throws java.io.IOException
* the packs cannot be committed. On failure a rollback must
* also be attempted by the caller.
*/
protected void commitPack(Collection<DfsPackDescription> desc,
Collection<DfsPackDescription> replaces) throws IOException {
commitPackImpl(desc, replaces);
getRepository().fireEvent(new DfsPacksChangedEvent());
}
/**
* Implementation of pack commit.
*
* @see #commitPack(Collection, Collection)
* @param desc
* description of the new packs.
* @param replaces
* if not null, list of packs to remove.
* @throws java.io.IOException
* the packs cannot be committed.
*/
protected abstract void commitPackImpl(Collection<DfsPackDescription> desc,
Collection<DfsPackDescription> replaces) throws IOException;
/**
* Try to rollback a pack creation.
* <p>
* JGit DFS always writes the pack first, then the index. If the pack does
* not yet exist, then neither does the index. A safe DFS implementation
* would try to remove both files to ensure they are really gone.
* <p>
* A rollback does not support failures, as it only occurs when there is
* already a failure in progress. A DFS implementor may wish to log
* warnings/error messages when a rollback fails, but should not send new
* exceptions up the Java callstack.
*
* @param desc
* pack to delete.
*/
protected abstract void rollbackPack(Collection<DfsPackDescription> desc);
/**
* List the available pack files.
* <p>
* The returned list must support random access and must be mutable by the
* caller. It is sorted in place using the natural sorting of the returned
* DfsPackDescription objects.
*
* @return available packs. May be empty if there are no packs.
* @throws java.io.IOException
* the packs cannot be listed and the object database is not
* functional to the caller.
*/
protected abstract List<DfsPackDescription> listPacks() throws IOException;
/**
* Open a pack, pack index, or other related file for reading.
*
* @param desc
* description of pack related to the data that will be read.
* This is an instance previously obtained from
* {@link #listPacks()}, but not necessarily from the same
* DfsObjDatabase instance.
* @param ext
* file extension that will be read i.e "pack" or "idx".
* @return channel to read the file.
* @throws java.io.FileNotFoundException
* the file does not exist.
* @throws java.io.IOException
* the file cannot be opened.
*/
protected abstract ReadableChannel openFile(
DfsPackDescription desc, PackExt ext)
throws FileNotFoundException, IOException;
/**
* Open a pack, pack index, or other related file for writing.
*
* @param desc
* description of pack related to the data that will be written.
* This is an instance previously obtained from
* {@link #newPack(PackSource)}.
* @param ext
* file extension that will be written i.e "pack" or "idx".
* @return channel to write the file.
* @throws java.io.IOException
* the file cannot be opened.
*/
protected abstract DfsOutputStream writeFile(
DfsPackDescription desc, PackExt ext) throws IOException;
void addPack(DfsPackFile newPack) throws IOException {
PackList o, n;
do {
o = packList.get();
if (o == NO_PACKS) {
// The repository may not have needed any existing objects to
// complete the current task of creating a pack (e.g. push of a
// pack with no external deltas). Because we don't scan for
// newly added packs on missed object lookups, scan now to
// make sure all older packs are available in the packList.
o = scanPacks(o);
// Its possible the scan identified the pack we were asked to
// add, as the pack was already committed via commitPack().
// If this is the case return without changing the list.
for (DfsPackFile p : o.packs) {
if (p.key.equals(newPack.key)) {
return;
}
}
}
DfsPackFile[] packs = new DfsPackFile[1 + o.packs.length];
packs[0] = newPack;
System.arraycopy(o.packs, 0, packs, 1, o.packs.length);
n = new PackListImpl(packs, o.reftables);
} while (!packList.compareAndSet(o, n));
}
void addReftable(DfsPackDescription add, Set<DfsPackDescription> remove)
throws IOException {
PackList o, n;
do {
o = packList.get();
if (o == NO_PACKS) {
o = scanPacks(o);
for (DfsReftable t : o.reftables) {
if (t.getPackDescription().equals(add)) {
return;
}
}
}
List<DfsReftable> tables = new ArrayList<>(1 + o.reftables.length);
for (DfsReftable t : o.reftables) {
if (!remove.contains(t.getPackDescription())) {
tables.add(t);
}
}
tables.add(new DfsReftable(add));
n = new PackListImpl(o.packs, tables.toArray(new DfsReftable[0]));
} while (!packList.compareAndSet(o, n));
}
PackList scanPacks(PackList original) throws IOException {
PackList o, n;
synchronized (packList) {
do {
o = packList.get();
if (o != original) {
// Another thread did the scan for us, while we
// were blocked on the monitor above.
//
return o;
}
n = scanPacksImpl(o);
if (n == o)
return n;
} while (!packList.compareAndSet(o, n));
}
getRepository().fireEvent(new DfsPacksChangedEvent());
return n;
}
private PackList scanPacksImpl(PackList old) throws IOException {
DfsBlockCache cache = DfsBlockCache.getInstance();
Map<DfsPackDescription, DfsPackFile> packs = packMap(old);
Map<DfsPackDescription, DfsReftable> reftables = reftableMap(old);
List<DfsPackDescription> scanned = listPacks();
Collections.sort(scanned, packComparator);
List<DfsPackFile> newPacks = new ArrayList<>(scanned.size());
List<DfsReftable> newReftables = new ArrayList<>(scanned.size());
boolean foundNew = false;
for (DfsPackDescription dsc : scanned) {
DfsPackFile oldPack = packs.remove(dsc);
if (oldPack != null) {
newPacks.add(oldPack);
} else if (dsc.hasFileExt(PackExt.PACK)) {
newPacks.add(new DfsPackFile(cache, dsc));
foundNew = true;
}
DfsReftable oldReftable = reftables.remove(dsc);
if (oldReftable != null) {
newReftables.add(oldReftable);
} else if (dsc.hasFileExt(PackExt.REFTABLE)) {
newReftables.add(new DfsReftable(cache, dsc));
foundNew = true;
}
}
if (newPacks.isEmpty() && newReftables.isEmpty())
return new PackListImpl(NO_PACKS.packs, NO_PACKS.reftables);
if (!foundNew) {
old.clearDirty();
return old;
}
Collections.sort(newReftables, reftableComparator());
return new PackListImpl(
newPacks.toArray(new DfsPackFile[0]),
newReftables.toArray(new DfsReftable[0]));
}
private static Map<DfsPackDescription, DfsPackFile> packMap(PackList old) {
Map<DfsPackDescription, DfsPackFile> forReuse = new HashMap<>();
for (DfsPackFile p : old.packs) {
if (!p.invalid()) {
forReuse.put(p.desc, p);
}
}
return forReuse;
}
private static Map<DfsPackDescription, DfsReftable> reftableMap(PackList old) {
Map<DfsPackDescription, DfsReftable> forReuse = new HashMap<>();
for (DfsReftable p : old.reftables) {
if (!p.invalid()) {
forReuse.put(p.desc, p);
}
}
return forReuse;
}
/**
* Get comparator to sort {@link DfsReftable} by priority.
*
* @return comparator to sort {@link DfsReftable} by priority.
*/
protected Comparator<DfsReftable> reftableComparator() {
return Comparator.comparing(
DfsReftable::getPackDescription,
DfsPackDescription.reftableComparator());
}
/**
* Clears the cached list of packs, forcing them to be scanned again.
*/
protected void clearCache() {
packList.set(NO_PACKS);
}
/** {@inheritDoc} */
@Override
public void close() {
packList.set(NO_PACKS);
}
/** Snapshot of packs scanned in a single pass. */
public abstract static class PackList {
/** All known packs, sorted. */
public final DfsPackFile[] packs;
/** All known reftables, sorted. */
public final DfsReftable[] reftables;
private long lastModified = -1;
PackList(DfsPackFile[] packs, DfsReftable[] reftables) {
this.packs = packs;
this.reftables = reftables;
}
/** @return last modified time of all packs, in milliseconds. */
public long getLastModified() {
if (lastModified < 0) {
long max = 0;
for (DfsPackFile pack : packs) {
max = Math.max(max, pack.getPackDescription().getLastModified());
}
lastModified = max;
}
return lastModified;
}
abstract boolean dirty();
abstract void clearDirty();
/**
* Mark pack list as dirty.
* <p>
* Used when the caller knows that new data might have been written to the
* repository that could invalidate open readers depending on this pack list,
* for example if refs are newly scanned.
*/
public abstract void markDirty();
}
private static final class PackListImpl extends PackList {
private volatile boolean dirty;
PackListImpl(DfsPackFile[] packs, DfsReftable[] reftables) {
super(packs, reftables);
}
@Override
boolean dirty() {
return dirty;
}
@Override
void clearDirty() {
dirty = false;
}
@Override
public void markDirty() {
dirty = true;
}
}
}