src/or/circuitlist.c

   1 /* Copyright 2001 Matej Pfajfar.
   2  * Copyright (c) 2001-2004, Roger Dingledine.
   3  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. */
   4 /* See LICENSE for licensing information */
   5 /* $Id$ */
   6 const char circuitlist_c_id[] =
   7   "$Id$";
   8
   9 /**
  10  * \file circuitlist.c
  11  * \brief Manage the global circuit list.
  12  **/
  13
  14 #include "or.h"
  15
  16 #include "../common/ht.h"
  17
  18 /********* START VARIABLES **********/
  19
  20 /** A global list of all circuits at this hop. */
  21 circuit_t *global_circuitlist=NULL;
  22
  23 /** A list of all the circuits in CIRCUIT_STATE_OR_WAIT. */
  24 smartlist_t *circuits_pending_or_conns=NULL;
  25
  26 static void circuit_free(circuit_t *circ);
  27 static void circuit_free_cpath(crypt_path_t *cpath);
  28 static void circuit_free_cpath_node(crypt_path_t *victim);
  29
  30 /********* END VARIABLES ************/
  31
  32 /** A map from OR connection and circuit ID to circuit.  (Lookup performance is
  33  * very important here, since we need to do it every time a cell arrives.) */
  34 typedef struct orconn_circid_circuit_map_t {
  35   HT_ENTRY(orconn_circid_circuit_map_t) node;
  36   connection_t *or_conn;
  37   uint16_t circ_id;
  38   circuit_t *circuit;
  39 } orconn_circid_circuit_map_t;
  40
  41 /** Helper for hash tables: compare the OR connection and circuit ID for a and
  42  * b, and return less than, equal to, or greater than zero appropriately.
  43  */
  44 static INLINE int
  45 _orconn_circid_entries_eq(orconn_circid_circuit_map_t *a,
  46                           orconn_circid_circuit_map_t *b)
  47 {
  48   return a->or_conn == b->or_conn && a->circ_id == b->circ_id;
  49 }
  50
  51 static INLINE unsigned int
  52 _orconn_circid_entry_hash(orconn_circid_circuit_map_t *a)
  53 {
  54   return (((unsigned)a->circ_id)<<16) ^ (unsigned)(uintptr_t)(a->or_conn);
  55 }
  56
  57 static HT_HEAD(orconn_circid_map, orconn_circid_circuit_map_t)
  58      orconn_circid_circuit_map = HT_INITIALIZER();
  59 HT_PROTOTYPE(orconn_circid_map, orconn_circid_circuit_map_t, node,
  60              _orconn_circid_entry_hash, _orconn_circid_entries_eq);
  61 HT_GENERATE(orconn_circid_map, orconn_circid_circuit_map_t, node,
  62             _orconn_circid_entry_hash, _orconn_circid_entries_eq, 0.6,
  63             malloc, realloc, free);
  64
  65 /** The most recently returned entry from circuit_get_by_circid_orconn;
  66  * used to improve performance when many cells arrive in a row from the
  67  * same circuit.
  68  */
  69 orconn_circid_circuit_map_t *_last_circid_orconn_ent = NULL;
  70
  71 /** Set the p_conn or n_conn field of a circuit <b>circ</b>, along
  72  * with the corresponding circuit ID, and add the circuit as appropriate
  73  * to the (orconn,id)-\>circuit map. */
  74 void
  75 circuit_set_circid_orconn(circuit_t *circ, uint16_t id,
  76                           connection_t *conn,
  77                           enum which_conn_changed_t which)
  78 {
  79   uint16_t old_id;
  80   connection_t *old_conn;
  81   orconn_circid_circuit_map_t search;
  82   orconn_circid_circuit_map_t *found;
  83
  84   tor_assert(!conn || conn->type == CONN_TYPE_OR);
  85
  86   if (which == P_CONN_CHANGED) {
  87     old_id = circ->p_circ_id;
  88     old_conn = circ->p_conn;
  89     circ->p_circ_id = id;
  90     circ->p_conn = conn;
  91   } else {
  92     old_id = circ->n_circ_id;
  93     old_conn = circ->n_conn;
  94     circ->n_circ_id = id;
  95     circ->n_conn = conn;
  96   }
  97   if (conn == old_conn && old_id == id)
  98     return;
  99
 100   if (_last_circid_orconn_ent &&
 101       ((old_id == _last_circid_orconn_ent->circ_id &&
 102         old_conn == _last_circid_orconn_ent->or_conn) ||
 103        (id == _last_circid_orconn_ent->circ_id &&
 104         conn == _last_circid_orconn_ent->or_conn))) {
 105     _last_circid_orconn_ent = NULL;
 106   }
 107
 108   if (old_conn) { /* we may need to remove it from the conn-circid map */
 109     tor_assert(old_conn->magic == CONNECTION_MAGIC);
 110     search.circ_id = old_id;
 111     search.or_conn = old_conn;
 112     found = HT_REMOVE(orconn_circid_map, &orconn_circid_circuit_map, &search);
 113     if (found) {
 114       tor_free(found);
 115       --old_conn->n_circuits;
 116     }
 117   }
 118
 119   if (conn == NULL)
 120     return;
 121
 122   /* now add the new one to the conn-circid map */
 123   search.circ_id = id;
 124   search.or_conn = conn;
 125   found = HT_FIND(orconn_circid_map, &orconn_circid_circuit_map, &search);
 126   if (found) {
 127     found->circuit = circ;
 128   } else {
 129     found = tor_malloc_zero(sizeof(orconn_circid_circuit_map_t));
 130     found->circ_id = id;
 131     found->or_conn = conn;
 132     found->circuit = circ;
 133     HT_INSERT(orconn_circid_map, &orconn_circid_circuit_map, found);
 134   }
 135   ++conn->n_circuits;
 136 }
 137
 138 /** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
 139  * it from lists as appropriate. */
 140 void
 141 circuit_set_state(circuit_t *circ, int state)
 142 {
 143   tor_assert(circ);
 144   if (state == circ->state)
 145     return;
 146   if (circ->state == CIRCUIT_STATE_OR_WAIT) {
 147     /* remove from waiting-circuit list. */
 148     if (circuits_pending_or_conns)
 149       smartlist_remove(circuits_pending_or_conns, circ);
 150   }
 151   if (state == CIRCUIT_STATE_OR_WAIT) {
 152     /* add to waiting-circuit list. */
 153     if (!circuits_pending_or_conns)
 154       circuits_pending_or_conns = smartlist_create();
 155     smartlist_add(circuits_pending_or_conns, circ);
 156   }
 157   circ->state = state;
 158 }
 159
 160 /** Add <b>circ</b> to the global list of circuits. This is called only from
 161  * within circuit_new.
 162  */
 163 static void
 164 circuit_add(circuit_t *circ)
 165 {
 166   if (!global_circuitlist) { /* first one */
 167     global_circuitlist = circ;
 168     circ->next = NULL;
 169   } else {
 170     circ->next = global_circuitlist;
 171     global_circuitlist = circ;
 172   }
 173 }
 174
 175 /** Detach from the global circuit list, and deallocate, all
 176  * circuits that have been marked for close.
 177  */
 178 void
 179 circuit_close_all_marked(void)
 180 {
 181   circuit_t *tmp,*m;
 182
 183   while (global_circuitlist && global_circuitlist->marked_for_close) {
 184     tmp = global_circuitlist->next;
 185     circuit_free(global_circuitlist);
 186     global_circuitlist = tmp;
 187   }
 188
 189   tmp = global_circuitlist;
 190   while (tmp && tmp->next) {
 191     if (tmp->next->marked_for_close) {
 192       m = tmp->next->next;
 193       circuit_free(tmp->next);
 194       tmp->next = m;
 195       /* Need to check new tmp->next; don't advance tmp. */
 196     } else {
 197       /* Advance tmp. */
 198       tmp = tmp->next;
 199     }
 200   }
 201 }
 202
 203 /** Return the head of the global linked list of circuits. **/
 204 circuit_t *
 205 _circuit_get_global_list(void)
 206 {
 207   return global_circuitlist;
 208 }
 209
 210 /** Function to make circ-\>state human-readable */
 211 const char *
 212 circuit_state_to_string(int state)
 213 {
 214   static char buf[64];
 215   switch (state) {
 216     case CIRCUIT_STATE_BUILDING: return "doing handshakes";
 217     case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion";
 218     case CIRCUIT_STATE_OR_WAIT: return "connecting to server";
 219     case CIRCUIT_STATE_OPEN: return "open";
 220     default:
 221       log_warn(LD_BUG, "Bug: unknown circuit state %d", state);
 222       tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
 223       return buf;
 224   }
 225 }
 226
 227 /** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
 228  * and <b>p_conn</b>. Add it to the global circuit list.
 229  */
 230 circuit_t *
 231 circuit_new(uint16_t p_circ_id, connection_t *p_conn)
 232 {
 233   circuit_t *circ;
 234   static uint32_t n_circuits_allocated = 1;
 235   /* never zero, since a global ID of 0 is treated specially by the
 236    * controller */
 237
 238   circ = tor_malloc_zero(sizeof(circuit_t));
 239   circ->magic = CIRCUIT_MAGIC;
 240
 241   circ->timestamp_created = time(NULL);
 242
 243   /* CircIDs */
 244   if (p_conn) {
 245     circuit_set_circid_orconn(circ, p_circ_id, p_conn, P_CONN_CHANGED);
 246   }
 247   /* circ->n_circ_id remains 0 because we haven't identified the next hop
 248    * yet */
 249
 250   circ->package_window = CIRCWINDOW_START;
 251   circ->deliver_window = CIRCWINDOW_START;
 252
 253   circ->next_stream_id = crypto_rand_int(1<<16);
 254   circ->global_identifier = n_circuits_allocated++;
 255
 256   circuit_add(circ);
 257
 258   return circ;
 259 }
 260
 261 /** Deallocate space associated with circ.
 262  */
 263 static void
 264 circuit_free(circuit_t *circ)
 265 {
 266   tor_assert(circ);
 267   tor_assert(circ->magic == CIRCUIT_MAGIC);
 268   if (circ->n_crypto)
 269     crypto_free_cipher_env(circ->n_crypto);
 270   if (circ->p_crypto)
 271     crypto_free_cipher_env(circ->p_crypto);
 272   if (circ->n_digest)
 273     crypto_free_digest_env(circ->n_digest);
 274   if (circ->p_digest)
 275     crypto_free_digest_env(circ->p_digest);
 276   if (circ->build_state) {
 277     if (circ->build_state->chosen_exit)
 278       extend_info_free(circ->build_state->chosen_exit);
 279     if (circ->build_state->pending_final_cpath)
 280       circuit_free_cpath_node(circ->build_state->pending_final_cpath);
 281   }
 282   tor_free(circ->build_state);
 283   tor_free(circ->onionskin);
 284   circuit_free_cpath(circ->cpath);
 285   if (circ->rend_splice) {
 286     tor_assert(circ->rend_splice->magic == CIRCUIT_MAGIC);
 287     circ->rend_splice->rend_splice = NULL;
 288   }
 289   /* Remove from map. */
 290   circuit_set_circid_orconn(circ, 0, NULL, P_CONN_CHANGED);
 291   circuit_set_circid_orconn(circ, 0, NULL, N_CONN_CHANGED);
 292
 293   memset(circ, 0xAA, sizeof(circuit_t)); /* poison memory */
 294   tor_free(circ);
 295 }
 296
 297 /** Deallocate space associated with the linked list <b>cpath</b>. */
 298 static void
 299 circuit_free_cpath(crypt_path_t *cpath)
 300 {
 301   crypt_path_t *victim, *head=cpath;
 302
 303   if (!cpath)
 304     return;
 305
 306   /* it's a doubly linked list, so we have to notice when we've
 307    * gone through it once. */
 308   while (cpath->next && cpath->next != head) {
 309     victim = cpath;
 310     cpath = victim->next;
 311     circuit_free_cpath_node(victim);
 312   }
 313
 314   circuit_free_cpath_node(cpath);
 315 }
 316
 317 /** Release all storage held by circuits. */
 318 void
 319 circuit_free_all(void)
 320 {
 321   circuit_t *next;
 322   while (global_circuitlist) {
 323     next = global_circuitlist->next;
 324     while (global_circuitlist->resolving_streams) {
 325       connection_t *next;
 326       next = global_circuitlist->resolving_streams->next_stream;
 327       connection_free(global_circuitlist->resolving_streams);
 328       global_circuitlist->resolving_streams = next;
 329     }
 330     circuit_free(global_circuitlist);
 331     global_circuitlist = next;
 332   }
 333   if (circuits_pending_or_conns) {
 334     smartlist_free(circuits_pending_or_conns);
 335     circuits_pending_or_conns = NULL;
 336   }
 337   HT_CLEAR(orconn_circid_map, &orconn_circid_circuit_map);
 338 }
 339
 340 /** Deallocate space associated with the cpath node <b>victim</b>. */
 341 static void
 342 circuit_free_cpath_node(crypt_path_t *victim)
 343 {
 344   if (victim->f_crypto)
 345     crypto_free_cipher_env(victim->f_crypto);
 346   if (victim->b_crypto)
 347     crypto_free_cipher_env(victim->b_crypto);
 348   if (victim->f_digest)
 349     crypto_free_digest_env(victim->f_digest);
 350   if (victim->b_digest)
 351     crypto_free_digest_env(victim->b_digest);
 352   if (victim->dh_handshake_state)
 353     crypto_dh_free(victim->dh_handshake_state);
 354   if (victim->extend_info)
 355     extend_info_free(victim->extend_info);
 356
 357   victim->magic = 0xDEADBEEFu;
 358   tor_free(victim);
 359 }
 360
 361 /** Return the circuit whose global ID is <b>id</b>, or NULL if no
 362  * such circuit exists. */
 363 circuit_t *
 364 circuit_get_by_global_id(uint32_t id)
 365 {
 366   circuit_t *circ;
 367   for (circ=global_circuitlist;circ;circ = circ->next) {
 368     if (circ->global_identifier == id) {
 369       if (circ->marked_for_close)
 370         return NULL;
 371       else
 372         return circ;
 373     }
 374   }
 375   return NULL;
 376 }
 377
 378 /** Return a circ such that:
 379  *  - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
 380  *  - circ is attached to <b>conn</b>, either as p_conn or n_conn.
 381  * Return NULL if no such circuit exists.
 382  */
 383 static INLINE circuit_t *
 384 circuit_get_by_circid_orconn_impl(uint16_t circ_id, connection_t *conn)
 385 {
 386   orconn_circid_circuit_map_t search;
 387   orconn_circid_circuit_map_t *found;
 388
 389   tor_assert(conn->type == CONN_TYPE_OR);
 390
 391   if (_last_circid_orconn_ent &&
 392       circ_id == _last_circid_orconn_ent->circ_id &&
 393       conn == _last_circid_orconn_ent->or_conn) {
 394     found = _last_circid_orconn_ent;
 395   } else {
 396     search.circ_id = circ_id;
 397     search.or_conn = conn;
 398     found = HT_FIND(orconn_circid_map, &orconn_circid_circuit_map, &search);
 399     _last_circid_orconn_ent = found;
 400   }
 401   if (found && found->circuit)
 402     return found->circuit;
 403
 404   return NULL;
 405
 406   /* The rest of this checks for bugs. Disabled by default. */
 407   {
 408     circuit_t *circ;
 409     for (circ=global_circuitlist;circ;circ = circ->next) {
 410       if (circ->p_conn == conn && circ->p_circ_id == circ_id) {
 411         log_warn(LD_BUG,
 412                  "circuit matches p_conn, but not in hash table (Bug!)");
 413         return circ;
 414       }
 415       if (circ->n_conn == conn && circ->n_circ_id == circ_id) {
 416         log_warn(LD_BUG,
 417                  "circuit matches n_conn, but not in hash table (Bug!)");
 418         return circ;
 419       }
 420     }
 421     return NULL;
 422   }
 423 }
 424
 425 /** Return a circ such that:
 426  *  - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
 427  *  - circ is attached to <b>conn</b>, either as p_conn or n_conn.
 428  *  - circ is not marked for close.
 429  * Return NULL if no such circuit exists.
 430  */
 431 circuit_t *
 432 circuit_get_by_circid_orconn(uint16_t circ_id, connection_t *conn)
 433 {
 434   circuit_t *circ = circuit_get_by_circid_orconn_impl(circ_id, conn);
 435   if (!circ || circ->marked_for_close)
 436     return NULL;
 437   else
 438     return circ;
 439 }
 440
 441 /** Return true iff there is a circ such that
 442  *  - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
 443  *  - circ is attached to <b>conn</b>, either as p_conn or n_conn.
 444  * Return NULL if no such circuit exists.
 445  */
 446 int
 447 circuit_id_used_on_conn(uint16_t circ_id, connection_t *conn)
 448 {
 449   circuit_t *circ = circuit_get_by_circid_orconn_impl(circ_id, conn);
 450   if (circ && circ->marked_for_close)
 451     log_fn(LOG_NOTICE, LD_CIRC,
 452            "I was about to re-use a circuit ID that had been marked."
 453            " Good thing we fixed that bug!");
 454   return circ != NULL;
 455 }
 456
 457 /** Return the circuit that a given edge connection is using. */
 458 circuit_t *
 459 circuit_get_by_edge_conn(connection_t *conn)
 460 {
 461   circuit_t *circ;
 462   tor_assert(CONN_IS_EDGE(conn));
 463
 464   circ = conn->on_circuit;
 465   tor_assert(!circ || circ->magic == CIRCUIT_MAGIC);
 466
 467   return circ;
 468 }
 469
 470 /** For each circuits that have <b>conn</b> as n_conn or p_conn, unlink the
 471  * circuit from the orconn,circid map, and mark it for close if it hasn't
 472  * been marked already.
 473  */
 474 void
 475 circuit_unlink_all_from_or_conn(connection_t *conn, int reason)
 476 {
 477   circuit_t *circ;
 478   for (circ = global_circuitlist; circ; circ = circ->next) {
 479     if (circ->n_conn == conn || circ->p_conn == conn) {
 480       if (circ->n_conn == conn)
 481         circuit_set_circid_orconn(circ, 0, NULL, N_CONN_CHANGED);
 482       if (circ->p_conn == conn)
 483         circuit_set_circid_orconn(circ, 0, NULL, P_CONN_CHANGED);
 484       if (!circ->marked_for_close)
 485         circuit_mark_for_close(circ, reason);
 486     }
 487   }
 488 }
 489
 490 /** Return a circ such that:
 491  *  - circ-\>rend_query is equal to <b>rend_query</b>, and
 492  *  - circ-\>purpose is equal to <b>purpose</b>.
 493  *
 494  * Return NULL if no such circuit exists.
 495  */
 496 circuit_t *
 497 circuit_get_by_rend_query_and_purpose(const char *rend_query, uint8_t purpose)
 498 {
 499   circuit_t *circ;
 500
 501   for (circ = global_circuitlist; circ; circ = circ->next) {
 502     if (!circ->marked_for_close &&
 503         circ->purpose == purpose &&
 504         !rend_cmp_service_ids(rend_query, circ->rend_query))
 505       return circ;
 506   }
 507   return NULL;
 508 }
 509
 510 /** Return the first circuit in global_circuitlist after <b>start</b>
 511  * whose rend_pk_digest field is <b>digest</b> and whose purpose is
 512  * <b>purpose</b>. Returns NULL if no circuit is found.
 513  * If <b>start</b> is NULL, begin at the start of the list.
 514  */
 515 circuit_t *
 516 circuit_get_next_by_pk_and_purpose(circuit_t *start,
 517                                    const char *digest, uint8_t purpose)
 518 {
 519   circuit_t *circ;
 520   if (start == NULL)
 521     circ = global_circuitlist;
 522   else
 523     circ = start->next;
 524
 525   for ( ; circ; circ = circ->next) {
 526     if (circ->marked_for_close)
 527       continue;
 528     if (circ->purpose != purpose)
 529       continue;
 530     if (!memcmp(circ->rend_pk_digest, digest, DIGEST_LEN))
 531       return circ;
 532   }
 533   return NULL;
 534 }
 535
 536 /** Return the circuit waiting for a rendezvous with the provided cookie.
 537  * Return NULL if no such circuit is found.
 538  */
 539 circuit_t *
 540 circuit_get_rendezvous(const char *cookie)
 541 {
 542   circuit_t *circ;
 543   for (circ = global_circuitlist; circ; circ = circ->next) {
 544     if (! circ->marked_for_close &&
 545         circ->purpose == CIRCUIT_PURPOSE_REND_POINT_WAITING &&
 546         ! memcmp(circ->rend_cookie, cookie, REND_COOKIE_LEN) )
 547       return circ;
 548   }
 549   return NULL;
 550 }
 551
 552 /** Return a circuit that is open, has specified <b>purpose</b>,
 553  * has a timestamp_dirty value of 0, is uptime/capacity/internal
 554  * if required, and if info is defined, does not already use info
 555  * as any of its hops; or NULL if no circuit fits this description.
 556  *
 557  * Return need_uptime circuits if that is requested; and if it's not
 558  * requested, return non-uptime circuits if possible, else either.
 559  *
 560  * Only return internal circuits if that is requested.
 561  */
 562 circuit_t *
 563 circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info,
 564                             int need_uptime,
 565                             int need_capacity, int internal)
 566 {
 567   circuit_t *circ;
 568   circuit_t *best=NULL;
 569
 570   log_debug(LD_CIRC,
 571             "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
 572             "capacity %d, internal %d",
 573             purpose, need_uptime, need_capacity, internal);
 574
 575   for (circ=global_circuitlist; circ; circ = circ->next) {
 576     if (CIRCUIT_IS_ORIGIN(circ) &&
 577         circ->state == CIRCUIT_STATE_OPEN &&
 578         !circ->marked_for_close &&
 579         circ->purpose == purpose &&
 580         !circ->timestamp_dirty &&
 581         (!need_uptime || circ->build_state->need_uptime) &&
 582         (!need_capacity || circ->build_state->need_capacity) &&
 583         (internal == circ->build_state->is_internal)) {
 584       if (info) {
 585         /* need to make sure we don't duplicate hops */
 586         crypt_path_t *hop = circ->cpath;
 587         do {
 588           if (!memcmp(hop->extend_info->identity_digest,
 589                       info->identity_digest, DIGEST_LEN))
 590             goto next;
 591           hop=hop->next;
 592         } while (hop!=circ->cpath);
 593       }
 594       if (!best || (best->build_state->need_uptime && !need_uptime))
 595         best = circ;
 596       next: ;
 597     }
 598   }
 599   return best;
 600 }
 601
 602 /** Go through the circuitlist; mark-for-close each circuit that starts
 603  *  at us but has not yet been used. */
 604 void
 605 circuit_mark_all_unused_circs(void)
 606 {
 607   circuit_t *circ;
 608
 609   for (circ=global_circuitlist; circ; circ = circ->next) {
 610     if (CIRCUIT_IS_ORIGIN(circ) &&
 611         !circ->marked_for_close &&
 612         !circ->timestamp_dirty)
 613       circuit_mark_for_close(circ, END_CIRC_AT_ORIGIN);
 614   }
 615 }
 616
 617 /** Go through the circuitlist; for each circuit that starts at us
 618  * and is dirty, frob its timestamp_dirty so we won't use it for any
 619  * new streams.
 620  *
 621  * This is useful for letting the user change pseudonyms, so new
 622  * streams will not be linkable to old streams.
 623  */
 624 void
 625 circuit_expire_all_dirty_circs(void)
 626 {
 627   circuit_t *circ;
 628   or_options_t *options = get_options();
 629
 630   for (circ=global_circuitlist; circ; circ = circ->next) {
 631     if (CIRCUIT_IS_ORIGIN(circ) &&
 632         !circ->marked_for_close &&
 633         circ->timestamp_dirty)
 634       circ->timestamp_dirty -= options->MaxCircuitDirtiness;
 635   }
 636 }
 637
 638 /** Mark <b>circ</b> to be closed next time we call
 639  * circuit_close_all_marked(). Do any cleanup needed:
 640  *   - If state is onionskin_pending, remove circ from the onion_pending
 641  *     list.
 642  *   - If circ isn't open yet: call circuit_build_failed() if we're
 643  *     the origin, and in either case call circuit_rep_hist_note_result()
 644  *     to note stats.
 645  *   - If purpose is C_INTRODUCE_ACK_WAIT, remove the intro point we
 646  *     just tried from our list of intro points for that service
 647  *     descriptor.
 648  *   - Send appropriate destroys and edge_destroys for conns and
 649  *     streams attached to circ.
 650  *   - If circ->rend_splice is set (we are the midpoint of a joined
 651  *     rendezvous stream), then mark the other circuit to close as well.
 652  */
 653 void
 654 _circuit_mark_for_close(circuit_t *circ, int reason, int line,
 655                         const char *file)
 656 {
 657   connection_t *conn;
 658
 659   assert_circuit_ok(circ);
 660   tor_assert(line);
 661   tor_assert(file);
 662
 663   if (circ->marked_for_close) {
 664     log(LOG_WARN,LD_BUG,
 665         "Duplicate call to circuit_mark_for_close at %s:%d"
 666         " (first at %s:%d)", file, line,
 667         circ->marked_for_close_file, circ->marked_for_close);
 668     return;
 669   }
 670   if (reason == END_CIRC_AT_ORIGIN) {
 671     if (!CIRCUIT_IS_ORIGIN(circ)) {
 672       log_warn(LD_BUG, "Specified 'at-origin' non-reason for ending circuit, "
 673                "but circuit was not at origin. (called %s:%d, purpose=%d)",
 674                file, line, circ->purpose);
 675     }
 676     reason = END_CIRC_REASON_NONE;
 677   } else if (CIRCUIT_IS_ORIGIN(circ) && reason != END_CIRC_REASON_NONE) {
 678     /* Don't warn about this; there are plenty of places where our code
 679      * is origin-agnosic. */
 680     reason = END_CIRC_REASON_NONE;
 681   }
 682   if (reason < _END_CIRC_REASON_MIN || reason > _END_CIRC_REASON_MAX) {
 683     log_warn(LD_BUG, "Reason %d out of range at %s:%d", reason, file, line);
 684     reason = END_CIRC_REASON_NONE;
 685   }
 686
 687   if (circ->state == CIRCUIT_STATE_ONIONSKIN_PENDING) {
 688     onion_pending_remove(circ);
 689   }
 690   /* If the circuit ever became OPEN, we sent it to the reputation history
 691    * module then.  If it isn't OPEN, we send it there now to remember which
 692    * links worked and which didn't.
 693    */
 694   if (circ->state != CIRCUIT_STATE_OPEN) {
 695     if (CIRCUIT_IS_ORIGIN(circ)) {
 696       circuit_build_failed(circ); /* take actions if necessary */
 697     }
 698     circuit_rep_hist_note_result(circ);
 699   }
 700   if (circ->state == CIRCUIT_STATE_OR_WAIT) {
 701     if (circuits_pending_or_conns)
 702       smartlist_remove(circuits_pending_or_conns, circ);
 703   }
 704   if (CIRCUIT_IS_ORIGIN(circ)) {
 705     control_event_circuit_status(circ,
 706      (circ->state == CIRCUIT_STATE_OPEN)?CIRC_EVENT_CLOSED:CIRC_EVENT_FAILED);
 707   }
 708   if (circ->purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) {
 709     tor_assert(circ->state == CIRCUIT_STATE_OPEN);
 710     tor_assert(circ->build_state->chosen_exit);
 711     /* treat this like getting a nack from it */
 712     log_info(LD_REND, "Failed intro circ %s to %s (awaiting ack). "
 713              "Removing from descriptor.",
 714              safe_str(circ->rend_query),
 715              safe_str(build_state_get_exit_nickname(circ->build_state)));
 716     rend_client_remove_intro_point(circ->build_state->chosen_exit,
 717                                    circ->rend_query);
 718   }
 719
 720   if (circ->n_conn)
 721     connection_or_send_destroy(circ->n_circ_id, circ->n_conn, reason);
 722   for (conn=circ->n_streams; conn; conn=conn->next_stream)
 723     connection_edge_destroy(circ->n_circ_id, conn);
 724   while (circ->resolving_streams) {
 725     conn = circ->resolving_streams;
 726     circ->resolving_streams = conn->next_stream;
 727     if (!conn->marked_for_close) {
 728       /* The other side will see a DESTROY, and infer that the connections
 729        * are closing because the circuit is getting torn down.  No need
 730        * to send an end cell. */
 731       conn->has_sent_end = 1;
 732       connection_mark_for_close(conn);
 733     }
 734     conn->on_circuit = NULL;
 735   }
 736   if (circ->p_conn)
 737     connection_or_send_destroy(circ->p_circ_id, circ->p_conn, reason);
 738   for (conn=circ->p_streams; conn; conn=conn->next_stream)
 739     connection_edge_destroy(circ->p_circ_id, conn);
 740
 741   circ->marked_for_close = line;
 742   circ->marked_for_close_file = file;
 743
 744   if (circ->rend_splice) {
 745     if (!circ->rend_splice->marked_for_close) {
 746       /* do this after marking this circuit, to avoid infinite recursion. */
 747       circuit_mark_for_close(circ->rend_splice, reason);
 748     }
 749     circ->rend_splice = NULL;
 750   }
 751 }
 752
 753 /** Verify that cpath layer <b>cp</b> has all of its invariants
 754  * correct. Trigger an assert if anything is invalid.
 755  */
 756 void
 757 assert_cpath_layer_ok(const crypt_path_t *cp)
 758 {
 759 //  tor_assert(cp->addr); /* these are zero for rendezvous extra-hops */
 760 //  tor_assert(cp->port);
 761   tor_assert(cp);
 762   tor_assert(cp->magic == CRYPT_PATH_MAGIC);
 763   switch (cp->state)
 764     {
 765     case CPATH_STATE_OPEN:
 766       tor_assert(cp->f_crypto);
 767       tor_assert(cp->b_crypto);
 768       /* fall through */
 769     case CPATH_STATE_CLOSED:
 770       tor_assert(!cp->dh_handshake_state);
 771       break;
 772     case CPATH_STATE_AWAITING_KEYS:
 773       /* tor_assert(cp->dh_handshake_state); */
 774       break;
 775     default:
 776       log_fn(LOG_ERR, LD_BUG, "Unexpected state %d", cp->state);
 777       tor_assert(0);
 778     }
 779   tor_assert(cp->package_window >= 0);
 780   tor_assert(cp->deliver_window >= 0);
 781 }
 782
 783 /** Verify that cpath <b>cp</b> has all of its invariants
 784  * correct. Trigger an assert if anything is invalid.
 785  */
 786 static void
 787 assert_cpath_ok(const crypt_path_t *cp)
 788 {
 789   const crypt_path_t *start = cp;
 790
 791   do {
 792     assert_cpath_layer_ok(cp);
 793     /* layers must be in sequence of: "open* awaiting? closed*" */
 794     if (cp != start) {
 795       if (cp->state == CPATH_STATE_AWAITING_KEYS) {
 796         tor_assert(cp->prev->state == CPATH_STATE_OPEN);
 797       } else if (cp->state == CPATH_STATE_OPEN) {
 798         tor_assert(cp->prev->state == CPATH_STATE_OPEN);
 799       }
 800     }
 801     cp = cp->next;
 802     tor_assert(cp);
 803   } while (cp != start);
 804 }
 805
 806 /** Verify that circuit <b>c</b> has all of its invariants
 807  * correct. Trigger an assert if anything is invalid.
 808  */
 809 void
 810 assert_circuit_ok(const circuit_t *c)
 811 {
 812   connection_t *conn;
 813
 814   tor_assert(c);
 815   tor_assert(c->magic == CIRCUIT_MAGIC);
 816   tor_assert(c->purpose >= _CIRCUIT_PURPOSE_MIN &&
 817              c->purpose <= _CIRCUIT_PURPOSE_MAX);
 818
 819   if (c->n_conn) {
 820     tor_assert(c->n_conn->type == CONN_TYPE_OR);
 821     tor_assert(!memcmp(c->n_conn->identity_digest, c->n_conn_id_digest,
 822                        DIGEST_LEN));
 823     if (c->n_circ_id)
 824       tor_assert(c == circuit_get_by_circid_orconn(c->n_circ_id, c->n_conn));
 825   }
 826   if (c->p_conn) {
 827     tor_assert(c->p_conn->type == CONN_TYPE_OR);
 828     if (c->p_circ_id)
 829       tor_assert(c == circuit_get_by_circid_orconn(c->p_circ_id, c->p_conn));
 830   }
 831   for (conn = c->p_streams; conn; conn = conn->next_stream)
 832     tor_assert(conn->type == CONN_TYPE_AP);
 833   for (conn = c->n_streams; conn; conn = conn->next_stream)
 834     tor_assert(conn->type == CONN_TYPE_EXIT);
 835
 836   tor_assert(c->deliver_window >= 0);
 837   tor_assert(c->package_window >= 0);
 838   if (c->state == CIRCUIT_STATE_OPEN) {
 839     tor_assert(!c->onionskin);
 840     if (c->cpath) {
 841       tor_assert(CIRCUIT_IS_ORIGIN(c));
 842       tor_assert(!c->n_crypto);
 843       tor_assert(!c->p_crypto);
 844       tor_assert(!c->n_digest);
 845       tor_assert(!c->p_digest);
 846     } else {
 847       tor_assert(!CIRCUIT_IS_ORIGIN(c));
 848       tor_assert(c->n_crypto);
 849       tor_assert(c->p_crypto);
 850       tor_assert(c->n_digest);
 851       tor_assert(c->p_digest);
 852     }
 853   }
 854   if (c->state == CIRCUIT_STATE_OR_WAIT && !c->marked_for_close) {
 855     tor_assert(circuits_pending_or_conns &&
 856                smartlist_isin(circuits_pending_or_conns, c));
 857   } else {
 858     tor_assert(!circuits_pending_or_conns ||
 859                !smartlist_isin(circuits_pending_or_conns, c));
 860   }
 861   if (c->cpath) {
 862     assert_cpath_ok(c->cpath);
 863   }
 864   if (c->purpose == CIRCUIT_PURPOSE_REND_ESTABLISHED) {
 865     if (!c->marked_for_close) {
 866       tor_assert(c->rend_splice);
 867       tor_assert(c->rend_splice->rend_splice == c);
 868     }
 869     tor_assert(c->rend_splice != c);
 870   } else {
 871     tor_assert(!c->rend_splice);
 872   }
 873 }
 874