r16137@tombo: nickm | 2008-06-10 15:10:55 -0400
[tor.git] / src / or / geoip.c
blob39d31751aa6fe8407d9f667b743cbe0b49766451
1 /* Copyright (c) 2007-2008, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
3 /* $Id: /tor/trunk/src/or/networkstatus.c 15493 2007-12-16T18:33:25.055570Z nickm $ */
4 const char geoip_c_id[] =
5 "$Id: /tor/trunk/src/or/networkstatus.c 15493 2007-12-16T18:33:25.055570Z nickm $";
7 /**
8 * \file geoip.c
9 * \brief Functions related to maintaining an IP-to-country database and to
10 * summarizing client connections by country.
13 #define GEOIP_PRIVATE
14 #include "or.h"
15 #include "ht.h"
17 static void clear_geoip_db(void);
19 /** An entry from the GeoIP file: maps an IP range to a country. */
20 typedef struct geoip_entry_t {
21 uint32_t ip_low; /**< The lowest IP in the range, in host order */
22 uint32_t ip_high; /**< The highest IP in the range, in host order */
23 intptr_t country; /**< An index into geoip_countries */
24 } geoip_entry_t;
26 /** DOCDOC */
27 #define REQUEST_HIST_LEN 3
28 #define REQUEST_HIST_PERIOD (8*60*60)
30 typedef struct geoip_country_t {
31 char countrycode[3];
32 uint32_t n_v2_ns_requests[REQUEST_HIST_LEN];
33 uint32_t n_v3_ns_requests[REQUEST_HIST_LEN];
34 } geoip_country_t;
36 /** A list of geoip_country_t */
37 static smartlist_t *geoip_countries = NULL;
38 /** A map from lowercased country codes to their position in geoip_countries.
39 * The index is encoded in the pointer, and 1 is added so that NULL can mean
40 * not found. */
41 static strmap_t *country_idxplus1_by_lc_code = NULL;
42 /** A list of all known geoip_entry_t, sorted by ip_low. */
43 static smartlist_t *geoip_entries = NULL;
45 /** Add an entry to the GeoIP table, mapping all IPs between <b>low</b> and
46 * <b>high</b>, inclusive, to the 2-letter country code <b>country</b>.
48 static void
49 geoip_add_entry(uint32_t low, uint32_t high, const char *country)
51 intptr_t idx;
52 geoip_entry_t *ent;
53 void *_idxplus1;
55 if (high < low)
56 return;
58 _idxplus1 = strmap_get_lc(country_idxplus1_by_lc_code, country);
60 if (!_idxplus1) {
61 geoip_country_t *c = tor_malloc_zero(sizeof(geoip_country_t));
62 strlcpy(c->countrycode, country, sizeof(c->countrycode));
63 tor_strlower(c->countrycode);
64 smartlist_add(geoip_countries, c);
65 idx = smartlist_len(geoip_countries) - 1;
66 strmap_set_lc(country_idxplus1_by_lc_code, country, (void*)(idx+1));
67 } else {
68 idx = ((uintptr_t)_idxplus1)-1;
71 geoip_country_t *c = smartlist_get(geoip_countries, idx);
72 tor_assert(!strcasecmp(c->countrycode, country));
74 ent = tor_malloc_zero(sizeof(geoip_entry_t));
75 ent->ip_low = low;
76 ent->ip_high = high;
77 ent->country = idx;
78 smartlist_add(geoip_entries, ent);
81 /** Add an entry to the GeoIP table, parsing it from <b>line</b>. The
82 * format is as for geoip_load_file(). */
83 /*private*/ int
84 geoip_parse_entry(const char *line)
86 unsigned int low, high;
87 char b[3];
88 if (!geoip_countries) {
89 geoip_countries = smartlist_create();
90 geoip_entries = smartlist_create();
91 country_idxplus1_by_lc_code = strmap_new();
93 while (TOR_ISSPACE(*line))
94 ++line;
95 if (*line == '#')
96 return 0;
97 if (sscanf(line,"%u,%u,%2s", &low, &high, b) == 3) {
98 geoip_add_entry(low, high, b);
99 return 0;
100 } else if (sscanf(line,"\"%u\",\"%u\",\"%2s\",", &low, &high, b) == 3) {
101 geoip_add_entry(low, high, b);
102 return 0;
103 } else {
104 log_warn(LD_GENERAL, "Unable to parse line from GEOIP file: %s",
105 escaped(line));
106 return -1;
110 /** Sorting helper: return -1, 1, or 0 based on comparison of two
111 * geoip_entry_t */
112 static int
113 _geoip_compare_entries(const void **_a, const void **_b)
115 const geoip_entry_t *a = *_a, *b = *_b;
116 if (a->ip_low < b->ip_low)
117 return -1;
118 else if (a->ip_low > b->ip_low)
119 return 1;
120 else
121 return 0;
124 /** bsearch helper: return -1, 1, or 0 based on comparison of an IP (a pointer
125 * to a uint32_t in host order) to a geoip_entry_t */
126 static int
127 _geoip_compare_key_to_entry(const void *_key, const void **_member)
129 const uint32_t addr = *(uint32_t *)_key;
130 const geoip_entry_t *entry = *_member;
131 if (addr < entry->ip_low)
132 return -1;
133 else if (addr > entry->ip_high)
134 return 1;
135 else
136 return 0;
139 /** Return 1 if we should collect geoip stats on bridge users, and
140 * include them in our extrainfo descriptor. Else return 0. */
142 should_record_bridge_info(or_options_t *options)
144 return options->BridgeRelay && options->BridgeRecordUsageByCountry;
147 /** Clear the GeoIP database and reload it from the file
148 * <b>filename</b>. Return 0 on success, -1 on failure.
150 * Recognized line formats are:
151 * INTIPLOW,INTIPHIGH,CC
152 * and
153 * "INTIPLOW","INTIPHIGH","CC","CC3","COUNTRY NAME"
154 * where INTIPLOW and INTIPHIGH are IPv4 addresses encoded as 4-byte unsigned
155 * integers, and CC is a country code.
157 * It also recognizes, and skips over, blank lines and lines that start
158 * with '#' (comments).
161 geoip_load_file(const char *filename, or_options_t *options)
163 FILE *f;
164 int severity = should_record_bridge_info(options) ? LOG_WARN : LOG_INFO;
165 clear_geoip_db();
166 if (!(f = fopen(filename, "r"))) {
167 log_fn(severity, LD_GENERAL, "Failed to open GEOIP file %s.", filename);
168 return -1;
170 geoip_countries = smartlist_create();
171 geoip_entries = smartlist_create();
172 country_idxplus1_by_lc_code = strmap_new();
173 log_info(LD_GENERAL, "Parsing GEOIP file.");
174 while (!feof(f)) {
175 char buf[512];
176 if (fgets(buf, (int)sizeof(buf), f) == NULL)
177 break;
178 /* FFFF track full country name. */
179 geoip_parse_entry(buf);
181 /*XXXX020 abort and return -1 if no entries/illformed?*/
182 fclose(f);
184 smartlist_sort(geoip_entries, _geoip_compare_entries);
185 return 0;
188 /** Given an IP address in host order, return a number representing the
189 * country to which that address belongs, or -1 for unknown. The return value
190 * will always be less than geoip_get_n_countries(). To decode it,
191 * call geoip_get_country_name().
194 geoip_get_country_by_ip(uint32_t ipaddr)
196 geoip_entry_t *ent;
197 if (!geoip_entries)
198 return -1;
199 ent = smartlist_bsearch(geoip_entries, &ipaddr, _geoip_compare_key_to_entry);
200 return ent ? (int)ent->country : -1;
203 /** Return the number of countries recognized by the GeoIP database. */
205 geoip_get_n_countries(void)
207 return (int) smartlist_len(geoip_countries);
210 /** Return the two-letter country code associated with the number <b>num</b>,
211 * or "??" for an unknown value. */
212 const char *
213 geoip_get_country_name(int num)
215 if (geoip_countries && num >= 0 && num < smartlist_len(geoip_countries)) {
216 geoip_country_t *c = smartlist_get(geoip_countries, num);
217 return c->countrycode;
218 } else
219 return "??";
222 /** Return true iff we have loaded a GeoIP database.*/
224 geoip_is_loaded(void)
226 return geoip_countries != NULL && geoip_entries != NULL;
229 /** Entry in a map from IP address to the last time we've seen an incoming
230 * connection from that IP address. Used by bridges only, to track which
231 * countries have them blocked. */
232 typedef struct clientmap_entry_t {
233 HT_ENTRY(clientmap_entry_t) node;
234 uint32_t ipaddr;
235 time_t last_seen; /* The last 2 bits of this value hold the client
236 * operation. */
237 } clientmap_entry_t;
239 #define ACTION_MASK 3
241 /** Map from client IP address to last time seen. */
242 static HT_HEAD(clientmap, clientmap_entry_t) client_history =
243 HT_INITIALIZER();
244 /** Time at which we started tracking client IP history. */
245 static time_t client_history_starts = 0;
247 /** DOCDOC */
248 static time_t current_request_period_starts = 0;
249 static int n_old_request_periods = 0;
251 /** Hashtable helper: compute a hash of a clientmap_entry_t. */
252 static INLINE unsigned
253 clientmap_entry_hash(const clientmap_entry_t *a)
255 return ht_improve_hash((unsigned) a->ipaddr);
257 /** Hashtable helper: compare two clientmap_entry_t values for equality. */
258 static INLINE int
259 clientmap_entries_eq(const clientmap_entry_t *a, const clientmap_entry_t *b)
261 return a->ipaddr == b->ipaddr;
264 HT_PROTOTYPE(clientmap, clientmap_entry_t, node, clientmap_entry_hash,
265 clientmap_entries_eq);
266 HT_GENERATE(clientmap, clientmap_entry_t, node, clientmap_entry_hash,
267 clientmap_entries_eq, 0.6, malloc, realloc, free);
269 /** Note that we've seen a client connect from the IP <b>addr</b> (host order)
270 * at time <b>now</b>. Ignored by all but bridges. */
271 void
272 geoip_note_client_seen(geoip_client_action_t action,
273 uint32_t addr, time_t now)
275 or_options_t *options = get_options();
276 clientmap_entry_t lookup, *ent;
277 if (action == GEOIP_CLIENT_CONNECT) {
278 if (!(options->BridgeRelay && options->BridgeRecordUsageByCountry))
279 return;
280 } else {
281 #ifndef ENABLE_GEOIP_STATS
282 return;
283 #else
284 if (options->BridgeRelay || options->BridgeAuthoritativeDir ||
285 !options->DirRecordUsageByCountry)
286 return;
287 #endif
290 /* DOCDOC */
291 while (current_request_period_starts + REQUEST_HIST_PERIOD < now) {
292 if (!geoip_countries)
293 geoip_countries = smartlist_create();
294 SMARTLIST_FOREACH(geoip_countries, geoip_country_t *, c, {
295 memmove(&c->n_v2_ns_requests[0], &c->n_v2_ns_requests[1],
296 sizeof(uint32_t)*(REQUEST_HIST_LEN-1));
297 memmove(&c->n_v3_ns_requests[0], &c->n_v3_ns_requests[1],
298 sizeof(uint32_t)*(REQUEST_HIST_LEN-1));
299 c->n_v2_ns_requests[REQUEST_HIST_LEN-1] = 0;
300 c->n_v3_ns_requests[REQUEST_HIST_LEN-1] = 0;
302 current_request_period_starts += REQUEST_HIST_PERIOD;
303 if (n_old_request_periods < REQUEST_HIST_PERIOD-1)
304 ++n_old_request_periods;
307 /* We use the low 3 bits of the time to encode the action. Since we're
308 * potentially remembering tons of clients, we don't want to make
309 * clientmap_entry_t larger than it has to be. */
310 now = (now & ~ACTION_MASK) | (((int)action) & ACTION_MASK);
311 lookup.ipaddr = addr;
312 ent = HT_FIND(clientmap, &client_history, &lookup);
313 if (ent) {
314 ent->last_seen = now;
315 } else {
316 ent = tor_malloc_zero(sizeof(clientmap_entry_t));
317 ent->ipaddr = addr;
318 ent->last_seen = now;
319 HT_INSERT(clientmap, &client_history, ent);
322 if (action == GEOIP_CLIENT_NETWORKSTATUS ||
323 action == GEOIP_CLIENT_NETWORKSTATUS_V2) {
324 int country_idx = geoip_get_country_by_ip(addr);
325 if (country_idx >= 0 && country_idx < smartlist_len(geoip_countries)) {
326 geoip_country_t *country = smartlist_get(geoip_countries, country_idx);
327 if (action == GEOIP_CLIENT_NETWORKSTATUS)
328 ++country->n_v3_ns_requests[REQUEST_HIST_LEN-1];
329 else
330 ++country->n_v2_ns_requests[REQUEST_HIST_LEN-1];
334 if (!client_history_starts) {
335 client_history_starts = now;
336 current_request_period_starts = now;
340 /** HT_FOREACH helper: remove a clientmap_entry_t from the hashtable if it's
341 * older than a certain time. */
342 static int
343 _remove_old_client_helper(struct clientmap_entry_t *ent, void *_cutoff)
345 time_t cutoff = *(time_t*)_cutoff;
346 if (ent->last_seen < cutoff) {
347 tor_free(ent);
348 return 1;
349 } else {
350 return 0;
354 /** Forget about all clients that haven't connected since <b>cutoff</b>. */
355 void
356 geoip_remove_old_clients(time_t cutoff)
358 clientmap_HT_FOREACH_FN(&client_history,
359 _remove_old_client_helper,
360 &cutoff);
361 if (client_history_starts < cutoff)
362 client_history_starts = cutoff;
365 /** Do not mention any country from which fewer than this number of IPs have
366 * connected. This conceivably avoids reporting information that could
367 * deanonymize users, though analysis is lacking. */
368 #define MIN_IPS_TO_NOTE_COUNTRY 0
369 /** Do not report any geoip data at all if we have fewer than this number of
370 * IPs to report about. */
371 #define MIN_IPS_TO_NOTE_ANYTHING 0
372 /** When reporting geoip data about countries, round up to the nearest
373 * multiple of this value. */
374 #define IP_GRANULARITY 8
376 /** Return the time at which we started recording geoip data. */
377 time_t
378 geoip_get_history_start(void)
380 return client_history_starts;
383 /** Helper type: used to sort per-country totals by value. */
384 typedef struct c_hist_t {
385 char country[3]; /**< Two-letter country code. */
386 unsigned total; /**< Total IP addresses seen in this country. */
387 } c_hist_t;
389 /** Sorting helper: return -1, 1, or 0 based on comparison of two
390 * geoip_entry_t. Sort in descending order of total, and then by country
391 * code. */
392 static int
393 _c_hist_compare(const void **_a, const void **_b)
395 const c_hist_t *a = *_a, *b = *_b;
396 if (a->total > b->total)
397 return -1;
398 else if (a->total < b->total)
399 return 1;
400 else
401 return strcmp(a->country, b->country);
404 /*DOCDOC*/
405 #define GEOIP_MIN_OBSERVATION_TIME (12*60*60)
407 /** Return a newly allocated comma-separated string containing entries for all
408 * the countries from which we've seen enough clients connect. The entry
409 * format is cc=num where num is the number of IPs we've seen connecting from
410 * that country, and cc is a lowercased country code. Returns NULL if we don't
411 * want to export geoip data yet. */
412 char *
413 geoip_get_client_history(time_t now, geoip_client_action_t action)
415 char *result = NULL;
416 if (!geoip_is_loaded())
417 return NULL;
418 if (client_history_starts < (now - GEOIP_MIN_OBSERVATION_TIME)) {
419 char buf[32];
420 smartlist_t *chunks = NULL;
421 smartlist_t *entries = NULL;
422 int n_countries = geoip_get_n_countries();
423 int i;
424 clientmap_entry_t **ent;
425 unsigned *counts = tor_malloc_zero(sizeof(unsigned)*n_countries);
426 unsigned total = 0;
427 HT_FOREACH(ent, clientmap, &client_history) {
428 int country;
429 if (((*ent)->last_seen & ACTION_MASK) != action)
430 continue;
431 country = geoip_get_country_by_ip((*ent)->ipaddr);
432 if (country < 0)
433 continue;
434 tor_assert(0 <= country && country < n_countries);
435 ++counts[country];
436 ++total;
438 /* Don't record anything if we haven't seen enough IPs. */
439 #if (MIN_IPS_TO_NOTE_ANYTHING > 0)
440 if (total < MIN_IPS_TO_NOTE_ANYTHING)
441 goto done;
442 #endif
443 /* Make a list of c_hist_t */
444 entries = smartlist_create();
445 for (i = 0; i < n_countries; ++i) {
446 unsigned c = counts[i];
447 const char *countrycode;
448 c_hist_t *ent;
449 /* Only report a country if it has a minimum number of IPs. */
450 #if (MIN_IPS_TO_NOTE_COUNTRY > 0)
451 if (c >= MIN_IPS_TO_NOTE_COUNTRY) {
452 #else
453 if (c > 0) {
454 #endif
455 /* Round up to the next multiple of IP_GRANULARITY */
456 c += IP_GRANULARITY-1;
457 c -= c % IP_GRANULARITY;
458 countrycode = geoip_get_country_name(i);
459 ent = tor_malloc(sizeof(c_hist_t));
460 strlcpy(ent->country, countrycode, sizeof(ent->country));
461 ent->total = c;
462 smartlist_add(entries, ent);
465 /* Sort entries. Note that we must do this _AFTER_ rounding, or else
466 * the sort order could leak info. */
467 smartlist_sort(entries, _c_hist_compare);
469 /* Build the result. */
470 chunks = smartlist_create();
471 SMARTLIST_FOREACH(entries, c_hist_t *, ch, {
472 tor_snprintf(buf, sizeof(buf), "%s=%u", ch->country, ch->total);
473 smartlist_add(chunks, tor_strdup(buf));
475 result = smartlist_join_strings(chunks, ",", 0, NULL);
476 #if (MIN_IPS_TO_NOTE_ANYTHING > 0)
477 done:
478 #endif
479 tor_free(counts);
480 if (chunks) {
481 SMARTLIST_FOREACH(chunks, char *, c, tor_free(c));
482 smartlist_free(chunks);
484 if (entries) {
485 SMARTLIST_FOREACH(entries, c_hist_t *, c, tor_free(c));
486 smartlist_free(entries);
489 return result;
492 /**DOCDOC*/
493 char *
494 geoip_get_request_history(time_t now, geoip_client_action_t action)
496 smartlist_t *entries;
497 char *result;
498 if (client_history_starts >= (now - GEOIP_MIN_OBSERVATION_TIME))
499 return NULL;
500 if (action != GEOIP_CLIENT_NETWORKSTATUS &&
501 action != GEOIP_CLIENT_NETWORKSTATUS_V2)
502 return NULL;
503 if (!geoip_countries)
504 return NULL;
505 entries = smartlist_create();
506 SMARTLIST_FOREACH(geoip_countries, geoip_country_t *, c, {
507 uint32_t *n = (action == GEOIP_CLIENT_NETWORKSTATUS)
508 ? c->n_v3_ns_requests : c->n_v2_ns_requests;
509 uint32_t tot = 0;
510 int i;
511 char buf[32];
512 for (i=0; i < REQUEST_HIST_LEN; ++i)
513 tot += n[i];
514 tor_snprintf(buf, sizeof(buf), "%s=%ld", c->countrycode, (long)tot);
515 smartlist_add(entries, tor_strdup(buf));
517 smartlist_sort_strings(entries);
518 result = smartlist_join_strings(entries, ",", 0, NULL);
519 SMARTLIST_FOREACH(entries, char *, cp, tor_free(cp));
520 return result;
523 void
524 dump_geoip_stats(void)
526 #ifdef ENABLE_GEOIP_STATS
527 time_t now = time(NULL);
528 time_t request_start;
529 char *filename = get_datadir_fname("geoip-stats");
530 char *data_v2 = NULL, *data_v3 = NULL;
531 char since[ISO_TIME_LEN+1], written[ISO_TIME_LEN+1];
532 open_file_t *open_file = NULL;
533 double v2_share = 0.0, v3_share = 0.0;
534 FILE *out;
536 data_v2 = geoip_get_client_history(now, GEOIP_CLIENT_NETWORKSTATUS_V2);
537 data_v3 = geoip_get_client_history(now, GEOIP_CLIENT_NETWORKSTATUS);
538 format_iso_time(since, geoip_get_history_start());
539 format_iso_time(written, now);
540 out = start_writing_to_stdio_file(filename, OPEN_FLAGS_REPLACE,
541 0600, &open_file);
542 if (!out)
543 goto done;
544 if (fprintf(out, "written %s\nstarted-at %s\nns-ips %s\nns-v2-ips%s\n",
545 written, since,
546 data_v3 ? data_v3 : "", data_v2 ? data_v2 : "") < 0)
547 goto done;
548 tor_free(data_v2);
549 tor_free(data_v3);
551 request_start = current_request_period_starts -
552 (n_old_request_periods * REQUEST_HIST_PERIOD);
553 format_iso_time(since, request_start);
554 data_v2 = geoip_get_request_history(now, GEOIP_CLIENT_NETWORKSTATUS_V2);
555 data_v3 = geoip_get_request_history(now, GEOIP_CLIENT_NETWORKSTATUS);
556 if (fprintf(out, "requests-start %s\nn-ns-reqs %s\nn-v2-ns_reqs%s\n",
557 since,
558 data_v3 ? data_v3 : "", data_v2 ? data_v2 : "") < 0)
559 goto done;
560 if (!router_get_my_share_of_directory_requests(&v2_share, &v3_share)) {
561 if (fprintf(out, "v2-ns-share %0.2lf%%\n", v2_share*100) < 0)
562 goto done;
563 if (fprintf(out, "v3-ns-share %0.2lf%%\n", v3_share*100) < 0)
564 goto done;
567 finish_writing_to_file(open_file);
568 open_file = NULL;
569 done:
570 if (open_file)
571 abort_writing_to_file(open_file);
572 tor_free(filename);
573 tor_free(data_v2);
574 tor_free(data_v3);
575 #endif
578 /** Helper used to implement GETINFO ip-to-country/... controller command. */
580 getinfo_helper_geoip(control_connection_t *control_conn,
581 const char *question, char **answer)
583 (void)control_conn;
584 if (geoip_is_loaded() && !strcmpstart(question, "ip-to-country/")) {
585 int c;
586 uint32_t ip;
587 struct in_addr in;
588 question += strlen("ip-to-country/");
589 if (tor_inet_aton(question, &in) != 0) {
590 ip = ntohl(in.s_addr);
591 c = geoip_get_country_by_ip(ip);
592 *answer = tor_strdup(geoip_get_country_name(c));
595 return 0;
598 /** Release all storage held by the GeoIP database. */
599 static void
600 clear_geoip_db(void)
602 if (geoip_countries) {
603 SMARTLIST_FOREACH(geoip_countries, geoip_country_t *, c, tor_free(c));
604 smartlist_free(geoip_countries);
606 if (country_idxplus1_by_lc_code)
607 strmap_free(country_idxplus1_by_lc_code, NULL);
608 if (geoip_entries) {
609 SMARTLIST_FOREACH(geoip_entries, geoip_entry_t *, ent, tor_free(ent));
610 smartlist_free(geoip_entries);
612 geoip_countries = NULL;
613 country_idxplus1_by_lc_code = NULL;
614 geoip_entries = NULL;
617 /** Release all storage held in this file. */
618 void
619 geoip_free_all(void)
621 clientmap_entry_t **ent, **next, *this;
622 for (ent = HT_START(clientmap, &client_history); ent != NULL; ent = next) {
623 this = *ent;
624 next = HT_NEXT_RMV(clientmap, &client_history, ent);
625 tor_free(this);
627 HT_CLEAR(clientmap, &client_history);
629 clear_geoip_db();