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