lsquic_bw_sampler.c revision a74702c6
1a74702c6SGeorge Wang/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc. See LICENSE. */ 25392f7a3SLiteSpeed Tech#include <assert.h> 35392f7a3SLiteSpeed Tech#include <inttypes.h> 45392f7a3SLiteSpeed Tech#include <stddef.h> 55392f7a3SLiteSpeed Tech#include <stdint.h> 65392f7a3SLiteSpeed Tech#include <sys/queue.h> 75392f7a3SLiteSpeed Tech 85392f7a3SLiteSpeed Tech#include "lsquic_int_types.h" 95392f7a3SLiteSpeed Tech#include "lsquic_types.h" 105392f7a3SLiteSpeed Tech#include "lsquic_hash.h" 115392f7a3SLiteSpeed Tech#include "lsquic.h" 125392f7a3SLiteSpeed Tech#include "lsquic_conn.h" 135392f7a3SLiteSpeed Tech#include "lsquic_malo.h" 145392f7a3SLiteSpeed Tech#include "lsquic_util.h" 155392f7a3SLiteSpeed Tech#include "lsquic_packet_common.h" 165392f7a3SLiteSpeed Tech#include "lsquic_packet_out.h" 175392f7a3SLiteSpeed Tech#include "lsquic_parse.h" 185392f7a3SLiteSpeed Tech#include "lsquic_bw_sampler.h" 195392f7a3SLiteSpeed Tech 205392f7a3SLiteSpeed Tech#define LSQUIC_LOGGER_MODULE LSQLM_BW_SAMPLER 215392f7a3SLiteSpeed Tech#define LSQUIC_LOG_CONN_ID lsquic_conn_log_cid(sampler->bws_conn) 225392f7a3SLiteSpeed Tech#include "lsquic_logger.h" 235392f7a3SLiteSpeed Tech 245392f7a3SLiteSpeed Tech 255392f7a3SLiteSpeed Techint 265392f7a3SLiteSpeed Techlsquic_bw_sampler_init (struct bw_sampler *sampler, struct lsquic_conn *conn, 275392f7a3SLiteSpeed Tech enum quic_ft_bit retx_frames) 285392f7a3SLiteSpeed Tech{ 295392f7a3SLiteSpeed Tech struct malo *malo; 305392f7a3SLiteSpeed Tech 315392f7a3SLiteSpeed Tech assert(lsquic_is_zero(sampler, sizeof(*sampler))); 325392f7a3SLiteSpeed Tech 335392f7a3SLiteSpeed Tech malo = lsquic_malo_create(sizeof(struct bwp_state)); 345392f7a3SLiteSpeed Tech if (!malo) 355392f7a3SLiteSpeed Tech return -1; 365392f7a3SLiteSpeed Tech 375392f7a3SLiteSpeed Tech sampler->bws_malo = malo; 385392f7a3SLiteSpeed Tech sampler->bws_conn = conn; 395392f7a3SLiteSpeed Tech sampler->bws_retx_frames = retx_frames; 402ed07212SDmitri Tikhonov sampler->bws_flags |= BWS_APP_LIMITED; 415392f7a3SLiteSpeed Tech LSQ_DEBUG("init"); 425392f7a3SLiteSpeed Tech return 0; 435392f7a3SLiteSpeed Tech} 445392f7a3SLiteSpeed Tech 455392f7a3SLiteSpeed Tech 465392f7a3SLiteSpeed Techvoid 475392f7a3SLiteSpeed Techlsquic_bw_sampler_app_limited (struct bw_sampler *sampler) 485392f7a3SLiteSpeed Tech{ 495392f7a3SLiteSpeed Tech sampler->bws_flags |= BWS_APP_LIMITED; 505392f7a3SLiteSpeed Tech sampler->bws_end_of_app_limited_phase = sampler->bws_last_sent_packno; 515392f7a3SLiteSpeed Tech LSQ_DEBUG("app limited, end of limited phase is %"PRIu64, 525392f7a3SLiteSpeed Tech sampler->bws_end_of_app_limited_phase); 535392f7a3SLiteSpeed Tech} 545392f7a3SLiteSpeed Tech 555392f7a3SLiteSpeed Tech 565392f7a3SLiteSpeed Techvoid 575392f7a3SLiteSpeed Techlsquic_bw_sampler_cleanup (struct bw_sampler *sampler) 585392f7a3SLiteSpeed Tech{ 595392f7a3SLiteSpeed Tech if (sampler->bws_conn) 605392f7a3SLiteSpeed Tech LSQ_DEBUG("cleanup"); 615392f7a3SLiteSpeed Tech if (sampler->bws_malo) 62b1a7c3f9SDmitri Tikhonov { 635392f7a3SLiteSpeed Tech lsquic_malo_destroy(sampler->bws_malo); 64b1a7c3f9SDmitri Tikhonov sampler->bws_malo = NULL; 65b1a7c3f9SDmitri Tikhonov } 665392f7a3SLiteSpeed Tech} 675392f7a3SLiteSpeed Tech 685392f7a3SLiteSpeed Tech 695392f7a3SLiteSpeed Tech/* This module only fails when it is unable to allocate memory. This rarely 705392f7a3SLiteSpeed Tech * happens, so we avoid having to check return values and abort the connection 715392f7a3SLiteSpeed Tech * instead. 725392f7a3SLiteSpeed Tech */ 735392f7a3SLiteSpeed Techstatic void 745392f7a3SLiteSpeed Techbw_sampler_abort_conn (struct bw_sampler *sampler) 755392f7a3SLiteSpeed Tech{ 765392f7a3SLiteSpeed Tech if (!(sampler->bws_flags & BWS_CONN_ABORTED)) 775392f7a3SLiteSpeed Tech { 785392f7a3SLiteSpeed Tech sampler->bws_flags |= BWS_CONN_ABORTED; 795392f7a3SLiteSpeed Tech LSQ_WARN("aborting connection"); 805392f7a3SLiteSpeed Tech sampler->bws_conn->cn_if->ci_internal_error(sampler->bws_conn, 815392f7a3SLiteSpeed Tech "resources exhausted"); 825392f7a3SLiteSpeed Tech } 835392f7a3SLiteSpeed Tech} 845392f7a3SLiteSpeed Tech 855392f7a3SLiteSpeed Tech 86fb3e20e0SDmitri Tikhonov#define BW_WARN_ONCE(...) do { \ 875392f7a3SLiteSpeed Tech if (!(sampler->bws_flags & BWS_WARNED)) \ 885392f7a3SLiteSpeed Tech { \ 895392f7a3SLiteSpeed Tech sampler->bws_flags |= BWS_WARNED; \ 90fb3e20e0SDmitri Tikhonov LSQ_WARN(__VA_ARGS__); \ 915392f7a3SLiteSpeed Tech } \ 925392f7a3SLiteSpeed Tech} while (0) 935392f7a3SLiteSpeed Tech 945392f7a3SLiteSpeed Techvoid 955392f7a3SLiteSpeed Techlsquic_bw_sampler_packet_sent (struct bw_sampler *sampler, 965392f7a3SLiteSpeed Tech struct lsquic_packet_out *packet_out, uint64_t in_flight) 975392f7a3SLiteSpeed Tech{ 985392f7a3SLiteSpeed Tech struct bwp_state *state; 995392f7a3SLiteSpeed Tech unsigned short sent_sz; 1005392f7a3SLiteSpeed Tech 1015392f7a3SLiteSpeed Tech if (packet_out->po_bwp_state) 1025392f7a3SLiteSpeed Tech { 1035392f7a3SLiteSpeed Tech BW_WARN_ONCE("sent: packet %"PRIu64" already has state", 1045392f7a3SLiteSpeed Tech packet_out->po_packno); 1055392f7a3SLiteSpeed Tech return; 1065392f7a3SLiteSpeed Tech } 1075392f7a3SLiteSpeed Tech 1085392f7a3SLiteSpeed Tech sampler->bws_last_sent_packno = packet_out->po_packno; 1095392f7a3SLiteSpeed Tech 1105392f7a3SLiteSpeed Tech if (!(packet_out->po_frame_types & sampler->bws_retx_frames)) 1115392f7a3SLiteSpeed Tech return; 1125392f7a3SLiteSpeed Tech 1135392f7a3SLiteSpeed Tech sent_sz = lsquic_packet_out_sent_sz(sampler->bws_conn, packet_out); 1145392f7a3SLiteSpeed Tech sampler->bws_total_sent += sent_sz; 1155392f7a3SLiteSpeed Tech 1165392f7a3SLiteSpeed Tech // If there are no packets in flight, the time at which the new transmission 1175392f7a3SLiteSpeed Tech // opens can be treated as the A_0 point for the purpose of bandwidth 1185392f7a3SLiteSpeed Tech // sampling. This underestimates bandwidth to some extent, and produces some 1195392f7a3SLiteSpeed Tech // artificially low samples for most packets in flight, but it provides with 1205392f7a3SLiteSpeed Tech // samples at important points where we would not have them otherwise, most 1215392f7a3SLiteSpeed Tech // importantly at the beginning of the connection. 1225392f7a3SLiteSpeed Tech if (in_flight == 0) 1235392f7a3SLiteSpeed Tech { 1245392f7a3SLiteSpeed Tech sampler->bws_last_acked_packet_time = packet_out->po_sent; 1255392f7a3SLiteSpeed Tech sampler->bws_last_acked_total_sent = sampler->bws_total_sent; 1265392f7a3SLiteSpeed Tech // In this situation ack compression is not a concern, set send rate to 1275392f7a3SLiteSpeed Tech // effectively infinite. 1285392f7a3SLiteSpeed Tech sampler->bws_last_acked_sent_time = packet_out->po_sent; 1295392f7a3SLiteSpeed Tech } 1305392f7a3SLiteSpeed Tech 1315392f7a3SLiteSpeed Tech state = lsquic_malo_get(sampler->bws_malo); 1325392f7a3SLiteSpeed Tech if (!state) 1335392f7a3SLiteSpeed Tech { 1345392f7a3SLiteSpeed Tech bw_sampler_abort_conn(sampler); 1355392f7a3SLiteSpeed Tech return; 1365392f7a3SLiteSpeed Tech } 1375392f7a3SLiteSpeed Tech 1385392f7a3SLiteSpeed Tech state->bwps_send_state = (struct bwps_send_state) { 1395392f7a3SLiteSpeed Tech .total_bytes_sent = sampler->bws_total_sent, 1405392f7a3SLiteSpeed Tech .total_bytes_acked = sampler->bws_total_acked, 1415392f7a3SLiteSpeed Tech .total_bytes_lost = sampler->bws_total_lost, 1425392f7a3SLiteSpeed Tech .is_app_limited = !!(sampler->bws_flags & BWS_APP_LIMITED), 1435392f7a3SLiteSpeed Tech }; 1445392f7a3SLiteSpeed Tech state->bwps_sent_at_last_ack = sampler->bws_last_acked_total_sent; 1455392f7a3SLiteSpeed Tech state->bwps_last_ack_sent_time = sampler->bws_last_acked_sent_time; 1465392f7a3SLiteSpeed Tech state->bwps_last_ack_ack_time = sampler->bws_last_acked_packet_time; 1475392f7a3SLiteSpeed Tech state->bwps_packet_size = sent_sz; 1485392f7a3SLiteSpeed Tech 1495392f7a3SLiteSpeed Tech packet_out->po_bwp_state = state; 1505392f7a3SLiteSpeed Tech 1515392f7a3SLiteSpeed Tech LSQ_DEBUG("add info for packet %"PRIu64, packet_out->po_packno); 1525392f7a3SLiteSpeed Tech} 1535392f7a3SLiteSpeed Tech 1545392f7a3SLiteSpeed Tech 1555392f7a3SLiteSpeed Techvoid 1565392f7a3SLiteSpeed Techlsquic_bw_sampler_packet_lost (struct bw_sampler *sampler, 1575392f7a3SLiteSpeed Tech struct lsquic_packet_out *packet_out) 1585392f7a3SLiteSpeed Tech{ 1595392f7a3SLiteSpeed Tech if (!packet_out->po_bwp_state) 1605392f7a3SLiteSpeed Tech return; 1615392f7a3SLiteSpeed Tech 1625392f7a3SLiteSpeed Tech sampler->bws_total_lost += packet_out->po_bwp_state->bwps_packet_size; 1635392f7a3SLiteSpeed Tech lsquic_malo_put(packet_out->po_bwp_state); 1645392f7a3SLiteSpeed Tech packet_out->po_bwp_state = NULL; 1655392f7a3SLiteSpeed Tech LSQ_DEBUG("packet %"PRIu64" lost, total_lost goes to %"PRIu64, 1665392f7a3SLiteSpeed Tech packet_out->po_packno, sampler->bws_total_lost); 1675392f7a3SLiteSpeed Tech} 1685392f7a3SLiteSpeed Tech 1695392f7a3SLiteSpeed Tech 1705392f7a3SLiteSpeed Techstruct bw_sample * 1715392f7a3SLiteSpeed Techlsquic_bw_sampler_packet_acked (struct bw_sampler *sampler, 1725392f7a3SLiteSpeed Tech struct lsquic_packet_out *packet_out, lsquic_time_t ack_time) 1735392f7a3SLiteSpeed Tech{ 1745392f7a3SLiteSpeed Tech const struct bwp_state *state; 1755392f7a3SLiteSpeed Tech struct bw_sample *sample; 1765392f7a3SLiteSpeed Tech struct bandwidth send_rate, ack_rate; 1775392f7a3SLiteSpeed Tech lsquic_time_t rtt; 1785392f7a3SLiteSpeed Tech unsigned short sent_sz; 1795392f7a3SLiteSpeed Tech int is_app_limited; 1805392f7a3SLiteSpeed Tech 1815392f7a3SLiteSpeed Tech if (!packet_out->po_bwp_state) 1825392f7a3SLiteSpeed Tech return 0; 1835392f7a3SLiteSpeed Tech 1845392f7a3SLiteSpeed Tech state = packet_out->po_bwp_state; 1855392f7a3SLiteSpeed Tech sent_sz = lsquic_packet_out_sent_sz(sampler->bws_conn, packet_out); 1865392f7a3SLiteSpeed Tech 1875392f7a3SLiteSpeed Tech sampler->bws_total_acked += sent_sz; 1885392f7a3SLiteSpeed Tech sampler->bws_last_acked_total_sent = state->bwps_send_state.total_bytes_sent; 1895392f7a3SLiteSpeed Tech sampler->bws_last_acked_sent_time = packet_out->po_sent; 1905392f7a3SLiteSpeed Tech sampler->bws_last_acked_packet_time = ack_time; 1915392f7a3SLiteSpeed Tech 1925392f7a3SLiteSpeed Tech // Exit app-limited phase once a packet that was sent while the connection 1935392f7a3SLiteSpeed Tech // is not app-limited is acknowledged. 1945392f7a3SLiteSpeed Tech if ((sampler->bws_flags & BWS_APP_LIMITED) 1955392f7a3SLiteSpeed Tech && packet_out->po_packno > sampler->bws_end_of_app_limited_phase) 1965392f7a3SLiteSpeed Tech { 1975392f7a3SLiteSpeed Tech sampler->bws_flags &= ~BWS_APP_LIMITED; 1985392f7a3SLiteSpeed Tech LSQ_DEBUG("exit app-limited phase due to packet %"PRIu64" being acked", 1995392f7a3SLiteSpeed Tech packet_out->po_packno); 2005392f7a3SLiteSpeed Tech } 2015392f7a3SLiteSpeed Tech 2025392f7a3SLiteSpeed Tech // There might have been no packets acknowledged at the moment when the 2035392f7a3SLiteSpeed Tech // current packet was sent. In that case, there is no bandwidth sample to 2045392f7a3SLiteSpeed Tech // make. 2055392f7a3SLiteSpeed Tech if (state->bwps_last_ack_sent_time == 0) 2065392f7a3SLiteSpeed Tech goto no_sample; 2075392f7a3SLiteSpeed Tech 2085392f7a3SLiteSpeed Tech // Infinite rate indicates that the sampler is supposed to discard the 2095392f7a3SLiteSpeed Tech // current send rate sample and use only the ack rate. 2105392f7a3SLiteSpeed Tech if (packet_out->po_sent > state->bwps_last_ack_sent_time) 2115392f7a3SLiteSpeed Tech send_rate = BW_FROM_BYTES_AND_DELTA( 2125392f7a3SLiteSpeed Tech state->bwps_send_state.total_bytes_sent 2135392f7a3SLiteSpeed Tech - state->bwps_sent_at_last_ack, 2145392f7a3SLiteSpeed Tech packet_out->po_sent - state->bwps_last_ack_sent_time); 2155392f7a3SLiteSpeed Tech else 2165392f7a3SLiteSpeed Tech send_rate = BW_INFINITE(); 2175392f7a3SLiteSpeed Tech 2185392f7a3SLiteSpeed Tech // During the slope calculation, ensure that ack time of the current packet is 2195392f7a3SLiteSpeed Tech // always larger than the time of the previous packet, otherwise division by 2205392f7a3SLiteSpeed Tech // zero or integer underflow can occur. 2215392f7a3SLiteSpeed Tech if (ack_time <= state->bwps_last_ack_ack_time) 2225392f7a3SLiteSpeed Tech { 2235392f7a3SLiteSpeed Tech BW_WARN_ONCE("Time of the previously acked packet (%"PRIu64") is " 2245392f7a3SLiteSpeed Tech "is larger than the ack time of the current packet (%"PRIu64")", 2255392f7a3SLiteSpeed Tech state->bwps_last_ack_ack_time, ack_time); 2265392f7a3SLiteSpeed Tech goto no_sample; 2275392f7a3SLiteSpeed Tech } 2285392f7a3SLiteSpeed Tech 2295392f7a3SLiteSpeed Tech ack_rate = BW_FROM_BYTES_AND_DELTA( 2305392f7a3SLiteSpeed Tech sampler->bws_total_acked - state->bwps_send_state.total_bytes_acked, 2315392f7a3SLiteSpeed Tech ack_time - state->bwps_last_ack_ack_time); 2325392f7a3SLiteSpeed Tech LSQ_DEBUG("send rate: %"PRIu64"; ack rate: %"PRIu64, send_rate.value, 2335392f7a3SLiteSpeed Tech ack_rate.value); 2345392f7a3SLiteSpeed Tech 2355392f7a3SLiteSpeed Tech // Note: this sample does not account for delayed acknowledgement time. 2365392f7a3SLiteSpeed Tech // This means that the RTT measurements here can be artificially high, 2375392f7a3SLiteSpeed Tech // especially on low bandwidth connections. 2385392f7a3SLiteSpeed Tech rtt = ack_time - packet_out->po_sent; 2395392f7a3SLiteSpeed Tech is_app_limited = state->bwps_send_state.is_app_limited; 2405392f7a3SLiteSpeed Tech 2415392f7a3SLiteSpeed Tech /* After this point, we switch `sample' to point to `state' and don't 2425392f7a3SLiteSpeed Tech * reference `state' anymore. 2435392f7a3SLiteSpeed Tech */ 2445392f7a3SLiteSpeed Tech sample = (void *) packet_out->po_bwp_state; 2455392f7a3SLiteSpeed Tech packet_out->po_bwp_state = NULL; 2465392f7a3SLiteSpeed Tech if (BW_VALUE(&send_rate) < BW_VALUE(&ack_rate)) 2475392f7a3SLiteSpeed Tech sample->bandwidth = send_rate; 2485392f7a3SLiteSpeed Tech else 2495392f7a3SLiteSpeed Tech sample->bandwidth = ack_rate; 2505392f7a3SLiteSpeed Tech sample->rtt = rtt; 2515392f7a3SLiteSpeed Tech sample->is_app_limited = is_app_limited; 2525392f7a3SLiteSpeed Tech 2535392f7a3SLiteSpeed Tech LSQ_DEBUG("packet %"PRIu64" acked, bandwidth: %"PRIu64" bps", 2545392f7a3SLiteSpeed Tech packet_out->po_packno, BW_VALUE(&sample->bandwidth)); 2555392f7a3SLiteSpeed Tech 2565392f7a3SLiteSpeed Tech return sample; 2575392f7a3SLiteSpeed Tech 2585392f7a3SLiteSpeed Tech no_sample: 2595392f7a3SLiteSpeed Tech lsquic_malo_put(packet_out->po_bwp_state); 2605392f7a3SLiteSpeed Tech packet_out->po_bwp_state = NULL; 2615392f7a3SLiteSpeed Tech return NULL;; 2625392f7a3SLiteSpeed Tech} 2635392f7a3SLiteSpeed Tech 2645392f7a3SLiteSpeed Tech 2655392f7a3SLiteSpeed Techunsigned 2665392f7a3SLiteSpeed Techlsquic_bw_sampler_entry_count (const struct bw_sampler *sampler) 2675392f7a3SLiteSpeed Tech{ 2685392f7a3SLiteSpeed Tech void *el; 2695392f7a3SLiteSpeed Tech unsigned count; 2705392f7a3SLiteSpeed Tech 2715392f7a3SLiteSpeed Tech count = 0; 2725392f7a3SLiteSpeed Tech for (el = lsquic_malo_first(sampler->bws_malo); el; 2735392f7a3SLiteSpeed Tech el = lsquic_malo_next(sampler->bws_malo)) 2745392f7a3SLiteSpeed Tech ++count; 2755392f7a3SLiteSpeed Tech 2765392f7a3SLiteSpeed Tech return count; 2775392f7a3SLiteSpeed Tech} 278