circuitlist.c 73 KB

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