vsk created this revision.
There are two sources of undefined behavior in __next_hash_pow2: an
invalid shift (occurs when __n is 0 or 1), and an invalid call to CLZ
(when __n=1).
This patch corrects both issues. It's NFC for all values of __n which do
not trigger UB, and leads to defined results when __n is 0 or 1.
Minimal reproducer:
unordered_map<uint64_t, unsigned long> m;
m.reserve(4);
m.reserve(1);
I wrote a miniature 'fuzzer' to test this change and ran it with UBSan
enabled. AFAIK, this is the best we can do for a test. I don't know how
to write a non-flaky test which would fail without this patch applied.
Here is the 'fuzzer' (simply run with -fsanitize=undefined):
void fuzzUnorderedMap(unsigned NumInserts, unsigned NumReserve1,
unsigned NumReserve2) {
unordered_map<uint64_t, unsigned long> m;
m.reserve(NumReserve1);
for (unsigned I = 0; I < NumInserts; ++I) { m[I] = 0; }
size_t __n = size_t(ceil(float(m.size()) / m.max_load_factor()));
m.reserve(NumReserve2);
}
...
for (unsigned NumInserts = 0; NumInserts <= 64; ++NumInserts)
for (unsigned NumReserve1 = 1; NumReserve1 <= 64; ++NumReserve1)
for (unsigned NumReserve2 = 1; NumReserve2 <= 64; ++NumReserve2)
fuzzUnorderedMap(NumInserts, NumReserve1, NumReserve2);
rdar://problem/32407328
https://reviews.llvm.org/D33588
Files:
include/__hash_table
Index: include/__hash_table
===================================================================
--- include/__hash_table
+++ include/__hash_table
@@ -136,7 +136,7 @@
size_t
__next_hash_pow2(size_t __n)
{
- return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
+ return (__n > 1) ? (size_t(1) << (std::numeric_limits<size_t>::digits -
__clz(__n-1))) : __n;
}
Index: include/__hash_table
===================================================================
--- include/__hash_table
+++ include/__hash_table
@@ -136,7 +136,7 @@
size_t
__next_hash_pow2(size_t __n)
{
- return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
+ return (__n > 1) ? (size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1))) : __n;
}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
