commit d3063da691d0006cf41f6406099f056ab47c543a
Merge: 9e45d94 c37fdc2
Author: Nick Mathewson <nickm(a)torproject.org>
Date: Tue Jun 18 10:23:03 2013 -0400
Merge remote-tracking branch 'origin/maint-0.2.3' into maint-0.2.4
Conflicts:
src/or/config.c
src/or/relay.c
changes/bug9002 | 4 ++
changes/bug9063_redux | 15 ++++++++
doc/tor.1.txt | 9 +++++
src/common/mempool.h | 2 +
src/or/circuitlist.c | 102 +++++++++++++++++++++++++++++++++++++++++++++++++
src/or/circuitlist.h | 1 +
src/or/config.c | 8 ++++
src/or/or.h | 4 ++
src/or/relay.c | 33 +++++++++++++++-
src/or/relay.h | 1 +
src/or/rendcommon.c | 25 +++++++++++-
11 files changed, 200 insertions(+), 4 deletions(-)
diff --cc src/or/config.c
index df1a67e,d5c5689..55d19b8
--- a/src/or/config.c
+++ b/src/or/config.c
@@@ -299,9 -343,8 +299,10 @@@ static config_var_t option_vars_[] =
V(MaxAdvertisedBandwidth, MEMUNIT, "1 GB"),
V(MaxCircuitDirtiness, INTERVAL, "10 minutes"),
V(MaxClientCircuitsPending, UINT, "32"),
+ V(MaxMemInCellQueues, MEMUNIT, "8 GB"),
- V(MaxOnionsPending, UINT, "100"),
+ OBSOLETE("MaxOnionsPending"),
+ V(MaxOnionQueueDelay, MSEC_INTERVAL, "1750 msec"),
+ V(MinMeasuredBWsForAuthToIgnoreAdvertised, INT, "500"),
OBSOLETE("MonthlyAccountingStart"),
V(MyFamily, STRING, NULL),
V(NewCircuitPeriod, INTERVAL, "30 seconds"),
@@@ -2606,11 -3665,17 +2607,18 @@@ options_validate(or_options_t *old_opti
if (options->UseBridges && options->EntryNodes)
REJECT("You cannot set both UseBridges and EntryNodes.");
- if (options->EntryNodes && !options->UseEntryGuards)
- log_warn(LD_CONFIG, "EntryNodes is set, but UseEntryGuards is disabled. "
- "EntryNodes will be ignored.");
+ if (options->EntryNodes && !options->UseEntryGuards) {
+ REJECT("If EntryNodes is set, UseEntryGuards must be enabled.");
+ }
+ if (options->MaxMemInCellQueues < (500 << 20)) {
+ log_warn(LD_CONFIG, "MaxMemInCellQueues must be at least 500 MB for now. "
+ "Ideally, have it as large as you can afford.");
+ options->MaxMemInCellQueues = (500 << 20);
+ }
+
- options->_AllowInvalid = 0;
+ options->AllowInvalid_ = 0;
++
if (options->AllowInvalidNodes) {
SMARTLIST_FOREACH_BEGIN(options->AllowInvalidNodes, const char *, cp) {
if (!strcasecmp(cp, "entry"))
diff --cc src/or/relay.c
index 0f21663,fda9e89..3138c5e
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@@ -2106,15 -1864,14 +2106,15 @@@ dump_cell_pool_usage(int severity
circuit_t *c;
int n_circs = 0;
int n_cells = 0;
- for (c = _circuit_get_global_list(); c; c = c->next) {
- n_cells += c->n_conn_cells.n;
+ for (c = circuit_get_global_list_(); c; c = c->next) {
+ n_cells += c->n_chan_cells.n;
if (!CIRCUIT_IS_ORIGIN(c))
- n_cells += TO_OR_CIRCUIT(c)->p_conn_cells.n;
+ n_cells += TO_OR_CIRCUIT(c)->p_chan_cells.n;
++n_circs;
}
- log(severity, LD_MM, "%d cells allocated on %d circuits. %d cells leaked.",
- n_cells, n_circs, (int)total_cells_allocated - n_cells);
+ tor_log(severity, LD_MM,
+ "%d cells allocated on %d circuits. %d cells leaked.",
- n_cells, n_circs, total_cells_allocated - n_cells);
++ n_cells, n_circs, (int)total_cells_allocated - n_cells);
mp_pool_log_status(cell_pool, severity);
}
@@@ -2222,64 -1978,382 +2222,87 @@@ cell_queue_pop(cell_queue_t *queue
return cell;
}
+ /** Return the total number of bytes used for each packed_cell in a queue.
+ * Approximate. */
+ size_t
+ packed_cell_mem_cost(void)
+ {
+ return sizeof(packed_cell_t) + MP_POOL_ITEM_OVERHEAD +
+ get_options()->CellStatistics ?
+ (sizeof(insertion_time_elem_t)+MP_POOL_ITEM_OVERHEAD) : 0;
+ }
+
+ /** Check whether we've got too much space used for cells. If so,
+ * call the OOM handler and return 1. Otherwise, return 0. */
+ static int
+ cell_queues_check_size(void)
+ {
+ size_t alloc = total_cells_allocated * packed_cell_mem_cost();
+ if (alloc >= get_options()->MaxMemInCellQueues) {
+ circuits_handle_oom(alloc);
+ return 1;
+ }
+ return 0;
+ }
+
-/** Return a pointer to the "next_active_on_{n,p}_conn" pointer of <b>circ</b>,
- * depending on whether <b>conn</b> matches n_conn or p_conn. */
-static INLINE circuit_t **
-next_circ_on_conn_p(circuit_t *circ, or_connection_t *conn)
-{
- tor_assert(circ);
- tor_assert(conn);
- if (conn == circ->n_conn) {
- return &circ->next_active_on_n_conn;
- } else {
- or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
- tor_assert(conn == orcirc->p_conn);
- return &orcirc->next_active_on_p_conn;
- }
-}
-
-/** Return a pointer to the "prev_active_on_{n,p}_conn" pointer of <b>circ</b>,
- * depending on whether <b>conn</b> matches n_conn or p_conn. */
-static INLINE circuit_t **
-prev_circ_on_conn_p(circuit_t *circ, or_connection_t *conn)
-{
- tor_assert(circ);
- tor_assert(conn);
- if (conn == circ->n_conn) {
- return &circ->prev_active_on_n_conn;
- } else {
- or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
- tor_assert(conn == orcirc->p_conn);
- return &orcirc->prev_active_on_p_conn;
- }
-}
-
-/** Helper for sorting cell_ewma_t values in their priority queue. */
-static int
-compare_cell_ewma_counts(const void *p1, const void *p2)
-{
- const cell_ewma_t *e1=p1, *e2=p2;
- if (e1->cell_count < e2->cell_count)
- return -1;
- else if (e1->cell_count > e2->cell_count)
- return 1;
- else
- return 0;
-}
-
-/** Given a cell_ewma_t, return a pointer to the circuit containing it. */
-static circuit_t *
-cell_ewma_to_circuit(cell_ewma_t *ewma)
-{
- if (ewma->is_for_p_conn) {
- /* This is an or_circuit_t's p_cell_ewma. */
- or_circuit_t *orcirc = SUBTYPE_P(ewma, or_circuit_t, p_cell_ewma);
- return TO_CIRCUIT(orcirc);
- } else {
- /* This is some circuit's n_cell_ewma. */
- return SUBTYPE_P(ewma, circuit_t, n_cell_ewma);
- }
-}
-
-/* ==== Functions for scaling cell_ewma_t ====
-
- When choosing which cells to relay first, we favor circuits that have been
- quiet recently. This gives better latency on connections that aren't
- pushing lots of data, and makes the network feel more interactive.
-
- Conceptually, we take an exponentially weighted mean average of the number
- of cells a circuit has sent, and allow active circuits (those with cells to
- relay) to send cells in reverse order of their exponentially-weighted mean
- average (EWMA) cell count. [That is, a cell sent N seconds ago 'counts'
- F^N times as much as a cell sent now, for 0<F<1.0, and we favor the
- circuit that has sent the fewest cells]
-
- If 'double' had infinite precision, we could do this simply by counting a
- cell sent at startup as having weight 1.0, and a cell sent N seconds later
- as having weight F^-N. This way, we would never need to re-scale
- any already-sent cells.
-
- To prevent double from overflowing, we could count a cell sent now as
- having weight 1.0 and a cell sent N seconds ago as having weight F^N.
- This, however, would mean we'd need to re-scale *ALL* old circuits every
- time we wanted to send a cell.
-
- So as a compromise, we divide time into 'ticks' (currently, 10-second
- increments) and say that a cell sent at the start of a current tick is
- worth 1.0, a cell sent N seconds before the start of the current tick is
- worth F^N, and a cell sent N seconds after the start of the current tick is
- worth F^-N. This way we don't overflow, and we don't need to constantly
- rescale.
- */
-
-/** How long does a tick last (seconds)? */
-#define EWMA_TICK_LEN 10
-
-/** The default per-tick scale factor, if it hasn't been overridden by a
- * consensus or a configuration setting. zero means "disabled". */
-#define EWMA_DEFAULT_HALFLIFE 0.0
-
-/** Given a timeval <b>now</b>, compute the cell_ewma tick in which it occurs
- * and the fraction of the tick that has elapsed between the start of the tick
- * and <b>now</b>. Return the former and store the latter in
- * *<b>remainder_out</b>.
- *
- * These tick values are not meant to be shared between Tor instances, or used
- * for other purposes. */
-static unsigned
-cell_ewma_tick_from_timeval(const struct timeval *now,
- double *remainder_out)
-{
- unsigned res = (unsigned) (now->tv_sec / EWMA_TICK_LEN);
- /* rem */
- double rem = (now->tv_sec % EWMA_TICK_LEN) +
- ((double)(now->tv_usec)) / 1.0e6;
- *remainder_out = rem / EWMA_TICK_LEN;
- return res;
-}
-
-/** Compute and return the current cell_ewma tick. */
-unsigned
-cell_ewma_get_tick(void)
-{
- return ((unsigned)approx_time() / EWMA_TICK_LEN);
-}
-
-/** The per-tick scale factor to be used when computing cell-count EWMA
- * values. (A cell sent N ticks before the start of the current tick
- * has value ewma_scale_factor ** N.)
+/**
+ * Update the number of cells available on the circuit's n_chan or p_chan's
+ * circuit mux.
*/
-static double ewma_scale_factor = 0.1;
-/* DOCDOC ewma_enabled */
-static int ewma_enabled = 0;
-
-/*DOCDOC*/
-#define EPSILON 0.00001
-/*DOCDOC*/
-#define LOG_ONEHALF -0.69314718055994529
-
-/** Adjust the global cell scale factor based on <b>options</b> */
void
-cell_ewma_set_scale_factor(const or_options_t *options,
- const networkstatus_t *consensus)
+update_circuit_on_cmux_(circuit_t *circ, cell_direction_t direction,
+ const char *file, int lineno)
{
- int32_t halflife_ms;
- double halflife;
- const char *source;
- if (options && options->CircuitPriorityHalflife >= -EPSILON) {
- halflife = options->CircuitPriorityHalflife;
- source = "CircuitPriorityHalflife in configuration";
- } else if (consensus && (halflife_ms = networkstatus_get_param(
- consensus, "CircuitPriorityHalflifeMsec",
- -1, -1, INT32_MAX)) >= 0) {
- halflife = ((double)halflife_ms)/1000.0;
- source = "CircuitPriorityHalflifeMsec in consensus";
- } else {
- halflife = EWMA_DEFAULT_HALFLIFE;
- source = "Default value";
- }
+ channel_t *chan = NULL;
+ or_circuit_t *or_circ = NULL;
+ circuitmux_t *cmux = NULL;
- if (halflife <= EPSILON) {
- /* The cell EWMA algorithm is disabled. */
- ewma_scale_factor = 0.1;
- ewma_enabled = 0;
- log_info(LD_OR,
- "Disabled cell_ewma algorithm because of value in %s",
- source);
- } else {
- /* convert halflife into halflife-per-tick. */
- halflife /= EWMA_TICK_LEN;
- /* compute per-tick scale factor. */
- ewma_scale_factor = exp( LOG_ONEHALF / halflife );
- ewma_enabled = 1;
- log_info(LD_OR,
- "Enabled cell_ewma algorithm because of value in %s; "
- "scale factor is %f per %d seconds",
- source, ewma_scale_factor, EWMA_TICK_LEN);
- }
-}
-
-/** Return the multiplier necessary to convert the value of a cell sent in
- * 'from_tick' to one sent in 'to_tick'. */
-static INLINE double
-get_scale_factor(unsigned from_tick, unsigned to_tick)
-{
- /* This math can wrap around, but that's okay: unsigned overflow is
- well-defined */
- int diff = (int)(to_tick - from_tick);
- return pow(ewma_scale_factor, diff);
-}
-
-/** Adjust the cell count of <b>ewma</b> so that it is scaled with respect to
- * <b>cur_tick</b> */
-static void
-scale_single_cell_ewma(cell_ewma_t *ewma, unsigned cur_tick)
-{
- double factor = get_scale_factor(ewma->last_adjusted_tick, cur_tick);
- ewma->cell_count *= factor;
- ewma->last_adjusted_tick = cur_tick;
-}
-
-/** Adjust the cell count of every active circuit on <b>conn</b> so
- * that they are scaled with respect to <b>cur_tick</b> */
-static void
-scale_active_circuits(or_connection_t *conn, unsigned cur_tick)
-{
-
- double factor = get_scale_factor(
- conn->active_circuit_pqueue_last_recalibrated,
- cur_tick);
- /** Ordinarily it isn't okay to change the value of an element in a heap,
- * but it's okay here, since we are preserving the order. */
- SMARTLIST_FOREACH(conn->active_circuit_pqueue, cell_ewma_t *, e, {
- tor_assert(e->last_adjusted_tick ==
- conn->active_circuit_pqueue_last_recalibrated);
- e->cell_count *= factor;
- e->last_adjusted_tick = cur_tick;
- });
- conn->active_circuit_pqueue_last_recalibrated = cur_tick;
-}
-
-/** Rescale <b>ewma</b> to the same scale as <b>conn</b>, and add it to
- * <b>conn</b>'s priority queue of active circuits */
-static void
-add_cell_ewma_to_conn(or_connection_t *conn, cell_ewma_t *ewma)
-{
- tor_assert(ewma->heap_index == -1);
- scale_single_cell_ewma(ewma,
- conn->active_circuit_pqueue_last_recalibrated);
-
- smartlist_pqueue_add(conn->active_circuit_pqueue,
- compare_cell_ewma_counts,
- STRUCT_OFFSET(cell_ewma_t, heap_index),
- ewma);
-}
-
-/** Remove <b>ewma</b> from <b>conn</b>'s priority queue of active circuits */
-static void
-remove_cell_ewma_from_conn(or_connection_t *conn, cell_ewma_t *ewma)
-{
- tor_assert(ewma->heap_index != -1);
- smartlist_pqueue_remove(conn->active_circuit_pqueue,
- compare_cell_ewma_counts,
- STRUCT_OFFSET(cell_ewma_t, heap_index),
- ewma);
-}
-
-/** Remove and return the first cell_ewma_t from conn's priority queue of
- * active circuits. Requires that the priority queue is nonempty. */
-static cell_ewma_t *
-pop_first_cell_ewma_from_conn(or_connection_t *conn)
-{
- return smartlist_pqueue_pop(conn->active_circuit_pqueue,
- compare_cell_ewma_counts,
- STRUCT_OFFSET(cell_ewma_t, heap_index));
-}
-
-/** Add <b>circ</b> to the list of circuits with pending cells on
- * <b>conn</b>. No effect if <b>circ</b> is already linked. */
-void
-make_circuit_active_on_conn(circuit_t *circ, or_connection_t *conn)
-{
- circuit_t **nextp = next_circ_on_conn_p(circ, conn);
- circuit_t **prevp = prev_circ_on_conn_p(circ, conn);
-
- if (*nextp && *prevp) {
- /* Already active. */
- return;
- }
-
- assert_active_circuits_ok_paranoid(conn);
+ tor_assert(circ);
- if (! conn->active_circuits) {
- conn->active_circuits = circ;
- *prevp = *nextp = circ;
+ /* Okay, get the channel */
+ if (direction == CELL_DIRECTION_OUT) {
+ chan = circ->n_chan;
} else {
- circuit_t *head = conn->active_circuits;
- circuit_t *old_tail = *prev_circ_on_conn_p(head, conn);
- *next_circ_on_conn_p(old_tail, conn) = circ;
- *nextp = head;
- *prev_circ_on_conn_p(head, conn) = circ;
- *prevp = old_tail;
+ or_circ = TO_OR_CIRCUIT(circ);
+ chan = or_circ->p_chan;
}
- if (circ->n_conn == conn) {
- add_cell_ewma_to_conn(conn, &circ->n_cell_ewma);
- } else {
- or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
- tor_assert(conn == orcirc->p_conn);
- add_cell_ewma_to_conn(conn, &orcirc->p_cell_ewma);
- }
+ tor_assert(chan);
+ tor_assert(chan->cmux);
- assert_active_circuits_ok_paranoid(conn);
-}
+ /* Now get the cmux */
+ cmux = chan->cmux;
-/** Remove <b>circ</b> from the list of circuits with pending cells on
- * <b>conn</b>. No effect if <b>circ</b> is already unlinked. */
-void
-make_circuit_inactive_on_conn(circuit_t *circ, or_connection_t *conn)
-{
- circuit_t **nextp = next_circ_on_conn_p(circ, conn);
- circuit_t **prevp = prev_circ_on_conn_p(circ, conn);
- circuit_t *next = *nextp, *prev = *prevp;
-
- if (!next && !prev) {
- /* Already inactive. */
+ /* Cmux sanity check */
+ if (! circuitmux_is_circuit_attached(cmux, circ)) {
+ log_warn(LD_BUG, "called on non-attachd circuit from %s:%d",
+ file, lineno);
return;
}
+ tor_assert(circuitmux_attached_circuit_direction(cmux, circ) == direction);
- assert_active_circuits_ok_paranoid(conn);
-
- tor_assert(next && prev);
- tor_assert(*prev_circ_on_conn_p(next, conn) == circ);
- tor_assert(*next_circ_on_conn_p(prev, conn) == circ);
+ assert_cmux_ok_paranoid(chan);
- if (next == circ) {
- conn->active_circuits = NULL;
- } else {
- *prev_circ_on_conn_p(next, conn) = prev;
- *next_circ_on_conn_p(prev, conn) = next;
- if (conn->active_circuits == circ)
- conn->active_circuits = next;
- }
- *prevp = *nextp = NULL;
-
- if (circ->n_conn == conn) {
- remove_cell_ewma_from_conn(conn, &circ->n_cell_ewma);
+ /* Update the number of cells we have for the circuit mux */
+ if (direction == CELL_DIRECTION_OUT) {
+ circuitmux_set_num_cells(cmux, circ, circ->n_chan_cells.n);
} else {
- or_circuit_t *orcirc = TO_OR_CIRCUIT(circ);
- tor_assert(conn == orcirc->p_conn);
- remove_cell_ewma_from_conn(conn, &orcirc->p_cell_ewma);
+ circuitmux_set_num_cells(cmux, circ, or_circ->p_chan_cells.n);
}
- assert_active_circuits_ok_paranoid(conn);
+ assert_cmux_ok_paranoid(chan);
}
-/** Remove all circuits from the list of circuits with pending cells on
- * <b>conn</b>. */
+/** Remove all circuits from the cmux on <b>chan</b>. */
void
-connection_or_unlink_all_active_circs(or_connection_t *orconn)
+channel_unlink_all_circuits(channel_t *chan)
{
- circuit_t *head = orconn->active_circuits;
- circuit_t *cur = head;
- if (! head)
- return;
- do {
- circuit_t *next = *next_circ_on_conn_p(cur, orconn);
- *prev_circ_on_conn_p(cur, orconn) = NULL;
- *next_circ_on_conn_p(cur, orconn) = NULL;
- cur = next;
- } while (cur != head);
- orconn->active_circuits = NULL;
-
- SMARTLIST_FOREACH(orconn->active_circuit_pqueue, cell_ewma_t *, e,
- e->heap_index = -1);
- smartlist_clear(orconn->active_circuit_pqueue);
+ tor_assert(chan);
+ tor_assert(chan->cmux);
+
+ circuitmux_detach_all_circuits(chan->cmux);
+ chan->num_n_circuits = 0;
+ chan->num_p_circuits = 0;
}
/** Block (if <b>block</b> is true) or unblock (if <b>block</b> is false)
@@@ -2511,8 -2595,14 +2534,14 @@@ append_cell_to_circuit_queue(circuit_t
}
#endif
- cell_queue_append_packed_copy(queue, cell);
+ cell_queue_append_packed_copy(queue, cell, chan->wide_circ_ids);
+ if (PREDICT_UNLIKELY(cell_queues_check_size())) {
+ /* We ran the OOM handler */
+ if (circ->marked_for_close)
+ return;
+ }
+
/* If we have too many cells on the circuit, we should stop reading from
* the edge streams for a while. */
if (!streams_blocked && queue->n >= CELL_QUEUE_HIGHWATER_SIZE)
diff --cc src/or/relay.h
index 229fb4f,c55813b..1fef10a
--- a/src/or/relay.h
+++ b/src/or/relay.h
@@@ -46,25 -40,21 +46,26 @@@ void init_cell_pool(void)
void free_cell_pool(void);
void clean_cell_pool(void);
void dump_cell_pool_usage(int severity);
+ size_t packed_cell_mem_cost(void);
+/* For channeltls.c */
+void packed_cell_free(packed_cell_t *cell);
+
void cell_queue_clear(cell_queue_t *queue);
void cell_queue_append(cell_queue_t *queue, packed_cell_t *cell);
-void cell_queue_append_packed_copy(cell_queue_t *queue, const cell_t *cell);
+void cell_queue_append_packed_copy(cell_queue_t *queue, const cell_t *cell,
+ int wide_circ_ids);
-void append_cell_to_circuit_queue(circuit_t *circ, or_connection_t *orconn,
+void append_cell_to_circuit_queue(circuit_t *circ, channel_t *chan,
cell_t *cell, cell_direction_t direction,
streamid_t fromstream);
-void connection_or_unlink_all_active_circs(or_connection_t *conn);
-int connection_or_flush_from_first_active_circuit(or_connection_t *conn,
- int max, time_t now);
-void assert_active_circuits_ok(or_connection_t *orconn);
-void make_circuit_inactive_on_conn(circuit_t *circ, or_connection_t *conn);
-void make_circuit_active_on_conn(circuit_t *circ, or_connection_t *conn);
+void channel_unlink_all_circuits(channel_t *chan);
+int channel_flush_from_first_active_circuit(channel_t *chan, int max);
+void assert_circuit_mux_okay(channel_t *chan);
+void update_circuit_on_cmux_(circuit_t *circ, cell_direction_t direction,
+ const char *file, int lineno);
+#define update_circuit_on_cmux(circ, direction) \
+ update_circuit_on_cmux_((circ), (direction), SHORT_FILE__, __LINE__)
int append_address_to_payload(uint8_t *payload_out, const tor_addr_t *addr);
const uint8_t *decode_address_from_payload(tor_addr_t *addr_out,
