Conflux multipath core algorithms. More...

#include "core/or/relay_msg.h"
#include "core/or/or.h"
#include "core/or/circuit_st.h"
#include "core/or/sendme.h"
#include "core/or/relay.h"
#include "core/or/congestion_control_common.h"
#include "core/or/congestion_control_st.h"
#include "core/or/origin_circuit_st.h"
#include "core/or/circuitlist.h"
#include "core/or/circuituse.h"
#include "core/or/conflux.h"
#include "core/or/conflux_params.h"
#include "core/or/conflux_util.h"
#include "core/or/conflux_pool.h"
#include "core/or/conflux_st.h"
#include "core/or/conflux_cell.h"
#include "lib/time/compat_time.h"
#include "app/config/config.h"

Macros
#define	TOR_CONFLUX_PRIVATE

#define	USEC_PER_SEC 1000000

#define	CONFLUX_MIN_LINK_INCREMENT 31

Functions
static uint64_t	cwnd_sendable (const circuit_t *on_circ, uint64_t in_usec, uint64_t our_usec)

size_t	conflux_msg_alloc_cost (conflux_msg_t *msg)

bool	conflux_should_multiplex (int relay_command)

conflux_leg_t *	conflux_get_leg (conflux_t cfx, const circuit_t circ)

uint64_t	conflux_get_max_seq_sent (const conflux_t *cfx)

uint64_t	conflux_get_max_seq_recv (const conflux_t *cfx)

uint64_t	conflux_get_circ_bytes_allocation (const circuit_t *circ)

uint64_t	conflux_get_total_bytes_allocation (void)

size_t	conflux_handle_oom (size_t bytes_to_remove)

void	conflux_clear_ooo_q (conflux_t *cfx)

static bool	circuit_ready_to_send (const circuit_t *circ)

static const circuit_t *	conflux_decide_circ_minrtt (const conflux_t *cfx)

static const circuit_t *	conflux_decide_circ_lowrtt (const conflux_t *cfx)

static uint64_t	cwnd_available (const circuit_t *on_circ)

static bool	conflux_can_switch (const conflux_t *cfx)

static const circuit_t *	conflux_decide_circ_cwndrtt (const conflux_t *cfx)

circuit_t *	conflux_decide_circ_for_send (conflux_t cfx, circuit_t orig_circ, uint8_t relay_command)

void	conflux_note_cell_sent (conflux_t cfx, circuit_t circ, uint8_t relay_command)

static bool	conflux_pick_first_leg (conflux_t *cfx)

circuit_t *	conflux_decide_next_circ (conflux_t *cfx)

void	conflux_update_rtt (conflux_t cfx, circuit_t circ, uint64_t rtt_usec)

static int	conflux_queue_cmp (const void a, const void b)

const congestion_control_t *	circuit_ccontrol (const circuit_t *circ)

int	conflux_process_switch_command (circuit_t in_circ, crypt_path_t layer_hint, const relay_msg_t *msg)

bool	conflux_process_relay_msg (conflux_t cfx, circuit_t in_circ, crypt_path_t layer_hint, const relay_msg_t msg)

conflux_msg_t *	conflux_dequeue_relay_msg (circuit_t *circ)

void	conflux_relay_msg_free_ (conflux_msg_t *msg)

Variables
static uint64_t	total_ooo_q_bytes = 0

Detailed Description

Conflux multipath core algorithms.

Definition in file conflux.c.

Macro Definition Documentation

◆ CONFLUX_MIN_LINK_INCREMENT

#define CONFLUX_MIN_LINK_INCREMENT 31

Definition at line 782 of file conflux.c.

◆ TOR_CONFLUX_PRIVATE

#define TOR_CONFLUX_PRIVATE

Definition at line 10 of file conflux.c.

◆ USEC_PER_SEC

#define USEC_PER_SEC 1000000

One million microseconds in a second

Definition at line 32 of file conflux.c.

