/* Copyright (c) 2019-2021, The Tor Project, Inc. */
/* See LICENSE for licensing information */

/**
 * \file sendme_common.h
 * \brief Header file for sendme_common.c
 **/

#ifndef TOR_SENDME_COMMON_H
#define TOR_SENDME_COMMON_H

#include "core/or/crypt_path_st.h"
#include "core/or/circuit_st.h"

/** Signifies which sendme algorithm to use */
typedef enum {
  /** OG Tor fixed-sized circ and stream windows. It sucks, but it is important
   * to make sure that the new algs can compete with the old garbage. */
  SENDME_ALG_FIXED = 0,

  /**
   * Prop#324 TOR_WESTWOOD - Deliberately agressive. Westwood may not even
   * converge to fairness in some cases because max RTT will also increase
   * on congesgtion, which boosts the Westwood RTT congestion threshhold. So it
   * can cause runaway queue bloat, which may or may not lead to a robot
   * uprising... Ok that's Westworld, not Westwood. Still, we need to test
   * Vegas and NOLA against something more agressive to ensure they do not
   * starve in the presence of cheaters. We also need to make sure cheaters
   * trigger the oomkiller in those cases.
   *
   * Surprisingly, in live network testing against SENDME, this algorithm
   * can still stall out with current params.
   */
  SENDME_ALG_WESTWOOD = 1,

  /**
   * Prop#324 TOR_VEGAS - TCP Vegas-style BDP tracker. Because Vegas backs off
   * whenever it detects queue delay, it can be beaten out by more agressive
   * algs. However, in live network testing, it seems to do just fine against
   * current SENDMEs. It outperforms Westwood and does not stall. */
  SENDME_ALG_VEGAS = 2,

  /**
   * Prop#324: TOR_NOLA - NOLA looks the BDP right in the eye and uses it
   * immediately as CWND. No slow start, no other congestion signals, no delay,
   * no bullshit. Like TOR_VEGAS, it also uses agressive BDP estimates, to
   * avoid out-competition. It seems a bit better throughput than Vegas,
   * but its agressive BDP and rapid updates may lead to more queue latency. */
  SENDME_ALG_NOLA = 3,

  SENDME_ALG_MAX = 4,
} cc_alg_t;

/** Signifies how we estimate circuit BDP */
typedef enum {
  /* CWND-based BDP will respond to changes in RTT only, and is relative
   * to cwnd growth. So in slow-start, this will under-estimate BDP */
  BDP_ALG_CWND_RTT = 0,
  BDP_ALG_CWND_RTT_EWMA = 1,

  /* Sendme-based BDP will quickly measure BDP in less than
   * a cwnd worth of data when in use. So it should be good for slow-start.
   * But if the link goes idle, it will be vastly lower than true BDP. Thus,
   * this estimate gets reset when the cwnd is not fully utilized. */
  BDP_ALG_SENDME_RATE = 2,
  BDP_ALG_SENDME_RATE_EWMA = 3,

  /* In-flight BDP will cause the cwnd to drift down when underutilized;
   * this may be bad, esp since we don't exit steady-state when idle */
  BDP_ALG_INFLIGHT_RTT = 4,
  BDP_ALG_INFLIGHT_RTT_EWMA = 5,

  BDP_ALG_PIECEWISE = 6,
  BDP_ALG_PIECEWISE_EWMA = 7,
  BDP_ALG_MAX = 8,
} bdp_alg_t;

