9#define SCHEDULER_KIST_PRIVATE
17#define CHANNEL_OBJECT_PRIVATE
20#define SCHEDULER_PRIVATE
26#ifdef HAVE_SYS_IOCTL_H
30#ifdef HAVE_KIST_SUPPORT
32#include <netinet/tcp.h>
33#include <linux/sockios.h>
44socket_table_ent_hash(
const socket_table_ent_t *ent)
46 return (uint32_t)ent->chan->global_identifier;
50socket_table_ent_eq(
const socket_table_ent_t *a,
const socket_table_ent_t *b)
52 return a->chan == b->chan;
55typedef HT_HEAD(socket_table_s, socket_table_ent_t) socket_table_t;
57static socket_table_t socket_table = HT_INITIALIZER();
59HT_PROTOTYPE(socket_table_s, socket_table_ent_t, node, socket_table_ent_hash,
61HT_GENERATE2(socket_table_s, socket_table_ent_t, node, socket_table_ent_hash,
62 socket_table_ent_eq, 0.6, tor_reallocarray,
tor_free_);
69typedef struct outbuf_table_ent_t {
70 HT_ENTRY(outbuf_table_ent_t) node;
75outbuf_table_ent_hash(
const outbuf_table_ent_t *ent)
77 return (uint32_t)ent->chan->global_identifier;
81outbuf_table_ent_eq(
const outbuf_table_ent_t *a,
const outbuf_table_ent_t *b)
83 return a->chan->global_identifier == b->chan->global_identifier;
86HT_PROTOTYPE(outbuf_table_s, outbuf_table_ent_t, node, outbuf_table_ent_hash,
88HT_GENERATE2(outbuf_table_s, outbuf_table_ent_t, node, outbuf_table_ent_hash,
89 outbuf_table_ent_eq, 0.6, tor_reallocarray,
tor_free_);
101static double sock_buf_size_factor = 1.0;
103STATIC int sched_run_interval = KIST_SCHED_RUN_INTERVAL_DEFAULT;
105#ifdef HAVE_KIST_SUPPORT
108static unsigned int kist_lite_mode = 0;
112static unsigned int kist_no_kernel_support = 0;
114static unsigned int kist_lite_mode = 1;
129 if (SCHED_BUG(BASE_CHAN_TO_TLS(chan)->conn == NULL, chan)) {
137each_channel_write_to_kernel(outbuf_table_ent_t *ent,
void *data)
140 channel_write_to_kernel(ent->chan);
146free_outbuf_info_by_ent(outbuf_table_ent_t *ent,
void *data)
149 log_debug(
LD_SCHED,
"Freeing outbuf table entry from chan=%" PRIu64,
150 ent->chan->global_identifier);
157free_socket_info_by_ent(socket_table_ent_t *ent,
void *data)
160 log_debug(
LD_SCHED,
"Freeing socket table entry from chan=%" PRIu64,
161 ent->chan->global_identifier);
168free_all_socket_info(
void)
170 HT_FOREACH_FN(socket_table_s, &socket_table, free_socket_info_by_ent, NULL);
171 HT_CLEAR(socket_table_s, &socket_table);
174static socket_table_ent_t *
175socket_table_search(socket_table_t *table,
const channel_t *chan)
177 socket_table_ent_t search, *ent = NULL;
179 ent = HT_FIND(socket_table_s, table, &search);
185free_socket_info_by_chan(socket_table_t *table,
const channel_t *chan)
187 socket_table_ent_t *ent = NULL;
188 ent = socket_table_search(table, chan);
191 log_debug(
LD_SCHED,
"scheduler free socket info for chan=%" PRIu64,
193 HT_REMOVE(socket_table_s, table, ent);
194 free_socket_info_by_ent(ent, NULL);
200update_socket_info_impl, (socket_table_ent_t *ent))
202#ifdef HAVE_KIST_SUPPORT
203 int64_t tcp_space, extra_space;
207 TO_CONN(CONST_BASE_CHAN_TO_TLS(ent->chan)->conn)->s;
209 socklen_t tcp_info_len =
sizeof(tcp);
211 if (kist_no_kernel_support || kist_lite_mode) {
216 if (getsockopt(sock, SOL_TCP, TCP_INFO, (
void *)&(tcp), &tcp_info_len) < 0) {
217 if (errno == EINVAL) {
222 log_notice(
LD_SCHED,
"Looks like our kernel doesn't have the support "
223 "for KIST anymore. We will fallback to the naive "
224 "approach. Remove KIST from the Schedulers list "
226 kist_no_kernel_support = 1;
230 if (ioctl(sock, SIOCOUTQNSD, &(ent->notsent)) < 0) {
231 if (errno == EINVAL) {
232 log_notice(
LD_SCHED,
"Looks like our kernel doesn't have the support "
233 "for KIST anymore. We will fallback to the naive "
234 "approach. Remove KIST from the Schedulers list "
237 kist_no_kernel_support = 1;
241 ent->cwnd = tcp.tcpi_snd_cwnd;
242 ent->unacked = tcp.tcpi_unacked;
243 ent->mss = tcp.tcpi_snd_mss;
282 if (ent->cwnd >= ent->unacked) {
283 tcp_space = (ent->cwnd - ent->unacked) * (int64_t)(ent->mss);
294 (ent->cwnd * (int64_t)ent->mss) * sock_buf_size_factor) -
295 ent->notsent - (int64_t)channel_outbuf_length((
channel_t *) ent->chan);
296 if ((tcp_space + extra_space) < 0) {
303 ent->limit = (uint64_t)tcp_space + (uint64_t)extra_space;
317 ent->cwnd = ent->unacked = ent->mss = ent->notsent = 0;
323 (get_cell_network_size(ent->chan->wide_circ_ids) +
324 TLS_PER_CELL_OVERHEAD);
332init_socket_info(socket_table_t *table,
const channel_t *chan)
334 socket_table_ent_t *ent = NULL;
335 ent = socket_table_search(table, chan);
337 log_debug(
LD_SCHED,
"scheduler init socket info for chan=%" PRIu64,
339 ent = tor_malloc_zero(
sizeof(*ent));
341 HT_INSERT(socket_table_s, table, ent);
349outbuf_table_add(outbuf_table_t *table,
channel_t *chan)
351 outbuf_table_ent_t search, *ent;
353 ent = HT_FIND(outbuf_table_s, table, &search);
355 log_debug(
LD_SCHED,
"scheduler init outbuf info for chan=%" PRIu64,
357 ent = tor_malloc_zero(
sizeof(*ent));
359 HT_INSERT(outbuf_table_s, table, ent);
364outbuf_table_remove(outbuf_table_t *table,
channel_t *chan)
366 outbuf_table_ent_t search, *ent;
368 ent = HT_FIND(outbuf_table_s, table, &search);
370 HT_REMOVE(outbuf_table_s, table, ent);
371 free_outbuf_info_by_ent(ent, NULL);
377set_scheduler_run_interval(
void)
379 int old_sched_run_interval = sched_run_interval;
380 sched_run_interval = kist_scheduler_run_interval();
381 if (old_sched_run_interval != sched_run_interval) {
382 log_info(
LD_SCHED,
"Scheduler KIST changing its running interval "
383 "from %" PRId32
" to %" PRId32,
384 old_sched_run_interval, sched_run_interval);
390socket_can_write(socket_table_t *table,
const channel_t *chan)
392 socket_table_ent_t *ent = NULL;
393 ent = socket_table_search(table, chan);
394 if (SCHED_BUG(!ent, chan)) {
402 int64_t kist_limit_space =
403 (int64_t) (ent->limit - ent->written) /
405 return kist_limit_space > 0;
410update_socket_info(socket_table_t *table,
const channel_t *chan)
412 socket_table_ent_t *ent = NULL;
413 ent = socket_table_search(table, chan);
414 if (SCHED_BUG(!ent, chan)) {
417 update_socket_info_impl(ent);
418 log_debug(
LD_SCHED,
"chan=%" PRIu64
" updated socket info, limit: %" PRIu64
419 ", cwnd: %" PRIu32
", unacked: %" PRIu32
420 ", notsent: %" PRIu32
", mss: %" PRIu32,
421 ent->chan->global_identifier, ent->limit, ent->cwnd, ent->unacked,
422 ent->notsent, ent->mss);
427update_socket_written(socket_table_t *table,
channel_t *chan,
size_t bytes)
429 socket_table_ent_t *ent = NULL;
430 ent = socket_table_search(table, chan);
431 if (SCHED_BUG(!ent, chan)) {
435 log_debug(
LD_SCHED,
"chan=%" PRIu64
" wrote %lu bytes, old was %" PRIi64,
438 ent->written += bytes;
461MOCK_IMPL(
int, channel_should_write_to_kernel,
462 (outbuf_table_t *table,
channel_t *chan))
464 outbuf_table_add(table, chan);
478 size_t outbuf_len = channel_outbuf_length(chan);
479 if (outbuf_len == 0) {
483 log_debug(
LD_SCHED,
"Writing %lu bytes to kernel for chan %" PRIu64,
493 connection_handle_write(
TO_CONN(BASE_CHAN_TO_TLS(chan)->conn), 0);
504 return smartlist_len(cp) > 0;
511 free_all_socket_info();
516kist_on_channel_free_fn(
const channel_t *chan)
518 free_socket_info_by_chan(&socket_table, chan);
523kist_scheduler_on_new_consensus(
void)
525 set_scheduler_run_interval();
530kist_scheduler_on_new_options(
void)
535 set_scheduler_run_interval();
540kist_scheduler_init(
void)
552 kist_scheduler_on_new_options();
554 log_warn(
LD_SCHED,
"We are initing the KIST scheduler and noticed the "
555 "KISTSchedRunInterval is telling us to not use KIST. That's "
556 "weird! We'll continue using KIST, but at %" PRId32
"ms.",
557 KIST_SCHED_RUN_INTERVAL_DEFAULT);
558 sched_run_interval = KIST_SCHED_RUN_INTERVAL_DEFAULT;
564kist_scheduler_schedule(
void)
581 log_info(
LD_SCHED,
"Monotonic time between now and last run of scheduler "
582 "is negative: %" PRId64
". Setting diff to 0.", diff);
585 if (diff < sched_run_interval) {
591 next_run.tv_usec = (int) ((sched_run_interval - diff) * 1000);
601kist_scheduler_run(
void)
612 outbuf_table_t outbuf_table = HT_INITIALIZER();
616 init_socket_info(&socket_table, pchan);
617 update_socket_info(&socket_table, pchan);
618 } SMARTLIST_FOREACH_END(pchan);
620 log_debug(
LD_SCHED,
"Running the scheduler. %d channels pending",
624 while (smartlist_len(cp) > 0) {
628 if (SCHED_BUG(!chan, NULL)) {
634 outbuf_table_add(&outbuf_table, chan);
641 if (prev_chan != chan) {
642 if (channel_should_write_to_kernel(&outbuf_table, prev_chan)) {
643 channel_write_to_kernel(prev_chan);
644 outbuf_table_remove(&outbuf_table, prev_chan);
650 if (socket_can_write(&socket_table, chan)) {
659 if (!CHANNEL_IS_OPEN(chan)) {
666 if (flush_result > 0) {
667 update_socket_written(&socket_table, chan, flush_result *
676 "We didn't flush anything on a chan that we think "
677 "can write and wants to write. The channel's state is '%s' "
678 "and in scheduler state '%s'. We're going to mark it as "
679 "waiting_for_cells (as that's most likely the issue) and "
680 "stop scheduling it this round.",
691 !socket_can_write(&socket_table, chan)) {
716 }
else if (!socket_can_write(&socket_table, chan)) {
738 offsetof(
channel_t, sched_heap_idx), chan);
744 HT_FOREACH_FN(outbuf_table_s, &outbuf_table, each_channel_write_to_kernel,
747 HT_FOREACH_FN(outbuf_table_s, &outbuf_table, free_outbuf_info_by_ent, NULL);
748 HT_CLEAR(outbuf_table_s, &outbuf_table);
750 log_debug(
LD_SCHED,
"len pending=%d, len to_readd=%d",
752 (to_readd ? smartlist_len(to_readd) : -1));
759 if (!SCHED_BUG(readd_chan->sched_heap_idx != -1, readd_chan)) {
764 offsetof(
channel_t, sched_heap_idx), readd_chan);
767 } SMARTLIST_FOREACH_END(readd_chan);
768 smartlist_free(to_readd);
780 .type = SCHEDULER_KIST,
781 .free_all = kist_free_all,
782 .on_channel_free = kist_on_channel_free_fn,
783 .init = kist_scheduler_init,
784 .on_new_consensus = kist_scheduler_on_new_consensus,
785 .schedule = kist_scheduler_schedule,
786 .run = kist_scheduler_run,
787 .on_new_options = kist_scheduler_on_new_options,
793get_kist_scheduler(
void)
795 return &kist_scheduler;
808kist_scheduler_run_interval(
void)
812 if (run_interval != 0) {
813 log_debug(
LD_SCHED,
"Found KISTSchedRunInterval=%" PRId32
" in torrc. "
814 "Using that.", run_interval);
818 log_debug(
LD_SCHED,
"KISTSchedRunInterval=0, turning to the consensus.");
824 KIST_SCHED_RUN_INTERVAL_DEFAULT,
825 KIST_SCHED_RUN_INTERVAL_MIN,
826 KIST_SCHED_RUN_INTERVAL_MAX);
829 KIST_SCHED_RUN_INTERVAL_DEFAULT,
830 KIST_SCHED_RUN_INTERVAL_MIN,
831 KIST_SCHED_RUN_INTERVAL_MAX);
837scheduler_kist_set_lite_mode(
void)
840 kist_scheduler.type = SCHEDULER_KIST_LITE;
842 "Setting KIST scheduler without kernel support (KISTLite mode)");
847scheduler_kist_set_full_mode(
void)
850 kist_scheduler.type = SCHEDULER_KIST;
852 "Setting KIST scheduler with kernel support (KIST mode)");
855#ifdef HAVE_KIST_SUPPORT
859scheduler_can_use_kist(
void)
861 if (kist_no_kernel_support) {
868 int run_interval = kist_scheduler_run_interval();
869 log_debug(
LD_SCHED,
"Determined KIST sched_run_interval should be "
870 "%" PRId32
". Can%s use KIST.",
871 run_interval, (run_interval > 0 ?
"" :
" not"));
872 return run_interval > 0;
878scheduler_can_use_kist(
void)
size_t buf_datalen(const buf_t *buf)
Header file for buffers.c.
const char * channel_state_to_string(channel_state_t state)
ssize_t channel_flush_some_cells(channel_t *chan, ssize_t num_cells)
int channel_num_cells_writeable(channel_t *chan)
int channel_more_to_flush(channel_t *chan)
Header file for channel.c.
Header file for channeltls.c.
int64_t monotime_diff_msec(const monotime_t *start, const monotime_t *end)
void monotime_get(monotime_t *out)
const or_options_t * get_options(void)
Header file for config.c.
Header file for connection.c.
int64_t clamp_double_to_int64(double number)
HT_PROTOTYPE(hs_circuitmap_ht, circuit_t, hs_circuitmap_node, hs_circuit_hash_token, hs_circuits_have_same_token)
typedef HT_HEAD(hs_service_ht, hs_service_t) hs_service_ht
void tor_free_(void *mem)
int32_t networkstatus_get_param(const networkstatus_t *ns, const char *param_name, int32_t default_val, int32_t min_val, int32_t max_val)
Header file for networkstatus.c.
Master header file for Tor-specific functionality.
#define CELL_MAX_NETWORK_SIZE
int server_mode(const or_options_t *options)
Header file for routermode.c.
void scheduler_ev_active(void)
const char * get_scheduler_state_string(int scheduler_state)
smartlist_t * get_channels_pending(void)
int scheduler_compare_channels(const void *c1_v, const void *c2_v)
void scheduler_set_channel_state(channel_t *chan, int new_state)
void scheduler_ev_add(const struct timeval *next_run)
Header file for scheduler*.c.
void * smartlist_pqueue_pop(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset)
void smartlist_pqueue_add(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset, void *item)
int smartlist_contains(const smartlist_t *sl, const void *element)
smartlist_t * smartlist_new(void)
void smartlist_add(smartlist_t *sl, void *element)
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
enum channel_t::@9 scheduler_state
uint64_t global_identifier
double KISTSockBufSizeFactor
#define MOCK_IMPL(rv, funcname, arglist)
#define IF_BUG_ONCE(cond)