1
2
3
4
5
6
7
8
9
10
11
12 package org.eclipse.jgit.internal.storage.dfs;
13
14 import static org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackSource.UNREACHABLE_GARBAGE;
15 import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;
16
17 import java.io.IOException;
18 import java.util.ArrayList;
19 import java.util.Collection;
20 import java.util.Collections;
21 import java.util.Comparator;
22 import java.util.HashSet;
23 import java.util.Iterator;
24 import java.util.LinkedList;
25 import java.util.List;
26 import java.util.Set;
27 import java.util.zip.DataFormatException;
28 import java.util.zip.Inflater;
29
30 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
31 import org.eclipse.jgit.errors.MissingObjectException;
32 import org.eclipse.jgit.errors.StoredObjectRepresentationNotAvailableException;
33 import org.eclipse.jgit.internal.JGitText;
34 import org.eclipse.jgit.internal.storage.dfs.DfsObjDatabase.PackList;
35 import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl;
36 import org.eclipse.jgit.internal.storage.file.PackBitmapIndex;
37 import org.eclipse.jgit.internal.storage.file.PackIndex;
38 import org.eclipse.jgit.internal.storage.file.PackReverseIndex;
39 import org.eclipse.jgit.internal.storage.pack.CachedPack;
40 import org.eclipse.jgit.internal.storage.pack.ObjectReuseAsIs;
41 import org.eclipse.jgit.internal.storage.pack.ObjectToPack;
42 import org.eclipse.jgit.internal.storage.pack.PackOutputStream;
43 import org.eclipse.jgit.internal.storage.pack.PackWriter;
44 import org.eclipse.jgit.lib.AbbreviatedObjectId;
45 import org.eclipse.jgit.lib.AnyObjectId;
46 import org.eclipse.jgit.lib.AsyncObjectLoaderQueue;
47 import org.eclipse.jgit.lib.AsyncObjectSizeQueue;
48 import org.eclipse.jgit.lib.BitmapIndex;
49 import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
50 import org.eclipse.jgit.lib.InflaterCache;
51 import org.eclipse.jgit.lib.ObjectId;
52 import org.eclipse.jgit.lib.ObjectLoader;
53 import org.eclipse.jgit.lib.ObjectReader;
54 import org.eclipse.jgit.lib.ProgressMonitor;
55 import org.eclipse.jgit.util.BlockList;
56
57
58
59
60
61
62
63 public class DfsReader extends ObjectReader implements ObjectReuseAsIs {
64 private static final int MAX_RESOLVE_MATCHES = 256;
65
66
67 final byte[] tempId = new byte[OBJECT_ID_LENGTH];
68
69
70 final DfsObjDatabase db;
71
72 final DfsReaderIoStats.Accumulator stats = new DfsReaderIoStats.Accumulator();
73
74 private Inflater inf;
75 private DfsBlock block;
76 private DeltaBaseCache baseCache;
77 private DfsPackFile last;
78 private boolean avoidUnreachable;
79
80
81
82
83
84
85
86 protected DfsReader(DfsObjDatabase db) {
87 this.db = db;
88 this.streamFileThreshold = db.getReaderOptions().getStreamFileThreshold();
89 }
90
91 DfsReaderOptions getOptions() {
92 return db.getReaderOptions();
93 }
94
95 DeltaBaseCache getDeltaBaseCache() {
96 if (baseCache == null)
97 baseCache = new DeltaBaseCache(this);
98 return baseCache;
99 }
100
101
102 @Override
103 public ObjectReader newReader() {
104 return db.newReader();
105 }
106
107
108 @Override
109 public void setAvoidUnreachableObjects(boolean avoid) {
110 avoidUnreachable = avoid;
111 }
112
113
114 @Override
115 public BitmapIndex getBitmapIndex() throws IOException {
116 for (DfsPackFile pack : db.getPacks()) {
117 PackBitmapIndex bitmapIndex = pack.getBitmapIndex(this);
118 if (bitmapIndex != null)
119 return new BitmapIndexImpl(bitmapIndex);
120 }
121 return null;
122 }
123
124
125 @Override
126 public Collection<CachedPack> getCachedPacksAndUpdate(
127 BitmapBuilder needBitmap) throws IOException {
128 for (DfsPackFile pack : db.getPacks()) {
129 PackBitmapIndex bitmapIndex = pack.getBitmapIndex(this);
130 if (needBitmap.removeAllOrNone(bitmapIndex))
131 return Collections.<CachedPack> singletonList(
132 new DfsCachedPack(pack));
133 }
134 return Collections.emptyList();
135 }
136
137
138 @Override
139 public Collection<ObjectId> resolve(AbbreviatedObjectId id)
140 throws IOException {
141 if (id.isComplete())
142 return Collections.singleton(id.toObjectId());
143 HashSet<ObjectId> matches = new HashSet<>(4);
144 PackList packList = db.getPackList();
145 resolveImpl(packList, id, matches);
146 if (matches.size() < MAX_RESOLVE_MATCHES && packList.dirty()) {
147 stats.scanPacks++;
148 resolveImpl(db.scanPacks(packList), id, matches);
149 }
150 return matches;
151 }
152
153 private void resolveImpl(PackList packList, AbbreviatedObjectId id,
154 HashSet<ObjectId> matches) throws IOException {
155 for (DfsPackFile pack : packList.packs) {
156 if (skipGarbagePack(pack)) {
157 continue;
158 }
159 pack.resolve(this, matches, id, MAX_RESOLVE_MATCHES);
160 if (matches.size() >= MAX_RESOLVE_MATCHES) {
161 break;
162 }
163 }
164 }
165
166
167 @Override
168 public boolean has(AnyObjectId objectId) throws IOException {
169 if (last != null
170 && !skipGarbagePack(last)
171 && last.hasObject(this, objectId))
172 return true;
173 PackList packList = db.getPackList();
174 if (hasImpl(packList, objectId)) {
175 return true;
176 } else if (packList.dirty()) {
177 stats.scanPacks++;
178 return hasImpl(db.scanPacks(packList), objectId);
179 }
180 return false;
181 }
182
183 private boolean hasImpl(PackList packList, AnyObjectId objectId)
184 throws IOException {
185 for (DfsPackFile pack : packList.packs) {
186 if (pack == last || skipGarbagePack(pack))
187 continue;
188 if (pack.hasObject(this, objectId)) {
189 last = pack;
190 return true;
191 }
192 }
193 return false;
194 }
195
196
197 @Override
198 public ObjectLoader open(AnyObjectId objectId, int typeHint)
199 throws MissingObjectException, IncorrectObjectTypeException,
200 IOException {
201 ObjectLoader ldr;
202 if (last != null && !skipGarbagePack(last)) {
203 ldr = last.get(this, objectId);
204 if (ldr != null) {
205 return checkType(ldr, objectId, typeHint);
206 }
207 }
208
209 PackList packList = db.getPackList();
210 ldr = openImpl(packList, objectId);
211 if (ldr != null) {
212 return checkType(ldr, objectId, typeHint);
213 }
214 if (packList.dirty()) {
215 stats.scanPacks++;
216 ldr = openImpl(db.scanPacks(packList), objectId);
217 if (ldr != null) {
218 return checkType(ldr, objectId, typeHint);
219 }
220 }
221
222 if (typeHint == OBJ_ANY)
223 throw new MissingObjectException(objectId.copy(),
224 JGitText.get().unknownObjectType2);
225 throw new MissingObjectException(objectId.copy(), typeHint);
226 }
227
228 private static ObjectLoader../../../../org/eclipse/jgit/lib/ObjectLoader.html#ObjectLoader">ObjectLoader checkType(ObjectLoader ldr, AnyObjectId id,
229 int typeHint) throws IncorrectObjectTypeException {
230 if (typeHint != OBJ_ANY && ldr.getType() != typeHint) {
231 throw new IncorrectObjectTypeException(id.copy(), typeHint);
232 }
233 return ldr;
234 }
235
236 private ObjectLoader openImpl(PackList packList, AnyObjectId objectId)
237 throws IOException {
238 for (DfsPackFile pack : packList.packs) {
239 if (pack == last || skipGarbagePack(pack)) {
240 continue;
241 }
242 ObjectLoader ldr = pack.get(this, objectId);
243 if (ldr != null) {
244 last = pack;
245 return ldr;
246 }
247 }
248 return null;
249 }
250
251
252 @Override
253 public Set<ObjectId> getShallowCommits() {
254 return Collections.emptySet();
255 }
256
257 private static final Comparator<FoundObject<?>> FOUND_OBJECT_SORT = (
258 FoundObject<?> a, FoundObject<?> b) -> {
259 int cmp = a.packIndex - b.packIndex;
260 if (cmp == 0)
261 cmp = Long.signum(a.offset - b.offset);
262 return cmp;
263 };
264
265 private static class FoundObject<T extends ObjectId> {
266 final T id;
267 final DfsPackFile pack;
268 final long offset;
269 final int packIndex;
270
271 FoundObject(T objectId, int packIdx, DfsPackFile pack, long offset) {
272 this.id = objectId;
273 this.pack = pack;
274 this.offset = offset;
275 this.packIndex = packIdx;
276 }
277
278 FoundObject(T objectId) {
279 this.id = objectId;
280 this.pack = null;
281 this.offset = 0;
282 this.packIndex = 0;
283 }
284 }
285
286 private <T extends ObjectId> Iterable<FoundObject<T>> findAll(
287 Iterable<T> objectIds) throws IOException {
288 Collection<T> pending = new LinkedList<>();
289 for (T id : objectIds) {
290 pending.add(id);
291 }
292
293 PackList packList = db.getPackList();
294 List<FoundObject<T>> r = new ArrayList<>();
295 findAllImpl(packList, pending, r);
296 if (!pending.isEmpty() && packList.dirty()) {
297 stats.scanPacks++;
298 findAllImpl(db.scanPacks(packList), pending, r);
299 }
300 for (T t : pending) {
301 r.add(new FoundObject<>(t));
302 }
303 Collections.sort(r, FOUND_OBJECT_SORT);
304 return r;
305 }
306
307 private <T extends ObjectId> void findAllImpl(PackList packList,
308 Collection<T> pending, List<FoundObject<T>> r) {
309 DfsPackFile[] packs = packList.packs;
310 if (packs.length == 0) {
311 return;
312 }
313 int lastIdx = 0;
314 DfsPackFile lastPack = packs[lastIdx];
315
316 OBJECT_SCAN: for (Iterator<T> it = pending.iterator(); it.hasNext();) {
317 T t = it.next();
318 if (!skipGarbagePack(lastPack)) {
319 try {
320 long p = lastPack.findOffset(this, t);
321 if (0 < p) {
322 r.add(new FoundObject<>(t, lastIdx, lastPack, p));
323 it.remove();
324 continue;
325 }
326 } catch (IOException e) {
327
328 }
329 }
330
331 for (int i = 0; i < packs.length; i++) {
332 if (i == lastIdx)
333 continue;
334 DfsPackFile pack = packs[i];
335 if (skipGarbagePack(pack))
336 continue;
337 try {
338 long p = pack.findOffset(this, t);
339 if (0 < p) {
340 r.add(new FoundObject<>(t, i, pack, p));
341 it.remove();
342 lastIdx = i;
343 lastPack = pack;
344 continue OBJECT_SCAN;
345 }
346 } catch (IOException e) {
347
348 }
349 }
350 }
351
352 last = lastPack;
353 }
354
355 private boolean skipGarbagePack(DfsPackFile pack) {
356 return avoidUnreachable && pack.isGarbage();
357 }
358
359
360 @Override
361 public <T extends ObjectId> AsyncObjectLoaderQueue<T> open(
362 Iterable<T> objectIds, final boolean reportMissing) {
363 Iterable<FoundObject<T>> order;
364 IOException error = null;
365 try {
366 order = findAll(objectIds);
367 } catch (IOException e) {
368 order = Collections.emptyList();
369 error = e;
370 }
371
372 final Iterator<FoundObject<T>> idItr = order.iterator();
373 final IOException findAllError = error;
374 return new AsyncObjectLoaderQueue<T>() {
375 private FoundObject<T> cur;
376
377 @Override
378 public boolean next() throws MissingObjectException, IOException {
379 if (idItr.hasNext()) {
380 cur = idItr.next();
381 return true;
382 } else if (findAllError != null) {
383 throw findAllError;
384 } else {
385 return false;
386 }
387 }
388
389 @Override
390 public T getCurrent() {
391 return cur.id;
392 }
393
394 @Override
395 public ObjectId getObjectId() {
396 return cur.id;
397 }
398
399 @Override
400 public ObjectLoader open() throws IOException {
401 if (cur.pack == null)
402 throw new MissingObjectException(cur.id,
403 JGitText.get().unknownObjectType2);
404 return cur.pack.load(DfsReader.this, cur.offset);
405 }
406
407 @Override
408 public boolean cancel(boolean mayInterruptIfRunning) {
409 return true;
410 }
411
412 @Override
413 public void release() {
414
415 }
416 };
417 }
418
419
420 @Override
421 public <T extends ObjectId> AsyncObjectSizeQueue<T> getObjectSize(
422 Iterable<T> objectIds, final boolean reportMissing) {
423 Iterable<FoundObject<T>> order;
424 IOException error = null;
425 try {
426 order = findAll(objectIds);
427 } catch (IOException e) {
428 order = Collections.emptyList();
429 error = e;
430 }
431
432 final Iterator<FoundObject<T>> idItr = order.iterator();
433 final IOException findAllError = error;
434 return new AsyncObjectSizeQueue<T>() {
435 private FoundObject<T> cur;
436 private long sz;
437
438 @Override
439 public boolean next() throws MissingObjectException, IOException {
440 if (idItr.hasNext()) {
441 cur = idItr.next();
442 if (cur.pack == null)
443 throw new MissingObjectException(cur.id,
444 JGitText.get().unknownObjectType2);
445 sz = cur.pack.getObjectSize(DfsReader.this, cur.offset);
446 return true;
447 } else if (findAllError != null) {
448 throw findAllError;
449 } else {
450 return false;
451 }
452 }
453
454 @Override
455 public T getCurrent() {
456 return cur.id;
457 }
458
459 @Override
460 public ObjectId getObjectId() {
461 return cur.id;
462 }
463
464 @Override
465 public long getSize() {
466 return sz;
467 }
468
469 @Override
470 public boolean cancel(boolean mayInterruptIfRunning) {
471 return true;
472 }
473
474 @Override
475 public void release() {
476
477 }
478 };
479 }
480
481
482 @Override
483 public long getObjectSize(AnyObjectId objectId, int typeHint)
484 throws MissingObjectException, IncorrectObjectTypeException,
485 IOException {
486 if (last != null && !skipGarbagePack(last)) {
487 long sz = last.getObjectSize(this, objectId);
488 if (0 <= sz) {
489 return sz;
490 }
491 }
492
493 PackList packList = db.getPackList();
494 long sz = getObjectSizeImpl(packList, objectId);
495 if (0 <= sz) {
496 return sz;
497 }
498 if (packList.dirty()) {
499 sz = getObjectSizeImpl(packList, objectId);
500 if (0 <= sz) {
501 return sz;
502 }
503 }
504
505 if (typeHint == OBJ_ANY) {
506 throw new MissingObjectException(objectId.copy(),
507 JGitText.get().unknownObjectType2);
508 }
509 throw new MissingObjectException(objectId.copy(), typeHint);
510 }
511
512 private long getObjectSizeImpl(PackList packList, AnyObjectId objectId)
513 throws IOException {
514 for (DfsPackFile pack : packList.packs) {
515 if (pack == last || skipGarbagePack(pack)) {
516 continue;
517 }
518 long sz = pack.getObjectSize(this, objectId);
519 if (0 <= sz) {
520 last = pack;
521 return sz;
522 }
523 }
524 return -1;
525 }
526
527
528 @Override
529 public DfsObjectToPack newObjectToPack(AnyObjectId objectId, int type) {
530 return new DfsObjectToPack(objectId, type);
531 }
532
533 private static final Comparator<DfsObjectToPack> OFFSET_SORT = (
534 DfsObjectToPack a,
535 DfsObjectToPack b) -> Long.signum(a.getOffset() - b.getOffset());
536
537 @Override
538 public void selectObjectRepresentation(PackWriter packer,
539 ProgressMonitor monitor, Iterable<ObjectToPack> objects)
540 throws IOException, MissingObjectException {
541
542
543 List<DfsPackFile> packs = sortPacksForSelectRepresentation();
544 trySelectRepresentation(packer, monitor, objects, packs, false);
545
546 List<DfsPackFile> garbage = garbagePacksForSelectRepresentation();
547 if (!garbage.isEmpty() && checkGarbagePacks(objects)) {
548 trySelectRepresentation(packer, monitor, objects, garbage, true);
549 }
550 }
551
552 private void trySelectRepresentation(PackWriter packer,
553 ProgressMonitor monitor, Iterable<ObjectToPack> objects,
554 List<DfsPackFile> packs, boolean skipFound) throws IOException {
555 for (DfsPackFile pack : packs) {
556 List<DfsObjectToPack> tmp = findAllFromPack(pack, objects, skipFound);
557 if (tmp.isEmpty())
558 continue;
559 Collections.sort(tmp, OFFSET_SORT);
560 PackReverseIndex rev = pack.getReverseIdx(this);
561 DfsObjectRepresentation rep = new DfsObjectRepresentation(pack);
562 for (DfsObjectToPack otp : tmp) {
563 pack.representation(rep, otp.getOffset(), this, rev);
564 otp.setOffset(0);
565 packer.select(otp, rep);
566 if (!otp.isFound()) {
567 otp.setFound();
568 monitor.update(1);
569 }
570 }
571 }
572 }
573
574 private static final Comparator<DfsPackFile> PACK_SORT_FOR_REUSE =
575 Comparator.comparing(
576 DfsPackFile::getPackDescription, DfsPackDescription.reuseComparator());
577
578 private List<DfsPackFile> sortPacksForSelectRepresentation()
579 throws IOException {
580 DfsPackFile[] packs = db.getPacks();
581 List<DfsPackFile> sorted = new ArrayList<>(packs.length);
582 for (DfsPackFile p : packs) {
583 if (p.getPackDescription().getPackSource() != UNREACHABLE_GARBAGE) {
584 sorted.add(p);
585 }
586 }
587 Collections.sort(sorted, PACK_SORT_FOR_REUSE);
588 return sorted;
589 }
590
591 private List<DfsPackFile> garbagePacksForSelectRepresentation()
592 throws IOException {
593 DfsPackFile[] packs = db.getPacks();
594 List<DfsPackFile> garbage = new ArrayList<>(packs.length);
595 for (DfsPackFile p : packs) {
596 if (p.getPackDescription().getPackSource() == UNREACHABLE_GARBAGE) {
597 garbage.add(p);
598 }
599 }
600 return garbage;
601 }
602
603 private static boolean checkGarbagePacks(Iterable<ObjectToPack> objects) {
604 for (ObjectToPack otp : objects) {
605 if (!((DfsObjectToPack) otp).isFound()) {
606 return true;
607 }
608 }
609 return false;
610 }
611
612 private List<DfsObjectToPack> findAllFromPack(DfsPackFile pack,
613 Iterable<ObjectToPack> objects, boolean skipFound)
614 throws IOException {
615 List<DfsObjectToPack> tmp = new BlockList<>();
616 PackIndex idx = pack.getPackIndex(this);
617 for (ObjectToPack obj : objects) {
618 DfsObjectToPack otp = (DfsObjectToPack) obj;
619 if (skipFound && otp.isFound()) {
620 continue;
621 }
622 long p = idx.findOffset(otp);
623 if (0 < p && !pack.isCorrupt(p)) {
624 otp.setOffset(p);
625 tmp.add(otp);
626 }
627 }
628 return tmp;
629 }
630
631
632 @Override
633 public void copyObjectAsIs(PackOutputStream out, ObjectToPack otp,
634 boolean validate) throws IOException,
635 StoredObjectRepresentationNotAvailableException {
636 DfsObjectToPack src = (DfsObjectToPack) otp;
637 src.pack.copyAsIs(out, src, validate, this);
638 }
639
640
641 @Override
642 public void writeObjects(PackOutputStream out, List<ObjectToPack> list)
643 throws IOException {
644 for (ObjectToPack otp : list)
645 out.writeObject(otp);
646 }
647
648
649 @Override
650 public void copyPackAsIs(PackOutputStream out, CachedPack pack)
651 throws IOException {
652 ((DfsCachedPack) pack).copyAsIs(out, this);
653 }
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677 int copy(BlockBasedFile file, long position, byte[] dstbuf, int dstoff,
678 int cnt) throws IOException {
679 if (cnt == 0)
680 return 0;
681
682 long length = file.length;
683 if (0 <= length && length <= position)
684 return 0;
685
686 int need = cnt;
687 do {
688 pin(file, position);
689 int r = block.copy(position, dstbuf, dstoff, need);
690 position += r;
691 dstoff += r;
692 need -= r;
693 if (length < 0)
694 length = file.length;
695 } while (0 < need && position < length);
696 return cnt - need;
697 }
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720 int inflate(DfsPackFile pack, long position, byte[] dstbuf,
721 boolean headerOnly) throws IOException, DataFormatException {
722 long start = System.nanoTime();
723 prepareInflater();
724 pin(pack, position);
725 position += block.setInput(position, inf);
726 for (int dstoff = 0;;) {
727 int n = inf.inflate(dstbuf, dstoff, dstbuf.length - dstoff);
728 dstoff += n;
729 if (inf.finished() || (headerOnly && dstoff == dstbuf.length)) {
730 stats.inflatedBytes += dstoff;
731 stats.inflationMicros += BlockBasedFile.elapsedMicros(start);
732 return dstoff;
733 } else if (inf.needsInput()) {
734 pin(pack, position);
735 position += block.setInput(position, inf);
736 } else if (n == 0)
737 throw new DataFormatException();
738 }
739 }
740
741 DfsBlock quickCopy(DfsPackFile p, long pos, long cnt)
742 throws IOException {
743 pin(p, pos);
744 if (block.contains(p.key, pos + (cnt - 1)))
745 return block;
746 return null;
747 }
748
749 Inflater inflater() {
750 prepareInflater();
751 return inf;
752 }
753
754 private void prepareInflater() {
755 if (inf == null)
756 inf = InflaterCache.get();
757 else
758 inf.reset();
759 }
760
761 void pin(BlockBasedFile file, long position) throws IOException {
762 if (block == null || !block.contains(file.key, position)) {
763
764
765
766
767 block = null;
768 block = file.getOrLoadBlock(position, this);
769 }
770 }
771
772 void unpin() {
773 block = null;
774 }
775
776
777
778
779
780
781 public DfsReaderIoStats getIoStats() {
782 return new DfsReaderIoStats(stats);
783 }
784
785
786
787
788
789
790 @Override
791 public void close() {
792 last = null;
793 block = null;
794 baseCache = null;
795 try {
796 InflaterCache.release(inf);
797 } finally {
798 inf = null;
799 }
800 }
801 }