diff options
34 files changed, 1091 insertions, 501 deletions
diff --git a/autogen.sh b/autogen.sh index 0592f16c2..efa2251c2 100755 --- a/autogen.sh +++ b/autogen.sh @@ -1,7 +1,17 @@ #!/bin/sh if [ -x "`which autoreconf 2>/dev/null`" ] ; then - exec autoreconf -ivf + opt="-if" + + for i in $@; do + case "$i" in + -v) + opt=$opt"v" + ;; + esac + done + + exec autoreconf $opt fi set -e diff --git a/changes/4664 b/changes/4664 new file mode 100644 index 000000000..eb81da925 --- /dev/null +++ b/changes/4664 @@ -0,0 +1,4 @@ + o Minor features (build): + - Do not report status verbosely from autogen.sh unless the -v flag + is specified. Fixes issue 4664. Patch from Onizuka. + diff --git a/changes/bug5823 b/changes/bug5823 new file mode 100644 index 000000000..d76b59088 --- /dev/null +++ b/changes/bug5823 @@ -0,0 +1,5 @@ + o Removed featurs: + - Stop exporting estimates of v2 and v3 directory traffic shares + in extrainfo documents. They were unneeded and sometimes inaccurate. + Also stop exporting any v2 directory request statistics. Resolves + ticket 5823. diff --git a/changes/bug7802 b/changes/bug7802 new file mode 100644 index 000000000..9bc0f36fe --- /dev/null +++ b/changes/bug7802 @@ -0,0 +1,11 @@ + o Minor features: + - Path Use Bias: Perform separate accounting for successful circuit use. + Separate statistics on stream attempt versus success rates are kept + for each guard. Configurable thresholds are provided to determine + when to emit log messages or disable use of guards that fail too + many stream attempts. + o Minor bugfixes: + - Remove a source of rounding error during path bias count scaling. + - Don't count cannibalized circuits as used for path bias until we + actually try to use them. + - Fix circuit_package_relay_cell warning message about n_chan==NULL. diff --git a/changes/msvc b/changes/msvc index 9975c2d4c..1ae92e3f2 100644 --- a/changes/msvc +++ b/changes/msvc @@ -2,3 +2,5 @@ - Correctly define HAVE_EVENT_BASE_LOOPEXIT, since we only build with MSVC when using Libevent 2.0 or later. Fixes bug 7308. Reported by "ultramage". + - Make the ntor and curve25519 code build correctly with MSVC. + Fix on 0.2.4.8-alpha. diff --git a/changes/timed_onionqueue b/changes/timed_onionqueue new file mode 100644 index 000000000..fe54d78ac --- /dev/null +++ b/changes/timed_onionqueue @@ -0,0 +1,11 @@ + o Minor features (relay): + - Instead of limiting the number of queued onionskins to a configured, + hard-to-configure number, we limit the size of the queue based on how + many we expect to be able to process in a given amount of time. We + estimate the time it will take to process an onionskin based on average + processing time of previous onionskins. Closes ticket 7291. You'll + never have to configure MaxOnionsPending again. + + - We compute the overhead from passing onionskins back and forth to + cpuworkers, and report it when dumping statistics in response to + SIGUSR1. diff --git a/doc/tor.1.txt b/doc/tor.1.txt index 2b616bd26..5d4b51c18 100644 --- a/doc/tor.1.txt +++ b/doc/tor.1.txt @@ -1242,16 +1242,11 @@ The following options are useful only for clients (that is, if **PathBiasMultFactor** __NUM__ + -**PathBiasScaleFactor** __NUM__ + - -**PathBiasUseCloseCounts** __NUM__:: +**PathBiasScaleFactor** __NUM__:: These options override the default behavior of Tor's (**currently experimental**) path bias detection algorithm. To try to find broken or misbehaving guard nodes, Tor looks for nodes where more than a certain - fraction of circuits through that guard fail to get built. If - PathBiasUseCloseCounts is set to 1 (the default), usage-based accounting is - performed, and circuits that fail to carry streams are also counted as - failures. + + fraction of circuits through that guard fail to get built. + The PathBiasCircThreshold option controls how many circuits we need to build through a guard before we make these checks. The PathBiasNoticeRate, @@ -1270,6 +1265,28 @@ The following options are useful only for clients (that is, if If no defaults are available there, these options default to 150, .70, .50, .30, 0, 300, 1, and 2 respectively. +**PathBiasUseThreshold** __NUM__ + + +**PathBiasNoticeUseRate** __NUM__ + + +**PathBiasExtremeUseRate** __NUM__ + + +**PathBiasScaleUseThreshold** __NUM__:: + Similar to the above options, these options override the default behavior + of Tor's (**currently experimental**) path use bias detection algorithm. + + + Where as the path bias parameters govern thresholds for successfully + building circuits, these four path use bias parameters govern thresholds + only for circuit usage. Circuits which receive no stream usage + are not counted by this detection algorithm. A used circuit is considered + successful if it is capable of carrying streams or otherwise receiving + well-formed responses to RELAY cells. + + + By default, or if a negative value is provided for one of these options, + Tor uses reasonable defaults from the networkstatus consensus document. + If no defaults are available there, these options default to 20, .90, + .70, and 100, respectively. + **ClientUseIPv6** **0**|**1**:: If this option is set to 1, Tor might connect to entry nodes over IPv6. Note that clients configured with an IPv6 address in a @@ -1388,9 +1405,9 @@ is non-zero): If set, and we are an exit node, allow clients to use us for IPv6 traffic. (Default: 0) -**MaxOnionsPending** __NUM__:: - If you have more than this number of onionskins queued for decrypt, reject - new ones. (Default: 100) +**MaxOnionQueueDelay** __NUM__ [**msec**|**second**]:: + If we have more onionskins queued for processing than we can process in + this amount of time, reject new ones. (Default: 1750 msec) **MyFamily** __node__,__node__,__...__:: Declare that this Tor server is controlled or administered by a group or diff --git a/src/common/Makefile.nmake b/src/common/Makefile.nmake index 9672f4fe9..0ebeaaaf7 100644 --- a/src/common/Makefile.nmake +++ b/src/common/Makefile.nmake @@ -6,10 +6,14 @@ LIBOR_OBJECTS = address.obj compat.obj container.obj di_ops.obj \ log.obj memarea.obj mempool.obj procmon.obj util.obj \ util_codedigest.obj -LIBOR_CRYPTO_OBJECTS = aes.obj crypto.obj torgzip.obj tortls.obj +LIBOR_CRYPTO_OBJECTS = aes.obj crypto.obj torgzip.obj tortls.obj \ + crypto_curve25519.obj curve25519-donna.obj LIBOR_EVENT_OBJECTS = compat_libevent.obj +curve25519-donna.obj: ..\ext\curve25519_donna\curve25519-donna.c + $(CC) $(CFLAGS) /D inline=_inline /c ..\ext\curve25519_donna\curve25519-donna.c + libor.lib: $(LIBOR_OBJECTS) lib $(LIBOR_OBJECTS) /out:libor.lib diff --git a/src/common/compat_libevent.c b/src/common/compat_libevent.c index 2f41ed945..8cbb0db8e 100644 --- a/src/common/compat_libevent.c +++ b/src/common/compat_libevent.c @@ -54,7 +54,9 @@ typedef uint32_t le_version_t; * it is. */ #define LE_OTHER V(0,0,99) +#if 0 static le_version_t tor_get_libevent_version(const char **v_out); +#endif #if defined(HAVE_EVENT_SET_LOG_CALLBACK) || defined(RUNNING_DOXYGEN) /** A string which, if it appears in a libevent log, should be ignored. */ @@ -185,13 +187,6 @@ tor_libevent_initialize(tor_libevent_cfg *torcfg) /* some paths below don't use torcfg, so avoid unused variable warnings */ (void)torcfg; -#ifdef __APPLE__ - if (MACOSX_KQUEUE_IS_BROKEN || - tor_get_libevent_version(NULL) < V_OLD(1,1,'b')) { - setenv("EVENT_NOKQUEUE","1",1); - } -#endif - #ifdef HAVE_EVENT2_EVENT_H { int attempts = 0; @@ -364,6 +359,7 @@ le_versions_compatibility(le_version_t v) return 5; } +#if 0 /** Return the version number of the currently running version of Libevent. * See le_version_t for info on the format. */ @@ -386,6 +382,7 @@ tor_get_libevent_version(const char **v_out) *v_out = v; return r; } +#endif /** Return a string representation of the version of the currently running * version of Libevent. */ @@ -407,37 +404,9 @@ void tor_check_libevent_version(const char *m, int server, const char **badness_out) { - int thread_unsafe = 0; - le_version_t version; - const char *v = NULL; - const char *badness = NULL; - const char *sad_os = ""; (void) m; - - version = tor_get_libevent_version(&v); - - /* Libevent versions before 1.3b do very badly on operating systems with - * user-space threading implementations. */ -#if defined(__OpenBSD__) || defined(__FreeBSD__) || defined(__NetBSD__) - if (server && version < V_OLD(1,3,'b')) { - thread_unsafe = 1; - sad_os = "BSD variants"; - } -#elif defined(__APPLE__) || defined(__darwin__) - if (server && version < V_OLD(1,3,'b')) { - thread_unsafe = 1; - sad_os = "Mac OS X"; - } -#endif - - if (thread_unsafe) { - log(LOG_WARN, LD_GENERAL, - "Libevent version %s often crashes when running a Tor server with %s. " - "Please use the latest version of libevent (1.3b or later)",v,sad_os); - badness = "BROKEN"; - } - - *badness_out = badness; + (void) server; + *badness_out = NULL; } #if defined(LIBEVENT_VERSION) diff --git a/src/common/crypto.c b/src/common/crypto.c index 672ab2d55..7c73f79cf 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -2579,7 +2579,7 @@ smartlist_shuffle(smartlist_t *sl) } } -/** Base-64 encode <b>srclen</b> bytes of data from <b>src</b>. Write +/** Base64 encode <b>srclen</b> bytes of data from <b>src</b>. Write * the result into <b>dest</b>, if it will fit within <b>destlen</b> * bytes. Return the number of bytes written on success; -1 if * destlen is too short, or other failure. @@ -2638,7 +2638,7 @@ static const uint8_t base64_decode_table[256] = { X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, }; -/** Base-64 decode <b>srclen</b> bytes of data from <b>src</b>. Write +/** Base64 decode <b>srclen</b> bytes of data from <b>src</b>. Write * the result into <b>dest</b>, if it will fit within <b>destlen</b> * bytes. Return the number of bytes written on success; -1 if * destlen is too short, or other failure. @@ -2745,7 +2745,7 @@ base64_decode(char *dest, size_t destlen, const char *src, size_t srclen) #undef SP #undef PAD -/** Base-64 encode DIGEST_LINE bytes from <b>digest</b>, remove the trailing = +/** Base64 encode DIGEST_LINE bytes from <b>digest</b>, remove the trailing = * and newline characters, and store the nul-terminated result in the first * BASE64_DIGEST_LEN+1 bytes of <b>d64</b>. */ int @@ -2758,7 +2758,7 @@ digest_to_base64(char *d64, const char *digest) return 0; } -/** Given a base-64 encoded, nul-terminated digest in <b>d64</b> (without +/** Given a base64 encoded, nul-terminated digest in <b>d64</b> (without * trailing newline or = characters), decode it and store the result in the * first DIGEST_LEN bytes at <b>digest</b>. */ int @@ -2783,7 +2783,7 @@ digest_from_base64(char *digest, const char *d64) #endif } -/** Base-64 encode DIGEST256_LINE bytes from <b>digest</b>, remove the +/** Base64 encode DIGEST256_LINE bytes from <b>digest</b>, remove the * trailing = and newline characters, and store the nul-terminated result in * the first BASE64_DIGEST256_LEN+1 bytes of <b>d64</b>. */ int @@ -2796,7 +2796,7 @@ digest256_to_base64(char *d64, const char *digest) return 0; } -/** Given a base-64 encoded, nul-terminated digest in <b>d64</b> (without +/** Given a base64 encoded, nul-terminated digest in <b>d64</b> (without * trailing newline or = characters), decode it and store the result in the * first DIGEST256_LEN bytes at <b>digest</b>. */ int diff --git a/src/common/crypto.h b/src/common/crypto.h index 24f6a48bc..08efc801d 100644 --- a/src/common/crypto.h +++ b/src/common/crypto.h @@ -266,7 +266,7 @@ void smartlist_shuffle(struct smartlist_t *sl); int base64_encode(char *dest, size_t destlen, const char *src, size_t srclen); int base64_decode(char *dest, size_t destlen, const char *src, size_t srclen); -/** Characters that can appear (case-insensitively) in a base-32 encoding. */ +/** Characters that can appear (case-insensitively) in a base32 encoding. */ #define BASE32_CHARS "abcdefghijklmnopqrstuvwxyz234567" void base32_encode(char *dest, size_t destlen, const char *src, size_t srclen); int base32_decode(char *dest, size_t destlen, const char *src, size_t srclen); diff --git a/src/or/Makefile.nmake b/src/or/Makefile.nmake index c33407373..d67123a9a 100644 --- a/src/or/Makefile.nmake +++ b/src/or/Makefile.nmake @@ -44,6 +44,9 @@ LIBTOR_OBJECTS = \ nodelist.obj \ ntmain.obj \ onion.obj \ + onion_fast.obj \ + onion_ntor.obj \ + onion_tap.obj \ policies.obj \ reasons.obj \ relay.obj \ diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index b98624386..e3a9d59c0 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -67,7 +67,9 @@ static int entry_guard_inc_circ_attempt_count(entry_guard_t *guard); static void pathbias_count_build_success(origin_circuit_t *circ); static void pathbias_count_successful_close(origin_circuit_t *circ); static void pathbias_count_collapse(origin_circuit_t *circ); -static void pathbias_count_unusable(origin_circuit_t *circ); +static void pathbias_count_use_failed(origin_circuit_t *circ); +static int pathbias_check_use_rate(entry_guard_t *guard); +static int pathbias_check_close_rate(entry_guard_t *guard); /** This function tries to get a channel to the specified endpoint, * and then calls command_setup_channel() to give it the right @@ -821,9 +823,6 @@ circuit_send_next_onion_skin(origin_circuit_t *circ) /* We're done with measurement circuits here. Just close them */ if (circ->base_.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) { - /* If a measurement circ ever gets back to us, consider it - * succeeded for path bias */ - circ->path_state = PATH_STATE_USE_SUCCEEDED; circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED); } return 0; @@ -1210,19 +1209,65 @@ pathbias_get_mult_factor(const or_options_t *options) pathbias_get_scale_factor(options)); } +/** The minimum number of circuit usage attempts before we start + * thinking about warning about path use bias and dropping guards */ +static int +pathbias_get_min_use(const or_options_t *options) +{ +#define DFLT_PATH_BIAS_MIN_USE 20 + if (options->PathBiasUseThreshold >= 3) + return options->PathBiasUseThreshold; + else + return networkstatus_get_param(NULL, "pb_minuse", + DFLT_PATH_BIAS_MIN_USE, + 3, INT32_MAX); +} + +/** The circuit use success rate below which we issue a notice */ +static double +pathbias_get_notice_use_rate(const or_options_t *options) +{ +#define DFLT_PATH_BIAS_NOTICE_USE_PCT 90 + if (options->PathBiasNoticeUseRate >= 0.0) + return options->PathBiasNoticeUseRate; + else + return networkstatus_get_param(NULL, "pb_noticeusepct", + DFLT_PATH_BIAS_NOTICE_USE_PCT, + 0, 100)/100.0; +} + +/** + * The extreme use rate is the rate at which we would drop the guard, + * if pb_dropguard is also set. Otherwise we just warn. + */ +double +pathbias_get_extreme_use_rate(const or_options_t *options) +{ +#define DFLT_PATH_BIAS_EXTREME_USE_PCT 70 + if (options->PathBiasExtremeUseRate >= 0.0) + return options->PathBiasExtremeUseRate; + else + return networkstatus_get_param(NULL, "pb_extremeusepct", + DFLT_PATH_BIAS_EXTREME_USE_PCT, + 0, 100)/100.0; +} + /** - * If this parameter is set to a true value (default), we use the - * successful_circuits_closed. Otherwise, we use the success_count. + * This is the number of circuits at which we scale our + * use counts by mult_factor/scale_factor. Note, this count is + * not exact, as we only perform the scaling in the event + * of no integer truncation. */ static int -pathbias_use_close_counts(const or_options_t *options) +pathbias_get_scale_use_threshold(const or_options_t *options) { -#define DFLT_PATH_BIAS_USE_CLOSE_COUNTS 1 - if (options->PathBiasUseCloseCounts >= 0) - return options->PathBiasUseCloseCounts; +#define DFLT_PATH_BIAS_SCALE_USE_THRESHOLD 100 + if (options->PathBiasScaleUseThreshold >= 10) + return options->PathBiasScaleUseThreshold; else - return networkstatus_get_param(NULL, "pb_useclosecounts", - DFLT_PATH_BIAS_USE_CLOSE_COUNTS, 0, 1); + return networkstatus_get_param(NULL, "pb_scaleuse", + DFLT_PATH_BIAS_SCALE_USE_THRESHOLD, + 10, INT32_MAX); } /** @@ -1238,10 +1283,14 @@ pathbias_state_to_string(path_state_t state) return "build attempted"; case PATH_STATE_BUILD_SUCCEEDED: return "build succeeded"; + case PATH_STATE_USE_ATTEMPTED: + return "use attempted"; case PATH_STATE_USE_SUCCEEDED: return "use succeeded"; case PATH_STATE_USE_FAILED: return "use failed"; + case PATH_STATE_ALREADY_COUNTED: + return "already counted"; } return "unknown"; @@ -1338,7 +1387,7 @@ pathbias_should_count(origin_circuit_t *circ) * Also check for several potential error cases for bug #6475. */ static int -pathbias_count_circ_attempt(origin_circuit_t *circ) +pathbias_count_build_attempt(origin_circuit_t *circ) { #define CIRC_ATTEMPT_NOTICE_INTERVAL (600) static ratelim_t circ_attempt_notice_limit = @@ -1505,6 +1554,130 @@ pathbias_count_build_success(origin_circuit_t *circ) } /** + * Record an attempt to use a circuit. Changes the circuit's + * path state and update its guard's usage counter. + * + * Used for path bias usage accounting. + */ +void +pathbias_count_use_attempt(origin_circuit_t *circ) +{ + entry_guard_t *guard; + + if (!pathbias_should_count(circ)) { + return; + } + + if (circ->path_state < PATH_STATE_BUILD_SUCCEEDED) { + log_notice(LD_BUG, + "Used circuit is in strange path state %s. " + "Circuit is a %s currently %s.", + pathbias_state_to_string(circ->path_state), + circuit_purpose_to_string(circ->base_.purpose), + circuit_state_to_string(circ->base_.state)); + } else if (circ->path_state < PATH_STATE_USE_ATTEMPTED) { + guard = entry_guard_get_by_id_digest( + circ->cpath->extend_info->identity_digest); + if (guard) { + pathbias_check_use_rate(guard); + guard->use_attempts++; + + log_debug(LD_CIRC, + "Marked circuit %d (%f/%f) as used for guard %s=%s.", + circ->global_identifier, + guard->use_successes, guard->use_attempts, + guard->nickname, hex_str(guard->identity, DIGEST_LEN)); + } + + circ->path_state = PATH_STATE_USE_ATTEMPTED; + } else { + /* Harmless but educational log message */ + log_info(LD_CIRC, + "Used circuit %d is already in path state %s. " + "Circuit is a %s currently %s.", + circ->global_identifier, + pathbias_state_to_string(circ->path_state), + circuit_purpose_to_string(circ->base_.purpose), + circuit_state_to_string(circ->base_.state)); + } + + return; +} + +/** + * Check the circuit's path stat is appropriate and it as successfully + * used. + * + * We don't actually increment the guard's counters until + * pathbias_check_close(). + * + * Used for path bias usage accounting. + */ +void +pathbias_mark_use_success(origin_circuit_t *circ) +{ + if (!pathbias_should_count(circ)) { + return; + } + + if (circ->path_state < PATH_STATE_USE_ATTEMPTED) { + log_notice(LD_BUG, + "Used circuit %d is in strange path state %s. " + "Circuit is a %s currently %s.", + circ->global_identifier, + pathbias_state_to_string(circ->path_state), + circuit_purpose_to_string(circ->base_.purpose), + circuit_state_to_string(circ->base_.state)); + + pathbias_count_use_attempt(circ); + } + + /* We don't do any accounting at the guard until actual circuit close */ + circ->path_state = PATH_STATE_USE_SUCCEEDED; + + return; +} + +/** + * Actually count a circuit success towards a guard's usage counters + * if the path state is appropriate. + */ +static void +pathbias_count_use_success(origin_circuit_t *circ) +{ + entry_guard_t *guard; + + if (!pathbias_should_count(circ)) { + return; + } + + if (circ->path_state != PATH_STATE_USE_SUCCEEDED) { + log_notice(LD_BUG, + "Successfully used circuit %d is in strange path state %s. " + "Circuit is a %s currently %s.", + circ->global_identifier, + pathbias_state_to_string(circ->path_state), + circuit_purpose_to_string(circ->base_.purpose), + circuit_state_to_string(circ->base_.state)); + } else { + guard = entry_guard_get_by_id_digest( + circ->cpath->extend_info->identity_digest); + if (guard) { + guard->use_successes++; + + log_debug(LD_CIRC, + "Marked circuit %d (%f/%f) as used successfully for guard " + "%s=%s.", + circ->global_identifier, guard->use_successes, + guard->use_attempts, guard->nickname, + hex_str(guard->identity, DIGEST_LEN)); + } + } + + return; +} + +/** * Send a probe down a circuit that the client attempted to use, * but for which the stream timed out/failed. The probe is a * RELAY_BEGIN cell with a 0.a.b.c destination address, which @@ -1554,6 +1727,16 @@ pathbias_send_usable_probe(circuit_t *circ) return -1; } + /* Can't probe if the channel isn't open */ + if (circ->n_chan == NULL || + (circ->n_chan->state != CHANNEL_STATE_OPEN + && circ->n_chan->state != CHANNEL_STATE_MAINT)) { + log_info(LD_CIRC, + "Skipping pathbias probe for circuit %d: Channel is not open.", + ocirc->global_identifier); + return -1; + } + circuit_change_purpose(circ, CIRCUIT_PURPOSE_PATH_BIAS_TESTING); /* Update timestamp for when circuit_expire_building() should kill us */ @@ -1648,7 +1831,7 @@ pathbias_check_probe_response(circuit_t *circ, const cell_t *cell) /* Check nonce */ if (ipv4_host == ocirc->pathbias_probe_nonce) { - ocirc->path_state = PATH_STATE_USE_SUCCEEDED; + pathbias_mark_use_success(ocirc); circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED); log_info(LD_CIRC, "Got valid path bias probe back for circ %d, stream %d.", @@ -1691,24 +1874,11 @@ pathbias_check_close(origin_circuit_t *ocirc, int reason) return 0; } - if (ocirc->path_state == PATH_STATE_BUILD_SUCCEEDED) { - if (circ->timestamp_dirty) { - if (pathbias_send_usable_probe(circ) == 0) - return -1; - else - pathbias_count_unusable(ocirc); - - /* Any circuit where there were attempted streams but no successful - * streams could be bias */ - log_info(LD_CIRC, - "Circuit %d closed without successful use for reason %d. " - "Circuit purpose %d currently %d,%s. Len %d.", - ocirc->global_identifier, - reason, circ->purpose, ocirc->has_opened, - circuit_state_to_string(circ->state), - ocirc->build_state->desired_path_len); - - } else { + switch (ocirc->path_state) { + /* If the circuit was closed after building, but before use, we need + * to ensure we were the ones who tried to close it (and not a remote + * actor). */ + case PATH_STATE_BUILD_SUCCEEDED: if (reason & END_CIRC_REASON_FLAG_REMOTE) { /* Remote circ close reasons on an unused circuit all could be bias */ log_info(LD_CIRC, @@ -1739,11 +1909,41 @@ pathbias_check_close(origin_circuit_t *ocirc, int reason) } else { pathbias_count_successful_close(ocirc); } - } - } else if (ocirc->path_state == PATH_STATE_USE_SUCCEEDED) { - pathbias_count_successful_close(ocirc); + break; + + /* If we tried to use a circuit but failed, we should probe it to ensure + * it has not been tampered with. */ + case PATH_STATE_USE_ATTEMPTED: + /* XXX: Only probe and/or count failure if the network is live? + * What about clock jumps/suspends? */ + if (pathbias_send_usable_probe(circ) == 0) + return -1; + else + pathbias_count_use_failed(ocirc); + + /* Any circuit where there were attempted streams but no successful + * streams could be bias */ + log_info(LD_CIRC, + "Circuit %d closed without successful use for reason %d. " + "Circuit purpose %d currently %d,%s. Len %d.", + ocirc->global_identifier, + reason, circ->purpose, ocirc->has_opened, + circuit_state_to_string(circ->state), + ocirc->build_state->desired_path_len); + break; + + case PATH_STATE_USE_SUCCEEDED: + pathbias_count_successful_close(ocirc); + pathbias_count_use_success(ocirc); + break; + + default: + // Other states are uninteresting. No stats to count. + break; } + ocirc->path_state = PATH_STATE_ALREADY_COUNTED; + return 0; } @@ -1792,6 +1992,7 @@ static void pathbias_count_collapse(origin_circuit_t *circ) { entry_guard_t *guard = NULL; + if (!pathbias_should_count(circ)) { return; } @@ -1816,8 +2017,13 @@ pathbias_count_collapse(origin_circuit_t *circ) } } +/** + * Count a known failed circuit (because we could not probe it). + * + * This counter is informational. + */ static void -pathbias_count_unusable(origin_circuit_t *circ) +pathbias_count_use_failed(origin_circuit_t *circ) { entry_guard_t *guard = NULL; if (!pathbias_should_count(circ)) { @@ -1879,20 +2085,20 @@ pathbias_count_timeout(origin_circuit_t *circ) } /** - * Return the number of circuits counted as successfully closed for - * this guard. - * - * Also add in the currently open circuits to give them the benefit - * of the doubt. + * Helper function to count all of the currently opened circuits + * for a guard that are in a given path state range. The state + * range is inclusive on both ends. */ -double -pathbias_get_closed_count(entry_guard_t *guard) +static int +pathbias_count_circs_in_states(entry_guard_t *guard, + path_state_t from, + path_state_t to) { - circuit_t *circ; + circuit_t *circ = global_circuitlist; int open_circuits = 0; - /* Count currently open circuits. Give them the benefit of the doubt. */ - for (circ = global_circuitlist; circ; circ = circ->next) { + /* Count currently open circuits. Give them the benefit of the doubt */ + for ( ; circ; circ = circ->next) { origin_circuit_t *ocirc = NULL; if (!CIRCUIT_IS_ORIGIN(circ) || /* didn't originate here */ circ->marked_for_close) /* already counted */ @@ -1903,63 +2109,214 @@ pathbias_get_closed_count(entry_guard_t *guard) if (!ocirc->cpath || !ocirc->cpath->extend_info) continue; - if (ocirc->path_state >= PATH_STATE_BUILD_SUCCEEDED && + if (ocirc->path_state >= from && + ocirc->path_state <= to && + pathbias_should_count(ocirc) && fast_memeq(guard->identity, - ocirc->cpath->extend_info->identity_digest, - DIGEST_LEN)) { + ocirc->cpath->extend_info->identity_digest, + DIGEST_LEN)) { + log_debug(LD_CIRC, "Found opened circuit %d in path_state %s", + ocirc->global_identifier, + pathbias_state_to_string(ocirc->path_state)); open_circuits++; } } - return guard->successful_circuits_closed + open_circuits; + return open_circuits; } /** - * This function checks the consensus parameters to decide - * if it should return guard->circ_successes or - * guard->successful_circuits_closed. + * Return the number of circuits counted as successfully closed for + * this guard. + * + * Also add in the currently open circuits to give them the benefit + * of the doubt. */ double -pathbias_get_success_count(entry_guard_t *guard) +pathbias_get_close_success_count(entry_guard_t *guard) { - if (pathbias_use_close_counts(get_options())) { - return pathbias_get_closed_count(guard); - } else { - return guard->circ_successes; - } + return guard->successful_circuits_closed + + pathbias_count_circs_in_states(guard, + PATH_STATE_BUILD_SUCCEEDED, + PATH_STATE_USE_SUCCEEDED); } -/** Increment the number of times we successfully extended a circuit to - * <b>guard</b>, first checking if the failure rate is high enough that - * we should eliminate the guard. Return -1 if the guard looks no good; - * return 0 if the guard looks fine. +/** + * Return the number of circuits counted as successfully used + * this guard. + * + * Also add in the currently open circuits that we are attempting + * to use to give them the benefit of the doubt. + */ +double +pathbias_get_use_success_count(entry_guard_t *guard) +{ + return guard->use_successes + + pathbias_count_circs_in_states(guard, + PATH_STATE_USE_ATTEMPTED, + PATH_STATE_USE_SUCCEEDED); +} + +/** + * Check the path bias use rate against our consensus parameter limits. + * + * Emits a log message if the use success rates are too low. + * + * If pathbias_get_dropguards() is set, we also disable the use of + * very failure prone guards. + * + * Returns -1 if we decided to disable the guard, 0 otherwise. */ static int -entry_guard_inc_circ_attempt_count(entry_guard_t *guard) +pathbias_check_use_rate(entry_guard_t *guard) { const or_options_t *options = get_options(); - entry_guards_changed(); + if (guard->use_attempts > pathbias_get_min_use(options)) { + /* Note: We rely on the < comparison here to allow us to set a 0 + * rate and disable the feature entirely. If refactoring, don't + * change to <= */ + if (pathbias_get_use_success_count(guard)/guard->use_attempts + < pathbias_get_extreme_use_rate(options)) { + /* Dropping is currently disabled by default. */ + if (pathbias_get_dropguards(options)) { + if (!guard->path_bias_disabled) { + log_warn(LD_CIRC, + "Your Guard %s=%s is failing to carry an extremely large " + "amount of stream on its circuits. " + "To avoid potential route manipluation attacks, Tor has " + "disabled use of this guard. " + "Use counts are %ld/%ld. Success counts are %ld/%ld. " + "%ld circuits completed, %ld were unusable, %ld collapsed, " + "and %ld timed out. " + "For reference, your timeout cutoff is %ld seconds.", + guard->nickname, hex_str(guard->identity, DIGEST_LEN), + tor_lround(pathbias_get_use_success_count(guard)), + tor_lround(guard->use_attempts), + tor_lround(pathbias_get_close_success_count(guard)), + tor_lround(guard->circ_attempts), + tor_lround(guard->circ_successes), + tor_lround(guard->unusable_circuits), + tor_lround(guard->collapsed_circuits), + tor_lround(guard->timeouts), + tor_lround(circ_times.close_ms/1000)); + guard->path_bias_disabled = 1; + guard->bad_since = approx_time(); + return -1; + } + } else if (!guard->path_bias_extreme) { + guard->path_bias_extreme = 1; + log_warn(LD_CIRC, + "Your Guard %s=%s is failing to carry an extremely large " + "amount of streams on its circuits. " + "This could indicate a route manipulation attack, network " + "overload, bad local network connectivity, or a bug. " + "Use counts are %ld/%ld. Success counts are %ld/%ld. " + "%ld circuits completed, %ld were unusable, %ld collapsed, " + "and %ld timed out. " + "For reference, your timeout cutoff is %ld seconds.", + guard->nickname, hex_str(guard->identity, DIGEST_LEN), + tor_lround(pathbias_get_use_success_count(guard)), + tor_lround(guard->use_attempts), + tor_lround(pathbias_get_close_success_count(guard)), + tor_lround(guard->circ_attempts), + tor_lround(guard->circ_successes), + tor_lround(guard->unusable_circuits), + tor_lround(guard->collapsed_circuits), + tor_lround(guard->timeouts), + tor_lround(circ_times.close_ms/1000)); + } + } else if (pathbias_get_use_success_count(guard)/guard->use_attempts + < pathbias_get_notice_use_rate(options)) { + if (!guard->path_bias_noticed) { + guard->path_bias_noticed = 1; + log_notice(LD_CIRC, + "Your Guard %s=%s is failing to carry more streams on its " + "circuits than usual. " + "Most likely this means the Tor network is overloaded " + "or your network connection is poor. " + "Use counts are %ld/%ld. Success counts are %ld/%ld. " + "%ld circuits completed, %ld were unusable, %ld collapsed, " + "and %ld timed out. " + "For reference, your timeout cutoff is %ld seconds.", + guard->nickname, hex_str(guard->identity, DIGEST_LEN), + tor_lround(pathbias_get_use_success_count(guard)), + tor_lround(guard->use_attempts), + tor_lround(pathbias_get_close_success_count(guard)), + tor_lround(guard->circ_attempts), + tor_lround(guard->circ_successes), + tor_lround(guard->unusable_circuits), + tor_lround(guard->collapsed_circuits), + tor_lround(guard->timeouts), + tor_lround(circ_times.close_ms/1000)); + } + } + } + + /* If we get a ton of circuits, just scale everything down */ + if (guard->use_attempts > pathbias_get_scale_use_threshold(options)) { + const int scale_factor = pathbias_get_scale_factor(options); + const int mult_factor = pathbias_get_mult_factor(options); + int opened_attempts = pathbias_count_circs_in_states(guard, + PATH_STATE_USE_ATTEMPTED, PATH_STATE_USE_SUCCEEDED); + guard->use_attempts -= opened_attempts; + + guard->use_attempts *= mult_factor; + guard->use_successes *= mult_factor; + + guard->use_attempts /= scale_factor; + guard->use_successes /= scale_factor; + + guard->use_attempts += opened_attempts; + + log_info(LD_CIRC, + "Scaled pathbias use counts to %f/%f (%d open) for guard %s=%s", + guard->use_successes, guard->use_attempts, opened_attempts, + guard->nickname, hex_str(guard->identity, DIGEST_LEN)); + } + + return 0; +} + +/** + * Check the path bias circuit close status rates against our consensus + * parameter limits. + * + * Emits a log message if the use success rates are too low. + * + * If pathbias_get_dropguards() is set, we also disable the use of + * very failure prone guards. + * + * Returns -1 if we decided to disable the guard, 0 otherwise. + */ +static int +pathbias_check_close_rate(entry_guard_t *guard) +{ + const or_options_t *options = get_options(); if (guard->circ_attempts > pathbias_get_min_circs(options)) { /* Note: We rely on the < comparison here to allow us to set a 0 * rate and disable the feature entirely. If refactoring, don't * change to <= */ - if (pathbias_get_success_count(guard)/guard->circ_attempts + if (pathbias_get_close_success_count(guard)/guard->circ_attempts < pathbias_get_extreme_rate(options)) { /* Dropping is currently disabled by default. */ if (pathbias_get_dropguards(options)) { if (!guard->path_bias_disabled) { log_warn(LD_CIRC, - "Your Guard %s=%s is failing an extremely large amount of " - "circuits. To avoid potential route manipulation attacks, " - "Tor has disabled use of this guard. " - "Success counts are %ld/%ld. %ld circuits completed, %ld " - "were unusable, %ld collapsed, and %ld timed out. For " - "reference, your timeout cutoff is %ld seconds.", + "Your Guard %s=%s is failing an extremely large " + "amount of circuits. " + "To avoid potential route manipluation attacks, Tor has " + "disabled use of this guard. " + "Success counts are %ld/%ld. Use counts are %ld/%ld. " + "%ld circuits completed, %ld were unusable, %ld collapsed, " + "and %ld timed out. " + "For reference, your timeout cutoff is %ld seconds.", guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_closed_count(guard)), + tor_lround(pathbias_get_close_success_count(guard)), tor_lround(guard->circ_attempts), + tor_lround(pathbias_get_use_success_count(guard)), + tor_lround(guard->use_attempts), tor_lround(guard->circ_successes), tor_lround(guard->unusable_circuits), tor_lround(guard->collapsed_circuits), @@ -1972,60 +2329,72 @@ entry_guard_inc_circ_attempt_count(entry_guard_t *guard) } else if (!guard->path_bias_extreme) { guard->path_bias_extreme = 1; log_warn(LD_CIRC, - "Your Guard %s=%s is failing an extremely large amount of " - "circuits. This could indicate a route manipulation attack, " + "Your Guard %s=%s is failing an extremely large " + "amount of circuits. " + "This could indicate a route manipulation attack, " "extreme network overload, or a bug. " - "Success counts are %ld/%ld. %ld circuits completed, %ld " - "were unusable, %ld collapsed, and %ld timed out. For " - "reference, your timeout cutoff is %ld seconds.", + "Success counts are %ld/%ld. Use counts are %ld/%ld. " + "%ld circuits completed, %ld were unusable, %ld collapsed, " + "and %ld timed out. " + "For reference, your timeout cutoff is %ld seconds.", guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_closed_count(guard)), + tor_lround(pathbias_get_close_success_count(guard)), tor_lround(guard->circ_attempts), + tor_lround(pathbias_get_use_success_count(guard)), + tor_lround(guard->use_attempts), tor_lround(guard->circ_successes), tor_lround(guard->unusable_circuits), tor_lround(guard->collapsed_circuits), tor_lround(guard->timeouts), tor_lround(circ_times.close_ms/1000)); } - } else if (pathbias_get_success_count(guard)/((double)guard->circ_attempts) - < pathbias_get_warn_rate(options)) { + } else if (pathbias_get_close_success_count(guard)/guard->circ_attempts + < pathbias_get_warn_rate(options)) { if (!guard->path_bias_warned) { guard->path_bias_warned = 1; log_warn(LD_CIRC, - "Your Guard %s=%s is failing a very large amount of " - "circuits. Most likely this means the Tor network is " + "Your Guard %s=%s is failing a very large " + "amount of circuits. " + "Most likely this means the Tor network is " "overloaded, but it could also mean an attack against " - "you or potentially the guard itself. " - "Success counts are %ld/%ld. %ld circuits completed, %ld " - "were unusable, %ld collapsed, and %ld timed out. For " - "reference, your timeout cutoff is %ld seconds.", + "you or the potentially the guard itself. " + "Success counts are %ld/%ld. Use counts are %ld/%ld. " + "%ld circuits completed, %ld were unusable, %ld collapsed, " + "and %ld timed out. " + "For reference, your timeout cutoff is %ld seconds.", guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_closed_count(guard)), + tor_lround(pathbias_get_close_success_count(guard)), tor_lround(guard->circ_attempts), + tor_lround(pathbias_get_use_success_count(guard)), + tor_lround(guard->use_attempts), tor_lround(guard->circ_successes), tor_lround(guard->unusable_circuits), tor_lround(guard->collapsed_circuits), tor_lround(guard->timeouts), tor_lround(circ_times.close_ms/1000)); } - } else if (pathbias_get_success_count(guard)/((double)guard->circ_attempts) + } else if (pathbias_get_close_success_count(guard)/guard->circ_attempts < pathbias_get_notice_rate(options)) { if (!guard->path_bias_noticed) { guard->path_bias_noticed = 1; log_notice(LD_CIRC, - "Your Guard %s=%s is failing more circuits than usual. " - "Most likely this means the Tor network is overloaded. " - "Success counts are %ld/%ld. %ld circuits completed, %ld " - "were unusable, %ld collapsed, and %ld timed out. For " - "reference, your timeout cutoff is %ld seconds.", - guard->nickname, hex_str(guard->identity, DIGEST_LEN), - tor_lround(pathbias_get_closed_count(guard)), - tor_lround(guard->circ_attempts), - tor_lround(guard->circ_successes), - tor_lround(guard->unusable_circuits), - tor_lround(guard->collapsed_circuits), - tor_lround(guard->timeouts), - tor_lround(circ_times.close_ms/1000)); + "Your Guard %s=%s is failing more circuits than " + "usual. " + "Most likely this means the Tor network is overloaded. " + "Success counts are %ld/%ld. Use counts are %ld/%ld. " + "%ld circuits completed, %ld were unusable, %ld collapsed, " + "and %ld timed out. " + "For reference, your timeout cutoff is %ld seconds.", + guard->nickname, hex_str(guard->identity, DIGEST_LEN), + tor_lround(pathbias_get_close_success_count(guard)), + tor_lround(guard->circ_attempts), + tor_lround(pathbias_get_use_success_count(guard)), + tor_lround(guard->use_attempts), + tor_lround(guard->circ_successes), + tor_lround(guard->unusable_circuits), + tor_lround(guard->collapsed_circuits), + tor_lround(guard->timeouts), + tor_lround(circ_times.close_ms/1000)); } } } @@ -2034,11 +2403,13 @@ entry_guard_inc_circ_attempt_count(entry_guard_t *guard) if (guard->circ_attempts > pathbias_get_scale_threshold(options)) { const int scale_factor = pathbias_get_scale_factor(options); const int mult_factor = pathbias_get_mult_factor(options); - log_info(LD_CIRC, - "Scaling pathbias counts to (%f/%f)*(%d/%d) for guard %s=%s", - guard->circ_successes, guard->circ_attempts, - mult_factor, scale_factor, guard->nickname, - hex_str(guard->identity, DIGEST_LEN)); + int opened_attempts = pathbias_count_circs_in_states(guard, + PATH_STATE_BUILD_ATTEMPTED, PATH_STATE_BUILD_ATTEMPTED); + int opened_built = pathbias_count_circs_in_states(guard, + PATH_STATE_BUILD_SUCCEEDED, + PATH_STATE_USE_FAILED); + guard->circ_attempts -= opened_attempts; + guard->circ_successes -= opened_built; guard->circ_attempts *= mult_factor; guard->circ_successes *= mult_factor; @@ -2053,8 +2424,35 @@ entry_guard_inc_circ_attempt_count(entry_guard_t *guard) guard->successful_circuits_closed /= scale_factor; guard->collapsed_circuits /= scale_factor; guard->unusable_circuits /= scale_factor; + + guard->circ_attempts += opened_attempts; + guard->circ_successes += opened_built; + + log_info(LD_CIRC, + "Scaled pathbias counts to (%f,%f)/%f (%d/%d open) for guard " + "%s=%s", + guard->circ_successes, guard->successful_circuits_closed, + guard->circ_attempts, opened_built, opened_attempts, + guard->nickname, hex_str(guard->identity, DIGEST_LEN)); } + + return 0; +} + +/** Increment the number of times we successfully extended a circuit to + * 'guard', first checking if the failure rate is high enough that we should + * eliminate the guard. Return -1 if the guard looks no good; return 0 if the + * guard looks fine. */ +static int +entry_guard_inc_circ_attempt_count(entry_guard_t *guard) +{ + entry_guards_changed(); + + if (pathbias_check_close_rate(guard) < 0) + return -1; + guard->circ_attempts++; + log_info(LD_CIRC, "Got success count %f/%f for guard %s=%s", guard->circ_successes, guard->circ_attempts, guard->nickname, hex_str(guard->identity, DIGEST_LEN)); @@ -2078,7 +2476,7 @@ circuit_finish_handshake(origin_circuit_t *circ, crypt_path_t *hop; int rv; - if ((rv = pathbias_count_circ_attempt(circ)) < 0) + if ((rv = pathbias_count_build_attempt(circ)) < 0) return rv; if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) { @@ -2761,9 +3159,7 @@ circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit) return -1; } - /* Set timestamp_dirty, so we can check it for path use bias */ - if (!circ->base_.timestamp_dirty) - circ->base_.timestamp_dirty = time(NULL); + // XXX: Should cannibalized circuits be dirty or not? Not easy to say.. return 0; } diff --git a/src/or/circuitbuild.h b/src/or/circuitbuild.h index e6cf802f2..d03a7c532 100644 --- a/src/or/circuitbuild.h +++ b/src/or/circuitbuild.h @@ -58,10 +58,13 @@ const char *build_state_get_exit_nickname(cpath_build_state_t *state); const node_t *choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state); double pathbias_get_extreme_rate(const or_options_t *options); +double pathbias_get_extreme_use_rate(const or_options_t *options); int pathbias_get_dropguards(const or_options_t *options); void pathbias_count_timeout(origin_circuit_t *circ); int pathbias_check_close(origin_circuit_t *circ, int reason); int pathbias_check_probe_response(circuit_t *circ, const cell_t *cell); +void pathbias_count_use_attempt(origin_circuit_t *circ); +void pathbias_mark_use_success(origin_circuit_t *circ); #endif diff --git a/src/or/circuituse.c b/src/or/circuituse.c index 83734c9d6..48a774352 100644 --- a/src/or/circuituse.c +++ b/src/or/circuituse.c @@ -668,18 +668,6 @@ circuit_expire_building(void) circuit_build_times_set_timeout(&circ_times); } } - - if (TO_ORIGIN_CIRCUIT(victim)->has_opened && - victim->purpose != CIRCUIT_PURPOSE_PATH_BIAS_TESTING) { - /* For path bias: we want to let these guys live for a while - * so we get a chance to test them. */ - log_info(LD_CIRC, - "Allowing cannibalized circuit %d time to finish building " - "as a pathbias testing circ.", - TO_ORIGIN_CIRCUIT(victim)->global_identifier); - circuit_change_purpose(victim, CIRCUIT_PURPOSE_PATH_BIAS_TESTING); - continue; /* It now should have a longer timeout next time */ - } } /* If this is a hidden service client circuit which is far enough @@ -1090,7 +1078,10 @@ circuit_expire_old_circuits_clientside(void) "purpose %d)", circ->n_circ_id, (long)(now.tv_sec - circ->timestamp_dirty), circ->purpose); - circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED); + /* Don't do this magic for testing circuits. Their death is governed + * by circuit_expire_building */ + if (circ->purpose != CIRCUIT_PURPOSE_PATH_BIAS_TESTING) + circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED); } else if (!circ->timestamp_dirty && circ->state == CIRCUIT_STATE_OPEN) { if (timercmp(&circ->timestamp_began, &cutoff, <)) { if (circ->purpose == CIRCUIT_PURPOSE_C_GENERAL || @@ -1517,7 +1508,7 @@ circuit_launch_by_extend_info(uint8_t purpose, * If we decide to probe the initial portion of these circs, * (up to the adversaries final hop), we need to remove this. */ - circ->path_state = PATH_STATE_USE_SUCCEEDED; + /* This must be called before the purpose change */ pathbias_check_close(circ, END_CIRC_REASON_FINISHED); } @@ -2037,6 +2028,8 @@ connection_ap_handshake_attach_chosen_circuit(entry_connection_t *conn, if (!circ->base_.timestamp_dirty) circ->base_.timestamp_dirty = time(NULL); + pathbias_count_use_attempt(circ); + link_apconn_to_circ(conn, circ, cpath); tor_assert(conn->socks_request); if (conn->socks_request->command == SOCKS_COMMAND_CONNECT) { @@ -2163,6 +2156,11 @@ connection_ap_handshake_attach_circuit(entry_connection_t *conn) * feasibility, at this point. */ rendcirc->base_.timestamp_dirty = time(NULL); + + /* We've also attempted to use them. If they fail, we need to + * probe them for path bias */ + pathbias_count_use_attempt(rendcirc); + link_apconn_to_circ(conn, rendcirc, NULL); if (connection_ap_handshake_send_begin(conn) < 0) return 0; /* already marked, let them fade away */ @@ -2214,6 +2212,10 @@ connection_ap_handshake_attach_circuit(entry_connection_t *conn) case 0: /* success */ rendcirc->base_.timestamp_dirty = time(NULL); introcirc->base_.timestamp_dirty = time(NULL); + + pathbias_count_use_attempt(introcirc); + pathbias_count_use_attempt(rendcirc); + assert_circuit_ok(TO_CIRCUIT(rendcirc)); assert_circuit_ok(TO_CIRCUIT(introcirc)); return 0; diff --git a/src/or/config.c b/src/or/config.c index e50364546..dcd053ff6 100644 --- a/src/or/config.c +++ b/src/or/config.c @@ -296,7 +296,8 @@ static config_var_t option_vars_[] = { V(MaxAdvertisedBandwidth, MEMUNIT, "1 GB"), V(MaxCircuitDirtiness, INTERVAL, "10 minutes"), V(MaxClientCircuitsPending, UINT, "32"), - V(MaxOnionsPending, UINT, "100"), + OBSOLETE("MaxOnionsPending"), + V(MaxOnionQueueDelay, MSEC_INTERVAL, "1750 msec"), OBSOLETE("MonthlyAccountingStart"), V(MyFamily, STRING, NULL), V(NewCircuitPeriod, INTERVAL, "30 seconds"), @@ -323,7 +324,12 @@ static config_var_t option_vars_[] = { V(PathBiasScaleFactor, INT, "-1"), V(PathBiasMultFactor, INT, "-1"), V(PathBiasDropGuards, AUTOBOOL, "0"), - V(PathBiasUseCloseCounts, AUTOBOOL, "1"), + OBSOLETE("PathBiasUseCloseCounts"), + + V(PathBiasUseThreshold, INT, "-1"), + V(PathBiasNoticeUseRate, DOUBLE, "-1"), + V(PathBiasExtremeUseRate, DOUBLE, "-1"), + V(PathBiasScaleUseThreshold, INT, "-1"), V(PathsNeededToBuildCircuits, DOUBLE, "-1"), OBSOLETE("PathlenCoinWeight"), diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c index 870ded98c..9e2c15d2c 100644 --- a/src/or/connection_edge.c +++ b/src/or/connection_edge.c @@ -37,6 +37,7 @@ #include "router.h" #include "routerlist.h" #include "routerset.h" +#include "circuitbuild.h" #ifdef HAVE_LINUX_TYPES_H #include <linux/types.h> @@ -636,6 +637,16 @@ connection_ap_expire_beginning(void) } if (circ->purpose == CIRCUIT_PURPOSE_C_REND_JOINED) { if (seconds_idle >= options->SocksTimeout) { + /* Path bias: We need to probe the circuit to ensure validity. + * Roll its state back if it succeeded so that we do so upon close. */ + if (TO_ORIGIN_CIRCUIT(circ)->path_state == PATH_STATE_USE_SUCCEEDED) { + log_info(LD_CIRC, + "Rolling back pathbias use state to 'attempted' for timed " + "out rend circ %d", + TO_ORIGIN_CIRCUIT(circ)->global_identifier); + TO_ORIGIN_CIRCUIT(circ)->path_state = PATH_STATE_USE_ATTEMPTED; + } + log_fn(severity, LD_REND, "Rend stream is %d seconds late. Giving up on address" " '%s.onion'.", @@ -805,6 +816,15 @@ connection_ap_detach_retriable(entry_connection_t *conn, control_event_stream_status(conn, STREAM_EVENT_FAILED_RETRIABLE, reason); ENTRY_TO_CONN(conn)->timestamp_lastread = time(NULL); + /* Path bias: We need to probe the circuit to ensure validity. + * Roll its state back if it succeeded so that we do so upon close. */ + if (circ->path_state == PATH_STATE_USE_SUCCEEDED) { + log_info(LD_CIRC, + "Rolling back pathbias use state to 'attempted' for detached " + "circuit %d", circ->global_identifier); + circ->path_state = PATH_STATE_USE_ATTEMPTED; + } + if (conn->pending_optimistic_data) { generic_buffer_set_to_copy(&conn->sending_optimistic_data, conn->pending_optimistic_data); @@ -2205,8 +2225,10 @@ connection_ap_handshake_socks_reply(entry_connection_t *conn, char *reply, U64_PRINTF_ARG(ENTRY_TO_CONN(conn)->global_identifier), endreason); } else { - TO_ORIGIN_CIRCUIT(conn->edge_.on_circuit)->path_state - = PATH_STATE_USE_SUCCEEDED; + // XXX: Hrmm. It looks like optimistic data can't go through this + // codepath, but someone should probably test it and make sure. + // We don't want to mark optimistically opened streams as successful. + pathbias_mark_use_success(TO_ORIGIN_CIRCUIT(conn->edge_.on_circuit)); } } @@ -2480,7 +2502,7 @@ connection_exit_begin_conn(cell_t *cell, circuit_t *circ) connection_exit_connect(n_stream); /* For path bias: This circuit was used successfully */ - origin_circ->path_state = PATH_STATE_USE_SUCCEEDED; + pathbias_mark_use_success(origin_circ); tor_free(address); return 0; diff --git a/src/or/cpuworker.c b/src/or/cpuworker.c index 465f15516..b5740f091 100644 --- a/src/or/cpuworker.c +++ b/src/or/cpuworker.c @@ -98,6 +98,11 @@ typedef struct cpuworker_request_t { /** Task code. Must be one of CPUWORKER_TASK_* */ uint8_t task; + /** Flag: Are we timing this request? */ + unsigned timed : 1; + /** If we're timing this request, when was it sent to the cpuworker? */ + struct timeval started_at; + /** A create cell for the cpuworker to process. */ create_cell_t create_cell; @@ -113,6 +118,17 @@ typedef struct cpuworker_reply_t { /** True iff we got a successful request. */ uint8_t success; + /** Are we timing this request? */ + unsigned int timed : 1; + /** What handshake type was the request? (Used for timing) */ + uint16_t handshake_type; + /** When did we send the request to the cpuworker? */ + struct timeval started_at; + /** Once the cpuworker received the request, how many microseconds did it + * take? (This shouldn't overflow; 4 billion micoseconds is over an hour, + * and we'll never have an onion handshake that takes so long.) */ + uint32_t n_usec; + /** Output of processing a create cell * * @{ @@ -163,6 +179,110 @@ connection_cpu_reached_eof(connection_t *conn) return 0; } +/** Indexed by handshake type: how many onionskins have we processed and + * counted of that type? */ +static uint64_t onionskins_n_processed[MAX_ONION_HANDSHAKE_TYPE+1]; +/** Indexed by handshake type, corresponding to the onionskins counted in + * onionskins_n_processed: how many microseconds have we spent in cpuworkers + * processing that kind of onionskin? */ +static uint64_t onionskins_usec_internal[MAX_ONION_HANDSHAKE_TYPE+1]; +/** Indexed by handshake type, corresponding to onionskins counted in + * onionskins_n_processed: how many microseconds have we spent waiting for + * cpuworkers to give us answers for that kind of onionskin? + */ +static uint64_t onionskins_usec_roundtrip[MAX_ONION_HANDSHAKE_TYPE+1]; + +/** If any onionskin takes longer than this, we clip them to this + * time. (microseconds) */ +#define MAX_BELIEVABLE_ONIONSKIN_DELAY (2*1000*1000) + +/** Return true iff we'd like to measure a handshake of type + * <b>onionskin_type</b>. */ +static int +should_time_request(uint16_t onionskin_type) +{ + /* If we've never heard of this type, we shouldn't even be here. */ + if (onionskin_type > MAX_ONION_HANDSHAKE_TYPE) + return 0; + /* Measure the first N handshakes of each type, to ensure we have a + * sample */ + if (onionskins_n_processed[onionskin_type] < 4096) + return 1; + /** Otherwise, measure with P=1/128. We avoid doing this for every + * handshake, since the measurement itself can take a little time. */ + return tor_weak_random() < (TOR_RAND_MAX/128); +} + +/** Return an estimate of how many microseconds we will need for a single + * cpuworker to to process <b>n_requests</b> onionskins of type + * <b>onionskin_type</b>. */ +uint64_t +estimated_usec_for_onionskins(uint32_t n_requests, uint16_t onionskin_type) +{ + if (onionskin_type > MAX_ONION_HANDSHAKE_TYPE) /* should be impossible */ + return 1000 * n_requests; + if (PREDICT_UNLIKELY(onionskins_n_processed[onionskin_type] < 100)) { + /* Until we have 100 data points, just asssume everything takes 1 msec. */ + return 1000 * n_requests; + } else { + /* This can't overflow: we'll never have more than 500000 onionskins + * measured in onionskin_usec_internal, and they won't take anything near + * 1 sec each, and we won't have anything like 1 million queued + * onionskins. But that's 5e5 * 1e6 * 1e6, which is still less than + * UINT64_MAX. */ + return (onionskins_usec_internal[onionskin_type] * n_requests) / + onionskins_n_processed[onionskin_type]; + } +} + +/** Compute the absolute and relative overhead of using the cpuworker + * framework for onionskins of type <b>onionskin_type</b>.*/ +static int +get_overhead_for_onionskins(uint32_t *usec_out, double *frac_out, + uint16_t onionskin_type) +{ + uint64_t overhead; + + *usec_out = 0; + *frac_out = 0.0; + + if (onionskin_type > MAX_ONION_HANDSHAKE_TYPE) /* should be impossible */ + return -1; + if (onionskins_n_processed[onionskin_type] == 0 || + onionskins_usec_internal[onionskin_type] == 0 || + onionskins_usec_roundtrip[onionskin_type] == 0) + return -1; + + overhead = onionskins_usec_roundtrip[onionskin_type] - + onionskins_usec_internal[onionskin_type]; + + *usec_out = (uint32_t)(overhead / onionskins_n_processed[onionskin_type]); + *frac_out = U64_TO_DBL(overhead) / onionskins_usec_internal[onionskin_type]; + + return 0; +} + +/** If we've measured overhead for onionskins of type <b>onionskin_type</b>, + * log it. */ +void +cpuworker_log_onionskin_overhead(int severity, int onionskin_type, + const char *onionskin_type_name) +{ + uint32_t overhead; + double relative_overhead; + int r; + + r = get_overhead_for_onionskins(&overhead, &relative_overhead, + onionskin_type); + if (!overhead || r<0) + return; + + log_fn(severity, LD_OR, + "%s onionskins have averaged %u usec overhead (%.2f%%) in " + "cpuworker code ", + onionskin_type_name, (unsigned)overhead, relative_overhead*100); +} + /** Called when we get data from a cpuworker. If the answer is not complete, * wait for a complete answer. If the answer is complete, * process it as appropriate. @@ -190,6 +310,30 @@ connection_cpu_process_inbuf(connection_t *conn) connection_fetch_from_buf((void*)&rpl,sizeof(cpuworker_reply_t),conn); tor_assert(rpl.magic == CPUWORKER_REPLY_MAGIC); + + if (rpl.timed && rpl.success && + rpl.handshake_type <= MAX_ONION_HANDSHAKE_TYPE) { + /* Time how long this request took. The handshake_type check should be + needless, but let's leave it in to be safe. */ + struct timeval tv_end, tv_diff; + int64_t usec_roundtrip; + tor_gettimeofday(&tv_end); + timersub(&tv_end, &rpl.started_at, &tv_diff); + usec_roundtrip = ((int64_t)tv_diff.tv_sec)*1000000 + tv_diff.tv_usec; + if (usec_roundtrip >= 0 && + usec_roundtrip < MAX_BELIEVABLE_ONIONSKIN_DELAY) { + ++onionskins_n_processed[rpl.handshake_type]; + onionskins_usec_internal[rpl.handshake_type] += rpl.n_usec; + onionskins_usec_roundtrip[rpl.handshake_type] += usec_roundtrip; + if (onionskins_n_processed[rpl.handshake_type] >= 500000) { + /* Scale down every 500000 handshakes. On a busy server, that's + * less impressive than it sounds. */ + onionskins_n_processed[rpl.handshake_type] /= 2; + onionskins_usec_internal[rpl.handshake_type] /= 2; + onionskins_usec_roundtrip[rpl.handshake_type] /= 2; + } + } + } /* parse out the circ it was talking about */ tag_unpack(rpl.tag, &chan_id, &circ_id); circ = NULL; @@ -289,7 +433,13 @@ cpuworker_main(void *data) if (req.task == CPUWORKER_TASK_ONION) { const create_cell_t *cc = &req.create_cell; created_cell_t *cell_out = &rpl.created_cell; + struct timeval tv_start, tv_end; int n; + rpl.timed = req.timed; + rpl.started_at = req.started_at; + rpl.handshake_type = cc->handshake_type; + if (req.timed) + tor_gettimeofday(&tv_start); n = onion_skin_server_handshake(cc->handshake_type, cc->onionskin, cc->handshake_len, &onion_keys, @@ -321,6 +471,17 @@ cpuworker_main(void *data) rpl.success = 1; } rpl.magic = CPUWORKER_REPLY_MAGIC; + if (req.timed) { + struct timeval tv_diff; + int64_t usec; + tor_gettimeofday(&tv_end); + timersub(&tv_end, &tv_start, &tv_diff); + usec = ((int64_t)tv_diff.tv_sec)*1000000 + tv_diff.tv_usec; + if (usec < 0 || usec > MAX_BELIEVABLE_ONIONSKIN_DELAY) + rpl.n_usec = MAX_BELIEVABLE_ONIONSKIN_DELAY; + else + rpl.n_usec = (uint32_t) usec; + } if (write_all(fd, (void*)&rpl, sizeof(rpl), 1) != sizeof(rpl)) { log_err(LD_BUG,"writing response buf failed. Exiting."); goto end; @@ -478,6 +639,7 @@ assign_onionskin_to_cpuworker(connection_t *cpuworker, cpuworker_request_t req; time_t now = approx_time(); static time_t last_culled_cpuworkers = 0; + int should_time; /* Checking for wedged cpuworkers requires a linear search over all * connections, so let's do it only once a minute. @@ -512,16 +674,18 @@ assign_onionskin_to_cpuworker(connection_t *cpuworker, return -1; } + should_time = should_time_request(onionskin->handshake_type); memset(&req, 0, sizeof(req)); req.magic = CPUWORKER_REQUEST_MAGIC; tag_pack(req.tag, circ->p_chan->global_identifier, circ->p_circ_id); + req.timed = should_time; cpuworker->state = CPUWORKER_STATE_BUSY_ONION; /* touch the lastwritten timestamp, since that's how we check to * see how long it's been since we asked the question, and sometimes * we check before the first call to connection_handle_write(). */ - cpuworker->timestamp_lastwritten = time(NULL); + cpuworker->timestamp_lastwritten = now; num_cpuworkers_busy++; req.task = CPUWORKER_TASK_ONION; @@ -529,6 +693,9 @@ assign_onionskin_to_cpuworker(connection_t *cpuworker, tor_free(onionskin); + if (should_time) + tor_gettimeofday(&req.started_at); + connection_write_to_buf((void*)&req, sizeof(req), cpuworker); memwipe(&req, 0, sizeof(req)); } diff --git a/src/or/cpuworker.h b/src/or/cpuworker.h index 18d45153c..317cef43b 100644 --- a/src/or/cpuworker.h +++ b/src/or/cpuworker.h @@ -22,5 +22,10 @@ int assign_onionskin_to_cpuworker(connection_t *cpuworker, or_circuit_t *circ, struct create_cell_t *onionskin); +uint64_t estimated_usec_for_onionskins(uint32_t n_requests, + uint16_t onionskin_type); +void cpuworker_log_onionskin_overhead(int severity, int onionskin_type, + const char *onionskin_type_name); + #endif diff --git a/src/or/directory.c b/src/or/directory.c index 692a6d6b2..c68a4e3b2 100644 --- a/src/or/directory.c +++ b/src/or/directory.c @@ -2800,8 +2800,6 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, /* v2 or v3 network status fetch. */ smartlist_t *dir_fps = smartlist_new(); int is_v3 = !strcmpstart(url, "/tor/status-vote"); - geoip_client_action_t act = - is_v3 ? GEOIP_CLIENT_NETWORKSTATUS : GEOIP_CLIENT_NETWORKSTATUS_V2; const char *request_type = NULL; const char *key = url + strlen("/tor/status/"); long lifetime = NETWORKSTATUS_CACHE_LIFETIME; @@ -2851,7 +2849,7 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, write_http_status_line(conn, 404, "Consensus not signed by sufficient " "number of requested authorities"); smartlist_free(dir_fps); - geoip_note_ns_response(act, GEOIP_REJECT_NOT_ENOUGH_SIGS); + geoip_note_ns_response(GEOIP_REJECT_NOT_ENOUGH_SIGS); tor_free(flavor); goto done; } @@ -2870,7 +2868,8 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, if (!smartlist_len(dir_fps)) { /* we failed to create/cache cp */ write_http_status_line(conn, 503, "Network status object unavailable"); smartlist_free(dir_fps); - geoip_note_ns_response(act, GEOIP_REJECT_UNAVAILABLE); + if (is_v3) + geoip_note_ns_response(GEOIP_REJECT_UNAVAILABLE); goto done; } @@ -2878,13 +2877,15 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, write_http_status_line(conn, 404, "Not found"); SMARTLIST_FOREACH(dir_fps, char *, cp, tor_free(cp)); smartlist_free(dir_fps); - geoip_note_ns_response(act, GEOIP_REJECT_NOT_FOUND); + if (is_v3) + geoip_note_ns_response(GEOIP_REJECT_NOT_FOUND); goto done; } else if (!smartlist_len(dir_fps)) { write_http_status_line(conn, 304, "Not modified"); SMARTLIST_FOREACH(dir_fps, char *, cp, tor_free(cp)); smartlist_free(dir_fps); - geoip_note_ns_response(act, GEOIP_REJECT_NOT_MODIFIED); + if (is_v3) + geoip_note_ns_response(GEOIP_REJECT_NOT_MODIFIED); goto done; } @@ -2896,24 +2897,24 @@ directory_handle_command_get(dir_connection_t *conn, const char *headers, write_http_status_line(conn, 503, "Directory busy, try again later"); SMARTLIST_FOREACH(dir_fps, char *, fp, tor_free(fp)); smartlist_free(dir_fps); - geoip_note_ns_response(act, GEOIP_REJECT_BUSY); + if (is_v3) + geoip_note_ns_response(GEOIP_REJECT_BUSY); goto done; } - { + if (is_v3) { struct in_addr in; tor_addr_t addr; if (tor_inet_aton((TO_CONN(conn))->address, &in)) { tor_addr_from_ipv4h(&addr, ntohl(in.s_addr)); - geoip_note_client_seen(act, &addr, time(NULL)); - geoip_note_ns_response(act, GEOIP_SUCCESS); + geoip_note_client_seen(GEOIP_CLIENT_NETWORKSTATUS, &addr, time(NULL)); + geoip_note_ns_response(GEOIP_SUCCESS); /* Note that a request for a network status has started, so that we * can measure the download time later on. */ if (conn->dirreq_id) - geoip_start_dirreq(conn->dirreq_id, dlen, act, - DIRREQ_TUNNELED); + geoip_start_dirreq(conn->dirreq_id, dlen, DIRREQ_TUNNELED); else - geoip_start_dirreq(TO_CONN(conn)->global_identifier, dlen, act, + geoip_start_dirreq(TO_CONN(conn)->global_identifier, dlen, DIRREQ_DIRECT); } } diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c index 3e5837164..4ca56cbac 100644 --- a/src/or/entrynodes.c +++ b/src/or/entrynodes.c @@ -1098,6 +1098,40 @@ entry_guards_parse_state(or_state_t *state, int set, char **msg) continue; } digestmap_set(added_by, d, tor_strdup(line->value+HEX_DIGEST_LEN+1)); + } else if (!strcasecmp(line->key, "EntryGuardPathUseBias")) { + const or_options_t *options = get_options(); + double use_cnt, success_cnt; + + if (!node) { + *msg = tor_strdup("Unable to parse entry nodes: " + "EntryGuardPathUseBias without EntryGuard"); + break; + } + + if (tor_sscanf(line->value, "%lf %lf", + &use_cnt, &success_cnt) != 2) { + log_info(LD_GENERAL, "Malformed path use bias line for node %s", + node->nickname); + continue; + } + + node->use_attempts = use_cnt; + node->use_successes = success_cnt; + + log_info(LD_GENERAL, "Read %f/%f path use bias for node %s", + node->use_successes, node->use_attempts, node->nickname); + + /* Note: We rely on the < comparison here to allow us to set a 0 + * rate and disable the feature entirely. If refactoring, don't + * change to <= */ + if (pathbias_get_use_success_count(node)/node->use_attempts + < pathbias_get_extreme_use_rate(options) && + pathbias_get_dropguards(options)) { + node->path_bias_disabled = 1; + log_info(LD_GENERAL, + "Path use bias is too high (%f/%f); disabling node %s", + node->circ_successes, node->circ_attempts, node->nickname); + } } else if (!strcasecmp(line->key, "EntryGuardPathBias")) { const or_options_t *options = get_options(); double hop_cnt, success_cnt, timeouts, collapsed, successful_closed, @@ -1144,7 +1178,7 @@ entry_guards_parse_state(or_state_t *state, int set, char **msg) /* Note: We rely on the < comparison here to allow us to set a 0 * rate and disable the feature entirely. If refactoring, don't * change to <= */ - if (pathbias_get_success_count(node)/node->circ_attempts + if (pathbias_get_close_success_count(node)/node->circ_attempts < pathbias_get_extreme_rate(options) && pathbias_get_dropguards(options)) { node->path_bias_disabled = 1; @@ -1282,10 +1316,20 @@ entry_guards_update_state(or_state_t *state) * unusable_circuits */ tor_asprintf(&line->value, "%f %f %f %f %f %f", e->circ_attempts, e->circ_successes, - pathbias_get_closed_count(e), e->collapsed_circuits, + pathbias_get_close_success_count(e), + e->collapsed_circuits, e->unusable_circuits, e->timeouts); next = &(line->next); } + if (e->use_attempts > 0) { + *next = line = tor_malloc_zero(sizeof(config_line_t)); + line->key = tor_strdup("EntryGuardPathUseBias"); + + tor_asprintf(&line->value, "%f %f", + e->use_attempts, + pathbias_get_use_success_count(e)); + next = &(line->next); + } } SMARTLIST_FOREACH_END(e); if (!get_options()->AvoidDiskWrites) diff --git a/src/or/entrynodes.h b/src/or/entrynodes.h index 1e52ba28e..e6c973c95 100644 --- a/src/or/entrynodes.h +++ b/src/or/entrynodes.h @@ -61,6 +61,9 @@ typedef struct entry_guard_t { * attempted, but none succeeded. */ double timeouts; /**< Number of 'right-censored' circuit timeouts for this * guard. */ + double use_attempts; /**< Number of circuits we tried to use with streams */ + double use_successes; /**< Number of successfully used circuits using + * this guard as first hop. */ } entry_guard_t; entry_guard_t *entry_guard_get_by_id_digest(const char *digest); @@ -113,8 +116,8 @@ int find_transport_by_bridge_addrport(const tor_addr_t *addr, uint16_t port, int validate_pluggable_transports_config(void); -double pathbias_get_closed_count(entry_guard_t *gaurd); -double pathbias_get_success_count(entry_guard_t *guard); +double pathbias_get_close_success_count(entry_guard_t *guard); +double pathbias_get_use_success_count(entry_guard_t *guard); #endif diff --git a/src/or/geoip.c b/src/or/geoip.c index f9d036e07..9ba1e31b8 100644 --- a/src/or/geoip.c +++ b/src/or/geoip.c @@ -38,7 +38,6 @@ typedef struct geoip_ipv6_entry_t { /** A per-country record for GeoIP request history. */ typedef struct geoip_country_t { char countrycode[3]; - uint32_t n_v2_ns_requests; uint32_t n_v3_ns_requests; } geoip_country_t; @@ -515,67 +514,6 @@ client_history_clear(void) } } -/** How often do we update our estimate which share of v2 and v3 directory - * requests is sent to us? We could as well trigger updates of shares from - * network status updates, but that means adding a lot of calls into code - * that is independent from geoip stats (and keeping them up-to-date). We - * are perfectly fine with an approximation of 15-minute granularity. */ -#define REQUEST_SHARE_INTERVAL (15 * 60) - -/** When did we last determine which share of v2 and v3 directory requests - * is sent to us? */ -static time_t last_time_determined_shares = 0; - -/** Sum of products of v2 shares times the number of seconds for which we - * consider these shares as valid. */ -static double v2_share_times_seconds; - -/** Sum of products of v3 shares times the number of seconds for which we - * consider these shares as valid. */ -static double v3_share_times_seconds; - -/** Number of seconds we are determining v2 and v3 shares. */ -static int share_seconds; - -/** Try to determine which fraction of v2 and v3 directory requests aimed at - * caches will be sent to us at time <b>now</b> and store that value in - * order to take a mean value later on. */ -static void -geoip_determine_shares(time_t now) -{ - double v2_share = 0.0, v3_share = 0.0; - if (router_get_my_share_of_directory_requests(&v2_share, &v3_share) < 0) - return; - if (last_time_determined_shares) { - v2_share_times_seconds += v2_share * - ((double) (now - last_time_determined_shares)); - v3_share_times_seconds += v3_share * - ((double) (now - last_time_determined_shares)); - share_seconds += (int)(now - last_time_determined_shares); - } - last_time_determined_shares = now; -} - -/** Calculate which fraction of v2 and v3 directory requests aimed at caches - * have been sent to us since the last call of this function up to time - * <b>now</b>. Set *<b>v2_share_out</b> and *<b>v3_share_out</b> to the - * fractions of v2 and v3 protocol shares we expect to have seen. Reset - * counters afterwards. Return 0 on success, -1 on failure (e.g. when zero - * seconds have passed since the last call).*/ -static int -geoip_get_mean_shares(time_t now, double *v2_share_out, - double *v3_share_out) -{ - geoip_determine_shares(now); - if (!share_seconds) - return -1; - *v2_share_out = v2_share_times_seconds / ((double) share_seconds); - *v3_share_out = v3_share_times_seconds / ((double) share_seconds); - v2_share_times_seconds = v3_share_times_seconds = 0.0; - share_seconds = 0; - return 0; -} - /** Note that we've seen a client connect from the IP <b>addr</b> * at time <b>now</b>. Ignored by all but bridges and directories if * configured accordingly. */ @@ -610,22 +548,14 @@ geoip_note_client_seen(geoip_client_action_t action, else ent->last_seen_in_minutes = 0; - if (action == GEOIP_CLIENT_NETWORKSTATUS || - action == GEOIP_CLIENT_NETWORKSTATUS_V2) { + if (action == GEOIP_CLIENT_NETWORKSTATUS) { int country_idx = geoip_get_country_by_addr(addr); if (country_idx < 0) country_idx = 0; /** unresolved requests are stored at index 0. */ if (country_idx >= 0 && country_idx < smartlist_len(geoip_countries)) { geoip_country_t *country = smartlist_get(geoip_countries, country_idx); - if (action == GEOIP_CLIENT_NETWORKSTATUS) - ++country->n_v3_ns_requests; - else - ++country->n_v2_ns_requests; + ++country->n_v3_ns_requests; } - - /* Periodically determine share of requests that we should see */ - if (last_time_determined_shares + REQUEST_SHARE_INTERVAL < now) - geoip_determine_shares(now); } } @@ -652,36 +582,24 @@ geoip_remove_old_clients(time_t cutoff) &cutoff); } -/** How many responses are we giving to clients requesting v2 network - * statuses? */ -static uint32_t ns_v2_responses[GEOIP_NS_RESPONSE_NUM]; - /** How many responses are we giving to clients requesting v3 network * statuses? */ static uint32_t ns_v3_responses[GEOIP_NS_RESPONSE_NUM]; -/** Note that we've rejected a client's request for a v2 or v3 network - * status, encoded in <b>action</b> for reason <b>reason</b> at time - * <b>now</b>. */ +/** Note that we've rejected a client's request for a v3 network status + * for reason <b>reason</b> at time <b>now</b>. */ void -geoip_note_ns_response(geoip_client_action_t action, - geoip_ns_response_t response) +geoip_note_ns_response(geoip_ns_response_t response) { static int arrays_initialized = 0; if (!get_options()->DirReqStatistics) return; if (!arrays_initialized) { - memset(ns_v2_responses, 0, sizeof(ns_v2_responses)); memset(ns_v3_responses, 0, sizeof(ns_v3_responses)); arrays_initialized = 1; } - tor_assert(action == GEOIP_CLIENT_NETWORKSTATUS || - action == GEOIP_CLIENT_NETWORKSTATUS_V2); tor_assert(response < GEOIP_NS_RESPONSE_NUM); - if (action == GEOIP_CLIENT_NETWORKSTATUS) - ns_v3_responses[response]++; - else - ns_v2_responses[response]++; + ns_v3_responses[response]++; } /** Do not mention any country from which fewer than this number of IPs have @@ -736,7 +654,6 @@ typedef struct dirreq_map_entry_t { unsigned int state:3; /**< State of this directory request. */ unsigned int type:1; /**< Is this a direct or a tunneled request? */ unsigned int completed:1; /**< Is this request complete? */ - unsigned int action:2; /**< Is this a v2 or v3 request? */ /** When did we receive the request and started sending the response? */ struct timeval request_time; size_t response_size; /**< What is the size of the response in bytes? */ @@ -805,12 +722,11 @@ dirreq_map_get_(dirreq_type_t type, uint64_t dirreq_id) } /** Note that an either direct or tunneled (see <b>type</b>) directory - * request for a network status with unique ID <b>dirreq_id</b> of size - * <b>response_size</b> and action <b>action</b> (either v2 or v3) has - * started. */ + * request for a v3 network status with unique ID <b>dirreq_id</b> of size + * <b>response_size</b> has started. */ void geoip_start_dirreq(uint64_t dirreq_id, size_t response_size, - geoip_client_action_t action, dirreq_type_t type) + dirreq_type_t type) { dirreq_map_entry_t *ent; if (!get_options()->DirReqStatistics) @@ -819,7 +735,6 @@ geoip_start_dirreq(uint64_t dirreq_id, size_t response_size, ent->dirreq_id = dirreq_id; tor_gettimeofday(&ent->request_time); ent->response_size = response_size; - ent->action = action; ent->type = type; dirreq_map_put_(ent, type, dirreq_id); } @@ -860,8 +775,7 @@ geoip_change_dirreq_state(uint64_t dirreq_id, dirreq_type_t type, * times by deciles and quartiles. Return NULL if we have not observed * requests for long enough. */ static char * -geoip_get_dirreq_history(geoip_client_action_t action, - dirreq_type_t type) +geoip_get_dirreq_history(dirreq_type_t type) { char *result = NULL; smartlist_t *dirreq_completed = NULL; @@ -871,13 +785,10 @@ geoip_get_dirreq_history(geoip_client_action_t action, struct timeval now; tor_gettimeofday(&now); - if (action != GEOIP_CLIENT_NETWORKSTATUS && - action != GEOIP_CLIENT_NETWORKSTATUS_V2) - return NULL; dirreq_completed = smartlist_new(); for (ptr = HT_START(dirreqmap, &dirreq_map); ptr; ptr = next) { ent = *ptr; - if (ent->action != action || ent->type != type) { + if (ent->type != type) { next = HT_NEXT(dirreqmap, &dirreq_map, ptr); continue; } else { @@ -1063,18 +974,15 @@ geoip_get_client_history(geoip_client_action_t action, } /** Return a newly allocated string holding the per-country request history - * for <b>action</b> in a format suitable for an extra-info document, or NULL - * on failure. */ + * for v3 network statuses in a format suitable for an extra-info document, + * or NULL on failure. */ char * -geoip_get_request_history(geoip_client_action_t action) +geoip_get_request_history(void) { smartlist_t *entries, *strings; char *result; unsigned granularity = IP_GRANULARITY; - if (action != GEOIP_CLIENT_NETWORKSTATUS && - action != GEOIP_CLIENT_NETWORKSTATUS_V2) - return NULL; if (!geoip_countries) return NULL; @@ -1082,8 +990,7 @@ geoip_get_request_history(geoip_client_action_t action) SMARTLIST_FOREACH_BEGIN(geoip_countries, geoip_country_t *, c) { uint32_t tot = 0; c_hist_t *ent; - tot = (action == GEOIP_CLIENT_NETWORKSTATUS) ? - c->n_v3_ns_requests : c->n_v2_ns_requests; + tot = c->n_v3_ns_requests; if (!tot) continue; ent = tor_malloc_zero(sizeof(c_hist_t)); @@ -1121,14 +1028,13 @@ void geoip_reset_dirreq_stats(time_t now) { SMARTLIST_FOREACH(geoip_countries, geoip_country_t *, c, { - c->n_v2_ns_requests = c->n_v3_ns_requests = 0; + c->n_v3_ns_requests = 0; }); { clientmap_entry_t **ent, **next, *this; for (ent = HT_START(clientmap, &client_history); ent != NULL; ent = next) { - if ((*ent)->action == GEOIP_CLIENT_NETWORKSTATUS || - (*ent)->action == GEOIP_CLIENT_NETWORKSTATUS_V2) { + if ((*ent)->action == GEOIP_CLIENT_NETWORKSTATUS) { this = *ent; next = HT_NEXT_RMV(clientmap, &client_history, ent); tor_free(this); @@ -1137,10 +1043,6 @@ geoip_reset_dirreq_stats(time_t now) } } } - v2_share_times_seconds = v3_share_times_seconds = 0.0; - last_time_determined_shares = 0; - share_seconds = 0; - memset(ns_v2_responses, 0, sizeof(ns_v2_responses)); memset(ns_v3_responses, 0, sizeof(ns_v3_responses)); { dirreq_map_entry_t **ent, **next, *this; @@ -1168,12 +1070,9 @@ char * geoip_format_dirreq_stats(time_t now) { char t[ISO_TIME_LEN+1]; - double v2_share = 0.0, v3_share = 0.0; int i; - char *v3_ips_string, *v2_ips_string, *v3_reqs_string, *v2_reqs_string, - *v2_share_string = NULL, *v3_share_string = NULL, - *v3_direct_dl_string, *v2_direct_dl_string, - *v3_tunneled_dl_string, *v2_tunneled_dl_string; + char *v3_ips_string, *v3_reqs_string, *v3_direct_dl_string, + *v3_tunneled_dl_string; char *result; if (!start_of_dirreq_stats_interval) @@ -1182,90 +1081,45 @@ geoip_format_dirreq_stats(time_t now) tor_assert(now >= start_of_dirreq_stats_interval); format_iso_time(t, now); - geoip_get_client_history(GEOIP_CLIENT_NETWORKSTATUS_V2, &v2_ips_string, - NULL); geoip_get_client_history(GEOIP_CLIENT_NETWORKSTATUS, &v3_ips_string, NULL); - v2_reqs_string = geoip_get_request_history( - GEOIP_CLIENT_NETWORKSTATUS_V2); - v3_reqs_string = geoip_get_request_history(GEOIP_CLIENT_NETWORKSTATUS); + v3_reqs_string = geoip_get_request_history(); #define RESPONSE_GRANULARITY 8 for (i = 0; i < GEOIP_NS_RESPONSE_NUM; i++) { - ns_v2_responses[i] = round_uint32_to_next_multiple_of( - ns_v2_responses[i], RESPONSE_GRANULARITY); ns_v3_responses[i] = round_uint32_to_next_multiple_of( ns_v3_responses[i], RESPONSE_GRANULARITY); } #undef RESPONSE_GRANULARITY - if (!geoip_get_mean_shares(now, &v2_share, &v3_share)) { - tor_asprintf(&v2_share_string, "dirreq-v2-share %0.2f%%\n", - v2_share*100); - tor_asprintf(&v3_share_string, "dirreq-v3-share %0.2f%%\n", - v3_share*100); - } - - v2_direct_dl_string = geoip_get_dirreq_history( - GEOIP_CLIENT_NETWORKSTATUS_V2, DIRREQ_DIRECT); - v3_direct_dl_string = geoip_get_dirreq_history( - GEOIP_CLIENT_NETWORKSTATUS, DIRREQ_DIRECT); - - v2_tunneled_dl_string = geoip_get_dirreq_history( - GEOIP_CLIENT_NETWORKSTATUS_V2, DIRREQ_TUNNELED); - v3_tunneled_dl_string = geoip_get_dirreq_history( - GEOIP_CLIENT_NETWORKSTATUS, DIRREQ_TUNNELED); + v3_direct_dl_string = geoip_get_dirreq_history(DIRREQ_DIRECT); + v3_tunneled_dl_string = geoip_get_dirreq_history(DIRREQ_TUNNELED); /* Put everything together into a single string. */ tor_asprintf(&result, "dirreq-stats-end %s (%d s)\n" "dirreq-v3-ips %s\n" - "dirreq-v2-ips %s\n" "dirreq-v3-reqs %s\n" - "dirreq-v2-reqs %s\n" "dirreq-v3-resp ok=%u,not-enough-sigs=%u,unavailable=%u," "not-found=%u,not-modified=%u,busy=%u\n" - "dirreq-v2-resp ok=%u,unavailable=%u," - "not-found=%u,not-modified=%u,busy=%u\n" - "%s" - "%s" "dirreq-v3-direct-dl %s\n" - "dirreq-v2-direct-dl %s\n" - "dirreq-v3-tunneled-dl %s\n" - "dirreq-v2-tunneled-dl %s\n", + "dirreq-v3-tunneled-dl %s\n", t, (unsigned) (now - start_of_dirreq_stats_interval), v3_ips_string ? v3_ips_string : "", - v2_ips_string ? v2_ips_string : "", v3_reqs_string ? v3_reqs_string : "", - v2_reqs_string ? v2_reqs_string : "", ns_v3_responses[GEOIP_SUCCESS], ns_v3_responses[GEOIP_REJECT_NOT_ENOUGH_SIGS], ns_v3_responses[GEOIP_REJECT_UNAVAILABLE], ns_v3_responses[GEOIP_REJECT_NOT_FOUND], ns_v3_responses[GEOIP_REJECT_NOT_MODIFIED], ns_v3_responses[GEOIP_REJECT_BUSY], - ns_v2_responses[GEOIP_SUCCESS], - ns_v2_responses[GEOIP_REJECT_UNAVAILABLE], - ns_v2_responses[GEOIP_REJECT_NOT_FOUND], - ns_v2_responses[GEOIP_REJECT_NOT_MODIFIED], - ns_v2_responses[GEOIP_REJECT_BUSY], - v2_share_string ? v2_share_string : "", - v3_share_string ? v3_share_string : "", v3_direct_dl_string ? v3_direct_dl_string : "", - v2_direct_dl_string ? v2_direct_dl_string : "", - v3_tunneled_dl_string ? v3_tunneled_dl_string : "", - v2_tunneled_dl_string ? v2_tunneled_dl_string : ""); + v3_tunneled_dl_string ? v3_tunneled_dl_string : ""); /* Free partial strings. */ tor_free(v3_ips_string); - tor_free(v2_ips_string); tor_free(v3_reqs_string); - tor_free(v2_reqs_string); - tor_free(v2_share_string); - tor_free(v3_share_string); tor_free(v3_direct_dl_string); - tor_free(v2_direct_dl_string); tor_free(v3_tunneled_dl_string); - tor_free(v2_tunneled_dl_string); return result; } diff --git a/src/or/geoip.h b/src/or/geoip.h index 60d44a553..ebefee5f4 100644 --- a/src/or/geoip.h +++ b/src/or/geoip.h @@ -30,18 +30,17 @@ void geoip_note_client_seen(geoip_client_action_t action, const tor_addr_t *addr, time_t now); void geoip_remove_old_clients(time_t cutoff); -void geoip_note_ns_response(geoip_client_action_t action, - geoip_ns_response_t response); +void geoip_note_ns_response(geoip_ns_response_t response); int geoip_get_client_history(geoip_client_action_t action, char **country_str, char **ipver_str); -char *geoip_get_request_history(geoip_client_action_t action); +char *geoip_get_request_history(void); int getinfo_helper_geoip(control_connection_t *control_conn, const char *question, char **answer, const char **errmsg); void geoip_free_all(void); void geoip_start_dirreq(uint64_t dirreq_id, size_t response_size, - geoip_client_action_t action, dirreq_type_t type); + dirreq_type_t type); void geoip_change_dirreq_state(uint64_t dirreq_id, dirreq_type_t type, dirreq_state_t new_state); diff --git a/src/or/main.c b/src/or/main.c index 1dd207a75..3cdfe8acf 100644 --- a/src/or/main.c +++ b/src/or/main.c @@ -2202,6 +2202,9 @@ dumpstats(int severity) 100*(U64_TO_DBL(stats_n_data_bytes_received) / U64_TO_DBL(stats_n_data_cells_received*RELAY_PAYLOAD_SIZE)) ); + cpuworker_log_onionskin_overhead(severity, ONION_HANDSHAKE_TYPE_TAP, "TAP"); + cpuworker_log_onionskin_overhead(severity, ONION_HANDSHAKE_TYPE_NTOR,"ntor"); + if (now - time_of_process_start >= 0) elapsed = now - time_of_process_start; else diff --git a/src/or/onion.c b/src/or/onion.c index 4625346f2..e4cdea6bb 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -13,6 +13,7 @@ #include "or.h" #include "circuitlist.h" #include "config.h" +#include "cpuworker.h" #include "onion.h" #include "onion_fast.h" #include "onion_ntor.h" @@ -20,29 +21,71 @@ #include "relay.h" #include "rephist.h" #include "router.h" +#include "tor_queue.h" /** Type for a linked list of circuits that are waiting for a free CPU worker * to process a waiting onion handshake. */ typedef struct onion_queue_t { + TAILQ_ENTRY(onion_queue_t) next; or_circuit_t *circ; create_cell_t *onionskin; time_t when_added; - struct onion_queue_t *next; } onion_queue_t; /** 5 seconds on the onion queue til we just send back a destroy */ #define ONIONQUEUE_WAIT_CUTOFF 5 -/** First and last elements in the linked list of circuits waiting for CPU - * workers, or NULL if the list is empty. - * @{ */ -static onion_queue_t *ol_list=NULL; -static onion_queue_t *ol_tail=NULL; -/**@}*/ -/** Length of ol_list */ -static int ol_length=0; +/** Queue of circuits waiting for CPU workers, or NULL if the list is empty.*/ +TAILQ_HEAD(onion_queue_head_t, onion_queue_t) ol_list = + TAILQ_HEAD_INITIALIZER(ol_list); -/* XXXX Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN */ +/** Number of entries of each type currently in ol_list. */ +static int ol_entries[MAX_ONION_HANDSHAKE_TYPE+1]; + +static void onion_queue_entry_remove(onion_queue_t *victim); + +/* XXXX024 Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN. + * + * (By which I think I meant, "make sure that no + * X_ONIONSKIN_CHALLENGE/REPLY_LEN is greater than + * MAX_ONIONSKIN_CHALLENGE/REPLY_LEN." Also, make sure that we can pass + * over-large values via EXTEND2/EXTENDED2, for future-compatibility.*/ + +/** Return true iff we have room to queue another oninoskin of type + * <b>type</b>. */ +static int +have_room_for_onionskin(uint16_t type) +{ + const or_options_t *options = get_options(); + int num_cpus; + uint64_t tap_usec, ntor_usec; + /* If we've got fewer than 50 entries, we always have room for one more. */ + if (ol_entries[ONION_HANDSHAKE_TYPE_TAP] + + ol_entries[ONION_HANDSHAKE_TYPE_NTOR] < 50) + return 1; + num_cpus = get_num_cpus(options); + /* Compute how many microseconds we'd expect to need to clear all + * onionskins in the current queue. */ + tap_usec = estimated_usec_for_onionskins( + ol_entries[ONION_HANDSHAKE_TYPE_TAP], + ONION_HANDSHAKE_TYPE_TAP) / num_cpus; + ntor_usec = estimated_usec_for_onionskins( + ol_entries[ONION_HANDSHAKE_TYPE_NTOR], + ONION_HANDSHAKE_TYPE_NTOR) / num_cpus; + /* See whether that exceeds MaxOnionQueueDelay. If so, we can't queue + * this. */ + if ((tap_usec + ntor_usec) / 1000 > (uint64_t)options->MaxOnionQueueDelay) + return 0; +#ifdef CURVE25519_ENABLED + /* If we support the ntor handshake, then don't let TAP handshakes use + * more than 2/3 of the space on the queue. */ + if (type == ONION_HANDSHAKE_TYPE_TAP && + tap_usec / 1000 > (uint64_t)options->MaxOnionQueueDelay * 2 / 3) + return 0; +#endif + + return 1; +} /** Add <b>circ</b> to the end of ol_list and return 0, except * if ol_list is too long, in which case do nothing and return -1. @@ -58,19 +101,7 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) tmp->onionskin = onionskin; tmp->when_added = now; - if (!ol_tail) { - tor_assert(!ol_list); - tor_assert(!ol_length); - ol_list = tmp; - ol_tail = tmp; - ol_length++; - return 0; - } - - tor_assert(ol_list); - tor_assert(!ol_tail->next); - - if (ol_length >= get_options()->MaxOnionsPending) { + if (!have_room_for_onionskin(onionskin->handshake_type)) { #define WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL (60) static ratelim_t last_warned = RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL); @@ -87,13 +118,19 @@ onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin) return -1; } - ol_length++; - ol_tail->next = tmp; - ol_tail = tmp; - while ((int)(now - ol_list->when_added) >= ONIONQUEUE_WAIT_CUTOFF) { - /* cull elderly requests. */ - circ = ol_list->circ; - onion_pending_remove(ol_list->circ); + ++ol_entries[onionskin->handshake_type]; + circ->onionqueue_entry = tmp; + TAILQ_INSERT_TAIL(&ol_list, tmp, next); + + /* cull elderly requests. */ + while (1) { + onion_queue_t *head = TAILQ_FIRST(&ol_list); + if (now - head->when_added < (time_t)ONIONQUEUE_WAIT_CUTOFF) + break; + + circ = head->circ; + circ->onionqueue_entry = NULL; + onion_queue_entry_remove(head); log_info(LD_CIRC, "Circuit create request is too old; canceling due to overload."); circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_RESOURCELIMIT); @@ -108,17 +145,21 @@ or_circuit_t * onion_next_task(create_cell_t **onionskin_out) { or_circuit_t *circ; + onion_queue_t *head = TAILQ_FIRST(&ol_list); - if (!ol_list) + if (!head) return NULL; /* no onions pending, we're done */ - tor_assert(ol_list->circ); - tor_assert(ol_list->circ->p_chan); /* make sure it's still valid */ - tor_assert(ol_length > 0); - circ = ol_list->circ; - *onionskin_out = ol_list->onionskin; - ol_list->onionskin = NULL; /* prevent free. */ - onion_pending_remove(ol_list->circ); + tor_assert(head->circ); + tor_assert(head->circ->p_chan); /* make sure it's still valid */ + circ = head->circ; + if (head->onionskin && + head->onionskin->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) + --ol_entries[head->onionskin->handshake_type]; + *onionskin_out = head->onionskin; + head->onionskin = NULL; /* prevent free. */ + circ->onionqueue_entry = NULL; + onion_queue_entry_remove(head); return circ; } @@ -128,37 +169,29 @@ onion_next_task(create_cell_t **onionskin_out) void onion_pending_remove(or_circuit_t *circ) { - onion_queue_t *tmpo, *victim; - - if (!ol_list) - return; /* nothing here. */ - - /* first check to see if it's the first entry */ - tmpo = ol_list; - if (tmpo->circ == circ) { - /* it's the first one. remove it from the list. */ - ol_list = tmpo->next; - if (!ol_list) - ol_tail = NULL; - ol_length--; - victim = tmpo; - } else { /* we need to hunt through the rest of the list */ - for ( ;tmpo->next && tmpo->next->circ != circ; tmpo=tmpo->next) ; - if (!tmpo->next) { - log_debug(LD_GENERAL, - "circ (p_circ_id %d) not in list, probably at cpuworker.", - circ->p_circ_id); - return; - } - /* now we know tmpo->next->circ == circ */ - victim = tmpo->next; - tmpo->next = victim->next; - if (ol_tail == victim) - ol_tail = tmpo; - ol_length--; - } + onion_queue_t *victim; + + if (!circ) + return; + + victim = circ->onionqueue_entry; + if (victim) + onion_queue_entry_remove(victim); +} + +/** Remove a queue entry <b>victim</b> from the queue, unlinking it from + * its circuit and freeing it and any structures it owns.*/ +static void +onion_queue_entry_remove(onion_queue_t *victim) +{ + TAILQ_REMOVE(&ol_list, victim, next); + + if (victim->circ) + victim->circ->onionqueue_entry = NULL; - /* now victim points to the element that needs to be removed */ + if (victim->onionskin && + victim->onionskin->handshake_type <= MAX_ONION_HANDSHAKE_TYPE) + --ol_entries[victim->onionskin->handshake_type]; tor_free(victim->onionskin); tor_free(victim); @@ -168,14 +201,11 @@ onion_pending_remove(or_circuit_t *circ) void clear_pending_onions(void) { - while (ol_list) { - onion_queue_t *victim = ol_list; - ol_list = victim->next; - tor_free(victim->onionskin); - tor_free(victim); + onion_queue_t *victim; + while ((victim = TAILQ_FIRST(&ol_list))) { + onion_queue_entry_remove(victim); } - ol_list = ol_tail = NULL; - ol_length = 0; + memset(ol_entries, 0, sizeof(ol_entries)); } /* ============================================================ */ diff --git a/src/or/onion.h b/src/or/onion.h index 8b5fb7e3b..db4c999c9 100644 --- a/src/or/onion.h +++ b/src/or/onion.h @@ -101,9 +101,9 @@ typedef struct extended_cell_t { int create_cell_parse(create_cell_t *cell_out, const cell_t *cell_in); int created_cell_parse(created_cell_t *cell_out, const cell_t *cell_in); -int extend_cell_parse(extend_cell_t *cell_out, uint8_t command, +int extend_cell_parse(extend_cell_t *cell_out, const uint8_t command, const uint8_t *payload_in, size_t payload_len); -int extended_cell_parse(extended_cell_t *cell_out, uint8_t command, +int extended_cell_parse(extended_cell_t *cell_out, const uint8_t command, const uint8_t *payload_in, size_t payload_len); int create_cell_format(cell_t *cell_out, const create_cell_t *cell_in); diff --git a/src/or/or.h b/src/or/or.h index 4c76adf98..df933c353 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -2584,6 +2584,7 @@ struct ntor_handshake_state_t; #define ONION_HANDSHAKE_TYPE_TAP 0x0000 #define ONION_HANDSHAKE_TYPE_FAST 0x0001 #define ONION_HANDSHAKE_TYPE_NTOR 0x0002 +#define MAX_ONION_HANDSHAKE_TYPE 0x0002 typedef struct { uint16_t tag; union { @@ -2838,6 +2839,15 @@ typedef enum { PATH_STATE_BUILD_ATTEMPTED = 1, /** This circuit has been completely built */ PATH_STATE_BUILD_SUCCEEDED = 2, + /** Did we try to attach any SOCKS streams or hidserv introductions to + * this circuit? + * + * Note: If we ever implement end-to-end stream timing through test + * stream probes (#5707), we must *not* set this for those probes + * (or any other automatic streams) because the adversary could + * just tag at a later point. + */ + PATH_STATE_USE_ATTEMPTED = 3, /** Did any SOCKS streams or hidserv introductions actually succeed on * this circuit? * @@ -2846,13 +2856,20 @@ typedef enum { * (or any other automatic streams) because the adversary could * just tag at a later point. */ - PATH_STATE_USE_SUCCEEDED = 3, + PATH_STATE_USE_SUCCEEDED = 4, /** * This is a special state to indicate that we got a corrupted * relay cell on a circuit and we don't intend to probe it. */ - PATH_STATE_USE_FAILED = 4, + PATH_STATE_USE_FAILED = 5, + + /** + * This is a special state to indicate that we already counted + * the circuit. Used to guard against potential state machine + * violations. + */ + PATH_STATE_ALREADY_COUNTED = 6, } path_state_t; /** An origin_circuit_t holds data necessary to build and use a circuit. @@ -2997,9 +3014,10 @@ typedef struct origin_circuit_t { * ISO_STREAM. */ uint64_t associated_isolated_stream_global_id; /**@}*/ - } origin_circuit_t; +struct onion_queue_t; + /** An or_circuit_t holds information needed to implement a circuit at an * OR. */ typedef struct or_circuit_t { @@ -3013,6 +3031,9 @@ typedef struct or_circuit_t { * cells to p_chan. NULL if we have no cells pending, or if we're not * linked to an OR connection. */ struct circuit_t *prev_active_on_p_chan; + /** Pointer to an entry on the onion queue, if this circuit is waiting for a + * chance to give an onionskin to a cpuworker. Used only in onion.c */ + struct onion_queue_t *onionqueue_entry; /** The circuit_id used in the previous (backward) hop of this circuit. */ circid_t p_circ_id; @@ -3496,9 +3517,7 @@ typedef struct { * and try a new circuit if the stream has been * waiting for this many seconds. If zero, use * our default internal timeout schedule. */ - int MaxOnionsPending; /**< How many circuit CREATE requests do we allow - * to wait simultaneously before we start dropping - * them? */ + int MaxOnionQueueDelay; /**<DOCDOC*/ int NewCircuitPeriod; /**< How long do we use a circuit before building * a new one? */ int MaxCircuitDirtiness; /**< Never use circs that were first used more than @@ -3909,7 +3928,16 @@ typedef struct { int PathBiasScaleThreshold; int PathBiasScaleFactor; int PathBiasMultFactor; - int PathBiasUseCloseCounts; + /** @} */ + + /** + * Parameters for path-bias use detection + * @{ + */ + int PathBiasUseThreshold; + double PathBiasNoticeUseRate; + double PathBiasExtremeUseRate; + int PathBiasScaleUseThreshold; /** @} */ int IPv6Exit; /**< Do we support exiting to IPv6 addresses? */ diff --git a/src/or/relay.c b/src/or/relay.c index bb3a83544..f711eae92 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -730,7 +730,7 @@ connection_ap_process_end_not_open( * We rely on recognized+digest being strong enough to make * tags unlikely to allow us to get tagged, yet 'recognized' * reason codes here. */ - circ->path_state = PATH_STATE_USE_SUCCEEDED; + pathbias_mark_use_success(circ); } } diff --git a/src/or/rendclient.c b/src/or/rendclient.c index 32623c3f4..61e3b917e 100644 --- a/src/or/rendclient.c +++ b/src/or/rendclient.c @@ -71,6 +71,9 @@ rend_client_send_establish_rendezvous(origin_circuit_t *circ) * and the rend cookie also means we've used the circ. */ circ->base_.timestamp_dirty = time(NULL); + /* We've attempted to use this circuit. Probe it if we fail */ + pathbias_count_use_attempt(circ); + if (relay_send_command_from_edge(0, TO_CIRCUIT(circ), RELAY_COMMAND_ESTABLISH_RENDEZVOUS, circ->rend_data->rend_cookie, @@ -316,6 +319,8 @@ rend_client_send_introduction(origin_circuit_t *introcirc, * state. */ introcirc->base_.timestamp_dirty = time(NULL); + pathbias_count_use_attempt(introcirc); + goto cleanup; perm_err: @@ -395,7 +400,7 @@ rend_client_introduction_acked(origin_circuit_t *circ, /* For path bias: This circuit was used successfully. Valid * nacks and acks count. */ - circ->path_state = PATH_STATE_USE_SUCCEEDED; + pathbias_mark_use_success(circ); if (request_len == 0) { /* It's an ACK; the introduction point relayed our introduction request. */ @@ -902,7 +907,7 @@ rend_client_rendezvous_acked(origin_circuit_t *circ, const uint8_t *request, * Waiting any longer opens us up to attacks from Bob. He could induce * Alice to attempt to connect to his hidden service and never reply * to her rend requests */ - circ->path_state = PATH_STATE_USE_SUCCEEDED; + pathbias_mark_use_success(circ); /* XXXX This is a pretty brute-force approach. It'd be better to * attach only the connections that are waiting on this circuit, rather diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c index addbd42b9..79c1a724e 100644 --- a/src/or/rendcommon.c +++ b/src/or/rendcommon.c @@ -954,7 +954,7 @@ rend_cache_lookup_entry(const char *query, int version, rend_cache_entry_t **e) return 1; } -/** <b>query</b> is a base-32'ed service id. If it's malformed, return -1. +/** <b>query</b> is a base32'ed service id. If it's malformed, return -1. * Else look it up. * - If it is found, point *desc to it, and write its length into * *desc_len, and return 1. diff --git a/src/or/rendservice.c b/src/or/rendservice.c index 6ffa4f8f9..f115d8bfc 100644 --- a/src/or/rendservice.c +++ b/src/or/rendservice.c @@ -1384,9 +1384,6 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request, goto err; memcpy(cpath->rend_circ_nonce, keys, DIGEST_LEN); - /* For path bias: This intro circuit was used successfully */ - circuit->path_state = PATH_STATE_USE_SUCCEEDED; - goto done; log_error: @@ -2511,6 +2508,9 @@ rend_service_intro_has_opened(origin_circuit_t *circuit) goto err; } + /* We've attempted to use this circuit */ + pathbias_count_use_attempt(circuit); + goto done; err: @@ -2558,6 +2558,10 @@ rend_service_intro_established(origin_circuit_t *circuit, "Received INTRO_ESTABLISHED cell on circuit %d for service %s", circuit->base_.n_circ_id, serviceid); + /* Getting a valid INTRODUCE_ESTABLISHED means we've successfully + * used the circ */ + pathbias_mark_use_success(circuit); + return 0; err: circuit_mark_for_close(TO_CIRCUIT(circuit), END_CIRC_REASON_TORPROTOCOL); @@ -2589,6 +2593,9 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit) if (!circuit->base_.timestamp_dirty) circuit->base_.timestamp_dirty = time(NULL); + /* This may be redundant */ + pathbias_count_use_attempt(circuit); + hop = circuit->build_state->service_pending_final_cpath_ref->cpath; base16_encode(hexcookie,9,circuit->rend_data->rend_cookie,4); @@ -3061,7 +3068,8 @@ rend_services_introduce(void) if (intro->time_expiring + INTRO_POINT_EXPIRATION_GRACE_PERIOD > now) { /* This intro point has completely expired. Remove it, and * mark the circuit for close if it's still alive. */ - if (intro_circ != NULL) { + if (intro_circ != NULL && + intro_circ->base_.purpose != CIRCUIT_PURPOSE_PATH_BIAS_TESTING) { circuit_mark_for_close(TO_CIRCUIT(intro_circ), END_CIRC_REASON_FINISHED); } diff --git a/src/test/test.c b/src/test/test.c index e3e989b0c..b838172d5 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -1529,59 +1529,35 @@ test_geoip(void) *dirreq_stats_1 = "dirreq-stats-end 2010-08-12 13:27:30 (86400 s)\n" "dirreq-v3-ips ab=8\n" - "dirreq-v2-ips \n" "dirreq-v3-reqs ab=8\n" - "dirreq-v2-reqs \n" "dirreq-v3-resp ok=0,not-enough-sigs=0,unavailable=0,not-found=0," "not-modified=0,busy=0\n" - "dirreq-v2-resp ok=0,unavailable=0,not-found=0,not-modified=0," - "busy=0\n" "dirreq-v3-direct-dl complete=0,timeout=0,running=0\n" - "dirreq-v2-direct-dl complete=0,timeout=0,running=0\n" - "dirreq-v3-tunneled-dl complete=0,timeout=0,running=0\n" - "dirreq-v2-tunneled-dl complete=0,timeout=0,running=0\n", + "dirreq-v3-tunneled-dl complete=0,timeout=0,running=0\n", *dirreq_stats_2 = "dirreq-stats-end 2010-08-12 13:27:30 (86400 s)\n" "dirreq-v3-ips \n" - "dirreq-v2-ips \n" "dirreq-v3-reqs \n" - "dirreq-v2-reqs \n" "dirreq-v3-resp ok=0,not-enough-sigs=0,unavailable=0,not-found=0," "not-modified=0,busy=0\n" - "dirreq-v2-resp ok=0,unavailable=0,not-found=0,not-modified=0," - "busy=0\n" "dirreq-v3-direct-dl complete=0,timeout=0,running=0\n" - "dirreq-v2-direct-dl complete=0,timeout=0,running=0\n" - "dirreq-v3-tunneled-dl complete=0,timeout=0,running=0\n" - "dirreq-v2-tunneled-dl complete=0,timeout=0,running=0\n", + "dirreq-v3-tunneled-dl complete=0,timeout=0,running=0\n", *dirreq_stats_3 = "dirreq-stats-end 2010-08-12 13:27:30 (86400 s)\n" "dirreq-v3-ips \n" - "dirreq-v2-ips \n" "dirreq-v3-reqs \n" - "dirreq-v2-reqs \n" "dirreq-v3-resp ok=8,not-enough-sigs=0,unavailable=0,not-found=0," "not-modified=0,busy=0\n" - "dirreq-v2-resp ok=0,unavailable=0,not-found=0,not-modified=0," - "busy=0\n" "dirreq-v3-direct-dl complete=0,timeout=0,running=0\n" - "dirreq-v2-direct-dl complete=0,timeout=0,running=0\n" - "dirreq-v3-tunneled-dl complete=0,timeout=0,running=0\n" - "dirreq-v2-tunneled-dl complete=0,timeout=0,running=0\n", + "dirreq-v3-tunneled-dl complete=0,timeout=0,running=0\n", *dirreq_stats_4 = "dirreq-stats-end 2010-08-12 13:27:30 (86400 s)\n" "dirreq-v3-ips \n" - "dirreq-v2-ips \n" "dirreq-v3-reqs \n" - "dirreq-v2-reqs \n" "dirreq-v3-resp ok=8,not-enough-sigs=0,unavailable=0,not-found=0," "not-modified=0,busy=0\n" - "dirreq-v2-resp ok=0,unavailable=0,not-found=0,not-modified=0," - "busy=0\n" "dirreq-v3-direct-dl complete=0,timeout=0,running=0\n" - "dirreq-v2-direct-dl complete=0,timeout=0,running=0\n" - "dirreq-v3-tunneled-dl complete=0,timeout=0,running=4\n" - "dirreq-v2-tunneled-dl complete=0,timeout=0,running=0\n", + "dirreq-v3-tunneled-dl complete=0,timeout=0,running=4\n", *entry_stats_1 = "entry-stats-end 2010-08-12 13:27:30 (86400 s)\n" "entry-ips ab=8\n", @@ -1754,14 +1730,13 @@ test_geoip(void) /* Note a successful network status response and make sure that it * appears in the history string. */ - geoip_note_ns_response(GEOIP_CLIENT_NETWORKSTATUS, GEOIP_SUCCESS); + geoip_note_ns_response(GEOIP_SUCCESS); s = geoip_format_dirreq_stats(now + 86400); test_streq(dirreq_stats_3, s); tor_free(s); /* Start a tunneled directory request. */ - geoip_start_dirreq((uint64_t) 1, 1024, GEOIP_CLIENT_NETWORKSTATUS, - DIRREQ_TUNNELED); + geoip_start_dirreq((uint64_t) 1, 1024, DIRREQ_TUNNELED); s = geoip_format_dirreq_stats(now + 86400); test_streq(dirreq_stats_4, s); diff --git a/src/win32/orconfig.h b/src/win32/orconfig.h index 485590f11..6e45a2928 100644 --- a/src/win32/orconfig.h +++ b/src/win32/orconfig.h @@ -250,3 +250,6 @@ #define SHARE_DATADIR "" #define HAVE_EVENT2_DNS_H #define HAVE_EVENT_BASE_LOOPEXIT +#define CURVE25519_ENABLED +#define USE_CURVE25519_DONNA + |