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