patch, 4 partsRemove silent clamp of renameLimit

In a repo with around 60k files with deep directory hierarchies (due to being predominantly java code) and which had a few high level directories moved around (making it appear to git as dozens of thousands of individual file renames), attempts to cherry-pick commits across product versions resulted in non-sensical delete/modify conflicts (rather than rename/modify as expected). We had a few teams who were in the unenviable position of having to backport hundreds or thousands of commits across such product versions, and the result was months of pain, which could have been alleviated were it not for a few small git bugs:

  * When you try to cherry-pick changes, unlike when you merge two
    branches, git will not notify you when you need to set a higher
    merge.renameLimit.

  * If you know git internals well enough, you can try to trick git into
    telling you the correct renameLimit by doing a merge instead of a
    cherry-pick.  If you do that, and have a renameLimit that is too
    small, git will let you know the value you need.  You can then undo
    the merge and proceed with the cherry-pick.  Except that...

  * If you are performing a merge and specify a large renameLimit that
    isn't large enough, and the necessary renameLimit you need is greater
    than 32767, then git tells you nothing, leading you to believe that
    the limit you specified is high enough, but only to watch it still
    mess up the merge badly.

  * If you happen to specify a merge.renameLimit that *is* high enough,
    but just happens to be greater than 32767, then git will silently
    pretend you specified 32767, determine that 32767 is not high enough,
    not tell you anything about it's silent clamping, and then proceed to
    mess up the merge or cherry-pick badly.  Not only do you get no
    feedback, the clamping to 32767 isn't documented anywhere even if you
    tried to read every manual page.

Folks did discover the merge.renameLimit and tried setting it to various values, spread over the spectrum from 1000 (the default) up to 999999999 (or maybe more, that's just the highest number I heard), completely unaware that most their attempts were ignored and wondering why git couldn't handle things and couldn't explain why either.

Eventually folks wrote scripts that would run the output of format-patch through a bunch of sed commands to pretend patches were against the filename on the other side of history and then pipe back through git-am. Such scripts grew as more and more rename rules were added.

I eventually learned of one of these scripts and said something close to, "You don't need these pile of rename rules; just set merge.renameLimit to something higher." When they responded that merge.renameLimit didn't work, I didn't believe them. This patch series, along with two others that I will be sending shortly, represent my attempt to continue to not believe them. :-)

Elijah Newren (4):
  sequencer: Warn when internal merge may be suboptimal due to
    renameLimit
  Remove silent clamp of renameLimit
  progress: Fix progress meters when dealing with lots of work
  sequencer: Show rename progress during cherry picks

 diff.c            |  2 +-
 diffcore-rename.c | 15 ++++++---------
 progress.c        | 22 +++++++++++-----------
 progress.h        |  8 ++++----
 sequencer.c       |  2 ++
 5 files changed, 24 insertions(+), 25 deletions(-)

In commit 0024a5492 (Fix the rename detection limit checking; 2007-09-14), the renameLimit was clamped to 32767. This appears to have been to simply avoid integer overflow in the following computation:

   num_create * num_src <= rename_limit * rename_limit

although it also could be viewed as a hardcoded bound on the amount of CPU time we're willing to allow users to tell git to spend on handling renames. An upper bound may make sense, particularly as the computation is O(rename_limit^2), but only if the bound is documented and communicated to the user -- neither of which were true.

In fact, the silent clamping of the renameLimit to a smaller value and lack of reporting of the needed renameLimit when it was too large made it appear to the user as though they had used a high enough value; however, git would proceed to mess up the merge or cherry-pick badly based on the lack of rename detection. Some hardy folks, despite the lack of feedback on the correct limit to choose, were desperate enough to repeatedly retry their cherry-picks with increasingly larger renameLimit values (going orders of magnitude beyond the built-in limit of 32767), but were consistently met with the same failure.

Although large limits can make things slow, we have users who would be ecstatic to have a small five file change be correctly cherry picked even if they have to manually specify a large limit and it took git ten minutes to compute it.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 diff.c            |  2 +-
 diffcore-rename.c | 11 ++++-------
 2 files changed, 5 insertions(+), 8 deletions(-)

On Fri, Nov 10, 2017 at 9:39 AM, Elijah Newren <newren@gmail.com> wrote:

From a technical perspective, I would think that if (num_create <= rename_limit || num_src <= rename_limit) holds true, that the double-cast condition would also be always true? Could we just remove that last check?

Or phrased differently, if we can cast to double and extend the check here, do we have to adapt code at other places as well?

Thanks for taking a look!

On Fri, Nov 10, 2017 at 10:26 AM, Stefan Beller <sbeller@google.com> wrote: <snip>

Not necessarily. For example, if num_create = rename_limit-1 and num_src = rename_limit+2, then the first condition will be satisfied but the second won't. If it was && rather than ||, then the second condition would be superfluous.

Good point, and yes. Perhaps I should have re-ordered my patch series because I came back to it later and realized that the progress code was broken due to overflow/wraparound, and a patch 3 fixed that.

Further, the later patch used uint64_t instead of double. While double works, perhaps I should change the double here to uint64_t for consistency?

