March 2019 - tor-commits - lists.torproject.org

[tor/master] histogram_edges is histogram_len long
by nickm＠torproject.org 13 Mar '19

13 Mar '19

commit 341cd6ea6631217a5487198a773b56a057afd5f9 Author: George Kadianakis <desnacked(a)riseup.net> Date: Mon Feb 25 13:28:35 2019 +0200 histogram_edges is histogram_len long --- src/core/or/circuitpadding.c | 1 - src/core/or/circuitpadding.h | 2 +- src/test/test_circuitpadding.c | 2 -- 3 files changed, 1 insertion(+), 4 deletions(-) diff --git a/src/core/or/circuitpadding.c b/src/core/or/circuitpadding.c index ceb9181f9..09dda6da3 100644 --- a/src/core/or/circuitpadding.c +++ b/src/core/or/circuitpadding.c @@ -2185,7 +2185,6 @@ circpad_circ_responder_machine_init(void) circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_edges[3]= 4000; circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_edges[4]= 8000; circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_edges[5]= 16000; - circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_edges[6]=1000000; /* Specify histogram tokens */ circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram[0] = 0; circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram[1] = 1; diff --git a/src/core/or/circuitpadding.h b/src/core/or/circuitpadding.h index b9e903b9f..d11358a15 100644 --- a/src/core/or/circuitpadding.h +++ b/src/core/or/circuitpadding.h @@ -290,7 +290,7 @@ typedef struct circpad_state_t { * bin. The rightmost edge is always infinity and is not specified in this * array. * - * This array must have histogram_len+1 elements. */ + * This array must have histogram_len elements. */ circpad_delay_t histogram_edges[CIRCPAD_MAX_HISTOGRAM_LEN+1]; /** Total number of tokens in this histogram. This is a constant and is *not* * decremented every time we spend a token. It's used for initializing and diff --git a/src/test/test_circuitpadding.c b/src/test/test_circuitpadding.c index 65bf529e4..599b7fb24 100644 --- a/src/test/test_circuitpadding.c +++ b/src/test/test_circuitpadding.c @@ -425,8 +425,6 @@ helper_create_basic_machine(void) circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[2] = 5000; circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[3] = 10000; circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[4] = 20000; - circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[5] = 400000; - circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[6] = 1000000; circ_client_machine.states[CIRCPAD_STATE_BURST].histogram[0] = 1; circ_client_machine.states[CIRCPAD_STATE_BURST].histogram[1] = 0;

1 0

[tor/master] document picking infinity bin
by nickm＠torproject.org 13 Mar '19

13 Mar '19

commit 71c11d7306dbbcb81c780a7a786429e2d8eaa669 Author: George Kadianakis <desnacked(a)riseup.net> Date: Mon Feb 25 13:59:18 2019 +0200 document picking infinity bin --- src/core/or/circuitpadding.c | 4 ++++ src/core/or/circuitpadding.h | 6 ++++++ 2 files changed, 10 insertions(+) diff --git a/src/core/or/circuitpadding.c b/src/core/or/circuitpadding.c index 7e76cd7ad..29a618930 100644 --- a/src/core/or/circuitpadding.c +++ b/src/core/or/circuitpadding.c @@ -224,6 +224,10 @@ circpad_machine_current_state(const circpad_machine_state_t *mi) /** * Get the lower bound of a histogram bin. The upper bound is obtained by * calling this function with bin+1, and subtracting 1. + * + * This function can also be called with 'bin' set to a value equal or greater + * than histogram_len in which case the infinity bin is chosen and + * CIRCPAD_DELAY_INFINITE is returned. */ STATIC circpad_delay_t circpad_histogram_bin_to_usec(const circpad_machine_state_t *mi, diff --git a/src/core/or/circuitpadding.h b/src/core/or/circuitpadding.h index 4e6454b4a..ca19e31ca 100644 --- a/src/core/or/circuitpadding.h +++ b/src/core/or/circuitpadding.h @@ -276,6 +276,12 @@ typedef struct circpad_state_t { * histogram[] = { 6, 10, 6, 7, 9, 6 } * histogram_edges[] = { 0, 100, 200, 350, 500, 1000 } * + * The final bin is called the "infinity bin" and if it's chosen we don't + * schedule any padding. The infinity bin is strange because its lower edge + * is the max value of possible non-infinite delay allowed by this histogram, + * and its upper edge is CIRCPAD_DELAY_INFINITE. You can tell if the infinity + * bin is chosen by inspecting its bin index or inspecting its upper edge. + * * If a delay probability distribution is used for this state, this is set * to 0. */ circpad_hist_index_t histogram_len;

1 0

[tor/master] Fix dist_min_usec documentation and naming.
by nickm＠torproject.org 13 Mar '19

13 Mar '19

commit 331a067ae3ce778037650d5283504350979e50ee Author: George Kadianakis <desnacked(a)riseup.net> Date: Mon Feb 25 13:46:58 2019 +0200 Fix dist_min_usec documentation and naming. --- src/core/or/circuitpadding.c | 13 +++++++------ src/core/or/circuitpadding.h | 15 +++++++++------ src/test/test_circuitpadding.c | 24 ++++++++++++------------ 3 files changed, 28 insertions(+), 24 deletions(-) diff --git a/src/core/or/circuitpadding.c b/src/core/or/circuitpadding.c index 09dda6da3..7e76cd7ad 100644 --- a/src/core/or/circuitpadding.c +++ b/src/core/or/circuitpadding.c @@ -380,17 +380,17 @@ circpad_choose_state_length(circpad_machine_state_t *mi) */ static circpad_delay_t circpad_distribution_sample_iat_delay(const circpad_state_t *state, - circpad_delay_t min_delay) + circpad_delay_t delay_shift) { double val = circpad_distribution_sample(state->iat_dist); /* These comparisons are safe, because the output is in the range * [0, 2**32), and double has a precision of 53 bits. */ val = MAX(0, val); - val = MIN(val, state->dist_max_usec); + val = MIN(val, state->dist_max_sample_usec); /* This addition is exact: val is at most 2**32-1, min_delay * is at most 2**32-1, and doubles have a precision of 53 bits. */ - val += min_delay; + val += delay_shift; /* Clamp the distribution at infinite delay val */ return (circpad_delay_t)MIN(tor_llround(val), CIRCPAD_DELAY_INFINITE); @@ -420,9 +420,10 @@ circpad_machine_sample_delay(circpad_machine_state_t *mi) if (state->iat_dist.type != CIRCPAD_DIST_NONE) { /* Sample from a fixed IAT distribution and return */ - circpad_delay_t min_iat_delay = state->use_rtt_estimate ? - mi->rtt_estimate_usec + state->dist_min_usec : state->dist_min_usec; - return circpad_distribution_sample_iat_delay(state, min_iat_delay); + circpad_delay_t iat_delay_shift = state->use_rtt_estimate ? + mi->rtt_estimate_usec + state->dist_added_shift_usec : + state->dist_added_shift_usec; + return circpad_distribution_sample_iat_delay(state, iat_delay_shift); } else if (state->token_removal != CIRCPAD_TOKEN_REMOVAL_NONE) { /* We have a mutable histogram. Do basic sanity check and apply: */ if (BUG(!mi->histogram) || diff --git a/src/core/or/circuitpadding.h b/src/core/or/circuitpadding.h index d11358a15..4e6454b4a 100644 --- a/src/core/or/circuitpadding.h +++ b/src/core/or/circuitpadding.h @@ -309,13 +309,16 @@ typedef struct circpad_state_t { * results of sampling from this distribution (range_sec is used as a max). */ circpad_distribution_t iat_dist; - /* If a delay probability distribution is used, this represents the minimum - * delay we can sample from the distribution. */ - circpad_delay_t dist_min_usec; /* If a delay probability distribution is used, this is used as the max - * delay we can sample from the distribution. - */ - circpad_delay_t dist_max_usec; + * value we can sample from the distribution. However, RTT measurements and + * dist_added_shift gets applied on top of this value to derive the final + * padding delay. */ + circpad_delay_t dist_max_sample_usec; + /* If a delay probability distribution is used and this is set, we will add + * this value on top of the value sampled from the IAT distribution to + * derive the final padding delay (We also add the RTT measurement if it's + * enabled.). */ + circpad_delay_t dist_added_shift_usec; /** * The length dist is a parameterized way of encoding how long this diff --git a/src/test/test_circuitpadding.c b/src/test/test_circuitpadding.c index 599b7fb24..3570b179b 100644 --- a/src/test/test_circuitpadding.c +++ b/src/test/test_circuitpadding.c @@ -2098,48 +2098,48 @@ helper_circpad_circ_distribution_machine_setup(int min, int max) zero_st->iat_dist.type = CIRCPAD_DIST_UNIFORM; zero_st->iat_dist.param1 = min; zero_st->iat_dist.param2 = max; - zero_st->dist_min_usec = min; - zero_st->dist_max_usec = max; + zero_st->dist_added_shift_usec = min; + zero_st->dist_max_sample_usec = max; circpad_state_t *first_st = &circ_client_machine.states[1]; first_st->next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 2; first_st->iat_dist.type = CIRCPAD_DIST_LOGISTIC; first_st->iat_dist.param1 = min; first_st->iat_dist.param2 = max; - first_st->dist_min_usec = min; - first_st->dist_max_usec = max; + first_st->dist_added_shift_usec = min; + first_st->dist_max_sample_usec = max; circpad_state_t *second_st = &circ_client_machine.states[2]; second_st->next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 3; second_st->iat_dist.type = CIRCPAD_DIST_LOG_LOGISTIC; second_st->iat_dist.param1 = min; second_st->iat_dist.param2 = max; - second_st->dist_min_usec = min; - second_st->dist_max_usec = max; + second_st->dist_added_shift_usec = min; + second_st->dist_max_sample_usec = max; circpad_state_t *third_st = &circ_client_machine.states[3]; third_st->next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 4; third_st->iat_dist.type = CIRCPAD_DIST_GEOMETRIC; third_st->iat_dist.param1 = min; third_st->iat_dist.param2 = max; - third_st->dist_min_usec = min; - third_st->dist_max_usec = max; + third_st->dist_added_shift_usec = min; + third_st->dist_max_sample_usec = max; circpad_state_t *fourth_st = &circ_client_machine.states[4]; fourth_st->next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 5; fourth_st->iat_dist.type = CIRCPAD_DIST_WEIBULL; fourth_st->iat_dist.param1 = min; fourth_st->iat_dist.param2 = max; - fourth_st->dist_min_usec = min; - fourth_st->dist_max_usec = max; + fourth_st->dist_added_shift_usec = min; + fourth_st->dist_max_sample_usec = max; circpad_state_t *fifth_st = &circ_client_machine.states[5]; fifth_st->next_state[CIRCPAD_EVENT_NONPADDING_RECV] = 6; fifth_st->iat_dist.type = CIRCPAD_DIST_PARETO; fifth_st->iat_dist.param1 = min; fifth_st->iat_dist.param2 = max; - fifth_st->dist_min_usec = min; - fifth_st->dist_max_usec = max; + fifth_st->dist_added_shift_usec = min; + fifth_st->dist_max_sample_usec = max; } /** Simple test that the padding delays sampled from a uniform distribution

1 0

[tor/master] Switch an int32_t bin to a circpad_hist_index_t.
by nickm＠torproject.org 13 Mar '19

13 Mar '19

commit 18de065cbbcd9863842fc7f773033f295a0000dc Author: George Kadianakis <desnacked(a)riseup.net> Date: Mon Feb 25 14:01:55 2019 +0200 Switch an int32_t bin to a circpad_hist_index_t. --- src/core/or/circuitpadding.c | 2 +- src/core/or/circuitpadding.h | 3 +++ 2 files changed, 4 insertions(+), 1 deletion(-) diff --git a/src/core/or/circuitpadding.c b/src/core/or/circuitpadding.c index 29a618930..b7e4b5684 100644 --- a/src/core/or/circuitpadding.c +++ b/src/core/or/circuitpadding.c @@ -293,7 +293,7 @@ circpad_histogram_usec_to_bin(const circpad_machine_state_t *mi, { const circpad_state_t *state = circpad_machine_current_state(mi); circpad_delay_t rtt_add_usec = 0; - int32_t bin; + circpad_hist_index_t bin; /* Our state should have been checked to be non-null by the caller * (circpad_machine_remove_token()) */ diff --git a/src/core/or/circuitpadding.h b/src/core/or/circuitpadding.h index ca19e31ca..74f9f35c9 100644 --- a/src/core/or/circuitpadding.h +++ b/src/core/or/circuitpadding.h @@ -235,6 +235,9 @@ typedef uint16_t circpad_statenum_t; * * Memory concerns are not so great here since the corresponding histogram and * histogram_edges arrays are global and not per-circuit. + * + * If we ever upgrade this to a value that can't be represented by 8-bits we + * also need to upgrade circpad_hist_index_t. */ #define CIRCPAD_MAX_HISTOGRAM_LEN (100)

1 0

[tor/master] circpad: Machines MUST have strictly increasing histogram edges.
by nickm＠torproject.org 13 Mar '19

13 Mar '19

commit cdaff26f91ff6e3dceca6054157bbcf976713398 Author: George Kadianakis <desnacked(a)riseup.net> Date: Wed Mar 13 13:21:52 2019 +0200 circpad: Machines MUST have strictly increasing histogram edges. Add a basic validation function for the histograms. It can be a building block for the future --- src/core/or/circuitpadding.c | 98 +++++++++++++++++++++++++++++++++++++----- src/core/or/circuitpadding.h | 6 ++- src/test/test_circuitpadding.c | 15 +++---- 3 files changed, 99 insertions(+), 20 deletions(-) diff --git a/src/core/or/circuitpadding.c b/src/core/or/circuitpadding.c index 106bb4ffa..2ee233cc5 100644 --- a/src/core/or/circuitpadding.c +++ b/src/core/or/circuitpadding.c @@ -494,12 +494,13 @@ circpad_machine_sample_delay(circpad_machine_state_t *mi) * function below samples from [bin_start, bin_end) */ bin_end = circpad_histogram_bin_to_usec(mi, curr_bin+1); - // Sample uniformly between histogram[i] to histogram[i+1]-1, - // but no need to sample if they are the same timeval (aka bin 0 or bin 1). - if (bin_end <= bin_start+1) + /* Bin edges are monotonically increasing so this is a bug. Handle it. */ + if (BUG(bin_start > bin_end)) { return bin_start; - else - return (circpad_delay_t)crypto_rand_uint64_range(bin_start, bin_end); + } + + /* Sample randomly from within the bin width */ + return (circpad_delay_t)crypto_rand_uint64_range(bin_start, bin_end); } /** @@ -2050,16 +2051,92 @@ circpad_setup_machine_on_circ(circuit_t *on_circ, on_circ->padding_machine[machine->machine_index] = machine; } -/* These padding machines are only used for tests pending #28634. */ #ifdef TOR_UNIT_TESTS +/** Validate a single state of a padding machine */ +static bool +padding_machine_state_is_valid(const circpad_state_t *state) +{ + int b; + uint32_t tokens_count = 0; + circpad_delay_t prev_bin_edge = 0; + + /* We only validate histograms */ + if (!state->histogram_len) { + return true; + } + + /* We need at least two bins in a histogram */ + if (state->histogram_len < 2) { + log_warn(LD_GENERAL, "You can't have a histogram with less than 2 bins"); + return false; + } + + /* For each machine state, if it's a histogram, make sure all the + * histogram edges are well defined (i.e. are strictly monotonic). */ + for (b = 0 ; b < state->histogram_len ; b++) { + /* Check that histogram edges are strictly increasing. Ignore the first + * edge since it can be zero. */ + if (prev_bin_edge >= state->histogram_edges[b] && b > 0) { + log_warn(LD_GENERAL, "Histogram edges are not increasing [%u/%u]", + prev_bin_edge, state->histogram_edges[b]); + return false; + } + + prev_bin_edge = state->histogram_edges[b]; + + /* Also count the number of tokens as we go through the histogram states */ + tokens_count += state->histogram[b]; + } + /* Verify that the total number of tokens is correct */ + if (tokens_count != state->histogram_total_tokens) { + log_warn(LD_GENERAL, "Histogram token count is wrong [%u/%u]", + tokens_count, state->histogram_total_tokens); + return false; + } + + return true; +} + +/** Basic validation of padding machine */ +static bool +padding_machine_is_valid(const circpad_machine_spec_t *machine) +{ + int i; + + /* Validate the histograms of the padding machine */ + for (i = 0 ; i < machine->num_states ; i++) { + if (!padding_machine_state_is_valid(&machine->states[i])) { + return false; + } + } + + return true; +} + +/* Validate and register machine into machine_list. If + * machine_list is NULL, then just validate. */ +STATIC void +register_padding_machine(circpad_machine_spec_t *machine, + smartlist_t *machine_list) +{ + if (!padding_machine_is_valid(machine)) { + log_warn(LD_GENERAL, "Machine #%u is invalid. Ignoring.", + machine->machine_num); + return; + } + + if (machine_list) { + smartlist_add(machine_list, machine); + } +} + +/* These padding machines are only used for tests pending #28634. */ static void circpad_circ_client_machine_init(void) { circpad_machine_spec_t *circ_client_machine = tor_malloc_zero(sizeof(circpad_machine_spec_t)); - // XXX: Better conditions for merge.. Or disable this machine in - // merge? circ_client_machine->conditions.min_hops = 2; circ_client_machine->conditions.state_mask = CIRCPAD_CIRC_BUILDING|CIRCPAD_CIRC_OPENED|CIRCPAD_CIRC_HAS_RELAY_EARLY; @@ -2091,7 +2168,6 @@ circpad_circ_client_machine_init(void) circ_client_machine->states[CIRCPAD_STATE_BURST].token_removal = CIRCPAD_TOKEN_REMOVAL_CLOSEST; - // FIXME: Tune this histogram circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_len = 2; circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_edges[0]= 500; circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_edges[1]= 1000000; @@ -2105,7 +2181,7 @@ circpad_circ_client_machine_init(void) circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_total_tokens = 5; circ_client_machine->machine_num = smartlist_len(origin_padding_machines); - smartlist_add(origin_padding_machines, circ_client_machine); + register_padding_machine(circ_client_machine, origin_padding_machines); } static void @@ -2205,7 +2281,7 @@ circpad_circ_responder_machine_init(void) CIRCPAD_TOKEN_REMOVAL_CLOSEST_USEC; circ_responder_machine->machine_num = smartlist_len(relay_padding_machines); - smartlist_add(relay_padding_machines, circ_responder_machine); + register_padding_machine(circ_responder_machine, relay_padding_machines); } #endif diff --git a/src/core/or/circuitpadding.h b/src/core/or/circuitpadding.h index 2c763f46e..54039fa59 100644 --- a/src/core/or/circuitpadding.h +++ b/src/core/or/circuitpadding.h @@ -291,7 +291,7 @@ typedef struct circpad_state_t { /** The histogram itself: an array of uint16s of tokens, whose * widths are exponentially spaced, in microseconds. * - * This array must have histogram_len elements that are (non-strictly) + * This array must have histogram_len elements that are strictly * monotonically increasing. */ circpad_hist_token_t histogram[CIRCPAD_MAX_HISTOGRAM_LEN]; /* The histogram bin edges in usec. @@ -730,6 +730,10 @@ histogram_get_bin_upper_bound(const circpad_machine_state_t *mi, #ifdef TOR_UNIT_TESTS extern smartlist_t *origin_padding_machines; extern smartlist_t *relay_padding_machines; + +STATIC void +register_padding_machine(circpad_machine_spec_t *machine, + smartlist_t *machine_list); #endif #endif diff --git a/src/test/test_circuitpadding.c b/src/test/test_circuitpadding.c index 3570b179b..a62b2b516 100644 --- a/src/test/test_circuitpadding.c +++ b/src/test/test_circuitpadding.c @@ -794,7 +794,7 @@ test_circuitpadding_closest_token_removal(void *arg) tt_int_op(client_side->padding_info[0]->current_state, OP_EQ, CIRCPAD_STATE_BURST); circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[0] = 100; - circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[1] = 100; + circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[1] = 101; circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[2] = 120; mi->padding_scheduled_at_usec = current_time - 102; mi->histogram[0] = 0; @@ -903,7 +903,7 @@ test_circuitpadding_closest_token_removal_usec(void *arg) tt_int_op(client_side->padding_info[0]->current_state, OP_EQ, CIRCPAD_STATE_BURST); circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[0] = 100; - circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[1] = 100; + circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[1] = 101; circ_client_machine.states[CIRCPAD_STATE_BURST].histogram_edges[2] = 120; mi->padding_scheduled_at_usec = current_time - 102; mi->histogram[0] = 0; @@ -1649,7 +1649,7 @@ helper_create_conditional_machine(void) ret->states[CIRCPAD_STATE_BURST].histogram_len = 3; ret->states[CIRCPAD_STATE_BURST].histogram_edges[0] = 0; - ret->states[CIRCPAD_STATE_BURST].histogram_edges[1] = 0; + ret->states[CIRCPAD_STATE_BURST].histogram_edges[1] = 1; ret->states[CIRCPAD_STATE_BURST].histogram_edges[2] = 1000000; ret->states[CIRCPAD_STATE_BURST].histogram[0] = 6; @@ -1686,8 +1686,7 @@ helper_create_conditional_machines(void) add->conditions.state_mask = CIRCPAD_CIRC_BUILDING| CIRCPAD_CIRC_NO_STREAMS|CIRCPAD_CIRC_HAS_RELAY_EARLY; add->conditions.purpose_mask = CIRCPAD_PURPOSE_ALL; - - smartlist_add(origin_padding_machines, add); + register_padding_machine(add, origin_padding_machines); add = helper_create_conditional_machine(); add->machine_num = 3; @@ -1706,15 +1705,15 @@ helper_create_conditional_machines(void) add->conditions.state_mask = CIRCPAD_CIRC_OPENED| CIRCPAD_CIRC_STREAMS|CIRCPAD_CIRC_HAS_NO_RELAY_EARLY; add->conditions.purpose_mask = CIRCPAD_PURPOSE_ALL; - smartlist_add(origin_padding_machines, add); + register_padding_machine(add, origin_padding_machines); add = helper_create_conditional_machine(); add->machine_num = 2; - smartlist_add(relay_padding_machines, add); + register_padding_machine(add, relay_padding_machines); add = helper_create_conditional_machine(); add->machine_num = 3; - smartlist_add(relay_padding_machines, add); + register_padding_machine(add, relay_padding_machines); } void

1 0

[tor/master] circpad: Documentation improvements after Nick's review.
by nickm＠torproject.org 13 Mar '19

13 Mar '19

commit 32c821c47b56471802a6c6c0f2286eb41d07238b Author: George Kadianakis <desnacked(a)riseup.net> Date: Tue Mar 12 18:38:55 2019 +0200 circpad: Documentation improvements after Nick's review. --- src/core/or/circuitpadding.c | 10 ++++++---- src/core/or/circuitpadding.h | 3 ++- 2 files changed, 8 insertions(+), 5 deletions(-) diff --git a/src/core/or/circuitpadding.c b/src/core/or/circuitpadding.c index b7e4b5684..106bb4ffa 100644 --- a/src/core/or/circuitpadding.c +++ b/src/core/or/circuitpadding.c @@ -222,8 +222,9 @@ circpad_machine_current_state(const circpad_machine_state_t *mi) } /** - * Get the lower bound of a histogram bin. The upper bound is obtained by - * calling this function with bin+1, and subtracting 1. + * Get the lower bound of a histogram bin. + * + * You can obtain the upper bound using histogram_get_bin_upper_bound(). * * This function can also be called with 'bin' set to a value equal or greater * than histogram_len in which case the infinity bin is chosen and @@ -273,8 +274,7 @@ circpad_get_histogram_bin_midpoint(const circpad_machine_state_t *mi, int bin_index) { circpad_delay_t left_bound = circpad_histogram_bin_to_usec(mi, bin_index); - circpad_delay_t right_bound = - circpad_histogram_bin_to_usec(mi, bin_index+1)-1; + circpad_delay_t right_bound = histogram_get_bin_upper_bound(mi, bin_index); return left_bound + (right_bound - left_bound)/2; } @@ -381,6 +381,8 @@ circpad_choose_state_length(circpad_machine_state_t *mi) /** * Sample a value from our iat_dist, and clamp it safely * to circpad_delay_t. + * + * Before returning, add delay_shift (can be zero) to the sampled value. */ static circpad_delay_t circpad_distribution_sample_iat_delay(const circpad_state_t *state, diff --git a/src/core/or/circuitpadding.h b/src/core/or/circuitpadding.h index 74f9f35c9..2c763f46e 100644 --- a/src/core/or/circuitpadding.h +++ b/src/core/or/circuitpadding.h @@ -291,7 +291,8 @@ typedef struct circpad_state_t { /** The histogram itself: an array of uint16s of tokens, whose * widths are exponentially spaced, in microseconds. * - * This array must have histogram_len elements. */ + * This array must have histogram_len elements that are (non-strictly) + * monotonically increasing. */ circpad_hist_token_t histogram[CIRCPAD_MAX_HISTOGRAM_LEN]; /* The histogram bin edges in usec. *

1 0

[tor/master] Merge remote-tracking branch 'tor-github/pr/705'
by nickm＠torproject.org 13 Mar '19

13 Mar '19

commit 58fd864a85fc58650ac7c7c48a68f7a49de38260 Merge: 17ff69a26 cdaff26f9 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Mar 13 09:36:47 2019 -0400 Merge remote-tracking branch 'tor-github/pr/705' changes/bug29298 | 6 + src/core/or/circuitpadding.c | 258 ++++++++++++++++++++++++++--------------- src/core/or/circuitpadding.h | 103 +++++++++++----- src/test/test_circuitpadding.c | 138 +++++++++++++--------- 4 files changed, 326 insertions(+), 179 deletions(-)

1 0

[tor/master] Improve #include counting func and move it to metrics.py.
by nickm＠torproject.org 13 Mar '19

13 Mar '19

commit 371ea65c080471cb6e1a57d9f78e5beaaa4212b8 Author: George Kadianakis <desnacked(a)riseup.net> Date: Wed Feb 27 17:05:00 2019 +0200 Improve #include counting func and move it to metrics.py. --- scripts/maint/practracker/metrics.py | 8 ++++++++ scripts/maint/practracker/practracker.py | 5 +---- 2 files changed, 9 insertions(+), 4 deletions(-) diff --git a/scripts/maint/practracker/metrics.py b/scripts/maint/practracker/metrics.py index 43ec3f809..525a05840 100644 --- a/scripts/maint/practracker/metrics.py +++ b/scripts/maint/practracker/metrics.py @@ -8,6 +8,14 @@ def file_len(f): pass return i + 1 +def get_include_count(f): + """Get number of #include statements in the file""" + include_count = 0 + for line in f: + if re.match(r' *# *include', line): + include_count += 1 + return include_count + def function_lines(f): """ Return iterator which iterates over functions and returns (function name, function lines) diff --git a/scripts/maint/practracker/practracker.py b/scripts/maint/practracker/practracker.py index c95c432c3..c3b8a9783 100755 --- a/scripts/maint/practracker/practracker.py +++ b/scripts/maint/practracker/practracker.py @@ -57,10 +57,7 @@ def consider_file_size(fname, f, exceptions_str): print_violation_if_not_exception(violation_str, exceptions_str) def consider_includes(fname, f, exceptions_str): - include_count = 0 - for _, line in enumerate(f): - if line.startswith("#include "): - include_count += 1 + include_count = metrics.get_include_count(f) if include_count > MAX_INCLUDE_COUNT: violation_str = "violation include-count %s %d" % (fname, include_count)

1 0

[tor/master] Improve metrics implementation.
by nickm＠torproject.org 13 Mar '19

13 Mar '19

commit 2a722e2841c9b1631852affd313cc3d0403da7b9 Author: George Kadianakis <desnacked(a)riseup.net> Date: Wed Feb 27 19:29:27 2019 +0200 Improve metrics implementation. No longer messes up with MOCK_IMPL. Also update the tests to show that. We are still being innacurate on the line count in some cases, but that doesnt matter so much. --- scripts/maint/practracker/metrics.py | 17 ++++++++++++++--- scripts/maint/practracker/practracker_tests.py | 4 ++++ 2 files changed, 18 insertions(+), 3 deletions(-) diff --git a/scripts/maint/practracker/metrics.py b/scripts/maint/practracker/metrics.py index 525a05840..c7d2091d0 100644 --- a/scripts/maint/practracker/metrics.py +++ b/scripts/maint/practracker/metrics.py @@ -1,8 +1,12 @@ #!/usr/bin/python +# Implementation of various source code metrics. +# These are currently ad-hoc string operations and regexps. +# We might want to use a proper static analysis library in the future, if we want to get more advanced metrics. + import re -def file_len(f): +def get_file_len(f): """Get file length of file""" for i, l in enumerate(f): pass @@ -16,14 +20,20 @@ def get_include_count(f): include_count += 1 return include_count -def function_lines(f): +def get_function_lines(f): """ Return iterator which iterates over functions and returns (function name, function lines) """ - # XXX Buggy! Doesn't work with MOCK_IMPL and ENABLE_GCC_WARNINGS + # Skip lines with these terms since they confuse our regexp + REGEXP_CONFUSE_TERMS = ["MOCK_IMPL", "ENABLE_GCC_WARNINGS", "ENABLE_GCC_WARNING", "DUMMY_TYPECHECK_INSTANCE", + "DISABLE_GCC_WARNING", "DISABLE_GCC_WARNINGS"] + in_function = False for lineno, line in enumerate(f): + if any(x in line for x in REGEXP_CONFUSE_TERMS): + continue + if not in_function: # find the start of a function m = re.match(r'^([a-zA-Z_][a-zA-Z_0-9]*),?\(', line) @@ -31,6 +41,7 @@ def function_lines(f): func_name = m.group(1) func_start = lineno in_function = True + else: # Fund the end of a function if line.startswith("}"): diff --git a/scripts/maint/practracker/practracker_tests.py b/scripts/maint/practracker/practracker_tests.py index f3d225207..cdbab2908 100755 --- a/scripts/maint/practracker/practracker_tests.py +++ b/scripts/maint/practracker/practracker_tests.py @@ -40,6 +40,10 @@ class TestFunctionLength(unittest.TestCase): # All functions should have length 2 for name, lines in metrics.function_lines(funcs): self.assertEqual(name, "fun") + + funcs.seek(0) + + for name, lines in metrics.function_lines(funcs): self.assertEqual(lines, 2) if __name__ == '__main__':

1 0

[tor/master] Add more intelligent problem tracking.
by nickm＠torproject.org 13 Mar '19

13 Mar '19

commit 26c4f6cfd07fea6d49109e60a8b591b92ec59c49 Author: George Kadianakis <desnacked(a)riseup.net> Date: Wed Feb 27 18:24:10 2019 +0200 Add more intelligent problem tracking. --- scripts/maint/practracker/practracker.py | 55 +++++++++--------- scripts/maint/practracker/problem.py | 96 ++++++++++++++++++++++++++++++++ 2 files changed, 123 insertions(+), 28 deletions(-) diff --git a/scripts/maint/practracker/practracker.py b/scripts/maint/practracker/practracker.py index c3b8a9783..4fbca615c 100755 --- a/scripts/maint/practracker/practracker.py +++ b/scripts/maint/practracker/practracker.py @@ -5,7 +5,7 @@ Tor code best-practices tracker Go through the various .c files and collect metrics about them. If the metrics violate some of our best practices and they are not found in the optional -exceptions file ("./exceptions.txt"), then log a violation about them. +exceptions file ("./exceptions.txt"), then log a problem about them. The exceptions file is meant to be initialized with the current state of the source code as follows: ./practracker.py > ./exceptions.txt @@ -22,6 +22,7 @@ import os, sys import metrics import util +import problem # We don't want to run metrics for unittests, automatically-generated C files, # external libraries or git leftovers. @@ -41,76 +42,74 @@ MAX_INCLUDE_COUNT = 50 ####################################################### -def print_violation_if_not_exception(violation_str, exceptions_str): - # Check if this violation is already in the optional exceptions file - if exceptions_str and violation_str in exceptions_str: - return - - print violation_str +ProblemVault = None ####################################################### -def consider_file_size(fname, f, exceptions_str): +def consider_file_size(fname, f): file_size = metrics.file_len(f) if file_size > MAX_FILE_SIZE: - violation_str = "violation file-size %s %d" % (fname, file_size) - print_violation_if_not_exception(violation_str, exceptions_str) + v = problem.FileSizeProblem(fname, file_size) + ProblemVault.register_problem(v) -def consider_includes(fname, f, exceptions_str): +def consider_includes(fname, f): include_count = metrics.get_include_count(f) if include_count > MAX_INCLUDE_COUNT: - violation_str = "violation include-count %s %d" % (fname, include_count) - print_violation_if_not_exception(violation_str, exceptions_str) + v = problem.IncludeCountProblem(fname, include_count) + ProblemVault.register_problem(v) -def consider_function_size(fname, f, exceptions_str): +def consider_function_size(fname, f): for name, lines in metrics.function_lines(f): # Don't worry about functions within our limits if lines <= MAX_FUNCTION_SIZE: continue - # That's a big function! Issue a violation! + # That's a big function! Issue a problem! canonical_function_name = "%s:%s()" % (fname,name) - violation_str = "violation function-size %s %s" % (lines, canonical_function_name) - print_violation_if_not_exception(violation_str, exceptions_str) + v = problem.FunctionSizeProblem(canonical_function_name, lines) + ProblemVault.register_problem(v) ####################################################### -def consider_all_metrics(files_list, exceptions_str): +def consider_all_metrics(files_list): """Consider metrics for all files""" for fname in files_list: with open(fname, 'r') as f: - consider_metrics_for_file(fname, f, exceptions_str) + consider_metrics_for_file(fname, f) -def consider_metrics_for_file(fname, f, exceptions_str): +def consider_metrics_for_file(fname, f): """ Get metrics for file with filename 'fname' and file descriptor 'f'. """ # Get file length - consider_file_size(fname, f, exceptions_str) + consider_file_size(fname, f) # Consider number of #includes f.seek(0) - consider_includes(fname, f, exceptions_str) + consider_includes(fname, f) # Get function length f.seek(0) - consider_function_size(fname, f, exceptions_str) + consider_function_size(fname, f) def main(): + global ProblemVault + # 1) Get all the .c files we care about files_list = util.get_tor_c_files(TOR_TOPDIR, EXCLUDE_SOURCE_DIRS) - # 2) Read an optional exceptions file so that we don't warn about the past - exceptions_str = None + # 2) Initialize problem vault and load an optional exceptions file so that + # we don't warn about the past try: with open(EXCEPTIONS_FILE, 'r') as exception_f: - exceptions_str = exception_f.read() + ProblemVault = problem.ProblemVault(exception_f) except IOError: print "No exception file provided" + ProblemVault = problem.ProblemVault(None) - # 3) Go through all the files and report violations if they are not exceptions - consider_all_metrics(files_list, exceptions_str) + # 3) Go through all the files and report problems if they are not exceptions + consider_all_metrics(files_list) if __name__ == '__main__': main() diff --git a/scripts/maint/practracker/problem.py b/scripts/maint/practracker/problem.py new file mode 100644 index 000000000..fe6b30915 --- /dev/null +++ b/scripts/maint/practracker/problem.py @@ -0,0 +1,96 @@ +""" +In this file we define a ProblemVault class where we store all the +exceptions and all the problems we find with the code. + +The ProblemVault is capable of registering problems and also figuring out if a +problem is worse than a registered exception so that it only warns when things +get worse. +""" + +class ProblemVault(object): + """ + Singleton where we store the various new problems we + found in the code, and also the old problems we read from the exception + file. + """ + def __init__(self, exception_file): + # Exception dictionary: { problem.key() : Problem object } + self.exceptions = {} + + if exception_file: + self.register_exceptions(exception_file) + + def register_exceptions(self, exception_file): + # Register exceptions + for line in exception_file: + problem = get_old_problem_from_exception_str(line) + if problem is None: + continue + + # XXX this might overwrite problems with the same key (e.g. MOCK_IMPL) + self.exceptions[problem.key()] = problem + #print "Registering exception: %s" % problem + + def register_problem(self, problem): + # This is a new problem, print it + if problem.key() not in self.exceptions: + print problem + return + + # If it's an old problem, we don't warn if the situation got better + # (e.g. we went from 4k LoC to 3k LoC), but we do warn if the + # situation worsened (e.g. we went from 60 includes to 80). + if problem.is_worse_than(self.exceptions[problem.key()]): + print problem + return +# else: +# print "OK %s better than %s" % (problem, self.exceptions[problem.key()]) + + +class Problem(object): + def __init__(self, problem_type, problem_location, metric_value): + self.problem_location = problem_location + self.metric_value = int(metric_value) + self.problem_type = problem_type + + def is_worse_than(self, other_problem): + """Return True if this is a worse problem than other_problem""" + if self.metric_value > other_problem.metric_value: + return True + return False + + def key(self): + """Generate a unique key that describes this problem that can be used as a dictionary key""" + return "%s:%s" % (self.problem_location, self.problem_type) + + def __str__(self): + return "problem %s %s %s" % (self.problem_type, self.problem_location, self.metric_value) + +class FileSizeProblem(Problem): + def __init__(self, problem_location, metric_value): + super(FileSizeProblem, self).__init__("file-size", problem_location, metric_value) + +class IncludeCountProblem(Problem): + def __init__(self, problem_location, metric_value): + super(IncludeCountProblem, self).__init__("include-count", problem_location, metric_value) + +class FunctionSizeProblem(Problem): + def __init__(self, problem_location, metric_value): + super(FunctionSizeProblem, self).__init__("function-size", problem_location, metric_value) + +def get_old_problem_from_exception_str(exception_str): + try: + _, problem_type, problem_location, metric_value = exception_str.split(" ") + except ValueError: + return None + + if problem_type == "file-size": + return FileSizeProblem(problem_location, metric_value) + elif problem_type == "include-count": + return IncludeCountProblem(problem_location, metric_value) + elif problem_type == "function-size": + return FunctionSizeProblem(problem_location, metric_value) + else: + print "Unknown exception line %s" % exception_str + return None +

1 0