GNUnet  0.20.0
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_TreeEncoderGNUNET_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_UriGNUNET_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
clsclosure
chkcontent hash key for the block
offsetoffset of the block
depthdepth of the block, 0 for DBLOCKs
typetype of the block (IBLOCK or DBLOCK)
blockthe (encrypted) block
block_sizesize 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
clsclosure
offsetwhere are we in the file
pt_blockplaintext of the currently processed block
pt_sizesize of pt_block
depthdepth 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
flenfile 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.

126 {
127  unsigned int treeDepth;
128  uint64_t fl;
129 
130  treeDepth = 1;
131  fl = DBLOCK_SIZE;
132  while (fl < flen)
133  {
134  treeDepth++;
135  if (fl * CHK_PER_INODE < fl)
136  {
137  /* integer overflow, this is a HUGE file... */
138  return treeDepth;
139  }
140  fl = fl * CHK_PER_INODE;
141  }
142  return treeDepth;
143 }
#define DBLOCK_SIZE
Size of the individual blocks used for file-sharing.
Definition: fs.h:41
#define CHK_PER_INODE
Pick a multiple of 2 here to achieve 8-byte alignment! We also probably want DBlocks to have (roughly...
Definition: fs_api.h:44

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
depthdepth 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.

157 {
158  uint64_t rsize;
159  unsigned int i;
160 
161  rsize = DBLOCK_SIZE;
162  for (i = 0; i < depth; i++)
163  rsize *= CHK_PER_INODE;
164  return rsize;
165 }

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
fsizeoverall file size, must be > 0.
offsetoffset in the original data corresponding to the beginning of the tree induced by the block; must be < fsize
depthdepth 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.

213 {
214  size_t ret;
215  uint64_t rsize;
216  uint64_t epos;
217  unsigned int chks;
218 
219  GNUNET_assert (fsize > 0);
220  GNUNET_assert (offset <= fsize);
221  if (depth == 0)
222  {
223  ret = DBLOCK_SIZE;
224  if ((offset + ret > fsize) || (offset + ret < offset))
225  ret = (size_t) (fsize - offset);
226  return ret;
227  }
228 
229  rsize = GNUNET_FS_tree_compute_tree_size (depth - 1);
230  epos = offset + rsize * CHK_PER_INODE;
231  if ((epos < offset) || (epos > fsize))
232  epos = fsize;
233  /* round up when computing #CHKs in our IBlock */
234  chks = (epos - offset + rsize - 1) / rsize;
235  GNUNET_assert (chks <= CHK_PER_INODE);
236  return chks * sizeof(struct ContentHashKey);
237 }
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 f...
Definition: fs_tree.c:156
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
content hash key
Definition: fs.h:55

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
hthe global FS context
sizeoverall size of the file to encode
clsclosure for reader, proc, progress and cont
readerfunction to call to read plaintext data
procfunction to call on each encrypted block
progressfunction to call with progress information
contfunction 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
hthe global FS context
sizeoverall size of the file to encode
clsclosure for reader, proc, progress and cont
readerfunction to call to read plaintext data
procfunction to call on each encrypted block
progressfunction to call with progress information
contfunction to call when done

Definition at line 258 of file fs_tree.c.

264 {
265  struct GNUNET_FS_TreeEncoder *te;
266 
267  te = GNUNET_new (struct GNUNET_FS_TreeEncoder);
268  te->h = h;
269  te->size = size;
270  te->cls = cls;
271  te->reader = reader;
272  te->proc = proc;
273  te->progress = progress;
274  te->cont = cont;
276  te->chk_tree
278  struct ContentHashKey);
280  "Created tree encoder for file with %llu bytes and depth %u\n",
281  (unsigned long long) size,
282  te->chk_tree_depth);
283  return te;
284 }
unsigned int GNUNET_FS_compute_depth(uint64_t flen)
Compute the depth of the CHK tree.
Definition: fs_tree.c:125
static struct GNUNET_ARM_Handle * h
Connection with ARM.
Definition: gnunet-arm.c:99
#define GNUNET_log(kind,...)
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
static unsigned int size
Size of the "table".
Definition: peer.c:68
Context for an ECRS-based file encoder that computes the Merkle-ish-CHK tree.
Definition: fs_tree.c:36
GNUNET_FS_TreeProgressCallback progress
Function to call with progress information.
Definition: fs_tree.c:55
void * cls
Closure for all callbacks.
Definition: fs_tree.c:45
GNUNET_FS_TreeBlockProcessor proc
Function to call on encrypted blocks.
Definition: fs_tree.c:50
struct ContentHashKey * chk_tree
In-memory cache of the current CHK tree.
Definition: fs_tree.c:108
GNUNET_FS_DataReader reader
Function to call to receive input data.
Definition: fs_tree.c:60
unsigned int chk_tree_depth
How deep is the tree? Always > 0.
Definition: fs_tree.c:95
GNUNET_SCHEDULER_TaskCallback cont
Function to call once we're done with processing.
Definition: fs_tree.c:65
uint64_t size
Overall file size.
Definition: fs_tree.c:80
struct GNUNET_FS_Handle * h
Global FS context.
Definition: fs_tree.c:40

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
tetree encoder to use

