src/fs/fs_tree.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2009-2011 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      Affero General Public License for more details.
  14 */
  15 /**
  16  * @file fs/fs_tree.c
  17  * @brief Merkle-tree-ish-CHK file encoding for GNUnet
  18  * @see http://gnunet.org/encoding.php3
  19  * @author Krista Bennett
  20  * @author Christian Grothoff
  21  */
  22 #include "platform.h"
  23 #include "fs_tree.h"
  24
  25
  26 /**
  27  * Context for an ECRS-based file encoder that computes
  28  * the Merkle-ish-CHK tree.
  29  */
  30 struct GNUNET_FS_TreeEncoder
  31 {
  32
  33   /**
  34    * Global FS context.
  35    */
  36   struct GNUNET_FS_Handle *h;
  37
  38   /**
  39    * Closure for all callbacks.
  40    */
  41   void *cls;
  42
  43   /**
  44    * Function to call on encrypted blocks.
  45    */
  46   GNUNET_FS_TreeBlockProcessor proc;
  47
  48   /**
  49    * Function to call with progress information.
  50    */
  51   GNUNET_FS_TreeProgressCallback progress;
  52
  53   /**
  54    * Function to call to receive input data.
  55    */
  56   GNUNET_FS_DataReader reader;
  57
  58   /**
  59    * Function to call once we're done with processing.
  60    */
  61   GNUNET_SCHEDULER_TaskCallback cont;
  62
  63   /**
  64    * Set to an error message (if we had an error).
  65    */
  66   char *emsg;
  67
  68   /**
  69    * Set to the URI (upon successful completion)
  70    */
  71   struct GNUNET_FS_Uri *uri;
  72
  73   /**
  74    * Overall file size.
  75    */
  76   uint64_t size;
  77
  78   /**
  79    * How far are we?
  80    */
  81   uint64_t publish_offset;
  82
  83   /**
  84    * How deep are we?  Depth 0 is for the DBLOCKs.
  85    */
  86   unsigned int current_depth;
  87
  88   /**
  89    * How deep is the tree? Always > 0.
  90    */
  91   unsigned int chk_tree_depth;
  92
  93   /**
  94    * In-memory cache of the current CHK tree.
  95    * This struct will contain the CHK values
  96    * from the root to the currently processed
  97    * node in the tree as identified by
  98    * "current_depth" and "publish_offset".
  99    * The "chktree" will be initially NULL,
 100    * then allocated to a sufficient number of
 101    * entries for the size of the file and
 102    * finally freed once the upload is complete.
 103    */
 104   struct ContentHashKey *chk_tree;
 105
 106   /**
 107    * Are we currently in 'GNUNET_FS_tree_encoder_next'?
 108    * Flag used to prevent recursion.
 109    */
 110   int in_next;
 111 };
 112
 113
 114 /**
 115  * Compute the depth of the CHK tree.
 116  *
 117  * @param flen file length for which to compute the depth
 118  * @return depth of the tree, always > 0.  A depth of 1 means only a DBLOCK.
 119  */
 120 unsigned int
 121 GNUNET_FS_compute_depth (uint64_t flen)
 122 {
 123   unsigned int treeDepth;
 124   uint64_t fl;
 125
 126   treeDepth = 1;
 127   fl = DBLOCK_SIZE;
 128   while (fl < flen)
 129   {
 130     treeDepth++;
 131     if (fl * CHK_PER_INODE < fl)
 132     {
 133       /* integer overflow, this is a HUGE file... */
 134       return treeDepth;
 135     }
 136     fl = fl * CHK_PER_INODE;
 137   }
 138   return treeDepth;
 139 }
 140
 141
 142 /**
 143  * Calculate how many bytes of payload a block tree of the given
 144  * depth MAY correspond to at most (this function ignores the fact that
 145  * some blocks will only be present partially due to the total file
 146  * size cutting some blocks off at the end).
 147  *
 148  * @param depth depth of the block.  depth==0 is a DBLOCK.
 149  * @return number of bytes of payload a subtree of this depth may correspond to
 150  */
 151 uint64_t
 152 GNUNET_FS_tree_compute_tree_size (unsigned int depth)
 153 {
 154   uint64_t rsize;
 155   unsigned int i;
 156
 157   rsize = DBLOCK_SIZE;
 158   for (i = 0; i < depth; i++)
 159     rsize *= CHK_PER_INODE;
 160   return rsize;
 161 }
 162
 163
 164 /**
 165  * Compute the size of the current IBLOCK.  The encoder is
 166  * triggering the calculation of the size of an IBLOCK at the
 167  * *end* (hence end_offset) of its construction.  The IBLOCK
 168  * maybe a full or a partial IBLOCK, and this function is to
 169  * calculate how long it should be.
 170  *
 171  * @param depth depth of the IBlock in the tree, 0 would be a DBLOCK,
 172  *        must be > 0 (this function is for IBLOCKs only!)
 173  * @param end_offset current offset in the payload (!) of the overall file,
 174  *        must be > 0 (since this function is called at the
 175  *        end of a block).
 176  * @return size of the corresponding IBlock
 177  */
 178 static uint16_t
 179 GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset)
 180 {
 181   unsigned int ret;
 182   uint64_t mod;
 183   uint64_t bds;
 184
 185   GNUNET_assert (depth > 0);
 186   GNUNET_assert (end_offset > 0);
 187   bds = GNUNET_FS_tree_compute_tree_size (depth);
 188   mod = end_offset % bds;
 189   if (0 == mod)
 190   {
 191     /* we were triggered at the end of a full block */
 192     ret = CHK_PER_INODE;
 193   }
 194   else
 195   {
 196     /* we were triggered at the end of the file */
 197     bds /= CHK_PER_INODE;
 198     ret = mod / bds;
 199     if (0 != mod % bds)
 200       ret++;
 201   }
 202   return (uint16_t) (ret * sizeof (struct ContentHashKey));
 203 }
 204
 205
 206 /**
 207  * Compute how many bytes of data should be stored in
 208  * the specified block.
 209  *
 210  * @param fsize overall file size, must be > 0.
 211  * @param offset offset in the original data corresponding
 212  *         to the beginning of the tree induced by the block;
 213  *         must be <= fsize
 214  * @param depth depth of the node in the tree, 0 for DBLOCK
 215  * @return number of bytes stored in this node
 216  */
 217 size_t
 218 GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset,
 219                                      unsigned int depth)
 220 {
 221   size_t ret;
 222   uint64_t rsize;
 223   uint64_t epos;
 224   unsigned int chks;
 225
 226   GNUNET_assert (fsize > 0);
 227   GNUNET_assert (offset <= fsize);
 228   if (depth == 0)
 229   {
 230     ret = DBLOCK_SIZE;
 231     if ((offset + ret > fsize) || (offset + ret < offset))
 232       ret = (size_t) (fsize - offset);
 233     return ret;
 234   }
 235
 236   rsize = GNUNET_FS_tree_compute_tree_size (depth - 1);
 237   epos = offset + rsize * CHK_PER_INODE;
 238   if ((epos < offset) || (epos > fsize))
 239     epos = fsize;
 240   /* round up when computing #CHKs in our IBlock */
 241   chks = (epos - offset + rsize - 1) / rsize;
 242   GNUNET_assert (chks <= CHK_PER_INODE);
 243   return chks * sizeof (struct ContentHashKey);
 244 }
 245
 246
 247 /**
 248  * Initialize a tree encoder.  This function will call @a proc and
 249  * "progress" on each block in the tree.  Once all blocks have been
 250  * processed, "cont" will be scheduled.  The @a reader will be called
 251  * to obtain the (plaintext) blocks for the file.  Note that this
 252  * function will not actually call @a proc.  The client must
 253  * call #GNUNET_FS_tree_encoder_next to trigger encryption (and
 254  * calling of @a proc) for the each block.
 255  *
 256  * @param h the global FS context
 257  * @param size overall size of the file to encode
 258  * @param cls closure for reader, proc, progress and cont
 259  * @param reader function to call to read plaintext data
 260  * @param proc function to call on each encrypted block
 261  * @param progress function to call with progress information
 262  * @param cont function to call when done
 263  */
 264 struct GNUNET_FS_TreeEncoder *
 265 GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, uint64_t size,
 266                                void *cls,
 267                                GNUNET_FS_DataReader reader,
 268                                GNUNET_FS_TreeBlockProcessor proc,
 269                                GNUNET_FS_TreeProgressCallback progress,
 270                                GNUNET_SCHEDULER_TaskCallback cont)
 271 {
 272   struct GNUNET_FS_TreeEncoder *te;
 273
 274   te = GNUNET_new (struct GNUNET_FS_TreeEncoder);
 275   te->h = h;
 276   te->size = size;
 277   te->cls = cls;
 278   te->reader = reader;
 279   te->proc = proc;
 280   te->progress = progress;
 281   te->cont = cont;
 282   te->chk_tree_depth = GNUNET_FS_compute_depth (size);
 283   te->chk_tree
 284     = GNUNET_new_array (te->chk_tree_depth * CHK_PER_INODE,
 285                         struct ContentHashKey);
 286   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 287               "Created tree encoder for file with %llu bytes and depth %u\n",
 288               (unsigned long long) size,
 289               te->chk_tree_depth);
 290   return te;
 291 }
 292
 293
 294 /**
 295  * Compute the offset of the CHK for the
 296  * current block in the IBlock above.
 297  *
 298  * @param depth depth of the IBlock in the tree (aka overall
 299  *               number of tree levels minus depth); 0 == DBlock
 300  * @param end_offset current offset in the overall file,
 301  *               at the *beginning* of the block for DBLOCKs (depth==0),
 302  *               otherwise at the *end* of the block (exclusive)
 303  * @return (array of CHKs') offset in the above IBlock
 304  */
 305 static unsigned int
 306 compute_chk_offset (unsigned int depth, uint64_t end_offset)
 307 {
 308   uint64_t bds;
 309   unsigned int ret;
 310
 311   bds = GNUNET_FS_tree_compute_tree_size (depth);
 312   if (depth > 0)
 313     end_offset--;               /* round down since for depth > 0 offset is at the END of the block */
 314   ret = end_offset / bds;
 315   return ret % CHK_PER_INODE;
 316 }
 317
 318
 319 /**
 320  * Encrypt the next block of the file (and call proc and progress
 321  * accordingly; or of course "cont" if we have already completed
 322  * encoding of the entire file).
 323  *
 324  * @param te tree encoder to use
 325  */
 326 void
 327 GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te)
 328 {
 329   struct ContentHashKey *mychk;
 330   const void *pt_block;
 331   uint16_t pt_size;
 332   char iob[DBLOCK_SIZE];
 333   char enc[DBLOCK_SIZE];
 334   struct GNUNET_CRYPTO_SymmetricSessionKey sk;
 335   struct GNUNET_CRYPTO_SymmetricInitializationVector iv;
 336   unsigned int off;
 337
 338   GNUNET_assert (GNUNET_NO == te->in_next);
 339   te->in_next = GNUNET_YES;
 340   if (te->chk_tree_depth == te->current_depth)
 341   {
 342     off = CHK_PER_INODE * (te->chk_tree_depth - 1);
 343     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
 344                 GNUNET_h2s (&te->chk_tree[off].query), off);
 345     te->uri = GNUNET_new (struct GNUNET_FS_Uri);
 346     te->uri->type = GNUNET_FS_URI_CHK;
 347     te->uri->data.chk.chk = te->chk_tree[off];
 348     te->uri->data.chk.file_length = GNUNET_htonll (te->size);
 349     te->in_next = GNUNET_NO;
 350     te->cont (te->cls);
 351     return;
 352   }
 353   if (0 == te->current_depth)
 354   {
 355     /* read DBLOCK */
 356     pt_size = GNUNET_MIN (DBLOCK_SIZE, te->size - te->publish_offset);
 357     if (pt_size !=
 358         te->reader (te->cls, te->publish_offset, pt_size, iob, &te->emsg))
 359     {
 360       te->in_next = GNUNET_NO;
 361       te->cont (te->cls);
 362       return;
 363     }
 364     pt_block = iob;
 365   }
 366   else
 367   {
 368     pt_size =
 369         GNUNET_FS_tree_compute_iblock_size (te->current_depth,
 370                                             te->publish_offset);
 371     pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
 372   }
 373   off = compute_chk_offset (te->current_depth, te->publish_offset);
 374   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 375               "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
 376               (unsigned long long) te->publish_offset, te->current_depth,
 377               (unsigned int) pt_size, (unsigned int) off);
 378   mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off];
 379   GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
 380   GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
 381   GNUNET_CRYPTO_symmetric_encrypt (pt_block, pt_size, &sk, &iv, enc);
 382   GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
 383   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 384               "TE calculates query to be `%s', stored at %u\n",
 385               GNUNET_h2s (&mychk->query),
 386               te->current_depth * CHK_PER_INODE + off);
 387   if (NULL != te->proc)
 388     te->proc (te->cls, mychk, te->publish_offset, te->current_depth,
 389               (0 ==
 390                te->current_depth) ? GNUNET_BLOCK_TYPE_FS_DBLOCK :
 391               GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size);
 392   if (NULL != te->progress)
 393     te->progress (te->cls, te->publish_offset, pt_block, pt_size,
 394                   te->current_depth);
 395   if (0 == te->current_depth)
 396   {
 397     te->publish_offset += pt_size;
 398     if ((te->publish_offset == te->size) ||
 399         (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
 400       te->current_depth++;
 401   }
 402   else
 403   {
 404     if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
 405       te->current_depth++;
 406     else
 407       te->current_depth = 0;
 408   }
 409   te->in_next = GNUNET_NO;
 410 }
 411
 412
 413 /**
 414  * Get the resulting URI from the encoding.
 415  *
 416  * @param te the tree encoder to clean up
 417  * @return uri set to the resulting URI (if encoding finished), NULL otherwise
 418  */
 419 struct GNUNET_FS_Uri *
 420 GNUNET_FS_tree_encoder_get_uri (struct GNUNET_FS_TreeEncoder *te)
 421 {
 422   if (NULL != te->uri)
 423     return GNUNET_FS_uri_dup (te->uri);
 424   return NULL;
 425 }
 426
 427
 428 /**
 429  * Clean up a tree encoder and return information
 430  * about possible errors.
 431  *
 432  * @param te the tree encoder to clean up
 433  * @param emsg set to an error message (if an error occured
 434  *        within the tree encoder; if this function is called
 435  *        prior to completion and prior to an internal error,
 436  *        both "*emsg" will be set to NULL).
 437  */
 438 void
 439 GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te,
 440                                char **emsg)
 441 {
 442   if (NULL != te->reader)
 443   {
 444     (void) te->reader (te->cls, UINT64_MAX, 0, 0, NULL);
 445     te->reader =  NULL;
 446   }
 447   GNUNET_assert (GNUNET_NO == te->in_next);
 448   if (NULL != te->uri)
 449     GNUNET_FS_uri_destroy (te->uri);
 450   if (emsg != NULL)
 451     *emsg = te->emsg;
 452   else
 453     GNUNET_free_non_null (te->emsg);
 454   GNUNET_free (te->chk_tree);
 455   GNUNET_free (te);
 456 }
 457
 458 /* end of fs_tree.c */