relay.c 110 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
2
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
3
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4
 * Copyright (c) 2007-2017, The Tor Project, Inc. */
5
6
7
8
/* See LICENSE for licensing information */

/**
 * \file relay.c
9
 * \brief Handle relay cell encryption/decryption, plus packaging and
Nick Mathewson's avatar
Nick Mathewson committed
10
 *    receiving from circuits, plus queuing on circuits.
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 *
 * This is a core modules that makes Tor work. It's responsible for
 * dealing with RELAY cells (the ones that travel more than one hop along a
 * circuit), by:
 *  <ul>
 *   <li>constructing relays cells,
 *   <li>encrypting relay cells,
 *   <li>decrypting relay cells,
 *   <li>demultiplexing relay cells as they arrive on a connection,
 *   <li>queueing relay cells for retransmission,
 *   <li>or handling relay cells that are for us to receive (as an exit or a
 *   client).
 *  </ul>
 *
 * RELAY cells are generated throughout the code at the client or relay side,
 * using relay_send_command_from_edge() or one of the functions like
 * connection_edge_send_command() that calls it.  Of particular interest is
 * connection_edge_package_raw_inbuf(), which takes information that has
 * arrived on an edge connection socket, and packages it as a RELAY_DATA cell
 * -- this is how information is actually sent across the Tor network.  The
 * cryptography for these functions is handled deep in
 * circuit_package_relay_cell(), which either adds a single layer of
 * encryption (if we're an exit), or multiple layers (if we're the origin of
 * the circuit).  After construction and encryption, the RELAY cells are
 * passed to append_cell_to_circuit_queue(), which queues them for
 * transmission and tells the circuitmux (see circuitmux.c) that the circuit
 * is waiting to send something.
 *
 * Incoming RELAY cells arrive at circuit_receive_relay_cell(), called from
 * command.c.  There they are decrypted and, if they are for us, are passed to
 * connection_edge_process_relay_cell(). If they're not for us, they're
 * re-queued for retransmission again with append_cell_to_circuit_queue().
 *
 * The connection_edge_process_relay_cell() function handles all the different
 * types of relay cells, launching requests or transmitting data as needed.
46
47
 **/

48
#define RELAY_PRIVATE
49
#include "or.h"
50
#include "addressmap.h"
51
#include "backtrace.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
52
#include "buffers.h"
53
#include "channel.h"
54
#include "circpathbias.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
55
#include "circuitbuild.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
56
#include "circuitlist.h"
57
#include "circuituse.h"
58
#include "compress.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
59
#include "config.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
60
#include "connection.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
61
#include "connection_edge.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
62
#include "connection_or.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
63
#include "control.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
64
#include "geoip.h"
65
#include "hs_cache.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
66
#include "main.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
67
#include "networkstatus.h"
68
#include "nodelist.h"
69
#include "onion.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
70
#include "policies.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
71
#include "reasons.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
72
#include "relay.h"
73
#include "rendcache.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
74
#include "rendcommon.h"
75
#include "router.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
76
#include "routerlist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
77
#include "routerparse.h"
78
#include "scheduler.h"
79
#include "rephist.h"
80

81
static edge_connection_t *relay_lookup_conn(circuit_t *circ, cell_t *cell,
82
                                            cell_direction_t cell_direction,
83
                                            crypt_path_t *layer_hint);
84

85
86
87
88
89
90
91
92
93
94
95
96
static int connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ,
                                              edge_connection_t *conn,
                                              crypt_path_t *layer_hint);
static void circuit_consider_sending_sendme(circuit_t *circ,
                                            crypt_path_t *layer_hint);
static void circuit_resume_edge_reading(circuit_t *circ,
                                        crypt_path_t *layer_hint);
static int circuit_resume_edge_reading_helper(edge_connection_t *conn,
                                              circuit_t *circ,
                                              crypt_path_t *layer_hint);
static int circuit_consider_stop_edge_reading(circuit_t *circ,
                                              crypt_path_t *layer_hint);
97
static int circuit_queue_streams_are_blocked(circuit_t *circ);
98
99
100
101
static void adjust_exit_policy_from_exitpolicy_failure(origin_circuit_t *circ,
                                                  entry_connection_t *conn,
                                                  node_t *node,
                                                  const tor_addr_t *addr);
102
#if 0
103
static int get_max_middle_cells(void);
104
#endif
105

106
107
108
109
110
111
112
/** Stop reading on edge connections when we have this many cells
 * waiting on the appropriate queue. */
#define CELL_QUEUE_HIGHWATER_SIZE 256
/** Start reading from edge connections again when we get down to this many
 * cells. */
#define CELL_QUEUE_LOWWATER_SIZE 64

113
114
115
/** Stats: how many relay cells have originated at this hop, or have
 * been relayed onward (not recognized at this hop)?
 */
116
uint64_t stats_n_relay_cells_relayed = 0;
117
118
119
/** Stats: how many relay cells have been delivered to streams at this
 * hop?
 */
120
uint64_t stats_n_relay_cells_delivered = 0;
121

122
123
124
/** Used to tell which stream to read from first on a circuit. */
static tor_weak_rng_t stream_choice_rng = TOR_WEAK_RNG_INIT;

125
126
127
/** Update digest from the payload of cell. Assign integrity part to
 * cell.
 */
128
static void
129
relay_set_digest(crypto_digest_t *digest, cell_t *cell)
130
{
131
132
133
  char integrity[4];
  relay_header_t rh;

Nick Mathewson's avatar
Nick Mathewson committed
134
  crypto_digest_add_bytes(digest, (char*)cell->payload, CELL_PAYLOAD_SIZE);
135
136
137
138
139
140
141
142
143
144
145
146
147
148
  crypto_digest_get_digest(digest, integrity, 4);
//  log_fn(LOG_DEBUG,"Putting digest of %u %u %u %u into relay cell.",
//    integrity[0], integrity[1], integrity[2], integrity[3]);
  relay_header_unpack(&rh, cell->payload);
  memcpy(rh.integrity, integrity, 4);
  relay_header_pack(cell->payload, &rh);
}

