tor/src/or/circuitmux.c

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

/**
 * \file circuitmux.c
 * \brief Circuit mux/cell selection abstraction
 *
 * A circuitmux is responsible for <b>MU</b>ltiple<b>X</b>ing all of the
 * circuits that are writing on a single channel. It keeps track of which of
 * these circuits has something to write (aka, "active" circuits), and which
 * one should write next.  A circuitmux corresponds 1:1 with a channel.
 *
 * There can be different implementations of the circuitmux's rules (which
 * decide which circuit is next to write).
 *
 * A circuitmux exposes three distinct
 * interfaces to other components:
 *
 * To channels, which each have a circuitmux_t, the supported operations
 * (invoked from relay.c) are:
 *
 *   circuitmux_get_first_active_circuit():
 *
 *     Pick one of the circuitmux's active circuits to send cells from.
 *
 *   circuitmux_notify_xmit_cells():
 *
 *     Notify the circuitmux that cells have been sent on a circuit.
 *
 * To circuits, the exposed operations are:
 *
 *   circuitmux_attach_circuit():
 *
 *     Attach a circuit to the circuitmux; this will allocate any policy-
 *     specific data wanted for this circuit and add it to the active
 *     circuits list if it has queued cells.
 *
 *   circuitmux_detach_circuit():
 *
 *     Detach a circuit from the circuitmux, freeing associated structures.
 *
 *   circuitmux_clear_num_cells():
 *
 *     Clear the circuitmux's cell counter for this circuit.
 *
 *   circuitmux_set_num_cells():
 *
 *     Set the circuitmux's cell counter for this circuit. One of
 *     circuitmuc_clear_num_cells() or circuitmux_set_num_cells() MUST be
 *     called when the number of cells queued on a circuit changes.
 *
 * See circuitmux.h for the circuitmux_policy_t data structure, which contains
 * a table of function pointers implementing a circuit selection policy, and
 * circuitmux_ewma.c for an example of a circuitmux policy.  Circuitmux
 * policies can be manipulated with:
 *
 *   circuitmux_get_policy():
 *
 *     Return the current policy for a circuitmux_t, if any.
 *
 *   circuitmux_clear_policy():
 *
 *     Remove a policy installed on a circuitmux_t, freeing all associated
 *     data.  The circuitmux will revert to the built-in round-robin behavior.
 *
 *   circuitmux_set_policy():
 *
 *     Install a policy on a circuitmux_t; the appropriate callbacks will be
 *     made to attach all existing circuits to the new policy.
 **/

#include "or.h"
#include "channel.h"
#include "circuitlist.h"
#include "circuitmux.h"
#include "relay.h"

#include "or_circuit_st.h"

/*
 * Private typedefs for circuitmux.c
 */

/*
 * Map of muxinfos for circuitmux_t to use; struct is defined below (name
 * of struct must match HT_HEAD line).
 */
typedef struct chanid_circid_muxinfo_map chanid_circid_muxinfo_map_t;

/*
 * Hash table entry (yeah, calling it chanid_circid_muxinfo_s seems to
 * break the hash table code).
 */
typedef struct chanid_circid_muxinfo_t chanid_circid_muxinfo_t;

/*
 * Anything the mux wants to store per-circuit in the map; right now just
 * a count of queued cells.
 */

typedef struct circuit_muxinfo_s circuit_muxinfo_t;

/*
 * Structures for circuitmux.c
 */

struct circuitmux_s {
  /* Keep count of attached, active circuits */
  unsigned int n_circuits, n_active_circuits;

  /* Total number of queued cells on all circuits */
  unsigned int n_cells;

  /*
   * Map from (channel ID, circuit ID) pairs to circuit_muxinfo_t
   */
  chanid_circid_muxinfo_map_t *chanid_circid_map;

  /** List of queued destroy cells */
  destroy_cell_queue_t destroy_cell_queue;
  /** Boolean: True iff the last cell to circuitmux_get_first_active_circuit
   * returned the destroy queue. Used to force alternation between
   * destroy/non-destroy cells.
   *
   * XXXX There is no reason to think that alternating is a particularly good
   * approach -- it's just designed to prevent destroys from starving other
   * cells completely.
   */
  unsigned int last_cell_was_destroy : 1;
  /** Destroy counter: increment this when a destroy gets queued, decrement
   * when we unqueue it, so we can test to make sure they don't starve.
   */
  int64_t destroy_ctr;

  /*
   * Circuitmux policy; if this is non-NULL, it can override the built-
   * in round-robin active circuits behavior.  This is how EWMA works in
   * the new circuitmux_t world.
   */
  const circuitmux_policy_t *policy;

  /* Policy-specific data */
  circuitmux_policy_data_t *policy_data;
};

/*
 * This struct holds whatever we want to store per attached circuit on a
 * circuitmux_t; right now, just the count of queued cells and the direction.
 */

struct circuit_muxinfo_s {
  /* Count of cells on this circuit at last update */
  unsigned int cell_count;
  /* Direction of flow */
  cell_direction_t direction;
  /* Policy-specific data */
  circuitmux_policy_circ_data_t *policy_data;
  /* Mark bit for consistency checker */
  unsigned int mark:1;
};

/*
 * A map from channel ID and circuit ID to a circuit_muxinfo_t for that
 * circuit.
 */

struct chanid_circid_muxinfo_t {
  HT_ENTRY(chanid_circid_muxinfo_t) node;
  uint64_t chan_id;
  circid_t circ_id;
  circuit_muxinfo_t muxinfo;
};

/*
 * Static function declarations
 */

