fs_tree.h File Reference

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

#include "fs_api.h"

Include dependency graph for fs_tree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef void(*	GNUNET_FS_TreeBlockProcessor) (void *cls, const struct ContentHashKey *chk, uint64_t offset, unsigned int depth, enum GNUNET_BLOCK_Type type, const void *block, uint16_t block_size)
	Function called asking for the current (encoded) block to be processed. More...
typedef void(*	GNUNET_FS_TreeProgressCallback) (void *cls, uint64_t offset, const void *pt_block, size_t pt_size, unsigned int depth)
	Function called with information about our progress in computing the tree encoding. 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...
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...
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

https://gnunet.org/encoding

Author

Krista Bennett

Christian Grothoff

TODO:

• decide if this API should be made public (gnunet_fs_service.h) or remain "internal" (but with exported symbols?)

Definition in file fs_tree.h.

Typedef Documentation

GNUNET_FS_TreeBlockProcessor

typedef void(* GNUNET_FS_TreeBlockProcessor) (void *cls, const struct ContentHashKey *chk, uint64_t offset, unsigned int depth, enum GNUNET_BLOCK_Type type, const void *block, uint16_t block_size)

Function called asking for the current (encoded) block to be processed.

After processing the client should either call "GNUNET_FS_tree_encode_next" or (on error) "GNUNET_FS_tree_encode_finish".

Parameters

cls	closure
chk	content hash key for the block
offset	offset of the block
depth	depth of the block, 0 for DBLOCKs
type	type of the block (IBLOCK or DBLOCK)
block	the (encrypted) block
block_size	size of block (in bytes)

Definition at line 97 of file fs_tree.h.

GNUNET_FS_TreeProgressCallback

typedef void(* GNUNET_FS_TreeProgressCallback) (void *cls, uint64_t offset, const void *pt_block, size_t pt_size, unsigned int depth)

Function called with information about our progress in computing the tree encoding.

Parameters

cls	closure
offset	where are we in the file
pt_block	plaintext of the currently processed block
pt_size	size of pt_block
depth	depth of the block in the tree, 0 for DBLOCKS

Definition at line 116 of file fs_tree.h.

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_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 actually never call "proc"; the "proc" function must be triggered by calling "GNUNET_FS_tree_encoder_next" to trigger encryption (and calling of "proc") for 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

Returns

tree encoder context

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, GNUNET_FS_TreeEncoder::size, and 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:

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 GNUNET_FS_Uri::chk, FileIdentifier::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_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: