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

/**
 * \file sendme_common.c
 * \brief Common code used by all sendme algorithms.
 */

#define SENDME_COMMON_PRIVATE

#include "core/or/or.h"

#include "core/or/circuitlist.h"
#include "core/or/crypt_path.h"
#include "core/or/or_circuit_st.h"
#include "core/or/origin_circuit_st.h"
#include "core/or/channel.h"
#include "core/mainloop/connection.h"
#include "core/or/sendme.h"
#include "core/or/sendme_common.h"
#include "lib/time/compat_time.h"
#include "feature/nodelist/networkstatus.h"

/* Consensus parameter defaults */
#define CIRCWINDOW_ICW (500)

#define CWND_INC_PCT_SS_DFLT (100)

#define SENDME_INC_DFLT  (50)
#define CWND_MIN_DFLT    (MAX(100, SENDME_INC_DFLT))

#define CWND_INC_DFLT (50)

#define CWND_INC_RATE_DFLT (1)

#define WESTWOOD_BDP_ALG BDP_ALG_PIECEWISE_EWMA
#define VEGAS_BDP_MIX_ALG BDP_ALG_PIECEWISE_EWMA
#define NOLA_BDP_ALG BDP_ALG_PIECEWISE_EWMA

#define WESTWOOD_CWND_BACKOFF_M 75
#define WESTWOOD_RTT_BACKOFF_M 100
#define WESTWOOD_RTT_THRESH 33
#define WESTWOOD_MIN_BACKOFF 0

#define VEGAS_GAMMA(cc)   (6*(cc)->sendme_inc)
#define VEGAS_ALPHA(cc)   (3*(cc)->sendme_inc)
#define VEGAS_BETA(cc)    (6*(cc)->sendme_inc)

#define VEGAS_BDP_MIX_PCT       0

#define NOLA_BDP_OVERSHOOT    100

#define EWMA_CWND_COUNT_DFLT  2
#define BWE_SENDME_MIN_DFLT   4

/**
 * Get the number of sendme acks in the congestion window,
 * rounded to nearest int */
#define SENDME_PER_CWND(cc) \
       (((cc)->cwnd + (cc)->sendme_inc/2)/(cc)->sendme_inc)

/** Compute N-value previous EWMA: EWMA with alpha = 2/(N+1) */
#define N_EWMA(val, prev, N) \
     ((prev) ? \
        (((val)*2)/((N)+1) + ((prev)*((N)-1))/((N)+1)) : \
        (val))

static void sendme_update_circuit_rtt(congestion_control_t *, uint64_t);
static void sendme_update_circuit_bdp(circuit_t *, congestion_control_t *,
                                      crypt_path_t *, uint64_t);

/**
 * Set congestion control parameters on a circuit's congestion
 * control object based on values from the consensus.
 */