static inline int
chanid_circid_entries_eq(chanid_circid_muxinfo_t *a,
                         chanid_circid_muxinfo_t *b);
static inline unsigned int
chanid_circid_entry_hash(chanid_circid_muxinfo_t *a);
static chanid_circid_muxinfo_t *
circuitmux_find_map_entry(circuitmux_t *cmux, circuit_t *circ);
static void
circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ);
static void
circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ);

/* Static global variables */

/** Count the destroy balance to debug destroy queue logic */
static int64_t global_destroy_ctr = 0;

/* Function definitions */

/**
 * Helper for chanid_circid_cell_count_map_t hash table: compare the channel
 * ID and circuit ID for a and b, and return less than, equal to, or greater
 * than zero appropriately.
 */

static inline int
chanid_circid_entries_eq(chanid_circid_muxinfo_t *a,
                         chanid_circid_muxinfo_t *b)
{
    return a->chan_id == b->chan_id && a->circ_id == b->circ_id;
}

/**
 * Helper: return a hash based on circuit ID and channel ID in a.
 */

static inline unsigned int
chanid_circid_entry_hash(chanid_circid_muxinfo_t *a)
{
    return (((unsigned int)(a->circ_id) << 8) ^
            ((unsigned int)((a->chan_id >> 32) & 0xffffffff)) ^
            ((unsigned int)(a->chan_id & 0xffffffff)));
}

/* Declare the struct chanid_circid_muxinfo_map type */
HT_HEAD(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t);

/* Emit a bunch of hash table stuff */
HT_PROTOTYPE(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t, node,
             chanid_circid_entry_hash, chanid_circid_entries_eq)
HT_GENERATE2(chanid_circid_muxinfo_map, chanid_circid_muxinfo_t, node,
             chanid_circid_entry_hash, chanid_circid_entries_eq, 0.6,
             tor_reallocarray_, tor_free_)

/*
 * Circuitmux alloc/free functions
 */

/**
 * Allocate a new circuitmux_t
 */

circuitmux_t *
circuitmux_alloc(void)
{
  circuitmux_t *rv = NULL;

  rv = tor_malloc_zero(sizeof(*rv));
  rv->chanid_circid_map = tor_malloc_zero(sizeof(*( rv->chanid_circid_map)));
  HT_INIT(chanid_circid_muxinfo_map, rv->chanid_circid_map);
  destroy_cell_queue_init(&rv->destroy_cell_queue);

  return rv;
}

/**
 * Detach all circuits from a circuitmux (use before circuitmux_free())
 *
 * If <b>detached_out</b> is non-NULL, add every detached circuit_t to
 * detached_out.
 */

void
circuitmux_detach_all_circuits(circuitmux_t *cmux, smartlist_t *detached_out)
{
  chanid_circid_muxinfo_t **i = NULL, *to_remove;
  channel_t *chan = NULL;
  circuit_t *circ = NULL;

  tor_assert(cmux);

  i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
  while (i) {
    to_remove = *i;

    if (! to_remove) {
      log_warn(LD_BUG, "Somehow, an HT iterator gave us a NULL pointer.");
      break;
    } else {
      /* Find a channel and circuit */
      chan = channel_find_by_global_id(to_remove->chan_id);
      if (chan) {
        circ =
          circuit_get_by_circid_channel_even_if_marked(to_remove->circ_id,
                                                       chan);
        if (circ) {
          /* Clear the circuit's mux for this direction */
          if (to_remove->muxinfo.direction == CELL_DIRECTION_OUT) {
            /*
             * Update active_circuits et al.; this does policy notifies, so
             * comes before freeing policy data
             */

            if (to_remove->muxinfo.cell_count > 0) {
              circuitmux_make_circuit_inactive(cmux, circ);
            }

            /* Clear n_mux */
            circ->n_mux = NULL;

            if (detached_out)
              smartlist_add(detached_out, circ);
          } else if (circ->magic == OR_CIRCUIT_MAGIC) {
            /*
             * Update active_circuits et al.; this does policy notifies, so
             * comes before freeing policy data
             */

            if (to_remove->muxinfo.cell_count > 0) {
              circuitmux_make_circuit_inactive(cmux, circ);
            }

            /*
             * It has a sensible p_chan and direction == CELL_DIRECTION_IN,
             * so clear p_mux.
             */
            TO_OR_CIRCUIT(circ)->p_mux = NULL;

            if (detached_out)
              smartlist_add(detached_out, circ);
          } else {
            /* Complain and move on */
            log_warn(LD_CIRC,
                     "Circuit %u/channel " U64_FORMAT " had direction == "
                     "CELL_DIRECTION_IN, but isn't an or_circuit_t",
                     (unsigned)to_remove->circ_id,
                     U64_PRINTF_ARG(to_remove->chan_id));
          }

          /* Free policy-specific data if we have it */
          if (to_remove->muxinfo.policy_data) {
            /*
             * If we have policy data, assert that we have the means to
             * free it
             */
            tor_assert(cmux->policy);
            tor_assert(cmux->policy->free_circ_data);
            /* Call free_circ_data() */
            cmux->policy->free_circ_data(cmux,
                                         cmux->policy_data,
                                         circ,
                                         to_remove->muxinfo.policy_data);
            to_remove->muxinfo.policy_data = NULL;
          }
        } else {
          /* Complain and move on */
          log_warn(LD_CIRC,
                   "Couldn't find circuit %u (for channel " U64_FORMAT ")",
                   (unsigned)to_remove->circ_id,
                   U64_PRINTF_ARG(to_remove->chan_id));
        }
      } else {
        /* Complain and move on */
        log_warn(LD_CIRC,
                 "Couldn't find channel " U64_FORMAT " (for circuit id %u)",
                 U64_PRINTF_ARG(to_remove->chan_id),
                 (unsigned)to_remove->circ_id);
      }

      /* Assert that we don't have un-freed policy data for this circuit */
      tor_assert(to_remove->muxinfo.policy_data == NULL);
    }

    i = HT_NEXT_RMV(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);

    /* Free it */
    tor_free(to_remove);
  }

  cmux->n_circuits = 0;
  cmux->n_active_circuits = 0;
  cmux->n_cells = 0;
}