Referenced by tor_gettimeofday().

Function Documentation

◆ circuit_ccontrol()

const congestion_control_t * circuit_ccontrol ( const circuit_t * circ )

Get the congestion control object for a conflux circuit.

Because conflux can only be negotiated with the last hop, we can use the last hop of the cpath to obtain the congestion control object for origin circuits. For non-origin circuits, we can use the circuit itself.

Definition at line 760 of file conflux.c.

Referenced by cfx_del_leg(), circuit_ready_to_send(), conflux_can_switch(), conflux_log_set(), cwnd_available(), cwnd_sendable(), and edge_get_max_rtt().

◆ circuit_ready_to_send()

static bool circuit_ready_to_send ( const circuit_t * circ )

inlinestatic

Returns true if a circuit has package window space to send, and is not blocked locally.

Definition at line 241 of file conflux.c.

Referenced by conflux_decide_circ_cwndrtt(), conflux_decide_circ_lowrtt(), conflux_decide_circ_minrtt(), and conflux_decide_next_circ().

◆ conflux_can_switch()

static bool conflux_can_switch ( const conflux_t * cfx )

inlinestatic

Returns true if we can switch to a new circuit, false otherwise.

This function assumes we're primarily switching between two circuits, the current and the prev. If we're using more than two circuits, we need to set cfx_drain_pct to 100.

Definition at line 391 of file conflux.c.

Referenced by conflux_decide_next_circ().

◆ conflux_clear_ooo_q()

void conflux_clear_ooo_q ( conflux_t * cfx )

Free all cells in the ooo_q of the given cfx which updates the total_ooo_q_bytes.

Must be called before freeing the queue itself.

Definition at line 219 of file conflux.c.

◆ conflux_decide_circ_cwndrtt()

static const circuit_t * conflux_decide_circ_cwndrtt ( const conflux_t * cfx )

static

Favor the circuit with the lowest RTT that still has space in the congestion window up to the ratio of RTTs.

This algorithm should only use auxillary legs up to the point where their data arrives roughly the same time as the lowest RTT leg. It will not utilize the full cwnd of auxillary legs, except in slow start. Therefore, out-of-order queue bloat should be minimized to just the slow-start phase.

Definition at line 432 of file conflux.c.

Referenced by conflux_decide_next_circ().

◆ conflux_decide_circ_for_send()

circuit_t * conflux_decide_circ_for_send	(	conflux_t *	cfx,
		circuit_t *	orig_circ,
		uint8_t	relay_command )

This function is called when we want to send a relay cell on a conflux, as well as when we want to compute available space in to package from streams.

It determines the circuit that relay command should be sent on, and sends a SWITCH cell if necessary.

It returns the circuit we should send on. If no circuits are ready to send, it returns NULL.

Definition at line 489 of file conflux.c.

Referenced by relay_send_command_from_edge_().

◆ conflux_decide_circ_lowrtt()

static const circuit_t * conflux_decide_circ_lowrtt ( const conflux_t * cfx )

static

Favor the circuit with the lowest RTT that still has space in the congestion window.

This algorithm will maximize total throughput at the expense of bloating out-of-order queues.

Definition at line 307 of file conflux.c.

Referenced by conflux_decide_next_circ().

◆ conflux_decide_circ_minrtt()

static const circuit_t * conflux_decide_circ_minrtt ( const conflux_t * cfx )

static

Return the circuit with the minimum RTT. Do not use any other circuit.

This algorithm will minimize RTT always, and will not provide any throughput benefit. We expect it to be useful for VoIP/UDP use cases. Because it only uses one circuit on a leg at a time, it can have more than one circuit per guard (ie: to find lower-latency middles for the path).

Definition at line 275 of file conflux.c.

Referenced by conflux_decide_next_circ().

◆ conflux_decide_next_circ()

circuit_t * conflux_decide_next_circ ( conflux_t * cfx )

