connection_edge.c

/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
 * Copyright (c) 2007-2019, The Tor Project, Inc. */
/* See LICENSE for licensing information */

/**
 * \file connection_edge.c
 * \brief Handle edge streams.
 *
 * An edge_connection_t is a subtype of a connection_t, and represents two
 * critical concepts in Tor: a stream, and an edge connection.  From the Tor
 * protocol's point of view, a stream is a bi-directional channel that is
 * multiplexed on a single circuit.  Each stream on a circuit is identified
 * with a separate 16-bit stream ID, local to the (circuit,exit) pair.
 * Streams are created in response to client requests.
 *
 * An edge connection is one thing that can implement a stream: it is either a
 * TCP application socket that has arrived via (e.g.) a SOCKS request, or an
 * exit connection.
 *
 * Not every instance of edge_connection_t truly represents an edge connction,
 * however. (Sorry!) We also create edge_connection_t objects for streams that
 * we will not be handling with TCP.  The types of these streams are:
 *   <ul>
 *   <li>DNS lookup streams, created on the client side in response to
 *     a UDP DNS request received on a DNSPort, or a RESOLVE command
 *     on a controller.
 *   <li>DNS lookup streams, created on the exit side in response to
 *     a RELAY_RESOLVE cell from a client.
 *   <li>Tunneled directory streams, created on the directory cache side
 *     in response to a RELAY_BEGIN_DIR cell.  These streams attach directly
 *     to a dir_connection_t object without ever using TCP.
 *   </ul>
 *
 * This module handles general-purpose functionality having to do with
 * edge_connection_t.  On the client side, it accepts various types of
 * application requests on SocksPorts, TransPorts, and NATDPorts, and
 * creates streams appropriately.
 *
 * This module is also responsible for implementing stream isolation:
 * ensuring that streams that should not be linkable to one another are
 * kept to different circuits.
 *
 * On the exit side, this module handles the various stream-creating
 * type of RELAY cells by launching appropriate outgoing connections,
 * DNS requests, or directory connection objects.
 *
 * And for all edge connections, this module is responsible for handling
 * incoming and outdoing data as it arrives or leaves in the relay.c
 * module.  (Outgoing data will be packaged in
 * connection_edge_process_inbuf() as it calls
 * connection_edge_package_raw_inbuf(); incoming data from RELAY_DATA
 * cells is applied in connection_edge_process_relay_cell().)
 **/
#define CONNECTION_EDGE_PRIVATE

#include "core/or/or.h"

#include "lib/err/backtrace.h"

#include "app/config/config.h"
#include "core/mainloop/connection.h"
#include "core/mainloop/mainloop.h"
#include "core/mainloop/netstatus.h"
#include "core/or/channel.h"
#include "core/or/circuitbuild.h"
#include "core/or/circuitlist.h"
#include "core/or/circuituse.h"
#include "core/or/circuitpadding.h"
#include "core/or/connection_edge.h"
#include "core/or/connection_or.h"
#include "core/or/policies.h"
#include "core/or/reasons.h"
#include "core/or/relay.h"
#include "core/or/sendme.h"
#include "core/proto/proto_http.h"
#include "core/proto/proto_socks.h"
#include "feature/client/addressmap.h"
#include "feature/client/circpathbias.h"
#include "feature/client/dnsserv.h"
#include "feature/control/control_events.h"
#include "feature/dircache/dirserv.h"
#include "feature/dircommon/directory.h"
#include "feature/hibernate/hibernate.h"
#include "feature/hs/hs_cache.h"
#include "feature/hs/hs_circuit.h"
#include "feature/hs/hs_client.h"
#include "feature/hs/hs_common.h"
#include "feature/nodelist/describe.h"
#include "feature/nodelist/networkstatus.h"
#include "feature/nodelist/nodelist.h"
#include "feature/nodelist/routerlist.h"
#include "feature/nodelist/routerset.h"
#include "feature/relay/dns.h"
#include "feature/relay/router.h"
#include "feature/relay/routermode.h"
#include "feature/rend/rendclient.h"
#include "feature/rend/rendcommon.h"
#include "feature/rend/rendservice.h"
#include "feature/stats/predict_ports.h"
#include "feature/stats/rephist.h"
#include "lib/buf/buffers.h"
#include "lib/crypt_ops/crypto_util.h"

#include "core/or/cell_st.h"
#include "core/or/cpath_build_state_st.h"
#include "feature/dircommon/dir_connection_st.h"
#include "core/or/entry_connection_st.h"
#include "core/or/extend_info_st.h"
#include "feature/nodelist/node_st.h"
#include "core/or/or_circuit_st.h"
#include "core/or/origin_circuit_st.h"
#include "core/or/half_edge_st.h"
#include "core/or/socks_request_st.h"
#include "lib/evloop/compat_libevent.h"

