commit 7a2b30fe16eacc040b3dd11f8c39c410628c2f43 Merge: 4aa9aff 59f50c8 Author: Nick Mathewson nickm@torproject.org Date: Fri Nov 15 15:35:00 2013 -0500

Merge remote-tracking branch 'origin/maint-0.2.4'

Conflicts: src/or/relay.c

Conflict changes were easy; compilation fixes required were using using TOR_SIMPLEQ_FIRST to get head of cell queue.

changes/bug9093 | 7 ++++++ src/common/util.c | 12 +++++++++++ src/common/util.h | 1 + src/or/circuitlist.c | 58 +++++++++++++++++++++++++++++++++++++++++--------- src/or/or.h | 5 +++++ src/or/relay.c | 7 +++++- 6 files changed, 79 insertions(+), 11 deletions(-)

diff --cc src/or/circuitlist.c index 19f4618,b0e24a5..c31bc49 --- a/src/or/circuitlist.c +++ b/src/or/circuitlist.c @@@ -1620,10 -1525,41 +1620,43 @@@ n_cells_in_circ_queues(const circuit_t return n; }

- /** helper to sort a list of circuit_q by total queue lengths, in descending - * order. */ + /** + * Return the age of the oldest cell queued on <b>c</b>, in milliseconds. + * Return 0 if there are no cells queued on c. Requires that <b>now</b> be + * the current time in milliseconds since the epoch, truncated. + * + * This function will return incorrect results if the oldest cell queued on + * the circuit is older than 2**32 msec (about 49 days) old. + */ + static uint32_t + circuit_max_queued_cell_age(const circuit_t *c, uint32_t now) + { + uint32_t age = 0; - if (c->n_chan_cells.head) - age = now - c->n_chan_cells.head->inserted_time; ++ packed_cell_t *cell; ++ ++ if (NULL != (cell = TOR_SIMPLEQ_FIRST(&c->n_chan_cells.head))) ++ age = now - cell->inserted_time; + + if (! CIRCUIT_IS_ORIGIN(c)) { + const or_circuit_t *orcirc = TO_OR_CIRCUIT((circuit_t*)c); - if (orcirc->p_chan_cells.head) { - uint32_t age2 = now - orcirc->p_chan_cells.head->inserted_time; ++ if (NULL != (cell = TOR_SIMPLEQ_FIRST(&orcirc->p_chan_cells.head))) { ++ uint32_t age2 = now - cell->inserted_time; + if (age2 > age) + return age2; + } + } + return age; + } + + /** Temporary variable for circuits_compare_by_oldest_queued_cell_ This is a + * kludge to work around the fact that qsort doesn't provide a way for + * comparison functions to take an extra argument. */ + static uint32_t circcomp_now_tmp; + + /** Helper to sort a list of circuit_t by age of oldest cell, in descending + * order. Requires that circcomp_now_tmp is set correctly. */ static int - circuits_compare_by_queue_len_(const void **a_, const void **b_) + circuits_compare_by_oldest_queued_cell_(const void **a_, const void **b_) { const circuit_t *a = *a_; const circuit_t *b = *b_; @@@ -1667,12 -1604,16 +1701,16 @@@ circuits_handle_oom(size_t current_allo

/* This algorithm itself assumes that you've got enough memory slack * to actually run it. */ - for (circ = global_circuitlist; circ; circ = circ->next) + TOR_LIST_FOREACH(circ, &global_circuitlist, head) smartlist_add(circlist, circ);

+ /* Set circcomp_now_tmp so that the sort can work. */ + tor_gettimeofday_cached(&now); + circcomp_now_tmp = (uint32_t)tv_to_msec(&now); + /* This is O(n log n); there are faster algorithms we could use instead. * Let's hope this doesn't happen enough to be in the critical path. */ - smartlist_sort(circlist, circuits_compare_by_queue_len_); + smartlist_sort(circlist, circuits_compare_by_oldest_queued_cell_);

/* Okay, now the worst circuits are at the front of the list. Let's mark * them, and reclaim their storage aggressively. */ diff --cc src/or/or.h index a313248,5318b0f..6b18f13 --- a/src/or/or.h +++ b/src/or/or.h @@@ -1108,20 -1073,17 +1108,25 @@@ typedef struct var_cell_t uint8_t payload[FLEXIBLE_ARRAY_MEMBER]; } var_cell_t;

+/** A parsed Extended ORPort message. */ +typedef struct ext_or_cmd_t { + uint16_t cmd; /** Command type */ + uint16_t len; /** Body length */ + char body[FLEXIBLE_ARRAY_MEMBER]; /** Message body */ +} ext_or_cmd_t; + /** A cell as packed for writing to the network. */ typedef struct packed_cell_t { - struct packed_cell_t *next; /**< Next cell queued on this circuit. */ + /** Next cell queued on this circuit. */ + TOR_SIMPLEQ_ENTRY(packed_cell_t) next; char body[CELL_MAX_NETWORK_SIZE]; /**< Cell as packed for network. */ + uint32_t inserted_time; /**< Time (in milliseconds since epoch, with high + * bits truncated) when this cell was inserted. */ } packed_cell_t;

+ /* XXXX This next structure may be obsoleted by inserted_time in + * packed_cell_t */ + /** Number of cells added to a circuit queue including their insertion * time on 10 millisecond detail; used for buffer statistics. */ typedef struct insertion_time_elem_t { diff --cc src/or/relay.c index 3600707,63119cb..0c9267a --- a/src/or/relay.c +++ b/src/or/relay.c @@@ -2149,75 -2133,30 +2149,80 @@@ packed_cell_copy(const cell_t *cell, in void cell_queue_append(cell_queue_t *queue, packed_cell_t *cell) { - if (queue->tail) { - tor_assert(!queue->tail->next); - queue->tail->next = cell; + TOR_SIMPLEQ_INSERT_TAIL(&queue->head, cell, next); + ++queue->n; +} + +/** Append command of type <b>command</b> in direction to <b>queue</b> for + * CELL_STATS event. */ +static void +cell_command_queue_append(cell_queue_t *queue, uint8_t command) +{ + insertion_command_queue_t *ic_queue = queue->insertion_commands; + if (!ic_pool) + ic_pool = mp_pool_new(sizeof(insertion_command_elem_t), 1024); + if (!ic_queue) { + ic_queue = tor_malloc_zero(sizeof(insertion_command_queue_t)); + queue->insertion_commands = ic_queue; + } + if (ic_queue->last && ic_queue->last->command == command) { + ic_queue->last->counter++; } else { - queue->head = cell; + insertion_command_elem_t *elem = mp_pool_get(ic_pool); + elem->next = NULL; + elem->command = command; + elem->counter = 1; + if (ic_queue->last) { + ic_queue->last->next = elem; + ic_queue->last = elem; + } else { + ic_queue->first = ic_queue->last = elem; + } } - queue->tail = cell; - cell->next = NULL; - ++queue->n; }

-/** Append a newly allocated copy of <b>cell</b> to the end of <b>queue</b> */ +/** Retrieve oldest command from <b>queue</b> and write it to + * <b>command</b> for CELL_STATS event. Return 0 for success, -1 + * otherwise. */ +static int +cell_command_queue_pop(uint8_t *command, cell_queue_t *queue) +{ + int res = -1; + insertion_command_queue_t *ic_queue = queue->insertion_commands; + if (ic_queue && ic_queue->first) { + insertion_command_elem_t *ic_elem = ic_queue->first; + ic_elem->counter--; + if (ic_elem->counter < 1) { + ic_queue->first = ic_elem->next; + if (ic_elem == ic_queue->last) + ic_queue->last = NULL; + mp_pool_release(ic_elem); + } + *command = ic_elem->command; + res = 0; + } + return res; +} + +/** Append a newly allocated copy of <b>cell</b> to the end of the + * <b>exitward</b> (or app-ward) <b>queue</b> of <b>circ</b>. If + * <b>use_stats</b> is true, record statistics about the cell. + */ void -cell_queue_append_packed_copy(cell_queue_t *queue, const cell_t *cell, - int wide_circ_ids) +cell_queue_append_packed_copy(circuit_t *circ, cell_queue_t *queue, + int exitward, const cell_t *cell, + int wide_circ_ids, int use_stats) { + struct timeval now; packed_cell_t *copy = packed_cell_copy(cell, wide_circ_ids); + tor_gettimeofday_cached(&now); + copy->inserted_time = (uint32_t)tv_to_msec(&now); + /* Remember the time when this cell was put in the queue. */ + /*XXXX This may be obsoleted by inserted_time */ - if (get_options()->CellStatistics) { + if ((get_options()->CellStatistics || + get_options()->TestingEnableCellStatsEvent) && use_stats) { + struct timeval now; uint32_t added; insertion_time_queue_t *it_queue = queue->insertion_times; if (!it_pool)