circuituse.c 48.5 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-2007, Roger Dingledine, Nick Mathewson. */
4
5
/* See LICENSE for licensing information */
/* $Id$ */
6
7
const char circuituse_c_id[] =
  "$Id$";
8
9
10

/**
 * \file circuituse.c
11
 * \brief Launch the right sort of circuits and attach streams to them.
12
13
14
15
16
17
18
19
20
21
 **/

#include "or.h"

/********* START VARIABLES **********/

extern circuit_t *global_circuitlist; /* from circuitlist.c */

/********* END VARIABLES ************/

22
static void circuit_expire_old_circuits(time_t now);
23
24
static void circuit_increment_failure_count(void);

25
/** Return 1 if <b>circ</b> could be returned by circuit_get_best().
26
27
 * Else return 0.
 */
28
static int
29
circuit_is_acceptable(circuit_t *circ, edge_connection_t *conn,
30
31
                      int must_be_open, uint8_t purpose,
                      int need_uptime, int need_internal,
32
                      time_t now)
33
34
{
  routerinfo_t *exitrouter;
35
  cpath_build_state_t *build_state;
36
37
38
  tor_assert(circ);
  tor_assert(conn);
  tor_assert(conn->socks_request);
39
40
41
42
43
44
45
46
47

  if (!CIRCUIT_IS_ORIGIN(circ))
    return 0; /* this circ doesn't start at us */
  if (must_be_open && (circ->state != CIRCUIT_STATE_OPEN || !circ->n_conn))
    return 0; /* ignore non-open circs */
  if (circ->marked_for_close)
    return 0;

  /* if this circ isn't our purpose, skip. */
48
49
  if (purpose == CIRCUIT_PURPOSE_C_REND_JOINED && !must_be_open) {
    if (circ->purpose != CIRCUIT_PURPOSE_C_ESTABLISH_REND &&
50
51
52
        circ->purpose != CIRCUIT_PURPOSE_C_REND_READY &&
        circ->purpose != CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED &&
        circ->purpose != CIRCUIT_PURPOSE_C_REND_JOINED)
53
      return 0;
54
55
  } else if (purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT &&
             !must_be_open) {
56
57
58
59
    if (circ->purpose != CIRCUIT_PURPOSE_C_INTRODUCING &&
        circ->purpose != CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT)
      return 0;
  } else {
60
    if (purpose != circ->purpose)
61
62
63
      return 0;
  }

64
65
  if (purpose == CIRCUIT_PURPOSE_C_GENERAL)
    if (circ->timestamp_dirty &&
66
       circ->timestamp_dirty+get_options()->MaxCircuitDirtiness <= now)
67
68
      return 0;

69
  /* decide if this circ is suitable for this conn */
70

71
72
73
74
  /* for rend circs, circ->cpath->prev is not the last router in the
   * circuit, it's the magical extra bob hop. so just check the nickname
   * of the one we meant to finish at.
   */
75
76
  build_state = TO_ORIGIN_CIRCUIT(circ)->build_state;
  exitrouter = build_state_get_exit_router(build_state);
77

78
  if (need_uptime && !build_state->need_uptime)
79
    return 0;
80
  if (need_internal != build_state->is_internal)
81
    return 0;
82

83
  if (purpose == CIRCUIT_PURPOSE_C_GENERAL) {
84
85
    if (!exitrouter && !build_state->onehop_tunnel) {
        log_debug(LD_CIRC,"Not considering circuit with unknown router.");
86
87
88
      return 0; /* this circuit is screwed and doesn't know it yet,
                 * or is a rendezvous circuit. */
    }
89
90
91
92
93
    if (build_state->onehop_tunnel) {
      if (conn->socks_request->command != SOCKS_COMMAND_CONNECT_DIR) {
        log_debug(LD_CIRC,"Skipping one-hop circuit.");
        return 0;
      }
94
95
96
97
98
99
100
101
      tor_assert(conn->chosen_exit_name);
      if (build_state->chosen_exit) {
        char digest[DIGEST_LEN];
        if (hexdigest_to_digest(conn->chosen_exit_name, digest) < 0 ||
            memcmp(digest, build_state->chosen_exit->identity_digest,
                   DIGEST_LEN))
          return 0; /* this is a circuit to somewhere else */
      }
102
103
104
    } else {
      if (conn->socks_request->command == SOCKS_COMMAND_CONNECT_DIR) {
        /* don't use three-hop circuits -- that could hurt our anonymity. */
105
//        log_debug(LD_CIRC,"Skipping multi-hop circuit for CONNECT_DIR.");
106
107
108
        return 0;
      }
    }
109
    if (exitrouter && !connection_ap_can_use_exit(conn, exitrouter)) {
110
111
112
113
      /* can't exit from this router */
      return 0;
    }
  } else { /* not general */
114
115
    if (rend_cmp_service_ids(conn->rend_query,
                             TO_ORIGIN_CIRCUIT(circ)->rend_query)) {
116
117
      /* this circ is not for this conn */
      return 0;
118
119
120
121
122
    }
  }
  return 1;
}

123
/** Return 1 if circuit <b>a</b> is better than circuit <b>b</b> for
124
125
 * <b>purpose</b>, and return 0 otherwise. Used by circuit_get_best.
 */
