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