1 /* Copyright 2004 Roger Dingledine, Nick Mathewson. */
2 /* See LICENSE for licensing information */
7 * \brief Basic history functionality for reputation module.
12 static void bw_arrays_init(void);
14 /** History of an OR-\>OR link. */
15 typedef struct link_history_t
{
16 /** When did we start tracking this list? */
18 /** When did we most recently note a change to this link */
20 /** How many times did extending from OR1 to OR2 succeeed? */
21 unsigned long n_extend_ok
;
22 /** How many times did extending from OR1 to OR2 fail? */
23 unsigned long n_extend_fail
;
26 /** History of an OR. */
27 typedef struct or_history_t
{
28 /** When did we start tracking this OR? */
30 /** When did we most recently note a change to this OR? */
32 /** How many times did we successfully connect? */
33 unsigned long n_conn_ok
;
34 /** How many times did we try to connect and fail?*/
35 unsigned long n_conn_fail
;
36 /** How many seconds have we been connected to this OR before
39 /** How many seconds have we been unable to connect to this OR before
41 unsigned long downtime
;
42 /** If nonzero, we have been connected since this time. */
44 /** If nonzero, we have been unable to connect since this time. */
46 /** Map from hex OR2 identity digest to a link_history_t for the link
47 * from this OR to OR2. */
48 strmap_t
*link_history_map
;
51 /** Map from hex OR identity digest to or_history_t. */
52 static strmap_t
*history_map
= NULL
;
54 /** Return the or_history_t for the named OR, creating it if necessary.
56 static or_history_t
*get_or_history(const char* id
)
59 char hexid
[HEX_DIGEST_LEN
+1];
60 base16_encode(hexid
, HEX_DIGEST_LEN
+1, id
, DIGEST_LEN
);
62 if (!strcmp(hexid
, "0000000000000000000000000000000000000000"))
65 hist
= (or_history_t
*) strmap_get(history_map
, hexid
);
67 hist
= tor_malloc_zero(sizeof(or_history_t
));
68 hist
->link_history_map
= strmap_new();
69 hist
->since
= hist
->changed
= time(NULL
);
70 strmap_set(history_map
, hexid
, hist
);
75 /** Return the link_history_t for the link from the first named OR to
76 * the second, creating it if necessary. (ORs are identified by
79 static link_history_t
*get_link_history(const char *from_id
,
83 link_history_t
*lhist
;
84 char to_hexid
[HEX_DIGEST_LEN
+1];
85 orhist
= get_or_history(from_id
);
88 base16_encode(to_hexid
, HEX_DIGEST_LEN
+1, to_id
, DIGEST_LEN
);
89 if (!strcmp(to_hexid
, "0000000000000000000000000000000000000000"))
91 lhist
= (link_history_t
*) strmap_get(orhist
->link_history_map
, to_hexid
);
93 lhist
= tor_malloc_zero(sizeof(link_history_t
));
94 lhist
->since
= lhist
->changed
= time(NULL
);
95 strmap_set(orhist
->link_history_map
, to_hexid
, lhist
);
101 _free_link_history(void *val
)
107 free_or_history(or_history_t
*hist
)
109 strmap_free(hist
->link_history_map
, _free_link_history
);
113 /** Update an or_history_t object <b>hist</b> so that its uptime/downtime
114 * count is up-to-date as of <b>when</b>.
116 static void update_or_history(or_history_t
*hist
, time_t when
)
119 if (hist
->up_since
) {
120 tor_assert(!hist
->down_since
);
121 hist
->uptime
+= (when
- hist
->up_since
);
122 hist
->up_since
= when
;
123 } else if (hist
->down_since
) {
124 hist
->downtime
+= (when
- hist
->down_since
);
125 hist
->down_since
= when
;
129 /** Initialize the static data structures for tracking history.
131 void rep_hist_init(void)
133 history_map
= strmap_new();
137 /** Remember that an attempt to connect to the OR with identity digest
138 * <b>id</b> failed at <b>when</b>.
140 void rep_hist_note_connect_failed(const char* id
, time_t when
)
143 hist
= get_or_history(id
);
147 if (hist
->up_since
) {
148 hist
->uptime
+= (when
- hist
->up_since
);
151 if (!hist
->down_since
)
152 hist
->down_since
= when
;
153 hist
->changed
= when
;
156 /** Remember that an attempt to connect to the OR with identity digest
157 * <b>id</b> succeeded at <b>when</b>.
159 void rep_hist_note_connect_succeeded(const char* id
, time_t when
)
162 hist
= get_or_history(id
);
166 if (hist
->down_since
) {
167 hist
->downtime
+= (when
- hist
->down_since
);
168 hist
->down_since
= 0;
171 hist
->up_since
= when
;
172 hist
->changed
= when
;
175 /** Remember that we intentionally closed our connection to the OR
176 * with identity digest <b>id</b> at <b>when</b>.
178 void rep_hist_note_disconnect(const char* id
, time_t when
)
181 hist
= get_or_history(id
);
185 if (hist
->up_since
) {
186 hist
->uptime
+= (when
- hist
->up_since
);
189 hist
->changed
= when
;
192 /** Remember that our connection to the OR with identity digest
193 * <b>id</b> had an error and stopped working at <b>when</b>.
195 void rep_hist_note_connection_died(const char* id
, time_t when
)
199 /* XXXX009 Well, everybody has an ID now. Hm. */
200 /* If conn has no nickname, it's either an OP, or it is an OR
201 * which didn't complete its handshake (or did and was unapproved).
206 hist
= get_or_history(id
);
209 if (hist
->up_since
) {
210 hist
->uptime
+= (when
- hist
->up_since
);
213 if (!hist
->down_since
)
214 hist
->down_since
= when
;
215 hist
->changed
= when
;
218 /** Remember that we successfully extended from the OR with identity
219 * digest <b>from_id</b> to the OR with identity digest
222 void rep_hist_note_extend_succeeded(const char *from_id
,
225 link_history_t
*hist
;
226 /* log_fn(LOG_WARN, "EXTEND SUCCEEDED: %s->%s",from_name,to_name); */
227 hist
= get_link_history(from_id
, to_id
);
231 hist
->changed
= time(NULL
);
234 /** Remember that we tried to extend from the OR with identity digest
235 * <b>from_id</b> to the OR with identity digest <b>to_name</b>, but
238 void rep_hist_note_extend_failed(const char *from_id
, const char *to_id
)
240 link_history_t
*hist
;
241 /* log_fn(LOG_WARN, "EXTEND FAILED: %s->%s",from_name,to_name); */
242 hist
= get_link_history(from_id
, to_id
);
245 ++hist
->n_extend_fail
;
246 hist
->changed
= time(NULL
);
249 /** Log all the reliability data we have rememberred, with the chosen
252 void rep_hist_dump_stats(time_t now
, int severity
)
254 strmap_iter_t
*lhist_it
;
255 strmap_iter_t
*orhist_it
;
256 const char *name1
, *name2
, *hexdigest1
, *hexdigest2
;
257 or_history_t
*or_history
;
258 link_history_t
*link_history
;
259 void *or_history_p
, *link_history_p
;
264 unsigned long upt
, downt
;
267 rep_history_clean(now
-24*60*60);
269 log(severity
, "--------------- Dumping history information:");
271 for (orhist_it
= strmap_iter_init(history_map
); !strmap_iter_done(orhist_it
);
272 orhist_it
= strmap_iter_next(history_map
,orhist_it
)) {
273 strmap_iter_get(orhist_it
, &hexdigest1
, &or_history_p
);
274 or_history
= (or_history_t
*) or_history_p
;
276 if ((r
= router_get_by_hexdigest(hexdigest1
)))
281 update_or_history(or_history
, now
);
282 upt
= or_history
->uptime
;
283 downt
= or_history
->downtime
;
285 uptime
= ((double)upt
) / (upt
+downt
);
290 "OR %s [%s]: %ld/%ld good connections; uptime %ld/%ld sec (%.2f%%)",
292 or_history
->n_conn_ok
, or_history
->n_conn_fail
+or_history
->n_conn_ok
,
293 upt
, upt
+downt
, uptime
*100.0);
295 if (!strmap_isempty(or_history
->link_history_map
)) {
296 strlcpy(buffer
, " Good extend attempts: ", sizeof(buffer
));
297 len
= strlen(buffer
);
298 for (lhist_it
= strmap_iter_init(or_history
->link_history_map
);
299 !strmap_iter_done(lhist_it
);
300 lhist_it
= strmap_iter_next(or_history
->link_history_map
, lhist_it
)) {
301 strmap_iter_get(lhist_it
, &hexdigest2
, &link_history_p
);
302 if ((r
= router_get_by_hexdigest(hexdigest2
)))
307 link_history
= (link_history_t
*) link_history_p
;
309 ret
= tor_snprintf(buffer
+len
, 2048-len
, "%s(%ld/%ld); ", name2
,
310 link_history
->n_extend_ok
,
311 link_history
->n_extend_ok
+link_history
->n_extend_fail
);
317 log(severity
, "%s", buffer
);
322 /** Remove history info for routers/links that haven't changed since
324 void rep_history_clean(time_t before
)
326 or_history_t
*or_history
;
327 link_history_t
*link_history
;
328 void *or_history_p
, *link_history_p
;
329 strmap_iter_t
*orhist_it
, *lhist_it
;
330 const char *hd1
, *hd2
;
332 orhist_it
= strmap_iter_init(history_map
);
333 while (!strmap_iter_done(orhist_it
)) {
334 strmap_iter_get(orhist_it
, &hd1
, &or_history_p
);
335 or_history
= or_history_p
;
336 if (or_history
->changed
< before
) {
337 free_or_history(or_history
);
338 orhist_it
= strmap_iter_next_rmv(history_map
, orhist_it
);
341 for (lhist_it
= strmap_iter_init(or_history
->link_history_map
);
342 !strmap_iter_done(lhist_it
); ) {
343 strmap_iter_get(lhist_it
, &hd2
, &link_history_p
);
344 link_history
= link_history_p
;
345 if (link_history
->changed
< before
) {
346 tor_free(link_history
);
347 lhist_it
= strmap_iter_next_rmv(or_history
->link_history_map
,lhist_it
);
350 lhist_it
= strmap_iter_next(or_history
->link_history_map
,lhist_it
);
352 orhist_it
= strmap_iter_next(history_map
, orhist_it
);
357 void write_rep_history(const char *filename
)
362 or_history_t
*or_history
;
363 link_history_t
*link_history
;
364 strmap_iter_t
*lhist_it
;
365 strmap_iter_t
*orhist_it
;
366 void *or_history_p
, *link_history_p
;
369 tmpfile
= tor_malloc(strlen(filename
)+5);
370 tor_snprintf(tmpfile
, strlen(filename
)+5, "%s_tmp", filename
);
372 f
= fopen(tmpfile
, "w");
374 for (orhist_it
= strmap_iter_init(history_map
); !strmap_iter_done(orhist_it
);
375 orhist_it
= strmap_iter_next(history_map
,orhist_it
)) {
376 strmap_iter_get(orhist_it
, &name1
, &or_history_p
);
377 or_history
= (or_history_t
*) or_history_p
;
378 fprintf(f
, "link %s connected:u%ld failed:%uld uptime:%uld",
379 name1
, or_history
->since1
,
386 replace_file(filename
, tmpfile
);
393 #define NUM_SECS_ROLLING_MEASURE 10
394 #define NUM_SECS_BW_SUM_IS_VALID (24*60*60) /* one day */
395 #define NUM_SECS_BW_SUM_INTERVAL (15*60)
396 #define NUM_TOTALS (NUM_SECS_BW_SUM_IS_VALID/NUM_SECS_BW_SUM_INTERVAL)
399 * Structure to track bandwidth use, and remember the maxima for a given
402 typedef struct bw_array_t
{
403 /** Observation array: Total number of bytes transferred in each of the last
404 * NUM_SECS_ROLLING_MEASURE seconds. This is used as a circular array. */
405 int obs
[NUM_SECS_ROLLING_MEASURE
];
406 int cur_obs_idx
; /**< Current position in obs. */
407 time_t cur_obs_time
; /**< Time represented in obs[cur_obs_idx] */
408 int total_obs
; /**< Total for all members of obs except obs[cur_obs_idx] */
409 int max_total
; /**< Largest value that total_obs has taken on in the current
411 int total_in_period
; /**< Total bytes transferred in the current period. */
413 /** When does the next period begin? */
415 /** Where in 'maxima' should the maximum bandwidth usage for the current
416 * period be stored? */
418 /** How many values in maxima/totals have been set ever? */
420 /** Circular array of the maximum
421 * bandwidth-per-NUM_SECS_ROLLING_MEASURE usage for the last
422 * NUM_TOTALS periods */
423 int maxima
[NUM_TOTALS
];
424 /** Circular array of the total bandwidth usage for the last NUM_TOTALS
426 int totals
[NUM_TOTALS
];
429 /** Shift the current period of b forward by one.
431 static void commit_max(bw_array_t
*b
) {
432 /* Store total from current period. */
433 b
->totals
[b
->next_max_idx
] = b
->total_in_period
;
434 /* Store maximum from current period. */
435 b
->maxima
[b
->next_max_idx
++] = b
->max_total
;
436 /* Advance next_period and next_max_idx */
437 b
->next_period
+= NUM_SECS_BW_SUM_INTERVAL
;
438 if (b
->next_max_idx
== NUM_TOTALS
)
440 if (b
->num_maxes_set
< NUM_TOTALS
)
442 /* Reset max_total. */
444 /* Reset total_in_period. */
445 b
->total_in_period
= 0;
448 /** Shift the current observation time of 'b' forward by one second.
450 static INLINE
void advance_obs(bw_array_t
*b
) {
454 /* Calculate the total bandwidth for the last NUM_SECS_ROLLING_MEASURE
455 * seconds; adjust max_total as needed.*/
456 total
= b
->total_obs
+ b
->obs
[b
->cur_obs_idx
];
457 if (total
> b
->max_total
)
458 b
->max_total
= total
;
460 nextidx
= b
->cur_obs_idx
+1;
461 if (nextidx
== NUM_SECS_ROLLING_MEASURE
)
464 b
->total_obs
= total
- b
->obs
[nextidx
];
466 b
->cur_obs_idx
= nextidx
;
468 if (++b
->cur_obs_time
>= b
->next_period
)
472 /** Add 'n' bytes to the number of bytes in b for second 'when'.
474 static INLINE
void add_obs(bw_array_t
*b
, time_t when
, int n
) {
475 /* Don't record data in the past. */
476 if (when
<b
->cur_obs_time
)
478 /* If we're currently adding observations for an earlier second than
479 * 'when', advance b->cur_obs_time and b->cur_obs_idx by an
480 * appropriate number of seconds, and do all the other housekeeping */
481 while (when
>b
->cur_obs_time
)
484 b
->obs
[b
->cur_obs_idx
] += n
;
485 b
->total_in_period
+= n
;
488 /** Allocate, initialize, and return a new bw_array.
490 static bw_array_t
*bw_array_new(void) {
493 b
= tor_malloc_zero(sizeof(bw_array_t
));
495 b
->cur_obs_time
= start
;
496 b
->next_period
= start
+ NUM_SECS_BW_SUM_INTERVAL
;
500 static bw_array_t
*read_array
= NULL
;
501 static bw_array_t
*write_array
= NULL
;
503 /** Set up read_array and write_array
505 static void bw_arrays_init(void)
507 read_array
= bw_array_new();
508 write_array
= bw_array_new();
511 /** We read <b>num_bytes</b> more bytes in second <b>when</b>.
513 * Add num_bytes to the current running total for <b>when</b>.
515 * <b>when</b> can go back to time, but it's safe to ignore calls
516 * earlier than the latest <b>when</b> you've heard of.
518 void rep_hist_note_bytes_written(int num_bytes
, time_t when
) {
519 /* Maybe a circular array for recent seconds, and step to a new point
520 * every time a new second shows up. Or simpler is to just to have
521 * a normal array and push down each item every second; it's short.
523 /* When a new second has rolled over, compute the sum of the bytes we've
524 * seen over when-1 to when-1-NUM_SECS_ROLLING_MEASURE, and stick it
525 * somewhere. See rep_hist_bandwidth_assess() below.
527 add_obs(write_array
, when
, num_bytes
);
530 /** We wrote <b>num_bytes</b> more bytes in second <b>when</b>.
531 * (like rep_hist_note_bytes_written() above)
533 void rep_hist_note_bytes_read(int num_bytes
, time_t when
) {
534 /* if we're smart, we can make this func and the one above share code */
535 add_obs(read_array
, when
, num_bytes
);
538 /** Helper: Return the largest value in b->maxima. (This is equal to the
539 * most bandwidth used in any NUM_SECS_ROLLING_MEASURE period for the last
540 * NUM_SECS_BW_SUM_IS_VALID seconds.)
542 static int find_largest_max(bw_array_t
*b
)
546 for (i
=0; i
<NUM_TOTALS
; ++i
) {
547 if (b
->maxima
[i
]>max
)
554 * Find the largest sums in the past NUM_SECS_BW_SUM_IS_VALID (roughly)
555 * seconds. Find one sum for reading and one for writing. They don't have
556 * to be at the same time).
558 * Return the smaller of these sums, divided by NUM_SECS_ROLLING_MEASURE.
560 int rep_hist_bandwidth_assess(void) {
562 r
= find_largest_max(read_array
);
563 w
= find_largest_max(write_array
);
565 return (int)(w
/(double)NUM_SECS_ROLLING_MEASURE
);
567 return (int)(r
/(double)NUM_SECS_ROLLING_MEASURE
);
573 * Allocate and return lines for representing this server's bandwidth
574 * history in its descriptor.
577 rep_hist_get_bandwidth_lines(void)
580 char t
[ISO_TIME_LEN
+1];
585 /* opt (read|write)-history yyyy-mm-dd HH:MM:SS (n s) n,n,n,n,n... */
586 len
= (60+12*NUM_TOTALS
)*2;
587 buf
= tor_malloc_zero(len
);
590 b
= r
?read_array
:write_array
;
592 format_iso_time(t
, b
->next_period
-NUM_SECS_BW_SUM_INTERVAL
);
593 tor_snprintf(cp
, len
-(cp
-buf
), "opt %s %s (%d s) ", r
?"read-history ":"write-history", t
,
594 NUM_SECS_BW_SUM_INTERVAL
);
597 if (b
->num_maxes_set
<= b
->next_max_idx
)
598 /* We haven't been through the circular array yet; time starts at i=0.*/
601 /* We've been arround the array at least once. The next i to be
602 overwritten is the oldest. */
605 for (n
=0; n
<b
->num_maxes_set
; ++n
,++i
) {
606 while (i
>= NUM_TOTALS
) i
-= NUM_TOTALS
;
607 if (n
==(b
->num_maxes_set
-1))
608 tor_snprintf(cp
, len
-(cp
-buf
), "%d", b
->totals
[i
]);
610 tor_snprintf(cp
, len
-(cp
-buf
), "%d,", b
->totals
[i
]);
613 strlcat(cp
, "\n", len
-(cp
-buf
));