We should check for an integer overflow when expanding HashTable.
Created attachment 367492 [details] Fixes the bug
<rdar://problem/49928688>
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;
(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?
> > 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>.
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...