1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.file;
12
13 import static java.nio.charset.StandardCharsets.UTF_8;
14
15 import java.io.BufferedReader;
16 import java.io.File;
17 import java.io.FileInputStream;
18 import java.io.FileNotFoundException;
19 import java.io.FileOutputStream;
20 import java.io.IOException;
21 import java.io.InputStreamReader;
22 import java.nio.file.Files;
23 import java.nio.file.StandardCopyOption;
24 import java.util.ArrayList;
25 import java.util.Comparator;
26 import java.util.List;
27 import java.util.Map;
28 import java.util.Optional;
29 import java.util.function.Supplier;
30 import java.util.stream.Collectors;
31
32 import org.eclipse.jgit.annotations.Nullable;
33 import org.eclipse.jgit.errors.LockFailedException;
34 import org.eclipse.jgit.internal.storage.io.BlockSource;
35 import org.eclipse.jgit.internal.storage.reftable.MergedReftable;
36 import org.eclipse.jgit.internal.storage.reftable.ReftableCompactor;
37 import org.eclipse.jgit.internal.storage.reftable.ReftableConfig;
38 import org.eclipse.jgit.internal.storage.reftable.ReftableReader;
39 import org.eclipse.jgit.internal.storage.reftable.ReftableWriter;
40 import org.eclipse.jgit.lib.Config;
41 import org.eclipse.jgit.util.FileUtils;
42
43
44
45
46
47
48 public class FileReftableStack implements AutoCloseable {
49 private static class StackEntry {
50
51 String name;
52
53 ReftableReader reftableReader;
54 }
55
56 private MergedReftable mergedReftable;
57
58 private List<StackEntry> stack;
59
60 private long lastNextUpdateIndex;
61
62 private final File stackPath;
63
64 private final File reftableDir;
65
66 private final Runnable onChange;
67
68 private final Supplier<Config> configSupplier;
69
70
71 static class CompactionStats {
72
73 long tables;
74
75 long bytes;
76
77 int attempted;
78
79 int failed;
80
81 long refCount;
82
83 long logCount;
84
85 CompactionStats() {
86 tables = 0;
87 bytes = 0;
88 attempted = 0;
89 failed = 0;
90 logCount = 0;
91 refCount = 0;
92 }
93 }
94
95 private final CompactionStats stats;
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111 public FileReftableStack(File stackPath, File reftableDir,
112 @Nullable Runnable onChange, Supplier<Config> configSupplier)
113 throws IOException {
114 this.stackPath = stackPath;
115 this.reftableDir = reftableDir;
116 this.stack = new ArrayList<>();
117 this.configSupplier = configSupplier;
118 this.onChange = onChange;
119
120
121 lastNextUpdateIndex = 0;
122 reload();
123
124 stats = new CompactionStats();
125 }
126
127 CompactionStats getStats() {
128 return stats;
129 }
130
131
132 public static class ReftableNumbersNotIncreasingException
133 extends RuntimeException {
134 private static final long serialVersionUID = 1L;
135
136 String name;
137
138 long lastMax;
139
140 long min;
141
142 ReftableNumbersNotIncreasingException(String name, long lastMax,
143 long min) {
144 this.name = name;
145 this.lastMax = lastMax;
146 this.min = min;
147 }
148
149 @SuppressWarnings({ "nls", "boxing" })
150 @Override
151 public String toString() {
152 return String.format(
153 "ReftableNumbersNotIncreasingException %s: min %d, lastMax %d",
154 name, min, lastMax);
155 }
156 }
157
158
159
160
161
162
163
164
165
166
167
168 private void reloadOnce(List<String> names)
169 throws IOException, FileNotFoundException {
170 Map<String, ReftableReader> current = stack.stream()
171 .collect(Collectors.toMap(e -> e.name, e -> e.reftableReader));
172
173 List<ReftableReader> newTables = new ArrayList<>();
174 List<StackEntry> newStack = new ArrayList<>(stack.size() + 1);
175 try {
176 ReftableReader last = null;
177 for (String name : names) {
178 StackEntry entry = new StackEntry();
179 entry.name = name;
180
181 ReftableReader t = null;
182 if (current.containsKey(name)) {
183 t = current.remove(name);
184 } else {
185 File subtable = new File(reftableDir, name);
186 FileInputStream is;
187
188 is = new FileInputStream(subtable);
189
190 t = new ReftableReader(BlockSource.from(is));
191 newTables.add(t);
192 }
193
194 if (last != null) {
195
196 if (last.maxUpdateIndex() >= t.minUpdateIndex()) {
197 throw new ReftableNumbersNotIncreasingException(name,
198 last.maxUpdateIndex(), t.minUpdateIndex());
199 }
200 }
201 last = t;
202
203 entry.reftableReader = t;
204 newStack.add(entry);
205 }
206
207
208 stack = newStack;
209 newTables.clear();
210
211 current.values().forEach(r -> {
212 try {
213 r.close();
214 } catch (IOException e) {
215 throw new AssertionError(e);
216 }
217 });
218 } finally {
219 newTables.forEach(t -> {
220 try {
221 t.close();
222 } catch (IOException ioe) {
223
224 throw new AssertionError(ioe);
225 }
226 });
227 }
228 }
229
230 void reload() throws IOException {
231
232 long deadline = System.currentTimeMillis() + 2500;
233
234
235
236 long min = 1;
237 long max = 1000;
238 long delay = 0;
239 boolean success = false;
240
241
242
243 int tries = 0;
244 while (tries < 3 || System.currentTimeMillis() < deadline) {
245 List<String> names = readTableNames();
246 tries++;
247 try {
248 reloadOnce(names);
249 success = true;
250 break;
251 } catch (FileNotFoundException e) {
252 List<String> changed = readTableNames();
253 if (changed.equals(names)) {
254 throw e;
255 }
256 }
257
258 delay = FileUtils.delay(delay, min, max);
259 try {
260 Thread.sleep(delay);
261 } catch (InterruptedException e) {
262 Thread.currentThread().interrupt();
263 throw new RuntimeException(e);
264 }
265 }
266
267 if (!success) {
268 throw new LockFailedException(stackPath);
269 }
270
271 mergedReftable = new MergedReftable(stack.stream()
272 .map(x -> x.reftableReader).collect(Collectors.toList()));
273 long curr = nextUpdateIndex();
274 if (lastNextUpdateIndex > 0 && lastNextUpdateIndex != curr
275 && onChange != null) {
276 onChange.run();
277 }
278 lastNextUpdateIndex = curr;
279 }
280
281
282
283
284 public MergedReftable getMergedReftable() {
285 return mergedReftable;
286 }
287
288
289
290
291
292
293 public interface Writer {
294
295
296
297
298
299
300
301 void call(ReftableWriter w) throws IOException;
302 }
303
304 private List<String> readTableNames() throws IOException {
305 List<String> names = new ArrayList<>(stack.size() + 1);
306
307 try (BufferedReader br = new BufferedReader(
308 new InputStreamReader(new FileInputStream(stackPath), UTF_8))) {
309 String line;
310 while ((line = br.readLine()) != null) {
311 if (!line.isEmpty()) {
312 names.add(line);
313 }
314 }
315 } catch (FileNotFoundException e) {
316
317 }
318 return names;
319 }
320
321
322
323
324
325
326 boolean isUpToDate() throws IOException {
327
328
329 try {
330 List<String> names = readTableNames();
331 if (names.size() != stack.size()) {
332 return false;
333 }
334 for (int i = 0; i < names.size(); i++) {
335 if (!names.get(i).equals(stack.get(i).name)) {
336 return false;
337 }
338 }
339 } catch (FileNotFoundException e) {
340 return stack.isEmpty();
341 }
342 return true;
343 }
344
345
346
347
348 @Override
349 public void close() {
350 for (StackEntry entry : stack) {
351 try {
352 entry.reftableReader.close();
353 } catch (Exception e) {
354
355 throw new AssertionError(e);
356 }
357 }
358 }
359
360 private long nextUpdateIndex() throws IOException {
361 return stack.size() > 0
362 ? stack.get(stack.size() - 1).reftableReader.maxUpdateIndex()
363 + 1
364 : 1;
365 }
366
367 private String filename(long low, long high) {
368 return String.format("%012x-%012x",
369 Long.valueOf(low), Long.valueOf(high));
370 }
371
372
373
374
375
376
377
378
379
380
381
382
383 @SuppressWarnings("nls")
384 public boolean addReftable(Writer w) throws IOException {
385 LockFile lock = new LockFile(stackPath);
386 try {
387 if (!lock.lockForAppend()) {
388 return false;
389 }
390 if (!isUpToDate()) {
391 return false;
392 }
393
394 String fn = filename(nextUpdateIndex(), nextUpdateIndex());
395
396 File tmpTable = File.createTempFile(fn + "_", ".ref",
397 stackPath.getParentFile());
398
399 ReftableWriter.Stats s;
400 try (FileOutputStream fos = new FileOutputStream(tmpTable)) {
401 ReftableWriter rw = new ReftableWriter(reftableConfig(), fos);
402 w.call(rw);
403 rw.finish();
404 s = rw.getStats();
405 }
406
407 if (s.minUpdateIndex() < nextUpdateIndex()) {
408 return false;
409 }
410
411
412
413 fn += s.refCount() > 0 ? ".ref" : ".log";
414 File dest = new File(reftableDir, fn);
415
416 FileUtils.rename(tmpTable, dest, StandardCopyOption.ATOMIC_MOVE);
417 lock.write((fn + "\n").getBytes(UTF_8));
418 if (!lock.commit()) {
419 FileUtils.delete(dest);
420 return false;
421 }
422
423 reload();
424
425 autoCompact();
426 } finally {
427 lock.unlock();
428 }
429 return true;
430 }
431
432 private ReftableConfig reftableConfig() {
433 return new ReftableConfig(configSupplier.get());
434 }
435
436
437
438
439
440
441
442
443
444
445
446
447 private File compactLocked(int first, int last) throws IOException {
448 String fn = filename(first, last);
449
450 File tmpTable = File.createTempFile(fn + "_", ".ref",
451 stackPath.getParentFile());
452 try (FileOutputStream fos = new FileOutputStream(tmpTable)) {
453 ReftableCompactor c = new ReftableCompactor(fos)
454 .setConfig(reftableConfig())
455 .setIncludeDeletes(first > 0);
456
457 List<ReftableReader> compactMe = new ArrayList<>();
458 long totalBytes = 0;
459 for (int i = first; i <= last; i++) {
460 compactMe.add(stack.get(i).reftableReader);
461 totalBytes += stack.get(i).reftableReader.size();
462 }
463 c.addAll(compactMe);
464
465 c.compact();
466
467
468
469 stats.bytes += totalBytes;
470 stats.tables += first - last + 1;
471 stats.attempted++;
472 stats.refCount += c.getStats().refCount();
473 stats.logCount += c.getStats().logCount();
474 }
475
476 return tmpTable;
477 }
478
479
480
481
482
483
484
485
486
487
488
489
490
491 boolean compactRange(int first, int last) throws IOException {
492 if (first >= last) {
493 return true;
494 }
495 LockFile lock = new LockFile(stackPath);
496
497 File tmpTable = null;
498 List<LockFile> subtableLocks = new ArrayList<>();
499
500 try {
501 if (!lock.lock()) {
502 return false;
503 }
504 if (!isUpToDate()) {
505 return false;
506 }
507
508 List<File> deleteOnSuccess = new ArrayList<>();
509 for (int i = first; i <= last; i++) {
510 File f = new File(reftableDir, stack.get(i).name);
511 LockFile lf = new LockFile(f);
512 if (!lf.lock()) {
513 return false;
514 }
515 subtableLocks.add(lf);
516 deleteOnSuccess.add(f);
517 }
518
519 lock.unlock();
520 lock = null;
521
522 tmpTable = compactLocked(first, last);
523
524 lock = new LockFile(stackPath);
525 if (!lock.lock()) {
526 return false;
527 }
528 if (!isUpToDate()) {
529 return false;
530 }
531
532 String fn = filename(
533 stack.get(first).reftableReader.minUpdateIndex(),
534 stack.get(last).reftableReader.maxUpdateIndex());
535
536
537
538
539
540
541 fn += ".ref";
542 File dest = new File(reftableDir, fn);
543
544 FileUtils.rename(tmpTable, dest, StandardCopyOption.ATOMIC_MOVE);
545 tmpTable = null;
546
547 StringBuilder sb = new StringBuilder();
548
549 for (int i = 0; i < first; i++) {
550 sb.append(stack.get(i).name + "\n");
551 }
552 sb.append(fn + "\n");
553 for (int i = last + 1; i < stack.size(); i++) {
554 sb.append(stack.get(i).name + "\n");
555 }
556
557 lock.write(sb.toString().getBytes(UTF_8));
558 if (!lock.commit()) {
559 dest.delete();
560 return false;
561 }
562
563 for (File f : deleteOnSuccess) {
564 Files.delete(f.toPath());
565 }
566
567 reload();
568 return true;
569 } finally {
570 if (tmpTable != null) {
571 tmpTable.delete();
572 }
573 for (LockFile lf : subtableLocks) {
574 lf.unlock();
575 }
576 if (lock != null) {
577 lock.unlock();
578 }
579 }
580 }
581
582
583
584
585
586
587
588 static int log(long sz) {
589 long base = 2;
590 if (sz <= 0) {
591 throw new IllegalArgumentException("log2 negative");
592 }
593 int l = 0;
594 while (sz > 0) {
595 l++;
596 sz /= base;
597 }
598
599 return l - 1;
600 }
601
602
603
604
605
606 static class Segment {
607
608 int log;
609
610
611 long bytes;
612
613 int start;
614
615 int end;
616
617 int size() {
618 return end - start;
619 }
620
621 Segment(int start, int end, int log, long bytes) {
622 this.log = log;
623 this.start = start;
624 this.end = end;
625 this.bytes = bytes;
626 }
627
628 Segment() {
629 this(0, 0, 0, 0);
630 }
631
632 @Override
633 public int hashCode() {
634 return 0;
635 }
636
637 @Override
638 public boolean equals(Object other) {
639 Segment o = (Segment) other;
640 return o.bytes == bytes && o.log == log && o.start == start
641 && o.end == end;
642 }
643
644 @SuppressWarnings("boxing")
645 @Override
646 public String toString() {
647 return String.format("{ [%d,%d) l=%d sz=%d }", start, end, log,
648 bytes);
649 }
650 }
651
652 static List<Segment> segmentSizes(long[] sizes) {
653 List<Segment> segments = new ArrayList<>();
654 Segment cur = new Segment();
655 for (int i = 0; i < sizes.length; i++) {
656 int l = log(sizes[i]);
657 if (l != cur.log && cur.bytes > 0) {
658 segments.add(cur);
659 cur = new Segment();
660 cur.start = i;
661 cur.log = l;
662 }
663
664 cur.log = l;
665 cur.end = i + 1;
666 cur.bytes += sizes[i];
667 }
668 segments.add(cur);
669 return segments;
670 }
671
672 private static Optional<Segment> autoCompactCandidate(long[] sizes) {
673 if (sizes.length == 0) {
674 return Optional.empty();
675 }
676
677
678
679
680
681
682
683 List<Segment> segments = segmentSizes(sizes);
684 segments = segments.stream().filter(s -> s.size() > 1)
685 .collect(Collectors.toList());
686 if (segments.isEmpty()) {
687 return Optional.empty();
688 }
689
690 Optional<Segment> optMinSeg = segments.stream()
691 .min(Comparator.comparing(s -> Integer.valueOf(s.log)));
692
693 Segment smallCollected = optMinSeg.get();
694 while (smallCollected.start > 0) {
695 int prev = smallCollected.start - 1;
696 long prevSize = sizes[prev];
697 if (log(smallCollected.bytes) < log(prevSize)) {
698 break;
699 }
700 smallCollected.start = prev;
701 smallCollected.bytes += prevSize;
702 }
703
704 return Optional.of(smallCollected);
705 }
706
707
708
709
710
711
712
713 private void autoCompact() throws IOException {
714 Optional<Segment> cand = autoCompactCandidate(tableSizes());
715 if (cand.isPresent()) {
716 if (!compactRange(cand.get().start, cand.get().end - 1)) {
717 stats.failed++;
718 }
719 }
720 }
721
722
723 private static long OVERHEAD = 91;
724
725 private long[] tableSizes() throws IOException {
726 long[] sizes = new long[stack.size()];
727 for (int i = 0; i < stack.size(); i++) {
728
729
730
731 sizes[i] = stack.get(i).reftableReader.size() - OVERHEAD;
732 }
733 return sizes;
734 }
735
736 void compactFully() throws IOException {
737 if (!compactRange(0, stack.size() - 1)) {
738 stats.failed++;
739 }
740 }
741 }