scheduler_kist.c 31 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838
  1. /* Copyright (c) 2017, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. #define SCHEDULER_KIST_PRIVATE
  4. #include <event2/event.h>
  5. #include "or.h"
  6. #include "buffers.h"
  7. #include "config.h"
  8. #include "connection.h"
  9. #include "networkstatus.h"
  10. #define TOR_CHANNEL_INTERNAL_
  11. #include "channel.h"
  12. #include "channeltls.h"
  13. #define SCHEDULER_PRIVATE_
  14. #include "scheduler.h"
  15. #define TLS_PER_CELL_OVERHEAD 29
  16. #ifdef HAVE_KIST_SUPPORT
  17. /* Kernel interface needed for KIST. */
  18. #include <netinet/tcp.h>
  19. #include <linux/sockios.h>
  20. #endif /* HAVE_KIST_SUPPORT */
  21. /*****************************************************************************
  22. * Data structures and supporting functions
  23. *****************************************************************************/
  24. /* Socket_table hash table stuff. The socket_table keeps track of per-socket
  25. * limit information imposed by kist and used by kist. */
  26. static uint32_t
  27. socket_table_ent_hash(const socket_table_ent_t *ent)
  28. {
  29. return (uint32_t)ent->chan->global_identifier;
  30. }
  31. static unsigned
  32. socket_table_ent_eq(const socket_table_ent_t *a, const socket_table_ent_t *b)
  33. {
  34. return a->chan == b->chan;
  35. }
  36. typedef HT_HEAD(socket_table_s, socket_table_ent_s) socket_table_t;
  37. static socket_table_t socket_table = HT_INITIALIZER();
  38. HT_PROTOTYPE(socket_table_s, socket_table_ent_s, node, socket_table_ent_hash,
  39. socket_table_ent_eq)
  40. HT_GENERATE2(socket_table_s, socket_table_ent_s, node, socket_table_ent_hash,
  41. socket_table_ent_eq, 0.6, tor_reallocarray, tor_free_)
  42. /* outbuf_table hash table stuff. The outbuf_table keeps track of which
  43. * channels have data sitting in their outbuf so the kist scheduler can force
  44. * a write from outbuf to kernel periodically during a run and at the end of a
  45. * run. */
  46. typedef struct outbuf_table_ent_s {
  47. HT_ENTRY(outbuf_table_ent_s) node;
  48. channel_t *chan;
  49. } outbuf_table_ent_t;
  50. static uint32_t
  51. outbuf_table_ent_hash(const outbuf_table_ent_t *ent)
  52. {
  53. return (uint32_t)ent->chan->global_identifier;
  54. }
  55. static unsigned
  56. outbuf_table_ent_eq(const outbuf_table_ent_t *a, const outbuf_table_ent_t *b)
  57. {
  58. return a->chan->global_identifier == b->chan->global_identifier;
  59. }
  60. HT_PROTOTYPE(outbuf_table_s, outbuf_table_ent_s, node, outbuf_table_ent_hash,
  61. outbuf_table_ent_eq)
  62. HT_GENERATE2(outbuf_table_s, outbuf_table_ent_s, node, outbuf_table_ent_hash,
  63. outbuf_table_ent_eq, 0.6, tor_reallocarray, tor_free_)
  64. /*****************************************************************************
  65. * Other internal data
  66. *****************************************************************************/
  67. /* Store the last time the scheduler was run so we can decide when to next run
  68. * the scheduler based on it. */
  69. static monotime_t scheduler_last_run;
  70. /* This is a factor for the extra_space calculation in kist per-socket limits.
  71. * It is the number of extra congestion windows we want to write to the kernel.
  72. */
  73. static double sock_buf_size_factor = 1.0;
  74. /* How often the scheduler runs. */
  75. STATIC int sched_run_interval = KIST_SCHED_RUN_INTERVAL_DEFAULT;
  76. #ifdef HAVE_KIST_SUPPORT
  77. /* Indicate if KIST lite mode is on or off. We can disable it at runtime.
  78. * Important to have because of the KISTLite -> KIST possible transition. */
  79. static unsigned int kist_lite_mode = 0;
  80. /* Indicate if we don't have the kernel support. This can happen if the kernel
  81. * changed and it doesn't recognized the values passed to the syscalls needed
  82. * by KIST. In that case, fallback to the naive approach. */
  83. static unsigned int kist_no_kernel_support = 0;
  84. #else /* !(defined(HAVE_KIST_SUPPORT)) */
  85. static unsigned int kist_lite_mode = 1;
  86. #endif /* defined(HAVE_KIST_SUPPORT) */
  87. /*****************************************************************************
  88. * Internally called function implementations
  89. *****************************************************************************/
  90. /* Little helper function to get the length of a channel's output buffer */
  91. static inline size_t
  92. channel_outbuf_length(channel_t *chan)
  93. {
  94. /* In theory, this can not happen because we can not scheduler a channel
  95. * without a connection that has its outbuf initialized. Just in case, bug
  96. * on this so we can understand a bit more why it happened. */
  97. if (SCHED_BUG(BASE_CHAN_TO_TLS(chan)->conn == NULL, chan)) {
  98. return 0;
  99. }
  100. return buf_datalen(TO_CONN(BASE_CHAN_TO_TLS(chan)->conn)->outbuf);
  101. }
  102. /* Little helper function for HT_FOREACH_FN. */
  103. static int
  104. each_channel_write_to_kernel(outbuf_table_ent_t *ent, void *data)
  105. {
  106. (void) data; /* Make compiler happy. */
  107. channel_write_to_kernel(ent->chan);
  108. return 0; /* Returning non-zero removes the element from the table. */
  109. }
  110. /* Free the given outbuf table entry ent. */
  111. static int
  112. free_outbuf_info_by_ent(outbuf_table_ent_t *ent, void *data)
  113. {
  114. (void) data; /* Make compiler happy. */
  115. log_debug(LD_SCHED, "Freeing outbuf table entry from chan=%" PRIu64,
  116. ent->chan->global_identifier);
  117. tor_free(ent);
  118. return 1; /* So HT_FOREACH_FN will remove the element */
  119. }
  120. /* Free the given socket table entry ent. */
  121. static int
  122. free_socket_info_by_ent(socket_table_ent_t *ent, void *data)
  123. {
  124. (void) data; /* Make compiler happy. */
  125. log_debug(LD_SCHED, "Freeing socket table entry from chan=%" PRIu64,
  126. ent->chan->global_identifier);
  127. tor_free(ent);
  128. return 1; /* So HT_FOREACH_FN will remove the element */
  129. }
  130. /* Clean up socket_table. Probably because the KIST sched impl is going away */
  131. static void
  132. free_all_socket_info(void)
  133. {
  134. HT_FOREACH_FN(socket_table_s, &socket_table, free_socket_info_by_ent, NULL);
  135. HT_CLEAR(socket_table_s, &socket_table);
  136. }
  137. static socket_table_ent_t *
  138. socket_table_search(socket_table_t *table, const channel_t *chan)
  139. {
  140. socket_table_ent_t search, *ent = NULL;
  141. search.chan = chan;
  142. ent = HT_FIND(socket_table_s, table, &search);
  143. return ent;
  144. }
  145. /* Free a socket entry in table for the given chan. */
  146. static void
  147. free_socket_info_by_chan(socket_table_t *table, const channel_t *chan)
  148. {
  149. socket_table_ent_t *ent = NULL;
  150. ent = socket_table_search(table, chan);
  151. if (!ent)
  152. return;
  153. log_debug(LD_SCHED, "scheduler free socket info for chan=%" PRIu64,
  154. chan->global_identifier);
  155. HT_REMOVE(socket_table_s, table, ent);
  156. free_socket_info_by_ent(ent, NULL);
  157. }
  158. /* Perform system calls for the given socket in order to calculate kist's
  159. * per-socket limit as documented in the function body. */
  160. MOCK_IMPL(void,
  161. update_socket_info_impl, (socket_table_ent_t *ent))
  162. {
  163. #ifdef HAVE_KIST_SUPPORT
  164. int64_t tcp_space, extra_space;
  165. const tor_socket_t sock =
  166. TO_CONN(BASE_CHAN_TO_TLS((channel_t *) ent->chan)->conn)->s;
  167. struct tcp_info tcp;
  168. socklen_t tcp_info_len = sizeof(tcp);
  169. if (kist_no_kernel_support || kist_lite_mode) {
  170. goto fallback;
  171. }
  172. /* Gather information */
  173. if (getsockopt(sock, SOL_TCP, TCP_INFO, (void *)&(tcp), &tcp_info_len) < 0) {
  174. if (errno == EINVAL) {
  175. /* Oops, this option is not provided by the kernel, we'll have to
  176. * disable KIST entirely. This can happen if tor was built on a machine
  177. * with the support previously or if the kernel was updated and lost the
  178. * support. */
  179. log_notice(LD_SCHED, "Looks like our kernel doesn't have the support "
  180. "for KIST anymore. We will fallback to the naive "
  181. "approach. Remove KIST from the Schedulers list "
  182. "to disable.");
  183. kist_no_kernel_support = 1;
  184. }
  185. goto fallback;
  186. }
  187. if (ioctl(sock, SIOCOUTQNSD, &(ent->notsent)) < 0) {
  188. if (errno == EINVAL) {
  189. log_notice(LD_SCHED, "Looks like our kernel doesn't have the support "
  190. "for KIST anymore. We will fallback to the naive "
  191. "approach. Remove KIST from the Schedulers list "
  192. "to disable.");
  193. /* Same reason as the above. */
  194. kist_no_kernel_support = 1;
  195. }
  196. goto fallback;
  197. }
  198. ent->cwnd = tcp.tcpi_snd_cwnd;
  199. ent->unacked = tcp.tcpi_unacked;
  200. ent->mss = tcp.tcpi_snd_mss;
  201. /* In order to reduce outbound kernel queuing delays and thus improve Tor's
  202. * ability to prioritize circuits, KIST wants to set a socket write limit
  203. * that is near the amount that the socket would be able to immediately send
  204. * into the Internet.
  205. *
  206. * We first calculate how much the socket could send immediately (assuming
  207. * completely full packets) according to the congestion window and the number
  208. * of unacked packets.
  209. *
  210. * Then we add a little extra space in a controlled way. We do this so any
  211. * when the kernel gets ACKs back for data currently sitting in the "TCP
  212. * space", it will already have some more data to send immediately. It will
  213. * not have to wait for the scheduler to run again. The amount of extra space
  214. * is a factor of the current congestion window. With the suggested
  215. * sock_buf_size_factor value of 1.0, we allow at most 2*cwnd bytes to sit in
  216. * the kernel: 1 cwnd on the wire waiting for ACKs and 1 cwnd ready and
  217. * waiting to be sent when those ACKs finally come.
  218. *
  219. * In the below diagram, we see some bytes in the TCP-space (denoted by '*')
  220. * that have be sent onto the wire and are waiting for ACKs. We have a little
  221. * more room in "TCP space" that we can fill with data that will be
  222. * immediately sent. We also see the "extra space" KIST calculates. The sum
  223. * of the empty "TCP space" and the "extra space" is the kist-imposed write
  224. * limit for this socket.
  225. *
  226. * <----------------kernel-outbound-socket-queue----------------|
  227. * <*********---------------------------------------------------|
  228. * |----TCP-space-----|----extra-space-----|
  229. * |------------------|
  230. * ^ ((cwnd - unacked) * mss) bytes
  231. * |--------------------|
  232. * ^ ((cwnd * mss) * factor) bytes
  233. */
  234. /* These values from the kernel are uint32_t, they will always fit into a
  235. * int64_t tcp_space variable but if the congestion window cwnd is smaller
  236. * than the unacked packets, the remaining TCP space is set to 0. */
  237. if (ent->cwnd >= ent->unacked) {
  238. tcp_space = (ent->cwnd - ent->unacked) * (int64_t)(ent->mss);
  239. } else {
  240. tcp_space = 0;
  241. }
  242. /* The clamp_double_to_int64 makes sure the first part fits into an int64_t.
  243. * In fact, if sock_buf_size_factor is still forced to be >= 0 in config.c,
  244. * then it will be positive for sure. Then we subtract a uint32_t. Getting a
  245. * negative value is OK, see after how it is being handled. */
  246. extra_space =
  247. clamp_double_to_int64(
  248. (ent->cwnd * (int64_t)ent->mss) * sock_buf_size_factor) -
  249. ent->notsent;
  250. if ((tcp_space + extra_space) < 0) {
  251. /* This means that the "notsent" queue is just too big so we shouldn't put
  252. * more in the kernel for now. */
  253. ent->limit = 0;
  254. } else {
  255. /* The positive sum of two int64_t will always fit into an uint64_t.
  256. * And we know this will always be positive, since we checked above. */
  257. ent->limit = (uint64_t)tcp_space + (uint64_t)extra_space;
  258. }
  259. return;
  260. #else /* !(defined(HAVE_KIST_SUPPORT)) */
  261. goto fallback;
  262. #endif /* defined(HAVE_KIST_SUPPORT) */
  263. fallback:
  264. /* If all of a sudden we don't have kist support, we just zero out all the
  265. * variables for this socket since we don't know what they should be. We
  266. * also allow the socket to write as much as it can from the estimated
  267. * number of cells the lower layer can accept, effectively returning it to
  268. * Vanilla scheduler behavior. */
  269. ent->cwnd = ent->unacked = ent->mss = ent->notsent = 0;
  270. /* This function calls the specialized channel object (currently channeltls)
  271. * and ask how many cells it can write on the outbuf which we then multiply
  272. * by the size of the cells for this channel. The cast is because this
  273. * function requires a non-const channel object, meh. */
  274. ent->limit = channel_num_cells_writeable((channel_t *) ent->chan) *
  275. (get_cell_network_size(ent->chan->wide_circ_ids) +
  276. TLS_PER_CELL_OVERHEAD);
  277. }
  278. /* Given a socket that isn't in the table, add it.
  279. * Given a socket that is in the table, re-init values that need init-ing
  280. * every scheduling run
  281. */
  282. static void
  283. init_socket_info(socket_table_t *table, const channel_t *chan)
  284. {
  285. socket_table_ent_t *ent = NULL;
  286. ent = socket_table_search(table, chan);
  287. if (!ent) {
  288. log_debug(LD_SCHED, "scheduler init socket info for chan=%" PRIu64,
  289. chan->global_identifier);
  290. ent = tor_malloc_zero(sizeof(*ent));
  291. ent->chan = chan;
  292. HT_INSERT(socket_table_s, table, ent);
  293. }
  294. ent->written = 0;
  295. }
  296. /* Add chan to the outbuf table if it isn't already in it. If it is, then don't
  297. * do anything */
  298. static void
  299. outbuf_table_add(outbuf_table_t *table, channel_t *chan)
  300. {
  301. outbuf_table_ent_t search, *ent;
  302. search.chan = chan;
  303. ent = HT_FIND(outbuf_table_s, table, &search);
  304. if (!ent) {
  305. log_debug(LD_SCHED, "scheduler init outbuf info for chan=%" PRIu64,
  306. chan->global_identifier);
  307. ent = tor_malloc_zero(sizeof(*ent));
  308. ent->chan = chan;
  309. HT_INSERT(outbuf_table_s, table, ent);
  310. }
  311. }
  312. static void
  313. outbuf_table_remove(outbuf_table_t *table, channel_t *chan)
  314. {
  315. outbuf_table_ent_t search, *ent;
  316. search.chan = chan;
  317. ent = HT_FIND(outbuf_table_s, table, &search);
  318. if (ent) {
  319. HT_REMOVE(outbuf_table_s, table, ent);
  320. free_outbuf_info_by_ent(ent, NULL);
  321. }
  322. }
  323. /* Set the scheduler running interval. */
  324. static void
  325. set_scheduler_run_interval(void)
  326. {
  327. int old_sched_run_interval = sched_run_interval;
  328. sched_run_interval = kist_scheduler_run_interval();
  329. if (old_sched_run_interval != sched_run_interval) {
  330. log_info(LD_SCHED, "Scheduler KIST changing its running interval "
  331. "from %" PRId32 " to %" PRId32,
  332. old_sched_run_interval, sched_run_interval);
  333. }
  334. }
  335. /* Return true iff the channel hasn’t hit its kist-imposed write limit yet */
  336. static int
  337. socket_can_write(socket_table_t *table, const channel_t *chan)
  338. {
  339. socket_table_ent_t *ent = NULL;
  340. ent = socket_table_search(table, chan);
  341. if (SCHED_BUG(!ent, chan)) {
  342. return 1; // Just return true, saying that kist wouldn't limit the socket
  343. }
  344. /* We previously calculated a write limit for this socket. In the below
  345. * calculation, first determine how much room is left in bytes. Then divide
  346. * that by the amount of space a cell takes. If there's room for at least 1
  347. * cell, then KIST will allow the socket to write. */
  348. int64_t kist_limit_space =
  349. (int64_t) (ent->limit - ent->written) /
  350. (CELL_MAX_NETWORK_SIZE + TLS_PER_CELL_OVERHEAD);
  351. return kist_limit_space > 0;
  352. }
  353. /* Update the channel's socket kernel information. */
  354. static void
  355. update_socket_info(socket_table_t *table, const channel_t *chan)
  356. {
  357. socket_table_ent_t *ent = NULL;
  358. ent = socket_table_search(table, chan);
  359. if (SCHED_BUG(!ent, chan)) {
  360. return; // Whelp. Entry didn't exist for some reason so nothing to do.
  361. }
  362. update_socket_info_impl(ent);
  363. log_debug(LD_SCHED, "chan=%" PRIu64 " updated socket info, limit: %" PRIu64
  364. ", cwnd: %" PRIu32 ", unacked: %" PRIu32
  365. ", notsent: %" PRIu32 ", mss: %" PRIu32,
  366. ent->chan->global_identifier, ent->limit, ent->cwnd, ent->unacked,
  367. ent->notsent, ent->mss);
  368. }
  369. /* Increment the channel's socket written value by the number of bytes. */
  370. static void
  371. update_socket_written(socket_table_t *table, channel_t *chan, size_t bytes)
  372. {
  373. socket_table_ent_t *ent = NULL;
  374. ent = socket_table_search(table, chan);
  375. if (SCHED_BUG(!ent, chan)) {
  376. return; // Whelp. Entry didn't exist so nothing to do.
  377. }
  378. log_debug(LD_SCHED, "chan=%" PRIu64 " wrote %lu bytes, old was %" PRIi64,
  379. chan->global_identifier, (unsigned long) bytes, ent->written);
  380. ent->written += bytes;
  381. }
  382. /*
  383. * A naive KIST impl would write every single cell all the way to the kernel.
  384. * That would take a lot of system calls. A less bad KIST impl would write a
  385. * channel's outbuf to the kernel only when we are switching to a different
  386. * channel. But if we have two channels with equal priority, we end up writing
  387. * one cell for each and bouncing back and forth. This KIST impl avoids that
  388. * by only writing a channel's outbuf to the kernel if it has 8 cells or more
  389. * in it.
  390. */
  391. MOCK_IMPL(int, channel_should_write_to_kernel,
  392. (outbuf_table_t *table, channel_t *chan))
  393. {
  394. outbuf_table_add(table, chan);
  395. /* CELL_MAX_NETWORK_SIZE * 8 because we only want to write the outbuf to the
  396. * kernel if there's 8 or more cells waiting */
  397. return channel_outbuf_length(chan) > (CELL_MAX_NETWORK_SIZE * 8);
  398. }
  399. /* Little helper function to write a channel's outbuf all the way to the
  400. * kernel */
  401. MOCK_IMPL(void, channel_write_to_kernel, (channel_t *chan))
  402. {
  403. log_debug(LD_SCHED, "Writing %lu bytes to kernel for chan %" PRIu64,
  404. (unsigned long)channel_outbuf_length(chan),
  405. chan->global_identifier);
  406. connection_handle_write(TO_CONN(BASE_CHAN_TO_TLS(chan)->conn), 0);
  407. }
  408. /* Return true iff the scheduler has work to perform. */
  409. static int
  410. have_work(void)
  411. {
  412. smartlist_t *cp = get_channels_pending();
  413. IF_BUG_ONCE(!cp) {
  414. return 0; // channels_pending doesn't exist so... no work?
  415. }
  416. return smartlist_len(cp) > 0;
  417. }
  418. /* Function of the scheduler interface: free_all() */
  419. static void
  420. kist_free_all(void)
  421. {
  422. free_all_socket_info();
  423. }
  424. /* Function of the scheduler interface: on_channel_free() */
  425. static void
  426. kist_on_channel_free_fn(const channel_t *chan)
  427. {
  428. free_socket_info_by_chan(&socket_table, chan);
  429. }
  430. /* Function of the scheduler interface: on_new_consensus() */
  431. static void
  432. kist_scheduler_on_new_consensus(void)
  433. {
  434. set_scheduler_run_interval();
  435. }
  436. /* Function of the scheduler interface: on_new_options() */
  437. static void
  438. kist_scheduler_on_new_options(void)
  439. {
  440. sock_buf_size_factor = get_options()->KISTSockBufSizeFactor;
  441. /* Calls kist_scheduler_run_interval which calls get_options(). */
  442. set_scheduler_run_interval();
  443. }
  444. /* Function of the scheduler interface: init() */
  445. static void
  446. kist_scheduler_init(void)
  447. {
  448. /* When initializing the scheduler, the last run could be 0 because it is
  449. * declared static or a value in the past that was set when it was last
  450. * used. In both cases, we want to initialize it to now so we don't risk
  451. * using the value 0 which doesn't play well with our monotonic time
  452. * interface.
  453. *
  454. * One side effect is that the first scheduler run will be at the next tick
  455. * that is in now + 10 msec (KIST_SCHED_RUN_INTERVAL_DEFAULT) by default. */
  456. monotime_get(&scheduler_last_run);
  457. kist_scheduler_on_new_options();
  458. IF_BUG_ONCE(sched_run_interval == 0) {
  459. log_warn(LD_SCHED, "We are initing the KIST scheduler and noticed the "
  460. "KISTSchedRunInterval is telling us to not use KIST. That's "
  461. "weird! We'll continue using KIST, but at %" PRId32 "ms.",
  462. KIST_SCHED_RUN_INTERVAL_DEFAULT);
  463. sched_run_interval = KIST_SCHED_RUN_INTERVAL_DEFAULT;
  464. }
  465. }
  466. /* Function of the scheduler interface: schedule() */
  467. static void
  468. kist_scheduler_schedule(void)
  469. {
  470. struct monotime_t now;
  471. struct timeval next_run;
  472. int64_t diff;
  473. if (!have_work()) {
  474. return;
  475. }
  476. monotime_get(&now);
  477. /* If time is really monotonic, we can never have now being smaller than the
  478. * last scheduler run. The scheduler_last_run at first is set to 0.
  479. * Unfortunately, not all platforms guarantee monotonic time so we log at
  480. * info level but don't make it more noisy. */
  481. diff = monotime_diff_msec(&scheduler_last_run, &now);
  482. if (diff < 0) {
  483. log_info(LD_SCHED, "Monotonic time between now and last run of scheduler "
  484. "is negative: %" PRId64 ". Setting diff to 0.", diff);
  485. diff = 0;
  486. }
  487. if (diff < sched_run_interval) {
  488. next_run.tv_sec = 0;
  489. /* Takes 1000 ms -> us. This will always be valid because diff can NOT be
  490. * negative and can NOT be bigger than sched_run_interval so values can
  491. * only go from 1000 usec (diff set to interval - 1) to 100000 usec (diff
  492. * set to 0) for the maximum allowed run interval (100ms). */
  493. next_run.tv_usec = (int) ((sched_run_interval - diff) * 1000);
  494. /* Re-adding an event reschedules it. It does not duplicate it. */
  495. scheduler_ev_add(&next_run);
  496. } else {
  497. scheduler_ev_active(EV_TIMEOUT);
  498. }
  499. }
  500. /* Function of the scheduler interface: run() */
  501. static void
  502. kist_scheduler_run(void)
  503. {
  504. /* Define variables */
  505. channel_t *chan = NULL; // current working channel
  506. /* The last distinct chan served in a sched loop. */
  507. channel_t *prev_chan = NULL;
  508. int flush_result; // temporarily store results from flush calls
  509. /* Channels to be re-adding to pending at the end */
  510. smartlist_t *to_readd = NULL;
  511. smartlist_t *cp = get_channels_pending();
  512. outbuf_table_t outbuf_table = HT_INITIALIZER();
  513. /* For each pending channel, collect new kernel information */
  514. SMARTLIST_FOREACH_BEGIN(cp, const channel_t *, pchan) {
  515. init_socket_info(&socket_table, pchan);
  516. update_socket_info(&socket_table, pchan);
  517. } SMARTLIST_FOREACH_END(pchan);
  518. log_debug(LD_SCHED, "Running the scheduler. %d channels pending",
  519. smartlist_len(cp));
  520. /* The main scheduling loop. Loop until there are no more pending channels */
  521. while (smartlist_len(cp) > 0) {
  522. /* get best channel */
  523. chan = smartlist_pqueue_pop(cp, scheduler_compare_channels,
  524. offsetof(channel_t, sched_heap_idx));
  525. if (SCHED_BUG(!chan, NULL)) {
  526. /* Some-freaking-how a NULL got into the channels_pending. That should
  527. * never happen, but it should be harmless to ignore it and keep looping.
  528. */
  529. continue;
  530. }
  531. outbuf_table_add(&outbuf_table, chan);
  532. /* if we have switched to a new channel, consider writing the previous
  533. * channel's outbuf to the kernel. */
  534. if (!prev_chan) {
  535. prev_chan = chan;
  536. }
  537. if (prev_chan != chan) {
  538. if (channel_should_write_to_kernel(&outbuf_table, prev_chan)) {
  539. channel_write_to_kernel(prev_chan);
  540. outbuf_table_remove(&outbuf_table, prev_chan);
  541. }
  542. prev_chan = chan;
  543. }
  544. /* Only flush and write if the per-socket limit hasn't been hit */
  545. if (socket_can_write(&socket_table, chan)) {
  546. /* flush to channel queue/outbuf */
  547. flush_result = (int)channel_flush_some_cells(chan, 1); // 1 for num cells
  548. /* XXX: While flushing cells, it is possible that the connection write
  549. * fails leading to the channel to be closed which triggers a release
  550. * and free its entry in the socket table. And because of a engineering
  551. * design issue, the error is not propagated back so we don't get an
  552. * error at this point. So before we continue, make sure the channel is
  553. * open and if not just ignore it. See #23751. */
  554. if (!CHANNEL_IS_OPEN(chan)) {
  555. /* Channel isn't open so we put it back in IDLE mode. It is either
  556. * renegotiating its TLS session or about to be released. */
  557. scheduler_set_channel_state(chan, SCHED_CHAN_IDLE);
  558. continue;
  559. }
  560. /* flush_result has the # cells flushed */
  561. if (flush_result > 0) {
  562. update_socket_written(&socket_table, chan, flush_result *
  563. (CELL_MAX_NETWORK_SIZE + TLS_PER_CELL_OVERHEAD));
  564. } else {
  565. /* XXX: This can happen because tor sometimes does flush in an
  566. * opportunistic way cells from the circuit to the outbuf so the
  567. * channel can end up here without having anything to flush nor needed
  568. * to write to the kernel. Hopefully we'll fix that soon but for now
  569. * we have to handle this case which happens kind of often. */
  570. log_debug(LD_SCHED,
  571. "We didn't flush anything on a chan that we think "
  572. "can write and wants to write. The channel's state is '%s' "
  573. "and in scheduler state '%s'. We're going to mark it as "
  574. "waiting_for_cells (as that's most likely the issue) and "
  575. "stop scheduling it this round.",
  576. channel_state_to_string(chan->state),
  577. get_scheduler_state_string(chan->scheduler_state));
  578. scheduler_set_channel_state(chan, SCHED_CHAN_WAITING_FOR_CELLS);
  579. continue;
  580. }
  581. }
  582. /* Decide what to do with the channel now */
  583. if (!channel_more_to_flush(chan) &&
  584. !socket_can_write(&socket_table, chan)) {
  585. /* Case 1: no more cells to send, and cannot write */
  586. /*
  587. * You might think we should put the channel in SCHED_CHAN_IDLE. And
  588. * you're probably correct. While implementing KIST, we found that the
  589. * scheduling system would sometimes lose track of channels when we did
  590. * that. We suspect it has to do with the difference between "can't
  591. * write because socket/outbuf is full" and KIST's "can't write because
  592. * we've arbitrarily decided that that's enough for now." Sometimes
  593. * channels run out of cells at the same time they hit their
  594. * kist-imposed write limit and maybe the rest of Tor doesn't put the
  595. * channel back in pending when it is supposed to.
  596. *
  597. * This should be investigated again. It is as simple as changing
  598. * SCHED_CHAN_WAITING_FOR_CELLS to SCHED_CHAN_IDLE and seeing if Tor
  599. * starts having serious throughput issues. Best done in shadow/chutney.
  600. */
  601. scheduler_set_channel_state(chan, SCHED_CHAN_WAITING_FOR_CELLS);
  602. } else if (!channel_more_to_flush(chan)) {
  603. /* Case 2: no more cells to send, but still open for writes */
  604. scheduler_set_channel_state(chan, SCHED_CHAN_WAITING_FOR_CELLS);
  605. } else if (!socket_can_write(&socket_table, chan)) {
  606. /* Case 3: cells to send, but cannot write */
  607. /*
  608. * We want to write, but can't. If we left the channel in
  609. * channels_pending, we would never exit the scheduling loop. We need to
  610. * add it to a temporary list of channels to be added to channels_pending
  611. * after the scheduling loop is over. They can hopefully be taken care of
  612. * in the next scheduling round.
  613. */
  614. if (!to_readd) {
  615. to_readd = smartlist_new();
  616. }
  617. smartlist_add(to_readd, chan);
  618. } else {
  619. /* Case 4: cells to send, and still open for writes */
  620. scheduler_set_channel_state(chan, SCHED_CHAN_PENDING);
  621. if (!SCHED_BUG(chan->sched_heap_idx != -1, chan)) {
  622. smartlist_pqueue_add(cp, scheduler_compare_channels,
  623. offsetof(channel_t, sched_heap_idx), chan);
  624. }
  625. }
  626. } /* End of main scheduling loop */
  627. /* Write the outbuf of any channels that still have data */
  628. HT_FOREACH_FN(outbuf_table_s, &outbuf_table, each_channel_write_to_kernel,
  629. NULL);
  630. /* We are done with it. */
  631. HT_FOREACH_FN(outbuf_table_s, &outbuf_table, free_outbuf_info_by_ent, NULL);
  632. HT_CLEAR(outbuf_table_s, &outbuf_table);
  633. log_debug(LD_SCHED, "len pending=%d, len to_readd=%d",
  634. smartlist_len(cp),
  635. (to_readd ? smartlist_len(to_readd) : -1));
  636. /* Re-add any channels we need to */
  637. if (to_readd) {
  638. SMARTLIST_FOREACH_BEGIN(to_readd, channel_t *, readd_chan) {
  639. scheduler_set_channel_state(readd_chan, SCHED_CHAN_PENDING);
  640. if (!smartlist_contains(cp, readd_chan)) {
  641. if (!SCHED_BUG(chan->sched_heap_idx != -1, chan)) {
  642. /* XXXX Note that the check above is in theory redundant with
  643. * the smartlist_contains check. But let's make sure we're
  644. * not messing anything up, and leave them both for now. */
  645. smartlist_pqueue_add(cp, scheduler_compare_channels,
  646. offsetof(channel_t, sched_heap_idx), readd_chan);
  647. }
  648. }
  649. } SMARTLIST_FOREACH_END(readd_chan);
  650. smartlist_free(to_readd);
  651. }
  652. monotime_get(&scheduler_last_run);
  653. }
  654. /*****************************************************************************
  655. * Externally called function implementations not called through scheduler_t
  656. *****************************************************************************/
  657. /* Stores the kist scheduler function pointers. */
  658. static scheduler_t kist_scheduler = {
  659. .type = SCHEDULER_KIST,
  660. .free_all = kist_free_all,
  661. .on_channel_free = kist_on_channel_free_fn,
  662. .init = kist_scheduler_init,
  663. .on_new_consensus = kist_scheduler_on_new_consensus,
  664. .schedule = kist_scheduler_schedule,
  665. .run = kist_scheduler_run,
  666. .on_new_options = kist_scheduler_on_new_options,
  667. };
  668. /* Return the KIST scheduler object. If it didn't exists, return a newly
  669. * allocated one but init() is not called. */
  670. scheduler_t *
  671. get_kist_scheduler(void)
  672. {
  673. return &kist_scheduler;
  674. }
  675. /* Check the torrc (and maybe consensus) for the configured KIST scheduler run
  676. * interval.
  677. * - If torrc > 0, then return the positive torrc value (should use KIST, and
  678. * should use the set value)
  679. * - If torrc == 0, then look in the consensus for what the value should be.
  680. * - If == 0, then return 0 (don't use KIST)
  681. * - If > 0, then return the positive consensus value
  682. * - If consensus doesn't say anything, return 10 milliseconds, default.
  683. */
  684. int
  685. kist_scheduler_run_interval(void)
  686. {
  687. int run_interval = get_options()->KISTSchedRunInterval;
  688. if (run_interval != 0) {
  689. log_debug(LD_SCHED, "Found KISTSchedRunInterval=%" PRId32 " in torrc. "
  690. "Using that.", run_interval);
  691. return run_interval;
  692. }
  693. log_debug(LD_SCHED, "KISTSchedRunInterval=0, turning to the consensus.");
  694. /* Will either be the consensus value or the default. Note that 0 can be
  695. * returned which means the consensus wants us to NOT use KIST. */
  696. return networkstatus_get_param(NULL, "KISTSchedRunInterval",
  697. KIST_SCHED_RUN_INTERVAL_DEFAULT,
  698. KIST_SCHED_RUN_INTERVAL_MIN,
  699. KIST_SCHED_RUN_INTERVAL_MAX);
  700. }
  701. /* Set KISTLite mode that is KIST without kernel support. */
  702. void
  703. scheduler_kist_set_lite_mode(void)
  704. {
  705. kist_lite_mode = 1;
  706. kist_scheduler.type = SCHEDULER_KIST_LITE;
  707. log_info(LD_SCHED,
  708. "Setting KIST scheduler without kernel support (KISTLite mode)");
  709. }
  710. /* Set KIST mode that is KIST with kernel support. */
  711. void
  712. scheduler_kist_set_full_mode(void)
  713. {
  714. kist_lite_mode = 0;
  715. kist_scheduler.type = SCHEDULER_KIST;
  716. log_info(LD_SCHED,
  717. "Setting KIST scheduler with kernel support (KIST mode)");
  718. }
  719. #ifdef HAVE_KIST_SUPPORT
  720. /* Return true iff the scheduler subsystem should use KIST. */
  721. int
  722. scheduler_can_use_kist(void)
  723. {
  724. if (kist_no_kernel_support) {
  725. /* We have no kernel support so we can't use KIST. */
  726. return 0;
  727. }
  728. /* We do have the support, time to check if we can get the interval that the
  729. * consensus can be disabling. */
  730. int run_interval = kist_scheduler_run_interval();
  731. log_debug(LD_SCHED, "Determined KIST sched_run_interval should be "
  732. "%" PRId32 ". Can%s use KIST.",
  733. run_interval, (run_interval > 0 ? "" : " not"));
  734. return run_interval > 0;
  735. }
  736. #else /* !(defined(HAVE_KIST_SUPPORT)) */
  737. int
  738. scheduler_can_use_kist(void)
  739. {
  740. return 0;
  741. }
  742. #endif /* defined(HAVE_KIST_SUPPORT) */