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 | */ |
39 | void 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 | u64 tstamp_us = tcp_skb_timestamp_us(skb); |
59 | |
60 | tp->first_tx_mstamp = tstamp_us; |
61 | tp->delivered_mstamp = tstamp_us; |
62 | } |
63 | |
64 | TCP_SKB_CB(skb)->tx.first_tx_mstamp = tp->first_tx_mstamp; |
65 | TCP_SKB_CB(skb)->tx.delivered_mstamp = tp->delivered_mstamp; |
66 | TCP_SKB_CB(skb)->tx.delivered = tp->delivered; |
67 | TCP_SKB_CB(skb)->tx.is_app_limited = tp->app_limited ? 1 : 0; |
68 | } |
69 | |
70 | /* When an skb is sacked or acked, we fill in the rate sample with the (prior) |
71 | * delivery information when the skb was last transmitted. |
72 | * |
73 | * If an ACK (s)acks multiple skbs (e.g., stretched-acks), this function is |
74 | * called multiple times. We favor the information from the most recently |
75 | * sent skb, i.e., the skb with the highest prior_delivered count. |
76 | */ |
77 | void tcp_rate_skb_delivered(struct sock *sk, struct sk_buff *skb, |
78 | struct rate_sample *rs) |
79 | { |
80 | struct tcp_sock *tp = tcp_sk(sk); |
81 | struct tcp_skb_cb *scb = TCP_SKB_CB(skb); |
82 | |
83 | if (!scb->tx.delivered_mstamp) |
84 | return; |
85 | |
86 | if (!rs->prior_delivered || |
87 | after(scb->tx.delivered, rs->prior_delivered)) { |
88 | rs->prior_delivered = scb->tx.delivered; |
89 | rs->prior_mstamp = scb->tx.delivered_mstamp; |
90 | rs->is_app_limited = scb->tx.is_app_limited; |
91 | rs->is_retrans = scb->sacked & TCPCB_RETRANS; |
92 | |
93 | /* Record send time of most recently ACKed packet: */ |
94 | tp->first_tx_mstamp = tcp_skb_timestamp_us(skb); |
95 | /* Find the duration of the "send phase" of this window: */ |
96 | rs->interval_us = tcp_stamp_us_delta(tp->first_tx_mstamp, |
97 | scb->tx.first_tx_mstamp); |
98 | |
99 | } |
100 | /* Mark off the skb delivered once it's sacked to avoid being |
101 | * used again when it's cumulatively acked. For acked packets |
102 | * we don't need to reset since it'll be freed soon. |
103 | */ |
104 | if (scb->sacked & TCPCB_SACKED_ACKED) |
105 | scb->tx.delivered_mstamp = 0; |
106 | } |
107 | |
108 | /* Update the connection delivery information and generate a rate sample. */ |
109 | void tcp_rate_gen(struct sock *sk, u32 delivered, u32 lost, |
110 | bool is_sack_reneg, struct rate_sample *rs) |
111 | { |
112 | struct tcp_sock *tp = tcp_sk(sk); |
113 | u32 snd_us, ack_us; |
114 | |
115 | /* Clear app limited if bubble is acked and gone. */ |
116 | if (tp->app_limited && after(tp->delivered, tp->app_limited)) |
117 | tp->app_limited = 0; |
118 | |
119 | /* TODO: there are multiple places throughout tcp_ack() to get |
120 | * current time. Refactor the code using a new "tcp_acktag_state" |
121 | * to carry current time, flags, stats like "tcp_sacktag_state". |
122 | */ |
123 | if (delivered) |
124 | tp->delivered_mstamp = tp->tcp_mstamp; |
125 | |
126 | rs->acked_sacked = delivered; /* freshly ACKed or SACKed */ |
127 | rs->losses = lost; /* freshly marked lost */ |
128 | /* Return an invalid sample if no timing information is available or |
129 | * in recovery from loss with SACK reneging. Rate samples taken during |
130 | * a SACK reneging event may overestimate bw by including packets that |
131 | * were SACKed before the reneg. |
132 | */ |
133 | if (!rs->prior_mstamp || is_sack_reneg) { |
134 | rs->delivered = -1; |
135 | rs->interval_us = -1; |
136 | return; |
137 | } |
138 | rs->delivered = tp->delivered - rs->prior_delivered; |
139 | |
140 | /* Model sending data and receiving ACKs as separate pipeline phases |
141 | * for a window. Usually the ACK phase is longer, but with ACK |
142 | * compression the send phase can be longer. To be safe we use the |
143 | * longer phase. |
144 | */ |
145 | snd_us = rs->interval_us; /* send phase */ |
146 | ack_us = tcp_stamp_us_delta(tp->tcp_mstamp, |
147 | rs->prior_mstamp); /* ack phase */ |
148 | rs->interval_us = max(snd_us, ack_us); |
149 | |
150 | /* Record both segment send and ack receive intervals */ |
151 | rs->snd_interval_us = snd_us; |
152 | rs->rcv_interval_us = ack_us; |
153 | |
154 | /* Normally we expect interval_us >= min-rtt. |
155 | * Note that rate may still be over-estimated when a spuriously |
156 | * retransmistted skb was first (s)acked because "interval_us" |
157 | * is under-estimated (up to an RTT). However continuously |
158 | * measuring the delivery rate during loss recovery is crucial |
159 | * for connections suffer heavy or prolonged losses. |
160 | */ |
161 | if (unlikely(rs->interval_us < tcp_min_rtt(tp))) { |
162 | if (!rs->is_retrans) |
163 | pr_debug("tcp rate: %ld %d %u %u %u\n" , |
164 | rs->interval_us, rs->delivered, |
165 | inet_csk(sk)->icsk_ca_state, |
166 | tp->rx_opt.sack_ok, tcp_min_rtt(tp)); |
167 | rs->interval_us = -1; |
168 | return; |
169 | } |
170 | |
171 | /* Record the last non-app-limited or the highest app-limited bw */ |
172 | if (!rs->is_app_limited || |
173 | ((u64)rs->delivered * tp->rate_interval_us >= |
174 | (u64)tp->rate_delivered * rs->interval_us)) { |
175 | tp->rate_delivered = rs->delivered; |
176 | tp->rate_interval_us = rs->interval_us; |
177 | tp->rate_app_limited = rs->is_app_limited; |
178 | } |
179 | } |
180 | |
181 | /* If a gap is detected between sends, mark the socket application-limited. */ |
182 | void tcp_rate_check_app_limited(struct sock *sk) |
183 | { |
184 | struct tcp_sock *tp = tcp_sk(sk); |
185 | |
186 | if (/* We have less than one packet to send. */ |
187 | tp->write_seq - tp->snd_nxt < tp->mss_cache && |
188 | /* Nothing in sending host's qdisc queues or NIC tx queue. */ |
189 | sk_wmem_alloc_get(sk) < SKB_TRUESIZE(1) && |
190 | /* We are not limited by CWND. */ |
191 | tcp_packets_in_flight(tp) < tp->snd_cwnd && |
192 | /* All lost packets have been retransmitted. */ |
193 | tp->lost_out <= tp->retrans_out) |
194 | tp->app_limited = |
195 | (tp->delivered + tcp_packets_in_flight(tp)) ? : 1; |
196 | } |
197 | EXPORT_SYMBOL_GPL(tcp_rate_check_app_limited); |
198 | |