static void
congestion_control_init_params(congestion_control_t *cc,
                               cc_alg_t cc_alg,
                               int sendme_inc)
{
#define CWND_ICW_MIN 100
#define CWND_ICW_MAX (10000)
  cc->cwnd =
    networkstatus_get_param(NULL, "circwindow_cc",
        CIRCWINDOW_ICW,
        CWND_ICW_MIN,
        CWND_ICW_MAX);

#define CWND_INC_PCT_SS_MIN 1
#define CWND_INC_PCT_SS_MAX (500)
  cc->cwnd_inc_pct_ss =
    networkstatus_get_param(NULL, "cc_cwnd_inc_pct_ss",
        CWND_INC_PCT_SS_DFLT,
        CWND_INC_PCT_SS_MIN,
        CWND_INC_PCT_SS_MAX);

#define CWND_INC_MIN 1
#define CWND_INC_MAX (1000)
  cc->cwnd_inc =
    networkstatus_get_param(NULL, "cc_cwnd_inc",
        CWND_INC_DFLT,
        CWND_INC_MIN,
        CWND_INC_MAX);

#define CWND_INC_RATE_MIN 1
#define CWND_INC_RATE_MAX (100)
  cc->cwnd_inc_rate =
    networkstatus_get_param(NULL, "cc_cwnd_inc_rate",
        CWND_INC_RATE_DFLT,
        CWND_INC_RATE_MIN,
        CWND_INC_RATE_MAX);

#define SENDME_INC_MIN 10
#define SENDME_INC_MAX (1000)
  cc->sendme_inc =
    networkstatus_get_param(NULL, "cc_sendme_inc",
        sendme_inc,
        SENDME_INC_MIN,
        SENDME_INC_MAX);

  // XXX: this min needs to abide by sendme_inc range rules somehow
#define CWND_MIN_MIN sendme_inc
#define CWND_MIN_MAX (1000)
  cc->cwnd_min =
    networkstatus_get_param(NULL, "cc_cwnd_min",
        CWND_MIN_DFLT,
        CWND_MIN_MIN,
        CWND_MIN_MAX);

#define EWMA_CWND_COUNT_MIN 1
#define EWMA_CWND_COUNT_MAX (100)
  cc->ewma_cwnd_cnt =
    networkstatus_get_param(NULL, "cc_ewma_cwnd_cnt",
        EWMA_CWND_COUNT_DFLT,
        EWMA_CWND_COUNT_MIN,
        EWMA_CWND_COUNT_MAX);

#define BWE_SENDME_MIN_MIN 1
#define BWE_SENDME_MIN_MAX (20)
  cc->bwe_sendme_min =
    networkstatus_get_param(NULL, "cc_bwe_min",
        BWE_SENDME_MIN_DFLT,
        BWE_SENDME_MIN_MIN,
        BWE_SENDME_MIN_MAX);

#define CC_ALG_MIN 0
#define CC_ALG_MAX (SENDME_ALG_MAX-1)
  cc->cc_alg =
    networkstatus_get_param(NULL, "cc_alg",
        cc_alg,
        CC_ALG_MIN,
        CC_ALG_MAX);

  bdp_alg_t default_bdp_alg = 0;

  switch (cc->cc_alg) {
    case SENDME_ALG_WESTWOOD:
      default_bdp_alg = WESTWOOD_BDP_ALG;
      break;
    case SENDME_ALG_VEGAS:
      default_bdp_alg = VEGAS_BDP_MIX_ALG;
      break;
    case SENDME_ALG_NOLA:
      default_bdp_alg = NOLA_BDP_ALG;
      break;
    case SENDME_ALG_MAX:
    case SENDME_ALG_FIXED:
    default:
      return; // No alg-specific params
  }

  cc->bdp_alg =
    networkstatus_get_param(NULL, "cc_bdp_alg",
        default_bdp_alg,
        0,
        BDP_ALG_MAX);

  /* Algorithm-specific parameters */
  if (cc->cc_alg == SENDME_ALG_WESTWOOD) {
    cc->westwood_params.cwnd_backoff_m =
     networkstatus_get_param(NULL, "cc_westwood_cwnd_m",
        WESTWOOD_CWND_BACKOFF_M,
        0,
        100);

    cc->westwood_params.rtt_backoff_m =
     networkstatus_get_param(NULL, "cc_westwood_rtt_m",
        WESTWOOD_RTT_BACKOFF_M,
        0,
        100);

    cc->westwood_params.rtt_thresh =
     networkstatus_get_param(NULL, "cc_westwood_rtt_thresh",
        WESTWOOD_RTT_THRESH,
        0,
        100);

    cc->westwood_params.min_backoff =
     networkstatus_get_param(NULL, "cc_westwood_min_backoff",
        WESTWOOD_MIN_BACKOFF,
        0,
        1);
  } else if (cc->cc_alg == SENDME_ALG_VEGAS) {
    cc->vegas_params.gamma =
     networkstatus_get_param(NULL, "cc_vegas_gamma",
        VEGAS_GAMMA(cc),
        0,
        1000);

    cc->vegas_params.alpha =
     networkstatus_get_param(NULL, "cc_vegas_alpha",
        VEGAS_ALPHA(cc),
        0,
        1000);

    cc->vegas_params.beta =
     networkstatus_get_param(NULL, "cc_vegas_beta",
        VEGAS_BETA(cc),
        0,
        1000);

    cc->vegas_params.bdp_mix_pct =
     networkstatus_get_param(NULL, "cc_vegas_bdp_mix",
        VEGAS_BDP_MIX_PCT,
        0,
        100);
  } else if (cc->cc_alg == SENDME_ALG_NOLA) {
    cc->nola_params.bdp_overshoot =
     networkstatus_get_param(NULL, "cc_nola_overshoot",
        NOLA_BDP_OVERSHOOT,
        0,
        1000);
  }
}

