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