circuitlist.c 85 KB

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