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.c264
1 files changed, 131 insertions, 133 deletions
diff --git a/src/fs/fs_tree.c b/src/fs/fs_tree.c
index 203de3c7e..5d486a8c9 100644
--- a/src/fs/fs_tree.c
+++ b/src/fs/fs_tree.c
@@ -11,12 +11,12 @@
11 WITHOUT ANY WARRANTY; without even the implied warranty of 11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details. 13 Affero General Public License for more details.
14 14
15 You should have received a copy of the GNU Affero General Public License 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/>. 16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17 17
18 SPDX-License-Identifier: AGPL3.0-or-later 18 SPDX-License-Identifier: AGPL3.0-or-later
19*/ 19 */
20/** 20/**
21 * @file fs/fs_tree.c 21 * @file fs/fs_tree.c
22 * @brief Merkle-tree-ish-CHK file encoding for GNUnet 22 * @brief Merkle-tree-ish-CHK file encoding for GNUnet
@@ -32,9 +32,7 @@
32 * Context for an ECRS-based file encoder that computes 32 * Context for an ECRS-based file encoder that computes
33 * the Merkle-ish-CHK tree. 33 * the Merkle-ish-CHK tree.
34 */ 34 */
35struct GNUNET_FS_TreeEncoder 35struct GNUNET_FS_TreeEncoder {
36{
37
38 /** 36 /**
39 * Global FS context. 37 * Global FS context.
40 */ 38 */
@@ -123,7 +121,7 @@ struct GNUNET_FS_TreeEncoder
123 * @return depth of the tree, always > 0. A depth of 1 means only a DBLOCK. 121 * @return depth of the tree, always > 0. A depth of 1 means only a DBLOCK.
124 */ 122 */
125unsigned int 123unsigned int
126GNUNET_FS_compute_depth (uint64_t flen) 124GNUNET_FS_compute_depth(uint64_t flen)
127{ 125{
128 unsigned int treeDepth; 126 unsigned int treeDepth;
129 uint64_t fl; 127 uint64_t fl;
@@ -131,15 +129,15 @@ GNUNET_FS_compute_depth (uint64_t flen)
131 treeDepth = 1; 129 treeDepth = 1;
132 fl = DBLOCK_SIZE; 130 fl = DBLOCK_SIZE;
133 while (fl < flen) 131 while (fl < flen)
134 {
135 treeDepth++;
136 if (fl * CHK_PER_INODE < fl)
137 { 132 {
138 /* integer overflow, this is a HUGE file... */ 133 treeDepth++;
139 return treeDepth; 134 if (fl * CHK_PER_INODE < fl)
135 {
136 /* integer overflow, this is a HUGE file... */
137 return treeDepth;
138 }
139 fl = fl * CHK_PER_INODE;
140 } 140 }
141 fl = fl * CHK_PER_INODE;
142 }
143 return treeDepth; 141 return treeDepth;
144} 142}
145 143
@@ -154,7 +152,7 @@ GNUNET_FS_compute_depth (uint64_t flen)
154 * @return number of bytes of payload a subtree of this depth may correspond to 152 * @return number of bytes of payload a subtree of this depth may correspond to
155 */ 153 */
156uint64_t 154uint64_t
157GNUNET_FS_tree_compute_tree_size (unsigned int depth) 155GNUNET_FS_tree_compute_tree_size(unsigned int depth)
158{ 156{
159 uint64_t rsize; 157 uint64_t rsize;
160 unsigned int i; 158 unsigned int i;
@@ -181,30 +179,30 @@ GNUNET_FS_tree_compute_tree_size (unsigned int depth)
181 * @return size of the corresponding IBlock 179 * @return size of the corresponding IBlock
182 */ 180 */
183static uint16_t 181static uint16_t
184GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset) 182GNUNET_FS_tree_compute_iblock_size(unsigned int depth, uint64_t end_offset)
185{ 183{
186 unsigned int ret; 184 unsigned int ret;
187 uint64_t mod; 185 uint64_t mod;
188 uint64_t bds; 186 uint64_t bds;
189 187
190 GNUNET_assert (depth > 0); 188 GNUNET_assert(depth > 0);
191 GNUNET_assert (end_offset > 0); 189 GNUNET_assert(end_offset > 0);
192 bds = GNUNET_FS_tree_compute_tree_size (depth); 190 bds = GNUNET_FS_tree_compute_tree_size(depth);
193 mod = end_offset % bds; 191 mod = end_offset % bds;
194 if (0 == mod) 192 if (0 == mod)
195 { 193 {
196 /* we were triggered at the end of a full block */ 194 /* we were triggered at the end of a full block */
197 ret = CHK_PER_INODE; 195 ret = CHK_PER_INODE;
198 } 196 }
199 else 197 else
200 { 198 {
201 /* we were triggered at the end of the file */ 199 /* we were triggered at the end of the file */
202 bds /= CHK_PER_INODE; 200 bds /= CHK_PER_INODE;
203 ret = mod / bds; 201 ret = mod / bds;
204 if (0 != mod % bds) 202 if (0 != mod % bds)
205 ret++; 203 ret++;
206 } 204 }
207 return (uint16_t) (ret * sizeof (struct ContentHashKey)); 205 return (uint16_t)(ret * sizeof(struct ContentHashKey));
208} 206}
209 207
210 208
@@ -220,32 +218,32 @@ GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset)
220 * @return number of bytes stored in this node 218 * @return number of bytes stored in this node
221 */ 219 */
222size_t 220size_t
223GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset, 221GNUNET_FS_tree_calculate_block_size(uint64_t fsize, uint64_t offset,
224 unsigned int depth) 222 unsigned int depth)
225{ 223{
226 size_t ret; 224 size_t ret;
227 uint64_t rsize; 225 uint64_t rsize;
228 uint64_t epos; 226 uint64_t epos;
229 unsigned int chks; 227 unsigned int chks;
230 228
231 GNUNET_assert (fsize > 0); 229 GNUNET_assert(fsize > 0);
232 GNUNET_assert (offset <= fsize); 230 GNUNET_assert(offset <= fsize);
233 if (depth == 0) 231 if (depth == 0)
234 { 232 {
235 ret = DBLOCK_SIZE; 233 ret = DBLOCK_SIZE;
236 if ((offset + ret > fsize) || (offset + ret < offset)) 234 if ((offset + ret > fsize) || (offset + ret < offset))
237 ret = (size_t) (fsize - offset); 235 ret = (size_t)(fsize - offset);
238 return ret; 236 return ret;
239 } 237 }
240 238
241 rsize = GNUNET_FS_tree_compute_tree_size (depth - 1); 239 rsize = GNUNET_FS_tree_compute_tree_size(depth - 1);
242 epos = offset + rsize * CHK_PER_INODE; 240 epos = offset + rsize * CHK_PER_INODE;
243 if ((epos < offset) || (epos > fsize)) 241 if ((epos < offset) || (epos > fsize))
244 epos = fsize; 242 epos = fsize;
245 /* round up when computing #CHKs in our IBlock */ 243 /* round up when computing #CHKs in our IBlock */
246 chks = (epos - offset + rsize - 1) / rsize; 244 chks = (epos - offset + rsize - 1) / rsize;
247 GNUNET_assert (chks <= CHK_PER_INODE); 245 GNUNET_assert(chks <= CHK_PER_INODE);
248 return chks * sizeof (struct ContentHashKey); 246 return chks * sizeof(struct ContentHashKey);
249} 247}
250 248
251 249
@@ -267,16 +265,16 @@ GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset,
267 * @param cont function to call when done 265 * @param cont function to call when done
268 */ 266 */
269struct GNUNET_FS_TreeEncoder * 267struct GNUNET_FS_TreeEncoder *
270GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, uint64_t size, 268GNUNET_FS_tree_encoder_create(struct GNUNET_FS_Handle *h, uint64_t size,
271 void *cls, 269 void *cls,
272 GNUNET_FS_DataReader reader, 270 GNUNET_FS_DataReader reader,
273 GNUNET_FS_TreeBlockProcessor proc, 271 GNUNET_FS_TreeBlockProcessor proc,
274 GNUNET_FS_TreeProgressCallback progress, 272 GNUNET_FS_TreeProgressCallback progress,
275 GNUNET_SCHEDULER_TaskCallback cont) 273 GNUNET_SCHEDULER_TaskCallback cont)
276{ 274{
277 struct GNUNET_FS_TreeEncoder *te; 275 struct GNUNET_FS_TreeEncoder *te;
278 276
279 te = GNUNET_new (struct GNUNET_FS_TreeEncoder); 277 te = GNUNET_new(struct GNUNET_FS_TreeEncoder);
280 te->h = h; 278 te->h = h;
281 te->size = size; 279 te->size = size;
282 te->cls = cls; 280 te->cls = cls;
@@ -284,14 +282,14 @@ GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, uint64_t size,
284 te->proc = proc; 282 te->proc = proc;
285 te->progress = progress; 283 te->progress = progress;
286 te->cont = cont; 284 te->cont = cont;
287 te->chk_tree_depth = GNUNET_FS_compute_depth (size); 285 te->chk_tree_depth = GNUNET_FS_compute_depth(size);
288 te->chk_tree 286 te->chk_tree
289 = GNUNET_new_array (te->chk_tree_depth * CHK_PER_INODE, 287 = GNUNET_new_array(te->chk_tree_depth * CHK_PER_INODE,
290 struct ContentHashKey); 288 struct ContentHashKey);
291 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 289 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
292 "Created tree encoder for file with %llu bytes and depth %u\n", 290 "Created tree encoder for file with %llu bytes and depth %u\n",
293 (unsigned long long) size, 291 (unsigned long long)size,
294 te->chk_tree_depth); 292 te->chk_tree_depth);
295 return te; 293 return te;
296} 294}
297 295
@@ -308,12 +306,12 @@ GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, uint64_t size,
308 * @return (array of CHKs') offset in the above IBlock 306 * @return (array of CHKs') offset in the above IBlock
309 */ 307 */
310static unsigned int 308static unsigned int
311compute_chk_offset (unsigned int depth, uint64_t end_offset) 309compute_chk_offset(unsigned int depth, uint64_t end_offset)
312{ 310{
313 uint64_t bds; 311 uint64_t bds;
314 unsigned int ret; 312 unsigned int ret;
315 313
316 bds = GNUNET_FS_tree_compute_tree_size (depth); 314 bds = GNUNET_FS_tree_compute_tree_size(depth);
317 if (depth > 0) 315 if (depth > 0)
318 end_offset--; /* round down since for depth > 0 offset is at the END of the block */ 316 end_offset--; /* round down since for depth > 0 offset is at the END of the block */
319 ret = end_offset / bds; 317 ret = end_offset / bds;
@@ -329,7 +327,7 @@ compute_chk_offset (unsigned int depth, uint64_t end_offset)
329 * @param te tree encoder to use 327 * @param te tree encoder to use
330 */ 328 */
331void 329void
332GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te) 330GNUNET_FS_tree_encoder_next(struct GNUNET_FS_TreeEncoder *te)
333{ 331{
334 struct ContentHashKey *mychk; 332 struct ContentHashKey *mychk;
335 const void *pt_block; 333 const void *pt_block;
@@ -340,77 +338,77 @@ GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te)
340 struct GNUNET_CRYPTO_SymmetricInitializationVector iv; 338 struct GNUNET_CRYPTO_SymmetricInitializationVector iv;
341 unsigned int off; 339 unsigned int off;
342 340
343 GNUNET_assert (GNUNET_NO == te->in_next); 341 GNUNET_assert(GNUNET_NO == te->in_next);
344 te->in_next = GNUNET_YES; 342 te->in_next = GNUNET_YES;
345 if (te->chk_tree_depth == te->current_depth) 343 if (te->chk_tree_depth == te->current_depth)
346 {
347 off = CHK_PER_INODE * (te->chk_tree_depth - 1);
348 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
349 GNUNET_h2s (&te->chk_tree[off].query), off);
350 te->uri = GNUNET_new (struct GNUNET_FS_Uri);
351 te->uri->type = GNUNET_FS_URI_CHK;
352 te->uri->data.chk.chk = te->chk_tree[off];
353 te->uri->data.chk.file_length = GNUNET_htonll (te->size);
354 te->in_next = GNUNET_NO;
355 te->cont (te->cls);
356 return;
357 }
358 if (0 == te->current_depth)
359 {
360 /* read DBLOCK */
361 pt_size = GNUNET_MIN (DBLOCK_SIZE, te->size - te->publish_offset);
362 if (pt_size !=
363 te->reader (te->cls, te->publish_offset, pt_size, iob, &te->emsg))
364 { 344 {
345 off = CHK_PER_INODE * (te->chk_tree_depth - 1);
346 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n",
347 GNUNET_h2s(&te->chk_tree[off].query), off);
348 te->uri = GNUNET_new(struct GNUNET_FS_Uri);
349 te->uri->type = GNUNET_FS_URI_CHK;
350 te->uri->data.chk.chk = te->chk_tree[off];
351 te->uri->data.chk.file_length = GNUNET_htonll(te->size);
365 te->in_next = GNUNET_NO; 352 te->in_next = GNUNET_NO;
366 te->cont (te->cls); 353 te->cont(te->cls);
367 return; 354 return;
368 } 355 }
369 pt_block = iob; 356 if (0 == te->current_depth)
370 } 357 {
358 /* read DBLOCK */
359 pt_size = GNUNET_MIN(DBLOCK_SIZE, te->size - te->publish_offset);
360 if (pt_size !=
361 te->reader(te->cls, te->publish_offset, pt_size, iob, &te->emsg))
362 {
363 te->in_next = GNUNET_NO;
364 te->cont(te->cls);
365 return;
366 }
367 pt_block = iob;
368 }
371 else 369 else
372 { 370 {
373 pt_size = 371 pt_size =
374 GNUNET_FS_tree_compute_iblock_size (te->current_depth, 372 GNUNET_FS_tree_compute_iblock_size(te->current_depth,
375 te->publish_offset); 373 te->publish_offset);
376 pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE]; 374 pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE];
377 } 375 }
378 off = compute_chk_offset (te->current_depth, te->publish_offset); 376 off = compute_chk_offset(te->current_depth, te->publish_offset);
379 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 377 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", 378 "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, 379 (unsigned long long)te->publish_offset, te->current_depth,
382 (unsigned int) pt_size, (unsigned int) off); 380 (unsigned int)pt_size, (unsigned int)off);
383 mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off]; 381 mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off];
384 GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key); 382 GNUNET_CRYPTO_hash(pt_block, pt_size, &mychk->key);
385 GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv); 383 GNUNET_CRYPTO_hash_to_aes_key(&mychk->key, &sk, &iv);
386 GNUNET_CRYPTO_symmetric_encrypt (pt_block, pt_size, &sk, &iv, enc); 384 GNUNET_CRYPTO_symmetric_encrypt(pt_block, pt_size, &sk, &iv, enc);
387 GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query); 385 GNUNET_CRYPTO_hash(enc, pt_size, &mychk->query);
388 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, 386 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
389 "TE calculates query to be `%s', stored at %u\n", 387 "TE calculates query to be `%s', stored at %u\n",
390 GNUNET_h2s (&mychk->query), 388 GNUNET_h2s(&mychk->query),
391 te->current_depth * CHK_PER_INODE + off); 389 te->current_depth * CHK_PER_INODE + off);
392 if (NULL != te->proc) 390 if (NULL != te->proc)
393 te->proc (te->cls, mychk, te->publish_offset, te->current_depth, 391 te->proc(te->cls, mychk, te->publish_offset, te->current_depth,
394 (0 == 392 (0 ==
395 te->current_depth) ? GNUNET_BLOCK_TYPE_FS_DBLOCK : 393 te->current_depth) ? GNUNET_BLOCK_TYPE_FS_DBLOCK :
396 GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size); 394 GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size);
397 if (NULL != te->progress) 395 if (NULL != te->progress)
398 te->progress (te->cls, te->publish_offset, pt_block, pt_size, 396 te->progress(te->cls, te->publish_offset, pt_block, pt_size,
399 te->current_depth); 397 te->current_depth);
400 if (0 == te->current_depth) 398 if (0 == te->current_depth)
401 { 399 {
402 te->publish_offset += pt_size; 400 te->publish_offset += pt_size;
403 if ((te->publish_offset == te->size) || 401 if ((te->publish_offset == te->size) ||
404 (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE))) 402 (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE)))
405 te->current_depth++; 403 te->current_depth++;
406 } 404 }
407 else 405 else
408 { 406 {
409 if ((off == CHK_PER_INODE) || (te->publish_offset == te->size)) 407 if ((off == CHK_PER_INODE) || (te->publish_offset == te->size))
410 te->current_depth++; 408 te->current_depth++;
411 else 409 else
412 te->current_depth = 0; 410 te->current_depth = 0;
413 } 411 }
414 te->in_next = GNUNET_NO; 412 te->in_next = GNUNET_NO;
415} 413}
416 414
@@ -422,10 +420,10 @@ GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te)
422 * @return uri set to the resulting URI (if encoding finished), NULL otherwise 420 * @return uri set to the resulting URI (if encoding finished), NULL otherwise
423 */ 421 */
424struct GNUNET_FS_Uri * 422struct GNUNET_FS_Uri *
425GNUNET_FS_tree_encoder_get_uri (struct GNUNET_FS_TreeEncoder *te) 423GNUNET_FS_tree_encoder_get_uri(struct GNUNET_FS_TreeEncoder *te)
426{ 424{
427 if (NULL != te->uri) 425 if (NULL != te->uri)
428 return GNUNET_FS_uri_dup (te->uri); 426 return GNUNET_FS_uri_dup(te->uri);
429 return NULL; 427 return NULL;
430} 428}
431 429
@@ -441,23 +439,23 @@ GNUNET_FS_tree_encoder_get_uri (struct GNUNET_FS_TreeEncoder *te)
441 * both "*emsg" will be set to NULL). 439 * both "*emsg" will be set to NULL).
442 */ 440 */
443void 441void
444GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te, 442GNUNET_FS_tree_encoder_finish(struct GNUNET_FS_TreeEncoder *te,
445 char **emsg) 443 char **emsg)
446{ 444{
447 if (NULL != te->reader) 445 if (NULL != te->reader)
448 { 446 {
449 (void) te->reader (te->cls, UINT64_MAX, 0, 0, NULL); 447 (void)te->reader(te->cls, UINT64_MAX, 0, 0, NULL);
450 te->reader = NULL; 448 te->reader = NULL;
451 } 449 }
452 GNUNET_assert (GNUNET_NO == te->in_next); 450 GNUNET_assert(GNUNET_NO == te->in_next);
453 if (NULL != te->uri) 451 if (NULL != te->uri)
454 GNUNET_FS_uri_destroy (te->uri); 452 GNUNET_FS_uri_destroy(te->uri);
455 if (emsg != NULL) 453 if (emsg != NULL)
456 *emsg = te->emsg; 454 *emsg = te->emsg;
457 else 455 else
458 GNUNET_free_non_null (te->emsg); 456 GNUNET_free_non_null(te->emsg);
459 GNUNET_free (te->chk_tree); 457 GNUNET_free(te->chk_tree);
460 GNUNET_free (te); 458 GNUNET_free(te);
461} 459}
462 460
463/* end of fs_tree.c */ 461/* end of fs_tree.c */