{"thread":{"id":"54909","subject":"test-tool: bloom: generate_filter for multiple string?","startedAt":"2020-12-31T03:56:18Z","lastAt":"2021-01-13T15:14:36Z","messageCount":8,"participants":["Đoàn Trần Công Danh","Derrick Stolee","Taylor Blau"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"413209","messageId":"20201231035438.22533-1-congdanhqx@gmail.com","threadId":"54909","inReplyTo":null,"subject":"test-tool: bloom: generate_filter for multiple string?","fromName":"Đoàn Trần Công Danh","fromEmail":"congdanhqx@gmail.com","sentAt":"2020-12-31T03:54:38Z","receivedAt":"2020-12-31T03:56:18Z","isPatch":false,"sender":{"key":"congdanhqx@gmail.com","avatar":"https://avatars.githubusercontent.com/u/42673067?v=4"},"body":"\nHello,\n\nI'm reading the code for Bloom Filter to see if arXiv:2012.00472\ncould be an improvement.\n\nI'm not sure if I'm missing something or it's our test-bloom generate_filter\ndoesn't really support testing for multiple inputs.\n\nIf I understand correctly, we should either:\n* allocate more entry for inputs; or\n* abort if argc != 3\n\ndiff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c\nindex 46e97b04eb..1026facc59 100644\n--- a/t/helper/test-bloom.c\n+++ b/t/helper/test-bloom.c\n@@ -68,12 +68,14 @@ int cmd__bloom(int argc, const char **argv)\n \tif (!strcmp(argv[1], \"generate_filter\")) {\n \t\tstruct bloom_filter filter;\n \t\tint i = 2;\n-\t\tfilter.len =  (settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;\n-\t\tfilter.data = xcalloc(filter.len, sizeof(unsigned char));\n \n \t\tif (argc - 1 < i)\n \t\t\tusage(bloom_usage);\n \n+\t\tfilter.len = (settings.bits_per_entry * (argc - 2) + BITS_PER_WORD - 1)\n+\t\t\t/ BITS_PER_WORD;\n+\t\tfilter.data = xcalloc(filter.len, sizeof(unsigned char));\n+\n \t\twhile (argv[i]) {\n \t\t\tadd_string_to_filter(argv[i], &filter);\n \t\t\ti++;\ndiff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\nindex 7e4ab1795f..6d83927c86 100755\n--- a/t/t0095-bloom.sh\n+++ b/t/t0095-bloom.sh\n@@ -67,6 +67,17 @@ test_expect_success 'compute bloom key for test string 2' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'compute bloom key for multiple string' '\n+\tcat >expect <<-\\EOF &&\n+\tHashes:0xb270de9b|0x1bb6f26e|0x84fd0641|0xee431a14|0x57892de7|0xc0cf41ba|0x2a15558d|\n+\tHashes:0x20ab385b|0xf5237fe2|0xc99bc769|0x9e140ef0|0x728c5677|0x47049dfe|0x1b7ce585|\n+\tFilter_Length:3\n+\tFilter_Data:45|ba|ac|\n+\tEOF\n+\ttest-tool bloom generate_filter \"Hello world!\" file.txt >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success 'get bloom filters for commit with no changes' '\n \tgit init &&\n \tgit commit --allow-empty -m \"c0\" &&\n-- \nDanh\n"},{"id":"413213","messageId":"dfe3fbf9-4708-cd53-d78e-780375224b8e@gmail.com","threadId":"54909","inReplyTo":"20201231035438.22533-1-congdanhqx@gmail.com","subject":"Re: test-tool: bloom: generate_filter for multiple string?","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-12-31T11:31:52Z","receivedAt":"2020-12-31T11:32:42Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 12/30/2020 10:54 PM, Đoàn Trần Công Danh wrote:\n> \n> Hello,\n> \n> I'm reading the code for Bloom Filter to see if arXiv:2012.00472\n> could be an improvement.\n> \n> I'm not sure if I'm missing something or it's our test-bloom generate_filter\n> doesn't really support testing for multiple inputs.\n\nIt doesn't support creating a _realistic_ filter of the given size. The tests\nat this level are more about keeping the filters consistent so we can trust\nthat we are not accidentally changing the hashing algorithm and its file format.\n\nThe test works if we provide multiple inputs, the problem is that the resulting\nfilter has a higher density of bits than we expect, since we didn't size it\naccording to the number of inputs.\n\n> If I understand correctly, we should either:\n> * allocate more entry for inputs; or\n> * abort if argc != 3\n\nEither approach would be fine. I wonder what your goal is for testing the\nmultiple inputs. Are you expecting a larger filter to demonstrate some\nbehavior that is not tested by a small filter?\n\n> diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c\n> index 46e97b04eb..1026facc59 100644\n> --- a/t/helper/test-bloom.c\n> +++ b/t/helper/test-bloom.c\n> @@ -68,12 +68,14 @@ int cmd__bloom(int argc, const char **argv)\n>  \tif (!strcmp(argv[1], \"generate_filter\")) {\n>  \t\tstruct bloom_filter filter;\n>  \t\tint i = 2;\n> -\t\tfilter.len =  (settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;\n> -\t\tfilter.data = xcalloc(filter.len, sizeof(unsigned char));\n>  \n>  \t\tif (argc - 1 < i)\n>  \t\t\tusage(bloom_usage);\n>  \n> +\t\tfilter.len = (settings.bits_per_entry * (argc - 2) + BITS_PER_WORD - 1)\n> +\t\t\t/ BITS_PER_WORD;\n> +\t\tfilter.data = xcalloc(filter.len, sizeof(unsigned char));\n> +\n\nWhitespace issues aside, this is the right approach to make the filter grow with\nthe input.\n\n>  \t\twhile (argv[i]) {\n>  \t\t\tadd_string_to_filter(argv[i], &filter);\n>  \t\t\ti++;\n> diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\n> index 7e4ab1795f..6d83927c86 100755\n> --- a/t/t0095-bloom.sh\n> +++ b/t/t0095-bloom.sh\n> @@ -67,6 +67,17 @@ test_expect_success 'compute bloom key for test string 2' '\n>  \ttest_cmp expect actual\n>  '\n>  \n> +test_expect_success 'compute bloom key for multiple string' '\n> +\tcat >expect <<-\\EOF &&\n> +\tHashes:0xb270de9b|0x1bb6f26e|0x84fd0641|0xee431a14|0x57892de7|0xc0cf41ba|0x2a15558d|\n> +\tHashes:0x20ab385b|0xf5237fe2|0xc99bc769|0x9e140ef0|0x728c5677|0x47049dfe|0x1b7ce585|\n\nMultiple hash outputs work already, helping us build confidence that our\nhash algorithm hasn't changed.\n\n> +\tFilter_Length:3\n> +\tFilter_Data:45|ba|ac|\n\nAnd this is the part of the output that you are changing.\n\n> +\tEOF\n> +\ttest-tool bloom generate_filter \"Hello world!\" file.txt >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n\nSo, your suggested change has merit. I just wonder what value it provides on top\nof the current implementation? If your goal is to create a way to inspect a full-sized\nfilter, then that would be interesting to explore.\n\nThanks,\n-Stolee\n\n"},{"id":"413455","messageId":"X/RrAAXsQXdMJbpo@danh.dev","threadId":"54909","inReplyTo":"dfe3fbf9-4708-cd53-d78e-780375224b8e@gmail.com","subject":"Re: test-tool: bloom: generate_filter for multiple string?","fromName":"Đoàn Trần Công Danh","fromEmail":"congdanhqx@gmail.com","sentAt":"2021-01-05T13:34:56Z","receivedAt":"2021-01-05T13:35:41Z","isPatch":false,"sender":{"key":"congdanhqx@gmail.com","avatar":"https://avatars.githubusercontent.com/u/42673067?v=4"},"body":"On 2020-12-31 06:31:52-0500, Derrick Stolee <stolee@gmail.com> wrote:\n> On 12/30/2020 10:54 PM, Đoàn Trần Công Danh wrote:\n> > I'm reading the code for Bloom Filter to see if arXiv:2012.00472\n> > could be an improvement.\n> > \n> > I'm not sure if I'm missing something or it's our test-bloom generate_filter\n> > doesn't really support testing for multiple inputs.\n> \n> It doesn't support creating a _realistic_ filter of the given size. The tests\n> at this level are more about keeping the filters consistent so we can trust\n> that we are not accidentally changing the hashing algorithm and its file format.\n\n(Sorry for this late reply)\n\nYes, make sense.\n\n> The test works if we provide multiple inputs, the problem is that the resulting\n> filter has a higher density of bits than we expect, since we didn't size it\n> according to the number of inputs.\n\nOK.\n\n> > If I understand correctly, we should either:\n> > * allocate more entry for inputs; or\n> > * abort if argc != 3\n> \n> Either approach would be fine. I wonder what your goal is for testing the\n> multiple inputs. Are you expecting a larger filter to demonstrate some\n> behavior that is not tested by a small filter?\n\nI was expecting a larger filter to trying with some ideas that I had\nin mind before implement it in real code.\nHowever, after toying with my idea, I think it's more of a solution\nlooking for problem.\n(The original post was posted before I realised that).\n\n> > diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c\n> > index 46e97b04eb..1026facc59 100644\n> > --- a/t/helper/test-bloom.c\n> > +++ b/t/helper/test-bloom.c\n> > @@ -68,12 +68,14 @@ int cmd__bloom(int argc, const char **argv)\n> >  \tif (!strcmp(argv[1], \"generate_filter\")) {\n> >  \t\tstruct bloom_filter filter;\n> >  \t\tint i = 2;\n> > -\t\tfilter.len =  (settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;\n> > -\t\tfilter.data = xcalloc(filter.len, sizeof(unsigned char));\n> >  \n> >  \t\tif (argc - 1 < i)\n> >  \t\t\tusage(bloom_usage);\n> >  \n> > +\t\tfilter.len = (settings.bits_per_entry * (argc - 2) + BITS_PER_WORD - 1)\n> > +\t\t\t/ BITS_PER_WORD;\n> > +\t\tfilter.data = xcalloc(filter.len, sizeof(unsigned char));\n> > +\n> \n> Whitespace issues aside, this is the right approach to make the filter grow with\n> the input.\n> \n> >  \t\twhile (argv[i]) {\n> >  \t\t\tadd_string_to_filter(argv[i], &filter);\n> >  \t\t\ti++;\n> > diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\n> > index 7e4ab1795f..6d83927c86 100755\n> > --- a/t/t0095-bloom.sh\n> > +++ b/t/t0095-bloom.sh\n> > @@ -67,6 +67,17 @@ test_expect_success 'compute bloom key for test string 2' '\n> >  \ttest_cmp expect actual\n> >  '\n> >  \n> > +test_expect_success 'compute bloom key for multiple string' '\n> > +\tcat >expect <<-\\EOF &&\n> > +\tHashes:0xb270de9b|0x1bb6f26e|0x84fd0641|0xee431a14|0x57892de7|0xc0cf41ba|0x2a15558d|\n> > +\tHashes:0x20ab385b|0xf5237fe2|0xc99bc769|0x9e140ef0|0x728c5677|0x47049dfe|0x1b7ce585|\n> \n> Multiple hash outputs work already, helping us build confidence that our\n> hash algorithm hasn't changed.\n> \n> > +\tFilter_Length:3\n> > +\tFilter_Data:45|ba|ac|\n> \n> And this is the part of the output that you are changing.\n> \n> > +\tEOF\n> > +\ttest-tool bloom generate_filter \"Hello world!\" file.txt >actual &&\n> > +\ttest_cmp expect actual\n> > +'\n> > +\n> \n> So, your suggested change has merit. I just wonder what value it provides on top\n> of the current implementation? If your goal is to create a way to inspect a full-sized\n> filter, then that would be interesting to explore.\n\nYes, originally, I was trying to creat some way to inspect a full-size\nfilter, i.e. a bloom filter for some set of object_id during fetch\nnegotiation.\nBut, I realise it's not a good idea, now.\n\n-- \nDanh\n"},{"id":"414199","messageId":"X/3+PG2hi71tj/UA@nand.local","threadId":"54909","inReplyTo":"20201231035438.22533-1-congdanhqx@gmail.com","subject":"Re: test-tool: bloom: generate_filter for multiple string?","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-12T19:53:32Z","receivedAt":"2021-01-12T19:54:23Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Dec 31, 2020 at 10:54:38AM +0700, Đoàn Trần Công Danh wrote:\n>\n> Hello,\n>\n> I'm reading the code for Bloom Filter to see if arXiv:2012.00472\n> could be an improvement.\n\nI'm late to the party, but I'm curious to hear which part of this\narticle you think would help out the Bloom filter implementation.\n\n(I skimmed the article you're referencing during my time off, but\nhaven't come back to read it in detail since, so it's possible that the\npart I'm missing is just totally obvious.)\n\n> I'm not sure if I'm missing something or it's our test-bloom generate_filter\n> doesn't really support testing for multiple inputs.\n\nThe rest of this discussion downthread seems sane to me.\n\nThanks,\nTaylor\n"},{"id":"414252","messageId":"X/7guF05a/Bb/VNp@danh.dev","threadId":"54909","inReplyTo":"X/3+PG2hi71tj/UA@nand.local","subject":"Re: test-tool: bloom: generate_filter for multiple string?","fromName":"Đoàn Trần Công Danh","fromEmail":"congdanhqx@gmail.com","sentAt":"2021-01-13T11:59:52Z","receivedAt":"2021-01-13T12:00:37Z","isPatch":false,"sender":{"key":"congdanhqx@gmail.com","avatar":"https://avatars.githubusercontent.com/u/42673067?v=4"},"body":"On 2021-01-12 14:53:32-0500, Taylor Blau <me@ttaylorr.com> wrote:\n> On Thu, Dec 31, 2020 at 10:54:38AM +0700, Đoàn Trần Công Danh wrote:\n> > I'm reading the code for Bloom Filter to see if arXiv:2012.00472\n> > could be an improvement.\n> \n> I'm late to the party, but I'm curious to hear which part of this\n> article you think would help out the Bloom filter implementation.\n\nUhm, no. The article doesn't help the Bloom filter implementation.\nThe article was suggesting using Bloom filter to speed-up the\nnegotiation in fetch-pack and upload-pack. Which, in my own quick\nexperience, doesn't help much. Maybe it's me not understand the\narticle idea or I have made a naive implementation. However, I'm not\nconvinced to pursued further.\n\nIf you are curious, I'm attaching 2 quick-and-low-quality patches with\nthis email for your consideration.\n\n-- \nDanh\n\n\nFrom 287d1b94606bbc5475909e5298560cbd28ee998e Mon Sep 17 00:00:00 2001\nFrom: =?UTF-8?q?=C4=90o=C3=A0n=20Tr=E1=BA=A7n=20C=C3=B4ng=20Danh?=\n <congdanhqx@gmail.com>\nDate: Thu, 31 Dec 2020 10:58:22 +0700\nSubject: [PATCH 2/3] fetch-pack: implent bloom filter in client side\nMIME-Version: 1.0\nContent-Type: text/plain; charset=UTF-8\nContent-Transfer-Encoding: 8bit\n\nSigned-off-by: Đoàn Trần Công Danh <congdanhqx@gmail.com>\n---\n fetch-pack.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++++---\n 1 file changed, 81 insertions(+), 4 deletions(-)\n\ndiff --git a/fetch-pack.c b/fetch-pack.c\nindex 876f90c759..f423ccd816 100644\n--- a/fetch-pack.c\n+++ b/fetch-pack.c\n@@ -23,6 +23,9 @@\n #include \"fetch-negotiator.h\"\n #include \"fsck.h\"\n #include \"shallow.h\"\n+#include \"bloom.h\"\n+#include \"list-objects.h\"\n+#include \"revision.h\"\n \n static int transfer_unpack_limit = -1;\n static int fetch_unpack_limit = -1;\n@@ -1184,6 +1187,71 @@ static int add_haves(struct fetch_negotiator *negotiator,\n \treturn ret;\n }\n \n+static int rev_info_insert_ref_oid(const char *refname,\n+\t\t\t\t   const struct object_id *oid,\n+\t\t\t\t   int flag, void *cbdata)\n+{\n+\tstruct rev_info *rev_info = cbdata;\n+\tadd_pending_oid(rev_info, refname, oid, 0);\n+\treturn 1;\n+}\n+\n+static void rev_info_insert_to_oidset(struct commit *commit, void *cbdata)\n+{\n+\tstruct oidset *set = cbdata;\n+\toidset_insert(set, &commit->object.oid);\n+}\n+\n+static void add_bloom(struct strbuf *req_buf, struct oidset *common)\n+{\n+\tstruct oidset_iter iter;\n+\tstruct oidset haves = OIDSET_INIT;\n+\tstruct rev_info rev_info;\n+\tstruct bloom_filter filter;\n+\tstruct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;\n+\tstruct strbuf buf;\n+\tconst struct object_id *oid;\n+\tint i;\n+\n+\tif (oidset_size(common) == 0)\n+\t\treturn;\n+\t\n+\trepo_init_revisions(the_repository, &rev_info, NULL);\n+\n+\toidset_iter_init(common, &iter);\n+\twhile ((oid = oidset_iter_next(&iter))) {\n+\t\tadd_pending_oid(&rev_info, oid_to_hex(oid), oid,\n+\t\t\t       UNINTERESTING | BOTTOM);\n+\t}\n+\n+\tfor_each_rawref(rev_info_insert_ref_oid, &rev_info);\n+\tif (prepare_revision_walk(&rev_info)) {\n+\t\twarning(\"couldn't prepare revision walk for fetch\");\n+\t\treturn;\n+\t}\n+\ttraverse_commit_list(&rev_info, rev_info_insert_to_oidset, NULL, &haves);\n+\tif (oidset_size(&haves) == 0)\n+\t\treturn;\n+\tfilter.len = (oidset_size(&haves) * settings.bits_per_entry + BITS_PER_WORD - 1)\n+\t\t/ BITS_PER_WORD;\n+\tfree(filter.data);\n+\tfilter.data = xcalloc(filter.len, sizeof(unsigned char));\n+\toidset_iter_init(&haves, &iter);\n+\twhile ((oid = oidset_iter_next(&iter))) {\n+\t\tstruct bloom_key key;\n+\t\tfill_bloom_key((const char *)oid->hash, the_hash_algo->rawsz,\n+\t\t\t       &key, &settings);\n+\t\tadd_key_to_filter(&key, &filter, &settings);\n+\t}\n+\n+\tstrbuf_init(&buf, filter.len * 2 + strlen(\"bloom \\n\"));\n+\tstrbuf_addstr(&buf, \"bloom \");\n+\tfor (i = 0; i < filter.len; i++)\n+\t\tstrbuf_addf(&buf, \"%02x\", filter.data[i]);\n+\tstrbuf_addch(&buf, '\\n');\n+\tpacket_buf_write_len(req_buf, buf.buf, buf.len);\n+}\n+\n static int send_fetch_request(struct fetch_negotiator *negotiator, int fd_out,\n \t\t\t      struct fetch_pack_args *args,\n \t\t\t      const struct ref *wants, struct oidset *common,\n@@ -1191,6 +1259,7 @@ static int send_fetch_request(struct fetch_negotiator *negotiator, int fd_out,\n \t\t\t      int sideband_all, int seen_ack)\n {\n \tint ret = 0;\n+\tint transferbloom = 0;\n \tconst char *hash_name;\n \tstruct strbuf req_buf = STRBUF_INIT;\n \n@@ -1278,6 +1347,11 @@ static int send_fetch_request(struct fetch_negotiator *negotiator, int fd_out,\n \tret = add_haves(negotiator, seen_ack, &req_buf,\n \t\t\thaves_to_send, in_vain);\n \n+\t/* Add bloom filter represent commits we have from known common */\n+\tgit_config_get_maybe_bool(\"transfer.bloom\", &transferbloom);\n+\tif (transferbloom && server_supports_v2(\"bloom\", 0))\n+\t\tadd_bloom(&req_buf, common);\n+\n \t/* Send request */\n \tpacket_buf_flush(&req_buf);\n \tif (write_in_full(fd_out, req_buf.buf, req_buf.len) < 0)\n@@ -1352,11 +1426,14 @@ static enum common_found process_acks(struct fetch_negotiator *negotiator,\n \t\t\tstruct object_id oid;\n \t\t\treceived_ack = 1;\n \t\t\tif (!get_oid_hex(arg, &oid)) {\n+\t\t\t\tstruct object *obj;\n \t\t\t\tstruct commit *commit;\n-\t\t\t\toidset_insert(common, &oid);\n-\t\t\t\tcommit = lookup_commit(the_repository, &oid);\n-\t\t\t\tif (negotiator)\n-\t\t\t\t\tnegotiator->ack(negotiator, commit);\n+\t\t\t\tobj = lookup_object(the_repository, &oid);\n+\t\t\t\tif (obj && (commit = object_as_type(obj, OBJ_COMMIT, 0))) {\n+\t\t\t\t\toidset_insert(common, &oid);\n+\t\t\t\t\tif (negotiator)\n+\t\t\t\t\t\tnegotiator->ack(negotiator, commit);\n+\t\t\t\t}\n \t\t\t}\n \t\t\tcontinue;\n \t\t}\n-- \n2.30.0.4.gbe3229325d\n\n\n\nFrom 2c93a1a6c37d40ba37eb083a139b6f1312a547e6 Mon Sep 17 00:00:00 2001\nFrom: =?UTF-8?q?=C4=90o=C3=A0n=20Tr=E1=BA=A7n=20C=C3=B4ng=20Danh?=\n <congdanhqx@gmail.com>\nDate: Mon, 4 Jan 2021 20:23:29 +0700\nSubject: [PATCH 3/3] upload-pack: support bloom filter\nMIME-Version: 1.0\nContent-Type: text/plain; charset=UTF-8\nContent-Transfer-Encoding: 8bit\n\nSigned-off-by: Đoàn Trần Công Danh <congdanhqx@gmail.com>\n---\n serve.c              |  1 +\n t/t5701-git-serve.sh |  1 +\n upload-pack.c        | 86 ++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 88 insertions(+)\n\ndiff --git a/serve.c b/serve.c\nindex eec2fe6f29..daea53bfb7 100644\n--- a/serve.c\n+++ b/serve.c\n@@ -78,6 +78,7 @@ static struct protocol_capability capabilities[] = {\n \t{ \"server-option\", always_advertise, NULL },\n \t{ \"object-format\", object_format_advertise, NULL },\n \t{ \"session-id\", session_id_advertise, NULL },\n+\t{ \"bloom\", always_advertise, NULL },\n };\n \n static void advertise_capabilities(void)\ndiff --git a/t/t5701-git-serve.sh b/t/t5701-git-serve.sh\nindex a1f5fdc9fd..9fabdba6b1 100755\n--- a/t/t5701-git-serve.sh\n+++ b/t/t5701-git-serve.sh\n@@ -16,6 +16,7 @@ test_expect_success 'test capability advertisement' '\n \tfetch=shallow\n \tserver-option\n \tobject-format=$(test_oid algo)\n+\tbloom\n \t0000\n \tEOF\n \ndiff --git a/upload-pack.c b/upload-pack.c\nindex 3b66bf92ba..0eff165865 100644\n--- a/upload-pack.c\n+++ b/upload-pack.c\n@@ -27,6 +27,7 @@\n #include \"commit-graph.h\"\n #include \"commit-reach.h\"\n #include \"shallow.h\"\n+#include \"bloom.h\"\n \n /* Remember to update object flag allocation in object.h */\n #define THEY_HAVE\t(1u << 11)\n@@ -62,6 +63,8 @@ struct upload_pack_data {\n \tstruct object_array have_obj;\n \tstruct oid_array haves;\t\t\t\t\t/* v2 only */\n \tstruct string_list wanted_refs;\t\t\t\t/* v2 only */\n+\tstruct bloom_filter bloom_filter;\t\t\t/* v2 only */\n+\tstruct bloom_filter_settings bloom_filter_settings;\n \n \tstruct object_array shallows;\n \tstruct string_list deepen_not;\n@@ -113,6 +116,13 @@ struct upload_pack_data {\n \tunsigned advertise_sid : 1;\n };\n \n+struct upload_pack_bloom_args\n+{\n+\tstruct bloom_filter *bloom_filter;\n+\tstruct bloom_filter_settings *bloom_filter_settings;\n+\tstruct oid_array *acks;\n+};\n+\n static void upload_pack_data_init(struct upload_pack_data *data)\n {\n \tstruct string_list symref = STRING_LIST_INIT_DUP;\n@@ -125,6 +135,7 @@ static void upload_pack_data_init(struct upload_pack_data *data)\n \tstruct string_list uri_protocols = STRING_LIST_INIT_DUP;\n \tstruct object_array extra_edge_obj = OBJECT_ARRAY_INIT;\n \tstruct string_list allowed_filters = STRING_LIST_INIT_DUP;\n+\tstruct bloom_filter_settings bloom_filter_settings = DEFAULT_BLOOM_FILTER_SETTINGS;\n \n \tmemset(data, 0, sizeof(*data));\n \tdata->symref = symref;\n@@ -132,6 +143,7 @@ static void upload_pack_data_init(struct upload_pack_data *data)\n \tdata->want_obj = want_obj;\n \tdata->have_obj = have_obj;\n \tdata->haves = haves;\n+\tdata->bloom_filter_settings = bloom_filter_settings;\n \tdata->shallows = shallows;\n \tdata->deepen_not = deepen_not;\n \tdata->uri_protocols = uri_protocols;\n@@ -1464,6 +1476,34 @@ static int parse_have(const char *line, struct oid_array *haves)\n \treturn 0;\n }\n \n+static int parse_bloom(const char *line, struct bloom_filter *filter,\n+\t\t       struct bloom_filter_settings *settings)\n+{\n+\tconst char *arg;\n+\tunsigned char *p;\n+\tsize_t len;\n+\tif (!skip_prefix(line, \"bloom \", &arg))\n+\t\treturn 0;\n+\n+\tlen = strlen(arg);\n+\tif (len % 2)\n+\t\tdie(\"git upload-pack: corrupted bloom data with len: %zu\", len);\n+\tfilter->len = len / 2;\n+\tfilter->data = p = xmalloc(filter->len);\n+\twhile (*arg) {\n+\t\tint val = hex2chr(arg);\n+\t\tif (val < 0)\n+\t\t\tgoto errout;\n+\t\t*p++ = val;\n+\t\targ += 2;\n+\t}\n+\treturn 1;\n+errout:\n+\tfilter->len = 0;\n+\tFREE_AND_NULL(filter->data);\n+\treturn 0;\n+}\n+\n static void process_args(struct packet_reader *request,\n \t\t\t struct upload_pack_data *data)\n {\n@@ -1482,6 +1522,9 @@ static void process_args(struct packet_reader *request,\n \t\tif (parse_have(arg, &data->haves))\n \t\t\tcontinue;\n \n+\t\tif (parse_bloom(arg, &data->bloom_filter, &data->bloom_filter_settings))\n+\t\t\tcontinue;\n+\n \t\t/* process args like thin-pack */\n \t\tif (!strcmp(arg, \"thin-pack\")) {\n \t\t\tdata->use_thin_pack = 1;\n@@ -1570,6 +1613,48 @@ static int process_haves(struct upload_pack_data *data, struct oid_array *common\n \treturn 0;\n }\n \n+static void rev_info_bloom_ack(struct commit *commit, void *cbdata)\n+{\n+\tstruct upload_pack_bloom_args *args = cbdata;\n+\tstruct bloom_key key;\n+\tstruct object_id *oid = &commit->object.oid;\n+\tfill_bloom_key((const char *)oid->hash, the_hash_algo->rawsz,\n+\t\t       &key, args->bloom_filter_settings);\n+\tif (bloom_filter_contains(args->bloom_filter, &key,\n+\t\t\t\t  args->bloom_filter_settings))\n+\t\toid_array_append(args->acks, oid);\n+}\n+\n+/* Walking from wanted_obj until haves, add all MAYBE objects to acks */\n+static int process_bloom(struct upload_pack_data *data, struct oid_array *acks)\n+{\n+\tstruct upload_pack_bloom_args args;\n+\tstruct rev_info rev_info;\n+\tconst struct object_id *oid;\n+\tint i;\n+\n+\t/* unknown bloom data and/or no known common objects */\n+\tif (!data->bloom_filter.len || !acks->nr)\n+\t\treturn 0;\n+\trepo_init_revisions(the_repository, &rev_info, NULL);\n+\tfor (i = 0; i < acks->nr; i++) {\n+\t\toid = &acks->oid[i];\n+\t\tadd_pending_oid(&rev_info, oid_to_hex(oid), oid,\n+\t\t\t\tUNINTERESTING | BOTTOM);\n+\t}\n+\tfor (i = 0; i < data->want_obj.nr; i++) {\n+\t\toid = &data->want_obj.objects[i].item->oid;\n+\t\tadd_pending_oid(&rev_info, oid_to_hex(oid), oid, 0);\n+\t}\n+\tif (prepare_revision_walk(&rev_info))\n+\t\treturn 0;\n+\targs.bloom_filter = &data->bloom_filter;\n+\targs.bloom_filter_settings = &data->bloom_filter_settings;\n+\targs.acks = acks;\n+\ttraverse_commit_list(&rev_info, rev_info_bloom_ack, NULL, &args);\n+\treturn 0;\n+}\n+\n static int send_acks(struct upload_pack_data *data, struct oid_array *acks)\n {\n \tint i;\n@@ -1600,6 +1685,7 @@ static int process_haves_and_send_acks(struct upload_pack_data *data)\n \tint ret = 0;\n \n \tprocess_haves(data, &common);\n+\tprocess_bloom(data, &common);\n \tif (data->done) {\n \t\tret = 1;\n \t} else if (send_acks(data, &common)) {\n-- \n2.30.0.4.gbe3229325d\n\n"},{"id":"414253","messageId":"31aec25c-07ef-b3b7-2759-494ad47bcfb1@gmail.com","threadId":"54909","inReplyTo":"X/7guF05a/Bb/VNp@danh.dev","subject":"Re: test-tool: bloom: generate_filter for multiple string?","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-13T12:06:59Z","receivedAt":"2021-01-13T12:07:43Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/13/2021 6:59 AM, Đoàn Trần Công Danh wrote:\n> On 2021-01-12 14:53:32-0500, Taylor Blau <me@ttaylorr.com> wrote:\n>> On Thu, Dec 31, 2020 at 10:54:38AM +0700, Đoàn Trần Công Danh wrote:\n>>> I'm reading the code for Bloom Filter to see if arXiv:2012.00472\n>>> could be an improvement.\n>>\n>> I'm late to the party, but I'm curious to hear which part of this\n>> article you think would help out the Bloom filter implementation.\n> \n> Uhm, no. The article doesn't help the Bloom filter implementation.\n> The article was suggesting using Bloom filter to speed-up the\n> negotiation in fetch-pack and upload-pack. Which, in my own quick\n> experience, doesn't help much. Maybe it's me not understand the\n> article idea or I have made a naive implementation. However, I'm not\n> convinced to pursued further.\n\nI saw that idea, and was immediately skeptical. Bloom filters still\nhave size linear to the size of the set. By using a Bloom filter to\ndescribe \"these are ALL the objects I have\" instead of \"these are\nthe TIPS I have\" the size will explode to be much larger than our\ncurrent negotiation algorithm.\n\nThanks,\n-Stolee\n\n"},{"id":"414254","messageId":"X/7j4w22s3gEbm2R@danh.dev","threadId":"54909","inReplyTo":"31aec25c-07ef-b3b7-2759-494ad47bcfb1@gmail.com","subject":"Re: test-tool: bloom: generate_filter for multiple string?","fromName":"Đoàn Trần Công Danh","fromEmail":"congdanhqx@gmail.com","sentAt":"2021-01-13T12:13:23Z","receivedAt":"2021-01-13T12:14:07Z","isPatch":false,"sender":{"key":"congdanhqx@gmail.com","avatar":"https://avatars.githubusercontent.com/u/42673067?v=4"},"body":"On 2021-01-13 07:06:59-0500, Derrick Stolee <stolee@gmail.com> wrote:\n> On 1/13/2021 6:59 AM, Đoàn Trần Công Danh wrote:\n> > On 2021-01-12 14:53:32-0500, Taylor Blau <me@ttaylorr.com> wrote:\n> >> On Thu, Dec 31, 2020 at 10:54:38AM +0700, Đoàn Trần Công Danh wrote:\n> >>> I'm reading the code for Bloom Filter to see if arXiv:2012.00472\n> >>> could be an improvement.\n> >>\n> >> I'm late to the party, but I'm curious to hear which part of this\n> >> article you think would help out the Bloom filter implementation.\n> > \n> > Uhm, no. The article doesn't help the Bloom filter implementation.\n> > The article was suggesting using Bloom filter to speed-up the\n> > negotiation in fetch-pack and upload-pack. Which, in my own quick\n> > experience, doesn't help much. Maybe it's me not understand the\n> > article idea or I have made a naive implementation. However, I'm not\n> > convinced to pursued further.\n> \n> I saw that idea, and was immediately skeptical. Bloom filters still\n> have size linear to the size of the set. By using a Bloom filter to\n> describe \"these are ALL the objects I have\" instead of \"these are\n> the TIPS I have\" the size will explode to be much larger than our\n> current negotiation algorithm.\n\nYes, I saw that problem, too.\n\nMy implementation was trying to use it from the second round,\ndownstream will say: these are ALL the objects I have from our common\nobjects.\n\nThe result is not much different, though.\n\nThanks,\n\n-- \nDanh\n"},{"id":"414268","messageId":"X/8OLozuyx+rxEHN@nand.local","threadId":"54909","inReplyTo":"X/7guF05a/Bb/VNp@danh.dev","subject":"Re: test-tool: bloom: generate_filter for multiple string?","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-01-13T15:13:50Z","receivedAt":"2021-01-13T15:14:36Z","isPatch":false,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, Jan 13, 2021 at 06:59:52PM +0700, Đoàn Trần Công Danh wrote:\n> On 2021-01-12 14:53:32-0500, Taylor Blau <me@ttaylorr.com> wrote:\n> > On Thu, Dec 31, 2020 at 10:54:38AM +0700, Đoàn Trần Công Danh wrote:\n> > > I'm reading the code for Bloom Filter to see if arXiv:2012.00472\n> > > could be an improvement.\n> >\n> > I'm late to the party, but I'm curious to hear which part of this\n> > article you think would help out the Bloom filter implementation.\n>\n> Uhm, no. The article doesn't help the Bloom filter implementation.\n> The article was suggesting using Bloom filter to speed-up the\n> negotiation in fetch-pack and upload-pack. Which, in my own quick\n> experience, doesn't help much. Maybe it's me not understand the\n> article idea or I have made a naive implementation. However, I'm not\n> convinced to pursued further.\n\nI see. I read your \"reading the code for Bloom Filter to see if ...\ncould be an improvement\" as trying to improve the Bloom implementation.\nWhich after skimming the article, made me quite curious, since I didn't\nunderstand what you were getting at.\n\nBut trying to speed up the negotiation makes sense, and is in line with\nthe goal of the article. It's too bad that you weren't able to produce\nthe same benefits here, but I understand why.\n\n> If you are curious, I'm attaching 2 quick-and-low-quality patches with\n> this email for your consideration.\n\nThanks. They were an interesting read.\n\nThanks,\nTaylor\n"}]}