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