49 #define CIRCUITPADDING_PRIVATE
73 #include "core/or/or_circuit_st.h"
85 static void circpad_setup_machine_on_circ(
circuit_t *on_circ,
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;
101 static uint64_t circpad_global_nonpadding_sent;
122 #define FOR_EACH_CIRCUIT_MACHINE_BEGIN(loop_var) \
124 for (int loop_var = 0; loop_var < CIRCPAD_MAX_MACHINES; loop_var++) {
125 #define FOR_EACH_CIRCUIT_MACHINE_END } STMT_END ;
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]) \
133 #define FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END } STMT_END ;
188 if (!(reason == END_CIRC_REASON_NONE ||
189 reason == END_CIRC_REASON_FINISHED ||
190 reason == END_CIRC_REASON_IP_NOW_REDUNDANT)) {
219 log_info(
LD_CIRC,
"Circuit %d is not marked for close because of a "
220 "pending padding machine in index %d.",
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. "
261 } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
276 uint32_t machine_ctr)
287 "Padding shutdown for wrong (old?) machine ctr: %u vs %u",
295 } FOR_EACH_CIRCUIT_MACHINE_END;
308 } FOR_EACH_CIRCUIT_MACHINE_END;
343 "Invalid circuit padding state %d",
370 if (BUG(state == NULL)) {
385 return state->histogram_edges[bin] + rtt_add_usec;
407 return left_bound + (right_bound - left_bound)/2;
428 if (BUG(state == NULL)) {
535 if (!state || state->
length_dist.type == CIRCPAD_DIST_NONE) {
541 length =
MAX(0, length);
550 log_info(
LD_CIRC,
"State length sampled to %"PRIu64
" for circuit %u",
571 val = MIN(val, state->dist_max_sample_usec);
599 uint64_t curr_weight = 0;
600 uint64_t histogram_total_tokens = 0;
605 if (state->
iat_dist.type != CIRCPAD_DIST_NONE) {
609 state->dist_added_shift_usec;
614 histogram_total_tokens += histogram[b];
622 if (!histogram_total_tokens) {
627 histogram_total_tokens);
630 while (!histogram[curr_bin]) {
633 curr_weight = histogram[curr_bin];
637 while (curr_weight < bin_choice) {
643 curr_weight += histogram[curr_bin];
648 BUG(histogram[curr_bin] == 0)) {
676 if (BUG(bin_start >= bin_end)) {
696 case CIRCPAD_DIST_NONE:
702 case CIRCPAD_DIST_UNIFORM:
706 .base = UNIFORM(my_uniform),
710 return dist_sample(&my_uniform.base);
712 case CIRCPAD_DIST_LOGISTIC:
716 .base = LOGISTIC(my_logistic),
718 .sigma = dist.param2,
720 return dist_sample(&my_logistic.base);
722 case CIRCPAD_DIST_LOG_LOGISTIC:
726 .base = LOG_LOGISTIC(my_log_logistic),
727 .alpha = dist.param1,
730 return dist_sample(&my_log_logistic.base);
732 case CIRCPAD_DIST_GEOMETRIC:
736 .base = GEOMETRIC(my_geometric),
739 return dist_sample(&my_geometric.base);
741 case CIRCPAD_DIST_WEIBULL:
745 .base = WEIBULL(my_weibull),
747 .lambda = dist.param2,
749 return dist_sample(&my_weibull.base);
751 case CIRCPAD_DIST_PARETO:
755 .base = GENPARETO(my_genpareto),
757 .sigma = dist.param1,
760 return dist_sample(&my_genpareto.base);
805 for (; bin >= 0; bin--) {
860 #define ENSURE_BIN_CAPACITY(bin_index) \
861 if (BUG(mi->histogram[bin_index] == 0)) { \
888 if (BUG(lower > current) || BUG(higher < current)) {
898 ENSURE_BIN_CAPACITY(lower);
901 }
else if (lower == -1) {
903 ENSURE_BIN_CAPACITY(higher);
915 if (target_bin_usec < lower_usec) {
917 ENSURE_BIN_CAPACITY(lower);
918 bin_to_remove = lower;
919 }
else if (target_bin_usec > higher_usec) {
921 ENSURE_BIN_CAPACITY(higher);
922 bin_to_remove = higher;
923 }
else if (target_bin_usec-lower_usec > higher_usec-target_bin_usec) {
925 ENSURE_BIN_CAPACITY(higher);
926 bin_to_remove = higher;
929 ENSURE_BIN_CAPACITY(lower);
930 bin_to_remove = lower;
933 log_debug(
LD_CIRC,
"Removing token from bin %d", bin_to_remove);
936 if (current - lower > higher - current) {
938 ENSURE_BIN_CAPACITY(higher);
943 ENSURE_BIN_CAPACITY(lower);
950 #undef ENSURE_BIN_CAPACITY
979 uint32_t histogram_total_tokens = 0;
990 histogram_total_tokens += mi->
histogram[b];
993 if (histogram_total_tokens == 0) {
995 return CIRCPAD_STATE_CHANGED;
1003 return CIRCPAD_STATE_UNCHANGED;
1016 if (mi->
state_length != CIRCPAD_STATE_LENGTH_INFINITE &&
1165 log_warn(
LD_BUG,
"Circpad: Unknown token removal strategy %d",
1183 uint8_t relay_command,
const uint8_t *payload,
1184 ssize_t payload_len))
1197 if (target_hop->
state != CPATH_STATE_OPEN) {
1199 "Padding circuit %u has %d hops, not %d",
1206 ret = relay_send_command_from_edge(0,
TO_CIRCUIT(circ), relay_command,
1207 (
const char*)payload, payload_len,
1235 "Padding callback on circuit marked for close (%u). Ignoring.",
1238 return CIRCPAD_STATE_CHANGED;
1246 RELAY_COMMAND_DROP, NULL, 0);
1247 log_info(
LD_CIRC,
"Callback: Sending padding to origin circuit %u"
1248 " (%d) [length: %"PRIu64
"]",
1254 if (
TO_OR_CIRCUIT(circ)->p_chan_cells.n <= circpad_max_circ_queued_cells) {
1255 log_info(
LD_CIRC,
"Callback: Sending padding to circuit (%d)"
1257 relay_send_command_from_edge(0, mi->
on_circ, RELAY_COMMAND_DROP, NULL,
1261 static ratelim_t cell_lim = RATELIM_INIT(600);
1263 "Too many cells (%d) in circ queue to send padding.",
1277 return CIRCPAD_STATE_CHANGED;
1281 return CIRCPAD_STATE_CHANGED;
1298 (void)timer; (void)time;
1306 "Circuit closed while waiting for padding timer.");
1324 circpad_padding_reduced =
1328 circpad_global_allowed_cells =
1330 0, 0, UINT16_MAX-1);
1332 circpad_global_max_padding_percent =
1336 circpad_max_circ_queued_cells =
1338 CIRCWINDOW_START_MAX, 0, 50*CIRCWINDOW_START_MAX);
1394 if (circpad_global_max_padding_percent &&
1397 circpad_global_nonpadding_sent;
1401 circpad_global_max_padding_percent) {
1429 static ratelim_t padding_lim = RATELIM_INIT(600);
1431 "Padding has been disabled, but machine still on circuit %"PRIu64
1436 return CIRCPAD_STATE_UNCHANGED;
1441 log_info(
LD_CIRC,
"Not scheduling padding because we are dormant.");
1442 return CIRCPAD_STATE_UNCHANGED;
1451 return CIRCPAD_STATE_UNCHANGED;
1458 "Padding machine has reached padding limit on circuit %u",
1461 static ratelim_t padding_lim = RATELIM_INIT(600);
1463 "Padding machine has reached padding limit on circuit %"PRIu64
1468 return CIRCPAD_STATE_UNCHANGED;
1506 return CIRCPAD_STATE_UNCHANGED;
1533 return CIRCPAD_STATE_UNCHANGED;
1580 CIRCPAD_COMMAND_STOP,
1588 CIRCPAD_COMMAND_STOP,
1589 CIRCPAD_RESPONSE_OK,
1614 return CIRCPAD_STATE_UNCHANGED;
1619 return CIRCPAD_STATE_UNCHANGED;
1628 return CIRCPAD_STATE_UNCHANGED;
1639 "Circuit %u circpad machine %d transitioning from %u to %u",
1658 return CIRCPAD_STATE_CHANGED;
1663 return CIRCPAD_STATE_CHANGED;
1671 return CIRCPAD_STATE_UNCHANGED;
1712 "Stopping padding RTT estimation on circuit (%"PRIu64
1713 ", %d) after two back to back packets. Current RTT: %d",
1719 static ratelim_t rtt_lim = RATELIM_INIT(600);
1721 "Circuit got two cells back to back before estimating RTT.");
1771 if (rtt_time >= INT32_MAX) {
1773 "Circuit padding RTT estimate overflowed: %"PRIu64
1796 static ratelim_t rtt_lim = RATELIM_INIT(600);
1798 "Circuit sent two cells back to back before estimating RTT.");
1816 circpad_global_nonpadding_sent++;
1830 == CIRCPAD_STATE_UNCHANGED) {
1834 CIRCPAD_EVENT_NONPADDING_SENT);
1836 } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
1851 case RELAY_COMMAND_DROP:
1854 case RELAY_COMMAND_PADDING_NEGOTIATE:
1857 case RELAY_COMMAND_PADDING_NEGOTIATED:
1885 "Ignored cell (%d) that arrived in padding circuit "
1911 CIRCPAD_EVENT_NONPADDING_RECV);
1912 } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
1930 == CIRCPAD_STATE_UNCHANGED) {
1936 CIRCPAD_EVENT_PADDING_SENT);
1938 } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
1956 CIRCPAD_EVENT_PADDING_RECV);
1957 } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
1987 == CIRCPAD_STATE_CHANGED) {
1988 return CIRCPAD_STATE_CHANGED;
1992 return CIRCPAD_STATE_UNCHANGED;
2023 if (circpad_padding_reduced ||
get_options()->ReducedCircuitPadding) {
2089 retmask |= CIRCPAD_CIRC_STREAMS;
2091 retmask |= CIRCPAD_CIRC_NO_STREAMS;
2095 retmask |= CIRCPAD_CIRC_OPENED;
2097 retmask |= CIRCPAD_CIRC_BUILDING;
2100 retmask |= CIRCPAD_CIRC_HAS_RELAY_EARLY;
2102 retmask |= CIRCPAD_CIRC_HAS_NO_RELAY_EARLY;
2115 if (BUG(circ_purpose <= CIRCUIT_PURPOSE_OR_MAX_)) {
2121 if (BUG(circ_purpose - CIRCUIT_PURPOSE_OR_MAX_ - 1 > 32)) {
2126 return 1 << (circ_purpose - CIRCUIT_PURPOSE_OR_MAX_ - 1);
2153 CIRCPAD_COMMAND_STOP,
2156 } FOR_EACH_ACTIVE_CIRCUIT_MACHINE_END;
2175 #ifdef TOR_UNIT_TESTS
2182 if (on_circ->padding_negotiation_failed)
2202 if (machine->machine_index == i &&
2209 machine->target_hopnum)
2218 circpad_setup_machine_on_circ(circ, machine);
2220 machine->target_hopnum,
2221 CIRCPAD_COMMAND_START,
2224 "Padding not negotiated. Cleaning machine from circuit %u",
2229 on_circ->padding_negotiation_failed = 1;
2235 } SMARTLIST_FOREACH_END(machine);
2236 } FOR_EACH_CIRCUIT_MACHINE_END;
2351 if (target_hop == from_hop)
2353 } FOR_EACH_CIRCUIT_MACHINE_END;
2398 uint8_t relay_command,
2401 if (relay_command == RELAY_COMMAND_DROP) {
2435 uint8_t relay_command)
2443 if (relay_command == RELAY_COMMAND_DROP) {
2474 for (
int e = 0; e < CIRCPAD_NUM_EVENTS; e++) {
2481 circpad_setup_machine_on_circ(
circuit_t *on_circ,
2486 "Can't set up non-origin machine on origin circuit!");
2492 "Can't set up origin machine on non-origin circuit!");
2505 log_info(
LD_CIRC,
"Registering machine %s to origin circ %u (%d)",
2509 log_info(
LD_CIRC,
"Registering machine %s to non-origin circ (%d)",
2510 machine->name, on_circ->
purpose);
2534 uint32_t tokens_count = 0;
2544 log_warn(
LD_CIRC,
"You can't have a histogram with less than 2 bins");
2553 if (prev_bin_edge >= state->histogram_edges[b] && b > 0) {
2554 log_warn(
LD_CIRC,
"Histogram edges are not increasing [%u/%u]",
2555 prev_bin_edge, state->histogram_edges[b]);
2559 prev_bin_edge = state->histogram_edges[b];
2566 log_warn(
LD_CIRC,
"Histogram token count is wrong [%u/%u]",
2581 for (i = 0 ; i < machine->
num_states ; i++) {
2597 log_warn(
LD_CIRC,
"Machine #%u is invalid. Ignoring.",
2607 #ifdef TOR_UNIT_TESTS
2610 circpad_circ_client_machine_init(
void)
2617 CIRCPAD_CIRC_BUILDING|CIRCPAD_CIRC_OPENED|CIRCPAD_CIRC_HAS_RELAY_EARLY;
2660 circpad_register_padding_machine(circ_client_machine,
2665 circpad_circ_responder_machine_init(
void)
2719 histogram_total_tokens = 1;
2761 circpad_register_padding_machine(circ_responder_machine,
2790 #ifdef TOR_UNIT_TESTS
2791 circpad_circ_client_machine_init();
2792 circpad_circ_responder_machine_init();
2826 "supported" :
"unsupported");
2845 if (!iter || iter->
state != CPATH_STATE_OPEN)
2876 uint8_t target_hopnum,
2878 uint32_t machine_ctr)
2880 circpad_negotiate_t type;
2890 memset(&cell, 0,
sizeof(
cell_t));
2891 memset(&type, 0,
sizeof(circpad_negotiate_t));
2897 circpad_negotiate_set_command(&type,
command);
2898 circpad_negotiate_set_version(&type, 0);
2899 circpad_negotiate_set_machine_type(&type, machine);
2900 circpad_negotiate_set_machine_ctr(&type, machine_ctr);
2907 "Negotiating padding on circuit %u (%d), command %d, for ctr %u",
2912 RELAY_COMMAND_PADDING_NEGOTIATE,
2926 uint32_t machine_ctr)
2928 circpad_negotiated_t type;
2932 memset(&cell, 0,
sizeof(
cell_t));
2933 memset(&type, 0,
sizeof(circpad_negotiated_t));
2939 circpad_negotiated_set_command(&type,
command);
2940 circpad_negotiated_set_response(&type, response);
2941 circpad_negotiated_set_version(&type, 0);
2942 circpad_negotiated_set_machine_type(&type, machine);
2943 circpad_negotiated_set_machine_ctr(&type, machine_ctr);
2951 return relay_send_command_from_edge(0, circ,
2952 RELAY_COMMAND_PADDING_NEGOTIATED,
2954 (
size_t)len, NULL) == 0;
2970 circpad_negotiate_t *negotiate;
2974 "Padding negotiate cell unsupported at origin (circuit %u)",
2982 "Received malformed PADDING_NEGOTIATE cell; dropping.");
2986 if (negotiate->command == CIRCPAD_COMMAND_STOP) {
2989 negotiate->machine_type,
2990 negotiate->machine_ctr)) {
2991 log_info(
LD_CIRC,
"Received STOP command for machine %u, ctr %u",
2992 negotiate->machine_type, negotiate->machine_ctr);
2996 log_info(
LD_CIRC,
"Received STOP command for old machine %u, ctr %u",
2997 negotiate->machine_type, negotiate->machine_ctr);
3002 "Received circuit padding stop command for unknown machine.");
3005 }
else if (negotiate->command == CIRCPAD_COMMAND_START) {
3008 if (m->machine_num == negotiate->machine_type) {
3009 circpad_setup_machine_on_circ(circ, m);
3010 if (negotiate->machine_ctr &&
3013 "Client and relay have different counts for padding machines: "
3019 } SMARTLIST_FOREACH_END(m);
3028 (retval == 0) ? CIRCPAD_RESPONSE_OK : CIRCPAD_RESPONSE_ERR,
3029 negotiate->machine_ctr);
3030 circpad_negotiate_free(negotiate);
3047 circpad_negotiated_t *negotiated;
3051 "Padding negotiated cell unsupported at non-origin.");
3058 "Padding negotiated cell from wrong hop on circuit %u",
3066 "Received malformed PADDING_NEGOTIATED cell on circuit %u; "
3071 if (negotiated->command == CIRCPAD_COMMAND_STOP) {
3073 "Received STOP command on PADDING_NEGOTIATED for circuit %u",
3081 negotiated->machine_ctr);
3082 }
else if (negotiated->command == CIRCPAD_COMMAND_START &&
3083 negotiated->response == CIRCPAD_RESPONSE_ERR) {
3087 negotiated->machine_ctr)) {
3091 "Middle node did not accept our padding request on circuit "
3098 circpad_negotiated_free(negotiated);
3119 machine_spec_free(m);
3120 } SMARTLIST_FOREACH_END(m);
3126 machine_spec_free(m);
3127 } SMARTLIST_FOREACH_END(m);
3146 state->transition_cancel_events);
3148 for (
int i = 0; i < CIRCPAD_NUM_STATES; i++) {
3150 state->transition_events[i]);
3165 circpad_state_serialize(&machine->start, chunks);
3166 circpad_state_serialize(&machine->gap, chunks);
3167 circpad_state_serialize(&machine->burst, chunks);
3172 smartlist_free(chunks);
3178 circpad_string_to_machine(
const char *str)