From b5a164bde4f33fdd33c83a8425c6464c0f5ef60d Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Wed, 27 Feb 2013 19:43:50 -0800 Subject: Prefer measured bandwidths over advertised when computing things for votes on a dirauth --- changes/bug8273 | 3 + src/or/dirserv.c | 206 ++++++++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 201 insertions(+), 8 deletions(-) create mode 100644 changes/bug8273 diff --git a/changes/bug8273 b/changes/bug8273 new file mode 100644 index 000000000..257f57e7a --- /dev/null +++ b/changes/bug8273 @@ -0,0 +1,3 @@ + o Critical bugfixes: + - When dirserv.c computes flags and thresholds, use measured bandwidths + in preference to advertised ones. diff --git a/src/or/dirserv.c b/src/or/dirserv.c index badacd683..1c78d2d3b 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -85,6 +85,14 @@ static const signed_descriptor_t *get_signed_descriptor_by_fp( time_t publish_cutoff); static was_router_added_t dirserv_add_extrainfo(extrainfo_t *ei, const char **msg); +static void dirserv_cache_measured_bw(measured_bw_line_t *parsed_line, + time_t as_of); +static void dirserv_clear_measured_bw_cache(void); +static void dirserv_expire_measured_bw_cache(time_t now); +static int dirserv_get_measured_bw_cache_size(void); +static int dirserv_query_measured_bw_cache(char *node_id, long *bw_out, + time_t *as_of_out); +static uint32_t dirserv_get_bandwidth_for_router(routerinfo_t *ri); /************** Measured Bandwidth parsing code ******/ #define MAX_MEASUREMENT_AGE (3*24*60*60) /* 3 days */ @@ -1824,7 +1832,7 @@ dirserv_thinks_router_is_unreliable(time_t now, } } if (need_capacity) { - uint32_t bw = router_get_advertised_bandwidth(router); + uint32_t bw = dirserv_get_bandwidth_for_router(router); if (bw < fast_bandwidth) return 1; } @@ -1883,7 +1891,7 @@ router_counts_toward_thresholds(const node_t *node, time_t now, { return node->ri && router_is_active(node->ri, node, now) && !digestmap_get(omit_as_sybil, node->ri->cache_info.identity_digest) && - (router_get_advertised_bandwidth(node->ri) >= + (dirserv_get_bandwidth_for_router(node->ri) >= ABSOLUTE_MIN_BW_VALUE_TO_CONSIDER); } @@ -1947,7 +1955,7 @@ dirserv_compute_performance_thresholds(routerlist_t *rl, uptimes[n_active] = (uint32_t)real_uptime(ri, now); mtbfs[n_active] = rep_hist_get_stability(id, now); tks [n_active] = rep_hist_get_weighted_time_known(id, now); - bandwidths[n_active] = bw = router_get_advertised_bandwidth(ri); + bandwidths[n_active] = bw = dirserv_get_bandwidth_for_router(ri); total_bandwidth += bw; if (node->is_exit && !node->is_bad_exit) { total_exit_bandwidth += bw; @@ -2046,6 +2054,165 @@ dirserv_compute_performance_thresholds(routerlist_t *rl, tor_free(wfus); } +/** Measured bandwidth cache entry */ +typedef struct mbw_cache_entry_s { + long mbw; + time_t as_of; +} mbw_cache_entry_t; + +/** Measured bandwidth cache - keys are identity_digests, values are + * mbw_cache_entry_t *. */ +static digestmap_t *mbw_cache = NULL; + +/** Store a measured bandwidth cache entry when reading the measured + * bandwidths file. */ +static void +dirserv_cache_measured_bw(measured_bw_line_t *parsed_line, time_t as_of) +{ + mbw_cache_entry_t *e = NULL; + + tor_assert(parsed_line); + + /* Allocate a cache if we need */ + if (!mbw_cache) mbw_cache = digestmap_new(); + + /* Check if we have an existing entry */ + e = digestmap_get(mbw_cache, parsed_line->node_id); + /* If we do, we can re-use it */ + if (e) { + /* Check that we really are newer, and update */ + if (as_of > e->as_of) { + e->mbw = parsed_line->bw; + e->as_of = as_of; + } + } else { + /* We'll have to insert a new entry */ + e = tor_malloc(sizeof(*e)); + e->mbw = parsed_line->bw; + e->as_of = as_of; + digestmap_set(mbw_cache, parsed_line->node_id, e); + } +} + +/** Clear and free the measured bandwidth cache */ +static void +dirserv_clear_measured_bw_cache(void) +{ + if (mbw_cache) { + /* Free the map and all entries */ + digestmap_free(mbw_cache, tor_free_); + mbw_cache = NULL; + } +} + +/** Scan the measured bandwidth cache and remove expired entries */ +static void +dirserv_expire_measured_bw_cache(time_t now) +{ + digestmap_iter_t *itr = NULL; + const char *k = NULL; + void *e_v = NULL; + mbw_cache_entry_t *e = NULL; + int rmv; + + if (mbw_cache) { + /* Start iterating */ + itr = digestmap_iter_init(mbw_cache); + while (!digestmap_iter_done(itr)) { + rmv = 0; + digestmap_iter_get(itr, &k, &e_v); + e = (mbw_cache_entry_t *)e_v; + if (e) { + /* Check for expiration and remove if so */ + if (now - e->as_of > MAX_MEASUREMENT_AGE) { + tor_free(e); + rmv = 1; + } + } else { + /* Weird; remove it and complain */ + log_warn(LD_BUG, "Saw NULL entry in measured bandwidth cache"); + rmv = 1; + } + + /* Advance, or remove and advance */ + if (rmv) { + itr = digestmap_iter_next_rmv(mbw_cache, itr); + } else { + itr = digestmap_iter_next(mbw_cache, itr); + } + } + + /* Check if we cleared the whole thing and free if so */ + if (digestmap_size(mbw_cache) == 0) { + digestmap_free(mbw_cache, tor_free_); + mbw_cache = 0; + } + } +} + +/** Get the current size of the measured bandwidth cache */ +static int +dirserv_get_measured_bw_cache_size(void) +{ + if (mbw_cache) return digestmap_size(mbw_cache); + else return 0; +} + +/** Query the cache by identity digest, return value indicates whether + * we found it. */ +static int +dirserv_query_measured_bw_cache(char *node_id, long *bw_out, + time_t *as_of_out) +{ + mbw_cache_entry_t *v = NULL; + int rv = 0; + + if (mbw_cache && node_id) { + v = digestmap_get(mbw_cache, node_id); + if (v) { + /* Found something */ + rv = 1; + if (bw_out) *bw_out = v->mbw; + if (as_of_out) *as_of_out = v->as_of; + } + } + + return rv; +} + +/** Get the best estimate of a router's bandwidth for dirauth purposes, + * preferring measured to advertised values if available. */ + +static uint32_t +dirserv_get_bandwidth_for_router(routerinfo_t *ri) +{ + uint32_t bw = 0; + /* + * Yeah, measured bandwidths in measured_bw_line_t are (implicitly + * signed) longs and the ones router_get_advertised_bandwidth() returns + * are uint32_t. + */ + long mbw = 0; + + if (ri) { + /* + * * First try to see if we have a measured bandwidth; don't bother with + * as_of_out here, on the theory that a stale measured bandwidth is still + * better to trust than an advertised one. + */ + if (dirserv_query_measured_bw_cache(ri->cache_info.identity_digest, + &mbw, NULL)) { + /* Got one! */ + bw = (uint32_t)mbw; + } else { + /* If not, fall back to advertised */ + bw = router_get_advertised_bandwidth(ri); + } + } + + return bw; +} + /** Give a statement of our current performance thresholds for inclusion * in a vote document. */ char * @@ -2327,8 +2494,8 @@ compare_routerinfo_by_ip_and_bw_(const void **a, const void **b) else if (!first_is_running && second_is_running) return 1; - bw_first = router_get_advertised_bandwidth(first); - bw_second = router_get_advertised_bandwidth(second); + bw_first = dirserv_get_bandwidth_for_router(first); + bw_second = dirserv_get_bandwidth_for_router(second); if (bw_first > bw_second) return -1; @@ -2468,7 +2635,7 @@ set_routerstatus_from_routerinfo(routerstatus_t *rs, int listbaddirs, int vote_on_hsdirs) { const or_options_t *options = get_options(); - uint32_t routerbw = router_get_advertised_bandwidth(ri); + uint32_t routerbw = dirserv_get_bandwidth_for_router(ri); memset(rs, 0, sizeof(routerstatus_t)); @@ -2670,8 +2837,9 @@ dirserv_read_measured_bandwidths(const char *from_file, char line[256]; FILE *fp = tor_fopen_cloexec(from_file, "r"); int applied_lines = 0; - time_t file_time; + time_t file_time, now; int ok; + if (fp == NULL) { log_warn(LD_CONFIG, "Can't open bandwidth file at configured location: %s", from_file); @@ -2695,7 +2863,8 @@ dirserv_read_measured_bandwidths(const char *from_file, return -1; } - if ((time(NULL) - file_time) > MAX_MEASUREMENT_AGE) { + now = time(NULL); + if ((now - file_time) > MAX_MEASUREMENT_AGE) { log_warn(LD_DIRSERV, "Bandwidth measurement file stale. Age: %u", (unsigned)(time(NULL) - file_time)); fclose(fp); @@ -2709,12 +2878,17 @@ dirserv_read_measured_bandwidths(const char *from_file, measured_bw_line_t parsed_line; if (fgets(line, sizeof(line), fp) && strlen(line)) { if (measured_bw_line_parse(&parsed_line, line) != -1) { + /* Also cache the line for dirserv_get_bandwidth_for_router() */ + dirserv_cache_measured_bw(&parsed_line, file_time); if (measured_bw_line_apply(&parsed_line, routerstatuses) > 0) applied_lines++; } } } + /* Now would be a nice time to clean the cache, too */ + dirserv_expire_measured_bw_cache(now); + fclose(fp); log_info(LD_DIRSERV, "Bandwidth measurement file successfully read. " @@ -2778,6 +2952,14 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, if (!contact) contact = "(none)"; + /* + * Do this so dirserv_compute_performance_thresholds() and + * set_routerstatus_from_routerinfo() see up-to-date bandwidth info. + */ + if (options->V3BandwidthsFile) { + dirserv_read_measured_bandwidths(options->V3BandwidthsFile, NULL); + } + /* precompute this part, since we need it to decide what "stable" * means. */ SMARTLIST_FOREACH(rl->routers, routerinfo_t *, ri, { @@ -2841,6 +3023,14 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, if (options->V3BandwidthsFile) { dirserv_read_measured_bandwidths(options->V3BandwidthsFile, routerstatuses); + } else { + /* + * No bandwidths file; clear the measured bandwidth cache in case we had + * one last time around. + */ + if (dirserv_get_measured_bw_cache_size() > 0) { + dirserv_clear_measured_bw_cache(); + } } v3_out = tor_malloc_zero(sizeof(networkstatus_t)); -- cgit v1.2.3 From 0efe96cae81a078301ba8806d821175c830627b9 Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Tue, 5 Mar 2013 13:11:43 -0800 Subject: Call dirserv_clear_measured_bw_cache() from dirserv_free_all() --- src/or/dirserv.c | 2 ++ 1 file changed, 2 insertions(+) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 1c78d2d3b..b3a5177ee 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -4098,5 +4098,7 @@ dirserv_free_all(void) cached_v2_networkstatus = NULL; strmap_free(cached_consensuses, free_cached_dir_); cached_consensuses = NULL; + + dirserv_clear_measured_bw_cache(); } -- cgit v1.2.3 From 75eb79a6aa4ab46ddd6bd5f9c1d7567f80ace68c Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Thu, 7 Mar 2013 03:42:14 -0800 Subject: Make dirserv_cache_measured_bw() use a const measured_bw_line_t * --- src/or/dirserv.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index b3a5177ee..1160f6baf 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -85,7 +85,7 @@ static const signed_descriptor_t *get_signed_descriptor_by_fp( time_t publish_cutoff); static was_router_added_t dirserv_add_extrainfo(extrainfo_t *ei, const char **msg); -static void dirserv_cache_measured_bw(measured_bw_line_t *parsed_line, +static void dirserv_cache_measured_bw(const measured_bw_line_t *parsed_line, time_t as_of); static void dirserv_clear_measured_bw_cache(void); static void dirserv_expire_measured_bw_cache(time_t now); @@ -2067,7 +2067,8 @@ static digestmap_t *mbw_cache = NULL; /** Store a measured bandwidth cache entry when reading the measured * bandwidths file. */ static void -dirserv_cache_measured_bw(measured_bw_line_t *parsed_line, time_t as_of) +dirserv_cache_measured_bw(const measured_bw_line_t *parsed_line, + time_t as_of) { mbw_cache_entry_t *e = NULL; -- cgit v1.2.3 From c7947619df826f6c4568c857178d54b8dee17749 Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Thu, 7 Mar 2013 05:05:56 -0800 Subject: More constness in dirserv.c --- src/or/dirserv.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 1160f6baf..1846dc1ba 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -90,9 +90,9 @@ static void dirserv_cache_measured_bw(const measured_bw_line_t *parsed_line, static void dirserv_clear_measured_bw_cache(void); static void dirserv_expire_measured_bw_cache(time_t now); static int dirserv_get_measured_bw_cache_size(void); -static int dirserv_query_measured_bw_cache(char *node_id, long *bw_out, +static int dirserv_query_measured_bw_cache(const char *node_id, long *bw_out, time_t *as_of_out); -static uint32_t dirserv_get_bandwidth_for_router(routerinfo_t *ri); +static uint32_t dirserv_get_bandwidth_for_router(const routerinfo_t *ri); /************** Measured Bandwidth parsing code ******/ #define MAX_MEASUREMENT_AGE (3*24*60*60) /* 3 days */ @@ -2162,7 +2162,7 @@ dirserv_get_measured_bw_cache_size(void) /** Query the cache by identity digest, return value indicates whether * we found it. */ static int -dirserv_query_measured_bw_cache(char *node_id, long *bw_out, +dirserv_query_measured_bw_cache(const char *node_id, long *bw_out, time_t *as_of_out) { mbw_cache_entry_t *v = NULL; @@ -2185,7 +2185,7 @@ dirserv_query_measured_bw_cache(char *node_id, long *bw_out, * preferring measured to advertised values if available. */ static uint32_t -dirserv_get_bandwidth_for_router(routerinfo_t *ri) +dirserv_get_bandwidth_for_router(const routerinfo_t *ri) { uint32_t bw = 0; /* -- cgit v1.2.3 From 302d1dae6c468fd2bd5551de654e36b8464a7eab Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Thu, 7 Mar 2013 05:10:54 -0800 Subject: Make sure expiry check in dirserv_expire_measured_bw_cache() works if time_t is unsigned --- src/or/dirserv.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 1846dc1ba..3dfa1e74d 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -2125,7 +2125,7 @@ dirserv_expire_measured_bw_cache(time_t now) e = (mbw_cache_entry_t *)e_v; if (e) { /* Check for expiration and remove if so */ - if (now - e->as_of > MAX_MEASUREMENT_AGE) { + if (now > e->as_of + MAX_MEASUREMENT_AGE) { tor_free(e); rmv = 1; } -- cgit v1.2.3 From 6e978ab8294eda5bb9a658c8d062bdd0098a9ac5 Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Thu, 7 Mar 2013 15:41:22 -0800 Subject: Add unit test for dirserv measured bandwidth cache --- src/or/dirserv.c | 20 ++++---------- src/or/dirserv.h | 12 +++++++++ src/test/test_dir.c | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 95 insertions(+), 15 deletions(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 3dfa1e74d..e97def718 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -85,18 +85,8 @@ static const signed_descriptor_t *get_signed_descriptor_by_fp( time_t publish_cutoff); static was_router_added_t dirserv_add_extrainfo(extrainfo_t *ei, const char **msg); -static void dirserv_cache_measured_bw(const measured_bw_line_t *parsed_line, - time_t as_of); -static void dirserv_clear_measured_bw_cache(void); -static void dirserv_expire_measured_bw_cache(time_t now); -static int dirserv_get_measured_bw_cache_size(void); -static int dirserv_query_measured_bw_cache(const char *node_id, long *bw_out, - time_t *as_of_out); static uint32_t dirserv_get_bandwidth_for_router(const routerinfo_t *ri); -/************** Measured Bandwidth parsing code ******/ -#define MAX_MEASUREMENT_AGE (3*24*60*60) /* 3 days */ - /************** Fingerprint handling code ************/ #define FP_NAMED 1 /**< Listed in fingerprint file. */ @@ -2066,7 +2056,7 @@ static digestmap_t *mbw_cache = NULL; /** Store a measured bandwidth cache entry when reading the measured * bandwidths file. */ -static void +void dirserv_cache_measured_bw(const measured_bw_line_t *parsed_line, time_t as_of) { @@ -2096,7 +2086,7 @@ dirserv_cache_measured_bw(const measured_bw_line_t *parsed_line, } /** Clear and free the measured bandwidth cache */ -static void +void dirserv_clear_measured_bw_cache(void) { if (mbw_cache) { @@ -2107,7 +2097,7 @@ dirserv_clear_measured_bw_cache(void) } /** Scan the measured bandwidth cache and remove expired entries */ -static void +void dirserv_expire_measured_bw_cache(time_t now) { digestmap_iter_t *itr = NULL; @@ -2152,7 +2142,7 @@ dirserv_expire_measured_bw_cache(time_t now) } /** Get the current size of the measured bandwidth cache */ -static int +int dirserv_get_measured_bw_cache_size(void) { if (mbw_cache) return digestmap_size(mbw_cache); @@ -2161,7 +2151,7 @@ dirserv_get_measured_bw_cache_size(void) /** Query the cache by identity digest, return value indicates whether * we found it. */ -static int +int dirserv_query_measured_bw_cache(const char *node_id, long *bw_out, time_t *as_of_out) { diff --git a/src/or/dirserv.h b/src/or/dirserv.h index 0caf55f83..887a4992e 100644 --- a/src/or/dirserv.h +++ b/src/or/dirserv.h @@ -138,10 +138,22 @@ void cached_dir_decref(cached_dir_t *d); cached_dir_t *new_cached_dir(char *s, time_t published); #ifdef DIRSERV_PRIVATE + +/* Put the MAX_MEASUREMENT_AGE #define here so unit tests can see it */ +#define MAX_MEASUREMENT_AGE (3*24*60*60) /* 3 days */ + int measured_bw_line_parse(measured_bw_line_t *out, const char *line); int measured_bw_line_apply(measured_bw_line_t *parsed_line, smartlist_t *routerstatuses); + +void dirserv_cache_measured_bw(const measured_bw_line_t *parsed_line, + time_t as_of); +void dirserv_clear_measured_bw_cache(void); +void dirserv_expire_measured_bw_cache(time_t now); +int dirserv_get_measured_bw_cache_size(void); +int dirserv_query_measured_bw_cache(const char *node_id, long *bw_out, + time_t *as_of_out); #endif int dirserv_read_measured_bandwidths(const char *from_file, diff --git a/src/test/test_dir.c b/src/test/test_dir.c index fbd49b710..667e8f423 100644 --- a/src/test/test_dir.c +++ b/src/test/test_dir.c @@ -575,6 +575,83 @@ test_dir_measured_bw(void) return; } +#define MBWC_INIT_TIME 1000 + +/** Do the measured bandwidth cache unit test */ +static void +test_dir_measured_bw_cache(void) +{ + /* Initial fake time_t for testing */ + time_t curr = MBWC_INIT_TIME; + /* Some measured_bw_line_ts */ + measured_bw_line_t mbwl[3]; + /* For receiving output on cache queries */ + long bw; + time_t as_of; + + /* First, clear the cache and assert that it's empty */ + dirserv_clear_measured_bw_cache(); + test_eq(dirserv_get_measured_bw_cache_size(), 0); + /* + * Set up test mbwls; none of the dirserv_cache_*() functions care about + * the node_hex field. + */ + memset(mbwl[0].node_id, 0x01, DIGEST_LEN); + mbwl[0].bw = 20; + memset(mbwl[1].node_id, 0x02, DIGEST_LEN); + mbwl[1].bw = 40; + memset(mbwl[2].node_id, 0x03, DIGEST_LEN); + mbwl[2].bw = 80; + /* Try caching something */ + dirserv_cache_measured_bw(&(mbwl[0]), curr); + test_eq(dirserv_get_measured_bw_cache_size(), 1); + /* Okay, let's see if we can retrieve it */ + test_assert(dirserv_query_measured_bw_cache(mbwl[0].node_id, &bw, &as_of)); + test_eq(bw, 20); + test_eq(as_of, MBWC_INIT_TIME); + /* Try retrieving it without some outputs */ + test_assert(dirserv_query_measured_bw_cache(mbwl[0].node_id, NULL, NULL)); + test_assert(dirserv_query_measured_bw_cache(mbwl[0].node_id, &bw, NULL)); + test_eq(bw, 20); + test_assert(dirserv_query_measured_bw_cache(mbwl[0].node_id, NULL, &as_of)); + test_eq(as_of, MBWC_INIT_TIME); + /* Now expire it */ + curr += MAX_MEASUREMENT_AGE + 1; + dirserv_expire_measured_bw_cache(curr); + /* Check that the cache is empty */ + test_eq(dirserv_get_measured_bw_cache_size(), 0); + /* Check that we can't retrieve it */ + test_assert(!dirserv_query_measured_bw_cache(mbwl[0].node_id, NULL, NULL)); + /* Try caching a few things now */ + dirserv_cache_measured_bw(&(mbwl[0]), curr); + test_eq(dirserv_get_measured_bw_cache_size(), 1); + curr += MAX_MEASUREMENT_AGE / 4; + dirserv_cache_measured_bw(&(mbwl[1]), curr); + test_eq(dirserv_get_measured_bw_cache_size(), 2); + curr += MAX_MEASUREMENT_AGE / 4; + dirserv_cache_measured_bw(&(mbwl[2]), curr); + test_eq(dirserv_get_measured_bw_cache_size(), 3); + curr += MAX_MEASUREMENT_AGE / 4 + 1; + /* Do an expire that's too soon to get any of them */ + dirserv_expire_measured_bw_cache(curr); + test_eq(dirserv_get_measured_bw_cache_size(), 3); + /* Push the oldest one off the cliff */ + curr += MAX_MEASUREMENT_AGE / 4; + dirserv_expire_measured_bw_cache(curr); + test_eq(dirserv_get_measured_bw_cache_size(), 2); + /* And another... */ + curr += MAX_MEASUREMENT_AGE / 4; + dirserv_expire_measured_bw_cache(curr); + test_eq(dirserv_get_measured_bw_cache_size(), 1); + /* This should empty it out again */ + curr += MAX_MEASUREMENT_AGE / 4; + dirserv_expire_measured_bw_cache(curr); + test_eq(dirserv_get_measured_bw_cache_size(), 0); + + done: + return; +} + static void test_dir_param_voting(void) { @@ -2141,6 +2218,7 @@ struct testcase_t dir_tests[] = { DIR(scale_bw), DIR_LEGACY(clip_unmeasured_bw), DIR_LEGACY(clip_unmeasured_bw_alt), + DIR_LEGACY(measured_bw_cache), END_OF_TESTCASES }; -- cgit v1.2.3 From b5224348340238f231f81138c09f7f16541d0f1d Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Thu, 7 Mar 2013 15:55:01 -0800 Subject: Use DIGESTMAP_FOREACH_MODIFY in dirserv_expire_measured_bw_cache() for concision --- src/or/dirserv.c | 35 ++++++----------------------------- 1 file changed, 6 insertions(+), 29 deletions(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index e97def718..b6ff6f694 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -2100,38 +2100,15 @@ dirserv_clear_measured_bw_cache(void) void dirserv_expire_measured_bw_cache(time_t now) { - digestmap_iter_t *itr = NULL; - const char *k = NULL; - void *e_v = NULL; - mbw_cache_entry_t *e = NULL; - int rmv; if (mbw_cache) { - /* Start iterating */ - itr = digestmap_iter_init(mbw_cache); - while (!digestmap_iter_done(itr)) { - rmv = 0; - digestmap_iter_get(itr, &k, &e_v); - e = (mbw_cache_entry_t *)e_v; - if (e) { - /* Check for expiration and remove if so */ - if (now > e->as_of + MAX_MEASUREMENT_AGE) { - tor_free(e); - rmv = 1; - } - } else { - /* Weird; remove it and complain */ - log_warn(LD_BUG, "Saw NULL entry in measured bandwidth cache"); - rmv = 1; + /* Iterate through the cache and check each entry */ + DIGESTMAP_FOREACH_MODIFY(mbw_cache, k, mbw_cache_entry_t *, e) { + if (now > e->as_of + MAX_MEASUREMENT_AGE) { + tor_free(e); + MAP_DEL_CURRENT(k); } - - /* Advance, or remove and advance */ - if (rmv) { - itr = digestmap_iter_next_rmv(mbw_cache, itr); - } else { - itr = digestmap_iter_next(mbw_cache, itr); - } - } + } DIGESTMAP_FOREACH_END; /* Check if we cleared the whole thing and free if so */ if (digestmap_size(mbw_cache) == 0) { -- cgit v1.2.3 From 8027ebb5fdf43b5aa63e498c1f8e3c6b2c87bbb7 Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Thu, 7 Mar 2013 15:59:30 -0800 Subject: Better comment for dirserv_query_measured_bw_cache() --- src/or/dirserv.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index b6ff6f694..37934a032 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -2127,7 +2127,8 @@ dirserv_get_measured_bw_cache_size(void) } /** Query the cache by identity digest, return value indicates whether - * we found it. */ + * we found it. The bw_out and as_of_out pointers receive the cached + * bandwidth value and the time it was cached if not NULL. */ int dirserv_query_measured_bw_cache(const char *node_id, long *bw_out, time_t *as_of_out) -- cgit v1.2.3 From f93f7e331be94114d82c17108e741eb2482e6bda Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Mon, 18 Mar 2013 11:15:21 -0700 Subject: Ignore advertised bandwidths if we have enough measured bandwidths available --- changes/bug8435 | 4 +++ src/or/config.c | 1 + src/or/dirserv.c | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++---- src/or/or.h | 4 +++ 4 files changed, 99 insertions(+), 7 deletions(-) create mode 100644 changes/bug8435 diff --git a/changes/bug8435 b/changes/bug8435 new file mode 100644 index 000000000..da7ca7c1f --- /dev/null +++ b/changes/bug8435 @@ -0,0 +1,4 @@ + o Major bugfixes: + - When dirserv.c computes flags and thresholds, ignore advertised + bandwidths if we have more than a threshold number of routers with + measured bandwidths. diff --git a/src/or/config.c b/src/or/config.c index f88842624..f3e408318 100644 --- a/src/or/config.c +++ b/src/or/config.c @@ -299,6 +299,7 @@ static config_var_t option_vars_[] = { V(MaxClientCircuitsPending, UINT, "32"), OBSOLETE("MaxOnionsPending"), V(MaxOnionQueueDelay, MSEC_INTERVAL, "1750 msec"), + V(MinMeasuredBWsForAuthToIgnoreAdvertised, INT, "500"), OBSOLETE("MonthlyAccountingStart"), V(MyFamily, STRING, NULL), V(NewCircuitPeriod, INTERVAL, "30 seconds"), diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 37934a032..c769beda8 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -66,6 +66,9 @@ static cached_dir_t *the_directory = NULL; /** For authoritative directories: the current (v1) network status. */ static cached_dir_t the_runningrouters; +/** Total number of routers with measured bandwidth */ +static int routers_with_measured_bw = 0; + static void directory_remove_invalid(void); static cached_dir_t *dirserv_regenerate_directory(void); static char *format_versions_list(config_line_t *ln); @@ -86,6 +89,7 @@ static const signed_descriptor_t *get_signed_descriptor_by_fp( static was_router_added_t dirserv_add_extrainfo(extrainfo_t *ei, const char **msg); static uint32_t dirserv_get_bandwidth_for_router(const routerinfo_t *ri); +static uint32_t dirserv_get_credible_bandwidth(const routerinfo_t *ri); /************** Fingerprint handling code ************/ @@ -1877,12 +1881,18 @@ dirserv_thinks_router_is_hs_dir(const routerinfo_t *router, * include a router in our calculations, and return true iff we should. */ static int router_counts_toward_thresholds(const node_t *node, time_t now, - const digestmap_t *omit_as_sybil) + const digestmap_t *omit_as_sybil, + int require_mbw) { + /* Have measured bw? */ + int have_mbw = + dirserv_query_measured_bw_cache(node->ri->cache_info.identity_digest, + NULL, NULL); + return node->ri && router_is_active(node->ri, node, now) && !digestmap_get(omit_as_sybil, node->ri->cache_info.identity_digest) && - (dirserv_get_bandwidth_for_router(node->ri) >= - ABSOLUTE_MIN_BW_VALUE_TO_CONSIDER); + (dirserv_get_credible_bandwidth(node->ri) >= + ABSOLUTE_MIN_BW_VALUE_TO_CONSIDER) && (have_mbw || !require_mbw); } /** Look through the routerlist, the Mean Time Between Failure history, and @@ -1904,6 +1914,11 @@ dirserv_compute_performance_thresholds(routerlist_t *rl, time_t now = time(NULL); const or_options_t *options = get_options(); + /* Require mbw? */ + int require_mbw = + (routers_with_measured_bw > + options->MinMeasuredBWsForAuthToIgnoreAdvertised) ? 1 : 0; + /* initialize these all here, in case there are no routers */ stable_uptime = 0; stable_mtbf = 0; @@ -1936,7 +1951,8 @@ dirserv_compute_performance_thresholds(routerlist_t *rl, /* Now, fill in the arrays. */ SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), node_t *, node) { - if (router_counts_toward_thresholds(node, now, omit_as_sybil)) { + if (router_counts_toward_thresholds(node, now, omit_as_sybil, + require_mbw)) { routerinfo_t *ri = node->ri; const char *id = ri->cache_info.identity_digest; uint32_t bw; @@ -1945,7 +1961,7 @@ dirserv_compute_performance_thresholds(routerlist_t *rl, uptimes[n_active] = (uint32_t)real_uptime(ri, now); mtbfs[n_active] = rep_hist_get_stability(id, now); tks [n_active] = rep_hist_get_weighted_time_known(id, now); - bandwidths[n_active] = bw = dirserv_get_bandwidth_for_router(ri); + bandwidths[n_active] = bw = dirserv_get_credible_bandwidth(ri); total_bandwidth += bw; if (node->is_exit && !node->is_bad_exit) { total_exit_bandwidth += bw; @@ -2001,7 +2017,8 @@ dirserv_compute_performance_thresholds(routerlist_t *rl, n_familiar = 0; SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), node_t *, node) { - if (router_counts_toward_thresholds(node, now, omit_as_sybil)) { + if (router_counts_toward_thresholds(node, now, + omit_as_sybil, require_mbw)) { routerinfo_t *ri = node->ri; const char *id = ri->cache_info.identity_digest; long tk = rep_hist_get_weighted_time_known(id, now); @@ -2182,6 +2199,59 @@ dirserv_get_bandwidth_for_router(const routerinfo_t *ri) return bw; } +/** Look through the routerlist, and using the measured bandwidth cache count + * how many measured bandwidths we know. This is used to decide whether we + * ever trust advertised bandwidths for purposes of assigning flags. */ +static void +dirserv_count_measured_bws(routerlist_t *rl) +{ + /* Initialize this first */ + routers_with_measured_bw = 0; + + tor_assert(rl); + tor_assert(rl->routers); + + /* Iterate over the routerlist and count measured bandwidths */ + SMARTLIST_FOREACH_BEGIN(rl->routers, routerinfo_t *, ri) { + /* Check if we know a measured bandwidth for this one */ + if (dirserv_query_measured_bw_cache(ri->cache_info.identity_digest, + NULL, NULL)) { + ++routers_with_measured_bw; + } + } SMARTLIST_FOREACH_END(ri); +} + +/** Return the bandwidth we believe for assigning flags; prefer measured + * over advertised, and if we have above a threshold quantity of measured + * bandwidths, we don't want to ever give flags to unmeasured routers, so + * return 0. */ +static uint32_t +dirserv_get_credible_bandwidth(const routerinfo_t *ri) +{ + int threshold; + uint32_t bw = 0; + long mbw; + + tor_assert(ri); + /* Check if we have a measured bandwidth, and check the threshold if not */ + if (!(dirserv_query_measured_bw_cache(ri->cache_info.identity_digest, + &mbw, NULL))) { + threshold = get_options()->MinMeasuredBWsForAuthToIgnoreAdvertised; + if (routers_with_measured_bw > threshold) { + /* Return zero for unmeasured bandwidth if we are above threshold */ + bw = 0; + } else { + /* Return an advertised bandwidth otherwise */ + bw = router_get_advertised_bandwidth(ri); + } + } else { + /* We have the measured bandwidth in mbw */ + bw = (uint32_t)mbw; + } + + return bw; +} + /** Give a statement of our current performance thresholds for inclusion * in a vote document. */ char * @@ -2604,7 +2674,7 @@ set_routerstatus_from_routerinfo(routerstatus_t *rs, int listbaddirs, int vote_on_hsdirs) { const or_options_t *options = get_options(); - uint32_t routerbw = dirserv_get_bandwidth_for_router(ri); + uint32_t routerbw = dirserv_get_credible_bandwidth(ri); memset(rs, 0, sizeof(routerstatus_t)); @@ -2927,6 +2997,14 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, */ if (options->V3BandwidthsFile) { dirserv_read_measured_bandwidths(options->V3BandwidthsFile, NULL); + } else { + /* + * No bandwidths file; clear the measured bandwidth cache in case we had + * one last time around. + */ + if (dirserv_get_measured_bw_cache_size() > 0) { + dirserv_clear_measured_bw_cache(); + } } /* precompute this part, since we need it to decide what "stable" @@ -2945,6 +3023,10 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, rep_hist_make_router_pessimal(sybil_id, now); } DIGESTMAP_FOREACH_END; + /* Count how many have measured bandwidths so we know how to assign flags; + * this must come before dirserv_compute_performance_thresholds() */ + dirserv_count_measured_bws(rl); + dirserv_compute_performance_thresholds(rl, omit_as_sybil); routerstatuses = smartlist_new(); @@ -2989,6 +3071,7 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, smartlist_free(routers); digestmap_free(omit_as_sybil, NULL); + /* This pass through applies the measured bw lines to the routerstatuses */ if (options->V3BandwidthsFile) { dirserv_read_measured_bandwidths(options->V3BandwidthsFile, routerstatuses); diff --git a/src/or/or.h b/src/or/or.h index 45eb4673c..f2605d608 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -3870,6 +3870,10 @@ typedef struct { * consensus vote on the 'params' line. */ char *ConsensusParams; + /** Authority only: minimum number of measured bandwidths we must see + * before we only beliee measured bandwidths to assign flags. */ + int MinMeasuredBWsForAuthToIgnoreAdvertised; + /** The length of time that we think an initial consensus should be fresh. * Only altered on testing networks. */ int TestingV3AuthInitialVotingInterval; -- cgit v1.2.3 From d64e5969f470a18fe15a6a2863cf4b2b59b1bd27 Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Mon, 18 Mar 2013 11:56:42 -0700 Subject: Add dirserv_has_measured_bw() predicate wrapper for dirserv_query_measured_bw_cache() --- src/or/dirserv.c | 13 +++++++++---- src/or/dirserv.h | 1 + 2 files changed, 10 insertions(+), 4 deletions(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index c769beda8..47a4a7305 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -1886,8 +1886,7 @@ router_counts_toward_thresholds(const node_t *node, time_t now, { /* Have measured bw? */ int have_mbw = - dirserv_query_measured_bw_cache(node->ri->cache_info.identity_digest, - NULL, NULL); + dirserv_has_measured_bw(node->ri->cache_info.identity_digest); return node->ri && router_is_active(node->ri, node, now) && !digestmap_get(omit_as_sybil, node->ri->cache_info.identity_digest) && @@ -2166,6 +2165,13 @@ dirserv_query_measured_bw_cache(const char *node_id, long *bw_out, return rv; } +/** Predicate wrapper for dirserv_query_measured_bw_cache() */ +int +dirserv_has_measured_bw(const char *node_id) +{ + return dirserv_query_measured_bw_cache(node_id, NULL, NULL); +} + /** Get the best estimate of a router's bandwidth for dirauth purposes, * preferring measured to advertised values if available. */ @@ -2214,8 +2220,7 @@ dirserv_count_measured_bws(routerlist_t *rl) /* Iterate over the routerlist and count measured bandwidths */ SMARTLIST_FOREACH_BEGIN(rl->routers, routerinfo_t *, ri) { /* Check if we know a measured bandwidth for this one */ - if (dirserv_query_measured_bw_cache(ri->cache_info.identity_digest, - NULL, NULL)) { + if (dirserv_has_measured_bw(ri->cache_info.identity_digest)) { ++routers_with_measured_bw; } } SMARTLIST_FOREACH_END(ri); diff --git a/src/or/dirserv.h b/src/or/dirserv.h index 887a4992e..8728a0b70 100644 --- a/src/or/dirserv.h +++ b/src/or/dirserv.h @@ -154,6 +154,7 @@ void dirserv_expire_measured_bw_cache(time_t now); int dirserv_get_measured_bw_cache_size(void); int dirserv_query_measured_bw_cache(const char *node_id, long *bw_out, time_t *as_of_out); +int dirserv_has_measured_bw(const char *node_id); #endif int dirserv_read_measured_bandwidths(const char *from_file, -- cgit v1.2.3 From e9bdb695e82320fd320ba7e9c716ebdc51bfdeb0 Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Mon, 18 Mar 2013 11:58:30 -0700 Subject: Improve comment on router_counts_toward_thresholds() --- src/or/dirserv.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 47a4a7305..cf11e5013 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -1878,7 +1878,10 @@ dirserv_thinks_router_is_hs_dir(const routerinfo_t *router, #define ABSOLUTE_MIN_BW_VALUE_TO_CONSIDER 4096 /** Helper for dirserv_compute_performance_thresholds(): Decide whether to - * include a router in our calculations, and return true iff we should. */ + * include a router in our calculations, and return true iff we should; the + * require_mbw parameter is passed in by + * dirserv_compute_performance_thresholds() and controls whether we ever + * count routers with only advertised bandwidths */ static int router_counts_toward_thresholds(const node_t *node, time_t now, const digestmap_t *omit_as_sybil, -- cgit v1.2.3 From 0164f16f70d17da202c8085e620e9cf043eda0b3 Mon Sep 17 00:00:00 2001 From: Andrea Shepard Date: Mon, 18 Mar 2013 12:04:41 -0700 Subject: Improve comment for routers_with_measured_bw static var in dirserv.c --- src/or/dirserv.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index cf11e5013..5aed3fb6b 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -66,7 +66,11 @@ static cached_dir_t *the_directory = NULL; /** For authoritative directories: the current (v1) network status. */ static cached_dir_t the_runningrouters; -/** Total number of routers with measured bandwidth */ +/** Total number of routers with measured bandwidth; this is set by + * dirserv_count_measured_bws() before the loop in + * dirserv_generate_networkstatus_vote_obj() and checked by + * dirserv_get_credible_bandwidth() and + * dirserv_compute_performance_thresholds() */ static int routers_with_measured_bw = 0; static void directory_remove_invalid(void); -- cgit v1.2.3