Tor  0.4.5.0-alpha-dev
circuitpadding.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2017-2020, The Tor Project, Inc. */
3 /* See LICENSE for licensing information */
4 
5 /**
6  * \file circuitpadding.h
7  * \brief Header file for circuitpadding.c.
8  **/
9 
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 
20 /**
21  * Signed error return with the specific property that negative
22  * values mean error codes of various semantics, 0 means success,
23  * and positive values are unused.
24  *
25  * XXX: Tor uses this concept a lot but just calls it int. Should we move
26  * this somewhere centralized? Where?
27  */
28 typedef int signed_error_t;
29 
30 /**
31  * These constants specify the types of events that can cause
32  * transitions between state machine states.
33  *
34  * Note that SENT and RECV are relative to this endpoint. For
35  * relays, SENT means packets destined towards the client and
36  * RECV means packets destined towards the relay. On the client,
37  * SENT means packets destined towards the relay, where as RECV
38  * means packets destined towards the client.
39  */
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 
59 /** Boolean type that says if we decided to transition states or not */
60 typedef enum {
61  CIRCPAD_STATE_UNCHANGED = 0,
62  CIRCPAD_STATE_CHANGED = 1
64 
65 /** The type for the things in histogram bins (aka tokens) */
66 typedef uint32_t circpad_hist_token_t;
67 
68 /** The type for histogram indexes (needs to be negative for errors) */
69 typedef int8_t circpad_hist_index_t;
70 
71 /** The type for absolute time, from monotime_absolute_usec() */
72 typedef uint64_t circpad_time_t;
73 
74 /** The type for timer delays, in microseconds */
75 typedef uint32_t circpad_delay_t;
76 #define CIRCPAD_DELAY_UNITS_PER_SECOND (1000*1000)
77 
78 /**
79  * An infinite padding cell delay means don't schedule any padding --
80  * simply wait until a different event triggers a transition.
81  *
82  * This means that the maximum delay we can schedule is UINT32_MAX-1
83  * microseconds, or about 4300 seconds (1.25 hours).
84  * XXX: Is this enough if we want to simulate light, intermittent
85  * activity on an onion service?
86  */
87 #define CIRCPAD_DELAY_INFINITE (UINT32_MAX)
88 
89 /**
90  * This is the maximum delay that the circuit padding system can have, in
91  * seconds.
92  */
93 #define CIRCPAD_DELAY_MAX_SECS \
94  ((CIRCPAD_DELAY_INFINITE/CIRCPAD_DELAY_UNITS_PER_SECOND)+1)
95 
96 /**
97  * Macro to clarify when we're checking the infinity bin.
98  *
99  * Works with either circpad_state_t or circpad_machine_runtime_t
100  */
101 #define CIRCPAD_INFINITY_BIN(mi) ((mi)->histogram_len-1)
102 
103 /**
104  * These constants form a bitfield that specifies when a state machine
105  * should be applied to a circuit.
106  *
107  * If any of these elements is set, then the circuit will be tested against
108  * that specific condition. If an element is unset, then we don't test it.
109  * (E.g., if neither NO_STREAMS or STREAMS are set, then we will not care
110  * whether a circuit has streams attached when we apply a state machine.)
111  *
112  * The helper function circpad_circuit_state() converts circuit state
113  * flags into this more compact representation.
114  */
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 
131 /** Bitmask that says "apply this machine to all states" */
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 
137 /**
138  * A compact circuit purpose bitfield mask that allows us to compactly
139  * specify which circuit purposes a machine should apply to.
140  *
141  * The helper function circpad_circ_purpose_to_mask() converts circuit
142  * purposes into bit positions in this bitmask.
143  */
144 typedef uint32_t circpad_purpose_mask_t;
145 
146 /** Bitmask that says "apply this machine to all purposes". */
147 #define CIRCPAD_PURPOSE_ALL (0xFFFFFFFF)
148 
149 /**
150  * This type specifies all of the conditions that must be met before
151  * a client decides to initiate padding on a circuit.
152  *
153  * A circuit must satisfy every sub-field in this type in order
154  * to be considered to match the conditions.
155  */
157  /** Only apply the machine *if* the circuit has at least this many hops */
158  unsigned min_hops : 3;
159 
160  /** Only apply the machine *if* vanguards are enabled */
161  unsigned requires_vanguards : 1;
162 
163  /**
164  * This machine is ok to use if reduced padding is set in consensus
165  * or torrc. This machine will still be applied even if reduced padding
166  * is not set; this flag only acts to exclude machines that don't have
167  * it set when reduced padding is requested. Therefore, reduced padding
168  * machines should appear at the lowest priority in the padding machine
169  * lists (aka first in the list), so that non-reduced padding machines
170  * for the same purpose are given a chance to apply when reduced padding
171  * is not requested. */
172  unsigned reduced_padding_ok : 1;
173 
174  /** Only apply the machine *if* the circuit's state matches any of
175  * the bits set in this bitmask. */
177 
178  /** Only apply a machine *if* the circuit's purpose matches one
179  * of the bits set in this bitmask */
181 
182  /** Keep a machine if any of the circuits's state machine's match
183  * the bits set in this bitmask, but don't apply new machines if
184  * they match this mask. */
186 
187  /** Keep a machine if any of the circuits's state machine's match
188  * the bits set in this bitmask, but don't apply new machines if
189  * they match this mask. */
191 
193 
194 /**
195  * Token removal strategy options.
196  *
197  * The WTF-PAD histograms are meant to specify a target distribution to shape
198  * traffic towards. This is accomplished by removing tokens from the histogram
199  * when either padding or non-padding cells are sent.
200  *
201  * When we see a non-padding cell at a particular time since the last cell, you
202  * remove a token from the corresponding delay bin. These flags specify
203  * which bin to choose if that bin is already empty.
204  */
205 typedef enum {
206  /** Don't remove any tokens */
208  /**
209  * Remove from the first non-zero higher bin index when current is zero.
210  * This is the recommended strategy from the Adaptive Padding paper. */
212  /** Remove from the first non-zero lower bin index when current is empty. */
214  /** Remove from the closest non-zero bin index when current is empty. */
216  /** Remove from the closest bin by time value (since bins are
217  * exponentially spaced). */
219  /** Only remove from the exact bin corresponding to this delay. If
220  * the bin is 0, simply do nothing. Don't pick another bin. */
223 
224 /**
225  * Distribution types supported by circpad_distribution_sample().
226  *
227  * These can be used instead of histograms for the inter-packet
228  * timing distribution, or to specify a distribution on the number
229  * of cells that can be sent while in a specific state of the state
230  * machine.
231  *
232  * Each distribution takes up to two parameters which are described below. */
233 typedef enum {
234  /* No probability distribution is used */
235  CIRCPAD_DIST_NONE = 0,
236  /* Uniform distribution: param1 is lower bound and param2 is upper bound */
237  CIRCPAD_DIST_UNIFORM = 1,
238  /* Logistic distribution: param1 is Mu, param2 is sigma. */
239  CIRCPAD_DIST_LOGISTIC = 2,
240  /* Log-logistic distribution: param1 is Alpha, param2 is 1.0/Beta */
241  CIRCPAD_DIST_LOG_LOGISTIC = 3,
242  /* Geometric distribution: param1 is 'p' (success probability) */
243  CIRCPAD_DIST_GEOMETRIC = 4,
244  /* Weibull distribution: param1 is k, param2 is Lambda */
245  CIRCPAD_DIST_WEIBULL = 5,
246  /* Generalized Pareto distribution: param1 is sigma, param2 is xi */
247  CIRCPAD_DIST_PARETO = 6
249 
250 /**
251  * Distribution information.
252  *
253  * This type specifies a specific distribution above, as well as
254  * up to two parameters for that distribution. The specific
255  * per-distribution meaning of these parameters is specified
256  * in circpad_distribution_sample().
257  */
258 typedef struct circpad_distribution_t {
260  double param1;
261  double param2;
263 
264 /** State number type. Represents current state of state machine. */
265 typedef uint16_t circpad_statenum_t;
266 #define CIRCPAD_STATENUM_MAX (UINT16_MAX)
267 
268 /** A histogram can be used to sample padding delays given a machine state.
269  * This constant defines the maximum histogram width (i.e. the max number of
270  * bins).
271  *
272  * The current limit is arbitrary and could be raised if there is a need,
273  * however too many bins will be hard to serialize in the future.
274  *
275  * Memory concerns are not so great here since the corresponding histogram and
276  * histogram_edges arrays are global and not per-circuit.
277  *
278  * If we ever upgrade this to a value that can't be represented by 8-bits we
279  * also need to upgrade circpad_hist_index_t.
280  */
281 #define CIRCPAD_MAX_HISTOGRAM_LEN (100)
282 
283 /**
284  * A state of a padding state machine. The information here are immutable and
285  * represent the initial form of the state; it does not get updated as things
286  * happen. The mutable information that gets updated in runtime are carried in
287  * a circpad_machine_runtime_t.
288  *
289  * This struct describes the histograms and/or probability distributions, as
290  * well as parameters of a single state in the adaptive padding machine.
291  * Instances of this struct exist in global circpad machine definitions that
292  * come from torrc or the consensus.
293  */
294 typedef struct circpad_state_t {
295  /**
296  * If a histogram is used for this state, this specifies the number of bins
297  * of this histogram. Histograms must have at least 2 bins.
298  *
299  * In particular, the following histogram:
300  *
301  * Tokens
302  * +
303  * 10 | +----+
304  * 9 | | | +---------+
305  * 8 | | | | |
306  * 7 | | | +-----+ |
307  * 6 +----+ Bin+-----+ | +---------------+
308  * 5 | | #1 | | | | |
309  * | Bin| | Bin | Bin | Bin #4 | Bin #5 |
310  * | #0 | | #2 | #3 | | (infinity bin)|
311  * | | | | | | |
312  * | | | | | | |
313  * 0 +----+----+-----+-----+---------+---------------+
314  * 0 100 200 350 500 1000 inf microseconds
315  *
316  * would be specified the following way:
317  * histogram_len = 6;
318  * histogram[] = { 6, 10, 6, 7, 9, 6 }
319  * histogram_edges[] = { 0, 100, 200, 350, 500, 1000 }
320  *
321  * The final bin is called the "infinity bin" and if it's chosen we don't
322  * schedule any padding. The infinity bin is strange because its lower edge
323  * is the max value of possible non-infinite delay allowed by this histogram,
324  * and its upper edge is CIRCPAD_DELAY_INFINITE. You can tell if the infinity
325  * bin is chosen by inspecting its bin index or inspecting its upper edge.
326  *
327  * If a delay probability distribution is used for this state, this is set
328  * to 0. */
330  /** The histogram itself: an array of uint16s of tokens, whose
331  * widths are exponentially spaced, in microseconds.
332  *
333  * This array must have histogram_len elements that are strictly
334  * monotonically increasing. */
336  /* The histogram bin edges in usec.
337  *
338  * Each element of this array specifies the left edge of the corresponding
339  * bin. The rightmost edge is always infinity and is not specified in this
340  * array.
341  *
342  * This array must have histogram_len elements. */
343  circpad_delay_t histogram_edges[CIRCPAD_MAX_HISTOGRAM_LEN+1];
344  /** Total number of tokens in this histogram. This is a constant and is *not*
345  * decremented every time we spend a token. It's used for initializing and
346  * refilling the histogram. */
348 
349  /**
350  * Represents a delay probability distribution (aka IAT distribution). It's a
351  * parametrized way of encoding inter-packet delay information in
352  * microseconds. It can be used instead of histograms.
353  *
354  * If it is used, token_removal below must be set to
355  * CIRCPAD_TOKEN_REMOVAL_NONE.
356  *
357  * Start_usec, range_sec, and rtt_estimates are still applied to the
358  * results of sampling from this distribution (range_sec is used as a max).
359  */
361  /* If a delay probability distribution is used, this is used as the max
362  * value we can sample from the distribution. However, RTT measurements and
363  * dist_added_shift gets applied on top of this value to derive the final
364  * padding delay. */
365  circpad_delay_t dist_max_sample_usec;
366  /* If a delay probability distribution is used and this is set, we will add
367  * this value on top of the value sampled from the IAT distribution to
368  * derive the final padding delay (We also add the RTT measurement if it's
369  * enabled.). */
370  circpad_delay_t dist_added_shift_usec;
371 
372  /**
373  * The length dist is a parameterized way of encoding how long this
374  * state machine runs in terms of sent padding cells or all
375  * sent cells. Values are sampled from this distribution, clamped
376  * to max_len, and then start_len is added to that value.
377  *
378  * It may be specified instead of or in addition to
379  * the infinity bins and bins empty conditions. */
381  /** A minimum length value, added to the output of length_dist */
382  uint16_t start_length;
383  /** A cap on the length value that can be sampled from the length_dist */
384  uint64_t max_length;
385 
386  /** Should we decrement length when we see a nonpadding packet?
387  * XXX: Are there any machines that actually want to set this to 0? There may
388  * not be. OTOH, it's only a bit.. */
390 
391  /**
392  * This is an array that specifies the next state to transition to upon
393  * receipt an event matching the indicated array index.
394  *
395  * This aborts our scheduled packet and switches to the state
396  * corresponding to the index of the array. Tokens are filled upon
397  * this transition.
398  *
399  * States are allowed to transition to themselves, which means re-schedule
400  * a new padding timer. They are also allowed to temporarily "transition"
401  * to the "IGNORE" and "CANCEL" pseudo-states. See defines below
402  * for details on state behavior and meaning.
403  */
404  circpad_statenum_t next_state[CIRCPAD_NUM_EVENTS];
405 
406  /**
407  * If true, estimate the RTT from this relay to the exit/website and add that
408  * to start_usec for use as the histogram bin 0 start delay.
409  *
410  * Right now this is only supported for relay-side state machines.
411  */
412  unsigned use_rtt_estimate : 1;
413 
414  /** This specifies the token removal strategy to use upon padding and
415  * non-padding activity. */
418 
419 /**
420  * The start state for this machine.
421  *
422  * In the original WTF-PAD, this is only used for transition to/from
423  * the burst state. All other fields are not used. But to simplify the
424  * code we've made it a first-class state. This has no performance
425  * consequences, but may make naive serialization of the state machine
426  * large, if we're not careful about how we represent empty fields.
427  */
428 #define CIRCPAD_STATE_START 0
429 
430 /**
431  * The burst state for this machine.
432  *
433  * In the original Adaptive Padding algorithm and in WTF-PAD
434  * (https://www.freehaven.net/anonbib/cache/ShWa-Timing06.pdf and
435  * https://www.cs.kau.se/pulls/hot/thebasketcase-wtfpad/), the burst
436  * state serves to detect bursts in traffic. This is done by using longer
437  * delays in its histogram, which represent the expected delays between
438  * bursts of packets in the target stream. If this delay expires without a
439  * real packet being sent, the burst state sends a padding packet and then
440  * immediately transitions to the gap state, which is used to generate
441  * a synthetic padding packet train. In this implementation, this transition
442  * needs to be explicitly specified in the burst state's transition events.
443  *
444  * Because of this flexibility, other padding mechanisms can transition
445  * between these two states arbitrarily, to encode other dynamics of
446  * target traffic.
447  */
448 #define CIRCPAD_STATE_BURST 1
449 
450 /**
451  * The gap state for this machine.
452  *
453  * In the original Adaptive Padding algorithm and in WTF-PAD, the gap
454  * state serves to simulate an artificial packet train composed of padding
455  * packets. It does this by specifying much lower inter-packet delays than
456  * the burst state, and transitioning back to itself after padding is sent
457  * if these timers expire before real traffic is sent. If real traffic is
458  * sent, it transitions back to the burst state.
459  *
460  * Again, in this implementation, these transitions must be specified
461  * explicitly, and other transitions are also permitted.
462  */
463 #define CIRCPAD_STATE_GAP 2
464 
465 /**
466  * End is a pseudo-state that causes the machine to go completely
467  * idle, and optionally get torn down (depending on the
468  * value of circpad_machine_spec_t.should_negotiate_end)
469  *
470  * End MUST NOT occupy a slot in the machine state array.
471  */
472 #define CIRCPAD_STATE_END CIRCPAD_STATENUM_MAX
473 
474 /**
475  * "Ignore" is a pseudo-state that means "do not react to this
476  * event".
477  *
478  * "Ignore" MUST NOT occupy a slot in the machine state array.
479  */
480 #define CIRCPAD_STATE_IGNORE (CIRCPAD_STATENUM_MAX-1)
481 
482 /**
483  * "Cancel" is a pseudo-state that means "cancel pending timers,
484  * but remain in your current state".
485  *
486  * Cancel MUST NOT occupy a slot in the machine state array.
487  */
488 #define CIRCPAD_STATE_CANCEL (CIRCPAD_STATENUM_MAX-2)
489 
490 /**
491  * Since we have 3 pseudo-states, the max state array length is
492  * up to one less than cancel's statenum.
493  */
494 #define CIRCPAD_MAX_MACHINE_STATES (CIRCPAD_STATE_CANCEL-1)
495 
496 /**
497  * Mutable padding machine info.
498  *
499  * This structure contains mutable information about a padding
500  * machine. The mutable information must be kept separate because
501  * it exists per-circuit, where as the machines themselves are global.
502  * This separation is done to conserve space in the circuit structure.
503  *
504  * This is the per-circuit state that changes regarding the global state
505  * machine. Some parts of it are optional (ie NULL).
506  *
507  * XXX: Play with layout to minimize space on x64 Linux (most common relay).
508  */
510  /** The callback pointer for the padding callbacks.
511  *
512  * These timers stick around the machineinfo until the machineinfo's circuit
513  * is closed, at which point the timer is cancelled. For this reason it's
514  * safe to assume that the machineinfo exists if this timer gets
515  * triggered. */
516  tor_timer_t *padding_timer;
517 
518  /** The circuit for this machine */
520 
521  /** A mutable copy of the histogram for the current state.
522  * NULL if remove_tokens is false for that state */
524  /** Length of the above histogram.
525  * XXX: This field *could* be removed at the expense of added
526  * complexity+overhead for reaching back into the immutable machine
527  * state every time we need to inspect the histogram. It's only a byte,
528  * though, so it seemed worth it.
529  */
531  /** Remove token from this index upon sending padding */
533 
534  /** Stop padding/transition if this many cells sent */
535  uint64_t state_length;
536 #define CIRCPAD_STATE_LENGTH_INFINITE UINT64_MAX
537 
538  /** A scaled count of padding packets sent, used to limit padding overhead.
539  * When this reaches UINT16_MAX, we cut it and nonpadding_sent in half. */
540  uint16_t padding_sent;
541  /** A scaled count of non-padding packets sent, used to limit padding
542  * overhead. When this reaches UINT16_MAX, we cut it and padding_sent in
543  * half. */
544  uint16_t nonpadding_sent;
545 
546  /**
547  * Timestamp of the most recent cell event (sent, received, padding,
548  * non-padding), in seconds from approx_time().
549  *
550  * Used as an emergency break to stop holding padding circuits open.
551  */
553 
554  /**
555  * EWMA estimate of the RTT of the circuit from this hop
556  * to the exit end, in microseconds. */
558 
559  /**
560  * The last time we got an event relevant to estimating
561  * the RTT. Monotonic time in microseconds since system
562  * start.
563  */
565 
566  /**
567  * The time at which we scheduled a non-padding packet,
568  * or selected an infinite delay.
569  *
570  * Monotonic time in microseconds since system start.
571  * This is 0 if we haven't chosen a padding delay.
572  */
574 
575  /** What state is this machine in? */
577 
578  /** Machine counter, for shutdown sync.
579  *
580  * Set from circuit_t.padding_machine_ctr, which is incremented each
581  * padding machine instantiation.
582  */
583  uint32_t machine_ctr;
584 
585  /**
586  * True if we have scheduled a timer for padding.
587  *
588  * This is 1 if a timer is pending. It is 0 if
589  * no timer is scheduled. (It can be 0 even when
590  * padding_was_scheduled_at_usec is non-zero).
591  */
593 
594  /**
595  * If this is true, we have seen full duplex behavior.
596  * Stop updating the RTT.
597  */
598  unsigned stop_rtt_update : 1;
599 
600 /** Max number of padding machines on each circuit. If changed,
601  * also ensure the machine_index bitwith supports the new size. */
602 #define CIRCPAD_MAX_MACHINES (2)
603  /** Which padding machine index was this for.
604  * (make sure changes to the bitwidth can support the
605  * CIRCPAD_MAX_MACHINES define). */
606  unsigned machine_index : 1;
607 
609 
610 /** Helper macro to get an actual state machine from a machineinfo */
611 #define CIRCPAD_GET_MACHINE(machineinfo) \
612  ((machineinfo)->on_circ->padding_machine[(machineinfo)->machine_index])
613 
614 /**
615  * This specifies a particular padding machine to use after negotiation.
616  *
617  * The constants for machine_num_t are in trunnel.
618  * We want to be able to define extra numbers in the consensus/torrc, though.
619  */
620 typedef uint8_t circpad_machine_num_t;
621 
622 /** Global state machine structure from the consensus */
623 typedef struct circpad_machine_spec_t {
624  /* Just a user-friendly machine name for logs */
625  const char *name;
626 
627  /** Global machine number */
629 
630  /** Which machine index slot should this machine go into in
631  * the array on the circuit_t */
632  unsigned machine_index : 1;
633 
634  /** Send a padding negotiate to shut down machine at end state? */
635  unsigned should_negotiate_end : 1;
636 
637  // These next three fields are origin machine-only...
638  /** Origin side or relay side */
639  unsigned is_origin_side : 1;
640 
641  /** Which hop in the circuit should we send padding to/from?
642  * 1-indexed (ie: hop #1 is guard, #2 middle, #3 exit). */
643  unsigned target_hopnum : 3;
644 
645  /** If this flag is enabled, don't close circuits that use this machine even
646  * if another part of Tor wants to close this circuit.
647  *
648  * If this flag is set, the circuitpadding subsystem will close circuits the
649  * moment the machine transitions to the END state, and only if the circuit
650  * has already been asked to be closed by another part of Tor.
651  *
652  * Circuits that should have been closed but were kept open by a padding
653  * machine are re-purposed to CIRCUIT_PURPOSE_C_CIRCUIT_PADDING, hence
654  * machines should take that purpose into account if they are filtering
655  * circuits by purpose. */
656  unsigned manage_circ_lifetime : 1;
657 
658  /** This machine only kills fascists if the following conditions are met. */
660 
661  /** How many padding cells can be sent before we apply overhead limits?
662  * XXX: Note that we can only allow up to 64k of padding cells on an
663  * otherwise quiet circuit. Is this enough? It's 33MB. */
665 
666  /** Padding percent cap: Stop padding if we exceed this percent overhead.
667  * 0 means no limit. Overhead is defined as percent of total traffic, so
668  * that we can use 0..100 here. This is the same definition as used in
669  * Prop#265. */
671 
672  /** State array: indexed by circpad_statenum_t */
674 
675  /**
676  * Number of states this machine has (ie: length of the states array).
677  * XXX: This field is not needed other than for safety. */
680 
682 
683 int circpad_marked_circuit_for_padding(circuit_t *circ, int reason);
684 
685 /**
686  * The following are event call-in points that are of interest to
687  * the state machines. They are called during cell processing. */
689  cell_direction_t dir);
691  uint8_t relay_command);
693  uint8_t relay_command,
694  crypt_path_t *layer_hint);
695 
696 /** Cell events are delivered by the above delivery functions */
697 void circpad_cell_event_nonpadding_sent(struct circuit_t *on_circ);
699 void circpad_cell_event_padding_sent(struct circuit_t *on_circ);
700 void circpad_cell_event_padding_received(struct circuit_t *on_circ);
701 
702 /** Internal events are events the machines send to themselves */
709 
710 /** Machine creation events are events that cause us to set up or
711  * tear down padding state machines. */
717 void
719 
720 void circpad_machines_init(void);
721 void circpad_machines_free(void);
722 void circpad_register_padding_machine(circpad_machine_spec_t *machine,
723  smartlist_t *machine_list);
724 
726  circpad_statenum_t num_states);
727 
729 
731  crypt_path_t *from_hop);
732 
733 /** Serializaton functions for writing to/from torrc and consensus */
735 const circpad_machine_spec_t *circpad_string_to_machine(const char *str);
736 
737 /* Padding negotiation between client and middle */
739  struct cell_t *cell);
741  struct cell_t *cell,
742  crypt_path_t *layer_hint);
744  circpad_machine_num_t machine,
745  uint8_t target_hopnum,
746  uint8_t command,
747  uint32_t machine_ctr);
748 bool circpad_padding_negotiated(struct circuit_t *circ,
749  circpad_machine_num_t machine,
750  uint8_t command,
751  uint8_t response,
752  uint32_t machine_ctr);
753 
755 
757  crypt_path_t *layer_hint,
758  const relay_header_t *rh);
759 
762 
765  circpad_event_t event));
766 
769 
770 void circpad_free_all(void);
771 
772 #ifdef CIRCUITPADDING_PRIVATE
774 #define machine_spec_free(chan) \
775  FREE_AND_NULL(circpad_machine_spec_t,machine_spec_free_, (m))
776 
779 
780 STATIC bool
782 
786 
787 STATIC const circpad_state_t *
789 
791 
793  const circpad_machine_runtime_t *mi,
794  circpad_delay_t us);
795 
797  struct circuit_t *on_circ,
798  int machine_index);
800  circpad_delay_t target_bin_us);
802  circpad_delay_t target_bin_us);
804  circpad_delay_t target_bin_us,
805  bool use_usec);
807 
809 circpad_send_command_to_hop,(struct origin_circuit_t *circ, uint8_t hopnum,
810  uint8_t relay_command, const uint8_t *payload,
811  ssize_t payload_len));
812 
813 MOCK_DECL(STATIC const node_t *,
814 circuit_get_nth_node,(origin_circuit_t *circ, int hop));
815 
819 
820 STATIC void
822  smartlist_t *machines_sl);
823 
824 #ifdef TOR_UNIT_TESTS
827 
828 #endif
829 
830 #endif /* defined(CIRCUITPADDING_PRIVATE) */
831 
832 #endif /* !defined(TOR_CIRCUITPADDING_H) */
circpad_event_t
circpad_event_t
Definition: circuitpadding.h:40
circpad_deliver_unrecognized_cell_events
void circpad_deliver_unrecognized_cell_events(struct circuit_t *circ, cell_direction_t dir)
Definition: circuitpadding.c:2368
circpad_machine_runtime_t::rtt_estimate_usec
circpad_delay_t rtt_estimate_usec
Definition: circuitpadding.h:557
circpad_internal_event_infinity
circpad_decision_t circpad_internal_event_infinity(circpad_machine_runtime_t *mi)
Definition: circuitpadding.c:1969
circpad_machine_spec_t::allowed_padding_count
uint16_t allowed_padding_count
Definition: circuitpadding.h:664
circpad_send_padding_cell_for_callback
circpad_decision_t circpad_send_padding_cell_for_callback(circpad_machine_runtime_t *mi)
Definition: circuitpadding.c:1224
circpad_machine_conditions_t::reduced_padding_ok
unsigned reduced_padding_ok
Definition: circuitpadding.h:172
circpad_machine_spec_to_string
char * circpad_machine_spec_to_string(const circpad_machine_spec_t *machine)
circpad_state_t::use_rtt_estimate
unsigned use_rtt_estimate
Definition: circuitpadding.h:412
circpad_check_received_cell
int circpad_check_received_cell(cell_t *cell, circuit_t *circ, crypt_path_t *layer_hint, const relay_header_t *rh)
Definition: circuitpadding.c:1843
CIRCPAD_TOKEN_REMOVAL_HIGHER
@ CIRCPAD_TOKEN_REMOVAL_HIGHER
Definition: circuitpadding.h:211
circpad_purpose_mask_t
uint32_t circpad_purpose_mask_t
Definition: circuitpadding.h:144
circpad_machine_runtime_t
Definition: circuitpadding.h:509
circpad_machine_runtime_t::padding_scheduled_at_usec
circpad_time_t padding_scheduled_at_usec
Definition: circuitpadding.h:573
circpad_circ_purpose_to_mask
circpad_purpose_mask_t circpad_circ_purpose_to_mask(uint8_t circ_purpose)
Definition: circuitpadding.c:2111
circpad_machine_spec_t
Definition: circuitpadding.h:623
circpad_machine_event_circ_has_no_streams
void circpad_machine_event_circ_has_no_streams(struct origin_circuit_t *circ)
Definition: circuitpadding.c:2316
circpad_internal_event_state_length_up
circpad_decision_t circpad_internal_event_state_length_up(circpad_machine_runtime_t *)
Definition: circuitpadding.c:2002
circpad_machines_init
void circpad_machines_init(void)
Definition: circuitpadding.c:2772
CIRCPAD_TOKEN_REMOVAL_LOWER
@ CIRCPAD_TOKEN_REMOVAL_LOWER
Definition: circuitpadding.h:213
circpad_machine_remove_token
STATIC void circpad_machine_remove_token(circpad_machine_runtime_t *mi)
Definition: circuitpadding.c:1109
circpad_machine_event_circ_has_streams
void circpad_machine_event_circ_has_streams(struct origin_circuit_t *circ)
Definition: circuitpadding.c:2301
circpad_machine_event_circ_built
void circpad_machine_event_circ_built(struct origin_circuit_t *circ)
Definition: circuitpadding.c:2259
circpad_hist_index_t
int8_t circpad_hist_index_t
Definition: circuitpadding.h:69
cell_direction_t
cell_direction_t
Definition: or.h:483
circpad_machine_runtime_t::nonpadding_sent
uint16_t nonpadding_sent
Definition: circuitpadding.h:544
circpad_machine_spec_t::machine_index
unsigned machine_index
Definition: circuitpadding.h:632
circpad_machine_conditions_t::requires_vanguards
unsigned requires_vanguards
Definition: circuitpadding.h:161
circpad_cell_event_nonpadding_received
void circpad_cell_event_nonpadding_received(struct circuit_t *on_circ)
Definition: circuitpadding.c:1902
circpad_machine_conditions_t::apply_state_mask
circpad_circuit_state_t apply_state_mask
Definition: circuitpadding.h:176
circpad_machine_spec_t::states
circpad_state_t * states
Definition: circuitpadding.h:673
circpad_state_t::histogram_len
circpad_hist_index_t histogram_len
Definition: circuitpadding.h:329
circpad_statenum_t
uint16_t circpad_statenum_t
Definition: circuitpadding.h:265
crypt_path_t
Definition: crypt_path_st.h:47
circpad_machine_spec_t::conditions
circpad_machine_conditions_t conditions
Definition: circuitpadding.h:659
circpad_machine_spec_t::should_negotiate_end
unsigned should_negotiate_end
Definition: circuitpadding.h:635
circpad_handle_padding_negotiate
signed_error_t circpad_handle_padding_negotiate(struct circuit_t *circ, struct cell_t *cell)
Definition: circuitpadding.c:2966
circpad_delay_t
uint32_t circpad_delay_t
Definition: circuitpadding.h:75
circpad_circuit_machineinfo_new
STATIC circpad_machine_runtime_t * circpad_circuit_machineinfo_new(circuit_t *on_circ, int machine_index)
Definition: circuitpadding.c:315
cell_t
Definition: cell_st.h:17
circpad_machine_spec_t::is_origin_side
unsigned is_origin_side
Definition: circuitpadding.h:639
circpad_machine_runtime_t::padding_sent
uint16_t padding_sent
Definition: circuitpadding.h:540
circpad_machine_remove_lower_token
STATIC void circpad_machine_remove_lower_token(circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec)
Definition: circuitpadding.c:845
circpad_distribution_type_t
circpad_distribution_type_t
Definition: circuitpadding.h:233
circuit_get_nth_node
STATIC const node_t * circuit_get_nth_node(origin_circuit_t *circ, int hop)
Definition: circuitpadding.c:2840
machine_spec_free_
STATIC void machine_spec_free_(circpad_machine_spec_t *m)
Definition: circuitpadding.c:3103
circpad_machine_schedule_padding
circpad_decision_t circpad_machine_schedule_padding(circpad_machine_runtime_t *)
Definition: circuitpadding.c:1420
circpad_circuit_free_all_machineinfos
void circpad_circuit_free_all_machineinfos(struct circuit_t *circ)
Definition: circuitpadding.c:304
circpad_machine_runtime_t::chosen_bin
circpad_hist_index_t chosen_bin
Definition: circuitpadding.h:532
circpad_removal_t
circpad_removal_t
Definition: circuitpadding.h:205
circpad_machine_runtime_t::histogram_len
circpad_hist_index_t histogram_len
Definition: circuitpadding.h:530
circpad_machine_event_circ_has_no_relay_early
void circpad_machine_event_circ_has_no_relay_early(struct origin_circuit_t *circ)
Definition: circuitpadding.c:2286
circpad_machine_conditions_t::min_hops
unsigned min_hops
Definition: circuitpadding.h:158
circpad_machine_conditions_t::apply_purpose_mask
circpad_purpose_mask_t apply_purpose_mask
Definition: circuitpadding.h:180
node_t
Definition: node_st.h:34
origin_circuit_t
Definition: origin_circuit_st.h:79
circpad_machine_runtime_t::padding_timer
tor_timer_t * padding_timer
Definition: circuitpadding.h:516
CIRCPAD_TOKEN_REMOVAL_EXACT
@ CIRCPAD_TOKEN_REMOVAL_EXACT
Definition: circuitpadding.h:221
CIRCPAD_MAX_HISTOGRAM_LEN
#define CIRCPAD_MAX_HISTOGRAM_LEN
Definition: circuitpadding.h:281
circpad_machine_runtime_t::last_received_time_usec
circpad_time_t last_received_time_usec
Definition: circuitpadding.h:564
circpad_send_command_to_hop
STATIC signed_error_t circpad_send_command_to_hop(origin_circuit_t *circ, uint8_t hopnum, uint8_t relay_command, const uint8_t *payload, ssize_t payload_len)
Definition: circuitpadding.c:1184
circpad_machines_free
void circpad_machines_free(void)
Definition: circuitpadding.c:2799
circpad_machine_num_t
uint8_t circpad_machine_num_t
Definition: circuitpadding.h:620
relay_padding_machines
STATIC smartlist_t * relay_padding_machines
Definition: circuitpadding.c:117
circpad_state_t::iat_dist
circpad_distribution_t iat_dist
Definition: circuitpadding.h:360
circpad_machine_sample_delay
STATIC circpad_delay_t circpad_machine_sample_delay(circpad_machine_runtime_t *mi)
Definition: circuitpadding.c:591
circpad_cell_event_padding_sent
void circpad_cell_event_padding_sent(struct circuit_t *on_circ)
Definition: circuitpadding.c:1923
circuit_t
Definition: circuit_st.h:61
circpad_state_t
Definition: circuitpadding.h:294
CIRCPAD_TOKEN_REMOVAL_CLOSEST
@ CIRCPAD_TOKEN_REMOVAL_CLOSEST
Definition: circuitpadding.h:215
circpad_padding_negotiated
bool circpad_padding_negotiated(struct circuit_t *circ, circpad_machine_num_t machine, uint8_t command, uint8_t response, uint32_t machine_ctr)
Definition: circuitpadding.c:2921
circpad_marked_circuit_for_padding
int circpad_marked_circuit_for_padding(circuit_t *circ, int reason)
Definition: circuitpadding.c:174
circpad_add_matching_machines
STATIC void circpad_add_matching_machines(origin_circuit_t *on_circ, smartlist_t *machines_sl)
Definition: circuitpadding.c:2169
MOCK_DECL
#define MOCK_DECL(rv, funcname, arglist)
Definition: testsupport.h:127
circpad_histogram_usec_to_bin
STATIC circpad_hist_index_t circpad_histogram_usec_to_bin(const circpad_machine_runtime_t *mi, circpad_delay_t usec)
Definition: circuitpadding.c:419
command
tor_cmdline_mode_t command
Definition: config.c:2448
circpad_time_t
uint64_t circpad_time_t
Definition: circuitpadding.h:72
circpad_machine_runtime_t::current_state
circpad_statenum_t current_state
Definition: circuitpadding.h:576
circpad_cell_event_padding_received
void circpad_cell_event_padding_received(struct circuit_t *on_circ)
Definition: circuitpadding.c:1949
circpad_new_consensus_params
void circpad_new_consensus_params(const networkstatus_t *ns)
Definition: circuitpadding.c:1317
circpad_negotiate_padding
signed_error_t circpad_negotiate_padding(struct origin_circuit_t *circ, circpad_machine_num_t machine, uint8_t target_hopnum, uint8_t command, uint32_t machine_ctr)
Definition: circuitpadding.c:2873
circpad_machine_remove_closest_token
STATIC void circpad_machine_remove_closest_token(circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec, bool use_usec)
Definition: circuitpadding.c:876
circpad_histogram_bin_to_usec
STATIC circpad_delay_t circpad_histogram_bin_to_usec(const circpad_machine_runtime_t *mi, circpad_hist_index_t bin)
Definition: circuitpadding.c:362
signed_error_t
int signed_error_t
Definition: circuitpadding.h:18
circpad_state_t::length_includes_nonpadding
unsigned length_includes_nonpadding
Definition: circuitpadding.h:389
circpad_machine_remove_higher_token
STATIC void circpad_machine_remove_higher_token(circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec)
Definition: circuitpadding.c:822
circpad_machine_conditions_t
Definition: circuitpadding.h:156
circpad_hist_token_t
uint32_t circpad_hist_token_t
Definition: circuitpadding.h:66
circpad_distribution_t
Definition: circuitpadding.h:258
circpad_machine_runtime_t::on_circ
struct circuit_t * on_circ
Definition: circuitpadding.h:519
circpad_machine_spec_t::target_hopnum
unsigned target_hopnum
Definition: circuitpadding.h:643
circpad_machine_runtime_t::machine_index
unsigned machine_index
Definition: circuitpadding.h:606
circpad_machine_spec_t::max_padding_percent
uint8_t max_padding_percent
Definition: circuitpadding.h:670
circpad_state_t::next_state
circpad_statenum_t next_state[CIRCPAD_NUM_EVENTS]
Definition: circuitpadding.h:404
circpad_machine_reached_padding_limit
STATIC bool circpad_machine_reached_padding_limit(circpad_machine_runtime_t *mi)
Definition: circuitpadding.c:1372
circpad_padding_is_from_expected_hop
bool circpad_padding_is_from_expected_hop(struct circuit_t *circ, crypt_path_t *from_hop)
Definition: circuitpadding.c:2332
relay_header_t
Definition: or.h:638
circpad_state_t::histogram
circpad_hist_token_t histogram[CIRCPAD_MAX_HISTOGRAM_LEN]
Definition: circuitpadding.h:335
circpad_state_t::histogram_total_tokens
uint32_t histogram_total_tokens
Definition: circuitpadding.h:347
timers.h
Header for timers.c.
circpad_machine_runtime_t::machine_ctr
uint32_t machine_ctr
Definition: circuitpadding.h:583
circpad_machine_conditions_t::keep_purpose_mask
circpad_purpose_mask_t keep_purpose_mask
Definition: circuitpadding.h:190
circpad_state_t::token_removal
circpad_removal_t token_removal
Definition: circuitpadding.h:416
circpad_machine_conditions_t::keep_state_mask
circpad_circuit_state_t keep_state_mask
Definition: circuitpadding.h:185
circpad_deliver_recognized_relay_cell_events
void circpad_deliver_recognized_relay_cell_events(struct circuit_t *circ, uint8_t relay_command, crypt_path_t *layer_hint)
Definition: circuitpadding.c:2396
histogram_get_bin_upper_bound
STATIC circpad_delay_t histogram_get_bin_upper_bound(const circpad_machine_runtime_t *mi, circpad_hist_index_t bin)
Definition: circuitpadding.c:393
circpad_machine_states_init
void circpad_machine_states_init(circpad_machine_spec_t *machine, circpad_statenum_t num_states)
Definition: circuitpadding.c:2460
circpad_machine_current_state
STATIC const circpad_state_t * circpad_machine_current_state(const circpad_machine_runtime_t *mi)
Definition: circuitpadding.c:335
circpad_machine_runtime_t::stop_rtt_update
unsigned stop_rtt_update
Definition: circuitpadding.h:598
circpad_internal_event_bins_empty
circpad_decision_t circpad_internal_event_bins_empty(circpad_machine_runtime_t *)
Definition: circuitpadding.c:1983
circpad_machine_spec_transition
circpad_decision_t circpad_machine_spec_transition(circpad_machine_runtime_t *mi, circpad_event_t event)
Definition: circuitpadding.c:1605
circpad_machine_spec_t::machine_num
circpad_machine_num_t machine_num
Definition: circuitpadding.h:628
CIRCPAD_TOKEN_REMOVAL_NONE
@ CIRCPAD_TOKEN_REMOVAL_NONE
Definition: circuitpadding.h:207
circpad_machine_runtime_t::is_padding_timer_scheduled
unsigned is_padding_timer_scheduled
Definition: circuitpadding.h:592
circpad_state_t::max_length
uint64_t max_length
Definition: circuitpadding.h:384
circpad_deliver_sent_relay_cell_events
void circpad_deliver_sent_relay_cell_events(struct circuit_t *circ, uint8_t relay_command)
Definition: circuitpadding.c:2433
CIRCPAD_TOKEN_REMOVAL_CLOSEST_USEC
@ CIRCPAD_TOKEN_REMOVAL_CLOSEST_USEC
Definition: circuitpadding.h:218
circpad_circuit_state_t
circpad_circuit_state_t
Definition: circuitpadding.h:115
circpad_machine_setup_tokens
STATIC void circpad_machine_setup_tokens(circpad_machine_runtime_t *mi)
Definition: circuitpadding.c:495
circpad_decision_t
circpad_decision_t
Definition: circuitpadding.h:60
circpad_machine_spec_t::num_states
circpad_statenum_t num_states
Definition: circuitpadding.h:678
circpad_handle_padding_negotiated
signed_error_t circpad_handle_padding_negotiated(struct circuit_t *circ, struct cell_t *cell, crypt_path_t *layer_hint)
Definition: circuitpadding.c:3043
circpad_machine_event_circ_purpose_changed
void circpad_machine_event_circ_purpose_changed(struct origin_circuit_t *circ)
Definition: circuitpadding.c:2272
STATIC
#define STATIC
Definition: testsupport.h:32
circpad_machine_event_circ_added_hop
void circpad_machine_event_circ_added_hop(struct origin_circuit_t *on_circ)
Definition: circuitpadding.c:2245
networkstatus_t
Definition: networkstatus_st.h:26
circpad_machine_runtime_t::histogram
circpad_hist_token_t * histogram
Definition: circuitpadding.h:523
circpad_state_t::start_length
uint16_t start_length
Definition: circuitpadding.h:382
circpad_cell_event_nonpadding_sent
void circpad_cell_event_nonpadding_sent(struct circuit_t *on_circ)
Definition: circuitpadding.c:1812
smartlist_t
Definition: smartlist_core.h:26
circpad_machine_spec_t::manage_circ_lifetime
unsigned manage_circ_lifetime
Definition: circuitpadding.h:656
circpad_state_t::length_dist
circpad_distribution_t length_dist
Definition: circuitpadding.h:380
circpad_machine_runtime_t::last_cell_time_sec
time_t last_cell_time_sec
Definition: circuitpadding.h:552
circpad_free_all
void circpad_free_all(void)
Definition: circuitpadding.c:3113
circpad_machine_runtime_t::state_length
uint64_t state_length
Definition: circuitpadding.h:535
origin_padding_machines
STATIC smartlist_t * origin_padding_machines
Definition: circuitpadding.c:109