Simple reftable backend

This series comes from a conversation with Patrick Steinhardt at Gitlab, who have an interest in a more scalable ref storage system.

I unfortunately don't have business reasons to spend much time on this project anymore, and the original, sweeping migration has too many open questions.

I thought of an alternate approach, and I wanted to show it as input to discussions at the contributor summit.

I think the first part ("refs: push lock management into packed backend") is a good improvement overall, and could be landed separately without much tweaking.

The second part ("refs: alternate reftable ref backend implementation") is something open for discussion: the alternative "packed storage" is based on reftable, but it could conceivably be a different type of database/file format too. I think it's attractive to use reftable here, because over time more data (symrefs, reflog) could be moved into reftable.

Han-Wen Nienhuys (3):
refs: push lock management into packed backend
refs: move is_packed_transaction_needed out of packed-backend.c
refs: alternate reftable ref backend implementation

 Makefile                        |    1 +
 config.mak.uname                |    2 +-
 contrib/workdir/git-new-workdir |    2 +-
 refs.c                          |    8 +
 refs/debug.c                    |   15 +
 refs/files-backend.c            |  182 +++-
 refs/packed-backend.c           |  150 +--
 refs/packed-backend.h           |   19 -
 refs/refs-internal.h            |    6 +
 refs/reftable-backend.c         | 1745 +++++++++++++++++++++++++++++++
 refs/reftable-backend.h         |    8 +
 11 files changed, 1941 insertions(+), 197 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100644 refs/reftable-backend.h

base-commit: bda494f4043963b9ec9a1ecd4b19b7d1cd9a0518
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1574%2Fhanwen%2Fsimple-reftable-backend-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1574/hanwen/simple-reftable-backend-v1
Pull-Request: https://github.com/git/git/pull/1574

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

Introduces a ref backend method transaction_begin, which for the packed backend takes packed-refs.lock.

This decouples the files backend from the packed backend, allowing the latter to be swapped out by another ref backend.

---
 refs.c                |  8 +++++
 refs/debug.c          | 15 +++++++++
 refs/files-backend.c  | 78 +++++++++++++++----------------------------
 refs/packed-backend.c | 41 ++++++++++++++---------
 refs/packed-backend.h | 10 ------
 refs/refs-internal.h  |  5 +++
 6 files changed, 79 insertions(+), 78 deletions(-)

index fcae5dddc60..a2d1012520e 100644
@@ -1130,10 +1130,18 @@ struct ref_transaction *ref_store_transaction_begin(struct ref_store *refs,
 						    struct strbuf *err)
 {
 	struct ref_transaction *tr;
+	int ret = 0;
 	assert(err);
 
 	CALLOC_ARRAY(tr, 1);
 	tr->ref_store = refs;
+
+	if (refs->be->transaction_begin)
+		ret = refs->be->transaction_begin(refs, tr, err);
+	if (ret) {
+		free(tr);
+		return NULL;
+	}
 	return tr;
 }
 

index b7ffc4ce67e..964806e9301 100644
@@ -41,6 +41,20 @@ static int debug_init_db(struct ref_store *refs, struct strbuf *err)
 	return res;
 }
 
+static int debug_transaction_begin(struct ref_store *refs,
+				   struct ref_transaction *transaction,
+				   struct strbuf *err)
+{
+	struct debug_ref_store *drefs = (struct debug_ref_store *)refs;
+	int res;
+	transaction->ref_store = drefs->refs;
+	res = drefs->refs->be->transaction_begin(drefs->refs, transaction,
+						   err);
+	trace_printf_key(&trace_refs, "transaction_begin: %d \"%s\"\n", res,
+			 err->buf);
+	return res;
+}
+
 static int debug_transaction_prepare(struct ref_store *refs,
 				     struct ref_transaction *transaction,
 				     struct strbuf *err)

