{"thread":{"id":"52795","subject":"[PATCH 0/13] combining object filters and bitmaps","startedAt":"2020-02-13T02:15:08Z","lastAt":"2020-02-18T21:23:42Z","messageCount":73,"participants":["Jeff King","Junio C Hamano","Taylor Blau","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":13},"messages":[{"id":"391633","messageId":"20200213021506.GA1124607@coredump.intra.peff.net","threadId":"52795","inReplyTo":null,"subject":"[PATCH 0/13] combining object filters and bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:15:06Z","receivedAt":"2020-02-13T02:15:08Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Partial clones are nice for saving bandwidth, but they can actually be\nmore expensive in CPU because many of the filters require the server to\ndo extra work to figure out which objects to send.\n\nIn particular, it's impossible for many filters to work with\nreachability bitmaps, because the bitmap result doesn't provide enough\ninformation. E.g., we can't evaluate a path-based sparse filter without\nactually walking the trees to find out which objects are referred to at\nwhich paths.\n\nBut in some cases the bitmaps _do_ give enough information, and it's\njust a weakness of our implementation. E.g., it's easy to remove all of\nthe blobs from a bitmap result. So this patch series implements some of\nthe easier filters, while providing a framework for the bitmap code to\nsay \"nope, that filter is too complex for me\" so we can fallback to a\nnon-bitmap path.\n\nOne thing I'm not wild about is that this basically creates a parallel\nuniverse of filter implementations, as nothing is shared with the\ncode in list-objects-filter.c (beyond the option parsing stage).\nBut if you look at the implementations in patches 11 and 12, I think\nthat's how it has to be in order to be efficient. The existing filters\nare inherently about hooking into the traversal, and the whole point of\nreachability bitmaps is to avoid that traversal.\n\nSo I think the best we can do is carefully write bitmap-aware versions\nof specific filters, and then fall back to a regular traversal as\nnecessary. I'd like to also give server providers some tools for\nlimiting which filters they're willing to support (so they can protect\nthemselves from people running expensive filters), but I've left that as\nfuture work for now.\n\nHere's an outline of the series:\n\n [01/13]: pack-bitmap: factor out type iterator initialization\n [02/13]: pack-bitmap: fix leak of haves/wants object lists\n\n Some related fixes and cleanups in the bitmap area.\n\n [03/13]: rev-list: fallback to non-bitmap traversal when filtering\n [04/13]: rev-list: consolidate bitmap-disabling options\n [05/13]: rev-list: factor out bitmap-optimized routines\n\n It's much easier to exercise this code via rev-list, so this is some\n refactoring around the bitmap support there.\n\n [06/13]: rev-list: make --count work with --objects\n [07/13]: rev-list: allow bitmaps when counting objects\n\n These two aren't strictly necessary for the topic at hand, but have\n been bugging me for years. And they were made simple by the earlier\n refactoring, and provide a handy test mechanism.\n\n [08/13]: pack-bitmap: basic noop bitmap filter infrastructure\n [09/13]: rev-list: use bitmap filters for traversal\n [10/13]: bitmap: add bitmap_unset() function\n\n More refactoring in preparation for supporting filters.\n\n [11/13]: pack-bitmap: implement BLOB_NONE filtering\n [12/13]: pack-bitmap: implement BLOB_LIMIT filtering\n\n Some actual filters (tested with rev-list support added earlier).\n\n [13/13]: pack-objects: support filters with bitmaps\n\n And finally turning on support for pack generation. The final\n numeric result is (using linux.git with blob:none):\n\n Test HEAD^ HEAD\n ------------------------------------------------------------------------------\n 5310.9: simulated partial clone 38.94(37.28+5.87) 11.06(11.27+4.07) -71.6%\n\n which isn't too shabby.\n\n builtin/pack-objects.c | 3 +-\n builtin/rev-list.c | 124 +++++++++++---\n ewah/bitmap.c | 8 +\n ewah/ewok.h | 1 +\n object.c | 9 ++\n object.h | 2 +\n pack-bitmap.c | 252 +++++++++++++++++++++++++----\n pack-bitmap.h | 4 +-\n reachable.c | 2 +-\n t/perf/p5310-pack-bitmaps.sh | 14 ++\n t/t5310-pack-bitmaps.sh | 20 +++\n t/t6000-rev-list-misc.sh | 12 ++\n t/t6113-rev-list-bitmap-filters.sh | 77 +++++++++\n 13 files changed, 468 insertions(+), 60 deletions(-)\n create mode 100755 t/t6113-rev-list-bitmap-filters.sh\n\n-Peff\n"},{"id":"391634","messageId":"20200213021615.GA1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 01/13] pack-bitmap: factor out type iterator initialization","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:16:15Z","receivedAt":"2020-02-13T02:16:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When count_object_type() wants to iterate over the bitmap of all objects\nof a certain type, we have to pair up OBJ_COMMIT with bitmap->commits,\nand so forth. Since we're about to add more code to iterate over these\nbitmaps, let's pull the initialization into its own function.\n\nWe can also use this to simplify traverse_bitmap_commit_list(). It\naccomplishes the same thing by manually passing the object type and the\nbitmap to show_objects_for_type(), but using our helper we just need the\nobject type.\n\nNote there's one small code change here: previously we'd simply return\nzero when counting an unknown object type, and now we'll BUG(). This\nshouldn't matter in practice, as all of the callers pass in only usual\ncommit/tree/blob/tag types.\n\nSigned-off-by: Jeff King \n---\n pack-bitmap.c | 63 +++++++++++++++++++++++++++------------------------\n 1 file changed, 33 insertions(+), 30 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex e07c798879..9ca356ee29 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -616,9 +616,35 @@ static void show_extended_objects(struct bitmap_index *bitmap_git,\n \t}\n }\n \n+static void init_type_iterator(struct ewah_iterator *it,\n+\t\t\t struct bitmap_index *bitmap_git,\n+\t\t\t enum object_type type)\n+{\n+\tswitch (type) {\n+\tcase OBJ_COMMIT:\n+\t\tewah_iterator_init(it, bitmap_git->commits);\n+\t\tbreak;\n+\n+\tcase OBJ_TREE:\n+\t\tewah_iterator_init(it, bitmap_git->trees);\n+\t\tbreak;\n+\n+\tcase OBJ_BLOB:\n+\t\tewah_iterator_init(it, bitmap_git->blobs);\n+\t\tbreak;\n+\n+\tcase OBJ_TAG:\n+\t\tewah_iterator_init(it, bitmap_git->tags);\n+\t\tbreak;\n+\n+\tdefault:\n+\t\tBUG(\"object type %d not stored by bitmap type index\", type);\n+\t\tbreak;\n+\t}\n+}\n+\n static void show_objects_for_type(\n \tstruct bitmap_index *bitmap_git,\n-\tstruct ewah_bitmap *type_filter,\n \tenum object_type object_type,\n \tshow_reachable_fn show_reach)\n {\n@@ -633,7 +659,7 @@ static void show_objects_for_type(\n \tif (bitmap_git->reuse_objects == bitmap_git->pack->num_objects)\n \t\treturn;\n \n-\tewah_iterator_init(&it, type_filter);\n+\tinit_type_iterator(&it, bitmap_git, object_type);\n \n \twhile (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {\n \t\teword_t word = objects->words[i] & filter;\n@@ -835,14 +861,10 @@ void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,\n {\n \tassert(bitmap_git->result);\n \n-\tshow_objects_for_type(bitmap_git, bitmap_git->commits,\n-\t\tOBJ_COMMIT, show_reachable);\n-\tshow_objects_for_type(bitmap_git, bitmap_git->trees,\n-\t\tOBJ_TREE, show_reachable);\n-\tshow_objects_for_type(bitmap_git, bitmap_git->blobs,\n-\t\tOBJ_BLOB, show_reachable);\n-\tshow_objects_for_type(bitmap_git, bitmap_git->tags,\n-\t\tOBJ_TAG, show_reachable);\n+\tshow_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable);\n+\tshow_objects_for_type(bitmap_git, OBJ_TREE, show_reachable);\n+\tshow_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable);\n+\tshow_objects_for_type(bitmap_git, OBJ_TAG, show_reachable);\n \n \tshow_extended_objects(bitmap_git, show_reachable);\n }\n@@ -857,26 +879,7 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git,\n \tstruct ewah_iterator it;\n \teword_t filter;\n \n-\tswitch (type) {\n-\tcase OBJ_COMMIT:\n-\t\tewah_iterator_init(&it, bitmap_git->commits);\n-\t\tbreak;\n-\n-\tcase OBJ_TREE:\n-\t\tewah_iterator_init(&it, bitmap_git->trees);\n-\t\tbreak;\n-\n-\tcase OBJ_BLOB:\n-\t\tewah_iterator_init(&it, bitmap_git->blobs);\n-\t\tbreak;\n-\n-\tcase OBJ_TAG:\n-\t\tewah_iterator_init(&it, bitmap_git->tags);\n-\t\tbreak;\n-\n-\tdefault:\n-\t\treturn 0;\n-\t}\n+\tinit_type_iterator(&it, bitmap_git, type);\n \n \twhile (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {\n \t\teword_t word = objects->words[i++] & filter;\n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391635","messageId":"20200213021633.GB1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 02/13] pack-bitmap: fix leak of haves/wants object lists","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:16:33Z","receivedAt":"2020-02-13T02:16:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we do a bitmap-aware revision traversal, we create an object_list\nfor each of the \"haves\" and \"wants\" tips. After creating the result\nbitmaps these are no longer needed or used, but we never free the list\nmemory.\n\nSigned-off-by: Jeff King \n---\n object.c | 9 +++++++++\n object.h | 2 ++\n pack-bitmap.c | 5 +++++\n 3 files changed, 16 insertions(+)\n\ndiff --git a/object.c b/object.c\nindex 142ef69399..4d11949b38 100644\n--- a/object.c\n+++ b/object.c\n@@ -307,6 +307,15 @@ int object_list_contains(struct object_list *list, struct object *obj)\n \treturn 0;\n }\n \n+void object_list_free(struct object_list **list)\n+{\n+\twhile (*list) {\n+\t\tstruct object_list *p = *list;\n+\t\t*list = p->next;\n+\t\tfree(p);\n+\t}\n+}\n+\n /*\n * A zero-length string to which object_array_entry::name can be\n * initialized without requiring a malloc/free.\ndiff --git a/object.h b/object.h\nindex 25f5ab3d54..2dbabfca0a 100644\n--- a/object.h\n+++ b/object.h\n@@ -151,6 +151,8 @@ struct object_list *object_list_insert(struct object *item,\n \n int object_list_contains(struct object_list *list, struct object *obj);\n \n+void object_list_free(struct object_list **list);\n+\n /* Object array handling .. */\n void add_object_array(struct object *obj, const char *name, struct object_array *array);\n void add_object_array_with_path(struct object *obj, const char *name, struct object_array *array, unsigned mode, const char *path);\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 9ca356ee29..6c06099dc7 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -787,10 +787,15 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \tbitmap_git->result = wants_bitmap;\n \tbitmap_git->haves = haves_bitmap;\n \n+\tobject_list_free(&wants);\n+\tobject_list_free(&haves);\n+\n \treturn bitmap_git;\n \n cleanup:\n \tfree_bitmap_index(bitmap_git);\n+\tobject_list_free(&wants);\n+\tobject_list_free(&haves);\n \treturn NULL;\n }\n \n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391636","messageId":"20200213021730.GC1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 03/13] rev-list: fallback to non-bitmap traversal when filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:17:30Z","receivedAt":"2020-02-13T02:17:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The \"--use-bitmap-index\" option is usually aspirational: if we have\nbitmaps and the request can be fulfilled more quickly using them we'll\ndo so, but otherwise fall back to a non-bitmap traversal.\n\nThe exception is object filtering, which explicitly dies if the two\noptions are combined. Let's convert this to the usual fallback behavior.\nThis is a minor convenience for now (since the caller can easily know\nthat --filter and --use-bitmap-index don't combine), but will become\nmuch more useful as we start to support _some_ filters with bitmaps, but\nnot others.\n\nThe test infrastructure here is bigger than necessary for checking this\none small feature. But it will serve as the basis for more filtering\nbitmap tests in future patches.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 4 ++--\n t/t6113-rev-list-bitmap-filters.sh | 24 ++++++++++++++++++++++++\n 2 files changed, 26 insertions(+), 2 deletions(-)\n create mode 100755 t/t6113-rev-list-bitmap-filters.sh\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex e28d62ec64..bce406bd1e 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -521,8 +521,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (revs.show_notes)\n \t\tdie(_(\"rev-list does not support display of notes\"));\n \n-\tif (filter_options.choice && use_bitmap_index)\n-\t\tdie(_(\"cannot combine --use-bitmap-index with object filtering\"));\n+\tif (filter_options.choice)\n+\t\tuse_bitmap_index = 0;\n \n \tsave_commit_buffer = (revs.verbose_header ||\n \t\t\t revs.grep_filter.pattern_list ||\ndiff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh\nnew file mode 100755\nindex 0000000000..977f8d0930\n--- /dev/null\n+++ b/t/t6113-rev-list-bitmap-filters.sh\n@@ -0,0 +1,24 @@\n+#!/bin/sh\n+\n+test_description='rev-list combining bitmaps and filters'\n+. ./test-lib.sh\n+\n+test_expect_success 'set up bitmapped repo' '\n+\t# one commit will have bitmaps, the other will not\n+\ttest_commit one &&\n+\tgit repack -adb &&\n+\ttest_commit two\n+'\n+\n+test_expect_success 'filters fallback to non-bitmap traversal' '\n+\t# use a path-based filter, since they are inherently incompatible with\n+\t# bitmaps (i.e., this test will never get confused by later code to\n+\t# combine the features)\n+\tfilter=$(echo \"!one\" | git hash-object -w --stdin) &&\n+\tgit rev-list --objects --filter=sparse:oid=$filter HEAD >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t --objects --filter=sparse:oid=$filter HEAD >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391637","messageId":"20200213021749.GD1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 04/13] rev-list: consolidate bitmap-disabling options","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:17:49Z","receivedAt":"2020-02-13T02:17:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"A few options are incompatible with bitmaps, like --filter or\npathspec-based pruning. Let's put these checks all up front, so that\nfurther code can trust the use_bitmap_index as the final word.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex bce406bd1e..9635b544e3 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -521,7 +521,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (revs.show_notes)\n \t\tdie(_(\"rev-list does not support display of notes\"));\n \n-\tif (filter_options.choice)\n+\tif (filter_options.choice || revs.prune)\n \t\tuse_bitmap_index = 0;\n \n \tsave_commit_buffer = (revs.verbose_header ||\n@@ -533,7 +533,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (show_progress)\n \t\tprogress = start_delayed_progress(show_progress, 0);\n \n-\tif (use_bitmap_index && !revs.prune) {\n+\tif (use_bitmap_index) {\n \t\tif (revs.count && !revs.left_right && !revs.cherry_mark) {\n \t\t\tuint32_t commit_count;\n \t\t\tint max_count = revs.max_count;\n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391638","messageId":"20200213021820.GE1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 05/13] rev-list: factor out bitmap-optimized routines","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:18:20Z","receivedAt":"2020-02-13T02:18:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There are a few operations in rev-list that are optimized for bitmaps.\nRather than having the code inline in cmd_rev_list(), let's move them\ninto helpers. This not only makes the flow of the main function simpler,\nbut it lets us replace the complex \"can we do the optimization?\"\nconditionals with a series of early returns from the functions. That\nalso makes it easy to add comments explaining those conditions.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 88 +++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 67 insertions(+), 21 deletions(-)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 9635b544e3..c2daf40449 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -364,6 +364,69 @@ static inline int parse_missing_action_value(const char *value)\n \treturn 0;\n }\n \n+static int try_bitmap_count(struct rev_info *revs)\n+{\n+\tuint32_t commit_count;\n+\tint max_count;\n+\tstruct bitmap_index *bitmap_git;\n+\n+\t/* This function only handles counting, not general traversal. */\n+\tif (!revs->count)\n+\t\treturn -1;\n+\n+\t/*\n+\t * A bitmap result can't know left/right, etc, because we don't\n+\t * actually traverse.\n+\t */\n+\tif (revs->left_right || revs->cherry_mark)\n+\t\treturn -1;\n+\n+\t/*\n+\t * This must be saved before doing any walking, since the revision\n+\t * machinery will count it down to zero while traversing.\n+\t */\n+\tmax_count = revs->max_count;\n+\n+\tbitmap_git = prepare_bitmap_walk(revs);\n+\tif (!bitmap_git)\n+\t\treturn -1;\n+\n+\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n+\tif (max_count >= 0 && max_count < commit_count)\n+\t\tcommit_count = max_count;\n+\n+\tprintf(\"%d\\n\", commit_count);\n+\tfree_bitmap_index(bitmap_git);\n+\treturn 0;\n+}\n+\n+static int try_bitmap_traversal(struct rev_info *revs)\n+{\n+\tstruct bitmap_index *bitmap_git;\n+\n+\t/*\n+\t * We can't use a bitmap result with a traversal limit, since the set\n+\t * of commits we'd get would be essentially random.\n+\t */\n+\tif (revs->max_count >= 0)\n+\t\treturn -1;\n+\n+\t/*\n+\t * Our bitmap result will return all objects, and we're not\n+\t * yet prepared to show only particular types.\n+\t */\n+\tif (!revs->tag_objects || !revs->tree_objects || !revs->blob_objects)\n+\t\treturn -1;\n+\n+\tbitmap_git = prepare_bitmap_walk(revs);\n+\tif (!bitmap_git)\n+\t\treturn -1;\n+\n+\ttraverse_bitmap_commit_list(bitmap_git, &show_object_fast);\n+\tfree_bitmap_index(bitmap_git);\n+\treturn 0;\n+}\n+\n int cmd_rev_list(int argc, const char **argv, const char *prefix)\n {\n \tstruct rev_info revs;\n@@ -534,27 +597,10 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\tprogress = start_delayed_progress(show_progress, 0);\n \n \tif (use_bitmap_index) {\n-\t\tif (revs.count && !revs.left_right && !revs.cherry_mark) {\n-\t\t\tuint32_t commit_count;\n-\t\t\tint max_count = revs.max_count;\n-\t\t\tstruct bitmap_index *bitmap_git;\n-\t\t\tif ((bitmap_git = prepare_bitmap_walk(&revs))) {\n-\t\t\t\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n-\t\t\t\tif (max_count >= 0 && max_count < commit_count)\n-\t\t\t\t\tcommit_count = max_count;\n-\t\t\t\tprintf(\"%d\\n\", commit_count);\n-\t\t\t\tfree_bitmap_index(bitmap_git);\n-\t\t\t\treturn 0;\n-\t\t\t}\n-\t\t} else if (revs.max_count < 0 &&\n-\t\t\t revs.tag_objects && revs.tree_objects && revs.blob_objects) {\n-\t\t\tstruct bitmap_index *bitmap_git;\n-\t\t\tif ((bitmap_git = prepare_bitmap_walk(&revs))) {\n-\t\t\t\ttraverse_bitmap_commit_list(bitmap_git, &show_object_fast);\n-\t\t\t\tfree_bitmap_index(bitmap_git);\n-\t\t\t\treturn 0;\n-\t\t\t}\n-\t\t}\n+\t\tif (!try_bitmap_count(&revs))\n+\t\t\treturn 0;\n+\t\tif (!try_bitmap_traversal(&revs))\n+\t\t\treturn 0;\n \t}\n \n \tif (prepare_revision_walk(&revs))\n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391639","messageId":"20200213021929.GF1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 06/13] rev-list: make --count work with --objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:19:29Z","receivedAt":"2020-02-13T02:19:32Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The current behavior from \"rev-list --count --objects\" is nonsensical:\nwe enumerate all of the objects except commits, but then give a count of\ncommits. This wasn't planned, and is just what the code happens to do.\n\nInstead, let's give the answer the user almost certainly wanted: the\nfull count of objects.\n\nNote that there are more complicated cases around cherry-marking, etc.\nWe'll punt on those for now, but let the user know that we can't produce\nan answer (rather than giving them something useless).\n\nWe'll test both the new feature as well as a vanilla --count of commits,\nsince that surprisingly doesn't seem to be covered in the existing\ntests.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 13 +++++++++++++\n t/t6000-rev-list-misc.sh | 12 ++++++++++++\n 2 files changed, 25 insertions(+)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex c2daf40449..b4fd507f25 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -253,11 +253,19 @@ static int finish_object(struct object *obj, const char *name, void *cb_data)\n static void show_object(struct object *obj, const char *name, void *cb_data)\n {\n \tstruct rev_list_info *info = cb_data;\n+\tstruct rev_info *revs = info->revs;\n+\n \tif (finish_object(obj, name, cb_data))\n \t\treturn;\n \tdisplay_progress(progress, ++progress_counter);\n \tif (info->flags & REV_LIST_QUIET)\n \t\treturn;\n+\n+\tif (revs->count) {\n+\t\trevs->count_right++;\n+\t\treturn;\n+\t}\n+\n \tif (arg_show_object_names)\n \t\tshow_object_with_name(stdout, obj, name);\n \telse\n@@ -584,6 +592,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (revs.show_notes)\n \t\tdie(_(\"rev-list does not support display of notes\"));\n \n+\tif (revs.count &&\n+\t (revs.tag_objects || revs.tree_objects || revs.blob_objects) &&\n+\t (revs.left_right || revs.cherry_mark))\n+\t\tdie(_(\"marked counting is incompatible with --objects\"));\n+\n \tif (filter_options.choice || revs.prune)\n \t\tuse_bitmap_index = 0;\n \ndiff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh\nindex b8cf82349b..383f2c457d 100755\n--- a/t/t6000-rev-list-misc.sh\n+++ b/t/t6000-rev-list-misc.sh\n@@ -148,4 +148,16 @@ test_expect_success 'rev-list --end-of-options' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'rev-list --count' '\n+\tcount=$(git rev-list --count HEAD) &&\n+\tgit rev-list HEAD >actual &&\n+\ttest_line_count = $count actual\n+'\n+\n+test_expect_success 'rev-list --count --objects' '\n+\tcount=$(git rev-list --count --objects HEAD) &&\n+\tgit rev-list --objects HEAD >actual &&\n+\ttest_line_count = $count actual\n+'\n+\n test_done\n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391640","messageId":"20200213022005.GG1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 07/13] rev-list: allow bitmaps when counting objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:20:05Z","receivedAt":"2020-02-13T02:20:08Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The prior commit taught \"--count --objects\" to work without bitmaps. We\nshould be able to get the same answer much more quickly with bitmaps.\n\nNote that we punt on the max_count case here. This perhaps _could_ be\nmade to work if we find all of the boundary commits and treat them as\nUNINTERESTING, subtracting them (and their reachable objects) from the\nset we return. That implies an actual commit traversal, but we'd still\nbe faster due to avoiding opening up any trees. Given the complexity and\nthe fact that anyone is unlikely to want this, it makes sense to just\nfall back to the non-bitmap case for now.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 21 ++++++++++++++++++---\n t/t5310-pack-bitmaps.sh | 6 ++++++\n 2 files changed, 24 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex b4fd507f25..ce1cfc7da0 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -374,7 +374,10 @@ static inline int parse_missing_action_value(const char *value)\n \n static int try_bitmap_count(struct rev_info *revs)\n {\n-\tuint32_t commit_count;\n+\tuint32_t commit_count = 0,\n+\t\t tag_count = 0,\n+\t\t tree_count = 0,\n+\t\t blob_count = 0;\n \tint max_count;\n \tstruct bitmap_index *bitmap_git;\n \n@@ -389,6 +392,15 @@ static int try_bitmap_count(struct rev_info *revs)\n \tif (revs->left_right || revs->cherry_mark)\n \t\treturn -1;\n \n+\t/*\n+\t * If we're counting reachable objects, we can't handle a max count of\n+\t * commits to traverse, since we don't know which objects go with which\n+\t * commit.\n+\t */\n+\tif (revs->max_count >= 0 &&\n+\t (revs->tag_objects || revs->tree_objects || revs->blob_objects))\n+\t\treturn -1;\n+\n \t/*\n \t * This must be saved before doing any walking, since the revision\n \t * machinery will count it down to zero while traversing.\n@@ -399,11 +411,14 @@ static int try_bitmap_count(struct rev_info *revs)\n \tif (!bitmap_git)\n \t\treturn -1;\n \n-\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n+\tcount_bitmap_commit_list(bitmap_git, &commit_count,\n+\t\t\t\t revs->tree_objects ? &tree_count : NULL,\n+\t\t\t\t revs->blob_objects ? &blob_count : NULL,\n+\t\t\t\t revs->tag_objects ? &tag_count : NULL);\n \tif (max_count >= 0 && max_count < commit_count)\n \t\tcommit_count = max_count;\n \n-\tprintf(\"%d\\n\", commit_count);\n+\tprintf(\"%d\\n\", commit_count + tree_count + blob_count + tag_count);\n \tfree_bitmap_index(bitmap_git);\n \treturn 0;\n }\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 6640329ebf..7ba7d294a5 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -74,6 +74,12 @@ rev_list_tests() {\n \t\ttest_cmp expect actual\n \t'\n \n+\ttest_expect_success \"counting objects via bitmap ($state)\" '\n+\t\tgit rev-list --count --objects HEAD >expect &&\n+\t\tgit rev-list --use-bitmap-index --count --objects HEAD >actual &&\n+\t\ttest_cmp expect actual\n+\t'\n+\n \ttest_expect_success \"enumerate --objects ($state)\" '\n \t\tgit rev-list --objects --use-bitmap-index HEAD >tmp &&\n \t\tcut -d\" \" -f1 tmp2 &&\n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391641","messageId":"20200213022058.GH1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 08/13] pack-bitmap: basic noop bitmap filter infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:20:58Z","receivedAt":"2020-02-13T02:21:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Currently you can't use object filters with bitmaps, but we plan to\nsupport at least some filters with bitmaps. Let's introduce some\ninfrastructure that will help us do that:\n\n - prepare_bitmap_walk() now accepts a list_objects_filter_options\n parameter (which can be NULL for no filtering; all the current\n callers pass this)\n\n - we'll bail early if the filter is incompatible with bitmaps (just as\n we would if there were no bitmaps at all). Currently all filters are\n incompatible.\n\n - we'll filter the resulting bitmap; since there are no supported\n filters yet, this is always a noop.\n\nThere should be no behavior change yet, but we'll support some actual\nfilters in a future patch.\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 2 +-\n builtin/rev-list.c | 4 ++--\n pack-bitmap.c | 30 ++++++++++++++++++++++++++++--\n pack-bitmap.h | 4 +++-\n reachable.c | 2 +-\n 5 files changed, 35 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 393c20a2d7..60c943e42b 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3040,7 +3040,7 @@ static int pack_options_allow_reuse(void)\n \n static int get_object_list_from_bitmap(struct rev_info *revs)\n {\n-\tif (!(bitmap_git = prepare_bitmap_walk(revs)))\n+\tif (!(bitmap_git = prepare_bitmap_walk(revs, NULL)))\n \t\treturn -1;\n \n \tif (pack_options_allow_reuse() &&\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex ce1cfc7da0..1ef180469f 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -407,7 +407,7 @@ static int try_bitmap_count(struct rev_info *revs)\n \t */\n \tmax_count = revs->max_count;\n \n-\tbitmap_git = prepare_bitmap_walk(revs);\n+\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n \tif (!bitmap_git)\n \t\treturn -1;\n \n@@ -441,7 +441,7 @@ static int try_bitmap_traversal(struct rev_info *revs)\n \tif (!revs->tag_objects || !revs->tree_objects || !revs->blob_objects)\n \t\treturn -1;\n \n-\tbitmap_git = prepare_bitmap_walk(revs);\n+\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n \tif (!bitmap_git)\n \t\treturn -1;\n \ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 6c06099dc7..eb8888bb5e 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -12,6 +12,7 @@\n #include \"packfile.h\"\n #include \"repository.h\"\n #include \"object-store.h\"\n+#include \"list-objects-filter-options.h\"\n \n /*\n * An entry on the bitmap index, representing the bitmap for a given\n@@ -705,7 +706,25 @@ static int in_bitmapped_pack(struct bitmap_index *bitmap_git,\n \treturn 0;\n }\n \n-struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n+static int filter_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t struct object_list *tip_objects,\n+\t\t\t struct bitmap *to_filter,\n+\t\t\t struct list_objects_filter_options *filter)\n+{\n+\tif (!filter || filter->choice == LOFC_DISABLED)\n+\t\treturn 0;\n+\n+\t/* filter choice not handled */\n+\treturn -1;\n+}\n+\n+static int can_filter_bitmap(struct list_objects_filter_options *filter)\n+{\n+\treturn !filter_bitmap(NULL, NULL, NULL, filter);\n+}\n+\n+struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n+\t\t\t\t\t struct list_objects_filter_options *filter)\n {\n \tunsigned int i;\n \n@@ -715,9 +734,14 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \tstruct bitmap *wants_bitmap = NULL;\n \tstruct bitmap *haves_bitmap = NULL;\n \n-\tstruct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));\n+\tstruct bitmap_index *bitmap_git;\n+\n+\tif (!can_filter_bitmap(filter))\n+\t\treturn NULL;\n+\n \t/* try to open a bitmapped pack, but don't parse it yet\n \t * because we may not need to use it */\n+\tbitmap_git = xcalloc(1, sizeof(*bitmap_git));\n \tif (open_pack_bitmap(revs->repo, bitmap_git) < 0)\n \t\tgoto cleanup;\n \n@@ -784,6 +808,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \tif (haves_bitmap)\n \t\tbitmap_and_not(wants_bitmap, haves_bitmap);\n \n+\tfilter_bitmap(bitmap_git, wants, wants_bitmap, filter);\n+\n \tbitmap_git->result = wants_bitmap;\n \tbitmap_git->haves = haves_bitmap;\n \ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 466c5afa09..04bdb20c3c 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -8,6 +8,7 @@\n struct commit;\n struct repository;\n struct rev_info;\n+struct list_objects_filter_options;\n \n static const char BITMAP_IDX_SIGNATURE[] = {'B', 'I', 'T', 'M'};\n \n@@ -46,7 +47,8 @@ void count_bitmap_commit_list(struct bitmap_index *, uint32_t *commits,\n void traverse_bitmap_commit_list(struct bitmap_index *,\n \t\t\t\t show_reachable_fn show_reachable);\n void test_bitmap_walk(struct rev_info *revs);\n-struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs);\n+struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n+\t\t\t\t\t struct list_objects_filter_options *filter);\n int reuse_partial_packfile_from_bitmap(struct bitmap_index *,\n \t\t\t\t struct packed_git **packfile,\n \t\t\t\t uint32_t *entries, off_t *up_to);\ndiff --git a/reachable.c b/reachable.c\nindex 8f50235b28..45cde57cab 100644\n--- a/reachable.c\n+++ b/reachable.c\n@@ -223,7 +223,7 @@ void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n \tcp.progress = progress;\n \tcp.count = 0;\n \n-\tbitmap_git = prepare_bitmap_walk(revs);\n+\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n \tif (bitmap_git) {\n \t\ttraverse_bitmap_commit_list(bitmap_git, mark_object_seen);\n \t\tfree_bitmap_index(bitmap_git);\n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391642","messageId":"20200213022125.GI1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 09/13] rev-list: use bitmap filters for traversal","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:21:25Z","receivedAt":"2020-02-13T02:21:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This just passes the filter-options struct to prepare_bitmap_walk().\nSince the bitmap code doesn't actually support any filters yet, it will\nfallback to the non-bitmap code if any --filter is specified. But this\nlets us exercise that rejection code path, as well as getting us ready\nto test filters via rev-list when we _do_ support them.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 16 +++++++++-------\n 1 file changed, 9 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 1ef180469f..c6850e318b 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -372,7 +372,8 @@ static inline int parse_missing_action_value(const char *value)\n \treturn 0;\n }\n \n-static int try_bitmap_count(struct rev_info *revs)\n+static int try_bitmap_count(struct rev_info *revs,\n+\t\t\t struct list_objects_filter_options *filter)\n {\n \tuint32_t commit_count = 0,\n \t\t tag_count = 0,\n@@ -407,7 +408,7 @@ static int try_bitmap_count(struct rev_info *revs)\n \t */\n \tmax_count = revs->max_count;\n \n-\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n+\tbitmap_git = prepare_bitmap_walk(revs, filter);\n \tif (!bitmap_git)\n \t\treturn -1;\n \n@@ -423,7 +424,8 @@ static int try_bitmap_count(struct rev_info *revs)\n \treturn 0;\n }\n \n-static int try_bitmap_traversal(struct rev_info *revs)\n+static int try_bitmap_traversal(struct rev_info *revs,\n+\t\t\t\tstruct list_objects_filter_options *filter)\n {\n \tstruct bitmap_index *bitmap_git;\n \n@@ -441,7 +443,7 @@ static int try_bitmap_traversal(struct rev_info *revs)\n \tif (!revs->tag_objects || !revs->tree_objects || !revs->blob_objects)\n \t\treturn -1;\n \n-\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n+\tbitmap_git = prepare_bitmap_walk(revs, filter);\n \tif (!bitmap_git)\n \t\treturn -1;\n \n@@ -612,7 +614,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t (revs.left_right || revs.cherry_mark))\n \t\tdie(_(\"marked counting is incompatible with --objects\"));\n \n-\tif (filter_options.choice || revs.prune)\n+\tif (revs.prune)\n \t\tuse_bitmap_index = 0;\n \n \tsave_commit_buffer = (revs.verbose_header ||\n@@ -625,9 +627,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\tprogress = start_delayed_progress(show_progress, 0);\n \n \tif (use_bitmap_index) {\n-\t\tif (!try_bitmap_count(&revs))\n+\t\tif (!try_bitmap_count(&revs, &filter_options))\n \t\t\treturn 0;\n-\t\tif (!try_bitmap_traversal(&revs))\n+\t\tif (!try_bitmap_traversal(&revs, &filter_options))\n \t\t\treturn 0;\n \t}\n \n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391643","messageId":"20200213022150.GJ1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 10/13] bitmap: add bitmap_unset() function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:21:50Z","receivedAt":"2020-02-13T02:21:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We've never needed to unset an individual bit in a bitmap until now.\nTypically they start with all bits unset and we bitmap_set() them, or we\nare applying another bitmap as a mask. But the easiest way to apply an\nobject filter to a bitmap result will be to unset the individual bits.\n\nSigned-off-by: Jeff King \n---\n ewah/bitmap.c | 8 ++++++++\n ewah/ewok.h | 1 +\n 2 files changed, 9 insertions(+)\n\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex 52f1178db4..1c31b3e249 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -45,6 +45,14 @@ void bitmap_set(struct bitmap *self, size_t pos)\n \tself->words[block] |= EWAH_MASK(pos);\n }\n \n+void bitmap_unset(struct bitmap *self, size_t pos)\n+{\n+\tsize_t block = EWAH_BLOCK(pos);\n+\n+\tif (block < self->word_alloc)\n+\t\tself->words[block] &= ~EWAH_MASK(pos);\n+}\n+\n int bitmap_get(struct bitmap *self, size_t pos)\n {\n \tsize_t block = EWAH_BLOCK(pos);\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 84b2a29faa..59f4ef7c4f 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -173,6 +173,7 @@ struct bitmap {\n \n struct bitmap *bitmap_new(void);\n void bitmap_set(struct bitmap *self, size_t pos);\n+void bitmap_unset(struct bitmap *self, size_t pos);\n int bitmap_get(struct bitmap *self, size_t pos);\n void bitmap_reset(struct bitmap *self);\n void bitmap_free(struct bitmap *self);\n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391644","messageId":"20200213022347.GK1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 11/13] pack-bitmap: implement BLOB_NONE filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:23:47Z","receivedAt":"2020-02-13T02:23:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We can easily support BLOB_NONE filters with bitmaps. Since we know the\ntypes of all of the objects, we just need to clear the result bits of\nany blobs.\n\nNote two subtleties in the implementation (which I also called out in\ncomments):\n\n - we have to include any blobs that were specifically asked for (and\n not reached through graph traversal) to match the non-bitmap version\n\n - we have to handle in-pack and \"ext_index\" objects separately.\n Arguably prepare_bitmap_walk() could be adding these ext_index\n objects to the type bitmaps. But it doesn't for now, so let's match\n the rest of the bitmap code here (it probably wouldn't be an\n efficiency improvement to do so since the cost of extending those\n bitmaps is about the same as our loop here, but it might make the\n code a bit simpler).\n\nThe regression tests just compare the bitmap output to the non-bitmap\noutput. Since the code internally falls back to the non-bitmap path in\nsome cases, this is at risk of being a trivial noop. To combat this,\nwe'll check for small differences between the two outputs (see the\ncomment in the test). This is a little fragile, as it's possible that we\nmay teach the fallback path for --use-bitmap-index to produce\nbitmap-like output in the future. But the exact ordering of objects\nwould likely be different in such a case, anyway.\n\nPlus we'd catch an unexpected fallback when running the perf suite, as\nthings would get slower. Here's what it looks like now (on git.git):\n\nTest HEAD^ HEAD\n--------------------------------------------------------------------------------\n5310.7: rev-list count with blob:none 1.67(1.62+0.05) 0.22(0.21+0.02) -86.8%\n\nSigned-off-by: Jeff King \n---\n pack-bitmap.c | 74 ++++++++++++++++++++++++++++++\n t/perf/p5310-pack-bitmaps.sh | 5 ++\n t/t6113-rev-list-bitmap-filters.sh | 35 ++++++++++++++\n 3 files changed, 114 insertions(+)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex eb8888bb5e..f430ddc3d2 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -706,6 +706,73 @@ static int in_bitmapped_pack(struct bitmap_index *bitmap_git,\n \treturn 0;\n }\n \n+static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct object_list *tip_objects)\n+{\n+\tstruct bitmap *result = bitmap_new();\n+\tstruct object_list *p;\n+\n+\tfor (p = tip_objects; p; p = p->next) {\n+\t\tint pos;\n+\n+\t\tif (p->item->type != OBJ_BLOB)\n+\t\t\tcontinue;\n+\n+\t\tpos = bitmap_position(bitmap_git, &p->item->oid);\n+\t\tif (pos < 0)\n+\t\t\tcontinue;\n+\n+\t\tbitmap_set(result, pos);\n+\t}\n+\n+\treturn result;\n+}\n+\n+static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct object_list *tip_objects,\n+\t\t\t\t struct bitmap *to_filter)\n+{\n+\tstruct eindex *eindex = &bitmap_git->ext_index;\n+\tstruct bitmap *tips;\n+\tstruct ewah_iterator it;\n+\teword_t mask;\n+\tuint32_t i;\n+\n+\t/*\n+\t * The non-bitmap version of this filter never removes\n+\t * blobs which the other side specifically asked for,\n+\t * so we must match that behavior.\n+\t */\n+\ttips = find_tip_blobs(bitmap_git, tip_objects);\n+\n+\t/*\n+\t * We can use the blob type-bitmap to work in whole words\n+\t * for the objects that are actually in the bitmapped packfile.\n+\t */\n+\tfor (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB);\n+\t i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);\n+\t i++) {\n+\t\tif (i < tips->word_alloc)\n+\t\t\tmask &= ~tips->words[i];\n+\t\tto_filter->words[i] &= ~mask;\n+\t}\n+\n+\t/*\n+\t * Clear any blobs that weren't in the packfile (and so would not have\n+\t * been caught by the loop above. We'll have to check them\n+\t * individually.\n+\t */\n+\tfor (i = 0; i < eindex->count; i++) {\n+\t\tuint32_t pos = i + bitmap_git->pack->num_objects;\n+\t\tif (eindex->objects[i]->type == OBJ_BLOB &&\n+\t\t bitmap_get(to_filter, pos) &&\n+\t\t !bitmap_get(tips, pos))\n+\t\t\tbitmap_unset(to_filter, pos);\n+\t}\n+\n+\tbitmap_free(tips);\n+}\n+\n static int filter_bitmap(struct bitmap_index *bitmap_git,\n \t\t\t struct object_list *tip_objects,\n \t\t\t struct bitmap *to_filter,\n@@ -714,6 +781,13 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,\n \tif (!filter || filter->choice == LOFC_DISABLED)\n \t\treturn 0;\n \n+\tif (filter->choice == LOFC_BLOB_NONE) {\n+\t\tif (bitmap_git)\n+\t\t\tfilter_bitmap_blob_none(bitmap_git, tip_objects,\n+\t\t\t\t\t\tto_filter);\n+\t\treturn 0;\n+\t}\n+\n \t/* filter choice not handled */\n \treturn -1;\n }\ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex 6a3a42531b..3383983450 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -39,6 +39,11 @@ test_perf 'pack to file (bitmap)' '\n \tgit pack-objects --use-bitmap-index --all pack1b /dev/null\n '\n \n+test_perf 'rev-list count with blob:none' '\n+\tgit rev-list --use-bitmap-index --count --objects --all \\\n+\t\t--filter=blob:none >/dev/null\n+'\n+\n test_expect_success 'create partial bitmap state' '\n \t# pick a commit to represent the repo tip in the past\n \tcutoff=$(git rev-list HEAD~100 -1) &&\ndiff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh\nindex 977f8d0930..feaa6c0989 100755\n--- a/t/t6113-rev-list-bitmap-filters.sh\n+++ b/t/t6113-rev-list-bitmap-filters.sh\n@@ -21,4 +21,39 @@ test_expect_success 'filters fallback to non-bitmap traversal' '\n \ttest_cmp expect actual\n '\n \n+# the bitmap and regular traversals produce subtly different output:\n+#\n+# - regular output is in traversal order, whereas bitmap is split by type,\n+# with non-packed objects at the end\n+#\n+# - regular output has a space and the pathname appended to non-commit\n+# objects; bitmap output omits this\n+#\n+# Normalize and compare the two. The second argument should always be the\n+# bitmap output.\n+cmp_bitmap_traversal () {\n+\tif cmp \"$1\" \"$2\"\n+\tthen\n+\t\techo >&2 \"identical raw outputs; are you sure bitmaps were used?\"\n+\t\treturn 1\n+\tfi &&\n+\tcut -d' ' -f1 \"$1\" | sort >\"$1.normalized\" &&\n+\tsort \"$2\" >\"$2.normalized\" &&\n+\ttest_cmp \"$1.normalized\" \"$2.normalized\"\n+}\n+\n+test_expect_success 'blob:none filter' '\n+\tgit rev-list --objects --filter=blob:none HEAD >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t --objects --filter=blob:none HEAD >actual &&\n+\tcmp_bitmap_traversal expect actual\n+'\n+\n+test_expect_success 'blob:none filter with specified blob' '\n+\tgit rev-list --objects --filter=blob:none HEAD HEAD:two.t >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t --objects --filter=blob:none HEAD HEAD:two.t >actual &&\n+\tcmp_bitmap_traversal expect actual\n+'\n+\n test_done\n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391645","messageId":"20200213022523.GL1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 12/13] pack-bitmap: implement BLOB_LIMIT filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:25:23Z","receivedAt":"2020-02-13T02:25:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Just as the previous commit implemented BLOB_NONE, we can support\nBLOB_LIMIT filters by looking at the sizes of any blobs in the result\nand unsetting their bits as appropriate. This is slightly more expensive\nthan BLOB_NONE, but still produces a noticeable speedup (these results\nare on git.git):\n\n Test HEAD~2 HEAD\n ------------------------------------------------------------------------------------\n 5310.7: rev-list count with blob:none 1.80(1.77+0.02) 0.22(0.20+0.02) -87.8%\n 5310.8: rev-list count with blob:limit=1k 1.99(1.96+0.03) 0.29(0.25+0.03) -85.4%\n\nThe implementation is similar to the BLOB_NONE one, with the exception\nthat we have to go object-by-object while walking the blob-type bitmap\n(since we can't mask out the matches, but must look up the size\nindividually for each blob). The trick with using ctz64() is taken from\nshow_objects_for_type(), which likewise needs to find individual bits\n(but wants to quickly skip over big chunks without blobs).\n\nSigned-off-by: Jeff King \n---\n pack-bitmap.c | 80 ++++++++++++++++++++++++++++++\n t/perf/p5310-pack-bitmaps.sh | 5 ++\n t/t6113-rev-list-bitmap-filters.sh | 20 +++++++-\n 3 files changed, 104 insertions(+), 1 deletion(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex f430ddc3d2..76cb60e8c3 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -773,6 +773,78 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,\n \tbitmap_free(tips);\n }\n \n+static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,\n+\t\t\t\t uint32_t pos)\n+{\n+\tstruct packed_git *pack = bitmap_git->pack;\n+\tunsigned long size;\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n+\n+\toi.sizep = &size;\n+\n+\tif (pos < pack->num_objects) {\n+\t\tstruct revindex_entry *entry = &pack->revindex[pos];\n+\t\tif (packed_object_info(the_repository, pack,\n+\t\t\t\t entry->offset, &oi) < 0) {\n+\t\t\tstruct object_id oid;\n+\t\t\tnth_packed_object_oid(&oid, pack, entry->nr);\n+\t\t\tdie(_(\"unable to get size of %s\"), oid_to_hex(&oid));\n+\t\t}\n+\t} else {\n+\t\tstruct eindex *eindex = &bitmap_git->ext_index;\n+\t\tstruct object *obj = eindex->objects[pos - pack->num_objects];\n+\t\tif (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)\n+\t\t\tdie(_(\"unable to get size of %s\"), oid_to_hex(&obj->oid));\n+\t}\n+\n+\treturn size;\n+}\n+\n+static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct object_list *tip_objects,\n+\t\t\t\t struct bitmap *to_filter,\n+\t\t\t\t unsigned long limit)\n+{\n+\tstruct eindex *eindex = &bitmap_git->ext_index;\n+\tstruct bitmap *tips;\n+\tstruct ewah_iterator it;\n+\teword_t mask;\n+\tuint32_t i;\n+\n+\ttips = find_tip_blobs(bitmap_git, tip_objects);\n+\n+\tfor (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB);\n+\t i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);\n+\t i++) {\n+\t\teword_t word = to_filter->words[i] & mask;\n+\t\tunsigned offset;\n+\n+\t\tfor (offset = 0; offset < BITS_IN_EWORD; offset++) {\n+\t\t\tuint32_t pos;\n+\n+\t\t\tif ((word >> offset) == 0)\n+\t\t\t\tbreak;\n+\t\t\toffset += ewah_bit_ctz64(word >> offset);\n+\t\t\tpos = i * BITS_IN_EWORD + offset;\n+\n+\t\t\tif (!bitmap_get(tips, pos) &&\n+\t\t\t get_size_by_pos(bitmap_git, pos) >= limit)\n+\t\t\t\tbitmap_unset(to_filter, pos);\n+\t\t}\n+\t}\n+\n+\tfor (i = 0; i < eindex->count; i++) {\n+\t\tuint32_t pos = i + bitmap_git->pack->num_objects;\n+\t\tif (eindex->objects[i]->type == OBJ_BLOB &&\n+\t\t bitmap_get(to_filter, pos) &&\n+\t\t !bitmap_get(tips, pos) &&\n+\t\t get_size_by_pos(bitmap_git, pos) >= limit)\n+\t\t\tbitmap_unset(to_filter, pos);\n+\t}\n+\n+\tbitmap_free(tips);\n+}\n+\n static int filter_bitmap(struct bitmap_index *bitmap_git,\n \t\t\t struct object_list *tip_objects,\n \t\t\t struct bitmap *to_filter,\n@@ -788,6 +860,14 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,\n \t\treturn 0;\n \t}\n \n+\tif (filter->choice == LOFC_BLOB_LIMIT) {\n+\t\tif (bitmap_git)\n+\t\t\tfilter_bitmap_blob_limit(bitmap_git, tip_objects,\n+\t\t\t\t\t\t to_filter,\n+\t\t\t\t\t\t filter->blob_limit_value);\n+\t\treturn 0;\n+\t}\n+\n \t/* filter choice not handled */\n \treturn -1;\n }\ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex 3383983450..bbe1eb26a9 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -44,6 +44,11 @@ test_perf 'rev-list count with blob:none' '\n \t\t--filter=blob:none >/dev/null\n '\n \n+test_perf 'rev-list count with blob:limit=1k' '\n+\tgit rev-list --use-bitmap-index --count --objects --all \\\n+\t\t--filter=blob:limit=1k >/dev/null\n+'\n+\n test_expect_success 'create partial bitmap state' '\n \t# pick a commit to represent the repo tip in the past\n \tcutoff=$(git rev-list HEAD~100 -1) &&\ndiff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh\nindex feaa6c0989..0878f72828 100755\n--- a/t/t6113-rev-list-bitmap-filters.sh\n+++ b/t/t6113-rev-list-bitmap-filters.sh\n@@ -6,8 +6,10 @@ test_description='rev-list combining bitmaps and filters'\n test_expect_success 'set up bitmapped repo' '\n \t# one commit will have bitmaps, the other will not\n \ttest_commit one &&\n+\ttest_commit much-larger-blob-one &&\n \tgit repack -adb &&\n-\ttest_commit two\n+\ttest_commit two &&\n+\ttest_commit much-larger-blob-two\n '\n \n test_expect_success 'filters fallback to non-bitmap traversal' '\n@@ -56,4 +58,20 @@ test_expect_success 'blob:none filter with specified blob' '\n \tcmp_bitmap_traversal expect actual\n '\n \n+test_expect_success 'blob:limit filter' '\n+\tgit rev-list --objects --filter=blob:limit=5 HEAD >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t --objects --filter=blob:limit=5 HEAD >actual &&\n+\tcmp_bitmap_traversal expect actual\n+'\n+\n+test_expect_success 'blob:limit filter with specified blob' '\n+\tgit rev-list --objects --filter=blob:limit=5 \\\n+\t\t HEAD HEAD:much-larger-blob-two.t >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t --objects --filter=blob:limit=5 \\\n+\t\t HEAD HEAD:much-larger-blob-two.t >actual &&\n+\tcmp_bitmap_traversal expect actual\n+'\n+\n test_done\n-- \n2.25.0.785.g49bcbe7794\n\n"},{"id":"391646","messageId":"20200213022556.GM1126038@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH 13/13] pack-objects: support filters with bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T02:25:56Z","receivedAt":"2020-02-13T02:25:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Just as rev-list recently learned to combine filters and bitmaps, let's\ndo the same for pack-objects. The infrastructure is all there; we just\nneed to pass along our filter options, and the pack-bitmap code will\ndecide to use bitmaps or not.\n\nThis unsurprisingly makes things faster for partial clones of large\nrepositories (here we're cloning linux.git):\n\n Test HEAD^ HEAD\n ------------------------------------------------------------------------------\n 5310.9: simulated partial clone 38.94(37.28+5.87) 11.06(11.27+4.07) -71.6%\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 3 +--\n t/perf/p5310-pack-bitmaps.sh | 4 ++++\n t/t5310-pack-bitmaps.sh | 14 ++++++++++++++\n 3 files changed, 19 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 60c943e42b..b09f85bd30 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3040,7 +3040,7 @@ static int pack_options_allow_reuse(void)\n \n static int get_object_list_from_bitmap(struct rev_info *revs)\n {\n-\tif (!(bitmap_git = prepare_bitmap_walk(revs, NULL)))\n+\tif (!(bitmap_git = prepare_bitmap_walk(revs, &filter_options)))\n \t\treturn -1;\n \n \tif (pack_options_allow_reuse() &&\n@@ -3418,7 +3418,6 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (filter_options.choice) {\n \t\tif (!pack_to_stdout)\n \t\t\tdie(_(\"cannot use --filter without --stdout\"));\n-\t\tuse_bitmap_index = 0;\n \t}\n \n \t/*\ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex bbe1eb26a9..5ab2104ee8 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -49,6 +49,10 @@ test_perf 'rev-list count with blob:limit=1k' '\n \t\t--filter=blob:limit=1k >/dev/null\n '\n \n+test_perf 'simulated partial clone' '\n+\tgit pack-objects --stdout --all --filter=blob:none /dev/null\n+'\n+\n test_expect_success 'create partial bitmap state' '\n \t# pick a commit to represent the repo tip in the past\n \tcutoff=$(git rev-list HEAD~100 -1) &&\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 7ba7d294a5..ac9e6acf27 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -105,6 +105,20 @@ test_expect_success 'clone from bitmapped repository' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'partial clone from bitmapped repository' '\n+\ttest_config uploadpack.allowfilter true &&\n+\tgit clone --no-local --bare --filter=blob:none . partial-clone.git &&\n+\t(\n+\t\tcd partial-clone.git &&\n+\t\tpack=$(echo objects/pack/*.pack) &&\n+\t\tgit verify-pack -v \"$pack\" >have &&\n+\t\tawk \"/blob/ { print \\$1 }\" blobs &&\n+\t\t# we expect this single blob because of the direct ref\n+\t\tgit rev-parse refs/tags/tagged-blob >expect &&\n+\t\ttest_cmp expect blobs\n+\t)\n+'\n+\n test_expect_success 'setup further non-bitmapped commits' '\n \ttest_commit_bulk --id=further 10\n '\n-- \n2.25.0.785.g49bcbe7794\n"},{"id":"391674","messageId":"xmqqlfp6s7o5.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200213021615.GA1126038@coredump.intra.peff.net","subject":"Re: [PATCH 01/13] pack-bitmap: factor out type iterator initialization","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-13T17:45:14Z","receivedAt":"2020-02-13T17:45:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> When count_object_type() wants to iterate over the bitmap of all objects\n> of a certain type, we have to pair up OBJ_COMMIT with bitmap->commits,\n> and so forth. Since we're about to add more code to iterate over these\n> bitmaps, let's pull the initialization into its own function.\n>\n> We can also use this to simplify traverse_bitmap_commit_list(). It\n> accomplishes the same thing by manually passing the object type and the\n> bitmap to show_objects_for_type(), but using our helper we just need the\n> object type.\n>\n> Note there's one small code change here: previously we'd simply return\n> zero when counting an unknown object type, and now we'll BUG(). This\n> shouldn't matter in practice, as all of the callers pass in only usual\n> commit/tree/blob/tag types.\n>\n> Signed-off-by: Jeff King \n> ---\n> pack-bitmap.c | 63 +++++++++++++++++++++++++++------------------------\n> 1 file changed, 33 insertions(+), 30 deletions(-)\n\nNicely written and makes perfect sense. show_objects_for_type()\nused to have a redundant pair of parameters, but it is impossible\nto pass them inconsistently after this change.\n\nThanks.\n"},{"id":"391680","messageId":"xmqqd0ais6ez.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200213021633.GB1126038@coredump.intra.peff.net","subject":"Re: [PATCH 02/13] pack-bitmap: fix leak of haves/wants object lists","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-13T18:12:20Z","receivedAt":"2020-02-13T18:12:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> When we do a bitmap-aware revision traversal, we create an object_list\n> for each of the \"haves\" and \"wants\" tips. After creating the result\n> bitmaps these are no longer needed or used, but we never free the list\n> memory.\n>\n> Signed-off-by: Jeff King \n> ---\n\nObviously correct ;-)\n"},{"id":"391681","messageId":"xmqq8sl6s63c.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200213021730.GC1126038@coredump.intra.peff.net","subject":"Re: [PATCH 03/13] rev-list: fallback to non-bitmap traversal when filtering","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-13T18:19:19Z","receivedAt":"2020-02-13T18:19:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> The \"--use-bitmap-index\" option is usually aspirational: if we have\n> bitmaps and the request can be fulfilled more quickly using them we'll\n> do so, but otherwise fall back to a non-bitmap traversal.\n>\n> The exception is object filtering, which explicitly dies if the two\n> options are combined. Let's convert this to the usual fallback behavior.\n>\n> This is a minor convenience for now (since the caller can easily know\n> that --filter and --use-bitmap-index don't combine), but will become\n> much more useful as we start to support _some_ filters with bitmaps, but\n> not others.\n\nMakes sense. \n\nPerhaps the option should have been called allow-bitmap-index or\nsomething along that line, but it is too late ;-)\n\n> +test_expect_success 'set up bitmapped repo' '\n> +\t# one commit will have bitmaps, the other will not\n> +\ttest_commit one &&\n> +\tgit repack -adb &&\n> +\ttest_commit two\n> +'\n> +\n> +test_expect_success 'filters fallback to non-bitmap traversal' '\n> +\t# use a path-based filter, since they are inherently incompatible with\n> +\t# bitmaps (i.e., this test will never get confused by later code to\n> +\t# combine the features)\n> +\tfilter=$(echo \"!one\" | git hash-object -w --stdin) &&\n> +\tgit rev-list --objects --filter=sparse:oid=$filter HEAD >expect &&\n> +\tgit rev-list --use-bitmap-index \\\n> +\t\t --objects --filter=sparse:oid=$filter HEAD >actual &&\n> +\ttest_cmp expect actual\n> +'\n\nOK.\n"},{"id":"391682","messageId":"xmqq4kvus5dm.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200213021820.GE1126038@coredump.intra.peff.net","subject":"Re: [PATCH 05/13] rev-list: factor out bitmap-optimized routines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-13T18:34:45Z","receivedAt":"2020-02-13T18:34:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> There are a few operations in rev-list that are optimized for bitmaps.\n> Rather than having the code inline in cmd_rev_list(), let's move them\n> into helpers. This not only makes the flow of the main function simpler,\n> but it lets us replace the complex \"can we do the optimization?\"\n> conditionals with a series of early returns from the functions. That\n> also makes it easy to add comments explaining those conditions.\n\n... and these new comments makes the resulting code much easier to\nfollow. Nicely done.\n\n"},{"id":"391684","messageId":"20200213184033.GA15046@coredump.intra.peff.net","threadId":"52795","inReplyTo":"xmqq8sl6s63c.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 03/13] rev-list: fallback to non-bitmap traversal when filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T18:40:33Z","receivedAt":"2020-02-13T18:40:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Feb 13, 2020 at 10:19:19AM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > The \"--use-bitmap-index\" option is usually aspirational: if we have\n> > bitmaps and the request can be fulfilled more quickly using them we'll\n> > do so, but otherwise fall back to a non-bitmap traversal.\n> >\n> > The exception is object filtering, which explicitly dies if the two\n> > options are combined. Let's convert this to the usual fallback behavior.\n> >\n> > This is a minor convenience for now (since the caller can easily know\n> > that --filter and --use-bitmap-index don't combine), but will become\n> > much more useful as we start to support _some_ filters with bitmaps, but\n> > not others.\n> \n> Makes sense. \n> \n> Perhaps the option should have been called allow-bitmap-index or\n> something along that line, but it is too late ;-)\n\nYeah. It's also annoyingly long to type, and makes for long lines in the\ntest scripts. ;)\n\nThere are also some weird semantics with the fallback, because the\noutput may differ depending on whether we use bitmaps (see one of the\nlater patches). I wouldn't be opposed to cleaning this up and giving it\na new option (\"--allow-bitmaps\" or something) to keep compatibility, but\nit's out of scope here.\n\nThe existing option (and my suggestion, as well as most of the internal\ncode) are guilty of equating \"bitmap\" with \"object reachability bitmap\".\nThere's lots of things one might use bitmaps for, and at some point we\nmight even expose such a thing via rev-list.\n\nAnyway, that concludes my rant. I don't think any of these are urgent to\nfix, and definitely shouldn't be part of this series.\n\n-Peff\n"},{"id":"391695","messageId":"xmqqwo8qqozl.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200213021929.GF1126038@coredump.intra.peff.net","subject":"Re: [PATCH 06/13] rev-list: make --count work with --objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-13T19:14:06Z","receivedAt":"2020-02-13T19:14:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> The current behavior from \"rev-list --count --objects\" is nonsensical:\n> we enumerate all of the objects except commits, but then give a count of\n> commits. This wasn't planned, and is just what the code happens to do.\n>\n> Instead, let's give the answer the user almost certainly wanted: the\n> full count of objects.\n>\n> Note that there are more complicated cases around cherry-marking, etc.\n> We'll punt on those for now, but let the user know that we can't produce\n> an answer (rather than giving them something useless).\n\nNow, finally we start changing the behaviour. \n\nIs the reason why --left-right and --objects do not work well\ntogether because same trees and blobs can be shared between commits\non both sides?\n\n> diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh\n> index b8cf82349b..383f2c457d 100755\n> --- a/t/t6000-rev-list-misc.sh\n> +++ b/t/t6000-rev-list-misc.sh\n> @@ -148,4 +148,16 @@ test_expect_success 'rev-list --end-of-options' '\n> \ttest_cmp expect actual\n> '\n> \n> +test_expect_success 'rev-list --count' '\n> +\tcount=$(git rev-list --count HEAD) &&\n> +\tgit rev-list HEAD >actual &&\n> +\ttest_line_count = $count actual\n> +'\n> +\n> +test_expect_success 'rev-list --count --objects' '\n> +\tcount=$(git rev-list --count --objects HEAD) &&\n> +\tgit rev-list --objects HEAD >actual &&\n> +\ttest_line_count = $count actual\n> +'\n\nMakes sense to define --count as the same as number of objects\nshown and verify it.\n\n\n"},{"id":"391698","messageId":"20200213202744.GA18860@coredump.intra.peff.net","threadId":"52795","inReplyTo":"xmqqwo8qqozl.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 06/13] rev-list: make --count work with --objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T20:27:44Z","receivedAt":"2020-02-13T20:27:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Feb 13, 2020 at 11:14:06AM -0800, Junio C Hamano wrote:\n\n> > The current behavior from \"rev-list --count --objects\" is nonsensical:\n> > we enumerate all of the objects except commits, but then give a count of\n> > commits. This wasn't planned, and is just what the code happens to do.\n> >\n> > Instead, let's give the answer the user almost certainly wanted: the\n> > full count of objects.\n> >\n> > Note that there are more complicated cases around cherry-marking, etc.\n> > We'll punt on those for now, but let the user know that we can't produce\n> > an answer (rather than giving them something useless).\n> \n> Now, finally we start changing the behaviour. \n> \n> Is the reason why --left-right and --objects do not work well\n> together because same trees and blobs can be shared between commits\n> on both sides?\n\nYes, exactly. I think you could probably define some sensible responses\nthere. E.g., consider this history:\n\n commit() { echo $1 >$1 && git add $1 && git commit -m $1; }\n commit base\n commit left\n git checkout -b side HEAD^\n commit right\n\nwhich looks like this:\n\n $ git log --graph --oneline --all\n * e0b7b94 (master) left\n | * 2a4163a (HEAD -> side) right\n |/ \n * 8d8a806 base\n\nThat \"base\" commit is sort of in the same boat: it's reachable from\neither side. By default we don't count it at all:\n\n $ git rev-list --count --left-right master...side\n 1\t1\n\nbut we do know about it as a boundary commit, and you could ask for it\nto be counted on the right:\n\n $ git rev-list --boundary --left-right master...side\n 2a4163a0a9bbcb837af2ac2e80e17120798f863a\n -8d8a806249905f101b5ac3f1eb74fa426f90ddf2\n\n $ git rev-list --count --boundary --left-right master...side\n 2\t1\n\nSo probably it would be sensible to do the same for the objects.\nAnything reachable from both is a \"boundary\" object. But I don't think\nwe extend the left-right marking to --objects at all now:\n\n $ git rev-list --boundary --left-right --objects master...side\n 2a4163a0a9bbcb837af2ac2e80e17120798f863a\n -8d8a806249905f101b5ac3f1eb74fa426f90ddf2\n f48654b5fe8de485e4622598842ca14b04b62c0a\n 45cf141ba67d59203f02a54f03162f3fcef57830 left\n 4540e3db9d99d518601ecadb81f7d55d55855033\n c376d892e8b105bd712d06ec5162b5f31ce949c3 right\n\nNor do we even seem to dig into the boundary objects.\n\nSo there would need to be more infrastructure in the traversal itself to\nbe able to do this right, I think. I'm happy to wait until somebody\ndemonstrates a real use for it. :)\n\n-Peff\n"},{"id":"391701","messageId":"xmqqftfeqhvp.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200213022005.GG1126038@coredump.intra.peff.net","subject":"Re: [PATCH 07/13] rev-list: allow bitmaps when counting objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-13T21:47:38Z","receivedAt":"2020-02-13T21:47:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> -\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n> +\tcount_bitmap_commit_list(bitmap_git, &commit_count,\n> +\t\t\t\t revs->tree_objects ? &tree_count : NULL,\n> +\t\t\t\t revs->blob_objects ? &blob_count : NULL,\n> +\t\t\t\t revs->tag_objects ? &tag_count : NULL);\n\nSo count_bitmap_commit_list() has been prepared to count non-commits\nalready, but we are just starting to use that feature?\n\nInteresting.\n\n> -\tprintf(\"%d\\n\", commit_count);\n> +\tprintf(\"%d\\n\", commit_count + tree_count + blob_count + tag_count);\n\nThanks.\n"},{"id":"391705","messageId":"xmqqblq2qga8.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200213022125.GI1126038@coredump.intra.peff.net","subject":"Re: [PATCH 09/13] rev-list: use bitmap filters for traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-13T22:22:07Z","receivedAt":"2020-02-13T22:22:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> This just passes the filter-options struct to prepare_bitmap_walk().\n> Since the bitmap code doesn't actually support any filters yet, it will\n> fallback to the non-bitmap code if any --filter is specified. But this\n> lets us exercise that rejection code path, as well as getting us ready\n> to test filters via rev-list when we _do_ support them.\n\nSo we used to look at filter_options.choice and declared any filter\nis incompatible with use_bitmap_index quite early, but now we let\neach of the try_bitmap_*() helpers check what is in the filter and\nmake their own decisions.\n\nOf course, the prepare_bitmap_walk() call at the beginning of these\nhelpers does not know how to work with any filter at this point in\nthe series, so all of the above cancel out :-).\n\nMakes sense.\n\nI wonder if the \"revs.prune\" thing that forces use_bitmap_index off\nshould also move to prepare_bitmap_walk() at some point in the\nseries (or after the current series is done). After all, the point\nof introducing try_bitmap_*() helpers was to let these bitmap\nspecific logic to know what is and is not compatible with the bitmap\nroutines.\n\nThanks.\n\n> @@ -441,7 +443,7 @@ static int try_bitmap_traversal(struct rev_info *revs)\n> \tif (!revs->tag_objects || !revs->tree_objects || !revs->blob_objects)\n> \t\treturn -1;\n> \n> -\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n> +\tbitmap_git = prepare_bitmap_walk(revs, filter);\n> \tif (!bitmap_git)\n> \t\treturn -1;\n> \n> @@ -612,7 +614,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n> \t (revs.left_right || revs.cherry_mark))\n> \t\tdie(_(\"marked counting is incompatible with --objects\"));\n> \n> -\tif (filter_options.choice || revs.prune)\n> +\tif (revs.prune)\n> \t\tuse_bitmap_index = 0;\n> \n> \tsave_commit_buffer = (revs.verbose_header ||\n> @@ -625,9 +627,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n> \t\tprogress = start_delayed_progress(show_progress, 0);\n> \n> \tif (use_bitmap_index) {\n> -\t\tif (!try_bitmap_count(&revs))\n> +\t\tif (!try_bitmap_count(&revs, &filter_options))\n> \t\t\treturn 0;\n> -\t\tif (!try_bitmap_traversal(&revs))\n> +\t\tif (!try_bitmap_traversal(&revs, &filter_options))\n> \t\t\treturn 0;\n> \t}\n"},{"id":"391706","messageId":"20200213222710.GA25317@coredump.intra.peff.net","threadId":"52795","inReplyTo":"xmqqftfeqhvp.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 07/13] rev-list: allow bitmaps when counting objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T22:27:10Z","receivedAt":"2020-02-13T22:27:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Feb 13, 2020 at 01:47:38PM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > -\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n> > +\tcount_bitmap_commit_list(bitmap_git, &commit_count,\n> > +\t\t\t\t revs->tree_objects ? &tree_count : NULL,\n> > +\t\t\t\t revs->blob_objects ? &blob_count : NULL,\n> > +\t\t\t\t revs->tag_objects ? &tag_count : NULL);\n> \n> So count_bitmap_commit_list() has been prepared to count non-commits\n> already, but we are just starting to use that feature?\n> \n> Interesting.\n\nYeah, it goes all the way back to fff42755ef (pack-bitmap: add support\nfor bitmap indexes, 2013-12-21), but was never used for non-commits. I\nwas pleasantly surprised that it actually worked. ;)\n\n-Peff\n"},{"id":"391707","messageId":"20200213223407.GB25317@coredump.intra.peff.net","threadId":"52795","inReplyTo":"xmqqblq2qga8.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 09/13] rev-list: use bitmap filters for traversal","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-13T22:34:07Z","receivedAt":"2020-02-13T22:34:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Feb 13, 2020 at 02:22:07PM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > This just passes the filter-options struct to prepare_bitmap_walk().\n> > Since the bitmap code doesn't actually support any filters yet, it will\n> > fallback to the non-bitmap code if any --filter is specified. But this\n> > lets us exercise that rejection code path, as well as getting us ready\n> > to test filters via rev-list when we _do_ support them.\n> \n> So we used to look at filter_options.choice and declared any filter\n> is incompatible with use_bitmap_index quite early, but now we let\n> each of the try_bitmap_*() helpers check what is in the filter and\n> make their own decisions.\n> \n> Of course, the prepare_bitmap_walk() call at the beginning of these\n> helpers does not know how to work with any filter at this point in\n> the series, so all of the above cancel out :-).\n> \n> Makes sense.\n> \n> I wonder if the \"revs.prune\" thing that forces use_bitmap_index off\n> should also move to prepare_bitmap_walk() at some point in the\n> series (or after the current series is done). After all, the point\n> of introducing try_bitmap_*() helpers was to let these bitmap\n> specific logic to know what is and is not compatible with the bitmap\n> routines.\n\nAh, interesting thought. Yeah, we could push it down to that level to\navoid rev-list having to know details about how the bitmap code works.\nThat could replace the earlier patch to consolidate the filter/prune\nlogic. And then in this patch, this hunk:\n\n> > @@ -612,7 +614,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n> > \t (revs.left_right || revs.cherry_mark))\n> > \t\tdie(_(\"marked counting is incompatible with --objects\"));\n> > \n> > -\tif (filter_options.choice || revs.prune)\n> > +\tif (revs.prune)\n> > \t\tuse_bitmap_index = 0;\n\nwould just drop this conditional entirely. I like it.\n\n-Peff\n"},{"id":"391711","messageId":"xmqq7e0qqdqh.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200213022523.GL1126038@coredump.intra.peff.net","subject":"Re: [PATCH 12/13] pack-bitmap: implement BLOB_LIMIT filtering","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-13T23:17:10Z","receivedAt":"2020-02-13T23:17:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Just as the previous commit implemented BLOB_NONE, we can support\n> BLOB_LIMIT filters by looking at the sizes of any blobs in the result\n> and unsetting their bits as appropriate. This is slightly more expensive\n> than BLOB_NONE, but still produces a noticeable speedup (these results\n> are on git.git):\n>\n> Test HEAD~2 HEAD\n> ------------------------------------------------------------------------------------\n> 5310.7: rev-list count with blob:none 1.80(1.77+0.02) 0.22(0.20+0.02) -87.8%\n> 5310.8: rev-list count with blob:limit=1k 1.99(1.96+0.03) 0.29(0.25+0.03) -85.4%\n\nThat's respectable improvement. packed_object_info() that asks only\nfor the inflated size is quite cheap when the object is a delta, and\nhopefully we have more deltified blobs than deflated ones.\n\n> +static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,\n> +\t\t\t\t uint32_t pos)\n> +{\n> +\tstruct packed_git *pack = bitmap_git->pack;\n> +\tunsigned long size;\n> +\tstruct object_info oi = OBJECT_INFO_INIT;\n> +\n> +\toi.sizep = &size;\n> +\n> +\tif (pos < pack->num_objects) {\n> +\t\tstruct revindex_entry *entry = &pack->revindex[pos];\n> +\t\tif (packed_object_info(the_repository, pack,\n> +\t\t\t\t entry->offset, &oi) < 0) {\n> +\t\t\tstruct object_id oid;\n> +\t\t\tnth_packed_object_oid(&oid, pack, entry->nr);\n> +\t\t\tdie(_(\"unable to get size of %s\"), oid_to_hex(&oid));\n> +\t\t}\n> +\t} else {\n> +\t\tstruct eindex *eindex = &bitmap_git->ext_index;\n> +\t\tstruct object *obj = eindex->objects[pos - pack->num_objects];\n> +\t\tif (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)\n> +\t\t\tdie(_(\"unable to get size of %s\"), oid_to_hex(&obj->oid));\n> +\t}\n> +\n> +\treturn size;\n> +}\n\n"},{"id":"391777","messageId":"20200214182147.GA654525@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200213021506.GA1124607@coredump.intra.peff.net","subject":"[PATCH v2 0/15] combining object filters and bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:21:47Z","receivedAt":"2020-02-14T18:21:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Here's a v2 based on the early feedback from Junio, and a few things I\nnoticed while addressing it:\n\n - patch 4 now moves the check for revs.prune into the pack-bitmap code,\n rather than rearranging it within rev-list.\n\n - I noticed some more opportunities to reuse the \"compare the results\n of a bitmap and non-bitmap traversal\" code, so I factored that out\n into its own commit (patch 8)\n\n - I realized another long-standing annoyance is simple to fix: before\n we did not know how to do \"rev-list --use-bitmap-index\" without\n \"--objects\", but it was pretty easy to support. That's patch 9.\n\nThe range diff below is a little noisy because of the ripple effects of\nsome of those changes. If you just want to review the substantive\nchanges, look at patches 4, 8, and 9.\n\n [01/15]: pack-bitmap: factor out type iterator initialization\n [02/15]: pack-bitmap: fix leak of haves/wants object lists\n [03/15]: rev-list: fallback to non-bitmap traversal when filtering\n [04/15]: pack-bitmap: refuse to do a bitmap traversal with pathspecs\n [05/15]: rev-list: factor out bitmap-optimized routines\n [06/15]: rev-list: make --count work with --objects\n [07/15]: rev-list: allow bitmaps when counting objects\n [08/15]: t5310: factor out bitmap traversal comparison\n [09/15]: rev-list: allow commit-only bitmap traversals\n [10/15]: pack-bitmap: basic noop bitmap filter infrastructure\n [11/15]: rev-list: use bitmap filters for traversal\n [12/15]: bitmap: add bitmap_unset() function\n [13/15]: pack-bitmap: implement BLOB_NONE filtering\n [14/15]: pack-bitmap: implement BLOB_LIMIT filtering\n [15/15]: pack-objects: support filters with bitmaps\n\n builtin/pack-objects.c | 6 +-\n builtin/rev-list.c | 114 +++++++++---\n ewah/bitmap.c | 8 +\n ewah/ewok.h | 1 +\n object.c | 9 +\n object.h | 2 +\n pack-bitmap.c | 272 +++++++++++++++++++++++++----\n pack-bitmap.h | 5 +-\n reachable.c | 4 +-\n t/perf/p5310-pack-bitmaps.sh | 22 +++\n t/t5310-pack-bitmaps.sh | 36 +++-\n t/t6000-rev-list-misc.sh | 12 ++\n t/t6113-rev-list-bitmap-filters.sh | 56 ++++++\n t/test-lib-functions.sh | 27 +++\n 14 files changed, 504 insertions(+), 70 deletions(-)\n create mode 100755 t/t6113-rev-list-bitmap-filters.sh\n\nRange-diff from v1:\n\n 1: 283874f2ac = 1: 4424d745de pack-bitmap: factor out type iterator initialization\n 2: 68e7bed41c = 2: bc0576868f pack-bitmap: fix leak of haves/wants object lists\n 3: 1182593fb2 = 3: 9d2ef09b9b rev-list: fallback to non-bitmap traversal when filtering\n 4: 03b20e9b66 < -: ---------- rev-list: consolidate bitmap-disabling options\n -: ---------- > 4: ce7969221a pack-bitmap: refuse to do a bitmap traversal with pathspecs\n 5: 91032b0d78 = 5: a9a5513bb0 rev-list: factor out bitmap-optimized routines\n 6: c7c3a31cf3 ! 6: eab5dd34bc rev-list: make --count work with --objects\n @@ builtin/rev-list.c: int cmd_rev_list(int argc, const char **argv, const char *pr\n +\t (revs.left_right || revs.cherry_mark))\n +\t\tdie(_(\"marked counting is incompatible with --objects\"));\n +\n - \tif (filter_options.choice || revs.prune)\n + \tif (filter_options.choice)\n \t\tuse_bitmap_index = 0;\n \n \n 7: 0aabf6262b = 7: 04af6b9362 rev-list: allow bitmaps when counting objects\n -: ---------- > 8: 4b93d064b1 t5310: factor out bitmap traversal comparison\n -: ---------- > 9: d89509fa8f rev-list: allow commit-only bitmap traversals\n 8: 969238ec42 ! 10: c64d4db8e8 pack-bitmap: basic noop bitmap filter infrastructure\n @@ builtin/rev-list.c: static int try_bitmap_count(struct rev_info *revs)\n \t\treturn -1;\n \n @@ builtin/rev-list.c: static int try_bitmap_traversal(struct rev_info *revs)\n - \tif (!revs->tag_objects || !revs->tree_objects || !revs->blob_objects)\n + \tif (revs->max_count >= 0)\n \t\treturn -1;\n \n -\tbitmap_git = prepare_bitmap_walk(revs);\n @@ pack-bitmap.c: static int in_bitmapped_pack(struct bitmap_index *bitmap_git,\n \tunsigned int i;\n \n @@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n - \tstruct bitmap *wants_bitmap = NULL;\n - \tstruct bitmap *haves_bitmap = NULL;\n + \tif (revs->prune)\n + \t\treturn NULL;\n \n --\tstruct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));\n -+\tstruct bitmap_index *bitmap_git;\n -+\n +\tif (!can_filter_bitmap(filter))\n +\t\treturn NULL;\n +\n \t/* try to open a bitmapped pack, but don't parse it yet\n \t * because we may not need to use it */\n -+\tbitmap_git = xcalloc(1, sizeof(*bitmap_git));\n - \tif (open_pack_bitmap(revs->repo, bitmap_git) < 0)\n - \t\tgoto cleanup;\n - \n + \tbitmap_git = xcalloc(1, sizeof(*bitmap_git));\n @@ pack-bitmap.c: struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \tif (haves_bitmap)\n \t\tbitmap_and_not(wants_bitmap, haves_bitmap);\n @@ pack-bitmap.h\n \n static const char BITMAP_IDX_SIGNATURE[] = {'B', 'I', 'T', 'M'};\n \n -@@ pack-bitmap.h: void count_bitmap_commit_list(struct bitmap_index *, uint32_t *commits,\n - void traverse_bitmap_commit_list(struct bitmap_index *,\n +@@ pack-bitmap.h: void traverse_bitmap_commit_list(struct bitmap_index *,\n + \t\t\t\t struct rev_info *revs,\n \t\t\t\t show_reachable_fn show_reachable);\n void test_bitmap_walk(struct rev_info *revs);\n -struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs);\n @@ reachable.c: void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n -\tbitmap_git = prepare_bitmap_walk(revs);\n +\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n \tif (bitmap_git) {\n - \t\ttraverse_bitmap_commit_list(bitmap_git, mark_object_seen);\n + \t\ttraverse_bitmap_commit_list(bitmap_git, revs, mark_object_seen);\n \t\tfree_bitmap_index(bitmap_git);\n 9: b4eb8fcb9d ! 11: caa69ac535 rev-list: use bitmap filters for traversal\n @@ builtin/rev-list.c: static int try_bitmap_count(struct rev_info *revs)\n \tstruct bitmap_index *bitmap_git;\n \n @@ builtin/rev-list.c: static int try_bitmap_traversal(struct rev_info *revs)\n - \tif (!revs->tag_objects || !revs->tree_objects || !revs->blob_objects)\n + \tif (revs->max_count >= 0)\n \t\treturn -1;\n \n -\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n @@ builtin/rev-list.c: int cmd_rev_list(int argc, const char **argv, const char *pr\n \t (revs.left_right || revs.cherry_mark))\n \t\tdie(_(\"marked counting is incompatible with --objects\"));\n \n --\tif (filter_options.choice || revs.prune)\n -+\tif (revs.prune)\n - \t\tuse_bitmap_index = 0;\n - \n +-\tif (filter_options.choice)\n +-\t\tuse_bitmap_index = 0;\n +-\n \tsave_commit_buffer = (revs.verbose_header ||\n + \t\t\t revs.grep_filter.pattern_list ||\n + \t\t\t revs.grep_filter.header_list);\n @@ builtin/rev-list.c: int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\tprogress = start_delayed_progress(show_progress, 0);\n \n10: b518070c12 = 12: d3e7462138 bitmap: add bitmap_unset() function\n11: 438c21082e ! 13: 07ee699520 pack-bitmap: implement BLOB_NONE filtering\n @@ Commit message\n bitmaps is about the same as our loop here, but it might make the\n code a bit simpler).\n \n - The regression tests just compare the bitmap output to the non-bitmap\n - output. Since the code internally falls back to the non-bitmap path in\n - some cases, this is at risk of being a trivial noop. To combat this,\n - we'll check for small differences between the two outputs (see the\n - comment in the test). This is a little fragile, as it's possible that we\n - may teach the fallback path for --use-bitmap-index to produce\n - bitmap-like output in the future. But the exact ordering of objects\n - would likely be different in such a case, anyway.\n + Here are perf results for the new test on git.git:\n \n - Plus we'd catch an unexpected fallback when running the perf suite, as\n - things would get slower. Here's what it looks like now (on git.git):\n -\n - Test HEAD^ HEAD\n - --------------------------------------------------------------------------------\n - 5310.7: rev-list count with blob:none 1.67(1.62+0.05) 0.22(0.21+0.02) -86.8%\n + Test HEAD^ HEAD\n + --------------------------------------------------------------------------------\n + 5310.9: rev-list count with blob:none 1.67(1.62+0.05) 0.22(0.21+0.02) -86.8%\n \n ## pack-bitmap.c ##\n @@ pack-bitmap.c: static int in_bitmapped_pack(struct bitmap_index *bitmap_git,\n @@ pack-bitmap.c: static int filter_bitmap(struct bitmap_index *bitmap_git,\n }\n \n ## t/perf/p5310-pack-bitmaps.sh ##\n -@@ t/perf/p5310-pack-bitmaps.sh: test_perf 'pack to file (bitmap)' '\n - \tgit pack-objects --use-bitmap-index --all pack1b /dev/null\n +@@ t/perf/p5310-pack-bitmaps.sh: test_perf 'rev-list (objects)' '\n + \tgit rev-list --all --use-bitmap-index --objects >/dev/null\n '\n \n +test_perf 'rev-list count with blob:none' '\n @@ t/t6113-rev-list-bitmap-filters.sh: test_expect_success 'filters fallback to non\n \ttest_cmp expect actual\n '\n \n -+# the bitmap and regular traversals produce subtly different output:\n -+#\n -+# - regular output is in traversal order, whereas bitmap is split by type,\n -+# with non-packed objects at the end\n -+#\n -+# - regular output has a space and the pathname appended to non-commit\n -+# objects; bitmap output omits this\n -+#\n -+# Normalize and compare the two. The second argument should always be the\n -+# bitmap output.\n -+cmp_bitmap_traversal () {\n -+\tif cmp \"$1\" \"$2\"\n -+\tthen\n -+\t\techo >&2 \"identical raw outputs; are you sure bitmaps were used?\"\n -+\t\treturn 1\n -+\tfi &&\n -+\tcut -d' ' -f1 \"$1\" | sort >\"$1.normalized\" &&\n -+\tsort \"$2\" >\"$2.normalized\" &&\n -+\ttest_cmp \"$1.normalized\" \"$2.normalized\"\n -+}\n -+\n +test_expect_success 'blob:none filter' '\n +\tgit rev-list --objects --filter=blob:none HEAD >expect &&\n +\tgit rev-list --use-bitmap-index \\\n +\t\t --objects --filter=blob:none HEAD >actual &&\n -+\tcmp_bitmap_traversal expect actual\n ++\ttest_bitmap_traversal expect actual\n +'\n +\n +test_expect_success 'blob:none filter with specified blob' '\n +\tgit rev-list --objects --filter=blob:none HEAD HEAD:two.t >expect &&\n +\tgit rev-list --use-bitmap-index \\\n +\t\t --objects --filter=blob:none HEAD HEAD:two.t >actual &&\n -+\tcmp_bitmap_traversal expect actual\n ++\ttest_bitmap_traversal expect actual\n +'\n +\n test_done\n12: 05cd57f0ba ! 14: f35fab09a0 pack-bitmap: implement BLOB_LIMIT filtering\n @@ Commit message\n than BLOB_NONE, but still produces a noticeable speedup (these results\n are on git.git):\n \n - Test HEAD~2 HEAD\n + Test HEAD~2 HEAD\n ------------------------------------------------------------------------------------\n - 5310.7: rev-list count with blob:none 1.80(1.77+0.02) 0.22(0.20+0.02) -87.8%\n - 5310.8: rev-list count with blob:limit=1k 1.99(1.96+0.03) 0.29(0.25+0.03) -85.4%\n + 5310.9: rev-list count with blob:none 1.80(1.77+0.02) 0.22(0.20+0.02) -87.8%\n + 5310.10: rev-list count with blob:limit=1k 1.99(1.96+0.03) 0.29(0.25+0.03) -85.4%\n \n The implementation is similar to the BLOB_NONE one, with the exception\n that we have to go object-by-object while walking the blob-type bitmap\n @@ t/t6113-rev-list-bitmap-filters.sh: test_description='rev-list combining bitmaps\n \n test_expect_success 'filters fallback to non-bitmap traversal' '\n @@ t/t6113-rev-list-bitmap-filters.sh: test_expect_success 'blob:none filter with specified blob' '\n - \tcmp_bitmap_traversal expect actual\n + \ttest_bitmap_traversal expect actual\n '\n \n +test_expect_success 'blob:limit filter' '\n +\tgit rev-list --objects --filter=blob:limit=5 HEAD >expect &&\n +\tgit rev-list --use-bitmap-index \\\n +\t\t --objects --filter=blob:limit=5 HEAD >actual &&\n -+\tcmp_bitmap_traversal expect actual\n ++\ttest_bitmap_traversal expect actual\n +'\n +\n +test_expect_success 'blob:limit filter with specified blob' '\n @@ t/t6113-rev-list-bitmap-filters.sh: test_expect_success 'blob:none filter with s\n +\tgit rev-list --use-bitmap-index \\\n +\t\t --objects --filter=blob:limit=5 \\\n +\t\t HEAD HEAD:much-larger-blob-two.t >actual &&\n -+\tcmp_bitmap_traversal expect actual\n ++\ttest_bitmap_traversal expect actual\n +'\n +\n test_done\n13: 1e5befb73a ! 15: 797dbfe28f pack-objects: support filters with bitmaps\n @@ Commit message\n This unsurprisingly makes things faster for partial clones of large\n repositories (here we're cloning linux.git):\n \n - Test HEAD^ HEAD\n + Test HEAD^ HEAD\n ------------------------------------------------------------------------------\n - 5310.9: simulated partial clone 38.94(37.28+5.87) 11.06(11.27+4.07) -71.6%\n + 5310.11: simulated partial clone 38.94(37.28+5.87) 11.06(11.27+4.07) -71.6%\n \n ## builtin/pack-objects.c ##\n @@ builtin/pack-objects.c: static int pack_options_allow_reuse(void)\n"},{"id":"391778","messageId":"20200214182208.GA150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 01/15] pack-bitmap: factor out type iterator initialization","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:08Z","receivedAt":"2020-02-14T18:22:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When count_object_type() wants to iterate over the bitmap of all objects\nof a certain type, we have to pair up OBJ_COMMIT with bitmap->commits,\nand so forth. Since we're about to add more code to iterate over these\nbitmaps, let's pull the initialization into its own function.\n\nWe can also use this to simplify traverse_bitmap_commit_list(). It\naccomplishes the same thing by manually passing the object type and the\nbitmap to show_objects_for_type(), but using our helper we just need the\nobject type.\n\nNote there's one small code change here: previously we'd simply return\nzero when counting an unknown object type, and now we'll BUG(). This\nshouldn't matter in practice, as all of the callers pass in only usual\ncommit/tree/blob/tag types.\n\nSigned-off-by: Jeff King \n---\n pack-bitmap.c | 63 +++++++++++++++++++++++++++------------------------\n 1 file changed, 33 insertions(+), 30 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex e07c798879..9ca356ee29 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -616,9 +616,35 @@ static void show_extended_objects(struct bitmap_index *bitmap_git,\n \t}\n }\n \n+static void init_type_iterator(struct ewah_iterator *it,\n+\t\t\t struct bitmap_index *bitmap_git,\n+\t\t\t enum object_type type)\n+{\n+\tswitch (type) {\n+\tcase OBJ_COMMIT:\n+\t\tewah_iterator_init(it, bitmap_git->commits);\n+\t\tbreak;\n+\n+\tcase OBJ_TREE:\n+\t\tewah_iterator_init(it, bitmap_git->trees);\n+\t\tbreak;\n+\n+\tcase OBJ_BLOB:\n+\t\tewah_iterator_init(it, bitmap_git->blobs);\n+\t\tbreak;\n+\n+\tcase OBJ_TAG:\n+\t\tewah_iterator_init(it, bitmap_git->tags);\n+\t\tbreak;\n+\n+\tdefault:\n+\t\tBUG(\"object type %d not stored by bitmap type index\", type);\n+\t\tbreak;\n+\t}\n+}\n+\n static void show_objects_for_type(\n \tstruct bitmap_index *bitmap_git,\n-\tstruct ewah_bitmap *type_filter,\n \tenum object_type object_type,\n \tshow_reachable_fn show_reach)\n {\n@@ -633,7 +659,7 @@ static void show_objects_for_type(\n \tif (bitmap_git->reuse_objects == bitmap_git->pack->num_objects)\n \t\treturn;\n \n-\tewah_iterator_init(&it, type_filter);\n+\tinit_type_iterator(&it, bitmap_git, object_type);\n \n \twhile (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {\n \t\teword_t word = objects->words[i] & filter;\n@@ -835,14 +861,10 @@ void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,\n {\n \tassert(bitmap_git->result);\n \n-\tshow_objects_for_type(bitmap_git, bitmap_git->commits,\n-\t\tOBJ_COMMIT, show_reachable);\n-\tshow_objects_for_type(bitmap_git, bitmap_git->trees,\n-\t\tOBJ_TREE, show_reachable);\n-\tshow_objects_for_type(bitmap_git, bitmap_git->blobs,\n-\t\tOBJ_BLOB, show_reachable);\n-\tshow_objects_for_type(bitmap_git, bitmap_git->tags,\n-\t\tOBJ_TAG, show_reachable);\n+\tshow_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable);\n+\tshow_objects_for_type(bitmap_git, OBJ_TREE, show_reachable);\n+\tshow_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable);\n+\tshow_objects_for_type(bitmap_git, OBJ_TAG, show_reachable);\n \n \tshow_extended_objects(bitmap_git, show_reachable);\n }\n@@ -857,26 +879,7 @@ static uint32_t count_object_type(struct bitmap_index *bitmap_git,\n \tstruct ewah_iterator it;\n \teword_t filter;\n \n-\tswitch (type) {\n-\tcase OBJ_COMMIT:\n-\t\tewah_iterator_init(&it, bitmap_git->commits);\n-\t\tbreak;\n-\n-\tcase OBJ_TREE:\n-\t\tewah_iterator_init(&it, bitmap_git->trees);\n-\t\tbreak;\n-\n-\tcase OBJ_BLOB:\n-\t\tewah_iterator_init(&it, bitmap_git->blobs);\n-\t\tbreak;\n-\n-\tcase OBJ_TAG:\n-\t\tewah_iterator_init(&it, bitmap_git->tags);\n-\t\tbreak;\n-\n-\tdefault:\n-\t\treturn 0;\n-\t}\n+\tinit_type_iterator(&it, bitmap_git, type);\n \n \twhile (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {\n \t\teword_t word = objects->words[i++] & filter;\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391779","messageId":"20200214182213.GC150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 03/15] rev-list: fallback to non-bitmap traversal when filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:13Z","receivedAt":"2020-02-14T18:22:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The \"--use-bitmap-index\" option is usually aspirational: if we have\nbitmaps and the request can be fulfilled more quickly using them we'll\ndo so, but otherwise fall back to a non-bitmap traversal.\n\nThe exception is object filtering, which explicitly dies if the two\noptions are combined. Let's convert this to the usual fallback behavior.\nThis is a minor convenience for now (since the caller can easily know\nthat --filter and --use-bitmap-index don't combine), but will become\nmuch more useful as we start to support _some_ filters with bitmaps, but\nnot others.\n\nThe test infrastructure here is bigger than necessary for checking this\none small feature. But it will serve as the basis for more filtering\nbitmap tests in future patches.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 4 ++--\n t/t6113-rev-list-bitmap-filters.sh | 24 ++++++++++++++++++++++++\n 2 files changed, 26 insertions(+), 2 deletions(-)\n create mode 100755 t/t6113-rev-list-bitmap-filters.sh\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex e28d62ec64..bce406bd1e 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -521,8 +521,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (revs.show_notes)\n \t\tdie(_(\"rev-list does not support display of notes\"));\n \n-\tif (filter_options.choice && use_bitmap_index)\n-\t\tdie(_(\"cannot combine --use-bitmap-index with object filtering\"));\n+\tif (filter_options.choice)\n+\t\tuse_bitmap_index = 0;\n \n \tsave_commit_buffer = (revs.verbose_header ||\n \t\t\t revs.grep_filter.pattern_list ||\ndiff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh\nnew file mode 100755\nindex 0000000000..977f8d0930\n--- /dev/null\n+++ b/t/t6113-rev-list-bitmap-filters.sh\n@@ -0,0 +1,24 @@\n+#!/bin/sh\n+\n+test_description='rev-list combining bitmaps and filters'\n+. ./test-lib.sh\n+\n+test_expect_success 'set up bitmapped repo' '\n+\t# one commit will have bitmaps, the other will not\n+\ttest_commit one &&\n+\tgit repack -adb &&\n+\ttest_commit two\n+'\n+\n+test_expect_success 'filters fallback to non-bitmap traversal' '\n+\t# use a path-based filter, since they are inherently incompatible with\n+\t# bitmaps (i.e., this test will never get confused by later code to\n+\t# combine the features)\n+\tfilter=$(echo \"!one\" | git hash-object -w --stdin) &&\n+\tgit rev-list --objects --filter=sparse:oid=$filter HEAD >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t --objects --filter=sparse:oid=$filter HEAD >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_done\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391780","messageId":"20200214182216.GD150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 04/15] pack-bitmap: refuse to do a bitmap traversal with pathspecs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:16Z","receivedAt":"2020-02-14T18:22:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"rev-list has refused to use bitmaps with pathspec limiting since\nc8a70d3509 (rev-list: disable --use-bitmap-index when pruning commits,\n2015-07-01). But this is true not just for rev-list, but for anyone who\ncalls prepare_bitmap_walk(); the code isn't equipped to handle this\ncase. We never noticed because the only other callers would never pass\na pathspec limiter.\n\nBut let's push the check down into prepare_bitmap_walk() anyway. That's\na more logical place for it to live, as callers shouldn't need to know\nthe details (and must be prepared to fall back to a regular traversal\nanyway, since there might not be bitmaps in the repository).\n\nIt would also prepare us for a day where this case _is_ handled, but\nthat's pretty unlikely. E.g., we could use bitmaps to generate the set\nof commits, and then diff each commit to see if it matches the pathspec.\nThat would be slightly faster than a naive traversal that actually walks\nthe commits. But you'd probably do better still to make use of the newer\ncommit-graph feature to make walking the commits very cheap.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 2 +-\n pack-bitmap.c | 12 +++++++++++-\n 2 files changed, 12 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex bce406bd1e..4cb5a52dee 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -533,7 +533,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (show_progress)\n \t\tprogress = start_delayed_progress(show_progress, 0);\n \n-\tif (use_bitmap_index && !revs.prune) {\n+\tif (use_bitmap_index) {\n \t\tif (revs.count && !revs.left_right && !revs.cherry_mark) {\n \t\t\tuint32_t commit_count;\n \t\t\tint max_count = revs.max_count;\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 6c06099dc7..a97b717e55 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -715,9 +715,19 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \tstruct bitmap *wants_bitmap = NULL;\n \tstruct bitmap *haves_bitmap = NULL;\n \n-\tstruct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));\n+\tstruct bitmap_index *bitmap_git;\n+\n+\t/*\n+\t * We can't do pathspec limiting with bitmaps, because we don't know\n+\t * which commits are associated with which object changes (let alone\n+\t * even which objects are associated with which paths).\n+\t */\n+\tif (revs->prune)\n+\t\treturn NULL;\n+\n \t/* try to open a bitmapped pack, but don't parse it yet\n \t * because we may not need to use it */\n+\tbitmap_git = xcalloc(1, sizeof(*bitmap_git));\n \tif (open_pack_bitmap(revs->repo, bitmap_git) < 0)\n \t\tgoto cleanup;\n \n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391781","messageId":"20200214182218.GE150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 05/15] rev-list: factor out bitmap-optimized routines","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:18Z","receivedAt":"2020-02-14T18:22:26Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"There are a few operations in rev-list that are optimized for bitmaps.\nRather than having the code inline in cmd_rev_list(), let's move them\ninto helpers. This not only makes the flow of the main function simpler,\nbut it lets us replace the complex \"can we do the optimization?\"\nconditionals with a series of early returns from the functions. That\nalso makes it easy to add comments explaining those conditions.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 88 +++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 67 insertions(+), 21 deletions(-)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 4cb5a52dee..38c5ca5603 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -364,6 +364,69 @@ static inline int parse_missing_action_value(const char *value)\n \treturn 0;\n }\n \n+static int try_bitmap_count(struct rev_info *revs)\n+{\n+\tuint32_t commit_count;\n+\tint max_count;\n+\tstruct bitmap_index *bitmap_git;\n+\n+\t/* This function only handles counting, not general traversal. */\n+\tif (!revs->count)\n+\t\treturn -1;\n+\n+\t/*\n+\t * A bitmap result can't know left/right, etc, because we don't\n+\t * actually traverse.\n+\t */\n+\tif (revs->left_right || revs->cherry_mark)\n+\t\treturn -1;\n+\n+\t/*\n+\t * This must be saved before doing any walking, since the revision\n+\t * machinery will count it down to zero while traversing.\n+\t */\n+\tmax_count = revs->max_count;\n+\n+\tbitmap_git = prepare_bitmap_walk(revs);\n+\tif (!bitmap_git)\n+\t\treturn -1;\n+\n+\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n+\tif (max_count >= 0 && max_count < commit_count)\n+\t\tcommit_count = max_count;\n+\n+\tprintf(\"%d\\n\", commit_count);\n+\tfree_bitmap_index(bitmap_git);\n+\treturn 0;\n+}\n+\n+static int try_bitmap_traversal(struct rev_info *revs)\n+{\n+\tstruct bitmap_index *bitmap_git;\n+\n+\t/*\n+\t * We can't use a bitmap result with a traversal limit, since the set\n+\t * of commits we'd get would be essentially random.\n+\t */\n+\tif (revs->max_count >= 0)\n+\t\treturn -1;\n+\n+\t/*\n+\t * Our bitmap result will return all objects, and we're not\n+\t * yet prepared to show only particular types.\n+\t */\n+\tif (!revs->tag_objects || !revs->tree_objects || !revs->blob_objects)\n+\t\treturn -1;\n+\n+\tbitmap_git = prepare_bitmap_walk(revs);\n+\tif (!bitmap_git)\n+\t\treturn -1;\n+\n+\ttraverse_bitmap_commit_list(bitmap_git, &show_object_fast);\n+\tfree_bitmap_index(bitmap_git);\n+\treturn 0;\n+}\n+\n int cmd_rev_list(int argc, const char **argv, const char *prefix)\n {\n \tstruct rev_info revs;\n@@ -534,27 +597,10 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\tprogress = start_delayed_progress(show_progress, 0);\n \n \tif (use_bitmap_index) {\n-\t\tif (revs.count && !revs.left_right && !revs.cherry_mark) {\n-\t\t\tuint32_t commit_count;\n-\t\t\tint max_count = revs.max_count;\n-\t\t\tstruct bitmap_index *bitmap_git;\n-\t\t\tif ((bitmap_git = prepare_bitmap_walk(&revs))) {\n-\t\t\t\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n-\t\t\t\tif (max_count >= 0 && max_count < commit_count)\n-\t\t\t\t\tcommit_count = max_count;\n-\t\t\t\tprintf(\"%d\\n\", commit_count);\n-\t\t\t\tfree_bitmap_index(bitmap_git);\n-\t\t\t\treturn 0;\n-\t\t\t}\n-\t\t} else if (revs.max_count < 0 &&\n-\t\t\t revs.tag_objects && revs.tree_objects && revs.blob_objects) {\n-\t\t\tstruct bitmap_index *bitmap_git;\n-\t\t\tif ((bitmap_git = prepare_bitmap_walk(&revs))) {\n-\t\t\t\ttraverse_bitmap_commit_list(bitmap_git, &show_object_fast);\n-\t\t\t\tfree_bitmap_index(bitmap_git);\n-\t\t\t\treturn 0;\n-\t\t\t}\n-\t\t}\n+\t\tif (!try_bitmap_count(&revs))\n+\t\t\treturn 0;\n+\t\tif (!try_bitmap_traversal(&revs))\n+\t\t\treturn 0;\n \t}\n \n \tif (prepare_revision_walk(&revs))\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391782","messageId":"20200214182220.GF150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:20Z","receivedAt":"2020-02-14T18:22:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The current behavior from \"rev-list --count --objects\" is nonsensical:\nwe enumerate all of the objects except commits, but then give a count of\ncommits. This wasn't planned, and is just what the code happens to do.\n\nInstead, let's give the answer the user almost certainly wanted: the\nfull count of objects.\n\nNote that there are more complicated cases around cherry-marking, etc.\nWe'll punt on those for now, but let the user know that we can't produce\nan answer (rather than giving them something useless).\n\nWe'll test both the new feature as well as a vanilla --count of commits,\nsince that surprisingly doesn't seem to be covered in the existing\ntests.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 13 +++++++++++++\n t/t6000-rev-list-misc.sh | 12 ++++++++++++\n 2 files changed, 25 insertions(+)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 38c5ca5603..9452123988 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -253,11 +253,19 @@ static int finish_object(struct object *obj, const char *name, void *cb_data)\n static void show_object(struct object *obj, const char *name, void *cb_data)\n {\n \tstruct rev_list_info *info = cb_data;\n+\tstruct rev_info *revs = info->revs;\n+\n \tif (finish_object(obj, name, cb_data))\n \t\treturn;\n \tdisplay_progress(progress, ++progress_counter);\n \tif (info->flags & REV_LIST_QUIET)\n \t\treturn;\n+\n+\tif (revs->count) {\n+\t\trevs->count_right++;\n+\t\treturn;\n+\t}\n+\n \tif (arg_show_object_names)\n \t\tshow_object_with_name(stdout, obj, name);\n \telse\n@@ -584,6 +592,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \tif (revs.show_notes)\n \t\tdie(_(\"rev-list does not support display of notes\"));\n \n+\tif (revs.count &&\n+\t (revs.tag_objects || revs.tree_objects || revs.blob_objects) &&\n+\t (revs.left_right || revs.cherry_mark))\n+\t\tdie(_(\"marked counting is incompatible with --objects\"));\n+\n \tif (filter_options.choice)\n \t\tuse_bitmap_index = 0;\n \ndiff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh\nindex b8cf82349b..383f2c457d 100755\n--- a/t/t6000-rev-list-misc.sh\n+++ b/t/t6000-rev-list-misc.sh\n@@ -148,4 +148,16 @@ test_expect_success 'rev-list --end-of-options' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'rev-list --count' '\n+\tcount=$(git rev-list --count HEAD) &&\n+\tgit rev-list HEAD >actual &&\n+\ttest_line_count = $count actual\n+'\n+\n+test_expect_success 'rev-list --count --objects' '\n+\tcount=$(git rev-list --count --objects HEAD) &&\n+\tgit rev-list --objects HEAD >actual &&\n+\ttest_line_count = $count actual\n+'\n+\n test_done\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391783","messageId":"20200214182225.GH150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 08/15] t5310: factor out bitmap traversal comparison","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:25Z","receivedAt":"2020-02-14T18:22:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We check the results of \"rev-list --use-bitmap-index\" by comparing it to\nthe same traversal without the bitmap option. However, this is a little\ntricky to do because of some output differences (see the included\ncomment for details). Let's pull this out into a helper function, since\nwe'll be adding some similar tests.\n\nWhile we're at it, let's also try to confirm that the bitmap output did\nindeed use bitmaps. Since the code internally falls back to the\nnon-bitmap path in some cases, the tests are at risk of becoming trivial\nnoops.\n\nThis is a bit fragile, as not all outputs will differ (e.g., looking at\nonly the commits from a fully-bitmapped pack will end up exactly the\nsame as the normal traversal order, since it also matches the pack\norder). So we'll provide an escape hatch by which tests can disable this\ncheck (which should only be used after manually confirming that bitmaps\nkicked in).\n\nSigned-off-by: Jeff King \n---\n t/t5310-pack-bitmaps.sh | 10 +++-------\n t/test-lib-functions.sh | 27 +++++++++++++++++++++++++++\n 2 files changed, 30 insertions(+), 7 deletions(-)\n\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 7ba7d294a5..b8645ae070 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -81,13 +81,9 @@ rev_list_tests() {\n \t'\n \n \ttest_expect_success \"enumerate --objects ($state)\" '\n-\t\tgit rev-list --objects --use-bitmap-index HEAD >tmp &&\n-\t\tcut -d\" \" -f1 tmp2 &&\n-\t\tsort actual &&\n-\t\tgit rev-list --objects HEAD >tmp &&\n-\t\tcut -d\" \" -f1 tmp2 &&\n-\t\tsort expect &&\n-\t\ttest_cmp expect actual\n+\t\tgit rev-list --objects --use-bitmap-index HEAD >actual &&\n+\t\tgit rev-list --objects HEAD >expect &&\n+\t\ttest_bitmap_traversal expect actual\n \t'\n \n \ttest_expect_success \"bitmap --objects handles non-commit objects ($state)\" '\ndiff --git a/t/test-lib-functions.sh b/t/test-lib-functions.sh\nindex 284c52d076..352c213d52 100644\n--- a/t/test-lib-functions.sh\n+++ b/t/test-lib-functions.sh\n@@ -1516,3 +1516,30 @@ test_set_port () {\n \tport=$(($port + ${GIT_TEST_STRESS_JOB_NR:-0}))\n \teval $var=$port\n }\n+\n+# Compare a file containing rev-list bitmap traversal output to its non-bitmap\n+# counterpart. You can't just use test_cmp for this, because the two produce\n+# subtly different output:\n+#\n+# - regular output is in traversal order, whereas bitmap is split by type,\n+# with non-packed objects at the end\n+#\n+# - regular output has a space and the pathname appended to non-commit\n+# objects; bitmap output omits this\n+#\n+# This function normalizes and compares the two. The second file should\n+# always be the bitmap output.\n+test_bitmap_traversal () {\n+\tif test \"$1\" = \"--no-confirm-bitmaps\"\n+\tthen\n+\t\tshift\n+\telif cmp \"$1\" \"$2\"\n+\tthen\n+\t\techo >&2 \"identical raw outputs; are you sure bitmaps were used?\"\n+\t\treturn 1\n+\tfi &&\n+\tcut -d' ' -f1 \"$1\" | sort >\"$1.normalized\" &&\n+\tsort \"$2\" >\"$2.normalized\" &&\n+\ttest_cmp \"$1.normalized\" \"$2.normalized\" &&\n+\trm -f \"$1.normalized\" \"$2.normalized\"\n+}\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391784","messageId":"20200214182222.GG150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 07/15] rev-list: allow bitmaps when counting objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:22Z","receivedAt":"2020-02-14T18:22:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"The prior commit taught \"--count --objects\" to work without bitmaps. We\nshould be able to get the same answer much more quickly with bitmaps.\n\nNote that we punt on the max_count case here. This perhaps _could_ be\nmade to work if we find all of the boundary commits and treat them as\nUNINTERESTING, subtracting them (and their reachable objects) from the\nset we return. That implies an actual commit traversal, but we'd still\nbe faster due to avoiding opening up any trees. Given the complexity and\nthe fact that anyone is unlikely to want this, it makes sense to just\nfall back to the non-bitmap case for now.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 21 ++++++++++++++++++---\n t/t5310-pack-bitmaps.sh | 6 ++++++\n 2 files changed, 24 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 9452123988..70f3207ecc 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -374,7 +374,10 @@ static inline int parse_missing_action_value(const char *value)\n \n static int try_bitmap_count(struct rev_info *revs)\n {\n-\tuint32_t commit_count;\n+\tuint32_t commit_count = 0,\n+\t\t tag_count = 0,\n+\t\t tree_count = 0,\n+\t\t blob_count = 0;\n \tint max_count;\n \tstruct bitmap_index *bitmap_git;\n \n@@ -389,6 +392,15 @@ static int try_bitmap_count(struct rev_info *revs)\n \tif (revs->left_right || revs->cherry_mark)\n \t\treturn -1;\n \n+\t/*\n+\t * If we're counting reachable objects, we can't handle a max count of\n+\t * commits to traverse, since we don't know which objects go with which\n+\t * commit.\n+\t */\n+\tif (revs->max_count >= 0 &&\n+\t (revs->tag_objects || revs->tree_objects || revs->blob_objects))\n+\t\treturn -1;\n+\n \t/*\n \t * This must be saved before doing any walking, since the revision\n \t * machinery will count it down to zero while traversing.\n@@ -399,11 +411,14 @@ static int try_bitmap_count(struct rev_info *revs)\n \tif (!bitmap_git)\n \t\treturn -1;\n \n-\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n+\tcount_bitmap_commit_list(bitmap_git, &commit_count,\n+\t\t\t\t revs->tree_objects ? &tree_count : NULL,\n+\t\t\t\t revs->blob_objects ? &blob_count : NULL,\n+\t\t\t\t revs->tag_objects ? &tag_count : NULL);\n \tif (max_count >= 0 && max_count < commit_count)\n \t\tcommit_count = max_count;\n \n-\tprintf(\"%d\\n\", commit_count);\n+\tprintf(\"%d\\n\", commit_count + tree_count + blob_count + tag_count);\n \tfree_bitmap_index(bitmap_git);\n \treturn 0;\n }\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 6640329ebf..7ba7d294a5 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -74,6 +74,12 @@ rev_list_tests() {\n \t\ttest_cmp expect actual\n \t'\n \n+\ttest_expect_success \"counting objects via bitmap ($state)\" '\n+\t\tgit rev-list --count --objects HEAD >expect &&\n+\t\tgit rev-list --use-bitmap-index --count --objects HEAD >actual &&\n+\t\ttest_cmp expect actual\n+\t'\n+\n \ttest_expect_success \"enumerate --objects ($state)\" '\n \t\tgit rev-list --objects --use-bitmap-index HEAD >tmp &&\n \t\tcut -d\" \" -f1 tmp2 &&\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391785","messageId":"20200214182227.GI150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 09/15] rev-list: allow commit-only bitmap traversals","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:27Z","receivedAt":"2020-02-14T18:22:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Ever since we added reachability bitmap support, we've been able to use\nit with rev-list to get the full list of objects, like:\n\n git rev-list --objects --use-bitmap-index --all\n\nBut you can't do so without --objects, since we weren't ready to just\nshow the commits. However, the internals of the bitmap code are mostly\nready for this: they avoid opening up trees when walking to fill in the\nbitmaps. We just need to actually pass in the rev_info to\ntraverse_bitmap_commit_list() so it knows which types to bother\ntriggering our callback for.\n\nFor completeness, the perf test now covers both the existing --objects\ncase, as well as the new commits-only behavior (the objects one got way\nfaster when we introduced bitmaps, but obviously isn't improved now).\n\nHere are numbers for linux.git:\n\n Test HEAD^ HEAD\n ------------------------------------------------------------------------\n 5310.7: rev-list (commits) 8.29(8.10+0.19) 1.76(1.72+0.04) -78.8%\n 5310.8: rev-list (objects) 8.06(7.94+0.12) 8.14(7.94+0.13) +1.0%\n\nThat run was cheating a little, as I didn't have any commit-graph in the\nrepository, and we'd built it by default these days when running git-gc.\nHere are numbers with a commit-graph:\n\n Test HEAD^ HEAD\n ------------------------------------------------------------------------\n 5310.7: rev-list (commits) 0.70(0.58+0.12) 0.51(0.46+0.04) -27.1%\n 5310.8: rev-list (objects) 6.20(6.09+0.10) 6.27(6.16+0.11) +1.1%\n\nStill an improvement, but a lot less impressive.\n\nWe could have the perf script remove any commit-graph to show the\nout-sized effect, but it probably makes sense to leave it in what would\nbe a more typical setup.\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 3 ++-\n builtin/rev-list.c | 9 +--------\n pack-bitmap.c | 20 +++++++++++++++-----\n pack-bitmap.h | 1 +\n reachable.c | 2 +-\n t/perf/p5310-pack-bitmaps.sh | 8 ++++++++\n t/t5310-pack-bitmaps.sh | 6 ++++++\n 7 files changed, 34 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 393c20a2d7..06915ebe7f 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3054,7 +3054,8 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n \t\tdisplay_progress(progress_state, nr_result);\n \t}\n \n-\ttraverse_bitmap_commit_list(bitmap_git, &add_object_entry_from_bitmap);\n+\ttraverse_bitmap_commit_list(bitmap_git, revs,\n+\t\t\t\t &add_object_entry_from_bitmap);\n \treturn 0;\n }\n \ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 70f3207ecc..937324cef0 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -434,18 +434,11 @@ static int try_bitmap_traversal(struct rev_info *revs)\n \tif (revs->max_count >= 0)\n \t\treturn -1;\n \n-\t/*\n-\t * Our bitmap result will return all objects, and we're not\n-\t * yet prepared to show only particular types.\n-\t */\n-\tif (!revs->tag_objects || !revs->tree_objects || !revs->blob_objects)\n-\t\treturn -1;\n-\n \tbitmap_git = prepare_bitmap_walk(revs);\n \tif (!bitmap_git)\n \t\treturn -1;\n \n-\ttraverse_bitmap_commit_list(bitmap_git, &show_object_fast);\n+\ttraverse_bitmap_commit_list(bitmap_git, revs, &show_object_fast);\n \tfree_bitmap_index(bitmap_git);\n \treturn 0;\n }\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex a97b717e55..2fbc748b19 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -599,6 +599,7 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n }\n \n static void show_extended_objects(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct rev_info *revs,\n \t\t\t\t show_reachable_fn show_reach)\n {\n \tstruct bitmap *objects = bitmap_git->result;\n@@ -612,6 +613,11 @@ static void show_extended_objects(struct bitmap_index *bitmap_git,\n \t\t\tcontinue;\n \n \t\tobj = eindex->objects[i];\n+\t\tif ((obj->type == OBJ_BLOB && !revs->blob_objects) ||\n+\t\t (obj->type == OBJ_TREE && !revs->tree_objects) ||\n+\t\t (obj->type == OBJ_TAG && !revs->tag_objects))\n+\t\t\tcontinue;\n+\n \t\tshow_reach(&obj->oid, obj->type, 0, eindex->hashes[i], NULL, 0);\n \t}\n }\n@@ -872,16 +878,20 @@ int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n }\n \n void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct rev_info *revs,\n \t\t\t\t show_reachable_fn show_reachable)\n {\n \tassert(bitmap_git->result);\n \n \tshow_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable);\n-\tshow_objects_for_type(bitmap_git, OBJ_TREE, show_reachable);\n-\tshow_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable);\n-\tshow_objects_for_type(bitmap_git, OBJ_TAG, show_reachable);\n-\n-\tshow_extended_objects(bitmap_git, show_reachable);\n+\tif (revs->tree_objects)\n+\t\tshow_objects_for_type(bitmap_git, OBJ_TREE, show_reachable);\n+\tif (revs->blob_objects)\n+\t\tshow_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable);\n+\tif (revs->tag_objects)\n+\t\tshow_objects_for_type(bitmap_git, OBJ_TAG, show_reachable);\n+\n+\tshow_extended_objects(bitmap_git, revs, show_reachable);\n }\n \n static uint32_t count_object_type(struct bitmap_index *bitmap_git,\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 466c5afa09..b0c06a212e 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -44,6 +44,7 @@ struct bitmap_index *prepare_bitmap_git(struct repository *r);\n void count_bitmap_commit_list(struct bitmap_index *, uint32_t *commits,\n \t\t\t uint32_t *trees, uint32_t *blobs, uint32_t *tags);\n void traverse_bitmap_commit_list(struct bitmap_index *,\n+\t\t\t\t struct rev_info *revs,\n \t\t\t\t show_reachable_fn show_reachable);\n void test_bitmap_walk(struct rev_info *revs);\n struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs);\ndiff --git a/reachable.c b/reachable.c\nindex 8f50235b28..0919f025c4 100644\n--- a/reachable.c\n+++ b/reachable.c\n@@ -225,7 +225,7 @@ void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n \n \tbitmap_git = prepare_bitmap_walk(revs);\n \tif (bitmap_git) {\n-\t\ttraverse_bitmap_commit_list(bitmap_git, mark_object_seen);\n+\t\ttraverse_bitmap_commit_list(bitmap_git, revs, mark_object_seen);\n \t\tfree_bitmap_index(bitmap_git);\n \t\treturn;\n \t}\ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex 6a3a42531b..e52f66ec9e 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -39,6 +39,14 @@ test_perf 'pack to file (bitmap)' '\n \tgit pack-objects --use-bitmap-index --all pack1b /dev/null\n '\n \n+test_perf 'rev-list (commits)' '\n+\tgit rev-list --all --use-bitmap-index >/dev/null\n+'\n+\n+test_perf 'rev-list (objects)' '\n+\tgit rev-list --all --use-bitmap-index --objects >/dev/null\n+'\n+\n test_expect_success 'create partial bitmap state' '\n \t# pick a commit to represent the repo tip in the past\n \tcutoff=$(git rev-list HEAD~100 -1) &&\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex b8645ae070..2c64d0c441 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -80,6 +80,12 @@ rev_list_tests() {\n \t\ttest_cmp expect actual\n \t'\n \n+\ttest_expect_success \"enumerate commits ($state)\" '\n+\t\tgit rev-list --use-bitmap-index HEAD >actual &&\n+\t\tgit rev-list HEAD >expect &&\n+\t\ttest_bitmap_traversal --no-confirm-bitmaps expect actual\n+\t'\n+\n \ttest_expect_success \"enumerate --objects ($state)\" '\n \t\tgit rev-list --objects --use-bitmap-index HEAD >actual &&\n \t\tgit rev-list --objects HEAD >expect &&\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391786","messageId":"20200214182229.GJ150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 10/15] pack-bitmap: basic noop bitmap filter infrastructure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:29Z","receivedAt":"2020-02-14T18:22:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Currently you can't use object filters with bitmaps, but we plan to\nsupport at least some filters with bitmaps. Let's introduce some\ninfrastructure that will help us do that:\n\n - prepare_bitmap_walk() now accepts a list_objects_filter_options\n parameter (which can be NULL for no filtering; all the current\n callers pass this)\n\n - we'll bail early if the filter is incompatible with bitmaps (just as\n we would if there were no bitmaps at all). Currently all filters are\n incompatible.\n\n - we'll filter the resulting bitmap; since there are no supported\n filters yet, this is always a noop.\n\nThere should be no behavior change yet, but we'll support some actual\nfilters in a future patch.\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 2 +-\n builtin/rev-list.c | 4 ++--\n pack-bitmap.c | 26 +++++++++++++++++++++++++-\n pack-bitmap.h | 4 +++-\n reachable.c | 2 +-\n 5 files changed, 32 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 06915ebe7f..2bb81c2133 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3040,7 +3040,7 @@ static int pack_options_allow_reuse(void)\n \n static int get_object_list_from_bitmap(struct rev_info *revs)\n {\n-\tif (!(bitmap_git = prepare_bitmap_walk(revs)))\n+\tif (!(bitmap_git = prepare_bitmap_walk(revs, NULL)))\n \t\treturn -1;\n \n \tif (pack_options_allow_reuse() &&\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 937324cef0..6ff5e175fa 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -407,7 +407,7 @@ static int try_bitmap_count(struct rev_info *revs)\n \t */\n \tmax_count = revs->max_count;\n \n-\tbitmap_git = prepare_bitmap_walk(revs);\n+\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n \tif (!bitmap_git)\n \t\treturn -1;\n \n@@ -434,7 +434,7 @@ static int try_bitmap_traversal(struct rev_info *revs)\n \tif (revs->max_count >= 0)\n \t\treturn -1;\n \n-\tbitmap_git = prepare_bitmap_walk(revs);\n+\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n \tif (!bitmap_git)\n \t\treturn -1;\n \ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 2fbc748b19..48c8694f92 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -12,6 +12,7 @@\n #include \"packfile.h\"\n #include \"repository.h\"\n #include \"object-store.h\"\n+#include \"list-objects-filter-options.h\"\n \n /*\n * An entry on the bitmap index, representing the bitmap for a given\n@@ -711,7 +712,25 @@ static int in_bitmapped_pack(struct bitmap_index *bitmap_git,\n \treturn 0;\n }\n \n-struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n+static int filter_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t struct object_list *tip_objects,\n+\t\t\t struct bitmap *to_filter,\n+\t\t\t struct list_objects_filter_options *filter)\n+{\n+\tif (!filter || filter->choice == LOFC_DISABLED)\n+\t\treturn 0;\n+\n+\t/* filter choice not handled */\n+\treturn -1;\n+}\n+\n+static int can_filter_bitmap(struct list_objects_filter_options *filter)\n+{\n+\treturn !filter_bitmap(NULL, NULL, NULL, filter);\n+}\n+\n+struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n+\t\t\t\t\t struct list_objects_filter_options *filter)\n {\n \tunsigned int i;\n \n@@ -731,6 +750,9 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \tif (revs->prune)\n \t\treturn NULL;\n \n+\tif (!can_filter_bitmap(filter))\n+\t\treturn NULL;\n+\n \t/* try to open a bitmapped pack, but don't parse it yet\n \t * because we may not need to use it */\n \tbitmap_git = xcalloc(1, sizeof(*bitmap_git));\n@@ -800,6 +822,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \tif (haves_bitmap)\n \t\tbitmap_and_not(wants_bitmap, haves_bitmap);\n \n+\tfilter_bitmap(bitmap_git, wants, wants_bitmap, filter);\n+\n \tbitmap_git->result = wants_bitmap;\n \tbitmap_git->haves = haves_bitmap;\n \ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex b0c06a212e..956775d0bb 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -8,6 +8,7 @@\n struct commit;\n struct repository;\n struct rev_info;\n+struct list_objects_filter_options;\n \n static const char BITMAP_IDX_SIGNATURE[] = {'B', 'I', 'T', 'M'};\n \n@@ -47,7 +48,8 @@ void traverse_bitmap_commit_list(struct bitmap_index *,\n \t\t\t\t struct rev_info *revs,\n \t\t\t\t show_reachable_fn show_reachable);\n void test_bitmap_walk(struct rev_info *revs);\n-struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs);\n+struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n+\t\t\t\t\t struct list_objects_filter_options *filter);\n int reuse_partial_packfile_from_bitmap(struct bitmap_index *,\n \t\t\t\t struct packed_git **packfile,\n \t\t\t\t uint32_t *entries, off_t *up_to);\ndiff --git a/reachable.c b/reachable.c\nindex 0919f025c4..77a60c70a5 100644\n--- a/reachable.c\n+++ b/reachable.c\n@@ -223,7 +223,7 @@ void mark_reachable_objects(struct rev_info *revs, int mark_reflog,\n \tcp.progress = progress;\n \tcp.count = 0;\n \n-\tbitmap_git = prepare_bitmap_walk(revs);\n+\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n \tif (bitmap_git) {\n \t\ttraverse_bitmap_commit_list(bitmap_git, revs, mark_object_seen);\n \t\tfree_bitmap_index(bitmap_git);\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391787","messageId":"20200214182211.GB150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 02/15] pack-bitmap: fix leak of haves/wants object lists","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:11Z","receivedAt":"2020-02-14T18:22:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we do a bitmap-aware revision traversal, we create an object_list\nfor each of the \"haves\" and \"wants\" tips. After creating the result\nbitmaps these are no longer needed or used, but we never free the list\nmemory.\n\nSigned-off-by: Jeff King \n---\n object.c | 9 +++++++++\n object.h | 2 ++\n pack-bitmap.c | 5 +++++\n 3 files changed, 16 insertions(+)\n\ndiff --git a/object.c b/object.c\nindex 142ef69399..4d11949b38 100644\n--- a/object.c\n+++ b/object.c\n@@ -307,6 +307,15 @@ int object_list_contains(struct object_list *list, struct object *obj)\n \treturn 0;\n }\n \n+void object_list_free(struct object_list **list)\n+{\n+\twhile (*list) {\n+\t\tstruct object_list *p = *list;\n+\t\t*list = p->next;\n+\t\tfree(p);\n+\t}\n+}\n+\n /*\n * A zero-length string to which object_array_entry::name can be\n * initialized without requiring a malloc/free.\ndiff --git a/object.h b/object.h\nindex 25f5ab3d54..2dbabfca0a 100644\n--- a/object.h\n+++ b/object.h\n@@ -151,6 +151,8 @@ struct object_list *object_list_insert(struct object *item,\n \n int object_list_contains(struct object_list *list, struct object *obj);\n \n+void object_list_free(struct object_list **list);\n+\n /* Object array handling .. */\n void add_object_array(struct object *obj, const char *name, struct object_array *array);\n void add_object_array_with_path(struct object *obj, const char *name, struct object_array *array, unsigned mode, const char *path);\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 9ca356ee29..6c06099dc7 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -787,10 +787,15 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \tbitmap_git->result = wants_bitmap;\n \tbitmap_git->haves = haves_bitmap;\n \n+\tobject_list_free(&wants);\n+\tobject_list_free(&haves);\n+\n \treturn bitmap_git;\n \n cleanup:\n \tfree_bitmap_index(bitmap_git);\n+\tobject_list_free(&wants);\n+\tobject_list_free(&haves);\n \treturn NULL;\n }\n \n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391788","messageId":"20200214182232.GK150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 11/15] rev-list: use bitmap filters for traversal","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:32Z","receivedAt":"2020-02-14T18:22:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This just passes the filter-options struct to prepare_bitmap_walk().\nSince the bitmap code doesn't actually support any filters yet, it will\nfallback to the non-bitmap code if any --filter is specified. But this\nlets us exercise that rejection code path, as well as getting us ready\nto test filters via rev-list when we _do_ support them.\n\nSigned-off-by: Jeff King \n---\n builtin/rev-list.c | 17 ++++++++---------\n 1 file changed, 8 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/rev-list.c b/builtin/rev-list.c\nindex 6ff5e175fa..35e14ad2ed 100644\n--- a/builtin/rev-list.c\n+++ b/builtin/rev-list.c\n@@ -372,7 +372,8 @@ static inline int parse_missing_action_value(const char *value)\n \treturn 0;\n }\n \n-static int try_bitmap_count(struct rev_info *revs)\n+static int try_bitmap_count(struct rev_info *revs,\n+\t\t\t struct list_objects_filter_options *filter)\n {\n \tuint32_t commit_count = 0,\n \t\t tag_count = 0,\n@@ -407,7 +408,7 @@ static int try_bitmap_count(struct rev_info *revs)\n \t */\n \tmax_count = revs->max_count;\n \n-\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n+\tbitmap_git = prepare_bitmap_walk(revs, filter);\n \tif (!bitmap_git)\n \t\treturn -1;\n \n@@ -423,7 +424,8 @@ static int try_bitmap_count(struct rev_info *revs)\n \treturn 0;\n }\n \n-static int try_bitmap_traversal(struct rev_info *revs)\n+static int try_bitmap_traversal(struct rev_info *revs,\n+\t\t\t\tstruct list_objects_filter_options *filter)\n {\n \tstruct bitmap_index *bitmap_git;\n \n@@ -434,7 +436,7 @@ static int try_bitmap_traversal(struct rev_info *revs)\n \tif (revs->max_count >= 0)\n \t\treturn -1;\n \n-\tbitmap_git = prepare_bitmap_walk(revs, NULL);\n+\tbitmap_git = prepare_bitmap_walk(revs, filter);\n \tif (!bitmap_git)\n \t\treturn -1;\n \n@@ -605,9 +607,6 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t (revs.left_right || revs.cherry_mark))\n \t\tdie(_(\"marked counting is incompatible with --objects\"));\n \n-\tif (filter_options.choice)\n-\t\tuse_bitmap_index = 0;\n-\n \tsave_commit_buffer = (revs.verbose_header ||\n \t\t\t revs.grep_filter.pattern_list ||\n \t\t\t revs.grep_filter.header_list);\n@@ -618,9 +617,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n \t\tprogress = start_delayed_progress(show_progress, 0);\n \n \tif (use_bitmap_index) {\n-\t\tif (!try_bitmap_count(&revs))\n+\t\tif (!try_bitmap_count(&revs, &filter_options))\n \t\t\treturn 0;\n-\t\tif (!try_bitmap_traversal(&revs))\n+\t\tif (!try_bitmap_traversal(&revs, &filter_options))\n \t\t\treturn 0;\n \t}\n \n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391789","messageId":"20200214182234.GL150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 12/15] bitmap: add bitmap_unset() function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:34Z","receivedAt":"2020-02-14T18:22:45Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We've never needed to unset an individual bit in a bitmap until now.\nTypically they start with all bits unset and we bitmap_set() them, or we\nare applying another bitmap as a mask. But the easiest way to apply an\nobject filter to a bitmap result will be to unset the individual bits.\n\nSigned-off-by: Jeff King \n---\n ewah/bitmap.c | 8 ++++++++\n ewah/ewok.h | 1 +\n 2 files changed, 9 insertions(+)\n\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex 52f1178db4..1c31b3e249 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -45,6 +45,14 @@ void bitmap_set(struct bitmap *self, size_t pos)\n \tself->words[block] |= EWAH_MASK(pos);\n }\n \n+void bitmap_unset(struct bitmap *self, size_t pos)\n+{\n+\tsize_t block = EWAH_BLOCK(pos);\n+\n+\tif (block < self->word_alloc)\n+\t\tself->words[block] &= ~EWAH_MASK(pos);\n+}\n+\n int bitmap_get(struct bitmap *self, size_t pos)\n {\n \tsize_t block = EWAH_BLOCK(pos);\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 84b2a29faa..59f4ef7c4f 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -173,6 +173,7 @@ struct bitmap {\n \n struct bitmap *bitmap_new(void);\n void bitmap_set(struct bitmap *self, size_t pos);\n+void bitmap_unset(struct bitmap *self, size_t pos);\n int bitmap_get(struct bitmap *self, size_t pos);\n void bitmap_reset(struct bitmap *self);\n void bitmap_free(struct bitmap *self);\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391790","messageId":"20200214182241.GO150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 15/15] pack-objects: support filters with bitmaps","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:41Z","receivedAt":"2020-02-14T18:22:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Just as rev-list recently learned to combine filters and bitmaps, let's\ndo the same for pack-objects. The infrastructure is all there; we just\nneed to pass along our filter options, and the pack-bitmap code will\ndecide to use bitmaps or not.\n\nThis unsurprisingly makes things faster for partial clones of large\nrepositories (here we're cloning linux.git):\n\n Test HEAD^ HEAD\n ------------------------------------------------------------------------------\n 5310.11: simulated partial clone 38.94(37.28+5.87) 11.06(11.27+4.07) -71.6%\n\nSigned-off-by: Jeff King \n---\n builtin/pack-objects.c | 3 +--\n t/perf/p5310-pack-bitmaps.sh | 4 ++++\n t/t5310-pack-bitmaps.sh | 14 ++++++++++++++\n 3 files changed, 19 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 2bb81c2133..6bc9bc1ce2 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3040,7 +3040,7 @@ static int pack_options_allow_reuse(void)\n \n static int get_object_list_from_bitmap(struct rev_info *revs)\n {\n-\tif (!(bitmap_git = prepare_bitmap_walk(revs, NULL)))\n+\tif (!(bitmap_git = prepare_bitmap_walk(revs, &filter_options)))\n \t\treturn -1;\n \n \tif (pack_options_allow_reuse() &&\n@@ -3419,7 +3419,6 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (filter_options.choice) {\n \t\tif (!pack_to_stdout)\n \t\t\tdie(_(\"cannot use --filter without --stdout\"));\n-\t\tuse_bitmap_index = 0;\n \t}\n \n \t/*\ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex 8b43a545c1..7743f4f4c9 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -57,6 +57,10 @@ test_perf 'rev-list count with blob:limit=1k' '\n \t\t--filter=blob:limit=1k >/dev/null\n '\n \n+test_perf 'simulated partial clone' '\n+\tgit pack-objects --stdout --all --filter=blob:none /dev/null\n+'\n+\n test_expect_success 'create partial bitmap state' '\n \t# pick a commit to represent the repo tip in the past\n \tcutoff=$(git rev-list HEAD~100 -1) &&\ndiff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\nindex 2c64d0c441..8318781d2b 100755\n--- a/t/t5310-pack-bitmaps.sh\n+++ b/t/t5310-pack-bitmaps.sh\n@@ -107,6 +107,20 @@ test_expect_success 'clone from bitmapped repository' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'partial clone from bitmapped repository' '\n+\ttest_config uploadpack.allowfilter true &&\n+\tgit clone --no-local --bare --filter=blob:none . partial-clone.git &&\n+\t(\n+\t\tcd partial-clone.git &&\n+\t\tpack=$(echo objects/pack/*.pack) &&\n+\t\tgit verify-pack -v \"$pack\" >have &&\n+\t\tawk \"/blob/ { print \\$1 }\" blobs &&\n+\t\t# we expect this single blob because of the direct ref\n+\t\tgit rev-parse refs/tags/tagged-blob >expect &&\n+\t\ttest_cmp expect blobs\n+\t)\n+'\n+\n test_expect_success 'setup further non-bitmapped commits' '\n \ttest_commit_bulk --id=further 10\n '\n-- \n2.25.0.796.gcc29325708\n"},{"id":"391791","messageId":"20200214182239.GN150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 14/15] pack-bitmap: implement BLOB_LIMIT filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:39Z","receivedAt":"2020-02-14T18:22:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Just as the previous commit implemented BLOB_NONE, we can support\nBLOB_LIMIT filters by looking at the sizes of any blobs in the result\nand unsetting their bits as appropriate. This is slightly more expensive\nthan BLOB_NONE, but still produces a noticeable speedup (these results\nare on git.git):\n\n Test HEAD~2 HEAD\n ------------------------------------------------------------------------------------\n 5310.9: rev-list count with blob:none 1.80(1.77+0.02) 0.22(0.20+0.02) -87.8%\n 5310.10: rev-list count with blob:limit=1k 1.99(1.96+0.03) 0.29(0.25+0.03) -85.4%\n\nThe implementation is similar to the BLOB_NONE one, with the exception\nthat we have to go object-by-object while walking the blob-type bitmap\n(since we can't mask out the matches, but must look up the size\nindividually for each blob). The trick with using ctz64() is taken from\nshow_objects_for_type(), which likewise needs to find individual bits\n(but wants to quickly skip over big chunks without blobs).\n\nSigned-off-by: Jeff King \n---\n pack-bitmap.c | 80 ++++++++++++++++++++++++++++++\n t/perf/p5310-pack-bitmaps.sh | 5 ++\n t/t6113-rev-list-bitmap-filters.sh | 20 +++++++-\n 3 files changed, 104 insertions(+), 1 deletion(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex dcf8a9aadf..9d680065e4 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -779,6 +779,78 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,\n \tbitmap_free(tips);\n }\n \n+static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,\n+\t\t\t\t uint32_t pos)\n+{\n+\tstruct packed_git *pack = bitmap_git->pack;\n+\tunsigned long size;\n+\tstruct object_info oi = OBJECT_INFO_INIT;\n+\n+\toi.sizep = &size;\n+\n+\tif (pos < pack->num_objects) {\n+\t\tstruct revindex_entry *entry = &pack->revindex[pos];\n+\t\tif (packed_object_info(the_repository, pack,\n+\t\t\t\t entry->offset, &oi) < 0) {\n+\t\t\tstruct object_id oid;\n+\t\t\tnth_packed_object_oid(&oid, pack, entry->nr);\n+\t\t\tdie(_(\"unable to get size of %s\"), oid_to_hex(&oid));\n+\t\t}\n+\t} else {\n+\t\tstruct eindex *eindex = &bitmap_git->ext_index;\n+\t\tstruct object *obj = eindex->objects[pos - pack->num_objects];\n+\t\tif (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)\n+\t\t\tdie(_(\"unable to get size of %s\"), oid_to_hex(&obj->oid));\n+\t}\n+\n+\treturn size;\n+}\n+\n+static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct object_list *tip_objects,\n+\t\t\t\t struct bitmap *to_filter,\n+\t\t\t\t unsigned long limit)\n+{\n+\tstruct eindex *eindex = &bitmap_git->ext_index;\n+\tstruct bitmap *tips;\n+\tstruct ewah_iterator it;\n+\teword_t mask;\n+\tuint32_t i;\n+\n+\ttips = find_tip_blobs(bitmap_git, tip_objects);\n+\n+\tfor (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB);\n+\t i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);\n+\t i++) {\n+\t\teword_t word = to_filter->words[i] & mask;\n+\t\tunsigned offset;\n+\n+\t\tfor (offset = 0; offset < BITS_IN_EWORD; offset++) {\n+\t\t\tuint32_t pos;\n+\n+\t\t\tif ((word >> offset) == 0)\n+\t\t\t\tbreak;\n+\t\t\toffset += ewah_bit_ctz64(word >> offset);\n+\t\t\tpos = i * BITS_IN_EWORD + offset;\n+\n+\t\t\tif (!bitmap_get(tips, pos) &&\n+\t\t\t get_size_by_pos(bitmap_git, pos) >= limit)\n+\t\t\t\tbitmap_unset(to_filter, pos);\n+\t\t}\n+\t}\n+\n+\tfor (i = 0; i < eindex->count; i++) {\n+\t\tuint32_t pos = i + bitmap_git->pack->num_objects;\n+\t\tif (eindex->objects[i]->type == OBJ_BLOB &&\n+\t\t bitmap_get(to_filter, pos) &&\n+\t\t !bitmap_get(tips, pos) &&\n+\t\t get_size_by_pos(bitmap_git, pos) >= limit)\n+\t\t\tbitmap_unset(to_filter, pos);\n+\t}\n+\n+\tbitmap_free(tips);\n+}\n+\n static int filter_bitmap(struct bitmap_index *bitmap_git,\n \t\t\t struct object_list *tip_objects,\n \t\t\t struct bitmap *to_filter,\n@@ -794,6 +866,14 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,\n \t\treturn 0;\n \t}\n \n+\tif (filter->choice == LOFC_BLOB_LIMIT) {\n+\t\tif (bitmap_git)\n+\t\t\tfilter_bitmap_blob_limit(bitmap_git, tip_objects,\n+\t\t\t\t\t\t to_filter,\n+\t\t\t\t\t\t filter->blob_limit_value);\n+\t\treturn 0;\n+\t}\n+\n \t/* filter choice not handled */\n \treturn -1;\n }\ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex 936742314c..8b43a545c1 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -52,6 +52,11 @@ test_perf 'rev-list count with blob:none' '\n \t\t--filter=blob:none >/dev/null\n '\n \n+test_perf 'rev-list count with blob:limit=1k' '\n+\tgit rev-list --use-bitmap-index --count --objects --all \\\n+\t\t--filter=blob:limit=1k >/dev/null\n+'\n+\n test_expect_success 'create partial bitmap state' '\n \t# pick a commit to represent the repo tip in the past\n \tcutoff=$(git rev-list HEAD~100 -1) &&\ndiff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh\nindex f4e6d582f0..145603f124 100755\n--- a/t/t6113-rev-list-bitmap-filters.sh\n+++ b/t/t6113-rev-list-bitmap-filters.sh\n@@ -6,8 +6,10 @@ test_description='rev-list combining bitmaps and filters'\n test_expect_success 'set up bitmapped repo' '\n \t# one commit will have bitmaps, the other will not\n \ttest_commit one &&\n+\ttest_commit much-larger-blob-one &&\n \tgit repack -adb &&\n-\ttest_commit two\n+\ttest_commit two &&\n+\ttest_commit much-larger-blob-two\n '\n \n test_expect_success 'filters fallback to non-bitmap traversal' '\n@@ -35,4 +37,20 @@ test_expect_success 'blob:none filter with specified blob' '\n \ttest_bitmap_traversal expect actual\n '\n \n+test_expect_success 'blob:limit filter' '\n+\tgit rev-list --objects --filter=blob:limit=5 HEAD >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t --objects --filter=blob:limit=5 HEAD >actual &&\n+\ttest_bitmap_traversal expect actual\n+'\n+\n+test_expect_success 'blob:limit filter with specified blob' '\n+\tgit rev-list --objects --filter=blob:limit=5 \\\n+\t\t HEAD HEAD:much-larger-blob-two.t >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t --objects --filter=blob:limit=5 \\\n+\t\t HEAD HEAD:much-larger-blob-two.t >actual &&\n+\ttest_bitmap_traversal expect actual\n+'\n+\n test_done\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391792","messageId":"20200214182236.GM150965@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200214182147.GA654525@coredump.intra.peff.net","subject":"[PATCH v2 13/15] pack-bitmap: implement BLOB_NONE filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T18:22:36Z","receivedAt":"2020-02-14T18:22:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"We can easily support BLOB_NONE filters with bitmaps. Since we know the\ntypes of all of the objects, we just need to clear the result bits of\nany blobs.\n\nNote two subtleties in the implementation (which I also called out in\ncomments):\n\n - we have to include any blobs that were specifically asked for (and\n not reached through graph traversal) to match the non-bitmap version\n\n - we have to handle in-pack and \"ext_index\" objects separately.\n Arguably prepare_bitmap_walk() could be adding these ext_index\n objects to the type bitmaps. But it doesn't for now, so let's match\n the rest of the bitmap code here (it probably wouldn't be an\n efficiency improvement to do so since the cost of extending those\n bitmaps is about the same as our loop here, but it might make the\n code a bit simpler).\n\nHere are perf results for the new test on git.git:\n\n Test HEAD^ HEAD\n --------------------------------------------------------------------------------\n 5310.9: rev-list count with blob:none 1.67(1.62+0.05) 0.22(0.21+0.02) -86.8%\n\nSigned-off-by: Jeff King \n---\n pack-bitmap.c | 74 ++++++++++++++++++++++++++++++\n t/perf/p5310-pack-bitmaps.sh | 5 ++\n t/t6113-rev-list-bitmap-filters.sh | 14 ++++++\n 3 files changed, 93 insertions(+)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 48c8694f92..dcf8a9aadf 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -712,6 +712,73 @@ static int in_bitmapped_pack(struct bitmap_index *bitmap_git,\n \treturn 0;\n }\n \n+static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct object_list *tip_objects)\n+{\n+\tstruct bitmap *result = bitmap_new();\n+\tstruct object_list *p;\n+\n+\tfor (p = tip_objects; p; p = p->next) {\n+\t\tint pos;\n+\n+\t\tif (p->item->type != OBJ_BLOB)\n+\t\t\tcontinue;\n+\n+\t\tpos = bitmap_position(bitmap_git, &p->item->oid);\n+\t\tif (pos < 0)\n+\t\t\tcontinue;\n+\n+\t\tbitmap_set(result, pos);\n+\t}\n+\n+\treturn result;\n+}\n+\n+static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct object_list *tip_objects,\n+\t\t\t\t struct bitmap *to_filter)\n+{\n+\tstruct eindex *eindex = &bitmap_git->ext_index;\n+\tstruct bitmap *tips;\n+\tstruct ewah_iterator it;\n+\teword_t mask;\n+\tuint32_t i;\n+\n+\t/*\n+\t * The non-bitmap version of this filter never removes\n+\t * blobs which the other side specifically asked for,\n+\t * so we must match that behavior.\n+\t */\n+\ttips = find_tip_blobs(bitmap_git, tip_objects);\n+\n+\t/*\n+\t * We can use the blob type-bitmap to work in whole words\n+\t * for the objects that are actually in the bitmapped packfile.\n+\t */\n+\tfor (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB);\n+\t i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);\n+\t i++) {\n+\t\tif (i < tips->word_alloc)\n+\t\t\tmask &= ~tips->words[i];\n+\t\tto_filter->words[i] &= ~mask;\n+\t}\n+\n+\t/*\n+\t * Clear any blobs that weren't in the packfile (and so would not have\n+\t * been caught by the loop above. We'll have to check them\n+\t * individually.\n+\t */\n+\tfor (i = 0; i < eindex->count; i++) {\n+\t\tuint32_t pos = i + bitmap_git->pack->num_objects;\n+\t\tif (eindex->objects[i]->type == OBJ_BLOB &&\n+\t\t bitmap_get(to_filter, pos) &&\n+\t\t !bitmap_get(tips, pos))\n+\t\t\tbitmap_unset(to_filter, pos);\n+\t}\n+\n+\tbitmap_free(tips);\n+}\n+\n static int filter_bitmap(struct bitmap_index *bitmap_git,\n \t\t\t struct object_list *tip_objects,\n \t\t\t struct bitmap *to_filter,\n@@ -720,6 +787,13 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,\n \tif (!filter || filter->choice == LOFC_DISABLED)\n \t\treturn 0;\n \n+\tif (filter->choice == LOFC_BLOB_NONE) {\n+\t\tif (bitmap_git)\n+\t\t\tfilter_bitmap_blob_none(bitmap_git, tip_objects,\n+\t\t\t\t\t\tto_filter);\n+\t\treturn 0;\n+\t}\n+\n \t/* filter choice not handled */\n \treturn -1;\n }\ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex e52f66ec9e..936742314c 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -47,6 +47,11 @@ test_perf 'rev-list (objects)' '\n \tgit rev-list --all --use-bitmap-index --objects >/dev/null\n '\n \n+test_perf 'rev-list count with blob:none' '\n+\tgit rev-list --use-bitmap-index --count --objects --all \\\n+\t\t--filter=blob:none >/dev/null\n+'\n+\n test_expect_success 'create partial bitmap state' '\n \t# pick a commit to represent the repo tip in the past\n \tcutoff=$(git rev-list HEAD~100 -1) &&\ndiff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh\nindex 977f8d0930..f4e6d582f0 100755\n--- a/t/t6113-rev-list-bitmap-filters.sh\n+++ b/t/t6113-rev-list-bitmap-filters.sh\n@@ -21,4 +21,18 @@ test_expect_success 'filters fallback to non-bitmap traversal' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'blob:none filter' '\n+\tgit rev-list --objects --filter=blob:none HEAD >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t --objects --filter=blob:none HEAD >actual &&\n+\ttest_bitmap_traversal expect actual\n+'\n+\n+test_expect_success 'blob:none filter with specified blob' '\n+\tgit rev-list --objects --filter=blob:none HEAD HEAD:two.t >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t --objects --filter=blob:none HEAD HEAD:two.t >actual &&\n+\ttest_bitmap_traversal expect actual\n+'\n+\n test_done\n-- \n2.25.0.796.gcc29325708\n\n"},{"id":"391795","messageId":"xmqqeeuxng8x.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200214182216.GD150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 04/15] pack-bitmap: refuse to do a bitmap traversal with pathspecs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-14T19:03:26Z","receivedAt":"2020-02-14T19:03:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> It would also prepare us for a day where this case _is_ handled, but\n> that's pretty unlikely. E.g., we could use bitmaps to generate the set\n> of commits, and then diff each commit to see if it matches the pathspec.\n\nWould the gs/commit-graph-path-filter topic possibly help in this regard?\nI was wondering how it would fit within the framework this series sets\nup to teach object-filtering and reachability-bitmap codepaths to\nwork well together.\n\n"},{"id":"391797","messageId":"20200214205151.GB1210277@coredump.intra.peff.net","threadId":"52795","inReplyTo":"xmqqeeuxng8x.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 04/15] pack-bitmap: refuse to do a bitmap traversal with pathspecs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-14T20:51:51Z","receivedAt":"2020-02-14T20:51:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Feb 14, 2020 at 11:03:26AM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > It would also prepare us for a day where this case _is_ handled, but\n> > that's pretty unlikely. E.g., we could use bitmaps to generate the set\n> > of commits, and then diff each commit to see if it matches the pathspec.\n> \n> Would the gs/commit-graph-path-filter topic possibly help in this regard?\n> I was wondering how it would fit within the framework this series sets\n> up to teach object-filtering and reachability-bitmap codepaths to\n> work well together.\n\nI think it would make the scheme I described faster, because that diff\nbecomes faster. So the commit traversal itself becomes proportionally\nmore expensive. And if we could speed that up with bitmaps, that's some\nimprovement. OTOH, my later timings in patch 9 showed that commit graphs\nalready make that part pretty fast. And they do so without a bunch of\nweird restrictions and hassles. So I suspect it's not really worth the\neffort to implement this half-way bitmaps approach (for a special case\nthat it's not even clear anybody cares about).\n\nBut if somebody _does_ do so, I don't think we'd need to do anything too\nspecial to integrate with commit-graph-path-filter. The nice thing about\nthat approach is that the pathspec pruning will just magically return\nthe same answer, but faster.\n\n-Peff\n"},{"id":"391812","messageId":"20200215001036.GD11400@syl.local","threadId":"52795","inReplyTo":"20200214182208.GA150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 01/15] pack-bitmap: factor out type iterator initialization","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-02-15T00:10:36Z","receivedAt":"2020-02-15T00:10:41Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Peff,\n\nOn Fri, Feb 14, 2020 at 01:22:08PM -0500, Jeff King wrote:\n> When count_object_type() wants to iterate over the bitmap of all objects\n> of a certain type, we have to pair up OBJ_COMMIT with bitmap->commits,\n> and so forth. Since we're about to add more code to iterate over these\n> bitmaps, let's pull the initialization into its own function.\n>\n> We can also use this to simplify traverse_bitmap_commit_list(). It\n> accomplishes the same thing by manually passing the object type and the\n> bitmap to show_objects_for_type(), but using our helper we just need the\n> object type.\n>\n> Note there's one small code change here: previously we'd simply return\n> zero when counting an unknown object type, and now we'll BUG(). This\n> shouldn't matter in practice, as all of the callers pass in only usual\n> commit/tree/blob/tag types.\n\nThis all makes sense, as does the refactoring below.\n\nOn a relaid note: since you sent 'v2' before I had popped enough items\noff of my TODO list to look at your 'v1', I'll start my review in this\nthread instead of in v1.\n\n> Signed-off-by: Jeff King \n\nThanks,\nTaylor\n"},{"id":"391814","messageId":"20200215001552.GE11400@syl.local","threadId":"52795","inReplyTo":"20200214182211.GB150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 02/15] pack-bitmap: fix leak of haves/wants object lists","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-02-15T00:15:52Z","receivedAt":"2020-02-15T00:15:55Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Feb 14, 2020 at 01:22:11PM -0500, Jeff King wrote:\n> When we do a bitmap-aware revision traversal, we create an object_list\n> for each of the \"haves\" and \"wants\" tips. After creating the result\n> bitmaps these are no longer needed or used, but we never free the list\n> memory.\n>\n> Signed-off-by: Jeff King \n> ---\n> object.c | 9 +++++++++\n> object.h | 2 ++\n> pack-bitmap.c | 5 +++++\n> 3 files changed, 16 insertions(+)\n>\n> diff --git a/object.c b/object.c\n> index 142ef69399..4d11949b38 100644\n> --- a/object.c\n> +++ b/object.c\n> @@ -307,6 +307,15 @@ int object_list_contains(struct object_list *list, struct object *obj)\n> \treturn 0;\n> }\n>\n> +void object_list_free(struct object_list **list)\n> +{\n> +\twhile (*list) {\n> +\t\tstruct object_list *p = *list;\n> +\t\t*list = p->next;\n> +\t\tfree(p);\n> +\t}\n> +}\n\nHmm. I was going to write a comment saying more-or-less, \"I think I'm\nnitpicking here, but I'm not crazy about this as a 'while' loop\". But,\nwhen I wrote this as a 'for' loop instead, I wrote a use-after-free, and\nthen when I rid the code of that, it wasn't any more readable than the\nversion above.\n\n> /*\n> * A zero-length string to which object_array_entry::name can be\n> * initialized without requiring a malloc/free.\n> diff --git a/object.h b/object.h\n> index 25f5ab3d54..2dbabfca0a 100644\n> --- a/object.h\n> +++ b/object.h\n> @@ -151,6 +151,8 @@ struct object_list *object_list_insert(struct object *item,\n>\n> int object_list_contains(struct object_list *list, struct object *obj);\n>\n> +void object_list_free(struct object_list **list);\n> +\n> /* Object array handling .. */\n> void add_object_array(struct object *obj, const char *name, struct object_array *array);\n> void add_object_array_with_path(struct object *obj, const char *name, struct object_array *array, unsigned mode, const char *path);\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index 9ca356ee29..6c06099dc7 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -787,10 +787,15 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n> \tbitmap_git->result = wants_bitmap;\n> \tbitmap_git->haves = haves_bitmap;\n>\n> +\tobject_list_free(&wants);\n> +\tobject_list_free(&haves);\n> +\n\nMakes sense.\n\n> \treturn bitmap_git;\n>\n> cleanup:\n> \tfree_bitmap_index(bitmap_git);\n> +\tobject_list_free(&wants);\n> +\tobject_list_free(&haves);\n\nDitto.\n\n> \treturn NULL;\n> }\n>\n> --\n> 2.25.0.796.gcc29325708\n\nThanks,\nTaylor\n"},{"id":"391815","messageId":"20200215002232.GF11400@syl.local","threadId":"52795","inReplyTo":"20200214182213.GC150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 03/15] rev-list: fallback to non-bitmap traversal when filtering","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-02-15T00:22:32Z","receivedAt":"2020-02-15T00:22:37Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Feb 14, 2020 at 01:22:13PM -0500, Jeff King wrote:\n> The \"--use-bitmap-index\" option is usually aspirational: if we have\n> bitmaps and the request can be fulfilled more quickly using them we'll\n> do so, but otherwise fall back to a non-bitmap traversal.\n>\n> The exception is object filtering, which explicitly dies if the two\n> options are combined. Let's convert this to the usual fallback behavior.\n> This is a minor convenience for now (since the caller can easily know\n> that --filter and --use-bitmap-index don't combine), but will become\n> much more useful as we start to support _some_ filters with bitmaps, but\n> not others.\n\nYeah, I think that this convenience is worth it early on instead of\nlumping in these changes in a future patch.\n\n> The test infrastructure here is bigger than necessary for checking this\n> one small feature. But it will serve as the basis for more filtering\n> bitmap tests in future patches.\n>\n> Signed-off-by: Jeff King \n> ---\n> builtin/rev-list.c | 4 ++--\n> t/t6113-rev-list-bitmap-filters.sh | 24 ++++++++++++++++++++++++\n> 2 files changed, 26 insertions(+), 2 deletions(-)\n> create mode 100755 t/t6113-rev-list-bitmap-filters.sh\n>\n> diff --git a/builtin/rev-list.c b/builtin/rev-list.c\n> index e28d62ec64..bce406bd1e 100644\n> --- a/builtin/rev-list.c\n> +++ b/builtin/rev-list.c\n> @@ -521,8 +521,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n> \tif (revs.show_notes)\n> \t\tdie(_(\"rev-list does not support display of notes\"));\n>\n> -\tif (filter_options.choice && use_bitmap_index)\n> -\t\tdie(_(\"cannot combine --use-bitmap-index with object filtering\"));\n> +\tif (filter_options.choice)\n> +\t\tuse_bitmap_index = 0;\n>\n> \tsave_commit_buffer = (revs.verbose_header ||\n> \t\t\t revs.grep_filter.pattern_list ||\n> diff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh\n> new file mode 100755\n> index 0000000000..977f8d0930\n> --- /dev/null\n> +++ b/t/t6113-rev-list-bitmap-filters.sh\n> @@ -0,0 +1,24 @@\n> +#!/bin/sh\n> +\n> +test_description='rev-list combining bitmaps and filters'\n> +. ./test-lib.sh\n> +\n> +test_expect_success 'set up bitmapped repo' '\n> +\t# one commit will have bitmaps, the other will not\n> +\ttest_commit one &&\n> +\tgit repack -adb &&\n> +\ttest_commit two\n> +'\n> +\n> +test_expect_success 'filters fallback to non-bitmap traversal' '\n> +\t# use a path-based filter, since they are inherently incompatible with\n> +\t# bitmaps (i.e., this test will never get confused by later code to\n> +\t# combine the features)\n> +\tfilter=$(echo \"!one\" | git hash-object -w --stdin) &&\n> +\tgit rev-list --objects --filter=sparse:oid=$filter HEAD >expect &&\n> +\tgit rev-list --use-bitmap-index \\\n> +\t\t --objects --filter=sparse:oid=$filter HEAD >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n> +test_done\n> --\n> 2.25.0.796.gcc29325708\n\nMakes sense.\n\nThanks,\nTaylor\n"},{"id":"391816","messageId":"20200215003551.GA14791@syl.local","threadId":"52795","inReplyTo":"20200214182218.GE150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 05/15] rev-list: factor out bitmap-optimized routines","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-02-15T00:35:51Z","receivedAt":"2020-02-15T00:35:57Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Feb 14, 2020 at 01:22:18PM -0500, Jeff King wrote:\n> There are a few operations in rev-list that are optimized for bitmaps.\n> Rather than having the code inline in cmd_rev_list(), let's move them\n> into helpers. This not only makes the flow of the main function simpler,\n> but it lets us replace the complex \"can we do the optimization?\"\n> conditionals with a series of early returns from the functions. That\n> also makes it easy to add comments explaining those conditions.\n\nMakes sense.\n\n> Signed-off-by: Jeff King \n> ---\n> builtin/rev-list.c | 88 +++++++++++++++++++++++++++++++++++-----------\n> 1 file changed, 67 insertions(+), 21 deletions(-)\n>\n> diff --git a/builtin/rev-list.c b/builtin/rev-list.c\n> index 4cb5a52dee..38c5ca5603 100644\n> --- a/builtin/rev-list.c\n> +++ b/builtin/rev-list.c\n> @@ -364,6 +364,69 @@ static inline int parse_missing_action_value(const char *value)\n> \treturn 0;\n> }\n>\n> +static int try_bitmap_count(struct rev_info *revs)\n> +{\n> +\tuint32_t commit_count;\n> +\tint max_count;\n> +\tstruct bitmap_index *bitmap_git;\n> +\n> +\t/* This function only handles counting, not general traversal. */\n> +\tif (!revs->count)\n> +\t\treturn -1;\n> +\n> +\t/*\n> +\t * A bitmap result can't know left/right, etc, because we don't\n> +\t * actually traverse.\n> +\t */\n> +\tif (revs->left_right || revs->cherry_mark)\n> +\t\treturn -1;\n> +\n> +\t/*\n> +\t * This must be saved before doing any walking, since the revision\n> +\t * machinery will count it down to zero while traversing.\n> +\t */\n> +\tmax_count = revs->max_count;\n> +\n> +\tbitmap_git = prepare_bitmap_walk(revs);\n> +\tif (!bitmap_git)\n> +\t\treturn -1;\n> +\n> +\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n> +\tif (max_count >= 0 && max_count < commit_count)\n> +\t\tcommit_count = max_count;\n> +\n> +\tprintf(\"%d\\n\", commit_count);\n> +\tfree_bitmap_index(bitmap_git);\n> +\treturn 0;\n> +}\n> +\n> +static int try_bitmap_traversal(struct rev_info *revs)\n> +{\n> +\tstruct bitmap_index *bitmap_git;\n> +\n> +\t/*\n> +\t * We can't use a bitmap result with a traversal limit, since the set\n> +\t * of commits we'd get would be essentially random.\n> +\t */\n> +\tif (revs->max_count >= 0)\n> +\t\treturn -1;\n> +\n> +\t/*\n> +\t * Our bitmap result will return all objects, and we're not\n> +\t * yet prepared to show only particular types.\n> +\t */\n> +\tif (!revs->tag_objects || !revs->tree_objects || !revs->blob_objects)\n> +\t\treturn -1;\n> +\n> +\tbitmap_git = prepare_bitmap_walk(revs);\n> +\tif (!bitmap_git)\n> +\t\treturn -1;\n> +\n> +\ttraverse_bitmap_commit_list(bitmap_git, &show_object_fast);\n> +\tfree_bitmap_index(bitmap_git);\n> +\treturn 0;\n> +}\n> +\n> int cmd_rev_list(int argc, const char **argv, const char *prefix)\n> {\n> \tstruct rev_info revs;\n> @@ -534,27 +597,10 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n> \t\tprogress = start_delayed_progress(show_progress, 0);\n>\n> \tif (use_bitmap_index) {\n> -\t\tif (revs.count && !revs.left_right && !revs.cherry_mark) {\n> -\t\t\tuint32_t commit_count;\n> -\t\t\tint max_count = revs.max_count;\n> -\t\t\tstruct bitmap_index *bitmap_git;\n> -\t\t\tif ((bitmap_git = prepare_bitmap_walk(&revs))) {\n> -\t\t\t\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n> -\t\t\t\tif (max_count >= 0 && max_count < commit_count)\n> -\t\t\t\t\tcommit_count = max_count;\n> -\t\t\t\tprintf(\"%d\\n\", commit_count);\n> -\t\t\t\tfree_bitmap_index(bitmap_git);\n> -\t\t\t\treturn 0;\n> -\t\t\t}\n> -\t\t} else if (revs.max_count < 0 &&\n> -\t\t\t revs.tag_objects && revs.tree_objects && revs.blob_objects) {\n> -\t\t\tstruct bitmap_index *bitmap_git;\n> -\t\t\tif ((bitmap_git = prepare_bitmap_walk(&revs))) {\n> -\t\t\t\ttraverse_bitmap_commit_list(bitmap_git, &show_object_fast);\n> -\t\t\t\tfree_bitmap_index(bitmap_git);\n> -\t\t\t\treturn 0;\n> -\t\t\t}\n> -\t\t}\n> +\t\tif (!try_bitmap_count(&revs))\n> +\t\t\treturn 0;\n> +\t\tif (!try_bitmap_traversal(&revs))\n> +\t\t\treturn 0;\n> \t}\n>\n> \tif (prepare_revision_walk(&revs))\n> --\n> 2.25.0.796.gcc29325708\n\nThe refactoring here is straightforward, and looks correct to my\nreading.\n\nThanks,\nTaylor\n"},{"id":"391817","messageId":"20200215004216.GA15192@syl.local","threadId":"52795","inReplyTo":"20200214182220.GF150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-02-15T00:42:16Z","receivedAt":"2020-02-15T00:42:20Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Feb 14, 2020 at 01:22:20PM -0500, Jeff King wrote:\n> The current behavior from \"rev-list --count --objects\" is nonsensical:\n> we enumerate all of the objects except commits, but then give a count of\n> commits. This wasn't planned, and is just what the code happens to do.\n>\n> Instead, let's give the answer the user almost certainly wanted: the\n> full count of objects.\n\nThis makes sense: I've often worried about introducing\nbackwards-incompatible changes in newer versions of Git, even for\nbehavior that didn't make sense to begin with.\n\nOf course, backwards-incompatible changes *are* something worth worrying\nabout, but I don't find that the behavior was sensible to begin with, so\nI don't have a problem \"breaking\" it if \"breaking\" means making\nsomething nonsensical behave correctly.\n\n> Note that there are more complicated cases around cherry-marking, etc.\n> We'll punt on those for now, but let the user know that we can't produce\n> an answer (rather than giving them something useless).\n\nYep, sounds good.\n\n> We'll test both the new feature as well as a vanilla --count of commits,\n> since that surprisingly doesn't seem to be covered in the existing\n> tests.\n>\n> Signed-off-by: Jeff King \n> ---\n> builtin/rev-list.c | 13 +++++++++++++\n> t/t6000-rev-list-misc.sh | 12 ++++++++++++\n> 2 files changed, 25 insertions(+)\n>\n> diff --git a/builtin/rev-list.c b/builtin/rev-list.c\n> index 38c5ca5603..9452123988 100644\n> --- a/builtin/rev-list.c\n> +++ b/builtin/rev-list.c\n> @@ -253,11 +253,19 @@ static int finish_object(struct object *obj, const char *name, void *cb_data)\n> static void show_object(struct object *obj, const char *name, void *cb_data)\n> {\n> \tstruct rev_list_info *info = cb_data;\n> +\tstruct rev_info *revs = info->revs;\n> +\n> \tif (finish_object(obj, name, cb_data))\n> \t\treturn;\n> \tdisplay_progress(progress, ++progress_counter);\n> \tif (info->flags & REV_LIST_QUIET)\n> \t\treturn;\n> +\n> +\tif (revs->count) {\n> +\t\trevs->count_right++;\n> +\t\treturn;\n> +\t}\n> +\n\nHmm. This puzzled me at first. Do you think that it could benefit from a\ncomment?\n\n> \tif (arg_show_object_names)\n> \t\tshow_object_with_name(stdout, obj, name);\n> \telse\n> @@ -584,6 +592,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)\n> \tif (revs.show_notes)\n> \t\tdie(_(\"rev-list does not support display of notes\"));\n>\n> +\tif (revs.count &&\n> +\t (revs.tag_objects || revs.tree_objects || revs.blob_objects) &&\n> +\t (revs.left_right || revs.cherry_mark))\n> +\t\tdie(_(\"marked counting is incompatible with --objects\"));\n> +\n> \tif (filter_options.choice)\n> \t\tuse_bitmap_index = 0;\n>\n> diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh\n> index b8cf82349b..383f2c457d 100755\n> --- a/t/t6000-rev-list-misc.sh\n> +++ b/t/t6000-rev-list-misc.sh\n> @@ -148,4 +148,16 @@ test_expect_success 'rev-list --end-of-options' '\n> \ttest_cmp expect actual\n> '\n>\n> +test_expect_success 'rev-list --count' '\n> +\tcount=$(git rev-list --count HEAD) &&\n> +\tgit rev-list HEAD >actual &&\n> +\ttest_line_count = $count actual\n> +'\n> +\n> +test_expect_success 'rev-list --count --objects' '\n> +\tcount=$(git rev-list --count --objects HEAD) &&\n> +\tgit rev-list --objects HEAD >actual &&\n> +\ttest_line_count = $count actual\n> +'\n> +\n> test_done\n> --\n> 2.25.0.796.gcc29325708\n\nAll looks good.\n\nThanks,\nTaylor\n"},{"id":"391818","messageId":"20200215004555.GB15192@syl.local","threadId":"52795","inReplyTo":"20200214182222.GG150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 07/15] rev-list: allow bitmaps when counting objects","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-02-15T00:45:55Z","receivedAt":"2020-02-15T00:45:59Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Feb 14, 2020 at 01:22:22PM -0500, Jeff King wrote:\n> The prior commit taught \"--count --objects\" to work without bitmaps. We\n> should be able to get the same answer much more quickly with bitmaps.\n>\n> Note that we punt on the max_count case here. This perhaps _could_ be\n> made to work if we find all of the boundary commits and treat them as\n> UNINTERESTING, subtracting them (and their reachable objects) from the\n> set we return. That implies an actual commit traversal, but we'd still\n> be faster due to avoiding opening up any trees. Given the complexity and\n> the fact that anyone is unlikely to want this, it makes sense to just\n> fall back to the non-bitmap case for now.\n>\n> Signed-off-by: Jeff King \n> ---\n> builtin/rev-list.c | 21 ++++++++++++++++++---\n> t/t5310-pack-bitmaps.sh | 6 ++++++\n> 2 files changed, 24 insertions(+), 3 deletions(-)\n>\n> diff --git a/builtin/rev-list.c b/builtin/rev-list.c\n> index 9452123988..70f3207ecc 100644\n> --- a/builtin/rev-list.c\n> +++ b/builtin/rev-list.c\n> @@ -374,7 +374,10 @@ static inline int parse_missing_action_value(const char *value)\n>\n> static int try_bitmap_count(struct rev_info *revs)\n> {\n> -\tuint32_t commit_count;\n> +\tuint32_t commit_count = 0,\n> +\t\t tag_count = 0,\n> +\t\t tree_count = 0,\n> +\t\t blob_count = 0;\n\nHmm, I don't usually see the comma-separated declaration/initialization\nin git.git. Is there a reason you did it here? Not that I really mind\none way or the other, just interested.\n\n> \tint max_count;\n> \tstruct bitmap_index *bitmap_git;\n>\n> @@ -389,6 +392,15 @@ static int try_bitmap_count(struct rev_info *revs)\n> \tif (revs->left_right || revs->cherry_mark)\n> \t\treturn -1;\n>\n> +\t/*\n> +\t * If we're counting reachable objects, we can't handle a max count of\n> +\t * commits to traverse, since we don't know which objects go with which\n> +\t * commit.\n> +\t */\n> +\tif (revs->max_count >= 0 &&\n> +\t (revs->tag_objects || revs->tree_objects || revs->blob_objects))\n\nAn aside unrelated to the patch at hand: the expression\n\n (revs->tag_objects || revs->tree_objects || revs->blob_objects)\n\ndoes occur in an awful lot of places throughout this file. Do you\nimagine it'd be useful to pull this check out into its own function,\nperhaps as a preparatory patch in a later version of this series?\n\nI'm also not fussed if you don't think that such a change would be\nuseful, it's just an observation I had after seeing this expression a\nfew times.\n\n> +\t\treturn -1;\n> +\n> \t/*\n> \t * This must be saved before doing any walking, since the revision\n> \t * machinery will count it down to zero while traversing.\n> @@ -399,11 +411,14 @@ static int try_bitmap_count(struct rev_info *revs)\n> \tif (!bitmap_git)\n> \t\treturn -1;\n>\n> -\tcount_bitmap_commit_list(bitmap_git, &commit_count, NULL, NULL, NULL);\n> +\tcount_bitmap_commit_list(bitmap_git, &commit_count,\n> +\t\t\t\t revs->tree_objects ? &tree_count : NULL,\n> +\t\t\t\t revs->blob_objects ? &blob_count : NULL,\n> +\t\t\t\t revs->tag_objects ? &tag_count : NULL);\n> \tif (max_count >= 0 && max_count < commit_count)\n> \t\tcommit_count = max_count;\n>\n> -\tprintf(\"%d\\n\", commit_count);\n> +\tprintf(\"%d\\n\", commit_count + tree_count + blob_count + tag_count);\n> \tfree_bitmap_index(bitmap_git);\n> \treturn 0;\n> }\n> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\n> index 6640329ebf..7ba7d294a5 100755\n> --- a/t/t5310-pack-bitmaps.sh\n> +++ b/t/t5310-pack-bitmaps.sh\n> @@ -74,6 +74,12 @@ rev_list_tests() {\n> \t\ttest_cmp expect actual\n> \t'\n>\n> +\ttest_expect_success \"counting objects via bitmap ($state)\" '\n> +\t\tgit rev-list --count --objects HEAD >expect &&\n> +\t\tgit rev-list --use-bitmap-index --count --objects HEAD >actual &&\n> +\t\ttest_cmp expect actual\n> +\t'\n> +\n> \ttest_expect_success \"enumerate --objects ($state)\" '\n> \t\tgit rev-list --objects --use-bitmap-index HEAD >tmp &&\n> \t\tcut -d\" \" -f1 tmp2 &&\n> --\n> 2.25.0.796.gcc29325708\n\nYour tests look good to me, too.\n\nThanks,\nTaylor\n"},{"id":"391822","messageId":"20200215021446.GA16515@syl.local","threadId":"52795","inReplyTo":"20200214182225.GH150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 08/15] t5310: factor out bitmap traversal comparison","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-02-15T02:14:46Z","receivedAt":"2020-02-15T02:14:50Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Feb 14, 2020 at 01:22:25PM -0500, Jeff King wrote:\n> We check the results of \"rev-list --use-bitmap-index\" by comparing it to\n> the same traversal without the bitmap option. However, this is a little\n> tricky to do because of some output differences (see the included\n> comment for details). Let's pull this out into a helper function, since\n> we'll be adding some similar tests.\n>\n> While we're at it, let's also try to confirm that the bitmap output did\n> indeed use bitmaps. Since the code internally falls back to the\n> non-bitmap path in some cases, the tests are at risk of becoming trivial\n> noops.\n>\n> This is a bit fragile, as not all outputs will differ (e.g., looking at\n> only the commits from a fully-bitmapped pack will end up exactly the\n> same as the normal traversal order, since it also matches the pack\n> order). So we'll provide an escape hatch by which tests can disable this\n> check (which should only be used after manually confirming that bitmaps\n> kicked in).\n\nThanks for pointing out the rationale behind this.\n\n> Signed-off-by: Jeff King \n> ---\n> t/t5310-pack-bitmaps.sh | 10 +++-------\n> t/test-lib-functions.sh | 27 +++++++++++++++++++++++++++\n> 2 files changed, 30 insertions(+), 7 deletions(-)\n>\n> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\n> index 7ba7d294a5..b8645ae070 100755\n> --- a/t/t5310-pack-bitmaps.sh\n> +++ b/t/t5310-pack-bitmaps.sh\n> @@ -81,13 +81,9 @@ rev_list_tests() {\n> \t'\n>\n> \ttest_expect_success \"enumerate --objects ($state)\" '\n> -\t\tgit rev-list --objects --use-bitmap-index HEAD >tmp &&\n> -\t\tcut -d\" \" -f1 tmp2 &&\n> -\t\tsort actual &&\n> -\t\tgit rev-list --objects HEAD >tmp &&\n> -\t\tcut -d\" \" -f1 tmp2 &&\n> -\t\tsort expect &&\n> -\t\ttest_cmp expect actual\n> +\t\tgit rev-list --objects --use-bitmap-index HEAD >actual &&\n> +\t\tgit rev-list --objects HEAD >expect &&\n> +\t\ttest_bitmap_traversal expect actual\n> \t'\n>\n> \ttest_expect_success \"bitmap --objects handles non-commit objects ($state)\" '\n> diff --git a/t/test-lib-functions.sh b/t/test-lib-functions.sh\n> index 284c52d076..352c213d52 100644\n> --- a/t/test-lib-functions.sh\n> +++ b/t/test-lib-functions.sh\n> @@ -1516,3 +1516,30 @@ test_set_port () {\n> \tport=$(($port + ${GIT_TEST_STRESS_JOB_NR:-0}))\n> \teval $var=$port\n> }\n> +\n> +# Compare a file containing rev-list bitmap traversal output to its non-bitmap\n> +# counterpart. You can't just use test_cmp for this, because the two produce\n> +# subtly different output:\n> +#\n> +# - regular output is in traversal order, whereas bitmap is split by type,\n> +# with non-packed objects at the end\n> +#\n> +# - regular output has a space and the pathname appended to non-commit\n> +# objects; bitmap output omits this\n> +#\n> +# This function normalizes and compares the two. The second file should\n> +# always be the bitmap output.\n> +test_bitmap_traversal () {\n> +\tif test \"$1\" = \"--no-confirm-bitmaps\"\n> +\tthen\n> +\t\tshift\n> +\telif cmp \"$1\" \"$2\"\n\nAny reason to prefer 'cmp' here and then use 'test_cmp' below? I can't\nthink of a good reason one way or another, especially in places where\nGIT_TEST_CMP is just 'cmp', but I think the two usages should be\nconsistent with one another.\n\nIf there *is* a favorable argument for 'test_cmp' (instead of a bare\n'cmp'), I think that it'd be that the original code a couple of hunks up\nuses it.\n\n> +\tthen\n> +\t\techo >&2 \"identical raw outputs; are you sure bitmaps were used?\"\n> +\t\treturn 1\n> +\tfi &&\n> +\tcut -d' ' -f1 \"$1\" | sort >\"$1.normalized\" &&\n> +\tsort \"$2\" >\"$2.normalized\" &&\n> +\ttest_cmp \"$1.normalized\" \"$2.normalized\" &&\n> +\trm -f \"$1.normalized\" \"$2.normalized\"\n\nThis implementation looks good to me.\n\n> +}\n> --\n> 2.25.0.796.gcc29325708\n\nThanks,\nTaylor\n"},{"id":"391825","messageId":"20200215064654.GA1633703@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200215001552.GE11400@syl.local","subject":"Re: [PATCH v2 02/15] pack-bitmap: fix leak of haves/wants object lists","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-15T06:46:54Z","receivedAt":"2020-02-15T06:46:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Feb 14, 2020 at 04:15:52PM -0800, Taylor Blau wrote:\n\n> > +void object_list_free(struct object_list **list)\n> > +{\n> > +\twhile (*list) {\n> > +\t\tstruct object_list *p = *list;\n> > +\t\t*list = p->next;\n> > +\t\tfree(p);\n> > +\t}\n> > +}\n> \n> Hmm. I was going to write a comment saying more-or-less, \"I think I'm\n> nitpicking here, but I'm not crazy about this as a 'while' loop\". But,\n> when I wrote this as a 'for' loop instead, I wrote a use-after-free, and\n> then when I rid the code of that, it wasn't any more readable than the\n> version above.\n\nYep, linked lists are deceptive that way.\n\nThis _could_ be converted to use the generic list.h macros. Or better\nstill, we could probably ditch it entirely in favor of an object_array.\nBut I'd prefer to do that separately, if at all.\n\n-Peff\n"},{"id":"391826","messageId":"20200215064818.GB1633703@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200215004216.GA15192@syl.local","subject":"Re: [PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-15T06:48:18Z","receivedAt":"2020-02-15T06:48:21Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Feb 14, 2020 at 04:42:16PM -0800, Taylor Blau wrote:\n\n> On Fri, Feb 14, 2020 at 01:22:20PM -0500, Jeff King wrote:\n> > The current behavior from \"rev-list --count --objects\" is nonsensical:\n> > we enumerate all of the objects except commits, but then give a count of\n> > commits. This wasn't planned, and is just what the code happens to do.\n> >\n> > Instead, let's give the answer the user almost certainly wanted: the\n> > full count of objects.\n> \n> This makes sense: I've often worried about introducing\n> backwards-incompatible changes in newer versions of Git, even for\n> behavior that didn't make sense to begin with.\n> \n> Of course, backwards-incompatible changes *are* something worth worrying\n> about, but I don't find that the behavior was sensible to begin with, so\n> I don't have a problem \"breaking\" it if \"breaking\" means making\n> something nonsensical behave correctly.\n\nYeah, I admit I'm guessing that nobody cares about the current behavior,\nor that it was unplanned. But it seems sufficiently insane to me to take\na chance on.\n\n> > +\tif (revs->count) {\n> > +\t\trevs->count_right++;\n> > +\t\treturn;\n> > +\t}\n> > +\n> \n> Hmm. This puzzled me at first. Do you think that it could benefit from a\n> comment?\n\nWhat would it say (i.e., I'm not sure what confused you)?\n\n-Peff\n"},{"id":"391827","messageId":"20200215065500.GC1633703@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200215004555.GB15192@syl.local","subject":"Re: [PATCH v2 07/15] rev-list: allow bitmaps when counting objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-15T06:55:00Z","receivedAt":"2020-02-15T06:55:03Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Feb 14, 2020 at 04:45:55PM -0800, Taylor Blau wrote:\n\n> > static int try_bitmap_count(struct rev_info *revs)\n> > {\n> > -\tuint32_t commit_count;\n> > +\tuint32_t commit_count = 0,\n> > +\t\t tag_count = 0,\n> > +\t\t tree_count = 0,\n> > +\t\t blob_count = 0;\n> \n> Hmm, I don't usually see the comma-separated declaration/initialization\n> in git.git. Is there a reason you did it here? Not that I really mind\n> one way or the other, just interested.\n\nThe variables are all related, and all should have the same type. I'd\ncomplain about a patch that did:\n\n int ret, count;\n\nbecause there's no logical reason those two variables have the same\ntype. They just happen to. And putting them both on the same line is\neven worse, because it makes a diff changing one of them noisy.\n\nBut in the code quoted above, if one of them changes, they would all\n(presumably) change. So I think it communicates something to group them\nlike this. That said, if we had a style guideline that strictly forbade\nthis (because it's often applied in _bad_ spots), I wouldn't be that\nsad to convert it.\n\n> > +\tif (revs->max_count >= 0 &&\n> > +\t (revs->tag_objects || revs->tree_objects || revs->blob_objects))\n> \n> An aside unrelated to the patch at hand: the expression\n> \n> (revs->tag_objects || revs->tree_objects || revs->blob_objects)\n> \n> does occur in an awful lot of places throughout this file. Do you\n> imagine it'd be useful to pull this check out into its own function,\n> perhaps as a preparatory patch in a later version of this series?\n> \n> I'm also not fussed if you don't think that such a change would be\n> useful, it's just an observation I had after seeing this expression a\n> few times.\n\nThe most amusing part about it is that there's actually no way to\nspecify one type without the other. Most of the revision code tries to\nbe respectful of the fact that we might one day change that (though\nthere are some subtleties; e.g., asking for blobs but not trees would\nstill need to traverse the trees, but just not show them).\n\nSo this really could have been revs->objects. :) But I think given the\neffort to treat them individually so far, it would be a step backwards\nto switch now.\n\nAs far as whether there should be something like:\n\n int revs_show_objects(struct rev_info *revs)\n {\n\treturn revs->tag_objects || revs->tree_objects || revs->blob_objects;\n }\n\nI don't feel strongly either way. I find doing it inline perfectly\nreadable, but it's entirely possible my brain has been rotted by years\nof looking at the revision code.\n\n-Peff\n"},{"id":"391828","messageId":"20200215070054.GD1633703@coredump.intra.peff.net","threadId":"52795","inReplyTo":"20200215021446.GA16515@syl.local","subject":"Re: [PATCH v2 08/15] t5310: factor out bitmap traversal comparison","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-15T07:00:54Z","receivedAt":"2020-02-15T07:00:57Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Feb 14, 2020 at 06:14:46PM -0800, Taylor Blau wrote:\n\n> > This is a bit fragile, as not all outputs will differ (e.g., looking at\n> > only the commits from a fully-bitmapped pack will end up exactly the\n> > same as the normal traversal order, since it also matches the pack\n> > order). So we'll provide an escape hatch by which tests can disable this\n> > check (which should only be used after manually confirming that bitmaps\n> > kicked in).\n> \n> Thanks for pointing out the rationale behind this.\n\nI didn't write it this way at first, but the need became quite apparent\nwhen I ran the test from the next patch. :)\n\nI waffled on whether the extra option made the helper too convoluted to\nbe worthwhile. Another way to do it would be two separate functions:\n\n test_for_bitmap_output expect actual &&\n test_bitmap_output_matches expect actual\n\nbut as you can see I couldn't come up with good names.\n\nI doubt it matters all that much either way, as long as the docstring is\nclear.\n\n> > +test_bitmap_traversal () {\n> > +\tif test \"$1\" = \"--no-confirm-bitmaps\"\n> > +\tthen\n> > +\t\tshift\n> > +\telif cmp \"$1\" \"$2\"\n> \n> Any reason to prefer 'cmp' here and then use 'test_cmp' below? I can't\n> think of a good reason one way or another, especially in places where\n> GIT_TEST_CMP is just 'cmp', but I think the two usages should be\n> consistent with one another.\n\nOn most platforms GIT_TEST_CMP is \"diff -u\" (it's only on platforms with\na crappy system diff tool that we replace it with \"cmp\"). So I thought\nit would be confusing for it to dump a diff in the expected case (since\nunlike a normal test_cmp, we want the outputs to differ). \"cmp\" does\nstill write a short message to stderr; I thought about redirecting it to\n/dev/null, but worried that would make debugging verbose output harder).\n\n> If there *is* a favorable argument for 'test_cmp' (instead of a bare\n> 'cmp'), I think that it'd be that the original code a couple of hunks up\n> uses it.\n\nRight, but it uses to check that two things are equal (which we also use\nit for here).\n\n-Peff\n"},{"id":"391880","messageId":"xmqqwo8mm7ii.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200215064818.GB1633703@coredump.intra.peff.net","subject":"Re: [PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-16T23:34:13Z","receivedAt":"2020-02-16T23:34:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> > +\tif (revs->count) {\n>> > +\t\trevs->count_right++;\n>> > +\t\treturn;\n>> > +\t}\n>> > +\n>> \n>> Hmm. This puzzled me at first. Do you think that it could benefit from a\n>> comment?\n>\n> What would it say (i.e., I'm not sure what confused you)?\n\nI think the question reader had was \"why *right*?\"\n"},{"id":"391881","messageId":"xmqqsgjam7e2.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200215065500.GC1633703@coredump.intra.peff.net","subject":"Re: [PATCH v2 07/15] rev-list: allow bitmaps when counting objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-16T23:36:53Z","receivedAt":"2020-02-16T23:37:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> > +\tuint32_t commit_count = 0,\n>> > +\t\t tag_count = 0,\n>> > +\t\t tree_count = 0,\n>> > +\t\t blob_count = 0;\n>> \n>> Hmm, I don't usually see the comma-separated declaration/initialization\n>> in git.git. Is there a reason you did it here? Not that I really mind\n>> one way or the other, just interested.\n>\n> The variables are all related, and all should have the same type. I'd\n> complain about a patch that did:\n>\n> int ret, count;\n>\n> because there's no logical reason those two variables have the same\n> type. They just happen to. And putting them both on the same line is\n> even worse, because it makes a diff changing one of them noisy.\n>\n> But in the code quoted above, if one of them changes, they would all\n> (presumably) change. So I think it communicates something to group them\n> like this.\n\nI often apply exactly the same criteria as above to my code and\nreview---since it is not just you (or me), perhaps CodingGuideline\ncan help other readers, but I am OK to delay documenting it until we\nfind the third person who has been applying this rule that has not\nbeen spelt out explicitly ;-)\n"},{"id":"391965","messageId":"20200218052438.GB1641086@coredump.intra.peff.net","threadId":"52795","inReplyTo":"xmqqwo8mm7ii.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-18T05:24:38Z","receivedAt":"2020-02-18T05:24:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Feb 16, 2020 at 03:34:13PM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> >> > +\tif (revs->count) {\n> >> > +\t\trevs->count_right++;\n> >> > +\t\treturn;\n> >> > +\t}\n> >> > +\n> >> \n> >> Hmm. This puzzled me at first. Do you think that it could benefit from a\n> >> comment?\n> >\n> > What would it say (i.e., I'm not sure what confused you)?\n> \n> I think the question reader had was \"why *right*?\"\n\nAh. The answer is: because it's not SYMMETRIC_LEFT. ;)\n\nThe counting code accumulates there by default when there are no side\nmarkings, so that's what it will report when there's no left_right or\ncherry_mark (which we know will be the case here, since we die()\notherwise).\n\n-Peff\n"},{"id":"391994","messageId":"xmqqsgj7kdog.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200218052438.GB1641086@coredump.intra.peff.net","subject":"Re: [PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-18T17:28:31Z","receivedAt":"2020-02-18T17:28:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Sun, Feb 16, 2020 at 03:34:13PM -0800, Junio C Hamano wrote:\n>\n>> Jeff King writes:\n>> \n>> >> > +\tif (revs->count) {\n>> >> > +\t\trevs->count_right++;\n>> >> > +\t\treturn;\n>> >> > +\t}\n>> >> > +\n>> >> \n>> >> Hmm. This puzzled me at first. Do you think that it could benefit from a\n>> >> comment?\n>> >\n>> > What would it say (i.e., I'm not sure what confused you)?\n>> \n>> I think the question reader had was \"why *right*?\"\n>\n> Ah. The answer is: because it's not SYMMETRIC_LEFT. ;)\n>\n> The counting code accumulates there by default when there are no side\n> markings, so that's what it will report when there's no left_right or\n> cherry_mark (which we know will be the case here, since we die()\n> otherwise).\n\nYup.\n\n\t/*\n\t * The object count is always accumulated in the .count_right\n\t * field for traversal that is not a left-right traversal,\n\t * and cmd_rev_list() made sure that a .count request that\n\t * wants to count non-commit objects, which is handled by\n\t * the show_object() callback, does not ask for .left_right.\n\t */\n\nOverkill? I dunno.\n"},{"id":"391997","messageId":"28c2f199-e9eb-4405-9044-92a0af7632ec@gmail.com","threadId":"52795","inReplyTo":"20200214182211.GB150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 02/15] pack-bitmap: fix leak of haves/wants object lists","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-02-18T17:58:10Z","receivedAt":"2020-02-18T17:58:17Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/14/2020 1:22 PM, Jeff King wrote:\n> When we do a bitmap-aware revision traversal, we create an object_list\n> for each of the \"haves\" and \"wants\" tips. After creating the result\n> bitmaps these are no longer needed or used, but we never free the list\n> memory.\n\nIt's surprising that we got away with this for so long. Is it\npossible that this loop of freeing memory could provide significant\nperformance drawbacks? I'm assuming that the free() loop is much\nfaster than the malloc() loop, so the impact is negligible.\n\nThanks,\n-Stolee\n"},{"id":"391999","messageId":"3230c8c9-5208-3161-324e-c0ce948ee5b3@gmail.com","threadId":"52795","inReplyTo":"20200214182220.GF150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-02-18T18:05:35Z","receivedAt":"2020-02-18T18:05:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/14/2020 1:22 PM, Jeff King wrote:\n> +test_expect_success 'rev-list --count' '\n> +\tcount=$(git rev-list --count HEAD) &&\n> +\tgit rev-list HEAD >actual &&\n> +\ttest_line_count = $count actual\n> +'\n> +\n> +test_expect_success 'rev-list --count --objects' '\n> +\tcount=$(git rev-list --count --objects HEAD) &&\n> +\tgit rev-list --objects HEAD >actual &&\n> +\ttest_line_count = $count actual\n> +'\n\nI suppose these tests work, although I would probably\nprefer precomputed explicit expected counts instead\nof asking rev-list for the correct answer to a\nrev-list command. This is still fine, because we test\nthat the non-count versions return the correct results,\nbut I would hate for a bug to affect both modes equally\nand cause these tests to pass.\n\nThanks,\n-Stolee\n\n"},{"id":"392000","messageId":"967821c8-aca4-52ff-8eb9-01a74f5a8144@gmail.com","threadId":"52795","inReplyTo":"20200214182227.GI150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 09/15] rev-list: allow commit-only bitmap traversals","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-02-18T18:18:21Z","receivedAt":"2020-02-18T18:18:28Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/14/2020 1:22 PM, Jeff King wrote:\n> Here are numbers for linux.git:\n> \n> Test HEAD^ HEAD\n> ------------------------------------------------------------------------\n> 5310.7: rev-list (commits) 8.29(8.10+0.19) 1.76(1.72+0.04) -78.8%\n> 5310.8: rev-list (objects) 8.06(7.94+0.12) 8.14(7.94+0.13) +1.0%\n\nNice.\n\n> That run was cheating a little, as I didn't have any commit-graph in the\n> repository, and we'd built it by default these days when running git-gc.\n> Here are numbers with a commit-graph:\n> \n> Test HEAD^ HEAD\n> ------------------------------------------------------------------------\n> 5310.7: rev-list (commits) 0.70(0.58+0.12) 0.51(0.46+0.04) -27.1%\n> 5310.8: rev-list (objects) 6.20(6.09+0.10) 6.27(6.16+0.11) +1.1%\n> \n> Still an improvement, but a lot less impressive.\n\nI think this is still impressive, because you are still allocating the\nobject structs and writing data to the output. The commit-graph code allows\ncheating and doing very little work when navigating from one commit to\nanother. I suppose the biggest difference between these two approaches is\nthat the object cache contains \"parsed\" commits at the end (with allocated\nparents and initialized commit times) and we needed a priority queue for\nthe commit walk. I'm impressed that this is still 27% improvement!\n\n> diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh\n> index b8645ae070..2c64d0c441 100755\n> --- a/t/t5310-pack-bitmaps.sh\n> +++ b/t/t5310-pack-bitmaps.sh\n> @@ -80,6 +80,12 @@ rev_list_tests() {\n> \t\ttest_cmp expect actual\n> \t'\n> \n> +\ttest_expect_success \"enumerate commits ($state)\" '\n> +\t\tgit rev-list --use-bitmap-index HEAD >actual &&\n> +\t\tgit rev-list HEAD >expect &&\n> +\t\ttest_bitmap_traversal --no-confirm-bitmaps expect actual\n> +\t'\n> +\n\nI was wondering if there is anything we could add to the \"expect\"\ncommand that could better guarantee these commits show up in a\ndifferent order than the bitmap order, allowing us to drop the\n\"--no-confirm-bitmaps\". Perhaps the issue is the merge structure\nof the repository, and how it will cause these orders to always\nagree?\n\nI suppose \"--topo-order\" may actually present an order _even closer_\nto the bitmap order.\n\nThanks,\n-Stolee\n"},{"id":"392002","messageId":"800e4714-200e-6256-5538-ef39f6d9246c@gmail.com","threadId":"52795","inReplyTo":"20200214182236.GM150965@coredump.intra.peff.net","subject":"Re: [PATCH v2 13/15] pack-bitmap: implement BLOB_NONE filtering","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-02-18T19:26:53Z","receivedAt":"2020-02-18T19:27:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/14/2020 1:22 PM, Jeff King wrote:\n> We can easily support BLOB_NONE filters with bitmaps. Since we know the\n> types of all of the objects, we just need to clear the result bits of\n> any blobs.\n> \n> Note two subtleties in the implementation (which I also called out in\n> comments):\n> \n> - we have to include any blobs that were specifically asked for (and\n> not reached through graph traversal) to match the non-bitmap version\n\nI have a concern here, but maybe I'm worrying about nothing. When a\npartial clone asks for a pack of missing blobs, will your code create\nan empty bitmap and then add bits to that bitmap one-by-one instead\nof appending to a simple object list?\n\nIn the typical case where we ask for specific commits and trees, we\nexpect a very small number of blobs to add to the resulting bitmap.\nWhen no commits or trees are included in the wants, then we don't\nneed the bitmap at all. IIRC an EWAH bitmap is relatively expensive\nto update bits one at a time, so this is not incredibly efficient.\n\nI apologize that I don't have the time to dig into this myself.\n\n> - we have to handle in-pack and \"ext_index\" objects separately.\n> Arguably prepare_bitmap_walk() could be adding these ext_index\n> objects to the type bitmaps. But it doesn't for now, so let's match\n> the rest of the bitmap code here (it probably wouldn't be an\n> efficiency improvement to do so since the cost of extending those\n> bitmaps is about the same as our loop here, but it might make the\n> code a bit simpler).\n> \n> Here are perf results for the new test on git.git:\n> \n> Test HEAD^ HEAD\n> --------------------------------------------------------------------------------\n> 5310.9: rev-list count with blob:none 1.67(1.62+0.05) 0.22(0.21+0.02) -86.8%\n...\n> diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\n> index e52f66ec9e..936742314c 100755\n> --- a/t/perf/p5310-pack-bitmaps.sh\n> +++ b/t/perf/p5310-pack-bitmaps.sh\n> @@ -47,6 +47,11 @@ test_perf 'rev-list (objects)' '\n> \tgit rev-list --all --use-bitmap-index --objects >/dev/null\n> '\n> \n> +test_perf 'rev-list count with blob:none' '\n> +\tgit rev-list --use-bitmap-index --count --objects --all \\\n> +\t\t--filter=blob:none >/dev/null\n> +'\n\nI wondered why you chose to extend these tests instead of using\np5600-partial-clone.sh, but I guess this script definitely creates\nthe bitmap for the test. When I tested p5600-partial-clone.sh below,\nI manually repacked the Linux repo to have a bitmap:\n\nTest v2.25.0 HEAD \n----------------------------------------------------------------------------\n5600.2: clone without blobs 79.81(111.34+11.35) 36.00(69.37+7.30) -54.9%\n5600.3: checkout of result 45.56(114.59+4.81) 46.43(80.50+5.41) +1.9% \n\nPerhaps results for these tests would also be appropriate for your\ncommit messages?\n\nNote the +1.9% for the checkout. It's unlikely that this is actually\nsomething meaningful, but it _could_ be related to my concerns above\nabout building a blob list from an empty bitmap.\n\nThanks,\n-Stolee\n"},{"id":"392004","messageId":"ffb700bf-862c-8a40-453b-9d7adb638798@gmail.com","threadId":"52795","inReplyTo":"800e4714-200e-6256-5538-ef39f6d9246c@gmail.com","subject":"Re: [PATCH v2 13/15] pack-bitmap: implement BLOB_NONE filtering","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-02-18T19:36:55Z","receivedAt":"2020-02-18T19:37:00Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/18/2020 2:26 PM, Derrick Stolee wrote:\n> On 2/14/2020 1:22 PM, Jeff King wrote:\n>> +test_perf 'rev-list count with blob:none' '\n>> +\tgit rev-list --use-bitmap-index --count --objects --all \\\n>> +\t\t--filter=blob:none >/dev/null\n>> +'\n> \n> I wondered why you chose to extend these tests instead of using\n> p5600-partial-clone.sh, but I guess this script definitely creates\n> the bitmap for the test. When I tested p5600-partial-clone.sh below,\n> I manually repacked the Linux repo to have a bitmap:\n> \n> Test v2.25.0 HEAD \n> ----------------------------------------------------------------------------\n> 5600.2: clone without blobs 79.81(111.34+11.35) 36.00(69.37+7.30) -54.9%\n> 5600.3: checkout of result 45.56(114.59+4.81) 46.43(80.50+5.41) +1.9% \n> \n> Perhaps results for these tests would also be appropriate for your\n> commit messages?\n\nAnd speaking of valuable performance tests to update: should we take\nthe loop of fetch tests in p5311-pack-bitmaps-fetch.sh and make\nequivalent versions in p5600-partial-clone.sh? It would be good to\nmake sure that the incremental fetches also improve in this scenario.\n\nThanks,\n-Stolee\n"},{"id":"392006","messageId":"20200218195531.GA21774@coredump.intra.peff.net","threadId":"52795","inReplyTo":"xmqqsgj7kdog.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-18T19:55:31Z","receivedAt":"2020-02-18T19:55:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 18, 2020 at 09:28:31AM -0800, Junio C Hamano wrote:\n\n> >> I think the question reader had was \"why *right*?\"\n> >\n> > Ah. The answer is: because it's not SYMMETRIC_LEFT. ;)\n> >\n> > The counting code accumulates there by default when there are no side\n> > markings, so that's what it will report when there's no left_right or\n> > cherry_mark (which we know will be the case here, since we die()\n> > otherwise).\n> \n> Yup.\n> \n> \t/*\n> \t * The object count is always accumulated in the .count_right\n> \t * field for traversal that is not a left-right traversal,\n> \t * and cmd_rev_list() made sure that a .count request that\n> \t * wants to count non-commit objects, which is handled by\n> \t * the show_object() callback, does not ask for .left_right.\n> \t */\n> \n> Overkill? I dunno.\n\nNo, I think it looks good. Want to squash that in (and I'll do likewise\nlocally)?\n\n-Peff\n"},{"id":"392007","messageId":"20200218200219.GC21774@coredump.intra.peff.net","threadId":"52795","inReplyTo":"28c2f199-e9eb-4405-9044-92a0af7632ec@gmail.com","subject":"Re: [PATCH v2 02/15] pack-bitmap: fix leak of haves/wants object lists","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-18T20:02:19Z","receivedAt":"2020-02-18T20:05:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 18, 2020 at 12:58:10PM -0500, Derrick Stolee wrote:\n\n> On 2/14/2020 1:22 PM, Jeff King wrote:\n> > When we do a bitmap-aware revision traversal, we create an object_list\n> > for each of the \"haves\" and \"wants\" tips. After creating the result\n> > bitmaps these are no longer needed or used, but we never free the list\n> > memory.\n> \n> It's surprising that we got away with this for so long. Is it\n> possible that this loop of freeing memory could provide significant\n> performance drawbacks? I'm assuming that the free() loop is much\n> faster than the malloc() loop, so the impact is negligible.\n\nI don't think it's surprising. We're only talking about leaking hundreds\nor perhaps thousands of structs. So maybe a few kilobytes at most. And\nwe'd typically only run one such bitmap traversal per program.\n\nMeanwhile rev-list is generally storing that same set of objects in a\npending array, and I think we don't generally clean up after it (nor is\nthere even a convenient function to do so).\n\nSo I think it's sort of a drop in the bucket of Git's \"eh, this pretty\nmuch lasts about the whole program anyway\" leaks. I don't think there's\nmuch performance difference either way in freeing or not. It's mostly\njust a cleanliness thing. (I do one day dream of being able to run the\ntest suite through a leakchecker, but we're still a ways off, I think).\n\n-Peff\n"},{"id":"392008","messageId":"20200218200541.GD21774@coredump.intra.peff.net","threadId":"52795","inReplyTo":"967821c8-aca4-52ff-8eb9-01a74f5a8144@gmail.com","subject":"Re: [PATCH v2 09/15] rev-list: allow commit-only bitmap traversals","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-18T20:05:41Z","receivedAt":"2020-02-18T20:05:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 18, 2020 at 01:18:21PM -0500, Derrick Stolee wrote:\n\n> > +\ttest_expect_success \"enumerate commits ($state)\" '\n> > +\t\tgit rev-list --use-bitmap-index HEAD >actual &&\n> > +\t\tgit rev-list HEAD >expect &&\n> > +\t\ttest_bitmap_traversal --no-confirm-bitmaps expect actual\n> > +\t'\n> > +\n> \n> I was wondering if there is anything we could add to the \"expect\"\n> command that could better guarantee these commits show up in a\n> different order than the bitmap order, allowing us to drop the\n> \"--no-confirm-bitmaps\". Perhaps the issue is the merge structure\n> of the repository, and how it will cause these orders to always\n> agree?\n> \n> I suppose \"--topo-order\" may actually present an order _even closer_\n> to the bitmap order.\n\nI think in the partial-bitmap state it may have a different order,\nbecause we'd put the new commits at the end. But we run this test in\nboth fully-bitmapped and partial-bitmap conditions.\n\nWe could add something like --topo-order to the expected output, but I\nthink even if it worked, then the bitmap-confirmation in\ntest_bitmap_traversal wouldn't really be checking anything! I.e., if the\n\"actual\" traversal didn't use bitmaps, we'd still say \"oh, these two\noutputs are different, so one must have used bitmaps.\" So saying\n\"--no-confirm-bitmap\" at least documents that we don't expect any\ndifference.\n\n-Peff\n"},{"id":"392009","messageId":"20200218195901.GB21774@coredump.intra.peff.net","threadId":"52795","inReplyTo":"3230c8c9-5208-3161-324e-c0ce948ee5b3@gmail.com","subject":"Re: [PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-18T19:59:01Z","receivedAt":"2020-02-18T20:07:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 18, 2020 at 01:05:35PM -0500, Derrick Stolee wrote:\n\n> On 2/14/2020 1:22 PM, Jeff King wrote:\n> > +test_expect_success 'rev-list --count' '\n> > +\tcount=$(git rev-list --count HEAD) &&\n> > +\tgit rev-list HEAD >actual &&\n> > +\ttest_line_count = $count actual\n> > +'\n> > +\n> > +test_expect_success 'rev-list --count --objects' '\n> > +\tcount=$(git rev-list --count --objects HEAD) &&\n> > +\tgit rev-list --objects HEAD >actual &&\n> > +\ttest_line_count = $count actual\n> > +'\n> \n> I suppose these tests work, although I would probably\n> prefer precomputed explicit expected counts instead\n> of asking rev-list for the correct answer to a\n> rev-list command. This is still fine, because we test\n> that the non-count versions return the correct results,\n> but I would hate for a bug to affect both modes equally\n> and cause these tests to pass.\n\nI was hoping it would make the tests a bit less brittle. And as you\nnote, we should be checking the enumeration results themselves more\ncarefully in other tests, so I find it fairly unlikely to see a bug that\ndoesn't trigger _any_ test failure.\n\n-Peff\n"},{"id":"392011","messageId":"dad539af-adcc-4cda-17f8-423ce1cc9eed@gmail.com","threadId":"52795","inReplyTo":"20200218200541.GD21774@coredump.intra.peff.net","subject":"Re: [PATCH v2 09/15] rev-list: allow commit-only bitmap traversals","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-02-18T20:11:57Z","receivedAt":"2020-02-18T20:12:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 2/18/2020 3:05 PM, Jeff King wrote:\n> On Tue, Feb 18, 2020 at 01:18:21PM -0500, Derrick Stolee wrote:\n> \n>>> +\ttest_expect_success \"enumerate commits ($state)\" '\n>>> +\t\tgit rev-list --use-bitmap-index HEAD >actual &&\n>>> +\t\tgit rev-list HEAD >expect &&\n>>> +\t\ttest_bitmap_traversal --no-confirm-bitmaps expect actual\n>>> +\t'\n>>> +\n>>\n>> I was wondering if there is anything we could add to the \"expect\"\n>> command that could better guarantee these commits show up in a\n>> different order than the bitmap order, allowing us to drop the\n>> \"--no-confirm-bitmaps\". Perhaps the issue is the merge structure\n>> of the repository, and how it will cause these orders to always\n>> agree?\n>>\n>> I suppose \"--topo-order\" may actually present an order _even closer_\n>> to the bitmap order.\n> \n> I think in the partial-bitmap state it may have a different order,\n> because we'd put the new commits at the end. But we run this test in\n> both fully-bitmapped and partial-bitmap conditions.\n> \n> We could add something like --topo-order to the expected output, but I\n> think even if it worked, then the bitmap-confirmation in\n> test_bitmap_traversal wouldn't really be checking anything! I.e., if the\n> \"actual\" traversal didn't use bitmaps, we'd still say \"oh, these two\n> outputs are different, so one must have used bitmaps.\" So saying\n> \"--no-confirm-bitmap\" at least documents that we don't expect any\n> difference.\n\nThat's a pretty good point. Thanks!\n"},{"id":"392012","messageId":"20200218202417.GE21774@coredump.intra.peff.net","threadId":"52795","inReplyTo":"800e4714-200e-6256-5538-ef39f6d9246c@gmail.com","subject":"Re: [PATCH v2 13/15] pack-bitmap: implement BLOB_NONE filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-18T20:24:17Z","receivedAt":"2020-02-18T20:24:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 18, 2020 at 02:26:53PM -0500, Derrick Stolee wrote:\n\n> On 2/14/2020 1:22 PM, Jeff King wrote:\n> > We can easily support BLOB_NONE filters with bitmaps. Since we know the\n> > types of all of the objects, we just need to clear the result bits of\n> > any blobs.\n> > \n> > Note two subtleties in the implementation (which I also called out in\n> > comments):\n> > \n> > - we have to include any blobs that were specifically asked for (and\n> > not reached through graph traversal) to match the non-bitmap version\n> \n> I have a concern here, but maybe I'm worrying about nothing. When a\n> partial clone asks for a pack of missing blobs, will your code create\n> an empty bitmap and then add bits to that bitmap one-by-one instead\n> of appending to a simple object list?\n\nYes. They'd all be listed in revs->pending, so we'd add them to our\narray of \"wants\", and then create a bitmap. There's no traversal cost,\nbut we'd pay the cost to open the bitmap file. But...\n\n> In the typical case where we ask for specific commits and trees, we\n> expect a very small number of blobs to add to the resulting bitmap.\n> When no commits or trees are included in the wants, then we don't\n> need the bitmap at all. IIRC an EWAH bitmap is relatively expensive\n> to update bits one at a time, so this is not incredibly efficient.\n\nThere's no ewah bitmap at play here at all. The internal bitmap we\ncreate in memory for the walk is a real uncompressed bitmap, so settings\nand retrieving bits is pretty cheap.\n\nI'd worry much more about the fact that we had to parse the whole bitmap\nfile (which for historical format reasons involves actually running over\nall of the bytes in the file).\n\nI think that's somewhat orthogonal to this patch, though. The same\npessimality would be true of anybody fetching a couple blobs, whether\nthey use filters or not (and really, there's no reason that the\nfollow-up fetch for blobs in a filtered repository would need to use\nfilters, but for some reason it does).\n\nIt would be an easy optimization to say \"we have only blobs, don't\nbother opening the bitmap file\", but I think that should come on top.\nHowever, I have a suspicion that we actually call parse_object() on each\nblob before we even get to the bitmap code (via get_reference()). If so,\nthat's a much larger low-hanging fruit.\n\n> > --- a/t/perf/p5310-pack-bitmaps.sh\n> [...]\n> \n> I wondered why you chose to extend these tests instead of using\n> p5600-partial-clone.sh, but I guess this script definitely creates\n> the bitmap for the test. When I tested p5600-partial-clone.sh below,\n> I manually repacked the Linux repo to have a bitmap:\n\nRight, when the two features combine, we have to either pick a test\nscript that hits one or the other, or create a new one. Especially since\nthis one covers the full and partial bitmap states, I think it's nice to\nreuse that work.\n\n> Test v2.25.0 HEAD \n> ----------------------------------------------------------------------------\n> 5600.2: clone without blobs 79.81(111.34+11.35) 36.00(69.37+7.30) -54.9%\n> 5600.3: checkout of result 45.56(114.59+4.81) 46.43(80.50+5.41) +1.9% \n> \n> Perhaps results for these tests would also be appropriate for your\n> commit messages?\n\nI think your p5600.2 is basically the same as what I ended up with\nin p5310 for the final commit (when pack-objects finally learns to use\nthese filters, too). But we want to make sure we are testing with\nbitmaps, so I don't think we'd want to count on the sample repo having\nbitmaps already.\n\nI think this speaks to the general problems with the perf suite, in that\nwe probably ought to be testing combinations of repos and tests, rather\nthan manually creating situations in each script).\n\n> Note the +1.9% for the checkout. It's unlikely that this is actually\n> something meaningful, but it _could_ be related to my concerns above\n> about building a blob list from an empty bitmap.\n\nIn my experience with the perf suite, 2% is most likely noise\n(especially for a filesystem-heavy operation like checkout). Note that\nthe difference in system time covers almost all of the wall-clock time.\n\nIt is curious that the user time in your second test dropped so\ndrastically, but didn't create a wall-clock improvement. I've often seen\nweirdness there with the CPU clock changing due to external factors.\n\n-Peff\n"},{"id":"392013","messageId":"20200218203016.GF21774@coredump.intra.peff.net","threadId":"52795","inReplyTo":"ffb700bf-862c-8a40-453b-9d7adb638798@gmail.com","subject":"Re: [PATCH v2 13/15] pack-bitmap: implement BLOB_NONE filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-18T20:30:16Z","receivedAt":"2020-02-18T20:30:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 18, 2020 at 02:36:55PM -0500, Derrick Stolee wrote:\n\n> > I wondered why you chose to extend these tests instead of using\n> > p5600-partial-clone.sh, but I guess this script definitely creates\n> > the bitmap for the test. When I tested p5600-partial-clone.sh below,\n> > I manually repacked the Linux repo to have a bitmap:\n> > \n> > Test v2.25.0 HEAD \n> > ----------------------------------------------------------------------------\n> > 5600.2: clone without blobs 79.81(111.34+11.35) 36.00(69.37+7.30) -54.9%\n> > 5600.3: checkout of result 45.56(114.59+4.81) 46.43(80.50+5.41) +1.9% \n> > \n> > Perhaps results for these tests would also be appropriate for your\n> > commit messages?\n> \n> And speaking of valuable performance tests to update: should we take\n> the loop of fetch tests in p5311-pack-bitmaps-fetch.sh and make\n> equivalent versions in p5600-partial-clone.sh? It would be good to\n> make sure that the incremental fetches also improve in this scenario.\n\nI don't think it would make sense to add them permanently, since p5600\ndoesn't necessarily have bitmaps in effect.\n\nBut in any case, those tests are mostly about pack-objects realizing\nwhen we can use on-disk deltas due to the presence of bitmaps. If we're\navoiding sending blobs, then that cuts out a huge chunk of opportunity\nfor it to make any improvement (it might still have some impact because\nof trees, though). So I'd expect the effect to be muted.\n\nI dunno. It's true that I just hypothesized a result which we could\nconfirm. But the perf tests are quite expensive to run (and p5311 is one\nof the more expensive ones). I'm not sure that repeating those tests\ncombined with partial clones carries a lot of regression-testing value\nto merit adding that expense to all future runs.\n\n-Peff\n"},{"id":"392021","messageId":"xmqqpnebioeg.fsf@gitster-ct.c.googlers.com","threadId":"52795","inReplyTo":"20200218195531.GA21774@coredump.intra.peff.net","subject":"Re: [PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-02-18T21:19:51Z","receivedAt":"2020-02-18T21:19:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Tue, Feb 18, 2020 at 09:28:31AM -0800, Junio C Hamano wrote:\n>\n>> >> I think the question reader had was \"why *right*?\"\n>> >\n>> > Ah. The answer is: because it's not SYMMETRIC_LEFT. ;)\n>> >\n>> > The counting code accumulates there by default when there are no side\n>> > markings, so that's what it will report when there's no left_right or\n>> > cherry_mark (which we know will be the case here, since we die()\n>> > otherwise).\n>> \n>> Yup.\n>> \n>> \t/*\n>> \t * The object count is always accumulated in the .count_right\n>> \t * field for traversal that is not a left-right traversal,\n>> \t * and cmd_rev_list() made sure that a .count request that\n>> \t * wants to count non-commit objects, which is handled by\n>> \t * the show_object() callback, does not ask for .left_right.\n>> \t */\n>> \n>> Overkill? I dunno.\n>\n> No, I think it looks good. Want to squash that in (and I'll do likewise\n> locally)?\n\nIt's too late for squashing anything in, as they are in 'next'\nalready.\n\n"},{"id":"392022","messageId":"20200218212339.GC22630@coredump.intra.peff.net","threadId":"52795","inReplyTo":"xmqqpnebioeg.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v2 06/15] rev-list: make --count work with --objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-02-18T21:23:39Z","receivedAt":"2020-02-18T21:23:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Feb 18, 2020 at 01:19:51PM -0800, Junio C Hamano wrote:\n\n> >> \t/*\n> >> \t * The object count is always accumulated in the .count_right\n> >> \t * field for traversal that is not a left-right traversal,\n> >> \t * and cmd_rev_list() made sure that a .count request that\n> >> \t * wants to count non-commit objects, which is handled by\n> >> \t * the show_object() callback, does not ask for .left_right.\n> >> \t */\n> >> \n> >> Overkill? I dunno.\n> >\n> > No, I think it looks good. Want to squash that in (and I'll do likewise\n> > locally)?\n> \n> It's too late for squashing anything in, as they are in 'next'\n> already.\n\nAh, I hadn't noticed that yet. I can live without it, but I'd also be OK\nwith a patch on top if you want to add it.\n\n-Peff\n"}]}