GNUnet 0.21.1
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
76
80 uint64_t size;
81
86
90 unsigned int current_depth;
91
95 unsigned int chk_tree_depth;
96
109
115};
116
117
124unsigned int
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
155uint64_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
182static uint16_t
183GNUNET_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);
192 mod = end_offset % bds;
193 if (0 == mod)
194 {
195 /* we were triggered at the end of a full block */
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
210size_t
211GNUNET_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 {
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;
236 return chks * sizeof(struct ContentHashKey);
237}
238
239
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
298static unsigned int
299compute_chk_offset (unsigned int depth, uint64_t end_offset)
300{
301 uint64_t bds;
302 unsigned int ret;
303
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
319void
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);
340 te->uri->data.chk.chk = te->chk_tree[off];
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 ==
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) ||
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
412struct GNUNET_FS_Uri *
414{
415 if (NULL != te->uri)
416 return GNUNET_FS_uri_dup (te->uri);
417 return NULL;
418}
419
420
431void
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:41
@ GNUNET_FS_URI_CHK
Content-hash-key (simple file).
Definition: fs_api.h:144
#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
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
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
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
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
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
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 struct GNUNET_ARM_Handle * h
Connection with ARM.
Definition: gnunet-arm.c:99
static int ret
Final status code.
Definition: gnunet-arm.c:94
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.
struct GNUNET_FS_Uri * GNUNET_FS_uri_dup(const struct GNUNET_FS_Uri *uri)
Duplicate URI.
Definition: fs_uri.c:987
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:677
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
#define GNUNET_log(kind,...)
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
#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:68
@ GNUNET_BLOCK_TYPE_FS_DBLOCK
Data block (leaf) in the CHK tree.
@ GNUNET_BLOCK_TYPE_FS_IBLOCK
Inner block in the CHK tree.
content hash key
Definition: fs.h:55
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
Master context for most FS operations.
Definition: fs_api.h:1070
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:167
union GNUNET_FS_Uri::@49 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