cpath is now a doubly linked list, not an array

svn:r260

6 files changed, 126 insertions, 126 deletions

diff --git a/src/or/circuit.c b/src/or/circuit.c
index 03d95f05e..e2d1c0d24 100644
--- a/src/or/circuit.c
+++ b/src/or/circuit.c
@@ -89,8 +89,7 @@ void circuit_free(circuit_t *circ) {
 
   if(circ->onion)
     free(circ->onion);
-  if(circ->cpath)
-    circuit_free_cpath(circ->cpath, circ->cpathlen);
+  circuit_free_cpath(circ->cpath);
   while(circ->relay_queue) {
     tmpd = circ->relay_queue;
     circ->relay_queue = tmpd->next;
@@ -101,13 +100,29 @@ void circuit_free(circuit_t *circ) {
   free(circ);
 }
 
-void circuit_free_cpath(crypt_path_t **cpath, int cpathlen) {
-  int i;
+void circuit_free_cpath(crypt_path_t *cpath) {
+  crypt_path_t *victim, *head=cpath;
 
-  for(i=0;i<cpathlen;i++)
-    free(cpath[i]);
+  if(!cpath)
+    return;
+
+  /* it's a doubly linked list, so we have to notice when we've
+   * gone through it once. */
+  while(cpath->next && cpath->next != head) {
+    victim = cpath;
+    cpath = victim->next;
+    circuit_free_cpath_node(victim);
+  }
+
+  circuit_free_cpath_node(cpath);
+}
 
-  free(cpath);
+void circuit_free_cpath_node(crypt_path_t *victim) {
+  if(victim->f_crypto)
+    crypto_free_cipher_env(victim->f_crypto);
+  if(victim->b_crypto)
+    crypto_free_cipher_env(victim->b_crypto);
+  free(victim);
 }
 
 /* return 0 if can't get a unique aci. */
@@ -250,23 +265,18 @@ circuit_t *circuit_get_by_conn(connection_t *conn) {
   return NULL;
 }
 
-circuit_t *circuit_get_newest_by_edge_type(char edge_type) {
+circuit_t *circuit_get_newest_ap(void) {
   circuit_t *circ, *bestcirc=NULL;
 
   for(circ=global_circuitlist;circ;circ = circ->next) {
-    if(edge_type == EDGE_AP && (!circ->p_conn || circ->p_conn->type == CONN_TYPE_AP)) {
+    if(!circ->p_conn || circ->p_conn->type == CONN_TYPE_AP) {
       if(circ->state == CIRCUIT_STATE_OPEN && (!bestcirc ||
         bestcirc->timestamp_created < circ->timestamp_created)) {
-        log(LOG_DEBUG,"circuit_get_newest_by_edge_type(): Choosing n_aci %d.", circ->n_aci);
+        log(LOG_DEBUG,"circuit_get_newest_ap(): Choosing n_aci %d.", circ->n_aci);
         assert(circ->n_aci);
         bestcirc = circ;
       }
     }
-    if(edge_type == EDGE_EXIT && (!circ->n_conn || circ->n_conn->type == CONN_TYPE_EXIT)) {
-      if(circ->state == CIRCUIT_STATE_OPEN && (!bestcirc ||
-        bestcirc->timestamp_created < circ->timestamp_created))
-        bestcirc = circ;
-    }
   }
   return bestcirc;
 }
@@ -346,7 +356,6 @@ int circuit_deliver_relay_cell(cell_t *cell, circuit_t *circ, int cell_direction
 
 int circuit_crypt(circuit_t *circ, char *in, int inlen, char cell_direction) {
   char *out;
-  int i;
   crypt_path_t *thishop;
 
   assert(circ && in);
@@ -357,12 +366,10 @@ int circuit_crypt(circuit_t *circ, char *in, int inlen, char cell_direction) {
 
   if(cell_direction == CELL_DIRECTION_IN) { 
     if(circ->cpath) { /* we're at the beginning of the circuit. We'll want to do layered crypts. */
-      for (i=circ->cpathlen-1; i >= 0; i--) /* moving from first to last hop 
-                                       * Remember : cpath is in reverse order, i.e. last hop first
-                                       */
-      { 
-        thishop = circ->cpath[i];
-
+      thishop = circ->cpath;
+      /* Remember: cpath is in forward order, that is, first hop first. */
+      do {
+        assert(thishop);
         /* decrypt */
         if(crypto_cipher_decrypt(thishop->b_crypto, in, inlen, out)) {
           log(LOG_ERR,"Error performing decryption:%s",crypto_perror());
@@ -372,7 +379,8 @@ int circuit_crypt(circuit_t *circ, char *in, int inlen, char cell_direction) {
 
         /* copy ciphertext back to buf */
         memcpy(in,out,inlen);
-      }
+        thishop = thishop->next;
+      } while(thishop != circ->cpath);
     } else { /* we're in the middle. Just one crypt. */
       if(crypto_cipher_encrypt(circ->p_crypto,in, inlen, out)) {
         log(LOG_ERR,"circuit_encrypt(): Encryption failed for ACI : %u (%s).",
@@ -384,12 +392,10 @@ int circuit_crypt(circuit_t *circ, char *in, int inlen, char cell_direction) {
     }
   } else if(cell_direction == CELL_DIRECTION_OUT) { 
     if(circ->cpath) { /* we're at the beginning of the circuit. We'll want to do layered crypts. */
-      for (i=0; i < circ->cpathlen; i++) /* moving from last to first hop 
-                                          * Remember : cpath is in reverse order, i.e. last hop first
-                                          */
-      { 
-        thishop = circ->cpath[i];
-    
+      thishop = circ->cpath->prev;
+      /* moving from last to first hop */
+      do {
+        assert(thishop);
         /* encrypt */
         if(crypto_cipher_encrypt(thishop->f_crypto, in, inlen, (unsigned char *)out)) {
           log(LOG_ERR,"Error performing encryption:%s",crypto_perror());
@@ -399,7 +405,8 @@ int circuit_crypt(circuit_t *circ, char *in, int inlen, char cell_direction) {
 
         /* copy ciphertext back to buf */
         memcpy(in,out,inlen);
-      }
+        thishop = thishop->prev;
+      } while(thishop != circ->cpath->prev);
     } else { /* we're in the middle. Just one crypt. */
       if(crypto_cipher_decrypt(circ->n_crypto,in, inlen, out)) {
         log(LOG_ERR,"circuit_crypt(): Decryption failed for ACI : %u (%s).",
@@ -524,7 +531,7 @@ void circuit_close(circuit_t *circ) {
 
   assert(circ);
   if(options.APPort) {
-    youngest = circuit_get_newest_by_edge_type(EDGE_AP);
+    youngest = circuit_get_newest_ap();
     log(LOG_DEBUG,"circuit_close(): youngest %d, circ %d.",youngest,circ);
   }
   circuit_remove(circ);
@@ -623,7 +630,7 @@ void circuit_expire_unused_circuits(void) {
   circuit_t *circ, *tmpcirc;
   circuit_t *youngest;
 
-  youngest = circuit_get_newest_by_edge_type(EDGE_AP);
+  youngest = circuit_get_newest_ap();
 
   circ = global_circuitlist;
   while(circ) {
@@ -674,7 +681,7 @@ int circuit_create_onion(void) {
   unsigned int *route; /* hops in the route as an array of indexes into rarray */
   unsigned char *onion; /* holds the onion */
   int onionlen; /* onion length in host order */
-  crypt_path_t **cpath; /* defines the crypt operations that need to be performed on incoming/outgoing data */
+  crypt_path_t *cpath; /* defines the crypt operations that need to be performed on incoming/outgoing data */
 
   /* choose a route */
   route = (unsigned int *)router_new_route(&routelen);
@@ -684,30 +691,21 @@ int circuit_create_onion(void) {
   }
   log(LOG_DEBUG,"circuit_create_onion(): Chosen a route of length %u : ",routelen);
 
-  /* allocate memory for the crypt path */
-  cpath = malloc(routelen * sizeof(crypt_path_t *));
-  if (!cpath) { 
-    log(LOG_ERR,"circuit_create_onion(): Error allocating memory for cpath.");
-    free(route);
-    return -1;
-  }
-
   /* create an onion and calculate crypto keys */
-  onion = router_create_onion(route,routelen,&onionlen,cpath);
+  onion = router_create_onion(route,routelen,&onionlen, &cpath);
   if (!onion) {
     log(LOG_ERR,"circuit_create_onion(): Error creating an onion.");
     free(route);
-    free(cpath); /* it's got nothing in it, since !onion */
     return -1;
   }
   log(LOG_DEBUG,"circuit_create_onion(): Created an onion of size %u bytes.",onionlen);
-  log(LOG_DEBUG,"circuit_create_onion(): Crypt path :");
+//  log(LOG_DEBUG,"circuit_create_onion(): Crypt path :");
 
   return circuit_establish_circuit(route, routelen, onion, onionlen, cpath);
 }
 
 int circuit_establish_circuit(unsigned int *route, int routelen, char *onion,
-                                   int onionlen, crypt_path_t **cpath) {
+                                   int onionlen, crypt_path_t *cpath) {
   routerinfo_t *firsthop;
   connection_t *n_conn;
   circuit_t *circ;
@@ -722,7 +720,6 @@ int circuit_establish_circuit(unsigned int *route, int routelen, char *onion,
   circ->onion = onion;
   circ->onionlen = onionlen;
   circ->cpath = cpath;
-  circ->cpathlen = routelen;
 
   log(LOG_DEBUG,"circuit_establish_circuit(): Looking for firsthop '%s:%u'",
       firsthop->address,firsthop->or_port);
diff --git a/src/or/connection_ap.c b/src/or/connection_ap.c
index ada3ee9a3..ec8c05f0a 100644
--- a/src/or/connection_ap.c
+++ b/src/or/connection_ap.c
@@ -94,7 +94,7 @@ int ap_handshake_process_socks(connection_t *conn) {
   }
 
   /* find the circuit that we should use, if there is one. */
-  circ = circuit_get_newest_by_edge_type(EDGE_AP);
+  circ = circuit_get_newest_ap();
 
   if(!circ) {
     log(LOG_INFO,"ap_handshake_process_socks(): No circuit ready. Closing.");
diff --git a/src/or/main.c b/src/or/main.c
index 7dbb0f2e3..591d568fc 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -325,7 +325,7 @@ int prepare_for_poll(int *timeout) {
     if(options.APPort && time_to_new_circuit < now.tv_sec) {
       circuit_expire_unused_circuits();
       circuit_launch_new(-1); /* tell it to forget about previous failures */
-      circ = circuit_get_newest_by_edge_type(EDGE_AP);
+      circ = circuit_get_newest_ap();
       if(!circ || circ->dirty) {
         log(LOG_INFO,"prepare_for_poll(): Youngest circuit %s; launching replacement.", circ ? "dirty" : "missing");
         circuit_launch_new(0); /* make an onion and lay the circuit */
diff --git a/src/or/onion.c b/src/or/onion.c
index 419667651..fc50279c7 100644
--- a/src/or/onion.c
+++ b/src/or/onion.c
@@ -434,22 +434,24 @@ static int count_acceptable_routers(routerinfo_t **rarray, int rarray_len) {
 /* creates a new onion from route, stores it and its length into buf and len respectively */
 unsigned char *create_onion(routerinfo_t **rarray, int rarray_len, unsigned int *route, int routelen, int *len, crypt_path_t **cpath)
 {
-  int i,j;
+  int i;
   char *layerp;
-  crypt_path_t *hop = NULL;
+  crypt_path_t *hop;
   unsigned char *buf;
   routerinfo_t *router;
   unsigned char iv[16];
   struct in_addr netaddr;
   onion_layer_t layer;
 
-  assert(rarray && route && len && routelen);
+  assert(rarray && route && len && routelen && cpath);
+
+  *cpath = NULL;
 
   /* calculate the size of the onion */
   *len = routelen * ONION_LAYER_SIZE + ONION_PADDING_SIZE;
   /* 28 bytes per layer + 100 bytes padding for the innermost layer */
   log(LOG_DEBUG,"create_onion() : Size of the onion is %u.",*len);
-    
+
   /* allocate memory for the onion */
   buf = malloc(*len);
   if(!buf) {
@@ -457,7 +459,7 @@ unsigned char *create_onion(routerinfo_t **rarray, int rarray_len, unsigned int
     return NULL;
   }
   log(LOG_DEBUG,"create_onion() : Allocated memory for the onion.");
-    
+
   for(i=0; i<routelen; i++) {
     netaddr.s_addr = htonl((rarray[route[i]])->addr);
 
@@ -467,29 +469,20 @@ unsigned char *create_onion(routerinfo_t **rarray, int rarray_len, unsigned int
         (rarray[route[i]])->pkey,
         crypto_pk_keysize((rarray[route[i]])->pkey));
   }
-    
+
   layerp = buf + *len - ONION_LAYER_SIZE - ONION_PADDING_SIZE; /* pointer to innermost layer */
   /* create the onion layer by layer, starting with the innermost */
   for (i=0;i<routelen;i++) {
     router = rarray[route[i]];
-      
-//      log(LOG_DEBUG,"create_onion() : %u",router);
-//      log(LOG_DEBUG,"create_onion() : This router is %s:%u",inet_ntoa(*((struct in_addr *)&router->addr)),router->or_port);
-//      log(LOG_DEBUG,"create_onion() : Key pointer = %u.",router->pkey);
-//      log(LOG_DEBUG,"create_onion() : Key size = %u.",crypto_pk_keysize(router->pkey)); 
-    
 
     layer.version = OR_VERSION;
-    if (i) /* not last hop */
+    if (i) { /* not last hop */
       layer.port = rarray[route[i-1]]->or_port;
-    else
-      layer.port = 0;
-
-    /* Dest Addr */
-    if (i) /* not last hop */
       layer.addr = rarray[route[i-1]]->addr;
-    else
+    } else {
+      layer.port = 0;
       layer.addr = 0;
+    }
 
     /* Expiration Time */
     layer.expire = (uint32_t)(time(NULL) + 86400); /* NOW + 1 day */
@@ -503,47 +496,53 @@ unsigned char *create_onion(routerinfo_t **rarray, int rarray_len, unsigned int
     onion_pack(layerp, &layer);
 
 //      log(LOG_DEBUG,"create_onion() : Onion layer %u built : %u, %u, %u, %s, %u.",i+1,layer->zero,layer->backf,layer->forwf,inet_ntoa(*((struct in_addr *)&layer->addr)),layer->port);
-      
+
     /* build up the crypt_path */
-    if(cpath) {
-      cpath[i] = (crypt_path_t *)malloc(sizeof(crypt_path_t));
-      if(!cpath[i]) {
-        log(LOG_ERR,"Error allocating memory.");
-        goto error;
-      }
-      
-      log(LOG_DEBUG,"create_onion() : Building hop %u of crypt path.",i+1);
-      hop = cpath[i];
-
-      /* calculate keys */
-      crypto_SHA_digest(layer.keyseed,16,hop->digest3);
-      log(LOG_DEBUG,"create_onion() : First SHA pass performed.");
-      crypto_SHA_digest(hop->digest3,20,hop->digest2);
-      log(LOG_DEBUG,"create_onion() : Second SHA pass performed.");
-      crypto_SHA_digest(hop->digest2,20,hop->digest3);
-      log(LOG_DEBUG,"create_onion() : Third SHA pass performed.");
-      log(LOG_DEBUG,"create_onion() : Keys generated.");
-      /* set IV to zero */
-      memset((void *)iv,0,16);
-
-      /* initialize cipher engines */
-      if (! (hop->f_crypto = 
-             crypto_create_init_cipher(DEFAULT_CIPHER, hop->digest3, iv, 1))) {
-        /* cipher initialization failed */
-        log(LOG_ERR,"Could not create a crypto environment.");
-        goto error;
-      }
+    hop = (crypt_path_t *)malloc(sizeof(crypt_path_t));
+    if(!hop) {
+      log(LOG_ERR,"Error allocating memory.");
+      goto error;
+    }
 
-      if (! (hop->b_crypto = 
-             crypto_create_init_cipher(DEFAULT_CIPHER, hop->digest2, iv, 0))) {
-        /* cipher initialization failed */
-        log(LOG_ERR,"Could not create a crypto environment.");
-        goto error;
-      }
- 
-      log(LOG_DEBUG,"create_onion() : Built corresponding crypt path hop.");
+    /* link hop into the cpath, at the front */
+    hop->next = *cpath;
+    hop->prev = NULL;
+    hop->state = CPATH_STATE_OPEN; /* change when we move to incremental paths */
+    if(*cpath) {
+      (*cpath)->prev = hop;
     }
-      
+    *cpath = hop;
+
+    log(LOG_DEBUG,"create_onion() : Building hop %u of crypt path.",i+1);
+
+    /* calculate keys */
+    crypto_SHA_digest(layer.keyseed,16,hop->digest3);
+    log(LOG_DEBUG,"create_onion() : First SHA pass performed.");
+    crypto_SHA_digest(hop->digest3,20,hop->digest2);
+    log(LOG_DEBUG,"create_onion() : Second SHA pass performed.");
+    crypto_SHA_digest(hop->digest2,20,hop->digest3);
+    log(LOG_DEBUG,"create_onion() : Third SHA pass performed.");
+    log(LOG_DEBUG,"create_onion() : Keys generated.");
+    /* set IV to zero */
+    memset((void *)iv,0,16);
+
+    /* initialize cipher engines */
+    if (! (hop->f_crypto = 
+           crypto_create_init_cipher(DEFAULT_CIPHER, hop->digest3, iv, 1))) {
+      /* cipher initialization failed */
+      log(LOG_ERR,"Could not create a crypto environment.");
+      goto error;
+    }
+
+    if (! (hop->b_crypto = 
+           crypto_create_init_cipher(DEFAULT_CIPHER, hop->digest2, iv, 0))) {
+      /* cipher initialization failed */
+      log(LOG_ERR,"Could not create a crypto environment.");
+      goto error;
+    }
+
+    log(LOG_DEBUG,"create_onion() : Built corresponding crypt path hop.");
+
     /* padding if this is the innermost layer */
     if (!i) {
       if (crypto_pseudo_rand(ONION_PADDING_SIZE, layerp + ONION_LAYER_SIZE)) { /* error */
@@ -552,7 +551,7 @@ unsigned char *create_onion(routerinfo_t **rarray, int rarray_len, unsigned int
       }
       log(LOG_DEBUG,"create_onion() : This is the innermost layer. Adding 100 bytes of padding.");
     }
-      
+
     /* encrypt */
 
     if(encrypt_onion(layerp,ONION_PADDING_SIZE+(i+1)*ONION_LAYER_SIZE,router->pkey,layer.keyseed) < 0) {
@@ -560,25 +559,22 @@ unsigned char *create_onion(routerinfo_t **rarray, int rarray_len, unsigned int
       goto error;
     }
     log(LOG_DEBUG,"create_onion() : Encrypted layer.");
-      
+
     /* calculate pointer to next layer */
     layerp = buf + (routelen-i-2)*ONION_LAYER_SIZE;
   }
 
+  /* now link cpath->prev to the end of cpath */
+  for(hop=*cpath; hop->next; hop=hop->next) ;
+  hop->next = *cpath;
+  (*cpath)->prev = hop;
+
   return buf;
 
  error:
-  if (buf)
+  if(buf)
     free(buf);
-  if (cpath) {
-    for (j=0;j<i;j++) {
-      if(cpath[i]->f_crypto)
-        crypto_free_cipher_env(cpath[i]->f_crypto);
-      if(cpath[i]->b_crypto)
-        crypto_free_cipher_env(cpath[i]->b_crypto);
-      free((void *)cpath[i]);
-    }
-  }
+  circuit_free_cpath(*cpath);
   return NULL;
 }
 
diff --git a/src/or/or.h b/src/or/or.h
index 0d707dd68..54bfbe224 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -342,7 +342,14 @@ typedef struct {
   /* crypto environments */
   crypto_cipher_env_t *f_crypto;
   crypto_cipher_env_t *b_crypto;
-  
+
+  char state;
+#define CPATH_STATE_CLOSED 0
+#define CPATH_STATE_AWAITING_KEY 1
+#define CPATH_STATE_OPEN 2
+  void *next;
+  void *prev; /* doubly linked list */
+
 } crypt_path_t;
 
 struct relay_queue_t {
@@ -355,7 +362,7 @@ typedef struct {
   uint32_t n_addr;
   uint16_t n_port;
   connection_t *p_conn;
-  connection_t *n_conn;
+  connection_t *n_conn; /* convention: first conn is the OR conn, if there is one */
   int n_receive_circwindow;
   int p_receive_circwindow;
 
@@ -364,11 +371,10 @@ typedef struct {
 
   struct relay_queue_t *relay_queue; /* for queueing cells at the edges */
 
-  crypto_cipher_env_t *p_crypto; /* crypto environments */
+  crypto_cipher_env_t *p_crypto; /* used only for intermediate hops */
   crypto_cipher_env_t *n_crypto;
 
-  crypt_path_t **cpath;
-  int cpathlen; 
+  crypt_path_t *cpath;
 
   uint32_t expire; /* expiration time for the corresponding onion */
   long timestamp_created;
@@ -497,7 +503,7 @@ aci_t get_unique_aci_by_addr_port(uint32_t addr, uint16_t port, int aci_type);
 
 circuit_t *circuit_get_by_aci_conn(aci_t aci, connection_t *conn);
 circuit_t *circuit_get_by_conn(connection_t *conn);
-circuit_t *circuit_get_newest_by_edge_type(char edge_type);
+circuit_t *circuit_get_newest_ap(void);
 circuit_t *circuit_enumerate_by_naddr_nport(circuit_t *start, uint32_t naddr, uint16_t nport);
 
 int circuit_deliver_relay_cell_from_edge(cell_t *cell, circuit_t *circ, char edge_type);
@@ -510,7 +516,8 @@ int circuit_consider_sending_sendme(circuit_t *circ, int edge_type);
 
 int circuit_init(circuit_t *circ, int aci_type, onion_layer_t *layer);
 void circuit_free(circuit_t *circ);
-void circuit_free_cpath(crypt_path_t **cpath, int cpathlen);
+void circuit_free_cpath(crypt_path_t *cpath);
+void circuit_free_cpath_node(crypt_path_t *victim);
 
 void circuit_close(circuit_t *circ);
 
@@ -523,7 +530,7 @@ void circuit_expire_unused_circuits(void);
 void circuit_launch_new(int failure_status);
 int circuit_create_onion(void);
 int circuit_establish_circuit(unsigned int *route, int routelen, char *onion,
-                                   int onionlen, crypt_path_t **cpath);
+                                   int onionlen, crypt_path_t *cpath);
 void circuit_n_conn_open(connection_t *or_conn);
 int circuit_send_onion(connection_t *or_conn, circuit_t *circ);
 
diff --git a/src/or/test.c b/src/or/test.c
index 81d205eb9..1bcec568b 100644
--- a/src/or/test.c
+++ b/src/or/test.c
@@ -475,7 +475,7 @@ main(int c, char**v) {
   test_buffers();
   puts("========================== Crypto ==========================");
   test_crypto_dh();
-  test_crypto(); /* this seg faults :( */  /* Still? -NM 2003/04/30 */
+  test_crypto();
   puts("\n========================== Util ============================");
   test_util();
   puts("");