/** Reclaim all circuit IDs currently marked as unusable on <b>chan</b> because
 * of pending destroy cells in <b>cmux</b>.
 *
 * This function must be called AFTER circuits are unlinked from the (channel,
 * circuid-id) map with circuit_unlink_all_from_channel(), but before calling
 * circuitmux_free().
 */
void
circuitmux_mark_destroyed_circids_usable(circuitmux_t *cmux, channel_t *chan)
{
  destroy_cell_t *cell;
  TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
    channel_mark_circid_usable(chan, cell->circid);
  }
}

/**
 * Free a circuitmux_t; the circuits must be detached first with
 * circuitmux_detach_all_circuits().
 */

void
circuitmux_free_(circuitmux_t *cmux)
{
  if (!cmux) return;

  tor_assert(cmux->n_circuits == 0);
  tor_assert(cmux->n_active_circuits == 0);

  /*
   * Free policy-specific data if we have any; we don't
   * need to do circuitmux_set_policy(cmux, NULL) to cover
   * the circuits because they would have been handled in
   * circuitmux_detach_all_circuits() before this was
   * called.
   */
  if (cmux->policy && cmux->policy->free_cmux_data) {
    if (cmux->policy_data) {
      cmux->policy->free_cmux_data(cmux, cmux->policy_data);
      cmux->policy_data = NULL;
    }
  } else tor_assert(cmux->policy_data == NULL);

  if (cmux->chanid_circid_map) {
    HT_CLEAR(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
    tor_free(cmux->chanid_circid_map);
  }

  /*
   * We're throwing away some destroys; log the counter and
   * adjust the global counter by the queue size.
   */
  if (cmux->destroy_cell_queue.n > 0) {
    cmux->destroy_ctr -= cmux->destroy_cell_queue.n;
    global_destroy_ctr -= cmux->destroy_cell_queue.n;
    log_debug(LD_CIRC,
              "Freeing cmux at %p with %u queued destroys; the last cmux "
              "destroy balance was "I64_FORMAT", global is "I64_FORMAT,
              cmux, cmux->destroy_cell_queue.n,
              I64_PRINTF_ARG(cmux->destroy_ctr),
              I64_PRINTF_ARG(global_destroy_ctr));
  } else {
    log_debug(LD_CIRC,
              "Freeing cmux at %p with no queued destroys, the cmux destroy "
              "balance was "I64_FORMAT", global is "I64_FORMAT,
              cmux,
              I64_PRINTF_ARG(cmux->destroy_ctr),
              I64_PRINTF_ARG(global_destroy_ctr));
  }

  destroy_cell_queue_clear(&cmux->destroy_cell_queue);

  tor_free(cmux);
}

/*
 * Circuitmux policy control functions
 */

/**
 * Remove any policy installed on cmux; all policy data will be freed and
 * cmux behavior will revert to the built-in round-robin active_circuits
 * mechanism.
 */

void
circuitmux_clear_policy(circuitmux_t *cmux)
{
  tor_assert(cmux);

  /* Internally, this is just setting policy to NULL */
  circuitmux_set_policy(cmux, NULL);
}

/**
 * Return the policy currently installed on a circuitmux_t
 */

MOCK_IMPL(const circuitmux_policy_t *,
circuitmux_get_policy, (circuitmux_t *cmux))
{
  tor_assert(cmux);

  return cmux->policy;
}

/**
 * Set policy; allocate for new policy, detach all circuits from old policy
 * if any, attach them to new policy, and free old policy data.
 */

void
circuitmux_set_policy(circuitmux_t *cmux,
                      const circuitmux_policy_t *pol)
{
  const circuitmux_policy_t *old_pol = NULL, *new_pol = NULL;
  circuitmux_policy_data_t *old_pol_data = NULL, *new_pol_data = NULL;
  chanid_circid_muxinfo_t **i = NULL;
  channel_t *chan = NULL;
  uint64_t last_chan_id_searched = 0;
  circuit_t *circ = NULL;

  tor_assert(cmux);

  /* Set up variables */
  old_pol = cmux->policy;
  old_pol_data = cmux->policy_data;
  new_pol = pol;

  /* Check if this is the trivial case */
  if (old_pol == new_pol) return;

  /* Allocate data for new policy, if any */
  if (new_pol && new_pol->alloc_cmux_data) {
    /*
     * If alloc_cmux_data is not null, then we expect to get some policy
     * data.  Assert that we also have free_cmux_data so we can free it
     * when the time comes, and allocate it.
     */
    tor_assert(new_pol->free_cmux_data);
    new_pol_data = new_pol->alloc_cmux_data(cmux);
    tor_assert(new_pol_data);
  }

  /* Install new policy and new policy data on cmux */
  cmux->policy = new_pol;
  cmux->policy_data = new_pol_data;

  /* Iterate over all circuits, attaching/detaching each one */
  i = HT_START(chanid_circid_muxinfo_map, cmux->chanid_circid_map);
  while (i) {
    /* Assert that this entry isn't NULL */
    tor_assert(*i);

    /*
     * Get the channel; since normal case is all circuits on the mux share a
     * channel, we cache last_chan_id_searched
     */
    if (!chan || last_chan_id_searched != (*i)->chan_id) {
      chan = channel_find_by_global_id((*i)->chan_id);
      last_chan_id_searched = (*i)->chan_id;
    }
    tor_assert(chan);

    /* Get the circuit */
    circ = circuit_get_by_circid_channel_even_if_marked((*i)->circ_id, chan);
    tor_assert(circ);

    /* Need to tell old policy it becomes inactive (i.e., it is active) ? */
    if (old_pol && old_pol->notify_circ_inactive &&
        (*i)->muxinfo.cell_count > 0) {
      old_pol->notify_circ_inactive(cmux, old_pol_data, circ,
                                    (*i)->muxinfo.policy_data);
    }

    /* Need to free old policy data? */
    if ((*i)->muxinfo.policy_data) {
      /* Assert that we have the means to free it if we have policy data */
      tor_assert(old_pol);
      tor_assert(old_pol->free_circ_data);
      /* Free it */
      old_pol->free_circ_data(cmux, old_pol_data, circ,
                             (*i)->muxinfo.policy_data);
      (*i)->muxinfo.policy_data = NULL;
    }

    /* Need to allocate new policy data? */
    if (new_pol && new_pol->alloc_circ_data) {
      /*
       * If alloc_circ_data is not null, we expect to get some per-circuit
       * policy data.  Assert that we also have free_circ_data so we can
       * free it when the time comes, and allocate it.
       */
      tor_assert(new_pol->free_circ_data);
      (*i)->muxinfo.policy_data =
        new_pol->alloc_circ_data(cmux, new_pol_data, circ,
                                 (*i)->muxinfo.direction,
                                 (*i)->muxinfo.cell_count);
    }

    /* Need to make active on new policy? */
    if (new_pol && new_pol->notify_circ_active &&
        (*i)->muxinfo.cell_count > 0) {
      new_pol->notify_circ_active(cmux, new_pol_data, circ,
                                  (*i)->muxinfo.policy_data);
    }

    /* Advance to next circuit map entry */
    i = HT_NEXT(chanid_circid_muxinfo_map, cmux->chanid_circid_map, i);
  }

  /* Free data for old policy, if any */
  if (old_pol_data) {
    /*
     * If we had old policy data, we should have an old policy and a free
     * function for it.
     */
    tor_assert(old_pol);
    tor_assert(old_pol->free_cmux_data);
    old_pol->free_cmux_data(cmux, old_pol_data);
    old_pol_data = NULL;
  }
}

/*
 * Circuitmux/circuit attachment status inquiry functions
 */

/**
 * Query the direction of an attached circuit
 */

cell_direction_t
circuitmux_attached_circuit_direction(circuitmux_t *cmux, circuit_t *circ)
{
  chanid_circid_muxinfo_t *hashent = NULL;

  /* Try to find a map entry */
  hashent = circuitmux_find_map_entry(cmux, circ);

  /*
   * This function should only be called on attached circuits; assert that
   * we had a map entry.
   */
  tor_assert(hashent);

  /* Return the direction from the map entry */
  return hashent->muxinfo.direction;
}

/**
 * Find an entry in the cmux's map for this circuit or return NULL if there
 * is none.
 */

static chanid_circid_muxinfo_t *
circuitmux_find_map_entry(circuitmux_t *cmux, circuit_t *circ)
{
  chanid_circid_muxinfo_t search, *hashent = NULL;

  /* Sanity-check parameters */
  tor_assert(cmux);
  tor_assert(cmux->chanid_circid_map);
  tor_assert(circ);

  /* Check if we have n_chan */
  if (circ->n_chan) {
    /* Okay, let's see if it's attached for n_chan/n_circ_id */
    search.chan_id = circ->n_chan->global_identifier;
    search.circ_id = circ->n_circ_id;

    /* Query */
    hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
                      &search);
  }

  /* Found something? */
  if (hashent) {
    /*
     * Assert that the direction makes sense for a hashent we found by
     * n_chan/n_circ_id before we return it.
     */
    tor_assert(hashent->muxinfo.direction == CELL_DIRECTION_OUT);
  } else {
    /* Not there, have we got a p_chan/p_circ_id to try? */
    if (circ->magic == OR_CIRCUIT_MAGIC) {
      search.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
      /* Check for p_chan */
      if (TO_OR_CIRCUIT(circ)->p_chan) {
        search.chan_id = TO_OR_CIRCUIT(circ)->p_chan->global_identifier;
        /* Okay, search for that */
        hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
                          &search);
        /* Find anything? */
        if (hashent) {
          /* Assert that the direction makes sense before we return it */
          tor_assert(hashent->muxinfo.direction == CELL_DIRECTION_IN);
        }
      }
    }
  }

  /* Okay, hashent is it if it was there */
  return hashent;
}

