tor  0.4.2.0-alpha-dev
circuitpadding.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2017-2019, The Tor Project, Inc. */
3 /* See LICENSE for licensing information */
4 
10 #ifndef TOR_CIRCUITPADDING_H
11 #define TOR_CIRCUITPADDING_H
12 
13 #include "trunnel/circpad_negotiation.h"
14 #include "lib/evloop/timers.h"
15 
16 struct circuit_t;
17 struct origin_circuit_t;
18 struct cell_t;
19 
28 typedef int signed_error_t;
29 
40 typedef enum {
41  /* A non-padding cell was received. */
42  CIRCPAD_EVENT_NONPADDING_RECV = 0,
43  /* A non-padding cell was sent. */
44  CIRCPAD_EVENT_NONPADDING_SENT = 1,
45  /* A padding cell (RELAY_COMMAND_DROP) was sent. */
46  CIRCPAD_EVENT_PADDING_SENT = 2,
47  /* A padding cell was received. */
48  CIRCPAD_EVENT_PADDING_RECV = 3,
49  /* We tried to schedule padding but we ended up picking the infinity bin
50  * which means that padding was delayed infinitely */
51  CIRCPAD_EVENT_INFINITY = 4,
52  /* All histogram bins are empty (we are out of tokens) */
53  CIRCPAD_EVENT_BINS_EMPTY = 5,
54  /* This state has used up its cell count */
55  CIRCPAD_EVENT_LENGTH_COUNT = 6
57 #define CIRCPAD_NUM_EVENTS ((int)CIRCPAD_EVENT_LENGTH_COUNT+1)
58 
60 typedef enum {
61  CIRCPAD_STATE_UNCHANGED = 0,
62  CIRCPAD_STATE_CHANGED = 1
64 
66 typedef uint32_t circpad_hist_token_t;
67 
69 typedef int8_t circpad_hist_index_t;
70 
72 typedef uint64_t circpad_time_t;
73 
75 typedef uint32_t circpad_delay_t;
76 #define CIRCPAD_DELAY_UNITS_PER_SECOND (1000*1000)
77 
87 #define CIRCPAD_DELAY_INFINITE (UINT32_MAX)
88 
93 #define CIRCPAD_DELAY_MAX_SECS \
94  ((CIRCPAD_DELAY_INFINITE/CIRCPAD_DELAY_UNITS_PER_SECOND)+1)
95 
101 #define CIRCPAD_INFINITY_BIN(mi) ((mi)->histogram_len-1)
102 
115 typedef enum {
116  /* Only apply machine if the circuit is still building */
117  CIRCPAD_CIRC_BUILDING = 1<<0,
118  /* Only apply machine if the circuit is open */
119  CIRCPAD_CIRC_OPENED = 1<<1,
120  /* Only apply machine if the circuit has no attached streams */
121  CIRCPAD_CIRC_NO_STREAMS = 1<<2,
122  /* Only apply machine if the circuit has attached streams */
123  CIRCPAD_CIRC_STREAMS = 1<<3,
124  /* Only apply machine if the circuit still allows RELAY_EARLY cells */
125  CIRCPAD_CIRC_HAS_RELAY_EARLY = 1<<4,
126  /* Only apply machine if the circuit has depleted its RELAY_EARLY cells
127  * allowance. */
128  CIRCPAD_CIRC_HAS_NO_RELAY_EARLY = 1<<5
130 
132 #define CIRCPAD_STATE_ALL \
133  (CIRCPAD_CIRC_BUILDING|CIRCPAD_CIRC_OPENED| \
134  CIRCPAD_CIRC_STREAMS|CIRCPAD_CIRC_NO_STREAMS| \
135  CIRCPAD_CIRC_HAS_RELAY_EARLY|CIRCPAD_CIRC_HAS_NO_RELAY_EARLY)
136 
144 typedef uint32_t circpad_purpose_mask_t;
145 
147 #define CIRCPAD_PURPOSE_ALL (0xFFFFFFFF)
148 
158  unsigned min_hops : 3;
159 
161  unsigned requires_vanguards : 1;
162 
172  unsigned reduced_padding_ok : 1;
173 
177 
181 
183 
195 typedef enum {
213 
223 typedef enum {
224  /* No probability distribution is used */
225  CIRCPAD_DIST_NONE = 0,
226  /* Uniform distribution: param1 is lower bound and param2 is upper bound */
227  CIRCPAD_DIST_UNIFORM = 1,
228  /* Logistic distribution: param1 is Mu, param2 is sigma. */
229  CIRCPAD_DIST_LOGISTIC = 2,
230  /* Log-logistic distribution: param1 is Alpha, param2 is 1.0/Beta */
231  CIRCPAD_DIST_LOG_LOGISTIC = 3,
232  /* Geometric distribution: param1 is 'p' (success probability) */
233  CIRCPAD_DIST_GEOMETRIC = 4,
234  /* Weibull distribution: param1 is k, param2 is Lambda */
235  CIRCPAD_DIST_WEIBULL = 5,
236  /* Generalized Pareto distribution: param1 is sigma, param2 is xi */
237  CIRCPAD_DIST_PARETO = 6
239 
248 typedef struct circpad_distribution_t {
250  double param1;
251  double param2;
253 
255 typedef uint16_t circpad_statenum_t;
256 #define CIRCPAD_STATENUM_MAX (UINT16_MAX)
257 
271 #define CIRCPAD_MAX_HISTOGRAM_LEN (100)
272 
284 typedef struct circpad_state_t {
326  /* The histogram bin edges in usec.
327  *
328  * Each element of this array specifies the left edge of the corresponding
329  * bin. The rightmost edge is always infinity and is not specified in this
330  * array.
331  *
332  * This array must have histogram_len elements. */
333  circpad_delay_t histogram_edges[CIRCPAD_MAX_HISTOGRAM_LEN+1];
338 
351  /* If a delay probability distribution is used, this is used as the max
352  * value we can sample from the distribution. However, RTT measurements and
353  * dist_added_shift gets applied on top of this value to derive the final
354  * padding delay. */
355  circpad_delay_t dist_max_sample_usec;
356  /* If a delay probability distribution is used and this is set, we will add
357  * this value on top of the value sampled from the IAT distribution to
358  * derive the final padding delay (We also add the RTT measurement if it's
359  * enabled.). */
360  circpad_delay_t dist_added_shift_usec;
361 
372  uint16_t start_length;
374  uint64_t max_length;
375 
380 
394  circpad_statenum_t next_state[CIRCPAD_NUM_EVENTS];
395 
402  unsigned use_rtt_estimate : 1;
403 
408 
418 #define CIRCPAD_STATE_START 0
419 
438 #define CIRCPAD_STATE_BURST 1
439 
453 #define CIRCPAD_STATE_GAP 2
454 
462 #define CIRCPAD_STATE_END CIRCPAD_STATENUM_MAX
463 
470 #define CIRCPAD_STATE_IGNORE (CIRCPAD_STATENUM_MAX-1)
471 
478 #define CIRCPAD_STATE_CANCEL (CIRCPAD_STATENUM_MAX-2)
479 
484 #define CIRCPAD_MAX_MACHINE_STATES (CIRCPAD_STATE_CANCEL-1)
485 
506  tor_timer_t *padding_timer;
507 
510 
523 
525  uint64_t state_length;
526 #define CIRCPAD_STATE_LENGTH_INFINITE UINT64_MAX
527 
530  uint16_t padding_sent;
534  uint16_t nonpadding_sent;
535 
543 
548 
555 
564 
567 
576 
581  unsigned stop_rtt_update : 1;
582 
585 #define CIRCPAD_MAX_MACHINES (2)
586 
589  unsigned machine_index : 1;
590 
592 
594 #define CIRCPAD_GET_MACHINE(machineinfo) \
595  ((machineinfo)->on_circ->padding_machine[(machineinfo)->machine_index])
596 
603 typedef uint8_t circpad_machine_num_t;
604 
606 typedef struct circpad_machine_spec_t {
607  /* Just a user-friendly machine name for logs */
608  const char *name;
609 
612 
615  unsigned machine_index : 1;
616 
618  unsigned should_negotiate_end : 1;
619 
620  // These next three fields are origin machine-only...
622  unsigned is_origin_side : 1;
623 
626  unsigned target_hopnum : 3;
627 
639  unsigned manage_circ_lifetime : 1;
640 
643 
648 
654 
657 
663 
665 
666 int circpad_marked_circuit_for_padding(circuit_t *circ, int reason);
667 
672  cell_direction_t dir);
674  uint8_t relay_command);
676  uint8_t relay_command,
677  crypt_path_t *layer_hint);
678 
680 void circpad_cell_event_nonpadding_sent(struct circuit_t *on_circ);
682 void circpad_cell_event_padding_sent(struct circuit_t *on_circ);
683 void circpad_cell_event_padding_received(struct circuit_t *on_circ);
684 
692 
700 void
702 
703 void circpad_machines_init(void);
704 void circpad_machines_free(void);
705 void circpad_register_padding_machine(circpad_machine_spec_t *machine,
706  smartlist_t *machine_list);
707 
709  circpad_statenum_t num_states);
710 
712 
714  crypt_path_t *from_hop);
715 
718 const circpad_machine_spec_t *circpad_string_to_machine(const char *str);
719 
720 /* Padding negotiation between client and middle */
722  struct cell_t *cell);
724  struct cell_t *cell,
725  crypt_path_t *layer_hint);
727  circpad_machine_num_t machine,
728  uint8_t target_hopnum,
729  uint8_t command);
730 bool circpad_padding_negotiated(struct circuit_t *circ,
731  circpad_machine_num_t machine,
732  uint8_t command,
733  uint8_t response);
734 
736 
738  crypt_path_t *layer_hint,
739  const relay_header_t *rh);
740 
742 circpad_machine_schedule_padding,(circpad_machine_runtime_t *));
743 
745 circpad_machine_spec_transition, (circpad_machine_runtime_t *mi,
746  circpad_event_t event));
747 
750 
751 void circpad_free_all(void);
752 
753 #ifdef CIRCUITPADDING_PRIVATE
755 #define machine_spec_free(chan) \
756  FREE_AND_NULL(circpad_machine_spec_t,machine_spec_free_, (m))
757 
758 STATIC circpad_delay_t
760 
761 STATIC bool
763 
764 STATIC circpad_delay_t
767 
768 STATIC const circpad_state_t *
770 
772 
774  const circpad_machine_runtime_t *mi,
775  circpad_delay_t us);
776 
778  struct circuit_t *on_circ,
779  int machine_index);
781  circpad_delay_t target_bin_us);
783  circpad_delay_t target_bin_us);
785  circpad_delay_t target_bin_us,
786  bool use_usec);
788 
790 circpad_send_command_to_hop,(struct origin_circuit_t *circ, uint8_t hopnum,
791  uint8_t relay_command, const uint8_t *payload,
792  ssize_t payload_len));
793 
794 MOCK_DECL(STATIC const node_t *,
795 circuit_get_nth_node,(origin_circuit_t *circ, int hop));
796 
797 STATIC circpad_delay_t
800 
801 STATIC void
803  smartlist_t *machines_sl);
804 
805 #ifdef TOR_UNIT_TESTS
808 
809 #endif
810 
811 #endif /* defined(CIRCUITPADDING_PRIVATE) */
812 
813 #endif /* !defined(TOR_CIRCUITPADDING_H) */
struct circpad_machine_runtime_t circpad_machine_runtime_t
void circpad_machine_event_circ_built(struct origin_circuit_t *circ)
STATIC circpad_machine_runtime_t * circpad_circuit_machineinfo_new(circuit_t *on_circ, int machine_index)
circpad_decision_t
int circpad_marked_circuit_for_padding(circuit_t *circ, int reason)
struct circpad_machine_conditions_t circpad_machine_conditions_t
Definition: node_st.h:28
uint32_t circpad_delay_t
STATIC void machine_spec_free_(circpad_machine_spec_t *m)
void circpad_machine_event_circ_added_hop(struct origin_circuit_t *on_circ)
uint64_t circpad_time_t
void circpad_free_all(void)
circpad_distribution_type_t
circpad_removal_t
uint16_t start_length
int signed_error_t
Definition: cell_st.h:12
circpad_state_t * states
circpad_statenum_t current_state
circpad_removal_t token_removal
void circpad_machine_event_circ_has_no_relay_early(struct origin_circuit_t *circ)
circpad_purpose_mask_t circpad_circ_purpose_to_mask(uint8_t circ_purpose)
bool circpad_padding_negotiated(struct circuit_t *circ, circpad_machine_num_t machine, uint8_t command, uint8_t response)
void circpad_circuit_free_all_machineinfos(struct circuit_t *circ)
circpad_delay_t rtt_estimate_usec
void circpad_cell_event_padding_sent(struct circuit_t *on_circ)
STATIC void circpad_machine_remove_token(circpad_machine_runtime_t *mi)
void circpad_machines_free(void)
void circpad_cell_event_nonpadding_received(struct circuit_t *on_circ)
STATIC smartlist_t * relay_padding_machines
void circpad_deliver_sent_relay_cell_events(struct circuit_t *circ, uint8_t relay_command)
circpad_hist_index_t chosen_bin
STATIC circpad_delay_t circpad_machine_sample_delay(circpad_machine_runtime_t *mi)
cell_direction_t
Definition: or.h:482
STATIC void circpad_add_matching_machines(origin_circuit_t *on_circ, smartlist_t *machines_sl)
STATIC bool circpad_machine_reached_padding_limit(circpad_machine_runtime_t *mi)
STATIC void circpad_machine_remove_lower_token(circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec)
uint32_t circpad_hist_token_t
void circpad_deliver_unrecognized_cell_events(struct circuit_t *circ, cell_direction_t dir)
STATIC circpad_hist_index_t circpad_histogram_usec_to_bin(const circpad_machine_runtime_t *mi, circpad_delay_t usec)
STATIC void circpad_machine_remove_closest_token(circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec, bool use_usec)
circpad_hist_index_t histogram_len
STATIC void circpad_machine_remove_higher_token(circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec)
void circpad_machine_event_circ_purpose_changed(struct origin_circuit_t *circ)
circpad_decision_t circpad_internal_event_bins_empty(circpad_machine_runtime_t *)
circpad_statenum_t next_state[CIRCPAD_NUM_EVENTS]
unsigned use_rtt_estimate
circpad_decision_t circpad_internal_event_infinity(circpad_machine_runtime_t *mi)
uint32_t circpad_purpose_mask_t
circpad_decision_t circpad_send_padding_cell_for_callback(circpad_machine_runtime_t *mi)
circpad_time_t padding_scheduled_at_usec
void circpad_cell_event_nonpadding_sent(struct circuit_t *on_circ)
STATIC circpad_delay_t histogram_get_bin_upper_bound(const circpad_machine_runtime_t *mi, circpad_hist_index_t bin)
circpad_distribution_t length_dist
circpad_time_t last_received_time_usec
void circpad_machines_init(void)
struct circpad_distribution_t circpad_distribution_t
void circpad_machine_event_circ_has_no_streams(struct origin_circuit_t *circ)
#define CIRCPAD_MAX_HISTOGRAM_LEN
circpad_decision_t circpad_internal_event_state_length_up(circpad_machine_runtime_t *)
uint16_t circpad_statenum_t
void circpad_machine_event_circ_has_streams(struct origin_circuit_t *circ)
unsigned length_includes_nonpadding
STATIC void circpad_machine_setup_tokens(circpad_machine_runtime_t *mi)
void circpad_new_consensus_params(const networkstatus_t *ns)
circpad_machine_conditions_t conditions
circpad_purpose_mask_t purpose_mask
STATIC circpad_delay_t circpad_histogram_bin_to_usec(const circpad_machine_runtime_t *mi, circpad_hist_index_t bin)
Header for timers.c.
circpad_hist_index_t histogram_len
circpad_circuit_state_t
circpad_hist_token_t histogram[CIRCPAD_MAX_HISTOGRAM_LEN]
circpad_circuit_state_t state_mask
circpad_distribution_t iat_dist
struct circuit_t * on_circ
circpad_statenum_t num_states
char * circpad_machine_spec_to_string(const circpad_machine_spec_t *machine)
bool circpad_padding_is_from_expected_hop(struct circuit_t *circ, crypt_path_t *from_hop)
struct circpad_machine_spec_t circpad_machine_spec_t
signed_error_t circpad_handle_padding_negotiate(struct circuit_t *circ, struct cell_t *cell)
#define MOCK_DECL(rv, funcname, arglist)
Definition: testsupport.h:94
circpad_machine_num_t machine_num
STATIC smartlist_t * origin_padding_machines
int circpad_check_received_cell(cell_t *cell, circuit_t *circ, crypt_path_t *layer_hint, const relay_header_t *rh)
void circpad_deliver_recognized_relay_cell_events(struct circuit_t *circ, uint8_t relay_command, crypt_path_t *layer_hint)
void circpad_cell_event_padding_received(struct circuit_t *on_circ)
uint32_t histogram_total_tokens
signed_error_t circpad_negotiate_padding(struct origin_circuit_t *circ, circpad_machine_num_t machine, uint8_t target_hopnum, uint8_t command)
circpad_hist_token_t * histogram
circpad_event_t
void circpad_machine_states_init(circpad_machine_spec_t *machine, circpad_statenum_t num_states)
struct circpad_state_t circpad_state_t
int8_t circpad_hist_index_t
uint8_t circpad_machine_num_t
STATIC const circpad_state_t * circpad_machine_current_state(const circpad_machine_runtime_t *mi)
signed_error_t circpad_handle_padding_negotiated(struct circuit_t *circ, struct cell_t *cell, crypt_path_t *layer_hint)