#ifdef HAVE_LINUX_TYPES_H
#include <linux/types.h>
#endif
#ifdef HAVE_LINUX_NETFILTER_IPV4_H
#include <linux/netfilter_ipv4.h>
#define TRANS_NETFILTER
#define TRANS_NETFILTER_IPV4
#endif

#ifdef HAVE_LINUX_IF_H
#include <linux/if.h>
#endif

#ifdef HAVE_LINUX_NETFILTER_IPV6_IP6_TABLES_H
#include <linux/netfilter_ipv6/ip6_tables.h>
#if defined(IP6T_SO_ORIGINAL_DST)
#define TRANS_NETFILTER
#define TRANS_NETFILTER_IPV6
#endif
#endif /* defined(HAVE_LINUX_NETFILTER_IPV6_IP6_TABLES_H) */

#ifdef HAVE_FCNTL_H
#include <fcntl.h>
#endif
#ifdef HAVE_SYS_IOCTL_H
#include <sys/ioctl.h>
#endif
#ifdef HAVE_SYS_PARAM_H
#include <sys/param.h>
#endif

#if defined(HAVE_NET_IF_H) && defined(HAVE_NET_PFVAR_H)
#include <net/if.h>
#include <net/pfvar.h>
#define TRANS_PF
#endif

#ifdef IP_TRANSPARENT
#define TRANS_TPROXY
#endif

#define SOCKS4_GRANTED          90
#define SOCKS4_REJECT           91

static int connection_ap_handshake_process_socks(entry_connection_t *conn);
static int connection_ap_process_natd(entry_connection_t *conn);
static int connection_exit_connect_dir(edge_connection_t *exitconn);
static int consider_plaintext_ports(entry_connection_t *conn, uint16_t port);
static int connection_ap_supports_optimistic_data(const entry_connection_t *);

/** Convert a connection_t* to an edge_connection_t*; assert if the cast is
 * invalid. */
edge_connection_t *
TO_EDGE_CONN(connection_t *c)
{
  tor_assert(c->magic == EDGE_CONNECTION_MAGIC ||
             c->magic == ENTRY_CONNECTION_MAGIC);
  return DOWNCAST(edge_connection_t, c);
}

entry_connection_t *
TO_ENTRY_CONN(connection_t *c)
{
  tor_assert(c->magic == ENTRY_CONNECTION_MAGIC);
  return (entry_connection_t*) SUBTYPE_P(c, entry_connection_t, edge_.base_);
}

entry_connection_t *
EDGE_TO_ENTRY_CONN(edge_connection_t *c)
{
  tor_assert(c->base_.magic == ENTRY_CONNECTION_MAGIC);
  return (entry_connection_t*) SUBTYPE_P(c, entry_connection_t, edge_);
}

/** An AP stream has failed/finished. If it hasn't already sent back
 * a socks reply, send one now (based on endreason). Also set
 * has_sent_end to 1, and mark the conn.
 */
MOCK_IMPL(void,
connection_mark_unattached_ap_,(entry_connection_t *conn, int endreason,
                                int line, const char *file))
{
  connection_t *base_conn = ENTRY_TO_CONN(conn);
  edge_connection_t *edge_conn = ENTRY_TO_EDGE_CONN(conn);
  tor_assert(base_conn->type == CONN_TYPE_AP);
  ENTRY_TO_EDGE_CONN(conn)->edge_has_sent_end = 1; /* no circ yet */

  /* If this is a rendezvous stream and it is failing without ever
   * being attached to a circuit, assume that an attempt to connect to
   * the destination hidden service has just ended.
   *
   * XXXX This condition doesn't limit to only streams failing
   * without ever being attached.  That sloppiness should be harmless,
   * but we should fix it someday anyway. */
  if ((edge_conn->on_circuit != NULL || edge_conn->edge_has_sent_end) &&
      connection_edge_is_rendezvous_stream(edge_conn)) {
    if (edge_conn->rend_data) {
      rend_client_note_connection_attempt_ended(edge_conn->rend_data);
    }
  }

  if (base_conn->marked_for_close) {
    /* This call will warn as appropriate. */
    connection_mark_for_close_(base_conn, line, file);
    return;
  }

  if (!conn->socks_request->has_finished) {
    if (endreason & END_STREAM_REASON_FLAG_ALREADY_SOCKS_REPLIED)
      log_warn(LD_BUG,
               "stream (marked at %s:%d) sending two socks replies?",
               file, line);

    if (SOCKS_COMMAND_IS_CONNECT(conn->socks_request->command))
      connection_ap_handshake_socks_reply(conn, NULL, 0, endreason);
    else if (SOCKS_COMMAND_IS_RESOLVE(conn->socks_request->command))
      connection_ap_handshake_socks_resolved(conn,
                                             RESOLVED_TYPE_ERROR_TRANSIENT,
                                             0, NULL, -1, -1);
    else /* unknown or no handshake at all. send no response. */
      conn->socks_request->has_finished = 1;
  }

  connection_mark_and_flush_(base_conn, line, file);

  ENTRY_TO_EDGE_CONN(conn)->end_reason = endreason;
}

