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