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

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

#define SENDME_VEGAS_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_vegas.h"
#include "core/or/circuitlist.h"
#include "core/or/circuituse.h"
#include "core/or/origin_circuit_st.h"
#include "core/or/channel.h"

#define VEGAS_BDP_MIX_PCT(cc)  ((cc)->vegas_params.bdp_mix_pct)

#define VEGAS_BDP_MIX(cc)      \
        (VEGAS_BDP_MIX_PCT(cc)*(cc)->bdp[BDP_ALG_CWND_RTT_EWMA]/100 + \
         (100-VEGAS_BDP_MIX_PCT(cc))*(cc)->bdp[(cc)->bdp_alg]/100)

/**
 * Process a SENDME and update the congestion window according to the
 * rules specified in TOR_VEGAS of Proposal #324.
 *
 * Essentially, this algorithm attempts to measure queue lengths on
 * the circuit by subtracting the bandwidth-delay-product estimate
 * from the current congestion window.
 *
 * If the congestion window is larger than the bandwidth-delay-product,
 * then data is assumed to be queuing. We reduce the congestion window
 * in that case.
 *
 * If the congestion window is smaller than the bandwidth-delay-product,
 * then there is spare bandwidth capacity on the circuit. We increase the
 * congestion window in that case.
 *
 * 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_vegas_process_circuit_level(crypt_path_t *layer_hint,
                                   circuit_t *circ)
{
  congestion_control_t *cc;
  uint64_t queue_use;

  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) {
    /* The queue use is the amount in which our cwnd is above BDP;
     * if it is below, then 0 queue use. */
    if (VEGAS_BDP_MIX(cc) > cc->cwnd)
      queue_use = 0;
    else
      queue_use = cc->cwnd - VEGAS_BDP_MIX(cc);

    if (cc->in_slow_start) {
      if (queue_use < cc->vegas_params.gamma && !cc->blocked_chan) {
        /* Grow to BDP immediately, then exponential growth until
         * congestion signal */
        cc->cwnd = MAX(cc->cwnd + CWND_INC_SS(cc),
                       VEGAS_BDP_MIX(cc));
      } else {
        /* Congestion signal: Fall back to Vegas equilibrium (BDP) */
        cc->cwnd = VEGAS_BDP_MIX(cc);
        cc->in_slow_start = 0;
        log_notice(LD_CIRC, "Vegas exiting slow start");
      }
    } else {
      if (queue_use > cc->vegas_params.beta || cc->blocked_chan) {
        cc->cwnd -= CWND_INC(cc);
      } else if (queue_use < cc->vegas_params.alpha) {
        cc->cwnd += CWND_INC(cc);
      }
    }

    /* 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", "
                 "VBDP: %"PRIu64", "
                 "QUSE: %"PRIu64", "
                 "NCCE: %"PRIu64", "
                 "SS: %d",
               TO_ORIGIN_CIRCUIT(circ)->global_identifier,
               cc->cwnd,
               cc->inflight,
               VEGAS_BDP_MIX(cc),
               queue_use,
               cc->next_cc_event,
               cc->in_slow_start
               );
    } else {
      log_notice(LD_CIRC,
                 "Circuit %"PRIu64":%d "
                 "CWND: %"PRIu64", "
                 "INFL: %"PRIu64", "
                 "VBDP: %"PRIu64", "
                 "QUSE: %"PRIu64", "
                 "NCCE: %"PRIu64", "
                 "SS: %d",
                 circ->n_chan->global_identifier, circ->n_circ_id,
               cc->cwnd,
               cc->inflight,
               VEGAS_BDP_MIX(cc),
               queue_use,
               cc->next_cc_event,
               cc->in_slow_start
               );
    }
  }

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

  return 0;
}