/** Does the digest for this circuit indicate that this cell is for us?
 *
 * Update digest from the payload of cell (with the integrity part set
 * to 0). If the integrity part is valid, return 1, else restore digest
 * and cell to their original state and return 0.
 */
149
static int
150
relay_digest_matches(crypto_digest_t *digest, cell_t *cell)
151
{
152
  uint32_t received_integrity, calculated_integrity;
153
  relay_header_t rh;
154
  crypto_digest_checkpoint_t backup_digest;
155

156
  crypto_digest_checkpoint(&backup_digest, digest);
157
158

  relay_header_unpack(&rh, cell->payload);
159
  memcpy(&received_integrity, rh.integrity, 4);
160
161
162
163
164
165
166
  memset(rh.integrity, 0, 4);
  relay_header_pack(cell->payload, &rh);

//  log_fn(LOG_DEBUG,"Reading digest of %u %u %u %u from relay cell.",
//    received_integrity[0], received_integrity[1],
//    received_integrity[2], received_integrity[3]);

Nick Mathewson's avatar
Nick Mathewson committed
167
  crypto_digest_add_bytes(digest, (char*) cell->payload, CELL_PAYLOAD_SIZE);
168
  crypto_digest_get_digest(digest, (char*) &calculated_integrity, 4);
169

170
171
  int rv = 1;

172
  if (calculated_integrity != received_integrity) {
173
174
175
//    log_fn(LOG_INFO,"Recognized=0 but bad digest. Not recognizing.");
// (%d vs %d).", received_integrity, calculated_integrity);
    /* restore digest to its old form */
176
    crypto_digest_restore(digest, &backup_digest);
177
    /* restore the relay header */
178
    memcpy(rh.integrity, &received_integrity, 4);
179
    relay_header_pack(cell->payload, &rh);
180
    rv = 0;
181
  }
182
183
184

  memwipe(&backup_digest, 0, sizeof(backup_digest));
  return rv;
185
186
187
188
189
}

/** Apply <b>cipher</b> to CELL_PAYLOAD_SIZE bytes of <b>in</b>
 * (in place).
 *
190
 * Note that we use the same operation for encrypting and for decrypting.
191
 */
192
193
static void
relay_crypt_one_payload(crypto_cipher_t *cipher, uint8_t *in)
194
{
195
  crypto_cipher_crypt_inplace(cipher, (char*) in, CELL_PAYLOAD_SIZE);
196
197
}

198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
/**
 * Update channel usage state based on the type of relay cell and
 * circuit properties.
 *
 * This is needed to determine if a client channel is being
 * used for application traffic, and if a relay channel is being
 * used for multihop circuits and application traffic. The decision
 * to pad in channelpadding.c depends upon this info (as well as
 * consensus parameters) to decide what channels to pad.
 */
static void
circuit_update_channel_usage(circuit_t *circ, cell_t *cell)
{
  if (CIRCUIT_IS_ORIGIN(circ)) {
    /*
     * The client state was first set much earlier in
     * circuit_send_next_onion_skin(), so we can start padding as early as
     * possible.
     *
     * However, if padding turns out to be expensive, we may want to not do
     * it until actual application traffic starts flowing (which is controlled
     * via consensus param nf_pad_before_usage).
     *
     * So: If we're an origin circuit and we've created a full length circuit,
     * then any CELL_RELAY cell means application data. Increase the usage
     * state of the channel to indicate this.
     *
     * We want to wait for CELL_RELAY specifically here, so we know that
     * the channel was definitely being used for data and not for extends.
     * By default, we pad as soon as a channel has been used for *any*
     * circuits, so this state is irrelevant to the padding decision in
     * the default case. However, if padding turns out to be expensive,
     * we would like the ability to avoid padding until we're absolutely
     * sure that a channel is used for enough application data to be worth
     * padding.
     *
     * (So it does not matter that CELL_RELAY_EARLY can actually contain
     * application data. This is only a load reducing option and that edge
     * case does not matter if we're desperately trying to reduce overhead
     * anyway. See also consensus parameter nf_pad_before_usage).
     */
    if (BUG(!circ->n_chan))
      return;

    if (circ->n_chan->channel_usage == CHANNEL_USED_FOR_FULL_CIRCS &&
        cell->command == CELL_RELAY) {
      circ->n_chan->channel_usage = CHANNEL_USED_FOR_USER_TRAFFIC;
    }
  } else {
    /* If we're a relay circuit, the question is more complicated. Basically:
     * we only want to pad connections that carry multihop (anonymous)
     * circuits.
     *
     * We assume we're more than one hop if either the previous hop
     * is not a client, or if the previous hop is a client and there's
     * a next hop. Then, circuit traffic starts at RELAY_EARLY, and
     * user application traffic starts when we see RELAY cells.
     */
    or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);

    if (BUG(!or_circ->p_chan))
      return;

261
262
    if (!channel_is_client(or_circ->p_chan) ||
        (channel_is_client(or_circ->p_chan) && circ->n_chan)) {
263
264
265
266
267
268
269
270
271
272
273
      if (cell->command == CELL_RELAY_EARLY) {
        if (or_circ->p_chan->channel_usage < CHANNEL_USED_FOR_FULL_CIRCS) {
          or_circ->p_chan->channel_usage = CHANNEL_USED_FOR_FULL_CIRCS;
        }
      } else if (cell->command == CELL_RELAY) {
        or_circ->p_chan->channel_usage = CHANNEL_USED_FOR_USER_TRAFFIC;
      }
    }
  }
}