/**
 * Allocate and initialize fields in congestion control object.
 */
static void
congestion_control_init(congestion_control_t *cc, cc_alg_t cc_alg,
                        int sendme_inc)
{
  cc->sendme_pending_timestamps = smartlist_new();
  cc->sendme_arrival_timestamps = smartlist_new();

  cc->in_slow_start = 1;
  congestion_control_init_params(cc, cc_alg, sendme_inc);

  cc->next_cc_event = CWND_UPDATE_RATE(cc);
}

congestion_control_t *
congestion_control_new(void)
{
  congestion_control_t *cc = tor_malloc_zero(sizeof(congestion_control_t));

  // XXX: the alg and the sendme_inc need to be negotiated during
  // circuit handshake
  congestion_control_init(cc, SENDME_ALG_FIXED, SENDME_INC_DFLT);

  return cc;
}

/**
 * Free a congestion control object and its asssociated state.
 */
void
_congestion_control_free(congestion_control_t *cc)
{
  SMARTLIST_FOREACH(cc->sendme_pending_timestamps, uint64_t *, t, tor_free(t));
  SMARTLIST_FOREACH(cc->sendme_arrival_timestamps, uint64_t *, t, tor_free(t));
  smartlist_free(cc->sendme_pending_timestamps);
  smartlist_free(cc->sendme_arrival_timestamps);

  tor_free(cc);
}

/**
 * This is a hack to test different algs on the same circuit,
 * for perf comparison. It gets called when we send or recieve
 * a BEGIN, so we can test multiple CC algs on the same circuit,
 * one after another. */
void
sendme_next_cc_alg(circuit_t *circ, crypt_path_t *layer_hint)
{
  congestion_control_t *cc;

  if (layer_hint) {
    cc = layer_hint->ccontrol;
    layer_hint->deliver_window = CIRCWINDOW_START;
  } else {
    cc = circ->ccontrol;
    circ->deliver_window = CIRCWINDOW_START;
  }

  cc_alg_t cc_alg = (cc->cc_alg+1)%SENDME_ALG_MAX;
  SMARTLIST_FOREACH(cc->sendme_pending_timestamps, uint64_t *, t, tor_free(t));
  SMARTLIST_FOREACH(cc->sendme_arrival_timestamps, uint64_t *, t, tor_free(t));
  smartlist_free(cc->sendme_pending_timestamps);
  smartlist_free(cc->sendme_arrival_timestamps);

  memset(cc, 0, sizeof(*cc));

  congestion_control_init(cc, cc_alg, SENDME_INC_DFLT);

  if (circ->sendme_last_digests) {
    SMARTLIST_FOREACH(circ->sendme_last_digests, uint64_t *, t, tor_free(t));
    smartlist_free(circ->sendme_last_digests);
  }
  circ->sendme_last_digests = NULL;

  log_notice(LD_CIRC, "Switching to CC alg %d", cc->cc_alg);
}

/**
 * Get a package window from either old sendme logic, or congestion control.
 *
 * A package window is how many cells you can still send.
 */
int
sendme_get_package_window(circuit_t *circ, crypt_path_t *cpath)
{
  int package_window;
  congestion_control_t *cc;

  tor_assert(circ);

  if (cpath) {
    package_window = cpath->package_window;
    cc = cpath->ccontrol;
  } else {
    package_window = circ->package_window;
    cc = circ->ccontrol;
  }

  if (!cc || cc->cc_alg == SENDME_ALG_FIXED) {
    return package_window;
  } else {
    /* Inflight can be above cwnd if cwnd was just reduced */
    if (cc->inflight > cc->cwnd)
      return 0;
    return (int)(cc->cwnd - cc->inflight); // XXX: bounds
  }
}

/**
 * Get the sendme ack count for the current circuit.
 */
int
sendme_get_inc_count(circuit_t *circ, crypt_path_t *layer_hint)
{
  int sendme_inc = CIRCWINDOW_INCREMENT;
  congestion_control_t *cc = NULL;

  if (layer_hint) {
    cc = layer_hint->ccontrol;
  } else {
    cc = circ->ccontrol;
  }

  if (cc && cc->cc_alg != SENDME_ALG_FIXED) {
    sendme_inc = cc->sendme_inc;
  }

  return sendme_inc;
}