/**
 * Query whether a circuit is attached to a circuitmux
 */

int
circuitmux_is_circuit_attached(circuitmux_t *cmux, circuit_t *circ)
{
  chanid_circid_muxinfo_t *hashent = NULL;

  /* Look if it's in the circuit map */
  hashent = circuitmux_find_map_entry(cmux, circ);

  return (hashent != NULL);
}

/**
 * Query whether a circuit is active on a circuitmux
 */

int
circuitmux_is_circuit_active(circuitmux_t *cmux, circuit_t *circ)
{
  chanid_circid_muxinfo_t *hashent = NULL;
  int is_active = 0;

  tor_assert(cmux);
  tor_assert(circ);

  /* Look if it's in the circuit map */
  hashent = circuitmux_find_map_entry(cmux, circ);
  if (hashent) {
    /* Check the number of cells on this circuit */
    is_active = (hashent->muxinfo.cell_count > 0);
  }
  /* else not attached, so not active */

  return is_active;
}

/**
 * Query number of available cells for a circuit on a circuitmux
 */

unsigned int
circuitmux_num_cells_for_circuit(circuitmux_t *cmux, circuit_t *circ)
{
  chanid_circid_muxinfo_t *hashent = NULL;
  unsigned int n_cells = 0;

  tor_assert(cmux);
  tor_assert(circ);

  /* Look if it's in the circuit map */
  hashent = circuitmux_find_map_entry(cmux, circ);
  if (hashent) {
    /* Just get the cell count for this circuit */
    n_cells = hashent->muxinfo.cell_count;
  }
  /* else not attached, so 0 cells */

  return n_cells;
}