126
127
static int
circuit_is_better(circuit_t *a, circuit_t *b, uint8_t purpose)
128
{
129
  switch (purpose) {
130
131
132
133
    case CIRCUIT_PURPOSE_C_GENERAL:
      /* if it's used but less dirty it's best;
       * else if it's more recently created it's best
       */
134
135
      if (b->timestamp_dirty) {
        if (a->timestamp_dirty &&
136
            a->timestamp_dirty > b->timestamp_dirty)
137
138
          return 1;
      } else {
139
        if (a->timestamp_dirty ||
140
            a->timestamp_created > b->timestamp_created)
141
          return 1;
142
143
144
        if (CIRCUIT_IS_ORIGIN(b) &&
            TO_ORIGIN_CIRCUIT(b)->build_state->is_internal)
          return 1;
145
146
147
148
      }
      break;
    case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
      /* the closer it is to ack_wait the better it is */
149
      if (a->purpose > b->purpose)
150
151
152
153
        return 1;
      break;
    case CIRCUIT_PURPOSE_C_REND_JOINED:
      /* the closer it is to rend_joined the better it is */
154
      if (a->purpose > b->purpose)
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
        return 1;
      break;
  }
  return 0;
}

/** Find the best circ that conn can use, preferably one which is
 * dirty. Circ must not be too old.
 *
 * Conn must be defined.
 *
 * If must_be_open, ignore circs not in CIRCUIT_STATE_OPEN.
 *
 * circ_purpose specifies what sort of circuit we must have.
 * It can be C_GENERAL, C_INTRODUCE_ACK_WAIT, or C_REND_JOINED.
 *
 * If it's REND_JOINED and must_be_open==0, then return the closest
 * rendezvous-purposed circuit that you can find.
 *
 * If it's INTRODUCE_ACK_WAIT and must_be_open==0, then return the
 * closest introduce-purposed circuit that you can find.
 */
177
static origin_circuit_t *
178
circuit_get_best(edge_connection_t *conn, int must_be_open, uint8_t purpose,
179
                 int need_uptime, int need_internal)
180
181
182
183
184
185
186
187
188
189
190
{
  circuit_t *circ, *best=NULL;
  time_t now = time(NULL);

  tor_assert(conn);

  tor_assert(purpose == CIRCUIT_PURPOSE_C_GENERAL ||
             purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT ||
             purpose == CIRCUIT_PURPOSE_C_REND_JOINED);

  for (circ=global_circuitlist;circ;circ = circ->next) {
191
192
    if (!circuit_is_acceptable(circ,conn,must_be_open,purpose,
                               need_uptime,need_internal,now))
193
194
195
196
197
      continue;

    /* now this is an acceptable circ to hand back. but that doesn't
     * mean it's the *best* circ to hand back. try to decide.
     */
198
    if (!best || circuit_is_better(circ,best,purpose))
199
200
201
      best = circ;
  }

202
  return best ? TO_ORIGIN_CIRCUIT(best) : NULL;
203
204
205
}

/** Close all circuits that start at us, aren't open, and were born
206
 * at least CircuitBuildTimeout seconds ago.
207
 */
208
209
210
void
circuit_expire_building(time_t now)
{
211
  circuit_t *victim, *circ = global_circuitlist;
212
  time_t cutoff = now - get_options()->CircuitBuildTimeout;
213

214
  while (circ) {
215
216
    victim = circ;
    circ = circ->next;
217
218
219
220
    if (!CIRCUIT_IS_ORIGIN(victim) || /* didn't originate here */
        victim->timestamp_created > cutoff || /* Not old enough to expire */
        victim->marked_for_close) /* don't mess with marked circs */
      continue;
221

222
#if 0
223
    /* some debug logs, to help track bugs */
224
    if (victim->purpose >= CIRCUIT_PURPOSE_C_INTRODUCING &&
225
        victim->purpose <= CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED) {
226
      if (!victim->timestamp_dirty)
227
228
        log_fn(LOG_DEBUG,"Considering %sopen purp %d to %s (circid %d)."
               "(clean).",
229
               victim->state == CIRCUIT_STATE_OPEN ? "" : "non",
Nick Mathewson's avatar
Nick Mathewson committed
230
               victim->purpose, victim->build_state->chosen_exit_name,
231
232
               victim->n_circ_id);
      else
233
234
        log_fn(LOG_DEBUG,"Considering %sopen purp %d to %s (circid %d). "
               "%d secs since dirty.",
235
               victim->state == CIRCUIT_STATE_OPEN ? "" : "non",
Nick Mathewson's avatar
Nick Mathewson committed
236
               victim->purpose, victim->build_state->chosen_exit_name,
237
238
239
               victim->n_circ_id,
               (int)(now - victim->timestamp_dirty));
    }
240
#endif
241
242
243

    /* if circ is !open, or if it's open but purpose is a non-finished
     * intro or rend, then mark it for close */
244
245
    if (victim->state == CIRCUIT_STATE_OPEN) {
      switch (victim->purpose) {
246
        default: /* most open circuits can be left alone. */
247
248
          continue; /* yes, continue inside a switch refers to the nearest
                     * enclosing loop. C is smart. */
249
250
251
        case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
        case CIRCUIT_PURPOSE_C_INTRODUCING:
        case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
252
          break; /* too old, need to die */
253
254
        case CIRCUIT_PURPOSE_C_REND_READY:
          /* it's a rend_ready circ -- has it already picked a query? */
255
256
257
          /* c_rend_ready circs measure age since timestamp_dirty,
           * because that's set when they switch purposes
           */
258
259
          if (TO_ORIGIN_CIRCUIT(victim)->rend_query[0] ||
              victim->timestamp_dirty > cutoff)
260
261
262
263
264
265
266
267
268
269
270
271
            continue;
          break;
        case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
        case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
          /* rend and intro circs become dirty each time they
           * make an introduction attempt. so timestamp_dirty
           * will reflect the time since the last attempt.
           */
          if (victim->timestamp_dirty > cutoff)
            continue;
          break;
      }
272
    }
273
274

    if (victim->n_conn)
275
      log_info(LD_CIRC,"Abandoning circ %s:%d:%d (state %d:%s, purpose %d)",
276
277
               victim->n_conn->_base.address, victim->n_port,
               victim->n_circ_id,
278
279
               victim->state, circuit_state_to_string(victim->state),
               victim->purpose);
280
    else
281
282
283
      log_info(LD_CIRC,"Abandoning circ %d (state %d:%s, purpose %d)",
               victim->n_circ_id, victim->state,
               circuit_state_to_string(victim->state), victim->purpose);
284

285
    circuit_log_path(LOG_INFO,LD_CIRC,TO_ORIGIN_CIRCUIT(victim));
286
    circuit_mark_for_close(victim, END_CIRC_REASON_TIMEOUT);
287
288
289
  }
}