/** Return true iff the next cell we send will result in the other endpoint
 * sending a SENDME.
 *
 * We are able to know that because the package or inflight window value minus
 * one cell (the possible SENDME cell) should be a multiple of the increment
 * window value. */
bool
circuit_sent_cell_for_sendme(circuit_t *circ, crypt_path_t *layer_hint)
{
  congestion_control_t *cc;
  int window;

  tor_assert(circ);

  if (layer_hint) {
    window = layer_hint->package_window;
    cc = layer_hint->ccontrol;
  } else {
    window = circ->package_window;
    cc = circ->ccontrol;
  }

  /* If we are using congestion control and the alg is not
   * old-school 'fixed', then use cc->inflight to determine
   * when sendmes will be sent */
  if (cc && cc->cc_alg != SENDME_ALG_FIXED) {
    if (!cc->inflight)
      return false;

    if ((cc->inflight+1) % cc->sendme_inc != 0)
      return false;

    return true;
  }

  /* At the start of the window, no SENDME will be expected. */
  if (window == CIRCWINDOW_START) {
    return false;
  }

  /* Are we at the limit of the increment and if not, we don't expect next
   * cell is a SENDME.
   *
   * We test against the window minus 1 because when we are looking if the
   * next cell is a SENDME, the window (either package or deliver) hasn't been
   * decremented just yet so when this is called, we are currently processing
   * the "window - 1" cell.
   *
   * This function is used when recording a cell digest and this is done quite
   * low in the stack when decrypting or encrypting a cell. The window is only
   * updated once the cell is actually put in the outbuf. */
  if (((window - 1) % CIRCWINDOW_INCREMENT) != 0) {
    return false;
  }

  /* Next cell is expected to be a SENDME. */
  return true;
}

/**
 * Record the current time in a list of pending timestamps, so that
 * we can later compute the circuit RTT when the SENDME comes back */
void
sendme_record_time_for_rtt(circuit_t *circ, crypt_path_t *cpath)
{
  uint64_t *timestamp;
  congestion_control_t *cc;

  tor_assert(circ);

  if (cpath) {
    cc = cpath->ccontrol;
  } else {
    cc = circ->ccontrol;
  }
  tor_assert(cc);

  /* Is this the last cell before a SENDME? The idea is that if the
   * package_window reaches a multiple of the increment, after this cell, we
   * should expect a SENDME. */
  if (!circuit_sent_cell_for_sendme(circ, cpath)) {
    return;
  }

  timestamp = tor_malloc(sizeof(uint64_t));
  *timestamp = monotime_absolute_usec();

  smartlist_add(cc->sendme_pending_timestamps, timestamp);
}

/**
 * Returns true if any edge connections have pending data.
 *
 * We need to know this so that we can stop computing BDP if the
 * edges are not sending on the circuit.
 */
static int
sendme_circ_has_pending_streams(circuit_t *circ, crypt_path_t *layer_hint)
{
  edge_connection_t *streams;

  if (CIRCUIT_IS_ORIGIN(circ)) {
    streams = TO_ORIGIN_CIRCUIT(circ)->p_streams;
  } else {
    streams = TO_OR_CIRCUIT(circ)->n_streams;
  }

  /* Check linked list of streams */
  for (edge_connection_t *conn = streams; conn != NULL;
       conn = conn->next_stream) {
    if (conn->base_.marked_for_close)
      continue;

    if (!layer_hint || conn->cpath_layer == layer_hint) {
      if (connection_get_inbuf_len(TO_CONN(conn)) > 0) {
        //log_notice(LD_CIRC, "More in edge inbuf...");
        return 1;
      }

      /* If we did not reach EOF on this read, there's more */
      if (!TO_CONN(conn)->inbuf_reached_eof) {
        //log_notice(LD_CIRC, "More on edge conn...");
        return 1;
      }

      if (TO_CONN(conn)->linked_conn) {
        if (connection_get_inbuf_len(TO_CONN(conn)->linked_conn) > 0) {
          //log_notice(LD_CIRC, "More in linked inbuf...");
          return 1;
        }

        /* If there is a linked conn, and *it* did not each EOF,
         * there's more */
        if (!TO_CONN(conn)->linked_conn->inbuf_reached_eof) {
          //log_notice(LD_CIRC, "More on linked conn...");
          return 1;
        }
      }
    }
  }

  return 0;
}