Returns the circuit that conflux would send on next, if conflux_decide_circ_for_send were called. This is used to compute available space in the package window.

Definition at line 659 of file conflux.c.

Referenced by circuit_get_package_window(), circuit_resume_edge_reading_helper(), conflux_can_send(), and conflux_decide_circ_for_send().

◆ conflux_dequeue_relay_msg()

conflux_msg_t * conflux_dequeue_relay_msg ( circuit_t * circ )

Dequeue the top cell from our queue.

Returns the cell as a conflux_cell_t, or NULL if the queue is empty or has a hole.

Definition at line 967 of file conflux.c.

Referenced by connection_edge_process_relay_cell().

◆ conflux_get_circ_bytes_allocation()

uint64_t conflux_get_circ_bytes_allocation ( const circuit_t * circ )

Return the total memory allocation the circuit is using by conflux. If this circuit is not a Conflux circuit, 0 is returned.

Definition at line 181 of file conflux.c.

Referenced by circuits_handle_oom().

◆ conflux_get_leg()

conflux_leg_t * conflux_get_leg	(	conflux_t *	cfx,
		const circuit_t *	circ )

Return the leg for a circuit in a conflux set. Return NULL if not found.

Definition at line 127 of file conflux.c.

Referenced by cfx_del_leg(), conflux_decide_circ_for_send(), conflux_get_circ_rtt(), conflux_note_cell_sent(), conflux_process_relay_msg(), conflux_process_switch_command(), conflux_update_rtt(), and record_rtt_exit().

◆ conflux_get_max_seq_recv()

uint64_t conflux_get_max_seq_recv ( const conflux_t * cfx )

Gets the maximum last_seq_recv from all legs.

Definition at line 165 of file conflux.c.

Referenced by cfx_del_leg().

◆ conflux_get_max_seq_sent()

uint64_t conflux_get_max_seq_sent ( const conflux_t * cfx )

Gets the maximum last_seq_sent from all legs.

Definition at line 148 of file conflux.c.

Referenced by cfx_del_leg(), conflux_launch_leg(), and conflux_process_link().

◆ conflux_get_total_bytes_allocation()

uint64_t conflux_get_total_bytes_allocation ( void )

Return the total memory allocation in bytes by the subsystem.

At the moment, only out of order queues are consiered.

Definition at line 194 of file conflux.c.

Referenced by cell_queues_check_size().

◆ conflux_handle_oom()

size_t conflux_handle_oom ( size_t bytes_to_remove )

The OOM handler is asking us to try to free at least bytes_to_remove.

Definition at line 201 of file conflux.c.

Referenced by cell_queues_check_size().

◆ conflux_msg_alloc_cost()

size_t conflux_msg_alloc_cost ( conflux_msg_t * msg )

Return the total number of required allocated to store msg.

Definition at line 47 of file conflux.c.

Referenced by conflux_dequeue_relay_msg(), and conflux_process_relay_msg().

◆ conflux_note_cell_sent()

void conflux_note_cell_sent	(	conflux_t *	cfx,
		circuit_t *	circ,
		uint8_t	relay_command )

Called after conflux actually sent a cell on a circuit. This function updates sequence number counters, and switch counters.

Definition at line 578 of file conflux.c.

Referenced by relay_send_command_from_edge_().

◆ conflux_pick_first_leg()

static bool conflux_pick_first_leg ( conflux_t * cfx )

inlinestatic

Find the leg with lowest non-zero curr_rtt_usec, and pick it for our current leg.

Definition at line 602 of file conflux.c.

Referenced by conflux_decide_next_circ().

◆ conflux_process_relay_msg()

bool conflux_process_relay_msg	(	conflux_t *	cfx,
		circuit_t *	in_circ,
		crypt_path_t *	layer_hint,
		const relay_msg_t *	msg )

Process an incoming relay cell for conflux. Called from connection_edge_process_relay_cell().

Returns true if the conflux system now has well-ordered cells to deliver to streams, false otherwise.

