tor  master
Macros | Functions | Variables
scheduler.c File Reference

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

#include "or.h"
#include "config.h"
#include "compat_libevent.h"
#include "scheduler.h"
#include "main.h"
#include "buffers.h"
#include "channeltls.h"
Include dependency graph for scheduler.c:

Functions

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)
 
 MOCK_IMPL (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)
 
 MOCK_IMPL (void, scheduler_channel_doesnt_want_writes,(channel_t *chan))
 
 MOCK_IMPL (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)
 
 MOCK_IMPL (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
 

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:

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:

  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:

  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:

  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:
    • 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.

Function Documentation

◆ get_channels_pending()

smartlist_t* get_channels_pending ( void  )

Return the pending channel list.

◆ get_scheduler_state_string()

const char* get_scheduler_state_string ( int  scheduler_state)

Returns human readable string for the given channel scheduler state.

◆ MOCK_IMPL() [1/3]

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

Comparison function to use when sorting pending channels.

◆ MOCK_IMPL() [2/3]

MOCK_IMPL ( void  ,
scheduler_channel_doesnt_want_writes  ,
(channel_t *chan)   
)

Mark a channel as no longer ready to accept writes.

Here is the call graph for this function:

◆ MOCK_IMPL() [3/3]

MOCK_IMPL ( void  ,
scheduler_channel_has_waiting_cells  ,
(channel_t *chan)   
)

Mark a channel as having waiting cells.

Here is the call graph for this function:

◆ scheduler_channel_wants_writes()

void scheduler_channel_wants_writes ( channel_t *  chan)

Mark a channel as ready to accept writes

Here is the call graph for this function:

◆ 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.

◆ scheduler_ev_active()

void scheduler_ev_active ( void  )

Make the scheduler event active with the given flags.

Here is the call graph for this function:

◆ 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.

◆ 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.

◆ scheduler_notify_networkstatus_changed()

void scheduler_notify_networkstatus_changed ( void  )

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

◆ 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.

Here is the caller graph for this function:

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)

◆ 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.

◆ the_scheduler

STATIC const scheduler_t* the_scheduler

DOCDOC

Generated by   doxygen 1.8.13