290
291
/** Remove any elements in <b>needed_ports</b> that are handled by an
 * open or in-progress circuit.
292
 */
293
void
294
295
circuit_remove_handled_ports(smartlist_t *needed_ports)
{
296
  int i;
Roger Dingledine's avatar
Roger Dingledine committed
297
  uint16_t *port;
298
299

  for (i = 0; i < smartlist_len(needed_ports); ++i) {
Roger Dingledine's avatar
Roger Dingledine committed
300
301
    port = smartlist_get(needed_ports, i);
    tor_assert(*port);
302
303
    if (circuit_stream_is_being_handled(NULL, *port,
                                        MIN_CIRCUITS_HANDLING_STREAM)) {
304
//      log_debug(LD_CIRC,"Port %d is already being handled; removing.", port);
305
      smartlist_del(needed_ports, i--);
Roger Dingledine's avatar
Roger Dingledine committed
306
      tor_free(port);
307
    } else {
308
      log_debug(LD_CIRC,"Port %d is not handled.", *port);
309
310
311
    }
  }
}
312

313
314
315
/** Return 1 if at least <b>min</b> general-purpose non-internal circuits
 * will have an acceptable exit node for exit stream <b>conn</b> if it
 * is defined, else for "*:port".
316
 * Else return 0.
317
 */
318
int
319
320
circuit_stream_is_being_handled(edge_connection_t *conn,
                                uint16_t port, int min)
321
{
322
323
324
325
  circuit_t *circ;
  routerinfo_t *exitrouter;
  int num=0;
  time_t now = time(NULL);
326
327
  int need_uptime = smartlist_string_num_isin(get_options()->LongLivedPorts,
                                   conn ? conn->socks_request->port : port);
328

329
  for (circ=global_circuitlist;circ;circ = circ->next) {
330
331
332
333
    if (CIRCUIT_IS_ORIGIN(circ) &&
        !circ->marked_for_close &&
        circ->purpose == CIRCUIT_PURPOSE_C_GENERAL &&
        (!circ->timestamp_dirty ||
334
         circ->timestamp_dirty + get_options()->MaxCircuitDirtiness > now)) {
335
      cpath_build_state_t *build_state = TO_ORIGIN_CIRCUIT(circ)->build_state;
336
      if (build_state->is_internal || build_state->onehop_tunnel)
337
338
339
340
        continue;

      exitrouter = build_state_get_exit_router(build_state);
      if (exitrouter && (!need_uptime || build_state->need_uptime)) {
341
342
343
344
        int ok;
        if (conn) {
          ok = connection_ap_can_use_exit(conn, exitrouter);
        } else {
345
          addr_policy_result_t r = compare_addr_to_addr_policy(
346
              0, port, exitrouter->exit_policy);
347
348
349
350
351
352
          ok = r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED;
        }
        if (ok) {
          if (++num >= min)
            return 1;
        }
353
      }
354
355
356
357
358
    }
  }
  return 0;
}

359
/** Don't keep more than this many unused open circuits around. */
360
#define MAX_UNUSED_OPEN_CIRCUITS 12
361
362
363
364
365
366
367
368
369
370
371
372
373
374

/** Figure out how many circuits we have open that are clean. Make
 * sure it's enough for all the upcoming behaviors we predict we'll have.
 * But if we have too many, close the not-so-useful ones.
 */