/**
 * Query total number of available cells on a circuitmux
 */

MOCK_IMPL(unsigned int,
circuitmux_num_cells, (circuitmux_t *cmux))
{
  tor_assert(cmux);

  return cmux->n_cells + cmux->destroy_cell_queue.n;
}

/**
 * Query total number of circuits active on a circuitmux
 */

unsigned int
circuitmux_num_active_circuits(circuitmux_t *cmux)
{
  tor_assert(cmux);

  return cmux->n_active_circuits;
}

/**
 * Query total number of circuits attached to a circuitmux
 */

unsigned int
circuitmux_num_circuits(circuitmux_t *cmux)
{
  tor_assert(cmux);

  return cmux->n_circuits;
}

/*
 * Functions for circuit code to call to update circuit status
 */

/**
 * Attach a circuit to a circuitmux, for the specified direction.
 */

MOCK_IMPL(void,
circuitmux_attach_circuit,(circuitmux_t *cmux, circuit_t *circ,
                           cell_direction_t direction))
{
  channel_t *chan = NULL;
  uint64_t channel_id;
  circid_t circ_id;
  chanid_circid_muxinfo_t search, *hashent = NULL;
  unsigned int cell_count;

  tor_assert(cmux);
  tor_assert(circ);
  tor_assert(direction == CELL_DIRECTION_IN ||
             direction == CELL_DIRECTION_OUT);

  /*
   * Figure out which channel we're using, and get the circuit's current
   * cell count and circuit ID; assert that the circuit is not already
   * attached to another mux.
   */
  if (direction == CELL_DIRECTION_OUT) {
    /* It's n_chan */
    chan = circ->n_chan;
    cell_count = circ->n_chan_cells.n;
    circ_id = circ->n_circ_id;
  } else {
    /* We want p_chan */
    chan = TO_OR_CIRCUIT(circ)->p_chan;
    cell_count = TO_OR_CIRCUIT(circ)->p_chan_cells.n;
    circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
  }
  /* Assert that we did get a channel */
  tor_assert(chan);
  /* Assert that the circuit ID is sensible */
  tor_assert(circ_id != 0);

  /* Get the channel ID */
  channel_id = chan->global_identifier;

  /* See if we already have this one */
  search.chan_id = channel_id;
  search.circ_id = circ_id;
  hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
                    &search);

  if (hashent) {
    /*
     * This circuit was already attached to this cmux; make sure the
     * directions match and update the cell count and active circuit count.
     */
    log_info(LD_CIRC,
             "Circuit %u on channel " U64_FORMAT " was already attached to "
             "cmux %p (trying to attach to %p)",
             (unsigned)circ_id, U64_PRINTF_ARG(channel_id),
             ((direction == CELL_DIRECTION_OUT) ?
                circ->n_mux : TO_OR_CIRCUIT(circ)->p_mux),
             cmux);

    /*
     * The mux pointer on this circuit and the direction in result should
     * match; otherwise assert.
     */
    if (direction == CELL_DIRECTION_OUT) tor_assert(circ->n_mux == cmux);
    else tor_assert(TO_OR_CIRCUIT(circ)->p_mux == cmux);
    tor_assert(hashent->muxinfo.direction == direction);

    /*
     * Looks okay; just update the cell count and active circuits if we must
     */
    if (hashent->muxinfo.cell_count > 0 && cell_count == 0) {
      --(cmux->n_active_circuits);
      circuitmux_make_circuit_inactive(cmux, circ);
    } else if (hashent->muxinfo.cell_count == 0 && cell_count > 0) {
      ++(cmux->n_active_circuits);
      circuitmux_make_circuit_active(cmux, circ);
    }
    cmux->n_cells -= hashent->muxinfo.cell_count;
    cmux->n_cells += cell_count;
    hashent->muxinfo.cell_count = cell_count;
  } else {
    /*
     * New circuit; add an entry and update the circuit/active circuit
     * counts.
     */
    log_debug(LD_CIRC,
             "Attaching circuit %u on channel " U64_FORMAT " to cmux %p",
              (unsigned)circ_id, U64_PRINTF_ARG(channel_id), cmux);

    /*
     * Assert that the circuit doesn't already have a mux for this
     * direction.
     */
    if (direction == CELL_DIRECTION_OUT) tor_assert(circ->n_mux == NULL);
    else tor_assert(TO_OR_CIRCUIT(circ)->p_mux == NULL);

    /* Insert it in the map */
    hashent = tor_malloc_zero(sizeof(*hashent));
    hashent->chan_id = channel_id;
    hashent->circ_id = circ_id;
    hashent->muxinfo.cell_count = cell_count;
    hashent->muxinfo.direction = direction;
    /* Allocate policy specific circuit data if we need it */
    if (cmux->policy->alloc_circ_data) {
      /* Assert that we have the means to free policy-specific data */
      tor_assert(cmux->policy->free_circ_data);
      /* Allocate it */
      hashent->muxinfo.policy_data =
        cmux->policy->alloc_circ_data(cmux,
                                      cmux->policy_data,
                                      circ,
                                      direction,
                                      cell_count);
      /* If we wanted policy data, it's an error  not to get any */
      tor_assert(hashent->muxinfo.policy_data);
    }
    HT_INSERT(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
              hashent);

    /* Set the circuit's mux for this direction */
    if (direction == CELL_DIRECTION_OUT) circ->n_mux = cmux;
    else TO_OR_CIRCUIT(circ)->p_mux = cmux;

    /* Update counters */
    ++(cmux->n_circuits);
    if (cell_count > 0) {
      ++(cmux->n_active_circuits);
      circuitmux_make_circuit_active(cmux, circ);
    }
    cmux->n_cells += cell_count;
  }
}

