1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.reftable;
12
13 import static java.lang.Math.log;
14 import static java.nio.charset.StandardCharsets.UTF_8;
15 import static org.eclipse.jgit.internal.storage.reftable.BlockWriter.padBetweenBlocks;
16 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_FOOTER_LEN;
17 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_HEADER_LEN;
18 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_HEADER_MAGIC;
19 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.INDEX_BLOCK_TYPE;
20 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_BLOCK_TYPE;
21 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.MAX_BLOCK_SIZE;
22 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.MAX_RESTARTS;
23 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.OBJ_BLOCK_TYPE;
24 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.REF_BLOCK_TYPE;
25 import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VERSION_1;
26 import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;
27
28 import java.io.IOException;
29 import java.io.OutputStream;
30 import java.text.MessageFormat;
31 import java.util.ArrayList;
32 import java.util.Collection;
33 import java.util.Collections;
34 import java.util.HashSet;
35 import java.util.Iterator;
36 import java.util.List;
37 import java.util.Set;
38 import java.util.zip.CRC32;
39
40 import org.eclipse.jgit.annotations.Nullable;
41 import org.eclipse.jgit.internal.JGitText;
42 import org.eclipse.jgit.internal.storage.reftable.BlockWriter.DeleteLogEntry;
43 import org.eclipse.jgit.internal.storage.reftable.BlockWriter.Entry;
44 import org.eclipse.jgit.internal.storage.reftable.BlockWriter.IndexEntry;
45 import org.eclipse.jgit.internal.storage.reftable.BlockWriter.LogEntry;
46 import org.eclipse.jgit.internal.storage.reftable.BlockWriter.ObjEntry;
47 import org.eclipse.jgit.internal.storage.reftable.BlockWriter.RefEntry;
48 import org.eclipse.jgit.lib.AbbreviatedObjectId;
49 import org.eclipse.jgit.lib.AnyObjectId;
50 import org.eclipse.jgit.lib.ObjectId;
51 import org.eclipse.jgit.lib.ObjectIdOwnerMap;
52 import org.eclipse.jgit.lib.ObjectIdSubclassMap;
53 import org.eclipse.jgit.lib.PersonIdent;
54 import org.eclipse.jgit.lib.Ref;
55 import org.eclipse.jgit.util.LongList;
56 import org.eclipse.jgit.util.NB;
57
58
59
60
61
62
63
64
65
66 public class ReftableWriter {
67 private ReftableConfig config;
68 private int refBlockSize;
69 private int logBlockSize;
70 private int restartInterval;
71 private int maxIndexLevels;
72 private boolean alignBlocks;
73 private boolean indexObjects;
74
75 private long minUpdateIndex;
76 private long maxUpdateIndex;
77
78 private OutputStream outputStream;
79 private ReftableOutputStream out;
80 private ObjectIdSubclassMap<RefList> obj2ref;
81
82 private BlockWriter.Entry lastRef;
83 private BlockWriter.Entry lastLog;
84 private BlockWriter cur;
85 private Section refs;
86 private Section objs;
87 private Section logs;
88 private int objIdLen;
89 private Stats stats;
90
91
92
93
94
95
96
97 public ReftableWriter(OutputStream os) {
98 this(new ReftableConfig(), os);
99 lastRef = null;
100 lastLog = null;
101 }
102
103
104
105
106
107
108
109
110
111 public ReftableWriter(ReftableConfig cfg, OutputStream os) {
112 config = cfg;
113 outputStream = os;
114 }
115
116
117
118
119
120
121
122
123 public ReftableWriter setConfig(ReftableConfig cfg) {
124 this.config = cfg != null ? cfg : new ReftableConfig();
125 return this;
126 }
127
128
129
130
131
132
133
134
135
136
137
138 public ReftableWriter setMinUpdateIndex(long min) {
139 minUpdateIndex = min;
140 return this;
141 }
142
143
144
145
146
147
148
149
150
151
152
153
154 public ReftableWriter setMaxUpdateIndex(long max) {
155 maxUpdateIndex = max;
156 return this;
157 }
158
159
160
161
162
163
164
165 public ReftableWriter begin() {
166 if (out != null) {
167 throw new IllegalStateException("begin() called twice.");
168 }
169
170 refBlockSize = config.getRefBlockSize();
171 logBlockSize = config.getLogBlockSize();
172 restartInterval = config.getRestartInterval();
173 maxIndexLevels = config.getMaxIndexLevels();
174 alignBlocks = config.isAlignBlocks();
175 indexObjects = config.isIndexObjects();
176
177 if (refBlockSize <= 0) {
178 refBlockSize = 4 << 10;
179 } else if (refBlockSize > MAX_BLOCK_SIZE) {
180 throw new IllegalArgumentException();
181 }
182 if (logBlockSize <= 0) {
183 logBlockSize = 2 * refBlockSize;
184 }
185 if (restartInterval <= 0) {
186 restartInterval = refBlockSize < (60 << 10) ? 16 : 64;
187 }
188
189 out = new ReftableOutputStream(outputStream, refBlockSize, alignBlocks);
190 refs = new Section(REF_BLOCK_TYPE);
191 if (indexObjects) {
192 obj2ref = new ObjectIdSubclassMap<>();
193 }
194 writeFileHeader();
195 return this;
196 }
197
198
199
200
201
202
203
204
205
206
207
208 public ReftableWriter sortAndWriteRefs(Collection<Ref> refsToPack)
209 throws IOException {
210 Iterator<RefEntry> itr = refsToPack.stream()
211 .map(r -> new RefEntry(r, maxUpdateIndex - minUpdateIndex))
212 .sorted(Entry::compare)
213 .iterator();
214 RefEntry last = null;
215 while (itr.hasNext()) {
216 RefEntry entry = itr.next();
217 if (last != null && Entry.compare(last, entry) == 0) {
218 throwIllegalEntry(last, entry);
219 }
220
221 long blockPos = refs.write(entry);
222 indexRef(entry.ref, blockPos);
223 last = entry;
224 }
225 return this;
226 }
227
228
229
230
231
232
233
234
235
236
237
238 public void writeRef(Ref ref) throws IOException {
239 writeRef(ref, maxUpdateIndex);
240 }
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255 public void writeRef(Ref ref, long updateIndex) throws IOException {
256 if (updateIndex < minUpdateIndex) {
257 throw new IllegalArgumentException();
258 }
259 long d = updateIndex - minUpdateIndex;
260 RefEntry entry = new RefEntry(ref, d);
261 if (lastRef != null && Entry.compare(lastRef, entry) >= 0) {
262 throwIllegalEntry(lastRef, entry);
263 }
264 lastRef = entry;
265
266 long blockPos = refs.write(entry);
267 indexRef(ref, blockPos);
268 }
269
270 private void throwIllegalEntry(Entry last, Entry now) {
271 throw new IllegalArgumentException(MessageFormat.format(
272 JGitText.get().reftableRecordsMustIncrease,
273 new String(last.key, UTF_8), new String(now.key, UTF_8)));
274 }
275
276 private void indexRef(Ref ref, long blockPos) {
277 if (indexObjects && !ref.isSymbolic()) {
278 indexId(ref.getObjectId(), blockPos);
279 indexId(ref.getPeeledObjectId(), blockPos);
280 }
281 }
282
283 private void indexId(ObjectId id, long blockPos) {
284 if (id != null) {
285 RefList l = obj2ref.get(id);
286 if (l == null) {
287 l = new RefList(id);
288 obj2ref.add(l);
289 }
290 l.addBlock(blockPos);
291 }
292 }
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320 public void writeLog(String ref, long updateIndex, PersonIdent who,
321 ObjectId oldId, ObjectId newId, @Nullable String message)
322 throws IOException {
323 String msg = message != null ? message : "";
324 beginLog();
325 LogEntry entry = new LogEntry(ref, updateIndex, who, oldId, newId, msg);
326 if (lastLog != null && Entry.compare(lastLog, entry) >= 0) {
327 throwIllegalEntry(lastLog, entry);
328 }
329 lastLog = entry;
330 logs.write(entry);
331 }
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352 public void deleteLog(String ref, long updateIndex) throws IOException {
353 beginLog();
354 logs.write(new DeleteLogEntry(ref, updateIndex));
355 }
356
357 private void beginLog() throws IOException {
358 if (logs == null) {
359 finishRefAndObjSections();
360 out.flushFileHeader();
361 out.setBlockSize(logBlockSize);
362 logs = new Section(LOG_BLOCK_TYPE);
363 }
364 }
365
366
367
368
369
370
371
372
373
374
375
376 public long estimateTotalBytes() {
377 long bytes = out.size();
378 if (bytes == 0) {
379 bytes += FILE_HEADER_LEN;
380 }
381 if (cur != null) {
382 long curBlockPos = out.size();
383 int sz = cur.currentSize();
384 bytes += sz;
385
386 IndexBuilder idx = null;
387 if (cur.blockType() == REF_BLOCK_TYPE) {
388 idx = refs.idx;
389 } else if (cur.blockType() == LOG_BLOCK_TYPE) {
390 idx = logs.idx;
391 }
392 if (idx != null && shouldHaveIndex(idx)) {
393 if (idx == refs.idx) {
394 bytes += out.estimatePadBetweenBlocks(sz);
395 }
396 bytes += idx.estimateBytes(curBlockPos);
397 }
398 }
399 bytes += FILE_FOOTER_LEN;
400 return bytes;
401 }
402
403
404
405
406
407
408
409
410 public ReftableWriter finish() throws IOException {
411 finishRefAndObjSections();
412 finishLogSection();
413 writeFileFooter();
414 out.finishFile();
415
416 stats = new Stats(this, out);
417 out = null;
418 obj2ref = null;
419 cur = null;
420 refs = null;
421 objs = null;
422 logs = null;
423 return this;
424 }
425
426 private void finishRefAndObjSections() throws IOException {
427 if (cur != null && cur.blockType() == REF_BLOCK_TYPE) {
428 refs.finishSectionMaybeWriteIndex();
429 if (indexObjects && !obj2ref.isEmpty() && refs.idx.bytes > 0) {
430 writeObjBlocks();
431 }
432 obj2ref = null;
433 }
434 }
435
436 private void writeObjBlocks() throws IOException {
437 List<RefList> sorted = sortById(obj2ref);
438 obj2ref = null;
439 objIdLen = shortestUniqueAbbreviation(sorted);
440
441 out.padBetweenBlocksToNextBlock();
442 objs = new Section(OBJ_BLOCK_TYPE);
443 objs.entryCnt = sorted.size();
444 for (RefList l : sorted) {
445 objs.write(new ObjEntry(objIdLen, l, l.blockPos));
446 }
447 objs.finishSectionMaybeWriteIndex();
448 }
449
450 private void finishLogSection() throws IOException {
451 if (cur != null && cur.blockType() == LOG_BLOCK_TYPE) {
452 logs.finishSectionMaybeWriteIndex();
453 }
454 }
455
456 private boolean shouldHaveIndex(IndexBuilder idx) {
457 int threshold;
458 if (idx == refs.idx && alignBlocks) {
459 threshold = 4;
460 } else {
461 threshold = 1;
462 }
463 return idx.entries.size() + (cur != null ? 1 : 0) > threshold;
464 }
465
466 private void writeFileHeader() {
467 byte[] hdr = new byte[FILE_HEADER_LEN];
468 encodeHeader(hdr);
469 out.write(hdr, 0, FILE_HEADER_LEN);
470 }
471
472 private void encodeHeader(byte[] hdr) {
473 System.arraycopy(FILE_HEADER_MAGIC, 0, hdr, 0, 4);
474 int bs = alignBlocks ? refBlockSize : 0;
475 NB.encodeInt32(hdr, 4, (VERSION_1 << 24) | bs);
476 NB.encodeInt64(hdr, 8, minUpdateIndex);
477 NB.encodeInt64(hdr, 16, maxUpdateIndex);
478 }
479
480 private void writeFileFooter() {
481 int ftrLen = FILE_FOOTER_LEN;
482 byte[] ftr = new byte[ftrLen];
483 encodeHeader(ftr);
484
485 NB.encodeInt64(ftr, 24, indexPosition(refs));
486 NB.encodeInt64(ftr, 32, (firstBlockPosition(objs) << 5) | objIdLen);
487 NB.encodeInt64(ftr, 40, indexPosition(objs));
488 NB.encodeInt64(ftr, 48, firstBlockPosition(logs));
489 NB.encodeInt64(ftr, 56, indexPosition(logs));
490
491 CRC32 crc = new CRC32();
492 crc.update(ftr, 0, ftrLen - 4);
493 NB.encodeInt32(ftr, ftrLen - 4, (int) crc.getValue());
494
495 out.write(ftr, 0, ftrLen);
496 }
497
498 private static long firstBlockPosition(@Nullable Section s) {
499 return s != null ? s.firstBlockPosition : 0;
500 }
501
502 private static long indexPosition(@Nullable Section s) {
503 return s != null && s.idx != null ? s.idx.rootPosition : 0;
504 }
505
506
507
508
509
510
511 public Stats getStats() {
512 return stats;
513 }
514
515
516 public static class Stats {
517 private final int refBlockSize;
518 private final int logBlockSize;
519 private final int restartInterval;
520
521 private final long minUpdateIndex;
522 private final long maxUpdateIndex;
523
524 private final long refCnt;
525 private final long objCnt;
526 private final int objIdLen;
527 private final long logCnt;
528 private final long refBytes;
529 private final long objBytes;
530 private final long logBytes;
531 private final long paddingUsed;
532 private final long totalBytes;
533
534 private final int refIndexSize;
535 private final int refIndexLevels;
536 private final int objIndexSize;
537 private final int objIndexLevels;
538
539 Stats(ReftableWriter w, ReftableOutputStream o) {
540 refBlockSize = w.refBlockSize;
541 logBlockSize = w.logBlockSize;
542 restartInterval = w.restartInterval;
543
544 minUpdateIndex = w.minUpdateIndex;
545 maxUpdateIndex = w.maxUpdateIndex;
546 paddingUsed = o.paddingUsed();
547 totalBytes = o.size();
548
549 refCnt = w.refs.entryCnt;
550 refBytes = w.refs.bytes;
551
552 objCnt = w.objs != null ? w.objs.entryCnt : 0;
553 objBytes = w.objs != null ? w.objs.bytes : 0;
554 objIdLen = w.objIdLen;
555
556 logCnt = w.logs != null ? w.logs.entryCnt : 0;
557 logBytes = w.logs != null ? w.logs.bytes : 0;
558
559 IndexBuilder refIdx = w.refs.idx;
560 refIndexSize = refIdx.bytes;
561 refIndexLevels = refIdx.levels;
562
563 IndexBuilder objIdx = w.objs != null ? w.objs.idx : null;
564 objIndexSize = objIdx != null ? objIdx.bytes : 0;
565 objIndexLevels = objIdx != null ? objIdx.levels : 0;
566 }
567
568
569 public int refBlockSize() {
570 return refBlockSize;
571 }
572
573
574 public int logBlockSize() {
575 return logBlockSize;
576 }
577
578
579 public int restartInterval() {
580 return restartInterval;
581 }
582
583
584 public long minUpdateIndex() {
585 return minUpdateIndex;
586 }
587
588
589 public long maxUpdateIndex() {
590 return maxUpdateIndex;
591 }
592
593
594 public long refCount() {
595 return refCnt;
596 }
597
598
599 public long objCount() {
600 return objCnt;
601 }
602
603
604 public long logCount() {
605 return logCnt;
606 }
607
608
609 public long refBytes() {
610 return refBytes;
611 }
612
613
614 public long objBytes() {
615 return objBytes;
616 }
617
618
619 public long logBytes() {
620 return logBytes;
621 }
622
623
624 public long totalBytes() {
625 return totalBytes;
626 }
627
628
629 public long paddingBytes() {
630 return paddingUsed;
631 }
632
633
634 public int refIndexSize() {
635 return refIndexSize;
636 }
637
638
639 public int refIndexLevels() {
640 return refIndexLevels;
641 }
642
643
644 public int objIndexSize() {
645 return objIndexSize;
646 }
647
648
649 public int objIndexLevels() {
650 return objIndexLevels;
651 }
652
653
654
655
656
657
658 public int objIdLength() {
659 return objIdLen;
660 }
661 }
662
663 private static List<RefList> sortById(ObjectIdSubclassMap<RefList> m) {
664 List<RefList> s = new ArrayList<>(m.size());
665 for (RefList l : m) {
666 s.add(l);
667 }
668 Collections.sort(s);
669 return s;
670 }
671
672 private static int shortestUniqueAbbreviation(List<RefList> in) {
673
674 int bytes = Math.max(2, (int) (log(in.size()) / log(8)));
675 Set<AbbreviatedObjectId> tmp = new HashSet<>((int) (in.size() * 0.75f));
676 retry: for (;;) {
677 int hexLen = bytes * 2;
678 for (ObjectId id : in) {
679 AbbreviatedObjectId a = id.abbreviate(hexLen);
680 if (!tmp.add(a)) {
681 if (++bytes >= OBJECT_ID_LENGTH) {
682 return OBJECT_ID_LENGTH;
683 }
684 tmp.clear();
685 continue retry;
686 }
687 }
688 return bytes;
689 }
690 }
691
692 private static class RefList extends ObjectIdOwnerMap.Entry {
693 final LongListList.html#LongList">LongList blockPos = new LongList(2);
694
695 RefList(AnyObjectId id) {
696 super(id);
697 }
698
699 void addBlock(long pos) {
700 if (!blockPos.contains(pos)) {
701 blockPos.add(pos);
702 }
703 }
704 }
705
706 private class Section {
707 final IndexBuilder idx;
708 final long firstBlockPosition;
709
710 long entryCnt;
711 long bytes;
712
713 Section(byte keyType) {
714 idx = new IndexBuilder(keyType);
715 firstBlockPosition = out.size();
716 }
717
718 long write(BlockWriter.Entry entry) throws IOException {
719 if (cur == null) {
720 beginBlock(entry);
721 } else if (!cur.tryAdd(entry)) {
722 flushCurBlock();
723 if (cur.padBetweenBlocks()) {
724 out.padBetweenBlocksToNextBlock();
725 }
726 beginBlock(entry);
727 }
728 entryCnt++;
729 return out.size();
730 }
731
732 private void beginBlock(BlockWriter.Entry entry)
733 throws BlockSizeTooSmallException {
734 byte blockType = entry.blockType();
735 int bs = out.bytesAvailableInBlock();
736 cur = new BlockWriter(blockType, idx.keyType, bs, restartInterval);
737 cur.mustAdd(entry);
738 }
739
740 void flushCurBlock() throws IOException {
741 idx.entries.add(new IndexEntry(cur.lastKey(), out.size()));
742 cur.writeTo(out);
743 }
744
745 void finishSectionMaybeWriteIndex() throws IOException {
746 flushCurBlock();
747 cur = null;
748 if (shouldHaveIndex(idx)) {
749 idx.writeIndex();
750 }
751 bytes = out.size() - firstBlockPosition;
752 }
753 }
754
755 private class IndexBuilder {
756 final byte keyType;
757 List<IndexEntry> entries = new ArrayList<>();
758 long rootPosition;
759 int bytes;
760 int levels;
761
762 IndexBuilder(byte kt) {
763 keyType = kt;
764 }
765
766 int estimateBytes(long curBlockPos) {
767 BlockWriter b = new BlockWriter(
768 INDEX_BLOCK_TYPE, keyType,
769 MAX_BLOCK_SIZE,
770 Math.max(restartInterval, entries.size() / MAX_RESTARTS));
771 try {
772 for (Entry e : entries) {
773 b.mustAdd(e);
774 }
775 if (cur != null) {
776 b.mustAdd(new IndexEntry(cur.lastKey(), curBlockPos));
777 }
778 } catch (BlockSizeTooSmallException e) {
779 return b.currentSize();
780 }
781 return b.currentSize();
782 }
783
784 void writeIndex() throws IOException {
785 if (padBetweenBlocks(keyType)) {
786 out.padBetweenBlocksToNextBlock();
787 }
788 long startPos = out.size();
789 writeMultiLevelIndex(entries);
790 bytes = (int) (out.size() - startPos);
791 entries = null;
792 }
793
794 private void writeMultiLevelIndex(List<IndexEntry> keys)
795 throws IOException {
796 levels = 1;
797 while (maxIndexLevels == 0 || levels < maxIndexLevels) {
798 keys = writeOneLevel(keys);
799 if (keys == null) {
800 return;
801 }
802 levels++;
803 }
804
805
806
807 BlockWriter b = new BlockWriter(
808 INDEX_BLOCK_TYPE, keyType,
809 MAX_BLOCK_SIZE,
810 Math.max(restartInterval, keys.size() / MAX_RESTARTS));
811 for (Entry e : keys) {
812 b.mustAdd(e);
813 }
814 rootPosition = out.size();
815 b.writeTo(out);
816 }
817
818 private List<IndexEntry> writeOneLevel(List<IndexEntry> keys)
819 throws IOException {
820 Section thisLevel = new Section(keyType);
821 for (Entry e : keys) {
822 thisLevel.write(e);
823 }
824 if (!thisLevel.idx.entries.isEmpty()) {
825 thisLevel.flushCurBlock();
826 if (cur.padBetweenBlocks()) {
827 out.padBetweenBlocksToNextBlock();
828 }
829 cur = null;
830 return thisLevel.idx.entries;
831 }
832
833
834 rootPosition = out.size();
835 cur.writeTo(out);
836 cur = null;
837 return null;
838 }
839 }
840 }