lsquic_bw_sampler.c revision b1a7c3f9 
1/* Copyright (c) 2017 - 2020 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <assert.h>
3#include <inttypes.h>
4#include <stddef.h>
5#include <stdint.h>
6#include <sys/queue.h>
7
8#include "lsquic_int_types.h"
9#include "lsquic_types.h"
10#include "lsquic_hash.h"
11#include "lsquic.h"
12#include "lsquic_conn.h"
13#include "lsquic_malo.h"
14#include "lsquic_util.h"
15#include "lsquic_packet_common.h"
16#include "lsquic_packet_out.h"
17#include "lsquic_parse.h"
18#include "lsquic_bw_sampler.h"
19
20#define LSQUIC_LOGGER_MODULE LSQLM_BW_SAMPLER
21#define LSQUIC_LOG_CONN_ID lsquic_conn_log_cid(sampler->bws_conn)
22#include "lsquic_logger.h"
23
24
25int
26lsquic_bw_sampler_init (struct bw_sampler *sampler, struct lsquic_conn *conn,
27                                                enum quic_ft_bit retx_frames)
28{
29    struct malo *malo;
30
31    assert(lsquic_is_zero(sampler, sizeof(*sampler)));
32
33    malo = lsquic_malo_create(sizeof(struct bwp_state));
34    if (!malo)
35        return -1;
36
37    sampler->bws_malo = malo;
38    sampler->bws_conn = conn;
39    sampler->bws_retx_frames = retx_frames;
40    LSQ_DEBUG("init");
41    return 0;
42}
43
44
45void
46lsquic_bw_sampler_app_limited (struct bw_sampler *sampler)
47{
48    sampler->bws_flags |= BWS_APP_LIMITED;
49    sampler->bws_end_of_app_limited_phase = sampler->bws_last_sent_packno;
50    LSQ_DEBUG("app limited, end of limited phase is %"PRIu64,
51                                    sampler->bws_end_of_app_limited_phase);
52}
53
54
55void
56lsquic_bw_sampler_cleanup (struct bw_sampler *sampler)
57{
58    if (sampler->bws_conn)
59        LSQ_DEBUG("cleanup");
60    if (sampler->bws_malo)
61    {
62        lsquic_malo_destroy(sampler->bws_malo);
63        sampler->bws_malo = NULL;
64    }
65}
66
67
68/* This module only fails when it is unable to allocate memory.  This rarely
69 * happens, so we avoid having to check return values and abort the connection
70 * instead.
71 */
72static void
73bw_sampler_abort_conn (struct bw_sampler *sampler)
74{
75    if (!(sampler->bws_flags & BWS_CONN_ABORTED))
76    {
77        sampler->bws_flags |= BWS_CONN_ABORTED;
78        LSQ_WARN("aborting connection");
79        sampler->bws_conn->cn_if->ci_internal_error(sampler->bws_conn,
80                                                    "resources exhausted");
81    }
82}
83
84
85#define BW_WARN_ONCE(...) do {                                              \
86    if (!(sampler->bws_flags & BWS_WARNED))                                 \
87    {                                                                       \
88        sampler->bws_flags |= BWS_WARNED;                                   \
89        LSQ_WARN(__VA_ARGS__);                                              \
90    }                                                                       \
91} while (0)
92
93void
94lsquic_bw_sampler_packet_sent (struct bw_sampler *sampler,
95                    struct lsquic_packet_out *packet_out, uint64_t in_flight)
96{
97    struct bwp_state *state;
98    unsigned short sent_sz;
99
100    if (packet_out->po_bwp_state)
101    {
102        BW_WARN_ONCE("sent: packet %"PRIu64" already has state",
103                                                        packet_out->po_packno);
104        return;
105    }
106
107    sampler->bws_last_sent_packno = packet_out->po_packno;
108
109    if (!(packet_out->po_frame_types & sampler->bws_retx_frames))
110        return;
111
112    sent_sz = lsquic_packet_out_sent_sz(sampler->bws_conn, packet_out);
113    sampler->bws_total_sent += sent_sz;
114
115    // If there are no packets in flight, the time at which the new transmission
116    // opens can be treated as the A_0 point for the purpose of bandwidth
117    // sampling. This underestimates bandwidth to some extent, and produces some
118    // artificially low samples for most packets in flight, but it provides with
119    // samples at important points where we would not have them otherwise, most
120    // importantly at the beginning of the connection.
121    if (in_flight == 0)
122    {
123        sampler->bws_last_acked_packet_time = packet_out->po_sent;
124        sampler->bws_last_acked_total_sent = sampler->bws_total_sent;
125        // In this situation ack compression is not a concern, set send rate to
126        // effectively infinite.
127        sampler->bws_last_acked_sent_time = packet_out->po_sent;
128    }
129
130    state = lsquic_malo_get(sampler->bws_malo);
131    if (!state)
132    {
133        bw_sampler_abort_conn(sampler);
134        return;
135    }
136
137    state->bwps_send_state = (struct bwps_send_state) {
138        .total_bytes_sent   = sampler->bws_total_sent,
139        .total_bytes_acked  = sampler->bws_total_acked,
140        .total_bytes_lost   = sampler->bws_total_lost,
141        .is_app_limited     = !!(sampler->bws_flags & BWS_APP_LIMITED),
142    };
143    state->bwps_sent_at_last_ack = sampler->bws_last_acked_total_sent;
144    state->bwps_last_ack_sent_time = sampler->bws_last_acked_sent_time;
145    state->bwps_last_ack_ack_time = sampler->bws_last_acked_packet_time;
146    state->bwps_packet_size = sent_sz;
147
148    packet_out->po_bwp_state = state;
149
150    LSQ_DEBUG("add info for packet %"PRIu64, packet_out->po_packno);
151}
152
153
154void
155lsquic_bw_sampler_packet_lost (struct bw_sampler *sampler,
156                                    struct lsquic_packet_out *packet_out)
157{
158    if (!packet_out->po_bwp_state)
159        return;
160
161    sampler->bws_total_lost += packet_out->po_bwp_state->bwps_packet_size;
162    lsquic_malo_put(packet_out->po_bwp_state);
163    packet_out->po_bwp_state = NULL;
164    LSQ_DEBUG("packet %"PRIu64" lost, total_lost goes to %"PRIu64,
165                            packet_out->po_packno, sampler->bws_total_lost);
166}
167
168
169struct bw_sample *
170lsquic_bw_sampler_packet_acked (struct bw_sampler *sampler,
171                struct lsquic_packet_out *packet_out, lsquic_time_t ack_time)
172{
173    const struct bwp_state *state;
174    struct bw_sample *sample;
175    struct bandwidth send_rate, ack_rate;
176    lsquic_time_t rtt;
177    unsigned short sent_sz;
178    int is_app_limited;
179
180    if (!packet_out->po_bwp_state)
181        return 0;
182
183    state = packet_out->po_bwp_state;
184    sent_sz = lsquic_packet_out_sent_sz(sampler->bws_conn, packet_out);
185
186    sampler->bws_total_acked += sent_sz;
187    sampler->bws_last_acked_total_sent = state->bwps_send_state.total_bytes_sent;
188    sampler->bws_last_acked_sent_time = packet_out->po_sent;
189    sampler->bws_last_acked_packet_time = ack_time;
190
191    // Exit app-limited phase once a packet that was sent while the connection
192    // is not app-limited is acknowledged.
193    if ((sampler->bws_flags & BWS_APP_LIMITED)
194            && packet_out->po_packno > sampler->bws_end_of_app_limited_phase)
195    {
196        sampler->bws_flags &= ~BWS_APP_LIMITED;
197        LSQ_DEBUG("exit app-limited phase due to packet %"PRIu64" being acked",
198                                                        packet_out->po_packno);
199    }
200
201    // There might have been no packets acknowledged at the moment when the
202    // current packet was sent. In that case, there is no bandwidth sample to
203    // make.
204    if (state->bwps_last_ack_sent_time == 0)
205        goto no_sample;
206
207    // Infinite rate indicates that the sampler is supposed to discard the
208    // current send rate sample and use only the ack rate.
209    if (packet_out->po_sent > state->bwps_last_ack_sent_time)
210        send_rate = BW_FROM_BYTES_AND_DELTA(
211            state->bwps_send_state.total_bytes_sent
212                                    - state->bwps_sent_at_last_ack,
213            packet_out->po_sent - state->bwps_last_ack_sent_time);
214    else
215        send_rate = BW_INFINITE();
216
217    // During the slope calculation, ensure that ack time of the current packet is
218    // always larger than the time of the previous packet, otherwise division by
219    // zero or integer underflow can occur.
220    if (ack_time <= state->bwps_last_ack_ack_time)
221    {
222        BW_WARN_ONCE("Time of the previously acked packet (%"PRIu64") is "
223            "is larger than the ack time of the current packet (%"PRIu64")",
224            state->bwps_last_ack_ack_time, ack_time);
225        goto no_sample;
226    }
227
228    ack_rate = BW_FROM_BYTES_AND_DELTA(
229        sampler->bws_total_acked - state->bwps_send_state.total_bytes_acked,
230        ack_time - state->bwps_last_ack_ack_time);
231    LSQ_DEBUG("send rate: %"PRIu64"; ack rate: %"PRIu64, send_rate.value,
232                                                            ack_rate.value);
233
234    // Note: this sample does not account for delayed acknowledgement time.
235    // This means that the RTT measurements here can be artificially high,
236    // especially on low bandwidth connections.
237    rtt = ack_time - packet_out->po_sent;
238    is_app_limited = state->bwps_send_state.is_app_limited;
239
240    /* After this point, we switch `sample' to point to `state' and don't
241     * reference `state' anymore.
242     */
243    sample = (void *) packet_out->po_bwp_state;
244    packet_out->po_bwp_state = NULL;
245    if (BW_VALUE(&send_rate) < BW_VALUE(&ack_rate))
246        sample->bandwidth = send_rate;
247    else
248        sample->bandwidth = ack_rate;
249    sample->rtt = rtt;
250    sample->is_app_limited = is_app_limited;
251
252    LSQ_DEBUG("packet %"PRIu64" acked, bandwidth: %"PRIu64" bps",
253                        packet_out->po_packno, BW_VALUE(&sample->bandwidth));
254
255    return sample;
256
257  no_sample:
258    lsquic_malo_put(packet_out->po_bwp_state);
259    packet_out->po_bwp_state = NULL;
260    return NULL;;
261}
262
263
264unsigned
265lsquic_bw_sampler_entry_count (const struct bw_sampler *sampler)
266{
267    void *el;
268    unsigned count;
269
270    count = 0;
271    for (el = lsquic_malo_first(sampler->bws_malo); el;
272                                    el = lsquic_malo_next(sampler->bws_malo))
273        ++count;
274
275    return count;
276}
277