BlockWriter.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.ReftableConstants.FILE_HEADER_LEN;
  15. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.INDEX_BLOCK_TYPE;
  16. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_BLOCK_TYPE;
  17. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_DATA;
  18. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_NONE;
  19. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.MAX_RESTARTS;
  20. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.OBJ_BLOCK_TYPE;
  21. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.REF_BLOCK_TYPE;
  22. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_1ID;
  23. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_2ID;
  24. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_NONE;
  25. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_SYMREF;
  26. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_TYPE_MASK;
  27. import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.reverseUpdateIndex;
  28. import static org.eclipse.jgit.internal.storage.reftable.ReftableOutputStream.computeVarintSize;
  29. import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;
  30. import static org.eclipse.jgit.lib.Ref.Storage.NEW;

  32. import java.io.IOException;
  33. import java.util.ArrayList;
  34. import java.util.Arrays;
  35. import java.util.List;

  37. import org.eclipse.jgit.internal.JGitText;
  38. import org.eclipse.jgit.lib.ObjectId;
  39. import org.eclipse.jgit.lib.PersonIdent;
  40. import org.eclipse.jgit.lib.Ref;
  41. import org.eclipse.jgit.util.IntList;
  42. import org.eclipse.jgit.util.LongList;
  43. import org.eclipse.jgit.util.NB;

  45. /** Formats and writes blocks for {@link ReftableWriter}. */
  46. class BlockWriter {
  47.     private final byte blockType;
  48.     private final byte keyType;
  49.     private final List<Entry> entries;
  50.     private final int blockLimitBytes;
  51.     private final int restartInterval;

  53.     private int entriesSumBytes;
  54.     private int restartCnt;

  56.     BlockWriter(byte type, byte kt, int bs, int ri) {
  57.         blockType = type;
  58.         keyType = kt;
  59.         blockLimitBytes = bs;
  60.         restartInterval = ri;
  61.         entries = new ArrayList<>(estimateEntryCount(type, kt, bs));
  62.     }

  64.     private static int estimateEntryCount(byte blockType, byte keyType,
  65.             int blockLimitBytes) {
  66.         double avgBytesPerEntry;
  67.         switch (blockType) {
  68.         case REF_BLOCK_TYPE:
  69.         default:
  70.             avgBytesPerEntry = 35.31;
  71.             break;

  73.         case OBJ_BLOCK_TYPE:
  74.             avgBytesPerEntry = 4.19;
  75.             break;

  77.         case LOG_BLOCK_TYPE:
  78.             avgBytesPerEntry = 101.14;
  79.             break;

  81.         case INDEX_BLOCK_TYPE:
  82.             switch (keyType) {
  83.             case REF_BLOCK_TYPE:
  84.             case LOG_BLOCK_TYPE:
  85.             default:
  86.                 avgBytesPerEntry = 27.44;
  87.                 break;

  89.             case OBJ_BLOCK_TYPE:
  90.                 avgBytesPerEntry = 11.57;
  91.                 break;
  92.             }
  93.         }

  95.         int cnt = (int) (Math.ceil(blockLimitBytes / avgBytesPerEntry));
  96.         return Math.min(cnt, 4096);
  97.     }

  99.     byte blockType() {
  100.         return blockType;
  101.     }

  103.     boolean padBetweenBlocks() {
  104.         return padBetweenBlocks(blockType)
  105.                 || (blockType == INDEX_BLOCK_TYPE && padBetweenBlocks(keyType));
  106.     }

  108.     static boolean padBetweenBlocks(byte type) {
  109.         return type == REF_BLOCK_TYPE || type == OBJ_BLOCK_TYPE;
  110.     }

  112.     byte[] lastKey() {
  113.         return entries.get(entries.size() - 1).key;
  114.     }

  116.     int currentSize() {
  117.         return computeBlockBytes(0, false);
  118.     }

  120.     void mustAdd(Entry entry) throws BlockSizeTooSmallException {
  121.         if (!tryAdd(entry, true)) {
  122.             // Insanely long names need a larger block size.
  123.             throw blockSizeTooSmall(entry);
  124.         }
  125.     }

  127.     boolean tryAdd(Entry entry) {
  128.         if (entry instanceof ObjEntry
  129.                 && computeBlockBytes(entry.sizeBytes(), 1) > blockLimitBytes) {
  130.             // If the ObjEntry has so many ref block pointers that its
  131.             // encoding overflows any block, reconfigure it to tell readers to
  132.             // instead scan all refs for this ObjectId. That significantly
  133.             // shrinks the entry to a very small size, which may now fit into
  134.             // this block.
  135.             ((ObjEntry) entry).markScanRequired();
  136.         }

  138.         if (tryAdd(entry, true)) {
  139.             return true;
  140.         } else if (nextShouldBeRestart()) {
  141.             // It was time for another restart, but the entry doesn't fit
  142.             // with its complete key, as the block is nearly full. Try to
  143.             // force it to fit with prefix compression rather than waste
  144.             // the tail of the block with padding.
  145.             return tryAdd(entry, false);
  146.         }
  147.         return false;
  148.     }

  150.     private boolean tryAdd(Entry entry, boolean tryRestart) {
  151.         byte[] key = entry.key;
  152.         int prefixLen = 0;
  153.         boolean restart = tryRestart && nextShouldBeRestart();
  154.         if (!restart) {
  155.             Entry priorEntry = entries.get(entries.size() - 1);
  156.             byte[] prior = priorEntry.key;
  157.             prefixLen = commonPrefix(prior, prior.length, key);
  158.             if (prefixLen <= 5 /* "refs/" */ && keyType == REF_BLOCK_TYPE) {
  159.                 // Force restart points at transitions between namespaces
  160.                 // such as "refs/heads/" to "refs/tags/".
  161.                 restart = true;
  162.                 prefixLen = 0;
  163.             } else if (prefixLen == 0) {
  164.                 restart = true;
  165.             }
  166.         }

  168.         entry.restart = restart;
  169.         entry.prefixLen = prefixLen;
  170.         int entryBytes = entry.sizeBytes();
  171.         if (computeBlockBytes(entryBytes, restart) > blockLimitBytes) {
  172.             return false;
  173.         }

  175.         entriesSumBytes += entryBytes;
  176.         entries.add(entry);
  177.         if (restart) {
  178.             restartCnt++;
  179.         }
  180.         return true;
  181.     }

  183.     private boolean nextShouldBeRestart() {
  184.         int cnt = entries.size();
  185.         return (cnt == 0 || ((cnt + 1) % restartInterval) == 0)
  186.                 && restartCnt < MAX_RESTARTS;
  187.     }

  189.     private int computeBlockBytes(int entryBytes, boolean restart) {
  190.         return computeBlockBytes(
  191.                 entriesSumBytes + entryBytes,
  192.                 restartCnt + (restart ? 1 : 0));
  193.     }

  195.     private static int computeBlockBytes(int entryBytes, int restartCnt) {
  196.         return 4 // 4-byte block header
  197.                 + entryBytes
  198.                 + restartCnt * 3 // restart_offset
  199.                 + 2; // 2-byte restart_count
  200.     }

  202.     void writeTo(ReftableOutputStream os) throws IOException {
  203.         os.beginBlock(blockType);
  204.         IntList restarts = new IntList(restartCnt);
  205.         for (Entry entry : entries) {
  206.             if (entry.restart) {
  207.                 restarts.add(os.bytesWrittenInBlock());
  208.             }
  209.             entry.writeKey(os);
  210.             entry.writeValue(os);
  211.         }
  212.         if (restarts.size() == 0 || restarts.size() > MAX_RESTARTS) {
  213.             throw new IllegalStateException();
  214.         }
  215.         for (int i = 0; i < restarts.size(); i++) {
  216.             os.writeInt24(restarts.get(i));
  217.         }
  218.         os.writeInt16(restarts.size());
  219.         os.flushBlock();
  220.     }

  222.     private BlockSizeTooSmallException blockSizeTooSmall(Entry entry) {
  223.         // Compute size required to fit this entry by itself.
  224.         int min = FILE_HEADER_LEN + computeBlockBytes(entry.sizeBytes(), 1);
  225.         return new BlockSizeTooSmallException(min);
  226.     }

  228.     static int commonPrefix(byte[] a, int n, byte[] b) {
  229.         int len = Math.min(n, Math.min(a.length, b.length));
  230.         for (int i = 0; i < len; i++) {
  231.             if (a[i] != b[i]) {
  232.                 return i;
  233.             }
  234.         }
  235.         return len;
  236.     }

  238.     static int encodeSuffixAndType(int sfx, int valueType) {
  239.         return (sfx << 3) | valueType;
  240.     }

  242.     static int compare(
  243.             byte[] a, int ai, int aLen,
  244.             byte[] b, int bi, int bLen) {
  245.         int aEnd = ai + aLen;
  246.         int bEnd = bi + bLen;
  247.         while (ai < aEnd && bi < bEnd) {
  248.             int c = (a[ai++] & 0xff) - (b[bi++] & 0xff);
  249.             if (c != 0) {
  250.                 return c;
  251.             }
  252.         }
  253.         return aLen - bLen;
  254.     }

  256.     abstract static class Entry {
  257.         static int compare(Entry ea, Entry eb) {
  258.             byte[] a = ea.key;
  259.             byte[] b = eb.key;
  260.             return BlockWriter.compare(a, 0, a.length, b, 0, b.length);
  261.         }

  263.         final byte[] key;
  264.         int prefixLen;
  265.         boolean restart;

  267.         Entry(byte[] key) {
  268.             this.key = key;
  269.         }

  271.         void writeKey(ReftableOutputStream os) {
  272.             int sfxLen = key.length - prefixLen;
  273.             os.writeVarint(prefixLen);
  274.             os.writeVarint(encodeSuffixAndType(sfxLen, valueType()));
  275.             os.write(key, prefixLen, sfxLen);
  276.         }

  278.         int sizeBytes() {
  279.             int sfxLen = key.length - prefixLen;
  280.             int sfx = encodeSuffixAndType(sfxLen, valueType());
  281.             return computeVarintSize(prefixLen)
  282.                     + computeVarintSize(sfx)
  283.                     + sfxLen
  284.                     + valueSize();
  285.         }

  287.         abstract byte blockType();
  288.         abstract int valueType();
  289.         abstract int valueSize();
  290.         abstract void writeValue(ReftableOutputStream os) throws IOException;
  291.     }

  293.     static class IndexEntry extends Entry {
  294.         private final long blockPosition;

  296.         IndexEntry(byte[] key, long blockPosition) {
  297.             super(key);
  298.             this.blockPosition = blockPosition;
  299.         }

  301.         @Override
  302.         byte blockType() {
  303.             return INDEX_BLOCK_TYPE;
  304.         }

  306.         @Override
  307.         int valueType() {
  308.             return 0;
  309.         }

  311.         @Override
  312.         int valueSize() {
  313.             return computeVarintSize(blockPosition);
  314.         }

  316.         @Override
  317.         void writeValue(ReftableOutputStream os) {
  318.             os.writeVarint(blockPosition);
  319.         }
  320.     }

  322.     static class RefEntry extends Entry {
  323.         final Ref ref;
  324.         final long updateIndexDelta;

  326.         RefEntry(Ref ref, long updateIndexDelta) {
  327.             super(nameUtf8(ref));
  328.             this.ref = ref;
  329.             this.updateIndexDelta = updateIndexDelta;
  330.         }

  332.         @Override
  333.         byte blockType() {
  334.             return REF_BLOCK_TYPE;
  335.         }

  337.         @Override
  338.         int valueType() {
  339.             if (ref.isSymbolic()) {
  340.                 return VALUE_SYMREF;
  341.             } else if (ref.getStorage() == NEW && ref.getObjectId() == null) {
  342.                 return VALUE_NONE;
  343.             } else if (ref.getPeeledObjectId() != null) {
  344.                 return VALUE_2ID;
  345.             } else {
  346.                 return VALUE_1ID;
  347.             }
  348.         }

  350.         @Override
  351.         int valueSize() {
  352.             int n = computeVarintSize(updateIndexDelta);
  353.             switch (valueType()) {
  354.             case VALUE_NONE:
  355.                 return n;
  356.             case VALUE_1ID:
  357.                 return n + OBJECT_ID_LENGTH;
  358.             case VALUE_2ID:
  359.                 return n + 2 * OBJECT_ID_LENGTH;
  360.             case VALUE_SYMREF:
  361.                 if (ref.isSymbolic()) {
  362.                     int nameLen = nameUtf8(ref.getTarget()).length;
  363.                     return n + computeVarintSize(nameLen) + nameLen;
  364.                 }
  365.             }
  366.             throw new IllegalStateException();
  367.         }

  369.         @Override
  370.         void writeValue(ReftableOutputStream os) throws IOException {
  371.             os.writeVarint(updateIndexDelta);
  372.             switch (valueType()) {
  373.             case VALUE_NONE:
  374.                 return;

  376.             case VALUE_1ID: {
  377.                 ObjectId id1 = ref.getObjectId();
  378.                 if (!ref.isPeeled()) {
  379.                     throw new IOException(JGitText.get().peeledRefIsRequired);
  380.                 } else if (id1 == null) {
  381.                     throw new IOException(JGitText.get().invalidId0);
  382.                 }
  383.                 os.writeId(id1);
  384.                 return;
  385.             }

  387.             case VALUE_2ID: {
  388.                 ObjectId id1 = ref.getObjectId();
  389.                 ObjectId id2 = ref.getPeeledObjectId();
  390.                 if (!ref.isPeeled()) {
  391.                     throw new IOException(JGitText.get().peeledRefIsRequired);
  392.                 } else if (id1 == null || id2 == null) {
  393.                     throw new IOException(JGitText.get().invalidId0);
  394.                 }
  395.                 os.writeId(id1);
  396.                 os.writeId(id2);
  397.                 return;
  398.             }

  400.             case VALUE_SYMREF:
  401.                 if (ref.isSymbolic()) {
  402.                     os.writeVarintString(ref.getTarget().getName());
  403.                     return;
  404.                 }
  405.             }
  406.             throw new IllegalStateException();
  407.         }

  409.         private static byte[] nameUtf8(Ref ref) {
  410.             return ref.getName().getBytes(UTF_8);
  411.         }
  412.     }

  414.     static class ObjEntry extends Entry {
  415.         final LongList blockPos;

  417.         ObjEntry(int idLen, ObjectId id, LongList blockPos) {
  418.             super(key(idLen, id));
  419.             this.blockPos = blockPos;
  420.         }

  422.         private static byte[] key(int idLen, ObjectId id) {
  423.             byte[] key = new byte[OBJECT_ID_LENGTH];
  424.             id.copyRawTo(key, 0);
  425.             if (idLen < OBJECT_ID_LENGTH) {
  426.                 return Arrays.copyOf(key, idLen);
  427.             }
  428.             return key;
  429.         }

  431.         void markScanRequired() {
  432.             blockPos.clear();
  433.         }

  435.         @Override
  436.         byte blockType() {
  437.             return OBJ_BLOCK_TYPE;
  438.         }

  440.         @Override
  441.         int valueType() {
  442.             int cnt = blockPos.size();
  443.             return cnt != 0 && cnt <= VALUE_TYPE_MASK ? cnt : 0;
  444.         }

  446.         @Override
  447.         int valueSize() {
  448.             int cnt = blockPos.size();
  449.             if (cnt == 0) {
  450.                 return computeVarintSize(0);
  451.             }

  453.             int n = 0;
  454.             if (cnt > VALUE_TYPE_MASK) {
  455.                 n += computeVarintSize(cnt);
  456.             }
  457.             n += computeVarintSize(blockPos.get(0));
  458.             for (int j = 1; j < cnt; j++) {
  459.                 long prior = blockPos.get(j - 1);
  460.                 long b = blockPos.get(j);
  461.                 n += computeVarintSize(b - prior);
  462.             }
  463.             return n;
  464.         }

  466.         @Override
  467.         void writeValue(ReftableOutputStream os) throws IOException {
  468.             int cnt = blockPos.size();
  469.             if (cnt == 0) {
  470.                 os.writeVarint(0);
  471.                 return;
  472.             }

  474.             if (cnt > VALUE_TYPE_MASK) {
  475.                 os.writeVarint(cnt);
  476.             }
  477.             os.writeVarint(blockPos.get(0));
  478.             for (int j = 1; j < cnt; j++) {
  479.                 long prior = blockPos.get(j - 1);
  480.                 long b = blockPos.get(j);
  481.                 os.writeVarint(b - prior);
  482.             }
  483.         }
  484.     }

  486.     static class DeleteLogEntry extends Entry {
  487.         DeleteLogEntry(String refName, long updateIndex) {
  488.             super(LogEntry.key(refName, updateIndex));
  489.         }

  491.         @Override
  492.         byte blockType() {
  493.             return LOG_BLOCK_TYPE;
  494.         }

  496.         @Override
  497.         int valueType() {
  498.             return LOG_NONE;
  499.         }

  501.         @Override
  502.         int valueSize() {
  503.             return 0;
  504.         }

  506.         @Override
  507.         void writeValue(ReftableOutputStream os) {
  508.             // Nothing in a delete log record.
  509.         }
  510.     }

  512.     static class LogEntry extends Entry {
  513.         final ObjectId oldId;
  514.         final ObjectId newId;
  515.         final long timeSecs;
  516.         final short tz;
  517.         final byte[] name;
  518.         final byte[] email;
  519.         final byte[] msg;

  521.         LogEntry(String refName, long updateIndex, PersonIdent who,
  522.                 ObjectId oldId, ObjectId newId, String message) {
  523.             super(key(refName, updateIndex));

  525.             this.oldId = oldId;
  526.             this.newId = newId;
  527.             this.timeSecs = who.getWhen().getTime() / 1000L;
  528.             this.tz = (short) who.getTimeZoneOffset();
  529.             this.name = who.getName().getBytes(UTF_8);
  530.             this.email = who.getEmailAddress().getBytes(UTF_8);
  531.             this.msg = message.getBytes(UTF_8);
  532.         }

  534.         static byte[] key(String ref, long index) {
  535.             byte[] name = ref.getBytes(UTF_8);
  536.             byte[] key = Arrays.copyOf(name, name.length + 1 + 8);
  537.             NB.encodeInt64(key, key.length - 8, reverseUpdateIndex(index));
  538.             return key;
  539.         }

  541.         @Override
  542.         byte blockType() {
  543.             return LOG_BLOCK_TYPE;
  544.         }

  546.         @Override
  547.         int valueType() {
  548.             return LOG_DATA;
  549.         }

  551.         @Override
  552.         int valueSize() {
  553.             return 2 * OBJECT_ID_LENGTH
  554.                     + computeVarintSize(name.length) + name.length
  555.                     + computeVarintSize(email.length) + email.length
  556.                     + computeVarintSize(timeSecs)
  557.                     + 2 // tz
  558.                     + computeVarintSize(msg.length) + msg.length;
  559.         }

  561.         @Override
  562.         void writeValue(ReftableOutputStream os) {
  563.             os.writeId(oldId);
  564.             os.writeId(newId);
  565.             os.writeVarintString(name);
  566.             os.writeVarintString(email);
  567.             os.writeVarint(timeSecs);
  568.             os.writeInt16(tz);
  569.             os.writeVarintString(msg);
  570.         }
  571.     }
  572. }
Created with JaCoCo 0.8.6.202009150832