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