#32 6.4.2 and 7.0.0 `HashFact` multiplied a bit-field in `int`

[Batch Job 1]

HashFact multiplied a bit-field in int

What happened. Asserting an ordinary fact performed a signed integer overflow.

(deftemplate person (slot name) (slot age))
(assert (person (name alice) (age 30)))

Built with -fsanitize=signed-integer-overflow, that reports facthsh.c:100:60: runtime error: signed integer overflow: 41988 * 73981 cannot be represented in type 'int'.

Nothing in the fact is unusual. 41988 is where the symbol person happens to land in the symbol table, and every template name landing above bucket 29027 reaches the same overflow. The table holds 63559 buckets, so that is 54.3 per cent of them.

Why it is a fix and not a preference. Signed overflow is undefined behaviour, and the answers are the same before and after it is removed, so this contradicts nothing the manuals document. reports/README.md records reports declined on exactly that ground.

Two things separate this one. Reaching it needs nothing unusual: asserting a fact is the most ordinary thing a CLIPS program does, and a majority of template names trigger it. And it sits in a hash function, where a compiler entitled to assume the overflow cannot happen is equally entitled to drop the arithmetic around it.

Where it came from. HashFact in clips_core_source_642/core/facthsh.c:

   count += theFact->whichDeftemplate->header.name->bucket * 73981;

count is a size_t, but bucket is declared in symbol.h as unsigned int bucket : 29. A 29-bit unsigned bit-field is representable in int, so the integer promotions make the operand an int, and the product is formed in int before the addition widens anything. INT_MAX / 73981 is 29027, which is where the boundary comes from.

The change. The bit-field is converted to size_t before the multiplication, so the product is formed in the type the sum is kept in.

   count += ((size_t) theFact->whichDeftemplate->header.name->bucket) * 73981;

The hash value changes for a template name whose bucket is above 29027. It is internal and consistent within a build: HandleFactDuplication and RemoveHashedFact both reach it through HashFact, so insertion and removal agree.

Still present upstream. CLIPS 7.0.0 has the same line at core/facthsh.c:118, and a second instance of it at core/facthsh.c:159 in a function 6.4.2 does not have.