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