src/fs/fs_tree.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2009 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_NO
  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?
  91    */
  92   unsigned int current_depth;
  93
  94   /**
  95    * How deep is the tree?
  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
 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  * Initialize a tree encoder.  This function will call "proc" and
 150  * "progress" on each block in the tree.  Once all blocks have been
 151  * processed, "cont" will be scheduled.  The "reader" will be called
 152  * to obtain the (plaintext) blocks for the file.  Note that this
 153  * function will not actually call "proc".  The client must
 154  * call "GNUNET_FS_tree_encoder_next" to trigger encryption (and
 155  * calling of "proc") for the each block.
 156  *
 157  * @param h the global FS context
 158  * @param size overall size of the file to encode
 159  * @param cls closure for reader, proc, progress and cont
 160  * @param reader function to call to read plaintext data
 161  * @param proc function to call on each encrypted block
 162  * @param progress function to call with progress information
 163  * @param cont function to call when done
 164  */
 165 struct GNUNET_FS_TreeEncoder *
 166 GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h,
 167                                uint64_t size,
 168                                void *cls,
 169                                GNUNET_FS_DataReader reader,
 170                                GNUNET_FS_TreeBlockProcessor proc,
 171                                GNUNET_FS_TreeProgressCallback progress,
 172                                GNUNET_SCHEDULER_Task cont)
 173 {
 174   struct GNUNET_FS_TreeEncoder *te;
 175
 176   GNUNET_assert (size > 0);
 177   te = GNUNET_malloc (sizeof (struct GNUNET_FS_TreeEncoder));
 178   te->h = h;
 179   te->size = size;
 180   te->cls = cls;
 181   te->reader = reader;
 182   te->proc = proc;
 183   te->progress = progress;
 184   te->cont = cont;
 185   te->chk_tree_depth = GNUNET_FS_compute_depth (size);
 186   te->current_depth = te->chk_tree_depth;
 187   te->chk_tree = GNUNET_malloc (te->chk_tree_depth *
 188                                 CHK_PER_INODE *
 189                                 sizeof (struct ContentHashKey));
 190   return te;
 191 }
 192
 193
 194 /**
 195  * Compute the size of the current IBlock.
 196  *
 197  * @param height height of the IBlock in the tree (aka overall
 198  *               number of tree levels minus depth); 0 == DBlock
 199  * @param offset current offset in the overall file
 200  * @return size of the corresponding IBlock
 201  */
 202 uint16_t
 203 GNUNET_FS_tree_compute_iblock_size (unsigned int height,
 204                                     uint64_t offset)
 205 {
 206   unsigned int ret;
 207   unsigned int i;
 208   uint64_t mod;
 209   uint64_t bds;
 210
 211   GNUNET_assert (height > 0);
 212   bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
 213                                   corresponds to */
 214   for (i=0;i<height;i++)
 215     bds *= CHK_PER_INODE;
 216   mod = offset % bds;
 217   if (0 == mod)
 218     {
 219       /* we were triggered at the end of a full block */
 220       ret = CHK_PER_INODE;
 221     }
 222   else
 223     {
 224       /* we were triggered at the end of the file */
 225       bds /= CHK_PER_INODE;
 226       ret = mod / bds;
 227       if (0 != mod % bds)
 228         ret++;
 229     }
 230   return (uint16_t) (ret * sizeof(struct ContentHashKey));
 231 }
 232
 233
 234 /**
 235  * Compute how many bytes of data should be stored in
 236  * the specified node.
 237  *
 238  * @param fsize overall file size
 239  * @param totaldepth depth of the entire tree
 240  * @param offset offset of the node
 241  * @param depth depth of the node
 242  * @return number of bytes stored in this node
 243  */
 244 size_t
 245 GNUNET_FS_tree_calculate_block_size (uint64_t fsize,
 246                                      unsigned int totaldepth,
 247                                      uint64_t offset,
 248                                      unsigned int depth)
 249 {
 250   unsigned int i;
 251   size_t ret;
 252   uint64_t rsize;
 253   uint64_t epos;
 254   unsigned int chks;
 255
 256   GNUNET_assert (offset < fsize);
 257   if (depth == totaldepth)
 258     {
 259       ret = DBLOCK_SIZE;
 260       if (offset + ret > fsize)
 261         ret = (size_t) (fsize - offset);
 262       return ret;
 263     }
 264   /* FIXME: this code should be *equivalent* to the
 265      GNUNET_FS_tree_compute_iblock_size function above! Remove duplication! */
 266   rsize = DBLOCK_SIZE;
 267   for (i = totaldepth-1; i > depth; i--)
 268     rsize *= CHK_PER_INODE;
 269   epos = offset + rsize * CHK_PER_INODE;
 270   GNUNET_assert (epos > offset);
 271   if (epos > fsize)
 272     epos = fsize;
 273   /* round up when computing #CHKs in our IBlock */
 274   chks = (epos - offset + rsize - 1) / rsize;
 275   GNUNET_assert (chks <= CHK_PER_INODE);
 276   return chks * sizeof (struct ContentHashKey);
 277 }
 278
 279
 280 /**
 281  * Compute the offset of the CHK for the
 282  * current block in the IBlock above.
 283  *
 284  * @param height height of the IBlock in the tree (aka overall
 285  *               number of tree levels minus depth); 0 == DBlock
 286  * @param offset current offset in the overall file
 287  * @return (array of CHKs') offset in the above IBlock
 288  */
 289 static unsigned int
 290 compute_chk_offset (unsigned int height,
 291                     uint64_t offset)
 292 {
 293   uint64_t bds;
 294   unsigned int ret;
 295   unsigned int i;
 296
 297   bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
 298                                   corresponds to */
 299   for (i=0;i<height;i++)
 300     bds *= CHK_PER_INODE;
 301   if (height > 0)
 302     offset--; /* round down since for height > 0 offset is at the END of the block */
 303   ret = offset / bds;
 304   return ret % CHK_PER_INODE;
 305 }
 306
 307
 308 /**
 309  * Encrypt the next block of the file (and call proc and progress
 310  * accordingly; or of course "cont" if we have already completed
 311  * encoding of the entire file).
 312  *
 313  * @param te tree encoder to use
 314  */
 315 void
 316 GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
 317 {
 318   struct ContentHashKey *mychk;
 319   const void *pt_block;
 320   uint16_t pt_size;
 321   char iob[DBLOCK_SIZE];
 322   char enc[DBLOCK_SIZE];
 323   struct GNUNET_CRYPTO_AesSessionKey sk;
 324   struct GNUNET_CRYPTO_AesInitializationVector iv;
 325   unsigned int off;
 326
 327   GNUNET_assert (GNUNET_NO == te->in_next);
 328   te->in_next = GNUNET_YES;
 329   if (te->current_depth == te->chk_tree_depth)
 330     {
 331       pt_size = GNUNET_MIN(DBLOCK_SIZE,
 332                            te->size - te->publish_offset);
 333       if (pt_size !=
 334           te->reader (te->cls,
 335                       te->publish_offset,
 336                       pt_size,
 337                       iob,
 338                       &te->emsg))
 339         {
 340           GNUNET_SCHEDULER_add_continuation (te->cont,
 341                                              te->cls,
 342                                              GNUNET_SCHEDULER_REASON_TIMEOUT);
 343           te->in_next = GNUNET_NO;
 344           return;
 345         }
 346       pt_block = iob;
 347     }
 348   else
 349     {
 350       pt_size = GNUNET_FS_tree_compute_iblock_size (te->chk_tree_depth - te->current_depth,
 351                                                     te->publish_offset);
 352       pt_block = &te->chk_tree[te->current_depth *
 353                                CHK_PER_INODE];
 354     }
 355   if (0 == te->current_depth)
 356     {
 357       te->uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri));
 358       te->uri->type = chk;
 359       te->uri->data.chk.chk = te->chk_tree[0];
 360       te->uri->data.chk.file_length = GNUNET_htonll (te->size);
 361       GNUNET_SCHEDULER_add_continuation (te->cont,
 362                                          te->cls,
 363                                          GNUNET_SCHEDULER_REASON_PREREQ_DONE);
 364       te->in_next = GNUNET_NO;
 365       return;
 366     }
 367   off = compute_chk_offset (te->chk_tree_depth - te->current_depth,
 368                             te->publish_offset);
 369 #if DEBUG_TREE
 370   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 371               "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
 372               (unsigned long long) te->publish_offset,
 373               te->current_depth,
 374               (unsigned int) pt_size,
 375               (unsigned int) off);
 376 #endif
 377   mychk = &te->chk_tree[(te->current_depth-1)*CHK_PER_INODE+off];
 378   GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
 379   GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
 380   GNUNET_CRYPTO_aes_encrypt (pt_block,
 381                              pt_size,
 382                              &sk,
 383                              &iv,
 384                              enc);
 385   GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
 386 #if DEBUG_TREE
 387   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 388               "TE calculates query to be `%s'\n",
 389               GNUNET_h2s (&mychk->query));
 390 #endif
 391   if (NULL != te->proc)
 392     te->proc (te->cls,
 393               &mychk->query,
 394               te->publish_offset,
 395               te->current_depth,
 396               (te->current_depth == te->chk_tree_depth)
 397               ? GNUNET_BLOCK_TYPE_FS_DBLOCK
 398               : GNUNET_BLOCK_TYPE_FS_IBLOCK,
 399               enc,
 400               pt_size);
 401   if (NULL != te->progress)
 402     te->progress (te->cls,
 403                   te->publish_offset,
 404                   pt_block,
 405                   pt_size,
 406                   te->current_depth);
 407   if (te->current_depth == te->chk_tree_depth)
 408     {
 409       te->publish_offset += pt_size;
 410       if ( (te->publish_offset == te->size) ||
 411            (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE) ) )
 412         te->current_depth--;
 413     }
 414   else
 415     {
 416       if ( (off == CHK_PER_INODE) ||
 417            (te->publish_offset == te->size) )
 418         te->current_depth--;
 419       else
 420         te->current_depth = te->chk_tree_depth;
 421     }
 422   te->in_next = GNUNET_NO;
 423 }
 424
 425
 426 /**
 427  * Clean up a tree encoder and return information
 428  * about the resulting URI or an error message.
 429  *
 430  * @param te the tree encoder to clean up
 431  * @param uri set to the resulting URI (if encoding finished)
 432  * @param emsg set to an error message (if an error occured
 433  *        within the tree encoder; if this function is called
 434  *        prior to completion and prior to an internal error,
 435  *        both "*uri" and "*emsg" will be set to NULL).
 436  */
 437 void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te,
 438                                     struct GNUNET_FS_Uri **uri,
 439                                     char **emsg)
 440 {
 441   if (uri != NULL)
 442     *uri = te->uri;
 443   else
 444     if (NULL != te->uri)
 445       GNUNET_FS_uri_destroy (te->uri);
 446   if (emsg != NULL)
 447     *emsg = te->emsg;
 448   else
 449     GNUNET_free_non_null (te->emsg);
 450   GNUNET_free (te->chk_tree);
 451   GNUNET_free (te);
 452 }
 453
 454 /* end of fs_tree.c */