{"thread":{"id":"47194","subject":"[PATCH v2 1/4] sequencer: warn when internal merge may be suboptimal due to renameLimit","startedAt":"2017-11-13T20:16:15Z","lastAt":"2017-11-13T22:26:53Z","messageCount":8,"participants":["Elijah Newren","Jonathan Tan"],"isPatch":true,"patchVersion":2,"patchTotal":4},"messages":[{"id":"332439","messageId":"20171113201600.24878-2-newren@gmail.com","threadId":"47194","inReplyTo":"20171113201600.24878-1-newren@gmail.com","subject":"[PATCH v2 1/4] sequencer: warn when internal merge may be suboptimal due to renameLimit","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2017-11-13T20:15:57Z","receivedAt":"2017-11-13T20:16:15Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"When many files were renamed, the recursive merge strategy stopped\ndetecting renames and left many paths with delete/modify conflicts,\nwithout any warning about what was going on or providing any hints about\nhow to tell Git to spend more cycles to detect renames.\n\nSigned-off-by: Elijah Newren <newren@gmail.com>\n---\n sequencer.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/sequencer.c b/sequencer.c\nindex f2a10cc4f2..2b4cecb617 100644\n--- a/sequencer.c\n+++ b/sequencer.c\n@@ -462,6 +462,7 @@ static int do_recursive_merge(struct commit *base, struct commit *next,\n \tif (is_rebase_i(opts) && clean <= 0)\n \t\tfputs(o.obuf.buf, stdout);\n \tstrbuf_release(&o.obuf);\n+\tdiff_warn_rename_limit(\"merge.renamelimit\", o.needed_rename_limit, 0);\n \tif (clean < 0)\n \t\treturn clean;\n \n-- \n2.15.0.44.gf995e411c7\n\n"},{"id":"332440","messageId":"20171113201600.24878-4-newren@gmail.com","threadId":"47194","inReplyTo":"20171113201600.24878-1-newren@gmail.com","subject":"[PATCH v2 3/4] Remove silent clamp of renameLimit","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2017-11-13T20:15:59Z","receivedAt":"2017-11-13T20:16:16Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"In commit 0024a5492 (Fix the rename detection limit checking; 2007-09-14),\nthe renameLimit was clamped to 32767.  This appears to have been to simply\navoid integer overflow in the following computation:\n\n   num_create * num_src <= rename_limit * rename_limit\n\nalthough it also could be viewed as a hardcoded bound on the amount of CPU\ntime we're willing to allow users to tell git to spend on handling\nrenames.  An upper bound may make sense, but unfortunately this upper\nbound was neither communicated to the users, nor documented anywhere.\n\nAlthough large limits can make things slow, we have users who would be\necstatic to have a small five file change be correctly cherry picked even\nif they have to manually specify a large limit and wait ten minutes for\nthe renames to be detected.\n\nSigned-off-by: Elijah Newren <newren@gmail.com>\n---\n diff.c            |  2 +-\n diffcore-rename.c | 11 ++++-------\n 2 files changed, 5 insertions(+), 8 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 6fd288420b..c6597e3231 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -5524,7 +5524,7 @@ void diff_warn_rename_limit(const char *varname, int needed, int degraded_cc)\n \t\twarning(_(rename_limit_warning));\n \telse\n \t\treturn;\n-\tif (0 < needed && needed < 32767)\n+\tif (0 < needed)\n \t\twarning(_(rename_limit_advice), varname, needed);\n }\n \ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex c03f484d53..32366632f4 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -391,14 +391,10 @@ static int too_many_rename_candidates(int num_create,\n \t * growing larger than a \"rename_limit\" square matrix, ie:\n \t *\n \t *    num_create * num_src > rename_limit * rename_limit\n-\t *\n-\t * but handles the potential overflow case specially (and we\n-\t * assume at least 32-bit integers)\n \t */\n-\tif (rename_limit <= 0 || rename_limit > 32767)\n-\t\trename_limit = 32767;\n \tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n-\t    (num_create * num_src <= rename_limit * rename_limit))\n+\t    ((uint64_t)num_create * (uint64_t)num_src\n+\t     <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 0;\n \n \toptions->needed_rename_limit =\n@@ -415,7 +411,8 @@ static int too_many_rename_candidates(int num_create,\n \t\tnum_src++;\n \t}\n \tif ((num_create <= rename_limit || num_src <= rename_limit) &&\n-\t    (num_create * num_src <= rename_limit * rename_limit))\n+\t    ((uint64_t)num_create * (uint64_t)num_src\n+\t     <= (uint64_t)rename_limit * (uint64_t)rename_limit))\n \t\treturn 2;\n \treturn 1;\n }\n-- \n2.15.0.44.gf995e411c7\n\n"},{"id":"332441","messageId":"20171113201600.24878-1-newren@gmail.com","threadId":"47194","inReplyTo":null,"subject":"[PATCH v2 0/4] Fix issues with rename detection limits","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2017-11-13T20:15:56Z","receivedAt":"2017-11-13T20:16:19Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This patchset fixes some issues around rename detection limits.  Changes\nsince the original submission[1]:\n  * Patches 2 and 3 are swapped in order so as to not temporarily introduce\n    any bugs (even if only cosmetic)\n  * Commit message fixups\n  * Using uint64_t instead of double for holding multiplication of integers\n  * Corrected format specifier for printing 64-bit ints.\n\n[1] https://public-inbox.org/git/20171110173956.25105-1-newren@gmail.com/\n\nElijah Newren (4):\n  sequencer: warn when internal merge may be suboptimal due to\n    renameLimit\n  progress: fix progress meters when dealing with lots of work\n  Remove silent clamp of renameLimit\n  sequencer: show rename progress during cherry picks\n\n diff.c            |  2 +-\n diffcore-rename.c | 15 ++++++---------\n progress.c        | 22 +++++++++++-----------\n progress.h        |  8 ++++----\n sequencer.c       |  2 ++\n 5 files changed, 24 insertions(+), 25 deletions(-)\n\n-- \n2.15.0.44.gf995e411c7\n\n"},{"id":"332442","messageId":"20171113201600.24878-3-newren@gmail.com","threadId":"47194","inReplyTo":"20171113201600.24878-1-newren@gmail.com","subject":"[PATCH v2 2/4] progress: fix progress meters when dealing with lots of work","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2017-11-13T20:15:58Z","receivedAt":"2017-11-13T20:16:21Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"The possibility of setting merge.renameLimit beyond 2^16 raises the\npossibility that the values passed to progress can exceed 2^32.\nUse uint64_t, because it \"ought to be enough for anybody\".  :-)\n\nSigned-off-by: Elijah Newren <newren@gmail.com>\n---\nThis does imply 64-bit math for all progress operations.  Possible alternatives\nI could think of listed at\nhttps://public-inbox.org/git/CABPp-BH1Cpc9UfYpmBBAHWSqadg=QuD=28qx1oV29ZdvF4NbJw@mail.gmail.com/\nOpinions of others on whether 64-bit is okay, or preference for which alternative\nis picked?\n\n diffcore-rename.c |  4 ++--\n progress.c        | 22 +++++++++++-----------\n progress.h        |  8 ++++----\n 3 files changed, 17 insertions(+), 17 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 0d8c3d2ee4..c03f484d53 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -534,7 +534,7 @@ void diffcore_rename(struct diff_options *options)\n \tif (options->show_rename_progress) {\n \t\tprogress = start_delayed_progress(\n \t\t\t\t_(\"Performing inexact rename detection\"),\n-\t\t\t\trename_dst_nr * rename_src_nr);\n+\t\t\t\t(uint64_t)rename_dst_nr * (uint64_t)rename_src_nr);\n \t}\n \n \tmx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_create), sizeof(*mx));\n@@ -571,7 +571,7 @@ void diffcore_rename(struct diff_options *options)\n \t\t\tdiff_free_filespec_blob(two);\n \t\t}\n \t\tdst_cnt++;\n-\t\tdisplay_progress(progress, (i+1)*rename_src_nr);\n+\t\tdisplay_progress(progress, (uint64_t)(i+1)*(uint64_t)rename_src_nr);\n \t}\n \tstop_progress(&progress);\n \ndiff --git a/progress.c b/progress.c\nindex 289678d43d..837d3a8eb8 100644\n--- a/progress.c\n+++ b/progress.c\n@@ -30,8 +30,8 @@ struct throughput {\n \n struct progress {\n \tconst char *title;\n-\tint last_value;\n-\tunsigned total;\n+\tuint64_t last_value;\n+\tuint64_t total;\n \tunsigned last_percent;\n \tunsigned delay;\n \tunsigned delayed_percent_threshold;\n@@ -79,7 +79,7 @@ static int is_foreground_fd(int fd)\n \treturn tpgrp < 0 || tpgrp == getpgid(0);\n }\n \n-static int display(struct progress *progress, unsigned n, const char *done)\n+static int display(struct progress *progress, uint64_t n, const char *done)\n {\n \tconst char *eol, *tp;\n \n@@ -106,7 +106,7 @@ static int display(struct progress *progress, unsigned n, const char *done)\n \t\tif (percent != progress->last_percent || progress_update) {\n \t\t\tprogress->last_percent = percent;\n \t\t\tif (is_foreground_fd(fileno(stderr)) || done) {\n-\t\t\t\tfprintf(stderr, \"%s: %3u%% (%u/%u)%s%s\",\n+\t\t\t\tfprintf(stderr, \"%s: %3u%% (%\"PRIuMAX\"/%\"PRIuMAX\")%s%s\",\n \t\t\t\t\tprogress->title, percent, n,\n \t\t\t\t\tprogress->total, tp, eol);\n \t\t\t\tfflush(stderr);\n@@ -116,7 +116,7 @@ static int display(struct progress *progress, unsigned n, const char *done)\n \t\t}\n \t} else if (progress_update) {\n \t\tif (is_foreground_fd(fileno(stderr)) || done) {\n-\t\t\tfprintf(stderr, \"%s: %u%s%s\",\n+\t\t\tfprintf(stderr, \"%s: %\"PRIuMAX\"%s%s\",\n \t\t\t\tprogress->title, n, tp, eol);\n \t\t\tfflush(stderr);\n \t\t}\n@@ -127,7 +127,7 @@ static int display(struct progress *progress, unsigned n, const char *done)\n \treturn 0;\n }\n \n-static void throughput_string(struct strbuf *buf, off_t total,\n+static void throughput_string(struct strbuf *buf, uint64_t total,\n \t\t\t      unsigned int rate)\n {\n \tstrbuf_reset(buf);\n@@ -138,7 +138,7 @@ static void throughput_string(struct strbuf *buf, off_t total,\n \tstrbuf_addstr(buf, \"/s\");\n }\n \n-void display_throughput(struct progress *progress, off_t total)\n+void display_throughput(struct progress *progress, uint64_t total)\n {\n \tstruct throughput *tp;\n \tuint64_t now_ns;\n@@ -200,12 +200,12 @@ void display_throughput(struct progress *progress, off_t total)\n \t\tdisplay(progress, progress->last_value, NULL);\n }\n \n-int display_progress(struct progress *progress, unsigned n)\n+int display_progress(struct progress *progress, uint64_t n)\n {\n \treturn progress ? display(progress, n, NULL) : 0;\n }\n \n-static struct progress *start_progress_delay(const char *title, unsigned total,\n+static struct progress *start_progress_delay(const char *title, uint64_t total,\n \t\t\t\t\t     unsigned percent_threshold, unsigned delay)\n {\n \tstruct progress *progress = malloc(sizeof(*progress));\n@@ -227,12 +227,12 @@ static struct progress *start_progress_delay(const char *title, unsigned total,\n \treturn progress;\n }\n \n-struct progress *start_delayed_progress(const char *title, unsigned total)\n+struct progress *start_delayed_progress(const char *title, uint64_t total)\n {\n \treturn start_progress_delay(title, total, 0, 2);\n }\n \n-struct progress *start_progress(const char *title, unsigned total)\n+struct progress *start_progress(const char *title, uint64_t total)\n {\n \treturn start_progress_delay(title, total, 0, 0);\n }\ndiff --git a/progress.h b/progress.h\nindex 6392b63371..70a4d4a0d6 100644\n--- a/progress.h\n+++ b/progress.h\n@@ -3,10 +3,10 @@\n \n struct progress;\n \n-void display_throughput(struct progress *progress, off_t total);\n-int display_progress(struct progress *progress, unsigned n);\n-struct progress *start_progress(const char *title, unsigned total);\n-struct progress *start_delayed_progress(const char *title, unsigned total);\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_delayed_progress(const char *title, uint64_t total);\n void stop_progress(struct progress **progress);\n void stop_progress_msg(struct progress **progress, const char *msg);\n \n-- \n2.15.0.44.gf995e411c7\n\n"},{"id":"332443","messageId":"20171113201600.24878-5-newren@gmail.com","threadId":"47194","inReplyTo":"20171113201600.24878-1-newren@gmail.com","subject":"[PATCH v2 4/4] sequencer: show rename progress during cherry picks","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2017-11-13T20:16:00Z","receivedAt":"2017-11-13T20:16:23Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"When trying to cherry-pick a change that has lots of renames, it is\nsomewhat unsettling to wait a really long time without any feedback.\n\nSigned-off-by: Elijah Newren <newren@gmail.com>\n---\n sequencer.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/sequencer.c b/sequencer.c\nindex 2b4cecb617..247d93f363 100644\n--- a/sequencer.c\n+++ b/sequencer.c\n@@ -448,6 +448,7 @@ static int do_recursive_merge(struct commit *base, struct commit *next,\n \to.branch2 = next ? next_label : \"(empty tree)\";\n \tif (is_rebase_i(opts))\n \t\to.buffer_output = 2;\n+\to.show_rename_progress = 1;\n \n \thead_tree = parse_tree_indirect(head);\n \tnext_tree = next ? next->tree : empty_tree();\n-- \n2.15.0.44.gf995e411c7\n\n"},{"id":"332444","messageId":"20171113122834.20a69d1e87defe95d6e0e8ed@google.com","threadId":"47194","inReplyTo":"20171113201600.24878-3-newren@gmail.com","subject":"Re: [PATCH v2 2/4] progress: fix progress meters when dealing with lots of work","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-11-13T20:28:34Z","receivedAt":"2017-11-13T20:28:41Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Mon, 13 Nov 2017 12:15:58 -0800\nElijah Newren <newren@gmail.com> wrote:\n\n> The possibility of setting merge.renameLimit beyond 2^16 raises the\n> possibility that the values passed to progress can exceed 2^32.\n> Use uint64_t, because it \"ought to be enough for anybody\".  :-)\n> \n> Signed-off-by: Elijah Newren <newren@gmail.com>\n> ---\n> This does imply 64-bit math for all progress operations.  Possible alternatives\n> I could think of listed at\n> https://public-inbox.org/git/CABPp-BH1Cpc9UfYpmBBAHWSqadg=QuD=28qx1oV29ZdvF4NbJw@mail.gmail.com/\n> Opinions of others on whether 64-bit is okay, or preference for which alternative\n> is picked?\n\nI haven't looked into this in much detail, but another alternative to\nconsider is to use size_t everywhere. This also allows us to use st_add\nand st_mult, which checks overflow for us.\n\nChanging progress to use the size_t of the local machine makes sense to\nme.\n"},{"id":"332451","messageId":"20171113133316.c10bd360b4af10e572049443@google.com","threadId":"47194","inReplyTo":"20171113201600.24878-3-newren@gmail.com","subject":"Re: [PATCH v2 2/4] progress: fix progress meters when dealing with lots of work","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2017-11-13T21:33:16Z","receivedAt":"2017-11-13T21:33:28Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"On Mon, 13 Nov 2017 12:15:58 -0800\nElijah Newren <newren@gmail.com> wrote:\n\n> -static int display(struct progress *progress, unsigned n, const char *done)\n> +static int display(struct progress *progress, uint64_t n, const char *done)\n>  {\n>  \tconst char *eol, *tp;\n>  \n> @@ -106,7 +106,7 @@ static int display(struct progress *progress, unsigned n, const char *done)\n>  \t\tif (percent != progress->last_percent || progress_update) {\n>  \t\t\tprogress->last_percent = percent;\n>  \t\t\tif (is_foreground_fd(fileno(stderr)) || done) {\n> -\t\t\t\tfprintf(stderr, \"%s: %3u%% (%u/%u)%s%s\",\n> +\t\t\t\tfprintf(stderr, \"%s: %3u%% (%\"PRIuMAX\"/%\"PRIuMAX\")%s%s\",\n>  \t\t\t\t\tprogress->title, percent, n,\n>  \t\t\t\t\tprogress->total, tp, eol);\n\nI think it would be better to cast the appropriate arguments to\nuintmax_t - searching through the Git code shows that we do that in\nseveral situations. Same for the rest of the diff.\n"},{"id":"332460","messageId":"CABPp-BHhFq3C1t6TO2FMVT8=Bwf__cHhu2U-c+wd5zwHX-=9uQ@mail.gmail.com","threadId":"47194","inReplyTo":"20171113133316.c10bd360b4af10e572049443@google.com","subject":"Re: [PATCH v2 2/4] progress: fix progress meters when dealing with lots of work","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2017-11-13T22:26:44Z","receivedAt":"2017-11-13T22:26:53Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Thanks for the reviews!\n\nOn Mon, Nov 13, 2017 at 1:33 PM, Jonathan Tan <jonathantanmy@google.com> wrote:\n> On Mon, 13 Nov 2017 12:15:58 -0800\n> Elijah Newren <newren@gmail.com> wrote:\n>\n>> -static int display(struct progress *progress, unsigned n, const char *done)\n>> +static int display(struct progress *progress, uint64_t n, const char *done)\n>>  {\n>>       const char *eol, *tp;\n>>\n>> @@ -106,7 +106,7 @@ static int display(struct progress *progress, unsigned n, const char *done)\n>>               if (percent != progress->last_percent || progress_update) {\n>>                       progress->last_percent = percent;\n>>                       if (is_foreground_fd(fileno(stderr)) || done) {\n>> -                             fprintf(stderr, \"%s: %3u%% (%u/%u)%s%s\",\n>> +                             fprintf(stderr, \"%s: %3u%% (%\"PRIuMAX\"/%\"PRIuMAX\")%s%s\",\n>>                                       progress->title, percent, n,\n>>                                       progress->total, tp, eol);\n>\n> I think it would be better to cast the appropriate arguments to\n> uintmax_t - searching through the Git code shows that we do that in\n> several situations. Same for the rest of the diff.\n\nInteresting.  My first inclination was to ask why not just change the\nvariables to be of type uintmax_t instead of uint64_t (since we're\nalready changing their types already), and then get rid of the cast.\nBut I went digging through the source code based on your comment.\nAlmost all the existing examples in the codebase were off_t and size_t\nvalues; there was only one case with uint64_t...but that one case led\nme to commit 5be507fc95 (Use PRIuMAX instead of 'unsigned long long'\nin show-index 2007-10-21), and that commit does suggest doing exactly\nas you say here.\n\nI'll fix it up.\n"}]}