src/or/microdesc.c

   1 /* Copyright (c) 2009-2010, The Tor Project, Inc. */
   2 /* See LICENSE for licensing information */
   3
   4 #include "or.h"
   5 #include "config.h"
   6 #include "microdesc.h"
   7 #include "routerparse.h"
   8
   9 /** A data structure to hold a bunch of cached microdescriptors.  There are
  10  * two active files in the cache: a "cache file" that we mmap, and a "journal
  11  * file" that we append to.  Periodically, we rebuild the cache file to hold
  12  * only the microdescriptors that we want to keep */
  13 struct microdesc_cache_t {
  14   /** Map from sha256-digest to microdesc_t for every microdesc_t in the
  15    * cache. */
  16   HT_HEAD(microdesc_map, microdesc_t) map;
  17
  18   /** Name of the cache file. */
  19   char *cache_fname;
  20   /** Name of the journal file. */
  21   char *journal_fname;
  22   /** Mmap'd contents of the cache file, or NULL if there is none. */
  23   tor_mmap_t *cache_content;
  24   /** Number of bytes used in the journal file. */
  25   size_t journal_len;
  26
  27   /** Total bytes of microdescriptor bodies we have added to this cache */
  28   uint64_t total_len_seen;
  29   /** Total number of microdescriptors we have added to this cache */
  30   unsigned n_seen;
  31 };
  32
  33 /** Helper: computes a hash of <b>md</b> to place it in a hash table. */
  34 static INLINE unsigned int
  35 _microdesc_hash(microdesc_t *md)
  36 {
  37   unsigned *d = (unsigned*)md->digest;
  38 #if SIZEOF_INT == 4
  39   return d[0] ^ d[1] ^ d[2] ^ d[3] ^ d[4] ^ d[5] ^ d[6] ^ d[7];
  40 #else
  41   return d[0] ^ d[1] ^ d[2] ^ d[3];
  42 #endif
  43 }
  44
  45 /** Helper: compares <b>a</b> and </b> for equality for hash-table purposes. */
  46 static INLINE int
  47 _microdesc_eq(microdesc_t *a, microdesc_t *b)
  48 {
  49   return !memcmp(a->digest, b->digest, DIGEST256_LEN);
  50 }
  51
  52 HT_PROTOTYPE(microdesc_map, microdesc_t, node,
  53              _microdesc_hash, _microdesc_eq);
  54 HT_GENERATE(microdesc_map, microdesc_t, node,
  55              _microdesc_hash, _microdesc_eq, 0.6,
  56              malloc, realloc, free);
  57
  58 /** Write the body of <b>md</b> into <b>f</b>, with appropriate annotations.
  59  * On success, return the total number of bytes written, and set
  60  * *<b>annotation_len_out</b> to the number of bytes written as
  61  * annotations. */
  62 static ssize_t
  63 dump_microdescriptor(FILE *f, microdesc_t *md, size_t *annotation_len_out)
  64 {
  65   ssize_t r = 0;
  66   size_t written;
  67   /* XXXX drops unkown annotations. */
  68   if (md->last_listed) {
  69     char buf[ISO_TIME_LEN+1];
  70     char annotation[ISO_TIME_LEN+32];
  71     format_iso_time(buf, md->last_listed);
  72     tor_snprintf(annotation, sizeof(annotation), "@last-listed %s\n", buf);
  73     fputs(annotation, f);
  74     r += strlen(annotation);
  75     *annotation_len_out = r;
  76   } else {
  77     *annotation_len_out = 0;
  78   }
  79
  80   md->off = (off_t) ftell(f);
  81   written = fwrite(md->body, 1, md->bodylen, f);
  82   if (written != md->bodylen) {
  83     log_warn(LD_DIR,
  84              "Couldn't dump microdescriptor (wrote %lu out of %lu): %s",
  85              (unsigned long)written, (unsigned long)md->bodylen,
  86              strerror(ferror(f)));
  87     return -1;
  88   }
  89   r += md->bodylen;
  90   return r;
  91 }
  92
  93 /** Holds a pointer to the current microdesc_cache_t object, or NULL if no
  94  * such object has been allocated. */
  95 static microdesc_cache_t *the_microdesc_cache = NULL;
  96
  97 /** Return a pointer to the microdescriptor cache, loading it if necessary. */
  98 microdesc_cache_t *
  99 get_microdesc_cache(void)
 100 {
 101   if (PREDICT_UNLIKELY(the_microdesc_cache==NULL)) {
 102     microdesc_cache_t *cache = tor_malloc_zero(sizeof(microdesc_cache_t));
 103     HT_INIT(microdesc_map, &cache->map);
 104     cache->cache_fname = get_datadir_fname("cached-microdescs");
 105     cache->journal_fname = get_datadir_fname("cached-microdescs.new");
 106     microdesc_cache_reload(cache);
 107     the_microdesc_cache = cache;
 108   }
 109   return the_microdesc_cache;
 110 }
 111
 112 /* There are three sources of microdescriptors:
 113    1) Generated by us while acting as a directory authority.
 114    2) Loaded from the cache on disk.
 115    3) Downloaded.
 116 */
 117
 118 /** Decode the microdescriptors from the string starting at <b>s</b> and
 119  * ending at <b>eos</b>, and store them in <b>cache</b>.  If <b>no-save</b>,
 120  * mark them as non-writable to disk.  If <b>where</b> is SAVED_IN_CACHE,
 121  * leave their bodies as pointers to the mmap'd cache.  If where is
 122  * <b>SAVED_NOWHERE</b>, do not allow annotations.  Return a list of the added
 123  * microdescriptors.  */
 124 smartlist_t *
 125 microdescs_add_to_cache(microdesc_cache_t *cache,
 126                         const char *s, const char *eos, saved_location_t where,
 127                         int no_save)
 128 {
 129   /*XXXX need an argument that sets last_listed as appropriate. */
 130
 131   smartlist_t *descriptors, *added;
 132   const int allow_annotations = (where != SAVED_NOWHERE);
 133   const int copy_body = (where != SAVED_IN_CACHE);
 134
 135   descriptors = microdescs_parse_from_string(s, eos,
 136                                              allow_annotations,
 137                                              copy_body);
 138
 139   added = microdescs_add_list_to_cache(cache, descriptors, where, no_save);
 140   smartlist_free(descriptors);
 141   return added;
 142 }
 143
 144 /* As microdescs_add_to_cache, but takes a list of micrdescriptors instead of
 145  * a string to encode.  Frees any members of <b>descriptors</b> that it does
 146  * not add. */
 147 smartlist_t *
 148 microdescs_add_list_to_cache(microdesc_cache_t *cache,
 149                              smartlist_t *descriptors, saved_location_t where,
 150                              int no_save)
 151 {
 152   smartlist_t *added;
 153   open_file_t *open_file = NULL;
 154   FILE *f = NULL;
 155   //  int n_added = 0;
 156   ssize_t size = 0;
 157
 158   if (where == SAVED_NOWHERE && !no_save) {
 159     f = start_writing_to_stdio_file(cache->journal_fname,
 160                                     OPEN_FLAGS_APPEND|O_BINARY,
 161                                     0600, &open_file);
 162     if (!f) {
 163       log_warn(LD_DIR, "Couldn't append to journal in %s: %s",
 164                cache->journal_fname, strerror(errno));
 165       return NULL;
 166     }
 167   }
 168
 169   added = smartlist_create();
 170   SMARTLIST_FOREACH_BEGIN(descriptors, microdesc_t *, md) {
 171     microdesc_t *md2;
 172     md2 = HT_FIND(microdesc_map, &cache->map, md);
 173     if (md2) {
 174       /* We already had this one. */
 175       if (md2->last_listed < md->last_listed)
 176         md2->last_listed = md->last_listed;
 177       microdesc_free(md);
 178       continue;
 179     }
 180
 181     /* Okay, it's a new one. */
 182     if (f) {
 183       size_t annotation_len;
 184       size = dump_microdescriptor(f, md, &annotation_len);
 185       if (size < 0) {
 186         /* XXX handle errors from dump_microdescriptor() */
 187         /* log?  return -1?  die?  coredump the universe? */
 188         continue;
 189       }
 190       md->saved_location = SAVED_IN_JOURNAL;
 191       cache->journal_len += size;
 192     } else {
 193       md->saved_location = where;
 194     }
 195
 196     md->no_save = no_save;
 197
 198     HT_INSERT(microdesc_map, &cache->map, md);
 199     smartlist_add(added, md);
 200     ++cache->n_seen;
 201     cache->total_len_seen += md->bodylen;
 202   } SMARTLIST_FOREACH_END(md);
 203
 204   if (f)
 205     finish_writing_to_file(open_file); /*XXX Check me.*/
 206
 207   {
 208     size_t old_content_len =
 209       cache->cache_content ? cache->cache_content->size : 0;
 210     if (cache->journal_len > 16384 + old_content_len &&
 211         cache->journal_len > old_content_len * 2) {
 212       microdesc_cache_rebuild(cache);
 213     }
 214   }
 215
 216   return added;
 217 }
 218
 219 /** Remove every microdescriptor in <b>cache</b>. */
 220 void
 221 microdesc_cache_clear(microdesc_cache_t *cache)
 222 {
 223   microdesc_t **entry, **next;
 224   for (entry = HT_START(microdesc_map, &cache->map); entry; entry = next) {
 225     microdesc_t *md = *entry;
 226     next = HT_NEXT_RMV(microdesc_map, &cache->map, entry);
 227     microdesc_free(md);
 228   }
 229   HT_CLEAR(microdesc_map, &cache->map);
 230   if (cache->cache_content) {
 231     tor_munmap_file(cache->cache_content);
 232     cache->cache_content = NULL;
 233   }
 234   cache->total_len_seen = 0;
 235   cache->n_seen = 0;
 236 }
 237
 238 /** Reload the contents of <b>cache</b> from disk.  If it is empty, load it
 239  * for the first time.  Return 0 on success, -1 on failure. */
 240 int
 241 microdesc_cache_reload(microdesc_cache_t *cache)
 242 {
 243   struct stat st;
 244   char *journal_content;
 245   smartlist_t *added;
 246   tor_mmap_t *mm;
 247   int total = 0;
 248
 249   microdesc_cache_clear(cache);
 250
 251   mm = cache->cache_content = tor_mmap_file(cache->cache_fname);
 252   if (mm) {
 253     added = microdescs_add_to_cache(cache, mm->data, mm->data+mm->size,
 254                                     SAVED_IN_CACHE, 0);
 255     if (added) {
 256       total += smartlist_len(added);
 257       smartlist_free(added);
 258     }
 259   }
 260
 261   journal_content = read_file_to_str(cache->journal_fname,
 262                                      RFTS_IGNORE_MISSING, &st);
 263   if (journal_content) {
 264     added = microdescs_add_to_cache(cache, journal_content,
 265                                     journal_content+st.st_size,
 266                                     SAVED_IN_JOURNAL, 0);
 267     if (added) {
 268       total += smartlist_len(added);
 269       smartlist_free(added);
 270     }
 271     tor_free(journal_content);
 272   }
 273   log_notice(LD_DIR, "Reloaded microdescriptor cache.  Found %d descriptors.",
 274              total);
 275   return 0;
 276 }
 277
 278 /** Regenerate the main cache file for <b>cache</b>, clear the journal file,
 279  * and update every microdesc_t in the cache with pointers to its new
 280  * location. */
 281 int
 282 microdesc_cache_rebuild(microdesc_cache_t *cache)
 283 {
 284   open_file_t *open_file;
 285   FILE *f;
 286   microdesc_t **mdp;
 287   smartlist_t *wrote;
 288   ssize_t size;
 289   off_t off = 0;
 290   int orig_size, new_size;
 291
 292   log_info(LD_DIR, "Rebuilding the microdescriptor cache...");
 293   orig_size = (int)(cache->cache_content ? cache->cache_content->size : 0);
 294   orig_size += (int)cache->journal_len;
 295
 296   f = start_writing_to_stdio_file(cache->cache_fname,
 297                                   OPEN_FLAGS_REPLACE|O_BINARY,
 298                                   0600, &open_file);
 299   if (!f)
 300     return -1;
 301
 302   wrote = smartlist_create();
 303
 304   HT_FOREACH(mdp, microdesc_map, &cache->map) {
 305     microdesc_t *md = *mdp;
 306     size_t annotation_len;
 307     if (md->no_save)
 308       continue;
 309
 310     size = dump_microdescriptor(f, md, &annotation_len);
 311     if (size < 0) {
 312       /* XXX handle errors from dump_microdescriptor() */
 313       /* log?  return -1?  die?  coredump the universe? */
 314       continue;
 315     }
 316     md->off = off + annotation_len;
 317     off += size;
 318     if (md->saved_location != SAVED_IN_CACHE) {
 319       tor_free(md->body);
 320       md->saved_location = SAVED_IN_CACHE;
 321     }
 322     smartlist_add(wrote, md);
 323   }
 324
 325   finish_writing_to_file(open_file); /*XXX Check me.*/
 326
 327   if (cache->cache_content)
 328     tor_munmap_file(cache->cache_content);
 329   cache->cache_content = tor_mmap_file(cache->cache_fname);
 330
 331   if (!cache->cache_content && smartlist_len(wrote)) {
 332     log_err(LD_DIR, "Couldn't map file that we just wrote to %s!",
 333             cache->cache_fname);
 334     smartlist_free(wrote);
 335     return -1;
 336   }
 337   SMARTLIST_FOREACH_BEGIN(wrote, microdesc_t *, md) {
 338     tor_assert(md->saved_location == SAVED_IN_CACHE);
 339     md->body = (char*)cache->cache_content->data + md->off;
 340     tor_assert(!memcmp(md->body, "onion-key", 9));
 341   } SMARTLIST_FOREACH_END(md);
 342
 343   smartlist_free(wrote);
 344
 345   write_str_to_file(cache->journal_fname, "", 1);
 346   cache->journal_len = 0;
 347
 348   new_size = (int)cache->cache_content->size;
 349   log_info(LD_DIR, "Done rebuilding microdesc cache. "
 350            "Saved %d bytes; %d still used.",
 351            orig_size-new_size, new_size);
 352
 353   return 0;
 354 }
 355
 356 /** Deallocate a single microdescriptor.  Note: the microdescriptor MUST have
 357  * previously been removed from the cache if it had ever been inserted. */
 358 void
 359 microdesc_free(microdesc_t *md)
 360 {
 361   if (!md)
 362     return;
 363   /* Must be removed from hash table! */
 364   if (md->onion_pkey)
 365     crypto_free_pk_env(md->onion_pkey);
 366   if (md->body && md->saved_location != SAVED_IN_CACHE)
 367     tor_free(md->body);
 368
 369   if (md->family) {
 370     SMARTLIST_FOREACH(md->family, char *, cp, tor_free(cp));
 371     smartlist_free(md->family);
 372   }
 373   tor_free(md->exitsummary);
 374
 375   tor_free(md);
 376 }
 377
 378 /** Free all storage held in the microdesc.c module. */
 379 void
 380 microdesc_free_all(void)
 381 {
 382   if (the_microdesc_cache) {
 383     microdesc_cache_clear(the_microdesc_cache);
 384     tor_free(the_microdesc_cache->cache_fname);
 385     tor_free(the_microdesc_cache->journal_fname);
 386     tor_free(the_microdesc_cache);
 387   }
 388 }
 389
 390 /** If there is a microdescriptor in <b>cache</b> whose sha256 digest is
 391  * <b>d</b>, return it.  Otherwise return NULL. */
 392 microdesc_t *
 393 microdesc_cache_lookup_by_digest256(microdesc_cache_t *cache, const char *d)
 394 {
 395   microdesc_t *md, search;
 396   if (!cache)
 397     cache = get_microdesc_cache();
 398   memcpy(search.digest, d, DIGEST256_LEN);
 399   md = HT_FIND(microdesc_map, &cache->map, &search);
 400   return md;
 401 }
 402
 403 /** Return the mean size of decriptors added to <b>cache</b> since it was last
 404  * cleared.  Used to estimate the size of large downloads. */
 405 size_t
 406 microdesc_average_size(microdesc_cache_t *cache)
 407 {
 408   if (!cache)
 409     cache = get_microdesc_cache();
 410   if (!cache->n_seen)
 411     return 512;
 412   return (size_t)(cache->total_len_seen / cache->n_seen);
 413 }
 414