Add using Memory-mapped index reader
[teamcity/git-plugin.git] / git-server / src / org / eclipse / jgit / internal / storage / file / MemoryMappedPackIndex.java
1 /*
2  * Copyright 2000-2018 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 package org.eclipse.jgit.internal.storage.file;
18
19 import com.intellij.openapi.diagnostic.Logger;
20 import org.eclipse.jgit.errors.MissingObjectException;
21 import org.eclipse.jgit.lib.AbbreviatedObjectId;
22 import org.eclipse.jgit.lib.AnyObjectId;
23 import org.eclipse.jgit.lib.ObjectId;
24 import org.eclipse.jgit.util.NB;
25 import org.jetbrains.annotations.NotNull;
26 import sun.misc.Cleaner;
27 import sun.nio.ch.DirectBuffer;
28 import sun.reflect.generics.reflectiveObjects.NotImplementedException;
29
30 import java.io.File;
31 import java.io.IOException;
32 import java.nio.MappedByteBuffer;
33 import java.nio.channels.FileChannel;
34 import java.nio.file.StandardOpenOption;
35 import java.util.Arrays;
36 import java.util.Iterator;
37 import java.util.NoSuchElementException;
38 import java.util.Set;
39 import java.util.function.Function;
40
41 /**
42  * Memory mapped implementation on {@link PackIndex} reading.
43  * Stolen from Upsource.
44  *
45  * @see <a href="https://upsource.jetbrains.com/circlet/file/bcd361e152cbc90f09fe5d2751140da18d119862/vcs-hosting/vcs-server/git-backend/src/main/java/jetbrains/vcs/server/hosting/git/jgit/MemoryMappedPackIndex.kt">origin code</a>
46  *
47  * @author Mikhail Khorkov
48  * @since 2018.2
49  */
50 public class MemoryMappedPackIndex extends PackIndex.PackIndexFactory {
51
52   private final static Logger LOG = Logger.getInstance(MemoryMappedPackIndex.class.getName());
53
54   private static final long IS_O64 = 1L << 31;
55   private static final int FANOUT = 256;
56   private static final byte[] TOC = new byte[]{-1, "t".getBytes()[0], "O".getBytes()[0], "c".getBytes()[0]};
57
58   public PackIndex open(final File idxFile) throws IOException {
59     try {
60       final FileChannel fc = FileChannel.open(idxFile.toPath(), StandardOpenOption.READ);
61       final MappedByteBuffer buffer = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
62       if (isV2Index(buffer)) {
63         return new PackIndexV2MM(buffer, fc.size());
64       } else {
65         LOG.warn("Index " + idxFile.getPath() + " is not V2");
66       }
67     } catch (Throwable e) {
68       LOG.warn("Reading memory-mapped index " + idxFile.getPath(), e);
69       // use default method
70     }
71
72     return super.open(idxFile);
73   }
74
75   private boolean isV2Index(final MappedByteBuffer buffer) {
76     final byte[] toc = new byte[4];
77     buffer.get(toc, 0, toc.length);
78     if (!Arrays.equals(toc, TOC)) {
79       return false;
80     }
81
82     return decodeInt32(buffer) == 2;
83   }
84
85   /*
86       - A 4-byte magic number \377tOc which is an unreasonable fanout[0] value.
87       - A 4-byte version number (= 2)
88       - A 256-entry fan-out table just like v1.
89       - A table of sorted 20-byte SHA-1 object names. These are packed together without offset values to reduce the cache footprint of the binary search for a specific object name.
90       - A table of 4-byte CRC32 values of the packed object data. This is new in v2 so compressed data can be copied directly from pack to pack during repacking without undetected data corruption.
91       - A table of 4-byte offset values (in network byte order). These are usually 31-bit pack file offsets, but large offsets are encoded as an index into the next table with the msbit set.
92       - A table of 8-byte offset entries (empty for pack files less than 2 GiB). Pack files are organized with heavily used objects toward the front, so most object references should not need to refer to this table.
93       - A copy of the 20-byte SHA-1 checksum at the end of corresponding packfile.
94       - 20-byte SHA-1-checksum of all of the above.
95    */
96
97   private class PackIndexV2MM extends PackIndex {
98     private final MappedByteBuffer myBuffer;
99     private final long mySize;
100     private final int[] fanoutTable = new int[FANOUT];
101     private final int objectCnt;
102
103     private int shaOffset;
104     private int crcOffset;
105     private int ofsOffset;
106     private int o64Offset;
107
108     private volatile boolean isClosed = false;
109
110     PackIndexV2MM(final MappedByteBuffer buffer, final long size) throws IOException {
111       myBuffer = buffer;
112       mySize = size;
113
114       if (size >= Integer.MAX_VALUE) {
115         throw new IOException("index file too large");
116       }
117
118       for (int i = 0; i < FANOUT; i++) {
119         fanoutTable[i] = decodeInt32(myBuffer);
120       }
121
122       objectCnt = fanoutTable[FANOUT - 1];
123       if (objectCnt < 0) {
124         throw new IOException("More than 2G objects in index");
125       }
126
127       shaOffset = 4 + 4 + 256 * 4;
128       crcOffset = shaOffset + objectCnt * 20;
129       ofsOffset = crcOffset + objectCnt * 4;
130       o64Offset = ofsOffset + objectCnt * 4;
131
132       packChecksum = new byte[20];
133       myBuffer.position((int)mySize - 40);
134       myBuffer.get(packChecksum);
135     }
136
137     private void assertNotClosed() {
138       if (isClosed) {
139         throw new Error("PackIndex is closed");
140       }
141     }
142
143     /**
144      * Since mmaped buffer is always {@link DirectBuffer},
145      * use cleaner to help jvm to clean it
146      */
147     @Override
148     public void close() {
149       try {
150         final Cleaner cleaner = ((DirectBuffer)myBuffer).cleaner();
151         if (cleaner != null) {
152           cleaner.clean();
153         }
154       } catch (Throwable e) {
155         LOG.info("Exception while cleaning memory pack index", e);
156       }
157
158       isClosed = true;
159     }
160
161     @Override
162     public boolean hasCRC32Support() {
163       return true;
164     }
165
166     @Override
167     public long getOffset(final long nthPosition) {
168       assertNotClosed();
169
170       myBuffer.position(ofsOffset + (int)nthPosition * 4);
171       long offset = decodeUInt32(myBuffer);
172
173       if ((offset & IS_O64) != 0L) {
174         myBuffer.position(o64Offset + (int)(offset & (~IS_O64)) * 8);
175         return decodeUInt64(myBuffer);
176       }
177
178       return offset;
179     }
180
181     @Override
182     public ObjectId getObjectId(final long nthPosition) {
183       assertNotClosed();
184
185       myBuffer.position(shaOffset + (int)nthPosition * 20);
186       return ObjectId.fromRaw(MemoryMappedPackIndex.read(myBuffer, 20));
187     }
188
189     @Override
190     public void resolve(final Set<ObjectId> matches, final AbbreviatedObjectId id, final int matchLimit) {
191       assertNotClosed();
192
193       int pos = binarySearch(id.getFirstByte(), id::prefixCompare);
194       if (pos >= 0) {
195         // We may have landed in the middle of the matches.  Move
196         // backwards to the start of matches, then walk forwards.
197         //
198         while (0 < pos && (id.prefixCompare(getObjectId(pos - 1)) == 0)) {
199           pos--;
200         }
201         while (pos < objectCnt && (id.prefixCompare(getObjectId(pos)) == 0)) {
202           matches.add(getObjectId(pos));
203           if (matches.size() > matchLimit) {
204             break;
205           }
206           pos++;
207         }
208       }
209     }
210
211     @NotNull
212     @Override
213     public Iterator<MutableEntry> iterator() {
214       assertNotClosed();
215
216       class V2MutableEntry extends MutableEntry {
217
218         private long position = 0;
219
220         @Override
221         public void ensureId() {
222           idBuffer.fromObjectId(getObjectId(position));
223         }
224
225         public long getOffset() {
226           return PackIndexV2MM.this.getOffset(position);
227         }
228
229         @Override
230         public MutableEntry cloneEntry() {
231           final V2MutableEntry entry = new V2MutableEntry();
232           entry.position = this.position;
233           entry.idBuffer.fromObjectId(idBuffer);
234           return entry;
235         }
236       }
237
238       return new PackIndex.EntriesIterator() {
239
240         @Override
241         protected MutableEntry initEntry() {
242           return new V2MutableEntry();
243         }
244
245         /**
246          * Implementation must update {@link #returnedNumber} before returning
247          * element.
248          */
249         @Override
250         public MutableEntry next() {
251           if (returnedNumber < objectCnt) {
252             returnedNumber++;
253             ((V2MutableEntry)entry).position = returnedNumber - 1;
254             return entry;
255           }
256           throw new NoSuchElementException();
257         }
258       };
259     }
260
261     @Override
262     public long getOffset64Count() {
263       // actually, it is quite expensive to calculate this
264       throw new NotImplementedException();
265     }
266
267     @Override
268     public long findCRC32(final AnyObjectId objId) throws MissingObjectException {
269       assertNotClosed();
270
271       final int pos = binarySearch(objId);
272       if (pos < 0) {
273         throw new MissingObjectException(objId.copy(), "unknown");
274       }
275
276       myBuffer.position(crcOffset + pos * 4);
277       return decodeUInt32(myBuffer);
278     }
279
280     @Override
281     public long getObjectCount() {
282       return (long)objectCnt;
283     }
284
285     @Override
286     public long findOffset(final AnyObjectId objId) {
287       assertNotClosed();
288
289       final int pos = binarySearch(objId);
290       if (pos < 0) {
291         return -1;
292       }
293
294       return getOffset((long)pos);
295     }
296
297     // return < 0 if not found
298     private int binarySearch(final AnyObjectId objId) {
299       return binarySearch(objId.getFirstByte(), objId::compareTo);
300     }
301
302     private int binarySearch(int firstByte, Function<ObjectId, Integer> compare) {
303       int low = firstByte == 0 ? 0 : fanoutTable[firstByte - 1];
304       int high = fanoutTable[firstByte];
305
306       while (low < high) {
307         int mid = (low + high) >>> 1;
308         int cmp = compare.apply(getObjectId((long)mid));
309         if (cmp < 0) {
310           high = mid;
311         } else if (cmp == 0) {
312           return mid;
313         } else {
314           low = mid + 1;
315         }
316       }
317
318       return -1;
319     }
320   }
321
322   private static int decodeInt32(final MappedByteBuffer buffer) {
323     return NB.decodeInt32(read(buffer, 4), 0);
324   }
325
326   private static long decodeUInt32(final MappedByteBuffer buffer) {
327     return NB.decodeUInt32(read(buffer, 4), 0);
328   }
329
330   private static long decodeUInt64(final MappedByteBuffer buffer) {
331     return NB.decodeUInt64(read(buffer, 8), 0);
332   }
333
334   private static byte[] read(final MappedByteBuffer buffer, final int size) {
335     final byte[] bytes = new byte[size];
336     buffer.get(bytes);
337     return bytes;
338   }
339 }