rephist.c 26.1 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
397
398
399
400
401
402
 * 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. */
  int obs[NUM_SECS_ROLLING_MEASURE];
  int cur_obs_idx; /**< Current position in obs. */
  time_t cur_obs_time; /**< Time represented in obs[cur_obs_idx] */
  int total_obs; /**< Total for all members of obs except obs[cur_obs_idx] */
  int 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
  int 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
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
  int nextidx;
  int total;

  /* 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
472
473
static INLINE void
add_obs(bw_array_t *b, time_t when, int n)
{
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
550
static int
find_largest_max(bw_array_t *b)
551
552
553
554
555
556
557
558
{
  int i,max;
  max=0;
  for (i=0; i<NUM_TOTALS; ++i) {
    if (b->maxima[i]>max)
      max = b->maxima[i];
  }
  return max;
559
560
561
562
563
564
565
566
567
}

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

  return 0;
}

582
583
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
/**
 * 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.
 */
size_t
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;
}

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

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

649
650
/** Update <b>state</b> with the newest bandwidth history. */
void
651
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
681
682
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
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();
    smartlist_split_string(*s_values, buf, ",", SPLIT_SKIP_SPACE, 0);
  }
  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;
}

749
750
751
752
753
/** 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;

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

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

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

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

818
#define PREDICTED_CIRCS_RELEVANCE_TIME (3600) /* 1 hour */
819

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

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

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

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

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

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