static void
circuit_predict_and_launch_new(void)
{
  circuit_t *circ;
  int num=0, num_internal=0, num_uptime_internal=0;
  int hidserv_needs_uptime=0, hidserv_needs_capacity=1;
  int port_needs_uptime=0, port_needs_capacity=1;
  time_t now = time(NULL);

375
  /* First, count how many of each type of circuit we have already. */
376
  for (circ=global_circuitlist;circ;circ = circ->next) {
377
    cpath_build_state_t *build_state;
378
379
380
381
382
383
384
385
    if (!CIRCUIT_IS_ORIGIN(circ))
      continue;
    if (circ->marked_for_close)
      continue; /* don't mess with marked circs */
    if (circ->timestamp_dirty)
      continue; /* only count clean circs */
    if (circ->purpose != CIRCUIT_PURPOSE_C_GENERAL)
      continue; /* only pay attention to general-purpose circs */
386
    build_state = TO_ORIGIN_CIRCUIT(circ)->build_state;
387
388
389
    if (build_state->onehop_tunnel)
      continue;
    num++;
390
    if (build_state->is_internal)
391
      num_internal++;
392
    if (build_state->need_uptime && build_state->is_internal)
393
394
395
      num_uptime_internal++;
  }

396
397
398
399
400
401
402
403
404
  /* If that's enough, then stop now. */
  if (num >= MAX_UNUSED_OPEN_CIRCUITS)
    return; /* we already have many, making more probably will hurt */

  /* Second, see if we need any more exit circuits. */
  /* check if we know of a port that's been requested recently
   * and no circuit is currently available that can handle it. */
  if (!circuit_all_predicted_ports_handled(now, &port_needs_uptime,
                                           &port_needs_capacity)) {
405
406
407
    log_info(LD_CIRC,
             "Have %d clean circs (%d internal), need another exit circ.",
             num, num_internal);
408
    circuit_launch_by_router(CIRCUIT_PURPOSE_C_GENERAL, 0, NULL,
409
410
411
412
413
414
                             port_needs_uptime, port_needs_capacity, 0);
    return;
  }

  /* Third, see if we need any more hidden service (server) circuits. */
  if (num_rend_services() && num_uptime_internal < 3) {
415
416
417
418
    log_info(LD_CIRC,
             "Have %d clean circs (%d internal), need another internal "
             "circ for my hidden service.",
             num, num_internal);
419
    circuit_launch_by_router(CIRCUIT_PURPOSE_C_GENERAL, 0, NULL,
420
421
422
423
424
                             1, 1, 1);
    return;
  }

  /* Fourth, see if we need any more hidden service (client) circuits. */
425
426
  if (rep_hist_get_predicted_internal(now, &hidserv_needs_uptime,
                                      &hidserv_needs_capacity) &&
427
428
      ((num_uptime_internal<2 && hidserv_needs_uptime) ||
        num_internal<2)) {
429
430
431
432
    log_info(LD_CIRC,
             "Have %d clean circs (%d uptime-internal, %d internal), need"
             " another hidserv circ.",
             num, num_uptime_internal, num_internal);
433
    circuit_launch_by_router(CIRCUIT_PURPOSE_C_GENERAL, 0, NULL,
434
435
                             hidserv_needs_uptime, hidserv_needs_capacity, 1);
    return;
436
437
438
  }
}

439
440
441
/** Build a new test circuit every 5 minutes */
#define TESTING_CIRCUIT_INTERVAL 300

442
443
444
445
/** This function is called once a second, if router_have_min_dir_info() is
 * true. Its job is to make sure all services we offer have enough circuits
 * available. Some services just want enough circuits for current tasks,
 * whereas others want a minimum set of idle circuits hanging around.
446
 */
447
448
449
void
circuit_build_needed_circs(time_t now)
{
450
  static long time_to_new_circuit = 0;
451
  or_options_t *options = get_options();
452
453
454
455
456

  /* launch a new circ for any pending streams that need one */
  connection_ap_attach_pending();

  /* make sure any hidden services have enough intro points */
457
  rend_services_introduce();
458

459
  if (time_to_new_circuit < now) {
460
    circuit_reset_failure_count(1);
461
    time_to_new_circuit = now + options->NewCircuitPeriod;
462
    if (proxy_mode(get_options()))
463
      addressmap_clean(now);
464
    circuit_expire_old_circuits(now);
465

466
467
#if 0 /* disable for now, until predict-and-launch-new can cull leftovers */
    circ = circuit_get_youngest_clean_open(CIRCUIT_PURPOSE_C_GENERAL);
468
469
470
    if (get_options()->RunTesting &&
        circ &&
        circ->timestamp_created + TESTING_CIRCUIT_INTERVAL < now) {
471
      log_fn(LOG_INFO,"Creating a new testing circuit.");
472
      circuit_launch_by_router(CIRCUIT_PURPOSE_C_GENERAL, 0, NULL, 0, 0, 0);
473
    }
474
475
#endif
  }
476
477
  if (!options->DisablePredictedCircuits)
    circuit_predict_and_launch_new();
478
479
480
481
482
}

/** If the stream <b>conn</b> is a member of any of the linked
 * lists of <b>circ</b>, then remove it from the list.
 */