274
/** Receive a relay cell:
275
276
 *  - Crypt it (encrypt if headed toward the origin or if we <b>are</b> the
 *    origin; decrypt if we're headed toward the exit).
277
 *  - Check if recognized (if exitward).
278
279
 *  - If recognized and the digest checks out, then find if there's a stream
 *    that the cell is intended for, and deliver it to the right
280
 *    connection_edge.
281
282
 *  - If not recognized, then we need to relay it: append it to the appropriate
 *    cell_queue on <b>circ</b>.
283
 *
284
 * Return -<b>reason</b> on failure.
285
 */
286
int
287
288
circuit_receive_relay_cell(cell_t *cell, circuit_t *circ,
                           cell_direction_t cell_direction)
289
{
290
  channel_t *chan = NULL;
291
292
  crypt_path_t *layer_hint=NULL;
  char recognized=0;
293
  int reason;
294

295
296
297
298
  tor_assert(cell);
  tor_assert(circ);
  tor_assert(cell_direction == CELL_DIRECTION_OUT ||
             cell_direction == CELL_DIRECTION_IN);
299
300
301
  if (circ->marked_for_close)
    return 0;

302
  if (relay_crypt(circ, cell, cell_direction, &layer_hint, &recognized) < 0) {
303
304
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "relay crypt failed. Dropping connection.");
305
    return -END_CIRC_REASON_INTERNAL;
306
307
  }

308
309
  circuit_update_channel_usage(circ, cell);

310
  if (recognized) {
311
312
313
314
315
316
317
318
319
320
    edge_connection_t *conn = NULL;

    if (circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING) {
      pathbias_check_probe_response(circ, cell);

      /* We need to drop this cell no matter what to avoid code that expects
       * a certain purpose (such as the hidserv code). */
      return 0;
    }

321
    conn = relay_lookup_conn(circ, cell, cell_direction, layer_hint);
322
    if (cell_direction == CELL_DIRECTION_OUT) {
323
      ++stats_n_relay_cells_delivered;
324
      log_debug(LD_OR,"Sending away from origin.");
325
326
      if ((reason=connection_edge_process_relay_cell(cell, circ, conn, NULL))
          < 0) {
327
        log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
328
329
               "connection_edge_process_relay_cell (away from origin) "
               "failed.");
330
        return reason;
331
332
      }
    }
333
    if (cell_direction == CELL_DIRECTION_IN) {
334
      ++stats_n_relay_cells_delivered;
335
      log_debug(LD_OR,"Sending to origin.");
336
337
      if ((reason = connection_edge_process_relay_cell(cell, circ, conn,
                                                       layer_hint)) < 0) {
338
339
340
341
342
343
344
        /* If a client is trying to connect to unknown hidden service port,
         * END_CIRC_AT_ORIGIN is sent back so we can then close the circuit.
         * Do not log warn as this is an expected behavior for a service. */
        if (reason != END_CIRC_AT_ORIGIN) {
          log_warn(LD_OR,
                   "connection_edge_process_relay_cell (at origin) failed.");
        }
345
        return reason;
346
347
348
349
350
351
      }
    }
    return 0;
  }

  /* not recognized. pass it on. */
352
  if (cell_direction == CELL_DIRECTION_OUT) {
353
    cell->circ_id = circ->n_circ_id; /* switch it */
354
    chan = circ->n_chan;
355
356
  } else if (! CIRCUIT_IS_ORIGIN(circ)) {
    cell->circ_id = TO_OR_CIRCUIT(circ)->p_circ_id; /* switch it */
357
    chan = TO_OR_CIRCUIT(circ)->p_chan;
358
  } else {
359
360
    log_fn(LOG_PROTOCOL_WARN, LD_OR,
           "Dropping unrecognized inbound cell on origin circuit.");
361
362
363
364
365
366
367
368
369
    /* If we see unrecognized cells on path bias testing circs,
     * it's bad mojo. Those circuits need to die.
     * XXX: Shouldn't they always die? */
    if (circ->purpose == CIRCUIT_PURPOSE_PATH_BIAS_TESTING) {
      TO_ORIGIN_CIRCUIT(circ)->path_state = PATH_STATE_USE_FAILED;
      return -END_CIRC_REASON_TORPROTOCOL;
    } else {
      return 0;
    }
370
371
  }

372
  if (!chan) {
373
374
375
376
    // XXXX Can this splice stuff be done more cleanly?
    if (! CIRCUIT_IS_ORIGIN(circ) &&
        TO_OR_CIRCUIT(circ)->rend_splice &&
        cell_direction == CELL_DIRECTION_OUT) {
377
      or_circuit_t *splice_ = TO_OR_CIRCUIT(circ)->rend_splice;
378
      tor_assert(circ->purpose == CIRCUIT_PURPOSE_REND_ESTABLISHED);
379
380
      tor_assert(splice_->base_.purpose == CIRCUIT_PURPOSE_REND_ESTABLISHED);
      cell->circ_id = splice_->p_circ_id;
381
      cell->command = CELL_RELAY; /* can't be relay_early anyway */
382
      if ((reason = circuit_receive_relay_cell(cell, TO_CIRCUIT(splice_),
383
                                               CELL_DIRECTION_IN)) < 0) {
384
385
        log_warn(LD_REND, "Error relaying cell across rendezvous; closing "
                 "circuits");
386
        /* XXXX Do this here, or just return -1? */
387
388
        circuit_mark_for_close(circ, -reason);
        return reason;
389
390
391
      }
      return 0;
    }
392
393
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "Didn't recognize cell, but circ stops here! Closing circ.");
394
    return -END_CIRC_REASON_TORPROTOCOL;
395
396
  }

397
  log_debug(LD_OR,"Passing on unrecognized cell.");
398
399
400
401
402

  ++stats_n_relay_cells_relayed; /* XXXX no longer quite accurate {cells}
                                  * we might kill the circ before we relay
                                  * the cells. */

403
  append_cell_to_circuit_queue(circ, chan, cell, cell_direction, 0);
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
  return 0;
}

