Reftable support git-core

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

Reftable is a format for storing the ref database. Its rationale and specification is in the preceding commit.

This imports the upstream library as one big commit. For understanding the code, it is suggested to read the code in the following order:

* The specification under Documentation/technical/reftable.txt

* reftable.h - the public API

* record.{c,h} - reading and writing records

* block.{c,h} - reading and writing blocks.

* writer.{c,h} - writing a complete reftable file.

* merged.{c,h} and pq.{c,h} - reading a stack of reftables

* stack.{c,h} - writing and compacting stacks of reftable on the filesystem.

---
 reftable/LICENSE       |   31 ++
 reftable/README.md     |   11 +
 reftable/VERSION       |    5 +
 reftable/basics.c      |  209 ++++++++
 reftable/basics.h      |   53 ++
 reftable/block.c       |  425 +++++++++++++++
 reftable/block.h       |  124 +++++
 reftable/blocksource.h |   22 +
 reftable/bytes.c       |    0
 reftable/config.h      |    1 +
 reftable/constants.h   |   21 +
 reftable/dump.c        |   97 ++++
 reftable/file.c        |   98 ++++
 reftable/iter.c        |  234 ++++++++
 reftable/iter.h        |   60 +++
 reftable/merged.c      |  327 ++++++++++++
 reftable/merged.h      |   36 ++
 reftable/pq.c          |  115 ++++
 reftable/pq.h          |   34 ++
 reftable/reader.c      |  754 ++++++++++++++++++++++++++
 reftable/reader.h      |   68 +++
 reftable/record.c      | 1126 +++++++++++++++++++++++++++++++++++++++
 reftable/record.h      |  121 +++++
 reftable/reftable.h    |  527 ++++++++++++++++++
 reftable/slice.c       |  224 ++++++++
 reftable/slice.h       |   76 +++
 reftable/stack.c       | 1151 ++++++++++++++++++++++++++++++++++++++++
 reftable/stack.h       |   44 ++
 reftable/system.h      |   53 ++
 reftable/tree.c        |   67 +++
 reftable/tree.h        |   34 ++
 reftable/update.sh     |   23 +
 reftable/writer.c      |  661 +++++++++++++++++++++++
 reftable/writer.h      |   60 +++
 reftable/zlib-compat.c |   92 ++++
 35 files changed, 6984 insertions(+)
 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 100755 reftable/update.sh
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 reftable/zlib-compat.c

new file mode 100644
index 00000000000..402e0f9356b
@@ -0,0 +1,31 @@
+BSD License
+
+Copyright (c) 2020, Google LLC
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+* Redistributions of source code must retain the above copyright notice,
+this list of conditions and the following disclaimer.
+
+* Redistributions in binary form must reproduce the above copyright
+notice, this list of conditions and the following disclaimer in the
+documentation and/or other materials provided with the distribution.
+
+* Neither the name of Google LLC nor the names of its contributors may
+be used to endorse or promote products derived from this software
+without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

new file mode 100644
index 00000000000..21500563fd4
@@ -0,0 +1,11 @@
+
+The source code in this directory comes from https://github.com/google/reftable.
+
+The VERSION file keeps track of the current version of the reftable library.
+
+To update the library, do:
+
+   sh reftable/update.sh
+
+Bugfixes should be accompanied by a test and applied to upstream project at
+https://github.com/google/reftable.

new file mode 100644
index 00000000000..5d6fb5d9130
@@ -0,0 +1,5 @@
+commit a6d6b31bea256044621d789df64a8159647f21bc
+Author: Han-Wen Nienhuys <[email protected]>
+Date:   Mon Apr 27 20:46:21 2020 +0200
+
+    C: prefix error codes with REFTABLE_

new file mode 100644
index 00000000000..1fdf0bf4557
@@ -0,0 +1,22 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef BLOCKSOURCE_H
+#define BLOCKSOURCE_H
+
+#include "reftable.h"
+
+uint64_t block_source_size(struct reftable_block_source source);
+int block_source_read_block(struct reftable_block_source source,
+			    struct reftable_block *dest, uint64_t off,
+			    uint32_t size);
+void block_source_return_block(struct reftable_block_source source,
+			       struct reftable_block *ret);
+void block_source_close(struct reftable_block_source source);
+
+#endif

new file mode 100644
index 00000000000..e69de29bb2d

new file mode 100644
index 00000000000..40a8c178f10
@@ -0,0 +1 @@
+/* empty */

new file mode 100644
index 00000000000..5eee72c4c11
@@ -0,0 +1,21 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef CONSTANTS_H
+#define CONSTANTS_H
+
+#define BLOCK_TYPE_LOG 'g'
+#define BLOCK_TYPE_INDEX 'i'
+#define BLOCK_TYPE_REF 'r'
+#define BLOCK_TYPE_OBJ 'o'
+#define BLOCK_TYPE_ANY 0
+
+#define MAX_RESTARTS ((1 << 16) - 1)
+#define DEFAULT_BLOCK_SIZE 4096
+
+#endif

new file mode 100644
index 00000000000..d6e1a72733e
@@ -0,0 +1,36 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef MERGED_H
+#define MERGED_H
+
+#include "pq.h"
+#include "reftable.h"
+
+struct reftable_merged_table {
+	struct reftable_reader **stack;
+	int stack_len;
+	uint32_t hash_id;
+	bool suppress_deletions;
+
+	uint64_t min;
+	uint64_t max;
+};
+
+struct merged_iter {
+	struct reftable_iterator *stack;
+	uint32_t hash_id;
+	int stack_len;
+	byte typ;
+	bool suppress_deletions;
+	struct merged_iter_pqueue pq;
+};
+
+void merged_table_clear(struct reftable_merged_table *mt);
+
+#endif

new file mode 100644
index 00000000000..b585a52ee14
@@ -0,0 +1,34 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef PQ_H
+#define PQ_H
+
+#include "record.h"
+
+struct pq_entry {
+	int index;
+	struct record rec;
+};
+
+int pq_less(struct pq_entry a, struct pq_entry b);
+
+struct merged_iter_pqueue {
+	struct pq_entry *heap;
+	int len;
+	int cap;
+};
+
+struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);
+bool merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);
+void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
+struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e);
+void merged_iter_pqueue_clear(struct merged_iter_pqueue *pq);
+
+#endif

new file mode 100644
index 00000000000..954512e9a3a

new file mode 100755
index 00000000000..c37776c573f

gitgitgadget

Part of the diff is not shown here. View the raw message.

On 2020-04-27 20:13:35+0000, Han-Wen Nienhuys via GitGitGadget <[email protected]> wrote:
[..snip..]

	out[2] = (byte)( (i)(&0xff) )

[..snip..]

[..snip..]

[..snip..]

Danh

Wrong. A program (e.g. "git") can have various parts, some of which is licensed under GPL, some other parts under BSD, yet some other parts under LGPL. Read the second paragraph of README we ship without source.

I think you are thinking about the obligation a distributor of the linked binary compiled from such source has, which is that they need to make available not just the GPL part but the rest of the program used to compile the whole, including parts licensed under BSD and other licenses.

without --> with our

;-)

The reftable is structured as a library. The declaration for 'byte', as well as 'bool' is private to the library.

I removed the parens here, in
https://github.com/google/reftable/commit/6f883714588d2658122fefd85a2e2e76401ae2be

that also changes a number of 'int's to 'size_t's.

would you have a concrete suggestion to rewrite this? The rules for undefined behavior and integer casts are subtle, and I know they are a cause of concern in crypto code, and I'd rather be correct than rely on deep knowledge of the C standard.

fixed this.

Review style

there is precedent for this to be called binary search. See for example, https://golang.org/pkg/sort/#Search

The record structure contains two pointers.

I can't parse this sentence.

For uniformity all functions taking a struct Xyz* as the first argument are called

xyz_do_something

since this takes a block_writer, and it registers a restart, it is called block_writer_register_restart. The naming of this is uniform throughout the library.

good point, I'll look into this again.

Pleased to make your acquaintance!

fixed this.

I'm sorry, gcc -std=c89 said this was OK.

moved comment to header file.

No. 2^24-1 is the maximum size, as detailed in the specification.

thanks, I've removed these.

Removed

This was moved to a different directory in upstream; I've removed it now.

I've added a doc comment.

I don't understand your criticism; could you be more precise?

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, Halimah DeLaine Prado

I've pushed these fixes to
https://github.com/gitgitgadget/git/pull/539. Should I be sending new patches over email for each review round?

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, Halimah DeLaine Prado

As an outsider to this part of the codebase, a little more explanation could be handy in the commit message. I found the backends you mentioned in refs, and it seems like they're the only two, but it's not obvious how this delta is related to those backends. Furthermore, grepping looks like this function whose behavior is changing is being called from somewhere else, with no change to that function (and it looks like the callsite's callback doesn't check whether a ref begins with refs/ or not).

All this to say - it's hard to convince myself this is a safe change, and I'd really like to read more to understand why you made it.

Other current backend being the files-backend, which creates it below, isn't this a no-op at this stage?

What's more interesting is what would happen when a repo is initialized with the reftable backend as its sole backend.

Even then, the repository discovery code of existing versions of Git needs to see a directory with a ".git" subdirectory, in the latter of which there must be HEAD and objects and refs subdirectories, so we'd need to create refs/ directory even if reftable does not use it.

This step, from that point of view, may not be necessary. But as long as we make sure any repository creates refs/ and objects/ directories, regardless of the ref backend, we'd be OK.

I'll be the first to admit that I'm on shaky ground here. However, given that the test suite passes, if this is breaking some behavior, it's probably not very well tested behavior.

Here is what I know:

Git stores refs in multiple places:
- normal refs, packed: .git/packed-refs
- normal refs, loose: under refs/*/
- special refs: HEAD, ORIG_HEAD, REBASE_HEAD.

Currently, the special refs can only be read with refs_read_raw_ref(). If you iterate over the refs in the files/packed backend, you can never find HEAD, ORIG_HEAD etc.

Reftable does not have different classes of ref storage, so this means that the whole space of refs (including HEAD) is managed by the reftable backend, and if you iterate over the refs, reftable will also produce HEAD. This is not spelled out in the spec, but JGit actually stores HEAD in reftable too, and we want to be interoperable.

Without this patch, commands like "git show-ref" will produce an entry "HEAD", which is a regression.

With this patch, the default iteration is limited to the "refs/" prefix, so we don't produce HEAD in the reftable backend by default.

Now, I have several questions:

* how does this interact with worktrees? It seems that there is a special worktree namespace?
* if you are doing a rebase, and have unreachable objects in ORIG_HEAD, REBASE_HEAD, how does git-gc ensure that these objects stay alive? I'd think that you need to iterate over all entries (including REBASE_HEAD and friends), but I haven't been able to understand how that works.

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, Halimah DeLaine Prado

I've dropped this patch from the series; it probably was from before the compat hack that is described in

https://git.eclipse.org/r/#/c/157167/

for further clarification: reftable doesn't used the refs/ dir at all, but we still want to not confuse older git versions.

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, Halimah DeLaine Prado

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

---
 refs.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

index a92d2c74c83..9421c5b8465 100644
@@ -432,18 +432,21 @@ int delete_refs(const char *msg, struct string_list *refnames,
 int refs_delete_reflog(struct ref_store *refs, const char *refname);
 int delete_reflog(const char *refname);
 
-/* iterate over reflog entries */
+/* Iterate over reflog entries. */
 typedef int each_reflog_ent_fn(
 		struct object_id *old_oid, struct object_id *new_oid,
 		const char *committer, timestamp_t timestamp,
 		int tz, const char *msg, void *cb_data);
 
+/* Iterate in over reflog entries, oldest entry first. */
 int refs_for_each_reflog_ent(struct ref_store *refs, const char *refname,
 			     each_reflog_ent_fn fn, void *cb_data);
 int refs_for_each_reflog_ent_reverse(struct ref_store *refs,
 				     const char *refname,
 				     each_reflog_ent_fn fn,
 				     void *cb_data);
+
+/* Call a function for each reflog entry, oldest entry first. */
 int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_data);
 int for_each_reflog_ent_reverse(const char *refname, each_reflog_ent_fn fn, void *cb_data);
 

gitgitgadget

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

This happens implicitly in the files/packed ref backend; making it explicit simplifies adding alternate ref storage backends, such as reftable.

---
 refs.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

index 224ff66c7bb..4db27379661 100644
@@ -1525,7 +1525,7 @@ static int do_for_each_ref(struct ref_store *refs, const char *prefix,
 
 int refs_for_each_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref(refs, "", fn, 0, 0, cb_data);
+	return do_for_each_ref(refs, "refs/", fn, 0, 0, cb_data);
 }
 
 int for_each_ref(each_ref_fn fn, void *cb_data)

@@ -1585,8 +1585,8 @@ int for_each_namespaced_ref(each_ref_fn fn, void *cb_data)
 
 int refs_for_each_rawref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref(refs, "", fn, 0,
-			       DO_FOR_EACH_INCLUDE_BROKEN, cb_data);
+	return do_for_each_ref(refs, "refs/", fn, 0, DO_FOR_EACH_INCLUDE_BROKEN,
+			       cb_data);
 }
 
 int for_each_rawref(each_ref_fn fn, void *cb_data)

gitgitgadget

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

---
 reftable/.gitattributes | 1 +
 1 file changed, 1 insertion(+)
 create mode 100644 reftable/.gitattributes

new file mode 100644
index 00000000000..f44451a3795
@@ -0,0 +1 @@
+/zlib-compat.c	whitespace=-indent-with-non-tab,-trailing-space

gitgitgadget

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

---
 Documentation/technical/reftable.txt | 50 ++++++++++++++++------------
 1 file changed, 28 insertions(+), 22 deletions(-)

index 9fa4657d9ff..ee3f36ea851 100644
@@ -193,8 +193,8 @@ and non-aligned files.
 Very small files (e.g. 1 only ref block) may omit `padding` and the ref
 index to reduce total file size.
 
-Header
-^^^^^^
+Header (version 1)
+^^^^^^^^^^^^^^^^^^
 
 A 24-byte header appears at the beginning of the file:
 

@@ -215,6 +215,24 @@ used in a stack for link:#Update-transactions[transactions], these
 fields can order the files such that the prior file’s
 `max_update_index + 1` is the next file’s `min_update_index`.
 
+Header (version 2)
+^^^^^^^^^^^^^^^^^^
+
+A 28-byte header appears at the beginning of the file:
+
+....
+'REFT'
+uint8( version_number = 1 )
+uint24( block_size )
+uint64( min_update_index )
+uint64( max_update_index )
+uint32( hash_id )
+....
+
+The header is identical to `version_number=1`, with the 4-byte hash ID
+("sha1" for SHA1 and "s256" for SHA-256) append to the header.
+
+
 First ref block
 ^^^^^^^^^^^^^^^
 

@@ -671,14 +689,8 @@ Footer
 After the last block of the file, a file footer is written. It begins
 like the file header, but is extended with additional data.
 
-A 68-byte footer appears at the end:
-
 ....
-    'REFT'
-    uint8( version_number = 1 )
-    uint24( block_size )
-    uint64( min_update_index )
-    uint64( max_update_index )
+    HEADER
 
     uint64( ref_index_position )
     uint64( (obj_position << 5) | obj_id_len )

@@ -701,12 +713,16 @@ obj blocks.
 * `obj_index_position`: byte position for the start of the obj index.
 * `log_index_position`: byte position for the start of the log index.
 
+The size of the footer is 68 bytes for version 1, and 72 bytes for
+version 2.
+
 Reading the footer
 ++++++++++++++++++
 
-Readers must seek to `file_length - 68` to access the footer. A trusted
-external source (such as `stat(2)`) is necessary to obtain
-`file_length`. When reading the footer, readers must verify:
+Readers must first read the file start to determine the version
+number. Then they seek to `file_length - FOOTER_LENGTH` to access the
+footer. A trusted external source (such as `stat(2)`) is necessary to
+obtain `file_length`. When reading the footer, readers must verify:
 
 * 4-byte magic is correct
 * 1-byte version number is recognized

@@ -1055,13 +1071,3 @@ impossible.
 
 A common format that can be supported by all major Git implementations
 (git-core, JGit, libgit2) is strongly preferred.
-
-Future
-~~~~~~
-
-Longer hashes
-^^^^^^^^^^^^^
-
-Version will bump (e.g. 2) to indicate `value` uses a different object
-id length other than 20. The length could be stored in an expanded file
-header, or hardcoded as part of the version.

gitgitgadget

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

---
 refs/refs-internal.h | 5 +++++
 1 file changed, 5 insertions(+)

index ff2436c0fb7..3490aac3a40 100644
@@ -438,6 +438,11 @@ void base_ref_iterator_free(struct ref_iterator *iter);
 
 /* Virtual function declarations for ref_iterators: */
 
+/*
+ * backend-specific implementation of ref_iterator_advance.
+ * For symrefs, the function should set REF_ISSYMREF, and it should also
+ * dereference the symref to provide the OID referent.
+ */
 typedef int ref_iterator_advance_fn(struct ref_iterator *ref_iterator);
 
 typedef int ref_iterator_peel_fn(struct ref_iterator *ref_iterator,

gitgitgadget

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

The format allows for some ambiguity, as a lone footer also starts with a valid file header. However, the current JGit code will barf on this. This commit codifies this behavior into the standard.

---
 Documentation/technical/reftable.txt | 7 +++++++
 1 file changed, 7 insertions(+)

index ee3f36ea851..df5cb5f11b8 100644
@@ -731,6 +731,13 @@ version)
 
 Once verified, the other fields of the footer can be accessed.
 
+Empty tables
+++++++++++++
+
+A reftable may be empty. In this case, the file starts with a header
+and is immediately followed by a footer.
+
+
 Varint encoding
 ^^^^^^^^^^^^^^^
 

gitgitgadget

From: Johannes Schindelin <[email protected]>

This allows Git to be compiled via Visual Studio again after integrating the hn/reftable branch.

---
 config.mak.uname                           |  2 +-
 contrib/buildsystems/Generators/Vcxproj.pm | 11 ++++++++++-
 2 files changed, 11 insertions(+), 2 deletions(-)

index 5ad43c80b1a..484aec15ac2 100644
@@ -710,7 +710,7 @@ vcxproj:
 	# Make .vcxproj files and add them
 	unset QUIET_GEN QUIET_BUILT_IN; \
 	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 5c666f9ac03..33a08d31652 100644
