Tor  0.4.7.0-alpha-dev
scheduler_vanilla.c
Go to the documentation of this file.
1 /* Copyright (c) 2017-2021, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
3 
4 /**
5  * @file scheduler_vanilla.c
6  * @brief "Vanilla" (pre-KIST) cell scheduler code.
7  **/
8 
9 #include "core/or/or.h"
10 #include "app/config/config.h"
11 #define CHANNEL_OBJECT_PRIVATE
12 #include "core/or/channel.h"
13 #define SCHEDULER_PRIVATE
14 #include "core/or/scheduler.h"
15 
16 /*****************************************************************************
17  * Other internal data
18  *****************************************************************************/
19 
20 /* Maximum cells to flush in a single call to channel_flush_some_cells(); */
21 #define MAX_FLUSH_CELLS 1000
22 
23 /*****************************************************************************
24  * Externally called function implementations
25  *****************************************************************************/
26 
27 /* Return true iff the scheduler has work to perform. */
28 static int
29 have_work(void)
30 {
32  IF_BUG_ONCE(!cp) {
33  return 0; // channels_pending doesn't exist so... no work?
34  }
35  return smartlist_len(cp) > 0;
36 }
37 
38 /** Re-trigger the scheduler in a way safe to use from the callback */
39 
40 static void
42 {
43  if (!have_work()) {
44  return;
45  }
46 
47  /* Activate our event so it can process channels. */
49 }
50 
51 static void
52 vanilla_scheduler_run(void)
53 {
54  int n_cells, n_chans_before, n_chans_after;
55  ssize_t flushed, flushed_this_time;
57  smartlist_t *to_readd = NULL;
58  channel_t *chan = NULL;
59 
60  log_debug(LD_SCHED, "We have a chance to run the scheduler");
61 
62  n_chans_before = smartlist_len(cp);
63 
64  while (smartlist_len(cp) > 0) {
65  /* Pop off a channel */
66  chan = smartlist_pqueue_pop(cp,
68  offsetof(channel_t, sched_heap_idx));
69  IF_BUG_ONCE(!chan) {
70  /* Some-freaking-how a NULL got into the channels_pending. That should
71  * never happen, but it should be harmless to ignore it and keep looping.
72  */
73  continue;
74  }
75 
76  /* Figure out how many cells we can write */
77  n_cells = channel_num_cells_writeable(chan);
78  if (n_cells > 0) {
79  log_debug(LD_SCHED,
80  "Scheduler saw pending channel %"PRIu64 " at %p with "
81  "%d cells writeable",
82  (chan->global_identifier), chan, n_cells);
83 
84  flushed = 0;
85  while (flushed < n_cells) {
86  flushed_this_time =
88  MIN(MAX_FLUSH_CELLS, (size_t) n_cells - flushed));
89  if (flushed_this_time <= 0) break;
90  flushed += flushed_this_time;
91  }
92 
93  if (flushed < n_cells) {
94  /* We ran out of cells to flush */
95  scheduler_set_channel_state(chan, SCHED_CHAN_WAITING_FOR_CELLS);
96  } else {
97  /* The channel may still have some cells */
98  if (channel_more_to_flush(chan)) {
99  /* The channel goes to either pending or waiting_to_write */
100  if (channel_num_cells_writeable(chan) > 0) {
101  /* Add it back to pending later */
102  if (!to_readd) to_readd = smartlist_new();
103  smartlist_add(to_readd, chan);
104  log_debug(LD_SCHED,
105  "Channel %"PRIu64 " at %p "
106  "is still pending",
107  (chan->global_identifier),
108  chan);
109  } else {
110  /* It's waiting to be able to write more */
111  scheduler_set_channel_state(chan, SCHED_CHAN_WAITING_TO_WRITE);
112  }
113  } else {
114  /* No cells left; it can go to idle or waiting_for_cells */
115  if (channel_num_cells_writeable(chan) > 0) {
116  /*
117  * It can still accept writes, so it goes to
118  * waiting_for_cells
119  */
120  scheduler_set_channel_state(chan, SCHED_CHAN_WAITING_FOR_CELLS);
121  } else {
122  /*
123  * We exactly filled up the output queue with all available
124  * cells; go to idle.
125  */
126  scheduler_set_channel_state(chan, SCHED_CHAN_IDLE);
127  }
128  }
129  }
130 
131  log_debug(LD_SCHED,
132  "Scheduler flushed %d cells onto pending channel "
133  "%"PRIu64 " at %p",
134  (int)flushed, (chan->global_identifier),
135  chan);
136  } else {
137  log_info(LD_SCHED,
138  "Scheduler saw pending channel %"PRIu64 " at %p with "
139  "no cells writeable",
140  (chan->global_identifier), chan);
141  /* Put it back to WAITING_TO_WRITE */
142  scheduler_set_channel_state(chan, SCHED_CHAN_WAITING_TO_WRITE);
143  }
144  }
145 
146  /* Readd any channels we need to */
147  if (to_readd) {
148  SMARTLIST_FOREACH_BEGIN(to_readd, channel_t *, readd_chan) {
149  scheduler_set_channel_state(readd_chan, SCHED_CHAN_PENDING);
152  offsetof(channel_t, sched_heap_idx),
153  readd_chan);
154  } SMARTLIST_FOREACH_END(readd_chan);
155  smartlist_free(to_readd);
156  }
157 
158  n_chans_after = smartlist_len(cp);
159  log_debug(LD_SCHED, "Scheduler handled %d of %d pending channels",
160  n_chans_before - n_chans_after, n_chans_before);
161 }
162 
163 /* Stores the vanilla scheduler function pointers. */
164 static scheduler_t vanilla_scheduler = {
165  .type = SCHEDULER_VANILLA,
166  .free_all = NULL,
167  .on_channel_free = NULL,
168  .init = NULL,
169  .on_new_consensus = NULL,
170  .schedule = vanilla_scheduler_schedule,
171  .run = vanilla_scheduler_run,
172  .on_new_options = NULL,
173 };
174 
175 scheduler_t *
176 get_vanilla_scheduler(void)
177 {
178  return &vanilla_scheduler;
179 }
ssize_t channel_flush_some_cells(channel_t *chan, ssize_t num_cells)
Definition: channel.c:1730
int channel_num_cells_writeable(channel_t *chan)
Definition: channel.c:3056
int channel_more_to_flush(channel_t *chan)
Definition: channel.c:1773
Header file for channel.c.
Header file for config.c.
#define LD_SCHED
Definition: log.h:107
Master header file for Tor-specific functionality.
void scheduler_ev_active(void)
Definition: scheduler.c:598
int scheduler_compare_channels(const void *c1_v, const void *c2_v)
Definition: scheduler.c:403
void scheduler_set_channel_state(channel_t *chan, int new_state)
Definition: scheduler.c:385
smartlist_t * get_channels_pending(void)
Definition: scheduler.c:396
Header file for scheduler*.c.
static void vanilla_scheduler_schedule(void)
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
void * smartlist_pqueue_pop(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset)
Definition: smartlist.c:755
smartlist_t * smartlist_new(void)
void smartlist_add(smartlist_t *sl, void *element)
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
uint64_t global_identifier
Definition: channel.h:197
#define IF_BUG_ONCE(cond)
Definition: util_bug.h:246