/** Do the appropriate en/decryptions for <b>cell</b> arriving on
 * <b>circ</b> in direction <b>cell_direction</b>.
 *
 * If cell_direction == CELL_DIRECTION_IN:
 *   - If we're at the origin (we're the OP), for hops 1..N,
 *     decrypt cell. If recognized, stop.
 *   - Else (we're not the OP), encrypt one hop. Cell is not recognized.
 *
 * If cell_direction == CELL_DIRECTION_OUT:
 *   - decrypt one hop. Check if recognized.
 *
 * If cell is recognized, set *recognized to 1, and set
 * *layer_hint to the hop that recognized it.
 *
 * Return -1 to indicate that we should mark the circuit for close,
 * else return 0.
 */
424
int
425
relay_crypt(circuit_t *circ, cell_t *cell, cell_direction_t cell_direction,
426
427
            crypt_path_t **layer_hint, char *recognized)
{
428
429
  relay_header_t rh;

430
431
432
433
434
  tor_assert(circ);
  tor_assert(cell);
  tor_assert(recognized);
  tor_assert(cell_direction == CELL_DIRECTION_IN ||
             cell_direction == CELL_DIRECTION_OUT);
435

436
437
  if (cell_direction == CELL_DIRECTION_IN) {
    if (CIRCUIT_IS_ORIGIN(circ)) { /* We're at the beginning of the circuit.
438
                                    * We'll want to do layered decrypts. */
439
440
      crypt_path_t *thishop, *cpath = TO_ORIGIN_CIRCUIT(circ)->cpath;
      thishop = cpath;
441
      if (thishop->state != CPATH_STATE_OPEN) {
442
443
        log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
               "Relay cell before first created cell? Closing.");
444
445
446
447
448
        return -1;
      }
      do { /* Remember: cpath is in forward order, that is, first hop first. */
        tor_assert(thishop);

449
450
        /* decrypt one layer */
        relay_crypt_one_payload(thishop->b_crypto, cell->payload);
451
452

        relay_header_unpack(&rh, cell->payload);
453
        if (rh.recognized == 0) {
454
          /* it's possibly recognized. have to check digest to be sure. */
455
          if (relay_digest_matches(thishop->b_digest, cell)) {
456
457
458
459
460
461
462
            *recognized = 1;
            *layer_hint = thishop;
            return 0;
          }
        }

        thishop = thishop->next;
463
      } while (thishop != cpath && thishop->state == CPATH_STATE_OPEN);
464
465
      log_fn(LOG_PROTOCOL_WARN, LD_OR,
             "Incoming cell at client not recognized. Closing.");
466
      return -1;
467
468
469
    } else {
      /* We're in the middle. Encrypt one layer. */
      relay_crypt_one_payload(TO_OR_CIRCUIT(circ)->p_crypto, cell->payload);
470
471
    }
  } else /* cell_direction == CELL_DIRECTION_OUT */ {
472
    /* We're in the middle. Decrypt one layer. */
473

474
    relay_crypt_one_payload(TO_OR_CIRCUIT(circ)->n_crypto, cell->payload);
475
476
477
478

    relay_header_unpack(&rh, cell->payload);
    if (rh.recognized == 0) {
      /* it's possibly recognized. have to check digest to be sure. */
479
      if (relay_digest_matches(TO_OR_CIRCUIT(circ)->n_digest, cell)) {
480
481
482
483
484
485
486
487
        *recognized = 1;
        return 0;
      }
    }
  }
  return 0;
}

488
/** Package a relay cell from an edge:
489
 *  - Encrypt it to the right layer
490
 *  - Append it to the appropriate cell_queue on <b>circ</b>.
491
 */
492
static int
493
circuit_package_relay_cell(cell_t *cell, circuit_t *circ,
494
                           cell_direction_t cell_direction,
Nick Mathewson's avatar
Nick Mathewson committed
495
496
                           crypt_path_t *layer_hint, streamid_t on_stream,
                           const char *filename, int lineno)
Roger Dingledine's avatar
Roger Dingledine committed
497
{
498
  channel_t *chan; /* where to send the cell */
499

500
501
502
503
504
  if (circ->marked_for_close) {
    /* Circuit is marked; send nothing. */
    return 0;
  }

505
  if (cell_direction == CELL_DIRECTION_OUT) {
506
    crypt_path_t *thishop; /* counter for repeated crypts */
507
    chan = circ->n_chan;
Nick Mathewson's avatar
Nick Mathewson committed
508
509
    if (!chan) {
      log_warn(LD_BUG,"outgoing relay cell sent from %s:%d has n_chan==NULL."
510
511
512
513
514
515
516
517
518
               " Dropping. Circuit is in state %s (%d), and is "
               "%smarked for close. (%s:%d, %d)", filename, lineno,
               circuit_state_to_string(circ->state), circ->state,
               circ->marked_for_close ? "" : "not ",
               circ->marked_for_close_file?circ->marked_for_close_file:"",
               circ->marked_for_close, circ->marked_for_close_reason);
      if (CIRCUIT_IS_ORIGIN(circ)) {
        circuit_log_path(LOG_WARN, LD_BUG, TO_ORIGIN_CIRCUIT(circ));
      }
519
      log_backtrace(LOG_WARN,LD_BUG,"");
Nick Mathewson's avatar
Nick Mathewson committed
520
521
522
523
524
      return 0; /* just drop it */
    }
    if (!CIRCUIT_IS_ORIGIN(circ)) {
      log_warn(LD_BUG,"outgoing relay cell sent from %s:%d on non-origin "
               "circ. Dropping.", filename, lineno);
525
      log_backtrace(LOG_WARN,LD_BUG,"");
526
527
      return 0; /* just drop it */
    }
528

529
530
531
532
533
534
    relay_set_digest(layer_hint->f_digest, cell);

    thishop = layer_hint;
    /* moving from farthest to nearest hop */
    do {
      tor_assert(thishop);
535
536
      log_debug(LD_OR,"encrypting a layer of the relay cell.");
      relay_crypt_one_payload(thishop->f_crypto, cell->payload);
537
538

      thishop = thishop->prev;
539
    } while (thishop != TO_ORIGIN_CIRCUIT(circ)->cpath->prev);
540
541

  } else { /* incoming cell */
542
543
    or_circuit_t *or_circ;
    if (CIRCUIT_IS_ORIGIN(circ)) {
544
545
      /* We should never package an _incoming_ cell from the circuit
       * origin; that means we messed up somewhere. */
546
      log_warn(LD_BUG,"incoming relay cell at origin circuit. Dropping.");
547
      assert_circuit_ok(circ);
548
549
      return 0; /* just drop it */
    }
550
    or_circ = TO_OR_CIRCUIT(circ);
551
    chan = or_circ->p_chan;
552
    relay_set_digest(or_circ->p_digest, cell);
553
554
    /* encrypt one layer */
    relay_crypt_one_payload(or_circ->p_crypto, cell->payload);
555
556
  }
  ++stats_n_relay_cells_relayed;
557

558
  append_cell_to_circuit_queue(circ, chan, cell, cell_direction, on_stream);
559
560
561
562
563
564
  return 0;
}

