Re: [PATCH 1/3] diff histogram: intern strings

[Jeff King <peff@peff.net>]

On Fri, Nov 19, 2021 at 10:22:04PM +0100, Ævar Arnfjörð Bjarmason wrote:

> > Right, that makes more sense (and we are not likely to lift the 1GB
> > limit anytime soon; there are tons of 32-bit variables and potential
> > integer overflows all through the xdiff code).
> 
> Interestingly:
>     
>     $ du -sh 8gb*
>     8.1G    8gb
>     8.1G    8gb.cp
>     $ ~/g/git/git -P -c core.bigFileThreshold=10g diff -U0 --no-index --no-color-moved 2gb 2gb.cp
>     diff --git a/8gb b/8gb.cp
>     index a886cdfe5ce..4965a132d44 100644
>     --- a/8gb
>     +++ b/8gb.cp
>     @@ -17,0 +18 @@ more
>     +blah
> 
> And the only change I made was:
>     
>     diff --git a/xdiff-interface.c b/xdiff-interface.c
>     index 75b32aef51d..cb8ca5f5d0a 100644
>     --- a/xdiff-interface.c
>     +++ b/xdiff-interface.c
>     @@ -117,9 +117,6 @@ int xdi_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdemitconf_t co
>             mmfile_t a = *mf1;
>             mmfile_t b = *mf2;
>      
>     -       if (mf1->size > MAX_XDIFF_SIZE || mf2->size > MAX_XDIFF_SIZE)
>     -               return -1;
>     -
>             if (!xecfg->ctxlen && !(xecfg->flags & XDL_EMIT_FUNCCONTEXT))
>                     trim_common_tail(&a, &b);
> 
> Perhaps we're being overly concervative with these hardcoded limits, at
> least on some platforms? This is Linux x86_64.

It's been a couple of years since I looked, but I'm fairly certain there
are triggerable heap overflows. You probably need fewer than 2^31 lines,
but more than 2^30, as that will overflow the size computation of an
array whose elements are themselves 32-bit integers.

For instance, this:

  perl -e 'print "x\n" x (2**30 + 10)'  >gigaline
  cp gigaline gigaline.cp
  echo foo >>gigaline

results in:

  $ git.compile -c core.bigfilethreshold=10g --no-pager diff --no-index gigaline gigaline.cp
  fatal: Out of memory, malloc failed (tried to allocate 18446744056529682432 bytes)

so at some point we went negative with our allocation (and then it was
cast to size_t when we passed it xmalloc). There's probably a value
somewhere in the middle where it wraps but stays positive, and you'd get
a heap overflow.

> I understand from skimming the above that it's about the pathological
> case, these two files are the same except for a trailer at the end.

The real danger here is not producing a wrong answer for some dumb
cases, but introducing an exploitable heap overflow. Switching to
size_t, or at the very least using st_mult(), etc, everywhere in xdiff
would help. I looked at that long ago, but eventually decided it was
safer and less work to just stick the 1GB limit, since it practice
nobody really cares about diffing beyond that level. (And the limit is
really about number of lines, but 1GB of bytes is an easy proxy for
that).

It would be OK for somebody to fix it if they really want bigger diffs,
but I think it has to be done carefully.

-Peff