diff options
author | Christian Grothoff <christian@grothoff.org> | 2009-09-02 08:24:20 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2009-09-02 08:24:20 +0000 |
commit | 09118c85cd5200267784985900e4f83ea31b8622 (patch) | |
tree | 53fcbc1b6a38c3f4582769276243c485a7b98dff /src/fs/fs_tree.c | |
parent | 815c76f4aeb141fa9654bc3abc16998c8188268f (diff) | |
download | gnunet-09118c85cd5200267784985900e4f83ea31b8622.tar.gz gnunet-09118c85cd5200267784985900e4f83ea31b8622.zip |
refactoring publishing code
Diffstat (limited to 'src/fs/fs_tree.c')
-rw-r--r-- | src/fs/fs_tree.c | 381 |
1 files changed, 381 insertions, 0 deletions
diff --git a/src/fs/fs_tree.c b/src/fs/fs_tree.c new file mode 100644 index 000000000..5d6a4f1d9 --- /dev/null +++ b/src/fs/fs_tree.c | |||
@@ -0,0 +1,381 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | (C) 2009 Christian Grothoff (and other contributing authors) | ||
4 | |||
5 | GNUnet is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 2, or (at your | ||
8 | 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 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
18 | Boston, MA 02111-1307, USA. | ||
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 | * TODO: | ||
28 | * - decide if this API should be made public (gnunet_fs_service.h) | ||
29 | * or remain "internal" (but with exported symbols?) | ||
30 | */ | ||
31 | #include "platform.h" | ||
32 | #include "fs_tree.h" | ||
33 | |||
34 | |||
35 | /** | ||
36 | * Context for an ECRS-based file encoder that computes | ||
37 | * the Merkle-ish-CHK tree. | ||
38 | */ | ||
39 | struct GNUNET_FS_TreeEncoder | ||
40 | { | ||
41 | |||
42 | /** | ||
43 | * Global FS context. | ||
44 | */ | ||
45 | struct GNUNET_FS_Handle *h; | ||
46 | |||
47 | /** | ||
48 | * Closure for all callbacks. | ||
49 | */ | ||
50 | void *cls; | ||
51 | |||
52 | /** | ||
53 | * Function to call on encrypted blocks. | ||
54 | */ | ||
55 | GNUNET_FS_TreeBlockProcessor proc; | ||
56 | |||
57 | /** | ||
58 | * Function to call with progress information. | ||
59 | */ | ||
60 | GNUNET_FS_TreeProgressCallback progress; | ||
61 | |||
62 | /** | ||
63 | * Function to call to receive input data. | ||
64 | */ | ||
65 | GNUNET_FS_DataReader reader; | ||
66 | |||
67 | /** | ||
68 | * Function to call once we're done with processing. | ||
69 | */ | ||
70 | GNUNET_SCHEDULER_Task cont; | ||
71 | |||
72 | /** | ||
73 | * Set to an error message (if we had an error). | ||
74 | */ | ||
75 | char *emsg; | ||
76 | |||
77 | /** | ||
78 | * Set to the URI (upon successful completion) | ||
79 | */ | ||
80 | struct GNUNET_FS_Uri *uri; | ||
81 | |||
82 | /** | ||
83 | * Overall file size. | ||
84 | */ | ||
85 | uint64_t size; | ||
86 | |||
87 | /** | ||
88 | * How far are we? | ||
89 | */ | ||
90 | uint64_t publish_offset; | ||
91 | |||
92 | /** | ||
93 | * How deep are we? | ||
94 | */ | ||
95 | unsigned int current_depth; | ||
96 | |||
97 | /** | ||
98 | * How deep is the tree? | ||
99 | */ | ||
100 | unsigned int chk_tree_depth; | ||
101 | |||
102 | /** | ||
103 | * In-memory cache of the current CHK tree. | ||
104 | * This struct will contain the CHK values | ||
105 | * from the root to the currently processed | ||
106 | * node in the tree as identified by | ||
107 | * "current_depth" and "publish_offset". | ||
108 | * The "chktree" will be initially NULL, | ||
109 | * then allocated to a sufficient number of | ||
110 | * entries for the size of the file and | ||
111 | * finally freed once the upload is complete. | ||
112 | */ | ||
113 | struct ContentHashKey *chk_tree; | ||
114 | |||
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 | ||
123 | */ | ||
124 | static unsigned int | ||
125 | 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 | * Initialize a tree encoder. This function will call "proc" and | ||
148 | * "progress" on each block in the tree. Once all blocks have been | ||
149 | * processed, "cont" will be scheduled. The "reader" will be called | ||
150 | * to obtain the (plaintext) blocks for the file. Note that this | ||
151 | * function will not actually call "proc". The client must | ||
152 | * call "GNUNET_FS_tree_encoder_next" to trigger encryption (and | ||
153 | * calling of "proc") for the each block. | ||
154 | * | ||
155 | * @param h the global FS context | ||
156 | * @param size overall size of the file to encode | ||
157 | * @param cls closure for reader, proc, progress and cont | ||
158 | * @param reader function to call to read plaintext data | ||
159 | * @param proc function to call on each encrypted block | ||
160 | * @param progress function to call with progress information | ||
161 | * @param cont function to call when done | ||
162 | */ | ||
163 | struct GNUNET_FS_TreeEncoder * | ||
164 | GNUNET_FS_tree_encoder_create (struct GNUNET_FS_Handle *h, | ||
165 | uint64_t size, | ||
166 | void *cls, | ||
167 | GNUNET_FS_DataReader reader, | ||
168 | GNUNET_FS_TreeBlockProcessor proc, | ||
169 | GNUNET_FS_TreeProgressCallback progress, | ||
170 | GNUNET_SCHEDULER_Task cont) | ||
171 | { | ||
172 | struct GNUNET_FS_TreeEncoder *te; | ||
173 | |||
174 | te = GNUNET_malloc (sizeof (struct GNUNET_FS_TreeEncoder)); | ||
175 | te->h = h; | ||
176 | te->size = size; | ||
177 | te->cls = cls; | ||
178 | te->reader = reader; | ||
179 | te->proc = proc; | ||
180 | te->progress = progress; | ||
181 | te->cont = cont; | ||
182 | te->chk_tree_depth = compute_depth (size); | ||
183 | te->current_depth = te->chk_tree_depth; | ||
184 | te->chk_tree = GNUNET_malloc (te->chk_tree_depth * | ||
185 | CHK_PER_INODE * | ||
186 | sizeof (struct ContentHashKey)); | ||
187 | return te; | ||
188 | } | ||
189 | |||
190 | |||
191 | /** | ||
192 | * Compute the size of the current IBlock. | ||
193 | * | ||
194 | * @param height height of the IBlock in the tree (aka overall | ||
195 | * number of tree levels minus depth); 0 == DBlock | ||
196 | * @param offset current offset in the overall file | ||
197 | * @return size of the corresponding IBlock | ||
198 | */ | ||
199 | static uint16_t | ||
200 | compute_iblock_size (unsigned int height, | ||
201 | uint64_t offset) | ||
202 | { | ||
203 | unsigned int ret; | ||
204 | unsigned int i; | ||
205 | uint64_t mod; | ||
206 | uint64_t bds; | ||
207 | |||
208 | GNUNET_assert (height > 0); | ||
209 | bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i" | ||
210 | corresponds to */ | ||
211 | for (i=0;i<height;i++) | ||
212 | bds *= CHK_PER_INODE; | ||
213 | mod = offset % bds; | ||
214 | if (0 == mod) | ||
215 | { | ||
216 | /* we were triggered at the end of a full block */ | ||
217 | ret = CHK_PER_INODE; | ||
218 | } | ||
219 | else | ||
220 | { | ||
221 | /* we were triggered at the end of the file */ | ||
222 | bds /= CHK_PER_INODE; | ||
223 | ret = mod / bds; | ||
224 | if (0 != mod % bds) | ||
225 | ret++; | ||
226 | } | ||
227 | return (uint16_t) (ret * sizeof(struct ContentHashKey)); | ||
228 | } | ||
229 | |||
230 | |||
231 | /** | ||
232 | * Compute the offset of the CHK for the | ||
233 | * current block in the IBlock above. | ||
234 | * | ||
235 | * @param height height of the IBlock in the tree (aka overall | ||
236 | * number of tree levels minus depth); 0 == DBlock | ||
237 | * @param offset current offset in the overall file | ||
238 | * @return (array of CHKs') offset in the above IBlock | ||
239 | */ | ||
240 | static unsigned int | ||
241 | compute_chk_offset (unsigned int height, | ||
242 | uint64_t offset) | ||
243 | { | ||
244 | uint64_t bds; | ||
245 | unsigned int ret; | ||
246 | unsigned int i; | ||
247 | |||
248 | bds = DBLOCK_SIZE; /* number of bytes each CHK at level "i" | ||
249 | corresponds to */ | ||
250 | for (i=0;i<height;i++) | ||
251 | bds *= CHK_PER_INODE; | ||
252 | GNUNET_assert (0 == (offset % bds)); | ||
253 | ret = offset / bds; | ||
254 | return ret % CHK_PER_INODE; | ||
255 | } | ||
256 | |||
257 | |||
258 | /** | ||
259 | * Encrypt the next block of the file (and | ||
260 | * call proc and progress accordingly; or | ||
261 | * of course "cont" if we have already completed | ||
262 | * encoding of the entire file). | ||
263 | * | ||
264 | * @param te tree encoder to use | ||
265 | */ | ||
266 | void GNUNET_FS_tree_encoder_next (struct GNUNET_FS_TreeEncoder * te) | ||
267 | { | ||
268 | struct ContentHashKey *mychk; | ||
269 | const void *pt_block; | ||
270 | uint16_t pt_size; | ||
271 | char iob[DBLOCK_SIZE]; | ||
272 | char enc[DBLOCK_SIZE]; | ||
273 | struct GNUNET_CRYPTO_AesSessionKey sk; | ||
274 | struct GNUNET_CRYPTO_AesInitializationVector iv; | ||
275 | unsigned int off; | ||
276 | |||
277 | if (te->current_depth == te->chk_tree_depth) | ||
278 | { | ||
279 | pt_size = GNUNET_MIN(DBLOCK_SIZE, | ||
280 | te->size - te->publish_offset); | ||
281 | if (pt_size != | ||
282 | te->reader (te->cls, | ||
283 | te->publish_offset, | ||
284 | pt_size, | ||
285 | iob, | ||
286 | &te->emsg)) | ||
287 | { | ||
288 | GNUNET_SCHEDULER_add_continuation (te->h->sched, | ||
289 | GNUNET_NO, | ||
290 | te->cont, | ||
291 | te->cls, | ||
292 | GNUNET_SCHEDULER_REASON_TIMEOUT); | ||
293 | return; | ||
294 | } | ||
295 | pt_block = iob; | ||
296 | } | ||
297 | else | ||
298 | { | ||
299 | pt_size = compute_iblock_size (te->chk_tree_depth - te->current_depth, | ||
300 | te->publish_offset); | ||
301 | pt_block = &te->chk_tree[te->current_depth * | ||
302 | CHK_PER_INODE]; | ||
303 | } | ||
304 | off = compute_chk_offset (te->chk_tree_depth - te->current_depth, | ||
305 | te->publish_offset); | ||
306 | mychk = &te->chk_tree[(te->current_depth-1)*CHK_PER_INODE+off]; | ||
307 | GNUNET_CRYPTO_hash (pt_block, pt_size, &mychk->key); | ||
308 | GNUNET_CRYPTO_hash_to_aes_key (&mychk->key, &sk, &iv); | ||
309 | GNUNET_CRYPTO_aes_encrypt (pt_block, | ||
310 | pt_size, | ||
311 | &sk, | ||
312 | &iv, | ||
313 | enc); | ||
314 | if (NULL != te->proc) | ||
315 | te->proc (te->cls, | ||
316 | &mychk->query, | ||
317 | te->publish_offset, | ||
318 | pt_size, | ||
319 | enc, | ||
320 | (te->current_depth == te->chk_tree_depth) | ||
321 | ? GNUNET_DATASTORE_BLOCKTYPE_DBLOCK | ||
322 | : GNUNET_DATASTORE_BLOCKTYPE_IBLOCK); | ||
323 | if (NULL != te->progress) | ||
324 | te->progress (te->cls, | ||
325 | te->publish_offset, | ||
326 | pt_block, | ||
327 | pt_size, | ||
328 | te->current_depth); | ||
329 | GNUNET_CRYPTO_hash (enc, pt_size, &mychk->query); | ||
330 | if (te->current_depth == te->chk_tree_depth) | ||
331 | { | ||
332 | te->publish_offset += pt_size; | ||
333 | if ( (te->publish_offset == te->size) || | ||
334 | (0 == te->publish_offset % (CHK_PER_INODE * DBLOCK_SIZE) ) ) | ||
335 | te->current_depth--; | ||
336 | } | ||
337 | else | ||
338 | { | ||
339 | if ( (off == CHK_PER_INODE) || | ||
340 | (te->publish_offset == te->size) ) | ||
341 | te->current_depth--; | ||
342 | else | ||
343 | te->current_depth = te->chk_tree_depth; | ||
344 | } | ||
345 | if (0 == te->current_depth) | ||
346 | { | ||
347 | te->uri = GNUNET_malloc (sizeof(struct GNUNET_FS_Uri)); | ||
348 | te->uri->type = chk; | ||
349 | te->uri->data.chk.chk = te->chk_tree[0]; | ||
350 | te->uri->data.chk.file_length = te->size; | ||
351 | GNUNET_SCHEDULER_add_continuation (te->h->sched, | ||
352 | GNUNET_NO, | ||
353 | te->cont, | ||
354 | te->cls, | ||
355 | GNUNET_SCHEDULER_REASON_PREREQ_DONE); | ||
356 | } | ||
357 | } | ||
358 | |||
359 | |||
360 | /** | ||
361 | * Clean up a tree encoder and return information | ||
362 | * about the resulting URI or an error message. | ||
363 | * | ||
364 | * @param te the tree encoder to clean up | ||
365 | * @param uri set to the resulting URI (if encoding finished) | ||
366 | * @param emsg set to an error message (if an error occured | ||
367 | * within the tree encoder; if this function is called | ||
368 | * prior to completion and prior to an internal error, | ||
369 | * both "*uri" and "*emsg" will be set to NULL). | ||
370 | */ | ||
371 | void GNUNET_FS_tree_encoder_finish (struct GNUNET_FS_TreeEncoder * te, | ||
372 | struct GNUNET_FS_Uri **uri, | ||
373 | char **emsg) | ||
374 | { | ||
375 | *uri = te->uri; | ||
376 | *emsg = te->emsg; | ||
377 | GNUNET_free (te->chk_tree); | ||
378 | GNUNET_free (te); | ||
379 | } | ||
380 | |||
381 | /* end of fs_tree.c */ | ||