| Message ID | pull.539.v16.git.1591380199.gitgitgadget@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | Reftable support git-core | expand |
"Han-Wen Nienhuys via GitGitGadget" <gitgitgadget@gmail.com> writes: > This adds the reftable library, and hooks it up as a ref backend. Based on > hn/refs-cleanup. > > Includes testing support, to test: make -C t/ GIT_TEST_REFTABLE=1 > > Summary 20479 tests pass 1299 tests fail Thanks. > Some issues: > > * many tests inspect .git/{logs,heads}/ directly. > * worktrees broken. Are these with or without GIT_TEST_REFTABLE=1? The patches (with the fix-up I saw today) applied on top of your refs clean-up topic seems to pass the tests (without setting GIT_TEST_REFTABLE) as the whole, but when merged at the tip of 'pu', many tests fail (please see [*1*], for examples). I suspect that there may be some topics in flight that add more direct access to the .git/refs/ hierarchy, and/or there may be stupid mismerges (I'd especially appreciate it if you can spot any). [Reference] *1* https://travis-ci.org/github/git/git/builds/696638569
On Wed, Jun 10, 2020 at 1:14 AM Junio C Hamano <gitster@pobox.com> wrote: > > Some issues: > > > > * many tests inspect .git/{logs,heads}/ directly. > > * worktrees broken. > > Are these with or without GIT_TEST_REFTABLE=1? worktrees are broken with reftable, because HEAD is per-worktree ref, and I haven't decided how to handle those for reftable. > The patches (with the fix-up I saw today) applied on top of your > refs clean-up topic seems to pass the tests (without setting > GIT_TEST_REFTABLE) as the whole, but when merged at the tip of 'pu', > many tests fail (please see [*1*], for examples). I suspect that > there may be some topics in flight that add more direct access to > the .git/refs/ hierarchy, and/or there may be stupid mismerges (I'd > especially appreciate it if you can spot any). Curious; I'll have a look. There is also: reftable/stack_test.c:27:7: error: incompatible pointer types initializing 'PREC_DIR *' with an expression of type 'DIR *' [-Werror,-Wincompatible-pointer-types] DIR *dir = fdopendir(fd); on OSX. What is the proper dialect for reading out a directory within the git source code? opendir and fdopendir are POSIX, so I'm surprised this fails.
On Wed, Jun 10, 2020 at 1:14 AM Junio C Hamano <gitster@pobox.com> wrote: > > he patches (with the fix-up I saw today) applied on top of your > refs clean-up topic seems to pass the tests (without setting > GIT_TEST_REFTABLE) as the whole, but when merged at the tip of 'pu', > many tests fail (please see [*1*], for examples). I suspect that they all say warning: unable to upgrade repository format from 0 to 1: fatal: unable to upgrade repository format to support XXX maybe a mismerge in the code in init-db.c that deals with the repository format version?
Han-Wen Nienhuys <hanwenn@gmail.com> writes: > There is also: > > reftable/stack_test.c:27:7: error: incompatible pointer types > initializing 'PREC_DIR *' with an expression of type 'DIR *' > [-Werror,-Wincompatible-pointer-types] > DIR *dir = fdopendir(fd); > > on OSX. What is the proper dialect for reading out a directory within > the git source code? opendir and fdopendir are POSIX, so I'm surprised > this fails. I am reasonably sure we use opendir() to iterate over existing files and subdirectories in a directory (e.g. in the codepaths to enumerate loose object files in .git/objects/??/ directories). I do not offhand know we also use fdopendir() elsewhere. I strongly suspect we do not. Perhaps some platforms do POSIX.1-2001 but not ready for POSIX.1-2008 or something silly like that?
Junio C Hamano <gitster@pobox.com> writes: > I do not offhand know we also use fdopendir() elsewhere. I strongly > suspect we do not. Perhaps some platforms do POSIX.1-2001 but not > ready for POSIX.1-2008 or something silly like that? Searching "macos fdopendir" gives a few hits from other projects, all saying that before macOS 10.10 they did not have fdopendir() and their code failed to build on macs.
Hi Junio, On Wed, 10 Jun 2020, Junio C Hamano wrote: > Han-Wen Nienhuys <hanwenn@gmail.com> writes: > > > There is also: > > > > reftable/stack_test.c:27:7: error: incompatible pointer types > > initializing 'PREC_DIR *' with an expression of type 'DIR *' > > [-Werror,-Wincompatible-pointer-types] > > DIR *dir = fdopendir(fd); > > > > on OSX. What is the proper dialect for reading out a directory within > > the git source code? opendir and fdopendir are POSIX, so I'm surprised > > this fails. > > I am reasonably sure we use opendir() to iterate over existing files > and subdirectories in a directory (e.g. in the codepaths to > enumerate loose object files in .git/objects/??/ directories). > > I do not offhand know we also use fdopendir() elsewhere. I strongly > suspect we do not. Perhaps some platforms do POSIX.1-2001 but not > ready for POSIX.1-2008 or something silly like that? We don't. We also do not use `unlinkat()`. And we generally use `remove_dir_recursively()` instead of implementing a separate version of it that only handles one directory level ;-) This is what I needed in Git for Windows' `shears/pu` branch to make it compile again: -- snipsnap -- Subject: [PATCH] fixup??? Add reftable library Rather than causing a build failure e.g. on Windows, where `fdopendir()` and `unlinkat()` just is not a thing, and rather than re-inventing `remove_dir_recursively()`, let's just use the perfectly fine library function we already have for that purpose. Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> --- reftable/stack_test.c | 15 ++++++--------- 1 file changed, 6 insertions(+), 9 deletions(-) diff --git a/reftable/stack_test.c b/reftable/stack_test.c index ffcc1e42819a..4dadc39bf45f 100644 --- a/reftable/stack_test.c +++ b/reftable/stack_test.c @@ -17,23 +17,20 @@ license that can be found in the LICENSE file or at #include "reftable.h" #include "test_framework.h" #include "reftable-tests.h" +#include "dir.h" #include <sys/types.h> #include <dirent.h> static void clear_dir(const char *dirname) { - int fd = open(dirname, O_DIRECTORY, 0); - DIR *dir = fdopendir(fd); - struct dirent *ent = NULL; + struct strbuf buf = STRBUF_INIT; - assert(fd >= 0); + strbuf_addstr(&buf, dirname); + if (remove_dir_recursively(&buf, 0) < 0) + die("Could not remove '%s'", dirname); - while ((ent = readdir(dir)) != NULL) { - unlinkat(fd, ent->d_name, 0); - } - closedir(dir); - rmdir(dirname); + strbuf_release(&buf); } static void test_read_file(void) -- 2.27.0.windows.1
On Wed, Jun 10, 2020 at 8:59 PM Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote: > > I am reasonably sure we use opendir() to iterate over existing files > > and subdirectories in a directory (e.g. in the codepaths to > > enumerate loose object files in .git/objects/??/ directories). > > > > I do not offhand know we also use fdopendir() elsewhere. I strongly > > suspect we do not. Perhaps some platforms do POSIX.1-2001 but not > > ready for POSIX.1-2008 or something silly like that? > > We don't. We also do not use `unlinkat()`. And we generally use > `remove_dir_recursively()` instead of implementing a separate version of > it that only handles one directory level ;-) > > This is what I needed in Git for Windows' `shears/pu` branch to make it > compile again: Thanks Dscho. Last time I folded a fix into github.com/google/reftable, you seemed quite upset. How should I proceed with this fixup?
Hi Han-Wen, On Wed, 10 Jun 2020, Han-Wen Nienhuys wrote: > On Wed, Jun 10, 2020 at 8:59 PM Johannes Schindelin > <Johannes.Schindelin@gmx.de> wrote: > > > > I am reasonably sure we use opendir() to iterate over existing files > > > and subdirectories in a directory (e.g. in the codepaths to > > > enumerate loose object files in .git/objects/??/ directories). > > > > > > I do not offhand know we also use fdopendir() elsewhere. I strongly > > > suspect we do not. Perhaps some platforms do POSIX.1-2001 but not > > > ready for POSIX.1-2008 or something silly like that? > > > > We don't. We also do not use `unlinkat()`. And we generally use > > `remove_dir_recursively()` instead of implementing a separate version of > > it that only handles one directory level ;-) > > > > This is what I needed in Git for Windows' `shears/pu` branch to make it > > compile again: > > Thanks Dscho. Last time I folded a fix into > github.com/google/reftable, you seemed quite upset. I was not upset. I just pointed out how unnecessarily difficult and cumbersome it is to have this ever-growing patch, with the _actual_ commit history completely elsewhere. My assessment has not changed, and the situation has not changed, and does not look like it will change, so I'll just keep quiet from now on. :-) > How should I proceed with this fixup? That's for you to decide, not for me. My suggestions in the past seem not to have pleased you, so in the interest of keeping our relationship friendly, I will refrain from adding more suggestions. Ciao, Johannes
This adds the reftable library, and hooks it up as a ref backend. Based on hn/refs-cleanup. Includes testing support, to test: make -C t/ GIT_TEST_REFTABLE=1 Summary 20479 tests pass 1299 tests fail Some issues: * many tests inspect .git/{logs,heads}/ directly. * worktrees broken. v18 * fix pseudo ref usage * import and execute unittests too. Han-Wen Nienhuys (13): Write pseudorefs through ref backends. Make refs_ref_exists public Treat BISECT_HEAD as a pseudo ref Treat CHERRY_PICK_HEAD as a pseudo ref Treat REVERT_HEAD as a pseudo ref Move REF_LOG_ONLY to refs-internal.h Iterate over the "refs/" namespace in for_each_[raw]ref Add .gitattributes for the reftable/ directory Add reftable library Reftable support for git-core Hookup unittests for the reftable library. Add GIT_DEBUG_REFS debugging mechanism Add reftable testing infrastructure Johannes Schindelin (1): vcxproj: adjust for the reftable changes .../technical/repository-version.txt | 7 + Makefile | 45 +- builtin/bisect--helper.c | 3 +- builtin/clone.c | 3 +- builtin/commit.c | 34 +- builtin/init-db.c | 56 +- builtin/merge.c | 2 +- cache.h | 6 +- config.mak.uname | 2 +- contrib/buildsystems/Generators/Vcxproj.pm | 11 +- git-bisect.sh | 4 +- path.c | 2 - path.h | 9 +- refs.c | 157 +- refs.h | 16 + refs/debug.c | 309 ++++ refs/files-backend.c | 121 +- refs/packed-backend.c | 21 +- refs/refs-internal.h | 32 + refs/reftable-backend.c | 1331 +++++++++++++++++ reftable/.gitattributes | 1 + reftable/LICENSE | 31 + reftable/README.md | 11 + reftable/VERSION | 1 + reftable/basics.c | 215 +++ reftable/basics.h | 53 + reftable/block.c | 433 ++++++ reftable/block.h | 129 ++ reftable/block_test.c | 156 ++ reftable/constants.h | 21 + reftable/file.c | 95 ++ reftable/iter.c | 243 +++ reftable/iter.h | 72 + reftable/merged.c | 320 ++++ reftable/merged.h | 39 + reftable/merged_test.c | 273 ++++ reftable/pq.c | 113 ++ reftable/pq.h | 34 + reftable/reader.c | 742 +++++++++ reftable/reader.h | 65 + reftable/record.c | 1113 ++++++++++++++ reftable/record.h | 128 ++ reftable/record_test.c | 400 +++++ reftable/refname.c | 209 +++ reftable/refname.h | 38 + reftable/refname_test.c | 99 ++ reftable/reftable-tests.h | 13 + reftable/reftable.c | 90 ++ reftable/reftable.h | 564 +++++++ reftable/reftable_test.c | 631 ++++++++ reftable/slice.c | 243 +++ reftable/slice.h | 87 ++ reftable/slice_test.c | 40 + reftable/stack.c | 1207 +++++++++++++++ reftable/stack.h | 48 + reftable/stack_test.c | 743 +++++++++ reftable/system.h | 54 + reftable/test_framework.c | 69 + reftable/test_framework.h | 64 + reftable/tree.c | 63 + reftable/tree.h | 34 + reftable/tree_test.c | 62 + reftable/update.sh | 25 + reftable/writer.c | 644 ++++++++ reftable/writer.h | 60 + reftable/zlib-compat.c | 92 ++ repository.c | 2 + repository.h | 3 + sequencer.c | 56 +- setup.c | 12 +- t/helper/test-tool.c | 1 + t/helper/test-tool.h | 1 + t/t0031-reftable.sh | 147 ++ t/t0033-debug-refs.sh | 18 + t/t1409-avoid-packing-refs.sh | 6 + t/t1450-fsck.sh | 6 + t/t3210-pack-refs.sh | 6 + t/t9903-bash-prompt.sh | 6 + t/test-lib.sh | 5 + wt-status.c | 6 +- 80 files changed, 12118 insertions(+), 195 deletions(-) create mode 100644 refs/debug.c 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/block_test.c 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/merged_test.c 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/record_test.c create mode 100644 reftable/refname.c create mode 100644 reftable/refname.h create mode 100644 reftable/refname_test.c create mode 100644 reftable/reftable-tests.h create mode 100644 reftable/reftable.c create mode 100644 reftable/reftable.h create mode 100644 reftable/reftable_test.c create mode 100644 reftable/slice.c create mode 100644 reftable/slice.h create mode 100644 reftable/slice_test.c create mode 100644 reftable/stack.c create mode 100644 reftable/stack.h create mode 100644 reftable/stack_test.c create mode 100644 reftable/system.h create mode 100644 reftable/test_framework.c create mode 100644 reftable/test_framework.h create mode 100644 reftable/tree.c create mode 100644 reftable/tree.h create mode 100644 reftable/tree_test.c 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 create mode 100755 t/t0033-debug-refs.sh base-commit: aada2199e11bff14ee91d5d590c2e3d3eba5e148 Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-539%2Fhanwen%2Freftable-v16 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-539/hanwen/reftable-v16 Pull-Request: https://github.com/gitgitgadget/git/pull/539 Range-diff vs v15: 1: 9bb64f748dc ! 1: 4a1f600fb85 Write pseudorefs through ref backends. @@ refs/refs-internal.h: typedef int copy_ref_fn(struct ref_store *ref_store, + const struct object_id *oid, + const struct object_id *old_oid, + struct strbuf *err); ++ ++/* ++ * Deletes a pseudoref. Deletion always succeeds (even if the pseudoref doesn't ++ * exist.), except if old_oid is specified. If it is, it can fail due to lock ++ * failure, failure reading the old OID, or an OID mismatch ++ */ +typedef int delete_pseudoref_fn(struct ref_store *ref_store, + const char *pseudoref, + const struct object_id *old_oid); 2: d489806907b = 2: a4a67ce9635 Make refs_ref_exists public 3: 60a82678a1b = 3: ecd6591d86f Treat BISECT_HEAD as a pseudo ref 4: 1a925f5671a ! 4: 7c31727de69 Treat CHERRY_PICK_HEAD as a pseudo ref @@ sequencer.c: static int commit_staged_changes(struct repository *r, - if (file_exists(cherry_pick_head) && unlink(cherry_pick_head)) + if (refs_ref_exists(get_main_ref_store(r), + "CHERRY_PICK_HEAD") && -+ !refs_delete_pseudoref(get_main_ref_store(r), -+ "CHERRY_PICK_HEAD", NULL)) ++ refs_delete_pseudoref(get_main_ref_store(r), ++ "CHERRY_PICK_HEAD", NULL)) return error(_("could not remove CHERRY_PICK_HEAD")); if (!final_fixup) return 0; 5: 8f2ebf65b90 ! 5: fbdcee5208b Treat REVERT_HEAD as a pseudo ref @@ sequencer.c: static int create_seq_dir(struct repository *r) const char *in_progress_advice = NULL; unsigned int advise_skip = - file_exists(git_path_revert_head(r)) || -- refs_ref_exists(get_main_ref_store(r), "CHERRY_PICK_HEAD"); -+ refs_ref_exists(get_main_ref_store(r), "REVERT_HEAD"); -+ refs_ref_exists(get_main_ref_store(r), "CHERRY_PICK_HEAD"); ++ refs_ref_exists(get_main_ref_store(r), "REVERT_HEAD") || + refs_ref_exists(get_main_ref_store(r), "CHERRY_PICK_HEAD"); if (!sequencer_get_last_command(r, &action)) { - switch (action) { @@ sequencer.c: static int rollback_single_pick(struct repository *r) struct object_id head_oid; 6: e0e1e3a558d = 6: d8801367f7d Move REF_LOG_ONLY to refs-internal.h 7: 27a980d1d9d = 7: 556d57610cc Iterate over the "refs/" namespace in for_each_[raw]ref 8: dcbd000e7f7 = 8: 78cb1930172 Add .gitattributes for the reftable/ directory 9: 718b646a54e ! 9: 0bc28ac610f Add reftable library @@ reftable/README.md (new) ## reftable/VERSION (new) ## @@ -+commit fe15c65dd95b6a13de92b4baf711e50338ef20ae -+Author: Han-Wen Nienhuys <hanwen@google.com> -+Date: Thu May 28 19:28:24 2020 +0200 -+ -+ C: add 'canary' to struct slice -+ -+ This enforces that all slices are initialized explicitly with -+ SLICE_INIT, for future compatibility with git's strbuf. ++0c164275ea8f8aa7d099f7425ddcef1affe137e9 C: compile framework with Git options ## reftable/basics.c (new) ## @@ @@ reftable/block.c (new) +} + +int block_writer_register_restart(struct block_writer *w, int n, bool restart, -+ struct slice key); ++ struct slice *key); + +void block_writer_init(struct block_writer *bw, byte typ, byte *buf, + uint32_t block_size, uint32_t header_off, int hash_size) @@ reftable/block.c (new) + slice_consume(&out, n); + + if (block_writer_register_restart(w, start.len - out.len, restart, -+ key) < 0) ++ &key) < 0) + goto done; + + slice_release(&key); @@ reftable/block.c (new) +} + +int block_writer_register_restart(struct block_writer *w, int n, bool restart, -+ struct slice key) ++ struct slice *key) +{ + int rlen = w->restart_len; + if (rlen >= MAX_RESTARTS) { @@ reftable/block.c (new) + return -1; + } + -+ result = slice_cmp(a->key, rkey); ++ result = slice_cmp(&a->key, &rkey); + slice_release(&rkey); + return result; +} @@ reftable/block.c (new) +{ + dest->br = src->br; + dest->next_off = src->next_off; -+ slice_copy(&dest->last_key, src->last_key); ++ slice_copy(&dest->last_key, &src->last_key); +} + +int block_iter_next(struct block_iter *it, struct reftable_record *rec) @@ reftable/block.c (new) + return -1; + slice_consume(&in, n); + -+ slice_copy(&it->last_key, key); ++ slice_copy(&it->last_key, &key); + it->next_off += start.len - in.len; + slice_release(&key); + return 0; @@ reftable/block.c (new) + return 0; +} + -+int block_iter_seek(struct block_iter *it, struct slice want) ++int block_iter_seek(struct block_iter *it, struct slice *want) +{ + return block_reader_seek(it->br, it, want); +} @@ reftable/block.c (new) +} + +int block_reader_seek(struct block_reader *br, struct block_iter *it, -+ struct slice want) ++ struct slice *want) +{ + struct restart_find_args args = { -+ .key = want, ++ .key = *want, + .r = br, + }; + struct reftable_record rec = reftable_new_record(block_reader_type(br)); @@ reftable/block.c (new) + goto done; + + reftable_record_key(&rec, &key); -+ if (err > 0 || slice_cmp(key, want) >= 0) { ++ if (err > 0 || slice_cmp(&key, want) >= 0) { + err = 0; + goto done; + } @@ reftable/block.h (new) + +/* Position `it` to the `want` key in the block */ +int block_reader_seek(struct block_reader *br, struct block_iter *it, -+ struct slice want); ++ struct slice *want); + +/* Returns the block type (eg. 'r' for refs) */ +byte block_reader_type(struct block_reader *r); @@ reftable/block.h (new) +int block_iter_next(struct block_iter *it, struct reftable_record *rec); + +/* Seek to `want` with in the block pointed to by `it` */ -+int block_iter_seek(struct block_iter *it, struct slice want); ++int block_iter_seek(struct block_iter *it, struct slice *want); + +/* deallocate memory for `it`. The block reader and its block is left intact. */ +void block_iter_close(struct block_iter *it); @@ reftable/block.h (new) + +#endif + ## reftable/block_test.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 "block.h" ++ ++#include "system.h" ++ ++#include "basics.h" ++#include "constants.h" ++#include "record.h" ++#include "reftable.h" ++#include "test_framework.h" ++#include "reftable-tests.h" ++ ++struct binsearch_args { ++ int key; ++ int *arr; ++}; ++ ++static int binsearch_func(size_t i, void *void_args) ++{ ++ struct binsearch_args *args = (struct binsearch_args *)void_args; ++ ++ return args->key < args->arr[i]; ++} ++ ++static void test_binsearch(void) ++{ ++ int arr[] = { 2, 4, 6, 8, 10 }; ++ size_t sz = ARRAY_SIZE(arr); ++ struct binsearch_args args = { ++ .arr = arr, ++ }; ++ ++ int i = 0; ++ for (i = 1; i < 11; i++) { ++ int res; ++ args.key = i; ++ res = binsearch(sz, &binsearch_func, &args); ++ ++ if (res < sz) { ++ assert(args.key < arr[res]); ++ if (res > 0) { ++ assert(args.key >= arr[res - 1]); ++ } ++ } else { ++ assert(args.key == 10 || args.key == 11); ++ } ++ } ++} ++ ++static void test_block_read_write(void) ++{ ++ const int header_off = 21; /* random */ ++ char *names[30]; ++ const int N = ARRAY_SIZE(names); ++ const int block_size = 1024; ++ struct reftable_block block = { 0 }; ++ struct block_writer bw = { ++ .last_key = SLICE_INIT, ++ }; ++ struct reftable_ref_record ref = { 0 }; ++ struct reftable_record rec = { 0 }; ++ int i = 0; ++ int n; ++ struct block_reader br = { 0 }; ++ struct block_iter it = { .last_key = SLICE_INIT }; ++ int j = 0; ++ struct slice want = SLICE_INIT; ++ ++ block.data = reftable_calloc(block_size); ++ block.len = block_size; ++ block.source = malloc_block_source(); ++ block_writer_init(&bw, BLOCK_TYPE_REF, block.data, block_size, ++ header_off, hash_size(SHA1_ID)); ++ reftable_record_from_ref(&rec, &ref); ++ ++ for (i = 0; i < N; i++) { ++ char name[100]; ++ byte hash[SHA1_SIZE]; ++ snprintf(name, sizeof(name), "branch%02d", i); ++ memset(hash, i, sizeof(hash)); ++ ++ ref.ref_name = name; ++ ref.value = hash; ++ names[i] = xstrdup(name); ++ n = block_writer_add(&bw, &rec); ++ ref.ref_name = NULL; ++ ref.value = NULL; ++ assert(n == 0); ++ } ++ ++ n = block_writer_finish(&bw); ++ assert(n > 0); ++ ++ block_writer_clear(&bw); ++ ++ block_reader_init(&br, &block, header_off, block_size, SHA1_SIZE); ++ ++ block_reader_start(&br, &it); ++ ++ while (true) { ++ int r = block_iter_next(&it, &rec); ++ assert(r >= 0); ++ if (r > 0) { ++ break; ++ } ++ assert_streq(names[j], ref.ref_name); ++ j++; ++ } ++ ++ reftable_record_clear(&rec); ++ block_iter_close(&it); ++ ++ for (i = 0; i < N; i++) { ++ struct block_iter it = { .last_key = SLICE_INIT }; ++ slice_set_string(&want, names[i]); ++ ++ n = block_reader_seek(&br, &it, &want); ++ assert(n == 0); ++ ++ n = block_iter_next(&it, &rec); ++ assert(n == 0); ++ ++ assert_streq(names[i], ref.ref_name); ++ ++ want.len--; ++ n = block_reader_seek(&br, &it, &want); ++ assert(n == 0); ++ ++ n = block_iter_next(&it, &rec); ++ assert(n == 0); ++ assert_streq(names[10 * (i / 10)], ref.ref_name); ++ ++ block_iter_close(&it); ++ } ++ ++ reftable_record_clear(&rec); ++ reftable_block_done(&br.block); ++ slice_release(&want); ++ for (i = 0; i < N; i++) { ++ reftable_free(names[i]); ++ } ++} ++ ++int block_test_main(int argc, const char *argv[]) ++{ ++ add_test_case("binsearch", &test_binsearch); ++ add_test_case("block_read_write", &test_block_read_write); ++ return test_main(argc, argv); ++} + ## reftable/constants.h (new) ## @@ +/* @@ reftable/merged.c (new) + + reftable_record_key(&top.rec, &k); + -+ cmp = slice_cmp(k, entry_key); ++ cmp = slice_cmp(&k, &entry_key); + slice_release(&k); + + if (cmp > 0) { @@ reftable/merged.h (new) + +#endif + ## reftable/merged_test.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 "merged.h" ++ ++#include "system.h" ++ ++#include "basics.h" ++#include "block.h" ++#include "constants.h" ++#include "pq.h" ++#include "reader.h" ++#include "record.h" ++#include "reftable.h" ++#include "test_framework.h" ++#include "reftable-tests.h" ++ ++static void test_pq(void) ++{ ++ char *names[54] = { 0 }; ++ int N = ARRAY_SIZE(names) - 1; ++ ++ struct merged_iter_pqueue pq = { 0 }; ++ const char *last = NULL; ++ ++ int i = 0; ++ for (i = 0; i < N; i++) { ++ char name[100]; ++ snprintf(name, sizeof(name), "%02d", i); ++ names[i] = xstrdup(name); ++ } ++ ++ i = 1; ++ do { ++ struct reftable_record rec = ++ reftable_new_record(BLOCK_TYPE_REF); ++ struct pq_entry e = { 0 }; ++ ++ reftable_record_as_ref(&rec)->ref_name = names[i]; ++ e.rec = rec; ++ merged_iter_pqueue_add(&pq, e); ++ merged_iter_pqueue_check(pq); ++ i = (i * 7) % N; ++ } while (i != 1); ++ ++ while (!merged_iter_pqueue_is_empty(pq)) { ++ struct pq_entry e = merged_iter_pqueue_remove(&pq); ++ struct reftable_ref_record *ref = ++ reftable_record_as_ref(&e.rec); ++ ++ merged_iter_pqueue_check(pq); ++ ++ if (last != NULL) { ++ assert(strcmp(last, ref->ref_name) < 0); ++ } ++ last = ref->ref_name; ++ ref->ref_name = NULL; ++ reftable_free(ref); ++ } ++ ++ for (i = 0; i < N; i++) { ++ reftable_free(names[i]); ++ } ++ ++ merged_iter_pqueue_clear(&pq); ++} ++ ++static void write_test_table(struct slice *buf, ++ struct reftable_ref_record refs[], int n) ++{ ++ int min = 0xffffffff; ++ int max = 0; ++ int i = 0; ++ int err; ++ ++ struct reftable_write_options opts = { ++ .block_size = 256, ++ }; ++ struct reftable_writer *w = NULL; ++ for (i = 0; i < n; i++) { ++ uint64_t ui = refs[i].update_index; ++ if (ui > max) { ++ max = ui; ++ } ++ if (ui < min) { ++ min = ui; ++ } ++ } ++ ++ w = reftable_new_writer(&slice_add_void, buf, &opts); ++ reftable_writer_set_limits(w, min, max); ++ ++ for (i = 0; i < n; i++) { ++ uint64_t before = refs[i].update_index; ++ int n = reftable_writer_add_ref(w, &refs[i]); ++ assert(n == 0); ++ assert(before == refs[i].update_index); ++ } ++ ++ err = reftable_writer_close(w); ++ assert_err(err); ++ ++ reftable_writer_free(w); ++} ++ ++static struct reftable_merged_table * ++merged_table_from_records(struct reftable_ref_record **refs, ++ struct reftable_block_source **source, int *sizes, ++ struct slice *buf, int n) ++{ ++ struct reftable_reader **rd = reftable_calloc(n * sizeof(*rd)); ++ int i = 0; ++ struct reftable_merged_table *mt = NULL; ++ int err; ++ *source = reftable_calloc(n * sizeof(**source)); ++ for (i = 0; i < n; i++) { ++ write_test_table(&buf[i], refs[i], sizes[i]); ++ block_source_from_slice(&(*source)[i], &buf[i]); ++ ++ err = reftable_new_reader(&rd[i], &(*source)[i], "name"); ++ assert_err(err); ++ } ++ ++ err = reftable_new_merged_table(&mt, rd, n, SHA1_ID); ++ assert_err(err); ++ return mt; ++} ++ ++static void test_merged_between(void) ++{ ++ byte hash1[SHA1_SIZE] = { 1, 2, 3, 0 }; ++ ++ struct reftable_ref_record r1[] = { { ++ .ref_name = "b", ++ .update_index = 1, ++ .value = hash1, ++ } }; ++ struct reftable_ref_record r2[] = { { ++ .ref_name = "a", ++ .update_index = 2, ++ } }; ++ ++ struct reftable_ref_record *refs[] = { r1, r2 }; ++ int sizes[] = { 1, 1 }; ++ struct slice bufs[2] = { SLICE_INIT, SLICE_INIT }; ++ struct reftable_block_source *bs = NULL; ++ struct reftable_merged_table *mt = ++ merged_table_from_records(refs, &bs, sizes, bufs, 2); ++ int i; ++ struct reftable_ref_record ref = { 0 }; ++ struct reftable_iterator it = { 0 }; ++ int err = reftable_merged_table_seek_ref(mt, &it, "a"); ++ assert_err(err); ++ ++ err = reftable_iterator_next_ref(&it, &ref); ++ assert_err(err); ++ assert(ref.update_index == 2); ++ reftable_ref_record_clear(&ref); ++ ++ reftable_iterator_destroy(&it); ++ reftable_merged_table_close(mt); ++ reftable_merged_table_free(mt); ++ for (i = 0; i < ARRAY_SIZE(bufs); i++) { ++ slice_release(&bufs[i]); ++ } ++ reftable_free(bs); ++} ++ ++static void test_merged(void) ++{ ++ byte hash1[SHA1_SIZE] = { 1 }; ++ byte hash2[SHA1_SIZE] = { 2 }; ++ struct reftable_ref_record r1[] = { { ++ .ref_name = "a", ++ .update_index = 1, ++ .value = hash1, ++ }, ++ { ++ .ref_name = "b", ++ .update_index = 1, ++ .value = hash1, ++ }, ++ { ++ .ref_name = "c", ++ .update_index = 1, ++ .value = hash1, ++ } }; ++ struct reftable_ref_record r2[] = { { ++ .ref_name = "a", ++ .update_index = 2, ++ } }; ++ struct reftable_ref_record r3[] = { ++ { ++ .ref_name = "c", ++ .update_index = 3, ++ .value = hash2, ++ }, ++ { ++ .ref_name = "d", ++ .update_index = 3, ++ .value = hash1, ++ }, ++ }; ++ ++ struct reftable_ref_record want[] = { ++ r2[0], ++ r1[1], ++ r3[0], ++ r3[1], ++ }; ++ ++ struct reftable_ref_record *refs[] = { r1, r2, r3 }; ++ int sizes[3] = { 3, 1, 2 }; ++ struct slice bufs[3] = { SLICE_INIT, SLICE_INIT, SLICE_INIT }; ++ struct reftable_block_source *bs = NULL; ++ ++ struct reftable_merged_table *mt = ++ merged_table_from_records(refs, &bs, sizes, bufs, 3); ++ ++ struct reftable_iterator it = { 0 }; ++ int err = reftable_merged_table_seek_ref(mt, &it, "a"); ++ struct reftable_ref_record *out = NULL; ++ int len = 0; ++ int cap = 0; ++ int i = 0; ++ ++ assert_err(err); ++ while (len < 100) { /* cap loops/recursion. */ ++ struct reftable_ref_record ref = { 0 }; ++ int err = reftable_iterator_next_ref(&it, &ref); ++ if (err > 0) { ++ break; ++ } ++ if (len == cap) { ++ cap = 2 * cap + 1; ++ out = reftable_realloc( ++ out, sizeof(struct reftable_ref_record) * cap); ++ } ++ out[len++] = ref; ++ } ++ reftable_iterator_destroy(&it); ++ ++ assert(ARRAY_SIZE(want) == len); ++ for (i = 0; i < len; i++) { ++ assert(reftable_ref_record_equal(&want[i], &out[i], SHA1_SIZE)); ++ } ++ for (i = 0; i < len; i++) { ++ reftable_ref_record_clear(&out[i]); ++ } ++ reftable_free(out); ++ ++ for (i = 0; i < 3; i++) { ++ slice_release(&bufs[i]); ++ } ++ reftable_merged_table_close(mt); ++ reftable_merged_table_free(mt); ++ reftable_free(bs); ++} ++ ++/* XXX test refs_for(oid) */ ++ ++int merged_test_main(int argc, const char *argv[]) ++{ ++ add_test_case("test_merged_between", &test_merged_between); ++ add_test_case("test_pq", &test_pq); ++ add_test_case("test_merged", &test_merged); ++ return test_main(argc, argv); ++} + ## reftable/pq.c (new) ## @@ +/* @@ reftable/pq.c (new) + reftable_record_key(&a.rec, &ak); + reftable_record_key(&b.rec, &bk); + -+ cmp = slice_cmp(ak, bk); ++ cmp = slice_cmp(&ak, &bk); + + slice_release(&ak); + slice_release(&bk); @@ reftable/reader.c (new) + if (err < 0) + goto done; + -+ if (slice_cmp(got_key, want_key) > 0) { ++ if (slice_cmp(&got_key, &want_key) > 0) { + table_iter_block_done(&next); + break; + } @@ reftable/reader.c (new) + table_iter_copy_from(ti, &next); + } + -+ err = block_iter_seek(&ti->bi, want_key); ++ err = block_iter_seek(&ti->bi, &want_key); + if (err < 0) + goto done; + err = 0; @@ reftable/reader.c (new) + if (err != 0) + goto done; + -+ err = block_iter_seek(&next.bi, want_index.last_key); ++ err = block_iter_seek(&next.bi, &want_index.last_key); + if (err < 0) + goto done; + @@ reftable/record.c (new) +#include "constants.h" +#include "reftable.h" + -+int get_var_int(uint64_t *dest, struct slice in) ++int get_var_int(uint64_t *dest, struct slice *in) +{ + int ptr = 0; + uint64_t val; + -+ if (in.len == 0) ++ if (in->len == 0) + return -1; -+ val = in.buf[ptr] & 0x7f; ++ val = in->buf[ptr] & 0x7f; + -+ while (in.buf[ptr] & 0x80) { ++ while (in->buf[ptr] & 0x80) { + ptr++; -+ if (ptr > in.len) { ++ if (ptr > in->len) { + return -1; + } -+ val = (val + 1) << 7 | (uint64_t)(in.buf[ptr] & 0x7f); ++ val = (val + 1) << 7 | (uint64_t)(in->buf[ptr] & 0x7f); + } + + *dest = val; + return ptr + 1; +} + -+int put_var_int(struct slice dest, uint64_t val) ++int put_var_int(struct slice *dest, uint64_t val) +{ + byte buf[10] = { 0 }; + int i = 9; @@ reftable/record.c (new) + } + + n = sizeof(buf) - i - 1; -+ if (dest.len < n) ++ if (dest->len < n) + return -1; -+ memcpy(dest.buf, &buf[i + 1], n); ++ memcpy(dest->buf, &buf[i + 1], n); + return n; +} + @@ reftable/record.c (new) +{ + int start_len = in.len; + uint64_t tsize = 0; -+ int n = get_var_int(&tsize, in); ++ int n = get_var_int(&tsize, &in); + if (n <= 0) + return -1; + slice_consume(&in, n); @@ reftable/record.c (new) +{ + struct slice start = s; + int l = strlen(str); -+ int n = put_var_int(s, l); ++ int n = put_var_int(&s, l); + if (n < 0) + return -1; + slice_consume(&s, n); @@ reftable/record.c (new) + struct slice key, byte extra) +{ + struct slice start = dest; -+ int prefix_len = common_prefix_size(prev_key, key); ++ int prefix_len = common_prefix_size(&prev_key, &key); + uint64_t suffix_len = key.len - prefix_len; -+ int n = put_var_int(dest, (uint64_t)prefix_len); ++ int n = put_var_int(&dest, (uint64_t)prefix_len); + if (n < 0) + return -1; + slice_consume(&dest, n); + + *restart = (prefix_len == 0); + -+ n = put_var_int(dest, suffix_len << 3 | (uint64_t)extra); ++ n = put_var_int(&dest, suffix_len << 3 | (uint64_t)extra); + if (n < 0) + return -1; + slice_consume(&dest, n); @@ reftable/record.c (new) + int start_len = in.len; + uint64_t prefix_len = 0; + uint64_t suffix_len = 0; -+ int n = get_var_int(&prefix_len, in); ++ int n = get_var_int(&prefix_len, &in); + if (n < 0) + return -1; + slice_consume(&in, n); @@ reftable/record.c (new) + if (prefix_len > last_key.len) + return -1; + -+ n = get_var_int(&suffix_len, in); ++ n = get_var_int(&suffix_len, &in); + if (n <= 0) + return -1; + slice_consume(&in, n); @@ reftable/record.c (new) + const struct reftable_ref_record *r = + (const struct reftable_ref_record *)rec; + struct slice start = s; -+ int n = put_var_int(s, r->update_index); ++ int n = put_var_int(&s, r->update_index); + assert(hash_size > 0); + if (n < 0) + return -1; @@ reftable/record.c (new) + bool seen_target_value = false; + bool seen_target = false; + -+ int n = get_var_int(&r->update_index, in); ++ int n = get_var_int(&r->update_index, &in); + if (n < 0) + return n; + assert(hash_size > 0); @@ reftable/record.c (new) + int n = 0; + uint64_t last = 0; + if (r->offset_len == 0 || r->offset_len >= 8) { -+ n = put_var_int(s, r->offset_len); ++ n = put_var_int(&s, r->offset_len); + if (n < 0) { + return -1; + } @@ reftable/record.c (new) + } + if (r->offset_len == 0) + return start.len - s.len; -+ n = put_var_int(s, r->offsets[0]); ++ n = put_var_int(&s, r->offsets[0]); + if (n < 0) + return -1; + slice_consume(&s, n); + + last = r->offsets[0]; + for (i = 1; i < r->offset_len; i++) { -+ int n = put_var_int(s, r->offsets[i] - last); ++ int n = put_var_int(&s, r->offsets[i] - last); + if (n < 0) { + return -1; + } @@ reftable/record.c (new) + r->hash_prefix_len = key.len; + + if (val_type == 0) { -+ n = get_var_int(&count, in); ++ n = get_var_int(&count, &in); + if (n < 0) { + return n; + } @@ reftable/record.c (new) + r->offsets = reftable_malloc(count * sizeof(uint64_t)); + r->offset_len = count; + -+ n = get_var_int(&r->offsets[0], in); ++ n = get_var_int(&r->offsets[0], &in); + if (n < 0) + return n; + slice_consume(&in, n); @@ reftable/record.c (new) + j = 1; + while (j < count) { + uint64_t delta = 0; -+ int n = get_var_int(&delta, in); ++ int n = get_var_int(&delta, &in); + if (n < 0) { + return n; + } @@ reftable/record.c (new) + return -1; + slice_consume(&s, n); + -+ n = put_var_int(s, r->time); ++ n = put_var_int(&s, r->time); + if (n < 0) + return -1; + slice_consume(&s, n); @@ reftable/record.c (new) + r->email[dest.len] = 0; + + ts = 0; -+ n = get_var_int(&ts, in); ++ n = get_var_int(&ts, &in); + if (n < 0) + goto done; + slice_consume(&in, n); @@ reftable/record.c (new) +static void reftable_index_record_key(const void *r, struct slice *dest) +{ + struct reftable_index_record *rec = (struct reftable_index_record *)r; -+ slice_copy(dest, rec->last_key); ++ slice_copy(dest, &rec->last_key); +} + +static void reftable_index_record_copy_from(void *rec, const void *src_rec, @@ reftable/record.c (new) + struct reftable_index_record *src = + (struct reftable_index_record *)src_rec; + -+ slice_copy(&dst->last_key, src->last_key); ++ slice_copy(&dst->last_key, &src->last_key); + dst->offset = src->offset; +} + @@ reftable/record.c (new) + (const struct reftable_index_record *)rec; + struct slice start = out; + -+ int n = put_var_int(out, r->offset); ++ int n = put_var_int(&out, r->offset); + if (n < 0) + return n; + @@ reftable/record.c (new) + struct reftable_index_record *r = (struct reftable_index_record *)rec; + int n = 0; + -+ slice_copy(&r->last_key, key); ++ slice_copy(&r->last_key, &key); + -+ n = get_var_int(&r->offset, in); ++ n = get_var_int(&r->offset, &in); + if (n < 0) + return n; + @@ reftable/record.h (new) + +/* utilities for de/encoding varints */ + -+int get_var_int(uint64_t *dest, struct slice in); -+int put_var_int(struct slice dest, uint64_t val); ++int get_var_int(uint64_t *dest, struct slice *in); ++int put_var_int(struct slice *dest, uint64_t val); + +/* Methods for records. */ +struct reftable_record_vtable { @@ reftable/record.h (new) + +#endif - ## reftable/refname.c (new) ## + ## reftable/record_test.c (new) ## @@ +/* -+ Copyright 2020 Google LLC ++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 ++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 "record.h" ++ +#include "system.h" -+#include "reftable.h" +#include "basics.h" -+#include "refname.h" -+#include "slice.h" -+ -+struct find_arg { -+ char **names; -+ const char *want; -+}; ++#include "constants.h" ++#include "reftable.h" ++#include "test_framework.h" ++#include "reftable-tests.h" + -+static int find_name(size_t k, void *arg) ++static void test_copy(struct reftable_record *rec) +{ -+ struct find_arg *f_arg = (struct find_arg *)arg; -+ return strcmp(f_arg->names[k], f_arg->want) >= 0; ++ struct reftable_record copy = ++ reftable_new_record(reftable_record_type(rec)); ++ reftable_record_copy_from(©, rec, SHA1_SIZE); ++ /* do it twice to catch memory leaks */ ++ reftable_record_copy_from(©, rec, SHA1_SIZE); ++ switch (reftable_record_type(©)) { ++ case BLOCK_TYPE_REF: ++ assert(reftable_ref_record_equal(reftable_record_as_ref(©), ++ reftable_record_as_ref(rec), ++ SHA1_SIZE)); ++ break; ++ case BLOCK_TYPE_LOG: ++ assert(reftable_log_record_equal(reftable_record_as_log(©), ++ reftable_record_as_log(rec), ++ SHA1_SIZE)); ++ break; ++ } ++ reftable_record_destroy(©); +} + -+int modification_has_ref(struct modification *mod, const char *name) ++static void test_varint_roundtrip(void) +{ -+ struct reftable_ref_record ref = { 0 }; -+ int err = 0; ++ uint64_t inputs[] = { 0, ++ 1, ++ 27, ++ 127, ++ 128, ++ 257, ++ 4096, ++ ((uint64_t)1 << 63), ++ ((uint64_t)1 << 63) + ((uint64_t)1 << 63) - 1 }; ++ int i = 0; ++ for (i = 0; i < ARRAY_SIZE(inputs); i++) { ++ byte dest[10]; + -+ 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; -+ } -+ } ++ struct slice out = { .buf = dest, .len = 10, .cap = 10 }; + -+ 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; -+ } ++ uint64_t in = inputs[i]; ++ int n = put_var_int(&out, in); ++ uint64_t got = 0; ++ ++ assert(n > 0); ++ out.len = n; ++ n = get_var_int(&got, &out); ++ assert(n > 0); ++ ++ assert(got == in); + } ++} + -+ err = reftable_table_read_ref(&mod->tab, name, &ref); -+ reftable_ref_record_clear(&ref); -+ return err; ++static void test_common_prefix(void) ++{ ++ struct { ++ const char *a, *b; ++ int want; ++ } cases[] = { ++ { "abc", "ab", 2 }, ++ { "", "abc", 0 }, ++ { "abc", "abd", 2 }, ++ { "abc", "pqr", 0 }, ++ }; ++ ++ int i = 0; ++ for (i = 0; i < ARRAY_SIZE(cases); i++) { ++ struct slice a = SLICE_INIT; ++ struct slice b = SLICE_INIT; ++ slice_set_string(&a, cases[i].a); ++ slice_set_string(&b, cases[i].b); ++ ++ assert(common_prefix_size(&a, &b) == cases[i].want); ++ ++ slice_release(&a); ++ slice_release(&b); ++ } +} + -+static void modification_clear(struct modification *mod) ++static void set_hash(byte *h, int j) +{ -+ /* don't delete the strings themselves; they're owned by ref records. -+ */ -+ FREE_AND_NULL(mod->add); -+ FREE_AND_NULL(mod->del); -+ mod->add_len = 0; -+ mod->del_len = 0; ++ int i = 0; ++ for (i = 0; i < hash_size(SHA1_ID); i++) { ++ h[i] = (j >> i) & 0xff; ++ } +} + -+int modification_has_ref_with_prefix(struct modification *mod, -+ const char *prefix) ++static void test_reftable_ref_record_roundtrip(void) +{ -+ struct reftable_iterator it = { NULL }; -+ struct reftable_ref_record ref = { NULL }; -+ int err = 0; ++ int i = 0; ++ ++ for (i = 0; i <= 3; i++) { ++ struct reftable_ref_record in = { 0 }; ++ struct reftable_ref_record out = { ++ .ref_name = xstrdup("old name"), ++ .value = reftable_calloc(SHA1_SIZE), ++ .target_value = reftable_calloc(SHA1_SIZE), ++ .target = xstrdup("old value"), ++ }; ++ struct reftable_record rec_out = { 0 }; ++ struct slice key = SLICE_INIT; ++ struct reftable_record rec = { 0 }; ++ struct slice dest = SLICE_INIT; ++ int n, m; ++ ++ switch (i) { ++ case 0: ++ break; ++ case 1: ++ in.value = reftable_malloc(SHA1_SIZE); ++ set_hash(in.value, 1); ++ break; ++ case 2: ++ in.value = reftable_malloc(SHA1_SIZE); ++ set_hash(in.value, 1); ++ in.target_value = reftable_malloc(SHA1_SIZE); ++ set_hash(in.target_value, 2); ++ break; ++ case 3: ++ in.target = xstrdup("target"); ++ break; ++ } ++ in.ref_name = xstrdup("refs/heads/master"); ++ ++ reftable_record_from_ref(&rec, &in); ++ test_copy(&rec); ++ ++ assert(reftable_record_val_type(&rec) == i); ++ ++ reftable_record_key(&rec, &key); ++ slice_resize(&dest, 1024); ++ n = reftable_record_encode(&rec, dest, SHA1_SIZE); ++ assert(n > 0); ++ ++ /* decode into a non-zero reftable_record to test for leaks. */ ++ ++ reftable_record_from_ref(&rec_out, &out); ++ m = reftable_record_decode(&rec_out, key, i, dest, SHA1_SIZE); ++ assert(n == m); ++ ++ assert((out.value != NULL) == (in.value != NULL)); ++ assert((out.target_value != NULL) == (in.target_value != NULL)); ++ assert((out.target != NULL) == (in.target != NULL)); ++ reftable_record_clear(&rec_out); ++ ++ slice_release(&key); ++ slice_release(&dest); ++ reftable_ref_record_clear(&in); ++ } ++} ++ ++static void test_reftable_log_record_equal(void) ++{ ++ struct reftable_log_record in[2] = { ++ { ++ .ref_name = xstrdup("refs/heads/master"), ++ .update_index = 42, ++ }, ++ { ++ .ref_name = xstrdup("refs/heads/master"), ++ .update_index = 22, ++ } ++ }; ++ ++ assert(!reftable_log_record_equal(&in[0], &in[1], SHA1_SIZE)); ++ in[1].update_index = in[0].update_index; ++ assert(reftable_log_record_equal(&in[0], &in[1], SHA1_SIZE)); ++ reftable_log_record_clear(&in[0]); ++ reftable_log_record_clear(&in[1]); ++} ++ ++static void test_reftable_log_record_roundtrip(void) ++{ ++ struct reftable_log_record in[2] = { ++ { ++ .ref_name = xstrdup("refs/heads/master"), ++ .old_hash = reftable_malloc(SHA1_SIZE), ++ .new_hash = reftable_malloc(SHA1_SIZE), ++ .name = xstrdup("han-wen"), ++ .email = xstrdup("hanwen@google.com"), ++ .message = xstrdup("test"), ++ .update_index = 42, ++ .time = 1577123507, ++ .tz_offset = 100, ++ }, ++ { ++ .ref_name = xstrdup("refs/heads/master"), ++ .update_index = 22, ++ } ++ }; ++ set_test_hash(in[0].new_hash, 1); ++ set_test_hash(in[0].old_hash, 2); ++ for (int i = 0; i < ARRAY_SIZE(in); i++) { ++ struct reftable_record rec = { 0 }; ++ struct slice key = SLICE_INIT; ++ struct slice dest = SLICE_INIT; ++ /* populate out, to check for leaks. */ ++ struct reftable_log_record out = { ++ .ref_name = xstrdup("old name"), ++ .new_hash = reftable_calloc(SHA1_SIZE), ++ .old_hash = reftable_calloc(SHA1_SIZE), ++ .name = xstrdup("old name"), ++ .email = xstrdup("old@email"), ++ .message = xstrdup("old message"), ++ }; ++ struct reftable_record rec_out = { 0 }; ++ int n, m, valtype; ++ ++ reftable_record_from_log(&rec, &in[i]); ++ ++ test_copy(&rec); ++ ++ reftable_record_key(&rec, &key); ++ ++ slice_resize(&dest, 1024); ++ ++ n = reftable_record_encode(&rec, dest, SHA1_SIZE); ++ assert(n >= 0); ++ reftable_record_from_log(&rec_out, &out); ++ valtype = reftable_record_val_type(&rec); ++ m = reftable_record_decode(&rec_out, key, valtype, dest, ++ SHA1_SIZE); ++ assert(n == m); ++ ++ assert(reftable_log_record_equal(&in[i], &out, SHA1_SIZE)); ++ reftable_log_record_clear(&in[i]); ++ slice_release(&key); ++ slice_release(&dest); ++ reftable_record_clear(&rec_out); ++ } ++} ++ ++static void test_u24_roundtrip(void) ++{ ++ uint32_t in = 0x112233; ++ byte dest[3]; ++ uint32_t out; ++ put_be24(dest, in); ++ out = get_be24(dest); ++ assert(in == out); ++} ++ ++static void test_key_roundtrip(void) ++{ ++ struct slice dest = SLICE_INIT; ++ struct slice last_key = SLICE_INIT; ++ struct slice key = SLICE_INIT; ++ struct slice roundtrip = SLICE_INIT; ++ bool restart; ++ byte extra; ++ int n, m; ++ byte rt_extra; ++ ++ slice_resize(&dest, 1024); ++ slice_set_string(&last_key, "refs/heads/master"); ++ slice_set_string(&key, "refs/tags/bla"); ++ ++ extra = 6; ++ n = reftable_encode_key(&restart, dest, last_key, key, extra); ++ assert(!restart); ++ assert(n > 0); ++ ++ m = reftable_decode_key(&roundtrip, &rt_extra, last_key, dest); ++ assert(n == m); ++ assert(slice_equal(&key, &roundtrip)); ++ assert(rt_extra == extra); ++ ++ slice_release(&last_key); ++ slice_release(&key); ++ slice_release(&dest); ++ slice_release(&roundtrip); ++} ++ ++static void test_reftable_obj_record_roundtrip(void) ++{ ++ byte testHash1[SHA1_SIZE] = { 1, 2, 3, 4, 0 }; ++ uint64_t till9[] = { 1, 2, 3, 4, 500, 600, 700, 800, 9000 }; ++ struct reftable_obj_record recs[3] = { { ++ .hash_prefix = testHash1, ++ .hash_prefix_len = 5, ++ .offsets = till9, ++ .offset_len = 3, ++ }, ++ { ++ .hash_prefix = testHash1, ++ .hash_prefix_len = 5, ++ .offsets = till9, ++ .offset_len = 9, ++ }, ++ { ++ .hash_prefix = testHash1, ++ .hash_prefix_len = 5, ++ } }; ++ int i = 0; ++ for (i = 0; i < ARRAY_SIZE(recs); i++) { ++ struct reftable_obj_record in = recs[i]; ++ struct slice dest = SLICE_INIT; ++ struct reftable_record rec = { 0 }; ++ struct slice key = SLICE_INIT; ++ struct reftable_obj_record out = { 0 }; ++ struct reftable_record rec_out = { 0 }; ++ int n, m; ++ byte extra; ++ ++ reftable_record_from_obj(&rec, &in); ++ test_copy(&rec); ++ reftable_record_key(&rec, &key); ++ slice_resize(&dest, 1024); ++ n = reftable_record_encode(&rec, dest, SHA1_SIZE); ++ assert(n > 0); ++ extra = reftable_record_val_type(&rec); ++ reftable_record_from_obj(&rec_out, &out); ++ m = reftable_record_decode(&rec_out, key, extra, dest, ++ SHA1_SIZE); ++ assert(n == m); ++ ++ assert(in.hash_prefix_len == out.hash_prefix_len); ++ assert(in.offset_len == out.offset_len); ++ ++ assert(!memcmp(in.hash_prefix, out.hash_prefix, ++ in.hash_prefix_len)); ++ assert(0 == memcmp(in.offsets, out.offsets, ++ sizeof(uint64_t) * in.offset_len)); ++ slice_release(&key); ++ slice_release(&dest); ++ reftable_record_clear(&rec_out); ++ } ++} ++ ++static void test_reftable_index_record_roundtrip(void) ++{ ++ struct reftable_index_record in = { ++ .offset = 42, ++ .last_key = SLICE_INIT, ++ }; ++ struct slice dest = SLICE_INIT; ++ struct slice key = SLICE_INIT; ++ struct reftable_record rec = { 0 }; ++ struct reftable_index_record out = { .last_key = SLICE_INIT }; ++ struct reftable_record out_rec = { NULL }; ++ int n, m; ++ byte extra; ++ ++ slice_set_string(&in.last_key, "refs/heads/master"); ++ reftable_record_from_index(&rec, &in); ++ reftable_record_key(&rec, &key); ++ test_copy(&rec); ++ ++ assert(0 == slice_cmp(&key, &in.last_key)); ++ slice_resize(&dest, 1024); ++ n = reftable_record_encode(&rec, dest, SHA1_SIZE); ++ assert(n > 0); ++ ++ extra = reftable_record_val_type(&rec); ++ reftable_record_from_index(&out_rec, &out); ++ m = reftable_record_decode(&out_rec, key, extra, dest, SHA1_SIZE); ++ assert(m == n); ++ ++ assert(in.offset == out.offset); ++ ++ reftable_record_clear(&out_rec); ++ slice_release(&key); ++ slice_release(&in.last_key); ++ slice_release(&dest); ++} ++ ++int record_test_main(int argc, const char *argv[]) ++{ ++ add_test_case("test_reftable_log_record_equal", ++ &test_reftable_log_record_equal); ++ add_test_case("test_reftable_log_record_roundtrip", ++ &test_reftable_log_record_roundtrip); ++ add_test_case("test_reftable_ref_record_roundtrip", ++ &test_reftable_ref_record_roundtrip); ++ add_test_case("test_varint_roundtrip", &test_varint_roundtrip); ++ add_test_case("test_key_roundtrip", &test_key_roundtrip); ++ add_test_case("test_common_prefix", &test_common_prefix); ++ add_test_case("test_reftable_obj_record_roundtrip", ++ &test_reftable_obj_record_roundtrip); ++ add_test_case("test_reftable_index_record_roundtrip", ++ &test_reftable_index_record_roundtrip); ++ add_test_case("test_u24_roundtrip", &test_u24_roundtrip); ++ return test_main(argc, argv); ++} + + ## 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) ++{ ++ /* don't delete the strings themselves; they're owned by ref records. ++ */ ++ 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 = { @@ reftable/refname.h (new) + +int modification_validate(struct modification *mod); + ++#endif + + ## reftable/refname_test.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 "basics.h" ++#include "block.h" ++#include "constants.h" ++#include "reader.h" ++#include "record.h" ++#include "refname.h" ++#include "system.h" ++ ++#include "test_framework.h" ++#include "reftable-tests.h" ++ ++struct testcase { ++ char *add; ++ char *del; ++ int error_code; ++}; ++ ++static void test_conflict(void) ++{ ++ struct reftable_write_options opts = { 0 }; ++ struct slice buf = SLICE_INIT; ++ struct reftable_writer *w = ++ reftable_new_writer(&slice_add_void, &buf, &opts); ++ struct reftable_ref_record rec = { ++ .ref_name = "a/b", ++ .target = "destination", /* make sure it's not a symref. */ ++ .update_index = 1, ++ }; ++ int err; ++ int i; ++ struct reftable_block_source source = { 0 }; ++ struct reftable_reader *rd = NULL; ++ struct reftable_table tab = { NULL }; ++ struct testcase cases[] = { ++ { "a/b/c", NULL, REFTABLE_NAME_CONFLICT }, ++ { "b", NULL, 0 }, ++ { "a", NULL, REFTABLE_NAME_CONFLICT }, ++ { "a", "a/b", 0 }, ++ ++ { "p/", NULL, REFTABLE_REFNAME_ERROR }, ++ { "p//q", NULL, REFTABLE_REFNAME_ERROR }, ++ { "p/./q", NULL, REFTABLE_REFNAME_ERROR }, ++ { "p/../q", NULL, REFTABLE_REFNAME_ERROR }, ++ ++ { "a/b/c", "a/b", 0 }, ++ { NULL, "a//b", 0 }, ++ }; ++ reftable_writer_set_limits(w, 1, 1); ++ ++ err = reftable_writer_add_ref(w, &rec); ++ assert_err(err); ++ ++ err = reftable_writer_close(w); ++ assert_err(err); ++ reftable_writer_free(w); ++ ++ block_source_from_slice(&source, &buf); ++ err = reftable_new_reader(&rd, &source, "filename"); ++ assert_err(err); ++ ++ reftable_table_from_reader(&tab, rd); ++ ++ for (i = 0; i < ARRAY_SIZE(cases); i++) { ++ struct modification mod = { ++ .tab = tab, ++ }; ++ ++ if (cases[i].add != NULL) { ++ mod.add = &cases[i].add; ++ mod.add_len = 1; ++ } ++ if (cases[i].del != NULL) { ++ mod.del = &cases[i].del; ++ mod.del_len = 1; ++ } ++ ++ err = modification_validate(&mod); ++ assert(err == cases[i].error_code); ++ } ++ ++ reftable_reader_free(rd); ++ slice_release(&buf); ++} ++ ++int refname_test_main(int argc, const char *argv[]) ++{ ++ add_test_case("test_conflict", &test_conflict); ++ return test_main(argc, argv); ++} + + ## reftable/reftable-tests.h (new) ## +@@ ++#ifndef REFTABLE_TESTS_H ++#define REFTABLE_TESTS_H ++ ++int block_test_main(int argc, const char **argv); ++int merged_test_main(int argc, const char **argv); ++int record_test_main(int argc, const char **argv); ++int refname_test_main(int argc, const char **argv); ++int reftable_test_main(int argc, const char **argv); ++int slice_test_main(int argc, const char **argv); ++int stack_test_main(int argc, const char **argv); ++int tree_test_main(int argc, const char **argv); ++ +#endif ## reftable/reftable.c (new) ## @@ reftable/reftable.h (new) + +#endif - ## reftable/slice.c (new) ## + ## reftable/reftable_test.c (new) ## @@ +/* +Copyright 2020 Google LLC @@ reftable/slice.c (new) +https://developers.google.com/open-source/licenses/bsd +*/ + -+#include "slice.h" ++#include "reftable.h" + +#include "system.h" + -+#include "reftable.h" ++#include "basics.h" ++#include "block.h" ++#include "constants.h" ++#include "reader.h" ++#include "record.h" ++#include "test_framework.h" ++#include "reftable-tests.h" + -+struct slice reftable_empty_slice = SLICE_INIT; ++static const int update_index = 5; + -+void slice_set_string(struct slice *s, const char *str) ++static void test_buffer(void) +{ -+ int l; -+ if (str == NULL) { -+ s->len = 0; -+ return; -+ } -+ assert(s->canary == SLICE_CANARY); ++ struct slice buf = SLICE_INIT; ++ struct reftable_block_source source = { NULL }; ++ struct reftable_block out = { 0 }; ++ int n; ++ byte in[] = "hello"; ++ slice_add(&buf, in, sizeof(in)); ++ block_source_from_slice(&source, &buf); ++ assert(block_source_size(&source) == 6); ++ n = block_source_read_block(&source, &out, 0, sizeof(in)); ++ assert(n == sizeof(in)); ++ assert(!memcmp(in, out.data, n)); ++ reftable_block_done(&out); ++ ++ n = block_source_read_block(&source, &out, 1, 2); ++ assert(n == 2); ++ assert(!memcmp(out.data, "el", 2)); ++ ++ reftable_block_done(&out); ++ block_source_close(&source); ++ slice_release(&buf); ++} ++ ++static void test_default_write_opts(void) ++{ ++ struct reftable_write_options opts = { 0 }; ++ struct slice buf = SLICE_INIT; ++ struct reftable_writer *w = ++ reftable_new_writer(&slice_add_void, &buf, &opts); ++ ++ struct reftable_ref_record rec = { ++ .ref_name = "master", ++ .update_index = 1, ++ }; ++ int err; ++ struct reftable_block_source source = { 0 }; ++ struct reftable_reader **readers = malloc(sizeof(*readers) * 1); ++ uint32_t hash_id; ++ struct reftable_reader *rd = NULL; ++ struct reftable_merged_table *merged = NULL; + -+ l = strlen(str); -+ l++; /* \0 */ -+ slice_resize(s, l); -+ memcpy(s->buf, str, l); -+ s->len = l - 1; -+} ++ reftable_writer_set_limits(w, 1, 1); + -+void slice_init(struct slice *s) -+{ -+ struct slice empty = SLICE_INIT; -+ *s = empty; -+} ++ err = reftable_writer_add_ref(w, &rec); ++ assert_err(err); + -+void slice_resize(struct slice *s, int l) -+{ -+ assert(s->canary == SLICE_CANARY); -+ if (s->cap < l) { -+ int c = s->cap * 2; -+ if (c < l) { -+ c = l; -+ } -+ s->cap = c; -+ s->buf = reftable_realloc(s->buf, s->cap); -+ } -+ s->len = l; -+} ++ err = reftable_writer_close(w); ++ assert_err(err); ++ reftable_writer_free(w); + -+void slice_addstr(struct slice *d, const char *s) -+{ -+ int l1 = d->len; -+ int l2 = strlen(s); -+ assert(d->canary == SLICE_CANARY); ++ block_source_from_slice(&source, &buf); + -+ slice_resize(d, l2 + l1); -+ memcpy(d->buf + l1, s, l2); ++ err = reftable_new_reader(&rd, &source, "filename"); ++ assert_err(err); ++ ++ hash_id = reftable_reader_hash_id(rd); ++ assert(hash_id == SHA1_ID); ++ ++ readers[0] = rd; ++ ++ err = reftable_new_merged_table(&merged, readers, 1, SHA1_ID); ++ assert_err(err); ++ ++ reftable_merged_table_close(merged); ++ reftable_merged_table_free(merged); ++ slice_release(&buf); +} + -+void slice_addbuf(struct slice *s, struct slice a) ++static void write_table(char ***names, struct slice *buf, int N, int block_size, ++ uint32_t hash_id) +{ -+ int end = s->len; -+ assert(s->canary == SLICE_CANARY); -+ slice_resize(s, s->len + a.len); -+ memcpy(s->buf + end, a.buf, a.len); -+} -+ -+void slice_consume(struct slice *s, int n) -+{ -+ assert(s->canary == SLICE_CANARY); -+ s->buf += n; -+ s->len -= n; -+} ++ struct reftable_write_options opts = { ++ .block_size = block_size, ++ .hash_id = hash_id, ++ }; ++ struct reftable_writer *w = ++ reftable_new_writer(&slice_add_void, buf, &opts); ++ struct reftable_ref_record ref = { 0 }; ++ int i = 0, n; ++ struct reftable_log_record log = { 0 }; ++ const struct reftable_stats *stats = NULL; ++ *names = reftable_calloc(sizeof(char *) * (N + 1)); ++ reftable_writer_set_limits(w, update_index, update_index); ++ for (i = 0; i < N; i++) { ++ byte hash[SHA256_SIZE] = { 0 }; ++ char name[100]; ++ int n; + -+byte *slice_detach(struct slice *s) -+{ -+ byte *p = s->buf; -+ assert(s->canary == SLICE_CANARY); -+ s->buf = NULL; -+ s->cap = 0; -+ s->len = 0; -+ return p; -+} ++ set_test_hash(hash, i); + -+void slice_release(struct slice *s) -+{ -+ assert(s->canary == SLICE_CANARY); -+ reftable_free(slice_detach(s)); -+} ++ snprintf(name, sizeof(name), "refs/heads/branch%02d", i); + -+void slice_copy(struct slice *dest, struct slice src) -+{ -+ assert(dest->canary == SLICE_CANARY); -+ assert(src.canary == SLICE_CANARY); -+ slice_resize(dest, src.len); -+ memcpy(dest->buf, src.buf, src.len); -+} ++ ref.ref_name = name; ++ ref.value = hash; ++ ref.update_index = update_index; ++ (*names)[i] = xstrdup(name); + -+/* return the underlying data as char*. len is left unchanged, but -+ a \0 is added at the end. */ -+const char *slice_as_string(struct slice *s) -+{ -+ assert(s->canary == SLICE_CANARY); -+ if (s->cap == s->len) { -+ int l = s->len; -+ slice_resize(s, l + 1); -+ s->len = l; ++ n = reftable_writer_add_ref(w, &ref); ++ assert(n == 0); + } -+ s->buf[s->len] = 0; -+ return (const char *)s->buf; -+} + -+/* return a newly malloced string for this slice */ -+char *slice_to_string(struct slice in) -+{ -+ struct slice s = SLICE_INIT; -+ assert(in.canary == SLICE_CANARY); -+ slice_resize(&s, in.len + 1); -+ s.buf[in.len] = 0; -+ memcpy(s.buf, in.buf, in.len); -+ return (char *)slice_detach(&s); -+} ++ for (i = 0; i < N; i++) { ++ byte hash[SHA256_SIZE] = { 0 }; ++ char name[100]; ++ int n; + -+bool slice_equal(struct slice a, struct slice b) -+{ -+ assert(a.canary == SLICE_CANARY); -+ assert(b.canary == SLICE_CANARY); -+ if (a.len != b.len) -+ return 0; -+ return memcmp(a.buf, b.buf, a.len) == 0; -+} ++ set_test_hash(hash, i); + -+int slice_cmp(struct slice a, struct slice b) -+{ -+ int min = a.len < b.len ? a.len : b.len; -+ int res = memcmp(a.buf, b.buf, min); -+ assert(a.canary == SLICE_CANARY); -+ assert(b.canary == SLICE_CANARY); -+ if (res != 0) -+ return res; -+ if (a.len < b.len) -+ return -1; -+ else if (a.len > b.len) -+ return 1; -+ else -+ return 0; -+} ++ snprintf(name, sizeof(name), "refs/heads/branch%02d", i); + -+int slice_add(struct slice *b, byte *data, size_t sz) -+{ -+ assert(b->canary == SLICE_CANARY); -+ if (b->len + sz > b->cap) { -+ int newcap = 2 * b->cap + 1; -+ if (newcap < b->len + sz) { -+ newcap = (b->len + sz); ++ log.ref_name = name; ++ log.new_hash = hash; ++ log.update_index = update_index; ++ log.message = "message"; ++ ++ n = reftable_writer_add_log(w, &log); ++ assert(n == 0); ++ } ++ ++ n = reftable_writer_close(w); ++ assert(n == 0); ++ ++ stats = writer_stats(w); ++ for (i = 0; i < stats->ref_stats.blocks; i++) { ++ int off = i * opts.block_size; ++ if (off == 0) { ++ off = header_size((hash_id == SHA256_ID) ? 2 : 1); + } -+ b->buf = reftable_realloc(b->buf, newcap); -+ b->cap = newcap; ++ assert(buf->buf[off] == 'r'); + } + -+ memcpy(b->buf + b->len, data, sz); -+ b->len += sz; -+ return sz; ++ assert(stats->log_stats.blocks > 0); ++ reftable_writer_free(w); +} + -+int slice_add_void(void *b, byte *data, size_t sz) ++static void test_log_buffer_size(void) +{ -+ return slice_add((struct slice *)b, data, sz); -+} ++ struct slice buf = SLICE_INIT; ++ struct reftable_write_options opts = { ++ .block_size = 4096, ++ }; ++ int err; ++ struct reftable_log_record log = { ++ .ref_name = "refs/heads/master", ++ .name = "Han-Wen Nienhuys", ++ .email = "hanwen@google.com", ++ .tz_offset = 100, ++ .time = 0x5e430672, ++ .update_index = 0xa, ++ .message = "commit: 9\n", ++ }; ++ struct reftable_writer *w = ++ reftable_new_writer(&slice_add_void, &buf, &opts); + -+static uint64_t slice_size(void *b) -+{ -+ return ((struct slice *)b)->len; -+} ++ /* This tests buffer extension for log compression. Must use a random ++ hash, to ensure that the compressed part is larger than the original. ++ */ ++ byte hash1[SHA1_SIZE], hash2[SHA1_SIZE]; ++ for (int i = 0; i < SHA1_SIZE; i++) { ++ hash1[i] = (byte)(rand() % 256); ++ hash2[i] = (byte)(rand() % 256); ++ } ++ log.old_hash = hash1; ++ log.new_hash = hash2; ++ reftable_writer_set_limits(w, update_index, update_index); ++ err = reftable_writer_add_log(w, &log); ++ assert_err(err); ++ err = reftable_writer_close(w); ++ assert_err(err); ++ reftable_writer_free(w); ++ slice_release(&buf); ++} ++ ++static void test_log_write_read(void) ++{ ++ int N = 2; ++ char **names = reftable_calloc(sizeof(char *) * (N + 1)); ++ int err; ++ struct reftable_write_options opts = { ++ .block_size = 256, ++ }; ++ struct reftable_ref_record ref = { 0 }; ++ int i = 0; ++ struct reftable_log_record log = { 0 }; ++ int n; ++ struct reftable_iterator it = { 0 }; ++ struct reftable_reader rd = { 0 }; ++ struct reftable_block_source source = { 0 }; ++ struct slice buf = SLICE_INIT; ++ struct reftable_writer *w = ++ reftable_new_writer(&slice_add_void, &buf, &opts); ++ const struct reftable_stats *stats = NULL; ++ reftable_writer_set_limits(w, 0, N); ++ for (i = 0; i < N; i++) { ++ char name[256]; ++ struct reftable_ref_record ref = { 0 }; ++ snprintf(name, sizeof(name), "b%02d%0*d", i, 130, 7); ++ names[i] = xstrdup(name); ++ puts(name); ++ ref.ref_name = name; ++ ref.update_index = i; + -+static void slice_return_block(void *b, struct reftable_block *dest) -+{ -+ memset(dest->data, 0xff, dest->len); -+ reftable_free(dest->data); -+} ++ err = reftable_writer_add_ref(w, &ref); ++ assert_err(err); ++ } ++ for (i = 0; i < N; i++) { ++ byte hash1[SHA1_SIZE], hash2[SHA1_SIZE]; ++ struct reftable_log_record log = { 0 }; ++ set_test_hash(hash1, i); ++ set_test_hash(hash2, i + 1); + -+static void slice_close(void *b) -+{ -+} ++ log.ref_name = names[i]; ++ log.update_index = i; ++ log.old_hash = hash1; ++ log.new_hash = hash2; + -+static int slice_read_block(void *v, struct reftable_block *dest, uint64_t off, -+ uint32_t size) -+{ -+ struct slice *b = (struct slice *)v; -+ assert(off + size <= b->len); -+ dest->data = reftable_calloc(size); -+ memcpy(dest->data, b->buf + off, size); -+ dest->len = size; -+ return size; -+} ++ err = reftable_writer_add_log(w, &log); ++ assert_err(err); ++ } + -+struct reftable_block_source_vtable slice_vtable = { -+ .size = &slice_size, -+ .read_block = &slice_read_block, -+ .return_block = &slice_return_block, -+ .close = &slice_close, -+}; ++ n = reftable_writer_close(w); ++ assert(n == 0); + -+void block_source_from_slice(struct reftable_block_source *bs, -+ struct slice *buf) -+{ -+ assert(bs->ops == NULL); -+ bs->ops = &slice_vtable; -+ bs->arg = buf; -+} ++ stats = writer_stats(w); ++ assert(stats->log_stats.blocks > 0); ++ reftable_writer_free(w); ++ w = NULL; + -+static void malloc_return_block(void *b, struct reftable_block *dest) -+{ -+ memset(dest->data, 0xff, dest->len); -+ reftable_free(dest->data); -+} ++ block_source_from_slice(&source, &buf); + -+struct reftable_block_source_vtable malloc_vtable = { -+ .return_block = &malloc_return_block, -+}; ++ err = init_reader(&rd, &source, "file.log"); ++ assert_err(err); + -+struct reftable_block_source malloc_block_source_instance = { -+ .ops = &malloc_vtable, -+}; ++ err = reftable_reader_seek_ref(&rd, &it, names[N - 1]); ++ assert_err(err); + -+struct reftable_block_source malloc_block_source(void) -+{ -+ return malloc_block_source_instance; -+} ++ err = reftable_iterator_next_ref(&it, &ref); ++ assert_err(err); + -+int common_prefix_size(struct slice a, struct slice b) -+{ -+ int p = 0; -+ assert(a.canary == SLICE_CANARY); -+ assert(b.canary == SLICE_CANARY); -+ while (p < a.len && p < b.len) { -+ if (a.buf[p] != b.buf[p]) { ++ /* end of iteration. */ ++ err = reftable_iterator_next_ref(&it, &ref); ++ assert(0 < err); ++ ++ reftable_iterator_destroy(&it); ++ reftable_ref_record_clear(&ref); ++ ++ err = reftable_reader_seek_log(&rd, &it, ""); ++ assert_err(err); ++ ++ i = 0; ++ while (true) { ++ int err = reftable_iterator_next_log(&it, &log); ++ if (err > 0) { + break; + } -+ p++; ++ ++ assert_err(err); ++ assert_streq(names[i], log.ref_name); ++ assert(i == log.update_index); ++ i++; ++ reftable_log_record_clear(&log); + } + -+ return p; ++ assert(i == N); ++ reftable_iterator_destroy(&it); ++ ++ /* cleanup. */ ++ slice_release(&buf); ++ free_names(names); ++ reader_close(&rd); +} - - ## reftable/slice.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 -+*/ ++static void test_table_read_write_sequential(void) ++{ ++ char **names; ++ struct slice buf = SLICE_INIT; ++ int N = 50; ++ struct reftable_iterator it = { 0 }; ++ struct reftable_block_source source = { 0 }; ++ struct reftable_reader rd = { 0 }; ++ int err = 0; ++ int j = 0; + -+#ifndef SLICE_H -+#define SLICE_H ++ write_table(&names, &buf, N, 256, SHA1_ID); + -+#include "basics.h" -+#include "reftable.h" ++ block_source_from_slice(&source, &buf); + -+/* -+ provides bounds-checked byte ranges. -+ To use, initialize as "slice x = {0};" -+ */ -+struct slice { -+ int len; -+ int cap; -+ byte *buf; -+ byte canary; -+}; -+#define SLICE_CANARY 0x42 -+#define SLICE_INIT \ -+ { \ -+ 0, 0, NULL, SLICE_CANARY \ ++ err = init_reader(&rd, &source, "file.ref"); ++ assert_err(err); ++ ++ err = reftable_reader_seek_ref(&rd, &it, ""); ++ assert_err(err); ++ ++ while (true) { ++ struct reftable_ref_record ref = { 0 }; ++ int r = reftable_iterator_next_ref(&it, &ref); ++ assert(r >= 0); ++ if (r > 0) { ++ break; ++ } ++ assert(0 == strcmp(names[j], ref.ref_name)); ++ assert(update_index == ref.update_index); ++ ++ j++; ++ reftable_ref_record_clear(&ref); + } -+extern struct slice reftable_empty_slice; ++ assert(j == N); ++ reftable_iterator_destroy(&it); ++ slice_release(&buf); ++ free_names(names); + -+void slice_set_string(struct slice *dest, const char *src); -+void slice_addstr(struct slice *dest, const char *src); ++ reader_close(&rd); ++} + -+/* Deallocate and clear slice */ -+void slice_release(struct slice *slice); ++static void test_table_write_small_table(void) ++{ ++ char **names; ++ struct slice buf = SLICE_INIT; ++ int N = 1; ++ write_table(&names, &buf, N, 4096, SHA1_ID); ++ assert(buf.len < 200); ++ slice_release(&buf); ++ free_names(names); ++} + -+/* Return a malloced string for `src` */ -+char *slice_to_string(struct slice src); ++static void test_table_read_api(void) ++{ ++ char **names; ++ struct slice buf = SLICE_INIT; ++ int N = 50; ++ struct reftable_reader rd = { 0 }; ++ struct reftable_block_source source = { 0 }; ++ int err; ++ int i; ++ struct reftable_log_record log = { 0 }; ++ struct reftable_iterator it = { 0 }; + -+/* Initializes a slice. Accepts a slice with random garbage. */ -+void slice_init(struct slice *slice); ++ write_table(&names, &buf, N, 256, SHA1_ID); + -+/* Ensure that `buf` is \0 terminated. */ -+const char *slice_as_string(struct slice *src); ++ block_source_from_slice(&source, &buf); + -+/* Compare slices */ -+bool slice_equal(struct slice a, struct slice b); ++ err = init_reader(&rd, &source, "file.ref"); ++ assert_err(err); + -+/* Return `buf`, clearing out `s` */ -+byte *slice_detach(struct slice *s); ++ err = reftable_reader_seek_ref(&rd, &it, names[0]); ++ assert_err(err); + -+/* Copy bytes */ -+void slice_copy(struct slice *dest, struct slice src); ++ err = reftable_iterator_next_log(&it, &log); ++ assert(err == REFTABLE_API_ERROR); + -+/* Advance `buf` by `n`, and decrease length. A copy of the slice -+ should be kept for deallocating the slice. */ -+void slice_consume(struct slice *s, int n); ++ slice_release(&buf); ++ for (i = 0; i < N; i++) { ++ reftable_free(names[i]); ++ } ++ reftable_iterator_destroy(&it); ++ reftable_free(names); ++ reader_close(&rd); ++ slice_release(&buf); ++} + -+/* Set length of the slice to `l` */ -+void slice_resize(struct slice *s, int l); ++static void test_table_read_write_seek(bool index, int hash_id) ++{ ++ char **names; ++ struct slice buf = SLICE_INIT; ++ int N = 50; ++ struct reftable_reader rd = { 0 }; ++ struct reftable_block_source source = { 0 }; ++ int err; ++ int i = 0; + -+/* Signed comparison */ -+int slice_cmp(struct slice a, struct slice b); ++ struct reftable_iterator it = { 0 }; ++ struct slice pastLast = SLICE_INIT; ++ struct reftable_ref_record ref = { 0 }; + -+/* Append `data` to the `dest` slice. */ -+int slice_add(struct slice *dest, byte *data, size_t sz); ++ write_table(&names, &buf, N, 256, hash_id); + -+/* Append `add` to `dest. */ -+void slice_addbuf(struct slice *dest, struct slice add); ++ block_source_from_slice(&source, &buf); + -+/* Like slice_add, but suitable for passing to reftable_new_writer -+ */ -+int slice_add_void(void *b, byte *data, size_t sz); ++ err = init_reader(&rd, &source, "file.ref"); ++ assert_err(err); ++ assert(hash_id == reftable_reader_hash_id(&rd)); + -+/* Find the longest shared prefix size of `a` and `b` */ -+int common_prefix_size(struct slice a, struct slice b); ++ if (!index) { ++ rd.ref_offsets.index_offset = 0; ++ } else { ++ assert(rd.ref_offsets.index_offset > 0); ++ } + -+struct reftable_block_source; ++ for (i = 1; i < N; i++) { ++ int err = reftable_reader_seek_ref(&rd, &it, names[i]); ++ assert_err(err); ++ err = reftable_iterator_next_ref(&it, &ref); ++ assert_err(err); ++ assert(0 == strcmp(names[i], ref.ref_name)); ++ assert(i == ref.value[0]); + -+/* Create an in-memory block source for reading reftables */ -+void block_source_from_slice(struct reftable_block_source *bs, -+ struct slice *buf); ++ reftable_ref_record_clear(&ref); ++ reftable_iterator_destroy(&it); ++ } + -+struct reftable_block_source malloc_block_source(void); ++ slice_set_string(&pastLast, names[N - 1]); ++ slice_addstr(&pastLast, "/"); + -+#endif - - ## reftable/stack.c (new) ## -@@ -+/* -+Copyright 2020 Google LLC ++ err = reftable_reader_seek_ref(&rd, &it, slice_as_string(&pastLast)); ++ if (err == 0) { ++ struct reftable_ref_record ref = { 0 }; ++ int err = reftable_iterator_next_ref(&it, &ref); ++ assert(err > 0); ++ } else { ++ assert(err > 0); ++ } + -+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 -+*/ ++ slice_release(&pastLast); ++ reftable_iterator_destroy(&it); + -+#include "stack.h" ++ slice_release(&buf); ++ for (i = 0; i < N; i++) { ++ reftable_free(names[i]); ++ } ++ reftable_free(names); ++ reader_close(&rd); ++} + -+#include "system.h" -+#include "merged.h" -+#include "reader.h" -+#include "refname.h" -+#include "reftable.h" -+#include "writer.h" ++static void test_table_read_write_seek_linear(void) ++{ ++ test_table_read_write_seek(false, SHA1_ID); ++} + -+int reftable_new_stack(struct reftable_stack **dest, const char *dir, -+ struct reftable_write_options config) ++static void test_table_read_write_seek_linear_sha256(void) +{ -+ struct reftable_stack *p = -+ reftable_calloc(sizeof(struct reftable_stack)); -+ struct slice list_file_name = SLICE_INIT; -+ int err = 0; ++ test_table_read_write_seek(false, SHA256_ID); ++} + -+ if (config.hash_id == 0) { -+ config.hash_id = SHA1_ID; -+ } ++static void test_table_read_write_seek_index(void) ++{ ++ test_table_read_write_seek(true, SHA1_ID); ++} + -+ *dest = NULL; ++static void test_table_refs_for(bool indexed) ++{ ++ int N = 50; ++ char **want_names = reftable_calloc(sizeof(char *) * (N + 1)); ++ int want_names_len = 0; ++ byte want_hash[SHA1_SIZE]; + -+ slice_set_string(&list_file_name, dir); -+ slice_addstr(&list_file_name, "/tables.list"); ++ struct reftable_write_options opts = { ++ .block_size = 256, ++ }; ++ struct reftable_ref_record ref = { 0 }; ++ int i = 0; ++ int n; ++ int err; ++ struct reftable_reader rd; ++ struct reftable_block_source source = { 0 }; + -+ p->list_file = slice_to_string(list_file_name); -+ slice_release(&list_file_name); -+ p->reftable_dir = xstrdup(dir); -+ p->config = config; ++ struct slice buf = SLICE_INIT; ++ struct reftable_writer *w = ++ reftable_new_writer(&slice_add_void, &buf, &opts); + -+ err = reftable_stack_reload_maybe_reuse(p, true); -+ if (err < 0) { -+ reftable_stack_destroy(p); -+ } else { -+ *dest = p; -+ } -+ return err; -+} ++ struct reftable_iterator it = { 0 }; ++ int j; + -+static int fd_read_lines(int fd, char ***namesp) -+{ -+ off_t size = lseek(fd, 0, SEEK_END); -+ char *buf = NULL; -+ int err = 0; -+ if (size < 0) { -+ err = REFTABLE_IO_ERROR; -+ goto done; -+ } -+ err = lseek(fd, 0, SEEK_SET); -+ if (err < 0) { -+ err = REFTABLE_IO_ERROR; -+ goto done; ++ set_test_hash(want_hash, 4); ++ ++ for (i = 0; i < N; i++) { ++ byte hash[SHA1_SIZE]; ++ char fill[51] = { 0 }; ++ char name[100]; ++ byte hash1[SHA1_SIZE]; ++ byte hash2[SHA1_SIZE]; ++ struct reftable_ref_record ref = { 0 }; ++ ++ memset(hash, i, sizeof(hash)); ++ memset(fill, 'x', 50); ++ /* Put the variable part in the start */ ++ snprintf(name, sizeof(name), "br%02d%s", i, fill); ++ name[40] = 0; ++ ref.ref_name = name; ++ ++ set_test_hash(hash1, i / 4); ++ set_test_hash(hash2, 3 + i / 4); ++ ref.value = hash1; ++ ref.target_value = hash2; ++ ++ /* 80 bytes / entry, so 3 entries per block. Yields 17 ++ */ ++ /* blocks. */ ++ n = reftable_writer_add_ref(w, &ref); ++ assert(n == 0); ++ ++ if (!memcmp(hash1, want_hash, SHA1_SIZE) || ++ !memcmp(hash2, want_hash, SHA1_SIZE)) { ++ want_names[want_names_len++] = xstrdup(name); ++ } + } + -+ buf = reftable_malloc(size + 1); -+ if (read(fd, buf, size) != size) { -+ err = REFTABLE_IO_ERROR; -+ goto done; ++ n = reftable_writer_close(w); ++ assert(n == 0); ++ ++ reftable_writer_free(w); ++ w = NULL; ++ ++ block_source_from_slice(&source, &buf); ++ ++ err = init_reader(&rd, &source, "file.ref"); ++ assert_err(err); ++ if (!indexed) { ++ rd.obj_offsets.present = 0; + } -+ buf[size] = 0; + -+ parse_names(buf, size, namesp); ++ err = reftable_reader_seek_ref(&rd, &it, ""); ++ assert_err(err); ++ reftable_iterator_destroy(&it); + -+done: -+ reftable_free(buf); -+ return err; -+} ++ err = reftable_reader_refs_for(&rd, &it, want_hash); ++ assert_err(err); + -+int read_lines(const char *filename, char ***namesp) -+{ -+ int fd = open(filename, O_RDONLY, 0644); -+ int err = 0; -+ if (fd < 0) { -+ if (errno == ENOENT) { -+ *namesp = reftable_calloc(sizeof(char *)); -+ return 0; ++ j = 0; ++ while (true) { ++ int err = reftable_iterator_next_ref(&it, &ref); ++ assert(err >= 0); ++ if (err > 0) { ++ break; + } + -+ return REFTABLE_IO_ERROR; ++ assert(j < want_names_len); ++ assert(0 == strcmp(ref.ref_name, want_names[j])); ++ j++; ++ reftable_ref_record_clear(&ref); + } -+ err = fd_read_lines(fd, namesp); -+ close(fd); -+ return err; -+} ++ assert(j == want_names_len); + -+struct reftable_merged_table * -+reftable_stack_merged_table(struct reftable_stack *st) -+{ -+ return st->merged; ++ slice_release(&buf); ++ free_names(want_names); ++ reftable_iterator_destroy(&it); ++ reader_close(&rd); +} + -+/* Close and free the stack */ -+void reftable_stack_destroy(struct reftable_stack *st) ++static void test_table_refs_for_no_index(void) +{ -+ if (st->merged != NULL) { -+ reftable_merged_table_close(st->merged); -+ reftable_merged_table_free(st->merged); -+ st->merged = NULL; -+ } -+ FREE_AND_NULL(st->list_file); -+ FREE_AND_NULL(st->reftable_dir); -+ reftable_free(st); ++ test_table_refs_for(false); +} + -+static struct reftable_reader **stack_copy_readers(struct reftable_stack *st, -+ int cur_len) ++static void test_table_refs_for_obj_index(void) +{ -+ struct reftable_reader **cur = -+ reftable_calloc(sizeof(struct reftable_reader *) * cur_len); -+ int i = 0; -+ for (i = 0; i < cur_len; i++) { -+ cur[i] = st->merged->stack[i]; -+ } -+ return cur; ++ test_table_refs_for(true); +} + -+static int reftable_stack_reload_once(struct reftable_stack *st, char **names, -+ bool reuse_open) ++static void test_table_empty(void) +{ -+ int cur_len = st->merged == NULL ? 0 : st->merged->stack_len; -+ struct reftable_reader **cur = stack_copy_readers(st, cur_len); -+ int err = 0; -+ int names_len = names_length(names); -+ struct reftable_reader **new_tables = -+ reftable_malloc(sizeof(struct reftable_reader *) * names_len); -+ int new_tables_len = 0; -+ struct reftable_merged_table *new_merged = NULL; -+ int i; -+ struct slice table_path = SLICE_INIT; ++ struct reftable_write_options opts = { 0 }; ++ struct slice buf = SLICE_INIT; ++ struct reftable_writer *w = ++ reftable_new_writer(&slice_add_void, &buf, &opts); ++ struct reftable_block_source source = { 0 }; ++ struct reftable_reader *rd = NULL; ++ struct reftable_ref_record rec = { 0 }; ++ struct reftable_iterator it = { 0 }; ++ int err; + -+ while (*names) { -+ struct reftable_reader *rd = NULL; -+ char *name = *names++; ++ reftable_writer_set_limits(w, 1, 1); + -+ /* this is linear; we assume compaction keeps the number of -+ tables under control so this is not quadratic. */ -+ int j = 0; -+ for (j = 0; reuse_open && j < cur_len; j++) { -+ if (cur[j] != NULL && 0 == strcmp(cur[j]->name, name)) { -+ rd = cur[j]; -+ cur[j] = NULL; -+ break; -+ } -+ } ++ err = reftable_writer_close(w); ++ assert(err == REFTABLE_EMPTY_TABLE_ERROR); ++ reftable_writer_free(w); + -+ if (rd == NULL) { -+ struct reftable_block_source src = { 0 }; -+ slice_set_string(&table_path, st->reftable_dir); -+ slice_addstr(&table_path, "/"); -+ slice_addstr(&table_path, name); ++ assert(buf.len == header_size(1) + footer_size(1)); + -+ err = reftable_block_source_from_file( -+ &src, slice_as_string(&table_path)); -+ if (err < 0) -+ goto done; ++ block_source_from_slice(&source, &buf); + -+ err = reftable_new_reader(&rd, &src, name); -+ if (err < 0) -+ goto done; -+ } ++ err = reftable_new_reader(&rd, &source, "filename"); ++ assert_err(err); + -+ new_tables[new_tables_len++] = rd; -+ } ++ err = reftable_reader_seek_ref(rd, &it, ""); ++ assert_err(err); + -+ /* success! */ -+ err = reftable_new_merged_table(&new_merged, new_tables, new_tables_len, -+ st->config.hash_id); -+ if (err < 0) -+ goto done; ++ err = reftable_iterator_next_ref(&it, &rec); ++ assert(err > 0); + -+ new_tables = NULL; -+ new_tables_len = 0; -+ if (st->merged != NULL) { -+ merged_table_clear(st->merged); -+ reftable_merged_table_free(st->merged); -+ } -+ new_merged->suppress_deletions = true; -+ st->merged = new_merged; ++ reftable_iterator_destroy(&it); ++ reftable_reader_free(rd); ++ slice_release(&buf); ++} ++ ++int reftable_test_main(int argc, const char *argv[]) ++{ ++ add_test_case("test_default_write_opts", test_default_write_opts); ++ add_test_case("test_log_write_read", test_log_write_read); ++ add_test_case("test_table_read_write_seek_linear_sha256", ++ &test_table_read_write_seek_linear_sha256); ++ add_test_case("test_log_buffer_size", test_log_buffer_size); ++ add_test_case("test_table_write_small_table", ++ &test_table_write_small_table); ++ add_test_case("test_buffer", &test_buffer); ++ add_test_case("test_table_read_api", &test_table_read_api); ++ add_test_case("test_table_read_write_sequential", ++ &test_table_read_write_sequential); ++ add_test_case("test_table_read_write_seek_linear", ++ &test_table_read_write_seek_linear); ++ add_test_case("test_table_read_write_seek_index", ++ &test_table_read_write_seek_index); ++ add_test_case("test_table_read_write_refs_for_no_index", ++ &test_table_refs_for_no_index); ++ add_test_case("test_table_read_write_refs_for_obj_index", ++ &test_table_refs_for_obj_index); ++ add_test_case("test_table_empty", &test_table_empty); ++ return test_main(argc, argv); ++} + + ## reftable/slice.c (new) ## +@@ ++/* ++Copyright 2020 Google LLC + -+ for (i = 0; i < cur_len; i++) { -+ if (cur[i] != NULL) { -+ reader_close(cur[i]); -+ reftable_reader_free(cur[i]); -+ } -+ } ++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 ++*/ + -+done: -+ slice_release(&table_path); -+ for (i = 0; i < new_tables_len; i++) { -+ reader_close(new_tables[i]); -+ reftable_reader_free(new_tables[i]); -+ } -+ reftable_free(new_tables); -+ reftable_free(cur); -+ return err; -+} ++#include "slice.h" + -+/* return negative if a before b. */ -+static int tv_cmp(struct timeval *a, struct timeval *b) ++#include "system.h" ++ ++#include "reftable.h" ++ ++struct slice reftable_empty_slice = SLICE_INIT; ++ ++void slice_set_string(struct slice *s, const char *str) +{ -+ time_t diff = a->tv_sec - b->tv_sec; -+ int udiff = a->tv_usec - b->tv_usec; ++ int l; ++ if (str == NULL) { ++ s->len = 0; ++ return; ++ } ++ assert(s->canary == SLICE_CANARY); + -+ if (diff != 0) -+ return diff; ++ l = strlen(str); ++ l++; /* \0 */ ++ slice_resize(s, l); ++ memcpy(s->buf, str, l); ++ s->len = l - 1; ++} + -+ return udiff; ++void slice_init(struct slice *s) ++{ ++ struct slice empty = SLICE_INIT; ++ *s = empty; +} + -+int reftable_stack_reload_maybe_reuse(struct reftable_stack *st, -+ bool reuse_open) ++void slice_resize(struct slice *s, int l) +{ -+ struct timeval deadline = { 0 }; ++ assert(s->canary == SLICE_CANARY); ++ if (s->cap < l) { ++ int c = s->cap * 2; ++ if (c < l) { ++ c = l; ++ } ++ s->cap = c; ++ s->buf = reftable_realloc(s->buf, s->cap); ++ } ++ s->len = l; ++} ++ ++void slice_addstr(struct slice *d, const char *s) ++{ ++ int l1 = d->len; ++ int l2 = strlen(s); ++ assert(d->canary == SLICE_CANARY); ++ ++ slice_resize(d, l2 + l1); ++ memcpy(d->buf + l1, s, l2); ++} ++ ++void slice_addbuf(struct slice *s, struct slice *a) ++{ ++ int end = s->len; ++ assert(s->canary == SLICE_CANARY); ++ slice_resize(s, s->len + a->len); ++ memcpy(s->buf + end, a->buf, a->len); ++} ++ ++void slice_consume(struct slice *s, int n) ++{ ++ assert(s->canary == SLICE_CANARY); ++ s->buf += n; ++ s->len -= n; ++} ++ ++byte *slice_detach(struct slice *s) ++{ ++ byte *p = s->buf; ++ assert(s->canary == SLICE_CANARY); ++ s->buf = NULL; ++ s->cap = 0; ++ s->len = 0; ++ return p; ++} ++ ++void slice_release(struct slice *s) ++{ ++ assert(s->canary == SLICE_CANARY); ++ reftable_free(slice_detach(s)); ++} ++ ++void slice_copy(struct slice *dest, struct slice *src) ++{ ++ assert(dest->canary == SLICE_CANARY); ++ assert(src->canary == SLICE_CANARY); ++ slice_resize(dest, src->len); ++ memcpy(dest->buf, src->buf, src->len); ++} ++ ++/* return the underlying data as char*. len is left unchanged, but ++ a \0 is added at the end. */ ++const char *slice_as_string(struct slice *s) ++{ ++ assert(s->canary == SLICE_CANARY); ++ if (s->cap == s->len) { ++ int l = s->len; ++ slice_resize(s, l + 1); ++ s->len = l; ++ } ++ s->buf[s->len] = 0; ++ return (const char *)s->buf; ++} ++ ++/* return a newly malloced string for this slice */ ++char *slice_to_string(struct slice *in) ++{ ++ struct slice s = SLICE_INIT; ++ assert(in->canary == SLICE_CANARY); ++ slice_resize(&s, in->len + 1); ++ s.buf[in->len] = 0; ++ memcpy(s.buf, in->buf, in->len); ++ return (char *)slice_detach(&s); ++} ++ ++bool slice_equal(struct slice *a, struct slice *b) ++{ ++ return slice_cmp(a, b) == 0; ++} ++ ++int slice_cmp(const struct slice *a, const struct slice *b) ++{ ++ int min = a->len < b->len ? a->len : b->len; ++ int res = memcmp(a->buf, b->buf, min); ++ assert(a->canary == SLICE_CANARY); ++ assert(b->canary == SLICE_CANARY); ++ if (res != 0) ++ return res; ++ if (a->len < b->len) ++ return -1; ++ else if (a->len > b->len) ++ return 1; ++ else ++ return 0; ++} ++ ++int slice_add(struct slice *b, byte *data, size_t sz) ++{ ++ assert(b->canary == SLICE_CANARY); ++ if (b->len + sz > b->cap) { ++ int newcap = 2 * b->cap + 1; ++ if (newcap < b->len + sz) { ++ newcap = (b->len + sz); ++ } ++ b->buf = reftable_realloc(b->buf, newcap); ++ b->cap = newcap; ++ } ++ ++ memcpy(b->buf + b->len, data, sz); ++ b->len += sz; ++ return sz; ++} ++ ++int slice_add_void(void *b, byte *data, size_t sz) ++{ ++ return slice_add((struct slice *)b, data, sz); ++} ++ ++static uint64_t slice_size(void *b) ++{ ++ return ((struct slice *)b)->len; ++} ++ ++static void slice_return_block(void *b, struct reftable_block *dest) ++{ ++ memset(dest->data, 0xff, dest->len); ++ reftable_free(dest->data); ++} ++ ++static void slice_close(void *b) ++{ ++} ++ ++static int slice_read_block(void *v, struct reftable_block *dest, uint64_t off, ++ uint32_t size) ++{ ++ struct slice *b = (struct slice *)v; ++ assert(off + size <= b->len); ++ dest->data = reftable_calloc(size); ++ memcpy(dest->data, b->buf + off, size); ++ dest->len = size; ++ return size; ++} ++ ++struct reftable_block_source_vtable slice_vtable = { ++ .size = &slice_size, ++ .read_block = &slice_read_block, ++ .return_block = &slice_return_block, ++ .close = &slice_close, ++}; ++ ++void block_source_from_slice(struct reftable_block_source *bs, ++ struct slice *buf) ++{ ++ assert(bs->ops == NULL); ++ bs->ops = &slice_vtable; ++ bs->arg = buf; ++} ++ ++static void malloc_return_block(void *b, struct reftable_block *dest) ++{ ++ memset(dest->data, 0xff, dest->len); ++ reftable_free(dest->data); ++} ++ ++struct reftable_block_source_vtable malloc_vtable = { ++ .return_block = &malloc_return_block, ++}; ++ ++struct reftable_block_source malloc_block_source_instance = { ++ .ops = &malloc_vtable, ++}; ++ ++struct reftable_block_source malloc_block_source(void) ++{ ++ return malloc_block_source_instance; ++} ++ ++int common_prefix_size(struct slice *a, struct slice *b) ++{ ++ int p = 0; ++ assert(a->canary == SLICE_CANARY); ++ assert(b->canary == SLICE_CANARY); ++ while (p < a->len && p < b->len) { ++ if (a->buf[p] != b->buf[p]) { ++ break; ++ } ++ p++; ++ } ++ ++ return p; ++} + + ## reftable/slice.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 SLICE_H ++#define SLICE_H ++ ++#include "basics.h" ++#include "reftable.h" ++ ++/* ++ provides bounds-checked byte ranges. ++ To use, initialize as "slice x = {0};" ++ */ ++struct slice { ++ int len; ++ int cap; ++ byte *buf; ++ byte canary; ++}; ++#define SLICE_CANARY 0x42 ++#define SLICE_INIT \ ++ { \ ++ 0, 0, NULL, SLICE_CANARY \ ++ } ++extern struct slice reftable_empty_slice; ++ ++void slice_set_string(struct slice *dest, const char *src); ++void slice_addstr(struct slice *dest, const char *src); ++ ++/* Deallocate and clear slice */ ++void slice_release(struct slice *slice); ++ ++/* Return a malloced string for `src` */ ++char *slice_to_string(struct slice *src); ++ ++/* Initializes a slice. Accepts a slice with random garbage. */ ++void slice_init(struct slice *slice); ++ ++/* Ensure that `buf` is \0 terminated. */ ++const char *slice_as_string(struct slice *src); ++ ++/* Compare slices */ ++bool slice_equal(struct slice *a, struct slice *b); ++ ++/* Return `buf`, clearing out `s` */ ++byte *slice_detach(struct slice *s); ++ ++/* Copy bytes */ ++void slice_copy(struct slice *dest, struct slice *src); ++ ++/* Advance `buf` by `n`, and decrease length. A copy of the slice ++ should be kept for deallocating the slice. */ ++void slice_consume(struct slice *s, int n); ++ ++/* Set length of the slice to `l` */ ++void slice_resize(struct slice *s, int l); ++ ++/* Signed comparison */ ++int slice_cmp(const struct slice *a, const struct slice *b); ++ ++/* Append `data` to the `dest` slice. */ ++int slice_add(struct slice *dest, byte *data, size_t sz); ++ ++/* Append `add` to `dest. */ ++void slice_addbuf(struct slice *dest, struct slice *add); ++ ++/* Like slice_add, but suitable for passing to reftable_new_writer ++ */ ++int slice_add_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); ++ ++struct reftable_block_source; ++ ++/* Create an in-memory block source for reading reftables */ ++void block_source_from_slice(struct reftable_block_source *bs, ++ struct slice *buf); ++ ++struct reftable_block_source malloc_block_source(void); ++ ++#endif + + ## reftable/slice_test.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 "slice.h" ++ ++#include "system.h" ++ ++#include "basics.h" ++#include "record.h" ++#include "reftable.h" ++#include "test_framework.h" ++#include "reftable-tests.h" ++ ++static void test_slice(void) ++{ ++ struct slice s = SLICE_INIT; ++ struct slice t = SLICE_INIT; ++ ++ slice_set_string(&s, "abc"); ++ assert(0 == strcmp("abc", slice_as_string(&s))); ++ ++ slice_set_string(&t, "pqr"); ++ ++ slice_addbuf(&s, &t); ++ assert(0 == strcmp("abcpqr", slice_as_string(&s))); ++ ++ slice_release(&s); ++ slice_release(&t); ++} ++ ++int slice_test_main(int argc, const char *argv[]) ++{ ++ add_test_case("test_slice", &test_slice); ++ return test_main(argc, argv); ++} + + ## reftable/stack.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 "stack.h" ++ ++#include "system.h" ++#include "merged.h" ++#include "reader.h" ++#include "refname.h" ++#include "reftable.h" ++#include "writer.h" ++ ++int reftable_new_stack(struct reftable_stack **dest, const char *dir, ++ struct reftable_write_options config) ++{ ++ struct reftable_stack *p = ++ reftable_calloc(sizeof(struct reftable_stack)); ++ struct slice list_file_name = SLICE_INIT; ++ int err = 0; ++ ++ if (config.hash_id == 0) { ++ config.hash_id = SHA1_ID; ++ } ++ ++ *dest = NULL; ++ ++ slice_set_string(&list_file_name, dir); ++ slice_addstr(&list_file_name, "/tables.list"); ++ ++ p->list_file = slice_to_string(&list_file_name); ++ slice_release(&list_file_name); ++ p->reftable_dir = xstrdup(dir); ++ p->config = config; ++ ++ err = reftable_stack_reload_maybe_reuse(p, true); ++ if (err < 0) { ++ reftable_stack_destroy(p); ++ } else { ++ *dest = p; ++ } ++ return err; ++} ++ ++static int fd_read_lines(int fd, char ***namesp) ++{ ++ off_t size = lseek(fd, 0, SEEK_END); ++ char *buf = NULL; ++ int err = 0; ++ if (size < 0) { ++ err = REFTABLE_IO_ERROR; ++ goto done; ++ } ++ err = lseek(fd, 0, SEEK_SET); ++ if (err < 0) { ++ err = REFTABLE_IO_ERROR; ++ goto done; ++ } ++ ++ buf = reftable_malloc(size + 1); ++ if (read(fd, buf, size) != size) { ++ err = REFTABLE_IO_ERROR; ++ goto done; ++ } ++ buf[size] = 0; ++ ++ parse_names(buf, size, namesp); ++ ++done: ++ reftable_free(buf); ++ return err; ++} ++ ++int read_lines(const char *filename, char ***namesp) ++{ ++ int fd = open(filename, O_RDONLY, 0644); ++ int err = 0; ++ if (fd < 0) { ++ if (errno == ENOENT) { ++ *namesp = reftable_calloc(sizeof(char *)); ++ return 0; ++ } ++ ++ return REFTABLE_IO_ERROR; ++ } ++ err = fd_read_lines(fd, namesp); ++ close(fd); ++ return err; ++} ++ ++struct reftable_merged_table * ++reftable_stack_merged_table(struct reftable_stack *st) ++{ ++ return st->merged; ++} ++ ++/* Close and free the stack */ ++void reftable_stack_destroy(struct reftable_stack *st) ++{ ++ if (st->merged != NULL) { ++ reftable_merged_table_close(st->merged); ++ reftable_merged_table_free(st->merged); ++ st->merged = NULL; ++ } ++ FREE_AND_NULL(st->list_file); ++ FREE_AND_NULL(st->reftable_dir); ++ reftable_free(st); ++} ++ ++static struct reftable_reader **stack_copy_readers(struct reftable_stack *st, ++ int cur_len) ++{ ++ struct reftable_reader **cur = ++ reftable_calloc(sizeof(struct reftable_reader *) * cur_len); ++ int i = 0; ++ for (i = 0; i < cur_len; i++) { ++ cur[i] = st->merged->stack[i]; ++ } ++ return cur; ++} ++ ++static int reftable_stack_reload_once(struct reftable_stack *st, char **names, ++ bool reuse_open) ++{ ++ int cur_len = st->merged == NULL ? 0 : st->merged->stack_len; ++ struct reftable_reader **cur = stack_copy_readers(st, cur_len); ++ int err = 0; ++ int names_len = names_length(names); ++ struct reftable_reader **new_tables = ++ reftable_malloc(sizeof(struct reftable_reader *) * names_len); ++ int new_tables_len = 0; ++ struct reftable_merged_table *new_merged = NULL; ++ int i; ++ struct slice table_path = SLICE_INIT; ++ ++ while (*names) { ++ struct reftable_reader *rd = NULL; ++ char *name = *names++; ++ ++ /* this is linear; we assume compaction keeps the number of ++ tables under control so this is not quadratic. */ ++ int j = 0; ++ for (j = 0; reuse_open && j < cur_len; j++) { ++ if (cur[j] != NULL && 0 == strcmp(cur[j]->name, name)) { ++ rd = cur[j]; ++ cur[j] = NULL; ++ break; ++ } ++ } ++ ++ if (rd == NULL) { ++ struct reftable_block_source src = { 0 }; ++ slice_set_string(&table_path, st->reftable_dir); ++ slice_addstr(&table_path, "/"); ++ slice_addstr(&table_path, name); ++ ++ err = reftable_block_source_from_file( ++ &src, slice_as_string(&table_path)); ++ if (err < 0) ++ goto done; ++ ++ err = reftable_new_reader(&rd, &src, name); ++ if (err < 0) ++ goto done; ++ } ++ ++ new_tables[new_tables_len++] = rd; ++ } ++ ++ /* success! */ ++ err = reftable_new_merged_table(&new_merged, new_tables, new_tables_len, ++ st->config.hash_id); ++ if (err < 0) ++ goto done; ++ ++ new_tables = NULL; ++ new_tables_len = 0; ++ if (st->merged != NULL) { ++ merged_table_clear(st->merged); ++ reftable_merged_table_free(st->merged); ++ } ++ new_merged->suppress_deletions = true; ++ st->merged = new_merged; ++ ++ for (i = 0; i < cur_len; i++) { ++ if (cur[i] != NULL) { ++ reader_close(cur[i]); ++ reftable_reader_free(cur[i]); ++ } ++ } ++ ++done: ++ slice_release(&table_path); ++ for (i = 0; i < new_tables_len; i++) { ++ reader_close(new_tables[i]); ++ reftable_reader_free(new_tables[i]); ++ } ++ reftable_free(new_tables); ++ reftable_free(cur); ++ return err; ++} ++ ++/* return negative if a before b. */ ++static int tv_cmp(struct timeval *a, struct timeval *b) ++{ ++ time_t diff = a->tv_sec - b->tv_sec; ++ int udiff = a->tv_usec - b->tv_usec; ++ ++ if (diff != 0) ++ return diff; ++ ++ return udiff; ++} ++ ++int reftable_stack_reload_maybe_reuse(struct reftable_stack *st, ++ bool reuse_open) ++{ ++ struct timeval deadline = { 0 }; + int err = gettimeofday(&deadline, NULL); + int64_t delay = 0; + int tries = 0; + if (err < 0) -+ return err; ++ return err; ++ ++ deadline.tv_sec += 3; ++ while (true) { ++ char **names = NULL; ++ char **names_after = NULL; ++ struct timeval now = { 0 }; ++ int err = gettimeofday(&now, NULL); ++ int err2 = 0; ++ if (err < 0) { ++ return err; ++ } ++ ++ /* Only look at deadlines after the first few times. This ++ simplifies debugging in GDB */ ++ tries++; ++ if (tries > 3 && tv_cmp(&now, &deadline) >= 0) { ++ break; ++ } ++ ++ err = read_lines(st->list_file, &names); ++ if (err < 0) { ++ free_names(names); ++ return err; ++ } ++ err = reftable_stack_reload_once(st, names, reuse_open); ++ if (err == 0) { ++ free_names(names); ++ break; ++ } ++ if (err != REFTABLE_NOT_EXIST_ERROR) { ++ free_names(names); ++ return err; ++ } ++ ++ /* err == REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent ++ writer. Check if there was one by checking if the name list ++ changed. ++ */ ++ err2 = read_lines(st->list_file, &names_after); ++ if (err2 < 0) { ++ free_names(names); ++ return err2; ++ } ++ ++ if (names_equal(names_after, names)) { ++ free_names(names); ++ free_names(names_after); ++ return err; ++ } ++ free_names(names); ++ free_names(names_after); ++ ++ delay = delay + (delay * rand()) / RAND_MAX + 1; ++ sleep_millisec(delay); ++ } ++ ++ return 0; ++} ++ ++/* -1 = error ++ 0 = up to date ++ 1 = changed. */ ++static int stack_uptodate(struct reftable_stack *st) ++{ ++ char **names = NULL; ++ int err = read_lines(st->list_file, &names); ++ int i = 0; ++ if (err < 0) ++ return err; ++ ++ for (i = 0; i < st->merged->stack_len; i++) { ++ if (names[i] == NULL) { ++ err = 1; ++ goto done; ++ } ++ ++ if (strcmp(st->merged->stack[i]->name, names[i])) { ++ err = 1; ++ goto done; ++ } ++ } ++ ++ if (names[st->merged->stack_len] != NULL) { ++ err = 1; ++ goto done; ++ } ++ ++done: ++ free_names(names); ++ return err; ++} ++ ++int reftable_stack_reload(struct reftable_stack *st) ++{ ++ int err = stack_uptodate(st); ++ if (err > 0) ++ return reftable_stack_reload_maybe_reuse(st, true); ++ return err; ++} ++ ++int reftable_stack_add(struct reftable_stack *st, ++ int (*write)(struct reftable_writer *wr, void *arg), ++ void *arg) ++{ ++ 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. ++ */ ++ reftable_stack_reload(st); ++ } ++ return err; ++ } ++ ++ if (!st->disable_auto_compact) ++ return reftable_stack_auto_compact(st); ++ ++ return 0; ++} ++ ++static void format_name(struct slice *dest, uint64_t min, uint64_t max) ++{ ++ char buf[100]; ++ snprintf(buf, sizeof(buf), "0x%012" PRIx64 "-0x%012" PRIx64, min, max); ++ slice_set_string(dest, buf); ++} ++ ++struct reftable_addition { ++ int lock_file_fd; ++ struct slice lock_file_name; ++ struct reftable_stack *stack; ++ char **names; ++ char **new_tables; ++ int new_tables_len; ++ uint64_t next_update_index; ++}; ++ ++#define REFTABLE_ADDITION_INIT \ ++ { \ ++ .lock_file_name = SLICE_INIT \ ++ } ++ ++static int reftable_stack_init_addition(struct reftable_addition *add, ++ struct reftable_stack *st) ++{ ++ int err = 0; ++ add->stack = st; ++ ++ slice_set_string(&add->lock_file_name, st->list_file); ++ slice_addstr(&add->lock_file_name, ".lock"); ++ ++ add->lock_file_fd = open(slice_as_string(&add->lock_file_name), ++ O_EXCL | O_CREAT | O_WRONLY, 0644); ++ if (add->lock_file_fd < 0) { ++ if (errno == EEXIST) { ++ err = REFTABLE_LOCK_ERROR; ++ } else { ++ err = REFTABLE_IO_ERROR; ++ } ++ goto done; ++ } ++ err = stack_uptodate(st); ++ if (err < 0) ++ goto done; ++ ++ if (err > 1) { ++ err = REFTABLE_LOCK_ERROR; ++ goto done; ++ } ++ ++ add->next_update_index = reftable_stack_next_update_index(st); ++done: ++ if (err) { ++ reftable_addition_close(add); ++ } ++ return err; ++} ++ ++void reftable_addition_close(struct reftable_addition *add) ++{ ++ int i = 0; ++ struct slice nm = SLICE_INIT; ++ for (i = 0; i < add->new_tables_len; i++) { ++ slice_set_string(&nm, add->stack->list_file); ++ slice_addstr(&nm, "/"); ++ slice_addstr(&nm, add->new_tables[i]); ++ unlink(slice_as_string(&nm)); ++ reftable_free(add->new_tables[i]); ++ add->new_tables[i] = NULL; ++ } ++ reftable_free(add->new_tables); ++ add->new_tables = NULL; ++ add->new_tables_len = 0; ++ ++ if (add->lock_file_fd > 0) { ++ close(add->lock_file_fd); ++ add->lock_file_fd = 0; ++ } ++ if (add->lock_file_name.len > 0) { ++ unlink(slice_as_string(&add->lock_file_name)); ++ slice_release(&add->lock_file_name); ++ } ++ ++ free_names(add->names); ++ add->names = NULL; ++ slice_release(&nm); ++} ++ ++void reftable_addition_destroy(struct reftable_addition *add) ++{ ++ if (add == NULL) { ++ return; ++ } ++ reftable_addition_close(add); ++ reftable_free(add); ++} ++ ++int reftable_addition_commit(struct reftable_addition *add) ++{ ++ struct slice table_list = SLICE_INIT; ++ int i = 0; ++ int err = 0; ++ if (add->new_tables_len == 0) ++ goto done; ++ ++ for (i = 0; i < add->stack->merged->stack_len; i++) { ++ slice_addstr(&table_list, add->stack->merged->stack[i]->name); ++ slice_addstr(&table_list, "\n"); ++ } ++ for (i = 0; i < add->new_tables_len; i++) { ++ slice_addstr(&table_list, add->new_tables[i]); ++ slice_addstr(&table_list, "\n"); ++ } ++ ++ err = write(add->lock_file_fd, table_list.buf, table_list.len); ++ slice_release(&table_list); ++ if (err < 0) { ++ err = REFTABLE_IO_ERROR; ++ goto done; ++ } ++ ++ err = close(add->lock_file_fd); ++ add->lock_file_fd = 0; ++ if (err < 0) { ++ err = REFTABLE_IO_ERROR; ++ goto done; ++ } ++ ++ err = rename(slice_as_string(&add->lock_file_name), ++ add->stack->list_file); ++ if (err < 0) { ++ err = REFTABLE_IO_ERROR; ++ goto done; ++ } ++ ++ err = reftable_stack_reload(add->stack); ++ ++done: ++ reftable_addition_close(add); ++ return err; ++} ++ ++int reftable_stack_new_addition(struct reftable_addition **dest, ++ struct reftable_stack *st) ++{ ++ int err = 0; ++ struct reftable_addition empty = REFTABLE_ADDITION_INIT; ++ *dest = reftable_calloc(sizeof(**dest)); ++ **dest = empty; ++ err = reftable_stack_init_addition(*dest, st); ++ if (err) { ++ reftable_free(*dest); ++ *dest = NULL; ++ } ++ return err; ++} ++ ++int stack_try_add(struct reftable_stack *st, ++ int (*write_table)(struct reftable_writer *wr, void *arg), ++ void *arg) ++{ ++ struct reftable_addition add = REFTABLE_ADDITION_INIT; ++ int err = reftable_stack_init_addition(&add, st); ++ if (err < 0) ++ goto done; ++ if (err > 0) { ++ err = REFTABLE_LOCK_ERROR; ++ goto done; ++ } ++ ++ err = reftable_addition_add(&add, write_table, arg); ++ if (err < 0) ++ goto done; ++ ++ err = reftable_addition_commit(&add); ++done: ++ reftable_addition_close(&add); ++ return err; ++} ++ ++int reftable_addition_add(struct reftable_addition *add, ++ int (*write_table)(struct reftable_writer *wr, ++ void *arg), ++ void *arg) ++{ ++ struct slice temp_tab_file_name = SLICE_INIT; ++ struct slice tab_file_name = SLICE_INIT; ++ struct slice next_name = SLICE_INIT; ++ struct reftable_writer *wr = NULL; ++ int err = 0; ++ int tab_fd = 0; ++ ++ slice_resize(&next_name, 0); ++ format_name(&next_name, add->next_update_index, add->next_update_index); ++ ++ slice_set_string(&temp_tab_file_name, add->stack->reftable_dir); ++ slice_addstr(&temp_tab_file_name, "/"); ++ slice_addbuf(&temp_tab_file_name, &next_name); ++ slice_addstr(&temp_tab_file_name, ".temp.XXXXXX"); ++ ++ tab_fd = mkstemp((char *)slice_as_string(&temp_tab_file_name)); ++ if (tab_fd < 0) { ++ err = REFTABLE_IO_ERROR; ++ goto done; ++ } ++ ++ wr = reftable_new_writer(reftable_fd_write, &tab_fd, ++ &add->stack->config); ++ err = write_table(wr, arg); ++ if (err < 0) ++ goto done; ++ ++ err = reftable_writer_close(wr); ++ if (err == REFTABLE_EMPTY_TABLE_ERROR) { ++ err = 0; ++ goto done; ++ } ++ if (err < 0) ++ goto done; ++ ++ err = close(tab_fd); ++ tab_fd = 0; ++ if (err < 0) { ++ err = REFTABLE_IO_ERROR; ++ goto done; ++ } ++ ++ err = stack_check_addition(add->stack, ++ slice_as_string(&temp_tab_file_name)); ++ if (err < 0) ++ goto done; ++ ++ if (wr->min_update_index < add->next_update_index) { ++ err = REFTABLE_API_ERROR; ++ goto done; ++ } ++ ++ format_name(&next_name, wr->min_update_index, wr->max_update_index); ++ slice_addstr(&next_name, ".ref"); ++ ++ slice_set_string(&tab_file_name, add->stack->reftable_dir); ++ slice_addstr(&tab_file_name, "/"); ++ slice_addbuf(&tab_file_name, &next_name); ++ ++ /* TODO: should check destination out of paranoia */ ++ err = rename(slice_as_string(&temp_tab_file_name), ++ slice_as_string(&tab_file_name)); ++ if (err < 0) { ++ err = REFTABLE_IO_ERROR; ++ goto done; ++ } ++ ++ add->new_tables = reftable_realloc(add->new_tables, ++ sizeof(*add->new_tables) * ++ (add->new_tables_len + 1)); ++ add->new_tables[add->new_tables_len] = slice_to_string(&next_name); ++ add->new_tables_len++; ++done: ++ if (tab_fd > 0) { ++ close(tab_fd); ++ tab_fd = 0; ++ } ++ if (temp_tab_file_name.len > 0) { ++ unlink(slice_as_string(&temp_tab_file_name)); ++ } ++ ++ slice_release(&temp_tab_file_name); ++ slice_release(&tab_file_name); ++ slice_release(&next_name); ++ reftable_writer_free(wr); ++ return err; ++} ++ ++uint64_t reftable_stack_next_update_index(struct reftable_stack *st) ++{ ++ int sz = st->merged->stack_len; ++ if (sz > 0) ++ return reftable_reader_max_update_index( ++ st->merged->stack[sz - 1]) + ++ 1; ++ return 1; ++} ++ ++static int stack_compact_locked(struct reftable_stack *st, int first, int last, ++ struct slice *temp_tab, ++ struct reftable_log_expiry_config *config) ++{ ++ struct slice next_name = SLICE_INIT; ++ int tab_fd = -1; ++ struct reftable_writer *wr = NULL; ++ int err = 0; ++ ++ format_name(&next_name, ++ reftable_reader_min_update_index(st->merged->stack[first]), ++ reftable_reader_max_update_index(st->merged->stack[first])); ++ ++ slice_set_string(temp_tab, st->reftable_dir); ++ slice_addstr(temp_tab, "/"); ++ slice_addbuf(temp_tab, &next_name); ++ slice_addstr(temp_tab, ".temp.XXXXXX"); ++ ++ tab_fd = mkstemp((char *)slice_as_string(temp_tab)); ++ wr = reftable_new_writer(reftable_fd_write, &tab_fd, &st->config); ++ ++ err = stack_write_compact(st, wr, first, last, config); ++ if (err < 0) ++ goto done; ++ err = reftable_writer_close(wr); ++ if (err < 0) ++ goto done; ++ ++ err = close(tab_fd); ++ tab_fd = 0; ++ ++done: ++ reftable_writer_free(wr); ++ if (tab_fd > 0) { ++ close(tab_fd); ++ tab_fd = 0; ++ } ++ if (err != 0 && temp_tab->len > 0) { ++ unlink(slice_as_string(temp_tab)); ++ slice_release(temp_tab); ++ } ++ slice_release(&next_name); ++ return err; ++} ++ ++int stack_write_compact(struct reftable_stack *st, struct reftable_writer *wr, ++ int first, int last, ++ struct reftable_log_expiry_config *config) ++{ ++ int subtabs_len = last - first + 1; ++ struct reftable_reader **subtabs = reftable_calloc( ++ sizeof(struct reftable_reader *) * (last - first + 1)); ++ struct reftable_merged_table *mt = NULL; ++ int err = 0; ++ struct reftable_iterator it = { 0 }; ++ 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]; ++ subtabs[j++] = t; ++ st->stats.bytes += t->size; ++ } ++ reftable_writer_set_limits(wr, ++ st->merged->stack[first]->min_update_index, ++ st->merged->stack[last]->max_update_index); ++ ++ err = reftable_new_merged_table(&mt, subtabs, subtabs_len, ++ st->config.hash_id); ++ if (err < 0) { ++ reftable_free(subtabs); ++ goto done; ++ } ++ ++ err = reftable_merged_table_seek_ref(mt, &it, ""); ++ if (err < 0) ++ goto done; + -+ deadline.tv_sec += 3; + while (true) { -+ char **names = NULL; -+ char **names_after = NULL; -+ struct timeval now = { 0 }; -+ int err = gettimeofday(&now, NULL); -+ int err2 = 0; ++ err = reftable_iterator_next_ref(&it, &ref); ++ if (err > 0) { ++ err = 0; ++ break; ++ } + if (err < 0) { -+ return err; ++ break; ++ } ++ if (first == 0 && reftable_ref_record_is_deletion(&ref)) { ++ continue; + } + -+ /* Only look at deadlines after the first few times. This -+ simplifies debugging in GDB */ -+ tries++; -+ if (tries > 3 && tv_cmp(&now, &deadline) >= 0) { ++ err = reftable_writer_add_ref(wr, &ref); ++ if (err < 0) { + break; + } ++ entries++; ++ } ++ reftable_iterator_destroy(&it); + -+ err = read_lines(st->list_file, &names); -+ if (err < 0) { -+ free_names(names); -+ return err; ++ err = reftable_merged_table_seek_log(mt, &it, ""); ++ if (err < 0) ++ goto done; ++ ++ while (true) { ++ err = reftable_iterator_next_log(&it, &log); ++ if (err > 0) { ++ err = 0; ++ break; + } -+ err = reftable_stack_reload_once(st, names, reuse_open); -+ if (err == 0) { -+ free_names(names); ++ if (err < 0) { + break; + } -+ if (err != REFTABLE_NOT_EXIST_ERROR) { -+ free_names(names); -+ return err; ++ if (first == 0 && reftable_log_record_is_deletion(&log)) { ++ continue; + } + -+ /* err == REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent -+ writer. Check if there was one by checking if the name list -+ changed. -+ */ -+ err2 = read_lines(st->list_file, &names_after); -+ if (err2 < 0) { -+ free_names(names); -+ return err2; ++ if (config != NULL && config->time > 0 && ++ log.time < config->time) { ++ continue; + } + -+ if (names_equal(names_after, names)) { -+ free_names(names); -+ free_names(names_after); -+ return err; ++ if (config != NULL && config->min_update_index > 0 && ++ log.update_index < config->min_update_index) { ++ continue; + } -+ free_names(names); -+ free_names(names_after); + -+ delay = delay + (delay * rand()) / RAND_MAX + 1; -+ sleep_millisec(delay); ++ err = reftable_writer_add_log(wr, &log); ++ if (err < 0) { ++ break; ++ } ++ entries++; ++ } ++ ++done: ++ reftable_iterator_destroy(&it); ++ if (mt != NULL) { ++ merged_table_clear(mt); ++ reftable_merged_table_free(mt); ++ } ++ reftable_ref_record_clear(&ref); ++ reftable_log_record_clear(&log); ++ st->stats.entries_written += entries; ++ return err; ++} ++ ++/* < 0: error. 0 == OK, > 0 attempt failed; could retry. */ ++static int stack_compact_range(struct reftable_stack *st, int first, int last, ++ struct reftable_log_expiry_config *expiry) ++{ ++ struct slice temp_tab_file_name = SLICE_INIT; ++ struct slice new_table_name = SLICE_INIT; ++ struct slice lock_file_name = SLICE_INIT; ++ struct slice ref_list_contents = SLICE_INIT; ++ struct slice new_table_path = SLICE_INIT; ++ int err = 0; ++ bool have_lock = false; ++ int lock_file_fd = 0; ++ int compact_count = last - first + 1; ++ char **listp = NULL; ++ char **delete_on_success = ++ reftable_calloc(sizeof(char *) * (compact_count + 1)); ++ char **subtable_locks = ++ reftable_calloc(sizeof(char *) * (compact_count + 1)); ++ int i = 0; ++ int j = 0; ++ bool is_empty_table = false; ++ ++ if (first > last || (expiry == NULL && first == last)) { ++ err = 0; ++ goto done; ++ } ++ ++ st->stats.attempts++; ++ ++ slice_set_string(&lock_file_name, st->list_file); ++ slice_addstr(&lock_file_name, ".lock"); ++ ++ lock_file_fd = open(slice_as_string(&lock_file_name), ++ O_EXCL | O_CREAT | O_WRONLY, 0644); ++ if (lock_file_fd < 0) { ++ if (errno == EEXIST) { ++ err = 1; ++ } else { ++ err = REFTABLE_IO_ERROR; ++ } ++ goto done; ++ } ++ /* 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) ++ goto done; ++ ++ for (i = first, j = 0; i <= last; i++) { ++ struct slice subtab_file_name = SLICE_INIT; ++ struct slice subtab_lock = SLICE_INIT; ++ int sublock_file_fd = -1; ++ ++ slice_set_string(&subtab_file_name, st->reftable_dir); ++ slice_addstr(&subtab_file_name, "/"); ++ slice_addstr(&subtab_file_name, ++ reader_name(st->merged->stack[i])); ++ ++ slice_copy(&subtab_lock, &subtab_file_name); ++ slice_addstr(&subtab_lock, ".lock"); ++ ++ sublock_file_fd = open(slice_as_string(&subtab_lock), ++ O_EXCL | O_CREAT | O_WRONLY, 0644); ++ if (sublock_file_fd > 0) { ++ close(sublock_file_fd); ++ } else if (sublock_file_fd < 0) { ++ if (errno == EEXIST) { ++ err = 1; ++ } else { ++ err = REFTABLE_IO_ERROR; ++ } ++ } ++ ++ subtable_locks[j] = (char *)slice_as_string(&subtab_lock); ++ delete_on_success[j] = ++ (char *)slice_as_string(&subtab_file_name); ++ j++; ++ ++ if (err != 0) ++ goto done; + } + -+ return 0; -+} ++ err = unlink(slice_as_string(&lock_file_name)); ++ if (err < 0) ++ goto done; ++ have_lock = false; + -+/* -1 = error -+ 0 = up to date -+ 1 = changed. */ -+static int stack_uptodate(struct reftable_stack *st) -+{ -+ char **names = NULL; -+ int err = read_lines(st->list_file, &names); -+ int i = 0; ++ err = stack_compact_locked(st, first, last, &temp_tab_file_name, ++ expiry); ++ /* Compaction + tombstones can create an empty table out of non-empty ++ * tables. */ ++ is_empty_table = (err == REFTABLE_EMPTY_TABLE_ERROR); ++ if (is_empty_table) { ++ err = 0; ++ } + if (err < 0) -+ return err; ++ goto done; + -+ for (i = 0; i < st->merged->stack_len; i++) { -+ if (names[i] == NULL) { ++ lock_file_fd = open(slice_as_string(&lock_file_name), ++ O_EXCL | O_CREAT | O_WRONLY, 0644); ++ if (lock_file_fd < 0) { ++ if (errno == EEXIST) { + err = 1; -+ goto done; ++ } else { ++ err = REFTABLE_IO_ERROR; + } ++ goto done; ++ } ++ have_lock = true; + -+ if (strcmp(st->merged->stack[i]->name, names[i])) { -+ err = 1; ++ format_name(&new_table_name, st->merged->stack[first]->min_update_index, ++ st->merged->stack[last]->max_update_index); ++ slice_addstr(&new_table_name, ".ref"); ++ ++ slice_set_string(&new_table_path, st->reftable_dir); ++ slice_addstr(&new_table_path, "/"); ++ ++ slice_addbuf(&new_table_path, &new_table_name); ++ ++ if (!is_empty_table) { ++ err = rename(slice_as_string(&temp_tab_file_name), ++ slice_as_string(&new_table_path)); ++ if (err < 0) { ++ err = REFTABLE_IO_ERROR; + goto done; + } + } + -+ if (names[st->merged->stack_len] != NULL) { -+ err = 1; ++ for (i = 0; i < first; i++) { ++ slice_addstr(&ref_list_contents, st->merged->stack[i]->name); ++ slice_addstr(&ref_list_contents, "\n"); ++ } ++ if (!is_empty_table) { ++ slice_addbuf(&ref_list_contents, &new_table_name); ++ slice_addstr(&ref_list_contents, "\n"); ++ } ++ for (i = last + 1; i < st->merged->stack_len; i++) { ++ slice_addstr(&ref_list_contents, st->merged->stack[i]->name); ++ slice_addstr(&ref_list_contents, "\n"); ++ } ++ ++ err = write(lock_file_fd, ref_list_contents.buf, ref_list_contents.len); ++ if (err < 0) { ++ err = REFTABLE_IO_ERROR; ++ unlink(slice_as_string(&new_table_path)); ++ goto done; ++ } ++ err = close(lock_file_fd); ++ lock_file_fd = 0; ++ if (err < 0) { ++ err = REFTABLE_IO_ERROR; ++ unlink(slice_as_string(&new_table_path)); ++ goto done; ++ } ++ ++ err = rename(slice_as_string(&lock_file_name), st->list_file); ++ if (err < 0) { ++ err = REFTABLE_IO_ERROR; ++ unlink(slice_as_string(&new_table_path)); + goto done; + } ++ 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); ++ ++ listp = delete_on_success; ++ while (*listp) { ++ if (strcmp(*listp, slice_as_string(&new_table_path))) { ++ unlink(*listp); ++ } ++ listp++; ++ } + +done: -+ free_names(names); ++ free_names(delete_on_success); ++ ++ listp = subtable_locks; ++ while (*listp) { ++ unlink(*listp); ++ listp++; ++ } ++ free_names(subtable_locks); ++ if (lock_file_fd > 0) { ++ close(lock_file_fd); ++ lock_file_fd = 0; ++ } ++ if (have_lock) { ++ unlink(slice_as_string(&lock_file_name)); ++ } ++ slice_release(&new_table_name); ++ slice_release(&new_table_path); ++ slice_release(&ref_list_contents); ++ slice_release(&temp_tab_file_name); ++ slice_release(&lock_file_name); + return err; +} + -+int reftable_stack_reload(struct reftable_stack *st) ++int reftable_stack_compact_all(struct reftable_stack *st, ++ struct reftable_log_expiry_config *config) +{ -+ int err = stack_uptodate(st); -+ if (err > 0) -+ return reftable_stack_reload_maybe_reuse(st, true); -+ return err; ++ return stack_compact_range(st, 0, st->merged->stack_len - 1, config); +} + -+int reftable_stack_add(struct reftable_stack *st, -+ int (*write)(struct reftable_writer *wr, void *arg), -+ void *arg) ++static int stack_compact_range_stats(struct reftable_stack *st, int first, ++ int last, ++ struct reftable_log_expiry_config *config) +{ -+ 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. -+ */ -+ reftable_stack_reload(st); -+ } -+ return err; ++ int err = stack_compact_range(st, first, last, config); ++ if (err > 0) { ++ st->stats.failures++; + } -+ -+ if (!st->disable_auto_compact) -+ return reftable_stack_auto_compact(st); -+ -+ return 0; ++ return err; +} + -+static void format_name(struct slice *dest, uint64_t min, uint64_t max) ++static int segment_size(struct segment *s) +{ -+ char buf[100]; -+ snprintf(buf, sizeof(buf), "0x%012" PRIx64 "-0x%012" PRIx64, min, max); -+ slice_set_string(dest, buf); ++ return s->end - s->start; +} + -+struct reftable_addition { -+ int lock_file_fd; -+ struct slice lock_file_name; -+ struct reftable_stack *stack; -+ char **names; -+ char **new_tables; -+ int new_tables_len; -+ uint64_t next_update_index; -+}; -+ -+#define REFTABLE_ADDITION_INIT \ -+ { \ -+ .lock_file_name = SLICE_INIT \ ++int fastlog2(uint64_t sz) ++{ ++ int l = 0; ++ if (sz == 0) ++ return 0; ++ for (; sz; sz /= 2) { ++ l++; + } ++ return l - 1; ++} + -+static int reftable_stack_init_addition(struct reftable_addition *add, -+ struct reftable_stack *st) ++struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n) +{ -+ int err = 0; -+ add->stack = st; ++ struct segment *segs = reftable_calloc(sizeof(struct segment) * n); ++ int next = 0; ++ struct segment cur = { 0 }; ++ int i = 0; + -+ slice_set_string(&add->lock_file_name, st->list_file); -+ slice_addstr(&add->lock_file_name, ".lock"); ++ 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) { ++ struct segment fresh = { ++ .start = i, ++ }; + -+ add->lock_file_fd = open(slice_as_string(&add->lock_file_name), -+ O_EXCL | O_CREAT | O_WRONLY, 0644); -+ if (add->lock_file_fd < 0) { -+ if (errno == EEXIST) { -+ err = REFTABLE_LOCK_ERROR; -+ } else { -+ err = REFTABLE_IO_ERROR; ++ segs[next++] = cur; ++ cur = fresh; + } -+ goto done; ++ ++ cur.log = log; ++ cur.end = i + 1; ++ cur.bytes += sizes[i]; + } -+ err = stack_uptodate(st); -+ if (err < 0) -+ goto done; ++ segs[next++] = cur; ++ *seglen = next; ++ return segs; ++} + -+ if (err > 1) { -+ err = REFTABLE_LOCK_ERROR; -+ goto done; ++struct segment suggest_compaction_segment(uint64_t *sizes, int n) ++{ ++ int seglen = 0; ++ struct segment *segs = sizes_to_segments(&seglen, sizes, n); ++ struct segment min_seg = { ++ .log = 64, ++ }; ++ int i = 0; ++ for (i = 0; i < seglen; i++) { ++ if (segment_size(&segs[i]) == 1) { ++ continue; ++ } ++ ++ if (segs[i].log < min_seg.log) { ++ min_seg = segs[i]; ++ } + } + -+ add->next_update_index = reftable_stack_next_update_index(st); -+done: -+ if (err) { -+ reftable_addition_close(add); ++ while (min_seg.start > 0) { ++ int prev = min_seg.start - 1; ++ if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev])) { ++ break; ++ } ++ ++ min_seg.start = prev; ++ min_seg.bytes += sizes[prev]; + } -+ return err; ++ ++ reftable_free(segs); ++ return min_seg; +} + -+void reftable_addition_close(struct reftable_addition *add) ++static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack *st) +{ ++ uint64_t *sizes = ++ reftable_calloc(sizeof(uint64_t) * st->merged->stack_len); ++ int version = (st->config.hash_id == SHA1_ID) ? 1 : 2; ++ int overhead = header_size(version) - 1; + int i = 0; -+ struct slice nm = SLICE_INIT; -+ for (i = 0; i < add->new_tables_len; i++) { -+ slice_set_string(&nm, add->stack->list_file); -+ slice_addstr(&nm, "/"); -+ slice_addstr(&nm, add->new_tables[i]); -+ unlink(slice_as_string(&nm)); -+ reftable_free(add->new_tables[i]); -+ add->new_tables[i] = NULL; ++ for (i = 0; i < st->merged->stack_len; i++) { ++ sizes[i] = st->merged->stack[i]->size - overhead; + } -+ reftable_free(add->new_tables); -+ add->new_tables = NULL; -+ add->new_tables_len = 0; ++ return sizes; ++} + -+ if (add->lock_file_fd > 0) { -+ close(add->lock_file_fd); -+ add->lock_file_fd = 0; -+ } -+ if (add->lock_file_name.len > 0) { -+ unlink(slice_as_string(&add->lock_file_name)); -+ slice_release(&add->lock_file_name); -+ } ++int reftable_stack_auto_compact(struct reftable_stack *st) ++{ ++ uint64_t *sizes = stack_table_sizes_for_compaction(st); ++ struct segment seg = ++ suggest_compaction_segment(sizes, st->merged->stack_len); ++ reftable_free(sizes); ++ if (segment_size(&seg) > 0) ++ return stack_compact_range_stats(st, seg.start, seg.end - 1, ++ NULL); + -+ free_names(add->names); -+ add->names = NULL; -+ slice_release(&nm); ++ return 0; +} + -+void reftable_addition_destroy(struct reftable_addition *add) ++struct reftable_compaction_stats * ++reftable_stack_compaction_stats(struct reftable_stack *st) +{ -+ if (add == NULL) { -+ return; -+ } -+ reftable_addition_close(add); -+ reftable_free(add); ++ return &st->stats; +} + -+int reftable_addition_commit(struct reftable_addition *add) ++int reftable_stack_read_ref(struct reftable_stack *st, const char *refname, ++ struct reftable_ref_record *ref) +{ -+ struct slice table_list = SLICE_INIT; -+ int i = 0; -+ int err = 0; -+ if (add->new_tables_len == 0) -+ goto done; -+ -+ for (i = 0; i < add->stack->merged->stack_len; i++) { -+ slice_addstr(&table_list, add->stack->merged->stack[i]->name); -+ slice_addstr(&table_list, "\n"); -+ } -+ for (i = 0; i < add->new_tables_len; i++) { -+ slice_addstr(&table_list, add->new_tables[i]); -+ slice_addstr(&table_list, "\n"); -+ } ++ struct reftable_table tab = { NULL }; ++ reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st)); ++ return reftable_table_read_ref(&tab, refname, ref); ++} + -+ err = write(add->lock_file_fd, table_list.buf, table_list.len); -+ slice_release(&table_list); -+ if (err < 0) { -+ err = REFTABLE_IO_ERROR; ++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_log(mt, &it, refname); ++ if (err) + goto done; -+ } + -+ err = close(add->lock_file_fd); -+ add->lock_file_fd = 0; -+ if (err < 0) { -+ err = REFTABLE_IO_ERROR; ++ err = reftable_iterator_next_log(&it, log); ++ if (err) + goto done; -+ } + -+ err = rename(slice_as_string(&add->lock_file_name), -+ add->stack->list_file); -+ if (err < 0) { -+ err = REFTABLE_IO_ERROR; ++ if (strcmp(log->ref_name, refname) || ++ reftable_log_record_is_deletion(log)) { ++ err = 1; + goto done; + } + -+ err = reftable_stack_reload(add->stack); -+ +done: -+ reftable_addition_close(add); -+ return err; -+} -+ -+int reftable_stack_new_addition(struct reftable_addition **dest, -+ struct reftable_stack *st) -+{ -+ int err = 0; -+ struct reftable_addition empty = REFTABLE_ADDITION_INIT; -+ *dest = reftable_calloc(sizeof(**dest)); -+ **dest = empty; -+ err = reftable_stack_init_addition(*dest, st); + if (err) { -+ reftable_free(*dest); -+ *dest = NULL; ++ reftable_log_record_clear(log); + } ++ reftable_iterator_destroy(&it); + return err; +} + -+int stack_try_add(struct reftable_stack *st, -+ int (*write_table)(struct reftable_writer *wr, void *arg), -+ void *arg) ++int stack_check_addition(struct reftable_stack *st, const char *new_tab_name) +{ -+ struct reftable_addition add = REFTABLE_ADDITION_INIT; -+ int err = reftable_stack_init_addition(&add, st); ++ 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 done; ++ ++ err = reftable_new_reader(&rd, &src, new_tab_name); + if (err < 0) + goto done; ++ ++ err = reftable_reader_seek_ref(rd, &it, ""); + if (err > 0) { -+ err = REFTABLE_LOCK_ERROR; ++ err = 0; + goto done; + } -+ -+ err = reftable_addition_add(&add, write_table, arg); + if (err < 0) + goto done; + -+ err = reftable_addition_commit(&add); ++ while (true) { ++ struct reftable_ref_record ref = { 0 }; ++ err = reftable_iterator_next_ref(&it, &ref); ++ if (err > 0) { ++ break; ++ } ++ if (err < 0) ++ goto done; ++ ++ 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); ++ +done: -+ reftable_addition_close(&add); ++ for (i = 0; i < len; i++) { ++ reftable_ref_record_clear(&refs[i]); ++ } ++ ++ free(refs); ++ reftable_iterator_destroy(&it); ++ reftable_reader_free(rd); + return err; +} + + ## reftable/stack.h (new) ## +@@ ++/* ++Copyright 2020 Google LLC + -+int reftable_addition_add(struct reftable_addition *add, -+ int (*write_table)(struct reftable_writer *wr, -+ void *arg), -+ void *arg) -+{ -+ struct slice temp_tab_file_name = SLICE_INIT; -+ struct slice tab_file_name = SLICE_INIT; -+ struct slice next_name = SLICE_INIT; -+ struct reftable_writer *wr = NULL; -+ int err = 0; -+ int tab_fd = 0; ++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 ++*/ + -+ slice_resize(&next_name, 0); -+ format_name(&next_name, add->next_update_index, add->next_update_index); ++#ifndef STACK_H ++#define STACK_H + -+ slice_set_string(&temp_tab_file_name, add->stack->reftable_dir); -+ slice_addstr(&temp_tab_file_name, "/"); -+ slice_addbuf(&temp_tab_file_name, next_name); -+ slice_addstr(&temp_tab_file_name, ".temp.XXXXXX"); ++#include "reftable.h" ++#include "system.h" + -+ tab_fd = mkstemp((char *)slice_as_string(&temp_tab_file_name)); -+ if (tab_fd < 0) { -+ err = REFTABLE_IO_ERROR; -+ goto done; -+ } ++struct reftable_stack { ++ char *list_file; ++ char *reftable_dir; ++ bool disable_auto_compact; + -+ wr = reftable_new_writer(reftable_fd_write, &tab_fd, -+ &add->stack->config); -+ err = write_table(wr, arg); -+ if (err < 0) -+ goto done; ++ struct reftable_write_options config; + -+ err = reftable_writer_close(wr); -+ if (err == REFTABLE_EMPTY_TABLE_ERROR) { -+ err = 0; -+ goto done; -+ } -+ if (err < 0) -+ goto done; ++ struct reftable_merged_table *merged; ++ struct reftable_compaction_stats stats; ++}; + -+ err = close(tab_fd); -+ tab_fd = 0; -+ if (err < 0) { -+ err = REFTABLE_IO_ERROR; -+ goto done; -+ } ++int read_lines(const char *filename, char ***lines); ++int stack_try_add(struct reftable_stack *st, ++ int (*write_table)(struct reftable_writer *wr, void *arg), ++ void *arg); ++int stack_write_compact(struct reftable_stack *st, struct reftable_writer *wr, ++ 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); ++void reftable_addition_close(struct reftable_addition *add); ++int reftable_stack_reload_maybe_reuse(struct reftable_stack *st, ++ bool reuse_open); + -+ err = stack_check_addition(add->stack, -+ slice_as_string(&temp_tab_file_name)); -+ if (err < 0) -+ goto done; ++struct segment { ++ int start, end; ++ int log; ++ uint64_t bytes; ++}; + -+ if (wr->min_update_index < add->next_update_index) { -+ err = REFTABLE_API_ERROR; -+ goto done; -+ } ++struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n); ++struct segment suggest_compaction_segment(uint64_t *sizes, int n); + -+ format_name(&next_name, wr->min_update_index, wr->max_update_index); -+ slice_addstr(&next_name, ".ref"); ++#endif + + ## reftable/stack_test.c (new) ## +@@ ++/* ++Copyright 2020 Google LLC + -+ slice_set_string(&tab_file_name, add->stack->reftable_dir); -+ slice_addstr(&tab_file_name, "/"); -+ slice_addbuf(&tab_file_name, next_name); ++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 ++*/ + -+ /* TODO: should check destination out of paranoia */ -+ err = rename(slice_as_string(&temp_tab_file_name), -+ slice_as_string(&tab_file_name)); -+ if (err < 0) { -+ err = REFTABLE_IO_ERROR; -+ goto done; -+ } ++#include "stack.h" + -+ add->new_tables = reftable_realloc(add->new_tables, -+ sizeof(*add->new_tables) * -+ (add->new_tables_len + 1)); -+ add->new_tables[add->new_tables_len] = slice_to_string(next_name); -+ add->new_tables_len++; -+done: -+ if (tab_fd > 0) { -+ close(tab_fd); -+ tab_fd = 0; -+ } -+ if (temp_tab_file_name.len > 0) { -+ unlink(slice_as_string(&temp_tab_file_name)); -+ } ++#include "system.h" + -+ slice_release(&temp_tab_file_name); -+ slice_release(&tab_file_name); -+ slice_release(&next_name); -+ reftable_writer_free(wr); -+ return err; -+} ++#include "merged.h" ++#include "basics.h" ++#include "constants.h" ++#include "record.h" ++#include "reftable.h" ++#include "test_framework.h" ++#include "reftable-tests.h" + -+uint64_t reftable_stack_next_update_index(struct reftable_stack *st) -+{ -+ int sz = st->merged->stack_len; -+ if (sz > 0) -+ return reftable_reader_max_update_index( -+ st->merged->stack[sz - 1]) + -+ 1; -+ return 1; -+} ++#include <sys/types.h> ++#include <dirent.h> + -+static int stack_compact_locked(struct reftable_stack *st, int first, int last, -+ struct slice *temp_tab, -+ struct reftable_log_expiry_config *config) ++static void clear_dir(const char *dirname) +{ -+ struct slice next_name = SLICE_INIT; -+ int tab_fd = -1; -+ struct reftable_writer *wr = NULL; -+ int err = 0; ++ int fd = open(dirname, O_DIRECTORY, 0); ++ DIR *dir = fdopendir(fd); ++ struct dirent *ent = NULL; + -+ format_name(&next_name, -+ reftable_reader_min_update_index(st->merged->stack[first]), -+ reftable_reader_max_update_index(st->merged->stack[first])); ++ assert(fd >= 0); + -+ slice_set_string(temp_tab, st->reftable_dir); -+ slice_addstr(temp_tab, "/"); -+ slice_addbuf(temp_tab, next_name); -+ slice_addstr(temp_tab, ".temp.XXXXXX"); ++ while ((ent = readdir(dir)) != NULL) { ++ unlinkat(fd, ent->d_name, 0); ++ } ++ closedir(dir); ++ rmdir(dirname); ++} + -+ tab_fd = mkstemp((char *)slice_as_string(temp_tab)); -+ wr = reftable_new_writer(reftable_fd_write, &tab_fd, &st->config); ++static void test_read_file(void) ++{ ++ char fn[256] = "/tmp/stack.test_read_file.XXXXXX"; ++ int fd = mkstemp(fn); ++ char out[1024] = "line1\n\nline2\nline3"; ++ int n, err; ++ char **names = NULL; ++ char *want[] = { "line1", "line2", "line3" }; ++ int i = 0; + -+ err = stack_write_compact(st, wr, first, last, config); -+ if (err < 0) -+ goto done; -+ err = reftable_writer_close(wr); -+ if (err < 0) -+ goto done; ++ assert(fd > 0); ++ n = write(fd, out, strlen(out)); ++ assert(n == strlen(out)); ++ err = close(fd); ++ assert(err >= 0); + -+ err = close(tab_fd); -+ tab_fd = 0; ++ err = read_lines(fn, &names); ++ assert_err(err); + -+done: -+ reftable_writer_free(wr); -+ if (tab_fd > 0) { -+ close(tab_fd); -+ tab_fd = 0; ++ for (i = 0; names[i] != NULL; i++) { ++ assert(0 == strcmp(want[i], names[i])); + } -+ if (err != 0 && temp_tab->len > 0) { -+ unlink(slice_as_string(temp_tab)); -+ slice_release(temp_tab); -+ } -+ slice_release(&next_name); -+ return err; ++ free_names(names); ++ remove(fn); +} + -+int stack_write_compact(struct reftable_stack *st, struct reftable_writer *wr, -+ int first, int last, -+ struct reftable_log_expiry_config *config) ++static void test_parse_names(void) +{ -+ int subtabs_len = last - first + 1; -+ struct reftable_reader **subtabs = reftable_calloc( -+ sizeof(struct reftable_reader *) * (last - first + 1)); -+ struct reftable_merged_table *mt = NULL; -+ int err = 0; -+ struct reftable_iterator it = { 0 }; -+ struct reftable_ref_record ref = { 0 }; -+ struct reftable_log_record log = { 0 }; ++ char buf[] = "line\n"; ++ char **names = NULL; ++ parse_names(buf, strlen(buf), &names); + -+ uint64_t entries = 0; ++ assert(NULL != names[0]); ++ assert(0 == strcmp(names[0], "line")); ++ assert(NULL == names[1]); ++ free_names(names); ++} + -+ int i = 0, j = 0; -+ for (i = first, j = 0; i <= last; i++) { -+ struct reftable_reader *t = st->merged->stack[i]; -+ subtabs[j++] = t; -+ st->stats.bytes += t->size; -+ } -+ reftable_writer_set_limits(wr, -+ st->merged->stack[first]->min_update_index, -+ st->merged->stack[last]->max_update_index); ++static void test_names_equal(void) ++{ ++ char *a[] = { "a", "b", "c", NULL }; ++ char *b[] = { "a", "b", "d", NULL }; ++ char *c[] = { "a", "b", NULL }; + -+ err = reftable_new_merged_table(&mt, subtabs, subtabs_len, -+ st->config.hash_id); -+ if (err < 0) { -+ reftable_free(subtabs); -+ goto done; -+ } ++ assert(names_equal(a, a)); ++ assert(!names_equal(a, b)); ++ assert(!names_equal(a, c)); ++} + -+ err = reftable_merged_table_seek_ref(mt, &it, ""); -+ if (err < 0) -+ goto done; ++static int write_test_ref(struct reftable_writer *wr, void *arg) ++{ ++ struct reftable_ref_record *ref = arg; ++ reftable_writer_set_limits(wr, ref->update_index, ref->update_index); ++ return reftable_writer_add_ref(wr, ref); ++} + -+ while (true) { -+ err = reftable_iterator_next_ref(&it, &ref); -+ if (err > 0) { -+ err = 0; -+ break; -+ } -+ if (err < 0) { -+ break; -+ } -+ if (first == 0 && reftable_ref_record_is_deletion(&ref)) { -+ continue; -+ } ++struct write_log_arg { ++ struct reftable_log_record *log; ++ uint64_t update_index; ++}; + -+ err = reftable_writer_add_ref(wr, &ref); -+ if (err < 0) { -+ break; -+ } -+ entries++; -+ } -+ reftable_iterator_destroy(&it); ++static int write_test_log(struct reftable_writer *wr, void *arg) ++{ ++ struct write_log_arg *wla = arg; + -+ err = reftable_merged_table_seek_log(mt, &it, ""); -+ if (err < 0) -+ goto done; ++ reftable_writer_set_limits(wr, wla->update_index, wla->update_index); ++ return reftable_writer_add_log(wr, wla->log); ++} + -+ while (true) { -+ err = reftable_iterator_next_log(&it, &log); -+ if (err > 0) { -+ err = 0; -+ break; -+ } -+ if (err < 0) { -+ break; -+ } -+ if (first == 0 && reftable_log_record_is_deletion(&log)) { -+ continue; -+ } ++static void test_reftable_stack_add_one(void) ++{ ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ int err; ++ struct reftable_ref_record ref = { ++ .ref_name = "HEAD", ++ .update_index = 1, ++ .target = "master", ++ }; ++ struct reftable_ref_record dest = { 0 }; + -+ if (config != NULL && config->time > 0 && -+ log.time < config->time) { -+ continue; -+ } ++ assert(mkdtemp(dir)); + -+ if (config != NULL && config->min_update_index > 0 && -+ log.update_index < config->min_update_index) { -+ continue; -+ } ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); + -+ err = reftable_writer_add_log(wr, &log); -+ if (err < 0) { -+ break; -+ } -+ entries++; -+ } ++ err = reftable_stack_add(st, &write_test_ref, &ref); ++ assert_err(err); + -+done: -+ reftable_iterator_destroy(&it); -+ if (mt != NULL) { -+ merged_table_clear(mt); -+ reftable_merged_table_free(mt); -+ } -+ reftable_ref_record_clear(&ref); -+ reftable_log_record_clear(&log); -+ st->stats.entries_written += entries; -+ return err; ++ err = reftable_stack_read_ref(st, ref.ref_name, &dest); ++ assert_err(err); ++ assert(0 == strcmp("master", dest.target)); ++ ++ reftable_ref_record_clear(&dest); ++ reftable_stack_destroy(st); ++ clear_dir(dir); +} + -+/* < 0: error. 0 == OK, > 0 attempt failed; could retry. */ -+static int stack_compact_range(struct reftable_stack *st, int first, int last, -+ struct reftable_log_expiry_config *expiry) ++static void test_reftable_stack_uptodate(void) +{ -+ struct slice temp_tab_file_name = SLICE_INIT; -+ struct slice new_table_name = SLICE_INIT; -+ struct slice lock_file_name = SLICE_INIT; -+ struct slice ref_list_contents = SLICE_INIT; -+ struct slice new_table_path = SLICE_INIT; -+ int err = 0; -+ bool have_lock = false; -+ int lock_file_fd = 0; -+ int compact_count = last - first + 1; -+ char **listp = NULL; -+ char **delete_on_success = -+ reftable_calloc(sizeof(char *) * (compact_count + 1)); -+ char **subtable_locks = -+ reftable_calloc(sizeof(char *) * (compact_count + 1)); -+ int i = 0; -+ int j = 0; -+ bool is_empty_table = false; -+ -+ if (first > last || (expiry == NULL && first == last)) { -+ err = 0; -+ goto done; -+ } -+ -+ st->stats.attempts++; -+ -+ slice_set_string(&lock_file_name, st->list_file); -+ slice_addstr(&lock_file_name, ".lock"); ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st1 = NULL; ++ struct reftable_stack *st2 = NULL; ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ int err; ++ struct reftable_ref_record ref1 = { ++ .ref_name = "HEAD", ++ .update_index = 1, ++ .target = "master", ++ }; ++ struct reftable_ref_record ref2 = { ++ .ref_name = "branch2", ++ .update_index = 2, ++ .target = "master", ++ }; + -+ lock_file_fd = open(slice_as_string(&lock_file_name), -+ O_EXCL | O_CREAT | O_WRONLY, 0644); -+ if (lock_file_fd < 0) { -+ if (errno == EEXIST) { -+ err = 1; -+ } else { -+ err = REFTABLE_IO_ERROR; -+ } -+ goto done; -+ } -+ /* Don't want to write to the lock for now. */ -+ close(lock_file_fd); -+ lock_file_fd = 0; ++ assert(mkdtemp(dir)); + -+ have_lock = true; -+ err = stack_uptodate(st); -+ if (err != 0) -+ goto done; ++ err = reftable_new_stack(&st1, dir, cfg); ++ assert_err(err); + -+ for (i = first, j = 0; i <= last; i++) { -+ struct slice subtab_file_name = SLICE_INIT; -+ struct slice subtab_lock = SLICE_INIT; -+ int sublock_file_fd = -1; ++ err = reftable_new_stack(&st2, dir, cfg); ++ assert_err(err); + -+ slice_set_string(&subtab_file_name, st->reftable_dir); -+ slice_addstr(&subtab_file_name, "/"); -+ slice_addstr(&subtab_file_name, -+ reader_name(st->merged->stack[i])); ++ err = reftable_stack_add(st1, &write_test_ref, &ref1); ++ assert_err(err); + -+ slice_copy(&subtab_lock, subtab_file_name); -+ slice_addstr(&subtab_lock, ".lock"); ++ err = reftable_stack_add(st2, &write_test_ref, &ref2); ++ assert(err == REFTABLE_LOCK_ERROR); + -+ sublock_file_fd = open(slice_as_string(&subtab_lock), -+ O_EXCL | O_CREAT | O_WRONLY, 0644); -+ if (sublock_file_fd > 0) { -+ close(sublock_file_fd); -+ } else if (sublock_file_fd < 0) { -+ if (errno == EEXIST) { -+ err = 1; -+ } else { -+ err = REFTABLE_IO_ERROR; -+ } -+ } ++ err = reftable_stack_reload(st2); ++ assert_err(err); + -+ subtable_locks[j] = (char *)slice_as_string(&subtab_lock); -+ delete_on_success[j] = -+ (char *)slice_as_string(&subtab_file_name); -+ j++; ++ err = reftable_stack_add(st2, &write_test_ref, &ref2); ++ assert_err(err); ++ reftable_stack_destroy(st1); ++ reftable_stack_destroy(st2); ++ clear_dir(dir); ++} + -+ if (err != 0) -+ goto done; -+ } ++static void test_reftable_stack_transaction_api(void) ++{ ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ int err; ++ struct reftable_addition *add = NULL; + -+ err = unlink(slice_as_string(&lock_file_name)); -+ if (err < 0) -+ goto done; -+ have_lock = false; ++ struct reftable_ref_record ref = { ++ .ref_name = "HEAD", ++ .update_index = 1, ++ .target = "master", ++ }; ++ struct reftable_ref_record dest = { 0 }; + -+ err = stack_compact_locked(st, first, last, &temp_tab_file_name, -+ expiry); -+ /* Compaction + tombstones can create an empty table out of non-empty -+ * tables. */ -+ is_empty_table = (err == REFTABLE_EMPTY_TABLE_ERROR); -+ if (is_empty_table) { -+ err = 0; -+ } -+ if (err < 0) -+ goto done; ++ assert(mkdtemp(dir)); + -+ lock_file_fd = open(slice_as_string(&lock_file_name), -+ O_EXCL | O_CREAT | O_WRONLY, 0644); -+ if (lock_file_fd < 0) { -+ if (errno == EEXIST) { -+ err = 1; -+ } else { -+ err = REFTABLE_IO_ERROR; -+ } -+ goto done; -+ } -+ have_lock = true; ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); + -+ format_name(&new_table_name, st->merged->stack[first]->min_update_index, -+ st->merged->stack[last]->max_update_index); -+ slice_addstr(&new_table_name, ".ref"); ++ reftable_addition_destroy(add); + -+ slice_set_string(&new_table_path, st->reftable_dir); -+ slice_addstr(&new_table_path, "/"); ++ err = reftable_stack_new_addition(&add, st); ++ assert_err(err); + -+ slice_addbuf(&new_table_path, new_table_name); ++ err = reftable_addition_add(add, &write_test_ref, &ref); ++ assert_err(err); + -+ if (!is_empty_table) { -+ err = rename(slice_as_string(&temp_tab_file_name), -+ slice_as_string(&new_table_path)); -+ if (err < 0) { -+ err = REFTABLE_IO_ERROR; -+ goto done; -+ } -+ } ++ err = reftable_addition_commit(add); ++ assert_err(err); + -+ for (i = 0; i < first; i++) { -+ slice_addstr(&ref_list_contents, st->merged->stack[i]->name); -+ slice_addstr(&ref_list_contents, "\n"); -+ } -+ if (!is_empty_table) { -+ slice_addbuf(&ref_list_contents, new_table_name); -+ slice_addstr(&ref_list_contents, "\n"); -+ } -+ for (i = last + 1; i < st->merged->stack_len; i++) { -+ slice_addstr(&ref_list_contents, st->merged->stack[i]->name); -+ slice_addstr(&ref_list_contents, "\n"); -+ } ++ reftable_addition_destroy(add); + -+ err = write(lock_file_fd, ref_list_contents.buf, ref_list_contents.len); -+ if (err < 0) { -+ err = REFTABLE_IO_ERROR; -+ unlink(slice_as_string(&new_table_path)); -+ goto done; -+ } -+ err = close(lock_file_fd); -+ lock_file_fd = 0; -+ if (err < 0) { -+ err = REFTABLE_IO_ERROR; -+ unlink(slice_as_string(&new_table_path)); -+ goto done; -+ } ++ err = reftable_stack_read_ref(st, ref.ref_name, &dest); ++ assert_err(err); ++ assert(0 == strcmp("master", dest.target)); + -+ err = rename(slice_as_string(&lock_file_name), st->list_file); -+ if (err < 0) { -+ err = REFTABLE_IO_ERROR; -+ unlink(slice_as_string(&new_table_path)); -+ goto done; -+ } -+ have_lock = false; ++ reftable_ref_record_clear(&dest); ++ reftable_stack_destroy(st); ++ clear_dir(dir); ++} + -+ /* 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); ++static void test_reftable_stack_validate_refname(void) ++{ ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ int err; ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ int i; ++ struct reftable_ref_record ref = { ++ .ref_name = "a/b", ++ .update_index = 1, ++ .target = "master", ++ }; ++ char *additions[] = { "a", "a/b/c" }; + -+ listp = delete_on_success; -+ while (*listp) { -+ if (strcmp(*listp, slice_as_string(&new_table_path))) { -+ unlink(*listp); -+ } -+ listp++; -+ } ++ assert(mkdtemp(dir)); ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); + -+done: -+ free_names(delete_on_success); ++ err = reftable_stack_add(st, &write_test_ref, &ref); ++ assert_err(err); + -+ listp = subtable_locks; -+ while (*listp) { -+ unlink(*listp); -+ listp++; -+ } -+ free_names(subtable_locks); -+ if (lock_file_fd > 0) { -+ close(lock_file_fd); -+ lock_file_fd = 0; -+ } -+ if (have_lock) { -+ unlink(slice_as_string(&lock_file_name)); ++ for (i = 0; i < ARRAY_SIZE(additions); i++) { ++ struct reftable_ref_record ref = { ++ .ref_name = additions[i], ++ .update_index = 1, ++ .target = "master", ++ }; ++ ++ err = reftable_stack_add(st, &write_test_ref, &ref); ++ assert(err == REFTABLE_NAME_CONFLICT); + } -+ slice_release(&new_table_name); -+ slice_release(&new_table_path); -+ slice_release(&ref_list_contents); -+ slice_release(&temp_tab_file_name); -+ slice_release(&lock_file_name); -+ return err; -+} + -+int reftable_stack_compact_all(struct reftable_stack *st, -+ struct reftable_log_expiry_config *config) -+{ -+ return stack_compact_range(st, 0, st->merged->stack_len - 1, config); ++ reftable_stack_destroy(st); ++ clear_dir(dir); +} + -+static int stack_compact_range_stats(struct reftable_stack *st, int first, -+ int last, -+ struct reftable_log_expiry_config *config) ++static int write_error(struct reftable_writer *wr, void *arg) +{ -+ int err = stack_compact_range(st, first, last, config); -+ if (err > 0) { -+ st->stats.failures++; -+ } -+ return err; ++ return *((int *)arg); +} + -+static int segment_size(struct segment *s) ++static void test_reftable_stack_update_index_check(void) +{ -+ return s->end - s->start; ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ int err; ++ struct reftable_ref_record ref1 = { ++ .ref_name = "name1", ++ .update_index = 1, ++ .target = "master", ++ }; ++ struct reftable_ref_record ref2 = { ++ .ref_name = "name2", ++ .update_index = 1, ++ .target = "master", ++ }; ++ assert(mkdtemp(dir)); ++ ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); ++ ++ err = reftable_stack_add(st, &write_test_ref, &ref1); ++ assert_err(err); ++ ++ err = reftable_stack_add(st, &write_test_ref, &ref2); ++ assert(err == REFTABLE_API_ERROR); ++ reftable_stack_destroy(st); ++ clear_dir(dir); +} + -+int fastlog2(uint64_t sz) ++static void test_reftable_stack_lock_failure(void) +{ -+ int l = 0; -+ if (sz == 0) -+ return 0; -+ for (; sz; sz /= 2) { -+ l++; ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ int err, i; ++ assert(mkdtemp(dir)); ++ ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); ++ for (i = -1; i != REFTABLE_EMPTY_TABLE_ERROR; i--) { ++ err = reftable_stack_add(st, &write_error, &i); ++ assert(err == i); + } -+ return l - 1; ++ ++ reftable_stack_destroy(st); ++ clear_dir(dir); +} + -+struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n) ++static void test_reftable_stack_add(void) +{ -+ struct segment *segs = reftable_calloc(sizeof(struct segment) * n); -+ int next = 0; -+ struct segment cur = { 0 }; + int i = 0; ++ int err = 0; ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ struct reftable_ref_record refs[2] = { 0 }; ++ struct reftable_log_record logs[2] = { 0 }; ++ int N = ARRAY_SIZE(refs); ++ ++ assert(mkdtemp(dir)); ++ ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); ++ st->disable_auto_compact = true; ++ ++ for (i = 0; i < N; i++) { ++ char buf[256]; ++ snprintf(buf, sizeof(buf), "branch%02d", i); ++ refs[i].ref_name = xstrdup(buf); ++ refs[i].value = reftable_malloc(SHA1_SIZE); ++ refs[i].update_index = i + 1; ++ set_test_hash(refs[i].value, i); ++ ++ logs[i].ref_name = xstrdup(buf); ++ logs[i].update_index = N + i + 1; ++ logs[i].new_hash = reftable_malloc(SHA1_SIZE); ++ logs[i].email = xstrdup("identity@invalid"); ++ set_test_hash(logs[i].new_hash, i); ++ } ++ ++ for (i = 0; i < N; i++) { ++ int err = reftable_stack_add(st, &write_test_ref, &refs[i]); ++ assert_err(err); ++ } ++ ++ for (i = 0; i < N; i++) { ++ struct write_log_arg arg = { ++ .log = &logs[i], ++ .update_index = reftable_stack_next_update_index(st), ++ }; ++ int err = reftable_stack_add(st, &write_test_log, &arg); ++ assert_err(err); ++ } + -+ if (n == 0) { -+ *seglen = 0; -+ return segs; ++ err = reftable_stack_compact_all(st, NULL); ++ assert_err(err); ++ ++ for (i = 0; i < N; i++) { ++ struct reftable_ref_record dest = { 0 }; ++ int err = reftable_stack_read_ref(st, refs[i].ref_name, &dest); ++ assert_err(err); ++ assert(reftable_ref_record_equal(&dest, refs + i, SHA1_SIZE)); ++ reftable_ref_record_clear(&dest); + } -+ for (i = 0; i < n; i++) { -+ int log = fastlog2(sizes[i]); -+ if (cur.log != log && cur.bytes > 0) { -+ struct segment fresh = { -+ .start = i, -+ }; + -+ segs[next++] = cur; -+ cur = fresh; -+ } ++ for (i = 0; i < N; i++) { ++ struct reftable_log_record dest = { 0 }; ++ int err = reftable_stack_read_log(st, refs[i].ref_name, &dest); ++ assert_err(err); ++ assert(reftable_log_record_equal(&dest, logs + i, SHA1_SIZE)); ++ reftable_log_record_clear(&dest); ++ } + -+ cur.log = log; -+ cur.end = i + 1; -+ cur.bytes += sizes[i]; ++ /* cleanup */ ++ reftable_stack_destroy(st); ++ for (i = 0; i < N; i++) { ++ reftable_ref_record_clear(&refs[i]); ++ reftable_log_record_clear(&logs[i]); + } -+ segs[next++] = cur; -+ *seglen = next; -+ return segs; ++ clear_dir(dir); +} + -+struct segment suggest_compaction_segment(uint64_t *sizes, int n) ++static void test_reftable_stack_tombstone(void) +{ -+ int seglen = 0; -+ struct segment *segs = sizes_to_segments(&seglen, sizes, n); -+ struct segment min_seg = { -+ .log = 64, -+ }; + int i = 0; -+ for (i = 0; i < seglen; i++) { -+ if (segment_size(&segs[i]) == 1) { -+ continue; ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ int err; ++ struct reftable_ref_record refs[2] = { 0 }; ++ struct reftable_log_record logs[2] = { 0 }; ++ int N = ARRAY_SIZE(refs); ++ struct reftable_ref_record dest = { 0 }; ++ struct reftable_log_record log_dest = { 0 }; ++ ++ assert(mkdtemp(dir)); ++ ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); ++ ++ for (i = 0; i < N; i++) { ++ const char *buf = "branch"; ++ refs[i].ref_name = xstrdup(buf); ++ refs[i].update_index = i + 1; ++ if (i % 2 == 0) { ++ refs[i].value = reftable_malloc(SHA1_SIZE); ++ set_test_hash(refs[i].value, i); + } -+ -+ if (segs[i].log < min_seg.log) { -+ min_seg = segs[i]; ++ logs[i].ref_name = xstrdup(buf); ++ /* update_index is part of the key. */ ++ logs[i].update_index = 42; ++ if (i % 2 == 0) { ++ logs[i].new_hash = reftable_malloc(SHA1_SIZE); ++ set_test_hash(logs[i].new_hash, i); ++ logs[i].email = xstrdup("identity@invalid"); + } + } ++ for (i = 0; i < N; i++) { ++ int err = reftable_stack_add(st, &write_test_ref, &refs[i]); ++ assert_err(err); ++ } ++ for (i = 0; i < N; i++) { ++ struct write_log_arg arg = { ++ .log = &logs[i], ++ .update_index = reftable_stack_next_update_index(st), ++ }; ++ int err = reftable_stack_add(st, &write_test_log, &arg); ++ assert_err(err); ++ } + -+ while (min_seg.start > 0) { -+ int prev = min_seg.start - 1; -+ if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev])) { -+ break; -+ } ++ err = reftable_stack_read_ref(st, "branch", &dest); ++ assert(err == 1); ++ reftable_ref_record_clear(&dest); + -+ min_seg.start = prev; -+ min_seg.bytes += sizes[prev]; -+ } ++ err = reftable_stack_read_log(st, "branch", &log_dest); ++ assert(err == 1); ++ reftable_log_record_clear(&log_dest); + -+ reftable_free(segs); -+ return min_seg; -+} ++ err = reftable_stack_compact_all(st, NULL); ++ assert_err(err); + -+static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack *st) -+{ -+ uint64_t *sizes = -+ reftable_calloc(sizeof(uint64_t) * st->merged->stack_len); -+ int version = (st->config.hash_id == SHA1_ID) ? 1 : 2; -+ 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; ++ err = reftable_stack_read_ref(st, "branch", &dest); ++ assert(err == 1); ++ ++ err = reftable_stack_read_log(st, "branch", &log_dest); ++ assert(err == 1); ++ reftable_ref_record_clear(&dest); ++ reftable_log_record_clear(&log_dest); ++ ++ /* cleanup */ ++ reftable_stack_destroy(st); ++ for (i = 0; i < N; i++) { ++ reftable_ref_record_clear(&refs[i]); ++ reftable_log_record_clear(&logs[i]); + } -+ return sizes; ++ clear_dir(dir); +} + -+int reftable_stack_auto_compact(struct reftable_stack *st) ++static void test_reftable_stack_hash_id(void) +{ -+ uint64_t *sizes = stack_table_sizes_for_compaction(st); -+ struct segment seg = -+ suggest_compaction_segment(sizes, st->merged->stack_len); -+ reftable_free(sizes); -+ if (segment_size(&seg) > 0) -+ return stack_compact_range_stats(st, seg.start, seg.end - 1, -+ NULL); ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ int err; ++ ++ struct reftable_ref_record ref = { ++ .ref_name = "master", ++ .target = "target", ++ .update_index = 1, ++ }; ++ struct reftable_write_options cfg32 = { .hash_id = SHA256_ID }; ++ struct reftable_stack *st32 = NULL; ++ struct reftable_write_options cfg_default = { 0 }; ++ struct reftable_stack *st_default = NULL; ++ struct reftable_ref_record dest = { 0 }; ++ ++ assert(mkdtemp(dir)); ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); ++ ++ err = reftable_stack_add(st, &write_test_ref, &ref); ++ assert_err(err); ++ ++ /* can't read it with the wrong hash ID. */ ++ err = reftable_new_stack(&st32, dir, cfg32); ++ assert(err == REFTABLE_FORMAT_ERROR); ++ ++ /* check that we can read it back with default config too. */ ++ err = reftable_new_stack(&st_default, dir, cfg_default); ++ assert_err(err); ++ ++ err = reftable_stack_read_ref(st_default, "master", &dest); ++ assert_err(err); ++ ++ assert(!strcmp(dest.target, ref.target)); ++ reftable_ref_record_clear(&dest); ++ reftable_stack_destroy(st); ++ reftable_stack_destroy(st_default); ++ clear_dir(dir); ++} + -+ return 0; ++static void test_log2(void) ++{ ++ assert(1 == fastlog2(3)); ++ assert(2 == fastlog2(4)); ++ assert(2 == fastlog2(5)); +} + -+struct reftable_compaction_stats * -+reftable_stack_compaction_stats(struct reftable_stack *st) ++static void test_sizes_to_segments(void) +{ -+ return &st->stats; ++ uint64_t sizes[] = { 2, 3, 4, 5, 7, 9 }; ++ /* .................0 1 2 3 4 5 */ ++ ++ int seglen = 0; ++ struct segment *segs = ++ sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes)); ++ assert(segs[2].log == 3); ++ assert(segs[2].start == 5); ++ assert(segs[2].end == 6); ++ ++ assert(segs[1].log == 2); ++ assert(segs[1].start == 2); ++ assert(segs[1].end == 5); ++ reftable_free(segs); +} + -+int reftable_stack_read_ref(struct reftable_stack *st, const char *refname, -+ struct reftable_ref_record *ref) ++static void test_sizes_to_segments_empty(void) +{ -+ struct reftable_table tab = { NULL }; -+ reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st)); -+ return reftable_table_read_ref(&tab, refname, ref); ++ uint64_t sizes[0]; ++ ++ int seglen = 0; ++ struct segment *segs = ++ sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes)); ++ assert(seglen == 0); ++ reftable_free(segs); +} + -+int reftable_stack_read_log(struct reftable_stack *st, const char *refname, -+ struct reftable_log_record *log) ++static void test_sizes_to_segments_all_equal(void) +{ -+ 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) -+ goto done; ++ uint64_t sizes[] = { 5, 5 }; + -+ err = reftable_iterator_next_log(&it, log); -+ if (err) -+ goto done; ++ int seglen = 0; ++ struct segment *segs = ++ sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes)); ++ assert(seglen == 1); ++ assert(segs[0].start == 0); ++ assert(segs[0].end == 2); ++ reftable_free(segs); ++} + -+ if (strcmp(log->ref_name, refname) || -+ reftable_log_record_is_deletion(log)) { -+ err = 1; -+ goto done; -+ } ++static void test_suggest_compaction_segment(void) ++{ ++ uint64_t sizes[] = { 128, 64, 17, 16, 9, 9, 9, 16, 16 }; ++ /* .................0 1 2 3 4 5 6 */ ++ struct segment min = ++ suggest_compaction_segment(sizes, ARRAY_SIZE(sizes)); ++ assert(min.start == 2); ++ assert(min.end == 7); ++} + -+done: -+ if (err) { -+ reftable_log_record_clear(log); -+ } -+ reftable_iterator_destroy(&it); -+ return err; ++static void test_suggest_compaction_segment_nothing(void) ++{ ++ uint64_t sizes[] = { 64, 32, 16, 8, 4, 2 }; ++ struct segment result = ++ suggest_compaction_segment(sizes, ARRAY_SIZE(sizes)); ++ assert(result.start == result.end); +} + -+int stack_check_addition(struct reftable_stack *st, const char *new_tab_name) ++static void test_reflog_expire(void) +{ -+ 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; ++ char dir[256] = "/tmp/stack.test_reflog_expire.XXXXXX"; ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ struct reftable_log_record logs[20] = { 0 }; ++ int N = ARRAY_SIZE(logs) - 1; + int i = 0; ++ int err; ++ struct reftable_log_expiry_config expiry = { ++ .time = 10, ++ }; ++ struct reftable_log_record log = { 0 }; + -+ if (st->config.skip_name_check) -+ return 0; ++ assert(mkdtemp(dir)); + -+ err = reftable_block_source_from_file(&src, new_tab_name); -+ if (err < 0) -+ goto done; ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); + -+ err = reftable_new_reader(&rd, &src, new_tab_name); -+ if (err < 0) -+ goto done; ++ for (i = 1; i <= N; i++) { ++ char buf[256]; ++ snprintf(buf, sizeof(buf), "branch%02d", i); + -+ err = reftable_reader_seek_ref(rd, &it, ""); -+ if (err > 0) { -+ err = 0; -+ goto done; ++ logs[i].ref_name = xstrdup(buf); ++ logs[i].update_index = i; ++ logs[i].time = i; ++ logs[i].new_hash = reftable_malloc(SHA1_SIZE); ++ logs[i].email = xstrdup("identity@invalid"); ++ set_test_hash(logs[i].new_hash, i); + } -+ if (err < 0) -+ goto done; + -+ while (true) { -+ struct reftable_ref_record ref = { 0 }; -+ err = reftable_iterator_next_ref(&it, &ref); -+ if (err > 0) { -+ break; -+ } -+ if (err < 0) -+ goto done; ++ for (i = 1; i <= N; i++) { ++ struct write_log_arg arg = { ++ .log = &logs[i], ++ .update_index = reftable_stack_next_update_index(st), ++ }; ++ int err = reftable_stack_add(st, &write_test_log, &arg); ++ assert_err(err); ++ } + -+ if (len >= cap) { -+ cap = 2 * cap + 1; -+ refs = reftable_realloc(refs, cap * sizeof(refs[0])); -+ } ++ err = reftable_stack_compact_all(st, NULL); ++ assert_err(err); + -+ refs[len++] = ref; -+ } ++ err = reftable_stack_compact_all(st, &expiry); ++ assert_err(err); + -+ reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st)); ++ err = reftable_stack_read_log(st, logs[9].ref_name, &log); ++ assert(err == 1); + -+ err = validate_ref_record_addition(tab, refs, len); ++ err = reftable_stack_read_log(st, logs[11].ref_name, &log); ++ assert_err(err); + -+done: -+ for (i = 0; i < len; i++) { -+ reftable_ref_record_clear(&refs[i]); -+ } ++ expiry.min_update_index = 15; ++ err = reftable_stack_compact_all(st, &expiry); ++ assert_err(err); + -+ free(refs); -+ reftable_iterator_destroy(&it); -+ reftable_reader_free(rd); -+ return err; -+} - - ## reftable/stack.h (new) ## -@@ -+/* -+Copyright 2020 Google LLC ++ err = reftable_stack_read_log(st, logs[14].ref_name, &log); ++ assert(err == 1); + -+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 -+*/ ++ err = reftable_stack_read_log(st, logs[16].ref_name, &log); ++ assert_err(err); + -+#ifndef STACK_H -+#define STACK_H ++ /* cleanup */ ++ reftable_stack_destroy(st); ++ for (i = 0; i <= N; i++) { ++ reftable_log_record_clear(&logs[i]); ++ } ++ clear_dir(dir); ++ reftable_log_record_clear(&log); ++} + -+#include "reftable.h" -+#include "system.h" ++static int write_nothing(struct reftable_writer *wr, void *arg) ++{ ++ reftable_writer_set_limits(wr, 1, 1); ++ return 0; ++} + -+struct reftable_stack { -+ char *list_file; -+ char *reftable_dir; -+ bool disable_auto_compact; ++static void test_empty_add(void) ++{ ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ int err; ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ struct reftable_stack *st2 = NULL; + -+ struct reftable_write_options config; ++ assert(mkdtemp(dir)); + -+ struct reftable_merged_table *merged; -+ struct reftable_compaction_stats stats; -+}; ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); + -+int read_lines(const char *filename, char ***lines); -+int stack_try_add(struct reftable_stack *st, -+ int (*write_table)(struct reftable_writer *wr, void *arg), -+ void *arg); -+int stack_write_compact(struct reftable_stack *st, struct reftable_writer *wr, -+ 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); -+void reftable_addition_close(struct reftable_addition *add); -+int reftable_stack_reload_maybe_reuse(struct reftable_stack *st, -+ bool reuse_open); ++ err = reftable_stack_add(st, &write_nothing, NULL); ++ assert_err(err); + -+struct segment { -+ int start, end; -+ int log; -+ uint64_t bytes; -+}; ++ err = reftable_new_stack(&st2, dir, cfg); ++ assert_err(err); ++ clear_dir(dir); ++ reftable_stack_destroy(st); ++ reftable_stack_destroy(st2); ++} + -+struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n); -+struct segment suggest_compaction_segment(uint64_t *sizes, int n); ++static void test_reftable_stack_auto_compaction(void) ++{ ++ struct reftable_write_options cfg = { 0 }; ++ struct reftable_stack *st = NULL; ++ char dir[256] = "/tmp/stack_test.XXXXXX"; ++ int err, i; ++ int N = 100; ++ assert(mkdtemp(dir)); + -+#endif ++ err = reftable_new_stack(&st, dir, cfg); ++ assert_err(err); ++ ++ for (i = 0; i < N; i++) { ++ char name[100]; ++ struct reftable_ref_record ref = { ++ .ref_name = name, ++ .update_index = reftable_stack_next_update_index(st), ++ .target = "master", ++ }; ++ snprintf(name, sizeof(name), "branch%04d", i); ++ ++ err = reftable_stack_add(st, &write_test_ref, &ref); ++ assert_err(err); ++ ++ assert(i < 3 || st->merged->stack_len < 2 * fastlog2(i)); ++ } ++ ++ assert(reftable_stack_compaction_stats(st)->entries_written < ++ (uint64_t)(N * fastlog2(N))); ++ ++ reftable_stack_destroy(st); ++ clear_dir(dir); ++} ++ ++int stack_test_main(int argc, const char *argv[]) ++{ ++ add_test_case("test_reftable_stack_uptodate", ++ &test_reftable_stack_uptodate); ++ add_test_case("test_reftable_stack_transaction_api", ++ &test_reftable_stack_transaction_api); ++ add_test_case("test_reftable_stack_hash_id", ++ &test_reftable_stack_hash_id); ++ add_test_case("test_sizes_to_segments_all_equal", ++ &test_sizes_to_segments_all_equal); ++ add_test_case("test_reftable_stack_auto_compaction", ++ &test_reftable_stack_auto_compaction); ++ add_test_case("test_reftable_stack_validate_refname", ++ &test_reftable_stack_validate_refname); ++ add_test_case("test_reftable_stack_update_index_check", ++ &test_reftable_stack_update_index_check); ++ add_test_case("test_reftable_stack_lock_failure", ++ &test_reftable_stack_lock_failure); ++ add_test_case("test_reftable_stack_tombstone", ++ &test_reftable_stack_tombstone); ++ add_test_case("test_reftable_stack_add_one", ++ &test_reftable_stack_add_one); ++ add_test_case("test_empty_add", test_empty_add); ++ add_test_case("test_reflog_expire", test_reflog_expire); ++ add_test_case("test_suggest_compaction_segment", ++ &test_suggest_compaction_segment); ++ add_test_case("test_suggest_compaction_segment_nothing", ++ &test_suggest_compaction_segment_nothing); ++ add_test_case("test_sizes_to_segments", &test_sizes_to_segments); ++ add_test_case("test_sizes_to_segments_empty", ++ &test_sizes_to_segments_empty); ++ add_test_case("test_log2", &test_log2); ++ add_test_case("test_parse_names", &test_parse_names); ++ add_test_case("test_read_file", &test_read_file); ++ add_test_case("test_names_equal", &test_names_equal); ++ add_test_case("test_reftable_stack_add", &test_reftable_stack_add); ++ return test_main(argc, argv); ++} ## reftable/system.h (new) ## @@ @@ reftable/system.h (new) + const Bytef *source, uLong *sourceLen); +int hash_size(uint32_t id); + ++#endif + + ## reftable/test_framework.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 "test_framework.h" ++ ++#include "system.h" ++#include "basics.h" ++#include "constants.h" ++ ++struct test_case **test_cases; ++int test_case_len; ++int test_case_cap; ++ ++struct test_case *new_test_case(const char *name, void (*testfunc)(void)) ++{ ++ struct test_case *tc = reftable_malloc(sizeof(struct test_case)); ++ tc->name = name; ++ tc->testfunc = testfunc; ++ return tc; ++} ++ ++struct test_case *add_test_case(const char *name, void (*testfunc)(void)) ++{ ++ struct test_case *tc = new_test_case(name, testfunc); ++ if (test_case_len == test_case_cap) { ++ test_case_cap = 2 * test_case_cap + 1; ++ test_cases = reftable_realloc( ++ test_cases, sizeof(struct test_case) * test_case_cap); ++ } ++ ++ test_cases[test_case_len++] = tc; ++ return tc; ++} ++ ++int test_main(int argc, const char *argv[]) ++{ ++ const char *filter = NULL; ++ int i = 0; ++ if (argc > 1) { ++ filter = argv[1]; ++ } ++ ++ for (i = 0; i < test_case_len; i++) { ++ const char *name = test_cases[i]->name; ++ if (filter == NULL || strstr(name, filter) != NULL) { ++ printf("case %s\n", name); ++ test_cases[i]->testfunc(); ++ } else { ++ printf("skip %s\n", name); ++ } ++ ++ reftable_free(test_cases[i]); ++ } ++ reftable_free(test_cases); ++ test_cases = 0; ++ test_case_len = 0; ++ test_case_cap = 0; ++ return 0; ++} ++ ++void set_test_hash(byte *p, int i) ++{ ++ memset(p, (byte)i, hash_size(SHA1_ID)); ++} + + ## reftable/test_framework.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 TEST_FRAMEWORK_H ++#define TEST_FRAMEWORK_H ++ ++#include "system.h" ++ ++#include "reftable.h" ++ ++#ifdef NDEBUG ++#undef NDEBUG ++#endif ++ ++#include "system.h" ++ ++#ifdef assert ++#undef assert ++#endif ++ ++#define assert_err(c) \ ++ if (c != 0) { \ ++ fflush(stderr); \ ++ fflush(stdout); \ ++ fprintf(stderr, "%s: %d: error == %d (%s), want 0\n", \ ++ __FILE__, __LINE__, c, reftable_error_str(c)); \ ++ abort(); \ ++ } ++ ++#define assert_streq(a, b) \ ++ if (strcmp(a, b)) { \ ++ fflush(stderr); \ ++ fflush(stdout); \ ++ fprintf(stderr, "%s:%d: %s (%s) != %s (%s)\n", __FILE__, \ ++ __LINE__, #a, a, #b, b); \ ++ abort(); \ ++ } ++ ++#define assert(c) \ ++ if (!(c)) { \ ++ fflush(stderr); \ ++ fflush(stdout); \ ++ fprintf(stderr, "%s: %d: failed assertion %s\n", __FILE__, \ ++ __LINE__, #c); \ ++ abort(); \ ++ } ++ ++struct test_case { ++ const char *name; ++ void (*testfunc)(void); ++}; ++ ++struct test_case *new_test_case(const char *name, void (*testfunc)(void)); ++struct test_case *add_test_case(const char *name, void (*testfunc)(void)); ++int test_main(int argc, const char *argv[]); ++ ++void set_test_hash(byte *p, int i); ++ +#endif ## reftable/tree.c (new) ## @@ reftable/tree.h (new) + +#endif + ## reftable/tree_test.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 "tree.h" ++ ++#include "basics.h" ++#include "record.h" ++#include "reftable.h" ++#include "test_framework.h" ++#include "reftable-tests.h" ++ ++static int test_compare(const void *a, const void *b) ++{ ++ return (char *)a - (char *)b; ++} ++ ++struct curry { ++ void *last; ++}; ++ ++static void check_increasing(void *arg, void *key) ++{ ++ struct curry *c = (struct curry *)arg; ++ if (c->last != NULL) { ++ assert(test_compare(c->last, key) < 0); ++ } ++ c->last = key; ++} ++ ++static void test_tree(void) ++{ ++ struct tree_node *root = NULL; ++ ++ void *values[11] = { 0 }; ++ struct tree_node *nodes[11] = { 0 }; ++ int i = 1; ++ struct curry c = { 0 }; ++ do { ++ nodes[i] = tree_search(values + i, &root, &test_compare, 1); ++ i = (i * 7) % 11; ++ } while (i != 1); ++ ++ for (i = 1; i < ARRAY_SIZE(nodes); i++) { ++ assert(values + i == nodes[i]->key); ++ assert(nodes[i] == ++ tree_search(values + i, &root, &test_compare, 0)); ++ } ++ ++ infix_walk(root, check_increasing, &c); ++ tree_free(root); ++} ++ ++int tree_test_main(int argc, const char *argv[]) ++{ ++ add_test_case("test_tree", &test_tree); ++ return test_main(argc, argv); ++} + ## reftable/update.sh (new) ## @@ +#!/bin/sh @@ reftable/update.sh (new) +SRC=${SRC:-origin} +BRANCH=${BRANCH:-master} + -+((git --git-dir reftable-repo/.git fetch ${SRC} ${BRANCH}:import && cd reftable-repo && git checkout -f $(git rev-parse import) ) || ++((git --git-dir reftable-repo/.git fetch -f ${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 HEAD \ ++ ++git --git-dir reftable-repo/.git show --no-patch --format=oneline HEAD \ + > reftable/VERSION + +mv reftable/system.h reftable/system.h~ +sed 's|if REFTABLE_IN_GITCORE|if 1 /* REFTABLE_IN_GITCORE */|' < reftable/system.h~ > reftable/system.h + -+# Remove unittests and compatibility hacks we don't need here. -+rm reftable/*_test.c reftable/test_framework.* reftable/compat.* ++# Remove compatibility hacks we don't need here. ++rm reftable/compat.* + -+git add reftable/*.[ch] reftable/LICENSE reftable/VERSION ++git add reftable/*.[ch] reftable/LICENSE reftable/VERSION ## reftable/writer.c (new) ## @@ @@ reftable/writer.c (new) + +static int obj_index_tree_node_compare(const void *a, const void *b) +{ -+ return slice_cmp(((const struct obj_index_tree_node *)a)->hash, -+ ((const struct obj_index_tree_node *)b)->hash); ++ return slice_cmp(&((const struct obj_index_tree_node *)a)->hash, ++ &((const struct obj_index_tree_node *)b)->hash); +} + -+static void writer_index_hash(struct reftable_writer *w, struct slice hash) ++static void writer_index_hash(struct reftable_writer *w, struct slice *hash) +{ + uint64_t off = w->next; + -+ struct obj_index_tree_node want = { .hash = hash }; ++ struct obj_index_tree_node want = { .hash = *hash }; + + struct tree_node *node = tree_search(&want, &w->obj_index_tree, + &obj_index_tree_node_compare, 0); @@ reftable/writer.c (new) + struct slice key = SLICE_INIT; + int err = 0; + reftable_record_key(rec, &key); -+ if (slice_cmp(w->last_key, key) >= 0) ++ if (slice_cmp(&w->last_key, &key) >= 0) + goto done; + -+ slice_copy(&w->last_key, key); ++ slice_copy(&w->last_key, &key); + if (w->block_writer == NULL) { + writer_reinit_block_writer(w, reftable_record_type(rec)); + } @@ reftable/writer.c (new) + .canary = SLICE_CANARY, + }; + -+ writer_index_hash(w, h); ++ writer_index_hash(w, &h); + } + + if (!w->opts.skip_index_objects && ref->target_value != NULL) { @@ reftable/writer.c (new) + .len = hash_size(w->opts.hash_id), + .canary = SLICE_CANARY, + }; -+ writer_index_hash(w, h); ++ writer_index_hash(w, &h); + } + return 0; +} @@ reftable/writer.c (new) + struct common_prefix_arg *arg = (struct common_prefix_arg *)void_arg; + struct obj_index_tree_node *entry = (struct obj_index_tree_node *)key; + if (arg->last != NULL) { -+ int n = common_prefix_size(entry->hash, *arg->last); ++ int n = common_prefix_size(&entry->hash, arg->last); + if (n > arg->max) { + arg->max = n; + } @@ reftable/writer.c (new) + } + + ir.offset = w->next; -+ slice_copy(&ir.last_key, w->block_writer->last_key); ++ slice_copy(&ir.last_key, &w->block_writer->last_key); + w->index[w->index_len] = ir; + + w->index_len++; 10: a86c3753717 ! 10: f3d74b78135 Reftable support for git-core @@ builtin/init-db.c: 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; @@ refs/reftable-backend.c (new) + QSORT(sorted, transaction->nr, ref_update_cmp); + reftable_writer_set_limits(writer, ts, ts); + -+ + for (i = 0; i < transaction->nr; i++) { + struct ref_update *u = sorted[i]; + struct reftable_log_record *log = &logs[i]; @@ t/t0031-reftable.sh (new) + grep "commit: number 10" output && + git gc && + git reflog refs/heads/master >output && -+ test_line_count = 0 output ++ test_line_count = 0 output +' + +# This matches show-ref's output @@ t/t0031-reftable.sh (new) + print_ref "refs/heads/master" && + print_ref "refs/tags/file" && + print_ref "refs/tags/test_tag" && -+ print_ref "refs/tags/test_tag^{}" ++ print_ref "refs/tags/test_tag^{}" + } >expect && + git show-ref -d >actual && + test_cmp expect actual -: ----------- > 11: 3e7868ee409 Hookup unittests for the reftable library. 11: d3613c2ff53 = 12: 1f193b6da23 Add GIT_DEBUG_REFS debugging mechanism 12: 9b98ed614ec = 13: 0471f7e3570 vcxproj: adjust for the reftable changes 13: 5e401e4f1ac ! 14: a03c882b075 Add reftable testing infrastructure @@ builtin/clone.c: int cmd_clone(int argc, const char **argv, const char *prefix) if (real_git_dir) git_dir = real_git_dir; - ## builtin/init-db.c ## -@@ builtin/init-db.c: 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; - ## refs.c ## @@ refs.c: struct ref_store *get_main_ref_store(struct repository *r) r->refs_private = ref_store_init(r->gitdir,