lsquic_pacer.c revision 50aadb33 
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_packet_scheduled (struct pacer *pacer, unsigned n_in_flight,
46                            int in_recovery, tx_time_f tx_time, void *tx_ctx)
47{
48    lsquic_time_t delay, sched_time;
49    int app_limited, making_up;
50
51    if (n_in_flight == 0 && !in_recovery)
52    {
53        pacer->pa_burst_tokens = 10;
54        LSQ_DEBUG("%s: replenish tokens: %u", __func__, pacer->pa_burst_tokens);
55    }
56
57    if (pacer->pa_burst_tokens > 0)
58    {
59        --pacer->pa_burst_tokens;
60        pacer->pa_flags &= ~PA_LAST_SCHED_DELAYED;
61        pacer->pa_next_sched = 0;
62        pacer->pa_last_delayed = 0;
63        LSQ_DEBUG("%s: tokens: %u", __func__, pacer->pa_burst_tokens);
64        return;
65    }
66
67    sched_time = pacer->pa_now;
68    delay = tx_time(tx_ctx);
69    if (pacer->pa_flags & PA_LAST_SCHED_DELAYED)
70    {
71        pacer->pa_next_sched += delay;
72        app_limited = pacer->pa_last_delayed != 0
73            && pacer->pa_last_delayed + delay <= sched_time;
74        making_up = pacer->pa_next_sched <= sched_time;
75        LSQ_DEBUG("making up: %d; app limited; %d", making_up, app_limited);
76        if (making_up && !app_limited)
77            pacer->pa_last_delayed = sched_time;
78        else
79        {
80            pacer->pa_flags &= ~PA_LAST_SCHED_DELAYED;
81            pacer->pa_last_delayed = 0;
82        }
83    }
84    else
85        pacer->pa_next_sched = MAX(pacer->pa_next_sched + delay,
86                                                    sched_time + delay);
87    LSQ_DEBUG("next_sched is set to %"PRIu64" usec from now",
88                                pacer->pa_next_sched - lsquic_time_now());
89}
90
91
92void
93pacer_loss_event (struct pacer *pacer)
94{
95    pacer->pa_burst_tokens = 0;
96    LSQ_DEBUG("%s: tokens: %u", __func__, pacer->pa_burst_tokens);
97}
98
99
100static unsigned
101clock_granularity (const struct pacer *pacer)
102{
103#ifndef NDEBUG
104    if (pacer->pa_flags & PA_CONSTANT_INTERTICK)
105        return pacer->pa_max_intertick;
106#endif
107
108    return pacer->pa_intertick_var;
109}
110
111
112int
113pacer_can_schedule (struct pacer *pacer, unsigned n_in_flight)
114{
115    int can;
116
117    if (pacer->pa_burst_tokens > 0 || n_in_flight == 0)
118        can = 1;
119    else if (pacer->pa_next_sched > pacer->pa_now + clock_granularity(pacer))
120    {
121        pacer->pa_flags |= PA_LAST_SCHED_DELAYED;
122        can = 0;
123    }
124    else
125        can = 1;
126
127    LSQ_DEBUG("%s: %d", __func__, can);
128    return can;
129}
130
131
132#define ALPHA_SHIFT 3
133#define BETA_SHIFT  2
134
135static void
136update_avg_intertick (struct pacer *pacer, unsigned intertick)
137{
138    unsigned diff;
139
140#ifndef NDEBUG
141    if (pacer->pa_flags & PA_CONSTANT_INTERTICK)
142        return;
143#endif
144
145    if (pacer->pa_intertick_avg)
146    {
147        if (intertick > pacer->pa_intertick_avg)
148            diff = intertick - pacer->pa_intertick_avg;
149        else
150            diff = pacer->pa_intertick_avg - intertick;
151        pacer->pa_intertick_var -= pacer->pa_intertick_var >> BETA_SHIFT;
152        pacer->pa_intertick_var += diff >> BETA_SHIFT;
153        pacer->pa_intertick_avg -= pacer->pa_intertick_avg >> ALPHA_SHIFT;
154        pacer->pa_intertick_avg += intertick >> ALPHA_SHIFT;
155    }
156    else
157    {
158        pacer->pa_intertick_avg = intertick;
159        pacer->pa_intertick_var = intertick >> 1;
160    }
161}
162
163
164void
165pacer_tick (struct pacer *pacer, lsquic_time_t now)
166{
167    unsigned intertick;
168
169    assert(now > pacer->pa_now);
170    if (pacer->pa_now)
171    {
172        assert(now - pacer->pa_now < (1ULL << sizeof(unsigned) * 8));
173        intertick = now - pacer->pa_now;
174        LSQ_DEBUG("intertick estimate: %u; real value: %u; error: %d",
175            clock_granularity(pacer), intertick,
176            (int) clock_granularity(pacer) - (int) intertick);
177        update_avg_intertick(pacer, intertick);
178    }
179    pacer->pa_now = now;
180}
181