rephist.c 20.2 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
/* Copyright 2004 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
109
110
111
112
113
114
static void
_free_link_history(void *val)
{
  tor_free(val);
}

static void
free_or_history(or_history_t *hist)
{
  strmap_free(hist->link_history_map, _free_link_history);
  tor_free(hist);
}

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

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

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

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

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

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

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

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

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

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

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

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

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

298
    if (!strmap_isempty(or_history->link_history_map)) {
299
      strlcpy(buffer, "    Extend attempts: ", sizeof(buffer));
300
301
302
303
304
305
306
307
308
      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)";
309

310
        link_history = (link_history_t*) link_history_p;
311

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

359
360
361
362
363
364
365
366
367
368
369
370
371
372
#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);
373
  tor_snprintf(tmpfile, strlen(filename)+5, "%s_tmp", filename);
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395

  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

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

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

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

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

451
/** Shift the current observation time of 'b' forward by one second.
452
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
 */
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
478
479
480
481
482
483
484
  /* Don't record data in the past. */
  if (when<b->cur_obs_time)
    return;
  /* If we're currently adding observations for an earlier second than
   * 'when', advance b->cur_obs_time and b->cur_obs_idx by an
   * appropriate number of seconds, and do all the other housekeeping */
  while (when>b->cur_obs_time)
485
    advance_obs(b);
Nick Mathewson's avatar
Nick Mathewson committed
486

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

/** 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();
}
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
524
525
526
527
528
529
 */
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.
 */
530
  add_obs(write_array, when, num_bytes);
531
532
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)
 */
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 */
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
  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;
554
555
556
557
558
559
560
561
562
}

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

  return 0;
}

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

588
  /* opt (read|write)-history yyyy-mm-dd HH:MM:SS (n s) n,n,n,n,n... */
589
590
591
592
593
  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;
594
    tor_assert(b);
595
    format_iso_time(t, b->next_period-NUM_SECS_BW_SUM_INTERVAL);
596
    tor_snprintf(cp, len-(cp-buf), "opt %s %s (%d s) ", r?"read-history ":"write-history", t,
597
598
            NUM_SECS_BW_SUM_INTERVAL);
    cp += strlen(cp);
599

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

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

622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
/** 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 */
}

/** 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
654
  if (!port) /* record nothing */
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
    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);
}

#define PREFERRED_PORTS_RELEVANCE_TIME (6*3600) /* 6 hours */

/** Allocate and return a string of space-separated port numbers that
 * are likely to be asked for in the near future.
 */
char *rep_hist_get_predicted_ports(time_t now) {
  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);
    if (*tmp_time + PREFERRED_PORTS_RELEVANCE_TIME < now) {
      tmp_port = smartlist_get(predicted_ports_list, i);
      smartlist_del(predicted_ports_list, i);
      smartlist_del(predicted_ports_times, i);
      tor_free(tmp_port);
      tor_free(tmp_time);
      i--;
    }
  }
  return smartlist_join_strings(predicted_ports_list, " ", 0, NULL);
}