@@ -77,7 +77,7 @@ sub createProject {
     my $libs_release = "\n    ";
     my $libs_debug = "\n    ";
     if (!$static_library) {
-      $libs_release = join(";", sort(grep /^(?!libgit\.lib|xdiff\/lib\.lib|vcs-svn\/lib\.lib)/, @{$$build_structure{"$prefix${name}_LIBS"}}));
+      $libs_release = join(";", sort(grep /^(?!libgit\.lib|xdiff\/lib\.lib|vcs-svn\/lib\.lib|reftable\/libreftable\.lib)/, @{$$build_structure{"$prefix${name}_LIBS"}}));
       $libs_debug = $libs_release;
       $libs_debug =~ s/zlib\.lib/zlibd\.lib/g;
       $libs_debug =~ s/libcurl\.lib/libcurl-d\.lib/g;

@@ -231,6 +231,7 @@ sub createProject {
 EOM
     if (!$static_library || $target =~ 'vcs-svn' || $target =~ 'xdiff') {
       my $uuid_libgit = $$build_structure{"LIBS_libgit_GUID"};
+      my $uuid_libreftable = $$build_structure{"LIBS_reftable/libreftable_GUID"};
       my $uuid_xdiff_lib = $$build_structure{"LIBS_xdiff/lib_GUID"};
 
       print F << "EOM";

@@ -240,6 +241,14 @@ sub createProject {
       <ReferenceOutputAssembly>false</ReferenceOutputAssembly>
     </ProjectReference>
 EOM
+      if (!($name =~ /xdiff|libreftable/)) {
+        print F << "EOM";
+    <ProjectReference Include="$cdup\\reftable\\libreftable\\libreftable.vcxproj">
+      <Project>$uuid_libreftable</Project>
+      <ReferenceOutputAssembly>false</ReferenceOutputAssembly>
+    </ProjectReference>
+EOM
+      }
       if (!($name =~ 'xdiff')) {
         print F << "EOM";
     <ProjectReference Include="$cdup\\xdiff\\lib\\xdiff_lib.vcxproj">

gitgitgadget

This adds the reftable library, and hooks it up as a ref backend.

Includes testing support, to test: make -C t/ GIT_TEST_REFTABLE=1

Summary 18964 tests pass 2871 tests fail

Some issues:

* worktree support looks broken
* submodules (eg. t1013)
* many tests inspect .git/logs/ directly.

v14

* Fixes for Windows (thanks, Dscho!)
* Detect file/directory conflicts.
* Plug some memory leaks.
* Fixes for autocompaction

Han-Wen Nienhuys (10):
refs.h: clarify reflog iteration order
Iterate over the "refs/" namespace in for_each_[raw]ref
refs: document how ref_iterator_advance_fn should handle symrefs Add .gitattributes for the reftable/ directory
reftable: define version 2 of the spec to accomodate SHA256
reftable: clarify how empty tables should be written Add reftable library
Reftable support for git-core
Add some reftable testing infrastructure
t: use update-ref and show-ref to reading/writing refs

Johannes Schindelin (1):
vcxproj: adjust for the reftable changes

Jonathan Nieder (1):
reftable: file format documentation

 Documentation/Makefile                        |    1 +
 Documentation/technical/reftable.txt          | 1080 +++++++++++++++
 .../technical/repository-version.txt          |    7 +
 Makefile                                      |   27 +-
 builtin/clone.c                               |    3 +-
 builtin/init-db.c                             |   56 +-
 cache.h                                       |    6 +-
 config.mak.uname                              |    2 +-
 contrib/buildsystems/Generators/Vcxproj.pm    |   11 +-
 refs.c                                        |   33 +-
 refs.h                                        |    8 +-
 refs/refs-internal.h                          |    6 +
 refs/reftable-backend.c                       | 1045 ++++++++++++++
 reftable/.gitattributes                       |    1 +
 reftable/LICENSE                              |   31 +
 reftable/README.md                            |   11 +
 reftable/VERSION                              |    5 +
 reftable/basics.c                             |  215 +++
 reftable/basics.h                             |   53 +
 reftable/block.c                              |  436 ++++++
 reftable/block.h                              |  126 ++
 reftable/blocksource.h                        |   22 +
 reftable/constants.h                          |   21 +
 reftable/file.c                               |   99 ++
 reftable/iter.c                               |  240 ++++
 reftable/iter.h                               |   63 +
 reftable/merged.c                             |  327 +++++
 reftable/merged.h                             |   38 +
 reftable/pq.c                                 |  115 ++
 reftable/pq.h                                 |   34 +
 reftable/reader.c                             |  758 ++++++++++
 reftable/reader.h                             |   68 +
 reftable/record.c                             | 1131 +++++++++++++++
 reftable/record.h                             |  121 ++
 reftable/refname.c                            |  215 +++
 reftable/refname.h                            |   39 +
 reftable/reftable.c                           |   91 ++
 reftable/reftable.h                           |  564 ++++++++
 reftable/slice.c                              |  225 +++
 reftable/slice.h                              |   76 +
 reftable/stack.c                              | 1229 +++++++++++++++++
 reftable/stack.h                              |   45 +
 reftable/system.h                             |   54 +
 reftable/tree.c                               |   67 +
 reftable/tree.h                               |   34 +
 reftable/update.sh                            |   24 +
 reftable/writer.c                             |  661 +++++++++
 reftable/writer.h                             |   60 +
 reftable/zlib-compat.c                        |   92 ++
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 setup.c                                       |   12 +-
 t/t0002-gitfile.sh                            |    2 +-
 t/t0031-reftable.sh                           |  109 ++
 t/t1400-update-ref.sh                         |   32 +-
 t/t1506-rev-parse-diagnosis.sh                |    2 +-
 t/t3210-pack-refs.sh                          |    6 +
 t/t6050-replace.sh                            |    2 +-
 t/t9020-remote-svn.sh                         |    4 +-
 t/test-lib.sh                                 |    5 +
 60 files changed, 9798 insertions(+), 57 deletions(-)
 create mode 100644 Documentation/technical/reftable.txt
 create mode 100644 refs/reftable-backend.c
 create mode 100644 reftable/.gitattributes
 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/constants.h
 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/refname.c
 create mode 100644 reftable/refname.h
 create mode 100644 reftable/reftable.c
 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 100755 reftable/update.sh
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 reftable/zlib-compat.c
 create mode 100755 t/t0031-reftable.sh

base-commit: b34789c0b0d3b137f0bb516b417bd8d75e0cb306
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-539%2Fhanwen%2Freftable-v11
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-539/hanwen/reftable-v11
Pull-Request: https://github.com/gitgitgadget/git/pull/539

Range-diff vs v10:

  1:  d3d8ed2032c =  1:  dfa5fd74f85 refs.h: clarify reflog iteration order
  2:  45fd65f72e0 =  2:  340c5c415e1 Iterate over the "refs/" namespace in for_each_[raw]ref
  3:  bc89bcd9c8c <  -:  ----------- create .git/refs in files-backend.c
  4:  fd67cdff0cd =  3:  6553285043b refs: document how ref_iterator_advance_fn should handle symrefs
  5:  5373828f854 =  4:  7dc47c7756f Add .gitattributes for the reftable/ directory
  6:  8eeed29ebbf =  5:  06fcb49e903 reftable: file format documentation
  7:  5ebc272e23d =  6:  093fa74a3d0 reftable: define version 2 of the spec to accomodate SHA256
  8:  95aae041613 =  7:  6d9031372ce reftable: clarify how empty tables should be written
  9:  59209a5ad39 !  8:  6ee6c44752c Add reftable library
     @@ reftable/README.md (new)
      
       ## reftable/VERSION (new) ##
      @@
     -+commit a6d6b31bea256044621d789df64a8159647f21bc
     ++commit 3a486f79abcd17e88e3bca62f43188a7c8b80ff3
      +Author: Han-Wen Nienhuys <[email protected]>
     -+Date:   Mon Apr 27 20:46:21 2020 +0200
     ++Date:   Mon May 4 19:20:21 2020 +0200
      +
     -+    C: prefix error codes with REFTABLE_
     ++    C: include "cache.h" in git-core sleep_millisec()
      
       ## reftable/basics.c (new) ##
      @@
     @@ reftable/basics.c (new)
      +{
      +	out[0] = (byte)((i >> 16) & 0xff);
      +	out[1] = (byte)((i >> 8) & 0xff);
     -+	out[2] = (byte)((i)&0xff);
     ++	out[2] = (byte)(i & 0xff);
      +}
      +
      +uint32_t get_be24(byte *in)
     @@ reftable/basics.c (new)
      +void put_be16(uint8_t *out, uint16_t i)
      +{
      +	out[0] = (uint8_t)((i >> 8) & 0xff);
     -+	out[1] = (uint8_t)((i)&0xff);
     ++	out[1] = (uint8_t)(i & 0xff);
      +}
      +
     -+int binsearch(int sz, int (*f)(int k, void *args), void *args)
     ++int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)
      +{
     -+	int lo = 0;
     -+	int hi = sz;
     ++	size_t lo = 0;
     ++	size_t hi = sz;
      +
      +	/* invariant: (hi == sz) || f(hi) == true
      +	   (lo == 0 && f(0) == true) || fi(lo) == false
      +	 */
      +	while (hi - lo > 1) {
     -+		int mid = lo + (hi - lo) / 2;
     ++		size_t mid = lo + (hi - lo) / 2;
      +
      +		int val = f(mid, args);
      +		if (val) {
     @@ reftable/basics.c (new)
      +
      +const char *reftable_error_str(int err)
      +{
     ++	static char buf[250];
      +	switch (err) {
      +	case REFTABLE_IO_ERROR:
      +		return "I/O error";
     @@ reftable/basics.c (new)
      +		return "misuse of the reftable API";
      +	case REFTABLE_ZLIB_ERROR:
      +		return "zlib failure";
     ++	case REFTABLE_NAME_CONFLICT:
     ++		return "file/directory conflict";
     ++	case REFTABLE_REFNAME_ERROR:
     ++		return "invalid refname";
      +	case -1:
      +		return "general error";
      +	default:
     -+		return "unknown error code";
     ++		snprintf(buf, sizeof(buf), "unknown error code %d", err);
     ++		return buf;
      +	}
      +}
      +
     -+int reftable_error_to_errno(int err) {
     ++int reftable_error_to_errno(int err)
     ++{
      +	switch (err) {
      +	case REFTABLE_IO_ERROR:
      +		return EIO;
     @@ reftable/basics.c (new)
      +	}
      +}
      +
     -+
      +void *(*reftable_malloc_ptr)(size_t sz) = &malloc;
      +void *(*reftable_realloc_ptr)(void *, size_t) = &realloc;
      +void (*reftable_free_ptr)(void *) = &free;
     @@ reftable/basics.h (new)
      +  find smallest index i in [0, sz) at which f(i) is true, assuming
      +  that f is ascending. Return sz if f(i) is false for all indices.
      +*/
     -+int binsearch(int sz, int (*f)(int k, void *args), void *args);
     ++int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args);
      +
      +/*
      +  Frees a NULL terminated array of malloced strings. The array itself is also
     @@ reftable/block.c (new)
      +			memcpy(w->buf + block_header_skip, compressed.buf,
      +			       dest_len);
      +			w->next = dest_len + block_header_skip;
     ++			slice_clear(&compressed);
      +			break;
      +		}
      +	}
     @@ reftable/block.c (new)
      +	if (typ == BLOCK_TYPE_LOG) {
      +		struct slice uncompressed = { 0 };
      +		int block_header_skip = 4 + header_off;
     -+		uLongf dst_len = sz - block_header_skip;
     ++		uLongf dst_len = sz - block_header_skip; /* total size of dest
     ++							    buffer. */
      +		uLongf src_len = block->len - block_header_skip;
      +
     ++		/* Log blocks specify the *uncompressed* size in their header.
     ++		 */
      +		slice_resize(&uncompressed, sz);
     ++
     ++		/* Copy over the block header verbatim. It's not compressed. */
      +		memcpy(uncompressed.buf, block->data, block_header_skip);
      +
     ++		/* Uncompress */
      +		if (Z_OK != uncompress_return_consumed(
      +				    uncompressed.buf + block_header_skip,
      +				    &dst_len, block->data + block_header_skip,
     @@ reftable/block.c (new)
      +			return REFTABLE_ZLIB_ERROR;
      +		}
      +
     ++		if (dst_len + block_header_skip != sz) {
     ++			return REFTABLE_FORMAT_ERROR;
     ++		}
     ++
     ++		/* We're done with the input data. */
      +		block_source_return_block(block->source, block);
      +		block->data = uncompressed.buf;
     -+		block->len = dst_len; /* XXX: 4 bytes missing? */
     ++		block->len = sz;
      +		block->source = malloc_block_source();
      +		full_block_size = src_len + block_header_skip;
      +	} else if (full_block_size == 0) {
     @@ reftable/block.c (new)
      +	struct block_reader *r;
      +};
      +
     -+static int restart_key_less(int idx, void *args)
     ++static int restart_key_less(size_t idx, void *args)
      +{
      +	struct restart_find_args *a = (struct restart_find_args *)args;
      +	uint32_t off = block_reader_restart_offset(a->r, idx);
     @@ reftable/block.c (new)
      +	slice_copy(&dest->last_key, src->last_key);
      +}
      +
     -+/* return < 0 for error, 0 for OK, > 0 for EOF. */
      +int block_iter_next(struct block_iter *it, struct record rec)
      +{
      +	if (it->next_off >= it->br->block_len) {
     @@ reftable/block.h (new)
      +int block_reader_first_key(struct block_reader *br, struct slice *key);
      +
      +void block_iter_copy_from(struct block_iter *dest, struct block_iter *src);
     ++
     ++/* return < 0 for error, 0 for OK, > 0 for EOF. */
      +int block_iter_next(struct block_iter *it, struct record rec);
      +
      +/* Seek to `want` with in the block pointed to by `it` */
     @@ reftable/blocksource.h (new)
      +
      +#endif
      
     - ## reftable/bytes.c (new) ##
     -
     - ## reftable/config.h (new) ##
     -@@
     -+/* empty */
     -
       ## reftable/constants.h (new) ##
      @@
      +/*
     @@ reftable/constants.h (new)
      +
      +#endif
      
     - ## reftable/dump.c (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#include "system.h"
     -+
     -+#include "reftable.h"
     -+
     -+static int dump_table(const char *tablename)
     -+{
     -+	struct block_source src = { 0 };
     -+	int err = block_source_from_file(&src, tablename);
     -+	if (err < 0) {
     -+		return err;
     -+	}
     -+
     -+	struct reader *r = NULL;
     -+	err = new_reader(&r, src, tablename);
     -+	if (err < 0) {
     -+		return err;
     -+	}
     -+
     -+	{
     -+		struct iterator it = { 0 };
     -+		err = reader_seek_ref(r, &it, "");
     -+		if (err < 0) {
     -+			return err;
     -+		}
     -+
     -+		struct ref_record ref = { 0 };
     -+		while (1) {
     -+			err = iterator_next_ref(it, &ref);
     -+			if (err > 0) {
     -+				break;
     -+			}
     -+			if (err < 0) {
     -+				return err;
     -+			}
     -+			ref_record_print(&ref, 20);
     -+		}
     -+		iterator_destroy(&it);
     -+		ref_record_clear(&ref);
     -+	}
     -+
     -+	{
     -+		struct iterator it = { 0 };
     -+		err = reader_seek_log(r, &it, "");
     -+		if (err < 0) {
     -+			return err;
     -+		}
     -+		struct log_record log = { 0 };
     -+		while (1) {
     -+			err = iterator_next_log(it, &log);
     -+			if (err > 0) {
     -+				break;
     -+			}
     -+			if (err < 0) {
     -+				return err;
     -+			}
     -+			log_record_print(&log, 20);
     -+		}
     -+		iterator_destroy(&it);
     -+		log_record_clear(&log);
     -+	}
     -+	return 0;
     -+}
     -+
     -+int main(int argc, char *argv[])
     -+{
     -+	int opt;
     -+	const char *table = NULL;
     -+	while ((opt = getopt(argc, argv, "t:")) != -1) {
     -+		switch (opt) {
     -+		case 't':
     -+			table = xstrdup(optarg);
     -+			break;
     -+		case '?':
     -+			printf("usage: %s [-table tablefile]\n", argv[0]);
     -+			return 2;
     -+			break;
     -+		}
     -+	}
     -+
     -+	if (table != NULL) {
     -+		int err = dump_table(table);
     -+		if (err < 0) {
     -+			fprintf(stderr, "%s: %s: %s\n", argv[0], table,
     -+				error_str(err));
     -+			return 1;
     -+		}
     -+	}
     -+	return 0;
     -+}
     -
       ## reftable/file.c (new) ##
      @@
      +/*
     @@ reftable/file.c (new)
      +		p->size = st.st_size;
      +		p->fd = fd;
      +
     ++		assert(bs->ops == NULL);
      +		bs->ops = &file_vtable;
      +		bs->arg = p;
      +	}
      +	return 0;
      +}
      +
     -+int reftable_fd_write(void *arg, byte *data, int sz)
     ++int reftable_fd_write(void *arg, byte *data, size_t sz)
      +{
      +	int *fdp = (int *)arg;
      +	return write(*fdp, data, sz);
     @@ reftable/iter.c (new)
      +
      +void iterator_set_empty(struct reftable_iterator *it)
      +{
     ++	assert(it->ops == NULL);
      +	it->iter_arg = NULL;
      +	it->ops = &empty_vtable;
      +}
     @@ reftable/iter.c (new)
      +		(struct filtering_ref_iterator *)iter_arg;
      +	struct reftable_ref_record *ref =
      +		(struct reftable_ref_record *)rec.data;
     -+
     ++	int err = 0;
      +	while (true) {
     -+		int err = reftable_iterator_next_ref(fri->it, ref);
     ++		err = reftable_iterator_next_ref(fri->it, ref);
      +		if (err != 0) {
     -+			return err;
     ++			break;
      +		}
      +
      +		if (fri->double_check) {
      +			struct reftable_iterator it = { 0 };
      +
     -+			int err = reftable_reader_seek_ref(fri->r, &it,
     -+							   ref->ref_name);
     ++			err = reftable_reader_seek_ref(fri->r, &it,
     ++						       ref->ref_name);
      +			if (err == 0) {
      +				err = reftable_iterator_next_ref(it, ref);
      +			}
     @@ reftable/iter.c (new)
      +			reftable_iterator_destroy(&it);
      +
      +			if (err < 0) {
     -+				return err;
     ++				break;
      +			}
      +
      +			if (err > 0) {
     @@ reftable/iter.c (new)
      +			return 0;
      +		}
      +	}
     ++
     ++	reftable_ref_record_clear(ref);
     ++	return err;
      +}
      +
      +struct reftable_iterator_vtable filtering_ref_iterator_vtable = {
     @@ reftable/iter.c (new)
      +void iterator_from_filtering_ref_iterator(struct reftable_iterator *it,
      +					  struct filtering_ref_iterator *fri)
      +{
     ++	assert(it->ops == NULL);
      +	it->iter_arg = fri;
      +	it->ops = &filtering_ref_iterator_vtable;
      +}
     @@ reftable/iter.c (new)
      +void iterator_from_indexed_table_ref_iter(struct reftable_iterator *it,
      +					  struct indexed_table_ref_iter *itr)
      +{
     ++	assert(it->ops == NULL);
      +	it->iter_arg = itr;
      +	it->ops = &indexed_table_ref_iter_vtable;
      +}
     @@ reftable/iter.h (new)
      +
      +void iterator_set_empty(struct reftable_iterator *it);
      +int iterator_next(struct reftable_iterator it, struct record rec);
     ++
     ++/* Returns true for a zeroed out iterator, such as the one returned from
     ++   iterator_destroy. */
      +bool iterator_is_null(struct reftable_iterator it);
      +
      +/* iterator that produces only ref records that point to `oid` */
     @@ reftable/merged.c (new)
      +	reftable_free(mi->stack);
      +}
      +
     -+static int merged_iter_advance_subiter(struct merged_iter *mi, int idx)
     ++static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)
      +{
      +	if (iterator_is_null(mi->stack[idx])) {
      +		return 0;
     @@ reftable/merged.c (new)
      +static void iterator_from_merged_iter(struct reftable_iterator *it,
      +				      struct merged_iter *mi)
      +{
     ++	assert(it->ops == NULL);
      +	it->iter_arg = mi;
      +	it->ops = &merged_iter_vtable;
      +}
     @@ reftable/merged.c (new)
      +	return mt->min;
      +}
      +
     -+static int merged_table_seek_record(struct reftable_merged_table *mt,
     -+				    struct reftable_iterator *it,
     -+				    struct record rec)
     ++int merged_table_seek_record(struct reftable_merged_table *mt,
     ++			     struct reftable_iterator *it, struct record rec)
      +{
      +	struct reftable_iterator *iters = reftable_calloc(
      +		sizeof(struct reftable_iterator) * mt->stack_len);
     @@ reftable/merged.h (new)
      +};
      +
      +void merged_table_clear(struct reftable_merged_table *mt);
     ++int merged_table_seek_record(struct reftable_merged_table *mt,
     ++			     struct reftable_iterator *it, struct record rec);
      +
      +#endif
      
     @@ reftable/reader.c (new)
      +static void iterator_from_table_iter(struct reftable_iterator *it,
      +				     struct table_iter *ti)
      +{
     ++	assert(it->ops == NULL);
      +	it->iter_arg = ti;
      +	it->ops = &table_iter_vtable;
      +}
     @@ reftable/reader.c (new)
      +	if (err == 0) {
      +		*p = rd;
      +	} else {
     ++		block_source_close(&src);
      +		reftable_free(rd);
      +	}
      +	return err;
     @@ reftable/reader.c (new)
      +	struct record got_rec = { 0 };
      +	int err = 0;
      +
     ++	/* Look through the reverse index. */
      +	record_from_obj(&want_rec, &want);
     -+
      +	err = reader_seek(r, &oit, want_rec);
      +	if (err != 0) {
     -+		return err;
     ++		goto exit;
      +	}
      +
     ++	/* read out the obj_record */
      +	record_from_obj(&got_rec, &got);
      +	err = iterator_next(oit, got_rec);
     -+	reftable_iterator_destroy(&oit);
      +	if (err < 0) {
     -+		return err;
     ++		goto exit;
      +	}
      +
      +	if (err > 0 ||
      +	    memcmp(want.hash_prefix, got.hash_prefix, r->object_id_len)) {
     ++		/* didn't find it; return empty iterator */
      +		iterator_set_empty(it);
     -+		return 0;
     ++		err = 0;
     ++		goto exit;
      +	}
      +
      +	{
     @@ reftable/reader.c (new)
      +						 hash_size(r->hash_id),
      +						 got.offsets, got.offset_len);
      +		if (err < 0) {
     -+			record_clear(got_rec);
     -+			return err;
     ++			goto exit;
      +		}
      +		got.offsets = NULL;
     -+		record_clear(got_rec);
     -+
      +		iterator_from_indexed_table_ref_iter(it, itr);
      +	}
      +
     -+	return 0;
     ++exit:
     ++	reftable_iterator_destroy(&oit);
     ++	record_clear(got_rec);
     ++	return err;
      +}
      +
      +static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,
     @@ reftable/record.c (new)
      +	memcpy(r->message, dest.buf, dest.len);
      +	r->message[dest.len] = 0;
      +
     ++	slice_clear(&dest);
      +	return start.len - in.len;
      +
      +error:
     @@ reftable/record.c (new)
      +
      +struct record new_record(byte typ)
      +{
     -+	struct record rec;
     ++	struct record rec = { NULL };
      +	switch (typ) {
      +	case BLOCK_TYPE_REF: {
      +		struct reftable_ref_record *r =
     @@ reftable/record.c (new)
      +
      +void record_clear(struct record rec)
      +{
     -+	return rec.ops->clear(rec.data);
     ++	rec.ops->clear(rec.data);
      +}
      +
      +bool record_is_deletion(struct record rec)
     @@ reftable/record.c (new)
      +
      +void record_from_ref(struct record *rec, struct reftable_ref_record *ref_rec)
      +{
     ++	assert(rec->ops == NULL);
      +	rec->data = ref_rec;
      +	rec->ops = &reftable_ref_record_vtable;
      +}
      +
      +void record_from_obj(struct record *rec, struct obj_record *obj_rec)
      +{
     ++	assert(rec->ops == NULL);
      +	rec->data = obj_rec;
      +	rec->ops = &obj_record_vtable;
      +}
      +
      +void record_from_index(struct record *rec, struct index_record *index_rec)
      +{
     ++	assert(rec->ops == NULL);
      +	rec->data = index_rec;
      +	rec->ops = &index_record_vtable;
      +}
      +
      +void record_from_log(struct record *rec, struct reftable_log_record *log_rec)
      +{
     ++	assert(rec->ops == NULL);
      +	rec->data = log_rec;
      +	rec->ops = &reftable_log_record_vtable;
      +}
     @@ reftable/record.h (new)
      +
      +#endif
      
     + ## reftable/refname.c (new) ##
     +@@
     ++/*
     ++  Copyright 2020 Google LLC
     ++
     ++  Use of this source code is governed by a BSD-style
     ++  license that can be found in the LICENSE file or at
     ++  https://developers.google.com/open-source/licenses/bsd
     ++*/
     ++
     ++#include "system.h"
     ++#include "reftable.h"
     ++#include "basics.h"
     ++#include "refname.h"
     ++#include "slice.h"
     ++
     ++struct find_arg {
     ++	char **names;
     ++	const char *want;
     ++};
     ++
     ++static int find_name(size_t k, void *arg)
     ++{
     ++	struct find_arg *f_arg = (struct find_arg *)arg;
     ++
     ++	return strcmp(f_arg->names[k], f_arg->want) >= 0;
     ++}
     ++
     ++int modification_has_ref(struct modification *mod, const char *name)
     ++{
     ++	struct reftable_ref_record ref = { 0 };
     ++	int err = 0;
     ++
     ++	if (mod->add_len > 0) {
     ++		struct find_arg arg = {
     ++			.names = mod->add,
     ++			.want = name,
     ++		};
     ++		int idx = binsearch(mod->add_len, find_name, &arg);
     ++		if (idx < mod->add_len && !strcmp(mod->add[idx], name)) {
     ++			return 0;
     ++		}
     ++	}
     ++
     ++	if (mod->del_len > 0) {
     ++		struct find_arg arg = {
     ++			.names = mod->del,
     ++			.want = name,
     ++		};
     ++		int idx = binsearch(mod->del_len, find_name, &arg);
     ++		if (idx < mod->del_len && !strcmp(mod->del[idx], name)) {
     ++			return 1;
     ++		}
     ++	}
     ++
     ++	err = reftable_table_read_ref(mod->tab, name, &ref);
     ++	reftable_ref_record_clear(&ref);
     ++	return err;
     ++}
     ++
     ++static void modification_clear(struct modification *mod)
     ++{
     ++	FREE_AND_NULL(mod->add);
     ++	FREE_AND_NULL(mod->del);
     ++	mod->add_len = 0;
     ++	mod->del_len = 0;
     ++}
     ++
     ++int modification_has_ref_with_prefix(struct modification *mod,
     ++				     const char *prefix)
     ++{
     ++	struct reftable_iterator it = { NULL };
     ++	struct reftable_ref_record ref = { NULL };
     ++	int err = 0;
     ++
     ++	if (mod->add_len > 0) {
     ++		struct find_arg arg = {
     ++			.names = mod->add,
     ++			.want = prefix,
     ++		};
     ++		int idx = binsearch(mod->add_len, find_name, &arg);
     ++		if (idx < mod->add_len &&
     ++		    !strncmp(prefix, mod->add[idx], strlen(prefix))) {
     ++			goto exit;
     ++		}
     ++	}
     ++
     ++	err = reftable_table_seek_ref(mod->tab, &it, prefix);
     ++	if (err) {
     ++		goto exit;
     ++	}
     ++
     ++	while (true) {
     ++		err = reftable_iterator_next_ref(it, &ref);
     ++		if (err) {
     ++			goto exit;
     ++		}
     ++
     ++		if (mod->del_len > 0) {
     ++			struct find_arg arg = {
     ++				.names = mod->del,
     ++				.want = ref.ref_name,
     ++			};
     ++			int idx = binsearch(mod->del_len, find_name, &arg);
     ++			if (idx < mod->del_len &&
     ++			    !strcmp(ref.ref_name, mod->del[idx])) {
     ++				continue;
     ++			}
     ++		}
     ++
     ++		if (strncmp(ref.ref_name, prefix, strlen(prefix))) {
     ++			err = 1;
     ++			goto exit;
     ++		}
     ++		err = 0;
     ++		goto exit;
     ++	}
     ++
     ++exit:
     ++	reftable_ref_record_clear(&ref);
     ++	reftable_iterator_destroy(&it);
     ++	return err;
     ++}
     ++
     ++int validate_ref_name(const char *name)
     ++{
     ++	while (true) {
     ++		char *next = strchr(name, '/');
     ++		if (!*name) {
     ++			return REFTABLE_REFNAME_ERROR;
     ++		}
     ++		if (!next) {
     ++			return 0;
     ++		}
     ++		if (next - name == 0 || (next - name == 1 && *name == '.') ||
     ++		    (next - name == 2 && name[0] == '.' && name[1] == '.'))
     ++			return REFTABLE_REFNAME_ERROR;
     ++		name = next + 1;
     ++	}
     ++	return 0;
     ++}
     ++
     ++int validate_ref_record_addition(struct reftable_table tab,
     ++				 struct reftable_ref_record *recs, size_t sz)
     ++{
     ++	struct modification mod = {
     ++		.tab = tab,
     ++		.add = reftable_calloc(sizeof(char *) * sz),
     ++		.del = reftable_calloc(sizeof(char *) * sz),
     ++	};
     ++	int i = 0;
     ++	int err = 0;
     ++	for (; i < sz; i++) {
     ++		if (reftable_ref_record_is_deletion(&recs[i])) {
     ++			mod.del[mod.del_len++] = recs[i].ref_name;
     ++		} else {
     ++			mod.add[mod.add_len++] = recs[i].ref_name;
     ++		}
     ++	}
     ++
     ++	err = modification_validate(&mod);
     ++	modification_clear(&mod);
     ++	return err;
     ++}
     ++
     ++static void slice_trim_component(struct slice *sl)
     ++{
     ++	while (sl->len > 0) {
     ++		bool is_slash = (sl->buf[sl->len - 1] == '/');
     ++		sl->len--;
     ++		if (is_slash)
     ++			break;
     ++	}
     ++}
     ++
     ++int modification_validate(struct modification *mod)
     ++{
     ++	struct slice slashed = { 0 };
     ++	int err = 0;
     ++	int i = 0;
     ++	for (; i < mod->add_len; i++) {
     ++		err = validate_ref_name(mod->add[i]);
     ++		if (err) {
     ++			goto exit;
     ++		}
     ++		slice_set_string(&slashed, mod->add[i]);
     ++		slice_append_string(&slashed, "/");
     ++
     ++		err = modification_has_ref_with_prefix(
     ++			mod, slice_as_string(&slashed));
     ++		if (err == 0) {
     ++			err = REFTABLE_NAME_CONFLICT;
     ++			goto exit;
     ++		}
     ++		if (err < 0) {
     ++			goto exit;
     ++		}
     ++
     ++		slice_set_string(&slashed, mod->add[i]);
     ++		while (slashed.len) {
     ++			slice_trim_component(&slashed);
     ++			err = modification_has_ref(mod,
     ++						   slice_as_string(&slashed));
     ++			if (err == 0) {
     ++				err = REFTABLE_NAME_CONFLICT;
     ++				goto exit;
     ++			}
     ++			if (err < 0) {
     ++				goto exit;
     ++			}
     ++		}
     ++	}
     ++	err = 0;
     ++exit:
     ++	slice_clear(&slashed);
     ++	return err;
     ++}
     +
     + ## reftable/refname.h (new) ##
     +@@
     ++/*
     ++  Copyright 2020 Google LLC
     ++
     ++  Use of this source code is governed by a BSD-style
     ++  license that can be found in the LICENSE file or at
     ++  https://developers.google.com/open-source/licenses/bsd
     ++*/
     ++#ifndef REFNAME_H
     ++#define REFNAME_H
     ++
     ++struct modification {
     ++	struct reftable_table tab;
     ++
     ++	char **add;
     ++	size_t add_len;
     ++
     ++	char **del;
     ++	size_t del_len;
     ++};
     ++
     ++// -1 = error, 0 = found, 1 = not found
     ++int modification_has_ref(struct modification *mod, const char *name);
     ++
     ++// -1 = error, 0 = found, 1 = not found.
     ++int modification_has_ref_with_prefix(struct modification *mod,
     ++				     const char *prefix);
     ++
     ++// 0 = OK.
     ++int validate_ref_name(const char *name);
     ++
     ++int validate_ref_record_addition(struct reftable_table tab,
     ++				 struct reftable_ref_record *recs, size_t sz);
     ++
     ++int modification_validate(struct modification *mod);
     ++
     ++/* illegal name, or dir/file conflict */
     ++#define REFTABLE_REFNAME_ERROR -9
     ++
     ++#endif
     +
     + ## reftable/reftable.c (new) ##
     +@@
     ++/*
     ++Copyright 2020 Google LLC
     ++
     ++Use of this source code is governed by a BSD-style
     ++license that can be found in the LICENSE file or at
     ++https://developers.google.com/open-source/licenses/bsd
     ++*/
     ++
     ++#include "reftable.h"
     ++#include "record.h"
     ++#include "reader.h"
     ++#include "merged.h"
     ++
     ++struct reftable_table_vtable {
     ++	int (*seek)(void *tab, struct reftable_iterator *it, struct record);
     ++};
     ++
     ++static int reftable_reader_seek_void(void *tab, struct reftable_iterator *it,
     ++				     struct record rec)
     ++{
     ++	return reader_seek((struct reftable_reader *)tab, it, rec);
     ++}
     ++
     ++static struct reftable_table_vtable reader_vtable = {
     ++	.seek = reftable_reader_seek_void,
     ++};
     ++
     ++static int reftable_merged_table_seek_void(void *tab,
     ++					   struct reftable_iterator *it,
     ++					   struct record rec)
     ++{
     ++	return merged_table_seek_record((struct reftable_merged_table *)tab, it,
     ++					rec);
     ++}
     ++
     ++static struct reftable_table_vtable merged_table_vtable = {
     ++	.seek = reftable_merged_table_seek_void,
     ++};
     ++
     ++int reftable_table_seek_ref(struct reftable_table tab,
     ++			    struct reftable_iterator *it, const char *name)
     ++{
     ++	struct reftable_ref_record ref = {
     ++		.ref_name = (char *)name,
     ++	};
     ++	struct record rec = { 0 };
     ++	record_from_ref(&rec, &ref);
     ++	return tab.ops->seek(tab.table_arg, it, rec);
     ++}
     ++
     ++void reftable_table_from_reader(struct reftable_table *tab,
     ++				struct reftable_reader *reader)
     ++{
     ++	assert(tab->ops == NULL);
     ++	tab->ops = &reader_vtable;
     ++	tab->table_arg = reader;
     ++}
     ++
     ++void reftable_table_from_merged_table(struct reftable_table *tab,
     ++				      struct reftable_merged_table *merged)
     ++{
     ++	assert(tab->ops == NULL);
     ++	tab->ops = &merged_table_vtable;
     ++	tab->table_arg = merged;
     ++}
     ++
     ++int reftable_table_read_ref(struct reftable_table tab, const char *name,
     ++			    struct reftable_ref_record *ref)
     ++{
     ++	struct reftable_iterator it = { 0 };
     ++	int err = reftable_table_seek_ref(tab, &it, name);
     ++	if (err) {
     ++		goto exit;
     ++	}
     ++
     ++	err = reftable_iterator_next_ref(it, ref);
     ++	if (err) {
     ++		goto exit;
     ++	}
     ++
     ++	if (strcmp(ref->ref_name, name) ||
     ++	    reftable_ref_record_is_deletion(ref)) {
     ++		reftable_ref_record_clear(ref);
     ++		err = 1;
     ++		goto exit;
     ++	}
     ++
     ++exit:
     ++	reftable_iterator_destroy(&it);
     ++	return err;
     ++}
     +
       ## reftable/reftable.h (new) ##
      @@
      +/*
     @@ reftable/reftable.h (new)
      +
      +	/* Wrote a table without blocks. */
      +	REFTABLE_EMPTY_TABLE_ERROR = -8,
     ++
     ++	/* Dir/file conflict. */
     ++	REFTABLE_NAME_CONFLICT = -9,
     ++
     ++	/* Illegal ref name. */
     ++	REFTABLE_REFNAME_ERROR = -10,
      +};
      +
      +/* convert the numeric error code to a string. The string should not be
     @@ reftable/reftable.h (new)
      +	 * Defaults to SHA1 if unset
      +	 */
      +	uint32_t hash_id;
     ++
     ++	/* boolean: do not check ref names for validity or dir/file conflicts.
     ++	 */
     ++	int skip_name_check;
      +};
      +
      +/* reftable_block_stats holds statistics for a single block type */
     @@ reftable/reftable.h (new)
      +
      +/* reftable_new_writer creates a new writer */
      +struct reftable_writer *
     -+reftable_new_writer(int (*writer_func)(void *, uint8_t *, int),
     ++reftable_new_writer(int (*writer_func)(void *, uint8_t *, size_t),
      +		    void *writer_arg, struct reftable_write_options *opts);
      +
      +/* write to a file descriptor. fdp should be an int* pointing to the fd. */
     -+int reftable_fd_write(void *fdp, uint8_t *data, int size);
     ++int reftable_fd_write(void *fdp, uint8_t *data, size_t size);
      +
      +/* Set the range of update indices for the records we will add.  When
      +   writing a table into a stack, the min should be at least
     @@ reftable/reftable.h (new)
      +struct reftable_reader;
      +
      +/* reftable_new_reader opens a reftable for reading. If successful, returns 0
     -+ * code and sets pp.  The name is used for creating a
     -+ * stack. Typically, it is the basename of the file.
     ++ * code and sets pp. The name is used for creating a stack. Typically, it is the
     ++ * basename of the file. The block source `src` is owned by the reader, and is
     ++ * closed on calling reftable_reader_destroy().
      + */
      +int reftable_new_reader(struct reftable_reader **pp,
     -+			struct reftable_block_source, const char *name);
     ++			struct reftable_block_source src, const char *name);
      +
      +/* reftable_reader_seek_ref returns an iterator where 'name' would be inserted
      +   in the table.  To seek to the start of the table, use name = "".
     @@ reftable/reftable.h (new)
      +void reftable_merged_table_free(struct reftable_merged_table *m);
      +
      +/****************************************************************
     ++ Generic tables
     ++
     ++ A unified API for reading tables, either merged tables, or single readers.
     ++ ****************************************************************/
     ++
     ++struct reftable_table {
     ++	struct reftable_table_vtable *ops;
     ++	void *table_arg;
     ++};
     ++
     ++int reftable_table_seek_ref(struct reftable_table tab,
     ++			    struct reftable_iterator *it, const char *name);
     ++
     ++void reftable_table_from_reader(struct reftable_table *tab,
     ++				struct reftable_reader *reader);
     ++void reftable_table_from_merged_table(struct reftable_table *tab,
     ++				      struct reftable_merged_table *table);
     ++
     ++/* convenience function to read a single ref. Returns < 0 for error, 0
     ++   for success, and 1 if ref not found. */
     ++int reftable_table_read_ref(struct reftable_table tab, const char *name,
     ++			    struct reftable_ref_record *ref);
     ++
     ++/****************************************************************
      + Mutable ref database
      +
      + The stack presents an interface to a mutable sequence of reftables.
     @@ reftable/reftable.h (new)
      +/* statistics on past compactions. */
      +struct reftable_compaction_stats {
      +	uint64_t bytes; /* total number of bytes written */
     ++	uint64_t entries_written; /* total number of entries written, including
     ++				     failures. */
      +	int attempts; /* how often we tried to compact */
      +	int failures; /* failures happen on concurrent updates */
      +};
     @@ reftable/slice.c (new)
      +	}
      +}
      +
     -+int slice_write(struct slice *b, byte *data, int sz)
     ++int slice_write(struct slice *b, byte *data, size_t sz)
      +{
      +	if (b->len + sz > b->cap) {
      +		int newcap = 2 * b->cap + 1;
     @@ reftable/slice.c (new)
      +	return sz;
      +}
      +
     -+int slice_write_void(void *b, byte *data, int sz)
     ++int slice_write_void(void *b, byte *data, size_t sz)
      +{
      +	return slice_write((struct slice *)b, data, sz);
      +}
     @@ reftable/slice.c (new)
      +void block_source_from_slice(struct reftable_block_source *bs,
      +			     struct slice *buf)
      +{
     ++	assert(bs->ops == NULL);
      +	bs->ops = &slice_vtable;
      +	bs->arg = buf;
      +}
     @@ reftable/slice.h (new)
      +int slice_compare(struct slice a, struct slice b);
      +
      +/* Append `data` to the `dest` slice.  */
     -+int slice_write(struct slice *dest, byte *data, int sz);
     ++int slice_write(struct slice *dest, byte *data, size_t sz);
      +
      +/* Append `add` to `dest. */
      +void slice_append(struct slice *dest, struct slice add);
      +
      +/* Like slice_write, but suitable for passing to reftable_new_writer
      + */
     -+int slice_write_void(void *b, byte *data, int sz);
     ++int slice_write_void(void *b, byte *data, size_t sz);
      +
      +/* Find the longest shared prefix size of `a` and `b` */
      +int common_prefix_size(struct slice a, struct slice b);
     @@ reftable/stack.c (new)
      +#include "system.h"
      +#include "merged.h"
      +#include "reader.h"
     ++#include "refname.h"
      +#include "reftable.h"
      +#include "writer.h"
      +
     @@ reftable/stack.c (new)
      +{
      +	struct reftable_stack *p =
      +		reftable_calloc(sizeof(struct reftable_stack));
     -+	struct slice list_file_name = {};
     ++	struct slice list_file_name = { 0 };
      +	int err = 0;
      +
      +	if (config.hash_id == 0) {
     @@ reftable/stack.c (new)
      +			}
      +		}
      +	}
     ++
      +exit:
      +	slice_clear(&table_path);
      +	{
     @@ reftable/stack.c (new)
      +		free_names(names);
      +		free_names(names_after);
      +
     -+		delay = delay + (delay * rand()) / RAND_MAX + 100;
     -+		usleep(delay);
     ++		delay = delay + (delay * rand()) / RAND_MAX + 1;
     ++		sleep_millisec(delay);
      +	}
      +
      +	return 0;
     @@ reftable/stack.c (new)
      +	int err = stack_try_add(st, write, arg);
      +	if (err < 0) {
      +		if (err == REFTABLE_LOCK_ERROR) {
     -+			// Ignore error return, we want to propagate
     -+			// REFTABLE_LOCK_ERROR.
     ++			/* Ignore error return, we want to propagate
     ++			   REFTABLE_LOCK_ERROR.
     ++			*/
      +			reftable_stack_reload(st);
      +		}
      +		return err;
     @@ reftable/stack.c (new)
      +void reftable_addition_close(struct reftable_addition *add)
      +{
      +	int i = 0;
     -+	struct slice nm = {};
     ++	struct slice nm = { 0 };
      +	for (i = 0; i < add->new_tables_len; i++) {
      +		slice_set_string(&nm, add->stack->list_file);
      +		slice_append_string(&nm, "/");
      +		slice_append_string(&nm, add->new_tables[i]);
      +		unlink(slice_as_string(&nm));
     -+
      +		reftable_free(add->new_tables[i]);
      +		add->new_tables[i] = NULL;
      +	}
     @@ reftable/stack.c (new)
      +
      +	free_names(add->names);
      +	add->names = NULL;
     ++	slice_clear(&nm);
      +}
      +
      +int reftable_addition_commit(struct reftable_addition *add)
     @@ reftable/stack.c (new)
      +	struct reftable_writer *wr = NULL;
      +	int err = 0;
      +	int tab_fd = 0;
     -+	uint64_t next_update_index = 0;
      +
      +	slice_resize(&next_name, 0);
     -+	format_name(&next_name, next_update_index, next_update_index);
     ++	format_name(&next_name, add->next_update_index, add->next_update_index);
      +
      +	slice_set_string(&temp_tab_file_name, add->stack->reftable_dir);
      +	slice_append_string(&temp_tab_file_name, "/");
     @@ reftable/stack.c (new)
      +		goto exit;
      +	}
      +
     -+	if (wr->min_update_index < next_update_index) {
     ++	err = stack_check_addition(add->stack,
     ++				   slice_as_string(&temp_tab_file_name));
     ++	if (err < 0) {
     ++		goto exit;
     ++	}
     ++
     ++	if (wr->min_update_index < add->next_update_index) {
      +		err = REFTABLE_API_ERROR;
      +		goto exit;
      +	}
     @@ reftable/stack.c (new)
      +	struct reftable_ref_record ref = { 0 };
      +	struct reftable_log_record log = { 0 };
      +
     ++	uint64_t entries = 0;
     ++
      +	int i = 0, j = 0;
      +	for (i = first, j = 0; i <= last; i++) {
      +		struct reftable_reader *t = st->merged->stack[i];
     @@ reftable/stack.c (new)
      +		if (err < 0) {
      +			break;
      +		}
     ++		entries++;
      +	}
     ++	reftable_iterator_destroy(&it);
      +
      +	err = reftable_merged_table_seek_log(mt, &it, "");
      +	if (err < 0) {
     @@ reftable/stack.c (new)
      +			continue;
      +		}
      +
     -+		/* XXX collect stats? */
     -+
      +		if (config != NULL && config->time > 0 &&
      +		    log.time < config->time) {
      +			continue;
     @@ reftable/stack.c (new)
      +		if (err < 0) {
      +			break;
      +		}
     ++		entries++;
      +	}
      +
      +exit:
     @@ reftable/stack.c (new)
      +		reftable_merged_table_free(mt);
      +	}
      +	reftable_ref_record_clear(&ref);
     -+
     ++	reftable_log_record_clear(&log);
     ++	st->stats.entries_written += entries;
      +	return err;
      +}
      +
     @@ reftable/stack.c (new)
      +		}
      +		goto exit;
      +	}
     ++	/* Don't want to write to the lock for now.  */
     ++	close(lock_file_fd);
     ++	lock_file_fd = 0;
     ++
      +	have_lock = true;
      +	err = stack_uptodate(st);
      +	if (err != 0) {
     @@ reftable/stack.c (new)
      +	}
      +	have_lock = false;
      +
     ++	/* Reload the stack before deleting. On windows, we can only delete the
     ++	   files after we closed them.
     ++	*/
     ++	err = reftable_stack_reload_maybe_reuse(st, first < last);
     ++
      +	{
      +		char **p = delete_on_success;
      +		while (*p) {
     @@ reftable/stack.c (new)
      +		}
      +	}
      +
     -+	err = reftable_stack_reload_maybe_reuse(st, first < last);
      +exit:
      +	free_names(delete_on_success);
      +	{
     @@ reftable/stack.c (new)
      +int fastlog2(uint64_t sz)
      +{
      +	int l = 0;
     -+	assert(sz > 0);
     ++	if (sz == 0) {
     ++		return 0;
     ++	}
      +	for (; sz; sz /= 2) {
      +		l++;
      +	}
     @@ reftable/stack.c (new)
      +	int next = 0;
      +	struct segment cur = { 0 };
      +	int i = 0;
     ++
     ++	if (n == 0) {
     ++		*seglen = 0;
     ++		return segs;
     ++	}
      +	for (i = 0; i < n; i++) {
      +		int log = fastlog2(sizes[i]);
      +		if (cur.log != log && cur.bytes > 0) {
     @@ reftable/stack.c (new)
      +		cur.end = i + 1;
      +		cur.bytes += sizes[i];
      +	}
     -+	if (next > 0) {
     -+		segs[next++] = cur;
     -+	}
     ++	segs[next++] = cur;
      +	*seglen = next;
      +	return segs;
      +}
     @@ reftable/stack.c (new)
      +	uint64_t *sizes =
      +		reftable_calloc(sizeof(uint64_t) * st->merged->stack_len);
      +	int version = (st->config.hash_id == SHA1_ID) ? 1 : 2;
     -+	int overhead = footer_size(version) + header_size(version) - 1;
     ++	int overhead = header_size(version) - 1;
      +	int i = 0;
      +	for (i = 0; i < st->merged->stack_len; i++) {
      +		sizes[i] = st->merged->stack[i]->size - overhead;
     @@ reftable/stack.c (new)
      +int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,
      +			    struct reftable_ref_record *ref)
      +{
     ++	struct reftable_table tab = { NULL };
     ++	reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st));
     ++	return reftable_table_read_ref(tab, refname, ref);
     ++}
     ++
     ++int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
     ++			    struct reftable_log_record *log)
     ++{
      +	struct reftable_iterator it = { 0 };
      +	struct reftable_merged_table *mt = reftable_stack_merged_table(st);
     -+	int err = reftable_merged_table_seek_ref(mt, &it, refname);
     ++	int err = reftable_merged_table_seek_log(mt, &it, refname);
      +	if (err) {
      +		goto exit;
      +	}
      +
     -+	err = reftable_iterator_next_ref(it, ref);
     ++	err = reftable_iterator_next_log(it, log);
      +	if (err) {
      +		goto exit;
      +	}
      +
     -+	if (strcmp(ref->ref_name, refname) ||
     -+	    reftable_ref_record_is_deletion(ref)) {
     ++	if (strcmp(log->ref_name, refname) ||
     ++	    reftable_log_record_is_deletion(log)) {
      +		err = 1;
      +		goto exit;
      +	}
      +
      +exit:
     ++	if (err) {
     ++		reftable_log_record_clear(log);
     ++	}
      +	reftable_iterator_destroy(&it);
      +	return err;
      +}
      +
     -+int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
     -+			    struct reftable_log_record *log)
     ++int stack_check_addition(struct reftable_stack *st, const char *new_tab_name)
      +{
     -+	struct reftable_iterator it = { 0 };
     -+	struct reftable_merged_table *mt = reftable_stack_merged_table(st);
     -+	int err = reftable_merged_table_seek_log(mt, &it, refname);
     -+	if (err) {
     ++	int err = 0;
     ++	struct reftable_block_source src = { 0 };
     ++	struct reftable_reader *rd = NULL;
     ++	struct reftable_table tab = { NULL };
     ++	struct reftable_ref_record *refs = NULL;
     ++	struct reftable_iterator it = { NULL };
     ++	int cap = 0;
     ++	int len = 0;
     ++	int i = 0;
     ++
     ++	if (st->config.skip_name_check) {
     ++		return 0;
     ++	}
     ++
     ++	err = reftable_block_source_from_file(&src, new_tab_name);
     ++	if (err < 0) {
      +		goto exit;
      +	}
      +
     -+	err = reftable_iterator_next_log(it, log);
     -+	if (err) {
     ++	err = reftable_new_reader(&rd, src, new_tab_name);
     ++	if (err < 0) {
      +		goto exit;
      +	}
      +
     -+	if (strcmp(log->ref_name, refname) ||
     -+	    reftable_log_record_is_deletion(log)) {
     -+		err = 1;
     ++	err = reftable_reader_seek_ref(rd, &it, "");
     ++	if (err > 0) {
     ++		err = 0;
      +		goto exit;
      +	}
     ++	if (err < 0) {
     ++		goto exit;
     ++	}
     ++
     ++	while (true) {
     ++		struct reftable_ref_record ref = { 0 };
     ++		err = reftable_iterator_next_ref(it, &ref);
     ++		if (err > 0) {
     ++			break;
     ++		}
     ++		if (err < 0) {
     ++			goto exit;
     ++		}
     ++
     ++		if (len >= cap) {
     ++			cap = 2 * cap + 1;
     ++			refs = reftable_realloc(refs, cap * sizeof(refs[0]));
     ++		}
     ++
     ++		refs[len++] = ref;
     ++	}
     ++
     ++	reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st));
     ++
     ++	err = validate_ref_record_addition(tab, refs, len);
     ++
     ++	for (i = 0; i < len; i++) {
     ++		reftable_ref_record_clear(&refs[i]);
     ++	}
      +
      +exit:
     ++	free(refs);
      +	reftable_iterator_destroy(&it);
     ++	reftable_reader_free(rd);
      +	return err;
      +}
      
     @@ reftable/stack.h (new)
      +			int first, int last,
      +			struct reftable_log_expiry_config *config);
      +int fastlog2(uint64_t sz);
     ++int stack_check_addition(struct reftable_stack *st, const char *new_tab_name);
      +
      +struct segment {
      +	int start, end;
     @@ reftable/system.h (new)
      +#if 1 /* REFTABLE_IN_GITCORE */
      +
      +#include "git-compat-util.h"
     ++#include "cache.h"
      +#include <zlib.h>
      +
      +#else
     @@ reftable/update.sh (new)
      +set -eu
      +
      +# Override this to import from somewhere else, say "../reftable".
     -+SRC=${SRC:-origin} BRANCH=${BRANCH:-origin/master}
     ++SRC=${SRC:-origin}
     ++BRANCH=${BRANCH:-master}
      +
     -+((git --git-dir reftable-repo/.git fetch ${SRC} && cd reftable-repo && git checkout ${BRANCH} ) ||
     ++((git --git-dir reftable-repo/.git fetch ${SRC} ${BRANCH}:import && cd reftable-repo && git checkout -f $(git rev-parse import) ) ||
      +   git clone https://github.com/google/reftable reftable-repo)
      +
      +cp reftable-repo/c/*.[ch] reftable/
      +cp reftable-repo/c/include/*.[ch] reftable/
      +cp reftable-repo/LICENSE reftable/
     -+git --git-dir reftable-repo/.git show --no-patch origin/master \
     ++git --git-dir reftable-repo/.git show --no-patch HEAD \
      +  > reftable/VERSION
      +
      +mv reftable/system.h reftable/system.h~
     @@ reftable/writer.c (new)
      +}
      +
      +struct reftable_writer *
     -+reftable_new_writer(int (*writer_func)(void *, byte *, int), void *writer_arg,
     -+		    struct reftable_write_options *opts)
     ++reftable_new_writer(int (*writer_func)(void *, byte *, size_t),
     ++		    void *writer_arg, struct reftable_write_options *opts)
      +{
      +	struct reftable_writer *wp =
      +		reftable_calloc(sizeof(struct reftable_writer));
     @@ reftable/writer.c (new)
      +	}
      +	w->pending_padding = 0;
      +	if (empty_table) {
     -+		// Empty tables need a header anyway.
     ++		/* Empty tables need a header anyway. */
      +		byte header[28];
      +		int n = writer_write_header(w, header);
      +		err = padded_write(w, header, n, 0);
     @@ reftable/writer.h (new)
      +#include "tree.h"
      +
      +struct reftable_writer {
     -+	int (*write)(void *, byte *, int);
     ++	int (*write)(void *, byte *, size_t);
      +	void *write_arg;
      +	int pending_padding;
      +	struct slice last_key;
 10:  be2371cd6e4 !  9:  d731e1669b7 Reftable support for git-core
     @@ Commit message
      
           * Resolve spots marked with XXX
      
     -     * Detect and prevent directory/file conflicts in naming.
     -
           * Support worktrees (t0002-gitfile "linked repo" testcase)
      
          Example use: see t/t0031-reftable.sh
     @@ Makefile: TEST_SHELL_PATH = $(SHELL_PATH)
       VCSSVN_LIB = vcs-svn/lib.a
      +REFTABLE_LIB = reftable/libreftable.a
       
     + GENERATED_H += config-list.h
       GENERATED_H += command-list.h
     - 
     -@@ Makefile: LIB_OBJS += rebase-interactive.o
     +@@ Makefile: LIB_OBJS += ref-filter.o
       LIB_OBJS += reflog-walk.o
       LIB_OBJS += refs.o
       LIB_OBJS += refs/files-backend.o
     @@ Makefile: THIRD_PARTY_SOURCES += compat/regex/%
       EXTLIBS =
       
       GIT_USER_AGENT = git/$(GIT_VERSION)
     -@@ Makefile: VCSSVN_OBJS += vcs-svn/fast_export.o
     +@@ Makefile: VCSSVN_OBJS += vcs-svn/sliding_window.o
       VCSSVN_OBJS += vcs-svn/svndiff.o
       VCSSVN_OBJS += vcs-svn/svndump.o
       
      +REFTABLE_OBJS += reftable/basics.o
      +REFTABLE_OBJS += reftable/block.o
     -+REFTABLE_OBJS += reftable/bytes.o
      +REFTABLE_OBJS += reftable/file.o
      +REFTABLE_OBJS += reftable/iter.o
      +REFTABLE_OBJS += reftable/merged.o
      +REFTABLE_OBJS += reftable/pq.o
      +REFTABLE_OBJS += reftable/reader.o
      +REFTABLE_OBJS += reftable/record.o
     ++REFTABLE_OBJS += reftable/refname.o
     ++REFTABLE_OBJS += reftable/reftable.o
      +REFTABLE_OBJS += reftable/slice.o
      +REFTABLE_OBJS += reftable/stack.o
      +REFTABLE_OBJS += reftable/tree.o
     @@ builtin/init-db.c: static int create_default_files(const char *template_path,
      +	reinit = (!access(path, R_OK) ||
      +		  readlink(path, junk, sizeof(junk) - 1) != -1);
      +
     -+        /*
     -+         * refs/heads is a file when using reftable. We can't reinitialize with
     -+         * a reftable because it will overwrite HEAD
     -+         */
     ++	/*
     ++	 * refs/heads is a file when using reftable. We can't reinitialize with
     ++	 * a reftable because it will overwrite HEAD
     ++	 */
      +	if (reinit && (!strcmp(fmt->ref_storage, "reftable")) ==
      +			      is_directory(git_path_buf(&buf, "refs/heads"))) {
      +		die("cannot switch ref storage format.");
     @@ builtin/init-db.c: static int create_default_files(const char *template_path,
       	/*
       	 * We need to create a "refs" dir in any case so that older
       	 * versions of git can tell that this is a repository.
     - 	 */
     --
     - 	if (refs_init_db(&err))
     - 		die("failed to set up refs db: %s", err.buf);
     - 
      @@ builtin/init-db.c: static int create_default_files(const char *template_path,
       	 * Create the default symlink from ".git/HEAD" to the "master"
       	 * branch, if it does not exist yet.
     @@ builtin/init-db.c: static int create_default_files(const char *template_path,
       	if (!reinit) {
       		if (create_symref("HEAD", "refs/heads/master", NULL) < 0)
       			exit(1);
     --	}
     --
     --	initialize_repository_version(fmt->hash_algo);
     -+	} 
     + 	}
       
     +-	initialize_repository_version(fmt->hash_algo);
      +	initialize_repository_version(fmt->hash_algo, fmt->ref_storage);
     -+        
     + 
       	/* Check filemode trustability */
       	path = git_path_buf(&buf, "config");
     - 	filemode = TEST_FILEMODE;
      @@ builtin/init-db.c: static void validate_hash_algorithm(struct repository_format *repo_fmt, int hash
       }
       
     @@ refs.c: struct ref_store *get_main_ref_store(struct repository *r)
       		BUG("attempting to get main_ref_store outside of repository");
       
      -	r->refs_private = ref_store_init(r->gitdir, REF_STORE_ALL_CAPS);
     -+	r->refs_private = ref_store_init(
     -+                r->gitdir,
     -+                r->ref_storage_format ? r->ref_storage_format : DEFAULT_REF_STORAGE,
     -+                REF_STORE_ALL_CAPS);
     ++	r->refs_private = ref_store_init(r->gitdir,
     ++					 r->ref_storage_format ?
     ++						 r->ref_storage_format :
     ++						 DEFAULT_REF_STORAGE,
     ++					 REF_STORE_ALL_CAPS);
       	return r->refs_private;
       }
       
     @@ refs/reftable-backend.c (new)
      +	unsigned int store_flags;
      +
      +	int err;
     -+        char *repo_dir;
     ++	char *repo_dir;
      +	char *reftable_dir;
      +	struct reftable_stack *stack;
      +};
     @@ refs/reftable-backend.c (new)
      +
      +	base_ref_store_init(ref_store, &refs_be_reftable);
      +	refs->store_flags = store_flags;
     -+        refs->repo_dir = xstrdup(path);
     ++	refs->repo_dir = xstrdup(path);
      +	strbuf_addf(&sb, "%s/reftable", path);
      +	refs->reftable_dir = xstrdup(sb.buf);
      +	strbuf_reset(&sb);
     @@ refs/reftable-backend.c (new)
      +	strbuf_addf(&sb, "%s/refs/heads", refs->repo_dir);
      +	write_file(sb.buf, "this repository uses the reftable format");
      +
     -+        return 0;
     ++	return 0;
      +}
      +
      +struct git_reftable_iterator {
     @@ refs/reftable-backend.c (new)
      +	}
      +
      +	err = reftable_stack_read_ref(refs->stack, refname, &ref);
     -+        if (err > 0) {
     -+                errno = ENOENT;
     -+                err = -1;
     -+                goto exit;
     -+        }
     ++	if (err > 0) {
     ++		errno = ENOENT;
     ++		err = -1;
     ++		goto exit;
     ++	}
      +	if (err < 0) {
     -+                errno = reftable_error_to_errno(err);
     -+                err = -1;
     ++		errno = reftable_error_to_errno(err);
     ++		err = -1;
      +		goto exit;
      +	}
      +	if (ref.target != NULL) {
     @@ refs/reftable-backend.c (new)
      +	} else if (ref.value != NULL) {
      +		hashcpy(oid->hash, ref.value);
      +	} else {
     -+                *type |= REF_ISBROKEN;
     -+                errno = EINVAL;
     -+                err = -1;
     -+        }
     ++		*type |= REF_ISBROKEN;
     ++		errno = EINVAL;
     ++		err = -1;
     ++	}
      +exit:
      +	reftable_ref_record_clear(&ref);
      +	return err;
     @@ refs/reftable-backend.c (new)
      +	reftable_reflog_expire
      +};
      
     - ## reftable/update.sh ##
     -@@ reftable/update.sh: SRC=${SRC:-origin} BRANCH=${BRANCH:-origin/master}
     - cp reftable-repo/c/*.[ch] reftable/
     - cp reftable-repo/c/include/*.[ch] reftable/
     - cp reftable-repo/LICENSE reftable/
     --git --git-dir reftable-repo/.git show --no-patch origin/master \
     -+git --git-dir reftable-repo/.git show --no-patch ${BRANCH} \
     -   > reftable/VERSION
     - 
     - mv reftable/system.h reftable/system.h~
     -
       ## repository.c ##
      @@ repository.c: int repo_init(struct repository *repo,
       	if (worktree)
     @@ t/t0031-reftable.sh (new)
      +	git checkout -b master
      +'
      +
     ++
     ++test_expect_success 'dir/file conflict' '
     ++	initialize &&
     ++	test_commit file &&
     ++	! git branch master/forbidden
     ++'
     ++
     ++
      +test_expect_success 'do not clobber existing repo' '
      +	rm -rf .git &&
      +	git init --ref-storage=files &&
     @@ t/t0031-reftable.sh (new)
      +	test_cmp expect actual
      +'
      +
     ++
      +test_done
     ++
  -:  ----------- > 10:  513d585f0f8 vcxproj: adjust for the reftable changes
 11:  8af67b85e49 ! 11:  846fe29fa4b Add some reftable testing infrastructure
     @@ builtin/init-db.c: static const char *const init_db_usage[] = {
      
       ## refs.c ##
      @@ refs.c: struct ref_store *get_main_ref_store(struct repository *r)
     - 	if (!r->gitdir)
     - 		BUG("attempting to get main_ref_store outside of repository");
     - 
     --	r->refs_private = ref_store_init(
     --                r->gitdir,
     --                r->ref_storage_format ? r->ref_storage_format : DEFAULT_REF_STORAGE,
     --                REF_STORE_ALL_CAPS);
     -+	r->refs_private = ref_store_init(r->gitdir,
     -+					 r->ref_storage_format ?
     -+						 r->ref_storage_format :
     + 	r->refs_private = ref_store_init(r->gitdir,
     + 					 r->ref_storage_format ?
     + 						 r->ref_storage_format :
     +-						 DEFAULT_REF_STORAGE,
      +						 default_ref_storage(),
     -+					 REF_STORE_ALL_CAPS);
     + 					 REF_STORE_ALL_CAPS);
       	return r->refs_private;
       }
     - 
      @@ refs.c: struct ref_store *get_submodule_ref_store(const char *submodule)
       		goto done;

12: b02b83a92ad = 12: a7d1d2e721c t: use update-ref and show-ref to reading/writing refs

gitgitgadget

From: Jonathan Nieder <[email protected]>

Shawn Pearce explains:

Some repositories contain a lot of references (e.g. android at 866k, rails at 31k). The reftable format provides:

- Near constant time lookup for any single reference, even when the repository is cold and not in process or kernel cache.
- Near constant time verification a SHA-1 is referred to by at least one reference (for allow-tip-sha1-in-want).
- Efficient lookup of an entire namespace, such as refs/tags/.
- Support atomic push O(size_of_update) operations.
- Combine reflog storage with ref storage.

This file format spec was originally written in July, 2017 by Shawn Pearce. Some refinements since then were made by Shawn and by Han-Wen Nienhuys based on experiences implementing and experimenting with the format. (All of this was in the context of our work at Google and Google is happy to contribute the result to the Git project.)

Imported from JGit[1]'s current version (c217d33ff, "Documentation/technical/reftable: improve repo layout", 2020-02-04) of Documentation/technical/reftable.md and converted to asciidoc by running

pandoc -t asciidoc -f markdown reftable.md >reftable.txt

using pandoc 2.2.1. The result required the following additional minor changes:

- removed the [TOC] directive to add a table of contents, since asciidoc does not support it
- replaced git-scm.com/docs links with linkgit: directives that link to other pages within Git's documentation

[1] https://eclipse.googlesource.com/jgit/jgit

---
 Documentation/Makefile               |    1 +
 Documentation/technical/reftable.txt | 1067 ++++++++++++++++++++++++++
 2 files changed, 1068 insertions(+)
 create mode 100644 Documentation/technical/reftable.txt

index 15d9d04f316..ecd0b340b1c 100644
@@ -93,6 +93,7 @@ TECH_DOCS += technical/protocol-capabilities
 TECH_DOCS += technical/protocol-common
 TECH_DOCS += technical/protocol-v2
 TECH_DOCS += technical/racy-git
+TECH_DOCS += technical/reftable
 TECH_DOCS += technical/send-pack-pipeline
 TECH_DOCS += technical/shallow
 TECH_DOCS += technical/signature-format

gitgitgadget

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

* Add GIT_TEST_REFTABLE environment var to control default ref storage

* Add test_prerequisite REFTABLE. Skip t/t3210-pack-refs.sh for REFTABLE.

---
 builtin/clone.c      | 2 +-
 builtin/init-db.c    | 2 +-
 refs.c               | 6 +++---
 t/t3210-pack-refs.sh | 6 ++++++
 t/test-lib.sh        | 5 +++++
 5 files changed, 16 insertions(+), 5 deletions(-)

index 4d0cf065e4a..780c5807415 100644
@@ -1109,7 +1109,7 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 	}
 
 	init_db(git_dir, real_git_dir, option_template, GIT_HASH_UNKNOWN,
-		DEFAULT_REF_STORAGE, INIT_DB_QUIET);
+		default_ref_storage(), INIT_DB_QUIET);
 
 	if (real_git_dir)
 		git_dir = real_git_dir;

index b7053b9e370..da5b4670c84 100644
@@ -545,7 +545,7 @@ static const char *const init_db_usage[] = {
 int cmd_init_db(int argc, const char **argv, const char *prefix)
 {
 	const char *git_dir;
-	const char *ref_storage_format = DEFAULT_REF_STORAGE;
+	const char *ref_storage_format = default_ref_storage();
 	const char *real_git_dir = NULL;
 	const char *work_tree;
 	const char *template_dir = NULL;

index 299a5db8bf1..b9b3e7e7070 100644
@@ -1823,7 +1823,7 @@ struct ref_store *get_main_ref_store(struct repository *r)
 	r->refs_private = ref_store_init(r->gitdir,
 					 r->ref_storage_format ?
 						 r->ref_storage_format :
-						 DEFAULT_REF_STORAGE,
+						 default_ref_storage(),
 					 REF_STORE_ALL_CAPS);
 	return r->refs_private;
 }

@@ -1879,7 +1879,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule)
 		goto done;
 
 	/* assume that add_submodule_odb() has been called */
-	refs = ref_store_init(submodule_sb.buf, DEFAULT_REF_STORAGE, /* XXX */
+	refs = ref_store_init(submodule_sb.buf, default_ref_storage(),
 			      REF_STORE_READ | REF_STORE_ODB);
 	register_ref_store_map(&submodule_ref_stores, "submodule",
 			       refs, submodule);

@@ -1893,7 +1893,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule)
 
 struct ref_store *get_worktree_ref_store(const struct worktree *wt)
 {
-	const char *format = DEFAULT_REF_STORAGE; /* XXX */
+	const char *format = default_ref_storage();
 	struct ref_store *refs;
 	const char *id;
 

index f41b2afb996..edaef2c175a 100755
@@ -11,6 +11,12 @@ semantic is still the same.
 '
 . ./test-lib.sh
 
+if test_have_prereq REFTABLE
+then
+  skip_all='skipping pack-refs tests; incompatible with reftable'
+  test_done
+fi
+
 test_expect_success 'enable reflogs' '
 	git config core.logallrefupdates true
 '

index 1b221951a8e..b2b16979407 100644
@@ -1514,6 +1514,11 @@ FreeBSD)
 	;;
 esac
 
+if test -n "$GIT_TEST_REFTABLE"
+then
+  test_set_prereq REFTABLE
+fi
+
 ( COLUMNS=1 && test $COLUMNS = 1 ) && test_set_prereq COLUMNS_CAN_BE_1
 test -z "$NO_PERL" && test_set_prereq PERL
 test -z "$NO_PTHREADS" && test_set_prereq PTHREADS

gitgitgadget

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

For background, see the previous commit introducing the library.

TODO:

* Resolve spots marked with XXX

* Support worktrees (t0002-gitfile "linked repo" testcase)

Example use: see t/t0031-reftable.sh

---
 .../technical/repository-version.txt          |    7 +
 Makefile                                      |   27 +-
 builtin/clone.c                               |    3 +-
 builtin/init-db.c                             |   56 +-
 cache.h                                       |    6 +-
 refs.c                                        |   27 +-
 refs.h                                        |    3 +
 refs/refs-internal.h                          |    1 +
 refs/reftable-backend.c                       | 1045 +++++++++++++++++
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 setup.c                                       |   12 +-
 t/t0031-reftable.sh                           |  109 ++
 13 files changed, 1271 insertions(+), 30 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100755 t/t0031-reftable.sh

index 7844ef30ffd..72576235833 100644
@@ -100,3 +100,10 @@ If set, by default "git config" reads from both "config" and
 multiple working directory mode, "config" file is shared while
 "config.worktree" is per-working directory (i.e., it's in
 GIT_COMMON_DIR/worktrees/<id>/config.worktree)
+
+==== `refStorage`
+
+Specifies the file format for the ref database. Values are `files`
+(for the traditional packed + loose ref format) and `reftable` for the
+binary reftable format. See https://github.com/google/reftable for
+more information.

index 3d3a39fc192..f4848a382f4 100644
@@ -810,6 +810,7 @@ TEST_SHELL_PATH = $(SHELL_PATH)
 LIB_FILE = libgit.a
 XDIFF_LIB = xdiff/lib.a
 VCSSVN_LIB = vcs-svn/lib.a
+REFTABLE_LIB = reftable/libreftable.a
 
 GENERATED_H += config-list.h
 GENERATED_H += command-list.h

@@ -962,6 +963,7 @@ LIB_OBJS += ref-filter.o
 LIB_OBJS += reflog-walk.o
 LIB_OBJS += refs.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

@@ -1165,7 +1167,7 @@ THIRD_PARTY_SOURCES += compat/regex/%
 THIRD_PARTY_SOURCES += sha1collisiondetection/%
 THIRD_PARTY_SOURCES += sha1dc/%
 
-GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB)
+GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB)
 EXTLIBS =
 
 GIT_USER_AGENT = git/$(GIT_VERSION)

@@ -2360,11 +2362,29 @@ VCSSVN_OBJS += vcs-svn/sliding_window.o
 VCSSVN_OBJS += vcs-svn/svndiff.o
 VCSSVN_OBJS += vcs-svn/svndump.o
 
+REFTABLE_OBJS += reftable/basics.o
+REFTABLE_OBJS += reftable/block.o
+REFTABLE_OBJS += reftable/file.o
+REFTABLE_OBJS += reftable/iter.o
+REFTABLE_OBJS += reftable/merged.o
+REFTABLE_OBJS += reftable/pq.o
+REFTABLE_OBJS += reftable/reader.o
+REFTABLE_OBJS += reftable/record.o
+REFTABLE_OBJS += reftable/refname.o
+REFTABLE_OBJS += reftable/reftable.o
+REFTABLE_OBJS += reftable/slice.o
+REFTABLE_OBJS += reftable/stack.o
+REFTABLE_OBJS += reftable/tree.o
+REFTABLE_OBJS += reftable/writer.o
+REFTABLE_OBJS += reftable/zlib-compat.o
+
+
 TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
 OBJECTS := $(LIB_OBJS) $(BUILTIN_OBJS) $(PROGRAM_OBJS) $(TEST_OBJS) \
 	$(XDIFF_OBJS) \
 	$(VCSSVN_OBJS) \
 	$(FUZZ_OBJS) \
+	$(REFTABLE_OBJS) \
 	common-main.o \
 	git.o
 ifndef NO_CURL

@@ -2505,6 +2525,9 @@ $(XDIFF_LIB): $(XDIFF_OBJS)
 $(VCSSVN_LIB): $(VCSSVN_OBJS)
 	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
 
+$(REFTABLE_LIB): $(REFTABLE_OBJS)
+	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
+
 export DEFAULT_EDITOR DEFAULT_PAGER
 
 Documentation/GIT-EXCLUDED-PROGRAMS: FORCE

@@ -3120,7 +3143,7 @@ cocciclean:
 clean: profile-clean coverage-clean cocciclean
 	$(RM) *.res
 	$(RM) $(OBJECTS)
-	$(RM) $(LIB_FILE) $(XDIFF_LIB) $(VCSSVN_LIB)
+	$(RM) $(LIB_FILE) $(XDIFF_LIB) $(VCSSVN_LIB) $(REFTABLE_LIB)
 	$(RM) $(ALL_PROGRAMS) $(SCRIPT_LIB) $(BUILT_INS) git$X
 	$(RM) $(TEST_PROGRAMS)
 	$(RM) $(FUZZ_PROGRAMS)

index cb48a291caf..4d0cf065e4a 100644
@@ -1108,7 +1108,8 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 		}
 	}
 
