diff options
Diffstat (limited to 'src/fs/fs_tree.c')
-rw-r--r-- | src/fs/fs_tree.c | 463 |
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 | */ | ||
35 | struct 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 | */ | ||
124 | unsigned int | ||
125 | GNUNET_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 | */ | ||
155 | uint64_t | ||
156 | GNUNET_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 | */ | ||
182 | static uint16_t | ||
183 | GNUNET_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 | */ | ||
221 | size_t | ||
222 | GNUNET_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 | */ | ||
268 | struct GNUNET_FS_TreeEncoder * | ||
269 | GNUNET_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 | */ | ||
309 | static unsigned int | ||
310 | compute_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 | */ | ||
330 | void | ||
331 | GNUNET_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 | */ | ||
423 | struct GNUNET_FS_Uri * | ||
424 | GNUNET_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 | */ | ||
442 | void | ||
443 | GNUNET_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 */ | ||