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

 /*
  * Copyright (C) 2022, Google LLC 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.BufferedOutputStream;
 import java.io.IOException;
 import java.io.OutputStream;
 import java.util.List;

 import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.transport.PackedObjectInfo;
 import org.eclipse.jgit.util.NB;

 /**
  * Write an object index in the output stream
  */
 public abstract class PackObjectSizeIndexWriter {

 	private static final int MAX_24BITS_UINT = 0xffffff;

 	private static final PackObjectSizeIndexWriter NULL_WRITER = new PackObjectSizeIndexWriter() {
 		@Override
 		public void write(List<? extends PackedObjectInfo> objs) {
 			// Do nothing
 		}
 	};

 	/** Magic constant for the object size index file */
 	protected static final byte[] HEADER = { -1, 's', 'i', 'z' };

 	/**
 	 * Returns a writer for the latest index version
 	 *
 	 * @param os
 	 *            Output stream where to write the index
 	 * @param minSize
 	 *            objects strictly smaller than this size won't be added to the
 	 *            index. Negative size won't write AT ALL. Other sizes could write
 	 *            an empty index.
 	 * @return the index writer
 	 */
 	public static PackObjectSizeIndexWriter createWriter(OutputStream os,
 			int minSize) {
 		if (minSize < 0) {
 			return NULL_WRITER;
 		}
 		return new PackObjectSizeWriterV1(os, minSize);
 	}

 	/**
 	 * Add the objects to the index
 	 *
 	 * @param objs
 	 *            objects in the pack, in sha1 order. Their position in the list
 	 *            matches their position in the primary index.
 	 * @throws IOException
 	 *             problem writing to the stream
 	 */
 	public abstract void write(List<? extends PackedObjectInfo> objs)
 			throws IOException;

 	/**
 	 * Object size index v1.
 	 *
 	 * Store position (in the main index) to size as parallel arrays.
 	 *
 	 * <p>
 	 * Positions in the main index fit well in unsigned 24 bits (16M) for most
 	 * repositories, but some outliers have even more objects, so we need to
 	 * store also 32 bits positions.
 	 *
 	 * <p>
 	 * Sizes are stored as a first array parallel to positions. If a size
 	 * doesn't fit in an element of that array, then we encode there a position
 	 * on the next-size array. This "overflow" array doesn't have entries for
 	 * all positions.
 	 *
 	 * <pre>
 	 *
 	 *      positions       [10, 500, 1000, 1001]
 	 *      sizes (32bits)  [15MB, -1, 6MB, -2]
 	*                          ___/  ______/
 	 *                        /     /
 	 *      sizes (64 bits) [3GB, 6GB]
 	 * </pre>
 	 *
 	 * <p>
 	 * For sizes we use 32 bits as the first level and 64 for the rare objects
 	 * over 2GB.
 	 *
 	 * <p>
 	 * A 24/32/64 bits hierarchy of arrays saves space if we have a lot of small
 	 * objects, but wastes space if we have only big ones. The min size to index
 	 * is controlled by conf and in principle we want to index only rather big
 	 * objects (e.g. > 10MB). We could support more dynamics read/write of sizes
 	 * (e.g. 24 only if the threshold will include many of those objects) but it
 	 * complicates a lot code and spec. If needed it could go for a v2 of the
 	 * protocol.
 	 *
 	 * <p>
 	 * Format:
 	 * <ul>
 	 * <li>A header with the magic number (4 bytes)
 	 * <li>The index version (1 byte)
 	 * <li>The minimum object size (4 bytes)
 	 * <li>Total count of objects indexed (C, 4 bytes)
 	 * </ul>
 	 * (if count == 0, stop here)
 	 * <p>
 	 * Blocks of
 	 * <ul>
 	 * <li>Size per entry in bits (1 byte, either 24 (0x18) or 32 (0x20))
 	 * <li>Count of entries (4 bytes) (c, as a signed int)
 	 * <li>positions encoded in s bytes each (i.e s*c bytes)
 	 *
 	 * <li>0 (as a "size-per-entry = 0", marking end of the section)
 	 *
 	 * <li>32 bit sizes (C * 4 bytes). Negative size means
 	 * nextLevel[abs(size)-1]
 	 * <li>Count of 64 bit sizes (s64) (or 0 if no more indirections)
 	 * <li>64 bit sizes (s64 * 8 bytes)
 	 * <li>0 (end)
 	 * </ul>
 	 */
 	static class PackObjectSizeWriterV1 extends PackObjectSizeIndexWriter {

 		private final OutputStream os;

 		private final int minObjSize;

 		private final byte[] intBuffer = new byte[4];

 		PackObjectSizeWriterV1(OutputStream os, int minSize) {
 			this.os = new BufferedOutputStream(os);
 			this.minObjSize = minSize;
 		}

 		@Override
 		public void write(List<? extends PackedObjectInfo> allObjects)
 				throws IOException {
 			os.write(HEADER);
 			writeUInt8(1); // Version
 			writeInt32(minObjSize);

 			PackedObjectStats stats = countIndexableObjects(allObjects);
 			int[] indexablePositions = findIndexablePositions(allObjects,
 					stats.indexableObjs);
 			writeInt32(indexablePositions.length); // Total # of objects
 			if (indexablePositions.length == 0) {
 				os.flush();
 				return;
 			}

 			// Positions that fit in 3 bytes
 			if (stats.pos24Bits > 0) {
 				writeUInt8(24);
 				writeInt32(stats.pos24Bits);
 				applyToRange(indexablePositions, 0, stats.pos24Bits,
 						this::writeInt24);
 			}
 			// Positions that fit in 4 bytes
 			// We only use 31 bits due to sign,
 			// but that covers 2 billion objs
 			if (stats.pos31Bits > 0) {
 				writeUInt8(32);
 				writeInt32(stats.pos31Bits);
 				applyToRange(indexablePositions, stats.pos24Bits,
 						stats.pos24Bits + stats.pos31Bits, this::writeInt32);
 			}
 			writeUInt8(0);
 			writeSizes(allObjects, indexablePositions, stats.sizeOver2GB);
 			os.flush();
 		}

 		private void writeUInt8(int i) throws IOException {
 			if (i > 255) {
 				throw new IllegalStateException(
 						JGitText.get().numberDoesntFit);
 			}
 			NB.encodeInt32(intBuffer, 0, i);
 			os.write(intBuffer, 3, 1);
 		}

 		private void writeInt24(int i) throws IOException {
 			NB.encodeInt24(intBuffer, 1, i);
 			os.write(intBuffer, 1, 3);
 		}

 		private void writeInt32(int i) throws IOException {
 			NB.encodeInt32(intBuffer, 0, i);
 			os.write(intBuffer);
 		}

 		private void writeSizes(List<? extends PackedObjectInfo> allObjects,
 				int[] indexablePositions, int objsBiggerThan2Gb)
 				throws IOException {
 			if (indexablePositions.length == 0) {
 				writeInt32(0);
 				return;
 			}

 			byte[] sizes64bits = new byte[8 * objsBiggerThan2Gb];
 			int s64 = 0;
 			for (int i = 0; i < indexablePositions.length; i++) {
 				PackedObjectInfo info = allObjects.get(indexablePositions[i]);
 				if (info.getFullSize() < Integer.MAX_VALUE) {
 					writeInt32((int) info.getFullSize());
 				} else {
 					// Size needs more than 32 bits. Store -1 * offset in the
 					// next table as size.
 					writeInt32(-1 * (s64 + 1));
 					NB.encodeInt64(sizes64bits, s64 * 8, info.getFullSize());
 					s64++;
 				}
 			}
 			if (objsBiggerThan2Gb > 0) {
 				writeInt32(objsBiggerThan2Gb);
 				os.write(sizes64bits);
 			}
 			writeInt32(0);
 		}

 		private int[] findIndexablePositions(
 				List<? extends PackedObjectInfo> allObjects,
 				int indexableObjs) {
 			int[] positions = new int[indexableObjs];
 			int positionIdx = 0;
 			for (int i = 0; i < allObjects.size(); i++) {
 				PackedObjectInfo o = allObjects.get(i);
 				if (!shouldIndex(o)) {
 					continue;
 				}
 				positions[positionIdx++] = i;
 			}
 			return positions;
 		}

 		private PackedObjectStats countIndexableObjects(
 				List<? extends PackedObjectInfo> objs) {
 			PackedObjectStats stats = new PackedObjectStats();
 			for (int i = 0; i < objs.size(); i++) {
 				PackedObjectInfo o = objs.get(i);
 				if (!shouldIndex(o)) {
 					continue;
 				}
 				stats.indexableObjs++;
 				if (o.getFullSize() > Integer.MAX_VALUE) {
 					stats.sizeOver2GB++;
 				}
 				if (i <= MAX_24BITS_UINT) {
 					stats.pos24Bits++;
 				} else {
 					stats.pos31Bits++;
 					// i is a positive int, cannot be bigger than this
 				}
 			}
 			return stats;
 		}

 		private boolean shouldIndex(PackedObjectInfo o) {
 			return (o.getType() == Constants.OBJ_BLOB)
 					&& (o.getFullSize() >= minObjSize);
 		}

 		private static class PackedObjectStats {
 			int indexableObjs;

 			int pos24Bits;

 			int pos31Bits;

 			int sizeOver2GB;
 		}

 		@FunctionalInterface
 		interface IntEncoder {
 			void encode(int i) throws IOException;
 		}

 		private static void applyToRange(int[] allPositions, int start, int end,
 				IntEncoder encoder) throws IOException {
 			for (int i = start; i < end; i++) {
 				encoder.encode(allPositions[i]);
 			}
 		}
 	}
 }
	/*
	* Copyright (C) 2022, Google LLC 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.BufferedOutputStream;
	import java.io.IOException;
	import java.io.OutputStream;
	import java.util.List;

	import org.eclipse.jgit.internal.JGitText;
	import org.eclipse.jgit.lib.Constants;
	import org.eclipse.jgit.transport.PackedObjectInfo;
	import org.eclipse.jgit.util.NB;

	/**
	* Write an object index in the output stream
	*/
	public abstract class PackObjectSizeIndexWriter {

	private static final int MAX_24BITS_UINT = 0xffffff;

	private static final PackObjectSizeIndexWriter NULL_WRITER = new PackObjectSizeIndexWriter() {
	@Override
	public void write(List<? extends PackedObjectInfo> objs) {
	// Do nothing
	}
	};

	/** Magic constant for the object size index file */
	protected static final byte[] HEADER = { -1, 's', 'i', 'z' };

	/**
	* Returns a writer for the latest index version
	*
	* @param os
	* Output stream where to write the index
	* @param minSize
	* objects strictly smaller than this size won't be added to the
	* index. Negative size won't write AT ALL. Other sizes could write
	* an empty index.
	* @return the index writer
	*/
	public static PackObjectSizeIndexWriter createWriter(OutputStream os,
	int minSize) {
	if (minSize < 0) {
	return NULL_WRITER;
	}
	return new PackObjectSizeWriterV1(os, minSize);
	}

	/**
	* Add the objects to the index
	*
	* @param objs
	* objects in the pack, in sha1 order. Their position in the list
	* matches their position in the primary index.
	* @throws IOException
	* problem writing to the stream
	*/
	public abstract void write(List<? extends PackedObjectInfo> objs)
	throws IOException;

	/**
	* Object size index v1.
	*
	* Store position (in the main index) to size as parallel arrays.
	*
	* <p>
	* Positions in the main index fit well in unsigned 24 bits (16M) for most
	* repositories, but some outliers have even more objects, so we need to
	* store also 32 bits positions.
	*
	* <p>
	* Sizes are stored as a first array parallel to positions. If a size
	* doesn't fit in an element of that array, then we encode there a position
	* on the next-size array. This "overflow" array doesn't have entries for
	* all positions.
	*
	* <pre>
	*
	* positions [10, 500, 1000, 1001]
	* sizes (32bits) [15MB, -1, 6MB, -2]
	* ___/ ______/
	* / /
	* sizes (64 bits) [3GB, 6GB]
	* </pre>
	*
	* <p>
	* For sizes we use 32 bits as the first level and 64 for the rare objects
	* over 2GB.
	*
	* <p>
	* A 24/32/64 bits hierarchy of arrays saves space if we have a lot of small
	* objects, but wastes space if we have only big ones. The min size to index
	* is controlled by conf and in principle we want to index only rather big
	* objects (e.g. > 10MB). We could support more dynamics read/write of sizes
	* (e.g. 24 only if the threshold will include many of those objects) but it
	* complicates a lot code and spec. If needed it could go for a v2 of the
	* protocol.
	*
	* <p>
	* Format:
	* <ul>
	* <li>A header with the magic number (4 bytes)
	* <li>The index version (1 byte)
	* <li>The minimum object size (4 bytes)
	* <li>Total count of objects indexed (C, 4 bytes)
	* </ul>
	* (if count == 0, stop here)
	* <p>
	* Blocks of
	* <ul>
	* <li>Size per entry in bits (1 byte, either 24 (0x18) or 32 (0x20))
	* <li>Count of entries (4 bytes) (c, as a signed int)
	* <li>positions encoded in s bytes each (i.e s*c bytes)
	*
	* <li>0 (as a "size-per-entry = 0", marking end of the section)
	*
	* <li>32 bit sizes (C * 4 bytes). Negative size means
	* nextLevel[abs(size)-1]
	* <li>Count of 64 bit sizes (s64) (or 0 if no more indirections)
	* <li>64 bit sizes (s64 * 8 bytes)
	* <li>0 (end)
	* </ul>
	*/
	static class PackObjectSizeWriterV1 extends PackObjectSizeIndexWriter {

	private final OutputStream os;

	private final int minObjSize;

	private final byte[] intBuffer = new byte[4];

	PackObjectSizeWriterV1(OutputStream os, int minSize) {
	this.os = new BufferedOutputStream(os);
	this.minObjSize = minSize;
	}

	@Override
	public void write(List<? extends PackedObjectInfo> allObjects)
	throws IOException {
	os.write(HEADER);
	writeUInt8(1); // Version
	writeInt32(minObjSize);

	PackedObjectStats stats = countIndexableObjects(allObjects);
	int[] indexablePositions = findIndexablePositions(allObjects,
	stats.indexableObjs);
	writeInt32(indexablePositions.length); // Total # of objects
	if (indexablePositions.length == 0) {
	os.flush();
	return;
	}

	// Positions that fit in 3 bytes
	if (stats.pos24Bits > 0) {
	writeUInt8(24);
	writeInt32(stats.pos24Bits);
	applyToRange(indexablePositions, 0, stats.pos24Bits,
	this::writeInt24);
	}
	// Positions that fit in 4 bytes
	// We only use 31 bits due to sign,
	// but that covers 2 billion objs
	if (stats.pos31Bits > 0) {
	writeUInt8(32);
	writeInt32(stats.pos31Bits);
	applyToRange(indexablePositions, stats.pos24Bits,
	stats.pos24Bits + stats.pos31Bits, this::writeInt32);
	}
	writeUInt8(0);
	writeSizes(allObjects, indexablePositions, stats.sizeOver2GB);
	os.flush();
	}

	private void writeUInt8(int i) throws IOException {
	if (i > 255) {
	throw new IllegalStateException(
	JGitText.get().numberDoesntFit);
	}
	NB.encodeInt32(intBuffer, 0, i);
	os.write(intBuffer, 3, 1);
	}

	private void writeInt24(int i) throws IOException {
	NB.encodeInt24(intBuffer, 1, i);
	os.write(intBuffer, 1, 3);
	}

	private void writeInt32(int i) throws IOException {
	NB.encodeInt32(intBuffer, 0, i);
	os.write(intBuffer);
	}

	private void writeSizes(List<? extends PackedObjectInfo> allObjects,
	int[] indexablePositions, int objsBiggerThan2Gb)
	throws IOException {
	if (indexablePositions.length == 0) {
	writeInt32(0);
	return;
	}

	byte[] sizes64bits = new byte[8 * objsBiggerThan2Gb];
	int s64 = 0;
	for (int i = 0; i < indexablePositions.length; i++) {
	PackedObjectInfo info = allObjects.get(indexablePositions[i]);
	if (info.getFullSize() < Integer.MAX_VALUE) {
	writeInt32((int) info.getFullSize());
	} else {
	// Size needs more than 32 bits. Store -1 * offset in the
	// next table as size.
	writeInt32(-1 * (s64 + 1));
	NB.encodeInt64(sizes64bits, s64 * 8, info.getFullSize());
	s64++;
	}
	}
	if (objsBiggerThan2Gb > 0) {
	writeInt32(objsBiggerThan2Gb);
	os.write(sizes64bits);
	}
	writeInt32(0);
	}

	private int[] findIndexablePositions(
	List<? extends PackedObjectInfo> allObjects,
	int indexableObjs) {
	int[] positions = new int[indexableObjs];
	int positionIdx = 0;
	for (int i = 0; i < allObjects.size(); i++) {
	PackedObjectInfo o = allObjects.get(i);
	if (!shouldIndex(o)) {
	continue;
	}
	positions[positionIdx++] = i;
	}
	return positions;
	}

	private PackedObjectStats countIndexableObjects(
	List<? extends PackedObjectInfo> objs) {
	PackedObjectStats stats = new PackedObjectStats();
	for (int i = 0; i < objs.size(); i++) {
	PackedObjectInfo o = objs.get(i);
	if (!shouldIndex(o)) {
	continue;
	}
	stats.indexableObjs++;
	if (o.getFullSize() > Integer.MAX_VALUE) {
	stats.sizeOver2GB++;
	}
	if (i <= MAX_24BITS_UINT) {
	stats.pos24Bits++;
	} else {
	stats.pos31Bits++;
	// i is a positive int, cannot be bigger than this
	}
	}
	return stats;
	}

	private boolean shouldIndex(PackedObjectInfo o) {
	return (o.getType() == Constants.OBJ_BLOB)
	&& (o.getFullSize() >= minObjSize);
	}

	private static class PackedObjectStats {
	int indexableObjs;

	int pos24Bits;

	int pos31Bits;

	int sizeOver2GB;
	}

	@FunctionalInterface
	interface IntEncoder {
	void encode(int i) throws IOException;
	}

	private static void applyToRange(int[] allPositions, int start, int end,
	IntEncoder encoder) throws IOException {
	for (int i = start; i < end; i++) {
	encoder.encode(allPositions[i]);
	}
	}
	}
	}