src/fs/fs_tree.c

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