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

/**
 * \file sendme_westwood.c
 * \brief Code that implements the TOR_WESTWOOD congestion control algorithm
 *        from Proposal #324.
 */

#define SENDME_WESTWOOD_PRIVATE

#include "core/or/or.h"

#include "core/or/crypt_path.h"
#include "core/or/or_circuit_st.h"
#include "core/or/sendme.h"
#include "core/or/sendme_westwood.h"
#include "core/or/circuitlist.h"
#include "core/or/circuituse.h"
#include "core/or/origin_circuit_st.h"
#include "core/or/channel.h"

#define WESTWOOD_RTT_SIGNAL(cc) \
       (((100-(cc)->westwood_params.rtt_thresh)*(cc)->min_rtt_usec + \
        (cc)->westwood_params.rtt_thresh*(cc)->max_rtt_usec)/100)

#define WESTWOOD_MAX_RTT_BACKOFF(cc) \
    ((cc)->min_rtt_usec + \
     ((cc)->westwood_params.rtt_backoff_m * \
      ((cc)->max_rtt_usec - (cc)->min_rtt_usec))/100)

#define USEC_ONE_MS (1000)

/**
 * Returns true if the circuit is experiencing congestion, as per
 * TOR_WESTWOOD rules.
 */
static inline bool
westwood_is_congested(congestion_control_t *cc)
{
  /* If the local channel is blocked, that is always congestion */
  if (cc->blocked_chan)
    return true;

  /* If the min RTT is within 1ms of the signal, then there is not enough
   * range in RTTs to signify congestion. Treat that as not congested. */
  if (WESTWOOD_RTT_SIGNAL(cc) < cc->min_rtt_usec ||
      WESTWOOD_RTT_SIGNAL(cc) - cc->min_rtt_usec < USEC_ONE_MS)
    return false;

  /* If the EWMA-smoothed RTT exceeds the westwood RTT threshhold,
   * then it is congestion. */
  if (cc->ewma_rtt_usec > WESTWOOD_RTT_SIGNAL(cc))
    return true;

  return false;
}

/**
 * Process a SENDME and update the congestion window according to the
 * rules specified in TOR_WESTWOOD of Proposal #324.
 *
 * Essentially, this algorithm uses a threshhold of 'rtt_thresh', which
 * is a midpoint between the min and max RTT. If the RTT exceeds this
 * threshhold, then queue delay due to congestion is assumed to be present,
 * and the algirithm reduces the congestion window. If the RTT is below the
 * threshhold, the circuit is not congested (ie: queue delay is low), and we
 * increase the congestion window.
 *
 * The congestion window is updated only once every congestion window worth of
 * packets, even if the signal persists. It is also updated whenever the
 * upstream orcon blocks, or unblocks. This minimizes local client queues.
 */
int
sendme_westwood_process_circuit_level(crypt_path_t *layer_hint,
                                      circuit_t *circ)
{
  congestion_control_t *cc;

  tor_assert(circ);

  // Get CC object
  if (layer_hint) {
    tor_assert(CIRCUIT_IS_ORIGIN(circ));
    cc = layer_hint->ccontrol;
  } else {
    tor_assert(!CIRCUIT_IS_ORIGIN(circ));
    cc = circ->ccontrol;
  }

  /* Update ack counter until next congestion signal event is allowed */
  if (cc->next_cc_event)
    cc->next_cc_event--;

  /* Compute BDP and RTT */
  sendme_update_circuit_estimates(circ, cc, layer_hint);

  /* We only update anything once per window */
  if (cc->next_cc_event == 0) {
    if (!westwood_is_congested(cc)) {
      if (cc->in_slow_start) {
        cc->cwnd = MAX(cc->cwnd + CWND_INC_SS(cc),
                       cc->bdp[cc->bdp_alg]);
      } else {
        cc->cwnd = cc->cwnd + CWND_INC(cc);
      }
    } else {
      if (cc->westwood_params.min_backoff)
        cc->cwnd = MIN(cc->cwnd*cc->westwood_params.cwnd_backoff_m/100,
                       cc->bdp[cc->bdp_alg]);
      else
        cc->cwnd = MAX(cc->cwnd*cc->westwood_params.cwnd_backoff_m/100,
                       cc->bdp[cc->bdp_alg]);

      cc->in_slow_start = 0;

      // Because Westwood's congestion can runaway and boost max rtt,
      // which increases its congestion signal, we backoff the max rtt
      // too.
      cc->max_rtt_usec = WESTWOOD_MAX_RTT_BACKOFF(cc);

      log_notice(LD_CIRC, "Westwood congestion. New max RTT: %"PRIu64,
                 cc->max_rtt_usec/1000);
    }

    /* cwnd can never fall below 1 increment */
    cc->cwnd = MAX(cc->cwnd, cc->cwnd_min);

    /* Schedule next update */
    cc->next_cc_event = CWND_UPDATE_RATE(cc);

    if (CIRCUIT_IS_ORIGIN(circ)) {
      log_notice(LD_CIRC,
                 "Circuit %d "
                 "CWND: %"PRIu64", "
                 "INFL: %"PRIu64", "
                 "NCCE: %"PRIu64", "
                 "WRTT: %"PRIu64", "
                 "WSIG: %"PRIu64", "
                 "SS: %d",
               TO_ORIGIN_CIRCUIT(circ)->global_identifier,
               cc->cwnd,
               cc->inflight,
               cc->next_cc_event,
               cc->ewma_rtt_usec/1000,
               WESTWOOD_RTT_SIGNAL(cc)/1000,
               cc->in_slow_start
               );
    } else {
      log_notice(LD_CIRC,
                 "Circuit %"PRIu64":%d "
                 "CWND: %"PRIu64", "
                 "INFL: %"PRIu64", "
                 "NCCE: %"PRIu64", "
                 "WRTT: %"PRIu64", "
                 "WSIG: %"PRIu64", "
                 "SS: %d",
               circ->n_chan->global_identifier, circ->n_circ_id,
               cc->cwnd,
               cc->inflight,
               cc->next_cc_event,
               cc->ewma_rtt_usec/1000,
               WESTWOOD_RTT_SIGNAL(cc)/1000,
               cc->in_slow_start
               );
    }
  }

  /* Update inflight with ack */
  cc->inflight = cc->inflight - cc->sendme_inc;

  return 0;
}