Definition at line 885 of file conflux.c.

Referenced by connection_edge_process_relay_cell().

◆ conflux_process_switch_command()

int conflux_process_switch_command	(	circuit_t *	in_circ,
		crypt_path_t *	layer_hint,
		const relay_msg_t *	msg )

Validate and handle RELAY_COMMAND_CONFLUX_SWITCH.

Definition at line 787 of file conflux.c.

Referenced by handle_relay_msg().

◆ conflux_queue_cmp()

static int conflux_queue_cmp	(	const void *	a,
		const void *	b )

static

Comparison function for ooo_q pqueue.

Ensures that lower sequence numbers are at the head of the pqueue.

Definition at line 732 of file conflux.c.

Referenced by conflux_dequeue_relay_msg(), and conflux_process_relay_msg().

◆ conflux_relay_msg_free_()

void conflux_relay_msg_free_ ( conflux_msg_t * msg )

Free a given conflux msg object.

Definition at line 1022 of file conflux.c.

◆ conflux_should_multiplex()

bool conflux_should_multiplex ( int relay_command )

Determine if we should multiplex a specific relay command or not.

TODO: Version of this that is the set of forbidden commands on linked circuits

Definition at line 59 of file conflux.c.

Referenced by conflux_decide_circ_for_send(), conflux_note_cell_sent(), connection_edge_process_relay_cell(), and relay_send_command_from_edge_().

◆ conflux_update_rtt()

void conflux_update_rtt	(	conflux_t *	cfx,
		circuit_t *	circ,
		uint64_t	rtt_usec )

Called when we have a new RTT estimate for a circuit.

Definition at line 708 of file conflux.c.

Referenced by congestion_control_dispatch_cc_alg().

◆ cwnd_available()

static uint64_t cwnd_available ( const circuit_t * on_circ )

inlinestatic

Returns the amount of room in a cwnd on a circuit.

Definition at line 337 of file conflux.c.

Referenced by cwnd_sendable().

◆ cwnd_sendable()

static uint64_t cwnd_sendable	(	const circuit_t *	on_circ,
		uint64_t	in_usec,
		uint64_t	our_usec )

inlinestatic

Return the amount of congestion window we can send on on_circ during in_usec. However, if we're still in slow-start, send the whole window to establish the true cwnd.

Definition at line 355 of file conflux.c.

Referenced by conflux_decide_circ_cwndrtt().

Variable Documentation

◆ total_ooo_q_bytes

uint64_t total_ooo_q_bytes = 0

static

Definition at line 41 of file conflux.c.

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ CONFLUX_MIN_LINK_INCREMENT

◆ TOR_CONFLUX_PRIVATE

◆ USEC_PER_SEC

Function Documentation

◆ circuit_ccontrol()

◆ circuit_ready_to_send()

◆ conflux_can_switch()

◆ conflux_clear_ooo_q()

◆ conflux_decide_circ_cwndrtt()

◆ conflux_decide_circ_for_send()

◆ conflux_decide_circ_lowrtt()

◆ conflux_decide_circ_minrtt()

◆ conflux_decide_next_circ()

◆ conflux_dequeue_relay_msg()

◆ conflux_get_circ_bytes_allocation()

◆ conflux_get_leg()

◆ conflux_get_max_seq_recv()

◆ conflux_get_max_seq_sent()

◆ conflux_get_total_bytes_allocation()

◆ conflux_handle_oom()

◆ conflux_msg_alloc_cost()

◆ conflux_note_cell_sent()

◆ conflux_pick_first_leg()

◆ conflux_process_relay_msg()

◆ conflux_process_switch_command()

◆ conflux_queue_cmp()

◆ conflux_relay_msg_free_()

◆ conflux_should_multiplex()

◆ conflux_update_rtt()

◆ cwnd_available()

◆ cwnd_sendable()

Variable Documentation

◆ total_ooo_q_bytes