Re: [PATCH RFC 01/17] lib/crc: add crc32c_flip_range() for incremental CRC update

[Baokun Li <libaokun@linux.alibaba.com>]

在 2026/5/9 04:40, sashiko-bot@kernel.org 写道:
> Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
> - [High] Integer overflow in `bit_off + nbits` bypasses bounds checks, leading to out-of-bounds kernel memory reads.
> --
>
> commit 23c49b9c6860184b707e1c64499ef573ebaa8332
> Author: Baokun Li <libaokun@linux.alibaba.com>
>
> lib/crc: add crc32c_flip_range() for incremental CRC update
>
> This commit introduces crc32c_flip_range() to compute a CRC32c delta for
> flipped bits using precomputed GF(2) shift matrices. It gives O(log N)
> complexity for incremental updates, which is useful for situations like
> bitmap updates in filesystems.
>
>> diff --git a/lib/crc/crc32c-incr.c b/lib/crc/crc32c-incr.c
>> new file mode 100644
>> index 0000000000000..b6258231cc0df
>> --- /dev/null
>> +++ b/lib/crc/crc32c-incr.c
> [ ... ]
>> +u32 crc32c_flip_range(u32 old_crc, u32 total_bits,
>> +		      u32 bit_off, u32 nbits)
>> +{
>> +	u32 delta, trailing_bits;
>> +
>> +	if (!nbits)
>> +		return old_crc;
>> +
>> +	/*
>> +	 * total_bits must not exceed 2^INCR_MAX_ORDER bits (64KB).
>> +	 * bit_off + nbits must not exceed total_bits.
>> +	 */
>> +	if (WARN_ON_ONCE(total_bits > (1UL << INCR_MAX_ORDER)))
>> +		return old_crc;
>> +	if (WARN_ON_ONCE(bit_off + nbits > total_bits))
> Could this addition overflow since both bit_off and nbits are u32?
>
> If an external caller provides a very large nbits (such as 0xFFFFFFFF) and
> a small bit_off, their sum wraps around to a small value, which passes the
> greater-than total_bits check.
>
> If this occurs, the function proceeds to call crc32c_incr_get_ones_delta()
> with the large nbits value:
>
>> +		return old_crc;
>> +
>> +	trailing_bits = total_bits - (bit_off + nbits);
>> +
>> +	/* 1. Calculate CRC of the flip-mask (all 1s of length nbits) */
>> +	delta = crc32c_incr_get_ones_delta(nbits);
> Is it possible this leads to an out-of-bounds read?
>
> Looking at crc32c_incr_get_ones_delta(), passing a large nbits like
> 0xFFFFFFFF results in __fls(num_bits) evaluating to 31. This would be used
> to access indexes in crc32c_incr_ones_lookup[] (size 20) and
> crc32c_incr_nibble_table[] (size 19), reading past the end of the arrays.
>
> A bounds check like nbits > total_bits || bit_off > total_bits - nbits
> might prevent this overflow.
>
>
Indeed, I will fix this issue in the next version.

Thanks,
Baokun