commit c2f6064325af710b309ec6f1a7c920eddc97e028 Author: pulls tobias.pulls@kau.se Date: Mon Jul 8 16:53:29 2019 +0200

Improve circpad documentation.

Patch by Tobias Pulls. --- src/core/or/circuitpadding.c | 40 ++++++++++++++++++++++++---------------- src/core/or/circuitpadding.h | 21 +++++++++++---------- 2 files changed, 35 insertions(+), 26 deletions(-)

diff --git a/src/core/or/circuitpadding.c b/src/core/or/circuitpadding.c index 017ef7b6b..911794861 100644 --- a/src/core/or/circuitpadding.c +++ b/src/core/or/circuitpadding.c @@ -17,7 +17,7 @@ * Each padding type is described by a state machine (circpad_machine_spec_t), * which is also referred as a "padding machine" in this file. Currently, * these state machines are hardcoded in the source code (e.g. see - * circpad_circ_client_machine_init()), but in the future we will be able to + * circpad_machines_init()), but in the future we will be able to * serialize them in the torrc or the consensus. * * As specified by prop#254, clients can negotiate padding with relays by using @@ -552,11 +552,12 @@ circpad_distribution_sample_iat_delay(const circpad_state_t *state, }

/** - * Sample an expected time-until-next-packet delay from the histogram. + * Sample an expected time-until-next-packet delay from the histogram or + * probability distribution. * - * The bin is chosen with probability proportional to the number - * of tokens in each bin, and then a time value is chosen uniformly from - * that bin's [start,end) time range. + * A bin of the histogram is chosen with probability proportional to the number + * of tokens in each bin, and then a time value is chosen uniformly from that + * bin's [start,end) time range. */ STATIC circpad_delay_t circpad_machine_sample_delay(circpad_machine_runtime_t *mi) @@ -655,12 +656,7 @@ circpad_machine_sample_delay(circpad_machine_runtime_t *mi) /** * Sample a value from the specified probability distribution. * - * This performs inverse transform sampling - * (https://en.wikipedia.org/wiki/Inverse_transform_sampling). - * - * XXX: These formulas were taken verbatim. Need a floating wizard - * to check them for catastropic cancellation and other issues (teor?). - * Also: is 32bits of double from [0.0,1.0) enough? + * Uses functions from src/lib/math/prob_distr.c . */ static double circpad_distribution_sample(circpad_distribution_t dist) @@ -744,6 +740,8 @@ circpad_distribution_sample(circpad_distribution_t dist) /** * Find the index of the first bin whose upper bound is * greater than the target, and that has tokens remaining. + * + * Used for histograms with token removal. */ static circpad_hist_index_t circpad_machine_first_higher_index(const circpad_machine_runtime_t *mi, @@ -766,6 +764,8 @@ circpad_machine_first_higher_index(const circpad_machine_runtime_t *mi, /** * Find the index of the first bin whose lower bound is lower or equal to * <b>target_bin_usec</b>, and that still has tokens remaining. + * + * Used for histograms with token removal. */ static circpad_hist_index_t circpad_machine_first_lower_index(const circpad_machine_runtime_t *mi, @@ -787,6 +787,8 @@ circpad_machine_first_lower_index(const circpad_machine_runtime_t *mi, /** * Remove a token from the first non-empty bin whose upper bound is * greater than the target. + * + * Used for histograms with token removal. */ STATIC void circpad_machine_remove_higher_token(circpad_machine_runtime_t *mi, @@ -808,6 +810,8 @@ circpad_machine_remove_higher_token(circpad_machine_runtime_t *mi, /** * Remove a token from the first non-empty bin whose upper bound is * lower than the target. + * + * Used for histograms with token removal. */ STATIC void circpad_machine_remove_lower_token(circpad_machine_runtime_t *mi, @@ -837,6 +841,8 @@ circpad_machine_remove_lower_token(circpad_machine_runtime_t *mi, * midpoint. * * If it is false, use bin index distance only. + * + * Used for histograms with token removal. */ STATIC void circpad_machine_remove_closest_token(circpad_machine_runtime_t *mi, @@ -919,6 +925,8 @@ circpad_machine_remove_closest_token(circpad_machine_runtime_t *mi, * Remove a token from the exact bin corresponding to the target. * * If it is empty, do nothing. + * + * Used for histograms with token removal. */ static void circpad_machine_remove_exact(circpad_machine_runtime_t *mi, @@ -1352,7 +1360,7 @@ circpad_machine_reached_padding_limit(circpad_machine_runtime_t *mi)

/* If circpad_max_global_padding_pct is non-zero, and we've * sent more than the global padding cell limit, then check our - * gloabl tor process percentage limit on padding. */ + * global tor process percentage limit on padding. */ if (circpad_global_max_padding_percent && circpad_global_padding_sent >= circpad_global_allowed_cells) { uint64_t total_cells = circpad_global_padding_sent + @@ -1492,7 +1500,7 @@ circpad_machine_schedule_padding,(circpad_machine_runtime_t *mi)) /** * If the machine transitioned to the END state, we need * to check to see if it wants us to shut it down immediately. - * If it does, then we need to send the appropate negotation commands + * If it does, then we need to send the appropiate negotiation commands * depending on which side it is. * * After this function is called, mi may point to freed memory. Do @@ -1509,7 +1517,7 @@ circpad_machine_spec_transitioned_to_end(circpad_machine_runtime_t *mi) * we can handle the case where this machine started while it was * the only machine that matched conditions, but *since* then more * "higher ranking" machines now match the conditions, and would - * be given a chance to take precidence over this one in + * be given a chance to take precedence over this one in * circpad_add_matching_machines(). * * Returning to START or waiting forever in END would not give those @@ -1636,7 +1644,7 @@ circpad_estimate_circ_rtt_on_received(circuit_t *circ, if (CIRCUIT_IS_ORIGIN(circ) || mi->stop_rtt_update) return;

- /* If we already have a last receieved packet time, that means we + /* If we already have a last received packet time, that means we * did not get a response before this packet. The RTT estimate * only makes sense if we do not have multiple packets on the * wire, so stop estimating if this is the second packet @@ -2300,7 +2308,7 @@ circpad_deliver_sent_relay_cell_events(circuit_t *circ, /* Optimization: The event for RELAY_COMMAND_DROP is sent directly * from circpad_send_padding_cell_for_callback(). This is to avoid * putting a cell_t and a relay_header_t on the stack repeatedly - * if we decide to send a long train of padidng cells back-to-back + * if we decide to send a long train of padding cells back-to-back * with 0 delay. So we do nothing here. */ return; } else { diff --git a/src/core/or/circuitpadding.h b/src/core/or/circuitpadding.h index 3cf40e11d..fc2e595c0 100644 --- a/src/core/or/circuitpadding.h +++ b/src/core/or/circuitpadding.h @@ -51,7 +51,7 @@ typedef enum { CIRCPAD_EVENT_INFINITY = 4, /* All histogram bins are empty (we are out of tokens) */ CIRCPAD_EVENT_BINS_EMPTY = 5, - /* just a counter of the events above */ + /* This state has used up its cell count */ CIRCPAD_EVENT_LENGTH_COUNT = 6 } circpad_event_t; #define CIRCPAD_NUM_EVENTS ((int)CIRCPAD_EVENT_LENGTH_COUNT+1) @@ -79,7 +79,7 @@ typedef uint32_t circpad_delay_t; * An infinite padding cell delay means don't schedule any padding -- * simply wait until a different event triggers a transition. * - * This means that the maximum delay we can scedule is UINT32_MAX-1 + * This means that the maximum delay we can schedule is UINT32_MAX-1 * microseconds, or about 4300 seconds (1.25 hours). * XXX: Is this enough if we want to simulate light, intermittent * activity on an onion service? @@ -106,8 +106,8 @@ typedef uint32_t circpad_delay_t; * * If any of these elements is set, then the circuit will be tested against * that specific condition. If an element is unset, then we don't test it. - * (E.g. If neither NO_STREAMS or STREAMS are set, then we will not care - * whether a circuit has streams attached when we apply a state machine) + * (E.g., if neither NO_STREAMS or STREAMS are set, then we will not care + * whether a circuit has streams attached when we apply a state machine.) * * The helper function circpad_circuit_state() converts circuit state * flags into this more compact representation. @@ -255,8 +255,9 @@ typedef struct circpad_distribution_t { typedef uint16_t circpad_statenum_t; #define CIRCPAD_STATENUM_MAX (UINT16_MAX)

-/** A histogram is used to sample padding delays given a machine state. This - * constant defines the maximum histogram width (i.e. the max number of bins). +/** A histogram can be used to sample padding delays given a machine state. + * This constant defines the maximum histogram width (i.e. the max number of + * bins). * * The current limit is arbitrary and could be raised if there is a need, * however too many bins will be hard to serialize in the future. @@ -275,10 +276,10 @@ typedef uint16_t circpad_statenum_t; * happen. The mutable information that gets updated in runtime are carried in * a circpad_machine_runtime_t. * - * This struct describes the histograms and parameters of a single - * state in the adaptive padding machine. Instances of this struct - * exist in global circpad machine definitions that come from torrc - * or the consensus. + * This struct describes the histograms and/or probability distributions, as + * well as parameters of a single state in the adaptive padding machine. + * Instances of this struct exist in global circpad machine definitions that + * come from torrc or the consensus. */ typedef struct circpad_state_t { /**