From 12fa6e23cb4a45c51ae2ca9bddaabfc5da4ebb6e Mon Sep 17 00:00:00 2001 From: Mashael AlSabah Date: Mon, 29 Nov 2010 15:34:21 -0500 Subject: Improve fairness when activating streams in circuit_resume_edge_reading_helper The reason the "streams problem" occurs is due to the complicated interaction between Tor's congestion control and libevent. At some point during the experiment, the circuit window is exhausted, which blocks all edge streams. When a circuit level sendme is received at Exit, it resumes edge reading by looping over linked list of edge streams, and calling connection_start_reading() to inform libevent to resume reading. When the streams are activated again, Tor gets the chance to service the first three streams activated before the circuit window is exhausted again, which causes all streams to be blocked again. As an experiment, we reversed the order in which the streams are activated, and indeed the first three streams, rather than the last three, got service, while the others starved. Our solution is to change the order in which streams are activated. We choose a random edge connection from the linked list, and then we activate streams starting from that chosen stream. When we reach the end of the list, then we continue from the head of the list until our chosen stream (treating the linked list as a circular linked list). It would probably be better to actually remember which streams have received service recently, but this way is simple and effective. --- src/or/relay.c | 35 ++++++++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-) (limited to 'src/or') diff --git a/src/or/relay.c b/src/or/relay.c index 467f8847c8..7b618baa8b 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -1482,6 +1482,8 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, int packaged_this_round; int cells_on_queue; int cells_per_conn; + int num_streams = 0; + edge_connection_t *chosen_stream = NULL; /* How many cells do we have space for? It will be the minimum of * the number needed to exhaust the package window, and the minimum @@ -1499,7 +1501,38 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, /* Count how many non-marked streams there are that have anything on * their inbuf, and enable reading on all of the connections. */ n_streams = 0; - for (conn=first_conn; conn; conn=conn->next_stream) { + /* This used to start listening on the streams in the order they + * appeared in the linked list. That leads to starvation in the + * event that, for example, our circuit window is almost full, and + * there are lots of streams. Then the first few streams will have + * data read from them, and then the window will close again. When + * it reopens, we would enable reading from the beginning of the list + * again. Instead, we just pick a random stream on the list, and + * enable reading for streams starting at that point (and wrapping + * around as if the list were circular). It would probably be better + * to actually remember which streams we've serviced in the past, but + * this is simple and effective. */ + + /* Select a stream uniformly at random from the linked list. We + * don't need cryptographic randomness here. */ + for(conn = first_conn; conn; conn = conn->next_stream) { + num_streams++; + if((random() % num_streams)==0) chosen_stream = conn; + } + /* Activate reading starting from the chosen stream */ + for (conn=chosen_stream; conn; conn = conn->next_stream) { + /* Start reading for the streams starting from here */ + if (conn->_base.marked_for_close || conn->package_window <= 0) + continue; + if (!layer_hint || conn->cpath_layer == layer_hint) { + connection_start_reading(TO_CONN(conn)); + + if (connection_get_inbuf_len(TO_CONN(conn)) > 0) + ++n_streams; + } + } + /* Go back and do the ones we skipped, circular-style */ + for(conn = first_conn; conn != chosen_stream; conn = conn->next_stream) { if (conn->_base.marked_for_close || conn->package_window <= 0) continue; if (!layer_hint || conn->cpath_layer == layer_hint) { -- cgit v1.2.3-54-g00ecf From 0eafe23ff38dd895c15b2deba70e5df997cf97e9 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Mon, 29 Nov 2010 15:53:12 -0500 Subject: Fix whitespace in patch for 2210 and backport to 0.2.2 --- src/or/relay.c | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-) (limited to 'src/or') diff --git a/src/or/relay.c b/src/or/relay.c index 7b618baa8b..8a4edb933f 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -1515,9 +1515,12 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, /* Select a stream uniformly at random from the linked list. We * don't need cryptographic randomness here. */ - for(conn = first_conn; conn; conn = conn->next_stream) { + for (conn = first_conn; conn; conn = conn->next_stream) { num_streams++; - if((random() % num_streams)==0) chosen_stream = conn; + if ((random() % num_streams)==0) + chosen_stream = conn; + /* Invariant: chosen_stream has been chosen uniformly at random from among + * the first num_streams streams on first_conn. */ } /* Activate reading starting from the chosen stream */ for (conn=chosen_stream; conn; conn = conn->next_stream) { @@ -1525,14 +1528,14 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, if (conn->_base.marked_for_close || conn->package_window <= 0) continue; if (!layer_hint || conn->cpath_layer == layer_hint) { - connection_start_reading(TO_CONN(conn)); + connection_start_reading(TO_CONN(conn)); - if (connection_get_inbuf_len(TO_CONN(conn)) > 0) + if (buf_datalen(conn->_base.inbuf) > 0) ++n_streams; } } /* Go back and do the ones we skipped, circular-style */ - for(conn = first_conn; conn != chosen_stream; conn = conn->next_stream) { + for (conn = first_conn; conn != chosen_stream; conn = conn->next_stream) { if (conn->_base.marked_for_close || conn->package_window <= 0) continue; if (!layer_hint || conn->cpath_layer == layer_hint) { -- cgit v1.2.3-54-g00ecf From 89e97bdf940d6c063fc9860306395c500d1c7027 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Mon, 29 Nov 2010 15:53:33 -0500 Subject: Add wrappers function for libc random() On windows, it's called something different. --- src/common/compat.c | 24 ++++++++++++++++++++++++ src/common/compat.h | 5 +++++ src/common/crypto.c | 10 ++++++++++ src/or/relay.c | 2 +- 4 files changed, 40 insertions(+), 1 deletion(-) (limited to 'src/or') diff --git a/src/common/compat.c b/src/common/compat.c index 20394b4c5d..4d556a85e6 100644 --- a/src/common/compat.c +++ b/src/common/compat.c @@ -1679,6 +1679,30 @@ tor_lookup_hostname(const char *name, uint32_t *addr) return -1; } +/** Initialize the insecure libc RNG. */ +void +tor_init_weak_random(unsigned seed) +{ +#ifdef MS_WINDOWS + srand(seed); +#else + srandom(seed); +#endif +} + +/** Return a randomly chosen value in the range 0..TOR_RAND_MAX. This + * entropy will not be cryptographically strong; do not rely on it + * for anything an adversary should not be able to predict. */ +long +tor_weak_random(void) +{ +#ifdef MS_WINDOWS + return rand(); +#else + return random(); +#endif +} + /** Hold the result of our call to uname. */ static char uname_result[256]; /** True iff uname_result is set. */ diff --git a/src/common/compat.h b/src/common/compat.h index 7d59501e2b..449bf748f4 100644 --- a/src/common/compat.h +++ b/src/common/compat.h @@ -480,6 +480,11 @@ typedef enum { SOCKS5_ADDRESS_TYPE_NOT_SUPPORTED = 0x08, } socks5_reply_status_t; +/* ===== Insecure rng */ +void tor_init_weak_random(unsigned seed); +long tor_weak_random(void); +#define TOR_RAND_MAX (RAND_MAX) + /* ===== OS compatibility */ const char *get_uname(void); diff --git a/src/common/crypto.c b/src/common/crypto.c index b49547fa4d..81a432d8d4 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -1935,6 +1935,14 @@ crypto_dh_free(crypto_dh_env_t *dh) OPENSSL_VERSION_NUMBER <= 0x00907fffl) || \ (OPENSSL_VERSION_NUMBER >= 0x0090803fl)) +static void +seed_weak_rng(void) +{ + unsigned seed; + crypto_rand((void*)&seed, sizeof(seed)); + tor_init_weak_random(seed); +} + /** Seed OpenSSL's random number generator with bytes from the operating * system. startup should be true iff we have just started Tor and * have not yet allocated a bunch of fds. Return 0 on success, -1 on failure. @@ -1985,6 +1993,7 @@ crypto_seed_rng(int startup) } RAND_seed(buf, sizeof(buf)); memset(buf, 0, sizeof(buf)); + seed_weak_rng(); return 0; #else for (i = 0; filenames[i]; ++i) { @@ -2001,6 +2010,7 @@ crypto_seed_rng(int startup) } RAND_seed(buf, (int)sizeof(buf)); memset(buf, 0, sizeof(buf)); + seed_weak_rng(); return 0; } diff --git a/src/or/relay.c b/src/or/relay.c index 8a4edb933f..c64afe2dba 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -1517,7 +1517,7 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, * don't need cryptographic randomness here. */ for (conn = first_conn; conn; conn = conn->next_stream) { num_streams++; - if ((random() % num_streams)==0) + if ((tor_weak_random() % num_streams)==0) chosen_stream = conn; /* Invariant: chosen_stream has been chosen uniformly at random from among * the first num_streams streams on first_conn. */ -- cgit v1.2.3-54-g00ecf From 25b0fd88689becd5c10d871d10099f01411a5571 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Mon, 29 Nov 2010 15:59:59 -0500 Subject: Revise comment on 2210 a little; clean up n_streams/num_streams confusion Also add a changes file --- changes/bug2210 | 5 +++++ src/or/relay.c | 54 +++++++++++++++++++++++++++--------------------------- 2 files changed, 32 insertions(+), 27 deletions(-) create mode 100644 changes/bug2210 (limited to 'src/or') diff --git a/changes/bug2210 b/changes/bug2210 new file mode 100644 index 0000000000..739a8a9c60 --- /dev/null +++ b/changes/bug2210 @@ -0,0 +1,5 @@ + o ?? bugfixes: + - Fix a bug that would cause older streams on a given circuit to + get preference when reading bytes from the network. Fixes bug + 2210. Fix by Mashael AlSabah. This bug was introduced before + the first Tor release, in svn revision r152. diff --git a/src/or/relay.c b/src/or/relay.c index c64afe2dba..a65280e2a3 100644 --- a/src/or/relay.c +++ b/src/or/relay.c @@ -1478,11 +1478,10 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, crypt_path_t *layer_hint) { edge_connection_t *conn; - int n_streams, n_streams_left; + int n_packaging_streams, n_streams_left; int packaged_this_round; int cells_on_queue; int cells_per_conn; - int num_streams = 0; edge_connection_t *chosen_stream = NULL; /* How many cells do we have space for? It will be the minimum of @@ -1498,30 +1497,31 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, if (CELL_QUEUE_HIGHWATER_SIZE - cells_on_queue < max_to_package) max_to_package = CELL_QUEUE_HIGHWATER_SIZE - cells_on_queue; - /* Count how many non-marked streams there are that have anything on - * their inbuf, and enable reading on all of the connections. */ - n_streams = 0; - /* This used to start listening on the streams in the order they - * appeared in the linked list. That leads to starvation in the - * event that, for example, our circuit window is almost full, and - * there are lots of streams. Then the first few streams will have - * data read from them, and then the window will close again. When - * it reopens, we would enable reading from the beginning of the list - * again. Instead, we just pick a random stream on the list, and - * enable reading for streams starting at that point (and wrapping - * around as if the list were circular). It would probably be better - * to actually remember which streams we've serviced in the past, but - * this is simple and effective. */ + /* Once we used to start listening on the streams in the order they + * appeared in the linked list. That leads to starvation on the + * streams that appeared later on the list, since the first streams + * would always get to read first. Instead, we just pick a random + * stream on the list, and enable reading for streams starting at that + * point (and wrapping around as if the list were circular). It would + * probably be better to actually remember which streams we've + * serviced in the past, but this is simple and effective. */ /* Select a stream uniformly at random from the linked list. We * don't need cryptographic randomness here. */ - for (conn = first_conn; conn; conn = conn->next_stream) { - num_streams++; - if ((tor_weak_random() % num_streams)==0) - chosen_stream = conn; - /* Invariant: chosen_stream has been chosen uniformly at random from among - * the first num_streams streams on first_conn. */ + { + int num_streams = 0; + for (conn = first_conn; conn; conn = conn->next_stream) { + num_streams++; + if ((tor_weak_random() % num_streams)==0) + chosen_stream = conn; + /* Invariant: chosen_stream has been chosen uniformly at random from + * among the first num_streams streams on first_conn. */ + } } + + /* Count how many non-marked streams there are that have anything on + * their inbuf, and enable reading on all of the connections. */ + n_packaging_streams = 0; /* Activate reading starting from the chosen stream */ for (conn=chosen_stream; conn; conn = conn->next_stream) { /* Start reading for the streams starting from here */ @@ -1531,7 +1531,7 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, connection_start_reading(TO_CONN(conn)); if (buf_datalen(conn->_base.inbuf) > 0) - ++n_streams; + ++n_packaging_streams; } } /* Go back and do the ones we skipped, circular-style */ @@ -1542,16 +1542,16 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, connection_start_reading(TO_CONN(conn)); if (buf_datalen(conn->_base.inbuf) > 0) - ++n_streams; + ++n_packaging_streams; } } - if (n_streams == 0) /* avoid divide-by-zero */ + if (n_packaging_streams == 0) /* avoid divide-by-zero */ return 0; again: - cells_per_conn = CEIL_DIV(max_to_package, n_streams); + cells_per_conn = CEIL_DIV(max_to_package, n_packaging_streams); packaged_this_round = 0; n_streams_left = 0; @@ -1599,7 +1599,7 @@ circuit_resume_edge_reading_helper(edge_connection_t *first_conn, if (packaged_this_round && packaged_this_round < max_to_package && n_streams_left) { max_to_package -= packaged_this_round; - n_streams = n_streams_left; + n_packaging_streams = n_streams_left; goto again; } -- cgit v1.2.3-54-g00ecf