circuitlist.c 79 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463
  1. /* Copyright 2001 Matej Pfajfar.
  2. * Copyright (c) 2001-2004, Roger Dingledine.
  3. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  4. * Copyright (c) 2007-2017, The Tor Project, Inc. */
  5. /* See LICENSE for licensing information */
  6. /**
  7. * \file circuitlist.c
  8. *
  9. * \brief Manage global structures that list and index circuits, and
  10. * look up circuits within them.
  11. *
  12. * One of the most frequent operations in Tor occurs every time that
  13. * a relay cell arrives on a channel. When that happens, we need to
  14. * find which circuit it is associated with, based on the channel and the
  15. * circuit ID in the relay cell.
  16. *
  17. * To handle that, we maintain a global list of circuits, and a hashtable
  18. * mapping [channel,circID] pairs to circuits. Circuits are added to and
  19. * removed from this mapping using circuit_set_p_circid_chan() and
  20. * circuit_set_n_circid_chan(). To look up a circuit from this map, most
  21. * callers should use circuit_get_by_circid_channel(), though
  22. * circuit_get_by_circid_channel_even_if_marked() is appropriate under some
  23. * circumstances.
  24. *
  25. * We also need to allow for the possibility that we have blocked use of a
  26. * circuit ID (because we are waiting to send a DESTROY cell), but the
  27. * circuit is not there any more. For that case, we allow placeholder
  28. * entries in the table, using channel_mark_circid_unusable().
  29. *
  30. * To efficiently handle a channel that has just opened, we also maintain a
  31. * list of the circuits waiting for channels, so we can attach them as
  32. * needed without iterating through the whole list of circuits, using
  33. * circuit_get_all_pending_on_channel().
  34. *
  35. * In this module, we also handle the list of circuits that have been
  36. * marked for close elsewhere, and close them as needed. (We use this
  37. * "mark now, close later" pattern here and elsewhere to avoid
  38. * unpredictable recursion if we closed every circuit immediately upon
  39. * realizing it needed to close.) See circuit_mark_for_close() for the
  40. * mark function, and circuit_close_all_marked() for the close function.
  41. *
  42. * For hidden services, we need to be able to look up introduction point
  43. * circuits and rendezvous circuits by cookie, key, etc. These are
  44. * currently handled with linear searches in
  45. * circuit_get_ready_rend_circuit_by_rend_data(),
  46. * circuit_get_next_by_pk_and_purpose(), and with hash lookups in
  47. * circuit_get_rendezvous() and circuit_get_intro_point().
  48. *
  49. * This module is also the entry point for our out-of-memory handler
  50. * logic, which was originally circuit-focused.
  51. **/
  52. #define CIRCUITLIST_PRIVATE
  53. #include "or.h"
  54. #include "channel.h"
  55. #include "circpathbias.h"
  56. #include "circuitbuild.h"
  57. #include "circuitlist.h"
  58. #include "circuituse.h"
  59. #include "circuitstats.h"
  60. #include "connection.h"
  61. #include "config.h"
  62. #include "connection_edge.h"
  63. #include "connection_or.h"
  64. #include "control.h"
  65. #include "entrynodes.h"
  66. #include "main.h"
  67. #include "hs_circuitmap.h"
  68. #include "hs_common.h"
  69. #include "networkstatus.h"
  70. #include "nodelist.h"
  71. #include "onion.h"
  72. #include "onion_fast.h"
  73. #include "policies.h"
  74. #include "relay.h"
  75. #include "rendclient.h"
  76. #include "rendcommon.h"
  77. #include "rephist.h"
  78. #include "routerlist.h"
  79. #include "routerset.h"
  80. #include "channelpadding.h"
  81. #include "ht.h"
  82. /********* START VARIABLES **********/
  83. /** A global list of all circuits at this hop. */
  84. static smartlist_t *global_circuitlist = NULL;
  85. /** A global list of all origin circuits. Every element of this is also
  86. * an element of global_circuitlist. */
  87. static smartlist_t *global_origin_circuit_list = NULL;
  88. /** A list of all the circuits in CIRCUIT_STATE_CHAN_WAIT. */
  89. static smartlist_t *circuits_pending_chans = NULL;
  90. /** List of all the (origin) circuits whose state is
  91. * CIRCUIT_STATE_GUARD_WAIT. */
  92. static smartlist_t *circuits_pending_other_guards = NULL;
  93. /** A list of all the circuits that have been marked with
  94. * circuit_mark_for_close and which are waiting for circuit_about_to_free. */
  95. static smartlist_t *circuits_pending_close = NULL;
  96. static void circuit_free_cpath_node(crypt_path_t *victim);
  97. static void cpath_ref_decref(crypt_path_reference_t *cpath_ref);
  98. static void circuit_about_to_free_atexit(circuit_t *circ);
  99. static void circuit_about_to_free(circuit_t *circ);
  100. /********* END VARIABLES ************/
  101. /** A map from channel and circuit ID to circuit. (Lookup performance is
  102. * very important here, since we need to do it every time a cell arrives.) */
  103. typedef struct chan_circid_circuit_map_t {
  104. HT_ENTRY(chan_circid_circuit_map_t) node;
  105. channel_t *chan;
  106. circid_t circ_id;
  107. circuit_t *circuit;
  108. /* For debugging 12184: when was this placeholder item added? */
  109. time_t made_placeholder_at;
  110. } chan_circid_circuit_map_t;
  111. /** Helper for hash tables: compare the channel and circuit ID for a and
  112. * b, and return less than, equal to, or greater than zero appropriately.
  113. */
  114. static inline int
  115. chan_circid_entries_eq_(chan_circid_circuit_map_t *a,
  116. chan_circid_circuit_map_t *b)
  117. {
  118. return a->chan == b->chan && a->circ_id == b->circ_id;
  119. }
  120. /** Helper: return a hash based on circuit ID and the pointer value of
  121. * chan in <b>a</b>. */
  122. static inline unsigned int
  123. chan_circid_entry_hash_(chan_circid_circuit_map_t *a)
  124. {
  125. /* Try to squeze the siphash input into 8 bytes to save any extra siphash
  126. * rounds. This hash function is in the critical path. */
  127. uintptr_t chan = (uintptr_t) (void*) a->chan;
  128. uint32_t array[2];
  129. array[0] = a->circ_id;
  130. /* The low bits of the channel pointer are uninteresting, since the channel
  131. * is a pretty big structure. */
  132. array[1] = (uint32_t) (chan >> 6);
  133. return (unsigned) siphash24g(array, sizeof(array));
  134. }
  135. /** Map from [chan,circid] to circuit. */
  136. static HT_HEAD(chan_circid_map, chan_circid_circuit_map_t)
  137. chan_circid_map = HT_INITIALIZER();
  138. HT_PROTOTYPE(chan_circid_map, chan_circid_circuit_map_t, node,
  139. chan_circid_entry_hash_, chan_circid_entries_eq_)
  140. HT_GENERATE2(chan_circid_map, chan_circid_circuit_map_t, node,
  141. chan_circid_entry_hash_, chan_circid_entries_eq_, 0.6,
  142. tor_reallocarray_, tor_free_)
  143. /** The most recently returned entry from circuit_get_by_circid_chan;
  144. * used to improve performance when many cells arrive in a row from the
  145. * same circuit.
  146. */
  147. static chan_circid_circuit_map_t *_last_circid_chan_ent = NULL;
  148. /** Implementation helper for circuit_set_{p,n}_circid_channel: A circuit ID
  149. * and/or channel for circ has just changed from <b>old_chan, old_id</b>
  150. * to <b>chan, id</b>. Adjust the chan,circid map as appropriate, removing
  151. * the old entry (if any) and adding a new one. */
  152. static void
  153. circuit_set_circid_chan_helper(circuit_t *circ, int direction,
  154. circid_t id,
  155. channel_t *chan)
  156. {
  157. chan_circid_circuit_map_t search;
  158. chan_circid_circuit_map_t *found;
  159. channel_t *old_chan, **chan_ptr;
  160. circid_t old_id, *circid_ptr;
  161. int make_active, attached = 0;
  162. if (direction == CELL_DIRECTION_OUT) {
  163. chan_ptr = &circ->n_chan;
  164. circid_ptr = &circ->n_circ_id;
  165. make_active = circ->n_chan_cells.n > 0;
  166. } else {
  167. or_circuit_t *c = TO_OR_CIRCUIT(circ);
  168. chan_ptr = &c->p_chan;
  169. circid_ptr = &c->p_circ_id;
  170. make_active = c->p_chan_cells.n > 0;
  171. }
  172. old_chan = *chan_ptr;
  173. old_id = *circid_ptr;
  174. if (id == old_id && chan == old_chan)
  175. return;
  176. if (_last_circid_chan_ent &&
  177. ((old_id == _last_circid_chan_ent->circ_id &&
  178. old_chan == _last_circid_chan_ent->chan) ||
  179. (id == _last_circid_chan_ent->circ_id &&
  180. chan == _last_circid_chan_ent->chan))) {
  181. _last_circid_chan_ent = NULL;
  182. }
  183. if (old_chan) {
  184. /*
  185. * If we're changing channels or ID and had an old channel and a non
  186. * zero old ID and weren't marked for close (i.e., we should have been
  187. * attached), detach the circuit. ID changes require this because
  188. * circuitmux hashes on (channel_id, circuit_id).
  189. */
  190. if (old_id != 0 && (old_chan != chan || old_id != id) &&
  191. !(circ->marked_for_close)) {
  192. tor_assert(old_chan->cmux);
  193. circuitmux_detach_circuit(old_chan->cmux, circ);
  194. }
  195. /* we may need to remove it from the conn-circid map */
  196. search.circ_id = old_id;
  197. search.chan = old_chan;
  198. found = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
  199. if (found) {
  200. tor_free(found);
  201. if (direction == CELL_DIRECTION_OUT) {
  202. /* One fewer circuits use old_chan as n_chan */
  203. --(old_chan->num_n_circuits);
  204. } else {
  205. /* One fewer circuits use old_chan as p_chan */
  206. --(old_chan->num_p_circuits);
  207. }
  208. }
  209. }
  210. /* Change the values only after we have possibly made the circuit inactive
  211. * on the previous chan. */
  212. *chan_ptr = chan;
  213. *circid_ptr = id;
  214. if (chan == NULL)
  215. return;
  216. /* now add the new one to the conn-circid map */
  217. search.circ_id = id;
  218. search.chan = chan;
  219. found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
  220. if (found) {
  221. found->circuit = circ;
  222. found->made_placeholder_at = 0;
  223. } else {
  224. found = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
  225. found->circ_id = id;
  226. found->chan = chan;
  227. found->circuit = circ;
  228. HT_INSERT(chan_circid_map, &chan_circid_map, found);
  229. }
  230. /*
  231. * Attach to the circuitmux if we're changing channels or IDs and
  232. * have a new channel and ID to use and the circuit is not marked for
  233. * close.
  234. */
  235. if (chan && id != 0 && (old_chan != chan || old_id != id) &&
  236. !(circ->marked_for_close)) {
  237. tor_assert(chan->cmux);
  238. circuitmux_attach_circuit(chan->cmux, circ, direction);
  239. attached = 1;
  240. }
  241. /*
  242. * This is a no-op if we have no cells, but if we do it marks us active to
  243. * the circuitmux
  244. */
  245. if (make_active && attached)
  246. update_circuit_on_cmux(circ, direction);
  247. /* Adjust circuit counts on new channel */
  248. if (direction == CELL_DIRECTION_OUT) {
  249. ++chan->num_n_circuits;
  250. } else {
  251. ++chan->num_p_circuits;
  252. }
  253. }
  254. /** Mark that circuit id <b>id</b> shouldn't be used on channel <b>chan</b>,
  255. * even if there is no circuit on the channel. We use this to keep the
  256. * circuit id from getting re-used while we have queued but not yet sent
  257. * a destroy cell. */
  258. void
  259. channel_mark_circid_unusable(channel_t *chan, circid_t id)
  260. {
  261. chan_circid_circuit_map_t search;
  262. chan_circid_circuit_map_t *ent;
  263. /* See if there's an entry there. That wouldn't be good. */
  264. memset(&search, 0, sizeof(search));
  265. search.chan = chan;
  266. search.circ_id = id;
  267. ent = HT_FIND(chan_circid_map, &chan_circid_map, &search);
  268. if (ent && ent->circuit) {
  269. /* we have a problem. */
  270. log_warn(LD_BUG, "Tried to mark %u unusable on %p, but there was already "
  271. "a circuit there.", (unsigned)id, chan);
  272. } else if (ent) {
  273. /* It's already marked. */
  274. if (!ent->made_placeholder_at)
  275. ent->made_placeholder_at = approx_time();
  276. } else {
  277. ent = tor_malloc_zero(sizeof(chan_circid_circuit_map_t));
  278. ent->chan = chan;
  279. ent->circ_id = id;
  280. /* leave circuit at NULL. */
  281. ent->made_placeholder_at = approx_time();
  282. HT_INSERT(chan_circid_map, &chan_circid_map, ent);
  283. }
  284. }
  285. /** Mark that a circuit id <b>id</b> can be used again on <b>chan</b>.
  286. * We use this to re-enable the circuit ID after we've sent a destroy cell.
  287. */
  288. void
  289. channel_mark_circid_usable(channel_t *chan, circid_t id)
  290. {
  291. chan_circid_circuit_map_t search;
  292. chan_circid_circuit_map_t *ent;
  293. /* See if there's an entry there. That wouldn't be good. */
  294. memset(&search, 0, sizeof(search));
  295. search.chan = chan;
  296. search.circ_id = id;
  297. ent = HT_REMOVE(chan_circid_map, &chan_circid_map, &search);
  298. if (ent && ent->circuit) {
  299. log_warn(LD_BUG, "Tried to mark %u usable on %p, but there was already "
  300. "a circuit there.", (unsigned)id, chan);
  301. return;
  302. }
  303. if (_last_circid_chan_ent == ent)
  304. _last_circid_chan_ent = NULL;
  305. tor_free(ent);
  306. }
  307. /** Called to indicate that a DESTROY is pending on <b>chan</b> with
  308. * circuit ID <b>id</b>, but hasn't been sent yet. */
  309. void
  310. channel_note_destroy_pending(channel_t *chan, circid_t id)
  311. {
  312. circuit_t *circ = circuit_get_by_circid_channel_even_if_marked(id,chan);
  313. if (circ) {
  314. if (circ->n_chan == chan && circ->n_circ_id == id) {
  315. circ->n_delete_pending = 1;
  316. } else {
  317. or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
  318. if (orcirc->p_chan == chan && orcirc->p_circ_id == id) {
  319. circ->p_delete_pending = 1;
  320. }
  321. }
  322. return;
  323. }
  324. channel_mark_circid_unusable(chan, id);
  325. }
  326. /** Called to indicate that a DESTROY is no longer pending on <b>chan</b> with
  327. * circuit ID <b>id</b> -- typically, because it has been sent. */
  328. MOCK_IMPL(void,
  329. channel_note_destroy_not_pending,(channel_t *chan, circid_t id))
  330. {
  331. circuit_t *circ = circuit_get_by_circid_channel_even_if_marked(id,chan);
  332. if (circ) {
  333. if (circ->n_chan == chan && circ->n_circ_id == id) {
  334. circ->n_delete_pending = 0;
  335. } else {
  336. or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
  337. if (orcirc->p_chan == chan && orcirc->p_circ_id == id) {
  338. circ->p_delete_pending = 0;
  339. }
  340. }
  341. /* XXXX this shouldn't happen; log a bug here. */
  342. return;
  343. }
  344. channel_mark_circid_usable(chan, id);
  345. }
  346. /** Set the p_conn field of a circuit <b>circ</b>, along
  347. * with the corresponding circuit ID, and add the circuit as appropriate
  348. * to the (chan,id)-\>circuit map. */
  349. void
  350. circuit_set_p_circid_chan(or_circuit_t *or_circ, circid_t id,
  351. channel_t *chan)
  352. {
  353. circuit_t *circ = TO_CIRCUIT(or_circ);
  354. channel_t *old_chan = or_circ->p_chan;
  355. circid_t old_id = or_circ->p_circ_id;
  356. circuit_set_circid_chan_helper(circ, CELL_DIRECTION_IN, id, chan);
  357. if (chan) {
  358. tor_assert(bool_eq(or_circ->p_chan_cells.n,
  359. or_circ->next_active_on_p_chan));
  360. chan->timestamp_last_had_circuits = approx_time();
  361. }
  362. if (circ->p_delete_pending && old_chan) {
  363. channel_mark_circid_unusable(old_chan, old_id);
  364. circ->p_delete_pending = 0;
  365. }
  366. }
  367. /** Set the n_conn field of a circuit <b>circ</b>, along
  368. * with the corresponding circuit ID, and add the circuit as appropriate
  369. * to the (chan,id)-\>circuit map. */
  370. void
  371. circuit_set_n_circid_chan(circuit_t *circ, circid_t id,
  372. channel_t *chan)
  373. {
  374. channel_t *old_chan = circ->n_chan;
  375. circid_t old_id = circ->n_circ_id;
  376. circuit_set_circid_chan_helper(circ, CELL_DIRECTION_OUT, id, chan);
  377. if (chan) {
  378. tor_assert(bool_eq(circ->n_chan_cells.n, circ->next_active_on_n_chan));
  379. chan->timestamp_last_had_circuits = approx_time();
  380. }
  381. if (circ->n_delete_pending && old_chan) {
  382. channel_mark_circid_unusable(old_chan, old_id);
  383. circ->n_delete_pending = 0;
  384. }
  385. }
  386. /** Change the state of <b>circ</b> to <b>state</b>, adding it to or removing
  387. * it from lists as appropriate. */
  388. void
  389. circuit_set_state(circuit_t *circ, uint8_t state)
  390. {
  391. tor_assert(circ);
  392. if (state == circ->state)
  393. return;
  394. if (PREDICT_UNLIKELY(!circuits_pending_chans))
  395. circuits_pending_chans = smartlist_new();
  396. if (PREDICT_UNLIKELY(!circuits_pending_other_guards))
  397. circuits_pending_other_guards = smartlist_new();
  398. if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
  399. /* remove from waiting-circuit list. */
  400. smartlist_remove(circuits_pending_chans, circ);
  401. }
  402. if (state == CIRCUIT_STATE_CHAN_WAIT) {
  403. /* add to waiting-circuit list. */
  404. smartlist_add(circuits_pending_chans, circ);
  405. }
  406. if (circ->state == CIRCUIT_STATE_GUARD_WAIT) {
  407. smartlist_remove(circuits_pending_other_guards, circ);
  408. }
  409. if (state == CIRCUIT_STATE_GUARD_WAIT) {
  410. smartlist_add(circuits_pending_other_guards, circ);
  411. }
  412. if (state == CIRCUIT_STATE_GUARD_WAIT || state == CIRCUIT_STATE_OPEN)
  413. tor_assert(!circ->n_chan_create_cell);
  414. circ->state = state;
  415. }
  416. /** Append to <b>out</b> all circuits in state CHAN_WAIT waiting for
  417. * the given connection. */
  418. void
  419. circuit_get_all_pending_on_channel(smartlist_t *out, channel_t *chan)
  420. {
  421. tor_assert(out);
  422. tor_assert(chan);
  423. if (!circuits_pending_chans)
  424. return;
  425. SMARTLIST_FOREACH_BEGIN(circuits_pending_chans, circuit_t *, circ) {
  426. if (circ->marked_for_close)
  427. continue;
  428. if (!circ->n_hop)
  429. continue;
  430. tor_assert(circ->state == CIRCUIT_STATE_CHAN_WAIT);
  431. if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
  432. /* Look at addr/port. This is an unkeyed connection. */
  433. if (!channel_matches_extend_info(chan, circ->n_hop))
  434. continue;
  435. } else {
  436. /* We expected a key. See if it's the right one. */
  437. if (tor_memneq(chan->identity_digest,
  438. circ->n_hop->identity_digest, DIGEST_LEN))
  439. continue;
  440. }
  441. smartlist_add(out, circ);
  442. } SMARTLIST_FOREACH_END(circ);
  443. }
  444. /** Return the number of circuits in state CHAN_WAIT, waiting for the given
  445. * channel. */
  446. int
  447. circuit_count_pending_on_channel(channel_t *chan)
  448. {
  449. int cnt;
  450. smartlist_t *sl = smartlist_new();
  451. tor_assert(chan);
  452. circuit_get_all_pending_on_channel(sl, chan);
  453. cnt = smartlist_len(sl);
  454. smartlist_free(sl);
  455. log_debug(LD_CIRC,"or_conn to %s at %s, %d pending circs",
  456. chan->nickname ? chan->nickname : "NULL",
  457. channel_get_canonical_remote_descr(chan),
  458. cnt);
  459. return cnt;
  460. }
  461. /** Remove <b>origin_circ</b> from the global list of origin circuits.
  462. * Called when we are freeing a circuit.
  463. */
  464. static void
  465. circuit_remove_from_origin_circuit_list(origin_circuit_t *origin_circ)
  466. {
  467. int origin_idx = origin_circ->global_origin_circuit_list_idx;
  468. if (origin_idx < 0)
  469. return;
  470. origin_circuit_t *c2;
  471. tor_assert(origin_idx <= smartlist_len(global_origin_circuit_list));
  472. c2 = smartlist_get(global_origin_circuit_list, origin_idx);
  473. tor_assert(origin_circ == c2);
  474. smartlist_del(global_origin_circuit_list, origin_idx);
  475. if (origin_idx < smartlist_len(global_origin_circuit_list)) {
  476. origin_circuit_t *replacement =
  477. smartlist_get(global_origin_circuit_list, origin_idx);
  478. replacement->global_origin_circuit_list_idx = origin_idx;
  479. }
  480. origin_circ->global_origin_circuit_list_idx = -1;
  481. }
  482. /** Add <b>origin_circ</b> to the global list of origin circuits. Called
  483. * when creating the circuit. */
  484. static void
  485. circuit_add_to_origin_circuit_list(origin_circuit_t *origin_circ)
  486. {
  487. tor_assert(origin_circ->global_origin_circuit_list_idx == -1);
  488. smartlist_t *lst = circuit_get_global_origin_circuit_list();
  489. smartlist_add(lst, origin_circ);
  490. origin_circ->global_origin_circuit_list_idx = smartlist_len(lst) - 1;
  491. }
  492. /** Detach from the global circuit list, and deallocate, all
  493. * circuits that have been marked for close.
  494. */
  495. void
  496. circuit_close_all_marked(void)
  497. {
  498. if (circuits_pending_close == NULL)
  499. return;
  500. smartlist_t *lst = circuit_get_global_list();
  501. SMARTLIST_FOREACH_BEGIN(circuits_pending_close, circuit_t *, circ) {
  502. tor_assert(circ->marked_for_close);
  503. /* Remove it from the circuit list. */
  504. int idx = circ->global_circuitlist_idx;
  505. smartlist_del(lst, idx);
  506. if (idx < smartlist_len(lst)) {
  507. circuit_t *replacement = smartlist_get(lst, idx);
  508. replacement->global_circuitlist_idx = idx;
  509. }
  510. circ->global_circuitlist_idx = -1;
  511. /* Remove it from the origin circuit list, if appropriate. */
  512. if (CIRCUIT_IS_ORIGIN(circ)) {
  513. circuit_remove_from_origin_circuit_list(TO_ORIGIN_CIRCUIT(circ));
  514. }
  515. circuit_about_to_free(circ);
  516. circuit_free(circ);
  517. } SMARTLIST_FOREACH_END(circ);
  518. smartlist_clear(circuits_pending_close);
  519. }
  520. /** Return a pointer to the global list of circuits. */
  521. MOCK_IMPL(smartlist_t *,
  522. circuit_get_global_list,(void))
  523. {
  524. if (NULL == global_circuitlist)
  525. global_circuitlist = smartlist_new();
  526. return global_circuitlist;
  527. }
  528. /** Return a pointer to the global list of origin circuits. */
  529. smartlist_t *
  530. circuit_get_global_origin_circuit_list(void)
  531. {
  532. if (NULL == global_origin_circuit_list)
  533. global_origin_circuit_list = smartlist_new();
  534. return global_origin_circuit_list;
  535. }
  536. /** Function to make circ-\>state human-readable */
  537. const char *
  538. circuit_state_to_string(int state)
  539. {
  540. static char buf[64];
  541. switch (state) {
  542. case CIRCUIT_STATE_BUILDING: return "doing handshakes";
  543. case CIRCUIT_STATE_ONIONSKIN_PENDING: return "processing the onion";
  544. case CIRCUIT_STATE_CHAN_WAIT: return "connecting to server";
  545. case CIRCUIT_STATE_GUARD_WAIT: return "waiting to see how other "
  546. "guards perform";
  547. case CIRCUIT_STATE_OPEN: return "open";
  548. default:
  549. log_warn(LD_BUG, "Unknown circuit state %d", state);
  550. tor_snprintf(buf, sizeof(buf), "unknown state [%d]", state);
  551. return buf;
  552. }
  553. }
  554. /** Map a circuit purpose to a string suitable to be displayed to a
  555. * controller. */
  556. const char *
  557. circuit_purpose_to_controller_string(uint8_t purpose)
  558. {
  559. static char buf[32];
  560. switch (purpose) {
  561. case CIRCUIT_PURPOSE_OR:
  562. case CIRCUIT_PURPOSE_INTRO_POINT:
  563. case CIRCUIT_PURPOSE_REND_POINT_WAITING:
  564. case CIRCUIT_PURPOSE_REND_ESTABLISHED:
  565. return "SERVER"; /* A controller should never see these, actually. */
  566. case CIRCUIT_PURPOSE_C_GENERAL:
  567. return "GENERAL";
  568. case CIRCUIT_PURPOSE_C_INTRODUCING:
  569. case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
  570. case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
  571. return "HS_CLIENT_INTRO";
  572. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  573. case CIRCUIT_PURPOSE_C_REND_READY:
  574. case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
  575. case CIRCUIT_PURPOSE_C_REND_JOINED:
  576. return "HS_CLIENT_REND";
  577. case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
  578. case CIRCUIT_PURPOSE_S_INTRO:
  579. return "HS_SERVICE_INTRO";
  580. case CIRCUIT_PURPOSE_S_CONNECT_REND:
  581. case CIRCUIT_PURPOSE_S_REND_JOINED:
  582. return "HS_SERVICE_REND";
  583. case CIRCUIT_PURPOSE_TESTING:
  584. return "TESTING";
  585. case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
  586. return "MEASURE_TIMEOUT";
  587. case CIRCUIT_PURPOSE_CONTROLLER:
  588. return "CONTROLLER";
  589. case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
  590. return "PATH_BIAS_TESTING";
  591. default:
  592. tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
  593. return buf;
  594. }
  595. }
  596. /** Return a string specifying the state of the hidden-service circuit
  597. * purpose <b>purpose</b>, or NULL if <b>purpose</b> is not a
  598. * hidden-service-related circuit purpose. */
  599. const char *
  600. circuit_purpose_to_controller_hs_state_string(uint8_t purpose)
  601. {
  602. switch (purpose)
  603. {
  604. default:
  605. log_fn(LOG_WARN, LD_BUG,
  606. "Unrecognized circuit purpose: %d",
  607. (int)purpose);
  608. tor_fragile_assert();
  609. /* fall through */
  610. case CIRCUIT_PURPOSE_OR:
  611. case CIRCUIT_PURPOSE_C_GENERAL:
  612. case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
  613. case CIRCUIT_PURPOSE_TESTING:
  614. case CIRCUIT_PURPOSE_CONTROLLER:
  615. case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
  616. return NULL;
  617. case CIRCUIT_PURPOSE_INTRO_POINT:
  618. return "OR_HSSI_ESTABLISHED";
  619. case CIRCUIT_PURPOSE_REND_POINT_WAITING:
  620. return "OR_HSCR_ESTABLISHED";
  621. case CIRCUIT_PURPOSE_REND_ESTABLISHED:
  622. return "OR_HS_R_JOINED";
  623. case CIRCUIT_PURPOSE_C_INTRODUCING:
  624. return "HSCI_CONNECTING";
  625. case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
  626. return "HSCI_INTRO_SENT";
  627. case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
  628. return "HSCI_DONE";
  629. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  630. return "HSCR_CONNECTING";
  631. case CIRCUIT_PURPOSE_C_REND_READY:
  632. return "HSCR_ESTABLISHED_IDLE";
  633. case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
  634. return "HSCR_ESTABLISHED_WAITING";
  635. case CIRCUIT_PURPOSE_C_REND_JOINED:
  636. return "HSCR_JOINED";
  637. case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
  638. return "HSSI_CONNECTING";
  639. case CIRCUIT_PURPOSE_S_INTRO:
  640. return "HSSI_ESTABLISHED";
  641. case CIRCUIT_PURPOSE_S_CONNECT_REND:
  642. return "HSSR_CONNECTING";
  643. case CIRCUIT_PURPOSE_S_REND_JOINED:
  644. return "HSSR_JOINED";
  645. }
  646. }
  647. /** Return a human-readable string for the circuit purpose <b>purpose</b>. */
  648. const char *
  649. circuit_purpose_to_string(uint8_t purpose)
  650. {
  651. static char buf[32];
  652. switch (purpose)
  653. {
  654. case CIRCUIT_PURPOSE_OR:
  655. return "Circuit at relay";
  656. case CIRCUIT_PURPOSE_INTRO_POINT:
  657. return "Acting as intro point";
  658. case CIRCUIT_PURPOSE_REND_POINT_WAITING:
  659. return "Acting as rendevous (pending)";
  660. case CIRCUIT_PURPOSE_REND_ESTABLISHED:
  661. return "Acting as rendevous (established)";
  662. case CIRCUIT_PURPOSE_C_GENERAL:
  663. return "General-purpose client";
  664. case CIRCUIT_PURPOSE_C_INTRODUCING:
  665. return "Hidden service client: Connecting to intro point";
  666. case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
  667. return "Hidden service client: Waiting for ack from intro point";
  668. case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
  669. return "Hidden service client: Received ack from intro point";
  670. case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
  671. return "Hidden service client: Establishing rendezvous point";
  672. case CIRCUIT_PURPOSE_C_REND_READY:
  673. return "Hidden service client: Pending rendezvous point";
  674. case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
  675. return "Hidden service client: Pending rendezvous point (ack received)";
  676. case CIRCUIT_PURPOSE_C_REND_JOINED:
  677. return "Hidden service client: Active rendezvous point";
  678. case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
  679. return "Measuring circuit timeout";
  680. case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
  681. return "Hidden service: Establishing introduction point";
  682. case CIRCUIT_PURPOSE_S_INTRO:
  683. return "Hidden service: Introduction point";
  684. case CIRCUIT_PURPOSE_S_CONNECT_REND:
  685. return "Hidden service: Connecting to rendezvous point";
  686. case CIRCUIT_PURPOSE_S_REND_JOINED:
  687. return "Hidden service: Active rendezvous point";
  688. case CIRCUIT_PURPOSE_TESTING:
  689. return "Testing circuit";
  690. case CIRCUIT_PURPOSE_CONTROLLER:
  691. return "Circuit made by controller";
  692. case CIRCUIT_PURPOSE_PATH_BIAS_TESTING:
  693. return "Path-bias testing circuit";
  694. default:
  695. tor_snprintf(buf, sizeof(buf), "UNKNOWN_%d", (int)purpose);
  696. return buf;
  697. }
  698. }
  699. /** Pick a reasonable package_window to start out for our circuits.
  700. * Originally this was hard-coded at 1000, but now the consensus votes
  701. * on the answer. See proposal 168. */
  702. int32_t
  703. circuit_initial_package_window(void)
  704. {
  705. int32_t num = networkstatus_get_param(NULL, "circwindow", CIRCWINDOW_START,
  706. CIRCWINDOW_START_MIN,
  707. CIRCWINDOW_START_MAX);
  708. /* If the consensus tells us a negative number, we'd assert. */
  709. if (num < 0)
  710. num = CIRCWINDOW_START;
  711. return num;
  712. }
  713. /** Initialize the common elements in a circuit_t, and add it to the global
  714. * list. */
  715. static void
  716. init_circuit_base(circuit_t *circ)
  717. {
  718. tor_gettimeofday(&circ->timestamp_created);
  719. // Gets reset when we send CREATE_FAST.
  720. // circuit_expire_building() expects these to be equal
  721. // until the orconn is built.
  722. circ->timestamp_began = circ->timestamp_created;
  723. circ->package_window = circuit_initial_package_window();
  724. circ->deliver_window = CIRCWINDOW_START;
  725. cell_queue_init(&circ->n_chan_cells);
  726. smartlist_add(circuit_get_global_list(), circ);
  727. circ->global_circuitlist_idx = smartlist_len(circuit_get_global_list()) - 1;
  728. }
  729. /** If we haven't yet decided on a good timeout value for circuit
  730. * building, we close idle circuits aggressively so we can get more
  731. * data points. */
  732. #define IDLE_TIMEOUT_WHILE_LEARNING (1*60)
  733. /** Allocate space for a new circuit, initializing with <b>p_circ_id</b>
  734. * and <b>p_conn</b>. Add it to the global circuit list.
  735. */
  736. origin_circuit_t *
  737. origin_circuit_new(void)
  738. {
  739. origin_circuit_t *circ;
  740. /* never zero, since a global ID of 0 is treated specially by the
  741. * controller */
  742. static uint32_t n_circuits_allocated = 1;
  743. circ = tor_malloc_zero(sizeof(origin_circuit_t));
  744. circ->base_.magic = ORIGIN_CIRCUIT_MAGIC;
  745. circ->next_stream_id = crypto_rand_int(1<<16);
  746. circ->global_identifier = n_circuits_allocated++;
  747. circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
  748. circ->remaining_relay_early_cells -= crypto_rand_int(2);
  749. init_circuit_base(TO_CIRCUIT(circ));
  750. /* Add to origin-list. */
  751. circ->global_origin_circuit_list_idx = -1;
  752. circuit_add_to_origin_circuit_list(circ);
  753. circuit_build_times_update_last_circ(get_circuit_build_times_mutable());
  754. if (! circuit_build_times_disabled(get_options()) &&
  755. circuit_build_times_needs_circuits(get_circuit_build_times())) {
  756. /* Circuits should be shorter lived if we need more of them
  757. * for learning a good build timeout */
  758. circ->circuit_idle_timeout = IDLE_TIMEOUT_WHILE_LEARNING;
  759. } else {
  760. // This should always be larger than the current port prediction time
  761. // remaining, or else we'll end up with the case where a circuit times out
  762. // and another one is built, effectively doubling the timeout window.
  763. //
  764. // We also randomize it by up to 5% more (ie 5% of 0 to 3600 seconds,
  765. // depending on how much circuit prediction time is remaining) so that
  766. // we don't close a bunch of unused circuits all at the same time.
  767. int prediction_time_remaining =
  768. predicted_ports_prediction_time_remaining(time(NULL));
  769. circ->circuit_idle_timeout = prediction_time_remaining+1+
  770. crypto_rand_int(1+prediction_time_remaining/20);
  771. if (circ->circuit_idle_timeout <= 0) {
  772. log_warn(LD_BUG,
  773. "Circuit chose a negative idle timeout of %d based on "
  774. "%d seconds of predictive building remaining.",
  775. circ->circuit_idle_timeout,
  776. prediction_time_remaining);
  777. circ->circuit_idle_timeout = IDLE_TIMEOUT_WHILE_LEARNING;
  778. }
  779. log_info(LD_CIRC,
  780. "Circuit " U64_FORMAT " chose an idle timeout of %d based on "
  781. "%d seconds of predictive building remaining.",
  782. U64_PRINTF_ARG(circ->global_identifier),
  783. circ->circuit_idle_timeout,
  784. prediction_time_remaining);
  785. }
  786. return circ;
  787. }
  788. /** Allocate a new or_circuit_t, connected to <b>p_chan</b> as
  789. * <b>p_circ_id</b>. If <b>p_chan</b> is NULL, the circuit is unattached. */
  790. or_circuit_t *
  791. or_circuit_new(circid_t p_circ_id, channel_t *p_chan)
  792. {
  793. /* CircIDs */
  794. or_circuit_t *circ;
  795. circ = tor_malloc_zero(sizeof(or_circuit_t));
  796. circ->base_.magic = OR_CIRCUIT_MAGIC;
  797. if (p_chan)
  798. circuit_set_p_circid_chan(circ, p_circ_id, p_chan);
  799. circ->remaining_relay_early_cells = MAX_RELAY_EARLY_CELLS_PER_CIRCUIT;
  800. cell_queue_init(&circ->p_chan_cells);
  801. init_circuit_base(TO_CIRCUIT(circ));
  802. return circ;
  803. }
  804. /** Free all storage held in circ->testing_cell_stats */
  805. void
  806. circuit_clear_testing_cell_stats(circuit_t *circ)
  807. {
  808. if (!circ || !circ->testing_cell_stats)
  809. return;
  810. SMARTLIST_FOREACH(circ->testing_cell_stats, testing_cell_stats_entry_t *,
  811. ent, tor_free(ent));
  812. smartlist_free(circ->testing_cell_stats);
  813. circ->testing_cell_stats = NULL;
  814. }
  815. /** Deallocate space associated with circ.
  816. */
  817. STATIC void
  818. circuit_free(circuit_t *circ)
  819. {
  820. void *mem;
  821. size_t memlen;
  822. int should_free = 1;
  823. if (!circ)
  824. return;
  825. circuit_clear_testing_cell_stats(circ);
  826. if (CIRCUIT_IS_ORIGIN(circ)) {
  827. origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
  828. mem = ocirc;
  829. memlen = sizeof(origin_circuit_t);
  830. tor_assert(circ->magic == ORIGIN_CIRCUIT_MAGIC);
  831. circuit_remove_from_origin_circuit_list(ocirc);
  832. if (ocirc->build_state) {
  833. extend_info_free(ocirc->build_state->chosen_exit);
  834. circuit_free_cpath_node(ocirc->build_state->pending_final_cpath);
  835. cpath_ref_decref(ocirc->build_state->service_pending_final_cpath_ref);
  836. }
  837. tor_free(ocirc->build_state);
  838. /* Cancel before freeing, if we haven't already succeeded or failed. */
  839. if (ocirc->guard_state) {
  840. entry_guard_cancel(&ocirc->guard_state);
  841. }
  842. circuit_guard_state_free(ocirc->guard_state);
  843. circuit_clear_cpath(ocirc);
  844. crypto_pk_free(ocirc->intro_key);
  845. rend_data_free(ocirc->rend_data);
  846. tor_free(ocirc->dest_address);
  847. if (ocirc->socks_username) {
  848. memwipe(ocirc->socks_username, 0x12, ocirc->socks_username_len);
  849. tor_free(ocirc->socks_username);
  850. }
  851. if (ocirc->socks_password) {
  852. memwipe(ocirc->socks_password, 0x06, ocirc->socks_password_len);
  853. tor_free(ocirc->socks_password);
  854. }
  855. addr_policy_list_free(ocirc->prepend_policy);
  856. } else {
  857. or_circuit_t *ocirc = TO_OR_CIRCUIT(circ);
  858. /* Remember cell statistics for this circuit before deallocating. */
  859. if (get_options()->CellStatistics)
  860. rep_hist_buffer_stats_add_circ(circ, time(NULL));
  861. mem = ocirc;
  862. memlen = sizeof(or_circuit_t);
  863. tor_assert(circ->magic == OR_CIRCUIT_MAGIC);
  864. should_free = (ocirc->workqueue_entry == NULL);
  865. crypto_cipher_free(ocirc->p_crypto);
  866. crypto_digest_free(ocirc->p_digest);
  867. crypto_cipher_free(ocirc->n_crypto);
  868. crypto_digest_free(ocirc->n_digest);
  869. if (ocirc->rend_splice) {
  870. or_circuit_t *other = ocirc->rend_splice;
  871. tor_assert(other->base_.magic == OR_CIRCUIT_MAGIC);
  872. other->rend_splice = NULL;
  873. }
  874. /* remove from map. */
  875. circuit_set_p_circid_chan(ocirc, 0, NULL);
  876. /* Clear cell queue _after_ removing it from the map. Otherwise our
  877. * "active" checks will be violated. */
  878. cell_queue_clear(&ocirc->p_chan_cells);
  879. }
  880. extend_info_free(circ->n_hop);
  881. tor_free(circ->n_chan_create_cell);
  882. if (circ->global_circuitlist_idx != -1) {
  883. int idx = circ->global_circuitlist_idx;
  884. circuit_t *c2 = smartlist_get(global_circuitlist, idx);
  885. tor_assert(c2 == circ);
  886. smartlist_del(global_circuitlist, idx);
  887. if (idx < smartlist_len(global_circuitlist)) {
  888. c2 = smartlist_get(global_circuitlist, idx);
  889. c2->global_circuitlist_idx = idx;
  890. }
  891. }
  892. /* Remove from map. */
  893. circuit_set_n_circid_chan(circ, 0, NULL);
  894. /* Clear HS circuitmap token from this circ (if any) */
  895. if (circ->hs_token) {
  896. hs_circuitmap_remove_circuit(circ);
  897. }
  898. /* Clear cell queue _after_ removing it from the map. Otherwise our
  899. * "active" checks will be violated. */
  900. cell_queue_clear(&circ->n_chan_cells);
  901. if (should_free) {
  902. memwipe(mem, 0xAA, memlen); /* poison memory */
  903. tor_free(mem);
  904. } else {
  905. /* If we made it here, this is an or_circuit_t that still has a pending
  906. * cpuworker request which we weren't able to cancel. Instead, set up
  907. * the magic value so that when the reply comes back, we'll know to discard
  908. * the reply and free this structure.
  909. */
  910. memwipe(mem, 0xAA, memlen);
  911. circ->magic = DEAD_CIRCUIT_MAGIC;
  912. }
  913. }
  914. /** Deallocate the linked list circ-><b>cpath</b>, and remove the cpath from
  915. * <b>circ</b>. */
  916. void
  917. circuit_clear_cpath(origin_circuit_t *circ)
  918. {
  919. crypt_path_t *victim, *head, *cpath;
  920. head = cpath = circ->cpath;
  921. if (!cpath)
  922. return;
  923. /* it's a circular list, so we have to notice when we've
  924. * gone through it once. */
  925. while (cpath->next && cpath->next != head) {
  926. victim = cpath;
  927. cpath = victim->next;
  928. circuit_free_cpath_node(victim);
  929. }
  930. circuit_free_cpath_node(cpath);
  931. circ->cpath = NULL;
  932. }
  933. /** Release all storage held by circuits. */
  934. void
  935. circuit_free_all(void)
  936. {
  937. smartlist_t *lst = circuit_get_global_list();
  938. SMARTLIST_FOREACH_BEGIN(lst, circuit_t *, tmp) {
  939. if (! CIRCUIT_IS_ORIGIN(tmp)) {
  940. or_circuit_t *or_circ = TO_OR_CIRCUIT(tmp);
  941. while (or_circ->resolving_streams) {
  942. edge_connection_t *next_conn;
  943. next_conn = or_circ->resolving_streams->next_stream;
  944. connection_free(TO_CONN(or_circ->resolving_streams));
  945. or_circ->resolving_streams = next_conn;
  946. }
  947. }
  948. tmp->global_circuitlist_idx = -1;
  949. circuit_about_to_free_atexit(tmp);
  950. circuit_free(tmp);
  951. SMARTLIST_DEL_CURRENT(lst, tmp);
  952. } SMARTLIST_FOREACH_END(tmp);
  953. smartlist_free(lst);
  954. global_circuitlist = NULL;
  955. smartlist_free(global_origin_circuit_list);
  956. global_origin_circuit_list = NULL;
  957. smartlist_free(circuits_pending_chans);
  958. circuits_pending_chans = NULL;
  959. smartlist_free(circuits_pending_close);
  960. circuits_pending_close = NULL;
  961. smartlist_free(circuits_pending_other_guards);
  962. circuits_pending_other_guards = NULL;
  963. {
  964. chan_circid_circuit_map_t **elt, **next, *c;
  965. for (elt = HT_START(chan_circid_map, &chan_circid_map);
  966. elt;
  967. elt = next) {
  968. c = *elt;
  969. next = HT_NEXT_RMV(chan_circid_map, &chan_circid_map, elt);
  970. tor_assert(c->circuit == NULL);
  971. tor_free(c);
  972. }
  973. }
  974. HT_CLEAR(chan_circid_map, &chan_circid_map);
  975. }
  976. /** Deallocate space associated with the cpath node <b>victim</b>. */
  977. static void
  978. circuit_free_cpath_node(crypt_path_t *victim)
  979. {
  980. if (!victim)
  981. return;
  982. crypto_cipher_free(victim->f_crypto);
  983. crypto_cipher_free(victim->b_crypto);
  984. crypto_digest_free(victim->f_digest);
  985. crypto_digest_free(victim->b_digest);
  986. onion_handshake_state_release(&victim->handshake_state);
  987. crypto_dh_free(victim->rend_dh_handshake_state);
  988. extend_info_free(victim->extend_info);
  989. memwipe(victim, 0xBB, sizeof(crypt_path_t)); /* poison memory */
  990. tor_free(victim);
  991. }
  992. /** Release a crypt_path_reference_t*, which may be NULL. */
  993. static void
  994. cpath_ref_decref(crypt_path_reference_t *cpath_ref)
  995. {
  996. if (cpath_ref != NULL) {
  997. if (--(cpath_ref->refcount) == 0) {
  998. circuit_free_cpath_node(cpath_ref->cpath);
  999. tor_free(cpath_ref);
  1000. }
  1001. }
  1002. }
  1003. /** A helper function for circuit_dump_by_conn() below. Log a bunch
  1004. * of information about circuit <b>circ</b>.
  1005. */
  1006. static void
  1007. circuit_dump_conn_details(int severity,
  1008. circuit_t *circ,
  1009. int conn_array_index,
  1010. const char *type,
  1011. circid_t this_circid,
  1012. circid_t other_circid)
  1013. {
  1014. tor_log(severity, LD_CIRC, "Conn %d has %s circuit: circID %u "
  1015. "(other side %u), state %d (%s), born %ld:",
  1016. conn_array_index, type, (unsigned)this_circid, (unsigned)other_circid,
  1017. circ->state, circuit_state_to_string(circ->state),
  1018. (long)circ->timestamp_began.tv_sec);
  1019. if (CIRCUIT_IS_ORIGIN(circ)) { /* circ starts at this node */
  1020. circuit_log_path(severity, LD_CIRC, TO_ORIGIN_CIRCUIT(circ));
  1021. }
  1022. }
  1023. /** Log, at severity <b>severity</b>, information about each circuit
  1024. * that is connected to <b>conn</b>.
  1025. */
  1026. void
  1027. circuit_dump_by_conn(connection_t *conn, int severity)
  1028. {
  1029. edge_connection_t *tmpconn;
  1030. SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
  1031. circid_t n_circ_id = circ->n_circ_id, p_circ_id = 0;
  1032. if (circ->marked_for_close) {
  1033. continue;
  1034. }
  1035. if (!CIRCUIT_IS_ORIGIN(circ)) {
  1036. p_circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
  1037. }
  1038. if (CIRCUIT_IS_ORIGIN(circ)) {
  1039. for (tmpconn=TO_ORIGIN_CIRCUIT(circ)->p_streams; tmpconn;
  1040. tmpconn=tmpconn->next_stream) {
  1041. if (TO_CONN(tmpconn) == conn) {
  1042. circuit_dump_conn_details(severity, circ, conn->conn_array_index,
  1043. "App-ward", p_circ_id, n_circ_id);
  1044. }
  1045. }
  1046. }
  1047. if (! CIRCUIT_IS_ORIGIN(circ)) {
  1048. for (tmpconn=TO_OR_CIRCUIT(circ)->n_streams; tmpconn;
  1049. tmpconn=tmpconn->next_stream) {
  1050. if (TO_CONN(tmpconn) == conn) {
  1051. circuit_dump_conn_details(severity, circ, conn->conn_array_index,
  1052. "Exit-ward", n_circ_id, p_circ_id);
  1053. }
  1054. }
  1055. }
  1056. }
  1057. SMARTLIST_FOREACH_END(circ);
  1058. }
  1059. /** Return the circuit whose global ID is <b>id</b>, or NULL if no
  1060. * such circuit exists. */
  1061. origin_circuit_t *
  1062. circuit_get_by_global_id(uint32_t id)
  1063. {
  1064. SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
  1065. if (CIRCUIT_IS_ORIGIN(circ) &&
  1066. TO_ORIGIN_CIRCUIT(circ)->global_identifier == id) {
  1067. if (circ->marked_for_close)
  1068. return NULL;
  1069. else
  1070. return TO_ORIGIN_CIRCUIT(circ);
  1071. }
  1072. }
  1073. SMARTLIST_FOREACH_END(circ);
  1074. return NULL;
  1075. }
  1076. /** Return a circ such that:
  1077. * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
  1078. * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
  1079. * Return NULL if no such circuit exists.
  1080. *
  1081. * If <b>found_entry_out</b> is provided, set it to true if we have a
  1082. * placeholder entry for circid/chan, and leave it unset otherwise.
  1083. */
  1084. static inline circuit_t *
  1085. circuit_get_by_circid_channel_impl(circid_t circ_id, channel_t *chan,
  1086. int *found_entry_out)
  1087. {
  1088. chan_circid_circuit_map_t search;
  1089. chan_circid_circuit_map_t *found;
  1090. if (_last_circid_chan_ent &&
  1091. circ_id == _last_circid_chan_ent->circ_id &&
  1092. chan == _last_circid_chan_ent->chan) {
  1093. found = _last_circid_chan_ent;
  1094. } else {
  1095. search.circ_id = circ_id;
  1096. search.chan = chan;
  1097. found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
  1098. _last_circid_chan_ent = found;
  1099. }
  1100. if (found && found->circuit) {
  1101. log_debug(LD_CIRC,
  1102. "circuit_get_by_circid_channel_impl() returning circuit %p for"
  1103. " circ_id %u, channel ID " U64_FORMAT " (%p)",
  1104. found->circuit, (unsigned)circ_id,
  1105. U64_PRINTF_ARG(chan->global_identifier), chan);
  1106. if (found_entry_out)
  1107. *found_entry_out = 1;
  1108. return found->circuit;
  1109. }
  1110. log_debug(LD_CIRC,
  1111. "circuit_get_by_circid_channel_impl() found %s for"
  1112. " circ_id %u, channel ID " U64_FORMAT " (%p)",
  1113. found ? "placeholder" : "nothing",
  1114. (unsigned)circ_id,
  1115. U64_PRINTF_ARG(chan->global_identifier), chan);
  1116. if (found_entry_out)
  1117. *found_entry_out = found ? 1 : 0;
  1118. return NULL;
  1119. /* The rest of this checks for bugs. Disabled by default. */
  1120. /* We comment it out because coverity complains otherwise.
  1121. {
  1122. circuit_t *circ;
  1123. TOR_LIST_FOREACH(circ, &global_circuitlist, head) {
  1124. if (! CIRCUIT_IS_ORIGIN(circ)) {
  1125. or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
  1126. if (or_circ->p_chan == chan && or_circ->p_circ_id == circ_id) {
  1127. log_warn(LD_BUG,
  1128. "circuit matches p_chan, but not in hash table (Bug!)");
  1129. return circ;
  1130. }
  1131. }
  1132. if (circ->n_chan == chan && circ->n_circ_id == circ_id) {
  1133. log_warn(LD_BUG,
  1134. "circuit matches n_chan, but not in hash table (Bug!)");
  1135. return circ;
  1136. }
  1137. }
  1138. return NULL;
  1139. } */
  1140. }
  1141. /** Return a circ such that:
  1142. * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
  1143. * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
  1144. * - circ is not marked for close.
  1145. * Return NULL if no such circuit exists.
  1146. */
  1147. circuit_t *
  1148. circuit_get_by_circid_channel(circid_t circ_id, channel_t *chan)
  1149. {
  1150. circuit_t *circ = circuit_get_by_circid_channel_impl(circ_id, chan, NULL);
  1151. if (!circ || circ->marked_for_close)
  1152. return NULL;
  1153. else
  1154. return circ;
  1155. }
  1156. /** Return a circ such that:
  1157. * - circ-\>n_circ_id or circ-\>p_circ_id is equal to <b>circ_id</b>, and
  1158. * - circ is attached to <b>chan</b>, either as p_chan or n_chan.
  1159. * Return NULL if no such circuit exists.
  1160. */
  1161. circuit_t *
  1162. circuit_get_by_circid_channel_even_if_marked(circid_t circ_id,
  1163. channel_t *chan)
  1164. {
  1165. return circuit_get_by_circid_channel_impl(circ_id, chan, NULL);
  1166. }
  1167. /** Return true iff the circuit ID <b>circ_id</b> is currently used by a
  1168. * circuit, marked or not, on <b>chan</b>, or if the circ ID is reserved until
  1169. * a queued destroy cell can be sent.
  1170. *
  1171. * (Return 1 if the circuit is present, marked or not; Return 2
  1172. * if the circuit ID is pending a destroy.)
  1173. **/
  1174. int
  1175. circuit_id_in_use_on_channel(circid_t circ_id, channel_t *chan)
  1176. {
  1177. int found = 0;
  1178. if (circuit_get_by_circid_channel_impl(circ_id, chan, &found) != NULL)
  1179. return 1;
  1180. if (found)
  1181. return 2;
  1182. return 0;
  1183. }
  1184. /** Helper for debugging 12184. Returns the time since which 'circ_id' has
  1185. * been marked unusable on 'chan'. */
  1186. time_t
  1187. circuit_id_when_marked_unusable_on_channel(circid_t circ_id, channel_t *chan)
  1188. {
  1189. chan_circid_circuit_map_t search;
  1190. chan_circid_circuit_map_t *found;
  1191. memset(&search, 0, sizeof(search));
  1192. search.circ_id = circ_id;
  1193. search.chan = chan;
  1194. found = HT_FIND(chan_circid_map, &chan_circid_map, &search);
  1195. if (! found || found->circuit)
  1196. return 0;
  1197. return found->made_placeholder_at;
  1198. }
  1199. /** Return the circuit that a given edge connection is using. */
  1200. circuit_t *
  1201. circuit_get_by_edge_conn(edge_connection_t *conn)
  1202. {
  1203. circuit_t *circ;
  1204. circ = conn->on_circuit;
  1205. tor_assert(!circ ||
  1206. (CIRCUIT_IS_ORIGIN(circ) ? circ->magic == ORIGIN_CIRCUIT_MAGIC
  1207. : circ->magic == OR_CIRCUIT_MAGIC));
  1208. return circ;
  1209. }
  1210. /** For each circuit that has <b>chan</b> as n_chan or p_chan, unlink the
  1211. * circuit from the chan,circid map, and mark it for close if it hasn't
  1212. * been marked already.
  1213. */
  1214. void
  1215. circuit_unlink_all_from_channel(channel_t *chan, int reason)
  1216. {
  1217. smartlist_t *detached = smartlist_new();
  1218. /* #define DEBUG_CIRCUIT_UNLINK_ALL */
  1219. channel_unlink_all_circuits(chan, detached);
  1220. #ifdef DEBUG_CIRCUIT_UNLINK_ALL
  1221. {
  1222. smartlist_t *detached_2 = smartlist_new();
  1223. int mismatch = 0, badlen = 0;
  1224. SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
  1225. if (circ->n_chan == chan ||
  1226. (!CIRCUIT_IS_ORIGIN(circ) &&
  1227. TO_OR_CIRCUIT(circ)->p_chan == chan)) {
  1228. smartlist_add(detached_2, circ);
  1229. }
  1230. }
  1231. SMARTLIST_FOREACH_END(circ);
  1232. if (smartlist_len(detached) != smartlist_len(detached_2)) {
  1233. log_warn(LD_BUG, "List of detached circuits had the wrong length! "
  1234. "(got %d, should have gotten %d)",
  1235. (int)smartlist_len(detached),
  1236. (int)smartlist_len(detached_2));
  1237. badlen = 1;
  1238. }
  1239. smartlist_sort_pointers(detached);
  1240. smartlist_sort_pointers(detached_2);
  1241. SMARTLIST_FOREACH(detached, circuit_t *, c,
  1242. if (c != smartlist_get(detached_2, c_sl_idx))
  1243. mismatch = 1;
  1244. );
  1245. if (mismatch)
  1246. log_warn(LD_BUG, "Mismatch in list of detached circuits.");
  1247. if (badlen || mismatch) {
  1248. smartlist_free(detached);
  1249. detached = detached_2;
  1250. } else {
  1251. log_notice(LD_CIRC, "List of %d circuits was as expected.",
  1252. (int)smartlist_len(detached));
  1253. smartlist_free(detached_2);
  1254. }
  1255. }
  1256. #endif
  1257. SMARTLIST_FOREACH_BEGIN(detached, circuit_t *, circ) {
  1258. int mark = 0;
  1259. if (circ->n_chan == chan) {
  1260. circuit_set_n_circid_chan(circ, 0, NULL);
  1261. mark = 1;
  1262. /* If we didn't request this closure, pass the remote
  1263. * bit to mark_for_close. */
  1264. if (chan->reason_for_closing != CHANNEL_CLOSE_REQUESTED)
  1265. reason |= END_CIRC_REASON_FLAG_REMOTE;
  1266. }
  1267. if (! CIRCUIT_IS_ORIGIN(circ)) {
  1268. or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
  1269. if (or_circ->p_chan == chan) {
  1270. circuit_set_p_circid_chan(or_circ, 0, NULL);
  1271. mark = 1;
  1272. }
  1273. }
  1274. if (!mark) {
  1275. log_warn(LD_BUG, "Circuit on detached list which I had no reason "
  1276. "to mark");
  1277. continue;
  1278. }
  1279. if (!circ->marked_for_close)
  1280. circuit_mark_for_close(circ, reason);
  1281. } SMARTLIST_FOREACH_END(circ);
  1282. smartlist_free(detached);
  1283. }
  1284. /** Return a circ such that
  1285. * - circ-\>rend_data-\>onion_address is equal to
  1286. * <b>rend_data</b>-\>onion_address,
  1287. * - circ-\>rend_data-\>rend_cookie is equal to
  1288. * <b>rend_data</b>-\>rend_cookie, and
  1289. * - circ-\>purpose is equal to CIRCUIT_PURPOSE_C_REND_READY.
  1290. *
  1291. * Return NULL if no such circuit exists.
  1292. */
  1293. origin_circuit_t *
  1294. circuit_get_ready_rend_circ_by_rend_data(const rend_data_t *rend_data)
  1295. {
  1296. SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
  1297. if (!circ->marked_for_close &&
  1298. circ->purpose == CIRCUIT_PURPOSE_C_REND_READY) {
  1299. origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
  1300. if (ocirc->rend_data == NULL) {
  1301. continue;
  1302. }
  1303. if (!rend_cmp_service_ids(rend_data_get_address(rend_data),
  1304. rend_data_get_address(ocirc->rend_data)) &&
  1305. tor_memeq(ocirc->rend_data->rend_cookie,
  1306. rend_data->rend_cookie,
  1307. REND_COOKIE_LEN))
  1308. return ocirc;
  1309. }
  1310. }
  1311. SMARTLIST_FOREACH_END(circ);
  1312. return NULL;
  1313. }
  1314. /** Return the first service introduction circuit originating from the global
  1315. * circuit list after <b>start</b> or at the start of the list if <b>start</b>
  1316. * is NULL. Return NULL if no circuit is found.
  1317. *
  1318. * A service introduction point circuit has a purpose of either
  1319. * CIRCUIT_PURPOSE_S_ESTABLISH_INTRO or CIRCUIT_PURPOSE_S_INTRO. This does not
  1320. * return a circuit marked for close and its state must be open. */
  1321. origin_circuit_t *
  1322. circuit_get_next_service_intro_circ(origin_circuit_t *start)
  1323. {
  1324. int idx = 0;
  1325. smartlist_t *lst = circuit_get_global_list();
  1326. if (start) {
  1327. idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1;
  1328. }
  1329. for ( ; idx < smartlist_len(lst); ++idx) {
  1330. circuit_t *circ = smartlist_get(lst, idx);
  1331. /* Ignore a marked for close circuit or purpose not matching a service
  1332. * intro point or if the state is not open. */
  1333. if (circ->marked_for_close || circ->state != CIRCUIT_STATE_OPEN ||
  1334. (circ->purpose != CIRCUIT_PURPOSE_S_ESTABLISH_INTRO &&
  1335. circ->purpose != CIRCUIT_PURPOSE_S_INTRO)) {
  1336. continue;
  1337. }
  1338. /* The purposes we are looking for are only for origin circuits so the
  1339. * following is valid. */
  1340. return TO_ORIGIN_CIRCUIT(circ);
  1341. }
  1342. /* Not found. */
  1343. return NULL;
  1344. }
  1345. /** Return the first circuit originating here in global_circuitlist after
  1346. * <b>start</b> whose purpose is <b>purpose</b>, and where <b>digest</b> (if
  1347. * set) matches the private key digest of the rend data associated with the
  1348. * circuit. Return NULL if no circuit is found. If <b>start</b> is NULL,
  1349. * begin at the start of the list.
  1350. */
  1351. origin_circuit_t *
  1352. circuit_get_next_by_pk_and_purpose(origin_circuit_t *start,
  1353. const uint8_t *digest, uint8_t purpose)
  1354. {
  1355. int idx;
  1356. smartlist_t *lst = circuit_get_global_list();
  1357. tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(purpose));
  1358. if (start == NULL)
  1359. idx = 0;
  1360. else
  1361. idx = TO_CIRCUIT(start)->global_circuitlist_idx + 1;
  1362. for ( ; idx < smartlist_len(lst); ++idx) {
  1363. circuit_t *circ = smartlist_get(lst, idx);
  1364. origin_circuit_t *ocirc;
  1365. if (circ->marked_for_close)
  1366. continue;
  1367. if (circ->purpose != purpose)
  1368. continue;
  1369. /* At this point we should be able to get a valid origin circuit because
  1370. * the origin purpose we are looking for matches this circuit. */
  1371. if (BUG(!CIRCUIT_PURPOSE_IS_ORIGIN(circ->purpose))) {
  1372. break;
  1373. }
  1374. ocirc = TO_ORIGIN_CIRCUIT(circ);
  1375. if (!digest)
  1376. return ocirc;
  1377. if (rend_circuit_pk_digest_eq(ocirc, digest)) {
  1378. return ocirc;
  1379. }
  1380. }
  1381. return NULL;
  1382. }
  1383. /** Return a circuit that is open, is CIRCUIT_PURPOSE_C_GENERAL,
  1384. * has a timestamp_dirty value of 0, has flags matching the CIRCLAUNCH_*
  1385. * flags in <b>flags</b>, and if info is defined, does not already use info
  1386. * as any of its hops; or NULL if no circuit fits this description.
  1387. *
  1388. * The <b>purpose</b> argument (currently ignored) refers to the purpose of
  1389. * the circuit we want to create, not the purpose of the circuit we want to
  1390. * cannibalize.
  1391. *
  1392. * If !CIRCLAUNCH_NEED_UPTIME, prefer returning non-uptime circuits.
  1393. *
  1394. * To "cannibalize" a circuit means to extend it an extra hop, and use it
  1395. * for some other purpose than we had originally intended. We do this when
  1396. * we want to perform some low-bandwidth task at a specific relay, and we
  1397. * would like the circuit to complete as soon as possible. (If we were going
  1398. * to use a lot of bandwidth, we wouldn't want a circuit with an extra hop.
  1399. * If we didn't care about circuit completion latency, we would just build
  1400. * a new circuit.)
  1401. */
  1402. origin_circuit_t *
  1403. circuit_find_to_cannibalize(uint8_t purpose, extend_info_t *info,
  1404. int flags)
  1405. {
  1406. origin_circuit_t *best=NULL;
  1407. int need_uptime = (flags & CIRCLAUNCH_NEED_UPTIME) != 0;
  1408. int need_capacity = (flags & CIRCLAUNCH_NEED_CAPACITY) != 0;
  1409. int internal = (flags & CIRCLAUNCH_IS_INTERNAL) != 0;
  1410. const or_options_t *options = get_options();
  1411. /* Make sure we're not trying to create a onehop circ by
  1412. * cannibalization. */
  1413. tor_assert(!(flags & CIRCLAUNCH_ONEHOP_TUNNEL));
  1414. log_debug(LD_CIRC,
  1415. "Hunting for a circ to cannibalize: purpose %d, uptime %d, "
  1416. "capacity %d, internal %d",
  1417. purpose, need_uptime, need_capacity, internal);
  1418. SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ_) {
  1419. if (CIRCUIT_IS_ORIGIN(circ_) &&
  1420. circ_->state == CIRCUIT_STATE_OPEN &&
  1421. !circ_->marked_for_close &&
  1422. circ_->purpose == CIRCUIT_PURPOSE_C_GENERAL &&
  1423. !circ_->timestamp_dirty) {
  1424. origin_circuit_t *circ = TO_ORIGIN_CIRCUIT(circ_);
  1425. if ((!need_uptime || circ->build_state->need_uptime) &&
  1426. (!need_capacity || circ->build_state->need_capacity) &&
  1427. (internal == circ->build_state->is_internal) &&
  1428. !circ->unusable_for_new_conns &&
  1429. circ->remaining_relay_early_cells &&
  1430. circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN &&
  1431. !circ->build_state->onehop_tunnel &&
  1432. !circ->isolation_values_set) {
  1433. if (info) {
  1434. /* need to make sure we don't duplicate hops */
  1435. crypt_path_t *hop = circ->cpath;
  1436. const node_t *ri1 = node_get_by_id(info->identity_digest);
  1437. do {
  1438. const node_t *ri2;
  1439. if (tor_memeq(hop->extend_info->identity_digest,
  1440. info->identity_digest, DIGEST_LEN))
  1441. goto next;
  1442. if (ri1 &&
  1443. (ri2 = node_get_by_id(hop->extend_info->identity_digest))
  1444. && nodes_in_same_family(ri1, ri2))
  1445. goto next;
  1446. hop=hop->next;
  1447. } while (hop!=circ->cpath);
  1448. }
  1449. if (options->ExcludeNodes) {
  1450. /* Make sure no existing nodes in the circuit are excluded for
  1451. * general use. (This may be possible if StrictNodes is 0, and we
  1452. * thought we needed to use an otherwise excluded node for, say, a
  1453. * directory operation.) */
  1454. crypt_path_t *hop = circ->cpath;
  1455. do {
  1456. if (routerset_contains_extendinfo(options->ExcludeNodes,
  1457. hop->extend_info))
  1458. goto next;
  1459. hop = hop->next;
  1460. } while (hop != circ->cpath);
  1461. }
  1462. if (!best || (best->build_state->need_uptime && !need_uptime))
  1463. best = circ;
  1464. next: ;
  1465. }
  1466. }
  1467. }
  1468. SMARTLIST_FOREACH_END(circ_);
  1469. return best;
  1470. }
  1471. /**
  1472. * Check whether any of the origin circuits that are waiting to see if
  1473. * their guard is good enough to use can be upgraded to "ready". If so,
  1474. * return a new smartlist containing them. Otherwise return NULL.
  1475. */
  1476. smartlist_t *
  1477. circuit_find_circuits_to_upgrade_from_guard_wait(void)
  1478. {
  1479. /* Only if some circuit is actually waiting on an upgrade should we
  1480. * run the algorithm. */
  1481. if (! circuits_pending_other_guards ||
  1482. smartlist_len(circuits_pending_other_guards)==0)
  1483. return NULL;
  1484. /* Only if we have some origin circuits should we run the algorithm. */
  1485. if (!global_origin_circuit_list)
  1486. return NULL;
  1487. /* Okay; we can pass our circuit list to entrynodes.c.*/
  1488. smartlist_t *result = smartlist_new();
  1489. int circuits_upgraded = entry_guards_upgrade_waiting_circuits(
  1490. get_guard_selection_info(),
  1491. global_origin_circuit_list,
  1492. result);
  1493. if (circuits_upgraded && smartlist_len(result)) {
  1494. return result;
  1495. } else {
  1496. smartlist_free(result);
  1497. return NULL;
  1498. }
  1499. }
  1500. /** Return the number of hops in circuit's path. If circ has no entries,
  1501. * or is NULL, returns 0. */
  1502. int
  1503. circuit_get_cpath_len(origin_circuit_t *circ)
  1504. {
  1505. int n = 0;
  1506. if (circ && circ->cpath) {
  1507. crypt_path_t *cpath, *cpath_next = NULL;
  1508. for (cpath = circ->cpath; cpath_next != circ->cpath; cpath = cpath_next) {
  1509. cpath_next = cpath->next;
  1510. ++n;
  1511. }
  1512. }
  1513. return n;
  1514. }
  1515. /** Return the <b>hopnum</b>th hop in <b>circ</b>->cpath, or NULL if there
  1516. * aren't that many hops in the list. <b>hopnum</b> starts at 1.
  1517. * Returns NULL if <b>hopnum</b> is 0 or negative. */
  1518. crypt_path_t *
  1519. circuit_get_cpath_hop(origin_circuit_t *circ, int hopnum)
  1520. {
  1521. if (circ && circ->cpath && hopnum > 0) {
  1522. crypt_path_t *cpath, *cpath_next = NULL;
  1523. for (cpath = circ->cpath; cpath_next != circ->cpath; cpath = cpath_next) {
  1524. cpath_next = cpath->next;
  1525. if (--hopnum <= 0)
  1526. return cpath;
  1527. }
  1528. }
  1529. return NULL;
  1530. }
  1531. /** Go through the circuitlist; mark-for-close each circuit that starts
  1532. * at us but has not yet been used. */
  1533. void
  1534. circuit_mark_all_unused_circs(void)
  1535. {
  1536. SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
  1537. if (CIRCUIT_IS_ORIGIN(circ) &&
  1538. !circ->marked_for_close &&
  1539. !circ->timestamp_dirty)
  1540. circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
  1541. }
  1542. SMARTLIST_FOREACH_END(circ);
  1543. }
  1544. /** Go through the circuitlist; for each circuit that starts at us
  1545. * and is dirty, frob its timestamp_dirty so we won't use it for any
  1546. * new streams.
  1547. *
  1548. * This is useful for letting the user change pseudonyms, so new
  1549. * streams will not be linkable to old streams.
  1550. */
  1551. void
  1552. circuit_mark_all_dirty_circs_as_unusable(void)
  1553. {
  1554. SMARTLIST_FOREACH_BEGIN(circuit_get_global_list(), circuit_t *, circ) {
  1555. if (CIRCUIT_IS_ORIGIN(circ) &&
  1556. !circ->marked_for_close &&
  1557. circ->timestamp_dirty) {
  1558. mark_circuit_unusable_for_new_conns(TO_ORIGIN_CIRCUIT(circ));
  1559. }
  1560. }
  1561. SMARTLIST_FOREACH_END(circ);
  1562. }
  1563. /** Mark <b>circ</b> to be closed next time we call
  1564. * circuit_close_all_marked(). Do any cleanup needed:
  1565. * - If state is onionskin_pending, remove circ from the onion_pending
  1566. * list.
  1567. * - If circ isn't open yet: call circuit_build_failed() if we're
  1568. * the origin, and in either case call circuit_rep_hist_note_result()
  1569. * to note stats.
  1570. * - If purpose is C_INTRODUCE_ACK_WAIT, report the intro point
  1571. * failure we just had to the hidden service client module.
  1572. * - If purpose is C_INTRODUCING and <b>reason</b> isn't TIMEOUT,
  1573. * report to the hidden service client module that the intro point
  1574. * we just tried may be unreachable.
  1575. * - Send appropriate destroys and edge_destroys for conns and
  1576. * streams attached to circ.
  1577. * - If circ->rend_splice is set (we are the midpoint of a joined
  1578. * rendezvous stream), then mark the other circuit to close as well.
  1579. */
  1580. MOCK_IMPL(void,
  1581. circuit_mark_for_close_, (circuit_t *circ, int reason, int line,
  1582. const char *file))
  1583. {
  1584. int orig_reason = reason; /* Passed to the controller */
  1585. assert_circuit_ok(circ);
  1586. tor_assert(line);
  1587. tor_assert(file);
  1588. if (circ->marked_for_close) {
  1589. log_warn(LD_BUG,
  1590. "Duplicate call to circuit_mark_for_close at %s:%d"
  1591. " (first at %s:%d)", file, line,
  1592. circ->marked_for_close_file, circ->marked_for_close);
  1593. return;
  1594. }
  1595. if (reason == END_CIRC_AT_ORIGIN) {
  1596. if (!CIRCUIT_IS_ORIGIN(circ)) {
  1597. log_warn(LD_BUG, "Specified 'at-origin' non-reason for ending circuit, "
  1598. "but circuit was not at origin. (called %s:%d, purpose=%d)",
  1599. file, line, circ->purpose);
  1600. }
  1601. reason = END_CIRC_REASON_NONE;
  1602. }
  1603. if (CIRCUIT_IS_ORIGIN(circ)) {
  1604. if (pathbias_check_close(TO_ORIGIN_CIRCUIT(circ), reason) == -1) {
  1605. /* Don't close it yet, we need to test it first */
  1606. return;
  1607. }
  1608. /* We don't send reasons when closing circuits at the origin. */
  1609. reason = END_CIRC_REASON_NONE;
  1610. }
  1611. if (reason & END_CIRC_REASON_FLAG_REMOTE)
  1612. reason &= ~END_CIRC_REASON_FLAG_REMOTE;
  1613. if (reason < END_CIRC_REASON_MIN_ || reason > END_CIRC_REASON_MAX_) {
  1614. if (!(orig_reason & END_CIRC_REASON_FLAG_REMOTE))
  1615. log_warn(LD_BUG, "Reason %d out of range at %s:%d", reason, file, line);
  1616. reason = END_CIRC_REASON_NONE;
  1617. }
  1618. circ->marked_for_close = line;
  1619. circ->marked_for_close_file = file;
  1620. circ->marked_for_close_reason = reason;
  1621. circ->marked_for_close_orig_reason = orig_reason;
  1622. if (!CIRCUIT_IS_ORIGIN(circ)) {
  1623. or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
  1624. if (or_circ->rend_splice) {
  1625. if (!or_circ->rend_splice->base_.marked_for_close) {
  1626. /* do this after marking this circuit, to avoid infinite recursion. */
  1627. circuit_mark_for_close(TO_CIRCUIT(or_circ->rend_splice), reason);
  1628. }
  1629. or_circ->rend_splice = NULL;
  1630. }
  1631. }
  1632. if (circuits_pending_close == NULL)
  1633. circuits_pending_close = smartlist_new();
  1634. smartlist_add(circuits_pending_close, circ);
  1635. }
  1636. /** Called immediately before freeing a marked circuit <b>circ</b> from
  1637. * circuit_free_all() while shutting down Tor; this is a safe-at-shutdown
  1638. * version of circuit_about_to_free(). It's important that it at least
  1639. * do circuitmux_detach_circuit() when appropriate.
  1640. */
  1641. static void
  1642. circuit_about_to_free_atexit(circuit_t *circ)
  1643. {
  1644. if (circ->n_chan) {
  1645. circuit_clear_cell_queue(circ, circ->n_chan);
  1646. circuitmux_detach_circuit(circ->n_chan->cmux, circ);
  1647. circuit_set_n_circid_chan(circ, 0, NULL);
  1648. }
  1649. if (! CIRCUIT_IS_ORIGIN(circ)) {
  1650. or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
  1651. if (or_circ->p_chan) {
  1652. circuit_clear_cell_queue(circ, or_circ->p_chan);
  1653. circuitmux_detach_circuit(or_circ->p_chan->cmux, circ);
  1654. circuit_set_p_circid_chan(or_circ, 0, NULL);
  1655. }
  1656. }
  1657. }
  1658. /** Called immediately before freeing a marked circuit <b>circ</b>.
  1659. * Disconnects the circuit from other data structures, launches events
  1660. * as appropriate, and performs other housekeeping.
  1661. */
  1662. static void
  1663. circuit_about_to_free(circuit_t *circ)
  1664. {
  1665. int reason = circ->marked_for_close_reason;
  1666. int orig_reason = circ->marked_for_close_orig_reason;
  1667. if (circ->state == CIRCUIT_STATE_ONIONSKIN_PENDING) {
  1668. onion_pending_remove(TO_OR_CIRCUIT(circ));
  1669. }
  1670. /* If the circuit ever became OPEN, we sent it to the reputation history
  1671. * module then. If it isn't OPEN, we send it there now to remember which
  1672. * links worked and which didn't.
  1673. */
  1674. if (circ->state != CIRCUIT_STATE_OPEN &&
  1675. circ->state != CIRCUIT_STATE_GUARD_WAIT) {
  1676. if (CIRCUIT_IS_ORIGIN(circ)) {
  1677. origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
  1678. circuit_build_failed(ocirc); /* take actions if necessary */
  1679. circuit_rep_hist_note_result(ocirc);
  1680. }
  1681. }
  1682. if (circ->state == CIRCUIT_STATE_CHAN_WAIT) {
  1683. if (circuits_pending_chans)
  1684. smartlist_remove(circuits_pending_chans, circ);
  1685. }
  1686. if (circuits_pending_other_guards) {
  1687. smartlist_remove(circuits_pending_other_guards, circ);
  1688. }
  1689. if (CIRCUIT_IS_ORIGIN(circ)) {
  1690. control_event_circuit_status(TO_ORIGIN_CIRCUIT(circ),
  1691. (circ->state == CIRCUIT_STATE_OPEN ||
  1692. circ->state == CIRCUIT_STATE_GUARD_WAIT) ?
  1693. CIRC_EVENT_CLOSED:CIRC_EVENT_FAILED,
  1694. orig_reason);
  1695. }
  1696. if (circ->purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) {
  1697. origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
  1698. int timed_out = (reason == END_CIRC_REASON_TIMEOUT);
  1699. tor_assert(circ->state == CIRCUIT_STATE_OPEN);
  1700. tor_assert(ocirc->build_state->chosen_exit);
  1701. tor_assert(ocirc->rend_data);
  1702. if (orig_reason != END_CIRC_REASON_IP_NOW_REDUNDANT) {
  1703. /* treat this like getting a nack from it */
  1704. log_info(LD_REND, "Failed intro circ %s to %s (awaiting ack). %s",
  1705. safe_str_client(rend_data_get_address(ocirc->rend_data)),
  1706. safe_str_client(build_state_get_exit_nickname(ocirc->build_state)),
  1707. timed_out ? "Recording timeout." : "Removing from descriptor.");
  1708. rend_client_report_intro_point_failure(ocirc->build_state->chosen_exit,
  1709. ocirc->rend_data,
  1710. timed_out ?
  1711. INTRO_POINT_FAILURE_TIMEOUT :
  1712. INTRO_POINT_FAILURE_GENERIC);
  1713. }
  1714. } else if (circ->purpose == CIRCUIT_PURPOSE_C_INTRODUCING &&
  1715. reason != END_CIRC_REASON_TIMEOUT) {
  1716. origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
  1717. if (ocirc->build_state->chosen_exit && ocirc->rend_data) {
  1718. if (orig_reason != END_CIRC_REASON_IP_NOW_REDUNDANT) {
  1719. log_info(LD_REND, "Failed intro circ %s to %s "
  1720. "(building circuit to intro point). "
  1721. "Marking intro point as possibly unreachable.",
  1722. safe_str_client(rend_data_get_address(ocirc->rend_data)),
  1723. safe_str_client(build_state_get_exit_nickname(
  1724. ocirc->build_state)));
  1725. rend_client_report_intro_point_failure(ocirc->build_state->chosen_exit,
  1726. ocirc->rend_data,
  1727. INTRO_POINT_FAILURE_UNREACHABLE);
  1728. }
  1729. }
  1730. }
  1731. if (circ->n_chan) {
  1732. circuit_clear_cell_queue(circ, circ->n_chan);
  1733. /* Only send destroy if the channel isn't closing anyway */
  1734. if (!CHANNEL_CONDEMNED(circ->n_chan)) {
  1735. channel_send_destroy(circ->n_circ_id, circ->n_chan, reason);
  1736. }
  1737. circuitmux_detach_circuit(circ->n_chan->cmux, circ);
  1738. circuit_set_n_circid_chan(circ, 0, NULL);
  1739. }
  1740. if (! CIRCUIT_IS_ORIGIN(circ)) {
  1741. or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
  1742. edge_connection_t *conn;
  1743. for (conn=or_circ->n_streams; conn; conn=conn->next_stream)
  1744. connection_edge_destroy(or_circ->p_circ_id, conn);
  1745. or_circ->n_streams = NULL;
  1746. while (or_circ->resolving_streams) {
  1747. conn = or_circ->resolving_streams;
  1748. or_circ->resolving_streams = conn->next_stream;
  1749. if (!conn->base_.marked_for_close) {
  1750. /* The client will see a DESTROY, and infer that the connections
  1751. * are closing because the circuit is getting torn down. No need
  1752. * to send an end cell. */
  1753. conn->edge_has_sent_end = 1;
  1754. conn->end_reason = END_STREAM_REASON_DESTROY;
  1755. conn->end_reason |= END_STREAM_REASON_FLAG_ALREADY_SENT_CLOSED;
  1756. connection_mark_for_close(TO_CONN(conn));
  1757. }
  1758. conn->on_circuit = NULL;
  1759. }
  1760. if (or_circ->p_chan) {
  1761. circuit_clear_cell_queue(circ, or_circ->p_chan);
  1762. /* Only send destroy if the channel isn't closing anyway */
  1763. if (!CHANNEL_CONDEMNED(or_circ->p_chan)) {
  1764. channel_send_destroy(or_circ->p_circ_id, or_circ->p_chan, reason);
  1765. }
  1766. circuitmux_detach_circuit(or_circ->p_chan->cmux, circ);
  1767. circuit_set_p_circid_chan(or_circ, 0, NULL);
  1768. }
  1769. } else {
  1770. origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
  1771. edge_connection_t *conn;
  1772. for (conn=ocirc->p_streams; conn; conn=conn->next_stream)
  1773. connection_edge_destroy(circ->n_circ_id, conn);
  1774. ocirc->p_streams = NULL;
  1775. }
  1776. }
  1777. /** Given a marked circuit <b>circ</b>, aggressively free its cell queues to
  1778. * recover memory. */
  1779. static void
  1780. marked_circuit_free_cells(circuit_t *circ)
  1781. {
  1782. if (!circ->marked_for_close) {
  1783. log_warn(LD_BUG, "Called on non-marked circuit");
  1784. return;
  1785. }
  1786. cell_queue_clear(&circ->n_chan_cells);
  1787. if (circ->n_mux)
  1788. circuitmux_clear_num_cells(circ->n_mux, circ);
  1789. if (! CIRCUIT_IS_ORIGIN(circ)) {
  1790. or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
  1791. cell_queue_clear(&orcirc->p_chan_cells);
  1792. if (orcirc->p_mux)
  1793. circuitmux_clear_num_cells(orcirc->p_mux, circ);
  1794. }
  1795. }
  1796. static size_t
  1797. single_conn_free_bytes(connection_t *conn)
  1798. {
  1799. size_t result = 0;
  1800. if (conn->inbuf) {
  1801. result += buf_allocation(conn->inbuf);
  1802. buf_clear(conn->inbuf);
  1803. }
  1804. if (conn->outbuf) {
  1805. result += buf_allocation(conn->outbuf);
  1806. buf_clear(conn->outbuf);
  1807. }
  1808. if (conn->type == CONN_TYPE_DIR) {
  1809. dir_connection_t *dir_conn = TO_DIR_CONN(conn);
  1810. if (dir_conn->compress_state) {
  1811. result += tor_compress_state_size(dir_conn->compress_state);
  1812. tor_compress_free(dir_conn->compress_state);
  1813. dir_conn->compress_state = NULL;
  1814. }
  1815. }
  1816. return result;
  1817. }
  1818. /** Aggressively free buffer contents on all the buffers of all streams in the
  1819. * list starting at <b>stream</b>. Return the number of bytes recovered. */
  1820. static size_t
  1821. marked_circuit_streams_free_bytes(edge_connection_t *stream)
  1822. {
  1823. size_t result = 0;
  1824. for ( ; stream; stream = stream->next_stream) {
  1825. connection_t *conn = TO_CONN(stream);
  1826. result += single_conn_free_bytes(conn);
  1827. if (conn->linked_conn) {
  1828. result += single_conn_free_bytes(conn->linked_conn);
  1829. }
  1830. }
  1831. return result;
  1832. }
  1833. /** Aggressively free buffer contents on all the buffers of all streams on
  1834. * circuit <b>c</b>. Return the number of bytes recovered. */
  1835. static size_t
  1836. marked_circuit_free_stream_bytes(circuit_t *c)
  1837. {
  1838. if (CIRCUIT_IS_ORIGIN(c)) {
  1839. return marked_circuit_streams_free_bytes(TO_ORIGIN_CIRCUIT(c)->p_streams);
  1840. } else {
  1841. return marked_circuit_streams_free_bytes(TO_OR_CIRCUIT(c)->n_streams);
  1842. }
  1843. }
  1844. /** Return the number of cells used by the circuit <b>c</b>'s cell queues. */
  1845. STATIC size_t
  1846. n_cells_in_circ_queues(const circuit_t *c)
  1847. {
  1848. size_t n = c->n_chan_cells.n;
  1849. if (! CIRCUIT_IS_ORIGIN(c)) {
  1850. circuit_t *cc = (circuit_t *) c;
  1851. n += TO_OR_CIRCUIT(cc)->p_chan_cells.n;
  1852. }
  1853. return n;
  1854. }
  1855. /**
  1856. * Return the age of the oldest cell queued on <b>c</b>, in milliseconds.
  1857. * Return 0 if there are no cells queued on c. Requires that <b>now</b> be
  1858. * the current time in milliseconds since the epoch, truncated.
  1859. *
  1860. * This function will return incorrect results if the oldest cell queued on
  1861. * the circuit is older than 2**32 msec (about 49 days) old.
  1862. */
  1863. STATIC uint32_t
  1864. circuit_max_queued_cell_age(const circuit_t *c, uint32_t now)
  1865. {
  1866. uint32_t age = 0;
  1867. packed_cell_t *cell;
  1868. if (NULL != (cell = TOR_SIMPLEQ_FIRST(&c->n_chan_cells.head)))
  1869. age = now - cell->inserted_time;
  1870. if (! CIRCUIT_IS_ORIGIN(c)) {
  1871. const or_circuit_t *orcirc = CONST_TO_OR_CIRCUIT(c);
  1872. if (NULL != (cell = TOR_SIMPLEQ_FIRST(&orcirc->p_chan_cells.head))) {
  1873. uint32_t age2 = now - cell->inserted_time;
  1874. if (age2 > age)
  1875. return age2;
  1876. }
  1877. }
  1878. return age;
  1879. }
  1880. /** Return the age in milliseconds of the oldest buffer chunk on <b>conn</b>,
  1881. * where age is taken in milliseconds before the time <b>now</b> (in truncated
  1882. * absolute monotonic msec). If the connection has no data, treat
  1883. * it as having age zero.
  1884. **/
  1885. static uint32_t
  1886. conn_get_buffer_age(const connection_t *conn, uint32_t now)
  1887. {
  1888. uint32_t age = 0, age2;
  1889. if (conn->outbuf) {
  1890. age2 = buf_get_oldest_chunk_timestamp(conn->outbuf, now);
  1891. if (age2 > age)
  1892. age = age2;
  1893. }
  1894. if (conn->inbuf) {
  1895. age2 = buf_get_oldest_chunk_timestamp(conn->inbuf, now);
  1896. if (age2 > age)
  1897. age = age2;
  1898. }
  1899. return age;
  1900. }
  1901. /** Return the age in milliseconds of the oldest buffer chunk on any stream in
  1902. * the linked list <b>stream</b>, where age is taken in milliseconds before
  1903. * the time <b>now</b> (in truncated milliseconds since the epoch). */
  1904. static uint32_t
  1905. circuit_get_streams_max_data_age(const edge_connection_t *stream, uint32_t now)
  1906. {
  1907. uint32_t age = 0, age2;
  1908. for (; stream; stream = stream->next_stream) {
  1909. const connection_t *conn = TO_CONN(stream);
  1910. age2 = conn_get_buffer_age(conn, now);
  1911. if (age2 > age)
  1912. age = age2;
  1913. if (conn->linked_conn) {
  1914. age2 = conn_get_buffer_age(conn->linked_conn, now);
  1915. if (age2 > age)
  1916. age = age2;
  1917. }
  1918. }
  1919. return age;
  1920. }
  1921. /** Return the age in milliseconds of the oldest buffer chunk on any stream
  1922. * attached to the circuit <b>c</b>, where age is taken in milliseconds before
  1923. * the time <b>now</b> (in truncated milliseconds since the epoch). */
  1924. STATIC uint32_t
  1925. circuit_max_queued_data_age(const circuit_t *c, uint32_t now)
  1926. {
  1927. if (CIRCUIT_IS_ORIGIN(c)) {
  1928. return circuit_get_streams_max_data_age(
  1929. CONST_TO_ORIGIN_CIRCUIT(c)->p_streams, now);
  1930. } else {
  1931. return circuit_get_streams_max_data_age(
  1932. CONST_TO_OR_CIRCUIT(c)->n_streams, now);
  1933. }
  1934. }
  1935. /** Return the age of the oldest cell or stream buffer chunk on the circuit
  1936. * <b>c</b>, where age is taken in milliseconds before the time <b>now</b> (in
  1937. * truncated milliseconds since the epoch). */
  1938. STATIC uint32_t
  1939. circuit_max_queued_item_age(const circuit_t *c, uint32_t now)
  1940. {
  1941. uint32_t cell_age = circuit_max_queued_cell_age(c, now);
  1942. uint32_t data_age = circuit_max_queued_data_age(c, now);
  1943. if (cell_age > data_age)
  1944. return cell_age;
  1945. else
  1946. return data_age;
  1947. }
  1948. /** Helper to sort a list of circuit_t by age of oldest item, in descending
  1949. * order. */
  1950. static int
  1951. circuits_compare_by_oldest_queued_item_(const void **a_, const void **b_)
  1952. {
  1953. const circuit_t *a = *a_;
  1954. const circuit_t *b = *b_;
  1955. uint32_t age_a = a->age_tmp;
  1956. uint32_t age_b = b->age_tmp;
  1957. if (age_a < age_b)
  1958. return 1;
  1959. else if (age_a == age_b)
  1960. return 0;
  1961. else
  1962. return -1;
  1963. }
  1964. static uint32_t now_ms_for_buf_cmp;
  1965. /** Helper to sort a list of circuit_t by age of oldest item, in descending
  1966. * order. */
  1967. static int
  1968. conns_compare_by_buffer_age_(const void **a_, const void **b_)
  1969. {
  1970. const connection_t *a = *a_;
  1971. const connection_t *b = *b_;
  1972. time_t age_a = conn_get_buffer_age(a, now_ms_for_buf_cmp);
  1973. time_t age_b = conn_get_buffer_age(b, now_ms_for_buf_cmp);
  1974. if (age_a < age_b)
  1975. return 1;
  1976. else if (age_a == age_b)
  1977. return 0;
  1978. else
  1979. return -1;
  1980. }
  1981. #define FRACTION_OF_DATA_TO_RETAIN_ON_OOM 0.90
  1982. /** We're out of memory for cells, having allocated <b>current_allocation</b>
  1983. * bytes' worth. Kill the 'worst' circuits until we're under
  1984. * FRACTION_OF_DATA_TO_RETAIN_ON_OOM of our maximum usage. */
  1985. void
  1986. circuits_handle_oom(size_t current_allocation)
  1987. {
  1988. smartlist_t *circlist;
  1989. smartlist_t *connection_array = get_connection_array();
  1990. int conn_idx;
  1991. size_t mem_to_recover;
  1992. size_t mem_recovered=0;
  1993. int n_circuits_killed=0;
  1994. int n_dirconns_killed=0;
  1995. uint32_t now_ms;
  1996. log_notice(LD_GENERAL, "We're low on memory. Killing circuits with "
  1997. "over-long queues. (This behavior is controlled by "
  1998. "MaxMemInQueues.)");
  1999. {
  2000. size_t mem_target = (size_t)(get_options()->MaxMemInQueues *
  2001. FRACTION_OF_DATA_TO_RETAIN_ON_OOM);
  2002. if (current_allocation <= mem_target)
  2003. return;
  2004. mem_to_recover = current_allocation - mem_target;
  2005. }
  2006. now_ms = (uint32_t)monotime_coarse_absolute_msec();
  2007. circlist = circuit_get_global_list();
  2008. SMARTLIST_FOREACH_BEGIN(circlist, circuit_t *, circ) {
  2009. circ->age_tmp = circuit_max_queued_item_age(circ, now_ms);
  2010. } SMARTLIST_FOREACH_END(circ);
  2011. /* This is O(n log n); there are faster algorithms we could use instead.
  2012. * Let's hope this doesn't happen enough to be in the critical path. */
  2013. smartlist_sort(circlist, circuits_compare_by_oldest_queued_item_);
  2014. /* Fix up the indices before we run into trouble */
  2015. SMARTLIST_FOREACH_BEGIN(circlist, circuit_t *, circ) {
  2016. circ->global_circuitlist_idx = circ_sl_idx;
  2017. } SMARTLIST_FOREACH_END(circ);
  2018. /* Now sort the connection array ... */
  2019. now_ms_for_buf_cmp = now_ms;
  2020. smartlist_sort(connection_array, conns_compare_by_buffer_age_);
  2021. now_ms_for_buf_cmp = 0;
  2022. /* Fix up the connection array to its new order. */
  2023. SMARTLIST_FOREACH_BEGIN(connection_array, connection_t *, conn) {
  2024. conn->conn_array_index = conn_sl_idx;
  2025. } SMARTLIST_FOREACH_END(conn);
  2026. /* Okay, now the worst circuits and connections are at the front of their
  2027. * respective lists. Let's mark them, and reclaim their storage
  2028. * aggressively. */
  2029. conn_idx = 0;
  2030. SMARTLIST_FOREACH_BEGIN(circlist, circuit_t *, circ) {
  2031. size_t n;
  2032. size_t freed;
  2033. /* Free storage in any non-linked directory connections that have buffered
  2034. * data older than this circuit. */
  2035. while (conn_idx < smartlist_len(connection_array)) {
  2036. connection_t *conn = smartlist_get(connection_array, conn_idx);
  2037. uint32_t conn_age = conn_get_buffer_age(conn, now_ms);
  2038. if (conn_age < circ->age_tmp) {
  2039. break;
  2040. }
  2041. if (conn->type == CONN_TYPE_DIR && conn->linked_conn == NULL) {
  2042. if (!conn->marked_for_close)
  2043. connection_mark_for_close(conn);
  2044. mem_recovered += single_conn_free_bytes(conn);
  2045. ++n_dirconns_killed;
  2046. if (mem_recovered >= mem_to_recover)
  2047. goto done_recovering_mem;
  2048. }
  2049. ++conn_idx;
  2050. }
  2051. /* Now, kill the circuit. */
  2052. n = n_cells_in_circ_queues(circ);
  2053. if (! circ->marked_for_close) {
  2054. circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
  2055. }
  2056. marked_circuit_free_cells(circ);
  2057. freed = marked_circuit_free_stream_bytes(circ);
  2058. ++n_circuits_killed;
  2059. mem_recovered += n * packed_cell_mem_cost();
  2060. mem_recovered += freed;
  2061. if (mem_recovered >= mem_to_recover)
  2062. goto done_recovering_mem;
  2063. } SMARTLIST_FOREACH_END(circ);
  2064. done_recovering_mem:
  2065. log_notice(LD_GENERAL, "Removed "U64_FORMAT" bytes by killing %d circuits; "
  2066. "%d circuits remain alive. Also killed %d non-linked directory "
  2067. "connections.",
  2068. U64_PRINTF_ARG(mem_recovered),
  2069. n_circuits_killed,
  2070. smartlist_len(circlist) - n_circuits_killed,
  2071. n_dirconns_killed);
  2072. }
  2073. /** Verify that cpath layer <b>cp</b> has all of its invariants
  2074. * correct. Trigger an assert if anything is invalid.
  2075. */
  2076. void
  2077. assert_cpath_layer_ok(const crypt_path_t *cp)
  2078. {
  2079. // tor_assert(cp->addr); /* these are zero for rendezvous extra-hops */
  2080. // tor_assert(cp->port);
  2081. tor_assert(cp);
  2082. tor_assert(cp->magic == CRYPT_PATH_MAGIC);
  2083. switch (cp->state)
  2084. {
  2085. case CPATH_STATE_OPEN:
  2086. tor_assert(cp->f_crypto);
  2087. tor_assert(cp->b_crypto);
  2088. /* fall through */
  2089. case CPATH_STATE_CLOSED:
  2090. /*XXXX Assert that there's no handshake_state either. */
  2091. tor_assert(!cp->rend_dh_handshake_state);
  2092. break;
  2093. case CPATH_STATE_AWAITING_KEYS:
  2094. /* tor_assert(cp->dh_handshake_state); */
  2095. break;
  2096. default:
  2097. log_fn(LOG_ERR, LD_BUG, "Unexpected state %d", cp->state);
  2098. tor_assert(0);
  2099. }
  2100. tor_assert(cp->package_window >= 0);
  2101. tor_assert(cp->deliver_window >= 0);
  2102. }
  2103. /** Verify that cpath <b>cp</b> has all of its invariants
  2104. * correct. Trigger an assert if anything is invalid.
  2105. */
  2106. static void
  2107. assert_cpath_ok(const crypt_path_t *cp)
  2108. {
  2109. const crypt_path_t *start = cp;
  2110. do {
  2111. assert_cpath_layer_ok(cp);
  2112. /* layers must be in sequence of: "open* awaiting? closed*" */
  2113. if (cp != start) {
  2114. if (cp->state == CPATH_STATE_AWAITING_KEYS) {
  2115. tor_assert(cp->prev->state == CPATH_STATE_OPEN);
  2116. } else if (cp->state == CPATH_STATE_OPEN) {
  2117. tor_assert(cp->prev->state == CPATH_STATE_OPEN);
  2118. }
  2119. }
  2120. cp = cp->next;
  2121. tor_assert(cp);
  2122. } while (cp != start);
  2123. }
  2124. /** Verify that circuit <b>c</b> has all of its invariants
  2125. * correct. Trigger an assert if anything is invalid.
  2126. */
  2127. void
  2128. assert_circuit_ok(const circuit_t *c)
  2129. {
  2130. edge_connection_t *conn;
  2131. const or_circuit_t *or_circ = NULL;
  2132. const origin_circuit_t *origin_circ = NULL;
  2133. tor_assert(c);
  2134. tor_assert(c->magic == ORIGIN_CIRCUIT_MAGIC || c->magic == OR_CIRCUIT_MAGIC);
  2135. tor_assert(c->purpose >= CIRCUIT_PURPOSE_MIN_ &&
  2136. c->purpose <= CIRCUIT_PURPOSE_MAX_);
  2137. if (CIRCUIT_IS_ORIGIN(c))
  2138. origin_circ = CONST_TO_ORIGIN_CIRCUIT(c);
  2139. else
  2140. or_circ = CONST_TO_OR_CIRCUIT(c);
  2141. if (c->n_chan) {
  2142. tor_assert(!c->n_hop);
  2143. if (c->n_circ_id) {
  2144. /* We use the _impl variant here to make sure we don't fail on marked
  2145. * circuits, which would not be returned by the regular function. */
  2146. circuit_t *c2 = circuit_get_by_circid_channel_impl(c->n_circ_id,
  2147. c->n_chan, NULL);
  2148. tor_assert(c == c2);
  2149. }
  2150. }
  2151. if (or_circ && or_circ->p_chan) {
  2152. if (or_circ->p_circ_id) {
  2153. /* ibid */
  2154. circuit_t *c2 =
  2155. circuit_get_by_circid_channel_impl(or_circ->p_circ_id,
  2156. or_circ->p_chan, NULL);
  2157. tor_assert(c == c2);
  2158. }
  2159. }
  2160. if (or_circ)
  2161. for (conn = or_circ->n_streams; conn; conn = conn->next_stream)
  2162. tor_assert(conn->base_.type == CONN_TYPE_EXIT);
  2163. tor_assert(c->deliver_window >= 0);
  2164. tor_assert(c->package_window >= 0);
  2165. if (c->state == CIRCUIT_STATE_OPEN ||
  2166. c->state == CIRCUIT_STATE_GUARD_WAIT) {
  2167. tor_assert(!c->n_chan_create_cell);
  2168. if (or_circ) {
  2169. tor_assert(or_circ->n_crypto);
  2170. tor_assert(or_circ->p_crypto);
  2171. tor_assert(or_circ->n_digest);
  2172. tor_assert(or_circ->p_digest);
  2173. }
  2174. }
  2175. if (c->state == CIRCUIT_STATE_CHAN_WAIT && !c->marked_for_close) {
  2176. tor_assert(circuits_pending_chans &&
  2177. smartlist_contains(circuits_pending_chans, c));
  2178. } else {
  2179. tor_assert(!circuits_pending_chans ||
  2180. !smartlist_contains(circuits_pending_chans, c));
  2181. }
  2182. if (origin_circ && origin_circ->cpath) {
  2183. assert_cpath_ok(origin_circ->cpath);
  2184. }
  2185. if (c->purpose == CIRCUIT_PURPOSE_REND_ESTABLISHED) {
  2186. tor_assert(or_circ);
  2187. if (!c->marked_for_close) {
  2188. tor_assert(or_circ->rend_splice);
  2189. tor_assert(or_circ->rend_splice->rend_splice == or_circ);
  2190. }
  2191. tor_assert(or_circ->rend_splice != or_circ);
  2192. } else {
  2193. tor_assert(!or_circ || !or_circ->rend_splice);
  2194. }
  2195. }