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