commit 20432fc541bf0fb8f136f0d4635b264c624ce3eb Author: Nick Mathewson nickm@torproject.org Date: Wed Apr 27 10:16:43 2016 -0400

Refactor out u64_dbl_t

This type saved a tiny amount of allocation, but not enough to be worth keeping.

(This is in preparation for moving choose_array_element_by_weight) --- src/or/routerlist.c | 58 ++++++++++++++++++++++++++++++----------------------- src/or/routerlist.h | 13 +++--------- src/test/test_dir.c | 45 +++++++++++++++++++++-------------------- 3 files changed, 59 insertions(+), 57 deletions(-)

diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 80d0197..620b614 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -67,7 +67,7 @@ typedef struct cert_list_t cert_list_t; /* static function prototypes */ static int compute_weighted_bandwidths(const smartlist_t *sl, bandwidth_weight_rule_t rule, - u64_dbl_t **bandwidths_out); + double **bandwidths_out); static const routerstatus_t *router_pick_trusteddirserver_impl( const smartlist_t *sourcelist, dirinfo_type_t auth, int flags, int *n_busy_out); @@ -1799,20 +1799,23 @@ dirserver_choose_by_weight(const smartlist_t *servers, double authority_weight) { int n = smartlist_len(servers); int i; - u64_dbl_t *weights; + double *weights_dbl; + uint64_t *weights_u64; const dir_server_t *ds;

- weights = tor_calloc(n, sizeof(u64_dbl_t)); + weights_dbl = tor_calloc(n, sizeof(double)); + weights_u64 = tor_calloc(n, sizeof(uint64_t)); for (i = 0; i < n; ++i) { ds = smartlist_get(servers, i); - weights[i].dbl = ds->weight; + weights_dbl[i] = ds->weight; if (ds->is_authority) - weights[i].dbl *= authority_weight; + weights_dbl[i] *= authority_weight; }

- scale_array_elements_to_u64(weights, n, NULL); - i = choose_array_element_by_weight(weights, n); - tor_free(weights); + scale_array_elements_to_u64(weights_u64, weights_dbl, n, NULL); + i = choose_array_element_by_weight(weights_u64, n); + tor_free(weights_dbl); + tor_free(weights_u64); return (i < 0) ? NULL : smartlist_get(servers, i); }

