{"thread":{"id":"50771","subject":"[PATCH 0/3] multi-pack-index: fix verify on large repos","startedAt":"2019-03-18T14:29:59Z","lastAt":"2019-03-25T17:18:24Z","messageCount":26,"participants":["Jeff Hostetler via GitGitGadget","Ævar Arnfjörð Bjarmason","Jeff Hostetler","Junio C Hamano","Eric Sunshine"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"371812","messageId":"pull.166.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":null,"subject":"[PATCH 0/3] multi-pack-index: fix verify on large repos","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-18T14:29:55Z","receivedAt":"2019-03-18T14:29:59Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"Teach \"multi-pack-index verify\" to handle cases where the number of\npackfiles exceeds the open file handle limit.\n\nThe first commit fixes a problem that prevented the LRU-style\nclose_one_pack() mechanism from working which caused midx verify to run out\nof file descriptors.\n\nThe second commit teaches midx verify to sort the set of objects to verify\nby packfile rather than verifying them in OID order. This eliminates the\nneed to have more than one packfile/idx open at the same time.\n\nWith the second commit, runtime on 3600 packfiles went from 12 minutes to 25\nseconds.\n\nThanks, Jeff\n\nJeff Hostetler (3):\n midx: verify: add midx packfiles to the packed_git list\n midx: verify: group objects by packfile to speed up object\n verification\n trace2:data: add trace2 data to midx\n\n builtin/multi-pack-index.c | 3 ++\n midx.c | 60 ++++++++++++++++++++++++++++++++++----\n packfile.c | 2 +-\n packfile.h | 2 ++\n 4 files changed, 61 insertions(+), 6 deletions(-)\n\n\nbase-commit: e902e9bcae2010bc42648c80ab6adc6c5a16a4a5\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-166%2Fjeffhostetler%2Fupstream-midx-verify-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-166/jeffhostetler/upstream-midx-verify-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/166\n-- \ngitgitgadget\n"},{"id":"371813","messageId":"d1a730df94a02f4424fa1b9e543981aea4999d77.1552919394.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.git.gitgitgadget@gmail.com","subject":"[PATCH 1/3] midx: verify: add midx packfiles to the packed_git list","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-18T14:29:57Z","receivedAt":"2019-03-18T14:30:02Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nFix \"git multi-pack-index verify\" to handle repos with thousands\nof packfiles.\n\nMidx verify adds the individual \"packed_git\" structures to the\nmulti_pack_index.packs array, but it does not add them to the\n\"repository.objects.packed_git\" list. During the verification\ncode, each packfile is opened and scanned. And \"pack_open_fds\"\nis incremented. If \"pack_open_fds\" equals the \"pack_max_fds\"\nopen_packed_git_1() calls close_one_pack() to LRU-style close\nan already open packfile. But because the packfiles were never\nadded to the \"packed_git\" list, close_one_pack() does nothing.\nIf there are very many packfiles, Git runs out of file descriptors\nand fails.\n\nNote that this was observed on Windows when build with GCC and\nin a repository with more than (2048-25) packfiles.\n\nSigned-off-by: Jeff Hostetler \n---\n midx.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/midx.c b/midx.c\nindex 8a505fd423..d2c39b6d37 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -971,6 +971,9 @@ int verify_midx_file(const char *object_dir)\n \tfor (i = 0; i < m->num_packs; i++) {\n \t\tif (prepare_midx_pack(m, i))\n \t\t\tmidx_report(\"failed to load pack in position %d\", i);\n+\n+\t\tif (m->packs[i])\n+\t\t\tinstall_packed_git(the_repository, m->packs[i]);\n \t}\n \n \tfor (i = 0; i < 255; i++) {\n-- \ngitgitgadget\n\n"},{"id":"371814","messageId":"2d23bc24b72f8a196b222a89454bd8c9938207fe.1552919394.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.git.gitgitgadget@gmail.com","subject":"[PATCH 3/3] trace2:data: add trace2 data to midx","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-18T14:29:58Z","receivedAt":"2019-03-18T14:30:02Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nLog multi-pack-index command mode.\nLog number of objects and packfiles in the midx.\n\nSigned-off-by: Jeff Hostetler \n---\n builtin/multi-pack-index.c | 3 +++\n midx.c | 4 ++++\n 2 files changed, 7 insertions(+)\n\ndiff --git a/builtin/multi-pack-index.c b/builtin/multi-pack-index.c\nindex fca70f8e4f..ae6e476ad5 100644\n--- a/builtin/multi-pack-index.c\n+++ b/builtin/multi-pack-index.c\n@@ -3,6 +3,7 @@\n #include \"config.h\"\n #include \"parse-options.h\"\n #include \"midx.h\"\n+#include \"trace2.h\"\n \n static char const * const builtin_multi_pack_index_usage[] = {\n \tN_(\"git multi-pack-index [--object-dir=] (write|verify)\"),\n@@ -40,6 +41,8 @@ int cmd_multi_pack_index(int argc, const char **argv,\n \t\treturn 1;\n \t}\n \n+\ttrace2_cmd_mode(argv[0]);\n+\n \tif (!strcmp(argv[0], \"write\"))\n \t\treturn write_midx_file(opts.object_dir);\n \tif (!strcmp(argv[0], \"verify\"))\ndiff --git a/midx.c b/midx.c\nindex 0376757390..df1df20a66 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -8,6 +8,7 @@\n #include \"sha1-lookup.h\"\n #include \"midx.h\"\n #include \"progress.h\"\n+#include \"trace2.h\"\n \n #define MIDX_SIGNATURE 0x4d494458 /* \"MIDX\" */\n #define MIDX_VERSION 1\n@@ -164,6 +165,9 @@ struct multi_pack_index *load_multi_pack_index(const char *object_dir, int local\n \t\t\t m->pack_names[i]);\n \t}\n \n+\ttrace2_data_intmax(\"midx\", the_repository, \"load/num_packs\", m->num_packs);\n+\ttrace2_data_intmax(\"midx\", the_repository, \"load/num_objects\", m->num_objects);\n+\n \treturn m;\n \n cleanup_fail:\n-- \ngitgitgadget\n"},{"id":"371815","messageId":"86f6b0325821a9e1742a28895f9c9b712a1fdec4.1552919394.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.git.gitgitgadget@gmail.com","subject":"[PATCH 2/3] midx: verify: group objects by packfile to speed up object verification","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-18T14:29:57Z","receivedAt":"2019-03-18T14:30:03Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nTeach `multi-pack-index verify` to sort the set of objects by\npackfile so that only one packfile needs to be open at a time.\n\nThis is a performance improvement. Previously, objects were\nverified in OID order. This essentially requires all packfiles\nto be open at the same time. If the number of packfiles exceeds\nthe open file limit, packfiles would be LRU-closed and re-opened\nmany times.\n\nSigned-off-by: Jeff Hostetler \n---\n midx.c | 53 ++++++++++++++++++++++++++++++++++++++++++++++++-----\n packfile.c | 2 +-\n packfile.h | 2 ++\n 3 files changed, 51 insertions(+), 6 deletions(-)\n\ndiff --git a/midx.c b/midx.c\nindex d2c39b6d37..0376757390 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -958,9 +958,29 @@ static void midx_report(const char *fmt, ...)\n \tva_end(ap);\n }\n \n+struct pair_pos_vs_id\n+{\n+\tuint32_t pos;\n+\tuint32_t pack_int_id;\n+};\n+\n+static int compare_pair_pos_vs_id(const void *_a, const void *_b)\n+{\n+\tstruct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;\n+\tstruct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;\n+\n+\tif (a->pack_int_id < b->pack_int_id)\n+\t\treturn -1;\n+\tif (a->pack_int_id > b->pack_int_id)\n+\t\treturn 1;\n+\n+\treturn 0;\n+}\n+\n int verify_midx_file(const char *object_dir)\n {\n-\tuint32_t i;\n+\tstruct pair_pos_vs_id *pairs = NULL;\n+\tuint32_t i, k;\n \tstruct progress *progress;\n \tstruct multi_pack_index *m = load_multi_pack_index(object_dir, 1);\n \tverify_midx_error = 0;\n@@ -997,15 +1017,36 @@ int verify_midx_file(const char *object_dir)\n \t}\n \n \tprogress = start_progress(_(\"Verifying object offsets\"), m->num_objects);\n+\n+\t/*\n+\t * Create an array mapping each object to its packfile id. Sort it\n+\t * to group the objects by packfile. Use this permutation to visit\n+\t * each of the objects and only require 1 packfile to be open at a\n+\t * time.\n+\t */\n+\tALLOC_ARRAY(pairs, m->num_objects);\n \tfor (i = 0; i < m->num_objects; i++) {\n+\t\tpairs[i].pos = i;\n+\t\tpairs[i].pack_int_id = nth_midxed_pack_int_id(m, i);\n+\t}\n+\tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n+\n+\tfor (k = 0; k < m->num_objects; k++) {\n \t\tstruct object_id oid;\n \t\tstruct pack_entry e;\n \t\toff_t m_offset, p_offset;\n \n-\t\tnth_midxed_object_oid(&oid, m, i);\n+\t\tif (k > 0 && pairs[k-1].pack_int_id != pairs[k].pack_int_id &&\n+\t\t m->packs[pairs[k-1].pack_int_id])\n+\t\t{\n+\t\t\tclose_pack_fd(m->packs[pairs[k-1].pack_int_id]);\n+\t\t\tclose_pack_index(m->packs[pairs[k-1].pack_int_id]);\n+\t\t}\n+\n+\t\tnth_midxed_object_oid(&oid, m, pairs[k].pos);\n \t\tif (!fill_midx_entry(&oid, &e, m)) {\n \t\t\tmidx_report(_(\"failed to load pack entry for oid[%d] = %s\"),\n-\t\t\t\t i, oid_to_hex(&oid));\n+\t\t\t\t pairs[k].pos, oid_to_hex(&oid));\n \t\t\tcontinue;\n \t\t}\n \n@@ -1020,11 +1061,13 @@ int verify_midx_file(const char *object_dir)\n \n \t\tif (m_offset != p_offset)\n \t\t\tmidx_report(_(\"incorrect object offset for oid[%d] = %s: %\"PRIx64\" != %\"PRIx64),\n-\t\t\t\t i, oid_to_hex(&oid), m_offset, p_offset);\n+\t\t\t\t pairs[k].pos, oid_to_hex(&oid), m_offset, p_offset);\n \n-\t\tdisplay_progress(progress, i + 1);\n+\t\tdisplay_progress(progress, k + 1);\n \t}\n \tstop_progress(&progress);\n \n+\tfree(pairs);\n+\n \treturn verify_midx_error;\n }\ndiff --git a/packfile.c b/packfile.c\nindex 16bcb75262..d2bcb2f860 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -309,7 +309,7 @@ void close_pack_windows(struct packed_git *p)\n \t}\n }\n \n-static int close_pack_fd(struct packed_git *p)\n+int close_pack_fd(struct packed_git *p)\n {\n \tif (p->pack_fd < 0)\n \t\treturn 0;\ndiff --git a/packfile.h b/packfile.h\nindex d70c6d9afb..b1c18504eb 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -76,6 +76,8 @@ extern int open_pack_index(struct packed_git *);\n */\n extern void close_pack_index(struct packed_git *);\n \n+int close_pack_fd(struct packed_git *p);\n+\n extern uint32_t get_pack_fanout(struct packed_git *p, uint32_t value);\n \n extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t, unsigned long *);\n-- \ngitgitgadget\n\n"},{"id":"371818","messageId":"87pnqodvr9.fsf@evledraar.gmail.com","threadId":"50771","inReplyTo":"86f6b0325821a9e1742a28895f9c9b712a1fdec4.1552919394.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/3] midx: verify: group objects by packfile to speed up object verification","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-03-18T15:53:30Z","receivedAt":"2019-03-18T15:53:36Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Mar 18 2019, Jeff Hostetler via GitGitGadget wrote:\n\n> +static int compare_pair_pos_vs_id(const void *_a, const void *_b)\n> +{\n> +\tstruct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;\n> +\tstruct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;\n> +\n> +\tif (a->pack_int_id < b->pack_int_id)\n> +\t\treturn -1;\n> +\tif (a->pack_int_id > b->pack_int_id)\n> +\t\treturn 1;\n> +\n> +\treturn 0;\n> +}\n\nNot a suggestion for a change, just a note that this sent me down the\nrabbit hole of looking at the different idioms we use for QSORT() in\ndifferent places. Some use this form, some a ternary nest, and some the\nsuccinct subtraction idiom of e.g. (in this case):\n\n return b->pack_int_id - a->pack_int_id;\n\n> +\n> int verify_midx_file(const char *object_dir)\n> {\n> -\tuint32_t i;\n> +\tstruct pair_pos_vs_id *pairs = NULL;\n> +\tuint32_t i, k;\n> \tstruct progress *progress;\n> \tstruct multi_pack_index *m = load_multi_pack_index(object_dir, 1);\n> \tverify_midx_error = 0;\n> @@ -997,15 +1017,36 @@ int verify_midx_file(const char *object_dir)\n> \t}\n>\n> \tprogress = start_progress(_(\"Verifying object offsets\"), m->num_objects);\n> +\n> +\t/*\n> +\t * Create an array mapping each object to its packfile id. Sort it\n> +\t * to group the objects by packfile. Use this permutation to visit\n> +\t * each of the objects and only require 1 packfile to be open at a\n> +\t * time.\n> +\t */\n> +\tALLOC_ARRAY(pairs, m->num_objects);\n> \tfor (i = 0; i < m->num_objects; i++) {\n> +\t\tpairs[i].pos = i;\n> +\t\tpairs[i].pack_int_id = nth_midxed_pack_int_id(m, i);\n> +\t}\n> +\tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n> +\n> +\tfor (k = 0; k < m->num_objects; k++) {\n> [...]\n\nI have not tested this (or midx in general), but isn't this new QSORT()\nintroducing the same sort of progress stalling that I fixed for\ncommit-graph in 890226ccb57 (\"commit-graph write: add itermediate\nprogress\", 2019-01-19)? I.e. something you can work around with a\n\"display_progress(progress, 0)\" before the QSORT().\n"},{"id":"371848","messageId":"9c4da72d-6066-8d05-f181-a93c3926705f@jeffhostetler.com","threadId":"50771","inReplyTo":"87pnqodvr9.fsf@evledraar.gmail.com","subject":"Re: [PATCH 2/3] midx: verify: group objects by packfile to speed up object verification","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2019-03-18T21:39:44Z","receivedAt":"2019-03-18T21:39:47Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 3/18/2019 11:53 AM, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Mon, Mar 18 2019, Jeff Hostetler via GitGitGadget wrote:\n> \n>> +static int compare_pair_pos_vs_id(const void *_a, const void *_b)\n>> +{\n>> +\tstruct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;\n>> +\tstruct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;\n>> +\n>> +\tif (a->pack_int_id < b->pack_int_id)\n>> +\t\treturn -1;\n>> +\tif (a->pack_int_id > b->pack_int_id)\n>> +\t\treturn 1;\n>> +\n>> +\treturn 0;\n>> +}\n> \n> Not a suggestion for a change, just a note that this sent me down the\n> rabbit hole of looking at the different idioms we use for QSORT() in\n> different places. Some use this form, some a ternary nest, and some the\n> succinct subtraction idiom of e.g. (in this case):\n> \n> return b->pack_int_id - a->pack_int_id;\n\nYeah, I'm not sure which way is better or worse here.\nAn earlier draft of this function sorted by packfile id\nand then by OID (thinking we might benefit from some\nlocality later when we do the verify), hence the independent\nif statements. But it didn't help, so I removed the other\nlines.\n\nOn 43+M objects, your version is a hair faster, so I might\nas well take it instead.\n\n> \n>> +\n>> int verify_midx_file(const char *object_dir)\n>> {\n>> -\tuint32_t i;\n>> +\tstruct pair_pos_vs_id *pairs = NULL;\n>> +\tuint32_t i, k;\n>> \tstruct progress *progress;\n>> \tstruct multi_pack_index *m = load_multi_pack_index(object_dir, 1);\n>> \tverify_midx_error = 0;\n>> @@ -997,15 +1017,36 @@ int verify_midx_file(const char *object_dir)\n>> \t}\n>>\n>> \tprogress = start_progress(_(\"Verifying object offsets\"), m->num_objects);\n>> +\n>> +\t/*\n>> +\t * Create an array mapping each object to its packfile id. Sort it\n>> +\t * to group the objects by packfile. Use this permutation to visit\n>> +\t * each of the objects and only require 1 packfile to be open at a\n>> +\t * time.\n>> +\t */\n>> +\tALLOC_ARRAY(pairs, m->num_objects);\n>> \tfor (i = 0; i < m->num_objects; i++) {\n>> +\t\tpairs[i].pos = i;\n>> +\t\tpairs[i].pack_int_id = nth_midxed_pack_int_id(m, i);\n>> +\t}\n>> +\tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n>> +\n>> +\tfor (k = 0; k < m->num_objects; k++) {\n>> [...]\n> \n> I have not tested this (or midx in general), but isn't this new QSORT()\n> introducing the same sort of progress stalling that I fixed for\n> commit-graph in 890226ccb57 (\"commit-graph write: add itermediate\n> progress\", 2019-01-19)? I.e. something you can work around with a\n> \"display_progress(progress, 0)\" before the QSORT().\n> \n\nI wasn't tracking your commit-graph changes, but yes, I think it is.\n\nTinkering with how to display progress, I found a couple of problems.\nOn my 3599 packfile, 43M object example, QSORT() takes about 5 seconds.\nBut there's about 2 seconds of setup before the sort starts. The final\nverify loops takes about 17 seconds.\n\nHere I put trace2 regions around the main loops and used the\nGIT_TR2_PERF stream.\n\n> | cmd_name | | | | | multi-pack-index (multi-pack-index)\n> | cmd_mode | | | | | verify\n> | data | r0 | 0.031295 | 0.031295 | midx | load/num_packs:3599\n> | data | r0 | 0.031330 | 0.031330 | midx | load/num_objects:42704807\n> | region_enter | r0 | 0.031352 | | midx | label:verify/prepare \n> | region_leave | r0 | 0.626547 | 0.595195 | midx | label:verify/prepare \n> | region_enter | r0 | 0.626602 | | midx | label:verify/oid_order \n> | region_leave | r0 | 1.570195 | 0.943593 | midx | label:verify/oid_order \n> | region_enter | r0 | 1.570253 | | midx | label:verify/sort_setup \n> | region_leave | r0 | 1.809723 | 0.239470 | midx | label:verify/sort_setup \n> | region_enter | r0 | 1.809803 | | midx | label:verify/sort \n> | region_leave | r0 | 6.950595 | 5.140792 | midx | label:verify/sort \n> | region_enter | r0 | 6.950651 | | midx | label:verify/offsets \n> | region_leave | r0 | 24.059736 | 17.109085 | midx | label:verify/offsets \n> | exit | | 24.101434 | | | code:0\n\nSo just adding a delay progress block by itself around the sort doesn't\nhelp much. It just sits there for 7 seconds before the actual progress\nstarts.\n\nIf I add a non-delay progress block around the \"verify/prepare\",\n\"verify/oid_order\" and the \"verify/offsets\" loops, we get a pretty good\nexperience.\n\nThere is the dead time while the sort() itself is running, but at least\nthere is isn't a 5+ second frozen at 0% message on screen.\n\nI'll re-roll shortly.\n\nThanks,\nJeff\n"},{"id":"371853","messageId":"87lg1bet9d.fsf@evledraar.gmail.com","threadId":"50771","inReplyTo":"9c4da72d-6066-8d05-f181-a93c3926705f@jeffhostetler.com","subject":"Re: [PATCH 2/3] midx: verify: group objects by packfile to speed up object verification","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-03-18T22:02:06Z","receivedAt":"2019-03-18T22:02:12Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Mar 18 2019, Jeff Hostetler wrote:\n\n> On 3/18/2019 11:53 AM, Ævar Arnfjörð Bjarmason wrote:\n>>\n>> On Mon, Mar 18 2019, Jeff Hostetler via GitGitGadget wrote:\n>>\n>>> +static int compare_pair_pos_vs_id(const void *_a, const void *_b)\n>>> +{\n>>> +\tstruct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;\n>>> +\tstruct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;\n>>> +\n>>> +\tif (a->pack_int_id < b->pack_int_id)\n>>> +\t\treturn -1;\n>>> +\tif (a->pack_int_id > b->pack_int_id)\n>>> +\t\treturn 1;\n>>> +\n>>> +\treturn 0;\n>>> +}\n>>\n>> Not a suggestion for a change, just a note that this sent me down the\n>> rabbit hole of looking at the different idioms we use for QSORT() in\n>> different places. Some use this form, some a ternary nest, and some the\n>> succinct subtraction idiom of e.g. (in this case):\n>>\n>> return b->pack_int_id - a->pack_int_id;\n>\n> Yeah, I'm not sure which way is better or worse here.\n> An earlier draft of this function sorted by packfile id\n> and then by OID (thinking we might benefit from some\n> locality later when we do the verify), hence the independent\n> if statements. But it didn't help, so I removed the other\n> lines.\n>\n> On 43+M objects, your version is a hair faster, so I might\n> as well take it instead.\n\nCool!\n\n>>\n>>> +\n>>> int verify_midx_file(const char *object_dir)\n>>> {\n>>> -\tuint32_t i;\n>>> +\tstruct pair_pos_vs_id *pairs = NULL;\n>>> +\tuint32_t i, k;\n>>> \tstruct progress *progress;\n>>> \tstruct multi_pack_index *m = load_multi_pack_index(object_dir, 1);\n>>> \tverify_midx_error = 0;\n>>> @@ -997,15 +1017,36 @@ int verify_midx_file(const char *object_dir)\n>>> \t}\n>>>\n>>> \tprogress = start_progress(_(\"Verifying object offsets\"), m->num_objects);\n>>> +\n>>> +\t/*\n>>> +\t * Create an array mapping each object to its packfile id. Sort it\n>>> +\t * to group the objects by packfile. Use this permutation to visit\n>>> +\t * each of the objects and only require 1 packfile to be open at a\n>>> +\t * time.\n>>> +\t */\n>>> +\tALLOC_ARRAY(pairs, m->num_objects);\n>>> \tfor (i = 0; i < m->num_objects; i++) {\n>>> +\t\tpairs[i].pos = i;\n>>> +\t\tpairs[i].pack_int_id = nth_midxed_pack_int_id(m, i);\n>>> +\t}\n>>> +\tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n>>> +\n>>> +\tfor (k = 0; k < m->num_objects; k++) {\n>>> [...]\n>>\n>> I have not tested this (or midx in general), but isn't this new QSORT()\n>> introducing the same sort of progress stalling that I fixed for\n>> commit-graph in 890226ccb57 (\"commit-graph write: add itermediate\n>> progress\", 2019-01-19)? I.e. something you can work around with a\n>> \"display_progress(progress, 0)\" before the QSORT().\n>>\n>\n> I wasn't tracking your commit-graph changes, but yes, I think it is.\n>\n> Tinkering with how to display progress, I found a couple of problems.\n> On my 3599 packfile, 43M object example, QSORT() takes about 5 seconds.\n> But there's about 2 seconds of setup before the sort starts. The final\n> verify loops takes about 17 seconds.\n>\n> Here I put trace2 regions around the main loops and used the\n> GIT_TR2_PERF stream.\n>\n>> | cmd_name | | | | | multi-pack-index (multi-pack-index)\n>> | cmd_mode | | | | | verify\n>> | data | r0 | 0.031295 | 0.031295 | midx | load/num_packs:3599\n>> | data | r0 | 0.031330 | 0.031330 | midx | load/num_objects:42704807\n>> | region_enter | r0 | 0.031352 | | midx |\n>> label:verify/prepare | region_leave | r0 | 0.626547 | 0.595195 |\n>> midx | label:verify/prepare | region_enter | r0 | 0.626602 |\n>> | midx | label:verify/oid_order | region_leave | r0 |\n>> 1.570195 | 0.943593 | midx | label:verify/oid_order |\n>> region_enter | r0 | 1.570253 | | midx |\n>> label:verify/sort_setup | region_leave | r0 | 1.809723 | 0.239470\n>> | midx | label:verify/sort_setup | region_enter | r0 |\n>> 1.809803 | | midx | label:verify/sort | region_leave\n>> | r0 | 6.950595 | 5.140792 | midx | label:verify/sort |\n>> region_enter | r0 | 6.950651 | | midx |\n>> label:verify/offsets | region_leave | r0 | 24.059736 | 17.109085 |\n>> midx | label:verify/offsets | exit | | 24.101434 |\n>> | | code:0\n>\n> So just adding a delay progress block by itself around the sort doesn't\n> help much. It just sits there for 7 seconds before the actual progress\n> starts.\n>\n> If I add a non-delay progress block around the \"verify/prepare\",\n> \"verify/oid_order\" and the \"verify/offsets\" loops, we get a pretty good\n> experience.\n>\n> There is the dead time while the sort() itself is running, but at least\n> there is isn't a 5+ second frozen at 0% message on screen.\n\nYeah, the same with the commit-graph with my hack. I.e. it'll sit there,\nbut at least it sits like this:\n\n What I was doing before 100% (X/Y)\n What I'm about to start doing 0% (0/Z) [hanging]\n\nInstead of:\n\n What I was doing before 100% (X/Y)\n [hanging]\n\nSo that's an improvement, i.e. you know it's started that next phase at\nleast instead of just having a non-descriptive hang.\n\nIdeally there would be some way to reach into the QSORT() and display\nprogress there, but that's all sorts of nasty, so as the TODO comment in\ncommit-graph.c notes I punted it.\n"},{"id":"371876","messageId":"xmqqmulry08d.fsf@gitster-ct.c.googlers.com","threadId":"50771","inReplyTo":"87lg1bet9d.fsf@evledraar.gmail.com","subject":"Re: [PATCH 2/3] midx: verify: group objects by packfile to speed up object verification","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-03-19T04:08:50Z","receivedAt":"2019-03-19T04:08:55Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason writes:\n\n>>>> +\tif (a->pack_int_id < b->pack_int_id)\n>>>> +\t\treturn -1;\n>>>> +\tif (a->pack_int_id > b->pack_int_id)\n>>>> +\t\treturn 1;\n>>>> +\n>>>> +\treturn 0;\n>>>> +}\n>>> ...\n>>> succinct subtraction idiom of e.g. (in this case):\n>>>\n>>> return b->pack_int_id - a->pack_int_id;\n>> ...\n>> On 43+M objects, your version is a hair faster, so I might\n>> as well take it instead.\n>\n> Cool!\n\nYup, following a well-known short idiom lets readers' eyes coast\nover without forcing them to make sure the two if statements have\ncomparison going in the right direction and return the constant with\nthe right sign, etc. Even if the idiomatic version weren't faster,\nit is worth using it.\n\nThanks.\n"},{"id":"371903","messageId":"d3f119b1-22f6-e34a-a68f-883aca3d8013@jeffhostetler.com","threadId":"50771","inReplyTo":"87lg1bet9d.fsf@evledraar.gmail.com","subject":"Re: [PATCH 2/3] midx: verify: group objects by packfile to speed up object verification","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2019-03-19T14:00:32Z","receivedAt":"2019-03-19T14:00:37Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 3/18/2019 6:02 PM, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Mon, Mar 18 2019, Jeff Hostetler wrote:\n> \n>> On 3/18/2019 11:53 AM, Ævar Arnfjörð Bjarmason wrote:\n>>>\n>>> On Mon, Mar 18 2019, Jeff Hostetler via GitGitGadget wrote:\n>>>\n[...]\n>>>> +\tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n>>>> +\n>>>> +\tfor (k = 0; k < m->num_objects; k++) {\n>>>> [...]\n>>>\n>>> I have not tested this (or midx in general), but isn't this new QSORT()\n>>> introducing the same sort of progress stalling that I fixed for\n>>> commit-graph in 890226ccb57 (\"commit-graph write: add itermediate\n>>> progress\", 2019-01-19)? I.e. something you can work around with a\n>>> \"display_progress(progress, 0)\" before the QSORT().\n>>>\n>>\n>> I wasn't tracking your commit-graph changes, but yes, I think it is.\n>>\n[...]\n>>\n>> There is the dead time while the sort() itself is running, but at least\n>> there is isn't a 5+ second frozen at 0% message on screen.\n> \n> Yeah, the same with the commit-graph with my hack. I.e. it'll sit there,\n> but at least it sits like this:\n> \n> What I was doing before 100% (X/Y)\n> What I'm about to start doing 0% (0/Z) [hanging]\n> \n> Instead of:\n> \n> What I was doing before 100% (X/Y)\n> [hanging]\n> \n> So that's an improvement, i.e. you know it's started that next phase at\n> least instead of just having a non-descriptive hang.\n> \n> Ideally there would be some way to reach into the QSORT() and display\n> progress there, but that's all sorts of nasty, so as the TODO comment in\n> commit-graph.c notes I punted it.\n\nPerhaps I'm confused or this is a Windows issue, but when I do:\n\n\tprogress = start_delayed_progress(\"sorting\", n);\n\tdisplay_progress(progress, 0);\n\tQSORT(...);\n\tstop_progress(&progress);\n\nI never see the 0% message. It always does the hang with the cursor in\ncolumn 0 on a blank line. If I make this a regular start_progress(),\nI do see the 0% message for the duration of the qsort hang.\n\nI did some similar testing around your QSORT() in commit-graph.c\nand got the same result. It looks like start_delayed_processing()\nwants to wait at least 2 seconds before displaying anything and has\nan interval timer to notify it that another message should be printed,\nbut the display_progress(0) prior to the QSORT() arrives before the 2\nseconds are up and so nothing is printed. It's not until we get into\nthe loop below the QSORT that one of the display_progress(i+1) calls\ncould cause a message to appear.\n\nRight?\nJeff\n\n\n\n\n\n\n"},{"id":"371905","messageId":"877ecvdklm.fsf@evledraar.gmail.com","threadId":"50771","inReplyTo":"d3f119b1-22f6-e34a-a68f-883aca3d8013@jeffhostetler.com","subject":"Re: [PATCH 2/3] midx: verify: group objects by packfile to speed up object verification","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2019-03-19T14:06:45Z","receivedAt":"2019-03-19T14:06:52Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Tue, Mar 19 2019, Jeff Hostetler wrote:\n\n> On 3/18/2019 6:02 PM, Ævar Arnfjörð Bjarmason wrote:\n>>\n>> On Mon, Mar 18 2019, Jeff Hostetler wrote:\n>>\n>>> On 3/18/2019 11:53 AM, Ævar Arnfjörð Bjarmason wrote:\n>>>>\n>>>> On Mon, Mar 18 2019, Jeff Hostetler via GitGitGadget wrote:\n>>>>\n> [...]\n>>>>> +\tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n>>>>> +\n>>>>> +\tfor (k = 0; k < m->num_objects; k++) {\n>>>>> [...]\n>>>>\n>>>> I have not tested this (or midx in general), but isn't this new QSORT()\n>>>> introducing the same sort of progress stalling that I fixed for\n>>>> commit-graph in 890226ccb57 (\"commit-graph write: add itermediate\n>>>> progress\", 2019-01-19)? I.e. something you can work around with a\n>>>> \"display_progress(progress, 0)\" before the QSORT().\n>>>>\n>>>\n>>> I wasn't tracking your commit-graph changes, but yes, I think it is.\n>>>\n> [...]\n>>>\n>>> There is the dead time while the sort() itself is running, but at least\n>>> there is isn't a 5+ second frozen at 0% message on screen.\n>>\n>> Yeah, the same with the commit-graph with my hack. I.e. it'll sit there,\n>> but at least it sits like this:\n>>\n>> What I was doing before 100% (X/Y)\n>> What I'm about to start doing 0% (0/Z) [hanging]\n>>\n>> Instead of:\n>>\n>> What I was doing before 100% (X/Y)\n>> [hanging]\n>>\n>> So that's an improvement, i.e. you know it's started that next phase at\n>> least instead of just having a non-descriptive hang.\n>>\n>> Ideally there would be some way to reach into the QSORT() and display\n>> progress there, but that's all sorts of nasty, so as the TODO comment in\n>> commit-graph.c notes I punted it.\n>\n> Perhaps I'm confused or this is a Windows issue, but when I do:\n>\n> \tprogress = start_delayed_progress(\"sorting\", n);\n> \tdisplay_progress(progress, 0);\n> \tQSORT(...);\n> \tstop_progress(&progress);\n>\n> I never see the 0% message. It always does the hang with the cursor in\n> column 0 on a blank line. If I make this a regular start_progress(),\n> I do see the 0% message for the duration of the qsort hang.\n>\n> I did some similar testing around your QSORT() in commit-graph.c\n> and got the same result. It looks like start_delayed_processing()\n> wants to wait at least 2 seconds before displaying anything and has\n> an interval timer to notify it that another message should be printed,\n> but the display_progress(0) prior to the QSORT() arrives before the 2\n> seconds are up and so nothing is printed. It's not until we get into\n> the loop below the QSORT that one of the display_progress(i+1) calls\n> could cause a message to appear.\n\nCorrect, it'll still hang the N seconds that start_delayed_progress()\nimposes.\n\nIn the commit-graph code this would sometimes take longer than that, so\nI'd see the 0% earlier.\n\nBut maybe in this case even on humongous repositories it's faster than\nthat.\n"},{"id":"371906","messageId":"pull.166.v2.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.git.gitgitgadget@gmail.com","subject":"[PATCH v2 0/4] multi-pack-index: fix verify on large repos","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-19T14:37:48Z","receivedAt":"2019-03-19T14:37:53Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"Version 2 addresses progress-related concerns raised in the previous version\nof the midx verify code.\n\nThis version also extends the existing progress.[ch] code and adds a\n\"sparse\" mode that automatically ensures the 100% message is issued.\n\n\n----------------------------------------------------------------------------\n\nTeach \"multi-pack-index verify\" to handle cases where the number of\npackfiles exceeds the open file handle limit.\n\nThe first commit fixes a problem that prevented the LRU-style\nclose_one_pack() mechanism from working which caused midx verify to run out\nof file descriptors.\n\nThe second commit teaches midx verify to sort the set of objects to verify\nby packfile rather than verifying them in OID order. This eliminates the\nneed to have more than one packfile/idx open at the same time.\n\nWith the second commit, runtime on 3600 packfiles went from 12 minutes to 25\nseconds.\n\nThanks, Jeff\n\nCc: dstolee@microsoft.com\n\nJeff Hostetler (4):\n progress: add sparse mode to force 100% complete message\n trace2:data: add trace2 data to midx\n midx: verify: add midx packfiles to the packed_git list\n midx: verify: group objects by packfile to speed up object\n verification\n\n builtin/multi-pack-index.c | 3 ++\n midx.c | 84 +++++++++++++++++++++++++++++++++++---\n packfile.c | 2 +-\n packfile.h | 2 +\n progress.c | 40 ++++++++++++++++--\n progress.h | 3 ++\n 6 files changed, 124 insertions(+), 10 deletions(-)\n\n\nbase-commit: e902e9bcae2010bc42648c80ab6adc6c5a16a4a5\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-166%2Fjeffhostetler%2Fupstream-midx-verify-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-166/jeffhostetler/upstream-midx-verify-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/166\n\nRange-diff vs v1:\n\n -: ---------- > 1: e1da1f84a8 progress: add sparse mode to force 100% complete message\n 3: 2d23bc24b7 = 2: 11c88845e7 trace2:data: add trace2 data to midx\n 1: d1a730df94 = 3: ced7f1cb34 midx: verify: add midx packfiles to the packed_git list\n 2: 86f6b03258 ! 4: e2dd99911f midx: verify: group objects by packfile to speed up object verification\n @@ -31,13 +31,20 @@\n +\tstruct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;\n +\tstruct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;\n +\n -+\tif (a->pack_int_id < b->pack_int_id)\n -+\t\treturn -1;\n -+\tif (a->pack_int_id > b->pack_int_id)\n -+\t\treturn 1;\n -+\n -+\treturn 0;\n ++\treturn b->pack_int_id - a->pack_int_id;\n +}\n ++\n ++/*\n ++ * Limit calls to display_progress() for performance reasons.\n ++ * The interval here was arbitrarily chosen.\n ++ */\n ++#define SPARSE_PROGRESS_INTERVAL (1 << 12)\n ++#define midx_display_sparse_progress(progress, n) \\\n ++\tdo { \\\n ++\t\tuint64_t _n = (n); \\\n ++\t\tif ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0)\t\\\n ++\t\t\tdisplay_progress(progress, _n); \\\n ++\t} while (0)\n +\n int verify_midx_file(const char *object_dir)\n {\n @@ -48,10 +55,43 @@\n \tstruct multi_pack_index *m = load_multi_pack_index(object_dir, 1);\n \tverify_midx_error = 0;\n @@\n + \tif (!m)\n + \t\treturn 0;\n + \n ++\tprogress = start_progress(_(\"Looking for referenced packfiles\"),\n ++\t\t\t\t m->num_packs);\n + \tfor (i = 0; i < m->num_packs; i++) {\n + \t\tif (prepare_midx_pack(m, i))\n + \t\t\tmidx_report(\"failed to load pack in position %d\", i);\n + \n + \t\tif (m->packs[i])\n + \t\t\tinstall_packed_git(the_repository, m->packs[i]);\n ++\n ++\t\tdisplay_progress(progress, i + 1);\n + \t}\n ++\tstop_progress(&progress);\n + \n + \tfor (i = 0; i < 255; i++) {\n + \t\tuint32_t oid_fanout1 = ntohl(m->chunk_oid_fanout[i]);\n +@@\n + \t\t\t\t i, oid_fanout1, oid_fanout2, i + 1);\n \t}\n \n - \tprogress = start_progress(_(\"Verifying object offsets\"), m->num_objects);\n ++\tprogress = start_sparse_progress(_(\"Verifying OID order in MIDX\"),\n ++\t\t\t\t\t m->num_objects - 1);\n + \tfor (i = 0; i < m->num_objects - 1; i++) {\n + \t\tstruct object_id oid1, oid2;\n + \n +@@\n + \t\tif (oidcmp(&oid1, &oid2) >= 0)\n + \t\t\tmidx_report(_(\"oid lookup out of order: oid[%d] = %s >= %s = oid[%d]\"),\n + \t\t\t\t i, oid_to_hex(&oid1), oid_to_hex(&oid2), i + 1);\n +\n ++\t\tmidx_display_sparse_progress(progress, i + 1);\n + \t}\n ++\tstop_progress(&progress);\n + \n +-\tprogress = start_progress(_(\"Verifying object offsets\"), m->num_objects);\n +\t/*\n +\t * Create an array mapping each object to its packfile id. Sort it\n +\t * to group the objects by packfile. Use this permutation to visit\n @@ -63,8 +103,15 @@\n +\t\tpairs[i].pos = i;\n +\t\tpairs[i].pack_int_id = nth_midxed_pack_int_id(m, i);\n +\t}\n ++\n ++\tprogress = start_sparse_progress(\n ++\t\t_(\"Sorting objects by packfile\"), m->num_objects);\n ++\tdisplay_progress(progress, 0); /* TODO: Measure QSORT() progress */\n +\tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n ++\tstop_progress(&progress);\n +\n ++\tprogress = start_sparse_progress(_(\"Verifying object offsets\"),\n ++\t\t\t\t\t m->num_objects);\n +\tfor (k = 0; k < m->num_objects; k++) {\n \t\tstruct object_id oid;\n \t\tstruct pack_entry e;\n @@ -94,7 +141,7 @@\n +\t\t\t\t pairs[k].pos, oid_to_hex(&oid), m_offset, p_offset);\n \n -\t\tdisplay_progress(progress, i + 1);\n -+\t\tdisplay_progress(progress, k + 1);\n ++\t\tmidx_display_sparse_progress(progress, k + 1);\n \t}\n \tstop_progress(&progress);\n \n\n-- \ngitgitgadget\n"},{"id":"371907","messageId":"e1da1f84a85165703e3b6be4a240bd36d62b4b01.1553006268.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.v2.git.gitgitgadget@gmail.com","subject":"[PATCH v2 1/4] progress: add sparse mode to force 100% complete message","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-19T14:37:49Z","receivedAt":"2019-03-19T14:37:54Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nAdd new start_sparse_progress() and start_delayed_sparse_progress()\nconstructors and \"sparse\" flag to struct progress.\n\nTeach stop_progress() to force a 100% complete progress message before\nprinting the final \"done\" message when \"sparse\" is set.\n\nCalling display_progress() for every item in a large set can\nbe expensive. If callers try to filter this for performance\nreasons, such as emitting every k-th item, progress would\nnot reach 100% unless they made a final call to display_progress()\nwith the item count before calling stop_progress().\n\nNow this is automatic when \"sparse\" is set.\n\nSigned-off-by: Jeff Hostetler \n---\n progress.c | 40 +++++++++++++++++++++++++++++++++++++---\n progress.h | 3 +++\n 2 files changed, 40 insertions(+), 3 deletions(-)\n\ndiff --git a/progress.c b/progress.c\nindex 5a99c9fbf0..3d75376c96 100644\n--- a/progress.c\n+++ b/progress.c\n@@ -34,6 +34,7 @@ struct progress {\n \tuint64_t total;\n \tunsigned last_percent;\n \tunsigned delay;\n+\tunsigned sparse;\n \tstruct throughput *throughput;\n \tuint64_t start_ns;\n };\n@@ -194,7 +195,7 @@ int display_progress(struct progress *progress, uint64_t n)\n }\n \n static struct progress *start_progress_delay(const char *title, uint64_t total,\n-\t\t\t\t\t unsigned delay)\n+\t\t\t\t\t unsigned delay, unsigned sparse)\n {\n \tstruct progress *progress = malloc(sizeof(*progress));\n \tif (!progress) {\n@@ -208,6 +209,7 @@ static struct progress *start_progress_delay(const char *title, uint64_t total,\n \tprogress->last_value = -1;\n \tprogress->last_percent = -1;\n \tprogress->delay = delay;\n+\tprogress->sparse = sparse;\n \tprogress->throughput = NULL;\n \tprogress->start_ns = getnanotime();\n \tset_progress_signal();\n@@ -216,16 +218,48 @@ static struct progress *start_progress_delay(const char *title, uint64_t total,\n \n struct progress *start_delayed_progress(const char *title, uint64_t total)\n {\n-\treturn start_progress_delay(title, total, 2);\n+\treturn start_progress_delay(title, total, 2, 0);\n }\n \n struct progress *start_progress(const char *title, uint64_t total)\n {\n-\treturn start_progress_delay(title, total, 0);\n+\treturn start_progress_delay(title, total, 0, 0);\n+}\n+\n+/*\n+ * Here \"sparse\" means that the caller might use some sampling criteria to\n+ * decide when to call display_progress() rather than calling it for every\n+ * integer value in[0 .. total). In particular, the caller might not call\n+ * display_progress() for the last value in the range.\n+ *\n+ * When \"sparse\" is set, stop_progress() will automatically force the done\n+ * message to show 100%.\n+ */\n+struct progress *start_sparse_progress(const char *title, uint64_t total)\n+{\n+\treturn start_progress_delay(title, total, 0, 1);\n+}\n+\n+struct progress *start_delayed_sparse_progress(const char *title,\n+\t\t\t\t\t uint64_t total)\n+{\n+\treturn start_progress_delay(title, total, 2, 1);\n+}\n+\n+static void finish_if_sparse(struct progress **p_progress)\n+{\n+\tstruct progress *progress = *p_progress;\n+\n+\tif (progress &&\n+\t progress->sparse &&\n+\t progress->last_value != progress->total)\n+\t\tdisplay_progress(progress, progress->total);\n }\n \n void stop_progress(struct progress **p_progress)\n {\n+\tfinish_if_sparse(p_progress);\n+\n \tstop_progress_msg(p_progress, _(\"done\"));\n }\n \ndiff --git a/progress.h b/progress.h\nindex 70a4d4a0d6..7b725acc8d 100644\n--- a/progress.h\n+++ b/progress.h\n@@ -6,7 +6,10 @@ struct progress;\n void display_throughput(struct progress *progress, uint64_t total);\n int display_progress(struct progress *progress, uint64_t n);\n struct progress *start_progress(const char *title, uint64_t total);\n+struct progress *start_sparse_progress(const char *title, uint64_t total);\n struct progress *start_delayed_progress(const char *title, uint64_t total);\n+struct progress *start_delayed_sparse_progress(const char *title,\n+\t\t\t\t\t uint64_t total);\n void stop_progress(struct progress **progress);\n void stop_progress_msg(struct progress **progress, const char *msg);\n \n-- \ngitgitgadget\n\n"},{"id":"371908","messageId":"ced7f1cb3486885aef018d91fae37958282a351e.1553006268.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.v2.git.gitgitgadget@gmail.com","subject":"[PATCH v2 3/4] midx: verify: add midx packfiles to the packed_git list","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-19T14:37:51Z","receivedAt":"2019-03-19T14:37:55Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nFix \"git multi-pack-index verify\" to handle repos with thousands\nof packfiles.\n\nMidx verify adds the individual \"packed_git\" structures to the\nmulti_pack_index.packs array, but it does not add them to the\n\"repository.objects.packed_git\" list. During the verification\ncode, each packfile is opened and scanned. And \"pack_open_fds\"\nis incremented. If \"pack_open_fds\" equals the \"pack_max_fds\"\nopen_packed_git_1() calls close_one_pack() to LRU-style close\nan already open packfile. But because the packfiles were never\nadded to the \"packed_git\" list, close_one_pack() does nothing.\nIf there are very many packfiles, Git runs out of file descriptors\nand fails.\n\nNote that this was observed on Windows when build with GCC and\nin a repository with more than (2048-25) packfiles.\n\nSigned-off-by: Jeff Hostetler \n---\n midx.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/midx.c b/midx.c\nindex 24141a7c62..b2f33bcd90 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -975,6 +975,9 @@ int verify_midx_file(const char *object_dir)\n \tfor (i = 0; i < m->num_packs; i++) {\n \t\tif (prepare_midx_pack(m, i))\n \t\t\tmidx_report(\"failed to load pack in position %d\", i);\n+\n+\t\tif (m->packs[i])\n+\t\t\tinstall_packed_git(the_repository, m->packs[i]);\n \t}\n \n \tfor (i = 0; i < 255; i++) {\n-- \ngitgitgadget\n\n"},{"id":"371909","messageId":"11c88845e7c68990415e3f5d42227ce83a9f8d67.1553006268.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.v2.git.gitgitgadget@gmail.com","subject":"[PATCH v2 2/4] trace2:data: add trace2 data to midx","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-19T14:37:50Z","receivedAt":"2019-03-19T14:37:56Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nLog multi-pack-index command mode.\nLog number of objects and packfiles in the midx.\n\nSigned-off-by: Jeff Hostetler \n---\n builtin/multi-pack-index.c | 3 +++\n midx.c | 4 ++++\n 2 files changed, 7 insertions(+)\n\ndiff --git a/builtin/multi-pack-index.c b/builtin/multi-pack-index.c\nindex fca70f8e4f..ae6e476ad5 100644\n--- a/builtin/multi-pack-index.c\n+++ b/builtin/multi-pack-index.c\n@@ -3,6 +3,7 @@\n #include \"config.h\"\n #include \"parse-options.h\"\n #include \"midx.h\"\n+#include \"trace2.h\"\n \n static char const * const builtin_multi_pack_index_usage[] = {\n \tN_(\"git multi-pack-index [--object-dir=] (write|verify)\"),\n@@ -40,6 +41,8 @@ int cmd_multi_pack_index(int argc, const char **argv,\n \t\treturn 1;\n \t}\n \n+\ttrace2_cmd_mode(argv[0]);\n+\n \tif (!strcmp(argv[0], \"write\"))\n \t\treturn write_midx_file(opts.object_dir);\n \tif (!strcmp(argv[0], \"verify\"))\ndiff --git a/midx.c b/midx.c\nindex 8a505fd423..24141a7c62 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -8,6 +8,7 @@\n #include \"sha1-lookup.h\"\n #include \"midx.h\"\n #include \"progress.h\"\n+#include \"trace2.h\"\n \n #define MIDX_SIGNATURE 0x4d494458 /* \"MIDX\" */\n #define MIDX_VERSION 1\n@@ -164,6 +165,9 @@ struct multi_pack_index *load_multi_pack_index(const char *object_dir, int local\n \t\t\t m->pack_names[i]);\n \t}\n \n+\ttrace2_data_intmax(\"midx\", the_repository, \"load/num_packs\", m->num_packs);\n+\ttrace2_data_intmax(\"midx\", the_repository, \"load/num_objects\", m->num_objects);\n+\n \treturn m;\n \n cleanup_fail:\n-- \ngitgitgadget\n\n"},{"id":"371910","messageId":"e2dd99911f6054cc7a60d9d3a7187b487f594a65.1553006268.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.v2.git.gitgitgadget@gmail.com","subject":"[PATCH v2 4/4] midx: verify: group objects by packfile to speed up object verification","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-19T14:37:52Z","receivedAt":"2019-03-19T14:37:57Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nTeach `multi-pack-index verify` to sort the set of objects by\npackfile so that only one packfile needs to be open at a time.\n\nThis is a performance improvement. Previously, objects were\nverified in OID order. This essentially requires all packfiles\nto be open at the same time. If the number of packfiles exceeds\nthe open file limit, packfiles would be LRU-closed and re-opened\nmany times.\n\nSigned-off-by: Jeff Hostetler \n---\n midx.c | 77 +++++++++++++++++++++++++++++++++++++++++++++++++-----\n packfile.c | 2 +-\n packfile.h | 2 ++\n 3 files changed, 74 insertions(+), 7 deletions(-)\n\ndiff --git a/midx.c b/midx.c\nindex b2f33bcd90..a37c09f2a5 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -962,9 +962,36 @@ static void midx_report(const char *fmt, ...)\n \tva_end(ap);\n }\n \n+struct pair_pos_vs_id\n+{\n+\tuint32_t pos;\n+\tuint32_t pack_int_id;\n+};\n+\n+static int compare_pair_pos_vs_id(const void *_a, const void *_b)\n+{\n+\tstruct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;\n+\tstruct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;\n+\n+\treturn b->pack_int_id - a->pack_int_id;\n+}\n+\n+/*\n+ * Limit calls to display_progress() for performance reasons.\n+ * The interval here was arbitrarily chosen.\n+ */\n+#define SPARSE_PROGRESS_INTERVAL (1 << 12)\n+#define midx_display_sparse_progress(progress, n) \\\n+\tdo { \\\n+\t\tuint64_t _n = (n); \\\n+\t\tif ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0)\t\\\n+\t\t\tdisplay_progress(progress, _n); \\\n+\t} while (0)\n+\n int verify_midx_file(const char *object_dir)\n {\n-\tuint32_t i;\n+\tstruct pair_pos_vs_id *pairs = NULL;\n+\tuint32_t i, k;\n \tstruct progress *progress;\n \tstruct multi_pack_index *m = load_multi_pack_index(object_dir, 1);\n \tverify_midx_error = 0;\n@@ -972,13 +999,18 @@ int verify_midx_file(const char *object_dir)\n \tif (!m)\n \t\treturn 0;\n \n+\tprogress = start_progress(_(\"Looking for referenced packfiles\"),\n+\t\t\t\t m->num_packs);\n \tfor (i = 0; i < m->num_packs; i++) {\n \t\tif (prepare_midx_pack(m, i))\n \t\t\tmidx_report(\"failed to load pack in position %d\", i);\n \n \t\tif (m->packs[i])\n \t\t\tinstall_packed_git(the_repository, m->packs[i]);\n+\n+\t\tdisplay_progress(progress, i + 1);\n \t}\n+\tstop_progress(&progress);\n \n \tfor (i = 0; i < 255; i++) {\n \t\tuint32_t oid_fanout1 = ntohl(m->chunk_oid_fanout[i]);\n@@ -989,6 +1021,8 @@ int verify_midx_file(const char *object_dir)\n \t\t\t\t i, oid_fanout1, oid_fanout2, i + 1);\n \t}\n \n+\tprogress = start_sparse_progress(_(\"Verifying OID order in MIDX\"),\n+\t\t\t\t\t m->num_objects - 1);\n \tfor (i = 0; i < m->num_objects - 1; i++) {\n \t\tstruct object_id oid1, oid2;\n \n@@ -998,18 +1032,47 @@ int verify_midx_file(const char *object_dir)\n \t\tif (oidcmp(&oid1, &oid2) >= 0)\n \t\t\tmidx_report(_(\"oid lookup out of order: oid[%d] = %s >= %s = oid[%d]\"),\n \t\t\t\t i, oid_to_hex(&oid1), oid_to_hex(&oid2), i + 1);\n+\n+\t\tmidx_display_sparse_progress(progress, i + 1);\n \t}\n+\tstop_progress(&progress);\n \n-\tprogress = start_progress(_(\"Verifying object offsets\"), m->num_objects);\n+\t/*\n+\t * Create an array mapping each object to its packfile id. Sort it\n+\t * to group the objects by packfile. Use this permutation to visit\n+\t * each of the objects and only require 1 packfile to be open at a\n+\t * time.\n+\t */\n+\tALLOC_ARRAY(pairs, m->num_objects);\n \tfor (i = 0; i < m->num_objects; i++) {\n+\t\tpairs[i].pos = i;\n+\t\tpairs[i].pack_int_id = nth_midxed_pack_int_id(m, i);\n+\t}\n+\n+\tprogress = start_sparse_progress(\n+\t\t_(\"Sorting objects by packfile\"), m->num_objects);\n+\tdisplay_progress(progress, 0); /* TODO: Measure QSORT() progress */\n+\tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n+\tstop_progress(&progress);\n+\n+\tprogress = start_sparse_progress(_(\"Verifying object offsets\"),\n+\t\t\t\t\t m->num_objects);\n+\tfor (k = 0; k < m->num_objects; k++) {\n \t\tstruct object_id oid;\n \t\tstruct pack_entry e;\n \t\toff_t m_offset, p_offset;\n \n-\t\tnth_midxed_object_oid(&oid, m, i);\n+\t\tif (k > 0 && pairs[k-1].pack_int_id != pairs[k].pack_int_id &&\n+\t\t m->packs[pairs[k-1].pack_int_id])\n+\t\t{\n+\t\t\tclose_pack_fd(m->packs[pairs[k-1].pack_int_id]);\n+\t\t\tclose_pack_index(m->packs[pairs[k-1].pack_int_id]);\n+\t\t}\n+\n+\t\tnth_midxed_object_oid(&oid, m, pairs[k].pos);\n \t\tif (!fill_midx_entry(&oid, &e, m)) {\n \t\t\tmidx_report(_(\"failed to load pack entry for oid[%d] = %s\"),\n-\t\t\t\t i, oid_to_hex(&oid));\n+\t\t\t\t pairs[k].pos, oid_to_hex(&oid));\n \t\t\tcontinue;\n \t\t}\n \n@@ -1024,11 +1087,13 @@ int verify_midx_file(const char *object_dir)\n \n \t\tif (m_offset != p_offset)\n \t\t\tmidx_report(_(\"incorrect object offset for oid[%d] = %s: %\"PRIx64\" != %\"PRIx64),\n-\t\t\t\t i, oid_to_hex(&oid), m_offset, p_offset);\n+\t\t\t\t pairs[k].pos, oid_to_hex(&oid), m_offset, p_offset);\n \n-\t\tdisplay_progress(progress, i + 1);\n+\t\tmidx_display_sparse_progress(progress, k + 1);\n \t}\n \tstop_progress(&progress);\n \n+\tfree(pairs);\n+\n \treturn verify_midx_error;\n }\ndiff --git a/packfile.c b/packfile.c\nindex 16bcb75262..d2bcb2f860 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -309,7 +309,7 @@ void close_pack_windows(struct packed_git *p)\n \t}\n }\n \n-static int close_pack_fd(struct packed_git *p)\n+int close_pack_fd(struct packed_git *p)\n {\n \tif (p->pack_fd < 0)\n \t\treturn 0;\ndiff --git a/packfile.h b/packfile.h\nindex d70c6d9afb..b1c18504eb 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -76,6 +76,8 @@ extern int open_pack_index(struct packed_git *);\n */\n extern void close_pack_index(struct packed_git *);\n \n+int close_pack_fd(struct packed_git *p);\n+\n extern uint32_t get_pack_fanout(struct packed_git *p, uint32_t value);\n \n extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t, unsigned long *);\n-- \ngitgitgadget\n"},{"id":"371912","messageId":"CAPig+cTC0AmJyU7D=f9VAGOOwJpk+aMe95MDqiiCqMdU5-kk+A@mail.gmail.com","threadId":"50771","inReplyTo":"e1da1f84a85165703e3b6be4a240bd36d62b4b01.1553006268.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/4] progress: add sparse mode to force 100% complete message","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2019-03-19T16:42:54Z","receivedAt":"2019-03-19T16:43:09Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Tue, Mar 19, 2019 at 10:37 AM Jeff Hostetler via GitGitGadget\n wrote:\n> Add new start_sparse_progress() and start_delayed_sparse_progress()\n> constructors and \"sparse\" flag to struct progress.\n>\n> Teach stop_progress() to force a 100% complete progress message before\n> printing the final \"done\" message when \"sparse\" is set.\n>\n> Calling display_progress() for every item in a large set can\n> be expensive. If callers try to filter this for performance\n> reasons, such as emitting every k-th item, progress would\n> not reach 100% unless they made a final call to display_progress()\n> with the item count before calling stop_progress().\n>\n> Now this is automatic when \"sparse\" is set.\n>\n> Signed-off-by: Jeff Hostetler \n> ---\n> diff --git a/progress.c b/progress.c\n> +/*\n> + * Here \"sparse\" means that the caller might use some sampling criteria to\n> + * decide when to call display_progress() rather than calling it for every\n> + * integer value in[0 .. total). In particular, the caller might not call\n> + * display_progress() for the last value in the range.\n> + *\n> + * When \"sparse\" is set, stop_progress() will automatically force the done\n> + * message to show 100%.\n> + */\n> +static void finish_if_sparse(struct progress **p_progress)\n> +{\n> + struct progress *progress = *p_progress;\n> +\n> + if (progress &&\n> + progress->sparse &&\n> + progress->last_value != progress->total)\n> + display_progress(progress, progress->total);\n> }\n\nThere's no reason for this function to take a 'struct progress **'\nrather than the simpler 'struct progress *', and doing so just\nconfuses the reader.\n\n> void stop_progress(struct progress **p_progress)\n> {\n> + finish_if_sparse(p_progress);\n> +\n> stop_progress_msg(p_progress, _(\"done\"));\n> }\n\nRather than adding a new \"sparse\" mode, I wonder if this entire\nconcept can be boiled down to a single new function:\n\n void finish_progress(struct progress **p_progress, const char *msg)\n {\n struct progress *progress = *p_progress;\n if (progress && progress->last_value != progress->total)\n display_progress(progress, progress->total);\n if (msg)\n stop_progress_msg(p_progress, msg);\n else\n stop_progress(p_progress);\n }\n\nwithout having to make any other changes to the implementation or add\na new field to the structure. It would mean, though, that the caller\nwould have to remember to invoke finish_progress() rather than\nstop_progress(). Which leads one to wonder why this functionality is\nneeded at all since it's easy enough for a caller to make the one\nextra call to simulate this:\n\n /* client code */\n if (progress)\n display_progress(progress, progress->total);\n stop_progress(&progress);\n"},{"id":"371915","messageId":"fbb2ce21-18ce-3d1e-e6f6-907c8b9693d9@jeffhostetler.com","threadId":"50771","inReplyTo":"CAPig+cTC0AmJyU7D=f9VAGOOwJpk+aMe95MDqiiCqMdU5-kk+A@mail.gmail.com","subject":"Re: [PATCH v2 1/4] progress: add sparse mode to force 100% complete message","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2019-03-19T18:33:38Z","receivedAt":"2019-03-19T18:33:41Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 3/19/2019 12:42 PM, Eric Sunshine wrote:\n> On Tue, Mar 19, 2019 at 10:37 AM Jeff Hostetler via GitGitGadget\n> wrote:\n>> Add new start_sparse_progress() and start_delayed_sparse_progress()\n>> constructors and \"sparse\" flag to struct progress.\n>>\n>> Teach stop_progress() to force a 100% complete progress message before\n>> printing the final \"done\" message when \"sparse\" is set.\n>>\n>> Calling display_progress() for every item in a large set can\n>> be expensive. If callers try to filter this for performance\n>> reasons, such as emitting every k-th item, progress would\n>> not reach 100% unless they made a final call to display_progress()\n>> with the item count before calling stop_progress().\n>>\n>> Now this is automatic when \"sparse\" is set.\n>>\n>> Signed-off-by: Jeff Hostetler \n>> ---\n>> diff --git a/progress.c b/progress.c\n>> +/*\n>> + * Here \"sparse\" means that the caller might use some sampling criteria to\n>> + * decide when to call display_progress() rather than calling it for every\n>> + * integer value in[0 .. total). In particular, the caller might not call\n>> + * display_progress() for the last value in the range.\n>> + *\n>> + * When \"sparse\" is set, stop_progress() will automatically force the done\n>> + * message to show 100%.\n>> + */\n>> +static void finish_if_sparse(struct progress **p_progress)\n>> +{\n>> + struct progress *progress = *p_progress;\n>> +\n>> + if (progress &&\n>> + progress->sparse &&\n>> + progress->last_value != progress->total)\n>> + display_progress(progress, progress->total);\n>> }\n> \n> There's no reason for this function to take a 'struct progress **'\n> rather than the simpler 'struct progress *', and doing so just\n> confuses the reader.\n\nI was just trying to match the existing API in the stop_progress()\nand stop_progress_msg() routines. But yes, I can simplify this.\n\n> \n>> void stop_progress(struct progress **p_progress)\n>> {\n>> + finish_if_sparse(p_progress);\n>> +\n>> stop_progress_msg(p_progress, _(\"done\"));\n>> }\n> \n> Rather than adding a new \"sparse\" mode, I wonder if this entire\n> concept can be boiled down to a single new function:\n> \n> void finish_progress(struct progress **p_progress, const char *msg)\n> {\n> struct progress *progress = *p_progress;\n> if (progress && progress->last_value != progress->total)\n> display_progress(progress, progress->total);\n> if (msg)\n> stop_progress_msg(p_progress, msg);\n> else\n> stop_progress(p_progress);\n> }\n> \n> without having to make any other changes to the implementation or add\n> a new field to the structure.\n\nThe existing model has start_progress() and start_delayed_progress().\nI was following that model and added the new option at the start.\nI'm not planning on adding any additional flags, but if we had some\nwe'd want them available on the startup next to this one.\n\n\n> It would mean, though, that the caller\n> would have to remember to invoke finish_progress() rather than\n> stop_progress().\n\nRight, I was trying to isolate the change to the setup, so that loop\nbottoms and any in-loop return points don't all have to worry about\nwhether to call stop_ or finish_.\n\n\n> Which leads one to wonder why this functionality is\n> needed at all since it's easy enough for a caller to make the one\n> extra call to simulate this:\n> \n> /* client code */\n> if (progress)\n> display_progress(progress, progress->total);\n> stop_progress(&progress);\n> \n\n\"struct progress\" is private and I didn't want to publish it just for\nthis. And again as with the finish_ remarks, that leads to more\nplaces that would need to be updated or maintained.\n\nAnd you're right, callers could always just call:\n\tx = ...whatever...\n\tprogress = start_progress(..., x);\n\t...loop or whatever...\n\tdisplay_progress(progress, x);\n\tstop_progress(...);\n\nbut that puts the burden on the caller to keep a copy of \"x\"\nthat matches the original value so that we get the 100% message.\nI was doing that for a while, but after 3 or 4 progress loops,\nI found myself wanting the progress routines to handle that\nbookkeeping for me.\n\nJeff\n\n"},{"id":"371916","messageId":"CAPig+cQhs-YDv2LySbAJkXOWGEAQohkPipj1WLz-BZqrWFyo1Q@mail.gmail.com","threadId":"50771","inReplyTo":"fbb2ce21-18ce-3d1e-e6f6-907c8b9693d9@jeffhostetler.com","subject":"Re: [PATCH v2 1/4] progress: add sparse mode to force 100% complete message","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2019-03-19T18:46:54Z","receivedAt":"2019-03-19T18:47:08Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Tue, Mar 19, 2019 at 2:33 PM Jeff Hostetler wrote:\n> On 3/19/2019 12:42 PM, Eric Sunshine wrote:\n> > Rather than adding a new \"sparse\" mode, I wonder if this entire\n> > concept can be boiled down to a single new function:\n> >\n> > void finish_progress(struct progress **p_progress, const char *msg)\n> > {\n> > [...]\n> > }\n> >\n> > without having to make any other changes to the implementation or add\n> > a new field to the structure.\n>\n> The existing model has start_progress() and start_delayed_progress().\n> I was following that model and added the new option at the start.\n> I'm not planning on adding any additional flags, but if we had some\n> we'd want them available on the startup next to this one.\n\nPerhaps it makes sense to just take a 'flags' argument instead of\n'sparse' so we don't have to worry about this going forward. In other\nwords:\n\n #define PROGRESS_DELAYED (1 << 0)\n #define PROGRESS_SPARSE (1 << 1)\n\n struct progress *start_progress_x(const char *title, uint64_t total,\n unsigned flags);\n\nwhich covers \"delayed\" start and \"sparse\". (\"_x\" is a placeholder\nsince I can't think of a good name).\n\n> > It would mean, though, that the caller\n> > would have to remember to invoke finish_progress() rather than\n> > stop_progress().\n>\n> Right, I was trying to isolate the change to the setup, so that loop\n> bottoms and any in-loop return points don't all have to worry about\n> whether to call stop_ or finish_.\n\nYes, I understand the benefit.\n\nAnyhow, my comments are akin to bikeshedding, thus not necessarily actionable.\n"},{"id":"371930","messageId":"e09812cf-5c9a-4829-9b6e-0cf8c4fb79c7@jeffhostetler.com","threadId":"50771","inReplyTo":"ced7f1cb3486885aef018d91fae37958282a351e.1553006268.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 3/4] midx: verify: add midx packfiles to the packed_git list","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2019-03-19T19:53:34Z","receivedAt":"2019-03-19T19:53:37Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 3/19/2019 10:37 AM, Jeff Hostetler via GitGitGadget wrote:\n> From: Jeff Hostetler \n> \n> Fix \"git multi-pack-index verify\" to handle repos with thousands\n> of packfiles.\n> \n> Midx verify adds the individual \"packed_git\" structures to the\n> multi_pack_index.packs array, but it does not add them to the\n> \"repository.objects.packed_git\" list. During the verification\n> code, each packfile is opened and scanned. And \"pack_open_fds\"\n> is incremented. If \"pack_open_fds\" equals the \"pack_max_fds\"\n> open_packed_git_1() calls close_one_pack() to LRU-style close\n> an already open packfile. But because the packfiles were never\n> added to the \"packed_git\" list, close_one_pack() does nothing.\n> If there are very many packfiles, Git runs out of file descriptors\n> and fails.\n> \n> Note that this was observed on Windows when build with GCC and\n> in a repository with more than (2048-25) packfiles.\n> \n> Signed-off-by: Jeff Hostetler \n> ---\n> midx.c | 3 +++\n> 1 file changed, 3 insertions(+)\n> \n> diff --git a/midx.c b/midx.c\n> index 24141a7c62..b2f33bcd90 100644\n> --- a/midx.c\n> +++ b/midx.c\n> @@ -975,6 +975,9 @@ int verify_midx_file(const char *object_dir)\n> \tfor (i = 0; i < m->num_packs; i++) {\n> \t\tif (prepare_midx_pack(m, i))\n> \t\t\tmidx_report(\"failed to load pack in position %d\", i);\n> +\n> +\t\tif (m->packs[i])\n> +\t\t\tinstall_packed_git(the_repository, m->packs[i]);\n> \t}\n> \n> \tfor (i = 0; i < 255; i++) {\n> \n\nI'd like to drop this commit from this series.\n\nI talked with Stolee offline about this. It does\naddress the problem in this one instance, but it leads\nus to think about other places where there may be a\nsimilar problem.\n\nAlso, the sort by packfile in the next commit in this\nseries means we'll only have 1 packfile open at a time\nand so this commit isn't needed in this particular case.\n\nThanks,\nJeff\n\n"},{"id":"372153","messageId":"498258b12097acf9dfe6c06f3b256cbd9b0c2e9f.1553196970.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.v3.git.gitgitgadget@gmail.com","subject":"[PATCH v3 2/4] trace2:data: add trace2 data to midx","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-21T19:36:13Z","receivedAt":"2019-03-21T19:36:16Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nLog multi-pack-index command mode.\nLog number of objects and packfiles in the midx.\n\nSigned-off-by: Jeff Hostetler \n---\n builtin/multi-pack-index.c | 3 +++\n midx.c | 4 ++++\n 2 files changed, 7 insertions(+)\n\ndiff --git a/builtin/multi-pack-index.c b/builtin/multi-pack-index.c\nindex fca70f8e4f..ae6e476ad5 100644\n--- a/builtin/multi-pack-index.c\n+++ b/builtin/multi-pack-index.c\n@@ -3,6 +3,7 @@\n #include \"config.h\"\n #include \"parse-options.h\"\n #include \"midx.h\"\n+#include \"trace2.h\"\n \n static char const * const builtin_multi_pack_index_usage[] = {\n \tN_(\"git multi-pack-index [--object-dir=] (write|verify)\"),\n@@ -40,6 +41,8 @@ int cmd_multi_pack_index(int argc, const char **argv,\n \t\treturn 1;\n \t}\n \n+\ttrace2_cmd_mode(argv[0]);\n+\n \tif (!strcmp(argv[0], \"write\"))\n \t\treturn write_midx_file(opts.object_dir);\n \tif (!strcmp(argv[0], \"verify\"))\ndiff --git a/midx.c b/midx.c\nindex 8a505fd423..24141a7c62 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -8,6 +8,7 @@\n #include \"sha1-lookup.h\"\n #include \"midx.h\"\n #include \"progress.h\"\n+#include \"trace2.h\"\n \n #define MIDX_SIGNATURE 0x4d494458 /* \"MIDX\" */\n #define MIDX_VERSION 1\n@@ -164,6 +165,9 @@ struct multi_pack_index *load_multi_pack_index(const char *object_dir, int local\n \t\t\t m->pack_names[i]);\n \t}\n \n+\ttrace2_data_intmax(\"midx\", the_repository, \"load/num_packs\", m->num_packs);\n+\ttrace2_data_intmax(\"midx\", the_repository, \"load/num_objects\", m->num_objects);\n+\n \treturn m;\n \n cleanup_fail:\n-- \ngitgitgadget\n\n"},{"id":"372154","messageId":"pull.166.v3.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.v2.git.gitgitgadget@gmail.com","subject":"[PATCH v3 0/4] multi-pack-index: fix verify on large repos","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-21T19:36:11Z","receivedAt":"2019-03-21T19:36:17Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"Version 3 drops the packed-git commit I mentioned earlier, simplifies the\nfinish_if_sparse API as suggested by Eric, and splits the object sort commit\ninto 2 commits: one to add the additional progress indicators and one to\nsort the objects by packfile. This makes it easier to follow.\n\n\n----------------------------------------------------------------------------\n\nVersion 2 addresses progress-related concerns raised in the previous version\nof the midx verify code.\n\nThis version also extends the existing progress.[ch] code and adds a\n\"sparse\" mode that automatically ensures the 100% message is issued.\n\n\n----------------------------------------------------------------------------\n\nTeach \"multi-pack-index verify\" to handle cases where the number of\npackfiles exceeds the open file handle limit.\n\nThe first commit fixes a problem that prevented the LRU-style\nclose_one_pack() mechanism from working which caused midx verify to run out\nof file descriptors.\n\nThe second commit teaches midx verify to sort the set of objects to verify\nby packfile rather than verifying them in OID order. This eliminates the\nneed to have more than one packfile/idx open at the same time.\n\nWith the second commit, runtime on 3600 packfiles went from 12 minutes to 25\nseconds.\n\nThanks, Jeff\n\nCc: dstolee@microsoft.com\n\nJeff Hostetler (4):\n progress: add sparse mode to force 100% complete message\n trace2:data: add trace2 data to midx\n midx: add progress indicators in multi-pack-index verify\n midx: during verify group objects by packfile to speed verification\n\n builtin/multi-pack-index.c | 3 ++\n midx.c | 79 +++++++++++++++++++++++++++++++++++---\n packfile.c | 2 +-\n packfile.h | 2 +\n progress.c | 38 ++++++++++++++++--\n progress.h | 3 ++\n 6 files changed, 118 insertions(+), 9 deletions(-)\n\n\nbase-commit: e902e9bcae2010bc42648c80ab6adc6c5a16a4a5\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-166%2Fjeffhostetler%2Fupstream-midx-verify-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-166/jeffhostetler/upstream-midx-verify-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/166\n\nRange-diff vs v2:\n\n 1: e1da1f84a8 ! 1: 5595e019c8 progress: add sparse mode to force 100% complete message\n @@ -80,10 +80,8 @@\n +\treturn start_progress_delay(title, total, 2, 1);\n +}\n +\n -+static void finish_if_sparse(struct progress **p_progress)\n ++static void finish_if_sparse(struct progress *progress)\n +{\n -+\tstruct progress *progress = *p_progress;\n -+\n +\tif (progress &&\n +\t progress->sparse &&\n +\t progress->last_value != progress->total)\n @@ -92,7 +90,7 @@\n \n void stop_progress(struct progress **p_progress)\n {\n -+\tfinish_if_sparse(p_progress);\n ++\tfinish_if_sparse(*p_progress);\n +\n \tstop_progress_msg(p_progress, _(\"done\"));\n }\n 2: 11c88845e7 = 2: 498258b120 trace2:data: add trace2 data to midx\n 3: ced7f1cb34 < -: ---------- midx: verify: add midx packfiles to the packed_git list\n -: ---------- > 3: 8a60902d65 midx: add progress indicators in multi-pack-index verify\n 4: e2dd99911f ! 4: 7e98ea005a midx: verify: group objects by packfile to speed up object verification\n @@ -1,8 +1,8 @@\n Author: Jeff Hostetler \n \n - midx: verify: group objects by packfile to speed up object verification\n + midx: during verify group objects by packfile to speed verification\n \n - Teach `multi-pack-index verify` to sort the set of objects by\n + Teach `multi-pack-index verify` to sort the set of object by\n packfile so that only one packfile needs to be open at a time.\n \n This is a performance improvement. Previously, objects were\n @@ -34,64 +34,21 @@\n +\treturn b->pack_int_id - a->pack_int_id;\n +}\n +\n -+/*\n -+ * Limit calls to display_progress() for performance reasons.\n -+ * The interval here was arbitrarily chosen.\n -+ */\n -+#define SPARSE_PROGRESS_INTERVAL (1 << 12)\n -+#define midx_display_sparse_progress(progress, n) \\\n -+\tdo { \\\n -+\t\tuint64_t _n = (n); \\\n -+\t\tif ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0)\t\\\n -+\t\t\tdisplay_progress(progress, _n); \\\n -+\t} while (0)\n -+\n + /*\n + * Limit calls to display_progress() for performance reasons.\n + * The interval here was arbitrarily chosen.\n +@@\n + \n int verify_midx_file(const char *object_dir)\n {\n --\tuint32_t i;\n +\tstruct pair_pos_vs_id *pairs = NULL;\n -+\tuint32_t i, k;\n + \tuint32_t i;\n \tstruct progress *progress;\n \tstruct multi_pack_index *m = load_multi_pack_index(object_dir, 1);\n - \tverify_midx_error = 0;\n -@@\n - \tif (!m)\n - \t\treturn 0;\n - \n -+\tprogress = start_progress(_(\"Looking for referenced packfiles\"),\n -+\t\t\t\t m->num_packs);\n - \tfor (i = 0; i < m->num_packs; i++) {\n - \t\tif (prepare_midx_pack(m, i))\n - \t\t\tmidx_report(\"failed to load pack in position %d\", i);\n - \n - \t\tif (m->packs[i])\n - \t\t\tinstall_packed_git(the_repository, m->packs[i]);\n -+\n -+\t\tdisplay_progress(progress, i + 1);\n - \t}\n -+\tstop_progress(&progress);\n - \n - \tfor (i = 0; i < 255; i++) {\n - \t\tuint32_t oid_fanout1 = ntohl(m->chunk_oid_fanout[i]);\n @@\n - \t\t\t\t i, oid_fanout1, oid_fanout2, i + 1);\n \t}\n + \tstop_progress(&progress);\n \n -+\tprogress = start_sparse_progress(_(\"Verifying OID order in MIDX\"),\n -+\t\t\t\t\t m->num_objects - 1);\n - \tfor (i = 0; i < m->num_objects - 1; i++) {\n - \t\tstruct object_id oid1, oid2;\n - \n -@@\n - \t\tif (oidcmp(&oid1, &oid2) >= 0)\n - \t\t\tmidx_report(_(\"oid lookup out of order: oid[%d] = %s >= %s = oid[%d]\"),\n - \t\t\t\t i, oid_to_hex(&oid1), oid_to_hex(&oid2), i + 1);\n -+\n -+\t\tmidx_display_sparse_progress(progress, i + 1);\n - \t}\n -+\tstop_progress(&progress);\n - \n --\tprogress = start_progress(_(\"Verifying object offsets\"), m->num_objects);\n +\t/*\n +\t * Create an array mapping each object to its packfile id. Sort it\n +\t * to group the objects by packfile. Use this permutation to visit\n @@ -99,37 +56,37 @@\n +\t * time.\n +\t */\n +\tALLOC_ARRAY(pairs, m->num_objects);\n - \tfor (i = 0; i < m->num_objects; i++) {\n ++\tfor (i = 0; i < m->num_objects; i++) {\n +\t\tpairs[i].pos = i;\n +\t\tpairs[i].pack_int_id = nth_midxed_pack_int_id(m, i);\n +\t}\n +\n -+\tprogress = start_sparse_progress(\n -+\t\t_(\"Sorting objects by packfile\"), m->num_objects);\n ++\tprogress = start_sparse_progress(_(\"Sorting objects by packfile\"),\n ++\t\t\t\t\t m->num_objects);\n +\tdisplay_progress(progress, 0); /* TODO: Measure QSORT() progress */\n +\tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n +\tstop_progress(&progress);\n +\n -+\tprogress = start_sparse_progress(_(\"Verifying object offsets\"),\n -+\t\t\t\t\t m->num_objects);\n -+\tfor (k = 0; k < m->num_objects; k++) {\n + \tprogress = start_sparse_progress(_(\"Verifying object offsets\"), m->num_objects);\n + \tfor (i = 0; i < m->num_objects; i++) {\n \t\tstruct object_id oid;\n \t\tstruct pack_entry e;\n \t\toff_t m_offset, p_offset;\n \n -\t\tnth_midxed_object_oid(&oid, m, i);\n -+\t\tif (k > 0 && pairs[k-1].pack_int_id != pairs[k].pack_int_id &&\n -+\t\t m->packs[pairs[k-1].pack_int_id])\n ++\t\tif (i > 0 && pairs[i-1].pack_int_id != pairs[i].pack_int_id &&\n ++\t\t m->packs[pairs[i-1].pack_int_id])\n +\t\t{\n -+\t\t\tclose_pack_fd(m->packs[pairs[k-1].pack_int_id]);\n -+\t\t\tclose_pack_index(m->packs[pairs[k-1].pack_int_id]);\n ++\t\t\tclose_pack_fd(m->packs[pairs[i-1].pack_int_id]);\n ++\t\t\tclose_pack_index(m->packs[pairs[i-1].pack_int_id]);\n +\t\t}\n +\n -+\t\tnth_midxed_object_oid(&oid, m, pairs[k].pos);\n ++\t\tnth_midxed_object_oid(&oid, m, pairs[i].pos);\n ++\n \t\tif (!fill_midx_entry(&oid, &e, m)) {\n \t\t\tmidx_report(_(\"failed to load pack entry for oid[%d] = %s\"),\n -\t\t\t\t i, oid_to_hex(&oid));\n -+\t\t\t\t pairs[k].pos, oid_to_hex(&oid));\n ++\t\t\t\t pairs[i].pos, oid_to_hex(&oid));\n \t\t\tcontinue;\n \t\t}\n \n @@ -138,10 +95,9 @@\n \t\tif (m_offset != p_offset)\n \t\t\tmidx_report(_(\"incorrect object offset for oid[%d] = %s: %\"PRIx64\" != %\"PRIx64),\n -\t\t\t\t i, oid_to_hex(&oid), m_offset, p_offset);\n -+\t\t\t\t pairs[k].pos, oid_to_hex(&oid), m_offset, p_offset);\n ++\t\t\t\t pairs[i].pos, oid_to_hex(&oid), m_offset, p_offset);\n \n --\t\tdisplay_progress(progress, i + 1);\n -+\t\tmidx_display_sparse_progress(progress, k + 1);\n + \t\tmidx_display_sparse_progress(progress, i + 1);\n \t}\n \tstop_progress(&progress);\n \n\n-- \ngitgitgadget\n"},{"id":"372155","messageId":"8a60902d65c6b36c20b6e9fc99eace37602ca28b.1553196970.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.v3.git.gitgitgadget@gmail.com","subject":"[PATCH v3 3/4] midx: add progress indicators in multi-pack-index verify","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-21T19:36:14Z","receivedAt":"2019-03-21T19:36:18Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nAdd progress indicators to more parts of midx verify.\nUse sparse progress indicator for object iteration.\n\nSigned-off-by: Jeff Hostetler \n---\n midx.c | 26 ++++++++++++++++++++++++--\n 1 file changed, 24 insertions(+), 2 deletions(-)\n\ndiff --git a/midx.c b/midx.c\nindex 24141a7c62..e3919387d9 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -962,6 +962,18 @@ static void midx_report(const char *fmt, ...)\n \tva_end(ap);\n }\n \n+/*\n+ * Limit calls to display_progress() for performance reasons.\n+ * The interval here was arbitrarily chosen.\n+ */\n+#define SPARSE_PROGRESS_INTERVAL (1 << 12)\n+#define midx_display_sparse_progress(progress, n) \\\n+\tdo { \\\n+\t\tuint64_t _n = (n); \\\n+\t\tif ((_n & (SPARSE_PROGRESS_INTERVAL - 1)) == 0) \\\n+\t\t\tdisplay_progress(progress, _n); \\\n+\t} while (0)\n+\n int verify_midx_file(const char *object_dir)\n {\n \tuint32_t i;\n@@ -972,10 +984,15 @@ int verify_midx_file(const char *object_dir)\n \tif (!m)\n \t\treturn 0;\n \n+\tprogress = start_progress(_(\"Looking for referenced packfiles\"),\n+\t\t\t\t m->num_packs);\n \tfor (i = 0; i < m->num_packs; i++) {\n \t\tif (prepare_midx_pack(m, i))\n \t\t\tmidx_report(\"failed to load pack in position %d\", i);\n+\n+\t\tdisplay_progress(progress, i + 1);\n \t}\n+\tstop_progress(&progress);\n \n \tfor (i = 0; i < 255; i++) {\n \t\tuint32_t oid_fanout1 = ntohl(m->chunk_oid_fanout[i]);\n@@ -986,6 +1003,8 @@ int verify_midx_file(const char *object_dir)\n \t\t\t\t i, oid_fanout1, oid_fanout2, i + 1);\n \t}\n \n+\tprogress = start_sparse_progress(_(\"Verifying OID order in MIDX\"),\n+\t\t\t\t\t m->num_objects - 1);\n \tfor (i = 0; i < m->num_objects - 1; i++) {\n \t\tstruct object_id oid1, oid2;\n \n@@ -995,9 +1014,12 @@ int verify_midx_file(const char *object_dir)\n \t\tif (oidcmp(&oid1, &oid2) >= 0)\n \t\t\tmidx_report(_(\"oid lookup out of order: oid[%d] = %s >= %s = oid[%d]\"),\n \t\t\t\t i, oid_to_hex(&oid1), oid_to_hex(&oid2), i + 1);\n+\n+\t\tmidx_display_sparse_progress(progress, i + 1);\n \t}\n+\tstop_progress(&progress);\n \n-\tprogress = start_progress(_(\"Verifying object offsets\"), m->num_objects);\n+\tprogress = start_sparse_progress(_(\"Verifying object offsets\"), m->num_objects);\n \tfor (i = 0; i < m->num_objects; i++) {\n \t\tstruct object_id oid;\n \t\tstruct pack_entry e;\n@@ -1023,7 +1045,7 @@ int verify_midx_file(const char *object_dir)\n \t\t\tmidx_report(_(\"incorrect object offset for oid[%d] = %s: %\"PRIx64\" != %\"PRIx64),\n \t\t\t\t i, oid_to_hex(&oid), m_offset, p_offset);\n \n-\t\tdisplay_progress(progress, i + 1);\n+\t\tmidx_display_sparse_progress(progress, i + 1);\n \t}\n \tstop_progress(&progress);\n \n-- \ngitgitgadget\n\n"},{"id":"372156","messageId":"5595e019c82b0aa67c2c738dbb9b9ec8287ec363.1553196970.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.v3.git.gitgitgadget@gmail.com","subject":"[PATCH v3 1/4] progress: add sparse mode to force 100% complete message","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-21T19:36:11Z","receivedAt":"2019-03-21T19:36:20Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nAdd new start_sparse_progress() and start_delayed_sparse_progress()\nconstructors and \"sparse\" flag to struct progress.\n\nTeach stop_progress() to force a 100% complete progress message before\nprinting the final \"done\" message when \"sparse\" is set.\n\nCalling display_progress() for every item in a large set can\nbe expensive. If callers try to filter this for performance\nreasons, such as emitting every k-th item, progress would\nnot reach 100% unless they made a final call to display_progress()\nwith the item count before calling stop_progress().\n\nNow this is automatic when \"sparse\" is set.\n\nSigned-off-by: Jeff Hostetler \n---\n progress.c | 38 +++++++++++++++++++++++++++++++++++---\n progress.h | 3 +++\n 2 files changed, 38 insertions(+), 3 deletions(-)\n\ndiff --git a/progress.c b/progress.c\nindex 5a99c9fbf0..212d00e524 100644\n--- a/progress.c\n+++ b/progress.c\n@@ -34,6 +34,7 @@ struct progress {\n \tuint64_t total;\n \tunsigned last_percent;\n \tunsigned delay;\n+\tunsigned sparse;\n \tstruct throughput *throughput;\n \tuint64_t start_ns;\n };\n@@ -194,7 +195,7 @@ int display_progress(struct progress *progress, uint64_t n)\n }\n \n static struct progress *start_progress_delay(const char *title, uint64_t total,\n-\t\t\t\t\t unsigned delay)\n+\t\t\t\t\t unsigned delay, unsigned sparse)\n {\n \tstruct progress *progress = malloc(sizeof(*progress));\n \tif (!progress) {\n@@ -208,6 +209,7 @@ static struct progress *start_progress_delay(const char *title, uint64_t total,\n \tprogress->last_value = -1;\n \tprogress->last_percent = -1;\n \tprogress->delay = delay;\n+\tprogress->sparse = sparse;\n \tprogress->throughput = NULL;\n \tprogress->start_ns = getnanotime();\n \tset_progress_signal();\n@@ -216,16 +218,46 @@ static struct progress *start_progress_delay(const char *title, uint64_t total,\n \n struct progress *start_delayed_progress(const char *title, uint64_t total)\n {\n-\treturn start_progress_delay(title, total, 2);\n+\treturn start_progress_delay(title, total, 2, 0);\n }\n \n struct progress *start_progress(const char *title, uint64_t total)\n {\n-\treturn start_progress_delay(title, total, 0);\n+\treturn start_progress_delay(title, total, 0, 0);\n+}\n+\n+/*\n+ * Here \"sparse\" means that the caller might use some sampling criteria to\n+ * decide when to call display_progress() rather than calling it for every\n+ * integer value in[0 .. total). In particular, the caller might not call\n+ * display_progress() for the last value in the range.\n+ *\n+ * When \"sparse\" is set, stop_progress() will automatically force the done\n+ * message to show 100%.\n+ */\n+struct progress *start_sparse_progress(const char *title, uint64_t total)\n+{\n+\treturn start_progress_delay(title, total, 0, 1);\n+}\n+\n+struct progress *start_delayed_sparse_progress(const char *title,\n+\t\t\t\t\t uint64_t total)\n+{\n+\treturn start_progress_delay(title, total, 2, 1);\n+}\n+\n+static void finish_if_sparse(struct progress *progress)\n+{\n+\tif (progress &&\n+\t progress->sparse &&\n+\t progress->last_value != progress->total)\n+\t\tdisplay_progress(progress, progress->total);\n }\n \n void stop_progress(struct progress **p_progress)\n {\n+\tfinish_if_sparse(*p_progress);\n+\n \tstop_progress_msg(p_progress, _(\"done\"));\n }\n \ndiff --git a/progress.h b/progress.h\nindex 70a4d4a0d6..7b725acc8d 100644\n--- a/progress.h\n+++ b/progress.h\n@@ -6,7 +6,10 @@ struct progress;\n void display_throughput(struct progress *progress, uint64_t total);\n int display_progress(struct progress *progress, uint64_t n);\n struct progress *start_progress(const char *title, uint64_t total);\n+struct progress *start_sparse_progress(const char *title, uint64_t total);\n struct progress *start_delayed_progress(const char *title, uint64_t total);\n+struct progress *start_delayed_sparse_progress(const char *title,\n+\t\t\t\t\t uint64_t total);\n void stop_progress(struct progress **progress);\n void stop_progress_msg(struct progress **progress, const char *msg);\n \n-- \ngitgitgadget\n\n"},{"id":"372157","messageId":"7e98ea005aa62ca36af7da34dc6c21a1f77b351e.1553196970.git.gitgitgadget@gmail.com","threadId":"50771","inReplyTo":"pull.166.v3.git.gitgitgadget@gmail.com","subject":"[PATCH v3 4/4] midx: during verify group objects by packfile to speed verification","fromName":"Jeff Hostetler via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2019-03-21T19:36:15Z","receivedAt":"2019-03-21T19:36:21Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"From: Jeff Hostetler \n\nTeach `multi-pack-index verify` to sort the set of object by\npackfile so that only one packfile needs to be open at a time.\n\nThis is a performance improvement. Previously, objects were\nverified in OID order. This essentially requires all packfiles\nto be open at the same time. If the number of packfiles exceeds\nthe open file limit, packfiles would be LRU-closed and re-opened\nmany times.\n\nSigned-off-by: Jeff Hostetler \n---\n midx.c | 49 ++++++++++++++++++++++++++++++++++++++++++++++---\n packfile.c | 2 +-\n packfile.h | 2 ++\n 3 files changed, 49 insertions(+), 4 deletions(-)\n\ndiff --git a/midx.c b/midx.c\nindex e3919387d9..f1cd868f8c 100644\n--- a/midx.c\n+++ b/midx.c\n@@ -962,6 +962,20 @@ static void midx_report(const char *fmt, ...)\n \tva_end(ap);\n }\n \n+struct pair_pos_vs_id\n+{\n+\tuint32_t pos;\n+\tuint32_t pack_int_id;\n+};\n+\n+static int compare_pair_pos_vs_id(const void *_a, const void *_b)\n+{\n+\tstruct pair_pos_vs_id *a = (struct pair_pos_vs_id *)_a;\n+\tstruct pair_pos_vs_id *b = (struct pair_pos_vs_id *)_b;\n+\n+\treturn b->pack_int_id - a->pack_int_id;\n+}\n+\n /*\n * Limit calls to display_progress() for performance reasons.\n * The interval here was arbitrarily chosen.\n@@ -976,6 +990,7 @@ static void midx_report(const char *fmt, ...)\n \n int verify_midx_file(const char *object_dir)\n {\n+\tstruct pair_pos_vs_id *pairs = NULL;\n \tuint32_t i;\n \tstruct progress *progress;\n \tstruct multi_pack_index *m = load_multi_pack_index(object_dir, 1);\n@@ -1019,16 +1034,42 @@ int verify_midx_file(const char *object_dir)\n \t}\n \tstop_progress(&progress);\n \n+\t/*\n+\t * Create an array mapping each object to its packfile id. Sort it\n+\t * to group the objects by packfile. Use this permutation to visit\n+\t * each of the objects and only require 1 packfile to be open at a\n+\t * time.\n+\t */\n+\tALLOC_ARRAY(pairs, m->num_objects);\n+\tfor (i = 0; i < m->num_objects; i++) {\n+\t\tpairs[i].pos = i;\n+\t\tpairs[i].pack_int_id = nth_midxed_pack_int_id(m, i);\n+\t}\n+\n+\tprogress = start_sparse_progress(_(\"Sorting objects by packfile\"),\n+\t\t\t\t\t m->num_objects);\n+\tdisplay_progress(progress, 0); /* TODO: Measure QSORT() progress */\n+\tQSORT(pairs, m->num_objects, compare_pair_pos_vs_id);\n+\tstop_progress(&progress);\n+\n \tprogress = start_sparse_progress(_(\"Verifying object offsets\"), m->num_objects);\n \tfor (i = 0; i < m->num_objects; i++) {\n \t\tstruct object_id oid;\n \t\tstruct pack_entry e;\n \t\toff_t m_offset, p_offset;\n \n-\t\tnth_midxed_object_oid(&oid, m, i);\n+\t\tif (i > 0 && pairs[i-1].pack_int_id != pairs[i].pack_int_id &&\n+\t\t m->packs[pairs[i-1].pack_int_id])\n+\t\t{\n+\t\t\tclose_pack_fd(m->packs[pairs[i-1].pack_int_id]);\n+\t\t\tclose_pack_index(m->packs[pairs[i-1].pack_int_id]);\n+\t\t}\n+\n+\t\tnth_midxed_object_oid(&oid, m, pairs[i].pos);\n+\n \t\tif (!fill_midx_entry(&oid, &e, m)) {\n \t\t\tmidx_report(_(\"failed to load pack entry for oid[%d] = %s\"),\n-\t\t\t\t i, oid_to_hex(&oid));\n+\t\t\t\t pairs[i].pos, oid_to_hex(&oid));\n \t\t\tcontinue;\n \t\t}\n \n@@ -1043,11 +1084,13 @@ int verify_midx_file(const char *object_dir)\n \n \t\tif (m_offset != p_offset)\n \t\t\tmidx_report(_(\"incorrect object offset for oid[%d] = %s: %\"PRIx64\" != %\"PRIx64),\n-\t\t\t\t i, oid_to_hex(&oid), m_offset, p_offset);\n+\t\t\t\t pairs[i].pos, oid_to_hex(&oid), m_offset, p_offset);\n \n \t\tmidx_display_sparse_progress(progress, i + 1);\n \t}\n \tstop_progress(&progress);\n \n+\tfree(pairs);\n+\n \treturn verify_midx_error;\n }\ndiff --git a/packfile.c b/packfile.c\nindex 16bcb75262..d2bcb2f860 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -309,7 +309,7 @@ void close_pack_windows(struct packed_git *p)\n \t}\n }\n \n-static int close_pack_fd(struct packed_git *p)\n+int close_pack_fd(struct packed_git *p)\n {\n \tif (p->pack_fd < 0)\n \t\treturn 0;\ndiff --git a/packfile.h b/packfile.h\nindex d70c6d9afb..b1c18504eb 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -76,6 +76,8 @@ extern int open_pack_index(struct packed_git *);\n */\n extern void close_pack_index(struct packed_git *);\n \n+int close_pack_fd(struct packed_git *p);\n+\n extern uint32_t get_pack_fanout(struct packed_git *p, uint32_t value);\n \n extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t, unsigned long *);\n-- \ngitgitgadget\n"},{"id":"372203","messageId":"xmqqy357pizb.fsf@gitster-ct.c.googlers.com","threadId":"50771","inReplyTo":"pull.166.v3.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/4] multi-pack-index: fix verify on large repos","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-03-22T05:37:44Z","receivedAt":"2019-03-22T05:37:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Jeff Hostetler via GitGitGadget\" writes:\n\n> Teach \"multi-pack-index verify\" to handle cases where the number of\n> packfiles exceeds the open file handle limit.\n>\n> The first commit fixes a problem that prevented the LRU-style\n> close_one_pack() mechanism from working which caused midx verify to run out\n> of file descriptors.\n>\n> The second commit teaches midx verify to sort the set of objects to verify\n> by packfile rather than verifying them in OID order. This eliminates the\n> need to have more than one packfile/idx open at the same time.\n>\n> With the second commit, runtime on 3600 packfiles went from 12 minutes to 25\n> seconds.\n\nThese reference to the first and second commit might have become\nstale across interations, but logically it makes sense---the first\npoint is about correctness (i.e. do not die by running out of fds)\nand the second one is about usable-performance.\n\nBut in this round (possibly in the previous one, too?) the \"group\nobjects by packfile\" one addresses both points?\n"},{"id":"372441","messageId":"2eaa3617-326d-4f26-6bc0-7192a12ab192@jeffhostetler.com","threadId":"50771","inReplyTo":"xmqqy357pizb.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH v3 0/4] multi-pack-index: fix verify on large repos","fromName":"Jeff Hostetler","fromEmail":"git@jeffhostetler.com","sentAt":"2019-03-25T17:18:20Z","receivedAt":"2019-03-25T17:18:24Z","isPatch":true,"sender":{"key":"git@jeffhostetler.com","avatar":null},"body":"\n\nOn 3/22/2019 1:37 AM, Junio C Hamano wrote:\n> \"Jeff Hostetler via GitGitGadget\" writes:\n> \n>> Teach \"multi-pack-index verify\" to handle cases where the number of\n>> packfiles exceeds the open file handle limit.\n>>\n>> The first commit fixes a problem that prevented the LRU-style\n>> close_one_pack() mechanism from working which caused midx verify to run out\n>> of file descriptors.\n>>\n>> The second commit teaches midx verify to sort the set of objects to verify\n>> by packfile rather than verifying them in OID order. This eliminates the\n>> need to have more than one packfile/idx open at the same time.\n>>\n>> With the second commit, runtime on 3600 packfiles went from 12 minutes to 25\n>> seconds.\n> \n> These reference to the first and second commit might have become\n> stale across interations, but logically it makes sense---the first\n> point is about correctness (i.e. do not die by running out of fds)\n> and the second one is about usable-performance.\n> \n> But in this round (possibly in the previous one, too?) the \"group\n> objects by packfile\" one addresses both points?\n> \n\n\nSorry, I forgot to remote the stale content in the cover letter for\nthe V3 version.\n\nThis version just has the sorting by packfile commit and because it only\nkeeps 1 packfile open at a time, it does not need the change to add \npackfiles to the packed-git list because it does not trigger the\nclose_one_pack() problem.\n\nWe suspect there are other places (not-yet-observed) where the design of\nthe all-packs and packed-git lists will lead to similar fd exhaustion\nerrors and want to fix it properly in the packfile and/or midx code.\nWe'll address this potential problem in a future patch series.\n\nJeff\n"}]}