/** If cell's stream_id matches the stream_id of any conn that's
 * attached to circ, return that conn, else return NULL.
 */
565
static edge_connection_t *
Nick Mathewson's avatar
Nick Mathewson committed
566
567
relay_lookup_conn(circuit_t *circ, cell_t *cell,
                  cell_direction_t cell_direction, crypt_path_t *layer_hint)
568
{
569
  edge_connection_t *tmpconn;
570
571
572
573
  relay_header_t rh;

  relay_header_unpack(&rh, cell->payload);

574
  if (!rh.stream_id)
575
576
577
578
579
580
    return NULL;

  /* IN or OUT cells could have come from either direction, now
   * that we allow rendezvous *to* an OP.
   */

581
582
583
  if (CIRCUIT_IS_ORIGIN(circ)) {
    for (tmpconn = TO_ORIGIN_CIRCUIT(circ)->p_streams; tmpconn;
         tmpconn=tmpconn->next_stream) {
584
      if (rh.stream_id == tmpconn->stream_id &&
585
          !tmpconn->base_.marked_for_close &&
586
          tmpconn->cpath_layer == layer_hint) {
587
        log_debug(LD_APP,"found conn for stream %d.", rh.stream_id);
588
        return tmpconn;
589
      }
590
    }
591
592
593
  } else {
    for (tmpconn = TO_OR_CIRCUIT(circ)->n_streams; tmpconn;
         tmpconn=tmpconn->next_stream) {
594
      if (rh.stream_id == tmpconn->stream_id &&
595
          !tmpconn->base_.marked_for_close) {
596
597
598
599
600
        log_debug(LD_EXIT,"found conn for stream %d.", rh.stream_id);
        if (cell_direction == CELL_DIRECTION_OUT ||
            connection_edge_is_rendezvous_stream(tmpconn))
          return tmpconn;
      }
601
    }
602
603
    for (tmpconn = TO_OR_CIRCUIT(circ)->resolving_streams; tmpconn;
         tmpconn=tmpconn->next_stream) {
604
      if (rh.stream_id == tmpconn->stream_id &&
605
          !tmpconn->base_.marked_for_close) {
606
607
608
        log_debug(LD_EXIT,"found conn for stream %d.", rh.stream_id);
        return tmpconn;
      }
609
610
611
612
613
    }
  }
  return NULL; /* probably a begin relay cell */
}

614
615
616
617
/** Pack the relay_header_t host-order structure <b>src</b> into
 * network-order in the buffer <b>dest</b>. See tor-spec.txt for details
 * about the wire format.
 */
618
void
Nick Mathewson's avatar
Nick Mathewson committed
619
relay_header_pack(uint8_t *dest, const relay_header_t *src)
620
{
Nick Mathewson's avatar
Nick Mathewson committed
621
  set_uint8(dest, src->command);
622
623
624
625
626
627
628
629
630
  set_uint16(dest+1, htons(src->recognized));
  set_uint16(dest+3, htons(src->stream_id));
  memcpy(dest+5, src->integrity, 4);
  set_uint16(dest+9, htons(src->length));
}

/** Unpack the network-order buffer <b>src</b> into a host-order
 * relay_header_t structure <b>dest</b>.
 */
631
void
Nick Mathewson's avatar
Nick Mathewson committed
632
relay_header_unpack(relay_header_t *dest, const uint8_t *src)
633
{
Nick Mathewson's avatar
Nick Mathewson committed
634
  dest->command = get_uint8(src);
635
636
637
638
639
640
  dest->recognized = ntohs(get_uint16(src+1));
  dest->stream_id = ntohs(get_uint16(src+3));
  memcpy(dest->integrity, src+5, 4);
  dest->length = ntohs(get_uint16(src+9));
}

