src/or/circuitlist.c

   1 /* Copyright 2001 Matej Pfajfar.
   2  * Copyright 2001-2004 Roger Dingledine.
   3  * Copyright 2004-2005 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 = 1;
  80     /* never zero, since a global ID of 0 is treated specially by the controller */
  81
  82   circ = tor_malloc_zero(sizeof(circuit_t));
  83   circ->magic = CIRCUIT_MAGIC;
  84
  85   circ->timestamp_created = time(NULL);
  86
  87   circ->p_circ_id = p_circ_id;
  88   circ->p_conn = p_conn;
  89
  90   circ->state = CIRCUIT_STATE_ONIONSKIN_PENDING;
  91
  92   /* CircIDs */
  93   circ->p_circ_id = p_circ_id;
  94   /* circ->n_circ_id remains 0 because we haven't identified the next hop yet */
  95
  96   circ->package_window = CIRCWINDOW_START;
  97   circ->deliver_window = CIRCWINDOW_START;
  98
  99   circ->next_stream_id = crypto_pseudo_rand_int(1<<16);
 100   circ->global_identifier = n_circuits_allocated++;
 101
 102   circuit_add(circ);
 103
 104   return circ;
 105 }
 106
 107 /** Deallocate space associated with circ.
 108  */
 109 static void circuit_free(circuit_t *circ) {
 110   tor_assert(circ);
 111   tor_assert(circ->magic == CIRCUIT_MAGIC);
 112   if (circ->n_crypto)
 113     crypto_free_cipher_env(circ->n_crypto);
 114   if (circ->p_crypto)
 115     crypto_free_cipher_env(circ->p_crypto);
 116   if (circ->n_digest)
 117     crypto_free_digest_env(circ->n_digest);
 118   if (circ->p_digest)
 119     crypto_free_digest_env(circ->p_digest);
 120   if (circ->build_state) {
 121     tor_free(circ->build_state->chosen_exit_name);
 122     if (circ->build_state->pending_final_cpath)
 123       circuit_free_cpath_node(circ->build_state->pending_final_cpath);
 124   }
 125   tor_free(circ->build_state);
 126   circuit_free_cpath(circ->cpath);
 127   if (circ->rend_splice) {
 128     circ->rend_splice->rend_splice = NULL;
 129   }
 130
 131   memset(circ, 0xAA, sizeof(circuit_t)); /* poison memory */
 132   tor_free(circ);
 133 }
 134
 135 /** Deallocate space associated with the linked list <b>cpath</b>. */
 136 static void circuit_free_cpath(crypt_path_t *cpath) {
 137   crypt_path_t *victim, *head=cpath;
 138
 139   if (!cpath)
 140     return;
 141
 142   /* it's a doubly linked list, so we have to notice when we've
 143    * gone through it once. */
 144   while (cpath->next && cpath->next != head) {
 145     victim = cpath;
 146     cpath = victim->next;
 147     circuit_free_cpath_node(victim);
 148   }
 149
 150   circuit_free_cpath_node(cpath);
 151 }
 152
 153 /** Release all storage held by circuits. */
 154 void
 155 circuit_free_all(void)
 156 {
 157   circuit_t *next;
 158   while (global_circuitlist) {
 159     next = global_circuitlist->next;
 160     while (global_circuitlist->resolving_streams) {
 161       connection_t *next;
 162       next = global_circuitlist->resolving_streams->next_stream;
 163       connection_free(global_circuitlist->resolving_streams);
 164       global_circuitlist->resolving_streams = next;
 165     }
 166     circuit_free(global_circuitlist);
 167     global_circuitlist = next;
 168   }
 169 }
 170
 171 /** Deallocate space associated with the cpath node <b>victim</b>. */
 172 static void
 173 circuit_free_cpath_node(crypt_path_t *victim) {
 174   if (victim->f_crypto)
 175     crypto_free_cipher_env(victim->f_crypto);
 176   if (victim->b_crypto)
 177     crypto_free_cipher_env(victim->b_crypto);
 178   if (victim->f_digest)
 179     crypto_free_digest_env(victim->f_digest);
 180   if (victim->b_digest)
 181     crypto_free_digest_env(victim->b_digest);
 182   if (victim->handshake_state)
 183     crypto_dh_free(victim->handshake_state);
 184   victim->magic = 0xDEADBEEFu;
 185   tor_free(victim);
 186 }
 187
 188 /** Return the circuit whose global ID is <b>id</b>, or NULL if no
 189  * such circuit exists. */
 190 circuit_t *
 191 circuit_get_by_global_id(uint32_t id)
 192 {
 193   circuit_t *circ;
 194   for (circ=global_circuitlist;circ;circ = circ->next) {
 195     if (circ->global_identifier == id) {
 196       if (circ->marked_for_close)
 197         return NULL;
 198       else
 199         return circ;
 200     }
 201   }
 202   return NULL;
 203 }
 204
 205 /** Return a circ such that:
 206  *  - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
 207  *  - circ is attached to <b>conn</b>, either as p_conn, n-conn, or
 208  *    in p_streams or n_streams.
 209  * Return NULL if no such circuit exists.
 210  */
 211 circuit_t *circuit_get_by_circ_id_conn(uint16_t circ_id, 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_circ_id == circ_id) {
 220       if (circ->p_conn == conn)
 221         return circ;
 222       for (tmpconn = circ->p_streams; tmpconn; tmpconn = tmpconn->next_stream) {
 223         if (tmpconn == conn)
 224           return circ;
 225       }
 226     }
 227     if (circ->n_circ_id == circ_id) {
 228       if (circ->n_conn == conn)
 229         return circ;
 230       for (tmpconn = circ->n_streams; tmpconn; tmpconn = tmpconn->next_stream) {
 231         if (tmpconn == conn)
 232           return circ;
 233       }
 234       for (tmpconn = circ->resolving_streams; tmpconn; tmpconn = tmpconn->next_stream) {
 235         if (tmpconn == conn)
 236           return circ;
 237       }
 238     }
 239   }
 240   return NULL;
 241 }
 242
 243 /** Return a circ such that circ is attached to <b>conn</b>, either as
 244  * p_conn, n-conn, or in p_streams or n_streams or resolving_streams.
 245  *
 246  * Return NULL if no such circuit exists.
 247  */
 248 circuit_t *circuit_get_by_conn(connection_t *conn) {
 249   circuit_t *circ;
 250   connection_t *tmpconn;
 251
 252   for (circ=global_circuitlist;circ;circ = circ->next) {
 253     if (circ->marked_for_close)
 254       continue;
 255
 256     if (circ->p_conn == conn)
 257       return circ;
 258     if (circ->n_conn == conn)
 259       return circ;
 260     for (tmpconn = circ->p_streams; tmpconn; tmpconn=tmpconn->next_stream)
 261       if (tmpconn == conn)
 262         return circ;
 263     for (tmpconn = circ->n_streams; tmpconn; tmpconn=tmpconn->next_stream)
 264       if (tmpconn == conn)
 265         return circ;
 266     for (tmpconn = circ->resolving_streams; tmpconn; tmpconn=tmpconn->next_stream)
 267       if (tmpconn == conn)
 268         return circ;
 269   }
 270   return NULL;
 271 }
 272
 273 /** Return a circ such that:
 274  *  - circ-\>rend_query is equal to <b>rend_query</b>, and
 275  *  - circ-\>purpose is equal to <b>purpose</b>.
 276  *
 277  * Return NULL if no such circuit exists.
 278  */
 279 circuit_t *circuit_get_by_rend_query_and_purpose(const char *rend_query, uint8_t purpose) {
 280   circuit_t *circ;
 281
 282   for (circ = global_circuitlist; circ; circ = circ->next) {
 283     if (!circ->marked_for_close &&
 284         circ->purpose == purpose &&
 285         !rend_cmp_service_ids(rend_query, circ->rend_query))
 286       return circ;
 287   }
 288   return NULL;
 289 }
 290
 291 /** Return the first circuit in global_circuitlist after <b>start</b> whose
 292  * rend_pk_digest field is <b>digest</b> and whose purpose is <b>purpose</b>. Returns
 293  * NULL if no circuit is found.  If <b>start</b> is NULL, begin at the start of
 294  * the list.
 295  */
 296 circuit_t *
 297 circuit_get_next_by_pk_and_purpose(circuit_t *start,
 298                                    const char *digest, uint8_t purpose)
 299 {
 300   circuit_t *circ;
 301   if (start == NULL)
 302     circ = global_circuitlist;
 303   else
 304     circ = start->next;
 305
 306   for ( ; circ; circ = circ->next) {
 307     if (circ->marked_for_close)
 308       continue;
 309     if (circ->purpose != purpose)
 310       continue;
 311     if (!memcmp(circ->rend_pk_digest, digest, DIGEST_LEN))
 312       return circ;
 313   }
 314   return NULL;
 315 }
 316
 317 /** Return the circuit waiting for a rendezvous with the provided cookie.
 318  * Return NULL if no such circuit is found.
 319  */
 320 circuit_t *circuit_get_rendezvous(const char *cookie)
 321 {
 322   circuit_t *circ;
 323   for (circ = global_circuitlist; circ; circ = circ->next) {
 324     if (! circ->marked_for_close &&
 325         circ->purpose == CIRCUIT_PURPOSE_REND_POINT_WAITING &&
 326         ! memcmp(circ->rend_cookie, cookie, REND_COOKIE_LEN) )
 327       return circ;
 328   }
 329   return NULL;
 330 }
 331
 332 /** Return a circuit that is open, has specified <b>purpose</b>,
 333  * has a timestamp_dirty value of 0, and is uptime/capacity/internal
 334  * if required; or NULL if no circuit fits this description.
 335  *
 336  * Avoid returning need_uptime circuits if not necessary.
 337  * FFFF As a more important goal, not yet implemented, avoid returning
 338  * internal circuits if not necessary.
 339  */
 340 circuit_t *
 341 circuit_get_clean_open(uint8_t purpose, int need_uptime,
 342                        int need_capacity, int internal) {
 343   circuit_t *circ;
 344   circuit_t *best=NULL;
 345
 346   log_fn(LOG_DEBUG,"Hunting for a circ to cannibalize: purpose %d, uptime %d, capacity %d, internal %d", purpose, need_uptime, need_capacity, internal);
 347
 348   for (circ=global_circuitlist; circ; circ = circ->next) {
 349     if (CIRCUIT_IS_ORIGIN(circ) &&
 350         circ->state == CIRCUIT_STATE_OPEN &&
 351         !circ->marked_for_close &&
 352         circ->purpose == purpose &&
 353         !circ->timestamp_dirty &&
 354         (!need_uptime || circ->build_state->need_uptime) &&
 355         (!need_capacity || circ->build_state->need_capacity) &&
 356         (!internal || circ->build_state->is_internal)) {
 357       if (!best || (best->build_state->need_uptime && !need_uptime))
 358         best = circ;
 359     }
 360   }
 361   return best;
 362 }
 363
 364 /** Go through the circuitlist; mark-for-close each circuit that starts
 365  *  at us but has not yet been used. */
 366 void circuit_mark_all_unused_circs(void) {
 367   circuit_t *circ;
 368
 369   for (circ=global_circuitlist; circ; circ = circ->next) {
 370     if (CIRCUIT_IS_ORIGIN(circ) &&
 371         !circ->marked_for_close &&
 372         !circ->timestamp_dirty)
 373       circuit_mark_for_close(circ);
 374   }
 375 }
 376
 377 /** Mark <b>circ</b> to be closed next time we call
 378  * circuit_close_all_marked(). Do any cleanup needed:
 379  *   - If state is onionskin_pending, remove circ from the onion_pending
 380  *     list.
 381  *   - If circ isn't open yet: call circuit_build_failed() if we're
 382  *     the origin, and in either case call circuit_rep_hist_note_result()
 383  *     to note stats.
 384  *   - If purpose is C_INTRODUCE_ACK_WAIT, remove the intro point we
 385  *     just tried from our list of intro points for that service
 386  *     descriptor.
 387  *   - Send appropriate destroys and edge_destroys for conns and
 388  *     streams attached to circ.
 389  *   - If circ->rend_splice is set (we are the midpoint of a joined
 390  *     rendezvous stream), then mark the other circuit to close as well.
 391  */
 392 void _circuit_mark_for_close(circuit_t *circ, int line, const char *file)
 393 {
 394   connection_t *conn;
 395
 396   assert_circuit_ok(circ);
 397   tor_assert(line);
 398   tor_assert(file);
 399
 400   if (circ->marked_for_close) {
 401     log(LOG_WARN,"Duplicate call to circuit_mark_for_close at %s:%d"
 402         " (first at %s:%d)", line, file,
 403         circ->marked_for_close_file, circ->marked_for_close);
 404     return;
 405   }
 406
 407   if (circ->state == CIRCUIT_STATE_ONIONSKIN_PENDING) {
 408     onion_pending_remove(circ);
 409   }
 410   /* If the circuit ever became OPEN, we sent it to the reputation history
 411    * module then.  If it isn't OPEN, we send it there now to remember which
 412    * links worked and which didn't.
 413    */
 414   if (circ->state != CIRCUIT_STATE_OPEN) {
 415     if (CIRCUIT_IS_ORIGIN(circ)) {
 416       circuit_build_failed(circ); /* take actions if necessary */
 417     }
 418     circuit_rep_hist_note_result(circ);
 419   }
 420   if (CIRCUIT_IS_ORIGIN(circ)) {
 421     control_event_circuit_status(circ,
 422      (circ->state == CIRCUIT_STATE_OPEN)?CIRC_EVENT_CLOSED:CIRC_EVENT_FAILED);
 423   }
 424   if (circ->purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) {
 425     tor_assert(circ->state == CIRCUIT_STATE_OPEN);
 426     /* treat this like getting a nack from it */
 427     log_fn(LOG_INFO,"Failed intro circ %s to %s (awaiting ack). Removing from descriptor.",
 428            circ->rend_query, circ->build_state->chosen_exit_name);
 429     rend_client_remove_intro_point(circ->build_state->chosen_exit_name, circ->rend_query);
 430   }
 431
 432   if (circ->n_conn)
 433     connection_send_destroy(circ->n_circ_id, circ->n_conn);
 434   for (conn=circ->n_streams; conn; conn=conn->next_stream)
 435     connection_edge_destroy(circ->n_circ_id, conn);
 436   while (circ->resolving_streams) {
 437     conn = circ->resolving_streams;
 438     circ->resolving_streams = conn->next_stream;
 439     if (!conn->marked_for_close) {
 440       /* The other side will see a DESTROY, and infer that the connections
 441        * are closing because the circuit is getting torn down.  No need
 442        * to send an end cell*/
 443       conn->has_sent_end = 1; /* we're closing the circuit, nothing to send to */
 444       connection_mark_for_close(conn);
 445     }
 446   }
 447   if (circ->p_conn)
 448     connection_send_destroy(circ->p_circ_id, circ->p_conn);
 449   for (conn=circ->p_streams; conn; conn=conn->next_stream)
 450     connection_edge_destroy(circ->p_circ_id, conn);
 451
 452   circ->marked_for_close = line;
 453   circ->marked_for_close_file = file;
 454
 455   if (circ->rend_splice && !circ->rend_splice->marked_for_close) {
 456     /* do this after marking this circuit, to avoid infinite recursion. */
 457     circuit_mark_for_close(circ->rend_splice);
 458     circ->rend_splice = NULL;
 459   }
 460   return 0;
 461 }
 462
 463 /** Verify that cpath layer <b>cp</b> has all of its invariants
 464  * correct. Trigger an assert if anything is invalid.
 465  */
 466 void assert_cpath_layer_ok(const crypt_path_t *cp)
 467 {
 468 //  tor_assert(cp->addr); /* these are zero for rendezvous extra-hops */
 469 //  tor_assert(cp->port);
 470   tor_assert(cp);
 471   tor_assert(cp->magic == CRYPT_PATH_MAGIC);
 472   switch (cp->state)
 473     {
 474     case CPATH_STATE_OPEN:
 475       tor_assert(cp->f_crypto);
 476       tor_assert(cp->b_crypto);
 477       /* fall through */
 478     case CPATH_STATE_CLOSED:
 479       tor_assert(!cp->handshake_state);
 480       break;
 481     case CPATH_STATE_AWAITING_KEYS:
 482       tor_assert(cp->handshake_state);
 483       break;
 484     default:
 485       log_fn(LOG_ERR,"Unexpected state %d",cp->state);
 486       tor_assert(0);
 487     }
 488   tor_assert(cp->package_window >= 0);
 489   tor_assert(cp->deliver_window >= 0);
 490 }
 491
 492 /** Verify that cpath <b>cp</b> has all of its invariants
 493  * correct. Trigger an assert if anything is invalid.
 494  */
 495 static void
 496 assert_cpath_ok(const crypt_path_t *cp)
 497 {
 498   const crypt_path_t *start = cp;
 499
 500   do {
 501     assert_cpath_layer_ok(cp);
 502     /* layers must be in sequence of: "open* awaiting? closed*" */
 503     if (cp != start) {
 504       if (cp->state == CPATH_STATE_AWAITING_KEYS) {
 505         tor_assert(cp->prev->state == CPATH_STATE_OPEN);
 506       } else if (cp->state == CPATH_STATE_OPEN) {
 507         tor_assert(cp->prev->state == CPATH_STATE_OPEN);
 508       }
 509     }
 510     cp = cp->next;
 511     tor_assert(cp);
 512   } while (cp != start);
 513 }
 514
 515 /** Verify that circuit <b>c</b> has all of its invariants
 516  * correct. Trigger an assert if anything is invalid.
 517  */
 518 void assert_circuit_ok(const circuit_t *c)
 519 {
 520   connection_t *conn;
 521
 522   tor_assert(c);
 523   tor_assert(c->magic == CIRCUIT_MAGIC);
 524   tor_assert(c->purpose >= _CIRCUIT_PURPOSE_MIN &&
 525              c->purpose <= _CIRCUIT_PURPOSE_MAX);
 526
 527   if (c->n_conn) {
 528     tor_assert(c->n_conn->type == CONN_TYPE_OR);
 529     tor_assert(!memcmp(c->n_conn->identity_digest, c->n_conn_id_digest, DIGEST_LEN));
 530   }
 531   if (c->p_conn)
 532     tor_assert(c->p_conn->type == CONN_TYPE_OR);
 533   for (conn = c->p_streams; conn; conn = conn->next_stream)
 534     tor_assert(conn->type == CONN_TYPE_AP);
 535   for (conn = c->n_streams; conn; conn = conn->next_stream)
 536     tor_assert(conn->type == CONN_TYPE_EXIT);
 537
 538   tor_assert(c->deliver_window >= 0);
 539   tor_assert(c->package_window >= 0);
 540   if (c->state == CIRCUIT_STATE_OPEN) {
 541     if (c->cpath) {
 542       tor_assert(CIRCUIT_IS_ORIGIN(c));
 543       tor_assert(!c->n_crypto);
 544       tor_assert(!c->p_crypto);
 545       tor_assert(!c->n_digest);
 546       tor_assert(!c->p_digest);
 547     } else {
 548       tor_assert(!CIRCUIT_IS_ORIGIN(c));
 549       tor_assert(c->n_crypto);
 550       tor_assert(c->p_crypto);
 551       tor_assert(c->n_digest);
 552       tor_assert(c->p_digest);
 553     }
 554   }
 555   if (c->cpath) {
 556     assert_cpath_ok(c->cpath);
 557   }
 558   if (c->purpose == CIRCUIT_PURPOSE_REND_ESTABLISHED) {
 559     if (!c->marked_for_close) {
 560       tor_assert(c->rend_splice);
 561       tor_assert(c->rend_splice->rend_splice == c);
 562     }
 563     tor_assert(c->rend_splice != c);
 564   } else {
 565     tor_assert(!c->rend_splice);
 566   }
 567 }
 568