/**
 * Detach a circuit from a circuitmux and update all counters as needed;
 * no-op if not attached.
 */

MOCK_IMPL(void,
circuitmux_detach_circuit,(circuitmux_t *cmux, circuit_t *circ))
{
  chanid_circid_muxinfo_t search, *hashent = NULL;
  /*
   * Use this to keep track of whether we found it for n_chan or
   * p_chan for consistency checking.
   *
   * The 0 initializer is not a valid cell_direction_t value.
   * We assert that it has been replaced with a valid value before it is used.
   */
  cell_direction_t last_searched_direction = 0;

  tor_assert(cmux);
  tor_assert(cmux->chanid_circid_map);
  tor_assert(circ);

  /* See if we have it for n_chan/n_circ_id */
  if (circ->n_chan) {
    search.chan_id = circ->n_chan->global_identifier;
    search.circ_id = circ->n_circ_id;
    hashent = HT_FIND(chanid_circid_muxinfo_map, cmux->chanid_circid_map,
                        &search);
    last_searched_direction = CELL_DIRECTION_OUT;
  }

  /* Got one? If not, see if it's an or_circuit_t and try p_chan/p_circ_id */
  if (!hashent) {
    if (circ->magic == OR_CIRCUIT_MAGIC) {
      search.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
      if (TO_OR_CIRCUIT(circ)->p_chan) {
        search.chan_id = TO_OR_CIRCUIT(circ)->p_chan->global_identifier;
        hashent = HT_FIND(chanid_circid_muxinfo_map,
                            cmux->chanid_circid_map,
                            &search);
        last_searched_direction = CELL_DIRECTION_IN;
      }
    }
  }

  tor_assert(last_searched_direction == CELL_DIRECTION_OUT
             || last_searched_direction == CELL_DIRECTION_IN);

  /*
   * If hashent isn't NULL, we have a circuit to detach; don't remove it from
   * the map until later of circuitmux_make_circuit_inactive() breaks.
   */
  if (hashent) {
    /* Update counters */
    --(cmux->n_circuits);
    if (hashent->muxinfo.cell_count > 0) {
      --(cmux->n_active_circuits);
      /* This does policy notifies, so comes before freeing policy data */
      circuitmux_make_circuit_inactive(cmux, circ);
    }
    cmux->n_cells -= hashent->muxinfo.cell_count;

    /* Free policy-specific data if we have it */
    if (hashent->muxinfo.policy_data) {
      /* If we have policy data, assert that we have the means to free it */
      tor_assert(cmux->policy);
      tor_assert(cmux->policy->free_circ_data);
      /* Call free_circ_data() */
      cmux->policy->free_circ_data(cmux,
                                   cmux->policy_data,
                                   circ,
                                   hashent->muxinfo.policy_data);
      hashent->muxinfo.policy_data = NULL;
    }

    /* Consistency check: the direction must match the direction searched */
    tor_assert(last_searched_direction == hashent->muxinfo.direction);
    /* Clear the circuit's mux for this direction */
    if (last_searched_direction == CELL_DIRECTION_OUT) circ->n_mux = NULL;
    else TO_OR_CIRCUIT(circ)->p_mux = NULL;

    /* Now remove it from the map */
    HT_REMOVE(chanid_circid_muxinfo_map, cmux->chanid_circid_map, hashent);

    /* Free the hash entry */
    tor_free(hashent);
  }
}

/**
 * Make a circuit active; update active list and policy-specific info, but
 * we don't mess with the counters or hash table here.
 */

static void
circuitmux_make_circuit_active(circuitmux_t *cmux, circuit_t *circ)
{
  tor_assert(cmux);
  tor_assert(cmux->policy);
  tor_assert(circ);

  /* Policy-specific notification */
  if (cmux->policy->notify_circ_active) {
    /* Okay, we need to check the circuit for policy data now */
    chanid_circid_muxinfo_t *hashent = circuitmux_find_map_entry(cmux, circ);
    /* We should have found something */
    tor_assert(hashent);
    /* Notify */
    cmux->policy->notify_circ_active(cmux, cmux->policy_data,
                                     circ, hashent->muxinfo.policy_data);
  }
}

/**
 * Make a circuit inactive; update active list and policy-specific info, but
 * we don't mess with the counters or hash table here.
 */

