sched: Implement the KIST scheduler

Closes #12541

Signed-off-by: David Goulet <dgoulet@torproject.org>

1 files changed, 149 insertions, 36 deletions

diff --git a/src/or/scheduler.h b/src/or/scheduler.h
index 699ccde7a3..3932e60490 100644
--- a/src/or/scheduler.h
+++ b/src/or/scheduler.h
@@ -1,9 +1,9 @@
-/* * Copyright (c) 2013-2017, The Tor Project, Inc. */
+/* * Copyright (c) 2017, The Tor Project, Inc. */
 /* See LICENSE for licensing information */
 
 /**
  * \file scheduler.h
- * \brief Header file for scheduler.c
+ * \brief Header file for scheduler*.c
  **/
 
 #ifndef TOR_SCHEDULER_H
@@ -13,50 +13,163 @@
 #include "channel.h"
 #include "testsupport.h"
 
-/* Global-visibility scheduler functions */
+/*
+ * A scheduler implementation is a collection of function pointers. If you
+ * would like to add a new scheduler called foo, create scheduler_foo.c,
+ * implement at least the mandatory ones, and implement get_foo_scheduler()
+ * that returns a complete scheduler_t for your foo scheduler. See
+ * scheduler_kist.c for an example.
+ *
+ * These function pointers SHOULD NOT be used anywhere outside of the
+ * scheduling source files. The rest of Tor should communicate with the
+ * scheduling system through the functions near the bottom of this file, and
+ * those functions will call into the current scheduler implementation as
+ * necessary.
+ *
+ * If your scheduler doesn't need to implement something (for example: it
+ * doesn't create any state for itself, thus it has nothing to free when Tor
+ * is shutting down), then set that function pointer to NULL.
+ */
+typedef struct scheduler_s {
+  /* (Optional) To be called when we want to prepare a scheduler for use.
+   * Perhaps Tor just started and we are the lucky chosen scheduler, or
+   * perhaps Tor is switching to this scheduler. No matter the case, this is
+   * where we would prepare any state and initialize parameters. You might
+   * think of this as the opposite of free_all(). */
+  void (*init)(void);
+
+  /* (Optional) To be called when we want to tell the scheduler to delete all
+   * of its state (if any). Perhaps Tor is shutting down or perhaps we are
+   * switching schedulers. */
+  void (*free_all)(void);
+
+  /* (Mandatory) Libevent controls the main event loop in Tor, and this is
+   * where we register with libevent the next execution of run_sched_ev [which
+   * ultimately calls run()]. */
+  void (*schedule)(void);
+
+  /* (Mandatory) This is the heart of a scheduler! This is where the
+   * excitement happens! Here libevent has given us the chance to execute, and
+   * we should do whatever we need to do in order to move some cells from
+   * their circuit queues to output buffers in an intelligent manner. We
+   * should do this quickly. When we are done, we'll try to schedule() ourself
+   * if more work needs to be done to setup the next scehduling run. */
+  void (*run)(void);
+
+  /*
+   * External event not related to the scheduler but that can influence it.
+   */
+
+  /* (Optional) To be called whenever Tor finds out about a new consensus.
+   * First the scheduling system as a whole will react to the new consensus
+   * and change the scheduler if needed. After that, whatever is the (possibly
+   * new) scheduler will call this so it has the chance to react to the new
+   * consensus too. If there's a consensus parameter that your scheduler wants
+   * to keep an eye on, this is where you should check for it.  */
+  void (*on_new_consensus)(const networkstatus_t *old_c,
+                           const networkstatus_t *new_c);
+
+  /* (Optional) To be called when a channel is being freed. Sometimes channels
+   * go away (for example: the relay on the other end is shutting down). If
+   * the scheduler keeps any channel-specific state and has memory to free
+   * when channels go away, implement this and free it here. */
+  void (*on_channel_free)(const channel_t *);
+
+  /* (Optional) To be called whenever Tor is reloading configuration options.
+   * For example: SIGHUP was issued and Tor is rereading its torrc. A
+   * scheduler should use this as an opportunity to parse and cache torrc
+   * options so that it doesn't have to call get_options() all the time. */
+  void (*on_new_options)(void);
+} scheduler_t;
+
+/*****************************************************************************
+ * Globally visible scheduler functions
+ *
+ * These functions are how the rest of Tor communicates with the scheduling
+ * system.
+ *****************************************************************************/
 
-/* Set up and shut down the scheduler from main.c */
-void scheduler_free_all(void);
 void scheduler_init(void);