-	init_db(git_dir, real_git_dir, option_template, GIT_HASH_UNKNOWN, INIT_DB_QUIET);
+	init_db(git_dir, real_git_dir, option_template, GIT_HASH_UNKNOWN,
+		DEFAULT_REF_STORAGE, INIT_DB_QUIET);
 
 	if (real_git_dir)
 		git_dir = real_git_dir;

index 0f0485ecfe2..8cb884773c3 100644
@@ -628,8 +628,9 @@ int path_inside_repo(const char *prefix, const char *path);
 
 int init_db(const char *git_dir, const char *real_git_dir,
 	    const char *template_dir, int hash_algo,
-	    unsigned int flags);
-void initialize_repository_version(int hash_algo);
+	    const char *ref_storage_format, unsigned int flags);
+void initialize_repository_version(int hash_algo,
+				   const char *ref_storage_format);
 
 void sanitize_stdfds(void);
 int daemonize(void);

@@ -1043,6 +1044,7 @@ struct repository_format {
 	int is_bare;
 	int hash_algo;
 	char *work_tree;
+	char *ref_storage;
 	struct string_list unknown_extensions;
 };
 

index 4db27379661..299a5db8bf1 100644
@@ -17,10 +17,16 @@
 #include "argv-array.h"
 #include "repository.h"
 
