GNUnet  0.10.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 {
37 
42 
46  void *cls;
47 
52 
57 
62 
67 
71  char *emsg;
72 
76  struct GNUNET_FS_Uri *uri;
77 
81  uint64_t size;
82 
86  uint64_t publish_offset;
87 
91  unsigned int current_depth;
92 
96  unsigned int chk_tree_depth;
97 
110 
115  int in_next;
116 };
117 
118 
125 unsigned int
126 GNUNET_FS_compute_depth (uint64_t flen)
127 {
128  unsigned int treeDepth;
129  uint64_t fl;
130 
131  treeDepth = 1;
132  fl = DBLOCK_SIZE;
133  while (fl < flen)
134  {
135  treeDepth++;
136  if (fl * CHK_PER_INODE < fl)
137  {
138  /* integer overflow, this is a HUGE file... */
139  return treeDepth;
140  }
141  fl = fl * CHK_PER_INODE;
142  }
143  return treeDepth;
144 }
145 
146 
156 uint64_t
158 {
159  uint64_t rsize;
160  unsigned int i;
161 
162  rsize = DBLOCK_SIZE;
163  for (i = 0; i < depth; i++)
164  rsize *= CHK_PER_INODE;
165  return rsize;
166 }
167 
168 
183 static uint16_t
184 GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset)
185 {
186  unsigned int ret;
187  uint64_t mod;
188  uint64_t bds;
189 
190  GNUNET_assert (depth > 0);
191  GNUNET_assert (end_offset > 0);
192  bds = GNUNET_FS_tree_compute_tree_size (depth);
193  mod = end_offset % bds;
194  if (0 == mod)
195  {
196  /* we were triggered at the end of a full block */
197  ret = CHK_PER_INODE;
198  }
199  else
200  {
201  /* we were triggered at the end of the file */
202  bds /= CHK_PER_INODE;
203  ret = mod / bds;
204  if (0 != mod % bds)
205  ret++;
206  }
207  return (uint16_t) (ret * sizeof (struct ContentHashKey));
208 }
209 
210 
222 size_t
223 GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset,
224  unsigned int depth)
225 {
226  size_t ret;
227  uint64_t rsize;
228  uint64_t epos;
229  unsigned int chks;
230 
231  GNUNET_assert (fsize > 0);
232  GNUNET_assert (offset <= fsize);
233  if (depth == 0)
234  {
235  ret = DBLOCK_SIZE;
236  if ((offset + ret > fsize) || (offset + ret < offset))
237  ret = (size_t) (fsize - offset);
238  return ret;
239  }
240 
241  rsize = GNUNET_FS_tree_compute_tree_size (depth - 1);
242  epos = offset + rsize * CHK_PER_INODE;
243  if ((epos < offset) || (epos > fsize))
244  epos = fsize;
245  /* round up when computing #CHKs in our IBlock */
246  chks = (epos - offset + rsize - 1) / rsize;
247  GNUNET_assert (chks <= CHK_PER_INODE);
248  return chks * sizeof (struct ContentHashKey);
249 }
250 
251 
269 struct GNUNET_FS_TreeEncoder *
271  void *cls,
276 {
277  struct GNUNET_FS_TreeEncoder *te;
278 
279  te = GNUNET_new (struct GNUNET_FS_TreeEncoder);
280  te->h = h;
281  te->size = size;
282  te->cls = cls;
283  te->reader = reader;
284  te->proc = proc;
285  te->progress = progress;
286  te->cont = cont;
288  te->chk_tree
290  struct ContentHashKey);
292  "Created tree encoder for file with %llu bytes and depth %u\n",
293  (unsigned long long) size,
294  te->chk_tree_depth);
295  return te;
296 }
297 
298 
310 static unsigned int
311 compute_chk_offset (unsigned int depth, uint64_t end_offset)
312 {
313  uint64_t bds;
314  unsigned int ret;
315 
316  bds = GNUNET_FS_tree_compute_tree_size (depth);
317  if (depth > 0)
318  end_offset--; /* round down since for depth > 0 offset is at the END of the block */
319  ret = end_offset / bds;
320  return ret % CHK_PER_INODE;
321 }
322 
323 
331 void
333 {
334  struct ContentHashKey *mychk;
335  const void *pt_block;
336  uint16_t pt_size;
337  char iob[DBLOCK_SIZE];
338  char enc[DBLOCK_SIZE];
341  unsigned int off;
342 
344  te->in_next = GNUNET_YES;
345  if (te->chk_tree_depth == te->current_depth)
346  {
347  off = CHK_PER_INODE * (te->chk_tree_depth - 1);
348  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
349  GNUNET_h2s (&te->chk_tree[off].query), off);
350  te->uri = GNUNET_new (struct GNUNET_FS_Uri);
351  te->uri->type = GNUNET_FS_URI_CHK;
352  te->uri->data.chk.chk = te->chk_tree[off];
353  te->uri->data.chk.file_length = GNUNET_htonll (te->size);
354  te->in_next = GNUNET_NO;
355  te->cont (te->cls);
356  return;
357  }
358  if (0 == te->current_depth)
359  {
360  /* read DBLOCK */
361  pt_size = GNUNET_MIN (DBLOCK_SIZE, te->size - te->publish_offset);
362  if (pt_size !=
363  te->reader (te->cls, te->publish_offset, pt_size, iob, &te->emsg))
364  {
365  te->in_next = GNUNET_NO;
366  te->cont (te->cls);
367  return;
368  }
369  pt_block = iob;
370  }
371  else
372  {
373  pt_size =
375  te->publish_offset);
376  pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
377  }
380  "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
381  (unsigned long long) te->publish_offset, te->current_depth,
382  (unsigned int) pt_size, (unsigned int) off);
383  mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off];
384  GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
385  GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
386  GNUNET_CRYPTO_symmetric_encrypt (pt_block, pt_size, &sk, &iv, enc);
387  GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
389  "TE calculates query to be `%s', stored at %u\n",
390  GNUNET_h2s (&mychk->query),
391  te->current_depth * CHK_PER_INODE + off);
392  if (NULL != te->proc)
393  te->proc (te->cls, mychk, te->publish_offset, te->current_depth,
394  (0 ==
396  GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size);
397  if (NULL != te->progress)
398  te->progress (te->cls, te->publish_offset, pt_block, pt_size,
399  te->current_depth);
400  if (0 == te->current_depth)
401  {
402  te->publish_offset += pt_size;
403  if ((te->publish_offset == te->size) ||
404  (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
405  te->current_depth++;
406  }
407  else
408  {
409  if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
410  te->current_depth++;
411  else
412  te->current_depth = 0;
413  }
414  te->in_next = GNUNET_NO;
415 }
416 
417 
424 struct GNUNET_FS_Uri *
426 {
427  if (NULL != te->uri)
428  return GNUNET_FS_uri_dup (te->uri);
429  return NULL;
430 }
431 
432 
443 void
445  char **emsg)
446 {
447  if (NULL != te->reader)
448  {
449  (void) te->reader (te->cls, UINT64_MAX, 0, 0, NULL);
450  te->reader = NULL;
451  }
453  if (NULL != te->uri)
455  if (emsg != NULL)
456  *emsg = te->emsg;
457  else
459  GNUNET_free (te->chk_tree);
460  GNUNET_free (te);
461 }
462 
463 /* end of fs_tree.c */
uint64_t size
Overall file size.
Definition: fs_tree.c:81
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:104
GNUNET_FS_DataReader reader
Function to call to receive input data.
Definition: fs_tree.c:61
struct FileIdentifier chk
Information needed to retrieve a file (content-hash-key plus file size).
Definition: fs_api.h:215
struct GNUNET_FS_Uri * uri
Set to the URI (upon successful completion)
Definition: fs_tree.c:76
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:311
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:86
content hash key
Definition: fs.h:53
Master context for most FS operations.
Definition: fs_api.h:1087
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:46
unsigned int current_depth
How deep are we? Depth 0 is for the DBLOCKs.
Definition: fs_tree.c:91
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:332
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:157
#define GNUNET_NO
Definition: gnunet_common.h:81
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 int ret
Final status code.
Definition: gnunet-arm.c:89
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:184
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:425
struct GNUNET_FS_Uri * GNUNET_FS_uri_dup(const struct GNUNET_FS_Uri *uri)
Duplicate URI.
Definition: fs_uri.c:988
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:126
GNUNET_FS_TreeBlockProcessor proc
Function to call on encrypted blocks.
Definition: fs_tree.c:51
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
Definition: crypto_hash.c:44
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:41
GNUNET_SCHEDULER_TaskCallback cont
Function to call once we&#39;re done with processing.
Definition: fs_tree.c:66
struct GNUNET_HashCode query
Hash of the encrypted content, used for querying.
Definition: fs.h:63
union GNUNET_FS_Uri::@16 data
#define GNUNET_MIN(a, b)
Definition: gnunet_common.h:83
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:270
void GNUNET_FS_uri_destroy(struct GNUNET_FS_Uri *uri)
Free URI.
Definition: fs_uri.c:670
int in_next
Are we currently in &#39;GNUNET_FS_tree_encoder_next&#39;? Flag used to prevent recursion.
Definition: fs_tree.c:115
struct ContentHashKey * chk_tree
In-memory cache of the current CHK tree.
Definition: fs_tree.c:109
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:212
#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:146
enum GNUNET_FS_UriType type
Type of the URI.
Definition: fs_api.h:173
char * emsg
Set to an error message (if we had an error).
Definition: fs_tree.c:71
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:96
A Universal Resource Identifier (URI), opaque.
Definition: fs_api.h:168
uint64_t file_length
Total size of the file in bytes.
Definition: fs_api.h:99
static OpusEncoder * enc
OPUS encoder.
#define GNUNET_log(kind,...)
GNUNET_FS_TreeProgressCallback progress
Function to call with progress information.
Definition: fs_tree.c:56
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:444
#define GNUNET_YES
Definition: gnunet_common.h:80
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:223
#define GNUNET_free(ptr)
Wrapper around free.
Merkle-tree-ish-CHK file encoding for GNUnet.