[or-cvs] Finish implementing the rest of the exitpolicy stuff, excep...

[nickm@seul.org (Nick Mathewson)]

Update of /home/or/cvsroot/src/or
In directory moria.mit.edu:/tmp/cvs-serv2439/or

Modified Files:
	connection_edge.c onion.c or.h routers.c 
Log Message:
Finish implementing the rest of the exitpolicy stuff, except for automatically starting circuit builds.

Index: connection_edge.c
===================================================================
RCS file: /home/or/cvsroot/src/or/connection_edge.c,v
retrieving revision 1.54
retrieving revision 1.55
diff -u -d -r1.54 -r1.55
--- connection_edge.c	14 Nov 2003 20:45:47 -0000	1.54
+++ connection_edge.c	16 Nov 2003 05:33:45 -0000	1.55
@@ -255,8 +255,10 @@
          * forgotten it.
          */
         addr = ntohl(*cell->payload+RELAY_HEADER_SIZE+1);
-        client_dns_set_entry(conn->address, addr);
-        /* XXX Move state back into CIRCUIT_WAIT. */
+        client_dns_set_entry(conn->socks_request->addr, addr);
+        conn->state = AP_CONN_STATE_CIRCUIT_WAIT;
+        /* XXX Build another circuit as required */
+        return 0;
       }
       log_fn(LOG_INFO,"end cell (%s) for stream %d. Removing stream.",
         connection_edge_end_reason(cell->payload+RELAY_HEADER_SIZE, cell->length),
@@ -479,12 +481,19 @@
 /* Tell any APs that are waiting for a new circuit that one is available */
 void connection_ap_attach_pending(void)
 {
-  connection_t *conn;
+  connection_t **carray;
+  int n, i;
+  int need_new_circuit = 0;
 
-  while ((conn = connection_get_by_type_state(CONN_TYPE_AP,
-                                              AP_CONN_STATE_CIRCUIT_WAIT))) {
-    if (connection_ap_handshake_attach_circuit(conn) == 0)
-      break; /* There was no circuit to attach to: stop the loop. */
+  get_connection_array(&carray, &n);
+
+  for (i = 0; i < n; ++i) {
+    if (carray[i]->type != CONN_TYPE_AP || 
+        carray[i]->type != AP_CONN_STATE_CIRCUIT_WAIT)
+      continue;
+    if (connection_ap_handshake_attach_circuit(carray[i])) {
+      need_new_circuit = 1; /* XXX act on this. */
+    }
   }
 }
 
@@ -540,8 +549,9 @@
   } /* else socks handshake is done, continue processing */
 
   conn->state = AP_CONN_STATE_CIRCUIT_WAIT;
-  if (connection_ap_handshake_attach_circuit(conn)<0)
-    return -1;
+  if (connection_ap_handshake_attach_circuit(conn)) {
+    /* XXX we need a circuit */
+  }      
   return 0;
 }
 
@@ -569,8 +579,18 @@
      *     client until we're connected. the socks spec promises that it
      *     won't write. is that good enough?
      */
-    return 0;
+    return -1;
   }
+  if (connection_ap_can_use_exit(conn,
+                  router_get_by_addr_port(circ->cpath->prev->addr,
+                                          circ->cpath->prev->port)) < 0) {
+    /* The exit on this circuit will _definitely_ reject this connection. */
+    log_fn(LOG_INFO,"Most recent circuit will reject AP connection; delaying.");
+    /* XXX Build another circuit. */
+    connection_stop_reading(conn);
+    return -1;
+  }
+
   connection_start_reading(conn);
 
   circ->dirty = 1;
@@ -586,7 +606,7 @@
 
   connection_ap_handshake_send_begin(conn, circ);
 
-  return 1;
+  return 0;
 }
 
 /* deliver the destaddr:destport in a relay cell */
@@ -763,6 +783,14 @@
                                connected_payload, 4, conn->cpath_layer);
 }
 
+int connection_ap_can_use_exit(connection_t *conn, routerinfo_t *exit)
+{
+  uint32_t addr;
+  
+  addr = client_dns_lookup_entry(conn->socks_request->addr);
+  return router_supports_exit_address(addr, conn->port, exit);
+}
+
 /* ***** Client DNS code ***** */
 #define MAX_DNS_ENTRY_AGE 30*60
 