static void
circuitmux_make_circuit_inactive(circuitmux_t *cmux, circuit_t *circ)
{
  tor_assert(cmux);
  tor_assert(cmux->policy);
  tor_assert(circ);

  /* Policy-specific notification */
  if (cmux->policy->notify_circ_inactive) {
    /* Okay, we need to check the circuit for policy data now */
    chanid_circid_muxinfo_t *hashent = circuitmux_find_map_entry(cmux, circ);
    /* We should have found something */
    tor_assert(hashent);
    /* Notify */
    cmux->policy->notify_circ_inactive(cmux, cmux->policy_data,
                                       circ, hashent->muxinfo.policy_data);
  }
}

/**
 * Clear the cell counter for a circuit on a circuitmux
 */

void
circuitmux_clear_num_cells(circuitmux_t *cmux, circuit_t *circ)
{
  /* This is the same as setting the cell count to zero */
  circuitmux_set_num_cells(cmux, circ, 0);
}

/**
 * Set the cell counter for a circuit on a circuitmux
 */

void
circuitmux_set_num_cells(circuitmux_t *cmux, circuit_t *circ,
                         unsigned int n_cells)
{
  chanid_circid_muxinfo_t *hashent = NULL;

  tor_assert(cmux);
  tor_assert(circ);

  /* Search for this circuit's entry */
  hashent = circuitmux_find_map_entry(cmux, circ);
  /* Assert that we found one */
  tor_assert(hashent);

  /* Update cmux cell counter */
  cmux->n_cells -= hashent->muxinfo.cell_count;
  cmux->n_cells += n_cells;

  /* Do we need to notify a cmux policy? */
  if (cmux->policy->notify_set_n_cells) {
    /* Call notify_set_n_cells */
    cmux->policy->notify_set_n_cells(cmux,
                                     cmux->policy_data,
                                     circ,
                                     hashent->muxinfo.policy_data,
                                     n_cells);
  }

  /*
   * Update cmux active circuit counter: is the old cell count > 0 and the
   * new cell count == 0 ?
   */
  if (hashent->muxinfo.cell_count > 0 && n_cells == 0) {
    --(cmux->n_active_circuits);
    hashent->muxinfo.cell_count = n_cells;
    circuitmux_make_circuit_inactive(cmux, circ);
  /* Is the old cell count == 0 and the new cell count > 0 ? */
  } else if (hashent->muxinfo.cell_count == 0 && n_cells > 0) {
    ++(cmux->n_active_circuits);
    hashent->muxinfo.cell_count = n_cells;
    circuitmux_make_circuit_active(cmux, circ);
  } else {
    hashent->muxinfo.cell_count = n_cells;
  }
}

/*
 * Functions for channel code to call to get a circuit to transmit from or
 * notify that cells have been transmitted.
 */

/**
 * Pick a circuit to send from, using the active circuits list or a
 * circuitmux policy if one is available.  This is called from channel.c.
 *
 * If we would rather send a destroy cell, return NULL and set
 * *<b>destroy_queue_out</b> to the destroy queue.
 *
 * If we have nothing to send, set *<b>destroy_queue_out</b> to NULL and
 * return NULL.
 */

circuit_t *
circuitmux_get_first_active_circuit(circuitmux_t *cmux,
                                    destroy_cell_queue_t **destroy_queue_out)
{
  circuit_t *circ = NULL;

  tor_assert(cmux);
  tor_assert(cmux->policy);
  /* This callback is mandatory. */
  tor_assert(cmux->policy->pick_active_circuit);
  tor_assert(destroy_queue_out);

  *destroy_queue_out = NULL;

  if (cmux->destroy_cell_queue.n &&
        (!cmux->last_cell_was_destroy || cmux->n_active_circuits == 0)) {
    /* We have destroy cells to send, and either we just sent a relay cell,
     * or we have no relay cells to send. */

    /* XXXX We should let the cmux policy have some say in this eventually. */
    /* XXXX Alternating is not a terribly brilliant approach here. */
    *destroy_queue_out = &cmux->destroy_cell_queue;

    cmux->last_cell_was_destroy = 1;
  } else if (cmux->n_active_circuits > 0) {
    /* We also must have a cell available for this to be the case */
    tor_assert(cmux->n_cells > 0);
    /* Do we have a policy-provided circuit selector? */
    circ = cmux->policy->pick_active_circuit(cmux, cmux->policy_data);
    cmux->last_cell_was_destroy = 0;
  } else {
    tor_assert(cmux->n_cells == 0);
    tor_assert(cmux->destroy_cell_queue.n == 0);
  }

  return circ;
}

/**
 * Notify the circuitmux that cells have been sent on a circuit; this
 * is called from channel.c.
 */

void
circuitmux_notify_xmit_cells(circuitmux_t *cmux, circuit_t *circ,
                             unsigned int n_cells)
{
  chanid_circid_muxinfo_t *hashent = NULL;
  int becomes_inactive = 0;

  tor_assert(cmux);
  tor_assert(circ);

  if (n_cells == 0) return;

  /*
   * To handle this, we have to:
   *
   * 1.) Adjust the circuit's cell counter in the cmux hash table
   * 2.) Move the circuit to the tail of the active_circuits linked list
   *     for this cmux, or make the circuit inactive if the cell count
   *     went to zero.
   * 3.) Call cmux->policy->notify_xmit_cells(), if any
   */

  /* Find the hash entry */
  hashent = circuitmux_find_map_entry(cmux, circ);
  /* Assert that we found one */
  tor_assert(hashent);

  /* Adjust the cell counter and assert that we had that many cells to send */
  tor_assert(n_cells <= hashent->muxinfo.cell_count);
  hashent->muxinfo.cell_count -= n_cells;
  /* Do we need to make the circuit inactive? */
  if (hashent->muxinfo.cell_count == 0) becomes_inactive = 1;
  /* Adjust the mux cell counter */
  cmux->n_cells -= n_cells;

  /*
   * We call notify_xmit_cells() before making the circuit inactive if needed,
   * so the policy can always count on this coming in on an active circuit.
   */
  if (cmux->policy->notify_xmit_cells) {
    cmux->policy->notify_xmit_cells(cmux, cmux->policy_data, circ,
                                    hashent->muxinfo.policy_data,
                                    n_cells);
  }

  /*
   * Now make the circuit inactive if needed; this will call the policy's
   * notify_circ_inactive() if present.
   */
  if (becomes_inactive) {
    --(cmux->n_active_circuits);
    circuitmux_make_circuit_inactive(cmux, circ);
  }
}

