2 This file is part of GNUnet.
3 (C) 2009-2011 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
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
30 #define DEBUG_TREE GNUNET_EXTRA_LOGGING
33 * Context for an ECRS-based file encoder that computes
34 * the Merkle-ish-CHK tree.
36 struct GNUNET_FS_TreeEncoder
42 struct GNUNET_FS_Handle *h;
45 * Closure for all callbacks.
50 * Function to call on encrypted blocks.
52 GNUNET_FS_TreeBlockProcessor proc;
55 * Function to call with progress information.
57 GNUNET_FS_TreeProgressCallback progress;
60 * Function to call to receive input data.
62 GNUNET_FS_DataReader reader;
65 * Function to call once we're done with processing.
67 GNUNET_SCHEDULER_Task cont;
70 * Set to an error message (if we had an error).
75 * Set to the URI (upon successful completion)
77 struct GNUNET_FS_Uri *uri;
87 uint64_t publish_offset;
90 * How deep are we? Depth 0 is for the DBLOCKs.
92 unsigned int current_depth;
95 * How deep is the tree? Always > 0.
97 unsigned int chk_tree_depth;
100 * In-memory cache of the current CHK tree.
101 * This struct will contain the CHK values
102 * from the root to the currently processed
103 * node in the tree as identified by
104 * "current_depth" and "publish_offset".
105 * The "chktree" will be initially NULL,
106 * then allocated to a sufficient number of
107 * entries for the size of the file and
108 * finally freed once the upload is complete.
110 struct ContentHashKey *chk_tree;
113 * Are we currently in 'GNUNET_FS_tree_encoder_next'?
114 * Flag used to prevent recursion.
121 * Compute the depth of the CHK tree.
123 * @param flen file length for which to compute the depth
124 * @return depth of the tree, always > 0. A depth of 1 means only a DBLOCK.
127 GNUNET_FS_compute_depth (uint64_t flen)
129 unsigned int treeDepth;
137 if (fl * CHK_PER_INODE < fl)
139 /* integer overflow, this is a HUGE file... */
142 fl = fl * CHK_PER_INODE;
149 * Calculate how many bytes of payload a block tree of the given
150 * depth MAY correspond to at most (this function ignores the fact that
151 * some blocks will only be present partially due to the total file
152 * size cutting some blocks off at the end).
154 * @param depth depth of the block. depth==0 is a DBLOCK.
155 * @return number of bytes of payload a subtree of this depth may correspond to
158 GNUNET_FS_tree_compute_tree_size (unsigned int depth)
164 for (i = 0; i < depth; i++)
165 rsize *= CHK_PER_INODE;
171 * Compute the size of the current IBLOCK. The encoder is
172 * triggering the calculation of the size of an IBLOCK at the
173 * *end* (hence end_offset) of its construction. The IBLOCK
174 * maybe a full or a partial IBLOCK, and this function is to
175 * calculate how long it should be.
177 * @param depth depth of the IBlock in the tree, 0 would be a DBLOCK,
178 * must be > 0 (this function is for IBLOCKs only!)
179 * @param end_offset current offset in the payload (!) of the overall file,
180 * must be > 0 (since this function is called at the
182 * @return size of the corresponding IBlock
185 GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset)
191 GNUNET_assert (depth > 0);
192 GNUNET_assert (end_offset > 0);
193 bds = GNUNET_FS_tree_compute_tree_size (depth);
194 mod = end_offset % bds;
197 /* we were triggered at the end of a full block */
202 /* we were triggered at the end of the file */
203 bds /= CHK_PER_INODE;
208 return (uint16_t) (ret * sizeof (struct ContentHashKey));
213 * Compute how many bytes of data should be stored in
214 * the specified block.
216 * @param fsize overall file size, must be > 0.
217 * @param offset offset in the original data corresponding
218 * to the beginning of the tree induced by the block;
220 * @param depth depth of the node in the tree, 0 for DBLOCK
221 * @return number of bytes stored in this node
224 GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset,
232 GNUNET_assert (fsize > 0);
233 GNUNET_assert (offset <= fsize);
237 if ((offset + ret > fsize) || (offset + ret < offset))
238 ret = (size_t) (fsize - offset);
242 rsize = GNUNET_FS_tree_compute_tree_size (depth - 1);
243 epos = offset + rsize * CHK_PER_INODE;
244 if ((epos < offset) || (epos > fsize))
246 /* round up when computing #CHKs in our IBlock */
247 chks = (epos - offset + rsize - 1) / rsize;
248 GNUNET_assert (chks <= CHK_PER_INODE);
249 return chks * sizeof (struct ContentHashKey);
254 * Initialize a tree encoder. This function will call "proc" and
255 * "progress" on each block in the tree. Once all blocks have been
256 * processed, "cont" will be scheduled. The "reader" will be called
257 * to obtain the (plaintext) blocks for the file. Note that this
258 * function will not actually call "proc". The client must
259 * call "GNUNET_FS_tree_encoder_next" to trigger encryption (and
260 * calling of "proc") for the each block.
262 * @param h the global FS context
263 * @param size overall size of the file to encode
264 * @param cls closure for reader, proc, progress and cont
265 * @param reader function to call to read plaintext data
266 * @param proc function to call on each encrypted block
267 * @param progress function to call with progress information
268 * @param cont function to call when done
270 struct GNUNET_FS_TreeEncoder *
271 GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, uint64_t size,
272 void *cls, GNUNET_FS_DataReader reader,
273 GNUNET_FS_TreeBlockProcessor proc,
274 GNUNET_FS_TreeProgressCallback progress,
275 GNUNET_SCHEDULER_Task cont)
277 struct GNUNET_FS_TreeEncoder *te;
279 te = GNUNET_malloc (sizeof (struct GNUNET_FS_TreeEncoder));
285 te->progress = progress;
287 te->chk_tree_depth = GNUNET_FS_compute_depth (size);
289 GNUNET_malloc (te->chk_tree_depth * CHK_PER_INODE *
290 sizeof (struct ContentHashKey));
296 * Compute the offset of the CHK for the
297 * current block in the IBlock above.
299 * @param depth depth of the IBlock in the tree (aka overall
300 * number of tree levels minus depth); 0 == DBlock
301 * @param end_offset current offset in the overall file,
302 * at the *beginning* of the block for DBLOCKs (depth==0),
303 * otherwise at the *end* of the block (exclusive)
304 * @return (array of CHKs') offset in the above IBlock
307 compute_chk_offset (unsigned int depth, uint64_t end_offset)
312 bds = GNUNET_FS_tree_compute_tree_size (depth);
314 end_offset--; /* round down since for depth > 0 offset is at the END of the block */
315 ret = end_offset / bds;
316 return ret % CHK_PER_INODE;
321 * Encrypt the next block of the file (and call proc and progress
322 * accordingly; or of course "cont" if we have already completed
323 * encoding of the entire file).
325 * @param te tree encoder to use
328 GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te)
330 struct ContentHashKey *mychk;
331 const void *pt_block;
333 char iob[DBLOCK_SIZE];
334 char enc[DBLOCK_SIZE];
335 struct GNUNET_CRYPTO_AesSessionKey sk;
336 struct GNUNET_CRYPTO_AesInitializationVector iv;
339 GNUNET_assert (GNUNET_NO == te->in_next);
340 te->in_next = GNUNET_YES;
341 if (te->chk_tree_depth == te->current_depth)
343 off = CHK_PER_INODE * (te->chk_tree_depth - 1);
345 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
346 GNUNET_h2s (&te->chk_tree[off].query), off);
348 te->uri = GNUNET_malloc (sizeof (struct GNUNET_FS_Uri));
350 te->uri->data.chk.chk = te->chk_tree[off];
351 te->uri->data.chk.file_length = GNUNET_htonll (te->size);
352 te->in_next = GNUNET_NO;
353 te->cont (te->cls, NULL);
356 if (0 == te->current_depth)
359 pt_size = GNUNET_MIN (DBLOCK_SIZE, te->size - te->publish_offset);
361 te->reader (te->cls, te->publish_offset, pt_size, iob, &te->emsg))
363 GNUNET_SCHEDULER_add_continuation (te->cont, te->cls,
364 GNUNET_SCHEDULER_REASON_TIMEOUT);
365 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);
379 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
380 "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
381 (unsigned long long) te->publish_offset, te->current_depth,
382 (unsigned int) pt_size, (unsigned int) off);
384 mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off];
385 GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
386 GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
387 GNUNET_CRYPTO_aes_encrypt (pt_block, pt_size, &sk, &iv, enc);
388 GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
390 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
391 "TE calculates query to be `%s', stored at %u\n",
392 GNUNET_h2s (&mychk->query),
393 te->current_depth * CHK_PER_INODE + off);
395 if (NULL != te->proc)
396 te->proc (te->cls, mychk, te->publish_offset, te->current_depth,
398 te->current_depth) ? GNUNET_BLOCK_TYPE_FS_DBLOCK :
399 GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size);
400 if (NULL != te->progress)
401 te->progress (te->cls, te->publish_offset, pt_block, pt_size,
403 if (0 == te->current_depth)
405 te->publish_offset += pt_size;
406 if ((te->publish_offset == te->size) ||
407 (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
412 if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
415 te->current_depth = 0;
417 te->in_next = GNUNET_NO;
422 * Clean up a tree encoder and return information
423 * about the resulting URI or an error message.
425 * @param te the tree encoder to clean up
426 * @param uri set to the resulting URI (if encoding finished)
427 * @param emsg set to an error message (if an error occured
428 * within the tree encoder; if this function is called
429 * prior to completion and prior to an internal error,
430 * both "*uri" and "*emsg" will be set to NULL).
433 GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te,
434 struct GNUNET_FS_Uri **uri, char **emsg)
436 GNUNET_assert (GNUNET_NO == te->in_next);
439 else if (NULL != te->uri)
440 GNUNET_FS_uri_destroy (te->uri);
444 GNUNET_free_non_null (te->emsg);
445 GNUNET_free (te->chk_tree);
449 /* end of fs_tree.c */