-MOCK_DECL(void, scheduler_run, (void));
-
-/* Mark channels as having cells or wanting/not wanting writes */
-MOCK_DECL(void,scheduler_channel_doesnt_want_writes,(channel_t *chan));
-MOCK_DECL(void,scheduler_channel_has_waiting_cells,(channel_t *chan));
-void scheduler_channel_wants_writes(channel_t *chan);
-
-/* Notify the scheduler of a channel being closed */
-MOCK_DECL(void,scheduler_release_channel,(channel_t *chan));
-
-/* Notify scheduler of queue size adjustments */
-void scheduler_adjust_queue_size(channel_t *chan, int dir, uint64_t adj);
-
-/* Notify scheduler that a channel's queue position may have changed */
-void scheduler_touch_channel(channel_t *chan);
-
-/* Adjust the watermarks from config file*/
-void scheduler_set_watermarks(uint32_t lo, uint32_t hi, uint32_t max_flush);
-
-/* XXXFORTOR Temp def of this func to get this commit to compile. Replace with
- * real func */
+void scheduler_free_all(void);
+void scheduler_conf_changed(void);
 void scheduler_notify_networkstatus_changed(const networkstatus_t *old_c,
                                             const networkstatus_t *new_c);
+MOCK_DECL(void, scheduler_release_channel, (channel_t *chan));
 
-/* Things only scheduler.c and its test suite should see */
-
+/*
+ * Ways for a channel to interact with the scheduling system. A channel only
+ * really knows (i) whether or not it has cells it wants to send, and
+ * (ii) whether or not it would like to write.
+ */
+void scheduler_channel_wants_writes(channel_t *chan);
+MOCK_DECL(void, scheduler_channel_doesnt_want_writes, (channel_t *chan));
+MOCK_DECL(void, scheduler_channel_has_waiting_cells, (channel_t *chan));
+
+/*****************************************************************************
+ * Private scheduler functions
+ *
+ * These functions are only visible to the scheduling system, the current
+ * scheduler implementation, and tests.
+ *****************************************************************************/
 #ifdef SCHEDULER_PRIVATE_
-MOCK_DECL(STATIC int, scheduler_compare_channels,
+
+/*********************************
+ * Defined in scheduler.c
+ *********************************/
+int scheduler_should_use_kist(void);
+smartlist_t *get_channels_pending(void);
+struct event *get_run_sched_ev(void);
+MOCK_DECL(int, scheduler_compare_channels,
           (const void *c1_v, const void *c2_v));
-STATIC uint64_t scheduler_get_queue_heuristic(void);
-STATIC void scheduler_update_queue_heuristic(time_t now);
 
 #ifdef TOR_UNIT_TESTS
 extern smartlist_t *channels_pending;
 extern struct event *run_sched_ev;
-extern uint64_t queue_heuristic;
-extern time_t queue_heuristic_timestamp;
-#endif
-#endif
+extern scheduler_t *scheduler;
+void scheduler_touch_channel(channel_t *chan);
+#endif /* TOR_UNIT_TESTS */
+
+/*********************************
+ * Defined in scheduler_kist.c
+ *********************************/
+
+/* Socke table entry which holds information of a channel's socket and kernel
+ * TCP information. Only used by KIST. */
+typedef struct socket_table_ent_s {
+  HT_ENTRY(socket_table_ent_s) node;
+  const channel_t *chan;
+  /* Amount written this scheduling run */
+  uint64_t written;
+  /* Amount that can be written this scheduling run */
+  uint64_t limit;
+  /* TCP info from the kernel */
+  uint32_t cwnd;
+  uint32_t unacked;
+  uint32_t mss;
+  uint32_t notsent;
+} socket_table_ent_t;
+
+typedef HT_HEAD(outbuf_table_s, outbuf_table_ent_s) outbuf_table_t;
+
+MOCK_DECL(int, channel_should_write_to_kernel,
+          (outbuf_table_t *table, channel_t *chan));
+MOCK_DECL(void, channel_write_to_kernel, (channel_t *chan));
+MOCK_DECL(void, update_socket_info_impl, (socket_table_ent_t *ent));
+
+scheduler_t *get_kist_scheduler(void);
+int32_t kist_scheduler_run_interval(const networkstatus_t *ns);
+
+#ifdef TOR_UNIT_TESTS
+extern int32_t sched_run_interval;
+#endif /* TOR_UNIT_TESTS */
+
+/*********************************
+ * Defined in scheduler_vanilla.c
+ *********************************/
+
+scheduler_t *get_vanilla_scheduler(void);
+
+#endif /* SCHEDULER_PRIVATE_ */
 
-#endif /* !defined(TOR_SCHEDULER_H) */
+#endif /* TOR_SCHEDULER_H */