1 /* Copyright (c) 2007-2010, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
6 * \brief Functions related to maintaining an IP-to-country database and to
7 * summarizing client connections by country.
14 static void clear_geoip_db(void);
16 /** An entry from the GeoIP file: maps an IP range to a country. */
17 typedef struct geoip_entry_t
{
18 uint32_t ip_low
; /**< The lowest IP in the range, in host order */
19 uint32_t ip_high
; /**< The highest IP in the range, in host order */
20 intptr_t country
; /**< An index into geoip_countries */
23 /** For how many periods should we remember per-country request history? */
24 #define REQUEST_HIST_LEN 3
25 /** How long are the periods for which we should remember request history? */
26 #define REQUEST_HIST_PERIOD (8*60*60)
28 /** A per-country record for GeoIP request history. */
29 typedef struct geoip_country_t
{
31 uint32_t n_v2_ns_requests
[REQUEST_HIST_LEN
];
32 uint32_t n_v3_ns_requests
[REQUEST_HIST_LEN
];
35 /** A list of geoip_country_t */
36 static smartlist_t
*geoip_countries
= NULL
;
37 /** A map from lowercased country codes to their position in geoip_countries.
38 * The index is encoded in the pointer, and 1 is added so that NULL can mean
40 static strmap_t
*country_idxplus1_by_lc_code
= NULL
;
41 /** A list of all known geoip_entry_t, sorted by ip_low. */
42 static smartlist_t
*geoip_entries
= NULL
;
44 /** Return the index of the <b>country</b>'s entry in the GeoIP DB
45 * if it is a valid 2-letter country code, otherwise return zero.
48 geoip_get_country(const char *country
)
53 _idxplus1
= strmap_get_lc(country_idxplus1_by_lc_code
, country
);
57 idx
= ((uintptr_t)_idxplus1
)-1;
58 return (country_t
)idx
;
61 /** Add an entry to the GeoIP table, mapping all IPs between <b>low</b> and
62 * <b>high</b>, inclusive, to the 2-letter country code <b>country</b>.
65 geoip_add_entry(uint32_t low
, uint32_t high
, const char *country
)
74 _idxplus1
= strmap_get_lc(country_idxplus1_by_lc_code
, country
);
77 geoip_country_t
*c
= tor_malloc_zero(sizeof(geoip_country_t
));
78 strlcpy(c
->countrycode
, country
, sizeof(c
->countrycode
));
79 tor_strlower(c
->countrycode
);
80 smartlist_add(geoip_countries
, c
);
81 idx
= smartlist_len(geoip_countries
) - 1;
82 strmap_set_lc(country_idxplus1_by_lc_code
, country
, (void*)(idx
+1));
84 idx
= ((uintptr_t)_idxplus1
)-1;
87 geoip_country_t
*c
= smartlist_get(geoip_countries
, idx
);
88 tor_assert(!strcasecmp(c
->countrycode
, country
));
90 ent
= tor_malloc_zero(sizeof(geoip_entry_t
));
94 smartlist_add(geoip_entries
, ent
);
97 /** Add an entry to the GeoIP table, parsing it from <b>line</b>. The
98 * format is as for geoip_load_file(). */
100 geoip_parse_entry(const char *line
)
102 unsigned int low
, high
;
104 if (!geoip_countries
) {
105 geoip_countries
= smartlist_create();
106 geoip_entries
= smartlist_create();
107 country_idxplus1_by_lc_code
= strmap_new();
109 while (TOR_ISSPACE(*line
))
113 if (sscanf(line
,"%u,%u,%2s", &low
, &high
, b
) == 3) {
114 geoip_add_entry(low
, high
, b
);
116 } else if (sscanf(line
,"\"%u\",\"%u\",\"%2s\",", &low
, &high
, b
) == 3) {
117 geoip_add_entry(low
, high
, b
);
120 log_warn(LD_GENERAL
, "Unable to parse line from GEOIP file: %s",
126 /** Sorting helper: return -1, 1, or 0 based on comparison of two
129 _geoip_compare_entries(const void **_a
, const void **_b
)
131 const geoip_entry_t
*a
= *_a
, *b
= *_b
;
132 if (a
->ip_low
< b
->ip_low
)
134 else if (a
->ip_low
> b
->ip_low
)
140 /** bsearch helper: return -1, 1, or 0 based on comparison of an IP (a pointer
141 * to a uint32_t in host order) to a geoip_entry_t */
143 _geoip_compare_key_to_entry(const void *_key
, const void **_member
)
145 const uint32_t addr
= *(uint32_t *)_key
;
146 const geoip_entry_t
*entry
= *_member
;
147 if (addr
< entry
->ip_low
)
149 else if (addr
> entry
->ip_high
)
155 /** Return 1 if we should collect geoip stats on bridge users, and
156 * include them in our extrainfo descriptor. Else return 0. */
158 should_record_bridge_info(or_options_t
*options
)
160 return options
->BridgeRelay
&& options
->BridgeRecordUsageByCountry
;
163 /** Clear the GeoIP database and reload it from the file
164 * <b>filename</b>. Return 0 on success, -1 on failure.
166 * Recognized line formats are:
167 * INTIPLOW,INTIPHIGH,CC
169 * "INTIPLOW","INTIPHIGH","CC","CC3","COUNTRY NAME"
170 * where INTIPLOW and INTIPHIGH are IPv4 addresses encoded as 4-byte unsigned
171 * integers, and CC is a country code.
173 * It also recognizes, and skips over, blank lines and lines that start
174 * with '#' (comments).
177 geoip_load_file(const char *filename
, or_options_t
*options
)
180 const char *msg
= "";
181 int severity
= options_need_geoip_info(options
, &msg
) ? LOG_WARN
: LOG_INFO
;
183 if (!(f
= fopen(filename
, "r"))) {
184 log_fn(severity
, LD_GENERAL
, "Failed to open GEOIP file %s. %s",
188 if (!geoip_countries
) {
189 geoip_countries
= smartlist_create();
190 country_idxplus1_by_lc_code
= strmap_new();
193 SMARTLIST_FOREACH(geoip_entries
, geoip_entry_t
*, e
, tor_free(e
));
194 smartlist_free(geoip_entries
);
196 geoip_entries
= smartlist_create();
197 log_notice(LD_GENERAL
, "Parsing GEOIP file.");
200 if (fgets(buf
, (int)sizeof(buf
), f
) == NULL
)
202 /* FFFF track full country name. */
203 geoip_parse_entry(buf
);
205 /*XXXX abort and return -1 if no entries/illformed?*/
208 smartlist_sort(geoip_entries
, _geoip_compare_entries
);
210 /* Okay, now we need to maybe change our mind about what is in which
212 refresh_all_country_info();
217 /** Given an IP address in host order, return a number representing the
218 * country to which that address belongs, or -1 for unknown. The return value
219 * will always be less than geoip_get_n_countries(). To decode it,
220 * call geoip_get_country_name().
223 geoip_get_country_by_ip(uint32_t ipaddr
)
228 ent
= smartlist_bsearch(geoip_entries
, &ipaddr
, _geoip_compare_key_to_entry
);
229 return ent
? (int)ent
->country
: -1;
232 /** Return the number of countries recognized by the GeoIP database. */
234 geoip_get_n_countries(void)
236 return (int) smartlist_len(geoip_countries
);
239 /** Return the two-letter country code associated with the number <b>num</b>,
240 * or "??" for an unknown value. */
242 geoip_get_country_name(country_t num
)
244 if (geoip_countries
&& num
>= 0 && num
< smartlist_len(geoip_countries
)) {
245 geoip_country_t
*c
= smartlist_get(geoip_countries
, num
);
246 return c
->countrycode
;
251 /** Return true iff we have loaded a GeoIP database.*/
253 geoip_is_loaded(void)
255 return geoip_countries
!= NULL
&& geoip_entries
!= NULL
;
258 /** Entry in a map from IP address to the last time we've seen an incoming
259 * connection from that IP address. Used by bridges only, to track which
260 * countries have them blocked. */
261 typedef struct clientmap_entry_t
{
262 HT_ENTRY(clientmap_entry_t
) node
;
264 time_t last_seen
; /* The last 2 bits of this value hold the client
268 #define ACTION_MASK 3
270 /** Map from client IP address to last time seen. */
271 static HT_HEAD(clientmap
, clientmap_entry_t
) client_history
=
273 /** Time at which we started tracking client IP history. */
274 static time_t client_history_starts
= 0;
276 /** When did the current period of checking per-country request history
278 static time_t current_request_period_starts
= 0;
279 /** How many older request periods are we remembering? */
280 static int n_old_request_periods
= 0;
282 /** Hashtable helper: compute a hash of a clientmap_entry_t. */
283 static INLINE
unsigned
284 clientmap_entry_hash(const clientmap_entry_t
*a
)
286 return ht_improve_hash((unsigned) a
->ipaddr
);
288 /** Hashtable helper: compare two clientmap_entry_t values for equality. */
290 clientmap_entries_eq(const clientmap_entry_t
*a
, const clientmap_entry_t
*b
)
292 return a
->ipaddr
== b
->ipaddr
;
295 HT_PROTOTYPE(clientmap
, clientmap_entry_t
, node
, clientmap_entry_hash
,
296 clientmap_entries_eq
);
297 HT_GENERATE(clientmap
, clientmap_entry_t
, node
, clientmap_entry_hash
,
298 clientmap_entries_eq
, 0.6, malloc
, realloc
, free
);
300 /** Note that we've seen a client connect from the IP <b>addr</b> (host order)
301 * at time <b>now</b>. Ignored by all but bridges. */
303 geoip_note_client_seen(geoip_client_action_t action
,
304 uint32_t addr
, time_t now
)
306 or_options_t
*options
= get_options();
307 clientmap_entry_t lookup
, *ent
;
308 if (action
== GEOIP_CLIENT_CONNECT
) {
309 if (!(options
->BridgeRelay
&& options
->BridgeRecordUsageByCountry
))
311 /* Did we recently switch from bridge to relay or back? */
312 if (client_history_starts
> now
)
315 #ifndef ENABLE_GEOIP_STATS
318 if (options
->BridgeRelay
|| options
->BridgeAuthoritativeDir
||
319 !options
->DirRecordUsageByCountry
)
324 /* Rotate the current request period. */
325 while (current_request_period_starts
+ REQUEST_HIST_PERIOD
< now
) {
326 if (!geoip_countries
)
327 geoip_countries
= smartlist_create();
328 if (!current_request_period_starts
) {
329 current_request_period_starts
= now
;
332 SMARTLIST_FOREACH(geoip_countries
, geoip_country_t
*, c
, {
333 memmove(&c
->n_v2_ns_requests
[0], &c
->n_v2_ns_requests
[1],
334 sizeof(uint32_t)*(REQUEST_HIST_LEN
-1));
335 memmove(&c
->n_v3_ns_requests
[0], &c
->n_v3_ns_requests
[1],
336 sizeof(uint32_t)*(REQUEST_HIST_LEN
-1));
337 c
->n_v2_ns_requests
[REQUEST_HIST_LEN
-1] = 0;
338 c
->n_v3_ns_requests
[REQUEST_HIST_LEN
-1] = 0;
340 current_request_period_starts
+= REQUEST_HIST_PERIOD
;
341 if (n_old_request_periods
< REQUEST_HIST_LEN
-1)
342 ++n_old_request_periods
;
345 /* We use the low 3 bits of the time to encode the action. Since we're
346 * potentially remembering tons of clients, we don't want to make
347 * clientmap_entry_t larger than it has to be. */
348 now
= (now
& ~ACTION_MASK
) | (((int)action
) & ACTION_MASK
);
349 lookup
.ipaddr
= addr
;
350 ent
= HT_FIND(clientmap
, &client_history
, &lookup
);
352 ent
->last_seen
= now
;
354 ent
= tor_malloc_zero(sizeof(clientmap_entry_t
));
356 ent
->last_seen
= now
;
357 HT_INSERT(clientmap
, &client_history
, ent
);
360 if (action
== GEOIP_CLIENT_NETWORKSTATUS
||
361 action
== GEOIP_CLIENT_NETWORKSTATUS_V2
) {
362 int country_idx
= geoip_get_country_by_ip(addr
);
363 if (country_idx
>= 0 && country_idx
< smartlist_len(geoip_countries
)) {
364 geoip_country_t
*country
= smartlist_get(geoip_countries
, country_idx
);
365 if (action
== GEOIP_CLIENT_NETWORKSTATUS
)
366 ++country
->n_v3_ns_requests
[REQUEST_HIST_LEN
-1];
368 ++country
->n_v2_ns_requests
[REQUEST_HIST_LEN
-1];
372 if (!client_history_starts
) {
373 client_history_starts
= now
;
374 current_request_period_starts
= now
;
378 /** HT_FOREACH helper: remove a clientmap_entry_t from the hashtable if it's
379 * older than a certain time. */
381 _remove_old_client_helper(struct clientmap_entry_t
*ent
, void *_cutoff
)
383 time_t cutoff
= *(time_t*)_cutoff
;
384 if (ent
->last_seen
< cutoff
) {
392 /** Forget about all clients that haven't connected since <b>cutoff</b>.
393 * If <b>cutoff</b> is in the future, clients won't be added to the history
394 * until this time is reached. This is useful to prevent relays that switch
395 * to bridges from reporting unbelievable numbers of clients. */
397 geoip_remove_old_clients(time_t cutoff
)
399 clientmap_HT_FOREACH_FN(&client_history
,
400 _remove_old_client_helper
,
402 if (client_history_starts
< cutoff
)
403 client_history_starts
= cutoff
;
406 /** Do not mention any country from which fewer than this number of IPs have
407 * connected. This conceivably avoids reporting information that could
408 * deanonymize users, though analysis is lacking. */
409 #define MIN_IPS_TO_NOTE_COUNTRY 1
410 /** Do not report any geoip data at all if we have fewer than this number of
411 * IPs to report about. */
412 #define MIN_IPS_TO_NOTE_ANYTHING 1
413 /** When reporting geoip data about countries, round up to the nearest
414 * multiple of this value. */
415 #define IP_GRANULARITY 8
417 /** Return the time at which we started recording geoip data. */
419 geoip_get_history_start(void)
421 return client_history_starts
;
424 /** Helper type: used to sort per-country totals by value. */
425 typedef struct c_hist_t
{
426 char country
[3]; /**< Two-letter country code. */
427 unsigned total
; /**< Total IP addresses seen in this country. */
430 /** Sorting helper: return -1, 1, or 0 based on comparison of two
431 * geoip_entry_t. Sort in descending order of total, and then by country
434 _c_hist_compare(const void **_a
, const void **_b
)
436 const c_hist_t
*a
= *_a
, *b
= *_b
;
437 if (a
->total
> b
->total
)
439 else if (a
->total
< b
->total
)
442 return strcmp(a
->country
, b
->country
);
445 /** How long do we have to have observed per-country request history before we
446 * are willing to talk about it? */
447 #define GEOIP_MIN_OBSERVATION_TIME (12*60*60)
449 /** Return the lowest x such that x is at least <b>number</b>, and x modulo
450 * <b>divisor</b> == 0. */
451 static INLINE
unsigned
452 round_to_next_multiple_of(unsigned number
, unsigned divisor
)
454 number
+= divisor
- 1;
455 number
-= number
% divisor
;
459 /** Return a newly allocated comma-separated string containing entries for all
460 * the countries from which we've seen enough clients connect. The entry
461 * format is cc=num where num is the number of IPs we've seen connecting from
462 * that country, and cc is a lowercased country code. Returns NULL if we don't
463 * want to export geoip data yet. */
465 geoip_get_client_history(time_t now
, geoip_client_action_t action
)
468 if (!geoip_is_loaded())
470 if (client_history_starts
< (now
- GEOIP_MIN_OBSERVATION_TIME
)) {
472 smartlist_t
*chunks
= NULL
;
473 smartlist_t
*entries
= NULL
;
474 int n_countries
= geoip_get_n_countries();
476 clientmap_entry_t
**ent
;
477 unsigned *counts
= tor_malloc_zero(sizeof(unsigned)*n_countries
);
479 unsigned granularity
= IP_GRANULARITY
;
480 #ifdef ENABLE_GEOIP_STATS
481 if (get_options()->DirRecordUsageByCountry
)
482 granularity
= get_options()->DirRecordUsageGranularity
;
484 HT_FOREACH(ent
, clientmap
, &client_history
) {
486 if (((*ent
)->last_seen
& ACTION_MASK
) != (int)action
)
488 country
= geoip_get_country_by_ip((*ent
)->ipaddr
);
491 tor_assert(0 <= country
&& country
< n_countries
);
495 /* Don't record anything if we haven't seen enough IPs. */
496 if (total
< MIN_IPS_TO_NOTE_ANYTHING
)
498 /* Make a list of c_hist_t */
499 entries
= smartlist_create();
500 for (i
= 0; i
< n_countries
; ++i
) {
501 unsigned c
= counts
[i
];
502 const char *countrycode
;
504 /* Only report a country if it has a minimum number of IPs. */
505 if (c
>= MIN_IPS_TO_NOTE_COUNTRY
) {
506 c
= round_to_next_multiple_of(c
, granularity
);
507 countrycode
= geoip_get_country_name(i
);
508 ent
= tor_malloc(sizeof(c_hist_t
));
509 strlcpy(ent
->country
, countrycode
, sizeof(ent
->country
));
511 smartlist_add(entries
, ent
);
514 /* Sort entries. Note that we must do this _AFTER_ rounding, or else
515 * the sort order could leak info. */
516 smartlist_sort(entries
, _c_hist_compare
);
518 /* Build the result. */
519 chunks
= smartlist_create();
520 SMARTLIST_FOREACH(entries
, c_hist_t
*, ch
, {
521 tor_snprintf(buf
, sizeof(buf
), "%s=%u", ch
->country
, ch
->total
);
522 smartlist_add(chunks
, tor_strdup(buf
));
524 result
= smartlist_join_strings(chunks
, ",", 0, NULL
);
528 SMARTLIST_FOREACH(chunks
, char *, c
, tor_free(c
));
529 smartlist_free(chunks
);
532 SMARTLIST_FOREACH(entries
, c_hist_t
*, c
, tor_free(c
));
533 smartlist_free(entries
);
539 /** Return a newly allocated string holding the per-country request history
540 * for <b>action</b> in a format suitable for an extra-info document, or NULL
543 geoip_get_request_history(time_t now
, geoip_client_action_t action
)
545 smartlist_t
*entries
, *strings
;
547 unsigned granularity
= IP_GRANULARITY
;
548 #ifdef ENABLE_GEOIP_STATS
549 if (get_options()->DirRecordUsageByCountry
)
550 granularity
= get_options()->DirRecordUsageGranularity
;
553 if (client_history_starts
>= (now
- GEOIP_MIN_OBSERVATION_TIME
))
555 if (action
!= GEOIP_CLIENT_NETWORKSTATUS
&&
556 action
!= GEOIP_CLIENT_NETWORKSTATUS_V2
)
558 if (!geoip_countries
)
561 entries
= smartlist_create();
562 SMARTLIST_FOREACH(geoip_countries
, geoip_country_t
*, c
, {
563 uint32_t *n
= (action
== GEOIP_CLIENT_NETWORKSTATUS
)
564 ? c
->n_v3_ns_requests
: c
->n_v2_ns_requests
;
568 for (i
=0; i
< REQUEST_HIST_LEN
; ++i
)
572 ent
= tor_malloc_zero(sizeof(c_hist_t
));
573 strlcpy(ent
->country
, c
->countrycode
, sizeof(ent
->country
));
574 ent
->total
= round_to_next_multiple_of(tot
, granularity
);
575 smartlist_add(entries
, ent
);
577 smartlist_sort(entries
, _c_hist_compare
);
579 strings
= smartlist_create();
580 SMARTLIST_FOREACH(entries
, c_hist_t
*, ent
, {
582 tor_snprintf(buf
, sizeof(buf
), "%s=%u", ent
->country
, ent
->total
);
583 smartlist_add(strings
, tor_strdup(buf
));
585 result
= smartlist_join_strings(strings
, ",", 0, NULL
);
586 SMARTLIST_FOREACH(strings
, char *, cp
, tor_free(cp
));
587 SMARTLIST_FOREACH(entries
, c_hist_t
*, ent
, tor_free(ent
));
588 smartlist_free(strings
);
589 smartlist_free(entries
);
593 /** Store all our geoip statistics into $DATADIR/geoip-stats. */
595 dump_geoip_stats(void)
597 #ifdef ENABLE_GEOIP_STATS
598 time_t now
= time(NULL
);
599 time_t request_start
;
600 char *filename
= get_datadir_fname("geoip-stats");
601 char *data_v2
= NULL
, *data_v3
= NULL
;
602 char since
[ISO_TIME_LEN
+1], written
[ISO_TIME_LEN
+1];
603 open_file_t
*open_file
= NULL
;
604 double v2_share
= 0.0, v3_share
= 0.0;
607 data_v2
= geoip_get_client_history(now
, GEOIP_CLIENT_NETWORKSTATUS_V2
);
608 data_v3
= geoip_get_client_history(now
, GEOIP_CLIENT_NETWORKSTATUS
);
609 format_iso_time(since
, geoip_get_history_start());
610 format_iso_time(written
, now
);
611 out
= start_writing_to_stdio_file(filename
, OPEN_FLAGS_REPLACE
,
615 if (fprintf(out
, "written %s\nstarted-at %s\nns-ips %s\nns-v2-ips %s\n",
617 data_v3
? data_v3
: "", data_v2
? data_v2
: "") < 0)
622 request_start
= current_request_period_starts
-
623 (n_old_request_periods
* REQUEST_HIST_PERIOD
);
624 format_iso_time(since
, request_start
);
625 data_v2
= geoip_get_request_history(now
, GEOIP_CLIENT_NETWORKSTATUS_V2
);
626 data_v3
= geoip_get_request_history(now
, GEOIP_CLIENT_NETWORKSTATUS
);
627 if (fprintf(out
, "requests-start %s\nn-ns-reqs %s\nn-v2-ns-reqs %s\n",
629 data_v3
? data_v3
: "", data_v2
? data_v2
: "") < 0)
631 if (!router_get_my_share_of_directory_requests(&v2_share
, &v3_share
)) {
632 if (fprintf(out
, "v2-ns-share %0.2lf%%\n", v2_share
*100) < 0)
634 if (fprintf(out
, "v3-ns-share %0.2lf%%\n", v3_share
*100) < 0)
638 finish_writing_to_file(open_file
);
642 abort_writing_to_file(open_file
);
649 /** Helper used to implement GETINFO ip-to-country/... controller command. */
651 getinfo_helper_geoip(control_connection_t
*control_conn
,
652 const char *question
, char **answer
)
655 if (geoip_is_loaded() && !strcmpstart(question
, "ip-to-country/")) {
659 question
+= strlen("ip-to-country/");
660 if (tor_inet_aton(question
, &in
) != 0) {
661 ip
= ntohl(in
.s_addr
);
662 c
= geoip_get_country_by_ip(ip
);
663 *answer
= tor_strdup(geoip_get_country_name(c
));
669 /** Release all storage held by the GeoIP database. */
673 if (geoip_countries
) {
674 SMARTLIST_FOREACH(geoip_countries
, geoip_country_t
*, c
, tor_free(c
));
675 smartlist_free(geoip_countries
);
677 if (country_idxplus1_by_lc_code
)
678 strmap_free(country_idxplus1_by_lc_code
, NULL
);
680 SMARTLIST_FOREACH(geoip_entries
, geoip_entry_t
*, ent
, tor_free(ent
));
681 smartlist_free(geoip_entries
);
683 geoip_countries
= NULL
;
684 country_idxplus1_by_lc_code
= NULL
;
685 geoip_entries
= NULL
;
688 /** Release all storage held in this file. */
692 clientmap_entry_t
**ent
, **next
, *this;
693 for (ent
= HT_START(clientmap
, &client_history
); ent
!= NULL
; ent
= next
) {
695 next
= HT_NEXT_RMV(clientmap
, &client_history
, ent
);
698 HT_CLEAR(clientmap
, &client_history
);