/**
 * Upon receipt of a SENDME, pop the oldest timestamp off the timestamp
 * list, and use this to update RTT
 */
void
sendme_update_circuit_estimates(circuit_t *circ, congestion_control_t *cc,
                                crypt_path_t *layer_hint)
{
  uint64_t now_usec = monotime_absolute_usec();

  /* Update RTT first, then BDP. BDP needs fresh RTT */
  sendme_update_circuit_rtt(cc, now_usec);
  sendme_update_circuit_bdp(circ, cc, layer_hint, now_usec);
}

/**
 * Called when we get a SENDME. Updates circuit RTT by pulling off a
 * timestamp of when we sent the CIRCWINDOW_INCREMENT-th cell from
 * the queue of such timestamps, and comparing that to current time.
 *
 * Also updates min, max, and EWMA of RTT.
 */
static void
sendme_update_circuit_rtt(congestion_control_t *cc, uint64_t now_usec)
{
  uint64_t *timestamp, rtt;
  uint64_t ewma_cnt;

  tor_assert(cc);

  timestamp = smartlist_get(cc->sendme_pending_timestamps, 0);
  smartlist_del_keeporder(cc->sendme_pending_timestamps, 0);
  rtt = now_usec - *timestamp;
  tor_free(timestamp);

  cc->curr_rtt_usec = rtt;

  ewma_cnt = cc->ewma_cwnd_cnt*SENDME_PER_CWND(cc);
  ewma_cnt = MAX(ewma_cnt, 2); // Use at least 2

  cc->ewma_rtt_usec = N_EWMA(rtt, cc->ewma_rtt_usec, ewma_cnt);

  if (rtt > cc->max_rtt_usec) {
    cc->max_rtt_usec = rtt;
  }

  if (cc->min_rtt_usec == 0 || rtt < cc->min_rtt_usec) {
    cc->min_rtt_usec = rtt;
  }
}

/**
 * Called when we get a SENDME. Updates the bandwidth-delay-product (BDP)
 * estimates of a circuit. Several methods of computing BDP are used,
 * depending on scenario. While some congestion control algorithms only
 * use one of these methods, we update them all because it's quick and easy.
 */
