rephist.c 22.7 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

16
17
uint64_t rephist_total_alloc;

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

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

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

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

66
67
68
  if (!strcmp(hexid, "0000000000000000000000000000000000000000"))
    return NULL;

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

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

106
107
108
static void
_free_link_history(void *val)
{
109
  rephist_total_alloc -= sizeof(link_history_t);
110
111
112
113
  tor_free(val);
}

static void
114
free_or_history(void *_hist)
115
{
116
  or_history_t *hist = _hist;
117
  strmap_free(hist->link_history_map, _free_link_history);
118
  rephist_total_alloc -= sizeof(or_history_t);
119
120
121
  tor_free(hist);
}

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

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

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

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

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

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

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

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

277
278
  rep_history_clean(now-24*60*60);

279
  log(severity, "--------------- Dumping history information:");
280
281
282

  for (orhist_it = strmap_iter_init(history_map); !strmap_iter_done(orhist_it);
       orhist_it = strmap_iter_next(history_map,orhist_it)) {
283
    strmap_iter_get(orhist_it, &hexdigest1, &or_history_p);
284
    or_history = (or_history_t*) or_history_p;
285

286
287
288
289
290
    if ((r = router_get_by_hexdigest(hexdigest1)))
      name1 = r->nickname;
    else
      name1 = "(unknown)";

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

305
    if (!strmap_isempty(or_history->link_history_map)) {
306
      strlcpy(buffer, "    Extend attempts: ", sizeof(buffer));
307
308
309
310
311
312
313
314
315
      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)";
316

317
        link_history = (link_history_t*) link_history_p;
318

Nick Mathewson's avatar
Nick Mathewson committed
319
        ret = tor_snprintf(buffer+len, 2048-len, "%s(%ld/%ld); ", name2,
320
321
                        link_history->n_extend_ok,
                        link_history->n_extend_ok+link_history->n_extend_fail);
Nick Mathewson's avatar
Nick Mathewson committed
322
        if (ret<0)
323
          break;
Nick Mathewson's avatar
Nick Mathewson committed
324
        else
Nick Mathewson's avatar
Nick Mathewson committed
325
          len += ret;
326
      }
327
      log(severity, "%s", buffer);
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
/** 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) {
356
        rephist_total_alloc -= sizeof(link_history_t);
357
358
359
360
361
362
363
364
365
366
        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);
  }
}

367
368
369
370
371
372
373
374
375
376
377
378
379
380
#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);
381
  tor_snprintf(tmpfile, strlen(filename)+5, "%s_tmp", filename);
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403

  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

404
#define NUM_SECS_ROLLING_MEASURE 10
405
#define NUM_SECS_BW_SUM_IS_VALID (24*60*60) /* one day */
406
407
408
409
#define NUM_SECS_BW_SUM_INTERVAL (15*60)
#define NUM_TOTALS (NUM_SECS_BW_SUM_IS_VALID/NUM_SECS_BW_SUM_INTERVAL)

/**
410
 * Structure to track bandwidth use, and remember the maxima for a given
411
412
413
414
415
416
417
418
419
420
421
 * 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. */
422
  int total_in_period; /**< Total bytes transferred in the current period. */
423
424
425
426
427
428

  /** 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;
429
430
431
432
433
  /** 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 */
434
  int maxima[NUM_TOTALS];
435
436
437
  /** Circular array of the total bandwidth usage for the last NUM_TOTALS
   * periods */
  int totals[NUM_TOTALS];
438
439
} bw_array_t;

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

459
/** Shift the current observation time of 'b' forward by one second.
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
 */
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
486
487
488
489
490
491
492
  /* 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)
493
    advance_obs(b);
Nick Mathewson's avatar
Nick Mathewson committed
494

495
  b->obs[b->cur_obs_idx] += n;
496
  b->total_in_period += n;
497
498
499
500
501
502
503
504
}

/** 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));
505
  rephist_total_alloc += sizeof(bw_array_t);
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
  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();
}
522
523
524
525
526
527

/** 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
528
 * earlier than the latest <b>when</b> you've heard of.
529
530
531
532
533
534
535
536
537
538
 */
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.
 */
539
  add_obs(write_array, when, num_bytes);
540
541
542
543
544
545
546
}

/** 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 */
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
  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;
563
564
565
566
567
568
569
570
571
}

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

  return 0;
}

584
/**
585
586
 * Allocate and return lines for representing this server's bandwidth
 * history in its descriptor.
587
 */
