commit 0d78a16c3642f7538266e007da79c39860aac332 Merge: 9c72324 5a4f7fa Author: Nick Mathewson nickm@torproject.org Date: Tue Mar 8 15:52:43 2011 -0500

Merge remote branch 'sebastian/bug1035' into maint-0.2.2

changes/bug1035 | 13 +++++++++ src/or/connection_or.c | 3 -- src/or/dirserv.c | 18 +++++++++--- src/or/rephist.c | 65 ++++++++++++++++++++++++++++++++++++++++++------ src/or/rephist.h | 3 +- 5 files changed, 85 insertions(+), 17 deletions(-)

diff --combined src/or/connection_or.c index b93699c,6279c93..2d24444 --- a/src/or/connection_or.c +++ b/src/or/connection_or.c @@@ -1,7 -1,7 +1,7 @@@ /* Copyright (c) 2001 Matej Pfajfar. * Copyright (c) 2001-2004, Roger Dingledine. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. - * Copyright (c) 2007-2010, The Tor Project, Inc. */ + * Copyright (c) 2007-2011, The Tor Project, Inc. */ /* See LICENSE for licensing information */

/** @@@ -370,11 -370,11 +370,11 @@@ connection_or_update_token_buckets_help * bandwidth parameters in the consensus, but allow local config * options to override. */ rate = options->PerConnBWRate ? (int)options->PerConnBWRate : - (int)networkstatus_get_param(NULL, "perconnbwrate", - (int)options->BandwidthRate); + networkstatus_get_param(NULL, "perconnbwrate", + (int)options->BandwidthRate, 1, INT32_MAX); burst = options->PerConnBWBurst ? (int)options->PerConnBWBurst : - (int)networkstatus_get_param(NULL, "perconnbwburst", - (int)options->BandwidthBurst); + networkstatus_get_param(NULL, "perconnbwburst", + (int)options->BandwidthBurst, 1, INT32_MAX); }

