Shave off another 4.7%: remove a linear search when figuring out which circuits wanted us to open a given OR connection.

svn:r5489

5 files changed, 67 insertions, 14 deletions

diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 64818ca5e..67bdfff8c 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -279,7 +279,7 @@ circuit_t *
 circuit_init(uint8_t purpose, int need_uptime, int need_capacity, int internal)
 {
   circuit_t *circ = circuit_new(0, NULL); /* sets circ->p_circ_id and circ->p_conn */
-  circ->state = CIRCUIT_STATE_OR_WAIT;
+  circuit_set_state(circ, CIRCUIT_STATE_OR_WAIT);
   circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
   circ->build_state->need_uptime = need_uptime;
   circ->build_state->need_capacity = need_capacity;
@@ -388,16 +388,20 @@ circuit_handle_first_hop(circuit_t *circ)
 void
 circuit_n_conn_done(connection_t *or_conn, int status)
 {
-  circuit_t *circ;
+  extern smartlist_t *circuits_pending_or_conns;
 
   debug(LD_CIRC,"or_conn to %s, status=%d",
          or_conn->nickname ? or_conn->nickname : "NULL", status);
 
-  for (circ=global_circuitlist;circ;circ = circ->next) {
+  if (!circuits_pending_or_conns)
+    return;
+
+  SMARTLIST_FOREACH(circuits_pending_or_conns, circuit_t *, circ,
+  {
     if (circ->marked_for_close)
       continue;
-    if (circ->state == CIRCUIT_STATE_OR_WAIT &&
-        !circ->n_conn &&
+    tor_assert(circ->state == CIRCUIT_STATE_OR_WAIT);
+    if (!circ->n_conn &&
         circ->n_addr == or_conn->addr &&
         circ->n_port == or_conn->port &&
         !memcmp(or_conn->identity_digest, circ->n_conn_id_digest, DIGEST_LEN)) {
@@ -407,6 +411,8 @@ circuit_n_conn_done(connection_t *or_conn, int status)
         continue;
       }
       debug(LD_CIRC,"Found circ %d, sending create cell.", circ->n_circ_id);
+      /* circuit_deliver_create_cell will set n_circ_id and add us to the
+       * index. */
       circ->n_conn = or_conn;
       memcpy(circ->n_conn_id_digest, or_conn->identity_digest, DIGEST_LEN);
       if (CIRCUIT_IS_ORIGIN(circ)) {
@@ -424,10 +430,10 @@ circuit_n_conn_done(connection_t *or_conn, int status)
           continue;
         }
         tor_free(circ->onionskin);
-        circ->state = CIRCUIT_STATE_OPEN;
+        circuit_set_state(circ, CIRCUIT_STATE_OPEN);
       }
     }
-  }
+  });
 }
 
 /** Find a new circid that isn't currently in use by the outgoing
@@ -543,7 +549,7 @@ circuit_send_next_onion_skin(circuit_t *circ)
       return -1;
 
     circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
-    circ->state = CIRCUIT_STATE_BUILDING;
+    circuit_set_state(circ, CIRCUIT_STATE_BUILDING);
     debug(LD_CIRC,"first skin; finished sending create cell.");
   } else {
     tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
@@ -552,7 +558,7 @@ circuit_send_next_onion_skin(circuit_t *circ)
     hop = onion_next_hop_in_cpath(circ->cpath);
     if (!hop) {
       /* done building the circuit. whew. */
