Merge remote branch 'origin/maint-0.2.2'

Conflicts:
	src/or/relay.c

4 files changed, 82 insertions, 7 deletions

diff --git a/src/common/compat.c b/src/common/compat.c
index b7f4f17cae..0ebad62de3 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 <b>uname</b>. */
 static char uname_result[256];
 /** True iff uname_result is set. */
diff --git a/src/common/compat.h b/src/common/compat.h
index 2471e6b830..38e0f99ba9 100644
--- a/src/common/compat.h
+++ b/src/common/compat.h
@@ -487,6 +487,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.  <b>startup</b> 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 1d7a5171b6..6529efb243 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -1472,10 +1472,11 @@ 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;
+  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
@@ -1490,26 +1491,61 @@ 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;
 
+  /* 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. */
+  {
+    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_streams = 0;
-  for (conn=first_conn; conn; conn=conn->next_stream) {
+  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 */
+    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_packaging_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) {
       connection_start_reading(TO_CONN(conn));
 
       if (connection_get_inbuf_len(TO_CONN(conn)) > 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;
@@ -1557,7 +1593,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;
   }