Karsten Loesing's avatar
Karsten Loesing committed
641
642
643
644
/** Convert the relay <b>command</b> into a human-readable string. */
static const char *
relay_command_to_string(uint8_t command)
{
645
  static char buf[64];
Karsten Loesing's avatar
Karsten Loesing committed
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
  switch (command) {
    case RELAY_COMMAND_BEGIN: return "BEGIN";
    case RELAY_COMMAND_DATA: return "DATA";
    case RELAY_COMMAND_END: return "END";
    case RELAY_COMMAND_CONNECTED: return "CONNECTED";
    case RELAY_COMMAND_SENDME: return "SENDME";
    case RELAY_COMMAND_EXTEND: return "EXTEND";
    case RELAY_COMMAND_EXTENDED: return "EXTENDED";
    case RELAY_COMMAND_TRUNCATE: return "TRUNCATE";
    case RELAY_COMMAND_TRUNCATED: return "TRUNCATED";
    case RELAY_COMMAND_DROP: return "DROP";
    case RELAY_COMMAND_RESOLVE: return "RESOLVE";
    case RELAY_COMMAND_RESOLVED: return "RESOLVED";
    case RELAY_COMMAND_BEGIN_DIR: return "BEGIN_DIR";
    case RELAY_COMMAND_ESTABLISH_INTRO: return "ESTABLISH_INTRO";
    case RELAY_COMMAND_ESTABLISH_RENDEZVOUS: return "ESTABLISH_RENDEZVOUS";
    case RELAY_COMMAND_INTRODUCE1: return "INTRODUCE1";
    case RELAY_COMMAND_INTRODUCE2: return "INTRODUCE2";
    case RELAY_COMMAND_RENDEZVOUS1: return "RENDEZVOUS1";
    case RELAY_COMMAND_RENDEZVOUS2: return "RENDEZVOUS2";
    case RELAY_COMMAND_INTRO_ESTABLISHED: return "INTRO_ESTABLISHED";
    case RELAY_COMMAND_RENDEZVOUS_ESTABLISHED:
      return "RENDEZVOUS_ESTABLISHED";
    case RELAY_COMMAND_INTRODUCE_ACK: return "INTRODUCE_ACK";
670
671
672
673
674
675
    case RELAY_COMMAND_EXTEND2: return "EXTEND2";
    case RELAY_COMMAND_EXTENDED2: return "EXTENDED2";
    default:
      tor_snprintf(buf, sizeof(buf), "Unrecognized relay command %u",
                   (unsigned)command);
      return buf;
Karsten Loesing's avatar
Karsten Loesing committed
676
677
678
  }
}

679
680
681
682
683
/** Make a relay cell out of <b>relay_command</b> and <b>payload</b>, and send
 * it onto the open circuit <b>circ</b>. <b>stream_id</b> is the ID on
 * <b>circ</b> for the stream that's sending the relay cell, or 0 if it's a
 * control cell.  <b>cpath_layer</b> is NULL for OR->OP cells, or the
 * destination hop for OP->OR cells.
684
 *
685
686
 * If you can't send the cell, mark the circuit for close and return -1. Else
 * return 0.
687
 */
688
689
690
691
692
MOCK_IMPL(int,
relay_send_command_from_edge_,(streamid_t stream_id, circuit_t *circ,
                               uint8_t relay_command, const char *payload,
                               size_t payload_len, crypt_path_t *cpath_layer,
                               const char *filename, int lineno))
693
{
694
695
  cell_t cell;
  relay_header_t rh;
696
  cell_direction_t cell_direction;
697
  /* XXXX NM Split this function into a separate versions per circuit type? */
698

699
  tor_assert(circ);
700
  tor_assert(payload_len <= RELAY_PAYLOAD_SIZE);
701
702
703

  memset(&cell, 0, sizeof(cell_t));
  cell.command = CELL_RELAY;
704
705
  if (CIRCUIT_IS_ORIGIN(circ)) {
    tor_assert(cpath_layer);
706
707
    cell.circ_id = circ->n_circ_id;
    cell_direction = CELL_DIRECTION_OUT;
708
  } else {
709
    tor_assert(! cpath_layer);
710
    cell.circ_id = TO_OR_CIRCUIT(circ)->p_circ_id;
711
712
713
714
715
    cell_direction = CELL_DIRECTION_IN;
  }

  memset(&rh, 0, sizeof(rh));
  rh.command = relay_command;
716
  rh.stream_id = stream_id;
717
718
  rh.length = payload_len;
  relay_header_pack(cell.payload, &rh);
719
  if (payload_len)
720
721
    memcpy(cell.payload+RELAY_HEADER_SIZE, payload, payload_len);

722
723
  log_debug(LD_OR,"delivering %d cell %s.", relay_command,
            cell_direction == CELL_DIRECTION_OUT ? "forward" : "backward");
724

725
726
727
  if (relay_command == RELAY_COMMAND_DROP)
    rep_hist_padding_count_write(PADDING_TYPE_DROP);

728
729
  /* If we are sending an END cell and this circuit is used for a tunneled
   * directory request, advance its state. */
730
731
732
  if (relay_command == RELAY_COMMAND_END && circ->dirreq_id)
    geoip_change_dirreq_state(circ->dirreq_id, DIRREQ_TUNNELED,
                              DIRREQ_END_CELL_SENT);
733

734
  if (cell_direction == CELL_DIRECTION_OUT && circ->n_chan) {
735
    /* if we're using relaybandwidthrate, this conn wants priority */
736
    channel_timestamp_client(circ->n_chan);
737
738
  }

739
740
  if (cell_direction == CELL_DIRECTION_OUT) {
    origin_circuit_t *origin_circ = TO_ORIGIN_CIRCUIT(circ);
741
742
    if (origin_circ->remaining_relay_early_cells > 0 &&
        (relay_command == RELAY_COMMAND_EXTEND ||
743
         relay_command == RELAY_COMMAND_EXTEND2 ||
744
745
746
747
         cpath_layer != origin_circ->cpath)) {
      /* If we've got any relay_early cells left and (we're sending
       * an extend cell or we're not talking to the first hop), use
       * one of them.  Don't worry about the conn protocol version:
748
       * append_cell_to_circuit_queue will fix it up. */
749
750
751
752
      cell.command = CELL_RELAY_EARLY;
      --origin_circ->remaining_relay_early_cells;
      log_debug(LD_OR, "Sending a RELAY_EARLY cell; %d remaining.",
                (int)origin_circ->remaining_relay_early_cells);
Karsten Loesing's avatar
Karsten Loesing committed
753
754
755
756
      /* Memorize the command that is sent as RELAY_EARLY cell; helps debug
       * task 878. */
      origin_circ->relay_early_commands[
          origin_circ->relay_early_cells_sent++] = relay_command;
757
758
    } else if (relay_command == RELAY_COMMAND_EXTEND ||
               relay_command == RELAY_COMMAND_EXTEND2) {
Karsten Loesing's avatar
Karsten Loesing committed
759
760
761
      /* If no RELAY_EARLY cells can be sent over this circuit, log which
       * commands have been sent as RELAY_EARLY cells before; helps debug
       * task 878. */
762
      smartlist_t *commands_list = smartlist_new();
Karsten Loesing's avatar
Karsten Loesing committed
763
764
765
766
767
768
      int i = 0;
      char *commands = NULL;
      for (; i < origin_circ->relay_early_cells_sent; i++)
        smartlist_add(commands_list, (char *)
            relay_command_to_string(origin_circ->relay_early_commands[i]));
      commands = smartlist_join_strings(commands_list, ",", 0, NULL);
769
      log_warn(LD_BUG, "Uh-oh.  We're sending a RELAY_COMMAND_EXTEND cell, "
Karsten Loesing's avatar
Karsten Loesing committed
770
771
772
773
               "but we have run out of RELAY_EARLY cells on that circuit. "
               "Commands sent before: %s", commands);
      tor_free(commands);
      smartlist_free(commands_list);
774
775
776
    }
  }

777
  if (circuit_package_relay_cell(&cell, circ, cell_direction, cpath_layer,
Nick Mathewson's avatar
Nick Mathewson committed
778
                                 stream_id, filename, lineno) < 0) {
779
    log_warn(LD_BUG,"circuit_package_relay_cell failed. Closing.");
780
    circuit_mark_for_close(circ, END_CIRC_REASON_INTERNAL);
781
782
783
784
785
    return -1;
  }
  return 0;
}

