GNUnet  0.17.6
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 
210 size_t
211 GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset,
212  unsigned int depth)
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 }
238 
239 
257 struct GNUNET_FS_TreeEncoder *
259  void *cls,
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 }
285 
286 
298 static unsigned int
299 compute_chk_offset (unsigned int depth, uint64_t end_offset)
300 {
301  uint64_t bds;
302  unsigned int ret;
303 
304  bds = GNUNET_FS_tree_compute_tree_size (depth);
305  if (depth > 0)
306  end_offset--; /* round down since for depth > 0 offset is at the END of the block */
307  ret = end_offset / bds;
308  return ret % CHK_PER_INODE;
309 }
310 
311 
319 void
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 }
404 
405 
412 struct GNUNET_FS_Uri *
414 {
415  if (NULL != te->uri)
416  return GNUNET_FS_uri_dup (te->uri);
417  return NULL;
418 }
419 
420 
431 void
433  char **emsg)
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 }
450 
451 
452 /* end of fs_tree.c */
#define DBLOCK_SIZE
Size of the individual blocks used for file-sharing.
Definition: fs.h:40
@ GNUNET_FS_URI_CHK
Content-hash-key (simple file).
Definition: fs_api.h:143
#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:43
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:320
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:413
unsigned int GNUNET_FS_compute_depth(uint64_t flen)
Compute the depth of the CHK tree.
Definition: fs_tree.c:125
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:432
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
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:258
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
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:211
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
Merkle-tree-ish-CHK file encoding for GNUnet.
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
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
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
static struct GNUNET_ARM_Handle * h
Connection with ARM.
Definition: gnunet-arm.c:99
static OpusEncoder * enc
OPUS encoder.
@ GNUNET_BLOCK_TYPE_FS_DBLOCK
Data block (leaf) in the CHK tree.
@ GNUNET_BLOCK_TYPE_FS_IBLOCK
Inner block in the CHK tree.
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.
size_t(* GNUNET_FS_DataReader)(void *cls, uint64_t offset, size_t max, void *buf, char **emsg)
Function that provides data.
void GNUNET_FS_uri_destroy(struct GNUNET_FS_Uri *uri)
Free URI.
Definition: fs_uri.c:684
struct GNUNET_FS_Uri * GNUNET_FS_uri_dup(const struct GNUNET_FS_Uri *uri)
Duplicate URI.
Definition: fs_uri.c:1003
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:151
#define GNUNET_log(kind,...)
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:36
#define GNUNET_MIN(a, b)
@ GNUNET_YES
@ GNUNET_NO
Definition: gnunet_common.h:98
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
@ 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.
#define GNUNET_free(ptr)
Wrapper around free.
void(* GNUNET_SCHEDULER_TaskCallback)(void *cls)
Signature of the main function of a task.
static unsigned int size
Size of the "table".
Definition: peer.c:67
content hash key
Definition: fs.h:54
struct GNUNET_HashCode key
Hash of the original content, used for encryption.
Definition: fs.h:58
struct GNUNET_HashCode query
Hash of the encrypted content, used for querying.
Definition: fs.h:63
struct ContentHashKey chk
Query and key of the top GNUNET_EC_IBlock.
Definition: fs_api.h:103
uint64_t file_length
Total size of the file in bytes.
Definition: fs_api.h:98
Master context for most FS operations.
Definition: fs_api.h:1069
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
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
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
int in_next
Are we currently in 'GNUNET_FS_tree_encoder_next'? Flag used to prevent recursion.
Definition: fs_tree.c:114
struct GNUNET_FS_Handle * h
Global FS context.
Definition: fs_tree.c:40
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:166
union GNUNET_FS_Uri::@13 data
enum GNUNET_FS_UriType type
Type of the URI.
Definition: fs_api.h:170
struct FileIdentifier chk
Information needed to retrieve a file (content-hash-key plus file size).
Definition: fs_api.h:211