+const char *default_ref_storage(void)
+{
+	const char *test = getenv("GIT_TEST_REFTABLE");
+	return test ? "reftable" : "files";
+}
+
 /*
  * List of all available backends
  */
-static struct ref_storage_be *refs_backends = &refs_be_files;
+static struct ref_storage_be *refs_backends = &refs_be_reftable;
 
 static struct ref_storage_be *find_ref_storage_backend(const char *name)
 {

@@ -1792,13 +1798,13 @@ static struct ref_store *lookup_ref_store_map(struct hashmap *map,
  * Create, record, and return a ref_store instance for the specified
  * gitdir.
  */
-static struct ref_store *ref_store_init(const char *gitdir,
+static struct ref_store *ref_store_init(const char *gitdir, const char *be_name,
 					unsigned int flags)
 {
-	const char *be_name = "files";
-	struct ref_storage_be *be = find_ref_storage_backend(be_name);
+	struct ref_storage_be *be;
 	struct ref_store *refs;
 
+	be = find_ref_storage_backend(be_name);
 	if (!be)
 		BUG("reference backend %s is unknown", be_name);
 

@@ -1814,7 +1820,11 @@ struct ref_store *get_main_ref_store(struct repository *r)
 	if (!r->gitdir)
 		BUG("attempting to get main_ref_store outside of repository");
 
-	r->refs_private = ref_store_init(r->gitdir, REF_STORE_ALL_CAPS);
+	r->refs_private = ref_store_init(r->gitdir,
+					 r->ref_storage_format ?
+						 r->ref_storage_format :
+						 DEFAULT_REF_STORAGE,
+					 REF_STORE_ALL_CAPS);
 	return r->refs_private;
 }
 

@@ -1869,7 +1879,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule)
 		goto done;
 
 	/* assume that add_submodule_odb() has been called */
-	refs = ref_store_init(submodule_sb.buf,
+	refs = ref_store_init(submodule_sb.buf, DEFAULT_REF_STORAGE, /* XXX */
 			      REF_STORE_READ | REF_STORE_ODB);
 	register_ref_store_map(&submodule_ref_stores, "submodule",
 			       refs, submodule);

@@ -1883,6 +1893,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule)
 
 struct ref_store *get_worktree_ref_store(const struct worktree *wt)
 {
+	const char *format = DEFAULT_REF_STORAGE; /* XXX */
 	struct ref_store *refs;
 	const char *id;
 

@@ -1896,9 +1907,9 @@ struct ref_store *get_worktree_ref_store(const struct worktree *wt)
 
 	if (wt->id)
 		refs = ref_store_init(git_common_path("worktrees/%s", wt->id),
-				      REF_STORE_ALL_CAPS);
+				      format, REF_STORE_ALL_CAPS);
 	else
-		refs = ref_store_init(get_git_common_dir(),
+		refs = ref_store_init(get_git_common_dir(), format,
 				      REF_STORE_ALL_CAPS);
 
 	if (refs)

index 9421c5b8465..15f6d78ee84 100644
@@ -9,6 +9,9 @@ struct string_list;
 struct string_list_item;
 struct worktree;
 
+/* Returns the ref storage backend to use by default. */
+const char *default_ref_storage(void);
+
 /*
  * Resolve a reference, recursively following symbolic refererences.
  *

index 3490aac3a40..cafe5b97376 100644
@@ -661,6 +661,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;
 
 /*

index 6f7f6f002b1..087760bc184 100644
@@ -178,6 +178,8 @@ int repo_init(struct repository *repo,
 	if (worktree)
 		repo_set_worktree(repo, worktree);
 
+	repo->ref_storage_format = xstrdup_or_null(format.ref_storage);
+
 	clear_repository_format(&format);
 	return 0;
 

index 6534fbb7b31..f57b73f4a27 100644
@@ -74,6 +74,9 @@ struct repository {
 	 */
 	struct ref_store *refs_private;
 
+	/* The format to use for the ref database. */
+	char *ref_storage_format;
+
 	/*
 	 * Contains path to often used file names.
 	 */

index 65fe5ecefbe..2ef970f9f88 100644
@@ -468,9 +468,11 @@ static int check_repo_format(const char *var, const char *value, void *vdata)
 			if (!value)
 				return config_error_nonbool(var);
 			data->partial_clone = xstrdup(value);
-		} else if (!strcmp(ext, "worktreeconfig"))
+		} else if (!strcmp(ext, "worktreeconfig")) {
 			data->worktree_config = git_config_bool(var, value);
-		else
+		} else if (!strcmp(ext, "refstorage")) {
+			data->ref_storage = xstrdup(value);
+		} else
 			string_list_append(&data->unknown_extensions, ext);
 	}
 

