X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Ffs%2Ffs_tree.c;h=e57e4e4943e806adcc2e8ba4367203f23076bd5c;hb=0e592870059883b779d02a14fa5ea13be5f50595;hp=b38a9c3828e75c665d2ad7366f4abb1f31ca49a0;hpb=75a33a1499cf60ea4364c9aa673816629a6c1413;p=oweals%2Fgnunet.git diff --git a/src/fs/fs_tree.c b/src/fs/fs_tree.c index b38a9c382..e57e4e494 100644 --- a/src/fs/fs_tree.c +++ b/src/fs/fs_tree.c @@ -1,6 +1,6 @@ /* This file is part of GNUnet. - (C) 2009 Christian Grothoff (and other contributing authors) + Copyright (C) 2009-2011 GNUnet e.V. GNUnet is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published @@ -14,8 +14,8 @@ You should have received a copy of the GNU General Public License along with GNUnet; see the file COPYING. If not, write to the - Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. + Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. */ /** * @file fs/fs_tree.c @@ -27,7 +27,6 @@ #include "platform.h" #include "fs_tree.h" -#define DEBUG_TREE GNUNET_NO /** * Context for an ECRS-based file encoder that computes @@ -40,7 +39,7 @@ struct GNUNET_FS_TreeEncoder * Global FS context. */ struct GNUNET_FS_Handle *h; - + /** * Closure for all callbacks. */ @@ -64,8 +63,8 @@ struct GNUNET_FS_TreeEncoder /** * Function to call once we're done with processing. */ - GNUNET_SCHEDULER_Task cont; - + GNUNET_SCHEDULER_TaskCallback cont; + /** * Set to an error message (if we had an error). */ @@ -75,7 +74,7 @@ struct GNUNET_FS_TreeEncoder * Set to the URI (upon successful completion) */ struct GNUNET_FS_Uri *uri; - + /** * Overall file size. */ @@ -87,12 +86,12 @@ struct GNUNET_FS_TreeEncoder uint64_t publish_offset; /** - * How deep are we? + * How deep are we? Depth 0 is for the DBLOCKs. */ unsigned int current_depth; /** - * How deep is the tree? + * How deep is the tree? Always > 0. */ unsigned int chk_tree_depth; @@ -100,7 +99,7 @@ struct GNUNET_FS_TreeEncoder * In-memory cache of the current CHK tree. * This struct will contain the CHK values * from the root to the currently processed - * node in the tree as identified by + * node in the tree as identified by * "current_depth" and "publish_offset". * The "chktree" will be initially NULL, * then allocated to a sufficient number of @@ -109,6 +108,11 @@ struct GNUNET_FS_TreeEncoder */ struct ContentHashKey *chk_tree; + /** + * Are we currently in 'GNUNET_FS_tree_encoder_next'? + * Flag used to prevent recursion. + */ + int in_next; }; @@ -116,7 +120,7 @@ struct GNUNET_FS_TreeEncoder * Compute the depth of the CHK tree. * * @param flen file length for which to compute the depth - * @return depth of the tree + * @return depth of the tree, always > 0. A depth of 1 means only a DBLOCK. */ unsigned int GNUNET_FS_compute_depth (uint64_t flen) @@ -127,143 +131,116 @@ GNUNET_FS_compute_depth (uint64_t flen) treeDepth = 1; fl = DBLOCK_SIZE; while (fl < flen) + { + treeDepth++; + if (fl * CHK_PER_INODE < fl) { - treeDepth++; - if (fl * CHK_PER_INODE < fl) - { - /* integer overflow, this is a HUGE file... */ - return treeDepth; - } - fl = fl * CHK_PER_INODE; + /* integer overflow, this is a HUGE file... */ + return treeDepth; } + fl = fl * CHK_PER_INODE; + } return treeDepth; } /** - * Initialize a tree encoder. This function will call "proc" and - * "progress" on each block in the tree. Once all blocks have been - * processed, "cont" will be scheduled. The "reader" will be called - * to obtain the (plaintext) blocks for the file. Note that this - * function will not actually call "proc". The client must - * call "GNUNET_FS_tree_encoder_next" to trigger encryption (and - * calling of "proc") for the each block. + * Calculate how many bytes of payload a block tree of the given + * depth MAY correspond to at most (this function ignores the fact that + * some blocks will only be present partially due to the total file + * size cutting some blocks off at the end). * - * @param h the global FS context - * @param size overall size of the file to encode - * @param cls closure for reader, proc, progress and cont - * @param reader function to call to read plaintext data - * @param proc function to call on each encrypted block - * @param progress function to call with progress information - * @param cont function to call when done + * @param depth depth of the block. depth==0 is a DBLOCK. + * @return number of bytes of payload a subtree of this depth may correspond to */ -struct GNUNET_FS_TreeEncoder * -GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, - uint64_t size, - void *cls, - GNUNET_FS_DataReader reader, - GNUNET_FS_TreeBlockProcessor proc, - GNUNET_FS_TreeProgressCallback progress, - GNUNET_SCHEDULER_Task cont) +uint64_t +GNUNET_FS_tree_compute_tree_size (unsigned int depth) { - struct GNUNET_FS_TreeEncoder *te; - - GNUNET_assert (size > 0); - te = GNUNET_malloc (sizeof (struct GNUNET_FS_TreeEncoder)); - te->h = h; - te->size = size; - te->cls = cls; - te->reader = reader; - te->proc = proc; - te->progress = progress; - te->cont = cont; - te->chk_tree_depth = GNUNET_FS_compute_depth (size); - te->current_depth = te->chk_tree_depth; - te->chk_tree = GNUNET_malloc (te->chk_tree_depth * - CHK_PER_INODE * - sizeof (struct ContentHashKey)); - return te; + uint64_t rsize; + unsigned int i; + + rsize = DBLOCK_SIZE; + for (i = 0; i < depth; i++) + rsize *= CHK_PER_INODE; + return rsize; } /** - * Compute the size of the current IBlock. + * Compute the size of the current IBLOCK. The encoder is + * triggering the calculation of the size of an IBLOCK at the + * *end* (hence end_offset) of its construction. The IBLOCK + * maybe a full or a partial IBLOCK, and this function is to + * calculate how long it should be. * - * @param height height of the IBlock in the tree (aka overall - * number of tree levels minus depth); 0 == DBlock - * @param offset current offset in the overall file + * @param depth depth of the IBlock in the tree, 0 would be a DBLOCK, + * must be > 0 (this function is for IBLOCKs only!) + * @param end_offset current offset in the payload (!) of the overall file, + * must be > 0 (since this function is called at the + * end of a block). * @return size of the corresponding IBlock */ -uint16_t -GNUNET_FS_tree_compute_iblock_size (unsigned int height, - uint64_t offset) +static uint16_t +GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset) { unsigned int ret; - unsigned int i; uint64_t mod; uint64_t bds; - GNUNET_assert (height > 0); - bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i" - corresponds to */ - for (i=0;i 0); + GNUNET_assert (end_offset > 0); + bds = GNUNET_FS_tree_compute_tree_size (depth); + mod = end_offset % bds; if (0 == mod) - { - /* we were triggered at the end of a full block */ - ret = CHK_PER_INODE; - } + { + /* we were triggered at the end of a full block */ + ret = CHK_PER_INODE; + } else - { - /* we were triggered at the end of the file */ - bds /= CHK_PER_INODE; - ret = mod / bds; - if (0 != mod % bds) - ret++; - } - return (uint16_t) (ret * sizeof(struct ContentHashKey)); + { + /* we were triggered at the end of the file */ + bds /= CHK_PER_INODE; + ret = mod / bds; + if (0 != mod % bds) + ret++; + } + return (uint16_t) (ret * sizeof (struct ContentHashKey)); } /** * Compute how many bytes of data should be stored in - * the specified node. + * the specified block. * - * @param fsize overall file size - * @param totaldepth depth of the entire tree - * @param offset offset of the node - * @param depth depth of the node + * @param fsize overall file size, must be > 0. + * @param offset offset in the original data corresponding + * to the beginning of the tree induced by the block; + * must be <= fsize + * @param depth depth of the node in the tree, 0 for DBLOCK * @return number of bytes stored in this node */ size_t -GNUNET_FS_tree_calculate_block_size (uint64_t fsize, - unsigned int totaldepth, - uint64_t offset, - unsigned int depth) +GNUNET_FS_tree_calculate_block_size (uint64_t fsize, uint64_t offset, + unsigned int depth) { - unsigned int i; size_t ret; uint64_t rsize; uint64_t epos; unsigned int chks; - GNUNET_assert (offset < fsize); - if (depth == totaldepth) - { - ret = DBLOCK_SIZE; - if (offset + ret > fsize) - ret = (size_t) (fsize - offset); - return ret; - } - /* FIXME: this code should be *equivalent* to the - GNUNET_FS_tree_compute_iblock_size function above! Remove duplication! */ - rsize = DBLOCK_SIZE; - for (i = totaldepth-1; i > depth; i--) - rsize *= CHK_PER_INODE; + GNUNET_assert (fsize > 0); + GNUNET_assert (offset <= fsize); + if (depth == 0) + { + ret = DBLOCK_SIZE; + if ((offset + ret > fsize) || (offset + ret < offset)) + ret = (size_t) (fsize - offset); + return ret; + } + + rsize = GNUNET_FS_tree_compute_tree_size (depth - 1); epos = offset + rsize * CHK_PER_INODE; - GNUNET_assert (epos > offset); - if (epos > fsize) + if ((epos < offset) || (epos > fsize)) epos = fsize; /* round up when computing #CHKs in our IBlock */ chks = (epos - offset + rsize - 1) / rsize; @@ -272,31 +249,75 @@ GNUNET_FS_tree_calculate_block_size (uint64_t fsize, } +/** + * Initialize a tree encoder. This function will call @a proc and + * "progress" on each block in the tree. Once all blocks have been + * processed, "cont" will be scheduled. The @a reader will be called + * to obtain the (plaintext) blocks for the file. Note that this + * function will not actually call @a proc. The client must + * call #GNUNET_FS_tree_encoder_next to trigger encryption (and + * calling of @a proc) for the each block. + * + * @param h the global FS context + * @param size overall size of the file to encode + * @param cls closure for reader, proc, progress and cont + * @param reader function to call to read plaintext data + * @param proc function to call on each encrypted block + * @param progress function to call with progress information + * @param cont function to call when done + */ +struct GNUNET_FS_TreeEncoder * +GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, uint64_t size, + void *cls, + GNUNET_FS_DataReader reader, + GNUNET_FS_TreeBlockProcessor proc, + GNUNET_FS_TreeProgressCallback progress, + GNUNET_SCHEDULER_TaskCallback cont) +{ + struct GNUNET_FS_TreeEncoder *te; + + te = GNUNET_new (struct GNUNET_FS_TreeEncoder); + te->h = h; + te->size = size; + te->cls = cls; + te->reader = reader; + te->proc = proc; + te->progress = progress; + te->cont = cont; + te->chk_tree_depth = GNUNET_FS_compute_depth (size); + te->chk_tree + = GNUNET_new_array (te->chk_tree_depth * CHK_PER_INODE, + struct ContentHashKey); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Created tree encoder for file with %llu bytes and depth %u\n", + (unsigned long long) size, + te->chk_tree_depth); + return te; +} + + /** * Compute the offset of the CHK for the * current block in the IBlock above. * - * @param height height of the IBlock in the tree (aka overall + * @param depth depth of the IBlock in the tree (aka overall * number of tree levels minus depth); 0 == DBlock - * @param offset current offset in the overall file + * @param end_offset current offset in the overall file, + * at the *beginning* of the block for DBLOCKs (depth==0), + * otherwise at the *end* of the block (exclusive) * @return (array of CHKs') offset in the above IBlock */ static unsigned int -compute_chk_offset (unsigned int height, - uint64_t offset) +compute_chk_offset (unsigned int depth, uint64_t end_offset) { uint64_t bds; unsigned int ret; - unsigned int i; - bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i" - corresponds to */ - for (i=0;i 0) - offset--; /* round down since for height > 0 offset is at the END of the block */ - ret = offset / bds; - return ret % CHK_PER_INODE; + bds = GNUNET_FS_tree_compute_tree_size (depth); + if (depth > 0) + end_offset--; /* round down since for depth > 0 offset is at the END of the block */ + ret = end_offset / bds; + return ret % CHK_PER_INODE; } @@ -307,130 +328,130 @@ compute_chk_offset (unsigned int height, * * @param te tree encoder to use */ -void GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te) +void +GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder *te) { struct ContentHashKey *mychk; const void *pt_block; uint16_t pt_size; char iob[DBLOCK_SIZE]; char enc[DBLOCK_SIZE]; - struct GNUNET_CRYPTO_AesSessionKey sk; - struct GNUNET_CRYPTO_AesInitializationVector iv; + struct GNUNET_CRYPTO_SymmetricSessionKey sk; + struct GNUNET_CRYPTO_SymmetricInitializationVector iv; unsigned int off; - if (te->current_depth == te->chk_tree_depth) - { - pt_size = GNUNET_MIN(DBLOCK_SIZE, - te->size - te->publish_offset); - if (pt_size != - te->reader (te->cls, - te->publish_offset, - pt_size, - iob, - &te->emsg)) - { - GNUNET_SCHEDULER_add_continuation (te->cont, - te->cls, - GNUNET_SCHEDULER_REASON_TIMEOUT); - return; - } - pt_block = iob; - } - else - { - pt_size = GNUNET_FS_tree_compute_iblock_size (te->chk_tree_depth - te->current_depth, - te->publish_offset); - pt_block = &te->chk_tree[te->current_depth * - CHK_PER_INODE]; - } + GNUNET_assert (GNUNET_NO == te->in_next); + te->in_next = GNUNET_YES; + if (te->chk_tree_depth == te->current_depth) + { + off = CHK_PER_INODE * (te->chk_tree_depth - 1); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TE done, reading CHK `%s' from %u\n", + GNUNET_h2s (&te->chk_tree[off].query), off); + te->uri = GNUNET_new (struct GNUNET_FS_Uri); + te->uri->type = GNUNET_FS_URI_CHK; + te->uri->data.chk.chk = te->chk_tree[off]; + te->uri->data.chk.file_length = GNUNET_htonll (te->size); + te->in_next = GNUNET_NO; + te->cont (te->cls); + return; + } if (0 == te->current_depth) + { + /* read DBLOCK */ + pt_size = GNUNET_MIN (DBLOCK_SIZE, te->size - te->publish_offset); + if (pt_size != + te->reader (te->cls, te->publish_offset, pt_size, iob, &te->emsg)) { - te->uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri)); - te->uri->type = chk; - te->uri->data.chk.chk = te->chk_tree[0]; - te->uri->data.chk.file_length = GNUNET_htonll (te->size); - GNUNET_SCHEDULER_add_continuation (te->cont, - te->cls, - GNUNET_SCHEDULER_REASON_PREREQ_DONE); + te->in_next = GNUNET_NO; + te->cont (te->cls); return; } - off = compute_chk_offset (te->chk_tree_depth - te->current_depth, - te->publish_offset); -#if DEBUG_TREE + pt_block = iob; + } + else + { + pt_size = + GNUNET_FS_tree_compute_iblock_size (te->current_depth, + te->publish_offset); + pt_block = &te->chk_tree[(te->current_depth - 1) * CHK_PER_INODE]; + } + off = compute_chk_offset (te->current_depth, te->publish_offset); GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n", - (unsigned long long) te->publish_offset, - te->current_depth, - (unsigned int) pt_size, - (unsigned int) off); -#endif - mychk = &te->chk_tree[(te->current_depth-1)*CHK_PER_INODE+off]; + "TE is at offset %llu and depth %u with block size %u and target-CHK-offset %u\n", + (unsigned long long) te->publish_offset, te->current_depth, + (unsigned int) pt_size, (unsigned int) off); + mychk = &te->chk_tree[te->current_depth * CHK_PER_INODE + off]; GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key); GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv); - GNUNET_CRYPTO_aes_encrypt (pt_block, - pt_size, - &sk, - &iv, - enc); + GNUNET_CRYPTO_symmetric_encrypt (pt_block, pt_size, &sk, &iv, enc); GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query); -#if DEBUG_TREE GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "TE calculates query to be `%s'\n", - GNUNET_h2s (&mychk->query)); -#endif + "TE calculates query to be `%s', stored at %u\n", + GNUNET_h2s (&mychk->query), + te->current_depth * CHK_PER_INODE + off); if (NULL != te->proc) - te->proc (te->cls, - &mychk->query, - te->publish_offset, - (te->current_depth == te->chk_tree_depth) - ? GNUNET_BLOCK_TYPE_FS_DBLOCK - : GNUNET_BLOCK_TYPE_FS_IBLOCK, - enc, - pt_size); + te->proc (te->cls, mychk, te->publish_offset, te->current_depth, + (0 == + te->current_depth) ? GNUNET_BLOCK_TYPE_FS_DBLOCK : + GNUNET_BLOCK_TYPE_FS_IBLOCK, enc, pt_size); if (NULL != te->progress) - te->progress (te->cls, - te->publish_offset, - pt_block, - pt_size, - te->current_depth); - if (te->current_depth == te->chk_tree_depth) - { - te->publish_offset += pt_size; - if ( (te->publish_offset == te->size) || - (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE) ) ) - te->current_depth--; - } + te->progress (te->cls, te->publish_offset, pt_block, pt_size, + te->current_depth); + if (0 == te->current_depth) + { + te->publish_offset += pt_size; + if ((te->publish_offset == te->size) || + (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE))) + te->current_depth++; + } else - { - if ( (off == CHK_PER_INODE) || - (te->publish_offset == te->size) ) - te->current_depth--; - else - te->current_depth = te->chk_tree_depth; - } + { + if ((off == CHK_PER_INODE) || (te->publish_offset == te->size)) + te->current_depth++; + else + te->current_depth = 0; + } + te->in_next = GNUNET_NO; +} + + +/** + * Get the resulting URI from the encoding. + * + * @param te the tree encoder to clean up + * @return uri set to the resulting URI (if encoding finished), NULL otherwise + */ +struct GNUNET_FS_Uri * +GNUNET_FS_tree_encoder_get_uri (struct GNUNET_FS_TreeEncoder *te) +{ + if (NULL != te->uri) + return GNUNET_FS_uri_dup (te->uri); + return NULL; } /** * Clean up a tree encoder and return information - * about the resulting URI or an error message. - * + * about possible errors. + * * @param te the tree encoder to clean up - * @param uri set to the resulting URI (if encoding finished) * @param emsg set to an error message (if an error occured * within the tree encoder; if this function is called * prior to completion and prior to an internal error, - * both "*uri" and "*emsg" will be set to NULL). + * both "*emsg" will be set to NULL). */ -void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te, - struct GNUNET_FS_Uri **uri, - char **emsg) +void +GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te, + char **emsg) { - if (uri != NULL) - *uri = te->uri; - else - if (NULL != te->uri) - GNUNET_FS_uri_destroy (te->uri); + if (NULL != te->reader) + { + (void) te->reader (te->cls, UINT64_MAX, 0, 0, NULL); + te->reader = NULL; + } + GNUNET_assert (GNUNET_NO == te->in_next); + if (NULL != te->uri) + GNUNET_FS_uri_destroy (te->uri); if (emsg != NULL) *emsg = te->emsg; else