rephist.c 22 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
const char rephist_c_id[] = "$Id$";
5

Nick Mathewson's avatar
Nick Mathewson committed
6
7
8
9
/**
 * \file rephist.c
 * \brief Basic history functionality for reputation module.
 **/
10

11
12
#include "or.h"

13
static void bw_arrays_init(void);
14
static void predicted_ports_init(void);
15

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

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

Nick Mathewson's avatar
Nick Mathewson committed
53
/** Map from hex OR identity digest to or_history_t. */
54
static strmap_t *history_map = NULL;
55

Nick Mathewson's avatar
Nick Mathewson committed
56
/** Return the or_history_t for the named OR, creating it if necessary.
57
 */
58
static or_history_t *get_or_history(const char* id)
59
60
{
  or_history_t *hist;
61
62
63
  char hexid[HEX_DIGEST_LEN+1];
  base16_encode(hexid, HEX_DIGEST_LEN+1, id, DIGEST_LEN);

64
65
66
  if (!strcmp(hexid, "0000000000000000000000000000000000000000"))
    return NULL;

67
  hist = (or_history_t*) strmap_get(history_map, hexid);
68
69
70
  if (!hist) {
    hist = tor_malloc_zero(sizeof(or_history_t));
    hist->link_history_map = strmap_new();
71
    hist->since = hist->changed = time(NULL);
72
    strmap_set(history_map, hexid, hist);
73
74
75
76
  }
  return hist;
}

Nick Mathewson's avatar
Nick Mathewson committed
77
/** Return the link_history_t for the link from the first named OR to
Nick Mathewson's avatar
Nick Mathewson committed
78
79
 * the second, creating it if necessary. (ORs are identified by
 * identity digest)
80
 */
81
82
static link_history_t *get_link_history(const char *from_id,
                                        const char *to_id)
83
84
85
{
  or_history_t *orhist;
  link_history_t *lhist;
86
87
  char to_hexid[HEX_DIGEST_LEN+1];
  orhist = get_or_history(from_id);
88
89
  if (!orhist)
    return NULL;
90
  base16_encode(to_hexid, HEX_DIGEST_LEN+1, to_id, DIGEST_LEN);
Nick Mathewson's avatar
Nick Mathewson committed
91
  if (!strcmp(to_hexid, "0000000000000000000000000000000000000000"))
92
    return NULL;
93
  lhist = (link_history_t*) strmap_get(orhist->link_history_map, to_hexid);
94
95
  if (!lhist) {
    lhist = tor_malloc_zero(sizeof(link_history_t));
96
    lhist->since = lhist->changed = time(NULL);
97
    strmap_set(orhist->link_history_map, to_hexid, lhist);
98
99
100
101
  }
  return lhist;
}

102
103
104
105
106
107
108
static void
_free_link_history(void *val)
{
  tor_free(val);
}

static void
109
free_or_history(void *_hist)
110
{
111
  or_history_t *hist = _hist;
112
113
114
115
  strmap_free(hist->link_history_map, _free_link_history);
  tor_free(hist);
}

Nick Mathewson's avatar
Nick Mathewson committed
116
117
/** Update an or_history_t object <b>hist</b> so that its uptime/downtime
 * count is up-to-date as of <b>when</b>.
118
 */
