1 /* Copyright (c) 2013-2017, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
7 #include "compat_libevent.h"
8 #define SCHEDULER_PRIVATE_
9 #define SCHEDULER_KIST_PRIVATE
10 #include "scheduler.h"
13 #define TOR_CHANNEL_INTERNAL_
14 #include "channeltls.h"
16 #include <event2/event.h>
20 * \brief Channel scheduling system: decides which channels should send and
23 * This module is the global/common parts of the scheduling system. This system
24 * is what decides what channels get to send cells on their circuits and when.
27 * - "Scheduling system": the collection of scheduler*.{h,c} files and their
29 * - "Scheduler implementation": a scheduler_t. The scheduling system has one
30 * active scheduling implementation at a time.
32 * In this file you will find state that any scheduler implementation can have
33 * access to as well as the functions the rest of Tor uses to interact with the
36 * The earliest versions of Tor approximated a kind of round-robin system
37 * among active connections, but only approximated it. It would only consider
38 * one connection (roughly equal to a channel in today's terms) at a time, and
39 * thus could only prioritize circuits against others on the same connection.
41 * Then in response to the KIST paper[0], Tor implemented a global
42 * circuit scheduler. It was supposed to prioritize circuits across many
43 * channels, but wasn't effective. It is preserved in scheduler_vanilla.c.
45 * [0]: http://www.robgjansen.com/publications/kist-sec2014.pdf
47 * Then we actually got around to implementing KIST for real. We decided to
48 * modularize the scheduler so new ones can be implemented. You can find KIST
49 * in scheduler_kist.c.
51 * Channels have one of four scheduling states based on whether or not they
52 * have cells to send and whether or not they are able to send.
56 * Not open for writes, no cells to send.
57 * <ul><li> Not much to do here, and the channel will have scheduler_state
59 * <li> Transitions from:
61 * <li>Open for writes/has cells by simultaneously draining all circuit
62 * queues and filling the output buffer.
64 * <li> Transitions to:
66 * <li> Not open for writes/has cells by arrival of cells on an attached
67 * circuit (this would be driven from append_cell_to_circuit_queue())
68 * <li> Open for writes/no cells by a channel type specific path;
69 * driven from connection_or_flushed_some() for channel_tls_t.
73 * <li> Open for writes, no cells to send
75 * <li>Not much here either; this will be the state an idle but open
76 * channel can be expected to settle in. It will have scheduler_state
77 * == SCHED_CHAN_WAITING_FOR_CELLS
78 * <li> Transitions from:
80 * <li>Not open for writes/no cells by flushing some of the output
82 * <li>Open for writes/has cells by the scheduler moving cells from
83 * circuit queues to channel output queue, but not having enough
84 * to fill the output queue.
86 * <li> Transitions to:
88 * <li>Open for writes/has cells by arrival of new cells on an attached
89 * circuit, in append_cell_to_circuit_queue()
93 * <li>Not open for writes, cells to send
95 * <li>This is the state of a busy circuit limited by output bandwidth;
96 * cells have piled up in the circuit queues waiting to be relayed.
97 * The channel will have scheduler_state == SCHED_CHAN_WAITING_TO_WRITE.
98 * <li> Transitions from:
100 * <li>Not open for writes/no cells by arrival of cells on an attached
102 * <li>Open for writes/has cells by filling an output buffer without
103 * draining all cells from attached circuits
105 * <li> Transitions to:
107 * <li>Opens for writes/has cells by draining some of the output buffer
108 * via the connection_or_flushed_some() path (for channel_tls_t).
112 * <li>Open for writes, cells to send
114 * <li>This connection is ready to relay some cells and waiting for
115 * the scheduler to choose it. The channel will have scheduler_state ==
116 * SCHED_CHAN_PENDING.
117 * <li>Transitions from:
119 * <li>Not open for writes/has cells by the connection_or_flushed_some()
121 * <li>Open for writes/no cells by the append_cell_to_circuit_queue()
124 * <li> Transitions to:
126 * <li>Not open for writes/no cells by draining all circuit queues and
127 * simultaneously filling the output buffer.
128 * <li>Not open for writes/has cells by writing enough cells to fill the
130 * <li>Open for writes/no cells by draining all attached circuit queues
131 * without also filling the output buffer
136 * Other event-driven parts of the code move channels between these scheduling
137 * states by calling scheduler functions. The scheduling system builds up a
138 * list of channels in the SCHED_CHAN_PENDING state that the scheduler
139 * implementation should then use when it runs. Scheduling implementations need
140 * to properly update channel states during their scheduler_t->run() function
141 * as that is the only opportunity for channels to move from SCHED_CHAN_PENDING
142 * to any other state.
144 * The remainder of this file is a small amount of state that any scheduler
145 * implementation should have access to, and the functions the rest of Tor uses
146 * to interact with the scheduling system.
149 /*****************************************************************************
150 * Scheduling system state
152 * State that can be accessed from any scheduler implementation (but not
153 * outside the scheduling system)
154 *****************************************************************************/
157 STATIC
const scheduler_t
*the_scheduler
;
160 * We keep a list of channels that are pending - i.e, have cells to write
161 * and can accept them to send. The enum scheduler_state in channel_t
162 * is reserved for our use.
164 * Priority queue of channels that can write and have cells (pending work)
166 STATIC smartlist_t
*channels_pending
= NULL
;
169 * This event runs the scheduler from its callback, and is manually
170 * activated whenever a channel enters open for writes/cells to send.
172 STATIC
struct event
*run_sched_ev
= NULL
;
174 static int have_logged_kist_suddenly_disabled
= 0;
176 /*****************************************************************************
177 * Scheduling system static function definitions
179 * Functions that can only be accessed from this file.
180 *****************************************************************************/
182 /** Return a human readable string for the given scheduler type. */
184 get_scheduler_type_string(scheduler_types_t type
)
187 case SCHEDULER_VANILLA
:
191 case SCHEDULER_KIST_LITE
:
196 tor_assert_unreached();
202 * Scheduler event callback; this should get triggered once per event loop
203 * if any scheduling work was created during the event loop.
206 scheduler_evt_callback(evutil_socket_t fd
, short events
, void *arg
)
212 log_debug(LD_SCHED
, "Scheduler event callback called");
214 /* Run the scheduler. This is a mandatory function. */
216 /* We might as well assert on this. If this function doesn't exist, no cells
217 * are getting scheduled. Things are very broken. scheduler_t says the run()
218 * function is mandatory. */
219 tor_assert(the_scheduler
->run
);
220 the_scheduler
->run();
222 /* Schedule itself back in if it has more work. */
224 /* Again, might as well assert on this mandatory scheduler_t function. If it
225 * doesn't exist, there's no way to tell libevent to run the scheduler again
227 tor_assert(the_scheduler
->schedule
);
228 the_scheduler
->schedule();
231 /** Using the global options, select the scheduler we should be using. */
233 select_scheduler(void)
235 scheduler_t
*new_scheduler
= NULL
;
237 #ifdef TOR_UNIT_TESTS
238 /* This is hella annoying to set in the options for every test that passes
239 * through the scheduler and there are many so if we don't explicitly have
240 * a list of types set, just put the vanilla one. */
241 if (get_options()->SchedulerTypes_
== NULL
) {
242 the_scheduler
= get_vanilla_scheduler();
245 #endif /* defined(TOR_UNIT_TESTS) */
247 /* This list is ordered that is first entry has the first priority. Thus, as
248 * soon as we find a scheduler type that we can use, we use it and stop. */
249 SMARTLIST_FOREACH_BEGIN(get_options()->SchedulerTypes_
, int *, type
) {
251 case SCHEDULER_VANILLA
:
252 new_scheduler
= get_vanilla_scheduler();
255 if (!scheduler_can_use_kist()) {
256 #ifdef HAVE_KIST_SUPPORT
257 if (!have_logged_kist_suddenly_disabled
) {
258 /* We should only log this once in most cases. If it was the kernel
259 * losing support for kist that caused scheduler_can_use_kist() to
260 * return false, then this flag makes sure we only log this message
261 * once. If it was the consensus that switched from "yes use kist"
262 * to "no don't use kist", then we still set the flag so we log
263 * once, but we unset the flag elsewhere if we ever can_use_kist()
266 have_logged_kist_suddenly_disabled
= 1;
267 log_notice(LD_SCHED
, "Scheduler type KIST has been disabled by "
268 "the consensus or no kernel support.");
270 #else /* !(defined(HAVE_KIST_SUPPORT)) */
271 log_info(LD_SCHED
, "Scheduler type KIST not built in");
272 #endif /* defined(HAVE_KIST_SUPPORT) */
275 /* This flag will only get set in one of two cases:
276 * 1 - the kernel lost support for kist. In that case, we don't expect to
278 * 2 - the consensus went from "yes use kist" to "no don't use kist".
279 * We might end up here if the consensus changes back to "yes", in which
280 * case we might want to warn the user again if it goes back to "no"
281 * yet again. Thus we unset the flag */
282 have_logged_kist_suddenly_disabled
= 0;
283 new_scheduler
= get_kist_scheduler();
284 scheduler_kist_set_full_mode();
286 case SCHEDULER_KIST_LITE
:
287 new_scheduler
= get_kist_scheduler();
288 scheduler_kist_set_lite_mode();
293 /* Our option validation should have caught this. */
294 tor_assert_unreached();
296 } SMARTLIST_FOREACH_END(type
);
299 if (new_scheduler
== NULL
) {
300 log_err(LD_SCHED
, "Tor was unable to select a scheduler type. Please "
301 "make sure Schedulers is correctly configured with "
302 "what Tor does support.");
303 /* We weren't able to choose a scheduler which means that none of the ones
304 * set in Schedulers are supported or usable. We will respect the user
305 * wishes of using what it has been configured and don't do a sneaky
306 * fallback. Because this can be changed at runtime, we have to stop tor
308 exit(1); // XXXX bad exit
311 /* Set the chosen scheduler. */
312 the_scheduler
= new_scheduler
;
316 * Helper function called from a few different places. It changes the
317 * scheduler implementation, if necessary. And if it did, it then tells the
318 * old one to free its state and the new one to initialize.
323 const scheduler_t
*old_scheduler
= the_scheduler
;
324 scheduler_types_t old_scheduler_type
= SCHEDULER_NONE
;
326 /* We keep track of the type in order to log only if the type switched. We
327 * can't just use the scheduler pointers because KIST and KISTLite share the
330 old_scheduler_type
= the_scheduler
->type
;
333 /* From the options, select the scheduler type to set. */
335 tor_assert(the_scheduler
);
337 /* We look at the pointer difference in case the old sched and new sched
338 * share the same scheduler object, as is the case with KIST and KISTLite. */
339 if (old_scheduler
!= the_scheduler
) {
340 /* Allow the old scheduler to clean up, if needed. */
341 if (old_scheduler
&& old_scheduler
->free_all
) {
342 old_scheduler
->free_all();
345 /* Initialize the new scheduler. */
346 if (the_scheduler
->init
) {
347 the_scheduler
->init();
351 /* Finally we notice log if we switched schedulers. We use the type in case
352 * two schedulers share a scheduler object. */
353 if (old_scheduler_type
!= the_scheduler
->type
) {
354 log_notice(LD_CONFIG
, "Scheduler type %s has been enabled.",
355 get_scheduler_type_string(the_scheduler
->type
));
359 /*****************************************************************************
360 * Scheduling system private function definitions
362 * Functions that can only be accessed from scheduler*.c
363 *****************************************************************************/
365 /** Returns human readable string for the given channel scheduler state. */
367 get_scheduler_state_string(int scheduler_state
)
369 switch (scheduler_state
) {
370 case SCHED_CHAN_IDLE
:
372 case SCHED_CHAN_WAITING_FOR_CELLS
:
373 return "WAITING_FOR_CELLS";
374 case SCHED_CHAN_WAITING_TO_WRITE
:
375 return "WAITING_TO_WRITE";
376 case SCHED_CHAN_PENDING
:
383 /** Helper that logs channel scheduler_state changes. Use this instead of
384 * setting scheduler_state directly. */
386 scheduler_set_channel_state(channel_t
*chan
, int new_state
)
388 log_debug(LD_SCHED
, "chan %" PRIu64
" changed from scheduler state %s to %s",
389 chan
->global_identifier
,
390 get_scheduler_state_string(chan
->scheduler_state
),
391 get_scheduler_state_string(new_state
));
392 chan
->scheduler_state
= new_state
;
395 /** Return the pending channel list. */
397 get_channels_pending(void)
399 return channels_pending
;
402 /** Comparison function to use when sorting pending channels. */
404 scheduler_compare_channels
, (const void *c1_v
, const void *c2_v
))
406 const channel_t
*c1
= NULL
, *c2
= NULL
;
407 /* These are a workaround for -Wbad-function-cast throwing a fit */
408 const circuitmux_policy_t
*p1
, *p2
;
409 uintptr_t p1_i
, p2_i
;
414 c1
= (const channel_t
*)(c1_v
);
415 c2
= (const channel_t
*)(c2_v
);
418 if (circuitmux_get_policy(c1
->cmux
) ==
419 circuitmux_get_policy(c2
->cmux
)) {
420 /* Same cmux policy, so use the mux comparison */
421 return circuitmux_compare_muxes(c1
->cmux
, c2
->cmux
);
424 * Different policies; not important to get this edge case perfect
425 * because the current code never actually gives different channels
426 * different cmux policies anyway. Just use this arbitrary but
429 p1
= circuitmux_get_policy(c1
->cmux
);
430 p2
= circuitmux_get_policy(c2
->cmux
);
431 p1_i
= (uintptr_t)p1
;
432 p2_i
= (uintptr_t)p2
;
434 return (p1_i
< p2_i
) ? -1 : 1;
437 /* c1 == c2, so always equal */
442 /*****************************************************************************
443 * Scheduling system global functions
445 * Functions that can be accessed from anywhere in Tor.
446 *****************************************************************************/
449 * This is how the scheduling system is notified of Tor's configuration
450 * changing. For example: a SIGHUP was issued.
453 scheduler_conf_changed(void)
455 /* Let the scheduler decide what it should do. */
458 /* Then tell the (possibly new) scheduler that we have new options. */
459 if (the_scheduler
->on_new_options
) {
460 the_scheduler
->on_new_options();
465 * Whenever we get a new consensus, this function is called.
468 scheduler_notify_networkstatus_changed(void)
470 /* Maybe the consensus param made us change the scheduler. */
473 /* Then tell the (possibly new) scheduler that we have a new consensus */
474 if (the_scheduler
->on_new_consensus
) {
475 the_scheduler
->on_new_consensus();
480 * Free everything scheduling-related from main.c. Note this is only called
481 * when Tor is shutting down, while scheduler_t->free_all() is called both when
482 * Tor is shutting down and when we are switching schedulers.
485 scheduler_free_all(void)
487 log_debug(LD_SCHED
, "Shutting down scheduler");
490 if (event_del(run_sched_ev
) < 0) {
491 log_warn(LD_BUG
, "Problem deleting run_sched_ev");
493 tor_event_free(run_sched_ev
);
497 if (channels_pending
) {
498 /* We don't have ownership of the objects in this list. */
499 smartlist_free(channels_pending
);
500 channels_pending
= NULL
;
503 if (the_scheduler
&& the_scheduler
->free_all
) {
504 the_scheduler
->free_all();
506 the_scheduler
= NULL
;
509 /** Mark a channel as no longer ready to accept writes. */
511 scheduler_channel_doesnt_want_writes
,(channel_t
*chan
))
516 IF_BUG_ONCE(!channels_pending
) {
520 /* If it's already in pending, we can put it in waiting_to_write */
521 if (chan
->scheduler_state
== SCHED_CHAN_PENDING
) {
523 * It's in channels_pending, so it shouldn't be in any of
524 * the other lists. It can't write any more, so it goes to
525 * channels_waiting_to_write.
527 smartlist_pqueue_remove(channels_pending
,
528 scheduler_compare_channels
,
529 offsetof(channel_t
, sched_heap_idx
),
531 scheduler_set_channel_state(chan
, SCHED_CHAN_WAITING_TO_WRITE
);
534 * It's not in pending, so it can't become waiting_to_write; it's
535 * either not in any of the lists (nothing to do) or it's already in
536 * waiting_for_cells (remove it, can't write any more).
538 if (chan
->scheduler_state
== SCHED_CHAN_WAITING_FOR_CELLS
) {
539 scheduler_set_channel_state(chan
, SCHED_CHAN_IDLE
);
544 /** Mark a channel as having waiting cells. */
546 scheduler_channel_has_waiting_cells
,(channel_t
*chan
))
551 IF_BUG_ONCE(!channels_pending
) {
555 /* First, check if it's also writeable */
556 if (chan
->scheduler_state
== SCHED_CHAN_WAITING_FOR_CELLS
) {
558 * It's in channels_waiting_for_cells, so it shouldn't be in any of
559 * the other lists. It has waiting cells now, so it goes to
562 scheduler_set_channel_state(chan
, SCHED_CHAN_PENDING
);
563 if (!SCHED_BUG(chan
->sched_heap_idx
!= -1, chan
)) {
564 smartlist_pqueue_add(channels_pending
,
565 scheduler_compare_channels
,
566 offsetof(channel_t
, sched_heap_idx
),
569 /* If we made a channel pending, we potentially have scheduling work to
571 the_scheduler
->schedule();
574 * It's not in waiting_for_cells, so it can't become pending; it's
575 * either not in any of the lists (we add it to waiting_to_write)
576 * or it's already in waiting_to_write or pending (we do nothing)
578 if (!(chan
->scheduler_state
== SCHED_CHAN_WAITING_TO_WRITE
||
579 chan
->scheduler_state
== SCHED_CHAN_PENDING
)) {
580 scheduler_set_channel_state(chan
, SCHED_CHAN_WAITING_TO_WRITE
);
585 /** Add the scheduler event to the set of pending events with next_run being
586 * the longest time libevent should wait before triggering the event. */
588 scheduler_ev_add(const struct timeval
*next_run
)
590 tor_assert(run_sched_ev
);
591 tor_assert(next_run
);
592 if (BUG(event_add(run_sched_ev
, next_run
) < 0)) {
593 log_warn(LD_SCHED
, "Adding to libevent failed. Next run time was set to: "
594 "%ld.%06ld", next_run
->tv_sec
, (long)next_run
->tv_usec
);
599 /** Make the scheduler event active with the given flags. */
601 scheduler_ev_active(int flags
)
603 tor_assert(run_sched_ev
);
604 event_active(run_sched_ev
, flags
, 1);
608 * Initialize everything scheduling-related from config.c. Note this is only
609 * called when Tor is starting up, while scheduler_t->init() is called both
610 * when Tor is starting up and when we are switching schedulers.
615 log_debug(LD_SCHED
, "Initting scheduler");
617 // Two '!' because we really do want to check if the pointer is non-NULL
618 IF_BUG_ONCE(!!run_sched_ev
) {
619 log_warn(LD_SCHED
, "We should not already have a libevent scheduler event."
620 "I'll clean the old one up, but this is odd.");
621 tor_event_free(run_sched_ev
);
624 run_sched_ev
= tor_event_new(tor_libevent_get_base(), -1,
625 0, scheduler_evt_callback
, NULL
);
626 channels_pending
= smartlist_new();
632 * If a channel is going away, this is how the scheduling system is informed
633 * so it can do any freeing necessary. This ultimately calls
634 * scheduler_t->on_channel_free() so the current scheduler can release any
635 * state specific to this channel.
638 scheduler_release_channel
,(channel_t
*chan
))
643 IF_BUG_ONCE(!channels_pending
) {
647 /* Try to remove the channel from the pending list regardless of its
648 * scheduler state. We can release a channel in many places in the tor code
649 * so we can't rely on the channel state (PENDING) to remove it from the
652 * For instance, the channel can change state from OPEN to CLOSING while
653 * being handled in the scheduler loop leading to the channel being in
654 * PENDING state but not in the pending list. Furthermore, we release the
655 * channel when it changes state to close and a second time when we free it.
656 * Not ideal at all but for now that is the way it is. */
657 if (chan
->sched_heap_idx
!= -1) {
658 smartlist_pqueue_remove(channels_pending
,
659 scheduler_compare_channels
,
660 offsetof(channel_t
, sched_heap_idx
),
664 if (the_scheduler
->on_channel_free
) {
665 the_scheduler
->on_channel_free(chan
);
667 scheduler_set_channel_state(chan
, SCHED_CHAN_IDLE
);
670 /** Mark a channel as ready to accept writes */
673 scheduler_channel_wants_writes(channel_t
*chan
)
678 IF_BUG_ONCE(!channels_pending
) {
682 /* If it's already in waiting_to_write, we can put it in pending */
683 if (chan
->scheduler_state
== SCHED_CHAN_WAITING_TO_WRITE
) {
685 * It can write now, so it goes to channels_pending.
687 scheduler_set_channel_state(chan
, SCHED_CHAN_PENDING
);
688 if (!SCHED_BUG(chan
->sched_heap_idx
!= -1, chan
)) {
689 smartlist_pqueue_add(channels_pending
,
690 scheduler_compare_channels
,
691 offsetof(channel_t
, sched_heap_idx
),
694 /* We just made a channel pending, we have scheduling work to do. */
695 the_scheduler
->schedule();
698 * It's not in SCHED_CHAN_WAITING_TO_WRITE, so it can't become pending;
699 * it's either idle and goes to WAITING_FOR_CELLS, or it's a no-op.
701 if (!(chan
->scheduler_state
== SCHED_CHAN_WAITING_FOR_CELLS
||
702 chan
->scheduler_state
== SCHED_CHAN_PENDING
)) {
703 scheduler_set_channel_state(chan
, SCHED_CHAN_WAITING_FOR_CELLS
);
708 /* Log warn the given channel and extra scheduler context as well. This is
709 * used by SCHED_BUG() in order to be able to extract as much information as
710 * we can when we hit a bug. Channel chan can be NULL. */
712 scheduler_bug_occurred(const channel_t
*chan
)
717 const size_t outbuf_len
=
718 buf_datalen(TO_CONN(BASE_CHAN_TO_TLS((channel_t
*) chan
)->conn
)->outbuf
);
719 tor_snprintf(buf
, sizeof(buf
),
720 "Channel %" PRIu64
" in state %s and scheduler state %s."
721 " Num cells on cmux: %d. Connection outbuf len: %lu.",
722 chan
->global_identifier
,
723 channel_state_to_string(chan
->state
),
724 get_scheduler_state_string(chan
->scheduler_state
),
725 circuitmux_num_cells(chan
->cmux
),
726 (unsigned long)outbuf_len
);
731 /* Rate limit every 60 seconds. If we start seeing this every 60 sec, we
732 * know something is stuck/wrong. It *should* be loud but not too much. */
733 static ratelim_t rlimit
= RATELIM_INIT(60);
734 if ((msg
= rate_limit_log(&rlimit
, approx_time()))) {
735 log_warn(LD_BUG
, "%s Num pending channels: %d. "
736 "Channel in pending list: %s.%s",
737 (chan
!= NULL
) ? buf
: "No channel in bug context.",
738 smartlist_len(channels_pending
),
739 (smartlist_pos(channels_pending
, chan
) == -1) ? "no" : "yes",
746 #ifdef TOR_UNIT_TESTS
749 * Notify scheduler that a channel's queue position may have changed.
752 scheduler_touch_channel(channel_t
*chan
)
758 if (chan
->scheduler_state
== SCHED_CHAN_PENDING
) {
759 /* Remove and re-add it */
760 smartlist_pqueue_remove(channels_pending
,
761 scheduler_compare_channels
,
762 offsetof(channel_t
, sched_heap_idx
),
764 smartlist_pqueue_add(channels_pending
,
765 scheduler_compare_channels
,
766 offsetof(channel_t
, sched_heap_idx
),
769 /* else no-op, since it isn't in the queue */
772 #endif /* defined(TOR_UNIT_TESTS) */