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 
40 
44  void *cls;
45 
50 
55 
60 
65 
69  char *emsg;
70 
74  struct GNUNET_FS_Uri *uri;
75 
79  uint64_t size;
80 
84  uint64_t publish_offset;
85 
89  unsigned int current_depth;
90 
94  unsigned int chk_tree_depth;
95 
108 
113  int in_next;
114 };
115 
116 
123 unsigned int
125 {
126  unsigned int treeDepth;
127  uint64_t fl;
128 
129  treeDepth = 1;
130  fl = DBLOCK_SIZE;
131  while (fl < flen)
132  {
133  treeDepth++;
134  if (fl * CHK_PER_INODE < fl)
135  {
136  /* integer overflow, this is a HUGE file... */
137  return treeDepth;
138  }
139  fl = fl * CHK_PER_INODE;
140  }
141  return treeDepth;
142 }
143 
144 
154 uint64_t
156 {
157  uint64_t rsize;
158  unsigned int i;
159 
160  rsize = DBLOCK_SIZE;
161  for (i = 0; i < depth; i++)
162  rsize *= CHK_PER_INODE;
163  return rsize;
164 }
165 
166 
181 static uint16_t
182 GNUNET_FS_tree_compute_iblock_size(unsigned int depth, uint64_t end_offset)
183 {
184  unsigned int ret;
185  uint64_t mod;
186  uint64_t bds;
187 
188  GNUNET_assert(depth > 0);
189  GNUNET_assert(end_offset > 0);
191  mod = end_offset % bds;
192  if (0 == mod)
193  {
194  /* we were triggered at the end of a full block */
195  ret = CHK_PER_INODE;
196  }
197  else
198  {
199  /* we were triggered at the end of the file */
200  bds /= CHK_PER_INODE;
201  ret = mod / bds;
202  if (0 != mod % bds)
203  ret++;
204  }
205  return (uint16_t)(ret * sizeof(struct ContentHashKey));
206 }
207 
208 
220 size_t
221 GNUNET_FS_tree_calculate_block_size(uint64_t fsize, uint64_t offset,
222  unsigned int depth)
223 {
224  size_t ret;
225  uint64_t rsize;
226  uint64_t epos;
227  unsigned int chks;
228 
229  GNUNET_assert(fsize > 0);
230  GNUNET_assert(offset <= fsize);
231  if (depth == 0)
232  {
233  ret = DBLOCK_SIZE;
234  if ((offset + ret > fsize) || (offset + ret < offset))
235  ret = (size_t)(fsize - offset);
236  return ret;
237  }
238 
239  rsize = GNUNET_FS_tree_compute_tree_size(depth - 1);
240  epos = offset + rsize * CHK_PER_INODE;
241  if ((epos < offset) || (epos > fsize))
242  epos = fsize;
243  /* round up when computing #CHKs in our IBlock */
244  chks = (epos - offset + rsize - 1) / rsize;
245  GNUNET_assert(chks <= CHK_PER_INODE);
246  return chks * sizeof(struct ContentHashKey);
247 }
248 
249 
267 struct GNUNET_FS_TreeEncoder *
269  void *cls,
274 {
275  struct GNUNET_FS_TreeEncoder *te;
276 
277  te = GNUNET_new(struct GNUNET_FS_TreeEncoder);
278  te->h = h;
279  te->size = size;
280  te->cls = cls;
281  te->reader = reader;
282  te->proc = proc;
283  te->progress = progress;
284  te->cont = cont;
286  te->chk_tree
288  struct ContentHashKey);
290  "Created tree encoder for file with %llu bytes and depth %u\n",
291  (unsigned long long)size,
292  te->chk_tree_depth);
293  return te;
294 }
295 
296 
308 static unsigned int
309 compute_chk_offset(unsigned int depth, uint64_t end_offset)
310 {
311  uint64_t bds;
312  unsigned int ret;
313 
315  if (depth > 0)
316  end_offset--; /* round down since for depth > 0 offset is at the END of the block */
317  ret = end_offset / bds;
318  return ret % CHK_PER_INODE;
319 }
320 
321 
329 void
331 {
332  struct ContentHashKey *mychk;
333  const void *pt_block;
334  uint16_t pt_size;
335  char iob[DBLOCK_SIZE];
336  char enc[DBLOCK_SIZE];
339  unsigned int off;
340 
342  te->in_next = GNUNET_YES;
343  if (te->chk_tree_depth == te->current_depth)
344  {
345  off = CHK_PER_INODE * (te->chk_tree_depth - 1);
346  GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
347  GNUNET_h2s(&te->chk_tree[off].query), off);
348  te->uri = GNUNET_new(struct GNUNET_FS_Uri);
349  te->uri->type = GNUNET_FS_URI_CHK;
350  te->uri->data.chk.chk = te->chk_tree[off];
352  te->in_next = GNUNET_NO;
353  te->cont(te->cls);
354  return;
355  }
356  if (0 == te->current_depth)
357  {
358  /* read DBLOCK */
359  pt_size = GNUNET_MIN(DBLOCK_SIZE, te->size - te->publish_offset);
360  if (pt_size !=
361  te->reader(te->cls, te->publish_offset, pt_size, iob, &te->emsg))
362  {
363  te->in_next = GNUNET_NO;
364  te->cont(te->cls);
365  return;
366  }
367  pt_block = iob;
368  }
369  else
370  {
371  pt_size =
373  te->publish_offset);
374  pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
375  }
378  "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
379  (unsigned long long)te->publish_offset, te->current_depth,
380  (unsigned int)pt_size, (unsigned int)off);
381  mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off];
382  GNUNET_CRYPTO_hash(pt_block, pt_size, &mychk->key);
383  GNUNET_CRYPTO_hash_to_aes_key(&mychk->key, &sk, &iv);
384  GNUNET_CRYPTO_symmetric_encrypt(pt_block, pt_size, &sk, &iv, enc);
385  GNUNET_CRYPTO_hash(enc, pt_size, &mychk->query);
387  "TE calculates query to be `%s', stored at %u\n",
388  GNUNET_h2s(&mychk->query),
389  te->current_depth * CHK_PER_INODE + off);
390  if (NULL != te->proc)
391  te->proc(te->cls, mychk, te->publish_offset, te->current_depth,
392  (0 ==
394  GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size);
395  if (NULL != te->progress)
396  te->progress(te->cls, te->publish_offset, pt_block, pt_size,
397  te->current_depth);
398  if (0 == te->current_depth)
399  {
400  te->publish_offset += pt_size;
401  if ((te->publish_offset == te->size) ||
402  (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
403  te->current_depth++;
404  }
405  else
406  {
407  if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
408  te->current_depth++;
409  else
410  te->current_depth = 0;
411  }
412  te->in_next = GNUNET_NO;
413 }
414 
415 
422 struct GNUNET_FS_Uri *
424 {
425  if (NULL != te->uri)
426  return GNUNET_FS_uri_dup(te->uri);
427  return NULL;
428 }
429 
430 
441 void
443  char **emsg)
444 {
445  if (NULL != te->reader)
446  {
447  (void)te->reader(te->cls, UINT64_MAX, 0, 0, NULL);
448  te->reader = NULL;
449  }
451  if (NULL != te->uri)
453  if (emsg != NULL)
454  *emsg = te->emsg;
455  else
457  GNUNET_free(te->chk_tree);
458  GNUNET_free(te);
459 }
460 
461 /* end of fs_tree.c */
uint64_t size
Overall file size.
Definition: fs_tree.c:79
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:102
GNUNET_FS_DataReader reader
Function to call to receive input data.
Definition: fs_tree.c:59
struct FileIdentifier chk
Information needed to retrieve a file (content-hash-key plus file size).
Definition: fs_api.h:204
struct GNUNET_FS_Uri * uri
Set to the URI (upon successful completion)
Definition: fs_tree.c:74
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:309
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:84
content hash key
Definition: fs.h:53
Master context for most FS operations.
Definition: fs_api.h:1056
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:44
unsigned int current_depth
How deep are we? Depth 0 is for the DBLOCKs.
Definition: fs_tree.c:89
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:330
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:155
#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 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:182
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:423
struct GNUNET_FS_Uri * GNUNET_FS_uri_dup(const struct GNUNET_FS_Uri *uri)
Duplicate URI.
Definition: fs_uri.c:995
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:124
GNUNET_FS_TreeBlockProcessor proc
Function to call on encrypted blocks.
Definition: fs_tree.c:49
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:39
GNUNET_SCHEDULER_TaskCallback cont
Function to call once we&#39;re done with processing.
Definition: fs_tree.c:64
struct GNUNET_HashCode query
Hash of the encrypted content, used for querying.
Definition: fs.h:62
union GNUNET_FS_Uri::@16 data
#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:268
void GNUNET_FS_uri_destroy(struct GNUNET_FS_Uri *uri)
Free URI.
Definition: fs_uri.c:675
int in_next
Are we currently in &#39;GNUNET_FS_tree_encoder_next&#39;? Flag used to prevent recursion.
Definition: fs_tree.c:113
struct ContentHashKey * chk_tree
In-memory cache of the current CHK tree.
Definition: fs_tree.c:107
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:140
enum GNUNET_FS_UriType type
Type of the URI.
Definition: fs_api.h:166
char * emsg
Set to an error message (if we had an error).
Definition: fs_tree.c:69
struct GNUNET_HashCode key
Hash of the original content, used for encryption.
Definition: fs.h:57
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:94
A Universal Resource Identifier (URI), opaque.
Definition: fs_api.h:162
uint64_t file_length
Total size of the file in bytes.
Definition: fs_api.h:97
static OpusEncoder * enc
OPUS encoder.
#define GNUNET_log(kind,...)
GNUNET_FS_TreeProgressCallback progress
Function to call with progress information.
Definition: fs_tree.c:54
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:442
#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:221
#define GNUNET_free(ptr)
Wrapper around free.
Merkle-tree-ish-CHK file encoding for GNUnet.