lsquic_pacer.c revision bfc7bfd8 
1/* Copyright (c) 2017 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <assert.h>
3#include <inttypes.h>
4#include <stdint.h>
5#ifndef NDEBUG
6#include <stdlib.h>     /* getenv */
7#endif
8#include <string.h>
9
10#include "lsquic_types.h"
11#include "lsquic_int_types.h"
12#include "lsquic_pacer.h"
13#include "lsquic_packet_common.h"
14#include "lsquic_packet_out.h"
15#include "lsquic_util.h"
16
17#define LSQUIC_LOGGER_MODULE LSQLM_PACER
18#define LSQUIC_LOG_CONN_ID pacer->pa_cid
19#include "lsquic_logger.h"
20
21#ifndef MAX
22#   define MAX(a, b) ((a) > (b) ? (a) : (b))
23#endif
24
25
26void
27pacer_init (struct pacer *pacer, lsquic_cid_t cid, unsigned max_intertick)
28{
29    memset(pacer, 0, sizeof(*pacer));
30    pacer->pa_burst_tokens = 10;
31    pacer->pa_cid = cid;
32    pacer->pa_max_intertick = max_intertick;
33#ifndef NDEBUG
34    const char *val;
35    if ((val = getenv("LSQUIC_PACER_INTERTICK")))
36    {
37        pacer->pa_flags |= PA_CONSTANT_INTERTICK;
38        pacer->pa_intertick_avg = atoi(val);
39    }
40#endif
41}
42
43
44void
45pacer_cleanup (struct pacer *pacer)
46{
47#ifndef NDEBUG
48    LSQ_NOTICE("scheduled calls: %u", pacer->pa_stats.n_scheduled);
49#endif
50}
51
52
53void
54pacer_packet_scheduled (struct pacer *pacer, unsigned n_in_flight,
55                            int in_recovery, tx_time_f tx_time, void *tx_ctx)
56{
57    lsquic_time_t delay, sched_time;
58    int app_limited, making_up;
59
60#ifndef NDEBUG
61    ++pacer->pa_stats.n_scheduled;
62#endif
63
64    if (n_in_flight == 0 && !in_recovery)
65    {
66        pacer->pa_burst_tokens = 10;
67        LSQ_DEBUG("%s: replenish tokens: %u", __func__, pacer->pa_burst_tokens);
68    }
69
70    if (pacer->pa_burst_tokens > 0)
71    {
72        --pacer->pa_burst_tokens;
73        pacer->pa_flags &= ~PA_LAST_SCHED_DELAYED;
74        pacer->pa_next_sched = 0;
75        pacer->pa_last_delayed = 0;
76        LSQ_DEBUG("%s: tokens: %u", __func__, pacer->pa_burst_tokens);
77        return;
78    }
79
80    sched_time = pacer->pa_now;
81    delay = tx_time(tx_ctx);
82    if (pacer->pa_flags & PA_LAST_SCHED_DELAYED)
83    {
84        pacer->pa_next_sched += delay;
85        app_limited = pacer->pa_last_delayed != 0
86            && pacer->pa_last_delayed + delay <= sched_time;
87        making_up = pacer->pa_next_sched <= sched_time;
88        LSQ_DEBUG("making up: %d; app limited; %d", making_up, app_limited);
89        if (making_up && !app_limited)
90            pacer->pa_last_delayed = sched_time;
91        else
92        {
93            pacer->pa_flags &= ~PA_LAST_SCHED_DELAYED;
94            pacer->pa_last_delayed = 0;
95        }
96    }
97    else
98        pacer->pa_next_sched = MAX(pacer->pa_next_sched + delay,
99                                                    sched_time + delay);
100    LSQ_DEBUG("next_sched is set to %"PRIu64" usec from now",
101                                pacer->pa_next_sched - lsquic_time_now());
102}
103
104
105void
106pacer_loss_event (struct pacer *pacer)
107{
108    pacer->pa_burst_tokens = 0;
109    LSQ_DEBUG("%s: tokens: %u", __func__, pacer->pa_burst_tokens);
110}
111
112
113static unsigned
114clock_granularity (const struct pacer *pacer)
115{
116    return pacer->pa_intertick_avg;
117}
118
119
120int
121pacer_can_schedule (struct pacer *pacer, unsigned n_in_flight)
122{
123    int can;
124
125    if (pacer->pa_burst_tokens > 0 || n_in_flight == 0)
126        can = 1;
127    else if (pacer->pa_next_sched > pacer->pa_now + clock_granularity(pacer))
128    {
129        pacer->pa_flags |= PA_LAST_SCHED_DELAYED;
130        can = 0;
131    }
132    else
133        can = 1;
134
135    LSQ_DEBUG("%s: %d", __func__, can);
136    return can;
137}
138
139
140#define ALPHA_SHIFT 3
141#define BETA_SHIFT  2
142
143static void
144update_avg_intertick (struct pacer *pacer, unsigned intertick)
145{
146    unsigned diff;
147
148#ifndef NDEBUG
149    if (pacer->pa_flags & PA_CONSTANT_INTERTICK)
150        return;
151#endif
152
153    if (pacer->pa_intertick_avg)
154    {
155        if (intertick > pacer->pa_intertick_avg)
156            diff = intertick - pacer->pa_intertick_avg;
157        else
158            diff = pacer->pa_intertick_avg - intertick;
159        pacer->pa_intertick_var -= pacer->pa_intertick_var >> BETA_SHIFT;
160        pacer->pa_intertick_var += diff >> BETA_SHIFT;
161        pacer->pa_intertick_avg -= pacer->pa_intertick_avg >> ALPHA_SHIFT;
162        pacer->pa_intertick_avg += intertick >> ALPHA_SHIFT;
163    }
164    else
165    {
166        pacer->pa_intertick_avg = intertick;
167        pacer->pa_intertick_var = intertick >> 1;
168    }
169}
170
171
172void
173pacer_tick (struct pacer *pacer, lsquic_time_t now)
174{
175    unsigned intertick;
176
177    assert(now > pacer->pa_now);
178    if (pacer->pa_now)
179    {
180        assert(now - pacer->pa_now < (1ULL << sizeof(unsigned) * 8));
181        intertick = now - pacer->pa_now;
182        LSQ_DEBUG("intertick estimate: %u; real value: %u; error: %d",
183            clock_granularity(pacer), intertick,
184            (int) clock_granularity(pacer) - (int) intertick);
185        update_avg_intertick(pacer, intertick);
186    }
187    pacer->pa_now = now;
188}
189