483
void
484
circuit_detach_stream(circuit_t *circ, edge_connection_t *conn)
485
{
486
  edge_connection_t *prevconn;
487

488
489
  tor_assert(circ);
  tor_assert(conn);
490

491
  conn->cpath_layer = NULL; /* make sure we don't keep a stale pointer */
492
  conn->on_circuit = NULL;
493

494
495
496
497
498
499
  if (CIRCUIT_IS_ORIGIN(circ)) {
    origin_circuit_t *origin_circ = TO_ORIGIN_CIRCUIT(circ);
    if (conn == origin_circ->p_streams) {
      origin_circ->p_streams = conn->next_stream;
      return;
    }
500

501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
    for (prevconn = origin_circ->p_streams;
         prevconn && prevconn->next_stream && prevconn->next_stream != conn;
         prevconn = prevconn->next_stream)
      ;
    if (prevconn && prevconn->next_stream) {
      prevconn->next_stream = conn->next_stream;
      return;
    }
  } else {
    or_circuit_t *or_circ = TO_OR_CIRCUIT(circ);
    if (conn == or_circ->n_streams) {
      or_circ->n_streams = conn->next_stream;
      return;
    }
    if (conn == or_circ->resolving_streams) {
      or_circ->resolving_streams = conn->next_stream;
      return;
    }
519

520
521
522
523
524
525
526
527
    for (prevconn = or_circ->n_streams;
         prevconn && prevconn->next_stream && prevconn->next_stream != conn;
         prevconn = prevconn->next_stream)
      ;
    if (prevconn && prevconn->next_stream) {
      prevconn->next_stream = conn->next_stream;
      return;
    }
528

529
530
531
532
533
534
535
536
    for (prevconn = or_circ->resolving_streams;
         prevconn && prevconn->next_stream && prevconn->next_stream != conn;
         prevconn = prevconn->next_stream)
      ;
    if (prevconn && prevconn->next_stream) {
      prevconn->next_stream = conn->next_stream;
      return;
    }
537
538
  }

539
540
541
  log_warn(LD_BUG,"Edge connection not in circuit's list.");
  /* Don't give an error here; it's harmless. */
  // tor_fragile_assert();
542
543
}

544
/** Find each circuit that has been unused for too long, or dirty
545
 * for too long and has no streams on it: mark it for close.
546
547
 */
static void
548
circuit_expire_old_circuits(time_t now)
549
550
{
  circuit_t *circ;
551
  time_t cutoff = now - get_options()->CircuitIdleTimeout;
552
553

  for (circ = global_circuitlist; circ; circ = circ->next) {
554
    if (circ->marked_for_close || ! CIRCUIT_IS_ORIGIN(circ))
555
556
557
558
559
      continue;
    /* If the circuit has been dirty for too long, and there are no streams
     * on it, mark it for close.
     */
    if (circ->timestamp_dirty &&
560
        circ->timestamp_dirty + get_options()->MaxCircuitDirtiness < now &&
561
        !TO_ORIGIN_CIRCUIT(circ)->p_streams /* nothing attached */ ) {
562
563
564
      log_debug(LD_CIRC, "Closing n_circ_id %d (dirty %d secs ago, purp %d)",
                circ->n_circ_id, (int)(now - circ->timestamp_dirty),
                circ->purpose);
565
      circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
566
    } else if (!circ->timestamp_dirty &&
567
568
               circ->state == CIRCUIT_STATE_OPEN &&
               circ->purpose == CIRCUIT_PURPOSE_C_GENERAL) {
569
      if (circ->timestamp_created < cutoff) {
570
571
572
        log_debug(LD_CIRC,
                  "Closing circuit that has been unused for %d seconds.",
                  (int)(now - circ->timestamp_created));
573
        circuit_mark_for_close(circ, END_CIRC_REASON_FINISHED);
574
      }
575
576
577
578
    }
  }
}

Roger Dingledine's avatar
Roger Dingledine committed
579
/** Number of testing circuits we want open before testing our bandwidth. */
580
581
#define NUM_PARALLEL_TESTING_CIRCS 4

Roger Dingledine's avatar
Roger Dingledine committed
582
/** True iff we've ever had enough testing circuits open to test our
583
 * bandwidth. */
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
static int have_performed_bandwidth_test = 0;

/** Reset have_performed_bandwidth_test, so we'll start building
 * testing circuits again so we can exercise our bandwidth. */
void
reset_bandwidth_test(void)
{
  have_performed_bandwidth_test = 0;
}

/** Return 1 if we've already exercised our bandwidth, or if we
 * have fewer than NUM_PARALLEL_TESTING_CIRCS testing circuits
 * established or on the way. Else return 0.
 */
int
circuit_enough_testing_circs(void)
{
  circuit_t *circ;
  int num = 0;

  if (have_performed_bandwidth_test)
    return 1;

  for (circ = global_circuitlist; circ; circ = circ->next) {
    if (!circ->marked_for_close && CIRCUIT_IS_ORIGIN(circ) &&
        circ->purpose == CIRCUIT_PURPOSE_TESTING &&
        circ->state == CIRCUIT_STATE_OPEN)
      num++;
  }
  return num >= NUM_PARALLEL_TESTING_CIRCS;
}

/** A testing circuit has completed. Take whatever stats we want.
 * Noticing reachability is taken care of in onionskin_answer(),
 * so there's no need to record anything here. But if we still want
 * to do the bandwidth test, and we now have enough testing circuits
 * open, do it.
 */
622
static void
623
circuit_testing_opened(origin_circuit_t *circ)
624
{
625
626
627
628
629
  if (have_performed_bandwidth_test) {
    circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_AT_ORIGIN);
  } else if (circuit_enough_testing_circs()) {
    router_perform_bandwidth_test(NUM_PARALLEL_TESTING_CIRCS, time(NULL));
    have_performed_bandwidth_test = 1;
630
631
  } else
    consider_testing_reachability(1, 0);
