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