net/ipv4/tcp_rate.c

   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                 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  */
  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)
  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      = tcp_stamp_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 = 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,
 109                   bool is_sack_reneg, 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 = tp->tcp_mstamp;
 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 or
 128          * in recovery from loss with SACK reneging. Rate samples taken during
 129          * a SACK reneging event may overestimate bw by including packets that
 130          * were SACKed before the reneg.
 131          */
 132         if (!rs->prior_mstamp || is_sack_reneg) {
 133                 rs->delivered = -1;
 134                 rs->interval_us = -1;
 135                 return;
 136         }
 137         rs->delivered   = tp->delivered - rs->prior_delivered;
 138
 139         /* Model sending data and receiving ACKs as separate pipeline phases
 140          * for a window. Usually the ACK phase is longer, but with ACK
 141          * compression the send phase can be longer. To be safe we use the
 142          * longer phase.
 143          */
 144         snd_us = rs->interval_us;                               /* send phase */
 145         ack_us = tcp_stamp_us_delta(tp->tcp_mstamp,
 146                                     rs->prior_mstamp); /* ack phase */
 147         rs->interval_us = max(snd_us, ack_us);
 148
 149         /* Normally we expect interval_us >= min-rtt.
 150          * Note that rate may still be over-estimated when a spuriously
 151          * retransmistted skb was first (s)acked because "interval_us"
 152          * is under-estimated (up to an RTT). However continuously
 153          * measuring the delivery rate during loss recovery is crucial
 154          * for connections suffer heavy or prolonged losses.
 155          */
 156         if (unlikely(rs->interval_us < tcp_min_rtt(tp))) {
 157                 if (!rs->is_retrans)
 158                         pr_debug("tcp rate: %ld %d %u %u %u\n",
 159                                  rs->interval_us, rs->delivered,
 160                                  inet_csk(sk)->icsk_ca_state,
 161                                  tp->rx_opt.sack_ok, tcp_min_rtt(tp));
 162                 rs->interval_us = -1;
 163                 return;
 164         }
 165
 166         /* Record the last non-app-limited or the highest app-limited bw */
 167         if (!rs->is_app_limited ||
 168             ((u64)rs->delivered * tp->rate_interval_us >=
 169              (u64)tp->rate_delivered * rs->interval_us)) {
 170                 tp->rate_delivered = rs->delivered;
 171                 tp->rate_interval_us = rs->interval_us;
 172                 tp->rate_app_limited = rs->is_app_limited;
 173         }
 174 }
 175
 176 /* If a gap is detected between sends, mark the socket application-limited. */
 177 void tcp_rate_check_app_limited(struct sock *sk)
 178 {
 179         struct tcp_sock *tp = tcp_sk(sk);
 180
 181         if (/* We have less than one packet to send. */
 182             tp->write_seq - tp->snd_nxt < tp->mss_cache &&
 183             /* Nothing in sending host's qdisc queues or NIC tx queue. */
 184             sk_wmem_alloc_get(sk) < SKB_TRUESIZE(1) &&
 185             /* We are not limited by CWND. */
 186             tcp_packets_in_flight(tp) < tp->snd_cwnd &&
 187             /* All lost packets have been retransmitted. */
 188             tp->lost_out <= tp->retrans_out)
 189                 tp->app_limited =
 190                         (tp->delivered + tcp_packets_in_flight(tp)) ? : 1;
 191 }
 192 EXPORT_SYMBOL_GPL(tcp_rate_check_app_limited);