fs_tree.c File Reference

Merkle-tree-ish-CHK file encoding for GNUnet. More...

#include "platform.h"
#include "fs_tree.h"

Include dependency graph for fs_tree.c:

Go to the source code of this file.

Data Structures
struct	GNUNET_FS_TreeEncoder
	Context for an ECRS-based file encoder that computes the Merkle-ish-CHK tree. More...

Functions
unsigned int	GNUNET_FS_compute_depth (uint64_t flen)
	Compute the depth of the CHK tree. More...
uint64_t	GNUNET_FS_tree_compute_tree_size (unsigned int depth)
	Calculate how many bytes of payload a block tree of the given depth MAY correspond to at most (this function ignores the fact that some blocks will only be present partially due to the total file size cutting some blocks off at the end). More...
static uint16_t	GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset)
	Compute the size of the current IBLOCK. More...
size_t	GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset, unsigned int depth)
	Compute how many bytes of data should be stored in the specified block. More...
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)
	Initialize a tree encoder. More...
static unsigned int	compute_chk_offset (unsigned int depth, uint64_t end_offset)
	Compute the offset of the CHK for the current block in the IBlock above. More...
void	GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te)
	Encrypt the next block of the file (and call proc and progress accordingly; or of course "cont" if we have already completed encoding of the entire file). More...
struct GNUNET_FS_Uri *	GNUNET_FS_tree_encoder_get_uri (struct GNUNET_FS_TreeEncoder *te)
	Get the resulting URI from the encoding. More...
void	GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te, char **emsg)
	Clean up a tree encoder and return information about possible errors. More...

Detailed Description

Merkle-tree-ish-CHK file encoding for GNUnet.

See also

http://gnunet.org/encoding.php3

Author

Krista Bennett

Christian Grothoff

Definition in file fs_tree.c.

Function Documentation

GNUNET_FS_compute_depth()

unsigned int GNUNET_FS_compute_depth

(

uint64_t

flen

)

Compute the depth of the CHK tree.

Parameters

flen	file length for which to compute the depth

Returns

depth of the tree, always > 0. A depth of 1 means only a DBLOCK.

Definition at line 125 of file fs_tree.c.

{
  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;
}

References CHK_PER_INODE, and DBLOCK_SIZE.

Referenced by create_download_context(), deserialize_download(), encode_cont(), and GNUNET_FS_tree_encoder_create().

Here is the caller graph for this function:

GNUNET_FS_tree_compute_tree_size()

uint64_t GNUNET_FS_tree_compute_tree_size

(

unsigned int

depth

)

Calculate how many bytes of payload a block tree of the given depth MAY correspond to at most (this function ignores the fact that some blocks will only be present partially due to the total file size cutting some blocks off at the end).

Parameters

depth

depth of the block. depth==0 is a DBLOCK.

Returns

number of bytes of payload a subtree of this depth may correspond to

Definition at line 156 of file fs_tree.c.

{
  uint64_t rsize;
  unsigned int i;
 
  rsize = DBLOCK_SIZE;
  for (i = 0; i < depth; i++)
    rsize *= CHK_PER_INODE;
  return rsize;
}

References CHK_PER_INODE, and DBLOCK_SIZE.

Referenced by compute_chk_offset(), create_download_request(), GNUNET_FS_tree_calculate_block_size(), GNUNET_FS_tree_compute_iblock_size(), reconstruct_cb(), and try_top_down_reconstruction().

Here is the caller graph for this function:

GNUNET_FS_tree_compute_iblock_size()

static uint16_t GNUNET_FS_tree_compute_iblock_size ( unsigned int  depth, uint64_t  end_offset  )

static

Compute the size of the current IBLOCK.

The encoder is triggering the calculation of the size of an IBLOCK at the end (hence end_offset) of its construction. The IBLOCK maybe a full or a partial IBLOCK, and this function is to calculate how long it should be.

Parameters

depth	depth of the IBlock in the tree, 0 would be a DBLOCK, must be > 0 (this function is for IBLOCKs only!)
end_offset	current offset in the payload (!) of the overall file, must be > 0 (since this function is called at the end of a block).

