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