/** There was an EOF. Send an end and mark the connection for close.
 */
int
connection_edge_reached_eof(edge_connection_t *conn)
{
  if (connection_get_inbuf_len(TO_CONN(conn)) &&
      connection_state_is_open(TO_CONN(conn))) {
    /* it still has stuff to process. don't let it die yet. */
    return 0;
  }
  log_info(LD_EDGE,"conn (fd "TOR_SOCKET_T_FORMAT") reached eof. Closing.",
           conn->base_.s);
  if (!conn->base_.marked_for_close) {
    /* only mark it if not already marked. it's possible to
     * get the 'end' right around when the client hangs up on us. */
    connection_edge_end(conn, END_STREAM_REASON_DONE);
    if (conn->base_.type == CONN_TYPE_AP) {
      /* eof, so don't send a socks reply back */
      if (EDGE_TO_ENTRY_CONN(conn)->socks_request)
        EDGE_TO_ENTRY_CONN(conn)->socks_request->has_finished = 1;
    }
    connection_mark_for_close(TO_CONN(conn));
  }
  return 0;
}

/** Handle new bytes on conn->inbuf based on state:
 *   - If it's waiting for socks info, try to read another step of the
 *     socks handshake out of conn->inbuf.
 *   - If it's waiting for the original destination, fetch it.
 *   - If it's open, then package more relay cells from the stream.
 *   - Else, leave the bytes on inbuf alone for now.
 *
 * Mark and return -1 if there was an unexpected error with the conn,
 * else return 0.
 */
int
connection_edge_process_inbuf(edge_connection_t *conn, int package_partial)
{
  tor_assert(conn);

  switch (conn->base_.state) {
    case AP_CONN_STATE_SOCKS_WAIT:
      if (connection_ap_handshake_process_socks(EDGE_TO_ENTRY_CONN(conn)) <0) {
        /* already marked */
        return -1;
      }
      return 0;
    case AP_CONN_STATE_NATD_WAIT:
      if (connection_ap_process_natd(EDGE_TO_ENTRY_CONN(conn)) < 0) {
        /* already marked */
        return -1;
      }
      return 0;
    case AP_CONN_STATE_HTTP_CONNECT_WAIT:
      if (connection_ap_process_http_connect(EDGE_TO_ENTRY_CONN(conn)) < 0) {
        return -1;
      }
      return 0;
    case AP_CONN_STATE_OPEN:
      if (! conn->base_.linked) {
        note_user_activity(approx_time());
      }

      FALLTHROUGH;
    case EXIT_CONN_STATE_OPEN:
      if (connection_edge_package_raw_inbuf(conn, package_partial, NULL) < 0) {
        /* (We already sent an end cell if possible) */
        connection_mark_for_close(TO_CONN(conn));
        return -1;
      }
      return 0;
    case AP_CONN_STATE_CONNECT_WAIT:
      if (connection_ap_supports_optimistic_data(EDGE_TO_ENTRY_CONN(conn))) {
        log_info(LD_EDGE,
                 "data from edge while in '%s' state. Sending it anyway. "
                 "package_partial=%d, buflen=%ld",
                 conn_state_to_string(conn->base_.type, conn->base_.state),
                 package_partial,
                 (long)connection_get_inbuf_len(TO_CONN(conn)));
        if (connection_edge_package_raw_inbuf(conn, package_partial, NULL)<0) {
          /* (We already sent an end cell if possible) */
          connection_mark_for_close(TO_CONN(conn));
          return -1;
        }
        return 0;
      }
      /* Fall through if the connection is on a circuit without optimistic
       * data support. */
      FALLTHROUGH;
    case EXIT_CONN_STATE_CONNECTING:
    case AP_CONN_STATE_RENDDESC_WAIT:
    case AP_CONN_STATE_CIRCUIT_WAIT:
    case AP_CONN_STATE_RESOLVE_WAIT:
    case AP_CONN_STATE_CONTROLLER_WAIT:
      log_info(LD_EDGE,
               "data from edge while in '%s' state. Leaving it on buffer.",
               conn_state_to_string(conn->base_.type, conn->base_.state));
      return 0;
  }
  log_warn(LD_BUG,"Got unexpected state %d. Closing.",conn->base_.state);
  tor_fragile_assert();
  connection_edge_end(conn, END_STREAM_REASON_INTERNAL);
  connection_mark_for_close(TO_CONN(conn));
  return -1;
}