@@ -559,6 +561,7 @@ void clear_repository_format(struct repository_format *format)
 	string_list_clear(&format->unknown_extensions, 0);
 	free(format->work_tree);
 	free(format->partial_clone);
+	free(format->ref_storage);
 	init_repository_format(format);
 }
 

@@ -1204,8 +1207,11 @@ const char *setup_git_directory_gently(int *nongit_ok)
 				gitdir = DEFAULT_GIT_DIR_ENVIRONMENT;
 			setup_git_env(gitdir);
 		}
-		if (startup_info->have_repository)
+		if (startup_info->have_repository) {
 			repo_set_hash_algo(the_repository, repo_fmt.hash_algo);
+			the_repository->ref_storage_format =
+				xstrdup_or_null(repo_fmt.ref_storage);
+		}
 	}
 
 	strbuf_release(&dir);

gitgitgadget

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

Reading and writing .git/refs/* assumes that refs are stored in the 'files' ref backend.

---
 t/t0002-gitfile.sh             |  2 +-
 t/t1400-update-ref.sh          | 32 ++++++++++++++++----------------
 t/t1506-rev-parse-diagnosis.sh |  2 +-
 t/t6050-replace.sh             |  2 +-
 t/t9020-remote-svn.sh          |  4 ++--
 5 files changed, 21 insertions(+), 21 deletions(-)

index 0aa9908ea12..960ed150cb5 100755
@@ -62,7 +62,7 @@ test_expect_success 'check commit-tree' '
 '
 
 test_expect_success 'check rev-list' '
-	echo $SHA >"$REAL/HEAD" &&
+	git update-ref "HEAD" "$SHA" &&
 	test "$SHA" = "$(git rev-list HEAD)"
 '
 

index e1197ac8189..27171f82612 100755
@@ -37,15 +37,15 @@ test_expect_success setup '
 
 test_expect_success "create $m" '
 	git update-ref $m $A &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 test_expect_success "create $m with oldvalue verification" '
 	git update-ref $m $B $A &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "fail to delete $m with stale ref" '
 	test_must_fail git update-ref -d $m $A &&
-	test $B = "$(cat .git/$m)"
+	test $B = "$(git show-ref -s --verify $m)"
 '
 test_expect_success "delete $m" '
 	test_when_finished "rm -f .git/$m" &&

@@ -56,7 +56,7 @@ test_expect_success "delete $m" '
 test_expect_success "delete $m without oldvalue verification" '
 	test_when_finished "rm -f .git/$m" &&
 	git update-ref $m $A &&
-	test $A = $(cat .git/$m) &&
+	test $A = $(git show-ref -s --verify $m) &&
 	git update-ref -d $m &&
 	test_path_is_missing .git/$m
 '

@@ -69,15 +69,15 @@ test_expect_success "fail to create $n" '
 
 test_expect_success "create $m (by HEAD)" '
 	git update-ref HEAD $A &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 test_expect_success "create $m (by HEAD) with oldvalue verification" '
 	git update-ref HEAD $B $A &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "fail to delete $m (by HEAD) with stale ref" '
 	test_must_fail git update-ref -d HEAD $A &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "delete $m (by HEAD)" '
 	test_when_finished "rm -f .git/$m" &&

@@ -178,14 +178,14 @@ test_expect_success '--no-create-reflog overrides core.logAllRefUpdates=always'
 
 test_expect_success "create $m (by HEAD)" '
 	git update-ref HEAD $A &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 test_expect_success 'pack refs' '
 	git pack-refs --all
 '
 test_expect_success "move $m (by HEAD)" '
 	git update-ref HEAD $B $A &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "delete $m (by HEAD) should remove both packed and loose $m" '
 	test_when_finished "rm -f .git/$m" &&

@@ -255,7 +255,7 @@ test_expect_success '(not) change HEAD with wrong SHA1' '
 '
 test_expect_success "(not) changed .git/$m" '
 	test_when_finished "rm -f .git/$m" &&
-	! test $B = $(cat .git/$m)
+	! test $B = $(git show-ref -s --verify $m)
 '
 
 rm -f .git/logs/refs/heads/master

@@ -263,19 +263,19 @@ test_expect_success "create $m (logged by touch)" '
 	test_config core.logAllRefUpdates false &&
 	GIT_COMMITTER_DATE="2005-05-26 23:30" \
 	git update-ref --create-reflog HEAD $A -m "Initial Creation" &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 test_expect_success "update $m (logged by touch)" '
 	test_config core.logAllRefUpdates false &&
 	GIT_COMMITTER_DATE="2005-05-26 23:31" \
 	git update-ref HEAD $B $A -m "Switch" &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "set $m (logged by touch)" '
 	test_config core.logAllRefUpdates false &&
 	GIT_COMMITTER_DATE="2005-05-26 23:41" \
 	git update-ref HEAD $A &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 
 test_expect_success 'empty directory removal' '

@@ -319,19 +319,19 @@ test_expect_success "create $m (logged by config)" '
 	test_config core.logAllRefUpdates true &&
 	GIT_COMMITTER_DATE="2005-05-26 23:32" \
 	git update-ref HEAD $A -m "Initial Creation" &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 test_expect_success "update $m (logged by config)" '
 	test_config core.logAllRefUpdates true &&
 	GIT_COMMITTER_DATE="2005-05-26 23:33" \
 	git update-ref HEAD'" $B $A "'-m "Switch" &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "set $m (logged by config)" '
 	test_config core.logAllRefUpdates true &&
 	GIT_COMMITTER_DATE="2005-05-26 23:43" \
 	git update-ref HEAD $A &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 
 cat >expect <<EOF

index 52edcbdcc32..dbf690b9c1b 100755
@@ -207,7 +207,7 @@ test_expect_success 'arg before dashdash must be a revision (ambiguous)' '
 	{
 		# we do not want to use rev-parse here, because
 		# we are testing it
-		cat .git/refs/heads/foobar &&
+		git show-ref -s refs/heads/foobar &&
 		printf "%s\n" --
 	} >expect &&
 	git rev-parse foobar -- >actual &&

index e7e64e085dd..c80dc10b8f1 100755
@@ -135,7 +135,7 @@ test_expect_success 'tag replaced commit' '
 test_expect_success '"git fsck" works' '
      git fsck master >fsck_master.out &&
      test_i18ngrep "dangling commit $R" fsck_master.out &&
-     test_i18ngrep "dangling tag $(cat .git/refs/tags/mytag)" fsck_master.out &&
+     test_i18ngrep "dangling tag $(git show-ref -s refs/tags/mytag)" fsck_master.out &&
      test -z "$(git fsck)"
 '
 

index 6fca08e5e35..9fcfa969a9b 100755
@@ -48,8 +48,8 @@ test_expect_success REMOTE_SVN 'simple fetch' '
 '
 
 test_debug '
-	cat .git/refs/svn/svnsim/master
-	cat .git/refs/remotes/svnsim/master
+	git show-ref -s refs/svn/svnsim/master
+	git show-ref -s refs/remotes/svnsim/master
 '
 
 test_expect_success REMOTE_SVN 'repeated fetch, nothing shall change' '

gitgitgadget

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

Reftable is a format for storing the ref database. Its rationale and specification is in the preceding commit.

This imports the upstream library as one big commit. For understanding the code, it is suggested to read the code in the following order:

* The specification under Documentation/technical/reftable.txt

* reftable.h - the public API

* record.{c,h} - reading and writing records

* block.{c,h} - reading and writing blocks.

* writer.{c,h} - writing a complete reftable file.

* merged.{c,h} and pq.{c,h} - reading a stack of reftables

* stack.{c,h} - writing and compacting stacks of reftable on the filesystem.

---
 reftable/LICENSE       |   31 +
 reftable/README.md     |   11 +
 reftable/VERSION       |    5 +
 reftable/basics.c      |  215 +++++++
 reftable/basics.h      |   53 ++
 reftable/block.c       |  436 ++++++++++++++
 reftable/block.h       |  126 ++++
 reftable/blocksource.h |   22 +
 reftable/constants.h   |   21 +
 reftable/file.c        |   99 ++++
 reftable/iter.c        |  240 ++++++++
 reftable/iter.h        |   63 ++
 reftable/merged.c      |  327 +++++++++++
 reftable/merged.h      |   38 ++
 reftable/pq.c          |  115 ++++
 reftable/pq.h          |   34 ++
 reftable/reader.c      |  758 +++++++++++++++++++++++++
 reftable/reader.h      |   68 +++
 reftable/record.c      | 1131 ++++++++++++++++++++++++++++++++++++
 reftable/record.h      |  121 ++++
 reftable/refname.c     |  215 +++++++
 reftable/refname.h     |   39 ++
 reftable/reftable.c    |   91 +++
 reftable/reftable.h    |  564 ++++++++++++++++++
 reftable/slice.c       |  225 ++++++++
 reftable/slice.h       |   76 +++
 reftable/stack.c       | 1229 ++++++++++++++++++++++++++++++++++++++++
 reftable/stack.h       |   45 ++
 reftable/system.h      |   54 ++
 reftable/tree.c        |   67 +++
 reftable/tree.h        |   34 ++
 reftable/update.sh     |   24 +
 reftable/writer.c      |  661 +++++++++++++++++++++
 reftable/writer.h      |   60 ++
 reftable/zlib-compat.c |   92 +++
 35 files changed, 7390 insertions(+)
 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/constants.h
 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/refname.c
 create mode 100644 reftable/refname.h
 create mode 100644 reftable/reftable.c
 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 100755 reftable/update.sh
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 reftable/zlib-compat.c

new file mode 100644
index 00000000000..402e0f9356b
@@ -0,0 +1,31 @@
+BSD License
+
+Copyright (c) 2020, Google LLC
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+* Redistributions of source code must retain the above copyright notice,
+this list of conditions and the following disclaimer.
+
+* Redistributions in binary form must reproduce the above copyright
+notice, this list of conditions and the following disclaimer in the
+documentation and/or other materials provided with the distribution.
+
+* Neither the name of Google LLC nor the names of its contributors may
+be used to endorse or promote products derived from this software
+without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

new file mode 100644
index 00000000000..21500563fd4
@@ -0,0 +1,11 @@
+
+The source code in this directory comes from https://github.com/google/reftable.
+
+The VERSION file keeps track of the current version of the reftable library.
+
+To update the library, do:
+
+   sh reftable/update.sh
+
+Bugfixes should be accompanied by a test and applied to upstream project at
+https://github.com/google/reftable.

new file mode 100644
index 00000000000..b947a05c089
@@ -0,0 +1,5 @@
+commit 3a486f79abcd17e88e3bca62f43188a7c8b80ff3
+Author: Han-Wen Nienhuys <[email protected]>
+Date:   Mon May 4 19:20:21 2020 +0200
+
+    C: include "cache.h" in git-core sleep_millisec()

new file mode 100644
index 00000000000..1fdf0bf4557
@@ -0,0 +1,22 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef BLOCKSOURCE_H
+#define BLOCKSOURCE_H
+
+#include "reftable.h"
+
+uint64_t block_source_size(struct reftable_block_source source);
+int block_source_read_block(struct reftable_block_source source,
+			    struct reftable_block *dest, uint64_t off,
+			    uint32_t size);
+void block_source_return_block(struct reftable_block_source source,
+			       struct reftable_block *ret);
+void block_source_close(struct reftable_block_source source);
+
+#endif

new file mode 100644
index 00000000000..5eee72c4c11
@@ -0,0 +1,21 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef CONSTANTS_H
+#define CONSTANTS_H
+
+#define BLOCK_TYPE_LOG 'g'
+#define BLOCK_TYPE_INDEX 'i'
+#define BLOCK_TYPE_REF 'r'
+#define BLOCK_TYPE_OBJ 'o'
+#define BLOCK_TYPE_ANY 0
+
+#define MAX_RESTARTS ((1 << 16) - 1)
+#define DEFAULT_BLOCK_SIZE 4096
+
+#endif

new file mode 100644
index 00000000000..a71f36ecbae
@@ -0,0 +1,38 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef MERGED_H
+#define MERGED_H
+
+#include "pq.h"
+#include "reftable.h"
+
+struct reftable_merged_table {
+	struct reftable_reader **stack;
+	int stack_len;
+	uint32_t hash_id;
+	bool suppress_deletions;
+
+	uint64_t min;
+	uint64_t max;
+};
+
+struct merged_iter {
+	struct reftable_iterator *stack;
+	uint32_t hash_id;
+	int stack_len;
+	byte typ;
+	bool suppress_deletions;
+	struct merged_iter_pqueue pq;
+};
+
+void merged_table_clear(struct reftable_merged_table *mt);
+int merged_table_seek_record(struct reftable_merged_table *mt,
+			     struct reftable_iterator *it, struct record rec);
+
+#endif

new file mode 100644
index 00000000000..b585a52ee14
@@ -0,0 +1,34 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef PQ_H
+#define PQ_H
+
+#include "record.h"
+
+struct pq_entry {
+	int index;
+	struct record rec;
+};
+
+int pq_less(struct pq_entry a, struct pq_entry b);
+
+struct merged_iter_pqueue {
+	struct pq_entry *heap;
+	int len;
+	int cap;
+};
+
+struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);
+bool merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);
+void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
+struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e);
+void merged_iter_pqueue_clear(struct merged_iter_pqueue *pq);
+
+#endif

new file mode 100644
index 00000000000..e0c40b7fa9e

new file mode 100644
index 00000000000..954512e9a3a

new file mode 100755
index 00000000000..ef32aeda515

gitgitgadget

Part of the diff is not shown here. View the raw message.

A large source of test failures of the reftable patch series is the handling of pseudo refs (HEAD, CHERRY_PICK_HEAD etc.)

These are written as

  if (ref_type(refname) == REF_TYPE_PSEUDOREF) {
    assert(refs == get_main_ref_store(the_repository));
    ret = write_pseudoref(refname, new_oid, old_oid, &err);
  } else {
    t = ref_store_transaction_begin(refs, &err);
    ..

write_pseudoref writes a file directly to the .git/ directory.

However, on read (for example, CHERRY_PICK_HEAD), the pseudo ref is given to lookup_commit_reference_by_name, which in the end calls refs_resolve_ref_unsafe(). If reftable is active, the pseudo ref isn't read from .git/CHERRY_PICK_HEAD.

If the pseudo refs are read through a ref backend, shouldn't they be written through a ref backend too?

This causes all rebase and all cherry-pick tests to fail with reftable.

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, Halimah DeLaine Prado

I queued this to 'pu', and we are seeing

    https://github.com/git/git/runs/648285159

The ci/run-static-analysis.sh job's failure report ends like so:

HDR reftable/record.h
HDR reftable/refname.h
HDR reftable/reftable.h
HDR reftable/slice.h
HDR reftable/stack.h
HDR reftable/system.h
HDR reftable/tree.h
HDR reftable/writer.h
HDR remote.h
In file included from reftable/refname.hcc:2:0:
./reftable/refname.h:12:24: error: field ‘tab’ has incomplete type

  struct reftable_table tab;
                        ^~~
./reftable/refname.h:32:13: error: ‘struct reftable_ref_record’ declared inside parameter list will not be visible outside of this definition or declaration [-Werror]
      struct reftable_ref_record *recs, size_t sz);
             ^~~~~~~~~~~~~~~~~~~

cc1: all warnings being treated as errors
make: *** [reftable/refname.hco] Error 1 Makefile:2842: recipe for target 'reftable/refname.hco' failed
make: *** Waiting for unfinished jobs....

Thanks.

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

---
 refs.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

index a92d2c74c83..9421c5b8465 100644
@@ -432,18 +432,21 @@ int delete_refs(const char *msg, struct string_list *refnames,
 int refs_delete_reflog(struct ref_store *refs, const char *refname);
 int delete_reflog(const char *refname);
 
-/* iterate over reflog entries */
+/* Iterate over reflog entries. */
 typedef int each_reflog_ent_fn(
 		struct object_id *old_oid, struct object_id *new_oid,
 		const char *committer, timestamp_t timestamp,
 		int tz, const char *msg, void *cb_data);
 