632
633
634
635
}

/** A testing circuit has failed to build. Take whatever stats we want. */
static void
636
circuit_testing_failed(origin_circuit_t *circ, int at_last_hop)
637
{
638
  routerinfo_t *me = router_get_my_routerinfo();
639
640
  if (server_mode(get_options()) && check_whether_orport_reachable())
    return;
641
642
  if (!me)
    return;
643

644
645
  log_info(LD_GENERAL,
           "Our testing circuit (to see if your ORPort is reachable) "
646
           "has failed. I'll try again later.");
647
648
  control_event_server_status(LOG_WARN, "REACHABILITY_FAILED ORADDRESS=%s:%d",
                             me->address, me->or_port);
649
650
651
652

  /* These aren't used yet. */
  (void)circ;
  (void)at_last_hop;
653
654
}

655
656
657
658
659
660
/** The circuit <b>circ</b> has just become open. Take the next
 * step: for rendezvous circuits, we pass circ to the appropriate
 * function in rendclient or rendservice. For general circuits, we
 * call connection_ap_attach_pending, which looks for pending streams
 * that could use circ.
 */
661
void
662
circuit_has_opened(origin_circuit_t *circ)
663
{
664
  control_event_circuit_status(circ, CIRC_EVENT_BUILT, 0);
665

666
  switch (TO_CIRCUIT(circ)->purpose) {
667
668
    case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
      rend_client_rendcirc_has_opened(circ);
669
      connection_ap_attach_pending();
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
      break;
    case CIRCUIT_PURPOSE_C_INTRODUCING:
      rend_client_introcirc_has_opened(circ);
      break;
    case CIRCUIT_PURPOSE_C_GENERAL:
      /* Tell any AP connections that have been waiting for a new
       * circuit that one is ready. */
      connection_ap_attach_pending();
      break;
    case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
      /* at Bob, waiting for introductions */
      rend_service_intro_has_opened(circ);
      break;
    case CIRCUIT_PURPOSE_S_CONNECT_REND:
      /* at Bob, connecting to rend point */
      rend_service_rendezvous_has_opened(circ);
      break;
687
688
689
    case CIRCUIT_PURPOSE_TESTING:
      circuit_testing_opened(circ);
      break;
690
691
692
    /* default:
     * This won't happen in normal operation, but might happen if the
     * controller did it. Just let it slide. */
693
694
695
  }
}

696
/** Called whenever a circuit could not be successfully built.
697
 */
698
void
699
circuit_build_failed(origin_circuit_t *circ)
700
{
701
702
703
704
705
706
707
708
709
  /* we should examine circ and see if it failed because of
   * the last hop or an earlier hop. then use this info below.
   */
  int failed_at_last_hop = 0;
  /* If the last hop isn't open, and the second-to-last is, we failed
   * at the last hop. */
  if (circ->cpath &&
      circ->cpath->prev->state != CPATH_STATE_OPEN &&
      circ->cpath->prev->prev->state == CPATH_STATE_OPEN) {
710
711
712
713
714
715
    failed_at_last_hop = 1;
  }
  if (circ->cpath &&
      circ->cpath->state != CPATH_STATE_OPEN) {
    /* We failed at the first hop. If there's an OR connection
       to blame, blame it. */
716
    or_connection_t *n_conn = NULL;
717
718
719
    if (circ->_base.n_conn) {
      n_conn = circ->_base.n_conn;
    } else if (circ->_base.state == CIRCUIT_STATE_OR_WAIT) {
720
      /* we have to hunt for it */
721
722
      n_conn = connection_or_get_by_identity_digest(
                                               circ->_base.n_conn_id_digest);
723
724
    }
    if (n_conn) {
725
726
727
      log_info(LD_OR,
               "Our circuit failed to get a response from the first hop "
               "(%s:%d). I'm going to try to rotate to a better connection.",
728
729
               n_conn->_base.address, n_conn->_base.port);
      n_conn->_base.or_is_obsolete = 1;
730
731
      entry_guard_register_connect_status(n_conn->identity_digest, 0,
                                          time(NULL));
732
    }
733
734
  }

735
  switch (circ->_base.purpose) {
736
    case CIRCUIT_PURPOSE_C_GENERAL:
737
738
      /* If we never built the circuit, note it as a failure. */
      circuit_increment_failure_count();
739
740
741
742
743
      if (failed_at_last_hop) {
        /* Make sure any streams that demand our last hop as their exit
         * know that it's unlikely to happen. */
        circuit_discard_optional_exit_enclaves(circ->cpath->prev->extend_info);
      }
744
      break;
745
746
747
    case CIRCUIT_PURPOSE_TESTING:
      circuit_testing_failed(circ, failed_at_last_hop);
      break;
748
749
    case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
      /* at Bob, waiting for introductions */
750
      if (circ->_base.state != CIRCUIT_STATE_OPEN) {
751
752
753
754
755
756
757
758
759
760
761
762
763
764
        circuit_increment_failure_count();
      }
      /* no need to care here, because bob will rebuild intro
       * points periodically. */
      break;
    case CIRCUIT_PURPOSE_C_INTRODUCING:
      /* at Alice, connecting to intro point */
      /* Don't increment failure count, since Bob may have picked
       * the introduction point maliciously */
      /* Alice will pick a new intro point when this one dies, if
       * the stream in question still cares. No need to act here. */
      break;
    case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
      /* at Alice, waiting for Bob */
765
      circuit_increment_failure_count();
766
767
768
769
770
771
772
      /* Alice will pick a new rend point when this one dies, if
       * the stream in question still cares. No need to act here. */
      break;
    case CIRCUIT_PURPOSE_S_CONNECT_REND:
      /* at Bob, connecting to rend point */
      /* Don't increment failure count, since Alice may have picked
       * the rendezvous point maliciously */
773
774
775
      log_info(LD_REND,
               "Couldn't connect to Alice's chosen rend point %s "
               "(%s hop failed).",
776
               escaped(build_state_get_exit_nickname(circ->build_state)),
777
               failed_at_last_hop?"last":"non-last");
778
      rend_service_relaunch_rendezvous(circ);
779
      break;
780
781
782
    /* default:
     * This won't happen in normal operation, but might happen if the
     * controller did it. Just let it slide. */
783
784
785
786
787
788
789
  }
}

