PackBitmapIndexV1.java

  1. /*
  2.  * Copyright (C) 2012, Google Inc. and others
  3.  *
  4.  * This program and the accompanying materials are made available under the
  5.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  6.  * https://www.eclipse.org/org/documents/edl-v10.php.
  7.  *
  8.  * SPDX-License-Identifier: BSD-3-Clause
  9.  */

  11. package org.eclipse.jgit.internal.storage.file;

  13. import java.io.DataInput;
  14. import java.io.IOException;
  15. import java.io.InputStream;
  16. import java.text.MessageFormat;
  17. import java.util.ArrayList;
  18. import java.util.Arrays;
  19. import java.util.List;
  20. import java.util.concurrent.ExecutionException;
  21. import java.util.concurrent.ExecutorService;
  22. import java.util.concurrent.Executors;
  23. import java.util.concurrent.Future;
  24. import java.util.concurrent.ThreadFactory;
  25. import java.util.concurrent.atomic.AtomicInteger;

  27. import org.eclipse.jgit.annotations.Nullable;
  28. import org.eclipse.jgit.internal.JGitText;
  29. import org.eclipse.jgit.lib.AnyObjectId;
  30. import org.eclipse.jgit.lib.Constants;
  31. import org.eclipse.jgit.lib.ObjectId;
  32. import org.eclipse.jgit.lib.ObjectIdOwnerMap;
  33. import org.eclipse.jgit.util.IO;
  34. import org.eclipse.jgit.util.NB;

  36. import com.googlecode.javaewah.EWAHCompressedBitmap;

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

  47.     private static final int MAX_XOR_OFFSET = 126;

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

  54.                 private final AtomicInteger threadNumber = new AtomicInteger(0);

  56.                 @Override
  57.                 public Thread newThread(Runnable runnable) {
  58.                     Thread thread = baseFactory.newThread(runnable);
  59.                     thread.setName("JGit-PackBitmapIndexV1-" //$NON-NLS-1$
  60.                             + threadNumber.getAndIncrement());
  61.                     thread.setDaemon(true);
  62.                     return thread;
  63.                 }
  64.             });

  66.     private final PackIndex packIndex;
  67.     private final PackReverseIndex reverseIndex;
  68.     private final EWAHCompressedBitmap commits;
  69.     private final EWAHCompressedBitmap trees;
  70.     private final EWAHCompressedBitmap blobs;
  71.     private final EWAHCompressedBitmap tags;

  73.     private final ObjectIdOwnerMap<StoredBitmap> bitmaps;

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

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

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

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

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

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

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

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

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

  134.         // Read the bitmaps for the Git types
  135.         SimpleDataInput dataInput = new SimpleDataInput(fd);
  136.         this.commits = readBitmap(dataInput);
  137.         this.trees = readBitmap(dataInput);
  138.         this.blobs = readBitmap(dataInput);
  139.         this.tags = readBitmap(dataInput);

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

  152.             if (nthObjectId < 0) {
  153.                 throw new IOException(MessageFormat.format(
  154.                         JGitText.get().invalidId, String.valueOf(nthObjectId)));
  155.             }
  156.             if (xorOffset < 0) {
  157.                 throw new IOException(MessageFormat.format(
  158.                         JGitText.get().invalidId, String.valueOf(xorOffset)));
  159.             }
  160.             if (xorOffset > MAX_XOR_OFFSET) {
  161.                 throw new IOException(MessageFormat.format(
  162.                         JGitText.get().expectedLessThanGot,
  163.                         String.valueOf(MAX_XOR_OFFSET),
  164.                         String.valueOf(xorOffset)));
  165.             }
  166.             if (xorOffset > i) {
  167.                 throw new IOException(MessageFormat.format(
  168.                         JGitText.get().expectedLessThanGot, String.valueOf(i),
  169.                         String.valueOf(xorOffset)));
  170.             }
  171.             IdxPositionBitmap xorIdxPositionBitmap = null;
  172.             if (xorOffset > 0) {
  173.                 int index = (i - xorOffset);
  174.                 xorIdxPositionBitmap = recentBitmaps[index
  175.                         % recentBitmaps.length];
  176.                 if (xorIdxPositionBitmap == null) {
  177.                     throw new IOException(MessageFormat.format(
  178.                             JGitText.get().invalidId,
  179.                             String.valueOf(xorOffset)));
  180.                 }
  181.             }
  182.             IdxPositionBitmap idxPositionBitmap = new IdxPositionBitmap(
  183.                     nthObjectId, xorIdxPositionBitmap, bitmap, flags);
  184.             idxPositionBitmapList.add(idxPositionBitmap);
  185.             recentBitmaps[i % recentBitmaps.length] = idxPositionBitmap;
  186.         }

  188.         this.packIndex = packIndexSupplier.get();
  189.         for (int i = 0; i < idxPositionBitmapList.size(); ++i) {
  190.             IdxPositionBitmap idxPositionBitmap = idxPositionBitmapList.get(i);
  191.             ObjectId objectId = packIndex
  192.                     .getObjectId(idxPositionBitmap.nthObjectId);
  193.             StoredBitmap sb = new StoredBitmap(objectId,
  194.                     idxPositionBitmap.bitmap,
  195.                     idxPositionBitmap.getXorStoredBitmap(),
  196.                     idxPositionBitmap.flags);
  197.             // Save the StoredBitmap for a possible future XorStoredBitmap
  198.             // reference.
  199.             idxPositionBitmap.sb = sb;
  200.             bitmaps.add(sb);
  201.         }

  203.         PackReverseIndex computedReverseIndex;
  204.         if (loadParallelRevIndex && reverseIndexFuture != null) {
  205.             try {
  206.                 computedReverseIndex = reverseIndexFuture.get();
  207.             } catch (InterruptedException | ExecutionException e) {
  208.                 // Fallback to loading reverse index through a supplier.
  209.                 computedReverseIndex = reverseIndexSupplier.get();
  210.             }
  211.         } else {
  212.             computedReverseIndex = reverseIndexSupplier.get();
  213.         }
  214.         this.reverseIndex = computedReverseIndex;
  215.     }

  217.     /** {@inheritDoc} */
  218.     @Override
  219.     public int findPosition(AnyObjectId objectId) {
  220.         long offset = packIndex.findOffset(objectId);
  221.         if (offset == -1)
  222.             return -1;
  223.         return reverseIndex.findPostion(offset);
  224.     }

  226.     /** {@inheritDoc} */
  227.     @Override
  228.     public ObjectId getObject(int position) throws IllegalArgumentException {
  229.         ObjectId objectId = reverseIndex.findObjectByPosition(position);
  230.         if (objectId == null)
  231.             throw new IllegalArgumentException();
  232.         return objectId;
  233.     }

  235.     /** {@inheritDoc} */
  236.     @Override
  237.     public int getObjectCount() {
  238.         return (int) packIndex.getObjectCount();
  239.     }

  241.     /** {@inheritDoc} */
  242.     @Override
  243.     public EWAHCompressedBitmap ofObjectType(
  244.             EWAHCompressedBitmap bitmap, int type) {
  245.         switch (type) {
  246.         case Constants.OBJ_BLOB:
  247.             return blobs.and(bitmap);
  248.         case Constants.OBJ_TREE:
  249.             return trees.and(bitmap);
  250.         case Constants.OBJ_COMMIT:
  251.             return commits.and(bitmap);
  252.         case Constants.OBJ_TAG:
  253.             return tags.and(bitmap);
  254.         }
  255.         throw new IllegalArgumentException();
  256.     }

  258.     /** {@inheritDoc} */
  259.     @Override
  260.     public int getBitmapCount() {
  261.         return bitmaps.size();
  262.     }

  264.     /** {@inheritDoc} */
  265.     @Override
  266.     public boolean equals(Object o) {
  267.         // TODO(cranger): compare the pack checksum?
  268.         if (o instanceof PackBitmapIndexV1)
  269.             return getPackIndex() == ((PackBitmapIndexV1) o).getPackIndex();
  270.         return false;
  271.     }

  273.     /** {@inheritDoc} */
  274.     @Override
  275.     public int hashCode() {
  276.         return getPackIndex().hashCode();
  277.     }

  279.     PackIndex getPackIndex() {
  280.         return packIndex;
  281.     }

  283.     private static EWAHCompressedBitmap readBitmap(DataInput dataInput)
  284.             throws IOException {
  285.         EWAHCompressedBitmap bitmap = new EWAHCompressedBitmap();
  286.         bitmap.deserialize(dataInput);
  287.         return bitmap;
  288.     }

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

  297.         IdxPositionBitmap xorIdxPositionBitmap;

  299.         EWAHCompressedBitmap bitmap;

  301.         int flags;

  303.         StoredBitmap sb;

  305.         IdxPositionBitmap(int nthObjectId,
  306.                 @Nullable IdxPositionBitmap xorIdxPositionBitmap,
  307.                 EWAHCompressedBitmap bitmap, int flags) {
  308.             this.nthObjectId = nthObjectId;
  309.             this.xorIdxPositionBitmap = xorIdxPositionBitmap;
  310.             this.bitmap = bitmap;
  311.             this.flags = flags;
  312.         }

  314.         StoredBitmap getXorStoredBitmap() {
  315.             return xorIdxPositionBitmap == null ? null
  316.                     : xorIdxPositionBitmap.sb;
  317.         }
  318.     }
  319. }
Created with JaCoCo 0.8.7.202105040129