Back to index

tor  0.2.3.19-rc
routerlist.c
Go to the documentation of this file.
00001 /* Copyright (c) 2001 Matej Pfajfar.
00002  * Copyright (c) 2001-2004, Roger Dingledine.
00003  * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
00004  * Copyright (c) 2007-2012, The Tor Project, Inc. */
00005 /* See LICENSE for licensing information */
00006 
00014 #include "or.h"
00015 #include "circuitbuild.h"
00016 #include "config.h"
00017 #include "connection.h"
00018 #include "control.h"
00019 #include "directory.h"
00020 #include "dirserv.h"
00021 #include "dirvote.h"
00022 #include "geoip.h"
00023 #include "hibernate.h"
00024 #include "main.h"
00025 #include "microdesc.h"
00026 #include "networkstatus.h"
00027 #include "nodelist.h"
00028 #include "policies.h"
00029 #include "reasons.h"
00030 #include "rendcommon.h"
00031 #include "rendservice.h"
00032 #include "rephist.h"
00033 #include "router.h"
00034 #include "routerlist.h"
00035 #include "routerparse.h"
00036 
00037 // #define DEBUG_ROUTERLIST
00038 
00039 /****************************************************************************/
00040 
00041 /* static function prototypes */
00042 static const routerstatus_t *router_pick_directory_server_impl(
00043                                            dirinfo_type_t auth, int flags);
00044 static const routerstatus_t *router_pick_trusteddirserver_impl(
00045                           dirinfo_type_t auth, int flags, int *n_busy_out);
00046 static void mark_all_trusteddirservers_up(void);
00047 static int router_nickname_matches(const routerinfo_t *router,
00048                                    const char *nickname);
00049 static int node_nickname_matches(const node_t *router,
00050                                  const char *nickname);
00051 static void trusted_dir_server_free(trusted_dir_server_t *ds);
00052 static int signed_desc_digest_is_recognized(signed_descriptor_t *desc);
00053 static void update_router_have_minimum_dir_info(void);
00054 static const char *signed_descriptor_get_body_impl(
00055                                               const signed_descriptor_t *desc,
00056                                               int with_annotations);
00057 static void list_pending_downloads(digestmap_t *result,
00058                                    int purpose, const char *prefix);
00059 static void launch_dummy_descriptor_download_as_needed(time_t now,
00060                                    const or_options_t *options);
00061 
00062 DECLARE_TYPED_DIGESTMAP_FNS(sdmap_, digest_sd_map_t, signed_descriptor_t)
00063 DECLARE_TYPED_DIGESTMAP_FNS(rimap_, digest_ri_map_t, routerinfo_t)
00064 DECLARE_TYPED_DIGESTMAP_FNS(eimap_, digest_ei_map_t, extrainfo_t)
00065 #define SDMAP_FOREACH(map, keyvar, valvar)                              \
00066   DIGESTMAP_FOREACH(sdmap_to_digestmap(map), keyvar, signed_descriptor_t *, \
00067                     valvar)
00068 #define RIMAP_FOREACH(map, keyvar, valvar) \
00069   DIGESTMAP_FOREACH(rimap_to_digestmap(map), keyvar, routerinfo_t *, valvar)
00070 #define EIMAP_FOREACH(map, keyvar, valvar) \
00071   DIGESTMAP_FOREACH(eimap_to_digestmap(map), keyvar, extrainfo_t *, valvar)
00072 
00073 /****************************************************************************/
00074 
00077 static smartlist_t *trusted_dir_servers = NULL;
00078 
00081 typedef struct cert_list_t {
00082   download_status_t dl_status;
00083   smartlist_t *certs;
00084 } cert_list_t;
00086 static digestmap_t *trusted_dir_certs = NULL;
00090 static int trusted_dir_servers_certs_changed = 0;
00091 
00093 static routerlist_t *routerlist = NULL;
00094 
00097 static smartlist_t *warned_nicknames = NULL;
00098 
00102 static time_t last_descriptor_download_attempted = 0;
00103 
00110 static uint64_t sl_last_total_weighted_bw = 0,
00111   sl_last_weighted_bw_of_me = 0;
00116 int
00117 get_n_authorities(dirinfo_type_t type)
00118 {
00119   int n = 0;
00120   if (!trusted_dir_servers)
00121     return 0;
00122   SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
00123                     if (ds->type & type)
00124                       ++n);
00125   return n;
00126 }
00127 
00128 #define get_n_v2_authorities() get_n_authorities(V2_DIRINFO)
00129 
00132 static cert_list_t *
00133 get_cert_list(const char *id_digest)
00134 {
00135   cert_list_t *cl;
00136   if (!trusted_dir_certs)
00137     trusted_dir_certs = digestmap_new();
00138   cl = digestmap_get(trusted_dir_certs, id_digest);
00139   if (!cl) {
00140     cl = tor_malloc_zero(sizeof(cert_list_t));
00141     cl->dl_status.schedule = DL_SCHED_CONSENSUS;
00142     cl->certs = smartlist_new();
00143     digestmap_set(trusted_dir_certs, id_digest, cl);
00144   }
00145   return cl;
00146 }
00147 
00150 int
00151 trusted_dirs_reload_certs(void)
00152 {
00153   char *filename;
00154   char *contents;
00155   int r;
00156 
00157   filename = get_datadir_fname("cached-certs");
00158   contents = read_file_to_str(filename, RFTS_IGNORE_MISSING, NULL);
00159   tor_free(filename);
00160   if (!contents)
00161     return 0;
00162   r = trusted_dirs_load_certs_from_string(contents, 1, 1);
00163   tor_free(contents);
00164   return r;
00165 }
00166 
00169 static INLINE int
00170 already_have_cert(authority_cert_t *cert)
00171 {
00172   cert_list_t *cl = get_cert_list(cert->cache_info.identity_digest);
00173 
00174   SMARTLIST_FOREACH(cl->certs, authority_cert_t *, c,
00175   {
00176     if (tor_memeq(c->cache_info.signed_descriptor_digest,
00177                 cert->cache_info.signed_descriptor_digest,
00178                 DIGEST_LEN))
00179       return 1;
00180   });
00181   return 0;
00182 }
00183 
00189 int
00190 trusted_dirs_load_certs_from_string(const char *contents, int from_store,
00191                                     int flush)
00192 {
00193   trusted_dir_server_t *ds;
00194   const char *s, *eos;
00195   int failure_code = 0;
00196 
00197   for (s = contents; *s; s = eos) {
00198     authority_cert_t *cert = authority_cert_parse_from_string(s, &eos);
00199     cert_list_t *cl;
00200     if (!cert) {
00201       failure_code = -1;
00202       break;
00203     }
00204     ds = trusteddirserver_get_by_v3_auth_digest(
00205                                        cert->cache_info.identity_digest);
00206     log_debug(LD_DIR, "Parsed certificate for %s",
00207               ds ? ds->nickname : "unknown authority");
00208 
00209     if (already_have_cert(cert)) {
00210       /* we already have this one. continue. */
00211       log_info(LD_DIR, "Skipping %s certificate for %s that we "
00212                "already have.",
00213                from_store ? "cached" : "downloaded",
00214                ds ? ds->nickname : "an old or new authority");
00215 
00216       /* a duplicate on a download should be treated as a failure, since it
00217        * probably means we wanted a different secret key or we are trying to
00218        * replace an expired cert that has not in fact been updated. */
00219       if (!from_store) {
00220         if (authdir_mode(get_options())) {
00221           log_warn(LD_DIR,
00222                    "Got a certificate for %s, but we already have it. "
00223                    "Maybe they haven't updated it. Waiting for a while.",
00224                    ds ? ds->nickname : "an old or new authority");
00225         } else {
00226           log_info(LD_DIR,
00227                    "Got a certificate for %s, but we already have it. "
00228                    "Maybe they haven't updated it. Waiting for a while.",
00229                    ds ? ds->nickname : "an old or new authority");
00230         }
00231 
00232         authority_cert_dl_failed(cert->cache_info.identity_digest, 404);
00233       }
00234 
00235       authority_cert_free(cert);
00236       continue;
00237     }
00238 
00239     if (ds) {
00240       log_info(LD_DIR, "Adding %s certificate for directory authority %s with "
00241                "signing key %s", from_store ? "cached" : "downloaded",
00242                ds->nickname, hex_str(cert->signing_key_digest,DIGEST_LEN));
00243     } else {
00244       int adding = directory_caches_unknown_auth_certs(get_options());
00245       log_info(LD_DIR, "%s %s certificate for unrecognized directory "
00246                "authority with signing key %s",
00247                adding ? "Adding" : "Not adding",
00248                from_store ? "cached" : "downloaded",
00249                hex_str(cert->signing_key_digest,DIGEST_LEN));
00250       if (!adding) {
00251         authority_cert_free(cert);
00252         continue;
00253       }
00254     }
00255 
00256     cl = get_cert_list(cert->cache_info.identity_digest);
00257     smartlist_add(cl->certs, cert);
00258     if (ds && cert->cache_info.published_on > ds->addr_current_at) {
00259       /* Check to see whether we should update our view of the authority's
00260        * address. */
00261       if (cert->addr && cert->dir_port &&
00262           (ds->addr != cert->addr ||
00263            ds->dir_port != cert->dir_port)) {
00264         char *a = tor_dup_ip(cert->addr);
00265         log_notice(LD_DIR, "Updating address for directory authority %s "
00266                    "from %s:%d to %s:%d based on certificate.",
00267                    ds->nickname, ds->address, (int)ds->dir_port,
00268                    a, cert->dir_port);
00269         tor_free(a);
00270         ds->addr = cert->addr;
00271         ds->dir_port = cert->dir_port;
00272       }
00273       ds->addr_current_at = cert->cache_info.published_on;
00274     }
00275 
00276     if (!from_store)
00277       trusted_dir_servers_certs_changed = 1;
00278   }
00279 
00280   if (flush)
00281     trusted_dirs_flush_certs_to_disk();
00282 
00283   /* call this even if failure_code is <0, since some certs might have
00284    * succeeded. */
00285   networkstatus_note_certs_arrived();
00286 
00287   return failure_code;
00288 }
00289 
00291 void
00292 trusted_dirs_flush_certs_to_disk(void)
00293 {
00294   char *filename;
00295   smartlist_t *chunks;
00296 
00297   if (!trusted_dir_servers_certs_changed || !trusted_dir_certs)
00298     return;
00299 
00300   chunks = smartlist_new();
00301   DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
00302     SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
00303           {
00304             sized_chunk_t *c = tor_malloc(sizeof(sized_chunk_t));
00305             c->bytes = cert->cache_info.signed_descriptor_body;
00306             c->len = cert->cache_info.signed_descriptor_len;
00307             smartlist_add(chunks, c);
00308           });
00309   } DIGESTMAP_FOREACH_END;
00310 
00311   filename = get_datadir_fname("cached-certs");
00312   if (write_chunks_to_file(filename, chunks, 0)) {
00313     log_warn(LD_FS, "Error writing certificates to disk.");
00314   }
00315   tor_free(filename);
00316   SMARTLIST_FOREACH(chunks, sized_chunk_t *, c, tor_free(c));
00317   smartlist_free(chunks);
00318 
00319   trusted_dir_servers_certs_changed = 0;
00320 }
00321 
00326 static void
00327 trusted_dirs_remove_old_certs(void)
00328 {
00329   time_t now = time(NULL);
00330 #define DEAD_CERT_LIFETIME (2*24*60*60)
00331 #define OLD_CERT_LIFETIME (7*24*60*60)
00332 #define CERT_EXPIRY_SKEW (60*60)
00333   if (!trusted_dir_certs)
00334     return;
00335 
00336   DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
00337     authority_cert_t *newest = NULL;
00338     SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
00339           if (!newest || (cert->cache_info.published_on >
00340                           newest->cache_info.published_on))
00341             newest = cert);
00342     if (newest) {
00343       const time_t newest_published = newest->cache_info.published_on;
00344       SMARTLIST_FOREACH_BEGIN(cl->certs, authority_cert_t *, cert) {
00345         int expired;
00346         time_t cert_published;
00347         if (newest == cert)
00348           continue;
00349         expired = now > cert->expires;
00350         cert_published = cert->cache_info.published_on;
00351         /* Store expired certs for 48 hours after a newer arrives;
00352          */
00353         if (expired ?
00354             (newest_published + DEAD_CERT_LIFETIME < now) :
00355             (cert_published + OLD_CERT_LIFETIME < newest_published)) {
00356           SMARTLIST_DEL_CURRENT(cl->certs, cert);
00357           authority_cert_free(cert);
00358           trusted_dir_servers_certs_changed = 1;
00359         }
00360       } SMARTLIST_FOREACH_END(cert);
00361     }
00362   } DIGESTMAP_FOREACH_END;
00363 #undef OLD_CERT_LIFETIME
00364 
00365   trusted_dirs_flush_certs_to_disk();
00366 }
00367 
00371 authority_cert_t *
00372 authority_cert_get_newest_by_id(const char *id_digest)
00373 {
00374   cert_list_t *cl;
00375   authority_cert_t *best = NULL;
00376   if (!trusted_dir_certs ||
00377       !(cl = digestmap_get(trusted_dir_certs, id_digest)))
00378     return NULL;
00379 
00380   SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
00381   {
00382     if (!best || cert->cache_info.published_on > best->cache_info.published_on)
00383       best = cert;
00384   });
00385   return best;
00386 }
00387 
00391 authority_cert_t *
00392 authority_cert_get_by_sk_digest(const char *sk_digest)
00393 {
00394   authority_cert_t *c;
00395   if (!trusted_dir_certs)
00396     return NULL;
00397 
00398   if ((c = get_my_v3_authority_cert()) &&
00399       tor_memeq(c->signing_key_digest, sk_digest, DIGEST_LEN))
00400     return c;
00401   if ((c = get_my_v3_legacy_cert()) &&
00402       tor_memeq(c->signing_key_digest, sk_digest, DIGEST_LEN))
00403     return c;
00404 
00405   DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
00406     SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
00407     {
00408       if (tor_memeq(cert->signing_key_digest, sk_digest, DIGEST_LEN))
00409         return cert;
00410     });
00411   } DIGESTMAP_FOREACH_END;
00412   return NULL;
00413 }
00414 
00418 authority_cert_t *
00419 authority_cert_get_by_digests(const char *id_digest,
00420                               const char *sk_digest)
00421 {
00422   cert_list_t *cl;
00423   if (!trusted_dir_certs ||
00424       !(cl = digestmap_get(trusted_dir_certs, id_digest)))
00425     return NULL;
00426   SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
00427     if (tor_memeq(cert->signing_key_digest, sk_digest, DIGEST_LEN))
00428       return cert; );
00429 
00430   return NULL;
00431 }
00432 
00434 void
00435 authority_cert_get_all(smartlist_t *certs_out)
00436 {
00437   tor_assert(certs_out);
00438   if (!trusted_dir_certs)
00439     return;
00440 
00441   DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
00442     SMARTLIST_FOREACH(cl->certs, authority_cert_t *, c,
00443                       smartlist_add(certs_out, c));
00444   } DIGESTMAP_FOREACH_END;
00445 }
00446 
00450 void
00451 authority_cert_dl_failed(const char *id_digest, int status)
00452 {
00453   cert_list_t *cl;
00454   if (!trusted_dir_certs ||
00455       !(cl = digestmap_get(trusted_dir_certs, id_digest)))
00456     return;
00457 
00458   download_status_failed(&cl->dl_status, status);
00459 }
00460 
00464 int
00465 authority_cert_dl_looks_uncertain(const char *id_digest)
00466 {
00467 #define N_AUTH_CERT_DL_FAILURES_TO_BUG_USER 2
00468   cert_list_t *cl;
00469   int n_failures;
00470   if (!trusted_dir_certs ||
00471       !(cl = digestmap_get(trusted_dir_certs, id_digest)))
00472     return 0;
00473 
00474   n_failures = download_status_get_n_failures(&cl->dl_status);
00475   return n_failures >= N_AUTH_CERT_DL_FAILURES_TO_BUG_USER;
00476 }
00477 
00479 #define MAX_CERT_DL_FAILURES 8
00480 
00487 void
00488 authority_certs_fetch_missing(networkstatus_t *status, time_t now)
00489 {
00490   digestmap_t *pending;
00491   authority_cert_t *cert;
00492   smartlist_t *missing_digests;
00493   char *resource = NULL;
00494   cert_list_t *cl;
00495   const int cache = directory_caches_unknown_auth_certs(get_options());
00496 
00497   if (should_delay_dir_fetches(get_options()))
00498     return;
00499 
00500   pending = digestmap_new();
00501   missing_digests = smartlist_new();
00502 
00503   list_pending_downloads(pending, DIR_PURPOSE_FETCH_CERTIFICATE, "fp/");
00504   if (status) {
00505     SMARTLIST_FOREACH_BEGIN(status->voters, networkstatus_voter_info_t *,
00506                             voter) {
00507       if (!smartlist_len(voter->sigs))
00508         continue; /* This authority never signed this consensus, so don't
00509                    * go looking for a cert with key digest 0000000000. */
00510       if (!cache &&
00511           !trusteddirserver_get_by_v3_auth_digest(voter->identity_digest))
00512         continue; /* We are not a cache, and we don't know this authority.*/
00513       cl = get_cert_list(voter->identity_digest);
00514       SMARTLIST_FOREACH_BEGIN(voter->sigs, document_signature_t *, sig) {
00515         cert = authority_cert_get_by_digests(voter->identity_digest,
00516                                              sig->signing_key_digest);
00517         if (cert) {
00518           if (now < cert->expires)
00519             download_status_reset(&cl->dl_status);
00520           continue;
00521         }
00522         if (download_status_is_ready(&cl->dl_status, now,
00523                                      MAX_CERT_DL_FAILURES) &&
00524             !digestmap_get(pending, voter->identity_digest)) {
00525           log_info(LD_DIR, "We're missing a certificate from authority "
00526                    "with signing key %s: launching request.",
00527                    hex_str(sig->signing_key_digest, DIGEST_LEN));
00528           smartlist_add(missing_digests, sig->identity_digest);
00529         }
00530       } SMARTLIST_FOREACH_END(sig);
00531     } SMARTLIST_FOREACH_END(voter);
00532   }
00533   SMARTLIST_FOREACH_BEGIN(trusted_dir_servers, trusted_dir_server_t *, ds) {
00534     int found = 0;
00535     if (!(ds->type & V3_DIRINFO))
00536       continue;
00537     if (smartlist_digest_isin(missing_digests, ds->v3_identity_digest))
00538       continue;
00539     cl = get_cert_list(ds->v3_identity_digest);
00540     SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert, {
00541       if (now < cert->expires) {
00542         /* It's not expired, and we weren't looking for something to
00543          * verify a consensus with.  Call it done. */
00544         download_status_reset(&cl->dl_status);
00545         found = 1;
00546         break;
00547       }
00548     });
00549     if (!found &&
00550         download_status_is_ready(&cl->dl_status, now,MAX_CERT_DL_FAILURES) &&
00551         !digestmap_get(pending, ds->v3_identity_digest)) {
00552       log_info(LD_DIR, "No current certificate known for authority %s; "
00553                "launching request.", ds->nickname);
00554         smartlist_add(missing_digests, ds->v3_identity_digest);
00555     }
00556   } SMARTLIST_FOREACH_END(ds);
00557 
00558   if (!smartlist_len(missing_digests)) {
00559     goto done;
00560   } else {
00561     smartlist_t *fps = smartlist_new();
00562     smartlist_add(fps, tor_strdup("fp/"));
00563     SMARTLIST_FOREACH(missing_digests, const char *, d, {
00564         char *fp;
00565         if (digestmap_get(pending, d))
00566           continue;
00567         fp = tor_malloc(HEX_DIGEST_LEN+2);
00568         base16_encode(fp, HEX_DIGEST_LEN+1, d, DIGEST_LEN);
00569         fp[HEX_DIGEST_LEN] = '+';
00570         fp[HEX_DIGEST_LEN+1] = '\0';
00571         smartlist_add(fps, fp);
00572       });
00573     if (smartlist_len(fps) == 1) {
00574       /* we didn't add any: they were all pending */
00575       SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
00576       smartlist_free(fps);
00577       goto done;
00578     }
00579     resource = smartlist_join_strings(fps, "", 0, NULL);
00580     resource[strlen(resource)-1] = '\0';
00581     SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
00582     smartlist_free(fps);
00583   }
00584   directory_get_from_dirserver(DIR_PURPOSE_FETCH_CERTIFICATE, 0,
00585                                resource, PDS_RETRY_IF_NO_SERVERS);
00586 
00587  done:
00588   tor_free(resource);
00589   smartlist_free(missing_digests);
00590   digestmap_free(pending, NULL);
00591 }
00592 
00593 /* Router descriptor storage.
00594  *
00595  * Routerdescs are stored in a big file, named "cached-descriptors".  As new
00596  * routerdescs arrive, we append them to a journal file named
00597  * "cached-descriptors.new".
00598  *
00599  * From time to time, we replace "cached-descriptors" with a new file
00600  * containing only the live, non-superseded descriptors, and clear
00601  * cached-routers.new.
00602  *
00603  * On startup, we read both files.
00604  */
00605 
00608 static int
00609 router_should_rebuild_store(desc_store_t *store)
00610 {
00611   if (store->store_len > (1<<16))
00612     return (store->journal_len > store->store_len / 2 ||
00613             store->bytes_dropped > store->store_len / 2);
00614   else
00615     return store->journal_len > (1<<15);
00616 }
00617 
00620 static INLINE desc_store_t *
00621 desc_get_store(routerlist_t *rl, const signed_descriptor_t *sd)
00622 {
00623   if (sd->is_extrainfo)
00624     return &rl->extrainfo_store;
00625   else
00626     return &rl->desc_store;
00627 }
00628 
00632 static int
00633 signed_desc_append_to_journal(signed_descriptor_t *desc,
00634                               desc_store_t *store)
00635 {
00636   char *fname = get_datadir_fname_suffix(store->fname_base, ".new");
00637   const char *body = signed_descriptor_get_body_impl(desc,1);
00638   size_t len = desc->signed_descriptor_len + desc->annotations_len;
00639 
00640   if (append_bytes_to_file(fname, body, len, 1)) {
00641     log_warn(LD_FS, "Unable to store router descriptor");
00642     tor_free(fname);
00643     return -1;
00644   }
00645   desc->saved_location = SAVED_IN_JOURNAL;
00646   tor_free(fname);
00647 
00648   desc->saved_offset = store->journal_len;
00649   store->journal_len += len;
00650 
00651   return 0;
00652 }
00653 
00657 static int
00658 _compare_signed_descriptors_by_age(const void **_a, const void **_b)
00659 {
00660   const signed_descriptor_t *r1 = *_a, *r2 = *_b;
00661   return (int)(r1->published_on - r2->published_on);
00662 }
00663 
00664 #define RRS_FORCE 1
00665 #define RRS_DONT_REMOVE_OLD 2
00666 
00673 static int
00674 router_rebuild_store(int flags, desc_store_t *store)
00675 {
00676   smartlist_t *chunk_list = NULL;
00677   char *fname = NULL, *fname_tmp = NULL;
00678   int r = -1;
00679   off_t offset = 0;
00680   smartlist_t *signed_descriptors = NULL;
00681   int nocache=0;
00682   size_t total_expected_len = 0;
00683   int had_any;
00684   int force = flags & RRS_FORCE;
00685 
00686   if (!force && !router_should_rebuild_store(store)) {
00687     r = 0;
00688     goto done;
00689   }
00690   if (!routerlist) {
00691     r = 0;
00692     goto done;
00693   }
00694 
00695   if (store->type == EXTRAINFO_STORE)
00696     had_any = !eimap_isempty(routerlist->extra_info_map);
00697   else
00698     had_any = (smartlist_len(routerlist->routers)+
00699                smartlist_len(routerlist->old_routers))>0;
00700 
00701   /* Don't save deadweight. */
00702   if (!(flags & RRS_DONT_REMOVE_OLD))
00703     routerlist_remove_old_routers();
00704 
00705   log_info(LD_DIR, "Rebuilding %s cache", store->description);
00706 
00707   fname = get_datadir_fname(store->fname_base);
00708   fname_tmp = get_datadir_fname_suffix(store->fname_base, ".tmp");
00709 
00710   chunk_list = smartlist_new();
00711 
00712   /* We sort the routers by age to enhance locality on disk. */
00713   signed_descriptors = smartlist_new();
00714   if (store->type == EXTRAINFO_STORE) {
00715     eimap_iter_t *iter;
00716     for (iter = eimap_iter_init(routerlist->extra_info_map);
00717          !eimap_iter_done(iter);
00718          iter = eimap_iter_next(routerlist->extra_info_map, iter)) {
00719       const char *key;
00720       extrainfo_t *ei;
00721       eimap_iter_get(iter, &key, &ei);
00722       smartlist_add(signed_descriptors, &ei->cache_info);
00723     }
00724   } else {
00725     SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd,
00726                       smartlist_add(signed_descriptors, sd));
00727     SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, ri,
00728                       smartlist_add(signed_descriptors, &ri->cache_info));
00729   }
00730 
00731   smartlist_sort(signed_descriptors, _compare_signed_descriptors_by_age);
00732 
00733   /* Now, add the appropriate members to chunk_list */
00734   SMARTLIST_FOREACH(signed_descriptors, signed_descriptor_t *, sd,
00735     {
00736       sized_chunk_t *c;
00737       const char *body = signed_descriptor_get_body_impl(sd, 1);
00738       if (!body) {
00739         log_warn(LD_BUG, "No descriptor available for router.");
00740         goto done;
00741       }
00742       if (sd->do_not_cache) {
00743         ++nocache;
00744         continue;
00745       }
00746       c = tor_malloc(sizeof(sized_chunk_t));
00747       c->bytes = body;
00748       c->len = sd->signed_descriptor_len + sd->annotations_len;
00749       total_expected_len += c->len;
00750       smartlist_add(chunk_list, c);
00751     });
00752 
00753   if (write_chunks_to_file(fname_tmp, chunk_list, 1)<0) {
00754     log_warn(LD_FS, "Error writing router store to disk.");
00755     goto done;
00756   }
00757 
00758   /* Our mmap is now invalid. */
00759   if (store->mmap) {
00760     tor_munmap_file(store->mmap);
00761     store->mmap = NULL;
00762   }
00763 
00764   if (replace_file(fname_tmp, fname)<0) {
00765     log_warn(LD_FS, "Error replacing old router store: %s", strerror(errno));
00766     goto done;
00767   }
00768 
00769   errno = 0;
00770   store->mmap = tor_mmap_file(fname);
00771   if (! store->mmap) {
00772     if (errno == ERANGE) {
00773       /* empty store.*/
00774       if (total_expected_len) {
00775         log_warn(LD_FS, "We wrote some bytes to a new descriptor file at '%s',"
00776                  " but when we went to mmap it, it was empty!", fname);
00777       } else if (had_any) {
00778         log_info(LD_FS, "We just removed every descriptor in '%s'.  This is "
00779                  "okay if we're just starting up after a long time. "
00780                  "Otherwise, it's a bug.", fname);
00781       }
00782     } else {
00783       log_warn(LD_FS, "Unable to mmap new descriptor file at '%s'.",fname);
00784     }
00785   }
00786 
00787   log_info(LD_DIR, "Reconstructing pointers into cache");
00788 
00789   offset = 0;
00790   SMARTLIST_FOREACH(signed_descriptors, signed_descriptor_t *, sd,
00791     {
00792       if (sd->do_not_cache)
00793         continue;
00794       sd->saved_location = SAVED_IN_CACHE;
00795       if (store->mmap) {
00796         tor_free(sd->signed_descriptor_body); // sets it to null
00797         sd->saved_offset = offset;
00798       }
00799       offset += sd->signed_descriptor_len + sd->annotations_len;
00800       signed_descriptor_get_body(sd); /* reconstruct and assert */
00801     });
00802 
00803   tor_free(fname);
00804   fname = get_datadir_fname_suffix(store->fname_base, ".new");
00805   write_str_to_file(fname, "", 1);
00806 
00807   r = 0;
00808   store->store_len = (size_t) offset;
00809   store->journal_len = 0;
00810   store->bytes_dropped = 0;
00811  done:
00812   smartlist_free(signed_descriptors);
00813   tor_free(fname);
00814   tor_free(fname_tmp);
00815   if (chunk_list) {
00816     SMARTLIST_FOREACH(chunk_list, sized_chunk_t *, c, tor_free(c));
00817     smartlist_free(chunk_list);
00818   }
00819 
00820   return r;
00821 }
00822 
00826 static int
00827 router_reload_router_list_impl(desc_store_t *store)
00828 {
00829   char *fname = NULL, *altname = NULL, *contents = NULL;
00830   struct stat st;
00831   int read_from_old_location = 0;
00832   int extrainfo = (store->type == EXTRAINFO_STORE);
00833   time_t now = time(NULL);
00834   store->journal_len = store->store_len = 0;
00835 
00836   fname = get_datadir_fname(store->fname_base);
00837   if (store->fname_alt_base)
00838     altname = get_datadir_fname(store->fname_alt_base);
00839 
00840   if (store->mmap) /* get rid of it first */
00841     tor_munmap_file(store->mmap);
00842   store->mmap = NULL;
00843 
00844   store->mmap = tor_mmap_file(fname);
00845   if (!store->mmap && altname && file_status(altname) == FN_FILE) {
00846     read_from_old_location = 1;
00847     log_notice(LD_DIR, "Couldn't read %s; trying to load routers from old "
00848                "location %s.", fname, altname);
00849     if ((store->mmap = tor_mmap_file(altname)))
00850       read_from_old_location = 1;
00851   }
00852   if (altname && !read_from_old_location) {
00853     remove_file_if_very_old(altname, now);
00854   }
00855   if (store->mmap) {
00856     store->store_len = store->mmap->size;
00857     if (extrainfo)
00858       router_load_extrainfo_from_string(store->mmap->data,
00859                                         store->mmap->data+store->mmap->size,
00860                                         SAVED_IN_CACHE, NULL, 0);
00861     else
00862       router_load_routers_from_string(store->mmap->data,
00863                                       store->mmap->data+store->mmap->size,
00864                                       SAVED_IN_CACHE, NULL, 0, NULL);
00865   }
00866 
00867   tor_free(fname);
00868   fname = get_datadir_fname_suffix(store->fname_base, ".new");
00869   if (file_status(fname) == FN_FILE)
00870     contents = read_file_to_str(fname, RFTS_BIN|RFTS_IGNORE_MISSING, &st);
00871   if (read_from_old_location) {
00872     tor_free(altname);
00873     altname = get_datadir_fname_suffix(store->fname_alt_base, ".new");
00874     if (!contents)
00875       contents = read_file_to_str(altname, RFTS_BIN|RFTS_IGNORE_MISSING, &st);
00876     else
00877       remove_file_if_very_old(altname, now);
00878   }
00879   if (contents) {
00880     if (extrainfo)
00881       router_load_extrainfo_from_string(contents, NULL,SAVED_IN_JOURNAL,
00882                                         NULL, 0);
00883     else
00884       router_load_routers_from_string(contents, NULL, SAVED_IN_JOURNAL,
00885                                       NULL, 0, NULL);
00886     store->journal_len = (size_t) st.st_size;
00887     tor_free(contents);
00888   }
00889 
00890   tor_free(fname);
00891   tor_free(altname);
00892 
00893   if (store->journal_len || read_from_old_location) {
00894     /* Always clear the journal on startup.*/
00895     router_rebuild_store(RRS_FORCE, store);
00896   } else if (!extrainfo) {
00897     /* Don't cache expired routers. (This is in an else because
00898      * router_rebuild_store() also calls remove_old_routers().) */
00899     routerlist_remove_old_routers();
00900   }
00901 
00902   return 0;
00903 }
00904 
00908 int
00909 router_reload_router_list(void)
00910 {
00911   routerlist_t *rl = router_get_routerlist();
00912   if (router_reload_router_list_impl(&rl->desc_store))
00913     return -1;
00914   if (router_reload_router_list_impl(&rl->extrainfo_store))
00915     return -1;
00916   return 0;
00917 }
00918 
00923 smartlist_t *
00924 router_get_trusted_dir_servers(void)
00925 {
00926   if (!trusted_dir_servers)
00927     trusted_dir_servers = smartlist_new();
00928 
00929   return trusted_dir_servers;
00930 }
00931 
00947 const routerstatus_t *
00948 router_pick_directory_server(dirinfo_type_t type, int flags)
00949 {
00950   const routerstatus_t *choice;
00951   if (get_options()->PreferTunneledDirConns)
00952     flags |= _PDS_PREFER_TUNNELED_DIR_CONNS;
00953 
00954   if (!routerlist)
00955     return NULL;
00956 
00957   choice = router_pick_directory_server_impl(type, flags);
00958   if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
00959     return choice;
00960 
00961   log_info(LD_DIR,
00962            "No reachable router entries for dirservers. "
00963            "Trying them all again.");
00964   /* mark all authdirservers as up again */
00965   mark_all_trusteddirservers_up();
00966   /* try again */
00967   choice = router_pick_directory_server_impl(type, flags);
00968   return choice;
00969 }
00970 
00975 int
00976 router_get_my_share_of_directory_requests(double *v2_share_out,
00977                                           double *v3_share_out)
00978 {
00979   const routerinfo_t *me = router_get_my_routerinfo();
00980   const routerstatus_t *rs;
00981   const int pds_flags = PDS_ALLOW_SELF|PDS_IGNORE_FASCISTFIREWALL;
00982   *v2_share_out = *v3_share_out = 0.0;
00983   if (!me)
00984     return -1;
00985   rs = router_get_consensus_status_by_id(me->cache_info.identity_digest);
00986   if (!rs)
00987     return -1;
00988 
00989   /* Calling for side effect */
00990   /* XXXX This is a bit of a kludge */
00991   if (rs->is_v2_dir) {
00992     sl_last_total_weighted_bw = 0;
00993     router_pick_directory_server(V2_DIRINFO, pds_flags);
00994     if (sl_last_total_weighted_bw != 0) {
00995       *v2_share_out = U64_TO_DBL(sl_last_weighted_bw_of_me) /
00996         U64_TO_DBL(sl_last_total_weighted_bw);
00997     }
00998   }
00999 
01000   if (rs->version_supports_v3_dir) {
01001     sl_last_total_weighted_bw = 0;
01002     router_pick_directory_server(V3_DIRINFO, pds_flags);
01003     if (sl_last_total_weighted_bw != 0) {
01004       *v3_share_out = U64_TO_DBL(sl_last_weighted_bw_of_me) /
01005         U64_TO_DBL(sl_last_total_weighted_bw);
01006     }
01007   }
01008 
01009   return 0;
01010 }
01011 
01015 trusted_dir_server_t *
01016 router_get_trusteddirserver_by_digest(const char *digest)
01017 {
01018   if (!trusted_dir_servers)
01019     return NULL;
01020 
01021   SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
01022      {
01023        if (tor_memeq(ds->digest, digest, DIGEST_LEN))
01024          return ds;
01025      });
01026 
01027   return NULL;
01028 }
01029 
01034 trusted_dir_server_t *
01035 trusteddirserver_get_by_v3_auth_digest(const char *digest)
01036 {
01037   if (!trusted_dir_servers)
01038     return NULL;
01039 
01040   SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
01041      {
01042        if (tor_memeq(ds->v3_identity_digest, digest, DIGEST_LEN) &&
01043            (ds->type & V3_DIRINFO))
01044          return ds;
01045      });
01046 
01047   return NULL;
01048 }
01049 
01053 const routerstatus_t *
01054 router_pick_trusteddirserver(dirinfo_type_t type, int flags)
01055 {
01056   const routerstatus_t *choice;
01057   int busy = 0;
01058   if (get_options()->PreferTunneledDirConns)
01059     flags |= _PDS_PREFER_TUNNELED_DIR_CONNS;
01060 
01061   choice = router_pick_trusteddirserver_impl(type, flags, &busy);
01062   if (choice || !(flags & PDS_RETRY_IF_NO_SERVERS))
01063     return choice;
01064   if (busy) {
01065     /* If the reason that we got no server is that servers are "busy",
01066      * we must be excluding good servers because we already have serverdesc
01067      * fetches with them.  Do not mark down servers up because of this. */
01068     tor_assert((flags & (PDS_NO_EXISTING_SERVERDESC_FETCH|
01069                          PDS_NO_EXISTING_MICRODESC_FETCH)));
01070     return NULL;
01071   }
01072 
01073   log_info(LD_DIR,
01074            "No trusted dirservers are reachable. Trying them all again.");
01075   mark_all_trusteddirservers_up();
01076   return router_pick_trusteddirserver_impl(type, flags, NULL);
01077 }
01078 
01080 #define DIR_503_TIMEOUT (60*60)
01081 
01089 static const routerstatus_t *
01090 router_pick_directory_server_impl(dirinfo_type_t type, int flags)
01091 {
01092   const or_options_t *options = get_options();
01093   const node_t *result;
01094   smartlist_t *direct, *tunnel;
01095   smartlist_t *trusted_direct, *trusted_tunnel;
01096   smartlist_t *overloaded_direct, *overloaded_tunnel;
01097   time_t now = time(NULL);
01098   const networkstatus_t *consensus = networkstatus_get_latest_consensus();
01099   int requireother = ! (flags & PDS_ALLOW_SELF);
01100   int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
01101   int prefer_tunnel = (flags & _PDS_PREFER_TUNNELED_DIR_CONNS);
01102   int try_excluding = 1, n_excluded = 0;
01103 
01104   if (!consensus)
01105     return NULL;
01106 
01107  retry_without_exclude:
01108 
01109   direct = smartlist_new();
01110   tunnel = smartlist_new();
01111   trusted_direct = smartlist_new();
01112   trusted_tunnel = smartlist_new();
01113   overloaded_direct = smartlist_new();
01114   overloaded_tunnel = smartlist_new();
01115 
01116   /* Find all the running dirservers we know about. */
01117   SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) {
01118     int is_trusted;
01119     int is_overloaded;
01120     tor_addr_t addr;
01121     const routerstatus_t *status = node->rs;
01122     const country_t country = node->country;
01123     if (!status)
01124       continue;
01125 
01126     if (!node->is_running || !status->dir_port || !node->is_valid)
01127       continue;
01128     if (node->is_bad_directory)
01129       continue;
01130     if (requireother && router_digest_is_me(node->identity))
01131       continue;
01132     if (type & V3_DIRINFO) {
01133       if (!(status->version_supports_v3_dir ||
01134             router_digest_is_trusted_dir_type(node->identity,
01135                                               V3_DIRINFO)))
01136         continue;
01137     }
01138     is_trusted = router_digest_is_trusted_dir(node->identity);
01139     if ((type & V2_DIRINFO) && !(node->rs->is_v2_dir || is_trusted))
01140       continue;
01141     if ((type & EXTRAINFO_DIRINFO) &&
01142         !router_supports_extrainfo(node->identity, 0))
01143       continue;
01144     if ((type & MICRODESC_DIRINFO) && !is_trusted &&
01145         !node->rs->version_supports_microdesc_cache)
01146       continue;
01147     if (try_excluding &&
01148         routerset_contains_routerstatus(options->ExcludeNodes, status,
01149                                         country)) {
01150       ++n_excluded;
01151       continue;
01152     }
01153 
01154     /* XXXX IP6 proposal 118 */
01155     tor_addr_from_ipv4h(&addr, node->rs->addr);
01156 
01157     is_overloaded = status->last_dir_503_at + DIR_503_TIMEOUT > now;
01158 
01159     if (prefer_tunnel &&
01160         status->version_supports_begindir &&
01161         (!fascistfirewall ||
01162          fascist_firewall_allows_address_or(&addr, status->or_port)))
01163       smartlist_add(is_trusted ? trusted_tunnel :
01164                     is_overloaded ? overloaded_tunnel : tunnel, (void*)node);
01165     else if (!fascistfirewall ||
01166              fascist_firewall_allows_address_dir(&addr, status->dir_port))
01167       smartlist_add(is_trusted ? trusted_direct :
01168                     is_overloaded ? overloaded_direct : direct, (void*)node);
01169   } SMARTLIST_FOREACH_END(node);
01170 
01171   if (smartlist_len(tunnel)) {
01172     result = node_sl_choose_by_bandwidth(tunnel, WEIGHT_FOR_DIR);
01173   } else if (smartlist_len(overloaded_tunnel)) {
01174     result = node_sl_choose_by_bandwidth(overloaded_tunnel,
01175                                                  WEIGHT_FOR_DIR);
01176   } else if (smartlist_len(trusted_tunnel)) {
01177     /* FFFF We don't distinguish between trusteds and overloaded trusteds
01178      * yet. Maybe one day we should. */
01179     /* FFFF We also don't load balance over authorities yet. I think this
01180      * is a feature, but it could easily be a bug. -RD */
01181     result = smartlist_choose(trusted_tunnel);
01182   } else if (smartlist_len(direct)) {
01183     result = node_sl_choose_by_bandwidth(direct, WEIGHT_FOR_DIR);
01184   } else if (smartlist_len(overloaded_direct)) {
01185     result = node_sl_choose_by_bandwidth(overloaded_direct,
01186                                          WEIGHT_FOR_DIR);
01187   } else {
01188     result = smartlist_choose(trusted_direct);
01189   }
01190   smartlist_free(direct);
01191   smartlist_free(tunnel);
01192   smartlist_free(trusted_direct);
01193   smartlist_free(trusted_tunnel);
01194   smartlist_free(overloaded_direct);
01195   smartlist_free(overloaded_tunnel);
01196 
01197   if (result == NULL && try_excluding && !options->StrictNodes && n_excluded) {
01198     /* If we got no result, and we are excluding nodes, and StrictNodes is
01199      * not set, try again without excluding nodes. */
01200     try_excluding = 0;
01201     n_excluded = 0;
01202     goto retry_without_exclude;
01203   }
01204 
01205   return result ? result->rs : NULL;
01206 }
01207 
01211 static const routerstatus_t *
01212 router_pick_trusteddirserver_impl(dirinfo_type_t type, int flags,
01213                                   int *n_busy_out)
01214 {
01215   const or_options_t *options = get_options();
01216   smartlist_t *direct, *tunnel;
01217   smartlist_t *overloaded_direct, *overloaded_tunnel;
01218   const routerinfo_t *me = router_get_my_routerinfo();
01219   const routerstatus_t *result;
01220   time_t now = time(NULL);
01221   const int requireother = ! (flags & PDS_ALLOW_SELF);
01222   const int fascistfirewall = ! (flags & PDS_IGNORE_FASCISTFIREWALL);
01223   const int prefer_tunnel = (flags & _PDS_PREFER_TUNNELED_DIR_CONNS);
01224   const int no_serverdesc_fetching =(flags & PDS_NO_EXISTING_SERVERDESC_FETCH);
01225   const int no_microdesc_fetching =(flags & PDS_NO_EXISTING_MICRODESC_FETCH);
01226   int n_busy = 0;
01227   int try_excluding = 1, n_excluded = 0;
01228 
01229   if (!trusted_dir_servers)
01230     return NULL;
01231 
01232  retry_without_exclude:
01233 
01234   direct = smartlist_new();
01235   tunnel = smartlist_new();
01236   overloaded_direct = smartlist_new();
01237   overloaded_tunnel = smartlist_new();
01238 
01239   SMARTLIST_FOREACH_BEGIN(trusted_dir_servers, trusted_dir_server_t *, d)
01240     {
01241       int is_overloaded =
01242           d->fake_status.last_dir_503_at + DIR_503_TIMEOUT > now;
01243       tor_addr_t addr;
01244       if (!d->is_running) continue;
01245       if ((type & d->type) == 0)
01246         continue;
01247       if ((type & EXTRAINFO_DIRINFO) &&
01248           !router_supports_extrainfo(d->digest, 1))
01249         continue;
01250       if (requireother && me && router_digest_is_me(d->digest))
01251           continue;
01252       if (try_excluding &&
01253           routerset_contains_routerstatus(options->ExcludeNodes,
01254                                           &d->fake_status, -1)) {
01255         ++n_excluded;
01256         continue;
01257       }
01258 
01259       /* XXXX IP6 proposal 118 */
01260       tor_addr_from_ipv4h(&addr, d->addr);
01261 
01262       if (no_serverdesc_fetching) {
01263         if (connection_get_by_type_addr_port_purpose(
01264             CONN_TYPE_DIR, &addr, d->dir_port, DIR_PURPOSE_FETCH_SERVERDESC)
01265          || connection_get_by_type_addr_port_purpose(
01266              CONN_TYPE_DIR, &addr, d->dir_port, DIR_PURPOSE_FETCH_EXTRAINFO)) {
01267           //log_debug(LD_DIR, "We have an existing connection to fetch "
01268           //           "descriptor from %s; delaying",d->description);
01269           ++n_busy;
01270           continue;
01271         }
01272       }
01273       if (no_microdesc_fetching) {
01274         if (connection_get_by_type_addr_port_purpose(
01275              CONN_TYPE_DIR, &addr, d->dir_port, DIR_PURPOSE_FETCH_MICRODESC)) {
01276           ++n_busy;
01277           continue;
01278         }
01279       }
01280 
01281       if (prefer_tunnel &&
01282           d->or_port &&
01283           (!fascistfirewall ||
01284            fascist_firewall_allows_address_or(&addr, d->or_port)))
01285         smartlist_add(is_overloaded ? overloaded_tunnel : tunnel,
01286                       &d->fake_status);
01287       else if (!fascistfirewall ||
01288                fascist_firewall_allows_address_dir(&addr, d->dir_port))
01289         smartlist_add(is_overloaded ? overloaded_direct : direct,
01290                       &d->fake_status);
01291     }
01292   SMARTLIST_FOREACH_END(d);
01293 
01294   if (smartlist_len(tunnel)) {
01295     result = smartlist_choose(tunnel);
01296   } else if (smartlist_len(overloaded_tunnel)) {
01297     result = smartlist_choose(overloaded_tunnel);
01298   } else if (smartlist_len(direct)) {
01299     result = smartlist_choose(direct);
01300   } else {
01301     result = smartlist_choose(overloaded_direct);
01302   }
01303 
01304   if (n_busy_out)
01305     *n_busy_out = n_busy;
01306 
01307   smartlist_free(direct);
01308   smartlist_free(tunnel);
01309   smartlist_free(overloaded_direct);
01310   smartlist_free(overloaded_tunnel);
01311 
01312   if (result == NULL && try_excluding && !options->StrictNodes && n_excluded) {
01313     /* If we got no result, and we are excluding nodes, and StrictNodes is
01314      * not set, try again without excluding nodes. */
01315     try_excluding = 0;
01316     n_excluded = 0;
01317     goto retry_without_exclude;
01318   }
01319 
01320   return result;
01321 }
01322 
01324 static void
01325 mark_all_trusteddirservers_up(void)
01326 {
01327   SMARTLIST_FOREACH(nodelist_get_list(), node_t *, node, {
01328        if (router_digest_is_trusted_dir(node->identity))
01329          node->is_running = 1;
01330     });
01331   if (trusted_dir_servers) {
01332     SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, dir,
01333     {
01334       routerstatus_t *rs;
01335       dir->is_running = 1;
01336       download_status_reset(&dir->v2_ns_dl_status);
01337       rs = router_get_mutable_consensus_status_by_id(dir->digest);
01338       if (rs) {
01339         rs->last_dir_503_at = 0;
01340         control_event_networkstatus_changed_single(rs);
01341       }
01342     });
01343   }
01344   router_dir_info_changed();
01345 }
01346 
01348 int
01349 routers_have_same_or_addr(const routerinfo_t *r1, const routerinfo_t *r2)
01350 {
01351   return r1->addr == r2->addr && r1->or_port == r2->or_port;
01352 }
01353 
01356 void
01357 router_reset_status_download_failures(void)
01358 {
01359   mark_all_trusteddirservers_up();
01360 }
01361 
01364 static INLINE int
01365 addrs_in_same_network_family(const tor_addr_t *a1,
01366                              const tor_addr_t *a2)
01367 {
01368   /* XXXX MOVE ? */
01369   return 0 == tor_addr_compare_masked(a1, a2, 16, CMP_SEMANTIC);
01370 }
01371 
01381 void
01382 nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
01383 {
01384   /* XXXX MOVE */
01385   const smartlist_t *all_nodes = nodelist_get_list();
01386   const smartlist_t *declared_family;
01387   const or_options_t *options = get_options();
01388 
01389   tor_assert(node);
01390 
01391   declared_family = node_get_declared_family(node);
01392 
01393   /* Let's make sure that we have the node itself, if it's a real node. */
01394   {
01395     const node_t *real_node = node_get_by_id(node->identity);
01396     if (real_node)
01397       smartlist_add(sl, (node_t*)real_node);
01398   }
01399 
01400   /* First, add any nodes with similar network addresses. */
01401   if (options->EnforceDistinctSubnets) {
01402     tor_addr_t node_addr;
01403     node_get_addr(node, &node_addr);
01404 
01405     SMARTLIST_FOREACH_BEGIN(all_nodes, const node_t *, node2) {
01406       tor_addr_t a;
01407       node_get_addr(node2, &a);
01408       if (addrs_in_same_network_family(&a, &node_addr))
01409         smartlist_add(sl, (void*)node2);
01410     } SMARTLIST_FOREACH_END(node2);
01411   }
01412 
01413   /* Now, add all nodes in the declared_family of this node, if they
01414    * also declare this node to be in their family. */
01415   if (declared_family) {
01416     /* Add every r such that router declares familyness with node, and node
01417      * declares familyhood with router. */
01418     SMARTLIST_FOREACH_BEGIN(declared_family, const char *, name) {
01419       const node_t *node2;
01420       const smartlist_t *family2;
01421       if (!(node2 = node_get_by_nickname(name, 0)))
01422         continue;
01423       if (!(family2 = node_get_declared_family(node2)))
01424         continue;
01425       SMARTLIST_FOREACH_BEGIN(family2, const char *, name2) {
01426           if (node_nickname_matches(node, name2)) {
01427             smartlist_add(sl, (void*)node2);
01428             break;
01429           }
01430       } SMARTLIST_FOREACH_END(name2);
01431     } SMARTLIST_FOREACH_END(name);
01432   }
01433 
01434   /* If the user declared any families locally, honor those too. */
01435   if (options->NodeFamilySets) {
01436     SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, {
01437       if (routerset_contains_node(rs, node)) {
01438         routerset_get_all_nodes(sl, rs, NULL, 0);
01439       }
01440     });
01441   }
01442 }
01443 
01450 static void
01451 routerlist_add_node_and_family(smartlist_t *sl, const routerinfo_t *router)
01452 {
01453   /* XXXX MOVE ? */
01454   node_t fake_node;
01455   const node_t *node = node_get_by_id(router->cache_info.identity_digest);;
01456   if (node == NULL) {
01457     memset(&fake_node, 0, sizeof(fake_node));
01458     fake_node.ri = (routerinfo_t *)router;
01459     memcpy(fake_node.identity, router->cache_info.identity_digest, DIGEST_LEN);
01460     node = &fake_node;
01461   }
01462   nodelist_add_node_and_family(sl, node);
01463 }
01464 
01466 static INLINE int
01467 node_in_nickname_smartlist(const smartlist_t *lst, const node_t *node)
01468 {
01469   /* XXXX MOVE */
01470   if (!lst) return 0;
01471   SMARTLIST_FOREACH(lst, const char *, name, {
01472     if (node_nickname_matches(node, name))
01473       return 1;
01474   });
01475   return 0;
01476 }
01477 
01480 int
01481 nodes_in_same_family(const node_t *node1, const node_t *node2)
01482 {
01483   /* XXXX MOVE */
01484   const or_options_t *options = get_options();
01485 
01486   /* Are they in the same family because of their addresses? */
01487   if (options->EnforceDistinctSubnets) {
01488     tor_addr_t a1, a2;
01489     node_get_addr(node1, &a1);
01490     node_get_addr(node2, &a2);
01491     if (addrs_in_same_network_family(&a1, &a2))
01492       return 1;
01493   }
01494 
01495   /* Are they in the same family because the agree they are? */
01496   {
01497     const smartlist_t *f1, *f2;
01498     f1 = node_get_declared_family(node1);
01499     f2 = node_get_declared_family(node2);
01500     if (f1 && f2 &&
01501         node_in_nickname_smartlist(f1, node2) &&
01502         node_in_nickname_smartlist(f2, node1))
01503       return 1;
01504   }
01505 
01506   /* Are they in the same option because the user says they are? */
01507   if (options->NodeFamilySets) {
01508     SMARTLIST_FOREACH(options->NodeFamilySets, const routerset_t *, rs, {
01509         if (routerset_contains_node(rs, node1) &&
01510             routerset_contains_node(rs, node2))
01511           return 1;
01512       });
01513   }
01514 
01515   return 0;
01516 }
01517 
01522 int
01523 router_nickname_is_in_list(const routerinfo_t *router, const char *list)
01524 {
01525   smartlist_t *nickname_list;
01526   int v = 0;
01527 
01528   if (!list)
01529     return 0; /* definitely not */
01530   tor_assert(router);
01531 
01532   nickname_list = smartlist_new();
01533   smartlist_split_string(nickname_list, list, ",",
01534     SPLIT_SKIP_SPACE|SPLIT_STRIP_SPACE|SPLIT_IGNORE_BLANK, 0);
01535   SMARTLIST_FOREACH(nickname_list, const char *, cp,
01536                     if (router_nickname_matches(router, cp)) {v=1;break;});
01537   SMARTLIST_FOREACH(nickname_list, char *, cp, tor_free(cp));
01538   smartlist_free(nickname_list);
01539   return v;
01540 }
01541 
01545 static void
01546 router_add_running_nodes_to_smartlist(smartlist_t *sl, int allow_invalid,
01547                                       int need_uptime, int need_capacity,
01548                                       int need_guard, int need_desc)
01549 { /* XXXX MOVE */
01550   SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) {
01551     if (!node->is_running ||
01552         (!node->is_valid && !allow_invalid))
01553       continue;
01554     if (need_desc && !(node->ri || (node->rs && node->md)))
01555       continue;
01556     if (node->ri && node->ri->purpose != ROUTER_PURPOSE_GENERAL)
01557       continue;
01558     if (node_is_unreliable(node, need_uptime, need_capacity, need_guard))
01559       continue;
01560 
01561     smartlist_add(sl, (void *)node);
01562   } SMARTLIST_FOREACH_END(node);
01563 }
01564 
01567 const routerinfo_t *
01568 routerlist_find_my_routerinfo(void)
01569 {
01570   if (!routerlist)
01571     return NULL;
01572 
01573   SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
01574   {
01575     if (router_is_me(router))
01576       return router;
01577   });
01578   return NULL;
01579 }
01580 
01587 const node_t *
01588 router_find_exact_exit_enclave(const char *address, uint16_t port)
01589 {/*XXXX MOVE*/
01590   uint32_t addr;
01591   struct in_addr in;
01592   tor_addr_t a;
01593   const or_options_t *options = get_options();
01594 
01595   if (!tor_inet_aton(address, &in))
01596     return NULL; /* it's not an IP already */
01597   addr = ntohl(in.s_addr);
01598 
01599   tor_addr_from_ipv4h(&a, addr);
01600 
01601   SMARTLIST_FOREACH(nodelist_get_list(), const node_t *, node, {
01602     if (node_get_addr_ipv4h(node) == addr &&
01603         node->is_running &&
01604         compare_tor_addr_to_node_policy(&a, port, node) ==
01605           ADDR_POLICY_ACCEPTED &&
01606         !routerset_contains_node(options->_ExcludeExitNodesUnion, node))
01607       return node;
01608   });
01609   return NULL;
01610 }
01611 
01618 int
01619 node_is_unreliable(const node_t *node, int need_uptime,
01620                    int need_capacity, int need_guard)
01621 {
01622   if (need_uptime && !node->is_stable)
01623     return 1;
01624   if (need_capacity && !node->is_fast)
01625     return 1;
01626   if (need_guard && !node->is_possible_guard)
01627     return 1;
01628   return 0;
01629 }
01630 
01633 uint32_t
01634 router_get_advertised_bandwidth(const routerinfo_t *router)
01635 {
01636   if (router->bandwidthcapacity < router->bandwidthrate)
01637     return router->bandwidthcapacity;
01638   return router->bandwidthrate;
01639 }
01640 
01643 #define DEFAULT_MAX_BELIEVABLE_BANDWIDTH 10000000 /* 10 MB/sec */
01644 
01647 uint32_t
01648 router_get_advertised_bandwidth_capped(const routerinfo_t *router)
01649 {
01650   uint32_t result = router->bandwidthcapacity;
01651   if (result > router->bandwidthrate)
01652     result = router->bandwidthrate;
01653   if (result > DEFAULT_MAX_BELIEVABLE_BANDWIDTH)
01654     result = DEFAULT_MAX_BELIEVABLE_BANDWIDTH;
01655   return result;
01656 }
01657 
01661 #define BRIDGE_MIN_BELIEVABLE_BANDWIDTH 20000  /* 20 kB/sec */
01662 #define BRIDGE_MAX_BELIEVABLE_BANDWIDTH 100000 /* 100 kB/sec */
01663 
01668 static uint32_t
01669 bridge_get_advertised_bandwidth_bounded(routerinfo_t *router)
01670 {
01671   uint32_t result = router->bandwidthcapacity;
01672   if (result > router->bandwidthrate)
01673     result = router->bandwidthrate;
01674   if (result > BRIDGE_MAX_BELIEVABLE_BANDWIDTH)
01675     result = BRIDGE_MAX_BELIEVABLE_BANDWIDTH;
01676   else if (result < BRIDGE_MIN_BELIEVABLE_BANDWIDTH)
01677     result = BRIDGE_MIN_BELIEVABLE_BANDWIDTH;
01678   return result;
01679 }
01680 
01683 static INLINE int32_t
01684 kb_to_bytes(uint32_t bw)
01685 {
01686   return (bw > (INT32_MAX/1000)) ? INT32_MAX : bw*1000;
01687 }
01688 
01703 static const node_t *
01704 smartlist_choose_node_by_bandwidth_weights(smartlist_t *sl,
01705                                            bandwidth_weight_rule_t rule)
01706 {
01707   int64_t weight_scale;
01708   int64_t rand_bw;
01709   double Wg = -1, Wm = -1, We = -1, Wd = -1;
01710   double Wgb = -1, Wmb = -1, Web = -1, Wdb = -1;
01711   double weighted_bw = 0, unweighted_bw = 0;
01712   double *bandwidths;
01713   double tmp = 0;
01714   unsigned int i;
01715   int have_unknown = 0; /* true iff sl contains element not in consensus. */
01716 
01717   /* Can't choose exit and guard at same time */
01718   tor_assert(rule == NO_WEIGHTING ||
01719              rule == WEIGHT_FOR_EXIT ||
01720              rule == WEIGHT_FOR_GUARD ||
01721              rule == WEIGHT_FOR_MID ||
01722              rule == WEIGHT_FOR_DIR);
01723 
01724   if (smartlist_len(sl) == 0) {
01725     log_info(LD_CIRC,
01726              "Empty routerlist passed in to consensus weight node "
01727              "selection for rule %s",
01728              bandwidth_weight_rule_to_string(rule));
01729     return NULL;
01730   }
01731 
01732   weight_scale = circuit_build_times_get_bw_scale(NULL);
01733 
01734   if (rule == WEIGHT_FOR_GUARD) {
01735     Wg = networkstatus_get_bw_weight(NULL, "Wgg", -1);
01736     Wm = networkstatus_get_bw_weight(NULL, "Wgm", -1); /* Bridges */
01737     We = 0;
01738     Wd = networkstatus_get_bw_weight(NULL, "Wgd", -1);
01739 
01740     Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
01741     Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
01742     Web = networkstatus_get_bw_weight(NULL, "Web", -1);
01743     Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
01744   } else if (rule == WEIGHT_FOR_MID) {
01745     Wg = networkstatus_get_bw_weight(NULL, "Wmg", -1);
01746     Wm = networkstatus_get_bw_weight(NULL, "Wmm", -1);
01747     We = networkstatus_get_bw_weight(NULL, "Wme", -1);
01748     Wd = networkstatus_get_bw_weight(NULL, "Wmd", -1);
01749 
01750     Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
01751     Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
01752     Web = networkstatus_get_bw_weight(NULL, "Web", -1);
01753     Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
01754   } else if (rule == WEIGHT_FOR_EXIT) {
01755     // Guards CAN be exits if they have weird exit policies
01756     // They are d then I guess...
01757     We = networkstatus_get_bw_weight(NULL, "Wee", -1);
01758     Wm = networkstatus_get_bw_weight(NULL, "Wem", -1); /* Odd exit policies */
01759     Wd = networkstatus_get_bw_weight(NULL, "Wed", -1);
01760     Wg = networkstatus_get_bw_weight(NULL, "Weg", -1); /* Odd exit policies */
01761 
01762     Wgb = networkstatus_get_bw_weight(NULL, "Wgb", -1);
01763     Wmb = networkstatus_get_bw_weight(NULL, "Wmb", -1);
01764     Web = networkstatus_get_bw_weight(NULL, "Web", -1);
01765     Wdb = networkstatus_get_bw_weight(NULL, "Wdb", -1);
01766   } else if (rule == WEIGHT_FOR_DIR) {
01767     We = networkstatus_get_bw_weight(NULL, "Wbe", -1);
01768     Wm = networkstatus_get_bw_weight(NULL, "Wbm", -1);
01769     Wd = networkstatus_get_bw_weight(NULL, "Wbd", -1);
01770     Wg = networkstatus_get_bw_weight(NULL, "Wbg", -1);
01771 
01772     Wgb = Wmb = Web = Wdb = weight_scale;
01773   } else if (rule == NO_WEIGHTING) {
01774     Wg = Wm = We = Wd = weight_scale;
01775     Wgb = Wmb = Web = Wdb = weight_scale;
01776   }
01777 
01778   if (Wg < 0 || Wm < 0 || We < 0 || Wd < 0 || Wgb < 0 || Wmb < 0 || Wdb < 0
01779       || Web < 0) {
01780     log_debug(LD_CIRC,
01781               "Got negative bandwidth weights. Defaulting to old selection"
01782               " algorithm.");
01783     return NULL; // Use old algorithm.
01784   }
01785 
01786   Wg /= weight_scale;
01787   Wm /= weight_scale;
01788   We /= weight_scale;
01789   Wd /= weight_scale;
01790 
01791   Wgb /= weight_scale;
01792   Wmb /= weight_scale;
01793   Web /= weight_scale;
01794   Wdb /= weight_scale;
01795 
01796   bandwidths = tor_malloc_zero(sizeof(double)*smartlist_len(sl));
01797 
01798   // Cycle through smartlist and total the bandwidth.
01799   SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
01800     int is_exit = 0, is_guard = 0, is_dir = 0, this_bw = 0, is_me = 0;
01801     double weight = 1;
01802     is_exit = node->is_exit && ! node->is_bad_exit;
01803     is_guard = node->is_possible_guard;
01804     is_dir = node_is_dir(node);
01805     if (node->rs) {
01806       if (!node->rs->has_bandwidth) {
01807         tor_free(bandwidths);
01808         /* This should never happen, unless all the authorites downgrade
01809          * to 0.2.0 or rogue routerstatuses get inserted into our consensus. */
01810         log_warn(LD_BUG,
01811                  "Consensus is not listing bandwidths. Defaulting back to "
01812                  "old router selection algorithm.");
01813         return NULL;
01814       }
01815       this_bw = kb_to_bytes(node->rs->bandwidth);
01816     } else if (node->ri) {
01817       /* bridge or other descriptor not in our consensus */
01818       this_bw = bridge_get_advertised_bandwidth_bounded(node->ri);
01819       have_unknown = 1;
01820     } else {
01821       /* We can't use this one. */
01822       continue;
01823     }
01824     is_me = router_digest_is_me(node->identity);
01825 
01826     if (is_guard && is_exit) {
01827       weight = (is_dir ? Wdb*Wd : Wd);
01828     } else if (is_guard) {
01829       weight = (is_dir ? Wgb*Wg : Wg);
01830     } else if (is_exit) {
01831       weight = (is_dir ? Web*We : We);
01832     } else { // middle
01833       weight = (is_dir ? Wmb*Wm : Wm);
01834     }
01835 
01836     bandwidths[node_sl_idx] = weight*this_bw;
01837     weighted_bw += weight*this_bw;
01838     unweighted_bw += this_bw;
01839     if (is_me)
01840       sl_last_weighted_bw_of_me = weight*this_bw;
01841   } SMARTLIST_FOREACH_END(node);
01842 
01843   /* XXXX this is a kludge to expose these values. */
01844   sl_last_total_weighted_bw = weighted_bw;
01845 
01846   log_debug(LD_CIRC, "Choosing node for rule %s based on weights "
01847             "Wg=%f Wm=%f We=%f Wd=%f with total bw %f",
01848             bandwidth_weight_rule_to_string(rule),
01849             Wg, Wm, We, Wd, weighted_bw);
01850 
01851   /* If there is no bandwidth, choose at random */
01852   if (DBL_TO_U64(weighted_bw) == 0) {
01853     /* Don't warn when using bridges/relays not in the consensus */
01854     if (!have_unknown) {
01855 #define ZERO_BANDWIDTH_WARNING_INTERVAL (15)
01856       static ratelim_t zero_bandwidth_warning_limit =
01857         RATELIM_INIT(ZERO_BANDWIDTH_WARNING_INTERVAL);
01858       char *msg;
01859       if ((msg = rate_limit_log(&zero_bandwidth_warning_limit,
01860                                 approx_time()))) {
01861         log_warn(LD_CIRC,
01862                  "Weighted bandwidth is %f in node selection for rule %s "
01863                  "(unweighted was %f) %s",
01864                  weighted_bw, bandwidth_weight_rule_to_string(rule),
01865                  unweighted_bw, msg);
01866       }
01867     }
01868     tor_free(bandwidths);
01869     return smartlist_choose(sl);
01870   }
01871 
01872   rand_bw = crypto_rand_uint64(DBL_TO_U64(weighted_bw));
01873   rand_bw++; /* crypto_rand_uint64() counts from 0, and we need to count
01874               * from 1 below. See bug 1203 for details. */
01875 
01876   /* Last, count through sl until we get to the element we picked */
01877   tmp = 0.0;
01878   for (i=0; i < (unsigned)smartlist_len(sl); i++) {
01879     tmp += bandwidths[i];
01880     if (tmp >= rand_bw)
01881       break;
01882   }
01883 
01884   if (i == (unsigned)smartlist_len(sl)) {
01885     /* This was once possible due to round-off error, but shouldn't be able
01886      * to occur any longer. */
01887     tor_fragile_assert();
01888     --i;
01889     log_warn(LD_BUG, "Round-off error in computing bandwidth had an effect on "
01890              " which router we chose. Please tell the developers. "
01891              "%f " U64_FORMAT " %f", tmp, U64_PRINTF_ARG(rand_bw),
01892              weighted_bw);
01893   }
01894   tor_free(bandwidths);
01895   return smartlist_get(sl, i);
01896 }
01897 
01911 static const node_t *
01912 smartlist_choose_node_by_bandwidth(smartlist_t *sl,
01913                                    bandwidth_weight_rule_t rule)
01914 {
01915   unsigned i;
01916   int32_t *bandwidths;
01917   int is_exit;
01918   int is_guard;
01919   uint64_t total_nonexit_bw = 0, total_exit_bw = 0, total_bw = 0;
01920   uint64_t total_nonguard_bw = 0, total_guard_bw = 0;
01921   uint64_t rand_bw, tmp;
01922   double exit_weight;
01923   double guard_weight;
01924   int n_unknown = 0;
01925   bitarray_t *exit_bits;
01926   bitarray_t *guard_bits;
01927   int me_idx = -1;
01928 
01929   // This function does not support WEIGHT_FOR_DIR
01930   // or WEIGHT_FOR_MID
01931   if (rule == WEIGHT_FOR_DIR || rule == WEIGHT_FOR_MID) {
01932     rule = NO_WEIGHTING;
01933   }
01934 
01935   /* Can't choose exit and guard at same time */
01936   tor_assert(rule == NO_WEIGHTING ||
01937              rule == WEIGHT_FOR_EXIT ||
01938              rule == WEIGHT_FOR_GUARD);
01939 
01940   if (smartlist_len(sl) == 0) {
01941     log_info(LD_CIRC,
01942              "Empty routerlist passed in to old node selection for rule %s",
01943              bandwidth_weight_rule_to_string(rule));
01944     return NULL;
01945   }
01946 
01947   /* First count the total bandwidth weight, and make a list
01948    * of each value.  <0 means "unknown; no routerinfo."  We use the
01949    * bits of negative values to remember whether the router was fast (-x)&1
01950    * and whether it was an exit (-x)&2 or guard (-x)&4.  Yes, it's a hack. */
01951   bandwidths = tor_malloc(sizeof(int32_t)*smartlist_len(sl));
01952   exit_bits = bitarray_init_zero(smartlist_len(sl));
01953   guard_bits = bitarray_init_zero(smartlist_len(sl));
01954 
01955   /* Iterate over all the routerinfo_t or routerstatus_t, and */
01956   SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) {
01957     /* first, learn what bandwidth we think i has */
01958     int is_known = 1;
01959     int32_t flags = 0;
01960     uint32_t this_bw = 0;
01961     i = node_sl_idx;
01962 
01963     if (router_digest_is_me(node->identity))
01964       me_idx = node_sl_idx;
01965 
01966     is_exit = node->is_exit;
01967     is_guard = node->is_possible_guard;
01968     if (node->rs) {
01969       if (node->rs->has_bandwidth) {
01970         this_bw = kb_to_bytes(node->rs->bandwidth);
01971       } else { /* guess */
01972         /* XXX024 once consensuses always list bandwidths, we can take
01973          * this guessing business out. -RD */
01974         is_known = 0;
01975         flags = node->rs->is_fast ? 1 : 0;
01976         flags |= is_exit ? 2 : 0;
01977         flags |= is_guard ? 4 : 0;
01978       }
01979     } else if (node->ri) {
01980       /* Must be a bridge if we're willing to use it */
01981       this_bw = bridge_get_advertised_bandwidth_bounded(node->ri);
01982     }
01983 
01984     if (is_exit)
01985       bitarray_set(exit_bits, i);
01986     if (is_guard)
01987       bitarray_set(guard_bits, i);
01988     if (is_known) {
01989       bandwidths[i] = (int32_t) this_bw; // safe since MAX_BELIEVABLE<INT32_MAX
01990       // XXX this is no longer true! We don't always cap the bw anymore. Can
01991       // a consensus make us overflow?-sh
01992       tor_assert(bandwidths[i] >= 0);
01993       if (is_guard)
01994         total_guard_bw += this_bw;
01995       else
01996         total_nonguard_bw += this_bw;
01997       if (is_exit)
01998         total_exit_bw += this_bw;
01999       else
02000         total_nonexit_bw += this_bw;
02001     } else {
02002       ++n_unknown;
02003       bandwidths[node_sl_idx] = -flags;
02004     }
02005   } SMARTLIST_FOREACH_END(node);
02006 
02007   /* Now, fill in the unknown values. */
02008   if (n_unknown) {
02009     int32_t avg_fast, avg_slow;
02010     if (total_exit_bw+total_nonexit_bw) {
02011       /* if there's some bandwidth, there's at least one known router,
02012        * so no worries about div by 0 here */
02013       int n_known = smartlist_len(sl)-n_unknown;
02014       avg_fast = avg_slow = (int32_t)
02015         ((total_exit_bw+total_nonexit_bw)/((uint64_t) n_known));
02016     } else {
02017       avg_fast = 40000;
02018       avg_slow = 20000;
02019     }
02020     for (i=0; i<(unsigned)smartlist_len(sl); ++i) {
02021       int32_t bw = bandwidths[i];
02022       if (bw>=0)
02023         continue;
02024       is_exit = ((-bw)&2);
02025       is_guard = ((-bw)&4);
02026       bandwidths[i] = ((-bw)&1) ? avg_fast : avg_slow;
02027       if (is_exit)
02028         total_exit_bw += bandwidths[i];
02029       else
02030         total_nonexit_bw += bandwidths[i];
02031       if (is_guard)
02032         total_guard_bw += bandwidths[i];
02033       else
02034         total_nonguard_bw += bandwidths[i];
02035     }
02036   }
02037 
02038   /* If there's no bandwidth at all, pick at random. */
02039   if (!(total_exit_bw+total_nonexit_bw)) {
02040     tor_free(bandwidths);
02041     tor_free(exit_bits);
02042     tor_free(guard_bits);
02043     return smartlist_choose(sl);
02044   }
02045 
02046   /* Figure out how to weight exits and guards */
02047   {
02048     double all_bw = U64_TO_DBL(total_exit_bw+total_nonexit_bw);
02049     double exit_bw = U64_TO_DBL(total_exit_bw);
02050     double guard_bw = U64_TO_DBL(total_guard_bw);
02051     /*
02052      * For detailed derivation of this formula, see
02053      *   http://archives.seul.org/or/dev/Jul-2007/msg00056.html
02054      */
02055     if (rule == WEIGHT_FOR_EXIT || !total_exit_bw)
02056       exit_weight = 1.0;
02057     else
02058       exit_weight = 1.0 - all_bw/(3.0*exit_bw);
02059 
02060     if (rule == WEIGHT_FOR_GUARD || !total_guard_bw)
02061       guard_weight = 1.0;
02062     else
02063       guard_weight = 1.0 - all_bw/(3.0*guard_bw);
02064 
02065     if (exit_weight <= 0.0)
02066       exit_weight = 0.0;
02067 
02068     if (guard_weight <= 0.0)
02069       guard_weight = 0.0;
02070 
02071     total_bw = 0;
02072     sl_last_weighted_bw_of_me = 0;
02073     for (i=0; i < (unsigned)smartlist_len(sl); i++) {
02074       uint64_t bw;
02075       is_exit = bitarray_is_set(exit_bits, i);
02076       is_guard = bitarray_is_set(guard_bits, i);
02077       if (is_exit && is_guard)
02078         bw = ((uint64_t)(bandwidths[i] * exit_weight * guard_weight));
02079       else if (is_guard)
02080         bw = ((uint64_t)(bandwidths[i] * guard_weight));
02081       else if (is_exit)
02082         bw = ((uint64_t)(bandwidths[i] * exit_weight));
02083       else
02084         bw = bandwidths[i];
02085       total_bw += bw;
02086       if (i == (unsigned) me_idx)
02087         sl_last_weighted_bw_of_me = bw;
02088     }
02089   }
02090 
02091   /* XXXX this is a kludge to expose these values. */
02092   sl_last_total_weighted_bw = total_bw;
02093 
02094   log_debug(LD_CIRC, "Total weighted bw = "U64_FORMAT
02095             ", exit bw = "U64_FORMAT
02096             ", nonexit bw = "U64_FORMAT", exit weight = %f "
02097             "(for exit == %d)"
02098             ", guard bw = "U64_FORMAT
02099             ", nonguard bw = "U64_FORMAT", guard weight = %f "
02100             "(for guard == %d)",
02101             U64_PRINTF_ARG(total_bw),
02102             U64_PRINTF_ARG(total_exit_bw), U64_PRINTF_ARG(total_nonexit_bw),
02103             exit_weight, (int)(rule == WEIGHT_FOR_EXIT),
02104             U64_PRINTF_ARG(total_guard_bw), U64_PRINTF_ARG(total_nonguard_bw),
02105             guard_weight, (int)(rule == WEIGHT_FOR_GUARD));
02106 
02107   /* Almost done: choose a random value from the bandwidth weights. */
02108   rand_bw = crypto_rand_uint64(total_bw);
02109   rand_bw++; /* crypto_rand_uint64() counts from 0, and we need to count
02110               * from 1 below. See bug 1203 for details. */
02111 
02112   /* Last, count through sl until we get to the element we picked */
02113   tmp = 0;
02114   for (i=0; i < (unsigned)smartlist_len(sl); i++) {
02115     is_exit = bitarray_is_set(exit_bits, i);
02116     is_guard = bitarray_is_set(guard_bits, i);
02117 
02118     /* Weights can be 0 if not counting guards/exits */
02119     if (is_exit && is_guard)
02120       tmp += ((uint64_t)(bandwidths[i] * exit_weight * guard_weight));
02121     else if (is_guard)
02122       tmp += ((uint64_t)(bandwidths[i] * guard_weight));
02123     else if (is_exit)
02124       tmp += ((uint64_t)(bandwidths[i] * exit_weight));
02125     else
02126       tmp += bandwidths[i];
02127 
02128     if (tmp >= rand_bw)
02129       break;
02130   }
02131   if (i == (unsigned)smartlist_len(sl)) {
02132     /* This was once possible due to round-off error, but shouldn't be able
02133      * to occur any longer. */
02134     tor_fragile_assert();
02135     --i;
02136     log_warn(LD_BUG, "Round-off error in computing bandwidth had an effect on "
02137              " which router we chose. Please tell the developers. "
02138              U64_FORMAT " " U64_FORMAT " " U64_FORMAT, U64_PRINTF_ARG(tmp),
02139              U64_PRINTF_ARG(rand_bw), U64_PRINTF_ARG(total_bw));
02140   }
02141   tor_free(bandwidths);
02142   tor_free(exit_bits);
02143   tor_free(guard_bits);
02144   return smartlist_get(sl, i);
02145 }
02146 
02149 const node_t *
02150 node_sl_choose_by_bandwidth(smartlist_t *sl,
02151                             bandwidth_weight_rule_t rule)
02152 { /*XXXX MOVE */
02153   const node_t *ret;
02154   if ((ret = smartlist_choose_node_by_bandwidth_weights(sl, rule))) {
02155     return ret;
02156   } else {
02157     return smartlist_choose_node_by_bandwidth(sl, rule);
02158   }
02159 }
02160 
02179 const node_t *
02180 router_choose_random_node(smartlist_t *excludedsmartlist,
02181                           routerset_t *excludedset,
02182                           router_crn_flags_t flags)
02183 { /* XXXX MOVE */
02184   const int need_uptime = (flags & CRN_NEED_UPTIME) != 0;
02185   const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0;
02186   const int need_guard = (flags & CRN_NEED_GUARD) != 0;
02187   const int allow_invalid = (flags & CRN_ALLOW_INVALID) != 0;
02188   const int weight_for_exit = (flags & CRN_WEIGHT_AS_EXIT) != 0;
02189   const int need_desc = (flags & CRN_NEED_DESC) != 0;
02190 
02191   smartlist_t *sl=smartlist_new(),
02192     *excludednodes=smartlist_new();
02193   const node_t *choice = NULL;
02194   const routerinfo_t *r;
02195   bandwidth_weight_rule_t rule;
02196 
02197   tor_assert(!(weight_for_exit && need_guard));
02198   rule = weight_for_exit ? WEIGHT_FOR_EXIT :
02199     (need_guard ? WEIGHT_FOR_GUARD : WEIGHT_FOR_MID);
02200 
02201   /* Exclude relays that allow single hop exit circuits, if the user
02202    * wants to (such relays might be risky) */
02203   if (get_options()->ExcludeSingleHopRelays) {
02204     SMARTLIST_FOREACH(nodelist_get_list(), node_t *, node,
02205       if (node_allows_single_hop_exits(node)) {
02206         smartlist_add(excludednodes, node);
02207       });
02208   }
02209 
02210   if ((r = routerlist_find_my_routerinfo()))
02211     routerlist_add_node_and_family(excludednodes, r);
02212 
02213   router_add_running_nodes_to_smartlist(sl, allow_invalid,
02214                                         need_uptime, need_capacity,
02215                                         need_guard, need_desc);
02216   smartlist_subtract(sl,excludednodes);
02217   if (excludedsmartlist)
02218     smartlist_subtract(sl,excludedsmartlist);
02219   if (excludedset)
02220     routerset_subtract_nodes(sl,excludedset);
02221 
02222   // Always weight by bandwidth
02223   choice = node_sl_choose_by_bandwidth(sl, rule);
02224 
02225   smartlist_free(sl);
02226   if (!choice && (need_uptime || need_capacity || need_guard)) {
02227     /* try once more -- recurse but with fewer restrictions. */
02228     log_info(LD_CIRC,
02229              "We couldn't find any live%s%s%s routers; falling back "
02230              "to list of all routers.",
02231              need_capacity?", fast":"",
02232              need_uptime?", stable":"",
02233              need_guard?", guard":"");
02234     flags &= ~ (CRN_NEED_UPTIME|CRN_NEED_CAPACITY|CRN_NEED_GUARD);
02235     choice = router_choose_random_node(
02236                      excludedsmartlist, excludedset, flags);
02237   }
02238   smartlist_free(excludednodes);
02239   if (!choice) {
02240     log_warn(LD_CIRC,
02241              "No available nodes when trying to choose node. Failing.");
02242   }
02243   return choice;
02244 }
02245 
02262 int
02263 hex_digest_nickname_decode(const char *hexdigest,
02264                            char *digest_out,
02265                            char *nickname_qualifier_char_out,
02266                            char *nickname_out)
02267 {
02268   size_t len;
02269 
02270   tor_assert(hexdigest);
02271   if (hexdigest[0] == '$')
02272     ++hexdigest;
02273 
02274   len = strlen(hexdigest);
02275   if (len < HEX_DIGEST_LEN) {
02276     return -1;
02277   } else if (len > HEX_DIGEST_LEN && (hexdigest[HEX_DIGEST_LEN] == '=' ||
02278                                     hexdigest[HEX_DIGEST_LEN] == '~') &&
02279            len <= HEX_DIGEST_LEN+1+MAX_NICKNAME_LEN) {
02280     *nickname_qualifier_char_out = hexdigest[HEX_DIGEST_LEN];
02281     strlcpy(nickname_out, hexdigest+HEX_DIGEST_LEN+1 , MAX_NICKNAME_LEN+1);
02282   } else if (len == HEX_DIGEST_LEN) {
02283     ;
02284   } else {
02285     return -1;
02286   }
02287 
02288   if (base16_decode(digest_out, DIGEST_LEN, hexdigest, HEX_DIGEST_LEN)<0)
02289     return -1;
02290   return 0;
02291 }
02292 
02297 static int
02298 hex_digest_nickname_matches(const char *hexdigest, const char *identity_digest,
02299                             const char *nickname, int is_named)
02300 {
02301   char digest[DIGEST_LEN];
02302   char nn_char='\0';
02303   char nn_buf[MAX_NICKNAME_LEN+1];
02304 
02305   if (hex_digest_nickname_decode(hexdigest, digest, &nn_char, nn_buf) == -1)
02306     return 0;
02307 
02308   if (nn_char == '=' || nn_char == '~') {
02309     if (!nickname)
02310       return 0;
02311     if (strcasecmp(nn_buf, nickname))
02312       return 0;
02313     if (nn_char == '=' && !is_named)
02314       return 0;
02315   }
02316 
02317   return tor_memeq(digest, identity_digest, DIGEST_LEN);
02318 }
02319 
02322 int
02323 router_is_named(const routerinfo_t *router)
02324 {
02325   const char *digest =
02326     networkstatus_get_router_digest_by_nickname(router->nickname);
02327 
02328   return (digest &&
02329           tor_memeq(digest, router->cache_info.identity_digest, DIGEST_LEN));
02330 }
02331 
02336 static INLINE int
02337 router_hex_digest_matches(const routerinfo_t *router, const char *hexdigest)
02338 {
02339   return hex_digest_nickname_matches(hexdigest,
02340                                      router->cache_info.identity_digest,
02341                                      router->nickname,
02342                                      router_is_named(router));
02343 }
02344 
02349 static int
02350 router_nickname_matches(const routerinfo_t *router, const char *nickname)
02351 {
02352   if (nickname[0]!='$' && !strcasecmp(router->nickname, nickname))
02353     return 1;
02354   return router_hex_digest_matches(router, nickname);
02355 }
02356 
02361 static int
02362 node_nickname_matches(const node_t *node, const char *nickname)
02363 {
02364   const char *n = node_get_nickname(node);
02365   if (n && nickname[0]!='$' && !strcasecmp(n, nickname))
02366     return 1;
02367   return hex_digest_nickname_matches(nickname,
02368                                      node->identity,
02369                                      n,
02370                                      node_is_named(node));
02371 }
02372 
02377 const routerinfo_t *
02378 router_get_by_nickname(const char *nickname, int warn_if_unnamed)
02379 {
02380 #if 1
02381   const node_t *node = node_get_by_nickname(nickname, warn_if_unnamed);
02382   if (node)
02383     return node->ri;
02384   else
02385     return NULL;
02386 #else
02387   int maybedigest;
02388   char digest[DIGEST_LEN];
02389   routerinfo_t *best_match=NULL;
02390   int n_matches = 0;
02391   const char *named_digest = NULL;
02392 
02393   tor_assert(nickname);
02394   if (!routerlist)
02395     return NULL;
02396   if (nickname[0] == '$')
02397     return router_get_by_hexdigest(nickname);
02398   if (!strcasecmp(nickname, UNNAMED_ROUTER_NICKNAME))
02399     return NULL;
02400 
02401   maybedigest = (strlen(nickname) >= HEX_DIGEST_LEN) &&
02402     (base16_decode(digest,DIGEST_LEN,nickname,HEX_DIGEST_LEN) == 0);
02403 
02404   if ((named_digest = networkstatus_get_router_digest_by_nickname(nickname))) {
02405     return rimap_get(routerlist->identity_map, named_digest);
02406   }
02407   if (networkstatus_nickname_is_unnamed(nickname))
02408     return NULL;
02409 
02410   /* If we reach this point, there's no canonical value for the nickname. */
02411 
02412   SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, router,
02413   {
02414     if (!strcasecmp(router->nickname, nickname)) {
02415       ++n_matches;
02416       if (n_matches <= 1 || router->is_running)
02417         best_match = router;
02418     } else if (maybedigest &&
02419                tor_memeq(digest, router->cache_info.identity_digest,
02420                          DIGEST_LEN)) {
02421       if (router_hex_digest_matches(router, nickname))
02422         return router;
02423       /* If we reach this point, we have a ID=name syntax that matches the
02424        * identity but not the name. That isn't an acceptable match. */
02425     }
02426   });
02427 
02428   if (best_match) {
02429     if (warn_if_unnamed && n_matches > 1) {
02430       smartlist_t *fps = smartlist_new();
02431       int any_unwarned = 0;
02432       SMARTLIST_FOREACH_BEGIN(routerlist->routers, routerinfo_t *, router) {
02433           routerstatus_t *rs;
02434           char fp[HEX_DIGEST_LEN+1];
02435           if (strcasecmp(router->nickname, nickname))
02436             continue;
02437           rs = router_get_mutable_consensus_status_by_id(
02438                                           router->cache_info.identity_digest);
02439           if (rs && !rs->name_lookup_warned) {
02440             rs->name_lookup_warned = 1;
02441             any_unwarned = 1;
02442           }
02443           base16_encode(fp, sizeof(fp),
02444                         router->cache_info.identity_digest, DIGEST_LEN);
02445           smartlist_add_asprintf(fps, "\"$%s\" for the one at %s:%d",
02446                        fp, router->address, router->or_port);
02447       } SMARTLIST_FOREACH_END(router);
02448       if (any_unwarned) {
02449         char *alternatives = smartlist_join_strings(fps, "; ",0,NULL);
02450         log_warn(LD_CONFIG,
02451                  "There are multiple matches for the nickname \"%s\","
02452                  " but none is listed as named by the directory authorities. "
02453                  "Choosing one arbitrarily. If you meant one in particular, "
02454                  "you should say %s.", nickname, alternatives);
02455         tor_free(alternatives);
02456       }
02457       SMARTLIST_FOREACH(fps, char *, cp, tor_free(cp));
02458       smartlist_free(fps);
02459     } else if (warn_if_unnamed) {
02460       routerstatus_t *rs = router_get_mutable_consensus_status_by_id(
02461           best_match->cache_info.identity_digest);
02462       if (rs && !rs->name_lookup_warned) {
02463         char fp[HEX_DIGEST_LEN+1];
02464         base16_encode(fp, sizeof(fp),
02465                       best_match->cache_info.identity_digest, DIGEST_LEN);
02466         log_warn(LD_CONFIG, "You specified a server \"%s\" by name, but this "
02467              "name is not registered, so it could be used by any server, "
02468              "not just the one you meant. "
02469              "To make sure you get the same server in the future, refer to "
02470              "it by key, as \"$%s\".", nickname, fp);
02471         rs->name_lookup_warned = 1;
02472       }
02473     }
02474     return best_match;
02475   }
02476   return NULL;
02477 #endif
02478 }
02479 
02483 int
02484 router_digest_is_trusted_dir_type(const char *digest, dirinfo_type_t type)
02485 {
02486   if (!trusted_dir_servers)
02487     return 0;
02488   if (authdir_mode(get_options()) && router_digest_is_me(digest))
02489     return 1;
02490   SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent,
02491     if (tor_memeq(digest, ent->digest, DIGEST_LEN)) {
02492       return (!type) || ((type & ent->type) != 0);
02493     });
02494   return 0;
02495 }
02496 
02499 int
02500 router_addr_is_trusted_dir(uint32_t addr)
02501 {
02502   if (!trusted_dir_servers)
02503     return 0;
02504   SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent,
02505     if (ent->addr == addr)
02506       return 1;
02507     );
02508   return 0;
02509 }
02510 
02515 int
02516 hexdigest_to_digest(const char *hexdigest, char *digest)
02517 {
02518   if (hexdigest[0]=='$')
02519     ++hexdigest;
02520   if (strlen(hexdigest) < HEX_DIGEST_LEN ||
02521       base16_decode(digest,DIGEST_LEN,hexdigest,HEX_DIGEST_LEN) < 0)
02522     return -1;
02523   return 0;
02524 }
02525 
02528 const routerinfo_t *
02529 router_get_by_hexdigest(const char *hexdigest)
02530 {
02531   if (is_legal_nickname(hexdigest))
02532     return NULL;
02533 
02534   /* It's not a legal nickname, so it must be a hexdigest or nothing. */
02535   return router_get_by_nickname(hexdigest, 1);
02536 }
02537 
02540 routerinfo_t *
02541 router_get_mutable_by_digest(const char *digest)
02542 {
02543   tor_assert(digest);
02544 
02545   if (!routerlist) return NULL;
02546 
02547   // routerlist_assert_ok(routerlist);
02548 
02549   return rimap_get(routerlist->identity_map, digest);
02550 }
02551 
02554 const routerinfo_t *
02555 router_get_by_id_digest(const char *digest)
02556 {
02557   return router_get_mutable_by_digest(digest);
02558 }
02559 
02562 signed_descriptor_t *
02563 router_get_by_descriptor_digest(const char *digest)
02564 {
02565   tor_assert(digest);
02566 
02567   if (!routerlist) return NULL;
02568 
02569   return sdmap_get(routerlist->desc_digest_map, digest);
02570 }
02571 
02575 signed_descriptor_t *
02576 router_get_by_extrainfo_digest(const char *digest)
02577 {
02578   tor_assert(digest);
02579 
02580   if (!routerlist) return NULL;
02581 
02582   return sdmap_get(routerlist->desc_by_eid_map, digest);
02583 }
02584 
02588 signed_descriptor_t *
02589 extrainfo_get_by_descriptor_digest(const char *digest)
02590 {
02591   extrainfo_t *ei;
02592   tor_assert(digest);
02593   if (!routerlist) return NULL;
02594   ei = eimap_get(routerlist->extra_info_map, digest);
02595   return ei ? &ei->cache_info : NULL;
02596 }
02597 
02609 static const char *
02610 signed_descriptor_get_body_impl(const signed_descriptor_t *desc,
02611                                 int with_annotations)
02612 {
02613   const char *r = NULL;
02614   size_t len = desc->signed_descriptor_len;
02615   off_t offset = desc->saved_offset;
02616   if (with_annotations)
02617     len += desc->annotations_len;
02618   else
02619     offset += desc->annotations_len;
02620 
02621   tor_assert(len > 32);
02622   if (desc->saved_location == SAVED_IN_CACHE && routerlist) {
02623     desc_store_t *store = desc_get_store(router_get_routerlist(), desc);
02624     if (store && store->mmap) {
02625       tor_assert(desc->saved_offset + len <= store->mmap->size);
02626       r = store->mmap->data + offset;
02627     } else if (store) {
02628       log_err(LD_DIR, "We couldn't read a descriptor that is supposedly "
02629               "mmaped in our cache.  Is another process running in our data "
02630               "directory?  Exiting.");
02631       exit(1);
02632     }
02633   }
02634   if (!r) /* no mmap, or not in cache. */
02635     r = desc->signed_descriptor_body +
02636       (with_annotations ? 0 : desc->annotations_len);
02637 
02638   tor_assert(r);
02639   if (!with_annotations) {
02640     if (fast_memcmp("router ", r, 7) && fast_memcmp("extra-info ", r, 11)) {
02641       char *cp = tor_strndup(r, 64);
02642       log_err(LD_DIR, "descriptor at %p begins with unexpected string %s.  "
02643               "Is another process running in our data directory?  Exiting.",
02644               desc, escaped(cp));
02645       exit(1);
02646     }
02647   }
02648 
02649   return r;
02650 }
02651 
02658 const char *
02659 signed_descriptor_get_body(const signed_descriptor_t *desc)
02660 {
02661   return signed_descriptor_get_body_impl(desc, 0);
02662 }
02663 
02666 const char *
02667 signed_descriptor_get_annotations(const signed_descriptor_t *desc)
02668 {
02669   return signed_descriptor_get_body_impl(desc, 1);
02670 }
02671 
02673 routerlist_t *
02674 router_get_routerlist(void)
02675 {
02676   if (PREDICT_UNLIKELY(!routerlist)) {
02677     routerlist = tor_malloc_zero(sizeof(routerlist_t));
02678     routerlist->routers = smartlist_new();
02679     routerlist->old_routers = smartlist_new();
02680     routerlist->identity_map = rimap_new();
02681     routerlist->desc_digest_map = sdmap_new();
02682     routerlist->desc_by_eid_map = sdmap_new();
02683     routerlist->extra_info_map = eimap_new();
02684 
02685     routerlist->desc_store.fname_base = "cached-descriptors";
02686     routerlist->desc_store.fname_alt_base = "cached-routers";
02687     routerlist->extrainfo_store.fname_base = "cached-extrainfo";
02688 
02689     routerlist->desc_store.type = ROUTER_STORE;
02690     routerlist->extrainfo_store.type = EXTRAINFO_STORE;
02691 
02692     routerlist->desc_store.description = "router descriptors";
02693     routerlist->extrainfo_store.description = "extra-info documents";
02694   }
02695   return routerlist;
02696 }
02697 
02699 void
02700 routerinfo_free(routerinfo_t *router)
02701 {
02702   if (!router)
02703     return;
02704 
02705   tor_free(router->cache_info.signed_descriptor_body);
02706   tor_free(router->address);
02707   tor_free(router->nickname);
02708   tor_free(router->platform);
02709   tor_free(router->contact_info);
02710   if (router->onion_pkey)
02711     crypto_pk_free(router->onion_pkey);
02712   if (router->identity_pkey)
02713     crypto_pk_free(router->identity_pkey);
02714   if (router->declared_family) {
02715     SMARTLIST_FOREACH(router->declared_family, char *, s, tor_free(s));
02716     smartlist_free(router->declared_family);
02717   }
02718   addr_policy_list_free(router->exit_policy);
02719 
02720   memset(router, 77, sizeof(routerinfo_t));
02721 
02722   tor_free(router);
02723 }
02724 
02726 void
02727 extrainfo_free(extrainfo_t *extrainfo)
02728 {
02729   if (!extrainfo)
02730     return;
02731   tor_free(extrainfo->cache_info.signed_descriptor_body);
02732   tor_free(extrainfo->pending_sig);
02733 
02734   memset(extrainfo, 88, sizeof(extrainfo_t)); /* debug bad memory usage */
02735   tor_free(extrainfo);
02736 }
02737 
02739 static void
02740 signed_descriptor_free(signed_descriptor_t *sd)
02741 {
02742   if (!sd)
02743     return;
02744 
02745   tor_free(sd->signed_descriptor_body);
02746 
02747   memset(sd, 99, sizeof(signed_descriptor_t)); /* Debug bad mem usage */
02748   tor_free(sd);
02749 }
02750 
02754 static signed_descriptor_t *
02755 signed_descriptor_from_routerinfo(routerinfo_t *ri)
02756 {
02757   signed_descriptor_t *sd;
02758   tor_assert(ri->purpose == ROUTER_PURPOSE_GENERAL);
02759   sd = tor_malloc_zero(sizeof(signed_descriptor_t));
02760   memcpy(sd, &(ri->cache_info), sizeof(signed_descriptor_t));
02761   sd->routerlist_index = -1;
02762   ri->cache_info.signed_descriptor_body = NULL;
02763   routerinfo_free(ri);
02764   return sd;
02765 }
02766 
02768 static void
02769 _extrainfo_free(void *e)
02770 {
02771   extrainfo_free(e);
02772 }
02773 
02775 void
02776 routerlist_free(routerlist_t *rl)
02777 {
02778   if (!rl)
02779     return;
02780   rimap_free(rl->identity_map, NULL);
02781   sdmap_free(rl->desc_digest_map, NULL);
02782   sdmap_free(rl->desc_by_eid_map, NULL);
02783   eimap_free(rl->extra_info_map, _extrainfo_free);
02784   SMARTLIST_FOREACH(rl->routers, routerinfo_t *, r,
02785                     routerinfo_free(r));
02786   SMARTLIST_FOREACH(rl->old_routers, signed_descriptor_t *, sd,
02787                     signed_descriptor_free(sd));
02788   smartlist_free(rl->routers);
02789   smartlist_free(rl->old_routers);
02790   if (routerlist->desc_store.mmap)
02791     tor_munmap_file(routerlist->desc_store.mmap);
02792   if (routerlist->extrainfo_store.mmap)
02793     tor_munmap_file(routerlist->extrainfo_store.mmap);
02794   tor_free(rl);
02795 
02796   router_dir_info_changed();
02797 }
02798 
02801 void
02802 dump_routerlist_mem_usage(int severity)
02803 {
02804   uint64_t livedescs = 0;
02805   uint64_t olddescs = 0;
02806   if (!routerlist)
02807     return;
02808   SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, r,
02809                     livedescs += r->cache_info.signed_descriptor_len);
02810   SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd,
02811                     olddescs += sd->signed_descriptor_len);
02812 
02813   log(severity, LD_DIR,
02814       "In %d live descriptors: "U64_FORMAT" bytes.  "
02815       "In %d old descriptors: "U64_FORMAT" bytes.",
02816       smartlist_len(routerlist->routers), U64_PRINTF_ARG(livedescs),
02817       smartlist_len(routerlist->old_routers), U64_PRINTF_ARG(olddescs));
02818 }
02819 
02824 static INLINE int
02825 _routerlist_find_elt(smartlist_t *sl, void *ri, int idx)
02826 {
02827   if (idx < 0) {
02828     idx = -1;
02829     SMARTLIST_FOREACH(sl, routerinfo_t *, r,
02830                       if (r == ri) {
02831                         idx = r_sl_idx;
02832                         break;
02833                       });
02834   } else {
02835     tor_assert(idx < smartlist_len(sl));
02836     tor_assert(smartlist_get(sl, idx) == ri);
02837   };
02838   return idx;
02839 }
02840 
02846 static void
02847 routerlist_insert(routerlist_t *rl, routerinfo_t *ri)
02848 {
02849   routerinfo_t *ri_old;
02850   signed_descriptor_t *sd_old;
02851   {
02852     const routerinfo_t *ri_generated = router_get_my_routerinfo();
02853     tor_assert(ri_generated != ri);
02854   }
02855   tor_assert(ri->cache_info.routerlist_index == -1);
02856 
02857   ri_old = rimap_set(rl->identity_map, ri->cache_info.identity_digest, ri);
02858   tor_assert(!ri_old);
02859 
02860   sd_old = sdmap_set(rl->desc_digest_map,
02861                      ri->cache_info.signed_descriptor_digest,
02862                      &(ri->cache_info));
02863   if (sd_old) {
02864     int idx = sd_old->routerlist_index;
02865     sd_old->routerlist_index = -1;
02866     smartlist_del(rl->old_routers, idx);
02867     if (idx < smartlist_len(rl->old_routers)) {
02868        signed_descriptor_t *d = smartlist_get(rl->old_routers, idx);
02869        d->routerlist_index = idx;
02870     }
02871     rl->desc_store.bytes_dropped += sd_old->signed_descriptor_len;
02872     sdmap_remove(rl->desc_by_eid_map, sd_old->extra_info_digest);
02873     signed_descriptor_free(sd_old);
02874   }
02875 
02876   if (!tor_digest_is_zero(ri->cache_info.extra_info_digest))
02877     sdmap_set(rl->desc_by_eid_map, ri->cache_info.extra_info_digest,
02878               &ri->cache_info);
02879   smartlist_add(rl->routers, ri);
02880   ri->cache_info.routerlist_index = smartlist_len(rl->routers) - 1;
02881   nodelist_add_routerinfo(ri);
02882   router_dir_info_changed();
02883 #ifdef DEBUG_ROUTERLIST
02884   routerlist_assert_ok(rl);
02885 #endif
02886 }
02887 
02891 static int
02892 extrainfo_insert(routerlist_t *rl, extrainfo_t *ei)
02893 {
02894   int r = 0;
02895   routerinfo_t *ri = rimap_get(rl->identity_map,
02896                                ei->cache_info.identity_digest);
02897   signed_descriptor_t *sd =
02898     sdmap_get(rl->desc_by_eid_map, ei->cache_info.signed_descriptor_digest);
02899   extrainfo_t *ei_tmp;
02900 
02901   {
02902     extrainfo_t *ei_generated = router_get_my_extrainfo();
02903     tor_assert(ei_generated != ei);
02904   }
02905 
02906   if (!ri) {
02907     /* This router is unknown; we can't even verify the signature. Give up.*/
02908     goto done;
02909   }
02910   if (routerinfo_incompatible_with_extrainfo(ri, ei, sd, NULL)) {
02911     goto done;
02912   }
02913 
02914   /* Okay, if we make it here, we definitely have a router corresponding to
02915    * this extrainfo. */
02916 
02917   ei_tmp = eimap_set(rl->extra_info_map,
02918                      ei->cache_info.signed_descriptor_digest,
02919                      ei);
02920   r = 1;
02921   if (ei_tmp) {
02922     rl->extrainfo_store.bytes_dropped +=
02923       ei_tmp->cache_info.signed_descriptor_len;
02924     extrainfo_free(ei_tmp);
02925   }
02926 
02927  done:
02928   if (r == 0)
02929     extrainfo_free(ei);
02930 
02931 #ifdef DEBUG_ROUTERLIST
02932   routerlist_assert_ok(rl);
02933 #endif
02934   return r;
02935 }
02936 
02937 #define should_cache_old_descriptors() \
02938   directory_caches_dir_info(get_options())
02939 
02943 static void
02944 routerlist_insert_old(routerlist_t *rl, routerinfo_t *ri)
02945 {
02946   {
02947     const routerinfo_t *ri_generated = router_get_my_routerinfo();
02948     tor_assert(ri_generated != ri);
02949   }
02950   tor_assert(ri->cache_info.routerlist_index == -1);
02951 
02952   if (should_cache_old_descriptors() &&
02953       ri->purpose == ROUTER_PURPOSE_GENERAL &&
02954       !sdmap_get(rl->desc_digest_map,
02955                  ri->cache_info.signed_descriptor_digest)) {
02956     signed_descriptor_t *sd = signed_descriptor_from_routerinfo(ri);
02957     sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
02958     smartlist_add(rl->old_routers, sd);
02959     sd->routerlist_index = smartlist_len(rl->old_routers)-1;
02960     if (!tor_digest_is_zero(sd->extra_info_digest))
02961       sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
02962   } else {
02963     routerinfo_free(ri);
02964   }
02965 #ifdef DEBUG_ROUTERLIST
02966   routerlist_assert_ok(rl);
02967 #endif
02968 }
02969 
02978 void
02979 routerlist_remove(routerlist_t *rl, routerinfo_t *ri, int make_old, time_t now)
02980 {
02981   routerinfo_t *ri_tmp;
02982   extrainfo_t *ei_tmp;
02983   int idx = ri->cache_info.routerlist_index;
02984   tor_assert(0 <= idx && idx < smartlist_len(rl->routers));
02985   tor_assert(smartlist_get(rl->routers, idx) == ri);
02986 
02987   nodelist_remove_routerinfo(ri);
02988 
02989   /* make sure the rephist module knows that it's not running */
02990   rep_hist_note_router_unreachable(ri->cache_info.identity_digest, now);
02991 
02992   ri->cache_info.routerlist_index = -1;
02993   smartlist_del(rl->routers, idx);
02994   if (idx < smartlist_len(rl->routers)) {
02995     routerinfo_t *r = smartlist_get(rl->routers, idx);
02996     r->cache_info.routerlist_index = idx;
02997   }
02998 
02999   ri_tmp = rimap_remove(rl->identity_map, ri->cache_info.identity_digest);
03000   router_dir_info_changed();
03001   tor_assert(ri_tmp == ri);
03002 
03003   if (make_old && should_cache_old_descriptors() &&
03004       ri->purpose == ROUTER_PURPOSE_GENERAL) {
03005     signed_descriptor_t *sd;
03006     sd = signed_descriptor_from_routerinfo(ri);
03007     smartlist_add(rl->old_routers, sd);
03008     sd->routerlist_index = smartlist_len(rl->old_routers)-1;
03009     sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
03010     if (!tor_digest_is_zero(sd->extra_info_digest))
03011       sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
03012   } else {
03013     signed_descriptor_t *sd_tmp;
03014     sd_tmp = sdmap_remove(rl->desc_digest_map,
03015                           ri->cache_info.signed_descriptor_digest);
03016     tor_assert(sd_tmp == &(ri->cache_info));
03017     rl->desc_store.bytes_dropped += ri->cache_info.signed_descriptor_len;
03018     ei_tmp = eimap_remove(rl->extra_info_map,
03019                           ri->cache_info.extra_info_digest);
03020     if (ei_tmp) {
03021       rl->extrainfo_store.bytes_dropped +=
03022         ei_tmp->cache_info.signed_descriptor_len;
03023       extrainfo_free(ei_tmp);
03024     }
03025     if (!tor_digest_is_zero(ri->cache_info.extra_info_digest))
03026       sdmap_remove(rl->desc_by_eid_map, ri->cache_info.extra_info_digest);
03027     routerinfo_free(ri);
03028   }
03029 #ifdef DEBUG_ROUTERLIST
03030   routerlist_assert_ok(rl);
03031 #endif
03032 }
03033 
03037 static void
03038 routerlist_remove_old(routerlist_t *rl, signed_descriptor_t *sd, int idx)
03039 {
03040   signed_descriptor_t *sd_tmp;
03041   extrainfo_t *ei_tmp;
03042   desc_store_t *store;
03043   if (idx == -1) {
03044     idx = sd->routerlist_index;
03045   }
03046   tor_assert(0 <= idx && idx < smartlist_len(rl->old_routers));
03047   /* XXXX edmanm's bridge relay triggered the following assert while
03048    * running 0.2.0.12-alpha.  If anybody triggers this again, see if we
03049    * can get a backtrace. */
03050   tor_assert(smartlist_get(rl->old_routers, idx) == sd);
03051   tor_assert(idx == sd->routerlist_index);
03052 
03053   sd->routerlist_index = -1;
03054   smartlist_del(rl->old_routers, idx);
03055   if (idx < smartlist_len(rl->old_routers)) {
03056     signed_descriptor_t *d = smartlist_get(rl->old_routers, idx);
03057     d->routerlist_index = idx;
03058   }
03059   sd_tmp = sdmap_remove(rl->desc_digest_map,
03060                         sd->signed_descriptor_digest);
03061   tor_assert(sd_tmp == sd);
03062   store = desc_get_store(rl, sd);
03063   if (store)
03064     store->bytes_dropped += sd->signed_descriptor_len;
03065 
03066   ei_tmp = eimap_remove(rl->extra_info_map,
03067                         sd->extra_info_digest);
03068   if (ei_tmp) {
03069     rl->extrainfo_store.bytes_dropped +=
03070       ei_tmp->cache_info.signed_descriptor_len;
03071     extrainfo_free(ei_tmp);
03072   }
03073   if (!tor_digest_is_zero(sd->extra_info_digest))
03074     sdmap_remove(rl->desc_by_eid_map, sd->extra_info_digest);
03075 
03076   signed_descriptor_free(sd);
03077 #ifdef DEBUG_ROUTERLIST
03078   routerlist_assert_ok(rl);
03079 #endif
03080 }
03081 
03090 static void
03091 routerlist_replace(routerlist_t *rl, routerinfo_t *ri_old,
03092                    routerinfo_t *ri_new)
03093 {
03094   int idx;
03095   int same_descriptors;
03096 
03097   routerinfo_t *ri_tmp;
03098   extrainfo_t *ei_tmp;
03099   {
03100     const routerinfo_t *ri_generated = router_get_my_routerinfo();
03101     tor_assert(ri_generated != ri_new);
03102   }
03103   tor_assert(ri_old != ri_new);
03104   tor_assert(ri_new->cache_info.routerlist_index == -1);
03105 
03106   idx = ri_old->cache_info.routerlist_index;
03107   tor_assert(0 <= idx && idx < smartlist_len(rl->routers));
03108   tor_assert(smartlist_get(rl->routers, idx) == ri_old);
03109 
03110   nodelist_remove_routerinfo(ri_old);
03111   nodelist_add_routerinfo(ri_new);
03112 
03113   router_dir_info_changed();
03114   if (idx >= 0) {
03115     smartlist_set(rl->routers, idx, ri_new);
03116     ri_old->cache_info.routerlist_index = -1;
03117     ri_new->cache_info.routerlist_index = idx;
03118     /* Check that ri_old is not in rl->routers anymore: */
03119     tor_assert( _routerlist_find_elt(rl->routers, ri_old, -1) == -1 );
03120   } else {
03121     log_warn(LD_BUG, "Appending entry from routerlist_replace.");
03122     routerlist_insert(rl, ri_new);
03123     return;
03124   }
03125   if (tor_memneq(ri_old->cache_info.identity_digest,
03126              ri_new->cache_info.identity_digest, DIGEST_LEN)) {
03127     /* digests don't match; digestmap_set won't replace */
03128     rimap_remove(rl->identity_map, ri_old->cache_info.identity_digest);
03129   }
03130   ri_tmp = rimap_set(rl->identity_map,
03131                      ri_new->cache_info.identity_digest, ri_new);
03132   tor_assert(!ri_tmp || ri_tmp == ri_old);
03133   sdmap_set(rl->desc_digest_map,
03134             ri_new->cache_info.signed_descriptor_digest,
03135             &(ri_new->cache_info));
03136 
03137   if (!tor_digest_is_zero(ri_new->cache_info.extra_info_digest)) {
03138     sdmap_set(rl->desc_by_eid_map, ri_new->cache_info.extra_info_digest,
03139               &ri_new->cache_info);
03140   }
03141 
03142   same_descriptors = tor_memeq(ri_old->cache_info.signed_descriptor_digest,
03143                               ri_new->cache_info.signed_descriptor_digest,
03144                               DIGEST_LEN);
03145 
03146   if (should_cache_old_descriptors() &&
03147       ri_old->purpose == ROUTER_PURPOSE_GENERAL &&
03148       !same_descriptors) {
03149     /* ri_old is going to become a signed_descriptor_t and go into
03150      * old_routers */
03151     signed_descriptor_t *sd = signed_descriptor_from_routerinfo(ri_old);
03152     smartlist_add(rl->old_routers, sd);
03153     sd->routerlist_index = smartlist_len(rl->old_routers)-1;
03154     sdmap_set(rl->desc_digest_map, sd->signed_descriptor_digest, sd);
03155     if (!tor_digest_is_zero(sd->extra_info_digest))
03156       sdmap_set(rl->desc_by_eid_map, sd->extra_info_digest, sd);
03157   } else {
03158     /* We're dropping ri_old. */
03159     if (!same_descriptors) {
03160       /* digests don't match; The sdmap_set above didn't replace */
03161       sdmap_remove(rl->desc_digest_map,
03162                    ri_old->cache_info.signed_descriptor_digest);
03163 
03164       if (tor_memneq(ri_old->cache_info.extra_info_digest,
03165                  ri_new->cache_info.extra_info_digest, DIGEST_LEN)) {
03166         ei_tmp = eimap_remove(rl->extra_info_map,
03167                               ri_old->cache_info.extra_info_digest);
03168         if (ei_tmp) {
03169           rl->extrainfo_store.bytes_dropped +=
03170             ei_tmp->cache_info.signed_descriptor_len;
03171           extrainfo_free(ei_tmp);
03172         }
03173       }
03174 
03175       if (!tor_digest_is_zero(ri_old->cache_info.extra_info_digest)) {
03176         sdmap_remove(rl->desc_by_eid_map,
03177                      ri_old->cache_info.extra_info_digest);
03178       }
03179     }
03180     rl->desc_store.bytes_dropped += ri_old->cache_info.signed_descriptor_len;
03181     routerinfo_free(ri_old);
03182   }
03183 #ifdef DEBUG_ROUTERLIST
03184   routerlist_assert_ok(rl);
03185 #endif
03186 }
03187 
03190 static routerinfo_t *
03191 routerlist_reparse_old(routerlist_t *rl, signed_descriptor_t *sd)
03192 {
03193   routerinfo_t *ri;
03194   const char *body;
03195 
03196   body = signed_descriptor_get_annotations(sd);
03197 
03198   ri = router_parse_entry_from_string(body,
03199                          body+sd->signed_descriptor_len+sd->annotations_len,
03200                          0, 1, NULL);
03201   if (!ri)
03202     return NULL;
03203   memcpy(&ri->cache_info, sd, sizeof(signed_descriptor_t));
03204   sd->signed_descriptor_body = NULL; /* Steal reference. */
03205   ri->cache_info.routerlist_index = -1;
03206 
03207   routerlist_remove_old(rl, sd, -1);
03208 
03209   return ri;
03210 }
03211 
03213 void
03214 routerlist_free_all(void)
03215 {
03216   routerlist_free(routerlist);
03217   routerlist = NULL;
03218   if (warned_nicknames) {
03219     SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp));
03220     smartlist_free(warned_nicknames);
03221     warned_nicknames = NULL;
03222   }
03223   if (trusted_dir_servers) {
03224     SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ds,
03225                       trusted_dir_server_free(ds));
03226     smartlist_free(trusted_dir_servers);
03227     trusted_dir_servers = NULL;
03228   }
03229   if (trusted_dir_certs) {
03230     DIGESTMAP_FOREACH(trusted_dir_certs, key, cert_list_t *, cl) {
03231       SMARTLIST_FOREACH(cl->certs, authority_cert_t *, cert,
03232                         authority_cert_free(cert));
03233       smartlist_free(cl->certs);
03234       tor_free(cl);
03235     } DIGESTMAP_FOREACH_END;
03236     digestmap_free(trusted_dir_certs, NULL);
03237     trusted_dir_certs = NULL;
03238   }
03239 }
03240 
03243 void
03244 routerlist_reset_warnings(void)
03245 {
03246   if (!warned_nicknames)
03247     warned_nicknames = smartlist_new();
03248   SMARTLIST_FOREACH(warned_nicknames, char *, cp, tor_free(cp));
03249   smartlist_clear(warned_nicknames); /* now the list is empty. */
03250 
03251   networkstatus_reset_warnings();
03252 }
03253 
03256 void
03257 router_set_status(const char *digest, int up)
03258 {
03259   node_t *node;
03260   tor_assert(digest);
03261 
03262   SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, d,
03263                     if (tor_memeq(d->digest, digest, DIGEST_LEN))
03264                       d->is_running = up);
03265 
03266   node = node_get_mutable_by_id(digest);
03267   if (node) {
03268 #if 0
03269     log_debug(LD_DIR,"Marking router %s as %s.",
03270               node_describe(node), up ? "up" : "down");
03271 #endif
03272     if (!up && node_is_me(node) && !net_is_disabled())
03273       log_warn(LD_NET, "We just marked ourself as down. Are your external "
03274                "addresses reachable?");
03275     node->is_running = up;
03276   }
03277 
03278   router_dir_info_changed();
03279 }
03280 
03301 was_router_added_t
03302 router_add_to_routerlist(routerinfo_t *router, const char **msg,
03303                          int from_cache, int from_fetch)
03304 {
03305   const char *id_digest;
03306   const or_options_t *options = get_options();
03307   int authdir = authdir_mode_handles_descs(options, router->purpose);
03308   int authdir_believes_valid = 0;
03309   routerinfo_t *old_router;
03310   networkstatus_t *consensus =
03311     networkstatus_get_latest_consensus_by_flavor(FLAV_NS);
03312   const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
03313   int in_consensus = 0;
03314 
03315   tor_assert(msg);
03316 
03317   if (!routerlist)
03318     router_get_routerlist();
03319 
03320   id_digest = router->cache_info.identity_digest;
03321 
03322   old_router = router_get_mutable_by_digest(id_digest);
03323 
03324   /* Make sure that we haven't already got this exact descriptor. */
03325   if (sdmap_get(routerlist->desc_digest_map,
03326                 router->cache_info.signed_descriptor_digest)) {
03327     /* If we have this descriptor already and the new descriptor is a bridge
03328      * descriptor, replace it. If we had a bridge descriptor before and the
03329      * new one is not a bridge descriptor, don't replace it. */
03330 
03331     /* Only members of routerlist->identity_map can be bridges; we don't
03332      * put bridges in old_routers. */
03333     const int was_bridge = old_router &&
03334       old_router->purpose == ROUTER_PURPOSE_BRIDGE;
03335 
03336     if (routerinfo_is_a_configured_bridge(router) &&
03337         router->purpose == ROUTER_PURPOSE_BRIDGE &&
03338         !was_bridge) {
03339       log_info(LD_DIR, "Replacing non-bridge descriptor with bridge "
03340                "descriptor for router %s",
03341                router_describe(router));
03342     } else {
03343       log_info(LD_DIR,
03344                "Dropping descriptor that we already have for router %s",
03345                router_describe(router));
03346       *msg = "Router descriptor was not new.";
03347       routerinfo_free(router);
03348       return ROUTER_WAS_NOT_NEW;
03349     }
03350   }
03351 
03352   if (authdir) {
03353     if (authdir_wants_to_reject_router(router, msg,
03354                                        !from_cache && !from_fetch,
03355                                        &authdir_believes_valid)) {
03356       tor_assert(*msg);
03357       routerinfo_free(router);
03358       return ROUTER_AUTHDIR_REJECTS;
03359     }
03360   } else if (from_fetch) {
03361     /* Only check the descriptor digest against the network statuses when
03362      * we are receiving in response to a fetch. */
03363 
03364     if (!signed_desc_digest_is_recognized(&router->cache_info) &&
03365         !routerinfo_is_a_configured_bridge(router)) {
03366       /* We asked for it, so some networkstatus must have listed it when we
03367        * did.  Save it if we're a cache in case somebody else asks for it. */
03368       log_info(LD_DIR,
03369                "Received a no-longer-recognized descriptor for router %s",
03370                router_describe(router));
03371       *msg = "Router descriptor is not referenced by any network-status.";
03372 
03373       /* Only journal this desc if we'll be serving it. */
03374       if (!from_cache && should_cache_old_descriptors())
03375         signed_desc_append_to_journal(&router->cache_info,
03376                                       &routerlist->desc_store);
03377       routerlist_insert_old(routerlist, router);
03378       return ROUTER_NOT_IN_CONSENSUS_OR_NETWORKSTATUS;
03379     }
03380   }
03381 
03382   /* We no longer need a router with this descriptor digest. */
03383   SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
03384   {
03385     routerstatus_t *rs =
03386       networkstatus_v2_find_mutable_entry(ns, id_digest);
03387     if (rs && tor_memeq(rs->descriptor_digest,
03388                       router->cache_info.signed_descriptor_digest,
03389                       DIGEST_LEN))
03390       rs->need_to_mirror = 0;
03391   });
03392   if (consensus) {
03393     routerstatus_t *rs = networkstatus_vote_find_mutable_entry(
03394                                                      consensus, id_digest);
03395     if (rs && tor_memeq(rs->descriptor_digest,
03396                       router->cache_info.signed_descriptor_digest,
03397                       DIGEST_LEN)) {
03398       in_consensus = 1;
03399       rs->need_to_mirror = 0;
03400     }
03401   }
03402 
03403   if (router->purpose == ROUTER_PURPOSE_GENERAL &&
03404       consensus && !in_consensus && !authdir) {
03405     /* If it's a general router not listed in the consensus, then don't
03406      * consider replacing the latest router with it. */
03407     if (!from_cache && should_cache_old_descriptors())
03408       signed_desc_append_to_journal(&router->cache_info,
03409                                     &routerlist->desc_store);
03410     routerlist_insert_old(routerlist, router);
03411     *msg = "Skipping router descriptor: not in consensus.";
03412     return ROUTER_NOT_IN_CONSENSUS;
03413   }
03414 
03415   /* If we're reading a bridge descriptor from our cache, and we don't
03416    * recognize it as one of our currently configured bridges, drop the
03417    * descriptor. Otherwise we could end up using it as one of our entry
03418    * guards even if it isn't in our Bridge config lines. */
03419   if (router->purpose == ROUTER_PURPOSE_BRIDGE && from_cache &&
03420       !authdir_mode_bridge(options) &&
03421       !routerinfo_is_a_configured_bridge(router)) {
03422     log_info(LD_DIR, "Dropping bridge descriptor for %s because we have "
03423              "no bridge configured at that address.",
03424              safe_str_client(router_describe(router)));
03425     *msg = "Router descriptor was not a configured bridge.";
03426     routerinfo_free(router);
03427     return ROUTER_WAS_NOT_WANTED;
03428   }
03429 
03430   /* If we have a router with the same identity key, choose the newer one. */
03431   if (old_router) {
03432     if (!in_consensus && (router->cache_info.published_on <=
03433                           old_router->cache_info.published_on)) {
03434       /* Same key, but old.  This one is not listed in the consensus. */
03435       log_debug(LD_DIR, "Not-new descriptor for router %s",
03436                 router_describe(router));
03437       /* Only journal this desc if we'll be serving it. */
03438       if (!from_cache && should_cache_old_descriptors())
03439         signed_desc_append_to_journal(&router->cache_info,
03440                                       &routerlist->desc_store);
03441       routerlist_insert_old(routerlist, router);
03442       *msg = "Router descriptor was not new.";
03443       return ROUTER_WAS_NOT_NEW;
03444     } else {
03445       /* Same key, and either new, or listed in the consensus. */
03446       log_debug(LD_DIR, "Replacing entry for router %s",
03447                 router_describe(router));
03448       if (routers_have_same_or_addr(router, old_router)) {
03449         /* these carry over when the address and orport are unchanged. */
03450         router->last_reachable = old_router->last_reachable;
03451         router->testing_since = old_router->testing_since;
03452       }
03453       routerlist_replace(routerlist, old_router, router);
03454       if (!from_cache) {
03455         signed_desc_append_to_journal(&router->cache_info,
03456                                       &routerlist->desc_store);
03457       }
03458       directory_set_dirty();
03459       *msg = authdir_believes_valid ? "Valid server updated" :
03460         ("Invalid server updated. (This dirserver is marking your "
03461          "server as unapproved.)");
03462       return ROUTER_ADDED_SUCCESSFULLY;
03463     }
03464   }
03465 
03466   if (!in_consensus && from_cache &&
03467       router->cache_info.published_on < time(NULL) - OLD_ROUTER_DESC_MAX_AGE) {
03468     *msg = "Router descriptor was really old.";
03469     routerinfo_free(router);
03470     return ROUTER_WAS_NOT_NEW;
03471   }
03472 
03473   /* We haven't seen a router with this identity before. Add it to the end of
03474    * the list. */
03475   routerlist_insert(routerlist, router);
03476   if (!from_cache) {
03477     signed_desc_append_to_journal(&router->cache_info,
03478                                   &routerlist->desc_store);
03479   }
03480   directory_set_dirty();
03481   return ROUTER_ADDED_SUCCESSFULLY;
03482 }
03483 
03488 was_router_added_t
03489 router_add_extrainfo_to_routerlist(extrainfo_t *ei, const char **msg,
03490                                    int from_cache, int from_fetch)
03491 {
03492   int inserted;
03493   (void)from_fetch;
03494   if (msg) *msg = NULL;
03495   /*XXXX023 Do something with msg */
03496 
03497   inserted = extrainfo_insert(router_get_routerlist(), ei);
03498 
03499   if (inserted && !from_cache)
03500     signed_desc_append_to_journal(&ei->cache_info,
03501                                   &routerlist->extrainfo_store);
03502 
03503   if (inserted)
03504     return ROUTER_ADDED_SUCCESSFULLY;
03505   else
03506     return ROUTER_BAD_EI;
03507 }
03508 
03512 static int
03513 _compare_old_routers_by_identity(const void **_a, const void **_b)
03514 {
03515   int i;
03516   const signed_descriptor_t *r1 = *_a, *r2 = *_b;
03517   if ((i = fast_memcmp(r1->identity_digest, r2->identity_digest, DIGEST_LEN)))
03518     return i;
03519   return (int)(r1->published_on - r2->published_on);
03520 }
03521 
03525 struct duration_idx_t {
03526   int duration;
03527   int idx;
03528   int old;
03529 };
03530 
03532 static int
03533 _compare_duration_idx(const void *_d1, const void *_d2)
03534 {
03535   const struct duration_idx_t *d1 = _d1;
03536   const struct duration_idx_t *d2 = _d2;
03537   return d1->duration - d2->duration;
03538 }
03539 
03548 static void
03549 routerlist_remove_old_cached_routers_with_id(time_t now,
03550                                              time_t cutoff, int lo, int hi,
03551                                              digestset_t *retain)
03552 {
03553   int i, n = hi-lo+1;
03554   unsigned n_extra, n_rmv = 0;
03555   struct duration_idx_t *lifespans;
03556   uint8_t *rmv, *must_keep;
03557   smartlist_t *lst = routerlist->old_routers;
03558 #if 1
03559   const char *ident;
03560   tor_assert(hi < smartlist_len(lst));
03561   tor_assert(lo <= hi);
03562   ident = ((signed_descriptor_t*)smartlist_get(lst, lo))->identity_digest;
03563   for (i = lo+1; i <= hi; ++i) {
03564     signed_descriptor_t *r = smartlist_get(lst, i);
03565     tor_assert(tor_memeq(ident, r->identity_digest, DIGEST_LEN));
03566   }
03567 #endif
03568   /* Check whether we need to do anything at all. */
03569   {
03570     int mdpr = directory_caches_dir_info(get_options()) ? 2 : 1;
03571     if (n <= mdpr)
03572       return;
03573     n_extra = n - mdpr;
03574   }
03575 
03576   lifespans = tor_malloc_zero(sizeof(struct duration_idx_t)*n);
03577   rmv = tor_malloc_zero(sizeof(uint8_t)*n);
03578   must_keep = tor_malloc_zero(sizeof(uint8_t)*n);
03579   /* Set lifespans to contain the lifespan and index of each server. */
03580   /* Set rmv[i-lo]=1 if we're going to remove a server for being too old. */
03581   for (i = lo; i <= hi; ++i) {
03582     signed_descriptor_t *r = smartlist_get(lst, i);
03583     signed_descriptor_t *r_next;
03584     lifespans[i-lo].idx = i;
03585     if (r->last_listed_as_valid_until >= now ||
03586         (retain && digestset_isin(retain, r->signed_descriptor_digest))) {
03587       must_keep[i-lo] = 1;
03588     }
03589     if (i < hi) {
03590       r_next = smartlist_get(lst, i+1);
03591       tor_assert(r->published_on <= r_next->published_on);
03592       lifespans[i-lo].duration = (int)(r_next->published_on - r->published_on);
03593     } else {
03594       r_next = NULL;
03595       lifespans[i-lo].duration = INT_MAX;
03596     }
03597     if (!must_keep[i-lo] && r->published_on < cutoff && n_rmv < n_extra) {
03598       ++n_rmv;
03599       lifespans[i-lo].old = 1;
03600       rmv[i-lo] = 1;
03601     }
03602   }
03603 
03604   if (n_rmv < n_extra) {
03610     qsort(lifespans, n, sizeof(struct duration_idx_t), _compare_duration_idx);
03611     for (i = 0; i < n && n_rmv < n_extra; ++i) {
03612       if (!must_keep[lifespans[i].idx-lo] && !lifespans[i].old) {
03613         rmv[lifespans[i].idx-lo] = 1;
03614         ++n_rmv;
03615       }
03616     }
03617   }
03618 
03619   i = hi;
03620   do {
03621     if (rmv[i-lo])
03622       routerlist_remove_old(routerlist, smartlist_get(lst, i), i);
03623   } while (--i >= lo);
03624   tor_free(must_keep);
03625   tor_free(rmv);
03626   tor_free(lifespans);
03627 }
03628 
03633 void
03634 routerlist_remove_old_routers(void)
03635 {
03636   int i, hi=-1;
03637   const char *cur_id = NULL;
03638   time_t now = time(NULL);
03639   time_t cutoff;
03640   routerinfo_t *router;
03641   signed_descriptor_t *sd;
03642   digestset_t *retain;
03643   int caches = directory_caches_dir_info(get_options());
03644   const networkstatus_t *consensus = networkstatus_get_latest_consensus();
03645   const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
03646   int have_enough_v2;
03647   const or_options_t *options = get_options();
03648 
03649   trusted_dirs_remove_old_certs();
03650 
03651   if (!routerlist || !consensus)
03652     return;
03653 
03654   // routerlist_assert_ok(routerlist);
03655 
03656   /* We need to guess how many router descriptors we will wind up wanting to
03657      retain, so that we can be sure to allocate a large enough Bloom filter
03658      to hold the digest set.  Overestimating is fine; underestimating is bad.
03659   */
03660   {
03661     /* We'll probably retain everything in the consensus. */
03662     int n_max_retain = smartlist_len(consensus->routerstatus_list);
03663     if (caches && networkstatus_v2_list) {
03664       /* If we care about v2 statuses, we'll retain at most as many as are
03665          listed any of the v2 statues.  This will be at least the length of
03666          the largest v2 networkstatus, and in the worst case, this set will be
03667          equal to the sum of the lengths of all v2 consensuses.  Take the
03668          worst case.
03669       */
03670       SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
03671                         n_max_retain += smartlist_len(ns->entries));
03672     }
03673     retain = digestset_new(n_max_retain);
03674   }
03675 
03676   cutoff = now - OLD_ROUTER_DESC_MAX_AGE;
03677   /* Build a list of all the descriptors that _anybody_ lists. */
03678   if (caches && networkstatus_v2_list) {
03679     SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
03680     {
03681       /* XXXX The inner loop here gets pretty expensive, and actually shows up
03682        * on some profiles.  It may be the reason digestmap_set shows up in
03683        * profiles too.  If instead we kept a per-descriptor digest count of
03684        * how many networkstatuses recommended each descriptor, and changed
03685        * that only when the networkstatuses changed, that would be a speed
03686        * improvement, possibly 1-4% if it also removes digestmap_set from the
03687        * profile.  Not worth it for 0.1.2.x, though.  The new directory
03688        * system will obsolete this whole thing in 0.2.0.x. */
03689       SMARTLIST_FOREACH(ns->entries, routerstatus_t *, rs,
03690         if (rs->published_on >= cutoff)
03691           digestset_add(retain, rs->descriptor_digest));
03692     });
03693   }
03694 
03695   /* Retain anything listed in the consensus. */
03696   if (consensus) {
03697     SMARTLIST_FOREACH(consensus->routerstatus_list, routerstatus_t *, rs,
03698         if (rs->published_on >= cutoff)
03699           digestset_add(retain, rs->descriptor_digest));
03700   }
03701 
03702   /* If we have a consensus, and nearly as many v2 networkstatuses as we want,
03703    * we should consider pruning current routers that are too old and that
03704    * nobody recommends.  (If we don't have a consensus or enough v2
03705    * networkstatuses, then we should get more before we decide to kill
03706    * routers.) */
03707   /* we set this to true iff we don't care about v2 info, or we have enough. */
03708   have_enough_v2 = !caches ||
03709     !(authdir_mode_any_main(options) || options->FetchV2Networkstatus) ||
03710     (networkstatus_v2_list &&
03711      smartlist_len(networkstatus_v2_list) > get_n_v2_authorities() / 2);
03712 
03713   if (have_enough_v2 && consensus) {
03714     cutoff = now - ROUTER_MAX_AGE;
03715     /* Remove too-old unrecommended members of routerlist->routers. */
03716     for (i = 0; i < smartlist_len(routerlist->routers); ++i) {
03717       router = smartlist_get(routerlist->routers, i);
03718       if (router->cache_info.published_on <= cutoff &&
03719           router->cache_info.last_listed_as_valid_until < now &&
03720           !digestset_isin(retain,
03721                           router->cache_info.signed_descriptor_digest)) {
03722         /* Too old: remove it.  (If we're a cache, just move it into
03723          * old_routers.) */
03724         log_info(LD_DIR,
03725                  "Forgetting obsolete (too old) routerinfo for router %s",
03726                  router_describe(router));
03727         routerlist_remove(routerlist, router, 1, now);
03728         i--;
03729       }
03730     }
03731   }
03732 
03733   //routerlist_assert_ok(routerlist);
03734 
03735   /* Remove far-too-old members of routerlist->old_routers. */
03736   cutoff = now - OLD_ROUTER_DESC_MAX_AGE;
03737   for (i = 0; i < smartlist_len(routerlist->old_routers); ++i) {
03738     sd = smartlist_get(routerlist->old_routers, i);
03739     if (sd->published_on <= cutoff &&
03740         sd->last_listed_as_valid_until < now &&
03741         !digestset_isin(retain, sd->signed_descriptor_digest)) {
03742       /* Too old.  Remove it. */
03743       routerlist_remove_old(routerlist, sd, i--);
03744     }
03745   }
03746 
03747   //routerlist_assert_ok(routerlist);
03748 
03749   log_info(LD_DIR, "We have %d live routers and %d old router descriptors.",
03750            smartlist_len(routerlist->routers),
03751            smartlist_len(routerlist->old_routers));
03752 
03753   /* Now we might have to look at routerlist->old_routers for extraneous
03754    * members. (We'd keep all the members if we could, but we need to save
03755    * space.) First, check whether we have too many router descriptors, total.
03756    * We're okay with having too many for some given router, so long as the
03757    * total number doesn't approach max_descriptors_per_router()*len(router).
03758    */
03759   if (smartlist_len(routerlist->old_routers) <
03760       smartlist_len(routerlist->routers))
03761     goto done;
03762 
03763   /* Sort by identity, then fix indices. */
03764   smartlist_sort(routerlist->old_routers, _compare_old_routers_by_identity);
03765   /* Fix indices. */
03766   for (i = 0; i < smartlist_len(routerlist->old_routers); ++i) {
03767     signed_descriptor_t *r = smartlist_get(routerlist->old_routers, i);
03768     r->routerlist_index = i;
03769   }
03770 
03771   /* Iterate through the list from back to front, so when we remove descriptors
03772    * we don't mess up groups we haven't gotten to. */
03773   for (i = smartlist_len(routerlist->old_routers)-1; i >= 0; --i) {
03774     signed_descriptor_t *r = smartlist_get(routerlist->old_routers, i);
03775     if (!cur_id) {
03776       cur_id = r->identity_digest;
03777       hi = i;
03778     }
03779     if (tor_memneq(cur_id, r->identity_digest, DIGEST_LEN)) {
03780       routerlist_remove_old_cached_routers_with_id(now,
03781                                                    cutoff, i+1, hi, retain);
03782       cur_id = r->identity_digest;
03783       hi = i;
03784     }
03785   }
03786   if (hi>=0)
03787     routerlist_remove_old_cached_routers_with_id(now, cutoff, 0, hi, retain);
03788   //routerlist_assert_ok(routerlist);
03789 
03790  done:
03791   digestset_free(retain);
03792   router_rebuild_store(RRS_DONT_REMOVE_OLD, &routerlist->desc_store);
03793   router_rebuild_store(RRS_DONT_REMOVE_OLD,&routerlist->extrainfo_store);
03794 }
03795 
03798 void
03799 routerlist_descriptors_added(smartlist_t *sl, int from_cache)
03800 {
03801   tor_assert(sl);
03802   control_event_descriptors_changed(sl);
03803   SMARTLIST_FOREACH_BEGIN(sl, routerinfo_t *, ri) {
03804     if (ri->purpose == ROUTER_PURPOSE_BRIDGE)
03805       learned_bridge_descriptor(ri, from_cache);
03806     if (ri->needs_retest_if_added) {
03807       ri->needs_retest_if_added = 0;
03808       dirserv_single_reachability_test(approx_time(), ri);
03809     }
03810   } SMARTLIST_FOREACH_END(ri);
03811 }
03812 
03825 int
03826 router_load_single_router(const char *s, uint8_t purpose, int cache,
03827                           const char **msg)
03828 {
03829   routerinfo_t *ri;
03830   was_router_added_t r;
03831   smartlist_t *lst;
03832   char annotation_buf[ROUTER_ANNOTATION_BUF_LEN];
03833   tor_assert(msg);
03834   *msg = NULL;
03835 
03836   tor_snprintf(annotation_buf, sizeof(annotation_buf),
03837                "@source controller\n"
03838                "@purpose %s\n", router_purpose_to_string(purpose));
03839 
03840   if (!(ri = router_parse_entry_from_string(s, NULL, 1, 0, annotation_buf))) {
03841     log_warn(LD_DIR, "Error parsing router descriptor; dropping.");
03842     *msg = "Couldn't parse router descriptor.";
03843     return -1;
03844   }
03845   tor_assert(ri->purpose == purpose);
03846   if (router_is_me(ri)) {
03847     log_warn(LD_DIR, "Router's identity key matches mine; dropping.");
03848     *msg = "Router's identity key matches mine.";
03849     routerinfo_free(ri);
03850     return 0;
03851   }
03852 
03853   if (!cache) /* obey the preference of the controller */
03854     ri->cache_info.do_not_cache = 1;
03855 
03856   lst = smartlist_new();
03857   smartlist_add(lst, ri);
03858   routers_update_status_from_consensus_networkstatus(lst, 0);
03859 
03860   r = router_add_to_routerlist(ri, msg, 0, 0);
03861   if (!WRA_WAS_ADDED(r)) {
03862     /* we've already assigned to *msg now, and ri is already freed */
03863     tor_assert(*msg);
03864     if (r == ROUTER_AUTHDIR_REJECTS)
03865       log_warn(LD_DIR, "Couldn't add router to list: %s Dropping.", *msg);
03866     smartlist_free(lst);
03867     return 0;
03868   } else {
03869     routerlist_descriptors_added(lst, 0);
03870     smartlist_free(lst);
03871     log_debug(LD_DIR, "Added router to list");
03872     return 1;
03873   }
03874 }
03875 
03891 int
03892 router_load_routers_from_string(const char *s, const char *eos,
03893                                 saved_location_t saved_location,
03894                                 smartlist_t *requested_fingerprints,
03895                                 int descriptor_digests,
03896                                 const char *prepend_annotations)
03897 {
03898   smartlist_t *routers = smartlist_new(), *changed = smartlist_new();
03899   char fp[HEX_DIGEST_LEN+1];
03900   const char *msg;
03901   int from_cache = (saved_location != SAVED_NOWHERE);
03902   int allow_annotations = (saved_location != SAVED_NOWHERE);
03903   int any_changed = 0;
03904 
03905   router_parse_list_from_string(&s, eos, routers, saved_location, 0,
03906                                 allow_annotations, prepend_annotations);
03907 
03908   routers_update_status_from_consensus_networkstatus(routers, !from_cache);
03909 
03910   log_info(LD_DIR, "%d elements to add", smartlist_len(routers));
03911 
03912   SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) {
03913     was_router_added_t r;
03914     char d[DIGEST_LEN];
03915     if (requested_fingerprints) {
03916       base16_encode(fp, sizeof(fp), descriptor_digests ?
03917                       ri->cache_info.signed_descriptor_digest :
03918                       ri->cache_info.identity_digest,
03919                     DIGEST_LEN);
03920       if (smartlist_string_isin(requested_fingerprints, fp)) {
03921         smartlist_string_remove(requested_fingerprints, fp);
03922       } else {
03923         char *requested =
03924           smartlist_join_strings(requested_fingerprints," ",0,NULL);
03925         log_warn(LD_DIR,
03926                  "We received a router descriptor with a fingerprint (%s) "
03927                  "that we never requested. (We asked for: %s.) Dropping.",
03928                  fp, requested);
03929         tor_free(requested);
03930         routerinfo_free(ri);
03931         continue;
03932       }
03933     }
03934 
03935     memcpy(d, ri->cache_info.signed_descriptor_digest, DIGEST_LEN);
03936     r = router_add_to_routerlist(ri, &msg, from_cache, !from_cache);
03937     if (WRA_WAS_ADDED(r)) {
03938       any_changed++;
03939       smartlist_add(changed, ri);
03940       routerlist_descriptors_added(changed, from_cache);
03941       smartlist_clear(changed);
03942     } else if (WRA_WAS_REJECTED(r)) {
03943       download_status_t *dl_status;
03944       dl_status = router_get_dl_status_by_descriptor_digest(d);
03945       if (dl_status) {
03946         log_info(LD_GENERAL, "Marking router %s as never downloadable",
03947                  hex_str(d, DIGEST_LEN));
03948         download_status_mark_impossible(dl_status);
03949       }
03950     }
03951   } SMARTLIST_FOREACH_END(ri);
03952 
03953   routerlist_assert_ok(routerlist);
03954 
03955   if (any_changed)
03956     router_rebuild_store(0, &routerlist->desc_store);
03957 
03958   smartlist_free(routers);
03959   smartlist_free(changed);
03960 
03961   return any_changed;
03962 }
03963 
03967 void
03968 router_load_extrainfo_from_string(const char *s, const char *eos,
03969                                   saved_location_t saved_location,
03970                                   smartlist_t *requested_fingerprints,
03971                                   int descriptor_digests)
03972 {
03973   smartlist_t *extrainfo_list = smartlist_new();
03974   const char *msg;
03975   int from_cache = (saved_location != SAVED_NOWHERE);
03976 
03977   router_parse_list_from_string(&s, eos, extrainfo_list, saved_location, 1, 0,
03978                                 NULL);
03979 
03980   log_info(LD_DIR, "%d elements to add", smartlist_len(extrainfo_list));
03981 
03982   SMARTLIST_FOREACH(extrainfo_list, extrainfo_t *, ei, {
03983       was_router_added_t added =
03984         router_add_extrainfo_to_routerlist(ei, &msg, from_cache, !from_cache);
03985       if (WRA_WAS_ADDED(added) && requested_fingerprints) {
03986         char fp[HEX_DIGEST_LEN+1];
03987         base16_encode(fp, sizeof(fp), descriptor_digests ?
03988                         ei->cache_info.signed_descriptor_digest :
03989                         ei->cache_info.identity_digest,
03990                       DIGEST_LEN);
03991         smartlist_string_remove(requested_fingerprints, fp);
03992         /* We silently let people stuff us with extrainfos we didn't ask for,
03993          * so long as we would have wanted them anyway.  Since we always fetch
03994          * all the extrainfos we want, and we never actually act on them
03995          * inside Tor, this should be harmless. */
03996       }
03997     });
03998 
03999   routerlist_assert_ok(routerlist);
04000   router_rebuild_store(0, &router_get_routerlist()->extrainfo_store);
04001 
04002   smartlist_free(extrainfo_list);
04003 }
04004 
04007 static int
04008 signed_desc_digest_is_recognized(signed_descriptor_t *desc)
04009 {
04010   const routerstatus_t *rs;
04011   networkstatus_t *consensus = networkstatus_get_latest_consensus();
04012   int caches = directory_caches_dir_info(get_options());
04013   const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
04014 
04015   if (consensus) {
04016     rs = networkstatus_vote_find_entry(consensus, desc->identity_digest);
04017     if (rs && tor_memeq(rs->descriptor_digest,
04018                       desc->signed_descriptor_digest, DIGEST_LEN))
04019       return 1;
04020   }
04021   if (caches && networkstatus_v2_list) {
04022     SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
04023     {
04024       if (!(rs = networkstatus_v2_find_entry(ns, desc->identity_digest)))
04025         continue;
04026       if (tor_memeq(rs->descriptor_digest,
04027                   desc->signed_descriptor_digest, DIGEST_LEN))
04028         return 1;
04029     });
04030   }
04031   return 0;
04032 }
04033 
04036 void
04037 update_all_descriptor_downloads(time_t now)
04038 {
04039   if (get_options()->DisableNetwork)
04040     return;
04041   update_router_descriptor_downloads(now);
04042   update_microdesc_downloads(now);
04043   launch_dummy_descriptor_download_as_needed(now, get_options());
04044 }
04045 
04048 void
04049 routerlist_retry_directory_downloads(time_t now)
04050 {
04051   router_reset_status_download_failures();
04052   router_reset_descriptor_download_failures();
04053   if (get_options()->DisableNetwork)
04054     return;
04055   update_networkstatus_downloads(now);
04056   update_all_descriptor_downloads(now);
04057 }
04058 
04061 int
04062 router_exit_policy_all_nodes_reject(const tor_addr_t *addr, uint16_t port,
04063                                     int need_uptime)
04064 { /* XXXX MOVE */
04065   addr_policy_result_t r;
04066 
04067   SMARTLIST_FOREACH_BEGIN(nodelist_get_list(), const node_t *, node) {
04068     if (node->is_running &&
04069         !node_is_unreliable(node, need_uptime, 0, 0)) {
04070 
04071       r = compare_tor_addr_to_node_policy(addr, port, node);
04072 
04073       if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
04074         return 0; /* this one could be ok. good enough. */
04075     }
04076   } SMARTLIST_FOREACH_END(node);
04077   return 1; /* all will reject. */
04078 }
04079 
04082 int
04083 router_exit_policy_rejects_all(const routerinfo_t *router)
04084 {
04085   return router->policy_is_reject_star;
04086 }
04087 
04092 trusted_dir_server_t *
04093 add_trusted_dir_server(const char *nickname, const char *address,
04094                        uint16_t dir_port, uint16_t or_port,
04095                        const char *digest, const char *v3_auth_digest,
04096                        dirinfo_type_t type)
04097 {
04098   trusted_dir_server_t *ent;
04099   uint32_t a;
04100   char *hostname = NULL;
04101   if (!trusted_dir_servers)
04102     trusted_dir_servers = smartlist_new();
04103 
04104   if (!address) { /* The address is us; we should guess. */
04105     if (resolve_my_address(LOG_WARN, get_options(), &a, &hostname) < 0) {
04106       log_warn(LD_CONFIG,
04107                "Couldn't find a suitable address when adding ourself as a "
04108                "trusted directory server.");
04109       return NULL;
04110     }
04111   } else {
04112     if (tor_lookup_hostname(address, &a)) {
04113       log_warn(LD_CONFIG,
04114                "Unable to lookup address for directory server at '%s'",
04115                address);
04116       return NULL;
04117     }
04118     hostname = tor_strdup(address);
04119   }
04120 
04121   ent = tor_malloc_zero(sizeof(trusted_dir_server_t));
04122   ent->nickname = nickname ? tor_strdup(nickname) : NULL;
04123   ent->address = hostname;
04124   ent->addr = a;
04125   ent->dir_port = dir_port;
04126   ent->or_port = or_port;
04127   ent->is_running = 1;
04128   ent->type = type;
04129   memcpy(ent->digest, digest, DIGEST_LEN);
04130   if (v3_auth_digest && (type & V3_DIRINFO))
04131     memcpy(ent->v3_identity_digest, v3_auth_digest, DIGEST_LEN);
04132 
04133   if (nickname)
04134     tor_asprintf(&ent->description, "directory server \"%s\" at %s:%d",
04135                  nickname, hostname, (int)dir_port);
04136   else
04137     tor_asprintf(&ent->description, "directory server at %s:%d",
04138                  hostname, (int)dir_port);
04139 
04140   ent->fake_status.addr = ent->addr;
04141   memcpy(ent->fake_status.identity_digest, digest, DIGEST_LEN);
04142   if (nickname)
04143     strlcpy(ent->fake_status.nickname, nickname,
04144             sizeof(ent->fake_status.nickname));
04145   else
04146     ent->fake_status.nickname[0] = '\0';
04147   ent->fake_status.dir_port = ent->dir_port;
04148   ent->fake_status.or_port = ent->or_port;
04149 
04150   if (ent->or_port)
04151     ent->fake_status.version_supports_begindir = 1;
04152 
04153   ent->fake_status.version_supports_conditional_consensus = 1;
04154 
04155   smartlist_add(trusted_dir_servers, ent);
04156   router_dir_info_changed();
04157   return ent;
04158 }
04159 
04161 void
04162 authority_cert_free(authority_cert_t *cert)
04163 {
04164   if (!cert)
04165     return;
04166 
04167   tor_free(cert->cache_info.signed_descriptor_body);
04168   crypto_pk_free(cert->signing_key);
04169   crypto_pk_free(cert->identity_key);
04170 
04171   tor_free(cert);
04172 }
04173 
04175 static void
04176 trusted_dir_server_free(trusted_dir_server_t *ds)
04177 {
04178   if (!ds)
04179     return;
04180 
04181   tor_free(ds->nickname);
04182   tor_free(ds->description);
04183   tor_free(ds->address);
04184   tor_free(ds);
04185 }
04186 
04188 void
04189 clear_trusted_dir_servers(void)
04190 {
04191   if (trusted_dir_servers) {
04192     SMARTLIST_FOREACH(trusted_dir_servers, trusted_dir_server_t *, ent,
04193                       trusted_dir_server_free(ent));
04194     smartlist_clear(trusted_dir_servers);
04195   } else {
04196     trusted_dir_servers = smartlist_new();
04197   }
04198   router_dir_info_changed();
04199 }
04200 
04203 int
04204 any_trusted_dir_is_v1_authority(void)
04205 {
04206   if (trusted_dir_servers)
04207     return get_n_authorities(V1_DIRINFO) > 0;
04208 
04209   return 0;
04210 }
04211 
04218 static void
04219 list_pending_downloads(digestmap_t *result,
04220                        int purpose, const char *prefix)
04221 {
04222   const size_t p_len = strlen(prefix);
04223   smartlist_t *tmp = smartlist_new();
04224   smartlist_t *conns = get_connection_array();
04225   int flags = DSR_HEX;
04226   if (purpose == DIR_PURPOSE_FETCH_MICRODESC)
04227     flags = DSR_DIGEST256|DSR_BASE64;
04228 
04229   tor_assert(result);
04230 
04231   SMARTLIST_FOREACH_BEGIN(conns, connection_t *, conn) {
04232     if (conn->type == CONN_TYPE_DIR &&
04233         conn->purpose == purpose &&
04234         !conn->marked_for_close) {
04235       const char *resource = TO_DIR_CONN(conn)->requested_resource;
04236       if (!strcmpstart(resource, prefix))
04237         dir_split_resource_into_fingerprints(resource + p_len,
04238                                              tmp, NULL, flags);
04239     }
04240   } SMARTLIST_FOREACH_END(conn);
04241 
04242   SMARTLIST_FOREACH(tmp, char *, d,
04243                     {
04244                       digestmap_set(result, d, (void*)1);
04245                       tor_free(d);
04246                     });
04247   smartlist_free(tmp);
04248 }
04249 
04253 static void
04254 list_pending_descriptor_downloads(digestmap_t *result, int extrainfo)
04255 {
04256   int purpose =
04257     extrainfo ? DIR_PURPOSE_FETCH_EXTRAINFO : DIR_PURPOSE_FETCH_SERVERDESC;
04258   list_pending_downloads(result, purpose, "d/");
04259 }
04260 
04268 void
04269 list_pending_microdesc_downloads(digestmap_t *result)
04270 {
04271   list_pending_downloads(result, DIR_PURPOSE_FETCH_MICRODESC, "d/");
04272 }
04273 
04279 static void
04280 initiate_descriptor_downloads(const routerstatus_t *source,
04281                               int purpose,
04282                               smartlist_t *digests,
04283                               int lo, int hi, int pds_flags)
04284 {
04285   int i, n = hi-lo;
04286   char *resource, *cp;
04287   size_t r_len;
04288 
04289   int digest_len = DIGEST_LEN, enc_digest_len = HEX_DIGEST_LEN;
04290   char sep = '+';
04291   int b64_256 = 0;
04292 
04293   if (purpose == DIR_PURPOSE_FETCH_MICRODESC) {
04294     /* Microdescriptors are downloaded by "-"-separated base64-encoded
04295      * 256-bit digests. */
04296     digest_len = DIGEST256_LEN;
04297     enc_digest_len = BASE64_DIGEST256_LEN;
04298     sep = '-';
04299     b64_256 = 1;
04300   }
04301 
04302   if (n <= 0)
04303     return;
04304   if (lo < 0)
04305     lo = 0;
04306   if (hi > smartlist_len(digests))
04307     hi = smartlist_len(digests);
04308 
04309   r_len = 8 + (enc_digest_len+1)*n;
04310   cp = resource = tor_malloc(r_len);
04311   memcpy(cp, "d/", 2);
04312   cp += 2;
04313   for (i = lo; i < hi; ++i) {
04314     if (b64_256) {
04315       digest256_to_base64(cp, smartlist_get(digests, i));
04316     } else {
04317       base16_encode(cp, r_len-(cp-resource),
04318                     smartlist_get(digests,i), digest_len);
04319     }
04320     cp += enc_digest_len;
04321     *cp++ = sep;
04322   }
04323   memcpy(cp-1, ".z", 3);
04324 
04325   if (source) {
04326     /* We know which authority we want. */
04327     directory_initiate_command_routerstatus(source, purpose,
04328                                             ROUTER_PURPOSE_GENERAL,
04329                                             0, /* not private */
04330                                             resource, NULL, 0, 0);
04331   } else {
04332     directory_get_from_dirserver(purpose, ROUTER_PURPOSE_GENERAL, resource,
04333                                  pds_flags);
04334   }
04335   tor_free(resource);
04336 }
04337 
04341 static INLINE int
04342 client_would_use_router(const routerstatus_t *rs, time_t now,
04343                         const or_options_t *options)
04344 {
04345   if (!rs->is_flagged_running && !options->FetchUselessDescriptors) {
04346     /* If we had this router descriptor, we wouldn't even bother using it.
04347      * But, if we want to have a complete list, fetch it anyway. */
04348     return 0;
04349   }
04350   if (rs->published_on + options->TestingEstimatedDescriptorPropagationTime
04351       > now) {
04352     /* Most caches probably don't have this descriptor yet. */
04353     return 0;
04354   }
04355   if (rs->published_on + OLD_ROUTER_DESC_MAX_AGE < now) {
04356     /* We'd drop it immediately for being too old. */
04357     return 0;
04358   }
04359   return 1;
04360 }
04361 
04368 #define MAX_DL_PER_REQUEST 96
04369 #define MAX_MICRODESC_DL_PER_REQUEST 92
04370 
04372 #define MIN_DL_PER_REQUEST 4
04373 
04375 #define MIN_REQUESTS 3
04376 
04379 #define MAX_DL_TO_DELAY 16
04380 
04382 #define MAX_CLIENT_INTERVAL_WITHOUT_REQUEST (10*60)
04383 
04390 void
04391 launch_descriptor_downloads(int purpose,
04392                             smartlist_t *downloadable,
04393                             const routerstatus_t *source, time_t now)
04394 {
04395   int should_delay = 0, n_downloadable;
04396   const or_options_t *options = get_options();
04397   const char *descname;
04398 
04399   tor_assert(purpose == DIR_PURPOSE_FETCH_SERVERDESC ||
04400              purpose == DIR_PURPOSE_FETCH_MICRODESC);
04401 
04402   descname = (purpose == DIR_PURPOSE_FETCH_SERVERDESC) ?
04403     "routerdesc" : "microdesc";
04404 
04405   n_downloadable = smartlist_len(downloadable);
04406   if (!directory_fetches_dir_info_early(options)) {
04407     if (n_downloadable >= MAX_DL_TO_DELAY) {
04408       log_debug(LD_DIR,
04409                 "There are enough downloadable %ss to launch requests.",
04410                 descname);
04411       should_delay = 0;
04412     } else {
04413       should_delay = (last_descriptor_download_attempted +
04414                       MAX_CLIENT_INTERVAL_WITHOUT_REQUEST) > now;
04415       if (!should_delay && n_downloadable) {
04416         if (last_descriptor_download_attempted) {
04417           log_info(LD_DIR,
04418                    "There are not many downloadable %ss, but we've "
04419                    "been waiting long enough (%d seconds). Downloading.",
04420                    descname,
04421                    (int)(now-last_descriptor_download_attempted));
04422         } else {
04423           log_info(LD_DIR,
04424                    "There are not many downloadable %ss, but we haven't "
04425                    "tried downloading descriptors recently. Downloading.",
04426                    descname);
04427         }
04428       }
04429     }
04430   }
04431   /* XXX should we consider having even the dir mirrors delay
04432    * a little bit, so we don't load the authorities as much? -RD
04433    * I don't think so.  If we do, clients that want those descriptors may
04434    * not actually find them if the caches haven't got them yet. -NM
04435    */
04436 
04437   if (! should_delay && n_downloadable) {
04438     int i, n_per_request;
04439     const char *req_plural = "", *rtr_plural = "";
04440     int pds_flags = PDS_RETRY_IF_NO_SERVERS;
04441     if (! authdir_mode_any_nonhidserv(options)) {
04442       /* If we wind up going to the authorities, we want to only open one
04443        * connection to each authority at a time, so that we don't overload
04444        * them.  We do this by setting PDS_NO_EXISTING_SERVERDESC_FETCH
04445        * regardless of whether we're a cache or not; it gets ignored if we're
04446        * not calling router_pick_trusteddirserver.
04447        *
04448        * Setting this flag can make initiate_descriptor_downloads() ignore
04449        * requests.  We need to make sure that we do in fact call
04450        * update_router_descriptor_downloads() later on, once the connections
04451        * have succeeded or failed.
04452        */
04453       pds_flags |= (purpose == DIR_PURPOSE_FETCH_MICRODESC) ?
04454         PDS_NO_EXISTING_MICRODESC_FETCH :
04455         PDS_NO_EXISTING_SERVERDESC_FETCH;
04456     }
04457 
04458     n_per_request = CEIL_DIV(n_downloadable, MIN_REQUESTS);
04459     if (purpose == DIR_PURPOSE_FETCH_MICRODESC) {
04460       if (n_per_request > MAX_MICRODESC_DL_PER_REQUEST)
04461         n_per_request = MAX_MICRODESC_DL_PER_REQUEST;
04462     } else {
04463       if (n_per_request > MAX_DL_PER_REQUEST)
04464         n_per_request = MAX_DL_PER_REQUEST;
04465     }
04466     if (n_per_request < MIN_DL_PER_REQUEST)
04467       n_per_request = MIN_DL_PER_REQUEST;
04468 
04469     if (n_downloadable > n_per_request)
04470       req_plural = rtr_plural = "s";
04471     else if (n_downloadable > 1)
04472       rtr_plural = "s";
04473 
04474     log_info(LD_DIR,
04475              "Launching %d request%s for %d router%s, %d at a time",
04476              CEIL_DIV(n_downloadable, n_per_request),
04477              req_plural, n_downloadable, rtr_plural, n_per_request);
04478     smartlist_sort_digests(downloadable);
04479     for (i=0; i < n_downloadable; i += n_per_request) {
04480       initiate_descriptor_downloads(source, purpose,
04481                                     downloadable, i, i+n_per_request,
04482                                     pds_flags);
04483     }
04484     last_descriptor_download_attempted = now;
04485   }
04486 }
04487 
04492 static void
04493 update_router_descriptor_cache_downloads_v2(time_t now)
04494 {
04495   smartlist_t **downloadable; /* For each authority, what can we dl from it? */
04496   smartlist_t **download_from; /*          ... and, what will we dl from it? */
04497   digestmap_t *map; /* Which descs are in progress, or assigned? */
04498   int i, j, n;
04499   int n_download;
04500   const or_options_t *options = get_options();
04501   const smartlist_t *networkstatus_v2_list = networkstatus_get_v2_list();
04502 
04503   if (! directory_fetches_dir_info_early(options)) {
04504     log_warn(LD_BUG, "Called update_router_descriptor_cache_downloads_v2() "
04505              "on a non-dir-mirror?");
04506   }
04507 
04508   if (!networkstatus_v2_list || !smartlist_len(networkstatus_v2_list))
04509     return;
04510 
04511   map = digestmap_new();
04512   n = smartlist_len(networkstatus_v2_list);
04513 
04514   downloadable = tor_malloc_zero(sizeof(smartlist_t*) * n);
04515   download_from = tor_malloc_zero(sizeof(smartlist_t*) * n);
04516 
04517   /* Set map[d]=1 for the digest of every descriptor that we are currently
04518    * downloading. */
04519   list_pending_descriptor_downloads(map, 0);
04520 
04521   /* For the digest of every descriptor that we don't have, and that we aren't
04522    * downloading, add d to downloadable[i] if the i'th networkstatus knows
04523    * about that descriptor, and we haven't already failed to get that
04524    * descriptor from the corresponding authority.
04525    */
04526   n_download = 0;
04527   SMARTLIST_FOREACH(networkstatus_v2_list, networkstatus_v2_t *, ns,
04528     {
04529       trusted_dir_server_t *ds;
04530       smartlist_t *dl;
04531       dl = downloadable[ns_sl_idx] = smartlist_new();
04532       download_from[ns_sl_idx] = smartlist_new();
04533       if (ns->published_on + MAX_NETWORKSTATUS_AGE+10*60 < now) {
04534         /* Don't download if the networkstatus is almost ancient. */
04535         /* Actually, I suspect what's happening here is that we ask
04536          * for the descriptor when we have a given networkstatus,
04537          * and then we get a newer networkstatus, and then we receive
04538          * the descriptor. Having a networkstatus actually expire is
04539          * probably a rare event, and we'll probably be happiest if
04540          * we take this clause out. -RD */
04541         continue;
04542       }
04543 
04544       /* Don't try dirservers that we think are down -- we might have
04545        * just tried them and just marked them as down. */
04546       ds = router_get_trusteddirserver_by_digest(ns->identity_digest);
04547       if (ds && !ds->is_running)
04548         continue;
04549 
04550       SMARTLIST_FOREACH(ns->entries, routerstatus_t * , rs,
04551         {
04552           if (!rs->need_to_mirror)
04553             continue;
04554           if (router_get_by_descriptor_digest(rs->descriptor_digest)) {
04555             log_warn(LD_BUG,
04556                      "We have a router descriptor, but need_to_mirror=1.");
04557             rs->need_to_mirror = 0;
04558             continue;
04559           }
04560           if (authdir_mode(options) && dirserv_would_reject_router(rs)) {
04561             rs->need_to_mirror = 0;
04562             continue;
04563           }
04564           if (digestmap_get(map, rs->descriptor_digest)) {
04565             /* We're downloading it already. */
04566             continue;
04567           } else {
04568             /* We could download it from this guy. */
04569             smartlist_add(dl, rs->descriptor_digest);
04570             ++n_download;
04571           }
04572         });
04573     });
04574 
04575   /* At random, assign descriptors to authorities such that:
04576    * - if d is a member of some downloadable[x], d is a member of some
04577    *   download_from[y].  (Everything we want to download, we try to download
04578    *   from somebody.)
04579    * - If d is a member of download_from[y], d is a member of downloadable[y].
04580    *   (We only try to download descriptors from authorities who claim to have
04581    *   them.)
04582    * - No d is a member of download_from[x] and download_from[y] s.t. x != y.
04583    *   (We don't try to download anything from two authorities concurrently.)
04584    */
04585   while (n_download) {
04586     int which_ns = crypto_rand_int(n);
04587     smartlist_t *dl = downloadable[which_ns];
04588     int idx;
04589     char *d;
04590     if (!smartlist_len(dl))
04591       continue;
04592     idx = crypto_rand_int(smartlist_len(dl));
04593     d = smartlist_get(dl, idx);
04594     if (! digestmap_get(map, d)) {
04595       smartlist_add(download_from[which_ns], d);
04596       digestmap_set(map, d, (void*) 1);
04597     }
04598     smartlist_del(dl, idx);
04599     --n_download;
04600   }
04601 
04602   /* Now, we can actually launch our requests. */
04603   for (i=0; i<n; ++i) {
04604     networkstatus_v2_t *ns = smartlist_get(networkstatus_v2_list, i);
04605     trusted_dir_server_t *ds =
04606       router_get_trusteddirserver_by_digest(ns->identity_digest);
04607     smartlist_t *dl = download_from[i];
04608     int pds_flags = PDS_RETRY_IF_NO_SERVERS;
04609     if (! authdir_mode_any_nonhidserv(options))
04610       pds_flags |= PDS_NO_EXISTING_SERVERDESC_FETCH; /* XXXX ignored*/
04611 
04612     if (!ds) {
04613       log_info(LD_DIR, "Networkstatus with no corresponding authority!");
04614       continue;
04615     }
04616     if (! smartlist_len(dl))
04617       continue;
04618     log_info(LD_DIR, "Requesting %d descriptors from authority \"%s\"",
04619              smartlist_len(dl), ds->nickname);
04620     for (j=0; j < smartlist_len(dl); j += MAX_DL_PER_REQUEST) {
04621       initiate_descriptor_downloads(&(ds->fake_status),
04622                                     DIR_PURPOSE_FETCH_SERVERDESC, dl, j,
04623                                     j+MAX_DL_PER_REQUEST, pds_flags);
04624     }
04625   }
04626 
04627   for (i=0; i<n; ++i) {
04628     smartlist_free(download_from[i]);
04629     smartlist_free(downloadable[i]);
04630   }
04631   tor_free(download_from);
04632   tor_free(downloadable);
04633   digestmap_free(map,NULL);
04634 }
04635 
04638 void
04639 update_consensus_router_descriptor_downloads(time_t now, int is_vote,
04640                                              networkstatus_t *consensus)
04641 {
04642   const or_options_t *options = get_options();
04643   digestmap_t *map = NULL;
04644   smartlist_t *no_longer_old = smartlist_new();
04645   smartlist_t *downloadable = smartlist_new();
04646   routerstatus_t *source = NULL;
04647   int authdir = authdir_mode(options);
04648   int n_delayed=0, n_have=0, n_would_reject=0, n_wouldnt_use=0,
04649     n_inprogress=0, n_in_oldrouters=0;
04650 
04651   if (directory_too_idle_to_fetch_descriptors(options, now))
04652     goto done;
04653   if (!consensus)
04654     goto done;
04655 
04656   if (is_vote) {
04657     /* where's it from, so we know whom to ask for descriptors */
04658     trusted_dir_server_t *ds;
04659     networkstatus_voter_info_t *voter = smartlist_get(consensus->voters, 0);
04660     tor_assert(voter);
04661     ds = trusteddirserver_get_by_v3_auth_digest(voter->identity_digest);
04662     if (ds)
04663       source = &(ds->fake_status);
04664     else
04665       log_warn(LD_DIR, "couldn't lookup source from vote?");
04666   }
04667 
04668   map = digestmap_new();
04669   list_pending_descriptor_downloads(map, 0);
04670   SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, void *, rsp) {
04671       routerstatus_t *rs =
04672         is_vote ? &(((vote_routerstatus_t *)rsp)->status) : rsp;
04673       signed_descriptor_t *sd;
04674       if ((sd = router_get_by_descriptor_digest(rs->descriptor_digest))) {
04675         const routerinfo_t *ri;
04676         ++n_have;
04677         if (!(ri = router_get_by_id_digest(rs->identity_digest)) ||
04678             tor_memneq(ri->cache_info.signed_descriptor_digest,
04679                    sd->signed_descriptor_digest, DIGEST_LEN)) {
04680           /* We have a descriptor with this digest, but either there is no
04681            * entry in routerlist with the same ID (!ri), or there is one,
04682            * but the identity digest differs (memcmp).
04683            */
04684           smartlist_add(no_longer_old, sd);
04685           ++n_in_oldrouters; /* We have it in old_routers. */
04686         }
04687         continue; /* We have it already. */
04688       }
04689       if (digestmap_get(map, rs->descriptor_digest)) {
04690         ++n_inprogress;
04691         continue; /* We have an in-progress download. */
04692       }
04693       if (!download_status_is_ready(&rs->dl_status, now,
04694                                     MAX_ROUTERDESC_DOWNLOAD_FAILURES)) {
04695         ++n_delayed; /* Not ready for retry. */
04696         continue;
04697       }
04698       if (authdir && dirserv_would_reject_router(rs)) {
04699         ++n_would_reject;
04700         continue; /* We would throw it out immediately. */
04701       }
04702       if (!directory_caches_dir_info(options) &&
04703           !client_would_use_router(rs, now, options)) {
04704         ++n_wouldnt_use;
04705         continue; /* We would never use it ourself. */
04706       }
04707       if (is_vote && source) {
04708         char time_bufnew[ISO_TIME_LEN+1];
04709         char time_bufold[ISO_TIME_LEN+1];
04710         const routerinfo_t *oldrouter;
04711         oldrouter = router_get_by_id_digest(rs->identity_digest);
04712         format_iso_time(time_bufnew, rs->published_on);
04713         if (oldrouter)
04714           format_iso_time(time_bufold, oldrouter->cache_info.published_on);
04715         log_info(LD_DIR, "Learned about %s (%s vs %s) from %s's vote (%s)",
04716                  routerstatus_describe(rs),
04717                  time_bufnew,
04718                  oldrouter ? time_bufold : "none",
04719                  source->nickname, oldrouter ? "known" : "unknown");
04720       }
04721       smartlist_add(downloadable, rs->descriptor_digest);
04722   } SMARTLIST_FOREACH_END(rsp);
04723 
04724   if (!authdir_mode_handles_descs(options, ROUTER_PURPOSE_GENERAL)
04725       && smartlist_len(no_longer_old)) {
04726     routerlist_t *rl = router_get_routerlist();
04727     log_info(LD_DIR, "%d router descriptors listed in consensus are "
04728              "currently in old_routers; making them current.",
04729              smartlist_len(no_longer_old));
04730     SMARTLIST_FOREACH(no_longer_old, signed_descriptor_t *, sd, {
04731         const char *msg;
04732         was_router_added_t r;
04733         routerinfo_t *ri = routerlist_reparse_old(rl, sd);
04734         if (!ri) {
04735           log_warn(LD_BUG, "Failed to re-parse a router.");
04736           continue;
04737         }
04738         r = router_add_to_routerlist(ri, &msg, 1, 0);
04739         if (WRA_WAS_OUTDATED(r)) {
04740           log_warn(LD_DIR, "Couldn't add re-parsed router: %s",
04741                    msg?msg:"???");
04742         }
04743       });
04744     routerlist_assert_ok(rl);
04745   }
04746 
04747   log_info(LD_DIR,
04748            "%d router descriptors downloadable. %d delayed; %d present "
04749            "(%d of those were in old_routers); %d would_reject; "
04750            "%d wouldnt_use; %d in progress.",
04751            smartlist_len(downloadable), n_delayed, n_have, n_in_oldrouters,
04752            n_would_reject, n_wouldnt_use, n_inprogress);
04753 
04754   launch_descriptor_downloads(DIR_PURPOSE_FETCH_SERVERDESC,
04755                               downloadable, source, now);
04756 
04757   digestmap_free(map, NULL);
04758  done:
04759   smartlist_free(downloadable);
04760   smartlist_free(no_longer_old);
04761 }
04762 
04765 /*XXXX024 this info should come from netinfo cells or something, or we should
04766  * do this only when we aren't seeing incoming data. see bug 652. */
04767 #define DUMMY_DOWNLOAD_INTERVAL (20*60)
04768 
04771 static void
04772 launch_dummy_descriptor_download_as_needed(time_t now,
04773                                            const or_options_t *options)
04774 {
04775   static time_t last_dummy_download = 0;
04776   /* XXXX024 we could be smarter here; see notes on bug 652. */
04777   /* If we're a server that doesn't have a configured address, we rely on
04778    * directory fetches to learn when our address changes.  So if we haven't
04779    * tried to get any routerdescs in a long time, try a dummy fetch now. */
04780   if (!options->Address &&
04781       server_mode(options) &&
04782       last_descriptor_download_attempted + DUMMY_DOWNLOAD_INTERVAL < now &&
04783       last_dummy_download + DUMMY_DOWNLOAD_INTERVAL < now) {
04784     last_dummy_download = now;
04785     directory_get_from_dirserver(DIR_PURPOSE_FETCH_SERVERDESC,
04786                                  ROUTER_PURPOSE_GENERAL, "authority.z",
04787                                  PDS_RETRY_IF_NO_SERVERS);
04788   }
04789 }
04790 
04792 void
04793 update_router_descriptor_downloads(time_t now)
04794 {
04795   const or_options_t *options = get_options();
04796   if (should_delay_dir_fetches(options))
04797     return;
04798   if (!we_fetch_router_descriptors(options))
04799     return;
04800   if (directory_fetches_dir_info_early(options)) {
04801     update_router_descriptor_cache_downloads_v2(now);
04802   }
04803 
04804   update_consensus_router_descriptor_downloads(now, 0,
04805                   networkstatus_get_reasonably_live_consensus(now, FLAV_NS));
04806 }
04807 
04809 void
04810 update_extrainfo_downloads(time_t now)
04811 {
04812   const or_options_t *options = get_options();
04813   routerlist_t *rl;
04814   smartlist_t *wanted;
04815   digestmap_t *pending;
04816   int old_routers, i;
04817   int n_no_ei = 0, n_pending = 0, n_have = 0, n_delay = 0;
04818   if (! options->DownloadExtraInfo)
04819     return;
04820   if (should_delay_dir_fetches(options))
04821     return;
04822   if (!router_have_minimum_dir_info())
04823     return;
04824 
04825   pending = digestmap_new();
04826   list_pending_descriptor_downloads(pending, 1);
04827   rl = router_get_routerlist();
04828   wanted = smartlist_new();
04829   for (old_routers = 0; old_routers < 2; ++old_routers) {
04830     smartlist_t *lst = old_routers ? rl->old_routers : rl->routers;
04831     for (i = 0; i < smartlist_len(lst); ++i) {
04832       signed_descriptor_t *sd;
04833       char *d;
04834       if (old_routers)
04835         sd = smartlist_get(lst, i);
04836       else
04837         sd = &((routerinfo_t*)smartlist_get(lst, i))->cache_info;
04838       if (sd->is_extrainfo)
04839         continue; /* This should never happen. */
04840       if (old_routers && !router_get_by_id_digest(sd->identity_digest))
04841         continue; /* Couldn't check the signature if we got it. */
04842       if (sd->extrainfo_is_bogus)
04843         continue;
04844       d = sd->extra_info_digest;
04845       if (tor_digest_is_zero(d)) {
04846         ++n_no_ei;
04847         continue;
04848       }
04849       if (eimap_get(rl->extra_info_map, d)) {
04850         ++n_have;
04851         continue;
04852       }
04853       if (!download_status_is_ready(&sd->ei_dl_status, now,
04854                                     MAX_ROUTERDESC_DOWNLOAD_FAILURES)) {
04855         ++n_delay;
04856         continue;
04857       }
04858       if (digestmap_get(pending, d)) {
04859         ++n_pending;
04860         continue;
04861       }
04862       smartlist_add(wanted, d);
04863     }
04864   }
04865   digestmap_free(pending, NULL);
04866 
04867   log_info(LD_DIR, "Extrainfo download status: %d router with no ei, %d "
04868            "with present ei, %d delaying, %d pending, %d downloadable.",
04869            n_no_ei, n_have, n_delay, n_pending, smartlist_len(wanted));
04870 
04871   smartlist_shuffle(wanted);
04872   for (i = 0; i < smartlist_len(wanted); i += MAX_DL_PER_REQUEST) {
04873     initiate_descriptor_downloads(NULL, DIR_PURPOSE_FETCH_EXTRAINFO,
04874                                   wanted, i, i + MAX_DL_PER_REQUEST,
04875                 PDS_RETRY_IF_NO_SERVERS|PDS_NO_EXISTING_SERVERDESC_FETCH);
04876   }
04877 
04878   smartlist_free(wanted);
04879 }
04880 
04883 static int have_min_dir_info = 0;
04887 static int need_to_update_have_min_dir_info = 1;
04890 static char dir_info_status[128] = "";
04891 
04895 //XXX should consider whether we have enough exiting nodes here.
04896 int
04897 router_have_minimum_dir_info(void)
04898 {
04899   if (PREDICT_UNLIKELY(need_to_update_have_min_dir_info)) {
04900     update_router_have_minimum_dir_info();
04901     need_to_update_have_min_dir_info = 0;
04902   }
04903   return have_min_dir_info;
04904 }
04905 
04910 void
04911 router_dir_info_changed(void)
04912 {
04913   need_to_update_have_min_dir_info = 1;
04914   rend_hsdir_routers_changed();
04915 }
04916 
04919 const char *
04920 get_dir_info_status_string(void)
04921 {
04922   return dir_info_status;
04923 }
04924 
04932 static void
04933 count_usable_descriptors(int *num_present, int *num_usable,
04934                          const networkstatus_t *consensus,
04935                          const or_options_t *options, time_t now,
04936                          routerset_t *in_set, int exit_only)
04937 {
04938   const int md = (consensus->flavor == FLAV_MICRODESC);
04939   *num_present = 0, *num_usable=0;
04940 
04941   SMARTLIST_FOREACH_BEGIN(consensus->routerstatus_list, routerstatus_t *, rs)
04942     {
04943        if (exit_only && ! rs->is_exit)
04944          continue;
04945        if (in_set && ! routerset_contains_routerstatus(in_set, rs, -1))
04946          continue;
04947        if (client_would_use_router(rs, now, options)) {
04948          const char * const digest = rs->descriptor_digest;
04949          int present;
04950          ++*num_usable; /* the consensus says we want it. */
04951          if (md)
04952            present = NULL != microdesc_cache_lookup_by_digest256(NULL, digest);
04953          else
04954            present = NULL != router_get_by_descriptor_digest(digest);
04955          if (present) {
04956            /* we have the descriptor listed in the consensus. */
04957            ++*num_present;
04958          }
04959        }
04960      }
04961   SMARTLIST_FOREACH_END(rs);
04962 
04963   log_debug(LD_DIR, "%d usable, %d present.", *num_usable, *num_present);
04964 }
04965 
04969 int
04970 count_loading_descriptors_progress(void)
04971 {
04972   int num_present = 0, num_usable=0;
04973   time_t now = time(NULL);
04974   const networkstatus_t *consensus =
04975     networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor());
04976   double fraction;
04977 
04978   if (!consensus)
04979     return 0; /* can't count descriptors if we have no list of them */
04980 
04981   count_usable_descriptors(&num_present, &num_usable,
04982                            consensus, get_options(), now, NULL, 0);
04983 
04984   if (num_usable == 0)
04985     return 0; /* don't div by 0 */
04986   fraction = num_present / (num_usable/4.);
04987   if (fraction > 1.0)
04988     return 0; /* it's not the number of descriptors holding us back */
04989   return BOOTSTRAP_STATUS_LOADING_DESCRIPTORS + (int)
04990     (fraction*(BOOTSTRAP_STATUS_CONN_OR-1 -
04991                BOOTSTRAP_STATUS_LOADING_DESCRIPTORS));
04992 }
04993 
04997 static void
04998 update_router_have_minimum_dir_info(void)
04999 {
05000   int num_present = 0, num_usable=0;
05001   int num_exit_present = 0, num_exit_usable = 0;
05002   time_t now = time(NULL);
05003   int res;
05004   const or_options_t *options = get_options();
05005   const networkstatus_t *consensus =
05006     networkstatus_get_reasonably_live_consensus(now,usable_consensus_flavor());
05007   int using_md;
05008 
05009   if (!consensus) {
05010     if (!networkstatus_get_latest_consensus())
05011       strlcpy(dir_info_status, "We have no usable consensus.",
05012               sizeof(dir_info_status));
05013     else
05014       strlcpy(dir_info_status, "We have no recent usable consensus.",
05015               sizeof(dir_info_status));
05016     res = 0;
05017     goto done;
05018   }
05019 
05020   if (should_delay_dir_fetches(get_options())) {
05021     log_notice(LD_DIR, "no known bridge descriptors running yet; stalling");
05022     strlcpy(dir_info_status, "No live bridge descriptors.",
05023             sizeof(dir_info_status));
05024     res = 0;
05025     goto done;
05026   }
05027 
05028   using_md = consensus->flavor == FLAV_MICRODESC;
05029 
05030   count_usable_descriptors(&num_present, &num_usable, consensus, options, now,
05031                            NULL, 0);
05032   count_usable_descriptors(&num_exit_present, &num_exit_usable,
05033                            consensus, options, now, options->ExitNodes, 1);
05034 
05035 /* What fraction of desired server descriptors do we need before we will
05036  * build circuits? */
05037 #define FRAC_USABLE_NEEDED .75
05038 /* What fraction of desired _exit_ server descriptors do we need before we
05039  * will build circuits? */
05040 #define FRAC_EXIT_USABLE_NEEDED .5
05041 
05042   if (num_present < num_usable * FRAC_USABLE_NEEDED) {
05043     tor_snprintf(dir_info_status, sizeof(dir_info_status),
05044                  "We have only %d/%d usable %sdescriptors.",
05045                  num_present, num_usable, using_md ? "micro" : "");
05046     res = 0;
05047     control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0);
05048     goto done;
05049   } else if (num_present < 2) {
05050     tor_snprintf(dir_info_status, sizeof(dir_info_status),
05051                  "Only %d %sdescriptor%s here and believed reachable!",
05052                  num_present, using_md ? "micro" : "", num_present ? "" : "s");
05053     res = 0;
05054     goto done;
05055   } else if (num_exit_present < num_exit_usable * FRAC_EXIT_USABLE_NEEDED) {
05056     tor_snprintf(dir_info_status, sizeof(dir_info_status),
05057                  "We have only %d/%d usable exit node descriptors.",
05058                  num_exit_present, num_exit_usable);
05059     res = 0;
05060     control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_DESCRIPTORS, 0);
05061     goto done;
05062   }
05063 
05064   /* Check for entry nodes. */
05065   if (options->EntryNodes) {
05066     count_usable_descriptors(&num_present, &num_usable, consensus, options,
05067                              now, options->EntryNodes, 0);
05068 
05069     if (!num_usable || !num_present) {
05070       tor_snprintf(dir_info_status, sizeof(dir_info_status),
05071                    "We have only %d/%d usable entry node %sdescriptors.",
05072                    num_present, num_usable, using_md?"micro":"");
05073       res = 0;
05074       goto done;
05075     }
05076   }
05077 
05078   res = 1;
05079 
05080  done:
05081   if (res && !have_min_dir_info) {
05082     log(LOG_NOTICE, LD_DIR,
05083         "We now have enough directory information to build circuits.");
05084     control_event_client_status(LOG_NOTICE, "ENOUGH_DIR_INFO");
05085     control_event_bootstrap(BOOTSTRAP_STATUS_CONN_OR, 0);
05086   }
05087   if (!res && have_min_dir_info) {
05088     int quiet = directory_too_idle_to_fetch_descriptors(options, now);
05089     log(quiet ? LOG_INFO : LOG_NOTICE, LD_DIR,
05090         "Our directory information is no longer up-to-date "
05091         "enough to build circuits: %s", dir_info_status);
05092 
05093     /* a) make us log when we next complete a circuit, so we know when Tor
05094      * is back up and usable, and b) disable some activities that Tor
05095      * should only do while circuits are working, like reachability tests
05096      * and fetching bridge descriptors only over circuits. */
05097     can_complete_circuit = 0;
05098 
05099     control_event_client_status(LOG_NOTICE, "NOT_ENOUGH_DIR_INFO");
05100   }
05101   have_min_dir_info = res;
05102   need_to_update_have_min_dir_info = 0;
05103 }
05104 
05108 void
05109 router_reset_descriptor_download_failures(void)
05110 {
05111   networkstatus_reset_download_failures();
05112   last_descriptor_download_attempted = 0;
05113   if (!routerlist)
05114     return;
05115   SMARTLIST_FOREACH(routerlist->routers, routerinfo_t *, ri,
05116   {
05117     download_status_reset(&ri->cache_info.ei_dl_status);
05118   });
05119   SMARTLIST_FOREACH(routerlist->old_routers, signed_descriptor_t *, sd,
05120   {
05121     download_status_reset(&sd->ei_dl_status);
05122   });
05123 }
05124 
05127 #define ROUTER_MAX_COSMETIC_TIME_DIFFERENCE (2*60*60)
05128 
05130 #define ROUTER_ALLOW_UPTIME_DRIFT (6*60*60)
05131 
05135 int
05136 router_differences_are_cosmetic(const routerinfo_t *r1, const routerinfo_t *r2)
05137 {
05138   time_t r1pub, r2pub;
05139   long time_difference;
05140   tor_assert(r1 && r2);
05141 
05142   /* r1 should be the one that was published first. */
05143   if (r1->cache_info.published_on > r2->cache_info.published_on) {
05144     const routerinfo_t *ri_tmp = r2;
05145     r2 = r1;
05146     r1 = ri_tmp;
05147   }
05148 
05149   /* If any key fields differ, they're different. */
05150   if (strcasecmp(r1->address, r2->address) ||
05151       strcasecmp(r1->nickname, r2->nickname) ||
05152       r1->or_port != r2->or_port ||
05153       r1->dir_port != r2->dir_port ||
05154       r1->purpose != r2->purpose ||
05155       crypto_pk_cmp_keys(r1->onion_pkey, r2->onion_pkey) ||
05156       crypto_pk_cmp_keys(r1->identity_pkey, r2->identity_pkey) ||
05157       strcasecmp(r1->platform, r2->platform) ||
05158       (r1->contact_info && !r2->contact_info) || /* contact_info is optional */
05159       (!r1->contact_info && r2->contact_info) ||
05160       (r1->contact_info && r2->contact_info &&
05161        strcasecmp(r1->contact_info, r2->contact_info)) ||
05162       r1->is_hibernating != r2->is_hibernating ||
05163       cmp_addr_policies(r1->exit_policy, r2->exit_policy))
05164     return 0;
05165   if ((r1->declared_family == NULL) != (r2->declared_family == NULL))
05166     return 0;
05167   if (r1->declared_family && r2->declared_family) {
05168     int i, n;
05169     if (smartlist_len(r1->declared_family)!=smartlist_len(r2->declared_family))
05170       return 0;
05171     n = smartlist_len(r1->declared_family);
05172     for (i=0; i < n; ++i) {
05173       if (strcasecmp(smartlist_get(r1->declared_family, i),
05174                      smartlist_get(r2->declared_family, i)))
05175         return 0;
05176     }
05177   }
05178 
05179   /* Did bandwidth change a lot? */
05180   if ((r1->bandwidthcapacity < r2->bandwidthcapacity/2) ||
05181       (r2->bandwidthcapacity < r1->bandwidthcapacity/2))
05182     return 0;
05183 
05184   /* Did the bandwidthrate or bandwidthburst change? */
05185   if ((r1->bandwidthrate != r2->bandwidthrate) ||
05186       (r1->bandwidthburst != r2->bandwidthburst))
05187     return 0;
05188 
05189   /* Did more than 12 hours pass? */
05190   if (r1->cache_info.published_on + ROUTER_MAX_COSMETIC_TIME_DIFFERENCE
05191       < r2->cache_info.published_on)
05192     return 0;
05193 
05194   /* Did uptime fail to increase by approximately the amount we would think,
05195    * give or take some slop? */
05196   r1pub = r1->cache_info.published_on;
05197   r2pub = r2->cache_info.published_on;
05198   time_difference = labs(r2->uptime - (r1->uptime + (r2pub - r1pub)));
05199   if (time_difference > ROUTER_ALLOW_UPTIME_DRIFT &&
05200       time_difference > r1->uptime * .05 &&
05201       time_difference > r2->uptime * .05)
05202     return 0;
05203 
05204   /* Otherwise, the difference is cosmetic. */
05205   return 1;
05206 }
05207 
05216 int
05217 routerinfo_incompatible_with_extrainfo(const routerinfo_t *ri,
05218                                        extrainfo_t *ei,
05219                                        signed_descriptor_t *sd,
05220                                        const char **msg)
05221 {
05222   int digest_matches, r=1;
05223   tor_assert(ri);
05224   tor_assert(ei);
05225   if (!sd)
05226     sd = (signed_descriptor_t*)&ri->cache_info;
05227 
05228   if (ei->bad_sig) {
05229     if (msg) *msg = "Extrainfo signature was bad, or signed with wrong key.";
05230     return 1;
05231   }
05232 
05233   digest_matches = tor_memeq(ei->cache_info.signed_descriptor_digest,
05234                            sd->extra_info_digest, DIGEST_LEN);
05235 
05236   /* The identity must match exactly to have been generated at the same time
05237    * by the same router. */
05238   if (tor_memneq(ri->cache_info.identity_digest,
05239                  ei->cache_info.identity_digest,
05240                  DIGEST_LEN)) {
05241     if (msg) *msg = "Extrainfo nickname or identity did not match routerinfo";
05242     goto err; /* different servers */
05243   }
05244 
05245   if (ei->pending_sig) {
05246     char signed_digest[128];
05247     if (crypto_pk_public_checksig(ri->identity_pkey,
05248                        signed_digest, sizeof(signed_digest),
05249                        ei->pending_sig, ei->pending_sig_len) != DIGEST_LEN ||
05250         tor_memneq(signed_digest, ei->cache_info.signed_descriptor_digest,
05251                DIGEST_LEN)) {
05252       ei->bad_sig = 1;
05253       tor_free(ei->pending_sig);
05254       if (msg) *msg = "Extrainfo signature bad, or signed with wrong key";
05255       goto err; /* Bad signature, or no match. */
05256     }
05257 
05258     ei->cache_info.send_unencrypted = ri->cache_info.send_unencrypted;
05259     tor_free(ei->pending_sig);
05260   }
05261 
05262   if (ei->cache_info.published_on < sd->published_on) {
05263     if (msg) *msg = "Extrainfo published time did not match routerdesc";
05264     goto err;
05265   } else if (ei->cache_info.published_on > sd->published_on) {
05266     if (msg) *msg = "Extrainfo published time did not match routerdesc";
05267     r = -1;
05268     goto err;
05269   }
05270 
05271   if (!digest_matches) {
05272     if (msg) *msg = "Extrainfo digest did not match value from routerdesc";
05273     goto err; /* Digest doesn't match declared value. */
05274   }
05275 
05276   return 0;
05277  err:
05278   if (digest_matches) {
05279     /* This signature was okay, and the digest was right: This is indeed the
05280      * corresponding extrainfo.  But insanely, it doesn't match the routerinfo
05281      * that lists it.  Don't try to fetch this one again. */
05282     sd->extrainfo_is_bogus = 1;
05283   }
05284 
05285   return r;
05286 }
05287 
05290 void
05291 routerlist_assert_ok(const routerlist_t *rl)
05292 {
05293   routerinfo_t *r2;
05294   signed_descriptor_t *sd2;
05295   if (!rl)
05296     return;
05297   SMARTLIST_FOREACH(rl->routers, routerinfo_t *, r,
05298   {
05299     r2 = rimap_get(rl->identity_map, r->cache_info.identity_digest);
05300     tor_assert(r == r2);
05301     sd2 = sdmap_get(rl->desc_digest_map,
05302                     r->cache_info.signed_descriptor_digest);
05303     tor_assert(&(r->cache_info) == sd2);
05304     tor_assert(r->cache_info.routerlist_index == r_sl_idx);
05305     /* XXXX
05306      *
05307      *   Hoo boy.  We need to fix this one, and the fix is a bit tricky, so
05308      * commenting this out is just a band-aid.
05309      *
05310      *   The problem is that, although well-behaved router descriptors
05311      * should never have the same value for their extra_info_digest, it's
05312      * possible for ill-behaved routers to claim whatever they like there.
05313      *
05314      *   The real answer is to trash desc_by_eid_map and instead have
05315      * something that indicates for a given extra-info digest we want,
05316      * what its download status is.  We'll do that as a part of routerlist
05317      * refactoring once consensus directories are in.  For now,
05318      * this rep violation is probably harmless: an adversary can make us
05319      * reset our retry count for an extrainfo, but that's not the end
05320      * of the world.  Changing the representation in 0.2.0.x would just
05321      * destabilize the codebase.
05322     if (!tor_digest_is_zero(r->cache_info.extra_info_digest)) {
05323       signed_descriptor_t *sd3 =
05324         sdmap_get(rl->desc_by_eid_map, r->cache_info.extra_info_digest);
05325       tor_assert(sd3 == &(r->cache_info));
05326     }
05327     */
05328   });
05329   SMARTLIST_FOREACH(rl->old_routers, signed_descriptor_t *, sd,
05330   {
05331     r2 = rimap_get(rl->identity_map, sd->identity_digest);
05332     tor_assert(sd != &(r2->cache_info));
05333     sd2 = sdmap_get(rl->desc_digest_map, sd->signed_descriptor_digest);
05334     tor_assert(sd == sd2);
05335     tor_assert(sd->routerlist_index == sd_sl_idx);
05336     /* XXXX see above.
05337     if (!tor_digest_is_zero(sd->extra_info_digest)) {
05338       signed_descriptor_t *sd3 =
05339         sdmap_get(rl->desc_by_eid_map, sd->extra_info_digest);
05340       tor_assert(sd3 == sd);
05341     }
05342     */
05343   });
05344 
05345   RIMAP_FOREACH(rl->identity_map, d, r) {
05346     tor_assert(tor_memeq(r->cache_info.identity_digest, d, DIGEST_LEN));
05347   } DIGESTMAP_FOREACH_END;
05348   SDMAP_FOREACH(rl->desc_digest_map, d, sd) {
05349     tor_assert(tor_memeq(sd->signed_descriptor_digest, d, DIGEST_LEN));
05350   } DIGESTMAP_FOREACH_END;
05351   SDMAP_FOREACH(rl->desc_by_eid_map, d, sd) {
05352     tor_assert(!tor_digest_is_zero(d));
05353     tor_assert(sd);
05354     tor_assert(tor_memeq(sd->extra_info_digest, d, DIGEST_LEN));
05355   } DIGESTMAP_FOREACH_END;
05356   EIMAP_FOREACH(rl->extra_info_map, d, ei) {
05357     signed_descriptor_t *sd;
05358     tor_assert(tor_memeq(ei->cache_info.signed_descriptor_digest,
05359                        d, DIGEST_LEN));
05360     sd = sdmap_get(rl->desc_by_eid_map,
05361                    ei->cache_info.signed_descriptor_digest);
05362     // tor_assert(sd); // XXXX see above
05363     if (sd) {
05364       tor_assert(tor_memeq(ei->cache_info.signed_descriptor_digest,
05365                          sd->extra_info_digest, DIGEST_LEN));
05366     }
05367   } DIGESTMAP_FOREACH_END;
05368 }
05369 
05380 const char *
05381 esc_router_info(const routerinfo_t *router)
05382 {
05383   static char *info=NULL;
05384   char *esc_contact, *esc_platform;
05385   tor_free(info);
05386 
05387   if (!router)
05388     return NULL; /* we're exiting; just free the memory we use */
05389 
05390   esc_contact = esc_for_log(router->contact_info);
05391   esc_platform = esc_for_log(router->platform);
05392 
05393   tor_asprintf(&info, "Contact %s, Platform %s", esc_contact, esc_platform);
05394   tor_free(esc_contact);
05395   tor_free(esc_platform);
05396 
05397   return info;
05398 }
05399 
05402 static int
05403 _compare_routerinfo_by_id_digest(const void **a, const void **b)
05404 {
05405   routerinfo_t *first = *(routerinfo_t **)a, *second = *(routerinfo_t **)b;
05406   return fast_memcmp(first->cache_info.identity_digest,
05407                 second->cache_info.identity_digest,
05408                 DIGEST_LEN);
05409 }
05410 
05412 void
05413 routers_sort_by_identity(smartlist_t *routers)
05414 {
05415   smartlist_sort(routers, _compare_routerinfo_by_id_digest);
05416 }
05417 
05422 struct routerset_t {
05427   smartlist_t *list;
05429   strmap_t *names;
05431   digestmap_t *digests;
05434   smartlist_t *policies;
05435 
05438   char *description;
05439 
05441   smartlist_t *country_names;
05443   int n_countries;
05448   bitarray_t *countries;
05449 };
05450 
05452 routerset_t *
05453 routerset_new(void)
05454 {
05455   routerset_t *result = tor_malloc_zero(sizeof(routerset_t));
05456   result->list = smartlist_new();
05457   result->names = strmap_new();
05458   result->digests = digestmap_new();
05459   result->policies = smartlist_new();
05460   result->country_names = smartlist_new();
05461   return result;
05462 }
05463 
05466 static char *
05467 routerset_get_countryname(const char *c)
05468 {
05469   char *country;
05470 
05471   if (strlen(c) < 4 || c[0] !='{' || c[3] !='}')
05472     return NULL;
05473 
05474   country = tor_strndup(c+1, 2);
05475   tor_strlower(country);
05476   return country;
05477 }
05478 
05482 void
05483 routerset_refresh_countries(routerset_t *target)
05484 {
05485   int cc;
05486   bitarray_free(target->countries);
05487 
05488   if (!geoip_is_loaded()) {
05489     target->countries = NULL;
05490     target->n_countries = 0;
05491     return;
05492   }
05493   target->n_countries = geoip_get_n_countries();
05494   target->countries = bitarray_init_zero(target->n_countries);
05495   SMARTLIST_FOREACH_BEGIN(target->country_names, const char *, country) {
05496     cc = geoip_get_country(country);
05497     if (cc >= 0) {
05498       tor_assert(cc < target->n_countries);
05499       bitarray_set(target->countries, cc);
05500     } else {
05501       log(LOG_WARN, LD_CONFIG, "Country code '%s' is not recognized.",
05502           country);
05503     }
05504   } SMARTLIST_FOREACH_END(country);
05505 }
05506 
05515 int
05516 routerset_parse(routerset_t *target, const char *s, const char *description)
05517 {
05518   int r = 0;
05519   int added_countries = 0;
05520   char *countryname;
05521   smartlist_t *list = smartlist_new();
05522   smartlist_split_string(list, s, ",",
05523                          SPLIT_SKIP_SPACE | SPLIT_IGNORE_BLANK, 0);
05524   SMARTLIST_FOREACH_BEGIN(list, char *, nick) {
05525       addr_policy_t *p;
05526       if (is_legal_hexdigest(nick)) {
05527         char d[DIGEST_LEN];
05528         if (*nick == '$')
05529           ++nick;
05530         log_debug(LD_CONFIG, "Adding identity %s to %s", nick, description);
05531         base16_decode(d, sizeof(d), nick, HEX_DIGEST_LEN);
05532         digestmap_set(target->digests, d, (void*)1);
05533       } else if (is_legal_nickname(nick)) {
05534         log_debug(LD_CONFIG, "Adding nickname %s to %s", nick, description);
05535         strmap_set_lc(target->names, nick, (void*)1);
05536       } else if ((countryname = routerset_get_countryname(nick)) != NULL) {
05537         log_debug(LD_CONFIG, "Adding country %s to %s", nick,
05538                   description);
05539         smartlist_add(target->country_names, countryname);
05540         added_countries = 1;
05541       } else if ((strchr(nick,'.') || strchr(nick, '*')) &&
05542                  (p = router_parse_addr_policy_item_from_string(
05543                                      nick, ADDR_POLICY_REJECT))) {
05544         log_debug(LD_CONFIG, "Adding address %s to %s", nick, description);
05545         smartlist_add(target->policies, p);
05546       } else {
05547         log_warn(LD_CONFIG, "Entry '%s' in %s is misformed.", nick,
05548                  description);
05549         r = -1;
05550         tor_free(nick);
05551         SMARTLIST_DEL_CURRENT(list, nick);
05552       }
05553   } SMARTLIST_FOREACH_END(nick);
05554   smartlist_add_all(target->list, list);
05555   smartlist_free(list);
05556   if (added_countries)
05557     routerset_refresh_countries(target);
05558   return r;
05559 }
05560 
05564 void
05565 refresh_all_country_info(void)
05566 {
05567   const or_options_t *options = get_options();
05568 
05569   if (options->EntryNodes)
05570     routerset_refresh_countries(options->EntryNodes);
05571   if (options->ExitNodes)
05572     routerset_refresh_countries(options->ExitNodes);
05573   if (options->ExcludeNodes)
05574     routerset_refresh_countries(options->ExcludeNodes);
05575   if (options->ExcludeExitNodes)
05576     routerset_refresh_countries(options->ExcludeExitNodes);
05577   if (options->_ExcludeExitNodesUnion)
05578     routerset_refresh_countries(options->_ExcludeExitNodesUnion);
05579 
05580   nodelist_refresh_countries();
05581 }
05582 
05584 void
05585 routerset_union(routerset_t *target, const routerset_t *source)
05586 {
05587   char *s;
05588   tor_assert(target);
05589   if (!source || !source->list)
05590     return;
05591   s = routerset_to_string(source);
05592   routerset_parse(target, s, "other routerset");
05593   tor_free(s);
05594 }
05595 
05598 int
05599 routerset_is_list(const routerset_t *set)
05600 {
05601   return smartlist_len(set->country_names) == 0 &&
05602     smartlist_len(set->policies) == 0;
05603 }
05604 
05607 int
05608 routerset_needs_geoip(const routerset_t *set)
05609 {
05610   return set && smartlist_len(set->country_names);
05611 }
05612 
05614 int
05615 routerset_is_empty(const routerset_t *set)
05616 {
05617   return !set || smartlist_len(set->list) == 0;
05618 }
05619 
05627 static int
05628 routerset_contains(const routerset_t *set, const tor_addr_t *addr,
05629                    uint16_t orport,
05630                    const char *nickname, const char *id_digest,
05631                    country_t country)
05632 {
05633   if (!set || !set->list)
05634     return 0;
05635   if (nickname && strmap_get_lc(set->names, nickname))
05636     return 4;
05637   if (id_digest && digestmap_get(set->digests, id_digest))
05638     return 4;
05639   if (addr && compare_tor_addr_to_addr_policy(addr, orport, set->policies)
05640       == ADDR_POLICY_REJECTED)
05641     return 3;
05642   if (set->countries) {
05643     if (country < 0 && addr)
05644       country = geoip_get_country_by_ip(tor_addr_to_ipv4h(addr));
05645 
05646     if (country >= 0 && country < set->n_countries &&
05647         bitarray_is_set(set->countries, country))
05648       return 2;
05649   }
05650   return 0;
05651 }
05652 
05654 int
05655 routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei)
05656 {
05657   return routerset_contains(set,
05658                             &ei->addr,
05659                             ei->port,
05660                             ei->nickname,
05661                             ei->identity_digest,
05662                             -1 /*country*/);
05663 }
05664 
05667 int
05668 routerset_contains_router(const routerset_t *set, const routerinfo_t *ri,
05669                           country_t country)
05670 {
05671   tor_addr_t addr;
05672   tor_addr_from_ipv4h(&addr, ri->addr);
05673   return routerset_contains(set,
05674                             &addr,
05675                             ri->or_port,
05676                             ri->nickname,
05677                             ri->cache_info.identity_digest,
05678                             country);
05679 }
05680 
05683 int
05684 routerset_contains_routerstatus(const routerset_t *set,
05685                                 const routerstatus_t *rs,
05686                                 country_t country)
05687 {
05688   tor_addr_t addr;
05689   tor_addr_from_ipv4h(&addr, rs->addr);
05690   return routerset_contains(set,
05691                             &addr,
05692                             rs->or_port,
05693                             rs->nickname,
05694                             rs->identity_digest,
05695                             country);
05696 }
05697 
05699 int
05700 routerset_contains_node(const routerset_t *set, const node_t *node)
05701 {
05702   if (node->rs)
05703     return routerset_contains_routerstatus(set, node->rs, node->country);
05704   else if (node->ri)
05705     return routerset_contains_router(set, node->ri, node->country);
05706   else
05707     return 0;
05708 }
05709 
05713 void
05714 routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset,
05715                         const routerset_t *excludeset, int running_only)
05716 { /* XXXX MOVE */
05717   tor_assert(out);
05718   if (!routerset || !routerset->list)
05719     return;
05720 
05721   if (routerset_is_list(routerset)) {
05722     /* No routers are specified by type; all are given by name or digest.
05723      * we can do a lookup in O(len(routerset)). */
05724     SMARTLIST_FOREACH(routerset->list, const char *, name, {
05725         const node_t *node = node_get_by_nickname(name, 1);
05726         if (node) {
05727           if (!running_only || node->is_running)
05728             if (!routerset_contains_node(excludeset, node))
05729               smartlist_add(out, (void*)node);
05730         }
05731     });
05732   } else {
05733     /* We need to iterate over the routerlist to get all the ones of the
05734      * right kind. */
05735     smartlist_t *nodes = nodelist_get_list();
05736     SMARTLIST_FOREACH(nodes, const node_t *, node, {
05737         if (running_only && !node->is_running)
05738           continue;
05739         if (routerset_contains_node(routerset, node) &&
05740             !routerset_contains_node(excludeset, node))
05741           smartlist_add(out, (void*)node);
05742     });
05743   }
05744 }
05745 
05746 #if 0
05747 
05755 void
05756 routersets_get_node_disjunction(smartlist_t *target,
05757                            const smartlist_t *source,
05758                            const routerset_t *include,
05759                            const routerset_t *exclude, int running_only)
05760 {
05761   SMARTLIST_FOREACH(source, const node_t *, node, {
05762     int include_result;
05763     if (running_only && !node->is_running)
05764       continue;
05765     if (!routerset_is_empty(include))
05766       include_result = routerset_contains_node(include, node);
05767     else
05768       include_result = 1;
05769 
05770     if (include_result) {
05771       int exclude_result = routerset_contains_node(exclude, node);
05772       if (include_result >= exclude_result)
05773         smartlist_add(target, (void*)node);
05774     }
05775   });
05776 }
05777 #endif
05778 
05780 void
05781 routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
05782 { /*XXXX MOVE ? */
05783   tor_assert(lst);
05784   if (!routerset)
05785     return;
05786   SMARTLIST_FOREACH(lst, const node_t *, node, {
05787       if (routerset_contains_node(routerset, node)) {
05788         //log_debug(LD_DIR, "Subtracting %s",r->nickname);
05789         SMARTLIST_DEL_CURRENT(lst, node);
05790       }
05791     });
05792 }
05793 
05796 char *
05797 routerset_to_string(const routerset_t *set)
05798 {
05799   if (!set || !set->list)
05800     return tor_strdup("");
05801   return smartlist_join_strings(set->list, ",", 0, NULL);
05802 }
05803 
05806 int
05807 routerset_equal(const routerset_t *old, const routerset_t *new)
05808 {
05809   if (routerset_is_empty(old) && routerset_is_empty(new)) {
05810     /* Two empty sets are equal */
05811     return 1;
05812   } else if (routerset_is_empty(old) || routerset_is_empty(new)) {
05813     /* An empty set is equal to nothing else. */
05814     return 0;
05815   }
05816   tor_assert(old != NULL);
05817   tor_assert(new != NULL);
05818 
05819   if (smartlist_len(old->list) != smartlist_len(new->list))
05820     return 0;
05821 
05822   SMARTLIST_FOREACH(old->list, const char *, cp1, {
05823     const char *cp2 = smartlist_get(new->list, cp1_sl_idx);
05824     if (strcmp(cp1, cp2))
05825       return 0;
05826   });
05827 
05828   return 1;
05829 }
05830 
05832 void
05833 routerset_free(routerset_t *routerset)
05834 {
05835   if (!routerset)
05836     return;
05837 
05838   SMARTLIST_FOREACH(routerset->list, char *, cp, tor_free(cp));
05839   smartlist_free(routerset->list);
05840   SMARTLIST_FOREACH(routerset->policies, addr_policy_t *, p,
05841                     addr_policy_free(p));
05842   smartlist_free(routerset->policies);
05843   SMARTLIST_FOREACH(routerset->country_names, char *, cp, tor_free(cp));
05844   smartlist_free(routerset->country_names);
05845 
05846   strmap_free(routerset->names, NULL);
05847   digestmap_free(routerset->digests, NULL);
05848   bitarray_free(routerset->countries);
05849   tor_free(routerset);
05850 }
05851 
05854 void
05855 node_set_country(node_t *node)
05856 {
05857   if (node->rs)
05858     node->country = geoip_get_country_by_ip(node->rs->addr);
05859   else if (node->ri)
05860     node->country = geoip_get_country_by_ip(node->ri->addr);
05861   else
05862     node->country = -1;
05863 }
05864 
05866 void
05867 nodelist_refresh_countries(void) /* MOVE */
05868 {
05869   smartlist_t *nodes = nodelist_get_list();
05870   SMARTLIST_FOREACH(nodes, node_t *, node,
05871                     node_set_country(node));
05872 }
05873 
05878 int
05879 hid_serv_get_responsible_directories(smartlist_t *responsible_dirs,
05880                                      const char *id)
05881 {
05882   int start, found, n_added = 0, i;
05883   networkstatus_t *c = networkstatus_get_latest_consensus();
05884   if (!c || !smartlist_len(c->routerstatus_list)) {
05885     log_warn(LD_REND, "We don't have a consensus, so we can't perform v2 "
05886              "rendezvous operations.");
05887     return -1;
05888   }
05889   tor_assert(id);
05890   start = networkstatus_vote_find_entry_idx(c, id, &found);
05891   if (start == smartlist_len(c->routerstatus_list)) start = 0;
05892   i = start;
05893   do {
05894     routerstatus_t *r = smartlist_get(c->routerstatus_list, i);
05895     if (r->is_hs_dir) {
05896       smartlist_add(responsible_dirs, r);
05897       if (++n_added == REND_NUMBER_OF_CONSECUTIVE_REPLICAS)
05898         return 0;
05899     }
05900     if (++i == smartlist_len(c->routerstatus_list))
05901       i = 0;
05902   } while (i != start);
05903 
05904   /* Even though we don't have the desired number of hidden service
05905    * directories, be happy if we got any. */
05906   return smartlist_len(responsible_dirs) ? 0 : -1;
05907 }
05908 
05911 int
05912 hid_serv_acting_as_directory(void)
05913 {
05914   const routerinfo_t *me = router_get_my_routerinfo();
05915   if (!me)
05916     return 0;
05917   if (!get_options()->HidServDirectoryV2) {
05918     log_info(LD_REND, "We are not acting as hidden service directory, "
05919                       "because we have not been configured as such.");
05920     return 0;
05921   }
05922   return 1;
05923 }
05924 
05927 int
05928 hid_serv_responsible_for_desc_id(const char *query)
05929 {
05930   const routerinfo_t *me;
05931   routerstatus_t *last_rs;
05932   const char *my_id, *last_id;
05933   int result;
05934   smartlist_t *responsible;
05935   if (!hid_serv_acting_as_directory())
05936     return 0;
05937   if (!(me = router_get_my_routerinfo()))
05938     return 0; /* This is redundant, but let's be paranoid. */
05939   my_id = me->cache_info.identity_digest;
05940   responsible = smartlist_new();
05941   if (hid_serv_get_responsible_directories(responsible, query) < 0) {
05942     smartlist_free(responsible);
05943     return 0;
05944   }
05945   last_rs = smartlist_get(responsible, smartlist_len(responsible)-1);
05946   last_id = last_rs->identity_digest;
05947   result = rend_id_is_in_interval(my_id, query, last_id);
05948   smartlist_free(responsible);
05949   return result;
05950 }
05951