Rename connection_get_by_identity_digest to reflect that it is OR-only. Make it use a hashtable instead of a linear search.

svn:r5469

8 files changed, 129 insertions, 55 deletions

diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 183a8ef263..64818ca5e6 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -342,7 +342,7 @@ circuit_handle_first_hop(circuit_t *circ)
   /* imprint the circuit with its future n_conn->id */
   memcpy(circ->n_conn_id_digest, firsthop->extend_info->identity_digest,
          DIGEST_LEN);
-  n_conn = connection_get_by_identity_digest(
+  n_conn = connection_or_get_by_identity_digest(
          firsthop->extend_info->identity_digest);
   if (!n_conn || n_conn->state != OR_CONN_STATE_OPEN ||
       (n_conn->is_obsolete &&
@@ -637,7 +637,7 @@ circuit_extend(cell_t *cell, circuit_t *circ)
 
   onionskin = cell->payload+RELAY_HEADER_SIZE+4+2;
   id_digest = cell->payload+RELAY_HEADER_SIZE+4+2+ONIONSKIN_CHALLENGE_LEN;
-  n_conn = connection_get_by_identity_digest(id_digest);
+  n_conn = connection_or_get_by_identity_digest(id_digest);
 
   if (!n_conn || n_conn->state != OR_CONN_STATE_OPEN ||
     (n_conn->is_obsolete &&
diff --git a/src/or/connection.c b/src/or/connection.c
index 660678fe61..a9dcd4593e 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -237,6 +237,10 @@ _connection_free(connection_t *conn)
     tor_close_socket(conn->s);
   }
 
+  if (conn->type == CONN_TYPE_OR && !tor_digest_is_zero(conn->identity_digest)) {
+    connection_or_remove_from_identity_map(conn);
+  }
+
   memset(conn, 0xAA, sizeof(connection_t)); /* poison memory */
   tor_free(conn);
 }
@@ -1570,47 +1574,6 @@ connection_get_by_type_addr_port_purpose(int type, uint32_t addr, uint16_t port,
   return NULL;
 }
 
-/** Return the best connection of type OR with the
- * digest <b>digest</b> that we have, or NULL if we have none.
- *
- * 1) Don't return it if it's marked for close.
- * 2) If there are any open conns, ignore non-open conns.
- * 3) If there are any non-obsolete conns, ignore obsolete conns.
- * 4) Then if there are any non-empty conns, ignore empty conns.
- * 5) Of the remaining conns, prefer newer conns.
- */
-connection_t *
-connection_get_by_identity_digest(const char *digest)
-{
-  int i, n, newer;
-  connection_t *conn, *best=NULL;
-  connection_t **carray;
-
-  get_connection_array(&carray,&n);
-  for (i=0;i<n;i++) {
-    conn = carray[i];
-    if (conn->marked_for_close ||
-        conn->type != CONN_TYPE_OR ||
-        memcmp(conn->identity_digest, digest, DIGEST_LEN))
-      continue;
-    if (!best) {
-      best = conn; /* whatever it is, it's better than nothing. */
-      continue;
-    }
-    if (best->state == OR_CONN_STATE_OPEN &&
-        conn->state != OR_CONN_STATE_OPEN)
-      continue; /* avoid non-open conns if we can */
-    newer = best->timestamp_created < conn->timestamp_created;
-    if (conn->is_obsolete && (!best->is_obsolete || !newer))
-      continue; /* we have something, and it's better than this. */
-    if (best->n_circuits && !conn->n_circuits)
-      continue; /* prefer conns with circuits on them */
-    if (newer)
-      best = conn; /* lastly, prefer newer conns */
-  }
-  return best;
-}
-
 /** Return the connection with id <b>id</b> if it is not already
  * marked for close.
  */
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index 7b273f9bcc..b29a4ae738 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -22,6 +22,71 @@ static int connection_or_process_cells_from_inbuf(connection_t *conn);
 
 /**************************************************************/
 
+/** Map from identity digest of connected OR or desired OR to a connection_t
+ * with that identity digest.  If there is more than one such connection_t,
+ * they form a linked list, with next_with_same_id as the next pointer.*/
+static digestmap_t *orconn_identity_map = NULL;
+
+/** If conn is listed in orconn_identity_map, remove it, and clear
+ * conn->identity_digest. */
+void
+connection_or_remove_from_identity_map(connection_t *conn)
+{
+  connection_t *tmp;
+  tor_assert(conn);
+  tor_assert(conn->type == CONN_TYPE_OR);
+  if (!orconn_identity_map)
+    return;
+  tmp = digestmap_get(orconn_identity_map, conn->identity_digest);
+  if (!tmp)
+    return;
+  if (conn == tmp) {
+    if (conn->next_with_same_id)
+      digestmap_set(orconn_identity_map, conn->identity_digest,
+                    conn->next_with_same_id);
+    else
+      digestmap_remove(orconn_identity_map, conn->identity_digest);
+  } else {
+    while (tmp->next_with_same_id) {
+      if (tmp->next_with_same_id == conn) {
+        tmp->next_with_same_id = conn->next_with_same_id;
+        break;
+      }
+      tmp = tmp->next_with_same_id;
+    }
+  }
+  memset(conn->identity_digest, 0, DIGEST_LEN);
+  conn->next_with_same_id = NULL;
+}
+
+/** Change conn->identity_digest to digest, and add conn into
+ * orconn_digest_map. */
+static void
+connection_or_set_identity_digest(connection_t *conn, const char *digest)
+{
+  connection_t *tmp;
+  tor_assert(conn);
+  tor_assert(conn->type == CONN_TYPE_OR);
+  tor_assert(digest);
+
+  if (!orconn_identity_map)
+    orconn_identity_map = digestmap_new();
+  if (!memcmp(conn->identity_digest, digest, DIGEST_LEN))
+    return;
+  if (tor_digest_is_zero(conn->identity_digest))
+    connection_or_remove_from_identity_map(conn);
+
+  memcpy(conn->identity_digest, digest, DIGEST_LEN);
+  tmp = digestmap_set(orconn_identity_map, digest, conn);
+  conn->next_with_same_id = tmp;
+
+  /* Checking code; remove once I'm sure this works. XXXX*/
+  for (; tmp; tmp = tmp->next_with_same_id) {
+    tor_assert(!memcmp(tmp->identity_digest, digest, DIGEST_LEN));
+    tor_assert(tmp != conn);
+  }
+}
+
 /** Pack the cell_t host-order structure <b>src</b> into network-order
  * in the buffer <b>dest</b>. See tor-spec.txt for details about the
  * wire format.
@@ -227,7 +292,7 @@ connection_or_init_conn_from_router(connection_t *conn, routerinfo_t *router)
   conn->port = router->or_port;
   conn->receiver_bucket = conn->bandwidth = (int)options->BandwidthBurst;
   conn->identity_pkey = crypto_pk_dup_key(router->identity_pkey);
-  crypto_pk_get_digest(conn->identity_pkey, conn->identity_digest);
+  connection_or_set_identity_digest(conn, router->cache_info.identity_digest);
   conn->nickname = tor_strdup(router->nickname);
   tor_free(conn->address);
   conn->address = tor_strdup(router->address);
@@ -252,7 +317,7 @@ connection_or_init_conn_from_address(connection_t *conn,
   conn->port = port;
   /* This next part isn't really right, but it's good enough for now. */
   conn->receiver_bucket = conn->bandwidth = (int)options->BandwidthBurst;
-  memcpy(conn->identity_digest, id_digest, DIGEST_LEN);
+  connection_or_set_identity_digest(conn, id_digest);
   /* If we're an authoritative directory server, we may know a
    * nickname for this router. */
   n = dirserv_get_nickname_by_digest(id_digest);
@@ -268,6 +333,50 @@ connection_or_init_conn_from_address(connection_t *conn,
   conn->address = tor_dup_addr(addr);
 }
 
+/** Return the best connection of type OR with the
+ * digest <b>digest</b> that we have, or NULL if we have none.
+ *
+ * 1) Don't return it if it's marked for close.
+ * 2) If there are any open conns, ignore non-open conns.
+ * 3) If there are any non-obsolete conns, ignore obsolete conns.
+ * 4) Then if there are any non-empty conns, ignore empty conns.
+ * 5) Of the remaining conns, prefer newer conns.
+ */
+connection_t *
+connection_or_get_by_identity_digest(const char *digest)
+{
+  int newer;
+  connection_t *conn, *best=NULL;
+
+  if (!orconn_identity_map)
+    return NULL;
+
+  conn = digestmap_get(orconn_identity_map, digest);
+
+  for (; conn; conn = conn->next_with_same_id) {
+    tor_assert(conn->magic == CONNECTION_MAGIC);
+    tor_assert(conn->type == CONN_TYPE_OR);
+    tor_assert(!memcmp(conn->identity_digest, digest, DIGEST_LEN));
+    if (conn->marked_for_close)
+      continue;
+    if (!best) {
+      best = conn; /* whatever it is, it's better than nothing. */
+      continue;
+    }
+    if (best->state == OR_CONN_STATE_OPEN &&
+        conn->state != OR_CONN_STATE_OPEN)
+      continue; /* avoid non-open conns if we can */
+    newer = best->timestamp_created < conn->timestamp_created;
+    if (conn->is_obsolete && (!best->is_obsolete || !newer))
+      continue; /* we have something, and it's better than this. */
+    if (best->n_circuits && !conn->n_circuits)
+      continue; /* prefer conns with circuits on them */
+    if (newer)
+      best = conn; /* lastly, prefer newer conns */
+  }
+  return best;
+}
+
 /** "update an OR connection nickname on the fly"
  * Actually, nobody calls this. Should we remove it? */
 void
@@ -419,8 +528,6 @@ connection_tls_continue_handshake(connection_t *conn)
   return 0;
 }
 
-static char ZERO_DIGEST[] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
-
 /** Return 1 if we initiated this connection, or 0 if it started
  * out as an incoming connection.
  *
@@ -431,10 +538,9 @@ static char ZERO_DIGEST[] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };
 int
 connection_or_nonopen_was_started_here(connection_t *conn)
 {
-  tor_assert(sizeof(ZERO_DIGEST) == DIGEST_LEN);
   tor_assert(conn->type == CONN_TYPE_OR);
 
-  if (!memcmp(ZERO_DIGEST, conn->identity_digest, DIGEST_LEN))
+  if (tor_digest_is_zero(conn->identity_digest))
     return 0;
   else
     return 1;
@@ -560,7 +666,7 @@ connection_tls_finish_handshake(connection_t *conn)
   if (!connection_or_nonopen_was_started_here(conn)) {
 #if 0
     connection_t *c;
-    if ((c=connection_get_by_identity_digest(digest_rcvd))) {
+    if ((c=connection_or_get_by_identity_digest(digest_rcvd))) {
       debug(LD_OR,"Router '%s' is already connected on fd %d. Dropping fd %d.",
              c->nickname, c->s, conn->s);
       return -1;
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index 174141aeef..47e095af66 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -622,7 +622,7 @@ dirserv_thinks_router_is_reachable(routerinfo_t *router, time_t now)
   connection_t *conn;
   if (router_is_me(router) && !we_are_hibernating())
     return 1;
-  conn = connection_get_by_identity_digest(router->cache_info.identity_digest);
+  conn = connection_or_get_by_identity_digest(router->cache_info.identity_digest);
   if (conn && conn->state == OR_CONN_STATE_OPEN)
     return get_options()->AssumeReachable ||
            now < router->last_reachable + REACHABLE_TIMEOUT;
@@ -638,7 +638,7 @@ dirserv_thinks_router_is_blatantly_unreachable(routerinfo_t *router, time_t now)
   connection_t *conn;
   if (router->is_hibernating)
     return 0;
-  conn = connection_get_by_identity_digest(router->cache_info.identity_digest);
+  conn = connection_or_get_by_identity_digest(router->cache_info.identity_digest);
   if (conn && conn->state == OR_CONN_STATE_OPEN &&
       now >= router->last_reachable + 2*REACHABLE_TIMEOUT &&
       router->testing_since &&
diff --git a/src/or/or.h b/src/or/or.h
index cb0dbd8370..268b150157 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -665,6 +665,8 @@ struct connection_t {
                                 * we use? */
   int n_circuits; /**< How many circuits use this connection as p_conn or
                    * n_conn ? */
+  struct connection_t *next_with_same_id; /**< Next connection with same
+                                           * identity digest as this one. */
 
 /* Used only by DIR and AP connections: */
   char rend_query[REND_SERVICE_ID_LEN+1]; /**< What rendezvous service are we
@@ -1570,7 +1572,6 @@ void _connection_controller_force_write(connection_t *conn);
 void connection_write_to_buf(const char *string, size_t len, connection_t *conn);
 
 connection_t *connection_or_exact_get_by_addr_port(uint32_t addr, uint16_t port);
-connection_t *connection_get_by_identity_digest(const char *digest);
 connection_t *connection_get_by_global_id(uint32_t id);
 
 connection_t *connection_get_by_type(int type);
@@ -1660,6 +1661,9 @@ hostname_type_t parse_extended_hostname(char *address);
 
 /********************************* connection_or.c ***************************/
 
+void connection_or_remove_from_identity_map(connection_t *conn);
+connection_t *connection_or_get_by_identity_digest(const char *digest);
+
 int connection_or_reached_eof(connection_t *conn);
 int connection_or_process_inbuf(connection_t *conn);
 int connection_or_finished_flushing(connection_t *conn);
diff --git a/src/or/relay.c b/src/or/relay.c
index a8d0b087d4..ae1dafa44e 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -325,6 +325,7 @@ circuit_package_relay_cell(cell_t *cell, circuit_t *circ,
     if (!conn) {
       /* XXXX RD This is a bug, right? */
       warn(LD_BUG,"incoming relay cell has p_conn==NULL. Dropping.");
+      assert_circuit_ok(circ);
       return 0; /* just drop it */
     }
     relay_set_digest(circ->p_digest, cell);
diff --git a/src/or/router.c b/src/or/router.c
index ae1c602177..0fcf13737c 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -623,7 +623,7 @@ router_retry_connections(int force)
     if (!clique_mode(options) && !router_is_clique_mode(router))
       continue;
     if (force ||
-        !connection_get_by_identity_digest(router->cache_info.identity_digest)) {
+      !connection_or_get_by_identity_digest(router->cache_info.identity_digest)) {
       debug(LD_OR,"%sconnecting to %s at %s:%u.",
              clique_mode(options) ? "(forced) " : "",
              router->nickname, router->address, router->or_port);
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 0e5ec2aa91..70c28ee6a2 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -1538,7 +1538,7 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg,
          * make new ones with the new key.
          */
         connection_t *conn;
-        while ((conn = connection_get_by_identity_digest(
+        while ((conn = connection_or_get_by_identity_digest(
                       old_router->cache_info.identity_digest))) {
           // And LD_OR? XXXXNM
           info(LD_DIR,"Closing conn to router '%s'; there is now a named router with that name.",