diff options
Diffstat (limited to 'src/cadet/gnunet-service-cadet-new_paths.c')
-rw-r--r-- | src/cadet/gnunet-service-cadet-new_paths.c | 240 |
1 files changed, 181 insertions, 59 deletions
diff --git a/src/cadet/gnunet-service-cadet-new_paths.c b/src/cadet/gnunet-service-cadet-new_paths.c index 005d8e807..96f32a87b 100644 --- a/src/cadet/gnunet-service-cadet-new_paths.c +++ b/src/cadet/gnunet-service-cadet-new_paths.c | |||
@@ -24,6 +24,10 @@ | |||
24 | * @brief Information we track per path. | 24 | * @brief Information we track per path. |
25 | * @author Bartlomiej Polot | 25 | * @author Bartlomiej Polot |
26 | * @author Christian Grothoff | 26 | * @author Christian Grothoff |
27 | * | ||
28 | * TODO: | ||
29 | * - path desirability score calculations are not done | ||
30 | * (and will be tricky to have during path changes) | ||
27 | */ | 31 | */ |
28 | #include "platform.h" | 32 | #include "platform.h" |
29 | #include "gnunet-service-cadet-new_peer.h" | 33 | #include "gnunet-service-cadet-new_peer.h" |
@@ -69,7 +73,6 @@ struct CadetPeerPath | |||
69 | }; | 73 | }; |
70 | 74 | ||
71 | 75 | ||
72 | |||
73 | /** | 76 | /** |
74 | * Return how much we like keeping the path. This is an aggregate | 77 | * Return how much we like keeping the path. This is an aggregate |
75 | * score based on various factors, including the age of the path | 78 | * score based on various factors, including the age of the path |
@@ -86,27 +89,7 @@ struct CadetPeerPath | |||
86 | GNUNET_CONTAINER_HeapCostType | 89 | GNUNET_CONTAINER_HeapCostType |
87 | GCPP_get_desirability (const struct CadetPeerPath *path) | 90 | GCPP_get_desirability (const struct CadetPeerPath *path) |
88 | { | 91 | { |
89 | GNUNET_break (0); | 92 | return path->desirability; |
90 | return 0; | ||
91 | } | ||
92 | |||
93 | |||
94 | /** | ||
95 | * The given peer @a cp used to own this @a path. However, it is no | ||
96 | * longer interested in maintaining it, so the path should be | ||
97 | * discarded or shortened (in case a previous peer on the path finds | ||
98 | * the path desirable). | ||
99 | * | ||
100 | * @param path the path that is being released | ||
101 | * @param node entry in the heap of @a cp where this path is anchored | ||
102 | * should be used for updates to the desirability of this path | ||
103 | */ | ||
104 | void | ||
105 | GCPP_acquire (struct CadetPeerPath *path, | ||
106 | struct GNUNET_CONTAINER_HeapNode *node) | ||
107 | { | ||
108 | GNUNET_assert (NULL == path->hn); | ||
109 | path->hn = node; | ||
110 | } | 93 | } |
111 | 94 | ||
112 | 95 | ||
@@ -226,7 +209,8 @@ GCPP_release (struct CadetPeerPath *path) | |||
226 | /* see if new peer at the end likes this path any better */ | 209 | /* see if new peer at the end likes this path any better */ |
227 | entry = &path->entries[path->entries_length - 1]; | 210 | entry = &path->entries[path->entries_length - 1]; |
228 | path->hn = GCP_attach_path (entry->peer, | 211 | path->hn = GCP_attach_path (entry->peer, |
229 | path); | 212 | path, |
213 | path->entries_length); | ||
230 | if (NULL != path->hn) | 214 | if (NULL != path->hn) |
231 | return; /* yep, got attached, we are done. */ | 215 | return; /* yep, got attached, we are done. */ |
232 | } | 216 | } |
@@ -275,17 +259,109 @@ GCPP_update_score (struct CadetPeerPath *path, | |||
275 | 259 | ||
276 | 260 | ||
277 | /** | 261 | /** |
278 | * Create a peer path based on the result of a DHT lookup. | 262 | * Closure for #find_peer_at() and #check_match(). |
279 | * If we already know this path, or one that is longer, | 263 | */ |
280 | * simply return NULL. | 264 | struct CheckMatchContext |
265 | { | ||
266 | |||
267 | /** | ||
268 | * Set to a matching path, if any. | ||
269 | */ | ||
270 | struct CadetPeerPath *match; | ||
271 | |||
272 | /** | ||
273 | * Array the combined paths. | ||
274 | */ | ||
275 | struct CadetPeer **cpath; | ||
276 | |||
277 | }; | ||
278 | |||
279 | |||
280 | /** | ||
281 | * Check if the given path is identical on all of the | ||
282 | * hops until @a off, and not longer than @a off. If the | ||
283 | * @a path matches, store it in `match`. | ||
281 | * | 284 | * |
282 | * FIXME: change API completely! | 285 | * @param cls the `struct CheckMatchContext` to check against |
283 | * Should in here create path transiently, then call | 286 | * @param path the path to check |
284 | * callback, and then do path destroy (if applicable) | 287 | * @param off offset to check at |
285 | * without returning in the middle. | 288 | * @return #GNUNET_YES (continue to iterate), or if found #GNUNET_NO |
289 | */ | ||
290 | static int | ||
291 | check_match (void *cls, | ||
292 | struct CadetPeerPath *path, | ||
293 | unsigned int off) | ||
294 | { | ||
295 | struct CheckMatchContext *cm_ctx = cls; | ||
296 | |||
297 | if (path->entries_length > off) | ||
298 | return GNUNET_YES; /* too long, cannot be useful */ | ||
299 | for (unsigned int i=0;i<off;i++) | ||
300 | if (cm_ctx->cpath[i] != | ||
301 | GCPP_get_peer_at_offset (path, | ||
302 | i)) | ||
303 | return GNUNET_YES; /* missmatch, ignore */ | ||
304 | cm_ctx->match = path; | ||
305 | return GNUNET_NO; /* match, we are done! */ | ||
306 | } | ||
307 | |||
308 | |||
309 | /** | ||
310 | * Extend path @a path by the @a num_peers from the @a peers | ||
311 | * array, assuming the owners past the current owner want it. | ||
286 | * | 312 | * |
287 | * FIXME: also need to nicely handle case that this path | 313 | * @param path path to extend |
288 | * extends (lengthens!) an existing path. | 314 | * @param peers list of peers beyond the end of @a path |
315 | * @param num_peers length of the @a peers array | ||
316 | */ | ||
317 | static void | ||
318 | extend_path (struct CadetPeerPath *path, | ||
319 | struct CadetPeer **peers, | ||
320 | unsigned int num_peers) | ||
321 | { | ||
322 | unsigned int old_len = path->entries_length; | ||
323 | struct GNUNET_CONTAINER_HeapNode *hn; | ||
324 | int i; | ||
325 | |||
326 | /* If we extend an existing path, detach it from the | ||
327 | old owner and re-attach to the new one */ | ||
328 | hn = NULL; | ||
329 | for (i=num_peers-1;i>=0;i--) | ||
330 | { | ||
331 | /* FIXME: note that path->desirability is used, but not yet updated here! */ | ||
332 | hn = GCP_attach_path (peers[i], | ||
333 | path, | ||
334 | old_len + (unsigned int) i); | ||
335 | if (NULL != hn) | ||
336 | break; | ||
337 | } | ||
338 | if (NULL == hn) | ||
339 | return; /* none of the peers is interested in this path */ | ||
340 | GCP_detach_path (path->entries[old_len-1].peer, | ||
341 | path, | ||
342 | path->hn); | ||
343 | path->hn = hn; | ||
344 | GNUNET_array_grow (path->entries, | ||
345 | path->entries_length, | ||
346 | old_len + i); | ||
347 | for (;i >= 0;i--) | ||
348 | { | ||
349 | struct CadetPeerPathEntry *entry = &path->entries[old_len + i]; | ||
350 | |||
351 | entry->peer = peers[i]; | ||
352 | entry->path = path; | ||
353 | GCP_path_entry_add (entry->peer, | ||
354 | entry, | ||
355 | old_len + i); | ||
356 | } | ||
357 | } | ||
358 | |||
359 | |||
360 | /** | ||
361 | * Create a peer path based on the result of a DHT lookup. If we | ||
362 | * already know this path, or one that is longer, simply return NULL. | ||
363 | * Otherwise, we try to extend an existing path, or create a new one | ||
364 | * if applicable. | ||
289 | * | 365 | * |
290 | * @param get_path path of the get request | 366 | * @param get_path path of the get request |
291 | * @param get_path_length lenght of @a get_path | 367 | * @param get_path_length lenght of @a get_path |
@@ -293,47 +369,93 @@ GCPP_update_score (struct CadetPeerPath *path, | |||
293 | * @param put_path_length length of the @a put_path | 369 | * @param put_path_length length of the @a put_path |
294 | * @return a path through the network | 370 | * @return a path through the network |
295 | */ | 371 | */ |
296 | struct CadetPeerPath * | 372 | void |
297 | GCPP_path_from_dht (const struct GNUNET_PeerIdentity *get_path, | 373 | GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path, |
298 | unsigned int get_path_length, | 374 | unsigned int get_path_length, |
299 | const struct GNUNET_PeerIdentity *put_path, | 375 | const struct GNUNET_PeerIdentity *put_path, |
300 | unsigned int put_path_length) | 376 | unsigned int put_path_length) |
301 | { | 377 | { |
378 | struct CheckMatchContext cm_ctx; | ||
379 | struct CadetPeer *cpath[get_path_length + put_path_length]; | ||
302 | struct CadetPeerPath *path; | 380 | struct CadetPeerPath *path; |
381 | struct GNUNET_CONTAINER_HeapNode *hn; | ||
382 | int i; | ||
383 | |||
384 | /* precompute 'cpath' so we can avoid doing the lookups lots of times */ | ||
385 | for (unsigned int off=0;off<get_path_length + put_path_length;off++) | ||
386 | { | ||
387 | const struct GNUNET_PeerIdentity *pid; | ||
388 | |||
389 | pid = (off < get_path_length) | ||
390 | ? &get_path[get_path_length - off] | ||
391 | : &put_path[get_path_length + put_path_length - off]; | ||
392 | cpath[off] = GCP_get (pid, | ||
393 | GNUNET_YES); | ||
394 | } | ||
303 | 395 | ||
396 | /* First figure out if this path is a subset of an existing path, an | ||
397 | extension of an existing path, or a new path. */ | ||
398 | cm_ctx.cpath = cpath; | ||
399 | cm_ctx.match = NULL; | ||
400 | for (i=get_path_length + put_path_length-1;i>=0;i--) | ||
401 | { | ||
402 | GCP_iterate_paths_at (cpath[i], | ||
403 | (unsigned int) i, | ||
404 | &check_match, | ||
405 | &cm_ctx); | ||
406 | if (NULL != cm_ctx.match) | ||
407 | { | ||
408 | if (i == get_path_length + put_path_length - 1) | ||
409 | { | ||
410 | /* Existing path includes this one, nothing to do! */ | ||
411 | return; | ||
412 | } | ||
413 | if (cm_ctx.match->entries_length == i + 1) | ||
414 | { | ||
415 | /* Existing path ends in the middle of new path, extend it! */ | ||
416 | extend_path (cm_ctx.match, | ||
417 | &cpath[i], | ||
418 | get_path_length + put_path_length - i); | ||
419 | return; | ||
420 | } | ||
421 | } | ||
422 | } | ||
423 | |||
424 | /* No match at all, create completely new path */ | ||
304 | path = GNUNET_new (struct CadetPeerPath); | 425 | path = GNUNET_new (struct CadetPeerPath); |
305 | path->entries_length = get_path_length + put_path_length; | 426 | |
427 | /* First, try to attach it */ | ||
428 | hn = NULL; | ||
429 | for (i=get_path_length + put_path_length-1;i>=0;i--) | ||
430 | { | ||
431 | path->entries_length = i; | ||
432 | /* FIXME: note that path->desirability is used, but not yet initialized here! */ | ||
433 | hn = GCP_attach_path (cpath[i], | ||
434 | path, | ||
435 | (unsigned int) i); | ||
436 | if (NULL != hn) | ||
437 | break; | ||
438 | } | ||
439 | if (NULL == hn) | ||
440 | { | ||
441 | /* None of the peers on the path care about it. */ | ||
442 | GNUNET_free (path); | ||
443 | return; | ||
444 | } | ||
445 | path->hn = hn; | ||
446 | path->entries_length = i; | ||
306 | path->entries = GNUNET_new_array (path->entries_length, | 447 | path->entries = GNUNET_new_array (path->entries_length, |
307 | struct CadetPeerPathEntry); | 448 | struct CadetPeerPathEntry); |
308 | for (unsigned int i=0;i<get_path_length + put_path_length;i++) | 449 | for (;i>=0;i--) |
309 | { | 450 | { |
310 | struct CadetPeerPathEntry *entry = &path->entries[i]; | 451 | struct CadetPeerPathEntry *entry = &path->entries[i]; |
311 | const struct GNUNET_PeerIdentity *pid; | ||
312 | 452 | ||
313 | pid = (i < get_path_length) ? &get_path[get_path_length - i] : &put_path[path->entries_length - i]; | 453 | entry->peer = cpath[i]; |
314 | entry->peer = GCP_get (pid, | ||
315 | GNUNET_YES); | ||
316 | entry->path = path; | 454 | entry->path = path; |
317 | GCP_path_entry_add (entry->peer, | 455 | GCP_path_entry_add (entry->peer, |
318 | entry, | 456 | entry, |
319 | i); | 457 | i); |
320 | } | 458 | } |
321 | GNUNET_break (0); | ||
322 | return NULL; | ||
323 | } | ||
324 | |||
325 | |||
326 | /** | ||
327 | * Destroy a path, we no longer need it. | ||
328 | * | ||
329 | * @param p path to destroy. | ||
330 | */ | ||
331 | void | ||
332 | GCPP_path_destroy (struct CadetPeerPath *path) | ||
333 | { | ||
334 | if (NULL != path->hn) | ||
335 | return; /* path was attached, to be kept! */ | ||
336 | path_destroy (path); | ||
337 | } | 459 | } |
338 | 460 | ||
339 | 461 | ||