Allow a v4 link protocol for 4-byte circuit IDs.

Implements proposal 214.

Needs testing.

14 files changed, 165 insertions, 87 deletions

diff --git a/src/or/buffers.c b/src/or/buffers.c
index a8d06cef1..b6a21950e 100644
--- a/src/or/buffers.c
+++ b/src/or/buffers.c
@@ -1044,28 +1044,35 @@ cell_command_is_var_length(uint8_t command, int linkproto)
 int
 fetch_var_cell_from_buf(buf_t *buf, var_cell_t **out, int linkproto)
 {
-  char hdr[VAR_CELL_HEADER_SIZE];
+  char hdr[VAR_CELL_MAX_HEADER_SIZE];
   var_cell_t *result;
   uint8_t command;
   uint16_t length;
+  const int wide_circ_ids = linkproto >= MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS;
+  const int circ_id_len = wide_circ_ids ? 4 : 2;
+  const unsigned header_len = wide_circ_ids ? VAR_CELL_MAX_HEADER_SIZE :
+    VAR_CELL_MAX_HEADER_SIZE - 2;
   check();
   *out = NULL;
-  if (buf->datalen < VAR_CELL_HEADER_SIZE)
+  if (buf->datalen < header_len)
     return 0;
   peek_from_buf(hdr, sizeof(hdr), buf);
 
-  command = get_uint8(hdr+2);
+  command = get_uint8(hdr + circ_id_len);
   if (!(cell_command_is_var_length(command, linkproto)))
     return 0;
 
-  length = ntohs(get_uint16(hdr+3));
-  if (buf->datalen < (size_t)(VAR_CELL_HEADER_SIZE+length))
+  length = ntohs(get_uint16(hdr + circ_id_len + 1));
+  if (buf->datalen < (size_t)(header_len+length))
     return 1;
   result = var_cell_new(length);
   result->command = command;
-  result->circ_id = ntohs(get_uint16(hdr));
+  if (wide_circ_ids)
+    result->circ_id = ntohl(get_uint32(hdr));
+  else
+    result->circ_id = ntohs(get_uint16(hdr));
 
-  buf_remove_from_front(buf, VAR_CELL_HEADER_SIZE);
+  buf_remove_from_front(buf, header_len);
   peek_from_buf((char*) result->payload, length, buf);
   buf_remove_from_front(buf, length);
   check();
@@ -1124,30 +1131,37 @@ fetch_var_cell_from_evbuffer(struct evbuffer *buf, var_cell_t **out,
   uint16_t cell_length;
   var_cell_t *cell;
   int result = 0;
+  const int wide_circ_ids = linkproto >= MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS;
+  const int circ_id_len = wide_circ_ids ? 4 : 2;
+  const unsigned header_len = wide_circ_ids ? VAR_CELL_MAX_HEADER_SIZE :
+    VAR_CELL_MAX_HEADER_SIZE - 2;
 
   *out = NULL;
   buf_len = evbuffer_get_length(buf);
-  if (buf_len < VAR_CELL_HEADER_SIZE)
+  if (buf_len < header_len)
     return 0;
 
-  n = inspect_evbuffer(buf, &hdr, VAR_CELL_HEADER_SIZE, &free_hdr, NULL);
-  tor_assert(n >= VAR_CELL_HEADER_SIZE);
+  n = inspect_evbuffer(buf, &hdr, header_len, &free_hdr, NULL);
+  tor_assert(n >= header_len);
 
-  command = get_uint8(hdr+2);
+  command = get_uint8(hdr + circ_id_len);
   if (!(cell_command_is_var_length(command, linkproto))) {
     goto done;
   }
 
-  cell_length = ntohs(get_uint16(hdr+3));
-  if (buf_len < (size_t)(VAR_CELL_HEADER_SIZE+cell_length)) {
+  cell_length = ntohs(get_uint16(hdr + circ_id_len + 1));
+  if (buf_len < (size_t)(header_len+cell_length)) {
     result = 1; /* Not all here yet. */
     goto done;
   }
 
   cell = var_cell_new(cell_length);
   cell->command = command;
-  cell->circ_id = ntohs(get_uint16(hdr));
-  evbuffer_drain(buf, VAR_CELL_HEADER_SIZE);
+  if (wide_circ_ids)
+    cell->circ_id = ntohl(get_uint32(hdr));
+  else
+    cell->circ_id = ntohs(get_uint16(hdr));
+  evbuffer_drain(buf, header_len);
   evbuffer_remove(buf, cell->payload, cell_length);
   *out = cell;
   result = 1;
diff --git a/src/or/channel.h b/src/or/channel.h
index d2106551a..3cfc8b183 100644
--- a/src/or/channel.h
+++ b/src/or/channel.h
@@ -143,6 +143,8 @@ struct channel_s {
    * space should we use?
    */
   circ_id_type_t circ_id_type:2;
+  /** DOCDOC*/
+  unsigned wide_circ_ids:1;
   /*
    * Which circ_id do we try to use next on this connection?  This is
    * always in the range 0..1<<15-1.
diff --git a/src/or/channeltls.c b/src/or/channeltls.c
index d094d15af..4f87eb567 100644
--- a/src/or/channeltls.c
+++ b/src/or/channeltls.c
@@ -600,12 +600,14 @@ channel_tls_write_packed_cell_method(channel_t *chan,
                                      packed_cell_t *packed_cell)
 {
   channel_tls_t *tlschan = BASE_CHAN_TO_TLS(chan);
+  size_t cell_network_size = (chan->wide_circ_ids) ?
+    CELL_MAX_NETWORK_SIZE : CELL_MAX_NETWORK_SIZE - 2;
 
   tor_assert(tlschan);
   tor_assert(packed_cell);
   tor_assert(tlschan->conn);
 
-  connection_write_to_buf(packed_cell->body, CELL_NETWORK_SIZE,
+  connection_write_to_buf(packed_cell->body, cell_network_size,
                           TO_CONN(tlschan->conn));
 
   /* This is where the cell is finished; used to be done from relay.c */
@@ -893,7 +895,7 @@ channel_tls_handle_cell(cell_t *cell, or_connection_t *conn)
   }
 
   if (conn->base_.state == OR_CONN_STATE_OR_HANDSHAKING_V3)
-    or_handshake_state_record_cell(conn->handshake_state, cell, 1);
+    or_handshake_state_record_cell(conn, conn->handshake_state, cell, 1);
 
   switch (cell->command) {
     case CELL_PADDING:
@@ -1032,7 +1034,8 @@ channel_tls_handle_var_cell(var_cell_t *var_cell, or_connection_t *conn)
       break;
     case OR_CONN_STATE_OR_HANDSHAKING_V3:
       if (var_cell->command != CELL_AUTHENTICATE)
-        or_handshake_state_record_var_cell(conn->handshake_state, var_cell, 1);
+        or_handshake_state_record_var_cell(conn, conn->handshake_state,
+                                           var_cell, 1);
       break; /* Everything is allowed */
     case OR_CONN_STATE_OPEN:
       if (conn->link_proto < 3) {
@@ -1152,7 +1155,8 @@ enter_v3_handshake_with_cell(var_cell_t *cell, channel_tls_t *chan)
     connection_or_close_for_error(chan->conn, 0);
     return -1;
   }
-  or_handshake_state_record_var_cell(chan->conn->handshake_state, cell, 1);
+  or_handshake_state_record_var_cell(chan->conn,
+                                     chan->conn->handshake_state, cell, 1);
   return 0;
 }
 
@@ -1223,7 +1227,7 @@ channel_tls_process_versions_cell(var_cell_t *cell, channel_tls_t *chan)
     connection_or_close_for_error(chan->conn, 0);
     return;
   } else if (highest_supported_version < 3 &&
-             chan->conn->base_.state ==  OR_CONN_STATE_OR_HANDSHAKING_V3) {
+             chan->conn->base_.state == OR_CONN_STATE_OR_HANDSHAKING_V3) {
     log_fn(LOG_PROTOCOL_WARN, LD_OR,
            "Negotiated link protocol 2 or lower after doing a v3 TLS "
            "handshake. Closing connection.");
@@ -1292,6 +1296,13 @@ channel_tls_process_versions_cell(var_cell_t *cell, channel_tls_t *chan)
         return;
       }
     }
+
+    /* We set this after sending the verions cell. */
+    /*XXXXX symbolic const.*/
+    chan->base_.wide_circ_ids =
+      chan->conn->link_proto >= MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS;
+    chan->conn->wide_circ_ids = chan->base_.wide_circ_ids;
+
     if (send_certs) {
       if (connection_or_send_certs_cell(chan->conn) < 0) {
         log_warn(LD_OR, "Couldn't send certs cell");
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 1fb93bbd2..7607348b8 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -89,7 +89,7 @@ get_unique_circ_id_by_chan(channel_t *chan)
 {
   circid_t test_circ_id;
   circid_t attempts=0;
-  circid_t high_bit;
+  circid_t high_bit, max_range;
 
   tor_assert(chan);
 
@@ -99,17 +99,17 @@ get_unique_circ_id_by_chan(channel_t *chan)
              "a client with no identity.");
     return 0;
   }
-  high_bit =
-    (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
+  max_range =  (chan->wide_circ_ids) ? (1u<<31) : (1u<<15);
+  high_bit = (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? max_range : 0;
   do {
-    /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
+    /* Sequentially iterate over test_circ_id=1...max_range until we find a
      * circID such that (high_bit|test_circ_id) is not already used. */
     test_circ_id = chan->next_circ_id++;
-    if (test_circ_id == 0 || test_circ_id >= 1<<15) {
+    if (test_circ_id == 0 || test_circ_id >= max_range) {
       test_circ_id = 1;
       chan->next_circ_id = 2;
     }
-    if (++attempts > 1<<15) {
+    if (++attempts > max_range) {
       /* Make sure we don't loop forever if all circ_id's are used. This
        * matters because it's an external DoS opportunity.
        */
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 3ec2bf15b..3db235ae0 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -70,7 +70,7 @@ chan_circid_entries_eq_(chan_circid_circuit_map_t *a,
 static INLINE unsigned int
 chan_circid_entry_hash_(chan_circid_circuit_map_t *a)
 {
-  return (((unsigned)a->circ_id)<<8) ^ (unsigned)(uintptr_t)(a->chan);
+  return ((unsigned)a->circ_id) ^ (unsigned)(uintptr_t)(a->chan);
 }
 
 /** Map from [chan,circid] to circuit. */
diff --git a/src/or/command.c b/src/or/command.c
index 39eccdf82..4007cd600 100644
--- a/src/or/command.c
+++ b/src/or/command.c
@@ -220,7 +220,10 @@ command_process_create_cell(cell_t *cell, channel_t *chan)
 
   /* If the high bit of the circuit ID is not as expected, close the
    * circ. */
-  id_is_high = cell->circ_id & (1<<15);
+  if (chan->wide_circ_ids)
+    id_is_high = cell->circ_id & (1u<<31);
+  else
+    id_is_high = cell->circ_id & (1u<<15);
   if ((id_is_high &&
        chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ||
       (!id_is_high &&
diff --git a/src/or/connection.c b/src/or/connection.c
index 1fbce418a..b89e03cd9 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -2157,8 +2157,7 @@ connection_bucket_round_robin(int base, int priority,
 static ssize_t
 connection_bucket_read_limit(connection_t *conn, time_t now)
 {
-  int base = connection_speaks_cells(conn) ?
-               CELL_NETWORK_SIZE : RELAY_PAYLOAD_SIZE;
+  int base = RELAY_PAYLOAD_SIZE;
   int priority = conn->type != CONN_TYPE_DIR;
   int conn_bucket = -1;
   int global_bucket = global_read_bucket;
@@ -2167,6 +2166,8 @@ connection_bucket_read_limit(connection_t *conn, time_t now)
     or_connection_t *or_conn = TO_OR_CONN(conn);
     if (conn->state == OR_CONN_STATE_OPEN)
       conn_bucket = or_conn->read_bucket;
+    base = or_conn->wide_circ_ids ? CELL_MAX_NETWORK_SIZE :
+      CELL_MAX_NETWORK_SIZE - 2;
   }
 
   if (!connection_is_rate_limited(conn)) {
@@ -2186,8 +2187,7 @@ connection_bucket_read_limit(connection_t *conn, time_t now)
 ssize_t
 connection_bucket_write_limit(connection_t *conn, time_t now)
 {
-  int base = connection_speaks_cells(conn) ?
-               CELL_NETWORK_SIZE : RELAY_PAYLOAD_SIZE;
+  int base = RELAY_PAYLOAD_SIZE;
   int priority = conn->type != CONN_TYPE_DIR;
   int conn_bucket = (int)conn->outbuf_flushlen;
   int global_bucket = global_write_bucket;
@@ -2205,6 +2205,8 @@ connection_bucket_write_limit(connection_t *conn, time_t now)
       if (or_conn->write_bucket < conn_bucket)
         conn_bucket = or_conn->write_bucket >= 0 ?
                         or_conn->write_bucket : 0;
+    base = or_conn->wide_circ_ids ? CELL_MAX_NETWORK_SIZE :
+      CELL_MAX_NETWORK_SIZE - 2;
   }
 
   if (connection_counts_as_relayed_traffic(conn, now) &&
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index 9cd56bb89..11d38f887 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -352,33 +352,55 @@ connection_or_get_num_circuits(or_connection_t *conn)
  * should set it or clear it as appropriate.
  */
 void
-cell_pack(packed_cell_t *dst, const cell_t *src)
+cell_pack(packed_cell_t *dst, const cell_t *src, int wide_circ_ids)
 {
   char *dest = dst->body;
-  set_uint16(dest, htons(src->circ_id));
-  set_uint8(dest+2, src->command);
-  memcpy(dest+3, src->payload, CELL_PAYLOAD_SIZE);
+  if (wide_circ_ids) {
+    set_uint32(dest, htonl(src->circ_id));
+    dest += 4;
+  } else {
+    set_uint16(dest, htons(src->circ_id));
+    dest += 2;
+  }
+  set_uint8(dest, src->command);
+  memcpy(dest+1, src->payload, CELL_PAYLOAD_SIZE);
 }
 
 /** Unpack the network-order buffer <b>src</b> into a host-order
  * cell_t structure <b>dest</b>.
  */
 static void
-cell_unpack(cell_t *dest, const char *src)
+cell_unpack(cell_t *dest, const char *src, int wide_circ_ids)
 {
-  dest->circ_id = ntohs(get_uint16(src));
-  dest->command = get_uint8(src+2);
-  memcpy(dest->payload, src+3, CELL_PAYLOAD_SIZE);
+  if (wide_circ_ids) {
+    dest->circ_id = ntohl(get_uint32(src));
+    src += 4;
+  } else {
+    dest->circ_id = ntohs(get_uint16(src));
+    src += 2;
+  }
+  dest->command = get_uint8(src);
+  memcpy(dest->payload, src+1, CELL_PAYLOAD_SIZE);
 }
 
-/** Write the header of <b>cell</b> into the first VAR_CELL_HEADER_SIZE
- * bytes of <b>hdr_out</b>. */
-void
-var_cell_pack_header(const var_cell_t *cell, char *hdr_out)
+/** Write the header of <b>cell</b> into the first VAR_CELL_MAX_HEADER_SIZE
+ * bytes of <b>hdr_out</b>. Returns number of bytes used. */
+int
+var_cell_pack_header(const var_cell_t *cell, char *hdr_out, int wide_circ_ids)
 {
-  set_uint16(hdr_out, htons(cell->circ_id));
-  set_uint8(hdr_out+2, cell->command);
-  set_uint16(hdr_out+3, htons(cell->payload_len));
+  int r;
+  if (wide_circ_ids) {
+    set_uint32(hdr_out, htonl(cell->circ_id));
+    hdr_out += 4;
+    r = VAR_CELL_MAX_HEADER_SIZE;
+  } else {
+    set_uint16(hdr_out, htons(cell->circ_id));
+    hdr_out += 2;
+    r = VAR_CELL_MAX_HEADER_SIZE - 2;
+  }
+  set_uint8(hdr_out, cell->command);
+  set_uint16(hdr_out+1, htons(cell->payload_len));
+  return r;
 }
 
 /** Allocate and return a new var_cell_t with <b>payload_len</b> bytes of
@@ -498,6 +520,8 @@ connection_or_flushed_some(or_connection_t *conn)
 {
   size_t datalen, temp;
   ssize_t n, flushed;
+  size_t cell_network_size = conn->wide_circ_ids ? CELL_MAX_NETWORK_SIZE :
+    CELL_MAX_NETWORK_SIZE - 2;
 
   /* If we're under the low water mark, add cells until we're just over the
    * high water mark. */
@@ -505,7 +529,7 @@ connection_or_flushed_some(or_connection_t *conn)
   if (datalen < OR_CONN_LOWWATER) {
     while ((conn->chan) && channel_tls_more_to_flush(conn->chan)) {
       /* Compute how many more cells we want at most */
-      n = CEIL_DIV(OR_CONN_HIGHWATER - datalen, CELL_NETWORK_SIZE);
+      n = CEIL_DIV(OR_CONN_HIGHWATER - datalen, cell_network_size);
       /* Bail out if we don't want any more */
       if (n <= 0) break;
       /* We're still here; try to flush some more cells */
@@ -1733,10 +1757,13 @@ or_handshake_state_free(or_handshake_state_t *state)
  * authenticate cell.)
  */
 void
-or_handshake_state_record_cell(or_handshake_state_t *state,
+or_handshake_state_record_cell(or_connection_t *conn,
+                               or_handshake_state_t *state,
                                const cell_t *cell,
                                int incoming)
 {
+  size_t cell_network_size = conn->wide_circ_ids ? CELL_MAX_NETWORK_SIZE :
+    CELL_MAX_NETWORK_SIZE - 2;
   crypto_digest_t *d, **dptr;
   packed_cell_t packed;
   if (incoming) {
@@ -1758,8 +1785,8 @@ or_handshake_state_record_cell(or_handshake_state_t *state,
   d = *dptr;
   /* Re-packing like this is a little inefficient, but we don't have to do
      this very often at all. */
-  cell_pack(&packed, cell);
-  crypto_digest_add_bytes(d, packed.body, sizeof(packed.body));
+  cell_pack(&packed, cell, conn->wide_circ_ids);
+  crypto_digest_add_bytes(d, packed.body, cell_network_size);
   memset(&packed, 0, sizeof(packed));
 }
 
@@ -1772,12 +1799,14 @@ or_handshake_state_record_cell(or_handshake_state_t *state,
  * authenticate cell.)
  */
 void
-or_handshake_state_record_var_cell(or_handshake_state_t *state,
+or_handshake_state_record_var_cell(or_connection_t *conn,
+                                   or_handshake_state_t *state,
                                    const var_cell_t *cell,
                                    int incoming)
 {
   crypto_digest_t *d, **dptr;
-  char buf[VAR_CELL_HEADER_SIZE];
+  int n;
+  char buf[VAR_CELL_MAX_HEADER_SIZE];
   if (incoming) {
     if (!state->digest_received_data)
       return;
@@ -1791,8 +1820,8 @@ or_handshake_state_record_var_cell(or_handshake_state_t *state,
 
   d = *dptr;
 
-  var_cell_pack_header(cell, buf);
-  crypto_digest_add_bytes(d, buf, sizeof(buf));
+  n = var_cell_pack_header(cell, buf, conn->wide_circ_ids);
+  crypto_digest_add_bytes(d, buf, n);
   crypto_digest_add_bytes(d, (const char *)cell->payload, cell->payload_len);
 
   memset(buf, 0, sizeof(buf));
@@ -1826,20 +1855,22 @@ void
 connection_or_write_cell_to_buf(const cell_t *cell, or_connection_t *conn)
 {
   packed_cell_t networkcell;
+  size_t cell_network_size = (conn->wide_circ_ids) ?
+    CELL_MAX_NETWORK_SIZE : CELL_MAX_NETWORK_SIZE - 2;
 
   tor_assert(cell);
   tor_assert(conn);
 
-  cell_pack(&networkcell, cell);
+  cell_pack(&networkcell, cell, conn->wide_circ_ids);
 
-  connection_write_to_buf(networkcell.body, CELL_NETWORK_SIZE, TO_CONN(conn));
+  connection_write_to_buf(networkcell.body, cell_network_size, TO_CONN(conn));
 
   /* Touch the channel's active timestamp if there is one */
   if (conn->chan)
     channel_timestamp_active(TLS_CHAN_TO_BASE(conn->chan));
 
   if (conn->base_.state == OR_CONN_STATE_OR_HANDSHAKING_V3)
-    or_handshake_state_record_cell(conn->handshake_state, cell, 0);
+    or_handshake_state_record_cell(conn, conn->handshake_state, cell, 0);
 
   if (cell->command != CELL_PADDING)
     conn->timestamp_last_added_nonpadding = approx_time();
@@ -1853,15 +1884,16 @@ void
 connection_or_write_var_cell_to_buf(const var_cell_t *cell,
                                     or_connection_t *conn)
 {
-  char hdr[VAR_CELL_HEADER_SIZE];
+  int n;
+  char hdr[VAR_CELL_MAX_HEADER_SIZE];
   tor_assert(cell);
   tor_assert(conn);
-  var_cell_pack_header(cell, hdr);
-  connection_write_to_buf(hdr, sizeof(hdr), TO_CONN(conn));
+  n = var_cell_pack_header(cell, hdr, conn->wide_circ_ids);
+  connection_write_to_buf(hdr, n, TO_CONN(conn));
   connection_write_to_buf((char*)cell->payload,
                           cell->payload_len, TO_CONN(conn));
   if (conn->base_.state == OR_CONN_STATE_OR_HANDSHAKING_V3)
-    or_handshake_state_record_var_cell(conn->handshake_state, cell, 0);
+    or_handshake_state_record_var_cell(conn, conn->handshake_state, cell, 0);
   if (cell->command != CELL_PADDING)
     conn->timestamp_last_added_nonpadding = approx_time();
 
@@ -1913,10 +1945,13 @@ connection_or_process_cells_from_inbuf(or_connection_t *conn)
       channel_tls_handle_var_cell(var_cell, conn);
       var_cell_free(var_cell);
     } else {
-      char buf[CELL_NETWORK_SIZE];
+      const int wide_circ_ids = conn->wide_circ_ids;
+      const size_t cell_network_size = wide_circ_ids ? CELL_MAX_NETWORK_SIZE :
+        CELL_MAX_NETWORK_SIZE - 2;
+      char buf[CELL_MAX_NETWORK_SIZE];
       cell_t cell;
       if (connection_get_inbuf_len(TO_CONN(conn))
-          < CELL_NETWORK_SIZE) /* whole response available? */
+          < cell_network_size) /* whole response available? */
         return 0; /* not yet */
 
       /* Touch the channel's active timestamp if there is one */
@@ -1924,11 +1959,11 @@ connection_or_process_cells_from_inbuf(or_connection_t *conn)
         channel_timestamp_active(TLS_CHAN_TO_BASE(conn->chan));
 
       circuit_build_times_network_is_live(&circ_times);
-      connection_fetch_from_buf(buf, CELL_NETWORK_SIZE, TO_CONN(conn));
+      connection_fetch_from_buf(buf, cell_network_size, TO_CONN(conn));
 
       /* retrieve cell info from buf (create the host-order struct from the
        * network-order string) */
-      cell_unpack(&cell, buf);
+      cell_unpack(&cell, buf, wide_circ_ids);
 
       channel_tls_handle_cell(&cell, conn);
     }
@@ -1936,7 +1971,7 @@ connection_or_process_cells_from_inbuf(or_connection_t *conn)
 }
 
 /** Array of recognized link protocol versions. */
-static const uint16_t or_protocol_versions[] = { 1, 2, 3 };
+static const uint16_t or_protocol_versions[] = { 1, 2, 3, 4 };
 /** Number of versions in <b>or_protocol_versions</b>. */
 static const int n_or_protocol_versions =
   (int)( sizeof(or_protocol_versions)/sizeof(uint16_t) );
diff --git a/src/or/connection_or.h b/src/or/connection_or.h
index 727de211b..c0f8ec1ee 100644
--- a/src/or/connection_or.h
+++ b/src/or/connection_or.h
@@ -60,10 +60,12 @@ int connection_or_client_learned_peer_id(or_connection_t *conn,
 time_t connection_or_client_used(or_connection_t *conn);
 int connection_or_get_num_circuits(or_connection_t *conn);
 void or_handshake_state_free(or_handshake_state_t *state);
-void or_handshake_state_record_cell(or_handshake_state_t *state,
+void or_handshake_state_record_cell(or_connection_t *conn,
+                                    or_handshake_state_t *state,
                                     const cell_t *cell,
                                     int incoming);
-void or_handshake_state_record_var_cell(or_handshake_state_t *state,
+void or_handshake_state_record_var_cell(or_connection_t *conn,
+                                        or_handshake_state_t *state,
                                         const var_cell_t *cell,
                                         int incoming);
 
@@ -84,10 +86,14 @@ int connection_or_send_authenticate_cell(or_connection_t *conn, int type);
 
 int is_or_protocol_version_known(uint16_t version);
 
-void cell_pack(packed_cell_t *dest, const cell_t *src);
-void var_cell_pack_header(const var_cell_t *cell, char *hdr_out);
+void cell_pack(packed_cell_t *dest, const cell_t *src, int wide_circ_ids);
+int var_cell_pack_header(const var_cell_t *cell, char *hdr_out,
+                         int wide_circ_ids);
 var_cell_t *var_cell_new(uint16_t payload_len);
 void var_cell_free(var_cell_t *cell);
 
+/** DOCDOC */
+#define MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS 4
+
 #endif
 
diff --git a/src/or/cpuworker.c b/src/or/cpuworker.c
index 119892d71..a25a8a780 100644
--- a/src/or/cpuworker.c
+++ b/src/or/cpuworker.c
@@ -31,7 +31,7 @@
 #define MIN_CPUWORKERS 1
 
 /** The tag specifies which circuit this onionskin was from. */
-#define TAG_LEN 10
+#define TAG_LEN 12
 /** How many bytes are sent from the cpuworker back to tor? */
 #define LEN_ONION_RESPONSE \
   (1+TAG_LEN+ONIONSKIN_REPLY_LEN+CPATH_KEY_MATERIAL_LEN)
@@ -75,7 +75,7 @@ tag_pack(char *tag, uint64_t chan_id, circid_t circ_id)
   /*XXXX RETHINK THIS WHOLE MESS !!!! !NM NM NM NM*/
   /*XXXX DOUBLEPLUSTHIS!!!! AS AS AS AS*/
   set_uint64(tag, chan_id);
-  set_uint16(tag+8, circ_id);
+  set_uint32(tag+8, circ_id);
 }
 
 /** Unpack <b>tag</b> into addr, port, and circ_id.
@@ -84,7 +84,7 @@ static void
 tag_unpack(const char *tag, uint64_t *chan_id, circid_t *circ_id)
 {
   *chan_id = get_uint64(tag);
-  *circ_id = get_uint16(tag+8);
+  *circ_id = get_uint32(tag+8);
 }
 
 /** Called when the onion key has changed and we need to spawn new
diff --git a/src/or/or.h b/src/or/or.h
index 6510725f6..736438e6e 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -862,11 +862,12 @@ typedef enum {
 
 /** Number of bytes in a cell, minus cell header. */
 #define CELL_PAYLOAD_SIZE 509
-/** Number of bytes in a cell transmitted over the network. */
-#define CELL_NETWORK_SIZE 512
+/** Number of bytes in a cell transmitted over the network, in the longest
+ * form */
+#define CELL_MAX_NETWORK_SIZE 514
 
-/** Length of a header on a variable-length cell. */
-#define VAR_CELL_HEADER_SIZE 5
+/** Maximum length of a header on a variable-length cell. */
+#define VAR_CELL_MAX_HEADER_SIZE 7
 
 /** Number of bytes in a relay cell's header (not including general cell
  * header). */
@@ -875,7 +876,7 @@ typedef enum {
 #define RELAY_PAYLOAD_SIZE (CELL_PAYLOAD_SIZE-RELAY_HEADER_SIZE)
 
 /** Identifies a circuit on an or_connection */
-typedef uint16_t circid_t;
+typedef uint32_t circid_t;
 /** Identifies a stream on a circuit */
 typedef uint16_t streamid_t;
 
@@ -1044,7 +1045,7 @@ typedef struct var_cell_t {
 /** A cell as packed for writing to the network. */
 typedef struct packed_cell_t {
   struct packed_cell_t *next; /**< Next cell queued on this circuit. */
-  char body[CELL_NETWORK_SIZE]; /**< Cell as packed for network. */
+  char body[CELL_MAX_NETWORK_SIZE]; /**< Cell as packed for network. */
 } packed_cell_t;
 
 /** Number of cells added to a circuit queue including their insertion
@@ -1363,6 +1364,7 @@ typedef struct or_connection_t {
   /** True iff this is an outgoing connection. */
   unsigned int is_outgoing:1;
   unsigned int proxy_type:2; /**< One of PROXY_NONE...PROXY_SOCKS5 */
+  unsigned int wide_circ_ids:1;
   uint8_t link_proto; /**< What protocol version are we using? 0 for
                        * "none negotiated yet." */
 
diff --git a/src/or/relay.c b/src/or/relay.c
index bd99d91dc..b1e4bfb8f 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -1870,10 +1870,10 @@ dump_cell_pool_usage(int severity)
 
 /** Allocate a new copy of packed <b>cell</b>. */
 static INLINE packed_cell_t *
-packed_cell_copy(const cell_t *cell)
+packed_cell_copy(const cell_t *cell, int wide_circ_ids)
 {
   packed_cell_t *c = packed_cell_new();
-  cell_pack(c, cell);
+  cell_pack(c, cell, wide_circ_ids);
   c->next = NULL;
   return c;
 }
@@ -1895,9 +1895,10 @@ cell_queue_append(cell_queue_t *queue, packed_cell_t *cell)
 
 /** Append a newly allocated copy of <b>cell</b> to the end of <b>queue</b> */
 void
-cell_queue_append_packed_copy(cell_queue_t *queue, const cell_t *cell)
+cell_queue_append_packed_copy(cell_queue_t *queue, const cell_t *cell,
+                              int wide_circ_ids)
 {
-  packed_cell_t *copy = packed_cell_copy(cell);
+  packed_cell_t *copy = packed_cell_copy(cell, wide_circ_ids);
   /* Remember the time when this cell was put in the queue. */
   if (get_options()->CellStatistics) {
     struct timeval now;
@@ -2224,7 +2225,7 @@ append_cell_to_circuit_queue(circuit_t *circ, channel_t *chan,
     streams_blocked = circ->streams_blocked_on_p_chan;
   }
 
-  cell_queue_append_packed_copy(queue, cell);
+  cell_queue_append_packed_copy(queue, cell, chan->wide_circ_ids);
 
   /* If we have too many cells on the circuit, we should stop reading from
    * the edge streams for a while. */
diff --git a/src/or/relay.h b/src/or/relay.h
index 3906d6bf8..96c2a9dbb 100644
--- a/src/or/relay.h
+++ b/src/or/relay.h
@@ -46,7 +46,8 @@ void packed_cell_free(packed_cell_t *cell);
 
 void cell_queue_clear(cell_queue_t *queue);
 void cell_queue_append(cell_queue_t *queue, packed_cell_t *cell);
-void cell_queue_append_packed_copy(cell_queue_t *queue, const cell_t *cell);
+void cell_queue_append_packed_copy(cell_queue_t *queue, const cell_t *cell,
+                                   int wide_circ_ids);
 
 void append_cell_to_circuit_queue(circuit_t *circ, channel_t *chan,
                                   cell_t *cell, cell_direction_t direction,
diff --git a/src/or/router.c b/src/or/router.c
index 1cac63a3a..562704f14 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -1002,7 +1002,8 @@ router_dirport_found_reachable(void)
 void
 router_perform_bandwidth_test(int num_circs, time_t now)
 {
-  int num_cells = (int)(get_options()->BandwidthRate * 10 / CELL_NETWORK_SIZE);
+  int num_cells = (int)(get_options()->BandwidthRate * 10 /
+                        CELL_MAX_NETWORK_SIZE);
   int max_cells = num_cells < CIRCWINDOW_START ?
                     num_cells : CIRCWINDOW_START;
   int cells_per_circuit = max_cells / num_circs;