119
120
static void update_or_history(or_history_t *hist, time_t when)
{
Roger Dingledine's avatar
Roger Dingledine committed
121
  tor_assert(hist);
122
  if (hist->up_since) {
Roger Dingledine's avatar
Roger Dingledine committed
123
    tor_assert(!hist->down_since);
124
125
126
127
128
129
130
131
    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
132
/** Initialize the static data structures for tracking history.
133
 */
134
135
136
void rep_hist_init(void)
{
  history_map = strmap_new();
137
  bw_arrays_init();
138
  predicted_ports_init();
139
140
}

Nick Mathewson's avatar
Nick Mathewson committed
141
142
/** Remember that an attempt to connect to the OR with identity digest
 * <b>id</b> failed at <b>when</b>.
143
 */
144
void rep_hist_note_connect_failed(const char* id, time_t when)
145
146
{
  or_history_t *hist;
147
  hist = get_or_history(id);
148
149
  if (!hist)
    return;
150
151
152
153
154
155
156
  ++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;
157
  hist->changed = when;
158
159
}

Nick Mathewson's avatar
Nick Mathewson committed
160
161
/** Remember that an attempt to connect to the OR with identity digest
 * <b>id</b> succeeded at <b>when</b>.
162
 */
163
void rep_hist_note_connect_succeeded(const char* id, time_t when)
164
165
{
  or_history_t *hist;
166
  hist = get_or_history(id);
167
168
  if (!hist)
    return;
169
170
171
172
173
174
175
  ++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;
176
  hist->changed = when;
177
}
178

Nick Mathewson's avatar
Nick Mathewson committed
179
/** Remember that we intentionally closed our connection to the OR
Nick Mathewson's avatar
Nick Mathewson committed
180
 * with identity digest <b>id</b> at <b>when</b>.
181
 */
182
void rep_hist_note_disconnect(const char* id, time_t when)
183
184
{
  or_history_t *hist;
185
  hist = get_or_history(id);
186
187
  if (!hist)
    return;
188
189
190
191
192
  ++hist->n_conn_ok;
  if (hist->up_since) {
    hist->uptime += (when - hist->up_since);
    hist->up_since = 0;
  }
193
  hist->changed = when;
194
195
}

Nick Mathewson's avatar
Nick Mathewson committed
196
197
/** Remember that our connection to the OR with identity digest
 * <b>id</b> had an error and stopped working at <b>when</b>.
198
 */
199
void rep_hist_note_connection_died(const char* id, time_t when)
200
201
{
  or_history_t *hist;
202
  if (!id) {
203
    /* XXXX009 Well, everybody has an ID now. Hm. */
Nick Mathewson's avatar
Nick Mathewson committed
204
    /* If conn has no nickname, it's either an OP, or it is an OR
205
     * which didn't complete its handshake (or did and was unapproved).
Nick Mathewson's avatar
Nick Mathewson committed
206
     * Ignore it.
207
208
209
     */
    return;
  }
210
  hist = get_or_history(id);
211
212
  if (!hist)
    return;
213
214
215
216
217
218
  if (hist->up_since) {
    hist->uptime += (when - hist->up_since);
    hist->up_since = 0;
  }
  if (!hist->down_since)
    hist->down_since = when;
219
  hist->changed = when;
220
221
}

Nick Mathewson's avatar
Nick Mathewson committed
222
223
224
/** 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>.
225
 */
226
227
void rep_hist_note_extend_succeeded(const char *from_id,
                                    const char *to_id)
228
229
{
  link_history_t *hist;
230
  /* log_fn(LOG_WARN, "EXTEND SUCCEEDED: %s->%s",from_name,to_name); */
231
  hist = get_link_history(from_id, to_id);
232
233
  if (!hist)
    return;
234
  ++hist->n_extend_ok;
235
  hist->changed = time(NULL);
236
}
237

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

253
/** Log all the reliability data we have remembered, with the chosen
254
255
256
 * severity.
 */
void rep_hist_dump_stats(time_t now, int severity)
257
258
259
{
  strmap_iter_t *lhist_it;
  strmap_iter_t *orhist_it;
260
  const char *name1, *name2, *hexdigest1, *hexdigest2;
261
262
  or_history_t *or_history;
  link_history_t *link_history;
263
  void *or_history_p, *link_history_p;
264
265
  double uptime;
  char buffer[2048];
266
  size_t len;
Nick Mathewson's avatar
Nick Mathewson committed
267
  int ret;
268
  unsigned long upt, downt;
269
  routerinfo_t *r;
270

271
272
  rep_history_clean(now-24*60*60);

273
  log(severity, "--------------- Dumping history information:");
274
275
276

  for (orhist_it = strmap_iter_init(history_map); !strmap_iter_done(orhist_it);
       orhist_it = strmap_iter_next(history_map,orhist_it)) {
277
    strmap_iter_get(orhist_it, &hexdigest1, &or_history_p);
278
    or_history = (or_history_t*) or_history_p;
279

280
281
282
283
284
    if ((r = router_get_by_hexdigest(hexdigest1)))
      name1 = r->nickname;
    else
      name1 = "(unknown)";

285
    update_or_history(or_history, now);
286
287
288
289
290
291
292
293
    upt = or_history->uptime;
    downt = or_history->downtime;
    if (upt+downt) {
      uptime = ((double)upt) / (upt+downt);
    } else {
      uptime=1.0;
    }
    log(severity,
294
295
        "OR %s [%s]: %ld/%ld good connections; uptime %ld/%ld sec (%.2f%%)",
        name1, hexdigest1,
Roger Dingledine's avatar
tabs    
Roger Dingledine committed
296
        or_history->n_conn_ok, or_history->n_conn_fail+or_history->n_conn_ok,
297
        upt, upt+downt, uptime*100.0);
298

299
    if (!strmap_isempty(or_history->link_history_map)) {
300
      strlcpy(buffer, "    Extend attempts: ", sizeof(buffer));
301
302
303
304
305
306
307
308
309
      len = strlen(buffer);
      for (lhist_it = strmap_iter_init(or_history->link_history_map);
           !strmap_iter_done(lhist_it);
           lhist_it = strmap_iter_next(or_history->link_history_map, lhist_it)) {
        strmap_iter_get(lhist_it, &hexdigest2, &link_history_p);
        if ((r = router_get_by_hexdigest(hexdigest2)))
          name2 = r->nickname;
        else
          name2 = "(unknown)";
310

311
        link_history = (link_history_t*) link_history_p;
312

Nick Mathewson's avatar
Nick Mathewson committed
313
        ret = tor_snprintf(buffer+len, 2048-len, "%s(%ld/%ld); ", name2,
314
315
                        link_history->n_extend_ok,
                        link_history->n_extend_ok+link_history->n_extend_fail);
Nick Mathewson's avatar
Nick Mathewson committed
316
        if (ret<0)
317
          break;
Nick Mathewson's avatar
Nick Mathewson committed
318
        else
Nick Mathewson's avatar
Nick Mathewson committed
319
          len += ret;
320
      }
321
      log(severity, "%s", buffer);
322
323
324
325
    }
  }
}

326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
/** Remove history info for routers/links that haven't changed since
 * <b>before</b> */
void rep_history_clean(time_t before)
{
  or_history_t *or_history;
  link_history_t *link_history;
  void *or_history_p, *link_history_p;
  strmap_iter_t *orhist_it, *lhist_it;
  const char *hd1, *hd2;

  orhist_it = strmap_iter_init(history_map);
  while (!strmap_iter_done(orhist_it)) {
    strmap_iter_get(orhist_it, &hd1, &or_history_p);
    or_history = or_history_p;
    if (or_history->changed < before) {
      free_or_history(or_history);
      orhist_it = strmap_iter_next_rmv(history_map, orhist_it);
      continue;
    }
    for (lhist_it = strmap_iter_init(or_history->link_history_map);
         !strmap_iter_done(lhist_it); ) {
      strmap_iter_get(lhist_it, &hd2, &link_history_p);
      link_history = link_history_p;
      if (link_history->changed < before) {
        tor_free(link_history);
        lhist_it = strmap_iter_next_rmv(or_history->link_history_map,lhist_it);
        continue;
      }
      lhist_it = strmap_iter_next(or_history->link_history_map,lhist_it);
    }
    orhist_it = strmap_iter_next(history_map, orhist_it);
  }
}

360
361
362
363
364
365
366
367
368
369
370
371
372
373
#if 0
void write_rep_history(const char *filename)
{
  FILE *f = NULL;
  char *tmpfile;
  int completed = 0;
  or_history_t *or_history;
  link_history_t *link_history;
  strmap_iter_t *lhist_it;
  strmap_iter_t *orhist_it;
  void *or_history_p, *link_history_p;
  const char *name1;

  tmpfile = tor_malloc(strlen(filename)+5);
374
  tor_snprintf(tmpfile, strlen(filename)+5, "%s_tmp", filename);
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396

  f = fopen(tmpfile, "w");
  if (!f) goto done;
  for (orhist_it = strmap_iter_init(history_map); !strmap_iter_done(orhist_it);
       orhist_it = strmap_iter_next(history_map,orhist_it)) {
    strmap_iter_get(orhist_it, &name1, &or_history_p);
    or_history = (or_history_t*) or_history_p;
    fprintf(f, "link %s connected:u%ld failed:%uld uptime:%uld",
            name1, or_history->since1,
  }

 done:
  if (f)
    fclose(f);
  if (completed)
    replace_file(filename, tmpfile);
  else
    unlink(tmpfile);
  tor_free(tmpfile);
}
#endif

397
#define NUM_SECS_ROLLING_MEASURE 10
398
#define NUM_SECS_BW_SUM_IS_VALID (24*60*60) /* one day */
399
400
401
402
#define NUM_SECS_BW_SUM_INTERVAL (15*60)
#define NUM_TOTALS (NUM_SECS_BW_SUM_IS_VALID/NUM_SECS_BW_SUM_INTERVAL)

/**
403
 * Structure to track bandwidth use, and remember the maxima for a given
404
405
406
407
408
409
410
411
412
413
414
 * 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. */
415
  int total_in_period; /**< Total bytes transferred in the current period. */
416
417
418
419
420
421

  /** 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;
422
423
424
425
426
  /** 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 */
427
  int maxima[NUM_TOTALS];
428
429
430
  /** Circular array of the total bandwidth usage for the last NUM_TOTALS
   * periods */
  int totals[NUM_TOTALS];
431
432
} bw_array_t;

433
/** Shift the current period of b forward by one.
434
435
 */
static void commit_max(bw_array_t *b) {
436
437
  /* Store total from current period. */
  b->totals[b->next_max_idx] = b->total_in_period;
438
439
440
441
442
443
  /* 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;
444
445
  if (b->num_maxes_set < NUM_TOTALS)
    ++b->num_maxes_set;
446
447
  /* Reset max_total. */
  b->max_total = 0;
448
449
  /* Reset total_in_period. */
  b->total_in_period = 0;
450
451
}

452
/** Shift the current observation time of 'b' forward by one second.
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
 */
static INLINE void advance_obs(bw_array_t *b) {
  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'.
 */
static INLINE void add_obs(bw_array_t *b, time_t when, int n) {
Nick Mathewson's avatar
Nick Mathewson committed
479
480
481
482
483
484
485
  /* 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)
486
    advance_obs(b);
Nick Mathewson's avatar
Nick Mathewson committed
487

488
  b->obs[b->cur_obs_idx] += n;
489
  b->total_in_period += n;
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
}

/** Allocate, initialize, and return a new bw_array.
 */
static bw_array_t *bw_array_new(void) {
  bw_array_t *b;
  time_t start;
  b = tor_malloc_zero(sizeof(bw_array_t));
  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
 */
static void bw_arrays_init(void)
{
  read_array = bw_array_new();
  write_array = bw_array_new();
}
514
515
516
517
518
519

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

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

/**
 * 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.
 */
564
int rep_hist_bandwidth_assess(void) {
565
566
567
568
  int w,r;
  r = find_largest_max(read_array);
  w = find_largest_max(write_array);
  if (r>w)
569
    return (int)(w/(double)NUM_SECS_ROLLING_MEASURE);
570
  else
571
    return (int)(r/(double)NUM_SECS_ROLLING_MEASURE);
572
573
574
575

  return 0;
}

576
/**
577
578
 * Allocate and return lines for representing this server's bandwidth
 * history in its descriptor.
579
 */
580
581
char *
rep_hist_get_bandwidth_lines(void)
582
583
584
585
586
587
588
{
  char *buf, *cp;
  char t[ISO_TIME_LEN+1];
  int r, i, n;
  bw_array_t *b;
  size_t len;

589
  /* opt (read|write)-history yyyy-mm-dd HH:MM:SS (n s) n,n,n,n,n... */
590
591
592
593
594
  len = (60+12*NUM_TOTALS)*2;
  buf = tor_malloc_zero(len);
  cp = buf;
  for (r=0;r<2;++r) {
    b = r?read_array:write_array;
595
    tor_assert(b);
596
    format_iso_time(t, b->next_period-NUM_SECS_BW_SUM_INTERVAL);
597
    tor_snprintf(cp, len-(cp-buf), "opt %s %s (%d s) ", r?"read-history ":"write-history", t,
598
599
            NUM_SECS_BW_SUM_INTERVAL);
    cp += strlen(cp);
600

601
602
    if (b->num_maxes_set <= b->next_max_idx)
      /* We haven't been through the circular array yet; time starts at i=0.*/
603
604
      i = 0;
    else
605
      /* We've been around the array at least once.  The next i to be
606
         overwritten is the oldest. */
607
608
609
610
      i = b->next_max_idx;

    for (n=0; n<b->num_maxes_set; ++n,++i) {
      while (i >= NUM_TOTALS) i -= NUM_TOTALS;
611
      if (n==(b->num_maxes_set-1))
612
        tor_snprintf(cp, len-(cp-buf), "%d", b->totals[i]);
613
      else
614
        tor_snprintf(cp, len-(cp-buf), "%d,", b->totals[i]);
615
616
      cp += strlen(cp);
    }
617
    strlcat(cp, "\n", len-(cp-buf));
618
619
620
621
622
    ++cp;
  }
  return buf;
}

623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
/** 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;

static void add_predicted_port(uint16_t port, time_t now) {
  uint16_t *tmp_port = tor_malloc(sizeof(uint16_t));
  time_t *tmp_time = tor_malloc(sizeof(time_t));
  *tmp_port = port;
  *tmp_time = now;
  smartlist_add(predicted_ports_list, tmp_port);
  smartlist_add(predicted_ports_times, tmp_time);
}

static void predicted_ports_init(void) {
  predicted_ports_list = smartlist_create();
  predicted_ports_times = smartlist_create();
  add_predicted_port(80, time(NULL)); /* add one to kickstart us */
}

643
644
645
646
647
648
649
static void predicted_ports_free(void) {
  SMARTLIST_FOREACH(predicted_ports_list, char *, cp, tor_free(cp));
  smartlist_free(predicted_ports_list);
  SMARTLIST_FOREACH(predicted_ports_times, char *, cp, tor_free(cp));
  smartlist_free(predicted_ports_times);
}

650
651
652
653
654
655
656
657
658
659
660
661
/** 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
 * future and making circuits to anticipate that.
 */
void rep_hist_note_used_port(uint16_t port, time_t now) {
  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
662
  if (!port) /* record nothing */
663
664
665
666
667
668
669
670
671
672
673
674
675
676
    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);
}

677
#define PREDICTED_CIRCS_RELEVANCE_TIME (3600) /* 1 hour */
678

Roger Dingledine's avatar
Roger Dingledine committed
679
/** Return a pointer to the list of port numbers that
680
 * are likely to be asked for in the near future.
Roger Dingledine's avatar
Roger Dingledine committed
681
682
 *
 * The caller promises not to mess with it.
683
 */
Roger Dingledine's avatar
Roger Dingledine committed
684
smartlist_t *rep_hist_get_predicted_ports(time_t now) {
685
686
687
688
689
690
691
692
693
694
  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);
695
    if (*tmp_time + PREDICTED_CIRCS_RELEVANCE_TIME < now) {
696
      tmp_port = smartlist_get(predicted_ports_list, i);
Roger Dingledine's avatar
Roger Dingledine committed
697
      log_fn(LOG_DEBUG, "Expiring predicted port %d", *tmp_port);
698
699
700
701
702
703
704
      smartlist_del(predicted_ports_list, i);
      smartlist_del(predicted_ports_times, i);
      tor_free(tmp_port);
      tor_free(tmp_time);
      i--;
    }
  }
Roger Dingledine's avatar
Roger Dingledine committed
705
  return predicted_ports_list;
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
/** The last time at which we needed an internal circ. */
static time_t predicted_hidserv_time = 0;
/** The last time we needed an internal circ with good uptime. */
static time_t predicted_hidserv_uptime_time = 0;
/** The last time we needed an internal circ with good capacity. */
static time_t predicted_hidserv_capacity_time = 0;

/** Remember that we used an internal circ at time <b>now</b>. */
void rep_hist_note_used_hidserv(time_t now, int need_uptime, int need_capacity) {
  predicted_hidserv_time = now;
  if (need_uptime)
    predicted_hidserv_uptime_time = now;
  if (need_capacity)
    predicted_hidserv_capacity_time = now;
}

/** Return 1 if we've used an internal circ recently; else return 0. */
int rep_hist_get_predicted_hidserv(time_t now, int *need_uptime, int *need_capacity) {
  if (!predicted_hidserv_time) /* initialize it */
    predicted_hidserv_time = now;
  if (predicted_hidserv_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
    return 0; /* too long ago */
  if (predicted_hidserv_uptime_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
    *need_uptime = 1;
  if (predicted_hidserv_capacity_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
    *need_capacity = 1;
  return 1;
}

/* not used yet */
void rep_hist_note_used_resolve(time_t now) { }
int rep_hist_get_predicted_resolve(time_t now) { return 0; }

741
742
743
744
745
void rep_hist_free_all(void)
{
  strmap_free(history_map, free_or_history);
  tor_free(read_array);
  tor_free(write_array);
746
  predicted_ports_free();
747
}