1*b9f64820SYuchung Cheng #include <net/tcp.h> 2*b9f64820SYuchung Cheng 3*b9f64820SYuchung Cheng /* The bandwidth estimator estimates the rate at which the network 4*b9f64820SYuchung Cheng * can currently deliver outbound data packets for this flow. At a high 5*b9f64820SYuchung Cheng * level, it operates by taking a delivery rate sample for each ACK. 6*b9f64820SYuchung Cheng * 7*b9f64820SYuchung Cheng * A rate sample records the rate at which the network delivered packets 8*b9f64820SYuchung Cheng * for this flow, calculated over the time interval between the transmission 9*b9f64820SYuchung Cheng * of a data packet and the acknowledgment of that packet. 10*b9f64820SYuchung Cheng * 11*b9f64820SYuchung Cheng * Specifically, over the interval between each transmit and corresponding ACK, 12*b9f64820SYuchung Cheng * the estimator generates a delivery rate sample. Typically it uses the rate 13*b9f64820SYuchung Cheng * at which packets were acknowledged. However, the approach of using only the 14*b9f64820SYuchung Cheng * acknowledgment rate faces a challenge under the prevalent ACK decimation or 15*b9f64820SYuchung Cheng * compression: packets can temporarily appear to be delivered much quicker 16*b9f64820SYuchung Cheng * than the bottleneck rate. Since it is physically impossible to do that in a 17*b9f64820SYuchung Cheng * sustained fashion, when the estimator notices that the ACK rate is faster 18*b9f64820SYuchung Cheng * than the transmit rate, it uses the latter: 19*b9f64820SYuchung Cheng * 20*b9f64820SYuchung Cheng * send_rate = #pkts_delivered/(last_snd_time - first_snd_time) 21*b9f64820SYuchung Cheng * ack_rate = #pkts_delivered/(last_ack_time - first_ack_time) 22*b9f64820SYuchung Cheng * bw = min(send_rate, ack_rate) 23*b9f64820SYuchung Cheng * 24*b9f64820SYuchung Cheng * Notice the estimator essentially estimates the goodput, not always the 25*b9f64820SYuchung Cheng * network bottleneck link rate when the sending or receiving is limited by 26*b9f64820SYuchung Cheng * other factors like applications or receiver window limits. The estimator 27*b9f64820SYuchung Cheng * deliberately avoids using the inter-packet spacing approach because that 28*b9f64820SYuchung Cheng * approach requires a large number of samples and sophisticated filtering. 29*b9f64820SYuchung Cheng */ 30*b9f64820SYuchung Cheng 31*b9f64820SYuchung Cheng 32*b9f64820SYuchung Cheng /* Snapshot the current delivery information in the skb, to generate 33*b9f64820SYuchung Cheng * a rate sample later when the skb is (s)acked in tcp_rate_skb_delivered(). 34*b9f64820SYuchung Cheng */ 35*b9f64820SYuchung Cheng void tcp_rate_skb_sent(struct sock *sk, struct sk_buff *skb) 36*b9f64820SYuchung Cheng { 37*b9f64820SYuchung Cheng struct tcp_sock *tp = tcp_sk(sk); 38*b9f64820SYuchung Cheng 39*b9f64820SYuchung Cheng /* In general we need to start delivery rate samples from the 40*b9f64820SYuchung Cheng * time we received the most recent ACK, to ensure we include 41*b9f64820SYuchung Cheng * the full time the network needs to deliver all in-flight 42*b9f64820SYuchung Cheng * packets. If there are no packets in flight yet, then we 43*b9f64820SYuchung Cheng * know that any ACKs after now indicate that the network was 44*b9f64820SYuchung Cheng * able to deliver those packets completely in the sampling 45*b9f64820SYuchung Cheng * interval between now and the next ACK. 46*b9f64820SYuchung Cheng * 47*b9f64820SYuchung Cheng * Note that we use packets_out instead of tcp_packets_in_flight(tp) 48*b9f64820SYuchung Cheng * because the latter is a guess based on RTO and loss-marking 49*b9f64820SYuchung Cheng * heuristics. We don't want spurious RTOs or loss markings to cause 50*b9f64820SYuchung Cheng * a spuriously small time interval, causing a spuriously high 51*b9f64820SYuchung Cheng * bandwidth estimate. 52*b9f64820SYuchung Cheng */ 53*b9f64820SYuchung Cheng if (!tp->packets_out) { 54*b9f64820SYuchung Cheng tp->first_tx_mstamp = skb->skb_mstamp; 55*b9f64820SYuchung Cheng tp->delivered_mstamp = skb->skb_mstamp; 56*b9f64820SYuchung Cheng } 57*b9f64820SYuchung Cheng 58*b9f64820SYuchung Cheng TCP_SKB_CB(skb)->tx.first_tx_mstamp = tp->first_tx_mstamp; 59*b9f64820SYuchung Cheng TCP_SKB_CB(skb)->tx.delivered_mstamp = tp->delivered_mstamp; 60*b9f64820SYuchung Cheng TCP_SKB_CB(skb)->tx.delivered = tp->delivered; 61*b9f64820SYuchung Cheng } 62*b9f64820SYuchung Cheng 63*b9f64820SYuchung Cheng /* When an skb is sacked or acked, we fill in the rate sample with the (prior) 64*b9f64820SYuchung Cheng * delivery information when the skb was last transmitted. 65*b9f64820SYuchung Cheng * 66*b9f64820SYuchung Cheng * If an ACK (s)acks multiple skbs (e.g., stretched-acks), this function is 67*b9f64820SYuchung Cheng * called multiple times. We favor the information from the most recently 68*b9f64820SYuchung Cheng * sent skb, i.e., the skb with the highest prior_delivered count. 69*b9f64820SYuchung Cheng */ 70*b9f64820SYuchung Cheng void tcp_rate_skb_delivered(struct sock *sk, struct sk_buff *skb, 71*b9f64820SYuchung Cheng struct rate_sample *rs) 72*b9f64820SYuchung Cheng { 73*b9f64820SYuchung Cheng struct tcp_sock *tp = tcp_sk(sk); 74*b9f64820SYuchung Cheng struct tcp_skb_cb *scb = TCP_SKB_CB(skb); 75*b9f64820SYuchung Cheng 76*b9f64820SYuchung Cheng if (!scb->tx.delivered_mstamp.v64) 77*b9f64820SYuchung Cheng return; 78*b9f64820SYuchung Cheng 79*b9f64820SYuchung Cheng if (!rs->prior_delivered || 80*b9f64820SYuchung Cheng after(scb->tx.delivered, rs->prior_delivered)) { 81*b9f64820SYuchung Cheng rs->prior_delivered = scb->tx.delivered; 82*b9f64820SYuchung Cheng rs->prior_mstamp = scb->tx.delivered_mstamp; 83*b9f64820SYuchung Cheng rs->is_retrans = scb->sacked & TCPCB_RETRANS; 84*b9f64820SYuchung Cheng 85*b9f64820SYuchung Cheng /* Find the duration of the "send phase" of this window: */ 86*b9f64820SYuchung Cheng rs->interval_us = skb_mstamp_us_delta( 87*b9f64820SYuchung Cheng &skb->skb_mstamp, 88*b9f64820SYuchung Cheng &scb->tx.first_tx_mstamp); 89*b9f64820SYuchung Cheng 90*b9f64820SYuchung Cheng /* Record send time of most recently ACKed packet: */ 91*b9f64820SYuchung Cheng tp->first_tx_mstamp = skb->skb_mstamp; 92*b9f64820SYuchung Cheng } 93*b9f64820SYuchung Cheng /* Mark off the skb delivered once it's sacked to avoid being 94*b9f64820SYuchung Cheng * used again when it's cumulatively acked. For acked packets 95*b9f64820SYuchung Cheng * we don't need to reset since it'll be freed soon. 96*b9f64820SYuchung Cheng */ 97*b9f64820SYuchung Cheng if (scb->sacked & TCPCB_SACKED_ACKED) 98*b9f64820SYuchung Cheng scb->tx.delivered_mstamp.v64 = 0; 99*b9f64820SYuchung Cheng } 100*b9f64820SYuchung Cheng 101*b9f64820SYuchung Cheng /* Update the connection delivery information and generate a rate sample. */ 102*b9f64820SYuchung Cheng void tcp_rate_gen(struct sock *sk, u32 delivered, u32 lost, 103*b9f64820SYuchung Cheng struct skb_mstamp *now, struct rate_sample *rs) 104*b9f64820SYuchung Cheng { 105*b9f64820SYuchung Cheng struct tcp_sock *tp = tcp_sk(sk); 106*b9f64820SYuchung Cheng u32 snd_us, ack_us; 107*b9f64820SYuchung Cheng 108*b9f64820SYuchung Cheng /* TODO: there are multiple places throughout tcp_ack() to get 109*b9f64820SYuchung Cheng * current time. Refactor the code using a new "tcp_acktag_state" 110*b9f64820SYuchung Cheng * to carry current time, flags, stats like "tcp_sacktag_state". 111*b9f64820SYuchung Cheng */ 112*b9f64820SYuchung Cheng if (delivered) 113*b9f64820SYuchung Cheng tp->delivered_mstamp = *now; 114*b9f64820SYuchung Cheng 115*b9f64820SYuchung Cheng rs->acked_sacked = delivered; /* freshly ACKed or SACKed */ 116*b9f64820SYuchung Cheng rs->losses = lost; /* freshly marked lost */ 117*b9f64820SYuchung Cheng /* Return an invalid sample if no timing information is available. */ 118*b9f64820SYuchung Cheng if (!rs->prior_mstamp.v64) { 119*b9f64820SYuchung Cheng rs->delivered = -1; 120*b9f64820SYuchung Cheng rs->interval_us = -1; 121*b9f64820SYuchung Cheng return; 122*b9f64820SYuchung Cheng } 123*b9f64820SYuchung Cheng rs->delivered = tp->delivered - rs->prior_delivered; 124*b9f64820SYuchung Cheng 125*b9f64820SYuchung Cheng /* Model sending data and receiving ACKs as separate pipeline phases 126*b9f64820SYuchung Cheng * for a window. Usually the ACK phase is longer, but with ACK 127*b9f64820SYuchung Cheng * compression the send phase can be longer. To be safe we use the 128*b9f64820SYuchung Cheng * longer phase. 129*b9f64820SYuchung Cheng */ 130*b9f64820SYuchung Cheng snd_us = rs->interval_us; /* send phase */ 131*b9f64820SYuchung Cheng ack_us = skb_mstamp_us_delta(now, &rs->prior_mstamp); /* ack phase */ 132*b9f64820SYuchung Cheng rs->interval_us = max(snd_us, ack_us); 133*b9f64820SYuchung Cheng 134*b9f64820SYuchung Cheng /* Normally we expect interval_us >= min-rtt. 135*b9f64820SYuchung Cheng * Note that rate may still be over-estimated when a spuriously 136*b9f64820SYuchung Cheng * retransmistted skb was first (s)acked because "interval_us" 137*b9f64820SYuchung Cheng * is under-estimated (up to an RTT). However continuously 138*b9f64820SYuchung Cheng * measuring the delivery rate during loss recovery is crucial 139*b9f64820SYuchung Cheng * for connections suffer heavy or prolonged losses. 140*b9f64820SYuchung Cheng */ 141*b9f64820SYuchung Cheng if (unlikely(rs->interval_us < tcp_min_rtt(tp))) { 142*b9f64820SYuchung Cheng rs->interval_us = -1; 143*b9f64820SYuchung Cheng if (!rs->is_retrans) 144*b9f64820SYuchung Cheng pr_debug("tcp rate: %ld %d %u %u %u\n", 145*b9f64820SYuchung Cheng rs->interval_us, rs->delivered, 146*b9f64820SYuchung Cheng inet_csk(sk)->icsk_ca_state, 147*b9f64820SYuchung Cheng tp->rx_opt.sack_ok, tcp_min_rtt(tp)); 148*b9f64820SYuchung Cheng } 149*b9f64820SYuchung Cheng } 150