circuitmux.c 59 KB

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