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
  35 /**
  36  * Context for an ECRS-based file encoder that computes
  37  * the Merkle-ish-CHK tree.
  38  */
  39 struct GNUNET_FS_TreeEncoder
  40 {
  41
  42   /**
  43    * Global FS context.
  44    */
  45   struct GNUNET_FS_Handle *h;
  46
  47   /**
  48    * Closure for all callbacks.
  49    */
  50   void *cls;
  51
  52   /**
  53    * Function to call on encrypted blocks.
  54    */
  55   GNUNET_FS_TreeBlockProcessor proc;
  56
  57   /**
  58    * Function to call with progress information.
  59    */
  60   GNUNET_FS_TreeProgressCallback progress;
  61
  62   /**
  63    * Function to call to receive input data.
  64    */
  65   GNUNET_FS_DataReader reader;
  66
  67   /**
  68    * Function to call once we're done with processing.
  69    */
  70   GNUNET_SCHEDULER_Task cont;
  71
  72   /**
  73    * Set to an error message (if we had an error).
  74    */
  75   char *emsg;
  76
  77   /**
  78    * Set to the URI (upon successful completion)
  79    */
  80   struct GNUNET_FS_Uri *uri;
  81
  82   /**
  83    * Overall file size.
  84    */
  85   uint64_t size;
  86
  87   /**
  88    * How far are we?
  89    */
  90   uint64_t publish_offset;
  91
  92   /**
  93    * How deep are we?
  94    */
  95   unsigned int current_depth;
  96
  97   /**
  98    * How deep is the tree?
  99    */
 100   unsigned int chk_tree_depth;
 101
 102   /**
 103    * In-memory cache of the current CHK tree.
 104    * This struct will contain the CHK values
 105    * from the root to the currently processed
 106    * node in the tree as identified by
 107    * "current_depth" and "publish_offset".
 108    * The "chktree" will be initially NULL,
 109    * then allocated to a sufficient number of
 110    * entries for the size of the file and
 111    * finally freed once the upload is complete.
 112    */
 113   struct ContentHashKey *chk_tree;
 114
 115 };
 116
 117
 118 /**
 119  * Compute the depth of the CHK tree.
 120  *
 121  * @param flen file length for which to compute the depth
 122  * @return depth of the tree
 123  */
 124 unsigned int
 125 GNUNET_FS_compute_depth (uint64_t flen)
 126 {
 127   unsigned int treeDepth;
 128   uint64_t fl;
 129
 130   treeDepth = 1;
 131   fl = DBLOCK_SIZE;
 132   while (fl < flen)
 133     {
 134       treeDepth++;
 135       if (fl * CHK_PER_INODE < fl)
 136         {
 137           /* integer overflow, this is a HUGE file... */
 138           return treeDepth;
 139         }
 140       fl = fl * CHK_PER_INODE;
 141     }
 142   return treeDepth;
 143 }
 144
 145
 146 /**
 147  * Initialize a tree encoder.  This function will call "proc" and
 148  * "progress" on each block in the tree.  Once all blocks have been
 149  * processed, "cont" will be scheduled.  The "reader" will be called
 150  * to obtain the (plaintext) blocks for the file.  Note that this
 151  * function will not actually call "proc".  The client must
 152  * call "GNUNET_FS_tree_encoder_next" to trigger encryption (and
 153  * calling of "proc") for the each block.
 154  *
 155  * @param h the global FS context
 156  * @param size overall size of the file to encode
 157  * @param cls closure for reader, proc, progress and cont
 158  * @param reader function to call to read plaintext data
 159  * @param proc function to call on each encrypted block
 160  * @param progress function to call with progress information
 161  * @param cont function to call when done
 162  */
 163 struct GNUNET_FS_TreeEncoder *
 164 GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h,
 165                                uint64_t size,
 166                                void *cls,
 167                                GNUNET_FS_DataReader reader,
 168                                GNUNET_FS_TreeBlockProcessor proc,
 169                                GNUNET_FS_TreeProgressCallback progress,
 170                                GNUNET_SCHEDULER_Task cont)
 171 {
 172   struct GNUNET_FS_TreeEncoder *te;
 173
 174   te = GNUNET_malloc (sizeof (struct GNUNET_FS_TreeEncoder));
 175   te->h = h;
 176   te->size = size;
 177   te->cls = cls;
 178   te->reader = reader;
 179   te->proc = proc;
 180   te->progress = progress;
 181   te->cont = cont;
 182   te->chk_tree_depth = GNUNET_FS_compute_depth (size);
 183   te->current_depth = te->chk_tree_depth;
 184   te->chk_tree = GNUNET_malloc (te->chk_tree_depth *
 185                                 CHK_PER_INODE *
 186                                 sizeof (struct ContentHashKey));
 187   return te;
 188 }
 189
 190
 191 /**
 192  * Compute the size of the current IBlock.
 193  *
 194  * @param height height of the IBlock in the tree (aka overall
 195  *               number of tree levels minus depth); 0 == DBlock
 196  * @param offset current offset in the overall file
 197  * @return size of the corresponding IBlock
 198  */
 199 static uint16_t
 200 compute_iblock_size (unsigned int height,
 201                      uint64_t offset)
 202 {
 203   unsigned int ret;
 204   unsigned int i;
 205   uint64_t mod;
 206   uint64_t bds;
 207
 208   GNUNET_assert (height > 0);
 209   bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
 210                                   corresponds to */
 211   for (i=0;i<height;i++)
 212     bds *= CHK_PER_INODE;
 213   mod = offset % bds;
 214   if (0 == mod)
 215     {
 216       /* we were triggered at the end of a full block */
 217       ret = CHK_PER_INODE;
 218     }
 219   else
 220     {
 221       /* we were triggered at the end of the file */
 222       bds /= CHK_PER_INODE;
 223       ret = mod / bds;
 224       if (0 != mod % bds)
 225         ret++;
 226     }
 227   return (uint16_t) (ret * sizeof(struct ContentHashKey));
 228 }
 229
 230
 231 /**
 232  * Compute the offset of the CHK for the
 233  * current block in the IBlock above.
 234  *
 235  * @param height height of the IBlock in the tree (aka overall
 236  *               number of tree levels minus depth); 0 == DBlock
 237  * @param offset current offset in the overall file
 238  * @return (array of CHKs') offset in the above IBlock
 239  */
 240 static unsigned int
 241 compute_chk_offset (unsigned int height,
 242                     uint64_t offset)
 243 {
 244   uint64_t bds;
 245   unsigned int ret;
 246   unsigned int i;
 247
 248   bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
 249                                   corresponds to */
 250   for (i=0;i<height;i++)
 251     bds *= CHK_PER_INODE;
 252   GNUNET_assert (0 == (offset % bds));
 253   ret = offset / bds;
 254   return ret % CHK_PER_INODE;
 255 }
 256
 257
 258 /**
 259  * Encrypt the next block of the file (and
 260  * call proc and progress accordingly; or
 261  * of course "cont" if we have already completed
 262  * encoding of the entire file).
 263  *
 264  * @param te tree encoder to use
 265  */
 266 void GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
 267 {
 268   struct ContentHashKey *mychk;
 269   const void *pt_block;
 270   uint16_t pt_size;
 271   char iob[DBLOCK_SIZE];
 272   char enc[DBLOCK_SIZE];
 273   struct GNUNET_CRYPTO_AesSessionKey sk;
 274   struct GNUNET_CRYPTO_AesInitializationVector iv;
 275   unsigned int off;
 276
 277   if (te->current_depth == te->chk_tree_depth)
 278     {
 279       pt_size = GNUNET_MIN(DBLOCK_SIZE,
 280                            te->size - te->publish_offset);
 281       if (pt_size !=
 282           te->reader (te->cls,
 283                       te->publish_offset,
 284                       pt_size,
 285                       iob,
 286                       &te->emsg))
 287         {
 288           GNUNET_SCHEDULER_add_continuation (te->h->sched,
 289                                              GNUNET_NO,
 290                                              te->cont,
 291                                              te->cls,
 292                                              GNUNET_SCHEDULER_REASON_TIMEOUT);
 293           return;
 294         }
 295       pt_block = iob;
 296     }
 297   else
 298     {
 299       pt_size = compute_iblock_size (te->chk_tree_depth - te->current_depth,
 300                                      te->publish_offset);
 301       pt_block = &te->chk_tree[te->current_depth *
 302                                CHK_PER_INODE];
 303     }
 304   off = compute_chk_offset (te->chk_tree_depth - te->current_depth,
 305                             te->publish_offset);
 306   mychk = &te->chk_tree[(te->current_depth-1)*CHK_PER_INODE+off];
 307   GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
 308   GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
 309   GNUNET_CRYPTO_aes_encrypt (pt_block,
 310                              pt_size,
 311                              &sk,
 312                              &iv,
 313                              enc);
 314   if (NULL != te->proc)
 315     te->proc (te->cls,
 316               &mychk->query,
 317               te->publish_offset,
 318               pt_size,
 319               enc,
 320               (te->current_depth == te->chk_tree_depth)
 321               ? GNUNET_DATASTORE_BLOCKTYPE_DBLOCK
 322               : GNUNET_DATASTORE_BLOCKTYPE_IBLOCK);
 323   if (NULL != te->progress)
 324     te->progress (te->cls,
 325                   te->publish_offset,
 326                   pt_block,
 327                   pt_size,
 328                   te->current_depth);
 329   GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
 330   if (te->current_depth == te->chk_tree_depth)
 331     {
 332       te->publish_offset += pt_size;
 333       if ( (te->publish_offset == te->size) ||
 334            (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE) ) )
 335         te->current_depth--;
 336     }
 337   else
 338     {
 339       if ( (off == CHK_PER_INODE) ||
 340            (te->publish_offset == te->size) )
 341         te->current_depth--;
 342       else
 343         te->current_depth = te->chk_tree_depth;
 344     }
 345   if (0 == te->current_depth)
 346     {
 347       te->uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri));
 348       te->uri->type = chk;
 349       te->uri->data.chk.chk = te->chk_tree[0];
 350       te->uri->data.chk.file_length = GNUNET_htonll (te->size);
 351       GNUNET_SCHEDULER_add_continuation (te->h->sched,
 352                                          GNUNET_NO,
 353                                          te->cont,
 354                                          te->cls,
 355                                          GNUNET_SCHEDULER_REASON_PREREQ_DONE);
 356     }
 357 }
 358
 359
 360 /**
 361  * Clean up a tree encoder and return information
 362  * about the resulting URI or an error message.
 363  *
 364  * @param te the tree encoder to clean up
 365  * @param uri set to the resulting URI (if encoding finished)
 366  * @param emsg set to an error message (if an error occured
 367  *        within the tree encoder; if this function is called
 368  *        prior to completion and prior to an internal error,
 369  *        both "*uri" and "*emsg" will be set to NULL).
 370  */
 371 void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te,
 372                                     struct GNUNET_FS_Uri **uri,
 373                                     char **emsg)
 374 {
 375   *uri = te->uri;
 376   *emsg = te->emsg;
 377   GNUNET_free (te->chk_tree);
 378   GNUNET_free (te);
 379 }
 380
 381 /* end of fs_tree.c */