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