-      circ->state = CIRCUIT_STATE_OPEN;
+      circuit_set_state(circ, CIRCUIT_STATE_OPEN);
       info(LD_CIRC,"circuit built!");
       circuit_reset_failure_count(0);
       if (!has_completed_circuit) {
@@ -654,7 +660,7 @@ circuit_extend(cell_t *cell, circuit_t *circ)
 
     circ->onionskin = tor_malloc(ONIONSKIN_CHALLENGE_LEN);
     memcpy(circ->onionskin, onionskin, ONIONSKIN_CHALLENGE_LEN);
-    circ->state = CIRCUIT_STATE_OR_WAIT;
+    circuit_set_state(circ, CIRCUIT_STATE_OR_WAIT);
 
     /* imprint the circuit with its future n_conn->id */
     memcpy(circ->n_conn_id_digest, id_digest, DIGEST_LEN);
@@ -874,7 +880,7 @@ onionskin_answer(circuit_t *circ, uint8_t cell_type, char *payload, char *keys)
   cell.command = cell_type;
   cell.circ_id = circ->p_circ_id;
 
-  circ->state = CIRCUIT_STATE_OPEN;
+  circuit_set_state(circ, CIRCUIT_STATE_OPEN);
 
   memcpy(cell.payload, payload,
          cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2);
@@ -1325,7 +1331,7 @@ int
 circuit_extend_to_new_exit(circuit_t *circ, extend_info_t *info)
 {
   circuit_append_new_exit(circ, info);
-  circ->state = CIRCUIT_STATE_BUILDING;
+  circuit_set_state(circ, CIRCUIT_STATE_BUILDING);
   if (circuit_send_next_onion_skin(circ)<0) {
     warn(LD_CIRC, "Couldn't extend circuit to new point '%s'.",
            info->nickname);
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 78cda5334..908ecc35e 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -19,6 +19,9 @@ const char circuitlist_c_id[] = "$Id$";
 /** A global list of all circuits at this hop. */
 circuit_t *global_circuitlist=NULL;
 
+/** A list of all the circuits in CIRCUIT_STATE_OR_WAIT. */
+smartlist_t *circuits_pending_or_conns=NULL;
+
 static void circuit_free(circuit_t *circ);
 static void circuit_free_cpath(crypt_path_t *cpath);
 static void circuit_free_cpath_node(crypt_path_t *victim);
@@ -131,6 +134,36 @@ circuit_set_circid_orconn(circuit_t *circ, uint16_t id,
   ++conn->n_circuits;
 }
 
+/** Add <b>circ</b> to the list of circuits waiting for us to connect to
+ * an OR. */
+void
+circuit_set_state(circuit_t *circ, int state)
+{
+  tor_assert(circ);
+  if (state == circ->state)
+    return;
+  if (circ->state == CIRCUIT_STATE_OR_WAIT) {
+    /* remove from waiting-circuit list. */
+    if (!circuits_pending_or_conns)
+      circuits_pending_or_conns = smartlist_create();
+    smartlist_remove(circuits_pending_or_conns, circ);
+  }
+  if (state == CIRCUIT_STATE_OR_WAIT) {
+    /* add to waiting-circuit list. */
+    if (!circuits_pending_or_conns)
+      circuits_pending_or_conns = smartlist_create();
+    smartlist_add(circuits_pending_or_conns, circ);
+  }
+  circ->state = state;
+}
+
+/** Remove <b>circ</b> from the list of circuits waiting for us to connect to
+ * an OR. */
+void
+circuit_clear_state_orwait(circuit_t *circ)
+{
+}
+
 /** Add <b>circ</b> to the global list of circuits. This is called only from
  * within circuit_new.
  */
@@ -302,6 +335,8 @@ circuit_free_all(void)
     circuit_free(global_circuitlist);
     global_circuitlist = next;
   }
+  smartlist_free(circuits_pending_or_conns);
+  circuits_pending_or_conns = NULL;
 }
 
 /** Deallocate space associated with the cpath node <b>victim</b>. */
@@ -638,6 +673,10 @@ _circuit_mark_for_close(circuit_t *circ, int line, const char *file)
     }
     circuit_rep_hist_note_result(circ);
   }
+  if (circ->state == CIRCUIT_STATE_OR_WAIT) {
+    if (circuits_pending_or_conns)
+      smartlist_remove(circuits_pending_or_conns, circ);
+  }
   if (CIRCUIT_IS_ORIGIN(circ)) {
     control_event_circuit_status(circ,
      (circ->state == CIRCUIT_STATE_OPEN)?CIRC_EVENT_CLOSED:CIRC_EVENT_FAILED);
@@ -784,6 +823,13 @@ assert_circuit_ok(const circuit_t *c)
       tor_assert(c->p_digest);
     }
   }
+  if (c->state == CIRCUIT_STATE_OR_WAIT && !c->marked_for_close) {
+    tor_assert(circuits_pending_or_conns &&
+               smartlist_isin(circuits_pending_or_conns, c));
+  } else {
+    tor_assert(!circuits_pending_or_conns || !
+               !smartlist_isin(circuits_pending_or_conns, c));
+  }
   if (c->cpath) {
     assert_cpath_ok(c->cpath);
   }
diff --git a/src/or/command.c b/src/or/command.c
index d2fe460bd..73c3137cb 100644
--- a/src/or/command.c
+++ b/src/or/command.c
@@ -198,7 +198,7 @@ command_process_create_cell(cell_t *cell, connection_t *conn)
 
   circ = circuit_new(cell->circ_id, conn);
   circ->purpose = CIRCUIT_PURPOSE_OR;
-  circ->state = CIRCUIT_STATE_ONIONSKIN_PENDING;
+  circuit_set_state(circ, CIRCUIT_STATE_ONIONSKIN_PENDING);
   if (cell->command == CELL_CREATE) {
     circ->onionskin = tor_malloc(ONIONSKIN_CHALLENGE_LEN);
     memcpy(circ->onionskin, cell->payload, ONIONSKIN_CHALLENGE_LEN);
diff --git a/src/or/control.c b/src/or/control.c
index 88451cda3..94a4ca14b 100644
--- a/src/or/control.c
+++ b/src/or/control.c
@@ -1594,7 +1594,7 @@ handle_control_extendcircuit(connection_t *conn, uint32_t len,
     }
   } else {
     if (circ->state == CIRCUIT_STATE_OPEN) {
-      circ->state = CIRCUIT_STATE_BUILDING;
+      circuit_set_state(circ, CIRCUIT_STATE_BUILDING);
       if (circuit_send_next_onion_skin(circ) < 0) {
         info(LD_CONTROL,"send_next_onion_skin failed; circuit marked for closing.");
         circuit_mark_for_close(circ);
diff --git a/src/or/or.h b/src/or/or.h
index 1a9312ece..9812ba237 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1440,6 +1440,7 @@ enum which_conn_changed_t { P_CONN_CHANGED=1, N_CONN_CHANGED=0 };
 void circuit_set_circid_orconn(circuit_t *circ, uint16_t id,
                                connection_t *conn,
                                enum which_conn_changed_t which);
+void circuit_set_state(circuit_t *circ, int state);
 void circuit_close_all_marked(void);
 circuit_t *circuit_new(uint16_t p_circ_id, connection_t *p_conn);
 circuit_t *circuit_get_by_circid_orconn(uint16_t circ_id, connection_t *conn);