commit d3063da691d0006cf41f6406099f056ab47c543a Merge: 9e45d94 c37fdc2 Author: Nick Mathewson nickm@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,