/** This edge needs to be closed, because its circuit has closed.
 * Mark it for close and return 0.
 */
int
connection_edge_destroy(circid_t circ_id, edge_connection_t *conn)
{
  if (!conn->base_.marked_for_close) {
    log_info(LD_EDGE, "CircID %u: At an edge. Marking connection for close.",
             (unsigned) circ_id);
    if (conn->base_.type == CONN_TYPE_AP) {
      entry_connection_t *entry_conn = EDGE_TO_ENTRY_CONN(conn);
      connection_mark_unattached_ap(entry_conn, END_STREAM_REASON_DESTROY);
      control_event_stream_bandwidth(conn);
      control_event_stream_status(entry_conn, STREAM_EVENT_CLOSED,
                                  END_STREAM_REASON_DESTROY);
      conn->end_reason |= END_STREAM_REASON_FLAG_ALREADY_SENT_CLOSED;
    } else {
      /* closing the circuit, nothing to send an END to */
      conn->edge_has_sent_end = 1;
      conn->end_reason = END_STREAM_REASON_DESTROY;
      conn->end_reason |= END_STREAM_REASON_FLAG_ALREADY_SENT_CLOSED;
      connection_mark_and_flush(TO_CONN(conn));
    }
  }
  conn->cpath_layer = NULL;
  conn->on_circuit = NULL;
  return 0;
}

/** Send a raw end cell to the stream with ID <b>stream_id</b> out over the
 * <b>circ</b> towards the hop identified with <b>cpath_layer</b>. If this
 * is not a client connection, set the relay end cell's reason for closing
 * as <b>reason</b> */
static int
relay_send_end_cell_from_edge(streamid_t stream_id, circuit_t *circ,
                              uint8_t reason, crypt_path_t *cpath_layer)
{
  char payload[1];

  if (CIRCUIT_PURPOSE_IS_CLIENT(circ->purpose)) {
    /* Never send the server an informative reason code; it doesn't need to
     * know why the client stream is failing. */
    reason = END_STREAM_REASON_MISC;
  }

  payload[0] = (char) reason;

  /* Note: we have to use relay_send_command_from_edge here, not
   * connection_edge_end or connection_edge_send_command, since those require
   * that we have a stream connected to a circuit, and we don't connect to a
   * circuit until we have a pending/successful resolve. */
  return relay_send_command_from_edge(stream_id, circ, RELAY_COMMAND_END,
                                      payload, 1, cpath_layer);
}

/* If the connection <b>conn</b> is attempting to connect to an external
 * destination that is an hidden service and the reason is a connection
 * refused or timeout, log it so the operator can take appropriate actions.
 * The log statement is a rate limited warning. */
static void
warn_if_hs_unreachable(const edge_connection_t *conn, uint8_t reason)
{
  tor_assert(conn);

  if (conn->base_.type == CONN_TYPE_EXIT &&
      connection_edge_is_rendezvous_stream(conn) &&
      (reason == END_STREAM_REASON_CONNECTREFUSED ||
       reason == END_STREAM_REASON_TIMEOUT)) {
#define WARN_FAILED_HS_CONNECTION 300
    static ratelim_t warn_limit = RATELIM_INIT(WARN_FAILED_HS_CONNECTION);
    char *m;
    if ((m = rate_limit_log(&warn_limit, approx_time()))) {
      log_warn(LD_EDGE, "Onion service connection to %s failed (%s)",
               (conn->base_.socket_family == AF_UNIX) ?
               safe_str(conn->base_.address) :
               safe_str(fmt_addrport(&conn->base_.addr, conn->base_.port)),
               stream_end_reason_to_string(reason));
      tor_free(m);
    }
  }
}

/** Send a relay end cell from stream <b>conn</b> down conn's circuit, and
 * remember that we've done so.  If this is not a client connection, set the
 * relay end cell's reason for closing as <b>reason</b>.
 *
 * Return -1 if this function has already been called on this conn,
 * else return 0.
 */
