scheduler.c 26 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773
  1. /* Copyright (c) 2013-2017, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. #include "or.h"
  4. #include "config.h"
  5. #include "compat_libevent.h"
  6. #define SCHEDULER_PRIVATE_
  7. #define SCHEDULER_KIST_PRIVATE
  8. #include "scheduler.h"
  9. #include "main.h"
  10. #include "buffers.h"
  11. #define TOR_CHANNEL_INTERNAL_
  12. #include "channeltls.h"
  13. #include <event2/event.h>
  14. /**
  15. * \file scheduler.c
  16. * \brief Channel scheduling system: decides which channels should send and
  17. * receive when.
  18. *
  19. * This module is the global/common parts of the scheduling system. This system
  20. * is what decides what channels get to send cells on their circuits and when.
  21. *
  22. * Terms:
  23. * - "Scheduling system": the collection of scheduler*.{h,c} files and their
  24. * aggregate behavior.
  25. * - "Scheduler implementation": a scheduler_t. The scheduling system has one
  26. * active scheduling implementation at a time.
  27. *
  28. * In this file you will find state that any scheduler implementation can have
  29. * access to as well as the functions the rest of Tor uses to interact with the
  30. * scheduling system.
  31. *
  32. * The earliest versions of Tor approximated a kind of round-robin system
  33. * among active connections, but only approximated it. It would only consider
  34. * one connection (roughly equal to a channel in today's terms) at a time, and
  35. * thus could only prioritize circuits against others on the same connection.
  36. *
  37. * Then in response to the KIST paper[0], Tor implemented a global
  38. * circuit scheduler. It was supposed to prioritize circuits across many
  39. * channels, but wasn't effective. It is preserved in scheduler_vanilla.c.
  40. *
  41. * [0]: http://www.robgjansen.com/publications/kist-sec2014.pdf
  42. *
  43. * Then we actually got around to implementing KIST for real. We decided to
  44. * modularize the scheduler so new ones can be implemented. You can find KIST
  45. * in scheduler_kist.c.
  46. *
  47. * Channels have one of four scheduling states based on whether or not they
  48. * have cells to send and whether or not they are able to send.
  49. *
  50. * <ol>
  51. * <li>
  52. * Not open for writes, no cells to send.
  53. * <ul><li> Not much to do here, and the channel will have scheduler_state
  54. * == SCHED_CHAN_IDLE
  55. * <li> Transitions from:
  56. * <ul>
  57. * <li>Open for writes/has cells by simultaneously draining all circuit
  58. * queues and filling the output buffer.
  59. * </ul>
  60. * <li> Transitions to:
  61. * <ul>
  62. * <li> Not open for writes/has cells by arrival of cells on an attached
  63. * circuit (this would be driven from append_cell_to_circuit_queue())
  64. * <li> Open for writes/no cells by a channel type specific path;
  65. * driven from connection_or_flushed_some() for channel_tls_t.
  66. * </ul>
  67. * </ul>
  68. *
  69. * <li> Open for writes, no cells to send
  70. * <ul>
  71. * <li>Not much here either; this will be the state an idle but open
  72. * channel can be expected to settle in. It will have scheduler_state
  73. * == SCHED_CHAN_WAITING_FOR_CELLS
  74. * <li> Transitions from:
  75. * <ul>
  76. * <li>Not open for writes/no cells by flushing some of the output
  77. * buffer.
  78. * <li>Open for writes/has cells by the scheduler moving cells from
  79. * circuit queues to channel output queue, but not having enough
  80. * to fill the output queue.
  81. * </ul>
  82. * <li> Transitions to:
  83. * <ul>
  84. * <li>Open for writes/has cells by arrival of new cells on an attached
  85. * circuit, in append_cell_to_circuit_queue()
  86. * </ul>
  87. * </ul>
  88. *
  89. * <li>Not open for writes, cells to send
  90. * <ul>
  91. * <li>This is the state of a busy circuit limited by output bandwidth;
  92. * cells have piled up in the circuit queues waiting to be relayed.
  93. * The channel will have scheduler_state == SCHED_CHAN_WAITING_TO_WRITE.
  94. * <li> Transitions from:
  95. * <ul>
  96. * <li>Not open for writes/no cells by arrival of cells on an attached
  97. * circuit
  98. * <li>Open for writes/has cells by filling an output buffer without
  99. * draining all cells from attached circuits
  100. * </ul>
  101. * <li> Transitions to:
  102. * <ul>
  103. * <li>Opens for writes/has cells by draining some of the output buffer
  104. * via the connection_or_flushed_some() path (for channel_tls_t).
  105. * </ul>
  106. * </ul>
  107. *
  108. * <li>Open for writes, cells to send
  109. * <ul>
  110. * <li>This connection is ready to relay some cells and waiting for
  111. * the scheduler to choose it. The channel will have scheduler_state ==
  112. * SCHED_CHAN_PENDING.
  113. * <li>Transitions from:
  114. * <ul>
  115. * <li>Not open for writes/has cells by the connection_or_flushed_some()
  116. * path
  117. * <li>Open for writes/no cells by the append_cell_to_circuit_queue()
  118. * path
  119. * </ul>
  120. * <li> Transitions to:
  121. * <ul>
  122. * <li>Not open for writes/no cells by draining all circuit queues and
  123. * simultaneously filling the output buffer.
  124. * <li>Not open for writes/has cells by writing enough cells to fill the
  125. * output buffer
  126. * <li>Open for writes/no cells by draining all attached circuit queues
  127. * without also filling the output buffer
  128. * </ul>
  129. * </ul>
  130. * </ol>
  131. *
  132. * Other event-driven parts of the code move channels between these scheduling
  133. * states by calling scheduler functions. The scheduling system builds up a
  134. * list of channels in the SCHED_CHAN_PENDING state that the scheduler
  135. * implementation should then use when it runs. Scheduling implementations need
  136. * to properly update channel states during their scheduler_t->run() function
  137. * as that is the only opportunity for channels to move from SCHED_CHAN_PENDING
  138. * to any other state.
  139. *
  140. * The remainder of this file is a small amount of state that any scheduler
  141. * implementation should have access to, and the functions the rest of Tor uses
  142. * to interact with the scheduling system.
  143. */
  144. /*****************************************************************************
  145. * Scheduling system state
  146. *
  147. * State that can be accessed from any scheduler implementation (but not
  148. * outside the scheduling system)
  149. *****************************************************************************/
  150. /** DOCDOC */
  151. STATIC const scheduler_t *the_scheduler;
  152. /**
  153. * We keep a list of channels that are pending - i.e, have cells to write
  154. * and can accept them to send. The enum scheduler_state in channel_t
  155. * is reserved for our use.
  156. *
  157. * Priority queue of channels that can write and have cells (pending work)
  158. */
  159. STATIC smartlist_t *channels_pending = NULL;
  160. /**
  161. * This event runs the scheduler from its callback, and is manually
  162. * activated whenever a channel enters open for writes/cells to send.
  163. */
  164. STATIC struct event *run_sched_ev = NULL;
  165. static int have_logged_kist_suddenly_disabled = 0;
  166. /*****************************************************************************
  167. * Scheduling system static function definitions
  168. *
  169. * Functions that can only be accessed from this file.
  170. *****************************************************************************/
  171. /** Return a human readable string for the given scheduler type. */
  172. static const char *
  173. get_scheduler_type_string(scheduler_types_t type)
  174. {
  175. switch (type) {
  176. case SCHEDULER_VANILLA:
  177. return "Vanilla";
  178. case SCHEDULER_KIST:
  179. return "KIST";
  180. case SCHEDULER_KIST_LITE:
  181. return "KISTLite";
  182. case SCHEDULER_NONE:
  183. /* fallthrough */
  184. default:
  185. tor_assert_unreached();
  186. return "(N/A)";
  187. }
  188. }
  189. /**
  190. * Scheduler event callback; this should get triggered once per event loop
  191. * if any scheduling work was created during the event loop.
  192. */
  193. static void
  194. scheduler_evt_callback(evutil_socket_t fd, short events, void *arg)
  195. {
  196. (void) fd;
  197. (void) events;
  198. (void) arg;
  199. log_debug(LD_SCHED, "Scheduler event callback called");
  200. /* Run the scheduler. This is a mandatory function. */
  201. /* We might as well assert on this. If this function doesn't exist, no cells
  202. * are getting scheduled. Things are very broken. scheduler_t says the run()
  203. * function is mandatory. */
  204. tor_assert(the_scheduler->run);
  205. the_scheduler->run();
  206. /* Schedule itself back in if it has more work. */
  207. /* Again, might as well assert on this mandatory scheduler_t function. If it
  208. * doesn't exist, there's no way to tell libevent to run the scheduler again
  209. * in the future. */
  210. tor_assert(the_scheduler->schedule);
  211. the_scheduler->schedule();
  212. }
  213. /** Using the global options, select the scheduler we should be using. */
  214. static void
  215. select_scheduler(void)
  216. {
  217. scheduler_t *new_scheduler = NULL;
  218. #ifdef TOR_UNIT_TESTS
  219. /* This is hella annoying to set in the options for every test that passes
  220. * through the scheduler and there are many so if we don't explicitly have
  221. * a list of types set, just put the vanilla one. */
  222. if (get_options()->SchedulerTypes_ == NULL) {
  223. the_scheduler = get_vanilla_scheduler();
  224. return;
  225. }
  226. #endif /* defined(TOR_UNIT_TESTS) */
  227. /* This list is ordered that is first entry has the first priority. Thus, as
  228. * soon as we find a scheduler type that we can use, we use it and stop. */
  229. SMARTLIST_FOREACH_BEGIN(get_options()->SchedulerTypes_, int *, type) {
  230. switch (*type) {
  231. case SCHEDULER_VANILLA:
  232. new_scheduler = get_vanilla_scheduler();
  233. goto end;
  234. case SCHEDULER_KIST:
  235. if (!scheduler_can_use_kist()) {
  236. #ifdef HAVE_KIST_SUPPORT
  237. if (!have_logged_kist_suddenly_disabled) {
  238. /* We should only log this once in most cases. If it was the kernel
  239. * losing support for kist that caused scheduler_can_use_kist() to
  240. * return false, then this flag makes sure we only log this message
  241. * once. If it was the consensus that switched from "yes use kist"
  242. * to "no don't use kist", then we still set the flag so we log
  243. * once, but we unset the flag elsewhere if we ever can_use_kist()
  244. * again.
  245. */
  246. have_logged_kist_suddenly_disabled = 1;
  247. log_notice(LD_SCHED, "Scheduler type KIST has been disabled by "
  248. "the consensus or no kernel support.");
  249. }
  250. #else /* !(defined(HAVE_KIST_SUPPORT)) */
  251. log_info(LD_SCHED, "Scheduler type KIST not built in");
  252. #endif /* defined(HAVE_KIST_SUPPORT) */
  253. continue;
  254. }
  255. /* This flag will only get set in one of two cases:
  256. * 1 - the kernel lost support for kist. In that case, we don't expect to
  257. * ever end up here
  258. * 2 - the consensus went from "yes use kist" to "no don't use kist".
  259. * We might end up here if the consensus changes back to "yes", in which
  260. * case we might want to warn the user again if it goes back to "no"
  261. * yet again. Thus we unset the flag */
  262. have_logged_kist_suddenly_disabled = 0;
  263. new_scheduler = get_kist_scheduler();
  264. scheduler_kist_set_full_mode();
  265. goto end;
  266. case SCHEDULER_KIST_LITE:
  267. new_scheduler = get_kist_scheduler();
  268. scheduler_kist_set_lite_mode();
  269. goto end;
  270. case SCHEDULER_NONE:
  271. /* fallthrough */
  272. default:
  273. /* Our option validation should have caught this. */
  274. tor_assert_unreached();
  275. }
  276. } SMARTLIST_FOREACH_END(type);
  277. end:
  278. if (new_scheduler == NULL) {
  279. log_err(LD_SCHED, "Tor was unable to select a scheduler type. Please "
  280. "make sure Schedulers is correctly configured with "
  281. "what Tor does support.");
  282. /* We weren't able to choose a scheduler which means that none of the ones
  283. * set in Schedulers are supported or usable. We will respect the user
  284. * wishes of using what it has been configured and don't do a sneaky
  285. * fallback. Because this can be changed at runtime, we have to stop tor
  286. * right now. */
  287. exit(1); // XXXX bad exit
  288. }
  289. /* Set the chosen scheduler. */
  290. the_scheduler = new_scheduler;
  291. }
  292. /**
  293. * Helper function called from a few different places. It changes the
  294. * scheduler implementation, if necessary. And if it did, it then tells the
  295. * old one to free its state and the new one to initialize.
  296. */
  297. static void
  298. set_scheduler(void)
  299. {
  300. const scheduler_t *old_scheduler = the_scheduler;
  301. scheduler_types_t old_scheduler_type = SCHEDULER_NONE;
  302. /* We keep track of the type in order to log only if the type switched. We
  303. * can't just use the scheduler pointers because KIST and KISTLite share the
  304. * same object. */
  305. if (the_scheduler) {
  306. old_scheduler_type = the_scheduler->type;
  307. }
  308. /* From the options, select the scheduler type to set. */
  309. select_scheduler();
  310. tor_assert(the_scheduler);
  311. /* We look at the pointer difference in case the old sched and new sched
  312. * share the same scheduler object, as is the case with KIST and KISTLite. */
  313. if (old_scheduler != the_scheduler) {
  314. /* Allow the old scheduler to clean up, if needed. */
  315. if (old_scheduler && old_scheduler->free_all) {
  316. old_scheduler->free_all();
  317. }
  318. /* Initialize the new scheduler. */
  319. if (the_scheduler->init) {
  320. the_scheduler->init();
  321. }
  322. }
  323. /* Finally we notice log if we switched schedulers. We use the type in case
  324. * two schedulers share a scheduler object. */
  325. if (old_scheduler_type != the_scheduler->type) {
  326. log_notice(LD_CONFIG, "Scheduler type %s has been enabled.",
  327. get_scheduler_type_string(the_scheduler->type));
  328. }
  329. }
  330. /*****************************************************************************
  331. * Scheduling system private function definitions
  332. *
  333. * Functions that can only be accessed from scheduler*.c
  334. *****************************************************************************/
  335. /** Returns human readable string for the given channel scheduler state. */
  336. const char *
  337. get_scheduler_state_string(int scheduler_state)
  338. {
  339. switch (scheduler_state) {
  340. case SCHED_CHAN_IDLE:
  341. return "IDLE";
  342. case SCHED_CHAN_WAITING_FOR_CELLS:
  343. return "WAITING_FOR_CELLS";
  344. case SCHED_CHAN_WAITING_TO_WRITE:
  345. return "WAITING_TO_WRITE";
  346. case SCHED_CHAN_PENDING:
  347. return "PENDING";
  348. default:
  349. return "(invalid)";
  350. }
  351. }
  352. /** Helper that logs channel scheduler_state changes. Use this instead of
  353. * setting scheduler_state directly. */
  354. void
  355. scheduler_set_channel_state(channel_t *chan, int new_state)
  356. {
  357. log_debug(LD_SCHED, "chan %" PRIu64 " changed from scheduler state %s to %s",
  358. chan->global_identifier,
  359. get_scheduler_state_string(chan->scheduler_state),
  360. get_scheduler_state_string(new_state));
  361. chan->scheduler_state = new_state;
  362. }
  363. /** Return the pending channel list. */
  364. smartlist_t *
  365. get_channels_pending(void)
  366. {
  367. return channels_pending;
  368. }
  369. /** Comparison function to use when sorting pending channels. */
  370. MOCK_IMPL(int,
  371. scheduler_compare_channels, (const void *c1_v, const void *c2_v))
  372. {
  373. const channel_t *c1 = NULL, *c2 = NULL;
  374. /* These are a workaround for -Wbad-function-cast throwing a fit */
  375. const circuitmux_policy_t *p1, *p2;
  376. uintptr_t p1_i, p2_i;
  377. tor_assert(c1_v);
  378. tor_assert(c2_v);
  379. c1 = (const channel_t *)(c1_v);
  380. c2 = (const channel_t *)(c2_v);
  381. if (c1 != c2) {
  382. if (circuitmux_get_policy(c1->cmux) ==
  383. circuitmux_get_policy(c2->cmux)) {
  384. /* Same cmux policy, so use the mux comparison */
  385. return circuitmux_compare_muxes(c1->cmux, c2->cmux);
  386. } else {
  387. /*
  388. * Different policies; not important to get this edge case perfect
  389. * because the current code never actually gives different channels
  390. * different cmux policies anyway. Just use this arbitrary but
  391. * definite choice.
  392. */
  393. p1 = circuitmux_get_policy(c1->cmux);
  394. p2 = circuitmux_get_policy(c2->cmux);
  395. p1_i = (uintptr_t)p1;
  396. p2_i = (uintptr_t)p2;
  397. return (p1_i < p2_i) ? -1 : 1;
  398. }
  399. } else {
  400. /* c1 == c2, so always equal */
  401. return 0;
  402. }
  403. }
  404. /*****************************************************************************
  405. * Scheduling system global functions
  406. *
  407. * Functions that can be accessed from anywhere in Tor.
  408. *****************************************************************************/
  409. /**
  410. * This is how the scheduling system is notified of Tor's configuration
  411. * changing. For example: a SIGHUP was issued.
  412. */
  413. void
  414. scheduler_conf_changed(void)
  415. {
  416. /* Let the scheduler decide what it should do. */
  417. set_scheduler();
  418. /* Then tell the (possibly new) scheduler that we have new options. */
  419. if (the_scheduler->on_new_options) {
  420. the_scheduler->on_new_options();
  421. }
  422. }
  423. /**
  424. * Whenever we get a new consensus, this function is called.
  425. */
  426. void
  427. scheduler_notify_networkstatus_changed(void)
  428. {
  429. /* Maybe the consensus param made us change the scheduler. */
  430. set_scheduler();
  431. /* Then tell the (possibly new) scheduler that we have a new consensus */
  432. if (the_scheduler->on_new_consensus) {
  433. the_scheduler->on_new_consensus();
  434. }
  435. }
  436. /**
  437. * Free everything scheduling-related from main.c. Note this is only called
  438. * when Tor is shutting down, while scheduler_t->free_all() is called both when
  439. * Tor is shutting down and when we are switching schedulers.
  440. */
  441. void
  442. scheduler_free_all(void)
  443. {
  444. log_debug(LD_SCHED, "Shutting down scheduler");
  445. if (run_sched_ev) {
  446. if (event_del(run_sched_ev) < 0) {
  447. log_warn(LD_BUG, "Problem deleting run_sched_ev");
  448. }
  449. tor_event_free(run_sched_ev);
  450. run_sched_ev = NULL;
  451. }
  452. if (channels_pending) {
  453. /* We don't have ownership of the objects in this list. */
  454. smartlist_free(channels_pending);
  455. channels_pending = NULL;
  456. }
  457. if (the_scheduler && the_scheduler->free_all) {
  458. the_scheduler->free_all();
  459. }
  460. the_scheduler = NULL;
  461. }
  462. /** Mark a channel as no longer ready to accept writes. */
  463. MOCK_IMPL(void,
  464. scheduler_channel_doesnt_want_writes,(channel_t *chan))
  465. {
  466. IF_BUG_ONCE(!chan) {
  467. return;
  468. }
  469. IF_BUG_ONCE(!channels_pending) {
  470. return;
  471. }
  472. /* If it's already in pending, we can put it in waiting_to_write */
  473. if (chan->scheduler_state == SCHED_CHAN_PENDING) {
  474. /*
  475. * It's in channels_pending, so it shouldn't be in any of
  476. * the other lists. It can't write any more, so it goes to
  477. * channels_waiting_to_write.
  478. */
  479. smartlist_pqueue_remove(channels_pending,
  480. scheduler_compare_channels,
  481. offsetof(channel_t, sched_heap_idx),
  482. chan);
  483. scheduler_set_channel_state(chan, SCHED_CHAN_WAITING_TO_WRITE);
  484. } else {
  485. /*
  486. * It's not in pending, so it can't become waiting_to_write; it's
  487. * either not in any of the lists (nothing to do) or it's already in
  488. * waiting_for_cells (remove it, can't write any more).
  489. */
  490. if (chan->scheduler_state == SCHED_CHAN_WAITING_FOR_CELLS) {
  491. scheduler_set_channel_state(chan, SCHED_CHAN_IDLE);
  492. }
  493. }
  494. }
  495. /** Mark a channel as having waiting cells. */
  496. MOCK_IMPL(void,
  497. scheduler_channel_has_waiting_cells,(channel_t *chan))
  498. {
  499. IF_BUG_ONCE(!chan) {
  500. return;
  501. }
  502. IF_BUG_ONCE(!channels_pending) {
  503. return;
  504. }
  505. /* First, check if it's also writeable */
  506. if (chan->scheduler_state == SCHED_CHAN_WAITING_FOR_CELLS) {
  507. /*
  508. * It's in channels_waiting_for_cells, so it shouldn't be in any of
  509. * the other lists. It has waiting cells now, so it goes to
  510. * channels_pending.
  511. */
  512. scheduler_set_channel_state(chan, SCHED_CHAN_PENDING);
  513. if (!SCHED_BUG(chan->sched_heap_idx != -1, chan)) {
  514. smartlist_pqueue_add(channels_pending,
  515. scheduler_compare_channels,
  516. offsetof(channel_t, sched_heap_idx),
  517. chan);
  518. }
  519. /* If we made a channel pending, we potentially have scheduling work to
  520. * do. */
  521. the_scheduler->schedule();
  522. } else {
  523. /*
  524. * It's not in waiting_for_cells, so it can't become pending; it's
  525. * either not in any of the lists (we add it to waiting_to_write)
  526. * or it's already in waiting_to_write or pending (we do nothing)
  527. */
  528. if (!(chan->scheduler_state == SCHED_CHAN_WAITING_TO_WRITE ||
  529. chan->scheduler_state == SCHED_CHAN_PENDING)) {
  530. scheduler_set_channel_state(chan, SCHED_CHAN_WAITING_TO_WRITE);
  531. }
  532. }
  533. }
  534. /** Add the scheduler event to the set of pending events with next_run being
  535. * the longest time libevent should wait before triggering the event. */
  536. void
  537. scheduler_ev_add(const struct timeval *next_run)
  538. {
  539. tor_assert(run_sched_ev);
  540. tor_assert(next_run);
  541. if (BUG(event_add(run_sched_ev, next_run) < 0)) {
  542. log_warn(LD_SCHED, "Adding to libevent failed. Next run time was set to: "
  543. "%ld.%06ld", next_run->tv_sec, (long)next_run->tv_usec);
  544. return;
  545. }
  546. }
  547. /** Make the scheduler event active with the given flags. */
  548. void
  549. scheduler_ev_active(int flags)
  550. {
  551. tor_assert(run_sched_ev);
  552. event_active(run_sched_ev, flags, 1);
  553. }
  554. /*
  555. * Initialize everything scheduling-related from config.c. Note this is only
  556. * called when Tor is starting up, while scheduler_t->init() is called both
  557. * when Tor is starting up and when we are switching schedulers.
  558. */
  559. void
  560. scheduler_init(void)
  561. {
  562. log_debug(LD_SCHED, "Initting scheduler");
  563. // Two '!' because we really do want to check if the pointer is non-NULL
  564. IF_BUG_ONCE(!!run_sched_ev) {
  565. log_warn(LD_SCHED, "We should not already have a libevent scheduler event."
  566. "I'll clean the old one up, but this is odd.");
  567. tor_event_free(run_sched_ev);
  568. run_sched_ev = NULL;
  569. }
  570. run_sched_ev = tor_event_new(tor_libevent_get_base(), -1,
  571. 0, scheduler_evt_callback, NULL);
  572. channels_pending = smartlist_new();
  573. set_scheduler();
  574. }
  575. /*
  576. * If a channel is going away, this is how the scheduling system is informed
  577. * so it can do any freeing necessary. This ultimately calls
  578. * scheduler_t->on_channel_free() so the current scheduler can release any
  579. * state specific to this channel.
  580. */
  581. MOCK_IMPL(void,
  582. scheduler_release_channel,(channel_t *chan))
  583. {
  584. IF_BUG_ONCE(!chan) {
  585. return;
  586. }
  587. IF_BUG_ONCE(!channels_pending) {
  588. return;
  589. }
  590. /* Try to remove the channel from the pending list regardless of its
  591. * scheduler state. We can release a channel in many places in the tor code
  592. * so we can't rely on the channel state (PENDING) to remove it from the
  593. * list.
  594. *
  595. * For instance, the channel can change state from OPEN to CLOSING while
  596. * being handled in the scheduler loop leading to the channel being in
  597. * PENDING state but not in the pending list. Furthermore, we release the
  598. * channel when it changes state to close and a second time when we free it.
  599. * Not ideal at all but for now that is the way it is. */
  600. if (chan->sched_heap_idx != -1) {
  601. smartlist_pqueue_remove(channels_pending,
  602. scheduler_compare_channels,
  603. offsetof(channel_t, sched_heap_idx),
  604. chan);
  605. }
  606. if (the_scheduler->on_channel_free) {
  607. the_scheduler->on_channel_free(chan);
  608. }
  609. scheduler_set_channel_state(chan, SCHED_CHAN_IDLE);
  610. }
  611. /** Mark a channel as ready to accept writes */
  612. void
  613. scheduler_channel_wants_writes(channel_t *chan)
  614. {
  615. IF_BUG_ONCE(!chan) {
  616. return;
  617. }
  618. IF_BUG_ONCE(!channels_pending) {
  619. return;
  620. }
  621. /* If it's already in waiting_to_write, we can put it in pending */
  622. if (chan->scheduler_state == SCHED_CHAN_WAITING_TO_WRITE) {
  623. /*
  624. * It can write now, so it goes to channels_pending.
  625. */
  626. scheduler_set_channel_state(chan, SCHED_CHAN_PENDING);
  627. if (!SCHED_BUG(chan->sched_heap_idx != -1, chan)) {
  628. smartlist_pqueue_add(channels_pending,
  629. scheduler_compare_channels,
  630. offsetof(channel_t, sched_heap_idx),
  631. chan);
  632. }
  633. /* We just made a channel pending, we have scheduling work to do. */
  634. the_scheduler->schedule();
  635. } else {
  636. /*
  637. * It's not in SCHED_CHAN_WAITING_TO_WRITE, so it can't become pending;
  638. * it's either idle and goes to WAITING_FOR_CELLS, or it's a no-op.
  639. */
  640. if (!(chan->scheduler_state == SCHED_CHAN_WAITING_FOR_CELLS ||
  641. chan->scheduler_state == SCHED_CHAN_PENDING)) {
  642. scheduler_set_channel_state(chan, SCHED_CHAN_WAITING_FOR_CELLS);
  643. }
  644. }
  645. }
  646. /* Log warn the given channel and extra scheduler context as well. This is
  647. * used by SCHED_BUG() in order to be able to extract as much information as
  648. * we can when we hit a bug. Channel chan can be NULL. */
  649. void
  650. scheduler_bug_occurred(const channel_t *chan)
  651. {
  652. char buf[128];
  653. if (chan != NULL) {
  654. const size_t outbuf_len =
  655. buf_datalen(TO_CONN(BASE_CHAN_TO_TLS((channel_t *) chan)->conn)->outbuf);
  656. tor_snprintf(buf, sizeof(buf),
  657. "Channel %" PRIu64 " in state %s and scheduler state %s."
  658. " Num cells on cmux: %d. Connection outbuf len: %lu.",
  659. chan->global_identifier,
  660. channel_state_to_string(chan->state),
  661. get_scheduler_state_string(chan->scheduler_state),
  662. circuitmux_num_cells(chan->cmux),
  663. (unsigned long)outbuf_len);
  664. }
  665. {
  666. char *msg;
  667. /* Rate limit every 60 seconds. If we start seeing this every 60 sec, we
  668. * know something is stuck/wrong. It *should* be loud but not too much. */
  669. static ratelim_t rlimit = RATELIM_INIT(60);
  670. if ((msg = rate_limit_log(&rlimit, approx_time()))) {
  671. log_warn(LD_BUG, "%s Num pending channels: %d. "
  672. "Channel in pending list: %s.%s",
  673. (chan != NULL) ? buf : "No channel in bug context.",
  674. smartlist_len(channels_pending),
  675. (smartlist_pos(channels_pending, chan) == -1) ? "no" : "yes",
  676. msg);
  677. tor_free(msg);
  678. }
  679. }
  680. }
  681. #ifdef TOR_UNIT_TESTS
  682. /*
  683. * Notify scheduler that a channel's queue position may have changed.
  684. */
  685. void
  686. scheduler_touch_channel(channel_t *chan)
  687. {
  688. IF_BUG_ONCE(!chan) {
  689. return;
  690. }
  691. if (chan->scheduler_state == SCHED_CHAN_PENDING) {
  692. /* Remove and re-add it */
  693. smartlist_pqueue_remove(channels_pending,
  694. scheduler_compare_channels,
  695. offsetof(channel_t, sched_heap_idx),
  696. chan);
  697. smartlist_pqueue_add(channels_pending,
  698. scheduler_compare_channels,
  699. offsetof(channel_t, sched_heap_idx),
  700. chan);
  701. }
  702. /* else no-op, since it isn't in the queue */
  703. }
  704. #endif /* defined(TOR_UNIT_TESTS) */