/** Number of consecutive failures so far; should only be touched by
 * circuit_launch_new and circuit_*_failure_count.
 */
static int n_circuit_failures = 0;
790
791
/** Before the last time we called circuit_reset_failure_count(), were
 * there a lot of failures? */
792
static int did_circs_fail_last_period = 0;
793
794
795
796
797

/** Don't retry launching a new circuit if we try this many times with no
 * success. */
#define MAX_CIRCUIT_FAILURES 5

798
799
/** Launch a new circuit; see circuit_launch_by_extend_info() for
 * details on arguments. */
800
origin_circuit_t *
801
802
803
circuit_launch_by_router(uint8_t purpose, int onehop_tunnel,
                         routerinfo_t *exit, int need_uptime,
                         int need_capacity, int internal)
Nick Mathewson's avatar
Nick Mathewson committed
804
{
805
  origin_circuit_t *circ;
806
807
808
  extend_info_t *info = NULL;
  if (exit)
    info = extend_info_from_router(exit);
809
  circ = circuit_launch_by_extend_info(
810
    purpose, onehop_tunnel, info, need_uptime, need_capacity, internal);
811
812
813
814
815
816
817
818
819
820
821
  if (info)
    extend_info_free(info);
  return circ;
}

/** Launch a new circuit with purpose <b>purpose</b> and exit node <b>info</b>
 * (or NULL to select a random exit node).  If <b>need_uptime</b> is true,
 * choose among routers with high uptime.  If <b>need_capacity</b> is true,
 * choose among routers with high bandwidth.  If <b>internal</b> is true, the
 * last hop need not be an exit node. Return the newly allocated circuit on
 * success, or NULL on failure. */
822
origin_circuit_t *
823
824
825
circuit_launch_by_extend_info(uint8_t purpose, int onehop_tunnel,
                              extend_info_t *extend_info, int need_uptime,
                              int need_capacity, int internal)
826
{
827
  origin_circuit_t *circ;
828

829
  if (!onehop_tunnel && !router_have_minimum_dir_info()) {
830
831
    log_debug(LD_CIRC,"Haven't fetched enough directory info yet; canceling "
              "circuit launch.");
832
833
834
    return NULL;
  }

835
  if ((extend_info || purpose != CIRCUIT_PURPOSE_C_GENERAL) &&
836
      purpose != CIRCUIT_PURPOSE_TESTING && !onehop_tunnel) {
837
    /* see if there are appropriate circs available to cannibalize. */
838
    circ = circuit_find_to_cannibalize(CIRCUIT_PURPOSE_C_GENERAL, extend_info,
839
840
                                       need_uptime, need_capacity, internal);
    if (circ) {
841
842
      log_info(LD_CIRC,"Cannibalizing circ '%s' for purpose %d",
               build_state_get_exit_nickname(circ->build_state), purpose);
843
      circ->_base.purpose = purpose;
844
845
846
      /* reset the birth date of this circ, else expire_building
       * will see it and think it's been trying to build since it
       * began. */
847
      circ->_base.timestamp_created = time(NULL);
848
849
850
851
852
853
854
      switch (purpose) {
        case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
        case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
          /* it's ready right now */
          break;
        case CIRCUIT_PURPOSE_C_INTRODUCING:
        case CIRCUIT_PURPOSE_S_CONNECT_REND:
855
        case CIRCUIT_PURPOSE_C_GENERAL:
856
          /* need to add a new hop */
857
858
          tor_assert(extend_info);
          if (circuit_extend_to_new_exit(circ, extend_info) < 0)
859
860
861
            return NULL;
          break;
        default:
862
          log_warn(LD_BUG,
863
                   "unexpected purpose %d when cannibalizing a circ.",
864
                   purpose);
865
          tor_fragile_assert();
866
867
868
869
870
871
          return NULL;
      }
      return circ;
    }
  }

872
873
  if (did_circs_fail_last_period &&
      n_circuit_failures > MAX_CIRCUIT_FAILURES) {
874
875
876
877
878
    /* too many failed circs in a row. don't try. */
//    log_fn(LOG_INFO,"%d failures so far, not trying.",n_circuit_failures);
    return NULL;
  }

879
880
  /* try a circ. if it fails, circuit_mark_for_close will increment
   * n_circuit_failures */
881
  return circuit_establish_circuit(purpose, onehop_tunnel, extend_info,
882
                                   need_uptime, need_capacity, internal);
Nick Mathewson's avatar
Nick Mathewson committed
883
884
}

