2 This file is part of GNUnet.
3 Copyright (C) 2009-2011 GNUnet e.V.
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.
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.
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/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
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
32 * Context for an ECRS-based file encoder that computes
33 * the Merkle-ish-CHK tree.
35 struct GNUNET_FS_TreeEncoder
40 struct GNUNET_FS_Handle *h;
43 * Closure for all callbacks.
48 * Function to call on encrypted blocks.
50 GNUNET_FS_TreeBlockProcessor proc;
53 * Function to call with progress information.
55 GNUNET_FS_TreeProgressCallback progress;
58 * Function to call to receive input data.
60 GNUNET_FS_DataReader reader;
63 * Function to call once we're done with processing.
65 GNUNET_SCHEDULER_TaskCallback cont;
68 * Set to an error message (if we had an error).
73 * Set to the URI (upon successful completion)
75 struct GNUNET_FS_Uri *uri;
85 uint64_t publish_offset;
88 * How deep are we? Depth 0 is for the DBLOCKs.
90 unsigned int current_depth;
93 * How deep is the tree? Always > 0.
95 unsigned int chk_tree_depth;
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.
108 struct ContentHashKey *chk_tree;
111 * Are we currently in 'GNUNET_FS_tree_encoder_next'?
112 * Flag used to prevent recursion.
119 * Compute the depth of the CHK tree.
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.
125 GNUNET_FS_compute_depth (uint64_t flen)
127 unsigned int treeDepth;
135 if (fl * CHK_PER_INODE < fl)
137 /* integer overflow, this is a HUGE file... */
140 fl = fl * CHK_PER_INODE;
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).
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
156 GNUNET_FS_tree_compute_tree_size (unsigned int depth)
162 for (i = 0; i < depth; i++)
163 rsize *= CHK_PER_INODE;
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.
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
180 * @return size of the corresponding IBlock
183 GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset)
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;
195 /* we were triggered at the end of a full block */
200 /* we were triggered at the end of the file */
201 bds /= CHK_PER_INODE;
206 return (uint16_t) (ret * sizeof(struct ContentHashKey));
211 * Compute how many bytes of data should be stored in
212 * the specified block.
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;
218 * @param depth depth of the node in the tree, 0 for DBLOCK
219 * @return number of bytes stored in this node
222 GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset,
230 GNUNET_assert (fsize > 0);
231 GNUNET_assert (offset <= fsize);
235 if ((offset + ret > fsize) || (offset + ret < offset))
236 ret = (size_t) (fsize - offset);
240 rsize = GNUNET_FS_tree_compute_tree_size (depth - 1);
241 epos = offset + rsize * CHK_PER_INODE;
242 if ((epos < offset) || (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);
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.
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
268 struct GNUNET_FS_TreeEncoder *
269 GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, uint64_t size,
271 GNUNET_FS_DataReader reader,
272 GNUNET_FS_TreeBlockProcessor proc,
273 GNUNET_FS_TreeProgressCallback progress,
274 GNUNET_SCHEDULER_TaskCallback cont)
276 struct GNUNET_FS_TreeEncoder *te;
278 te = GNUNET_new (struct GNUNET_FS_TreeEncoder);
284 te->progress = progress;
286 te->chk_tree_depth = GNUNET_FS_compute_depth (size);
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,
299 * Compute the offset of the CHK for the
300 * current block in the IBlock above.
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
310 compute_chk_offset (unsigned int depth, uint64_t end_offset)
315 bds = GNUNET_FS_tree_compute_tree_size (depth);
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;
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).
328 * @param te tree encoder to use
331 GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te)
333 struct ContentHashKey *mychk;
334 const void *pt_block;
336 char iob[DBLOCK_SIZE];
337 char enc[DBLOCK_SIZE];
338 struct GNUNET_CRYPTO_SymmetricSessionKey sk;
339 struct GNUNET_CRYPTO_SymmetricInitializationVector iv;
342 GNUNET_assert (GNUNET_NO == te->in_next);
343 te->in_next = GNUNET_YES;
344 if (te->chk_tree_depth == te->current_depth)
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;
357 if (0 == te->current_depth)
360 pt_size = GNUNET_MIN (DBLOCK_SIZE, te->size - te->publish_offset);
362 te->reader (te->cls, te->publish_offset, pt_size, iob, &te->emsg))
364 te->in_next = GNUNET_NO;
373 GNUNET_FS_tree_compute_iblock_size (te->current_depth,
375 pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
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,
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,
399 if (0 == te->current_depth)
401 te->publish_offset += pt_size;
402 if ((te->publish_offset == te->size) ||
403 (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
408 if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
411 te->current_depth = 0;
413 te->in_next = GNUNET_NO;
418 * Get the resulting URI from the encoding.
420 * @param te the tree encoder to clean up
421 * @return uri set to the resulting URI (if encoding finished), NULL otherwise
423 struct GNUNET_FS_Uri *
424 GNUNET_FS_tree_encoder_get_uri (struct GNUNET_FS_TreeEncoder *te)
427 return GNUNET_FS_uri_dup (te->uri);
433 * Clean up a tree encoder and return information
434 * about possible errors.
436 * @param te the tree encoder to clean up
437 * @param emsg set to an error message (if an error occured
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).
443 GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te,
446 if (NULL != te->reader)
448 (void) te->reader (te->cls, UINT64_MAX, 0, 0, NULL);
451 GNUNET_assert (GNUNET_NO == te->in_next);
453 GNUNET_FS_uri_destroy (te->uri);
457 GNUNET_free_non_null (te->emsg);
458 GNUNET_free (te->chk_tree);
463 /* end of fs_tree.c */