On Fri, Nov 10, 2017 at 10:36:17AM -0800, Elijah Newren wrote:

I'm wondering if maybe you want to use size_t. If you end up using an unsigned type, you might be able to leverage unsigned_mult_overflows to avoid having to write this by hand.

Hi,

On Fri, Nov 10, 2017 at 3:42 PM, brian m. carlson <sandals@crustytoothpaste.net> wrote:

<snip>

Thanks for pointing out unsigned_mult_overflows; I was unaware of it. I think I'd prefer to not use it though; the fact that I had a case that genuinely needed a value greater than 2^31 (at least before my performance patches) meant that a slightly bigger repo is going to eventually need a value over 2^32, so I think we should just cast to a type that can hold it.

I'm curious why you suggest size_t, though. I have always associated that with an amount of memory that will be used, and there's no allocation based on this result. Was I wrong to make that association, or is there another good reason here?

On Sat, Nov 11, 2017 at 08:39:11AM -0800, Elijah Newren wrote:

That's fine. I had considered this in the context of 64-bit values, but I suppose that the likelihood of us hitting 2**64 iterations (and performing reasonably as well) is unlikely.

I usually like size_t for values that are unsigned and don't need to be fixed size because it's usually the largest efficient unsigned type. However, if you want something to handle items larger than 2**32, then I agree that it's maybe not a great idea if we want it to work on 32-bit systems.

The possibility of setting merge.renameLimit beyond 2^16 raises the possibility that the values passed to progress can exceed 2^32. For my usecase of interest, I only needed to pass a value a little over 2^31. If I were only interested in fixing my usecase, I could have simply changed last_value from int to unsigned, and casted each of rename_dst_nr and rename_src_nr (in merge-recursive.c) from int to unsigned just before multiplying them. However, as long as we're making changes to allow larger progress meters, we may as well make a little more room in general. Use uint64_t, because it "ought to be enough for anybody". :-)

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 diffcore-rename.c |  4 ++--
 progress.c        | 22 +++++++++++-----------
 progress.h        |  8 ++++----
 3 files changed, 17 insertions(+), 17 deletions(-)

Elijah Newren <newren@gmail.com> writes:

Style: s/Fix/fix/;

The middle part of the log message may waste more mental bandwidth of readers than it is worth. It might have gave you satisfaction to be able to vent, but don't (the place to do so is after the three dash lines).

I am not sure if we want all codepaths to do 64-bit math for progress meter, but let's see what others would think.

Are these (and there are probably other instances in this patch) %lu correct?

Thanks for the reviews and suggestions!

On Sun, Nov 12, 2017 at 9:24 PM, Junio C Hamano <gitster@pobox.com> wrote:

I also messed this up in a lot of my patches in my other patch series. I've fixed them all up, but I'll wait to resubmit those other series until I get some other reviews.

Cleaned it up, along with the other commit message you pointed out; I'll resubmit shortly.

If others don't want to do 64-bit math for the progress meter, what
would they like to see done instead?  I can see a few options:
  1) Have two separate progress codepaths, one for 32-bith math and
one for 64-bit math.
  2) Instead of counting pairs of source/dest files compared, just
count number of dest paths completed.  (Thus, we wouldn't need a value
big enough to hold rename_dst_nr * rename_src_nr, just big enough to
hold rename_dst_nr).
  3) just let the progress meter overflow and show nonsensical values
  4) don't show the progress meter if overflow would happen
  5) something else I'm not thinking of.

Oops, no. I think %llu is right, though looking around the code it appears folks use PRIuMAX and avoid %llu due to possible issues with old windows compilers. Not sure if that's still relevant, but I'll try to remain consistent with what I see elsewhere and include that fix in my re-roll.

Elijah Newren <newren@gmail.com> writes:

This sounds like the most sensible thing to do even if we do switch to larger integer size, but that is orthogonal to the main point of this series.

Having renamed files silently treated as deleted/modified conflicts instead of correctly resolving the renamed/modified case has caused lots of pain for some users. Eventually, some of them figured out to set merge.renameLimit to something higher, but without feedback about what value it should have, they were just repeatedly guessing and retrying.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 sequencer.c | 1 +
 1 file changed, 1 insertion(+)

Elijah Newren <newren@gmail.com> writes:

Style: please downcase s/Warn/warn/ to fit this better in "shortlog --no-merges"
output.

It would have been _much_ easier to read if you refrained from stating the gripes more prominently than the source of the gripe that you are fixing. E.g.

	If one side of a merge have renamed more paths than
	merge.renamelimit since the sides diverged, the recursive
	merge strategy stops detecting renames and instead leaves
	these many paths as delete/modify conflicts, without warning
	what is going on and giving hints on how to tell Git that it
	is allowed to spend more cycles to detect renames.

perhaps.

The addition of a call to diff_warn_rename_limit looks quite sensible.

Thanks.

When trying to cherry-pick a change that has lots of renames, it is somewhat unsettling to wait a really long time without any feedback.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 sequencer.c | 1 +
 1 file changed, 1 insertion(+)

Elijah Newren <newren@gmail.com> writes:

Style: s/Show/show/

Makes sense.