scheduler.c File Reference

Channel scheduling system: decides which channels should send and receive when. More...

#include "core/or/or.h"
#include "app/config/config.h"
#include "lib/evloop/compat_libevent.h"
#include "core/or/scheduler.h"
#include "core/mainloop/mainloop.h"
#include "lib/buf/buffers.h"
#include "core/or/channeltls.h"
#include "core/or/or_connection_st.h"

Go to the source code of this file.

Functions
static const char *	get_scheduler_type_string (scheduler_types_t type)
static void	scheduler_evt_callback (mainloop_event_t *event, void *arg)
static void	select_scheduler (void)
static void	set_scheduler (void)
const char *	get_scheduler_state_string (int scheduler_state)
void	scheduler_set_channel_state (channel_t *chan, int new_state)
smartlist_t *	get_channels_pending (void)
int	scheduler_compare_channels (const void *c1_v, const void *c2_v)
void	scheduler_conf_changed (void)
void	scheduler_notify_networkstatus_changed (void)
void	scheduler_free_all (void)
void	scheduler_channel_doesnt_want_writes (channel_t *chan)
void	scheduler_channel_has_waiting_cells (channel_t *chan)
void	scheduler_ev_add (const struct timeval *next_run)
void	scheduler_ev_active (void)
void	scheduler_init (void)
void	scheduler_release_channel (channel_t *chan)
void	scheduler_channel_wants_writes (channel_t *chan)
void	scheduler_bug_occurred (const channel_t *chan)

Variables
STATIC const scheduler_t *	the_scheduler
STATIC smartlist_t *	channels_pending = NULL
STATIC struct mainloop_event_t *	run_sched_ev = NULL
static int	have_logged_kist_suddenly_disabled = 0

Detailed Description

Channel scheduling system: decides which channels should send and receive when.

This module is the global/common parts of the scheduling system. This system is what decides what channels get to send cells on their circuits and when.

Terms:

• "Scheduling system": the collection of scheduler*.{h,c} files and their aggregate behavior.
• "Scheduler implementation": a scheduler_t. The scheduling system has one active scheduling implementation at a time.

In this file you will find state that any scheduler implementation can have access to as well as the functions the rest of Tor uses to interact with the scheduling system.

