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