int
connection_edge_end(edge_connection_t *conn, uint8_t reason)
{
  char payload[RELAY_PAYLOAD_SIZE];
  size_t payload_len=1;
  circuit_t *circ;
  uint8_t control_reason = reason;

  if (conn->edge_has_sent_end) {
    log_warn(LD_BUG,"(Harmless.) Calling connection_edge_end (reason %d) "
             "on an already ended stream?", reason);
    tor_fragile_assert();
    return -1;
  }

  if (conn->base_.marked_for_close) {
    log_warn(LD_BUG,
             "called on conn that's already marked for close at %s:%d.",
             conn->base_.marked_for_close_file, conn->base_.marked_for_close);
    return 0;
  }

  circ = circuit_get_by_edge_conn(conn);
  if (circ && CIRCUIT_PURPOSE_IS_CLIENT(circ->purpose)) {
    /* If this is a client circuit, don't send the server an informative
     * reason code; it doesn't need to know why the client stream is
     * failing. */
    reason = END_STREAM_REASON_MISC;
  }

  payload[0] = (char)reason;
  if (reason == END_STREAM_REASON_EXITPOLICY &&
      !connection_edge_is_rendezvous_stream(conn)) {
    int addrlen;
    if (tor_addr_family(&conn->base_.addr) == AF_INET) {
      set_uint32(payload+1, tor_addr_to_ipv4n(&conn->base_.addr));
      addrlen = 4;
    } else {
      memcpy(payload+1, tor_addr_to_in6_addr8(&conn->base_.addr), 16);
      addrlen = 16;
    }
    set_uint32(payload+1+addrlen, htonl(dns_clip_ttl(conn->address_ttl)));
    payload_len += 4+addrlen;
  }

  if (circ && !circ->marked_for_close) {
    log_debug(LD_EDGE,"Sending end on conn (fd "TOR_SOCKET_T_FORMAT").",
              conn->base_.s);

    if (CIRCUIT_IS_ORIGIN(circ)) {
      origin_circuit_t *origin_circ = TO_ORIGIN_CIRCUIT(circ);
      connection_half_edge_add(conn, origin_circ);
    }

    connection_edge_send_command(conn, RELAY_COMMAND_END,
                                 payload, payload_len);
    /* We'll log warn if the connection was an hidden service and couldn't be
     * made because the service wasn't available. */
    warn_if_hs_unreachable(conn, control_reason);
  } else {
    log_debug(LD_EDGE,"No circ to send end on conn "
              "(fd "TOR_SOCKET_T_FORMAT").",
              conn->base_.s);
  }

  conn->edge_has_sent_end = 1;
  conn->end_reason = control_reason;
  return 0;
}

/**
 * Helper function for bsearch.
 *
 * As per smartlist_bsearch, return < 0 if key preceeds member,
 * > 0 if member preceeds key, and 0 if they are equal.
 *
 * This is equivalent to subtraction of the values of key - member
 * (why does no one ever say that explicitly?).
 */
static int
connection_half_edge_compare_bsearch(const void *key, const void **member)
{
  const half_edge_t *e2;
  tor_assert(key);
  tor_assert(member && *(half_edge_t**)member);
  e2 = *(const half_edge_t **)member;

  return *(const streamid_t*)key - e2->stream_id;
}

/** Total number of half_edge_t objects allocated */
static size_t n_half_conns_allocated = 0;

/**
 * Add a half-closed connection to the list, to watch for activity.
 *
 * These connections are removed from the list upon receiving an end
 * cell.
 */
STATIC void
connection_half_edge_add(const edge_connection_t *conn,
                         origin_circuit_t *circ)
{
  half_edge_t *half_conn = NULL;
  int insert_at = 0;
  int ignored;

  /* Double-check for re-insertion. This should not happen,
   * but this check is cheap compared to the sort anyway */
  if (connection_half_edge_find_stream_id(circ->half_streams,
                                          conn->stream_id)) {
    log_warn(LD_BUG, "Duplicate stream close for stream %d on circuit %d",
             conn->stream_id, circ->global_identifier);
    return;
  }

  half_conn = tor_malloc_zero(sizeof(half_edge_t));
  ++n_half_conns_allocated;

  if (!circ->half_streams) {
    circ->half_streams = smartlist_new();
  }

  half_conn->stream_id = conn->stream_id;

  // How many sendme's should I expect?
  half_conn->sendmes_pending =
   (STREAMWINDOW_START-conn->package_window)/STREAMWINDOW_INCREMENT;

   // Is there a connected cell pending?
  half_conn->connected_pending = conn->base_.state ==
      AP_CONN_STATE_CONNECT_WAIT;

  /* Data should only arrive if we're not waiting on a resolved cell.
   * It can arrive after waiting on connected, because of optimistic
   * data. */
  if (conn->base_.state != AP_CONN_STATE_RESOLVE_WAIT) {
    // How many more data cells can arrive on this id?
    half_conn->data_pending = conn->deliver_window;
  }

  insert_at = smartlist_bsearch_idx(circ->half_streams, &half_conn->stream_id,
                                    connection_half_edge_compare_bsearch,
                                    &ignored);
  smartlist_insert(circ->half_streams, insert_at, half_conn);
}