/** Fields common to all congestion control algorithms */
typedef struct congestion_control_t {
  /**
   * Smartlist of monotime timestamp of when we sent a data cell that is
   * pending a sendme. FIFO queue that is managed similar to
   * sendme_last_digests */
  smartlist_t *sendme_pending_timestamps;

  /**
   * Smartlist of monotime timestamp of when sendme's arrived.
   * FIFO queue that is managed similar to sendme_last_digests.
   * Used to estimate bandwidth. */
  smartlist_t *sendme_arrival_timestamps;

  /** RTT time data for congestion control.
   * XXX: These could be uint32_t but we'd need to check for overflow
   * just in case Tor is ever used on Mars. */
  uint64_t curr_rtt_usec;
  uint64_t ewma_rtt_usec;

  uint64_t min_rtt_usec;
  uint64_t max_rtt_usec;

  /* BDP estimates by algorithm */
  uint64_t bdp[BDP_ALG_MAX];

  /** Congestion window */
  uint64_t cwnd;

  /** Number of cells in-flight (sent but awaiting SENDME ack) **/
  uint64_t inflight;

  /**
   * For steady-state: the number of sendme acks until we will acknowledge
   * a congestion event again. We only allow one congestion event per
   * cwnd packets. */
  uint64_t next_cc_event;

  /** Are we in slow start? */
  bool in_slow_start;

  /** Is the local channel blocked on us? That's a congestion signal */
  bool blocked_chan;

  /* The following parameters are cached from consensus values upon
   * circuit setup. */

  /** Percent of cwnd to increment by during slow start */
  uint16_t cwnd_inc_pct_ss;

  /** Number of cells to increment cwnd by during steady state */
  uint16_t cwnd_inc;

  /** Minimum congestion window (must be at least sendme_inc) */
  uint16_t cwnd_min;

  /**
   * Number of times per congestion window to update based on congestion
   * signals */
  uint8_t cwnd_inc_rate;

  /**
   * Number of cwnd worth of sendme acks to smooth RTT and BDP with,
   * using N_EWMA */
  uint8_t ewma_cwnd_cnt;

  /**
   * Minimum number of sendmes before we begin BDP estimates
   */
  uint8_t bwe_sendme_min;

  /**
   * Number of cells to ack with every sendme. Taken from consensus parameter
   * and negotiation during circuit setup. */
  uint8_t sendme_inc;

  /** Which congestion control algorithm to use. Taken from
   * consensus parameter and negotiation during circuit setup. */
  cc_alg_t cc_alg;

  /* Which algorithm to estimate circuit bandwidth with. Taken from
   * consensus parameter during circuit setup. */
  bdp_alg_t bdp_alg;

  /* Algorithm-specific parameters */
  union {
    struct westwood_params_t {
      uint8_t cwnd_backoff_m;
      uint8_t rtt_backoff_m;
      uint8_t rtt_thresh;
      bool min_backoff;
    } westwood_params;
    struct vegas_params_t {
      uint16_t gamma;
      uint16_t alpha;
      uint16_t beta;
      uint8_t bdp_mix_pct;
    } vegas_params;
    struct nola_params_t {
      uint16_t bdp_overshoot;
    } nola_params;
  };

} congestion_control_t;

#define CWND_UPDATE_RATE(cc)  \
       ((cc)->cwnd/((cc)->cwnd_inc_rate*(cc)->sendme_inc))
#define CWND_INC_SS(cc)        ((cc)->cwnd_inc_pct_ss*(cc)->cwnd/100)
#define CWND_INC(cc)           ((cc)->cwnd_inc)

#define congestion_control_free(cc) \
    do { \
      if ((cc)) \
        _congestion_control_free(cc); \
      (cc) = NULL; \
    } while (0)

void _congestion_control_free(congestion_control_t *cc);

void sendme_next_cc_alg(circuit_t *, crypt_path_t *);

congestion_control_t *congestion_control_new(void);

void sendme_record_time_for_rtt(circuit_t *circ, crypt_path_t *cpath);

void sendme_update_circuit_estimates(circuit_t *, congestion_control_t *,
                                     crypt_path_t *);

int sendme_get_package_window(circuit_t *circ, crypt_path_t *cpath);
int sendme_get_inc_count(circuit_t *circ, crypt_path_t *layer_hint);

bool circuit_sent_cell_for_sendme(circuit_t *, crypt_path_t *);

/* Private section starts. */
#ifdef SENDME_COMMON_PRIVATE

/*
 * Unit tests declaractions.
 */
#ifdef TOR_UNIT_TESTS

#endif /* defined(TOR_UNIT_TESTS) */

#endif /* defined(SENDME_COMMON_PRIVATE) */

#endif /* !defined(TOR_SENDME_COMMON_H) */
