{"thread":{"id":"10478","subject":"[PATCH 1/2] Fix ugly magic special case in exact rename detection","startedAt":"2007-10-26T23:51:28Z","lastAt":"2007-10-27T00:12:59Z","messageCount":3,"participants":["Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"57320","messageId":"alpine.LFD.0.999.0710261646230.30120@woody.linux-foundation.org","threadId":"10478","inReplyTo":null,"subject":"[PATCH 1/2] Fix ugly magic special case in exact rename detection","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-26T23:51:28Z","receivedAt":"2007-10-26T23:51:28Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFor historical reasons, the exact rename detection had populated the\nfilespecs for the entries it compared, and the rest of the similarity\nanalysis depended on that.  I hadn't even bothered to debug why that was\nthe case when I re-did the rename detection, I just made the new one\nhave the same broken behaviour, with a note about this special case.\n\nThis fixes that fixme.  The reason the exact rename detector needed to\nfill in the file sizes of the files it checked was that the _inexact_\nrename detector was broken, and started comparing file sizes before it\nfilled them in.\n\nFixing that allows the exact phase to do the sane thing of never even\ncaring (since all *it* cares about is really just the SHA1 itself, not\nthe size nor the contents).\n\nIt turns out that this also indirectly fixes a bug: trying to populate\nall the filespecs will run out of virtual memory if there is tons and\ntons of possible rename options.  The fuzzy similarity analysis does the\nright thing in this regard, and free's the blob info after it has\ngenerated the hash tables, so the special case code caused more trouble\nthan just some extra illogical code.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nWithout this, when I try to do a \"git commit --amend\" on my \nhorror-repository with the commit that moved around a hundred thousand \nfiles, I actually have \"git runstatus\" die() on me, because xmmap() fails \n(mmap() returns NULL due to running out of vm mappings).\n\nNot to mention that this is \"obviously correct\" (tm) and the \"right thing\" \n(tm)\" to do (famous last words). It's wrong of estimate_similarity() to \ntry to compare the sizes of the filespec entries before they have been \nfilled in, and it really shouldn't expect the exact rename detection to \nfill them in, since the exact rename detection doesn't even care!\n\n diffcore-rename.c |   27 ++++++++++++++-------------\n 1 files changed, 14 insertions(+), 13 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3946932..7ed5ef8 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -144,6 +144,20 @@ static int estimate_similarity(struct diff_filespec *src,\n \tif (!S_ISREG(src->mode) || !S_ISREG(dst->mode))\n \t\treturn 0;\n \n+\t/*\n+\t * Need to check that source and destination sizes are\n+\t * filled in before comparing them.\n+\t *\n+\t * If we already have \"cnt_data\" filled in, we know it's\n+\t * all good (avoid checking the size for zero, as that\n+\t * is a possible size - we really should have a flag to\n+\t * say whether the size is valid or not!)\n+\t */\n+\tif (!src->cnt_data && diff_populate_filespec(src, 0))\n+\t\treturn 0;\n+\tif (!dst->cnt_data && diff_populate_filespec(dst, 0))\n+\t\treturn 0;\n+\n \tmax_size = ((src->size > dst->size) ? src->size : dst->size);\n \tbase_size = ((src->size < dst->size) ? src->size : dst->size);\n \tdelta_size = max_size - base_size;\n@@ -159,11 +173,6 @@ static int estimate_similarity(struct diff_filespec *src,\n \tif (base_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)\n \t\treturn 0;\n \n-\tif ((!src->cnt_data && diff_populate_filespec(src, 0))\n-\t\t|| (!dst->cnt_data && diff_populate_filespec(dst, 0)))\n-\t\treturn 0; /* error but caught downstream */\n-\n-\n \tdelta_limit = (unsigned long)\n \t\t(base_size * (MAX_SCORE-minimum_score) / MAX_SCORE);\n \tif (diffcore_count_changes(src, dst,\n@@ -270,19 +279,11 @@ static int find_identical_files(struct file_similarity *src,\n \treturn renames;\n }\n \n-/*\n- * Note: the rest of the rename logic depends on this\n- * phase also populating all the filespecs for any\n- * entry that isn't matched up with an exact rename.\n- */\n static void free_similarity_list(struct file_similarity *p)\n {\n \twhile (p) {\n \t\tstruct file_similarity *entry = p;\n \t\tp = p->next;\n-\n-\t\t/* Stupid special case, see note above! */\n-\t\tdiff_populate_filespec(entry->filespec, 0);\n \t\tfree(entry);\n \t}\n }\n"},{"id":"57321","messageId":"alpine.LFD.0.999.0710261654300.30120@woody.linux-foundation.org","threadId":"10478","inReplyTo":"alpine.LFD.0.999.0710261646230.30120@woody.linux-foundation.org","subject":"[PATCH 2/2] Do the fuzzy rename detection limits with the exact renames removed","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-26T23:56:34Z","receivedAt":"2007-10-26T23:56:34Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nWhen we do the fuzzy rename detection, we don't care about the\ndestinations that we already handled with the exact rename detector.\nAnd, in fact, the code already knew that - but the rename limiter, which\nused to run *before* exact renames were detected, did not.\n\nThis fixes it so that the rename detection limiter now bases its\ndecisions on the *remaining* rename counts, rather than the original\nones.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nPretty obvious. It just moves the tests around a bit, and uses the updated \ncounters.\n\nWorks For Me(tm), although this isn't all that obviously testable (ie I \nshould find a test that is border-line, and triggers the rename detection \nlimits, but then has enough exact renames that the rename detection array \ngoes away).\n\n diffcore-rename.c |   32 ++++++++++++++++++--------------\n 1 files changed, 18 insertions(+), 14 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 7ed5ef8..f9ebea5 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -435,33 +435,37 @@ void diffcore_rename(struct diff_options *options)\n \t */\n \trename_count = find_exact_renames();\n \n+\t/* Did we only want exact renames? */\n+\tif (minimum_score == MAX_SCORE)\n+\t\tgoto cleanup;\n+\n+\t/*\n+\t * Calculate how many renames are left (but all the source\n+\t * files still remain as options for rename/copies!)\n+\t */\n+\tnum_create = (rename_dst_nr - rename_count);\n+\tnum_src = rename_src_nr;\n+\n+\t/* All done? */\n+\tif (!num_create)\n+\t\tgoto cleanup;\n+\n \t/*\n \t * This basically does a test for the rename matrix not\n \t * growing larger than a \"rename_limit\" square matrix, ie:\n \t *\n-\t *    rename_dst_nr * rename_src_nr > rename_limit * rename_limit\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 (rename_dst_nr > rename_limit && rename_src_nr > rename_limit)\n+\tif (num_create > rename_limit && num_src > rename_limit)\n \t\tgoto cleanup;\n-\tif (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)\n+\tif (num_create * num_src > rename_limit * rename_limit)\n \t\tgoto cleanup;\n \n-\t/* Have we run out the created file pool?  If so we can avoid\n-\t * doing the delta matrix altogether.\n-\t */\n-\tif (rename_count == rename_dst_nr)\n-\t\tgoto cleanup;\n-\n-\tif (minimum_score == MAX_SCORE)\n-\t\tgoto cleanup;\n-\n-\tnum_create = (rename_dst_nr - rename_count);\n-\tnum_src = rename_src_nr;\n \tmx = xmalloc(sizeof(*mx) * num_create * num_src);\n \tfor (dst_cnt = i = 0; i < rename_dst_nr; i++) {\n \t\tint base = dst_cnt * num_src;\n"},{"id":"57322","messageId":"alpine.LFD.0.999.0710261708520.30120@woody.linux-foundation.org","threadId":"10478","inReplyTo":"alpine.LFD.0.999.0710261654300.30120@woody.linux-foundation.org","subject":"Re: [PATCH 2/2] Do the fuzzy rename detection limits with the exact renames removed","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-10-27T00:12:59Z","receivedAt":"2007-10-27T00:12:59Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOn Fri, 26 Oct 2007, Linus Torvalds wrote:\n> \n> Works For Me(tm), although this isn't all that obviously testable (ie I \n> should find a test that is border-line, and triggers the rename detection \n> limits, but then has enough exact renames that the rename detection array \n> goes away).\n\nActually, I just tested it. I used that same 100,000 file thing, but added \none more (larger) file, and did another commit that moved the 100,000 \nfiles exactly, and the one larger file with a small change.\n\nThe code before this patch (but with my linear-time rename changes) would \nfind the 100,000 exact renames, but would *not* find the one that had a \nsmall change, because it would hit the rename limit, and wouldn't even \ntry.\n\nWith these two patches in place, it finds all the exact renames, and once \nit has done that, the resulting rename array is small enough (one single \nunknown target remaining, even if there are 100,001 possible source files) \nthat it doesn't trigger the rename limit, and it now finds the remaining \nnon-exact rename too.\n\nSo it not only looked obvious, it seems to work too.\n\n\t\tLinus\n"}]}