blob: 0169d328ac1357a6281e903c1995eb22b4dd465a [file] [log] [blame]
Frédéric Lécaille16013952022-04-29 15:07:48 +02001#include <import/eb64tree.h>
2
Amaury Denoyelle92fa63f2022-09-30 18:11:13 +02003#include <haproxy/quic_conn-t.h>
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +01004#include <haproxy/quic_loss.h>
Frédéric Lécaillee1a49cf2022-09-16 16:24:47 +02005#include <haproxy/quic_tls.h>
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +01006
Frédéric Lécailleeb791452022-05-24 16:01:39 +02007#include <haproxy/atomic.h>
Amaury Denoyelle5c25dc52022-09-30 17:44:15 +02008#include <haproxy/list.h>
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +01009#include <haproxy/ticks.h>
10#include <haproxy/trace.h>
11
12#define TRACE_SOURCE &trace_quic
13
14/* Update <ql> QUIC loss information with new <rtt> measurement and <ack_delay>
15 * on ACK frame receipt which MUST be min(ack->ack_delay, max_ack_delay)
16 * before the handshake is confirmed.
17 */
18void quic_loss_srtt_update(struct quic_loss *ql,
19 unsigned int rtt, unsigned int ack_delay,
20 struct quic_conn *qc)
21{
Frédéric Lécaillea8b2f842022-08-10 17:56:45 +020022 TRACE_ENTER(QUIC_EV_CONN_RTTUPDT, qc);
Frédéric Lécaille8f991942023-03-24 15:14:45 +010023 TRACE_PROTO("TX loss srtt update", QUIC_EV_CONN_RTTUPDT, qc, &rtt, &ack_delay, ql);
Frédéric Lécaillea8b2f842022-08-10 17:56:45 +020024
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010025 ql->latest_rtt = rtt;
26 if (!ql->rtt_min) {
27 /* No previous measurement. */
Frédéric Lécaille35fb5932023-09-05 15:24:11 +020028 ql->srtt = rtt;
29 ql->rtt_var = rtt / 2;
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010030 ql->rtt_min = rtt;
31 }
32 else {
33 int diff;
34
35 ql->rtt_min = QUIC_MIN(rtt, ql->rtt_min);
36 /* Specific to QUIC (RTT adjustment). */
Frédéric Lécaille14c90e92023-09-05 13:59:09 +020037 if (ack_delay && rtt >= ql->rtt_min + ack_delay)
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010038 rtt -= ack_delay;
Frédéric Lécaille35fb5932023-09-05 15:24:11 +020039 diff = ql->srtt - rtt;
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010040 if (diff < 0)
41 diff = -diff;
Frédéric Lécaille35fb5932023-09-05 15:24:11 +020042 ql->rtt_var = (3 * ql->rtt_var + diff) / 4;
43 ql->srtt = (7 * ql->srtt + rtt) / 8;
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010044 }
Frédéric Lécaillea8b2f842022-08-10 17:56:45 +020045
Frédéric Lécaille8f991942023-03-24 15:14:45 +010046 TRACE_PROTO("TX loss srtt update", QUIC_EV_CONN_RTTUPDT, qc,,, ql);
Frédéric Lécaillea8b2f842022-08-10 17:56:45 +020047 TRACE_LEAVE(QUIC_EV_CONN_RTTUPDT, qc);
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010048}
49
50/* Returns for <qc> QUIC connection the first packet number space which
51 * experienced packet loss, if any or a packet number space with
52 * TICK_ETERNITY as packet loss time if not.
53 */
54struct quic_pktns *quic_loss_pktns(struct quic_conn *qc)
55{
56 enum quic_tls_pktns i;
57 struct quic_pktns *pktns;
58
Frédéric Lécaillea8b2f842022-08-10 17:56:45 +020059 TRACE_ENTER(QUIC_EV_CONN_SPTO, qc);
60
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010061 pktns = &qc->pktns[QUIC_TLS_PKTNS_INITIAL];
Frédéric Lécaille8f991942023-03-24 15:14:45 +010062 TRACE_PROTO("TX loss pktns", QUIC_EV_CONN_SPTO, qc, pktns);
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010063 for (i = QUIC_TLS_PKTNS_HANDSHAKE; i < QUIC_TLS_PKTNS_MAX; i++) {
Frédéric Lécaille8f991942023-03-24 15:14:45 +010064 TRACE_PROTO("TX loss pktns", QUIC_EV_CONN_SPTO, qc, &qc->pktns[i]);
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010065 if (!tick_isset(pktns->tx.loss_time) ||
Frédéric Lécaille01505ae2023-06-19 10:47:24 +020066 tick_is_lt(qc->pktns[i].tx.loss_time, pktns->tx.loss_time))
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010067 pktns = &qc->pktns[i];
68 }
69
Frédéric Lécaillea8b2f842022-08-10 17:56:45 +020070 TRACE_LEAVE(QUIC_EV_CONN_SPTO, qc);
71
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010072 return pktns;
73}
74
75/* Returns for <qc> QUIC connection the first packet number space to
76 * arm the PTO for if any or a packet number space with TICK_ETERNITY
77 * as PTO value if not.
78 */
79struct quic_pktns *quic_pto_pktns(struct quic_conn *qc,
Frédéric Lécailleb75eecc2023-01-26 15:18:17 +010080 int handshake_confirmed,
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010081 unsigned int *pto)
82{
83 int i;
84 unsigned int duration, lpto;
85 struct quic_loss *ql = &qc->path->loss;
86 struct quic_pktns *pktns, *p;
87
88 TRACE_ENTER(QUIC_EV_CONN_SPTO, qc);
89 duration =
Frédéric Lécaille35fb5932023-09-05 15:24:11 +020090 ql->srtt +
91 (QUIC_MAX(4 * ql->rtt_var, QUIC_TIMER_GRANULARITY) << ql->pto_count);
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +010092
Amaury Denoyelle5f870412023-04-11 14:43:42 +020093 /* RFC 9002 6.2.2.1. Before Address Validation
94 *
95 * the client MUST set the PTO timer if the client has not received an
96 * acknowledgment for any of its Handshake packets and the handshake is
97 * not confirmed (see Section 4.1.2 of [QUIC-TLS]), even if there are no
98 * packets in flight.
99 *
100 * TODO implement the above paragraph for QUIC on backend side. Note
101 * that if now_ms is used this function is not reentrant anymore and can
102 * not be used anytime without side-effect (for example after QUIC
103 * connection migration).
104 */
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +0100105
106 lpto = TICK_ETERNITY;
107 pktns = p = &qc->pktns[QUIC_TLS_PKTNS_INITIAL];
108
109 for (i = QUIC_TLS_PKTNS_INITIAL; i < QUIC_TLS_PKTNS_MAX; i++) {
110 unsigned int tmp_pto;
111
112 if (!qc->pktns[i].tx.in_flight)
113 continue;
114
115 if (i == QUIC_TLS_PKTNS_01RTT) {
Frédéric Lécailleb75eecc2023-01-26 15:18:17 +0100116 if (!handshake_confirmed) {
Frédéric Lécaille2513b1d2023-04-07 15:39:17 +0200117 TRACE_STATE("TX PTO handshake not already confirmed", QUIC_EV_CONN_SPTO, qc);
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +0100118 pktns = p;
119 goto out;
120 }
121
122 duration += qc->max_ack_delay << ql->pto_count;
123 }
124
125 p = &qc->pktns[i];
126 tmp_pto = tick_add(p->tx.time_of_last_eliciting, duration);
Frédéric Lécaille0222cc62023-04-04 15:47:16 +0200127 if (!tick_isset(lpto) || tick_is_lt(tmp_pto, lpto)) {
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +0100128 lpto = tmp_pto;
129 pktns = p;
130 }
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100131 TRACE_PROTO("TX PTO", QUIC_EV_CONN_SPTO, qc, p);
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +0100132 }
133
134 out:
135 if (pto)
136 *pto = lpto;
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100137 TRACE_PROTO("TX PTO", QUIC_EV_CONN_SPTO, qc, pktns, &duration);
138 TRACE_LEAVE(QUIC_EV_CONN_SPTO, qc);
Amaury Denoyelle0c2d9642022-03-24 16:08:05 +0100139
140 return pktns;
141}
Frédéric Lécaille16013952022-04-29 15:07:48 +0200142
143/* Look for packet loss from sent packets for <qel> encryption level of a
144 * connection with <ctx> as I/O handler context. If remove is true, remove them from
145 * their tree if deemed as lost or set the <loss_time> value the packet number
146 * space if any not deemed lost.
147 * Should be called after having received an ACK frame with newly acknowledged
148 * packets or when the the loss detection timer has expired.
149 * Always succeeds.
150 */
151void qc_packet_loss_lookup(struct quic_pktns *pktns, struct quic_conn *qc,
152 struct list *lost_pkts)
153{
154 struct eb_root *pkts;
155 struct eb64_node *node;
156 struct quic_loss *ql;
157 unsigned int loss_delay;
Frederic Lecaillef1724f42024-02-13 19:38:46 +0100158 uint64_t pktthresh;
Frédéric Lécaille16013952022-04-29 15:07:48 +0200159
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100160 TRACE_ENTER(QUIC_EV_CONN_PKTLOSS, qc);
161 TRACE_PROTO("TX loss", QUIC_EV_CONN_PKTLOSS, qc, pktns);
Frédéric Lécaille16013952022-04-29 15:07:48 +0200162 pkts = &pktns->tx.pkts;
163 pktns->tx.loss_time = TICK_ETERNITY;
164 if (eb_is_empty(pkts))
165 goto out;
166
167 ql = &qc->path->loss;
Frédéric Lécaille35fb5932023-09-05 15:24:11 +0200168 loss_delay = QUIC_MAX(ql->latest_rtt, ql->srtt);
Frédéric Lécaillec40e19d2022-04-29 16:00:17 +0200169 loss_delay = QUIC_MAX(loss_delay, MS_TO_TICKS(QUIC_TIMER_GRANULARITY)) *
170 QUIC_LOSS_TIME_THRESHOLD_MULTIPLICAND / QUIC_LOSS_TIME_THRESHOLD_DIVISOR;
Frédéric Lécaille16013952022-04-29 15:07:48 +0200171
172 node = eb64_first(pkts);
Frederic Lecaillef1724f42024-02-13 19:38:46 +0100173
174 /* RFC 9002 6.1.1. Packet Threshold
175 * The RECOMMENDED initial value for the packet reordering threshold
176 * (kPacketThreshold) is 3, based on best practices for TCP loss detection
177 * [RFC5681] [RFC6675]. In order to remain similar to TCP, implementations
178 * SHOULD NOT use a packet threshold less than 3; see [RFC5681].
179
180 * Some networks may exhibit higher degrees of packet reordering, causing a
181 * sender to detect spurious losses. Additionally, packet reordering could be
182 * more common with QUIC than TCP because network elements that could observe
183 * and reorder TCP packets cannot do that for QUIC and also because QUIC
184 * packet numbers are encrypted.
185 */
186
187 /* Dynamic packet reordering threshold calculation depending on the distance
188 * (in packets) between the last transmitted packet and the oldest still in
189 * flight before loss detection.
190 */
191 pktthresh = pktns->tx.next_pn - 1 - eb64_entry(node, struct quic_tx_packet, pn_node)->pn_node.key;
192 /* Apply a ratio to this threshold and add it to QUIC_LOSS_PACKET_THRESHOLD. */
193 pktthresh = pktthresh * global.tune.quic_reorder_ratio / 100 + QUIC_LOSS_PACKET_THRESHOLD;
Frédéric Lécaille16013952022-04-29 15:07:48 +0200194 while (node) {
195 struct quic_tx_packet *pkt;
196 int64_t largest_acked_pn;
197 unsigned int loss_time_limit, time_sent;
Frederic Lecailledfeda3a2024-02-13 21:24:40 +0100198 int reordered;
Frédéric Lécaille16013952022-04-29 15:07:48 +0200199
200 pkt = eb64_entry(&node->node, struct quic_tx_packet, pn_node);
201 largest_acked_pn = pktns->rx.largest_acked_pn;
202 node = eb64_next(node);
203 if ((int64_t)pkt->pn_node.key > largest_acked_pn)
204 break;
205
206 time_sent = pkt->time_sent;
207 loss_time_limit = tick_add(time_sent, loss_delay);
Frederic Lecailledfeda3a2024-02-13 21:24:40 +0100208
209 reordered = (int64_t)largest_acked_pn >= pkt->pn_node.key + pktthresh;
210 if (reordered)
211 ql->nb_reordered_pkt++;
212
213 if (tick_is_le(loss_time_limit, now_ms) || reordered) {
Frédéric Lécaille16013952022-04-29 15:07:48 +0200214 eb64_delete(&pkt->pn_node);
215 LIST_APPEND(lost_pkts, &pkt->list);
Frédéric Lécaillefad0e6c2023-04-06 10:19:17 +0200216 ql->nb_lost_pkt++;
Frédéric Lécaille16013952022-04-29 15:07:48 +0200217 }
218 else {
219 if (tick_isset(pktns->tx.loss_time))
220 pktns->tx.loss_time = tick_first(pktns->tx.loss_time, loss_time_limit);
221 else
222 pktns->tx.loss_time = loss_time_limit;
Frédéric Lécailledc591cd2022-07-21 14:24:41 +0200223 break;
Frédéric Lécaille16013952022-04-29 15:07:48 +0200224 }
225 }
226
227 out:
Frédéric Lécaille8f991942023-03-24 15:14:45 +0100228 TRACE_PROTO("TX loss", QUIC_EV_CONN_PKTLOSS, qc, pktns, lost_pkts);
229 TRACE_LEAVE(QUIC_EV_CONN_PKTLOSS, qc);
Frédéric Lécaille16013952022-04-29 15:07:48 +0200230}
231