@@ -806,7 +834,7 @@
   assert(address);
 
   if (inet_aton(address, &in)) {
-    log_fn(LOG_DEBUG, "Using static address %s", address);
+    log_fn(LOG_DEBUG, "Using static address %s (%08X)", address, in.s_addr);
     return in.s_addr;
   }
   search.address = (char*)address;
@@ -867,6 +895,7 @@
     ++client_dns_size;
   }
 }
+
 static void client_dns_clean()
 {
   struct client_dns_entry **expired_entries;

Index: onion.c
===================================================================
RCS file: /home/or/cvsroot/src/or/onion.c,v
retrieving revision 1.83
retrieving revision 1.84
diff -u -d -r1.83 -r1.84
--- onion.c	14 Nov 2003 20:45:47 -0000	1.83
+++ onion.c	16 Nov 2003 05:33:45 -0000	1.84
@@ -8,6 +8,7 @@
 
 struct cpath_build_state_t {
   int desired_path_len;
+  char *chosen_exit; /* nicknames */
 };
 
 static int count_acceptable_routers(routerinfo_t **rarray, int rarray_len);
@@ -223,6 +224,95 @@
   return routelen;
 }
 
+static routerinfo_t *choose_good_exit_server(directory_t *dir)
+{
+  int *n_supported;
+  int *n_maybe_supported;
+  int i, j;
+  int n_pending_connections = 0;
+  connection_t **carray;
+  int n_connections;
+  int best_support = -1;
+  int best_maybe_support = -1;
+  int best_support_idx = -1;
+  int best_maybe_support_idx = -1;
+  int n_best_support=0, n_best_maybe_support=0;
+  
+  get_connection_array(&carray, &n_connections);
+
+  for (i = 0; i < n_connections; ++i) {
+    if (carray[i]->type == CONN_TYPE_AP && carray[i]->state == AP_CONN_STATE_CIRCUIT_WAIT)
+      ++n_pending_connections;
+  }
+  log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
+         n_pending_connections);
+  n_supported = tor_malloc(sizeof(int)*dir->n_routers);
+  n_maybe_supported = tor_malloc(sizeof(int)*dir->n_routers);
+  for (i = 0; i < dir->n_routers; ++i) {
+    n_supported[i] = n_maybe_supported[i] = 0;
+    for (j = 0; j < n_pending_connections; ++j) {
+      if (carray[i]->type != CONN_TYPE_AP || 
+          carray[i]->state == AP_CONN_STATE_CIRCUIT_WAIT ||
+          carray[i]->marked_for_close)
+        continue;
+      switch (connection_ap_can_use_exit(carray[j], dir->routers[i])) 
+        {
+        case -1:
+          break;
+        case 0:
+          ++n_supported[i];
+        case 1:
+          ++n_maybe_supported[i];
+        }
+    }
+    if (n_supported[i] > best_support) {
+      best_support = n_supported[i]; best_support_idx = i; n_best_support=1;
+    } else if (n_supported[i] == best_support) {
+      ++n_best_support;
+    }
+    if (n_maybe_supported[i] > best_maybe_support) {
+      best_maybe_support = n_maybe_supported[i]; best_maybe_support_idx = i;
+      n_best_maybe_support = 1;
+    } else if (n_maybe_supported[i] == best_maybe_support) {
+      ++n_best_maybe_support;
+    }
+  }
+  log_fn(LOG_WARN, "Found %d servers that will definitely support %d/%d pending connections, and %d that might support %d/%d.",
+         n_best_support, best_support, n_pending_connections,
+         n_best_maybe_support, best_maybe_support, n_pending_connections);
+  if (best_support) {
+    i = crypto_pseudo_rand_int(n_best_support);
+    for (j = best_support_idx; j < dir->n_routers; ++j) {
+      if (n_supported[j] == best_support) {
+        if (i) 
+          --i;
+        else {
+          tor_free(n_supported); tor_free(n_maybe_supported);
+          return dir->routers[i];
+        }
+      }
+    }
+  }
+  if (best_maybe_support) {
+    i = crypto_pseudo_rand_int(n_best_maybe_support);
+    for (j = best_maybe_support_idx; j < dir->n_routers; ++j) {
+      if (n_maybe_supported[j] == best_maybe_support) {
+        if (i) 
+          --i;
+        else {
+          tor_free(n_supported); tor_free(n_maybe_supported);
+          return dir->routers[i];
+        }
+      }
+    }
+  }
+  tor_free(n_supported);
+  tor_free(n_maybe_supported);
+  i = crypto_pseudo_rand_int(dir->n_routers);
+  log_fn(LOG_DEBUG, "Chose exit server '%s'", dir->routers[i]->nickname);
+  return dir->routers[i];
+}
+
 cpath_build_state_t *onion_new_cpath_build_state(void) {
   directory_t *dir;
   int r;
@@ -234,6 +324,8 @@
     return NULL;
   info = tor_malloc(sizeof(cpath_build_state_t));
   info->desired_path_len = r;
+  /* XXX This is leaked */
+  info->chosen_exit = tor_strdup(choose_good_exit_server(dir)->nickname);
   return info;
 }
 
