From: Junio C Hamano <hidden> Date: 2016-06-15 22:42:14
Nicolas Pitre [off-list ref] writes:
quoted
This is not just "diff". Our deltify code is half-broken, and
in the worst case this can corrupt our packs if an empty blob is
involved.
I would say involving an empty blob with deltas _is_ the bug in the
first place. Please don't let that happen.
Not all use of delta is to produce a pack. An empty->empty
delta is a valid two byte \0\0 sequence, and I do not see any
reason to forbid it. Although using such delta to represent
anything in a pack does *not* make any sense as you say, it
makes other callers simpler if they do not have to check if
from_len and to_len are empty before calling the delta code.
They care about from_len=0 (or to_len=0) case to produce similar
results as from_len=1 (or to_len=1) case and do not care at all
about the produced delta being a useful one for compressed
storage purposes.
Especially with pack files, an empty blob can be represented with a
_single_ byte. A delta must always be against something else and simply
storing the reference for the object the delta is against will always
use at least 20 bytes even for empty ones.
True, and the pack code is actually safe. It punts on NULL
return, so my initial worry about packs turns out to be
unneeded.
If my opinion is still of any weight I'd strongly vote for the former.
I ended up doing both ;-). The call site of diffcore-break was
certainly careless and broken (fixed); I've run git-grep to
check all callers to diff_delta() and the only one that did not
check the return value with NULL was the one that started with
thread.
I would say involving an empty blob with deltas _is_ the bug in the
first place. Please don't let that happen.
I agree with Nicolas.
Not all use of delta is to produce a pack. An empty->empty
delta is a valid two byte \0\0 sequence, and I do not see any
reason to forbid it. Although using such delta to represent
anything in a pack does *not* make any sense as you say, it
makes other callers simpler if they do not have to check if
from_len and to_len are empty before calling the delta code.
And you don't need to.
Do what pack-objects.c does: just call "diff_delta()" and check the result
for NULL. If the result is NULL, then you have to do some special code,
because that means that it's a full create or a full delete (or it's an
unchanged empty file). Regardless, it really _is_ a special case, and it
would be silly to generate a delta for it.
Linus
From: Junio C Hamano <hidden> Date: 2016-06-15 22:42:14
Linus Torvalds [off-list ref] writes:
Do what pack-objects.c does: just call "diff_delta()" and check the result
for NULL. If the result is NULL, then you have to do some special code,
because that means that it's a full create or a full delete (or it's an
unchanged empty file). Regardless, it really _is_ a special case, and it
would be silly to generate a delta for it.
When the result is NULL, it could be delta against empty, or
other failure in diff_delta() (could be it exceeded max_size,
could be it could not allocate memory, could be we introduced
some other failure modes later...).
I'll revert the changes anyway, but not because I necessarily
agree with you two. I am not 100% confident that the core of
the diff_delta code would work fine with empty input (it seems
to from my limited test), and I do not want to break things
unnecessarily at this point. More importantly, for the updated
delta code that allows empty input to work, the codepaths the
various existing callers that check with NULL must not be
assuming non-NULL return means non empty input -- otherwise my
change would subtly break things -- and I do not have enough
energy to verify that right now.
Since we do not break files smaller than MINIMUM_BREAK_SIZE,
this becomes a non-issue with the attached patch. I do not know
why I did not check both sides when I did it the first time; I
do not know why I was too stupid to notice that the earlier test
in the if() was far more expensive than the later one, either ;-).
-- >8 --
@@ -55,12 +55,6 @@ static int should_break(struct diff_file*isthedefault.*/-if(!S_ISREG(src->mode)||!S_ISREG(dst->mode))-return0;/* leave symlink rename alone */--if(diff_populate_filespec(src,0)||diff_populate_filespec(dst,0))-return0;/* error but caught downstream */-base_size=((src->size<dst->size)?src->size:dst->size);delta=diff_delta(src->data,src->size,
@@ -169,9 +163,15 @@ void diffcore_break(int break_score)if(DIFF_FILE_VALID(p->one)&&DIFF_FILE_VALID(p->two)&&!S_ISDIR(p->one->mode)&&!S_ISDIR(p->two->mode)&&!strcmp(p->one->path,p->two->path)){-if(should_break(p->one,p->two,-break_score,&score)&&-MINIMUM_BREAK_SIZE<=p->one->size){++if(S_ISREG(p->one->mode)&&+S_ISREG(p->two->mode)&&+!diff_populate_filespec(p->one,0)&&+MINIMUM_BREAK_SIZE<=p->one->size&&+!diff_populate_filespec(p->two,0)&&+MINIMUM_BREAK_SIZE<=p->two->size&&+should_break(p->one,p->two,+break_score,&score)){/* Split this into delete and create */structdiff_filespec*null_one,*null_two;structdiff_filepair*dp;
I'll revert the changes anyway, but not because I necessarily
agree with you two. I am not 100% confident that the core of
the diff_delta code would work fine with empty input (it seems
to from my limited test), and I do not want to break things
unnecessarily at this point.
Well, I checked the pack-objects.c side, and your patch to diff_delta()
should not hurt at least there. We already check the size and would have
broken out long before if either side was zero-sized.
But that's kind of part of the point - any user of diff_delta() is likely
to have checked the size anyway for other reasons. There's just very
seldom any valid reason to generate a delta against an empty file, there's
no interesting information that diff_delta() can really give us.
Basically, the binary diffs that diff-delta returns are interesting for
just two things:
- efficient packing, in the pack-objects.c style.
As mentioned, pack-objects.c needs to check the size heuristics before
doing diff_delta() _anyway_, for performance reasons as well as simply
because the secondary use of diff_delta() is to estimate how big the
delta is, and it's always pointless to generate a delta that is
guaranteed to be bigger than the file (which is always the case with
either side being an empty file - the size difference will inevitably
be bigger than the size of the resulting file).
- difference size estimation (ie for rename/copy detection)
This boils down to the same case as the secondary use of pack-objects,
ie delta size estimation. Again, if either side is empty, we _know_
that the delta generation is pointless, because the delta is always
going to be bigger than the end result, and thus it can't be sensible
for rename/copy detection.
So in one sense I actually agree with your patch: it makes the deltifier
code more generic and actually simplifies the diff_delta() code a bit by
avoiding one special case, and in that sense it's a good change.
So the reason I disagree with it is that doing the delta is always going
to be unnecessary work. And regardless of how we're ever going to use the
delta, we _know_ that it's unnecessary work.
So I think your diffcore-break.c patch is much more appropriate: it also
fixes the bug, but it fixes it by virtue of realizing that the delta
cannot matter and thus should never even be computed.
Now, your diff_setup() change may actually be worth it because of the
simplification, but on the other hand, you can also consider the NULL
return as being nice because it's effectively a way of saying "the delta
is meaningless, why did you even ask me?"
Linus
As mentioned, pack-objects.c needs to check the size heuristics before
doing diff_delta() _anyway_, for performance reasons as well as simply
because the secondary use of diff_delta() is to estimate how big the
delta is, and it's always pointless to generate a delta that is
guaranteed to be bigger than the file (which is always the case with
either side being an empty file - the size difference will inevitably
be bigger than the size of the resulting file).
Side note: this isn't technically entirely true. A binary diff that has a
source file that is empty could in theory be smaller than the destination
file simply because it may involve a certain amount of automatic
compression in the form of "insert 100 spaces" kind of diff encoding. I'm
not sure whether xdelta actually does something like that, but it's
certainly possible at least in theory.
Of course, even if the delta in such a case may be smaller than the
resulting file, such a delta is still not interesting: even from a packing
angle, if the resulting file has patterns that makes it easy to generate a
small delta against an empty file, the fact is, such a regular end result
will _compress_ better than the delta will, assuming any decent
compression mechanism.
So from a packing standpoint, generating the delta is still the wrong
thing to do - you're better off with just compressing the undeltified
result.
And from a similarity-estimation standpoint, going from an empty file to
anything else is also obviously not interesting either. An empty file
cannot be "similar" to anything else (except perhaps another empty file,
and even that is a matter of taste).
I just wanted to correct the technicality that delta's can certainly be
smaller than the result at least if the delta format allows for that kind
of encoding.
Linus
From: Nicolas Pitre <hidden> Date: 2016-06-15 22:42:14
On Mon, 12 Dec 2005, Linus Torvalds wrote:
On Mon, 12 Dec 2005, Linus Torvalds wrote:
quoted
As mentioned, pack-objects.c needs to check the size heuristics before
doing diff_delta() _anyway_, for performance reasons as well as simply
because the secondary use of diff_delta() is to estimate how big the
delta is, and it's always pointless to generate a delta that is
guaranteed to be bigger than the file (which is always the case with
either side being an empty file - the size difference will inevitably
be bigger than the size of the resulting file).
Side note: this isn't technically entirely true. A binary diff that has a
source file that is empty could in theory be smaller than the destination
file simply because it may involve a certain amount of automatic
compression in the form of "insert 100 spaces" kind of diff encoding. I'm
not sure whether xdelta actually does something like that, but it's
certainly possible at least in theory.
xdelta doesn't. It only has two functions currently:
1) copy x bytes from offset y in source file to current position in
destination file;
2) paste the x following bytes straight from the delta stream to
current position into the destination file.
Of course in the GIT context files are buffers.
However I added the possibility for (1) to use the destination file as
well as the "source" file for block copy in patch_delta(). However
diff_delta() currently doesn't use that capability. But if it did then
the "insert 100 spaces" would be:
- paste \x20\x20\x20\x20 to dest
(delta = 5 bytes, dest = 4 bytes)
- copy 4 bytes from offset 0 of dest to dest
(delta = 7 bytes, dest = 8 bytes)
- copy 8 bytes from offset 0 of dest to dest
(delta = 9 bytes, dest = 16 bytes)
- copy 16 bytes from offset 0 of dest to dest
(delta = 11 bytes, dest = 32 bytes)
- copy 32 bytes from offset 0 of dest to dest
(delta = 13 bytes, dest = 64 bytes)
- copy 36 bytes from offset 0 of dest to dest
(delta = 15 bytes, dest = 100 bytes)
And yet that could be optimized further with a better size for the
initial paste. However adding that capability to diff_delta() might
make it significantly slower for still unknown gain for real life data.
But I should write the code some day.
Nicolas