/** Release space held by <b>he</b> */
void
half_edge_free_(half_edge_t *he)
{
  if (!he)
    return;
  --n_half_conns_allocated;
  tor_free(he);
}

/** Return the number of bytes devoted to storing info on half-open streams. */
size_t
half_streams_get_total_allocation(void)
{
  return n_half_conns_allocated * sizeof(half_edge_t);
}

/**
 * Find a stream_id_t in the list in O(lg(n)).
 *
 * Returns NULL if the list is empty or element is not found.
 * Returns a pointer to the element if found.
 */
STATIC half_edge_t *
connection_half_edge_find_stream_id(const smartlist_t *half_conns,
                                    streamid_t stream_id)
{
  if (!half_conns)
    return NULL;

  return smartlist_bsearch(half_conns, &stream_id,
                           connection_half_edge_compare_bsearch);
}

/**
 * Check if this stream_id is in a half-closed state. If so,
 * check if it still has data cells pending, and decrement that
 * window if so.
 *
 * Return 1 if the data window was not empty.
 * Return 0 otherwise.
 */
int
connection_half_edge_is_valid_data(const smartlist_t *half_conns,
                                   streamid_t stream_id)
{
  half_edge_t *half = connection_half_edge_find_stream_id(half_conns,
                                                          stream_id);

  if (!half)
    return 0;

  if (half->data_pending > 0) {
    half->data_pending--;
    return 1;
  }

  return 0;
}

/**
 * Check if this stream_id is in a half-closed state. If so,
 * check if it still has a connected cell pending, and decrement
 * that window if so.
 *
 * Return 1 if the connected window was not empty.
 * Return 0 otherwise.
 */
int
connection_half_edge_is_valid_connected(const smartlist_t *half_conns,
                                        streamid_t stream_id)
{
  half_edge_t *half = connection_half_edge_find_stream_id(half_conns,
                                                          stream_id);

  if (!half)
    return 0;

  if (half->connected_pending) {
    half->connected_pending = 0;
    return 1;
  }

  return 0;
}

/**
 * Check if this stream_id is in a half-closed state. If so,
 * check if it still has sendme cells pending, and decrement that
 * window if so.
 *
 * Return 1 if the sendme window was not empty.
 * Return 0 otherwise.
 */
int
connection_half_edge_is_valid_sendme(const smartlist_t *half_conns,
                                     streamid_t stream_id)
{
  half_edge_t *half = connection_half_edge_find_stream_id(half_conns,
                                                          stream_id);

  if (!half)
    return 0;

  if (half->sendmes_pending > 0) {
    half->sendmes_pending--;
    return 1;
  }

  return 0;
}

/**
 * Check if this stream_id is in a half-closed state. If so, remove
 * it from the list. No other data should come after the END cell.
 *
 * Return 1 if stream_id was in half-closed state.
 * Return 0 otherwise.
 */
int
connection_half_edge_is_valid_end(smartlist_t *half_conns,
                                  streamid_t stream_id)
{
  half_edge_t *half;
  int found, remove_idx;

  if (!half_conns)
    return 0;

  remove_idx = smartlist_bsearch_idx(half_conns, &stream_id,
                                    connection_half_edge_compare_bsearch,
                                    &found);
  if (!found)
    return 0;

  half = smartlist_get(half_conns, remove_idx);
  smartlist_del_keeporder(half_conns, remove_idx);
  half_edge_free(half);
  return 1;
}

/**
 * Streams that were used to send a RESOLVE cell are closed
 * when they get the RESOLVED, without an end. So treat
 * a RESOLVED just like an end, and remove from the list.
 */
int
connection_half_edge_is_valid_resolved(smartlist_t *half_conns,
                                       streamid_t stream_id)
{
  return connection_half_edge_is_valid_end(half_conns, stream_id);
}

/** An error has just occurred on an operation on an edge connection
 * <b>conn</b>.  Extract the errno; convert it to an end reason, and send an
 * appropriate relay end cell to the other end of the connection's circuit.
 **/
int
connection_edge_end_errno(edge_connection_t *conn)
{
  uint8_t reason;
  tor_assert(conn);
  reason = errno_to_stream_end_reason(tor_socket_errno(conn->base_.s));
  return connection_edge_end(conn, reason);
}

/** We just wrote some data to <b>conn</b>; act appropriately.
 *
 * (That is, if it's open, consider sending a stream-level sendme cell if we
 * have just flushed enough.)
 */