@@ -272,12 +364,11 @@
   int cur_len;
   crypt_path_t *cpath, *hop;
   routerinfo_t **rarray, *r;
-  unsigned int choice;
+  routerinfo_t *choice;
   int rarray_len;
   int i;
   directory_t *dir;
-  char **nicknames;
-  int num_nicknames;
+  int n_failures;
 
   assert(head_ptr);
   assert(router_out);
@@ -302,28 +393,51 @@
   log_fn(LOG_DEBUG, "Path is %d long; we want %d", cur_len, 
          state->desired_path_len);
 
+  n_failures = 0;
+  goto start;
  again:
+  log_fn(LOG_DEBUG, "Picked an already-selected router for hop %d; retrying.",
+         cur_len);
+  ++n_failures;
+  if (n_failures == 25) {
+    /* This actually happens with P=1/30,000,000 when we _could_ build a
+     * circuit.  For now, let's leave it in.
+     */
+    log_fn(LOG_ERR, "Infinite loop in exit path selection");
+    exit(1);
+  }
+ start:
   if(cur_len == 0) { /* picking entry node */
-
-
+    log_fn(LOG_DEBUG, "Contemplating first hop: random choice.");
+    choice = rarray[crypto_pseudo_rand_int(rarray_len)];
+  } else if (cur_len == state->desired_path_len - 1) { /* Picking last node */
+    log_fn(LOG_DEBUG, "Contemplating last hop: choice already made.");
+    choice = router_get_by_nickname(state->chosen_exit);
+  } else {
+    log_fn(LOG_DEBUG, "Contemplating intermediate hop: random choice.");
+    choice = rarray[crypto_pseudo_rand_int(rarray_len)];
   }
-  choice = crypto_pseudo_rand_int(rarray_len);
-  log_fn(LOG_DEBUG,"Contemplating router %s for hop %d",
-         rarray[choice]->nickname, cur_len);
+  log_fn(LOG_DEBUG,"Contemplating router %s for hop %d (exit is %s)",
+         choice->nickname, cur_len, state->chosen_exit);
+  if (cur_len != state->desired_path_len-1 && 
+      !strcasecmp(choice->nickname, state->chosen_exit)) {
+    goto again;
+  }
+    
   for (i = 0, cpath = *head_ptr; i < cur_len; ++i, cpath=cpath->next) {
     r = router_get_by_addr_port(cpath->addr, cpath->port);
-    if ((r && !crypto_pk_cmp_keys(r->onion_pkey, rarray[choice]->onion_pkey))
-        || (cpath->addr == rarray[choice]->addr && 
-            cpath->port == rarray[choice]->or_port)
+    if ((r && !crypto_pk_cmp_keys(r->onion_pkey, choice->onion_pkey))
+        || (cur_len != state->desired_path_len-1 &&
+            !strcasecmp(choice->nickname, state->chosen_exit))
+        || (cpath->addr == choice->addr && 
+            cpath->port == choice->or_port)
         || (options.OnionRouter && 
-            !(connection_twin_get_by_addr_port(rarray[choice]->addr,
-                                               rarray[choice]->or_port)))) {
-      log_fn(LOG_DEBUG, "Picked an already-selected router for hop %d; retrying.",
-             cur_len);
+            !(connection_twin_get_by_addr_port(choice->addr,
+                                               choice->or_port)))) {
       goto again;
     }
   }
