]> git.ipfire.org Git - thirdparty/squid.git/commit - src/SquidMath.h
Fix Sum() by replacing it with a safer NaturalSum() (#869)
authorAlex Rousskov <rousskov@measurement-factory.com>
Thu, 24 Feb 2022 02:17:14 +0000 (02:17 +0000)
committerSquid Anubis <squid-anubis@squid-cache.org>
Thu, 24 Feb 2022 02:47:09 +0000 (02:47 +0000)
commitb308d7e2ad02ae6622f380d94d2303446f5831a9
tree0f388ffc885e779fc24ad3af6c0a6bb8aeea81c9
parentf70cf39b14872dddac2e14c2858bded78429150a
Fix Sum() by replacing it with a safer NaturalSum() (#869)

While testing future cache entry expiration computation code, we found a
Sum() bug: Sum(0l, -1lu) returns -1 instead of overflowing (long cannot
hold the maximum unsigned long value). This discovery triggered an
investigation that discovered several Sum() flaws, even inside the
supposed-to-be-trivial implementation branch for unsigned operands:

0. AllUnsigned-based optimization path selection was based on the
   detection of unsigned raw S and T types, but the actual s+t sum
   used integral-promoted types that could be signed!

1. "sizeof(T) >= sizeof(U)" assertion missed that same-size types have
   very different maximums when exactly one of the types is signed.

2. "auto sum = a + b" assignment missed that "auto" may be bigger than
   the return type "T" and, hence, the sum may not overflow when it does
   not fit T. The overflow would go undetected and the result will be
   truncated (to fit T) in the return statement. This automatic sum type
   enlargement may be due to signed->unsigned integral conversion
   related to the previous bullet, but it can also happen because of
   integral _promotions_ (e.g., those that convert "char" into "int").

3. Sum() silently truncated its arguments to fit T. Before commit
   1fba9ab, that silent truncation only applied to the first argument
   (if T did not match its actual type). After that commit, all other
   arguments could be silently truncated (except the last one).

4. It is trivial for the caller to do everything right when calling
   Sum() but then assign the result to a variable that cannot hold Sum()
   value, essentially undoing all the overflow detection work.

Fortunately, none of these bugs affected two existing Sum() callers.

Some of these problems were very difficult to fix! Eventually, a new,
simplified concept emerged that was easier to implement and that was a
better match for Squid current and foreseeable needs: NaturalSum().

NaturalSum() is designed for cases where we want an exact sum of
arguments but do not consider negative arguments as valid numbers. This
both simplifies the implementation and protects typical callers from
adding "-1" (e.g., a special "no delay" option setting) to "3600" (e.g.,
configured TTL) and getting a meaningless result of 3599.

NaturalSum() requires the caller to specify the summation type that will
be used to accumulate the sum value as Squid iterates over arguments.
Sum() wanted to automatically use the largest type that can accommodate
(partial) sums, but that complicated task was not implemented and
becomes unnecessary when dealing with only natural numbers -- there is
no need to temporary inflate the partial sum (beyond what the resulting
type can hold) in case some negative operand will decrease it later.

Also added SetToNaturalSumOrMax() to allow the caller to reset a
variable without guessing its type, avoiding silent sum truncation at
assignment time.

Also added unit test cases.
src/Makefile.am
src/SquidMath.h
src/base/ClpMap.h
src/tests/testMath.cc [new file with mode: 0644]