int
connection_edge_flushed_some(edge_connection_t *conn)
{
  switch (conn->base_.state) {
    case AP_CONN_STATE_OPEN:
      if (! conn->base_.linked) {
        note_user_activity(approx_time());
      }

      FALLTHROUGH;
    case EXIT_CONN_STATE_OPEN:
      sendme_connection_edge_consider_sending(conn);
      break;
  }
  return 0;
}

/** Connection <b>conn</b> has finished writing and has no bytes left on
 * its outbuf.
 *
 * If it's in state 'open', stop writing, consider responding with a
 * sendme, and return.
 * Otherwise, stop writing and return.
 *
 * If <b>conn</b> is broken, mark it for close and return -1, else
 * return 0.
 */
int
connection_edge_finished_flushing(edge_connection_t *conn)
{
  tor_assert(conn);

  switch (conn->base_.state) {
    case AP_CONN_STATE_OPEN:
    case EXIT_CONN_STATE_OPEN:
      sendme_connection_edge_consider_sending(conn);
      return 0;
    case AP_CONN_STATE_SOCKS_WAIT:
    case AP_CONN_STATE_NATD_WAIT:
    case AP_CONN_STATE_RENDDESC_WAIT:
    case AP_CONN_STATE_CIRCUIT_WAIT:
    case AP_CONN_STATE_CONNECT_WAIT:
    case AP_CONN_STATE_CONTROLLER_WAIT:
    case AP_CONN_STATE_RESOLVE_WAIT:
    case AP_CONN_STATE_HTTP_CONNECT_WAIT:
      return 0;
    default:
      log_warn(LD_BUG, "Called in unexpected state %d.",conn->base_.state);
      tor_fragile_assert();
      return -1;
  }
  return 0;
}

/** Longest size for the relay payload of a RELAY_CONNECTED cell that we're
 * able to generate. */
/* 4 zero bytes; 1 type byte; 16 byte IPv6 address; 4 byte TTL. */
#define MAX_CONNECTED_CELL_PAYLOAD_LEN 25

/** Set the buffer at <b>payload_out</b> -- which must have at least
 * MAX_CONNECTED_CELL_PAYLOAD_LEN bytes available -- to the body of a
 * RELAY_CONNECTED cell indicating that we have connected to <b>addr</b>, and
 * that the name resolution that led us to <b>addr</b> will be valid for
 * <b>ttl</b> seconds. Return -1 on error, or the number of bytes used on
 * success. */
STATIC int
connected_cell_format_payload(uint8_t *payload_out,
                              const tor_addr_t *addr,
                              uint32_t ttl)
{
  const sa_family_t family = tor_addr_family(addr);
  int connected_payload_len;

  /* should be needless */
  memset(payload_out, 0, MAX_CONNECTED_CELL_PAYLOAD_LEN);

  if (family == AF_INET) {
    set_uint32(payload_out, tor_addr_to_ipv4n(addr));
    connected_payload_len = 4;
  } else if (family == AF_INET6) {
    set_uint32(payload_out, 0);
    set_uint8(payload_out + 4, 6);
    memcpy(payload_out + 5, tor_addr_to_in6_addr8(addr), 16);
    connected_payload_len = 21;
  } else {
    return -1;
  }

  set_uint32(payload_out + connected_payload_len, htonl(dns_clip_ttl(ttl)));
  connected_payload_len += 4;

  tor_assert(connected_payload_len <= MAX_CONNECTED_CELL_PAYLOAD_LEN);

  return connected_payload_len;
}

/* This is an onion service client connection: Export the client circuit ID
 * according to the HAProxy proxy protocol. */
STATIC void
export_hs_client_circuit_id(edge_connection_t *edge_conn,
                            hs_circuit_id_protocol_t protocol)
{
  /* We only support HAProxy right now. */
  if (protocol != HS_CIRCUIT_ID_PROTOCOL_HAPROXY)
    return;

  char *buf = NULL;
  const char dst_ipv6[] = "::1";
  /* See RFC4193 regarding fc00::/7 */
  const char src_ipv6_prefix[] = "fc00:dead:beef:4dad:";
  uint16_t dst_port = 0;
  uint16_t src_port = 1; /* default value */
  uint32_t gid = 0; /* default value */

  /* Generate a GID and source port for this client */
  if (edge_conn->on_circuit != NULL) {
    gid = TO_ORIGIN_CIRCUIT(edge_conn->on_circuit)->global_identifier;
    src_port = gid & 0x0000ffff;
  }

  /* Grab the original dest port from the hs ident */
  if (edge_conn->hs_ident) {
    dst_port = edge_conn->hs_ident->orig_virtual_port;
  }

  /* Build the string */
  tor_asprintf(&buf, "PROXY TCP6 %s:%x:%x %s %d %d\r\n",
               src_ipv6_prefix,
               gid >> 16, gid & 0x0000ffff,
               dst_ipv6, src_port, dst_port);

  connection_buf_add(buf, strlen(buf), TO_CONN(edge_conn));

  tor_free(buf);
}

