Frédéric Lécaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 1 | #include <import/eb64tree.h> |
| 2 | |
Amaury Denoyelle | 92fa63f | 2022-09-30 18:11:13 +0200 | [diff] [blame] | 3 | #include <haproxy/quic_conn-t.h> |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 4 | #include <haproxy/quic_loss.h> |
Frédéric Lécaille | e1a49cf | 2022-09-16 16:24:47 +0200 | [diff] [blame] | 5 | #include <haproxy/quic_tls.h> |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 6 | |
Frédéric Lécaille | eb79145 | 2022-05-24 16:01:39 +0200 | [diff] [blame] | 7 | #include <haproxy/atomic.h> |
Amaury Denoyelle | 5c25dc5 | 2022-09-30 17:44:15 +0200 | [diff] [blame] | 8 | #include <haproxy/list.h> |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 9 | #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 | */ |
| 18 | void 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écaille | a8b2f84 | 2022-08-10 17:56:45 +0200 | [diff] [blame] | 22 | TRACE_ENTER(QUIC_EV_CONN_RTTUPDT, qc); |
Frédéric Lécaille | 8f99194 | 2023-03-24 15:14:45 +0100 | [diff] [blame] | 23 | TRACE_PROTO("TX loss srtt update", QUIC_EV_CONN_RTTUPDT, qc, &rtt, &ack_delay, ql); |
Frédéric Lécaille | a8b2f84 | 2022-08-10 17:56:45 +0200 | [diff] [blame] | 24 | |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 25 | ql->latest_rtt = rtt; |
| 26 | if (!ql->rtt_min) { |
| 27 | /* No previous measurement. */ |
Frédéric Lécaille | 35fb593 | 2023-09-05 15:24:11 +0200 | [diff] [blame] | 28 | ql->srtt = rtt; |
| 29 | ql->rtt_var = rtt / 2; |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 30 | 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écaille | 14c90e9 | 2023-09-05 13:59:09 +0200 | [diff] [blame] | 37 | if (ack_delay && rtt >= ql->rtt_min + ack_delay) |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 38 | rtt -= ack_delay; |
Frédéric Lécaille | 35fb593 | 2023-09-05 15:24:11 +0200 | [diff] [blame] | 39 | diff = ql->srtt - rtt; |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 40 | if (diff < 0) |
| 41 | diff = -diff; |
Frédéric Lécaille | 35fb593 | 2023-09-05 15:24:11 +0200 | [diff] [blame] | 42 | ql->rtt_var = (3 * ql->rtt_var + diff) / 4; |
| 43 | ql->srtt = (7 * ql->srtt + rtt) / 8; |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 44 | } |
Frédéric Lécaille | a8b2f84 | 2022-08-10 17:56:45 +0200 | [diff] [blame] | 45 | |
Frédéric Lécaille | 8f99194 | 2023-03-24 15:14:45 +0100 | [diff] [blame] | 46 | TRACE_PROTO("TX loss srtt update", QUIC_EV_CONN_RTTUPDT, qc,,, ql); |
Frédéric Lécaille | a8b2f84 | 2022-08-10 17:56:45 +0200 | [diff] [blame] | 47 | TRACE_LEAVE(QUIC_EV_CONN_RTTUPDT, qc); |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 48 | } |
| 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 | */ |
| 54 | struct 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écaille | a8b2f84 | 2022-08-10 17:56:45 +0200 | [diff] [blame] | 59 | TRACE_ENTER(QUIC_EV_CONN_SPTO, qc); |
| 60 | |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 61 | pktns = &qc->pktns[QUIC_TLS_PKTNS_INITIAL]; |
Frédéric Lécaille | 8f99194 | 2023-03-24 15:14:45 +0100 | [diff] [blame] | 62 | TRACE_PROTO("TX loss pktns", QUIC_EV_CONN_SPTO, qc, pktns); |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 63 | for (i = QUIC_TLS_PKTNS_HANDSHAKE; i < QUIC_TLS_PKTNS_MAX; i++) { |
Frédéric Lécaille | 8f99194 | 2023-03-24 15:14:45 +0100 | [diff] [blame] | 64 | TRACE_PROTO("TX loss pktns", QUIC_EV_CONN_SPTO, qc, &qc->pktns[i]); |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 65 | if (!tick_isset(pktns->tx.loss_time) || |
Frédéric Lécaille | 01505ae | 2023-06-19 10:47:24 +0200 | [diff] [blame] | 66 | tick_is_lt(qc->pktns[i].tx.loss_time, pktns->tx.loss_time)) |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 67 | pktns = &qc->pktns[i]; |
| 68 | } |
| 69 | |
Frédéric Lécaille | a8b2f84 | 2022-08-10 17:56:45 +0200 | [diff] [blame] | 70 | TRACE_LEAVE(QUIC_EV_CONN_SPTO, qc); |
| 71 | |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 72 | 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 | */ |
| 79 | struct quic_pktns *quic_pto_pktns(struct quic_conn *qc, |
Frédéric Lécaille | b75eecc | 2023-01-26 15:18:17 +0100 | [diff] [blame] | 80 | int handshake_confirmed, |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 81 | 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écaille | 35fb593 | 2023-09-05 15:24:11 +0200 | [diff] [blame] | 90 | ql->srtt + |
| 91 | (QUIC_MAX(4 * ql->rtt_var, QUIC_TIMER_GRANULARITY) << ql->pto_count); |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 92 | |
Amaury Denoyelle | 5f87041 | 2023-04-11 14:43:42 +0200 | [diff] [blame] | 93 | /* 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 Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 105 | |
| 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écaille | b75eecc | 2023-01-26 15:18:17 +0100 | [diff] [blame] | 116 | if (!handshake_confirmed) { |
Frédéric Lécaille | 2513b1d | 2023-04-07 15:39:17 +0200 | [diff] [blame] | 117 | TRACE_STATE("TX PTO handshake not already confirmed", QUIC_EV_CONN_SPTO, qc); |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 118 | 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écaille | 0222cc6 | 2023-04-04 15:47:16 +0200 | [diff] [blame] | 127 | if (!tick_isset(lpto) || tick_is_lt(tmp_pto, lpto)) { |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 128 | lpto = tmp_pto; |
| 129 | pktns = p; |
| 130 | } |
Frédéric Lécaille | 8f99194 | 2023-03-24 15:14:45 +0100 | [diff] [blame] | 131 | TRACE_PROTO("TX PTO", QUIC_EV_CONN_SPTO, qc, p); |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 132 | } |
| 133 | |
| 134 | out: |
| 135 | if (pto) |
| 136 | *pto = lpto; |
Frédéric Lécaille | 8f99194 | 2023-03-24 15:14:45 +0100 | [diff] [blame] | 137 | TRACE_PROTO("TX PTO", QUIC_EV_CONN_SPTO, qc, pktns, &duration); |
| 138 | TRACE_LEAVE(QUIC_EV_CONN_SPTO, qc); |
Amaury Denoyelle | 0c2d964 | 2022-03-24 16:08:05 +0100 | [diff] [blame] | 139 | |
| 140 | return pktns; |
| 141 | } |
Frédéric Lécaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 142 | |
| 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 | */ |
| 151 | void 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 Lecaille | f1724f4 | 2024-02-13 19:38:46 +0100 | [diff] [blame] | 158 | uint64_t pktthresh; |
Frédéric Lécaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 159 | |
Frédéric Lécaille | 8f99194 | 2023-03-24 15:14:45 +0100 | [diff] [blame] | 160 | TRACE_ENTER(QUIC_EV_CONN_PKTLOSS, qc); |
| 161 | TRACE_PROTO("TX loss", QUIC_EV_CONN_PKTLOSS, qc, pktns); |
Frédéric Lécaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 162 | 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écaille | 35fb593 | 2023-09-05 15:24:11 +0200 | [diff] [blame] | 168 | loss_delay = QUIC_MAX(ql->latest_rtt, ql->srtt); |
Frédéric Lécaille | c40e19d | 2022-04-29 16:00:17 +0200 | [diff] [blame] | 169 | 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écaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 171 | |
| 172 | node = eb64_first(pkts); |
Frederic Lecaille | f1724f4 | 2024-02-13 19:38:46 +0100 | [diff] [blame] | 173 | |
| 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écaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 194 | while (node) { |
| 195 | struct quic_tx_packet *pkt; |
| 196 | int64_t largest_acked_pn; |
| 197 | unsigned int loss_time_limit, time_sent; |
Frederic Lecaille | dfeda3a | 2024-02-13 21:24:40 +0100 | [diff] [blame] | 198 | int reordered; |
Frédéric Lécaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 199 | |
| 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 Lecaille | dfeda3a | 2024-02-13 21:24:40 +0100 | [diff] [blame] | 208 | |
| 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écaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 214 | eb64_delete(&pkt->pn_node); |
| 215 | LIST_APPEND(lost_pkts, &pkt->list); |
Frédéric Lécaille | fad0e6c | 2023-04-06 10:19:17 +0200 | [diff] [blame] | 216 | ql->nb_lost_pkt++; |
Frédéric Lécaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 217 | } |
| 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écaille | dc591cd | 2022-07-21 14:24:41 +0200 | [diff] [blame] | 223 | break; |
Frédéric Lécaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 224 | } |
| 225 | } |
| 226 | |
| 227 | out: |
Frédéric Lécaille | 8f99194 | 2023-03-24 15:14:45 +0100 | [diff] [blame] | 228 | TRACE_PROTO("TX loss", QUIC_EV_CONN_PKTLOSS, qc, pktns, lost_pkts); |
| 229 | TRACE_LEAVE(QUIC_EV_CONN_PKTLOSS, qc); |
Frédéric Lécaille | 1601395 | 2022-04-29 15:07:48 +0200 | [diff] [blame] | 230 | } |
| 231 | |