-  
+ 
   /* Okay, so we haven't used 'choice' before. */
   hop = (crypt_path_t *)tor_malloc(sizeof(crypt_path_t));
   memset(hop, 0, sizeof(crypt_path_t));
@@ -341,16 +455,16 @@
 
   hop->state = CPATH_STATE_CLOSED;
   
-  hop->port = rarray[choice]->or_port;
-  hop->addr = rarray[choice]->addr;
+  hop->port = choice->or_port;
+  hop->addr = choice->addr;
   
   hop->package_window = CIRCWINDOW_START;
   hop->deliver_window = CIRCWINDOW_START;
 
   log_fn(LOG_DEBUG, "Extended circuit path with %s for hop %d", 
-         rarray[choice]->nickname, cur_len);
+         choice->nickname, cur_len);
   
-  *router_out = rarray[choice];
+  *router_out = choice;
   return 0;
 }
 

Index: or.h
===================================================================
RCS file: /home/or/cvsroot/src/or/or.h,v
retrieving revision 1.185
retrieving revision 1.186
diff -u -d -r1.185 -r1.186
--- or.h	14 Nov 2003 20:45:47 -0000	1.185
+++ or.h	16 Nov 2003 05:33:45 -0000	1.186
@@ -745,6 +745,8 @@
 int router_get_dir_from_string_impl(char *s, directory_t **dest,
                                     crypto_pk_env_t *pkey);
 routerinfo_t *router_get_entry_from_string(char **s);
+int router_supports_exit_address(uint32_t addr, uint16_t port,
+                                 routerinfo_t *router);
 int router_compare_to_exit_policy(connection_t *conn);
 int router_compare_addr_to_exit_policy(uint32_t addr, uint16_t port,
                                        struct exit_policy_t *policy);
@@ -754,6 +756,7 @@
 const routerinfo_t *router_get_desc_routerinfo(void);
 const char *router_get_my_descriptor(void);
 int router_rebuild_descriptor(void);
+int connection_ap_can_use_exit(connection_t *conn, routerinfo_t *exit);
 
 /********************************* dirserv.c ***************************/
 int dirserv_add_own_fingerprint(const char *nickname, crypto_pk_env_t *pk);

Index: routers.c
===================================================================
RCS file: /home/or/cvsroot/src/or/routers.c,v
retrieving revision 1.89
retrieving revision 1.90
diff -u -d -r1.89 -r1.90
--- routers.c	14 Nov 2003 20:45:47 -0000	1.89
+++ routers.c	16 Nov 2003 05:33:45 -0000	1.90
@@ -1061,6 +1061,16 @@
   return -1;
 }
 
+/* Addr is 0 for "IP unknown".
+ *
+ * Returns -1 for 'rejected', 0 for accepted, 1 for 'maybe' (since IP is
+ * unknown.
+ */
+int router_supports_exit_address(uint32_t addr, uint16_t port,
+                                 routerinfo_t *router)
+{
+  return router_compare_addr_to_exit_policy(addr, port, router->exit_policy);
+}
 
 /* Addr is 0 for "IP unknown".
  *
@@ -1075,8 +1085,6 @@
   struct in_addr in;
   struct exit_policy_t *tmpe;
 
-  assert(desc_routerinfo);
-
   for(tmpe=policy; tmpe; tmpe=tmpe->next) {
     log_fn(LOG_DEBUG,"Considering exit policy %s", tmpe->string);
     if (!addr) {
@@ -1117,8 +1125,6 @@
  * Else return -1.
  */
 int router_compare_to_exit_policy(connection_t *conn) {
-  struct exit_policy_t *tmpe;
-
   assert(desc_routerinfo);
   
   if (router_compare_addr_to_exit_policy(conn->addr, conn->port,