Add circuitmux.c, circuitmux.h

5 files changed, 137 insertions, 7 deletions

diff --git a/src/or/Makefile.nmake b/src/or/Makefile.nmake
index b145fdcae..9f948d661 100644
--- a/src/or/Makefile.nmake
+++ b/src/or/Makefile.nmake
@@ -9,12 +9,12 @@ LIBS = ..\..\..\build-alpha\lib\libevent.a \
  ws2_32.lib advapi32.lib shell32.lib
 
 LIBTOR_OBJECTS = buffers.obj channel.obj channeltls.obj circuitbuild.obj \
-	circuitlist.obj circuituse.obj command.obj config.obj connection.obj
-	connection_edge.obj connection_or.obj control.obj cpuworker.obj \
-	directory.obj dirserv.obj dirvote.obj dns.obj dnsserv.obj geoip.obj \
-	hibernate.obj main.obj microdesc.obj networkstatus.obj \
-	nodelist.obj onion.obj policies.obj reasons.obj relay.obj \
-	rendclient.obj rendcommon.obj rendmid.obj rendservice.obj \
+	circuitlist.obj circuitmux.obj circuituse.obj command.obj config.obj \
+	connection.obj connection_edge.obj connection_or.obj control.obj \
+	cpuworker.obj directory.obj dirserv.obj dirvote.obj dns.obj \
+	dnsserv.obj geoip.obj hibernate.obj main.obj microdesc.obj \
+	networkstatus.obj nodelist.obj onion.obj policies.obj reasons.obj \
+	relay.obj rendclient.obj rendcommon.obj rendmid.obj rendservice.obj \
 	rephist.obj router.obj routerlist.obj routerparse.obj status.obj \
 	config_codedigest.obj ntmain.obj
 
