src/or/rephist.c

   1 /* Copyright 2004-2005 Roger Dingledine, Nick Mathewson. */
   2 /* See LICENSE for licensing information */
   3 /* $Id$ */
   4 const char rephist_c_id[] = "$Id$";
   5
   6 /**
   7  * \file rephist.c
   8  * \brief Basic history functionality for reputation module.
   9  **/
  10
  11 #include "or.h"
  12
  13 static void bw_arrays_init(void);
  14 static void predicted_ports_init(void);
  15
  16 uint64_t rephist_total_alloc;
  17
  18 /** History of an OR-\>OR link. */
  19 typedef struct link_history_t {
  20   /** When did we start tracking this list? */
  21   time_t since;
  22   /** When did we most recently note a change to this link */
  23   time_t changed;
  24   /** How many times did extending from OR1 to OR2 succeed? */
  25   unsigned long n_extend_ok;
  26   /** How many times did extending from OR1 to OR2 fail? */
  27   unsigned long n_extend_fail;
  28 } link_history_t;
  29
  30 /** History of an OR. */
  31 typedef struct or_history_t {
  32   /** When did we start tracking this OR? */
  33   time_t since;
  34   /** When did we most recently note a change to this OR? */
  35   time_t changed;
  36   /** How many times did we successfully connect? */
  37   unsigned long n_conn_ok;
  38   /** How many times did we try to connect and fail?*/
  39   unsigned long n_conn_fail;
  40   /** How many seconds have we been connected to this OR before
  41    * 'up_since'? */
  42   unsigned long uptime;
  43   /** How many seconds have we been unable to connect to this OR before
  44    * 'down_since'? */
  45   unsigned long downtime;
  46   /** If nonzero, we have been connected since this time. */
  47   time_t up_since;
  48   /** If nonzero, we have been unable to connect since this time. */
  49   time_t down_since;
  50   /** Map from hex OR2 identity digest to a link_history_t for the link
  51    * from this OR to OR2. */
  52   strmap_t *link_history_map;
  53 } or_history_t;
  54
  55 /** Map from hex OR identity digest to or_history_t. */
  56 static strmap_t *history_map = NULL;
  57
  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   char hexid[HEX_DIGEST_LEN+1];
  64   base16_encode(hexid, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
  65
  66   if (!strcmp(hexid, "0000000000000000000000000000000000000000"))
  67     return NULL;
  68
  69   hist = (or_history_t*) strmap_get(history_map, hexid);
  70   if (!hist) {
  71     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   return hist;
  78 }
  79
  80 /** Return the link_history_t for the link from the first named OR to
  81  * the second, creating it if necessary. (ORs are identified by
  82  * identity digest)
  83  */
  84 static link_history_t *get_link_history(const char *from_id,
  85                                         const char *to_id)
  86 {
  87   or_history_t *orhist;
  88   link_history_t *lhist;
  89   char to_hexid[HEX_DIGEST_LEN+1];
  90   orhist = get_or_history(from_id);
  91   if (!orhist)
  92     return NULL;
  93   base16_encode(to_hexid, HEX_DIGEST_LEN+1, to_id, DIGEST_LEN);
  94   if (!strcmp(to_hexid, "0000000000000000000000000000000000000000"))
  95     return NULL;
  96   lhist = (link_history_t*) strmap_get(orhist->link_history_map, to_hexid);
  97   if (!lhist) {
  98     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   return lhist;
 104 }
 105
 106 static void
 107 _free_link_history(void *val)
 108 {
 109   rephist_total_alloc -= sizeof(link_history_t);
 110   tor_free(val);
 111 }
 112
 113 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   tor_free(hist);
 120 }
 121
 122 /** Update an or_history_t object <b>hist</b> so that its uptime/downtime
 123  * count is up-to-date as of <b>when</b>.
 124  */
 125 static void update_or_history(or_history_t *hist, time_t when)
 126 {
 127   tor_assert(hist);
 128   if (hist->up_since) {
 129     tor_assert(!hist->down_since);
 130     hist->uptime += (when - hist->up_since);
 131     hist->up_since = when;
 132   } else if (hist->down_since) {
 133     hist->downtime += (when - hist->down_since);
 134     hist->down_since = when;
 135   }
 136 }
 137
 138 /** Initialize the static data structures for tracking history.
 139  */
 140 void rep_hist_init(void)
 141 {
 142   history_map = strmap_new();
 143   bw_arrays_init();
 144   predicted_ports_init();
 145 }
 146
 147 /** Remember that an attempt to connect to the OR with identity digest
 148  * <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   if (!hist)
 155     return;
 156   ++hist->n_conn_fail;
 157   if (hist->up_since) {
 158     hist->uptime += (when - hist->up_since);
 159     hist->up_since = 0;
 160   }
 161   if (!hist->down_since)
 162     hist->down_since = when;
 163   hist->changed = when;
 164 }
 165
 166 /** Remember that an attempt to connect to the OR with identity digest
 167  * <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   if (!hist)
 174     return;
 175   ++hist->n_conn_ok;
 176   if (hist->down_since) {
 177     hist->downtime += (when - hist->down_since);
 178     hist->down_since = 0;
 179   }
 180   if (!hist->up_since)
 181     hist->up_since = when;
 182   hist->changed = when;
 183 }
 184
 185 /** Remember that we intentionally closed our connection to the OR
 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   if (!hist)
 193     return;
 194   ++hist->n_conn_ok;
 195   if (hist->up_since) {
 196     hist->uptime += (when - hist->up_since);
 197     hist->up_since = 0;
 198   }
 199   hist->changed = when;
 200 }
 201
 202 /** Remember that our connection to the OR with identity digest
 203  * <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. */
 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).
 212      * Ignore it.
 213      */
 214     return;
 215   }
 216   hist = get_or_history(id);
 217   if (!hist)
 218     return;
 219   if (hist->up_since) {
 220     hist->uptime += (when - hist->up_since);
 221     hist->up_since = 0;
 222   }
 223   if (!hist->down_since)
 224     hist->down_since = when;
 225   hist->changed = when;
 226 }
 227
 228 /** Remember that we successfully extended from the OR with identity
 229  * digest <b>from_id</b> to the OR with identity digest
 230  *  <b>to_name</b>.
 231  */
 232 void rep_hist_note_extend_succeeded(const char *from_id,
 233                                     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   if (!hist)
 239     return;
 240   ++hist->n_extend_ok;
 241   hist->changed = time(NULL);
 242 }
 243
 244 /** Remember that we tried to extend from the OR with identity digest
 245  * <b>from_id</b> to the OR with identity digest <b>to_name</b>, but
 246  * 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   if (!hist)
 254     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  * severity.
 261  */
 262 void rep_hist_dump_stats(time_t now, int severity)
 263 {
 264   strmap_iter_t *lhist_it;
 265   strmap_iter_t *orhist_it;
 266   const char *name1, *name2, *hexdigest1, *hexdigest2;
 267   or_history_t *or_history;
 268   link_history_t *link_history;
 269   void *or_history_p, *link_history_p;
 270   double uptime;
 271   char buffer[2048];
 272   size_t len;
 273   int ret;
 274   unsigned long upt, downt;
 275   routerinfo_t *r;
 276
 277   rep_history_clean(now-24*60*60);
 278
 279   log(severity, "--------------- Dumping history information:");
 280
 281   for (orhist_it = strmap_iter_init(history_map); !strmap_iter_done(orhist_it);
 282        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     if ((r = router_get_by_hexdigest(hexdigest1)))
 287       name1 = r->nickname;
 288     else
 289       name1 = "(unknown)";
 290
 291     update_or_history(or_history, now);
 292     upt = or_history->uptime;
 293     downt = or_history->downtime;
 294     if (upt+downt) {
 295       uptime = ((double)upt) / (upt+downt);
 296     } else {
 297       uptime=1.0;
 298     }
 299     log(severity,
 300         "OR %s [%s]: %ld/%ld good connections; uptime %ld/%ld sec (%.2f%%)",
 301         name1, hexdigest1,
 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       len = strlen(buffer);
 308       for (lhist_it = strmap_iter_init(or_history->link_history_map);
 309            !strmap_iter_done(lhist_it);
 310            lhist_it = strmap_iter_next(or_history->link_history_map, lhist_it)) {
 311         strmap_iter_get(lhist_it, &hexdigest2, &link_history_p);
 312         if ((r = router_get_by_hexdigest(hexdigest2)))
 313           name2 = r->nickname;
 314         else
 315           name2 = "(unknown)";
 316
 317         link_history = (link_history_t*) link_history_p;
 318
 319         ret = tor_snprintf(buffer+len, 2048-len, "%s(%ld/%ld); ", name2,
 320                         link_history->n_extend_ok,
 321                         link_history->n_extend_ok+link_history->n_extend_fail);
 322         if (ret<0)
 323           break;
 324         else
 325           len += ret;
 326       }
 327       log(severity, "%s", buffer);
 328     }
 329   }
 330 }
 331
 332 /** Remove history info for routers/links that haven't changed since
 333  * <b>before</b> */
 334 void rep_history_clean(time_t before)
 335 {
 336   or_history_t *or_history;
 337   link_history_t *link_history;
 338   void *or_history_p, *link_history_p;
 339   strmap_iter_t *orhist_it, *lhist_it;
 340   const char *hd1, *hd2;
 341
 342   orhist_it = strmap_iter_init(history_map);
 343   while (!strmap_iter_done(orhist_it)) {
 344     strmap_iter_get(orhist_it, &hd1, &or_history_p);
 345     or_history = or_history_p;
 346     if (or_history->changed < before) {
 347       free_or_history(or_history);
 348       orhist_it = strmap_iter_next_rmv(history_map, orhist_it);
 349       continue;
 350     }
 351     for (lhist_it = strmap_iter_init(or_history->link_history_map);
 352          !strmap_iter_done(lhist_it); ) {
 353       strmap_iter_get(lhist_it, &hd2, &link_history_p);
 354       link_history = link_history_p;
 355       if (link_history->changed < before) {
 356         rephist_total_alloc -= sizeof(link_history_t);
 357         tor_free(link_history);
 358         lhist_it = strmap_iter_next_rmv(or_history->link_history_map,lhist_it);
 359         continue;
 360       }
 361       lhist_it = strmap_iter_next(or_history->link_history_map,lhist_it);
 362     }
 363     orhist_it = strmap_iter_next(history_map, orhist_it);
 364   }
 365 }
 366
 367 #if 0
 368 void write_rep_history(const char *filename)
 369 {
 370   FILE *f = NULL;
 371   char *tmpfile;
 372   int completed = 0;
 373   or_history_t *or_history;
 374   link_history_t *link_history;
 375   strmap_iter_t *lhist_it;
 376   strmap_iter_t *orhist_it;
 377   void *or_history_p, *link_history_p;
 378   const char *name1;
 379
 380   tmpfile = tor_malloc(strlen(filename)+5);
 381   tor_snprintf(tmpfile, strlen(filename)+5, "%s_tmp", filename);
 382
 383   f = fopen(tmpfile, "w");
 384   if (!f) goto done;
 385   for (orhist_it = strmap_iter_init(history_map); !strmap_iter_done(orhist_it);
 386        orhist_it = strmap_iter_next(history_map,orhist_it)) {
 387     strmap_iter_get(orhist_it, &name1, &or_history_p);
 388     or_history = (or_history_t*) or_history_p;
 389     fprintf(f, "link %s connected:u%ld failed:%uld uptime:%uld",
 390             name1, or_history->since1,
 391   }
 392
 393  done:
 394   if (f)
 395     fclose(f);
 396   if (completed)
 397     replace_file(filename, tmpfile);
 398   else
 399     unlink(tmpfile);
 400   tor_free(tmpfile);
 401 }
 402 #endif
 403
 404 #define NUM_SECS_ROLLING_MEASURE 10
 405 #define NUM_SECS_BW_SUM_IS_VALID (24*60*60) /* one day */
 406 #define NUM_SECS_BW_SUM_INTERVAL (15*60)
 407 #define NUM_TOTALS (NUM_SECS_BW_SUM_IS_VALID/NUM_SECS_BW_SUM_INTERVAL)
 408
 409 /**
 410  * Structure to track bandwidth use, and remember the maxima for a given
 411  * time period.
 412  */
 413 typedef struct bw_array_t {
 414   /** Observation array: Total number of bytes transferred in each of the last
 415    * NUM_SECS_ROLLING_MEASURE seconds. This is used as a circular array. */
 416   int obs[NUM_SECS_ROLLING_MEASURE];
 417   int cur_obs_idx; /**< Current position in obs. */
 418   time_t cur_obs_time; /**< Time represented in obs[cur_obs_idx] */
 419   int total_obs; /**< Total for all members of obs except obs[cur_obs_idx] */
 420   int max_total; /**< Largest value that total_obs has taken on in the current
 421                   * period. */
 422   int total_in_period; /**< Total bytes transferred in the current period. */
 423
 424   /** When does the next period begin? */
 425   time_t next_period;
 426   /** Where in 'maxima' should the maximum bandwidth usage for the current
 427    * period be stored? */
 428   int next_max_idx;
 429   /** How many values in maxima/totals have been set ever? */
 430   int num_maxes_set;
 431   /** Circular array of the maximum
 432    * bandwidth-per-NUM_SECS_ROLLING_MEASURE usage for the last
 433    * NUM_TOTALS periods */
 434   int maxima[NUM_TOTALS];
 435   /** Circular array of the total bandwidth usage for the last NUM_TOTALS
 436    * periods */
 437   int totals[NUM_TOTALS];
 438 } bw_array_t;
 439
 440 /** Shift the current period of b forward by one.
 441  */
 442 static void commit_max(bw_array_t *b) {
 443   /* Store total from current period. */
 444   b->totals[b->next_max_idx] = b->total_in_period;
 445   /* Store maximum from current period. */
 446   b->maxima[b->next_max_idx++] = b->max_total;
 447   /* Advance next_period and next_max_idx */
 448   b->next_period += NUM_SECS_BW_SUM_INTERVAL;
 449   if (b->next_max_idx == NUM_TOTALS)
 450     b->next_max_idx = 0;
 451   if (b->num_maxes_set < NUM_TOTALS)
 452     ++b->num_maxes_set;
 453   /* Reset max_total. */
 454   b->max_total = 0;
 455   /* Reset total_in_period. */
 456   b->total_in_period = 0;
 457 }
 458
 459 /** Shift the current observation time of 'b' forward by one second.
 460  */
 461 static INLINE void advance_obs(bw_array_t *b) {
 462   int nextidx;
 463   int total;
 464
 465   /* Calculate the total bandwidth for the last NUM_SECS_ROLLING_MEASURE
 466    * seconds; adjust max_total as needed.*/
 467   total = b->total_obs + b->obs[b->cur_obs_idx];
 468   if (total > b->max_total)
 469     b->max_total = total;
 470
 471   nextidx = b->cur_obs_idx+1;
 472   if (nextidx == NUM_SECS_ROLLING_MEASURE)
 473     nextidx = 0;
 474
 475   b->total_obs = total - b->obs[nextidx];
 476   b->obs[nextidx]=0;
 477   b->cur_obs_idx = nextidx;
 478
 479   if (++b->cur_obs_time >= b->next_period)
 480     commit_max(b);
 481 }
 482
 483 /** Add 'n' bytes to the number of bytes in b for second 'when'.
 484  */
 485 static INLINE void add_obs(bw_array_t *b, time_t when, int n) {
 486   /* Don't record data in the past. */
 487   if (when<b->cur_obs_time)
 488     return;
 489   /* If we're currently adding observations for an earlier second than
 490    * 'when', advance b->cur_obs_time and b->cur_obs_idx by an
 491    * appropriate number of seconds, and do all the other housekeeping */
 492   while (when>b->cur_obs_time)
 493     advance_obs(b);
 494
 495   b->obs[b->cur_obs_idx] += n;
 496   b->total_in_period += n;
 497 }
 498
 499 /** Allocate, initialize, and return a new bw_array.
 500  */
 501 static bw_array_t *bw_array_new(void) {
 502   bw_array_t *b;
 503   time_t start;
 504   b = tor_malloc_zero(sizeof(bw_array_t));
 505   rephist_total_alloc += sizeof(bw_array_t);
 506   start = time(NULL);
 507   b->cur_obs_time = start;
 508   b->next_period = start + NUM_SECS_BW_SUM_INTERVAL;
 509   return b;
 510 }
 511
 512 static bw_array_t *read_array = NULL;
 513 static bw_array_t *write_array = NULL;
 514
 515 /** Set up read_array and write_array
 516  */
 517 static void bw_arrays_init(void)
 518 {
 519   read_array = bw_array_new();
 520   write_array = bw_array_new();
 521 }
 522
 523 /** We read <b>num_bytes</b> more bytes in second <b>when</b>.
 524  *
 525  * Add num_bytes to the current running total for <b>when</b>.
 526  *
 527  * <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 void rep_hist_note_bytes_written(int num_bytes, time_t when) {
 531 /* Maybe a circular array for recent seconds, and step to a new point
 532  * every time a new second shows up. Or simpler is to just to have
 533  * a normal array and push down each item every second; it's short.
 534  */
 535 /* When a new second has rolled over, compute the sum of the bytes we've
 536  * seen over when-1 to when-1-NUM_SECS_ROLLING_MEASURE, and stick it
 537  * somewhere. See rep_hist_bandwidth_assess() below.
 538  */
 539   add_obs(write_array, when, num_bytes);
 540 }
 541
 542 /** We wrote <b>num_bytes</b> more bytes in second <b>when</b>.
 543  * (like rep_hist_note_bytes_written() above)
 544  */
 545 void rep_hist_note_bytes_read(int num_bytes, time_t when) {
 546 /* if we're smart, we can make this func and the one above share code */
 547   add_obs(read_array, when, num_bytes);
 548 }
 549
 550 /** Helper: Return the largest value in b->maxima.  (This is equal to the
 551  * most bandwidth used in any NUM_SECS_ROLLING_MEASURE period for the last
 552  * NUM_SECS_BW_SUM_IS_VALID seconds.)
 553  */
 554 static int find_largest_max(bw_array_t *b)
 555 {
 556   int i,max;
 557   max=0;
 558   for (i=0; i<NUM_TOTALS; ++i) {
 559     if (b->maxima[i]>max)
 560       max = b->maxima[i];
 561   }
 562   return max;
 563 }
 564
 565 /**
 566  * Find the largest sums in the past NUM_SECS_BW_SUM_IS_VALID (roughly)
 567  * seconds. Find one sum for reading and one for writing. They don't have
 568  * to be at the same time).
 569  *
 570  * Return the smaller of these sums, divided by NUM_SECS_ROLLING_MEASURE.
 571  */
 572 int rep_hist_bandwidth_assess(void) {
 573   int w,r;
 574   r = find_largest_max(read_array);
 575   w = find_largest_max(write_array);
 576   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   return 0;
 582 }
 583
 584 /**
 585  * Allocate and return lines for representing this server's bandwidth
 586  * history in its descriptor.
 587  */
 588 char *
 589 rep_hist_get_bandwidth_lines(void)
 590 {
 591   char *buf, *cp;
 592   char t[ISO_TIME_LEN+1];
 593   int r, i, n;
 594   bw_array_t *b;
 595   size_t len;
 596
 597   /* opt (read|write)-history yyyy-mm-dd HH:MM:SS (n s) n,n,n,n,n... */
 598   len = (60+12*NUM_TOTALS)*2;
 599   buf = tor_malloc_zero(len);
 600   cp = buf;
 601   for (r=0;r<2;++r) {
 602     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             NUM_SECS_BW_SUM_INTERVAL);
 607     cp += strlen(cp);
 608
 609     if (b->num_maxes_set <= b->next_max_idx)
 610       /* We haven't been through the circular array yet; time starts at i=0.*/
 611       i = 0;
 612     else
 613       /* We've been around the array at least once.  The next i to be
 614          overwritten is the oldest. */
 615       i = b->next_max_idx;
 616
 617     for (n=0; n<b->num_maxes_set; ++n,++i) {
 618       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       cp += strlen(cp);
 624     }
 625     strlcat(cp, "\n", len-(cp-buf));
 626     ++cp;
 627   }
 628   return buf;
 629 }
 630
 631 /** A list of port numbers that have been used recently. */
 632 static smartlist_t *predicted_ports_list=NULL;
 633 /** The corresponding most recently used time for each port. */
 634 static smartlist_t *predicted_ports_times=NULL;
 635
 636 static void add_predicted_port(uint16_t port, time_t now) {
 637   /* XXXX we could just use uintptr_t here, I think. */
 638   uint16_t *tmp_port = tor_malloc(sizeof(uint16_t));
 639   time_t *tmp_time = tor_malloc(sizeof(time_t));
 640   *tmp_port = port;
 641   *tmp_time = now;
 642   rephist_total_alloc += sizeof(uint16_t) + sizeof(time_t);
 643   smartlist_add(predicted_ports_list, tmp_port);
 644   smartlist_add(predicted_ports_times, tmp_time);
 645 }
 646
 647 static void predicted_ports_init(void) {
 648   predicted_ports_list = smartlist_create();
 649   predicted_ports_times = smartlist_create();
 650   add_predicted_port(80, time(NULL)); /* add one to kickstart us */
 651 }
 652
 653 static void predicted_ports_free(void) {
 654   rephist_total_alloc -= smartlist_len(predicted_ports_list)*sizeof(uint16_t);
 655   SMARTLIST_FOREACH(predicted_ports_list, char *, cp, tor_free(cp));
 656   smartlist_free(predicted_ports_list);
 657   rephist_total_alloc -= smartlist_len(predicted_ports_times)*sizeof(time_t);
 658   SMARTLIST_FOREACH(predicted_ports_times, char *, cp, tor_free(cp));
 659   smartlist_free(predicted_ports_times);
 660 }
 661
 662 /** Remember that <b>port</b> has been asked for as of time <b>now</b>.
 663  * This is used for predicting what sorts of streams we'll make in the
 664  * future and making circuits to anticipate that.
 665  */
 666 void rep_hist_note_used_port(uint16_t port, time_t now) {
 667   int i;
 668   uint16_t *tmp_port;
 669   time_t *tmp_time;
 670
 671   tor_assert(predicted_ports_list);
 672   tor_assert(predicted_ports_times);
 673
 674   if (!port) /* record nothing */
 675     return;
 676
 677   for (i = 0; i < smartlist_len(predicted_ports_list); ++i) {
 678     tmp_port = smartlist_get(predicted_ports_list, i);
 679     tmp_time = smartlist_get(predicted_ports_times, i);
 680     if (*tmp_port == port) {
 681       *tmp_time = now;
 682       return;
 683     }
 684   }
 685   /* it's not there yet; we need to add it */
 686   add_predicted_port(port, now);
 687 }
 688
 689 #define PREDICTED_CIRCS_RELEVANCE_TIME (3600) /* 1 hour */
 690
 691 /** Return a pointer to the list of port numbers that
 692  * are likely to be asked for in the near future.
 693  *
 694  * The caller promises not to mess with it.
 695  */
 696 smartlist_t *rep_hist_get_predicted_ports(time_t now) {
 697   int i;
 698   uint16_t *tmp_port;
 699   time_t *tmp_time;
 700
 701   tor_assert(predicted_ports_list);
 702   tor_assert(predicted_ports_times);
 703
 704   /* clean out obsolete entries */
 705   for (i = 0; i < smartlist_len(predicted_ports_list); ++i) {
 706     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);
 709       log_fn(LOG_DEBUG, "Expiring predicted port %d", *tmp_port);
 710       smartlist_del(predicted_ports_list, i);
 711       smartlist_del(predicted_ports_times, i);
 712       rephist_total_alloc -= sizeof(uint16_t)+sizeof(time_t);
 713       tor_free(tmp_port);
 714       tor_free(tmp_time);
 715       i--;
 716     }
 717   }
 718   return predicted_ports_list;
 719 }
 720
 721 /** The last time at which we needed an internal circ. */
 722 static time_t predicted_hidserv_time = 0;
 723 /** The last time we needed an internal circ with good uptime. */
 724 static time_t predicted_hidserv_uptime_time = 0;
 725 /** The last time we needed an internal circ with good capacity. */
 726 static time_t predicted_hidserv_capacity_time = 0;
 727
 728 /** Remember that we used an internal circ at time <b>now</b>. */
 729 void rep_hist_note_used_hidserv(time_t now, int need_uptime, int need_capacity) {
 730   predicted_hidserv_time = now;
 731   if (need_uptime)
 732     predicted_hidserv_uptime_time = now;
 733   if (need_capacity)
 734     predicted_hidserv_capacity_time = now;
 735 }
 736
 737 /** Return 1 if we've used an internal circ recently; else return 0. */
 738 int rep_hist_get_predicted_hidserv(time_t now, int *need_uptime, int *need_capacity) {
 739   if (!predicted_hidserv_time) /* initialize it */
 740     predicted_hidserv_time = now;
 741   if (predicted_hidserv_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
 742     return 0; /* too long ago */
 743   if (predicted_hidserv_uptime_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
 744     *need_uptime = 1;
 745   if (predicted_hidserv_capacity_time + PREDICTED_CIRCS_RELEVANCE_TIME < now)
 746     *need_capacity = 1;
 747   return 1;
 748 }
 749
 750 /* not used yet */
 751 void rep_hist_note_used_resolve(time_t now) { }
 752 int rep_hist_get_predicted_resolve(time_t now) { return 0; }
 753
 754 void rep_hist_free_all(void)
 755 {
 756   strmap_free(history_map, free_or_history);
 757   tor_free(read_array);
 758   tor_free(write_array);
 759   predicted_ports_free();
 760 }
 761