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