BlockReader.java

  1. /*
  2.  * Copyright (C) 2017, 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.reftable;

  13. import static java.nio.charset.StandardCharsets.UTF_8;
  14. import static org.eclipse.jgit.internal.storage.reftable.BlockWriter.compare;
  15. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_BLOCK_TYPE;
  16. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_HEADER_LEN;
  17. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.INDEX_BLOCK_TYPE;
  18. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_BLOCK_TYPE;
  19. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_DATA;
  20. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_NONE;
  21. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.OBJ_BLOCK_TYPE;
  22. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.REF_BLOCK_TYPE;
  23. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_1ID;
  24. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_2ID;
  25. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_NONE;
  26. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_SYMREF;
  27. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_TYPE_MASK;
  28. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.reverseUpdateIndex;
  29. import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;
  30. import static org.eclipse.jgit.lib.Ref.Storage.NEW;
  31. import static org.eclipse.jgit.lib.Ref.Storage.PACKED;

  33. import java.io.IOException;
  34. import java.nio.ByteBuffer;
  35. import java.util.Arrays;
  36. import java.util.zip.DataFormatException;
  37. import java.util.zip.Inflater;

  39. import org.eclipse.jgit.annotations.Nullable;
  40. import org.eclipse.jgit.internal.JGitText;
  41. import org.eclipse.jgit.internal.storage.io.BlockSource;
  42. import org.eclipse.jgit.lib.CheckoutEntry;
  43. import org.eclipse.jgit.lib.InflaterCache;
  44. import org.eclipse.jgit.lib.ObjectId;
  45. import org.eclipse.jgit.lib.ObjectIdRef;
  46. import org.eclipse.jgit.lib.PersonIdent;
  47. import org.eclipse.jgit.lib.Ref;
  48. import org.eclipse.jgit.lib.ReflogEntry;
  49. import org.eclipse.jgit.lib.SymbolicRef;
  50. import org.eclipse.jgit.util.LongList;
  51. import org.eclipse.jgit.util.NB;
  52. import org.eclipse.jgit.util.RawParseUtils;

  54. /**
  55.  * Reads a single block for {@link ReftableReader}. Instances are tied to a
  56.  * specific block in the file so are not reused for other blocks. Instances hold
  57.  * an offset into the block.
  58.  */
  59. class BlockReader {
  60.     private byte blockType;
  61.     private long endPosition;

  63.     private byte[] buf;
  64.     private int bufLen;
  65.     private int ptr;

  67.     private int keysStart;
  68.     private int keysEnd;

  70.     private int restartCnt;
  71.     private int restartTbl;

  73.     private byte[] nameBuf = new byte[256];
  74.     private int nameLen;
  75.     private int valueType;

  77.     byte type() {
  78.         return blockType;
  79.     }

  81.     long endPosition() {
  82.         return endPosition;
  83.     }

  85.     boolean next() {
  86.         return ptr < keysEnd;
  87.     }

  89.     void parseKey() {
  90.         int pfx = readVarint32();
  91.         valueType = readVarint32();
  92.         int sfx = valueType >>> 3;
  93.         if (pfx + sfx > nameBuf.length) {
  94.             int n = Math.max(pfx + sfx, nameBuf.length * 2);
  95.             nameBuf = Arrays.copyOf(nameBuf, n);
  96.         }
  97.         System.arraycopy(buf, ptr, nameBuf, pfx, sfx);
  98.         ptr += sfx;
  99.         nameLen = pfx + sfx;
  100.     }

  102.     String name() {
  103.         int len = nameLen;
  104.         if (blockType == LOG_BLOCK_TYPE) {
  105.             len -= 9;
  106.         }
  107.         return RawParseUtils.decode(UTF_8, nameBuf, 0, len);
  108.     }

  110.     // Matches the key against a name or a prefix. For reflogs, only the
  111.     // refname is matched, and the updateIndex suffix is ignored.
  112.     boolean match(byte[] match, boolean matchIsPrefix) {
  113.         int len = nameLen;
  114.         if (blockType == LOG_BLOCK_TYPE) {
  115.             len -= 9;
  116.         }
  117.         if (matchIsPrefix) {
  118.             return len >= match.length
  119.                     && compare(
  120.                             match, 0, match.length,
  121.                             nameBuf, 0, match.length) == 0;
  122.         }
  123.         return compare(match, 0, match.length, nameBuf, 0, len) == 0;
  124.     }

  126.     long readPositionFromIndex() throws IOException {
  127.         if (blockType != INDEX_BLOCK_TYPE) {
  128.             throw invalidBlock();
  129.         }

  131.         readVarint32(); // skip prefix length
  132.         int n = readVarint32() >>> 3;
  133.         ptr += n; // skip name
  134.         return readVarint64();
  135.     }

  137.     long readUpdateIndexDelta() {
  138.         return readVarint64();
  139.     }

  141.     Ref readRef(long minUpdateIndex) throws IOException {
  142.         long updateIndex = minUpdateIndex + readUpdateIndexDelta();
  143.         String name = RawParseUtils.decode(UTF_8, nameBuf, 0, nameLen);
  144.         switch (valueType & VALUE_TYPE_MASK) {
  145.         case VALUE_NONE: // delete
  146.             return newRef(name, updateIndex);

  148.         case VALUE_1ID:
  149.             return new ObjectIdRef.PeeledNonTag(PACKED, name, readValueId(),
  150.                     updateIndex);

  152.         case VALUE_2ID: { // annotated tag
  153.             ObjectId id1 = readValueId();
  154.             ObjectId id2 = readValueId();
  155.             return new ObjectIdRef.PeeledTag(PACKED, name, id1, id2,
  156.                     updateIndex);
  157.         }

  159.         case VALUE_SYMREF: {
  160.             String val = readValueString();
  161.             return new SymbolicRef(name, newRef(val, updateIndex), updateIndex);
  162.         }

  164.         default:
  165.             throw invalidBlock();
  166.         }
  167.     }

  169.     @Nullable
  170.     LongList readBlockPositionList() {
  171.         int n = valueType & VALUE_TYPE_MASK;
  172.         if (n == 0) {
  173.             n = readVarint32();
  174.             if (n == 0) {
  175.                 return null;
  176.             }
  177.         }

  179.         LongList b = new LongList(n);
  180.         b.add(readVarint64());
  181.         for (int j = 1; j < n; j++) {
  182.             long prior = b.get(j - 1);
  183.             b.add(prior + readVarint64());
  184.         }
  185.         return b;
  186.     }

  188.     long readLogUpdateIndex() {
  189.         return reverseUpdateIndex(NB.decodeUInt64(nameBuf, nameLen - 8));
  190.     }

  192.     @Nullable
  193.     ReflogEntry readLogEntry() {
  194.         if ((valueType & VALUE_TYPE_MASK) == LOG_NONE) {
  195.             return null;
  196.         }

  198.         ObjectId oldId = readValueId();
  199.         ObjectId newId = readValueId();
  200.         PersonIdent who = readPersonIdent();
  201.         String msg = readValueString();

  203.         return new ReflogEntry() {
  204.             @Override
  205.             public ObjectId getOldId() {
  206.                 return oldId;
  207.             }

  209.             @Override
  210.             public ObjectId getNewId() {
  211.                 return newId;
  212.             }

  214.             @Override
  215.             public PersonIdent getWho() {
  216.                 return who;
  217.             }

  219.             @Override
  220.             public String getComment() {
  221.                 return msg;
  222.             }

  224.             @Override
  225.             public CheckoutEntry parseCheckout() {
  226.                 return null;
  227.             }
  228.         };
  229.     }

  231.     private ObjectId readValueId() {
  232.         ObjectId id = ObjectId.fromRaw(buf, ptr);
  233.         ptr += OBJECT_ID_LENGTH;
  234.         return id;
  235.     }

  237.     private String readValueString() {
  238.         int len = readVarint32();
  239.         int end = ptr + len;
  240.         String s = RawParseUtils.decode(UTF_8, buf, ptr, end);
  241.         ptr = end;
  242.         return s;
  243.     }

  245.     private PersonIdent readPersonIdent() {
  246.         String name = readValueString();
  247.         String email = readValueString();
  248.         long ms = readVarint64() * 1000;
  249.         int tz = readInt16();
  250.         return new PersonIdent(name, email, ms, tz);
  251.     }

  253.     void readBlock(BlockSource src, long pos, int fileBlockSize)
  254.             throws IOException {
  255.         readBlockIntoBuf(src, pos, fileBlockSize);
  256.         parseBlockStart(src, pos, fileBlockSize);
  257.     }

  259.     private void readBlockIntoBuf(BlockSource src, long pos, int size)
  260.             throws IOException {
  261.         ByteBuffer b = src.read(pos, size);
  262.         bufLen = b.position();
  263.         if (bufLen <= 0) {
  264.             throw invalidBlock();
  265.         }
  266.         if (b.hasArray() && b.arrayOffset() == 0) {
  267.             buf = b.array();
  268.         } else {
  269.             buf = new byte[bufLen];
  270.             b.flip();
  271.             b.get(buf);
  272.         }
  273.         endPosition = pos + bufLen;
  274.     }

  276.     private void parseBlockStart(BlockSource src, long pos, int fileBlockSize)
  277.             throws IOException {
  278.         ptr = 0;
  279.         if (pos == 0) {
  280.             if (bufLen == FILE_HEADER_LEN) {
  281.                 setupEmptyFileBlock();
  282.                 return;
  283.             }
  284.             ptr += FILE_HEADER_LEN; // first block begins with file header
  285.         }

  287.         int typeAndSize = NB.decodeInt32(buf, ptr);
  288.         ptr += 4;

  290.         blockType = (byte) (typeAndSize >>> 24);
  291.         int blockLen = decodeBlockLen(typeAndSize);
  292.         if (blockType == LOG_BLOCK_TYPE) {
  293.             // Log blocks must be inflated after the header.
  294.             long deflatedSize = inflateBuf(src, pos, blockLen, fileBlockSize);
  295.             endPosition = pos + 4 + deflatedSize;
  296.         } else if (bufLen < blockLen) {
  297.             readBlockIntoBuf(src, pos, blockLen);
  298.         } else if (bufLen > blockLen) {
  299.             bufLen = blockLen;
  300.         }

  302.         if (blockType != FILE_BLOCK_TYPE) {
  303.             restartCnt = NB.decodeUInt16(buf, bufLen - 2);
  304.             restartTbl = bufLen - (restartCnt * 3 + 2);
  305.             keysStart = ptr;
  306.             keysEnd = restartTbl;
  307.         } else {
  308.             keysStart = ptr;
  309.             keysEnd = ptr;
  310.         }
  311.     }

  313.     static int decodeBlockLen(int typeAndSize) {
  314.         return typeAndSize & 0xffffff;
  315.     }

  317.     private long inflateBuf(BlockSource src, long pos, int blockLen,
  318.             int fileBlockSize) throws IOException {
  319.         byte[] dst = new byte[blockLen];
  320.         System.arraycopy(buf, 0, dst, 0, 4);

  322.         long deflatedSize = 0;
  323.         Inflater inf = InflaterCache.get();
  324.         try {
  325.             inf.setInput(buf, ptr, bufLen - ptr);
  326.             for (int o = 4;;) {
  327.                 int n = inf.inflate(dst, o, dst.length - o);
  328.                 o += n;
  329.                 if (inf.finished()) {
  330.                     deflatedSize = inf.getBytesRead();
  331.                     break;
  332.                 } else if (n <= 0 && inf.needsInput()) {
  333.                     long p = pos + 4 + inf.getBytesRead();
  334.                     readBlockIntoBuf(src, p, fileBlockSize);
  335.                     inf.setInput(buf, 0, bufLen);
  336.                 } else if (n <= 0) {
  337.                     throw invalidBlock();
  338.                 }
  339.             }
  340.         } catch (DataFormatException e) {
  341.             throw invalidBlock(e);
  342.         } finally {
  343.             InflaterCache.release(inf);
  344.         }

  346.         buf = dst;
  347.         bufLen = dst.length;
  348.         return deflatedSize;
  349.     }

  351.     private void setupEmptyFileBlock() {
  352.         // An empty reftable has only the file header in first block.
  353.         blockType = FILE_BLOCK_TYPE;
  354.         ptr = FILE_HEADER_LEN;
  355.         restartCnt = 0;
  356.         restartTbl = bufLen;
  357.         keysStart = bufLen;
  358.         keysEnd = bufLen;
  359.     }

  361.     void verifyIndex() throws IOException {
  362.         if (blockType != INDEX_BLOCK_TYPE) {
  363.             throw invalidBlock();
  364.         }
  365.     }

  367.     /**
  368.      * Finds a key in the block and positions the current pointer on its record.
  369.      * <p>
  370.      * As a side-effect this method arranges for the current pointer to be near
  371.      * or exactly on {@code key}, allowing other methods to access data from
  372.      * that current record:
  373.      * <ul>
  374.      * <li>{@link #name()}
  375.      * <li>{@link #match(byte[], boolean)}
  376.      * <li>{@link #readRef(long)}
  377.      * <li>{@link #readLogUpdateIndex()}
  378.      * <li>{@link #readLogEntry()}
  379.      * <li>{@link #readBlockPositionList()}
  380.      * </ul>
  381.      *
  382.      * @param key
  383.      *            key to find.
  384.      * @return {@code <0} if the key occurs before the start of this block;
  385.      *         {@code 0} if the block is positioned on the key; {@code >0} if
  386.      *         the key occurs after the last key of this block.
  387.      */
  388.     int seekKey(byte[] key) {
  389.         int low = 0;
  390.         int end = restartCnt;
  391.         for (;;) {
  392.             int mid = (low + end) >>> 1;
  393.             int p = NB.decodeUInt24(buf, restartTbl + mid * 3);
  394.             ptr = p + 1; // skip 0 prefix length
  395.             int n = readVarint32() >>> 3;
  396.             int cmp = compare(key, 0, key.length, buf, ptr, n);
  397.             if (cmp < 0) {
  398.                 end = mid;
  399.             } else if (cmp == 0) {
  400.                 ptr = p;
  401.                 return 0;
  402.             } else /* if (cmp > 0) */ {
  403.                 low = mid + 1;
  404.             }
  405.             if (low >= end) {
  406.                 return scanToKey(key, p, low, cmp);
  407.             }
  408.         }
  409.     }

  411.     /**
  412.      * Performs the linear search step within a restart interval.
  413.      * <p>
  414.      * Starts at a restart position whose key sorts before (or equal to)
  415.      * {@code key} and walks sequentially through the following prefix
  416.      * compressed records to find {@code key}.
  417.      *
  418.      * @param key
  419.      *            key the caller wants to find.
  420.      * @param rPtr
  421.      *            current record pointer from restart table binary search.
  422.      * @param rIdx
  423.      *            current restart table index.
  424.      * @param rCmp
  425.      *            result of compare from restart table binary search.
  426.      * @return {@code <0} if the key occurs before the start of this block;
  427.      *         {@code 0} if the block is positioned on the key; {@code >0} if
  428.      *         the key occurs after the last key of this block.
  429.      */
  430.     private int scanToKey(byte[] key, int rPtr, int rIdx, int rCmp) {
  431.         if (rCmp < 0) {
  432.             if (rIdx == 0) {
  433.                 ptr = keysStart;
  434.                 return -1;
  435.             }
  436.             ptr = NB.decodeUInt24(buf, restartTbl + (rIdx - 1) * 3);
  437.         } else {
  438.             ptr = rPtr;
  439.         }

  441.         int cmp;
  442.         do {
  443.             int savePtr = ptr;
  444.             parseKey();
  445.             cmp = compare(key, 0, key.length, nameBuf, 0, nameLen);
  446.             if (cmp <= 0) {
  447.                 // cmp < 0, name should be in this block, but is not.
  448.                 // cmp = 0, block is positioned at name.
  449.                 ptr = savePtr;
  450.                 return cmp < 0 && savePtr == keysStart ? -1 : 0;
  451.             }
  452.             skipValue();
  453.         } while (ptr < keysEnd);
  454.         return cmp;
  455.     }

  457.     void skipValue() {
  458.         switch (blockType) {
  459.         case REF_BLOCK_TYPE:
  460.             readVarint64(); // update_index_delta
  461.             switch (valueType & VALUE_TYPE_MASK) {
  462.             case VALUE_NONE:
  463.                 return;
  464.             case VALUE_1ID:
  465.                 ptr += OBJECT_ID_LENGTH;
  466.                 return;
  467.             case VALUE_2ID:
  468.                 ptr += 2 * OBJECT_ID_LENGTH;
  469.                 return;
  470.             case VALUE_SYMREF:
  471.                 skipString();
  472.                 return;
  473.             }
  474.             break;

  476.         case OBJ_BLOCK_TYPE: {
  477.             int n = valueType & VALUE_TYPE_MASK;
  478.             if (n == 0) {
  479.                 n = readVarint32();
  480.             }
  481.             while (n-- > 0) {
  482.                 readVarint32();
  483.             }
  484.             return;
  485.         }

  487.         case INDEX_BLOCK_TYPE:
  488.             readVarint32();
  489.             return;

  491.         case LOG_BLOCK_TYPE:
  492.             if ((valueType & VALUE_TYPE_MASK) == LOG_NONE) {
  493.                 return;
  494.             } else if ((valueType & VALUE_TYPE_MASK) == LOG_DATA) {
  495.                 ptr += 2 * OBJECT_ID_LENGTH; // oldId, newId
  496.                 skipString(); // name
  497.                 skipString(); // email
  498.                 readVarint64(); // time
  499.                 ptr += 2; // tz
  500.                 skipString(); // msg
  501.                 return;
  502.             }
  503.         }

  505.         throw new IllegalStateException();
  506.     }

  508.     private void skipString() {
  509.         int n = readVarint32(); // string length
  510.         ptr += n;
  511.     }

  513.     private short readInt16() {
  514.         short result =(short) NB.decodeUInt16(buf, ptr);
  515.         ptr += 2;
  516.         return result;
  517.     }

  519.     private int readVarint32() {
  520.         byte c = buf[ptr++];
  521.         int val = c & 0x7f;
  522.         while ((c & 0x80) != 0) {
  523.             c = buf[ptr++];
  524.             val++;
  525.             val <<= 7;
  526.             val |= (c & 0x7f);
  527.         }
  528.         return val;
  529.     }

  531.     private long readVarint64() {
  532.         byte c = buf[ptr++];
  533.         long val = c & 0x7f;
  534.         while ((c & 0x80) != 0) {
  535.             c = buf[ptr++];
  536.             val++;
  537.             val <<= 7;
  538.             val |= (c & 0x7f);
  539.         }
  540.         return val;
  541.     }

  543.     private static Ref newRef(String name, long updateIndex) {
  544.         return new ObjectIdRef.Unpeeled(NEW, name, null, updateIndex);
  545.     }

  547.     private static IOException invalidBlock() {
  548.         return invalidBlock(null);
  549.     }

  551.     private static IOException invalidBlock(Throwable cause) {
  552.         return new IOException(JGitText.get().invalidReftableBlock, cause);
  553.     }
  554. }
Created with JaCoCo 0.8.7.202105040129