@@ -2075,7 +2078,8 @@ router_get_advertised_bandwidth_capped(const routerinfo_t *router) * much of the range of uint64_t. If <b>total_out</b> is provided, set it to * the sum of all elements in the array _before_ scaling. */ STATIC void -scale_array_elements_to_u64(u64_dbl_t *entries, int n_entries, +scale_array_elements_to_u64(uint64_t *entries_out, const double *entries_in, + int n_entries, uint64_t *total_out) { double total = 0.0; @@ -2085,13 +2089,13 @@ scale_array_elements_to_u64(u64_dbl_t *entries, int n_entries, #define SCALE_TO_U64_MAX ((int64_t) (INT64_MAX / 4))

for (i = 0; i < n_entries; ++i) - total += entries[i].dbl; + total += entries_in[i];

if (total > 0.0) scale_factor = SCALE_TO_U64_MAX / total;

for (i = 0; i < n_entries; ++i) - entries[i].u64 = tor_llround(entries[i].dbl * scale_factor); + entries_out[i] = tor_llround(entries_in[i] * scale_factor);

if (total_out) *total_out = (uint64_t) total; @@ -2119,7 +2123,7 @@ gt_i64_timei(uint64_t a, uint64_t b) * an index at random. Return -1 on error. */ STATIC int -choose_array_element_by_weight(const u64_dbl_t *entries, int n_entries) +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; @@ -2127,7 +2131,7 @@ choose_array_element_by_weight(const u64_dbl_t *entries, int n_entries) uint64_t total = 0;

for (i = 0; i < n_entries; ++i) - total += entries[i].u64; + total += entries[i];

if (n_entries < 1) return -1; @@ -2140,7 +2144,7 @@ choose_array_element_by_weight(const u64_dbl_t *entries, int n_entries) rand_val = crypto_rand_uint64(total);

for (i = 0; i < n_entries; ++i) { - total_so_far += entries[i].u64; + total_so_far += entries[i]; if (gt_i64_timei(total_so_far, rand_val)) { i_chosen = i; n_chosen++; @@ -2206,17 +2210,21 @@ static const node_t * smartlist_choose_node_by_bandwidth_weights(const smartlist_t *sl, bandwidth_weight_rule_t rule) { - u64_dbl_t *bandwidths=NULL; + double *bandwidths_dbl=NULL; + uint64_t *bandwidths_u64=NULL;

- if (compute_weighted_bandwidths(sl, rule, &bandwidths) < 0) + if (compute_weighted_bandwidths(sl, rule, &bandwidths_dbl) < 0) return NULL;

- scale_array_elements_to_u64(bandwidths, smartlist_len(sl), NULL); + bandwidths_u64 = tor_calloc(smartlist_len(sl), sizeof(uint64_t)); + scale_array_elements_to_u64(bandwidths_u64, bandwidths_dbl, + smartlist_len(sl), NULL);

{ - int idx = choose_array_element_by_weight(bandwidths, + int idx = choose_array_element_by_weight(bandwidths_u64, smartlist_len(sl)); - tor_free(bandwidths); + tor_free(bandwidths_dbl); + tor_free(bandwidths_u64); return idx < 0 ? NULL : smartlist_get(sl, idx); } } @@ -2229,14 +2237,14 @@ smartlist_choose_node_by_bandwidth_weights(const smartlist_t *sl, static int compute_weighted_bandwidths(const smartlist_t *sl, bandwidth_weight_rule_t rule, - u64_dbl_t **bandwidths_out) + double **bandwidths_out) { int64_t weight_scale; double Wg = -1, Wm = -1, We = -1, Wd = -1; double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1; uint64_t weighted_bw = 0; guardfraction_bandwidth_t guardfraction_bw; - u64_dbl_t *bandwidths; + double *bandwidths;

/* Can't choose exit and guard at same time */ tor_assert(rule == NO_WEIGHTING || @@ -2318,7 +2326,7 @@ compute_weighted_bandwidths(const smartlist_t *sl, Web /= weight_scale; Wdb /= weight_scale;

- bandwidths = tor_calloc(smartlist_len(sl), sizeof(u64_dbl_t)); + bandwidths = tor_calloc(smartlist_len(sl), sizeof(double));

// Cycle through smartlist and total the bandwidth. static int warned_missing_bw = 0; @@ -2405,7 +2413,7 @@ compute_weighted_bandwidths(const smartlist_t *sl, final_weight = weight*this_bw; }

- bandwidths[node_sl_idx].dbl = final_weight + 0.5; + bandwidths[node_sl_idx] = final_weight + 0.5; } SMARTLIST_FOREACH_END(node);

log_debug(LD_CIRC, "Generated weighted bandwidths for rule %s based " @@ -2426,7 +2434,7 @@ double frac_nodes_with_descriptors(const smartlist_t *sl, bandwidth_weight_rule_t rule) { - u64_dbl_t *bandwidths = NULL; + double *bandwidths = NULL; double total, present;

if (smartlist_len(sl) == 0) @@ -2443,7 +2451,7 @@ frac_nodes_with_descriptors(const smartlist_t *sl,

total = present = 0.0; SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) { - const double bw = bandwidths[node_sl_idx].dbl; + const double bw = bandwidths[node_sl_idx]; total += bw; if (node_has_descriptor(node)) present += bw; diff --git a/src/or/routerlist.h b/src/or/routerlist.h index bc48c20..2166cf5 100644 --- a/src/or/routerlist.h +++ b/src/or/routerlist.h @@ -217,17 +217,10 @@ int hex_digest_nickname_matches(const char *hexdigest, const char *nickname, int is_named);

#ifdef ROUTERLIST_PRIVATE -/** Helper type for choosing routers by bandwidth: contains a union of - * double and uint64_t. Before we call scale_array_elements_to_u64, it holds - * a double; after, it holds a uint64_t. */ -typedef union u64_dbl_t { - uint64_t u64; - double dbl; -} u64_dbl_t; - -STATIC int choose_array_element_by_weight(const u64_dbl_t *entries, +STATIC int choose_array_element_by_weight(const uint64_t *entries, int n_entries); -STATIC void scale_array_elements_to_u64(u64_dbl_t *entries, int n_entries, +STATIC void scale_array_elements_to_u64(uint64_t *entries_out, + const double *entries_in, int n_entries, uint64_t *total_out); STATIC const routerstatus_t *router_pick_directory_server_impl( dirinfo_type_t auth, int flags, diff --git a/src/test/test_dir.c b/src/test/test_dir.c index ea179fb..747c4c4 100644 --- a/src/test/test_dir.c +++ b/src/test/test_dir.c @@ -2149,56 +2149,57 @@ test_dir_scale_bw(void *testdata) 1.0/7, 12.0, 24.0 }; - u64_dbl_t vals[8]; + double vals_dbl[8]; + uint64_t vals_u64[8]; uint64_t total; int i;

(void) testdata;

for (i=0; i<8; ++i) - vals[i].dbl = v[i]; + vals_dbl[i] = v[i];

- scale_array_elements_to_u64(vals, 8, &total); + scale_array_elements_to_u64(vals_u64, vals_dbl, 8, &total);

tt_int_op((int)total, OP_EQ, 48); total = 0; for (i=0; i<8; ++i) { - total += vals[i].u64; + total += vals_u64[i]; } tt_assert(total >= (U64_LITERAL(1)<<60)); tt_assert(total <= (U64_LITERAL(1)<<62));

for (i=0; i<8; ++i) { /* vals[2].u64 is the scaled value of 1.0 */ - double ratio = ((double)vals[i].u64) / vals[2].u64; + double ratio = ((double)vals_u64[i]) / vals_u64[2]; tt_double_op(fabs(ratio - v[i]), OP_LT, .00001); }

/* test handling of no entries */ total = 1; - scale_array_elements_to_u64(vals, 0, &total); + scale_array_elements_to_u64(vals_u64, vals_dbl, 0, &total); tt_assert(total == 0);

/* make sure we don't read the array when we have no entries * may require compiler flags to catch NULL dereferences */ total = 1; - scale_array_elements_to_u64(NULL, 0, &total); + scale_array_elements_to_u64(NULL, NULL, 0, &total); tt_assert(total == 0);

- scale_array_elements_to_u64(NULL, 0, NULL); + scale_array_elements_to_u64(NULL, NULL, 0, NULL);

/* test handling of zero totals */ total = 1; - vals[0].dbl = 0.0; - scale_array_elements_to_u64(vals, 1, &total); + vals_dbl[0] = 0.0; + scale_array_elements_to_u64(vals_u64, vals_dbl, 1, &total); tt_assert(total == 0); - tt_assert(vals[0].u64 == 0); + tt_assert(vals_u64[0] == 0);

- vals[0].dbl = 0.0; - vals[1].dbl = 0.0; - scale_array_elements_to_u64(vals, 2, NULL); - tt_assert(vals[0].u64 == 0); - tt_assert(vals[1].u64 == 0); + vals_dbl[0] = 0.0; + vals_dbl[1] = 0.0; + scale_array_elements_to_u64(vals_u64, vals_dbl, 2, NULL); + tt_assert(vals_u64[0] == 0); + tt_assert(vals_u64[1] == 0);

done: ; @@ -2209,7 +2210,7 @@ test_dir_random_weighted(void *testdata) { int histogram[10]; uint64_t vals[10] = {3,1,2,4,6,0,7,5,8,9}, total=0; - u64_dbl_t inp[10]; + uint64_t inp_u64[10]; int i, choice; const int n = 50000; double max_sq_error; @@ -2219,12 +2220,12 @@ test_dir_random_weighted(void *testdata) * in a scrambled order to make sure we don't depend on order. */ memset(histogram,0,sizeof(histogram)); for (i=0; i<10; ++i) { - inp[i].u64 = vals[i]; + inp_u64[i] = vals[i]; total += vals[i]; } tt_u64_op(total, OP_EQ, 45); for (i=0; i<n; ++i) { - choice = choose_array_element_by_weight(inp, 10); + choice = choose_array_element_by_weight(inp_u64, 10); tt_int_op(choice, OP_GE, 0); tt_int_op(choice, OP_LT, 10); histogram[choice]++; @@ -2251,16 +2252,16 @@ test_dir_random_weighted(void *testdata)

/* Now try a singleton; do we choose it? */ for (i = 0; i < 100; ++i) { - choice = choose_array_element_by_weight(inp, 1); + choice = choose_array_element_by_weight(inp_u64, 1); tt_int_op(choice, OP_EQ, 0); }

/* Now try an array of zeros. We should choose randomly. */ memset(histogram,0,sizeof(histogram)); for (i = 0; i < 5; ++i) - inp[i].u64 = 0; + inp_u64[i] = 0; for (i = 0; i < n; ++i) { - choice = choose_array_element_by_weight(inp, 5); + choice = choose_array_element_by_weight(inp_u64, 5); tt_int_op(choice, OP_GE, 0); tt_int_op(choice, OP_LT, 5); histogram[choice]++;