885
886
/** Launch a new circuit; see circuit_launch_by_extend_info() for
 * details on arguments. */
887
origin_circuit_t *
888
889
circuit_launch_by_nickname(uint8_t purpose, int onehop_tunnel,
                           const char *exit_nickname,
890
                           int need_uptime, int need_capacity, int internal)
Nick Mathewson's avatar
Nick Mathewson committed
891
{
892
  routerinfo_t *router = NULL;
Nick Mathewson's avatar
Nick Mathewson committed
893
894

  if (exit_nickname) {
895
    router = router_get_by_nickname(exit_nickname, 1);
896
    if (!router) {
897
898
      log_warn(LD_GENERAL, "Trying to launch circ by nickname, but "
               "no such OR as '%s'", exit_nickname);
Nick Mathewson's avatar
Nick Mathewson committed
899
900
901
      return NULL;
    }
  }
902
  return circuit_launch_by_router(purpose, onehop_tunnel, router,
903
                                  need_uptime, need_capacity, internal);
904
905
906
907
908
}

/** Record another failure at opening a general circuit. When we have
 * too many, we'll stop trying for the remainder of this minute.
 */
909
910
911
static void
circuit_increment_failure_count(void)
{
912
  ++n_circuit_failures;
913
  log_debug(LD_CIRC,"n_circuit_failures now %d.",n_circuit_failures);
914
915
916
917
918
919
}

/** Reset the failure count for opening general circuits. This means
 * we will try MAX_CIRCUIT_FAILURES times more (if necessary) before
 * stopping again.
 */
920
921
922
void
circuit_reset_failure_count(int timeout)
{
923
  if (timeout && n_circuit_failures > MAX_CIRCUIT_FAILURES)
924
925
926
    did_circs_fail_last_period = 1;
  else
    did_circs_fail_last_period = 0;
927
928
929
  n_circuit_failures = 0;
}

930
931
932
/** Find an open circ that we're happy to use for <b>conn</b> and return 1. If
 * there isn't one, and there isn't one on the way, launch one and return
 * 0. If it will never work, return -1.
933
934
935
936
 *
 * Write the found or in-progress or launched circ into *circp.
 */
static int
937
circuit_get_open_circ_or_launch(edge_connection_t *conn,
938
                                uint8_t desired_circuit_purpose,
939
                                origin_circuit_t **circp)
940
{
941
  origin_circuit_t *circ;
942
  int check_exit_policy;
943
  int need_uptime, need_internal;
944
  int want_onehop;
945
946
947

  tor_assert(conn);
  tor_assert(circp);
948
  tor_assert(conn->_base.state == AP_CONN_STATE_CIRCUIT_WAIT);
949
950
951
  check_exit_policy =
      (conn->socks_request->command == SOCKS_COMMAND_CONNECT) &&
      !connection_edge_is_rendezvous_stream(conn);
952
  want_onehop = conn->socks_request->command == SOCKS_COMMAND_CONNECT_DIR;
953

954
955
  need_uptime = (conn->socks_request->command == SOCKS_COMMAND_CONNECT) &&
                smartlist_string_num_isin(get_options()->LongLivedPorts,
956
957
958
959
960
                                          conn->socks_request->port);
  need_internal = desired_circuit_purpose != CIRCUIT_PURPOSE_C_GENERAL;

  circ = circuit_get_best(conn, 1, desired_circuit_purpose,
                          need_uptime, need_internal);
961

962
  if (circ) {
963
964
965
966
    *circp = circ;
    return 1; /* we're happy */
  }

967
  if (!want_onehop && !router_have_minimum_dir_info()) {
968
    if (!connection_get_by_type(CONN_TYPE_DIR)) {
969
970
971
      log_notice(LD_APP|LD_DIR,
                 "Application request when we're believed to be "
                 "offline. Optimistically trying directory fetches again.");
972
973
974
      router_reset_status_download_failures();
      router_reset_descriptor_download_failures();
      update_networkstatus_downloads(time(NULL));
975
      update_router_descriptor_downloads(time(NULL));
976
    }
977
    /* the stream will be dealt with when router_have_minimum_dir_info becomes
978
979
980
981
982
983
     * 1, or when all directory attempts fail and directory_all_unreachable()
     * kills it.
     */
    return 0;
  }

984
  /* Do we need to check exit policy? */
985
  if (check_exit_policy) {
986
987
988
989
    struct in_addr in;
    uint32_t addr = 0;
    if (tor_inet_aton(conn->socks_request->address, &in))
      addr = ntohl(in.s_addr);
990
991
    if (router_exit_policy_all_routers_reject(addr, conn->socks_request->port,
                                              need_uptime)) {
992
993
994
995
      log_notice(LD_APP,
                 "No Tor server exists that allows exit to %s:%d. Rejecting.",
                 safe_str(conn->socks_request->address),
                 conn->socks_request->port);
996
997
998
999
1000
      return -1;
    }
  }

  /* is one already on the way? */