/**
 * Notify the circuitmux that a destroy was sent, so we can update
 * the counter.
 */

void
circuitmux_notify_xmit_destroy(circuitmux_t *cmux)
{
  tor_assert(cmux);

  --(cmux->destroy_ctr);
  --(global_destroy_ctr);
  log_debug(LD_CIRC,
            "Cmux at %p sent a destroy, cmux counter is now "I64_FORMAT", "
            "global counter is now "I64_FORMAT,
            cmux,
            I64_PRINTF_ARG(cmux->destroy_ctr),
            I64_PRINTF_ARG(global_destroy_ctr));
}

/*DOCDOC */
void
circuitmux_append_destroy_cell(channel_t *chan,
                               circuitmux_t *cmux,
                               circid_t circ_id,
                               uint8_t reason)
{
  destroy_cell_queue_append(&cmux->destroy_cell_queue, circ_id, reason);

  /* Destroy entering the queue, update counters */
  ++(cmux->destroy_ctr);
  ++global_destroy_ctr;
  log_debug(LD_CIRC,
            "Cmux at %p queued a destroy for circ %u, cmux counter is now "
            I64_FORMAT", global counter is now "I64_FORMAT,
            cmux, circ_id,
            I64_PRINTF_ARG(cmux->destroy_ctr),
            I64_PRINTF_ARG(global_destroy_ctr));

  /* XXXX Duplicate code from append_cell_to_circuit_queue */
  if (!channel_has_queued_writes(chan)) {
    /* There is no data at all waiting to be sent on the outbuf.  Add a
     * cell, so that we can notice when it gets flushed, flushed_some can
     * get called, and we can start putting more data onto the buffer then.
     */
    log_debug(LD_GENERAL, "Primed a buffer.");
    channel_flush_from_first_active_circuit(chan, 1);
  }
}

/*DOCDOC; for debugging 12184.  This runs slowly. */
int64_t
circuitmux_count_queued_destroy_cells(const channel_t *chan,
                                      const circuitmux_t *cmux)
{
  int64_t n_destroy_cells = cmux->destroy_ctr;
  int64_t destroy_queue_size = cmux->destroy_cell_queue.n;

  int64_t manual_total = 0;
  int64_t manual_total_in_map = 0;
  destroy_cell_t *cell;

  TOR_SIMPLEQ_FOREACH(cell, &cmux->destroy_cell_queue.head, next) {
    circid_t id;
    ++manual_total;

    id = cell->circid;
    if (circuit_id_in_use_on_channel(id, (channel_t*)chan))
      ++manual_total_in_map;
  }

  if (n_destroy_cells != destroy_queue_size ||
      n_destroy_cells != manual_total ||
      n_destroy_cells != manual_total_in_map) {
    log_warn(LD_BUG, "  Discrepancy in counts for queued destroy cells on "
             "circuitmux. n="I64_FORMAT". queue_size="I64_FORMAT". "
             "manual_total="I64_FORMAT". manual_total_in_map="I64_FORMAT".",
             I64_PRINTF_ARG(n_destroy_cells),
             I64_PRINTF_ARG(destroy_queue_size),
             I64_PRINTF_ARG(manual_total),
             I64_PRINTF_ARG(manual_total_in_map));
  }

  return n_destroy_cells;
}

/**
 * Compare cmuxes to see which is more preferred; return < 0 if
 * cmux_1 has higher priority (i.e., cmux_1 < cmux_2 in the scheduler's
 * sort order), > 0 if cmux_2 has higher priority, or 0 if they are
 * equally preferred.
 *
 * If the cmuxes have different cmux policies or the policy does not
 * support the cmp_cmux method, return 0.
 */

MOCK_IMPL(int,
circuitmux_compare_muxes, (circuitmux_t *cmux_1, circuitmux_t *cmux_2))
{
  const circuitmux_policy_t *policy;

  tor_assert(cmux_1);
  tor_assert(cmux_2);

  if (cmux_1 == cmux_2) {
    /* Equivalent because they're the same cmux */
    return 0;
  }

  if (cmux_1->policy && cmux_2->policy) {
    if (cmux_1->policy == cmux_2->policy) {
      policy = cmux_1->policy;

      if (policy->cmp_cmux) {
        /* Okay, we can compare! */
        return policy->cmp_cmux(cmux_1, cmux_1->policy_data,
                                cmux_2, cmux_2->policy_data);
      } else {
        /*
         * Equivalent because the policy doesn't know how to compare between
         * muxes.
         */
        return 0;
      }
    } else {
      /* Equivalent because they have different policies */
      return 0;
    }
  } else {
    /* Equivalent because one or both are missing a policy */
    return 0;
  }
}