circuit.c 35 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128
  1. /* Copyright 2001,2002,2003 Roger Dingledine, Matej Pfajfar. */
  2. /* See LICENSE for licensing information */
  3. /* $Id$ */
  4. #include "or.h"
  5. extern or_options_t options; /* command-line and config-file options */
  6. static void circuit_free_cpath_node(crypt_path_t *victim);
  7. static circ_id_t get_unique_circ_id_by_conn(connection_t *conn, int circ_id_type);
  8. unsigned long stats_n_relay_cells_relayed = 0;
  9. unsigned long stats_n_relay_cells_delivered = 0;
  10. /********* START VARIABLES **********/
  11. static circuit_t *global_circuitlist=NULL;
  12. char *circuit_state_to_string[] = {
  13. "doing handshakes", /* 0 */
  14. "processing the onion", /* 1 */
  15. "connecting to firsthop", /* 2 */
  16. "open" /* 3 */
  17. };
  18. /********* END VARIABLES ************/
  19. void circuit_add(circuit_t *circ) {
  20. if(!global_circuitlist) { /* first one */
  21. global_circuitlist = circ;
  22. circ->next = NULL;
  23. } else {
  24. circ->next = global_circuitlist;
  25. global_circuitlist = circ;
  26. }
  27. }
  28. void circuit_remove(circuit_t *circ) {
  29. circuit_t *tmpcirc;
  30. assert(circ && global_circuitlist);
  31. if(global_circuitlist == circ) {
  32. global_circuitlist = global_circuitlist->next;
  33. return;
  34. }
  35. for(tmpcirc = global_circuitlist;tmpcirc->next;tmpcirc = tmpcirc->next) {
  36. if(tmpcirc->next == circ) {
  37. tmpcirc->next = circ->next;
  38. return;
  39. }
  40. }
  41. }
  42. circuit_t *circuit_new(circ_id_t p_circ_id, connection_t *p_conn) {
  43. circuit_t *circ;
  44. circ = tor_malloc_zero(sizeof(circuit_t));
  45. circ->timestamp_created = time(NULL);
  46. circ->p_circ_id = p_circ_id;
  47. circ->p_conn = p_conn;
  48. circ->state = CIRCUIT_STATE_ONIONSKIN_PENDING;
  49. /* CircIDs */
  50. circ->p_circ_id = p_circ_id;
  51. /* circ->n_circ_id remains 0 because we haven't identified the next hop yet */
  52. circ->package_window = CIRCWINDOW_START;
  53. circ->deliver_window = CIRCWINDOW_START;
  54. circuit_add(circ);
  55. return circ;
  56. }
  57. void circuit_free(circuit_t *circ) {
  58. assert(circ);
  59. if (circ->n_crypto)
  60. crypto_free_cipher_env(circ->n_crypto);
  61. if (circ->p_crypto)
  62. crypto_free_cipher_env(circ->p_crypto);
  63. if(circ->build_state)
  64. tor_free(circ->build_state->chosen_exit);
  65. tor_free(circ->build_state);
  66. circuit_free_cpath(circ->cpath);
  67. free(circ);
  68. }
  69. void circuit_free_cpath(crypt_path_t *cpath) {
  70. crypt_path_t *victim, *head=cpath;
  71. if(!cpath)
  72. return;
  73. /* it's a doubly linked list, so we have to notice when we've
  74. * gone through it once. */
  75. while(cpath->next && cpath->next != head) {
  76. victim = cpath;
  77. cpath = victim->next;
  78. circuit_free_cpath_node(victim);
  79. }
  80. circuit_free_cpath_node(cpath);
  81. }
  82. static void circuit_free_cpath_node(crypt_path_t *victim) {
  83. if(victim->f_crypto)
  84. crypto_free_cipher_env(victim->f_crypto);
  85. if(victim->b_crypto)
  86. crypto_free_cipher_env(victim->b_crypto);
  87. if(victim->handshake_state)
  88. crypto_dh_free(victim->handshake_state);
  89. free(victim);
  90. }
  91. /* return 0 if can't get a unique circ_id. */
  92. static circ_id_t get_unique_circ_id_by_conn(connection_t *conn, int circ_id_type) {
  93. circ_id_t test_circ_id;
  94. uint16_t high_bit;
  95. assert(conn && conn->type == CONN_TYPE_OR);
  96. high_bit = (circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
  97. do {
  98. /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find an
  99. * circID such that (high_bit|test_circ_id) is not already used. */
  100. /* XXX Will loop forever if all circ_id's in our range are used.
  101. * This matters because it's an external DoS vulnerability. */
  102. test_circ_id = conn->next_circ_id++;
  103. if (test_circ_id == 0 || test_circ_id >= 1<<15) {
  104. test_circ_id = 1;
  105. conn->next_circ_id = 2;
  106. }
  107. test_circ_id |= high_bit;
  108. } while(circuit_get_by_circ_id_conn(test_circ_id, conn));
  109. return test_circ_id;
  110. }
  111. circuit_t *circuit_get_by_circ_id_conn(circ_id_t circ_id, connection_t *conn) {
  112. circuit_t *circ;
  113. connection_t *tmpconn;
  114. for(circ=global_circuitlist;circ;circ = circ->next) {
  115. if(circ->p_circ_id == circ_id) {
  116. if(circ->p_conn == conn)
  117. return circ;
  118. for(tmpconn = circ->p_streams; tmpconn; tmpconn = tmpconn->next_stream) {
  119. if(tmpconn == conn)
  120. return circ;
  121. }
  122. }
  123. if(circ->n_circ_id == circ_id) {
  124. if(circ->n_conn == conn)
  125. return circ;
  126. for(tmpconn = circ->n_streams; tmpconn; tmpconn = tmpconn->next_stream) {
  127. if(tmpconn == conn)
  128. return circ;
  129. }
  130. }
  131. }
  132. return NULL;
  133. }
  134. circuit_t *circuit_get_by_conn(connection_t *conn) {
  135. circuit_t *circ;
  136. connection_t *tmpconn;
  137. for(circ=global_circuitlist;circ;circ = circ->next) {
  138. if(circ->p_conn == conn)
  139. return circ;
  140. if(circ->n_conn == conn)
  141. return circ;
  142. for(tmpconn = circ->p_streams; tmpconn; tmpconn=tmpconn->next_stream)
  143. if(tmpconn == conn)
  144. return circ;
  145. for(tmpconn = circ->n_streams; tmpconn; tmpconn=tmpconn->next_stream)
  146. if(tmpconn == conn)
  147. return circ;
  148. }
  149. return NULL;
  150. }
  151. /* Find the newest circ that conn can use, preferably one which is
  152. * dirty and not too old.
  153. * If !conn, return newest.
  154. *
  155. * If must_be_open, ignore circs not in CIRCUIT_STATE_OPEN.
  156. */
  157. circuit_t *circuit_get_newest(connection_t *conn, int must_be_open) {
  158. circuit_t *circ, *newest=NULL, *leastdirty=NULL;
  159. routerinfo_t *exitrouter;
  160. for(circ=global_circuitlist;circ;circ = circ->next) {
  161. if(!circ->cpath)
  162. continue; /* this circ doesn't start at us */
  163. if(must_be_open && (circ->state != CIRCUIT_STATE_OPEN || !circ->n_conn))
  164. continue; /* ignore non-open circs */
  165. if(conn) {
  166. if(circ->state == CIRCUIT_STATE_OPEN && circ->n_conn) /* open */
  167. exitrouter = router_get_by_addr_port(circ->cpath->prev->addr, circ->cpath->prev->port);
  168. else /* not open */
  169. exitrouter = router_get_by_nickname(circ->build_state->chosen_exit);
  170. if(!exitrouter || connection_ap_can_use_exit(conn, exitrouter) < 0) {
  171. /* can't exit from this router */
  172. continue;
  173. }
  174. }
  175. if(!newest || newest->timestamp_created < circ->timestamp_created) {
  176. newest = circ;
  177. }
  178. if(conn && circ->timestamp_dirty &&
  179. (!leastdirty || leastdirty->timestamp_dirty < circ->timestamp_dirty)) {
  180. leastdirty = circ;
  181. }
  182. }
  183. if(leastdirty &&
  184. leastdirty->timestamp_dirty+options.NewCircuitPeriod > time(NULL)) {
  185. /* log_fn(LOG_DEBUG,"Choosing in-use circuit %s:%d:%d.",
  186. leastdirty->n_conn->address, leastdirty->n_port, leastdirty->n_circ_id); */
  187. return leastdirty;
  188. }
  189. if(newest) {
  190. /* log_fn(LOG_DEBUG,"Choosing circuit %s:%d:%d.",
  191. newest->n_conn->address, newest->n_port, newest->n_circ_id); */
  192. return newest;
  193. }
  194. return NULL;
  195. }
  196. #define MIN_SECONDS_BEFORE_EXPIRING_CIRC 3
  197. /* circuits that were born at the end of their second might be expired
  198. * after 3.1 seconds; circuits born at the beginning might be expired
  199. * after closer to 4 seconds.
  200. */
  201. /* close all circuits that start at us, aren't open, and were born
  202. * at least MIN_SECONDS_BEFORE_EXPIRING_CIRC seconds ago */
  203. void circuit_expire_building(void) {
  204. int now = time(NULL);
  205. circuit_t *victim, *circ = global_circuitlist;
  206. while(circ) {
  207. victim = circ;
  208. circ = circ->next;
  209. if(victim->cpath &&
  210. victim->state != CIRCUIT_STATE_OPEN &&
  211. victim->timestamp_created + MIN_SECONDS_BEFORE_EXPIRING_CIRC+1 < now) {
  212. if(victim->n_conn)
  213. log_fn(LOG_INFO,"Abandoning circ %s:%d:%d (state %d:%s)",
  214. victim->n_conn->address, victim->n_port, victim->n_circ_id,
  215. victim->state, circuit_state_to_string[victim->state]);
  216. else
  217. log_fn(LOG_INFO,"Abandoning circ %d (state %d:%s)", victim->n_circ_id,
  218. victim->state, circuit_state_to_string[victim->state]);
  219. circuit_close(victim);
  220. }
  221. }
  222. }
  223. /* count the number of circs starting at us that aren't open */
  224. int circuit_count_building(void) {
  225. circuit_t *circ;
  226. int num=0;
  227. for(circ=global_circuitlist;circ;circ = circ->next) {
  228. if(circ->cpath && circ->state != CIRCUIT_STATE_OPEN)
  229. num++;
  230. }
  231. return num;
  232. }
  233. #define MIN_CIRCUITS_HANDLING_STREAM 2
  234. /* return 1 if at least MIN_CIRCUITS_HANDLING_STREAM non-open circuits
  235. * will have an acceptable exit node for conn. Else return 0.
  236. */
  237. int circuit_stream_is_being_handled(connection_t *conn) {
  238. circuit_t *circ;
  239. routerinfo_t *exitrouter;
  240. int num=0;
  241. for(circ=global_circuitlist;circ;circ = circ->next) {
  242. if(circ->cpath && circ->state != CIRCUIT_STATE_OPEN) {
  243. exitrouter = router_get_by_nickname(circ->build_state->chosen_exit);
  244. if(exitrouter && connection_ap_can_use_exit(conn, exitrouter) >= 0)
  245. if(++num >= MIN_CIRCUITS_HANDLING_STREAM)
  246. return 1;
  247. }
  248. }
  249. return 0;
  250. }
  251. int circuit_deliver_relay_cell(cell_t *cell, circuit_t *circ,
  252. int cell_direction, crypt_path_t *layer_hint) {
  253. connection_t *conn=NULL;
  254. char recognized=0;
  255. char buf[1+CELL_PAYLOAD_SIZE];
  256. assert(cell && circ);
  257. assert(cell_direction == CELL_DIRECTION_OUT || cell_direction == CELL_DIRECTION_IN);
  258. buf[0] = cell->length;
  259. memcpy(buf+1, cell->payload, CELL_PAYLOAD_SIZE);
  260. log_fn(LOG_DEBUG,"direction %d, streamid %d before crypt.", cell_direction, *(int*)(cell->payload+1));
  261. if(relay_crypt(circ, buf, 1+CELL_PAYLOAD_SIZE, cell_direction, &layer_hint, &recognized, &conn) < 0) {
  262. log_fn(LOG_WARN,"relay crypt failed. Dropping connection.");
  263. return -1;
  264. }
  265. cell->length = buf[0];
  266. memcpy(cell->payload, buf+1, CELL_PAYLOAD_SIZE);
  267. if(recognized) {
  268. if(cell_direction == CELL_DIRECTION_OUT) {
  269. ++stats_n_relay_cells_delivered;
  270. log_fn(LOG_DEBUG,"Sending to exit.");
  271. if (connection_edge_process_relay_cell(cell, circ, conn, EDGE_EXIT, NULL) < 0) {
  272. log_fn(LOG_WARN,"connection_edge_process_relay_cell (at exit) failed.");
  273. return -1;
  274. }
  275. }
  276. if(cell_direction == CELL_DIRECTION_IN) {
  277. ++stats_n_relay_cells_delivered;
  278. log_fn(LOG_DEBUG,"Sending to AP.");
  279. if (connection_edge_process_relay_cell(cell, circ, conn, EDGE_AP, layer_hint) < 0) {
  280. log_fn(LOG_WARN,"connection_edge_process_relay_cell (at AP) failed.");
  281. return -1;
  282. }
  283. }
  284. return 0;
  285. }
  286. /* not recognized. pass it on. */
  287. if(cell_direction == CELL_DIRECTION_OUT)
  288. conn = circ->n_conn;
  289. else
  290. conn = circ->p_conn;
  291. if(!conn) {
  292. log_fn(LOG_INFO,"Didn't recognize cell (%d), but circ stops here! Dropping.",
  293. *(int *)(cell->payload+1));
  294. return 0;
  295. }
  296. log_fn(LOG_DEBUG,"Passing on unrecognized cell.");
  297. ++stats_n_relay_cells_relayed;
  298. connection_or_write_cell_to_buf(cell, conn);
  299. return 0;
  300. }
  301. int relay_crypt(circuit_t *circ, char *in, int inlen, char cell_direction,
  302. crypt_path_t **layer_hint, char *recognized, connection_t **conn) {
  303. crypt_path_t *thishop;
  304. char out[256];
  305. assert(circ && in && recognized && conn);
  306. assert(inlen < 256);
  307. if(cell_direction == CELL_DIRECTION_IN) {
  308. if(circ->cpath) { /* we're at the beginning of the circuit. We'll want to do layered crypts. */
  309. thishop = circ->cpath;
  310. if(thishop->state != CPATH_STATE_OPEN) {
  311. log_fn(LOG_WARN,"Relay cell before first created cell?");
  312. return -1;
  313. }
  314. do { /* Remember: cpath is in forward order, that is, first hop first. */
  315. assert(thishop);
  316. log_fn(LOG_DEBUG,"before decrypt: %d",*(int*)(in+2));
  317. /* decrypt */
  318. if(crypto_cipher_decrypt(thishop->b_crypto, in, inlen, out)) {
  319. log_fn(LOG_WARN,"Error performing onion decryption: %s", crypto_perror());
  320. return -1;
  321. }
  322. memcpy(in,out,inlen);
  323. log_fn(LOG_DEBUG,"after decrypt: %d",*(int*)(in+2));
  324. if( (*recognized = relay_check_recognized(circ, cell_direction, in+2, conn))) {
  325. *layer_hint = thishop;
  326. return 0;
  327. }
  328. thishop = thishop->next;
  329. } while(thishop != circ->cpath && thishop->state == CPATH_STATE_OPEN);
  330. log_fn(LOG_INFO,"in-cell at OP not recognized. Dropping.");
  331. return 0;
  332. } else { /* we're in the middle. Just one crypt. */
  333. log_fn(LOG_DEBUG,"before encrypt: %d",*(int*)(in+2));
  334. if(crypto_cipher_encrypt(circ->p_crypto, in, inlen, out)) {
  335. log_fn(LOG_WARN,"Onion encryption failed for circID %u: %s",
  336. circ->p_circ_id, crypto_perror());
  337. return -1;
  338. }
  339. memcpy(in,out,inlen);
  340. log_fn(LOG_DEBUG,"after encrypt: %d",*(int*)(in+2));
  341. log_fn(LOG_DEBUG,"Skipping recognized check, because we're not the OP.");
  342. /* don't check for recognized. only the OP can recognize a stream on the way back. */
  343. }
  344. } else if(cell_direction == CELL_DIRECTION_OUT) {
  345. if(circ->cpath) { /* we're at the beginning of the circuit. We'll want to do layered crypts. */
  346. thishop = *layer_hint; /* we already know which layer, from when we package_raw_inbuf'ed */
  347. /* moving from last to first hop */
  348. do {
  349. assert(thishop);
  350. log_fn(LOG_DEBUG,"before encrypt: %d",*(int*)(in+2));
  351. if(crypto_cipher_encrypt(thishop->f_crypto, in, inlen, out)) {
  352. log_fn(LOG_WARN,"Error performing encryption: %s", crypto_perror());
  353. return -1;
  354. }
  355. memcpy(in,out,inlen);
  356. log_fn(LOG_DEBUG,"after encrypt: %d",*(int*)(in+2));
  357. thishop = thishop->prev;
  358. } while(thishop != circ->cpath->prev);
  359. } else { /* we're in the middle. Just one crypt. */
  360. if(crypto_cipher_decrypt(circ->n_crypto,in, inlen, out)) {
  361. log_fn(LOG_WARN,"Decryption failed for circID %u: %s",
  362. circ->n_circ_id, crypto_perror());
  363. return -1;
  364. }
  365. memcpy(in,out,inlen);
  366. if( (*recognized = relay_check_recognized(circ, cell_direction, in+2, conn)))
  367. return 0;
  368. }
  369. } else {
  370. log_fn(LOG_ERR,"unknown cell direction %d.", cell_direction);
  371. assert(0);
  372. }
  373. return 0;
  374. }
  375. int relay_check_recognized(circuit_t *circ, int cell_direction, char *stream, connection_t **conn) {
  376. /* FIXME can optimize by passing thishop in */
  377. connection_t *tmpconn;
  378. if(!memcmp(stream,ZERO_STREAM,STREAM_ID_SIZE)) {
  379. log_fn(LOG_DEBUG,"It's the zero stream. Recognized.");
  380. return 1; /* the zero stream is always recognized */
  381. }
  382. log_fn(LOG_DEBUG,"not the zero stream.");
  383. if(cell_direction == CELL_DIRECTION_OUT)
  384. tmpconn = circ->n_streams;
  385. else
  386. tmpconn = circ->p_streams;
  387. if(!tmpconn) {
  388. log_fn(LOG_DEBUG,"No conns. Not recognized.");
  389. return 0;
  390. }
  391. for( ; tmpconn; tmpconn=tmpconn->next_stream) {
  392. if(!memcmp(stream,tmpconn->stream_id, STREAM_ID_SIZE)) {
  393. log_fn(LOG_DEBUG,"recognized stream %d.", *(int*)stream);
  394. *conn = tmpconn;
  395. return 1;
  396. }
  397. log_fn(LOG_DEBUG,"considered stream %d, not it.",*(int*)tmpconn->stream_id);
  398. }
  399. log_fn(LOG_DEBUG,"Didn't recognize on this iteration of decryption.");
  400. return 0;
  401. }
  402. void circuit_resume_edge_reading(circuit_t *circ, int edge_type, crypt_path_t *layer_hint) {
  403. connection_t *conn;
  404. assert(edge_type == EDGE_EXIT || edge_type == EDGE_AP);
  405. log_fn(LOG_DEBUG,"resuming");
  406. if(edge_type == EDGE_EXIT)
  407. conn = circ->n_streams;
  408. else
  409. conn = circ->p_streams;
  410. for( ; conn; conn=conn->next_stream) {
  411. if((edge_type == EDGE_EXIT && conn->package_window > 0) ||
  412. (edge_type == EDGE_AP && conn->package_window > 0 && conn->cpath_layer == layer_hint)) {
  413. connection_start_reading(conn);
  414. connection_edge_package_raw_inbuf(conn); /* handle whatever might still be on the inbuf */
  415. /* If the circuit won't accept any more data, return without looking
  416. * at any more of the streams. Any connections that should be stopped
  417. * have already been stopped by connection_edge_package_raw_inbuf. */
  418. if(circuit_consider_stop_edge_reading(circ, edge_type, layer_hint))
  419. return;
  420. }
  421. }
  422. }
  423. /* returns 1 if the window is empty, else 0. If it's empty, tell edge conns to stop reading. */
  424. int circuit_consider_stop_edge_reading(circuit_t *circ, int edge_type, crypt_path_t *layer_hint) {
  425. connection_t *conn = NULL;
  426. assert(edge_type == EDGE_EXIT || edge_type == EDGE_AP);
  427. assert(edge_type == EDGE_EXIT || layer_hint);
  428. log_fn(LOG_DEBUG,"considering");
  429. if(edge_type == EDGE_EXIT && circ->package_window <= 0)
  430. conn = circ->n_streams;
  431. else if(edge_type == EDGE_AP && layer_hint->package_window <= 0)
  432. conn = circ->p_streams;
  433. else
  434. return 0;
  435. for( ; conn; conn=conn->next_stream)
  436. if(!layer_hint || conn->cpath_layer == layer_hint)
  437. connection_stop_reading(conn);
  438. log_fn(LOG_DEBUG,"yes. stopped.");
  439. return 1;
  440. }
  441. int circuit_consider_sending_sendme(circuit_t *circ, int edge_type, crypt_path_t *layer_hint) {
  442. cell_t cell;
  443. assert(circ);
  444. memset(&cell, 0, sizeof(cell_t));
  445. cell.command = CELL_RELAY;
  446. SET_CELL_RELAY_COMMAND(cell, RELAY_COMMAND_SENDME);
  447. SET_CELL_STREAM_ID(cell, ZERO_STREAM);
  448. cell.length = RELAY_HEADER_SIZE;
  449. if(edge_type == EDGE_AP) { /* i'm the AP */
  450. cell.circ_id = circ->n_circ_id;
  451. while(layer_hint->deliver_window < CIRCWINDOW_START-CIRCWINDOW_INCREMENT) {
  452. log_fn(LOG_DEBUG,"deliver_window %d, Queueing sendme forward.", layer_hint->deliver_window);
  453. layer_hint->deliver_window += CIRCWINDOW_INCREMENT;
  454. if(circuit_deliver_relay_cell(&cell, circ, CELL_DIRECTION_OUT, layer_hint) < 0) {
  455. log_fn(LOG_WARN,"At AP: circuit_deliver_relay_cell failed.");
  456. return -1;
  457. }
  458. }
  459. } else if(edge_type == EDGE_EXIT) { /* i'm the exit */
  460. cell.circ_id = circ->p_circ_id;
  461. while(circ->deliver_window < CIRCWINDOW_START-CIRCWINDOW_INCREMENT) {
  462. log_fn(LOG_DEBUG,"deliver_window %d, Queueing sendme back.", circ->deliver_window);
  463. circ->deliver_window += CIRCWINDOW_INCREMENT;
  464. if(circuit_deliver_relay_cell(&cell, circ, CELL_DIRECTION_IN, layer_hint) < 0) {
  465. log_fn(LOG_WARN,"At exit: circuit_deliver_relay_cell failed.");
  466. return -1;
  467. }
  468. }
  469. }
  470. return 0;
  471. }
  472. void circuit_close(circuit_t *circ) {
  473. connection_t *conn;
  474. assert(circ);
  475. circuit_remove(circ);
  476. if(circ->state == CIRCUIT_STATE_ONIONSKIN_PENDING) {
  477. onion_pending_remove(circ);
  478. }
  479. if(circ->n_conn)
  480. connection_send_destroy(circ->n_circ_id, circ->n_conn);
  481. for(conn=circ->n_streams; conn; conn=conn->next_stream) {
  482. connection_send_destroy(circ->n_circ_id, conn);
  483. }
  484. if(circ->p_conn)
  485. connection_send_destroy(circ->n_circ_id, circ->p_conn);
  486. for(conn=circ->p_streams; conn; conn=conn->next_stream) {
  487. connection_send_destroy(circ->p_circ_id, conn);
  488. }
  489. if (circ->state == CIRCUIT_STATE_BUILDING ||
  490. circ->state == CIRCUIT_STATE_OR_WAIT) {
  491. /* If we never built the circuit, note it as a failure. */
  492. circuit_increment_failure_count();
  493. }
  494. circuit_free(circ);
  495. }
  496. void circuit_about_to_close_connection(connection_t *conn) {
  497. /* send destroys for all circuits using conn */
  498. /* currently, we assume it's too late to flush conn's buf here.
  499. * down the road, maybe we'll consider that eof doesn't mean can't-write
  500. */
  501. circuit_t *circ;
  502. connection_t *prevconn;
  503. switch(conn->type) {
  504. case CONN_TYPE_OR:
  505. /* We must close all the circuits on it. */
  506. while((circ = circuit_get_by_conn(conn))) {
  507. if(circ->n_conn == conn) /* it's closing in front of us */
  508. circ->n_conn = NULL;
  509. if(circ->p_conn == conn) /* it's closing behind us */
  510. circ->p_conn = NULL;
  511. circuit_close(circ);
  512. }
  513. return;
  514. case CONN_TYPE_AP:
  515. case CONN_TYPE_EXIT:
  516. /* It's an edge conn. Need to remove it from the linked list of
  517. * conn's for this circuit. Confirm that 'end' relay command has
  518. * been sent. But don't kill the circuit.
  519. */
  520. circ = circuit_get_by_conn(conn);
  521. if(!circ)
  522. return;
  523. if(!conn->has_sent_end) {
  524. log_fn(LOG_INFO,"Edge connection hasn't sent end yet? Bug.");
  525. if(connection_edge_end(conn, END_STREAM_REASON_MISC, conn->cpath_layer) < 0)
  526. log_fn(LOG_WARN,"1: I called connection_edge_end redundantly.");
  527. }
  528. if(conn == circ->p_streams) {
  529. circ->p_streams = conn->next_stream;
  530. return;
  531. }
  532. if(conn == circ->n_streams) {
  533. circ->n_streams = conn->next_stream;
  534. return;
  535. }
  536. for(prevconn = circ->p_streams; prevconn && prevconn->next_stream && prevconn->next_stream != conn; prevconn = prevconn->next_stream) ;
  537. if(prevconn && prevconn->next_stream) {
  538. prevconn->next_stream = conn->next_stream;
  539. return;
  540. }
  541. for(prevconn = circ->n_streams; prevconn && prevconn->next_stream && prevconn->next_stream != conn; prevconn = prevconn->next_stream) ;
  542. if(prevconn && prevconn->next_stream) {
  543. prevconn->next_stream = conn->next_stream;
  544. return;
  545. }
  546. log_fn(LOG_ERR,"edge conn not in circuit's list?");
  547. assert(0); /* should never get here */
  548. } /* end switch */
  549. }
  550. void circuit_dump_details(int severity, circuit_t *circ, int poll_index,
  551. char *type, int this_circid, int other_circid) {
  552. struct crypt_path_t *hop;
  553. log(severity,"Conn %d has %s circuit: circID %d (other side %d), state %d (%s), born %d",
  554. poll_index, type, this_circid, other_circid, circ->state,
  555. circuit_state_to_string[circ->state], (int)circ->timestamp_created);
  556. if(circ->cpath) { /* circ starts at this node */
  557. if(circ->state == CIRCUIT_STATE_BUILDING)
  558. log(severity,"Building: desired len %d, planned exit node %s.",
  559. circ->build_state->desired_path_len, circ->build_state->chosen_exit);
  560. for(hop=circ->cpath;hop->next != circ->cpath; hop=hop->next)
  561. log(severity,"hop: state %d, addr %d, port %d", hop->state, hop->addr, hop->port);
  562. }
  563. }
  564. void circuit_dump_by_conn(connection_t *conn, int severity) {
  565. circuit_t *circ;
  566. connection_t *tmpconn;
  567. for(circ=global_circuitlist;circ;circ = circ->next) {
  568. if(circ->p_conn == conn)
  569. circuit_dump_details(severity, circ, conn->poll_index, "App-ward",
  570. circ->p_circ_id, circ->n_circ_id);
  571. for(tmpconn=circ->p_streams; tmpconn; tmpconn=tmpconn->next_stream) {
  572. if(tmpconn == conn) {
  573. circuit_dump_details(severity, circ, conn->poll_index, "App-ward",
  574. circ->p_circ_id, circ->n_circ_id);
  575. }
  576. }
  577. if(circ->n_conn == conn)
  578. circuit_dump_details(severity, circ, conn->poll_index, "Exit-ward",
  579. circ->n_circ_id, circ->p_circ_id);
  580. for(tmpconn=circ->n_streams; tmpconn; tmpconn=tmpconn->next_stream) {
  581. if(tmpconn == conn) {
  582. circuit_dump_details(severity, circ, conn->poll_index, "Exit-ward",
  583. circ->n_circ_id, circ->p_circ_id);
  584. }
  585. }
  586. }
  587. }
  588. void circuit_expire_unused_circuits(void) {
  589. circuit_t *circ, *tmpcirc;
  590. time_t now = time(NULL);
  591. circ = global_circuitlist;
  592. while(circ) {
  593. tmpcirc = circ;
  594. circ = circ->next;
  595. if(tmpcirc->timestamp_dirty &&
  596. tmpcirc->timestamp_dirty + options.NewCircuitPeriod < now &&
  597. !tmpcirc->p_conn && !tmpcirc->p_streams) {
  598. log_fn(LOG_DEBUG,"Closing n_circ_id %d",tmpcirc->n_circ_id);
  599. circuit_close(tmpcirc);
  600. }
  601. }
  602. }
  603. /* Number of consecutive failures so far; should only be touched by
  604. * circuit_launch_new and circuit_*_failure_count.
  605. */
  606. static int n_circuit_failures = 0;
  607. /* Return -1 if you aren't going to try to make a circuit, 0 if you did try. */
  608. int circuit_launch_new(void) {
  609. if(!options.SocksPort) /* we're not an application proxy. no need for circuits. */
  610. return -1;
  611. if(n_circuit_failures > 5) { /* too many failed circs in a row. don't try. */
  612. // log_fn(LOG_INFO,"%d failures so far, not trying.",n_circuit_failures);
  613. return -1;
  614. }
  615. /* try a circ. if it fails, circuit_close will increment n_circuit_failures */
  616. circuit_establish_circuit();
  617. return 0;
  618. }
  619. void circuit_increment_failure_count(void) {
  620. ++n_circuit_failures;
  621. log_fn(LOG_DEBUG,"n_circuit_failures now %d.",n_circuit_failures);
  622. }
  623. void circuit_reset_failure_count(void) {
  624. n_circuit_failures = 0;
  625. }
  626. int circuit_establish_circuit(void) {
  627. routerinfo_t *firsthop;
  628. connection_t *n_conn;
  629. circuit_t *circ;
  630. circ = circuit_new(0, NULL); /* sets circ->p_circ_id and circ->p_conn */
  631. circ->state = CIRCUIT_STATE_OR_WAIT;
  632. circ->build_state = onion_new_cpath_build_state();
  633. if (! circ->build_state) {
  634. log_fn(LOG_INFO,"Generating cpath length failed.");
  635. circuit_close(circ);
  636. return -1;
  637. }
  638. onion_extend_cpath(&circ->cpath, circ->build_state, &firsthop);
  639. if(!circ->cpath) {
  640. log_fn(LOG_INFO,"Generating first cpath hop failed.");
  641. circuit_close(circ);
  642. return -1;
  643. }
  644. /* now see if we're already connected to the first OR in 'route' */
  645. log_fn(LOG_DEBUG,"Looking for firsthop '%s:%u'",
  646. firsthop->address,firsthop->or_port);
  647. n_conn = connection_twin_get_by_addr_port(firsthop->addr,firsthop->or_port);
  648. if(!n_conn || n_conn->state != OR_CONN_STATE_OPEN) { /* not currently connected */
  649. circ->n_addr = firsthop->addr;
  650. circ->n_port = firsthop->or_port;
  651. if(options.ORPort) { /* we would be connected if he were up. and he's not. */
  652. log_fn(LOG_INFO,"Route's firsthop isn't connected.");
  653. circuit_close(circ);
  654. return -1;
  655. }
  656. if(!n_conn) { /* launch the connection */
  657. n_conn = connection_or_connect(firsthop);
  658. if(!n_conn) { /* connect failed, forget the whole thing */
  659. log_fn(LOG_INFO,"connect to firsthop failed. Closing.");
  660. circuit_close(circ);
  661. return -1;
  662. }
  663. }
  664. log_fn(LOG_DEBUG,"connecting in progress (or finished). Good.");
  665. return 0; /* return success. The onion/circuit/etc will be taken care of automatically
  666. * (may already have been) whenever n_conn reaches OR_CONN_STATE_OPEN.
  667. */
  668. } else { /* it (or a twin) is already open. use it. */
  669. circ->n_addr = n_conn->addr;
  670. circ->n_port = n_conn->port;
  671. circ->n_conn = n_conn;
  672. log_fn(LOG_DEBUG,"Conn open. Delivering first onion skin.");
  673. if(circuit_send_next_onion_skin(circ) < 0) {
  674. log_fn(LOG_INFO,"circuit_send_next_onion_skin failed.");
  675. circuit_close(circ);
  676. return -1;
  677. }
  678. }
  679. return 0;
  680. }
  681. /* find circuits that are waiting on me, if any, and get them to send the onion */
  682. void circuit_n_conn_open(connection_t *or_conn) {
  683. circuit_t *circ;
  684. for(circ=global_circuitlist;circ;circ = circ->next) {
  685. if(circ->cpath && circ->n_addr == or_conn->addr && circ->n_port == or_conn->port) {
  686. assert(circ->state == CIRCUIT_STATE_OR_WAIT);
  687. log_fn(LOG_DEBUG,"Found circ %d, sending onion skin.", circ->n_circ_id);
  688. circ->n_conn = or_conn;
  689. if(circuit_send_next_onion_skin(circ) < 0) {
  690. log_fn(LOG_INFO,"send_next_onion_skin failed; circuit marked for closing.");
  691. circuit_close(circ);
  692. continue;
  693. /* XXX could this be bad, eg if next_onion_skin failed because conn died? */
  694. }
  695. }
  696. }
  697. }
  698. int circuit_send_next_onion_skin(circuit_t *circ) {
  699. cell_t cell;
  700. crypt_path_t *hop;
  701. routerinfo_t *router;
  702. int r;
  703. int circ_id_type;
  704. assert(circ && circ->cpath);
  705. if(circ->cpath->state == CPATH_STATE_CLOSED) {
  706. assert(circ->n_conn && circ->n_conn->type == CONN_TYPE_OR);
  707. log_fn(LOG_DEBUG,"First skin; sending create cell.");
  708. circ_id_type = decide_circ_id_type(options.Nickname,
  709. circ->n_conn->nickname);
  710. circ->n_circ_id = get_unique_circ_id_by_conn(circ->n_conn, circ_id_type);
  711. memset(&cell, 0, sizeof(cell_t));
  712. cell.command = CELL_CREATE;
  713. cell.circ_id = circ->n_circ_id;
  714. cell.length = DH_ONIONSKIN_LEN;
  715. if(onion_skin_create(circ->n_conn->onion_pkey, &(circ->cpath->handshake_state), cell.payload) < 0) {
  716. log_fn(LOG_WARN,"onion_skin_create (first hop) failed.");
  717. return -1;
  718. }
  719. connection_or_write_cell_to_buf(&cell, circ->n_conn);
  720. circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
  721. circ->state = CIRCUIT_STATE_BUILDING;
  722. log_fn(LOG_DEBUG,"first skin; finished sending create cell.");
  723. } else {
  724. assert(circ->cpath->state == CPATH_STATE_OPEN);
  725. assert(circ->state == CIRCUIT_STATE_BUILDING);
  726. log_fn(LOG_DEBUG,"starting to send subsequent skin.");
  727. r = onion_extend_cpath(&circ->cpath, circ->build_state, &router);
  728. if (r==1) {
  729. /* done building the circuit. whew. */
  730. circ->state = CIRCUIT_STATE_OPEN;
  731. log_fn(LOG_INFO,"circuit built!");
  732. circuit_reset_failure_count();
  733. /* Tell any AP connections that have been waiting for a new
  734. * circuit that one is ready. */
  735. connection_ap_attach_pending();
  736. return 0;
  737. } else if (r<0) {
  738. log_fn(LOG_INFO,"Unable to extend circuit path.");
  739. return -1;
  740. }
  741. hop = circ->cpath->prev;
  742. memset(&cell, 0, sizeof(cell_t));
  743. cell.command = CELL_RELAY;
  744. cell.circ_id = circ->n_circ_id;
  745. SET_CELL_RELAY_COMMAND(cell, RELAY_COMMAND_EXTEND);
  746. SET_CELL_STREAM_ID(cell, ZERO_STREAM);
  747. cell.length = RELAY_HEADER_SIZE + 6 + DH_ONIONSKIN_LEN;
  748. *(uint32_t*)(cell.payload+RELAY_HEADER_SIZE) = htonl(hop->addr);
  749. *(uint16_t*)(cell.payload+RELAY_HEADER_SIZE+4) = htons(hop->port);
  750. if(onion_skin_create(router->onion_pkey, &(hop->handshake_state), cell.payload+RELAY_HEADER_SIZE+6) < 0) {
  751. log_fn(LOG_WARN,"onion_skin_create failed.");
  752. return -1;
  753. }
  754. log_fn(LOG_DEBUG,"Sending extend relay cell.");
  755. /* send it to hop->prev, because it will transfer it to a create cell and then send to hop */
  756. if(circuit_deliver_relay_cell(&cell, circ, CELL_DIRECTION_OUT, hop->prev) < 0) {
  757. log_fn(LOG_WARN,"failed to deliver extend cell. Closing.");
  758. return -1;
  759. }
  760. hop->state = CPATH_STATE_AWAITING_KEYS;
  761. }
  762. return 0;
  763. }
  764. /* take the 'extend' cell, pull out addr/port plus the onion skin. Make
  765. * sure we're connected to the next hop, and pass it the onion skin in
  766. * a create cell.
  767. */
  768. int circuit_extend(cell_t *cell, circuit_t *circ) {
  769. connection_t *n_conn;
  770. int circ_id_type;
  771. cell_t newcell;
  772. if(circ->n_conn) {
  773. log_fn(LOG_WARN,"n_conn already set. Bug/attack. Closing.");
  774. return -1;
  775. }
  776. circ->n_addr = ntohl(*(uint32_t*)(cell->payload+RELAY_HEADER_SIZE));
  777. circ->n_port = ntohs(*(uint16_t*)(cell->payload+RELAY_HEADER_SIZE+4));
  778. n_conn = connection_twin_get_by_addr_port(circ->n_addr,circ->n_port);
  779. if(!n_conn || n_conn->type != CONN_TYPE_OR) {
  780. /* i've disabled making connections through OPs, but it's definitely
  781. * possible here. I'm not sure if it would be a bug or a feature. -RD
  782. */
  783. /* note also that this will close circuits where the onion has the same
  784. * router twice in a row in the path. i think that's ok. -RD
  785. */
  786. struct in_addr in;
  787. in.s_addr = htonl(circ->n_addr);
  788. log_fn(LOG_INFO,"Next router (%s:%d) not connected. Closing.", inet_ntoa(in), circ->n_port);
  789. connection_edge_send_command(NULL, circ, RELAY_COMMAND_TRUNCATED,
  790. NULL, 0, NULL);
  791. return 0;
  792. }
  793. circ->n_addr = n_conn->addr; /* these are different if we found a twin instead */
  794. circ->n_port = n_conn->port;
  795. circ->n_conn = n_conn;
  796. log_fn(LOG_DEBUG,"n_conn is %s:%u",n_conn->address,n_conn->port);
  797. circ_id_type = decide_circ_id_type(options.Nickname, n_conn->nickname);
  798. log_fn(LOG_DEBUG,"circ_id_type = %u.",circ_id_type);
  799. circ->n_circ_id = get_unique_circ_id_by_conn(circ->n_conn, circ_id_type);
  800. if(!circ->n_circ_id) {
  801. log_fn(LOG_WARN,"failed to get unique circID.");
  802. return -1;
  803. }
  804. log_fn(LOG_DEBUG,"Chosen circID %u.",circ->n_circ_id);
  805. memset(&newcell, 0, sizeof(cell_t));
  806. newcell.command = CELL_CREATE;
  807. newcell.circ_id = circ->n_circ_id;
  808. newcell.length = DH_ONIONSKIN_LEN;
  809. memcpy(newcell.payload, cell->payload+RELAY_HEADER_SIZE+6, DH_ONIONSKIN_LEN);
  810. connection_or_write_cell_to_buf(&newcell, circ->n_conn);
  811. return 0;
  812. }
  813. int circuit_finish_handshake(circuit_t *circ, char *reply) {
  814. unsigned char iv[16];
  815. unsigned char keys[32];
  816. crypt_path_t *hop;
  817. memset(iv, 0, 16);
  818. assert(circ->cpath);
  819. if(circ->cpath->state == CPATH_STATE_AWAITING_KEYS)
  820. hop = circ->cpath;
  821. else {
  822. for(hop=circ->cpath->next;
  823. hop != circ->cpath && hop->state == CPATH_STATE_OPEN;
  824. hop=hop->next) ;
  825. if(hop == circ->cpath) { /* got an extended when we're all done? */
  826. log_fn(LOG_WARN,"got extended when circ already built? Closing.");
  827. return -1;
  828. }
  829. }
  830. assert(hop->state == CPATH_STATE_AWAITING_KEYS);
  831. if(onion_skin_client_handshake(hop->handshake_state, reply, keys, 32) < 0) {
  832. log_fn(LOG_WARN,"onion_skin_client_handshake failed.");
  833. return -1;
  834. }
  835. crypto_dh_free(hop->handshake_state); /* don't need it anymore */
  836. hop->handshake_state = NULL;
  837. log_fn(LOG_DEBUG,"hop %d init cipher forward %d, backward %d.", (uint32_t)hop, *(uint32_t*)keys, *(uint32_t*)(keys+16));
  838. if (!(hop->f_crypto =
  839. crypto_create_init_cipher(CIRCUIT_CIPHER,keys,iv,1))) {
  840. log(LOG_WARN,"forward cipher initialization failed.");
  841. return -1;
  842. }
  843. if (!(hop->b_crypto =
  844. crypto_create_init_cipher(CIRCUIT_CIPHER,keys+16,iv,0))) {
  845. log(LOG_WARN,"backward cipher initialization failed.");
  846. return -1;
  847. }
  848. hop->state = CPATH_STATE_OPEN;
  849. log_fn(LOG_INFO,"finished");
  850. return 0;
  851. }
  852. int circuit_truncated(circuit_t *circ, crypt_path_t *layer) {
  853. crypt_path_t *victim;
  854. connection_t *stream;
  855. assert(circ);
  856. assert(layer);
  857. /* XXX Since we don't ask for truncates currently, getting a truncated
  858. * means that a connection broke or an extend failed. For now,
  859. * just give up.
  860. */
  861. circuit_close(circ);
  862. return 0;
  863. while(layer->next != circ->cpath) {
  864. /* we need to clear out layer->next */
  865. victim = layer->next;
  866. log_fn(LOG_DEBUG, "Killing a layer of the cpath.");
  867. for(stream = circ->p_streams; stream; stream=stream->next_stream) {
  868. if(stream->cpath_layer == victim) {
  869. log_fn(LOG_INFO, "Marking stream %d for close.", *(int*)stream->stream_id);
  870. /* no need to send 'end' relay cells,
  871. * because the other side's already dead
  872. */
  873. stream->marked_for_close = 1;
  874. stream->has_sent_end = 1;
  875. }
  876. }
  877. layer->next = victim->next;
  878. circuit_free_cpath_node(victim);
  879. }
  880. log_fn(LOG_INFO, "finished");
  881. return 0;
  882. }
  883. void assert_cpath_layer_ok(const crypt_path_t *cp)
  884. {
  885. assert(cp->f_crypto);
  886. assert(cp->b_crypto);
  887. assert(cp->addr);
  888. assert(cp->port);
  889. switch(cp->state)
  890. {
  891. case CPATH_STATE_CLOSED:
  892. case CPATH_STATE_OPEN:
  893. assert(!cp->handshake_state);
  894. break;
  895. case CPATH_STATE_AWAITING_KEYS:
  896. assert(cp->handshake_state);
  897. break;
  898. default:
  899. assert(0);
  900. }
  901. assert(cp->package_window >= 0);
  902. assert(cp->deliver_window >= 0);
  903. }
  904. void assert_cpath_ok(const crypt_path_t *cp)
  905. {
  906. while(cp->prev)
  907. cp = cp->prev;
  908. while(cp->next) {
  909. assert_cpath_layer_ok(cp);
  910. /* layers must be in sequence of: "open* awaiting? closed*" */
  911. if (cp->prev) {
  912. if (cp->prev->state == CPATH_STATE_OPEN) {
  913. assert(cp->state == CPATH_STATE_CLOSED ||
  914. cp->state == CPATH_STATE_AWAITING_KEYS);
  915. } else {
  916. assert(cp->state == CPATH_STATE_CLOSED);
  917. }
  918. }
  919. cp = cp->next;
  920. }
  921. }
  922. void assert_circuit_ok(const circuit_t *c)
  923. {
  924. connection_t *conn;
  925. assert(c->n_addr);
  926. assert(c->n_port);
  927. assert(c->n_conn);
  928. assert(c->n_conn->type == CONN_TYPE_OR);
  929. if (c->p_conn)
  930. assert(c->p_conn->type == CONN_TYPE_OR);
  931. for (conn = c->p_streams; conn; conn = conn->next_stream)
  932. assert(c->p_conn->type == CONN_TYPE_EXIT);
  933. for (conn = c->n_streams; conn; conn = conn->next_stream)
  934. assert(conn->type == CONN_TYPE_EXIT);
  935. assert(c->deliver_window >= 0);
  936. assert(c->package_window >= 0);
  937. if (c->state == CIRCUIT_STATE_OPEN) {
  938. if (c->cpath) {
  939. assert(!c->n_crypto);
  940. assert(!c->p_crypto);
  941. } else {
  942. assert(c->n_crypto);
  943. assert(c->p_crypto);
  944. }
  945. }
  946. if (c->cpath) {
  947. assert_cpath_ok(c->cpath);
  948. }
  949. }
  950. /*
  951. Local Variables:
  952. mode:c
  953. indent-tabs-mode:nil
  954. c-basic-offset:2
  955. End:
  956. */