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