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