| Message ID | 3595db76a525fcebc3c896e231246704b044310c.1698101088.git.me@ttaylorr.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | merge-ort: implement support for packing objects together | expand |
On Mon, Oct 23, 2023 at 06:45:06PM -0400, Taylor Blau wrote: > When using merge-tree often within a repository[^1], it is possible to > generate a relatively large number of loose objects, which can result in > degraded performance, and inode exhaustion in extreme cases. > > Building on the functionality introduced in previous commits, the > bulk-checkin machinery now has support to write arbitrary blob and tree > objects which are small enough to be held in-core. We can use this to > write any blob/tree objects generated by ORT into a separate pack > instead of writing them out individually as loose. > > This functionality is gated behind a new `--write-pack` option to > `merge-tree` that works with the (non-deprecated) `--write-tree` mode. > > The implementation is relatively straightforward. There are two spots > within the ORT mechanism where we call `write_object_file()`, one for > content differences within blobs, and another to assemble any new trees > necessary to construct the merge. In each of those locations, > conditionally replace calls to `write_object_file()` with > `index_blob_bulk_checkin_incore()` or `index_tree_bulk_checkin_incore()` > depending on which kind of object we are writing. > > The only remaining task is to begin and end the transaction necessary to > initialize the bulk-checkin machinery, and move any new pack(s) it > created into the main object store. > > [^1]: Such is the case at GitHub, where we run presumptive "test merges" > on open pull requests to see whether or not we can light up the merge > button green depending on whether or not the presumptive merge was > conflicted. > > This is done in response to a number of user-initiated events, > including viewing an open pull request whose last test merge is stale > with respect to the current base and tip of the pull request. As a > result, merge-tree can be run very frequently on large, active > repositories. > > Signed-off-by: Taylor Blau <me@ttaylorr.com> > --- > Documentation/git-merge-tree.txt | 4 ++ > builtin/merge-tree.c | 5 ++ > merge-ort.c | 42 +++++++++++---- > merge-recursive.h | 1 + > t/t4301-merge-tree-write-tree.sh | 93 ++++++++++++++++++++++++++++++++ > 5 files changed, 136 insertions(+), 9 deletions(-) > > diff --git a/Documentation/git-merge-tree.txt b/Documentation/git-merge-tree.txt > index ffc4fbf7e8..9d37609ef1 100644 > --- a/Documentation/git-merge-tree.txt > +++ b/Documentation/git-merge-tree.txt > @@ -69,6 +69,10 @@ OPTIONS > specify a merge-base for the merge, and specifying multiple bases is > currently not supported. This option is incompatible with `--stdin`. > > +--write-pack:: > + Write any new objects into a separate packfile instead of as > + individual loose objects. > + > [[OUTPUT]] > OUTPUT > ------ > diff --git a/builtin/merge-tree.c b/builtin/merge-tree.c > index a35e0452d6..218442ac9b 100644 > --- a/builtin/merge-tree.c > +++ b/builtin/merge-tree.c > @@ -19,6 +19,7 @@ > #include "tree.h" > #include "config.h" > #include "strvec.h" > +#include "bulk-checkin.h" > > static int line_termination = '\n'; > > @@ -416,6 +417,7 @@ struct merge_tree_options { > int name_only; > int use_stdin; > struct merge_options merge_options; > + int write_pack; > }; > > static int real_merge(struct merge_tree_options *o, > @@ -441,6 +443,7 @@ static int real_merge(struct merge_tree_options *o, > _("not something we can merge")); > > opt.show_rename_progress = 0; > + opt.write_pack = o->write_pack; > > opt.branch1 = branch1; > opt.branch2 = branch2; > @@ -553,6 +556,8 @@ int cmd_merge_tree(int argc, const char **argv, const char *prefix) > N_("specify a merge-base for the merge")), > OPT_STRVEC('X', "strategy-option", &xopts, N_("option=value"), > N_("option for selected merge strategy")), > + OPT_BOOL(0, "write-pack", &o.write_pack, > + N_("write new objects to a pack instead of as loose")), > OPT_END() > }; > > diff --git a/merge-ort.c b/merge-ort.c > index 3653725661..523577d71e 100644 > --- a/merge-ort.c > +++ b/merge-ort.c > @@ -48,6 +48,7 @@ > #include "tree.h" > #include "unpack-trees.h" > #include "xdiff-interface.h" > +#include "bulk-checkin.h" > > /* > * We have many arrays of size 3. Whenever we have such an array, the > @@ -2108,10 +2109,19 @@ static int handle_content_merge(struct merge_options *opt, > if ((merge_status < 0) || !result_buf.ptr) > ret = error(_("failed to execute internal merge")); > > - if (!ret && > - write_object_file(result_buf.ptr, result_buf.size, > - OBJ_BLOB, &result->oid)) > - ret = error(_("unable to add %s to database"), path); > + if (!ret) { > + ret = opt->write_pack > + ? index_blob_bulk_checkin_incore(&result->oid, > + result_buf.ptr, > + result_buf.size, > + path, 1) > + : write_object_file(result_buf.ptr, > + result_buf.size, > + OBJ_BLOB, &result->oid); > + if (ret) > + ret = error(_("unable to add %s to database"), > + path); > + } > > free(result_buf.ptr); > if (ret) > @@ -3597,7 +3607,8 @@ static int tree_entry_order(const void *a_, const void *b_) > b->string, strlen(b->string), bmi->result.mode); > } > > -static int write_tree(struct object_id *result_oid, > +static int write_tree(struct merge_options *opt, > + struct object_id *result_oid, > struct string_list *versions, > unsigned int offset, > size_t hash_size) > @@ -3631,8 +3642,14 @@ static int write_tree(struct object_id *result_oid, > } > > /* Write this object file out, and record in result_oid */ > - if (write_object_file(buf.buf, buf.len, OBJ_TREE, result_oid)) > + ret = opt->write_pack > + ? index_tree_bulk_checkin_incore(result_oid, > + buf.buf, buf.len, "", 1) > + : write_object_file(buf.buf, buf.len, OBJ_TREE, result_oid); > + > + if (ret) > ret = -1; > + > strbuf_release(&buf); > return ret; > } > @@ -3797,8 +3814,8 @@ static int write_completed_directory(struct merge_options *opt, > */ > dir_info->is_null = 0; > dir_info->result.mode = S_IFDIR; > - if (write_tree(&dir_info->result.oid, &info->versions, offset, > - opt->repo->hash_algo->rawsz) < 0) > + if (write_tree(opt, &dir_info->result.oid, &info->versions, > + offset, opt->repo->hash_algo->rawsz) < 0) > ret = -1; > } > > @@ -4332,9 +4349,13 @@ static int process_entries(struct merge_options *opt, > fflush(stdout); > BUG("dir_metadata accounting completely off; shouldn't happen"); > } > - if (write_tree(result_oid, &dir_metadata.versions, 0, > + if (write_tree(opt, result_oid, &dir_metadata.versions, 0, > opt->repo->hash_algo->rawsz) < 0) > ret = -1; > + > + if (opt->write_pack) > + end_odb_transaction(); > + > cleanup: > string_list_clear(&plist, 0); > string_list_clear(&dir_metadata.versions, 0); > @@ -4878,6 +4899,9 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) > */ > strmap_init(&opt->priv->conflicts); > > + if (opt->write_pack) > + begin_odb_transaction(); > + > trace2_region_leave("merge", "allocate/init", opt->repo); > } > > diff --git a/merge-recursive.h b/merge-recursive.h > index 3d3b3e3c29..5c5ff380a8 100644 > --- a/merge-recursive.h > +++ b/merge-recursive.h > @@ -48,6 +48,7 @@ struct merge_options { > unsigned renormalize : 1; > unsigned record_conflict_msgs_as_headers : 1; > const char *msg_header_prefix; > + unsigned write_pack : 1; > > /* internal fields used by the implementation */ > struct merge_options_internal *priv; > diff --git a/t/t4301-merge-tree-write-tree.sh b/t/t4301-merge-tree-write-tree.sh > index b2c8a43fce..d2a8634523 100755 > --- a/t/t4301-merge-tree-write-tree.sh > +++ b/t/t4301-merge-tree-write-tree.sh > @@ -945,4 +945,97 @@ test_expect_success 'check the input format when --stdin is passed' ' > test_cmp expect actual > ' > > +packdir=".git/objects/pack" > + > +test_expect_success 'merge-tree can pack its result with --write-pack' ' > + test_when_finished "rm -rf repo" && > + git init repo && > + > + # base has lines [3, 4, 5] > + # - side adds to the beginning, resulting in [1, 2, 3, 4, 5] > + # - other adds to the end, resulting in [3, 4, 5, 6, 7] > + # > + # merging the two should result in a new blob object containing > + # [1, 2, 3, 4, 5, 6, 7], along with a new tree. > + test_commit -C repo base file "$(test_seq 3 5)" && > + git -C repo branch -M main && > + git -C repo checkout -b side main && > + test_commit -C repo side file "$(test_seq 1 5)" && > + git -C repo checkout -b other main && > + test_commit -C repo other file "$(test_seq 3 7)" && > + > + find repo/$packdir -type f -name "pack-*.idx" >packs.before && > + tree="$(git -C repo merge-tree --write-pack \ > + refs/tags/side refs/tags/other)" && > + blob="$(git -C repo rev-parse $tree:file)" && > + find repo/$packdir -type f -name "pack-*.idx" >packs.after && While we do assert that we write a new packfile, we don't assert whether parts of the written object may have been written as loose objects. Do we want to tighten the checks to verify that? Patrick > + test_must_be_empty packs.before && > + test_line_count = 1 packs.after && > + > + git show-index <$(cat packs.after) >objects && > + test_line_count = 2 objects && > + grep "^[1-9][0-9]* $tree" objects && > + grep "^[1-9][0-9]* $blob" objects > +' > + > +test_expect_success 'merge-tree can write multiple packs with --write-pack' ' > + test_when_finished "rm -rf repo" && > + git init repo && > + ( > + cd repo && > + > + git config pack.packSizeLimit 512 && > + > + test_seq 512 >f && > + > + # "f" contains roughly ~2,000 bytes. > + # > + # Each side ("foo" and "bar") adds a small amount of data at the > + # beginning and end of "base", respectively. > + git add f && > + test_tick && > + git commit -m base && > + git branch -M main && > + > + git checkout -b foo main && > + { > + echo foo && cat f > + } >f.tmp && > + mv f.tmp f && > + git add f && > + test_tick && > + git commit -m foo && > + > + git checkout -b bar main && > + echo bar >>f && > + git add f && > + test_tick && > + git commit -m bar && > + > + find $packdir -type f -name "pack-*.idx" >packs.before && > + # Merging either side should result in a new object which is > + # larger than 1M, thus the result should be split into two > + # separate packs. > + tree="$(git merge-tree --write-pack \ > + refs/heads/foo refs/heads/bar)" && > + blob="$(git rev-parse $tree:f)" && > + find $packdir -type f -name "pack-*.idx" >packs.after && > + > + test_must_be_empty packs.before && > + test_line_count = 2 packs.after && > + for idx in $(cat packs.after) > + do > + git show-index <$idx || return 1 > + done >objects && > + > + # The resulting set of packs should contain one copy of both > + # objects, each in a separate pack. > + test_line_count = 2 objects && > + grep "^[1-9][0-9]* $tree" objects && > + grep "^[1-9][0-9]* $blob" objects > + > + ) > +' > + > test_done > -- > 2.42.0.425.g963d08ddb3.dirty
On Wed, Oct 25, 2023 at 09:58:11AM +0200, Patrick Steinhardt wrote: > > +test_expect_success 'merge-tree can pack its result with --write-pack' ' > > + test_when_finished "rm -rf repo" && > > + git init repo && > > + > > + # base has lines [3, 4, 5] > > + # - side adds to the beginning, resulting in [1, 2, 3, 4, 5] > > + # - other adds to the end, resulting in [3, 4, 5, 6, 7] > > + # > > + # merging the two should result in a new blob object containing > > + # [1, 2, 3, 4, 5, 6, 7], along with a new tree. > > + test_commit -C repo base file "$(test_seq 3 5)" && > > + git -C repo branch -M main && > > + git -C repo checkout -b side main && > > + test_commit -C repo side file "$(test_seq 1 5)" && > > + git -C repo checkout -b other main && > > + test_commit -C repo other file "$(test_seq 3 7)" && > > + > > + find repo/$packdir -type f -name "pack-*.idx" >packs.before && > > + tree="$(git -C repo merge-tree --write-pack \ > > + refs/tags/side refs/tags/other)" && > > + blob="$(git -C repo rev-parse $tree:file)" && > > + find repo/$packdir -type f -name "pack-*.idx" >packs.after && > > While we do assert that we write a new packfile, we don't assert whether > parts of the written object may have been written as loose objects. Do > we want to tighten the checks to verify that? We could, but the tests in t1050 already verify this, so I'm not sure that we would be significantly hardening our test coverage here. If you feel strongly about it, though, I'm happy to change it up. Thanks, Taylor
Hi, Sorry for taking so long to find some time to review. And sorry for the bad news, but... On Mon, Oct 23, 2023 at 3:45 PM Taylor Blau <me@ttaylorr.com> wrote: > > When using merge-tree often within a repository[^1], it is possible to > generate a relatively large number of loose objects, which can result in > degraded performance, and inode exhaustion in extreme cases. > > Building on the functionality introduced in previous commits, the > bulk-checkin machinery now has support to write arbitrary blob and tree > objects which are small enough to be held in-core. We can use this to > write any blob/tree objects generated by ORT into a separate pack > instead of writing them out individually as loose. > > This functionality is gated behind a new `--write-pack` option to > `merge-tree` that works with the (non-deprecated) `--write-tree` mode. > > The implementation is relatively straightforward. There are two spots > within the ORT mechanism where we call `write_object_file()`, one for > content differences within blobs, and another to assemble any new trees > necessary to construct the merge. In each of those locations, > conditionally replace calls to `write_object_file()` with > `index_blob_bulk_checkin_incore()` or `index_tree_bulk_checkin_incore()` > depending on which kind of object we are writing. > > The only remaining task is to begin and end the transaction necessary to > initialize the bulk-checkin machinery, and move any new pack(s) it > created into the main object store. I believe the above is built on an assumption that any objects written will not need to be read until after the merge is completed. And we might have a nesting issue too... > @@ -2108,10 +2109,19 @@ static int handle_content_merge(struct merge_options *opt, > if ((merge_status < 0) || !result_buf.ptr) > ret = error(_("failed to execute internal merge")); > > - if (!ret && > - write_object_file(result_buf.ptr, result_buf.size, > - OBJ_BLOB, &result->oid)) > - ret = error(_("unable to add %s to database"), path); > + if (!ret) { > + ret = opt->write_pack > + ? index_blob_bulk_checkin_incore(&result->oid, > + result_buf.ptr, > + result_buf.size, > + path, 1) > + : write_object_file(result_buf.ptr, > + result_buf.size, > + OBJ_BLOB, &result->oid); > + if (ret) > + ret = error(_("unable to add %s to database"), > + path); > + } > > free(result_buf.ptr); > if (ret) This is unsafe; the object may need to be read later within the same merge. Perhaps the simplest example related to your testcase is modifying the middle section of that testcase (I'll highlight where when I comment on the testcase) to read: test_commit -C repo base file "$(test_seq 3 5)" && git -C repo branch -M main && git -C repo checkout -b side main && test_commit -C repo side-file file "$(test_seq 1 5)" && test_commit -C repo side-file2 file2 "$(test_seq 1 6)" && git -C repo checkout -b other main && test_commit -C repo other-file file "$(test_seq 3 7)" && git -C repo mv file file2 && git -C repo commit -m other-file2 && find repo/$packdir -type f -name "pack-*.idx" >packs.before && git -C repo merge-tree --write-pack side other && In words, what I'm doing here is having both sides modify "file" (the same as you did) but also having one side rename "file"->"file2". The side that doesn't rename "file" also introduces a new "file2". ort needs to merge the three versions of "file" to get a new blob object, and then merge that with the content from the brand new "file2". More complicated cases are possible, of course. Anyway, with the modified testcase above, merge-tree will fail with: fatal: unable to read blob object 06e567b11dfdafeaf7d3edcc89864149383aeab6 I think (untested) that you could fix this by creating two packs instead of just one. In particular, add a call to flush_odb_transcation() after the "redo_after_renames" block in merge_ort_nonrecursive_internal(). (It's probably easier to see that you could place the flush_odb_transaction() call inside detect_and_process_renames() just after the process_renames() call, but when redo_after_renames is true you'd end up with three packs instead of just two). What happens with the odb transaction stuff if no new objects are written before the call to flush_odb_transaction? Will that be a problem? (Since any tree written will not be re-read within the same merge, the other write_object_file() call you changed does not have the same problem as the one here.) >@@ -4332,9 +4349,13 @@ static int process_entries(struct merge_options *opt, > fflush(stdout); > BUG("dir_metadata accounting completely off; shouldn't happen"); > } >- if (write_tree(result_oid, &dir_metadata.versions, 0, >+ if (write_tree(opt, result_oid, &dir_metadata.versions, 0, > opt->repo->hash_algo->rawsz) < 0) > ret = -1; > > + > + if (opt->write_pack) > + end_odb_transaction(); > + Is the end_odb_transaction() here going to fail with an "Unbalanced ODB transaction nesting" when faced with a recursive merge? Perhaps flushing here, and then calling end_odb_transaction() in merge_finalize(), much as you do in your replay-and-write-pack series, should actually be moved to this commit and included here? This does mean that for a recursive merge, that you'll get up to 2*N packfiles, where N is the depth of the recursive merge. > + test_commit -C repo base file "$(test_seq 3 5)" && > + git -C repo branch -M main && > + git -C repo checkout -b side main && > + test_commit -C repo side file "$(test_seq 1 5)" && > + git -C repo checkout -b other main && > + test_commit -C repo other file "$(test_seq 3 7)" && > + > + find repo/$packdir -type f -name "pack-*.idx" >packs.before && > + tree="$(git -C repo merge-tree --write-pack \ > + refs/tags/side refs/tags/other)" && These were the lines from your testcase that I replaced to show the bug.
Elijah Newren <newren@gmail.com> writes: > I believe the above is built on an assumption that any objects written > will not need to be read until after the merge is completed. And we > might have a nesting issue too... > ... > This is unsafe; the object may need to be read later within the same > merge. Thanks for a good analysis. I agree.
On Fri, Nov 10, 2023 at 03:51:18PM -0800, Elijah Newren wrote: > > @@ -2108,10 +2109,19 @@ static int handle_content_merge(struct merge_options *opt, > > if ((merge_status < 0) || !result_buf.ptr) > > ret = error(_("failed to execute internal merge")); > > > > - if (!ret && > > - write_object_file(result_buf.ptr, result_buf.size, > > - OBJ_BLOB, &result->oid)) > > - ret = error(_("unable to add %s to database"), path); > > + if (!ret) { > > + ret = opt->write_pack > > + ? index_blob_bulk_checkin_incore(&result->oid, > > + result_buf.ptr, > > + result_buf.size, > > + path, 1) > > + : write_object_file(result_buf.ptr, > > + result_buf.size, > > + OBJ_BLOB, &result->oid); > > + if (ret) > > + ret = error(_("unable to add %s to database"), > > + path); > > + } > > > > free(result_buf.ptr); > > if (ret) > > This is unsafe; the object may need to be read later within the same > merge. Perhaps the simplest example related to your testcase is > modifying the middle section of that testcase (I'll highlight where > when I comment on the testcase) to read: > > test_commit -C repo base file "$(test_seq 3 5)" && > git -C repo branch -M main && > git -C repo checkout -b side main && > test_commit -C repo side-file file "$(test_seq 1 5)" && > test_commit -C repo side-file2 file2 "$(test_seq 1 6)" && > git -C repo checkout -b other main && > test_commit -C repo other-file file "$(test_seq 3 7)" && > git -C repo mv file file2 && > git -C repo commit -m other-file2 && > > find repo/$packdir -type f -name "pack-*.idx" >packs.before && > git -C repo merge-tree --write-pack side other && > > In words, what I'm doing here is having both sides modify "file" (the > same as you did) but also having one side rename "file"->"file2". The > side that doesn't rename "file" also introduces a new "file2". ort > needs to merge the three versions of "file" to get a new blob object, > and then merge that with the content from the brand new "file2". More > complicated cases are possible, of course. Anyway, with the modified > testcase above, merge-tree will fail with: > > fatal: unable to read blob object 06e567b11dfdafeaf7d3edcc89864149383aeab6 > > I think (untested) that you could fix this by creating two packs > instead of just one. In particular, add a call to > flush_odb_transcation() after the "redo_after_renames" block in > merge_ort_nonrecursive_internal(). (It's probably easier to see that > you could place the flush_odb_transaction() call inside > detect_and_process_renames() just after the process_renames() call, > but when redo_after_renames is true you'd end up with three packs > instead of just two). Great analysis, thanks for catching this error. I tested your approach, and indeed a flush_odb_transaction() call after the process_renames() call in detect_and_process_renames() does do the trick. > What happens with the odb transaction stuff if no new objects are > written before the call to flush_odb_transaction? Will that be a > problem? I think that the bulk-checkin code is flexible enough to understand that we shouldn't do anything when there aren't any objects to pack. > (Since any tree written will not be re-read within the same merge, the > other write_object_file() call you changed does not have the same > problem as the one here.) > > >@@ -4332,9 +4349,13 @@ static int process_entries(struct merge_options *opt, > > fflush(stdout); > > BUG("dir_metadata accounting completely off; shouldn't happen"); > > } > >- if (write_tree(result_oid, &dir_metadata.versions, 0, > >+ if (write_tree(opt, result_oid, &dir_metadata.versions, 0, > > opt->repo->hash_algo->rawsz) < 0) > > ret = -1; > > > > + > > + if (opt->write_pack) > > + end_odb_transaction(); > > + > > Is the end_odb_transaction() here going to fail with an "Unbalanced > ODB transaction nesting" when faced with a recursive merge? I think so, and we should have a test-case demonstrating that. In the remaining three patches that I posted to extend this approach to 'git replay', I moved this call elsewhere in such a way that I think > Perhaps flushing here, and then calling end_odb_transaction() in > merge_finalize(), much as you do in your replay-and-write-pack series, > should actually be moved to this commit and included here? Yep, exactly. > This does mean that for a recursive merge, that you'll get up to 2*N > packfiles, where N is the depth of the recursive merge. We definitely want to avoid that ;-). I think there are a couple of potential directions forward here, but the most promising one I think is due to Johannes who suggests that we write loose objects into a temporary directory with a replace_tmp_objdir() call, and then repack that side directory before migrating a single pack back into the main object store. Thanks, eaylor
On Sat, Nov 11, 2023 at 09:27:42AM +0900, Junio C Hamano wrote: > Elijah Newren <newren@gmail.com> writes: > > > I believe the above is built on an assumption that any objects written > > will not need to be read until after the merge is completed. And we > > might have a nesting issue too... > > ... > > This is unsafe; the object may need to be read later within the same > > merge. > > Thanks for a good analysis. I agree. Ditto. I responded to Elijah more in-depth elsewhere in the thread, but I think for your purposes it is OK to discard this series. Thanks, Taylor
On Fri, Nov 10, 2023 at 03:51:18PM -0800, Elijah Newren wrote: > This is unsafe; the object may need to be read later within the same > merge. [...] > > I think (untested) that you could fix this by creating two packs > instead of just one. In particular, add a call to > flush_odb_transcation() after the "redo_after_renames" block in > merge_ort_nonrecursive_internal(). It might not be too hard to just let in-process callers access the objects we've written. A quick and dirty patch is below, which works with the test you suggested (the test still fails because it finds a conflict, but it gets past the "woah, I can't find that sha1" part). I don't know if that is sufficient, though. Would other spawned processes (hooks, external merge drivers, and so on) need to be able to see these objects, too? The patch teaches the packfile code about the special bulk checkin pack. It might be cleaner to invert it, and just have the bulk checkin code register a magic packed_git (it would need to fake the .idx somehow). diff --git a/bulk-checkin.c b/bulk-checkin.c index bd6151ba3c..566fc36e68 100644 --- a/bulk-checkin.c +++ b/bulk-checkin.c @@ -30,6 +30,8 @@ static struct bulk_checkin_packfile { struct pack_idx_entry **written; uint32_t alloc_written; uint32_t nr_written; + + struct packed_git *fake_packed_git; } bulk_checkin_packfile; static void finish_tmp_packfile(struct strbuf *basename, @@ -82,6 +84,7 @@ static void flush_bulk_checkin_packfile(struct bulk_checkin_packfile *state) clear_exit: free(state->written); + free(state->fake_packed_git); memset(state, 0, sizeof(*state)); strbuf_release(&packname); @@ -530,3 +533,37 @@ void end_odb_transaction(void) flush_odb_transaction(); } + +static struct packed_git *fake_packed_git(struct bulk_checkin_packfile *state) +{ + struct packed_git *p = state->fake_packed_git; + if (!p) { + FLEX_ALLOC_STR(p, pack_name, "/fake/in-progress.pack"); + state->fake_packed_git = p; + p->pack_fd = state->f->fd; + p->do_not_close = 1; + } + + hashflush(state->f); + p->pack_size = state->f->total; /* maybe add 20 to simulate trailer? */ + + return p; +} + +int bulk_checkin_pack_entry(const struct object_id *oid, struct pack_entry *e) +{ + size_t i; + /* + * this really ought to have some more efficient data structure for + * lookup; ditto for the existing already_written() + */ + for (i = 0; i < bulk_checkin_packfile.nr_written; i++) { + struct pack_idx_entry *p = bulk_checkin_packfile.written[i]; + if (oideq(&p->oid, oid)) { + e->p = fake_packed_git(&bulk_checkin_packfile); + e->offset = p->offset; + return 0; + } + } + return -1; +} diff --git a/bulk-checkin.h b/bulk-checkin.h index 89786b3954..153fe87c06 100644 --- a/bulk-checkin.h +++ b/bulk-checkin.h @@ -44,4 +44,7 @@ void flush_odb_transaction(void); */ void end_odb_transaction(void); +struct pack_entry; +int bulk_checkin_pack_entry(const struct object_id *oid, struct pack_entry *e); + #endif diff --git a/packfile.c b/packfile.c index 9cc0a2e37a..05194b1d9b 100644 --- a/packfile.c +++ b/packfile.c @@ -23,6 +23,7 @@ #include "commit-graph.h" #include "pack-revindex.h" #include "promisor-remote.h" +#include "bulk-checkin.h" char *odb_pack_name(struct strbuf *buf, const unsigned char *hash, @@ -2045,6 +2046,9 @@ int find_pack_entry(struct repository *r, const struct object_id *oid, struct pa struct list_head *pos; struct multi_pack_index *m; + if (!bulk_checkin_pack_entry(oid, e)) + return 1; + prepare_packed_git(r); if (!r->objects->packed_git && !r->objects->multi_pack_index) return 0;
On Fri, Nov 10, 2023 at 08:24:44PM -0500, Taylor Blau wrote: > > This does mean that for a recursive merge, that you'll get up to 2*N > > packfiles, where N is the depth of the recursive merge. > > We definitely want to avoid that ;-). I think there are a couple of > potential directions forward here, but the most promising one I think is > due to Johannes who suggests that we write loose objects into a > temporary directory with a replace_tmp_objdir() call, and then repack > that side directory before migrating a single pack back into the main > object store. I posted an alternative in response to Elijah; the general idea being to allow the usual object-lookup code to access the in-progress pack. That would keep us limited to a single pack. It _might_ be a terrible idea. E.g., if you write a non-bulk object that references a bulk one, then that non-bulk one is broken from the perspective of other processes (until the bulk checkin is flushed). But I think we'd always be writing to one or the other here, never interleaving? -Peff
On Mon, Nov 13, 2023 at 05:02:54PM -0500, Jeff King wrote: > On Fri, Nov 10, 2023 at 03:51:18PM -0800, Elijah Newren wrote: > > > This is unsafe; the object may need to be read later within the same > > merge. [...] > > > > I think (untested) that you could fix this by creating two packs > > instead of just one. In particular, add a call to > > flush_odb_transcation() after the "redo_after_renames" block in > > merge_ort_nonrecursive_internal(). > > It might not be too hard to just let in-process callers access the > objects we've written. A quick and dirty patch is below, which works > with the test you suggested (the test still fails because it finds a > conflict, but it gets past the "woah, I can't find that sha1" part). That's a very slick idea, and I think that this series has some legs to stand on now as a result. There are a few of interesting conclusions we can draw here: 1. This solves the recursive merge problem that Elijah mentioned earlier where we could generate up to 2^N packs (where N is the maximum depth of the recursive merge). 2. This also solves the case where the merge-ort code needs to read an object that it wrote earlier on in the same process without having to flush out intermediate packs. So in the best case we need only a single pack (instead of two). 3. This also solves the 'replay' issue, *and* allows us to avoid the tmp-objdir thing there entirely, since we can simulate object reads in the bulk-checkin pack. So I think that this is a direction worth pursuing. In terms of making those lookups faster, I think that what you'd want is an oidmap. The overhead is slightly unfortunate, but I think that any other solution which requires keeping the written array in sorted order would in practice be more expensive as you have to constantly reallocate and copy portions of the array around to maintain its invariant. > I don't know if that is sufficient, though. Would other spawned > processes (hooks, external merge drivers, and so on) need to be able to > see these objects, too? Interesting point. In theory those processes could ask about newly created objects, and if they were spawned before the bulk-checkin pack was flushed, those lookups would fail. But that requires that, e.g. for hooks, that we know a-priori the object ID of some newly-written objects. If you wanted to make those lookups succeed, I think there are a couple of options: - teach child-processes about the bulk-checkin pack, and let them perform the same fake lookup - flush (but do not close) the bulk-checkin transaction In any event, I think that this is a sufficiently rare and niche case that we'd be OK to declare that you should not expect the above scenarios to work when using `--write-pack`. If someone does ask for that feature in the future, we could implement it relatively painlessly using one of the above options. Thanks, Taylor
Jeff King <peff@peff.net> writes: > I posted an alternative in response to Elijah; the general idea being to > allow the usual object-lookup code to access the in-progress pack. That > would keep us limited to a single pack. If such a mechanism is done in a generic way, would we be able to simplify fast-import a lot, I wonder? IIRC, it had quite a lot of code to remember what it has written to its output to work around the exact issue your alternative tries to solve. In fact, maybe we could make fast-import a thin wrapper around the bulk checkin infrastructure?
On Mon, Nov 13, 2023 at 2:34 PM Taylor Blau <me@ttaylorr.com> wrote: > > On Mon, Nov 13, 2023 at 05:02:54PM -0500, Jeff King wrote: > > On Fri, Nov 10, 2023 at 03:51:18PM -0800, Elijah Newren wrote: > > > > > This is unsafe; the object may need to be read later within the same > > > merge. [...] > > > > > > I think (untested) that you could fix this by creating two packs > > > instead of just one. In particular, add a call to > > > flush_odb_transcation() after the "redo_after_renames" block in > > > merge_ort_nonrecursive_internal(). > > > > It might not be too hard to just let in-process callers access the > > objects we've written. A quick and dirty patch is below, which works > > with the test you suggested (the test still fails because it finds a > > conflict, but it gets past the "woah, I can't find that sha1" part). > > That's a very slick idea, and I think that this series has some legs to > stand on now as a result. > > There are a few of interesting conclusions we can draw here: > > 1. This solves the recursive merge problem that Elijah mentioned > earlier where we could generate up to 2^N packs (where N is the > maximum depth of the recursive merge). > > 2. This also solves the case where the merge-ort code needs to read an > object that it wrote earlier on in the same process without having > to flush out intermediate packs. So in the best case we need only a > single pack (instead of two). > > 3. This also solves the 'replay' issue, *and* allows us to avoid the > tmp-objdir thing there entirely, since we can simulate object reads > in the bulk-checkin pack. > > So I think that this is a direction worth pursuing. Agreed; this looks great. It's basically bringing fast-import-like functionality -- writing objects to a single new packfile while making previous objects accessible to subsequent ones -- to additional callers. > In terms of making those lookups faster, I think that what you'd want is > an oidmap. The overhead is slightly unfortunate, but I think that any > other solution which requires keeping the written array in sorted order > would in practice be more expensive as you have to constantly reallocate > and copy portions of the array around to maintain its invariant. When comparing the overhead of an oidmap to a bunch of inodes, however, it seems relatively cheap. :-) > > I don't know if that is sufficient, though. Would other spawned > > processes (hooks, external merge drivers, and so on) need to be able to > > see these objects, too? > > Interesting point. In theory those processes could ask about newly > created objects, and if they were spawned before the bulk-checkin pack > was flushed, those lookups would fail. One of the big design differences that I was pushing really hard with git-replay was performance and things that came with it -- no worktree, no per-commit hooks (which are nearly ruled out by no worktree, but it's still worth calling out separately), etc. A post-operation hook could be fine, but would also not get to assume a worktree. merge-tree is the same as far as hooks; I'd rather just not have them, but if we did, they'd be a post-operation hook. In both cases, that makes hooks not much of a sticking point. External merge drivers, however... > But that requires that, e.g. for hooks, that we know a-priori the object > ID of some newly-written objects. If you wanted to make those lookups > succeed, I think there are a couple of options: > > - teach child-processes about the bulk-checkin pack, and let them > perform the same fake lookup > > - flush (but do not close) the bulk-checkin transaction > > In any event, I think that this is a sufficiently rare and niche case > that we'd be OK to declare that you should not expect the above > scenarios to work when using `--write-pack`. If someone does ask for > that feature in the future, we could implement it relatively painlessly > using one of the above options. Seems reasonable to me.
On Mon, Nov 13, 2023 at 5:41 PM Junio C Hamano <gitster@pobox.com> wrote: > > Jeff King <peff@peff.net> writes: > > > I posted an alternative in response to Elijah; the general idea being to > > allow the usual object-lookup code to access the in-progress pack. That > > would keep us limited to a single pack. > > If such a mechanism is done in a generic way, would we be able to > simplify fast-import a lot, I wonder? IIRC, it had quite a lot of > code to remember what it has written to its output to work around > the exact issue your alternative tries to solve. In fact, maybe we > could make fast-import a thin wrapper around the bulk checkin > infrastructure? fast-import also attempts to delta objects against previous ones as it writes them to the pack. That's one thing still lacking from this solution, but aside from that, it also sounds to me like the bulk checkin infrastructure is getting closer to becoming a replacement for much of the fast-import code.
On Mon, Nov 13, 2023 at 2:05 PM Jeff King <peff@peff.net> wrote: > > On Fri, Nov 10, 2023 at 08:24:44PM -0500, Taylor Blau wrote: > > > > This does mean that for a recursive merge, that you'll get up to 2*N > > > packfiles, where N is the depth of the recursive merge. > > > > We definitely want to avoid that ;-). I think there are a couple of > > potential directions forward here, but the most promising one I think is > > due to Johannes who suggests that we write loose objects into a > > temporary directory with a replace_tmp_objdir() call, and then repack > > that side directory before migrating a single pack back into the main > > object store. > > I posted an alternative in response to Elijah; the general idea being to > allow the usual object-lookup code to access the in-progress pack. That > would keep us limited to a single pack. > > It _might_ be a terrible idea. E.g., if you write a non-bulk object that > references a bulk one, then that non-bulk one is broken from the > perspective of other processes (until the bulk checkin is flushed). But > I think we'd always be writing to one or the other here, never > interleaving? I think it sounds like a really cool idea, personally. I also don't see why any current uses would result in interleaving. fast-import's created pack has the same kind of restriction...and has even grown some extensions to work around the need for early access. In particular, it has a `checkpoint` feature for flushing the current pack and starting a new one, and also gained the `cat-blob` command for when folks really wanted to access an object without writing out the whole packfile. So, _if_ the need for early access arises, we have some prior art to look to for ways to provide it.
On Mon, Nov 13, 2023 at 06:50:08PM -0800, Elijah Newren wrote: > merge-tree is the same as far as hooks; I'd rather just not have them, > but if we did, they'd be a post-operation hook. > > In both cases, that makes hooks not much of a sticking point. > > External merge drivers, however... I suspect external merge drivers are OK, in the sense that they should not be looking up arbitrary objects anyway. We should hand the driver what it needs via tempfiles, etc. That said, I'm also OK with the notion that "--write-pack" is optional, and if some features don't work with it, that's OK. It's nice if we can flag that explicitly (rather than having things break in weird and subtle ways), but I think we might not even know about an implicit assumption until somebody runs across it in practice. -Peff
On Tue, Nov 14, 2023 at 10:40:58AM +0900, Junio C Hamano wrote: > Jeff King <peff@peff.net> writes: > > > I posted an alternative in response to Elijah; the general idea being to > > allow the usual object-lookup code to access the in-progress pack. That > > would keep us limited to a single pack. > > If such a mechanism is done in a generic way, would we be able to > simplify fast-import a lot, I wonder? IIRC, it had quite a lot of > code to remember what it has written to its output to work around > the exact issue your alternative tries to solve. In fact, maybe we > could make fast-import a thin wrapper around the bulk checkin > infrastructure? I suspect that the implementation could be shared with fast-import. I'm not sure it would save all that much code, though. There's a lot going on in fast-import besides keeping track of which objects we wrote into a pack. ;) The bigger issue, though, is that fast-import does generate some deltas and the bulk checkin code does not. And I'm not sure how the bulk checkin interface would expose that API (you need the caller to say "...and I suspect this object might be a good delta base"). -Peff
On Mon, Nov 13, 2023 at 05:34:42PM -0500, Taylor Blau wrote: > > It might not be too hard to just let in-process callers access the > > objects we've written. A quick and dirty patch is below, which works > > with the test you suggested (the test still fails because it finds a > > conflict, but it gets past the "woah, I can't find that sha1" part). > > That's a very slick idea, and I think that this series has some legs to > stand on now as a result. I'm glad people seem to like it. ;) I was mostly throwing it out there as an illustration, and I don't plan on polishing it up further. But in case somebody else wants to work on it, here are random extra thoughts on the topic: - rather than teach packfile.c about bulk checkin, I think it might be cleaner to let packed_git structs have a function pointer for accessing the index (and if NULL, naturally we'd open the .idx file in the usual way). And then bulk checkin could just register the "fake" packed_git - the flip side, though, is: would it be weird for other parts of the code to ever see the fake bulk packed_git in the list? It doesn't represent a real packfile the way the other ones do. So maybe it is better to keep it separate - I suspect this scheme may violate some bounds-checking of the packfiles. For example, we haven't written the hashfile trailer yet in the still-open packfile. But I think use_pack() assumes we always have an extra the_hash_algo->rawsz bytes of padding at the end. I'm not sure if that would ever cause us to accidentally read past the end of the file. - as you mentioned, an oidmap would be an obvious replacement for the existing unsorted list - the existing already_written() function faces the same problem. I don't think anybody cared because we'd usually only bulk checkin a few huge objects. But with --write-pack, we might write a lot of such objects, and the linear scan in already_written() makes it accidentally quadratic. - speaking of already_written(): it calls repo_has_object_file() to see if we can elide the write. It probably should be using freshen_*_object() in the usual way. Again, this is an existing bug but I suspect nobody noticed because the bulk checkin code path hardly ever kicks in. -Peff
diff --git a/Documentation/git-merge-tree.txt b/Documentation/git-merge-tree.txt index ffc4fbf7e8..9d37609ef1 100644 --- a/Documentation/git-merge-tree.txt +++ b/Documentation/git-merge-tree.txt @@ -69,6 +69,10 @@ OPTIONS specify a merge-base for the merge, and specifying multiple bases is currently not supported. This option is incompatible with `--stdin`. +--write-pack:: + Write any new objects into a separate packfile instead of as + individual loose objects. + [[OUTPUT]] OUTPUT ------ diff --git a/builtin/merge-tree.c b/builtin/merge-tree.c index a35e0452d6..218442ac9b 100644 --- a/builtin/merge-tree.c +++ b/builtin/merge-tree.c @@ -19,6 +19,7 @@ #include "tree.h" #include "config.h" #include "strvec.h" +#include "bulk-checkin.h" static int line_termination = '\n'; @@ -416,6 +417,7 @@ struct merge_tree_options { int name_only; int use_stdin; struct merge_options merge_options; + int write_pack; }; static int real_merge(struct merge_tree_options *o, @@ -441,6 +443,7 @@ static int real_merge(struct merge_tree_options *o, _("not something we can merge")); opt.show_rename_progress = 0; + opt.write_pack = o->write_pack; opt.branch1 = branch1; opt.branch2 = branch2; @@ -553,6 +556,8 @@ int cmd_merge_tree(int argc, const char **argv, const char *prefix) N_("specify a merge-base for the merge")), OPT_STRVEC('X', "strategy-option", &xopts, N_("option=value"), N_("option for selected merge strategy")), + OPT_BOOL(0, "write-pack", &o.write_pack, + N_("write new objects to a pack instead of as loose")), OPT_END() }; diff --git a/merge-ort.c b/merge-ort.c index 3653725661..523577d71e 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -48,6 +48,7 @@ #include "tree.h" #include "unpack-trees.h" #include "xdiff-interface.h" +#include "bulk-checkin.h" /* * We have many arrays of size 3. Whenever we have such an array, the @@ -2108,10 +2109,19 @@ static int handle_content_merge(struct merge_options *opt, if ((merge_status < 0) || !result_buf.ptr) ret = error(_("failed to execute internal merge")); - if (!ret && - write_object_file(result_buf.ptr, result_buf.size, - OBJ_BLOB, &result->oid)) - ret = error(_("unable to add %s to database"), path); + if (!ret) { + ret = opt->write_pack + ? index_blob_bulk_checkin_incore(&result->oid, + result_buf.ptr, + result_buf.size, + path, 1) + : write_object_file(result_buf.ptr, + result_buf.size, + OBJ_BLOB, &result->oid); + if (ret) + ret = error(_("unable to add %s to database"), + path); + } free(result_buf.ptr); if (ret) @@ -3597,7 +3607,8 @@ static int tree_entry_order(const void *a_, const void *b_) b->string, strlen(b->string), bmi->result.mode); } -static int write_tree(struct object_id *result_oid, +static int write_tree(struct merge_options *opt, + struct object_id *result_oid, struct string_list *versions, unsigned int offset, size_t hash_size) @@ -3631,8 +3642,14 @@ static int write_tree(struct object_id *result_oid, } /* Write this object file out, and record in result_oid */ - if (write_object_file(buf.buf, buf.len, OBJ_TREE, result_oid)) + ret = opt->write_pack + ? index_tree_bulk_checkin_incore(result_oid, + buf.buf, buf.len, "", 1) + : write_object_file(buf.buf, buf.len, OBJ_TREE, result_oid); + + if (ret) ret = -1; + strbuf_release(&buf); return ret; } @@ -3797,8 +3814,8 @@ static int write_completed_directory(struct merge_options *opt, */ dir_info->is_null = 0; dir_info->result.mode = S_IFDIR; - if (write_tree(&dir_info->result.oid, &info->versions, offset, - opt->repo->hash_algo->rawsz) < 0) + if (write_tree(opt, &dir_info->result.oid, &info->versions, + offset, opt->repo->hash_algo->rawsz) < 0) ret = -1; } @@ -4332,9 +4349,13 @@ static int process_entries(struct merge_options *opt, fflush(stdout); BUG("dir_metadata accounting completely off; shouldn't happen"); } - if (write_tree(result_oid, &dir_metadata.versions, 0, + if (write_tree(opt, result_oid, &dir_metadata.versions, 0, opt->repo->hash_algo->rawsz) < 0) ret = -1; + + if (opt->write_pack) + end_odb_transaction(); + cleanup: string_list_clear(&plist, 0); string_list_clear(&dir_metadata.versions, 0); @@ -4878,6 +4899,9 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) */ strmap_init(&opt->priv->conflicts); + if (opt->write_pack) + begin_odb_transaction(); + trace2_region_leave("merge", "allocate/init", opt->repo); } diff --git a/merge-recursive.h b/merge-recursive.h index 3d3b3e3c29..5c5ff380a8 100644 --- a/merge-recursive.h +++ b/merge-recursive.h @@ -48,6 +48,7 @@ struct merge_options { unsigned renormalize : 1; unsigned record_conflict_msgs_as_headers : 1; const char *msg_header_prefix; + unsigned write_pack : 1; /* internal fields used by the implementation */ struct merge_options_internal *priv; diff --git a/t/t4301-merge-tree-write-tree.sh b/t/t4301-merge-tree-write-tree.sh index b2c8a43fce..d2a8634523 100755 --- a/t/t4301-merge-tree-write-tree.sh +++ b/t/t4301-merge-tree-write-tree.sh @@ -945,4 +945,97 @@ test_expect_success 'check the input format when --stdin is passed' ' test_cmp expect actual ' +packdir=".git/objects/pack" + +test_expect_success 'merge-tree can pack its result with --write-pack' ' + test_when_finished "rm -rf repo" && + git init repo && + + # base has lines [3, 4, 5] + # - side adds to the beginning, resulting in [1, 2, 3, 4, 5] + # - other adds to the end, resulting in [3, 4, 5, 6, 7] + # + # merging the two should result in a new blob object containing + # [1, 2, 3, 4, 5, 6, 7], along with a new tree. + test_commit -C repo base file "$(test_seq 3 5)" && + git -C repo branch -M main && + git -C repo checkout -b side main && + test_commit -C repo side file "$(test_seq 1 5)" && + git -C repo checkout -b other main && + test_commit -C repo other file "$(test_seq 3 7)" && + + find repo/$packdir -type f -name "pack-*.idx" >packs.before && + tree="$(git -C repo merge-tree --write-pack \ + refs/tags/side refs/tags/other)" && + blob="$(git -C repo rev-parse $tree:file)" && + find repo/$packdir -type f -name "pack-*.idx" >packs.after && + + test_must_be_empty packs.before && + test_line_count = 1 packs.after && + + git show-index <$(cat packs.after) >objects && + test_line_count = 2 objects && + grep "^[1-9][0-9]* $tree" objects && + grep "^[1-9][0-9]* $blob" objects +' + +test_expect_success 'merge-tree can write multiple packs with --write-pack' ' + test_when_finished "rm -rf repo" && + git init repo && + ( + cd repo && + + git config pack.packSizeLimit 512 && + + test_seq 512 >f && + + # "f" contains roughly ~2,000 bytes. + # + # Each side ("foo" and "bar") adds a small amount of data at the + # beginning and end of "base", respectively. + git add f && + test_tick && + git commit -m base && + git branch -M main && + + git checkout -b foo main && + { + echo foo && cat f + } >f.tmp && + mv f.tmp f && + git add f && + test_tick && + git commit -m foo && + + git checkout -b bar main && + echo bar >>f && + git add f && + test_tick && + git commit -m bar && + + find $packdir -type f -name "pack-*.idx" >packs.before && + # Merging either side should result in a new object which is + # larger than 1M, thus the result should be split into two + # separate packs. + tree="$(git merge-tree --write-pack \ + refs/heads/foo refs/heads/bar)" && + blob="$(git rev-parse $tree:f)" && + find $packdir -type f -name "pack-*.idx" >packs.after && + + test_must_be_empty packs.before && + test_line_count = 2 packs.after && + for idx in $(cat packs.after) + do + git show-index <$idx || return 1 + done >objects && + + # The resulting set of packs should contain one copy of both + # objects, each in a separate pack. + test_line_count = 2 objects && + grep "^[1-9][0-9]* $tree" objects && + grep "^[1-9][0-9]* $blob" objects + + ) +' + test_done
When using merge-tree often within a repository[^1], it is possible to generate a relatively large number of loose objects, which can result in degraded performance, and inode exhaustion in extreme cases. Building on the functionality introduced in previous commits, the bulk-checkin machinery now has support to write arbitrary blob and tree objects which are small enough to be held in-core. We can use this to write any blob/tree objects generated by ORT into a separate pack instead of writing them out individually as loose. This functionality is gated behind a new `--write-pack` option to `merge-tree` that works with the (non-deprecated) `--write-tree` mode. The implementation is relatively straightforward. There are two spots within the ORT mechanism where we call `write_object_file()`, one for content differences within blobs, and another to assemble any new trees necessary to construct the merge. In each of those locations, conditionally replace calls to `write_object_file()` with `index_blob_bulk_checkin_incore()` or `index_tree_bulk_checkin_incore()` depending on which kind of object we are writing. The only remaining task is to begin and end the transaction necessary to initialize the bulk-checkin machinery, and move any new pack(s) it created into the main object store. [^1]: Such is the case at GitHub, where we run presumptive "test merges" on open pull requests to see whether or not we can light up the merge button green depending on whether or not the presumptive merge was conflicted. This is done in response to a number of user-initiated events, including viewing an open pull request whose last test merge is stale with respect to the current base and tip of the pull request. As a result, merge-tree can be run very frequently on large, active repositories. Signed-off-by: Taylor Blau <me@ttaylorr.com> --- Documentation/git-merge-tree.txt | 4 ++ builtin/merge-tree.c | 5 ++ merge-ort.c | 42 +++++++++++---- merge-recursive.h | 1 + t/t4301-merge-tree-write-tree.sh | 93 ++++++++++++++++++++++++++++++++ 5 files changed, 136 insertions(+), 9 deletions(-)