conn->bandwidthrate = rate; @@@ -1098,9 -1098,6 +1098,6 @@@ connection_or_check_valid_tls_handshake as_advertised = 0; } if (authdir_mode_tests_reachability(options)) { - /* We initiated this connection to address:port. Drop all routers - * with the same address:port and a different key. - */ dirserv_orconn_tls_done(conn->_base.address, conn->_base.port, digest_rcvd_out, as_advertised); } @@@ -1259,8 -1256,7 +1256,8 @@@ connection_or_write_var_cell_to_buf(con tor_assert(conn); var_cell_pack_header(cell, hdr); connection_write_to_buf(hdr, sizeof(hdr), TO_CONN(conn)); - connection_write_to_buf(cell->payload, cell->payload_len, TO_CONN(conn)); + connection_write_to_buf((char*)cell->payload, + cell->payload_len, TO_CONN(conn)); if (cell->command != CELL_PADDING) conn->timestamp_last_added_nonpadding = approx_time(); } @@@ -1389,7 -1385,7 +1386,7 @@@ connection_or_send_netinfo(or_connectio time_t now = time(NULL); routerinfo_t *me; int len; - char *out; + uint8_t *out;

memset(&cell, 0, sizeof(cell_t)); cell.command = CELL_NETINFO; diff --combined src/or/dirserv.c index 3c15c59,f426881..aeeab45 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@@ -1,6 -1,6 +1,6 @@@ /* Copyright (c) 2001-2004, Roger Dingledine. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. - * Copyright (c) 2007-2010, The Tor Project, Inc. */ + * Copyright (c) 2007-2011, The Tor Project, Inc. */ /* See LICENSE for licensing information */

#define DIRSERV_PRIVATE @@@ -386,19 -386,13 +386,19 @@@ dirserv_get_status_impl(const char *id_ strmap_size(fingerprint_list->fp_by_name), digestmap_size(fingerprint_list->status_by_digest));

- /* Tor 0.1.2.x is pretty old, but there are a lot of them running still, - * and there aren't any critical relay-side vulnerabilities. Once more - * of them die off, we should raise this minimum to 0.2.0.x. */ - if (platform && !tor_version_as_new_as(platform,"0.1.2.14")) { + /* Tor 0.2.0.26-rc is the oldest version that currently caches the right + * directory information. Once more of them die off, we should raise this + * minimum. */ + if (platform && !tor_version_as_new_as(platform,"0.2.0.26-rc")) { if (msg) *msg = "Tor version is far too old to work."; return FP_REJECT; + } else if (platform && tor_version_as_new_as(platform,"0.2.1.3-alpha") + && !tor_version_as_new_as(platform, "0.2.1.19")) { + /* These versions mishandled RELAY_EARLY cells on rend circuits. */ + if (msg) + *msg = "Tor version is too buggy to work."; + return FP_REJECT; }

result = dirserv_get_name_status(id_digest, nickname); @@@ -1166,7 -1160,7 +1166,7 @@@ directory_fetches_from_authorities(or_o return 0; if (server_mode(options) && router_pick_published_address(options, &addr)<0) return 1; /* we don't know our IP address; ask an authority. */ - refuseunknown = router_my_exit_policy_is_reject_star() && + refuseunknown = ! router_my_exit_policy_is_reject_star() && should_refuse_unknown_exits(options); if (options->DirPort == 0 && !refuseunknown) return 0; @@@ -2970,8 -2964,6 +2970,8 @@@ dirserv_get_routerdesc_fingerprints(sma SMARTLIST_FOREACH(rl->routers, routerinfo_t *, r, smartlist_add(fps_out, tor_memdup(r->cache_info.identity_digest, DIGEST_LEN))); + /* Treat "all" requests as if they were unencrypted */ + for_unencrypted_conn = 1; } else if (!strcmp(key, "authority")) { routerinfo_t *ri = router_get_my_routerinfo(); if (ri) @@@ -3116,19 -3108,27 +3116,27 @@@ dirserv_orconn_tls_done(const char *add tor_assert(address); tor_assert(digest_rcvd);

- SMARTLIST_FOREACH(rl->routers, routerinfo_t *, ri, { + /* XXX023 Doing a loop like this is stupid. We should just look up the + * router by digest_rcvd, and see if address, orport, and as_advertised + * match up. -NM */ + SMARTLIST_FOREACH_BEGIN(rl->routers, routerinfo_t *, ri) { if (!strcasecmp(address, ri->address) && or_port == ri->or_port && as_advertised && !memcmp(ri->cache_info.identity_digest, digest_rcvd, DIGEST_LEN)) { /* correct digest. mark this router reachable! */ if (!bridge_auth || ri->purpose == ROUTER_PURPOSE_BRIDGE) { - log_info(LD_DIRSERV, "Found router %s to be reachable. Yay.", - ri->nickname); - rep_hist_note_router_reachable(digest_rcvd, now); + tor_addr_t addr, *addrp=NULL; + log_info(LD_DIRSERV, "Found router %s to be reachable at %s:%d. Yay.", + ri->nickname, address, ri->or_port ); + if (tor_addr_from_str(&addr, ri->address) != -1) + addrp = &addr; + else + log_warn(LD_BUG, "Couldn't parse IP address "%s"", ri->address); + rep_hist_note_router_reachable(digest_rcvd, addrp, or_port, now); ri->last_reachable = now; } } - }); + } SMARTLIST_FOREACH_END(ri); /* FFFF Maybe we should reinstate the code that dumps routers with the same * addr/port but with nonmatching keys, but instead of dumping, we should * skip testing. */ diff --combined src/or/rephist.c index 61ae2c3,207eb88..53214d6 --- a/src/or/rephist.c +++ b/src/or/rephist.c @@@ -1,5 -1,5 +1,5 @@@ /* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. - * Copyright (c) 2007-2010, The Tor Project, Inc. */ + * Copyright (c) 2007-2011, The Tor Project, Inc. */ /* See LICENSE for licensing information */

/** @@@ -14,6 -14,7 +14,7 @@@ #include "circuitlist.h" #include "circuituse.h" #include "config.h" + #include "networkstatus.h" #include "rephist.h" #include "router.h" #include "routerlist.h" @@@ -73,6 -74,13 +74,13 @@@ typedef struct or_history_t /** If nonzero, we have been unable to connect since this time. */ time_t down_since;

+ /** The address at which we most recently connected to this OR + * successfully. */ + tor_addr_t last_reached_addr; + + /** The port at which we most recently connected to this OR successfully */ + uint16_t last_reached_port; + /* === For MTBF tracking: */ /** Weighted sum total of all times that this router has been online. */ @@@ -119,6 -127,7 +127,7 @@@ get_or_history(const char* id rephist_total_num++; hist->link_history_map = digestmap_new(); hist->since = hist->changed = time(NULL); + tor_addr_make_unspec(&hist->last_reached_addr); digestmap_set(history_map, id, hist); } return hist; @@@ -289,13 -298,20 +298,20 @@@ rep_hist_note_connection_died(const cha /** We have just decided that this router with identity digest <b>id</b> is * reachable, meaning we will give it a "Running" flag for the next while. */ void - rep_hist_note_router_reachable(const char *id, time_t when) + rep_hist_note_router_reachable(const char *id, const tor_addr_t *at_addr, + const uint16_t at_port, time_t when) { or_history_t *hist = get_or_history(id); int was_in_run = 1; char tbuf[ISO_TIME_LEN+1]; + int addr_changed, port_changed;

tor_assert(hist); + tor_assert((!at_addr && !at_port) || (at_addr && at_port)); + + addr_changed = at_addr && + tor_addr_compare(at_addr, &hist->last_reached_addr, CMP_EXACT) != 0; + port_changed = at_port && at_port != hist->last_reached_port;

if (!started_tracking_stability) started_tracking_stability = time(NULL); @@@ -315,6 -331,27 +331,27 @@@ down_length = when - hist->start_of_downtime; hist->total_weighted_time += down_length; hist->start_of_downtime = 0; + } else if (addr_changed || port_changed) { + /* If we're reachable, but the address changed, treat this as some + * downtime. */ + int penalty = get_options()->TestingTorNetwork ? 240 : 3600; + networkstatus_t *ns; + + if ((ns = networkstatus_get_latest_consensus())) { + int fresh_interval = (int)(ns->fresh_until - ns->valid_after); + int live_interval = (int)(ns->valid_until - ns->valid_after); + /* on average, a descriptor addr change takes .5 intervals to make it + * into a consensus, and half a liveness period to make it to + * clients. */ + penalty = (int)(fresh_interval + live_interval) / 2; + } + format_local_iso_time(tbuf, hist->start_of_run); + log_info(LD_HIST,"Router %s still seems Running, but its address appears " + "to have changed since the last time it was reachable. I'm " + "going to treat it as having been down for %d seconds", + hex_str(id, DIGEST_LEN), penalty); + rep_hist_note_router_unreachable(id, when-penalty); + rep_hist_note_router_reachable(id, NULL, 0, when); } else { format_local_iso_time(tbuf, hist->start_of_run); if (was_in_run) @@@ -324,6 -361,10 +361,10 @@@ log_info(LD_HIST,"Router %s is now Running; it was previously untracked", hex_str(id, DIGEST_LEN)); } + if (at_addr) + tor_addr_copy(&hist->last_reached_addr, at_addr); + if (at_port) + hist->last_reached_port = at_port; }

/** We have just decided that this router is unreachable, meaning @@@ -344,12 -385,20 +385,20 @@@ rep_hist_note_router_unreachable(const long run_length = when - hist->start_of_run; format_local_iso_time(tbuf, hist->start_of_run);

- hist->weighted_run_length += run_length; hist->total_run_weights += 1.0; hist->start_of_run = 0; - hist->weighted_uptime += run_length; - hist->total_weighted_time += run_length; - + if (run_length < 0) { + unsigned long penalty = -run_length; + #define SUBTRACT_CLAMPED(var, penalty) \ + do { (var) = (var) < (penalty) ? 0 : (var) - (penalty); } while (0) + + SUBTRACT_CLAMPED(hist->weighted_run_length, penalty); + SUBTRACT_CLAMPED(hist->weighted_uptime, penalty); + } else { + hist->weighted_run_length += run_length; + hist->weighted_uptime += run_length; + hist->total_weighted_time += run_length; + } was_running = 1; log_info(LD_HIST, "Router %s is now non-Running: it had previously been " "Running since %s. Its total weighted uptime is %lu/%lu.", @@@ -422,7 -471,7 +471,7 @@@ rep_hist_downrate_old_runs(time_t now static double get_stability(or_history_t *hist, time_t when) { - unsigned long total = hist->weighted_run_length; + long total = hist->weighted_run_length; double total_weights = hist->total_run_weights;

if (hist->start_of_run) { @@@ -458,8 -507,8 +507,8 @@@ get_total_weighted_time(or_history_t *h static double get_weighted_fractional_uptime(or_history_t *hist, time_t when) { - unsigned long total = hist->total_weighted_time; - unsigned long up = hist->weighted_uptime; + long total = hist->total_weighted_time; + long up = hist->weighted_uptime;

if (hist->start_of_run) { long run_length = (when - hist->start_of_run); @@@ -1165,8 -1214,6 +1214,8 @@@ rep_hist_load_mtbf_data(time_t now * totals? */ #define NUM_SECS_ROLLING_MEASURE 10 /** How large are the intervals for which we track and report bandwidth use? */ +/* XXXX Watch out! Before Tor 0.2.2.21-alpha, using any other value here would + * generate an unparseable state file. */ #define NUM_SECS_BW_SUM_INTERVAL (15*60) /** How far in the past do we remember and publish bandwidth use? */ #define NUM_SECS_BW_SUM_IS_VALID (24*60*60) @@@ -1261,12 -1308,8 +1310,12 @@@ add_obs(bw_array_t *b, time_t when, uin /* If we're currently adding observations for an earlier second than * 'when', advance b->cur_obs_time and b->cur_obs_idx by an * appropriate number of seconds, and do all the other housekeeping */ - while (when>b->cur_obs_time) + while (when>b->cur_obs_time) { + /* Doing this one second at a time is potentially inefficient, if we start + with a state file that is very old. Fortunately, it doesn't seem to + show up in profiles, so we can just ignore it for now. */ advance_obs(b); + }

b->obs[b->cur_obs_idx] += n; b->total_in_period += n; @@@ -1297,15 -1340,10 +1346,15 @@@ static bw_array_t *dir_read_array = NUL directory protocol. */ static bw_array_t *dir_write_array = NULL;

-/** Set up [dir-]read_array and [dir-]write_array. */ +/** Set up [dir-]read_array and [dir-]write_array, freeing them if they + * already exist. */ static void bw_arrays_init(void) { + tor_free(read_array); + tor_free(write_array); + tor_free(dir_read_array); + tor_free(dir_write_array); read_array = bw_array_new(); write_array = bw_array_new(); dir_read_array = bw_array_new(); @@@ -1403,7 -1441,7 +1452,7 @@@ rep_hist_bandwidth_assess(void * It returns the number of bytes written. */ static size_t -rep_hist_fill_bandwidth_history(char *buf, size_t len, bw_array_t *b) +rep_hist_fill_bandwidth_history(char *buf, size_t len, const bw_array_t *b) { char *cp = buf; int i, n; @@@ -1495,181 -1533,163 +1544,181 @@@ rep_hist_get_bandwidth_lines(void return buf; }

+/** Write a single bw_array_t into the Values, Ends, Interval, and Maximum + * entries of an or_state_t. */ +static void +rep_hist_update_bwhist_state_section(or_state_t *state, + const bw_array_t *b, + smartlist_t **s_values, + smartlist_t **s_maxima, + time_t *s_begins, + int *s_interval) +{ + char *cp; + int i,j; + + if (*s_values) { + SMARTLIST_FOREACH(*s_values, char *, val, tor_free(val)); + smartlist_free(*s_values); + } + if (*s_maxima) { + SMARTLIST_FOREACH(*s_maxima, char *, val, tor_free(val)); + smartlist_free(*s_maxima); + } + if (! server_mode(get_options())) { + /* Clients don't need to store bandwidth history persistently; + * force these values to the defaults. */ + /* FFFF we should pull the default out of config.c's state table, + * so we don't have two defaults. */ + if (*s_begins != 0 || *s_interval != 900) { + time_t now = time(NULL); + time_t save_at = get_options()->AvoidDiskWrites ? now+3600 : now+600; + or_state_mark_dirty(state, save_at); + } + *s_begins = 0; + *s_interval = 900; + *s_values = smartlist_create(); + *s_maxima = smartlist_create(); + return; + } + *s_begins = b->next_period; + *s_interval = NUM_SECS_BW_SUM_INTERVAL; + + *s_values = smartlist_create(); + *s_maxima = smartlist_create(); + /* Set i to first position in circular array */ + i = (b->num_maxes_set <= b->next_max_idx) ? 0 : b->next_max_idx; + for (j=0; j < b->num_maxes_set; ++j,++i) { + uint64_t maxval; + if (i >= NUM_TOTALS) + i = 0; + tor_asprintf(&cp, U64_FORMAT, U64_PRINTF_ARG(b->totals[i] & ~0x3ff)); + smartlist_add(*s_values, cp); + maxval = b->maxima[i] / NUM_SECS_ROLLING_MEASURE; + tor_asprintf(&cp, U64_FORMAT, U64_PRINTF_ARG(maxval & ~0x3ff)); + smartlist_add(*s_maxima, cp); + } + tor_asprintf(&cp, U64_FORMAT, U64_PRINTF_ARG(b->total_in_period & ~0x3ff)); + smartlist_add(*s_values, cp); + tor_asprintf(&cp, U64_FORMAT, U64_PRINTF_ARG(b->max_total & ~0x3ff)); + smartlist_add(*s_maxima, cp); +} + /** Update <b>state</b> with the newest bandwidth history. */ void rep_hist_update_state(or_state_t *state) { - int len, r; - char *buf, *cp; - smartlist_t **s_values = NULL; - time_t *s_begins = NULL; - int *s_interval = NULL; - bw_array_t *b = NULL; +#define UPDATE(arrname,st) \ + rep_hist_update_bwhist_state_section(state,\ + (arrname),\ + &state->BWHistory ## st ## Values, \ + &state->BWHistory ## st ## Maxima, \ + &state->BWHistory ## st ## Ends, \ + &state->BWHistory ## st ## Interval)

- len = 20*NUM_TOTALS+1; - buf = tor_malloc_zero(len); + UPDATE(write_array, Write); + UPDATE(read_array, Read); + UPDATE(dir_write_array, DirWrite); + UPDATE(dir_read_array, DirRead);

- for (r=0;r<4;++r) { - switch (r) { - case 0: - b = write_array; - s_begins = &state->BWHistoryWriteEnds; - s_interval = &state->BWHistoryWriteInterval; - s_values = &state->BWHistoryWriteValues; - break; - case 1: - b = read_array; - s_begins = &state->BWHistoryReadEnds; - s_interval = &state->BWHistoryReadInterval; - s_values = &state->BWHistoryReadValues; - break; - case 2: - b = dir_write_array; - s_begins = &state->BWHistoryDirWriteEnds; - s_interval = &state->BWHistoryDirWriteInterval; - s_values = &state->BWHistoryDirWriteValues; - break; - case 3: - b = dir_read_array; - s_begins = &state->BWHistoryDirReadEnds; - s_interval = &state->BWHistoryDirReadInterval; - s_values = &state->BWHistoryDirReadValues; - break; - } - if (*s_values) { - SMARTLIST_FOREACH(*s_values, char *, val, tor_free(val)); - smartlist_free(*s_values); - } - if (! server_mode(get_options())) { - /* Clients don't need to store bandwidth history persistently; - * force these values to the defaults. */ - /* FFFF we should pull the default out of config.c's state table, - * so we don't have two defaults. */ - if (*s_begins != 0 || *s_interval != 900) { - time_t now = time(NULL); - time_t save_at = get_options()->AvoidDiskWrites ? now+3600 : now+600; - or_state_mark_dirty(state, save_at); - } - *s_begins = 0; - *s_interval = 900; - *s_values = smartlist_create(); - continue; - } - *s_begins = b->next_period; - *s_interval = NUM_SECS_BW_SUM_INTERVAL; - cp = buf; - cp += rep_hist_fill_bandwidth_history(cp, len, b); - tor_snprintf(cp, len-(cp-buf), cp == buf ? U64_FORMAT : ","U64_FORMAT, - U64_PRINTF_ARG(b->total_in_period)); - *s_values = smartlist_create(); - if (server_mode(get_options())) - smartlist_split_string(*s_values, buf, ",", SPLIT_SKIP_SPACE, 0); - } - tor_free(buf); if (server_mode(get_options())) { - or_state_mark_dirty(get_or_state(), time(NULL)+(2*3600)); + or_state_mark_dirty(state, time(NULL)+(2*3600)); } +#undef UPDATE }

-/** Set bandwidth history from our saved state. */ -int -rep_hist_load_state(or_state_t *state, char **err) +/** Load a single bw_array_t from its Values, Ends, Maxima, and Interval + * entries in an or_state_t. */ +static int +rep_hist_load_bwhist_state_section(bw_array_t *b, + const smartlist_t *s_values, + const smartlist_t *s_maxima, + const time_t s_begins, + const int s_interval) { - time_t s_begins = 0, start; time_t now = time(NULL); - uint64_t v; - int r,i,ok; - int all_ok = 1; - int s_interval = 0; - smartlist_t *s_values = NULL; - bw_array_t *b = NULL; - - /* Assert they already have been malloced */ - tor_assert(read_array && write_array); + int retval = 0; + time_t start;

- for (r=0;r<4;++r) { - switch (r) { - case 0: - b = write_array; - s_begins = state->BWHistoryWriteEnds; - s_interval = state->BWHistoryWriteInterval; - s_values = state->BWHistoryWriteValues; - break; - case 1: - b = read_array; - s_begins = state->BWHistoryReadEnds; - s_interval = state->BWHistoryReadInterval; - s_values = state->BWHistoryReadValues; - break; - case 2: - b = dir_write_array; - s_begins = state->BWHistoryDirWriteEnds; - s_interval = state->BWHistoryDirWriteInterval; - s_values = state->BWHistoryDirWriteValues; - break; - case 3: - b = dir_read_array; - s_begins = state->BWHistoryDirReadEnds; - s_interval = state->BWHistoryDirReadInterval; - s_values = state->BWHistoryDirReadValues; - break; - } - if (s_values && s_begins >= now - NUM_SECS_BW_SUM_INTERVAL*NUM_TOTALS) { - start = s_begins - s_interval*(smartlist_len(s_values)); - if (start > now) - continue; - b->cur_obs_time = start; - b->next_period = start + NUM_SECS_BW_SUM_INTERVAL; - SMARTLIST_FOREACH(s_values, char *, cp, { + uint64_t v, mv; + int i,ok,ok_m; + int have_maxima = (smartlist_len(s_values) == smartlist_len(s_maxima)); + + if (s_values && s_begins >= now - NUM_SECS_BW_SUM_INTERVAL*NUM_TOTALS) { + start = s_begins - s_interval*(smartlist_len(s_values)); + if (start > now) + return 0; + b->cur_obs_time = start; + b->next_period = start + NUM_SECS_BW_SUM_INTERVAL; + SMARTLIST_FOREACH_BEGIN(s_values, const char *, cp) { + const char *maxstr = NULL; v = tor_parse_uint64(cp, 10, 0, UINT64_MAX, &ok, NULL); + if (have_maxima) { + maxstr = smartlist_get(s_maxima, cp_sl_idx); + mv = tor_parse_uint64(maxstr, 10, 0, UINT64_MAX, &ok_m, NULL); + mv *= NUM_SECS_ROLLING_MEASURE; + } else { + /* No maxima known; guess average rate to be conservative. */ + mv = v / s_interval; + } if (!ok) { - all_ok=0; - log_notice(LD_HIST, "Could not parse '%s' into a number.'", cp); + retval = -1; + log_notice(LD_HIST, "Could not parse value '%s' into a number.'",cp); } + if (maxstr && !ok_m) { + retval = -1; + log_notice(LD_HIST, "Could not parse maximum '%s' into a number.'", + maxstr); + } + if (start < now) { add_obs(b, start, v); - start += NUM_SECS_BW_SUM_INTERVAL; + b->max_total = mv; + /* This will result in some fairly choppy history if s_interval + * is notthe same as NUM_SECS_BW_SUM_INTERVAL. XXXX */ + start += s_interval; } - }); - } + } SMARTLIST_FOREACH_END(cp); + }

- /* Clean up maxima and observed */ - /* Do we really want to zero this for the purpose of max capacity? */ - for (i=0; i<NUM_SECS_ROLLING_MEASURE; ++i) { - b->obs[i] = 0; - } - b->total_obs = 0; - for (i=0; i<NUM_TOTALS; ++i) { - b->maxima[i] = 0; - } - b->max_total = 0; + /* Clean up maxima and observed */ + for (i=0; i<NUM_SECS_ROLLING_MEASURE; ++i) { + b->obs[i] = 0; } + b->total_obs = 0; + + return retval; +}

+/** Set bandwidth history from our saved state. */ +int +rep_hist_load_state(or_state_t *state, char **err) +{ + int all_ok = 1; + + /* Assert they already have been malloced */ + tor_assert(read_array && write_array); + tor_assert(dir_read_array && dir_write_array); + +#define LOAD(arrname,st) \ + if (rep_hist_load_bwhist_state_section( \ + (arrname), \ + state->BWHistory ## st ## Values, \ + state->BWHistory ## st ## Maxima, \ + state->BWHistory ## st ## Ends, \ + state->BWHistory ## st ## Interval)<0) \ + all_ok = 0 + + LOAD(write_array, Write); + LOAD(read_array, Read); + LOAD(dir_write_array, DirWrite); + LOAD(dir_read_array, DirRead); + +#undef LOAD if (!all_ok) { *err = tor_strdup("Parsing of bandwidth history values failed"); /* and create fresh arrays */ - tor_free(read_array); - tor_free(write_array); - read_array = bw_array_new(); - write_array = bw_array_new(); + bw_arrays_init(); return -1; } return 0; @@@ -1972,8 -1992,9 +2021,8 @@@ dump_pk_ops(int severity #define EXIT_STATS_ROUND_UP_STREAMS 4 /** Number of TCP ports */ #define EXIT_STATS_NUM_PORTS 65536 -/** Reciprocal of threshold (= 0.01%) of total bytes that a port needs to - * see in order to be included in exit stats. */ -#define EXIT_STATS_THRESHOLD_RECIPROCAL 10000 +/** Top n ports that will be included in exit stats. */ +#define EXIT_STATS_TOP_N_PORTS 10

/* The following data structures are arrays and no fancy smartlists or maps, * so that all write operations can be done in constant time. This comes at @@@ -2023,24 -2044,15 +2072,24 @@@ rep_hist_exit_stats_term(void tor_free(exit_streams); }

+/** Helper for qsort: compare two ints. */ +static int +_compare_int(const void *x, const void *y) +{ + return (*(int*)x - *(int*)y); +} + /** Return a newly allocated string containing the exit port statistics * until <b>now</b>, or NULL if we're not collecting exit stats. */ char * rep_hist_format_exit_stats(time_t now) { - int i; - uint64_t total_bytes = 0, threshold_bytes, other_read = 0, - other_written = 0; - uint32_t other_streams = 0; + int i, j, top_elements = 0, cur_min_idx = 0, cur_port; + uint64_t top_bytes[EXIT_STATS_TOP_N_PORTS]; + int top_ports[EXIT_STATS_TOP_N_PORTS]; + uint64_t cur_bytes = 0, other_read = 0, other_written = 0, + total_read = 0, total_written = 0; + uint32_t total_streams = 0, other_streams = 0; char *buf; smartlist_t *written_strings, *read_strings, *streams_strings; char *written_string, *read_string, *streams_string; @@@ -2050,101 -2062,52 +2099,101 @@@ if (!start_of_exit_stats_interval) return NULL; /* Not initialized. */

- /* Count total number of bytes, so that we can attribute observations - * below or equal to a threshold of 1 / EXIT_STATS_THRESHOLD_RECIPROCAL - * of all bytes to a special port 'other'. */ + /* Go through all ports to find the n ports that saw most written and + * read bytes. + * + * Invariant: at the end of the loop for iteration i, + * total_read is the sum of all exit_bytes_read[0..i] + * total_written is the sum of all exit_bytes_written[0..i] + * total_stream is the sum of all exit_streams[0..i] + * + * top_elements = MAX(EXIT_STATS_TOP_N_PORTS, + * #{j | 0 <= j <= i && volume(i) > 0}) + * + * For all 0 <= j < top_elements, + * top_bytes[j] > 0 + * 0 <= top_ports[j] <= 65535 + * top_bytes[j] = volume(top_ports[j]) + * + * There is no j in 0..i and k in 0..top_elements such that: + * volume(j) > top_bytes[k] AND j is not in top_ports[0..top_elements] + * + * There is no j!=cur_min_idx in 0..top_elements such that: + * top_bytes[j] < top_bytes[cur_min_idx] + * + * where volume(x) == exit_bytes_read[x]+exit_bytes_written[x] + * + * Worst case: O(EXIT_STATS_NUM_PORTS * EXIT_STATS_TOP_N_PORTS) + */ for (i = 1; i < EXIT_STATS_NUM_PORTS; i++) { - total_bytes += exit_bytes_read[i]; - total_bytes += exit_bytes_written[i]; + total_read += exit_bytes_read[i]; + total_written += exit_bytes_written[i]; + total_streams += exit_streams[i]; + cur_bytes = exit_bytes_read[i] + exit_bytes_written[i]; + if (cur_bytes == 0) { + continue; + } + if (top_elements < EXIT_STATS_TOP_N_PORTS) { + top_bytes[top_elements] = cur_bytes; + top_ports[top_elements++] = i; + } else if (cur_bytes > top_bytes[cur_min_idx]) { + top_bytes[cur_min_idx] = cur_bytes; + top_ports[cur_min_idx] = i; + } else { + continue; + } + cur_min_idx = 0; + for (j = 1; j < top_elements; j++) { + if (top_bytes[j] < top_bytes[cur_min_idx]) { + cur_min_idx = j; + } + } } - threshold_bytes = total_bytes / EXIT_STATS_THRESHOLD_RECIPROCAL;

- /* Add observations of all ports above the threshold to smartlists and - * join them to single strings. Also count bytes and streams of ports - * below or equal to the threshold. */ + /* Add observations of top ports to smartlists. */ written_strings = smartlist_create(); read_strings = smartlist_create(); streams_strings = smartlist_create(); - for (i = 1; i < EXIT_STATS_NUM_PORTS; i++) { - if (exit_bytes_read[i] + exit_bytes_written[i] > threshold_bytes) { - if (exit_bytes_written[i] > 0) { - uint64_t num = round_uint64_to_next_multiple_of( - exit_bytes_written[i], EXIT_STATS_ROUND_UP_BYTES); - num /= 1024; - buf = NULL; - tor_asprintf(&buf, "%d="U64_FORMAT, i, U64_PRINTF_ARG(num)); - smartlist_add(written_strings, buf); - } - if (exit_bytes_read[i] > 0) { - uint64_t num = round_uint64_to_next_multiple_of( - exit_bytes_read[i], EXIT_STATS_ROUND_UP_BYTES); - num /= 1024; - buf = NULL; - tor_asprintf(&buf, "%d="U64_FORMAT, i, U64_PRINTF_ARG(num)); - smartlist_add(read_strings, buf); - } - if (exit_streams[i] > 0) { - uint32_t num = round_uint32_to_next_multiple_of(exit_streams[i], - EXIT_STATS_ROUND_UP_STREAMS); - buf = NULL; - tor_asprintf(&buf, "%d=%u", i, num); - smartlist_add(streams_strings, buf); - } - } else { - other_read += exit_bytes_read[i]; - other_written += exit_bytes_written[i]; - other_streams += exit_streams[i]; + other_read = total_read; + other_written = total_written; + other_streams = total_streams; + /* Sort the ports; this puts them out of sync with top_bytes, but we + * won't be using top_bytes again anyway */ + qsort(top_ports, top_elements, sizeof(int), _compare_int); + for (j = 0; j < top_elements; j++) { + cur_port = top_ports[j]; + if (exit_bytes_written[cur_port] > 0) { + uint64_t num = round_uint64_to_next_multiple_of( + exit_bytes_written[cur_port], + EXIT_STATS_ROUND_UP_BYTES); + num /= 1024; + buf = NULL; + tor_asprintf(&buf, "%d="U64_FORMAT, cur_port, U64_PRINTF_ARG(num)); + smartlist_add(written_strings, buf); + other_written -= exit_bytes_written[cur_port]; + } + if (exit_bytes_read[cur_port] > 0) { + uint64_t num = round_uint64_to_next_multiple_of( + exit_bytes_read[cur_port], + EXIT_STATS_ROUND_UP_BYTES); + num /= 1024; + buf = NULL; + tor_asprintf(&buf, "%d="U64_FORMAT, cur_port, U64_PRINTF_ARG(num)); + smartlist_add(read_strings, buf); + other_read -= exit_bytes_read[cur_port]; + } + if (exit_streams[cur_port] > 0) { + uint32_t num = round_uint32_to_next_multiple_of( + exit_streams[cur_port], + EXIT_STATS_ROUND_UP_STREAMS); + buf = NULL; + tor_asprintf(&buf, "%d=%u", cur_port, num); + smartlist_add(streams_strings, buf); + other_streams -= exit_streams[cur_port]; } } + + /* Add observations of other ports in a single element. */ other_written = round_uint64_to_next_multiple_of(other_written, EXIT_STATS_ROUND_UP_BYTES); other_written /= 1024; @@@ -2162,8 -2125,6 +2211,8 @@@ buf = NULL; tor_asprintf(&buf, "other=%u", other_streams); smartlist_add(streams_strings, buf); + + /* Join all observations in single strings. */ written_string = smartlist_join_strings(written_strings, ",", 0, NULL); read_string = smartlist_join_strings(read_strings, ",", 0, NULL); streams_string = smartlist_join_strings(streams_strings, ",", 0, NULL); diff --combined src/or/rephist.h index 9a39070,610c1a0..5f6b9f9 --- a/src/or/rephist.h +++ b/src/or/rephist.h @@@ -1,7 -1,7 +1,7 @@@ /* Copyright (c) 2001 Matej Pfajfar. * Copyright (c) 2001-2004, Roger Dingledine. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. - * Copyright (c) 2007-2010, The Tor Project, Inc. */ + * Copyright (c) 2007-2011, The Tor Project, Inc. */ /* See LICENSE for licensing information */

/** @@@ -33,7 -33,8 +33,8 @@@ void rep_hist_update_state(or_state_t * int rep_hist_load_state(or_state_t *state, char **err); void rep_history_clean(time_t before);

- void rep_hist_note_router_reachable(const char *id, time_t when); + void rep_hist_note_router_reachable(const char *id, const tor_addr_t *at_addr, + uint16_t at_port, time_t when); void rep_hist_note_router_unreachable(const char *id, time_t when); int rep_hist_record_mtbf_data(time_t now, int missing_means_down); int rep_hist_load_mtbf_data(time_t now);