circuitmux.c 61 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006
  1. /* * Copyright (c) 2012-2016, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /**
  4. * \file circuitmux.c
  5. * \brief Circuit mux/cell selection abstraction
  6. *
  7. * A circuitmux is responsible for <b>MU</b>ltiple<b>X</b>ing all of the
  8. * circuits that are writing on a single channel. It keeps track of which of
  9. * these circuits has something to write (aka, "active" circuits), and which
  10. * one should write next. A circuitmux corresponds 1:1 with a channel.
  11. *
  12. * There can be different implementations of the circuitmux's rules (which
  13. * decide which circuit is next to write).
  14. *
  15. * A circuitmux exposes three distinct
  16. * interfaces to other components:
  17. *
  18. * To channels, which each have a circuitmux_t, the supported operations
  19. * (invoked from relay.c) are:
  20. *
  21. * circuitmux_get_first_active_circuit():
  22. *
  23. * Pick one of the circuitmux's active circuits to send cells from.
  24. *
  25. * circuitmux_notify_xmit_cells():
  26. *
  27. * Notify the circuitmux that cells have been sent on a circuit.
  28. *
  29. * To circuits, the exposed operations are:
  30. *
  31. * circuitmux_attach_circuit():
  32. *
  33. * Attach a circuit to the circuitmux; this will allocate any policy-
  34. * specific data wanted for this circuit and add it to the active
  35. * circuits list if it has queued cells.
  36. *
  37. * circuitmux_detach_circuit():
  38. *
  39. * Detach a circuit from the circuitmux, freeing associated structures.
  40. *
  41. * circuitmux_clear_num_cells():
  42. *
  43. * Clear the circuitmux's cell counter for this circuit.
  44. *
  45. * circuitmux_set_num_cells():
  46. *
  47. * Set the circuitmux's cell counter for this circuit. One of
  48. * circuitmuc_clear_num_cells() or circuitmux_set_num_cells() MUST be
  49. * called when the number of cells queued on a circuit changes.
  50. *
  51. * See circuitmux.h for the circuitmux_policy_t data structure, which contains
  52. * a table of function pointers implementing a circuit selection policy, and
  53. * circuitmux_ewma.c for an example of a circuitmux policy. Circuitmux
  54. * policies can be manipulated with:
  55. *
  56. * circuitmux_get_policy():
  57. *
  58. * Return the current policy for a circuitmux_t, if any.
  59. *
  60. * circuitmux_clear_policy():
  61. *
  62. * Remove a policy installed on a circuitmux_t, freeing all associated
  63. * data. The circuitmux will revert to the built-in round-robin behavior.
  64. *
  65. * circuitmux_set_policy():
  66. *
  67. * Install a policy on a circuitmux_t; the appropriate callbacks will be
  68. * made to attach all existing circuits to the new policy.
  69. **/
  70. #include "or.h"
  71. #include "channel.h"
  72. #include "circuitlist.h"
  73. #include "circuitmux.h"
  74. #include "relay.h"
  75. /*
  76. * Private typedefs for circuitmux.c
  77. */
  78. /*
  79. * Map of muxinfos for circuitmux_t to use; struct is defined below (name
  80. * of struct must match HT_HEAD line).
  81. */
  82. typedef struct chanid_circid_muxinfo_map chanid_circid_muxinfo_map_t;
  83. /*
  84. * Hash table entry (yeah, calling it chanid_circid_muxinfo_s seems to
  85. * break the hash table code).
  86. */
  87. typedef struct chanid_circid_muxinfo_t chanid_circid_muxinfo_t;
  88. /*
  89. * Anything the mux wants to store per-circuit in the map; right now just
  90. * a count of queued cells.
  91. */
  92. typedef struct circuit_muxinfo_s circuit_muxinfo_t;
  93. /*
  94. * Structures for circuitmux.c
  95. */
  96. struct circuitmux_s {
  97. /* Keep count of attached, active circuits */
  98. unsigned int n_circuits, n_active_circuits;
  99. /* Total number of queued cells on all circuits */
  100. unsigned int n_cells;
  101. /*
  102. * Map from (channel ID, circuit ID) pairs to circuit_muxinfo_t
  103. */
  104. chanid_circid_muxinfo_map_t *chanid_circid_map;
  105. /*
  106. * Double-linked ring of circuits with queued cells waiting for room to
  107. * free up on this connection's outbuf. Every time we pull cells from
  108. * a circuit, we advance this pointer to the next circuit in the ring.
  109. */
  110. struct circuit_t *active_circuits_head, *active_circuits_tail;
  111. /** List of queued destroy cells */
  112. cell_queue_t destroy_cell_queue;
  113. /** Boolean: True iff the last cell to circuitmux_get_first_active_circuit
  114. * returned the destroy queue. Used to force alternation between
  115. * destroy/non-destroy cells.
  116. *
  117. * XXXX There is no reason to think that alternating is a particularly good
  118. * approach -- it's just designed to prevent destroys from starving other
  119. * cells completely.
  120. */
  121. unsigned int last_cell_was_destroy : 1;
  122. /** Destroy counter: increment this when a destroy gets queued, decrement
  123. * when we unqueue it, so we can test to make sure they don't starve.
  124. */
  125. int64_t destroy_ctr;
  126. /*
  127. * Circuitmux policy; if this is non-NULL, it can override the built-
  128. * in round-robin active circuits behavior. This is how EWMA works in
  129. * the new circuitmux_t world.
  130. */
  131. const circuitmux_policy_t *policy;
  132. /* Policy-specific data */
  133. circuitmux_policy_data_t *policy_data;
  134. };
  135. /*
  136. * This struct holds whatever we want to store per attached circuit on a
  137. * circuitmux_t; right now, just the count of queued cells and the direction.
  138. */
  139. struct circuit_muxinfo_s {
  140. /* Count of cells on this circuit at last update */
  141. unsigned int cell_count;
  142. /* Direction of flow */
  143. cell_direction_t direction;
  144. /* Policy-specific data */
  145. circuitmux_policy_circ_data_t *policy_data;
  146. /* Mark bit for consistency checker */
  147. unsigned int mark:1;
  148. };
  149. /*
  150. * A map from channel ID and circuit ID to a circuit_muxinfo_t for that
  151. * circuit.
  152. */
  153. struct chanid_circid_muxinfo_t {
  154. HT_ENTRY(chanid_circid_muxinfo_t) node;
  155. uint64_t chan_id;
  156. circid_t circ_id;
  157. circuit_muxinfo_t muxinfo;
  158. };
  159. /*
  160. * Internal-use #defines
  161. */
  162. #ifdef CMUX_PARANOIA
  163. #define circuitmux_assert_okay_paranoid(cmux) \
  164. circuitmux_assert_okay(cmux)
  165. #else
  166. #define circuitmux_assert_okay_paranoid(cmux)
  167. #endif
  168. /*
  169. * Static function declarations
  170. */
  171. static inline int
  172. chanid_circid_entries_eq(chanid_circid_muxinfo_t *a,
  173. chanid_circid_muxinfo_t *b);
  174. static inline unsigned int
  175. chanid_circid_entry_hash(chanid_circid_muxinfo_t *a);
  176. static chanid_circid_muxinfo_t *
  177. circuitmux_find_map_entry(circuitmux_t *cmux, circuit_t *circ);
  178. static void
  179. circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ,
  180. cell_direction_t direction);
  181. static void
  182. circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ,
  183. cell_direction_t direction);
  184. static inline void
  185. circuitmux_move_active_circ_to_tail(circuitmux_t *cmux, circuit_t *circ,
  186. cell_direction_t direction);
  187. static inline circuit_t **
  188. circuitmux_next_active_circ_p(circuitmux_t *cmux, circuit_t *circ);
  189. static inline circuit_t **
  190. circuitmux_prev_active_circ_p(circuitmux_t *cmux, circuit_t *circ);
  191. static void circuitmux_assert_okay_pass_one(circuitmux_t *cmux);
  192. static void circuitmux_assert_okay_pass_two(circuitmux_t *cmux);
  193. static void circuitmux_assert_okay_pass_three(circuitmux_t *cmux);
  194. /* Static global variables */
  195. /** Count the destroy balance to debug destroy queue logic */
  196. static int64_t global_destroy_ctr = 0;
  197. /* Function definitions */
  198. /**
  199. * Linked list helpers
  200. */
  201. /**
  202. * Move an active circuit to the tail of the cmux's active circuits list;
  203. * used by circuitmux_notify_xmit_cells().
  204. */
  205. static inline void
  206. circuitmux_move_active_circ_to_tail(circuitmux_t *cmux, circuit_t *circ,
  207. cell_direction_t direction)
  208. {
  209. circuit_t **next_p = NULL, **prev_p = NULL;
  210. circuit_t **next_prev = NULL, **prev_next = NULL;
  211. circuit_t **tail_next = NULL;
  212. or_circuit_t *or_circ = NULL;
  213. tor_assert(cmux);
  214. tor_assert(circ);
  215. circuitmux_assert_okay_paranoid(cmux);
  216. /* Figure out our next_p and prev_p for this cmux/direction */
  217. if (direction) {
  218. if (direction == CELL_DIRECTION_OUT) {
  219. tor_assert(circ->n_mux == cmux);
  220. next_p = &(circ->next_active_on_n_chan);
  221. prev_p = &(circ->prev_active_on_n_chan);
  222. } else {
  223. or_circ = TO_OR_CIRCUIT(circ);
  224. tor_assert(or_circ->p_mux == cmux);
  225. next_p = &(or_circ->next_active_on_p_chan);
  226. prev_p = &(or_circ->prev_active_on_p_chan);
  227. }
  228. } else {
  229. if (circ->n_mux == cmux) {
  230. next_p = &(circ->next_active_on_n_chan);
  231. prev_p = &(circ->prev_active_on_n_chan);
  232. direction = CELL_DIRECTION_OUT;
  233. } else {
  234. or_circ = TO_OR_CIRCUIT(circ);
  235. tor_assert(or_circ->p_mux == cmux);
  236. next_p = &(or_circ->next_active_on_p_chan);
  237. prev_p = &(or_circ->prev_active_on_p_chan);
  238. direction = CELL_DIRECTION_IN;
  239. }
  240. }
  241. tor_assert(next_p);
  242. tor_assert(prev_p);
  243. /* Check if this really is an active circuit */
  244. if ((*next_p == NULL && *prev_p == NULL) &&
  245. !(circ == cmux->active_circuits_head ||
  246. circ == cmux->active_circuits_tail)) {
  247. /* Not active, no-op */
  248. return;
  249. }
  250. /* Check if this is already the tail */
  251. if (circ == cmux->active_circuits_tail) return;
  252. /* Okay, we have to move it; figure out next_prev and prev_next */
  253. if (*next_p) next_prev = circuitmux_prev_active_circ_p(cmux, *next_p);
  254. if (*prev_p) prev_next = circuitmux_next_active_circ_p(cmux, *prev_p);
  255. /* Adjust the previous node's next pointer, if any */
  256. if (prev_next) *prev_next = *next_p;
  257. /* Otherwise, we were the head */
  258. else cmux->active_circuits_head = *next_p;
  259. /* Adjust the next node's previous pointer, if any */
  260. if (next_prev) *next_prev = *prev_p;
  261. /* We're out of the list; now re-attach at the tail */
  262. /* Adjust our next and prev pointers */
  263. *next_p = NULL;
  264. *prev_p = cmux->active_circuits_tail;
  265. /* Set the next pointer of the tail, or the head if none */
  266. if (cmux->active_circuits_tail) {
  267. tail_next = circuitmux_next_active_circ_p(cmux,
  268. cmux->active_circuits_tail);
  269. *tail_next = circ;
  270. } else {
  271. cmux->active_circuits_head = circ;
  272. }
  273. /* Set the tail to this circuit */
  274. cmux->active_circuits_tail = circ;
  275. circuitmux_assert_okay_paranoid(cmux);
  276. }
  277. static inline circuit_t **
  278. circuitmux_next_active_circ_p(circuitmux_t *cmux, circuit_t *circ)
  279. {
  280. tor_assert(cmux);
  281. tor_assert(circ);
  282. if (circ->n_mux == cmux) return &(circ->next_active_on_n_chan);
  283. else {
  284. tor_assert(TO_OR_CIRCUIT(circ)->p_mux == cmux);
  285. return &(TO_OR_CIRCUIT(circ)->next_active_on_p_chan);
  286. }
  287. }
  288. static inline circuit_t **
  289. circuitmux_prev_active_circ_p(circuitmux_t *cmux, circuit_t *circ)
  290. {
  291. tor_assert(cmux);
  292. tor_assert(circ);
  293. if (circ->n_mux == cmux) return &(circ->prev_active_on_n_chan);
  294. else {
  295. tor_assert(TO_OR_CIRCUIT(circ)->p_mux == cmux);
  296. return &(TO_OR_CIRCUIT(circ)->prev_active_on_p_chan);
  297. }
  298. }
  299. /**
  300. * Helper for chanid_circid_cell_count_map_t hash table: compare the channel
  301. * ID and circuit ID for a and b, and return less than, equal to, or greater
  302. * than zero appropriately.
  303. */
  304. static inline int
  305. chanid_circid_entries_eq(chanid_circid_muxinfo_t *a,
  306. chanid_circid_muxinfo_t *b)
  307. {
  308. return a->chan_id == b->chan_id && a->circ_id == b->circ_id;
  309. }
  310. /**
  311. * Helper: return a hash based on circuit ID and channel ID in a.
  312. */
  313. static inline unsigned int
  314. chanid_circid_entry_hash(chanid_circid_muxinfo_t *a)
  315. {
  316. return (((unsigned int)(a->circ_id) << 8) ^
  317. ((unsigned int)((a->chan_id >> 32) & 0xffffffff)) ^
  318. ((unsigned int)(a->chan_id & 0xffffffff)));
  319. }
  320. /* Declare the struct chanid_circid_muxinfo_map type */
  321. HT_HEAD(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t);
  322. /* Emit a bunch of hash table stuff */
  323. HT_PROTOTYPE(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t, node,
  324. chanid_circid_entry_hash, chanid_circid_entries_eq)
  325. HT_GENERATE2(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t, node,
  326. chanid_circid_entry_hash, chanid_circid_entries_eq, 0.6,
  327. tor_reallocarray_, tor_free_)
  328. /*
  329. * Circuitmux alloc/free functions
  330. */
  331. /**
  332. * Allocate a new circuitmux_t
  333. */
  334. circuitmux_t *
  335. circuitmux_alloc(void)
  336. {
  337. circuitmux_t *rv = NULL;
  338. rv = tor_malloc_zero(sizeof(*rv));
  339. rv->chanid_circid_map = tor_malloc_zero(sizeof(*( rv->chanid_circid_map)));
  340. HT_INIT(chanid_circid_muxinfo_map, rv->chanid_circid_map);
  341. cell_queue_init(&rv->destroy_cell_queue);
  342. return rv;
  343. }
  344. /**
  345. * Detach all circuits from a circuitmux (use before circuitmux_free())
  346. *
  347. * If <b>detached_out</b> is non-NULL, add every detached circuit_t to
  348. * detached_out.
  349. */
  350. void
  351. circuitmux_detach_all_circuits(circuitmux_t *cmux, smartlist_t *detached_out)
  352. {
  353. chanid_circid_muxinfo_t **i = NULL, *to_remove;
  354. channel_t *chan = NULL;
  355. circuit_t *circ = NULL;
  356. tor_assert(cmux);
  357. /*
  358. * Don't circuitmux_assert_okay_paranoid() here; this gets called when
  359. * channels are being freed and have already been unregistered, so
  360. * the channel ID lookups it does will fail.
  361. */
  362. i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
  363. while (i) {
  364. to_remove = *i;
  365. if (! to_remove) {
  366. log_warn(LD_BUG, "Somehow, an HT iterator gave us a NULL pointer.");
  367. break;
  368. } else {
  369. /* Find a channel and circuit */
  370. chan = channel_find_by_global_id(to_remove->chan_id);
  371. if (chan) {
  372. circ =
  373. circuit_get_by_circid_channel_even_if_marked(to_remove->circ_id,
  374. chan);
  375. if (circ) {
  376. /* Clear the circuit's mux for this direction */
  377. if (to_remove->muxinfo.direction == CELL_DIRECTION_OUT) {
  378. /*
  379. * Update active_circuits et al.; this does policy notifies, so
  380. * comes before freeing policy data
  381. */
  382. if (to_remove->muxinfo.cell_count > 0) {
  383. circuitmux_make_circuit_inactive(cmux, circ, CELL_DIRECTION_OUT);
  384. }
  385. /* Clear n_mux */
  386. circ->n_mux = NULL;
  387. if (detached_out)
  388. smartlist_add(detached_out, circ);
  389. } else if (circ->magic == OR_CIRCUIT_MAGIC) {
  390. /*
  391. * Update active_circuits et al.; this does policy notifies, so
  392. * comes before freeing policy data
  393. */
  394. if (to_remove->muxinfo.cell_count > 0) {
  395. circuitmux_make_circuit_inactive(cmux, circ, CELL_DIRECTION_IN);
  396. }
  397. /*
  398. * It has a sensible p_chan and direction == CELL_DIRECTION_IN,
  399. * so clear p_mux.
  400. */
  401. TO_OR_CIRCUIT(circ)->p_mux = NULL;
  402. if (detached_out)
  403. smartlist_add(detached_out, circ);
  404. } else {
  405. /* Complain and move on */
  406. log_warn(LD_CIRC,
  407. "Circuit %u/channel " U64_FORMAT " had direction == "
  408. "CELL_DIRECTION_IN, but isn't an or_circuit_t",
  409. (unsigned)to_remove->circ_id,
  410. U64_PRINTF_ARG(to_remove->chan_id));
  411. }
  412. /* Free policy-specific data if we have it */
  413. if (to_remove->muxinfo.policy_data) {
  414. /*
  415. * If we have policy data, assert that we have the means to
  416. * free it
  417. */
  418. tor_assert(cmux->policy);
  419. tor_assert(cmux->policy->free_circ_data);
  420. /* Call free_circ_data() */
  421. cmux->policy->free_circ_data(cmux,
  422. cmux->policy_data,
  423. circ,
  424. to_remove->muxinfo.policy_data);
  425. to_remove->muxinfo.policy_data = NULL;
  426. }
  427. } else {
  428. /* Complain and move on */
  429. log_warn(LD_CIRC,
  430. "Couldn't find circuit %u (for channel " U64_FORMAT ")",
  431. (unsigned)to_remove->circ_id,
  432. U64_PRINTF_ARG(to_remove->chan_id));
  433. }
  434. } else {
  435. /* Complain and move on */
  436. log_warn(LD_CIRC,
  437. "Couldn't find channel " U64_FORMAT " (for circuit id %u)",
  438. U64_PRINTF_ARG(to_remove->chan_id),
  439. (unsigned)to_remove->circ_id);
  440. }
  441. /* Assert that we don't have un-freed policy data for this circuit */
  442. tor_assert(to_remove->muxinfo.policy_data == NULL);
  443. }
  444. i = HT_NEXT_RMV(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);
  445. /* Free it */
  446. tor_free(to_remove);
  447. }
  448. cmux->n_circuits = 0;
  449. cmux->n_active_circuits = 0;
  450. cmux->n_cells = 0;
  451. }
  452. /** Reclaim all circuit IDs currently marked as unusable on <b>chan</b> because
  453. * of pending destroy cells in <b>cmux</b>.
  454. *
  455. * This function must be called AFTER circuits are unlinked from the (channel,
  456. * circuid-id) map with circuit_unlink_all_from_channel(), but before calling
  457. * circuitmux_free().
  458. */
  459. void
  460. circuitmux_mark_destroyed_circids_usable(circuitmux_t *cmux, channel_t *chan)
  461. {
  462. packed_cell_t *cell;
  463. int n_bad = 0;
  464. TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
  465. circid_t circid = 0;
  466. if (packed_cell_is_destroy(chan, cell, &circid)) {
  467. channel_mark_circid_usable(chan, circid);
  468. } else {
  469. ++n_bad;
  470. }
  471. }
  472. if (n_bad)
  473. log_warn(LD_BUG, "%d cell(s) on destroy queue did not look like a "
  474. "DESTROY cell.", n_bad);
  475. }
  476. /**
  477. * Free a circuitmux_t; the circuits must be detached first with
  478. * circuitmux_detach_all_circuits().
  479. */
  480. void
  481. circuitmux_free(circuitmux_t *cmux)
  482. {
  483. if (!cmux) return;
  484. tor_assert(cmux->n_circuits == 0);
  485. tor_assert(cmux->n_active_circuits == 0);
  486. /*
  487. * Free policy-specific data if we have any; we don't
  488. * need to do circuitmux_set_policy(cmux, NULL) to cover
  489. * the circuits because they would have been handled in
  490. * circuitmux_detach_all_circuits() before this was
  491. * called.
  492. */
  493. if (cmux->policy && cmux->policy->free_cmux_data) {
  494. if (cmux->policy_data) {
  495. cmux->policy->free_cmux_data(cmux, cmux->policy_data);
  496. cmux->policy_data = NULL;
  497. }
  498. } else tor_assert(cmux->policy_data == NULL);
  499. if (cmux->chanid_circid_map) {
  500. HT_CLEAR(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
  501. tor_free(cmux->chanid_circid_map);
  502. }
  503. /*
  504. * We're throwing away some destroys; log the counter and
  505. * adjust the global counter by the queue size.
  506. */
  507. if (cmux->destroy_cell_queue.n > 0) {
  508. cmux->destroy_ctr -= cmux->destroy_cell_queue.n;
  509. global_destroy_ctr -= cmux->destroy_cell_queue.n;
  510. log_debug(LD_CIRC,
  511. "Freeing cmux at %p with %u queued destroys; the last cmux "
  512. "destroy balance was "I64_FORMAT", global is "I64_FORMAT,
  513. cmux, cmux->destroy_cell_queue.n,
  514. I64_PRINTF_ARG(cmux->destroy_ctr),
  515. I64_PRINTF_ARG(global_destroy_ctr));
  516. } else {
  517. log_debug(LD_CIRC,
  518. "Freeing cmux at %p with no queued destroys, the cmux destroy "
  519. "balance was "I64_FORMAT", global is "I64_FORMAT,
  520. cmux,
  521. I64_PRINTF_ARG(cmux->destroy_ctr),
  522. I64_PRINTF_ARG(global_destroy_ctr));
  523. }
  524. cell_queue_clear(&cmux->destroy_cell_queue);
  525. tor_free(cmux);
  526. }
  527. /*
  528. * Circuitmux policy control functions
  529. */
  530. /**
  531. * Remove any policy installed on cmux; all policy data will be freed and
  532. * cmux behavior will revert to the built-in round-robin active_circuits
  533. * mechanism.
  534. */
  535. void
  536. circuitmux_clear_policy(circuitmux_t *cmux)
  537. {
  538. tor_assert(cmux);
  539. /* Internally, this is just setting policy to NULL */
  540. if (cmux->policy) {
  541. circuitmux_set_policy(cmux, NULL);
  542. }
  543. }
  544. /**
  545. * Return the policy currently installed on a circuitmux_t
  546. */
  547. MOCK_IMPL(const circuitmux_policy_t *,
  548. circuitmux_get_policy, (circuitmux_t *cmux))
  549. {
  550. tor_assert(cmux);
  551. return cmux->policy;
  552. }
  553. /**
  554. * Set policy; allocate for new policy, detach all circuits from old policy
  555. * if any, attach them to new policy, and free old policy data.
  556. */
  557. void
  558. circuitmux_set_policy(circuitmux_t *cmux,
  559. const circuitmux_policy_t *pol)
  560. {
  561. const circuitmux_policy_t *old_pol = NULL, *new_pol = NULL;
  562. circuitmux_policy_data_t *old_pol_data = NULL, *new_pol_data = NULL;
  563. chanid_circid_muxinfo_t **i = NULL;
  564. channel_t *chan = NULL;
  565. uint64_t last_chan_id_searched = 0;
  566. circuit_t *circ = NULL;
  567. tor_assert(cmux);
  568. /* Set up variables */
  569. old_pol = cmux->policy;
  570. old_pol_data = cmux->policy_data;
  571. new_pol = pol;
  572. /* Check if this is the trivial case */
  573. if (old_pol == new_pol) return;
  574. /* Allocate data for new policy, if any */
  575. if (new_pol && new_pol->alloc_cmux_data) {
  576. /*
  577. * If alloc_cmux_data is not null, then we expect to get some policy
  578. * data. Assert that we also have free_cmux_data so we can free it
  579. * when the time comes, and allocate it.
  580. */
  581. tor_assert(new_pol->free_cmux_data);
  582. new_pol_data = new_pol->alloc_cmux_data(cmux);
  583. tor_assert(new_pol_data);
  584. }
  585. /* Install new policy and new policy data on cmux */
  586. cmux->policy = new_pol;
  587. cmux->policy_data = new_pol_data;
  588. /* Iterate over all circuits, attaching/detaching each one */
  589. i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
  590. while (i) {
  591. /* Assert that this entry isn't NULL */
  592. tor_assert(*i);
  593. /*
  594. * Get the channel; since normal case is all circuits on the mux share a
  595. * channel, we cache last_chan_id_searched
  596. */
  597. if (!chan || last_chan_id_searched != (*i)->chan_id) {
  598. chan = channel_find_by_global_id((*i)->chan_id);
  599. last_chan_id_searched = (*i)->chan_id;
  600. }
  601. tor_assert(chan);
  602. /* Get the circuit */
  603. circ = circuit_get_by_circid_channel_even_if_marked((*i)->circ_id, chan);
  604. tor_assert(circ);
  605. /* Need to tell old policy it becomes inactive (i.e., it is active) ? */
  606. if (old_pol && old_pol->notify_circ_inactive &&
  607. (*i)->muxinfo.cell_count > 0) {
  608. old_pol->notify_circ_inactive(cmux, old_pol_data, circ,
  609. (*i)->muxinfo.policy_data);
  610. }
  611. /* Need to free old policy data? */
  612. if ((*i)->muxinfo.policy_data) {
  613. /* Assert that we have the means to free it if we have policy data */
  614. tor_assert(old_pol);
  615. tor_assert(old_pol->free_circ_data);
  616. /* Free it */
  617. old_pol->free_circ_data(cmux, old_pol_data, circ,
  618. (*i)->muxinfo.policy_data);
  619. (*i)->muxinfo.policy_data = NULL;
  620. }
  621. /* Need to allocate new policy data? */
  622. if (new_pol && new_pol->alloc_circ_data) {
  623. /*
  624. * If alloc_circ_data is not null, we expect to get some per-circuit
  625. * policy data. Assert that we also have free_circ_data so we can
  626. * free it when the time comes, and allocate it.
  627. */
  628. tor_assert(new_pol->free_circ_data);
  629. (*i)->muxinfo.policy_data =
  630. new_pol->alloc_circ_data(cmux, new_pol_data, circ,
  631. (*i)->muxinfo.direction,
  632. (*i)->muxinfo.cell_count);
  633. }
  634. /* Need to make active on new policy? */
  635. if (new_pol && new_pol->notify_circ_active &&
  636. (*i)->muxinfo.cell_count > 0) {
  637. new_pol->notify_circ_active(cmux, new_pol_data, circ,
  638. (*i)->muxinfo.policy_data);
  639. }
  640. /* Advance to next circuit map entry */
  641. i = HT_NEXT(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);
  642. }
  643. /* Free data for old policy, if any */
  644. if (old_pol_data) {
  645. /*
  646. * If we had old policy data, we should have an old policy and a free
  647. * function for it.
  648. */
  649. tor_assert(old_pol);
  650. tor_assert(old_pol->free_cmux_data);
  651. old_pol->free_cmux_data(cmux, old_pol_data);
  652. old_pol_data = NULL;
  653. }
  654. }
  655. /*
  656. * Circuitmux/circuit attachment status inquiry functions
  657. */
  658. /**
  659. * Query the direction of an attached circuit
  660. */
  661. cell_direction_t
  662. circuitmux_attached_circuit_direction(circuitmux_t *cmux, circuit_t *circ)
  663. {
  664. chanid_circid_muxinfo_t *hashent = NULL;
  665. /* Try to find a map entry */
  666. hashent = circuitmux_find_map_entry(cmux, circ);
  667. /*
  668. * This function should only be called on attached circuits; assert that
  669. * we had a map entry.
  670. */
  671. tor_assert(hashent);
  672. /* Return the direction from the map entry */
  673. return hashent->muxinfo.direction;
  674. }
  675. /**
  676. * Find an entry in the cmux's map for this circuit or return NULL if there
  677. * is none.
  678. */
  679. static chanid_circid_muxinfo_t *
  680. circuitmux_find_map_entry(circuitmux_t *cmux, circuit_t *circ)
  681. {
  682. chanid_circid_muxinfo_t search, *hashent = NULL;
  683. /* Sanity-check parameters */
  684. tor_assert(cmux);
  685. tor_assert(cmux->chanid_circid_map);
  686. tor_assert(circ);
  687. /* Check if we have n_chan */
  688. if (circ->n_chan) {
  689. /* Okay, let's see if it's attached for n_chan/n_circ_id */
  690. search.chan_id = circ->n_chan->global_identifier;
  691. search.circ_id = circ->n_circ_id;
  692. /* Query */
  693. hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
  694. &search);
  695. }
  696. /* Found something? */
  697. if (hashent) {
  698. /*
  699. * Assert that the direction makes sense for a hashent we found by
  700. * n_chan/n_circ_id before we return it.
  701. */
  702. tor_assert(hashent->muxinfo.direction == CELL_DIRECTION_OUT);
  703. } else {
  704. /* Not there, have we got a p_chan/p_circ_id to try? */
  705. if (circ->magic == OR_CIRCUIT_MAGIC) {
  706. search.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
  707. /* Check for p_chan */
  708. if (TO_OR_CIRCUIT(circ)->p_chan) {
  709. search.chan_id = TO_OR_CIRCUIT(circ)->p_chan->global_identifier;
  710. /* Okay, search for that */
  711. hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
  712. &search);
  713. /* Find anything? */
  714. if (hashent) {
  715. /* Assert that the direction makes sense before we return it */
  716. tor_assert(hashent->muxinfo.direction == CELL_DIRECTION_IN);
  717. }
  718. }
  719. }
  720. }
  721. /* Okay, hashent is it if it was there */
  722. return hashent;
  723. }
  724. /**
  725. * Query whether a circuit is attached to a circuitmux
  726. */
  727. int
  728. circuitmux_is_circuit_attached(circuitmux_t *cmux, circuit_t *circ)
  729. {
  730. chanid_circid_muxinfo_t *hashent = NULL;
  731. /* Look if it's in the circuit map */
  732. hashent = circuitmux_find_map_entry(cmux, circ);
  733. return (hashent != NULL);
  734. }
  735. /**
  736. * Query whether a circuit is active on a circuitmux
  737. */
  738. int
  739. circuitmux_is_circuit_active(circuitmux_t *cmux, circuit_t *circ)
  740. {
  741. chanid_circid_muxinfo_t *hashent = NULL;
  742. int is_active = 0;
  743. tor_assert(cmux);
  744. tor_assert(circ);
  745. /* Look if it's in the circuit map */
  746. hashent = circuitmux_find_map_entry(cmux, circ);
  747. if (hashent) {
  748. /* Check the number of cells on this circuit */
  749. is_active = (hashent->muxinfo.cell_count > 0);
  750. }
  751. /* else not attached, so not active */
  752. return is_active;
  753. }
  754. /**
  755. * Query number of available cells for a circuit on a circuitmux
  756. */
  757. unsigned int
  758. circuitmux_num_cells_for_circuit(circuitmux_t *cmux, circuit_t *circ)
  759. {
  760. chanid_circid_muxinfo_t *hashent = NULL;
  761. unsigned int n_cells = 0;
  762. tor_assert(cmux);
  763. tor_assert(circ);
  764. /* Look if it's in the circuit map */
  765. hashent = circuitmux_find_map_entry(cmux, circ);
  766. if (hashent) {
  767. /* Just get the cell count for this circuit */
  768. n_cells = hashent->muxinfo.cell_count;
  769. }
  770. /* else not attached, so 0 cells */
  771. return n_cells;
  772. }
  773. /**
  774. * Query total number of available cells on a circuitmux
  775. */
  776. MOCK_IMPL(unsigned int,
  777. circuitmux_num_cells, (circuitmux_t *cmux))
  778. {
  779. tor_assert(cmux);
  780. return cmux->n_cells + cmux->destroy_cell_queue.n;
  781. }
  782. /**
  783. * Query total number of circuits active on a circuitmux
  784. */
  785. unsigned int
  786. circuitmux_num_active_circuits(circuitmux_t *cmux)
  787. {
  788. tor_assert(cmux);
  789. return cmux->n_active_circuits;
  790. }
  791. /**
  792. * Query total number of circuits attached to a circuitmux
  793. */
  794. unsigned int
  795. circuitmux_num_circuits(circuitmux_t *cmux)
  796. {
  797. tor_assert(cmux);
  798. return cmux->n_circuits;
  799. }
  800. /*
  801. * Functions for circuit code to call to update circuit status
  802. */
  803. /**
  804. * Attach a circuit to a circuitmux, for the specified direction.
  805. */
  806. MOCK_IMPL(void,
  807. circuitmux_attach_circuit,(circuitmux_t *cmux, circuit_t *circ,
  808. cell_direction_t direction))
  809. {
  810. channel_t *chan = NULL;
  811. uint64_t channel_id;
  812. circid_t circ_id;
  813. chanid_circid_muxinfo_t search, *hashent = NULL;
  814. unsigned int cell_count;
  815. tor_assert(cmux);
  816. tor_assert(circ);
  817. tor_assert(direction == CELL_DIRECTION_IN ||
  818. direction == CELL_DIRECTION_OUT);
  819. circuitmux_assert_okay_paranoid(cmux);
  820. /*
  821. * Figure out which channel we're using, and get the circuit's current
  822. * cell count and circuit ID; assert that the circuit is not already
  823. * attached to another mux.
  824. */
  825. if (direction == CELL_DIRECTION_OUT) {
  826. /* It's n_chan */
  827. chan = circ->n_chan;
  828. cell_count = circ->n_chan_cells.n;
  829. circ_id = circ->n_circ_id;
  830. } else {
  831. /* We want p_chan */
  832. chan = TO_OR_CIRCUIT(circ)->p_chan;
  833. cell_count = TO_OR_CIRCUIT(circ)->p_chan_cells.n;
  834. circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
  835. }
  836. /* Assert that we did get a channel */
  837. tor_assert(chan);
  838. /* Assert that the circuit ID is sensible */
  839. tor_assert(circ_id != 0);
  840. /* Get the channel ID */
  841. channel_id = chan->global_identifier;
  842. /* See if we already have this one */
  843. search.chan_id = channel_id;
  844. search.circ_id = circ_id;
  845. hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
  846. &search);
  847. if (hashent) {
  848. /*
  849. * This circuit was already attached to this cmux; make sure the
  850. * directions match and update the cell count and active circuit count.
  851. */
  852. log_info(LD_CIRC,
  853. "Circuit %u on channel " U64_FORMAT " was already attached to "
  854. "cmux %p (trying to attach to %p)",
  855. (unsigned)circ_id, U64_PRINTF_ARG(channel_id),
  856. ((direction == CELL_DIRECTION_OUT) ?
  857. circ->n_mux : TO_OR_CIRCUIT(circ)->p_mux),
  858. cmux);
  859. /*
  860. * The mux pointer on this circuit and the direction in result should
  861. * match; otherwise assert.
  862. */
  863. if (direction == CELL_DIRECTION_OUT) tor_assert(circ->n_mux == cmux);
  864. else tor_assert(TO_OR_CIRCUIT(circ)->p_mux == cmux);
  865. tor_assert(hashent->muxinfo.direction == direction);
  866. /*
  867. * Looks okay; just update the cell count and active circuits if we must
  868. */
  869. if (hashent->muxinfo.cell_count > 0 && cell_count == 0) {
  870. --(cmux->n_active_circuits);
  871. circuitmux_make_circuit_inactive(cmux, circ, direction);
  872. } else if (hashent->muxinfo.cell_count == 0 && cell_count > 0) {
  873. ++(cmux->n_active_circuits);
  874. circuitmux_make_circuit_active(cmux, circ, direction);
  875. }
  876. cmux->n_cells -= hashent->muxinfo.cell_count;
  877. cmux->n_cells += cell_count;
  878. hashent->muxinfo.cell_count = cell_count;
  879. } else {
  880. /*
  881. * New circuit; add an entry and update the circuit/active circuit
  882. * counts.
  883. */
  884. log_debug(LD_CIRC,
  885. "Attaching circuit %u on channel " U64_FORMAT " to cmux %p",
  886. (unsigned)circ_id, U64_PRINTF_ARG(channel_id), cmux);
  887. /*
  888. * Assert that the circuit doesn't already have a mux for this
  889. * direction.
  890. */
  891. if (direction == CELL_DIRECTION_OUT) tor_assert(circ->n_mux == NULL);
  892. else tor_assert(TO_OR_CIRCUIT(circ)->p_mux == NULL);
  893. /* Insert it in the map */
  894. hashent = tor_malloc_zero(sizeof(*hashent));
  895. hashent->chan_id = channel_id;
  896. hashent->circ_id = circ_id;
  897. hashent->muxinfo.cell_count = cell_count;
  898. hashent->muxinfo.direction = direction;
  899. /* Allocate policy specific circuit data if we need it */
  900. if (cmux->policy && cmux->policy->alloc_circ_data) {
  901. /* Assert that we have the means to free policy-specific data */
  902. tor_assert(cmux->policy->free_circ_data);
  903. /* Allocate it */
  904. hashent->muxinfo.policy_data =
  905. cmux->policy->alloc_circ_data(cmux,
  906. cmux->policy_data,
  907. circ,
  908. direction,
  909. cell_count);
  910. /* If we wanted policy data, it's an error not to get any */
  911. tor_assert(hashent->muxinfo.policy_data);
  912. }
  913. HT_INSERT(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
  914. hashent);
  915. /* Set the circuit's mux for this direction */
  916. if (direction == CELL_DIRECTION_OUT) circ->n_mux = cmux;
  917. else TO_OR_CIRCUIT(circ)->p_mux = cmux;
  918. /* Make sure the next/prev pointers are NULL */
  919. if (direction == CELL_DIRECTION_OUT) {
  920. circ->next_active_on_n_chan = NULL;
  921. circ->prev_active_on_n_chan = NULL;
  922. } else {
  923. TO_OR_CIRCUIT(circ)->next_active_on_p_chan = NULL;
  924. TO_OR_CIRCUIT(circ)->prev_active_on_p_chan = NULL;
  925. }
  926. /* Update counters */
  927. ++(cmux->n_circuits);
  928. if (cell_count > 0) {
  929. ++(cmux->n_active_circuits);
  930. circuitmux_make_circuit_active(cmux, circ, direction);
  931. }
  932. cmux->n_cells += cell_count;
  933. }
  934. circuitmux_assert_okay_paranoid(cmux);
  935. }
  936. /**
  937. * Detach a circuit from a circuitmux and update all counters as needed;
  938. * no-op if not attached.
  939. */
  940. MOCK_IMPL(void,
  941. circuitmux_detach_circuit,(circuitmux_t *cmux, circuit_t *circ))
  942. {
  943. chanid_circid_muxinfo_t search, *hashent = NULL;
  944. /*
  945. * Use this to keep track of whether we found it for n_chan or
  946. * p_chan for consistency checking.
  947. *
  948. * The 0 initializer is not a valid cell_direction_t value.
  949. * We assert that it has been replaced with a valid value before it is used.
  950. */
  951. cell_direction_t last_searched_direction = 0;
  952. tor_assert(cmux);
  953. tor_assert(cmux->chanid_circid_map);
  954. tor_assert(circ);
  955. circuitmux_assert_okay_paranoid(cmux);
  956. /* See if we have it for n_chan/n_circ_id */
  957. if (circ->n_chan) {
  958. search.chan_id = circ->n_chan->global_identifier;
  959. search.circ_id = circ->n_circ_id;
  960. hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
  961. &search);
  962. last_searched_direction = CELL_DIRECTION_OUT;
  963. }
  964. /* Got one? If not, see if it's an or_circuit_t and try p_chan/p_circ_id */
  965. if (!hashent) {
  966. if (circ->magic == OR_CIRCUIT_MAGIC) {
  967. search.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
  968. if (TO_OR_CIRCUIT(circ)->p_chan) {
  969. search.chan_id = TO_OR_CIRCUIT(circ)->p_chan->global_identifier;
  970. hashent = HT_FIND(chanid_circid_muxinfo_map,
  971. cmux->chanid_circid_map,
  972. &search);
  973. last_searched_direction = CELL_DIRECTION_IN;
  974. }
  975. }
  976. }
  977. tor_assert(last_searched_direction == CELL_DIRECTION_OUT
  978. || last_searched_direction == CELL_DIRECTION_IN);
  979. /*
  980. * If hashent isn't NULL, we have a circuit to detach; don't remove it from
  981. * the map until later of circuitmux_make_circuit_inactive() breaks.
  982. */
  983. if (hashent) {
  984. /* Update counters */
  985. --(cmux->n_circuits);
  986. if (hashent->muxinfo.cell_count > 0) {
  987. --(cmux->n_active_circuits);
  988. /* This does policy notifies, so comes before freeing policy data */
  989. circuitmux_make_circuit_inactive(cmux, circ, last_searched_direction);
  990. }
  991. cmux->n_cells -= hashent->muxinfo.cell_count;
  992. /* Free policy-specific data if we have it */
  993. if (hashent->muxinfo.policy_data) {
  994. /* If we have policy data, assert that we have the means to free it */
  995. tor_assert(cmux->policy);
  996. tor_assert(cmux->policy->free_circ_data);
  997. /* Call free_circ_data() */
  998. cmux->policy->free_circ_data(cmux,
  999. cmux->policy_data,
  1000. circ,
  1001. hashent->muxinfo.policy_data);
  1002. hashent->muxinfo.policy_data = NULL;
  1003. }
  1004. /* Consistency check: the direction must match the direction searched */
  1005. tor_assert(last_searched_direction == hashent->muxinfo.direction);
  1006. /* Clear the circuit's mux for this direction */
  1007. if (last_searched_direction == CELL_DIRECTION_OUT) circ->n_mux = NULL;
  1008. else TO_OR_CIRCUIT(circ)->p_mux = NULL;
  1009. /* Now remove it from the map */
  1010. HT_REMOVE(chanid_circid_muxinfo_map, cmux->chanid_circid_map, hashent);
  1011. /* Free the hash entry */
  1012. tor_free(hashent);
  1013. }
  1014. circuitmux_assert_okay_paranoid(cmux);
  1015. }
  1016. /**
  1017. * Make a circuit active; update active list and policy-specific info, but
  1018. * we don't mess with the counters or hash table here.
  1019. */
  1020. static void
  1021. circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ,
  1022. cell_direction_t direction)
  1023. {
  1024. circuit_t **next_active = NULL, **prev_active = NULL, **next_prev = NULL;
  1025. circuitmux_t *circuit_cmux = NULL;
  1026. chanid_circid_muxinfo_t *hashent = NULL;
  1027. channel_t *chan = NULL;
  1028. circid_t circ_id;
  1029. int already_active;
  1030. tor_assert(cmux);
  1031. tor_assert(circ);
  1032. tor_assert(direction == CELL_DIRECTION_OUT ||
  1033. direction == CELL_DIRECTION_IN);
  1034. /*
  1035. * Don't circuitmux_assert_okay_paranoid(cmux) here because the cell count
  1036. * already got changed and we have to update the list for it to be consistent
  1037. * again.
  1038. */
  1039. /* Get the right set of active list links for this direction */
  1040. if (direction == CELL_DIRECTION_OUT) {
  1041. next_active = &(circ->next_active_on_n_chan);
  1042. prev_active = &(circ->prev_active_on_n_chan);
  1043. circuit_cmux = circ->n_mux;
  1044. chan = circ->n_chan;
  1045. circ_id = circ->n_circ_id;
  1046. } else {
  1047. next_active = &(TO_OR_CIRCUIT(circ)->next_active_on_p_chan);
  1048. prev_active = &(TO_OR_CIRCUIT(circ)->prev_active_on_p_chan);
  1049. circuit_cmux = TO_OR_CIRCUIT(circ)->p_mux;
  1050. chan = TO_OR_CIRCUIT(circ)->p_chan;
  1051. circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
  1052. }
  1053. /* Assert that it is attached to this mux and a channel */
  1054. tor_assert(cmux == circuit_cmux);
  1055. tor_assert(chan != NULL);
  1056. /*
  1057. * Check if the circuit really was inactive; if it's active, at least one
  1058. * of the next_active and prev_active pointers will not be NULL, or this
  1059. * circuit will be either the head or tail of the list for this cmux.
  1060. */
  1061. already_active = (*prev_active != NULL || *next_active != NULL ||
  1062. cmux->active_circuits_head == circ ||
  1063. cmux->active_circuits_tail == circ);
  1064. /* If we're already active, log a warning and finish */
  1065. if (already_active) {
  1066. log_warn(LD_CIRC,
  1067. "Circuit %u on channel " U64_FORMAT " was already active",
  1068. (unsigned)circ_id, U64_PRINTF_ARG(chan->global_identifier));
  1069. return;
  1070. }
  1071. /*
  1072. * This is going at the head of the list; if the old head is not NULL,
  1073. * then its prev pointer should point to this.
  1074. */
  1075. *next_active = cmux->active_circuits_head; /* Next is old head */
  1076. *prev_active = NULL; /* Prev is NULL (this will be the head) */
  1077. if (cmux->active_circuits_head) {
  1078. /* The list had an old head; update its prev pointer */
  1079. next_prev =
  1080. circuitmux_prev_active_circ_p(cmux, cmux->active_circuits_head);
  1081. tor_assert(next_prev);
  1082. *next_prev = circ;
  1083. } else {
  1084. /* The list was empty; this becomes the tail as well */
  1085. cmux->active_circuits_tail = circ;
  1086. }
  1087. /* This becomes the new head of the list */
  1088. cmux->active_circuits_head = circ;
  1089. /* Policy-specific notification */
  1090. if (cmux->policy &&
  1091. cmux->policy->notify_circ_active) {
  1092. /* Okay, we need to check the circuit for policy data now */
  1093. hashent = circuitmux_find_map_entry(cmux, circ);
  1094. /* We should have found something */
  1095. tor_assert(hashent);
  1096. /* Notify */
  1097. cmux->policy->notify_circ_active(cmux, cmux->policy_data,
  1098. circ, hashent->muxinfo.policy_data);
  1099. }
  1100. circuitmux_assert_okay_paranoid(cmux);
  1101. }
  1102. /**
  1103. * Make a circuit inactive; update active list and policy-specific info, but
  1104. * we don't mess with the counters or hash table here.
  1105. */
  1106. static void
  1107. circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ,
  1108. cell_direction_t direction)
  1109. {
  1110. circuit_t **next_active = NULL, **prev_active = NULL;
  1111. circuit_t **next_prev = NULL, **prev_next = NULL;
  1112. circuitmux_t *circuit_cmux = NULL;
  1113. chanid_circid_muxinfo_t *hashent = NULL;
  1114. channel_t *chan = NULL;
  1115. circid_t circ_id;
  1116. int already_inactive;
  1117. tor_assert(cmux);
  1118. tor_assert(circ);
  1119. tor_assert(direction == CELL_DIRECTION_OUT ||
  1120. direction == CELL_DIRECTION_IN);
  1121. /*
  1122. * Don't circuitmux_assert_okay_paranoid(cmux) here because the cell count
  1123. * already got changed and we have to update the list for it to be consistent
  1124. * again.
  1125. */
  1126. /* Get the right set of active list links for this direction */
  1127. if (direction == CELL_DIRECTION_OUT) {
  1128. next_active = &(circ->next_active_on_n_chan);
  1129. prev_active = &(circ->prev_active_on_n_chan);
  1130. circuit_cmux = circ->n_mux;
  1131. chan = circ->n_chan;
  1132. circ_id = circ->n_circ_id;
  1133. } else {
  1134. next_active = &(TO_OR_CIRCUIT(circ)->next_active_on_p_chan);
  1135. prev_active = &(TO_OR_CIRCUIT(circ)->prev_active_on_p_chan);
  1136. circuit_cmux = TO_OR_CIRCUIT(circ)->p_mux;
  1137. chan = TO_OR_CIRCUIT(circ)->p_chan;
  1138. circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
  1139. }
  1140. /* Assert that it is attached to this mux and a channel */
  1141. tor_assert(cmux == circuit_cmux);
  1142. tor_assert(chan != NULL);
  1143. /*
  1144. * Check if the circuit really was active; if it's inactive, the
  1145. * next_active and prev_active pointers will be NULL and this circuit
  1146. * will not be the head or tail of the list for this cmux.
  1147. */
  1148. already_inactive = (*prev_active == NULL && *next_active == NULL &&
  1149. cmux->active_circuits_head != circ &&
  1150. cmux->active_circuits_tail != circ);
  1151. /* If we're already inactive, log a warning and finish */
  1152. if (already_inactive) {
  1153. log_warn(LD_CIRC,
  1154. "Circuit %d on channel " U64_FORMAT " was already inactive",
  1155. (unsigned)circ_id, U64_PRINTF_ARG(chan->global_identifier));
  1156. return;
  1157. }
  1158. /* Remove from the list; first get next_prev and prev_next */
  1159. if (*next_active) {
  1160. /*
  1161. * If there's a next circuit, its previous circuit becomes this
  1162. * circuit's previous circuit.
  1163. */
  1164. next_prev = circuitmux_prev_active_circ_p(cmux, *next_active);
  1165. } else {
  1166. /* Else, the tail becomes this circuit's previous circuit */
  1167. next_prev = &(cmux->active_circuits_tail);
  1168. }
  1169. /* Got next_prev, now prev_next */
  1170. if (*prev_active) {
  1171. /*
  1172. * If there's a previous circuit, its next circuit becomes this circuit's
  1173. * next circuit.
  1174. */
  1175. prev_next = circuitmux_next_active_circ_p(cmux, *prev_active);
  1176. } else {
  1177. /* Else, the head becomes this circuit's next circuit */
  1178. prev_next = &(cmux->active_circuits_head);
  1179. }
  1180. /* Assert that we got sensible values for the next/prev pointers */
  1181. tor_assert(next_prev != NULL);
  1182. tor_assert(prev_next != NULL);
  1183. /* Update the next/prev pointers - this removes circ from the list */
  1184. *next_prev = *prev_active;
  1185. *prev_next = *next_active;
  1186. /* Now null out prev_active/next_active */
  1187. *prev_active = NULL;
  1188. *next_active = NULL;
  1189. /* Policy-specific notification */
  1190. if (cmux->policy &&
  1191. cmux->policy->notify_circ_inactive) {
  1192. /* Okay, we need to check the circuit for policy data now */
  1193. hashent = circuitmux_find_map_entry(cmux, circ);
  1194. /* We should have found something */
  1195. tor_assert(hashent);
  1196. /* Notify */
  1197. cmux->policy->notify_circ_inactive(cmux, cmux->policy_data,
  1198. circ, hashent->muxinfo.policy_data);
  1199. }
  1200. circuitmux_assert_okay_paranoid(cmux);
  1201. }
  1202. /**
  1203. * Clear the cell counter for a circuit on a circuitmux
  1204. */
  1205. void
  1206. circuitmux_clear_num_cells(circuitmux_t *cmux, circuit_t *circ)
  1207. {
  1208. /* This is the same as setting the cell count to zero */
  1209. circuitmux_set_num_cells(cmux, circ, 0);
  1210. }
  1211. /**
  1212. * Set the cell counter for a circuit on a circuitmux
  1213. */
  1214. void
  1215. circuitmux_set_num_cells(circuitmux_t *cmux, circuit_t *circ,
  1216. unsigned int n_cells)
  1217. {
  1218. chanid_circid_muxinfo_t *hashent = NULL;
  1219. tor_assert(cmux);
  1220. tor_assert(circ);
  1221. circuitmux_assert_okay_paranoid(cmux);
  1222. /* Search for this circuit's entry */
  1223. hashent = circuitmux_find_map_entry(cmux, circ);
  1224. /* Assert that we found one */
  1225. tor_assert(hashent);
  1226. /* Update cmux cell counter */
  1227. cmux->n_cells -= hashent->muxinfo.cell_count;
  1228. cmux->n_cells += n_cells;
  1229. /* Do we need to notify a cmux policy? */
  1230. if (cmux->policy && cmux->policy->notify_set_n_cells) {
  1231. /* Call notify_set_n_cells */
  1232. cmux->policy->notify_set_n_cells(cmux,
  1233. cmux->policy_data,
  1234. circ,
  1235. hashent->muxinfo.policy_data,
  1236. n_cells);
  1237. }
  1238. /*
  1239. * Update cmux active circuit counter: is the old cell count > 0 and the
  1240. * new cell count == 0 ?
  1241. */
  1242. if (hashent->muxinfo.cell_count > 0 && n_cells == 0) {
  1243. --(cmux->n_active_circuits);
  1244. hashent->muxinfo.cell_count = n_cells;
  1245. circuitmux_make_circuit_inactive(cmux, circ, hashent->muxinfo.direction);
  1246. /* Is the old cell count == 0 and the new cell count > 0 ? */
  1247. } else if (hashent->muxinfo.cell_count == 0 && n_cells > 0) {
  1248. ++(cmux->n_active_circuits);
  1249. hashent->muxinfo.cell_count = n_cells;
  1250. circuitmux_make_circuit_active(cmux, circ, hashent->muxinfo.direction);
  1251. } else {
  1252. /*
  1253. * Update the entry cell count like this so we can put a
  1254. * circuitmux_assert_okay_paranoid inside make_circuit_(in)active() too.
  1255. */
  1256. hashent->muxinfo.cell_count = n_cells;
  1257. }
  1258. circuitmux_assert_okay_paranoid(cmux);
  1259. }
  1260. /*
  1261. * Functions for channel code to call to get a circuit to transmit from or
  1262. * notify that cells have been transmitted.
  1263. */
  1264. /**
  1265. * Pick a circuit to send from, using the active circuits list or a
  1266. * circuitmux policy if one is available. This is called from channel.c.
  1267. *
  1268. * If we would rather send a destroy cell, return NULL and set
  1269. * *<b>destroy_queue_out</b> to the destroy queue.
  1270. *
  1271. * If we have nothing to send, set *<b>destroy_queue_out</b> to NULL and
  1272. * return NULL.
  1273. */
  1274. circuit_t *
  1275. circuitmux_get_first_active_circuit(circuitmux_t *cmux,
  1276. cell_queue_t **destroy_queue_out)
  1277. {
  1278. circuit_t *circ = NULL;
  1279. tor_assert(cmux);
  1280. tor_assert(destroy_queue_out);
  1281. *destroy_queue_out = NULL;
  1282. if (cmux->destroy_cell_queue.n &&
  1283. (!cmux->last_cell_was_destroy || cmux->n_active_circuits == 0)) {
  1284. /* We have destroy cells to send, and either we just sent a relay cell,
  1285. * or we have no relay cells to send. */
  1286. /* XXXX We should let the cmux policy have some say in this eventually. */
  1287. /* XXXX Alternating is not a terribly brilliant approach here. */
  1288. *destroy_queue_out = &cmux->destroy_cell_queue;
  1289. cmux->last_cell_was_destroy = 1;
  1290. } else if (cmux->n_active_circuits > 0) {
  1291. /* We also must have a cell available for this to be the case */
  1292. tor_assert(cmux->n_cells > 0);
  1293. /* Do we have a policy-provided circuit selector? */
  1294. if (cmux->policy && cmux->policy->pick_active_circuit) {
  1295. circ = cmux->policy->pick_active_circuit(cmux, cmux->policy_data);
  1296. }
  1297. /* Fall back on the head of the active circuits list */
  1298. if (!circ) {
  1299. tor_assert(cmux->active_circuits_head);
  1300. circ = cmux->active_circuits_head;
  1301. }
  1302. cmux->last_cell_was_destroy = 0;
  1303. } else {
  1304. tor_assert(cmux->n_cells == 0);
  1305. tor_assert(cmux->destroy_cell_queue.n == 0);
  1306. }
  1307. return circ;
  1308. }
  1309. /**
  1310. * Notify the circuitmux that cells have been sent on a circuit; this
  1311. * is called from channel.c.
  1312. */
  1313. void
  1314. circuitmux_notify_xmit_cells(circuitmux_t *cmux, circuit_t *circ,
  1315. unsigned int n_cells)
  1316. {
  1317. chanid_circid_muxinfo_t *hashent = NULL;
  1318. int becomes_inactive = 0;
  1319. tor_assert(cmux);
  1320. tor_assert(circ);
  1321. circuitmux_assert_okay_paranoid(cmux);
  1322. if (n_cells == 0) return;
  1323. /*
  1324. * To handle this, we have to:
  1325. *
  1326. * 1.) Adjust the circuit's cell counter in the cmux hash table
  1327. * 2.) Move the circuit to the tail of the active_circuits linked list
  1328. * for this cmux, or make the circuit inactive if the cell count
  1329. * went to zero.
  1330. * 3.) Call cmux->policy->notify_xmit_cells(), if any
  1331. */
  1332. /* Find the hash entry */
  1333. hashent = circuitmux_find_map_entry(cmux, circ);
  1334. /* Assert that we found one */
  1335. tor_assert(hashent);
  1336. /* Adjust the cell counter and assert that we had that many cells to send */
  1337. tor_assert(n_cells <= hashent->muxinfo.cell_count);
  1338. hashent->muxinfo.cell_count -= n_cells;
  1339. /* Do we need to make the circuit inactive? */
  1340. if (hashent->muxinfo.cell_count == 0) becomes_inactive = 1;
  1341. /* Adjust the mux cell counter */
  1342. cmux->n_cells -= n_cells;
  1343. /* If we aren't making it inactive later, move it to the tail of the list */
  1344. if (!becomes_inactive) {
  1345. circuitmux_move_active_circ_to_tail(cmux, circ,
  1346. hashent->muxinfo.direction);
  1347. }
  1348. /*
  1349. * We call notify_xmit_cells() before making the circuit inactive if needed,
  1350. * so the policy can always count on this coming in on an active circuit.
  1351. */
  1352. if (cmux->policy && cmux->policy->notify_xmit_cells) {
  1353. cmux->policy->notify_xmit_cells(cmux, cmux->policy_data, circ,
  1354. hashent->muxinfo.policy_data,
  1355. n_cells);
  1356. }
  1357. /*
  1358. * Now make the circuit inactive if needed; this will call the policy's
  1359. * notify_circ_inactive() if present.
  1360. */
  1361. if (becomes_inactive) {
  1362. --(cmux->n_active_circuits);
  1363. circuitmux_make_circuit_inactive(cmux, circ, hashent->muxinfo.direction);
  1364. }
  1365. circuitmux_assert_okay_paranoid(cmux);
  1366. }
  1367. /**
  1368. * Notify the circuitmux that a destroy was sent, so we can update
  1369. * the counter.
  1370. */
  1371. void
  1372. circuitmux_notify_xmit_destroy(circuitmux_t *cmux)
  1373. {
  1374. tor_assert(cmux);
  1375. --(cmux->destroy_ctr);
  1376. --(global_destroy_ctr);
  1377. log_debug(LD_CIRC,
  1378. "Cmux at %p sent a destroy, cmux counter is now "I64_FORMAT", "
  1379. "global counter is now "I64_FORMAT,
  1380. cmux,
  1381. I64_PRINTF_ARG(cmux->destroy_ctr),
  1382. I64_PRINTF_ARG(global_destroy_ctr));
  1383. }
  1384. /*
  1385. * Circuitmux consistency checking assertions
  1386. */
  1387. /**
  1388. * Check that circuitmux data structures are consistent and fail with an
  1389. * assert if not.
  1390. */
  1391. void
  1392. circuitmux_assert_okay(circuitmux_t *cmux)
  1393. {
  1394. tor_assert(cmux);
  1395. /*
  1396. * Pass 1: iterate the hash table; for each entry:
  1397. * a) Check that the circuit has this cmux for n_mux or p_mux
  1398. * b) If the cell_count is > 0, set the mark bit; otherwise clear it
  1399. * c) Also check activeness (cell_count > 0 should be active)
  1400. * d) Count the number of circuits, active circuits and queued cells
  1401. * and at the end check that they match the counters in the cmux.
  1402. *
  1403. * Pass 2: iterate the active circuits list; for each entry,
  1404. * make sure the circuit is attached to this mux and appears
  1405. * in the hash table. Make sure the mark bit is 1, and clear
  1406. * it in the hash table entry. Consistency-check the linked
  1407. * list pointers.
  1408. *
  1409. * Pass 3: iterate the hash table again; assert if any active circuits
  1410. * (mark bit set to 1) are discovered that weren't cleared in pass 2
  1411. * (don't appear in the linked list).
  1412. */
  1413. circuitmux_assert_okay_pass_one(cmux);
  1414. circuitmux_assert_okay_pass_two(cmux);
  1415. circuitmux_assert_okay_pass_three(cmux);
  1416. }
  1417. /**
  1418. * Do the first pass of circuitmux_assert_okay(); see the comment in that
  1419. * function.
  1420. */
  1421. static void
  1422. circuitmux_assert_okay_pass_one(circuitmux_t *cmux)
  1423. {
  1424. chanid_circid_muxinfo_t **i = NULL;
  1425. uint64_t chan_id;
  1426. channel_t *chan;
  1427. circid_t circ_id;
  1428. circuit_t *circ;
  1429. or_circuit_t *or_circ;
  1430. unsigned int circ_is_active;
  1431. circuit_t **next_p, **prev_p;
  1432. unsigned int n_circuits, n_active_circuits, n_cells;
  1433. tor_assert(cmux);
  1434. tor_assert(cmux->chanid_circid_map);
  1435. /* Reset the counters */
  1436. n_circuits = n_active_circuits = n_cells = 0;
  1437. /* Start iterating the hash table */
  1438. i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
  1439. while (i) {
  1440. /* Assert that the hash table entry isn't null */
  1441. tor_assert(*i);
  1442. /* Get the channel and circuit id */
  1443. chan_id = (*i)->chan_id;
  1444. circ_id = (*i)->circ_id;
  1445. /* Find the channel and circuit, assert that they exist */
  1446. chan = channel_find_by_global_id(chan_id);
  1447. tor_assert(chan);
  1448. circ = circuit_get_by_circid_channel_even_if_marked(circ_id, chan);
  1449. tor_assert(circ);
  1450. /* Clear the circ_is_active bit to start */
  1451. circ_is_active = 0;
  1452. /* Assert that we know which direction this is going */
  1453. tor_assert((*i)->muxinfo.direction == CELL_DIRECTION_OUT ||
  1454. (*i)->muxinfo.direction == CELL_DIRECTION_IN);
  1455. if ((*i)->muxinfo.direction == CELL_DIRECTION_OUT) {
  1456. /* We should be n_mux on this circuit */
  1457. tor_assert(cmux == circ->n_mux);
  1458. tor_assert(chan == circ->n_chan);
  1459. /* Get next and prev for next test */
  1460. next_p = &(circ->next_active_on_n_chan);
  1461. prev_p = &(circ->prev_active_on_n_chan);
  1462. } else {
  1463. /* This should be an or_circuit_t and we should be p_mux */
  1464. or_circ = TO_OR_CIRCUIT(circ);
  1465. tor_assert(cmux == or_circ->p_mux);
  1466. tor_assert(chan == or_circ->p_chan);
  1467. /* Get next and prev for next test */
  1468. next_p = &(or_circ->next_active_on_p_chan);
  1469. prev_p = &(or_circ->prev_active_on_p_chan);
  1470. }
  1471. /*
  1472. * Should this circuit be active? I.e., does the mux know about > 0
  1473. * cells on it?
  1474. */
  1475. circ_is_active = ((*i)->muxinfo.cell_count > 0);
  1476. /* It should be in the linked list iff it's active */
  1477. if (circ_is_active) {
  1478. /* Either we have a next link or we are the tail */
  1479. tor_assert(*next_p || (circ == cmux->active_circuits_tail));
  1480. /* Either we have a prev link or we are the head */
  1481. tor_assert(*prev_p || (circ == cmux->active_circuits_head));
  1482. /* Increment the active circuits counter */
  1483. ++n_active_circuits;
  1484. } else {
  1485. /* Shouldn't be in list, so no next or prev link */
  1486. tor_assert(!(*next_p));
  1487. tor_assert(!(*prev_p));
  1488. /* And can't be head or tail */
  1489. tor_assert(circ != cmux->active_circuits_head);
  1490. tor_assert(circ != cmux->active_circuits_tail);
  1491. }
  1492. /* Increment the circuits counter */
  1493. ++n_circuits;
  1494. /* Adjust the cell counter */
  1495. n_cells += (*i)->muxinfo.cell_count;
  1496. /* Set the mark bit to circ_is_active */
  1497. (*i)->muxinfo.mark = circ_is_active;
  1498. /* Advance to the next entry */
  1499. i = HT_NEXT(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);
  1500. }
  1501. /* Now check the counters */
  1502. tor_assert(n_cells == cmux->n_cells);
  1503. tor_assert(n_circuits == cmux->n_circuits);
  1504. tor_assert(n_active_circuits == cmux->n_active_circuits);
  1505. }
  1506. /**
  1507. * Do the second pass of circuitmux_assert_okay(); see the comment in that
  1508. * function.
  1509. */
  1510. static void
  1511. circuitmux_assert_okay_pass_two(circuitmux_t *cmux)
  1512. {
  1513. circuit_t *curr_circ, *prev_circ = NULL, *next_circ;
  1514. or_circuit_t *curr_or_circ;
  1515. uint64_t curr_chan_id;
  1516. circid_t curr_circ_id;
  1517. circuit_t **next_p, **prev_p;
  1518. channel_t *chan;
  1519. unsigned int n_active_circuits = 0;
  1520. cell_direction_t direction;
  1521. chanid_circid_muxinfo_t search, *hashent = NULL;
  1522. tor_assert(cmux);
  1523. tor_assert(cmux->chanid_circid_map);
  1524. /*
  1525. * Walk the linked list of active circuits in cmux; keep track of the
  1526. * previous circuit seen for consistency checking purposes. Count them
  1527. * to make sure the number in the linked list matches
  1528. * cmux->n_active_circuits.
  1529. */
  1530. curr_circ = cmux->active_circuits_head;
  1531. while (curr_circ) {
  1532. /* Reset some things */
  1533. chan = NULL;
  1534. curr_or_circ = NULL;
  1535. next_circ = NULL;
  1536. next_p = prev_p = NULL;
  1537. direction = 0;
  1538. /* Figure out if this is n_mux or p_mux */
  1539. if (cmux == curr_circ->n_mux) {
  1540. /* Get next_p and prev_p */
  1541. next_p = &(curr_circ->next_active_on_n_chan);
  1542. prev_p = &(curr_circ->prev_active_on_n_chan);
  1543. /* Get the channel */
  1544. chan = curr_circ->n_chan;
  1545. /* Get the circuit id */
  1546. curr_circ_id = curr_circ->n_circ_id;
  1547. /* Remember the direction */
  1548. direction = CELL_DIRECTION_OUT;
  1549. } else {
  1550. /* We must be p_mux and this must be an or_circuit_t */
  1551. curr_or_circ = TO_OR_CIRCUIT(curr_circ);
  1552. tor_assert(cmux == curr_or_circ->p_mux);
  1553. /* Get next_p and prev_p */
  1554. next_p = &(curr_or_circ->next_active_on_p_chan);
  1555. prev_p = &(curr_or_circ->prev_active_on_p_chan);
  1556. /* Get the channel */
  1557. chan = curr_or_circ->p_chan;
  1558. /* Get the circuit id */
  1559. curr_circ_id = curr_or_circ->p_circ_id;
  1560. /* Remember the direction */
  1561. direction = CELL_DIRECTION_IN;
  1562. }
  1563. /* Assert that we got a channel and get the channel ID */
  1564. tor_assert(chan);
  1565. curr_chan_id = chan->global_identifier;
  1566. /* Assert that prev_p points to last circuit we saw */
  1567. tor_assert(*prev_p == prev_circ);
  1568. /* If that's NULL, assert that we are the head */
  1569. if (!(*prev_p)) tor_assert(curr_circ == cmux->active_circuits_head);
  1570. /* Get the next circuit */
  1571. next_circ = *next_p;
  1572. /* If it's NULL, assert that we are the tail */
  1573. if (!(*next_p)) tor_assert(curr_circ == cmux->active_circuits_tail);
  1574. /* Now find the hash table entry for this circuit */
  1575. search.chan_id = curr_chan_id;
  1576. search.circ_id = curr_circ_id;
  1577. hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
  1578. &search);
  1579. /* Assert that we have one */
  1580. tor_assert(hashent);
  1581. /* Assert that the direction matches */
  1582. tor_assert(direction == hashent->muxinfo.direction);
  1583. /* Assert that the hash entry got marked in pass one */
  1584. tor_assert(hashent->muxinfo.mark);
  1585. /* Clear the mark */
  1586. hashent->muxinfo.mark = 0;
  1587. /* Increment the counter */
  1588. ++n_active_circuits;
  1589. /* Advance to the next active circuit and update prev_circ */
  1590. prev_circ = curr_circ;
  1591. curr_circ = next_circ;
  1592. }
  1593. /* Assert that the counter matches the cmux */
  1594. tor_assert(n_active_circuits == cmux->n_active_circuits);
  1595. }
  1596. /**
  1597. * Do the third pass of circuitmux_assert_okay(); see the comment in that
  1598. * function.
  1599. */
  1600. static void
  1601. circuitmux_assert_okay_pass_three(circuitmux_t *cmux)
  1602. {
  1603. chanid_circid_muxinfo_t **i = NULL;
  1604. tor_assert(cmux);
  1605. tor_assert(cmux->chanid_circid_map);
  1606. /* Start iterating the hash table */
  1607. i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
  1608. /* Advance through each entry */
  1609. while (i) {
  1610. /* Assert that it isn't null */
  1611. tor_assert(*i);
  1612. /*
  1613. * Assert that this entry is not marked - i.e., that either we didn't
  1614. * think it should be active in pass one or we saw it in the active
  1615. * circuits linked list.
  1616. */
  1617. tor_assert(!((*i)->muxinfo.mark));
  1618. /* Advance to the next entry */
  1619. i = HT_NEXT(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);
  1620. }
  1621. }
  1622. /*DOCDOC */
  1623. void
  1624. circuitmux_append_destroy_cell(channel_t *chan,
  1625. circuitmux_t *cmux,
  1626. circid_t circ_id,
  1627. uint8_t reason)
  1628. {
  1629. cell_t cell;
  1630. memset(&cell, 0, sizeof(cell_t));
  1631. cell.circ_id = circ_id;
  1632. cell.command = CELL_DESTROY;
  1633. cell.payload[0] = (uint8_t) reason;
  1634. cell_queue_append_packed_copy(NULL, &cmux->destroy_cell_queue, 0, &cell,
  1635. chan->wide_circ_ids, 0);
  1636. /* Destroy entering the queue, update counters */
  1637. ++(cmux->destroy_ctr);
  1638. ++global_destroy_ctr;
  1639. log_debug(LD_CIRC,
  1640. "Cmux at %p queued a destroy for circ %u, cmux counter is now "
  1641. I64_FORMAT", global counter is now "I64_FORMAT,
  1642. cmux, circ_id,
  1643. I64_PRINTF_ARG(cmux->destroy_ctr),
  1644. I64_PRINTF_ARG(global_destroy_ctr));
  1645. /* XXXX Duplicate code from append_cell_to_circuit_queue */
  1646. if (!channel_has_queued_writes(chan)) {
  1647. /* There is no data at all waiting to be sent on the outbuf. Add a
  1648. * cell, so that we can notice when it gets flushed, flushed_some can
  1649. * get called, and we can start putting more data onto the buffer then.
  1650. */
  1651. log_debug(LD_GENERAL, "Primed a buffer.");
  1652. channel_flush_from_first_active_circuit(chan, 1);
  1653. }
  1654. }
  1655. /*DOCDOC; for debugging 12184. This runs slowly. */
  1656. int64_t
  1657. circuitmux_count_queued_destroy_cells(const channel_t *chan,
  1658. const circuitmux_t *cmux)
  1659. {
  1660. int64_t n_destroy_cells = cmux->destroy_ctr;
  1661. int64_t destroy_queue_size = cmux->destroy_cell_queue.n;
  1662. int64_t manual_total = 0;
  1663. int64_t manual_total_in_map = 0;
  1664. packed_cell_t *cell;
  1665. TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
  1666. circid_t id;
  1667. ++manual_total;
  1668. id = packed_cell_get_circid(cell, chan->wide_circ_ids);
  1669. if (circuit_id_in_use_on_channel(id, (channel_t*)chan))
  1670. ++manual_total_in_map;
  1671. }
  1672. if (n_destroy_cells != destroy_queue_size ||
  1673. n_destroy_cells != manual_total ||
  1674. n_destroy_cells != manual_total_in_map) {
  1675. log_warn(LD_BUG, " Discrepancy in counts for queued destroy cells on "
  1676. "circuitmux. n="I64_FORMAT". queue_size="I64_FORMAT". "
  1677. "manual_total="I64_FORMAT". manual_total_in_map="I64_FORMAT".",
  1678. I64_PRINTF_ARG(n_destroy_cells),
  1679. I64_PRINTF_ARG(destroy_queue_size),
  1680. I64_PRINTF_ARG(manual_total),
  1681. I64_PRINTF_ARG(manual_total_in_map));
  1682. }
  1683. return n_destroy_cells;
  1684. }
  1685. /**
  1686. * Compare cmuxes to see which is more preferred; return < 0 if
  1687. * cmux_1 has higher priority (i.e., cmux_1 < cmux_2 in the scheduler's
  1688. * sort order), > 0 if cmux_2 has higher priority, or 0 if they are
  1689. * equally preferred.
  1690. *
  1691. * If the cmuxes have different cmux policies or the policy does not
  1692. * support the cmp_cmux method, return 0.
  1693. */
  1694. MOCK_IMPL(int,
  1695. circuitmux_compare_muxes, (circuitmux_t *cmux_1, circuitmux_t *cmux_2))
  1696. {
  1697. const circuitmux_policy_t *policy;
  1698. tor_assert(cmux_1);
  1699. tor_assert(cmux_2);
  1700. if (cmux_1 == cmux_2) {
  1701. /* Equivalent because they're the same cmux */
  1702. return 0;
  1703. }
  1704. if (cmux_1->policy && cmux_2->policy) {
  1705. if (cmux_1->policy == cmux_2->policy) {
  1706. policy = cmux_1->policy;
  1707. if (policy->cmp_cmux) {
  1708. /* Okay, we can compare! */
  1709. return policy->cmp_cmux(cmux_1, cmux_1->policy_data,
  1710. cmux_2, cmux_2->policy_data);
  1711. } else {
  1712. /*
  1713. * Equivalent because the policy doesn't know how to compare between
  1714. * muxes.
  1715. */
  1716. return 0;
  1717. }
  1718. } else {
  1719. /* Equivalent because they have different policies */
  1720. return 0;
  1721. }
  1722. } else {
  1723. /* Equivalent because one or both are missing a policy */
  1724. return 0;
  1725. }
  1726. }