* A chunk typically contains thousands of objects, compressed in the Git native * pack file format. Its associated {@link ChunkIndex} provides offsets for each * object's header and compressed data. *
* Chunks (and their indexes) are opaque binary blobs meant only to be read by * the Git implementation. */ public final class PackChunk { /** Constructs a {@link PackChunk} while reading from the DHT. */ public static class Members { private ChunkKey chunkKey; private byte[] dataBuf; private int dataPtr; private int dataLen; private byte[] indexBuf; private int indexPtr; private int indexLen; private ChunkMeta meta; /** @return the chunk key. Never null. */ public ChunkKey getChunkKey() { return chunkKey; } /** * @param key * @return {@code this} */ public Members setChunkKey(ChunkKey key) { this.chunkKey = key; return this; } /** @return true if there is chunk data present. */ public boolean hasChunkData() { return dataBuf != null; } /** @return the chunk data, or null if not available. */ public byte[] getChunkData() { return asArray(dataBuf, dataPtr, dataLen); } /** @return the chunk data, or null if not available. */ public ByteBuffer getChunkDataAsByteBuffer() { return asByteBuffer(dataBuf, dataPtr, dataLen); } private static byte[] asArray(byte[] buf, int ptr, int len) { if (buf == null) return null; if (ptr == 0 && buf.length == len) return buf; byte[] r = new byte[len]; System.arraycopy(buf, ptr, r, 0, len); return r; } private static ByteBuffer asByteBuffer(byte[] buf, int ptr, int len) { return buf != null ? ByteBuffer.wrap(buf, ptr, len) : null; } /** * @param chunkData * @return {@code this} */ public Members setChunkData(byte[] chunkData) { return setChunkData(chunkData, 0, chunkData.length); } /** * @param chunkData * @param ptr * @param len * @return {@code this} */ public Members setChunkData(byte[] chunkData, int ptr, int len) { this.dataBuf = chunkData; this.dataPtr = ptr; this.dataLen = len; return this; } /** @return true if there is a chunk index present. */ public boolean hasChunkIndex() { return indexBuf != null; } /** @return the chunk index, or null if not available. */ public byte[] getChunkIndex() { return asArray(indexBuf, indexPtr, indexLen); } /** @return the chunk index, or null if not available. */ public ByteBuffer getChunkIndexAsByteBuffer() { return asByteBuffer(indexBuf, indexPtr, indexLen); } /** * @param chunkIndex * @return {@code this} */ public Members setChunkIndex(byte[] chunkIndex) { return setChunkIndex(chunkIndex, 0, chunkIndex.length); } /** * @param chunkIndex * @param ptr * @param len * @return {@code this} */ public Members setChunkIndex(byte[] chunkIndex, int ptr, int len) { this.indexBuf = chunkIndex; this.indexPtr = ptr; this.indexLen = len; return this; } /** @return true if there is meta information present. */ public boolean hasMeta() { return meta != null; } /** @return the inline meta data, or null if not available. */ public ChunkMeta getMeta() { return meta; } /** * @param meta * @return {@code this} */ public Members setMeta(ChunkMeta meta) { this.meta = meta; return this; } /** * @return the PackChunk instance. * @throws DhtException * if early validation indicates the chunk data is corrupt * or not recognized by this version of the library. */ public PackChunk build() throws DhtException { ChunkIndex i; if (indexBuf != null) i = ChunkIndex.fromBytes(chunkKey, indexBuf, indexPtr, indexLen); else i = null; return new PackChunk(chunkKey, dataBuf, dataPtr, dataLen, i, meta); } } private static final int INFLATE_STRIDE = 512; private final ChunkKey key; private final byte[] dataBuf; private final int dataPtr; private final int dataLen; private final ChunkIndex index; private final ChunkMeta meta; private volatile Boolean valid; PackChunk(ChunkKey key, byte[] dataBuf, int dataPtr, int dataLen, ChunkIndex index, ChunkMeta meta) { this.key = key; this.dataBuf = dataBuf; this.dataPtr = dataPtr; this.dataLen = dataLen; this.index = index; this.meta = meta; } /** @return unique name of this chunk in the database. */ public ChunkKey getChunkKey() { return key; } /** @return index describing the objects stored within this chunk. */ public ChunkIndex getIndex() { return index; } /** @return inline meta information, or null if no data was necessary. */ public ChunkMeta getMeta() { return meta; } @Override public String toString() { return "PackChunk[" + getChunkKey() + "]"; } boolean hasIndex() { return index != null; } boolean isFragment() { return meta != null && 0 < meta.getFragmentCount(); } int findOffset(RepositoryKey repo, AnyObjectId objId) { if (key.getRepositoryId() == repo.asInt() && index != null) return index.findOffset(objId); return -1; } boolean contains(RepositoryKey repo, AnyObjectId objId) { return 0 <= findOffset(repo, objId); } static ObjectLoader read(PackChunk pc, int pos, final DhtReader ctx, final int typeHint) throws IOException { try { return read1(pc, pos, ctx, typeHint, true /* use recentChunks */); } catch (DeltaChainCycleException cycleFound) { // A cycle can occur if recentChunks cache was used by the reader // to satisfy an OBJ_REF_DELTA, but the chunk that was chosen has // a reverse delta back onto an object already being read during // this invocation. Its not as uncommon as it sounds, as the Git // wire protocol can sometimes copy an object the repository already // has when dealing with reverts or cherry-picks. // // Work around the cycle by disabling the recentChunks cache for // this resolution only. This will force the DhtReader to re-read // OBJECT_INDEX and consider only the oldest chunk for any given // object. There cannot be a cycle if the method only walks along // the oldest chunks. try { ctx.getStatistics().deltaChainCycles++; return read1(pc, pos, ctx, typeHint, false /* no recentChunks */); } catch (DeltaChainCycleException cannotRecover) { throw new DhtException(MessageFormat.format( DhtText.get().cycleInDeltaChain, pc.getChunkKey(), Integer.valueOf(pos))); } } } @SuppressWarnings("null") private static ObjectLoader read1(PackChunk pc, int pos, final DhtReader ctx, final int typeHint, final boolean recent) throws IOException, DeltaChainCycleException { try { Delta delta = null; byte[] data = null; int type = OBJ_BAD; boolean cached = false; SEARCH: for (;;) { final byte[] dataBuf = pc.dataBuf; final int dataPtr = pc.dataPtr; final int posPtr = dataPtr + pos; int c = dataBuf[posPtr] & 0xff; int typeCode = (c >> 4) & 7; long sz = c & 15; int shift = 4; int p = 1; while ((c & 0x80) != 0) { c = dataBuf[posPtr + p++] & 0xff; sz += ((long) (c & 0x7f)) << shift; shift += 7; } switch (typeCode) { case OBJ_COMMIT: case OBJ_TREE: case OBJ_BLOB: case OBJ_TAG: { if (delta != null) { data = inflate(sz, pc, pos + p, ctx); type = typeCode; break SEARCH; } if (sz < Integer.MAX_VALUE && !pc.isFragment()) { try { data = pc.inflateOne(sz, pos + p, ctx); return new ObjectLoader.SmallObject(typeCode, data); } catch (LargeObjectException tooBig) { // Fall through and stream. } } return new LargeNonDeltaObject(typeCode, sz, pc, pos + p, ctx); } case OBJ_OFS_DELTA: { c = dataBuf[posPtr + p++] & 0xff; long base = c & 127; while ((c & 128) != 0) { base += 1; c = dataBuf[posPtr + p++] & 0xff; base <<= 7; base += (c & 127); } ChunkKey baseChunkKey; int basePosInChunk; if (base <= pos) { // Base occurs in the same chunk, just earlier. baseChunkKey = pc.getChunkKey(); basePosInChunk = pos - (int) base; } else { // Long offset delta, base occurs in another chunk. // Adjust distance to be from our chunk start. base = base - pos; ChunkMeta.BaseChunk baseChunk; baseChunk = ChunkMetaUtil.getBaseChunk( pc.key, pc.meta, base); baseChunkKey = ChunkKey.fromString(baseChunk.getChunkKey()); basePosInChunk = (int) (baseChunk.getRelativeStart() - base); } delta = new Delta(delta, // pc.key, pos, (int) sz, p, // baseChunkKey, basePosInChunk); if (sz != delta.deltaSize) break SEARCH; DeltaBaseCache.Entry e = delta.getBase(ctx); if (e != null) { type = e.type; data = e.data; cached = true; break SEARCH; } if (baseChunkKey != pc.getChunkKey()) pc = ctx.getChunk(baseChunkKey); pos = basePosInChunk; continue SEARCH; } case OBJ_REF_DELTA: { ObjectId id = ObjectId.fromRaw(dataBuf, posPtr + p); PackChunk nc = pc; int base = pc.index.findOffset(id); if (base < 0) { DhtReader.ChunkAndOffset n; n = ctx.getChunk(id, typeHint, recent); nc = n.chunk; base = n.offset; } checkCycle(delta, pc.key, pos); delta = new Delta(delta, // pc.key, pos, (int) sz, p + 20, // nc.getChunkKey(), base); if (sz != delta.deltaSize) break SEARCH; DeltaBaseCache.Entry e = delta.getBase(ctx); if (e != null) { type = e.type; data = e.data; cached = true; break SEARCH; } pc = nc; pos = base; continue SEARCH; } default: throw new DhtException(MessageFormat.format( DhtText.get().unsupportedObjectTypeInChunk, // Integer.valueOf(typeCode), // pc.getChunkKey(), // Integer.valueOf(pos))); } } // At this point there is at least one delta to apply to data. // (Whole objects with no deltas to apply return early above.) do { if (!delta.deltaChunk.equals(pc.getChunkKey())) pc = ctx.getChunk(delta.deltaChunk); pos = delta.deltaPos; // Cache only the base immediately before desired object. if (cached) cached = false; else if (delta.next == null) delta.putBase(ctx, type, data); final byte[] cmds = delta.decompress(pc, ctx); final long sz = BinaryDelta.getResultSize(cmds); final byte[] result = newResult(sz); BinaryDelta.apply(data, cmds, result); data = result; delta = delta.next; } while (delta != null); return new ObjectLoader.SmallObject(type, data); } catch (DataFormatException dfe) { CorruptObjectException coe = new CorruptObjectException( MessageFormat.format(DhtText.get().corruptCompressedObject, pc.getChunkKey(), Integer.valueOf(pos))); coe.initCause(dfe); throw coe; } } private static byte[] inflate(long sz, PackChunk pc, int pos, DhtReader reader) throws DataFormatException, DhtException { if (pc.isFragment()) return inflateFragment(sz, pc, pos, reader); return pc.inflateOne(sz, pos, reader); } private byte[] inflateOne(long sz, int pos, DhtReader reader) throws DataFormatException { // Because the chunk ends in a 4 byte CRC, there is always // more data available for input than the inflater needs. // This also helps with an optimization in libz where it // wants at least 1 extra byte of input beyond the end. final byte[] dstbuf = newResult(sz); final Inflater inf = reader.inflater(); final int offset = pos; int dstoff = 0; int bs = Math.min(dataLen - pos, INFLATE_STRIDE); inf.setInput(dataBuf, dataPtr + pos, bs); pos += bs; while (dstoff < dstbuf.length) { int n = inf.inflate(dstbuf, dstoff, dstbuf.length - dstoff); if (n == 0) { if (inf.needsInput()) { bs = Math.min(dataLen - pos, INFLATE_STRIDE); inf.setInput(dataBuf, dataPtr + pos, bs); pos += bs; continue; } break; } dstoff += n; } if (dstoff != sz) { throw new DataFormatException(MessageFormat.format( DhtText.get().shortCompressedObject, getChunkKey(), Integer.valueOf(offset))); } return dstbuf; } private static byte[] inflateFragment(long sz, PackChunk pc, final int pos, DhtReader reader) throws DataFormatException, DhtException { byte[] dstbuf = newResult(sz); int dstoff = 0; final Inflater inf = reader.inflater(); final ChunkMeta meta = pc.meta; int nextChunk = 1; int bs = pc.dataLen - pos - TRAILER_SIZE; inf.setInput(pc.dataBuf, pc.dataPtr + pos, bs); while (dstoff < dstbuf.length) { int n = inf.inflate(dstbuf, dstoff, dstbuf.length - dstoff); if (n == 0) { if (inf.needsInput()) { if (meta.getFragmentCount() <= nextChunk) break; pc = reader.getChunk(ChunkKey.fromString( meta.getFragment(nextChunk++))); if (meta.getFragmentCount() == nextChunk) bs = pc.dataLen; // Include trailer on last chunk. else bs = pc.dataLen - TRAILER_SIZE; inf.setInput(pc.dataBuf, pc.dataPtr, bs); continue; } break; } dstoff += n; } if (dstoff != sz) { throw new DataFormatException(MessageFormat.format( DhtText.get().shortCompressedObject, ChunkKey.fromString(meta.getFragment(0)), Integer.valueOf(pos))); } return dstbuf; } private static byte[] newResult(long sz) { if (Integer.MAX_VALUE < sz) throw new LargeObjectException.ExceedsByteArrayLimit(); try { return new byte[(int) sz]; } catch (OutOfMemoryError noMemory) { throw new LargeObjectException.OutOfMemory(noMemory); } } int readObjectTypeAndSize(int ptr, PackParser.ObjectTypeAndSize info) { ptr += dataPtr; int c = dataBuf[ptr++] & 0xff; int typeCode = (c >> 4) & 7; long sz = c & 15; int shift = 4; while ((c & 0x80) != 0) { c = dataBuf[ptr++] & 0xff; sz += ((long) (c & 0x7f)) << shift; shift += 7; } switch (typeCode) { case OBJ_OFS_DELTA: c = dataBuf[ptr++] & 0xff; while ((c & 128) != 0) c = dataBuf[ptr++] & 0xff; break; case OBJ_REF_DELTA: ptr += 20; break; } info.type = typeCode; info.size = sz; return ptr - dataPtr; } int read(int ptr, byte[] dst, int dstPos, int cnt) { // Do not allow readers to read the CRC-32 from the tail. int n = Math.min(cnt, (dataLen - TRAILER_SIZE) - ptr); System.arraycopy(dataBuf, dataPtr + ptr, dst, dstPos, n); return n; } void copyObjectAsIs(PackOutputStream out, DhtObjectToPack obj, boolean validate, DhtReader ctx) throws IOException, StoredObjectRepresentationNotAvailableException { if (validate && !isValid()) { StoredObjectRepresentationNotAvailableException gone; gone = new StoredObjectRepresentationNotAvailableException(obj); gone.initCause(new DhtException(MessageFormat.format( DhtText.get().corruptChunk, getChunkKey()))); throw gone; } int ptr = dataPtr + obj.offset; int c = dataBuf[ptr++] & 0xff; int typeCode = (c >> 4) & 7; long inflatedSize = c & 15; int shift = 4; while ((c & 0x80) != 0) { c = dataBuf[ptr++] & 0xff; inflatedSize += ((long) (c & 0x7f)) << shift; shift += 7; } switch (typeCode) { case OBJ_OFS_DELTA: do { c = dataBuf[ptr++] & 0xff; } while ((c & 128) != 0); break; case OBJ_REF_DELTA: ptr += 20; break; } // If the size is positive, its accurate. If its -1, this is a // fragmented object that will need more handling below, // so copy all of the chunk, minus the trailer. final int maxAvail = (dataLen - TRAILER_SIZE) - (ptr - dataPtr); final int copyLen; if (0 < obj.size) copyLen = Math.min(obj.size, maxAvail); else if (-1 == obj.size) copyLen = maxAvail; else throw new DhtException(MessageFormat.format( DhtText.get().expectedObjectSizeDuringCopyAsIs, obj)); out.writeHeader(obj, inflatedSize); out.write(dataBuf, ptr, copyLen); // If the object was fragmented, send all of the other fragments. if (isFragment()) { int cnt = meta.getFragmentCount(); for (int fragId = 1; fragId < cnt; fragId++) { PackChunk pc = ctx.getChunk(ChunkKey.fromString( meta.getFragment(fragId))); pc.copyEntireChunkAsIs(out, obj, validate); } } } void copyEntireChunkAsIs(PackOutputStream out, DhtObjectToPack obj, boolean validate) throws IOException { if (validate && !isValid()) { if (obj != null) throw new CorruptObjectException(obj, MessageFormat.format( DhtText.get().corruptChunk, getChunkKey())); else throw new DhtException(MessageFormat.format( DhtText.get().corruptChunk, getChunkKey())); } // Do not copy the trailer onto the output stream. out.write(dataBuf, dataPtr, dataLen - TRAILER_SIZE); } @SuppressWarnings("boxing") private boolean isValid() { Boolean v = valid; if (v == null) { MessageDigest m = newMessageDigest(); m.update(dataBuf, dataPtr, dataLen); v = key.getChunkHash().compareTo(m.digest(), 0) == 0; valid = v; } return v.booleanValue(); } /** @return the complete size of this chunk, in memory. */ int getTotalSize() { // Assume the index is part of the buffer, and report its total size.. if (dataPtr != 0 || dataLen != dataBuf.length) return dataBuf.length; int sz = dataLen; if (index != null) sz += index.getIndexSize(); return sz; } private static class Delta { /** Child that applies onto this object. */ final Delta next; /** The chunk the delta is stored in. */ final ChunkKey deltaChunk; /** Offset of the delta object. */ final int deltaPos; /** Size of the inflated delta stream. */ final int deltaSize; /** Total size of the delta's pack entry header (including base). */ final int hdrLen; /** The chunk the base is stored in. */ final ChunkKey baseChunk; /** Offset of the base object. */ final int basePos; Delta(Delta next, ChunkKey dc, int ofs, int sz, int hdrLen, ChunkKey bc, int bp) { this.next = next; this.deltaChunk = dc; this.deltaPos = ofs; this.deltaSize = sz; this.hdrLen = hdrLen; this.baseChunk = bc; this.basePos = bp; } byte[] decompress(PackChunk chunk, DhtReader reader) throws DataFormatException, DhtException { return inflate(deltaSize, chunk, deltaPos + hdrLen, reader); } DeltaBaseCache.Entry getBase(DhtReader ctx) { return ctx.getDeltaBaseCache().get(baseChunk, basePos); } void putBase(DhtReader ctx, int type, byte[] data) { ctx.getDeltaBaseCache().put(baseChunk, basePos, type, data); } } private static void checkCycle(Delta delta, ChunkKey key, int ofs) throws DeltaChainCycleException { for (; delta != null; delta = delta.next) { if (delta.deltaPos == ofs && delta.deltaChunk.equals(key)) throw DeltaChainCycleException.INSTANCE; } } private static class DeltaChainCycleException extends Exception { private static final long serialVersionUID = 1L; static final DeltaChainCycleException INSTANCE = new DeltaChainCycleException(); } }