/** Connected handler for exit connections: start writing pending
 * data, deliver 'CONNECTED' relay cells as appropriate, and check
 * any pending data that may have been received. */
int
connection_edge_finished_connecting(edge_connection_t *edge_conn)
{
  connection_t *conn;

  tor_assert(edge_conn);
  tor_assert(edge_conn->base_.type == CONN_TYPE_EXIT);
  conn = TO_CONN(edge_conn);
  tor_assert(conn->state == EXIT_CONN_STATE_CONNECTING);

  log_info(LD_EXIT,"Exit connection to %s:%u (%s) established.",
           escaped_safe_str(conn->address), conn->port,
           safe_str(fmt_and_decorate_addr(&conn->addr)));

  rep_hist_note_exit_stream_opened(conn->port);

  conn->state = EXIT_CONN_STATE_OPEN;

  connection_watch_events(conn, READ_EVENT); /* stop writing, keep reading */
  if (connection_get_outbuf_len(conn)) /* in case there are any queued relay
                                        * cells */
    connection_start_writing(conn);
  /* deliver a 'connected' relay cell back through the circuit. */
  if (connection_edge_is_rendezvous_stream(edge_conn)) {
    if (connection_edge_send_command(edge_conn,
                                     RELAY_COMMAND_CONNECTED, NULL, 0) < 0)
      return 0; /* circuit is closed, don't continue */
  } else {
    uint8_t connected_payload[MAX_CONNECTED_CELL_PAYLOAD_LEN];
    int connected_payload_len =
      connected_cell_format_payload(connected_payload, &conn->addr,
                                    edge_conn->address_ttl);
    if (connected_payload_len < 0)
      return -1;

    if (connection_edge_send_command(edge_conn,
                        RELAY_COMMAND_CONNECTED,
                        (char*)connected_payload, connected_payload_len) < 0)
      return 0; /* circuit is closed, don't continue */
  }
  tor_assert(edge_conn->package_window > 0);
  /* in case the server has written anything */
  return connection_edge_process_inbuf(edge_conn, 1);
}

/** A list of all the entry_connection_t * objects that are not marked
 * for close, and are in AP_CONN_STATE_CIRCUIT_WAIT.
 *
 * (Right now, we check in several places to make sure that this list is
 * correct.  When it's incorrect, we'll fix it, and log a BUG message.)
 */
static smartlist_t *pending_entry_connections = NULL;

static int untried_pending_connections = 0;

/**
 * Mainloop event to tell us to scan for pending connections that can
 * be attached.
 */
static mainloop_event_t *attach_pending_entry_connections_ev = NULL;

/** Common code to connection_(ap|exit)_about_to_close. */
static void
connection_edge_about_to_close(edge_connection_t *edge_conn)
{
  if (!edge_conn->edge_has_sent_end) {
    connection_t *conn = TO_CONN(edge_conn);
    log_warn(LD_BUG, "(Harmless.) Edge connection (marked at %s:%d) "
             "hasn't sent end yet?",
             conn->marked_for_close_file, conn->marked_for_close);
    tor_fragile_assert();
  }
}

/** Called when we're about to finally unlink and free an AP (client)
 * connection: perform necessary accounting and cleanup */
void
connection_ap_about_to_close(entry_connection_t *entry_conn)
{
  circuit_t *circ;
  edge_connection_t *edge_conn = ENTRY_TO_EDGE_CONN(entry_conn);
  connection_t *conn = ENTRY_TO_CONN(entry_conn);

  connection_edge_about_to_close(edge_conn);

  if (entry_conn->socks_request->has_finished == 0) {
    /* since conn gets removed right after this function finishes,
     * there's no point trying to send back a reply at this point. */
    log_warn(LD_BUG,"Closing stream (marked at %s:%d) without sending"
             " back a socks reply.",
             conn->marked_for_close_file, conn->marked_for_close);
  }
  if (!edge_conn->end_reason) {
    log_warn(LD_BUG,"Closing stream (marked at %s:%d) without having"
             " set end_reason.",
             conn->marked_for_close_file, conn->marked_for_close);
  }
  if (entry_conn->dns_server_request) {
    log_warn(LD_BUG,"Closing stream (marked at %s:%d) without having"
             " replied to DNS request.",
             conn->marked_for_close_file, conn->marked_for_close);
    dnsserv_reject_request(entry_conn);