aboutsummaryrefslogtreecommitdiff
path: root/src/fs/fs_tree.c
blob: 5dc39e4e614ce33ad1069ef2c79049203ba90cb4 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
/*
     This file is part of GNUnet.
     (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
     by the Free Software Foundation; either version 3, or (at your
     option) any later version.

     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     General Public License for more details.

     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.
*/
/**
 * @file fs/fs_tree.c
 * @brief Merkle-tree-ish-CHK file encoding for GNUnet
 * @see http://gnunet.org/encoding.php3
 * @author Krista Bennett
 * @author Christian Grothoff
 */
#include "platform.h"
#include "fs_tree.h"


/**
 * Context for an ECRS-based file encoder that computes
 * the Merkle-ish-CHK tree.
 */
struct GNUNET_FS_TreeEncoder
{

  /**
   * Global FS context.
   */
  struct GNUNET_FS_Handle *h;

  /**
   * Closure for all callbacks.
   */
  void *cls;

  /**
   * Function to call on encrypted blocks.
   */
  GNUNET_FS_TreeBlockProcessor proc;

  /**
   * Function to call with progress information.
   */
  GNUNET_FS_TreeProgressCallback progress;

  /**
   * Function to call to receive input data.
   */
  GNUNET_FS_DataReader reader;

  /**
   * Function to call once we're done with processing.
   */
  GNUNET_SCHEDULER_Task cont;

  /**
   * Set to an error message (if we had an error).
   */
  char *emsg;

  /**
   * Set to the URI (upon successful completion)
   */
  struct GNUNET_FS_Uri *uri;

  /**
   * Overall file size.
   */
  uint64_t size;

  /**
   * How far are we?
   */
  uint64_t publish_offset;

  /**
   * How deep are we?  Depth 0 is for the DBLOCKs.
   */
  unsigned int current_depth;

  /**
   * How deep is the tree? Always > 0.
   */
  unsigned int chk_tree_depth;

  /**
   * 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
   * "current_depth" and "publish_offset".
   * The "chktree" will be initially NULL,
   * then allocated to a sufficient number of
   * entries for the size of the file and
   * finally freed once the upload is complete.
   */
  struct ContentHashKey *chk_tree;

  /**
   * Are we currently in 'GNUNET_FS_tree_encoder_next'?
   * Flag used to prevent recursion.
   */
  int in_next;
};


/**
 * Compute the depth of the CHK tree.
 *
 * @param flen file length for which to compute the depth
 * @return depth of the tree, always > 0.  A depth of 1 means only a DBLOCK.
 */
unsigned int
GNUNET_FS_compute_depth (uint64_t flen)
{
  unsigned int treeDepth;
  uint64_t fl;

  treeDepth = 1;
  fl = DBLOCK_SIZE;
  while (fl < flen)
  {
    treeDepth++;
    if (fl * CHK_PER_INODE < fl)
    {
      /* integer overflow, this is a HUGE file... */
      return treeDepth;
    }
    fl = fl * CHK_PER_INODE;
  }
  return treeDepth;
}


/**
 * 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 depth depth of the block.  depth==0 is a DBLOCK.
 * @return number of bytes of payload a subtree of this depth may correspond to
 */
uint64_t
GNUNET_FS_tree_compute_tree_size (unsigned int depth)
{
  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.  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 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
 */
static uint16_t
GNUNET_FS_tree_compute_iblock_size (unsigned int depth, uint64_t end_offset)
{
  unsigned int ret;
  uint64_t mod;
  uint64_t 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 */
    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));
}


/**
 * Compute how many bytes of data should be stored in
 * the specified block.
 *
 * @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, uint64_t offset,
                                     unsigned int depth)
{
  size_t ret;
  uint64_t rsize;
  uint64_t epos;
  unsigned int chks;

  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;
  if ((epos < offset) || (epos > fsize))
    epos = fsize;
  /* round up when computing #CHKs in our IBlock */
  chks = (epos - offset + rsize - 1) / rsize;
  GNUNET_assert (chks <= CHK_PER_INODE);
  return chks * sizeof (struct ContentHashKey);
}


/**
 * 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_Task 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_malloc (te->chk_tree_depth * CHK_PER_INODE *
                     sizeof (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 depth depth of the IBlock in the tree (aka overall
 *               number of tree levels minus depth); 0 == DBlock
 * @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 depth, uint64_t end_offset)
{
  uint64_t bds;
  unsigned int ret;

  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;
}


/**
 * Encrypt the next block of the file (and call proc and progress
 * accordingly; or of course "cont" if we have already completed
 * encoding of the entire file).
 *
 * @param te tree encoder to use
 */
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_SymmetricSessionKey sk;
  struct GNUNET_CRYPTO_SymmetricInitializationVector iv;
  unsigned int off;

  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, NULL);
    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->in_next = GNUNET_NO;
      te->cont (te->cls, NULL);
      return;
    }
    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);
  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_symmetric_encrypt (pt_block, pt_size, &sk, &iv, enc);
  GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query);
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "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, 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 (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 = 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 possible errors.
 *
 * @param te the tree encoder to clean up
 * @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 "*emsg" will be set to NULL).
 */
void
GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder *te,
			       char **emsg)
{
  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
    GNUNET_free_non_null (te->emsg);
  GNUNET_free (te->chk_tree);
  GNUNET_free (te);
}

/* end of fs_tree.c */