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