* Fix hash_search() duplicate-chain regression (#1115) and collision flood
When a hash chain contains > MAX_CHAIN_LEN identical colliding blocks
(such as 0x00 sparse regions colliding with 0xFF blocks at 64K/128K
block sizes), walking every duplicate entry exhausts MAX_CHAIN_LEN before
reaching valid matching blocks further down the chain (#1115).
Track the strong checksum of the last failed chain entry (last_false_sum2)
and unlink subsequent duplicate entries sharing the same strong checksum
(unless protected by SUMFLG_SAME_OFFSET in --inplace mode) so duplicates
are neither re-walked nor counted repeatedly against MAX_CHAIN_LEN.
Additionally, if 4 consecutive 1-byte rolling offsets experience a
weak-checksum collision where the entire chain fails to match, advance
offset by a full block rather than computing a full strong checksum on
every single byte.
* Split hash_search() collision tests and add boundary/--inplace coverage
Split testsuite/collision_test.py into two dedicated regression suites:
1. testsuite/hashsearch-dup-chain_test.py:
- Verifies forward chains (> MAX_CHAIN_LEN duplicates),
multi-group interleaved duplicate chains, and --inplace
SUMFLG_SAME_OFFSET preservation when mutating the chain after a
subsequent duplicate is overwritten on disk.
2. testsuite/hashsearch-collision-skip_test.py:
- Asserts explicit O(N/B) hash_hits CPU bounds and exact literal/matched
bandwidth bounds across skip boundaries (3, BLOCK, BLOCK+3, BLOCK+4,
2*BLOCK+3, 2*BLOCK+6, and 10*BLOCK+137) in both standard and
--inplace modes, and documents the bunched-perturbation hazard case.
* Unlink redundant SUMFLG_SAME_OFFSET duplicates in hash_search()
In --inplace mode, when > MAX_CHAIN_LEN identical basis blocks match
at their aligned offsets (such as 0x00 sparse runs), every matching
entry acquires SUMFLG_SAME_OFFSET. Skipping deduplication for all
SUMFLG_SAME_OFFSET entries left all pinned duplicates in the chain,
exhausting MAX_CHAIN_LEN, inflating false_alarms, and hiding valid
basis blocks behind them.
Track the flags of the entry that set last_false_sum2 (last_false_flags).
Once a SUMFLG_SAME_OFFSET entry has been retained as last_false_sum2,
unlink subsequent duplicate entries carrying SUMFLG_SAME_OFFSET as well,
while still preventing unpinned entries from unlinking a pinned entry.
Add Case 4 to testsuite/hashsearch-dup-chain_test.py to verify that
> MAX_CHAIN_LEN pinned duplicate blocks are unlinked and trailing valid
blocks behind them are matched with 0 extra literal bytes.
When updating_basis_file is active (--inplace), hash_search() advances
aligned_offset by s->blength and increments the 32-bit signed counter
aligned_i until aligned_offset catches up to offset.
If the source file is larger than 2 GiB and the peer supplies a small
s->blength and s->count, continuing to increment aligned_i past s->count
serves no purpose (as no basis blocks exist beyond s->count - 1) and can
overflow INT32_MAX into a negative index that bypasses the one-sided
aligned_i < s->count check.
Stop the catch-up loop once aligned_i reaches s->count so aligned_i
remains strictly within [0, s->count] and cannot overflow.
Reported-by: Mominul Islam Hemal <mominulislam-2021411216@cs.du.ac.bd>
Refuse malformed/hostile wire input that could crash or corrupt the receiver:
io.c (out-of-range file index, count*blength OFF_T overflow, read_args NUL room,
deferred in_multiplexed), flist.c (sub-flist after the final flist is freed,
FLAG_HLINKED on dirs / gated on preserve_hard_links, parent_ndx bound, cleared-
slot ndx in the transfer phase), hlink.c (undeclared cross-flist gnum -> error not
assert), match.c (clamp peer flength, re-check len before want_i), log.c (drop
peer-reachable asserts and F_SUM deref), exclude.c (merge-file recursion cap,
trailing-backslash heap fix), lib/pool_alloc.c (ASan redzone for pool underflow).
hash_search() walks the entire hash-table chain for the current rolling
checksum at every byte offset of the source file. Disk and VM images
contain large runs of identical blocks, so a single weak checksum
(get_checksum1) can collide thousands of times and pile every one of
those blocks onto one chain. When the sender then rolls across a region
whose weak checksum keeps landing on that chain without ever producing a
strong-checksum match, it re-walks the whole chain for every byte, giving
O(file_size * chain_length) behaviour. The result is rsync sitting at
100% CPU for hours with no apparent progress -- the long-standing "rsync
hangs on large files" reports.
Cap the number of same-weak-checksum candidates examined per offset at
MAX_CHAIN_LEN. Once the cap is hit we treat the offset as a non-match and
roll forward a byte; any block skipped this way is simply sent as literal
data, so the transferred result is always correct -- only the transfer
size is marginally affected. This is purely a sender-side search limit:
it changes no checksum, emitted byte, or protocol field, so a capped
sender interoperates with an unmodified receiver and vice versa.
On a synthetic 40000-block basis sharing one weak checksum, syncing a
60KB source dropped from ~18.4s to ~0.7s; the unbounded cost grows with
the square of the file size.
testsuite/hashsearch-chain_test.py reproduces the pathology with a tiny
basis of weak-checksum-colliding decoy blocks and asserts, via the
existing false_alarms counter (--debug=deltasum1), that the per-hash-hit
chain walk stays bounded. The assertion is exact and machine-independent
rather than timing-based.
- Put sum2_array into sum_struct to hold an array of sum2 checksums
that are each xfer_sum_len bytes.
- Remove sum2 buf from sum_buf.
- Add macro sum2_at() to access each sum2 array element.
- Throw an error if a sums header has an s2length larger than
xfer_sum_len.
- Size flist checksum data to hold the active size, not the max.
- Add a negotiated hash method to the daemon auth code.
- Use EVP for all openssl digests. This makes it easy to add more
openssl digest methods and avoids deprecation warnings.
- Support a way to re-enable deprecated digests via openssl conf
file and allow a default file to be configured.
- Supply a simple openssl-rsync.cnf file to enable legacy digests.
- All the memory-allocation macros now auto-check for failure and exit
with a failure message that incudes the caller's file and lineno
info. This includes strdup().
- Added the `--max-alloc=SIZE` option to be able to override the memory
allocator's sanity-check limit. It defaults to 1G (as before).
Fixes bugzilla bug 12769.
When checking a checksum that refers to a part of an --inplace file that
has been overwritten w/o getting SUMFLG_SAME_OFFSET set, we remove the
checksum from the list. This will speed up files that have a lot of
identical checksum blocks (e.g. sequences of zeros) that we can't use
due to them not getting marked as being the same. Patch provided by
Michael Chapman.
- Standardized the format of the opening comment, including adding a
brief description of what's in the file for those that lacked it.
- Added some missing copyright lines.
- Some minor whitespace tweaks (in a few of the files).
due to timing tests showing that the per-byte modulus calculation
slowed down regular sized files. Kept the other improvements
because they lessened our memory use and actually sped up the code.
Omar Elsayed