Definition at line 320 of file fs_tree.c.

321 {
322  struct ContentHashKey *mychk;
323  const void *pt_block;
324  uint16_t pt_size;
325  char iob[DBLOCK_SIZE];
326  char enc[DBLOCK_SIZE];
329  unsigned int off;
330 
332  te->in_next = GNUNET_YES;
333  if (te->chk_tree_depth == te->current_depth)
334  {
335  off = CHK_PER_INODE * (te->chk_tree_depth - 1);
336  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
337  GNUNET_h2s (&te->chk_tree[off].query), off);
338  te->uri = GNUNET_new (struct GNUNET_FS_Uri);
339  te->uri->type = GNUNET_FS_URI_CHK;
340  te->uri->data.chk.chk = te->chk_tree[off];
341  te->uri->data.chk.file_length = GNUNET_htonll (te->size);
342  te->in_next = GNUNET_NO;
343  te->cont (te->cls);
344  return;
345  }
346  if (0 == te->current_depth)
347  {
348  /* read DBLOCK */
349  pt_size = GNUNET_MIN (DBLOCK_SIZE, te->size - te->publish_offset);
350  if (pt_size !=
351  te->reader (te->cls, te->publish_offset, pt_size, iob, &te->emsg))
352  {
353  te->in_next = GNUNET_NO;
354  te->cont (te->cls);
355  return;
356  }
357  pt_block = iob;
358  }
359  else
360  {
361  pt_size =
363  te->publish_offset);
364  pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
365  }
368  "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
369  (unsigned long long) te->publish_offset, te->current_depth,
370  (unsigned int) pt_size, (unsigned int) off);
371  mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off];
372  GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
373  GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
374  GNUNET_CRYPTO_symmetric_encrypt (pt_block, pt_size, &sk, &iv, enc);
375  GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
377  "TE calculates query to be `%s', stored at %u\n",
378  GNUNET_h2s (&mychk->query),
379  te->current_depth * CHK_PER_INODE + off);
380  if (NULL != te->proc)
381  te->proc (te->cls, mychk, te->publish_offset, te->current_depth,
382  (0 ==
384  GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size);
385  if (NULL != te->progress)
386  te->progress (te->cls, te->publish_offset, pt_block, pt_size,
387  te->current_depth);
388  if (0 == te->current_depth)
389  {
390  te->publish_offset += pt_size;
391  if ((te->publish_offset == te->size) ||
392  (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
393  te->current_depth++;
394  }
395  else
396  {
397  if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
398  te->current_depth++;
399  else
400  te->current_depth = 0;
401  }
402  te->in_next = GNUNET_NO;
403 }
@ GNUNET_BLOCK_TYPE_FS_IBLOCK
Inner block in the CHK tree.
@ GNUNET_BLOCK_TYPE_FS_DBLOCK
Data block (leaf) in the CHK tree.
@ GNUNET_FS_URI_CHK
Content-hash-key (simple file).
Definition: fs_api.h:144
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.
Definition: fs_tree.c:299
static uint16_t GNUNET_FS_tree_compute_iblock_size(unsigned int depth, uint64_t end_offset)
Compute the size of the current IBLOCK.
Definition: fs_tree.c:183
static OpusEncoder * enc
OPUS encoder.
ssize_t GNUNET_CRYPTO_symmetric_encrypt(const void *block, size_t size, const struct GNUNET_CRYPTO_SymmetricSessionKey *sessionkey, const struct GNUNET_CRYPTO_SymmetricInitializationVector *iv, void *result)
Encrypt a block using a symmetric sessionkey.
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
Definition: crypto_hash.c:41
void GNUNET_CRYPTO_hash_to_aes_key(const struct GNUNET_HashCode *hc, struct GNUNET_CRYPTO_SymmetricSessionKey *skey, struct GNUNET_CRYPTO_SymmetricInitializationVector *iv)
Convert a hashcode into a key.
Definition: crypto_hash.c:152
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:37
#define GNUNET_MIN(a, b)
@ GNUNET_YES
@ GNUNET_NO
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
struct GNUNET_HashCode key
Hash of the original content, used for encryption.
Definition: fs.h:59
struct GNUNET_HashCode query
Hash of the encrypted content, used for querying.
Definition: fs.h:64
struct ContentHashKey chk
Query and key of the top GNUNET_EC_IBlock.
Definition: fs_api.h:104
uint64_t file_length
Total size of the file in bytes.
Definition: fs_api.h:99
char * emsg
Set to an error message (if we had an error).
Definition: fs_tree.c:70
struct GNUNET_FS_Uri * uri
Set to the URI (upon successful completion)
Definition: fs_tree.c:75
int in_next
Are we currently in 'GNUNET_FS_tree_encoder_next'? Flag used to prevent recursion.
Definition: fs_tree.c:114
uint64_t publish_offset
How far are we?
Definition: fs_tree.c:85
unsigned int current_depth
How deep are we? Depth 0 is for the DBLOCKs.
Definition: fs_tree.c:90
A Universal Resource Identifier (URI), opaque.
Definition: fs_api.h:167
union GNUNET_FS_Uri::@13 data
enum GNUNET_FS_UriType type
Type of the URI.
Definition: fs_api.h:171
struct FileIdentifier chk
Information needed to retrieve a file (content-hash-key plus file size).
Definition: fs_api.h:212

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
tethe 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.

414 {
415  if (NULL != te->uri)
416  return GNUNET_FS_uri_dup (te->uri);
417  return NULL;
418 }
struct GNUNET_FS_Uri * GNUNET_FS_uri_dup(const struct GNUNET_FS_Uri *uri)
Duplicate URI.
Definition: fs_uri.c:987

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
tethe tree encoder to clean up
emsgset 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.

434 {
435  if (NULL != te->reader)
436  {
437  (void) te->reader (te->cls, UINT64_MAX, 0, 0, NULL);
438  te->reader = NULL;
439  }
441  if (NULL != te->uri)
443  if (emsg != NULL)
444  *emsg = te->emsg;
445  else
446  GNUNET_free (te->emsg);
447  GNUNET_free (te->chk_tree);
448  GNUNET_free (te);
449 }
void GNUNET_FS_uri_destroy(struct GNUNET_FS_Uri *uri)
Free URI.
Definition: fs_uri.c:677
#define GNUNET_free(ptr)
Wrapper around free.

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: