rephist.c 26.2 KB
Newer Older
Nick Mathewson's avatar
Nick Mathewson committed
1
/* Copyright 2004-2005 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
    /* XXXX009 Well, everybody has an ID now. Hm. */
Nick Mathewson's avatar
Nick Mathewson committed
221
    /* If conn has no nickname, it's either an OP, or it is an OR
222
     * which didn't complete its handshake (or did and was unapproved).
Nick Mathewson's avatar
Nick Mathewson committed
223
     * Ignore it.
224
225
226
     */
    return;
  }
227
  hist = get_or_history(id);
228
229
  if (!hist)
    return;
230
231
232
233
234
235
  if (hist->up_since) {
    hist->uptime += (when - hist->up_since);
    hist->up_since = 0;
  }
  if (!hist->down_since)
    hist->down_since = when;
236
  hist->changed = when;
237
238
}

Nick Mathewson's avatar
Nick Mathewson committed
239
240
241
/** 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>.
242
 */
243
244
void
rep_hist_note_extend_succeeded(const char *from_id, const char *to_id)
245
246
{
  link_history_t *hist;
247
  /* log_fn(LOG_WARN, "EXTEND SUCCEEDED: %s->%s",from_name,to_name); */
248
  hist = get_link_history(from_id, to_id);
249
250
  if (!hist)
    return;
251
  ++hist->n_extend_ok;
252
  hist->changed = time(NULL);
253
}
254

Nick Mathewson's avatar
Nick Mathewson committed
255
256
257
/** 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.
258
 */
259
260
void
rep_hist_note_extend_failed(const char *from_id, const char *to_id)
261
262
{
  link_history_t *hist;
263
  /* log_fn(LOG_WARN, "EXTEND FAILED: %s->%s",from_name,to_name); */
264
  hist = get_link_history(from_id, to_id);
265
266
  if (!hist)
    return;
267
  ++hist->n_extend_fail;
268
  hist->changed = time(NULL);
269
270
}

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

291
  rep_history_clean(now - get_options()->RephistTrackTime);
292

293
  log(severity, LD_GENERAL, "--------------- Dumping history information:");
294

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

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

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

333
        link_history = (link_history_t*) link_history_p;
334

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

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

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

385
#define NUM_SECS_ROLLING_MEASURE 10
386
#define NUM_SECS_BW_SUM_IS_VALID (24*60*60) /* one day */
387
388
389
390
#define NUM_SECS_BW_SUM_INTERVAL (15*60)
#define NUM_TOTALS (NUM_SECS_BW_SUM_IS_VALID/NUM_SECS_BW_SUM_INTERVAL)

/**
391
 * Structure to track bandwidth use, and remember the maxima for a given
392
393
394
395
396
 * 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. */
397
  uint64_t obs[NUM_SECS_ROLLING_MEASURE];
398
399
  int cur_obs_idx; /**< Current position in obs. */
  time_t cur_obs_time; /**< Time represented in obs[cur_obs_idx] */
400
401
402
  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. */
403
404
  uint64_t total_in_period; /**< Total bytes transferred in the current
                             * period. */
405
406
407
408
409
410

  /** 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;
411
412
413
414
415
  /** 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 */
416
  uint64_t maxima[NUM_TOTALS];
417
418
  /** Circular array of the total bandwidth usage for the last NUM_TOTALS
   * periods */
419
  uint64_t totals[NUM_TOTALS];
420
421
} bw_array_t;

422
/** Shift the current period of b forward by one.
423
 */
424
425
426
static void
commit_max(bw_array_t *b)
{
427
428
  /* Store total from current period. */
  b->totals[b->next_max_idx] = b->total_in_period;
429
430
431
432
433
434
  /* 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;
435
436
  if (b->num_maxes_set < NUM_TOTALS)
    ++b->num_maxes_set;
437
438
  /* Reset max_total. */
  b->max_total = 0;
439
440
  /* Reset total_in_period. */
  b->total_in_period = 0;
441
442
}

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

  /* 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'.
 */
471
static INLINE void
472
add_obs(bw_array_t *b, time_t when, uint64_t n)
473
{
Nick Mathewson's avatar
Nick Mathewson committed
474
475
476
477
478
479
480
  /* 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)
481
    advance_obs(b);
Nick Mathewson's avatar
Nick Mathewson committed
482

483
  b->obs[b->cur_obs_idx] += n;
484
  b->total_in_period += n;
485
486
487
488
}

/** Allocate, initialize, and return a new bw_array.
 */
489
490
static bw_array_t *
bw_array_new(void)
491
{
492
493
494
  bw_array_t *b;
  time_t start;
  b = tor_malloc_zero(sizeof(bw_array_t));
495
  rephist_total_alloc += sizeof(bw_array_t);
496
497
498
499
500
501
502
503
504
505
506
  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
 */
507
508
static void
bw_arrays_init(void)
509
510
511
512
{
  read_array = bw_array_new();
  write_array = bw_array_new();
}
513
514
515
516
517
518

/** 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
519
 * earlier than the latest <b>when</b> you've heard of.
520
 */
521
522
523
void
rep_hist_note_bytes_written(int num_bytes, time_t when)
{
524
525
526
527
528
529
530
531
/* 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.
 */
532
  add_obs(write_array, when, num_bytes);
533
534
535
536
537
}

/** We wrote <b>num_bytes</b> more bytes in second <b>when</b>.
 * (like rep_hist_note_bytes_written() above)
 */
538
539
540
void
rep_hist_note_bytes_read(int num_bytes, time_t when)
{
541
/* if we're smart, we can make this func and the one above share code */
542
543
544
545
546
547
548
  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.)
 */
549
static uint64_t
550
find_largest_max(bw_array_t *b)
551
{
552
553
  int i;
  uint64_t max;
554
555
556
557
558
559
  max=0;
  for (i=0; i<NUM_TOTALS; ++i) {
    if (b->maxima[i]>max)
      max = b->maxima[i];
  }
  return max;
560
561
562
563
564
565
566
567
568
}

/**
 * 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.
 */
569
570
571
int
rep_hist_bandwidth_assess(void)
{
572
  uint64_t w,r;
573
574
575
  r = find_largest_max(read_array);
  w = find_largest_max(write_array);
  if (r>w)
576
    return (int)(w/(double)NUM_SECS_ROLLING_MEASURE);
577
  else
578
    return (int)(r/(double)NUM_SECS_ROLLING_MEASURE);
579
580
581
582

  return 0;
}

583
584
585
586
587
588
589
/**
 * 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.
 */
590
static size_t
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
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;
}

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

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

650
651
/** Update <b>state</b> with the newest bandwidth history. */
void
652
653
654
655
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
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();
681
682
    if (server_mode(get_options()))
      smartlist_split_string(*s_values, buf, ",", SPLIT_SKIP_SPACE, 0);
683
684
685
686
687
688
689
690
691
692
693
694
695
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
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
  }
  tor_free(buf);
  state->dirty = 1;
}

