org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackBitmapIndexV1.java - jgit - Git at Google

 /*
  * Copyright (C) 2012, 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.file;

 import java.io.DataInput;
 import java.io.IOException;
 import java.io.InputStream;
 import java.text.MessageFormat;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 import java.util.concurrent.Future;
 import java.util.concurrent.ThreadFactory;
 import java.util.concurrent.atomic.AtomicInteger;

 import org.eclipse.jgit.annotations.Nullable;
 import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectIdOwnerMap;
 import org.eclipse.jgit.util.IO;
 import org.eclipse.jgit.util.NB;

 import com.googlecode.javaewah.EWAHCompressedBitmap;

 /**
  * Support for the pack bitmap index v1 format.
  *
  * @see PackBitmapIndex
  */
 class PackBitmapIndexV1 extends BasePackBitmapIndex {
 	static final byte[] MAGIC = { 'B', 'I', 'T', 'M' };
 	static final int OPT_FULL = 1;

 	private static final int MAX_XOR_OFFSET = 126;

 	private static final ExecutorService executor = Executors
 			.newCachedThreadPool(new ThreadFactory() {
 				private final ThreadFactory baseFactory = Executors
 						.defaultThreadFactory();

 				private final AtomicInteger threadNumber = new AtomicInteger(0);

 				@Override
 				public Thread newThread(Runnable runnable) {
 					Thread thread = baseFactory.newThread(runnable);
 					thread.setName("JGit-PackBitmapIndexV1-" //$NON-NLS-1$
 							+ threadNumber.getAndIncrement());
 					thread.setDaemon(true);
 					return thread;
 				}
 			});

 	private final PackIndex packIndex;
 	private final PackReverseIndex reverseIndex;
 	private final EWAHCompressedBitmap commits;
 	private final EWAHCompressedBitmap trees;
 	private final EWAHCompressedBitmap blobs;
 	private final EWAHCompressedBitmap tags;

 	private final ObjectIdOwnerMap<StoredBitmap> bitmaps;

 	PackBitmapIndexV1(final InputStream fd, PackIndex packIndex,
 			PackReverseIndex reverseIndex) throws IOException {
 		this(fd, () -> packIndex, () -> reverseIndex, false);
 	}

 	PackBitmapIndexV1(final InputStream fd,
 			SupplierWithIOException<PackIndex> packIndexSupplier,
 			SupplierWithIOException<PackReverseIndex> reverseIndexSupplier,
 			boolean loadParallelRevIndex)
 			throws IOException {
 		// An entry is object id, xor offset, flag byte, and a length encoded
 		// bitmap. The object id is an int32 of the nth position sorted by name.
 		super(new ObjectIdOwnerMap<StoredBitmap>());
 		this.bitmaps = getBitmaps();

 		// Optionally start loading reverse index in parallel to loading bitmap
 		// from storage.
 		Future<PackReverseIndex> reverseIndexFuture = null;
 		if (loadParallelRevIndex) {
 			reverseIndexFuture = executor.submit(reverseIndexSupplier::get);
 		}

 		final byte[] scratch = new byte[32];
 		IO.readFully(fd, scratch, 0, scratch.length);

 		// Check the magic bytes
 		for (int i = 0; i < MAGIC.length; i++) {
 			if (scratch[i] != MAGIC[i]) {
 				byte[] actual = new byte[MAGIC.length];
 				System.arraycopy(scratch, 0, actual, 0, MAGIC.length);
 				throw new IOException(MessageFormat.format(
 						JGitText.get().expectedGot, Arrays.toString(MAGIC),
 						Arrays.toString(actual)));
 			}
 		}

 		// Read the version (2 bytes)
 		final int version = NB.decodeUInt16(scratch, 4);
 		if (version != 1)
 			throw new IOException(MessageFormat.format(
 					JGitText.get().unsupportedPackIndexVersion,
 					Integer.valueOf(version)));

 		// Read the options (2 bytes)
 		final int opts = NB.decodeUInt16(scratch, 6);
 		if ((opts & OPT_FULL) == 0)
 			throw new IOException(MessageFormat.format(
 					JGitText.get().expectedGot, Integer.valueOf(OPT_FULL),
 					Integer.valueOf(opts)));

 		// Read the number of entries (1 int32)
 		long numEntries = NB.decodeUInt32(scratch, 8);
 		if (numEntries > Integer.MAX_VALUE)
 			throw new IOException(JGitText.get().indexFileIsTooLargeForJgit);

 		// Checksum applied on the bottom of the corresponding pack file.
 		this.packChecksum = new byte[20];
 		System.arraycopy(scratch, 12, packChecksum, 0, packChecksum.length);

 		// Read the bitmaps for the Git types
 		SimpleDataInput dataInput = new SimpleDataInput(fd);
 		this.commits = readBitmap(dataInput);
 		this.trees = readBitmap(dataInput);
 		this.blobs = readBitmap(dataInput);
 		this.tags = readBitmap(dataInput);

 		// Read full bitmap from storage first.
 		List<IdxPositionBitmap> idxPositionBitmapList = new ArrayList<>();
 		// The xor offset is a single byte offset back in the list of entries.
 		IdxPositionBitmap[] recentBitmaps = new IdxPositionBitmap[MAX_XOR_OFFSET];
 		for (int i = 0; i < (int) numEntries; i++) {
 			IO.readFully(fd, scratch, 0, 6);
 			int nthObjectId = NB.decodeInt32(scratch, 0);
 			int xorOffset = scratch[4];
 			int flags = scratch[5];
 			EWAHCompressedBitmap bitmap = readBitmap(dataInput);

 			if (nthObjectId < 0) {
 				throw new IOException(MessageFormat.format(
 						JGitText.get().invalidId, String.valueOf(nthObjectId)));
 			}
 			if (xorOffset < 0) {
 				throw new IOException(MessageFormat.format(
 						JGitText.get().invalidId, String.valueOf(xorOffset)));
 			}
 			if (xorOffset > MAX_XOR_OFFSET) {
 				throw new IOException(MessageFormat.format(
 						JGitText.get().expectedLessThanGot,
 						String.valueOf(MAX_XOR_OFFSET),
 						String.valueOf(xorOffset)));
 			}
 			if (xorOffset > i) {
 				throw new IOException(MessageFormat.format(
 						JGitText.get().expectedLessThanGot, String.valueOf(i),
 						String.valueOf(xorOffset)));
 			}
 			IdxPositionBitmap xorIdxPositionBitmap = null;
 			if (xorOffset > 0) {
 				int index = (i - xorOffset);
 				xorIdxPositionBitmap = recentBitmaps[index
 						% recentBitmaps.length];
 				if (xorIdxPositionBitmap == null) {
 					throw new IOException(MessageFormat.format(
 							JGitText.get().invalidId,
 							String.valueOf(xorOffset)));
 				}
 			}
 			IdxPositionBitmap idxPositionBitmap = new IdxPositionBitmap(
 					nthObjectId, xorIdxPositionBitmap, bitmap, flags);
 			idxPositionBitmapList.add(idxPositionBitmap);
 			recentBitmaps[i % recentBitmaps.length] = idxPositionBitmap;
 		}

 		this.packIndex = packIndexSupplier.get();
 		for (int i = 0; i < idxPositionBitmapList.size(); ++i) {
 			IdxPositionBitmap idxPositionBitmap = idxPositionBitmapList.get(i);
 			ObjectId objectId = packIndex
 					.getObjectId(idxPositionBitmap.nthObjectId);
 			StoredBitmap sb = new StoredBitmap(objectId,
 					idxPositionBitmap.bitmap,
 					idxPositionBitmap.getXorStoredBitmap(),
 					idxPositionBitmap.flags);
 			// Save the StoredBitmap for a possible future XorStoredBitmap
 			// reference.
 			idxPositionBitmap.sb = sb;
 			bitmaps.add(sb);
 		}

 		PackReverseIndex computedReverseIndex;
 		if (loadParallelRevIndex && reverseIndexFuture != null) {
 			try {
 				computedReverseIndex = reverseIndexFuture.get();
 			} catch (InterruptedException | ExecutionException e) {
 				// Fallback to loading reverse index through a supplier.
 				computedReverseIndex = reverseIndexSupplier.get();
 			}
 		} else {
 			computedReverseIndex = reverseIndexSupplier.get();
 		}
 		this.reverseIndex = computedReverseIndex;
 	}

 	/** {@inheritDoc} */
 	@Override
 	public int findPosition(AnyObjectId objectId) {
 		long offset = packIndex.findOffset(objectId);
 		if (offset == -1)
 			return -1;
 		return reverseIndex.findPostion(offset);
 	}

 	/** {@inheritDoc} */
 	@Override
 	public ObjectId getObject(int position) throws IllegalArgumentException {
 		ObjectId objectId = reverseIndex.findObjectByPosition(position);
 		if (objectId == null)
 			throw new IllegalArgumentException();
 		return objectId;
 	}

 	/** {@inheritDoc} */
 	@Override
 	public int getObjectCount() {
 		return (int) packIndex.getObjectCount();
 	}

 	/** {@inheritDoc} */
 	@Override
 	public EWAHCompressedBitmap ofObjectType(
 			EWAHCompressedBitmap bitmap, int type) {
 		switch (type) {
 		case Constants.OBJ_BLOB:
 			return blobs.and(bitmap);
 		case Constants.OBJ_TREE:
 			return trees.and(bitmap);
 		case Constants.OBJ_COMMIT:
 			return commits.and(bitmap);
 		case Constants.OBJ_TAG:
 			return tags.and(bitmap);
 		}
 		throw new IllegalArgumentException();
 	}

 	/** {@inheritDoc} */
 	@Override
 	public int getBitmapCount() {
 		return bitmaps.size();
 	}

 	/** {@inheritDoc} */
 	@Override
 	public boolean equals(Object o) {
 		// TODO(cranger): compare the pack checksum?
 		if (o instanceof PackBitmapIndexV1)
 			return getPackIndex() == ((PackBitmapIndexV1) o).getPackIndex();
 		return false;
 	}

 	/** {@inheritDoc} */
 	@Override
 	public int hashCode() {
 		return getPackIndex().hashCode();
 	}

 	PackIndex getPackIndex() {
 		return packIndex;
 	}

 	private static EWAHCompressedBitmap readBitmap(DataInput dataInput)
 			throws IOException {
 		EWAHCompressedBitmap bitmap = new EWAHCompressedBitmap();
 		bitmap.deserialize(dataInput);
 		return bitmap;
 	}

 	/**
 	 * Temporary holder of object position in pack index and other metadata for
 	 * {@code StoredBitmap}.
 	 */
 	private static final class IdxPositionBitmap {
 		int nthObjectId;

 		IdxPositionBitmap xorIdxPositionBitmap;

 		EWAHCompressedBitmap bitmap;

 		int flags;

 		StoredBitmap sb;

 		IdxPositionBitmap(int nthObjectId,
 				@Nullable IdxPositionBitmap xorIdxPositionBitmap,
 				EWAHCompressedBitmap bitmap, int flags) {
 			this.nthObjectId = nthObjectId;
 			this.xorIdxPositionBitmap = xorIdxPositionBitmap;
 			this.bitmap = bitmap;
 			this.flags = flags;
 		}

 		StoredBitmap getXorStoredBitmap() {
 			return xorIdxPositionBitmap == null ? null
 					: xorIdxPositionBitmap.sb;
 		}
 	}
 }
	/*
	* Copyright (C) 2012, 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.file;

	import java.io.DataInput;
	import java.io.IOException;
	import java.io.InputStream;
	import java.text.MessageFormat;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.List;
	import java.util.concurrent.ExecutionException;
	import java.util.concurrent.ExecutorService;
	import java.util.concurrent.Executors;
	import java.util.concurrent.Future;
	import java.util.concurrent.ThreadFactory;
	import java.util.concurrent.atomic.AtomicInteger;

	import org.eclipse.jgit.annotations.Nullable;
	import org.eclipse.jgit.internal.JGitText;
	import org.eclipse.jgit.lib.AnyObjectId;
	import org.eclipse.jgit.lib.Constants;
	import org.eclipse.jgit.lib.ObjectId;
	import org.eclipse.jgit.lib.ObjectIdOwnerMap;
	import org.eclipse.jgit.util.IO;
	import org.eclipse.jgit.util.NB;

	import com.googlecode.javaewah.EWAHCompressedBitmap;

	/**
	* Support for the pack bitmap index v1 format.
	*
	* @see PackBitmapIndex
	*/
	class PackBitmapIndexV1 extends BasePackBitmapIndex {
	static final byte[] MAGIC = { 'B', 'I', 'T', 'M' };
	static final int OPT_FULL = 1;

	private static final int MAX_XOR_OFFSET = 126;

	private static final ExecutorService executor = Executors
	.newCachedThreadPool(new ThreadFactory() {
	private final ThreadFactory baseFactory = Executors
	.defaultThreadFactory();

	private final AtomicInteger threadNumber = new AtomicInteger(0);

	@Override
	public Thread newThread(Runnable runnable) {
	Thread thread = baseFactory.newThread(runnable);
	thread.setName("JGit-PackBitmapIndexV1-" //$NON-NLS-1$
	+ threadNumber.getAndIncrement());
	thread.setDaemon(true);
	return thread;
	}
	});

	private final PackIndex packIndex;
	private final PackReverseIndex reverseIndex;
	private final EWAHCompressedBitmap commits;
	private final EWAHCompressedBitmap trees;
	private final EWAHCompressedBitmap blobs;
	private final EWAHCompressedBitmap tags;

	private final ObjectIdOwnerMap<StoredBitmap> bitmaps;

	PackBitmapIndexV1(final InputStream fd, PackIndex packIndex,
	PackReverseIndex reverseIndex) throws IOException {
	this(fd, () -> packIndex, () -> reverseIndex, false);
	}

	PackBitmapIndexV1(final InputStream fd,
	SupplierWithIOException<PackIndex> packIndexSupplier,
	SupplierWithIOException<PackReverseIndex> reverseIndexSupplier,
	boolean loadParallelRevIndex)
	throws IOException {
	// An entry is object id, xor offset, flag byte, and a length encoded
	// bitmap. The object id is an int32 of the nth position sorted by name.
	super(new ObjectIdOwnerMap<StoredBitmap>());
	this.bitmaps = getBitmaps();

	// Optionally start loading reverse index in parallel to loading bitmap
	// from storage.
	Future<PackReverseIndex> reverseIndexFuture = null;
	if (loadParallelRevIndex) {
	reverseIndexFuture = executor.submit(reverseIndexSupplier::get);
	}

	final byte[] scratch = new byte[32];
	IO.readFully(fd, scratch, 0, scratch.length);

	// Check the magic bytes
	for (int i = 0; i < MAGIC.length; i++) {
	if (scratch[i] != MAGIC[i]) {
	byte[] actual = new byte[MAGIC.length];
	System.arraycopy(scratch, 0, actual, 0, MAGIC.length);
	throw new IOException(MessageFormat.format(
	JGitText.get().expectedGot, Arrays.toString(MAGIC),
	Arrays.toString(actual)));
	}
	}

	// Read the version (2 bytes)
	final int version = NB.decodeUInt16(scratch, 4);
	if (version != 1)
	throw new IOException(MessageFormat.format(
	JGitText.get().unsupportedPackIndexVersion,
	Integer.valueOf(version)));

	// Read the options (2 bytes)
	final int opts = NB.decodeUInt16(scratch, 6);
	if ((opts & OPT_FULL) == 0)
	throw new IOException(MessageFormat.format(
	JGitText.get().expectedGot, Integer.valueOf(OPT_FULL),
	Integer.valueOf(opts)));

	// Read the number of entries (1 int32)
	long numEntries = NB.decodeUInt32(scratch, 8);
	if (numEntries > Integer.MAX_VALUE)
	throw new IOException(JGitText.get().indexFileIsTooLargeForJgit);

	// Checksum applied on the bottom of the corresponding pack file.
	this.packChecksum = new byte[20];
	System.arraycopy(scratch, 12, packChecksum, 0, packChecksum.length);

	// Read the bitmaps for the Git types
	SimpleDataInput dataInput = new SimpleDataInput(fd);
	this.commits = readBitmap(dataInput);
	this.trees = readBitmap(dataInput);
	this.blobs = readBitmap(dataInput);
	this.tags = readBitmap(dataInput);

	// Read full bitmap from storage first.
	List<IdxPositionBitmap> idxPositionBitmapList = new ArrayList<>();
	// The xor offset is a single byte offset back in the list of entries.
	IdxPositionBitmap[] recentBitmaps = new IdxPositionBitmap[MAX_XOR_OFFSET];
	for (int i = 0; i < (int) numEntries; i++) {
	IO.readFully(fd, scratch, 0, 6);
	int nthObjectId = NB.decodeInt32(scratch, 0);
	int xorOffset = scratch[4];
	int flags = scratch[5];
	EWAHCompressedBitmap bitmap = readBitmap(dataInput);

	if (nthObjectId < 0) {
	throw new IOException(MessageFormat.format(
	JGitText.get().invalidId, String.valueOf(nthObjectId)));
	}
	if (xorOffset < 0) {
	throw new IOException(MessageFormat.format(
	JGitText.get().invalidId, String.valueOf(xorOffset)));
	}
	if (xorOffset > MAX_XOR_OFFSET) {
	throw new IOException(MessageFormat.format(
	JGitText.get().expectedLessThanGot,
	String.valueOf(MAX_XOR_OFFSET),
	String.valueOf(xorOffset)));
	}
	if (xorOffset > i) {
	throw new IOException(MessageFormat.format(
	JGitText.get().expectedLessThanGot, String.valueOf(i),
	String.valueOf(xorOffset)));
	}
	IdxPositionBitmap xorIdxPositionBitmap = null;
	if (xorOffset > 0) {
	int index = (i - xorOffset);
	xorIdxPositionBitmap = recentBitmaps[index
	% recentBitmaps.length];
	if (xorIdxPositionBitmap == null) {
	throw new IOException(MessageFormat.format(
	JGitText.get().invalidId,
	String.valueOf(xorOffset)));
	}
	}
	IdxPositionBitmap idxPositionBitmap = new IdxPositionBitmap(
	nthObjectId, xorIdxPositionBitmap, bitmap, flags);
	idxPositionBitmapList.add(idxPositionBitmap);
	recentBitmaps[i % recentBitmaps.length] = idxPositionBitmap;
	}

	this.packIndex = packIndexSupplier.get();
	for (int i = 0; i < idxPositionBitmapList.size(); ++i) {
	IdxPositionBitmap idxPositionBitmap = idxPositionBitmapList.get(i);
	ObjectId objectId = packIndex
	.getObjectId(idxPositionBitmap.nthObjectId);
	StoredBitmap sb = new StoredBitmap(objectId,
	idxPositionBitmap.bitmap,
	idxPositionBitmap.getXorStoredBitmap(),
	idxPositionBitmap.flags);
	// Save the StoredBitmap for a possible future XorStoredBitmap
	// reference.
	idxPositionBitmap.sb = sb;
	bitmaps.add(sb);
	}

	PackReverseIndex computedReverseIndex;
	if (loadParallelRevIndex && reverseIndexFuture != null) {
	try {
	computedReverseIndex = reverseIndexFuture.get();
	} catch (InterruptedException \| ExecutionException e) {
	// Fallback to loading reverse index through a supplier.
	computedReverseIndex = reverseIndexSupplier.get();
	}
	} else {
	computedReverseIndex = reverseIndexSupplier.get();
	}
	this.reverseIndex = computedReverseIndex;
	}

	/** {@inheritDoc} */
	@Override
	public int findPosition(AnyObjectId objectId) {
	long offset = packIndex.findOffset(objectId);
	if (offset == -1)
	return -1;
	return reverseIndex.findPostion(offset);
	}

	/** {@inheritDoc} */
	@Override
	public ObjectId getObject(int position) throws IllegalArgumentException {
	ObjectId objectId = reverseIndex.findObjectByPosition(position);
	if (objectId == null)
	throw new IllegalArgumentException();
	return objectId;
	}

	/** {@inheritDoc} */
	@Override
	public int getObjectCount() {
	return (int) packIndex.getObjectCount();
	}

	/** {@inheritDoc} */
	@Override
	public EWAHCompressedBitmap ofObjectType(
	EWAHCompressedBitmap bitmap, int type) {
	switch (type) {
	case Constants.OBJ_BLOB:
	return blobs.and(bitmap);
	case Constants.OBJ_TREE:
	return trees.and(bitmap);
	case Constants.OBJ_COMMIT:
	return commits.and(bitmap);
	case Constants.OBJ_TAG:
	return tags.and(bitmap);
	}
	throw new IllegalArgumentException();
	}

	/** {@inheritDoc} */
	@Override
	public int getBitmapCount() {
	return bitmaps.size();
	}

	/** {@inheritDoc} */
	@Override
	public boolean equals(Object o) {
	// TODO(cranger): compare the pack checksum?
	if (o instanceof PackBitmapIndexV1)
	return getPackIndex() == ((PackBitmapIndexV1) o).getPackIndex();
	return false;
	}

	/** {@inheritDoc} */
	@Override
	public int hashCode() {
	return getPackIndex().hashCode();
	}

	PackIndex getPackIndex() {
	return packIndex;
	}

	private static EWAHCompressedBitmap readBitmap(DataInput dataInput)
	throws IOException {
	EWAHCompressedBitmap bitmap = new EWAHCompressedBitmap();
	bitmap.deserialize(dataInput);
	return bitmap;
	}

	/**
	* Temporary holder of object position in pack index and other metadata for
	* {@code StoredBitmap}.
	*/
	private static final class IdxPositionBitmap {
	int nthObjectId;

	IdxPositionBitmap xorIdxPositionBitmap;

	EWAHCompressedBitmap bitmap;

	int flags;

	StoredBitmap sb;

	IdxPositionBitmap(int nthObjectId,
	@Nullable IdxPositionBitmap xorIdxPositionBitmap,
	EWAHCompressedBitmap bitmap, int flags) {
	this.nthObjectId = nthObjectId;
	this.xorIdxPositionBitmap = xorIdxPositionBitmap;
	this.bitmap = bitmap;
	this.flags = flags;
	}

	StoredBitmap getXorStoredBitmap() {
	return xorIdxPositionBitmap == null ? null
	: xorIdxPositionBitmap.sb;
	}
	}
	}