diff --git a/src/or/circuitmux.c b/src/or/circuitmux.c
new file mode 100644
index 000000000..45b72f27b
--- /dev/null
+++ b/src/or/circuitmux.c
@@ -0,0 +1,67 @@
+/* * Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file circuitmux.c
+ * \brief Circuit mux/cell selection abstraction
+ **/
+
+#include "or.h"
+#include "circuitmux.h"
+
+/*
+ * A circuitmux is a collection of circuits; it tracks which subset
+ * of the attached circuits are 'active' (i.e., have cells available
+ * to transmit) and how many cells on each.  It expoes three distinct
+ * interfaces to other components:
+ *
+ * To channels, which each have a circuitmux_t, the supported operations
+ * are:
+ *
+ * circuitmux_flush_cells():
+ *
+ *   Retrieve a cell from one of the active circuits, chosen according to
+ *   the circuitmux_t's cell selection policy.
+ *
+ * circuitmux_unlink_all():
+ *
+ *   The channel is closing down, all circuits must be detached.
+ *
+ * To circuits, the exposed operations are:
+ *
+ *   TODO
+ *
+ * To circuit selection policies, the exposed operations are:
+ *
+ *   TODO
+ *
+ * General status inquiries?
+ *     
+ */
+
+struct circuitmux_s {
+  /*
+   * Double-linked ring of circuits with queued cells waiting for room to
+   * free up on this connection's outbuf.  Every time we pull cells from
+   * a circuit, we advance this pointer to the next circuit in the ring.
+   */
+  struct circuit_t *active_circuits;
+
+  /*
+   * Priority queue of cell_ewma_t for circuits with queued cells waiting
+   * for room to free up on this connection's outbuf.  Kept in heap order
+   * according to EWMA.
+   *
+   * This is redundant with active_circuits; if we ever decide only to use
+   * the cell_ewma algorithm for choosing circuits, we can remove
+   * active_circuits.
+   */
+  smartlist_t *active_circuit_pqueue;
+
+  /*
+   * The tick on which the cell_ewma_ts in active_circuit_pqueue last had
+   * their ewma values rescaled.
+   */
+  unsigned active_circuit_pqueue_last_recalibrated;
+};
+
diff --git a/src/or/circuitmux.h b/src/or/circuitmux.h
new file mode 100644
index 000000000..c5f95268e
--- /dev/null
+++ b/src/or/circuitmux.h
@@ -0,0 +1,50 @@
+/* * Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file circuitmux.h
+ * \brief Header file for circuitmux.c
+ **/
+
+#ifndef _TOR_CIRCUITMUX_H
+#define _TOR_CIRCUITMUX_H
+
+#include "or.h"
+
+/* Consistency check */
+void circuitmux_assert_okay(circuitmux_t *cmux);
+
+/* Create/destroy */
+circuitmux_t * circuitmux_alloc(void);
+void circuitmux_detach_all_circuits(circuitmux_t *cmux);
+void circuitmux_free(circuitmux_t *cmux);
+
+/* Status inquiries */
+cell_direction_t circuitmux_attached_circuit_direction(
+    circuitmux_t *cmux,
+    circuit_t *circ);
+int circuitmux_is_circuit_attached(circuitmux_t *cmux, circuit_t *circ);
+int circuitmux_is_circuit_active(circuitmux_t *cmux, circuit_t *circ);
+unsigned int circuitmux_num_cells_for_circuit(circuitmux_t *cmux,
+                                              circuit_t *circ);
+unsigned int circuitmux_num_cells(circuitmux_t *cmux);
+unsigned int circuitmux_num_circuits(circuitmux_t *cmux);
+unsigned int circuitmux_num_active_circuits(circuitmux_t *cmux);
+
+/* Channel interface */
+circuit_t * circuitmux_get_first_active_circuit(circuitmux_t *cmux);
+void circuitmux_notify_xmit_cells(circuitmux_t *cmux, circuit_t *circ,
+                                  unsigned int n_cells);
+
+/* Circuit interface */
+void circuitmux_attach_circuit(circuitmux_t *cmux, circuit_t *circ,
+                               cell_direction_t direction);
+void circuitmux_detach_circuit(circuitmux_t *cmux, circuit_t *circ);
+void circuitmux_clear_num_cells(circuitmux_t *cmux, circuit_t *circ);
+void circuitmux_add_to_num_cells(circuitmux_t *cmux, circuit_t *circ,
+                                 unsigned int n_cells);
+void circuitmux_set_num_cells(circuitmux_t *cmux, circuit_t *circ,
+                              unsigned int n_cells);
+
+#endif /* _TOR_CIRCUITMUX_H */
+
diff --git a/src/or/include.am b/src/or/include.am
index c32357532..3ec94e5be 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -21,6 +21,7 @@ src_or_libtor_a_SOURCES = \
 	src/or/channeltls.c				\
 	src/or/circuitbuild.c				\
 	src/or/circuitlist.c				\
+	src/or/circuitmux.c				\
 	src/or/circuituse.c				\
 	src/or/command.c				\
 	src/or/config.c					\
@@ -92,6 +93,7 @@ ORHEADERS = \
 	src/or/channeltls.h				\
 	src/or/circuitbuild.h				\
 	src/or/circuitlist.h				\
+	src/or/circuitmux.h				\
 	src/or/circuituse.h				\
 	src/or/command.h				\
 	src/or/config.h					\
diff --git a/src/or/or.h b/src/or/or.h
index 5987eefd8..87ee7bb7f 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1016,6 +1016,10 @@ typedef enum {
 
 typedef struct channel_tls_s channel_tls_t;
 
+/* circuitmux_t typedef; struct circuitmux_s is in circuitmux.h */
+
+typedef struct circuitmux_s circuitmux_t;
+
 /** Parsed onion routing cell.  All communication between nodes
  * is via cells. */
 typedef struct cell_t {
@@ -2634,7 +2638,14 @@ typedef struct circuit_t {
   cell_queue_t n_chan_cells;
   /** The channel that is next in this circuit. */
   channel_t *n_chan;
-  /** The circuit_id used in the next (forward) hop of this circuit. */
+
+  /**
+   * The circuit_id used in the next (forward) hop of this circuit;
+   * this is unique to n_chan, but this ordered pair is globally
+   * unique:
+   *
+   * (n_chan->global_identifier, n_circ_id)
+   */
   circid_t n_circ_id;
 
   /** The hop to which we want to extend this circuit.  Should be NULL if