{"thread":{"id":"48921","subject":"[PATCH 0/3] histogram diff: Fix memory ballooning in corner case","startedAt":"2018-07-19T18:56:26Z","lastAt":"2018-07-19T22:19:47Z","messageCount":5,"participants":["Stefan Beller"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"353062","messageId":"20180719185620.124768-1-sbeller@google.com","threadId":"48921","inReplyTo":null,"subject":"[PATCH 0/3] histogram diff: Fix memory ballooning in corner case","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-19T18:56:17Z","receivedAt":"2018-07-19T18:56:26Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Currently if you run\n\n    seq 1   100000 >one\n    seq 1 4 100000 >two\n    git diff --no-index --histogram one two\n\nyou might run into memory issues. After applying the last patch of this series\nyou only have to wait a bit (as it doesn't fix run time complexity), but\ncomputes the result with less memory pressure.\n\nThanks,\nStefan\n\nStefan Beller (3):\n  xdiff/xhistogram: pass arguments directly to fall_back_to_classic_diff\n  xdiff/xhistogram: factor out memory cleanup into free_index()\n  xdiff/xhistogram: move index allocation into find_lcs\n\n xdiff/xhistogram.c | 117 +++++++++++++++++++++++++--------------------\n 1 file changed, 66 insertions(+), 51 deletions(-)\n\n-- \n2.18.0.233.g985f88cf7e-goog\n\n"},{"id":"353063","messageId":"20180719185620.124768-2-sbeller@google.com","threadId":"48921","inReplyTo":"20180719185620.124768-1-sbeller@google.com","subject":"[PATCH 1/3] xdiff/xhistogram: pass arguments directly to fall_back_to_classic_diff","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-19T18:56:18Z","receivedAt":"2018-07-19T18:56:29Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"By passing the 'xpp' and 'env' argument directly to the function\n'fall_back_to_classic_diff', we eliminate an occurrence of the 'index'\nin histogram_diff, which will prove useful in a bit.\n\nWhile at it, move it up in the file. This will make the diff of\none of the next patches more legible.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n xdiff/xhistogram.c | 22 +++++++++++-----------\n 1 file changed, 11 insertions(+), 11 deletions(-)\n\ndiff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\nindex 73210cb6f3f..6e20f75fe85 100644\n--- a/xdiff/xhistogram.c\n+++ b/xdiff/xhistogram.c\n@@ -233,6 +233,16 @@ static int try_lcs(struct histindex *index, struct region *lcs, int b_ptr,\n \treturn b_next;\n }\n \n+static int fall_back_to_classic_diff(xpparam_t const *xpp, xdfenv_t *env,\n+\t\tint line1, int count1, int line2, int count2)\n+{\n+\txpparam_t xpparam;\n+\txpparam.flags = xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;\n+\n+\treturn xdl_fall_back_diff(env, &xpparam,\n+\t\t\t\t  line1, count1, line2, count2);\n+}\n+\n static int find_lcs(struct histindex *index, struct region *lcs,\n \tint line1, int count1, int line2, int count2) {\n \tint b_ptr;\n@@ -248,16 +258,6 @@ static int find_lcs(struct histindex *index, struct region *lcs,\n \treturn index->has_common && index->max_chain_length < index->cnt;\n }\n \n-static int fall_back_to_classic_diff(struct histindex *index,\n-\t\tint line1, int count1, int line2, int count2)\n-{\n-\txpparam_t xpp;\n-\txpp.flags = index->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;\n-\n-\treturn xdl_fall_back_diff(index->env, &xpp,\n-\t\t\t\t  line1, count1, line2, count2);\n-}\n-\n static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n \tint line1, int count1, int line2, int count2)\n {\n@@ -320,7 +320,7 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n \n \tmemset(&lcs, 0, sizeof(lcs));\n \tif (find_lcs(&index, &lcs, line1, count1, line2, count2))\n-\t\tresult = fall_back_to_classic_diff(&index, line1, count1, line2, count2);\n+\t\tresult = fall_back_to_classic_diff(xpp, env, line1, count1, line2, count2);\n \telse {\n \t\tif (lcs.begin1 == 0 && lcs.begin2 == 0) {\n \t\t\twhile (count1--)\n-- \n2.18.0.233.g985f88cf7e-goog\n\n"},{"id":"353064","messageId":"20180719185620.124768-3-sbeller@google.com","threadId":"48921","inReplyTo":"20180719185620.124768-1-sbeller@google.com","subject":"[PATCH 2/3] xdiff/xhistogram: factor out memory cleanup into free_index()","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-19T18:56:19Z","receivedAt":"2018-07-19T18:56:31Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"This will be useful in the next patch as we'll introduce multiple\ncallers.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n xdiff/xhistogram.c | 13 +++++++++----\n 1 file changed, 9 insertions(+), 4 deletions(-)\n\ndiff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\nindex 6e20f75fe85..5098b6c5021 100644\n--- a/xdiff/xhistogram.c\n+++ b/xdiff/xhistogram.c\n@@ -243,6 +243,14 @@ static int fall_back_to_classic_diff(xpparam_t const *xpp, xdfenv_t *env,\n \t\t\t\t  line1, count1, line2, count2);\n }\n \n+static inline void free_index(struct histindex *index)\n+{\n+\txdl_free(index->records);\n+\txdl_free(index->line_map);\n+\txdl_free(index->next_ptrs);\n+\txdl_cha_free(&index->rcha);\n+}\n+\n static int find_lcs(struct histindex *index, struct region *lcs,\n \tint line1, int count1, int line2, int count2) {\n \tint b_ptr;\n@@ -343,10 +351,7 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n \t}\n \n cleanup:\n-\txdl_free(index.records);\n-\txdl_free(index.line_map);\n-\txdl_free(index.next_ptrs);\n-\txdl_cha_free(&index.rcha);\n+\tfree_index(&index);\n \n \treturn result;\n }\n-- \n2.18.0.233.g985f88cf7e-goog\n\n"},{"id":"353065","messageId":"20180719185620.124768-4-sbeller@google.com","threadId":"48921","inReplyTo":"20180719185620.124768-1-sbeller@google.com","subject":"[PATCH 3/3] xdiff/xhistogram: move index allocation into find_lcs","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-19T18:56:20Z","receivedAt":"2018-07-19T18:56:34Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"This fixes a memory issue when recursing a lot, which can be reproduced as\n\n    seq 1   100000 >one\n    seq 1 4 100000 >two\n    git diff --no-index --histogram one two\n\nBefore this patch, histogram_diff would call itself recursively before\ncalling free_index, which would mean a lot of memory is allocated during\nthe recursion and only freed afterwards. By moving the memory allocation\n(and its free call) into find_lcs, the memory is free'd before we recurse,\nsuch that memory is reused in the next step of the recursion instead of\nusing new memory.\n\nThis addresses only the memory pressure, not the run time complexity,\nthat is also awful for the corner case outlined above.\n\nHelpful in understanding the code (in addition to the sparse history of\nthis file), was https://stackoverflow.com/a/32367597 which reproduces\nmost of the code comments of the JGit implementation.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n xdiff/xhistogram.c | 96 +++++++++++++++++++++++++---------------------\n 1 file changed, 53 insertions(+), 43 deletions(-)\n\ndiff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\nindex 5098b6c5021..fc2d3cd95d9 100644\n--- a/xdiff/xhistogram.c\n+++ b/xdiff/xhistogram.c\n@@ -251,44 +251,13 @@ static inline void free_index(struct histindex *index)\n \txdl_cha_free(&index->rcha);\n }\n \n-static int find_lcs(struct histindex *index, struct region *lcs,\n-\tint line1, int count1, int line2, int count2) {\n-\tint b_ptr;\n-\n-\tif (scanA(index, line1, count1))\n-\t\treturn -1;\n-\n-\tindex->cnt = index->max_chain_length + 1;\n-\n-\tfor (b_ptr = line2; b_ptr <= LINE_END(2); )\n-\t\tb_ptr = try_lcs(index, lcs, b_ptr, line1, count1, line2, count2);\n-\n-\treturn index->has_common && index->max_chain_length < index->cnt;\n-}\n-\n-static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n-\tint line1, int count1, int line2, int count2)\n+static int find_lcs(xpparam_t const *xpp, xdfenv_t *env,\n+\t\t    struct region *lcs,\n+\t\t    int line1, int count1, int line2, int count2)\n {\n+\tint b_ptr;\n+\tint sz, ret = -1;\n \tstruct histindex index;\n-\tstruct region lcs;\n-\tint sz;\n-\tint result = -1;\n-\n-\tif (count1 <= 0 && count2 <= 0)\n-\t\treturn 0;\n-\n-\tif (LINE_END(1) >= MAX_PTR)\n-\t\treturn -1;\n-\n-\tif (!count1) {\n-\t\twhile(count2--)\n-\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n-\t\treturn 0;\n-\t} else if (!count2) {\n-\t\twhile(count1--)\n-\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n-\t\treturn 0;\n-\t}\n \n \tmemset(&index, 0, sizeof(index));\n \n@@ -326,8 +295,52 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n \tindex.ptr_shift = line1;\n \tindex.max_chain_length = 64;\n \n+\tif (scanA(&index, line1, count1))\n+\t\tgoto cleanup;\n+\n+\tindex.cnt = index.max_chain_length + 1;\n+\n+\tfor (b_ptr = line2; b_ptr <= LINE_END(2); )\n+\t\tb_ptr = try_lcs(&index, lcs, b_ptr, line1, count1, line2, count2);\n+\n+\tif (index.has_common && index.max_chain_length < index.cnt)\n+\t\tret = 1;\n+\telse\n+\t\tret = 0;\n+\n+cleanup:\n+\tfree_index(&index);\n+\treturn ret;\n+}\n+\n+static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n+\tint line1, int count1, int line2, int count2)\n+{\n+\tstruct region lcs;\n+\tint lcs_found;\n+\tint result = -1;\n+\n+\tif (count1 <= 0 && count2 <= 0)\n+\t\treturn 0;\n+\n+\tif (LINE_END(1) >= MAX_PTR)\n+\t\treturn -1;\n+\n+\tif (!count1) {\n+\t\twhile(count2--)\n+\t\t\tenv->xdf2.rchg[line2++ - 1] = 1;\n+\t\treturn 0;\n+\t} else if (!count2) {\n+\t\twhile(count1--)\n+\t\t\tenv->xdf1.rchg[line1++ - 1] = 1;\n+\t\treturn 0;\n+\t}\n+\n \tmemset(&lcs, 0, sizeof(lcs));\n-\tif (find_lcs(&index, &lcs, line1, count1, line2, count2))\n+\tlcs_found = find_lcs(xpp, env, &lcs, line1, count1, line2, count2);\n+\tif (lcs_found < 0)\n+\t\tgoto out;\n+\telse if (lcs_found)\n \t\tresult = fall_back_to_classic_diff(xpp, env, line1, count1, line2, count2);\n \telse {\n \t\tif (lcs.begin1 == 0 && lcs.begin2 == 0) {\n@@ -341,18 +354,15 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n \t\t\t\t\t\tline1, lcs.begin1 - line1,\n \t\t\t\t\t\tline2, lcs.begin2 - line2);\n \t\t\tif (result)\n-\t\t\t\tgoto cleanup;\n+\t\t\t\tgoto out;\n \t\t\tresult = histogram_diff(xpp, env,\n \t\t\t\t\t\tlcs.end1 + 1, LINE_END(1) - lcs.end1,\n \t\t\t\t\t\tlcs.end2 + 1, LINE_END(2) - lcs.end2);\n \t\t\tif (result)\n-\t\t\t\tgoto cleanup;\n+\t\t\t\tgoto out;\n \t\t}\n \t}\n-\n-cleanup:\n-\tfree_index(&index);\n-\n+out:\n \treturn result;\n }\n \n-- \n2.18.0.233.g985f88cf7e-goog\n\n"},{"id":"353094","messageId":"20180719221942.179565-1-sbeller@google.com","threadId":"48921","inReplyTo":"20180719185620.124768-4-sbeller@google.com","subject":"[PATCH] xdiff/histogram: remove tail recursion","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-19T22:19:42Z","receivedAt":"2018-07-19T22:19:47Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"When running the same reproduction script as the previous patch,\nit turns out the stack is too small, which can be easily avoided.\n\nSigned-off-by: Stefan Beller <sbeller@google.com>\n---\n xdiff/xhistogram.c | 20 ++++++++++++++------\n 1 file changed, 14 insertions(+), 6 deletions(-)\n\ndiff --git a/xdiff/xhistogram.c b/xdiff/xhistogram.c\nindex fc2d3cd95d9..ec85f5992bd 100644\n--- a/xdiff/xhistogram.c\n+++ b/xdiff/xhistogram.c\n@@ -318,7 +318,9 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n {\n \tstruct region lcs;\n \tint lcs_found;\n-\tint result = -1;\n+\tint result;\n+redo:\n+\tresult = -1;\n \n \tif (count1 <= 0 && count2 <= 0)\n \t\treturn 0;\n@@ -355,11 +357,17 @@ static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,\n \t\t\t\t\t\tline2, lcs.begin2 - line2);\n \t\t\tif (result)\n \t\t\t\tgoto out;\n-\t\t\tresult = histogram_diff(xpp, env,\n-\t\t\t\t\t\tlcs.end1 + 1, LINE_END(1) - lcs.end1,\n-\t\t\t\t\t\tlcs.end2 + 1, LINE_END(2) - lcs.end2);\n-\t\t\tif (result)\n-\t\t\t\tgoto out;\n+\t\t\t/*\n+\t\t\t * result = histogram_diff(xpp, env,\n+\t\t\t *            lcs.end1 + 1, LINE_END(1) - lcs.end1,\n+\t\t\t *            lcs.end2 + 1, LINE_END(2) - lcs.end2);\n+\t\t\t * but let's optimize tail recursion ourself:\n+\t\t\t*/\n+\t\t\tcount1 = LINE_END(1) - lcs.end1;\n+\t\t\tline1 = lcs.end1 + 1;\n+\t\t\tcount2 = LINE_END(2) - lcs.end2;\n+\t\t\tline2 = lcs.end2 + 1;\n+\t\t\tgoto redo;\n \t\t}\n \t}\n out:\n-- \n2.18.0.233.g985f88cf7e-goog\n\n"}]}