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 2, 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  * TODO:
  28  * - decide if this API should be made public (gnunet_fs_service.h)
  29  *   or remain "internal" (but with exported symbols?)
  30  */
  31 #include "platform.h"
  32 #include "fs_tree.h"
  33
  34 #define DEBUG_TREE GNUNET_NO
  35
  36 /**
  37  * Context for an ECRS-based file encoder that computes
  38  * the Merkle-ish-CHK tree.
  39  */
  40 struct GNUNET_FS_TreeEncoder
  41 {
  42
  43   /**
  44    * Global FS context.
  45    */
  46   struct GNUNET_FS_Handle *h;
  47
  48   /**
  49    * Closure for all callbacks.
  50    */
  51   void *cls;
  52
  53   /**
  54    * Function to call on encrypted blocks.
  55    */
  56   GNUNET_FS_TreeBlockProcessor proc;
  57
  58   /**
  59    * Function to call with progress information.
  60    */
  61   GNUNET_FS_TreeProgressCallback progress;
  62
  63   /**
  64    * Function to call to receive input data.
  65    */
  66   GNUNET_FS_DataReader reader;
  67
  68   /**
  69    * Function to call once we're done with processing.
  70    */
  71   GNUNET_SCHEDULER_Task cont;
  72
  73   /**
  74    * Set to an error message (if we had an error).
  75    */
  76   char *emsg;
  77
  78   /**
  79    * Set to the URI (upon successful completion)
  80    */
  81   struct GNUNET_FS_Uri *uri;
  82
  83   /**
  84    * Overall file size.
  85    */
  86   uint64_t size;
  87
  88   /**
  89    * How far are we?
  90    */
  91   uint64_t publish_offset;
  92
  93   /**
  94    * How deep are we?
  95    */
  96   unsigned int current_depth;
  97
  98   /**
  99    * How deep is the tree?
 100    */
 101   unsigned int chk_tree_depth;
 102
 103   /**
 104    * In-memory cache of the current CHK tree.
 105    * This struct will contain the CHK values
 106    * from the root to the currently processed
 107    * node in the tree as identified by
 108    * "current_depth" and "publish_offset".
 109    * The "chktree" will be initially NULL,
 110    * then allocated to a sufficient number of
 111    * entries for the size of the file and
 112    * finally freed once the upload is complete.
 113    */
 114   struct ContentHashKey *chk_tree;
 115
 116 };
 117
 118
 119 /**
 120  * Compute the depth of the CHK tree.
 121  *
 122  * @param flen file length for which to compute the depth
 123  * @return depth of the tree
 124  */
 125 unsigned int
 126 GNUNET_FS_compute_depth (uint64_t flen)
 127 {
 128   unsigned int treeDepth;
 129   uint64_t fl;
 130
 131   treeDepth = 1;
 132   fl = DBLOCK_SIZE;
 133   while (fl < flen)
 134     {
 135       treeDepth++;
 136       if (fl * CHK_PER_INODE < fl)
 137         {
 138           /* integer overflow, this is a HUGE file... */
 139           return treeDepth;
 140         }
 141       fl = fl * CHK_PER_INODE;
 142     }
 143   return treeDepth;
 144 }
 145
 146
 147 /**
 148  * Initialize a tree encoder.  This function will call "proc" and
 149  * "progress" on each block in the tree.  Once all blocks have been
 150  * processed, "cont" will be scheduled.  The "reader" will be called
 151  * to obtain the (plaintext) blocks for the file.  Note that this
 152  * function will not actually call "proc".  The client must
 153  * call "GNUNET_FS_tree_encoder_next" to trigger encryption (and
 154  * calling of "proc") for the each block.
 155  *
 156  * @param h the global FS context
 157  * @param size overall size of the file to encode
 158  * @param cls closure for reader, proc, progress and cont
 159  * @param reader function to call to read plaintext data
 160  * @param proc function to call on each encrypted block
 161  * @param progress function to call with progress information
 162  * @param cont function to call when done
 163  */
 164 struct GNUNET_FS_TreeEncoder *
 165 GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h,
 166                                uint64_t size,
 167                                void *cls,
 168                                GNUNET_FS_DataReader reader,
 169                                GNUNET_FS_TreeBlockProcessor proc,
 170                                GNUNET_FS_TreeProgressCallback progress,
 171                                GNUNET_SCHEDULER_Task cont)
 172 {
 173   struct GNUNET_FS_TreeEncoder *te;
 174
 175   GNUNET_assert (size > 0);
 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 GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
 315 {
 316   struct ContentHashKey *mychk;
 317   const void *pt_block;
 318   uint16_t pt_size;
 319   char iob[DBLOCK_SIZE];
 320   char enc[DBLOCK_SIZE];
 321   struct GNUNET_CRYPTO_AesSessionKey sk;
 322   struct GNUNET_CRYPTO_AesInitializationVector iv;
 323   unsigned int off;
 324
 325   if (te->current_depth == te->chk_tree_depth)
 326     {
 327       pt_size = GNUNET_MIN(DBLOCK_SIZE,
 328                            te->size - te->publish_offset);
 329       if (pt_size !=
 330           te->reader (te->cls,
 331                       te->publish_offset,
 332                       pt_size,
 333                       iob,
 334                       &te->emsg))
 335         {
 336           GNUNET_SCHEDULER_add_continuation (te->h->sched,
 337                                              te->cont,
 338                                              te->cls,
 339                                              GNUNET_SCHEDULER_REASON_TIMEOUT);
 340           return;
 341         }
 342       pt_block = iob;
 343     }
 344   else
 345     {
 346       pt_size = GNUNET_FS_tree_compute_iblock_size (te->chk_tree_depth - te->current_depth,
 347                                                     te->publish_offset);
 348       pt_block = &te->chk_tree[te->current_depth *
 349                                CHK_PER_INODE];
 350     }
 351   if (0 == te->current_depth)
 352     {
 353       te->uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri));
 354       te->uri->type = chk;
 355       te->uri->data.chk.chk = te->chk_tree[0];
 356       te->uri->data.chk.file_length = GNUNET_htonll (te->size);
 357       GNUNET_SCHEDULER_add_continuation (te->h->sched,
 358                                          te->cont,
 359                                          te->cls,
 360                                          GNUNET_SCHEDULER_REASON_PREREQ_DONE);
 361       return;
 362     }
 363   off = compute_chk_offset (te->chk_tree_depth - te->current_depth,
 364                             te->publish_offset);
 365 #if DEBUG_TREE
 366   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 367               "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
 368               (unsigned long long) te->publish_offset,
 369               te->current_depth,
 370               (unsigned int) pt_size,
 371               (unsigned int) off);
 372 #endif
 373   mychk = &te->chk_tree[(te->current_depth-1)*CHK_PER_INODE+off];
 374   GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
 375   GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
 376   GNUNET_CRYPTO_aes_encrypt (pt_block,
 377                              pt_size,
 378                              &sk,
 379                              &iv,
 380                              enc);
 381   GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
 382 #if DEBUG_TREE
 383   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 384               "TE calculates query to be `%s'\n",
 385               GNUNET_h2s (&mychk->query));
 386 #endif
 387   if (NULL != te->proc)
 388     te->proc (te->cls,
 389               &mychk->query,
 390               te->publish_offset,
 391               (te->current_depth == te->chk_tree_depth)
 392               ? GNUNET_BLOCK_TYPE_DBLOCK
 393               : GNUNET_BLOCK_TYPE_IBLOCK,
 394               enc,
 395               pt_size);
 396   if (NULL != te->progress)
 397     te->progress (te->cls,
 398                   te->publish_offset,
 399                   pt_block,
 400                   pt_size,
 401                   te->current_depth);
 402   if (te->current_depth == te->chk_tree_depth)
 403     {
 404       te->publish_offset += pt_size;
 405       if ( (te->publish_offset == te->size) ||
 406            (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE) ) )
 407         te->current_depth--;
 408     }
 409   else
 410     {
 411       if ( (off == CHK_PER_INODE) ||
 412            (te->publish_offset == te->size) )
 413         te->current_depth--;
 414       else
 415         te->current_depth = te->chk_tree_depth;
 416     }
 417 }
 418
 419
 420 /**
 421  * Clean up a tree encoder and return information
 422  * about the resulting URI or an error message.
 423  *
 424  * @param te the tree encoder to clean up
 425  * @param uri set to the resulting URI (if encoding finished)
 426  * @param emsg set to an error message (if an error occured
 427  *        within the tree encoder; if this function is called
 428  *        prior to completion and prior to an internal error,
 429  *        both "*uri" and "*emsg" will be set to NULL).
 430  */
 431 void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te,
 432                                     struct GNUNET_FS_Uri **uri,
 433                                     char **emsg)
 434 {
 435   if (uri != NULL)
 436     *uri = te->uri;
 437   else
 438     if (NULL != te->uri)
 439       GNUNET_FS_uri_destroy (te->uri);
 440   if (emsg != NULL)
 441     *emsg = te->emsg;
 442   else
 443     GNUNET_free_non_null (te->emsg);
 444   GNUNET_free (te->chk_tree);
 445   GNUNET_free (te);
 446 }
 447
 448 /* end of fs_tree.c */