{"thread":{"id":"53394","subject":"[PATCH 0/4] pack-bitmap: use bitmaps for traversals with '--filter=tree:0'","startedAt":"2020-05-04T23:12:27Z","lastAt":"2020-05-05T18:20:27Z","messageCount":12,"participants":["Taylor Blau","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"397007","messageId":"cover.1588633810.git.me@ttaylorr.com","threadId":"53394","inReplyTo":null,"subject":"[PATCH 0/4] pack-bitmap: use bitmaps for traversals with '--filter=tree:0'","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-04T23:12:22Z","receivedAt":"2020-05-04T23:12:27Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi,\n\nThis is a re-submission of mine and Peff's series in [1] to get some\nmore eyes on it. The intent of this series is to take advantage of\nthe type bitmaps when using '--filter=tree:0'.\n\nWe have been running these patches at GitHub for a couple of months now\nto power fetches with '--filter=tree:0' (but no other values of N,\npatches to come later to address this).\n\nThe content of the patches attached are the same as in\ntheir original submission; the only change on my part has been to\nrebase them over the latest from master.\n\nThanks in advance for your review.\n\n[1]: https://lore.kernel.org/git/cover.1587597151.git.me@ttaylorr.com/\n\nJeff King (2):\n  list-objects-filter: treat NULL filter_options as \"disabled\"\n  pack-bitmap: pass object filter to fill-in traversal\n\nTaylor Blau (2):\n  pack-bitmap.c: make object filtering functions generic\n  pack-bitmap.c: support 'tree:0' filtering\n\n list-objects-filter.c              |  3 ++\n pack-bitmap.c                      | 72 +++++++++++++++++++++++-------\n t/perf/p5310-pack-bitmaps.sh       | 10 +++++\n t/t6113-rev-list-bitmap-filters.sh | 21 +++++++++\n 4 files changed, 90 insertions(+), 16 deletions(-)\n\n--\n2.26.0.113.ge9739cdccc\n"},{"id":"397008","messageId":"bb7d99ee2582d60e2413df56cb2c3fb06c18de8e.1588633810.git.me@ttaylorr.com","threadId":"53394","inReplyTo":"cover.1588633810.git.me@ttaylorr.com","subject":"[PATCH 1/4] list-objects-filter: treat NULL filter_options as \"disabled\"","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-04T23:12:27Z","receivedAt":"2020-05-04T23:12:31Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"From: Jeff King <peff@peff.net>\n\nIn most callers, we have an actual list_objects_filter_options struct,\nand if no filtering is desired its \"choice\" element will be\nLOFC_DISABLED. However, some code may have only a pointer to such a\nstruct which may be NULL (because _their_ callers didn't care about\nfiltering, either). Rather than forcing them to handle this explicitly\nlike:\n\n  if (filter_options)\n          traverse_commit_list_filtered(filter_options, revs,\n\t                                show_commit, show_object,\n\t\t\t\t\tshow_data, NULL);\n  else\n          traverse_commit_list(revs, show_commit, show_object,\n\t                             show_data);\n\nlet's just treat a NULL filter_options the same as LOFC_DISABLED. We\nonly need a small change, since that option struct is converted into a\nreal filter only in the \"init\" function.\n\nSigned-off-by: Jeff King <peff@peff.net>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n list-objects-filter.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/list-objects-filter.c b/list-objects-filter.c\nindex 1e8d4e763d..0a3ef3cab3 100644\n--- a/list-objects-filter.c\n+++ b/list-objects-filter.c\n@@ -663,6 +663,9 @@ struct filter *list_objects_filter__init(\n \n \tassert((sizeof(s_filters) / sizeof(s_filters[0])) == LOFC__COUNT);\n \n+\tif (!filter_options)\n+\t\treturn NULL;\n+\n \tif (filter_options->choice >= LOFC__COUNT)\n \t\tBUG(\"invalid list-objects filter choice: %d\",\n \t\t    filter_options->choice);\n-- \n2.26.0.113.ge9739cdccc\n\n"},{"id":"397009","messageId":"b43a12894e7edf7d54ce2e9679f8db7dabec23e0.1588633810.git.me@ttaylorr.com","threadId":"53394","inReplyTo":"cover.1588633810.git.me@ttaylorr.com","subject":"[PATCH 2/4] pack-bitmap.c: make object filtering functions generic","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-04T23:12:31Z","receivedAt":"2020-05-04T23:12:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In 4f3bd5606a (pack-bitmap: implement BLOB_NONE filtering, 2020-02-14),\nfiltering support for bitmaps was added for the 'LOFC_BLOB_NONE' filter.\n\nIn the future, we would like to add support for filters that behave as\nif they exclude a certain type of object, for e.g., the tree depth\nfilter with depth 0.\n\nTo prepare for this, make some of the functions used for filtering more\ngeneric, such as 'find_tip_blobs' and 'filter_bitmap_blob_none' so that\nthey can work over arbitrary object types.\n\nTo that end, create 'find_tip_objects' and\n'filter_bitmap_exclude_type', and redefine the aforementioned functions\nin terms of those.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n pack-bitmap.c | 35 ++++++++++++++++++++++++-----------\n 1 file changed, 24 insertions(+), 11 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 49a8d10d0c..3693c9e62f 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -715,8 +715,9 @@ 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+static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git,\n+\t\t\t\t       struct object_list *tip_objects,\n+\t\t\t\t       enum object_type type)\n {\n \tstruct bitmap *result = bitmap_new();\n \tstruct object_list *p;\n@@ -724,7 +725,7 @@ static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git,\n \tfor (p = tip_objects; p; p = p->next) {\n \t\tint pos;\n \n-\t\tif (p->item->type != OBJ_BLOB)\n+\t\tif (p->item->type != type)\n \t\t\tcontinue;\n \n \t\tpos = bitmap_position(bitmap_git, &p->item->oid);\n@@ -737,9 +738,10 @@ static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git,\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+static void filter_bitmap_exclude_type(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       enum object_type type)\n {\n \tstruct eindex *eindex = &bitmap_git->ext_index;\n \tstruct bitmap *tips;\n@@ -747,18 +749,21 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,\n \teword_t mask;\n \tuint32_t i;\n \n+\tif (type != OBJ_BLOB)\n+\t\tBUG(\"filter_bitmap_exclude_type: unsupported type '%d'\", type);\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 * objects 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+\ttips = find_tip_objects(bitmap_git, tip_objects, type);\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+\tfor (i = 0, init_type_iterator(&it, bitmap_git, type);\n \t     i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);\n \t     i++) {\n \t\tif (i < tips->word_alloc)\n@@ -773,7 +778,7 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,\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\tif (eindex->objects[i]->type == type &&\n \t\t    bitmap_get(to_filter, pos) &&\n \t\t    !bitmap_get(tips, pos))\n \t\t\tbitmap_unset(to_filter, pos);\n@@ -782,6 +787,14 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,\n \tbitmap_free(tips);\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+\tfilter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,\n+\t\t\t\t   OBJ_BLOB);\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@@ -820,7 +833,7 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,\n \teword_t mask;\n \tuint32_t i;\n \n-\ttips = find_tip_blobs(bitmap_git, tip_objects);\n+\ttips = find_tip_objects(bitmap_git, tip_objects, OBJ_BLOB);\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-- \n2.26.0.113.ge9739cdccc\n\n"},{"id":"397010","messageId":"87b21d72bb588f7366d928544aeaf4de68b027a7.1588633810.git.me@ttaylorr.com","threadId":"53394","inReplyTo":"cover.1588633810.git.me@ttaylorr.com","subject":"[PATCH 3/4] pack-bitmap.c: support 'tree:0' filtering","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-04T23:12:35Z","receivedAt":"2020-05-04T23:12:39Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In the previous patch, we made it easy to define other filters that\nexclude all objects of a certain type. Use that in order to implement\nbitmap-level filtering for the '--filter=tree:<n>' filter when 'n' is\nequal to 0.\n\nThe general case is not helped by bitmaps, since for values of 'n > 0',\nthe object filtering machinery requires a full-blown tree traversal in\norder to determine the depth of a given tree. Caching this is\nnon-obvious, too, since the same tree object can have a different depth\ndepending on the context (e.g., a tree was moved up in the directory\nhierarchy between two commits).\n\nBut, the 'n = 0' case can be helped, and this patch does so. Running\np5310.11 in this tree and on master with the kernel, we can see that\nthis case is helped substantially:\n\n  Test                                  master              this tree\n  --------------------------------------------------------------------------------\n  5310.11: rev-list count with tree:0   10.68(10.39+0.27)   0.06(0.04+0.01) -99.4%\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n pack-bitmap.c                      | 25 ++++++++++++++++++++++++-\n t/perf/p5310-pack-bitmaps.sh       |  5 +++++\n t/t6113-rev-list-bitmap-filters.sh | 21 +++++++++++++++++++++\n 3 files changed, 50 insertions(+), 1 deletion(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 3693c9e62f..195ee8cad0 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -749,7 +749,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,\n \teword_t mask;\n \tuint32_t i;\n \n-\tif (type != OBJ_BLOB)\n+\tif (type != OBJ_BLOB && type != OBJ_TREE)\n \t\tBUG(\"filter_bitmap_exclude_type: unsupported type '%d'\", type);\n \n \t/*\n@@ -867,6 +867,20 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,\n \tbitmap_free(tips);\n }\n \n+static void filter_bitmap_tree_depth(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+\tif (limit)\n+\t\tBUG(\"filter_bitmap_tree_depth given non-zero limit\");\n+\n+\tfilter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,\n+\t\t\t\t   OBJ_TREE);\n+\tfilter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,\n+\t\t\t\t   OBJ_BLOB);\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@@ -890,6 +904,15 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,\n \t\treturn 0;\n \t}\n \n+\tif (filter->choice == LOFC_TREE_DEPTH &&\n+\t    filter->tree_exclude_depth == 0) {\n+\t\tif (bitmap_git)\n+\t\t\tfilter_bitmap_tree_depth(bitmap_git, tip_objects,\n+\t\t\t\t\t\t to_filter,\n+\t\t\t\t\t\t filter->tree_exclude_depth);\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 80c53edca7..75ccf9f4e3 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -53,6 +53,11 @@ test_perf 'rev-list count with blob:limit=1k' '\n \t\t--filter=blob:limit=1k >/dev/null\n '\n \n+test_perf 'rev-list count with tree:0' '\n+\tgit rev-list --use-bitmap-index --count --objects --all \\\n+\t\t--filter=tree:0 >/dev/null\n+'\n+\n test_perf 'simulated partial clone' '\n \tgit pack-objects --stdout --all --filter=blob:none </dev/null >/dev/null\n '\ndiff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh\nindex 145603f124..2b551e6fd0 100755\n--- a/t/t6113-rev-list-bitmap-filters.sh\n+++ b/t/t6113-rev-list-bitmap-filters.sh\n@@ -53,4 +53,25 @@ test_expect_success 'blob:limit filter with specified blob' '\n \ttest_bitmap_traversal expect actual\n '\n \n+test_expect_success 'tree:0 filter' '\n+\tgit rev-list --objects --filter=tree:0 HEAD >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t     --objects --filter=tree:0 HEAD >actual &&\n+\ttest_bitmap_traversal expect actual\n+'\n+\n+test_expect_success 'tree:0 filter with specified blob, tree' '\n+\tgit rev-list --objects --filter=tree:0 HEAD HEAD:two.t >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t     --objects --filter=tree:0 HEAD HEAD:two.t >actual &&\n+\ttest_bitmap_traversal expect actual\n+'\n+\n+test_expect_success 'tree:1 filter' '\n+\tgit rev-list --objects --filter=tree:1 HEAD >expect &&\n+\tgit rev-list --use-bitmap-index \\\n+\t\t     --objects --filter=tree:1 HEAD >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.26.0.113.ge9739cdccc\n\n"},{"id":"397011","messageId":"f1eb194b9fdf5e385610fa3c0ddee22b89cf4f0e.1588633810.git.me@ttaylorr.com","threadId":"53394","inReplyTo":"cover.1588633810.git.me@ttaylorr.com","subject":"[PATCH 4/4] pack-bitmap: pass object filter to fill-in traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-04T23:12:38Z","receivedAt":"2020-05-04T23:12:43Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"From: Jeff King <peff@peff.net>\n\nSometimes a bitmap traversal still has to walk some commits manually,\nbecause those commits aren't included in the bitmap packfile (e.g., due\nto a push or commit since the last full repack). If we're given an\nobject filter, we don't pass it down to this traversal. It's not\nnecessary for correctness because the bitmap code has its own filters to\npost-process the bitmap result (which it must, to filter out the objects\nthat _are_ mentioned in the bitmapped packfile).\n\nAnd with blob filters, there was no performance reason to pass along\nthose filters, either. The fill-in traversal could omit them from the\nresult, but it wouldn't save us any time to do so, since we'd still have\nto walk each tree entry to see if it's a blob or not.\n\nBut now that we support tree filters, there's opportunity for savings. A\ntree:depth=0 filter means we can avoid accessing trees entirely, since\nwe know we won't them (or any of the subtrees or blobs they point to).\nThe new test in p5310 shows this off (the \"partial bitmap\" state is one\nwhere HEAD~100 and its ancestors are all in a bitmapped pack, but\nHEAD~100..HEAD are not). Here are the results (run against linux.git):\n\n  Test                                                  HEAD^               HEAD\n  -------------------------------------------------------------------------------------------------\n  [...]\n  5310.16: rev-list with tree filter (partial bitmap)   0.19(0.17+0.02)     0.03(0.02+0.01) -84.2%\n\nThe absolute number of savings isn't _huge_, but keep in mind that we\nonly omitted 100 first-parent links (in the version of linux.git here,\nthat's 894 actual commits). In a more pathological case, we might have a\nmuch larger proportion of non-bitmapped commits. I didn't bother\ncreating such a case in the perf script because the setup is expensive,\nand this is plenty to show the savings as a percentage.\n\nSigned-off-by: Jeff King <peff@peff.net>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\n---\n pack-bitmap.c                | 14 +++++++++-----\n t/perf/p5310-pack-bitmaps.sh |  5 +++++\n 2 files changed, 14 insertions(+), 5 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 195ee8cad0..4077e731e8 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -506,7 +506,8 @@ static int should_include(struct commit *commit, void *_data)\n static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\t\t\t   struct rev_info *revs,\n \t\t\t\t   struct object_list *roots,\n-\t\t\t\t   struct bitmap *seen)\n+\t\t\t\t   struct bitmap *seen,\n+\t\t\t\t   struct list_objects_filter_options *filter)\n {\n \tstruct bitmap *base = NULL;\n \tint needs_walk = 0;\n@@ -599,8 +600,9 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n \t\tshow_data.bitmap_git = bitmap_git;\n \t\tshow_data.base = base;\n \n-\t\ttraverse_commit_list(revs, show_commit, show_object,\n-\t\t\t\t     &show_data);\n+\t\ttraverse_commit_list_filtered(filter, revs,\n+\t\t\t\t\t      show_commit, show_object,\n+\t\t\t\t\t      &show_data, NULL);\n \t}\n \n \treturn base;\n@@ -999,7 +1001,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \n \tif (haves) {\n \t\trevs->ignore_missing_links = 1;\n-\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n+\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL,\n+\t\t\t\t\t    filter);\n \t\treset_revision_walk();\n \t\trevs->ignore_missing_links = 0;\n \n@@ -1007,7 +1010,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n \t\t\tBUG(\"failed to perform bitmap walk\");\n \t}\n \n-\twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n+\twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap,\n+\t\t\t\t    filter);\n \n \tif (!wants_bitmap)\n \t\tBUG(\"failed to perform bitmap walk\");\ndiff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\nindex 75ccf9f4e3..b3e725f031 100755\n--- a/t/perf/p5310-pack-bitmaps.sh\n+++ b/t/perf/p5310-pack-bitmaps.sh\n@@ -91,4 +91,9 @@ test_perf 'pack to file (partial bitmap)' '\n \tgit pack-objects --use-bitmap-index --all pack2b </dev/null >/dev/null\n '\n \n+test_perf 'rev-list with tree filter (partial bitmap)' '\n+\tgit rev-list --use-bitmap-index --count --objects --all \\\n+\t\t--filter=tree:0 >/dev/null\n+'\n+\n test_done\n-- \n2.26.0.113.ge9739cdccc\n"},{"id":"397048","messageId":"xmqqh7wvc6l1.fsf@gitster.c.googlers.com","threadId":"53394","inReplyTo":"bb7d99ee2582d60e2413df56cb2c3fb06c18de8e.1588633810.git.me@ttaylorr.com","subject":"Re: [PATCH 1/4] list-objects-filter: treat NULL filter_options as \"disabled\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-05-05T05:07:54Z","receivedAt":"2020-05-05T05:08:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> From: Jeff King <peff@peff.net>\n>\n> In most callers, we have an actual list_objects_filter_options struct,\n> and if no filtering is desired its \"choice\" element will be\n> LOFC_DISABLED. However, some code may have only a pointer to such a\n> struct which may be NULL (because _their_ callers didn't care about\n> filtering, either). Rather than forcing them to handle this explicitly\n> like:\n>\n>   if (filter_options)\n>           traverse_commit_list_filtered(filter_options, revs,\n> \t                                show_commit, show_object,\n> \t\t\t\t\tshow_data, NULL);\n>   else\n>           traverse_commit_list(revs, show_commit, show_object,\n> \t                             show_data);\n>\n> let's just treat a NULL filter_options the same as LOFC_DISABLED. We\n> only need a small change, since that option struct is converted into a\n> real filter only in the \"init\" function.\n\nThis is not a problem the patch introduces, but anytime we improve\nthe revision traversal API, Documentation/MyFirstObjectWalk.txt\nrisks to be left behind (in the sense that it still is correct but\nis now suboptimal) or outright broken (when we change the function\nsignature).  I wonder if we can do some \"mark-up\" to that tutorial\nso that we can extract runnable code in some of the tests and make\nsure the code snippet in the documentation is still OK.\n\nAs to the patch, there apparently is no existing caller that passes\nNULL to the function (or they would be immediately segfaulting), so\nby definition, this step alone cannot break anything, but at the\nsame time, it is a bit hard to assess if this is a good change with\nthis step alone.  So let's read on.\n\nThanks.\n\n>\n> Signed-off-by: Jeff King <peff@peff.net>\n> Signed-off-by: Taylor Blau <me@ttaylorr.com>\n> ---\n>  list-objects-filter.c | 3 +++\n>  1 file changed, 3 insertions(+)\n>\n> diff --git a/list-objects-filter.c b/list-objects-filter.c\n> index 1e8d4e763d..0a3ef3cab3 100644\n> --- a/list-objects-filter.c\n> +++ b/list-objects-filter.c\n> @@ -663,6 +663,9 @@ struct filter *list_objects_filter__init(\n>  \n>  \tassert((sizeof(s_filters) / sizeof(s_filters[0])) == LOFC__COUNT);\n>  \n> +\tif (!filter_options)\n> +\t\treturn NULL;\n> +\n>  \tif (filter_options->choice >= LOFC__COUNT)\n>  \t\tBUG(\"invalid list-objects filter choice: %d\",\n>  \t\t    filter_options->choice);\n"},{"id":"397049","messageId":"xmqqd07jc6d4.fsf@gitster.c.googlers.com","threadId":"53394","inReplyTo":"b43a12894e7edf7d54ce2e9679f8db7dabec23e0.1588633810.git.me@ttaylorr.com","subject":"Re: [PATCH 2/4] pack-bitmap.c: make object filtering functions generic","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-05-05T05:12:39Z","receivedAt":"2020-05-05T05:12:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> In 4f3bd5606a (pack-bitmap: implement BLOB_NONE filtering, 2020-02-14),\n> filtering support for bitmaps was added for the 'LOFC_BLOB_NONE' filter.\n>\n> In the future, we would like to add support for filters that behave as\n> if they exclude a certain type of object, for e.g., the tree depth\n> filter with depth 0.\n>\n> To prepare for this, make some of the functions used for filtering more\n> generic, such as 'find_tip_blobs' and 'filter_bitmap_blob_none' so that\n> they can work over arbitrary object types.\n>\n> To that end, create 'find_tip_objects' and\n> 'filter_bitmap_exclude_type', and redefine the aforementioned functions\n> in terms of those.\n\nOK, so instead of blobs at the tip, we find objects of requested\ntype at the tip, which makes sense.\n\nSimilarly, blob_none filter used to exclude blobs at the tip, but a\nmore generic form is to exclude objects of requested type at the\ntip.\n\nAnd these \"more generic\" variants are named quite intuitively.\n\nThen the blob_none filter becomes a thin wrapper of the more generic\none, with hardcoded OBJ_BLOB type.\n\nNicely done.\n"},{"id":"397050","messageId":"xmqq7dxrc5r9.fsf@gitster.c.googlers.com","threadId":"53394","inReplyTo":"87b21d72bb588f7366d928544aeaf4de68b027a7.1588633810.git.me@ttaylorr.com","subject":"Re: [PATCH 3/4] pack-bitmap.c: support 'tree:0' filtering","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-05-05T05:25:46Z","receivedAt":"2020-05-05T05:25:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index 3693c9e62f..195ee8cad0 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -749,7 +749,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,\n>  \teword_t mask;\n>  \tuint32_t i;\n>  \n> -\tif (type != OBJ_BLOB)\n> +\tif (type != OBJ_BLOB && type != OBJ_TREE)\n>  \t\tBUG(\"filter_bitmap_exclude_type: unsupported type '%d'\", type);\n\nOK.  This is the same as the previous step, but why would we even\nneed this guard?  find_tip_objects() is equipped to find tips of any\nobject type, iterating on the bitmap for \"type\", or flipping the\nbits in the to_filter bitmap, does not have any limitation to the\nblob type in the previous step, and there is no limitation to the\nblob or tree types after this step, either, no?\n\n> @@ -867,6 +867,20 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,\n>  \tbitmap_free(tips);\n>  }\n>  \n> +static void filter_bitmap_tree_depth(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> +\tif (limit)\n> +\t\tBUG(\"filter_bitmap_tree_depth given non-zero limit\");\n\nThis one does make sense, because the code to exclude all trees and\nall blobs we have below won't be able to cull only trees at a given\ndepth or deeper.\n\n> +\tfilter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,\n> +\t\t\t\t   OBJ_TREE);\n> +\tfilter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,\n> +\t\t\t\t   OBJ_BLOB);\n\nAnd these two are quite straight-forward.\n\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> @@ -890,6 +904,15 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,\n>  \t\treturn 0;\n>  \t}\n>  \n> +\tif (filter->choice == LOFC_TREE_DEPTH &&\n> +\t    filter->tree_exclude_depth == 0) {\n> +\t\tif (bitmap_git)\n> +\t\t\tfilter_bitmap_tree_depth(bitmap_git, tip_objects,\n> +\t\t\t\t\t\t to_filter,\n> +\t\t\t\t\t\t filter->tree_exclude_depth);\n\nI briefly wondered if it is cleaner to read if we hardcode 0 as the\nlast argument.  But if the helper function ever learns how to filter\nby tree with non-zero depth, we can only tweak the if() condition\nwithout changing the call, so the way you wrote it is the right way.\n\nThanks.\n"},{"id":"397051","messageId":"xmqq1rnzc52c.fsf@gitster.c.googlers.com","threadId":"53394","inReplyTo":"f1eb194b9fdf5e385610fa3c0ddee22b89cf4f0e.1588633810.git.me@ttaylorr.com","subject":"Re: [PATCH 4/4] pack-bitmap: pass object filter to fill-in traversal","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-05-05T05:40:43Z","receivedAt":"2020-05-05T05:40:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> But now that we support tree filters, there's opportunity for savings. A\n> tree:depth=0 filter means we can avoid accessing trees entirely, since\n> we know we won't them (or any of the subtrees or blobs they point to).\n\n\"we know we won't _have_ them\"?\n\n> @@ -506,7 +506,8 @@ static int should_include(struct commit *commit, void *_data)\n>  static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n>  \t\t\t\t   struct rev_info *revs,\n>  \t\t\t\t   struct object_list *roots,\n> -\t\t\t\t   struct bitmap *seen)\n> +\t\t\t\t   struct bitmap *seen,\n> +\t\t\t\t   struct list_objects_filter_options *filter)\n>  {\n>  \tstruct bitmap *base = NULL;\n>  \tint needs_walk = 0;\n> @@ -599,8 +600,9 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n>  \t\tshow_data.bitmap_git = bitmap_git;\n>  \t\tshow_data.base = base;\n>  \n> -\t\ttraverse_commit_list(revs, show_commit, show_object,\n> -\t\t\t\t     &show_data);\n> +\t\ttraverse_commit_list_filtered(filter, revs,\n> +\t\t\t\t\t      show_commit, show_object,\n> +\t\t\t\t\t      &show_data, NULL);\n\nAnd then finally the change in step 1/4 pays off.\n\n>  \t}\n>  \n>  \treturn base;\n> @@ -999,7 +1001,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n>  \n>  \tif (haves) {\n>  \t\trevs->ignore_missing_links = 1;\n> -\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n> +\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL,\n> +\t\t\t\t\t    filter);\n>  \t\treset_revision_walk();\n>  \t\trevs->ignore_missing_links = 0;\n>  \n> @@ -1007,7 +1010,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n>  \t\t\tBUG(\"failed to perform bitmap walk\");\n>  \t}\n>  \n> -\twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n> +\twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap,\n> +\t\t\t\t    filter);\n>  \n>  \tif (!wants_bitmap)\n>  \t\tBUG(\"failed to perform bitmap walk\");\n> diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\n> index 75ccf9f4e3..b3e725f031 100755\n> --- a/t/perf/p5310-pack-bitmaps.sh\n> +++ b/t/perf/p5310-pack-bitmaps.sh\n> @@ -91,4 +91,9 @@ test_perf 'pack to file (partial bitmap)' '\n>  \tgit pack-objects --use-bitmap-index --all pack2b </dev/null >/dev/null\n>  '\n>  \n> +test_perf 'rev-list with tree filter (partial bitmap)' '\n> +\tgit rev-list --use-bitmap-index --count --objects --all \\\n> +\t\t--filter=tree:0 >/dev/null\n> +'\n> +\n>  test_done\n"},{"id":"397102","messageId":"20200505155951.GA69300@syl.local","threadId":"53394","inReplyTo":"xmqq7dxrc5r9.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 3/4] pack-bitmap.c: support 'tree:0' filtering","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-05T15:59:51Z","receivedAt":"2020-05-05T15:59:56Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, May 04, 2020 at 10:25:46PM -0700, Junio C Hamano wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n>\n> > diff --git a/pack-bitmap.c b/pack-bitmap.c\n> > index 3693c9e62f..195ee8cad0 100644\n> > --- a/pack-bitmap.c\n> > +++ b/pack-bitmap.c\n> > @@ -749,7 +749,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,\n> >  \teword_t mask;\n> >  \tuint32_t i;\n> >\n> > -\tif (type != OBJ_BLOB)\n> > +\tif (type != OBJ_BLOB && type != OBJ_TREE)\n> >  \t\tBUG(\"filter_bitmap_exclude_type: unsupported type '%d'\", type);\n>\n> OK.  This is the same as the previous step, but why would we even\n> need this guard?  find_tip_objects() is equipped to find tips of any\n> object type, iterating on the bitmap for \"type\", or flipping the\n> bits in the to_filter bitmap, does not have any limitation to the\n> blob type in the previous step, and there is no limitation to the\n> blob or tree types after this step, either, no?\n\nI think we need some sort of guard here, since we could receive any\nvalue of object_type, but you're right that this isn't the right one. It\nshould probably be something like:\n\n  if (type < OBJ_COMMIT || type > OBJ_TAG)\n\nto pick out the sentinel values like OBJ_BAD and OBJ_NONE, as well as\nthe pack-specific types, like OBJ_OFS_DELTA and so on.\n\nI fixed this locally, and will resend it along with the rest of v2 in a\nday or so. Thanks for a review :).\n\n> > @@ -867,6 +867,20 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,\n> >  \tbitmap_free(tips);\n> >  }\n> >\n> > +static void filter_bitmap_tree_depth(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> > +\tif (limit)\n> > +\t\tBUG(\"filter_bitmap_tree_depth given non-zero limit\");\n>\n> This one does make sense, because the code to exclude all trees and\n> all blobs we have below won't be able to cull only trees at a given\n> depth or deeper.\n>\n> > +\tfilter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,\n> > +\t\t\t\t   OBJ_TREE);\n> > +\tfilter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter,\n> > +\t\t\t\t   OBJ_BLOB);\n>\n> And these two are quite straight-forward.\n>\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> > @@ -890,6 +904,15 @@ static int filter_bitmap(struct bitmap_index *bitmap_git,\n> >  \t\treturn 0;\n> >  \t}\n> >\n> > +\tif (filter->choice == LOFC_TREE_DEPTH &&\n> > +\t    filter->tree_exclude_depth == 0) {\n> > +\t\tif (bitmap_git)\n> > +\t\t\tfilter_bitmap_tree_depth(bitmap_git, tip_objects,\n> > +\t\t\t\t\t\t to_filter,\n> > +\t\t\t\t\t\t filter->tree_exclude_depth);\n>\n> I briefly wondered if it is cleaner to read if we hardcode 0 as the\n> last argument.  But if the helper function ever learns how to filter\n> by tree with non-zero depth, we can only tweak the if() condition\n> without changing the call, so the way you wrote it is the right way.\n>\n> Thanks.\n\nThanks,\nTaylor\n"},{"id":"397103","messageId":"20200505160014.GB69300@syl.local","threadId":"53394","inReplyTo":"xmqq1rnzc52c.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 4/4] pack-bitmap: pass object filter to fill-in traversal","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-05T16:00:14Z","receivedAt":"2020-05-05T16:00:19Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, May 04, 2020 at 10:40:43PM -0700, Junio C Hamano wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n>\n> > But now that we support tree filters, there's opportunity for savings. A\n> > tree:depth=0 filter means we can avoid accessing trees entirely, since\n> > we know we won't them (or any of the subtrees or blobs they point to).\n>\n> \"we know we won't _have_ them\"?\n\nYep, fixed. Thanks for pointing it out.\n\n> > @@ -506,7 +506,8 @@ static int should_include(struct commit *commit, void *_data)\n> >  static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n> >  \t\t\t\t   struct rev_info *revs,\n> >  \t\t\t\t   struct object_list *roots,\n> > -\t\t\t\t   struct bitmap *seen)\n> > +\t\t\t\t   struct bitmap *seen,\n> > +\t\t\t\t   struct list_objects_filter_options *filter)\n> >  {\n> >  \tstruct bitmap *base = NULL;\n> >  \tint needs_walk = 0;\n> > @@ -599,8 +600,9 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git,\n> >  \t\tshow_data.bitmap_git = bitmap_git;\n> >  \t\tshow_data.base = base;\n> >\n> > -\t\ttraverse_commit_list(revs, show_commit, show_object,\n> > -\t\t\t\t     &show_data);\n> > +\t\ttraverse_commit_list_filtered(filter, revs,\n> > +\t\t\t\t\t      show_commit, show_object,\n> > +\t\t\t\t\t      &show_data, NULL);\n>\n> And then finally the change in step 1/4 pays off.\n\nWoohoo!\n\n> >  \t}\n> >\n> >  \treturn base;\n> > @@ -999,7 +1001,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n> >\n> >  \tif (haves) {\n> >  \t\trevs->ignore_missing_links = 1;\n> > -\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL);\n> > +\t\thaves_bitmap = find_objects(bitmap_git, revs, haves, NULL,\n> > +\t\t\t\t\t    filter);\n> >  \t\treset_revision_walk();\n> >  \t\trevs->ignore_missing_links = 0;\n> >\n> > @@ -1007,7 +1010,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,\n> >  \t\t\tBUG(\"failed to perform bitmap walk\");\n> >  \t}\n> >\n> > -\twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);\n> > +\twants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap,\n> > +\t\t\t\t    filter);\n> >\n> >  \tif (!wants_bitmap)\n> >  \t\tBUG(\"failed to perform bitmap walk\");\n> > diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh\n> > index 75ccf9f4e3..b3e725f031 100755\n> > --- a/t/perf/p5310-pack-bitmaps.sh\n> > +++ b/t/perf/p5310-pack-bitmaps.sh\n> > @@ -91,4 +91,9 @@ test_perf 'pack to file (partial bitmap)' '\n> >  \tgit pack-objects --use-bitmap-index --all pack2b </dev/null >/dev/null\n> >  '\n> >\n> > +test_perf 'rev-list with tree filter (partial bitmap)' '\n> > +\tgit rev-list --use-bitmap-index --count --objects --all \\\n> > +\t\t--filter=tree:0 >/dev/null\n> > +'\n> > +\n> >  test_done\n\nThanks,\nTaylor\n"},{"id":"397125","messageId":"xmqqftceb5wb.fsf@gitster.c.googlers.com","threadId":"53394","inReplyTo":"20200505155951.GA69300@syl.local","subject":"Re: [PATCH 3/4] pack-bitmap.c: support 'tree:0' filtering","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-05-05T18:20:20Z","receivedAt":"2020-05-05T18:20:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> I think we need some sort of guard here, since we could receive any\n> value of object_type, but you're right that this isn't the right one. It\n> should probably be something like:\n>\n>   if (type < OBJ_COMMIT || type > OBJ_TAG)\n>\n> to pick out the sentinel values like OBJ_BAD and OBJ_NONE, as well as\n> the pack-specific types, like OBJ_OFS_DELTA and so on.\n\nYeah, it looked strange to start checking for OBJ_BLOB and OBJ_TREE\nin commits that starts passing these types to the function, while\nthe code in the function was prepared to take any valid type, so\nusing the above condition from the get-go would probably be a lot\nmore sensible.\n\n"}]}