1 /* Copyright (c) 2017-2019, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
4 #define SCHEDULER_KIST_PRIVATE
6 #include "core/or/or.h"
7 #include "lib/buf/buffers.h"
8 #include "app/config/config.h"
9 #include "core/mainloop/connection.h"
10 #include "feature/nodelist/networkstatus.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"
18 #include "core/or/or_connection_st.h"
20 #ifdef HAVE_SYS_IOCTL_H
21 #include <sys/ioctl.h>
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 */
30 /*****************************************************************************
31 * Data structures and supporting functions
32 *****************************************************************************/
34 /* Socket_table hash table stuff. The socket_table keeps track of per-socket
35 * limit information imposed by kist and used by kist. */
38 socket_table_ent_hash(const socket_table_ent_t
*ent
)
40 return (uint32_t)ent
->chan
->global_identifier
;
44 socket_table_ent_eq(const socket_table_ent_t
*a
, const socket_table_ent_t
*b
)
46 return a
->chan
== b
->chan
;
49 typedef HT_HEAD(socket_table_s
, socket_table_ent_s
) socket_table_t
;
51 static socket_table_t socket_table
= HT_INITIALIZER();
53 HT_PROTOTYPE(socket_table_s
, socket_table_ent_s
, node
, socket_table_ent_hash
,
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_
)
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
63 typedef struct outbuf_table_ent_s
{
64 HT_ENTRY(outbuf_table_ent_s
) node
;
69 outbuf_table_ent_hash(const outbuf_table_ent_t
*ent
)
71 return (uint32_t)ent
->chan
->global_identifier
;
75 outbuf_table_ent_eq(const outbuf_table_ent_t
*a
, const outbuf_table_ent_t
*b
)
77 return a
->chan
->global_identifier
== b
->chan
->global_identifier
;
80 HT_PROTOTYPE(outbuf_table_s
, outbuf_table_ent_s
, node
, outbuf_table_ent_hash
,
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_
)
85 /*****************************************************************************
87 *****************************************************************************/
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.
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
;
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) */
111 /*****************************************************************************
112 * Internally called function implementations
113 *****************************************************************************/
115 /* Little helper function to get the length of a channel's output buffer */
117 channel_outbuf_length(channel_t
*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
)) {
126 return buf_datalen(TO_CONN(BASE_CHAN_TO_TLS(chan
)->conn
)->outbuf
);
129 /* Little helper function for HT_FOREACH_FN. */
131 each_channel_write_to_kernel(outbuf_table_ent_t
*ent
, void *data
)
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. */
138 /* Free the given outbuf table entry ent. */
140 free_outbuf_info_by_ent(outbuf_table_ent_t
*ent
, void *data
)
142 (void) data
; /* Make compiler happy. */
143 log_debug(LD_SCHED
, "Freeing outbuf table entry from chan=%" PRIu64
,
144 ent
->chan
->global_identifier
);
146 return 1; /* So HT_FOREACH_FN will remove the element */
149 /* Free the given socket table entry ent. */
151 free_socket_info_by_ent(socket_table_ent_t
*ent
, void *data
)
153 (void) data
; /* Make compiler happy. */
154 log_debug(LD_SCHED
, "Freeing socket table entry from chan=%" PRIu64
,
155 ent
->chan
->global_identifier
);
157 return 1; /* So HT_FOREACH_FN will remove the element */
160 /* Clean up socket_table. Probably because the KIST sched impl is going away */
162 free_all_socket_info(void)
164 HT_FOREACH_FN(socket_table_s
, &socket_table
, free_socket_info_by_ent
, NULL
);
165 HT_CLEAR(socket_table_s
, &socket_table
);
168 static socket_table_ent_t
*
169 socket_table_search(socket_table_t
*table
, const channel_t
*chan
)
171 socket_table_ent_t search
, *ent
= NULL
;
173 ent
= HT_FIND(socket_table_s
, table
, &search
);
177 /* Free a socket entry in table for the given chan. */
179 free_socket_info_by_chan(socket_table_t
*table
, const channel_t
*chan
)
181 socket_table_ent_t
*ent
= NULL
;
182 ent
= socket_table_search(table
, chan
);
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
);
191 /* Perform system calls for the given socket in order to calculate kist's
192 * per-socket limit as documented in the function body. */
194 update_socket_info_impl
, (socket_table_ent_t
*ent
))
196 #ifdef HAVE_KIST_SUPPORT
197 int64_t tcp_space
, extra_space
;
199 tor_assert(ent
->chan
);
200 const tor_socket_t sock
=
201 TO_CONN(BASE_CHAN_TO_TLS((channel_t
*) ent
->chan
)->conn
)->s
;
203 socklen_t tcp_info_len
= sizeof(tcp
);
205 if (kist_no_kernel_support
|| kist_lite_mode
) {
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
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 "
220 kist_no_kernel_support
= 1;
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 "
230 /* Same reason as the above. */
231 kist_no_kernel_support
= 1;
235 ent
->cwnd
= tcp
.tcpi_snd_cwnd
;
236 ent
->unacked
= tcp
.tcpi_unacked
;
237 ent
->mss
= tcp
.tcpi_snd_mss
;
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
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.
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.
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.
264 * <----------------kernel-outbound-socket-queue----------------|
265 * <*********---------------------------------------------------|
266 * |----TCP-space-----|----extra-space-----|
267 * |------------------|
268 * ^ ((cwnd - unacked) * mss) bytes
269 * |--------------------|
270 * ^ ((cwnd * mss) * factor) bytes
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
);
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. */
287 clamp_double_to_int64(
288 (ent
->cwnd
* (int64_t)ent
->mss
) * sock_buf_size_factor
) -
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. */
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
;
301 #else /* !(defined(HAVE_KIST_SUPPORT)) */
303 #endif /* defined(HAVE_KIST_SUPPORT) */
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
);
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
326 init_socket_info(socket_table_t
*table
, const channel_t
*chan
)
328 socket_table_ent_t
*ent
= NULL
;
329 ent
= socket_table_search(table
, chan
);
331 log_debug(LD_SCHED
, "scheduler init socket info for chan=%" PRIu64
,
332 chan
->global_identifier
);
333 ent
= tor_malloc_zero(sizeof(*ent
));
335 HT_INSERT(socket_table_s
, table
, ent
);
340 /* Add chan to the outbuf table if it isn't already in it. If it is, then don't
343 outbuf_table_add(outbuf_table_t
*table
, channel_t
*chan
)
345 outbuf_table_ent_t search
, *ent
;
347 ent
= HT_FIND(outbuf_table_s
, table
, &search
);
349 log_debug(LD_SCHED
, "scheduler init outbuf info for chan=%" PRIu64
,
350 chan
->global_identifier
);
351 ent
= tor_malloc_zero(sizeof(*ent
));
353 HT_INSERT(outbuf_table_s
, table
, ent
);
358 outbuf_table_remove(outbuf_table_t
*table
, channel_t
*chan
)
360 outbuf_table_ent_t search
, *ent
;
362 ent
= HT_FIND(outbuf_table_s
, table
, &search
);
364 HT_REMOVE(outbuf_table_s
, table
, ent
);
365 free_outbuf_info_by_ent(ent
, NULL
);
369 /* Set the scheduler running interval. */
371 set_scheduler_run_interval(void)
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
);
382 /* Return true iff the channel hasn't hit its kist-imposed write limit yet */
384 socket_can_write(socket_table_t
*table
, const channel_t
*chan
)
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
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;
402 /* Update the channel's socket kernel information. */
404 update_socket_info(socket_table_t
*table
, const channel_t
*chan
)
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.
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
);
419 /* Increment the channel's socket written value by the number of bytes. */
421 update_socket_written(socket_table_t
*table
, channel_t
*chan
, size_t bytes
)
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.
429 log_debug(LD_SCHED
, "chan=%" PRIu64
" wrote %lu bytes, old was %" PRIi64
,
430 chan
->global_identifier
, (unsigned long) bytes
, ent
->written
);
432 ent
->written
+= bytes
;
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
444 MOCK_IMPL(int, channel_should_write_to_kernel
,
445 (outbuf_table_t
*table
, channel_t
*chan
))
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);
453 /* Little helper function to write a channel's outbuf all the way to the
455 MOCK_IMPL(void, channel_write_to_kernel
, (channel_t
*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);
464 /* Return true iff the scheduler has work to perform. */
468 smartlist_t
*cp
= get_channels_pending();
470 return 0; // channels_pending doesn't exist so... no work?
472 return smartlist_len(cp
) > 0;
475 /* Function of the scheduler interface: free_all() */
479 free_all_socket_info();
482 /* Function of the scheduler interface: on_channel_free() */
484 kist_on_channel_free_fn(const channel_t
*chan
)
486 free_socket_info_by_chan(&socket_table
, chan
);
489 /* Function of the scheduler interface: on_new_consensus() */
491 kist_scheduler_on_new_consensus(void)
493 set_scheduler_run_interval();
496 /* Function of the scheduler interface: on_new_options() */
498 kist_scheduler_on_new_options(void)
500 sock_buf_size_factor
= get_options()->KISTSockBufSizeFactor
;
502 /* Calls kist_scheduler_run_interval which calls get_options(). */
503 set_scheduler_run_interval();
506 /* Function of the scheduler interface: init() */
508 kist_scheduler_init(void)
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
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
);
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
;
530 /* Function of the scheduler interface: schedule() */
532 kist_scheduler_schedule(void)
534 struct monotime_t now
;
535 struct timeval next_run
;
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
);
549 log_info(LD_SCHED
, "Monotonic time between now and last run of scheduler "
550 "is negative: %" PRId64
". Setting diff to 0.", diff
);
553 if (diff
< sched_run_interval
) {
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
);
563 scheduler_ev_active();
567 /* Function of the scheduler interface: run() */
569 kist_scheduler_run(void)
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
;
578 smartlist_t
*cp
= get_channels_pending();
580 outbuf_table_t outbuf_table
= HT_INITIALIZER();
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
);
588 log_debug(LD_SCHED
, "Running the scheduler. %d channels pending",
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.
602 outbuf_table_add(&outbuf_table
, chan
);
604 /* if we have switched to a new channel, consider writing the previous
605 * channel's outbuf to the kernel. */
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
);
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
);
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
));
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. */
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.",
649 channel_state_to_string(chan
->state
),
650 get_scheduler_state_string(chan
->scheduler_state
));
651 scheduler_set_channel_state(chan
, SCHED_CHAN_WAITING_FOR_CELLS
);
656 /* Decide what to do with the channel now */
658 if (!channel_more_to_flush(chan
) &&
659 !socket_can_write(&socket_table
, chan
)) {
661 /* Case 1: no more cells to send, and cannot write */
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.
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.
678 scheduler_set_channel_state(chan
, SCHED_CHAN_WAITING_FOR_CELLS
);
679 } else if (!channel_more_to_flush(chan
)) {
681 /* Case 2: no more cells to send, but still open for writes */
683 scheduler_set_channel_state(chan
, SCHED_CHAN_WAITING_FOR_CELLS
);
684 } else if (!socket_can_write(&socket_table
, chan
)) {
686 /* Case 3: cells to send, but cannot write */
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.
696 to_readd
= smartlist_new();
698 smartlist_add(to_readd
, chan
);
701 /* Case 4: cells to send, and still open for writes */
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
);
709 } /* End of main scheduling loop */
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
,
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
);
718 log_debug(LD_SCHED
, "len pending=%d, len to_readd=%d",
720 (to_readd
? smartlist_len(to_readd
) : -1));
722 /* Re-add any channels we need to */
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(chan
->sched_heap_idx
!= -1, 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
);
735 } SMARTLIST_FOREACH_END(readd_chan
);
736 smartlist_free(to_readd
);
739 monotime_get(&scheduler_last_run
);
742 /*****************************************************************************
743 * Externally called function implementations not called through scheduler_t
744 *****************************************************************************/
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
,
758 /* Return the KIST scheduler object. If it didn't exists, return a newly
759 * allocated one but init() is not called. */
761 get_kist_scheduler(void)
763 return &kist_scheduler
;
766 /* Check the torrc (and maybe consensus) for the configured KIST scheduler run
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.
776 kist_scheduler_run_interval(void)
778 int run_interval
= get_options()->KISTSchedRunInterval
;
780 if (run_interval
!= 0) {
781 log_debug(LD_SCHED
, "Found KISTSchedRunInterval=%" PRId32
" in torrc. "
782 "Using that.", run_interval
);
786 log_debug(LD_SCHED
, "KISTSchedRunInterval=0, turning to the consensus.");
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
);
796 /* Set KISTLite mode that is KIST without kernel support. */
798 scheduler_kist_set_lite_mode(void)
801 kist_scheduler
.type
= SCHEDULER_KIST_LITE
;
803 "Setting KIST scheduler without kernel support (KISTLite mode)");
806 /* Set KIST mode that is KIST with kernel support. */
808 scheduler_kist_set_full_mode(void)
811 kist_scheduler
.type
= SCHEDULER_KIST
;
813 "Setting KIST scheduler with kernel support (KIST mode)");
816 #ifdef HAVE_KIST_SUPPORT
818 /* Return true iff the scheduler subsystem should use KIST. */
820 scheduler_can_use_kist(void)
822 if (kist_no_kernel_support
) {
823 /* We have no kernel support so we can't use KIST. */
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;
836 #else /* !(defined(HAVE_KIST_SUPPORT)) */
839 scheduler_can_use_kist(void)
844 #endif /* defined(HAVE_KIST_SUPPORT) */