diff options
| -rw-r--r-- | src/or/directory.c | 2 | ||||
| -rw-r--r-- | src/or/or.h | 12 | ||||
| -rw-r--r-- | src/or/routerlist.c | 123 |
3 files changed, 88 insertions, 49 deletions
diff --git a/src/or/directory.c b/src/or/directory.c index 771a776a6..8dade1a44 100644 --- a/src/or/directory.c +++ b/src/or/directory.c @@ -1557,7 +1557,7 @@ static void dir_routerdesc_download_failed(smartlist_t *failed) { char digest[DIGEST_LEN]; - routerstatus_t *rs; + local_routerstatus_t *rs; SMARTLIST_FOREACH(failed, const char *, cp, { base16_decode(digest, DIGEST_LEN, cp, strlen(cp)); diff --git a/src/or/or.h b/src/or/or.h index f5d4b4122..485fc171f 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -800,11 +800,15 @@ typedef struct routerstatus_t { unsigned int is_running:1; /**< True iff this router is up. */ unsigned int is_named:1; /**< True iff "nickname" belongs to this router. */ unsigned int is_valid:1; /**< True iff this router is validated. */ - uint8_t n_download_failures; /**< Only used in summary list: number of - * failures trying to download the most - * recent descriptor. */ } routerstatus_t; +/** DOCDOC */ +typedef struct local_routerstatus_t { + routerstatus_t status; + uint8_t n_download_failures; /**< Number of failures trying to download the + * most recent descriptor. */ +} local_routerstatus_t; + /*XXXX011 make this configurable? */ #define MAX_ROUTERDESC_DOWNLOAD_FAILURES 8 @@ -2116,7 +2120,7 @@ void add_trusted_dir_server(const char *addr, uint16_t port, const char *digest, int supports_v1); void clear_trusted_dir_servers(void); networkstatus_t *networkstatus_get_by_digest(const char *digest); -routerstatus_t *router_get_combined_status_by_digest(const char *digest); +local_routerstatus_t *router_get_combined_status_by_digest(const char *digest); void update_networkstatus_cache_downloads(time_t now); void update_networkstatus_client_downloads(time_t now); void update_router_descriptor_downloads(time_t now); diff --git a/src/or/routerlist.c b/src/or/routerlist.c index f47ca2674..5f9b5ad07 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -1554,7 +1554,7 @@ networkstatus_find_entry(networkstatus_t *ns, const char *digest) } /*DOCDOC*/ -routerstatus_t * +local_routerstatus_t * router_get_combined_status_by_digest(const char *digest) { if (!routerstatus_list) @@ -2133,8 +2133,9 @@ routerstatus_list_update_from_networkstatus(time_t now) int n_trusted, n_statuses, n_recent=0, n_naming=0; int n_distinct = 0; int i; - smartlist_t *all_statuses, *result; - routerstatus_t *prev_rs; + int *index, *size; + networkstatus_t **networkstatus; + smartlist_t *result; networkstatus_list_update_recent(now); @@ -2159,37 +2160,66 @@ routerstatus_list_update_from_networkstatus(time_t now) log_fn(LOG_NOTICE, "rebuilding router status list."); - all_statuses = smartlist_create(); - result = smartlist_create(); - - SMARTLIST_FOREACH(networkstatus_list, networkstatus_t *, ns, - { - if (ns->binds_names) + index = tor_malloc(sizeof(int)*n_statuses); + size = tor_malloc(sizeof(int)*n_statuses); + networkstatus = tor_malloc(sizeof(networkstatus_t *)*n_statuses); + for (i = 0; i < n_statuses; ++i) { + index[i] = 0; + networkstatus[i] = smartlist_get(networkstatus_list, i); + size[i] = smartlist_len(networkstatus[i]->entries); + if (networkstatus[i]->binds_names) ++n_naming; - if (ns->is_recent) + if (networkstatus[i]->is_recent) ++n_recent; - smartlist_add_all(all_statuses, ns->entries); - }); + } - sort_routerstatus_entries(all_statuses); - for (i=0; i < smartlist_len(all_statuses); ++i) { + result = smartlist_create(); + + /* Iterate through all of the sorted routerstatus lists in step. + * Invariants: + * - For 0 <= i < n_statuses: index[i] is an index into + * networkstatus[i]->entries, which has size[i] elements. + * - For i1, i2, j such that 0 <= i1 < n_statuses, 0 <= i2 < n_statues, 0 <= + * j < index[i1], networkstatus[i1]->entries[j]->identity_digest < + * networkstatus[i2]->entries[index[i2]]->identity_digest. + * + * (That is, the indices are always advanced past lower digest before + * higher.) + */ + while (1) { int n_running=0, n_named=0, n_valid=0, n_listing=0; const char *the_name = NULL; - routerstatus_t *d_rs = smartlist_get(all_statuses, i); - routerstatus_t *rs_out, *rs, *most_recent; - if (i>0 && ! memcmp(d_rs->identity_digest, - ((routerstatus_t*)smartlist_get(all_statuses,i-1))->identity_digest, - DIGEST_LEN)) - continue; + local_routerstatus_t *rs_out, *rs_old; + routerstatus_t *rs, *most_recent; + networkstatus_t *ns; + const char *lowest = NULL; + /* Find out which of the digests appears first. */ + for (i = 0; i < n_statuses; ++i) { + if (index[i] < size[i]) { + rs = smartlist_get(networkstatus[i]->entries, index[i]); + if (!lowest || memcmp(rs->identity_digest, lowest, DIGEST_LEN)<0) + lowest = rs->identity_digest; + } + } + if (!lowest) { + /* We're out of routers. Great! */ + break; + } + /* Okay. The routers at networkstatus[i]->entries[index[i]] whose digests + * match "lowest" are next in order. Iterate over them, incrementing those + * index[i] as we go. */ ++n_distinct; - prev_rs = most_recent = d_rs; - SMARTLIST_FOREACH(networkstatus_list, networkstatus_t *, ns, - { - rs = networkstatus_find_entry(ns, d_rs->identity_digest); - if (!rs) + most_recent = NULL; + for (i = 0; i < n_statuses; ++i) { + if (index[i] >= size[i]) continue; + ns = networkstatus[i]; + rs = smartlist_get(ns->entries, index[i]); + if (memcmp(rs->identity_digest, lowest, DIGEST_LEN)) + continue; + ++index[i]; ++n_listing; - if (rs->published_on > most_recent->published_on) + if (!most_recent || rs->published_on > most_recent->published_on) most_recent = rs; if (rs->is_named && ns->binds_names) { if (!the_name) @@ -2204,31 +2234,35 @@ routerstatus_list_update_from_networkstatus(time_t now) ++n_valid; if (rs->is_running && ns->is_recent) ++n_running; - }); - rs_out = tor_malloc(sizeof(routerstatus_t)); - memcpy(rs_out, most_recent, sizeof(routerstatus_t)); - if ((rs = router_get_combined_status_by_digest(d_rs->identity_digest))) { - rs_out->n_download_failures = rs->n_download_failures; + } + rs_out = tor_malloc(sizeof(local_routerstatus_t)); + memcpy(&rs_out->status, most_recent, sizeof(routerstatus_t)); + if ((rs_old = router_get_combined_status_by_digest(lowest))) { + rs_out->n_download_failures = rs_old->n_download_failures; } smartlist_add(result, rs_out); log_fn(LOG_DEBUG, "Router '%s' is listed by %d/%d directories, " "named by %d/%d, validated by %d/%d, and %d/%d recent directories " "think it's running.", - rs_out->nickname, + rs_out->status.nickname, n_listing, n_statuses, n_named, n_naming, n_valid, n_statuses, n_running, n_recent); - rs_out->is_named = the_name && strcmp(the_name, "**mismatch**") && + rs_out->status.is_named = the_name && strcmp(the_name, "**mismatch**") && n_named > n_naming/2; - if (rs_out->is_named) - strlcpy(rs_out->nickname, the_name, sizeof(rs_out->nickname)); - rs_out->is_valid = n_valid > n_statuses/2; - rs_out->is_running = n_running > n_recent/2; + if (rs_out->status.is_named) + strlcpy(rs_out->status.nickname, the_name, sizeof(rs_out->status.nickname)); + rs_out->status.is_valid = n_valid > n_statuses/2; + rs_out->status.is_running = n_running > n_recent/2; } SMARTLIST_FOREACH(routerstatus_list, routerstatus_t *, rs, routerstatus_free(rs)); smartlist_free(routerstatus_list); routerstatus_list = result; + tor_free(networkstatus); + tor_free(index); + tor_free(size); + networkstatus_list_has_changed = 0; routerstatus_list_has_changed = 1; } @@ -2240,7 +2274,7 @@ void routers_update_status_from_networkstatus(smartlist_t *routers, int reset_failures) { trusted_dir_server_t *ds; - routerstatus_t *rs; + local_routerstatus_t *rs; or_options_t *options = get_options(); int authdir = options->AuthoritativeDir; int namingdir = options->NamingAuthoritativeDir; @@ -2260,12 +2294,12 @@ routers_update_status_from_networkstatus(smartlist_t *routers, int reset_failure rs->n_download_failures = 0; if (!namingdir) - router->is_named = rs->is_named; + router->is_named = rs->status.is_named; if (!authdir) { /* If we're an authdir, don't believe others. */ - router->is_verified = rs->is_valid; - router->is_running = rs->is_running; + router->is_verified = rs->status.is_valid; + router->is_running = rs->status.is_running; if (router->is_running && ds) { /* XXXX011 NM Hm. What about authorities? When do they reset @@ -2286,7 +2320,6 @@ router_list_downloadable(void) { smartlist_t *superseded = smartlist_create(); strmap_iter_t *iter; - routerstatus_t *rs; time_t now = time(NULL); strmap_t *status_map = NULL; char fp[HEX_DIGEST_LEN+1]; @@ -2297,15 +2330,16 @@ router_list_downloadable(void) routerstatus_list_update_from_networkstatus(now); status_map = strmap_new(); - SMARTLIST_FOREACH(routerstatus_list, routerstatus_t *, rs, + SMARTLIST_FOREACH(routerstatus_list, local_routerstatus_t *, rs, { - base16_encode(fp, sizeof(fp), rs->identity_digest, DIGEST_LEN); + base16_encode(fp, sizeof(fp), rs->status.identity_digest, DIGEST_LEN); strmap_set(status_map, fp, rs); }); if (routerlist) { SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, ri, { + routerstatus_t *rs; base16_encode(fp, sizeof(fp), ri->identity_digest, DIGEST_LEN); if (!(rs = strmap_get(status_map, fp))) { // log_fn(LOG_NOTICE, "No status for %s", fp); @@ -2341,6 +2375,7 @@ router_list_downloadable(void) iter = strmap_iter_next(status_map, iter)) { const char *key; void *val; + local_routerstatus_t *rs; strmap_iter_get(iter, &key, &val); rs = val; if (rs->n_download_failures >= MAX_ROUTERDESC_DOWNLOAD_FAILURES) |