Tor  0.4.4.0-alpha-dev
circuitpadding.c
Go to the documentation of this file.
1 /* Copyright (c) 2017 The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
3 
4 /**
5  * \file circuitpadding.c
6  * \brief Circuit-level padding implementation
7  *
8  * \details
9  *
10  * This file implements Tor proposal 254 "Padding Negotiation" which is heavily
11  * inspired by the paper "Toward an Efficient Website Fingerprinting Defense"
12  * by M. Juarez, M. Imani, M. Perry, C. Diaz, M. Wright.
13  *
14  * In particular the code in this file describes mechanisms for clients to
15  * negotiate various types of circuit-level padding from relays.
16  *
17  * Each padding type is described by a state machine (circpad_machine_spec_t),
18  * which is also referred as a "padding machine" in this file. Currently,
19  * these state machines are hardcoded in the source code (e.g. see
20  * circpad_machines_init()), but in the future we will be able to
21  * serialize them in the torrc or the consensus.
22  *
23  * As specified by prop#254, clients can negotiate padding with relays by using
24  * PADDING_NEGOTIATE cells. After successful padding negotiation, padding
25  * machines are assigned to the circuit in their mutable form as a
26  * circpad_machine_runtime_t.
27  *
28  * Each state of a padding state machine can be either:
29  * - A histogram that specifies inter-arrival padding delays.
30  * - Or a parametrized probability distribution that specifies inter-arrival
31  * delays (see circpad_distribution_type_t).
32  *
33  * Padding machines start from the START state and finish with the END
34  * state. They can transition between states using the events in
35  * circpad_event_t.
36  *
37  * When a padding machine reaches the END state, it gets wiped from the circuit
38  * so that other padding machines can take over if needed (see
39  * circpad_machine_spec_transitioned_to_end()).
40  *
41  ****************************
42  * General notes:
43  *
44  * All used machines should be heap allocated and placed into
45  * origin_padding_machines/relay_padding_machines so that they get correctly
46  * cleaned up by the circpad_free_all() function.
47  **/
48 
49 #define CIRCUITPADDING_PRIVATE
50 
51 #include <math.h>
52 #include "lib/math/fp.h"
53 #include "lib/math/prob_distr.h"
54 #include "core/or/or.h"
55 #include "core/or/circuitpadding.h"
57 #include "core/or/circuitlist.h"
58 #include "core/or/circuituse.h"
60 #include "core/or/relay.h"
61 #include "feature/stats/rephist.h"
63 
64 #include "core/or/channel.h"
65 
66 #include "lib/time/compat_time.h"
67 #include "lib/defs/time.h"
69 
70 #include "core/or/crypt_path_st.h"
71 #include "core/or/circuit_st.h"
73 #include "core/or/or_circuit_st.h"
76 #include "core/or/cell_st.h"
77 #include "core/or/extend_info_st.h"
80 
81 #include "app/config/config.h"
82 
84  origin_circuit_t *circ);
85 static void circpad_setup_machine_on_circ(circuit_t *on_circ,
86  const circpad_machine_spec_t *machine);
88 
91 
92 /** Cached consensus params */
93 static uint8_t circpad_padding_disabled;
94 static uint8_t circpad_padding_reduced;
95 static uint8_t circpad_global_max_padding_percent;
96 static uint16_t circpad_global_allowed_cells;
97 static uint16_t circpad_max_circ_queued_cells;
98 
99 /** Global cell counts, for rate limiting */
101 static uint64_t circpad_global_nonpadding_sent;
102 
103 /** This is the list of circpad_machine_spec_t's parsed from consensus and
104  * torrc that have origin_side == 1 (ie: are for client side).
105  *
106  * The machines in this smartlist are considered immutable and they are used
107  * as-is by circuits so they should not change or get deallocated in Tor's
108  * runtime and as long as circuits are alive. */
110 
111 /** This is the list of circpad_machine_spec_t's parsed from consensus and
112  * torrc that have origin_side == 0 (ie: are for relay side).
113  *
114  * The machines in this smartlist are considered immutable and they are used
115  * as-is by circuits so they should not change or get deallocated in Tor's
116  * runtime and as long as circuits are alive. */
118 
119 #ifndef COCCI
120 /** Loop over the current padding state machines using <b>loop_var</b> as the
121  * loop variable. */
122 #define FOR_EACH_CIRCUIT_MACHINE_BEGIN(loop_var) \
123  STMT_BEGIN \
124  for (int loop_var = 0; loop_var < CIRCPAD_MAX_MACHINES; loop_var++) {
125 #define FOR_EACH_CIRCUIT_MACHINE_END } STMT_END ;
126 
127 /** Loop over the current active padding state machines using <b>loop_var</b>
128  * as the loop variable. If a machine is not active, skip it. */
129 #define FOR_EACH_ACTIVE_CIRCUIT_MACHINE_BEGIN(loop_var, circ) \
130  FOR_EACH_CIRCUIT_MACHINE_BEGIN(loop_var) \
131  if (!(circ)->padding_info[loop_var]) \
132  continue;
133 #define FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END } STMT_END ;
134 #endif /* !defined(COCCI) */
135 
136 /**
137  * Free the machineinfo at an index
138  */
139 static void
141 {
142  if (circ->padding_info[idx]) {
143  log_fn(LOG_INFO,LD_CIRC, "Freeing padding info idx %d on circuit %u (%d)",
144  idx, CIRCUIT_IS_ORIGIN(circ) ?
145  TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0,
146  circ->purpose);
147 
148  tor_free(circ->padding_info[idx]->histogram);
149  timer_free(circ->padding_info[idx]->padding_timer);
150  tor_free(circ->padding_info[idx]);
151  }
152 }
153 
154 /**
155  * Return true if circpad has decided to hold the circuit open for additional
156  * padding. This function is used to take and retain ownership of certain
157  * types of circuits that have padding machines on them, that have been passed
158  * to circuit_mark_for_close().
159  *
160  * circuit_mark_for_close() calls this function to ask circpad if any padding
161  * machines want to keep the circuit open longer to pad.
162  *
163  * Any non-measurement circuit that was closed for a normal, non-error reason
164  * code may be held open for up to CIRCPAD_DELAY_INFINITE microseconds between
165  * network-driven cell events.
166  *
167  * After CIRCPAD_DELAY_INFINITE microseconds of silence on a circuit, this
168  * function will no longer hold it open (it will return 0 regardless of
169  * what the machines ask for, and thus circuit_expire_old_circuits_clientside()
170  * will close the circuit after roughly 1.25hr of idle time, maximum,
171  * regardless of the padding machine state.
172  */
173 int
175 {
176  /* If the circuit purpose is measurement or path bias, don't
177  * hold it open */
180  return 0;
181  }
182 
183  /* If the circuit is closed for any reason other than these three valid,
184  * client-side close reasons, do not try to keep it open. It is probably
185  * damaged or unusable. Note this is OK with vanguards because
186  * controller-closed circuits have REASON=REQUESTED, so vanguards-closed
187  * circuits will not be held open (we want them to close ASAP). */
188  if (!(reason == END_CIRC_REASON_NONE ||
189  reason == END_CIRC_REASON_FINISHED ||
190  reason == END_CIRC_REASON_IP_NOW_REDUNDANT)) {
191  return 0;
192  }
193 
196  if (!mi) {
197  continue; // No padding runtime info; check next machine
198  }
199 
201 
202  /* If we're in END state (NULL here), then check next machine */
203  if (!state) {
204  continue; // check next machine
205  }
206 
207  /* If the machine does not want to control the circuit close itself, then
208  * check the next machine */
209  if (!circ->padding_machine[i]->manage_circ_lifetime) {
210  continue; // check next machine
211  }
212 
213  /* If the machine has reached the END state, we can close. Check next
214  * machine. */
215  if (mi->current_state == CIRCPAD_STATE_END) {
216  continue; // check next machine
217  }
218 
219  log_info(LD_CIRC, "Circuit %d is not marked for close because of a "
220  "pending padding machine in index %d.",
221  CIRCUIT_IS_ORIGIN(circ) ?
222  TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0, i);
223 
224  /* If the machine has had no network events at all within the
225  * last circpad_delay_t timespan, it's in some deadlock state.
226  * Tell circuit_mark_for_close() that we don't own it anymore.
227  * This will allow circuit_expire_old_circuits_clientside() to
228  * close it.
229  */
230  if (circ->padding_info[i]->last_cell_time_sec +
231  (time_t)CIRCPAD_DELAY_MAX_SECS < approx_time()) {
232  log_notice(LD_BUG, "Circuit %d was not marked for close because of a "
233  "pending padding machine in index %d for over an hour. "
234  "Circuit is a %s",
235  CIRCUIT_IS_ORIGIN(circ) ?
236  TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0,
238 
239  return 0; // abort timer reached; mark the circuit for close now
240  }
241 
242  /* If we weren't marked dirty yet, let's pretend we're dirty now.
243  * ("Dirty" means that a circuit has been used for application traffic
244  * by Tor.. Dirty circuits have different expiry times, and are not
245  * considered in counts of built circuits, etc. By claiming that we're
246  * dirty, the rest of Tor will make decisions as if we were actually
247  * used by application data.
248  *
249  * This is most important for circuit_expire_old_circuits_clientside(),
250  * where we want that function to expire us after the padding machine
251  * has shut down, but using the MaxCircuitDirtiness timer instead of
252  * the idle circuit timer (again, we want this because we're not
253  * supposed to look idle to Guard nodes that can see our lifespan). */
254  if (!circ->timestamp_dirty)
255  circ->timestamp_dirty = approx_time();
256 
257  /* Take ownership of the circuit */
259 
260  return 1;
261  } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
262 
263  return 0; // No machine wanted to keep the circuit open; mark for close
264 }
265 
266 /**
267  * Free all the machineinfos in <b>circ</b> that match <b>machine_num</b>.
268  *
269  * Returns true if any machineinfos with that number were freed.
270  * False otherwise. */
271 static int
273 {
274  int found = 0;
276  if (circ->padding_machine[i] &&
277  circ->padding_machine[i]->machine_num == machine_num) {
279  circ->padding_machine[i] = NULL;
280  found = 1;
281  }
282  } FOR_EACH_CIRCUIT_MACHINE_END;
283 
284  return found;
285 }
286 
287 /**
288  * Free all padding machines and mutable info associated with circuit
289  */
290 void
292 {
295  } FOR_EACH_CIRCUIT_MACHINE_END;
296 }
297 
298 /**
299  * Allocate a new mutable machineinfo structure.
300  */
302 circpad_circuit_machineinfo_new(circuit_t *on_circ, int machine_index)
303 {
305  tor_malloc_zero(sizeof(circpad_machine_runtime_t));
306  mi->machine_index = machine_index;
307  mi->on_circ = on_circ;
309 
310  return mi;
311 }
312 
313 /**
314  * Return the circpad_state_t for the current state based on the
315  * mutable info.
316  *
317  * This function returns NULL when the machine is in the end state or in an
318  * invalid state.
319  */
320 STATIC const circpad_state_t *
322 {
323  const circpad_machine_spec_t *machine = CIRCPAD_GET_MACHINE(mi);
324 
325  if (mi->current_state == CIRCPAD_STATE_END) {
326  return NULL;
327  } else if (BUG(mi->current_state >= machine->num_states)) {
329  "Invalid circuit padding state %d",
330  mi->current_state);
331 
332  return NULL;
333  }
334 
335  return &machine->states[mi->current_state];
336 }
337 
338 /**
339  * Get the lower bound of a histogram bin.
340  *
341  * You can obtain the upper bound using histogram_get_bin_upper_bound().
342  *
343  * This function can also be called with 'bin' set to a value equal or greater
344  * than histogram_len in which case the infinity bin is chosen and
345  * CIRCPAD_DELAY_INFINITE is returned.
346  */
350 {
352  circpad_delay_t rtt_add_usec = 0;
353 
354  /* Our state should have been checked to be non-null by the caller
355  * (circpad_machine_remove_token()) */
356  if (BUG(state == NULL)) {
357  return CIRCPAD_DELAY_INFINITE;
358  }
359 
360  /* The infinity bin has an upper bound of infinity, so make sure we return
361  * that if they ask for it. */
362  if (bin > CIRCPAD_INFINITY_BIN(state)) {
363  return CIRCPAD_DELAY_INFINITE;
364  }
365 
366  /* If we are using an RTT estimate, consider it as well. */
367  if (state->use_rtt_estimate) {
368  rtt_add_usec = mi->rtt_estimate_usec;
369  }
370 
371  return state->histogram_edges[bin] + rtt_add_usec;
372 }
373 
374 /**
375  * Like circpad_histogram_bin_to_usec() but return the upper bound of bin.
376  * (The upper bound is included in the bin.)
377  */
381 {
382  return circpad_histogram_bin_to_usec(mi, bin+1) - 1;
383 }
384 
385 /** Return the midpoint of the histogram bin <b>bin_index</b>. */
386 static circpad_delay_t
388  int bin_index)
389 {
390  circpad_delay_t left_bound = circpad_histogram_bin_to_usec(mi, bin_index);
391  circpad_delay_t right_bound = histogram_get_bin_upper_bound(mi, bin_index);
392 
393  return left_bound + (right_bound - left_bound)/2;
394 }
395 
396 /**
397  * Return the bin that contains the usec argument.
398  * "Contains" is defined as us in [lower, upper).
399  *
400  * This function will never return the infinity bin (histogram_len-1), in order
401  * to simplify the rest of the code, so if a usec is provided that falls above
402  * the highest non-infinity bin, that bin index will be returned.
403  */
406  circpad_delay_t usec)
407 {
409  circpad_delay_t rtt_add_usec = 0;
411 
412  /* Our state should have been checked to be non-null by the caller
413  * (circpad_machine_remove_token()) */
414  if (BUG(state == NULL)) {
415  return 0;
416  }
417 
418  /* If we are using an RTT estimate, consider it as well. */
419  if (state->use_rtt_estimate) {
420  rtt_add_usec = mi->rtt_estimate_usec;
421  }
422 
423  /* Walk through the bins and check the upper bound of each bin, if 'usec' is
424  * less-or-equal to that, return that bin. If rtt_estimate is enabled then
425  * add that to the upper bound of each bin.
426  *
427  * We don't want to return the infinity bin here, so don't go there. */
428  for (bin = 0 ; bin < CIRCPAD_INFINITY_BIN(state) ; bin++) {
429  if (usec <= histogram_get_bin_upper_bound(mi, bin) + rtt_add_usec) {
430  return bin;
431  }
432  }
433 
434  /* We don't want to return the infinity bin here, so if we still didn't find
435  * the right bin, return the highest non-infinity bin */
436  return CIRCPAD_INFINITY_BIN(state)-1;
437 }
438 
439 /**
440  * Return true if the machine supports token removal.
441  *
442  * Token removal is equivalent to having a mutable histogram in the
443  * circpad_machine_runtime_t mutable info. So while we're at it,
444  * let's assert that everything is consistent between the mutable
445  * runtime and the readonly machine spec.
446  */
447 static inline int
449 {
450  /* No runtime histogram == no token removal */
451  if (mi->histogram == NULL) {
452  /* Machines that don't want token removal are trying to avoid
453  * potentially expensive mallocs, extra memory accesses, and/or
454  * potentially expensive monotime calls. Let's minimize checks
455  * and keep this path fast. */
456  tor_assert_nonfatal(mi->histogram_len == 0);
457  return 0;
458  } else {
459  /* Machines that do want token removal are less sensitive to performance.
460  * Let's spend some time to check that our state is consistent and sane */
462  if (BUG(!state)) {
463  return 1;
464  }
465  tor_assert_nonfatal(state->token_removal != CIRCPAD_TOKEN_REMOVAL_NONE);
466  tor_assert_nonfatal(state->histogram_len == mi->histogram_len);
467  tor_assert_nonfatal(mi->histogram_len != 0);
468  return 1;
469  }
470 
471  tor_assert_nonfatal_unreached();
472  return 0;
473 }
474 
475 /**
476  * This function frees any token bins allocated from a previous state
477  *
478  * Called after a state transition, or if the bins are empty.
479  */
480 STATIC void
482 {
484 
485  /* If this state doesn't exist, or doesn't have token removal,
486  * free any previous state's runtime histogram, and bail.
487  *
488  * If we don't have a token removal strategy, we also don't need a runtime
489  * histogram and we rely on the immutable one in machine_spec_t. */
490  if (!state || state->token_removal == CIRCPAD_TOKEN_REMOVAL_NONE) {
491  if (mi->histogram) {
492  tor_free(mi->histogram);
493  mi->histogram = NULL;
494  mi->histogram_len = 0;
495  }
496  return;
497  }
498 
499  /* Try to avoid re-mallocing if we don't really need to */
500  if (!mi->histogram || (mi->histogram
501  && mi->histogram_len != state->histogram_len)) {
502  tor_free(mi->histogram); // null ok
503  mi->histogram = tor_malloc_zero(sizeof(circpad_hist_token_t)
504  *state->histogram_len);
505  }
506  mi->histogram_len = state->histogram_len;
507 
508  memcpy(mi->histogram, state->histogram,
509  sizeof(circpad_hist_token_t)*state->histogram_len);
510 }
511 
512 /**
513  * Choose a length for this state (in cells), if specified.
514  */
515 static void
517 {
519  double length;
520 
521  if (!state || state->length_dist.type == CIRCPAD_DIST_NONE) {
522  mi->state_length = CIRCPAD_STATE_LENGTH_INFINITE;
523  return;
524  }
525 
526  length = circpad_distribution_sample(state->length_dist);
527  length = MAX(0, length);
528  length += state->start_length;
529 
530  if (state->max_length) {
531  length = MIN(length, state->max_length);
532  }
533 
534  mi->state_length = clamp_double_to_int64(length);
535 
536  log_info(LD_CIRC, "State length sampled to %"PRIu64" for circuit %u",
539 }
540 
541 /**
542  * Sample a value from our iat_dist, and clamp it safely
543  * to circpad_delay_t.
544  *
545  * Before returning, add <b>delay_shift</b> (can be zero) to the sampled value.
546  */
547 static circpad_delay_t
549  circpad_delay_t delay_shift)
550 {
551  double val = circpad_distribution_sample(state->iat_dist);
552  /* These comparisons are safe, because the output is in the range
553  * [0, 2**32), and double has a precision of 53 bits. */
554  /* We want a positive sample value */
555  val = MAX(0, val);
556  /* Respect the maximum sample setting */
557  val = MIN(val, state->dist_max_sample_usec);
558 
559  /* Now apply the shift:
560  * This addition is exact: val is at most 2**32-1, delay_shift is at most
561  * 2**32-1, and doubles have a precision of 53 bits. */
562  val += delay_shift;
563 
564  /* Clamp the distribution at infinite delay val */
566 }
567 
568 /**
569  * Sample an expected time-until-next-packet delay from the histogram or
570  * probability distribution.
571  *
572  * A bin of the histogram is chosen with probability proportional to the number
573  * of tokens in each bin, and then a time value is chosen uniformly from that
574  * bin's [start,end) time range.
575  */
578 {
580  const circpad_hist_token_t *histogram = NULL;
581  circpad_hist_index_t curr_bin = 0;
582  circpad_delay_t bin_start, bin_end;
583  /* These three must all be larger than circpad_hist_token_t, because
584  * we sum several circpad_hist_token_t values across the histogram */
585  uint64_t curr_weight = 0;
586  uint64_t histogram_total_tokens = 0;
587  uint64_t bin_choice;
588 
589  tor_assert(state);
590 
591  if (state->iat_dist.type != CIRCPAD_DIST_NONE) {
592  /* Sample from a fixed IAT distribution and return */
593  circpad_delay_t iat_delay_shift = state->use_rtt_estimate ?
594  mi->rtt_estimate_usec + state->dist_added_shift_usec :
595  state->dist_added_shift_usec;
596  return circpad_distribution_sample_iat_delay(state, iat_delay_shift);
597  } else if (circpad_is_token_removal_supported(mi)) {
598  histogram = mi->histogram;
599  for (circpad_hist_index_t b = 0; b < state->histogram_len; b++)
600  histogram_total_tokens += histogram[b];
601  } else {
602  /* We have a histogram, but it's immutable */
603  histogram = state->histogram;
604  histogram_total_tokens = state->histogram_total_tokens;
605  }
606 
607  /* If we are out of tokens, don't schedule padding. */
608  if (!histogram_total_tokens) {
609  return CIRCPAD_DELAY_INFINITE;
610  }
611 
613  histogram_total_tokens);
614 
615  /* Skip all the initial zero bins */
616  while (!histogram[curr_bin]) {
617  curr_bin++;
618  }
619  curr_weight = histogram[curr_bin];
620 
621  // TODO: This is not constant-time. Pretty sure we don't
622  // really need it to be, though.
623  while (curr_weight < bin_choice) {
624  curr_bin++;
625  /* It should be impossible to run past the end of the histogram */
626  if (BUG(curr_bin >= state->histogram_len)) {
627  return CIRCPAD_DELAY_INFINITE;
628  }
629  curr_weight += histogram[curr_bin];
630  }
631 
632  /* Do some basic checking of the current bin we are in */
633  if (BUG(curr_bin >= state->histogram_len) ||
634  BUG(histogram[curr_bin] == 0)) {
635  return CIRCPAD_DELAY_INFINITE;
636  }
637 
638  // Store this index to remove the token upon callback.
640  mi->chosen_bin = curr_bin;
641  }
642 
643  if (curr_bin >= CIRCPAD_INFINITY_BIN(state)) {
645  mi->histogram[curr_bin] > 0) {
646  mi->histogram[curr_bin]--;
647  }
648 
649  // Infinity: Don't send a padding packet. Wait for a real packet
650  // and then see if our bins are empty or what else we should do.
651  return CIRCPAD_DELAY_INFINITE;
652  }
653 
654  tor_assert(curr_bin < CIRCPAD_INFINITY_BIN(state));
655 
656  bin_start = circpad_histogram_bin_to_usec(mi, curr_bin);
657  /* We don't need to reduct 1 from the upper bound because the random range
658  * function below samples from [bin_start, bin_end) */
659  bin_end = circpad_histogram_bin_to_usec(mi, curr_bin+1);
660 
661  /* Bin edges are monotonically increasing so this is a bug. Handle it. */
662  if (BUG(bin_start >= bin_end)) {
663  return bin_start;
664  }
665 
667  bin_start, bin_end);
668 }
669 
670 /**
671  * Sample a value from the specified probability distribution.
672  *
673  * Uses functions from src/lib/math/prob_distr.c .
674  */
675 static double
677 {
678  log_fn(LOG_DEBUG,LD_CIRC, "Sampling delay with distribution %d",
679  dist.type);
680 
681  switch (dist.type) {
682  case CIRCPAD_DIST_NONE:
683  {
684  /* We should not get in here like this */
685  tor_assert_nonfatal_unreached();
686  return 0;
687  }
688  case CIRCPAD_DIST_UNIFORM:
689  {
690  // param2 is upper bound, param1 is lower
691  const struct uniform_t my_uniform = {
692  .base = UNIFORM(my_uniform),
693  .a = dist.param1,
694  .b = dist.param2,
695  };
696  return dist_sample(&my_uniform.base);
697  }
698  case CIRCPAD_DIST_LOGISTIC:
699  {
700  /* param1 is Mu, param2 is sigma. */
701  const struct logistic_t my_logistic = {
702  .base = LOGISTIC(my_logistic),
703  .mu = dist.param1,
704  .sigma = dist.param2,
705  };
706  return dist_sample(&my_logistic.base);
707  }
708  case CIRCPAD_DIST_LOG_LOGISTIC:
709  {
710  /* param1 is Alpha, param2 is 1.0/Beta */
711  const struct log_logistic_t my_log_logistic = {
712  .base = LOG_LOGISTIC(my_log_logistic),
713  .alpha = dist.param1,
714  .beta = dist.param2,
715  };
716  return dist_sample(&my_log_logistic.base);
717  }
718  case CIRCPAD_DIST_GEOMETRIC:
719  {
720  /* param1 is 'p' (success probability) */
721  const struct geometric_t my_geometric = {
722  .base = GEOMETRIC(my_geometric),
723  .p = dist.param1,
724  };
725  return dist_sample(&my_geometric.base);
726  }
727  case CIRCPAD_DIST_WEIBULL:
728  {
729  /* param1 is k, param2 is Lambda */
730  const struct weibull_t my_weibull = {
731  .base = WEIBULL(my_weibull),
732  .k = dist.param1,
733  .lambda = dist.param2,
734  };
735  return dist_sample(&my_weibull.base);
736  }
737  case CIRCPAD_DIST_PARETO:
738  {
739  /* param1 is sigma, param2 is xi, no more params for mu so we use 0 */
740  const struct genpareto_t my_genpareto = {
741  .base = GENPARETO(my_genpareto),
742  .mu = 0,
743  .sigma = dist.param1,
744  .xi = dist.param2,
745  };
746  return dist_sample(&my_genpareto.base);
747  }
748  }
749 
750  tor_assert_nonfatal_unreached();
751  return 0;
752 }
753 
754 /**
755  * Find the index of the first bin whose upper bound is
756  * greater than the target, and that has tokens remaining.
757  *
758  * Used for histograms with token removal.
759  */
762  circpad_delay_t target_bin_usec)
763 {
765  target_bin_usec);
766 
767  /* Don't remove from the infinity bin */
768  for (; bin < CIRCPAD_INFINITY_BIN(mi); bin++) {
769  if (mi->histogram[bin] &&
770  histogram_get_bin_upper_bound(mi, bin) >= target_bin_usec) {
771  return bin;
772  }
773  }
774 
775  return mi->histogram_len;
776 }
777 
778 /**
779  * Find the index of the first bin whose lower bound is lower or equal to
780  * <b>target_bin_usec</b>, and that still has tokens remaining.
781  *
782  * Used for histograms with token removal.
783  */
786  circpad_delay_t target_bin_usec)
787 {
789  target_bin_usec);
790 
791  for (; bin >= 0; bin--) {
792  if (mi->histogram[bin] &&
793  circpad_histogram_bin_to_usec(mi, bin) <= target_bin_usec) {
794  return bin;
795  }
796  }
797 
798  return -1;
799 }
800 
801 /**
802  * Remove a token from the first non-empty bin whose upper bound is
803  * greater than the target.
804  *
805  * Used for histograms with token removal.
806  */
807 STATIC void
809  circpad_delay_t target_bin_usec)
810 {
811  /* We need to remove the token from the first bin
812  * whose upper bound is greater than the target, and that
813  * has tokens remaining. */
815  target_bin_usec);
816 
817  if (bin >= 0 && bin < CIRCPAD_INFINITY_BIN(mi)) {
818  if (!BUG(mi->histogram[bin] == 0)) {
819  mi->histogram[bin]--;
820  }
821  }
822 }
823 
824 /**
825  * Remove a token from the first non-empty bin whose upper bound is
826  * lower than the target.
827  *
828  * Used for histograms with token removal.
829  */
830 STATIC void
832  circpad_delay_t target_bin_usec)
833 {
835  target_bin_usec);
836 
837  if (bin >= 0 && bin < CIRCPAD_INFINITY_BIN(mi)) {
838  if (!BUG(mi->histogram[bin] == 0)) {
839  mi->histogram[bin]--;
840  }
841  }
842 }
843 
844 /* Helper macro: Ensure that the bin has tokens available, and BUG out of the
845  * function if it's not the case. */
846 #define ENSURE_BIN_CAPACITY(bin_index) \
847  if (BUG(mi->histogram[bin_index] == 0)) { \
848  return; \
849  }
850 
851 /**
852  * Remove a token from the closest non-empty bin to the target.
853  *
854  * If use_usec is true, measure "closest" in terms of the next closest bin
855  * midpoint.
856  *
857  * If it is false, use bin index distance only.
858  *
859  * Used for histograms with token removal.
860  */
861 STATIC void
863  circpad_delay_t target_bin_usec,
864  bool use_usec)
865 {
866  circpad_hist_index_t lower, higher, current;
867  circpad_hist_index_t bin_to_remove = -1;
868 
869  lower = circpad_machine_first_lower_index(mi, target_bin_usec);
870  higher = circpad_machine_first_higher_index(mi, target_bin_usec);
871  current = circpad_histogram_usec_to_bin(mi, target_bin_usec);
872 
873  /* Sanity check the results */
874  if (BUG(lower > current) || BUG(higher < current)) {
875  return;
876  }
877 
878  /* Take care of edge cases first */
879  if (higher == mi->histogram_len && lower == -1) {
880  /* All bins are empty */
881  return;
882  } else if (higher == mi->histogram_len) {
883  /* All higher bins are empty */
884  ENSURE_BIN_CAPACITY(lower);
885  mi->histogram[lower]--;
886  return;
887  } else if (lower == -1) {
888  /* All lower bins are empty */
889  ENSURE_BIN_CAPACITY(higher);
890  mi->histogram[higher]--;
891  return;
892  }
893 
894  /* Now handle the intermediate cases */
895  if (use_usec) {
896  /* Find the closest bin midpoint to the target */
897  circpad_delay_t lower_usec = circpad_get_histogram_bin_midpoint(mi, lower);
898  circpad_delay_t higher_usec =
900 
901  if (target_bin_usec < lower_usec) {
902  // Lower bin is closer
903  ENSURE_BIN_CAPACITY(lower);
904  bin_to_remove = lower;
905  } else if (target_bin_usec > higher_usec) {
906  // Higher bin is closer
907  ENSURE_BIN_CAPACITY(higher);
908  bin_to_remove = higher;
909  } else if (target_bin_usec-lower_usec > higher_usec-target_bin_usec) {
910  // Higher bin is closer
911  ENSURE_BIN_CAPACITY(higher);
912  bin_to_remove = higher;
913  } else {
914  // Lower bin is closer
915  ENSURE_BIN_CAPACITY(lower);
916  bin_to_remove = lower;
917  }
918  mi->histogram[bin_to_remove]--;
919  log_debug(LD_CIRC, "Removing token from bin %d", bin_to_remove);
920  return;
921  } else {
922  if (current - lower > higher - current) {
923  // Higher bin is closer
924  ENSURE_BIN_CAPACITY(higher);
925  mi->histogram[higher]--;
926  return;
927  } else {
928  // Lower bin is closer
929  ENSURE_BIN_CAPACITY(lower);
930  mi->histogram[lower]--;
931  return;
932  }
933  }
934 }
935 
936 #undef ENSURE_BIN_CAPACITY
937 
938 /**
939  * Remove a token from the exact bin corresponding to the target.
940  *
941  * If it is empty, do nothing.
942  *
943  * Used for histograms with token removal.
944  */
945 static void
947  circpad_delay_t target_bin_usec)
948 {
950  target_bin_usec);
951 
952  if (mi->histogram[bin] > 0)
953  mi->histogram[bin]--;
954 }
955 
956 /**
957  * Check our state's cell limit count and tokens.
958  *
959  * Returns 1 if either limits are hit and we decide to change states,
960  * otherwise returns 0.
961  */
962 static circpad_decision_t
964 {
965  uint32_t histogram_total_tokens = 0;
966 
967  /* Check if bins empty. This requires summing up the current mutable
968  * machineinfo histogram token total and checking if it is zero.
969  * Machineinfo does not keep a running token count. We're assuming the
970  * extra space is not worth this short loop iteration.
971  *
972  * We also do not count infinity bin in histogram totals.
973  */
975  for (circpad_hist_index_t b = 0; b < CIRCPAD_INFINITY_BIN(mi); b++)
976  histogram_total_tokens += mi->histogram[b];
977 
978  /* If we change state, we're done */
979  if (histogram_total_tokens == 0) {
980  if (circpad_internal_event_bins_empty(mi) == CIRCPAD_STATE_CHANGED)
981  return CIRCPAD_STATE_CHANGED;
982  }
983  }
984 
985  if (mi->state_length == 0) {
987  }
988 
989  return CIRCPAD_STATE_UNCHANGED;
990 }
991 
992 /**
993  * Count that a padding packet was sent.
994  *
995  * This updates our state length count, our machine rate limit counts,
996  * and if token removal is used, decrements the histogram.
997  */
998 static inline void
1000 {
1001  /* If we have a valid state length bound, consider it */
1002  if (mi->state_length != CIRCPAD_STATE_LENGTH_INFINITE &&
1003  !BUG(mi->state_length <= 0)) {
1004  mi->state_length--;
1005  }
1006 
1007  /*
1008  * Update non-padding counts for rate limiting: We scale at UINT16_MAX
1009  * because we only use this for a percentile limit of 2 sig figs, and
1010  * space is scare in the machineinfo struct.
1011  */
1012  mi->padding_sent++;
1013  if (mi->padding_sent == UINT16_MAX) {
1014  mi->padding_sent /= 2;
1015  mi->nonpadding_sent /= 2;
1016  }
1017 
1019 
1020  /* If we have a mutable histogram, reduce the token count from
1021  * the chosen padding bin (this assumes we always send padding
1022  * when we intended to). */
1024  /* Check array bounds and token count before removing */
1025  if (!BUG(mi->chosen_bin >= mi->histogram_len) &&
1026  !BUG(mi->histogram[mi->chosen_bin] == 0)) {
1027  mi->histogram[mi->chosen_bin]--;
1028  }
1029  }
1030 }
1031 
1032 /**
1033  * Count a nonpadding packet as being sent.
1034  *
1035  * This function updates our overhead accounting variables, as well
1036  * as decrements the state limit packet counter, if the latter was
1037  * flagged as applying to non-padding as well.
1038  */
1039 static inline void
1041 {
1042  /* Update non-padding counts for rate limiting: We scale at UINT16_MAX
1043  * because we only use this for a percentile limit of 2 sig figs, and
1044  * space is scare in the machineinfo struct. */
1045  mi->nonpadding_sent++;
1046  if (mi->nonpadding_sent == UINT16_MAX) {
1047  mi->padding_sent /= 2;
1048  mi->nonpadding_sent /= 2;
1049  }
1050 
1051  /* Update any state packet length limits that apply */
1053 
1054  /* Remove a token from the histogram, if applicable */
1056 }
1057 
1058 /**
1059  * Decrement the state length counter for a non-padding packet.
1060  *
1061  * Only updates the state length if we're using that feature, we
1062  * have a state, and the machine wants to count non-padding packets
1063  * towards the state length.
1064  */
1065 static inline void
1068 {
1069  const circpad_state_t *state = NULL;
1070 
1071  if (mi->state_length == CIRCPAD_STATE_LENGTH_INFINITE)
1072  return;
1073 
1074  state = circpad_machine_current_state(mi);
1075 
1076  /* If we are not in a padding state (like start or end), we're done */
1077  if (!state)
1078  return;
1079 
1080  /* If we're enforcing a state length on non-padding packets,
1081  * decrement it */
1082  if (state->length_includes_nonpadding &&
1083  mi->state_length > 0) {
1084  mi->state_length--;
1085  }
1086 }
1087 
1088 /**
1089  * When a non-padding packet arrives, remove a token from the bin
1090  * corresponding to the delta since last sent packet. If that bin
1091  * is empty, choose a token based on the specified removal strategy
1092  * in the state machine.
1093  */
1094 STATIC void
1096 {
1097  const circpad_state_t *state = NULL;
1098  circpad_time_t current_time;
1099  circpad_delay_t target_bin_usec;
1100 
1101  /* Dont remove any tokens if there was no padding scheduled */
1102  if (!mi->padding_scheduled_at_usec) {
1103  return;
1104  }
1105 
1106  state = circpad_machine_current_state(mi);
1107 
1108  /* If we are not in a padding state (like start or end), we're done */
1109  if (!state)
1110  return;
1111  /* Don't remove any tokens if we're not doing token removal */
1113  return;
1114 
1115  current_time = monotime_absolute_usec();
1116 
1117  /* If we have scheduled padding some time in the future, we want to see what
1118  bin we are in at the current time */
1119  target_bin_usec = (circpad_delay_t)
1120  MIN((current_time - mi->padding_scheduled_at_usec),
1122 
1123  /* We are treating this non-padding cell as a padding cell, so we cancel
1124  padding timer, if present. */
1125  mi->padding_scheduled_at_usec = 0;
1126  if (mi->is_padding_timer_scheduled) {
1129  }
1130 
1131  /* Perform the specified token removal strategy */
1132  switch (state->token_removal) {
1134  circpad_machine_remove_closest_token(mi, target_bin_usec, 1);
1135  break;
1137  circpad_machine_remove_closest_token(mi, target_bin_usec, 0);
1138  break;
1140  circpad_machine_remove_lower_token(mi, target_bin_usec);
1141  break;
1143  circpad_machine_remove_higher_token(mi, target_bin_usec);
1144  break;
1146  circpad_machine_remove_exact(mi, target_bin_usec);
1147  break;
1149  default:
1150  tor_assert_nonfatal_unreached();
1151  log_warn(LD_BUG, "Circpad: Unknown token removal strategy %d",
1152  state->token_removal);
1153  break;
1154  }
1155 }
1156 
1157 /**
1158  * Send a relay command with a relay cell payload on a circuit to
1159  * the particular hopnum.
1160  *
1161  * Hopnum starts at 1 (1=guard, 2=middle, 3=exit, etc).
1162  *
1163  * Payload may be null.
1164  *
1165  * Returns negative on error, 0 on success.
1166  */
1168 circpad_send_command_to_hop,(origin_circuit_t *circ, uint8_t hopnum,
1169  uint8_t relay_command, const uint8_t *payload,
1170  ssize_t payload_len))
1171 {
1172  crypt_path_t *target_hop = circuit_get_cpath_hop(circ, hopnum);
1173  signed_error_t ret;
1174 
1175  /* Check that the cpath has the target hop */
1176  if (!target_hop) {
1177  log_fn(LOG_WARN, LD_BUG, "Padding circuit %u has %d hops, not %d",
1178  circ->global_identifier, circuit_get_cpath_len(circ), hopnum);
1179  return -1;
1180  }
1181 
1182  /* Check that the target hop is opened */
1183  if (target_hop->state != CPATH_STATE_OPEN) {
1185  "Padding circuit %u has %d hops, not %d",
1186  circ->global_identifier,
1187  circuit_get_cpath_opened_len(circ), hopnum);
1188  return -1;
1189  }
1190 
1191  /* Send the drop command to the second hop */
1192  ret = relay_send_command_from_edge(0, TO_CIRCUIT(circ), relay_command,
1193  (const char*)payload, payload_len,
1194  target_hop);
1195  return ret;
1196 }
1197 
1198 /**
1199  * Callback helper to send a padding cell.
1200  *
1201  * This helper is called after our histogram-sampled delay period passes
1202  * without another packet being sent first. If a packet is sent before this
1203  * callback happens, it is canceled. So when we're called here, send padding
1204  * right away.
1205  *
1206  * If sending this padding cell forced us to transition states return
1207  * CIRCPAD_STATE_CHANGED. Otherwise return CIRCPAD_STATE_UNCHANGED.
1208  */
1211 {
1212  circuit_t *circ = mi->on_circ;
1213  int machine_idx = mi->machine_index;
1214  mi->padding_scheduled_at_usec = 0;
1215  circpad_statenum_t state = mi->current_state;
1216 
1217  /* Make sure circuit didn't close on us */
1218  if (mi->on_circ->marked_for_close) {
1220  "Padding callback on circuit marked for close (%u). Ignoring.",
1221  CIRCUIT_IS_ORIGIN(mi->on_circ) ?
1223  return CIRCPAD_STATE_CHANGED;
1224  }
1225 
1227 
1228  if (CIRCUIT_IS_ORIGIN(mi->on_circ)) {
1230  CIRCPAD_GET_MACHINE(mi)->target_hopnum,
1231  RELAY_COMMAND_DROP, NULL, 0);
1232  log_info(LD_CIRC, "Callback: Sending padding to origin circuit %u"
1233  " (%d) [length: %"PRIu64"]",
1235  mi->on_circ->purpose, mi->state_length);
1236  } else {
1237  // If we're a non-origin circ, we can just send from here as if we're the
1238  // edge.
1239  if (TO_OR_CIRCUIT(circ)->p_chan_cells.n <= circpad_max_circ_queued_cells) {
1240  log_info(LD_CIRC, "Callback: Sending padding to circuit (%d)"
1241  " [length: %"PRIu64"]", mi->on_circ->purpose, mi->state_length);
1242  relay_send_command_from_edge(0, mi->on_circ, RELAY_COMMAND_DROP, NULL,
1243  0, NULL);
1245  } else {
1246  static ratelim_t cell_lim = RATELIM_INIT(600);
1247  log_fn_ratelim(&cell_lim,LOG_NOTICE,LD_CIRC,
1248  "Too many cells (%d) in circ queue to send padding.",
1249  TO_OR_CIRCUIT(circ)->p_chan_cells.n);
1250  }
1251  }
1252 
1253  /* This is a padding cell sent from the client or from the middle node,
1254  * (because it's invoked from circuitpadding.c) */
1256 
1257  /* The circpad_cell_event_padding_sent() could cause us to transition.
1258  * Check that we still have a padding machineinfo, and then check our token
1259  * supply. */
1260  if (circ->padding_info[machine_idx] != NULL) {
1261  if (state != circ->padding_info[machine_idx]->current_state)
1262  return CIRCPAD_STATE_CHANGED;
1263  else
1264  return check_machine_token_supply(circ->padding_info[machine_idx]);
1265  } else {
1266  return CIRCPAD_STATE_CHANGED;
1267  }
1268 }
1269 
1270 /**
1271  * Tor-timer compatible callback that tells us to send a padding cell.
1272  *
1273  * Timers are associated with circpad_machine_runtime_t's. When the machineinfo
1274  * is freed on a circuit, the timers are cancelled. Since the lifetime
1275  * of machineinfo is always longer than the timers, handles are not
1276  * needed.
1277  */
1278 static void
1279 circpad_send_padding_callback(tor_timer_t *timer, void *args,
1280  const struct monotime_t *time)
1281 {
1283  (void)timer; (void)time;
1284 
1285  if (mi && mi->on_circ) {
1288  } else {
1289  // This shouldn't happen (represents a timer leak)
1291  "Circuit closed while waiting for padding timer.");
1293  }
1294 
1295  // TODO-MP-AP: Unify this counter with channelpadding for rephist stats
1296  //total_timers_pending--;
1297 }
1298 
1299 /**
1300  * Cache our consensus parameters upon consensus update.
1301  */
1302 void
1304 {
1306  networkstatus_get_param(ns, "circpad_padding_disabled",
1307  0, 0, 1);
1308 
1309  circpad_padding_reduced =
1310  networkstatus_get_param(ns, "circpad_padding_reduced",
1311  0, 0, 1);
1312 
1313  circpad_global_allowed_cells =
1314  networkstatus_get_param(ns, "circpad_global_allowed_cells",
1315  0, 0, UINT16_MAX-1);
1316 
1317  circpad_global_max_padding_percent =
1318  networkstatus_get_param(ns, "circpad_global_max_padding_pct",
1319  0, 0, 100);
1320 
1321  circpad_max_circ_queued_cells =
1322  networkstatus_get_param(ns, "circpad_max_circ_queued_cells",
1323  CIRCWINDOW_START_MAX, 0, 50*CIRCWINDOW_START_MAX);
1324 }
1325 
1326 /**
1327  * Return true if padding is allowed by torrc and consensus.
1328  */
1329 static bool
1331 {
1332  /* If padding has been disabled in the consensus, don't send any more
1333  * padding. Technically the machine should be shut down when the next
1334  * machine condition check happens, but machine checks only happen on
1335  * certain circuit events, and if padding is disabled due to some
1336  * network overload or DoS condition, we really want to stop ASAP. */
1337  if (circpad_padding_disabled || !get_options()->CircuitPadding) {
1338  return 0;
1339  }
1340 
1341  return 1;
1342 }
1343 
1344 /**
1345  * Check this machine against its padding limits, as well as global
1346  * consensus limits.
1347  *
1348  * We have two limits: a percent and a cell count. The cell count
1349  * limit must be reached before the percent is enforced (this is to
1350  * optionally allow very light padding of things like circuit setup
1351  * while there is no other traffic on the circuit).
1352  *
1353  * TODO: Don't apply limits to machines form torrc.
1354  *
1355  * Returns 1 if limits are set and we've hit them. Otherwise returns 0.
1356  */
1357 STATIC bool
1359 {
1360  const circpad_machine_spec_t *machine = CIRCPAD_GET_MACHINE(mi);
1361 
1362  /* If machine_padding_pct is non-zero, and we've sent more
1363  * than the allowed count of padding cells, then check our
1364  * percent limits for this machine. */
1365  if (machine->max_padding_percent &&
1366  mi->padding_sent >= machine->allowed_padding_count) {
1367  uint32_t total_cells = mi->padding_sent + mi->nonpadding_sent;
1368 
1369  /* Check the percent */
1370  if ((100*(uint32_t)mi->padding_sent) / total_cells >
1371  machine->max_padding_percent) {
1372  return 1; // limit is reached. Stop.
1373  }
1374  }
1375 
1376  /* If circpad_max_global_padding_pct is non-zero, and we've
1377  * sent more than the global padding cell limit, then check our
1378  * global tor process percentage limit on padding. */
1379  if (circpad_global_max_padding_percent &&
1380  circpad_global_padding_sent >= circpad_global_allowed_cells) {
1381  uint64_t total_cells = circpad_global_padding_sent +
1382  circpad_global_nonpadding_sent;
1383 
1384  /* Check the percent */
1385  if ((100*circpad_global_padding_sent) / total_cells >
1386  circpad_global_max_padding_percent) {
1387  return 1; // global limit reached. Stop.
1388  }
1389  }
1390 
1391  return 0; // All good!
1392 }
1393 
1394 /**
1395  * Schedule the next padding time according to the machineinfo on a
1396  * circuit.
1397  *
1398  * The histograms represent inter-packet-delay. Whenever you get an packet
1399  * event you should be scheduling your next timer (after cancelling any old
1400  * ones and updating tokens accordingly).
1401  *
1402  * Returns 1 if we decide to transition states (due to infinity bin),
1403  * 0 otherwise.
1404  */
1407 {
1408  circpad_delay_t in_usec = 0;
1409  struct timeval timeout;
1410  tor_assert(mi);
1411 
1412  /* Don't schedule padding if it is disabled */
1413  if (!circpad_is_padding_allowed()) {
1414  static ratelim_t padding_lim = RATELIM_INIT(600);
1415  log_fn_ratelim(&padding_lim,LOG_INFO,LD_CIRC,
1416  "Padding has been disabled, but machine still on circuit %"PRIu64
1417  ", %d",
1418  mi->on_circ->n_chan ? mi->on_circ->n_chan->global_identifier : 0,
1419  mi->on_circ->n_circ_id);
1420 
1421  return CIRCPAD_STATE_UNCHANGED;
1422  }
1423 
1424  /* Don't schedule padding if we are currently in dormant mode. */
1425  if (!is_participating_on_network()) {
1426  log_info(LD_CIRC, "Not scheduling padding because we are dormant.");
1427  return CIRCPAD_STATE_UNCHANGED;
1428  }
1429 
1430  // Don't pad in end (but also don't cancel any previously
1431  // scheduled padding either).
1432  if (mi->current_state == CIRCPAD_STATE_END) {
1433  log_fn(LOG_INFO, LD_CIRC, "Padding end state on circuit %u",
1434  CIRCUIT_IS_ORIGIN(mi->on_circ) ?
1436  return CIRCPAD_STATE_UNCHANGED;
1437  }
1438 
1439  /* Check our padding limits */
1441  if (CIRCUIT_IS_ORIGIN(mi->on_circ)) {
1443  "Padding machine has reached padding limit on circuit %u",
1445  } else {
1446  static ratelim_t padding_lim = RATELIM_INIT(600);
1447  log_fn_ratelim(&padding_lim,LOG_INFO,LD_CIRC,
1448  "Padding machine has reached padding limit on circuit %"PRIu64
1449  ", %d",
1450  mi->on_circ->n_chan ? mi->on_circ->n_chan->global_identifier : 0,
1451  mi->on_circ->n_circ_id);
1452  }
1453  return CIRCPAD_STATE_UNCHANGED;
1454  }
1455 
1456  if (mi->is_padding_timer_scheduled) {
1457  /* Cancel current timer (if any) */
1460  }
1461 
1462  /* in_usec = in microseconds */
1463  in_usec = circpad_machine_sample_delay(mi);
1464  /* If we're using token removal, we need to know when the padding
1465  * was scheduled at, so we can remove the appropriate token if
1466  * a non-padding cell is sent before the padding timer expires.
1467  *
1468  * However, since monotime is unpredictably expensive, let's avoid
1469  * using it for machines that don't need token removal. */
1472  } else {
1473  mi->padding_scheduled_at_usec = 1;
1474  }
1475  log_fn(LOG_INFO,LD_CIRC,"\tPadding in %u usec on circuit %u", in_usec,
1476  CIRCUIT_IS_ORIGIN(mi->on_circ) ?
1478 
1479  // Don't schedule if we have infinite delay.
1480  if (in_usec == CIRCPAD_DELAY_INFINITE) {
1482  }
1483 
1484  if (mi->state_length == 0) {
1485  /* If we're at length 0, that means we hit 0 after sending
1486  * a cell earlier, and emitted an event for it, but
1487  * for whatever reason we did not decide to change states then.
1488  * So maybe the machine is waiting for bins empty, or for an
1489  * infinity event later? That would be a strange machine,
1490  * but there's no reason to make it impossible. */
1491  return CIRCPAD_STATE_UNCHANGED;
1492  }
1493 
1494  if (in_usec <= 0) {
1496  }
1497 
1498  timeout.tv_sec = in_usec/TOR_USEC_PER_SEC;
1499  timeout.tv_usec = (in_usec%TOR_USEC_PER_SEC);
1500 
1501  log_fn(LOG_INFO, LD_CIRC, "\tPadding circuit %u in %u sec, %u usec",
1502  CIRCUIT_IS_ORIGIN(mi->on_circ) ?
1504  (unsigned)timeout.tv_sec, (unsigned)timeout.tv_usec);
1505 
1506  if (mi->padding_timer) {
1508  } else {
1509  mi->padding_timer =
1511  }
1512  timer_schedule(mi->padding_timer, &timeout);
1514 
1515  // TODO-MP-AP: Unify with channelpadding counter
1516  //rep_hist_padding_count_timers(++total_timers_pending);
1517 
1518  return CIRCPAD_STATE_UNCHANGED;
1519 }
1520 
1521 /**
1522  * If the machine transitioned to the END state, we need
1523  * to check to see if it wants us to shut it down immediately.
1524  * If it does, then we need to send the appropiate negotiation commands
1525  * depending on which side it is.
1526  *
1527  * After this function is called, mi may point to freed memory. Do
1528  * not access it.
1529  */
1530 static void
1532 {
1533  const circpad_machine_spec_t *machine = CIRCPAD_GET_MACHINE(mi);
1534  circuit_t *on_circ = mi->on_circ;
1535 
1536  log_fn(LOG_INFO,LD_CIRC, "Padding machine in end state on circuit %u (%d)",
1537  CIRCUIT_IS_ORIGIN(on_circ) ?
1538  TO_ORIGIN_CIRCUIT(on_circ)->global_identifier : 0,
1539  on_circ->purpose);
1540 
1541  /*
1542  * We allow machines to shut down and delete themselves as opposed
1543  * to just going back to START or waiting forever in END so that
1544  * we can handle the case where this machine started while it was
1545  * the only machine that matched conditions, but *since* then more
1546  * "higher ranking" machines now match the conditions, and would
1547  * be given a chance to take precedence over this one in
1548  * circpad_add_matching_machines().
1549  *
1550  * Returning to START or waiting forever in END would not give those
1551  * other machines a chance to be launched, where as shutting down
1552  * here does.
1553  */
1554  if (machine->should_negotiate_end) {
1555  if (machine->is_origin_side) {
1556  /* We free the machine info here so that we can be replaced
1557  * by a different machine. But we must leave the padding_machine
1558  * in place to wait for the negotiated response */
1560  machine->machine_index);
1562  machine->machine_num,
1563  machine->target_hopnum,
1564  CIRCPAD_COMMAND_STOP);
1565  } else {
1567  machine->machine_index);
1569  machine->machine_num,
1570  CIRCPAD_COMMAND_STOP,
1571  CIRCPAD_RESPONSE_OK);
1572  on_circ->padding_machine[machine->machine_index] = NULL;
1573  }
1574  }
1575 }
1576 
1577 /**
1578  * Generic state transition function for padding state machines.
1579  *
1580  * Given an event and our mutable machine info, decide if/how to
1581  * transition to a different state, and perform actions accordingly.
1582  *
1583  * Returns 1 if we transition states, 0 otherwise.
1584  */
1588 {
1589  const circpad_state_t *state =
1591 
1592  /* If state is null we are in the end state. */
1593  if (!state) {
1594  /* If we in end state we don't pad no matter what. */
1595  return CIRCPAD_STATE_UNCHANGED;
1596  }
1597 
1598  /* Check if this event is ignored or causes a cancel */
1599  if (state->next_state[event] == CIRCPAD_STATE_IGNORE) {
1600  return CIRCPAD_STATE_UNCHANGED;
1601  } else if (state->next_state[event] == CIRCPAD_STATE_CANCEL) {
1602  /* Check cancel events and cancel any pending padding */
1603  mi->padding_scheduled_at_usec = 0;
1604  if (mi->is_padding_timer_scheduled) {
1606  /* Cancel current timer (if any) */
1608  }
1609  return CIRCPAD_STATE_UNCHANGED;
1610  } else {
1611  circpad_statenum_t s = state->next_state[event];
1612  /* See if we need to transition to any other states based on this event.
1613  * Whenever a transition happens, even to our own state, we schedule
1614  * padding.
1615  *
1616  * So if a state only wants to schedule padding for an event, it specifies
1617  * a transition to itself. All non-specified events are ignored.
1618  */
1620  "Circuit %u circpad machine %d transitioning from %u to %u",
1621  CIRCUIT_IS_ORIGIN(mi->on_circ) ?
1623  mi->machine_index, mi->current_state, s);
1624 
1625  /* If this is not the same state, switch and init tokens,
1626  * otherwise just reschedule padding. */
1627  if (mi->current_state != s) {
1628  mi->current_state = s;
1631 
1632  /* If we transition to the end state, check to see
1633  * if this machine wants to be shut down at end */
1634  if (s == CIRCPAD_STATE_END) {
1636  /* We transitioned but we don't pad in end. Also, mi
1637  * may be freed. Returning STATE_CHANGED prevents us
1638  * from accessing it in any callers of this function. */
1639  return CIRCPAD_STATE_CHANGED;
1640  }
1641 
1642  /* We transitioned to a new state, schedule padding */
1644  return CIRCPAD_STATE_CHANGED;
1645  }
1646 
1647  /* We transitioned back to the same state. Schedule padding,
1648  * and inform if that causes a state transition. */
1650  }
1651 
1652  return CIRCPAD_STATE_UNCHANGED;
1653 }
1654 
1655 /**
1656  * Estimate the circuit RTT from the current middle hop out to the
1657  * end of the circuit.
1658  *
1659  * We estimate RTT by calculating the time between "receive" and
1660  * "send" at a middle hop. This is because we "receive" a cell
1661  * from the origin, and then relay it towards the exit before a
1662  * response comes back. It is that response time from the exit side
1663  * that we want to measure, so that we can make use of it for synthetic
1664  * response delays.
1665  */
1666 static void
1669 {
1670  /* Origin circuits don't estimate RTT. They could do it easily enough,
1671  * but they have no reason to use it in any delay calculations. */
1672  if (CIRCUIT_IS_ORIGIN(circ) || mi->stop_rtt_update)
1673  return;
1674 
1675  /* If we already have a last received packet time, that means we
1676  * did not get a response before this packet. The RTT estimate
1677  * only makes sense if we do not have multiple packets on the
1678  * wire, so stop estimating if this is the second packet
1679  * back to back. However, for the first set of back-to-back
1680  * packets, we can wait until the very first response comes back
1681  * to us, to measure that RTT (for the response to optimistic
1682  * data, for example). Hence stop_rtt_update is only checked
1683  * in this received side function, and not in send side below.
1684  */
1685  if (mi->last_received_time_usec) {
1686  /* We also allow multiple back-to-back packets if the circuit is not
1687  * opened, to handle var cells.
1688  * XXX: Will this work with out var cell plans? Maybe not,
1689  * since we're opened at the middle hop as soon as we process
1690  * one var extend2 :/ */
1691  if (circ->state == CIRCUIT_STATE_OPEN) {
1693  "Stopping padding RTT estimation on circuit (%"PRIu64
1694  ", %d) after two back to back packets. Current RTT: %d",
1695  circ->n_chan ? circ->n_chan->global_identifier : 0,
1696  circ->n_circ_id, mi->rtt_estimate_usec);
1697  mi->stop_rtt_update = 1;
1698 
1699  if (!mi->rtt_estimate_usec) {
1700  static ratelim_t rtt_lim = RATELIM_INIT(600);
1701  log_fn_ratelim(&rtt_lim,LOG_NOTICE,LD_BUG,
1702  "Circuit got two cells back to back before estimating RTT.");
1703  }
1704  }
1705  } else {
1707  if (BUG(!state)) {
1708  return;
1709  }
1710 
1711  /* Since monotime is unpredictably expensive, only update this field
1712  * if rtt estimates are needed. Otherwise, stop the rtt update. */
1713  if (state->use_rtt_estimate) {
1715  } else {
1716  /* Let's fast-path future decisions not to update rtt if the
1717  * feature is not in use. */
1718  mi->stop_rtt_update = 1;
1719  }
1720  }
1721 }
1722 
1723 /**
1724  * Handles the "send" side of RTT calculation at middle nodes.
1725  *
1726  * This function calculates the RTT from the middle to the end
1727  * of the circuit by subtracting the last received cell timestamp
1728  * from the current time. It allows back-to-back cells until
1729  * the circuit is opened, to allow for var cell handshakes.
1730  * XXX: Check our var cell plans to make sure this will work.
1731  */
1732 static void
1735 {
1736  /* Origin circuits don't estimate RTT. They could do it easily enough,
1737  * but they have no reason to use it in any delay calculations. */
1738  if (CIRCUIT_IS_ORIGIN(circ))
1739  return;
1740 
1741  /* If last_received_time_usec is non-zero, we are waiting for a response
1742  * from the exit side. Calculate the time delta and use it as RTT. */
1743  if (mi->last_received_time_usec) {
1744  circpad_time_t rtt_time = monotime_absolute_usec() -
1746 
1747  /* Reset the last RTT packet time, so we can tell if two cells
1748  * arrive back to back */
1749  mi->last_received_time_usec = 0;
1750 
1751  /* Use INT32_MAX to ensure the addition doesn't overflow */
1752  if (rtt_time >= INT32_MAX) {
1754  "Circuit padding RTT estimate overflowed: %"PRIu64
1755  " vs %"PRIu64, monotime_absolute_usec(),
1757  return;
1758  }
1759 
1760  /* If the old RTT estimate is lower than this one, use this one, because
1761  * the circuit is getting longer. If this estimate is somehow
1762  * faster than the previous, then maybe that was network jitter, or a
1763  * bad monotonic clock source (so our ratchet returned a zero delta).
1764  * In that case, average them. */
1765  if (mi->rtt_estimate_usec < (circpad_delay_t)rtt_time) {
1766  mi->rtt_estimate_usec = (circpad_delay_t)rtt_time;
1767  } else {
1768  mi->rtt_estimate_usec += (circpad_delay_t)rtt_time;
1769  mi->rtt_estimate_usec /= 2;
1770  }
1771  } else if (circ->state == CIRCUIT_STATE_OPEN) {
1772  /* If last_received_time_usec is zero, then we have gotten two cells back
1773  * to back. Stop estimating RTT in this case. Note that we only
1774  * stop RTT update if the circuit is opened, to allow for RTT estimates
1775  * of var cells during circ setup. */
1776  if (!mi->rtt_estimate_usec && !mi->stop_rtt_update) {
1777  static ratelim_t rtt_lim = RATELIM_INIT(600);
1778  log_fn_ratelim(&rtt_lim,LOG_NOTICE,LD_BUG,
1779  "Circuit sent two cells back to back before estimating RTT.");
1780  }
1781  mi->stop_rtt_update = 1;
1782  }
1783 }
1784 
1785 /**
1786  * A "non-padding" cell has been sent from this endpoint. React
1787  * according to any padding state machines on the circuit.
1788  *
1789  * For origin circuits, this means we sent a cell into the network.
1790  * For middle relay circuits, this means we sent a cell towards the
1791  * origin.
1792  */
1793 void
1795 {
1796  /* Update global cell count */
1797  circpad_global_nonpadding_sent++;
1798 
1799  /* If there are no machines then this loop should not iterate */
1801  /* First, update any timestamps */
1802  on_circ->padding_info[i]->last_cell_time_sec = approx_time();
1803  circpad_estimate_circ_rtt_on_send(on_circ, on_circ->padding_info[i]);
1804 
1805  /* Then, do accounting */
1807 
1808  /* Check to see if we've run out of tokens for this state already,
1809  * and if not, check for other state transitions */
1810  if (check_machine_token_supply(on_circ->padding_info[i])
1811  == CIRCPAD_STATE_UNCHANGED) {
1812  /* If removing a token did not cause a transition, check if
1813  * non-padding sent event should */
1815  CIRCPAD_EVENT_NONPADDING_SENT);
1816  }
1817  } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
1818 }
1819 
1820 /** Check if this cell or circuit are related to circuit padding and handle
1821  * them if so. Return 0 if the cell was handled in this subsystem and does
1822  * not need any other consideration, otherwise return 1.
1823  */
1824 int
1826  crypt_path_t *layer_hint,
1827  const relay_header_t *rh)
1828 {
1829  /* First handle the padding commands, since we want to ignore any other
1830  * commands if this circuit is padding-specific. */
1831  switch (rh->command) {
1832  case RELAY_COMMAND_DROP:
1833  /* Already examined in circpad_deliver_recognized_relay_cell_events */
1834  return 0;
1835  case RELAY_COMMAND_PADDING_NEGOTIATE:
1837  return 0;
1838  case RELAY_COMMAND_PADDING_NEGOTIATED:
1839  if (circpad_handle_padding_negotiated(circ, cell, layer_hint) == 0)
1841  return 0;
1842  }
1843 
1844  /* If this is a padding circuit we don't need to parse any other commands
1845  * than the padding ones. Just drop them to the floor.
1846  *
1847  * Note: we deliberately do not call circuit_read_valid_data() here. The
1848  * vanguards addon (specifically the 'bandguards' component's dropped cell
1849  * detection) will thus close this circuit, as it would for any other
1850  * unexpected cell. However, default tor will *not* close the circuit.
1851  *
1852  * This is intentional. We are not yet certain that is it optimal to keep
1853  * padding circuits open in cases like these, rather than closing them.
1854  * We suspect that continuing to pad is optimal against a passive classifier,
1855  * but as soon as the adversary is active (even as a client adversary) this
1856  * might change.
1857  *
1858  * So as a way forward, we log the cell command and circuit number, to
1859  * help us enumerate the most common instances of this in testing with
1860  * vanguards, to see which are common enough to verify and handle
1861  * properly.
1862  * - Mike
1863  */
1865  log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
1866  "Ignored cell (%d) that arrived in padding circuit "
1867  " %u.", rh->command, CIRCUIT_IS_ORIGIN(circ) ?
1868  TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0);
1869  return 0;
1870  }
1871 
1872  return 1;
1873 }
1874 
1875 /**
1876  * A "non-padding" cell has been received by this endpoint. React
1877  * according to any padding state machines on the circuit.
1878  *
1879  * For origin circuits, this means we read a cell from the network.
1880  * For middle relay circuits, this means we received a cell from the
1881  * origin.
1882  */
1883 void
1885 {
1887  /* First, update any timestamps */
1888  on_circ->padding_info[i]->last_cell_time_sec = approx_time();
1890 
1892  CIRCPAD_EVENT_NONPADDING_RECV);
1893  } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
1894 }
1895 
1896 /**
1897  * A padding cell has been sent from this endpoint. React
1898  * according to any padding state machines on the circuit.
1899  *
1900  * For origin circuits, this means we sent a cell into the network.
1901  * For middle relay circuits, this means we sent a cell towards the
1902  * origin.
1903  */
1904 void
1906 {
1908  /* Check to see if we've run out of tokens for this state already,
1909  * and if not, check for other state transitions */
1910  if (check_machine_token_supply(on_circ->padding_info[i])
1911  == CIRCPAD_STATE_UNCHANGED) {
1912  /* If removing a token did not cause a transition, check if
1913  * non-padding sent event should */
1914 
1915  on_circ->padding_info[i]->last_cell_time_sec = approx_time();
1917  CIRCPAD_EVENT_PADDING_SENT);
1918  }
1919  } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
1920 }
1921 
1922 /**
1923  * A padding cell has been received by this endpoint. React
1924  * according to any padding state machines on the circuit.
1925  *
1926  * For origin circuits, this means we read a cell from the network.
1927  * For middle relay circuits, this means we received a cell from the
1928  * origin.
1929  */
1930 void
1932 {
1933  /* identical to padding sent */
1935  on_circ->padding_info[i]->last_cell_time_sec = approx_time();
1937  CIRCPAD_EVENT_PADDING_RECV);
1938  } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
1939 }
1940 
1941 /**
1942  * An "infinite" delay has ben chosen from one of our histograms.
1943  *
1944  * "Infinite" delays mean don't send padding -- but they can also
1945  * mean transition to another state depending on the state machine
1946  * definitions. Check the rules and react accordingly.
1947  *
1948  * Return 1 if we decide to transition, 0 otherwise.
1949  */
1952 {
1953  return circpad_machine_spec_transition(mi, CIRCPAD_EVENT_INFINITY);
1954 }
1955 
1956 /**
1957  * All of the bins of our current state's histogram's are empty.
1958  *
1959  * Check to see if this means transition to another state, and if
1960  * not, refill the tokens.
1961  *
1962  * Return 1 if we decide to transition, 0 otherwise.
1963  */
1966 {
1967  if (circpad_machine_spec_transition(mi, CIRCPAD_EVENT_BINS_EMPTY)
1968  == CIRCPAD_STATE_CHANGED) {
1969  return CIRCPAD_STATE_CHANGED;
1970  } else {
1971  /* If we dont transition, then we refill the tokens */
1973  return CIRCPAD_STATE_UNCHANGED;
1974  }
1975 }
1976 
1977 /**
1978  * This state has used up its cell count. Emit the event and
1979  * see if we transition.
1980  *
1981  * Return 1 if we decide to transition, 0 otherwise.
1982  */
1985 {
1986  return circpad_machine_spec_transition(mi, CIRCPAD_EVENT_LENGTH_COUNT);
1987 }
1988 
1989 /**
1990  * Returns true if the circuit matches the conditions.
1991  */
1992 static inline bool
1994  const circpad_machine_spec_t *machine)
1995 {
1996  /* If padding is disabled, no machines should match/apply. This has
1997  * the effect of shutting down all machines, and not adding any more. */
1998  if (circpad_padding_disabled || !get_options()->CircuitPadding)
1999  return 0;
2000 
2001  /* If the consensus or our torrc has selected reduced connection padding,
2002  * then only allow this machine if it is flagged as acceptable under
2003  * reduced padding conditions */
2004  if (circpad_padding_reduced || get_options()->ReducedCircuitPadding) {
2005  if (!machine->conditions.reduced_padding_ok)
2006  return 0;
2007  }
2008 
2009  if (!(circpad_circ_purpose_to_mask(TO_CIRCUIT(circ)->purpose)
2010  & machine->conditions.purpose_mask))
2011  return 0;
2012 
2013  if (machine->conditions.requires_vanguards) {
2014  const or_options_t *options = get_options();
2015 
2016  /* Pinned middles are effectively vanguards */
2017  if (!(options->HSLayer2Nodes || options->HSLayer3Nodes))
2018  return 0;
2019  }
2020 
2021  /* We check for any bits set in the circuit state mask so that machines
2022  * can say any of the following through their state bitmask:
2023  * "I want to apply to circuits with either streams or no streams"; OR
2024  * "I only want to apply to circuits with streams"; OR
2025  * "I only want to apply to circuits without streams". */
2026  if (!(circpad_circuit_state(circ) & machine->conditions.state_mask))
2027  return 0;
2028 
2029  if (circuit_get_cpath_opened_len(circ) < machine->conditions.min_hops)
2030  return 0;
2031 
2032  return 1;
2033 }
2034 
2035 /**
2036  * Returns a minimized representation of the circuit state.
2037  *
2038  * The padding code only cares if the circuit is building,
2039  * opened, used for streams, and/or still has relay early cells.
2040  * This returns a bitmask of all state properities that apply to
2041  * this circuit.
2042  */
2043 static inline
2046 {
2047  circpad_circuit_state_t retmask = 0;
2048 
2049  if (circ->p_streams)
2050  retmask |= CIRCPAD_CIRC_STREAMS;
2051  else
2052  retmask |= CIRCPAD_CIRC_NO_STREAMS;
2053 
2054  /* We use has_opened to prevent cannibialized circs from flapping. */
2055  if (circ->has_opened)
2056  retmask |= CIRCPAD_CIRC_OPENED;
2057  else
2058  retmask |= CIRCPAD_CIRC_BUILDING;
2059 
2060  if (circ->remaining_relay_early_cells > 0)
2061  retmask |= CIRCPAD_CIRC_HAS_RELAY_EARLY;
2062  else
2063  retmask |= CIRCPAD_CIRC_HAS_NO_RELAY_EARLY;
2064 
2065  return retmask;
2066 }
2067 
2068 /**
2069  * Convert a normal circuit purpose into a bitmask that we can
2070  * use for determining matching circuits.
2071  */
2073 circpad_circ_purpose_to_mask(uint8_t circ_purpose)
2074 {
2075  /* Treat OR circ purposes as ignored. They should not be passed here*/
2076  if (BUG(circ_purpose <= CIRCUIT_PURPOSE_OR_MAX_)) {
2077  return 0;
2078  }
2079 
2080  /* Treat new client circuit purposes as "OMG ITS EVERYTHING".
2081  * This also should not happen */
2082  if (BUG(circ_purpose - CIRCUIT_PURPOSE_OR_MAX_ - 1 > 32)) {
2083  return CIRCPAD_PURPOSE_ALL;
2084  }
2085 
2086  /* Convert the purpose to a bit position */
2087  return 1 << (circ_purpose - CIRCUIT_PURPOSE_OR_MAX_ - 1);
2088 }
2089 
2090 /**
2091  * Shut down any machines whose conditions no longer match
2092  * the current circuit.
2093  */
2094 static void
2096 {
2097  circuit_t *circ = TO_CIRCUIT(on_circ);
2098 
2100  if (!circpad_machine_conditions_met(on_circ,
2101  circ->padding_machine[i])) {
2102  // Clear machineinfo (frees timers)
2104  // Send padding negotiate stop
2105  circpad_negotiate_padding(on_circ,
2106  circ->padding_machine[i]->machine_num,
2107  circ->padding_machine[i]->target_hopnum,
2108  CIRCPAD_COMMAND_STOP);
2109  }
2110  } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
2111 }
2112 
2113 /**
2114  * Negotiate new machines that would apply to this circuit, given the machines
2115  * inside <b>machines_sl</b>.
2116  *
2117  * This function checks to see if we have any free machine indexes,
2118  * and for each free machine index, it initializes the most recently
2119  * added origin-side padding machine that matches the target machine
2120  * index and circuit conditions, and negotiates it with the appropriate
2121  * middle relay.
2122  */
2123 STATIC void
2125  smartlist_t *machines_sl)
2126 {
2127  circuit_t *circ = TO_CIRCUIT(on_circ);
2128 
2129 #ifdef TOR_UNIT_TESTS
2130  /* Tests don't have to init our padding machines */
2131  if (!machines_sl)
2132  return;
2133 #endif
2134 
2135  /* If padding negotiation failed before, do not try again */
2136  if (on_circ->padding_negotiation_failed)
2137  return;
2138 
2140  /* If there is a padding machine info, this index is occupied.
2141  * No need to check conditions for this index. */
2142  if (circ->padding_info[i])
2143  continue;
2144 
2145  /* We have a free machine index. Check the origin padding
2146  * machines in reverse order, so that more recently added
2147  * machines take priority over older ones. */
2148  SMARTLIST_FOREACH_REVERSE_BEGIN(machines_sl,
2150  machine) {
2151  /* Machine definitions have a specific target machine index.
2152  * This is so event ordering is deterministic with respect
2153  * to which machine gets events first when there are two
2154  * machines installed on a circuit. Make sure we only
2155  * add this machine if its target machine index is free. */
2156  if (machine->machine_index == i &&
2157  circpad_machine_conditions_met(on_circ, machine)) {
2158 
2159  // We can only replace this machine if the target hopnum
2160  // is the same, otherwise we'll get invalid data
2161  if (circ->padding_machine[i]) {
2162  if (circ->padding_machine[i]->target_hopnum !=
2163  machine->target_hopnum)
2164  continue;
2165  /* Replace it. (Don't free - is global). */
2166  circ->padding_machine[i] = NULL;
2167  }
2168 
2169  /* Set up the machine immediately so that the slot is occupied.
2170  * We will tear it down on error return, or if there is an error
2171  * response from the relay. */
2172  circpad_setup_machine_on_circ(circ, machine);
2173  if (circpad_negotiate_padding(on_circ, machine->machine_num,
2174  machine->target_hopnum,
2175  CIRCPAD_COMMAND_START) < 0) {
2176  log_info(LD_CIRC,
2177  "Padding not negotiated. Cleaning machine from circuit %u",
2178  CIRCUIT_IS_ORIGIN(circ) ?
2179  TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0);
2181  circ->padding_machine[i] = NULL;
2182  on_circ->padding_negotiation_failed = 1;
2183  } else {
2184  /* Success. Don't try any more machines on this index */
2185  break;
2186  }
2187  }
2188  } SMARTLIST_FOREACH_END(machine);
2189  } FOR_EACH_CIRCUIT_MACHINE_END;
2190 }
2191 
2192 /**
2193  * Event that tells us we added a hop to an origin circuit.
2194  *
2195  * This event is used to decide if we should create a padding machine
2196  * on a circuit.
2197  */
2198 void
2200 {
2201  /* Since our padding conditions do not specify a max_hops,
2202  * all we can do is add machines here */
2204 }
2205 
2206 /**
2207  * Event that tells us that an origin circuit is now built.
2208  *
2209  * Shut down any machines that only applied to un-built circuits.
2210  * Activate any new ones.
2211  */
2212 void
2214 {
2217 }
2218 
2219 /**
2220  * Circpad purpose changed event.
2221  *
2222  * Shut down any machines that don't apply to our circ purpose.
2223  * Activate any new ones that do.
2224  */
2225 void
2227 {
2230 }
2231 
2232 /**
2233  * Event that tells us that an origin circuit is out of RELAY_EARLY
2234  * cells.
2235  *
2236  * Shut down any machines that only applied to RELAY_EARLY circuits.
2237  * Activate any new ones.
2238  */
2239 void
2241 {
2244 }
2245 
2246 /**
2247  * Streams attached event.
2248  *
2249  * Called from link_apconn_to_circ() and handle_hs_exit_conn()
2250  *
2251  * Shut down any machines that only applied to machines without
2252  * streams. Activate any new ones.
2253  */
2254 void
2256 {
2259 }
2260 
2261 /**
2262  * Streams detached event.
2263  *
2264  * Called from circuit_detach_stream()
2265  *
2266  * Shut down any machines that only applied to machines without
2267  * streams. Activate any new ones.
2268  */
2269 void
2271 {
2274 }
2275 
2276 /**
2277  * Verify that padding is coming from the expected hop.
2278  *
2279  * Returns true if from_hop matches the target hop from
2280  * one of our padding machines.
2281  *
2282  * Returns false if we're not an origin circuit, or if from_hop
2283  * does not match one of the padding machines.
2284  */
2285 bool
2287  crypt_path_t *from_hop)
2288 {
2289  crypt_path_t *target_hop = NULL;
2290  if (!CIRCUIT_IS_ORIGIN(circ))
2291  return 0;
2292 
2294  /* We have to check padding_machine and not padding_info/active
2295  * machines here because padding may arrive after we shut down a
2296  * machine. The info is gone, but the padding_machine waits
2297  * for the padding_negotiated response to come back. */
2298  if (!circ->padding_machine[i])
2299  continue;
2300 
2301  target_hop = circuit_get_cpath_hop(TO_ORIGIN_CIRCUIT(circ),
2302  circ->padding_machine[i]->target_hopnum);
2303 
2304  if (target_hop == from_hop)
2305  return 1;
2306  } FOR_EACH_CIRCUIT_MACHINE_END;
2307 
2308  return 0;
2309 }
2310 
2311 /**
2312  * Deliver circpad events for an "unrecognized cell".
2313  *
2314  * Unrecognized cells are sent to relays and are forwarded
2315  * onto the next hop of their circuits. Unrecognized cells
2316  * are by definition not padding. We need to tell relay-side
2317  * state machines that a non-padding cell was sent or received,
2318  * depending on the direction, so they can update their histograms
2319  * and decide to pad or not.
2320  */
2321 void
2323  cell_direction_t dir)
2324 {
2325  // We should never see unrecognized cells at origin.
2326  // Our caller emits a warn when this happens.
2327  if (CIRCUIT_IS_ORIGIN(circ)) {
2328  return;
2329  }
2330 
2331  if (dir == CELL_DIRECTION_OUT) {
2332  /* When direction is out (away from origin), then we received non-padding
2333  cell coming from the origin to us. */
2335  } else if (dir == CELL_DIRECTION_IN) {
2336  /* It's in and not origin, so the cell is going away from us.
2337  * So we are relaying a non-padding cell towards the origin. */
2339  }
2340 }
2341 
2342 /**
2343  * Deliver circpad events for "recognized" relay cells.
2344  *
2345  * Recognized cells are destined for this hop, either client or middle.
2346  * Check if this is a padding cell or not, and send the appropiate
2347  * received event.
2348  */
2349 void
2351  uint8_t relay_command,
2352  crypt_path_t *layer_hint)
2353 {
2354  if (relay_command == RELAY_COMMAND_DROP) {
2356 
2357  if (CIRCUIT_IS_ORIGIN(circ)) {
2358  if (circpad_padding_is_from_expected_hop(circ, layer_hint)) {
2360  } else {
2361  /* This is unexpected padding. Ignore it for now. */
2362  return;
2363  }
2364  }
2365 
2366  /* The cell should be recognized by now, which means that we are on the
2367  destination, which means that we received a padding cell. We might be
2368  the client or the Middle node, still, because leaky-pipe. */
2370  log_fn(LOG_INFO, LD_CIRC, "Got padding cell on %s circuit %u.",
2371  CIRCUIT_IS_ORIGIN(circ) ? "origin" : "non-origin",
2372  CIRCUIT_IS_ORIGIN(circ) ?
2373  TO_ORIGIN_CIRCUIT(circ)->global_identifier : 0);
2374  } else {
2375  /* We received a non-padding cell on the edge */
2377  }
2378 }
2379 
2380 /**
2381  * Deliver circpad events for relay cells sent from us.
2382  *
2383  * If this is a padding cell, update our padding stats
2384  * and deliver the event. Otherwise just deliver the event.
2385  */
2386 void
2388  uint8_t relay_command)
2389 {
2390  /* RELAY_COMMAND_DROP is the multi-hop (aka circuit-level) padding cell in
2391  * tor. (CELL_PADDING is a channel-level padding cell, which is not relayed
2392  * or processed here).
2393  *
2394  * We do generate events for PADDING_NEGOTIATE and PADDING_NEGOTIATED cells.
2395  */
2396  if (relay_command == RELAY_COMMAND_DROP) {
2397  /* Optimization: The event for RELAY_COMMAND_DROP is sent directly
2398  * from circpad_send_padding_cell_for_callback(). This is to avoid
2399  * putting a cell_t and a relay_header_t on the stack repeatedly
2400  * if we decide to send a long train of padding cells back-to-back
2401  * with 0 delay. So we do nothing here. */
2402  return;
2403  } else {
2404  /* This is a non-padding cell sent from the client or from
2405  * this node. */
2407  }
2408 }
2409 
2410 /**
2411  * Initialize the states array for a circpad machine.
2412  */
2413 void
2415  circpad_statenum_t num_states)
2416 {
2417  if (BUG(num_states > CIRCPAD_MAX_MACHINE_STATES)) {
2418  num_states = CIRCPAD_MAX_MACHINE_STATES;
2419  }
2420 
2421  machine->num_states = num_states;
2422  machine->states = tor_malloc_zero(sizeof(circpad_state_t)*num_states);
2423 
2424  /* Initialize the default next state for all events to
2425  * "ignore" -- if events aren't specified, they are ignored. */
2426  for (circpad_statenum_t s = 0; s < num_states; s++) {
2427  for (int e = 0; e < CIRCPAD_NUM_EVENTS; e++) {
2428  machine->states[s].next_state[e] = CIRCPAD_STATE_IGNORE;
2429  }
2430  }
2431 }
2432 
2433 static void
2434 circpad_setup_machine_on_circ(circuit_t *on_circ,
2435  const circpad_machine_spec_t *machine)
2436 {
2437  if (CIRCUIT_IS_ORIGIN(on_circ) && !machine->is_origin_side) {
2439  "Can't set up non-origin machine on origin circuit!");
2440  return;
2441  }
2442 
2443  if (!CIRCUIT_IS_ORIGIN(on_circ) && machine->is_origin_side) {
2445  "Can't set up origin machine on non-origin circuit!");
2446  return;
2447  }
2448 
2449  IF_BUG_ONCE(on_circ->padding_machine[machine->machine_index] != NULL) {
2450  return;
2451  }
2452  IF_BUG_ONCE(on_circ->padding_info[machine->machine_index] != NULL) {
2453  return;
2454  }
2455 
2456  /* Log message */
2457  if (CIRCUIT_IS_ORIGIN(on_circ)) {
2458  log_info(LD_CIRC, "Registering machine %s to origin circ %u (%d)",
2459  machine->name,
2460  TO_ORIGIN_CIRCUIT(on_circ)->global_identifier, on_circ->purpose);
2461  } else {
2462  log_info(LD_CIRC, "Registering machine %s to non-origin circ (%d)",
2463  machine->name, on_circ->purpose);
2464  }
2465 
2466  on_circ->padding_info[machine->machine_index] =
2468  on_circ->padding_machine[machine->machine_index] = machine;
2469 }
2470 
2471 /** Validate a single state of a padding machine */
2472 static bool
2474 {
2475  int b;
2476  uint32_t tokens_count = 0;
2477  circpad_delay_t prev_bin_edge = 0;
2478 
2479  /* We only validate histograms */
2480  if (!state->histogram_len) {
2481  return true;
2482  }
2483 
2484  /* We need at least two bins in a histogram */
2485  if (state->histogram_len < 2) {
2486  log_warn(LD_CIRC, "You can't have a histogram with less than 2 bins");
2487  return false;
2488  }
2489 
2490  /* For each machine state, if it's a histogram, make sure all the
2491  * histogram edges are well defined (i.e. are strictly monotonic). */
2492  for (b = 0 ; b < state->histogram_len ; b++) {
2493  /* Check that histogram edges are strictly increasing. Ignore the first
2494  * edge since it can be zero. */
2495  if (prev_bin_edge >= state->histogram_edges[b] && b > 0) {
2496  log_warn(LD_CIRC, "Histogram edges are not increasing [%u/%u]",
2497  prev_bin_edge, state->histogram_edges[b]);
2498  return false;
2499  }
2500 
2501  prev_bin_edge = state->histogram_edges[b];
2502 
2503  /* Also count the number of tokens as we go through the histogram states */
2504  tokens_count += state->histogram[b];
2505  }
2506  /* Verify that the total number of tokens is correct */
2507  if (tokens_count != state->histogram_total_tokens) {
2508  log_warn(LD_CIRC, "Histogram token count is wrong [%u/%u]",
2509  tokens_count, state->histogram_total_tokens);
2510  return false;
2511  }
2512 
2513  return true;
2514 }
2515 
2516 /** Basic validation of padding machine */
2517 static bool
2519 {
2520  int i;
2521 
2522  /* Validate the histograms of the padding machine */
2523  for (i = 0 ; i < machine->num_states ; i++) {
2524  if (!padding_machine_state_is_valid(&machine->states[i])) {
2525  return false;
2526  }
2527  }
2528 
2529  return true;
2530 }
2531 
2532 /* Validate and register <b>machine</b> into <b>machine_list</b>. If
2533  * <b>machine_list</b> is NULL, then just validate. */
2534 void
2535 circpad_register_padding_machine(circpad_machine_spec_t *machine,
2536  smartlist_t *machine_list)
2537 {
2538  if (!padding_machine_is_valid(machine)) {
2539  log_warn(LD_CIRC, "Machine #%u is invalid. Ignoring.",
2540  machine->machine_num);
2541  return;
2542  }
2543 
2544  if (machine_list) {
2545  smartlist_add(machine_list, machine);
2546  }
2547 }
2548 
2549 #ifdef TOR_UNIT_TESTS
2550 /* These padding machines are only used for tests pending #28634. */
2551 static void
2552 circpad_circ_client_machine_init(void)
2553 {
2554  circpad_machine_spec_t *circ_client_machine
2555  = tor_malloc_zero(sizeof(circpad_machine_spec_t));
2556 
2557  circ_client_machine->conditions.min_hops = 2;
2558  circ_client_machine->conditions.state_mask =
2559  CIRCPAD_CIRC_BUILDING|CIRCPAD_CIRC_OPENED|CIRCPAD_CIRC_HAS_RELAY_EARLY;
2560  circ_client_machine->conditions.purpose_mask = CIRCPAD_PURPOSE_ALL;
2561  circ_client_machine->conditions.reduced_padding_ok = 1;
2562 
2563  circ_client_machine->target_hopnum = 2;
2564  circ_client_machine->is_origin_side = 1;
2565 
2566  /* Start, gap, burst */
2567  circpad_machine_states_init(circ_client_machine, 3);
2568 
2569  circ_client_machine->states[CIRCPAD_STATE_START].
2570  next_state[CIRCPAD_EVENT_NONPADDING_RECV] = CIRCPAD_STATE_BURST;
2571 
2572  circ_client_machine->states[CIRCPAD_STATE_BURST].
2573  next_state[CIRCPAD_EVENT_NONPADDING_RECV] = CIRCPAD_STATE_BURST;
2574  circ_client_machine->states[CIRCPAD_STATE_BURST].
2575  next_state[CIRCPAD_EVENT_PADDING_RECV] = CIRCPAD_STATE_BURST;
2576 
2577  /* If we are in burst state, and we send a non-padding cell, then we cancel
2578  the timer for the next padding cell:
2579  We dont want to send fake extends when actual extends are going on */
2580  circ_client_machine->states[CIRCPAD_STATE_BURST].
2581  next_state[CIRCPAD_EVENT_NONPADDING_SENT] = CIRCPAD_STATE_CANCEL;
2582 
2583  circ_client_machine->states[CIRCPAD_STATE_BURST].
2584  next_state[CIRCPAD_EVENT_BINS_EMPTY] = CIRCPAD_STATE_END;
2585 
2586  circ_client_machine->states[CIRCPAD_STATE_BURST].token_removal =
2588 
2589  circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_len = 2;
2590  circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_edges[0]= 500;
2591  circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_edges[1]= 1000000;
2592 
2593  /* We have 5 tokens in the histogram, which means that all circuits will look
2594  * like they have 7 hops (since we start this machine after the second hop,
2595  * and tokens are decremented for any valid hops, and fake extends are
2596  * used after that -- 2+5==7). */
2597  circ_client_machine->states[CIRCPAD_STATE_BURST].histogram[0] = 5;
2598 
2599  circ_client_machine->states[CIRCPAD_STATE_BURST].histogram_total_tokens = 5;
2600 
2601  circ_client_machine->machine_num = smartlist_len(origin_padding_machines);
2602  circpad_register_padding_machine(circ_client_machine,
2604 }
2605 
2606 static void
2607 circpad_circ_responder_machine_init(void)
2608 {
2609  circpad_machine_spec_t *circ_responder_machine
2610  = tor_malloc_zero(sizeof(circpad_machine_spec_t));
2611 
2612  /* Shut down the machine after we've sent enough packets */
2613  circ_responder_machine->should_negotiate_end = 1;
2614 
2615  /* The relay-side doesn't care what hopnum it is, but for consistency,
2616  * let's match the client */
2617  circ_responder_machine->target_hopnum = 2;
2618  circ_responder_machine->is_origin_side = 0;
2619 
2620  /* Start, gap, burst */
2621  circpad_machine_states_init(circ_responder_machine, 3);
2622 
2623  /* This is the settings of the state machine. In the future we are gonna
2624  serialize this into the consensus or the torrc */
2625 
2626  /* We transition to the burst state on padding receive and on non-padding
2627  * recieve */
2628  circ_responder_machine->states[CIRCPAD_STATE_START].
2629  next_state[CIRCPAD_EVENT_PADDING_RECV] = CIRCPAD_STATE_BURST;
2630  circ_responder_machine->states[CIRCPAD_STATE_START].
2631  next_state[CIRCPAD_EVENT_NONPADDING_RECV] = CIRCPAD_STATE_BURST;
2632 
2633  /* Inside the burst state we _stay_ in the burst state when a non-padding
2634  * is sent */
2635  circ_responder_machine->states[CIRCPAD_STATE_BURST].
2636  next_state[CIRCPAD_EVENT_NONPADDING_SENT] = CIRCPAD_STATE_BURST;
2637 
2638  /* Inside the burst state we transition to the gap state when we receive a
2639  * padding cell */
2640  circ_responder_machine->states[CIRCPAD_STATE_BURST].
2641  next_state[CIRCPAD_EVENT_PADDING_RECV] = CIRCPAD_STATE_GAP;
2642 
2643  /* These describe the padding charasteristics when in burst state */
2644 
2645  /* use_rtt_estimate tries to estimate how long padding cells take to go from
2646  C->M, and uses that as what as the base of the histogram */
2647  circ_responder_machine->states[CIRCPAD_STATE_BURST].use_rtt_estimate = 1;
2648  /* The histogram is 2 bins: an empty one, and infinity */
2649  circ_responder_machine->states[CIRCPAD_STATE_BURST].histogram_len = 2;
2650  circ_responder_machine->states[CIRCPAD_STATE_BURST].histogram_edges[0]= 500;
2651  circ_responder_machine->states[CIRCPAD_STATE_BURST].histogram_edges[1] =
2652  1000000;
2653  /* During burst state we wait forever for padding to arrive.
2654 
2655  We are waiting for a padding cell from the client to come in, so that we
2656  respond, and we immitate how extend looks like */
2657  circ_responder_machine->states[CIRCPAD_STATE_BURST].histogram[0] = 0;
2658  // Only infinity bin:
2659  circ_responder_machine->states[CIRCPAD_STATE_BURST].histogram[1] = 1;
2660  circ_responder_machine->states[CIRCPAD_STATE_BURST].
2661  histogram_total_tokens = 1;
2662 
2663  /* From the gap state, we _stay_ in the gap state, when we receive padding
2664  * or non padding */
2665  circ_responder_machine->states[CIRCPAD_STATE_GAP].
2666  next_state[CIRCPAD_EVENT_PADDING_RECV] = CIRCPAD_STATE_GAP;
2667  circ_responder_machine->states[CIRCPAD_STATE_GAP].
2668  next_state[CIRCPAD_EVENT_NONPADDING_RECV] = CIRCPAD_STATE_GAP;
2669 
2670  /* And from the gap state, we go to the end, when the bins are empty or a
2671  * non-padding cell is sent */
2672  circ_responder_machine->states[CIRCPAD_STATE_GAP].
2673  next_state[CIRCPAD_EVENT_BINS_EMPTY] = CIRCPAD_STATE_END;
2674  circ_responder_machine->states[CIRCPAD_STATE_GAP].
2675  next_state[CIRCPAD_EVENT_NONPADDING_SENT] = CIRCPAD_STATE_END;
2676 
2677  // FIXME: Tune this histogram
2678 
2679  /* The gap state is the delay you wait after you receive a padding cell
2680  before you send a padding response */
2681  circ_responder_machine->states[CIRCPAD_STATE_GAP].use_rtt_estimate = 1;
2682  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_len = 6;
2683  /* Specify histogram bins */
2684  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_edges[0]= 500;
2685  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_edges[1]= 1000;
2686  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_edges[2]= 2000;
2687  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_edges[3]= 4000;
2688  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_edges[4]= 8000;
2689  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_edges[5]= 16000;
2690  /* Specify histogram tokens */
2691  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram[0] = 0;
2692  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram[1] = 1;
2693  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram[2] = 2;
2694  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram[3] = 2;
2695  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram[4] = 1;
2696  /* Total number of tokens */
2697  circ_responder_machine->states[CIRCPAD_STATE_GAP].histogram_total_tokens = 6;
2698 
2699  circ_responder_machine->states[CIRCPAD_STATE_GAP].token_removal =
2701 
2702  circ_responder_machine->machine_num = smartlist_len(relay_padding_machines);
2703  circpad_register_padding_machine(circ_responder_machine,
2705 }
2706 #endif /* defined(TOR_UNIT_TESTS) */
2707 
2708 /**
2709  * Initialize all of our padding machines.
2710  *
2711  * This is called at startup. It sets up some global machines, and then
2712  * loads some from torrc, and from the tor consensus.
2713  */
2714 void
2716 {
2717  tor_assert_nonfatal(origin_padding_machines == NULL);
2718  tor_assert_nonfatal(relay_padding_machines == NULL);
2719 
2722 
2723  /* Register machines for hiding client-side intro circuits */
2726 
2727  /* Register machines for hiding client-side rendezvous circuits */
2730 
2731  // TODO: Parse machines from consensus and torrc
2732 #ifdef TOR_UNIT_TESTS
2733  circpad_circ_client_machine_init();
2734  circpad_circ_responder_machine_init();
2735 #endif
2736 }
2737 
2738 /**
2739  * Free our padding machines
2740  */
2741 void
2743 {
2747  m, tor_free(m->states); tor_free(m));
2748  smartlist_free(origin_padding_machines);
2749  }
2750 
2751  if (relay_padding_machines) {
2754  m, tor_free(m->states); tor_free(m));
2755  smartlist_free(relay_padding_machines);
2756  }
2757 }
2758 
2759 /**
2760  * Check the Protover info to see if a node supports padding.
2761  */
2762 static bool
2764 {
2765  if (node->rs) {
2766  log_fn(LOG_INFO, LD_CIRC, "Checking padding: %s",
2767  node->rs->pv.supports_hs_setup_padding ?
2768  "supported" : "unsupported");
2769  return node->rs->pv.supports_hs_setup_padding;
2770  }
2771 
2772  log_fn(LOG_INFO, LD_CIRC, "Empty routerstatus in padding check");
2773  return 0;
2774 }
2775 
2776 /**
2777  * Get a node_t for the nth hop in our circuit, starting from 1.
2778  *
2779  * Returns node_t from the consensus for that hop, if it is opened.
2780  * Otherwise returns NULL.
2781  */
2782 MOCK_IMPL(STATIC const node_t *,
2784 {
2785  crypt_path_t *iter = circuit_get_cpath_hop(circ, hop);
2786 
2787  if (!iter || iter->state != CPATH_STATE_OPEN)
2788  return NULL;
2789 
2791 }
2792 
2793 /**
2794  * Return true if a particular circuit supports padding
2795  * at the desired hop.
2796  */
2797 static bool
2799  int target_hopnum)
2800 {
2801  const node_t *hop;
2802 
2803  if (!(hop = circuit_get_nth_node(circ, target_hopnum))) {
2804  return 0;
2805  }
2806 
2807  return circpad_node_supports_padding(hop);
2808 }
2809 
2810 /**
2811  * Try to negotiate padding.
2812  *
2813  * Returns -1 on error, 0 on success.
2814  */
2817  circpad_machine_num_t machine,
2818  uint8_t target_hopnum,
2819  uint8_t command)
2820 {
2821  circpad_negotiate_t type;
2822  cell_t cell;
2823  ssize_t len;
2824 
2825  /* Check that the target hop lists support for padding in
2826  * its ProtoVer fields */
2827  if (!circpad_circuit_supports_padding(circ, target_hopnum)) {
2828  return -1;
2829  }
2830 
2831  memset(&cell, 0, sizeof(cell_t));
2832  memset(&type, 0, sizeof(circpad_negotiate_t));
2833  // This gets reset to RELAY_EARLY appropriately by
2834  // relay_send_command_from_edge_. At least, it looks that way.
2835  // QQQ-MP-AP: Verify that.
2836  cell.command = CELL_RELAY;
2837 
2838  circpad_negotiate_set_command(&type, command);
2839  circpad_negotiate_set_version(&type, 0);
2840  circpad_negotiate_set_machine_type(&type, machine);
2841 
2842  if ((len = circpad_negotiate_encode(cell.payload, CELL_PAYLOAD_SIZE,
2843  &type)) < 0)
2844  return -1;
2845 
2847  "Negotiating padding on circuit %u (%d), command %d",
2848  circ->global_identifier, TO_CIRCUIT(circ)->purpose, command);
2849 
2850  return circpad_send_command_to_hop(circ, target_hopnum,
2851  RELAY_COMMAND_PADDING_NEGOTIATE,
2852  cell.payload, len);
2853 }
2854 
2855 /**
2856  * Try to negotiate padding.
2857  *
2858  * Returns 1 if successful (or already set up), 0 otherwise.
2859  */
2860 bool
2862  circpad_machine_num_t machine,
2863  uint8_t command,
2864  uint8_t response)
2865 {
2866  circpad_negotiated_t type;
2867  cell_t cell;
2868  ssize_t len;
2869 
2870  memset(&cell, 0, sizeof(cell_t));
2871  memset(&type, 0, sizeof(circpad_negotiated_t));
2872  // This gets reset to RELAY_EARLY appropriately by
2873  // relay_send_command_from_edge_. At least, it looks that way.
2874  // QQQ-MP-AP: Verify that.
2875  cell.command = CELL_RELAY;
2876 
2877  circpad_negotiated_set_command(&type, command);
2878  circpad_negotiated_set_response(&type, response);
2879  circpad_negotiated_set_version(&type, 0);
2880  circpad_negotiated_set_machine_type(&type, machine);
2881 
2882  if ((len = circpad_negotiated_encode(cell.payload, CELL_PAYLOAD_SIZE,
2883  &type)) < 0)
2884  return 0;
2885 
2886  /* Use relay_send because we're from the middle to the origin. We don't
2887  * need to specify a target hop or layer_hint. */
2888  return relay_send_command_from_edge(0, circ,
2889  RELAY_COMMAND_PADDING_NEGOTIATED,
2890  (void*)cell.payload,
2891  (size_t)len, NULL) == 0;
2892 }
2893 
2894 /**
2895  * Parse and react to a padding_negotiate cell.
2896  *
2897  * This is called at the middle node upon receipt of the client's choice of
2898  * state machine, so that it can use the requested state machine index, if
2899  * it is available.
2900  *
2901  * Returns -1 on error, 0 on success.
2902  */
2905 {
2906  int retval = 0;
2907  circpad_negotiate_t *negotiate;
2908 
2909  if (CIRCUIT_IS_ORIGIN(circ)) {
2910  log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
2911  "Padding negotiate cell unsupported at origin (circuit %u)",
2912  TO_ORIGIN_CIRCUIT(circ)->global_identifier);
2913  return -1;
2914  }
2915 
2916  if (circpad_negotiate_parse(&negotiate, cell->payload+RELAY_HEADER_SIZE,
2918  log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
2919  "Received malformed PADDING_NEGOTIATE cell; dropping.");
2920  return -1;
2921  }
2922 
2923  if (negotiate->command == CIRCPAD_COMMAND_STOP) {
2924  /* Free the machine corresponding to this machine type */
2926  negotiate->machine_type)) {
2927  log_info(LD_CIRC, "Received STOP command for machine %u",
2928  negotiate->machine_type);
2929  goto done;
2930  }
2931  log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
2932  "Received circuit padding stop command for unknown machine.");
2933  goto err;
2934  } else if (negotiate->command == CIRCPAD_COMMAND_START) {
2936  const circpad_machine_spec_t *, m) {
2937  if (m->machine_num == negotiate->machine_type) {
2938  circpad_setup_machine_on_circ(circ, m);
2940  goto done;
2941  }
2942  } SMARTLIST_FOREACH_END(m);
2943  }
2944 
2945  err:
2946  retval = -1;
2947 
2948  done:
2949  circpad_padding_negotiated(circ, negotiate->machine_type,
2950  negotiate->command,
2951  (retval == 0) ? CIRCPAD_RESPONSE_OK : CIRCPAD_RESPONSE_ERR);
2952  circpad_negotiate_free(negotiate);
2953 
2954  return retval;
2955 }
2956 
2957 /**
2958  * Parse and react to a padding_negotiated cell.
2959  *
2960  * This is called at the origin upon receipt of the middle's response
2961  * to our choice of state machine.
2962  *
2963  * Returns -1 on error, 0 on success.
2964  */
2967  crypt_path_t *layer_hint)
2968 {
2969  circpad_negotiated_t *negotiated;
2970 
2971  if (!CIRCUIT_IS_ORIGIN(circ)) {
2972  log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
2973  "Padding negotiated cell unsupported at non-origin.");
2974  return -1;
2975  }
2976 
2977  /* Verify this came from the expected hop */
2978  if (!circpad_padding_is_from_expected_hop(circ, layer_hint)) {
2979  log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
2980  "Padding negotiated cell from wrong hop on circuit %u",
2981  TO_ORIGIN_CIRCUIT(circ)->global_identifier);
2982  return -1;
2983  }
2984 
2985  if (circpad_negotiated_parse(&negotiated, cell->payload+RELAY_HEADER_SIZE,
2987  log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
2988  "Received malformed PADDING_NEGOTIATED cell on circuit %u; "
2989  "dropping.", TO_ORIGIN_CIRCUIT(circ)->global_identifier);
2990  return -1;
2991  }
2992 
2993  if (negotiated->command == CIRCPAD_COMMAND_STOP) {
2994  log_info(LD_CIRC,
2995  "Received STOP command on PADDING_NEGOTIATED for circuit %u",
2996  TO_ORIGIN_CIRCUIT(circ)->global_identifier);
2997  /* There may not be a padding_info here if we shut down the
2998  * machine in circpad_shutdown_old_machines(). Or, if
2999  * circpad_add_matching_matchines() added a new machine,
3000  * there may be a padding_machine for a different machine num
3001  * than this response. */
3002  free_circ_machineinfos_with_machine_num(circ, negotiated->machine_type);
3003  } else if (negotiated->command == CIRCPAD_COMMAND_START &&
3004  negotiated->response == CIRCPAD_RESPONSE_ERR) {
3005  // This can happen due to consensus drift.. free the machines
3006  // and be sad
3007  free_circ_machineinfos_with_machine_num(circ, negotiated->machine_type);
3008  TO_ORIGIN_CIRCUIT(circ)->padding_negotiation_failed = 1;
3009  log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
3010  "Middle node did not accept our padding request on circuit %u (%d)",
3011  TO_ORIGIN_CIRCUIT(circ)->global_identifier,
3012  circ->purpose);
3013  }
3014 
3015  circpad_negotiated_free(negotiated);
3016  return 0;
3017 }
3018 
3019 /** Free memory allocated by this machine spec. */
3020 STATIC void
3022 {
3023  if (!m) return;
3024 
3025  tor_free(m->states);
3026  tor_free(m);
3027 }
3028 
3029 /** Free all memory allocated by the circuitpadding subsystem. */
3030 void
3032 {
3035  circpad_machine_spec_t *, m) {
3036  machine_spec_free(m);
3037  } SMARTLIST_FOREACH_END(m);
3038  smartlist_free(origin_padding_machines);
3039  }
3040  if (relay_padding_machines) {
3042  circpad_machine_spec_t *, m) {
3043  machine_spec_free(m);
3044  } SMARTLIST_FOREACH_END(m);
3045  smartlist_free(relay_padding_machines);
3046  }
3047 }
3048 
3049 /* Serialization */
3050 // TODO: Should we use keyword=value here? Are there helpers for that?
3051 #if 0
3052 static void
3053 circpad_state_serialize(const circpad_state_t *state,
3054  smartlist_t *chunks)
3055 {
3056  smartlist_add_asprintf(chunks, " %u", state->histogram[0]);
3057  for (int i = 1; i < state->histogram_len; i++) {
3058  smartlist_add_asprintf(chunks, ",%u",
3059  state->histogram[i]);
3060  }
3061 
3062  smartlist_add_asprintf(chunks, " 0x%x",
3063  state->transition_cancel_events);
3064 
3065  for (int i = 0; i < CIRCPAD_NUM_STATES; i++) {
3066  smartlist_add_asprintf(chunks, ",0x%x",
3067  state->transition_events[i]);
3068  }
3069 
3070  smartlist_add_asprintf(chunks, " %u %u",
3071  state->use_rtt_estimate,
3072  state->token_removal);
3073 }
3074 
3075 char *
3077 {
3078  smartlist_t *chunks = smartlist_new();
3079  char *out;
3080  (void)machine;
3081 
3082  circpad_state_serialize(&machine->start, chunks);
3083  circpad_state_serialize(&machine->gap, chunks);
3084  circpad_state_serialize(&machine->burst, chunks);
3085 
3086  out = smartlist_join_strings(chunks, "", 0, NULL);
3087 
3088  SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
3089  smartlist_free(chunks);
3090  return out;
3091 }
3092 
3093 // XXX: Writeme
3094 const circpad_machine_spec_t *
3095 circpad_string_to_machine(const char *str)
3096 {
3097  (void)str;
3098  return NULL;
3099 }
3100 
3101 #endif /* 0 */
void timer_disable(tor_timer_t *t)
Definition: timers.c:326
uint64_t global_identifier
Definition: channel.h:197
static circpad_delay_t circpad_get_histogram_bin_midpoint(const circpad_machine_runtime_t *mi, int bin_index)
#define CIRCPAD_PURPOSE_ALL
STATIC circpad_machine_runtime_t * circpad_circuit_machineinfo_new(circuit_t *on_circ, int machine_index)
#define CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
Definition: circuitlist.h:95
char identity_digest[DIGEST_LEN]
#define CIRCPAD_STATE_END
circpad_decision_t
Base circuit structure.
channel_t * n_chan
Definition: circuit_st.h:69
#define CIRCPAD_STATE_CANCEL
int circpad_check_received_cell(cell_t *cell, circuit_t *circ, crypt_path_t *layer_hint, const relay_header_t *rh)
Common functions for using (pseudo-)random number generators.
const struct circpad_machine_spec_t * padding_machine[CIRCPAD_MAX_MACHINES]
Definition: circuit_st.h:229
unsigned int supports_hs_setup_padding
Definition: or.h:845
Definition: node_st.h:34
uint32_t circpad_delay_t
STATIC void machine_spec_free_(circpad_machine_spec_t *m)
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
int64_t tor_llround(double d)
Definition: fp.c:46
int32_t networkstatus_get_param(const networkstatus_t *ns, const char *param_name, int32_t default_val, int32_t min_val, int32_t max_val)
extend_info_t * extend_info
Definition: crypt_path_st.h:61
circpad_decision_t circpad_internal_event_state_length_up(circpad_machine_runtime_t *mi)
#define MOCK_IMPL(rv, funcname, arglist)
Definition: testsupport.h:133
crypt_path_t * circuit_get_cpath_hop(origin_circuit_t *circ, int hopnum)
Definition: circuitlist.c:2076
uint64_t circpad_time_t
void circpad_machine_event_circ_added_hop(origin_circuit_t *on_circ)
Definitions for timing-related constants.
int signed_error_t
void circpad_machine_relay_hide_rend_circuits(smartlist_t *machines_sl)
uint64_t crypto_fast_rng_get_uint64(crypto_fast_rng_t *rng, uint64_t limit)
circpad_hist_index_t chosen_bin
circpad_hist_token_t histogram[CIRCPAD_MAX_HISTOGRAM_LEN]
Definition: cell_st.h:17
#define CIRCUIT_IS_ORIGIN(c)
Definition: circuitlist.h:146
Path structures for origin circuits.
Functions and types for monotonic times.
const char * circuit_purpose_to_string(uint8_t purpose)
Definition: circuitlist.c:900
#define LOG_INFO
Definition: log.h:45
Header file for nodelist.c.
uint8_t state
Definition: circuit_st.h:110
void circpad_machine_client_hide_rend_circuits(smartlist_t *machines_sl)
uint8_t purpose
Definition: circuit_st.h:111
void smartlist_add(smartlist_t *sl, void *element)
static void circpad_machine_count_padding_sent(circpad_machine_runtime_t *mi)
Node information structure.
void assert_circuit_ok(const circuit_t *c)
Definition: circuitlist.c:2755
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)
void circpad_deliver_recognized_relay_cell_events(circuit_t *circ, uint8_t relay_command, crypt_path_t *layer_hint)
#define TO_CIRCUIT(x)
Definition: or.h:951
circpad_state_t * states
Header file for config.c.
STATIC const node_t * circuit_get_nth_node(origin_circuit_t *circ, int hop)
struct circpad_machine_runtime_t * padding_info[CIRCPAD_MAX_MACHINES]
Definition: circuit_st.h:240
const or_options_t * get_options(void)
Definition: config.c:925
#define tor_assert(expr)
Definition: util_bug.h:102
uint64_t monotime_absolute_usec(void)
Definition: compat_time.c:801
static double circpad_distribution_sample(circpad_distribution_t dist)
#define CIRCPAD_INFINITY_BIN(mi)
circpad_removal_t token_removal
#define tor_free(p)
Definition: malloc.h:52
void circpad_deliver_unrecognized_cell_events(circuit_t *circ, cell_direction_t dir)
uint16_t marked_for_close
Definition: circuit_st.h:189
#define tor_fragile_assert()
Definition: util_bug.h:246
void circpad_new_consensus_params(const networkstatus_t *ns)
bool circpad_padding_negotiated(circuit_t *circ, circpad_machine_num_t machine, uint8_t command, uint8_t response)
#define LOG_NOTICE
Definition: log.h:50
STATIC void circpad_machine_remove_token(circpad_machine_runtime_t *mi)
void circpad_machine_client_hide_intro_circuits(smartlist_t *machines_sl)
int circuit_get_cpath_len(origin_circuit_t *circ)
Definition: circuitlist.c:2040
smartlist_t * smartlist_new(void)
circpad_machine_conditions_t conditions
static uint64_t circpad_global_padding_sent
STATIC smartlist_t * relay_padding_machines
STATIC circpad_delay_t circpad_machine_sample_delay(circpad_machine_runtime_t *mi)
circpad_statenum_t next_state[CIRCPAD_NUM_EVENTS]
uint8_t payload[CELL_PAYLOAD_SIZE]
Definition: cell_st.h:21
#define STATIC
Definition: testsupport.h:32
static bool padding_machine_state_is_valid(const circpad_state_t *state)
circpad_decision_t circpad_internal_event_bins_empty(circpad_machine_runtime_t *mi)
void circpad_circuit_free_all_machineinfos(circuit_t *circ)
cell_direction_t
Definition: or.h:482
void rep_hist_padding_count_read(padding_type_t type)
Definition: rephist.c:2759
STATIC void circpad_add_matching_machines(origin_circuit_t *on_circ, smartlist_t *machines_sl)
Routerstatus (consensus entry) structure.
static bool padding_machine_is_valid(const circpad_machine_spec_t *machine)
void circpad_machines_init(void)
unsigned int remaining_relay_early_cells
#define CIRCPAD_DELAY_INFINITE
circpad_hist_index_t histogram_len
static bool circpad_node_supports_padding(const node_t *node)
STATIC bool circpad_machine_reached_padding_limit(circpad_machine_runtime_t *mi)
static void circpad_estimate_circ_rtt_on_send(circuit_t *circ, circpad_machine_runtime_t *mi)
static void circpad_estimate_circ_rtt_on_received(circuit_t *circ, circpad_machine_runtime_t *mi)
STATIC void circpad_machine_remove_lower_token(circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec)
Header file for channel.c.
signed_error_t circpad_handle_padding_negotiated(circuit_t *circ, cell_t *cell, crypt_path_t *layer_hint)
uint32_t circpad_hist_token_t
static void circpad_machine_update_state_length_for_nonpadding(circpad_machine_runtime_t *mi)
STATIC circpad_hist_index_t circpad_histogram_usec_to_bin(const circpad_machine_runtime_t *mi, circpad_delay_t usec)
void circpad_machine_event_circ_has_streams(origin_circuit_t *circ)
STATIC void circpad_machine_remove_closest_token(circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec, bool use_usec)
Header for fp.c.
#define LD_CIRC
Definition: log.h:82
STATIC void circpad_machine_remove_higher_token(circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec)
Header file for circuitpadding.c.
signed_error_t circpad_handle_padding_negotiate(circuit_t *circ, cell_t *cell)
Origin circuit structure.
uint32_t circpad_purpose_mask_t
void smartlist_add_asprintf(struct smartlist_t *sl, const char *pattern,...)
Definition: smartlist.c:36
static bool circpad_circuit_supports_padding(origin_circuit_t *circ, int target_hopnum)
Master header file for Tor-specific functionality.
circpad_decision_t circpad_machine_spec_transition(circpad_machine_runtime_t *mi, circpad_event_t event)
#define CIRCUIT_STATE_OPEN
Definition: circuitlist.h:32
#define FOR_EACH_ACTIVE_CIRCUIT_MACHINE_BEGIN(loop_var, circ)
Header file for circuitpadding_machines.c.
circpad_time_t last_received_time_usec
void circpad_machine_event_circ_has_no_streams(origin_circuit_t *circ)
protover_summary_flags_t pv
struct routerset_t * HSLayer2Nodes
#define TOR_USEC_PER_SEC
Definition: time.h:17
static bool circpad_is_padding_allowed(void)
const node_t * node_get_by_id(const char *identity_digest)
Definition: nodelist.c:223
Header file for rephist.c.
uint64_t crypto_fast_rng_uint64_range(crypto_fast_rng_t *rng, uint64_t min, uint64_t max)
void circpad_machines_free(void)
void timer_schedule(tor_timer_t *t, const struct timeval *tv)
Definition: timers.c:301
#define LOG_WARN
Definition: log.h:53
bool is_participating_on_network(void)
Definition: netstatus.c:110
Header for netstatus.c.
#define log_fn_ratelim(ratelim, severity, domain, args,...)
Definition: log.h:292
Header file for circuituse.c.
Extend-info structure.
Header for prob_distr.c.
STATIC circpad_delay_t histogram_get_bin_upper_bound(const circpad_machine_runtime_t *mi, circpad_hist_index_t bin)
#define CIRCPAD_STATE_GAP
static void circpad_send_padding_callback(tor_timer_t *timer, void *args, const struct monotime_t *time)
static circpad_circuit_state_t circpad_circuit_state(origin_circuit_t *circ)
circpad_statenum_t current_state
Header file for circuitlist.c.
#define CIRCUIT_PURPOSE_PATH_BIAS_TESTING
Definition: circuitlist.h:122
void circpad_cell_event_padding_sent(circuit_t *on_circ)
circpad_distribution_t length_dist
static bool circpad_machine_conditions_met(origin_circuit_t *circ, const circpad_machine_spec_t *machine)
Fixed-size cell structure.
#define CIRCPAD_STATE_START
#define CIRCPAD_STATE_IGNORE
uint8_t command
Definition: cell_st.h:19
static circpad_decision_t check_machine_token_supply(circpad_machine_runtime_t *mi)
int circpad_marked_circuit_for_padding(circuit_t *circ, int reason)
#define CIRCPAD_GET_MACHINE(machineinfo)
unsigned use_rtt_estimate
static void circpad_circuit_machineinfo_free_idx(circuit_t *circ, int idx)
circpad_decision_t circpad_machine_schedule_padding(circpad_machine_runtime_t *mi)
struct circuit_t * on_circ
void circpad_machine_states_init(circpad_machine_spec_t *machine, circpad_statenum_t num_states)
uint16_t circpad_statenum_t
void circpad_machine_relay_hide_intro_circuits(smartlist_t *machines_sl)
circpad_machine_num_t machine_num
circpad_distribution_t iat_dist
STATIC void circpad_machine_setup_tokens(circpad_machine_runtime_t *mi)
origin_circuit_t * TO_ORIGIN_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:165
circpad_hist_token_t * histogram
char * smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, size_t *len_out)
Definition: smartlist.c:279
void circpad_free_all(void)
#define CELL_PAYLOAD_SIZE
Definition: or.h:576
crypto_fast_rng_t * get_thread_fast_rng(void)
#define IF_BUG_ONCE(cond)
Definition: util_bug.h:239
#define CIRCPAD_DELAY_MAX_SECS
STATIC circpad_delay_t circpad_histogram_bin_to_usec(const circpad_machine_runtime_t *mi, circpad_hist_index_t bin)
tor_timer_t * timer_new(timer_cb_fn_t cb, void *arg)
Definition: timers.c:250
#define CIRCPAD_STATE_BURST
void rep_hist_padding_count_write(padding_type_t type)
Definition: rephist.c:2731
circpad_circuit_state_t
Header file for relay.c.
#define SMARTLIST_FOREACH(sl, type, var, cmd)
circpad_decision_t circpad_send_padding_cell_for_callback(circpad_machine_runtime_t *mi)
static int circpad_is_token_removal_supported(circpad_machine_runtime_t *mi)
void timer_set_cb(tor_timer_t *t, timer_cb_fn_t cb, void *arg)
Definition: timers.c:276
uint32_t histogram_total_tokens
static void circpad_machine_remove_exact(circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec)
static circpad_hist_index_t circpad_machine_first_lower_index(const circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec)
int circuit_get_cpath_opened_len(const origin_circuit_t *circ)
Definition: circuitlist.c:2056
uint16_t length
Definition: or.h:642
circpad_statenum_t num_states
#define log_fn(severity, domain, args,...)
Definition: log.h:287
void circpad_cell_event_nonpadding_received(circuit_t *on_circ)
circpad_purpose_mask_t circpad_circ_purpose_to_mask(uint8_t circ_purpose)
char * circpad_machine_spec_to_string(const circpad_machine_spec_t *machine)
or_circuit_t * TO_OR_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:153
edge_connection_t * p_streams
void circpad_machine_event_circ_built(origin_circuit_t *circ)
time_t approx_time(void)
Definition: approx_time.c:32
time_t timestamp_dirty
Definition: circuit_st.h:187
#define LOG_DEBUG
Definition: log.h:42
void circpad_cell_event_nonpadding_sent(circuit_t *on_circ)
STATIC smartlist_t * origin_padding_machines
tor_cmdline_mode_t command
Definition: config.c:2444
circid_t n_circ_id
Definition: circuit_st.h:78
circpad_time_t padding_scheduled_at_usec
void circuit_change_purpose(circuit_t *circ, uint8_t new_purpose)
Definition: circuituse.c:3095
circpad_purpose_mask_t purpose_mask
#define MAX(a, b)
Definition: cmp.h:22
static void circpad_machine_spec_transitioned_to_end(circpad_machine_runtime_t *mi)
signed_error_t circpad_negotiate_padding(origin_circuit_t *circ, circpad_machine_num_t machine, uint8_t target_hopnum, uint8_t command)
void circuit_read_valid_data(origin_circuit_t *circ, uint16_t relay_body_len)
Definition: circuituse.c:3184
bool circpad_padding_is_from_expected_hop(circuit_t *circ, crypt_path_t *from_hop)
static void circpad_shutdown_old_machines(origin_circuit_t *on_circ)
static int free_circ_machineinfos_with_machine_num(circuit_t *circ, int machine_num)
circpad_event_t
struct routerset_t * HSLayer3Nodes
uint16_t start_length
circpad_decision_t circpad_internal_event_infinity(circpad_machine_runtime_t *mi)
int8_t circpad_hist_index_t
int64_t clamp_double_to_int64(double number)
Definition: fp.c:61
uint8_t circpad_machine_num_t
static circpad_delay_t circpad_distribution_sample_iat_delay(const circpad_state_t *state, circpad_delay_t delay_shift)
unsigned length_includes_nonpadding
static void circpad_choose_state_length(circpad_machine_runtime_t *mi)
circpad_hist_index_t histogram_len
void circpad_machine_event_circ_has_no_relay_early(origin_circuit_t *circ)
#define RELAY_HEADER_SIZE
Definition: or.h:603
circpad_circuit_state_t state_mask
uint8_t command
Definition: or.h:638
STATIC const circpad_state_t * circpad_machine_current_state(const circpad_machine_runtime_t *mi)
void circpad_deliver_sent_relay_cell_events(circuit_t *circ, uint8_t relay_command)
static void circpad_machine_count_nonpadding_sent(circpad_machine_runtime_t *mi)
static circpad_hist_index_t circpad_machine_first_higher_index(const circpad_machine_runtime_t *mi, circpad_delay_t target_bin_usec)
#define FOR_EACH_CIRCUIT_MACHINE_BEGIN(loop_var)
Header file for networkstatus.c.
#define LD_BUG
Definition: log.h:86
Header for relay_crypto.c.
uint8_t state
Definition: crypt_path_st.h:68
static uint8_t circpad_padding_disabled
unsigned int has_opened
circpad_delay_t rtt_estimate_usec
#define CIRCUIT_PURPOSE_C_CIRCUIT_PADDING
Definition: circuitlist.h:97
void circpad_cell_event_padding_received(circuit_t *on_circ)
#define SMARTLIST_FOREACH_REVERSE_BEGIN(sl, type, var)
#define CIRCPAD_MAX_MACHINE_STATES
void circpad_machine_event_circ_purpose_changed(origin_circuit_t *circ)