circuitbuild.c 81 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413
  1. /* Copyright (c) 2001 Matej Pfajfar.
  2. * Copyright (c) 2001-2004, Roger Dingledine.
  3. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  4. * Copyright (c) 2007-2012, The Tor Project, Inc. */
  5. /* See LICENSE for licensing information */
  6. /**
  7. * \file circuitbuild.c
  8. * \brief The actual details of building circuits.
  9. **/
  10. #include "or.h"
  11. #include "channel.h"
  12. #include "circuitbuild.h"
  13. #include "circuitlist.h"
  14. #include "circuitstats.h"
  15. #include "circuituse.h"
  16. #include "command.h"
  17. #include "config.h"
  18. #include "confparse.h"
  19. #include "connection.h"
  20. #include "connection_edge.h"
  21. #include "connection_or.h"
  22. #include "control.h"
  23. #include "directory.h"
  24. #include "entrynodes.h"
  25. #include "main.h"
  26. #include "networkstatus.h"
  27. #include "nodelist.h"
  28. #include "onion.h"
  29. #include "onion_tap.h"
  30. #include "onion_fast.h"
  31. #include "policies.h"
  32. #include "transports.h"
  33. #include "relay.h"
  34. #include "rephist.h"
  35. #include "router.h"
  36. #include "routerlist.h"
  37. #include "routerparse.h"
  38. #include "routerset.h"
  39. #include "crypto.h"
  40. #ifndef MIN
  41. #define MIN(a,b) ((a)<(b)?(a):(b))
  42. #endif
  43. /********* START VARIABLES **********/
  44. /** A global list of all circuits at this hop. */
  45. extern circuit_t *global_circuitlist;
  46. /********* END VARIABLES ************/
  47. static channel_t * channel_connect_for_circuit(const tor_addr_t *addr,
  48. uint16_t port,
  49. const char *id_digest);
  50. static int circuit_deliver_create_cell(circuit_t *circ,
  51. const create_cell_t *create_cell);
  52. static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
  53. static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
  54. static int onion_extend_cpath(origin_circuit_t *circ);
  55. static int count_acceptable_nodes(smartlist_t *routers);
  56. static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
  57. static int entry_guard_inc_first_hop_count(entry_guard_t *guard);
  58. static void pathbias_count_success(origin_circuit_t *circ);
  59. /** This function tries to get a channel to the specified endpoint,
  60. * and then calls command_setup_channel() to give it the right
  61. * callbacks.
  62. */
  63. static channel_t *
  64. channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port,
  65. const char *id_digest)
  66. {
  67. channel_t *chan;
  68. chan = channel_connect(addr, port, id_digest);
  69. if (chan) command_setup_channel(chan);
  70. return chan;
  71. }
  72. /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
  73. * and with the high bit specified by conn-\>circ_id_type, until we get
  74. * a circ_id that is not in use by any other circuit on that conn.
  75. *
  76. * Return it, or 0 if can't get a unique circ_id.
  77. */
  78. static circid_t
  79. get_unique_circ_id_by_chan(channel_t *chan)
  80. {
  81. circid_t test_circ_id;
  82. circid_t attempts=0;
  83. circid_t high_bit;
  84. tor_assert(chan);
  85. if (chan->circ_id_type == CIRC_ID_TYPE_NEITHER) {
  86. log_warn(LD_BUG,
  87. "Trying to pick a circuit ID for a connection from "
  88. "a client with no identity.");
  89. return 0;
  90. }
  91. high_bit =
  92. (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
  93. do {
  94. /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
  95. * circID such that (high_bit|test_circ_id) is not already used. */
  96. test_circ_id = chan->next_circ_id++;
  97. if (test_circ_id == 0 || test_circ_id >= 1<<15) {
  98. test_circ_id = 1;
  99. chan->next_circ_id = 2;
  100. }
  101. if (++attempts > 1<<15) {
  102. /* Make sure we don't loop forever if all circ_id's are used. This
  103. * matters because it's an external DoS opportunity.
  104. */
  105. log_warn(LD_CIRC,"No unused circ IDs. Failing.");
  106. return 0;
  107. }
  108. test_circ_id |= high_bit;
  109. } while (circuit_id_in_use_on_channel(test_circ_id, chan));
  110. return test_circ_id;
  111. }
  112. /** If <b>verbose</b> is false, allocate and return a comma-separated list of
  113. * the currently built elements of <b>circ</b>. If <b>verbose</b> is true, also
  114. * list information about link status in a more verbose format using spaces.
  115. * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
  116. * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
  117. * names.
  118. */
  119. static char *
  120. circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
  121. {
  122. crypt_path_t *hop;
  123. smartlist_t *elements;
  124. const char *states[] = {"closed", "waiting for keys", "open"};
  125. char *s;
  126. elements = smartlist_new();
  127. if (verbose) {
  128. const char *nickname = build_state_get_exit_nickname(circ->build_state);
  129. smartlist_add_asprintf(elements, "%s%s circ (length %d%s%s):",
  130. circ->build_state->is_internal ? "internal" : "exit",
  131. circ->build_state->need_uptime ? " (high-uptime)" : "",
  132. circ->build_state->desired_path_len,
  133. circ->base_.state == CIRCUIT_STATE_OPEN ? "" : ", last hop ",
  134. circ->base_.state == CIRCUIT_STATE_OPEN ? "" :
  135. (nickname?nickname:"*unnamed*"));
  136. }
  137. hop = circ->cpath;
  138. do {
  139. char *elt;
  140. const char *id;
  141. const node_t *node;
  142. if (!hop)
  143. break;
  144. if (!verbose && hop->state != CPATH_STATE_OPEN)
  145. break;
  146. if (!hop->extend_info)
  147. break;
  148. id = hop->extend_info->identity_digest;
  149. if (verbose_names) {
  150. elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1);
  151. if ((node = node_get_by_id(id))) {
  152. node_get_verbose_nickname(node, elt);
  153. } else if (is_legal_nickname(hop->extend_info->nickname)) {
  154. elt[0] = '$';
  155. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  156. elt[HEX_DIGEST_LEN+1]= '~';
  157. strlcpy(elt+HEX_DIGEST_LEN+2,
  158. hop->extend_info->nickname, MAX_NICKNAME_LEN+1);
  159. } else {
  160. elt[0] = '$';
  161. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  162. }
  163. } else { /* ! verbose_names */
  164. node = node_get_by_id(id);
  165. if (node && node_is_named(node)) {
  166. elt = tor_strdup(node_get_nickname(node));
  167. } else {
  168. elt = tor_malloc(HEX_DIGEST_LEN+2);
  169. elt[0] = '$';
  170. base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  171. }
  172. }
  173. tor_assert(elt);
  174. if (verbose) {
  175. tor_assert(hop->state <= 2);
  176. smartlist_add_asprintf(elements,"%s(%s)",elt,states[hop->state]);
  177. tor_free(elt);
  178. } else {
  179. smartlist_add(elements, elt);
  180. }
  181. hop = hop->next;
  182. } while (hop != circ->cpath);
  183. s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
  184. SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  185. smartlist_free(elements);
  186. return s;
  187. }
  188. /** If <b>verbose</b> is false, allocate and return a comma-separated
  189. * list of the currently built elements of <b>circ</b>. If
  190. * <b>verbose</b> is true, also list information about link status in
  191. * a more verbose format using spaces.
  192. */
  193. char *
  194. circuit_list_path(origin_circuit_t *circ, int verbose)
  195. {
  196. return circuit_list_path_impl(circ, verbose, 0);
  197. }
  198. /** Allocate and return a comma-separated list of the currently built elements
  199. * of <b>circ</b>, giving each as a verbose nickname.
  200. */
  201. char *
  202. circuit_list_path_for_controller(origin_circuit_t *circ)
  203. {
  204. return circuit_list_path_impl(circ, 0, 1);
  205. }
  206. /** Log, at severity <b>severity</b>, the nicknames of each router in
  207. * <b>circ</b>'s cpath. Also log the length of the cpath, and the intended
  208. * exit point.
  209. */
  210. void
  211. circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
  212. {
  213. char *s = circuit_list_path(circ,1);
  214. tor_log(severity,domain,"%s",s);
  215. tor_free(s);
  216. }
  217. /** Tell the rep(utation)hist(ory) module about the status of the links
  218. * in <b>circ</b>. Hops that have become OPEN are marked as successfully
  219. * extended; the _first_ hop that isn't open (if any) is marked as
  220. * unable to extend.
  221. */
  222. /* XXXX Someday we should learn from OR circuits too. */
  223. void
  224. circuit_rep_hist_note_result(origin_circuit_t *circ)
  225. {
  226. crypt_path_t *hop;
  227. const char *prev_digest = NULL;
  228. hop = circ->cpath;
  229. if (!hop) /* circuit hasn't started building yet. */
  230. return;
  231. if (server_mode(get_options())) {
  232. const routerinfo_t *me = router_get_my_routerinfo();
  233. if (!me)
  234. return;
  235. prev_digest = me->cache_info.identity_digest;
  236. }
  237. do {
  238. const node_t *node = node_get_by_id(hop->extend_info->identity_digest);
  239. if (node) { /* Why do we check this? We know the identity. -NM XXXX */
  240. if (prev_digest) {
  241. if (hop->state == CPATH_STATE_OPEN)
  242. rep_hist_note_extend_succeeded(prev_digest, node->identity);
  243. else {
  244. rep_hist_note_extend_failed(prev_digest, node->identity);
  245. break;
  246. }
  247. }
  248. prev_digest = node->identity;
  249. } else {
  250. prev_digest = NULL;
  251. }
  252. hop=hop->next;
  253. } while (hop!=circ->cpath);
  254. }
  255. /** Pick all the entries in our cpath. Stop and return 0 when we're
  256. * happy, or return -1 if an error occurs. */
  257. static int
  258. onion_populate_cpath(origin_circuit_t *circ)
  259. {
  260. int r;
  261. again:
  262. r = onion_extend_cpath(circ);
  263. if (r < 0) {
  264. log_info(LD_CIRC,"Generating cpath hop failed.");
  265. return -1;
  266. }
  267. if (r == 0)
  268. goto again;
  269. return 0; /* if r == 1 */
  270. }
  271. /** Create and return a new origin circuit. Initialize its purpose and
  272. * build-state based on our arguments. The <b>flags</b> argument is a
  273. * bitfield of CIRCLAUNCH_* flags. */
  274. origin_circuit_t *
  275. origin_circuit_init(uint8_t purpose, int flags)
  276. {
  277. /* sets circ->p_circ_id and circ->p_chan */
  278. origin_circuit_t *circ = origin_circuit_new();
  279. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_CHAN_WAIT);
  280. circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
  281. circ->build_state->onehop_tunnel =
  282. ((flags & CIRCLAUNCH_ONEHOP_TUNNEL) ? 1 : 0);
  283. circ->build_state->need_uptime =
  284. ((flags & CIRCLAUNCH_NEED_UPTIME) ? 1 : 0);
  285. circ->build_state->need_capacity =
  286. ((flags & CIRCLAUNCH_NEED_CAPACITY) ? 1 : 0);
  287. circ->build_state->is_internal =
  288. ((flags & CIRCLAUNCH_IS_INTERNAL) ? 1 : 0);
  289. circ->base_.purpose = purpose;
  290. return circ;
  291. }
  292. /** Build a new circuit for <b>purpose</b>. If <b>exit</b>
  293. * is defined, then use that as your exit router, else choose a suitable
  294. * exit node.
  295. *
  296. * Also launch a connection to the first OR in the chosen path, if
  297. * it's not open already.
  298. */
  299. origin_circuit_t *
  300. circuit_establish_circuit(uint8_t purpose, extend_info_t *exit, int flags)
  301. {
  302. origin_circuit_t *circ;
  303. int err_reason = 0;
  304. circ = origin_circuit_init(purpose, flags);
  305. if (onion_pick_cpath_exit(circ, exit) < 0 ||
  306. onion_populate_cpath(circ) < 0) {
  307. circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
  308. return NULL;
  309. }
  310. control_event_circuit_status(circ, CIRC_EVENT_LAUNCHED, 0);
  311. if ((err_reason = circuit_handle_first_hop(circ)) < 0) {
  312. circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
  313. return NULL;
  314. }
  315. return circ;
  316. }
  317. /** Start establishing the first hop of our circuit. Figure out what
  318. * OR we should connect to, and if necessary start the connection to
  319. * it. If we're already connected, then send the 'create' cell.
  320. * Return 0 for ok, -reason if circ should be marked-for-close. */
  321. int
  322. circuit_handle_first_hop(origin_circuit_t *circ)
  323. {
  324. crypt_path_t *firsthop;
  325. channel_t *n_chan;
  326. int err_reason = 0;
  327. const char *msg = NULL;
  328. int should_launch = 0;
  329. firsthop = onion_next_hop_in_cpath(circ->cpath);
  330. tor_assert(firsthop);
  331. tor_assert(firsthop->extend_info);
  332. /* now see if we're already connected to the first OR in 'route' */
  333. log_debug(LD_CIRC,"Looking for firsthop '%s'",
  334. fmt_addrport(&firsthop->extend_info->addr,
  335. firsthop->extend_info->port));
  336. n_chan = channel_get_for_extend(firsthop->extend_info->identity_digest,
  337. &firsthop->extend_info->addr,
  338. &msg,
  339. &should_launch);
  340. if (!n_chan) {
  341. /* not currently connected in a useful way. */
  342. log_info(LD_CIRC, "Next router is %s: %s",
  343. safe_str_client(extend_info_describe(firsthop->extend_info)),
  344. msg?msg:"???");
  345. circ->base_.n_hop = extend_info_dup(firsthop->extend_info);
  346. if (should_launch) {
  347. if (circ->build_state->onehop_tunnel)
  348. control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR, 0);
  349. n_chan = channel_connect_for_circuit(
  350. &firsthop->extend_info->addr,
  351. firsthop->extend_info->port,
  352. firsthop->extend_info->identity_digest);
  353. if (!n_chan) { /* connect failed, forget the whole thing */
  354. log_info(LD_CIRC,"connect to firsthop failed. Closing.");
  355. return -END_CIRC_REASON_CONNECTFAILED;
  356. }
  357. }
  358. log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
  359. /* return success. The onion/circuit/etc will be taken care of
  360. * automatically (may already have been) whenever n_chan reaches
  361. * OR_CONN_STATE_OPEN.
  362. */
  363. return 0;
  364. } else { /* it's already open. use it. */
  365. tor_assert(!circ->base_.n_hop);
  366. circ->base_.n_chan = n_chan;
  367. log_debug(LD_CIRC,"Conn open. Delivering first onion skin.");
  368. if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) {
  369. log_info(LD_CIRC,"circuit_send_next_onion_skin failed.");
  370. return err_reason;
  371. }
  372. }
  373. return 0;
  374. }
  375. /** Find any circuits that are waiting on <b>or_conn</b> to become
  376. * open and get them to send their create cells forward.
  377. *
  378. * Status is 1 if connect succeeded, or 0 if connect failed.
  379. */
  380. void
  381. circuit_n_chan_done(channel_t *chan, int status)
  382. {
  383. smartlist_t *pending_circs;
  384. int err_reason = 0;
  385. tor_assert(chan);
  386. log_debug(LD_CIRC,"chan to %s/%s, status=%d",
  387. chan->nickname ? chan->nickname : "NULL",
  388. channel_get_canonical_remote_descr(chan), status);
  389. pending_circs = smartlist_new();
  390. circuit_get_all_pending_on_channel(pending_circs, chan);
  391. SMARTLIST_FOREACH_BEGIN(pending_circs, circuit_t *, circ)
  392. {
  393. /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
  394. * leaving them in in case it's possible for the status of a circuit to
  395. * change as we're going down the list. */
  396. if (circ->marked_for_close || circ->n_chan || !circ->n_hop ||
  397. circ->state != CIRCUIT_STATE_CHAN_WAIT)
  398. continue;
  399. if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
  400. /* Look at addr/port. This is an unkeyed connection. */
  401. if (!channel_matches_extend_info(chan, circ->n_hop))
  402. continue;
  403. } else {
  404. /* We expected a key. See if it's the right one. */
  405. if (tor_memneq(chan->identity_digest,
  406. circ->n_hop->identity_digest, DIGEST_LEN))
  407. continue;
  408. }
  409. if (!status) { /* chan failed; close circ */
  410. log_info(LD_CIRC,"Channel failed; closing circ.");
  411. circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
  412. continue;
  413. }
  414. log_debug(LD_CIRC, "Found circ, sending create cell.");
  415. /* circuit_deliver_create_cell will set n_circ_id and add us to
  416. * chan_circuid_circuit_map, so we don't need to call
  417. * set_circid_chan here. */
  418. circ->n_chan = chan;
  419. extend_info_free(circ->n_hop);
  420. circ->n_hop = NULL;
  421. if (CIRCUIT_IS_ORIGIN(circ)) {
  422. if ((err_reason =
  423. circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ))) < 0) {
  424. log_info(LD_CIRC,
  425. "send_next_onion_skin failed; circuit marked for closing.");
  426. circuit_mark_for_close(circ, -err_reason);
  427. continue;
  428. /* XXX could this be bad, eg if next_onion_skin failed because conn
  429. * died? */
  430. }
  431. } else {
  432. /* pull the create cell out of circ->n_chan_create_cell, and send it */
  433. tor_assert(circ->n_chan_create_cell);
  434. if (circuit_deliver_create_cell(circ, circ->n_chan_create_cell)<0) {
  435. circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
  436. continue;
  437. }
  438. tor_free(circ->n_chan_create_cell);
  439. circuit_set_state(circ, CIRCUIT_STATE_OPEN);
  440. }
  441. }
  442. SMARTLIST_FOREACH_END(circ);
  443. smartlist_free(pending_circs);
  444. }
  445. /** Find a new circid that isn't currently in use on the circ->n_chan
  446. * for the outgoing
  447. * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
  448. * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
  449. * to this circuit. DOCDOC payload_len
  450. * Return -1 if we failed to find a suitable circid, else return 0.
  451. */
  452. static int
  453. circuit_deliver_create_cell(circuit_t *circ, const create_cell_t *create_cell)
  454. {
  455. cell_t cell;
  456. circid_t id;
  457. tor_assert(circ);
  458. tor_assert(circ->n_chan);
  459. tor_assert(create_cell);
  460. tor_assert(create_cell->cell_type == CELL_CREATE ||
  461. create_cell->cell_type == CELL_CREATE_FAST ||
  462. create_cell->cell_type == CELL_CREATE2);
  463. id = get_unique_circ_id_by_chan(circ->n_chan);
  464. if (!id) {
  465. log_warn(LD_CIRC,"failed to get unique circID.");
  466. return -1;
  467. }
  468. log_debug(LD_CIRC,"Chosen circID %u.", id);
  469. circuit_set_n_circid_chan(circ, id, circ->n_chan);
  470. memset(&cell, 0, sizeof(cell_t));
  471. if (create_cell_format(&cell, create_cell) < 0) {
  472. log_warn(LD_CIRC,"Couldn't format create cell");
  473. return -1;
  474. }
  475. cell.circ_id = circ->n_circ_id;
  476. append_cell_to_circuit_queue(circ, circ->n_chan, &cell,
  477. CELL_DIRECTION_OUT, 0);
  478. if (CIRCUIT_IS_ORIGIN(circ)) {
  479. /* mark it so it gets better rate limiting treatment. */
  480. channel_timestamp_client(circ->n_chan);
  481. }
  482. return 0;
  483. }
  484. /** We've decided to start our reachability testing. If all
  485. * is set, log this to the user. Return 1 if we did, or 0 if
  486. * we chose not to log anything. */
  487. int
  488. inform_testing_reachability(void)
  489. {
  490. char dirbuf[128];
  491. const routerinfo_t *me = router_get_my_routerinfo();
  492. if (!me)
  493. return 0;
  494. control_event_server_status(LOG_NOTICE,
  495. "CHECKING_REACHABILITY ORADDRESS=%s:%d",
  496. me->address, me->or_port);
  497. if (me->dir_port) {
  498. tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d",
  499. me->address, me->dir_port);
  500. control_event_server_status(LOG_NOTICE,
  501. "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
  502. me->address, me->dir_port);
  503. }
  504. log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
  505. "(this may take up to %d minutes -- look for log "
  506. "messages indicating success)",
  507. me->address, me->or_port,
  508. me->dir_port ? dirbuf : "",
  509. me->dir_port ? "are" : "is",
  510. TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT/60);
  511. return 1;
  512. }
  513. /** Return true iff we should send a create_fast cell to start building a given
  514. * circuit */
  515. static INLINE int
  516. should_use_create_fast_for_circuit(origin_circuit_t *circ)
  517. {
  518. const or_options_t *options = get_options();
  519. tor_assert(circ->cpath);
  520. tor_assert(circ->cpath->extend_info);
  521. if (!circ->cpath->extend_info->onion_key)
  522. return 1; /* our hand is forced: only a create_fast will work. */
  523. if (!options->FastFirstHopPK)
  524. return 0; /* we prefer to avoid create_fast */
  525. if (public_server_mode(options)) {
  526. /* We're a server, and we know an onion key. We can choose.
  527. * Prefer to blend our circuit into the other circuits we are
  528. * creating on behalf of others. */
  529. return 0;
  530. }
  531. return 1;
  532. }
  533. /** Return true if <b>circ</b> is the type of circuit we want to count
  534. * timeouts from. In particular, we want it to have not completed yet
  535. * (already completing indicates we cannibalized it), and we want it to
  536. * have exactly three hops.
  537. */
  538. int
  539. circuit_timeout_want_to_count_circ(origin_circuit_t *circ)
  540. {
  541. return !circ->has_opened
  542. && circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN;
  543. }
  544. /** This is the backbone function for building circuits.
  545. *
  546. * If circ's first hop is closed, then we need to build a create
  547. * cell and send it forward.
  548. *
  549. * Otherwise, we need to build a relay extend cell and send it
  550. * forward.
  551. *
  552. * Return -reason if we want to tear down circ, else return 0.
  553. */
  554. int
  555. circuit_send_next_onion_skin(origin_circuit_t *circ)
  556. {
  557. crypt_path_t *hop;
  558. const node_t *node;
  559. tor_assert(circ);
  560. if (circ->cpath->state == CPATH_STATE_CLOSED) {
  561. /* This is the first hop. */
  562. create_cell_t cc;
  563. int fast;
  564. int len;
  565. log_debug(LD_CIRC,"First skin; sending create cell.");
  566. memset(&cc, 0, sizeof(cc));
  567. if (circ->build_state->onehop_tunnel)
  568. control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
  569. else
  570. control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);
  571. node = node_get_by_id(circ->base_.n_chan->identity_digest);
  572. fast = should_use_create_fast_for_circuit(circ);
  573. if (!fast) {
  574. /* We are an OR and we know the right onion key: we should
  575. * send an old slow create cell.
  576. */
  577. cc.cell_type = CELL_CREATE;
  578. cc.handshake_type = ONION_HANDSHAKE_TYPE_TAP;
  579. note_request("cell: create", 1);
  580. } else {
  581. /* We are not an OR, and we're building the first hop of a circuit to a
  582. * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
  583. * and a DH operation. */
  584. cc.cell_type = CELL_CREATE_FAST;
  585. cc.handshake_type = ONION_HANDSHAKE_TYPE_FAST;
  586. note_request("cell: create fast", 1);
  587. }
  588. len = onion_skin_create(cc.handshake_type,
  589. circ->cpath->extend_info,
  590. &circ->cpath->handshake_state,
  591. cc.onionskin);
  592. if (len < 0) {
  593. log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
  594. return - END_CIRC_REASON_INTERNAL;
  595. }
  596. cc.handshake_len = len;
  597. if (circuit_deliver_create_cell(TO_CIRCUIT(circ), &cc) < 0)
  598. return - END_CIRC_REASON_RESOURCELIMIT;
  599. circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
  600. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  601. log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'",
  602. fast ? "CREATE_FAST" : "CREATE",
  603. node ? node_describe(node) : "<unnamed>");
  604. } else {
  605. extend_cell_t ec;
  606. int len;
  607. tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
  608. tor_assert(circ->base_.state == CIRCUIT_STATE_BUILDING);
  609. log_debug(LD_CIRC,"starting to send subsequent skin.");
  610. hop = onion_next_hop_in_cpath(circ->cpath);
  611. memset(&ec, 0, sizeof(ec));
  612. if (!hop) {
  613. /* done building the circuit. whew. */
  614. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  615. if (circuit_timeout_want_to_count_circ(circ)) {
  616. struct timeval end;
  617. long timediff;
  618. tor_gettimeofday(&end);
  619. timediff = tv_mdiff(&circ->base_.timestamp_created, &end);
  620. /*
  621. * If the circuit build time is much greater than we would have cut
  622. * it off at, we probably had a suspend event along this codepath,
  623. * and we should discard the value.
  624. */
  625. if (timediff < 0 || timediff > 2*circ_times.close_ms+1000) {
  626. log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. "
  627. "Assuming clock jump. Purpose %d (%s)", timediff,
  628. circ->base_.purpose,
  629. circuit_purpose_to_string(circ->base_.purpose));
  630. } else if (!circuit_build_times_disabled()) {
  631. /* Only count circuit times if the network is live */
  632. if (circuit_build_times_network_check_live(&circ_times)) {
  633. circuit_build_times_add_time(&circ_times, (build_time_t)timediff);
  634. circuit_build_times_set_timeout(&circ_times);
  635. }
  636. if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
  637. circuit_build_times_network_circ_success(&circ_times);
  638. }
  639. }
  640. }
  641. log_info(LD_CIRC,"circuit built!");
  642. circuit_reset_failure_count(0);
  643. if (circ->build_state->onehop_tunnel || circ->has_opened) {
  644. control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0);
  645. }
  646. if (!can_complete_circuit && !circ->build_state->onehop_tunnel) {
  647. const or_options_t *options = get_options();
  648. can_complete_circuit=1;
  649. /* FFFF Log a count of known routers here */
  650. log_notice(LD_GENERAL,
  651. "Tor has successfully opened a circuit. "
  652. "Looks like client functionality is working.");
  653. control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0);
  654. control_event_client_status(LOG_NOTICE, "CIRCUIT_ESTABLISHED");
  655. clear_broken_connection_map(1);
  656. if (server_mode(options) && !check_whether_orport_reachable()) {
  657. inform_testing_reachability();
  658. consider_testing_reachability(1, 1);
  659. }
  660. }
  661. pathbias_count_success(circ);
  662. circuit_rep_hist_note_result(circ);
  663. circuit_has_opened(circ); /* do other actions as necessary */
  664. /* We're done with measurement circuits here. Just close them */
  665. if (circ->base_.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT)
  666. circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
  667. return 0;
  668. }
  669. if (tor_addr_family(&hop->extend_info->addr) != AF_INET) {
  670. log_warn(LD_BUG, "Trying to extend to a non-IPv4 address.");
  671. return - END_CIRC_REASON_INTERNAL;
  672. }
  673. ec.cell_type = RELAY_COMMAND_EXTEND;
  674. tor_addr_copy(&ec.orport_ipv4.addr, &hop->extend_info->addr);
  675. ec.orport_ipv4.port = hop->extend_info->port;
  676. tor_addr_make_unspec(&ec.orport_ipv6.addr);
  677. memcpy(ec.node_id, hop->extend_info->identity_digest, DIGEST_LEN);
  678. ec.create_cell.handshake_type = ONION_HANDSHAKE_TYPE_TAP;
  679. ec.create_cell.cell_type = CELL_CREATE;
  680. len = onion_skin_create(ec.create_cell.handshake_type,
  681. hop->extend_info,
  682. &hop->handshake_state,
  683. ec.create_cell.onionskin);
  684. if (len < 0) {
  685. log_warn(LD_CIRC,"onion_skin_create failed.");
  686. return - END_CIRC_REASON_INTERNAL;
  687. }
  688. ec.create_cell.handshake_len = len;
  689. log_info(LD_CIRC,"Sending extend relay cell.");
  690. note_request("cell: extend", 1);
  691. {
  692. uint8_t command = 0;
  693. uint16_t payload_len=0;
  694. uint8_t payload[RELAY_PAYLOAD_SIZE];
  695. if (extend_cell_format(&command, &payload_len, payload, &ec)<0) {
  696. log_warn(LD_CIRC,"Couldn't format extend cell");
  697. return -END_CIRC_REASON_INTERNAL;
  698. }
  699. /* send it to hop->prev, because it will transfer
  700. * it to a create cell and then send to hop */
  701. if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
  702. command,
  703. (char*)payload, payload_len,
  704. hop->prev) < 0)
  705. return 0; /* circuit is closed */
  706. }
  707. hop->state = CPATH_STATE_AWAITING_KEYS;
  708. }
  709. return 0;
  710. }
  711. /** Our clock just jumped by <b>seconds_elapsed</b>. Assume
  712. * something has also gone wrong with our network: notify the user,
  713. * and abandon all not-yet-used circuits. */
  714. void
  715. circuit_note_clock_jumped(int seconds_elapsed)
  716. {
  717. int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE;
  718. tor_log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; "
  719. "assuming established circuits no longer work.",
  720. seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed,
  721. seconds_elapsed >=0 ? "forward" : "backward");
  722. control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%d",
  723. seconds_elapsed);
  724. can_complete_circuit=0; /* so it'll log when it works again */
  725. control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
  726. "CLOCK_JUMPED");
  727. circuit_mark_all_unused_circs();
  728. circuit_expire_all_dirty_circs();
  729. }
  730. /** Take the 'extend' <b>cell</b>, pull out addr/port plus the onion
  731. * skin and identity digest for the next hop. If we're already connected,
  732. * pass the onion skin to the next hop using a create cell; otherwise
  733. * launch a new OR connection, and <b>circ</b> will notice when the
  734. * connection succeeds or fails.
  735. *
  736. * Return -1 if we want to warn and tear down the circuit, else return 0.
  737. */
  738. int
  739. circuit_extend(cell_t *cell, circuit_t *circ)
  740. {
  741. channel_t *n_chan;
  742. relay_header_t rh;
  743. extend_cell_t ec;
  744. const char *msg = NULL;
  745. int should_launch = 0;
  746. if (circ->n_chan) {
  747. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  748. "n_chan already set. Bug/attack. Closing.");
  749. return -1;
  750. }
  751. if (circ->n_hop) {
  752. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  753. "conn to next hop already launched. Bug/attack. Closing.");
  754. return -1;
  755. }
  756. if (!server_mode(get_options())) {
  757. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  758. "Got an extend cell, but running as a client. Closing.");
  759. return -1;
  760. }
  761. relay_header_unpack(&rh, cell->payload);
  762. if (extend_cell_parse(&ec, rh.command,
  763. cell->payload+RELAY_HEADER_SIZE,
  764. rh.length) < 0) {
  765. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  766. "Can't parse extend cell. Closing circuit.");
  767. return -1;
  768. }
  769. if (!ec.orport_ipv4.port || tor_addr_is_null(&ec.orport_ipv4.addr)) {
  770. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  771. "Client asked me to extend to zero destination port or addr.");
  772. return -1;
  773. }
  774. if (tor_addr_is_internal(&ec.orport_ipv4.addr, 0) &&
  775. !get_options()->ExtendAllowPrivateAddresses) {
  776. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  777. "Client asked me to extend to a private address");
  778. return -1;
  779. }
  780. /* Check if they asked us for 0000..0000. We support using
  781. * an empty fingerprint for the first hop (e.g. for a bridge relay),
  782. * but we don't want to let people send us extend cells for empty
  783. * fingerprints -- a) because it opens the user up to a mitm attack,
  784. * and b) because it lets an attacker force the relay to hold open a
  785. * new TLS connection for each extend request. */
  786. if (tor_digest_is_zero((const char*)ec.node_id)) {
  787. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  788. "Client asked me to extend without specifying an id_digest.");
  789. return -1;
  790. }
  791. /* Next, check if we're being asked to connect to the hop that the
  792. * extend cell came from. There isn't any reason for that, and it can
  793. * assist circular-path attacks. */
  794. if (tor_memeq(ec.node_id,
  795. TO_OR_CIRCUIT(circ)->p_chan->identity_digest,
  796. DIGEST_LEN)) {
  797. log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
  798. "Client asked me to extend back to the previous hop.");
  799. return -1;
  800. }
  801. n_chan = channel_get_for_extend((const char*)ec.node_id,
  802. &ec.orport_ipv4.addr,
  803. &msg,
  804. &should_launch);
  805. if (!n_chan) {
  806. log_debug(LD_CIRC|LD_OR,"Next router (%s): %s",
  807. fmt_addrport(&ec.orport_ipv4.addr,ec.orport_ipv4.port),
  808. msg?msg:"????");
  809. circ->n_hop = extend_info_new(NULL /*nickname*/,
  810. (const char*)ec.node_id,
  811. NULL /*onion_key*/,
  812. &ec.orport_ipv4.addr,
  813. ec.orport_ipv4.port);
  814. /* XXXX Make sure we can eventually deliver create cell with weird
  815. * content */
  816. circ->n_chan_create_cell = tor_memdup(&ec.create_cell,
  817. sizeof(ec.create_cell));
  818. circuit_set_state(circ, CIRCUIT_STATE_CHAN_WAIT);
  819. if (should_launch) {
  820. /* we should try to open a connection */
  821. n_chan = channel_connect_for_circuit(&ec.orport_ipv4.addr,
  822. ec.orport_ipv4.port,
  823. (const char*)ec.node_id);
  824. if (!n_chan) {
  825. log_info(LD_CIRC,"Launching n_chan failed. Closing circuit.");
  826. circuit_mark_for_close(circ, END_CIRC_REASON_CONNECTFAILED);
  827. return 0;
  828. }
  829. log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
  830. }
  831. /* return success. The onion/circuit/etc will be taken care of
  832. * automatically (may already have been) whenever n_chan reaches
  833. * OR_CONN_STATE_OPEN.
  834. */
  835. return 0;
  836. }
  837. tor_assert(!circ->n_hop); /* Connection is already established. */
  838. circ->n_chan = n_chan;
  839. log_debug(LD_CIRC,
  840. "n_chan is %s",
  841. channel_get_canonical_remote_descr(n_chan));
  842. if (circuit_deliver_create_cell(circ, &ec.create_cell) < 0)
  843. return -1;
  844. return 0;
  845. }
  846. /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in
  847. * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are
  848. * used as follows:
  849. * - 20 to initialize f_digest
  850. * - 20 to initialize b_digest
  851. * - 16 to key f_crypto
  852. * - 16 to key b_crypto
  853. *
  854. * (If 'reverse' is true, then f_XX and b_XX are swapped.)
  855. */
  856. int
  857. circuit_init_cpath_crypto(crypt_path_t *cpath, const char *key_data,
  858. int reverse)
  859. {
  860. crypto_digest_t *tmp_digest;
  861. crypto_cipher_t *tmp_crypto;
  862. tor_assert(cpath);
  863. tor_assert(key_data);
  864. tor_assert(!(cpath->f_crypto || cpath->b_crypto ||
  865. cpath->f_digest || cpath->b_digest));
  866. cpath->f_digest = crypto_digest_new();
  867. crypto_digest_add_bytes(cpath->f_digest, key_data, DIGEST_LEN);
  868. cpath->b_digest = crypto_digest_new();
  869. crypto_digest_add_bytes(cpath->b_digest, key_data+DIGEST_LEN, DIGEST_LEN);
  870. if (!(cpath->f_crypto =
  871. crypto_cipher_new(key_data+(2*DIGEST_LEN)))) {
  872. log_warn(LD_BUG,"Forward cipher initialization failed.");
  873. return -1;
  874. }
  875. if (!(cpath->b_crypto =
  876. crypto_cipher_new(key_data+(2*DIGEST_LEN)+CIPHER_KEY_LEN))) {
  877. log_warn(LD_BUG,"Backward cipher initialization failed.");
  878. return -1;
  879. }
  880. if (reverse) {
  881. tmp_digest = cpath->f_digest;
  882. cpath->f_digest = cpath->b_digest;
  883. cpath->b_digest = tmp_digest;
  884. tmp_crypto = cpath->f_crypto;
  885. cpath->f_crypto = cpath->b_crypto;
  886. cpath->b_crypto = tmp_crypto;
  887. }
  888. return 0;
  889. }
  890. /** The minimum number of first hop completions before we start
  891. * thinking about warning about path bias and dropping guards */
  892. static int
  893. pathbias_get_min_circs(const or_options_t *options)
  894. {
  895. #define DFLT_PATH_BIAS_MIN_CIRC 20
  896. if (options->PathBiasCircThreshold >= 5)
  897. return options->PathBiasCircThreshold;
  898. else
  899. return networkstatus_get_param(NULL, "pb_mincircs",
  900. DFLT_PATH_BIAS_MIN_CIRC,
  901. 5, INT32_MAX);
  902. }
  903. static double
  904. pathbias_get_notice_rate(const or_options_t *options)
  905. {
  906. #define DFLT_PATH_BIAS_NOTICE_PCT 40
  907. if (options->PathBiasNoticeRate >= 0.0)
  908. return options->PathBiasNoticeRate;
  909. else
  910. return networkstatus_get_param(NULL, "pb_noticepct",
  911. DFLT_PATH_BIAS_NOTICE_PCT, 0, 100)/100.0;
  912. }
  913. /* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
  914. double
  915. pathbias_get_disable_rate(const or_options_t *options)
  916. {
  917. // XXX: This needs tuning based on use + experimentation before we set it
  918. #define DFLT_PATH_BIAS_DISABLE_PCT 0
  919. if (options->PathBiasDisableRate >= 0.0)
  920. return options->PathBiasDisableRate;
  921. else
  922. return networkstatus_get_param(NULL, "pb_disablepct",
  923. DFLT_PATH_BIAS_DISABLE_PCT, 0, 100)/100.0;
  924. }
  925. static int
  926. pathbias_get_scale_threshold(const or_options_t *options)
  927. {
  928. #define DFLT_PATH_BIAS_SCALE_THRESHOLD 200
  929. if (options->PathBiasScaleThreshold >= 2)
  930. return options->PathBiasScaleThreshold;
  931. else
  932. return networkstatus_get_param(NULL, "pb_scalecircs",
  933. DFLT_PATH_BIAS_SCALE_THRESHOLD, 10,
  934. INT32_MAX);
  935. }
  936. static int
  937. pathbias_get_scale_factor(const or_options_t *options)
  938. {
  939. #define DFLT_PATH_BIAS_SCALE_FACTOR 2
  940. if (options->PathBiasScaleFactor >= 1)
  941. return options->PathBiasScaleFactor;
  942. else
  943. return networkstatus_get_param(NULL, "pb_scalefactor",
  944. DFLT_PATH_BIAS_SCALE_FACTOR, 1, INT32_MAX);
  945. }
  946. static const char *
  947. pathbias_state_to_string(path_state_t state)
  948. {
  949. switch (state) {
  950. case PATH_STATE_NEW_CIRC:
  951. return "new";
  952. case PATH_STATE_DID_FIRST_HOP:
  953. return "first hop";
  954. case PATH_STATE_SUCCEEDED:
  955. return "succeeded";
  956. }
  957. return "unknown";
  958. }
  959. /**
  960. * Check our circuit state to see if this is a successful first hop.
  961. * If so, record it in the current guard's path bias first_hop count.
  962. *
  963. * Also check for several potential error cases for bug #6475.
  964. */
  965. static int
  966. pathbias_count_first_hop(origin_circuit_t *circ)
  967. {
  968. #define FIRST_HOP_NOTICE_INTERVAL (600)
  969. static ratelim_t first_hop_notice_limit =
  970. RATELIM_INIT(FIRST_HOP_NOTICE_INTERVAL);
  971. char *rate_msg = NULL;
  972. /* We can't do path bias accounting without entry guards.
  973. * Testing and controller circuits also have no guards. */
  974. if (get_options()->UseEntryGuards == 0 ||
  975. circ->base_.purpose == CIRCUIT_PURPOSE_TESTING ||
  976. circ->base_.purpose == CIRCUIT_PURPOSE_CONTROLLER) {
  977. return 0;
  978. }
  979. /* Completely ignore one hop circuits */
  980. if (circ->build_state->onehop_tunnel ||
  981. circ->build_state->desired_path_len == 1) {
  982. /* Check for inconsistency */
  983. if (circ->build_state->desired_path_len != 1 ||
  984. !circ->build_state->onehop_tunnel) {
  985. if ((rate_msg = rate_limit_log(&first_hop_notice_limit,
  986. approx_time()))) {
  987. log_notice(LD_BUG,
  988. "One-hop circuit has length %d. Path state is %s. "
  989. "Circuit is a %s currently %s.%s",
  990. circ->build_state->desired_path_len,
  991. pathbias_state_to_string(circ->path_state),
  992. circuit_purpose_to_string(circ->base_.purpose),
  993. circuit_state_to_string(circ->base_.state),
  994. rate_msg);
  995. tor_free(rate_msg);
  996. }
  997. tor_fragile_assert();
  998. }
  999. return 0;
  1000. }
  1001. if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) {
  1002. /* Help track down the real cause of bug #6475: */
  1003. if (circ->has_opened && circ->path_state != PATH_STATE_DID_FIRST_HOP) {
  1004. if ((rate_msg = rate_limit_log(&first_hop_notice_limit,
  1005. approx_time()))) {
  1006. log_info(LD_BUG,
  1007. "Opened circuit is in strange path state %s. "
  1008. "Circuit is a %s currently %s.%s",
  1009. pathbias_state_to_string(circ->path_state),
  1010. circuit_purpose_to_string(circ->base_.purpose),
  1011. circuit_state_to_string(circ->base_.state),
  1012. rate_msg);
  1013. tor_free(rate_msg);
  1014. }
  1015. }
  1016. /* Don't count cannibalized circs for path bias */
  1017. if (!circ->has_opened) {
  1018. entry_guard_t *guard;
  1019. guard =
  1020. entry_guard_get_by_id_digest(circ->base_.n_chan->identity_digest);
  1021. if (guard) {
  1022. if (circ->path_state == PATH_STATE_NEW_CIRC) {
  1023. circ->path_state = PATH_STATE_DID_FIRST_HOP;
  1024. if (entry_guard_inc_first_hop_count(guard) < 0) {
  1025. /* Bogus guard; we already warned. */
  1026. return -END_CIRC_REASON_TORPROTOCOL;
  1027. }
  1028. } else {
  1029. if ((rate_msg = rate_limit_log(&first_hop_notice_limit,
  1030. approx_time()))) {
  1031. log_info(LD_BUG,
  1032. "Unopened circuit has strange path state %s. "
  1033. "Circuit is a %s currently %s.%s",
  1034. pathbias_state_to_string(circ->path_state),
  1035. circuit_purpose_to_string(circ->base_.purpose),
  1036. circuit_state_to_string(circ->base_.state),
  1037. rate_msg);
  1038. tor_free(rate_msg);
  1039. }
  1040. }
  1041. } else {
  1042. if ((rate_msg = rate_limit_log(&first_hop_notice_limit,
  1043. approx_time()))) {
  1044. log_info(LD_BUG,
  1045. "Unopened circuit has no known guard. "
  1046. "Circuit is a %s currently %s.%s",
  1047. circuit_purpose_to_string(circ->base_.purpose),
  1048. circuit_state_to_string(circ->base_.state),
  1049. rate_msg);
  1050. tor_free(rate_msg);
  1051. }
  1052. }
  1053. }
  1054. } else {
  1055. /* Help track down the real cause of bug #6475: */
  1056. if (circ->path_state == PATH_STATE_NEW_CIRC) {
  1057. if ((rate_msg = rate_limit_log(&first_hop_notice_limit,
  1058. approx_time()))) {
  1059. log_info(LD_BUG,
  1060. "A %s circuit is in cpath state %d (opened: %d). "
  1061. "Circuit is a %s currently %s.%s",
  1062. pathbias_state_to_string(circ->path_state),
  1063. circ->cpath->state, circ->has_opened,
  1064. circuit_purpose_to_string(circ->base_.purpose),
  1065. circuit_state_to_string(circ->base_.state),
  1066. rate_msg);
  1067. tor_free(rate_msg);
  1068. }
  1069. }
  1070. }
  1071. return 0;
  1072. }
  1073. /**
  1074. * Check our circuit state to see if this is a successful circuit
  1075. * completion. If so, record it in the current guard's path bias
  1076. * success count.
  1077. *
  1078. * Also check for several potential error cases for bug #6475.
  1079. */
  1080. static void
  1081. pathbias_count_success(origin_circuit_t *circ)
  1082. {
  1083. #define SUCCESS_NOTICE_INTERVAL (600)
  1084. static ratelim_t success_notice_limit =
  1085. RATELIM_INIT(SUCCESS_NOTICE_INTERVAL);
  1086. char *rate_msg = NULL;
  1087. entry_guard_t *guard = NULL;
  1088. /* We can't do path bias accounting without entry guards.
  1089. * Testing and controller circuits also have no guards. */
  1090. if (get_options()->UseEntryGuards == 0 ||
  1091. circ->base_.purpose == CIRCUIT_PURPOSE_TESTING ||
  1092. circ->base_.purpose == CIRCUIT_PURPOSE_CONTROLLER) {
  1093. return;
  1094. }
  1095. /* Ignore one hop circuits */
  1096. if (circ->build_state->onehop_tunnel ||
  1097. circ->build_state->desired_path_len == 1) {
  1098. /* Check for consistency */
  1099. if (circ->build_state->desired_path_len != 1 ||
  1100. !circ->build_state->onehop_tunnel) {
  1101. if ((rate_msg = rate_limit_log(&success_notice_limit,
  1102. approx_time()))) {
  1103. log_notice(LD_BUG,
  1104. "One-hop circuit has length %d. Path state is %s. "
  1105. "Circuit is a %s currently %s.%s",
  1106. circ->build_state->desired_path_len,
  1107. pathbias_state_to_string(circ->path_state),
  1108. circuit_purpose_to_string(circ->base_.purpose),
  1109. circuit_state_to_string(circ->base_.state),
  1110. rate_msg);
  1111. tor_free(rate_msg);
  1112. }
  1113. tor_fragile_assert();
  1114. }
  1115. return;
  1116. }
  1117. /* Don't count cannibalized/reused circs for path bias */
  1118. if (!circ->has_opened) {
  1119. guard =
  1120. entry_guard_get_by_id_digest(circ->base_.n_chan->identity_digest);
  1121. if (guard) {
  1122. if (circ->path_state == PATH_STATE_DID_FIRST_HOP) {
  1123. circ->path_state = PATH_STATE_SUCCEEDED;
  1124. guard->circuit_successes++;
  1125. log_info(LD_PROTOCOL, "Got success count %u/%u for guard %s=%s",
  1126. guard->circuit_successes, guard->first_hops,
  1127. guard->nickname, hex_str(guard->identity, DIGEST_LEN));
  1128. } else {
  1129. if ((rate_msg = rate_limit_log(&success_notice_limit,
  1130. approx_time()))) {
  1131. log_info(LD_BUG,
  1132. "Succeeded circuit is in strange path state %s. "
  1133. "Circuit is a %s currently %s.%s",
  1134. pathbias_state_to_string(circ->path_state),
  1135. circuit_purpose_to_string(circ->base_.purpose),
  1136. circuit_state_to_string(circ->base_.state),
  1137. rate_msg);
  1138. tor_free(rate_msg);
  1139. }
  1140. }
  1141. if (guard->first_hops < guard->circuit_successes) {
  1142. log_notice(LD_BUG, "Unexpectedly high circuit_successes (%u/%u) "
  1143. "for guard %s=%s",
  1144. guard->circuit_successes, guard->first_hops,
  1145. guard->nickname, hex_str(guard->identity, DIGEST_LEN));
  1146. }
  1147. /* In rare cases, CIRCUIT_PURPOSE_TESTING can get converted to
  1148. * CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT and have no guards here.
  1149. * No need to log that case. */
  1150. } else if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
  1151. if ((rate_msg = rate_limit_log(&success_notice_limit,
  1152. approx_time()))) {
  1153. log_info(LD_BUG,
  1154. "Completed circuit has no known guard. "
  1155. "Circuit is a %s currently %s.%s",
  1156. circuit_purpose_to_string(circ->base_.purpose),
  1157. circuit_state_to_string(circ->base_.state),
  1158. rate_msg);
  1159. tor_free(rate_msg);
  1160. }
  1161. }
  1162. } else {
  1163. if (circ->path_state != PATH_STATE_SUCCEEDED) {
  1164. if ((rate_msg = rate_limit_log(&success_notice_limit,
  1165. approx_time()))) {
  1166. log_info(LD_BUG,
  1167. "Opened circuit is in strange path state %s. "
  1168. "Circuit is a %s currently %s.%s",
  1169. pathbias_state_to_string(circ->path_state),
  1170. circuit_purpose_to_string(circ->base_.purpose),
  1171. circuit_state_to_string(circ->base_.state),
  1172. rate_msg);
  1173. tor_free(rate_msg);
  1174. }
  1175. }
  1176. }
  1177. }
  1178. /** Increment the number of times we successfully extended a circuit to
  1179. * 'guard', first checking if the failure rate is high enough that we should
  1180. * eliminate the guard. Return -1 if the guard looks no good; return 0 if the
  1181. * guard looks fine. */
  1182. static int
  1183. entry_guard_inc_first_hop_count(entry_guard_t *guard)
  1184. {
  1185. const or_options_t *options = get_options();
  1186. entry_guards_changed();
  1187. if (guard->first_hops > (unsigned)pathbias_get_min_circs(options)) {
  1188. /* Note: We rely on the < comparison here to allow us to set a 0
  1189. * rate and disable the feature entirely. If refactoring, don't
  1190. * change to <= */
  1191. if (guard->circuit_successes/((double)guard->first_hops)
  1192. < pathbias_get_disable_rate(options)) {
  1193. /* This message is currently disabled by default. */
  1194. log_warn(LD_PROTOCOL,
  1195. "Extremely low circuit success rate %u/%u for guard %s=%s. "
  1196. "This indicates either an overloaded guard, an attack, or "
  1197. "a bug.",
  1198. guard->circuit_successes, guard->first_hops, guard->nickname,
  1199. hex_str(guard->identity, DIGEST_LEN));
  1200. guard->path_bias_disabled = 1;
  1201. guard->bad_since = approx_time();
  1202. return -1;
  1203. } else if (guard->circuit_successes/((double)guard->first_hops)
  1204. < pathbias_get_notice_rate(options)
  1205. && !guard->path_bias_notice) {
  1206. guard->path_bias_notice = 1;
  1207. log_notice(LD_PROTOCOL,
  1208. "Low circuit success rate %u/%u for guard %s=%s.",
  1209. guard->circuit_successes, guard->first_hops, guard->nickname,
  1210. hex_str(guard->identity, DIGEST_LEN));
  1211. }
  1212. }
  1213. /* If we get a ton of circuits, just scale everything down */
  1214. if (guard->first_hops > (unsigned)pathbias_get_scale_threshold(options)) {
  1215. const int scale_factor = pathbias_get_scale_factor(options);
  1216. /* For now, only scale if there will be no rounding error...
  1217. * XXX024: We want to switch to a real moving average for 0.2.4. */
  1218. if ((guard->first_hops % scale_factor) == 0 &&
  1219. (guard->circuit_successes % scale_factor) == 0) {
  1220. log_info(LD_PROTOCOL,
  1221. "Scaling pathbias counts to (%u/%u)/%d for guard %s=%s",
  1222. guard->circuit_successes, guard->first_hops,
  1223. scale_factor, guard->nickname, hex_str(guard->identity,
  1224. DIGEST_LEN));
  1225. guard->first_hops /= scale_factor;
  1226. guard->circuit_successes /= scale_factor;
  1227. }
  1228. }
  1229. guard->first_hops++;
  1230. log_info(LD_PROTOCOL, "Got success count %u/%u for guard %s=%s",
  1231. guard->circuit_successes, guard->first_hops, guard->nickname,
  1232. hex_str(guard->identity, DIGEST_LEN));
  1233. return 0;
  1234. }
  1235. /** A created or extended cell came back to us on the circuit, and it included
  1236. * reply_cell as its body. (If <b>reply_type</b> is CELL_CREATED, the body
  1237. * contains (the second DH key, plus KH). If <b>reply_type</b> is
  1238. * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
  1239. *
  1240. * Calculate the appropriate keys and digests, make sure KH is
  1241. * correct, and initialize this hop of the cpath.
  1242. *
  1243. * Return - reason if we want to mark circ for close, else return 0.
  1244. */
  1245. int
  1246. circuit_finish_handshake(origin_circuit_t *circ,
  1247. const created_cell_t *reply)
  1248. {
  1249. char keys[CPATH_KEY_MATERIAL_LEN];
  1250. crypt_path_t *hop;
  1251. int rv;
  1252. if ((rv = pathbias_count_first_hop(circ)) < 0)
  1253. return rv;
  1254. if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) {
  1255. hop = circ->cpath;
  1256. } else {
  1257. hop = onion_next_hop_in_cpath(circ->cpath);
  1258. if (!hop) { /* got an extended when we're all done? */
  1259. log_warn(LD_PROTOCOL,"got extended when circ already built? Closing.");
  1260. return - END_CIRC_REASON_TORPROTOCOL;
  1261. }
  1262. }
  1263. tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);
  1264. {
  1265. if (onion_skin_client_handshake(hop->handshake_state.tag,
  1266. &hop->handshake_state,
  1267. reply->reply, reply->handshake_len,
  1268. (uint8_t*)keys, sizeof(keys),
  1269. (uint8_t*)hop->rend_circ_nonce) < 0) {
  1270. log_warn(LD_CIRC,"onion_skin_client_handshake failed.");
  1271. return -END_CIRC_REASON_TORPROTOCOL;
  1272. }
  1273. }
  1274. onion_handshake_state_release(&hop->handshake_state);
  1275. if (circuit_init_cpath_crypto(hop, keys, 0)<0) {
  1276. return -END_CIRC_REASON_TORPROTOCOL;
  1277. }
  1278. hop->state = CPATH_STATE_OPEN;
  1279. log_info(LD_CIRC,"Finished building circuit hop:");
  1280. circuit_log_path(LOG_INFO,LD_CIRC,circ);
  1281. control_event_circuit_status(circ, CIRC_EVENT_EXTENDED, 0);
  1282. return 0;
  1283. }
  1284. /** We received a relay truncated cell on circ.
  1285. *
  1286. * Since we don't ask for truncates currently, getting a truncated
  1287. * means that a connection broke or an extend failed. For now,
  1288. * just give up: for circ to close, and return 0.
  1289. */
  1290. int
  1291. circuit_truncated(origin_circuit_t *circ, crypt_path_t *layer, int reason)
  1292. {
  1293. // crypt_path_t *victim;
  1294. // connection_t *stream;
  1295. tor_assert(circ);
  1296. tor_assert(layer);
  1297. /* XXX Since we don't ask for truncates currently, getting a truncated
  1298. * means that a connection broke or an extend failed. For now,
  1299. * just give up.
  1300. */
  1301. circuit_mark_for_close(TO_CIRCUIT(circ),
  1302. END_CIRC_REASON_FLAG_REMOTE|reason);
  1303. return 0;
  1304. #if 0
  1305. while (layer->next != circ->cpath) {
  1306. /* we need to clear out layer->next */
  1307. victim = layer->next;
  1308. log_debug(LD_CIRC, "Killing a layer of the cpath.");
  1309. for (stream = circ->p_streams; stream; stream=stream->next_stream) {
  1310. if (stream->cpath_layer == victim) {
  1311. log_info(LD_APP, "Marking stream %d for close because of truncate.",
  1312. stream->stream_id);
  1313. /* no need to send 'end' relay cells,
  1314. * because the other side's already dead
  1315. */
  1316. connection_mark_unattached_ap(stream, END_STREAM_REASON_DESTROY);
  1317. }
  1318. }
  1319. layer->next = victim->next;
  1320. circuit_free_cpath_node(victim);
  1321. }
  1322. log_info(LD_CIRC, "finished");
  1323. return 0;
  1324. #endif
  1325. }
  1326. /** Given a response payload and keys, initialize, then send a created
  1327. * cell back.
  1328. */
  1329. int
  1330. onionskin_answer(or_circuit_t *circ, uint8_t cell_type, const char *payload,
  1331. size_t payload_len, const char *keys,
  1332. const uint8_t *rend_circ_nonce)
  1333. {
  1334. cell_t cell;
  1335. crypt_path_t *tmp_cpath;
  1336. tmp_cpath = tor_malloc_zero(sizeof(crypt_path_t));
  1337. tmp_cpath->magic = CRYPT_PATH_MAGIC;
  1338. memset(&cell, 0, sizeof(cell_t));
  1339. cell.command = cell_type;
  1340. cell.circ_id = circ->p_circ_id;
  1341. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
  1342. memcpy(cell.payload, payload, payload_len);
  1343. log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.",
  1344. (unsigned int)get_uint32(keys),
  1345. (unsigned int)get_uint32(keys+20));
  1346. if (circuit_init_cpath_crypto(tmp_cpath, keys, 0)<0) {
  1347. log_warn(LD_BUG,"Circuit initialization failed");
  1348. tor_free(tmp_cpath);
  1349. return -1;
  1350. }
  1351. circ->n_digest = tmp_cpath->f_digest;
  1352. circ->n_crypto = tmp_cpath->f_crypto;
  1353. circ->p_digest = tmp_cpath->b_digest;
  1354. circ->p_crypto = tmp_cpath->b_crypto;
  1355. tmp_cpath->magic = 0;
  1356. tor_free(tmp_cpath);
  1357. memcpy(circ->rend_circ_nonce, rend_circ_nonce, DIGEST_LEN);
  1358. circ->is_first_hop = (cell_type == CELL_CREATED_FAST);
  1359. append_cell_to_circuit_queue(TO_CIRCUIT(circ),
  1360. circ->p_chan, &cell, CELL_DIRECTION_IN, 0);
  1361. log_debug(LD_CIRC,"Finished sending '%s' cell.",
  1362. circ->is_first_hop ? "created_fast" : "created");
  1363. if (!channel_is_local(circ->p_chan) &&
  1364. !channel_is_outgoing(circ->p_chan)) {
  1365. /* record that we could process create cells from a non-local conn
  1366. * that we didn't initiate; presumably this means that create cells
  1367. * can reach us too. */
  1368. router_orport_found_reachable();
  1369. }
  1370. return 0;
  1371. }
  1372. /** Choose a length for a circuit of purpose <b>purpose</b>.
  1373. * Default length is 3 + the number of endpoints that would give something
  1374. * away. If the routerlist <b>routers</b> doesn't have enough routers
  1375. * to handle the desired path length, return as large a path length as
  1376. * is feasible, except if it's less than 2, in which case return -1.
  1377. */
  1378. static int
  1379. new_route_len(uint8_t purpose, extend_info_t *exit,
  1380. smartlist_t *nodes)
  1381. {
  1382. int num_acceptable_routers;
  1383. int routelen;
  1384. tor_assert(nodes);
  1385. routelen = DEFAULT_ROUTE_LEN;
  1386. if (exit &&
  1387. purpose != CIRCUIT_PURPOSE_TESTING &&
  1388. purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
  1389. routelen++;
  1390. num_acceptable_routers = count_acceptable_nodes(nodes);
  1391. log_debug(LD_CIRC,"Chosen route length %d (%d/%d routers suitable).",
  1392. routelen, num_acceptable_routers, smartlist_len(nodes));
  1393. if (num_acceptable_routers < 2) {
  1394. log_info(LD_CIRC,
  1395. "Not enough acceptable routers (%d). Discarding this circuit.",
  1396. num_acceptable_routers);
  1397. return -1;
  1398. }
  1399. if (num_acceptable_routers < routelen) {
  1400. log_info(LD_CIRC,"Not enough routers: cutting routelen from %d to %d.",
  1401. routelen, num_acceptable_routers);
  1402. routelen = num_acceptable_routers;
  1403. }
  1404. return routelen;
  1405. }
  1406. /** Return a newly allocated list of uint16_t * for each predicted port not
  1407. * handled by a current circuit. */
  1408. static smartlist_t *
  1409. circuit_get_unhandled_ports(time_t now)
  1410. {
  1411. smartlist_t *dest = rep_hist_get_predicted_ports(now);
  1412. circuit_remove_handled_ports(dest);
  1413. return dest;
  1414. }
  1415. /** Return 1 if we already have circuits present or on the way for
  1416. * all anticipated ports. Return 0 if we should make more.
  1417. *
  1418. * If we're returning 0, set need_uptime and need_capacity to
  1419. * indicate any requirements that the unhandled ports have.
  1420. */
  1421. int
  1422. circuit_all_predicted_ports_handled(time_t now, int *need_uptime,
  1423. int *need_capacity)
  1424. {
  1425. int i, enough;
  1426. uint16_t *port;
  1427. smartlist_t *sl = circuit_get_unhandled_ports(now);
  1428. smartlist_t *LongLivedServices = get_options()->LongLivedPorts;
  1429. tor_assert(need_uptime);
  1430. tor_assert(need_capacity);
  1431. // Always predict need_capacity
  1432. *need_capacity = 1;
  1433. enough = (smartlist_len(sl) == 0);
  1434. for (i = 0; i < smartlist_len(sl); ++i) {
  1435. port = smartlist_get(sl, i);
  1436. if (smartlist_string_num_isin(LongLivedServices, *port))
  1437. *need_uptime = 1;
  1438. tor_free(port);
  1439. }
  1440. smartlist_free(sl);
  1441. return enough;
  1442. }
  1443. /** Return 1 if <b>node</b> can handle one or more of the ports in
  1444. * <b>needed_ports</b>, else return 0.
  1445. */
  1446. static int
  1447. node_handles_some_port(const node_t *node, smartlist_t *needed_ports)
  1448. { /* XXXX MOVE */
  1449. int i;
  1450. uint16_t port;
  1451. for (i = 0; i < smartlist_len(needed_ports); ++i) {
  1452. addr_policy_result_t r;
  1453. /* alignment issues aren't a worry for this dereference, since
  1454. needed_ports is explicitly a smartlist of uint16_t's */
  1455. port = *(uint16_t *)smartlist_get(needed_ports, i);
  1456. tor_assert(port);
  1457. if (node)
  1458. r = compare_tor_addr_to_node_policy(NULL, port, node);
  1459. else
  1460. continue;
  1461. if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
  1462. return 1;
  1463. }
  1464. return 0;
  1465. }
  1466. /** Return true iff <b>conn</b> needs another general circuit to be
  1467. * built. */
  1468. static int
  1469. ap_stream_wants_exit_attention(connection_t *conn)
  1470. {
  1471. entry_connection_t *entry;
  1472. if (conn->type != CONN_TYPE_AP)
  1473. return 0;
  1474. entry = TO_ENTRY_CONN(conn);
  1475. if (conn->state == AP_CONN_STATE_CIRCUIT_WAIT &&
  1476. !conn->marked_for_close &&
  1477. !(entry->want_onehop) && /* ignore one-hop streams */
  1478. !(entry->use_begindir) && /* ignore targeted dir fetches */
  1479. !(entry->chosen_exit_name) && /* ignore defined streams */
  1480. !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn)) &&
  1481. !circuit_stream_is_being_handled(TO_ENTRY_CONN(conn), 0,
  1482. MIN_CIRCUITS_HANDLING_STREAM))
  1483. return 1;
  1484. return 0;
  1485. }
  1486. /** Return a pointer to a suitable router to be the exit node for the
  1487. * general-purpose circuit we're about to build.
  1488. *
  1489. * Look through the connection array, and choose a router that maximizes
  1490. * the number of pending streams that can exit from this router.
  1491. *
  1492. * Return NULL if we can't find any suitable routers.
  1493. */
  1494. static const node_t *
  1495. choose_good_exit_server_general(int need_uptime, int need_capacity)
  1496. {
  1497. int *n_supported;
  1498. int n_pending_connections = 0;
  1499. smartlist_t *connections;
  1500. int best_support = -1;
  1501. int n_best_support=0;
  1502. const or_options_t *options = get_options();
  1503. const smartlist_t *the_nodes;
  1504. const node_t *node=NULL;
  1505. connections = get_connection_array();
  1506. /* Count how many connections are waiting for a circuit to be built.
  1507. * We use this for log messages now, but in the future we may depend on it.
  1508. */
  1509. SMARTLIST_FOREACH(connections, connection_t *, conn,
  1510. {
  1511. if (ap_stream_wants_exit_attention(conn))
  1512. ++n_pending_connections;
  1513. });
  1514. // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
  1515. // n_pending_connections);
  1516. /* Now we count, for each of the routers in the directory, how many
  1517. * of the pending connections could possibly exit from that
  1518. * router (n_supported[i]). (We can't be sure about cases where we
  1519. * don't know the IP address of the pending connection.)
  1520. *
  1521. * -1 means "Don't use this router at all."
  1522. */
  1523. the_nodes = nodelist_get_list();
  1524. n_supported = tor_malloc(sizeof(int)*smartlist_len(the_nodes));
  1525. SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
  1526. const int i = node_sl_idx;
  1527. if (router_digest_is_me(node->identity)) {
  1528. n_supported[i] = -1;
  1529. // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
  1530. /* XXX there's probably a reverse predecessor attack here, but
  1531. * it's slow. should we take this out? -RD
  1532. */
  1533. continue;
  1534. }
  1535. if (!node_has_descriptor(node)) {
  1536. n_supported[i] = -1;
  1537. continue;
  1538. }
  1539. if (!node->is_running || node->is_bad_exit) {
  1540. n_supported[i] = -1;
  1541. continue; /* skip routers that are known to be down or bad exits */
  1542. }
  1543. if (node_get_purpose(node) != ROUTER_PURPOSE_GENERAL) {
  1544. /* never pick a non-general node as a random exit. */
  1545. n_supported[i] = -1;
  1546. continue;
  1547. }
  1548. if (routerset_contains_node(options->ExcludeExitNodesUnion_, node)) {
  1549. n_supported[i] = -1;
  1550. continue; /* user asked us not to use it, no matter what */
  1551. }
  1552. if (options->ExitNodes &&
  1553. !routerset_contains_node(options->ExitNodes, node)) {
  1554. n_supported[i] = -1;
  1555. continue; /* not one of our chosen exit nodes */
  1556. }
  1557. if (node_is_unreliable(node, need_uptime, need_capacity, 0)) {
  1558. n_supported[i] = -1;
  1559. continue; /* skip routers that are not suitable. Don't worry if
  1560. * this makes us reject all the possible routers: if so,
  1561. * we'll retry later in this function with need_update and
  1562. * need_capacity set to 0. */
  1563. }
  1564. if (!(node->is_valid || options->AllowInvalid_ & ALLOW_INVALID_EXIT)) {
  1565. /* if it's invalid and we don't want it */
  1566. n_supported[i] = -1;
  1567. // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
  1568. // router->nickname, i);
  1569. continue; /* skip invalid routers */
  1570. }
  1571. if (options->ExcludeSingleHopRelays &&
  1572. node_allows_single_hop_exits(node)) {
  1573. n_supported[i] = -1;
  1574. continue;
  1575. }
  1576. if (node_exit_policy_rejects_all(node)) {
  1577. n_supported[i] = -1;
  1578. // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
  1579. // router->nickname, i);
  1580. continue; /* skip routers that reject all */
  1581. }
  1582. n_supported[i] = 0;
  1583. /* iterate over connections */
  1584. SMARTLIST_FOREACH_BEGIN(connections, connection_t *, conn) {
  1585. if (!ap_stream_wants_exit_attention(conn))
  1586. continue; /* Skip everything but APs in CIRCUIT_WAIT */
  1587. if (connection_ap_can_use_exit(TO_ENTRY_CONN(conn), node)) {
  1588. ++n_supported[i];
  1589. // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
  1590. // router->nickname, i, n_supported[i]);
  1591. } else {
  1592. // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
  1593. // router->nickname, i);
  1594. }
  1595. } SMARTLIST_FOREACH_END(conn);
  1596. if (n_pending_connections > 0 && n_supported[i] == 0) {
  1597. /* Leave best_support at -1 if that's where it is, so we can
  1598. * distinguish it later. */
  1599. continue;
  1600. }
  1601. if (n_supported[i] > best_support) {
  1602. /* If this router is better than previous ones, remember its index
  1603. * and goodness, and start counting how many routers are this good. */
  1604. best_support = n_supported[i]; n_best_support=1;
  1605. // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
  1606. // router->nickname);
  1607. } else if (n_supported[i] == best_support) {
  1608. /* If this router is _as good_ as the best one, just increment the
  1609. * count of equally good routers.*/
  1610. ++n_best_support;
  1611. }
  1612. } SMARTLIST_FOREACH_END(node);
  1613. log_info(LD_CIRC,
  1614. "Found %d servers that might support %d/%d pending connections.",
  1615. n_best_support, best_support >= 0 ? best_support : 0,
  1616. n_pending_connections);
  1617. /* If any routers definitely support any pending connections, choose one
  1618. * at random. */
  1619. if (best_support > 0) {
  1620. smartlist_t *supporting = smartlist_new();
  1621. SMARTLIST_FOREACH(the_nodes, const node_t *, node, {
  1622. if (n_supported[node_sl_idx] == best_support)
  1623. smartlist_add(supporting, (void*)node);
  1624. });
  1625. node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
  1626. smartlist_free(supporting);
  1627. } else {
  1628. /* Either there are no pending connections, or no routers even seem to
  1629. * possibly support any of them. Choose a router at random that satisfies
  1630. * at least one predicted exit port. */
  1631. int attempt;
  1632. smartlist_t *needed_ports, *supporting;
  1633. if (best_support == -1) {
  1634. if (need_uptime || need_capacity) {
  1635. log_info(LD_CIRC,
  1636. "We couldn't find any live%s%s routers; falling back "
  1637. "to list of all routers.",
  1638. need_capacity?", fast":"",
  1639. need_uptime?", stable":"");
  1640. tor_free(n_supported);
  1641. return choose_good_exit_server_general(0, 0);
  1642. }
  1643. log_notice(LD_CIRC, "All routers are down or won't exit%s -- "
  1644. "choosing a doomed exit at random.",
  1645. options->ExcludeExitNodesUnion_ ? " or are Excluded" : "");
  1646. }
  1647. supporting = smartlist_new();
  1648. needed_ports = circuit_get_unhandled_ports(time(NULL));
  1649. for (attempt = 0; attempt < 2; attempt++) {
  1650. /* try once to pick only from routers that satisfy a needed port,
  1651. * then if there are none, pick from any that support exiting. */
  1652. SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
  1653. if (n_supported[node_sl_idx] != -1 &&
  1654. (attempt || node_handles_some_port(node, needed_ports))) {
  1655. // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
  1656. // try, router->nickname);
  1657. smartlist_add(supporting, (void*)node);
  1658. }
  1659. } SMARTLIST_FOREACH_END(node);
  1660. node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
  1661. if (node)
  1662. break;
  1663. smartlist_clear(supporting);
  1664. /* If we reach this point, we can't actually support any unhandled
  1665. * predicted ports, so clear all the remaining ones. */
  1666. if (smartlist_len(needed_ports))
  1667. rep_hist_remove_predicted_ports(needed_ports);
  1668. }
  1669. SMARTLIST_FOREACH(needed_ports, uint16_t *, cp, tor_free(cp));
  1670. smartlist_free(needed_ports);
  1671. smartlist_free(supporting);
  1672. }
  1673. tor_free(n_supported);
  1674. if (node) {
  1675. log_info(LD_CIRC, "Chose exit server '%s'", node_describe(node));
  1676. return node;
  1677. }
  1678. if (options->ExitNodes) {
  1679. log_warn(LD_CIRC,
  1680. "No specified %sexit routers seem to be running: "
  1681. "can't choose an exit.",
  1682. options->ExcludeExitNodesUnion_ ? "non-excluded " : "");
  1683. }
  1684. return NULL;
  1685. }
  1686. /** Return a pointer to a suitable router to be the exit node for the
  1687. * circuit of purpose <b>purpose</b> that we're about to build (or NULL
  1688. * if no router is suitable).
  1689. *
  1690. * For general-purpose circuits, pass it off to
  1691. * choose_good_exit_server_general()
  1692. *
  1693. * For client-side rendezvous circuits, choose a random node, weighted
  1694. * toward the preferences in 'options'.
  1695. */
  1696. static const node_t *
  1697. choose_good_exit_server(uint8_t purpose,
  1698. int need_uptime, int need_capacity, int is_internal)
  1699. {
  1700. const or_options_t *options = get_options();
  1701. router_crn_flags_t flags = CRN_NEED_DESC;
  1702. if (need_uptime)
  1703. flags |= CRN_NEED_UPTIME;
  1704. if (need_capacity)
  1705. flags |= CRN_NEED_CAPACITY;
  1706. switch (purpose) {
  1707. case CIRCUIT_PURPOSE_C_GENERAL:
  1708. if (options->AllowInvalid_ & ALLOW_INVALID_MIDDLE)
  1709. flags |= CRN_ALLOW_INVALID;
  1710. if (is_internal) /* pick it like a middle hop */
  1711. return router_choose_random_node(NULL, options->ExcludeNodes, flags);
  1712. else
  1713. return choose_good_exit_server_general(need_uptime,need_capacity);
  1714. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  1715. if (options->AllowInvalid_ & ALLOW_INVALID_RENDEZVOUS)
  1716. flags |= CRN_ALLOW_INVALID;
  1717. return router_choose_random_node(NULL, options->ExcludeNodes, flags);
  1718. }
  1719. log_warn(LD_BUG,"Unhandled purpose %d", purpose);
  1720. tor_fragile_assert();
  1721. return NULL;
  1722. }
  1723. /** Log a warning if the user specified an exit for the circuit that
  1724. * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
  1725. static void
  1726. warn_if_last_router_excluded(origin_circuit_t *circ, const extend_info_t *exit)
  1727. {
  1728. const or_options_t *options = get_options();
  1729. routerset_t *rs = options->ExcludeNodes;
  1730. const char *description;
  1731. uint8_t purpose = circ->base_.purpose;
  1732. if (circ->build_state->onehop_tunnel)
  1733. return;
  1734. switch (purpose)
  1735. {
  1736. default:
  1737. case CIRCUIT_PURPOSE_OR:
  1738. case CIRCUIT_PURPOSE_INTRO_POINT:
  1739. case CIRCUIT_PURPOSE_REND_POINT_WAITING:
  1740. case CIRCUIT_PURPOSE_REND_ESTABLISHED:
  1741. log_warn(LD_BUG, "Called on non-origin circuit (purpose %d, %s)",
  1742. (int)purpose,
  1743. circuit_purpose_to_string(purpose));
  1744. return;
  1745. case CIRCUIT_PURPOSE_C_GENERAL:
  1746. if (circ->build_state->is_internal)
  1747. return;
  1748. description = "requested exit node";
  1749. rs = options->ExcludeExitNodesUnion_;
  1750. break;
  1751. case CIRCUIT_PURPOSE_C_INTRODUCING:
  1752. case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
  1753. case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
  1754. case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
  1755. case CIRCUIT_PURPOSE_S_CONNECT_REND:
  1756. case CIRCUIT_PURPOSE_S_REND_JOINED:
  1757. case CIRCUIT_PURPOSE_TESTING:
  1758. return;
  1759. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  1760. case CIRCUIT_PURPOSE_C_REND_READY:
  1761. case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
  1762. case CIRCUIT_PURPOSE_C_REND_JOINED:
  1763. description = "chosen rendezvous point";
  1764. break;
  1765. case CIRCUIT_PURPOSE_CONTROLLER:
  1766. rs = options->ExcludeExitNodesUnion_;
  1767. description = "controller-selected circuit target";
  1768. break;
  1769. }
  1770. if (routerset_contains_extendinfo(rs, exit)) {
  1771. /* We should never get here if StrictNodes is set to 1. */
  1772. if (options->StrictNodes) {
  1773. log_warn(LD_BUG, "Using %s '%s' which is listed in ExcludeNodes%s, "
  1774. "even though StrictNodes is set. Please report. "
  1775. "(Circuit purpose: %s)",
  1776. description, extend_info_describe(exit),
  1777. rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
  1778. circuit_purpose_to_string(purpose));
  1779. } else {
  1780. log_warn(LD_CIRC, "Using %s '%s' which is listed in "
  1781. "ExcludeNodes%s, because no better options were available. To "
  1782. "prevent this (and possibly break your Tor functionality), "
  1783. "set the StrictNodes configuration option. "
  1784. "(Circuit purpose: %s)",
  1785. description, extend_info_describe(exit),
  1786. rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
  1787. circuit_purpose_to_string(purpose));
  1788. }
  1789. circuit_log_path(LOG_WARN, LD_CIRC, circ);
  1790. }
  1791. return;
  1792. }
  1793. /** Decide a suitable length for circ's cpath, and pick an exit
  1794. * router (or use <b>exit</b> if provided). Store these in the
  1795. * cpath. Return 0 if ok, -1 if circuit should be closed. */
  1796. static int
  1797. onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit)
  1798. {
  1799. cpath_build_state_t *state = circ->build_state;
  1800. if (state->onehop_tunnel) {
  1801. log_debug(LD_CIRC, "Launching a one-hop circuit for dir tunnel.");
  1802. state->desired_path_len = 1;
  1803. } else {
  1804. int r = new_route_len(circ->base_.purpose, exit, nodelist_get_list());
  1805. if (r < 1) /* must be at least 1 */
  1806. return -1;
  1807. state->desired_path_len = r;
  1808. }
  1809. if (exit) { /* the circuit-builder pre-requested one */
  1810. warn_if_last_router_excluded(circ, exit);
  1811. log_info(LD_CIRC,"Using requested exit node '%s'",
  1812. extend_info_describe(exit));
  1813. exit = extend_info_dup(exit);
  1814. } else { /* we have to decide one */
  1815. const node_t *node =
  1816. choose_good_exit_server(circ->base_.purpose, state->need_uptime,
  1817. state->need_capacity, state->is_internal);
  1818. if (!node) {
  1819. log_warn(LD_CIRC,"failed to choose an exit server");
  1820. return -1;
  1821. }
  1822. exit = extend_info_from_node(node, 0);
  1823. tor_assert(exit);
  1824. }
  1825. state->chosen_exit = exit;
  1826. return 0;
  1827. }
  1828. /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
  1829. * hop to the cpath reflecting this. Don't send the next extend cell --
  1830. * the caller will do this if it wants to.
  1831. */
  1832. int
  1833. circuit_append_new_exit(origin_circuit_t *circ, extend_info_t *exit)
  1834. {
  1835. cpath_build_state_t *state;
  1836. tor_assert(exit);
  1837. tor_assert(circ);
  1838. state = circ->build_state;
  1839. tor_assert(state);
  1840. extend_info_free(state->chosen_exit);
  1841. state->chosen_exit = extend_info_dup(exit);
  1842. ++circ->build_state->desired_path_len;
  1843. onion_append_hop(&circ->cpath, exit);
  1844. return 0;
  1845. }
  1846. /** Take an open <b>circ</b>, and add a new hop at the end, based on
  1847. * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
  1848. * send the next extend cell to begin connecting to that hop.
  1849. */
  1850. int
  1851. circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit)
  1852. {
  1853. int err_reason = 0;
  1854. warn_if_last_router_excluded(circ, exit);
  1855. circuit_append_new_exit(circ, exit);
  1856. circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  1857. if ((err_reason = circuit_send_next_onion_skin(circ))<0) {
  1858. log_warn(LD_CIRC, "Couldn't extend circuit to new point %s.",
  1859. extend_info_describe(exit));
  1860. circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
  1861. return -1;
  1862. }
  1863. return 0;
  1864. }
  1865. /** Return the number of routers in <b>routers</b> that are currently up
  1866. * and available for building circuits through.
  1867. */
  1868. static int
  1869. count_acceptable_nodes(smartlist_t *nodes)
  1870. {
  1871. int num=0;
  1872. SMARTLIST_FOREACH_BEGIN(nodes, const node_t *, node) {
  1873. // log_debug(LD_CIRC,
  1874. // "Contemplating whether router %d (%s) is a new option.",
  1875. // i, r->nickname);
  1876. if (! node->is_running)
  1877. // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
  1878. continue;
  1879. if (! node->is_valid)
  1880. // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
  1881. continue;
  1882. if (! node_has_descriptor(node))
  1883. continue;
  1884. /* XXX This clause makes us count incorrectly: if AllowInvalidRouters
  1885. * allows this node in some places, then we're getting an inaccurate
  1886. * count. For now, be conservative and don't count it. But later we
  1887. * should try to be smarter. */
  1888. ++num;
  1889. } SMARTLIST_FOREACH_END(node);
  1890. // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
  1891. return num;
  1892. }
  1893. /** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>.
  1894. * This function is used to extend cpath by another hop.
  1895. */
  1896. void
  1897. onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop)
  1898. {
  1899. if (*head_ptr) {
  1900. new_hop->next = (*head_ptr);
  1901. new_hop->prev = (*head_ptr)->prev;
  1902. (*head_ptr)->prev->next = new_hop;
  1903. (*head_ptr)->prev = new_hop;
  1904. } else {
  1905. *head_ptr = new_hop;
  1906. new_hop->prev = new_hop->next = new_hop;
  1907. }
  1908. }
  1909. /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
  1910. * and <b>state</b> and the cpath <b>head</b> (currently populated only
  1911. * to length <b>cur_len</b> to decide a suitable middle hop for a
  1912. * circuit. In particular, make sure we don't pick the exit node or its
  1913. * family, and make sure we don't duplicate any previous nodes or their
  1914. * families. */
  1915. static const node_t *
  1916. choose_good_middle_server(uint8_t purpose,
  1917. cpath_build_state_t *state,
  1918. crypt_path_t *head,
  1919. int cur_len)
  1920. {
  1921. int i;
  1922. const node_t *r, *choice;
  1923. crypt_path_t *cpath;
  1924. smartlist_t *excluded;
  1925. const or_options_t *options = get_options();
  1926. router_crn_flags_t flags = CRN_NEED_DESC;
  1927. tor_assert(CIRCUIT_PURPOSE_MIN_ <= purpose &&
  1928. purpose <= CIRCUIT_PURPOSE_MAX_);
  1929. log_debug(LD_CIRC, "Contemplating intermediate hop: random choice.");
  1930. excluded = smartlist_new();
  1931. if ((r = build_state_get_exit_node(state))) {
  1932. nodelist_add_node_and_family(excluded, r);
  1933. }
  1934. for (i = 0, cpath = head; i < cur_len; ++i, cpath=cpath->next) {
  1935. if ((r = node_get_by_id(cpath->extend_info->identity_digest))) {
  1936. nodelist_add_node_and_family(excluded, r);
  1937. }
  1938. }
  1939. if (state->need_uptime)
  1940. flags |= CRN_NEED_UPTIME;
  1941. if (state->need_capacity)
  1942. flags |= CRN_NEED_CAPACITY;
  1943. if (options->AllowInvalid_ & ALLOW_INVALID_MIDDLE)
  1944. flags |= CRN_ALLOW_INVALID;
  1945. choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
  1946. smartlist_free(excluded);
  1947. return choice;
  1948. }
  1949. /** Pick a good entry server for the circuit to be built according to
  1950. * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
  1951. * router (if we're an OR), and respect firewall settings; if we're
  1952. * configured to use entry guards, return one.
  1953. *
  1954. * If <b>state</b> is NULL, we're choosing a router to serve as an entry
  1955. * guard, not for any particular circuit.
  1956. */
  1957. /* XXXX024 I'd like to have this be static again, but entrynodes.c needs it. */
  1958. const node_t *
  1959. choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state)
  1960. {
  1961. const node_t *choice;
  1962. smartlist_t *excluded;
  1963. const or_options_t *options = get_options();
  1964. router_crn_flags_t flags = CRN_NEED_GUARD|CRN_NEED_DESC;
  1965. const node_t *node;
  1966. if (state && options->UseEntryGuards &&
  1967. (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) {
  1968. /* This request is for an entry server to use for a regular circuit,
  1969. * and we use entry guard nodes. Just return one of the guard nodes. */
  1970. return choose_random_entry(state);
  1971. }
  1972. excluded = smartlist_new();
  1973. if (state && (node = build_state_get_exit_node(state))) {
  1974. /* Exclude the exit node from the state, if we have one. Also exclude its
  1975. * family. */
  1976. nodelist_add_node_and_family(excluded, node);
  1977. }
  1978. if (firewall_is_fascist_or()) {
  1979. /* Exclude all ORs that we can't reach through our firewall */
  1980. smartlist_t *nodes = nodelist_get_list();
  1981. SMARTLIST_FOREACH(nodes, const node_t *, node, {
  1982. if (!fascist_firewall_allows_node(node))
  1983. smartlist_add(excluded, (void*)node);
  1984. });
  1985. }
  1986. /* and exclude current entry guards and their families, if applicable */
  1987. if (options->UseEntryGuards) {
  1988. SMARTLIST_FOREACH(get_entry_guards(), const entry_guard_t *, entry,
  1989. {
  1990. if ((node = node_get_by_id(entry->identity))) {
  1991. nodelist_add_node_and_family(excluded, node);
  1992. }
  1993. });
  1994. }
  1995. if (state) {
  1996. if (state->need_uptime)
  1997. flags |= CRN_NEED_UPTIME;
  1998. if (state->need_capacity)
  1999. flags |= CRN_NEED_CAPACITY;
  2000. }
  2001. if (options->AllowInvalid_ & ALLOW_INVALID_ENTRY)
  2002. flags |= CRN_ALLOW_INVALID;
  2003. choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
  2004. smartlist_free(excluded);
  2005. return choice;
  2006. }
  2007. /** Return the first non-open hop in cpath, or return NULL if all
  2008. * hops are open. */
  2009. static crypt_path_t *
  2010. onion_next_hop_in_cpath(crypt_path_t *cpath)
  2011. {
  2012. crypt_path_t *hop = cpath;
  2013. do {
  2014. if (hop->state != CPATH_STATE_OPEN)
  2015. return hop;
  2016. hop = hop->next;
  2017. } while (hop != cpath);
  2018. return NULL;
  2019. }
  2020. /** Choose a suitable next hop in the cpath <b>head_ptr</b>,
  2021. * based on <b>state</b>. Append the hop info to head_ptr.
  2022. */
  2023. static int
  2024. onion_extend_cpath(origin_circuit_t *circ)
  2025. {
  2026. uint8_t purpose = circ->base_.purpose;
  2027. cpath_build_state_t *state = circ->build_state;
  2028. int cur_len = circuit_get_cpath_len(circ);
  2029. extend_info_t *info = NULL;
  2030. if (cur_len >= state->desired_path_len) {
  2031. log_debug(LD_CIRC, "Path is complete: %d steps long",
  2032. state->desired_path_len);
  2033. return 1;
  2034. }
  2035. log_debug(LD_CIRC, "Path is %d long; we want %d", cur_len,
  2036. state->desired_path_len);
  2037. if (cur_len == state->desired_path_len - 1) { /* Picking last node */
  2038. info = extend_info_dup(state->chosen_exit);
  2039. } else if (cur_len == 0) { /* picking first node */
  2040. const node_t *r = choose_good_entry_server(purpose, state);
  2041. if (r) {
  2042. /* If we're a client, use the preferred address rather than the
  2043. primary address, for potentially connecting to an IPv6 OR
  2044. port. */
  2045. info = extend_info_from_node(r, server_mode(get_options()) == 0);
  2046. tor_assert(info);
  2047. }
  2048. } else {
  2049. const node_t *r =
  2050. choose_good_middle_server(purpose, state, circ->cpath, cur_len);
  2051. if (r) {
  2052. info = extend_info_from_node(r, 0);
  2053. tor_assert(info);
  2054. }
  2055. }
  2056. if (!info) {
  2057. log_warn(LD_CIRC,"Failed to find node for hop %d of our path. Discarding "
  2058. "this circuit.", cur_len);
  2059. return -1;
  2060. }
  2061. log_debug(LD_CIRC,"Chose router %s for hop %d (exit is %s)",
  2062. extend_info_describe(info),
  2063. cur_len+1, build_state_get_exit_nickname(state));
  2064. onion_append_hop(&circ->cpath, info);
  2065. extend_info_free(info);
  2066. return 0;
  2067. }
  2068. /** Create a new hop, annotate it with information about its
  2069. * corresponding router <b>choice</b>, and append it to the
  2070. * end of the cpath <b>head_ptr</b>. */
  2071. static int
  2072. onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
  2073. {
  2074. crypt_path_t *hop = tor_malloc_zero(sizeof(crypt_path_t));
  2075. /* link hop into the cpath, at the end. */
  2076. onion_append_to_cpath(head_ptr, hop);
  2077. hop->magic = CRYPT_PATH_MAGIC;
  2078. hop->state = CPATH_STATE_CLOSED;
  2079. hop->extend_info = extend_info_dup(choice);
  2080. hop->package_window = circuit_initial_package_window();
  2081. hop->deliver_window = CIRCWINDOW_START;
  2082. return 0;
  2083. }
  2084. /** Allocate a new extend_info object based on the various arguments. */
  2085. extend_info_t *
  2086. extend_info_new(const char *nickname, const char *digest,
  2087. crypto_pk_t *onion_key,
  2088. const tor_addr_t *addr, uint16_t port)
  2089. {
  2090. extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
  2091. memcpy(info->identity_digest, digest, DIGEST_LEN);
  2092. if (nickname)
  2093. strlcpy(info->nickname, nickname, sizeof(info->nickname));
  2094. if (onion_key)
  2095. info->onion_key = crypto_pk_dup_key(onion_key);
  2096. tor_addr_copy(&info->addr, addr);
  2097. info->port = port;
  2098. return info;
  2099. }
  2100. /** Allocate and return a new extend_info that can be used to build a
  2101. * circuit to or through the node <b>node</b>. Use the primary address
  2102. * of the node (i.e. its IPv4 address) unless
  2103. * <b>for_direct_connect</b> is true, in which case the preferred
  2104. * address is used instead. May return NULL if there is not enough
  2105. * info about <b>node</b> to extend to it--for example, if there is no
  2106. * routerinfo_t or microdesc_t.
  2107. **/
  2108. extend_info_t *
  2109. extend_info_from_node(const node_t *node, int for_direct_connect)
  2110. {
  2111. tor_addr_port_t ap;
  2112. if (node->ri == NULL && (node->rs == NULL || node->md == NULL))
  2113. return NULL;
  2114. if (for_direct_connect)
  2115. node_get_pref_orport(node, &ap);
  2116. else
  2117. node_get_prim_orport(node, &ap);
  2118. log_debug(LD_CIRC, "using %s for %s",
  2119. fmt_addrport(&ap.addr, ap.port),
  2120. node->ri ? node->ri->nickname : node->rs->nickname);
  2121. if (node->ri)
  2122. return extend_info_new(node->ri->nickname,
  2123. node->identity,
  2124. node->ri->onion_pkey,
  2125. &ap.addr,
  2126. ap.port);
  2127. else if (node->rs && node->md)
  2128. return extend_info_new(node->rs->nickname,
  2129. node->identity,
  2130. node->md->onion_pkey,
  2131. &ap.addr,
  2132. ap.port);
  2133. else
  2134. return NULL;
  2135. }
  2136. /** Release storage held by an extend_info_t struct. */
  2137. void
  2138. extend_info_free(extend_info_t *info)
  2139. {
  2140. if (!info)
  2141. return;
  2142. crypto_pk_free(info->onion_key);
  2143. tor_free(info);
  2144. }
  2145. /** Allocate and return a new extend_info_t with the same contents as
  2146. * <b>info</b>. */
  2147. extend_info_t *
  2148. extend_info_dup(extend_info_t *info)
  2149. {
  2150. extend_info_t *newinfo;
  2151. tor_assert(info);
  2152. newinfo = tor_malloc(sizeof(extend_info_t));
  2153. memcpy(newinfo, info, sizeof(extend_info_t));
  2154. if (info->onion_key)
  2155. newinfo->onion_key = crypto_pk_dup_key(info->onion_key);
  2156. else
  2157. newinfo->onion_key = NULL;
  2158. return newinfo;
  2159. }
  2160. /** Return the routerinfo_t for the chosen exit router in <b>state</b>.
  2161. * If there is no chosen exit, or if we don't know the routerinfo_t for
  2162. * the chosen exit, return NULL.
  2163. */
  2164. const node_t *
  2165. build_state_get_exit_node(cpath_build_state_t *state)
  2166. {
  2167. if (!state || !state->chosen_exit)
  2168. return NULL;
  2169. return node_get_by_id(state->chosen_exit->identity_digest);
  2170. }
  2171. /** Return the nickname for the chosen exit router in <b>state</b>. If
  2172. * there is no chosen exit, or if we don't know the routerinfo_t for the
  2173. * chosen exit, return NULL.
  2174. */
  2175. const char *
  2176. build_state_get_exit_nickname(cpath_build_state_t *state)
  2177. {
  2178. if (!state || !state->chosen_exit)
  2179. return NULL;
  2180. return state->chosen_exit->nickname;
  2181. }