static void
sendme_update_circuit_bdp(circuit_t *circ, congestion_control_t *cc,
                          crypt_path_t *layer_hint, uint64_t now_usec)
{
  int chan_q = 0;
  unsigned int blocked_on_chan = 0;
  uint64_t *timestamp = NULL;

  tor_assert(cc);

  if (CIRCUIT_IS_ORIGIN(circ)) {
    /* origin circs use n_chan */
    chan_q = circ->n_chan_cells.n;
    blocked_on_chan = circ->streams_blocked_on_n_chan;
  } else {
    /* Both onion services and exits use or_circuit and p_chan */
    chan_q = TO_OR_CIRCUIT(circ)->p_chan_cells.n;
    blocked_on_chan = circ->streams_blocked_on_p_chan;
  }

  /* Congestion window based BDP will respond to changes in RTT only, and is
   * relative to cwnd growth. So in slow-start, this will underestimate BDP. */
  cc->bdp[BDP_ALG_CWND_RTT] = cc->cwnd*cc->min_rtt_usec/cc->curr_rtt_usec;
  cc->bdp[BDP_ALG_CWND_RTT_EWMA] = cc->cwnd*cc->min_rtt_usec/cc->ewma_rtt_usec;

  /*
   * If we have no pending streams, we do not have enough data to fill
   * the BDP, so preserve our old estimates but do not make any more.
   */
  if (!blocked_on_chan && !sendme_circ_has_pending_streams(circ, layer_hint)) {
    log_notice(LD_CIRC,
               "Streams drained. Spare package window: %"PRIu64
               ", no BDP update", cc->cwnd - cc->inflight);

    /* Clear SENDME timestamps; they will be wrong with intermittent data */
    SMARTLIST_FOREACH(cc->sendme_arrival_timestamps, uint64_t *, t,
                      tor_free(t));
    smartlist_clear(cc->sendme_arrival_timestamps);
  } else {
    /* Sendme-based BDP will quickly measure BDP in much less than
     * a cwnd worth of data when in use (in 2-10 SENDMEs).
     *
     * But if the link goes idle, it will be vastly lower than true BDP. Hence
     * we only compute it if we have either pending stream data, or streams
     * are still blocked on the channel queued data.
     */
    timestamp = tor_malloc(sizeof(uint64_t));
    *timestamp = now_usec;
    smartlist_add(cc->sendme_arrival_timestamps, timestamp);

    if (smartlist_len(cc->sendme_arrival_timestamps) >= cc->bwe_sendme_min) {
      /* If we have more sendmes than fit in a cwnd, trim the list.
       * Those are not acurrately measuring throughput, if cwnd is
       * currently smaller than BDP */
      while (smartlist_len(cc->sendme_arrival_timestamps) >
             cc->bwe_sendme_min &&
             (uint64_t)smartlist_len(cc->sendme_arrival_timestamps) >
                       SENDME_PER_CWND(cc)) {
        timestamp = smartlist_get(cc->sendme_arrival_timestamps, 0);
        smartlist_del_keeporder(cc->sendme_arrival_timestamps, 0);

        tor_free(timestamp);
      }
      int sendme_cnt = smartlist_len(cc->sendme_arrival_timestamps);

      /* Calculate SENDME_BWE_COUNT pure average */
      timestamp = smartlist_get(cc->sendme_arrival_timestamps, 0);
      uint64_t delta = now_usec - *timestamp;
      uint64_t cells = (sendme_cnt-1)*cc->sendme_inc*cc->min_rtt_usec;
      cc->bdp[BDP_ALG_SENDME_RATE] = cells/delta;

      /* Calculate BDP_EWMA_COUNT N-EWMA */
      cc->bdp[BDP_ALG_SENDME_RATE_EWMA] =
                 N_EWMA(cells/delta, cc->bdp[BDP_ALG_SENDME_RATE_EWMA],
                        cc->ewma_cwnd_cnt*SENDME_PER_CWND(cc));
    }

    /* In-flight BDP will cause the cwnd to drift down when underutilized.
     * Also only compute it if we're utilized */
    // XXX: On exits and onion services, this may be a channel queue with many
    // circuits. We should divide chan_q by that number of circs (unless it is
    // already just this circuit's queue??)
    cc->bdp[BDP_ALG_INFLIGHT_RTT] =
        (cc->inflight - chan_q)*cc->min_rtt_usec/cc->curr_rtt_usec;
    cc->bdp[BDP_ALG_INFLIGHT_RTT_EWMA] =
        (cc->inflight - chan_q)*cc->min_rtt_usec/cc->ewma_rtt_usec;
  }

  /* The orconn is blocked; use smaller of inflight vs SENDME */
  if (blocked_on_chan) {
    log_notice(LD_CIRC, "Streams blocked. Chanq: %d", chan_q);

    /* A blocked channel is an immediate congestion signal, but it still
     * happens only once per cwnd */
    if (!cc->blocked_chan) {
      cc->next_cc_event = 0;
      cc->blocked_chan = 1;
    }

    if (cc->bdp[BDP_ALG_SENDME_RATE]) {
      cc->bdp[BDP_ALG_PIECEWISE] = MIN(
                                       MIN(cc->bdp[BDP_ALG_INFLIGHT_RTT],
                                           cc->bdp[BDP_ALG_SENDME_RATE]),
                                       MIN(cc->bdp[BDP_ALG_INFLIGHT_RTT_EWMA],
                                           cc->bdp[BDP_ALG_SENDME_RATE_EWMA]));
    } else {
      cc->bdp[BDP_ALG_PIECEWISE] = MIN(cc->bdp[BDP_ALG_INFLIGHT_RTT],
                                       cc->bdp[BDP_ALG_INFLIGHT_RTT_EWMA]);
    }

    /* Drop the EWMA to ensure we immediately backoff this event */
    cc->bdp[BDP_ALG_PIECEWISE_EWMA] = cc->bdp[BDP_ALG_PIECEWISE];
  } else {

    /* If we were previously blocked, emit a new congestion event
     * now that we are unblocked, to re-evaluate cwnd */
    if (cc->blocked_chan) {
      cc->blocked_chan = 0;
      cc->next_cc_event = 0;
      log_notice(LD_CIRC, "Streams un-blocked. Chanq: %d", chan_q);
    }

    cc->bdp[BDP_ALG_PIECEWISE] = MAX(
                                     MAX(cc->bdp[BDP_ALG_SENDME_RATE],
                                         cc->bdp[BDP_ALG_CWND_RTT]),
                                     MAX(cc->bdp[BDP_ALG_SENDME_RATE_EWMA],
                                         cc->bdp[BDP_ALG_CWND_RTT_EWMA]));

    cc->bdp[BDP_ALG_PIECEWISE_EWMA] =
        N_EWMA(cc->bdp[BDP_ALG_PIECEWISE],
             cc->bdp[BDP_ALG_PIECEWISE_EWMA],
             cc->ewma_cwnd_cnt*SENDME_PER_CWND(cc));
  }

  /* We can end up with no piecewise value if we didn't have either
   * a SENDME estimate or enough data for an inflight estimate.
   * It also happens on the very first sendme, since we need two
   * to get a BDP. In these cases, use the cwnd method. */
  if (!cc->bdp[BDP_ALG_PIECEWISE]) {
    cc->bdp[BDP_ALG_PIECEWISE] = cc->bdp[BDP_ALG_CWND_RTT];
    cc->bdp[BDP_ALG_PIECEWISE_EWMA] = cc->bdp[BDP_ALG_CWND_RTT_EWMA];
    log_notice(LD_CIRC, "No piecewise BDP. Using %"PRIu64". Have %"PRIu64,
               cc->bdp[BDP_ALG_PIECEWISE], cc->bdp[BDP_ALG_INFLIGHT_RTT]);
  }

  if (cc->next_cc_event == 0) {
    if (CIRCUIT_IS_ORIGIN(circ)) {
      log_notice(LD_CIRC,
                 "Circuit %d "
                 "SENDME RTT: %"PRIu64", %"PRIu64", %"PRIu64", %"PRIu64", "
                 "BDP estimates: "
                 "%"PRIu64", "
                 "%"PRIu64", "
                 "%"PRIu64", "
                 "%"PRIu64", "
                 "%"PRIu64", "
                 "%"PRIu64". ",
               TO_ORIGIN_CIRCUIT(circ)->global_identifier,
               cc->min_rtt_usec/1000,
               cc->curr_rtt_usec/1000,
               cc->ewma_rtt_usec/1000,
               cc->max_rtt_usec/1000,
               cc->bdp[BDP_ALG_INFLIGHT_RTT],
               cc->bdp[BDP_ALG_INFLIGHT_RTT_EWMA],
               cc->bdp[BDP_ALG_SENDME_RATE],
               cc->bdp[BDP_ALG_SENDME_RATE_EWMA],
               cc->bdp[BDP_ALG_PIECEWISE],
               cc->bdp[BDP_ALG_PIECEWISE_EWMA]
               );
    } else {
      log_notice(LD_CIRC,
                 "Circuit %"PRIu64":%d "
                 "SENDME RTT: %"PRIu64", %"PRIu64", %"PRIu64", %"PRIu64", "
                 "%"PRIu64", "
                 "%"PRIu64", "
                 "%"PRIu64", "
                 "%"PRIu64", "
                 "%"PRIu64", "
                 "%"PRIu64". ",
                 // XXX: actually, is this p_chan here? This is
                 // an or_circuit (exit or onion)
                 circ->n_chan->global_identifier, circ->n_circ_id,
                 cc->min_rtt_usec/1000,
                 cc->curr_rtt_usec/1000,
                 cc->ewma_rtt_usec/1000,
                 cc->max_rtt_usec/1000,
                 cc->bdp[BDP_ALG_INFLIGHT_RTT],
                 cc->bdp[BDP_ALG_INFLIGHT_RTT_EWMA],
                 cc->bdp[BDP_ALG_SENDME_RATE],
                 cc->bdp[BDP_ALG_SENDME_RATE_EWMA],
                 cc->bdp[BDP_ALG_PIECEWISE],
                 cc->bdp[BDP_ALG_PIECEWISE_EWMA]
                 );
    }
  }
}
