GNUnet  0.11.x
fs_tree.c
Go to the documentation of this file.
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  */
27 #include "platform.h"
28 #include "fs_tree.h"
29 
30 
36 {
41 
45  void *cls;
46 
51 
56 
61 
66 
70  char *emsg;
71 
75  struct GNUNET_FS_Uri *uri;
76 
80  uint64_t size;
81 
85  uint64_t publish_offset;
86 
90  unsigned int current_depth;
91 
95  unsigned int chk_tree_depth;
96 
109 
114  int in_next;
115 };
116 
117 
124 unsigned int
125 GNUNET_FS_compute_depth (uint64_t flen)
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 }
144 
145 
155 uint64_t
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 }
166 
167 
182 static uint16_t
183 GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset)
184 {
185  unsigned int ret;
186  uint64_t mod;
187  uint64_t bds;
188 
189  GNUNET_assert (depth > 0);
190  GNUNET_assert (end_offset > 0);
191  bds = GNUNET_FS_tree_compute_tree_size (depth);
192  mod = end_offset % bds;
193  if (0 == mod)
194  {
195  /* we were triggered at the end of a full block */
196  ret = CHK_PER_INODE;
197  }
198  else
199  {
200  /* we were triggered at the end of the file */
201  bds /= CHK_PER_INODE;
202  ret = mod / bds;
203  if (0 != mod % bds)
204  ret++;
205  }
206  return (uint16_t) (ret * sizeof(struct ContentHashKey));
207 }
208 
209 
221 size_t
222 GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset,
223  unsigned int depth)
224 {
225  size_t ret;
226  uint64_t rsize;
227  uint64_t epos;
228  unsigned int chks;
229 
230  GNUNET_assert (fsize > 0);
231  GNUNET_assert (offset <= fsize);
232  if (depth == 0)
233  {
234  ret = DBLOCK_SIZE;
235  if ((offset + ret > fsize) || (offset + ret < offset))
236  ret = (size_t) (fsize - offset);
237  return ret;
238  }
239 
240  rsize = GNUNET_FS_tree_compute_tree_size (depth - 1);
241  epos = offset + rsize * CHK_PER_INODE;
242  if ((epos < offset) || (epos > fsize))
243  epos = fsize;
244  /* round up when computing #CHKs in our IBlock */
245  chks = (epos - offset + rsize - 1) / rsize;
246  GNUNET_assert (chks <= CHK_PER_INODE);
247  return chks * sizeof(struct ContentHashKey);
248 }
249 
250 
268 struct GNUNET_FS_TreeEncoder *
270  void *cls,
275 {
276  struct GNUNET_FS_TreeEncoder *te;
277 
278  te = GNUNET_new (struct GNUNET_FS_TreeEncoder);
279  te->h = h;
280  te->size = size;
281  te->cls = cls;
282  te->reader = reader;
283  te->proc = proc;
284  te->progress = progress;
285  te->cont = cont;
287  te->chk_tree
289  struct ContentHashKey);
291  "Created tree encoder for file with %llu bytes and depth %u\n",
292  (unsigned long long) size,
293  te->chk_tree_depth);
294  return te;
295 }
296 
297 
309 static unsigned int
310 compute_chk_offset (unsigned int depth, uint64_t end_offset)
311 {
312  uint64_t bds;
313  unsigned int ret;
314 
315  bds = GNUNET_FS_tree_compute_tree_size (depth);
316  if (depth > 0)
317  end_offset--; /* round down since for depth > 0 offset is at the END of the block */
318  ret = end_offset / bds;
319  return ret % CHK_PER_INODE;
320 }
321 
322 
330 void
332 {
333  struct ContentHashKey *mychk;
334  const void *pt_block;
335  uint16_t pt_size;
336  char iob[DBLOCK_SIZE];
337  char enc[DBLOCK_SIZE];
340  unsigned int off;
341 
343  te->in_next = GNUNET_YES;
344  if (te->chk_tree_depth == te->current_depth)
345  {
346  off = CHK_PER_INODE * (te->chk_tree_depth - 1);
347  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
348  GNUNET_h2s (&te->chk_tree[off].query), off);
349  te->uri = GNUNET_new (struct GNUNET_FS_Uri);
350  te->uri->type = GNUNET_FS_URI_CHK;
351  te->uri->data.chk.chk = te->chk_tree[off];
352  te->uri->data.chk.file_length = GNUNET_htonll (te->size);
353  te->in_next = GNUNET_NO;
354  te->cont (te->cls);
355  return;
356  }
357  if (0 == te->current_depth)
358  {
359  /* read DBLOCK */
360  pt_size = GNUNET_MIN (DBLOCK_SIZE, te->size - te->publish_offset);
361  if (pt_size !=
362  te->reader (te->cls, te->publish_offset, pt_size, iob, &te->emsg))
363  {
364  te->in_next = GNUNET_NO;
365  te->cont (te->cls);
366  return;
367  }
368  pt_block = iob;
369  }
370  else
371  {
372  pt_size =
374  te->publish_offset);
375  pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
376  }
379  "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
380  (unsigned long long) te->publish_offset, te->current_depth,
381  (unsigned int) pt_size, (unsigned int) off);
382  mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off];
383  GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
384  GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
385  GNUNET_CRYPTO_symmetric_encrypt (pt_block, pt_size, &sk, &iv, enc);
386  GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
388  "TE calculates query to be `%s', stored at %u\n",
389  GNUNET_h2s (&mychk->query),
390  te->current_depth * CHK_PER_INODE + off);
391  if (NULL != te->proc)
392  te->proc (te->cls, mychk, te->publish_offset, te->current_depth,
393  (0 ==
395  GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size);
396  if (NULL != te->progress)
397  te->progress (te->cls, te->publish_offset, pt_block, pt_size,
398  te->current_depth);
399  if (0 == te->current_depth)
400  {
401  te->publish_offset += pt_size;
402  if ((te->publish_offset == te->size) ||
403  (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
404  te->current_depth++;
405  }
406  else
407  {
408  if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
409  te->current_depth++;
410  else
411  te->current_depth = 0;
412  }
413  te->in_next = GNUNET_NO;
414 }
415 
416 
423 struct GNUNET_FS_Uri *
425 {
426  if (NULL != te->uri)
427  return GNUNET_FS_uri_dup (te->uri);
428  return NULL;
429 }
430 
431 
442 void
444  char **emsg)
445 {
446  if (NULL != te->reader)
447  {
448  (void) te->reader (te->cls, UINT64_MAX, 0, 0, NULL);
449  te->reader = NULL;
450  }
452  if (NULL != te->uri)
454  if (emsg != NULL)
455  *emsg = te->emsg;
456  else
458  GNUNET_free (te->chk_tree);
459  GNUNET_free (te);
460 }
461 
462 
463 /* end of fs_tree.c */
uint64_t size
Overall file size.
Definition: fs_tree.c:80
Context for an ECRS-based file encoder that computes the Merkle-ish-CHK tree.
Definition: fs_tree.c:35
struct ContentHashKey chk
Query and key of the top GNUNET_EC_IBlock.
Definition: fs_api.h:103
GNUNET_FS_DataReader reader
Function to call to receive input data.
Definition: fs_tree.c:60
struct FileIdentifier chk
Information needed to retrieve a file (content-hash-key plus file size).
Definition: fs_api.h:211
struct GNUNET_FS_Uri * uri
Set to the URI (upon successful completion)
Definition: fs_tree.c:75
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:310
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.
Definition: fs_tree.h:116
uint64_t publish_offset
How far are we?
Definition: fs_tree.c:85
content hash key
Definition: fs.h:53
Master context for most FS operations.
Definition: fs_api.h:1068
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.
Definition: fs_tree.h:97
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
void * cls
Closure for all callbacks.
Definition: fs_tree.c:45
unsigned int current_depth
How deep are we? Depth 0 is for the DBLOCKs.
Definition: fs_tree.c:90
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...
Definition: fs_tree.c:331
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
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
#define GNUNET_NO
Definition: gnunet_common.h:78
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
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
struct GNUNET_FS_Uri * GNUNET_FS_tree_encoder_get_uri(struct GNUNET_FS_TreeEncoder *te)
Get the resulting URI from the encoding.
Definition: fs_tree.c:424
struct GNUNET_FS_Uri * GNUNET_FS_uri_dup(const struct GNUNET_FS_Uri *uri)
Duplicate URI.
Definition: fs_uri.c:998
void(* GNUNET_SCHEDULER_TaskCallback)(void *cls)
Signature of the main function of a task.
unsigned int GNUNET_FS_compute_depth(uint64_t flen)
Compute the depth of the CHK tree.
Definition: fs_tree.c:125
GNUNET_FS_TreeBlockProcessor proc
Function to call on encrypted blocks.
Definition: fs_tree.c:50
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
Definition: crypto_hash.c:48
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.
struct GNUNET_FS_Handle * h
Global FS context.
Definition: fs_tree.c:40
GNUNET_SCHEDULER_TaskCallback cont
Function to call once we&#39;re done with processing.
Definition: fs_tree.c:65
struct GNUNET_HashCode query
Hash of the encrypted content, used for querying.
Definition: fs.h:63
#define GNUNET_MIN(a, b)
Definition: gnunet_common.h:80
Inner block in the CHK tree.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
#define CHK_PER_INODE
Pick a multiple of 2 here to achive 8-byte alignment! We also probably want DBlocks to have (roughly)...
Definition: fs_api.h:43
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.
Definition: fs_tree.c:269
void GNUNET_FS_uri_destroy(struct GNUNET_FS_Uri *uri)
Free URI.
Definition: fs_uri.c:678
int in_next
Are we currently in &#39;GNUNET_FS_tree_encoder_next&#39;? Flag used to prevent recursion.
Definition: fs_tree.c:114
struct ContentHashKey * chk_tree
In-memory cache of the current CHK tree.
Definition: fs_tree.c:108
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:222
#define DBLOCK_SIZE
Size of the individual blocks used for file-sharing.
Definition: fs.h:40
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:35
Content-hash-key (simple file).
Definition: fs_api.h:143
enum GNUNET_FS_UriType type
Type of the URI.
Definition: fs_api.h:170
union GNUNET_FS_Uri::@13 data
char * emsg
Set to an error message (if we had an error).
Definition: fs_tree.c:70
struct GNUNET_HashCode key
Hash of the original content, used for encryption.
Definition: fs.h:58
size_t(* GNUNET_FS_DataReader)(void *cls, uint64_t offset, size_t max, void *buf, char **emsg)
Function that provides data.
unsigned int chk_tree_depth
How deep is the tree? Always > 0.
Definition: fs_tree.c:95
A Universal Resource Identifier (URI), opaque.
Definition: fs_api.h:165
uint64_t file_length
Total size of the file in bytes.
Definition: fs_api.h:98
static OpusEncoder * enc
OPUS encoder.
#define GNUNET_log(kind,...)
GNUNET_FS_TreeProgressCallback progress
Function to call with progress information.
Definition: fs_tree.c:55
Data block (leaf) in the CHK tree.
void GNUNET_FS_tree_encoder_finish(struct GNUNET_FS_TreeEncoder *te, char **emsg)
Clean up a tree encoder and return information about possible errors.
Definition: fs_tree.c:443
#define GNUNET_YES
Definition: gnunet_common.h:77
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.
Definition: fs_tree.c:222
#define GNUNET_free(ptr)
Wrapper around free.
Merkle-tree-ish-CHK file encoding for GNUnet.