Returns

size of the corresponding IBlock

Definition at line 183 of file fs_tree.c.

{
  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));
}

References CHK_PER_INODE, GNUNET_assert, GNUNET_FS_tree_compute_tree_size(), and ret.

Referenced by GNUNET_FS_tree_encoder_next().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_FS_tree_calculate_block_size()

size_t GNUNET_FS_tree_calculate_block_size	(	uint64_t	fsize,
		uint64_t	offset,
		unsigned int	depth
	)

Compute how many bytes of data should be stored in the specified block.

Parameters

fsize	overall file size, must be > 0.
offset	offset in the original data corresponding to the beginning of the tree induced by the block; must be < fsize
depth	depth of the node in the tree, 0 for DBLOCK

Returns

number of bytes stored in this node

Definition at line 211 of file fs_tree.c.

{
  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);
}

References CHK_PER_INODE, DBLOCK_SIZE, GNUNET_assert, GNUNET_FS_tree_compute_tree_size(), and ret.

Referenced by process_result_with_request(), and try_top_down_reconstruction().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_FS_tree_encoder_create()

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
	)

Initialize a tree encoder.

This function will call proc and "progress" on each block in the tree. Once all blocks have been processed, "cont" will be scheduled. The reader will be called to obtain the (plaintext) blocks for the file. Note that this function will not actually call proc. The client must call GNUNET_FS_tree_encoder_next to trigger encryption (and calling of proc) for the each block.

Parameters

h	the global FS context
size	overall size of the file to encode
cls	closure for reader, proc, progress and cont
reader	function to call to read plaintext data
proc	function to call on each encrypted block
progress	function to call with progress information
cont	function to call when done

Definition at line 258 of file fs_tree.c.

{
  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;
}

References CHK_PER_INODE, GNUNET_FS_TreeEncoder::chk_tree, GNUNET_FS_TreeEncoder::chk_tree_depth, GNUNET_FS_TreeEncoder::cls, GNUNET_FS_TreeEncoder::cont, GNUNET_ERROR_TYPE_DEBUG, GNUNET_FS_compute_depth(), GNUNET_log, GNUNET_new, GNUNET_new_array, h, GNUNET_FS_TreeEncoder::h, GNUNET_FS_TreeEncoder::proc, GNUNET_FS_TreeEncoder::progress, GNUNET_FS_TreeEncoder::reader, size, and GNUNET_FS_TreeEncoder::size.

Referenced by GNUNET_FS_download_start_task_(), GNUNET_FS_unindex_do_remove_(), and publish_content().

Here is the call graph for this function:

Here is the caller graph for this function:

compute_chk_offset()

static unsigned int compute_chk_offset ( unsigned int  depth, uint64_t  end_offset  )

static

Compute the offset of the CHK for the current block in the IBlock above.

Parameters

depth	depth of the IBlock in the tree (aka overall number of tree levels minus depth); 0 == DBlock
end_offset	current offset in the overall file, at the beginning of the block for DBLOCKs (depth==0), otherwise at the end of the block (exclusive)

Returns

