summaryrefslogtreecommitdiff
path: root/src/cadet/gnunet-service-cadet_paths.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/cadet/gnunet-service-cadet_paths.c')
-rw-r--r--src/cadet/gnunet-service-cadet_paths.c748
1 files changed, 372 insertions, 376 deletions
diff --git a/src/cadet/gnunet-service-cadet_paths.c b/src/cadet/gnunet-service-cadet_paths.c
index bdc92668e..149ac659a 100644
--- a/src/cadet/gnunet-service-cadet_paths.c
+++ b/src/cadet/gnunet-service-cadet_paths.c
@@ -11,15 +11,15 @@
11 WITHOUT ANY WARRANTY; without even the implied warranty of 11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details. 13 Affero General Public License for more details.
14 14
15 You should have received a copy of the GNU Affero General Public License 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/>. 16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17 17
18 SPDX-License-Identifier: AGPL3.0-or-later 18 SPDX-License-Identifier: AGPL3.0-or-later
19*/ 19 */
20/** 20/**
21 * @file cadet/gnunet-service-cadet_paths.c 21 * @file cadet/gnunet-service-cadet_paths.c
22 * @brief Information we track per path. 22 * @brief Information we track per path.
23 * @author Bartlomiej Polot 23 * @author Bartlomiej Polot
24 * @author Christian Grothoff 24 * @author Christian Grothoff
25 */ 25 */
@@ -30,15 +30,13 @@
30#include "gnunet-service-cadet_paths.h" 30#include "gnunet-service-cadet_paths.h"
31 31
32 32
33#define LOG(level, ...) GNUNET_log_from(level,"cadet-pat",__VA_ARGS__) 33#define LOG(level, ...) GNUNET_log_from(level, "cadet-pat", __VA_ARGS__)
34 34
35 35
36/** 36/**
37 * Information regarding a possible path to reach a peer. 37 * Information regarding a possible path to reach a peer.
38 */ 38 */
39struct CadetPeerPath 39struct CadetPeerPath {
40{
41
42 /** 40 /**
43 * Array of all the peers on the path. If @e hn is non-NULL, the 41 * Array of all the peers on the path. If @e hn is non-NULL, the
44 * last one is our owner. 42 * last one is our owner.
@@ -61,7 +59,6 @@ struct CadetPeerPath
61 * Length of the @e entries array. 59 * Length of the @e entries array.
62 */ 60 */
63 unsigned int entries_length; 61 unsigned int entries_length;
64
65}; 62};
66 63
67 64
@@ -71,18 +68,18 @@ struct CadetPeerPath
71 * @param path path to calculate the score for 68 * @param path path to calculate the score for
72 */ 69 */
73static void 70static void
74recalculate_path_desirability (struct CadetPeerPath *path) 71recalculate_path_desirability(struct CadetPeerPath *path)
75{ 72{
76 double result = 0.0; 73 double result = 0.0;
77 74
78 for (unsigned int i=0;i<path->entries_length;i++) 75 for (unsigned int i = 0; i < path->entries_length; i++)
79 { 76 {
80 struct CadetPeer *cp = path->entries[i]->peer; 77 struct CadetPeer *cp = path->entries[i]->peer;
81 78
82 result += GCP_get_desirability_of_path (cp, 79 result += GCP_get_desirability_of_path(cp,
83 i); 80 i);
84 } 81 }
85 path->desirability = (GNUNET_CONTAINER_HeapCostType) result; 82 path->desirability = (GNUNET_CONTAINER_HeapCostType)result;
86} 83}
87 84
88 85
@@ -100,7 +97,7 @@ recalculate_path_desirability (struct CadetPeerPath *path)
100 * @return desirability of the path, larger is more desirable 97 * @return desirability of the path, larger is more desirable
101 */ 98 */
102GNUNET_CONTAINER_HeapCostType 99GNUNET_CONTAINER_HeapCostType
103GCPP_get_desirability (const struct CadetPeerPath *path) 100GCPP_get_desirability(const struct CadetPeerPath *path)
104{ 101{
105 return path->desirability; 102 return path->desirability;
106} 103}
@@ -117,15 +114,15 @@ GCPP_get_desirability (const struct CadetPeerPath *path)
117 * otherwise connection from us to @a destination via @a path 114 * otherwise connection from us to @a destination via @a path
118 */ 115 */
119struct CadetConnection * 116struct CadetConnection *
120GCPP_get_connection (struct CadetPeerPath *path, 117GCPP_get_connection(struct CadetPeerPath *path,
121 struct CadetPeer *destination, 118 struct CadetPeer *destination,
122 unsigned int off) 119 unsigned int off)
123{ 120{
124 struct CadetPeerPathEntry *entry; 121 struct CadetPeerPathEntry *entry;
125 122
126 GNUNET_assert (off < path->entries_length); 123 GNUNET_assert(off < path->entries_length);
127 entry = path->entries[off]; 124 entry = path->entries[off];
128 GNUNET_assert (entry->peer == destination); 125 GNUNET_assert(entry->peer == destination);
129 return entry->cc; 126 return entry->cc;
130} 127}
131 128
@@ -139,21 +136,21 @@ GCPP_get_connection (struct CadetPeerPath *path,
139 * @param cc the connection to remember 136 * @param cc the connection to remember
140 */ 137 */
141void 138void
142GCPP_add_connection (struct CadetPeerPath *path, 139GCPP_add_connection(struct CadetPeerPath *path,
143 unsigned int off, 140 unsigned int off,
144 struct CadetConnection *cc) 141 struct CadetConnection *cc)
145{ 142{
146 struct CadetPeerPathEntry *entry; 143 struct CadetPeerPathEntry *entry;
147 144
148 LOG (GNUNET_ERROR_TYPE_DEBUG, 145 LOG(GNUNET_ERROR_TYPE_DEBUG,
149 "Adding %s to path %s at offset %u\n", 146 "Adding %s to path %s at offset %u\n",
150 GCC_2s (cc), 147 GCC_2s(cc),
151 GCPP_2s (path), 148 GCPP_2s(path),
152 off); 149 off);
153 GNUNET_assert (off < path->entries_length); 150 GNUNET_assert(off < path->entries_length);
154 entry = path->entries[off]; 151 entry = path->entries[off];
155 GNUNET_assert (NULL == entry->cc); 152 GNUNET_assert(NULL == entry->cc);
156 GNUNET_assert (NULL != cc); 153 GNUNET_assert(NULL != cc);
157 entry->cc = cc; 154 entry->cc = cc;
158} 155}
159 156
@@ -168,20 +165,20 @@ GCPP_add_connection (struct CadetPeerPath *path,
168 * @param cc the connection to forget 165 * @param cc the connection to forget
169 */ 166 */
170void 167void
171GCPP_del_connection (struct CadetPeerPath *path, 168GCPP_del_connection(struct CadetPeerPath *path,
172 unsigned int off, 169 unsigned int off,
173 struct CadetConnection *cc) 170 struct CadetConnection *cc)
174{ 171{
175 struct CadetPeerPathEntry *entry; 172 struct CadetPeerPathEntry *entry;
176 173
177 LOG (GNUNET_ERROR_TYPE_DEBUG, 174 LOG(GNUNET_ERROR_TYPE_DEBUG,
178 "Removing connection %s to path %s at offset %u\n", 175 "Removing connection %s to path %s at offset %u\n",
179 GCC_2s (cc), 176 GCC_2s(cc),
180 GCPP_2s (path), 177 GCPP_2s(path),
181 off); 178 off);
182 GNUNET_assert (off < path->entries_length); 179 GNUNET_assert(off < path->entries_length);
183 entry = path->entries[off]; 180 entry = path->entries[off];
184 GNUNET_assert (cc == entry->cc); 181 GNUNET_assert(cc == entry->cc);
185 entry->cc = NULL; 182 entry->cc = NULL;
186} 183}
187 184
@@ -196,42 +193,42 @@ GCPP_del_connection (struct CadetPeerPath *path,
196 * @param stop_at the path length at which to stop trying 193 * @param stop_at the path length at which to stop trying
197 */ 194 */
198static void 195static void
199attach_path (struct CadetPeerPath *path, unsigned int stop_at) 196attach_path(struct CadetPeerPath *path, unsigned int stop_at)
200{ 197{
201 GNUNET_assert (NULL == path->hn); 198 GNUNET_assert(NULL == path->hn);
202 199
203 /* Try to attach this path to a peer, working backwards from the end. */ 200 /* Try to attach this path to a peer, working backwards from the end. */
204 while (path->entries_length > stop_at) 201 while (path->entries_length > stop_at)
205 { 202 {
206 unsigned int end = path->entries_length - 1; 203 unsigned int end = path->entries_length - 1;
207 struct CadetPeerPathEntry *entry = path->entries[end]; 204 struct CadetPeerPathEntry *entry = path->entries[end];
208 int force = GNUNET_NO; 205 int force = GNUNET_NO;
209 206
210 recalculate_path_desirability (path); 207 recalculate_path_desirability(path);
211 /* If the entry already has a connection using it, force attach. */ 208 /* If the entry already has a connection using it, force attach. */
212 if (NULL != entry->cc) 209 if (NULL != entry->cc)
213 force = GNUNET_YES; 210 force = GNUNET_YES;
214 path->hn = GCP_attach_path (entry->peer, 211 path->hn = GCP_attach_path(entry->peer,
215 path, 212 path,
216 end, 213 end,
217 force); 214 force);
218 if (NULL != path->hn) 215 if (NULL != path->hn)
219 break; 216 break;
220 217
221 /* Attach failed, trim this entry from the path. */ 218 /* Attach failed, trim this entry from the path. */
222 GNUNET_assert (NULL == entry->cc); 219 GNUNET_assert(NULL == entry->cc);
223 GCP_path_entry_remove (entry->peer, 220 GCP_path_entry_remove(entry->peer,
224 entry, 221 entry,
225 end); 222 end);
226 GNUNET_free (entry); 223 GNUNET_free(entry);
227 path->entries[end] = NULL; 224 path->entries[end] = NULL;
228 path->entries_length--; 225 path->entries_length--;
229 } 226 }
230 227
231 /* Shrink array to actual path length. */ 228 /* Shrink array to actual path length. */
232 GNUNET_array_grow (path->entries, 229 GNUNET_array_grow(path->entries,
233 path->entries_length, 230 path->entries_length,
234 path->entries_length); 231 path->entries_length);
235} 232}
236 233
237 234
@@ -243,33 +240,33 @@ attach_path (struct CadetPeerPath *path, unsigned int stop_at)
243 * @param path the path that is being released 240 * @param path the path that is being released
244 */ 241 */
245void 242void
246GCPP_release (struct CadetPeerPath *path) 243GCPP_release(struct CadetPeerPath *path)
247{ 244{
248 struct CadetPeerPathEntry *entry; 245 struct CadetPeerPathEntry *entry;
249 246
250 LOG (GNUNET_ERROR_TYPE_DEBUG, 247 LOG(GNUNET_ERROR_TYPE_DEBUG,
251 "Owner releases path %s\n", 248 "Owner releases path %s\n",
252 GCPP_2s (path)); 249 GCPP_2s(path));
253 path->hn = NULL; 250 path->hn = NULL;
254 entry = path->entries[path->entries_length - 1]; 251 entry = path->entries[path->entries_length - 1];
255 GNUNET_assert (path == entry->path); 252 GNUNET_assert(path == entry->path);
256 GNUNET_assert (NULL == entry->cc); 253 GNUNET_assert(NULL == entry->cc);
257 /* cut 'off' end of path */ 254 /* cut 'off' end of path */
258 GCP_path_entry_remove (entry->peer, 255 GCP_path_entry_remove(entry->peer,
259 entry, 256 entry,
260 path->entries_length - 1); 257 path->entries_length - 1);
261 GNUNET_free (entry); 258 GNUNET_free(entry);
262 path->entries[path->entries_length - 1] = NULL; 259 path->entries[path->entries_length - 1] = NULL;
263 path->entries_length--; 260 path->entries_length--;
264 /* see if new peer at the end likes this path any better */ 261 /* see if new peer at the end likes this path any better */
265 attach_path (path, 0); 262 attach_path(path, 0);
266 if (NULL == path->hn) 263 if (NULL == path->hn)
267 { 264 {
268 /* nobody wants us, discard the path */ 265 /* nobody wants us, discard the path */
269 GNUNET_assert (0 == path->entries_length); 266 GNUNET_assert(0 == path->entries_length);
270 GNUNET_assert (NULL == path->entries); 267 GNUNET_assert(NULL == path->entries);
271 GNUNET_free (path); 268 GNUNET_free(path);
272 } 269 }
273} 270}
274 271
275 272
@@ -282,40 +279,38 @@ GCPP_release (struct CadetPeerPath *path)
282 * @param delta change in the score to apply 279 * @param delta change in the score to apply
283 */ 280 */
284void 281void
285GCPP_update_score (struct CadetPeerPath *path, 282GCPP_update_score(struct CadetPeerPath *path,
286 unsigned int off, 283 unsigned int off,
287 int delta) 284 int delta)
288{ 285{
289 struct CadetPeerPathEntry *entry; 286 struct CadetPeerPathEntry *entry;
290 287
291 GNUNET_assert (off < path->entries_length); 288 GNUNET_assert(off < path->entries_length);
292 entry = path->entries[off]; 289 entry = path->entries[off];
293 290
294 /* Add delta, with checks for overflows */ 291 /* Add delta, with checks for overflows */
295 if (delta >= 0) 292 if (delta >= 0)
296 { 293 {
297 if (delta + entry->score < entry->score) 294 if (delta + entry->score < entry->score)
298 entry->score = INT_MAX; 295 entry->score = INT_MAX;
299 else 296 else
300 entry->score += delta; 297 entry->score += delta;
301 } 298 }
302 else 299 else
303 { 300 {
304 if (delta + entry->score > entry->score) 301 if (delta + entry->score > entry->score)
305 entry->score = INT_MIN; 302 entry->score = INT_MIN;
306 else 303 else
307 entry->score += delta; 304 entry->score += delta;
308 } 305 }
309 recalculate_path_desirability (path); 306 recalculate_path_desirability(path);
310} 307}
311 308
312 309
313/** 310/**
314 * Closure for #find_peer_at() and #check_match(). 311 * Closure for #find_peer_at() and #check_match().
315 */ 312 */
316struct CheckMatchContext 313struct CheckMatchContext {
317{
318
319 /** 314 /**
320 * Set to a matching path, if any. 315 * Set to a matching path, if any.
321 */ 316 */
@@ -330,7 +325,6 @@ struct CheckMatchContext
330 * How long is the @e cpath array? 325 * How long is the @e cpath array?
331 */ 326 */
332 unsigned int cpath_length; 327 unsigned int cpath_length;
333
334}; 328};
335 329
336 330
@@ -345,38 +339,38 @@ struct CheckMatchContext
345 * @return #GNUNET_YES (continue to iterate), or if found #GNUNET_NO 339 * @return #GNUNET_YES (continue to iterate), or if found #GNUNET_NO
346 */ 340 */
347static int 341static int
348check_match (void *cls, 342check_match(void *cls,
349 struct CadetPeerPath *path, 343 struct CadetPeerPath *path,
350 unsigned int off) 344 unsigned int off)
351{ 345{
352 struct CheckMatchContext *cm_ctx = cls; 346 struct CheckMatchContext *cm_ctx = cls;
353 347
354 GNUNET_assert (path->entries_length > off); 348 GNUNET_assert(path->entries_length > off);
355 if ( (path->entries_length != off + 1) && 349 if ((path->entries_length != off + 1) &&
356 (off + 1 != cm_ctx->cpath_length) ) 350 (off + 1 != cm_ctx->cpath_length))
357 {
358 LOG (GNUNET_ERROR_TYPE_DEBUG,
359 "check_match mismatch because path %s is too long (%u vs. %u vs. %u)\n",
360 GCPP_2s (path),
361 path->entries_length,
362 off + 1,
363 cm_ctx->cpath_length);
364 return GNUNET_YES; /* too long, goes somewhere else already, thus cannot be useful */
365 }
366 for (unsigned int i=0;i<off;i++)
367 if (cm_ctx->cpath[i] !=
368 GCPP_get_peer_at_offset (path,
369 i))
370 { 351 {
371 LOG (GNUNET_ERROR_TYPE_DEBUG, 352 LOG(GNUNET_ERROR_TYPE_DEBUG,
372 "check_match path %s mismatches at offset %u\n", 353 "check_match mismatch because path %s is too long (%u vs. %u vs. %u)\n",
373 GCPP_2s (path), 354 GCPP_2s(path),
374 i); 355 path->entries_length,
375 return GNUNET_YES; /* mismatch, ignore */ 356 off + 1,
357 cm_ctx->cpath_length);
358 return GNUNET_YES; /* too long, goes somewhere else already, thus cannot be useful */
376 } 359 }
377 LOG (GNUNET_ERROR_TYPE_DEBUG, 360 for (unsigned int i = 0; i < off; i++)
378 "check_match found match with path %s\n", 361 if (cm_ctx->cpath[i] !=
379 GCPP_2s (path)); 362 GCPP_get_peer_at_offset(path,
363 i))
364 {
365 LOG(GNUNET_ERROR_TYPE_DEBUG,
366 "check_match path %s mismatches at offset %u\n",
367 GCPP_2s(path),
368 i);
369 return GNUNET_YES; /* mismatch, ignore */
370 }
371 LOG(GNUNET_ERROR_TYPE_DEBUG,
372 "check_match found match with path %s\n",
373 GCPP_2s(path));
380 cm_ctx->match = path; 374 cm_ctx->match = path;
381 return GNUNET_NO; /* match, we are done! */ 375 return GNUNET_NO; /* match, we are done! */
382} 376}
@@ -393,68 +387,70 @@ check_match (void *cls,
393 * paths already 387 * paths already
394 */ 388 */
395static void 389static void
396extend_path (struct CadetPeerPath *path, 390extend_path(struct CadetPeerPath *path,
397 struct CadetPeer **peers, 391 struct CadetPeer **peers,
398 unsigned int num_peers, 392 unsigned int num_peers,
399 int force) 393 int force)
400{ 394{
401 unsigned int old_len = path->entries_length; 395 unsigned int old_len = path->entries_length;
402 int i; 396 int i;
403 397
404 /* Expand path */ 398 /* Expand path */
405 GNUNET_array_grow (path->entries, 399 GNUNET_array_grow(path->entries,
406 path->entries_length, 400 path->entries_length,
407 old_len + num_peers); 401 old_len + num_peers);
408 for (i=num_peers-1;i >= 0;i--) 402 for (i = num_peers - 1; i >= 0; i--)
409 { 403 {
410 struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry); 404 struct CadetPeerPathEntry *entry = GNUNET_new(struct CadetPeerPathEntry);
411 405
412 path->entries[old_len + i] = entry; 406 path->entries[old_len + i] = entry;
413 entry->peer = peers[i]; 407 entry->peer = peers[i];
414 entry->path = path; 408 entry->path = path;
415 } 409 }
416 for (i=num_peers-1;i >= 0;i--) 410 for (i = num_peers - 1; i >= 0; i--)
417 { 411 {
418 struct CadetPeerPathEntry *entry = path->entries[old_len + i]; 412 struct CadetPeerPathEntry *entry = path->entries[old_len + i];
419 413
420 GCP_path_entry_add (entry->peer, 414 GCP_path_entry_add(entry->peer,
421 entry, 415 entry,
422 old_len + i); 416 old_len + i);
423 } 417 }
424 418
425 /* If we extend an existing path, detach it from the 419 /* If we extend an existing path, detach it from the
426 old owner and re-attach to the new one */ 420 old owner and re-attach to the new one */
427 GCP_detach_path (path->entries[old_len-1]->peer, 421 GCP_detach_path(path->entries[old_len - 1]->peer,
428 path, 422 path,
429 path->hn); 423 path->hn);
430 path->hn = NULL; 424 path->hn = NULL;
431 path->entries_length = old_len + num_peers; 425 path->entries_length = old_len + num_peers;
432 if (GNUNET_YES == force) 426 if (GNUNET_YES == force)
433 { 427 {
434 int end = path->entries_length - 1; 428 int end = path->entries_length - 1;
435 429
436 path->hn = GCP_attach_path (path->entries[end]->peer, 430 path->hn = GCP_attach_path(path->entries[end]->peer,
437 path, 431 path,
438 end, 432 end,
439 GNUNET_YES); 433 GNUNET_YES);
440 } else { 434 }
441 attach_path (path, old_len); 435 else
442 } 436 {
437 attach_path(path, old_len);
438 }
443 if (NULL == path->hn) 439 if (NULL == path->hn)
444 { 440 {
445 /* none of the peers is interested in this path; 441 /* none of the peers is interested in this path;
446 re-attach. */ 442 re-attach. */
447 GNUNET_assert (old_len == path->entries_length); 443 GNUNET_assert(old_len == path->entries_length);
448 path->hn = GCP_attach_path (path->entries[old_len - 1]->peer, 444 path->hn = GCP_attach_path(path->entries[old_len - 1]->peer,
449 path, 445 path,
450 old_len - 1, 446 old_len - 1,
451 GNUNET_YES); 447 GNUNET_YES);
452 GNUNET_assert (NULL != path->hn); 448 GNUNET_assert(NULL != path->hn);
453 return; 449 return;
454 } 450 }
455 LOG (GNUNET_ERROR_TYPE_DEBUG, 451 LOG(GNUNET_ERROR_TYPE_DEBUG,
456 "Extended path %s\n", 452 "Extended path %s\n",
457 GCPP_2s (path)); 453 GCPP_2s(path));
458} 454}
459 455
460 456
@@ -471,10 +467,10 @@ extend_path (struct CadetPeerPath *path,
471 * @return a path through the network 467 * @return a path through the network
472 */ 468 */
473void 469void
474GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path, 470GCPP_try_path_from_dht(const struct GNUNET_PeerIdentity *get_path,
475 unsigned int get_path_length, 471 unsigned int get_path_length,
476 const struct GNUNET_PeerIdentity *put_path, 472 const struct GNUNET_PeerIdentity *put_path,
477 unsigned int put_path_length) 473 unsigned int put_path_length)
478{ 474{
479 struct CadetPeer *cpath[get_path_length + put_path_length]; 475 struct CadetPeer *cpath[get_path_length + put_path_length];
480 struct CheckMatchContext cm_ctx; 476 struct CheckMatchContext cm_ctx;
@@ -484,42 +480,42 @@ GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path,
484 480
485 /* precompute 'cpath' so we can avoid doing the lookups lots of times */ 481 /* precompute 'cpath' so we can avoid doing the lookups lots of times */
486 skip = 0; 482 skip = 0;
487 memset (cpath, 483 memset(cpath,
488 0, 484 0,
489 sizeof (cpath)); /* Just to trigger harder errors later. */ 485 sizeof(cpath)); /* Just to trigger harder errors later. */
490 total_len = get_path_length + put_path_length; 486 total_len = get_path_length + put_path_length;
491 for (unsigned int off=0;off<total_len;off++) 487 for (unsigned int off = 0; off < total_len; off++)
492 {
493 const struct GNUNET_PeerIdentity *pid;
494
495 pid = (off < get_path_length)
496 ? &get_path[get_path_length - off - 1]
497 : &put_path[get_path_length + put_path_length - off - 1];
498 /* Check that I am not in the path */
499 if (0 == GNUNET_memcmp (&my_full_id,
500 pid))
501 { 488 {
502 skip = off + 1; 489 const struct GNUNET_PeerIdentity *pid;
503 continue; 490
491 pid = (off < get_path_length)
492 ? &get_path[get_path_length - off - 1]
493 : &put_path[get_path_length + put_path_length - off - 1];
494 /* Check that I am not in the path */
495 if (0 == GNUNET_memcmp(&my_full_id,
496 pid))
497 {
498 skip = off + 1;
499 continue;
500 }
501 cpath[off - skip] = GCP_get(pid,
502 GNUNET_YES);
503 /* Check that no peer is twice on the path */
504 for (unsigned int i = 0; i < off - skip; i++)
505 {
506 if (cpath[i] == cpath[off - skip])
507 {
508 skip = off - i;
509 break;
510 }
511 }
504 } 512 }
505 cpath[off - skip] = GCP_get (pid, 513 if (skip >= total_len)
506 GNUNET_YES);
507 /* Check that no peer is twice on the path */
508 for (unsigned int i=0;i<off - skip;i++)
509 { 514 {
510 if (cpath[i] == cpath[off - skip]) 515 LOG(GNUNET_ERROR_TYPE_DEBUG,
511 { 516 "Path discovered from DHT is one big cycle?\n");
512 skip = off - i; 517 return;
513 break;
514 }
515 } 518 }
516 }
517 if (skip >= total_len)
518 {
519 LOG (GNUNET_ERROR_TYPE_DEBUG,
520 "Path discovered from DHT is one big cycle?\n");
521 return;
522 }
523 total_len -= skip; 519 total_len -= skip;
524 520
525 /* First figure out if this path is a subset of an existing path, an 521 /* First figure out if this path is a subset of an existing path, an
@@ -527,73 +523,73 @@ GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path,
527 cm_ctx.cpath_length = total_len; 523 cm_ctx.cpath_length = total_len;
528 cm_ctx.cpath = cpath; 524 cm_ctx.cpath = cpath;
529 cm_ctx.match = NULL; 525 cm_ctx.match = NULL;
530 for (int i=total_len-1;i>=0;i--) 526 for (int i = total_len - 1; i >= 0; i--)
531 {
532 GCP_iterate_paths_at (cpath[i],
533 (unsigned int) i,
534 &check_match,
535 &cm_ctx);
536 if (NULL != cm_ctx.match)
537 { 527 {
538 if (i == total_len - 1) 528 GCP_iterate_paths_at(cpath[i],
539 { 529 (unsigned int)i,
540 /* Existing path includes this one, nothing to do! */ 530 &check_match,
541 LOG (GNUNET_ERROR_TYPE_DEBUG, 531 &cm_ctx);
542 "Path discovered from DHT is already known\n"); 532 if (NULL != cm_ctx.match)
543 return; 533 {
544 } 534 if (i == total_len - 1)
545 if (cm_ctx.match->entries_length == i + 1) 535 {
546 { 536 /* Existing path includes this one, nothing to do! */
547 /* Existing path ends in the middle of new path, extend it! */ 537 LOG(GNUNET_ERROR_TYPE_DEBUG,
548 LOG (GNUNET_ERROR_TYPE_DEBUG, 538 "Path discovered from DHT is already known\n");
549 "Trying to extend existing path %s by additional links discovered from DHT\n", 539 return;
550 GCPP_2s (cm_ctx.match)); 540 }
551 extend_path (cm_ctx.match, 541 if (cm_ctx.match->entries_length == i + 1)
552 &cpath[i + 1], 542 {
553 total_len - i - 1, 543 /* Existing path ends in the middle of new path, extend it! */
554 GNUNET_NO); 544 LOG(GNUNET_ERROR_TYPE_DEBUG,
555 return; 545 "Trying to extend existing path %s by additional links discovered from DHT\n",
556 } 546 GCPP_2s(cm_ctx.match));
547 extend_path(cm_ctx.match,
548 &cpath[i + 1],
549 total_len - i - 1,
550 GNUNET_NO);
551 return;
552 }
553 }
557 } 554 }
558 }
559 555
560 /* No match at all, create completely new path */ 556 /* No match at all, create completely new path */
561 path = GNUNET_new (struct CadetPeerPath); 557 path = GNUNET_new(struct CadetPeerPath);
562 path->entries_length = total_len; 558 path->entries_length = total_len;
563 path->entries = GNUNET_new_array (path->entries_length, 559 path->entries = GNUNET_new_array(path->entries_length,
564 struct CadetPeerPathEntry *); 560 struct CadetPeerPathEntry *);
565 for (int i=path->entries_length-1;i>=0;i--) 561 for (int i = path->entries_length - 1; i >= 0; i--)
566 { 562 {
567 struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry); 563 struct CadetPeerPathEntry *entry = GNUNET_new(struct CadetPeerPathEntry);
568 564
569 path->entries[i] = entry; 565 path->entries[i] = entry;
570 entry->peer = cpath[i]; 566 entry->peer = cpath[i];
571 entry->path = path; 567 entry->path = path;
572 } 568 }
573 for (int i=path->entries_length-1;i>=0;i--) 569 for (int i = path->entries_length - 1; i >= 0; i--)
574 { 570 {
575 struct CadetPeerPathEntry *entry = path->entries[i]; 571 struct CadetPeerPathEntry *entry = path->entries[i];
576 572
577 GCP_path_entry_add (entry->peer, 573 GCP_path_entry_add(entry->peer,
578 entry, 574 entry,
579 i); 575 i);
580 } 576 }
581 577
582 /* Finally, try to attach it */ 578 /* Finally, try to attach it */
583 attach_path (path, 0); 579 attach_path(path, 0);
584 if (NULL == path->hn) 580 if (NULL == path->hn)
585 { 581 {
586 /* None of the peers on the path care about it. */ 582 /* None of the peers on the path care about it. */
587 LOG (GNUNET_ERROR_TYPE_DEBUG, 583 LOG(GNUNET_ERROR_TYPE_DEBUG,
588 "Path discovered from DHT is not interesting to us\n"); 584 "Path discovered from DHT is not interesting to us\n");
589 GNUNET_assert (0 == path->entries_length); 585 GNUNET_assert(0 == path->entries_length);
590 GNUNET_assert (NULL == path->entries); 586 GNUNET_assert(NULL == path->entries);
591 GNUNET_free (path); 587 GNUNET_free(path);
592 return; 588 return;
593 } 589 }
594 LOG (GNUNET_ERROR_TYPE_DEBUG, 590 LOG(GNUNET_ERROR_TYPE_DEBUG,
595 "Created new path %s based on information from DHT\n", 591 "Created new path %s based on information from DHT\n",
596 GCPP_2s (path)); 592 GCPP_2s(path));
597} 593}
598 594
599 595
@@ -605,8 +601,8 @@ GCPP_try_path_from_dht (const struct GNUNET_PeerIdentity *get_path,
605 * @return corresponding path object 601 * @return corresponding path object
606 */ 602 */
607struct CadetPeerPath * 603struct CadetPeerPath *
608GCPP_get_path_from_route (unsigned int path_length, 604GCPP_get_path_from_route(unsigned int path_length,
609 const struct GNUNET_PeerIdentity *pids) 605 const struct GNUNET_PeerIdentity *pids)
610{ 606{
611 struct CheckMatchContext cm_ctx; 607 struct CheckMatchContext cm_ctx;
612 struct CadetPeer *cpath[path_length]; 608 struct CadetPeer *cpath[path_length];
@@ -614,79 +610,79 @@ GCPP_get_path_from_route (unsigned int path_length,
614 610
615 /* precompute inverted 'cpath' so we can avoid doing the lookups and 611 /* precompute inverted 'cpath' so we can avoid doing the lookups and
616 have the correct order */ 612 have the correct order */
617 for (unsigned int off=0;off<path_length;off++) 613 for (unsigned int off = 0; off < path_length; off++)
618 cpath[off] = GCP_get (&pids[path_length - 1 - off], 614 cpath[off] = GCP_get(&pids[path_length - 1 - off],
619 GNUNET_YES); 615 GNUNET_YES);
620 616
621 /* First figure out if this path is a subset of an existing path, an 617 /* First figure out if this path is a subset of an existing path, an
622 extension of an existing path, or a new path. */ 618 extension of an existing path, or a new path. */
623 cm_ctx.cpath = cpath; 619 cm_ctx.cpath = cpath;
624 cm_ctx.cpath_length = path_length; 620 cm_ctx.cpath_length = path_length;
625 cm_ctx.match = NULL; 621 cm_ctx.match = NULL;
626 for (int i=path_length-1;i>=0;i--) 622 for (int i = path_length - 1; i >= 0; i--)
627 {
628 GCP_iterate_paths_at (cpath[i],
629 (unsigned int) i,
630 &check_match,
631 &cm_ctx);
632 if (NULL != cm_ctx.match)
633 { 623 {
634 if (i == path_length - 1) 624 GCP_iterate_paths_at(cpath[i],
635 { 625 (unsigned int)i,
636 /* Existing path includes this one, return the match! */ 626 &check_match,
637 LOG (GNUNET_ERROR_TYPE_DEBUG, 627 &cm_ctx);
638 "Returning existing path %s as inverse for incoming connection\n", 628 if (NULL != cm_ctx.match)
639 GCPP_2s (cm_ctx.match)); 629 {
640 return cm_ctx.match; 630 if (i == path_length - 1)
641 } 631 {
642 if (cm_ctx.match->entries_length == i + 1) 632 /* Existing path includes this one, return the match! */
643 { 633 LOG(GNUNET_ERROR_TYPE_DEBUG,
644 /* Existing path ends in the middle of new path, extend it! */ 634 "Returning existing path %s as inverse for incoming connection\n",
645 LOG (GNUNET_ERROR_TYPE_DEBUG, 635 GCPP_2s(cm_ctx.match));
646 "Extending existing path %s to create inverse for incoming connection\n", 636 return cm_ctx.match;
647 GCPP_2s (cm_ctx.match)); 637 }
648 extend_path (cm_ctx.match, 638 if (cm_ctx.match->entries_length == i + 1)
649 &cpath[i + 1], 639 {
650 path_length - i - 1, 640 /* Existing path ends in the middle of new path, extend it! */
651 GNUNET_YES); 641 LOG(GNUNET_ERROR_TYPE_DEBUG,
652 /* Check that extension was successful */ 642 "Extending existing path %s to create inverse for incoming connection\n",
653 GNUNET_assert (cm_ctx.match->entries_length == path_length); 643 GCPP_2s(cm_ctx.match));
654 return cm_ctx.match; 644 extend_path(cm_ctx.match,
655 } 645 &cpath[i + 1],
656 /* Eh, we found a match but couldn't use it? Something is wrong. */ 646 path_length - i - 1,
657 GNUNET_break (0); 647 GNUNET_YES);
648 /* Check that extension was successful */
649 GNUNET_assert(cm_ctx.match->entries_length == path_length);
650 return cm_ctx.match;
651 }
652 /* Eh, we found a match but couldn't use it? Something is wrong. */
653 GNUNET_break(0);
654 }
658 } 655 }
659 }
660 656
661 /* No match at all, create completely new path */ 657 /* No match at all, create completely new path */
662 path = GNUNET_new (struct CadetPeerPath); 658 path = GNUNET_new(struct CadetPeerPath);
663 path->entries_length = path_length; 659 path->entries_length = path_length;
664 path->entries = GNUNET_new_array (path->entries_length, 660 path->entries = GNUNET_new_array(path->entries_length,
665 struct CadetPeerPathEntry *); 661 struct CadetPeerPathEntry *);
666 for (int i=path_length-1;i>=0;i--) 662 for (int i = path_length - 1; i >= 0; i--)
667 { 663 {
668 struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry); 664 struct CadetPeerPathEntry *entry = GNUNET_new(struct CadetPeerPathEntry);
669 665
670 path->entries[i] = entry; 666 path->entries[i] = entry;
671 entry->peer = cpath[i]; 667 entry->peer = cpath[i];
672 entry->path = path; 668 entry->path = path;
673 } 669 }
674 for (int i=path_length-1;i>=0;i--) 670 for (int i = path_length - 1; i >= 0; i--)
675 { 671 {
676 struct CadetPeerPathEntry *entry = path->entries[i]; 672 struct CadetPeerPathEntry *entry = path->entries[i];
677 673
678 GCP_path_entry_add (entry->peer, 674 GCP_path_entry_add(entry->peer,
679 entry, 675 entry,
680 i); 676 i);
681 } 677 }
682 recalculate_path_desirability (path); 678 recalculate_path_desirability(path);
683 LOG (GNUNET_ERROR_TYPE_DEBUG, 679 LOG(GNUNET_ERROR_TYPE_DEBUG,
684 "Created new path %s to create inverse for incoming connection\n", 680 "Created new path %s to create inverse for incoming connection\n",
685 GCPP_2s (path)); 681 GCPP_2s(path));
686 path->hn = GCP_attach_path (cpath[path_length - 1], 682 path->hn = GCP_attach_path(cpath[path_length - 1],
687 path, 683 path,
688 path_length - 1, 684 path_length - 1,
689 GNUNET_YES); 685 GNUNET_YES);
690 return path; 686 return path;
691} 687}
692 688
@@ -699,7 +695,7 @@ GCPP_get_path_from_route (unsigned int path_length,
699 * @return number of peers on the path 695 * @return number of peers on the path
700 */ 696 */
701unsigned int 697unsigned int
702GCPP_get_length (struct CadetPeerPath *path) 698GCPP_get_length(struct CadetPeerPath *path)
703{ 699{
704 return path->entries_length; 700 return path->entries_length;
705} 701}
@@ -713,14 +709,14 @@ GCPP_get_length (struct CadetPeerPath *path)
713 * @return offset of @a cp on @a path, or UINT_MAX if not found 709 * @return offset of @a cp on @a path, or UINT_MAX if not found
714 */ 710 */
715unsigned int 711unsigned int
716GCPP_find_peer (struct CadetPeerPath *path, 712GCPP_find_peer(struct CadetPeerPath *path,
717 struct CadetPeer *cp) 713 struct CadetPeer *cp)
718{ 714{
719 for (unsigned int off = 0; 715 for (unsigned int off = 0;
720 off < path->entries_length; 716 off < path->entries_length;
721 off++) 717 off++)
722 if (cp == GCPP_get_peer_at_offset (path, 718 if (cp == GCPP_get_peer_at_offset(path,
723 off)) 719 off))
724 return off; 720 return off;
725 return UINT_MAX; 721 return UINT_MAX;
726} 722}
@@ -734,10 +730,10 @@ GCPP_find_peer (struct CadetPeerPath *path,
734 * @return the peer at offset @a off 730 * @return the peer at offset @a off
735 */ 731 */
736struct CadetPeer * 732struct CadetPeer *
737GCPP_get_peer_at_offset (struct CadetPeerPath *path, 733GCPP_get_peer_at_offset(struct CadetPeerPath *path,
738 unsigned int off) 734 unsigned int off)
739{ 735{
740 GNUNET_assert (off < path->entries_length); 736 GNUNET_assert(off < path->entries_length);
741 return path->entries[off]->peer; 737 return path->entries[off]->peer;
742} 738}
743 739
@@ -749,7 +745,7 @@ GCPP_get_peer_at_offset (struct CadetPeerPath *path,
749 * @return string, to be freed by caller (unlike other *_2s APIs!) 745 * @return string, to be freed by caller (unlike other *_2s APIs!)
750 */ 746 */
751const char * 747const char *
752GCPP_2s (struct CadetPeerPath *path) 748GCPP_2s(struct CadetPeerPath *path)
753{ 749{
754 static char buf[2048]; 750 static char buf[2048];
755 size_t off; 751 size_t off;
@@ -759,27 +755,27 @@ GCPP_2s (struct CadetPeerPath *path)
759 for (unsigned int i = 0; 755 for (unsigned int i = 0;
760 i < path->entries_length; 756 i < path->entries_length;
761 i++) 757 i++)
762 { 758 {
763 if ( (path->entries_length > max_plen) && 759 if ((path->entries_length > max_plen) &&
764 (i == max_plen / 2) ) 760 (i == max_plen / 2))
765 off += GNUNET_snprintf (&buf[off], 761 off += GNUNET_snprintf(&buf[off],
766 sizeof (buf) - off, 762 sizeof(buf) - off,
767 "...-"); 763 "...-");
768 if ( (path->entries_length > max_plen) && 764 if ((path->entries_length > max_plen) &&
769 (i > max_plen / 2) && 765 (i > max_plen / 2) &&
770 (i < path->entries_length - max_plen / 2) ) 766 (i < path->entries_length - max_plen / 2))
771 continue; 767 continue;
772 off += GNUNET_snprintf (&buf[off], 768 off += GNUNET_snprintf(&buf[off],
773 sizeof (buf) - off, 769 sizeof(buf) - off,
774 "%s%s", 770 "%s%s",
775 GNUNET_i2s (GCP_get_id (GCPP_get_peer_at_offset (path, 771 GNUNET_i2s(GCP_get_id(GCPP_get_peer_at_offset(path,
776 i))), 772 i))),
777 (i == path->entries_length -1) ? "" : "-"); 773 (i == path->entries_length - 1) ? "" : "-");
778 } 774 }
779 GNUNET_snprintf (&buf[off], 775 GNUNET_snprintf(&buf[off],
780 sizeof (buf) - off, 776 sizeof(buf) - off,
781 "(%p)", 777 "(%p)",
782 path); 778 path);
783 return buf; 779 return buf;
784} 780}
785 781