588
589
char *
rep_hist_get_bandwidth_lines(void)
590
591
592
593
594
595
596
{
  char *buf, *cp;
  char t[ISO_TIME_LEN+1];
  int r, i, n;
  bw_array_t *b;
  size_t len;

597
  /* opt (read|write)-history yyyy-mm-dd HH:MM:SS (n s) n,n,n,n,n... */
598
599
600
601
602
  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;
603
    tor_assert(b);
604
    format_iso_time(t, b->next_period-NUM_SECS_BW_SUM_INTERVAL);
605
    tor_snprintf(cp, len-(cp-buf), "opt %s %s (%d s) ", r?"read-history ":"write-history", t,
606
607
            NUM_SECS_BW_SUM_INTERVAL);
    cp += strlen(cp);
608

609
610
    if (b->num_maxes_set <= b->next_max_idx)
      /* We haven't been through the circular array yet; time starts at i=0.*/
611
612
      i = 0;
    else
613
      /* We've been around the array at least once.  The next i to be
614
         overwritten is the oldest. */
615
616
617
618
      i = b->next_max_idx;

    for (n=0; n<b->num_maxes_set; ++n,++i) {
      while (i >= NUM_TOTALS) i -= NUM_TOTALS;
619
      if (n==(b->num_maxes_set-1))
620
        tor_snprintf(cp, len-(cp-buf), "%d", b->totals[i]);
621
      else
622
        tor_snprintf(cp, len-(cp-buf), "%d,", b->totals[i]);
623
624
      cp += strlen(cp);
    }
625
    strlcat(cp, "\n", len-(cp-buf));
626
627
628
629
630
    ++cp;
  }
  return buf;
}

631
632
633
634
635
636
/** 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) {
637
  /* XXXX we could just use uintptr_t here, I think. */
638
639
640
641
  uint16_t *tmp_port = tor_malloc(sizeof(uint16_t));
  time_t *tmp_time = tor_malloc(sizeof(time_t));
  *tmp_port = port;
  *tmp_time = now;
642
  rephist_total_alloc += sizeof(uint16_t) + sizeof(time_t);
643
644
645
646
647
648
649
650
651
652
  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 */
}

653
static void predicted_ports_free(void) {
654
  rephist_total_alloc -= smartlist_len(predicted_ports_list)*sizeof(uint16_t);
655
656
  SMARTLIST_FOREACH(predicted_ports_list, char *, cp, tor_free(cp));
  smartlist_free(predicted_ports_list);
657
  rephist_total_alloc -= smartlist_len(predicted_ports_times)*sizeof(time_t);
658
659
660
661
  SMARTLIST_FOREACH(predicted_ports_times, char *, cp, tor_free(cp));
  smartlist_free(predicted_ports_times);
}

662
663
664
665
666
667
668
669
670
671
672
673
/** 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
674
  if (!port) /* record nothing */
675
676
677
678
679
680
681
682
683
684
685
686
687
688
    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);
}

689
#define PREDICTED_CIRCS_RELEVANCE_TIME (3600) /* 1 hour */
690

Roger Dingledine's avatar
Roger Dingledine committed
691
/** Return a pointer to the list of port numbers that
692
 * are likely to be asked for in the near future.
Roger Dingledine's avatar
Roger Dingledine committed
693
694
 *
 * The caller promises not to mess with it.
695
 */
Roger Dingledine's avatar
Roger Dingledine committed
696
smartlist_t *rep_hist_get_predicted_ports(time_t now) {
697
698
699
700
701
702
703
704
705
706
  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);
707
    if (*tmp_time + PREDICTED_CIRCS_RELEVANCE_TIME < now) {
708
      tmp_port = smartlist_get(predicted_ports_list, i);
Roger Dingledine's avatar
Roger Dingledine committed
709
      log_fn(LOG_DEBUG, "Expiring predicted port %d", *tmp_port);
710
711
      smartlist_del(predicted_ports_list, i);
      smartlist_del(predicted_ports_times, i);
712
      rephist_total_alloc -= sizeof(uint16_t)+sizeof(time_t);
713
714
715
716
717
      tor_free(tmp_port);
      tor_free(tmp_time);
      i--;
    }
  }
Roger Dingledine's avatar
Roger Dingledine committed
718
  return predicted_ports_list;
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
751
752
753
/** 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; }

754
755
756
757
758
void rep_hist_free_all(void)
{
  strmap_free(history_map, free_or_history);
  tor_free(read_array);
  tor_free(write_array);
759
  predicted_ports_free();
760
}