(array of CHKs') offset in the above IBlock

Definition at line 299 of file fs_tree.c.

{
  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;
}

References CHK_PER_INODE, GNUNET_FS_tree_compute_tree_size(), and ret.

Referenced by GNUNET_FS_tree_encoder_next().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_FS_tree_encoder_next()

void GNUNET_FS_tree_encoder_next

(

struct GNUNET_FS_TreeEncoder *

te

)

Encrypt the next block of the file (and call proc and progress accordingly; or of course "cont" if we have already completed encoding of the entire file).

Parameters

te	tree encoder to use

Definition at line 320 of file fs_tree.c.

{
  struct ContentHashKey *mychk;
  const void *pt_block;
  uint16_t pt_size;
  char iob[DBLOCK_SIZE];
  char enc[DBLOCK_SIZE];
  struct GNUNET_CRYPTO_SymmetricSessionKey sk;
  struct GNUNET_CRYPTO_SymmetricInitializationVector 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_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
  GNUNET_CRYPTO_symmetric_encrypt (pt_block, pt_size, &sk, &iv, enc);
  GNUNET_CRYPTO_hash (enc, pt_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, pt_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;
}

References FileIdentifier::chk, GNUNET_FS_Uri::chk, CHK_PER_INODE, GNUNET_FS_TreeEncoder::chk_tree, GNUNET_FS_TreeEncoder::chk_tree_depth, GNUNET_FS_TreeEncoder::cls, compute_chk_offset(), GNUNET_FS_TreeEncoder::cont, GNUNET_FS_TreeEncoder::current_depth, GNUNET_FS_Uri::data, DBLOCK_SIZE, GNUNET_FS_TreeEncoder::emsg, enc, FileIdentifier::file_length, GNUNET_assert, GNUNET_BLOCK_TYPE_FS_DBLOCK, GNUNET_BLOCK_TYPE_FS_IBLOCK, GNUNET_CRYPTO_hash(), GNUNET_CRYPTO_hash_to_aes_key(), GNUNET_CRYPTO_symmetric_encrypt(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_FS_tree_compute_iblock_size(), GNUNET_FS_URI_CHK, GNUNET_h2s(), GNUNET_htonll(), GNUNET_log, GNUNET_MIN, GNUNET_new, GNUNET_NO, GNUNET_YES, GNUNET_FS_TreeEncoder::in_next, ContentHashKey::key, GNUNET_FS_TreeEncoder::proc, GNUNET_FS_TreeEncoder::progress, GNUNET_FS_TreeEncoder::publish_offset, ContentHashKey::query, GNUNET_FS_TreeEncoder::reader, GNUNET_FS_TreeEncoder::size, GNUNET_FS_Uri::type, and GNUNET_FS_TreeEncoder::uri.

Referenced by get_next_block(), GNUNET_FS_unindex_do_remove_(), process_cont(), and publish_content().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_FS_tree_encoder_get_uri()

struct GNUNET_FS_Uri * GNUNET_FS_tree_encoder_get_uri

(

struct GNUNET_FS_TreeEncoder *

te

)

Get the resulting URI from the encoding.

Parameters

te	the tree encoder to clean up

Returns

uri set to the resulting URI (if encoding finished), NULL otherwise

Definition at line 413 of file fs_tree.c.

{
  if (NULL != te->uri)
    return GNUNET_FS_uri_dup (te->uri);
  return NULL;
}

References GNUNET_FS_uri_dup(), and GNUNET_FS_TreeEncoder::uri.

Referenced by encode_cont().

Here is the call graph for this function:

Here is the caller graph for this function:

GNUNET_FS_tree_encoder_finish()

void GNUNET_FS_tree_encoder_finish	(	struct GNUNET_FS_TreeEncoder *	te,
		char **	emsg
	)

Clean up a tree encoder and return information about possible errors.

Parameters

te	the tree encoder to clean up
emsg	set to an error message (if an error occurred within the tree encoder; if this function is called prior to completion and prior to an internal error, both "*emsg" will be set to NULL).

Definition at line 432 of file fs_tree.c.

{
  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);
}

References GNUNET_FS_TreeEncoder::chk_tree, GNUNET_FS_TreeEncoder::cls, GNUNET_FS_TreeEncoder::emsg, GNUNET_assert, GNUNET_free, GNUNET_FS_uri_destroy(), GNUNET_NO, GNUNET_FS_TreeEncoder::in_next, GNUNET_FS_TreeEncoder::reader, and GNUNET_FS_TreeEncoder::uri.

Referenced by encode_cont(), GNUNET_FS_download_signal_suspend_(), GNUNET_FS_download_stop(), GNUNET_FS_file_information_destroy(), GNUNET_FS_unindex_signal_suspend_(), GNUNET_FS_unindex_stop(), and unindex_finish().

Here is the call graph for this function:

Here is the caller graph for this function: