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