aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNick Mathewson <nickm@torproject.org>2012-09-13 10:34:49 -0400
committerNick Mathewson <nickm@torproject.org>2012-09-14 09:51:24 -0400
commit37953497d8689bdde65837b00f56bf8ff1e0e459 (patch)
treeeba5ce37971b301dffc9fe788b2ab1d439717284
parent582f2187a769ea723f6bf13bc91f7a4b3c861408 (diff)
downloadtor-37953497d8689bdde65837b00f56bf8ff1e0e459.tar.gz
tor-37953497d8689bdde65837b00f56bf8ff1e0e459.zip
Don't compute ((uint64_t)1)<<64 in round_to_power_of_2
This would be undefined behavior if it happened. (It can't actually happen as we're using round_to_power_of_2, since we would have to be trying to allocate exabytes of data.) While we're at it, fix the behavior of round_to_power_of_2(0), and document the function better. Fix for bug 6831.
-rw-r--r--changes/bug68314
-rw-r--r--src/common/util.c18
-rw-r--r--src/test/test_util.c13
3 files changed, 31 insertions, 4 deletions
diff --git a/changes/bug6831 b/changes/bug6831
new file mode 100644
index 0000000000..ac4775ba83
--- /dev/null
+++ b/changes/bug6831
@@ -0,0 +1,4 @@
+ o Minor bugfixes:
+ - Fix round_to_power_of_2 so it doesn't invoke undefined behavior
+ with large values. This was untriggered, but nevertheless incorrect.
+ Fixes bug 6831; bugfix on 0.2.0.1-alpha.
diff --git a/src/common/util.c b/src/common/util.c
index 84b31502e6..0e0dcb179c 100644
--- a/src/common/util.c
+++ b/src/common/util.c
@@ -394,12 +394,24 @@ tor_log2(uint64_t u64)
return r;
}
-/** Return the power of 2 closest to <b>u64</b>. */
+/** Return the power of 2 in range [1,UINT64_MAX] closest to <b>u64</b>. If
+ * there are two powers of 2 equally close, round down. */
uint64_t
round_to_power_of_2(uint64_t u64)
{
- int lg2 = tor_log2(u64);
- uint64_t low = U64_LITERAL(1) << lg2, high = U64_LITERAL(1) << (lg2+1);
+ int lg2;
+ uint64_t low;
+ uint64_t high;
+ if (u64 == 0)
+ return 1;
+
+ lg2 = tor_log2(u64);
+ low = U64_LITERAL(1) << lg2;
+
+ if (lg2 == 63)
+ return low;
+
+ high = U64_LITERAL(1) << (lg2+1);
if (high - u64 < u64 - low)
return high;
else
diff --git a/src/test/test_util.c b/src/test/test_util.c
index 7ef4d1f78c..2a194ef840 100644
--- a/src/test/test_util.c
+++ b/src/test/test_util.c
@@ -1109,6 +1109,7 @@ test_util_pow2(void)
test_eq(tor_log2(64), 6);
test_eq(tor_log2(65), 6);
test_eq(tor_log2(63), 5);
+ test_eq(tor_log2(0), 0); /* incorrect mathematically, but as specified */
test_eq(tor_log2(1), 0);
test_eq(tor_log2(2), 1);
test_eq(tor_log2(3), 1);
@@ -1123,7 +1124,17 @@ test_util_pow2(void)
test_eq(round_to_power_of_2(130), 128);
test_eq(round_to_power_of_2(U64_LITERAL(40000000000000000)),
U64_LITERAL(1)<<55);
- test_eq(round_to_power_of_2(0), 2);
+ test_eq(round_to_power_of_2(U64_LITERAL(0xffffffffffffffff)),
+ U64_LITERAL(1)<<63);
+ test_eq(round_to_power_of_2(0), 1);
+ test_eq(round_to_power_of_2(1), 1);
+ test_eq(round_to_power_of_2(2), 2);
+ test_eq(round_to_power_of_2(3), 2);
+ test_eq(round_to_power_of_2(4), 4);
+ test_eq(round_to_power_of_2(4), 4);
+ test_eq(round_to_power_of_2(5), 4);
+ test_eq(round_to_power_of_2(6), 4);
+ test_eq(round_to_power_of_2(7), 8);
done:
;