Yuchung Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 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. |
Soheil Hassas Yeganeh | d7722e8 | 2016-09-19 23:39:15 -0400 | [diff] [blame] | 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. |
Yuchung Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 34 | */ |
| 35 | |
Yuchung Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 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 | 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 Yeganeh | d7722e8 | 2016-09-19 23:39:15 -0400 | [diff] [blame] | 65 | TCP_SKB_CB(skb)->tx.is_app_limited = tp->app_limited ? 1 : 0; |
Yuchung Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 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 | */ |
| 75 | void 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 Yeganeh | d7722e8 | 2016-09-19 23:39:15 -0400 | [diff] [blame] | 88 | rs->is_app_limited = scb->tx.is_app_limited; |
Yuchung Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 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. */ |
| 108 | void tcp_rate_gen(struct sock *sk, u32 delivered, u32 lost, |
Eric Dumazet | 88d5c65 | 2017-04-25 10:15:37 -0700 | [diff] [blame] | 109 | struct rate_sample *rs) |
Yuchung Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 110 | { |
| 111 | struct tcp_sock *tp = tcp_sk(sk); |
| 112 | u32 snd_us, ack_us; |
| 113 | |
Soheil Hassas Yeganeh | d7722e8 | 2016-09-19 23:39:15 -0400 | [diff] [blame] | 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 | |
Yuchung Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 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) |
Eric Dumazet | 88d5c65 | 2017-04-25 10:15:37 -0700 | [diff] [blame] | 123 | tp->delivered_mstamp = tp->tcp_mstamp; |
Yuchung Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 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 */ |
Eric Dumazet | 88d5c65 | 2017-04-25 10:15:37 -0700 | [diff] [blame] | 141 | ack_us = skb_mstamp_us_delta(&tp->tcp_mstamp, |
| 142 | &rs->prior_mstamp); /* ack phase */ |
Yuchung Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 143 | 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 Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 153 | 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 Cheng | eb8329e | 2016-09-19 23:39:16 -0400 | [diff] [blame] | 158 | 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 Cheng | b9f6482 | 2016-09-19 23:39:14 -0400 | [diff] [blame] | 169 | } |
| 170 | } |
Soheil Hassas Yeganeh | d7722e8 | 2016-09-19 23:39:15 -0400 | [diff] [blame] | 171 | |
| 172 | /* If a gap is detected between sends, mark the socket application-limited. */ |
| 173 | void 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 | } |