/*
 * 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);
}