@@ -451,6 +465,7 @@ struct ref_storage_be refs_be_debug = {
 	 * has a function we should also have a wrapper for it here.
 	 * Test the output with "GIT_TRACE_REFS=1".
 	 */
+	.transaction_begin = debug_transaction_begin,
 	.transaction_prepare = debug_transaction_prepare,
 	.transaction_finish = debug_transaction_finish,
 	.transaction_abort = debug_transaction_abort,

index 9dd8a344c34..ade3c8a5ac4 100644
@@ -17,16 +17,6 @@ struct ref_store *packed_ref_store_create(struct repository *repo,
 					  const char *gitdir,
 					  unsigned int store_flags);
 
-/*
- * Lock the packed-refs file for writing. Flags is passed to
- * hold_lock_file_for_update(). Return 0 on success. On errors, write
- * an error message to `err` and return a nonzero value.
- */
-int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err);
-
-void packed_refs_unlock(struct ref_store *ref_store);
-int packed_refs_is_locked(struct ref_store *ref_store);
-
 /*
  * Return true if `transaction` really needs to be carried out against
  * the specified packed_ref_store, or false if it can be skipped

index 9db8aec4da8..87f8e8b51d6 100644
@@ -531,6 +531,10 @@ typedef struct ref_store *ref_store_init_fn(struct repository *repo,
 
 typedef int ref_init_db_fn(struct ref_store *refs, struct strbuf *err);
 
+typedef int ref_transaction_begin_fn(struct ref_store *refs,
+				     struct ref_transaction *transaction,
+				     struct strbuf *err);
+
 typedef int ref_transaction_prepare_fn(struct ref_store *refs,
 				       struct ref_transaction *transaction,
 				       struct strbuf *err);

@@ -670,6 +674,7 @@ struct ref_storage_be {
 	ref_store_init_fn *init;
 	ref_init_db_fn *init_db;
 
+	ref_transaction_begin_fn *transaction_begin;
 	ref_transaction_prepare_fn *transaction_prepare;
 	ref_transaction_finish_fn *transaction_finish;
 	ref_transaction_abort_fn *transaction_abort;

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

It is no longer specific to the packed backend.

---
 refs/files-backend.c  | 96 +++++++++++++++++++++++++++++++++++++++++++
 refs/packed-backend.c | 95 ------------------------------------------
 refs/packed-backend.h |  9 ----
 3 files changed, 96 insertions(+), 104 deletions(-)

index 4a6781af783..c0a7e3d375b 100644
@@ -2630,6 +2630,101 @@ out:
 	return ret;
 }
 
+
+/*
+ * Return true if `transaction` really needs to be carried out against
+ * the specified packed_ref_store, or false if it can be skipped
+ * (i.e., because it is an obvious NOOP). `ref_store` must be locked
+ * before calling this function.
+ */
+static int is_packed_transaction_needed(struct ref_store *ref_store,
+				 struct ref_transaction *transaction)
+{
+	struct strbuf referent = STRBUF_INIT;
+	size_t i;
+	int ret;
+
+	/*
+	 * We're only going to bother returning false for the common,
+	 * trivial case that references are only being deleted, their
+	 * old values are not being checked, and the old `packed-refs`
+	 * file doesn't contain any of those reference(s). This gives
+	 * false positives for some other cases that could
+	 * theoretically be optimized away:
+	 *
+	 * 1. It could be that the old value is being verified without
+	 *    setting a new value. In this case, we could verify the
+	 *    old value here and skip the update if it agrees. If it
+	 *    disagrees, we could either let the update go through
+	 *    (the actual commit would re-detect and report the
+	 *    problem), or come up with a way of reporting such an
+	 *    error to *our* caller.
+	 *
+	 * 2. It could be that a new value is being set, but that it
+	 *    is identical to the current packed value of the
+	 *    reference.
+	 *
+	 * Neither of these cases will come up in the current code,
+	 * because the only caller of this function passes to it a
+	 * transaction that only includes `delete` updates with no
+	 * `old_id`. Even if that ever changes, false positives only
+	 * cause an optimization to be missed; they do not affect
+	 * correctness.
+	 */
+
+	/*
+	 * Start with the cheap checks that don't require old
+	 * reference values to be read:
+	 */
+	for (i = 0; i < transaction->nr; i++) {
+		struct ref_update *update = transaction->updates[i];
+
+		if (update->flags & REF_HAVE_OLD)
+			/* Have to check the old value -> needed. */
+			return 1;
+
+		if ((update->flags & REF_HAVE_NEW) && !is_null_oid(&update->new_oid))
+			/* Have to set a new value -> needed. */
+			return 1;
+	}
+
+	/*
+	 * The transaction isn't checking any old values nor is it
+	 * setting any nonzero new values, so it still might be able
+	 * to be skipped. Now do the more expensive check: the update
+	 * is needed if any of the updates is a delete, and the old
+	 * `packed-refs` file contains a value for that reference.
+	 */
+	ret = 0;
+	for (i = 0; i < transaction->nr; i++) {
+		struct ref_update *update = transaction->updates[i];
+		int failure_errno;
+		unsigned int type;
+		struct object_id oid;
+
+		if (!(update->flags & REF_HAVE_NEW))
+			/*
+			 * This reference isn't being deleted -> not
+			 * needed.
+			 */
+			continue;
+
+		if (!refs_read_raw_ref(ref_store, update->refname, &oid,
+				       &referent, &type, &failure_errno) ||
+		    failure_errno != ENOENT) {
+			/*
+			 * We have to actually delete that reference
+			 * -> this transaction is needed.
+			 */
+			ret = 1;
+			break;
+		}
+	}
+
+	strbuf_release(&referent);
+	return ret;
+}
+
 struct files_transaction_backend_data {
 	struct ref_transaction *packed_transaction;
 	int packed_transaction_needed;

@@ -3294,3 +3389,4 @@ struct ref_storage_be refs_be_files = {
 	.delete_reflog = files_delete_reflog,
 	.reflog_expire = files_reflog_expire
 };
+

index ade3c8a5ac4..51a3b6a332a 100644
@@ -17,13 +17,4 @@ struct ref_store *packed_ref_store_create(struct repository *repo,
 					  const char *gitdir,
 					  unsigned int store_flags);
 
-/*
- * Return true if `transaction` really needs to be carried out against
- * the specified packed_ref_store, or false if it can be skipped
- * (i.e., because it is an obvious NOOP). `ref_store` must be locked
- * before calling this function.
- */
-int is_packed_transaction_needed(struct ref_store *ref_store,
-				 struct ref_transaction *transaction);
-
 #endif /* REFS_PACKED_BACKEND_H */

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

This introduces the reftable backend as an alternative to the packed backend. This simplifies the code, because we now longer have to worry about:

- pseudorefs and the HEAD ref
- worktrees
- commands that blur together files and references (cherry-pick, rebase)

This deviates from the spec that in Documentation/technical/reftable.txt. It might be possible to update the code such that all writes by default go to reftable directly. Then the result would be compatible with an implementation that writes only reftable (the reftable lock would still prevent races) relative to an implementation that disregards loose refs. Or, JGit could be adapted to follow this implementation.

For this incremental path, the reftable format is arguably more complex than necessary, as

- packed-refs doesn't support symrefs
- reflogs aren't moved into reftable/

on the other hand, the code is already there, and it's well-structured and well-tested.

This implementation is a prototype. To test, you need to do export GIT_TEST_REFTABLE=1. Doing so creates a handful of errors in the test-suite, most seemingly related to the new behavior of pack-refs (which creates a reftable/ dir and not a packed-refs file.), but it seems overseeable.

---
 Makefile                        |    1 +
 config.mak.uname                |    2 +-
 contrib/workdir/git-new-workdir |    2 +-
 refs/files-backend.c            |    8 +-
 refs/packed-backend.c           |   14 +-
 refs/refs-internal.h            |    1 +
 refs/reftable-backend.c         | 1745 +++++++++++++++++++++++++++++++
 refs/reftable-backend.h         |    8 +
 8 files changed, 1766 insertions(+), 15 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100644 refs/reftable-backend.h

index 57763093653..272d3f7f1e9 100644
@@ -1118,6 +1118,7 @@ LIB_OBJS += reflog.o
 LIB_OBJS += refs.o
 LIB_OBJS += refs/debug.o
 LIB_OBJS += refs/files-backend.o
+LIB_OBJS += refs/reftable-backend.o
 LIB_OBJS += refs/iterator.o
 LIB_OBJS += refs/packed-backend.o
 LIB_OBJS += refs/ref-cache.o

index 3bb03f423a0..843829c02fd 100644
@@ -743,7 +743,7 @@ vcxproj:
 
 	# Make .vcxproj files and add them
 	perl contrib/buildsystems/generate -g Vcxproj
-	git add -f git.sln {*,*/lib,t/helper/*}/*.vcxproj
+	git add -f git.sln {*,*/lib,*/libreftable,t/helper/*}/*.vcxproj
 
 	# Generate the LinkOrCopyBuiltins.targets and LinkOrCopyRemoteHttp.targets file
 	(echo '<Project xmlns="http://schemas.microsoft.com/developer/msbuild/2003">' && \

index 888c34a5215..989197aace0 100755
@@ -79,7 +79,7 @@ trap cleanup $siglist
 # create the links to the original repo.  explicitly exclude index, HEAD and
 # logs/HEAD from the list since they are purely related to the current working
 # directory, and should not be shared.
-for x in config refs logs/refs objects info hooks packed-refs remotes rr-cache svn
+for x in config refs logs/refs objects info hooks packed-refs remotes rr-cache svn reftable
 do
 	# create a containing directory if needed
 	case $x in

index c0a7e3d375b..725321a229e 100644
@@ -9,6 +9,7 @@
 #include "refs-internal.h"
 #include "ref-cache.h"
 #include "packed-backend.h"
+#include "reftable-backend.h"
 #include "../ident.h"
 #include "../iterator.h"
 #include "../dir-iterator.h"

@@ -103,8 +104,13 @@ static struct ref_store *files_ref_store_create(struct repository *repo,
 	refs->store_flags = flags;
 	get_common_dir_noenv(&sb, gitdir);
 	refs->gitcommondir = strbuf_detach(&sb, NULL);
+
+	/* TODO: should look at the repo to decide whether to use packed-refs or
+	 * reftable. */
 	refs->packed_ref_store =
-		packed_ref_store_create(repo, refs->gitcommondir, flags);
+		git_env_bool("GIT_TEST_REFTABLE", 0)  
+		? git_reftable_ref_store_create(repo, refs->gitcommondir, flags)
+		: packed_ref_store_create(repo, refs->gitcommondir, flags);
 
 	chdir_notify_reparent("files-backend $GIT_DIR", &refs->base.gitdir);
 	chdir_notify_reparent("files-backend $GIT_COMMONDIR",

index ba895c845c0..ad72cad8024 100644
@@ -1153,7 +1153,7 @@ static int write_packed_entry(FILE *fh, const char *refname,
 	return 0;
 }
 
-int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)
+static int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)
 {
 	struct packed_ref_store *refs =
 		packed_downcast(ref_store, REF_STORE_WRITE | REF_STORE_MAIN,

@@ -1212,7 +1212,7 @@ int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)
 	return 0;
 }
 
-void packed_refs_unlock(struct ref_store *ref_store)
+static void packed_refs_unlock(struct ref_store *ref_store)
 {
 	struct packed_ref_store *refs = packed_downcast(
 			ref_store,

@@ -1224,16 +1224,6 @@ void packed_refs_unlock(struct ref_store *ref_store)
 	rollback_lock_file(&refs->lock);
 }
 
-int packed_refs_is_locked(struct ref_store *ref_store)
-{
-	struct packed_ref_store *refs = packed_downcast(
-			ref_store,
-			REF_STORE_READ | REF_STORE_WRITE,
-			"packed_refs_is_locked");
-
-	return is_lock_file_locked(&refs->lock);
-}
-
 /*
  * The packed-refs header line that we write out. Perhaps other traits
  * will be added later.

index 87f8e8b51d6..172ae23534b 100644
@@ -700,6 +700,7 @@ struct ref_storage_be {
 };
 
 extern struct ref_storage_be refs_be_files;
+extern struct ref_storage_be refs_be_reftable;
 extern struct ref_storage_be refs_be_packed;
 
 /*

new file mode 100644
index 00000000000..bf5fd42229a
@@ -0,0 +1,8 @@
+#ifndef REFS_REFTABLE_BACKEND_H
+#define REFS_REFTABLE_BACKEND_H
+
+struct ref_store *git_reftable_ref_store_create(struct repository *repo,
+						const char *gitdir,
+						unsigned int store_flags);
+
+#endif /* REFS_REFTABLE_BACKEND_H */

gitgitgadget

It looked quite nice to remove more knowledge specific to the .git/packed-refs backend from the files backend, and instead have the files backend rely more on the backend-provided methods to make it work together with whatever backend happens to be in use. There were a few minor things I found puzzling, but other than that, the two patches looked mostly sensible.

Changed this in the next version.

you're not missing something. I didn't have enough time yesterday to look into all the details.

Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--

Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Geschäftsführer: Paul Manicle, Liana Sebastian

From: Han-Wen Nienhuys <[email protected]>

This prepares for taking locks on constructing the transaction.

---
 refs.c                | 8 +++-----
 refs/debug.c          | 8 ++++++++
 refs/files-backend.c  | 8 ++++++++
 refs/packed-backend.c | 9 +++++++++
 refs/refs-internal.h  | 4 ++++
 5 files changed, 32 insertions(+), 5 deletions(-)

index fcae5dddc60..f7ba3e56284 100644
@@ -1129,11 +1129,9 @@ int read_ref_at(struct ref_store *refs, const char *refname,
 struct ref_transaction *ref_store_transaction_begin(struct ref_store *refs,
 						    struct strbuf *err)
 {
-	struct ref_transaction *tr;
-	assert(err);
-
-	CALLOC_ARRAY(tr, 1);
-	tr->ref_store = refs;
+	struct ref_transaction *tr = refs->be->transaction_begin(refs, err);
+	if (tr)
+		tr->ref_store = refs;
 	return tr;
 }
 

index b7ffc4ce67e..95fb3eb4430 100644
@@ -41,6 +41,13 @@ static int debug_init_db(struct ref_store *refs, struct strbuf *err)
 	return res;
 }
 
+static struct ref_transaction *debug_transaction_begin(struct ref_store *ref_store,
+						       struct strbuf *err) {
+	struct ref_transaction *tr;
+	CALLOC_ARRAY(tr, 1);
+	return tr;
+}
+
 static int debug_transaction_prepare(struct ref_store *refs,
 				     struct ref_transaction *transaction,
 				     struct strbuf *err)

@@ -451,6 +458,7 @@ struct ref_storage_be refs_be_debug = {
 	 * has a function we should also have a wrapper for it here.
 	 * Test the output with "GIT_TRACE_REFS=1".
 	 */
+	.transaction_begin = debug_transaction_begin,
 	.transaction_prepare = debug_transaction_prepare,
 	.transaction_finish = debug_transaction_finish,
 	.transaction_abort = debug_transaction_abort,

index 341354182bb..d83eea8b408 100644
@@ -2681,6 +2681,13 @@ static void files_transaction_cleanup(struct files_ref_store *refs,
 	transaction->state = REF_TRANSACTION_CLOSED;
 }
 
+static struct ref_transaction *files_transaction_begin(struct ref_store *ref_store,
+						       struct strbuf *err) {
+	struct ref_transaction *tr;
+	CALLOC_ARRAY(tr, 1);
+	return tr;
+}
+
 static int files_transaction_prepare(struct ref_store *ref_store,
 				     struct ref_transaction *transaction,
 				     struct strbuf *err)

@@ -3297,6 +3304,7 @@ struct ref_storage_be refs_be_files = {
 	.name = "files",
 	.init = files_ref_store_create,
 	.init_db = files_init_db,
+	.transaction_begin = files_transaction_begin,
 	.transaction_prepare = files_transaction_prepare,
 	.transaction_finish = files_transaction_finish,
 	.transaction_abort = files_transaction_abort,

index 59c78d7941f..4f5b1025605 100644
@@ -1580,6 +1580,14 @@ static void packed_transaction_cleanup(struct packed_ref_store *refs,
 	transaction->state = REF_TRANSACTION_CLOSED;
 }
 
+
+static struct ref_transaction *packed_transaction_begin(struct ref_store *ref_store,
+							struct strbuf *err) {
+	struct ref_transaction *tr;
+	CALLOC_ARRAY(tr, 1);
+	return tr;
+}
+
 static int packed_transaction_prepare(struct ref_store *ref_store,
 				      struct ref_transaction *transaction,
 				      struct strbuf *err)

@@ -1758,6 +1766,7 @@ struct ref_storage_be refs_be_packed = {
 	.name = "packed",
 	.init = packed_ref_store_create,
 	.init_db = packed_init_db,
+	.transaction_begin = packed_transaction_begin,
 	.transaction_prepare = packed_transaction_prepare,
 	.transaction_finish = packed_transaction_finish,
 	.transaction_abort = packed_transaction_abort,

index 9db8aec4da8..0a15e8a2ac8 100644
@@ -531,6 +531,9 @@ typedef struct ref_store *ref_store_init_fn(struct repository *repo,
 
 typedef int ref_init_db_fn(struct ref_store *refs, struct strbuf *err);
 
+typedef struct ref_transaction *ref_transaction_begin_fn(struct ref_store *refs,
+							 struct strbuf *err);
+
 typedef int ref_transaction_prepare_fn(struct ref_store *refs,
 				       struct ref_transaction *transaction,
 				       struct strbuf *err);

@@ -670,6 +673,7 @@ struct ref_storage_be {
 	ref_store_init_fn *init;
 	ref_init_db_fn *init_db;
 
+	ref_transaction_begin_fn *transaction_begin;
 	ref_transaction_prepare_fn *transaction_prepare;
 	ref_transaction_finish_fn *transaction_finish;
 	ref_transaction_abort_fn *transaction_abort;

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

This ensures that all transaction methods are properly printed. This is needed because the callbacks are called as transaction->ref_store->backend->$CALLBACK.

Originally, there was a hacky workaround which overwrote transaction->ref_store before passing it into the non-debug prepare() callback. This would print something for the prepare function, but not for abort/finish functions.

---
 refs/debug.c | 83 +++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 59 insertions(+), 24 deletions(-)

index 95fb3eb4430..30509da4b89 100644
@@ -43,25 +43,18 @@ static int debug_init_db(struct ref_store *refs, struct strbuf *err)
 
 static struct ref_transaction *debug_transaction_begin(struct ref_store *ref_store,
 						       struct strbuf *err) {
+	struct debug_ref_store *drefs = (struct debug_ref_store *)ref_store;
 	struct ref_transaction *tr;
+	struct ref_transaction *sub_tr = ref_store_transaction_begin(drefs->refs, err);
+	trace_printf_key(&trace_refs, "transaction_begin: %s\n", err->buf);
+	if (!sub_tr) {
+		return NULL;
+	}
 	CALLOC_ARRAY(tr, 1);
+	tr->backend_data = sub_tr;
 	return tr;
 }
 
-static int debug_transaction_prepare(struct ref_store *refs,
-				     struct ref_transaction *transaction,
-				     struct strbuf *err)
-{
-	struct debug_ref_store *drefs = (struct debug_ref_store *)refs;
-	int res;
-	transaction->ref_store = drefs->refs;
-	res = drefs->refs->be->transaction_prepare(drefs->refs, transaction,
-						   err);
-	trace_printf_key(&trace_refs, "transaction_prepare: %d \"%s\"\n", res,
-			 err->buf);
-	return res;
-}
-
 static void print_update(int i, const char *refname,
 			 const struct object_id *old_oid,
 			 const struct object_id *new_oid, unsigned int flags,

@@ -77,20 +70,59 @@ static void print_update(int i, const char *refname,
 	type &= 0xf; /* see refs.h REF_* */
 	flags &= REF_HAVE_NEW | REF_HAVE_OLD | REF_NO_DEREF |
 		REF_FORCE_CREATE_REFLOG;
-	trace_printf_key(&trace_refs, "%d: %s %s -> %s (F=0x%x, T=0x%x) \"%s\"\n", i, refname,
+	trace_printf_key(&trace_refs, "  %d: '%s' %s -> %s (F=0x%x, T=0x%x) \"%s\"\n", i, refname,
 		o, n, flags, type, msg);
 }
 
-static void print_transaction(struct ref_transaction *transaction)
+static void print_transaction(struct ref_transaction *transaction,
+			      const char *action,
+			      int res, struct strbuf *err)
 {
 	int i;
-	trace_printf_key(&trace_refs, "transaction {\n");
+	trace_printf_key(&trace_refs, "transaction %s {\n", action);
 	for (i = 0; i < transaction->nr; i++) {
 		struct ref_update *u = transaction->updates[i];
 		print_update(i, u->refname, &u->old_oid, &u->new_oid, u->flags,
 			     u->type, u->msg);
 	}
-	trace_printf_key(&trace_refs, "}\n");
+	trace_printf_key(&trace_refs, "}: %d '%s'\n", res, err->buf);
+}
+
+static void copy_update(struct ref_update *dst,
+			struct ref_update *src) {
+	/* dst->refname is const char; can't assign structs */
+	dst->new_oid = src->new_oid;
+	dst->old_oid = src->old_oid;
+	dst->flags = src->flags;
+	dst->backend_data = NULL;
+	dst->type = src->type;
+	dst->msg = xstrdup(src->msg);
+	dst->parent_update = NULL;
+	/* refname is done as part of FLEX_ALLOC_STR. */
+}
+
+static int debug_transaction_prepare(struct ref_store *refs,
+				     struct ref_transaction *transaction,
+				     struct strbuf *err)
+{
+	struct debug_ref_store *drefs = (struct debug_ref_store *)refs;
+	struct ref_transaction *sub_transaction = transaction->backend_data;
+	int res;
+	int i;
+
+	ALLOC_GROW(sub_transaction->updates, transaction->nr, sub_transaction->alloc);
+	for (i = 0;  i < transaction->nr; i++) {
+		struct ref_update *up = transaction->updates[i];
+		struct ref_update *sub_up;
+		FLEX_ALLOC_STR(sub_up, refname, up->refname);
+		copy_update(sub_up, up);
+		sub_transaction->updates[i] = sub_up;
+	}
+	sub_transaction->nr = transaction->nr;
+	res = drefs->refs->be->transaction_prepare(drefs->refs, sub_transaction,
+						   err);
+	print_transaction(sub_transaction, "prepare", res, err);
+	return res;
 }
 
 static int debug_transaction_finish(struct ref_store *refs,

@@ -98,12 +130,11 @@ static int debug_transaction_finish(struct ref_store *refs,
 				    struct strbuf *err)
 {
 	struct debug_ref_store *drefs = (struct debug_ref_store *)refs;
+	struct ref_transaction *sub_transaction = transaction->backend_data;
 	int res;
-	transaction->ref_store = drefs->refs;
-	res = drefs->refs->be->transaction_finish(drefs->refs, transaction,
+	res = drefs->refs->be->transaction_finish(drefs->refs, sub_transaction,
 						  err);
-	print_transaction(transaction);
-	trace_printf_key(&trace_refs, "finish: %d\n", res);
+	print_transaction(sub_transaction, "finish", res, err);
 	return res;
 }
 

@@ -112,9 +143,11 @@ static int debug_transaction_abort(struct ref_store *refs,
 				   struct strbuf *err)
 {
 	struct debug_ref_store *drefs = (struct debug_ref_store *)refs;
+	struct ref_transaction *sub_transaction = transaction->backend_data;
 	int res;
 	transaction->ref_store = drefs->refs;
-	res = drefs->refs->be->transaction_abort(drefs->refs, transaction, err);
+	res = drefs->refs->be->transaction_abort(drefs->refs, sub_transaction, err);
+	print_transaction(sub_transaction, "abort", res, err);
 	return res;
 }
 

@@ -123,10 +156,12 @@ static int debug_initial_transaction_commit(struct ref_store *refs,
 					    struct strbuf *err)
 {
 	struct debug_ref_store *drefs = (struct debug_ref_store *)refs;
+	struct ref_transaction *sub_transaction = transaction->backend_data;
 	int res;
 	transaction->ref_store = drefs->refs;
 	res = drefs->refs->be->initial_transaction_commit(drefs->refs,
-							  transaction, err);
+							  sub_transaction, err);
+	print_transaction(sub_transaction, "commit", res, err);
 	return res;
 }
 

gitgitgadget

This series comes from a conversation with Patrick Steinhardt at Gitlab, who have an interest in a more scalable ref storage system.

I unfortunately don't have business reasons to spend much time on this project anymore, and the original, sweeping migration has too many open questions.

I thought of an alternate approach, and I wanted to show it as input to discussions at the contributor summit.

I think the first part (everything before "refs: alternate reftable ref backend implementation") is a good improvement overall, and could be landed separately without much tweaking.

The second part ("refs: alternate reftable ref backend implementation" and follow-on) is something open for discussion: the alternative "packed storage" is based on reftable, but it could conceivably be a different type of database/file format too. I think it's attractive to use reftable here, because over time more data (symrefs, reflog) could be moved into reftable.

I'm offering this series as a RFC. I hope that someone else (Patrick?) can look into getting the bits and pieces of this merged.

Han-Wen Nienhuys (6):
refs: construct transaction using a _begin callback
refs: wrap transaction in a debug-specific transaction
refs: push lock management into packed backend
refs: move is_packed_transaction_needed out of packed-backend.c
refs: alternate reftable ref backend implementation
refs: always try to do packed transactions for reftable

 Makefile                        |    1 +
 config.mak.uname                |    2 +-
 contrib/workdir/git-new-workdir |    2 +-
 refs.c                          |   13 +-
 refs/debug.c                    |   87 +-
 refs/files-backend.c            |  216 ++--
 refs/packed-backend.c           |  149 +--
 refs/packed-backend.h           |   19 -
 refs/refs-internal.h            |    5 +
 refs/reftable-backend.c         | 1658 +++++++++++++++++++++++++++++++
 refs/reftable-backend.h         |    8 +
 11 files changed, 1929 insertions(+), 231 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100644 refs/reftable-backend.h

base-commit: bda494f4043963b9ec9a1ecd4b19b7d1cd9a0518
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-1574%2Fhanwen%2Fsimple-reftable-backend-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-1574/hanwen/simple-reftable-backend-v2
Pull-Request: https://github.com/git/git/pull/1574

Range-diff vs v1:

 -:  ----------- > 1:  e99f3d20056 refs: construct transaction using a _begin callback
 -:  ----------- > 2:  9a459259330 refs: wrap transaction in a debug-specific transaction
 1:  dea0fbb139a ! 3:  8dedb23eb69 refs: push lock management into packed backend

@@ Metadata
## Commit message ##
refs: push lock management into packed backend

- Introduces a ref backend method transaction_begin, which for the
- packed backend takes packed-refs.lock.
+ Take packed-refs.lock in the transaction_begin of the packed backend.

This decouples the files backend from the packed backend, allowing the latter to be swapped out by another ref backend.
@@ Commit message

## refs.c ##
-@@ refs.c: struct ref_transaction *ref_store_transaction_begin(struct ref_store *refs,
- struct strbuf *err)
- {
- struct ref_transaction *tr;
-+ int ret = 0;
- assert(err);
-
- CALLOC_ARRAY(tr, 1);
- tr->ref_store = refs;
-+
-+ if (refs->be->transaction_begin)
-+ ret = refs->be->transaction_begin(refs, tr, err);
-+ if (ret) {
-+ free(tr);
-+ return NULL;
-+ }
- return tr;
- }
-
-
- ## refs/debug.c ##
-@@ refs/debug.c: static int debug_init_db(struct ref_store *refs, struct strbuf *err)
- return res;
- }
-
-+static int debug_transaction_begin(struct ref_store *refs,
-+ struct ref_transaction *transaction,
-+ struct strbuf *err)
-+{
-+ struct debug_ref_store *drefs = (struct debug_ref_store *)refs;
-+ int res;
-+ transaction->ref_store = drefs->refs;
-+ res = drefs->refs->be->transaction_begin(drefs->refs, transaction,
-+ err);
-+ trace_printf_key(&trace_refs, "transaction_begin: %d \"%s\"\n", res,
-+ err->buf);
-+ return res;
-+}
-+
- static int debug_transaction_prepare(struct ref_store *refs,
- struct ref_transaction *transaction,
- struct strbuf *err)
-@@ refs/debug.c: struct ref_storage_be refs_be_debug = {
- * has a function we should also have a wrapper for it here.
- * Test the output with "GIT_TRACE_REFS=1".
- */
-+ .transaction_begin = debug_transaction_begin,
- .transaction_prepare = debug_transaction_prepare,
- .transaction_finish = debug_transaction_finish,
- .transaction_abort = debug_transaction_abort,
+@@ refs.c: int ref_transaction_abort(struct ref_transaction *transaction,
+ int ret = 0;
+
+ switch (transaction->state) {
+- case REF_TRANSACTION_OPEN:
+- /* No need to abort explicitly. */
+- break;
+ case REF_TRANSACTION_PREPARED:
++ case REF_TRANSACTION_OPEN:
++ /* an OPEN transactions may have a lock. */
+ ret = refs->be->transaction_abort(refs, transaction, err);
+ break;
+ case REF_TRANSACTION_CLOSED:

## refs/files-backend.c ##
@@ refs/files-backend.c: static int files_pack_refs(struct ref_store *ref_store,
@@ refs/files-backend.c: static int files_transaction_finish(struct ref_store *ref_
- backend_data->packed_transaction = NULL;
- if (ret)
- goto cleanup;
-+ if (backend_data->packed_transaction) {
++ if (backend_data->packed_transaction) {
+ if (backend_data->packed_transaction_needed) {
+ ret = ref_transaction_commit(packed_transaction, err);
+ if (ret)
+ goto cleanup;
-+ /* TODO: leaks on error path. */
++
+ ref_transaction_free(packed_transaction);
+ packed_transaction = NULL;
+ backend_data->packed_transaction = NULL;
@@ refs/files-backend.c: static int files_initial_transaction_commit(struct ref_sto
ref_transaction_free(packed_transaction);

## refs/packed-backend.c ##
+@@ refs/packed-backend.c: static int write_packed_entry(FILE *fh, const char *refname,
+ return 0;
+ }
+
+-int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err) ++static int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)
+ {
+ struct packed_ref_store *refs =
+ packed_downcast(ref_store, REF_STORE_WRITE | REF_STORE_MAIN,
+@@ refs/packed-backend.c: int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)
+ return 0;
+ }
+
+-void packed_refs_unlock(struct ref_store *ref_store)
++static void packed_refs_unlock(struct ref_store *ref_store)
+ {
+ struct packed_ref_store *refs = packed_downcast(
+ ref_store,
+@@ refs/packed-backend.c: void packed_refs_unlock(struct ref_store *ref_store)
+ rollback_lock_file(&refs->lock);
+ }
+
+-int packed_refs_is_locked(struct ref_store *ref_store)
+-{
+- struct packed_ref_store *refs = packed_downcast(
+- ref_store,
+- REF_STORE_READ | REF_STORE_WRITE,
+- "packed_refs_is_locked");
+-
+- return is_lock_file_locked(&refs->lock);
+-}
+-
+ /*
+ * The packed-refs header line that we write out. Perhaps other traits
+ * will be added later.
@@ refs/packed-backend.c: int is_packed_transaction_needed(struct ref_store *ref_store,

struct packed_transaction_backend_data {
@@ refs/packed-backend.c: static void packed_transaction_cleanup(struct packed_ref_
transaction->state = REF_TRANSACTION_CLOSED;
}

-+static int packed_transaction_begin(struct ref_store *ref_store,
-+ struct ref_transaction *transaction,
+-
+ static struct ref_transaction *packed_transaction_begin(struct ref_store *ref_store,
+- struct strbuf *err) {
+- struct ref_transaction *tr;
+- CALLOC_ARRAY(tr, 1);
+- return tr;
+ struct strbuf *err)
+{
+ struct packed_ref_store *refs = packed_downcast(
@@ refs/packed-backend.c: static void packed_transaction_cleanup(struct packed_ref_
+ REF_STORE_READ | REF_STORE_WRITE | REF_STORE_ODB,
+ "ref_transaction_begin");
+ struct packed_transaction_backend_data *data;
-+
-+ CALLOC_ARRAY(data, 1);
-+ string_list_init_nodup(&data->updates);
++ struct ref_transaction *transaction;
+
+ if (!is_lock_file_locked(&refs->lock)) {
+ if (packed_refs_lock(ref_store, 0, err))
-+ /* todo: leaking data */
-+ return -1;
++ return NULL;
+ }
++ CALLOC_ARRAY(transaction, 1);
++ CALLOC_ARRAY(data, 1);
++ string_list_init_nodup(&data->updates);
+ transaction->backend_data = data;
-+ return 0;
-+}
-+
++ return transaction;
+ }
+
static int packed_transaction_prepare(struct ref_store *ref_store,
- struct ref_transaction *transaction,
- struct strbuf *err)
@@ refs/packed-backend.c: static int packed_transaction_prepare(struct ref_store *ref_store,
ref_store,
REF_STORE_READ | REF_STORE_WRITE | REF_STORE_ODB,
@@ refs/packed-backend.c: static int packed_transaction_prepare(struct ref_store *r
if (write_with_updates(refs, &data->updates, err))
goto failure;

-@@ refs/packed-backend.c: struct ref_storage_be refs_be_packed = {
- .name = "packed",
- .init = packed_ref_store_create,
- .init_db = packed_init_db,
-+ .transaction_begin = packed_transaction_begin,
- .transaction_prepare = packed_transaction_prepare,
- .transaction_finish = packed_transaction_finish,
- .transaction_abort = packed_transaction_abort,

## refs/packed-backend.h ##
@@ refs/packed-backend.h: struct ref_store *packed_ref_store_create(struct repository *repo,
@@ refs/packed-backend.h: struct ref_store *packed_ref_store_create(struct reposito
/*
* Return true if transaction really needs to be carried out against
* the specified packed_ref_store, or false if it can be skipped
-
- ## refs/refs-internal.h ##
-@@ refs/refs-internal.h: typedef struct ref_store *ref_store_init_fn(struct repository *repo, -
- typedef int ref_init_db_fn(struct ref_store *refs, struct strbuf *err);
-
-+typedef int ref_transaction_begin_fn(struct ref_store *refs,
-+ struct ref_transaction *transaction,
-+ struct strbuf *err);
-+
- typedef int ref_transaction_prepare_fn(struct ref_store *refs,
- struct ref_transaction *transaction,
- struct strbuf *err);
-@@ refs/refs-internal.h: struct ref_storage_be {
- ref_store_init_fn *init;
- ref_init_db_fn *init_db;
-
-+ ref_transaction_begin_fn *transaction_begin;
- ref_transaction_prepare_fn *transaction_prepare;
- ref_transaction_finish_fn *transaction_finish;
- ref_transaction_abort_fn *transaction_abort;
2: a5cb3adc662 ! 4: 0b8919b05c4 refs: move is_packed_transaction_needed out of packed-backend.c

     @@ refs/files-backend.c: out:
       	return ret;
       }
       
     -+
      +/*
      + * Return true if `transaction` really needs to be carried out against
      + * the specified packed_ref_store, or false if it can be skipped
     @@ refs/files-backend.c: out:
       struct files_transaction_backend_data {
       	struct ref_transaction *packed_transaction;
       	int packed_transaction_needed;
     -@@ refs/files-backend.c: struct ref_storage_be refs_be_files = {
     - 	.delete_reflog = files_delete_reflog,
     - 	.reflog_expire = files_reflog_expire
     - };
     -+
      
       ## refs/packed-backend.c ##
      @@ refs/packed-backend.c: error:
 3:  559c04cee99 ! 5:  d5669da57e3 refs: alternate reftable ref backend implementation
     @@ Commit message
          refs: alternate reftable ref backend implementation
      
          This introduces the reftable backend as an alternative to the packed
     -    backend. This simplifies the code, because we now longer have to worry
     -    about:
     +    backend.
     +
     +    This is an alternative to the approach which was explored in
     +    https://github.com/git/git/pull/1215/. This alternative is simpler,
     +    because we now longer have to worry about:
      
          - pseudorefs and the HEAD ref
          - worktrees
          - commands that blur together files and references (cherry-pick, rebase)
      
          This deviates from the spec that in
     -    Documentation/technical/reftable.txt. It might be possible to update
     -    the code such that all writes by default go to reftable directly. Then
     -    the result would be compatible with an implementation that writes only
     -    reftable (the reftable lock would still prevent races) relative to an
     -    implementation that disregards loose refs. Or,  JGit could be adapted
     -    to follow this implementation.
     +    Documentation/technical/reftable.txt. It might be possible to update the
     +    code such that all writes by default go to reftable directly. Then the
     +    result would be compatible with an implementation that writes only
     +    reftable (the reftable lock would still prevent races), but something
     +    must be done about the HEAD ref (which JGit keeps in reftable too.)
     +    Alternatively, JGit could be adapted to follow this implementation:
     +    despite the code being there for 4 years now, I haven't heard of anyone
     +    using it in production (exactly because CGit does not support it).
      
          For this incremental path, the reftable format is arguably more
          complex than necessary, as
      
          - packed-refs doesn't support symrefs
     -    - reflogs aren't moved into reftable/
     +    - reflogs aren't moved into reftable
      
          on the other hand, the code is already there, and it's well-structured
          and well-tested.
      
     -    This implementation is a prototype. To test, you need to do `export
     -    GIT_TEST_REFTABLE=1`. Doing so creates a handful of errors in the
     -    test-suite, most seemingly related to the new behavior of pack-refs
     -    (which creates a reftable/ dir and not a packed-refs file.), but it
     -    seems overseeable.
     +    refs/reftable-backend.c was created by cannibalizing the first version
     +    of reftable support (github PR 1215 as mentioned above). It supports
     +    reflogs and symrefs, even though those features are never exercised.
     +
     +    This implementation is a prototype, for the following reasons:
     +
     +    - no considerations of backward compatibility and configuring an
     +    extension
     +    - no support for converting between packed-refs and reftable
     +    - no documentation
     +    - test failures when setting GIT_TEST_REFTABLE=1.
      
          Signed-off-by: Han-Wen Nienhuys <[email protected]>
      
     @@ contrib/workdir/git-new-workdir: trap cleanup $siglist
       	case $x in
      
       ## refs/files-backend.c ##
     +@@
     + #include "../git-compat-util.h"
     ++#include "../abspath.h"
     + #include "../config.h"
     + #include "../copy.h"
     + #include "../environment.h"
      @@
       #include "refs-internal.h"
       #include "ref-cache.h"
     @@ refs/files-backend.c
       #include "../iterator.h"
       #include "../dir-iterator.h"
      @@ refs/files-backend.c: static struct ref_store *files_ref_store_create(struct repository *repo,
     + 	struct files_ref_store *refs = xcalloc(1, sizeof(*refs));
     + 	struct ref_store *ref_store = (struct ref_store *)refs;
     + 	struct strbuf sb = STRBUF_INIT;
     ++	int has_reftable, has_packed;
     + 
     + 	base_ref_store_init(ref_store, repo, gitdir, &refs_be_files);
       	refs->store_flags = flags;
       	get_common_dir_noenv(&sb, gitdir);
       	refs->gitcommondir = strbuf_detach(&sb, NULL);
     -+
     -+	/* TODO: should look at the repo to decide whether to use packed-refs or
     -+	 * reftable. */
     - 	refs->packed_ref_store =
     +-	refs->packed_ref_store =
      -		packed_ref_store_create(repo, refs->gitcommondir, flags);
     -+		git_env_bool("GIT_TEST_REFTABLE", 0)  
     ++
     ++	strbuf_addf(&sb, "%s/reftable", refs->gitcommondir);
     ++	has_reftable = is_directory(sb.buf);
     ++	strbuf_reset(&sb);
     ++	strbuf_addf(&sb, "%s/packed-refs", refs->gitcommondir);
     ++	has_packed = file_exists(sb.buf);
     ++
     ++	if (!has_packed && !has_reftable)
     ++		has_reftable = git_env_bool("GIT_TEST_REFTABLE", 0);
     ++
     ++	refs->packed_ref_store = has_reftable
      +		? git_reftable_ref_store_create(repo, refs->gitcommondir, flags)
      +		: packed_ref_store_create(repo, refs->gitcommondir, flags);
       
       	chdir_notify_reparent("files-backend $GIT_DIR", &refs->base.gitdir);
       	chdir_notify_reparent("files-backend $GIT_COMMONDIR",
      
     - ## refs/packed-backend.c ##
     -@@ refs/packed-backend.c: static int write_packed_entry(FILE *fh, const char *refname,
     - 	return 0;
     - }
     - 
     --int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)
     -+static int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)
     - {
     - 	struct packed_ref_store *refs =
     - 		packed_downcast(ref_store, REF_STORE_WRITE | REF_STORE_MAIN,
     -@@ refs/packed-backend.c: int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)
     - 	return 0;
     - }
     - 
     --void packed_refs_unlock(struct ref_store *ref_store)
     -+static void packed_refs_unlock(struct ref_store *ref_store)
     - {
     - 	struct packed_ref_store *refs = packed_downcast(
     - 			ref_store,
     -@@ refs/packed-backend.c: void packed_refs_unlock(struct ref_store *ref_store)
     - 	rollback_lock_file(&refs->lock);
     - }
     - 
     --int packed_refs_is_locked(struct ref_store *ref_store)
     --{
     --	struct packed_ref_store *refs = packed_downcast(
     --			ref_store,
     --			REF_STORE_READ | REF_STORE_WRITE,
     --			"packed_refs_is_locked");
     --
     --	return is_lock_file_locked(&refs->lock);
     --}
     --
     - /*
     -  * The packed-refs header line that we write out. Perhaps other traits
     -  * will be added later.
     -
       ## refs/refs-internal.h ##
      @@ refs/refs-internal.h: struct ref_storage_be {
       };
     @@ refs/reftable-backend.c (new)
      +#include "../worktree.h"
      +#include "refs-internal.h"
      +#include "reftable-backend.h"
     ++#include "../repository.h"
      +
      +extern struct ref_storage_be refs_be_reftable;
      +
     @@ refs/reftable-backend.c (new)
      +	return &ri->base;
      +}
      +
     -+static int fixup_symrefs(struct ref_store *ref_store,
     -+			 struct ref_transaction *transaction)
     -+{
     -+	struct strbuf referent = STRBUF_INIT;
     -+	int i = 0;
     -+	int err = 0;
     -+
     -+	for (i = 0; i < transaction->nr; i++) {
     -+		struct ref_update *update = transaction->updates[i];
     -+		struct object_id old_oid;
     -+		int failure_errno;
     -+
     -+		err = git_reftable_read_raw_ref(ref_store, update->refname,
     -+						&old_oid, &referent,
     -+						/* mutate input, like
     -+						   files-backend.c */
     -+						&update->type, &failure_errno);
     -+		if (err < 0 && failure_errno == ENOENT &&
     -+		    is_null_oid(&update->old_oid)) {
     -+			err = 0;
     -+		}
     -+		if (err < 0)
     -+			goto done;
     -+
     -+		if (!(update->type & REF_ISSYMREF))
     -+			continue;
     -+
     -+		if (update->flags & REF_NO_DEREF) {
     -+			/* what should happen here? See files-backend.c
     -+			 * lock_ref_for_update. */
     -+		} else {
     -+			/*
     -+			  If we are updating a symref (eg. HEAD), we should also
     -+			  update the branch that the symref points to.
     -+
     -+			  This is generic functionality, and would be better
     -+			  done in refs.c, but the current implementation is
     -+			  intertwined with the locking in files-backend.c.
     -+			*/
     -+			int new_flags = update->flags;
     -+			struct ref_update *new_update = NULL;
     -+
     -+			/* if this is an update for HEAD, should also record a
     -+			   log entry for HEAD? See files-backend.c,
     -+			   split_head_update()
     -+			*/
     -+			new_update = ref_transaction_add_update(
     -+				transaction, referent.buf, new_flags,
     -+				&update->new_oid, &update->old_oid,
     -+				update->msg);
     -+			new_update->parent_update = update;
     -+
     -+			/* files-backend sets REF_LOG_ONLY here. */
     -+			update->flags |= REF_NO_DEREF | REF_LOG_ONLY;
     -+			update->flags &= ~REF_HAVE_OLD;
     -+		}
     -+	}
     -+
     -+done:
     -+	assert(err != REFTABLE_API_ERROR);
     -+	strbuf_release(&referent);
     -+	return err;
     -+}
     -+
     -+static int git_reftable_transaction_prepare(struct ref_store *ref_store,
     -+					    struct ref_transaction *transaction,
     -+					    struct strbuf *errbuf)
     ++static struct ref_transaction *git_reftable_transaction_begin(struct ref_store *ref_store,
     ++							      struct strbuf *errbuf)
      +{
      +	struct git_reftable_ref_store *refs =
      +		(struct git_reftable_ref_store *)ref_store;
      +	struct reftable_addition *add = NULL;
     -+	struct reftable_stack *stack = stack_for(
     -+		refs,
     -+		transaction->nr ? transaction->updates[0]->refname : NULL);
     -+	int i;
     ++	struct ref_transaction *transaction = NULL;
     ++	struct reftable_stack *stack = refs->main_stack;
      +
      +	int err = refs->err;
      +	if (err < 0) {
     @@ refs/reftable-backend.c (new)
      +
      +	err = reftable_stack_new_addition(&add, stack);
      +	if (err) {
     ++		strbuf_addf(errbuf, "reftable: transaction begin: %s",
     ++			    reftable_error_str(err));
      +		goto done;
      +	}
      +
     -+	for (i = 0; i < transaction->nr; i++) {
     -+		struct ref_update *u = transaction->updates[i];
     -+		if ((u->flags & REF_HAVE_NEW) && !is_null_oid(&u->new_oid) &&
     -+		    !(u->flags & REF_SKIP_OID_VERIFICATION) &&
     -+		    !(u->flags & REF_LOG_ONLY)) {
     -+			struct object *o =
     -+				parse_object(refs->base.repo, &u->new_oid);
     -+			if (!o) {
     -+				strbuf_addf(
     -+					errbuf,
     -+					"trying to write ref '%s' with nonexistent object %s",
     -+					u->refname, oid_to_hex(&u->new_oid));
     -+				err = -1;
     -+				goto done;
     -+			}
     -+		}
     -+	}
     -+
     -+	err = fixup_symrefs(ref_store, transaction);
     -+	if (err) {
     -+		goto done;
     -+	}
     -+
     ++	CALLOC_ARRAY(transaction, 1);
      +	transaction->backend_data = add;
     -+	transaction->state = REF_TRANSACTION_PREPARED;
     -+
      +done:
     -+	assert(err != REFTABLE_API_ERROR);
     -+	if (err < 0) {
     -+		if (add) {
     -+			reftable_addition_destroy(add);
     -+			add = NULL;
     -+		}
     -+		transaction->state = REF_TRANSACTION_CLOSED;
     -+		if (!errbuf->len)
     -+			strbuf_addf(errbuf, "reftable: transaction prepare: %s",
     -+				    reftable_error_str(err));
     -+	}
     ++	return transaction;
     ++}
      +
     -+	return err;
     ++static int git_reftable_transaction_prepare(struct ref_store *ref_store,
     ++					    struct ref_transaction *transaction,
     ++					    struct strbuf *errbuf)
     ++{
     ++	transaction->state = REF_TRANSACTION_PREPARED;
     ++	return 0;
      +}
      +
      +static int git_reftable_transaction_abort(struct ref_store *ref_store,
     @@ refs/reftable-backend.c (new)
      +					   struct ref_transaction *transaction,
      +					   struct strbuf *errmsg)
      +{
     ++	struct git_reftable_ref_store *refs =
     ++		(struct git_reftable_ref_store *)transaction->ref_store;
      +	struct reftable_addition *add =
      +		(struct reftable_addition *)transaction->backend_data;
      +	int err = 0;
     @@ refs/reftable-backend.c (new)
      +
      +	err = reftable_addition_commit(add);
      +
     ++	if (!err)
     ++		err = reftable_stack_auto_compact(refs->main_stack);
      +done:
      +	assert(err != REFTABLE_API_ERROR);
      +	reftable_addition_destroy(add);
     @@ refs/reftable-backend.c (new)
      +	.name = "reftable",
      +	.init = git_reftable_ref_store_create,
      +	.init_db = git_reftable_init_db,
     ++	.transaction_begin = git_reftable_transaction_begin,
      +	.transaction_prepare = git_reftable_transaction_prepare,
      +	.transaction_finish = git_reftable_transaction_finish,
      +	.transaction_abort = git_reftable_transaction_abort,

-: ----------- > 6: 2cf743031ab refs: always try to do packed transactions for reftable

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

Take packed-refs.lock in the transaction_begin of the packed backend.

This decouples the files backend from the packed backend, allowing the latter to be swapped out by another ref backend.

---
 refs.c                |  5 ++-
 refs/files-backend.c  | 78 +++++++++++++++----------------------------
 refs/packed-backend.c | 55 ++++++++++++------------------
 refs/packed-backend.h | 10 ------
 4 files changed, 50 insertions(+), 98 deletions(-)

index f7ba3e56284..0611197dc6e 100644
@@ -2320,10 +2320,9 @@ int ref_transaction_abort(struct ref_transaction *transaction,
 	int ret = 0;
 
 	switch (transaction->state) {
-	case REF_TRANSACTION_OPEN:
-		/* No need to abort explicitly. */
-		break;
 	case REF_TRANSACTION_PREPARED:
+	case REF_TRANSACTION_OPEN:
+		/* an OPEN transactions may have a lock. */
 		ret = refs->be->transaction_abort(refs, transaction, err);
 		break;
 	case REF_TRANSACTION_CLOSED:

index 9dd8a344c34..ade3c8a5ac4 100644
@@ -17,16 +17,6 @@ struct ref_store *packed_ref_store_create(struct repository *repo,
 					  const char *gitdir,
 					  unsigned int store_flags);
 
-/*
- * Lock the packed-refs file for writing. Flags is passed to
- * hold_lock_file_for_update(). Return 0 on success. On errors, write
- * an error message to `err` and return a nonzero value.
- */
-int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err);
-
-void packed_refs_unlock(struct ref_store *ref_store);
-int packed_refs_is_locked(struct ref_store *ref_store);
-
 /*
  * Return true if `transaction` really needs to be carried out against
  * the specified packed_ref_store, or false if it can be skipped

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

It is no longer specific to the packed backend.

---
 refs/files-backend.c  | 94 ++++++++++++++++++++++++++++++++++++++++++
 refs/packed-backend.c | 95 -------------------------------------------
 refs/packed-backend.h |  9 ----
 3 files changed, 94 insertions(+), 104 deletions(-)

index 43c1882be3c..5d288bf38bb 100644
@@ -2630,6 +2630,100 @@ out:
 	return ret;
 }
 
+/*
+ * Return true if `transaction` really needs to be carried out against
+ * the specified packed_ref_store, or false if it can be skipped
+ * (i.e., because it is an obvious NOOP). `ref_store` must be locked
+ * before calling this function.
+ */
+static int is_packed_transaction_needed(struct ref_store *ref_store,
+				 struct ref_transaction *transaction)
+{
+	struct strbuf referent = STRBUF_INIT;
+	size_t i;
+	int ret;
+
+	/*
+	 * We're only going to bother returning false for the common,
+	 * trivial case that references are only being deleted, their
+	 * old values are not being checked, and the old `packed-refs`
+	 * file doesn't contain any of those reference(s). This gives
+	 * false positives for some other cases that could
+	 * theoretically be optimized away:
+	 *
+	 * 1. It could be that the old value is being verified without
+	 *    setting a new value. In this case, we could verify the
+	 *    old value here and skip the update if it agrees. If it
+	 *    disagrees, we could either let the update go through
+	 *    (the actual commit would re-detect and report the
+	 *    problem), or come up with a way of reporting such an
+	 *    error to *our* caller.
+	 *
+	 * 2. It could be that a new value is being set, but that it
+	 *    is identical to the current packed value of the
+	 *    reference.
+	 *
+	 * Neither of these cases will come up in the current code,
+	 * because the only caller of this function passes to it a
+	 * transaction that only includes `delete` updates with no
+	 * `old_id`. Even if that ever changes, false positives only
+	 * cause an optimization to be missed; they do not affect
+	 * correctness.
+	 */
+
+	/*
+	 * Start with the cheap checks that don't require old
+	 * reference values to be read:
+	 */
+	for (i = 0; i < transaction->nr; i++) {
+		struct ref_update *update = transaction->updates[i];
+
+		if (update->flags & REF_HAVE_OLD)
+			/* Have to check the old value -> needed. */
+			return 1;
+
+		if ((update->flags & REF_HAVE_NEW) && !is_null_oid(&update->new_oid))
+			/* Have to set a new value -> needed. */
+			return 1;
+	}
+
+	/*
+	 * The transaction isn't checking any old values nor is it
+	 * setting any nonzero new values, so it still might be able
+	 * to be skipped. Now do the more expensive check: the update
+	 * is needed if any of the updates is a delete, and the old
+	 * `packed-refs` file contains a value for that reference.
+	 */
+	ret = 0;
+	for (i = 0; i < transaction->nr; i++) {
+		struct ref_update *update = transaction->updates[i];
+		int failure_errno;
+		unsigned int type;
+		struct object_id oid;
+
+		if (!(update->flags & REF_HAVE_NEW))
+			/*
+			 * This reference isn't being deleted -> not
+			 * needed.
+			 */
+			continue;
+
+		if (!refs_read_raw_ref(ref_store, update->refname, &oid,
+				       &referent, &type, &failure_errno) ||
+		    failure_errno != ENOENT) {
+			/*
+			 * We have to actually delete that reference
+			 * -> this transaction is needed.
+			 */
+			ret = 1;
+			break;
+		}
+	}
+
+	strbuf_release(&referent);
+	return ret;
+}
+
 struct files_transaction_backend_data {
 	struct ref_transaction *packed_transaction;
 	int packed_transaction_needed;

index ade3c8a5ac4..51a3b6a332a 100644
@@ -17,13 +17,4 @@ struct ref_store *packed_ref_store_create(struct repository *repo,
 					  const char *gitdir,
 					  unsigned int store_flags);
 
-/*
- * Return true if `transaction` really needs to be carried out against
- * the specified packed_ref_store, or false if it can be skipped
- * (i.e., because it is an obvious NOOP). `ref_store` must be locked
- * before calling this function.
- */
-int is_packed_transaction_needed(struct ref_store *ref_store,
-				 struct ref_transaction *transaction);
-
 #endif /* REFS_PACKED_BACKEND_H */

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

Reftable updates are cheap (compared to packed-refs updates), so do them always. This also helps exercise this code more in tests.

This should commit should not be merged currently. It fails 55 tests when running with GIT_TEST_REFTABLE.

---
 refs/files-backend.c | 22 +++++++++++++++++-----
 1 file changed, 17 insertions(+), 5 deletions(-)

index 2cd596bbeba..0d61a18b4ba 100644
@@ -2800,6 +2800,7 @@ static int files_transaction_prepare(struct ref_store *ref_store,
 	int head_type;
 	struct files_transaction_backend_data *backend_data;
 	struct ref_transaction *packed_transaction = NULL;
+	int is_reftable = !strcmp(refs->packed_ref_store->be->name, "reftable");
 
 	assert(err);
 

@@ -2809,6 +2810,16 @@ static int files_transaction_prepare(struct ref_store *ref_store,
 	CALLOC_ARRAY(backend_data, 1);
 	transaction->backend_data = backend_data;
 
+	if (is_reftable) {
+		packed_transaction = ref_store_transaction_begin(
+			refs->packed_ref_store, err);
+		if (!packed_transaction) {
+			ret = TRANSACTION_GENERIC_ERROR;
+			goto cleanup;
+		}
+		backend_data->packed_transaction = packed_transaction;
+	}
+
 	/*
 	 * Fail if a refname appears more than once in the
 	 * transaction. (If we end up splitting up any updates using

@@ -2881,9 +2892,9 @@ static int files_transaction_prepare(struct ref_store *ref_store,
 		if (ret)
 			goto cleanup;
 
-		if (update->flags & REF_DELETING &&
-		    !(update->flags & REF_LOG_ONLY) &&
-		    !(update->flags & REF_IS_PRUNING)) {
+		if (is_reftable || (update->flags & REF_DELETING &&
+				    !(update->flags & REF_LOG_ONLY) &&
+				    !(update->flags & REF_IS_PRUNING))) {
 			/*
 			 * This reference has to be deleted from
 			 * packed-refs if it exists there.

@@ -2909,8 +2920,9 @@ static int files_transaction_prepare(struct ref_store *ref_store,
 	}
 
 	if (packed_transaction) {
-		backend_data->packed_transaction_needed = is_packed_transaction_needed(refs->packed_ref_store,
-										       packed_transaction);
+		backend_data->packed_transaction_needed = is_reftable ||
+			is_packed_transaction_needed(refs->packed_ref_store,
+						     packed_transaction);
 		if (backend_data->packed_transaction_needed) {
 			ret = ref_transaction_prepare(packed_transaction, err);
 			/*

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

This introduces the reftable backend as an alternative to the packed backend.

This is an alternative to the approach which was explored in
https://github.com/git/git/pull/1215/. This alternative is simpler, because we now longer have to worry about:

- pseudorefs and the HEAD ref
- worktrees
- commands that blur together files and references (cherry-pick, rebase)

This deviates from the spec that in Documentation/technical/reftable.txt. It might be possible to update the code such that all writes by default go to reftable directly. Then the result would be compatible with an implementation that writes only reftable (the reftable lock would still prevent races), but something must be done about the HEAD ref (which JGit keeps in reftable too.) Alternatively, JGit could be adapted to follow this implementation:
despite the code being there for 4 years now, I haven't heard of anyone using it in production (exactly because CGit does not support it).

For this incremental path, the reftable format is arguably more complex than necessary, as

- packed-refs doesn't support symrefs
- reflogs aren't moved into reftable

on the other hand, the code is already there, and it's well-structured and well-tested.

refs/reftable-backend.c was created by cannibalizing the first version of reftable support (github PR 1215 as mentioned above). It supports reflogs and symrefs, even though those features are never exercised.

This implementation is a prototype, for the following reasons:

- no considerations of backward compatibility and configuring an extension
- no support for converting between packed-refs and reftable
- no documentation
- test failures when setting GIT_TEST_REFTABLE=1.

---
 Makefile                        |    1 +
 config.mak.uname                |    2 +-
 contrib/workdir/git-new-workdir |    2 +-
 refs/files-backend.c            |   18 +-
 refs/refs-internal.h            |    1 +
 refs/reftable-backend.c         | 1658 +++++++++++++++++++++++++++++++
 refs/reftable-backend.h         |    8 +
 7 files changed, 1686 insertions(+), 4 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100644 refs/reftable-backend.h

index 57763093653..272d3f7f1e9 100644
@@ -1118,6 +1118,7 @@ LIB_OBJS += reflog.o
 LIB_OBJS += refs.o
 LIB_OBJS += refs/debug.o
 LIB_OBJS += refs/files-backend.o
+LIB_OBJS += refs/reftable-backend.o
 LIB_OBJS += refs/iterator.o
 LIB_OBJS += refs/packed-backend.o
 LIB_OBJS += refs/ref-cache.o

index 3bb03f423a0..843829c02fd 100644
@@ -743,7 +743,7 @@ vcxproj:
 
 	# Make .vcxproj files and add them
 	perl contrib/buildsystems/generate -g Vcxproj
-	git add -f git.sln {*,*/lib,t/helper/*}/*.vcxproj
+	git add -f git.sln {*,*/lib,*/libreftable,t/helper/*}/*.vcxproj
 
 	# Generate the LinkOrCopyBuiltins.targets and LinkOrCopyRemoteHttp.targets file
 	(echo '<Project xmlns="http://schemas.microsoft.com/developer/msbuild/2003">' && \

index 888c34a5215..989197aace0 100755
@@ -79,7 +79,7 @@ trap cleanup $siglist
 # create the links to the original repo.  explicitly exclude index, HEAD and
 # logs/HEAD from the list since they are purely related to the current working
 # directory, and should not be shared.
-for x in config refs logs/refs objects info hooks packed-refs remotes rr-cache svn
+for x in config refs logs/refs objects info hooks packed-refs remotes rr-cache svn reftable
 do
 	# create a containing directory if needed
 	case $x in

index 5d288bf38bb..2cd596bbeba 100644
@@ -1,4 +1,5 @@
 #include "../git-compat-util.h"
+#include "../abspath.h"
 #include "../config.h"
 #include "../copy.h"
 #include "../environment.h"

@@ -9,6 +10,7 @@
 #include "refs-internal.h"
 #include "ref-cache.h"
 #include "packed-backend.h"
+#include "reftable-backend.h"
 #include "../ident.h"
 #include "../iterator.h"
 #include "../dir-iterator.h"

@@ -98,13 +100,25 @@ static struct ref_store *files_ref_store_create(struct repository *repo,
 	struct files_ref_store *refs = xcalloc(1, sizeof(*refs));
 	struct ref_store *ref_store = (struct ref_store *)refs;
 	struct strbuf sb = STRBUF_INIT;
+	int has_reftable, has_packed;
 
 	base_ref_store_init(ref_store, repo, gitdir, &refs_be_files);
 	refs->store_flags = flags;
 	get_common_dir_noenv(&sb, gitdir);
 	refs->gitcommondir = strbuf_detach(&sb, NULL);
-	refs->packed_ref_store =
-		packed_ref_store_create(repo, refs->gitcommondir, flags);
+
+	strbuf_addf(&sb, "%s/reftable", refs->gitcommondir);
+	has_reftable = is_directory(sb.buf);
+	strbuf_reset(&sb);
+	strbuf_addf(&sb, "%s/packed-refs", refs->gitcommondir);
+	has_packed = file_exists(sb.buf);
+
+	if (!has_packed && !has_reftable)
+		has_reftable = git_env_bool("GIT_TEST_REFTABLE", 0);
+
+	refs->packed_ref_store = has_reftable
+		? git_reftable_ref_store_create(repo, refs->gitcommondir, flags)
+		: packed_ref_store_create(repo, refs->gitcommondir, flags);
 
 	chdir_notify_reparent("files-backend $GIT_DIR", &refs->base.gitdir);
 	chdir_notify_reparent("files-backend $GIT_COMMONDIR",

index 0a15e8a2ac8..13bd9c79f3c 100644
@@ -699,6 +699,7 @@ struct ref_storage_be {
 };
 
 extern struct ref_storage_be refs_be_files;
+extern struct ref_storage_be refs_be_reftable;
 extern struct ref_storage_be refs_be_packed;
 
 /*

new file mode 100644
index 00000000000..bf5fd42229a
@@ -0,0 +1,8 @@
+#ifndef REFS_REFTABLE_BACKEND_H
+#define REFS_REFTABLE_BACKEND_H
+
+struct ref_store *git_reftable_ref_store_create(struct repository *repo,
+						const char *gitdir,
+						unsigned int store_flags);
+
+#endif /* REFS_REFTABLE_BACKEND_H */

gitgitgadget

I've added this topic to the Contributor's summit such that the project can discuss what to do about the different proposals that exist around next-gen reference backends. If the conclusion is that reftables and this proposal here is still likely to land, then I'm happy to pick it up and try to get it upstreamed.

I'll have a look at this RFC early next week.

Thanks!

Patrick