2 This file is part of GNUnet.
3 (C) 2009 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 2, 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
28 * - decide if this API should be made public (gnunet_fs_service.h)
29 * or remain "internal" (but with exported symbols?)
34 #define DEBUG_TREE GNUNET_NO
37 * Context for an ECRS-based file encoder that computes
38 * the Merkle-ish-CHK tree.
40 struct GNUNET_FS_TreeEncoder
46 struct GNUNET_FS_Handle *h;
49 * Closure for all callbacks.
54 * Function to call on encrypted blocks.
56 GNUNET_FS_TreeBlockProcessor proc;
59 * Function to call with progress information.
61 GNUNET_FS_TreeProgressCallback progress;
64 * Function to call to receive input data.
66 GNUNET_FS_DataReader reader;
69 * Function to call once we're done with processing.
71 GNUNET_SCHEDULER_Task cont;
74 * Set to an error message (if we had an error).
79 * Set to the URI (upon successful completion)
81 struct GNUNET_FS_Uri *uri;
91 uint64_t publish_offset;
96 unsigned int current_depth;
99 * How deep is the tree?
101 unsigned int chk_tree_depth;
104 * In-memory cache of the current CHK tree.
105 * This struct will contain the CHK values
106 * from the root to the currently processed
107 * node in the tree as identified by
108 * "current_depth" and "publish_offset".
109 * The "chktree" will be initially NULL,
110 * then allocated to a sufficient number of
111 * entries for the size of the file and
112 * finally freed once the upload is complete.
114 struct ContentHashKey *chk_tree;
120 * Compute the depth of the CHK tree.
122 * @param flen file length for which to compute the depth
123 * @return depth of the tree
126 GNUNET_FS_compute_depth (uint64_t flen)
128 unsigned int treeDepth;
136 if (fl * CHK_PER_INODE < fl)
138 /* integer overflow, this is a HUGE file... */
141 fl = fl * CHK_PER_INODE;
148 * Initialize a tree encoder. This function will call "proc" and
149 * "progress" on each block in the tree. Once all blocks have been
150 * processed, "cont" will be scheduled. The "reader" will be called
151 * to obtain the (plaintext) blocks for the file. Note that this
152 * function will not actually call "proc". The client must
153 * call "GNUNET_FS_tree_encoder_next" to trigger encryption (and
154 * calling of "proc") for the each block.
156 * @param h the global FS context
157 * @param size overall size of the file to encode
158 * @param cls closure for reader, proc, progress and cont
159 * @param reader function to call to read plaintext data
160 * @param proc function to call on each encrypted block
161 * @param progress function to call with progress information
162 * @param cont function to call when done
164 struct GNUNET_FS_TreeEncoder *
165 GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h,
168 GNUNET_FS_DataReader reader,
169 GNUNET_FS_TreeBlockProcessor proc,
170 GNUNET_FS_TreeProgressCallback progress,
171 GNUNET_SCHEDULER_Task cont)
173 struct GNUNET_FS_TreeEncoder *te;
175 GNUNET_assert (size > 0);
176 te = GNUNET_malloc (sizeof (struct GNUNET_FS_TreeEncoder));
182 te->progress = progress;
184 te->chk_tree_depth = GNUNET_FS_compute_depth (size);
185 te->current_depth = te->chk_tree_depth;
186 te->chk_tree = GNUNET_malloc (te->chk_tree_depth *
188 sizeof (struct ContentHashKey));
194 * Compute the size of the current IBlock.
196 * @param height height of the IBlock in the tree (aka overall
197 * number of tree levels minus depth); 0 == DBlock
198 * @param offset current offset in the overall file
199 * @return size of the corresponding IBlock
202 compute_iblock_size (unsigned int height,
210 GNUNET_assert (height > 0);
211 bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
213 for (i=0;i<height;i++)
214 bds *= CHK_PER_INODE;
218 /* we were triggered at the end of a full block */
223 /* we were triggered at the end of the file */
224 bds /= CHK_PER_INODE;
229 return (uint16_t) (ret * sizeof(struct ContentHashKey));
234 * Compute the offset of the CHK for the
235 * current block in the IBlock above.
237 * @param height height of the IBlock in the tree (aka overall
238 * number of tree levels minus depth); 0 == DBlock
239 * @param offset current offset in the overall file
240 * @return (array of CHKs') offset in the above IBlock
243 compute_chk_offset (unsigned int height,
250 bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i"
252 for (i=0;i<height;i++)
253 bds *= CHK_PER_INODE;
255 offset--; /* round down since for height > 0 offset is at the END of the block */
257 return ret % CHK_PER_INODE;
262 * Encrypt the next block of the file (and call proc and progress
263 * accordingly; or of course "cont" if we have already completed
264 * encoding of the entire file).
266 * @param te tree encoder to use
268 void GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
270 struct ContentHashKey *mychk;
271 const void *pt_block;
273 char iob[DBLOCK_SIZE];
274 char enc[DBLOCK_SIZE];
275 struct GNUNET_CRYPTO_AesSessionKey sk;
276 struct GNUNET_CRYPTO_AesInitializationVector iv;
279 if (te->current_depth == te->chk_tree_depth)
281 pt_size = GNUNET_MIN(DBLOCK_SIZE,
282 te->size - te->publish_offset);
290 GNUNET_SCHEDULER_add_continuation (te->h->sched,
293 GNUNET_SCHEDULER_REASON_TIMEOUT);
300 pt_size = compute_iblock_size (te->chk_tree_depth - te->current_depth,
302 pt_block = &te->chk_tree[te->current_depth *
305 if (0 == te->current_depth)
307 te->uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri));
309 te->uri->data.chk.chk = te->chk_tree[0];
310 te->uri->data.chk.file_length = GNUNET_htonll (te->size);
311 GNUNET_SCHEDULER_add_continuation (te->h->sched,
314 GNUNET_SCHEDULER_REASON_PREREQ_DONE);
317 off = compute_chk_offset (te->chk_tree_depth - te->current_depth,
320 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
321 "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n",
322 (unsigned long long) te->publish_offset,
324 (unsigned int) pt_size,
327 mychk = &te->chk_tree[(te->current_depth-1)*CHK_PER_INODE+off];
328 GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key);
329 GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv);
330 GNUNET_CRYPTO_aes_encrypt (pt_block,
335 GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
337 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
338 "TE calculates query to be `%s'\n",
339 GNUNET_h2s (&mychk->query));
341 if (NULL != te->proc)
345 (te->current_depth == te->chk_tree_depth)
346 ? GNUNET_DATASTORE_BLOCKTYPE_DBLOCK
347 : GNUNET_DATASTORE_BLOCKTYPE_IBLOCK,
350 if (NULL != te->progress)
351 te->progress (te->cls,
356 if (te->current_depth == te->chk_tree_depth)
358 te->publish_offset += pt_size;
359 if ( (te->publish_offset == te->size) ||
360 (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE) ) )
365 if ( (off == CHK_PER_INODE) ||
366 (te->publish_offset == te->size) )
369 te->current_depth = te->chk_tree_depth;
375 * Clean up a tree encoder and return information
376 * about the resulting URI or an error message.
378 * @param te the tree encoder to clean up
379 * @param uri set to the resulting URI (if encoding finished)
380 * @param emsg set to an error message (if an error occured
381 * within the tree encoder; if this function is called
382 * prior to completion and prior to an internal error,
383 * both "*uri" and "*emsg" will be set to NULL).
385 void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te,
386 struct GNUNET_FS_Uri **uri,
393 GNUNET_FS_uri_destroy (te->uri);
397 GNUNET_free_non_null (te->emsg);
398 GNUNET_free (te->chk_tree);
402 /* end of fs_tree.c */