rephist.c 27.1 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
/* Copyright 2004-2006 Roger Dingledine, Nick Mathewson. */
2
3
/* See LICENSE for licensing information */
/* $Id$ */
4
5
const char rephist_c_id[] =
  "$Id$";
6

Nick Mathewson's avatar
Nick Mathewson committed
7
8
/**
 * \file rephist.c
9
10
11
 * \brief Basic history and "reputation" functionality to remember
 *    which servers have worked in the past, how much bandwidth we've
 *    been using, which ports we tend to want, and so on.
Nick Mathewson's avatar
Nick Mathewson committed
12
 **/
13

14
15
#include "or.h"

16
static void bw_arrays_init(void);
17
static void predicted_ports_init(void);
18

19
20
uint64_t rephist_total_alloc=0;
uint32_t rephist_total_num=0;
21

Nick Mathewson's avatar
Nick Mathewson committed
22
/** History of an OR-\>OR link. */
23
typedef struct link_history_t {
Nick Mathewson's avatar
Nick Mathewson committed
24
  /** When did we start tracking this list? */
25
  time_t since;
26
27
  /** When did we most recently note a change to this link */
  time_t changed;
28
  /** How many times did extending from OR1 to OR2 succeed? */
29
  unsigned long n_extend_ok;
Nick Mathewson's avatar
Nick Mathewson committed
30
  /** How many times did extending from OR1 to OR2 fail? */
31
32
33
  unsigned long n_extend_fail;
} link_history_t;

Nick Mathewson's avatar
Nick Mathewson committed
34
/** History of an OR. */
35
typedef struct or_history_t {
Nick Mathewson's avatar
Nick Mathewson committed
36
  /** When did we start tracking this OR? */
37
  time_t since;
38
39
  /** When did we most recently note a change to this OR? */
  time_t changed;
Nick Mathewson's avatar
Nick Mathewson committed
40
  /** How many times did we successfully connect? */
41
  unsigned long n_conn_ok;
Nick Mathewson's avatar
Nick Mathewson committed
42
  /** How many times did we try to connect and fail?*/
43
  unsigned long n_conn_fail;
Nick Mathewson's avatar
Nick Mathewson committed
44
  /** How many seconds have we been connected to this OR before
45
   * 'up_since'? */
46
  unsigned long uptime;
Nick Mathewson's avatar
Nick Mathewson committed
47
  /** How many seconds have we been unable to connect to this OR before
48
   * 'down_since'? */
49
  unsigned long downtime;
Nick Mathewson's avatar
Nick Mathewson committed
50
  /** If nonzero, we have been connected since this time. */
51
  time_t up_since;
Nick Mathewson's avatar
Nick Mathewson committed
52
  /** If nonzero, we have been unable to connect since this time. */
53
  time_t down_since;
Nick Mathewson's avatar
Nick Mathewson committed
54
  /** Map from hex OR2 identity digest to a link_history_t for the link
55
   * from this OR to OR2. */
56
  digestmap_t *link_history_map;
57
58
} or_history_t;

Nick Mathewson's avatar
Nick Mathewson committed
59
/** Map from hex OR identity digest to or_history_t. */
60
static digestmap_t *history_map = NULL;
61

Nick Mathewson's avatar
Nick Mathewson committed
62
/** Return the or_history_t for the named OR, creating it if necessary.
63
 */
