circuitmux.c 52 KB

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