From 5c6c374ff660437571369782bfbacea62d2b81a0 Mon Sep 17 00:00:00 2001 From: Anna Papitto Date: Thu, 10 Nov 2022 14:48:22 -0800 Subject: [PATCH] Gc#deleteOrphans: avoid dependence on PackExt alphabetical ordering Deleting orphan files depends on .pack and .keep being reverse-sorted to before the corresponding index files that could be orphans. The new reverse index file extension (.rev) will break that frail dependency. Rewrite Gc#deleteOrphans to avoid that dependence by tracking which pack names have a .pack or .keep file and then deleting any index files that without a corresponding one. This approach takes linear time instead of the O(n logn) time needed for sorting. Change-Id: If83c378ea070b8871d4b01ae008e7bf8270de763 Signed-off-by: Anna Papitto --- .../storage/file/GcOrphanFilesTest.java | 35 +++++++++- .../jgit/internal/storage/file/GC.java | 69 ++++++++++--------- 2 files changed, 69 insertions(+), 35 deletions(-) diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcOrphanFilesTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcOrphanFilesTest.java index 620aedf20f..342e559643 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcOrphanFilesTest.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcOrphanFilesTest.java @@ -10,6 +10,7 @@ package org.eclipse.jgit.internal.storage.file; +import static org.eclipse.jgit.internal.storage.pack.PackExt.REVERSE_INDEX; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; @@ -36,6 +37,14 @@ public class GcOrphanFilesTest extends GcTestCase { private static final String PACK_File_3 = PACK + "-3.pack"; + private static final String REVERSE_File_2 = PACK + "-2." + + REVERSE_INDEX.getExtension(); + + private static final String REVERSE_File_4 = PACK + "-4." + + REVERSE_INDEX.getExtension(); + + private static final String NONEXISTENT_EXT = PACK + "-4.xxxxx"; + private File packDir; @Override @@ -46,14 +55,27 @@ public class GcOrphanFilesTest extends GcTestCase { } @Test - public void bitmapAndIdxDeletedButPackNot() throws Exception { + public void indexesDeletedButPackNot() throws Exception { createFileInPackFolder(BITMAP_File_1); createFileInPackFolder(IDX_File_2); createFileInPackFolder(PACK_File_3); + createFileInPackFolder(REVERSE_File_4); gc.gc().get(); assertFalse(new File(packDir, BITMAP_File_1).exists()); assertFalse(new File(packDir, IDX_File_2).exists()); assertTrue(new File(packDir, PACK_File_3).exists()); + assertFalse(new File(packDir, REVERSE_File_4).exists()); + } + + @Test + public void noPacks_allIndexesDeleted() throws Exception { + createFileInPackFolder(BITMAP_File_1); + createFileInPackFolder(IDX_File_2); + createFileInPackFolder(REVERSE_File_4); + gc.gc().get(); + assertFalse(new File(packDir, BITMAP_File_1).exists()); + assertFalse(new File(packDir, IDX_File_2).exists()); + assertFalse(new File(packDir, REVERSE_File_4).exists()); } @Test @@ -76,19 +98,28 @@ public class GcOrphanFilesTest extends GcTestCase { assertTrue(new File(packDir, IDX_File_malformed).exists()); } + @Test + public void nonexistantExtensionNotDeleted() throws Exception { + createFileInPackFolder(NONEXISTENT_EXT); + gc.gc().get(); + assertTrue(new File(packDir, NONEXISTENT_EXT).exists()); + } + @Test public void keepPreventsDeletionOfIndexFilesForMissingPackFile() throws Exception { createFileInPackFolder(BITMAP_File_1); - createFileInPackFolder(IDX_File_2); createFileInPackFolder(BITMAP_File_2); + createFileInPackFolder(IDX_File_2); createFileInPackFolder(KEEP_File_2); + createFileInPackFolder(REVERSE_File_2); createFileInPackFolder(PACK_File_3); gc.gc().get(); assertFalse(new File(packDir, BITMAP_File_1).exists()); assertTrue(new File(packDir, BITMAP_File_2).exists()); assertTrue(new File(packDir, IDX_File_2).exists()); assertTrue(new File(packDir, KEEP_File_2).exists()); + assertTrue(new File(packDir, REVERSE_File_2).exists()); assertTrue(new File(packDir, PACK_File_3).exists()); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java index ca4f7a21e3..d81f8ee49c 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java @@ -14,6 +14,7 @@ import static org.eclipse.jgit.internal.storage.pack.PackExt.BITMAP_INDEX; import static org.eclipse.jgit.internal.storage.pack.PackExt.INDEX; import static org.eclipse.jgit.internal.storage.pack.PackExt.KEEP; import static org.eclipse.jgit.internal.storage.pack.PackExt.PACK; +import static org.eclipse.jgit.internal.storage.pack.PackExt.REVERSE_INDEX; import java.io.File; import java.io.FileOutputStream; @@ -44,6 +45,7 @@ import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Objects; +import java.util.Optional; import java.util.Set; import java.util.TreeMap; import java.util.concurrent.CompletableFuture; @@ -110,14 +112,10 @@ public class GC { private static final Pattern PATTERN_LOOSE_OBJECT = Pattern .compile("[0-9a-fA-F]{38}"); //$NON-NLS-1$ - private static final String PACK_EXT = "." + PackExt.PACK.getExtension();//$NON-NLS-1$ + private static final Set PARENT_EXTS = Set.of(PACK, KEEP); - private static final String BITMAP_EXT = "." //$NON-NLS-1$ - + PackExt.BITMAP_INDEX.getExtension(); - - private static final String INDEX_EXT = "." + PackExt.INDEX.getExtension(); //$NON-NLS-1$ - - private static final String KEEP_EXT = "." + PackExt.KEEP.getExtension(); //$NON-NLS-1$ + private static final Set CHILD_EXTS = Set.of(BITMAP_INDEX, INDEX, + REVERSE_INDEX); private static final int DEFAULT_AUTOPACKLIMIT = 50; @@ -937,47 +935,52 @@ public class GC { } } + private static Optional toPackFileWithValidExt( + Path packFilePath) { + try { + PackFile packFile = new PackFile(packFilePath.toFile()); + if (packFile.getPackExt() == null) { + return Optional.empty(); + } + return Optional.of(packFile); + } catch (IllegalArgumentException e) { + return Optional.empty(); + } + } + /** * Deletes orphans *

