fs_tree.c

Go to the documentation of this file.

/*
     This file is part of GNUnet.
     Copyright (C) 2009-2011 GNUnet e.V.
 
     GNUnet is free software: you can redistribute it and/or modify it
     under the terms of the GNU Affero General Public License as published
     by the Free Software Foundation, either version 3 of the License,
     or (at your option) any later version.
 
     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     Affero General Public License for more details.
 
     You should have received a copy of the GNU Affero General Public License
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
     SPDX-License-Identifier: AGPL3.0-or-later
 */
#include "platform.h"
#include "fs_tree.h"
 
 
struct GNUNET_FS_TreeEncoder
{
  struct GNUNET_FS_Handle *h;
 
  void *cls;
 
  GNUNET_FS_TreeBlockProcessor proc;
 
  GNUNET_FS_TreeProgressCallback progress;
 
  GNUNET_FS_DataReader reader;
 
  GNUNET_SCHEDULER_TaskCallback cont;
 
  char *emsg;
 
  struct GNUNET_FS_Uri *uri;
 
  uint64_t size;
 
  uint64_t publish_offset;
 
  unsigned int current_depth;
 
  unsigned int chk_tree_depth;
 
  struct ContentHashKey *chk_tree;
 
  int in_next;
};
 
 
unsigned int
GNUNET_FS_compute_depth (uint64_t flen)
{
  unsigned int treeDepth;
  uint64_t fl;
 
  treeDepth = 1;
  fl = DBLOCK_SIZE;
  while (fl < flen)
  {
    treeDepth++;
    if (fl * CHK_PER_INODE < fl)
    {
      /* integer overflow, this is a HUGE file... */
      return treeDepth;
    }
    fl = fl * CHK_PER_INODE;
  }
  return treeDepth;
}
 
 
uint64_t
GNUNET_FS_tree_compute_tree_size (unsigned int depth)
{
  uint64_t rsize;
  unsigned int i;
 
  rsize = DBLOCK_SIZE;
  for (i = 0; i < depth; i++)
    rsize *= CHK_PER_INODE;
  return rsize;
}
 
 
static uint16_t
GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset)
{
  unsigned int ret;
  uint64_t mod;
  uint64_t bds;
 
  GNUNET_assert (depth > 0);
  GNUNET_assert (end_offset > 0);
  bds = GNUNET_FS_tree_compute_tree_size (depth);
  mod = end_offset % bds;
  if (0 == mod)
  {
    /* we were triggered at the end of a full block */
    ret = CHK_PER_INODE;
  }
  else
  {
    /* we were triggered at the end of the file */
    bds /= CHK_PER_INODE;
    ret = mod / bds;
    if (0 != mod % bds)
      ret++;
  }
  return (uint16_t) (ret * sizeof(struct ContentHashKey));
}
 
 
size_t
GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset,
                                     unsigned int depth)
{
  size_t ret;
  uint64_t rsize;
  uint64_t epos;
  unsigned int chks;
 
  GNUNET_assert (fsize > 0);
  GNUNET_assert (offset <= fsize);
  if (depth == 0)
  {
    ret = DBLOCK_SIZE;
    if ((offset + ret > fsize) || (offset + ret < offset))
      ret = (size_t) (fsize - offset);
    return ret;
  }
 
  rsize = GNUNET_FS_tree_compute_tree_size (depth - 1);
  epos = offset + rsize * CHK_PER_INODE;
  if ((epos < offset) || (epos > fsize))
    epos = fsize;
  /* round up when computing #CHKs in our IBlock */
  chks = (epos - offset + rsize - 1) / rsize;
  GNUNET_assert (chks <= CHK_PER_INODE);
  return chks * sizeof(struct ContentHashKey);
}
 
 
struct GNUNET_FS_TreeEncoder *
GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, uint64_t size,
                               void *cls,
                               GNUNET_FS_DataReader reader,
                               GNUNET_FS_TreeBlockProcessor proc,
                               GNUNET_FS_TreeProgressCallback progress,
                               GNUNET_SCHEDULER_TaskCallback cont)
{
  struct GNUNET_FS_TreeEncoder *te;
 
  te = GNUNET_new (struct GNUNET_FS_TreeEncoder);
  te->h = h;
  te->size = size;
  te->cls = cls;
  te->reader = reader;
  te->proc = proc;
  te->progress = progress;
  te->cont = cont;
  te->chk_tree_depth = GNUNET_FS_compute_depth (size);
  te->chk_tree
    = GNUNET_new_array (te->chk_tree_depth * CHK_PER_INODE,
                        struct ContentHashKey);
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "Created tree encoder for file with %llu bytes and depth %u\n",
              (unsigned long long) size,
              te->chk_tree_depth);
  return te;
}
 
 
static unsigned int
compute_chk_offset (unsigned int depth, uint64_t end_offset)
{
  uint64_t bds;
  unsigned int ret;
 
  bds = GNUNET_FS_tree_compute_tree_size (depth);
  if (depth > 0)
    end_offset--;               /* round down since for depth > 0 offset is at the END of the block */
  ret = end_offset / bds;
  return ret % CHK_PER_INODE;
}
 
 
void
GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te)
{
  struct ContentHashKey *mychk;
  const void *pt_block;
  uint16_t pt_size;
  uint16_t ct_size;
  char iob[DBLOCK_SIZE];
  char enc[DBLOCK_SIZE];
  struct GNUNET_CRYPTO_AeadSecretKey sk;
  struct GNUNET_CRYPTO_AeadNonce iv;
  unsigned int off;
 
  GNUNET_assert (GNUNET_NO == te->in_next);
  te->in_next = GNUNET_YES;
  if (te->chk_tree_depth == te->current_depth)
  {
    off = CHK_PER_INODE * (te->chk_tree_depth - 1);
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
                GNUNET_h2s (&te->chk_tree[off].query), off);
    te->uri = GNUNET_new (struct GNUNET_FS_Uri);
    te->uri->type = GNUNET_FS_URI_CHK;
    te->uri->data.chk.chk = te->chk_tree[off];
    te->uri->data.chk.file_length = GNUNET_htonll (te->size);
    te->in_next = GNUNET_NO;
    te->cont (te->cls);
    return;
  }
  if (0 == te->current_depth)
  {
    /* read DBLOCK */
    pt_size = GNUNET_MIN (DBLOCK_SIZE, te->size - te->publish_offset);
    if (pt_size !=
        te->reader (te->cls, te->publish_offset, pt_size, iob, &te->emsg))
    {
      te->in_next = GNUNET_NO;
      te->cont (te->cls);
      return;
    }
    pt_block = iob;
  }
  else
  {
    pt_size =
      GNUNET_FS_tree_compute_iblock_size (te->current_depth,
                                          te->publish_offset);
    pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
  }
  off = compute_chk_offset (te->current_depth, te->publish_offset);
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
              (unsigned long long) te->publish_offset, te->current_depth,
              (unsigned int) pt_size, (unsigned int) off);
  mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off];
  GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
  GNUNET_FS_hash_to_symmetric_key (&mychk->key, &sk, &iv);
  ct_size = pt_size + sizeof (struct GNUNET_CRYPTO_AeadMac);
  GNUNET_assert (pt_size <= sizeof (enc) - sizeof (struct
                                                   GNUNET_CRYPTO_AeadMac));
  GNUNET_CRYPTO_aead_encrypt (pt_size,
                              pt_block,
                              0,
                              NULL,
                              &sk,
                              &iv,
                              enc,
                              (struct GNUNET_CRYPTO_AeadMac*) &enc[pt_size]);
  GNUNET_CRYPTO_hash (enc,
                      ct_size,
                      &mychk->query);
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "TE calculates query to be `%s', stored at %u\n",
              GNUNET_h2s (&mychk->query),
              te->current_depth * CHK_PER_INODE + off);
  if (NULL != te->proc)
    te->proc (te->cls, mychk, te->publish_offset, te->current_depth,
              (0 ==
               te->current_depth) ? GNUNET_BLOCK_TYPE_FS_DBLOCK :
              GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, ct_size);
  if (NULL != te->progress)
    te->progress (te->cls, te->publish_offset, pt_block, pt_size,
                  te->current_depth);
  if (0 == te->current_depth)
  {
    te->publish_offset += pt_size;
    if ((te->publish_offset == te->size) ||
        (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
      te->current_depth++;
  }
  else
  {
    if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
      te->current_depth++;
    else
      te->current_depth = 0;
  }
  te->in_next = GNUNET_NO;
}
 
 
struct GNUNET_FS_Uri *
GNUNET_FS_tree_encoder_get_uri (struct GNUNET_FS_TreeEncoder *te)
{
  if (NULL != te->uri)
    return GNUNET_FS_uri_dup (te->uri);
  return NULL;
}
 
 
void
GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te,
                               char **emsg)
{
  if (NULL != te->reader)
  {
    (void) te->reader (te->cls, UINT64_MAX, 0, 0, NULL);
    te->reader = NULL;
  }
  GNUNET_assert (GNUNET_NO == te->in_next);
  if (NULL != te->uri)
    GNUNET_FS_uri_destroy (te->uri);
  if (emsg != NULL)
    *emsg = te->emsg;
  else
    GNUNET_free (te->emsg);
  GNUNET_free (te->chk_tree);
  GNUNET_free (te);
}
 
 
/* end of fs_tree.c */