PackIndexV2.java

  1. /*
  2.  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> 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.  */

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

  11. import java.io.IOException;
  12. import java.io.InputStream;
  13. import java.text.MessageFormat;
  14. import java.util.Arrays;
  15. import java.util.Iterator;
  16. import java.util.NoSuchElementException;
  17. import java.util.Set;

  18. import org.eclipse.jgit.errors.MissingObjectException;
  19. import org.eclipse.jgit.internal.JGitText;
  20. import org.eclipse.jgit.lib.AbbreviatedObjectId;
  21. import org.eclipse.jgit.lib.AnyObjectId;
  22. import org.eclipse.jgit.lib.Constants;
  23. import org.eclipse.jgit.lib.ObjectId;
  24. import org.eclipse.jgit.util.IO;
  25. import org.eclipse.jgit.util.NB;

  26. /** Support for the pack index v2 format. */
  27. class PackIndexV2 extends PackIndex {
  28.     private static final long IS_O64 = 1L << 31;

  29.     private static final int FANOUT = 256;

  30.     private static final int[] NO_INTS = {};

  31.     private static final byte[] NO_BYTES = {};

  32.     private long objectCnt;

  33.     private final long[] fanoutTable;

  34.     /** 256 arrays of contiguous object names. */
  35.     int[][] names;

  36.     /** 256 arrays of the 32 bit offset data, matching {@link #names}. */
  37.     byte[][] offset32;

  38.     /** 256 arrays of the CRC-32 of objects, matching {@link #names}. */
  39.     private byte[][] crc32;

  40.     /** 64 bit offset table. */
  41.     byte[] offset64;

  42.     PackIndexV2(final InputStream fd) throws IOException {
  43.         final byte[] fanoutRaw = new byte[4 * FANOUT];
  44.         IO.readFully(fd, fanoutRaw, 0, fanoutRaw.length);
  45.         fanoutTable = new long[FANOUT];
  46.         for (int k = 0; k < FANOUT; k++)
  47.             fanoutTable[k] = NB.decodeUInt32(fanoutRaw, k * 4);
  48.         objectCnt = fanoutTable[FANOUT - 1];

  49.         names = new int[FANOUT][];
  50.         offset32 = new byte[FANOUT][];
  51.         crc32 = new byte[FANOUT][];

  52.         // Object name table. The size we can permit per fan-out bucket
  53.         // is limited to Java's 2 GB per byte array limitation. That is
  54.         // no more than 107,374,182 objects per fan-out.
  55.         //
  56.         for (int k = 0; k < FANOUT; k++) {
  57.             final long bucketCnt;
  58.             if (k == 0)
  59.                 bucketCnt = fanoutTable[k];
  60.             else
  61.                 bucketCnt = fanoutTable[k] - fanoutTable[k - 1];

  62.             if (bucketCnt == 0) {
  63.                 names[k] = NO_INTS;
  64.                 offset32[k] = NO_BYTES;
  65.                 crc32[k] = NO_BYTES;
  66.                 continue;
  67.             } else if (bucketCnt < 0)
  68.                 throw new IOException(MessageFormat.format(
  69.                         JGitText.get().indexFileCorruptedNegativeBucketCount,
  70.                         Long.valueOf(bucketCnt)));

  71.             final long nameLen = bucketCnt * Constants.OBJECT_ID_LENGTH;
  72.             if (nameLen > Integer.MAX_VALUE - 8) // see http://stackoverflow.com/a/8381338
  73.                 throw new IOException(JGitText.get().indexFileIsTooLargeForJgit);

  74.             final int intNameLen = (int) nameLen;
  75.             final byte[] raw = new byte[intNameLen];
  76.             final int[] bin = new int[intNameLen >>> 2];
  77.             IO.readFully(fd, raw, 0, raw.length);
  78.             for (int i = 0; i < bin.length; i++)
  79.                 bin[i] = NB.decodeInt32(raw, i << 2);

  80.             names[k] = bin;
  81.             offset32[k] = new byte[(int) (bucketCnt * 4)];
  82.             crc32[k] = new byte[(int) (bucketCnt * 4)];
  83.         }

  84.         // CRC32 table.
  85.         for (int k = 0; k < FANOUT; k++)
  86.             IO.readFully(fd, crc32[k], 0, crc32[k].length);

  87.         // 32 bit offset table. Any entries with the most significant bit
  88.         // set require a 64 bit offset entry in another table.
  89.         //
  90.         int o64cnt = 0;
  91.         for (int k = 0; k < FANOUT; k++) {
  92.             final byte[] ofs = offset32[k];
  93.             IO.readFully(fd, ofs, 0, ofs.length);
  94.             for (int p = 0; p < ofs.length; p += 4)
  95.                 if (ofs[p] < 0)
  96.                     o64cnt++;
  97.         }

  98.         // 64 bit offset table. Most objects should not require an entry.
  99.         //
  100.         if (o64cnt > 0) {
  101.             offset64 = new byte[o64cnt * 8];
  102.             IO.readFully(fd, offset64, 0, offset64.length);
  103.         } else {
  104.             offset64 = NO_BYTES;
  105.         }

  106.         packChecksum = new byte[20];
  107.         IO.readFully(fd, packChecksum, 0, packChecksum.length);
  108.     }

  109.     /** {@inheritDoc} */
  110.     @Override
  111.     public long getObjectCount() {
  112.         return objectCnt;
  113.     }

  114.     /** {@inheritDoc} */
  115.     @Override
  116.     public long getOffset64Count() {
  117.         return offset64.length / 8;
  118.     }

  119.     private int findLevelOne(long nthPosition) {
  120.         int levelOne = Arrays.binarySearch(fanoutTable, nthPosition + 1);
  121.         if (levelOne >= 0) {
  122.             // If we hit the bucket exactly the item is in the bucket, or
  123.             // any bucket before it which has the same object count.
  124.             //
  125.             long base = fanoutTable[levelOne];
  126.             while (levelOne > 0 && base == fanoutTable[levelOne - 1])
  127.                 levelOne--;
  128.         } else {
  129.             // The item is in the bucket we would insert it into.
  130.             //
  131.             levelOne = -(levelOne + 1);
  132.         }
  133.         return levelOne;
  134.     }

  135.     private int getLevelTwo(long nthPosition, int levelOne) {
  136.         final long base = levelOne > 0 ? fanoutTable[levelOne - 1] : 0;
  137.         return (int) (nthPosition - base);
  138.     }

  139.     /** {@inheritDoc} */
  140.     @Override
  141.     public ObjectId getObjectId(long nthPosition) {
  142.         final int levelOne = findLevelOne(nthPosition);
  143.         final int p = getLevelTwo(nthPosition, levelOne);
  144.         final int p4 = p << 2;
  145.         return ObjectId.fromRaw(names[levelOne], p4 + p); // p * 5
  146.     }

  147.     /** {@inheritDoc} */
  148.     @Override
  149.     public long getOffset(long nthPosition) {
  150.         final int levelOne = findLevelOne(nthPosition);
  151.         final int levelTwo = getLevelTwo(nthPosition, levelOne);
  152.         return getOffset(levelOne, levelTwo);
  153.     }

  154.     /** {@inheritDoc} */
  155.     @Override
  156.     public long findOffset(AnyObjectId objId) {
  157.         final int levelOne = objId.getFirstByte();
  158.         final int levelTwo = binarySearchLevelTwo(objId, levelOne);
  159.         if (levelTwo == -1)
  160.             return -1;
  161.         return getOffset(levelOne, levelTwo);
  162.     }

  163.     private long getOffset(int levelOne, int levelTwo) {
  164.         final long p = NB.decodeUInt32(offset32[levelOne], levelTwo << 2);
  165.         if ((p & IS_O64) != 0)
  166.             return NB.decodeUInt64(offset64, (8 * (int) (p & ~IS_O64)));
  167.         return p;
  168.     }

  169.     /** {@inheritDoc} */
  170.     @Override
  171.     public long findCRC32(AnyObjectId objId) throws MissingObjectException {
  172.         final int levelOne = objId.getFirstByte();
  173.         final int levelTwo = binarySearchLevelTwo(objId, levelOne);
  174.         if (levelTwo == -1)
  175.             throw new MissingObjectException(objId.copy(), "unknown"); //$NON-NLS-1$
  176.         return NB.decodeUInt32(crc32[levelOne], levelTwo << 2);
  177.     }

  178.     /** {@inheritDoc} */
  179.     @Override
  180.     public boolean hasCRC32Support() {
  181.         return true;
  182.     }

  183.     /** {@inheritDoc} */
  184.     @Override
  185.     public Iterator<MutableEntry> iterator() {
  186.         return new EntriesIteratorV2();
  187.     }

  188.     /** {@inheritDoc} */
  189.     @Override
  190.     public void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
  191.             int matchLimit) throws IOException {
  192.         int[] data = names[id.getFirstByte()];
  193.         int max = offset32[id.getFirstByte()].length >>> 2;
  194.         int high = max;
  195.         if (high == 0)
  196.             return;
  197.         int low = 0;
  198.         do {
  199.             int p = (low + high) >>> 1;
  200.             final int cmp = id.prefixCompare(data, idOffset(p));
  201.             if (cmp < 0)
  202.                 high = p;
  203.             else if (cmp == 0) {
  204.                 // We may have landed in the middle of the matches.  Move
  205.                 // backwards to the start of matches, then walk forwards.
  206.                 //
  207.                 while (0 < p && id.prefixCompare(data, idOffset(p - 1)) == 0)
  208.                     p--;
  209.                 for (; p < max && id.prefixCompare(data, idOffset(p)) == 0; p++) {
  210.                     matches.add(ObjectId.fromRaw(data, idOffset(p)));
  211.                     if (matches.size() > matchLimit)
  212.                         break;
  213.                 }
  214.                 return;
  215.             } else
  216.                 low = p + 1;
  217.         } while (low < high);
  218.     }

  219.     private static int idOffset(int p) {
  220.         return (p << 2) + p; // p * 5
  221.     }

  222.     private int binarySearchLevelTwo(AnyObjectId objId, int levelOne) {
  223.         final int[] data = names[levelOne];
  224.         int high = offset32[levelOne].length >>> 2;
  225.         if (high == 0)
  226.             return -1;
  227.         int low = 0;
  228.         do {
  229.             final int mid = (low + high) >>> 1;
  230.             final int mid4 = mid << 2;
  231.             final int cmp;

  232.             cmp = objId.compareTo(data, mid4 + mid); // mid * 5
  233.             if (cmp < 0)
  234.                 high = mid;
  235.             else if (cmp == 0) {
  236.                 return mid;
  237.             } else
  238.                 low = mid + 1;
  239.         } while (low < high);
  240.         return -1;
  241.     }

  242.     private class EntriesIteratorV2 extends EntriesIterator {
  243.         int levelOne;

  244.         int levelTwo;

  245.         @Override
  246.         protected MutableEntry initEntry() {
  247.             return new MutableEntry() {
  248.                 @Override
  249.                 protected void ensureId() {
  250.                     idBuffer.fromRaw(names[levelOne], levelTwo
  251.                             - Constants.OBJECT_ID_LENGTH / 4);
  252.                 }
  253.             };
  254.         }

  255.         @Override
  256.         public MutableEntry next() {
  257.             for (; levelOne < names.length; levelOne++) {
  258.                 if (levelTwo < names[levelOne].length) {
  259.                     int idx = levelTwo / (Constants.OBJECT_ID_LENGTH / 4) * 4;
  260.                     long offset = NB.decodeUInt32(offset32[levelOne], idx);
  261.                     if ((offset & IS_O64) != 0) {
  262.                         idx = (8 * (int) (offset & ~IS_O64));
  263.                         offset = NB.decodeUInt64(offset64, idx);
  264.                     }
  265.                     entry.offset = offset;

  266.                     levelTwo += Constants.OBJECT_ID_LENGTH / 4;
  267.                     returnedNumber++;
  268.                     return entry;
  269.                 }
  270.                 levelTwo = 0;
  271.             }
  272.             throw new NoSuchElementException();
  273.         }
  274.     }

  275. }