1// SPDX-License-Identifier: GPL-2.0-only 2#include <net/tcp.h> 3 4/* The bandwidth estimator estimates the rate at which the network 5 * can currently deliver outbound data packets for this flow. At a high 6 * level, it operates by taking a delivery rate sample for each ACK. 7 * 8 * A rate sample records the rate at which the network delivered packets 9 * for this flow, calculated over the time interval between the transmission 10 * of a data packet and the acknowledgment of that packet. 11 * 12 * Specifically, over the interval between each transmit and corresponding ACK, 13 * the estimator generates a delivery rate sample. Typically it uses the rate 14 * at which packets were acknowledged. However, the approach of using only the 15 * acknowledgment rate faces a challenge under the prevalent ACK decimation or 16 * compression: packets can temporarily appear to be delivered much quicker 17 * than the bottleneck rate. Since it is physically impossible to do that in a 18 * sustained fashion, when the estimator notices that the ACK rate is faster 19 * than the transmit rate, it uses the latter: 20 * 21 * send_rate = #pkts_delivered/(last_snd_time - first_snd_time) 22 * ack_rate = #pkts_delivered/(last_ack_time - first_ack_time) 23 * bw = min(send_rate, ack_rate) 24 * 25 * Notice the estimator essentially estimates the goodput, not always the 26 * network bottleneck link rate when the sending or receiving is limited by 27 * other factors like applications or receiver window limits. The estimator 28 * deliberately avoids using the inter-packet spacing approach because that 29 * approach requires a large number of samples and sophisticated filtering. 30 * 31 * TCP flows can often be application-limited in request/response workloads. 32 * The estimator marks a bandwidth sample as application-limited if there 33 * was some moment during the sampled window of packets when there was no data 34 * ready to send in the write queue. 35 */ 36 37/* Snapshot the current delivery information in the skb, to generate 38 * a rate sample later when the skb is (s)acked in tcp_rate_skb_delivered(). 39 */ 40void tcp_rate_skb_sent(struct sock *sk, struct sk_buff *skb) 41{ 42 struct tcp_sock *tp = tcp_sk(sk); 43 44 /* In general we need to start delivery rate samples from the 45 * time we received the most recent ACK, to ensure we include 46 * the full time the network needs to deliver all in-flight 47 * packets. If there are no packets in flight yet, then we 48 * know that any ACKs after now indicate that the network was 49 * able to deliver those packets completely in the sampling 50 * interval between now and the next ACK. 51 * 52 * Note that we use packets_out instead of tcp_packets_in_flight(tp) 53 * because the latter is a guess based on RTO and loss-marking 54 * heuristics. We don't want spurious RTOs or loss markings to cause 55 * a spuriously small time interval, causing a spuriously high 56 * bandwidth estimate. 57 */ 58 if (!tp->packets_out) { 59 u64 tstamp_us = tcp_skb_timestamp_us(skb); 60 61 tp->first_tx_mstamp = tstamp_us; 62 tp->delivered_mstamp = tstamp_us; 63 } 64 65 TCP_SKB_CB(skb)->tx.first_tx_mstamp = tp->first_tx_mstamp; 66 TCP_SKB_CB(skb)->tx.delivered_mstamp = tp->delivered_mstamp; 67 TCP_SKB_CB(skb)->tx.delivered = tp->delivered; 68 TCP_SKB_CB(skb)->tx.is_app_limited = tp->app_limited ? 1 : 0; 69} 70 71/* When an skb is sacked or acked, we fill in the rate sample with the (prior) 72 * delivery information when the skb was last transmitted. 73 * 74 * If an ACK (s)acks multiple skbs (e.g., stretched-acks), this function is 75 * called multiple times. We favor the information from the most recently 76 * sent skb, i.e., the skb with the most recently sent time and the highest 77 * sequence. 78 */ 79void tcp_rate_skb_delivered(struct sock *sk, struct sk_buff *skb, 80 struct rate_sample *rs) 81{ 82 struct tcp_sock *tp = tcp_sk(sk); 83 struct tcp_skb_cb *scb = TCP_SKB_CB(skb); 84 u64 tx_tstamp; 85 86 if (!scb->tx.delivered_mstamp) 87 return; 88 89 tx_tstamp = tcp_skb_timestamp_us(skb); 90 if (!rs->prior_delivered || 91 tcp_skb_sent_after(tx_tstamp, tp->first_tx_mstamp, 92 scb->end_seq, rs->last_end_seq)) { 93 rs->prior_delivered = scb->tx.delivered; 94 rs->prior_mstamp = scb->tx.delivered_mstamp; 95 rs->is_app_limited = scb->tx.is_app_limited; 96 rs->is_retrans = scb->sacked & TCPCB_RETRANS; 97 rs->last_end_seq = scb->end_seq; 98 99 /* Record send time of most recently ACKed packet: */ 100 tp->first_tx_mstamp = tx_tstamp; 101 /* Find the duration of the "send phase" of this window: */ 102 rs->interval_us = tcp_stamp_us_delta(tp->first_tx_mstamp, 103 scb->tx.first_tx_mstamp); 104 105 } 106 /* Mark off the skb delivered once it's sacked to avoid being 107 * used again when it's cumulatively acked. For acked packets 108 * we don't need to reset since it'll be freed soon. 109 */ 110 if (scb->sacked & TCPCB_SACKED_ACKED) 111 scb->tx.delivered_mstamp = 0; 112} 113 114/* Update the connection delivery information and generate a rate sample. */ 115void tcp_rate_gen(struct sock *sk, u32 delivered, u32 lost, 116 bool is_sack_reneg, struct rate_sample *rs) 117{ 118 struct tcp_sock *tp = tcp_sk(sk); 119 u32 snd_us, ack_us; 120 121 /* Clear app limited if bubble is acked and gone. */ 122 if (tp->app_limited && after(tp->delivered, tp->app_limited)) 123 tp->app_limited = 0; 124 125 /* TODO: there are multiple places throughout tcp_ack() to get 126 * current time. Refactor the code using a new "tcp_acktag_state" 127 * to carry current time, flags, stats like "tcp_sacktag_state". 128 */ 129 if (delivered) 130 tp->delivered_mstamp = tp->tcp_mstamp; 131 132 rs->acked_sacked = delivered; /* freshly ACKed or SACKed */ 133 rs->losses = lost; /* freshly marked lost */ 134 /* Return an invalid sample if no timing information is available or 135 * in recovery from loss with SACK reneging. Rate samples taken during 136 * a SACK reneging event may overestimate bw by including packets that 137 * were SACKed before the reneg. 138 */ 139 if (!rs->prior_mstamp || is_sack_reneg) { 140 rs->delivered = -1; 141 rs->interval_us = -1; 142 return; 143 } 144 rs->delivered = tp->delivered - rs->prior_delivered; 145 146 /* Model sending data and receiving ACKs as separate pipeline phases 147 * for a window. Usually the ACK phase is longer, but with ACK 148 * compression the send phase can be longer. To be safe we use the 149 * longer phase. 150 */ 151 snd_us = rs->interval_us; /* send phase */ 152 ack_us = tcp_stamp_us_delta(tp->tcp_mstamp, 153 rs->prior_mstamp); /* ack phase */ 154 rs->interval_us = max(snd_us, ack_us); 155 156 /* Record both segment send and ack receive intervals */ 157 rs->snd_interval_us = snd_us; 158 rs->rcv_interval_us = ack_us; 159 160 /* Normally we expect interval_us >= min-rtt. 161 * Note that rate may still be over-estimated when a spuriously 162 * retransmistted skb was first (s)acked because "interval_us" 163 * is under-estimated (up to an RTT). However continuously 164 * measuring the delivery rate during loss recovery is crucial 165 * for connections suffer heavy or prolonged losses. 166 */ 167 if (unlikely(rs->interval_us < tcp_min_rtt(tp))) { 168 if (!rs->is_retrans) 169 pr_debug("tcp rate: %ld %d %u %u %u\n", 170 rs->interval_us, rs->delivered, 171 inet_csk(sk)->icsk_ca_state, 172 tp->rx_opt.sack_ok, tcp_min_rtt(tp)); 173 rs->interval_us = -1; 174 return; 175 } 176 177 /* Record the last non-app-limited or the highest app-limited bw */ 178 if (!rs->is_app_limited || 179 ((u64)rs->delivered * tp->rate_interval_us >= 180 (u64)tp->rate_delivered * rs->interval_us)) { 181 tp->rate_delivered = rs->delivered; 182 tp->rate_interval_us = rs->interval_us; 183 tp->rate_app_limited = rs->is_app_limited; 184 } 185} 186 187/* If a gap is detected between sends, mark the socket application-limited. */ 188void tcp_rate_check_app_limited(struct sock *sk) 189{ 190 struct tcp_sock *tp = tcp_sk(sk); 191 192 if (/* We have less than one packet to send. */ 193 tp->write_seq - tp->snd_nxt < tp->mss_cache && 194 /* Nothing in sending host's qdisc queues or NIC tx queue. */ 195 sk_wmem_alloc_get(sk) < SKB_TRUESIZE(1) && 196 /* We are not limited by CWND. */ 197 tcp_packets_in_flight(tp) < tp->snd_cwnd && 198 /* All lost packets have been retransmitted. */ 199 tp->lost_out <= tp->retrans_out) 200 tp->app_limited = 201 (tp->delivered + tcp_packets_in_flight(tp)) ? : 1; 202} 203EXPORT_SYMBOL_GPL(tcp_rate_check_app_limited); 204