src/or/circuitlist.c

   1 /* Copyright 2001 Matej Pfajfar.
   2  * Copyright 2001-2004 Roger Dingledine.
   3  * Copyright 2004 Roger Dingledine, Nick Mathewson. */
   4 /* See LICENSE for licensing information */
   5 /* $Id$ */
   6 const char circuitlist_c_id[] = "$Id$";
   7
   8 /**
   9  * \file circuitlist.c
  10  * \brief Manage the global circuit list.
  11  **/
  12
  13 #include "or.h"
  14
  15 /********* START VARIABLES **********/
  16
  17 /** A global list of all circuits at this hop. */
  18 circuit_t *global_circuitlist=NULL;
  19
  20 /** Array of strings to make circ-\>state human-readable */
  21 const char *circuit_state_to_string[] = {
  22   "doing handshakes",        /* 0 */
  23   "processing the onion",    /* 1 */
  24   "connecting to firsthop",  /* 2 */
  25   "open"                     /* 3 */
  26 };
  27
  28 /********* END VARIABLES ************/
  29
  30 static void circuit_free(circuit_t *circ);
  31 static void circuit_free_cpath(crypt_path_t *cpath);
  32 static void circuit_free_cpath_node(crypt_path_t *victim);
  33
  34 /** Add <b>circ</b> to the global list of circuits. This is called only from
  35  * within circuit_new.
  36  */
  37 static void circuit_add(circuit_t *circ) {
  38   if (!global_circuitlist) { /* first one */
  39     global_circuitlist = circ;
  40     circ->next = NULL;
  41   } else {
  42     circ->next = global_circuitlist;
  43     global_circuitlist = circ;
  44   }
  45 }
  46
  47 /** Detach from the global circuit list, and deallocate, all
  48  * circuits that have been marked for close.
  49  */
  50 void circuit_close_all_marked(void)
  51 {
  52   circuit_t *tmp,*m;
  53
  54   while (global_circuitlist && global_circuitlist->marked_for_close) {
  55     tmp = global_circuitlist->next;
  56     circuit_free(global_circuitlist);
  57     global_circuitlist = tmp;
  58   }
  59
  60   tmp = global_circuitlist;
  61   while (tmp && tmp->next) {
  62     if (tmp->next->marked_for_close) {
  63       m = tmp->next->next;
  64       circuit_free(tmp->next);
  65       tmp->next = m;
  66       /* Need to check new tmp->next; don't advance tmp. */
  67     } else {
  68       /* Advance tmp. */
  69       tmp = tmp->next;
  70     }
  71   }
  72 }
  73
  74 /** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
  75  * and <b>p_conn</b>. Add it to the global circuit list.
  76  */
  77 circuit_t *circuit_new(uint16_t p_circ_id, connection_t *p_conn) {
  78   circuit_t *circ;
  79   static uint32_t n_circuits_allocated = 0;
  80
  81   circ = tor_malloc_zero(sizeof(circuit_t));
  82   circ->magic = CIRCUIT_MAGIC;
  83
  84   circ->timestamp_created = time(NULL);
  85
  86   circ->p_circ_id = p_circ_id;
  87   circ->p_conn = p_conn;
  88
  89   circ->state = CIRCUIT_STATE_ONIONSKIN_PENDING;
  90
  91   /* CircIDs */
  92   circ->p_circ_id = p_circ_id;
  93   /* circ->n_circ_id remains 0 because we haven't identified the next hop yet */
  94
  95   circ->package_window = CIRCWINDOW_START;
  96   circ->deliver_window = CIRCWINDOW_START;
  97
  98   circ->next_stream_id = crypto_pseudo_rand_int(1<<16);
  99   circ->global_identifier = n_circuits_allocated++;
 100
 101   circuit_add(circ);
 102
 103   return circ;
 104 }
 105
 106 /** Deallocate space associated with circ.
 107  */
 108 static void circuit_free(circuit_t *circ) {
 109   tor_assert(circ);
 110   tor_assert(circ->magic == CIRCUIT_MAGIC);
 111   if (circ->n_crypto)
 112     crypto_free_cipher_env(circ->n_crypto);
 113   if (circ->p_crypto)
 114     crypto_free_cipher_env(circ->p_crypto);
 115   if (circ->n_digest)
 116     crypto_free_digest_env(circ->n_digest);
 117   if (circ->p_digest)
 118     crypto_free_digest_env(circ->p_digest);
 119   if (circ->build_state) {
 120     tor_free(circ->build_state->chosen_exit_name);
 121     if (circ->build_state->pending_final_cpath)
 122       circuit_free_cpath_node(circ->build_state->pending_final_cpath);
 123   }
 124   tor_free(circ->build_state);
 125   circuit_free_cpath(circ->cpath);
 126   if (circ->rend_splice) {
 127     circ->rend_splice->rend_splice = NULL;
 128   }
 129
 130   memset(circ, 0xAA, sizeof(circuit_t)); /* poison memory */
 131   tor_free(circ);
 132 }
 133
 134 /** Deallocate space associated with the linked list <b>cpath</b>. */
 135 static void circuit_free_cpath(crypt_path_t *cpath) {
 136   crypt_path_t *victim, *head=cpath;
 137
 138   if (!cpath)
 139     return;
 140
 141   /* it's a doubly linked list, so we have to notice when we've
 142    * gone through it once. */
 143   while (cpath->next && cpath->next != head) {
 144     victim = cpath;
 145     cpath = victim->next;
 146     circuit_free_cpath_node(victim);
 147   }
 148
 149   circuit_free_cpath_node(cpath);
 150 }
 151
 152 /** Deallocate space associated with the cpath node <b>victim</b>. */
 153 static void
 154 circuit_free_cpath_node(crypt_path_t *victim) {
 155   if (victim->f_crypto)
 156     crypto_free_cipher_env(victim->f_crypto);
 157   if (victim->b_crypto)
 158     crypto_free_cipher_env(victim->b_crypto);
 159   if (victim->f_digest)
 160     crypto_free_digest_env(victim->f_digest);
 161   if (victim->b_digest)
 162     crypto_free_digest_env(victim->b_digest);
 163   if (victim->handshake_state)
 164     crypto_dh_free(victim->handshake_state);
 165   tor_free(victim);
 166 }
 167
 168 /** Return a circ such that:
 169  *  - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
 170  *  - circ is attached to <b>conn</b>, either as p_conn, n-conn, or
 171  *    in p_streams or n_streams.
 172  * Return NULL if no such circuit exists.
 173  */
 174 circuit_t *circuit_get_by_circ_id_conn(uint16_t circ_id, connection_t *conn) {
 175   circuit_t *circ;
 176   connection_t *tmpconn;
 177
 178   for (circ=global_circuitlist;circ;circ = circ->next) {
 179     if (circ->marked_for_close)
 180       continue;
 181
 182     if (circ->p_circ_id == circ_id) {
 183       if (circ->p_conn == conn)
 184         return circ;
 185       for (tmpconn = circ->p_streams; tmpconn; tmpconn = tmpconn->next_stream) {
 186         if (tmpconn == conn)
 187           return circ;
 188       }
 189     }
 190     if (circ->n_circ_id == circ_id) {
 191       if (circ->n_conn == conn)
 192         return circ;
 193       for (tmpconn = circ->n_streams; tmpconn; tmpconn = tmpconn->next_stream) {
 194         if (tmpconn == conn)
 195           return circ;
 196       }
 197       for (tmpconn = circ->resolving_streams; tmpconn; tmpconn = tmpconn->next_stream) {
 198         if (tmpconn == conn)
 199           return circ;
 200       }
 201     }
 202   }
 203   return NULL;
 204 }
 205
 206 /** Return a circ such that circ is attached to <b>conn</b>, either as
 207  * p_conn, n-conn, or in p_streams or n_streams or resolving_streams.
 208  *
 209  * Return NULL if no such circuit exists.
 210  */
 211 circuit_t *circuit_get_by_conn(connection_t *conn) {
 212   circuit_t *circ;
 213   connection_t *tmpconn;
 214
 215   for (circ=global_circuitlist;circ;circ = circ->next) {
 216     if (circ->marked_for_close)
 217       continue;
 218
 219     if (circ->p_conn == conn)
 220       return circ;
 221     if (circ->n_conn == conn)
 222       return circ;
 223     for (tmpconn = circ->p_streams; tmpconn; tmpconn=tmpconn->next_stream)
 224       if (tmpconn == conn)
 225         return circ;
 226     for (tmpconn = circ->n_streams; tmpconn; tmpconn=tmpconn->next_stream)
 227       if (tmpconn == conn)
 228         return circ;
 229     for (tmpconn = circ->resolving_streams; tmpconn; tmpconn=tmpconn->next_stream)
 230       if (tmpconn == conn)
 231         return circ;
 232   }
 233   return NULL;
 234 }
 235
 236 /** Return a circ such that:
 237  *  - circ-\>rend_query is equal to <b>rend_query</b>, and
 238  *  - circ-\>purpose is equal to <b>purpose</b>.
 239  *
 240  * Return NULL if no such circuit exists.
 241  */
 242 circuit_t *circuit_get_by_rend_query_and_purpose(const char *rend_query, uint8_t purpose) {
 243   circuit_t *circ;
 244
 245   for (circ = global_circuitlist; circ; circ = circ->next) {
 246     if (!circ->marked_for_close &&
 247         circ->purpose == purpose &&
 248         !rend_cmp_service_ids(rend_query, circ->rend_query))
 249       return circ;
 250   }
 251   return NULL;
 252 }
 253
 254 /** Return the first circuit in global_circuitlist after <b>start</b> whose
 255  * rend_pk_digest field is <b>digest</b> and whose purpose is <b>purpose</b>. Returns
 256  * NULL if no circuit is found.  If <b>start</b> is NULL, begin at the start of
 257  * the list.
 258  */
 259 circuit_t *
 260 circuit_get_next_by_pk_and_purpose(circuit_t *start,
 261                                    const char *digest, uint8_t purpose)
 262 {
 263   circuit_t *circ;
 264   if (start == NULL)
 265     circ = global_circuitlist;
 266   else
 267     circ = start->next;
 268
 269   for ( ; circ; circ = circ->next) {
 270     if (circ->marked_for_close)
 271       continue;
 272     if (circ->purpose != purpose)
 273       continue;
 274     if (!memcmp(circ->rend_pk_digest, digest, DIGEST_LEN))
 275       return circ;
 276   }
 277   return NULL;
 278 }
 279
 280 /** Return the circuit waiting for a rendezvous with the provided cookie.
 281  * Return NULL if no such circuit is found.
 282  */
 283 circuit_t *circuit_get_rendezvous(const char *cookie)
 284 {
 285   circuit_t *circ;
 286   for (circ = global_circuitlist; circ; circ = circ->next) {
 287     if (! circ->marked_for_close &&
 288         circ->purpose == CIRCUIT_PURPOSE_REND_POINT_WAITING &&
 289         ! memcmp(circ->rend_cookie, cookie, REND_COOKIE_LEN) )
 290       return circ;
 291   }
 292   return NULL;
 293 }
 294
 295 /** Return a circuit that is open, has specified <b>purpose</b>,
 296  * has a timestamp_dirty value of 0, and is uptime/capacity/internal
 297  * if required; or NULL if no circuit fits this description.
 298  *
 299  * Avoid returning need_uptime circuits if not necessary.
 300  * FFFF As a more important goal, not yet implemented, avoid returning
 301  * internal circuits if not necessary.
 302  */
 303 circuit_t *
 304 circuit_get_clean_open(uint8_t purpose, int need_uptime,
 305                        int need_capacity, int internal) {
 306   circuit_t *circ;
 307   circuit_t *best=NULL;
 308
 309   log_fn(LOG_DEBUG,"Hunting for a circ to cannibalize: purpose %d, uptime %d, capacity %d, internal %d", purpose, need_uptime, need_capacity, internal);
 310
 311   for (circ=global_circuitlist; circ; circ = circ->next) {
 312     if (CIRCUIT_IS_ORIGIN(circ) &&
 313         circ->state == CIRCUIT_STATE_OPEN &&
 314         !circ->marked_for_close &&
 315         circ->purpose == purpose &&
 316         !circ->timestamp_dirty &&
 317         (!need_uptime || circ->build_state->need_uptime) &&
 318         (!need_capacity || circ->build_state->need_capacity) &&
 319         (!internal || circ->build_state->is_internal)) {
 320       if (!best || (best->build_state->need_uptime && !need_uptime))
 321         best = circ;
 322     }
 323   }
 324   return best;
 325 }
 326
 327 /** Mark <b>circ</b> to be closed next time we call
 328  * circuit_close_all_marked(). Do any cleanup needed:
 329  *   - If state is onionskin_pending, remove circ from the onion_pending
 330  *     list.
 331  *   - If circ isn't open yet: call circuit_build_failed() if we're
 332  *     the origin, and in either case call circuit_rep_hist_note_result()
 333  *     to note stats.
 334  *   - If purpose is C_INTRODUCE_ACK_WAIT, remove the intro point we
 335  *     just tried from our list of intro points for that service
 336  *     descriptor.
 337  *   - Send appropriate destroys and edge_destroys for conns and
 338  *     streams attached to circ.
 339  *   - If circ->rend_splice is set (we are the midpoint of a joined
 340  *     rendezvous stream), then mark the other circuit to close as well.
 341  */
 342 int _circuit_mark_for_close(circuit_t *circ) {
 343   connection_t *conn;
 344
 345   assert_circuit_ok(circ);
 346   if (circ->marked_for_close)
 347     return -1;
 348
 349   if (circ->state == CIRCUIT_STATE_ONIONSKIN_PENDING) {
 350     onion_pending_remove(circ);
 351   }
 352   /* If the circuit ever became OPEN, we sent it to the reputation history
 353    * module then.  If it isn't OPEN, we send it there now to remember which
 354    * links worked and which didn't.
 355    */
 356   if (circ->state != CIRCUIT_STATE_OPEN) {
 357     if (CIRCUIT_IS_ORIGIN(circ)) {
 358       circuit_build_failed(circ); /* take actions if necessary */
 359     }
 360     circuit_rep_hist_note_result(circ);
 361   }
 362   if (CIRCUIT_IS_ORIGIN(circ)) {
 363     control_event_circuit_status(circ,
 364      (circ->state == CIRCUIT_STATE_OPEN)?CIRC_EVENT_CLOSED:CIRC_EVENT_FAILED);
 365   }
 366   if (circ->purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) {
 367     tor_assert(circ->state == CIRCUIT_STATE_OPEN);
 368     /* treat this like getting a nack from it */
 369     log_fn(LOG_INFO,"Failed intro circ %s to %s (awaiting ack). Removing from descriptor.",
 370            circ->rend_query, circ->build_state->chosen_exit_name);
 371     rend_client_remove_intro_point(circ->build_state->chosen_exit_name, circ->rend_query);
 372   }
 373
 374   if (circ->n_conn)
 375     connection_send_destroy(circ->n_circ_id, circ->n_conn);
 376   for (conn=circ->n_streams; conn; conn=conn->next_stream)
 377     connection_edge_destroy(circ->n_circ_id, conn);
 378   while (circ->resolving_streams) {
 379     conn = circ->resolving_streams;
 380     circ->resolving_streams = conn->next_stream;
 381     if (!conn->marked_for_close)
 382       connection_mark_for_close(conn);
 383   }
 384   if (circ->p_conn)
 385     connection_send_destroy(circ->p_circ_id, circ->p_conn);
 386   for (conn=circ->p_streams; conn; conn=conn->next_stream)
 387     connection_edge_destroy(circ->p_circ_id, conn);
 388
 389   circ->marked_for_close = 1;
 390
 391   if (circ->rend_splice && !circ->rend_splice->marked_for_close) {
 392     /* do this after marking this circuit, to avoid infinite recursion. */
 393     circuit_mark_for_close(circ->rend_splice);
 394     circ->rend_splice = NULL;
 395   }
 396   return 0;
 397 }
 398
 399 /** Verify that cpath layer <b>cp</b> has all of its invariants
 400  * correct. Trigger an assert if anything is invalid.
 401  */
 402 void assert_cpath_layer_ok(const crypt_path_t *cp)
 403 {
 404 //  tor_assert(cp->addr); /* these are zero for rendezvous extra-hops */
 405 //  tor_assert(cp->port);
 406   switch (cp->state)
 407     {
 408     case CPATH_STATE_OPEN:
 409       tor_assert(cp->f_crypto);
 410       tor_assert(cp->b_crypto);
 411       /* fall through */
 412     case CPATH_STATE_CLOSED:
 413       tor_assert(!cp->handshake_state);
 414       break;
 415     case CPATH_STATE_AWAITING_KEYS:
 416       tor_assert(cp->handshake_state);
 417       break;
 418     default:
 419       log_fn(LOG_ERR,"Unexpected state %d",cp->state);
 420       tor_assert(0);
 421     }
 422   tor_assert(cp->package_window >= 0);
 423   tor_assert(cp->deliver_window >= 0);
 424 }
 425
 426 /** Verify that cpath <b>cp</b> has all of its invariants
 427  * correct. Trigger an assert if anything is invalid.
 428  */
 429 static void
 430 assert_cpath_ok(const crypt_path_t *cp)
 431 {
 432   const crypt_path_t *start = cp;
 433
 434   do {
 435     assert_cpath_layer_ok(cp);
 436     /* layers must be in sequence of: "open* awaiting? closed*" */
 437     if (cp != start) {
 438       if (cp->state == CPATH_STATE_AWAITING_KEYS) {
 439         tor_assert(cp->prev->state == CPATH_STATE_OPEN);
 440       } else if (cp->state == CPATH_STATE_OPEN) {
 441         tor_assert(cp->prev->state == CPATH_STATE_OPEN);
 442       }
 443     }
 444     cp = cp->next;
 445     tor_assert(cp);
 446   } while (cp != start);
 447 }
 448
 449 /** Verify that circuit <b>c</b> has all of its invariants
 450  * correct. Trigger an assert if anything is invalid.
 451  */
 452 void assert_circuit_ok(const circuit_t *c)
 453 {
 454   connection_t *conn;
 455
 456   tor_assert(c);
 457   tor_assert(c->magic == CIRCUIT_MAGIC);
 458   tor_assert(c->purpose >= _CIRCUIT_PURPOSE_MIN &&
 459              c->purpose <= _CIRCUIT_PURPOSE_MAX);
 460
 461   if (c->n_conn) {
 462     tor_assert(c->n_conn->type == CONN_TYPE_OR);
 463     tor_assert(!memcmp(c->n_conn->identity_digest, c->n_conn_id_digest, DIGEST_LEN));
 464   }
 465   if (c->p_conn)
 466     tor_assert(c->p_conn->type == CONN_TYPE_OR);
 467   for (conn = c->p_streams; conn; conn = conn->next_stream)
 468     tor_assert(conn->type == CONN_TYPE_AP);
 469   for (conn = c->n_streams; conn; conn = conn->next_stream)
 470     tor_assert(conn->type == CONN_TYPE_EXIT);
 471
 472   tor_assert(c->deliver_window >= 0);
 473   tor_assert(c->package_window >= 0);
 474   if (c->state == CIRCUIT_STATE_OPEN) {
 475     if (c->cpath) {
 476       tor_assert(CIRCUIT_IS_ORIGIN(c));
 477       tor_assert(!c->n_crypto);
 478       tor_assert(!c->p_crypto);
 479       tor_assert(!c->n_digest);
 480       tor_assert(!c->p_digest);
 481     } else {
 482       tor_assert(!CIRCUIT_IS_ORIGIN(c));
 483       tor_assert(c->n_crypto);
 484       tor_assert(c->p_crypto);
 485       tor_assert(c->n_digest);
 486       tor_assert(c->p_digest);
 487     }
 488   }
 489   if (c->cpath) {
 490     assert_cpath_ok(c->cpath);
 491   }
 492   if (c->purpose == CIRCUIT_PURPOSE_REND_ESTABLISHED) {
 493     if (!c->marked_for_close) {
 494       tor_assert(c->rend_splice);
 495       tor_assert(c->rend_splice->rend_splice == c);
 496     }
 497     tor_assert(c->rend_splice != c);
 498   } else {
 499     tor_assert(!c->rend_splice);
 500   }
 501 }
 502