/** Set bandwidth history from our saved state.
 */
int
rep_hist_load_state(or_state_t *state, const char **err)
{
  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;
          notice(LD_GENERAL, "Could not parse '%s' into a number.'", cp);
        }
        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) {
    if (err)
      *err = "Parsing of bandwidth history values failed";
    /* 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;
}

751
752
753
754
755
/** 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;

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

770
771
772
773
/** DOCDOC */
static void
predicted_ports_init(void)
{
774
775
776
777
778
  predicted_ports_list = smartlist_create();
  predicted_ports_times = smartlist_create();
  add_predicted_port(80, time(NULL)); /* add one to kickstart us */
}

779
780
781
782
/** DOCDOC */
static void
predicted_ports_free(void)
{
783
  rephist_total_alloc -= smartlist_len(predicted_ports_list)*sizeof(uint16_t);
784
785
  SMARTLIST_FOREACH(predicted_ports_list, char *, cp, tor_free(cp));
  smartlist_free(predicted_ports_list);
786
  rephist_total_alloc -= smartlist_len(predicted_ports_times)*sizeof(time_t);
787
788
789
790
  SMARTLIST_FOREACH(predicted_ports_times, char *, cp, tor_free(cp));
  smartlist_free(predicted_ports_times);
}

791
792
/** 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
793
 * future and making exit circuits to anticipate that.
794
 */
795
796
797
void
rep_hist_note_used_port(uint16_t port, time_t now)
{
798
799
800
801
802
803
804
  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
805
  if (!port) /* record nothing */
806
807
808
809
810
811
812
813
814
815
816
817
818
819
    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);
}

820
#define PREDICTED_CIRCS_RELEVANCE_TIME (3600) /* 1 hour */
821

Roger Dingledine's avatar
Roger Dingledine committed
822
/** Return a pointer to the list of port numbers that
823
 * are likely to be asked for in the near future.
Roger Dingledine's avatar
Roger Dingledine committed
824
825
 *
 * The caller promises not to mess with it.
826
 */
827
828
829
smartlist_t *
rep_hist_get_predicted_ports(time_t now)
{
830
831
832
833
834
835
836
837
838
839
  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);
840
    if (*tmp_time + PREDICTED_CIRCS_RELEVANCE_TIME < now) {
841
      tmp_port = smartlist_get(predicted_ports_list, i);
842
      debug(LD_CIRC, "Expiring predicted port %d", *tmp_port);
843
844
      smartlist_del(predicted_ports_list, i);
      smartlist_del(predicted_ports_times, i);
845
      rephist_total_alloc -= sizeof(uint16_t)+sizeof(time_t);
846
847
848
849
850
      tor_free(tmp_port);
      tor_free(tmp_time);
      i--;
    }
  }
Roger Dingledine's avatar
Roger Dingledine committed
851
  return predicted_ports_list;
852
853
}

854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
/** 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

873
/** The last time at which we needed an internal circ. */
874
static time_t predicted_internal_time = 0;
875
/** The last time we needed an internal circ with good uptime. */
876
static time_t predicted_internal_uptime_time = 0;
877
/** The last time we needed an internal circ with good capacity. */
878
static time_t predicted_internal_capacity_time = 0;
879
880

/** Remember that we used an internal circ at time <b>now</b>. */
881
void
882
rep_hist_note_used_internal(time_t now, int need_uptime, int need_capacity)
883
{
884
  predicted_internal_time = now;
885
  if (need_uptime)
886
    predicted_internal_uptime_time = now;
887
  if (need_capacity)
888
    predicted_internal_capacity_time = now;
889
890
891
}

/** Return 1 if we've used an internal circ recently; else return 0. */
892
int
893
894
rep_hist_get_predicted_internal(time_t now, int *need_uptime,
                                int *need_capacity)
895
{
896
897
898
899
  if (!predicted_internal_time) { /* initialize it */
    predicted_internal_time = now;
    predicted_internal_uptime_time = now;
    predicted_internal_capacity_time = now;
900
  }
901
  if (predicted_internal_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
902
    return 0; /* too long ago */
903
  if (predicted_internal_uptime_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
904
    *need_uptime = 1;
905
  if (predicted_internal_capacity_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
906
907
908
909
    *need_capacity = 1;
  return 1;
}

910
911
912
913
/** 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)
914
{
915
  digestmap_free(history_map, free_or_history);
916
917
  tor_free(read_array);
  tor_free(write_array);
918
  predicted_ports_free();
919
}
920