Tor 0.4.9.2-alpha-dev
All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Modules Pages
conflux.c
Go to the documentation of this file.
1/* Copyright (c) 2021, The Tor Project, Inc. */
2/* See LICENSE for licensing information */
3
4/**
5 * \file conflux.c
6 * \brief Conflux multipath core algorithms
7 */
8
9#include "core/or/relay_msg.h"
10#define TOR_CONFLUX_PRIVATE
11
12#include "core/or/or.h"
13
14#include "core/or/circuit_st.h"
15#include "core/or/sendme.h"
16#include "core/or/relay.h"
20#include "core/or/circuitlist.h"
21#include "core/or/circuituse.h"
22#include "core/or/conflux.h"
26#include "core/or/conflux_st.h"
29#include "app/config/config.h"
30
31/** One million microseconds in a second */
32#define USEC_PER_SEC 1000000
33
34static inline uint64_t cwnd_sendable(const circuit_t *on_circ,
35 uint64_t in_usec, uint64_t our_usec);
36
37/* Track the total number of bytes used by all ooo_q so it can be used by the
38 * OOM handler to assess. */
39static uint64_t total_ooo_q_bytes = 0;
40
41/**
42 * Determine if we should multiplex a specific relay command or not.
43 *
44 * TODO: Version of this that is the set of forbidden commands
45 * on linked circuits
46 */
47bool
48conflux_should_multiplex(int relay_command)
49{
50 switch (relay_command) {
51 /* These are all fine to multiplex, and must be
52 * so that ordering is preserved */
53 case RELAY_COMMAND_BEGIN:
54 case RELAY_COMMAND_DATA:
55 case RELAY_COMMAND_END:
56 case RELAY_COMMAND_CONNECTED:
57 return true;
58
59 /* We can't multiplex these because they are
60 * circuit-specific */
61 case RELAY_COMMAND_SENDME:
62 case RELAY_COMMAND_EXTEND:
63 case RELAY_COMMAND_EXTENDED:
64 case RELAY_COMMAND_TRUNCATE:
65 case RELAY_COMMAND_TRUNCATED:
66 case RELAY_COMMAND_DROP:
67 return false;
68
69 /* We must multiplex RESOLVEs because their ordering
70 * impacts begin/end. */
71 case RELAY_COMMAND_RESOLVE:
72 case RELAY_COMMAND_RESOLVED:
73 return true;
74
75 /* These are all circuit-specific */
76 case RELAY_COMMAND_BEGIN_DIR:
77 case RELAY_COMMAND_EXTEND2:
78 case RELAY_COMMAND_EXTENDED2:
79 case RELAY_COMMAND_ESTABLISH_INTRO:
80 case RELAY_COMMAND_ESTABLISH_RENDEZVOUS:
81 case RELAY_COMMAND_INTRODUCE1:
82 case RELAY_COMMAND_INTRODUCE2:
83 case RELAY_COMMAND_RENDEZVOUS1:
84 case RELAY_COMMAND_RENDEZVOUS2:
85 case RELAY_COMMAND_INTRO_ESTABLISHED:
86 case RELAY_COMMAND_RENDEZVOUS_ESTABLISHED:
87 case RELAY_COMMAND_INTRODUCE_ACK:
88 case RELAY_COMMAND_PADDING_NEGOTIATE:
89 case RELAY_COMMAND_PADDING_NEGOTIATED:
90 return false;
91
92 /* These must be multiplexed because their ordering
93 * relative to BEGIN/END must be preserved */
94 case RELAY_COMMAND_XOFF:
95 case RELAY_COMMAND_XON:
96 return true;
97
98 /* These two are not multiplexed, because they must
99 * be processed immediately to update sequence numbers
100 * before any other cells are processed on the circuit */
101 case RELAY_COMMAND_CONFLUX_SWITCH:
102 case RELAY_COMMAND_CONFLUX_LINK:
103 case RELAY_COMMAND_CONFLUX_LINKED:
104 case RELAY_COMMAND_CONFLUX_LINKED_ACK:
105 return false;
106
107 default:
108 log_warn(LD_BUG, "Conflux asked to multiplex unknown relay command %d",
109 relay_command);
110 return false;
111 }
112}
113
114/** Return the leg for a circuit in a conflux set. Return NULL if not found. */
117{
118 conflux_leg_t *leg_found = NULL;
119 tor_assert(cfx);
120 tor_assert(cfx->legs);
121
122 // Find the leg that the cell is written on
124 if (leg->circ == circ) {
125 leg_found = leg;
126 break;
127 }
128 } CONFLUX_FOR_EACH_LEG_END(leg);
129
130 return leg_found;
131}
132
133/**
134 * Gets the maximum last_seq_sent from all legs.
135 */
136uint64_t
138{
139 uint64_t max_seq_sent = 0;
140
142 if (leg->last_seq_sent > max_seq_sent) {
143 max_seq_sent = leg->last_seq_sent;
144 }
145 } CONFLUX_FOR_EACH_LEG_END(leg);
146
147 return max_seq_sent;
148}
149
150/**
151 * Gets the maximum last_seq_recv from all legs.
152 */
153uint64_t
155{
156 uint64_t max_seq_recv = 0;
157
159 if (leg->last_seq_recv > max_seq_recv) {
160 max_seq_recv = leg->last_seq_recv;
161 }
162 } CONFLUX_FOR_EACH_LEG_END(leg);
163
164 return max_seq_recv;
165}
166
167/** Return the total memory allocation the circuit is using by conflux. If this
168 * circuit is not a Conflux circuit, 0 is returned. */
169uint64_t
171{
172 if (circ->conflux) {
173 return smartlist_len(circ->conflux->ooo_q) * sizeof(conflux_msg_t);
174 }
175 return 0;
176}
177
178/** Return the total memory allocation in bytes by the subsystem.
179 *
180 * At the moment, only out of order queues are consiered. */
181uint64_t
183{
184 return total_ooo_q_bytes;
185}
186
187/** The OOM handler is asking us to try to free at least bytes_to_remove. */
188size_t
189conflux_handle_oom(size_t bytes_to_remove)
190{
191 (void) bytes_to_remove;
192
193 /* We are not doing anything on the sets, the OOM handler will trigger a
194 * circuit clean up which will affect conflux sets, by pruning oldest
195 * circuits. */
196
197 log_info(LD_CIRC, "OOM handler triggered. OOO queus allocation: %" PRIu64,
198 total_ooo_q_bytes);
199 return 0;
200}
201
202/**
203 * Returns true if a circuit has package window space to send, and is
204 * not blocked locally.
205 */
206static inline bool
208{
209 const congestion_control_t *cc = circuit_ccontrol(circ);
210 bool cc_sendable = true;
211
212 /* We consider ourselves blocked if we're within 1 sendme of the
213 * cwnd, because inflight is decremented before this check */
214 // TODO-329-TUNING: This subtraction not be right.. It depends
215 // on call order wrt decisions and sendme arrival
216 if (cc->inflight >= cc->cwnd) {
217 cc_sendable = false;
218 }
219
220 /* Origin circuits use the package window of the last hop, and
221 * have an outbound cell direction (towards exit). Otherwise,
222 * there is no cpath and direction is inbound. */
223 if (CIRCUIT_IS_ORIGIN(circ)) {
224 return cc_sendable && !circ->circuit_blocked_on_n_chan;
225 } else {
226 return cc_sendable && !circ->circuit_blocked_on_p_chan;
227 }
228}
229
230/**
231 * Return the circuit with the minimum RTT. Do not use any
232 * other circuit.
233 *
234 * This algorithm will minimize RTT always, and will not provide
235 * any throughput benefit. We expect it to be useful for VoIP/UDP
236 * use cases. Because it only uses one circuit on a leg at a time,
237 * it can have more than one circuit per guard (ie: to find
238 * lower-latency middles for the path).
239 */
240static const circuit_t *
242{
243 uint64_t min_rtt = UINT64_MAX;
244 const circuit_t *circ = NULL;
245
246 /* Can't get here without any legs. */
248
250
251 /* Ignore circuits with no RTT measurement */
252 if (leg->circ_rtts_usec && leg->circ_rtts_usec < min_rtt) {
253 circ = leg->circ;
254 min_rtt = leg->circ_rtts_usec;
255 }
256 } CONFLUX_FOR_EACH_LEG_END(leg);
257
258 /* If the minRTT circuit can't send, dont send on any circuit. */
259 if (!circ || !circuit_ready_to_send(circ)) {
260 return NULL;
261 }
262 return circ;
263}
264
265/**
266 * Favor the circuit with the lowest RTT that still has space in the
267 * congestion window.
268 *
269 * This algorithm will maximize total throughput at the expense of
270 * bloating out-of-order queues.
271 */
272static const circuit_t *
274{
275 uint64_t low_rtt = UINT64_MAX;
276 const circuit_t *circ = NULL;
277
278 /* Can't get here without any legs. */
280
282 /* If the package window is full, skip it */
283 if (!circuit_ready_to_send(leg->circ)) {
284 continue;
285 }
286
287 /* Ignore circuits with no RTT */
288 if (leg->circ_rtts_usec && leg->circ_rtts_usec < low_rtt) {
289 low_rtt = leg->circ_rtts_usec;
290 circ = leg->circ;
291 }
292 } CONFLUX_FOR_EACH_LEG_END(leg);
293
294 /* At this point, if we found a circuit, we've already validated that its
295 * congestion window has room. */
296 return circ;
297}
298
299/**
300 * Returns the amount of room in a cwnd on a circuit.
301 */
302static inline uint64_t
304{
305 const congestion_control_t *cc = circuit_ccontrol(on_circ);
306 tor_assert(cc);
307
308 if (cc->cwnd < cc->inflight)
309 return 0;
310
311 return cc->cwnd - cc->inflight;
312}
313
314/**
315 * Return the amount of congestion window we can send on
316 * on_circ during in_usec. However, if we're still in
317 * slow-start, send the whole window to establish the true
318 * cwnd.
319 */
320static inline uint64_t
321cwnd_sendable(const circuit_t *on_circ, uint64_t in_usec,
322 uint64_t our_usec)
323{
324 const congestion_control_t *cc = circuit_ccontrol(on_circ);
325 tor_assert(cc);
326 uint64_t cwnd_adjusted = cwnd_available(on_circ);
327
328 if (our_usec == 0 || in_usec == 0) {
329 log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
330 "cwnd_sendable: Missing RTT data. in_usec: %" PRIu64
331 " our_usec: %" PRIu64, in_usec, our_usec);
332 return cwnd_adjusted;
333 }
334
335 if (cc->in_slow_start) {
336 return cwnd_adjusted;
337 } else {
338 /* For any given leg, it has min_rtt/2 time before the 'primary'
339 * leg's acks start arriving. So, the amount of data this
340 * 'secondary' leg can send while the min_rtt leg transmits these
341 * acks is:
342 * (cwnd_leg/(leg_rtt/2))*min_rtt/2 = cwnd_leg*min_rtt/leg_rtt.
343 */
344 uint64_t sendable = cwnd_adjusted*in_usec/our_usec;
345 return MIN(cc->cwnd, sendable);
346 }
347}
348
349/**
350 * Returns true if we can switch to a new circuit, false otherwise.
351 *
352 * This function assumes we're primarily switching between two circuits,
353 * the current and the prev. If we're using more than two circuits, we
354 * need to set cfx_drain_pct to 100.
355 */
356static inline bool
358{
359 /* If we still expected to send more cells on this circuit,
360 * we're only allowed to switch if the previous circuit emptied. */
361 if (cfx->cells_until_switch > 0) {
362 /* If there is no prev leg, skip the inflight check. */
363 if (!cfx->prev_leg) {
364 return false;
365 }
366 const congestion_control_t *ccontrol =
368
369 /* If the inflight count has drained to below cfx_drain_pct
370 * of the congestion window, then we can switch.
371 * We check the sendme_inc because there may be un-ackable
372 * data in inflight as well, and we can still switch then. */
373 // TODO-329-TUNING: Should we try to switch if the prev_leg is
374 // ready to send, instead of this?
375 if (ccontrol->inflight < ccontrol->sendme_inc ||
376 100*ccontrol->inflight <=
378 return true;
379 }
380
381 return false;
382 }
383
384 return true;
385}
386
387/**
388 * Favor the circuit with the lowest RTT that still has space in the
389 * congestion window up to the ratio of RTTs.
390 *
391 * This algorithm should only use auxillary legs up to the point
392 * where their data arrives roughly the same time as the lowest
393 * RTT leg. It will not utilize the full cwnd of auxillary legs,
394 * except in slow start. Therefore, out-of-order queue bloat should
395 * be minimized to just the slow-start phase.
396 */
397static const circuit_t *
399{
400 uint64_t min_rtt = UINT64_MAX;
401 const conflux_leg_t *leg = NULL;
402
403 /* Can't get here without any legs. */
405
406 /* Find the leg with the minimum RTT.*/
408 /* Ignore circuits with invalid RTT */
409 if (l->circ_rtts_usec && l->circ_rtts_usec < min_rtt) {
410 min_rtt = l->circ_rtts_usec;
411 leg = l;
412 }
413 } CONFLUX_FOR_EACH_LEG_END(l);
414
415 /* If the package window is has room, use it */
416 if (leg && circuit_ready_to_send(leg->circ)) {
417 return leg->circ;
418 }
419
420 leg = NULL;
421
423 if (!circuit_ready_to_send(l->circ)) {
424 continue;
425 }
426
427 /* Pick a 'min_leg' with the lowest RTT that still has
428 * room in the congestion window. Note that this works for
429 * min_leg itself, up to inflight. */
430 if (l->circ_rtts_usec &&
431 cwnd_sendable(l->circ, min_rtt, l->circ_rtts_usec) > 0) {
432 leg = l;
433 }
434 } CONFLUX_FOR_EACH_LEG_END(l);
435
436 /* If the circuit can't send, don't send on any circuit. */
437 if (!leg || !circuit_ready_to_send(leg->circ)) {
438 return NULL;
439 }
440 return leg->circ;
441}
442
443/**
444 * This function is called when we want to send a relay cell on a
445 * conflux, as well as when we want to compute available space in
446 * to package from streams.
447 *
448 * It determines the circuit that relay command should be sent on,
449 * and sends a SWITCH cell if necessary.
450 *
451 * It returns the circuit we should send on. If no circuits are ready
452 * to send, it returns NULL.
453 */
454circuit_t *
456 circuit_t *orig_circ,
457 uint8_t relay_command)
458{
459 /* If this command should not be multiplexed, send it on the original
460 * circuit */
461 if (!conflux_should_multiplex(relay_command)) {
462 return orig_circ;
463 }
464
465 circuit_t *new_circ = conflux_decide_next_circ(cfx);
466
467 /* Because our congestion window only cover relay data command, we can end up
468 * in a situation where we need to send non data command when all circuits
469 * are at capacity. For those cases, keep using the *current* leg,
470 * so these commands arrive in-order. */
471 if (!new_circ && relay_command != RELAY_COMMAND_DATA) {
472 /* Curr leg should be set, because conflux_decide_next_circ() should
473 * have set it earlier. No BUG() here because the only caller BUG()s. */
474 if (!cfx->curr_leg) {
475 log_warn(LD_BUG, "No current leg for conflux with relay command %d",
476 relay_command);
477 return NULL;
478 }
479 return cfx->curr_leg->circ;
480 }
481
482 /*
483 * If we are switching to a new circuit, we need to send a SWITCH command.
484 * We also need to compute an estimate of how much data we can send on
485 * the new circuit before we are allowed to switch again, to rate
486 * limit the frequency of switching.
487 */
488 if (new_circ) {
489 conflux_leg_t *new_leg = conflux_get_leg(cfx, new_circ);
490 tor_assert(cfx->curr_leg);
491
492 if (new_circ != cfx->curr_leg->circ) {
493 // TODO-329-TUNING: This is one mechanism to rate limit switching,
494 // which should reduce the OOQ mem. However, we're not going to do that
495 // until we get some data on if the memory usage is high
496 cfx->cells_until_switch = 0;
497 //cwnd_sendable(new_circ,cfx->curr_leg->circ_rtts_usec,
498 // new_leg->circ_rtts_usec);
499
501
502 cfx->prev_leg = cfx->curr_leg;
503 cfx->curr_leg = new_leg;
504
505 tor_assert(cfx->prev_leg);
506 tor_assert(cfx->curr_leg);
507
508 uint64_t relative_seq = cfx->prev_leg->last_seq_sent -
510
512 cfx->curr_leg->last_seq_sent);
513 conflux_send_switch_command(cfx->curr_leg->circ, relative_seq);
515 }
516 }
517
518 return new_circ;
519}
520
521/** Called after conflux actually sent a cell on a circuit.
522 * This function updates sequence number counters, and
523 * switch counters.
524 */
525void
526conflux_note_cell_sent(conflux_t *cfx, circuit_t *circ, uint8_t relay_command)
527{
528 conflux_leg_t *leg = NULL;
529
530 if (!conflux_should_multiplex(relay_command)) {
531 return;
532 }
533
534 leg = conflux_get_leg(cfx, circ);
535 if (leg == NULL) {
536 log_fn(LOG_PROTOCOL_WARN, LD_BUG, "No Conflux leg after sending a cell");
537 return;
538 }
539
540 leg->last_seq_sent++;
541
542 if (cfx->cells_until_switch > 0) {
543 cfx->cells_until_switch--;
544 }
545}
546
547/** Find the leg with lowest non-zero curr_rtt_usec, and
548 * pick it for our current leg. */
549static inline bool
551{
552 conflux_leg_t *min_leg = NULL;
553
555 /* We need to skip 0-RTT legs, since this can happen at the exit
556 * when there is a race between BEGIN and LINKED_ACK, and BEGIN
557 * wins the race. The good news is that because BEGIN won,
558 * we don't need to consider those other legs, since they are
559 * slower. */
560 if (leg->circ_rtts_usec > 0) {
561 if (!min_leg || leg->circ_rtts_usec < min_leg->circ_rtts_usec) {
562 min_leg = leg;
563 }
564 }
565 } CONFLUX_FOR_EACH_LEG_END(leg);
566
567 if (!min_leg) {
568 // Get the 0th leg; if it does not exist, log the set.
569 // Bug 40827 managed to hit this, so let's dump the sets
570 // in case it happens again.
571 if (BUG(smartlist_len(cfx->legs) <= 0)) {
572 // Since we have no legs, we have no idea if this is really a client
573 // or server set. Try to find any that match:
574 log_warn(LD_BUG, "Matching client sets:");
575 conflux_log_set(LOG_WARN, cfx, true);
576 log_warn(LD_BUG, "Matching server sets:");
577 conflux_log_set(LOG_WARN, cfx, false);
578 log_warn(LD_BUG, "End conflux set dump");
579 return false;
580 }
581
582 min_leg = smartlist_get(cfx->legs, 0);
583 tor_assert(min_leg);
584 if (BUG(min_leg->linked_sent_usec == 0)) {
585 log_warn(LD_BUG, "Conflux has no legs with non-zero RTT. "
586 "Using first leg.");
588 }
589 }
590
591 // TODO-329-TUNING: We may want to initialize this to a cwnd, to
592 // minimize early switching?
593 //cfx->cells_until_switch = circuit_ccontrol(min_leg->circ)->cwnd;
594 cfx->cells_until_switch = 0;
595
596 cfx->curr_leg = min_leg;
597
598 return true;
599}
600
601/**
602 * Returns the circuit that conflux would send on next, if
603 * conflux_decide_circ_for_send were called. This is used to compute
604 * available space in the package window.
605 */
606circuit_t *
608{
609 // TODO-329-TUNING: Temporarily validate legs here. We can remove
610 // this once tuning is complete.
612
613 /* If the conflux set is tearing down and has no current leg,
614 * bail and give up */
615 if (cfx->in_full_teardown) {
616 return NULL;
617 }
618
619 /* If we don't have a current leg yet, pick one.
620 * (This is the only non-const operation in this function). */
621 if (!cfx->curr_leg) {
622 if (!conflux_pick_first_leg(cfx))
623 return NULL;
624 }
625
626 /* First, check if we can switch. */
627 if (!conflux_can_switch(cfx)) {
628 tor_assert(cfx->curr_leg);
629 circuit_t *curr_circ = cfx->curr_leg->circ;
630
631 /* If we can't switch, and the current circuit can't send,
632 * then return null. */
633 if (circuit_ready_to_send(curr_circ)) {
634 return curr_circ;
635 }
636 log_info(LD_CIRC, "Conflux can't switch; no circuit to send on.");
637 return NULL;
638 }
639
640 switch (cfx->params.alg) {
641 case CONFLUX_ALG_MINRTT: // latency (no ooq)
643 case CONFLUX_ALG_LOWRTT: // high throughput (high oooq)
645 case CONFLUX_ALG_CWNDRTT: // throughput (low oooq)
647 default:
648 return NULL;
649 }
650}
651
652/**
653 * Called when we have a new RTT estimate for a circuit.
654 */
655void
656conflux_update_rtt(conflux_t *cfx, circuit_t *circ, uint64_t rtt_usec)
657{
658 conflux_leg_t *leg = conflux_get_leg(cfx, circ);
659
660 if (!leg) {
661 log_warn(LD_BUG, "Got RTT update for circuit not in conflux");
662 return;
663 }
664
665 // Update RTT
666 leg->circ_rtts_usec = rtt_usec;
667
668 // TODO-329-ARTI: For UDP latency targeting, arti could decide to launch
669 // new a test leg to potentially replace this one, if a latency target
670 // was requested and we now exceed it. Since C-Tor client likely
671 // will not have UDP support, we aren't doing this here.
672}
673
674/**
675 * Comparison function for ooo_q pqueue.
676 *
677 * Ensures that lower sequence numbers are at the head of the pqueue.
678 */
679static int
680conflux_queue_cmp(const void *a, const void *b)
681{
682 // Compare a and b as conflux_cell_t using the seq field, and return a
683 // comparison result such that the lowest seq is at the head of the pqueue.
684 const conflux_msg_t *cell_a = a;
685 const conflux_msg_t *cell_b = b;
686
687 tor_assert(cell_a);
688 tor_assert(cell_b);
689
690 if (cell_a->seq < cell_b->seq) {
691 return -1;
692 } else if (cell_a->seq > cell_b->seq) {
693 return 1;
694 } else {
695 return 0;
696 }
697}
698
699/**
700 * Get the congestion control object for a conflux circuit.
701 *
702 * Because conflux can only be negotiated with the last hop, we
703 * can use the last hop of the cpath to obtain the congestion
704 * control object for origin circuits. For non-origin circuits,
705 * we can use the circuit itself.
706 */
709{
710 const congestion_control_t *ccontrol = NULL;
711 tor_assert(circ);
712
713 if (CIRCUIT_IS_ORIGIN(circ)) {
714 tor_assert(CONST_TO_ORIGIN_CIRCUIT(circ)->cpath);
715 tor_assert(CONST_TO_ORIGIN_CIRCUIT(circ)->cpath->prev);
716 ccontrol = CONST_TO_ORIGIN_CIRCUIT(circ)->cpath->prev->ccontrol;
717 } else {
718 ccontrol = circ->ccontrol;
719 }
720
721 /* Conflux circuits always have congestion control*/
722 tor_assert(ccontrol);
723 return ccontrol;
724}
725
726// TODO-329-TUNING: For LowRTT, we can at most switch every SENDME,
727// but for BLEST, we should switch at most every cwnd.. But
728// we do not know the other side's CWND here.. We can at best
729// asssume it is above the cwnd_min
730#define CONFLUX_MIN_LINK_INCREMENT 31
731/**
732 * Validate and handle RELAY_COMMAND_CONFLUX_SWITCH.
733 */
734int
736 crypt_path_t *layer_hint,
737 const relay_msg_t *msg)
738{
739 tor_assert(in_circ);
740 tor_assert(msg);
741
742 conflux_t *cfx = in_circ->conflux;
743 uint32_t relative_seq;
744 conflux_leg_t *leg;
745
746 if (!conflux_is_enabled(in_circ)) {
747 circuit_mark_for_close(in_circ, END_CIRC_REASON_TORPROTOCOL);
748 return -1;
749 }
750
751 /* If there is no conflux object negotiated, this is invalid.
752 * log and close circ */
753 if (!cfx) {
754 log_warn(LD_BUG, "Got a conflux switch command on a circuit without "
755 "conflux negotiated. Closing circuit.");
756
757 circuit_mark_for_close(in_circ, END_CIRC_REASON_TORPROTOCOL);
758 return -1;
759 }
760
761 // TODO-329-TUNING: Temporarily validate that we have all legs.
762 // After tuning is complete, we can remove this.
764
765 leg = conflux_get_leg(cfx, in_circ);
766
767 /* If we can't find the conflux leg, we got big problems..
768 * Close the circuit. */
769 if (!leg) {
770 log_warn(LD_BUG, "Got a conflux switch command on a circuit without "
771 "conflux leg. Closing circuit.");
772 circuit_mark_for_close(in_circ, END_CIRC_REASON_INTERNAL);
773 return -1;
774 }
775
776 // Check source hop via layer_hint
777 if (!conflux_validate_source_hop(in_circ, layer_hint)) {
778 log_warn(LD_BUG, "Got a conflux switch command on a circuit with "
779 "invalid source hop. Closing circuit.");
780 circuit_mark_for_close(in_circ, END_CIRC_REASON_TORPROTOCOL);
781 return -1;
782 }
783
784 relative_seq = conflux_cell_parse_switch(msg);
785
786 /*
787 * We have to make sure that the switch command is truely
788 * incrementing the sequence number, or else it becomes
789 * a side channel that can be spammed for traffic analysis.
790 */
791 // TODO-329-TUNING: This can happen. Disabling for now..
792 //if (relative_seq < CONFLUX_MIN_LINK_INCREMENT) {
793 // log_warn(LD_CIRC, "Got a conflux switch command with a relative "
794 // "sequence number less than the minimum increment. Closing "
795 // "circuit.");
796 // circuit_mark_for_close(in_circ, END_CIRC_REASON_TORPROTOCOL);
797 // return -1;
798 //}
799
800 // TODO-329-UDP: When Prop#340 exits and was negotiated, ensure we're
801 // in a packed cell, with another cell following, otherwise
802 // this is a spammed side-channel.
803 // - We definitely should never get switches back-to-back.
804 // - We should not get switches across all legs with no data
805 // But before Prop#340, it doesn't make much sense to do this.
806 // C-Tor is riddled with side-channels like this anyway, unless
807 // vanguards is in use. And this feature is not supported by
808 // onion servicees in C-Tor, so we're good there.
809
810 /* Update the absolute sequence number on this leg by the delta.
811 * Since this cell is not multiplexed, we do not count it towards
812 * absolute sequence numbers. We only increment the sequence
813 * numbers for multiplexed cells. Hence there is no +1 here. */
814 leg->last_seq_recv += relative_seq;
815
816 /* Mark this data as validated for controlport and vanguards
817 * dropped cell handling */
818 if (CIRCUIT_IS_ORIGIN(in_circ)) {
819 circuit_read_valid_data(TO_ORIGIN_CIRCUIT(in_circ), msg->length);
820 }
821
822 return 0;
823}
824
825/**
826 * Process an incoming relay cell for conflux. Called from
827 * connection_edge_process_relay_cell().
828 *
829 * Returns true if the conflux system now has well-ordered cells to deliver
830 * to streams, false otherwise.
831 */
832bool
834 crypt_path_t *layer_hint, const relay_msg_t *msg)
835{
836 // TODO-329-TUNING: Temporarily validate legs here. We can remove
837 // this after tuning is complete.
839
840 conflux_leg_t *leg = conflux_get_leg(cfx, in_circ);
841 if (!leg) {
842 log_warn(LD_BUG, "Got a conflux cell on a circuit without "
843 "conflux leg. Closing circuit.");
844 circuit_mark_for_close(in_circ, END_CIRC_REASON_INTERNAL);
845 return false;
846 }
847
848 /* We need to make sure this cell came from the expected hop, or
849 * else it could be a data corruption attack from a middle node. */
850 if (!conflux_validate_source_hop(in_circ, layer_hint)) {
851 circuit_mark_for_close(in_circ, END_CIRC_REASON_TORPROTOCOL);
852 return false;
853 }
854
855 /* Update the running absolute sequence number */
856 leg->last_seq_recv++;
857
858 /* If this cell is next, fast-path it by processing the cell in-place */
859 if (leg->last_seq_recv == cfx->last_seq_delivered + 1) {
860 /* The cell is now ready to be processed, and rest of the queue should
861 * now be checked for remaining elements */
862 cfx->last_seq_delivered++;
863 return true;
864 } else if (BUG(leg->last_seq_recv <= cfx->last_seq_delivered)) {
865 log_warn(LD_BUG, "Got a conflux cell with a sequence number "
866 "less than the last delivered. Closing circuit.");
867 circuit_mark_for_close(in_circ, END_CIRC_REASON_INTERNAL);
868 return false;
869 } else {
870 conflux_msg_t *c_msg = tor_malloc_zero(sizeof(conflux_msg_t));
871 c_msg->seq = leg->last_seq_recv;
872 /* Notice the copy here. Reason is that we don't have ownership of the
873 * message. If we wanted to pull that off, we would need to change the
874 * whole calling stack and unit tests on either not touching it after this
875 * function indicates that it has taken it or never allocate it from the
876 * stack. This is simpler and less error prone but might show up in our
877 * profile (maybe?). The Maze is serious. It needs to be respected. */
878 c_msg->msg = relay_msg_copy(msg);
879
881 offsetof(conflux_msg_t, heap_idx), c_msg);
882 total_ooo_q_bytes += sizeof(msg->length);
883
884 /* This cell should not be processed yet, and the queue is not ready
885 * to process because the next absolute seqnum has not yet arrived */
886 return false;
887 }
888}
889
890/**
891 * Dequeue the top cell from our queue.
892 *
893 * Returns the cell as a conflux_cell_t, or NULL if the queue is empty
894 * or has a hole.
895 */
898{
899 conflux_msg_t *top = NULL;
900 if (smartlist_len(cfx->ooo_q) == 0)
901 return NULL;
902
903 top = smartlist_get(cfx->ooo_q, 0);
904
905 /* If the top cell is the next sequence number we need, then
906 * pop and return it. */
907 if (top->seq == cfx->last_seq_delivered+1) {
909 offsetof(conflux_msg_t, heap_idx));
910 total_ooo_q_bytes -= sizeof(top->msg->length);
911 cfx->last_seq_delivered++;
912 return top;
913 } else {
914 return NULL;
915 }
916}
917
918/** Free a given conflux msg object. */
919void
921{
922 if (msg) {
923 relay_msg_free(msg->msg);
924 tor_free(msg);
925 }
926}
Base circuit structure.
origin_circuit_t * TO_ORIGIN_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:185
Header file for circuitlist.c.
#define CIRCUIT_IS_ORIGIN(c)
Definition: circuitlist.h:154
void circuit_read_valid_data(origin_circuit_t *circ, uint16_t relay_body_len)
Definition: circuituse.c:3202
Header file for circuituse.c.
Functions and types for monotonic times.
Header file for config.c.
void conflux_note_cell_sent(conflux_t *cfx, circuit_t *circ, uint8_t relay_command)
Definition: conflux.c:526
static uint64_t cwnd_sendable(const circuit_t *on_circ, uint64_t in_usec, uint64_t our_usec)
Definition: conflux.c:321
static bool conflux_pick_first_leg(conflux_t *cfx)
Definition: conflux.c:550
void conflux_update_rtt(conflux_t *cfx, circuit_t *circ, uint64_t rtt_usec)
Definition: conflux.c:656
bool conflux_should_multiplex(int relay_command)
Definition: conflux.c:48
circuit_t * conflux_decide_next_circ(conflux_t *cfx)
Definition: conflux.c:607
static int conflux_queue_cmp(const void *a, const void *b)
Definition: conflux.c:680
static const circuit_t * conflux_decide_circ_lowrtt(const conflux_t *cfx)
Definition: conflux.c:273
static uint64_t cwnd_available(const circuit_t *on_circ)
Definition: conflux.c:303
uint64_t conflux_get_circ_bytes_allocation(const circuit_t *circ)
Definition: conflux.c:170
const congestion_control_t * circuit_ccontrol(const circuit_t *circ)
Definition: conflux.c:708
uint64_t conflux_get_max_seq_recv(const conflux_t *cfx)
Definition: conflux.c:154
uint64_t conflux_get_max_seq_sent(const conflux_t *cfx)
Definition: conflux.c:137
void conflux_relay_msg_free_(conflux_msg_t *msg)
Definition: conflux.c:920
static bool conflux_can_switch(const conflux_t *cfx)
Definition: conflux.c:357
circuit_t * conflux_decide_circ_for_send(conflux_t *cfx, circuit_t *orig_circ, uint8_t relay_command)
Definition: conflux.c:455
static const circuit_t * conflux_decide_circ_cwndrtt(const conflux_t *cfx)
Definition: conflux.c:398
conflux_msg_t * conflux_dequeue_relay_msg(conflux_t *cfx)
Definition: conflux.c:897
conflux_leg_t * conflux_get_leg(conflux_t *cfx, const circuit_t *circ)
Definition: conflux.c:116
bool conflux_process_relay_msg(conflux_t *cfx, circuit_t *in_circ, crypt_path_t *layer_hint, const relay_msg_t *msg)
Definition: conflux.c:833
static const circuit_t * conflux_decide_circ_minrtt(const conflux_t *cfx)
Definition: conflux.c:241
int conflux_process_switch_command(circuit_t *in_circ, crypt_path_t *layer_hint, const relay_msg_t *msg)
Definition: conflux.c:735
size_t conflux_handle_oom(size_t bytes_to_remove)
Definition: conflux.c:189
static bool circuit_ready_to_send(const circuit_t *circ)
Definition: conflux.c:207
uint64_t conflux_get_total_bytes_allocation(void)
Definition: conflux.c:182
Public APIs for conflux multipath support.
#define CONFLUX_FOR_EACH_LEG_BEGIN(cfx, var)
Definition: conflux.h:20
#define CONFLUX_NUM_LEGS(cfx)
Definition: conflux.h:26
uint32_t conflux_cell_parse_switch(const relay_msg_t *msg)
Definition: conflux_cell.c:287
bool conflux_send_switch_command(circuit_t *send_circ, uint64_t relative_seq)
Definition: conflux_cell.c:311
Header file for conflux_cell.c.
Header file for conflux_params.c.
uint8_t conflux_params_get_drain_pct(void)
void conflux_log_set(int loglevel, const conflux_t *cfx, bool is_client)
Header file for conflux_pool.c.
Structure definitions for conflux multipath.
void conflux_validate_stream_lists(const conflux_t *cfx)
Definition: conflux_util.c:373
void conflux_validate_legs(const conflux_t *cfx)
Definition: conflux_util.c:405
bool conflux_validate_source_hop(circuit_t *in_circ, crypt_path_t *layer_hint)
Definition: conflux_util.c:145
Header file for conflux_util.c.
Public APIs for congestion control.
Structure definitions for congestion control.
#define log_fn(severity, domain, args,...)
Definition: log.h:283
#define LD_BUG
Definition: log.h:86
#define LD_CIRC
Definition: log.h:82
#define LOG_WARN
Definition: log.h:53
#define tor_free(p)
Definition: malloc.h:56
Master header file for Tor-specific functionality.
Origin circuit structure.
Header file for relay.c.
relay_msg_t * relay_msg_copy(const relay_msg_t *msg)
Definition: relay_msg.c:68
Header file for relay_msg.c.
Header file for sendme.c.
void * smartlist_pqueue_pop(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset)
Definition: smartlist.c:755
void smartlist_pqueue_add(smartlist_t *sl, int(*compare)(const void *a, const void *b), ptrdiff_t idx_field_offset, void *item)
Definition: smartlist.c:726
unsigned int circuit_blocked_on_n_chan
Definition: circuit_st.h:92
unsigned int circuit_blocked_on_p_chan
Definition: circuit_st.h:95
struct conflux_t * conflux
Definition: circuit_st.h:263
struct congestion_control_t * ccontrol
Definition: circuit_st.h:250
uint64_t last_seq_sent
Definition: conflux_st.h:66
uint64_t last_seq_recv
Definition: conflux_st.h:47
uint64_t circ_rtts_usec
Definition: conflux_st.h:75
uint64_t linked_sent_usec
Definition: conflux_st.h:79
circuit_t * circ
Definition: conflux_st.h:82
uint64_t seq
Definition: conflux.h:33
relay_msg_t * msg
Definition: conflux.h:42
smartlist_t * ooo_q
Definition: conflux_st.h:103
struct conflux_leg_t * curr_leg
Definition: conflux_st.h:117
struct conflux_params_t params
Definition: conflux_st.h:88
struct conflux_leg_t * prev_leg
Definition: conflux_st.h:121
uint64_t cells_until_switch
Definition: conflux_st.h:113
uint64_t last_seq_delivered
Definition: conflux_st.h:108
smartlist_t * legs
Definition: conflux_st.h:93
bool in_full_teardown
Definition: conflux_st.h:129
struct crypt_path_t * prev
Definition: crypt_path_st.h:79
struct congestion_control_t * ccontrol
Definition: crypt_path_st.h:88
crypt_path_t * cpath
#define tor_assert(expr)
Definition: util_bug.h:103