commit ecd91d96481c0f46cf268e51200b28e7d5d1d052
parent 4b688bcb7ea6b08369b6870d48185ebfc0ad76e5
Author: Thieu Le <thieule@chromium.org>
Date: Thu, 24 Sep 2020 16:46:19 +1000
bsdiff: Speed up pathological case
bsdiff does not properly handle the case where there is a large block of
data in the new file that only differs from the old file by less than 8
bytes. This causes bsdiff to continue searching through the files one
byte at a time and at each byte, re-compare the same large block of data
which leads to excessively long run times.
This fix checks for this edge condition and breaks out of the search
loop early. This retains the size efficiency of the patch file for most
binaries while preserving the runtime efficiency for files that fall
into this category.
Change-Id: If84ad928603c71297f4d0977405893345f39d5c3
Reviewed-on: http://gerrit.chromium.org/gerrit/2640
Reviewed-by: Andrew de los Reyes <adlr@chromium.org>
Tested-by: Thieu Le <thieule@chromium.org>
Diffstat:
1 file changed, 22 insertions(+), 0 deletions(-)
diff --git a/bsdiff.c b/bsdiff.c
@@ -149,7 +149,18 @@ main(int argc, char **argv)
while (scan < newsize) {
oldscore = 0;
+ /*
+ * If we come across a large block of data that only differs by
+ * less than 8 bytes, this loop takes a long time to go past it.
+ * Track the number of times we're stuck in the block and break
+ * out of it. */
+ int num_less_than_eight = 0;
+ off_t prev_len, prev_oldscore, prev_pos;
for (scsc = scan += len; scan < newsize; scan++) {
+ prev_len = len;
+ prev_oldscore = oldscore;
+ prev_pos = pos;
+
len = search(I, old, oldsize, new + scan,
newsize - scan, 0, oldsize, &pos);
@@ -165,6 +176,17 @@ main(int argc, char **argv)
if (scan + lastoffset < oldsize &&
old[scan + lastoffset] == new[scan])
oldscore--;
+
+ if (len == prev_len - 1 &&
+ oldscore == prev_oldscore - 1 &&
+ pos == prev_pos + 1 &&
+ len > oldscore &&
+ len <= oldscore + 8)
+ num_less_than_eight++;
+ else
+ num_less_than_eight = 0;
+ if (num_less_than_eight > 100)
+ break;
}
if (len != oldscore || scan == newsize) {