Adding upstream version 0.12.1+dfsg.upstream/0.12.1+dfsgupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 470 insertions, 0 deletions

diff --git a/tests/ngtcp2_rtb_test.c b/tests/ngtcp2_rtb_test.c
new file mode 100644
index 0000000..7c91c38
--- /dev/null
+++ b/tests/ngtcp2_rtb_test.c
@@ -0,0 +1,470 @@
+/*
+ * ngtcp2
+ *
+ * Copyright (c) 2017 ngtcp2 contributors
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+#include "ngtcp2_rtb_test.h"
+
+#include <assert.h>
+
+#include <CUnit/CUnit.h>
+
+#include "ngtcp2_rtb.h"
+#include "ngtcp2_test_helper.h"
+#include "ngtcp2_mem.h"
+#include "ngtcp2_pkt.h"
+
+static void conn_stat_init(ngtcp2_conn_stat *cstat) {
+  memset(cstat, 0, sizeof(*cstat));
+  cstat->max_tx_udp_payload_size = NGTCP2_MAX_UDP_PAYLOAD_SIZE;
+}
+
+void test_ngtcp2_rtb_add(void) {
+  ngtcp2_rtb rtb;
+  ngtcp2_rtb_entry *ent;
+  int rv;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  ngtcp2_pkt_hd hd;
+  ngtcp2_log log;
+  ngtcp2_cid dcid;
+  ngtcp2_ksl_it it;
+  ngtcp2_conn_stat cstat;
+  ngtcp2_cc cc;
+  ngtcp2_strm crypto;
+  const ngtcp2_pktns_id pktns_id = NGTCP2_PKTNS_ID_HANDSHAKE;
+  ngtcp2_rst rst;
+  ngtcp2_objalloc frc_objalloc;
+  ngtcp2_objalloc rtb_entry_objalloc;
+
+  ngtcp2_objalloc_init(&frc_objalloc, 1024, mem);
+  ngtcp2_objalloc_init(&rtb_entry_objalloc, 1024, mem);
+
+  ngtcp2_strm_init(&crypto, 0, NGTCP2_STRM_FLAG_NONE, 0, 0, NULL, &frc_objalloc,
+                   mem);
+  dcid_init(&dcid);
+  conn_stat_init(&cstat);
+  ngtcp2_rst_init(&rst);
+  ngtcp2_log_init(&log, NULL, NULL, 0, NULL);
+  ngtcp2_cc_reno_cc_init(&cc, &log, mem);
+  ngtcp2_rtb_init(&rtb, pktns_id, &crypto, &rst, &cc, &log, NULL,
+                  &rtb_entry_objalloc, &frc_objalloc, mem);
+
+  ngtcp2_pkt_hd_init(&hd, NGTCP2_PKT_FLAG_NONE, NGTCP2_PKT_1RTT, &dcid, NULL,
+                     1000000007, 1, NGTCP2_PROTO_VER_V1, 0);
+
+  rv = ngtcp2_rtb_entry_objalloc_new(
+      &ent, &hd, NULL, 10, 0, NGTCP2_RTB_ENTRY_FLAG_NONE, &rtb_entry_objalloc);
+
+  CU_ASSERT(0 == rv);
+
+  ngtcp2_rtb_add(&rtb, ent, &cstat);
+
+  ngtcp2_pkt_hd_init(&hd, NGTCP2_PKT_FLAG_NONE, NGTCP2_PKT_1RTT, &dcid, NULL,
+                     1000000008, 2, NGTCP2_PROTO_VER_V1, 0);
+
+  rv = ngtcp2_rtb_entry_objalloc_new(
+      &ent, &hd, NULL, 9, 0, NGTCP2_RTB_ENTRY_FLAG_NONE, &rtb_entry_objalloc);
+
+  CU_ASSERT(0 == rv);
+
+  ngtcp2_rtb_add(&rtb, ent, &cstat);
+
+  ngtcp2_pkt_hd_init(&hd, NGTCP2_PKT_FLAG_NONE, NGTCP2_PKT_1RTT, &dcid, NULL,
+                     1000000009, 4, NGTCP2_PROTO_VER_V1, 0);
+
+  rv = ngtcp2_rtb_entry_objalloc_new(
+      &ent, &hd, NULL, 11, 0, NGTCP2_RTB_ENTRY_FLAG_NONE, &rtb_entry_objalloc);
+
+  CU_ASSERT(0 == rv);
+
+  ngtcp2_rtb_add(&rtb, ent, &cstat);
+
+  it = ngtcp2_rtb_head(&rtb);
+  ent = ngtcp2_ksl_it_get(&it);
+
+  /* Check the top of the queue */
+  CU_ASSERT(1000000009 == ent->hd.pkt_num);
+
+  ngtcp2_ksl_it_next(&it);
+  ent = ngtcp2_ksl_it_get(&it);
+
+  CU_ASSERT(1000000008 == ent->hd.pkt_num);
+
+  ngtcp2_ksl_it_next(&it);
+  ent = ngtcp2_ksl_it_get(&it);
+
+  CU_ASSERT(1000000007 == ent->hd.pkt_num);
+
+  ngtcp2_ksl_it_next(&it);
+
+  CU_ASSERT(ngtcp2_ksl_it_end(&it));
+
+  ngtcp2_rtb_free(&rtb);
+  ngtcp2_cc_reno_cc_free(&cc, mem);
+  ngtcp2_strm_free(&crypto);
+
+  ngtcp2_objalloc_free(&rtb_entry_objalloc);
+  ngtcp2_objalloc_free(&frc_objalloc);
+}
+
+static void add_rtb_entry_range(ngtcp2_rtb *rtb, int64_t base_pkt_num,
+                                size_t len, ngtcp2_conn_stat *cstat,
+                                ngtcp2_objalloc *objalloc) {
+  ngtcp2_pkt_hd hd;
+  ngtcp2_rtb_entry *ent;
+  size_t i;
+  ngtcp2_cid dcid;
+
+  dcid_init(&dcid);
+
+  for (i = 0; i < len; ++i) {
+    ngtcp2_pkt_hd_init(&hd, NGTCP2_PKT_FLAG_NONE, NGTCP2_PKT_1RTT, &dcid, NULL,
+                       base_pkt_num + (int64_t)i, 1, NGTCP2_PROTO_VER_V1, 0);
+    ngtcp2_rtb_entry_objalloc_new(&ent, &hd, NULL, 0, 0,
+                                  NGTCP2_RTB_ENTRY_FLAG_NONE, objalloc);
+    ngtcp2_rtb_add(rtb, ent, cstat);
+  }
+}
+
+static void setup_rtb_fixture(ngtcp2_rtb *rtb, ngtcp2_conn_stat *cstat,
+                              ngtcp2_objalloc *objalloc) {
+  /* 100, ..., 154 */
+  add_rtb_entry_range(rtb, 100, 55, cstat, objalloc);
+  /* 180, ..., 184 */
+  add_rtb_entry_range(rtb, 180, 5, cstat, objalloc);
+  /* 440, ..., 446 */
+  add_rtb_entry_range(rtb, 440, 7, cstat, objalloc);
+}
+
+static void assert_rtb_entry_not_found(ngtcp2_rtb *rtb, int64_t pkt_num) {
+  ngtcp2_ksl_it it = ngtcp2_rtb_head(rtb);
+  ngtcp2_rtb_entry *ent;
+
+  for (; !ngtcp2_ksl_it_end(&it); ngtcp2_ksl_it_next(&it)) {
+    ent = ngtcp2_ksl_it_get(&it);
+    CU_ASSERT(ent->hd.pkt_num != pkt_num);
+  }
+}
+
+void test_ngtcp2_rtb_recv_ack(void) {
+  ngtcp2_rtb rtb;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  ngtcp2_max_frame mfr;
+  ngtcp2_ack *fr = &mfr.ackfr.ack;
+  ngtcp2_ack_range *ranges;
+  ngtcp2_log log;
+  ngtcp2_conn_stat cstat;
+  ngtcp2_cc cc;
+  ngtcp2_pkt_hd hd;
+  ngtcp2_ssize num_acked;
+  ngtcp2_strm crypto;
+  const ngtcp2_pktns_id pktns_id = NGTCP2_PKTNS_ID_HANDSHAKE;
+  ngtcp2_rst rst;
+  ngtcp2_objalloc frc_objalloc;
+  ngtcp2_objalloc rtb_entry_objalloc;
+
+  ngtcp2_objalloc_init(&frc_objalloc, 1024, mem);
+  ngtcp2_objalloc_init(&rtb_entry_objalloc, 1024, mem);
+
+  ngtcp2_strm_init(&crypto, 0, NGTCP2_STRM_FLAG_NONE, 0, 0, NULL, &frc_objalloc,
+                   mem);
+  ngtcp2_log_init(&log, NULL, NULL, 0, NULL);
+  ngtcp2_pkt_hd_init(&hd, NGTCP2_PKT_FLAG_NONE, NGTCP2_PKT_1RTT, NULL, NULL, 0,
+                     1, NGTCP2_PROTO_VER_V1, 0);
+
+  /* no ack block */
+  conn_stat_init(&cstat);
+  ngtcp2_rst_init(&rst);
+  ngtcp2_cc_reno_cc_init(&cc, &log, mem);
+  ngtcp2_rtb_init(&rtb, pktns_id, &crypto, &rst, &cc, &log, NULL,
+                  &rtb_entry_objalloc, &frc_objalloc, mem);
+  setup_rtb_fixture(&rtb, &cstat, &rtb_entry_objalloc);
+
+  CU_ASSERT(67 == ngtcp2_ksl_len(&rtb.ents));
+
+  fr->largest_ack = 446;
+  fr->first_ack_range = 1;
+  fr->rangecnt = 0;
+
+  num_acked =
+      ngtcp2_rtb_recv_ack(&rtb, fr, &cstat, NULL, NULL, 1000000009, 1000000009);
+
+  CU_ASSERT(2 == num_acked);
+  CU_ASSERT(65 == ngtcp2_ksl_len(&rtb.ents));
+  assert_rtb_entry_not_found(&rtb, 446);
+  assert_rtb_entry_not_found(&rtb, 445);
+
+  ngtcp2_rtb_free(&rtb);
+  ngtcp2_cc_reno_cc_free(&cc, mem);
+
+  /* with ack block */
+  conn_stat_init(&cstat);
+  ngtcp2_cc_reno_cc_init(&cc, &log, mem);
+  ngtcp2_rtb_init(&rtb, pktns_id, &crypto, &rst, &cc, &log, NULL,
+                  &rtb_entry_objalloc, &frc_objalloc, mem);
+  setup_rtb_fixture(&rtb, &cstat, &rtb_entry_objalloc);
+
+  fr->largest_ack = 441;
+  fr->first_ack_range = 3; /* (441), (440), 439, 438 */
+  fr->rangecnt = 2;
+  ranges = fr->ranges;
+  ranges[0].gap = 253;
+  ranges[0].len = 0; /* (183) */
+  ranges[1].gap = 1; /* 182, 181 */
+  ranges[1].len = 1; /* (180), 179 */
+
+  num_acked =
+      ngtcp2_rtb_recv_ack(&rtb, fr, &cstat, NULL, NULL, 1000000009, 1000000009);
+
+  CU_ASSERT(4 == num_acked);
+  CU_ASSERT(63 == ngtcp2_ksl_len(&rtb.ents));
+  CU_ASSERT(441 == rtb.largest_acked_tx_pkt_num);
+  assert_rtb_entry_not_found(&rtb, 441);
+  assert_rtb_entry_not_found(&rtb, 440);
+  assert_rtb_entry_not_found(&rtb, 183);
+  assert_rtb_entry_not_found(&rtb, 180);
+
+  ngtcp2_rtb_free(&rtb);
+  ngtcp2_cc_reno_cc_free(&cc, mem);
+
+  /* gap+len points to pkt_num 0 */
+  conn_stat_init(&cstat);
+  ngtcp2_cc_reno_cc_init(&cc, &log, mem);
+  ngtcp2_rtb_init(&rtb, pktns_id, &crypto, &rst, &cc, &log, NULL,
+                  &rtb_entry_objalloc, &frc_objalloc, mem);
+  add_rtb_entry_range(&rtb, 0, 1, &cstat, &rtb_entry_objalloc);
+
+  fr->largest_ack = 250;
+  fr->first_ack_range = 0;
+  fr->rangecnt = 1;
+  fr->ranges[0].gap = 248;
+  fr->ranges[0].len = 0;
+
+  num_acked =
+      ngtcp2_rtb_recv_ack(&rtb, fr, &cstat, NULL, NULL, 1000000009, 1000000009);
+
+  CU_ASSERT(1 == num_acked);
+  assert_rtb_entry_not_found(&rtb, 0);
+
+  ngtcp2_rtb_free(&rtb);
+  ngtcp2_cc_reno_cc_free(&cc, mem);
+
+  /* pkt_num = 0 (first ack block) */
+  conn_stat_init(&cstat);
+  ngtcp2_cc_reno_cc_init(&cc, &log, mem);
+  ngtcp2_rtb_init(&rtb, pktns_id, &crypto, &rst, &cc, &log, NULL,
+                  &rtb_entry_objalloc, &frc_objalloc, mem);
+  add_rtb_entry_range(&rtb, 0, 1, &cstat, &rtb_entry_objalloc);
+
+  fr->largest_ack = 0;
+  fr->first_ack_range = 0;
+  fr->rangecnt = 0;
+
+  num_acked =
+      ngtcp2_rtb_recv_ack(&rtb, fr, &cstat, NULL, NULL, 1000000009, 1000000009);
+
+  CU_ASSERT(1 == num_acked);
+  assert_rtb_entry_not_found(&rtb, 0);
+
+  ngtcp2_rtb_free(&rtb);
+  ngtcp2_cc_reno_cc_free(&cc, mem);
+
+  /* pkt_num = 0 */
+  conn_stat_init(&cstat);
+  ngtcp2_cc_reno_cc_init(&cc, &log, mem);
+  ngtcp2_rtb_init(&rtb, pktns_id, &crypto, &rst, &cc, &log, NULL,
+                  &rtb_entry_objalloc, &frc_objalloc, mem);
+  add_rtb_entry_range(&rtb, 0, 1, &cstat, &rtb_entry_objalloc);
+
+  fr->largest_ack = 2;
+  fr->first_ack_range = 0;
+  fr->rangecnt = 1;
+  fr->ranges[0].gap = 0;
+  fr->ranges[0].len = 0;
+
+  num_acked =
+      ngtcp2_rtb_recv_ack(&rtb, fr, &cstat, NULL, NULL, 1000000009, 1000000009);
+
+  CU_ASSERT(1 == num_acked);
+  assert_rtb_entry_not_found(&rtb, 0);
+
+  ngtcp2_rtb_free(&rtb);
+  ngtcp2_cc_reno_cc_free(&cc, mem);
+  ngtcp2_strm_free(&crypto);
+
+  ngtcp2_objalloc_free(&rtb_entry_objalloc);
+  ngtcp2_objalloc_free(&frc_objalloc);
+}
+
+void test_ngtcp2_rtb_lost_pkt_ts(void) {
+  ngtcp2_rtb rtb;
+  const ngtcp2_pktns_id pktns_id = NGTCP2_PKTNS_ID_APPLICATION;
+  ngtcp2_strm crypto;
+  ngtcp2_log log;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  ngtcp2_cc cc;
+  ngtcp2_rst rst;
+  ngtcp2_conn_stat cstat;
+  ngtcp2_ksl_it it;
+  ngtcp2_rtb_entry *ent;
+  ngtcp2_objalloc frc_objalloc;
+  ngtcp2_objalloc rtb_entry_objalloc;
+
+  ngtcp2_objalloc_init(&frc_objalloc, 1024, mem);
+  ngtcp2_objalloc_init(&rtb_entry_objalloc, 1024, mem);
+
+  ngtcp2_strm_init(&crypto, 0, NGTCP2_STRM_FLAG_NONE, 0, 0, NULL, &frc_objalloc,
+                   mem);
+  ngtcp2_log_init(&log, NULL, NULL, 0, NULL);
+
+  conn_stat_init(&cstat);
+  ngtcp2_rst_init(&rst);
+  ngtcp2_cc_reno_cc_init(&cc, &log, mem);
+  ngtcp2_rtb_init(&rtb, pktns_id, &crypto, &rst, &cc, &log, NULL,
+                  &rtb_entry_objalloc, &frc_objalloc, mem);
+
+  add_rtb_entry_range(&rtb, 0, 1, &cstat, &rtb_entry_objalloc);
+
+  CU_ASSERT(UINT64_MAX == ngtcp2_rtb_lost_pkt_ts(&rtb));
+
+  it = ngtcp2_ksl_end(&rtb.ents);
+  ngtcp2_ksl_it_prev(&it);
+  ent = ngtcp2_ksl_it_get(&it);
+  ent->flags |= NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED;
+  ent->lost_ts = 16777217;
+
+  CU_ASSERT(16777217 == ngtcp2_rtb_lost_pkt_ts(&rtb));
+
+  ngtcp2_rtb_free(&rtb);
+  ngtcp2_cc_reno_cc_free(&cc, mem);
+  ngtcp2_strm_free(&crypto);
+
+  ngtcp2_objalloc_free(&rtb_entry_objalloc);
+  ngtcp2_objalloc_free(&frc_objalloc);
+}
+
+void test_ngtcp2_rtb_remove_expired_lost_pkt(void) {
+  ngtcp2_rtb rtb;
+  const ngtcp2_pktns_id pktns_id = NGTCP2_PKTNS_ID_APPLICATION;
+  ngtcp2_strm crypto;
+  ngtcp2_log log;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  ngtcp2_cc cc;
+  ngtcp2_rst rst;
+  ngtcp2_conn_stat cstat;
+  ngtcp2_ksl_it it;
+  ngtcp2_rtb_entry *ent;
+  size_t i;
+  ngtcp2_objalloc frc_objalloc;
+  ngtcp2_objalloc rtb_entry_objalloc;
+
+  ngtcp2_objalloc_init(&frc_objalloc, 1024, mem);
+  ngtcp2_objalloc_init(&rtb_entry_objalloc, 1024, mem);
+
+  ngtcp2_strm_init(&crypto, 0, NGTCP2_STRM_FLAG_NONE, 0, 0, NULL, &frc_objalloc,
+                   mem);
+  ngtcp2_log_init(&log, NULL, NULL, 0, NULL);
+
+  conn_stat_init(&cstat);
+  ngtcp2_rst_init(&rst);
+  ngtcp2_cc_reno_cc_init(&cc, &log, mem);
+  ngtcp2_rtb_init(&rtb, pktns_id, &crypto, &rst, &cc, &log, NULL,
+                  &rtb_entry_objalloc, &frc_objalloc, mem);
+
+  add_rtb_entry_range(&rtb, 0, 7, &cstat, &rtb_entry_objalloc);
+
+  it = ngtcp2_ksl_end(&rtb.ents);
+
+  for (i = 0; i < 5; ++i) {
+    ngtcp2_ksl_it_prev(&it);
+    ent = ngtcp2_ksl_it_get(&it);
+    ent->flags |= NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED;
+    ent->lost_ts = 16777217 + i;
+  }
+
+  ngtcp2_rtb_remove_expired_lost_pkt(&rtb, 1, 16777219);
+
+  CU_ASSERT(5 == ngtcp2_ksl_len(&rtb.ents));
+
+  ngtcp2_rtb_remove_expired_lost_pkt(&rtb, 1, 16777223);
+
+  CU_ASSERT(2 == ngtcp2_ksl_len(&rtb.ents));
+
+  ngtcp2_rtb_free(&rtb);
+  ngtcp2_cc_reno_cc_free(&cc, mem);
+  ngtcp2_strm_free(&crypto);
+
+  ngtcp2_objalloc_free(&rtb_entry_objalloc);
+  ngtcp2_objalloc_free(&frc_objalloc);
+}
+
+void test_ngtcp2_rtb_remove_excessive_lost_pkt(void) {
+  ngtcp2_rtb rtb;
+  const ngtcp2_pktns_id pktns_id = NGTCP2_PKTNS_ID_APPLICATION;
+  ngtcp2_strm crypto;
+  ngtcp2_log log;
+  const ngtcp2_mem *mem = ngtcp2_mem_default();
+  ngtcp2_cc cc;
+  ngtcp2_rst rst;
+  ngtcp2_conn_stat cstat;
+  ngtcp2_ksl_it it;
+  ngtcp2_rtb_entry *ent;
+  size_t i;
+  ngtcp2_objalloc frc_objalloc;
+  ngtcp2_objalloc rtb_entry_objalloc;
+
+  ngtcp2_objalloc_init(&frc_objalloc, 1024, mem);
+  ngtcp2_objalloc_init(&rtb_entry_objalloc, 1024, mem);
+
+  ngtcp2_strm_init(&crypto, 0, NGTCP2_STRM_FLAG_NONE, 0, 0, NULL, &frc_objalloc,
+                   mem);
+  ngtcp2_log_init(&log, NULL, NULL, 0, NULL);
+
+  conn_stat_init(&cstat);
+  ngtcp2_rst_init(&rst);
+  ngtcp2_cc_reno_cc_init(&cc, &log, mem);
+  ngtcp2_rtb_init(&rtb, pktns_id, &crypto, &rst, &cc, &log, NULL,
+                  &rtb_entry_objalloc, &frc_objalloc, mem);
+
+  add_rtb_entry_range(&rtb, 0, 7, &cstat, &rtb_entry_objalloc);
+
+  it = ngtcp2_ksl_end(&rtb.ents);
+
+  for (i = 0; i < 5; ++i) {
+    ngtcp2_ksl_it_prev(&it);
+    ent = ngtcp2_ksl_it_get(&it);
+    ent->flags |= NGTCP2_RTB_ENTRY_FLAG_LOST_RETRANSMITTED;
+    ent->lost_ts = 16777217;
+    ++rtb.num_lost_pkts;
+  }
+
+  ngtcp2_rtb_remove_excessive_lost_pkt(&rtb, 2);
+
+  CU_ASSERT(4 == ngtcp2_ksl_len(&rtb.ents));
+
+  ngtcp2_rtb_free(&rtb);
+  ngtcp2_cc_reno_cc_free(&cc, mem);
+  ngtcp2_strm_free(&crypto);
+
+  ngtcp2_objalloc_free(&rtb_entry_objalloc);
+  ngtcp2_objalloc_free(&frc_objalloc);
+}