major rewrite of fs_download, hopefully fixing 1641

1 files changed, 139 insertions, 111 deletions

diff --git a/src/fs/fs_tree.c b/src/fs/fs_tree.c
index 05c9c55cd..e22ce8221 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)
+     (C) 2009-2011 Christian Grothoff (and other contributing authors)
 
      GNUnet is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
@@ -75,7 +75,7 @@ struct GNUNET_FS_TreeEncoder
    * Set to the URI (upon successful completion)
    */
   struct GNUNET_FS_Uri *uri;
-  
+
   /**
    * Overall file size.
    */
@@ -87,12 +87,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;
 
@@ -121,7 +121,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)
@@ -146,73 +146,53 @@ GNUNET_FS_compute_depth (uint64_t flen)
 
 
 /**
- * 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;
-  
-  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<height;i++)
-    bds *= CHK_PER_INODE;
-  mod = offset % bds;
+  GNUNET_assert (depth > 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 */
@@ -232,42 +212,40 @@ GNUNET_FS_tree_compute_iblock_size (unsigned int height,
 
 /**
  * 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)
 {
-  unsigned int i;
   size_t ret;
   uint64_t rsize;
   uint64_t epos;
   unsigned int chks;
 
+  GNUNET_assert (fsize > 0);
   GNUNET_assert (offset <= fsize);
-  if (depth == totaldepth)
+  if (depth == 0)
     {
       ret = DBLOCK_SIZE;
-      if (offset + ret > fsize)
+      if ( (offset + ret > fsize) ||
+           (offset + ret < offset) )
         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;
+
+  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;
@@ -277,29 +255,71 @@ GNUNET_FS_tree_calculate_block_size (uint64_t fsize,
 
 
 /**
+ * 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.
+ *
+ * @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_Task cont)
+{
+  struct GNUNET_FS_TreeEncoder *te;
+  
+  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->chk_tree = GNUNET_malloc (te->chk_tree_depth *
+                                CHK_PER_INODE *
+                                sizeof (struct ContentHashKey));
+  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<height;i++)
-    bds *= CHK_PER_INODE;
-  if (height > 0)
-    offset--; /* round down since for height > 0 offset is at the END of the block */
-  ret = offset / bds;
+  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; 
 }
 
@@ -325,8 +345,26 @@ GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
 
   GNUNET_assert (GNUNET_NO == te->in_next);
   te->in_next = GNUNET_YES;
-  if (te->current_depth == te->chk_tree_depth)
+  if (te->chk_tree_depth == te->current_depth)
+    {
+      off = CHK_PER_INODE * (te->chk_tree_depth - 1);
+#if DEBUG_TREE
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+              "TE done, reading CHK `%s' from %u\n",
+              GNUNET_h2s (&te->chk_tree[off].query),           
+              off);
+#endif
+      te->uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri));
+      te->uri->type = 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, NULL);
+      return;
+    }
+  if (0 == te->current_depth)
     {
+      /* read DBLOCK */
       pt_size = GNUNET_MIN(DBLOCK_SIZE,
                            te->size - te->publish_offset);
       if (pt_size !=
@@ -346,24 +384,12 @@ GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
     }
   else
     {
-      pt_size = GNUNET_FS_tree_compute_iblock_size (te->chk_tree_depth - te->current_depth,
+      pt_size = GNUNET_FS_tree_compute_iblock_size (te->current_depth,
                                                     te->publish_offset); 
-      pt_block = &te->chk_tree[te->current_depth *
+      pt_block = &te->chk_tree[(te->current_depth - 1) *
                                CHK_PER_INODE];
     }
-  if (0 == te->current_depth)
-    {
-      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;
-      return;
-    }
-  off = compute_chk_offset (te->chk_tree_depth - te->current_depth,
+  off = compute_chk_offset (te->current_depth,
                             te->publish_offset);
 #if DEBUG_TREE
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
@@ -373,7 +399,7 @@ GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
               (unsigned int) pt_size,
               (unsigned int) off);
 #endif
-  mychk = &te->chk_tree[(te->current_depth-1)*CHK_PER_INODE+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,
@@ -384,15 +410,16 @@ GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
   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));
+              "TE calculates query to be `%s', stored at %u\n",
+              GNUNET_h2s (&mychk->query),
+              te->current_depth * CHK_PER_INODE + off);
 #endif
   if (NULL != te->proc)
     te->proc (te->cls,
-              &mychk->query,
+              mychk,
               te->publish_offset,
               te->current_depth,
-              (te->current_depth == te->chk_tree_depth) 
+              (0 == te->current_depth)
               ? GNUNET_BLOCK_TYPE_FS_DBLOCK 
               : GNUNET_BLOCK_TYPE_FS_IBLOCK,
               enc,
@@ -403,20 +430,20 @@ GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
                   pt_block,
                   pt_size,
                   te->current_depth);
-  if (te->current_depth == te->chk_tree_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--;
+        te->current_depth++;
     }
   else
     {
       if ( (off == CHK_PER_INODE) ||
            (te->publish_offset == te->size) )
-        te->current_depth--;
+        te->current_depth++;
       else
-        te->current_depth = te->chk_tree_depth;
+        te->current_depth = 0;
     }
   te->in_next = GNUNET_NO;
 }
@@ -433,10 +460,11 @@ GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te)
  *        prior to completion and prior to an internal error,
  *        both "*uri" and "*emsg" will be set to NULL).
  */
-void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te,
+void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te,
                                     struct GNUNET_FS_Uri **uri,
                                     char **emsg)
 {
+  GNUNET_assert (GNUNET_NO == te->in_next);
   if (uri != NULL)
     *uri = te->uri;
   else