+/* Iterate in over reflog entries, oldest entry first. */
 int refs_for_each_reflog_ent(struct ref_store *refs, const char *refname,
 			     each_reflog_ent_fn fn, void *cb_data);
 int refs_for_each_reflog_ent_reverse(struct ref_store *refs,
 				     const char *refname,
 				     each_reflog_ent_fn fn,
 				     void *cb_data);
+
+/* Call a function for each reflog entry, oldest entry first. */
 int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_data);
 int for_each_reflog_ent_reverse(const char *refname, each_reflog_ent_fn fn, void *cb_data);
 

gitgitgadget

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

This happens implicitly in the files/packed ref backend; making it explicit simplifies adding alternate ref storage backends, such as reftable.

---
 refs.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

index 224ff66c7bb..4db27379661 100644
@@ -1525,7 +1525,7 @@ static int do_for_each_ref(struct ref_store *refs, const char *prefix,
 
 int refs_for_each_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref(refs, "", fn, 0, 0, cb_data);
+	return do_for_each_ref(refs, "refs/", fn, 0, 0, cb_data);
 }
 
 int for_each_ref(each_ref_fn fn, void *cb_data)

@@ -1585,8 +1585,8 @@ int for_each_namespaced_ref(each_ref_fn fn, void *cb_data)
 
 int refs_for_each_rawref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
 {
-	return do_for_each_ref(refs, "", fn, 0,
-			       DO_FOR_EACH_INCLUDE_BROKEN, cb_data);
+	return do_for_each_ref(refs, "refs/", fn, 0, DO_FOR_EACH_INCLUDE_BROKEN,
+			       cb_data);
 }
 
 int for_each_rawref(each_ref_fn fn, void *cb_data)

gitgitgadget

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

---
 refs/refs-internal.h | 5 +++++
 1 file changed, 5 insertions(+)

index ff2436c0fb7..3490aac3a40 100644
@@ -438,6 +438,11 @@ void base_ref_iterator_free(struct ref_iterator *iter);
 
 /* Virtual function declarations for ref_iterators: */
 
+/*
+ * backend-specific implementation of ref_iterator_advance.
+ * For symrefs, the function should set REF_ISSYMREF, and it should also
+ * dereference the symref to provide the OID referent.
+ */
 typedef int ref_iterator_advance_fn(struct ref_iterator *ref_iterator);
 
 typedef int ref_iterator_peel_fn(struct ref_iterator *ref_iterator,

gitgitgadget

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

---
 Documentation/technical/reftable.txt | 50 ++++++++++++++++------------
 1 file changed, 28 insertions(+), 22 deletions(-)

index 9fa4657d9ff..ee3f36ea851 100644
@@ -193,8 +193,8 @@ and non-aligned files.
 Very small files (e.g. 1 only ref block) may omit `padding` and the ref
 index to reduce total file size.
 
-Header
-^^^^^^
+Header (version 1)
+^^^^^^^^^^^^^^^^^^
 
 A 24-byte header appears at the beginning of the file:
 

@@ -215,6 +215,24 @@ used in a stack for link:#Update-transactions[transactions], these
 fields can order the files such that the prior file’s
 `max_update_index + 1` is the next file’s `min_update_index`.
 
+Header (version 2)
+^^^^^^^^^^^^^^^^^^
+
+A 28-byte header appears at the beginning of the file:
+
+....
+'REFT'
+uint8( version_number = 1 )
+uint24( block_size )
+uint64( min_update_index )
+uint64( max_update_index )
+uint32( hash_id )
+....
+
+The header is identical to `version_number=1`, with the 4-byte hash ID
+("sha1" for SHA1 and "s256" for SHA-256) append to the header.
+
+
 First ref block
 ^^^^^^^^^^^^^^^
 

@@ -671,14 +689,8 @@ Footer
 After the last block of the file, a file footer is written. It begins
 like the file header, but is extended with additional data.
 
-A 68-byte footer appears at the end:
-
 ....
-    'REFT'
-    uint8( version_number = 1 )
-    uint24( block_size )
-    uint64( min_update_index )
-    uint64( max_update_index )
+    HEADER
 
     uint64( ref_index_position )
     uint64( (obj_position << 5) | obj_id_len )

@@ -701,12 +713,16 @@ obj blocks.
 * `obj_index_position`: byte position for the start of the obj index.
 * `log_index_position`: byte position for the start of the log index.
 
+The size of the footer is 68 bytes for version 1, and 72 bytes for
+version 2.
+
 Reading the footer
 ++++++++++++++++++
 
-Readers must seek to `file_length - 68` to access the footer. A trusted
-external source (such as `stat(2)`) is necessary to obtain
-`file_length`. When reading the footer, readers must verify:
+Readers must first read the file start to determine the version
+number. Then they seek to `file_length - FOOTER_LENGTH` to access the
+footer. A trusted external source (such as `stat(2)`) is necessary to
+obtain `file_length`. When reading the footer, readers must verify:
 
 * 4-byte magic is correct
 * 1-byte version number is recognized

@@ -1055,13 +1071,3 @@ impossible.
 
 A common format that can be supported by all major Git implementations
 (git-core, JGit, libgit2) is strongly preferred.
-
-Future
-~~~~~~
-
-Longer hashes
-^^^^^^^^^^^^^
-
-Version will bump (e.g. 2) to indicate `value` uses a different object
-id length other than 20. The length could be stored in an expanded file
-header, or hardcoded as part of the version.

gitgitgadget

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

The format allows for some ambiguity, as a lone footer also starts with a valid file header. However, the current JGit code will barf on this. This commit codifies this behavior into the standard.

---
 Documentation/technical/reftable.txt | 7 +++++++
 1 file changed, 7 insertions(+)

index ee3f36ea851..df5cb5f11b8 100644
@@ -731,6 +731,13 @@ version)
 
 Once verified, the other fields of the footer can be accessed.
 
+Empty tables
+++++++++++++
+
+A reftable may be empty. In this case, the file starts with a header
+and is immediately followed by a footer.
+
+
 Varint encoding
 ^^^^^^^^^^^^^^^
 

gitgitgadget

From: Jonathan Nieder <[email protected]>

Shawn Pearce explains:

Some repositories contain a lot of references (e.g. android at 866k, rails at 31k). The reftable format provides:

- Near constant time lookup for any single reference, even when the repository is cold and not in process or kernel cache.
- Near constant time verification a SHA-1 is referred to by at least one reference (for allow-tip-sha1-in-want).
- Efficient lookup of an entire namespace, such as refs/tags/.
- Support atomic push O(size_of_update) operations.
- Combine reflog storage with ref storage.

This file format spec was originally written in July, 2017 by Shawn Pearce. Some refinements since then were made by Shawn and by Han-Wen Nienhuys based on experiences implementing and experimenting with the format. (All of this was in the context of our work at Google and Google is happy to contribute the result to the Git project.)

Imported from JGit[1]'s current version (c217d33ff, "Documentation/technical/reftable: improve repo layout", 2020-02-04) of Documentation/technical/reftable.md and converted to asciidoc by running

pandoc -t asciidoc -f markdown reftable.md >reftable.txt

using pandoc 2.2.1. The result required the following additional minor changes:

- removed the [TOC] directive to add a table of contents, since asciidoc does not support it
- replaced git-scm.com/docs links with linkgit: directives that link to other pages within Git's documentation

[1] https://eclipse.googlesource.com/jgit/jgit

---
 Documentation/Makefile               |    1 +
 Documentation/technical/reftable.txt | 1067 ++++++++++++++++++++++++++
 2 files changed, 1068 insertions(+)
 create mode 100644 Documentation/technical/reftable.txt

index 15d9d04f316..ecd0b340b1c 100644
@@ -93,6 +93,7 @@ TECH_DOCS += technical/protocol-capabilities
 TECH_DOCS += technical/protocol-common
 TECH_DOCS += technical/protocol-v2
 TECH_DOCS += technical/racy-git
+TECH_DOCS += technical/reftable
 TECH_DOCS += technical/send-pack-pipeline
 TECH_DOCS += technical/shallow
 TECH_DOCS += technical/signature-format

gitgitgadget

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

---
 reftable/.gitattributes | 1 +
 1 file changed, 1 insertion(+)
 create mode 100644 reftable/.gitattributes

new file mode 100644
index 00000000000..f44451a3795
@@ -0,0 +1 @@
+/zlib-compat.c	whitespace=-indent-with-non-tab,-trailing-space

gitgitgadget

From: Johannes Schindelin <[email protected]>

This allows Git to be compiled via Visual Studio again after integrating the hn/reftable branch.

---
 config.mak.uname                           |  2 +-
 contrib/buildsystems/Generators/Vcxproj.pm | 11 ++++++++++-
 2 files changed, 11 insertions(+), 2 deletions(-)

index 5ad43c80b1a..484aec15ac2 100644
@@ -710,7 +710,7 @@ vcxproj:
 	# Make .vcxproj files and add them
 	unset QUIET_GEN QUIET_BUILT_IN; \
 	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 5c666f9ac03..33a08d31652 100644
