commit e40cfc4425d1e173b5d122e38ab07dd798b11925 Author: Nick Mathewson nickm@torproject.org Date: Wed Apr 27 10:33:46 2016 -0400
Move the ctime part of choose_array_element_by_weight into di_ops
This way it gets the ctime options. --- src/common/di_ops.c | 45 +++++++++++++++++++++++++++++++++++++++++++++ src/common/di_ops.h | 2 ++ src/or/routerlist.c | 35 +++-------------------------------- 3 files changed, 50 insertions(+), 32 deletions(-)
diff --git a/src/common/di_ops.c b/src/common/di_ops.c index 5dfe828..e671af6 100644 --- a/src/common/di_ops.c +++ b/src/common/di_ops.c @@ -226,3 +226,48 @@ safe_mem_is_zero(const void *mem, size_t sz) return 1 & ((total - 1) >> 8); }
+/** Time-invariant 64-bit greater-than; works on two integers in the range + * (0,INT64_MAX). */ +#if SIZEOF_VOID_P == 8 +#define gt_i64_timei(a,b) ((a) > (b)) +#else +static inline int +gt_i64_timei(uint64_t a, uint64_t b) +{ + int64_t diff = (int64_t) (b - a); + int res = diff >> 63; + return res & 1; +} +#endif + +/** + * Given an array of list of <b>n_entries</b> uint64_t values, whose sum is + * <b>total</b>, find the first i such that the total of all elements 0...i is + * greater than rand_val. + * + * Try to perform this operation in a constant-time way. + */ +int +select_array_member_cumulative_timei(const uint64_t *entries, int n_entries, + uint64_t total, uint64_t rand_val) +{ + int i, i_chosen=-1, n_chosen=0; + uint64_t total_so_far = 0; + + for (i = 0; i < n_entries; ++i) { + total_so_far += entries[i]; + if (gt_i64_timei(total_so_far, rand_val)) { + i_chosen = i; + n_chosen++; + /* Set rand_val to INT64_MAX rather than stopping the loop. This way, + * the time we spend in the loop does not leak which element we chose. */ + rand_val = INT64_MAX; + } + } + tor_assert(total_so_far == total); + tor_assert(n_chosen == 1); + tor_assert(i_chosen >= 0); + tor_assert(i_chosen < n_entries); + + return i_chosen; +} diff --git a/src/common/di_ops.h b/src/common/di_ops.h index 6e77b5c..f1050a0 100644 --- a/src/common/di_ops.h +++ b/src/common/di_ops.h @@ -42,6 +42,8 @@ void dimap_add_entry(di_digest256_map_t **map, const uint8_t *key, void *val); void *dimap_search(const di_digest256_map_t *map, const uint8_t *key, void *dflt_val); +int select_array_member_cumulative_timei(const uint64_t *entries, int n_entries, + uint64_t total, uint64_t rand_val);
#endif
diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 620b614..b6247a1 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -2103,20 +2103,6 @@ scale_array_elements_to_u64(uint64_t *entries_out, const double *entries_in, #undef SCALE_TO_U64_MAX }
-/** Time-invariant 64-bit greater-than; works on two integers in the range - * (0,INT64_MAX). */ -#if SIZEOF_VOID_P == 8 -#define gt_i64_timei(a,b) ((a) > (b)) -#else -static inline int -gt_i64_timei(uint64_t a, uint64_t b) -{ - int64_t diff = (int64_t) (b - a); - int res = diff >> 63; - return res & 1; -} -#endif - /** Pick a random element of <b>n_entries</b>-element array <b>entries</b>, * choosing each element with a probability proportional to its (uint64_t) * value, and return the index of that element. If all elements are 0, choose @@ -2125,8 +2111,7 @@ gt_i64_timei(uint64_t a, uint64_t b) STATIC int choose_array_element_by_weight(const uint64_t *entries, int n_entries) { - int i, i_chosen=-1, n_chosen=0; - uint64_t total_so_far = 0; + int i; uint64_t rand_val; uint64_t total = 0;
@@ -2143,22 +2128,8 @@ choose_array_element_by_weight(const uint64_t *entries, int n_entries)
rand_val = crypto_rand_uint64(total);
- for (i = 0; i < n_entries; ++i) { - total_so_far += entries[i]; - if (gt_i64_timei(total_so_far, rand_val)) { - i_chosen = i; - n_chosen++; - /* Set rand_val to INT64_MAX rather than stopping the loop. This way, - * the time we spend in the loop does not leak which element we chose. */ - rand_val = INT64_MAX; - } - } - tor_assert(total_so_far == total); - tor_assert(n_chosen == 1); - tor_assert(i_chosen >= 0); - tor_assert(i_chosen < n_entries); - - return i_chosen; + return select_array_member_cumulative_timei( + entries, n_entries, total, rand_val); }
/** When weighting bridges, enforce these values as lower and upper