blob: c6a9fa8946462100947ab62d86464ff8f99565c2 [file] [log] [blame]
Yuchung Chengb9f64822016-09-19 23:39:14 -04001#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.
Soheil Hassas Yeganehd7722e82016-09-19 23:39:15 -040029 *
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.
Yuchung Chengb9f64822016-09-19 23:39:14 -040034 */
35
Yuchung Chengb9f64822016-09-19 23:39:14 -040036/* 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;
Soheil Hassas Yeganehd7722e82016-09-19 23:39:15 -040065 TCP_SKB_CB(skb)->tx.is_app_limited = tp->app_limited ? 1 : 0;
Yuchung Chengb9f64822016-09-19 23:39:14 -040066}
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;
Soheil Hassas Yeganehd7722e82016-09-19 23:39:15 -040088 rs->is_app_limited = scb->tx.is_app_limited;
Yuchung Chengb9f64822016-09-19 23:39:14 -040089 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,
Eric Dumazet88d5c652017-04-25 10:15:37 -0700109 struct rate_sample *rs)
Yuchung Chengb9f64822016-09-19 23:39:14 -0400110{
111 struct tcp_sock *tp = tcp_sk(sk);
112 u32 snd_us, ack_us;
113
Soheil Hassas Yeganehd7722e82016-09-19 23:39:15 -0400114 /* 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
Yuchung Chengb9f64822016-09-19 23:39:14 -0400118 /* 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)
Eric Dumazet88d5c652017-04-25 10:15:37 -0700123 tp->delivered_mstamp = tp->tcp_mstamp;
Yuchung Chengb9f64822016-09-19 23:39:14 -0400124
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 */
Eric Dumazet88d5c652017-04-25 10:15:37 -0700141 ack_us = skb_mstamp_us_delta(&tp->tcp_mstamp,
142 &rs->prior_mstamp); /* ack phase */
Yuchung Chengb9f64822016-09-19 23:39:14 -0400143 rs->interval_us = max(snd_us, ack_us);
144
145 /* Normally we expect interval_us >= min-rtt.
146 * Note that rate may still be over-estimated when a spuriously
147 * retransmistted skb was first (s)acked because "interval_us"
148 * is under-estimated (up to an RTT). However continuously
149 * measuring the delivery rate during loss recovery is crucial
150 * for connections suffer heavy or prolonged losses.
151 */
152 if (unlikely(rs->interval_us < tcp_min_rtt(tp))) {
Yuchung Chengb9f64822016-09-19 23:39:14 -0400153 if (!rs->is_retrans)
154 pr_debug("tcp rate: %ld %d %u %u %u\n",
155 rs->interval_us, rs->delivered,
156 inet_csk(sk)->icsk_ca_state,
157 tp->rx_opt.sack_ok, tcp_min_rtt(tp));
Yuchung Chengeb8329e2016-09-19 23:39:16 -0400158 rs->interval_us = -1;
159 return;
160 }
161
162 /* Record the last non-app-limited or the highest app-limited bw */
163 if (!rs->is_app_limited ||
164 ((u64)rs->delivered * tp->rate_interval_us >=
165 (u64)tp->rate_delivered * rs->interval_us)) {
166 tp->rate_delivered = rs->delivered;
167 tp->rate_interval_us = rs->interval_us;
168 tp->rate_app_limited = rs->is_app_limited;
Yuchung Chengb9f64822016-09-19 23:39:14 -0400169 }
170}
Soheil Hassas Yeganehd7722e82016-09-19 23:39:15 -0400171
172/* If a gap is detected between sends, mark the socket application-limited. */
173void tcp_rate_check_app_limited(struct sock *sk)
174{
175 struct tcp_sock *tp = tcp_sk(sk);
176
177 if (/* We have less than one packet to send. */
178 tp->write_seq - tp->snd_nxt < tp->mss_cache &&
179 /* Nothing in sending host's qdisc queues or NIC tx queue. */
180 sk_wmem_alloc_get(sk) < SKB_TRUESIZE(1) &&
181 /* We are not limited by CWND. */
182 tcp_packets_in_flight(tp) < tp->snd_cwnd &&
183 /* All lost packets have been retransmitted. */
184 tp->lost_out <= tp->retrans_out)
185 tp->app_limited =
186 (tp->delivered + tcp_packets_in_flight(tp)) ? : 1;
187}