786
787
788
789
790
791
792
793
794
795
/** Make a relay cell out of <b>relay_command</b> and <b>payload</b>, and
 * send it onto the open circuit <b>circ</b>. <b>fromconn</b> is the stream
 * that's sending the relay cell, or NULL if it's a control cell.
 * <b>cpath_layer</b> is NULL for OR->OP cells, or the destination hop
 * for OP->OR cells.
 *
 * If you can't send the cell, mark the circuit for close and
 * return -1. Else return 0.
 */
int
796
connection_edge_send_command(edge_connection_t *fromconn,
797
                             uint8_t relay_command, const char *payload,
798
                             size_t payload_len)
799
800
{
  /* XXXX NM Split this function into a separate versions per circuit type? */
801
  circuit_t *circ;
802
  crypt_path_t *cpath_layer = fromconn->cpath_layer;
803
804
  tor_assert(fromconn);
  circ = fromconn->on_circuit;
805

806
  if (fromconn->base_.marked_for_close) {
807
    log_warn(LD_BUG,
808
             "called on conn that's already marked for close at %s:%d.",
809
810
             fromconn->base_.marked_for_close_file,
             fromconn->base_.marked_for_close);
811
812
813
814
    return 0;
  }

  if (!circ) {
815
    if (fromconn->base_.type == CONN_TYPE_AP) {
816
      log_info(LD_APP,"no circ. Closing conn.");
817
818
      connection_mark_unattached_ap(EDGE_TO_ENTRY_CONN(fromconn),
                                    END_STREAM_REASON_INTERNAL);
819
820
    } else {
      log_info(LD_EXIT,"no circ. Closing conn.");
821
      fromconn->edge_has_sent_end = 1; /* no circ to send to */
822
      fromconn->end_reason = END_STREAM_REASON_INTERNAL;
823
824
825
826
827
      connection_mark_for_close(TO_CONN(fromconn));
    }
    return -1;
  }

828
829
830
831
832
833
  if (circ->marked_for_close) {
    /* The circuit has been marked, but not freed yet. When it's freed, it
     * will mark this connection for close. */
    return -1;
  }

834
835
836
837
838
839
840
841
#ifdef MEASUREMENTS_21206
  /* Keep track of the number of RELAY_DATA cells sent for directory
   * connections. */
  connection_t *linked_conn = TO_CONN(fromconn)->linked_conn;

  if (linked_conn && linked_conn->type == CONN_TYPE_DIR) {
    ++(TO_DIR_CONN(linked_conn)->data_cells_sent);
  }
842
#endif /* defined(MEASUREMENTS_21206) */
843

844
845
  return relay_send_command_from_edge(fromconn->stream_id, circ,
                                      relay_command, payload,
846
                                      payload_len, cpath_layer);
847
848
}

849
/** How many times will I retry a stream that fails due to DNS
850
 * resolve failure or misc error?
851
852
853
 */
#define MAX_RESOLVE_FAILURES 3

854
855
/** Return 1 if reason is something that you should retry if you
 * get the end cell before you've connected; else return 0. */
856
static int
857
858
edge_reason_is_retriable(int reason)
{
859
860
861
  return reason == END_STREAM_REASON_HIBERNATING ||
         reason == END_STREAM_REASON_RESOURCELIMIT ||
         reason == END_STREAM_REASON_EXITPOLICY ||
862
         reason == END_STREAM_REASON_RESOLVEFAILED ||
863
864
         reason == END_STREAM_REASON_MISC ||
         reason == END_STREAM_REASON_NOROUTE;
865
866
}

867
868
/** Called when we receive an END cell on a stream that isn't open yet,
 * from the client side.
869
870
 * Arguments are as for connection_edge_process_relay_cell().
 */
871
static int
872
connection_ap_process_end_not_open(
873
    relay_header_t *rh, cell_t *cell, origin_circuit_t *circ,
874
    entry_connection_t *conn, crypt_path_t *layer_hint)
