error handling
[oweals/gnunet.git] / src / fs / fs_tree.c
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 occured
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_non_null (te->emsg);
458   GNUNET_free (te->chk_tree);
459   GNUNET_free (te);
460 }
461
462
463 /* end of fs_tree.c */