@@ -77,7 +77,7 @@ sub createProject {
     my $libs_release = "\n    ";
     my $libs_debug = "\n    ";
     if (!$static_library) {
-      $libs_release = join(";", sort(grep /^(?!libgit\.lib|xdiff\/lib\.lib|vcs-svn\/lib\.lib)/, @{$$build_structure{"$prefix${name}_LIBS"}}));
+      $libs_release = join(";", sort(grep /^(?!libgit\.lib|xdiff\/lib\.lib|vcs-svn\/lib\.lib|reftable\/libreftable\.lib)/, @{$$build_structure{"$prefix${name}_LIBS"}}));
       $libs_debug = $libs_release;
       $libs_debug =~ s/zlib\.lib/zlibd\.lib/g;
       $libs_debug =~ s/libcurl\.lib/libcurl-d\.lib/g;

@@ -231,6 +231,7 @@ sub createProject {
 EOM
     if (!$static_library || $target =~ 'vcs-svn' || $target =~ 'xdiff') {
       my $uuid_libgit = $$build_structure{"LIBS_libgit_GUID"};
+      my $uuid_libreftable = $$build_structure{"LIBS_reftable/libreftable_GUID"};
       my $uuid_xdiff_lib = $$build_structure{"LIBS_xdiff/lib_GUID"};
 
       print F << "EOM";

@@ -240,6 +241,14 @@ sub createProject {
       <ReferenceOutputAssembly>false</ReferenceOutputAssembly>
     </ProjectReference>
 EOM
+      if (!($name =~ /xdiff|libreftable/)) {
+        print F << "EOM";
+    <ProjectReference Include="$cdup\\reftable\\libreftable\\libreftable.vcxproj">
+      <Project>$uuid_libreftable</Project>
+      <ReferenceOutputAssembly>false</ReferenceOutputAssembly>
+    </ProjectReference>
+EOM
+      }
       if (!($name =~ 'xdiff')) {
         print F << "EOM";
     <ProjectReference Include="$cdup\\xdiff\\lib\\xdiff_lib.vcxproj">

gitgitgadget

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

For background, see the previous commit introducing the library.

This introduces the refs/reftable-backend.c containing reftable powered ref storage backend.

It can be activated by passing --ref-storage=reftable to "git init".

TODO:

* Resolve spots marked with XXX

Example use: see t/t0031-reftable.sh

---
 .../technical/repository-version.txt          |    7 +
 Makefile                                      |   27 +-
 builtin/clone.c                               |    3 +-
 builtin/init-db.c                             |   56 +-
 cache.h                                       |    6 +-
 refs.c                                        |   27 +-
 refs.h                                        |    3 +
 refs/refs-internal.h                          |    1 +
 refs/reftable-backend.c                       | 1045 +++++++++++++++++
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 setup.c                                       |   12 +-
 t/t0031-reftable.sh                           |  109 ++
 13 files changed, 1271 insertions(+), 30 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100755 t/t0031-reftable.sh

index 7844ef30ffd..72576235833 100644
@@ -100,3 +100,10 @@ If set, by default "git config" reads from both "config" and
 multiple working directory mode, "config" file is shared while
 "config.worktree" is per-working directory (i.e., it's in
 GIT_COMMON_DIR/worktrees/<id>/config.worktree)
+
+==== `refStorage`
+
+Specifies the file format for the ref database. Values are `files`
+(for the traditional packed + loose ref format) and `reftable` for the
+binary reftable format. See https://github.com/google/reftable for
+more information.

index 3d3a39fc192..f4848a382f4 100644
@@ -810,6 +810,7 @@ TEST_SHELL_PATH = $(SHELL_PATH)
 LIB_FILE = libgit.a
 XDIFF_LIB = xdiff/lib.a
 VCSSVN_LIB = vcs-svn/lib.a
+REFTABLE_LIB = reftable/libreftable.a
 
 GENERATED_H += config-list.h
 GENERATED_H += command-list.h

@@ -962,6 +963,7 @@ LIB_OBJS += ref-filter.o
 LIB_OBJS += reflog-walk.o
 LIB_OBJS += refs.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

@@ -1165,7 +1167,7 @@ THIRD_PARTY_SOURCES += compat/regex/%
 THIRD_PARTY_SOURCES += sha1collisiondetection/%
 THIRD_PARTY_SOURCES += sha1dc/%
 
-GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB)
+GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB)
 EXTLIBS =
 
 GIT_USER_AGENT = git/$(GIT_VERSION)

@@ -2360,11 +2362,29 @@ VCSSVN_OBJS += vcs-svn/sliding_window.o
 VCSSVN_OBJS += vcs-svn/svndiff.o
 VCSSVN_OBJS += vcs-svn/svndump.o
 
+REFTABLE_OBJS += reftable/basics.o
+REFTABLE_OBJS += reftable/block.o
+REFTABLE_OBJS += reftable/file.o
+REFTABLE_OBJS += reftable/iter.o
+REFTABLE_OBJS += reftable/merged.o
+REFTABLE_OBJS += reftable/pq.o
+REFTABLE_OBJS += reftable/reader.o
+REFTABLE_OBJS += reftable/record.o
+REFTABLE_OBJS += reftable/refname.o
+REFTABLE_OBJS += reftable/reftable.o
+REFTABLE_OBJS += reftable/slice.o
+REFTABLE_OBJS += reftable/stack.o
+REFTABLE_OBJS += reftable/tree.o
+REFTABLE_OBJS += reftable/writer.o
+REFTABLE_OBJS += reftable/zlib-compat.o
+
+
 TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
 OBJECTS := $(LIB_OBJS) $(BUILTIN_OBJS) $(PROGRAM_OBJS) $(TEST_OBJS) \
 	$(XDIFF_OBJS) \
 	$(VCSSVN_OBJS) \
 	$(FUZZ_OBJS) \
+	$(REFTABLE_OBJS) \
 	common-main.o \
 	git.o
 ifndef NO_CURL

@@ -2505,6 +2525,9 @@ $(XDIFF_LIB): $(XDIFF_OBJS)
 $(VCSSVN_LIB): $(VCSSVN_OBJS)
 	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
 
+$(REFTABLE_LIB): $(REFTABLE_OBJS)
+	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
+
 export DEFAULT_EDITOR DEFAULT_PAGER
 
 Documentation/GIT-EXCLUDED-PROGRAMS: FORCE

@@ -3120,7 +3143,7 @@ cocciclean:
 clean: profile-clean coverage-clean cocciclean
 	$(RM) *.res
 	$(RM) $(OBJECTS)
-	$(RM) $(LIB_FILE) $(XDIFF_LIB) $(VCSSVN_LIB)
+	$(RM) $(LIB_FILE) $(XDIFF_LIB) $(VCSSVN_LIB) $(REFTABLE_LIB)
 	$(RM) $(ALL_PROGRAMS) $(SCRIPT_LIB) $(BUILT_INS) git$X
 	$(RM) $(TEST_PROGRAMS)
 	$(RM) $(FUZZ_PROGRAMS)

index cb48a291caf..4d0cf065e4a 100644
@@ -1108,7 +1108,8 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 		}
 	}
 
-	init_db(git_dir, real_git_dir, option_template, GIT_HASH_UNKNOWN, INIT_DB_QUIET);
+	init_db(git_dir, real_git_dir, option_template, GIT_HASH_UNKNOWN,
+		DEFAULT_REF_STORAGE, INIT_DB_QUIET);
 
 	if (real_git_dir)
 		git_dir = real_git_dir;

index 0f0485ecfe2..8cb884773c3 100644
@@ -628,8 +628,9 @@ int path_inside_repo(const char *prefix, const char *path);
 
 int init_db(const char *git_dir, const char *real_git_dir,
 	    const char *template_dir, int hash_algo,
-	    unsigned int flags);
-void initialize_repository_version(int hash_algo);
+	    const char *ref_storage_format, unsigned int flags);
+void initialize_repository_version(int hash_algo,
+				   const char *ref_storage_format);
 
 void sanitize_stdfds(void);
 int daemonize(void);

@@ -1043,6 +1044,7 @@ struct repository_format {
 	int is_bare;
 	int hash_algo;
 	char *work_tree;
+	char *ref_storage;
 	struct string_list unknown_extensions;
 };
 

index 4db27379661..299a5db8bf1 100644
@@ -17,10 +17,16 @@
 #include "argv-array.h"
 #include "repository.h"
 
+const char *default_ref_storage(void)
+{
+	const char *test = getenv("GIT_TEST_REFTABLE");
+	return test ? "reftable" : "files";
+}
+
 /*
  * List of all available backends
  */
-static struct ref_storage_be *refs_backends = &refs_be_files;
+static struct ref_storage_be *refs_backends = &refs_be_reftable;
 
 static struct ref_storage_be *find_ref_storage_backend(const char *name)
 {

@@ -1792,13 +1798,13 @@ static struct ref_store *lookup_ref_store_map(struct hashmap *map,
  * Create, record, and return a ref_store instance for the specified
  * gitdir.
  */
-static struct ref_store *ref_store_init(const char *gitdir,
+static struct ref_store *ref_store_init(const char *gitdir, const char *be_name,
 					unsigned int flags)
 {
-	const char *be_name = "files";
-	struct ref_storage_be *be = find_ref_storage_backend(be_name);
+	struct ref_storage_be *be;
 	struct ref_store *refs;
 
+	be = find_ref_storage_backend(be_name);
 	if (!be)
 		BUG("reference backend %s is unknown", be_name);
 

@@ -1814,7 +1820,11 @@ struct ref_store *get_main_ref_store(struct repository *r)
 	if (!r->gitdir)
 		BUG("attempting to get main_ref_store outside of repository");
 
-	r->refs_private = ref_store_init(r->gitdir, REF_STORE_ALL_CAPS);
+	r->refs_private = ref_store_init(r->gitdir,
+					 r->ref_storage_format ?
+						 r->ref_storage_format :
+						 DEFAULT_REF_STORAGE,
+					 REF_STORE_ALL_CAPS);
 	return r->refs_private;
 }
 

@@ -1869,7 +1879,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule)
 		goto done;
 
 	/* assume that add_submodule_odb() has been called */
-	refs = ref_store_init(submodule_sb.buf,
+	refs = ref_store_init(submodule_sb.buf, DEFAULT_REF_STORAGE, /* XXX */
 			      REF_STORE_READ | REF_STORE_ODB);
 	register_ref_store_map(&submodule_ref_stores, "submodule",
 			       refs, submodule);

@@ -1883,6 +1893,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule)
 
 struct ref_store *get_worktree_ref_store(const struct worktree *wt)
 {
+	const char *format = DEFAULT_REF_STORAGE; /* XXX */
 	struct ref_store *refs;
 	const char *id;
 

@@ -1896,9 +1907,9 @@ struct ref_store *get_worktree_ref_store(const struct worktree *wt)
 
 	if (wt->id)
 		refs = ref_store_init(git_common_path("worktrees/%s", wt->id),
-				      REF_STORE_ALL_CAPS);
+				      format, REF_STORE_ALL_CAPS);
 	else
-		refs = ref_store_init(get_git_common_dir(),
+		refs = ref_store_init(get_git_common_dir(), format,
 				      REF_STORE_ALL_CAPS);
 
 	if (refs)

index 9421c5b8465..15f6d78ee84 100644
@@ -9,6 +9,9 @@ struct string_list;
 struct string_list_item;
 struct worktree;
 
+/* Returns the ref storage backend to use by default. */
+const char *default_ref_storage(void);
+
 /*
  * Resolve a reference, recursively following symbolic refererences.
  *

index 3490aac3a40..cafe5b97376 100644
@@ -661,6 +661,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;
 
 /*

index 6f7f6f002b1..087760bc184 100644
@@ -178,6 +178,8 @@ int repo_init(struct repository *repo,
 	if (worktree)
 		repo_set_worktree(repo, worktree);
 
+	repo->ref_storage_format = xstrdup_or_null(format.ref_storage);
+
 	clear_repository_format(&format);
 	return 0;
 

index 6534fbb7b31..f57b73f4a27 100644
@@ -74,6 +74,9 @@ struct repository {
 	 */
 	struct ref_store *refs_private;
 
+	/* The format to use for the ref database. */
+	char *ref_storage_format;
+
 	/*
 	 * Contains path to often used file names.
 	 */

index 65fe5ecefbe..2ef970f9f88 100644
@@ -468,9 +468,11 @@ static int check_repo_format(const char *var, const char *value, void *vdata)
 			if (!value)
 				return config_error_nonbool(var);
 			data->partial_clone = xstrdup(value);
-		} else if (!strcmp(ext, "worktreeconfig"))
+		} else if (!strcmp(ext, "worktreeconfig")) {
 			data->worktree_config = git_config_bool(var, value);
-		else
+		} else if (!strcmp(ext, "refstorage")) {
+			data->ref_storage = xstrdup(value);
+		} else
 			string_list_append(&data->unknown_extensions, ext);
 	}
 

@@ -559,6 +561,7 @@ void clear_repository_format(struct repository_format *format)
 	string_list_clear(&format->unknown_extensions, 0);
 	free(format->work_tree);
 	free(format->partial_clone);
+	free(format->ref_storage);
 	init_repository_format(format);
 }
 

@@ -1204,8 +1207,11 @@ const char *setup_git_directory_gently(int *nongit_ok)
 				gitdir = DEFAULT_GIT_DIR_ENVIRONMENT;
 			setup_git_env(gitdir);
 		}
-		if (startup_info->have_repository)
+		if (startup_info->have_repository) {
 			repo_set_hash_algo(the_repository, repo_fmt.hash_algo);
+			the_repository->ref_storage_format =
+				xstrdup_or_null(repo_fmt.ref_storage);
+		}
 	}
 
 	strbuf_release(&dir);

gitgitgadget

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

Reftable is a format for storing the ref database. Its rationale and specification is in the preceding commit.

This imports the upstream library as one big commit. For understanding the code, it is suggested to read the code in the following order:

* The specification under Documentation/technical/reftable.txt

* reftable.h - the public API

* record.{c,h} - reading and writing records

* block.{c,h} - reading and writing blocks.

* writer.{c,h} - writing a complete reftable file.

* merged.{c,h} and pq.{c,h} - reading a stack of reftables

* stack.{c,h} - writing and compacting stacks of reftable on the filesystem.

---
 reftable/LICENSE       |   31 +
 reftable/README.md     |   11 +
 reftable/VERSION       |    5 +
 reftable/basics.c      |  215 +++++++
 reftable/basics.h      |   53 ++
 reftable/block.c       |  435 ++++++++++++++
 reftable/block.h       |  129 +++++
 reftable/constants.h   |   21 +
 reftable/file.c        |   99 ++++
 reftable/iter.c        |  240 ++++++++
 reftable/iter.h        |   63 ++
 reftable/merged.c      |  327 +++++++++++
 reftable/merged.h      |   38 ++
 reftable/pq.c          |  115 ++++
 reftable/pq.h          |   34 ++
 reftable/reader.c      |  753 ++++++++++++++++++++++++
 reftable/reader.h      |   65 +++
 reftable/record.c      | 1133 ++++++++++++++++++++++++++++++++++++
 reftable/record.h      |  121 ++++
 reftable/refname.c     |  215 +++++++
 reftable/refname.h     |   38 ++
 reftable/reftable.c    |   91 +++
 reftable/reftable.h    |  563 ++++++++++++++++++
 reftable/slice.c       |  225 ++++++++
 reftable/slice.h       |   76 +++
 reftable/stack.c       | 1230 ++++++++++++++++++++++++++++++++++++++++
 reftable/stack.h       |   45 ++
 reftable/system.h      |   54 ++
 reftable/tree.c        |   67 +++
 reftable/tree.h        |   34 ++
 reftable/update.sh     |   24 +
 reftable/writer.c      |  661 +++++++++++++++++++++
 reftable/writer.h      |   60 ++
 reftable/zlib-compat.c |   92 +++
 34 files changed, 7363 insertions(+)
 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/constants.h
 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/refname.c
 create mode 100644 reftable/refname.h
 create mode 100644 reftable/reftable.c
 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 100755 reftable/update.sh
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 reftable/zlib-compat.c

new file mode 100644
index 00000000000..402e0f9356b
@@ -0,0 +1,31 @@
+BSD License
+
+Copyright (c) 2020, Google LLC
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+* Redistributions of source code must retain the above copyright notice,
+this list of conditions and the following disclaimer.
+
+* Redistributions in binary form must reproduce the above copyright
+notice, this list of conditions and the following disclaimer in the
+documentation and/or other materials provided with the distribution.
+
+* Neither the name of Google LLC nor the names of its contributors may
+be used to endorse or promote products derived from this software
+without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

new file mode 100644
index 00000000000..21500563fd4
@@ -0,0 +1,11 @@
+
+The source code in this directory comes from https://github.com/google/reftable.
+
+The VERSION file keeps track of the current version of the reftable library.
+
+To update the library, do:
+
+   sh reftable/update.sh
+
+Bugfixes should be accompanied by a test and applied to upstream project at
+https://github.com/google/reftable.

new file mode 100644
index 00000000000..09ceed05220
@@ -0,0 +1,5 @@
+commit 06dd91a8377b0f920d9835b9835d0d650f928dce
+Author: Han-Wen Nienhuys <[email protected]>
+Date:   Wed May 6 21:27:32 2020 +0200
+
+    C: fix small memory leak in stack.c error path

new file mode 100644
index 00000000000..5eee72c4c11
@@ -0,0 +1,21 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef CONSTANTS_H
+#define CONSTANTS_H
+
+#define BLOCK_TYPE_LOG 'g'
+#define BLOCK_TYPE_INDEX 'i'
+#define BLOCK_TYPE_REF 'r'
+#define BLOCK_TYPE_OBJ 'o'
+#define BLOCK_TYPE_ANY 0
+
+#define MAX_RESTARTS ((1 << 16) - 1)
+#define DEFAULT_BLOCK_SIZE 4096
+
+#endif

new file mode 100644
index 00000000000..a71f36ecbae
@@ -0,0 +1,38 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef MERGED_H
+#define MERGED_H
+
+#include "pq.h"
+#include "reftable.h"
+
+struct reftable_merged_table {
+	struct reftable_reader **stack;
+	int stack_len;
+	uint32_t hash_id;
+	bool suppress_deletions;
+
+	uint64_t min;
+	uint64_t max;
+};
+
+struct merged_iter {
+	struct reftable_iterator *stack;
+	uint32_t hash_id;
+	int stack_len;
+	byte typ;
+	bool suppress_deletions;
+	struct merged_iter_pqueue pq;
+};
+
+void merged_table_clear(struct reftable_merged_table *mt);
+int merged_table_seek_record(struct reftable_merged_table *mt,
+			     struct reftable_iterator *it, struct record rec);
+
+#endif

new file mode 100644
index 00000000000..b585a52ee14
@@ -0,0 +1,34 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef PQ_H
+#define PQ_H
+
+#include "record.h"
+
+struct pq_entry {
+	int index;
+	struct record rec;
+};
+
+int pq_less(struct pq_entry a, struct pq_entry b);
+
+struct merged_iter_pqueue {
+	struct pq_entry *heap;
+	int len;
+	int cap;
+};
+
+struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);
+bool merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);
+void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
+struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e);
+void merged_iter_pqueue_clear(struct merged_iter_pqueue *pq);
+
+#endif

new file mode 100644
index 00000000000..f335287fcdb

new file mode 100644
index 00000000000..954512e9a3a

new file mode 100755
index 00000000000..ef32aeda515

gitgitgadget

Part of the diff is not shown here. View the raw message.

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

