This adds the reftable library, and hooks it up as a ref backend.
Feedback wanted:
* spots marked with XXX in the Git source code.
* how to write a unittest script? From the command-line, it works; inside
the test framework, it says:
fatal: could not open '/usr/local/google/home/hanwen/vc/git/t/trash directory.t0031-reftable/.git/refs/heads' for writing: Is a directory
ie. the files backend already initialized.
* what is a good test strategy? Could we have a CI flavor where we flip the
default to reftable, and see how it fares?
v6
* implement reflog expiry.
v7
* support SHA256 as version 2 of the format.
Han-Wen Nienhuys (5):
refs.h: clarify reflog iteration order
create .git/refs in files-backend.c
refs: document how ref_iterator_advance_fn should handle symrefs
Add reftable library
Reftable support for git-core
.../technical/repository-version.txt | 7 +
Makefile | 24 +-
builtin/clone.c | 4 +-
builtin/init-db.c | 57 +-
cache.h | 4 +-
refs.c | 20 +-
refs.h | 8 +-
refs/files-backend.c | 6 +
refs/refs-internal.h | 6 +
refs/reftable-backend.c | 971 +++++++++++++++
reftable/LICENSE | 31 +
reftable/README.md | 19 +
reftable/VERSION | 11 +
reftable/basics.c | 196 +++
reftable/basics.h | 37 +
reftable/block.c | 413 ++++++
reftable/block.h | 71 ++
reftable/blocksource.h | 20 +
reftable/bytes.c | 0
reftable/config.h | 1 +
reftable/constants.h | 25 +
reftable/dump.c | 97 ++
reftable/file.c | 97 ++
reftable/iter.c | 229 ++++
reftable/iter.h | 56 +
reftable/merged.c | 290 +++++
reftable/merged.h | 34 +
reftable/pq.c | 114 ++
reftable/pq.h | 34 +
reftable/reader.c | 718 +++++++++++
reftable/reader.h | 52 +
reftable/record.c | 1107 +++++++++++++++++
reftable/record.h | 79 ++
reftable/reftable.h | 405 ++++++
reftable/slice.c | 199 +++
reftable/slice.h | 39 +
reftable/stack.c | 984 +++++++++++++++
reftable/stack.h | 40 +
reftable/system.h | 59 +
reftable/tree.c | 66 +
reftable/tree.h | 24 +
reftable/writer.c | 630 ++++++++++
reftable/writer.h | 46 +
reftable/zlib-compat.c | 92 ++
repository.c | 2 +
repository.h | 3 +
setup.c | 12 +-
47 files changed, 7407 insertions(+), 32 deletions(-)
create mode 100644 refs/reftable-backend.c
create mode 100644 reftable/LICENSE
create mode 100644 reftable/README.md
create mode 100644 reftable/VERSION
create mode 100644 reftable/basics.c
create mode 100644 reftable/basics.h
create mode 100644 reftable/block.c
create mode 100644 reftable/block.h
create mode 100644 reftable/blocksource.h
create mode 100644 reftable/bytes.c
create mode 100644 reftable/config.h
create mode 100644 reftable/constants.h
create mode 100644 reftable/dump.c
create mode 100644 reftable/file.c
create mode 100644 reftable/iter.c
create mode 100644 reftable/iter.h
create mode 100644 reftable/merged.c
create mode 100644 reftable/merged.h
create mode 100644 reftable/pq.c
create mode 100644 reftable/pq.h
create mode 100644 reftable/reader.c
create mode 100644 reftable/reader.h
create mode 100644 reftable/record.c
create mode 100644 reftable/record.h
create mode 100644 reftable/reftable.h
create mode 100644 reftable/slice.c
create mode 100644 reftable/slice.h
create mode 100644 reftable/stack.c
create mode 100644 reftable/stack.h
create mode 100644 reftable/system.h
create mode 100644 reftable/tree.c
create mode 100644 reftable/tree.h
create mode 100644 reftable/writer.c
create mode 100644 reftable/writer.h
create mode 100644 reftable/zlib-compat.c
base-commit: e68e29171cc2d6968902e0654b5687fbe1ccb903
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-539%2Fhanwen%2Freftable-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-539/hanwen/reftable-v6
Pull-Request: https://github.com/gitgitgadget/git/pull/539
Range-diff vs v5:
1: c00403c94de = 1: e4b0773becd refs.h: clarify reflog iteration order
2: 4d6da9bc473 = 2: c25b6c601dc create .git/refs in files-backend.c
3: fbdcdccc885 = 3: e132e0f4e00 refs: document how ref_iterator_advance_fn should handle symrefs
4: 546b82fe798 ! 4: fe29a9db399 Add reftable library
@@ -86,7 +86,7 @@
+ cp reftable-repo/LICENSE reftable/ &&
+ git --git-dir reftable-repo/.git show --no-patch origin/master \
+ > reftable/VERSION && \
-+ echo '/* empty */' > reftable/config.h
++ sed -i~ 's|if REFTABLE_IN_GITCORE|if 1 /* REFTABLE_IN_GITCORE */|' reftable/system.h
+ rm reftable/*_test.c reftable/test_framework.*
+ git add reftable/*.[ch]
+
@@ -98,11 +98,17 @@
--- /dev/null
+++ b/reftable/VERSION
@@
-+commit 6115b50fdb9bc662be39b05f5589bc109282ae7f
++commit 42aa04f301a682197f0698867b9771b78ce4fdaf
+Author: Han-Wen Nienhuys <hanwen@google.com>
-+Date: Mon Feb 10 13:59:52 2020 +0100
-+
-+ README: add a note about the Java implementation
++Date: Mon Feb 17 16:05:22 2020 +0100
++
++ C: simplify system and config header handling
++
++ reftable.h only depends on <stdint.h>
++
++ system.h is only included from .c files. The git-core specific code is
++ guarded by a #if REFTABLE_IN_GITCORE, which we'll edit with a sed
++ script on the git-core side.
diff --git a/reftable/basics.c b/reftable/basics.c
new file mode 100644
@@ -485,19 +491,31 @@
+ if (block_writer_type(w) == BLOCK_TYPE_LOG) {
+ int block_header_skip = 4 + w->header_off;
+ struct slice compressed = {};
-+ uLongf dest_len = 0, src_len = 0;
-+ slice_resize(&compressed, w->next - block_header_skip);
++ int zresult = 0;
++ uLongf src_len = w->next - block_header_skip;
++ slice_resize(&compressed, src_len);
+
-+ dest_len = compressed.len;
-+ src_len = w->next - block_header_skip;
++ while (1) {
++ uLongf dest_len = compressed.len;
+
-+ if (Z_OK != compress2(compressed.buf, &dest_len,
-+ w->buf + block_header_skip, src_len, 9)) {
-+ free(slice_yield(&compressed));
-+ return ZLIB_ERROR;
++ zresult = compress2(compressed.buf, &dest_len,
++ w->buf + block_header_skip, src_len,
++ 9);
++ if (zresult == Z_BUF_ERROR) {
++ slice_resize(&compressed, 2 * compressed.len);
++ continue;
++ }
++
++ if (Z_OK != zresult) {
++ free(slice_yield(&compressed));
++ return ZLIB_ERROR;
++ }
++
++ memcpy(w->buf + block_header_skip, compressed.buf,
++ dest_len);
++ w->next = dest_len + block_header_skip;
++ break;
+ }
-+ memcpy(w->buf + block_header_skip, compressed.buf, dest_len);
-+ w->next = dest_len + block_header_skip;
+ }
+ return w->next;
+}
@@ -885,8 +903,6 @@
+#ifndef CONSTANTS_H
+#define CONSTANTS_H
+
-+#define SHA1_SIZE 20
-+#define SHA256_SIZE 32
+#define VERSION 1
+#define HEADER_SIZE 24
+#define FOOTER_SIZE 68
@@ -1555,13 +1571,17 @@
+ it->ops = &merged_iter_vtable;
+}
+
-+int new_merged_table(struct merged_table **dest, struct reader **stack, int n)
++int new_merged_table(struct merged_table **dest, struct reader **stack, int n,
++ int hash_size)
+{
+ uint64_t last_max = 0;
+ uint64_t first_min = 0;
+ int i = 0;
+ for (i = 0; i < n; i++) {
+ struct reader *r = stack[i];
++ if (reader_hash_size(r) != hash_size) {
++ return FORMAT_ERROR;
++ }
+ if (i > 0 && last_max >= reader_min_update_index(r)) {
+ return FORMAT_ERROR;
+ }
@@ -1578,7 +1598,7 @@
+ .stack_len = n,
+ .min = first_min,
+ .max = last_max,
-+ .hash_size = SHA1_SIZE,
++ .hash_size = hash_size,
+ };
+
+ *dest = calloc(sizeof(struct merged_table), 1);
@@ -1985,6 +2005,11 @@
+ block_source_return_block(r->source, p);
+}
+
++int reader_hash_size(struct reader *r)
++{
++ return r->hash_size;
++}
++
+const char *reader_name(struct reader *r)
+{
+ return r->name;
@@ -2005,8 +2030,13 @@
+ goto exit;
+ }
+
++ r->hash_size = SHA1_SIZE;
+ {
+ byte version = *f++;
++ if (version == 2) {
++ r->hash_size = SHA256_SIZE;
++ version = 1;
++ }
+ if (version != 1) {
+ err = FORMAT_ERROR;
+ goto exit;
@@ -2070,7 +2100,7 @@
+ r->size = block_source_size(source) - FOOTER_SIZE;
+ r->source = source;
+ r->name = strdup(name);
-+ r->hash_size = SHA1_SIZE;
++ r->hash_size = 0;
+
+ err = block_source_read_block(source, &footer, r->size, FOOTER_SIZE);
+ if (err != FOOTER_SIZE) {
@@ -3883,7 +3913,7 @@
+#ifndef REFTABLE_H
+#define REFTABLE_H
+
-+#include "system.h"
++#include <stdint.h>
+
+/* block_source is a generic wrapper for a seekable readable file.
+ It is generally passed around by value.
@@ -3934,6 +3964,10 @@
+
+ /* how often to write complete keys in each block. */
+ int restart_interval;
++
++ /* width of the hash. Should be 20 for SHA1 or 32 for SHA256. Defaults
++ * to SHA1 if unset */
++ int hash_size;
+};
+
+/* ref_record holds a ref database entry target_value */
@@ -4147,6 +4181,9 @@
+ */
+int reader_seek_ref(struct reader *r, struct iterator *it, const char *name);
+
++/* returns the hash size used in this table. */
++int reader_hash_size(struct reader *r);
++
+/* seek to logs for the given name, older than update_index. */
+int reader_seek_log_at(struct reader *r, struct iterator *it, const char *name,
+ uint64_t update_index);
@@ -4173,7 +4210,11 @@
+/* new_merged_table creates a new merged table. It takes ownership of the stack
+ array.
+*/
-+int new_merged_table(struct merged_table **dest, struct reader **stack, int n);
++int new_merged_table(struct merged_table **dest, struct reader **stack, int n,
++ int hash_size);
++
++/* returns the hash size used in this merged table. */
++int merged_hash_size(struct merged_table *mt);
+
+/* returns an iterator positioned just before 'name' */
+int merged_table_seek_ref(struct merged_table *mt, struct iterator *it,
@@ -4688,7 +4729,8 @@
+ }
+
+ /* success! */
-+ err = new_merged_table(&new_merged, new_tables, new_tables_len);
++ err = new_merged_table(&new_merged, new_tables, new_tables_len,
++ st->config.hash_size);
+ if (err < 0) {
+ goto exit;
+ }
@@ -5084,7 +5126,7 @@
+ writer_set_limits(wr, st->merged->stack[first]->min_update_index,
+ st->merged->stack[last]->max_update_index);
+
-+ err = new_merged_table(&mt, subtabs, subtabs_len);
++ err = new_merged_table(&mt, subtabs, subtabs_len, st->config.hash_size);
+ if (err < 0) {
+ free(subtabs);
+ goto exit;
@@ -5568,9 +5610,7 @@
+#ifndef SYSTEM_H
+#define SYSTEM_H
+
-+#include "config.h"
-+
-+#ifndef REFTABLE_STANDALONE
++#if 1 /* REFTABLE_IN_GITCORE */
+
+#include "git-compat-util.h"
+#include <zlib.h>
@@ -5606,7 +5646,7 @@
+ memcpy(&a, &b, sizeof(a)); \
+ memcpy(&b, &tmp[0], sizeof(a)); \
+ }
-+#endif
++#endif /* REFTABLE_IN_GITCORE */
+
+typedef uint8_t byte;
+typedef int bool;
@@ -5614,6 +5654,9 @@
+int uncompress_return_consumed(Bytef *dest, uLongf *destLen,
+ const Bytef *source, uLong *sourceLen);
+
++#define SHA1_SIZE 20
++#define SHA256_SIZE 32
++
+#endif
diff --git a/reftable/tree.c b/reftable/tree.c
@@ -5788,6 +5831,9 @@
+ opts->restart_interval = 16;
+ }
+
++ if (opts->hash_size == 0) {
++ opts->hash_size = SHA1_SIZE;
++ }
+ if (opts->block_size == 0) {
+ opts->block_size = DEFAULT_BLOCK_SIZE;
+ }
@@ -5796,7 +5842,8 @@
+static int writer_write_header(struct writer *w, byte *dest)
+{
+ memcpy((char *)dest, "REFT", 4);
-+ dest[4] = 1; /* version */
++ dest[4] = (w->hash_size == SHA1_SIZE) ? 1 : 2; /* version */
++
+ put_u24(dest + 5, w->opts.block_size);
+ put_u64(dest + 8, w->min_update_index);
+ put_u64(dest + 16, w->max_update_index);
@@ -5825,7 +5872,7 @@
+ /* TODO - error return? */
+ abort();
+ }
-+ wp->hash_size = SHA1_SIZE;
++ wp->hash_size = opts->hash_size;
+ wp->block = calloc(opts->block_size, 1);
+ wp->write = writer_func;
+ wp->write_arg = writer_arg;
@@ -6222,7 +6269,10 @@
+ byte footer[68];
+ byte *p = footer;
+
-+ writer_finish_public_section(w);
++ int err = writer_finish_public_section(w);
++ if (err != 0) {
++ return err;
++ }
+
+ writer_write_header(w, footer);
+ p += 24;
5: 702fb89871e ! 5: 8d95ab52f75 Reftable support for git-core
@@ -6,10 +6,8 @@
TODO:
- * Make CI on gitgitgadget compile.
- * Redo interaction between repo config, repo storage version
- * Resolve the design problem with reflog expiry.
* Resolve spots marked with XXX
+ * Test strategy?
Example use:
@@ -411,11 +409,6 @@ $^
+
+#include "../reftable/reftable.h"
+
-+/*
-+ The reftable v1 spec only supports 20-byte binary SHA1s. A new format version
-+ will be needed to support SHA256.
-+ */
-+
+extern struct ref_storage_be refs_be_reftable;
+
+struct reftable_ref_store {
@@ -470,6 +463,7 @@ $^
+ struct ref_store *ref_store = (struct ref_store *)refs;
+ struct write_options cfg = {
+ .block_size = 4096,
++ .hash_size = the_hash_algo->rawsz,
+ };
+ struct strbuf sb = STRBUF_INIT;
+
@@ -676,6 +670,7 @@ $^
+ (struct reftable_ref_store *)transaction->ref_store;
+ uint64_t ts = stack_next_update_index(refs->stack);
+ int err = 0;
++ struct log_record *logs = calloc(transaction->nr, sizeof(*logs));
+ struct ref_update **sorted =
+ malloc(transaction->nr * sizeof(struct ref_update *));
+ COPY_ARRAY(sorted, transaction->updates, transaction->nr);
@@ -695,6 +690,14 @@ $^
+
+ for (int i = 0; i < transaction->nr; i++) {
+ struct ref_update *u = sorted[i];
++ struct log_record *log = &logs[i];
++ fill_log_record(log);
++ log->ref_name = (char *)u->refname;
++ log->old_hash = u->old_oid.hash;
++ log->new_hash = u->new_oid.hash;
++ log->update_index = ts;
++ log->message = u->msg;
++
+ if (u->flags & REF_HAVE_NEW) {
+ struct object_id out_oid = {};
+ int out_flags = 0;
@@ -706,6 +709,7 @@ $^
+ struct ref_record ref = {};
+ ref.ref_name =
+ (char *)(resolved ? resolved : u->refname);
++ log->ref_name = ref.ref_name;
+ ref.value = u->new_oid.hash;
+ ref.update_index = ts;
+ err = writer_add_ref(writer, &ref);
@@ -716,23 +720,15 @@ $^
+ }
+
+ for (int i = 0; i < transaction->nr; i++) {
-+ struct ref_update *u = sorted[i];
-+ struct log_record log = {};
-+ fill_log_record(&log);
-+
-+ log.ref_name = (char *)u->refname;
-+ log.old_hash = u->old_oid.hash;
-+ log.new_hash = u->new_oid.hash;
-+ log.update_index = ts;
-+ log.message = u->msg;
-+
-+ err = writer_add_log(writer, &log);
-+ clear_log_record(&log);
++ err = writer_add_log(writer, &logs[i]);
++ clear_log_record(&logs[i]);
+ if (err < 0) {
-+ return err;
++ goto exit;
+ }
+ }
++
+exit:
++ free(logs);
+ free(sorted);
+ return err;
+}
@@ -1076,7 +1072,7 @@ $^
+ 1);
+ ri->base.oid = &ri->oid;
+
-+ return empty_ref_iterator_begin();
++ return (struct ref_iterator *)ri;
+}
+
+static int
@@ -1214,6 +1210,53 @@ $^
+ return 0;
+}
+
++struct reflog_expiry_arg {
++ struct reftable_ref_store *refs;
++ struct log_record *tombstones;
++ int len;
++ int cap;
++};
++
++static void clear_log_tombstones(struct reflog_expiry_arg *arg)
++{
++ int i = 0;
++ for (; i < arg->len; i++) {
++ log_record_clear(&arg->tombstones[i]);
++ }
++
++ FREE_AND_NULL(arg->tombstones);
++}
++
++static void add_log_tombstone(struct reflog_expiry_arg *arg,
++ const char *refname, uint64_t ts)
++{
++ struct log_record tombstone = {
++ .ref_name = xstrdup(refname),
++ .update_index = ts,
++ };
++ if (arg->len == arg->cap) {
++ arg->cap = 2 * arg->cap + 1;
++ arg->tombstones =
++ realloc(arg->tombstones, arg->cap * sizeof(tombstone));
++ }
++ arg->tombstones[arg->len++] = tombstone;
++}
++
++static int write_reflog_expiry_table(struct writer *writer, void *argv)
++{
++ struct reflog_expiry_arg *arg = (struct reflog_expiry_arg *)argv;
++ uint64_t ts = stack_next_update_index(arg->refs->stack);
++ int i = 0;
++ writer_set_limits(writer, ts, ts);
++ for (i = 0; i < arg->len; i++) {
++ int err = writer_add_log(writer, &arg->tombstones[i]);
++ if (err) {
++ return err;
++ }
++ }
++ return 0;
++}
++
+static int reftable_reflog_expire(struct ref_store *ref_store,
+ const char *refname,
+ const struct object_id *oid,
@@ -1223,11 +1266,57 @@ $^
+ reflog_expiry_cleanup_fn cleanup_fn,
+ void *policy_cb_data)
+{
-+ BUG("per ref reflog expiry is not implemented for reftable backend.");
+ /*
-+ TODO: should iterate over the reflog, and write tombstones. The
-+ tombstones will be removed on compaction.
-+ */
++ For log expiry, we write tombstones in place of the expired entries,
++ This means that the entries are still retrievable by delving into the
++ stack, and expiring entries paradoxically takes extra memory.
++
++ This memory is only reclaimed when some operation issues a
++ reftable_pack_refs(), which will compact the entire stack and get rid
++ of deletion entries.
++
++ It would be better if the refs backend supported an API that sets a
++ criterion for all refs, passing the criterion to pack_refs().
++ */
++ struct reftable_ref_store *refs =
++ (struct reftable_ref_store *)ref_store;
++ struct merged_table *mt = stack_merged_table(refs->stack);
++ struct reflog_expiry_arg arg = {
++ .refs = refs,
++ };
++ struct log_record log = {};
++ struct iterator it = {};
++ int err = merged_table_seek_log(mt, &it, refname);
++ if (err < 0) {
++ return err;
++ }
++
++ while (1) {
++ struct object_id ooid = {};
++ struct object_id noid = {};
++
++ int err = iterator_next_log(it, &log);
++ if (err < 0) {
++ return err;
++ }
++
++ if (err > 0 || strcmp(log.ref_name, refname)) {
++ break;
++ }
++ hashcpy(ooid.hash, log.old_hash);
++ hashcpy(noid.hash, log.new_hash);
++
++ if (should_prune_fn(&ooid, &noid, log.email,
++ (timestamp_t)log.time, log.tz_offset,
++ log.message, policy_cb_data)) {
++ add_log_tombstone(&arg, refname, log.update_index);
++ }
++ }
++ log_record_clear(&log);
++ iterator_destroy(&it);
++ err = stack_add(refs->stack, &write_reflog_expiry_table, &arg);
++ clear_log_tombstones(&arg);
++ return err;
+}
+
+static int reftable_read_raw_ref(struct ref_store *ref_store,Han-Wen Nienhuys via GitGitGadget <gitgitgadget@gmail.com>