diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-09-12 04:44:07 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-09-12 04:44:07 +0000 |
| commit | bdd6bd04ba39d67eaf51ef77cba67321c787258e (patch) | |
| tree | b38069ef607224c4060da303320a4c7a9d71c671 /src/contrib | |
| parent | Adding upstream version 3.3.8. (diff) | |
| download | knot-bdd6bd04ba39d67eaf51ef77cba67321c787258e.tar.xz knot-bdd6bd04ba39d67eaf51ef77cba67321c787258e.zip | |
Adding upstream version 3.3.9.upstream/3.3.9
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/contrib')
29 files changed, 569 insertions, 572 deletions
diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_balloc.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_balloc.c index 5cc39ee..a270a43 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_balloc.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_balloc.c @@ -66,7 +66,7 @@ int ngtcp2_balloc_get(ngtcp2_balloc *balloc, void **pbuf, size_t n) { if (ngtcp2_buf_left(&balloc->buf) < n) { p = ngtcp2_mem_malloc(balloc->mem, - sizeof(ngtcp2_memblock_hd) + 0x10u + balloc->blklen); + sizeof(ngtcp2_memblock_hd) + 0x8u + balloc->blklen); if (p == NULL) { return NGTCP2_ERR_NOMEM; } diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_balloc.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_balloc.h index 1fb1632..9920987 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_balloc.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_balloc.h @@ -39,7 +39,10 @@ typedef struct ngtcp2_memblock_hd ngtcp2_memblock_hd; * ngtcp2_memblock_hd is the header of memory block. */ struct ngtcp2_memblock_hd { - ngtcp2_memblock_hd *next; + union { + ngtcp2_memblock_hd *next; + uint64_t pad; + }; }; /* diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_bbr.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_bbr.c index 2211a31..8b3845c 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_bbr.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_bbr.c @@ -39,8 +39,9 @@ #define NGTCP2_BBR_EXTRA_ACKED_FILTERLEN 10 #define NGTCP2_BBR_STARTUP_PACING_GAIN_H 277 +#define NGTCP2_BBR_DRAIN_PACING_GAIN_H 35 -#define NGTCP2_BBR_STARTUP_CWND_GAIN_H 200 +#define NGTCP2_BBR_DEFAULT_CWND_GAIN_H 200 #define NGTCP2_BBR_PROBE_RTT_CWND_GAIN_H 50 @@ -72,7 +73,7 @@ static void bbr_reset_lower_bounds(ngtcp2_cc_bbr *bbr); static void bbr_init_round_counting(ngtcp2_cc_bbr *bbr); -static void bbr_init_full_pipe(ngtcp2_cc_bbr *bbr); +static void bbr_reset_full_bw(ngtcp2_cc_bbr *bbr); static void bbr_init_pacing_rate(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat); @@ -84,8 +85,7 @@ static void bbr_set_pacing_rate(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat); static void bbr_enter_startup(ngtcp2_cc_bbr *bbr); -static void bbr_check_startup_done(ngtcp2_cc_bbr *bbr, - const ngtcp2_cc_ack *ack); +static void bbr_check_startup_done(ngtcp2_cc_bbr *bbr); static void bbr_update_on_ack(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts); @@ -148,16 +148,17 @@ static void bbr_start_probe_bw_cruise(ngtcp2_cc_bbr *bbr); static void bbr_start_probe_bw_refill(ngtcp2_cc_bbr *bbr); -static void bbr_start_probe_bw_up(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, - ngtcp2_tstamp ts); +static void bbr_start_probe_bw_up(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat); static void bbr_update_probe_bw_cycle_phase(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts); -static int bbr_check_time_to_cruise(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, - ngtcp2_tstamp ts); +static int bbr_is_time_to_cruise(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, + ngtcp2_tstamp ts); + +static int bbr_is_time_to_go_down(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat); static int bbr_has_elapsed_in_phase(ngtcp2_cc_bbr *bbr, ngtcp2_duration interval, ngtcp2_tstamp ts); @@ -175,9 +176,8 @@ static void bbr_probe_inflight_hi_upward(ngtcp2_cc_bbr *bbr, static void bbr_adapt_upper_bounds(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts); -static int bbr_check_time_to_probe_bw(ngtcp2_cc_bbr *bbr, - ngtcp2_conn_stat *cstat, - ngtcp2_tstamp ts); +static int bbr_is_time_to_probe_bw(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, + ngtcp2_tstamp ts); static void bbr_pick_probe_wait(ngtcp2_cc_bbr *bbr); @@ -197,6 +197,8 @@ static void bbr_handle_inflight_too_high(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, const ngtcp2_rs *rs, ngtcp2_tstamp ts); +static void bbr_note_loss(ngtcp2_cc_bbr *bbr); + static void bbr_handle_lost_packet(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts); @@ -227,15 +229,14 @@ static void bbr_handle_restart_from_idle(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts); -static uint64_t bbr_bdp_multiple(ngtcp2_cc_bbr *bbr, uint64_t bw, - uint64_t gain_h); +static uint64_t bbr_bdp_multiple(ngtcp2_cc_bbr *bbr, uint64_t gain_h); static uint64_t bbr_quantization_budget(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, uint64_t inflight); static uint64_t bbr_inflight(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, - uint64_t bw, uint64_t gain_h); + uint64_t gain_h); static void bbr_update_max_inflight(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat); @@ -247,10 +248,6 @@ static uint64_t min_pipe_cwnd(size_t max_udp_payload_size); static void bbr_advance_max_bw_filter(ngtcp2_cc_bbr *bbr); -static void bbr_modulate_cwnd_for_recovery(ngtcp2_cc_bbr *bbr, - ngtcp2_conn_stat *cstat, - const ngtcp2_cc_ack *ack); - static void bbr_save_cwnd(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat); static void bbr_restore_cwnd(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat); @@ -272,7 +269,7 @@ static int in_congestion_recovery(const ngtcp2_conn_stat *cstat, ngtcp2_tstamp sent_time); static void bbr_handle_recovery(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, - const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts); + const ngtcp2_cc_ack *ack); static void bbr_on_init(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, ngtcp2_tstamp initial_ts) { @@ -289,11 +286,12 @@ static void bbr_on_init(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, bbr->idle_restart = 0; bbr->extra_acked_interval_start = initial_ts; bbr->extra_acked_delivered = 0; + bbr->full_bw_reached = 0; bbr_reset_congestion_signals(bbr); bbr_reset_lower_bounds(bbr); bbr_init_round_counting(bbr); - bbr_init_full_pipe(bbr); + bbr_reset_full_bw(bbr); bbr_init_pacing_rate(bbr, cstat); bbr_enter_startup(bbr); @@ -326,23 +324,17 @@ static void bbr_on_init(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, bbr->bw_probe_up_acks = 0; bbr->inflight_hi = UINT64_MAX; - bbr->bw_hi = UINT64_MAX; bbr->probe_rtt_expired = 0; bbr->probe_rtt_min_delay = UINT64_MAX; bbr->probe_rtt_min_stamp = initial_ts; bbr->in_loss_recovery = 0; - bbr->packet_conservation = 0; + bbr->round_count_at_recovery = UINT64_MAX; bbr->max_inflight = 0; bbr->congestion_recovery_start_ts = UINT64_MAX; - bbr->congestion_recovery_next_round_delivered = 0; - - bbr->prior_inflight_lo = 0; - bbr->prior_inflight_hi = 0; - bbr->prior_bw_lo = 0; } static void bbr_reset_congestion_signals(ngtcp2_cc_bbr *bbr) { @@ -362,48 +354,53 @@ static void bbr_init_round_counting(ngtcp2_cc_bbr *bbr) { bbr->round_count = 0; } -static void bbr_init_full_pipe(ngtcp2_cc_bbr *bbr) { - bbr->filled_pipe = 0; +static void bbr_reset_full_bw(ngtcp2_cc_bbr *bbr) { bbr->full_bw = 0; bbr->full_bw_count = 0; + bbr->full_bw_now = 0; } -static void bbr_check_startup_full_bandwidth(ngtcp2_cc_bbr *bbr) { - if (bbr->filled_pipe || !bbr->round_start || bbr->rst->rs.is_app_limited) { +static void bbr_check_full_bw_reached(ngtcp2_cc_bbr *bbr, + ngtcp2_conn_stat *cstat) { + if (bbr->full_bw_now || bbr->rst->rs.is_app_limited) { return; } - if (bbr->max_bw * 100 >= bbr->full_bw * 125) { - bbr->full_bw = bbr->max_bw; - bbr->full_bw_count = 0; - } + if (cstat->delivery_rate_sec * 100 >= bbr->full_bw * 125) { + bbr_reset_full_bw(bbr); + bbr->full_bw = cstat->delivery_rate_sec; - ++bbr->full_bw_count; - - if (bbr->full_bw_count >= 3) { - bbr->filled_pipe = 1; - - ngtcp2_log_info(bbr->cc.log, NGTCP2_LOG_EVENT_CCA, - "bbr filled pipe, full_bw=%" PRIu64, bbr->full_bw); + return; } -} -static void bbr_check_startup_high_loss(ngtcp2_cc_bbr *bbr, - const ngtcp2_cc_ack *ack) { - if (bbr->filled_pipe || !bbr->round_start || bbr->rst->rs.is_app_limited) { + if (!bbr->round_start) { return; } - if (bbr->loss_events_in_round <= 3) { + ++bbr->full_bw_count; + + bbr->full_bw_now = bbr->full_bw_count >= 3; + if (!bbr->full_bw_now) { return; } - /* loss_thresh = 2% */ - if (bbr->bytes_lost_in_round * 100 <= ack->prior_bytes_in_flight * 2) { + bbr->full_bw_reached = 1; + + ngtcp2_log_info(bbr->cc.log, NGTCP2_LOG_EVENT_CCA, + "bbr reached full bandwidth, full_bw=%" PRIu64, bbr->full_bw); +} + +static void bbr_check_startup_high_loss(ngtcp2_cc_bbr *bbr) { + if (bbr->full_bw_reached || bbr->loss_events_in_round <= 6 || + (bbr->in_loss_recovery && + bbr->round_count <= bbr->round_count_at_recovery) || + !is_inflight_too_high(&bbr->rst->rs)) { return; } - bbr->filled_pipe = 1; + bbr->full_bw_reached = 1; + bbr->inflight_hi = ngtcp2_max_uint64(bbr_bdp_multiple(bbr, bbr->cwnd_gain_h), + bbr->inflight_latest); } static void bbr_init_pacing_rate(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat) { @@ -423,7 +420,7 @@ static void bbr_set_pacing_rate_with_gain(ngtcp2_cc_bbr *bbr, interval = NGTCP2_SECONDS * 100 * 100 / pacing_gain_h / bbr->bw / (100 - NGTCP2_BBR_PACING_MARGIN_PERCENT); - if (bbr->filled_pipe || interval < cstat->pacing_interval) { + if (bbr->full_bw_reached || interval < cstat->pacing_interval) { cstat->pacing_interval = interval; } } @@ -437,15 +434,13 @@ static void bbr_enter_startup(ngtcp2_cc_bbr *bbr) { bbr->state = NGTCP2_BBR_STATE_STARTUP; bbr->pacing_gain_h = NGTCP2_BBR_STARTUP_PACING_GAIN_H; - bbr->cwnd_gain_h = NGTCP2_BBR_STARTUP_CWND_GAIN_H; + bbr->cwnd_gain_h = NGTCP2_BBR_DEFAULT_CWND_GAIN_H; } -static void bbr_check_startup_done(ngtcp2_cc_bbr *bbr, - const ngtcp2_cc_ack *ack) { - bbr_check_startup_full_bandwidth(bbr); - bbr_check_startup_high_loss(bbr, ack); +static void bbr_check_startup_done(ngtcp2_cc_bbr *bbr) { + bbr_check_startup_high_loss(bbr); - if (bbr->state == NGTCP2_BBR_STATE_STARTUP && bbr->filled_pipe) { + if (bbr->state == NGTCP2_BBR_STATE_STARTUP && bbr->full_bw_reached) { bbr_enter_drain(bbr); } } @@ -468,7 +463,8 @@ static void bbr_update_model_and_state(ngtcp2_cc_bbr *bbr, bbr_update_latest_delivery_signals(bbr, cstat); bbr_update_congestion_signals(bbr, cstat, ack); bbr_update_ack_aggregation(bbr, cstat, ack, ts); - bbr_check_startup_done(bbr, ack); + bbr_check_full_bw_reached(bbr, cstat); + bbr_check_startup_done(bbr); bbr_check_drain(bbr, cstat, ts); bbr_update_probe_bw_cycle_phase(bbr, cstat, ack, ts); bbr_update_min_rtt(bbr, ack, ts); @@ -519,11 +515,6 @@ static void bbr_update_congestion_signals(ngtcp2_cc_bbr *bbr, if (ack->bytes_lost) { bbr->bytes_lost_in_round += ack->bytes_lost; ++bbr->loss_events_in_round; - - if (!bbr->loss_in_round) { - bbr->loss_in_round = 1; - bbr->loss_round_delivered = bbr->rst->delivered; - } } if (!bbr->loss_round_start) { @@ -568,7 +559,6 @@ static void bbr_loss_lower_bounds(ngtcp2_cc_bbr *bbr) { static void bbr_bound_bw_for_model(ngtcp2_cc_bbr *bbr) { bbr->bw = ngtcp2_min_uint64(bbr->max_bw, bbr->bw_lo); - bbr->bw = ngtcp2_min_uint64(bbr->bw, bbr->bw_hi); } static void bbr_update_max_bw(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, @@ -636,6 +626,12 @@ static void bbr_update_ack_aggregation(ngtcp2_cc_bbr *bbr, extra = bbr->extra_acked_delivered - expected_delivered; extra = ngtcp2_min_uint64(extra, cstat->cwnd); + if (bbr->full_bw_reached) { + bbr->extra_acked_filter.window_length = NGTCP2_BBR_EXTRA_ACKED_FILTERLEN; + } else { + bbr->extra_acked_filter.window_length = 1; + } + ngtcp2_window_filter_update(&bbr->extra_acked_filter, extra, bbr->round_count); @@ -646,14 +642,14 @@ static void bbr_enter_drain(ngtcp2_cc_bbr *bbr) { ngtcp2_log_info(bbr->cc.log, NGTCP2_LOG_EVENT_CCA, "bbr enter Drain"); bbr->state = NGTCP2_BBR_STATE_DRAIN; - bbr->pacing_gain_h = 100 * 100 / NGTCP2_BBR_STARTUP_CWND_GAIN_H; - bbr->cwnd_gain_h = NGTCP2_BBR_STARTUP_CWND_GAIN_H; + bbr->pacing_gain_h = NGTCP2_BBR_DRAIN_PACING_GAIN_H; + bbr->cwnd_gain_h = NGTCP2_BBR_DEFAULT_CWND_GAIN_H; } static void bbr_check_drain(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, ngtcp2_tstamp ts) { if (bbr->state == NGTCP2_BBR_STATE_DRAIN && - cstat->bytes_in_flight <= bbr_inflight(bbr, cstat, bbr->bw, 100)) { + cstat->bytes_in_flight <= bbr_inflight(bbr, cstat, 100)) { bbr_enter_probe_bw(bbr, ts); } } @@ -678,7 +674,7 @@ static void bbr_start_probe_bw_down(ngtcp2_cc_bbr *bbr, ngtcp2_tstamp ts) { bbr->state = NGTCP2_BBR_STATE_PROBE_BW_DOWN; bbr->pacing_gain_h = 90; - bbr->cwnd_gain_h = 200; + bbr->cwnd_gain_h = NGTCP2_BBR_DEFAULT_CWND_GAIN_H; } static void bbr_start_probe_bw_cruise(ngtcp2_cc_bbr *bbr) { @@ -687,7 +683,7 @@ static void bbr_start_probe_bw_cruise(ngtcp2_cc_bbr *bbr) { bbr->state = NGTCP2_BBR_STATE_PROBE_BW_CRUISE; bbr->pacing_gain_h = 100; - bbr->cwnd_gain_h = 200; + bbr->cwnd_gain_h = NGTCP2_BBR_DEFAULT_CWND_GAIN_H; } static void bbr_start_probe_bw_refill(ngtcp2_cc_bbr *bbr) { @@ -704,18 +700,18 @@ static void bbr_start_probe_bw_refill(ngtcp2_cc_bbr *bbr) { bbr->state = NGTCP2_BBR_STATE_PROBE_BW_REFILL; bbr->pacing_gain_h = 100; - bbr->cwnd_gain_h = 200; + bbr->cwnd_gain_h = NGTCP2_BBR_DEFAULT_CWND_GAIN_H; } -static void bbr_start_probe_bw_up(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, - ngtcp2_tstamp ts) { +static void bbr_start_probe_bw_up(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat) { ngtcp2_log_info(bbr->cc.log, NGTCP2_LOG_EVENT_CCA, "bbr start ProbeBW_UP"); bbr->ack_phase = NGTCP2_BBR_ACK_PHASE_ACKS_PROBE_STARTING; bbr_start_round(bbr); + bbr_reset_full_bw(bbr); - bbr->cycle_stamp = ts; + bbr->full_bw = cstat->delivery_rate_sec; bbr->state = NGTCP2_BBR_STATE_PROBE_BW_UP; bbr->pacing_gain_h = 125; bbr->cwnd_gain_h = 225; @@ -727,7 +723,7 @@ static void bbr_update_probe_bw_cycle_phase(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts) { - if (!bbr->filled_pipe) { + if (!bbr->full_bw_reached) { return; } @@ -739,17 +735,17 @@ static void bbr_update_probe_bw_cycle_phase(ngtcp2_cc_bbr *bbr, switch (bbr->state) { case NGTCP2_BBR_STATE_PROBE_BW_DOWN: - if (bbr_check_time_to_probe_bw(bbr, cstat, ts)) { + if (bbr_is_time_to_probe_bw(bbr, cstat, ts)) { return; } - if (bbr_check_time_to_cruise(bbr, cstat, ts)) { + if (bbr_is_time_to_cruise(bbr, cstat, ts)) { bbr_start_probe_bw_cruise(bbr); } break; case NGTCP2_BBR_STATE_PROBE_BW_CRUISE: - if (bbr_check_time_to_probe_bw(bbr, cstat, ts)) { + if (bbr_is_time_to_probe_bw(bbr, cstat, ts)) { return; } @@ -757,13 +753,12 @@ static void bbr_update_probe_bw_cycle_phase(ngtcp2_cc_bbr *bbr, case NGTCP2_BBR_STATE_PROBE_BW_REFILL: if (bbr->round_start) { bbr->bw_probe_samples = 1; - bbr_start_probe_bw_up(bbr, cstat, ts); + bbr_start_probe_bw_up(bbr, cstat); } break; case NGTCP2_BBR_STATE_PROBE_BW_UP: - if (bbr_has_elapsed_in_phase(bbr, bbr->min_rtt, ts) && - cstat->bytes_in_flight > bbr_inflight(bbr, cstat, bbr->max_bw, 125)) { + if (bbr_is_time_to_go_down(bbr, cstat)) { bbr_start_probe_bw_down(bbr, ts); } @@ -773,15 +768,26 @@ static void bbr_update_probe_bw_cycle_phase(ngtcp2_cc_bbr *bbr, } } -static int bbr_check_time_to_cruise(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, - ngtcp2_tstamp ts) { +static int bbr_is_time_to_cruise(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, + ngtcp2_tstamp ts) { (void)ts; if (cstat->bytes_in_flight > bbr_inflight_with_headroom(bbr, cstat)) { return 0; } - if (cstat->bytes_in_flight <= bbr_inflight(bbr, cstat, bbr->max_bw, 100)) { + if (cstat->bytes_in_flight <= bbr_inflight(bbr, cstat, 100)) { + return 1; + } + + return 0; +} + +static int bbr_is_time_to_go_down(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat) { + if (bbr->rst->is_cwnd_limited && cstat->cwnd >= bbr->inflight_hi) { + bbr_reset_full_bw(bbr); + bbr->full_bw = cstat->delivery_rate_sec; + } else if (bbr->full_bw_now) { return 1; } @@ -861,8 +867,7 @@ static void bbr_adapt_upper_bounds(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, } if (!bbr_check_inflight_too_high(bbr, cstat, ts)) { - /* bbr->bw_hi never be updated */ - if (bbr->inflight_hi == UINT64_MAX /* || bbr->bw_hi == UINT64_MAX */) { + if (bbr->inflight_hi == UINT64_MAX) { return; } @@ -870,19 +875,14 @@ static void bbr_adapt_upper_bounds(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, bbr->inflight_hi = bbr->rst->rs.tx_in_flight; } - if (cstat->delivery_rate_sec > bbr->bw_hi) { - bbr->bw_hi = cstat->delivery_rate_sec; - } - if (bbr->state == NGTCP2_BBR_STATE_PROBE_BW_UP) { bbr_probe_inflight_hi_upward(bbr, cstat, ack); } } } -static int bbr_check_time_to_probe_bw(ngtcp2_cc_bbr *bbr, - ngtcp2_conn_stat *cstat, - ngtcp2_tstamp ts) { +static int bbr_is_time_to_probe_bw(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, + ngtcp2_tstamp ts) { if (bbr_has_elapsed_in_phase(bbr, bbr->bw_probe_wait, ts) || bbr_is_reno_coexistence_probe_time(bbr, cstat)) { bbr_start_probe_bw_refill(bbr); @@ -916,7 +916,7 @@ static int bbr_is_reno_coexistence_probe_time(ngtcp2_cc_bbr *bbr, static uint64_t bbr_target_inflight(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat) { - uint64_t bdp = bbr_inflight(bbr, cstat, bbr->bw, 100); + uint64_t bdp = bbr_bdp_multiple(bbr, bbr->cwnd_gain_h); return ngtcp2_min_uint64(bdp, cstat->cwnd); } @@ -957,10 +957,21 @@ static void bbr_handle_inflight_too_high(ngtcp2_cc_bbr *bbr, } } +static void bbr_note_loss(ngtcp2_cc_bbr *bbr) { + if (bbr->loss_in_round) { + return; + } + + bbr->loss_in_round = 1; + bbr->loss_round_delivered = bbr->rst->delivered; +} + static void bbr_handle_lost_packet(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts) { ngtcp2_rs rs = {0}; + bbr_note_loss(bbr); + if (!bbr->bw_probe_samples) { return; } @@ -1107,7 +1118,7 @@ static void bbr_mark_connection_app_limited(ngtcp2_cc_bbr *bbr, static void bbr_exit_probe_rtt(ngtcp2_cc_bbr *bbr, ngtcp2_tstamp ts) { bbr_reset_lower_bounds(bbr); - if (bbr->filled_pipe) { + if (bbr->full_bw_reached) { bbr_start_probe_bw_down(bbr, ts); bbr_start_probe_bw_cruise(bbr); } else { @@ -1132,15 +1143,14 @@ static void bbr_handle_restart_from_idle(ngtcp2_cc_bbr *bbr, } } -static uint64_t bbr_bdp_multiple(ngtcp2_cc_bbr *bbr, uint64_t bw, - uint64_t gain_h) { +static uint64_t bbr_bdp_multiple(ngtcp2_cc_bbr *bbr, uint64_t gain_h) { uint64_t bdp; if (bbr->min_rtt == UINT64_MAX) { return bbr->initial_cwnd; } - bdp = bw * bbr->min_rtt / NGTCP2_SECONDS; + bdp = bbr->bw * bbr->min_rtt / NGTCP2_SECONDS; return (uint64_t)(bdp * gain_h / 100); } @@ -1166,8 +1176,8 @@ static uint64_t bbr_quantization_budget(ngtcp2_cc_bbr *bbr, } static uint64_t bbr_inflight(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, - uint64_t bw, uint64_t gain_h) { - uint64_t inflight = bbr_bdp_multiple(bbr, bw, gain_h); + uint64_t gain_h) { + uint64_t inflight = bbr_bdp_multiple(bbr, gain_h); return bbr_quantization_budget(bbr, cstat, inflight); } @@ -1179,8 +1189,7 @@ static void bbr_update_max_inflight(ngtcp2_cc_bbr *bbr, /* Not documented */ /* bbr_update_aggregation_budget(bbr); */ - inflight = - bbr_bdp_multiple(bbr, bbr->bw, bbr->cwnd_gain_h) + bbr->extra_acked; + inflight = bbr_bdp_multiple(bbr, bbr->cwnd_gain_h) + bbr->extra_acked; bbr->max_inflight = bbr_quantization_budget(bbr, cstat, inflight); } @@ -1193,25 +1202,6 @@ static void bbr_advance_max_bw_filter(ngtcp2_cc_bbr *bbr) { ++bbr->cycle_count; } -static void bbr_modulate_cwnd_for_recovery(ngtcp2_cc_bbr *bbr, - ngtcp2_conn_stat *cstat, - const ngtcp2_cc_ack *ack) { - if (ack->bytes_lost > 0) { - if (cstat->cwnd > ack->bytes_lost) { - cstat->cwnd -= ack->bytes_lost; - cstat->cwnd = - ngtcp2_max_uint64(cstat->cwnd, 2 * cstat->max_tx_udp_payload_size); - } else { - cstat->cwnd = 2 * cstat->max_tx_udp_payload_size; - } - } - - if (bbr->packet_conservation) { - cstat->cwnd = ngtcp2_max_uint64(cstat->cwnd, cstat->bytes_in_flight + - ack->bytes_delivered); - } -} - static void bbr_save_cwnd(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat) { if (!bbr->in_loss_recovery && bbr->state != NGTCP2_BBR_STATE_PROBE_RTT) { bbr->prior_cwnd = cstat->cwnd; @@ -1228,7 +1218,7 @@ static void bbr_restore_cwnd(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat) { static uint64_t bbr_probe_rtt_cwnd(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat) { uint64_t probe_rtt_cwnd = - bbr_bdp_multiple(bbr, bbr->bw, NGTCP2_BBR_PROBE_RTT_CWND_GAIN_H); + bbr_bdp_multiple(bbr, NGTCP2_BBR_PROBE_RTT_CWND_GAIN_H); uint64_t mpcwnd = min_pipe_cwnd(cstat->max_tx_udp_payload_size); return ngtcp2_max_uint64(probe_rtt_cwnd, mpcwnd); @@ -1250,21 +1240,18 @@ static void bbr_set_cwnd(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, uint64_t mpcwnd; bbr_update_max_inflight(bbr, cstat); - bbr_modulate_cwnd_for_recovery(bbr, cstat, ack); - - if (!bbr->packet_conservation) { - if (bbr->filled_pipe) { - cstat->cwnd += ack->bytes_delivered; - cstat->cwnd = ngtcp2_min_uint64(cstat->cwnd, bbr->max_inflight); - } else if (cstat->cwnd < bbr->max_inflight || - bbr->rst->delivered < bbr->initial_cwnd) { - cstat->cwnd += ack->bytes_delivered; - } - mpcwnd = min_pipe_cwnd(cstat->max_tx_udp_payload_size); - cstat->cwnd = ngtcp2_max_uint64(cstat->cwnd, mpcwnd); + if (bbr->full_bw_reached) { + cstat->cwnd += ack->bytes_delivered; + cstat->cwnd = ngtcp2_min_uint64(cstat->cwnd, bbr->max_inflight); + } else if (cstat->cwnd < bbr->max_inflight || + bbr->rst->delivered < bbr->initial_cwnd) { + cstat->cwnd += ack->bytes_delivered; } + mpcwnd = min_pipe_cwnd(cstat->max_tx_udp_payload_size); + cstat->cwnd = ngtcp2_max_uint64(cstat->cwnd, mpcwnd); + bbr_bound_cwnd_for_probe_rtt(bbr, cstat); bbr_bound_cwnd_for_model(bbr, cstat); } @@ -1289,23 +1276,16 @@ static void bbr_bound_cwnd_for_model(ngtcp2_cc_bbr *bbr, } static void bbr_set_send_quantum(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat) { - size_t floor, send_quantum; + size_t send_quantum = 64 * 1024; (void)bbr; - if (cstat->pacing_interval > (NGTCP2_SECONDS * 8 * 10 / 12) >> 20) { - floor = cstat->max_tx_udp_payload_size; - } else { - floor = 2 * cstat->max_tx_udp_payload_size; - } - if (cstat->pacing_interval) { - send_quantum = (size_t)(NGTCP2_MILLISECONDS / cstat->pacing_interval); - send_quantum = ngtcp2_min_size(send_quantum, 64 * 1024); - } else { - send_quantum = 64 * 1024; + send_quantum = ngtcp2_min_size( + send_quantum, (size_t)(NGTCP2_MILLISECONDS / cstat->pacing_interval)); } - cstat->send_quantum = ngtcp2_max_size(send_quantum, floor); + cstat->send_quantum = + ngtcp2_max_size(send_quantum, 2 * cstat->max_tx_udp_payload_size); } static int in_congestion_recovery(const ngtcp2_conn_stat *cstat, @@ -1315,16 +1295,12 @@ static int in_congestion_recovery(const ngtcp2_conn_stat *cstat, } static void bbr_handle_recovery(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, - const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts) { + const ngtcp2_cc_ack *ack) { if (bbr->in_loss_recovery) { - if (ts - cstat->congestion_recovery_start_ts >= cstat->smoothed_rtt) { - bbr->packet_conservation = 0; - } - if (ack->largest_pkt_sent_ts != UINT64_MAX && !in_congestion_recovery(cstat, ack->largest_pkt_sent_ts)) { bbr->in_loss_recovery = 0; - bbr->packet_conservation = 0; + bbr->round_count_at_recovery = UINT64_MAX; bbr_restore_cwnd(bbr, cstat); } @@ -1333,6 +1309,8 @@ static void bbr_handle_recovery(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, if (bbr->congestion_recovery_start_ts != UINT64_MAX) { bbr->in_loss_recovery = 1; + bbr->round_count_at_recovery = + bbr->round_start ? bbr->round_count : bbr->round_count + 1; bbr_save_cwnd(bbr, cstat); cstat->cwnd = cstat->bytes_in_flight + @@ -1340,11 +1318,6 @@ static void bbr_handle_recovery(ngtcp2_cc_bbr *bbr, ngtcp2_conn_stat *cstat, cstat->congestion_recovery_start_ts = bbr->congestion_recovery_start_ts; bbr->congestion_recovery_start_ts = UINT64_MAX; - bbr->packet_conservation = 1; - bbr->congestion_recovery_next_round_delivered = bbr->rst->delivered; - bbr->prior_inflight_hi = bbr->inflight_hi; - bbr->prior_inflight_lo = bbr->inflight_lo; - bbr->prior_bw_lo = bbr->bw_lo; } } @@ -1352,6 +1325,10 @@ static void bbr_cc_on_pkt_lost(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts) { ngtcp2_cc_bbr *bbr = ngtcp2_struct_of(cc, ngtcp2_cc_bbr, cc); + if (bbr->state == NGTCP2_BBR_STATE_STARTUP) { + return; + } + bbr_update_on_loss(bbr, cstat, pkt, ts); } @@ -1379,15 +1356,8 @@ static void bbr_cc_on_spurious_congestion(ngtcp2_cc *cc, if (bbr->in_loss_recovery) { bbr->in_loss_recovery = 0; - bbr->packet_conservation = 0; + bbr->round_count_at_recovery = UINT64_MAX; bbr_restore_cwnd(bbr, cstat); - bbr->full_bw_count = 0; - bbr->loss_in_round = 0; - bbr->inflight_lo = - ngtcp2_max_uint64(bbr->inflight_lo, bbr->prior_inflight_lo); - bbr->inflight_hi = - ngtcp2_max_uint64(bbr->inflight_hi, bbr->prior_inflight_hi); - bbr->bw_lo = ngtcp2_max_uint64(bbr->bw_lo, bbr->prior_bw_lo); } } @@ -1400,7 +1370,7 @@ static void bbr_cc_on_persistent_congestion(ngtcp2_cc *cc, cstat->congestion_recovery_start_ts = UINT64_MAX; bbr->congestion_recovery_start_ts = UINT64_MAX; bbr->in_loss_recovery = 0; - bbr->packet_conservation = 0; + bbr->round_count_at_recovery = UINT64_MAX; bbr_save_cwnd(bbr, cstat); cstat->cwnd = cstat->bytes_in_flight + cstat->max_tx_udp_payload_size; @@ -1412,7 +1382,7 @@ static void bbr_cc_on_ack_recv(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts) { ngtcp2_cc_bbr *bbr = ngtcp2_struct_of(cc, ngtcp2_cc_bbr, cc); - bbr_handle_recovery(bbr, cstat, ack, ts); + bbr_handle_recovery(bbr, cstat, ack); bbr_update_on_ack(bbr, cstat, ack, ts); } diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_bbr.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_bbr.h index 0017be3..097d0fe 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_bbr.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_bbr.h @@ -95,9 +95,10 @@ typedef struct ngtcp2_cc_bbr { uint64_t round_count; /* Full pipe */ - int filled_pipe; uint64_t full_bw; size_t full_bw_count; + int full_bw_reached; + int full_bw_now; /* Pacing rate */ uint64_t pacing_gain_h; @@ -123,19 +124,13 @@ typedef struct ngtcp2_cc_bbr { size_t bw_probe_up_rounds; uint64_t bw_probe_up_acks; uint64_t inflight_hi; - uint64_t bw_hi; int probe_rtt_expired; ngtcp2_duration probe_rtt_min_delay; ngtcp2_tstamp probe_rtt_min_stamp; int in_loss_recovery; - int packet_conservation; + uint64_t round_count_at_recovery; uint64_t max_inflight; ngtcp2_tstamp congestion_recovery_start_ts; - uint64_t congestion_recovery_next_round_delivered; - - uint64_t prior_inflight_lo; - uint64_t prior_inflight_hi; - uint64_t prior_bw_lo; } ngtcp2_cc_bbr; void ngtcp2_cc_bbr_init(ngtcp2_cc_bbr *bbr, ngtcp2_log *log, diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_conn.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_conn.c index a5a47b7..0e272c8 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_conn.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_conn.c @@ -1167,9 +1167,9 @@ static int conn_new(ngtcp2_conn **pconn, const ngtcp2_cid *dcid, ngtcp2_pq_init(&(*pconn)->tx.strmq, cycle_less, mem); - ngtcp2_idtr_init(&(*pconn)->remote.bidi.idtr, !server, mem); + ngtcp2_idtr_init(&(*pconn)->remote.bidi.idtr, mem); - ngtcp2_idtr_init(&(*pconn)->remote.uni.idtr, !server, mem); + ngtcp2_idtr_init(&(*pconn)->remote.uni.idtr, mem); ngtcp2_static_ringbuf_path_challenge_init(&(*pconn)->rx.path_challenge); @@ -1604,7 +1604,7 @@ void ngtcp2_conn_del(ngtcp2_conn *conn) { ngtcp2_idtr_free(&conn->remote.bidi.idtr); ngtcp2_mem_free(conn->mem, conn->tx.ack); ngtcp2_pq_free(&conn->tx.strmq); - ngtcp2_map_each_free(&conn->strms, delete_strms_each, (void *)conn); + ngtcp2_map_each(&conn->strms, delete_strms_each, (void *)conn); ngtcp2_map_free(&conn->strms); ngtcp2_pq_free(&conn->scid.used); @@ -12729,7 +12729,7 @@ static void conn_discard_early_data_state(ngtcp2_conn *conn) { ngtcp2_rtb_remove_early_data(&conn->pktns.rtb, &conn->cstat); - ngtcp2_map_each_free(&conn->strms, delete_strms_pq_each, conn); + ngtcp2_map_each(&conn->strms, delete_strms_pq_each, conn); ngtcp2_map_clear(&conn->strms); conn->tx.offset = 0; diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_gaptr.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_gaptr.c index 87c2389..6f8e055 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_gaptr.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_gaptr.c @@ -36,14 +36,8 @@ void ngtcp2_gaptr_init(ngtcp2_gaptr *gaptr, const ngtcp2_mem *mem) { static int gaptr_gap_init(ngtcp2_gaptr *gaptr) { ngtcp2_range range = {0, UINT64_MAX}; - int rv; - - rv = ngtcp2_ksl_insert(&gaptr->gap, NULL, &range, NULL); - if (rv != 0) { - return rv; - } - return 0; + return ngtcp2_ksl_insert(&gaptr->gap, NULL, &range, NULL); } void ngtcp2_gaptr_free(ngtcp2_gaptr *gaptr) { @@ -80,7 +74,9 @@ int ngtcp2_gaptr_push(ngtcp2_gaptr *gaptr, uint64_t offset, uint64_t datalen) { ngtcp2_ksl_remove_hint(&gaptr->gap, &it, &it, &k); continue; } + ngtcp2_range_cut(&l, &r, &k, &m); + if (ngtcp2_range_len(&l)) { ngtcp2_ksl_update_key(&gaptr->gap, &k, &l); @@ -93,23 +89,23 @@ int ngtcp2_gaptr_push(ngtcp2_gaptr *gaptr, uint64_t offset, uint64_t datalen) { } else if (ngtcp2_range_len(&r)) { ngtcp2_ksl_update_key(&gaptr->gap, &k, &r); } + ngtcp2_ksl_it_next(&it); } + return 0; } uint64_t ngtcp2_gaptr_first_gap_offset(ngtcp2_gaptr *gaptr) { ngtcp2_ksl_it it; - ngtcp2_range r; if (ngtcp2_ksl_len(&gaptr->gap) == 0) { return 0; } it = ngtcp2_ksl_begin(&gaptr->gap); - r = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it); - return r.begin; + return ((ngtcp2_range *)ngtcp2_ksl_it_key(&it))->begin; } ngtcp2_range ngtcp2_gaptr_get_first_gap_after(ngtcp2_gaptr *gaptr, @@ -134,7 +130,6 @@ int ngtcp2_gaptr_is_pushed(ngtcp2_gaptr *gaptr, uint64_t offset, uint64_t datalen) { ngtcp2_range q = {offset, offset + datalen}; ngtcp2_ksl_it it; - ngtcp2_range k; ngtcp2_range m; if (ngtcp2_ksl_len(&gaptr->gap) == 0) { @@ -143,8 +138,7 @@ int ngtcp2_gaptr_is_pushed(ngtcp2_gaptr *gaptr, uint64_t offset, it = ngtcp2_ksl_lower_bound_compar(&gaptr->gap, &q, ngtcp2_ksl_range_exclusive_compar); - k = *(ngtcp2_range *)ngtcp2_ksl_it_key(&it); - m = ngtcp2_range_intersect(&q, &k); + m = ngtcp2_range_intersect(&q, (ngtcp2_range *)ngtcp2_ksl_it_key(&it)); return ngtcp2_range_len(&m) == 0; } diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_gaptr.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_gaptr.h index 0f100a8..e3fea1c 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_gaptr.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_gaptr.h @@ -39,8 +39,9 @@ * ngtcp2_gaptr maintains the gap in the range [0, UINT64_MAX). */ typedef struct ngtcp2_gaptr { - /* gap maintains the range of offset which is not received - yet. Initially, its range is [0, UINT64_MAX). */ + /* gap maintains the range of offset which is not pushed + yet. Initially, its range is [0, UINT64_MAX). "gap" is the range + that is not pushed yet. */ ngtcp2_ksl gap; /* mem is custom memory allocator */ const ngtcp2_mem *mem; @@ -57,8 +58,7 @@ void ngtcp2_gaptr_init(ngtcp2_gaptr *gaptr, const ngtcp2_mem *mem); void ngtcp2_gaptr_free(ngtcp2_gaptr *gaptr); /* - * ngtcp2_gaptr_push adds new data of length |datalen| at the stream - * offset |offset|. + * ngtcp2_gaptr_push pushes the range [offset, offset + datalen). * * This function returns 0 if it succeeds, or one of the following * negative error codes: @@ -76,7 +76,7 @@ uint64_t ngtcp2_gaptr_first_gap_offset(ngtcp2_gaptr *gaptr); /* * ngtcp2_gaptr_get_first_gap_after returns the first gap which - * overlaps or comes after |offset|. + * includes or comes after |offset|. */ ngtcp2_range ngtcp2_gaptr_get_first_gap_after(ngtcp2_gaptr *gaptr, uint64_t offset); diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_idtr.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_idtr.c index d988022..93c6ac9 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_idtr.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_idtr.c @@ -26,10 +26,8 @@ #include <assert.h> -void ngtcp2_idtr_init(ngtcp2_idtr *idtr, int server, const ngtcp2_mem *mem) { +void ngtcp2_idtr_init(ngtcp2_idtr *idtr, const ngtcp2_mem *mem) { ngtcp2_gaptr_init(&idtr->gap, mem); - - idtr->server = server; } void ngtcp2_idtr_free(ngtcp2_idtr *idtr) { @@ -41,8 +39,7 @@ void ngtcp2_idtr_free(ngtcp2_idtr *idtr) { } /* - * id_from_stream_id translates |stream_id| to id space used by - * ngtcp2_idtr. + * id_from_stream_id translates |stream_id| to an internal ID. */ static uint64_t id_from_stream_id(int64_t stream_id) { return (uint64_t)(stream_id >> 2); @@ -51,9 +48,6 @@ static uint64_t id_from_stream_id(int64_t stream_id) { int ngtcp2_idtr_open(ngtcp2_idtr *idtr, int64_t stream_id) { uint64_t q; - assert((idtr->server && (stream_id % 2)) || - (!idtr->server && (stream_id % 2)) == 0); - q = id_from_stream_id(stream_id); if (ngtcp2_gaptr_is_pushed(&idtr->gap, q, 1)) { @@ -66,14 +60,7 @@ int ngtcp2_idtr_open(ngtcp2_idtr *idtr, int64_t stream_id) { int ngtcp2_idtr_is_open(ngtcp2_idtr *idtr, int64_t stream_id) { uint64_t q; - assert((idtr->server && (stream_id % 2)) || - (!idtr->server && (stream_id % 2)) == 0); - q = id_from_stream_id(stream_id); return ngtcp2_gaptr_is_pushed(&idtr->gap, q, 1); } - -uint64_t ngtcp2_idtr_first_gap(ngtcp2_idtr *idtr) { - return ngtcp2_gaptr_first_gap_offset(&idtr->gap); -} diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_idtr.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_idtr.h index edb8c68..cdb2b61 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_idtr.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_idtr.h @@ -38,21 +38,17 @@ * ngtcp2_idtr tracks the usage of stream ID. */ typedef struct ngtcp2_idtr { - /* gap maintains the range of ID which is not used yet. Initially, - its range is [0, UINT64_MAX). */ + /* gap maintains the range of an internal ID which is not used yet. + Initially, its range is [0, UINT64_MAX). The internal ID and + stream ID are in the different number spaces. See + id_from_stream_id to convert a stream ID to an internal ID. */ ngtcp2_gaptr gap; - /* server is nonzero if this object records server initiated stream - ID. */ - int server; } ngtcp2_idtr; /* * ngtcp2_idtr_init initializes |idtr|. - * - * If this object records server initiated ID (even number), set - * |server| to nonzero. */ -void ngtcp2_idtr_init(ngtcp2_idtr *idtr, int server, const ngtcp2_mem *mem); +void ngtcp2_idtr_init(ngtcp2_idtr *idtr, const ngtcp2_mem *mem); /* * ngtcp2_idtr_free frees resources allocated for |idtr|. @@ -60,30 +56,21 @@ void ngtcp2_idtr_init(ngtcp2_idtr *idtr, int server, const ngtcp2_mem *mem); void ngtcp2_idtr_free(ngtcp2_idtr *idtr); /* - * ngtcp2_idtr_open claims that |stream_id| is in used. + * ngtcp2_idtr_open claims that |stream_id| is in use. * * It returns 0 if it succeeds, or one of the following negative error * codes: * * NGTCP2_ERR_STREAM_IN_USE - * ID has already been used. + * |stream_id| has already been used. * NGTCP2_ERR_NOMEM * Out of memory. */ int ngtcp2_idtr_open(ngtcp2_idtr *idtr, int64_t stream_id); /* - * ngtcp2_idtr_open tells whether ID |stream_id| is in used or not. - * - * It returns nonzero if |stream_id| is used. + * ngtcp2_idtr_open returns nonzero if |stream_id| is in use. */ int ngtcp2_idtr_is_open(ngtcp2_idtr *idtr, int64_t stream_id); -/* - * ngtcp2_idtr_first_gap returns the first id of first gap. If there - * is no gap, it returns UINT64_MAX. The returned id is an id space - * used in this object internally, and not stream ID. - */ -uint64_t ngtcp2_idtr_first_gap(ngtcp2_idtr *idtr); - #endif /* NGTCP2_IDTR_H */ diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.c index a7284bd..df2b640 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.c @@ -38,8 +38,10 @@ static ngtcp2_ksl_blk null_blk = {{{NULL, NULL, 0, 0, {0}}}}; ngtcp2_objalloc_def(ksl_blk, ngtcp2_ksl_blk, oplent); static size_t ksl_nodelen(size_t keylen) { - return (sizeof(ngtcp2_ksl_node) + keylen - sizeof(uint64_t) + 0xfu) & - ~(uintptr_t)0xfu; + assert(keylen >= sizeof(uint64_t)); + + return (sizeof(ngtcp2_ksl_node) + keylen - sizeof(uint64_t) + 0x7u) & + ~(uintptr_t)0x7u; } static size_t ksl_blklen(size_t nodelen) { @@ -65,9 +67,9 @@ void ngtcp2_ksl_init(ngtcp2_ksl *ksl, ngtcp2_ksl_compar compar, size_t keylen, ksl->head = NULL; ksl->front = ksl->back = NULL; ksl->compar = compar; + ksl->n = 0; ksl->keylen = keylen; ksl->nodelen = nodelen; - ksl->n = 0; } static ngtcp2_ksl_blk *ksl_blk_objalloc_new(ngtcp2_ksl *ksl) { @@ -81,6 +83,7 @@ static void ksl_blk_objalloc_del(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk) { static int ksl_head_init(ngtcp2_ksl *ksl) { ngtcp2_ksl_blk *head = ksl_blk_objalloc_new(ksl); + if (!head) { return NGTCP2_ERR_NOMEM; } @@ -142,21 +145,22 @@ static ngtcp2_ksl_blk *ksl_split_blk(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk) { rblk->next = blk->next; blk->next = rblk; + if (rblk->next) { rblk->next->prev = rblk; } else if (ksl->back == blk) { ksl->back = rblk; } + rblk->prev = blk; rblk->leaf = blk->leaf; rblk->n = blk->n / 2; + blk->n -= rblk->n; - memcpy(rblk->nodes, blk->nodes + ksl->nodelen * (blk->n - rblk->n), + memcpy(rblk->nodes, blk->nodes + ksl->nodelen * blk->n, ksl->nodelen * rblk->n); - blk->n -= rblk->n; - assert(blk->n >= NGTCP2_KSL_MIN_NBLK); assert(rblk->n >= NGTCP2_KSL_MIN_NBLK); @@ -172,7 +176,7 @@ static ngtcp2_ksl_blk *ksl_split_blk(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk) { * codes: * * NGTCP2_ERR_NOMEM - * Out of memory. + * Out of memory. */ static int ksl_split_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) { ngtcp2_ksl_node *node; @@ -206,7 +210,7 @@ static int ksl_split_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) { * codes: * * NGTCP2_ERR_NOMEM - * Out of memory. + * Out of memory. */ static int ksl_split_head(ngtcp2_ksl *ksl) { ngtcp2_ksl_blk *rblk = NULL, *lblk, *nhead = NULL; @@ -220,10 +224,12 @@ static int ksl_split_head(ngtcp2_ksl *ksl) { lblk = ksl->head; nhead = ksl_blk_objalloc_new(ksl); + if (nhead == NULL) { ksl_blk_objalloc_del(ksl, rblk); return NGTCP2_ERR_NOMEM; } + nhead->next = nhead->prev = NULL; nhead->n = 2; nhead->leaf = 0; @@ -242,9 +248,9 @@ static int ksl_split_head(ngtcp2_ksl *ksl) { } /* - * insert_node inserts a node whose key is |key| with the associated - * |data| at the index of |i|. This function assumes that the number - * of nodes contained by |blk| is strictly less than + * ksl_insert_node inserts a node whose key is |key| with the + * associated |data| at the index of |i|. This function assumes that + * the number of nodes contained by |blk| is strictly less than * NGTCP2_KSL_MAX_NBLK. */ static void ksl_insert_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i, @@ -263,8 +269,8 @@ static void ksl_insert_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i, ++blk->n; } -static size_t ksl_bsearch(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, - const ngtcp2_ksl_key *key, ngtcp2_ksl_compar compar) { +static size_t ksl_search(const ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, + const ngtcp2_ksl_key *key, ngtcp2_ksl_compar compar) { size_t i; ngtcp2_ksl_node *node; @@ -290,18 +296,17 @@ int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, } } - blk = ksl->head; - - if (blk->n == NGTCP2_KSL_MAX_NBLK) { + if (ksl->head->n == NGTCP2_KSL_MAX_NBLK) { rv = ksl_split_head(ksl); if (rv != 0) { return rv; } - blk = ksl->head; } + blk = ksl->head; + for (;;) { - i = ksl_bsearch(ksl, blk, key, ksl->compar); + i = ksl_search(ksl, blk, key, ksl->compar); if (blk->leaf) { if (i < blk->n && @@ -309,13 +314,17 @@ int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, if (it) { *it = ngtcp2_ksl_end(ksl); } + return NGTCP2_ERR_INVALID_ARGUMENT; } + ksl_insert_node(ksl, blk, i, key, data); ++ksl->n; + if (it) { ngtcp2_ksl_it_init(it, ksl, blk, i); } + return 0; } @@ -328,16 +337,21 @@ int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, if (rv != 0) { return rv; } + node = ngtcp2_ksl_nth_node(ksl, blk, blk->n - 1); } + ksl_node_set_key(ksl, node, key); blk = node->blk; } + ksl_insert_node(ksl, blk, blk->n, key, data); ++ksl->n; + if (it) { ngtcp2_ksl_it_init(it, ksl, blk, blk->n - 1); } + return 0; } @@ -348,8 +362,10 @@ int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, if (rv != 0) { return rv; } + if (ksl->compar((ngtcp2_ksl_key *)node->key, key)) { node = ngtcp2_ksl_nth_node(ksl, blk, i + 1); + if (ksl->compar((ngtcp2_ksl_key *)node->key, key)) { ksl_node_set_key(ksl, node, key); } @@ -375,19 +391,22 @@ static void ksl_remove_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) { * ksl_merge_node merges 2 nodes which are the nodes at the index of * |i| and |i + 1|. * - * If |blk| is the direct descendant of head (root) block and the head - * block contains just 2 nodes, the merged block becomes head block, - * which decreases the height of |ksl| by 1. + * If |blk| is the head (root) block and it contains just 2 nodes + * before merging nodes, the merged block becomes head block, which + * decreases the height of |ksl| by 1. * * This function returns the pointer to the merged block. */ static ngtcp2_ksl_blk *ksl_merge_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) { + ngtcp2_ksl_node *lnode; ngtcp2_ksl_blk *lblk, *rblk; assert(i + 1 < blk->n); - lblk = ngtcp2_ksl_nth_node(ksl, blk, i)->blk; + lnode = ngtcp2_ksl_nth_node(ksl, blk, i); + + lblk = lnode->blk; rblk = ngtcp2_ksl_nth_node(ksl, blk, i + 1)->blk; assert(lblk->n + rblk->n < NGTCP2_KSL_MAX_NBLK); @@ -397,6 +416,7 @@ static ngtcp2_ksl_blk *ksl_merge_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, lblk->n += rblk->n; lblk->next = rblk->next; + if (lblk->next) { lblk->next->prev = lblk; } else if (ksl->back == rblk) { @@ -410,7 +430,7 @@ static ngtcp2_ksl_blk *ksl_merge_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, ksl->head = lblk; } else { ksl_remove_node(ksl, blk, i + 1); - ksl_node_set_key(ksl, ngtcp2_ksl_nth_node(ksl, blk, i), + ksl_node_set_key(ksl, lnode, ngtcp2_ksl_nth_node(ksl, lblk, lblk->n - 1)->key); } @@ -424,6 +444,7 @@ static ngtcp2_ksl_blk *ksl_merge_node(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, */ static void ksl_shift_left(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) { ngtcp2_ksl_node *lnode, *rnode; + ngtcp2_ksl_blk *lblk, *rblk; size_t n; assert(i > 0); @@ -431,35 +452,37 @@ static void ksl_shift_left(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) { lnode = ngtcp2_ksl_nth_node(ksl, blk, i - 1); rnode = ngtcp2_ksl_nth_node(ksl, blk, i); - assert(lnode->blk->n < NGTCP2_KSL_MAX_NBLK); - assert(rnode->blk->n > NGTCP2_KSL_MIN_NBLK); + lblk = lnode->blk; + rblk = rnode->blk; + + assert(lblk->n < NGTCP2_KSL_MAX_NBLK); + assert(rblk->n > NGTCP2_KSL_MIN_NBLK); - n = (lnode->blk->n + rnode->blk->n + 1) / 2 - lnode->blk->n; + n = (lblk->n + rblk->n + 1) / 2 - lblk->n; assert(n > 0); - assert(lnode->blk->n <= NGTCP2_KSL_MAX_NBLK - n); - assert(rnode->blk->n >= NGTCP2_KSL_MIN_NBLK + n); + assert(lblk->n <= NGTCP2_KSL_MAX_NBLK - n); + assert(rblk->n >= NGTCP2_KSL_MIN_NBLK + n); - memcpy(lnode->blk->nodes + ksl->nodelen * lnode->blk->n, rnode->blk->nodes, - ksl->nodelen * n); + memcpy(lblk->nodes + ksl->nodelen * lblk->n, rblk->nodes, ksl->nodelen * n); - lnode->blk->n += (uint32_t)n; - rnode->blk->n -= (uint32_t)n; + lblk->n += (uint32_t)n; + rblk->n -= (uint32_t)n; - ksl_node_set_key( - ksl, lnode, ngtcp2_ksl_nth_node(ksl, lnode->blk, lnode->blk->n - 1)->key); + ksl_node_set_key(ksl, lnode, + ngtcp2_ksl_nth_node(ksl, lblk, lblk->n - 1)->key); - memmove(rnode->blk->nodes, rnode->blk->nodes + ksl->nodelen * n, - ksl->nodelen * rnode->blk->n); + memmove(rblk->nodes, rblk->nodes + ksl->nodelen * n, ksl->nodelen * rblk->n); } /* * ksl_shift_right moves the last nodes in blk->nodes[i]->blk->nodes * to blk->nodes[i + 1]->blk->nodes in a manner that they have the - * same amount of nodes as much as possible.. + * same amount of nodes as much as possible. */ static void ksl_shift_right(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) { ngtcp2_ksl_node *lnode, *rnode; + ngtcp2_ksl_blk *lblk, *rblk; size_t n; assert(i < blk->n - 1); @@ -467,26 +490,27 @@ static void ksl_shift_right(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t i) { lnode = ngtcp2_ksl_nth_node(ksl, blk, i); rnode = ngtcp2_ksl_nth_node(ksl, blk, i + 1); - assert(lnode->blk->n > NGTCP2_KSL_MIN_NBLK); - assert(rnode->blk->n < NGTCP2_KSL_MAX_NBLK); + lblk = lnode->blk; + rblk = rnode->blk; - n = (lnode->blk->n + rnode->blk->n + 1) / 2 - rnode->blk->n; + assert(lblk->n > NGTCP2_KSL_MIN_NBLK); + assert(rblk->n < NGTCP2_KSL_MAX_NBLK); + + n = (lblk->n + rblk->n + 1) / 2 - rblk->n; assert(n > 0); - assert(lnode->blk->n >= NGTCP2_KSL_MIN_NBLK + n); - assert(rnode->blk->n <= NGTCP2_KSL_MAX_NBLK - n); + assert(lblk->n >= NGTCP2_KSL_MIN_NBLK + n); + assert(rblk->n <= NGTCP2_KSL_MAX_NBLK - n); - memmove(rnode->blk->nodes + ksl->nodelen * n, rnode->blk->nodes, - ksl->nodelen * rnode->blk->n); + memmove(rblk->nodes + ksl->nodelen * n, rblk->nodes, ksl->nodelen * rblk->n); - rnode->blk->n += (uint32_t)n; - lnode->blk->n -= (uint32_t)n; + rblk->n += (uint32_t)n; + lblk->n -= (uint32_t)n; - memcpy(rnode->blk->nodes, lnode->blk->nodes + ksl->nodelen * lnode->blk->n, - ksl->nodelen * n); + memcpy(rblk->nodes, lblk->nodes + ksl->nodelen * lblk->n, ksl->nodelen * n); - ksl_node_set_key( - ksl, lnode, ngtcp2_ksl_nth_node(ksl, lnode->blk, lnode->blk->n - 1)->key); + ksl_node_set_key(ksl, lnode, + ngtcp2_ksl_nth_node(ksl, lblk, lblk->n - 1)->key); } /* @@ -530,23 +554,24 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, ngtcp2_ksl_node *node; size_t i; - if (!ksl->head) { + if (!blk) { return NGTCP2_ERR_INVALID_ARGUMENT; } if (!blk->leaf && blk->n == 2 && ngtcp2_ksl_nth_node(ksl, blk, 0)->blk->n == NGTCP2_KSL_MIN_NBLK && ngtcp2_ksl_nth_node(ksl, blk, 1)->blk->n == NGTCP2_KSL_MIN_NBLK) { - blk = ksl_merge_node(ksl, ksl->head, 0); + blk = ksl_merge_node(ksl, blk, 0); } for (;;) { - i = ksl_bsearch(ksl, blk, key, ksl->compar); + i = ksl_search(ksl, blk, key, ksl->compar); if (i == blk->n) { if (it) { *it = ngtcp2_ksl_end(ksl); } + return NGTCP2_ERR_INVALID_ARGUMENT; } @@ -555,10 +580,13 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, if (it) { *it = ngtcp2_ksl_end(ksl); } + return NGTCP2_ERR_INVALID_ARGUMENT; } + ksl_remove_node(ksl, blk, i); --ksl->n; + if (it) { if (blk->n == i && blk->next) { ngtcp2_ksl_it_init(it, ksl, blk->next, 0); @@ -566,6 +594,7 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, ngtcp2_ksl_it_init(it, ksl, blk, i); } } + return 0; } @@ -582,6 +611,7 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, ngtcp2_ksl_nth_node(ksl, blk, i + 1)->blk->n > NGTCP2_KSL_MIN_NBLK) { ksl_shift_left(ksl, blk, i + 1); blk = node->blk; + continue; } @@ -589,6 +619,7 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, ngtcp2_ksl_nth_node(ksl, blk, i - 1)->blk->n > NGTCP2_KSL_MIN_NBLK) { ksl_shift_right(ksl, blk, i - 1); blk = node->blk; + continue; } @@ -603,48 +634,12 @@ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, } } -ngtcp2_ksl_it ngtcp2_ksl_lower_bound(ngtcp2_ksl *ksl, +ngtcp2_ksl_it ngtcp2_ksl_lower_bound(const ngtcp2_ksl *ksl, const ngtcp2_ksl_key *key) { - ngtcp2_ksl_blk *blk = ksl->head; - ngtcp2_ksl_it it; - size_t i; - - if (!blk) { - ngtcp2_ksl_it_init(&it, ksl, &null_blk, 0); - return it; - } - - for (;;) { - i = ksl_bsearch(ksl, blk, key, ksl->compar); - - if (blk->leaf) { - if (i == blk->n && blk->next) { - blk = blk->next; - i = 0; - } - ngtcp2_ksl_it_init(&it, ksl, blk, i); - return it; - } - - if (i == blk->n) { - /* This happens if descendant has smaller key. Fast forward to - find last node in this subtree. */ - for (; !blk->leaf; blk = ngtcp2_ksl_nth_node(ksl, blk, blk->n - 1)->blk) - ; - if (blk->next) { - blk = blk->next; - i = 0; - } else { - i = blk->n; - } - ngtcp2_ksl_it_init(&it, ksl, blk, i); - return it; - } - blk = ngtcp2_ksl_nth_node(ksl, blk, i)->blk; - } + return ngtcp2_ksl_lower_bound_compar(ksl, key, ksl->compar); } -ngtcp2_ksl_it ngtcp2_ksl_lower_bound_compar(ngtcp2_ksl *ksl, +ngtcp2_ksl_it ngtcp2_ksl_lower_bound_compar(const ngtcp2_ksl *ksl, const ngtcp2_ksl_key *key, ngtcp2_ksl_compar compar) { ngtcp2_ksl_blk *blk = ksl->head; @@ -657,14 +652,16 @@ ngtcp2_ksl_it ngtcp2_ksl_lower_bound_compar(ngtcp2_ksl *ksl, } for (;;) { - i = ksl_bsearch(ksl, blk, key, compar); + i = ksl_search(ksl, blk, key, compar); if (blk->leaf) { if (i == blk->n && blk->next) { blk = blk->next; i = 0; } + ngtcp2_ksl_it_init(&it, ksl, blk, i); + return it; } @@ -673,15 +670,19 @@ ngtcp2_ksl_it ngtcp2_ksl_lower_bound_compar(ngtcp2_ksl *ksl, find last node in this subtree. */ for (; !blk->leaf; blk = ngtcp2_ksl_nth_node(ksl, blk, blk->n - 1)->blk) ; + if (blk->next) { blk = blk->next; i = 0; } else { i = blk->n; } + ngtcp2_ksl_it_init(&it, ksl, blk, i); + return it; } + blk = ngtcp2_ksl_nth_node(ksl, blk, i)->blk; } } @@ -695,7 +696,7 @@ void ngtcp2_ksl_update_key(ngtcp2_ksl *ksl, const ngtcp2_ksl_key *old_key, assert(ksl->head); for (;;) { - i = ksl_bsearch(ksl, blk, old_key, ksl->compar); + i = ksl_search(ksl, blk, old_key, ksl->compar); assert(i < blk->n); node = ngtcp2_ksl_nth_node(ksl, blk, i); @@ -703,6 +704,7 @@ void ngtcp2_ksl_update_key(ngtcp2_ksl *ksl, const ngtcp2_ksl_key *old_key, if (blk->leaf) { assert(key_equal(ksl->compar, (ngtcp2_ksl_key *)node->key, old_key)); ksl_node_set_key(ksl, node, new_key); + return; } @@ -715,7 +717,7 @@ void ngtcp2_ksl_update_key(ngtcp2_ksl *ksl, const ngtcp2_ksl_key *old_key, } } -size_t ngtcp2_ksl_len(ngtcp2_ksl *ksl) { return ksl->n; } +size_t ngtcp2_ksl_len(const ngtcp2_ksl *ksl) { return ksl->n; } void ngtcp2_ksl_clear(ngtcp2_ksl *ksl) { if (!ksl->head) { @@ -733,7 +735,8 @@ void ngtcp2_ksl_clear(ngtcp2_ksl *ksl) { } #ifndef WIN32 -static void ksl_print(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t level) { +static void ksl_print(const ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, + size_t level) { size_t i; ngtcp2_ksl_node *node; @@ -744,7 +747,9 @@ static void ksl_print(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t level) { node = ngtcp2_ksl_nth_node(ksl, blk, i); fprintf(stderr, " %" PRId64, *(int64_t *)(void *)node->key); } + fprintf(stderr, "\n"); + return; } @@ -753,7 +758,7 @@ static void ksl_print(ngtcp2_ksl *ksl, ngtcp2_ksl_blk *blk, size_t level) { } } -void ngtcp2_ksl_print(ngtcp2_ksl *ksl) { +void ngtcp2_ksl_print(const ngtcp2_ksl *ksl) { if (!ksl->head) { return; } diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.h index d972bfc..89b5f2b 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ksl.h @@ -35,10 +35,6 @@ #include "ngtcp2_objalloc.h" -/* - * Skip List using single key instead of range. - */ - #define NGTCP2_KSL_DEGR 16 /* NGTCP2_KSL_MAX_NBLK is the maximum number of nodes which a single block can contain. */ @@ -85,7 +81,8 @@ struct ngtcp2_ksl_blk { struct { /* next points to the next block if leaf field is nonzero. */ ngtcp2_ksl_blk *next; - /* prev points to the previous block if leaf field is nonzero. */ + /* prev points to the previous block if leaf field is + nonzero. */ ngtcp2_ksl_blk *prev; /* n is the number of nodes this object contains in nodes. */ uint32_t n; @@ -120,7 +117,7 @@ typedef struct ngtcp2_ksl ngtcp2_ksl; typedef struct ngtcp2_ksl_it ngtcp2_ksl_it; /* - * ngtcp2_ksl_it is a forward iterator to iterate nodes. + * ngtcp2_ksl_it is a bidirectional iterator to iterate nodes. */ struct ngtcp2_ksl_it { const ngtcp2_ksl *ksl; @@ -140,6 +137,7 @@ struct ngtcp2_ksl { /* back points to the last leaf block. */ ngtcp2_ksl_blk *back; ngtcp2_ksl_compar compar; + /* n is the number of elements stored. */ size_t n; /* keylen is the size of key */ size_t keylen; @@ -150,7 +148,8 @@ struct ngtcp2_ksl { /* * ngtcp2_ksl_init initializes |ksl|. |compar| specifies compare - * function. |keylen| is the length of key. + * function. |keylen| is the length of key and must be at least + * sizeof(uint64_t). */ void ngtcp2_ksl_init(ngtcp2_ksl *ksl, ngtcp2_ksl_compar compar, size_t keylen, const ngtcp2_mem *mem); @@ -165,15 +164,15 @@ void ngtcp2_ksl_free(ngtcp2_ksl *ksl); /* * ngtcp2_ksl_insert inserts |key| with its associated |data|. On * successful insertion, the iterator points to the inserted node is - * stored in |*it|. + * stored in |*it| if |it| is not NULL. * * This function returns 0 if it succeeds, or one of the following * negative error codes: * * NGTCP2_ERR_NOMEM - * Out of memory. + * Out of memory. * NGTCP2_ERR_INVALID_ARGUMENT - * |key| already exists. + * |key| already exists. */ int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, const ngtcp2_ksl_key *key, void *data); @@ -184,13 +183,14 @@ int ngtcp2_ksl_insert(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, * This function assigns the iterator to |*it|, which points to the * node which is located at the right next of the removed node if |it| * is not NULL. If |key| is not found, no deletion takes place and - * the return value of ngtcp2_ksl_end(ksl) is assigned to |*it|. + * the return value of ngtcp2_ksl_end(ksl) is assigned to |*it| if + * |it| is not NULL. * * This function returns 0 if it succeeds, or one of the following * negative error codes: * * NGTCP2_ERR_INVALID_ARGUMENT - * |key| does not exist. + * |key| does not exist. */ int ngtcp2_ksl_remove(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, const ngtcp2_ksl_key *key); @@ -213,14 +213,14 @@ int ngtcp2_ksl_remove_hint(ngtcp2_ksl *ksl, ngtcp2_ksl_it *it, * node, it returns the iterator which satisfies ngtcp2_ksl_it_end(it) * != 0. */ -ngtcp2_ksl_it ngtcp2_ksl_lower_bound(ngtcp2_ksl *ksl, +ngtcp2_ksl_it ngtcp2_ksl_lower_bound(const ngtcp2_ksl *ksl, const ngtcp2_ksl_key *key); /* * ngtcp2_ksl_lower_bound_compar works like ngtcp2_ksl_lower_bound, * but it takes custom function |compar| to do lower bound search. */ -ngtcp2_ksl_it ngtcp2_ksl_lower_bound_compar(ngtcp2_ksl *ksl, +ngtcp2_ksl_it ngtcp2_ksl_lower_bound_compar(const ngtcp2_ksl *ksl, const ngtcp2_ksl_key *key, ngtcp2_ksl_compar compar); @@ -235,7 +235,8 @@ void ngtcp2_ksl_update_key(ngtcp2_ksl *ksl, const ngtcp2_ksl_key *old_key, /* * ngtcp2_ksl_begin returns the iterator which points to the first * node. If there is no node in |ksl|, it returns the iterator which - * satisfies ngtcp2_ksl_it_end(it) != 0. + * satisfies both ngtcp2_ksl_it_begin(it) != 0 and + * ngtcp2_ksl_it_end(it) != 0. */ ngtcp2_ksl_it ngtcp2_ksl_begin(const ngtcp2_ksl *ksl); @@ -243,14 +244,15 @@ ngtcp2_ksl_it ngtcp2_ksl_begin(const ngtcp2_ksl *ksl); * ngtcp2_ksl_end returns the iterator which points to the node * following the last node. The returned object satisfies * ngtcp2_ksl_it_end(). If there is no node in |ksl|, it returns the - * iterator which satisfies ngtcp2_ksl_it_begin(it) != 0. + * iterator which satisfies ngtcp2_ksl_it_begin(it) != 0 and + * ngtcp2_ksl_it_end(it) != 0. */ ngtcp2_ksl_it ngtcp2_ksl_end(const ngtcp2_ksl *ksl); /* * ngtcp2_ksl_len returns the number of elements stored in |ksl|. */ -size_t ngtcp2_ksl_len(ngtcp2_ksl *ksl); +size_t ngtcp2_ksl_len(const ngtcp2_ksl *ksl); /* * ngtcp2_ksl_clear removes all elements stored in |ksl|. @@ -269,7 +271,7 @@ void ngtcp2_ksl_clear(ngtcp2_ksl *ksl); * that the key is of type int64_t. This function should be used for * the debugging purpose only. */ -void ngtcp2_ksl_print(ngtcp2_ksl *ksl); +void ngtcp2_ksl_print(const ngtcp2_ksl *ksl); #endif /* !WIN32 */ /* @@ -304,16 +306,16 @@ void ngtcp2_ksl_it_init(ngtcp2_ksl_it *it, const ngtcp2_ksl *ksl, void ngtcp2_ksl_it_prev(ngtcp2_ksl_it *it); /* - * ngtcp2_ksl_it_end returns nonzero if |it| points to the beyond the - * last node. + * ngtcp2_ksl_it_end returns nonzero if |it| points to the one beyond + * the last node. */ #define ngtcp2_ksl_it_end(IT) \ ((IT)->blk->n == (IT)->i && (IT)->blk->next == NULL) /* * ngtcp2_ksl_it_begin returns nonzero if |it| points to the first - * node. |it| might satisfy both ngtcp2_ksl_it_begin(&it) and - * ngtcp2_ksl_it_end(&it) if the skip list has no node. + * node. |it| might satisfy both ngtcp2_ksl_it_begin(it) != 0 and + * ngtcp2_ksl_it_end(it) != 0 if the skip list has no node. */ int ngtcp2_ksl_it_begin(const ngtcp2_ksl_it *it); diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_macro.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_macro.h index 46cfebc..62d7036 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_macro.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_macro.h @@ -34,7 +34,7 @@ #include <ngtcp2/ngtcp2.h> #define ngtcp2_struct_of(ptr, type, member) \ - ((type *)(void *)((char *)(ptr)-offsetof(type, member))) + ((type *)(void *)((char *)(ptr) - offsetof(type, member))) /* ngtcp2_list_insert inserts |T| before |*PD|. The contract is that this is singly linked list, and the next element is pointed by next diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_map.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_map.c index 33e9fcc..10cb657 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_map.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_map.c @@ -35,7 +35,6 @@ void ngtcp2_map_init(ngtcp2_map *map, const ngtcp2_mem *mem) { map->mem = mem; - map->tablelen = 0; map->tablelenbits = 0; map->table = NULL; map->size = 0; @@ -49,33 +48,20 @@ void ngtcp2_map_free(ngtcp2_map *map) { ngtcp2_mem_free(map->mem, map->table); } -void ngtcp2_map_each_free(ngtcp2_map *map, int (*func)(void *data, void *ptr), - void *ptr) { - uint32_t i; - ngtcp2_map_bucket *bkt; - - for (i = 0; i < map->tablelen; ++i) { - bkt = &map->table[i]; - - if (bkt->data == NULL) { - continue; - } - - func(bkt->data, ptr); - } -} - -int ngtcp2_map_each(ngtcp2_map *map, int (*func)(void *data, void *ptr), +int ngtcp2_map_each(const ngtcp2_map *map, int (*func)(void *data, void *ptr), void *ptr) { int rv; - uint32_t i; + size_t i; ngtcp2_map_bucket *bkt; + size_t tablelen; if (map->size == 0) { return 0; } - for (i = 0; i < map->tablelen; ++i) { + tablelen = 1u << map->tablelenbits; + + for (i = 0; i < tablelen; ++i) { bkt = &map->table[i]; if (bkt->data == NULL) { @@ -95,78 +81,81 @@ static uint32_t hash(ngtcp2_map_key_type key) { return (uint32_t)((key * 11400714819323198485llu) >> 32); } -static size_t h2idx(uint32_t hash, uint32_t bits) { - return hash >> (32 - bits); -} - -static size_t distance(uint32_t tablelen, uint32_t tablelenbits, - ngtcp2_map_bucket *bkt, size_t idx) { - return (idx - h2idx(bkt->hash, tablelenbits)) & (tablelen - 1); -} +static size_t h2idx(uint32_t hash, size_t bits) { return hash >> (32 - bits); } static void map_bucket_swap(ngtcp2_map_bucket *bkt, uint32_t *phash, - ngtcp2_map_key_type *pkey, void **pdata) { + uint32_t *ppsl, ngtcp2_map_key_type *pkey, + void **pdata) { uint32_t h = bkt->hash; + uint32_t psl = bkt->psl; ngtcp2_map_key_type key = bkt->key; void *data = bkt->data; bkt->hash = *phash; + bkt->psl = *ppsl; bkt->key = *pkey; bkt->data = *pdata; *phash = h; + *ppsl = psl; *pkey = key; *pdata = data; } static void map_bucket_set_data(ngtcp2_map_bucket *bkt, uint32_t hash, - ngtcp2_map_key_type key, void *data) { + uint32_t psl, ngtcp2_map_key_type key, + void *data) { bkt->hash = hash; + bkt->psl = psl; bkt->key = key; bkt->data = data; } #ifndef WIN32 -void ngtcp2_map_print_distance(ngtcp2_map *map) { - uint32_t i; +void ngtcp2_map_print_distance(const ngtcp2_map *map) { + size_t i; size_t idx; ngtcp2_map_bucket *bkt; + size_t tablelen; - for (i = 0; i < map->tablelen; ++i) { + if (map->size == 0) { + return; + } + + tablelen = 1u << map->tablelenbits; + + for (i = 0; i < tablelen; ++i) { bkt = &map->table[i]; if (bkt->data == NULL) { - fprintf(stderr, "@%u <EMPTY>\n", i); + fprintf(stderr, "@%zu <EMPTY>\n", i); continue; } idx = h2idx(bkt->hash, map->tablelenbits); - fprintf(stderr, "@%u hash=%08x key=%" PRIu64 " base=%zu distance=%zu\n", i, - bkt->hash, bkt->key, idx, - distance(map->tablelen, map->tablelenbits, bkt, idx)); + fprintf(stderr, "@%zu hash=%08x key=%" PRIu64 " base=%zu distance=%u\n", i, + bkt->hash, bkt->key, idx, bkt->psl); } } #endif /* !WIN32 */ -static int insert(ngtcp2_map_bucket *table, uint32_t tablelen, - uint32_t tablelenbits, uint32_t hash, ngtcp2_map_key_type key, - void *data) { +static int insert(ngtcp2_map_bucket *table, size_t tablelenbits, uint32_t hash, + ngtcp2_map_key_type key, void *data) { size_t idx = h2idx(hash, tablelenbits); - size_t d = 0, dd; + uint32_t psl = 0; ngtcp2_map_bucket *bkt; + size_t mask = (1u << tablelenbits) - 1; for (;;) { bkt = &table[idx]; if (bkt->data == NULL) { - map_bucket_set_data(bkt, hash, key, data); + map_bucket_set_data(bkt, hash, psl, key, data); return 0; } - dd = distance(tablelen, tablelenbits, bkt, idx); - if (d > dd) { - map_bucket_swap(bkt, &hash, &key, &data); - d = dd; + if (psl > bkt->psl) { + map_bucket_swap(bkt, &hash, &psl, &key, &data); } else if (bkt->key == key) { /* TODO This check is just a waste after first swap or if this function is called from map_resize. That said, there is no @@ -175,40 +164,41 @@ static int insert(ngtcp2_map_bucket *table, uint32_t tablelen, return NGTCP2_ERR_INVALID_ARGUMENT; } - ++d; - idx = (idx + 1) & (tablelen - 1); + ++psl; + idx = (idx + 1) & mask; } } -/* new_tablelen must be power of 2 and new_tablelen == (1 << - new_tablelenbits) must hold. */ -static int map_resize(ngtcp2_map *map, uint32_t new_tablelen, - uint32_t new_tablelenbits) { - uint32_t i; +static int map_resize(ngtcp2_map *map, size_t new_tablelenbits) { + size_t i; ngtcp2_map_bucket *new_table; ngtcp2_map_bucket *bkt; + size_t tablelen; int rv; (void)rv; - new_table = - ngtcp2_mem_calloc(map->mem, new_tablelen, sizeof(ngtcp2_map_bucket)); + new_table = ngtcp2_mem_calloc(map->mem, 1u << new_tablelenbits, + sizeof(ngtcp2_map_bucket)); if (new_table == NULL) { return NGTCP2_ERR_NOMEM; } - for (i = 0; i < map->tablelen; ++i) { - bkt = &map->table[i]; - if (bkt->data == NULL) { - continue; - } - rv = insert(new_table, new_tablelen, new_tablelenbits, bkt->hash, bkt->key, - bkt->data); + if (map->size) { + tablelen = 1u << map->tablelenbits; - assert(0 == rv); + for (i = 0; i < tablelen; ++i) { + bkt = &map->table[i]; + if (bkt->data == NULL) { + continue; + } + + rv = insert(new_table, new_tablelenbits, bkt->hash, bkt->key, bkt->data); + + assert(0 == rv); + } } ngtcp2_mem_free(map->mem, map->table); - map->tablelen = new_tablelen; map->tablelenbits = new_tablelenbits; map->table = new_table; @@ -221,35 +211,38 @@ int ngtcp2_map_insert(ngtcp2_map *map, ngtcp2_map_key_type key, void *data) { assert(data); /* Load factor is 0.75 */ - if ((map->size + 1) * 4 > map->tablelen * 3) { - if (map->tablelen) { - rv = map_resize(map, map->tablelen * 2, map->tablelenbits + 1); + /* Under the very initial condition, that is map->size == 0 and + map->tablelenbits == 0, 4 > 3 still holds nicely. */ + if ((map->size + 1) * 4 > (1u << map->tablelenbits) * 3) { + if (map->tablelenbits) { + rv = map_resize(map, map->tablelenbits + 1); if (rv != 0) { return rv; } } else { - rv = map_resize(map, 1 << NGTCP2_INITIAL_TABLE_LENBITS, - NGTCP2_INITIAL_TABLE_LENBITS); + rv = map_resize(map, NGTCP2_INITIAL_TABLE_LENBITS); if (rv != 0) { return rv; } } } - rv = insert(map->table, map->tablelen, map->tablelenbits, hash(key), key, - data); + rv = insert(map->table, map->tablelenbits, hash(key), key, data); if (rv != 0) { return rv; } + ++map->size; + return 0; } -void *ngtcp2_map_find(ngtcp2_map *map, ngtcp2_map_key_type key) { +void *ngtcp2_map_find(const ngtcp2_map *map, ngtcp2_map_key_type key) { uint32_t h; size_t idx; ngtcp2_map_bucket *bkt; size_t d = 0; + size_t mask; if (map->size == 0) { return NULL; @@ -257,12 +250,12 @@ void *ngtcp2_map_find(ngtcp2_map *map, ngtcp2_map_key_type key) { h = hash(key); idx = h2idx(h, map->tablelenbits); + mask = (1u << map->tablelenbits) - 1; for (;;) { bkt = &map->table[idx]; - if (bkt->data == NULL || - d > distance(map->tablelen, map->tablelenbits, bkt, idx)) { + if (bkt->data == NULL || d > bkt->psl) { return NULL; } @@ -271,7 +264,7 @@ void *ngtcp2_map_find(ngtcp2_map *map, ngtcp2_map_key_type key) { } ++d; - idx = (idx + 1) & (map->tablelen - 1); + idx = (idx + 1) & mask; } } @@ -280,6 +273,7 @@ int ngtcp2_map_remove(ngtcp2_map *map, ngtcp2_map_key_type key) { size_t idx, didx; ngtcp2_map_bucket *bkt; size_t d = 0; + size_t mask; if (map->size == 0) { return NGTCP2_ERR_INVALID_ARGUMENT; @@ -287,33 +281,31 @@ int ngtcp2_map_remove(ngtcp2_map *map, ngtcp2_map_key_type key) { h = hash(key); idx = h2idx(h, map->tablelenbits); + mask = (1u << map->tablelenbits) - 1; for (;;) { bkt = &map->table[idx]; - if (bkt->data == NULL || - d > distance(map->tablelen, map->tablelenbits, bkt, idx)) { + if (bkt->data == NULL || d > bkt->psl) { return NGTCP2_ERR_INVALID_ARGUMENT; } if (bkt->key == key) { - map_bucket_set_data(bkt, 0, 0, NULL); - didx = idx; - idx = (idx + 1) & (map->tablelen - 1); + idx = (idx + 1) & mask; for (;;) { bkt = &map->table[idx]; - if (bkt->data == NULL || - distance(map->tablelen, map->tablelenbits, bkt, idx) == 0) { + if (bkt->data == NULL || bkt->psl == 0) { + map_bucket_set_data(&map->table[didx], 0, 0, 0, NULL); break; } + --bkt->psl; map->table[didx] = *bkt; - map_bucket_set_data(bkt, 0, 0, NULL); didx = idx; - idx = (idx + 1) & (map->tablelen - 1); + idx = (idx + 1) & mask; } --map->size; @@ -322,17 +314,17 @@ int ngtcp2_map_remove(ngtcp2_map *map, ngtcp2_map_key_type key) { } ++d; - idx = (idx + 1) & (map->tablelen - 1); + idx = (idx + 1) & mask; } } void ngtcp2_map_clear(ngtcp2_map *map) { - if (map->tablelen == 0) { + if (map->size == 0) { return; } - memset(map->table, 0, sizeof(*map->table) * map->tablelen); + memset(map->table, 0, sizeof(*map->table) * (1u << map->tablelenbits)); map->size = 0; } -size_t ngtcp2_map_size(ngtcp2_map *map) { return map->size; } +size_t ngtcp2_map_size(const ngtcp2_map *map) { return map->size; } diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_map.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_map.h index d05b165..cc85d07 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_map.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_map.h @@ -40,6 +40,7 @@ typedef uint64_t ngtcp2_map_key_type; typedef struct ngtcp2_map_bucket { uint32_t hash; + uint32_t psl; ngtcp2_map_key_type key; void *data; } ngtcp2_map_bucket; @@ -48,33 +49,24 @@ typedef struct ngtcp2_map { ngtcp2_map_bucket *table; const ngtcp2_mem *mem; size_t size; - uint32_t tablelen; - uint32_t tablelenbits; + size_t tablelenbits; } ngtcp2_map; /* - * Initializes the map |map|. + * ngtcp2_map_init initializes the map |map|. */ void ngtcp2_map_init(ngtcp2_map *map, const ngtcp2_mem *mem); /* - * Deallocates any resources allocated for |map|. The stored entries - * are not freed by this function. Use ngtcp2_map_each_free() to free - * each entries. + * ngtcp2_map_free deallocates any resources allocated for |map|. The + * stored entries are not freed by this function. Use + * ngtcp2_map_each() to free each entry. */ void ngtcp2_map_free(ngtcp2_map *map); /* - * Deallocates each entries using |func| function and any resources - * allocated for |map|. The |func| function is responsible for freeing - * given the |data| object. The |ptr| will be passed to the |func| as - * send argument. The return value of the |func| will be ignored. - */ -void ngtcp2_map_each_free(ngtcp2_map *map, int (*func)(void *data, void *ptr), - void *ptr); - -/* - * Inserts the new |data| with the |key| to the map |map|. + * ngtcp2_map_insert inserts the new |data| with the |key| to the map + * |map|. * * This function returns 0 if it succeeds, or one of the following * negative error codes: @@ -82,57 +74,56 @@ void ngtcp2_map_each_free(ngtcp2_map *map, int (*func)(void *data, void *ptr), * NGTCP2_ERR_INVALID_ARGUMENT * The item associated by |key| already exists. * NGTCP2_ERR_NOMEM - * Out of memory + * Out of memory */ int ngtcp2_map_insert(ngtcp2_map *map, ngtcp2_map_key_type key, void *data); /* - * Returns the data associated by the key |key|. If there is no such - * data, this function returns NULL. + * ngtcp2_map_find returns the entry associated by the key |key|. If + * there is no such entry, this function returns NULL. */ -void *ngtcp2_map_find(ngtcp2_map *map, ngtcp2_map_key_type key); +void *ngtcp2_map_find(const ngtcp2_map *map, ngtcp2_map_key_type key); /* - * Removes the data associated by the key |key| from the |map|. The - * removed data is not freed by this function. + * ngtcp2_map_remove removes the entry associated by the key |key| + * from the |map|. The removed entry is not freed by this function. * * This function returns 0 if it succeeds, or one of the following * negative error codes: * * NGTCP2_ERR_INVALID_ARGUMENT - * The data associated by |key| does not exist. + * The entry associated by |key| does not exist. */ int ngtcp2_map_remove(ngtcp2_map *map, ngtcp2_map_key_type key); /* - * Removes all entries from |map|. + * ngtcp2_map_clear removes all entries from |map|. The removed entry + * is not freed by this function. */ void ngtcp2_map_clear(ngtcp2_map *map); /* - * Returns the number of items stored in the map |map|. + * ngtcp2_map_size returns the number of items stored in the map + * |map|. */ -size_t ngtcp2_map_size(ngtcp2_map *map); +size_t ngtcp2_map_size(const ngtcp2_map *map); /* - * Applies the function |func| to each data in the |map| with the - * optional user supplied pointer |ptr|. + * ngtcp2_map_each applies the function |func| to each entry in the + * |map| with the optional user supplied pointer |ptr|. * * If the |func| returns 0, this function calls the |func| with the - * next data. If the |func| returns nonzero, it will not call the + * next entry. If the |func| returns nonzero, it will not call the * |func| for further entries and return the return value of the * |func| immediately. Thus, this function returns 0 if all the * invocations of the |func| return 0, or nonzero value which the last * invocation of |func| returns. - * - * Don't use this function to free each data. Use - * ngtcp2_map_each_free() instead. */ -int ngtcp2_map_each(ngtcp2_map *map, int (*func)(void *data, void *ptr), +int ngtcp2_map_each(const ngtcp2_map *map, int (*func)(void *data, void *ptr), void *ptr); #ifndef WIN32 -void ngtcp2_map_print_distance(ngtcp2_map *map); +void ngtcp2_map_print_distance(const ngtcp2_map *map); #endif /* !WIN32 */ #endif /* NGTCP2_MAP_H */ diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ppe.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ppe.c index 34363d0..268559c 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ppe.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ppe.c @@ -66,6 +66,7 @@ int ngtcp2_ppe_encode_hd(ngtcp2_ppe *ppe, const ngtcp2_pkt_hd *hd) { rv = ngtcp2_pkt_encode_hd_short( buf->last, ngtcp2_buf_left(buf) - cc->aead.max_overhead, hd); } + if (rv < 0) { return (int)rv; } @@ -74,7 +75,6 @@ int ngtcp2_ppe_encode_hd(ngtcp2_ppe *ppe, const ngtcp2_pkt_hd *hd) { ppe->pkt_numlen = hd->pkt_numlen; ppe->hdlen = (size_t)rv; - ppe->pkt_num = hd->pkt_num; return 0; @@ -138,7 +138,7 @@ ngtcp2_ssize ngtcp2_ppe_final(ngtcp2_ppe *ppe, const uint8_t **ppkt) { buf->last = payload + payloadlen + cc->aead.max_overhead; - /* TODO Check that we have enough space to get sample */ + /* Make sure that we have enough space to get sample */ assert(ppe_sample_offset(ppe) + NGTCP2_HP_SAMPLELEN <= ngtcp2_buf_len(buf)); rv = cc->hp_mask(mask, &cc->hp, &cc->hp_ctx, diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ppe.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ppe.h index 2f9275c..c1f4b16 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ppe.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_ppe.h @@ -36,10 +36,13 @@ #include "ngtcp2_crypto.h" /* - * ngtcp2_ppe is the Protected Packet Encoder. + * ngtcp2_ppe is the QUIC Packet Encoder. */ typedef struct ngtcp2_ppe { + /* buf is the buffer where a QUIC packet is written. */ ngtcp2_buf buf; + /* cc is the encryption context that includes callback functions to + encrypt a QUIC packet, and AEAD cipher, etc. */ ngtcp2_crypto_cc *cc; /* dgram_offset is the offset in UDP datagram payload that this QUIC packet is positioned at. */ @@ -56,7 +59,7 @@ typedef struct ngtcp2_ppe { /* pkt_num is the packet number written in buf. */ int64_t pkt_num; /* nonce is the buffer to store nonce. It should be equal or longer - than then length of IV. */ + than the length of IV. */ uint8_t nonce[32]; } ngtcp2_ppe; @@ -89,7 +92,7 @@ int ngtcp2_ppe_encode_hd(ngtcp2_ppe *ppe, const ngtcp2_pkt_hd *hd); int ngtcp2_ppe_encode_frame(ngtcp2_ppe *ppe, ngtcp2_frame *fr); /* - * ngtcp2_ppe_final encrypts QUIC packet payload. If |**ppkt| is not + * ngtcp2_ppe_final encrypts QUIC packet payload. If |ppkt| is not * NULL, the pointer to the packet is assigned to it. * * This function returns the length of QUIC packet, including header, diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_pq.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_pq.c index 96cde8f..dcf6717 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_pq.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_pq.c @@ -29,17 +29,20 @@ #include "ngtcp2_macro.h" -void ngtcp2_pq_init(ngtcp2_pq *pq, ngtcp2_less less, const ngtcp2_mem *mem) { - pq->mem = mem; - pq->capacity = 0; +void ngtcp2_pq_init(ngtcp2_pq *pq, ngtcp2_pq_less less, const ngtcp2_mem *mem) { pq->q = NULL; + pq->mem = mem; pq->length = 0; + pq->capacity = 0; pq->less = less; } void ngtcp2_pq_free(ngtcp2_pq *pq) { + if (!pq) { + return; + } + ngtcp2_mem_free(pq->mem, pq->q); - pq->q = NULL; } static void swap(ngtcp2_pq *pq, size_t i, size_t j) { @@ -54,11 +57,13 @@ static void swap(ngtcp2_pq *pq, size_t i, size_t j) { static void bubble_up(ngtcp2_pq *pq, size_t index) { size_t parent; - while (index != 0) { + + while (index) { parent = (index - 1) / 2; if (!pq->less(pq->q[index], pq->q[parent])) { return; } + swap(pq, parent, index); index = parent; } @@ -76,49 +81,57 @@ int ngtcp2_pq_push(ngtcp2_pq *pq, ngtcp2_pq_entry *item) { if (nq == NULL) { return NGTCP2_ERR_NOMEM; } + pq->capacity = ncapacity; pq->q = nq; } + pq->q[pq->length] = item; item->index = pq->length; ++pq->length; - bubble_up(pq, pq->length - 1); + bubble_up(pq, item->index); + return 0; } -ngtcp2_pq_entry *ngtcp2_pq_top(ngtcp2_pq *pq) { +ngtcp2_pq_entry *ngtcp2_pq_top(const ngtcp2_pq *pq) { assert(pq->length); return pq->q[0]; } static void bubble_down(ngtcp2_pq *pq, size_t index) { size_t i, j, minindex; + for (;;) { j = index * 2 + 1; minindex = index; + for (i = 0; i < 2; ++i, ++j) { if (j >= pq->length) { break; } + if (pq->less(pq->q[j], pq->q[minindex])) { minindex = j; } } + if (minindex == index) { return; } + swap(pq, index, minindex); index = minindex; } } void ngtcp2_pq_pop(ngtcp2_pq *pq) { - if (pq->length > 0) { - pq->q[0] = pq->q[pq->length - 1]; - pq->q[0]->index = 0; - --pq->length; - bubble_down(pq, 0); - } + assert(pq->length); + + pq->q[0] = pq->q[pq->length - 1]; + pq->q[0]->index = 0; + --pq->length; + bubble_down(pq, 0); } void ngtcp2_pq_remove(ngtcp2_pq *pq, ngtcp2_pq_entry *item) { @@ -145,20 +158,22 @@ void ngtcp2_pq_remove(ngtcp2_pq *pq, ngtcp2_pq_entry *item) { } } -int ngtcp2_pq_empty(ngtcp2_pq *pq) { return pq->length == 0; } +int ngtcp2_pq_empty(const ngtcp2_pq *pq) { return pq->length == 0; } -size_t ngtcp2_pq_size(ngtcp2_pq *pq) { return pq->length; } +size_t ngtcp2_pq_size(const ngtcp2_pq *pq) { return pq->length; } -int ngtcp2_pq_each(ngtcp2_pq *pq, ngtcp2_pq_item_cb fun, void *arg) { +int ngtcp2_pq_each(const ngtcp2_pq *pq, ngtcp2_pq_item_cb fun, void *arg) { size_t i; if (pq->length == 0) { return 0; } + for (i = 0; i < pq->length; ++i) { if ((*fun)(pq->q[i], arg)) { return 1; } } + return 0; } diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_pq.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_pq.h index 484c8f2..2fe5e74 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_pq.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_pq.h @@ -45,37 +45,39 @@ typedef struct ngtcp2_pq_entry { size_t index; } ngtcp2_pq_entry; -/* "less" function, return nonzero if |lhs| is less than |rhs|. */ -typedef int (*ngtcp2_less)(const ngtcp2_pq_entry *lhs, - const ngtcp2_pq_entry *rhs); +/* ngtcp2_pq_less is a "less" function, that returns nonzero if |lhs| + is considered to be less than |rhs|. */ +typedef int (*ngtcp2_pq_less)(const ngtcp2_pq_entry *lhs, + const ngtcp2_pq_entry *rhs); typedef struct ngtcp2_pq { - /* The pointer to the pointer to the item stored */ + /* q is a pointer to an array that stores the items. */ ngtcp2_pq_entry **q; - /* Memory allocator */ + /* mem is a memory allocator. */ const ngtcp2_mem *mem; - /* The number of items stored */ + /* length is the number of items stored. */ size_t length; - /* The maximum number of items this pq can store. This is - automatically extended when length is reached to this value. */ + /* capacity is the maximum number of items this queue can store. + This is automatically extended when length is reached to this + limit. */ size_t capacity; - /* The less function between items */ - ngtcp2_less less; + /* less is the less function to compare items. */ + ngtcp2_pq_less less; } ngtcp2_pq; /* - * Initializes priority queue |pq| with compare function |cmp|. + * ngtcp2_pq_init initializes |pq| with compare function |cmp|. */ -void ngtcp2_pq_init(ngtcp2_pq *pq, ngtcp2_less less, const ngtcp2_mem *mem); +void ngtcp2_pq_init(ngtcp2_pq *pq, ngtcp2_pq_less less, const ngtcp2_mem *mem); /* - * Deallocates any resources allocated for |pq|. The stored items are - * not freed by this function. + * ngtcp2_pq_free deallocates any resources allocated for |pq|. The + * stored items are not freed by this function. */ void ngtcp2_pq_free(ngtcp2_pq *pq); /* - * Adds |item| to the priority queue |pq|. + * ngtcp2_pq_push adds |item| to |pq|. * * This function returns 0 if it succeeds, or one of the following * negative error codes: @@ -86,40 +88,41 @@ void ngtcp2_pq_free(ngtcp2_pq *pq); int ngtcp2_pq_push(ngtcp2_pq *pq, ngtcp2_pq_entry *item); /* - * Returns item at the top of the queue |pq|. It is undefined if the - * queue is empty. + * ngtcp2_pq_top returns item at the top of |pq|. It is undefined if + * |pq| is empty. */ -ngtcp2_pq_entry *ngtcp2_pq_top(ngtcp2_pq *pq); +ngtcp2_pq_entry *ngtcp2_pq_top(const ngtcp2_pq *pq); /* - * Pops item at the top of the queue |pq|. The popped item is not - * freed by this function. + * ngtcp2_pq_pop pops item at the top of |pq|. The popped item is not + * freed by this function. It is undefined if |pq| is empty. */ void ngtcp2_pq_pop(ngtcp2_pq *pq); /* - * Returns nonzero if the queue |pq| is empty. + * ngtcp2_pq_empty returns nonzero if |pq| is empty. */ -int ngtcp2_pq_empty(ngtcp2_pq *pq); +int ngtcp2_pq_empty(const ngtcp2_pq *pq); /* - * Returns the number of items in the queue |pq|. + * ngtcp2_pq_size returns the number of items |pq| contains. */ -size_t ngtcp2_pq_size(ngtcp2_pq *pq); +size_t ngtcp2_pq_size(const ngtcp2_pq *pq); typedef int (*ngtcp2_pq_item_cb)(ngtcp2_pq_entry *item, void *arg); /* - * Applies |fun| to each item in |pq|. The |arg| is passed as arg - * parameter to callback function. This function must not change the - * ordering key. If the return value from callback is nonzero, this - * function returns 1 immediately without iterating remaining items. - * Otherwise this function returns 0. + * ngtcp2_pq_each applies |fun| to each item in |pq|. The |arg| is + * passed as arg parameter to callback function. This function must + * not change the ordering key. If the return value from callback is + * nonzero, this function returns 1 immediately without iterating + * remaining items. Otherwise this function returns 0. */ -int ngtcp2_pq_each(ngtcp2_pq *pq, ngtcp2_pq_item_cb fun, void *arg); +int ngtcp2_pq_each(const ngtcp2_pq *pq, ngtcp2_pq_item_cb fun, void *arg); /* - * Removes |item| from priority queue. + * ngtcp2_pq_remove removes |item| from |pq|. |pq| must contain + * |item| otherwise the behavior is undefined. */ void ngtcp2_pq_remove(ngtcp2_pq *pq, ngtcp2_pq_entry *item); diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_qlog.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_qlog.c index 2767534..c4713f1 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_qlog.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_qlog.c @@ -184,8 +184,7 @@ static uint8_t *write_pair_cid_impl(uint8_t *p, const uint8_t *name, write_pair_cid_impl((DEST), (const uint8_t *)(NAME), sizeof(NAME) - 1, \ (VALUE)) -#define ngtcp2_make_vec_lit(S) \ - { (uint8_t *)(S), sizeof((S)) - 1 } +#define ngtcp2_make_vec_lit(S) {(uint8_t *)(S), sizeof((S)) - 1} static uint8_t *write_common_fields(uint8_t *p, const ngtcp2_cid *odcid) { p = write_verbatim( diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_range.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_range.c index ed07eb3..7bbefc0 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_range.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_range.c @@ -35,9 +35,11 @@ ngtcp2_range ngtcp2_range_intersect(const ngtcp2_range *a, ngtcp2_range r = {0, 0}; uint64_t begin = ngtcp2_max_uint64(a->begin, b->begin); uint64_t end = ngtcp2_min_uint64(a->end, b->end); + if (begin < end) { ngtcp2_range_init(&r, begin, end); } + return r; } diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_range.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_range.h index a776c4e..cf01ef3 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_range.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_range.h @@ -58,7 +58,7 @@ uint64_t ngtcp2_range_len(const ngtcp2_range *r); /* * ngtcp2_range_eq returns nonzero if |a| equals |b|, such that - * a->begin == b->begin, and a->end == b->end hold. + * a->begin == b->begin and a->end == b->end hold. */ int ngtcp2_range_eq(const ngtcp2_range *a, const ngtcp2_range *b); diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rob.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rob.c index 4fa3b83..596e76d 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rob.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rob.c @@ -56,7 +56,6 @@ int ngtcp2_rob_data_new(ngtcp2_rob_data **pd, uint64_t offset, size_t chunk, (*pd)->range.begin = offset; (*pd)->range.end = offset + chunk; (*pd)->begin = (uint8_t *)(*pd) + sizeof(ngtcp2_rob_data); - (*pd)->end = (*pd)->begin + chunk; return 0; } @@ -177,9 +176,11 @@ int ngtcp2_rob_push(ngtcp2_rob *rob, uint64_t offset, const uint8_t *data, if (!ngtcp2_range_len(&m)) { break; } + if (ngtcp2_range_eq(&g->range, &m)) { ngtcp2_ksl_remove_hint(&rob->gapksl, &it, &it, &g->range); ngtcp2_rob_gap_del(g, rob->mem); + rv = rob_write_data(rob, m.begin, data + (m.begin - offset), (size_t)ngtcp2_range_len(&m)); if (rv != 0) { @@ -188,17 +189,21 @@ int ngtcp2_rob_push(ngtcp2_rob *rob, uint64_t offset, const uint8_t *data, continue; } + ngtcp2_range_cut(&l, &r, &g->range, &m); + if (ngtcp2_range_len(&l)) { ngtcp2_ksl_update_key(&rob->gapksl, &g->range, &l); g->range = l; if (ngtcp2_range_len(&r)) { ngtcp2_rob_gap *ng; + rv = ngtcp2_rob_gap_new(&ng, r.begin, r.end, rob->mem); if (rv != 0) { return rv; } + rv = ngtcp2_ksl_insert(&rob->gapksl, &it, &ng->range, ng); if (rv != 0) { ngtcp2_rob_gap_del(ng, rob->mem); @@ -209,13 +214,16 @@ int ngtcp2_rob_push(ngtcp2_rob *rob, uint64_t offset, const uint8_t *data, ngtcp2_ksl_update_key(&rob->gapksl, &g->range, &r); g->range = r; } + rv = rob_write_data(rob, m.begin, data + (m.begin - offset), (size_t)ngtcp2_range_len(&m)); if (rv != 0) { return rv; } + ngtcp2_ksl_it_next(&it); } + return 0; } @@ -231,12 +239,16 @@ void ngtcp2_rob_remove_prefix(ngtcp2_rob *rob, uint64_t offset) { if (offset <= g->range.begin) { break; } + if (offset < g->range.end) { ngtcp2_range r = {offset, g->range.end}; + ngtcp2_ksl_update_key(&rob->gapksl, &g->range, &r); g->range.begin = offset; + break; } + ngtcp2_ksl_remove_hint(&rob->gapksl, &it, &it, &g->range); ngtcp2_rob_gap_del(g, rob->mem); } @@ -248,6 +260,7 @@ void ngtcp2_rob_remove_prefix(ngtcp2_rob *rob, uint64_t offset) { if (offset < d->range.begin + rob->chunk) { return; } + ngtcp2_ksl_remove_hint(&rob->dataksl, &it, &it, &d->range); ngtcp2_rob_data_del(d, rob->mem); } diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rob.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rob.h index 6518d56..9ebc68b 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rob.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rob.h @@ -70,12 +70,10 @@ void ngtcp2_rob_gap_del(ngtcp2_rob_gap *g, const ngtcp2_mem *mem); * ngtcp2_rob_data holds the buffered stream data. */ typedef struct ngtcp2_rob_data { - /* range is the range of this gap. */ + /* range is the range of this data. */ ngtcp2_range range; /* begin points to the buffer. */ uint8_t *begin; - /* end points to the one beyond of the last byte of the buffer */ - uint8_t *end; } ngtcp2_rob_data; /* @@ -110,8 +108,8 @@ typedef struct ngtcp2_rob { /* gapksl maintains the range of offset which is not received yet. Initially, its range is [0, UINT64_MAX). */ ngtcp2_ksl gapksl; - /* dataksl maintains the list of buffers which store received data - ordered by stream offset. */ + /* dataksl maintains the buffers which store received out-of-order + data ordered by stream offset. */ ngtcp2_ksl dataksl; /* mem is custom memory allocator */ const ngtcp2_mem *mem; @@ -137,8 +135,8 @@ int ngtcp2_rob_init(ngtcp2_rob *rob, size_t chunk, const ngtcp2_mem *mem); void ngtcp2_rob_free(ngtcp2_rob *rob); /* - * ngtcp2_rob_push adds new data of length |datalen| at the stream - * offset |offset|. + * ngtcp2_rob_push adds new data pointed by |data| of length |datalen| + * at the stream offset |offset|. * * This function returns 0 if it succeeds, or one of the following * negative error codes: @@ -151,7 +149,8 @@ int ngtcp2_rob_push(ngtcp2_rob *rob, uint64_t offset, const uint8_t *data, /* * ngtcp2_rob_remove_prefix removes gap up to |offset|, exclusive. It - * also removes data buffer if it is completely included in |offset|. + * also removes buffered data if it is completely included in + * |offset|. */ void ngtcp2_rob_remove_prefix(ngtcp2_rob *rob, uint64_t offset); @@ -159,7 +158,8 @@ void ngtcp2_rob_remove_prefix(ngtcp2_rob *rob, uint64_t offset); * ngtcp2_rob_data_at stores the pointer to the buffer of stream * offset |offset| to |*pdest| if it is available, and returns the * valid length of available data. If no data is available, it - * returns 0. + * returns 0. This function only returns the data before the first + * gap. It returns 0 even if data is available after the first gap. */ size_t ngtcp2_rob_data_at(ngtcp2_rob *rob, const uint8_t **pdest, uint64_t offset); diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rst.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rst.c index 862fa8d..4937c17 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rst.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rst.c @@ -35,12 +35,13 @@ void ngtcp2_rs_init(ngtcp2_rs *rs) { rs->interval = UINT64_MAX; rs->delivered = 0; rs->prior_delivered = 0; - rs->prior_ts = 0; + rs->prior_ts = UINT64_MAX; rs->tx_in_flight = 0; rs->lost = 0; rs->prior_lost = 0; rs->send_elapsed = 0; rs->ack_elapsed = 0; + rs->last_end_seq = -1; rs->is_app_limited = 0; } @@ -55,6 +56,7 @@ void ngtcp2_rst_init(ngtcp2_rst *rst) { rst->round_count = 0; rst->is_cwnd_limited = 0; rst->lost = 0; + rst->last_seq = -1; } void ngtcp2_rst_on_pkt_sent(ngtcp2_rst *rst, ngtcp2_rtb_entry *ent, @@ -68,6 +70,7 @@ void ngtcp2_rst_on_pkt_sent(ngtcp2_rst *rst, ngtcp2_rtb_entry *ent, ent->rst.is_app_limited = rst->app_limited != 0; ent->rst.tx_in_flight = cstat->bytes_in_flight + ent->pktlen; ent->rst.lost = rst->lost; + ent->rst.end_seq = ++rst->last_seq; } void ngtcp2_rst_on_ack_recv(ngtcp2_rst *rst, ngtcp2_conn_stat *cstat, @@ -84,7 +87,7 @@ void ngtcp2_rst_on_ack_recv(ngtcp2_rst *rst, ngtcp2_conn_stat *cstat, ++rst->round_count; } - if (rs->prior_ts == 0) { + if (rs->prior_ts == UINT64_MAX) { return; } @@ -104,12 +107,18 @@ void ngtcp2_rst_on_ack_recv(ngtcp2_rst *rst, ngtcp2_conn_stat *cstat, rate = rs->delivered * NGTCP2_SECONDS / rs->interval; - if (rate > ngtcp2_window_filter_get_best(&rst->wf) || !rst->app_limited) { + if (rate >= ngtcp2_window_filter_get_best(&rst->wf) || !rst->app_limited) { ngtcp2_window_filter_update(&rst->wf, rate, rst->round_count); cstat->delivery_rate_sec = ngtcp2_window_filter_get_best(&rst->wf); } } +static int rst_is_newest_pkt(const ngtcp2_rst *rst, const ngtcp2_rtb_entry *ent, + const ngtcp2_rs *rs) { + return ent->ts > rst->first_sent_ts || + (ent->ts == rst->first_sent_ts && ent->rst.end_seq > rs->last_end_seq); +} + void ngtcp2_rst_update_rate_sample(ngtcp2_rst *rst, const ngtcp2_rtb_entry *ent, ngtcp2_tstamp ts) { ngtcp2_rs *rs = &rst->rs; @@ -117,7 +126,7 @@ void ngtcp2_rst_update_rate_sample(ngtcp2_rst *rst, const ngtcp2_rtb_entry *ent, rst->delivered += ent->pktlen; rst->delivered_ts = ts; - if (ent->rst.delivered > rs->prior_delivered) { + if (rs->prior_ts == UINT64_MAX || rst_is_newest_pkt(rst, ent, rs)) { rs->prior_delivered = ent->rst.delivered; rs->prior_ts = ent->rst.delivered_ts; rs->is_app_limited = ent->rst.is_app_limited; @@ -125,6 +134,7 @@ void ngtcp2_rst_update_rate_sample(ngtcp2_rst *rst, const ngtcp2_rtb_entry *ent, rs->ack_elapsed = rst->delivered_ts - ent->rst.delivered_ts; rs->tx_in_flight = ent->rst.tx_in_flight; rs->prior_lost = ent->rst.lost; + rs->last_end_seq = ent->rst.end_seq; rst->first_sent_ts = ent->ts; } } diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rst.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rst.h index c9e1e16..74c1400 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rst.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rst.h @@ -51,6 +51,7 @@ typedef struct ngtcp2_rs { uint64_t prior_lost; ngtcp2_duration send_elapsed; ngtcp2_duration ack_elapsed; + int64_t last_end_seq; int is_app_limited; } ngtcp2_rs; @@ -58,7 +59,7 @@ void ngtcp2_rs_init(ngtcp2_rs *rs); /* * ngtcp2_rst implements delivery rate estimation described in - * https://tools.ietf.org/html/draft-cheng-iccrg-delivery-rate-estimation-00 + * https://ietf-wg-ccwg.github.io/draft-cardwell-ccwg-bbr/draft-cardwell-ccwg-bbr.html */ typedef struct ngtcp2_rst { ngtcp2_rs rs; @@ -70,6 +71,11 @@ typedef struct ngtcp2_rst { uint64_t next_round_delivered; uint64_t round_count; uint64_t lost; + /* last_seq is the sequence number of packets across all packet + number spaces. If we would adopt single packet number sequence + across all packet number spaces, we can replace this with a + packet number. */ + int64_t last_seq; int is_cwnd_limited; } ngtcp2_rst; diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rtb.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rtb.h index a1ff208..043cff3 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rtb.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_rtb.h @@ -111,6 +111,7 @@ struct ngtcp2_rtb_entry { ngtcp2_tstamp first_sent_ts; uint64_t tx_in_flight; uint64_t lost; + int64_t end_seq; int is_app_limited; } rst; /* flags is bitwise-OR of zero or more of diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_strm.c b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_strm.c index 15b3827..de92f33 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_strm.c +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_strm.c @@ -40,8 +40,9 @@ void ngtcp2_strm_init(ngtcp2_strm *strm, int64_t stream_id, uint32_t flags, uint64_t max_rx_offset, uint64_t max_tx_offset, void *stream_user_data, ngtcp2_objalloc *frc_objalloc, const ngtcp2_mem *mem) { - strm->frc_objalloc = frc_objalloc; + strm->pe.index = NGTCP2_PQ_BAD_INDEX; strm->cycle = 0; + strm->frc_objalloc = frc_objalloc; strm->tx.acked_offset = NULL; strm->tx.cont_acked_offset = 0; strm->tx.streamfrq = NULL; @@ -56,13 +57,12 @@ void ngtcp2_strm_init(ngtcp2_strm *strm, int64_t stream_id, uint32_t flags, strm->rx.rob = NULL; strm->rx.cont_offset = 0; strm->rx.last_offset = 0; - strm->stream_id = stream_id; - strm->flags = flags; - strm->stream_user_data = stream_user_data; - strm->rx.window = strm->rx.max_offset = strm->rx.unsent_max_offset = + strm->rx.max_offset = strm->rx.unsent_max_offset = strm->rx.window = max_rx_offset; - strm->pe.index = NGTCP2_PQ_BAD_INDEX; strm->mem = mem; + strm->stream_id = stream_id; + strm->stream_user_data = stream_user_data; + strm->flags = flags; strm->app_error_code = 0; } @@ -271,6 +271,7 @@ static int strm_streamfrq_unacked_pop(ngtcp2_strm *strm, } ngtcp2_frame_chain_objalloc_del(frc, strm->frc_objalloc, strm->mem); + continue; } @@ -306,6 +307,7 @@ static int strm_streamfrq_unacked_pop(ngtcp2_strm *strm, fr->data[0].len -= (size_t)base_offset; *pfrc = frc; + return 0; } @@ -336,6 +338,7 @@ static int strm_streamfrq_unacked_pop(ngtcp2_strm *strm, assert(ngtcp2_err_is_fatal(rv)); ngtcp2_frame_chain_objalloc_del(nfrc, strm->frc_objalloc, strm->mem); ngtcp2_frame_chain_objalloc_del(frc, strm->frc_objalloc, strm->mem); + return rv; } @@ -350,14 +353,17 @@ static int strm_streamfrq_unacked_pop(ngtcp2_strm *strm, fr->fin = 0; fr->offset = offset + base_offset; fr->datacnt = end_idx - idx; + if (end_base_offset) { assert(fr->data[fr->datacnt - 1].len > end_base_offset); fr->data[fr->datacnt - 1].len = (size_t)end_base_offset; } + fr->data[0].base += base_offset; fr->data[0].len -= (size_t)base_offset; *pfrc = frc; + return 0; } @@ -385,6 +391,7 @@ int ngtcp2_strm_streamfrq_pop(ngtcp2_strm *strm, ngtcp2_frame_chain **pfrc, if (rv != 0) { return rv; } + if (frc == NULL) { *pfrc = NULL; return 0; @@ -401,7 +408,9 @@ int ngtcp2_strm_streamfrq_pop(ngtcp2_strm *strm, ngtcp2_frame_chain **pfrc, ngtcp2_frame_chain_objalloc_del(frc, strm->frc_objalloc, strm->mem); return rv; } + *pfrc = NULL; + return 0; } @@ -437,6 +446,7 @@ int ngtcp2_strm_streamfrq_pop(ngtcp2_strm *strm, ngtcp2_frame_chain **pfrc, assert(ngtcp2_err_is_fatal(rv)); ngtcp2_frame_chain_objalloc_del(nfrc, strm->frc_objalloc, strm->mem); ngtcp2_frame_chain_objalloc_del(frc, strm->frc_objalloc, strm->mem); + return rv; } @@ -501,8 +511,10 @@ int ngtcp2_strm_streamfrq_pop(ngtcp2_strm *strm, ngtcp2_frame_chain **pfrc, assert(ngtcp2_err_is_fatal(rv)); ngtcp2_frame_chain_objalloc_del(nfrc, strm->frc_objalloc, strm->mem); ngtcp2_frame_chain_objalloc_del(frc, strm->frc_objalloc, strm->mem); + return rv; } + break; } @@ -560,6 +572,7 @@ int ngtcp2_strm_streamfrq_pop(ngtcp2_strm *strm, ngtcp2_frame_chain **pfrc, } *pfrc = frc; + return 0; } @@ -606,9 +619,11 @@ uint64_t ngtcp2_strm_streamfrq_unacked_offset(ngtcp2_strm *strm) { if (gap.begin <= fr->offset) { return fr->offset; } + if (gap.begin < fr->offset + datalen) { return gap.begin; } + if (fr->offset + datalen == gap.begin && fr->fin && !(strm->flags & NGTCP2_STRM_FLAG_FIN_ACKED)) { return fr->offset + datalen; @@ -625,6 +640,7 @@ ngtcp2_frame_chain *ngtcp2_strm_streamfrq_top(ngtcp2_strm *strm) { assert(ngtcp2_ksl_len(strm->tx.streamfrq)); it = ngtcp2_ksl_begin(strm->tx.streamfrq); + return ngtcp2_ksl_it_get(&it); } @@ -645,6 +661,7 @@ void ngtcp2_strm_streamfrq_clear(ngtcp2_strm *strm) { frc = ngtcp2_ksl_it_get(&it); ngtcp2_frame_chain_objalloc_del(frc, strm->frc_objalloc, strm->mem); } + ngtcp2_ksl_clear(strm->tx.streamfrq); } diff --git a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_strm.h b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_strm.h index e396b24..e7e2fa6 100644 --- a/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_strm.h +++ b/src/contrib/libngtcp2/ngtcp2/lib/ngtcp2_strm.h @@ -108,13 +108,13 @@ struct ngtcp2_strm { acked_offset is used instead. */ uint64_t cont_acked_offset; /* streamfrq contains STREAM or CRYPTO frame for - retransmission. The flow control credits have been paid - when they are transmitted first time. There are no + retransmission. The flow control credits have already been + paid when they are transmitted first time. There are no restriction regarding flow control for retransmission. */ ngtcp2_ksl *streamfrq; - /* offset is the next offset of outgoing data. In other words, it - is the number of bytes sent in this stream without - duplication. */ + /* offset is the next offset of new outgoing data. In other + words, it is the number of bytes sent in this stream + without duplication. */ uint64_t offset; /* max_tx_offset is the maximum offset that local endpoint can send for this stream. */ @@ -218,8 +218,8 @@ int ngtcp2_strm_recv_reordering(ngtcp2_strm *strm, const uint8_t *data, size_t datalen, uint64_t offset); /* - * ngtcp2_strm_update_rx_offset tells that data up to offset bytes are - * received in order. + * ngtcp2_strm_update_rx_offset tells that data up to |offset| bytes + * are received in order. */ void ngtcp2_strm_update_rx_offset(ngtcp2_strm *strm, uint64_t offset); @@ -230,13 +230,14 @@ void ngtcp2_strm_update_rx_offset(ngtcp2_strm *strm, uint64_t offset); void ngtcp2_strm_discard_reordered_data(ngtcp2_strm *strm); /* - * ngtcp2_strm_shutdown shutdowns |strm|. |flags| should be - * NGTCP2_STRM_FLAG_SHUT_RD, and/or NGTCP2_STRM_FLAG_SHUT_WR. + * ngtcp2_strm_shutdown shutdowns |strm|. |flags| should be one of + * NGTCP2_STRM_FLAG_SHUT_RD, NGTCP2_STRM_FLAG_SHUT_WR, and + * NGTCP2_STRM_FLAG_SHUT_RDWR. */ void ngtcp2_strm_shutdown(ngtcp2_strm *strm, uint32_t flags); /* - * ngtcp2_strm_streamfrq_push pushes |frc| to streamfrq for + * ngtcp2_strm_streamfrq_push pushes |frc| to strm->tx.streamfrq for * retransmission. * * This function returns 0 if it succeeds, or one of the following @@ -248,11 +249,12 @@ void ngtcp2_strm_shutdown(ngtcp2_strm *strm, uint32_t flags); int ngtcp2_strm_streamfrq_push(ngtcp2_strm *strm, ngtcp2_frame_chain *frc); /* - * ngtcp2_strm_streamfrq_pop pops the first ngtcp2_frame_chain and - * assigns it to |*pfrc|. This function splits into or merges several - * ngtcp2_frame_chain objects so that the returned ngtcp2_frame_chain - * has at most |left| data length. If there is no frames to send, - * this function returns 0 and |*pfrc| is NULL. + * ngtcp2_strm_streamfrq_pop assigns a ngtcp2_frame_chain that only + * contains unacknowledged stream data with smallest offset to |*pfrc| + * for retransmission. The assigned ngtcp2_frame_chain has stream + * data at most |left| bytes. strm->tx.streamfrq is adjusted to + * exclude the portion of data included in it. If there is no stream + * data to send, this function returns 0 and |*pfrc| is NULL. * * This function returns 0 if it succeeds, or one of the following * negative error codes: @@ -305,7 +307,7 @@ int ngtcp2_strm_is_all_tx_data_fin_acked(ngtcp2_strm *strm); /* * ngtcp2_strm_get_unacked_range_after returns the range that is not - * acknowledged yet and intersects or comes after |offset|. + * acknowledged yet and includes or comes after |offset|. */ ngtcp2_range ngtcp2_strm_get_unacked_range_after(ngtcp2_strm *strm, uint64_t offset); @@ -318,8 +320,8 @@ ngtcp2_range ngtcp2_strm_get_unacked_range_after(ngtcp2_strm *strm, uint64_t ngtcp2_strm_get_acked_offset(ngtcp2_strm *strm); /* - * ngtcp2_strm_ack_data tells |strm| that the data [offset, - * offset+len) is acknowledged by a remote endpoint. + * ngtcp2_strm_ack_data tells |strm| that the data [|offset|, |offset| + * + |len|) is acknowledged by a remote endpoint. */ int ngtcp2_strm_ack_data(ngtcp2_strm *strm, uint64_t offset, uint64_t len); diff --git a/src/contrib/libngtcp2/ngtcp2/version.h b/src/contrib/libngtcp2/ngtcp2/version.h index 85ef77b..4aa1164 100644 --- a/src/contrib/libngtcp2/ngtcp2/version.h +++ b/src/contrib/libngtcp2/ngtcp2/version.h @@ -36,7 +36,7 @@ * * Version number of the ngtcp2 library release. */ -#define NGTCP2_VERSION "1.6.0" +#define NGTCP2_VERSION "1.7.0" /** * @macro @@ -46,6 +46,6 @@ * number, 8 bits for minor and 8 bits for patch. Version 1.2.3 * becomes 0x010203. */ -#define NGTCP2_VERSION_NUM 0x010600 +#define NGTCP2_VERSION_NUM 0x010700 #endif /* VERSION_H */ |