Bug 196935 – Add an overflow check to HashTable

• Component: Web Template Framework
• Status: NEW

[Ryosuke Niwa]

We should check for an integer overflow when expanding HashTable.

[Ryosuke Niwa]

Created attachment 367492 [details]
Fixes the bug

[Radar WebKit Bug Importer]

<rdar://problem/49928688>

[Geoffrey Garen]

Comment on attachment 367492 [details]
Fixes the bug

View in context: https://bugs.webkit.org/attachment.cgi?id=367492&action=review

r=me

> Source/WTF/wtf/HashTable.h:1206
> +        Checked<unsigned, CrashOnOverflow> bestTableSize = WTF::roundUpToPowerOfTwo(keyCount);
> +        if (bestTableSize.unsafeGet() < keyCount)
> +            bestTableSize.overflowed();
> +        bestTableSize *= 2;

If we needed a check here, I would recommend doing using Checked<T>.

But we don't need this less-than check. roundUpToPowerOfTwo(2^32) is 2^32. There's no overflow case.

I think I would write this as

    auto bestTableSize = Checked<unsigned, CrashOnOverflow>(WTF::roundUpToPowerOfTwo(keyCount)) * 2;

[Ryosuke Niwa]

(In reply to Geoffrey Garen from comment #3)
> Comment on attachment 367492 [details]
> Fixes the bug
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=367492&action=review
> 
> r=me
> 
> > Source/WTF/wtf/HashTable.h:1206
> > +        Checked<unsigned, CrashOnOverflow> bestTableSize = WTF::roundUpToPowerOfTwo(keyCount);
> > +        if (bestTableSize.unsafeGet() < keyCount)
> > +            bestTableSize.overflowed();
> > +        bestTableSize *= 2;
> 
> If we needed a check here, I would recommend doing using Checked<T>.
> 
> But we don't need this less-than check. roundUpToPowerOfTwo(2^32) is 2^32.
> There's no overflow case.

Hm... roundUpToPowerOfTwo(0x8fffffff) is 0 though. Do we have some guarantee that 0x80000000 would be the maximum key count?

[Geoffrey Garen]

> > If we needed a check here, I would recommend doing using Checked<T>.
> > 
> > But we don't need this less-than check. roundUpToPowerOfTwo(2^32) is 2^32.
> > There's no overflow case.
> 
> Hm... roundUpToPowerOfTwo(0x8fffffff) is 0 though. Do we have some guarantee
> that 0x80000000 would be the maximum key count?

Eep! I have immortalized in Bugzilla my inability to do binary arithmetic. Don't tell Gavin. :)

I think the problem input case is anything in the range (0x80000000, 0xffffffff], which is (2^31, 2^32-1]. In that case, the correct answer is 0x0000000100000000, which is not representable as uint32_t. And the implementation of roundUpToPowerOfTwo() will happen to return 0 (as you said).

Maybe the right solution is to templatize roundUpToPowerOfTwo() to accept uint32_t or Checked<uint32_t>, so it can naturally catch the overflow to zero on the final ++ operation?

I'm open to any solution that doesn't require an explicit check in the calling code. That's the primary benefit of Checked<T>.

[Ryosuke Niwa]

Interesting, in the process of adding Checked<U, V> support to roundUpToPowerOfTwo, I found out that CachedTypes::malloc converts size_t to uint32_t that's probably a bug...