Reading and writing .git/refs/* assumes that refs are stored in the 'files' ref backend.

---
 t/t0002-gitfile.sh             |  2 +-
 t/t1400-update-ref.sh          | 32 ++++++++++++++++----------------
 t/t1506-rev-parse-diagnosis.sh |  2 +-
 t/t6050-replace.sh             |  2 +-
 t/t9020-remote-svn.sh          |  4 ++--
 5 files changed, 21 insertions(+), 21 deletions(-)

index 0aa9908ea12..960ed150cb5 100755
@@ -62,7 +62,7 @@ test_expect_success 'check commit-tree' '
 '
 
 test_expect_success 'check rev-list' '
-	echo $SHA >"$REAL/HEAD" &&
+	git update-ref "HEAD" "$SHA" &&
 	test "$SHA" = "$(git rev-list HEAD)"
 '
 

index e1197ac8189..27171f82612 100755
@@ -37,15 +37,15 @@ test_expect_success setup '
 
 test_expect_success "create $m" '
 	git update-ref $m $A &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 test_expect_success "create $m with oldvalue verification" '
 	git update-ref $m $B $A &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "fail to delete $m with stale ref" '
 	test_must_fail git update-ref -d $m $A &&
-	test $B = "$(cat .git/$m)"
+	test $B = "$(git show-ref -s --verify $m)"
 '
 test_expect_success "delete $m" '
 	test_when_finished "rm -f .git/$m" &&

@@ -56,7 +56,7 @@ test_expect_success "delete $m" '
 test_expect_success "delete $m without oldvalue verification" '
 	test_when_finished "rm -f .git/$m" &&
 	git update-ref $m $A &&
-	test $A = $(cat .git/$m) &&
+	test $A = $(git show-ref -s --verify $m) &&
 	git update-ref -d $m &&
 	test_path_is_missing .git/$m
 '

@@ -69,15 +69,15 @@ test_expect_success "fail to create $n" '
 
 test_expect_success "create $m (by HEAD)" '
 	git update-ref HEAD $A &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 test_expect_success "create $m (by HEAD) with oldvalue verification" '
 	git update-ref HEAD $B $A &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "fail to delete $m (by HEAD) with stale ref" '
 	test_must_fail git update-ref -d HEAD $A &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "delete $m (by HEAD)" '
 	test_when_finished "rm -f .git/$m" &&

@@ -178,14 +178,14 @@ test_expect_success '--no-create-reflog overrides core.logAllRefUpdates=always'
 
 test_expect_success "create $m (by HEAD)" '
 	git update-ref HEAD $A &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 test_expect_success 'pack refs' '
 	git pack-refs --all
 '
 test_expect_success "move $m (by HEAD)" '
 	git update-ref HEAD $B $A &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "delete $m (by HEAD) should remove both packed and loose $m" '
 	test_when_finished "rm -f .git/$m" &&

@@ -255,7 +255,7 @@ test_expect_success '(not) change HEAD with wrong SHA1' '
 '
 test_expect_success "(not) changed .git/$m" '
 	test_when_finished "rm -f .git/$m" &&
-	! test $B = $(cat .git/$m)
+	! test $B = $(git show-ref -s --verify $m)
 '
 
 rm -f .git/logs/refs/heads/master

@@ -263,19 +263,19 @@ test_expect_success "create $m (logged by touch)" '
 	test_config core.logAllRefUpdates false &&
 	GIT_COMMITTER_DATE="2005-05-26 23:30" \
 	git update-ref --create-reflog HEAD $A -m "Initial Creation" &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 test_expect_success "update $m (logged by touch)" '
 	test_config core.logAllRefUpdates false &&
 	GIT_COMMITTER_DATE="2005-05-26 23:31" \
 	git update-ref HEAD $B $A -m "Switch" &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "set $m (logged by touch)" '
 	test_config core.logAllRefUpdates false &&
 	GIT_COMMITTER_DATE="2005-05-26 23:41" \
 	git update-ref HEAD $A &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 
 test_expect_success 'empty directory removal' '

@@ -319,19 +319,19 @@ test_expect_success "create $m (logged by config)" '
 	test_config core.logAllRefUpdates true &&
 	GIT_COMMITTER_DATE="2005-05-26 23:32" \
 	git update-ref HEAD $A -m "Initial Creation" &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 test_expect_success "update $m (logged by config)" '
 	test_config core.logAllRefUpdates true &&
 	GIT_COMMITTER_DATE="2005-05-26 23:33" \
 	git update-ref HEAD'" $B $A "'-m "Switch" &&
-	test $B = $(cat .git/$m)
+	test $B = $(git show-ref -s --verify $m)
 '
 test_expect_success "set $m (logged by config)" '
 	test_config core.logAllRefUpdates true &&
 	GIT_COMMITTER_DATE="2005-05-26 23:43" \
 	git update-ref HEAD $A &&
-	test $A = $(cat .git/$m)
+	test $A = $(git show-ref -s --verify $m)
 '
 
 cat >expect <<EOF

index 52edcbdcc32..dbf690b9c1b 100755
@@ -207,7 +207,7 @@ test_expect_success 'arg before dashdash must be a revision (ambiguous)' '
 	{
 		# we do not want to use rev-parse here, because
 		# we are testing it
-		cat .git/refs/heads/foobar &&
+		git show-ref -s refs/heads/foobar &&
 		printf "%s\n" --
 	} >expect &&
 	git rev-parse foobar -- >actual &&

index e7e64e085dd..c80dc10b8f1 100755
@@ -135,7 +135,7 @@ test_expect_success 'tag replaced commit' '
 test_expect_success '"git fsck" works' '
      git fsck master >fsck_master.out &&
      test_i18ngrep "dangling commit $R" fsck_master.out &&
-     test_i18ngrep "dangling tag $(cat .git/refs/tags/mytag)" fsck_master.out &&
+     test_i18ngrep "dangling tag $(git show-ref -s refs/tags/mytag)" fsck_master.out &&
      test -z "$(git fsck)"
 '
 

index 6fca08e5e35..9fcfa969a9b 100755
@@ -48,8 +48,8 @@ test_expect_success REMOTE_SVN 'simple fetch' '
 '
 
 test_debug '
-	cat .git/refs/svn/svnsim/master
-	cat .git/refs/remotes/svnsim/master
+	git show-ref -s refs/svn/svnsim/master
+	git show-ref -s refs/remotes/svnsim/master
 '
 
 test_expect_success REMOTE_SVN 'repeated fetch, nothing shall change' '

gitgitgadget

This adds the reftable library, and hooks it up as a ref backend.

Includes testing support, to test: make -C t/ GIT_TEST_REFTABLE=1

Summary 18964 tests pass 2871 tests fail

Some issues:

* pseudorefs are broken
* many tests inspect .git/{logs,heads}/ directly.

v15

* fix static analysis error
* plug some memory leaks

Han-Wen Nienhuys (10):
refs.h: clarify reflog iteration order
Iterate over the "refs/" namespace in for_each_[raw]ref
refs: document how ref_iterator_advance_fn should handle symrefs Add .gitattributes for the reftable/ directory
reftable: define version 2 of the spec to accomodate SHA256
reftable: clarify how empty tables should be written Add reftable library
Reftable support for git-core
t: use update-ref and show-ref to reading/writing refs Add some reftable testing infrastructure

Johannes Schindelin (1):
vcxproj: adjust for the reftable changes

Jonathan Nieder (1):
reftable: file format documentation

 Documentation/Makefile                        |    1 +
 Documentation/technical/reftable.txt          | 1080 +++++++++++++++
 .../technical/repository-version.txt          |    7 +
 Makefile                                      |   27 +-
 builtin/clone.c                               |    3 +-
 builtin/init-db.c                             |   56 +-
 cache.h                                       |    6 +-
 config.mak.uname                              |    2 +-
 contrib/buildsystems/Generators/Vcxproj.pm    |   11 +-
 refs.c                                        |   33 +-
 refs.h                                        |    8 +-
 refs/refs-internal.h                          |    6 +
 refs/reftable-backend.c                       | 1045 ++++++++++++++
 reftable/.gitattributes                       |    1 +
 reftable/LICENSE                              |   31 +
 reftable/README.md                            |   11 +
 reftable/VERSION                              |    5 +
 reftable/basics.c                             |  215 +++
 reftable/basics.h                             |   53 +
 reftable/block.c                              |  435 ++++++
 reftable/block.h                              |  129 ++
 reftable/constants.h                          |   21 +
 reftable/file.c                               |   99 ++
 reftable/iter.c                               |  240 ++++
 reftable/iter.h                               |   63 +
 reftable/merged.c                             |  327 +++++
 reftable/merged.h                             |   38 +
 reftable/pq.c                                 |  115 ++
 reftable/pq.h                                 |   34 +
 reftable/reader.c                             |  753 ++++++++++
 reftable/reader.h                             |   65 +
 reftable/record.c                             | 1133 +++++++++++++++
 reftable/record.h                             |  121 ++
 reftable/refname.c                            |  215 +++
 reftable/refname.h                            |   38 +
 reftable/reftable.c                           |   91 ++
 reftable/reftable.h                           |  563 ++++++++
 reftable/slice.c                              |  225 +++
 reftable/slice.h                              |   76 +
 reftable/stack.c                              | 1230 +++++++++++++++++
 reftable/stack.h                              |   45 +
 reftable/system.h                             |   54 +
 reftable/tree.c                               |   67 +
 reftable/tree.h                               |   34 +
 reftable/update.sh                            |   24 +
 reftable/writer.c                             |  661 +++++++++
 reftable/writer.h                             |   60 +
 reftable/zlib-compat.c                        |   92 ++
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 setup.c                                       |   12 +-
 t/t0002-gitfile.sh                            |    2 +-
 t/t0031-reftable.sh                           |  109 ++
 t/t1400-update-ref.sh                         |   32 +-
 t/t1409-avoid-packing-refs.sh                 |    6 +
 t/t1506-rev-parse-diagnosis.sh                |    2 +-
 t/t3210-pack-refs.sh                          |    6 +
 t/t6050-replace.sh                            |    2 +-
 t/t9020-remote-svn.sh                         |    4 +-
 t/test-lib.sh                                 |    5 +
 60 files changed, 9777 insertions(+), 57 deletions(-)
 create mode 100644 Documentation/technical/reftable.txt
 create mode 100644 refs/reftable-backend.c
 create mode 100644 reftable/.gitattributes
 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/constants.h
 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/refname.c
 create mode 100644 reftable/refname.h
 create mode 100644 reftable/reftable.c
 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 100755 reftable/update.sh
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 reftable/zlib-compat.c
 create mode 100755 t/t0031-reftable.sh

base-commit: b34789c0b0d3b137f0bb516b417bd8d75e0cb306
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-539%2Fhanwen%2Freftable-v12
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-539/hanwen/reftable-v12
Pull-Request: https://github.com/gitgitgadget/git/pull/539

Range-diff vs v11:

  1:  dfa5fd74f85 =  1:  dfa5fd74f85 refs.h: clarify reflog iteration order
  2:  340c5c415e1 =  2:  340c5c415e1 Iterate over the "refs/" namespace in for_each_[raw]ref
  3:  6553285043b =  3:  6553285043b refs: document how ref_iterator_advance_fn should handle symrefs
  4:  7dc47c7756f =  4:  7dc47c7756f Add .gitattributes for the reftable/ directory
  5:  06fcb49e903 =  5:  06fcb49e903 reftable: file format documentation
  6:  093fa74a3d0 =  6:  093fa74a3d0 reftable: define version 2 of the spec to accomodate SHA256
  7:  6d9031372ce =  7:  6d9031372ce reftable: clarify how empty tables should be written
  8:  6ee6c44752c !  8:  57d338c4983 Add reftable library
     @@ reftable/README.md (new)
      
       ## reftable/VERSION (new) ##
      @@
     -+commit 3a486f79abcd17e88e3bca62f43188a7c8b80ff3
     ++commit 06dd91a8377b0f920d9835b9835d0d650f928dce
      +Author: Han-Wen Nienhuys <[email protected]>
     -+Date:   Mon May 4 19:20:21 2020 +0200
     ++Date:   Wed May 6 21:27:32 2020 +0200
      +
     -+    C: include "cache.h" in git-core sleep_millisec()
     ++    C: fix small memory leak in stack.c error path
      
       ## reftable/basics.c (new) ##
      @@
     @@ reftable/block.c (new)
      +
      +#include "system.h"
      +
     -+#include "blocksource.h"
      +#include "constants.h"
      +#include "record.h"
      +#include "reftable.h"
     @@ reftable/block.c (new)
      +		}
      +
      +		/* We're done with the input data. */
     -+		block_source_return_block(block->source, block);
     ++		reftable_block_done(block);
      +		block->data = uncompressed.buf;
      +		block->len = sz;
      +		block->source = malloc_block_source();
     @@ reftable/block.h (new)
      +/* size of file footer, depending on format version */
      +int footer_size(int version);
      +
     -+#endif
     -
     - ## reftable/blocksource.h (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#ifndef BLOCKSOURCE_H
     -+#define BLOCKSOURCE_H
     -+
     -+#include "reftable.h"
     -+
     -+uint64_t block_source_size(struct reftable_block_source source);
     -+int block_source_read_block(struct reftable_block_source source,
     -+			    struct reftable_block *dest, uint64_t off,
     -+			    uint32_t size);
     -+void block_source_return_block(struct reftable_block_source source,
     -+			       struct reftable_block *ret);
     -+void block_source_close(struct reftable_block_source source);
     ++/* returns a block to its source. */
     ++void reftable_block_done(struct reftable_block *ret);
      +
      +#endif
      
     @@ reftable/iter.c (new)
      +		if (fri->double_check) {
      +			struct reftable_iterator it = { 0 };
      +
     -+			err = reftable_reader_seek_ref(fri->r, &it,
     -+						       ref->ref_name);
     ++			err = reftable_table_seek_ref(fri->tab, &it,
     ++						      ref->ref_name);
      +			if (err == 0) {
      +				err = reftable_iterator_next_ref(it, ref);
      +			}
     @@ reftable/iter.c (new)
      +{
      +	struct indexed_table_ref_iter *it = (struct indexed_table_ref_iter *)p;
      +	block_iter_close(&it->cur);
     -+	reader_return_block(it->r, &it->block_reader.block);
     ++	reftable_block_done(&it->block_reader.block);
      +	slice_clear(&it->oid);
      +}
      +
     @@ reftable/iter.c (new)
      +		return 1;
      +	}
      +
     -+	reader_return_block(it->r, &it->block_reader.block);
     ++	reftable_block_done(&it->block_reader.block);
      +
      +	{
      +		uint64_t off = it->offsets[it->offset_idx++];
     @@ reftable/iter.h (new)
      +/* iterator that produces only ref records that point to `oid` */
      +struct filtering_ref_iterator {
      +	bool double_check;
     -+	struct reftable_reader *r;
     ++	struct reftable_table tab;
      +	struct slice oid;
      +	struct reftable_iterator it;
      +};
     @@ reftable/reader.c (new)
      +#include "reader.h"
      +
      +#include "system.h"
     -+
      +#include "block.h"
      +#include "constants.h"
      +#include "iter.h"
     @@ reftable/reader.c (new)
      +	return result;
      +}
      +
     -+void block_source_return_block(struct reftable_block_source source,
     -+			       struct reftable_block *blockp)
     ++void reftable_block_done(struct reftable_block *blockp)
      +{
     -+	source.ops->return_block(source.arg, blockp);
     ++	struct reftable_block_source source = blockp->source;
     ++	if (blockp != NULL && source.ops != NULL)
     ++		source.ops->return_block(source.arg, blockp);
      +	blockp->data = NULL;
      +	blockp->len = 0;
      +	blockp->source.ops = NULL;
     @@ reftable/reader.c (new)
      +	return block_source_read_block(r->source, dest, off, sz);
      +}
      +
     -+void reader_return_block(struct reftable_reader *r, struct reftable_block *p)
     -+{
     -+	block_source_return_block(r->source, p);
     -+}
     -+
      +uint32_t reftable_reader_hash_id(struct reftable_reader *r)
      +{
      +	return r->hash_id;
     @@ reftable/reader.c (new)
      +
      +	err = parse_footer(r, footer.data, header.data);
      +exit:
     -+	block_source_return_block(r->source, &footer);
     -+	block_source_return_block(r->source, &header);
     ++	reftable_block_done(&footer);
     ++	reftable_block_done(&header);
      +	return err;
      +}
      +
     @@ reftable/reader.c (new)
      +	if (ti->bi.br == NULL) {
      +		return;
      +	}
     -+	reader_return_block(ti->r, &ti->bi.br->block);
     ++	reftable_block_done(&ti->bi.br->block);
      +	FREE_AND_NULL(ti->bi.br);
      +
      +	ti->bi.last_key.len = 0;
     @@ reftable/reader.c (new)
      +	}
      +
      +	if (want_typ != BLOCK_TYPE_ANY && block_typ != want_typ) {
     -+		reader_return_block(r, &block);
     ++		reftable_block_done(&block);
      +		return 1;
      +	}
      +
      +	if (block_size > guess_block_size) {
     -+		reader_return_block(r, &block);
     ++		reftable_block_done(&block);
      +		err = reader_get_block(r, &block, next_off, block_size);
      +		if (err < 0) {
      +			return err;
     @@ reftable/reader.c (new)
      +
      +static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,
      +					      struct reftable_iterator *it,
     -+					      byte *oid, int oid_len)
     ++					      byte *oid)
      +{
      +	struct table_iter *ti = reftable_calloc(sizeof(struct table_iter));
      +	struct filtering_ref_iterator *filter = NULL;
     ++	int oid_len = hash_size(r->hash_id);
      +	int err = reader_start(r, ti, BLOCK_TYPE_REF, false);
      +	if (err < 0) {
      +		reftable_free(ti);
     @@ reftable/reader.c (new)
      +	filter = reftable_calloc(sizeof(struct filtering_ref_iterator));
      +	slice_resize(&filter->oid, oid_len);
      +	memcpy(filter->oid.buf, oid, oid_len);
     -+	filter->r = r;
     ++	reftable_table_from_reader(&filter->tab, r);
      +	filter->double_check = false;
      +	iterator_from_table_iter(&filter->it, ti);
      +
     @@ reftable/reader.c (new)
      +}
      +
      +int reftable_reader_refs_for(struct reftable_reader *r,
     -+			     struct reftable_iterator *it, byte *oid,
     -+			     int oid_len)
     ++			     struct reftable_iterator *it, byte *oid)
      +{
      +	if (r->obj_offsets.present) {
      +		return reftable_reader_refs_for_indexed(r, it, oid);
      +	}
     -+	return reftable_reader_refs_for_unindexed(r, it, oid, oid_len);
     ++	return reftable_reader_refs_for_unindexed(r, it, oid);
      +}
      +
      +uint64_t reftable_reader_max_update_index(struct reftable_reader *r)
     @@ reftable/reader.h (new)
      +int block_source_read_block(struct reftable_block_source source,
      +			    struct reftable_block *dest, uint64_t off,
      +			    uint32_t size);
     -+void block_source_return_block(struct reftable_block_source source,
     -+			       struct reftable_block *ret);
      +void block_source_close(struct reftable_block_source *source);
      +
      +/* metadata for a block type */
     @@ reftable/reader.h (new)
      +		struct record rec);
      +void reader_close(struct reftable_reader *r);
      +const char *reader_name(struct reftable_reader *r);
     -+void reader_return_block(struct reftable_reader *r, struct reftable_block *p);
      +
      +/* initialize a block reader to read from `r` */
      +int reader_init_block_reader(struct reftable_reader *r, struct block_reader *br,
     @@ reftable/record.c (new)
      +	memcpy(dest->buf, rec->hash_prefix, rec->hash_prefix_len);
      +}
      +
     ++static void obj_record_clear(void *rec)
     ++{
     ++	struct obj_record *obj = (struct obj_record *)rec;
     ++	FREE_AND_NULL(obj->hash_prefix);
     ++	FREE_AND_NULL(obj->offsets);
     ++	memset(obj, 0, sizeof(struct obj_record));
     ++}
     ++
      +static void obj_record_copy_from(void *rec, const void *src_rec, int hash_size)
      +{
     -+	struct obj_record *ref = (struct obj_record *)rec;
     ++	struct obj_record *obj = (struct obj_record *)rec;
      +	const struct obj_record *src = (const struct obj_record *)src_rec;
      +
     -+	*ref = *src;
     -+	ref->hash_prefix = reftable_malloc(ref->hash_prefix_len);
     -+	memcpy(ref->hash_prefix, src->hash_prefix, ref->hash_prefix_len);
     ++	obj_record_clear(obj);
     ++	*obj = *src;
     ++	obj->hash_prefix = reftable_malloc(obj->hash_prefix_len);
     ++	memcpy(obj->hash_prefix, src->hash_prefix, obj->hash_prefix_len);
      +
      +	{
     -+		int olen = ref->offset_len * sizeof(uint64_t);
     -+		ref->offsets = reftable_malloc(olen);
     -+		memcpy(ref->offsets, src->offsets, olen);
     ++		int olen = obj->offset_len * sizeof(uint64_t);
     ++		obj->offsets = reftable_malloc(olen);
     ++		memcpy(obj->offsets, src->offsets, olen);
      +	}
      +}
      +
     -+static void obj_record_clear(void *rec)
     -+{
     -+	struct obj_record *ref = (struct obj_record *)rec;
     -+	FREE_AND_NULL(ref->hash_prefix);
     -+	FREE_AND_NULL(ref->offsets);
     -+	memset(ref, 0, sizeof(struct obj_record));
     -+}
     -+
      +static byte obj_record_val_type(const void *rec)
      +{
      +	struct obj_record *r = (struct obj_record *)rec;
     @@ reftable/record.c (new)
      +	const struct reftable_log_record *src =
      +		(const struct reftable_log_record *)src_rec;
      +
     ++	reftable_log_record_clear(dst);
      +	*dst = *src;
      +	if (dst->ref_name != NULL) {
      +		dst->ref_name = xstrdup(dst->ref_name);
     @@ reftable/refname.h (new)
      +#ifndef REFNAME_H
      +#define REFNAME_H
      +
     ++#include "reftable.h"
     ++
      +struct modification {
      +	struct reftable_table tab;
      +
     @@ reftable/refname.h (new)
      +
      +int modification_validate(struct modification *mod);
      +
     -+/* illegal name, or dir/file conflict */
     -+#define REFTABLE_REFNAME_ERROR -9
     -+
      +#endif
      
       ## reftable/reftable.c (new) ##
     @@ reftable/reftable.h (new)
      +/* closes and deallocates a reader. */
      +void reftable_reader_free(struct reftable_reader *);
      +
     -+/* return an iterator for the refs pointing to oid */
     ++/* return an iterator for the refs pointing to `oid`. */
      +int reftable_reader_refs_for(struct reftable_reader *r,
     -+			     struct reftable_iterator *it, uint8_t *oid,
     -+			     int oid_len);
     ++			     struct reftable_iterator *it, uint8_t *oid);
      +
      +/* return the max_update_index for a table */
      +uint64_t reftable_reader_max_update_index(struct reftable_reader *r);
     @@ reftable/stack.c (new)
      +		int i = 0;
      +		for (i = 0; i < new_tables_len; i++) {
      +			reader_close(new_tables[i]);
     ++			reftable_reader_free(new_tables[i]);
      +		}
      +	}
      +	reftable_free(new_tables);

9: d731e1669b7 ! 9: f3bb9410038 Reftable support for git-core
@@ Commit message

For background, see the previous commit introducing the library.

- TODO:
+ This introduces the refs/reftable-backend.c containing reftable powered ref
+ storage backend.
+
+ It can be activated by passing --ref-storage=reftable to "git init".

- * Resolve spots marked with XXX
+ TODO:

- * Support worktrees (t0002-gitfile "linked repo" testcase)
+ * Resolve spots marked with XXX

Example use: see t/t0031-reftable.sh

 10:  513d585f0f8 = 10:  94fcc6dca6a vcxproj: adjust for the reftable changes
 12:  a7d1d2e721c = 11:  2abcbd1af99 t: use update-ref and show-ref to reading/writing refs
 11:  846fe29fa4b ! 12:  fe9407d10b1 Add some reftable testing infrastructure

@@ Commit message

* Add test_prerequisite REFTABLE. Skip t/t3210-pack-refs.sh for REFTABLE.

+ Major test failures:
+
+ * t9903-bash-prompt - The bash mode reads .git/HEAD directly
+ * t1400-update-ref.sh - Reads from .git/{refs,logs} directly
+ * t1404-update-ref-errors.sh - Manipulates .git/refs/ directly
+ * t1405 - inspecs .git/ directly.
+ * t1450-fsck.sh - manipulates .git/ directly to create invalid state
+ * Rebase, cherry-pick: pseudo refs aren't written through the refs backend.
+
+ Other tests by decreasing brokenness:
+
+ t1407-worktree-ref-store.sh - 5 of 5
+ t1413-reflog-detach.sh - 7 of 7
+ t1415-worktree-refs.sh - 11 of 11
+ t3908-stash-in-worktree.sh - 2 of 2
+ t4207-log-decoration-colors.sh - 2 of 2
+ t5515-fetch-merge-logic.sh - 17 of 17
+ t5900-repo-selection.sh - 8 of 8
+ t6016-rev-list-graph-simplify-history.sh - 12 of 12
+ t5573-pull-verify-signatures.sh - 15 of 16
+ t5612-clone-refspec.sh - 12 of 13
+ t5514-fetch-multiple.sh - 11 of 12
+ t6030-bisect-porcelain.sh - 64 of 71
+ t5533-push-cas.sh - 15 of 17
+ t5539-fetch-http-shallow.sh - 7 of 8
+ t7413-submodule-is-active.sh - 7 of 8
+ t2400-worktree-add.sh - 59 of 69
+ t0100-previous.sh - 5 of 6
+ t7419-submodule-set-branch.sh - 5 of 6
+ t1404-update-ref-errors.sh - 44 of 53
+ t6003-rev-list-topo-order.sh - 29 of 35
+ t1409-avoid-packing-refs.sh - 9 of 11
+ t5541-http-push-smart.sh - 31 of 38
+ t5407-post-rewrite-hook.sh - 13 of 16
+ t9903-bash-prompt.sh - 52 of 66
+ t1414-reflog-walk.sh - 9 of 12
+ t1507-rev-parse-upstream.sh - 21 of 28
+ t2404-worktree-config.sh - 9 of 12
+ t1505-rev-parse-last.sh - 5 of 7
+ t7510-signed-commit.sh - 16 of 23
+ t2018-checkout-branch.sh - 15 of 22
+ (..etc)
+
+
+