64
65
static or_history_t *
get_or_history(const char* id)
66
67
{
  or_history_t *hist;
68

69
  if (!memcmp(id, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0", DIGEST_LEN))
70
71
    return NULL;

72
  hist = digestmap_get(history_map, id);
73
74
  if (!hist) {
    hist = tor_malloc_zero(sizeof(or_history_t));
75
    rephist_total_alloc += sizeof(or_history_t);
76
    rephist_total_num++;
77
    hist->link_history_map = digestmap_new();
78
    hist->since = hist->changed = time(NULL);
79
    digestmap_set(history_map, id, hist);
80
81
82
83
  }
  return hist;
}

Nick Mathewson's avatar
Nick Mathewson committed
84
/** Return the link_history_t for the link from the first named OR to
Nick Mathewson's avatar
Nick Mathewson committed
85
86
 * the second, creating it if necessary. (ORs are identified by
 * identity digest)
87
 */
88
89
static link_history_t *
get_link_history(const char *from_id, const char *to_id)
90
91
92
{
  or_history_t *orhist;
  link_history_t *lhist;
93
  orhist = get_or_history(from_id);
94
95
  if (!orhist)
    return NULL;
96
  if (!memcmp(to_id, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0", DIGEST_LEN))
97
    return NULL;
98
  lhist = (link_history_t*) digestmap_get(orhist->link_history_map, to_id);
99
100
  if (!lhist) {
    lhist = tor_malloc_zero(sizeof(link_history_t));
101
    rephist_total_alloc += sizeof(link_history_t);
102
    lhist->since = lhist->changed = time(NULL);
103
    digestmap_set(orhist->link_history_map, to_id, lhist);
104
105
106
107
  }
  return lhist;
}

108
/** Helper: free storage held by a single link history entry */
109
110
111
static void
_free_link_history(void *val)
{
112
  rephist_total_alloc -= sizeof(link_history_t);
113
114
115
  tor_free(val);
}

116
/** Helper: free storage held by a single OR history entry */
117
static void
118
free_or_history(void *_hist)
119
{
120
  or_history_t *hist = _hist;
121
  digestmap_free(hist->link_history_map, _free_link_history);
122
  rephist_total_alloc -= sizeof(or_history_t);
123
  rephist_total_num--;
124
125
126
  tor_free(hist);
}

Nick Mathewson's avatar
Nick Mathewson committed
127
128
/** Update an or_history_t object <b>hist</b> so that its uptime/downtime
 * count is up-to-date as of <b>when</b>.
129
 */
130
131
static void
update_or_history(or_history_t *hist, time_t when)
132
{
Roger Dingledine's avatar
Roger Dingledine committed
133
  tor_assert(hist);
134
  if (hist->up_since) {
Roger Dingledine's avatar
Roger Dingledine committed
135
    tor_assert(!hist->down_since);
136
137
138
139
140
141
142
143
    hist->uptime += (when - hist->up_since);
    hist->up_since = when;
  } else if (hist->down_since) {
    hist->downtime += (when - hist->down_since);
    hist->down_since = when;
  }
}

Nick Mathewson's avatar
Nick Mathewson committed
144
/** Initialize the static data structures for tracking history.
145
 */
146
147
void
rep_hist_init(void)
148
{
149
  history_map = digestmap_new();
150
  bw_arrays_init();
151
  predicted_ports_init();
152
153
}

Nick Mathewson's avatar
Nick Mathewson committed
154
155
/** Remember that an attempt to connect to the OR with identity digest
 * <b>id</b> failed at <b>when</b>.
156
 */
157
158
void
rep_hist_note_connect_failed(const char* id, time_t when)
159
160
{
  or_history_t *hist;
161
  hist = get_or_history(id);
162
163
  if (!hist)
    return;
164
165
166
167
168
169
170
  ++hist->n_conn_fail;
  if (hist->up_since) {
    hist->uptime += (when - hist->up_since);
    hist->up_since = 0;
  }
  if (!hist->down_since)
    hist->down_since = when;
171
  hist->changed = when;
172
173
}

Nick Mathewson's avatar
Nick Mathewson committed
174
175
/** Remember that an attempt to connect to the OR with identity digest
 * <b>id</b> succeeded at <b>when</b>.
176
 */
177
178
void
rep_hist_note_connect_succeeded(const char* id, time_t when)
179
180
{
  or_history_t *hist;
181
  hist = get_or_history(id);
182
183
  if (!hist)
    return;
184
185
186
187
188
189
190
  ++hist->n_conn_ok;
  if (hist->down_since) {
    hist->downtime += (when - hist->down_since);
    hist->down_since = 0;
  }
  if (!hist->up_since)
    hist->up_since = when;
191
  hist->changed = when;
192
}
193

Nick Mathewson's avatar
Nick Mathewson committed
194
/** Remember that we intentionally closed our connection to the OR
Nick Mathewson's avatar
Nick Mathewson committed
195
 * with identity digest <b>id</b> at <b>when</b>.
196
 */
197
198
void
rep_hist_note_disconnect(const char* id, time_t when)
199
200
{
  or_history_t *hist;
201
  hist = get_or_history(id);
202
203
  if (!hist)
    return;
204
205
206
207
208
  ++hist->n_conn_ok;
  if (hist->up_since) {
    hist->uptime += (when - hist->up_since);
    hist->up_since = 0;
  }
209
  hist->changed = when;
210
211
}

Nick Mathewson's avatar
Nick Mathewson committed
212
213
/** Remember that our connection to the OR with identity digest
 * <b>id</b> had an error and stopped working at <b>when</b>.
214
 */
215
216
void
rep_hist_note_connection_died(const char* id, time_t when)
217
218
{
  or_history_t *hist;
219
  if (!id) {
220
221
    /* If conn has no nickname, it didn't complete its handshake, or something
     * went wrong.  Ignore it.
222
223
224
     */
    return;
  }
225
  hist = get_or_history(id);
226
227
  if (!hist)
    return;
228
229
230
231
232
233
  if (hist->up_since) {
    hist->uptime += (when - hist->up_since);
    hist->up_since = 0;
  }
  if (!hist->down_since)
    hist->down_since = when;
234
  hist->changed = when;
235
236
}

Nick Mathewson's avatar
Nick Mathewson committed
237
238
239
/** Remember that we successfully extended from the OR with identity
 * digest <b>from_id</b> to the OR with identity digest
 *  <b>to_name</b>.
240
 */
241
242
void
rep_hist_note_extend_succeeded(const char *from_id, const char *to_id)
243
244
{
  link_history_t *hist;
245
  /* log_fn(LOG_WARN, "EXTEND SUCCEEDED: %s->%s",from_name,to_name); */
246
  hist = get_link_history(from_id, to_id);
247
248
  if (!hist)
    return;
249
  ++hist->n_extend_ok;
250
  hist->changed = time(NULL);
251
}
252

Nick Mathewson's avatar
Nick Mathewson committed
253
254
255
/** Remember that we tried to extend from the OR with identity digest
 * <b>from_id</b> to the OR with identity digest <b>to_name</b>, but
 * failed.
256
 */
257
258
void
rep_hist_note_extend_failed(const char *from_id, const char *to_id)
259
260
{
  link_history_t *hist;
261
  /* log_fn(LOG_WARN, "EXTEND FAILED: %s->%s",from_name,to_name); */
262
  hist = get_link_history(from_id, to_id);
263
264
  if (!hist)
    return;
265
  ++hist->n_extend_fail;
266
  hist->changed = time(NULL);
267
268
}

269
/** Log all the reliability data we have remembered, with the chosen
270
271
 * severity.
 */
272
273
void
rep_hist_dump_stats(time_t now, int severity)
274
{
275
276
277
278
  digestmap_iter_t *lhist_it;
  digestmap_iter_t *orhist_it;
  const char *name1, *name2, *digest1, *digest2;
  char hexdigest1[HEX_DIGEST_LEN+1];
279
280
  or_history_t *or_history;
  link_history_t *link_history;
281
  void *or_history_p, *link_history_p;
282
283
  double uptime;
  char buffer[2048];
284
  size_t len;
Nick Mathewson's avatar
Nick Mathewson committed
285
  int ret;
286
  unsigned long upt, downt;
287
  routerinfo_t *r;
288

289
  rep_history_clean(now - get_options()->RephistTrackTime);
290

291
  log(severity, LD_GENERAL, "--------------- Dumping history information:");
292

293
294
  for (orhist_it = digestmap_iter_init(history_map);
       !digestmap_iter_done(orhist_it);
295
296
       orhist_it = digestmap_iter_next(history_map,orhist_it)) {
    digestmap_iter_get(orhist_it, &digest1, &or_history_p);
297
    or_history = (or_history_t*) or_history_p;
298

299
    if ((r = router_get_by_digest(digest1)))
300
301
302
      name1 = r->nickname;
    else
      name1 = "(unknown)";
303
    base16_encode(hexdigest1, sizeof(hexdigest1), digest1, DIGEST_LEN);
304
    update_or_history(or_history, now);
305
306
307
308
309
310
311
    upt = or_history->uptime;
    downt = or_history->downtime;
    if (upt+downt) {
      uptime = ((double)upt) / (upt+downt);
    } else {
      uptime=1.0;
    }
312
    log(severity, LD_GENERAL,
313
314
        "OR %s [%s]: %ld/%ld good connections; uptime %ld/%ld sec (%.2f%%)",
        name1, hexdigest1,
Roger Dingledine's avatar
tabs    
Roger Dingledine committed
315
        or_history->n_conn_ok, or_history->n_conn_fail+or_history->n_conn_ok,
316
        upt, upt+downt, uptime*100.0);
317

318
    if (!digestmap_isempty(or_history->link_history_map)) {
319
      strlcpy(buffer, "    Extend attempts: ", sizeof(buffer));
320
      len = strlen(buffer);
321
322
      for (lhist_it = digestmap_iter_init(or_history->link_history_map);
           !digestmap_iter_done(lhist_it);
323
324
           lhist_it = digestmap_iter_next(or_history->link_history_map,
                                          lhist_it)) {
325
326
        digestmap_iter_get(lhist_it, &digest2, &link_history_p);
        if ((r = router_get_by_digest(digest2)))
327
328
329
          name2 = r->nickname;
        else
          name2 = "(unknown)";
330

331
        link_history = (link_history_t*) link_history_p;
332

Nick Mathewson's avatar
Nick Mathewson committed
333
        ret = tor_snprintf(buffer+len, 2048-len, "%s(%ld/%ld); ", name2,
334
335
                        link_history->n_extend_ok,
                        link_history->n_extend_ok+link_history->n_extend_fail);
Nick Mathewson's avatar
Nick Mathewson committed
336
        if (ret<0)
337
          break;
Nick Mathewson's avatar
Nick Mathewson committed
338
        else
Nick Mathewson's avatar
Nick Mathewson committed
339
          len += ret;
340
      }
341
      log(severity, LD_GENERAL, "%s", buffer);
342
343
344
345
    }
  }
}

346
347
/** Remove history info for routers/links that haven't changed since
 * <b>before</b> */
348
349
void
rep_history_clean(time_t before)
350
351
352
353
{
  or_history_t *or_history;
  link_history_t *link_history;
  void *or_history_p, *link_history_p;
354
355
  digestmap_iter_t *orhist_it, *lhist_it;
  const char *d1, *d2;
356

357
358
359
  orhist_it = digestmap_iter_init(history_map);
  while (!digestmap_iter_done(orhist_it)) {
    digestmap_iter_get(orhist_it, &d1, &or_history_p);
360
361
    or_history = or_history_p;
    if (or_history->changed < before) {
362
      orhist_it = digestmap_iter_next_rmv(history_map, orhist_it);
363
      free_or_history(or_history);
364
365
      continue;
    }
366
367
368
    for (lhist_it = digestmap_iter_init(or_history->link_history_map);
         !digestmap_iter_done(lhist_it); ) {
      digestmap_iter_get(lhist_it, &d2, &link_history_p);
369
370
      link_history = link_history_p;
      if (link_history->changed < before) {
371
372
        lhist_it = digestmap_iter_next_rmv(or_history->link_history_map,
                                           lhist_it);
373
        rephist_total_alloc -= sizeof(link_history_t);
374
375
376
        tor_free(link_history);
        continue;
      }
377
      lhist_it = digestmap_iter_next(or_history->link_history_map,lhist_it);
378
    }
379
    orhist_it = digestmap_iter_next(history_map, orhist_it);
380
381
382
  }
}

383
384
/** For how many seconds do we keep track of individual per-second bandwidth
 * totals? */
385
#define NUM_SECS_ROLLING_MEASURE 10
386
/** How large are the intervals for with we track and report bandwidth use? */
387
#define NUM_SECS_BW_SUM_INTERVAL (15*60)
388
389
390
/** How far in the past do we remember and publish bandwidth use? */
#define NUM_SECS_BW_SUM_IS_VALID (24*60*60)
/** How many bandwidth usage intervals do we remember? (derived.) */
391
392
393
#define NUM_TOTALS (NUM_SECS_BW_SUM_IS_VALID/NUM_SECS_BW_SUM_INTERVAL)

/**
394
 * Structure to track bandwidth use, and remember the maxima for a given
395
396
397
398
399
 * time period.
 */
typedef struct bw_array_t {
  /** Observation array: Total number of bytes transferred in each of the last
   * NUM_SECS_ROLLING_MEASURE seconds. This is used as a circular array. */
400
  uint64_t obs[NUM_SECS_ROLLING_MEASURE];
401
402
  int cur_obs_idx; /**< Current position in obs. */
  time_t cur_obs_time; /**< Time represented in obs[cur_obs_idx] */
Nick Mathewson's avatar
Nick Mathewson committed
403
404
405
406
  uint64_t total_obs; /**< Total for all members of obs except
                       * obs[cur_obs_idx] */
  uint64_t max_total; /**< Largest value that total_obs has taken on in the
                       * current period. */
407
408
  uint64_t total_in_period; /**< Total bytes transferred in the current
                             * period. */
409
410
411
412
413
414

  /** When does the next period begin? */
  time_t next_period;
  /** Where in 'maxima' should the maximum bandwidth usage for the current
   * period be stored? */
  int next_max_idx;
415
416
417
418
419
  /** How many values in maxima/totals have been set ever? */
  int num_maxes_set;
  /** Circular array of the maximum
   * bandwidth-per-NUM_SECS_ROLLING_MEASURE usage for the last
   * NUM_TOTALS periods */
420
  uint64_t maxima[NUM_TOTALS];
421
422
  /** Circular array of the total bandwidth usage for the last NUM_TOTALS
   * periods */
423
  uint64_t totals[NUM_TOTALS];
424
425
} bw_array_t;

426
/** Shift the current period of b forward by one.
427
 */
428
429
430
static void
commit_max(bw_array_t *b)
{
431
432
  /* Store total from current period. */
  b->totals[b->next_max_idx] = b->total_in_period;
433
434
435
436
437
438
  /* Store maximum from current period. */
  b->maxima[b->next_max_idx++] = b->max_total;
  /* Advance next_period and next_max_idx */
  b->next_period += NUM_SECS_BW_SUM_INTERVAL;
  if (b->next_max_idx == NUM_TOTALS)
    b->next_max_idx = 0;
439
440
  if (b->num_maxes_set < NUM_TOTALS)
    ++b->num_maxes_set;
441
442
  /* Reset max_total. */
  b->max_total = 0;
443
444
  /* Reset total_in_period. */
  b->total_in_period = 0;
445
446
}

447
/** Shift the current observation time of 'b' forward by one second.
448
 */
449
450
451
static INLINE void
advance_obs(bw_array_t *b)
{
452
  int nextidx;
453
  uint64_t total;
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474

  /* Calculate the total bandwidth for the last NUM_SECS_ROLLING_MEASURE
   * seconds; adjust max_total as needed.*/
  total = b->total_obs + b->obs[b->cur_obs_idx];
  if (total > b->max_total)
    b->max_total = total;

  nextidx = b->cur_obs_idx+1;
  if (nextidx == NUM_SECS_ROLLING_MEASURE)
    nextidx = 0;

  b->total_obs = total - b->obs[nextidx];
  b->obs[nextidx]=0;
  b->cur_obs_idx = nextidx;

  if (++b->cur_obs_time >= b->next_period)
    commit_max(b);
}

/** Add 'n' bytes to the number of bytes in b for second 'when'.
 */
475
static INLINE void
476
add_obs(bw_array_t *b, time_t when, uint64_t n)
477
{
Nick Mathewson's avatar
Nick Mathewson committed
478
479
480
481
482
483
484
  /* Don't record data in the past. */
  if (when<b->cur_obs_time)
    return;
  /* If we're currently adding observations for an earlier second than
   * 'when', advance b->cur_obs_time and b->cur_obs_idx by an
   * appropriate number of seconds, and do all the other housekeeping */
  while (when>b->cur_obs_time)
485
    advance_obs(b);
Nick Mathewson's avatar
Nick Mathewson committed
486

487
  b->obs[b->cur_obs_idx] += n;
488
  b->total_in_period += n;
489
490
491
492
}

/** Allocate, initialize, and return a new bw_array.
 */
493
494
static bw_array_t *
bw_array_new(void)
495
{
496
497
498
  bw_array_t *b;
  time_t start;
  b = tor_malloc_zero(sizeof(bw_array_t));
499
  rephist_total_alloc += sizeof(bw_array_t);
500
501
502
503
504
505
506
507
508
509
510
  start = time(NULL);
  b->cur_obs_time = start;
  b->next_period = start + NUM_SECS_BW_SUM_INTERVAL;
  return b;
}

static bw_array_t *read_array = NULL;
static bw_array_t *write_array = NULL;

/** Set up read_array and write_array
 */
511
512
static void
bw_arrays_init(void)
513
514
515
516
{
  read_array = bw_array_new();
  write_array = bw_array_new();
}
517
518
519
520
521
522

/** We read <b>num_bytes</b> more bytes in second <b>when</b>.
 *
 * Add num_bytes to the current running total for <b>when</b>.
 *
 * <b>when</b> can go back to time, but it's safe to ignore calls
523
 * earlier than the latest <b>when</b> you've heard of.
524
 */
525
526
527
void
rep_hist_note_bytes_written(int num_bytes, time_t when)
{
528
529
530
531
532
533
534
535
/* Maybe a circular array for recent seconds, and step to a new point
 * every time a new second shows up. Or simpler is to just to have
 * a normal array and push down each item every second; it's short.
 */
/* When a new second has rolled over, compute the sum of the bytes we've
 * seen over when-1 to when-1-NUM_SECS_ROLLING_MEASURE, and stick it
 * somewhere. See rep_hist_bandwidth_assess() below.
 */
536
  add_obs(write_array, when, num_bytes);
537
538
539
540
541
}

/** We wrote <b>num_bytes</b> more bytes in second <b>when</b>.
 * (like rep_hist_note_bytes_written() above)
 */
542
543
544
void
rep_hist_note_bytes_read(int num_bytes, time_t when)
{
545
/* if we're smart, we can make this func and the one above share code */
546
547
548
549
550
551
552
  add_obs(read_array, when, num_bytes);
}

/** Helper: Return the largest value in b->maxima.  (This is equal to the
 * most bandwidth used in any NUM_SECS_ROLLING_MEASURE period for the last
 * NUM_SECS_BW_SUM_IS_VALID seconds.)
 */
553
static uint64_t
554
find_largest_max(bw_array_t *b)
555
{
556
557
  int i;
  uint64_t max;
558
559
560
561
562
563
  max=0;
  for (i=0; i<NUM_TOTALS; ++i) {
    if (b->maxima[i]>max)
      max = b->maxima[i];
  }
  return max;
564
565
566
567
568
569
570
571
572
}

/**
 * Find the largest sums in the past NUM_SECS_BW_SUM_IS_VALID (roughly)
 * seconds. Find one sum for reading and one for writing. They don't have
 * to be at the same time).
 *
 * Return the smaller of these sums, divided by NUM_SECS_ROLLING_MEASURE.
 */
573
574
575
int
rep_hist_bandwidth_assess(void)
{
576
  uint64_t w,r;
577
578
579
  r = find_largest_max(read_array);
  w = find_largest_max(write_array);
  if (r>w)
580
    return (int)(w/(double)NUM_SECS_ROLLING_MEASURE);
581
  else
582
    return (int)(r/(double)NUM_SECS_ROLLING_MEASURE);
583
584
585
586

  return 0;
}

587
588
589
590
591
592
593
/**
 * Print the bandwidth history of b (either read_array or write_array)
 * into the buffer pointed to by buf.  The format is simply comma
 * separated numbers, from oldest to newest.
 *
 * It returns the number of bytes written.
 */
594
static size_t
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
rep_hist_fill_bandwidth_history(char *buf, size_t len, bw_array_t *b)
{
  char *cp = buf;
  int i, n;

  if (b->num_maxes_set <= b->next_max_idx) {
    /* We haven't been through the circular array yet; time starts at i=0.*/
    i = 0;
  } else {
    /* We've been around the array at least once.  The next i to be
       overwritten is the oldest. */
    i = b->next_max_idx;
  }

  for (n=0; n<b->num_maxes_set; ++n,++i) {
    while (i >= NUM_TOTALS) i -= NUM_TOTALS;
    if (n==(b->num_maxes_set-1))
      tor_snprintf(cp, len-(cp-buf), U64_FORMAT,
                   U64_PRINTF_ARG(b->totals[i]));
    else
      tor_snprintf(cp, len-(cp-buf), U64_FORMAT",",
                   U64_PRINTF_ARG(b->totals[i]));
    cp += strlen(cp);
  }
  return cp-buf;
}

622
/**
623
624
 * Allocate and return lines for representing this server's bandwidth
 * history in its descriptor.
625
 */
626
627
char *
rep_hist_get_bandwidth_lines(void)
628
629
630
{
  char *buf, *cp;
  char t[ISO_TIME_LEN+1];
631
  int r;
632
633
634
  bw_array_t *b;
  size_t len;

635
  /* opt (read|write)-history yyyy-mm-dd HH:MM:SS (n s) n,n,n,n,n... */
636
  len = (60+20*NUM_TOTALS)*2;
637
638
639
640
  buf = tor_malloc_zero(len);
  cp = buf;
  for (r=0;r<2;++r) {
    b = r?read_array:write_array;
641
    tor_assert(b);
642
    format_iso_time(t, b->next_period-NUM_SECS_BW_SUM_INTERVAL);
643
    tor_snprintf(cp, len-(cp-buf), "opt %s %s (%d s) ",
644
                 r ? "read-history" : "write-history", t,
645
                 NUM_SECS_BW_SUM_INTERVAL);
646
    cp += strlen(cp);
647
    cp += rep_hist_fill_bandwidth_history(cp, len-(cp-buf), b);
648
    strlcat(cp, "\n", len-(cp-buf));
649
650
651
652
653
    ++cp;
  }
  return buf;
}

654
655
/** Update <b>state</b> with the newest bandwidth history. */
void
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
rep_hist_update_state(or_state_t *state)
{
  int len, r;
  char *buf, *cp;
  smartlist_t **s_values;
  time_t *s_begins;
  int *s_interval;
  bw_array_t *b;

  len = 20*NUM_TOTALS+1;
  buf = tor_malloc_zero(len);

  for (r=0;r<2;++r) {
    b = r?read_array:write_array;
    s_begins  = r?&state->BWHistoryReadEnds    :&state->BWHistoryWriteEnds;
    s_interval= r?&state->BWHistoryReadInterval:&state->BWHistoryWriteInterval;
    s_values  = r?&state->BWHistoryReadValues  :&state->BWHistoryWriteValues;

    *s_begins = b->next_period;
    *s_interval = NUM_SECS_BW_SUM_INTERVAL;
    if (*s_values) {
      SMARTLIST_FOREACH(*s_values, char *, cp, tor_free(cp));
      smartlist_free(*s_values);
    }
    cp = buf;
    cp += rep_hist_fill_bandwidth_history(cp, len, b);
    tor_snprintf(cp, len-(cp-buf), cp == buf ? U64_FORMAT : ","U64_FORMAT,
                 U64_PRINTF_ARG(b->total_in_period));
    *s_values = smartlist_create();
685
686
    if (server_mode(get_options()))
      smartlist_split_string(*s_values, buf, ",", SPLIT_SKIP_SPACE, 0);
687
688
689
690
691
692
693
694
  }
  tor_free(buf);
  state->dirty = 1;
}

/** Set bandwidth history from our saved state.
 */
int
695
rep_hist_load_state(or_state_t *state, char **err)
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
{
  time_t s_begins, start;
  time_t now = time(NULL);
  uint64_t v;
  int r,i,ok;
  int all_ok = 1;
  int s_interval;
  smartlist_t *s_values;
  bw_array_t *b;

  /* Assert they already have been malloced */
  tor_assert(read_array && write_array);

  for (r=0;r<2;++r) {
    b = r?read_array:write_array;
    s_begins = r?state->BWHistoryReadEnds:state->BWHistoryWriteEnds;
    s_interval =  r?state->BWHistoryReadInterval:state->BWHistoryWriteInterval;
    s_values =  r?state->BWHistoryReadValues:state->BWHistoryWriteValues;
    if (s_values && s_begins >= now - NUM_SECS_BW_SUM_INTERVAL*NUM_TOTALS) {
      start = s_begins - s_interval*(smartlist_len(s_values));

      b->cur_obs_time = start;
      b->next_period = start + NUM_SECS_BW_SUM_INTERVAL;
      SMARTLIST_FOREACH(s_values, char *, cp, {
        v = tor_parse_uint64(cp, 10, 0, UINT64_MAX, &ok, NULL);
        if (!ok) {
          all_ok=0;
723
          log_notice(LD_GENERAL, "Could not parse '%s' into a number.'", cp);
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
        }
        add_obs(b, start, v);
        start += NUM_SECS_BW_SUM_INTERVAL;
      });
    }

    /* Clean up maxima and observed */
    /* Do we really want to zero this for the purpose of max capacity? */
    for (i=0; i<NUM_SECS_ROLLING_MEASURE; ++i) {
      b->obs[i] = 0;
    }
    b->total_obs = 0;
    for (i=0; i<NUM_TOTALS; ++i) {
      b->maxima[i] = 0;
    }
    b->max_total = 0;
  }

  if (!all_ok) {
743
    *err = tor_strdup("Parsing of bandwidth history values failed");
744
745
746
747
748
749
750
751
752
753
    /* and create fresh arrays */
    tor_free(read_array);
    tor_free(write_array);
    read_array = bw_array_new();
    write_array = bw_array_new();
    return -1;
  }
  return 0;
}

754
755
/*********************************************************************/

756
757
758
759
760
/** A list of port numbers that have been used recently. */
static smartlist_t *predicted_ports_list=NULL;
/** The corresponding most recently used time for each port. */
static smartlist_t *predicted_ports_times=NULL;

761
762
763
764
/** DOCDOC */
static void
add_predicted_port(uint16_t port, time_t now)
{
765
  /* XXXX we could just use uintptr_t here, I think. */
766
767
768
769
  uint16_t *tmp_port = tor_malloc(sizeof(uint16_t));
  time_t *tmp_time = tor_malloc(sizeof(time_t));
  *tmp_port = port;
  *tmp_time = now;
770
  rephist_total_alloc += sizeof(uint16_t) + sizeof(time_t);
771
772
773
774
  smartlist_add(predicted_ports_list, tmp_port);
  smartlist_add(predicted_ports_times, tmp_time);
}

775
776
777
778
/** DOCDOC */
static void
predicted_ports_init(void)
{
779
780
781
782
783
  predicted_ports_list = smartlist_create();
  predicted_ports_times = smartlist_create();
  add_predicted_port(80, time(NULL)); /* add one to kickstart us */
}

784
785
786
787
/** DOCDOC */
static void
predicted_ports_free(void)
{
788
  rephist_total_alloc -= smartlist_len(predicted_ports_list)*sizeof(uint16_t);
789
790
  SMARTLIST_FOREACH(predicted_ports_list, char *, cp, tor_free(cp));
  smartlist_free(predicted_ports_list);
791
  rephist_total_alloc -= smartlist_len(predicted_ports_times)*sizeof(time_t);
792
793
794
795
  SMARTLIST_FOREACH(predicted_ports_times, char *, cp, tor_free(cp));
  smartlist_free(predicted_ports_times);
}

796
797
/** Remember that <b>port</b> has been asked for as of time <b>now</b>.
 * This is used for predicting what sorts of streams we'll make in the
798
 * future and making exit circuits to anticipate that.
799
 */
800
801
802
void
rep_hist_note_used_port(uint16_t port, time_t now)
{
803
804
805
806
807
808
809
  int i;
  uint16_t *tmp_port;
  time_t *tmp_time;

  tor_assert(predicted_ports_list);
  tor_assert(predicted_ports_times);

Nick Mathewson's avatar
Nick Mathewson committed
810
  if (!port) /* record nothing */
811
812
813
814
815
816
817
818
819
820
821
822
823
824
    return;

  for (i = 0; i < smartlist_len(predicted_ports_list); ++i) {
    tmp_port = smartlist_get(predicted_ports_list, i);
    tmp_time = smartlist_get(predicted_ports_times, i);
    if (*tmp_port == port) {
      *tmp_time = now;
      return;
    }
  }
  /* it's not there yet; we need to add it */
  add_predicted_port(port, now);
}

825
826
827
/** For this long after we've seen a request for a given port, assume that
 * we'll want to make connections to the same port in the future.  */
#define PREDICTED_CIRCS_RELEVANCE_TIME (60*60)
828

Roger Dingledine's avatar
Roger Dingledine committed
829
/** Return a pointer to the list of port numbers that
830
 * are likely to be asked for in the near future.
Roger Dingledine's avatar
Roger Dingledine committed
831
832
 *
 * The caller promises not to mess with it.
833
 */
834
835
836
smartlist_t *
rep_hist_get_predicted_ports(time_t now)
{
837
838
839
840
841
842
843
844
845
846
  int i;
  uint16_t *tmp_port;
  time_t *tmp_time;

  tor_assert(predicted_ports_list);
  tor_assert(predicted_ports_times);

  /* clean out obsolete entries */
  for (i = 0; i < smartlist_len(predicted_ports_list); ++i) {
    tmp_time = smartlist_get(predicted_ports_times, i);
847
    if (*tmp_time + PREDICTED_CIRCS_RELEVANCE_TIME < now) {
848
      tmp_port = smartlist_get(predicted_ports_list, i);
849
      log_debug(LD_CIRC, "Expiring predicted port %d", *tmp_port);
850
851
      smartlist_del(predicted_ports_list, i);
      smartlist_del(predicted_ports_times, i);
852
      rephist_total_alloc -= sizeof(uint16_t)+sizeof(time_t);
853
854
855
856
857
      tor_free(tmp_port);
      tor_free(tmp_time);
      i--;
    }
  }
Roger Dingledine's avatar
Roger Dingledine committed
858
  return predicted_ports_list;
859
860
}

861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
/** The user asked us to do a resolve. Rather than keeping track of
 * timings and such of resolves, we fake it for now by making treating
 * it the same way as a connection to port 80. This way we will continue
 * to have circuits lying around if the user only uses Tor for resolves.
 */
void
rep_hist_note_used_resolve(time_t now)
{
  rep_hist_note_used_port(80, now);
}

#if 0
int
rep_hist_get_predicted_resolve(time_t now)
{
  return 0;
}
#endif

880
/** The last time at which we needed an internal circ. */
881
static time_t predicted_internal_time = 0;
882
/** The last time we needed an internal circ with good uptime. */
883
static time_t predicted_internal_uptime_time = 0;
884
/** The last time we needed an internal circ with good capacity. */
885
static time_t predicted_internal_capacity_time = 0;
886
887

/** Remember that we used an internal circ at time <b>now</b>. */
888
void
889
rep_hist_note_used_internal(time_t now, int need_uptime, int need_capacity)
890
{
891
  predicted_internal_time = now;
892
  if (need_uptime)
893
    predicted_internal_uptime_time = now;
894
  if (need_capacity)
895
    predicted_internal_capacity_time = now;
896
897
898
}

/** Return 1 if we've used an internal circ recently; else return 0. */
899
int
900
901
rep_hist_get_predicted_internal(time_t now, int *need_uptime,
                                int *need_capacity)
902
{
903
904
905
906
  if (!predicted_internal_time) { /* initialize it */
    predicted_internal_time = now;
    predicted_internal_uptime_time = now;
    predicted_internal_capacity_time = now;
907
  }
908
  if (predicted_internal_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
909
    return 0; /* too long ago */
910
  if (predicted_internal_uptime_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
911
    *need_uptime = 1;
912
  if (predicted_internal_capacity_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
913
914
915
916
    *need_capacity = 1;
  return 1;
}

917
918
919
920
/** Return 1 if we have no need for circuits currently, else return 0. */
int
rep_hist_circbuilding_dormant(void)
{
921
922
  /* Any ports used lately? These are pre-seeded if we just started
   * up or if we're running a hidden service. */
923
  if (predicted_ports_list || predicted_internal_time)
924
925
926
    return 0;

  /* see if we'll still need to build testing circuits */
927
  if (server_mode(get_options()) && !check_whether_orport_reachable())
928
929
930
931
    return 0;
  if (!check_whether_dirport_reachable())
    return 0;

932
933
934
  return 1;
}

935
936
937
938
/** Free all storage held by the OR/link history caches, by the
 * bandwidth history arrays, or by the port history. */
void
rep_hist_free_all(void)
939
{
940
  digestmap_free(history_map, free_or_history);
941
942
  tor_free(read_array);
  tor_free(write_array);
943
  predicted_ports_free();
944
}
945