875
{
876
  node_t *exitrouter;
877
  int reason = *(cell->payload+RELAY_HEADER_SIZE);
878
  int control_reason;
879
  edge_connection_t *edge_conn = ENTRY_TO_EDGE_CONN(conn);
880
  (void) layer_hint; /* unused */
881

882
  if (rh->length > 0) {
883
884
    if (reason == END_STREAM_REASON_TORPROTOCOL ||
        reason == END_STREAM_REASON_DESTROY) {
885
      /* Both of these reasons could mean a failed tag
886
       * hit the exit and it complained. Do not probe.
887
888
889
       * Fail the circuit. */
      circ->path_state = PATH_STATE_USE_FAILED;
      return -END_CIRC_REASON_TORPROTOCOL;
890
891
892
    } else if (reason == END_STREAM_REASON_INTERNAL) {
      /* We can't infer success or failure, since older Tors report
       * ENETUNREACH as END_STREAM_REASON_INTERNAL. */
893
894
    } else {
      /* Path bias: If we get a valid reason code from the exit,
895
896
897
898
899
       * it wasn't due to tagging.
       *
       * We rely on recognized+digest being strong enough to make
       * tags unlikely to allow us to get tagged, yet 'recognized'
       * reason codes here. */
900
      pathbias_mark_use_success(circ);
901
    }
902
903
  }

904
905
906
907
  if (rh->length == 0) {
    reason = END_STREAM_REASON_MISC;
  }

908
909
  control_reason = reason | END_STREAM_REASON_FLAG_REMOTE;

910
  if (edge_reason_is_retriable(reason) &&
911
912
      /* avoid retry if rend */
      !connection_edge_is_rendezvous_stream(edge_conn)) {
913
914
    const char *chosen_exit_digest =
      circ->build_state->chosen_exit->identity_digest;
915
916
    log_info(LD_APP,"Address '%s' refused due to '%s'. Considering retrying.",
             safe_str(conn->socks_request->address),
917
             stream_end_reason_to_string(reason));
918
    exitrouter = node_get_mutable_by_id(chosen_exit_digest);
919
    switch (reason) {
920
921
922
      case END_STREAM_REASON_EXITPOLICY: {
        tor_addr_t addr;
        tor_addr_make_unspec(&addr);
923
        if (rh->length >= 5) {
924
925
926
927
928
929
930
931
932
933
934
935
936
937
          int ttl = -1;
          tor_addr_make_unspec(&addr);
          if (rh->length == 5 || rh->length == 9) {
            tor_addr_from_ipv4n(&addr,
                                get_uint32(cell->payload+RELAY_HEADER_SIZE+1));
            if (rh->length == 9)
              ttl = (int)ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE+5));
          } else if (rh->length == 17 || rh->length == 21) {
            tor_addr_from_ipv6_bytes(&addr,
                                (char*)(cell->payload+RELAY_HEADER_SIZE+1));
            if (rh->length == 21)
              ttl = (int)ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE+17));
          }
          if (tor_addr_is_null(&addr)) {
938
939
            log_info(LD_APP,"Address '%s' resolved to 0.0.0.0. Closing,",
                     safe_str(conn->socks_request->address));
940
941
942
            connection_mark_unattached_ap(conn, END_STREAM_REASON_TORPROTOCOL);
            return 0;
          }
Roger Dingledine's avatar
Roger Dingledine committed
943

Nick Mathewson's avatar
Nick Mathewson committed
944
945
946
947
          if ((tor_addr_family(&addr) == AF_INET &&
                                          !conn->entry_cfg.ipv4_traffic) ||
              (tor_addr_family(&addr) == AF_INET6 &&
                                          !conn->entry_cfg.ipv6_traffic)) {
948
949
950
951
952
953
            log_fn(LOG_PROTOCOL_WARN, LD_APP,
                   "Got an EXITPOLICY failure on a connection with a "
                   "mismatched family. Closing.");
            connection_mark_unattached_ap(conn, END_STREAM_REASON_TORPROTOCOL);
            return 0;
          }
954
          if (get_options()->ClientDNSRejectInternalAddresses &&
955
              tor_addr_is_internal(&addr, 0)) {
956
957
958
959
960
            log_info(LD_APP,"Address '%s' resolved to internal. Closing,",
                     safe_str(conn->socks_request->address));
            connection_mark_unattached_ap(conn, END_STREAM_REASON_TORPROTOCOL);
            return 0;
          }
961

962
          client_dns_set_addressmap(conn,
963
                                    conn->socks_request->address, &addr,
964
                                    conn->chosen_exit_name, ttl);
965
966
967
968
969
970
971
972
973
974

          {
            char new_addr[TOR_ADDR_BUF_LEN];
            tor_addr_to_str(new_addr, &addr, sizeof(new_addr), 1);
            if (strcmp(conn->socks_request->address, new_addr)) {
              strlcpy(conn->socks_request->address, new_addr,
                      sizeof(conn->socks_request->address));
              control_event_stream_status(conn, STREAM_EVENT_REMAP, 0);
            }
          }
975
        }
976
        /* check if the exit *ought* to have allowed it */
977
978
979
980
981

        adjust_exit_policy_from_exitpolicy_failure(circ,
                                                   conn,
                                                   exitrouter,
                                                   &addr);
982

983
984
        if (conn->chosen_exit_optional ||
            conn->chosen_exit_retries) {
985
          /* stop wanting a specific exit */
986
          conn->chosen_exit_optional = 0;
987
988
989
990
991
992
993
          /* A non-zero chosen_exit_retries can happen if we set a
           * TrackHostExits for this address under a port that the exit
           * relay allows, but then try the same address with a different
           * port that it doesn't allow to exit. We shouldn't unregister
           * the mapping, since it is probably still wanted on the
           * original port. But now we give away to the exit relay that
           * we probably have a TrackHostExits on it. So be it. */
994
          conn->chosen_exit_retries = 0;
995
          tor_free(conn->chosen_exit_name); /* clears it */
996
        }
997
        if (connection_ap_detach_retriable(conn, circ, control_reason) >= 0)
998
999
1000
          return 0;
        /* else, conn will get closed below */
        break;
For faster browsing, not all history is shown. View entire blame