lsquic_bbr.c revision a74702c6
1a74702c6SGeorge Wang/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc.  See LICENSE. */
25392f7a3SLiteSpeed Tech// Copyright 2016 The Chromium Authors. All rights reserved.
35392f7a3SLiteSpeed Tech// Use of this source code is governed by a BSD-style license that can be
45392f7a3SLiteSpeed Tech// found in the LICENSE.chrome file.
55392f7a3SLiteSpeed Tech
65392f7a3SLiteSpeed Tech#include <assert.h>
75392f7a3SLiteSpeed Tech#include <inttypes.h>
85392f7a3SLiteSpeed Tech#include <stdint.h>
95392f7a3SLiteSpeed Tech#include <stdlib.h>
105392f7a3SLiteSpeed Tech#include <string.h>
115392f7a3SLiteSpeed Tech#include <sys/queue.h>
125392f7a3SLiteSpeed Tech
135392f7a3SLiteSpeed Tech#include "lsquic.h"
145392f7a3SLiteSpeed Tech#include "lsquic_int_types.h"
155392f7a3SLiteSpeed Tech#include "lsquic_cong_ctl.h"
165392f7a3SLiteSpeed Tech#include "lsquic_minmax.h"
175392f7a3SLiteSpeed Tech#include "lsquic_packet_common.h"
185392f7a3SLiteSpeed Tech#include "lsquic_packet_out.h"
195392f7a3SLiteSpeed Tech#include "lsquic_bw_sampler.h"
205392f7a3SLiteSpeed Tech#include "lsquic_bbr.h"
215392f7a3SLiteSpeed Tech#include "lsquic_hash.h"
225392f7a3SLiteSpeed Tech#include "lsquic_conn.h"
235392f7a3SLiteSpeed Tech#include "lsquic_sfcw.h"
245392f7a3SLiteSpeed Tech#include "lsquic_conn_flow.h"
255392f7a3SLiteSpeed Tech#include "lsquic_varint.h"
265392f7a3SLiteSpeed Tech#include "lsquic_hq.h"
275392f7a3SLiteSpeed Tech#include "lsquic_stream.h"
285392f7a3SLiteSpeed Tech#include "lsquic_rtt.h"
295392f7a3SLiteSpeed Tech#include "lsquic_conn_public.h"
305392f7a3SLiteSpeed Tech#include "lsquic_util.h"
315392f7a3SLiteSpeed Tech#include "lsquic_malo.h"
3210c41073SDmitri Tikhonov#include "lsquic_crand.h"
3310c41073SDmitri Tikhonov#include "lsquic_mm.h"
3410c41073SDmitri Tikhonov#include "lsquic_engine_public.h"
355392f7a3SLiteSpeed Tech
365392f7a3SLiteSpeed Tech#define LSQUIC_LOGGER_MODULE LSQLM_BBR
3710c41073SDmitri Tikhonov#define LSQUIC_LOG_CONN_ID lsquic_conn_log_cid(bbr->bbr_conn_pub->lconn)
385392f7a3SLiteSpeed Tech#include "lsquic_logger.h"
395392f7a3SLiteSpeed Tech
405392f7a3SLiteSpeed Tech#define MIN(a, b) ((a) < (b) ? (a) : (b))
415392f7a3SLiteSpeed Tech#define MAX(a, b) ((a) > (b) ? (a) : (b))
425392f7a3SLiteSpeed Tech
435392f7a3SLiteSpeed Tech#define ms(val_) ((val_) * 1000)
445392f7a3SLiteSpeed Tech#define sec(val_) ((val_) * 1000 * 1000)
455392f7a3SLiteSpeed Tech
465392f7a3SLiteSpeed Tech// Default maximum packet size used in the Linux TCP implementation.
475392f7a3SLiteSpeed Tech// Used in QUIC for congestion window computations in bytes.
485392f7a3SLiteSpeed Tech#define kDefaultTCPMSS 1460
495392f7a3SLiteSpeed Tech#define kMaxSegmentSize kDefaultTCPMSS
505392f7a3SLiteSpeed Tech
515392f7a3SLiteSpeed Tech// Constants based on TCP defaults.
525392f7a3SLiteSpeed Tech// The minimum CWND to ensure delayed acks don't reduce bandwidth measurements.
535392f7a3SLiteSpeed Tech// Does not inflate the pacing rate.
545392f7a3SLiteSpeed Tech#define kDefaultMinimumCongestionWindow  (4 * kDefaultTCPMSS)
555392f7a3SLiteSpeed Tech
565392f7a3SLiteSpeed Tech// The gain used for the STARTUP, equal to 2/ln(2).
575392f7a3SLiteSpeed Tech#define kDefaultHighGain 2.885f
585392f7a3SLiteSpeed Tech
595392f7a3SLiteSpeed Tech// The newly derived gain for STARTUP, equal to 4 * ln(2)
605392f7a3SLiteSpeed Tech#define kDerivedHighGain 2.773f
615392f7a3SLiteSpeed Tech
625392f7a3SLiteSpeed Tech// The newly derived CWND gain for STARTUP, 2.
635392f7a3SLiteSpeed Tech#define kDerivedHighCWNDGain 2.0f
645392f7a3SLiteSpeed Tech
655392f7a3SLiteSpeed Tech// The gain used in STARTUP after loss has been detected.
665392f7a3SLiteSpeed Tech// 1.5 is enough to allow for 25% exogenous loss and still observe a 25% growth
675392f7a3SLiteSpeed Tech// in measured bandwidth.
685392f7a3SLiteSpeed Tech#define kStartupAfterLossGain 1.5f
695392f7a3SLiteSpeed Tech
705392f7a3SLiteSpeed Tech// We match SPDY's use of 32 (since we'd compete with SPDY).
715392f7a3SLiteSpeed Tech#define kInitialCongestionWindow 32
725392f7a3SLiteSpeed Tech
735392f7a3SLiteSpeed Tech/* Taken from send_algorithm_interface.h */
745392f7a3SLiteSpeed Tech#define kDefaultMaxCongestionWindowPackets 2000
755392f7a3SLiteSpeed Tech
765392f7a3SLiteSpeed Tech// The time after which the current min_rtt value expires.
775392f7a3SLiteSpeed Tech#define kMinRttExpiry sec(10)
785392f7a3SLiteSpeed Tech
795392f7a3SLiteSpeed Tech// Coefficient to determine if a new RTT is sufficiently similar to min_rtt that
805392f7a3SLiteSpeed Tech// we don't need to enter PROBE_RTT.
815392f7a3SLiteSpeed Tech#define kSimilarMinRttThreshold 1.125f
825392f7a3SLiteSpeed Tech
835392f7a3SLiteSpeed Tech// If the bandwidth does not increase by the factor of |kStartupGrowthTarget|
845392f7a3SLiteSpeed Tech// within |kRoundTripsWithoutGrowthBeforeExitingStartup| rounds, the connection
855392f7a3SLiteSpeed Tech// will exit the STARTUP mode.
865392f7a3SLiteSpeed Tech#define kStartupGrowthTarget 1.25
875392f7a3SLiteSpeed Tech
885392f7a3SLiteSpeed Tech#define kRoundTripsWithoutGrowthBeforeExitingStartup 3
895392f7a3SLiteSpeed Tech
905392f7a3SLiteSpeed Tech#define startup_rate_reduction_multiplier_ 0
915392f7a3SLiteSpeed Tech
925392f7a3SLiteSpeed Tech// The cycle of gains used during the PROBE_BW stage.
935392f7a3SLiteSpeed Techstatic const float kPacingGain[] = {1.25, 0.75, 1, 1, 1, 1, 1, 1};
945392f7a3SLiteSpeed Tech
955392f7a3SLiteSpeed Tech// The length of the gain cycle.
965392f7a3SLiteSpeed Techstatic const size_t kGainCycleLength = sizeof(kPacingGain)
975392f7a3SLiteSpeed Tech                                                    / sizeof(kPacingGain[0]);
985392f7a3SLiteSpeed Tech
995392f7a3SLiteSpeed Tech// Coefficient of target congestion window to use when basing PROBE_RTT on BDP.
1005392f7a3SLiteSpeed Tech#define kModerateProbeRttMultiplier 0.75
1015392f7a3SLiteSpeed Tech
1025392f7a3SLiteSpeed Tech// The maximum packet size of any QUIC packet over IPv6, based on ethernet's max
1035392f7a3SLiteSpeed Tech// size, minus the IP and UDP headers. IPv6 has a 40 byte header, UDP adds an
1045392f7a3SLiteSpeed Tech// additional 8 bytes.  This is a total overhead of 48 bytes.  Ethernet's
1055392f7a3SLiteSpeed Tech// max packet size is 1500 bytes,  1500 - 48 = 1452.
1065392f7a3SLiteSpeed Tech#define kMaxV6PacketSize 1452
1075392f7a3SLiteSpeed Tech// The maximum packet size of any QUIC packet over IPv4.
1085392f7a3SLiteSpeed Tech// 1500(Ethernet) - 20(IPv4 header) - 8(UDP header) = 1472.
1095392f7a3SLiteSpeed Tech#define kMaxV4PacketSize 1472
1105392f7a3SLiteSpeed Tech// The maximum incoming packet size allowed.
1115392f7a3SLiteSpeed Tech#define kMaxIncomingPacketSize kMaxV4PacketSize
1125392f7a3SLiteSpeed Tech// The maximum outgoing packet size allowed.
1135392f7a3SLiteSpeed Tech#define kMaxOutgoingPacketSize kMaxV6PacketSize
1145392f7a3SLiteSpeed Tech
1155392f7a3SLiteSpeed Tech// The minimum time the connection can spend in PROBE_RTT mode.
1165392f7a3SLiteSpeed Tech#define kProbeRttTime ms(200)
1175392f7a3SLiteSpeed Tech
1185392f7a3SLiteSpeed Tech/* FLAG* are from net/quic/quic_flags_list.h */
1195392f7a3SLiteSpeed Tech
1205392f7a3SLiteSpeed Tech// When in STARTUP and recovery, do not add bytes_acked to QUIC BBR's CWND in
1215392f7a3SLiteSpeed Tech// CalculateCongestionWindow()
1225392f7a3SLiteSpeed Tech#define FLAGS_quic_bbr_no_bytes_acked_in_startup_recovery 0
1235392f7a3SLiteSpeed Tech
1245392f7a3SLiteSpeed Tech// When true, ensure BBR allows at least one MSS to be sent in response to an
1255392f7a3SLiteSpeed Tech// ACK in packet conservation.
1265392f7a3SLiteSpeed Tech#define FLAG_quic_bbr_one_mss_conservation 0
1275392f7a3SLiteSpeed Tech
1285392f7a3SLiteSpeed Tech/* From net/quic/quic_flags_list.h */
1295392f7a3SLiteSpeed Tech#define kCwndGain 2.0
1305392f7a3SLiteSpeed Tech
1315392f7a3SLiteSpeed Tech
1325392f7a3SLiteSpeed Techstatic uint64_t lsquic_bbr_get_cwnd (void *);
1335392f7a3SLiteSpeed Tech
1345392f7a3SLiteSpeed Tech
1355392f7a3SLiteSpeed Techstatic const char *const mode2str[] =
1365392f7a3SLiteSpeed Tech{
1375392f7a3SLiteSpeed Tech    [BBR_MODE_STARTUP]   = "STARTUP",
1385392f7a3SLiteSpeed Tech    [BBR_MODE_DRAIN]     = "DRAIN",
1395392f7a3SLiteSpeed Tech    [BBR_MODE_PROBE_BW]  = "PROBE_BW",
1405392f7a3SLiteSpeed Tech    [BBR_MODE_PROBE_RTT] = "PROBE_RTT",
1415392f7a3SLiteSpeed Tech};
1425392f7a3SLiteSpeed Tech
1435392f7a3SLiteSpeed Tech
1445392f7a3SLiteSpeed Techstatic void
1455392f7a3SLiteSpeed Techset_mode (struct lsquic_bbr *bbr, enum bbr_mode mode)
1465392f7a3SLiteSpeed Tech{
1475392f7a3SLiteSpeed Tech    if (bbr->bbr_mode != mode)
1485392f7a3SLiteSpeed Tech    {
1495392f7a3SLiteSpeed Tech        LSQ_DEBUG("mode change %s -> %s", mode2str[bbr->bbr_mode],
1505392f7a3SLiteSpeed Tech                                                        mode2str[mode]);
1515392f7a3SLiteSpeed Tech        bbr->bbr_mode = mode;
1525392f7a3SLiteSpeed Tech    }
1535392f7a3SLiteSpeed Tech    else
1545392f7a3SLiteSpeed Tech        LSQ_DEBUG("mode remains %s", mode2str[mode]);
1555392f7a3SLiteSpeed Tech}
1565392f7a3SLiteSpeed Tech
1575392f7a3SLiteSpeed Tech
1585392f7a3SLiteSpeed Techstatic void
1595392f7a3SLiteSpeed Techset_startup_values (struct lsquic_bbr *bbr)
1605392f7a3SLiteSpeed Tech{
1615392f7a3SLiteSpeed Tech    bbr->bbr_pacing_gain = bbr->bbr_high_gain;
1625392f7a3SLiteSpeed Tech    bbr->bbr_cwnd_gain = bbr->bbr_high_cwnd_gain;
1635392f7a3SLiteSpeed Tech}
1645392f7a3SLiteSpeed Tech
1655392f7a3SLiteSpeed Tech
1665392f7a3SLiteSpeed Techstatic void
1679fc12041SDmitri Tikhonovinit_bbr (struct lsquic_bbr *bbr)
1685392f7a3SLiteSpeed Tech{
1695392f7a3SLiteSpeed Tech    bbr->bbr_mode = BBR_MODE_STARTUP;
1705392f7a3SLiteSpeed Tech    bbr->bbr_round_count = 0;
1715392f7a3SLiteSpeed Tech    minmax_init(&bbr->bbr_max_bandwidth, 10);
1725392f7a3SLiteSpeed Tech    minmax_init(&bbr->bbr_max_ack_height, 10);
1735392f7a3SLiteSpeed Tech    bbr->bbr_aggregation_epoch_bytes = 0;
1745392f7a3SLiteSpeed Tech    bbr->bbr_aggregation_epoch_start_time = 0;
1755392f7a3SLiteSpeed Tech    bbr->bbr_min_rtt = 0;
1765392f7a3SLiteSpeed Tech    bbr->bbr_min_rtt_timestamp = 0;
1775392f7a3SLiteSpeed Tech    bbr->bbr_init_cwnd = kInitialCongestionWindow * kDefaultTCPMSS;
1785392f7a3SLiteSpeed Tech    bbr->bbr_cwnd = kInitialCongestionWindow * kDefaultTCPMSS;
1795392f7a3SLiteSpeed Tech    bbr->bbr_max_cwnd = kDefaultMaxCongestionWindowPackets * kDefaultTCPMSS;
1805392f7a3SLiteSpeed Tech    bbr->bbr_min_cwnd = kDefaultMinimumCongestionWindow;
1815392f7a3SLiteSpeed Tech    bbr->bbr_high_gain = kDefaultHighGain;
1825392f7a3SLiteSpeed Tech    bbr->bbr_high_cwnd_gain = kDefaultHighGain;
183fb3e20e0SDmitri Tikhonov    bbr->bbr_drain_gain = 1.0f / kDefaultHighGain;
1845392f7a3SLiteSpeed Tech    bbr->bbr_pacing_rate = BW_ZERO();
1855392f7a3SLiteSpeed Tech    bbr->bbr_pacing_gain = 1.0;
1865392f7a3SLiteSpeed Tech    bbr->bbr_cwnd_gain = 1.0;
1875392f7a3SLiteSpeed Tech    bbr->bbr_num_startup_rtts = kRoundTripsWithoutGrowthBeforeExitingStartup;
1885392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_EXIT_STARTUP_ON_LOSS;
1895392f7a3SLiteSpeed Tech    bbr->bbr_cycle_current_offset = 0;
1905392f7a3SLiteSpeed Tech    bbr->bbr_last_cycle_start = 0;
1915392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_IS_AT_FULL_BANDWIDTH;
1925392f7a3SLiteSpeed Tech    bbr->bbr_round_wo_bw_gain = 0;
1935392f7a3SLiteSpeed Tech    bbr->bbr_bw_at_last_round = BW_ZERO();
1945392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_EXITING_QUIESCENCE;
1955392f7a3SLiteSpeed Tech    bbr->bbr_exit_probe_rtt_at = 0;
1965392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_PROBE_RTT_ROUND_PASSED;
1975392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_LAST_SAMPLE_APP_LIMITED;
1985392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_HAS_NON_APP_LIMITED;
1995392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_FLEXIBLE_APP_LIMITED;
2005392f7a3SLiteSpeed Tech    set_startup_values(bbr);
2019fc12041SDmitri Tikhonov}
2029fc12041SDmitri Tikhonov
2039fc12041SDmitri Tikhonov
2049fc12041SDmitri Tikhonovstatic void
2059fc12041SDmitri Tikhonovlsquic_bbr_init (void *cong_ctl, const struct lsquic_conn_public *conn_pub,
2069fc12041SDmitri Tikhonov                                                enum quic_ft_bit retx_frames)
2079fc12041SDmitri Tikhonov{
2089fc12041SDmitri Tikhonov    struct lsquic_bbr *const bbr = cong_ctl;
2099fc12041SDmitri Tikhonov    bbr->bbr_conn_pub = conn_pub;
2109fc12041SDmitri Tikhonov    lsquic_bw_sampler_init(&bbr->bbr_bw_sampler, conn_pub->lconn, retx_frames);
2119fc12041SDmitri Tikhonov    bbr->bbr_rtt_stats = &conn_pub->rtt_stats;
2129fc12041SDmitri Tikhonov
2139fc12041SDmitri Tikhonov    init_bbr(bbr);
2145392f7a3SLiteSpeed Tech
2155392f7a3SLiteSpeed Tech    LSQ_DEBUG("initialized");
2165392f7a3SLiteSpeed Tech}
2175392f7a3SLiteSpeed Tech
2185392f7a3SLiteSpeed Tech
2199fc12041SDmitri Tikhonovstatic void
2209fc12041SDmitri Tikhonovlsquic_bbr_reinit (void *cong_ctl)
2219fc12041SDmitri Tikhonov{
2229fc12041SDmitri Tikhonov    struct lsquic_bbr *const bbr = cong_ctl;
2239fc12041SDmitri Tikhonov
2249fc12041SDmitri Tikhonov    init_bbr(bbr);
2259fc12041SDmitri Tikhonov
2269fc12041SDmitri Tikhonov    LSQ_DEBUG("re-initialized");
2279fc12041SDmitri Tikhonov}
2289fc12041SDmitri Tikhonov
2299fc12041SDmitri Tikhonov
2305392f7a3SLiteSpeed Techstatic lsquic_time_t
2315392f7a3SLiteSpeed Techget_min_rtt (const struct lsquic_bbr *bbr)
2325392f7a3SLiteSpeed Tech{
2335392f7a3SLiteSpeed Tech    lsquic_time_t min_rtt;
2345392f7a3SLiteSpeed Tech
2355392f7a3SLiteSpeed Tech    if (bbr->bbr_min_rtt)
2365392f7a3SLiteSpeed Tech        return bbr->bbr_min_rtt;
2375392f7a3SLiteSpeed Tech    else
2385392f7a3SLiteSpeed Tech    {
2395392f7a3SLiteSpeed Tech        min_rtt = lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats);
2405392f7a3SLiteSpeed Tech        if (min_rtt == 0)
2415392f7a3SLiteSpeed Tech            min_rtt = 25000;
2425392f7a3SLiteSpeed Tech        return min_rtt;
2435392f7a3SLiteSpeed Tech    }
2445392f7a3SLiteSpeed Tech}
2455392f7a3SLiteSpeed Tech
2465392f7a3SLiteSpeed Tech
2475392f7a3SLiteSpeed Techstatic uint64_t
2485392f7a3SLiteSpeed Techlsquic_bbr_pacing_rate (void *cong_ctl, int in_recovery)
2495392f7a3SLiteSpeed Tech{
2505392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
2515392f7a3SLiteSpeed Tech    lsquic_time_t min_rtt;
2525392f7a3SLiteSpeed Tech    struct bandwidth bw;
2535392f7a3SLiteSpeed Tech
2545392f7a3SLiteSpeed Tech    if (!BW_IS_ZERO(&bbr->bbr_pacing_rate))
2555392f7a3SLiteSpeed Tech        bw = bbr->bbr_pacing_rate;
2565392f7a3SLiteSpeed Tech    else
2575392f7a3SLiteSpeed Tech    {
2585392f7a3SLiteSpeed Tech        min_rtt = get_min_rtt(bbr);
2595392f7a3SLiteSpeed Tech        bw = BW_FROM_BYTES_AND_DELTA(bbr->bbr_init_cwnd, min_rtt);
2605392f7a3SLiteSpeed Tech        bw = BW_TIMES(&bw, bbr->bbr_high_cwnd_gain);
2615392f7a3SLiteSpeed Tech    }
2625392f7a3SLiteSpeed Tech
2635392f7a3SLiteSpeed Tech    return BW_TO_BYTES_PER_SEC(&bw);
2645392f7a3SLiteSpeed Tech}
2655392f7a3SLiteSpeed Tech
2665392f7a3SLiteSpeed Tech
2675392f7a3SLiteSpeed Tech/* BbrSender::GetTargetCongestionWindow */
2685392f7a3SLiteSpeed Techstatic uint64_t
2695392f7a3SLiteSpeed Techget_target_cwnd (const struct lsquic_bbr *bbr, float gain)
2705392f7a3SLiteSpeed Tech{
2715392f7a3SLiteSpeed Tech    struct bandwidth bw;
2725392f7a3SLiteSpeed Tech    uint64_t bdp, cwnd;
2735392f7a3SLiteSpeed Tech
2745392f7a3SLiteSpeed Tech    bw = BW(minmax_get(&bbr->bbr_max_bandwidth));
2755392f7a3SLiteSpeed Tech    bdp = get_min_rtt(bbr) * BW_TO_BYTES_PER_SEC(&bw) / 1000000;
2765392f7a3SLiteSpeed Tech    cwnd = gain * bdp;
2775392f7a3SLiteSpeed Tech
2785392f7a3SLiteSpeed Tech    // BDP estimate will be zero if no bandwidth samples are available yet.
2795392f7a3SLiteSpeed Tech    if (cwnd == 0)
2805392f7a3SLiteSpeed Tech        cwnd = gain * bbr->bbr_init_cwnd;
2815392f7a3SLiteSpeed Tech
2825392f7a3SLiteSpeed Tech    return MAX(cwnd, bbr->bbr_min_cwnd);
2835392f7a3SLiteSpeed Tech}
2845392f7a3SLiteSpeed Tech
2855392f7a3SLiteSpeed Tech
2865392f7a3SLiteSpeed Tech/* See BbrSender::IsPipeSufficientlyFull */
2875392f7a3SLiteSpeed Techstatic int
2885392f7a3SLiteSpeed Techis_pipe_sufficiently_full (struct lsquic_bbr *bbr, uint64_t bytes_in_flight)
2895392f7a3SLiteSpeed Tech{
2905392f7a3SLiteSpeed Tech    // See if we need more bytes in flight to see more bandwidth.
2915392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_STARTUP)
2925392f7a3SLiteSpeed Tech        // STARTUP exits if it doesn't observe a 25% bandwidth increase, so
2935392f7a3SLiteSpeed Tech        // the CWND must be more than 25% above the target.
2945392f7a3SLiteSpeed Tech        return bytes_in_flight >= get_target_cwnd(bbr, 1.5);
2955392f7a3SLiteSpeed Tech    else if (bbr->bbr_pacing_gain > 1)
2965392f7a3SLiteSpeed Tech        // Super-unity PROBE_BW doesn't exit until 1.25 * BDP is achieved.
2975392f7a3SLiteSpeed Tech        return bytes_in_flight >= get_target_cwnd(bbr, bbr->bbr_pacing_gain);
2985392f7a3SLiteSpeed Tech    else
2995392f7a3SLiteSpeed Tech        // If bytes_in_flight are above the target congestion window, it should
3005392f7a3SLiteSpeed Tech        // be possible to observe the same or more bandwidth if it's available.
301fb3e20e0SDmitri Tikhonov        return bytes_in_flight >= get_target_cwnd(bbr, 1.1f);
3025392f7a3SLiteSpeed Tech}
3035392f7a3SLiteSpeed Tech
3045392f7a3SLiteSpeed Tech
3055392f7a3SLiteSpeed Techstatic void
306cca25415SDmitri Tikhonovlsquic_bbr_was_quiet (void *cong_ctl, lsquic_time_t now, uint64_t in_flight)
3075392f7a3SLiteSpeed Tech{
3085392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
309cca25415SDmitri Tikhonov    LSQ_DEBUG("was quiet");         /* Do nothing */
310cca25415SDmitri Tikhonov}
311cca25415SDmitri Tikhonov
312cca25415SDmitri Tikhonov
313cca25415SDmitri Tikhonov/* See BbrSender::OnApplicationLimited */
314cca25415SDmitri Tikhonovstatic void
315cca25415SDmitri Tikhonovbbr_app_limited (struct lsquic_bbr *bbr, uint64_t bytes_in_flight)
316cca25415SDmitri Tikhonov{
3175392f7a3SLiteSpeed Tech    uint64_t cwnd;
3185392f7a3SLiteSpeed Tech
319cca25415SDmitri Tikhonov    cwnd = lsquic_bbr_get_cwnd(bbr);
3205392f7a3SLiteSpeed Tech    if (bytes_in_flight >= cwnd)
3215392f7a3SLiteSpeed Tech        return;
3225392f7a3SLiteSpeed Tech    if ((bbr->bbr_flags & BBR_FLAG_FLEXIBLE_APP_LIMITED)
3235392f7a3SLiteSpeed Tech                            && is_pipe_sufficiently_full(bbr, bytes_in_flight))
3245392f7a3SLiteSpeed Tech        return;
3255392f7a3SLiteSpeed Tech
3265392f7a3SLiteSpeed Tech    bbr->bbr_flags |= BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT;
3275392f7a3SLiteSpeed Tech    lsquic_bw_sampler_app_limited(&bbr->bbr_bw_sampler);
3285392f7a3SLiteSpeed Tech    LSQ_DEBUG("becoming application-limited.  Last sent packet: %"PRIu64"; "
3295392f7a3SLiteSpeed Tech                            "CWND: %"PRIu64, bbr->bbr_last_sent_packno, cwnd);
3305392f7a3SLiteSpeed Tech}
3315392f7a3SLiteSpeed Tech
3325392f7a3SLiteSpeed Tech
3335392f7a3SLiteSpeed Techstatic void
3345392f7a3SLiteSpeed Techlsquic_bbr_ack (void *cong_ctl, struct lsquic_packet_out *packet_out,
3355392f7a3SLiteSpeed Tech                  unsigned packet_sz, lsquic_time_t now_time, int app_limited)
3365392f7a3SLiteSpeed Tech{
3375392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
3385392f7a3SLiteSpeed Tech    struct bw_sample *sample;
3395392f7a3SLiteSpeed Tech
3405392f7a3SLiteSpeed Tech    assert(bbr->bbr_flags & BBR_FLAG_IN_ACK);
3415392f7a3SLiteSpeed Tech
3425392f7a3SLiteSpeed Tech    sample = lsquic_bw_sampler_packet_acked(&bbr->bbr_bw_sampler, packet_out,
3435392f7a3SLiteSpeed Tech                                                bbr->bbr_ack_state.ack_time);
3445392f7a3SLiteSpeed Tech    if (sample)
3455392f7a3SLiteSpeed Tech        TAILQ_INSERT_TAIL(&bbr->bbr_ack_state.samples, sample, next);
3465392f7a3SLiteSpeed Tech
347bbee242aSDmitri Tikhonov    if (!is_valid_packno(bbr->bbr_ack_state.max_packno)
348bbee242aSDmitri Tikhonov                /* Packet ordering is checked for, and warned about, in
349bbee242aSDmitri Tikhonov                 * lsquic_senhist_add().
350bbee242aSDmitri Tikhonov                 */
351bbee242aSDmitri Tikhonov            || packet_out->po_packno > bbr->bbr_ack_state.max_packno)
352bbee242aSDmitri Tikhonov        bbr->bbr_ack_state.max_packno = packet_out->po_packno;
3535392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.acked_bytes += packet_sz;
3545392f7a3SLiteSpeed Tech}
3555392f7a3SLiteSpeed Tech
3565392f7a3SLiteSpeed Tech
3575392f7a3SLiteSpeed Techstatic void
3585392f7a3SLiteSpeed Techlsquic_bbr_sent (void *cong_ctl, struct lsquic_packet_out *packet_out,
359cca25415SDmitri Tikhonov                                        uint64_t in_flight, int app_limited)
3605392f7a3SLiteSpeed Tech{
3615392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
3625392f7a3SLiteSpeed Tech
3635392f7a3SLiteSpeed Tech    if (!(packet_out->po_flags & PO_MINI))
3645392f7a3SLiteSpeed Tech        lsquic_bw_sampler_packet_sent(&bbr->bbr_bw_sampler, packet_out,
3655392f7a3SLiteSpeed Tech                                                                in_flight);
3665392f7a3SLiteSpeed Tech
3675392f7a3SLiteSpeed Tech    /* Obviously we make an assumption that sent packet number are always
3685392f7a3SLiteSpeed Tech     * increasing.
3695392f7a3SLiteSpeed Tech     */
3705392f7a3SLiteSpeed Tech    bbr->bbr_last_sent_packno = packet_out->po_packno;
371cca25415SDmitri Tikhonov
372cca25415SDmitri Tikhonov    if (app_limited)
373cca25415SDmitri Tikhonov        bbr_app_limited(bbr, in_flight);
3745392f7a3SLiteSpeed Tech}
3755392f7a3SLiteSpeed Tech
3765392f7a3SLiteSpeed Tech
3775392f7a3SLiteSpeed Techstatic void
3785392f7a3SLiteSpeed Techlsquic_bbr_lost (void *cong_ctl, struct lsquic_packet_out *packet_out,
3795392f7a3SLiteSpeed Tech                                                        unsigned packet_sz)
3805392f7a3SLiteSpeed Tech{
3815392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
3825392f7a3SLiteSpeed Tech
3835392f7a3SLiteSpeed Tech    lsquic_bw_sampler_packet_lost(&bbr->bbr_bw_sampler, packet_out);
3845392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.has_losses = 1;
3855392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.lost_bytes += packet_sz;
3865392f7a3SLiteSpeed Tech}
3875392f7a3SLiteSpeed Tech
3885392f7a3SLiteSpeed Tech
3895392f7a3SLiteSpeed Techstatic void
3905392f7a3SLiteSpeed Techlsquic_bbr_begin_ack (void *cong_ctl, lsquic_time_t ack_time, uint64_t in_flight)
3915392f7a3SLiteSpeed Tech{
3925392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
3935392f7a3SLiteSpeed Tech
3945392f7a3SLiteSpeed Tech    assert(!(bbr->bbr_flags & BBR_FLAG_IN_ACK));
3955392f7a3SLiteSpeed Tech    bbr->bbr_flags |= BBR_FLAG_IN_ACK;
3965392f7a3SLiteSpeed Tech    memset(&bbr->bbr_ack_state, 0, sizeof(bbr->bbr_ack_state));
3975392f7a3SLiteSpeed Tech    TAILQ_INIT(&bbr->bbr_ack_state.samples);
3985392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.ack_time = ack_time;
3995392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.max_packno = UINT64_MAX;
4005392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.in_flight = in_flight;
4015392f7a3SLiteSpeed Tech    bbr->bbr_ack_state.total_bytes_acked_before
4025392f7a3SLiteSpeed Tech                        = lsquic_bw_sampler_total_acked(&bbr->bbr_bw_sampler);
4035392f7a3SLiteSpeed Tech}
4045392f7a3SLiteSpeed Tech
4055392f7a3SLiteSpeed Tech
4065392f7a3SLiteSpeed Tech/* Based on BbrSender::ShouldExtendMinRttExpiry() */
4075392f7a3SLiteSpeed Techstatic int
4085392f7a3SLiteSpeed Techshould_extend_min_rtt_expiry (const struct lsquic_bbr *bbr)
4095392f7a3SLiteSpeed Tech{
4105392f7a3SLiteSpeed Tech    int increased_since_last_probe;
4115392f7a3SLiteSpeed Tech
4125392f7a3SLiteSpeed Tech    if ((bbr->bbr_flags & (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT
4135392f7a3SLiteSpeed Tech                          |BBR_FLAG_PROBE_RTT_DISABLED_IF_APP_LIMITED))
4145392f7a3SLiteSpeed Tech            == (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT
4155392f7a3SLiteSpeed Tech               |BBR_FLAG_PROBE_RTT_DISABLED_IF_APP_LIMITED))
4165392f7a3SLiteSpeed Tech        // Extend the current min_rtt if we've been app limited recently.
4175392f7a3SLiteSpeed Tech        return 1;
4185392f7a3SLiteSpeed Tech
4195392f7a3SLiteSpeed Tech    increased_since_last_probe = bbr->bbr_min_rtt_since_last_probe
4205392f7a3SLiteSpeed Tech                                > bbr->bbr_min_rtt * kSimilarMinRttThreshold;
4215392f7a3SLiteSpeed Tech    if ((bbr->bbr_flags & (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT
4225392f7a3SLiteSpeed Tech                          |BBR_FLAG_PROBE_RTT_SKIPPED_IF_SIMILAR_RTT))
4235392f7a3SLiteSpeed Tech            == (BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT
4245392f7a3SLiteSpeed Tech               |BBR_FLAG_PROBE_RTT_SKIPPED_IF_SIMILAR_RTT)
4255392f7a3SLiteSpeed Tech            && !increased_since_last_probe)
4265392f7a3SLiteSpeed Tech        // Extend the current min_rtt if we've been app limited recently and an
4275392f7a3SLiteSpeed Tech        // rtt has been measured in that time that's less than 12.5% more than
4285392f7a3SLiteSpeed Tech        // the current min_rtt.
4295392f7a3SLiteSpeed Tech        return 1;
4305392f7a3SLiteSpeed Tech
4315392f7a3SLiteSpeed Tech    return 0;
4325392f7a3SLiteSpeed Tech}
4335392f7a3SLiteSpeed Tech
4345392f7a3SLiteSpeed Tech
4355392f7a3SLiteSpeed Tech/* Based on BbrSender::UpdateBandwidthAndMinRtt */
4365392f7a3SLiteSpeed Tech/* Returns true if min RTT expired, false otherwise */
4375392f7a3SLiteSpeed Techstatic int
4385392f7a3SLiteSpeed Techupdate_bandwidth_and_min_rtt (struct lsquic_bbr *bbr)
4395392f7a3SLiteSpeed Tech{
4405392f7a3SLiteSpeed Tech    struct bw_sample *sample, *next_sample;
4415392f7a3SLiteSpeed Tech    uint64_t sample_min_rtt;
4425392f7a3SLiteSpeed Tech    int min_rtt_expired;
4435392f7a3SLiteSpeed Tech
4445392f7a3SLiteSpeed Tech    sample_min_rtt = UINT64_MAX;
4455392f7a3SLiteSpeed Tech    for (sample = TAILQ_FIRST(&bbr->bbr_ack_state.samples); sample;
4465392f7a3SLiteSpeed Tech                                                        sample = next_sample)
4475392f7a3SLiteSpeed Tech    {
4485392f7a3SLiteSpeed Tech        next_sample = TAILQ_NEXT(sample, next);
4495392f7a3SLiteSpeed Tech
4505392f7a3SLiteSpeed Tech        if (sample->is_app_limited)
4515392f7a3SLiteSpeed Tech            bbr->bbr_flags |= BBR_FLAG_LAST_SAMPLE_APP_LIMITED;
4525392f7a3SLiteSpeed Tech        else
4535392f7a3SLiteSpeed Tech        {
4545392f7a3SLiteSpeed Tech            bbr->bbr_flags &= ~BBR_FLAG_LAST_SAMPLE_APP_LIMITED;
4555392f7a3SLiteSpeed Tech            bbr->bbr_flags |=  BBR_FLAG_HAS_NON_APP_LIMITED;
4565392f7a3SLiteSpeed Tech        }
4575392f7a3SLiteSpeed Tech
4585392f7a3SLiteSpeed Tech        if (sample_min_rtt == UINT64_MAX || sample->rtt < sample_min_rtt)
4595392f7a3SLiteSpeed Tech            sample_min_rtt = sample->rtt;
4605392f7a3SLiteSpeed Tech
4615392f7a3SLiteSpeed Tech        if (!sample->is_app_limited
4625392f7a3SLiteSpeed Tech                    || BW_VALUE(&sample->bandwidth)
4635392f7a3SLiteSpeed Tech                                    > minmax_get(&bbr->bbr_max_bandwidth))
4645392f7a3SLiteSpeed Tech            minmax_upmax(&bbr->bbr_max_bandwidth, bbr->bbr_round_count,
4655392f7a3SLiteSpeed Tech                                                BW_VALUE(&sample->bandwidth));
4665392f7a3SLiteSpeed Tech
4675392f7a3SLiteSpeed Tech        lsquic_malo_put(sample);
4685392f7a3SLiteSpeed Tech    }
4695392f7a3SLiteSpeed Tech
4705392f7a3SLiteSpeed Tech    if (sample_min_rtt == UINT64_MAX)
4715392f7a3SLiteSpeed Tech        return 0;
4725392f7a3SLiteSpeed Tech
4735392f7a3SLiteSpeed Tech    bbr->bbr_min_rtt_since_last_probe
4745392f7a3SLiteSpeed Tech                    = MIN(bbr->bbr_min_rtt_since_last_probe, sample_min_rtt);
4755392f7a3SLiteSpeed Tech
4765392f7a3SLiteSpeed Tech    min_rtt_expired = bbr->bbr_min_rtt != 0 && (bbr->bbr_ack_state.ack_time
4775392f7a3SLiteSpeed Tech                                > bbr->bbr_min_rtt_timestamp + kMinRttExpiry);
4785392f7a3SLiteSpeed Tech    if (min_rtt_expired || sample_min_rtt < bbr->bbr_min_rtt
4795392f7a3SLiteSpeed Tech                                                    || 0 == bbr->bbr_min_rtt)
4805392f7a3SLiteSpeed Tech    {
4815392f7a3SLiteSpeed Tech        if (min_rtt_expired && should_extend_min_rtt_expiry(bbr))
4825392f7a3SLiteSpeed Tech        {
4835392f7a3SLiteSpeed Tech            LSQ_DEBUG("min rtt expiration extended, stay at: %"PRIu64,
4845392f7a3SLiteSpeed Tech                bbr->bbr_min_rtt);
4855392f7a3SLiteSpeed Tech            min_rtt_expired = 0;
4865392f7a3SLiteSpeed Tech        }
4875392f7a3SLiteSpeed Tech        else
4885392f7a3SLiteSpeed Tech        {
4895392f7a3SLiteSpeed Tech            LSQ_DEBUG("min rtt updated: %"PRIu64" -> %"PRIu64,
4905392f7a3SLiteSpeed Tech                bbr->bbr_min_rtt, sample_min_rtt);
4915392f7a3SLiteSpeed Tech            bbr->bbr_min_rtt = sample_min_rtt;
4925392f7a3SLiteSpeed Tech        }
4935392f7a3SLiteSpeed Tech        bbr->bbr_min_rtt_timestamp = bbr->bbr_ack_state.ack_time;
4945392f7a3SLiteSpeed Tech        bbr->bbr_min_rtt_since_last_probe = UINT64_MAX;
4955392f7a3SLiteSpeed Tech        bbr->bbr_flags &= ~BBR_FLAG_APP_LIMITED_SINCE_LAST_PROBE_RTT;
4965392f7a3SLiteSpeed Tech    }
4975392f7a3SLiteSpeed Tech
4985392f7a3SLiteSpeed Tech    return min_rtt_expired;
4995392f7a3SLiteSpeed Tech}
5005392f7a3SLiteSpeed Tech
5015392f7a3SLiteSpeed Tech
5025392f7a3SLiteSpeed Tech/* Based on BbrSender::UpdateRecoveryState() */
5035392f7a3SLiteSpeed Techstatic void
5045392f7a3SLiteSpeed Techupdate_recovery_state (struct lsquic_bbr *bbr, int is_round_start)
5055392f7a3SLiteSpeed Tech{
5065392f7a3SLiteSpeed Tech    // Exit recovery when there are no losses for a round.
5075392f7a3SLiteSpeed Tech    if (bbr->bbr_ack_state.has_losses)
5085392f7a3SLiteSpeed Tech        bbr->bbr_end_recovery_at = bbr->bbr_last_sent_packno;
5095392f7a3SLiteSpeed Tech
5105392f7a3SLiteSpeed Tech    switch (bbr->bbr_recovery_state)
5115392f7a3SLiteSpeed Tech    {
5125392f7a3SLiteSpeed Tech    case BBR_RS_NOT_IN_RECOVERY:
5135392f7a3SLiteSpeed Tech        // Enter conservation on the first loss.
5145392f7a3SLiteSpeed Tech        if (bbr->bbr_ack_state.has_losses)
5155392f7a3SLiteSpeed Tech        {
5165392f7a3SLiteSpeed Tech            bbr->bbr_recovery_state = BBR_RS_CONSERVATION;
5175392f7a3SLiteSpeed Tech            // This will cause the |bbr_recovery_window| to be set to the
5185392f7a3SLiteSpeed Tech            // correct value in CalculateRecoveryWindow().
5195392f7a3SLiteSpeed Tech            bbr->bbr_recovery_window = 0;
5205392f7a3SLiteSpeed Tech            // Since the conservation phase is meant to be lasting for a whole
5215392f7a3SLiteSpeed Tech            // round, extend the current round as if it were started right now.
5225392f7a3SLiteSpeed Tech            bbr->bbr_current_round_trip_end = bbr->bbr_last_sent_packno;
5235392f7a3SLiteSpeed Tech        }
5245392f7a3SLiteSpeed Tech        break;
5255392f7a3SLiteSpeed Tech    case BBR_RS_CONSERVATION:
5265392f7a3SLiteSpeed Tech        if (is_round_start)
5275392f7a3SLiteSpeed Tech            bbr->bbr_recovery_state = BBR_RS_GROWTH;
5285392f7a3SLiteSpeed Tech        /* Fall-through */
5295392f7a3SLiteSpeed Tech    case BBR_RS_GROWTH:
5305392f7a3SLiteSpeed Tech        // Exit recovery if appropriate.
5315392f7a3SLiteSpeed Tech        if (!bbr->bbr_ack_state.has_losses
5325392f7a3SLiteSpeed Tech                && bbr->bbr_ack_state.max_packno > bbr->bbr_end_recovery_at)
5335392f7a3SLiteSpeed Tech            bbr->bbr_recovery_state = BBR_RS_NOT_IN_RECOVERY;
5345392f7a3SLiteSpeed Tech        break;
5355392f7a3SLiteSpeed Tech    }
5365392f7a3SLiteSpeed Tech}
5375392f7a3SLiteSpeed Tech
5385392f7a3SLiteSpeed Tech
5395392f7a3SLiteSpeed Techstatic uint64_t
5405392f7a3SLiteSpeed Techupdate_ack_aggregation_bytes (struct lsquic_bbr *bbr,
5415392f7a3SLiteSpeed Tech                                                uint64_t newly_acked_bytes)
5425392f7a3SLiteSpeed Tech{
5435392f7a3SLiteSpeed Tech    const lsquic_time_t ack_time = bbr->bbr_ack_state.ack_time;
5445392f7a3SLiteSpeed Tech    uint64_t expected_bytes_acked, diff;
5455392f7a3SLiteSpeed Tech
5465392f7a3SLiteSpeed Tech    // Compute how many bytes are expected to be delivered, assuming max
5475392f7a3SLiteSpeed Tech    // bandwidth is correct.
5485392f7a3SLiteSpeed Tech    expected_bytes_acked = minmax_get(&bbr->bbr_max_bandwidth)
5495392f7a3SLiteSpeed Tech                        * (ack_time - bbr->bbr_aggregation_epoch_start_time);
5505392f7a3SLiteSpeed Tech
5515392f7a3SLiteSpeed Tech    // Reset the current aggregation epoch as soon as the ack arrival rate is
5525392f7a3SLiteSpeed Tech    // less than or equal to the max bandwidth.
5535392f7a3SLiteSpeed Tech    if (bbr->bbr_aggregation_epoch_bytes <= expected_bytes_acked)
5545392f7a3SLiteSpeed Tech    {
5555392f7a3SLiteSpeed Tech        // Reset to start measuring a new aggregation epoch.
5565392f7a3SLiteSpeed Tech        bbr->bbr_aggregation_epoch_bytes = newly_acked_bytes;
5575392f7a3SLiteSpeed Tech        bbr->bbr_aggregation_epoch_start_time = ack_time;
5585392f7a3SLiteSpeed Tech        return 0;
5595392f7a3SLiteSpeed Tech    }
5605392f7a3SLiteSpeed Tech
5615392f7a3SLiteSpeed Tech    // Compute how many extra bytes were delivered vs max bandwidth.
5625392f7a3SLiteSpeed Tech    // Include the bytes most recently acknowledged to account for stretch acks.
5635392f7a3SLiteSpeed Tech    bbr->bbr_aggregation_epoch_bytes += newly_acked_bytes;
5645392f7a3SLiteSpeed Tech    diff = bbr->bbr_aggregation_epoch_bytes - expected_bytes_acked;
5655392f7a3SLiteSpeed Tech    minmax_upmax(&bbr->bbr_max_ack_height, bbr->bbr_round_count, diff);
5665392f7a3SLiteSpeed Tech    return diff;
5675392f7a3SLiteSpeed Tech}
5685392f7a3SLiteSpeed Tech
5695392f7a3SLiteSpeed Tech
5705392f7a3SLiteSpeed Tech/* See BbrSender::UpdateGainCyclePhase() */
5715392f7a3SLiteSpeed Techstatic void
5725392f7a3SLiteSpeed Techupdate_gain_cycle_phase (struct lsquic_bbr *bbr, uint64_t bytes_in_flight)
5735392f7a3SLiteSpeed Tech{
5745392f7a3SLiteSpeed Tech    const uint64_t prior_in_flight = bbr->bbr_ack_state.in_flight;
5755392f7a3SLiteSpeed Tech    const lsquic_time_t now = bbr->bbr_ack_state.ack_time;
5765392f7a3SLiteSpeed Tech    // In most cases, the cycle is advanced after an RTT passes.
5775392f7a3SLiteSpeed Tech    int should_advance_gain_cycling
5785392f7a3SLiteSpeed Tech        = now - bbr->bbr_last_cycle_start > get_min_rtt(bbr);
5795392f7a3SLiteSpeed Tech
5805392f7a3SLiteSpeed Tech    // If the pacing gain is above 1.0, the connection is trying to probe the
5815392f7a3SLiteSpeed Tech    // bandwidth by increasing the number of bytes in flight to at least
5825392f7a3SLiteSpeed Tech    // pacing_gain * BDP.  Make sure that it actually reaches the target, as
5835392f7a3SLiteSpeed Tech    // long as there are no losses suggesting that the buffers are not able to
5845392f7a3SLiteSpeed Tech    // hold that much.
5855392f7a3SLiteSpeed Tech    if (bbr->bbr_pacing_gain > 1.0
5865392f7a3SLiteSpeed Tech            && !bbr->bbr_ack_state.has_losses
5875392f7a3SLiteSpeed Tech            && prior_in_flight < get_target_cwnd(bbr, bbr->bbr_pacing_gain))
5885392f7a3SLiteSpeed Tech        should_advance_gain_cycling = 0;
5895392f7a3SLiteSpeed Tech
5905392f7a3SLiteSpeed Tech    /* Several optimizations are possible here: "else if" instead of "if", as
5915392f7a3SLiteSpeed Tech     * well as not calling get_target_cwnd() if `should_advance_gain_cycling'
5925392f7a3SLiteSpeed Tech     * is already set to the target value.
5935392f7a3SLiteSpeed Tech     */
5945392f7a3SLiteSpeed Tech
5955392f7a3SLiteSpeed Tech    // If pacing gain is below 1.0, the connection is trying to drain the extra
5965392f7a3SLiteSpeed Tech    // queue which could have been incurred by probing prior to it.  If the
5975392f7a3SLiteSpeed Tech    // number of bytes in flight falls down to the estimated BDP value earlier,
5985392f7a3SLiteSpeed Tech    // conclude that the queue has been successfully drained and exit this cycle
5995392f7a3SLiteSpeed Tech    // early.
6005392f7a3SLiteSpeed Tech    if (bbr->bbr_pacing_gain < 1.0
6015392f7a3SLiteSpeed Tech                                && bytes_in_flight <= get_target_cwnd(bbr, 1))
6025392f7a3SLiteSpeed Tech        should_advance_gain_cycling = 1;
6035392f7a3SLiteSpeed Tech
6045392f7a3SLiteSpeed Tech    if (should_advance_gain_cycling)
6055392f7a3SLiteSpeed Tech    {
6065392f7a3SLiteSpeed Tech        bbr->bbr_cycle_current_offset =
6075392f7a3SLiteSpeed Tech                        (bbr->bbr_cycle_current_offset + 1) % kGainCycleLength;
6085392f7a3SLiteSpeed Tech        bbr->bbr_last_cycle_start = now;
6095392f7a3SLiteSpeed Tech        // Stay in low gain mode until the target BDP is hit.  Low gain mode
6105392f7a3SLiteSpeed Tech        // will be exited immediately when the target BDP is achieved.
6115392f7a3SLiteSpeed Tech        if ((bbr->bbr_flags & BBR_FLAG_DRAIN_TO_TARGET)
6125392f7a3SLiteSpeed Tech                && bbr->bbr_pacing_gain < 1
6135392f7a3SLiteSpeed Tech                && kPacingGain[bbr->bbr_cycle_current_offset] == 1
6145392f7a3SLiteSpeed Tech                && bytes_in_flight > get_target_cwnd(bbr, 1))
6155392f7a3SLiteSpeed Tech              return;
6165392f7a3SLiteSpeed Tech        bbr->bbr_pacing_gain = kPacingGain[bbr->bbr_cycle_current_offset];
6175392f7a3SLiteSpeed Tech        LSQ_DEBUG("advanced gain cycle, pacing gain set to %.2f",
6185392f7a3SLiteSpeed Tech                                                        bbr->bbr_pacing_gain);
6195392f7a3SLiteSpeed Tech    }
6205392f7a3SLiteSpeed Tech}
6215392f7a3SLiteSpeed Tech
6225392f7a3SLiteSpeed Tech
6235392f7a3SLiteSpeed Tech/* BbrSender::InRecovery() */
6245392f7a3SLiteSpeed Techstatic int
6255392f7a3SLiteSpeed Techin_recovery (const struct lsquic_bbr *bbr)
6265392f7a3SLiteSpeed Tech{
6275392f7a3SLiteSpeed Tech    return bbr->bbr_recovery_state != BBR_RS_NOT_IN_RECOVERY;
6285392f7a3SLiteSpeed Tech}
6295392f7a3SLiteSpeed Tech
6305392f7a3SLiteSpeed Tech
6315392f7a3SLiteSpeed Tech/* See BbrSender::CheckIfFullBandwidthReached() */
6325392f7a3SLiteSpeed Techstatic void
6335392f7a3SLiteSpeed Techcheck_if_full_bw_reached (struct lsquic_bbr *bbr)
6345392f7a3SLiteSpeed Tech{
6355392f7a3SLiteSpeed Tech    struct bandwidth target, bw;
6365392f7a3SLiteSpeed Tech
6375392f7a3SLiteSpeed Tech    if (bbr->bbr_flags & BBR_FLAG_LAST_SAMPLE_APP_LIMITED)
6385392f7a3SLiteSpeed Tech    {
6395392f7a3SLiteSpeed Tech        LSQ_DEBUG("last sample app limited: full BW not reached");
6405392f7a3SLiteSpeed Tech        return;
6415392f7a3SLiteSpeed Tech    }
6425392f7a3SLiteSpeed Tech
6435392f7a3SLiteSpeed Tech    target = BW_TIMES(&bbr->bbr_bw_at_last_round, kStartupGrowthTarget);
6445392f7a3SLiteSpeed Tech    bw = BW(minmax_get(&bbr->bbr_max_bandwidth));
6455392f7a3SLiteSpeed Tech    if (BW_VALUE(&bw) >= BW_VALUE(&target))
6465392f7a3SLiteSpeed Tech    {
6475392f7a3SLiteSpeed Tech        bbr->bbr_bw_at_last_round = bw;
6485392f7a3SLiteSpeed Tech        bbr->bbr_round_wo_bw_gain = 0;
6495392f7a3SLiteSpeed Tech        if (bbr->bbr_flags & BBR_FLAG_EXPIRE_ACK_AGG_IN_STARTUP)
6505392f7a3SLiteSpeed Tech            // Expire old excess delivery measurements now that bandwidth
6515392f7a3SLiteSpeed Tech            // increased.
6525392f7a3SLiteSpeed Tech            minmax_reset(&bbr->bbr_max_ack_height,
6535392f7a3SLiteSpeed Tech                        ((struct minmax_sample) { bbr->bbr_round_count, 0, }));
6545392f7a3SLiteSpeed Tech        LSQ_DEBUG("BW estimate %"PRIu64"bps greater than or equal to target "
6555392f7a3SLiteSpeed Tech            "%"PRIu64"bps: full BW not reached",
6565392f7a3SLiteSpeed Tech            BW_VALUE(&bw), BW_VALUE(&target));
6575392f7a3SLiteSpeed Tech        return;
6585392f7a3SLiteSpeed Tech    }
6595392f7a3SLiteSpeed Tech
6605392f7a3SLiteSpeed Tech    ++bbr->bbr_round_wo_bw_gain;
6615392f7a3SLiteSpeed Tech    if ((bbr->bbr_round_wo_bw_gain >= bbr->bbr_num_startup_rtts)
6625392f7a3SLiteSpeed Tech            || ((bbr->bbr_flags & BBR_FLAG_EXIT_STARTUP_ON_LOSS)
6635392f7a3SLiteSpeed Tech                                                    && in_recovery(bbr)))
6645392f7a3SLiteSpeed Tech    {
6655392f7a3SLiteSpeed Tech        assert(bbr->bbr_flags & BBR_FLAG_HAS_NON_APP_LIMITED);  /* DCHECK */
6665392f7a3SLiteSpeed Tech        bbr->bbr_flags |= BBR_FLAG_IS_AT_FULL_BANDWIDTH;
6675392f7a3SLiteSpeed Tech        LSQ_DEBUG("reached full BW");
6685392f7a3SLiteSpeed Tech    }
6695392f7a3SLiteSpeed Tech    else
6705392f7a3SLiteSpeed Tech        LSQ_DEBUG("rounds w/o gain: %u, full BW not reached",
6715392f7a3SLiteSpeed Tech                                                bbr->bbr_round_wo_bw_gain);
6725392f7a3SLiteSpeed Tech}
6735392f7a3SLiteSpeed Tech
6745392f7a3SLiteSpeed Tech
6755392f7a3SLiteSpeed Tech/* See BbrSender::OnExitStartup */
6765392f7a3SLiteSpeed Techstatic void
6775392f7a3SLiteSpeed Techon_exit_startup (struct lsquic_bbr *bbr, lsquic_time_t now)
6785392f7a3SLiteSpeed Tech{
6795392f7a3SLiteSpeed Tech    assert(bbr->bbr_mode == BBR_MODE_STARTUP);
6805392f7a3SLiteSpeed Tech    /* Apparently this method is just to update stats, something that we
6815392f7a3SLiteSpeed Tech     * don't do yet.
6825392f7a3SLiteSpeed Tech     */
6835392f7a3SLiteSpeed Tech}
6845392f7a3SLiteSpeed Tech
6855392f7a3SLiteSpeed Tech
6865392f7a3SLiteSpeed Tech/* See BbrSender::EnterProbeBandwidthMode */
6875392f7a3SLiteSpeed Techstatic void
6885392f7a3SLiteSpeed Techenter_probe_bw_mode (struct lsquic_bbr *bbr, lsquic_time_t now)
6895392f7a3SLiteSpeed Tech{
69010c41073SDmitri Tikhonov    uint8_t rand;
69110c41073SDmitri Tikhonov
6925392f7a3SLiteSpeed Tech    set_mode(bbr, BBR_MODE_PROBE_BW);
6935392f7a3SLiteSpeed Tech    bbr->bbr_cwnd_gain = kCwndGain;
6945392f7a3SLiteSpeed Tech
6955392f7a3SLiteSpeed Tech    // Pick a random offset for the gain cycle out of {0, 2..7} range. 1 is
6965392f7a3SLiteSpeed Tech    // excluded because in that case increased gain and decreased gain would not
6975392f7a3SLiteSpeed Tech    // follow each other.
69810c41073SDmitri Tikhonov    rand = lsquic_crand_get_byte(bbr->bbr_conn_pub->enpub->enp_crand);
69910c41073SDmitri Tikhonov    bbr->bbr_cycle_current_offset = rand % (kGainCycleLength - 1);
7005392f7a3SLiteSpeed Tech    if (bbr->bbr_cycle_current_offset >= 1)
7015392f7a3SLiteSpeed Tech        ++bbr->bbr_cycle_current_offset;
7025392f7a3SLiteSpeed Tech
7035392f7a3SLiteSpeed Tech    bbr->bbr_last_cycle_start = now;
7045392f7a3SLiteSpeed Tech    bbr->bbr_pacing_gain = kPacingGain[bbr->bbr_cycle_current_offset];
7055392f7a3SLiteSpeed Tech}
7065392f7a3SLiteSpeed Tech
7075392f7a3SLiteSpeed Tech
7085392f7a3SLiteSpeed Tech/* See BbrSender::EnterStartupMode */
7095392f7a3SLiteSpeed Techstatic void
7105392f7a3SLiteSpeed Techenter_startup_mode (struct lsquic_bbr *bbr, lsquic_time_t now)
7115392f7a3SLiteSpeed Tech{
7125392f7a3SLiteSpeed Tech    set_mode(bbr, BBR_MODE_STARTUP);
7135392f7a3SLiteSpeed Tech    set_startup_values(bbr);
7145392f7a3SLiteSpeed Tech}
7155392f7a3SLiteSpeed Tech
7165392f7a3SLiteSpeed Tech
7175392f7a3SLiteSpeed Tech/* See  BbrSender::MaybeExitStartupOrDrain() */
7185392f7a3SLiteSpeed Techstatic void
7195392f7a3SLiteSpeed Techmaybe_exit_startup_or_drain (struct lsquic_bbr *bbr, lsquic_time_t now,
7205392f7a3SLiteSpeed Tech                                                    uint64_t bytes_in_flight)
7215392f7a3SLiteSpeed Tech{
7225392f7a3SLiteSpeed Tech    uint64_t target_cwnd;
7235392f7a3SLiteSpeed Tech
7245392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_STARTUP
7255392f7a3SLiteSpeed Tech                        && (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH))
7265392f7a3SLiteSpeed Tech    {
7275392f7a3SLiteSpeed Tech        on_exit_startup(bbr, now);
7285392f7a3SLiteSpeed Tech        set_mode(bbr, BBR_MODE_DRAIN);
7295392f7a3SLiteSpeed Tech        bbr->bbr_pacing_gain = bbr->bbr_drain_gain;
7305392f7a3SLiteSpeed Tech        bbr->bbr_cwnd_gain = bbr->bbr_high_cwnd_gain;
7315392f7a3SLiteSpeed Tech    }
7325392f7a3SLiteSpeed Tech
7335392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_DRAIN)
7345392f7a3SLiteSpeed Tech    {
7355392f7a3SLiteSpeed Tech        target_cwnd = get_target_cwnd(bbr, 1);
7365392f7a3SLiteSpeed Tech        LSQ_DEBUG("%s: bytes in flight: %"PRIu64"; target cwnd: %"PRIu64,
7375392f7a3SLiteSpeed Tech                                    __func__, bytes_in_flight, target_cwnd);
7385392f7a3SLiteSpeed Tech        if (bytes_in_flight <= target_cwnd)
7395392f7a3SLiteSpeed Tech            enter_probe_bw_mode(bbr, now);
7405392f7a3SLiteSpeed Tech    }
7415392f7a3SLiteSpeed Tech}
7425392f7a3SLiteSpeed Tech
7435392f7a3SLiteSpeed Tech
7445392f7a3SLiteSpeed Techstatic int
7455392f7a3SLiteSpeed Techin_slow_start (const struct lsquic_bbr *bbr)
7465392f7a3SLiteSpeed Tech{
7475392f7a3SLiteSpeed Tech    return bbr->bbr_mode == BBR_MODE_STARTUP;
7485392f7a3SLiteSpeed Tech}
7495392f7a3SLiteSpeed Tech
7505392f7a3SLiteSpeed Tech
7515392f7a3SLiteSpeed Tech/* See QuicByteCount BbrSender::ProbeRttCongestionWindow() */
7525392f7a3SLiteSpeed Techstatic uint64_t
7535392f7a3SLiteSpeed Techget_probe_rtt_cwnd (const struct lsquic_bbr *bbr)
7545392f7a3SLiteSpeed Tech{
7555392f7a3SLiteSpeed Tech    if (bbr->bbr_flags & BBR_FLAG_PROBE_RTT_BASED_ON_BDP)
7565392f7a3SLiteSpeed Tech        return get_target_cwnd(bbr, kModerateProbeRttMultiplier);
7575392f7a3SLiteSpeed Tech    else
7585392f7a3SLiteSpeed Tech        return bbr->bbr_min_cwnd;
7595392f7a3SLiteSpeed Tech}
7605392f7a3SLiteSpeed Tech
7615392f7a3SLiteSpeed Tech
7625392f7a3SLiteSpeed Techstatic uint64_t
7635392f7a3SLiteSpeed Techlsquic_bbr_get_cwnd (void *cong_ctl)
7645392f7a3SLiteSpeed Tech{
7655392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
7665392f7a3SLiteSpeed Tech    uint64_t cwnd;
7675392f7a3SLiteSpeed Tech
7685392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_PROBE_RTT)
7695392f7a3SLiteSpeed Tech        cwnd = get_probe_rtt_cwnd(bbr);
7705392f7a3SLiteSpeed Tech    else if (in_recovery(bbr) &&
7715392f7a3SLiteSpeed Tech                !((bbr->bbr_flags & BBR_FLAG_RATE_BASED_STARTUP)
7725392f7a3SLiteSpeed Tech                                    && bbr->bbr_mode == BBR_MODE_STARTUP))
7735392f7a3SLiteSpeed Tech        cwnd = MIN(bbr->bbr_cwnd, bbr->bbr_recovery_window);
7745392f7a3SLiteSpeed Tech    else
7755392f7a3SLiteSpeed Tech        cwnd = bbr->bbr_cwnd;
7765392f7a3SLiteSpeed Tech
7775392f7a3SLiteSpeed Tech    return cwnd;
7785392f7a3SLiteSpeed Tech}
7795392f7a3SLiteSpeed Tech
7805392f7a3SLiteSpeed Tech
7815392f7a3SLiteSpeed Tech/* See BbrSender::MaybeEnterOrExitProbeRtt */
7825392f7a3SLiteSpeed Techstatic void
7835392f7a3SLiteSpeed Techmaybe_enter_or_exit_probe_rtt (struct lsquic_bbr *bbr, lsquic_time_t now,
7845392f7a3SLiteSpeed Tech            int is_round_start, int min_rtt_expired, uint64_t bytes_in_flight)
7855392f7a3SLiteSpeed Tech{
7865392f7a3SLiteSpeed Tech    if (min_rtt_expired
7875392f7a3SLiteSpeed Tech            && !(bbr->bbr_flags & BBR_FLAG_EXITING_QUIESCENCE)
7885392f7a3SLiteSpeed Tech                && bbr->bbr_mode != BBR_MODE_PROBE_RTT)
7895392f7a3SLiteSpeed Tech    {
7905392f7a3SLiteSpeed Tech        if (in_slow_start(bbr))
7915392f7a3SLiteSpeed Tech            on_exit_startup(bbr, now);
7925392f7a3SLiteSpeed Tech        set_mode(bbr, BBR_MODE_PROBE_RTT);
7935392f7a3SLiteSpeed Tech        bbr->bbr_pacing_gain = 1;
7945392f7a3SLiteSpeed Tech        // Do not decide on the time to exit PROBE_RTT until the
7955392f7a3SLiteSpeed Tech        // |bytes_in_flight| is at the target small value.
7965392f7a3SLiteSpeed Tech        bbr->bbr_exit_probe_rtt_at = 0;
7975392f7a3SLiteSpeed Tech    }
7985392f7a3SLiteSpeed Tech
7995392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_PROBE_RTT)
8005392f7a3SLiteSpeed Tech    {
8015392f7a3SLiteSpeed Tech        lsquic_bw_sampler_app_limited(&bbr->bbr_bw_sampler);
8025392f7a3SLiteSpeed Tech        LSQ_DEBUG("%s: exit probe at: %"PRIu64"; now: %"PRIu64
8035392f7a3SLiteSpeed Tech            "; round start: %d; round passed: %d; rtt: %"PRIu64" usec",
8045392f7a3SLiteSpeed Tech            __func__, bbr->bbr_exit_probe_rtt_at, now, is_round_start,
8055392f7a3SLiteSpeed Tech            !!(bbr->bbr_flags & BBR_FLAG_PROBE_RTT_ROUND_PASSED),
8065392f7a3SLiteSpeed Tech            lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats));
8075392f7a3SLiteSpeed Tech        if (bbr->bbr_exit_probe_rtt_at == 0)
8085392f7a3SLiteSpeed Tech        {
8095392f7a3SLiteSpeed Tech            // If the window has reached the appropriate size, schedule exiting
8105392f7a3SLiteSpeed Tech            // PROBE_RTT.  The CWND during PROBE_RTT is
8115392f7a3SLiteSpeed Tech            // kMinimumCongestionWindow, but we allow an extra packet since QUIC
8125392f7a3SLiteSpeed Tech            // checks CWND before sending a packet.
8135392f7a3SLiteSpeed Tech            if (bytes_in_flight
8145392f7a3SLiteSpeed Tech                        < get_probe_rtt_cwnd(bbr) + kMaxOutgoingPacketSize)
8155392f7a3SLiteSpeed Tech            {
8165392f7a3SLiteSpeed Tech                bbr->bbr_exit_probe_rtt_at = now + kProbeRttTime;
8175392f7a3SLiteSpeed Tech                bbr->bbr_flags &= ~BBR_FLAG_PROBE_RTT_ROUND_PASSED;
8185392f7a3SLiteSpeed Tech            }
8195392f7a3SLiteSpeed Tech        }
8205392f7a3SLiteSpeed Tech        else
8215392f7a3SLiteSpeed Tech        {
8225392f7a3SLiteSpeed Tech            if (is_round_start)
8235392f7a3SLiteSpeed Tech                bbr->bbr_flags |= BBR_FLAG_PROBE_RTT_ROUND_PASSED;
8245392f7a3SLiteSpeed Tech            if (now >= bbr->bbr_exit_probe_rtt_at
8255392f7a3SLiteSpeed Tech                        && (bbr->bbr_flags & BBR_FLAG_PROBE_RTT_ROUND_PASSED))
8265392f7a3SLiteSpeed Tech            {
8275392f7a3SLiteSpeed Tech                bbr->bbr_min_rtt_timestamp = now;
8285392f7a3SLiteSpeed Tech                if (!(bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH))
8295392f7a3SLiteSpeed Tech                    enter_startup_mode(bbr, now);
8305392f7a3SLiteSpeed Tech                else
8315392f7a3SLiteSpeed Tech                    enter_probe_bw_mode(bbr, now);
8325392f7a3SLiteSpeed Tech            }
8335392f7a3SLiteSpeed Tech        }
8345392f7a3SLiteSpeed Tech    }
8355392f7a3SLiteSpeed Tech
8365392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_EXITING_QUIESCENCE;
8375392f7a3SLiteSpeed Tech}
8385392f7a3SLiteSpeed Tech
8395392f7a3SLiteSpeed Tech
8405392f7a3SLiteSpeed Tech/* See BbrSender::CalculatePacingRate */
8415392f7a3SLiteSpeed Techstatic void
8425392f7a3SLiteSpeed Techcalculate_pacing_rate (struct lsquic_bbr *bbr)
8435392f7a3SLiteSpeed Tech{
8445392f7a3SLiteSpeed Tech    struct bandwidth bw, target_rate;
8455392f7a3SLiteSpeed Tech
8465392f7a3SLiteSpeed Tech    bw = BW(minmax_get(&bbr->bbr_max_bandwidth));
8475392f7a3SLiteSpeed Tech    if (BW_IS_ZERO(&bw))
8485392f7a3SLiteSpeed Tech        return;
8495392f7a3SLiteSpeed Tech
8505392f7a3SLiteSpeed Tech    LSQ_DEBUG("BW estimate: %"PRIu64, BW_VALUE(&bw));
8515392f7a3SLiteSpeed Tech
8525392f7a3SLiteSpeed Tech    target_rate = BW_TIMES(&bw, bbr->bbr_pacing_gain);
8535392f7a3SLiteSpeed Tech    if (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH)
8545392f7a3SLiteSpeed Tech    {
8555392f7a3SLiteSpeed Tech        bbr->bbr_pacing_rate = target_rate;
8565392f7a3SLiteSpeed Tech        return;
8575392f7a3SLiteSpeed Tech    }
8585392f7a3SLiteSpeed Tech
8595392f7a3SLiteSpeed Tech    // Pace at the rate of initial_window / RTT as soon as RTT measurements are
8605392f7a3SLiteSpeed Tech    // available.
8615392f7a3SLiteSpeed Tech    if (BW_IS_ZERO(&bbr->bbr_pacing_rate)
8625392f7a3SLiteSpeed Tech            && 0 != lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats))
8635392f7a3SLiteSpeed Tech    {
8645392f7a3SLiteSpeed Tech        bbr->bbr_pacing_rate = BW_FROM_BYTES_AND_DELTA(
8655392f7a3SLiteSpeed Tech            bbr->bbr_init_cwnd,
8665392f7a3SLiteSpeed Tech            lsquic_rtt_stats_get_min_rtt(bbr->bbr_rtt_stats));
8675392f7a3SLiteSpeed Tech        return;
8685392f7a3SLiteSpeed Tech    }
8695392f7a3SLiteSpeed Tech
8705392f7a3SLiteSpeed Tech    // Slow the pacing rate in STARTUP once loss has ever been detected.
8715392f7a3SLiteSpeed Tech    const int has_ever_detected_loss = bbr->bbr_end_recovery_at != 0;
8725392f7a3SLiteSpeed Tech    if (has_ever_detected_loss
8735392f7a3SLiteSpeed Tech            && (bbr->bbr_flags & (BBR_FLAG_SLOWER_STARTUP
8745392f7a3SLiteSpeed Tech                                  |BBR_FLAG_HAS_NON_APP_LIMITED))
8755392f7a3SLiteSpeed Tech                == (BBR_FLAG_SLOWER_STARTUP|BBR_FLAG_HAS_NON_APP_LIMITED))
8765392f7a3SLiteSpeed Tech    {
8775392f7a3SLiteSpeed Tech        bbr->bbr_pacing_rate = BW_TIMES(&bw, kStartupAfterLossGain);
8785392f7a3SLiteSpeed Tech        return;
8795392f7a3SLiteSpeed Tech    }
8805392f7a3SLiteSpeed Tech
8815392f7a3SLiteSpeed Tech    // Slow the pacing rate in STARTUP by the bytes_lost / CWND.
8825392f7a3SLiteSpeed Tech    if (startup_rate_reduction_multiplier_ != 0
8835392f7a3SLiteSpeed Tech            && has_ever_detected_loss
8845392f7a3SLiteSpeed Tech                && (bbr->bbr_flags & BBR_FLAG_HAS_NON_APP_LIMITED))
8855392f7a3SLiteSpeed Tech    {
8865392f7a3SLiteSpeed Tech        bbr->bbr_pacing_rate = BW_TIMES(&target_rate,
8875392f7a3SLiteSpeed Tech            (1 - (bbr->bbr_startup_bytes_lost
8885392f7a3SLiteSpeed Tech                    * startup_rate_reduction_multiplier_ * 1.0f
8895392f7a3SLiteSpeed Tech                        / bbr->bbr_cwnd_gain)));
8905392f7a3SLiteSpeed Tech        // Ensure the pacing rate doesn't drop below the startup growth target
8915392f7a3SLiteSpeed Tech        // times  the bandwidth estimate.
8925392f7a3SLiteSpeed Tech        if (BW_VALUE(&bbr->bbr_pacing_rate)
8935392f7a3SLiteSpeed Tech                                        < BW_VALUE(&bw) * kStartupGrowthTarget)
8945392f7a3SLiteSpeed Tech            bbr->bbr_pacing_rate = BW_TIMES(&bw, kStartupGrowthTarget);
8955392f7a3SLiteSpeed Tech        return;
8965392f7a3SLiteSpeed Tech    }
8975392f7a3SLiteSpeed Tech
8985392f7a3SLiteSpeed Tech    // Do not decrease the pacing rate during startup.
8995392f7a3SLiteSpeed Tech    if (BW_VALUE(&bbr->bbr_pacing_rate) < BW_VALUE(&target_rate))
9005392f7a3SLiteSpeed Tech        bbr->bbr_pacing_rate = target_rate;
9015392f7a3SLiteSpeed Tech}
9025392f7a3SLiteSpeed Tech
9035392f7a3SLiteSpeed Tech
9045392f7a3SLiteSpeed Tech/* See BbrSender::CalculateCongestionWindow */
9055392f7a3SLiteSpeed Techstatic void
9065392f7a3SLiteSpeed Techcalculate_cwnd (struct lsquic_bbr *bbr, uint64_t bytes_acked,
9075392f7a3SLiteSpeed Tech                                                  uint64_t excess_acked)
9085392f7a3SLiteSpeed Tech{
9095392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_PROBE_RTT)
9105392f7a3SLiteSpeed Tech        return;
9115392f7a3SLiteSpeed Tech
9125392f7a3SLiteSpeed Tech    uint64_t target_window = get_target_cwnd(bbr, bbr->bbr_cwnd_gain);
9135392f7a3SLiteSpeed Tech    if (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH)
9145392f7a3SLiteSpeed Tech        // Add the max recently measured ack aggregation to CWND.
9155392f7a3SLiteSpeed Tech        target_window += minmax_get(&bbr->bbr_max_ack_height);
9165392f7a3SLiteSpeed Tech    else if (bbr->bbr_flags & BBR_FLAG_ENABLE_ACK_AGG_IN_STARTUP)
9175392f7a3SLiteSpeed Tech        // Add the most recent excess acked.  Because CWND never decreases in
9185392f7a3SLiteSpeed Tech        // STARTUP, this will automatically create a very localized max filter.
9195392f7a3SLiteSpeed Tech        target_window += excess_acked;
9205392f7a3SLiteSpeed Tech
9215392f7a3SLiteSpeed Tech    // Instead of immediately setting the target CWND as the new one, BBR grows
9225392f7a3SLiteSpeed Tech    // the CWND towards |target_window| by only increasing it |bytes_acked| at a
9235392f7a3SLiteSpeed Tech    // time.
9245392f7a3SLiteSpeed Tech    const int add_bytes_acked =
9255392f7a3SLiteSpeed Tech	!FLAGS_quic_bbr_no_bytes_acked_in_startup_recovery || !in_recovery(bbr);
9265392f7a3SLiteSpeed Tech    if (bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH)
9275392f7a3SLiteSpeed Tech        bbr->bbr_cwnd = MIN(target_window, bbr->bbr_cwnd + bytes_acked);
9285392f7a3SLiteSpeed Tech    else if (add_bytes_acked &&
929843f807bSwangfuyu             (bbr->bbr_cwnd < target_window ||
9305392f7a3SLiteSpeed Tech              lsquic_bw_sampler_total_acked(&bbr->bbr_bw_sampler)
9315392f7a3SLiteSpeed Tech                                                        < bbr->bbr_init_cwnd))
9325392f7a3SLiteSpeed Tech        // If the connection is not yet out of startup phase, do not decrease
9335392f7a3SLiteSpeed Tech        // the window.
9345392f7a3SLiteSpeed Tech        bbr->bbr_cwnd += bytes_acked;
9355392f7a3SLiteSpeed Tech
9365392f7a3SLiteSpeed Tech    // Enforce the limits on the congestion window.
9375392f7a3SLiteSpeed Tech    if (bbr->bbr_cwnd < bbr->bbr_min_cwnd)
9385392f7a3SLiteSpeed Tech        bbr->bbr_cwnd = bbr->bbr_min_cwnd;
9395392f7a3SLiteSpeed Tech    else if (bbr->bbr_cwnd > bbr->bbr_max_cwnd)
9405392f7a3SLiteSpeed Tech    {
9415392f7a3SLiteSpeed Tech        LSQ_DEBUG("exceed max cwnd");
9425392f7a3SLiteSpeed Tech        bbr->bbr_cwnd = bbr->bbr_max_cwnd;
9435392f7a3SLiteSpeed Tech    }
9445392f7a3SLiteSpeed Tech}
9455392f7a3SLiteSpeed Tech
9465392f7a3SLiteSpeed Tech
9475392f7a3SLiteSpeed Tech/* See BbrSender::CalculateRecoveryWindow */
9485392f7a3SLiteSpeed Techstatic void
9495392f7a3SLiteSpeed Techcalculate_recovery_window (struct lsquic_bbr *bbr, uint64_t bytes_acked,
9505392f7a3SLiteSpeed Tech                                uint64_t bytes_lost, uint64_t bytes_in_flight)
9515392f7a3SLiteSpeed Tech{
9525392f7a3SLiteSpeed Tech    if ((bbr->bbr_flags & BBR_FLAG_RATE_BASED_STARTUP)
9535392f7a3SLiteSpeed Tech                                        && bbr->bbr_mode == BBR_MODE_STARTUP)
9545392f7a3SLiteSpeed Tech        return;
9555392f7a3SLiteSpeed Tech
9565392f7a3SLiteSpeed Tech    if (bbr->bbr_recovery_state == BBR_RS_NOT_IN_RECOVERY)
9575392f7a3SLiteSpeed Tech        return;
9585392f7a3SLiteSpeed Tech
9595392f7a3SLiteSpeed Tech    // Set up the initial recovery window.
9605392f7a3SLiteSpeed Tech    if (bbr->bbr_recovery_window == 0)
9615392f7a3SLiteSpeed Tech    {
9625392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window = bytes_in_flight + bytes_acked;
9635392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window = MAX(bbr->bbr_min_cwnd,
9645392f7a3SLiteSpeed Tech                                                    bbr->bbr_recovery_window);
9655392f7a3SLiteSpeed Tech        return;
9665392f7a3SLiteSpeed Tech    }
9675392f7a3SLiteSpeed Tech
9685392f7a3SLiteSpeed Tech    // Remove losses from the recovery window, while accounting for a potential
9695392f7a3SLiteSpeed Tech    // integer underflow.
9705392f7a3SLiteSpeed Tech    if (bbr->bbr_recovery_window >= bytes_lost)
9715392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window -= bytes_lost;
9725392f7a3SLiteSpeed Tech    else
9735392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window = kMaxSegmentSize;
9745392f7a3SLiteSpeed Tech
9755392f7a3SLiteSpeed Tech    // In CONSERVATION mode, just subtracting losses is sufficient.  In GROWTH,
9765392f7a3SLiteSpeed Tech    // release additional |bytes_acked| to achieve a slow-start-like behavior.
9775392f7a3SLiteSpeed Tech    if (bbr->bbr_recovery_state == BBR_RS_GROWTH)
9785392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window += bytes_acked;
9795392f7a3SLiteSpeed Tech
9805392f7a3SLiteSpeed Tech    // Sanity checks.  Ensure that we always allow to send at least an MSS or
9815392f7a3SLiteSpeed Tech    // |bytes_acked| in response, whichever is larger.
9825392f7a3SLiteSpeed Tech    bbr->bbr_recovery_window = MAX(bbr->bbr_recovery_window,
9835392f7a3SLiteSpeed Tech                                            bytes_in_flight + bytes_acked);
9845392f7a3SLiteSpeed Tech    if (FLAG_quic_bbr_one_mss_conservation)
9855392f7a3SLiteSpeed Tech        bbr->bbr_recovery_window = MAX(bbr->bbr_recovery_window,
9865392f7a3SLiteSpeed Tech                                            bytes_in_flight + kMaxSegmentSize);
9875392f7a3SLiteSpeed Tech    bbr->bbr_recovery_window = MAX(bbr->bbr_recovery_window, bbr->bbr_min_cwnd);
9885392f7a3SLiteSpeed Tech}
9895392f7a3SLiteSpeed Tech
9905392f7a3SLiteSpeed Tech
9915392f7a3SLiteSpeed Techstatic void
9925392f7a3SLiteSpeed Techlsquic_bbr_end_ack (void *cong_ctl, uint64_t in_flight)
9935392f7a3SLiteSpeed Tech{
9945392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
9955392f7a3SLiteSpeed Tech    int is_round_start, min_rtt_expired;
9965392f7a3SLiteSpeed Tech    uint64_t bytes_acked, excess_acked, bytes_lost;
9975392f7a3SLiteSpeed Tech
9985392f7a3SLiteSpeed Tech    assert(bbr->bbr_flags & BBR_FLAG_IN_ACK);
9995392f7a3SLiteSpeed Tech    bbr->bbr_flags &= ~BBR_FLAG_IN_ACK;
10005392f7a3SLiteSpeed Tech
10015392f7a3SLiteSpeed Tech    LSQ_DEBUG("end_ack; mode: %s; in_flight: %"PRIu64, mode2str[bbr->bbr_mode],
10025392f7a3SLiteSpeed Tech                                                                    in_flight);
10035392f7a3SLiteSpeed Tech
10045392f7a3SLiteSpeed Tech    bytes_acked = lsquic_bw_sampler_total_acked(&bbr->bbr_bw_sampler)
10055392f7a3SLiteSpeed Tech                            - bbr->bbr_ack_state.total_bytes_acked_before;
10065392f7a3SLiteSpeed Tech    if (bbr->bbr_ack_state.acked_bytes)
10075392f7a3SLiteSpeed Tech    {
10085392f7a3SLiteSpeed Tech        is_round_start = bbr->bbr_ack_state.max_packno
10095392f7a3SLiteSpeed Tech                                    > bbr->bbr_current_round_trip_end
10105392f7a3SLiteSpeed Tech                    || !is_valid_packno(bbr->bbr_current_round_trip_end);
10115392f7a3SLiteSpeed Tech        if (is_round_start)
10125392f7a3SLiteSpeed Tech        {
10135392f7a3SLiteSpeed Tech            ++bbr->bbr_round_count;
10145392f7a3SLiteSpeed Tech            bbr->bbr_current_round_trip_end = bbr->bbr_last_sent_packno;
10155392f7a3SLiteSpeed Tech            LSQ_DEBUG("up round count to %"PRIu64"; new rt end: %"PRIu64,
10165392f7a3SLiteSpeed Tech                        bbr->bbr_round_count, bbr->bbr_current_round_trip_end);
10175392f7a3SLiteSpeed Tech        }
10185392f7a3SLiteSpeed Tech        min_rtt_expired = update_bandwidth_and_min_rtt(bbr);
10195392f7a3SLiteSpeed Tech        update_recovery_state(bbr, is_round_start);
10205392f7a3SLiteSpeed Tech        excess_acked = update_ack_aggregation_bytes(bbr, bytes_acked);
10215392f7a3SLiteSpeed Tech    }
10225392f7a3SLiteSpeed Tech    else
10235392f7a3SLiteSpeed Tech    {
10245392f7a3SLiteSpeed Tech        is_round_start = 0;
10255392f7a3SLiteSpeed Tech        min_rtt_expired = 0;
10265392f7a3SLiteSpeed Tech        excess_acked = 0;
10275392f7a3SLiteSpeed Tech    }
10285392f7a3SLiteSpeed Tech
10295392f7a3SLiteSpeed Tech    if (bbr->bbr_mode == BBR_MODE_PROBE_BW)
10305392f7a3SLiteSpeed Tech        update_gain_cycle_phase(bbr, in_flight);
10315392f7a3SLiteSpeed Tech
10325392f7a3SLiteSpeed Tech    if (is_round_start && !(bbr->bbr_flags & BBR_FLAG_IS_AT_FULL_BANDWIDTH))
10335392f7a3SLiteSpeed Tech        check_if_full_bw_reached(bbr);
10345392f7a3SLiteSpeed Tech
10355392f7a3SLiteSpeed Tech    maybe_exit_startup_or_drain(bbr, bbr->bbr_ack_state.ack_time, in_flight);
10365392f7a3SLiteSpeed Tech
10375392f7a3SLiteSpeed Tech    maybe_enter_or_exit_probe_rtt(bbr, bbr->bbr_ack_state.ack_time,
10385392f7a3SLiteSpeed Tech                                is_round_start, min_rtt_expired, in_flight);
10395392f7a3SLiteSpeed Tech
10405392f7a3SLiteSpeed Tech    // Calculate number of packets acked and lost.
10415392f7a3SLiteSpeed Tech    bytes_lost = bbr->bbr_ack_state.lost_bytes;
10425392f7a3SLiteSpeed Tech
10435392f7a3SLiteSpeed Tech    // After the model is updated, recalculate the pacing rate and congestion
10445392f7a3SLiteSpeed Tech    // window.
10455392f7a3SLiteSpeed Tech    calculate_pacing_rate(bbr);
10465392f7a3SLiteSpeed Tech    calculate_cwnd(bbr, bytes_acked, excess_acked);
10475392f7a3SLiteSpeed Tech    calculate_recovery_window(bbr, bytes_acked, bytes_lost, in_flight);
10485392f7a3SLiteSpeed Tech
10495392f7a3SLiteSpeed Tech    /* We don't need to clean up BW sampler */
10505392f7a3SLiteSpeed Tech}
10515392f7a3SLiteSpeed Tech
10525392f7a3SLiteSpeed Tech
10535392f7a3SLiteSpeed Techstatic void
10545392f7a3SLiteSpeed Techlsquic_bbr_cleanup (void *cong_ctl)
10555392f7a3SLiteSpeed Tech{
10565392f7a3SLiteSpeed Tech    struct lsquic_bbr *const bbr = cong_ctl;
10575392f7a3SLiteSpeed Tech
1058a6cdaedbSDmitri Tikhonov    lsquic_bw_sampler_cleanup(&bbr->bbr_bw_sampler);
10595392f7a3SLiteSpeed Tech    LSQ_DEBUG("cleanup");
10605392f7a3SLiteSpeed Tech}
10615392f7a3SLiteSpeed Tech
10625392f7a3SLiteSpeed Tech
10635392f7a3SLiteSpeed Techstatic void
10645392f7a3SLiteSpeed Techlsquic_bbr_loss (void *cong_ctl) {   /* Noop */   }
10655392f7a3SLiteSpeed Tech
10665392f7a3SLiteSpeed Tech
10675392f7a3SLiteSpeed Techstatic void
10685392f7a3SLiteSpeed Techlsquic_bbr_timeout (void *cong_ctl) {   /* Noop */   }
10695392f7a3SLiteSpeed Tech
10705392f7a3SLiteSpeed Tech
10715392f7a3SLiteSpeed Techconst struct cong_ctl_if lsquic_cong_bbr_if =
10725392f7a3SLiteSpeed Tech{
10735392f7a3SLiteSpeed Tech    .cci_ack           = lsquic_bbr_ack,
10745392f7a3SLiteSpeed Tech    .cci_begin_ack     = lsquic_bbr_begin_ack,
10755392f7a3SLiteSpeed Tech    .cci_end_ack       = lsquic_bbr_end_ack,
10765392f7a3SLiteSpeed Tech    .cci_cleanup       = lsquic_bbr_cleanup,
10775392f7a3SLiteSpeed Tech    .cci_get_cwnd      = lsquic_bbr_get_cwnd,
10785392f7a3SLiteSpeed Tech    .cci_init          = lsquic_bbr_init,
10795392f7a3SLiteSpeed Tech    .cci_pacing_rate   = lsquic_bbr_pacing_rate,
10805392f7a3SLiteSpeed Tech    .cci_loss          = lsquic_bbr_loss,
10815392f7a3SLiteSpeed Tech    .cci_lost          = lsquic_bbr_lost,
10829fc12041SDmitri Tikhonov    .cci_reinit        = lsquic_bbr_reinit,
10835392f7a3SLiteSpeed Tech    .cci_timeout       = lsquic_bbr_timeout,
10845392f7a3SLiteSpeed Tech    .cci_sent          = lsquic_bbr_sent,
10855392f7a3SLiteSpeed Tech    .cci_was_quiet     = lsquic_bbr_was_quiet,
10865392f7a3SLiteSpeed Tech};
1087