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 static uint16_t
 202 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 the offset of the CHK for the
 235  * current block in the IBlock above.
 236  *
 237  * @param height height of the IBlock in the tree (aka overall
 238  *               number of tree levels minus depth); 0 == DBlock
 239  * @param offset current offset in the overall file
 240  * @return (array of CHKs') offset in the above IBlock
 241  */
 242 static unsigned int
 243 compute_chk_offset (unsigned int height,
 244                     uint64_t offset)
 245 {
 246   uint64_t bds;
 247   unsigned int ret;
 248   unsigned int i;
 249
 250   bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
 251                                   corresponds to */
 252   for (i=0;i<height;i++)
 253     bds *= CHK_PER_INODE;
 254   ret = offset / bds;
 255   return ret % CHK_PER_INODE;
 256 }
 257
 258
 259 /**
 260  * Encrypt the next block of the file (and
 261  * call proc and progress accordingly; or
 262  * of course "cont" if we have already completed
 263  * encoding of the entire file).
 264  *
 265  * @param te tree encoder to use
 266  */
 267 void GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
 268 {
 269   struct ContentHashKey *mychk;
 270   const void *pt_block;
 271   uint16_t pt_size;
 272   char iob[DBLOCK_SIZE];
 273   char enc[DBLOCK_SIZE];
 274   struct GNUNET_CRYPTO_AesSessionKey sk;
 275   struct GNUNET_CRYPTO_AesInitializationVector iv;
 276   unsigned int off;
 277
 278   if (te->current_depth == te->chk_tree_depth)
 279     {
 280       pt_size = GNUNET_MIN(DBLOCK_SIZE,
 281                            te->size - te->publish_offset);
 282       if (pt_size !=
 283           te->reader (te->cls,
 284                       te->publish_offset,
 285                       pt_size,
 286                       iob,
 287                       &te->emsg))
 288         {
 289           GNUNET_SCHEDULER_add_continuation (te->h->sched,
 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   if (0 == te->current_depth)
 305     {
 306       te->uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri));
 307       te->uri->type = chk;
 308       te->uri->data.chk.chk = te->chk_tree[0];
 309       te->uri->data.chk.file_length = GNUNET_htonll (te->size);
 310       GNUNET_SCHEDULER_add_continuation (te->h->sched,
 311                                          te->cont,
 312                                          te->cls,
 313                                          GNUNET_SCHEDULER_REASON_PREREQ_DONE);
 314       return;
 315     }
 316   off = compute_chk_offset (te->chk_tree_depth - te->current_depth,
 317                             te->publish_offset);
 318 #if DEBUG_TREE
 319   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 320               "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
 321               (unsigned long long) te->publish_offset,
 322               te->current_depth,
 323               (unsigned int) pt_size,
 324               (unsigned int) off);
 325 #endif
 326   mychk = &te->chk_tree[(te->current_depth-1)*CHK_PER_INODE+off];
 327   GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
 328   GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
 329   GNUNET_CRYPTO_aes_encrypt (pt_block,
 330                              pt_size,
 331                              &sk,
 332                              &iv,
 333                              enc);
 334   GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
 335 #if DEBUG_TREE
 336   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 337               "TE calculates query to be `%s'\n",
 338               GNUNET_h2s (&mychk->query));
 339 #endif
 340   if (NULL != te->proc)
 341     te->proc (te->cls,
 342               &mychk->query,
 343               te->publish_offset,
 344               (te->current_depth == te->chk_tree_depth)
 345               ? GNUNET_DATASTORE_BLOCKTYPE_DBLOCK
 346               : GNUNET_DATASTORE_BLOCKTYPE_IBLOCK,
 347               enc,
 348               pt_size);
 349   if (NULL != te->progress)
 350     te->progress (te->cls,
 351                   te->publish_offset,
 352                   pt_block,
 353                   pt_size,
 354                   te->current_depth);
 355   if (te->current_depth == te->chk_tree_depth)
 356     {
 357       te->publish_offset += pt_size;
 358       if ( (te->publish_offset == te->size) ||
 359            (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE) ) )
 360         te->current_depth--;
 361     }
 362   else
 363     {
 364       if ( (off == CHK_PER_INODE) ||
 365            (te->publish_offset == te->size) )
 366         te->current_depth--;
 367       else
 368         te->current_depth = te->chk_tree_depth;
 369     }
 370 }
 371
 372
 373 /**
 374  * Clean up a tree encoder and return information
 375  * about the resulting URI or an error message.
 376  *
 377  * @param te the tree encoder to clean up
 378  * @param uri set to the resulting URI (if encoding finished)
 379  * @param emsg set to an error message (if an error occured
 380  *        within the tree encoder; if this function is called
 381  *        prior to completion and prior to an internal error,
 382  *        both "*uri" and "*emsg" will be set to NULL).
 383  */
 384 void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te,
 385                                     struct GNUNET_FS_Uri **uri,
 386                                     char **emsg)
 387 {
 388   if (uri != NULL)
 389     *uri = te->uri;
 390   else
 391     if (NULL != te->uri)
 392       GNUNET_FS_uri_destroy (te->uri);
 393   if (emsg != NULL)
 394     *emsg = te->emsg;
 395   else
 396     GNUNET_free_non_null (te->emsg);
 397   GNUNET_free (te->chk_tree);
 398   GNUNET_free (te);
 399 }
 400
 401 /* end of fs_tree.c */