circuitmux.c 60 KB

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