- * A file is considered an orphan if it is either a "bitmap" or an index - * file, and its corresponding pack file is missing in the list. + * A file is considered an orphan if it is some type of index file, but + * there is not a corresponding pack or keep file present in the directory. *

*/ private void deleteOrphans() { Path packDir = repo.getObjectDatabase().getPackDirectory().toPath(); - List fileNames = null; + List childFiles; + Set seenParentIds = new HashSet<>(); try (Stream files = Files.list(packDir)) { - fileNames = files.map(path -> path.getFileName().toString()) - .filter(name -> (name.endsWith(PACK_EXT) - || name.endsWith(BITMAP_EXT) - || name.endsWith(INDEX_EXT) - || name.endsWith(KEEP_EXT))) - // sort files with same base name in the order: - // .pack, .keep, .index, .bitmap to avoid look ahead - .sorted(Collections.reverseOrder()) - .collect(Collectors.toList()); + childFiles = files.map(GC::toPackFileWithValidExt) + .filter(Optional::isPresent).map(Optional::get) + .filter(packFile -> { + PackExt ext = packFile.getPackExt(); + if (PARENT_EXTS.contains(ext)) { + seenParentIds.add(packFile.getId()); + return false; + } + return CHILD_EXTS.contains(ext); + }).collect(Collectors.toList()); } catch (IOException e) { LOG.error(e.getMessage(), e); return; } - if (fileNames == null) { - return; - } - String latestId = null; - for (String n : fileNames) { - PackFile pf = new PackFile(packDir.toFile(), n); - PackExt ext = pf.getPackExt(); - if (ext.equals(PACK) || ext.equals(KEEP)) { - latestId = pf.getId(); - } - if (latestId == null || !pf.getId().equals(latestId)) { - // no pack or keep for this id + for (PackFile child : childFiles) { + if (!seenParentIds.contains(child.getId())) { try { - FileUtils.delete(pf, + FileUtils.delete(child, FileUtils.RETRY | FileUtils.SKIP_MISSING); - LOG.warn(JGitText.get().deletedOrphanInPackDir, pf); + LOG.warn(JGitText.get().deletedOrphanInPackDir, child); } catch (IOException e) { LOG.error(e.getMessage(), e); } -- 2.39.5