aboutsummaryrefslogtreecommitdiff
path: root/src/fs/fs_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/fs/fs_tree.c')
-rw-r--r--src/fs/fs_tree.c463
1 files changed, 0 insertions, 463 deletions
diff --git a/src/fs/fs_tree.c b/src/fs/fs_tree.c
deleted file mode 100644
index 4d49809f8..000000000
--- a/src/fs/fs_tree.c
+++ /dev/null
@@ -1,463 +0,0 @@
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 */
20/**
21 * @file fs/fs_tree.c
22 * @brief Merkle-tree-ish-CHK file encoding for GNUnet
23 * @see http://gnunet.org/encoding.php3
24 * @author Krista Bennett
25 * @author Christian Grothoff
26 */
27#include "platform.h"
28#include "fs_tree.h"
29
30
31/**
32 * Context for an ECRS-based file encoder that computes
33 * the Merkle-ish-CHK tree.
34 */
35struct GNUNET_FS_TreeEncoder
36{
37 /**
38 * Global FS context.
39 */
40 struct GNUNET_FS_Handle *h;
41
42 /**
43 * Closure for all callbacks.
44 */
45 void *cls;
46
47 /**
48 * Function to call on encrypted blocks.
49 */
50 GNUNET_FS_TreeBlockProcessor proc;
51
52 /**
53 * Function to call with progress information.
54 */
55 GNUNET_FS_TreeProgressCallback progress;
56
57 /**
58 * Function to call to receive input data.
59 */
60 GNUNET_FS_DataReader reader;
61
62 /**
63 * Function to call once we're done with processing.
64 */
65 GNUNET_SCHEDULER_TaskCallback cont;
66
67 /**
68 * Set to an error message (if we had an error).
69 */
70 char *emsg;
71
72 /**
73 * Set to the URI (upon successful completion)
74 */
75 struct GNUNET_FS_Uri *uri;
76
77 /**
78 * Overall file size.
79 */
80 uint64_t size;
81
82 /**
83 * How far are we?
84 */
85 uint64_t publish_offset;
86
87 /**
88 * How deep are we? Depth 0 is for the DBLOCKs.
89 */
90 unsigned int current_depth;
91
92 /**
93 * How deep is the tree? Always > 0.
94 */
95 unsigned int chk_tree_depth;
96
97 /**
98 * In-memory cache of the current CHK tree.
99 * This struct will contain the CHK values
100 * from the root to the currently processed
101 * node in the tree as identified by
102 * "current_depth" and "publish_offset".
103 * The "chktree" will be initially NULL,
104 * then allocated to a sufficient number of
105 * entries for the size of the file and
106 * finally freed once the upload is complete.
107 */
108 struct ContentHashKey *chk_tree;
109
110 /**
111 * Are we currently in 'GNUNET_FS_tree_encoder_next'?
112 * Flag used to prevent recursion.
113 */
114 int in_next;
115};
116
117
118/**
119 * Compute the depth of the CHK tree.
120 *
121 * @param flen file length for which to compute the depth
122 * @return depth of the tree, always > 0. A depth of 1 means only a DBLOCK.
123 */
124unsigned int
125GNUNET_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
146/**
147 * Calculate how many bytes of payload a block tree of the given
148 * depth MAY correspond to at most (this function ignores the fact that
149 * some blocks will only be present partially due to the total file
150 * size cutting some blocks off at the end).
151 *
152 * @param depth depth of the block. depth==0 is a DBLOCK.
153 * @return number of bytes of payload a subtree of this depth may correspond to
154 */
155uint64_t
156GNUNET_FS_tree_compute_tree_size (unsigned int depth)
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
168/**
169 * Compute the size of the current IBLOCK. The encoder is
170 * triggering the calculation of the size of an IBLOCK at the
171 * *end* (hence end_offset) of its construction. The IBLOCK
172 * maybe a full or a partial IBLOCK, and this function is to
173 * calculate how long it should be.
174 *
175 * @param depth depth of the IBlock in the tree, 0 would be a DBLOCK,
176 * must be > 0 (this function is for IBLOCKs only!)
177 * @param end_offset current offset in the payload (!) of the overall file,
178 * must be > 0 (since this function is called at the
179 * end of a block).
180 * @return size of the corresponding IBlock
181 */
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);
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/**
211 * Compute how many bytes of data should be stored in
212 * the specified block.
213 *
214 * @param fsize overall file size, must be > 0.
215 * @param offset offset in the original data corresponding
216 * to the beginning of the tree induced by the block;
217 * must be <= fsize
218 * @param depth depth of the node in the tree, 0 for DBLOCK
219 * @return number of bytes stored in this node
220 */
221size_t
222GNUNET_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
251/**
252 * Initialize a tree encoder. This function will call @a proc and
253 * "progress" on each block in the tree. Once all blocks have been
254 * processed, "cont" will be scheduled. The @a reader will be called
255 * to obtain the (plaintext) blocks for the file. Note that this
256 * function will not actually call @a proc. The client must
257 * call #GNUNET_FS_tree_encoder_next to trigger encryption (and
258 * calling of @a proc) for the each block.
259 *
260 * @param h the global FS context
261 * @param size overall size of the file to encode
262 * @param cls closure for reader, proc, progress and cont
263 * @param reader function to call to read plaintext data
264 * @param proc function to call on each encrypted block
265 * @param progress function to call with progress information
266 * @param cont function to call when done
267 */
268struct GNUNET_FS_TreeEncoder *
269GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, uint64_t size,
270 void *cls,
271 GNUNET_FS_DataReader reader,
272 GNUNET_FS_TreeBlockProcessor proc,
273 GNUNET_FS_TreeProgressCallback progress,
274 GNUNET_SCHEDULER_TaskCallback cont)
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;
286 te->chk_tree_depth = GNUNET_FS_compute_depth (size);
287 te->chk_tree
288 = GNUNET_new_array (te->chk_tree_depth * CHK_PER_INODE,
289 struct ContentHashKey);
290 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
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
298/**
299 * Compute the offset of the CHK for the
300 * current block in the IBlock above.
301 *
302 * @param depth depth of the IBlock in the tree (aka overall
303 * number of tree levels minus depth); 0 == DBlock
304 * @param end_offset current offset in the overall file,
305 * at the *beginning* of the block for DBLOCKs (depth==0),
306 * otherwise at the *end* of the block (exclusive)
307 * @return (array of CHKs') offset in the above IBlock
308 */
309static unsigned int
310compute_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
323/**
324 * Encrypt the next block of the file (and call proc and progress
325 * accordingly; or of course "cont" if we have already completed
326 * encoding of the entire file).
327 *
328 * @param te tree encoder to use
329 */
330void
331GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te)
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];
338 struct GNUNET_CRYPTO_SymmetricSessionKey sk;
339 struct GNUNET_CRYPTO_SymmetricInitializationVector iv;
340 unsigned int off;
341
342 GNUNET_assert (GNUNET_NO == te->in_next);
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 =
373 GNUNET_FS_tree_compute_iblock_size (te->current_depth,
374 te->publish_offset);
375 pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
376 }
377 off = compute_chk_offset (te->current_depth, te->publish_offset);
378 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
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);
387 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
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 ==
394 te->current_depth) ? GNUNET_BLOCK_TYPE_FS_DBLOCK :
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
417/**
418 * Get the resulting URI from the encoding.
419 *
420 * @param te the tree encoder to clean up
421 * @return uri set to the resulting URI (if encoding finished), NULL otherwise
422 */
423struct GNUNET_FS_Uri *
424GNUNET_FS_tree_encoder_get_uri (struct GNUNET_FS_TreeEncoder *te)
425{
426 if (NULL != te->uri)
427 return GNUNET_FS_uri_dup (te->uri);
428 return NULL;
429}
430
431
432/**
433 * Clean up a tree encoder and return information
434 * about possible errors.
435 *
436 * @param te the tree encoder to clean up
437 * @param emsg set to an error message (if an error occurred
438 * within the tree encoder; if this function is called
439 * prior to completion and prior to an internal error,
440 * both "*emsg" will be set to NULL).
441 */
442void
443GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te,
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 }
451 GNUNET_assert (GNUNET_NO == te->in_next);
452 if (NULL != te->uri)
453 GNUNET_FS_uri_destroy (te->uri);
454 if (emsg != NULL)
455 *emsg = te->emsg;
456 else
457 GNUNET_free (te->emsg);
458 GNUNET_free (te->chk_tree);
459 GNUNET_free (te);
460}
461
462
463/* end of fs_tree.c */