reftable: explicitly store update_index per ref

Add an update_index to every reference in a reftable, storing the
exact transaction that last modified the reference.  This is necessary
to fix some merge race conditions.

Consider updates at T1, T3 are present in two reftables.  Compacting
these will create a table with range [T1,T3].  If T2 arrives during
or after the compaction its impossible for readers to know how to
merge the [T1,T3] table with the T2 table.

With an explicit update_index per reference, MergedReftable is able to
individually sort each reference, merging individual entries at T3
from [T1,T3] ahead of identically named entries appearing in T2.

Change-Id: Ie4065d4176a5a0207dcab9696ae05d086e042140

2 files changed, 55 insertions, 13 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java
index f9ebaf6926..adba048e65 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java
@@ -262,6 +262,41 @@ public class MergedReftableTest {
 	}
 
 	@Test
+	public void missedUpdate() throws IOException {
+		ByteArrayOutputStream buf = new ByteArrayOutputStream();
+		ReftableWriter writer = new ReftableWriter()
+				.setMinUpdateIndex(1)
+				.setMaxUpdateIndex(3)
+				.begin(buf);
+		writer.writeRef(ref("refs/heads/a", 1), 1);
+		writer.writeRef(ref("refs/heads/c", 3), 3);
+		writer.finish();
+		byte[] base = buf.toByteArray();
+
+		byte[] delta = write(Arrays.asList(
+				ref("refs/heads/b", 2),
+				ref("refs/heads/c", 4)),
+				2);
+		MergedReftable mr = merge(base, delta);
+		try (RefCursor rc = mr.allRefs()) {
+			assertTrue(rc.next());
+			assertEquals("refs/heads/a", rc.getRef().getName());
+			assertEquals(id(1), rc.getRef().getObjectId());
+			assertEquals(1, rc.getUpdateIndex());
+
+			assertTrue(rc.next());
+			assertEquals("refs/heads/b", rc.getRef().getName());
+			assertEquals(id(2), rc.getRef().getObjectId());
+			assertEquals(2, rc.getUpdateIndex());
+
+			assertTrue(rc.next());
+			assertEquals("refs/heads/c", rc.getRef().getName());
+			assertEquals(id(3), rc.getRef().getObjectId());
+			assertEquals(3, rc.getUpdateIndex());
+		}
+	}
+
+	@Test
 	public void compaction() throws IOException {
 		List<Ref> delta1 = Arrays.asList(
 				ref("refs/heads/next", 4),
@@ -322,12 +357,18 @@ public class MergedReftableTest {
 	}
 
 	private byte[] write(Collection<Ref> refs) throws IOException {
+		return write(refs, 1);
+	}
+
+	private byte[] write(Collection<Ref> refs, long updateIndex)
+			throws IOException {
 		ByteArrayOutputStream buffer = new ByteArrayOutputStream();
-		ReftableWriter writer = new ReftableWriter().begin(buffer);
-		for (Ref r : RefComparator.sort(refs)) {
-			writer.writeRef(r);
-		}
-		writer.finish();
+		new ReftableWriter()
+				.setMinUpdateIndex(updateIndex)
+				.setMaxUpdateIndex(updateIndex)
+				.begin(buffer)
+				.sortAndWriteRefs(refs)
+				.finish();
 		return buffer.toByteArray();
 	}
 
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java
index 6809d7b2b2..3ea3061e38 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java
@@ -126,7 +126,7 @@ public class ReftableTest {
 	@Test
 	public void estimateCurrentBytesOneRef() throws IOException {
 		Ref exp = ref(MASTER, 1);
-		int expBytes = 24 + 4 + 5 + 3 + MASTER.length() + 20 + 68;
+		int expBytes = 24 + 4 + 5 + 4 + MASTER.length() + 20 + 68;
 
 		byte[] table;
 		ReftableConfig cfg = new ReftableConfig();
@@ -155,7 +155,7 @@ public class ReftableTest {
 		cfg.setIndexObjects(false);
 		cfg.setMaxIndexLevels(1);
 
-		int expBytes = 139654;
+		int expBytes = 147860;
 		byte[] table;
 		ReftableWriter writer = new ReftableWriter().setConfig(cfg);
 		try (ByteArrayOutputStream buf = new ByteArrayOutputStream()) {
@@ -174,7 +174,7 @@ public class ReftableTest {
 	public void oneIdRef() throws IOException {
 		Ref exp = ref(MASTER, 1);
 		byte[] table = write(exp);
-		assertEquals(24 + 4 + 5 + 3 + MASTER.length() + 20 + 68, table.length);
+		assertEquals(24 + 4 + 5 + 4 + MASTER.length() + 20 + 68, table.length);
 
 		ReftableReader t = read(table);
 		try (RefCursor rc = t.allRefs()) {
@@ -203,7 +203,7 @@ public class ReftableTest {
 	public void oneTagRef() throws IOException {
 		Ref exp = tag(V1_0, 1, 2);
 		byte[] table = write(exp);
-		assertEquals(24 + 4 + 5 + 2 + V1_0.length() + 40 + 68, table.length);
+		assertEquals(24 + 4 + 5 + 3 + V1_0.length() + 40 + 68, table.length);
 
 		ReftableReader t = read(table);
 		try (RefCursor rc = t.allRefs()) {
@@ -224,7 +224,7 @@ public class ReftableTest {
 		Ref exp = sym(HEAD, MASTER);
 		byte[] table = write(exp);
 		assertEquals(
-				24 + 4 + 5 + 2 + HEAD.length() + 1 + MASTER.length() + 68,
+				24 + 4 + 5 + 2 + HEAD.length() + 2 + MASTER.length() + 68,
 				table.length);
 
 		ReftableReader t = read(table);
@@ -281,7 +281,7 @@ public class ReftableTest {
 		String name = "refs/heads/gone";
 		Ref exp = newRef(name);
 		byte[] table = write(exp);
-		assertEquals(24 + 4 + 5 + 2 + name.length() + 68, table.length);
+		assertEquals(24 + 4 + 5 + 3 + name.length() + 68, table.length);
 
 		ReftableReader t = read(table);
 		try (RefCursor rc = t.allRefs()) {
@@ -425,13 +425,14 @@ public class ReftableTest {
 
 		writer.finish();
 		byte[] table = buffer.toByteArray();
-		assertEquals(245, table.length);
+		assertEquals(247, table.length);
 
 		ReftableReader t = read(table);
 		try (RefCursor rc = t.allRefs()) {
 			assertTrue(rc.next());
 			assertEquals(MASTER, rc.getRef().getName());
 			assertEquals(id(1), rc.getRef().getObjectId());
+			assertEquals(1, rc.getUpdateIndex());
 
 			assertTrue(rc.next());
 			assertEquals(NEXT, rc.getRef().getName());
@@ -636,7 +637,7 @@ public class ReftableTest {
 			writer.finish();
 			fail("expected BlockSizeTooSmallException");
 		} catch (BlockSizeTooSmallException e) {
-			assertEquals(84, e.getMinimumBlockSize());
+			assertEquals(85, e.getMinimumBlockSize());
 		}
 	}