src/fs/fs_tree.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2009-2011 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your 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      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18      SPDX-License-Identifier: AGPL3.0-or-later
  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
  31 /**
  32  * Context for an ECRS-based file encoder that computes
  33  * the Merkle-ish-CHK tree.
  34  */
  35 struct GNUNET_FS_TreeEncoder {
  36   /**
  37    * Global FS context.
  38    */
  39   struct GNUNET_FS_Handle *h;
  40
  41   /**
  42    * Closure for all callbacks.
  43    */
  44   void *cls;
  45
  46   /**
  47    * Function to call on encrypted blocks.
  48    */
  49   GNUNET_FS_TreeBlockProcessor proc;
  50
  51   /**
  52    * Function to call with progress information.
  53    */
  54   GNUNET_FS_TreeProgressCallback progress;
  55
  56   /**
  57    * Function to call to receive input data.
  58    */
  59   GNUNET_FS_DataReader reader;
  60
  61   /**
  62    * Function to call once we're done with processing.
  63    */
  64   GNUNET_SCHEDULER_TaskCallback cont;
  65
  66   /**
  67    * Set to an error message (if we had an error).
  68    */
  69   char *emsg;
  70
  71   /**
  72    * Set to the URI (upon successful completion)
  73    */
  74   struct GNUNET_FS_Uri *uri;
  75
  76   /**
  77    * Overall file size.
  78    */
  79   uint64_t size;
  80
  81   /**
  82    * How far are we?
  83    */
  84   uint64_t publish_offset;
  85
  86   /**
  87    * How deep are we?  Depth 0 is for the DBLOCKs.
  88    */
  89   unsigned int current_depth;
  90
  91   /**
  92    * How deep is the tree? Always > 0.
  93    */
  94   unsigned int chk_tree_depth;
  95
  96   /**
  97    * In-memory cache of the current CHK tree.
  98    * This struct will contain the CHK values
  99    * from the root to the currently processed
 100    * node in the tree as identified by
 101    * "current_depth" and "publish_offset".
 102    * The "chktree" will be initially NULL,
 103    * then allocated to a sufficient number of
 104    * entries for the size of the file and
 105    * finally freed once the upload is complete.
 106    */
 107   struct ContentHashKey *chk_tree;
 108
 109   /**
 110    * Are we currently in 'GNUNET_FS_tree_encoder_next'?
 111    * Flag used to prevent recursion.
 112    */
 113   int in_next;
 114 };
 115
 116
 117 /**
 118  * Compute the depth of the CHK tree.
 119  *
 120  * @param flen file length for which to compute the depth
 121  * @return depth of the tree, always > 0.  A depth of 1 means only a DBLOCK.
 122  */
 123 unsigned int
 124 GNUNET_FS_compute_depth(uint64_t flen)
 125 {
 126   unsigned int treeDepth;
 127   uint64_t fl;
 128
 129   treeDepth = 1;
 130   fl = DBLOCK_SIZE;
 131   while (fl < flen)
 132     {
 133       treeDepth++;
 134       if (fl * CHK_PER_INODE < fl)
 135         {
 136           /* integer overflow, this is a HUGE file... */
 137           return treeDepth;
 138         }
 139       fl = fl * CHK_PER_INODE;
 140     }
 141   return treeDepth;
 142 }
 143
 144
 145 /**
 146  * Calculate how many bytes of payload a block tree of the given
 147  * depth MAY correspond to at most (this function ignores the fact that
 148  * some blocks will only be present partially due to the total file
 149  * size cutting some blocks off at the end).
 150  *
 151  * @param depth depth of the block.  depth==0 is a DBLOCK.
 152  * @return number of bytes of payload a subtree of this depth may correspond to
 153  */
 154 uint64_t
 155 GNUNET_FS_tree_compute_tree_size(unsigned int depth)
 156 {
 157   uint64_t rsize;
 158   unsigned int i;
 159
 160   rsize = DBLOCK_SIZE;
 161   for (i = 0; i < depth; i++)
 162     rsize *= CHK_PER_INODE;
 163   return rsize;
 164 }
 165
 166
 167 /**
 168  * Compute the size of the current IBLOCK.  The encoder is
 169  * triggering the calculation of the size of an IBLOCK at the
 170  * *end* (hence end_offset) of its construction.  The IBLOCK
 171  * maybe a full or a partial IBLOCK, and this function is to
 172  * calculate how long it should be.
 173  *
 174  * @param depth depth of the IBlock in the tree, 0 would be a DBLOCK,
 175  *        must be > 0 (this function is for IBLOCKs only!)
 176  * @param end_offset current offset in the payload (!) of the overall file,
 177  *        must be > 0 (since this function is called at the
 178  *        end of a block).
 179  * @return size of the corresponding IBlock
 180  */
 181 static uint16_t
 182 GNUNET_FS_tree_compute_iblock_size(unsigned int depth, uint64_t end_offset)
 183 {
 184   unsigned int ret;
 185   uint64_t mod;
 186   uint64_t bds;
 187
 188   GNUNET_assert(depth > 0);
 189   GNUNET_assert(end_offset > 0);
 190   bds = GNUNET_FS_tree_compute_tree_size(depth);
 191   mod = end_offset % bds;
 192   if (0 == mod)
 193     {
 194       /* we were triggered at the end of a full block */
 195       ret = CHK_PER_INODE;
 196     }
 197   else
 198     {
 199       /* we were triggered at the end of the file */
 200       bds /= CHK_PER_INODE;
 201       ret = mod / bds;
 202       if (0 != mod % bds)
 203         ret++;
 204     }
 205   return (uint16_t)(ret * sizeof(struct ContentHashKey));
 206 }
 207
 208
 209 /**
 210  * Compute how many bytes of data should be stored in
 211  * the specified block.
 212  *
 213  * @param fsize overall file size, must be > 0.
 214  * @param offset offset in the original data corresponding
 215  *         to the beginning of the tree induced by the block;
 216  *         must be <= fsize
 217  * @param depth depth of the node in the tree, 0 for DBLOCK
 218  * @return number of bytes stored in this node
 219  */
 220 size_t
 221 GNUNET_FS_tree_calculate_block_size(uint64_t fsize, uint64_t offset,
 222                                     unsigned int depth)
 223 {
 224   size_t ret;
 225   uint64_t rsize;
 226   uint64_t epos;
 227   unsigned int chks;
 228
 229   GNUNET_assert(fsize > 0);
 230   GNUNET_assert(offset <= fsize);
 231   if (depth == 0)
 232     {
 233       ret = DBLOCK_SIZE;
 234       if ((offset + ret > fsize) || (offset + ret < offset))
 235         ret = (size_t)(fsize - offset);
 236       return ret;
 237     }
 238
 239   rsize = GNUNET_FS_tree_compute_tree_size(depth - 1);
 240   epos = offset + rsize * CHK_PER_INODE;
 241   if ((epos < offset) || (epos > fsize))
 242     epos = fsize;
 243   /* round up when computing #CHKs in our IBlock */
 244   chks = (epos - offset + rsize - 1) / rsize;
 245   GNUNET_assert(chks <= CHK_PER_INODE);
 246   return chks * sizeof(struct ContentHashKey);
 247 }
 248
 249
 250 /**
 251  * Initialize a tree encoder.  This function will call @a proc and
 252  * "progress" on each block in the tree.  Once all blocks have been
 253  * processed, "cont" will be scheduled.  The @a reader will be called
 254  * to obtain the (plaintext) blocks for the file.  Note that this
 255  * function will not actually call @a proc.  The client must
 256  * call #GNUNET_FS_tree_encoder_next to trigger encryption (and
 257  * calling of @a proc) for the each block.
 258  *
 259  * @param h the global FS context
 260  * @param size overall size of the file to encode
 261  * @param cls closure for reader, proc, progress and cont
 262  * @param reader function to call to read plaintext data
 263  * @param proc function to call on each encrypted block
 264  * @param progress function to call with progress information
 265  * @param cont function to call when done
 266  */
 267 struct GNUNET_FS_TreeEncoder *
 268 GNUNET_FS_tree_encoder_create(struct GNUNET_FS_Handle *h, uint64_t size,
 269                               void *cls,
 270                               GNUNET_FS_DataReader reader,
 271                               GNUNET_FS_TreeBlockProcessor proc,
 272                               GNUNET_FS_TreeProgressCallback progress,
 273                               GNUNET_SCHEDULER_TaskCallback cont)
 274 {
 275   struct GNUNET_FS_TreeEncoder *te;
 276
 277   te = GNUNET_new(struct GNUNET_FS_TreeEncoder);
 278   te->h = h;
 279   te->size = size;
 280   te->cls = cls;
 281   te->reader = reader;
 282   te->proc = proc;
 283   te->progress = progress;
 284   te->cont = cont;
 285   te->chk_tree_depth = GNUNET_FS_compute_depth(size);
 286   te->chk_tree
 287     = GNUNET_new_array(te->chk_tree_depth * CHK_PER_INODE,
 288                        struct ContentHashKey);
 289   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 290              "Created tree encoder for file with %llu bytes and depth %u\n",
 291              (unsigned long long)size,
 292              te->chk_tree_depth);
 293   return te;
 294 }
 295
 296
 297 /**
 298  * Compute the offset of the CHK for the
 299  * current block in the IBlock above.
 300  *
 301  * @param depth depth of the IBlock in the tree (aka overall
 302  *               number of tree levels minus depth); 0 == DBlock
 303  * @param end_offset current offset in the overall file,
 304  *               at the *beginning* of the block for DBLOCKs (depth==0),
 305  *               otherwise at the *end* of the block (exclusive)
 306  * @return (array of CHKs') offset in the above IBlock
 307  */
 308 static unsigned int
 309 compute_chk_offset(unsigned int depth, uint64_t end_offset)
 310 {
 311   uint64_t bds;
 312   unsigned int ret;
 313
 314   bds = GNUNET_FS_tree_compute_tree_size(depth);
 315   if (depth > 0)
 316     end_offset--;               /* round down since for depth > 0 offset is at the END of the block */
 317   ret = end_offset / bds;
 318   return ret % CHK_PER_INODE;
 319 }
 320
 321
 322 /**
 323  * Encrypt the next block of the file (and call proc and progress
 324  * accordingly; or of course "cont" if we have already completed
 325  * encoding of the entire file).
 326  *
 327  * @param te tree encoder to use
 328  */
 329 void
 330 GNUNET_FS_tree_encoder_next(struct GNUNET_FS_TreeEncoder *te)
 331 {
 332   struct ContentHashKey *mychk;
 333   const void *pt_block;
 334   uint16_t pt_size;
 335   char iob[DBLOCK_SIZE];
 336   char enc[DBLOCK_SIZE];
 337   struct GNUNET_CRYPTO_SymmetricSessionKey sk;
 338   struct GNUNET_CRYPTO_SymmetricInitializationVector iv;
 339   unsigned int off;
 340
 341   GNUNET_assert(GNUNET_NO == te->in_next);
 342   te->in_next = GNUNET_YES;
 343   if (te->chk_tree_depth == te->current_depth)
 344     {
 345       off = CHK_PER_INODE * (te->chk_tree_depth - 1);
 346       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
 347                  GNUNET_h2s(&te->chk_tree[off].query), off);
 348       te->uri = GNUNET_new(struct GNUNET_FS_Uri);
 349       te->uri->type = GNUNET_FS_URI_CHK;
 350       te->uri->data.chk.chk = te->chk_tree[off];
 351       te->uri->data.chk.file_length = GNUNET_htonll(te->size);
 352       te->in_next = GNUNET_NO;
 353       te->cont(te->cls);
 354       return;
 355     }
 356   if (0 == te->current_depth)
 357     {
 358       /* read DBLOCK */
 359       pt_size = GNUNET_MIN(DBLOCK_SIZE, te->size - te->publish_offset);
 360       if (pt_size !=
 361           te->reader(te->cls, te->publish_offset, pt_size, iob, &te->emsg))
 362         {
 363           te->in_next = GNUNET_NO;
 364           te->cont(te->cls);
 365           return;
 366         }
 367       pt_block = iob;
 368     }
 369   else
 370     {
 371       pt_size =
 372         GNUNET_FS_tree_compute_iblock_size(te->current_depth,
 373                                            te->publish_offset);
 374       pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
 375     }
 376   off = compute_chk_offset(te->current_depth, te->publish_offset);
 377   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 378              "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
 379              (unsigned long long)te->publish_offset, te->current_depth,
 380              (unsigned int)pt_size, (unsigned int)off);
 381   mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off];
 382   GNUNET_CRYPTO_hash(pt_block, pt_size, &mychk->key);
 383   GNUNET_CRYPTO_hash_to_aes_key(&mychk->key, &sk, &iv);
 384   GNUNET_CRYPTO_symmetric_encrypt(pt_block, pt_size, &sk, &iv, enc);
 385   GNUNET_CRYPTO_hash(enc, pt_size, &mychk->query);
 386   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 387              "TE calculates query to be `%s', stored at %u\n",
 388              GNUNET_h2s(&mychk->query),
 389              te->current_depth * CHK_PER_INODE + off);
 390   if (NULL != te->proc)
 391     te->proc(te->cls, mychk, te->publish_offset, te->current_depth,
 392              (0 ==
 393               te->current_depth) ? GNUNET_BLOCK_TYPE_FS_DBLOCK :
 394              GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size);
 395   if (NULL != te->progress)
 396     te->progress(te->cls, te->publish_offset, pt_block, pt_size,
 397                  te->current_depth);
 398   if (0 == te->current_depth)
 399     {
 400       te->publish_offset += pt_size;
 401       if ((te->publish_offset == te->size) ||
 402           (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
 403         te->current_depth++;
 404     }
 405   else
 406     {
 407       if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
 408         te->current_depth++;
 409       else
 410         te->current_depth = 0;
 411     }
 412   te->in_next = GNUNET_NO;
 413 }
 414
 415
 416 /**
 417  * Get the resulting URI from the encoding.
 418  *
 419  * @param te the tree encoder to clean up
 420  * @return uri set to the resulting URI (if encoding finished), NULL otherwise
 421  */
 422 struct GNUNET_FS_Uri *
 423 GNUNET_FS_tree_encoder_get_uri(struct GNUNET_FS_TreeEncoder *te)
 424 {
 425   if (NULL != te->uri)
 426     return GNUNET_FS_uri_dup(te->uri);
 427   return NULL;
 428 }
 429
 430
 431 /**
 432  * Clean up a tree encoder and return information
 433  * about possible errors.
 434  *
 435  * @param te the tree encoder to clean up
 436  * @param emsg set to an error message (if an error occured
 437  *        within the tree encoder; if this function is called
 438  *        prior to completion and prior to an internal error,
 439  *        both "*emsg" will be set to NULL).
 440  */
 441 void
 442 GNUNET_FS_tree_encoder_finish(struct GNUNET_FS_TreeEncoder *te,
 443                               char **emsg)
 444 {
 445   if (NULL != te->reader)
 446     {
 447       (void)te->reader(te->cls, UINT64_MAX, 0, 0, NULL);
 448       te->reader = NULL;
 449     }
 450   GNUNET_assert(GNUNET_NO == te->in_next);
 451   if (NULL != te->uri)
 452     GNUNET_FS_uri_destroy(te->uri);
 453   if (emsg != NULL)
 454     *emsg = te->emsg;
 455   else
 456     GNUNET_free_non_null(te->emsg);
 457   GNUNET_free(te->chk_tree);
 458   GNUNET_free(te);
 459 }
 460
 461 /* end of fs_tree.c */