lsquic_pacer.c revision 50aadb33
150aadb33SDmitri Tikhonov/* Copyright (c) 2017 LiteSpeed Technologies Inc.  See LICENSE. */
250aadb33SDmitri Tikhonov#include <assert.h>
350aadb33SDmitri Tikhonov#include <inttypes.h>
450aadb33SDmitri Tikhonov#include <stdint.h>
550aadb33SDmitri Tikhonov#ifndef NDEBUG
650aadb33SDmitri Tikhonov#include <stdlib.h>     /* getenv */
750aadb33SDmitri Tikhonov#endif
850aadb33SDmitri Tikhonov#include <string.h>
950aadb33SDmitri Tikhonov
1050aadb33SDmitri Tikhonov#include "lsquic_types.h"
1150aadb33SDmitri Tikhonov#include "lsquic_int_types.h"
1250aadb33SDmitri Tikhonov#include "lsquic_pacer.h"
1350aadb33SDmitri Tikhonov#include "lsquic_packet_common.h"
1450aadb33SDmitri Tikhonov#include "lsquic_packet_out.h"
1550aadb33SDmitri Tikhonov#include "lsquic_util.h"
1650aadb33SDmitri Tikhonov
1750aadb33SDmitri Tikhonov#define LSQUIC_LOGGER_MODULE LSQLM_PACER
1850aadb33SDmitri Tikhonov#define LSQUIC_LOG_CONN_ID pacer->pa_cid
1950aadb33SDmitri Tikhonov#include "lsquic_logger.h"
2050aadb33SDmitri Tikhonov
2150aadb33SDmitri Tikhonov#ifndef MAX
2250aadb33SDmitri Tikhonov#   define MAX(a, b) ((a) > (b) ? (a) : (b))
2350aadb33SDmitri Tikhonov#endif
2450aadb33SDmitri Tikhonov
2550aadb33SDmitri Tikhonov
2650aadb33SDmitri Tikhonovvoid
2750aadb33SDmitri Tikhonovpacer_init (struct pacer *pacer, lsquic_cid_t cid, unsigned max_intertick)
2850aadb33SDmitri Tikhonov{
2950aadb33SDmitri Tikhonov    memset(pacer, 0, sizeof(*pacer));
3050aadb33SDmitri Tikhonov    pacer->pa_burst_tokens = 10;
3150aadb33SDmitri Tikhonov    pacer->pa_cid = cid;
3250aadb33SDmitri Tikhonov    pacer->pa_max_intertick = max_intertick;
3350aadb33SDmitri Tikhonov#ifndef NDEBUG
3450aadb33SDmitri Tikhonov    const char *val;
3550aadb33SDmitri Tikhonov    if ((val = getenv("LSQUIC_PACER_INTERTICK")))
3650aadb33SDmitri Tikhonov    {
3750aadb33SDmitri Tikhonov        pacer->pa_flags |= PA_CONSTANT_INTERTICK;
3850aadb33SDmitri Tikhonov        pacer->pa_intertick_avg = atoi(val);
3950aadb33SDmitri Tikhonov    }
4050aadb33SDmitri Tikhonov#endif
4150aadb33SDmitri Tikhonov}
4250aadb33SDmitri Tikhonov
4350aadb33SDmitri Tikhonov
4450aadb33SDmitri Tikhonovvoid
4550aadb33SDmitri Tikhonovpacer_packet_scheduled (struct pacer *pacer, unsigned n_in_flight,
4650aadb33SDmitri Tikhonov                            int in_recovery, tx_time_f tx_time, void *tx_ctx)
4750aadb33SDmitri Tikhonov{
4850aadb33SDmitri Tikhonov    lsquic_time_t delay, sched_time;
4950aadb33SDmitri Tikhonov    int app_limited, making_up;
5050aadb33SDmitri Tikhonov
5150aadb33SDmitri Tikhonov    if (n_in_flight == 0 && !in_recovery)
5250aadb33SDmitri Tikhonov    {
5350aadb33SDmitri Tikhonov        pacer->pa_burst_tokens = 10;
5450aadb33SDmitri Tikhonov        LSQ_DEBUG("%s: replenish tokens: %u", __func__, pacer->pa_burst_tokens);
5550aadb33SDmitri Tikhonov    }
5650aadb33SDmitri Tikhonov
5750aadb33SDmitri Tikhonov    if (pacer->pa_burst_tokens > 0)
5850aadb33SDmitri Tikhonov    {
5950aadb33SDmitri Tikhonov        --pacer->pa_burst_tokens;
6050aadb33SDmitri Tikhonov        pacer->pa_flags &= ~PA_LAST_SCHED_DELAYED;
6150aadb33SDmitri Tikhonov        pacer->pa_next_sched = 0;
6250aadb33SDmitri Tikhonov        pacer->pa_last_delayed = 0;
6350aadb33SDmitri Tikhonov        LSQ_DEBUG("%s: tokens: %u", __func__, pacer->pa_burst_tokens);
6450aadb33SDmitri Tikhonov        return;
6550aadb33SDmitri Tikhonov    }
6650aadb33SDmitri Tikhonov
6750aadb33SDmitri Tikhonov    sched_time = pacer->pa_now;
6850aadb33SDmitri Tikhonov    delay = tx_time(tx_ctx);
6950aadb33SDmitri Tikhonov    if (pacer->pa_flags & PA_LAST_SCHED_DELAYED)
7050aadb33SDmitri Tikhonov    {
7150aadb33SDmitri Tikhonov        pacer->pa_next_sched += delay;
7250aadb33SDmitri Tikhonov        app_limited = pacer->pa_last_delayed != 0
7350aadb33SDmitri Tikhonov            && pacer->pa_last_delayed + delay <= sched_time;
7450aadb33SDmitri Tikhonov        making_up = pacer->pa_next_sched <= sched_time;
7550aadb33SDmitri Tikhonov        LSQ_DEBUG("making up: %d; app limited; %d", making_up, app_limited);
7650aadb33SDmitri Tikhonov        if (making_up && !app_limited)
7750aadb33SDmitri Tikhonov            pacer->pa_last_delayed = sched_time;
7850aadb33SDmitri Tikhonov        else
7950aadb33SDmitri Tikhonov        {
8050aadb33SDmitri Tikhonov            pacer->pa_flags &= ~PA_LAST_SCHED_DELAYED;
8150aadb33SDmitri Tikhonov            pacer->pa_last_delayed = 0;
8250aadb33SDmitri Tikhonov        }
8350aadb33SDmitri Tikhonov    }
8450aadb33SDmitri Tikhonov    else
8550aadb33SDmitri Tikhonov        pacer->pa_next_sched = MAX(pacer->pa_next_sched + delay,
8650aadb33SDmitri Tikhonov                                                    sched_time + delay);
8750aadb33SDmitri Tikhonov    LSQ_DEBUG("next_sched is set to %"PRIu64" usec from now",
8850aadb33SDmitri Tikhonov                                pacer->pa_next_sched - lsquic_time_now());
8950aadb33SDmitri Tikhonov}
9050aadb33SDmitri Tikhonov
9150aadb33SDmitri Tikhonov
9250aadb33SDmitri Tikhonovvoid
9350aadb33SDmitri Tikhonovpacer_loss_event (struct pacer *pacer)
9450aadb33SDmitri Tikhonov{
9550aadb33SDmitri Tikhonov    pacer->pa_burst_tokens = 0;
9650aadb33SDmitri Tikhonov    LSQ_DEBUG("%s: tokens: %u", __func__, pacer->pa_burst_tokens);
9750aadb33SDmitri Tikhonov}
9850aadb33SDmitri Tikhonov
9950aadb33SDmitri Tikhonov
10050aadb33SDmitri Tikhonovstatic unsigned
10150aadb33SDmitri Tikhonovclock_granularity (const struct pacer *pacer)
10250aadb33SDmitri Tikhonov{
10350aadb33SDmitri Tikhonov#ifndef NDEBUG
10450aadb33SDmitri Tikhonov    if (pacer->pa_flags & PA_CONSTANT_INTERTICK)
10550aadb33SDmitri Tikhonov        return pacer->pa_max_intertick;
10650aadb33SDmitri Tikhonov#endif
10750aadb33SDmitri Tikhonov
10850aadb33SDmitri Tikhonov    return pacer->pa_intertick_var;
10950aadb33SDmitri Tikhonov}
11050aadb33SDmitri Tikhonov
11150aadb33SDmitri Tikhonov
11250aadb33SDmitri Tikhonovint
11350aadb33SDmitri Tikhonovpacer_can_schedule (struct pacer *pacer, unsigned n_in_flight)
11450aadb33SDmitri Tikhonov{
11550aadb33SDmitri Tikhonov    int can;
11650aadb33SDmitri Tikhonov
11750aadb33SDmitri Tikhonov    if (pacer->pa_burst_tokens > 0 || n_in_flight == 0)
11850aadb33SDmitri Tikhonov        can = 1;
11950aadb33SDmitri Tikhonov    else if (pacer->pa_next_sched > pacer->pa_now + clock_granularity(pacer))
12050aadb33SDmitri Tikhonov    {
12150aadb33SDmitri Tikhonov        pacer->pa_flags |= PA_LAST_SCHED_DELAYED;
12250aadb33SDmitri Tikhonov        can = 0;
12350aadb33SDmitri Tikhonov    }
12450aadb33SDmitri Tikhonov    else
12550aadb33SDmitri Tikhonov        can = 1;
12650aadb33SDmitri Tikhonov
12750aadb33SDmitri Tikhonov    LSQ_DEBUG("%s: %d", __func__, can);
12850aadb33SDmitri Tikhonov    return can;
12950aadb33SDmitri Tikhonov}
13050aadb33SDmitri Tikhonov
13150aadb33SDmitri Tikhonov
13250aadb33SDmitri Tikhonov#define ALPHA_SHIFT 3
13350aadb33SDmitri Tikhonov#define BETA_SHIFT  2
13450aadb33SDmitri Tikhonov
13550aadb33SDmitri Tikhonovstatic void
13650aadb33SDmitri Tikhonovupdate_avg_intertick (struct pacer *pacer, unsigned intertick)
13750aadb33SDmitri Tikhonov{
13850aadb33SDmitri Tikhonov    unsigned diff;
13950aadb33SDmitri Tikhonov
14050aadb33SDmitri Tikhonov#ifndef NDEBUG
14150aadb33SDmitri Tikhonov    if (pacer->pa_flags & PA_CONSTANT_INTERTICK)
14250aadb33SDmitri Tikhonov        return;
14350aadb33SDmitri Tikhonov#endif
14450aadb33SDmitri Tikhonov
14550aadb33SDmitri Tikhonov    if (pacer->pa_intertick_avg)
14650aadb33SDmitri Tikhonov    {
14750aadb33SDmitri Tikhonov        if (intertick > pacer->pa_intertick_avg)
14850aadb33SDmitri Tikhonov            diff = intertick - pacer->pa_intertick_avg;
14950aadb33SDmitri Tikhonov        else
15050aadb33SDmitri Tikhonov            diff = pacer->pa_intertick_avg - intertick;
15150aadb33SDmitri Tikhonov        pacer->pa_intertick_var -= pacer->pa_intertick_var >> BETA_SHIFT;
15250aadb33SDmitri Tikhonov        pacer->pa_intertick_var += diff >> BETA_SHIFT;
15350aadb33SDmitri Tikhonov        pacer->pa_intertick_avg -= pacer->pa_intertick_avg >> ALPHA_SHIFT;
15450aadb33SDmitri Tikhonov        pacer->pa_intertick_avg += intertick >> ALPHA_SHIFT;
15550aadb33SDmitri Tikhonov    }
15650aadb33SDmitri Tikhonov    else
15750aadb33SDmitri Tikhonov    {
15850aadb33SDmitri Tikhonov        pacer->pa_intertick_avg = intertick;
15950aadb33SDmitri Tikhonov        pacer->pa_intertick_var = intertick >> 1;
16050aadb33SDmitri Tikhonov    }
16150aadb33SDmitri Tikhonov}
16250aadb33SDmitri Tikhonov
16350aadb33SDmitri Tikhonov
16450aadb33SDmitri Tikhonovvoid
16550aadb33SDmitri Tikhonovpacer_tick (struct pacer *pacer, lsquic_time_t now)
16650aadb33SDmitri Tikhonov{
16750aadb33SDmitri Tikhonov    unsigned intertick;
16850aadb33SDmitri Tikhonov
16950aadb33SDmitri Tikhonov    assert(now > pacer->pa_now);
17050aadb33SDmitri Tikhonov    if (pacer->pa_now)
17150aadb33SDmitri Tikhonov    {
17250aadb33SDmitri Tikhonov        assert(now - pacer->pa_now < (1ULL << sizeof(unsigned) * 8));
17350aadb33SDmitri Tikhonov        intertick = now - pacer->pa_now;
17450aadb33SDmitri Tikhonov        LSQ_DEBUG("intertick estimate: %u; real value: %u; error: %d",
17550aadb33SDmitri Tikhonov            clock_granularity(pacer), intertick,
17650aadb33SDmitri Tikhonov            (int) clock_granularity(pacer) - (int) intertick);
17750aadb33SDmitri Tikhonov        update_avg_intertick(pacer, intertick);
17850aadb33SDmitri Tikhonov    }
17950aadb33SDmitri Tikhonov    pacer->pa_now = now;
18050aadb33SDmitri Tikhonov}
181