The earliest versions of Tor approximated a kind of round-robin system among active connections, but only approximated it. It would only consider one connection (roughly equal to a channel in today's terms) at a time, and thus could only prioritize circuits against others on the same connection.

Then in response to the KIST paper0, Tor implemented a global circuit scheduler. It was supposed to prioritize circuits across many channels, but wasn't effective. It is preserved in scheduler_vanilla.c.

Then we actually got around to implementing KIST for real. We decided to modularize the scheduler so new ones can be implemented. You can find KIST in scheduler_kist.c.

Channels have one of four scheduling states based on whether or not they have cells to send and whether or not they are able to send.

1. Not open for writes, no cells to send.

   • Not much to do here, and the channel will have scheduler_state == SCHED_CHAN_IDLE
   • Transitions from:
     • Open for writes/has cells by simultaneously draining all circuit queues and filling the output buffer.
   • Transitions to:
     • Not open for writes/has cells by arrival of cells on an attached circuit (this would be driven from append_cell_to_circuit_queue())
     • Open for writes/no cells by a channel type specific path; driven from connection_or_flushed_some() for channel_tls_t.

2. Open for writes, no cells to send

   • Not much here either; this will be the state an idle but open channel can be expected to settle in. It will have scheduler_state == SCHED_CHAN_WAITING_FOR_CELLS
   • Transitions from:
     • Not open for writes/no cells by flushing some of the output buffer.
     • Open for writes/has cells by the scheduler moving cells from circuit queues to channel output queue, but not having enough to fill the output queue.
   • Transitions to:
     • Open for writes/has cells by arrival of new cells on an attached circuit, in append_cell_to_circuit_queue()

3. Not open for writes, cells to send

   • This is the state of a busy circuit limited by output bandwidth; cells have piled up in the circuit queues waiting to be relayed. The channel will have scheduler_state == SCHED_CHAN_WAITING_TO_WRITE.
   • Transitions from:
     • Not open for writes/no cells by arrival of cells on an attached circuit
     • Open for writes/has cells by filling an output buffer without draining all cells from attached circuits
   • Transitions to:
     • Opens for writes/has cells by draining some of the output buffer via the connection_or_flushed_some() path (for channel_tls_t).

4. Open for writes, cells to send
   • This connection is ready to relay some cells and waiting for the scheduler to choose it. The channel will have scheduler_state == SCHED_CHAN_PENDING.
   • Transitions from:
     • Not open for writes/has cells by the connection_or_flushed_some() path
     • Open for writes/no cells by the append_cell_to_circuit_queue() path
   • Transitions to:
     • Not open for writes/no cells by draining all circuit queues and simultaneously filling the output buffer.
     • Not open for writes/has cells by writing enough cells to fill the output buffer
     • Open for writes/no cells by draining all attached circuit queues without also filling the output buffer

Other event-driven parts of the code move channels between these scheduling states by calling scheduler functions. The scheduling system builds up a list of channels in the SCHED_CHAN_PENDING state that the scheduler implementation should then use when it runs. Scheduling implementations need to properly update channel states during their scheduler_t->run() function as that is the only opportunity for channels to move from SCHED_CHAN_PENDING to any other state.

The remainder of this file is a small amount of state that any scheduler implementation should have access to, and the functions the rest of Tor uses to interact with the scheduling system.

Definition in file scheduler.c.

Function Documentation

get_channels_pending()

smartlist_t* get_channels_pending

(

void

)

Return the pending channel list.

Definition at line 396 of file scheduler.c.

get_scheduler_state_string()

const char* get_scheduler_state_string

(

int

scheduler_state

)

Returns human readable string for the given channel scheduler state.

Definition at line 366 of file scheduler.c.

get_scheduler_type_string()

static const char* get_scheduler_type_string ( scheduler_types_t  type )

static

Return a human readable string for the given scheduler type.

Definition at line 184 of file scheduler.c.

scheduler_channel_doesnt_want_writes()

void scheduler_channel_doesnt_want_writes

(

channel_t *

chan

)

Mark a channel as no longer ready to accept writes.

Possible state changes:

• SCHED_CHAN_PENDING -> SCHED_CHAN_WAITING_TO_WRITE
• SCHED_CHAN_WAITING_FOR_CELLS -> SCHED_CHAN_IDLE

Definition at line 512 of file scheduler.c.

scheduler_channel_has_waiting_cells()

void scheduler_channel_has_waiting_cells

(

channel_t *

chan

)

Mark a channel as having waiting cells.

Possible state changes:

• SCHED_CHAN_WAITING_FOR_CELLS -> SCHED_CHAN_PENDING
• SCHED_CHAN_IDLE -> SCHED_CHAN_WAITING_TO_WRITE

Definition at line 548 of file scheduler.c.

scheduler_channel_wants_writes()

void scheduler_channel_wants_writes

(

channel_t *

chan

)

Mark a channel as ready to accept writes. Possible state changes:

• SCHED_CHAN_WAITING_TO_WRITE -> SCHED_CHAN_PENDING
• SCHED_CHAN_IDLE -> SCHED_CHAN_WAITING_FOR_CELLS

Definition at line 673 of file scheduler.c.

scheduler_compare_channels()

int scheduler_compare_channels	(	const void *	c1_v,
		const void *	c2_v
	)

Comparison function to use when sorting pending channels.

Definition at line 403 of file scheduler.c.

Referenced by scheduler_channel_doesnt_want_writes(), scheduler_channel_has_waiting_cells(), and scheduler_channel_wants_writes().

scheduler_conf_changed()

void scheduler_conf_changed

(

void

)

This is how the scheduling system is notified of Tor's configuration changing. For example: a SIGHUP was issued.

Definition at line 452 of file scheduler.c.

scheduler_ev_active()

void scheduler_ev_active

(

void

)

Make the scheduler event active with the given flags.

Definition at line 598 of file scheduler.c.

scheduler_ev_add()

void scheduler_ev_add

(

const struct timeval *

next_run

)

Add the scheduler event to the set of pending events with next_run being the longest time libevent should wait before triggering the event.

Definition at line 585 of file scheduler.c.

scheduler_evt_callback()

static void scheduler_evt_callback ( mainloop_event_t *  event, void *  arg  )

static

Scheduler event callback; this should get triggered once per event loop if any scheduling work was created during the event loop.

Definition at line 206 of file scheduler.c.

scheduler_free_all()

void scheduler_free_all

(

void

)

Free everything scheduling-related from main.c. Note this is only called when Tor is shutting down, while scheduler_t->free_all() is called both when Tor is shutting down and when we are switching schedulers.

Definition at line 484 of file scheduler.c.

scheduler_notify_networkstatus_changed()

void scheduler_notify_networkstatus_changed

(

void

)

Whenever we get a new consensus, this function is called.

Definition at line 467 of file scheduler.c.

scheduler_set_channel_state()

void scheduler_set_channel_state	(	channel_t *	chan,
		int	new_state
	)

Helper that logs channel scheduler_state changes. Use this instead of setting scheduler_state directly.

Definition at line 385 of file scheduler.c.

Referenced by scheduler_channel_doesnt_want_writes(), scheduler_channel_has_waiting_cells(), and scheduler_channel_wants_writes().

select_scheduler()

static void select_scheduler ( void  )

static

Using the global options, select the scheduler we should be using.

Definition at line 232 of file scheduler.c.

set_scheduler()

static void set_scheduler ( void  )

static

Helper function called from a few different places. It changes the scheduler implementation, if necessary. And if it did, it then tells the old one to free its state and the new one to initialize.

Definition at line 320 of file scheduler.c.

Referenced by scheduler_conf_changed(), and scheduler_notify_networkstatus_changed().

Variable Documentation

channels_pending

STATIC smartlist_t* channels_pending = NULL

We keep a list of channels that are pending - i.e, have cells to write and can accept them to send. The enum scheduler_state in channel_t is reserved for our use.

Priority queue of channels that can write and have cells (pending work)

Definition at line 166 of file scheduler.c.

Referenced by get_channels_pending(), scheduler_channel_doesnt_want_writes(), scheduler_channel_has_waiting_cells(), and scheduler_channel_wants_writes().

run_sched_ev

STATIC struct mainloop_event_t* run_sched_ev = NULL

This event runs the scheduler from its callback, and is manually activated whenever a channel enters open for writes/cells to send.

Definition at line 172 of file scheduler.c.

Referenced by scheduler_ev_active(), and scheduler_ev_add().

the_scheduler

STATIC const scheduler_t* the_scheduler

DOCDOC

Definition at line 157 of file scheduler.c.

Referenced by scheduler_channel_has_waiting_cells(), scheduler_channel_wants_writes(), scheduler_conf_changed(), scheduler_notify_networkstatus_changed(), select_scheduler(), and set_scheduler().