GNUnet  0.10.x
gnunet-service-cadet_paths.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet.
3  Copyright (C) 2001-2017 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 */
26 #include "platform.h"
31 
32 
33 #define LOG(level, ...) GNUNET_log_from(level,"cadet-pat",__VA_ARGS__)
34 
35 
40 {
41 
47 
53 
59 
63  unsigned int entries_length;
64 
65 };
66 
67 
73 static void
75 {
76  double result = 0.0;
77 
78  for (unsigned int i=0;i<path->entries_length;i++)
79  {
80  struct CadetPeer *cp = path->entries[i]->peer;
81 
82  result += GCP_get_desirability_of_path (cp,
83  i);
84  }
86 }
87 
88 
104 {
105  return path->desirability;
106 }
107 
108 
119 struct CadetConnection *
121  struct CadetPeer *destination,
122  unsigned int off)
123 {
124  struct CadetPeerPathEntry *entry;
125 
126  GNUNET_assert (off < path->entries_length);
127  entry = path->entries[off];
128  GNUNET_assert (entry->peer == destination);
129  return entry->cc;
130 }
131 
132 
141 void
143  unsigned int off,
144  struct CadetConnection *cc)
145 {
146  struct CadetPeerPathEntry *entry;
147 
149  "Adding %s to path %s at offset %u\n",
150  GCC_2s (cc),
151  GCPP_2s (path),
152  off);
153  GNUNET_assert (off < path->entries_length);
154  entry = path->entries[off];
155  GNUNET_assert (NULL == entry->cc);
156  GNUNET_assert (NULL != cc);
157  entry->cc = cc;
158 }
159 
160 
161 
170 void
172  unsigned int off,
173  struct CadetConnection *cc)
174 {
175  struct CadetPeerPathEntry *entry;
176 
178  "Removing connection %s to path %s at offset %u\n",
179  GCC_2s (cc),
180  GCPP_2s (path),
181  off);
182  GNUNET_assert (off < path->entries_length);
183  entry = path->entries[off];
184  GNUNET_assert (cc == entry->cc);
185  entry->cc = NULL;
186 }
187 
188 
198 static void
199 attach_path (struct CadetPeerPath *path, unsigned int stop_at)
200 {
201  GNUNET_assert (NULL == path->hn);
202 
203  /* Try to attach this path to a peer, working backwards from the end. */
204  while (path->entries_length > stop_at)
205  {
206  unsigned int end = path->entries_length - 1;
207  struct CadetPeerPathEntry *entry = path->entries[end];
208  int force = GNUNET_NO;
209 
211  /* If the entry already has a connection using it, force attach. */
212  if (NULL != entry->cc)
213  force = GNUNET_YES;
214  path->hn = GCP_attach_path (entry->peer,
215  path,
216  end,
217  force);
218  if (NULL != path->hn)
219  break;
220 
221  /* Attach failed, trim this entry from the path. */
222  GNUNET_assert (NULL == entry->cc);
223  GCP_path_entry_remove (entry->peer,
224  entry,
225  end);
226  GNUNET_free (entry);
227  path->entries[end] = NULL;
228  path->entries_length--;
229  }
230 
231  /* Shrink array to actual path length. */
232  GNUNET_array_grow (path->entries,
233  path->entries_length,
234  path->entries_length);
235 }
236 
237 
245 void
247 {
248  struct CadetPeerPathEntry *entry;
249 
251  "Owner releases path %s\n",
252  GCPP_2s (path));
253  path->hn = NULL;
254  entry = path->entries[path->entries_length - 1];
255  GNUNET_assert (path == entry->path);
256  GNUNET_assert (NULL == entry->cc);
257  /* cut 'off' end of path */
258  GCP_path_entry_remove (entry->peer,
259  entry,
260  path->entries_length - 1);
261  GNUNET_free (entry);
262  path->entries[path->entries_length - 1] = NULL;
263  path->entries_length--;
264  /* see if new peer at the end likes this path any better */
265  attach_path (path, 0);
266  if (NULL == path->hn)
267  {
268  /* nobody wants us, discard the path */
269  GNUNET_assert (0 == path->entries_length);
270  GNUNET_assert (NULL == path->entries);
271  GNUNET_free (path);
272  }
273 }
274 
275 
284 void
286  unsigned int off,
287  int delta)
288 {
289  struct CadetPeerPathEntry *entry;
290 
291  GNUNET_assert (off < path->entries_length);
292  entry = path->entries[off];
293 
294  /* Add delta, with checks for overflows */
295  if (delta >= 0)
296  {
297  if (delta + entry->score < entry->score)
298  entry->score = INT_MAX;
299  else
300  entry->score += delta;
301  }
302  else
303  {
304  if (delta + entry->score > entry->score)
305  entry->score = INT_MIN;
306  else
307  entry->score += delta;
308  }
310 }
311 
312 
317 {
318 
323 
327  struct CadetPeer **cpath;
328 
332  unsigned int cpath_length;
333 
334 };
335 
336 
347 static int
348 check_match (void *cls,
349  struct CadetPeerPath *path,
350  unsigned int off)
351 {
352  struct CheckMatchContext *cm_ctx = cls;
353 
354  GNUNET_assert (path->entries_length > off);
355  if ( (path->entries_length != off + 1) &&
356  (off + 1 != cm_ctx->cpath_length) )
357  {
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] !=
369  i))
370  {
372  "check_match path %s mismatches at offset %u\n",
373  GCPP_2s (path),
374  i);
375  return GNUNET_YES; /* mismatch, ignore */
376  }
378  "check_match found match with path %s\n",
379  GCPP_2s (path));
380  cm_ctx->match = path;
381  return GNUNET_NO; /* match, we are done! */
382 }
383 
384 
395 static void
397  struct CadetPeer **peers,
398  unsigned int num_peers,
399  int force)
400 {
401  unsigned int old_len = path->entries_length;
402  int i;
403 
404  /* Expand path */
405  GNUNET_array_grow (path->entries,
406  path->entries_length,
407  old_len + num_peers);
408  for (i=num_peers-1;i >= 0;i--)
409  {
410  struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
411 
412  path->entries[old_len + i] = entry;
413  entry->peer = peers[i];
414  entry->path = path;
415  }
416  for (i=num_peers-1;i >= 0;i--)
417  {
418  struct CadetPeerPathEntry *entry = path->entries[old_len + i];
419 
420  GCP_path_entry_add (entry->peer,
421  entry,
422  old_len + i);
423  }
424 
425  /* If we extend an existing path, detach it from the
426  old owner and re-attach to the new one */
427  GCP_detach_path (path->entries[old_len-1]->peer,
428  path,
429  path->hn);
430  path->hn = NULL;
431  path->entries_length = old_len + num_peers;
432  if (GNUNET_YES == force)
433  {
434  int end = path->entries_length - 1;
435 
436  path->hn = GCP_attach_path (path->entries[end]->peer,
437  path,
438  end,
439  GNUNET_YES);
440  } else {
441  attach_path (path, old_len);
442  }
443  if (NULL == path->hn)
444  {
445  /* none of the peers is interested in this path;
446  re-attach. */
447  GNUNET_assert (old_len == path->entries_length);
448  path->hn = GCP_attach_path (path->entries[old_len - 1]->peer,
449  path,
450  old_len - 1,
451  GNUNET_YES);
452  GNUNET_assert (NULL != path->hn);
453  return;
454  }
456  "Extended path %s\n",
457  GCPP_2s (path));
458 }
459 
460 
473 void
475  unsigned int get_path_length,
476  const struct GNUNET_PeerIdentity *put_path,
477  unsigned int put_path_length)
478 {
479  struct CadetPeer *cpath[get_path_length + put_path_length];
480  struct CheckMatchContext cm_ctx;
481  struct CadetPeerPath *path;
482  unsigned int skip;
483  unsigned int total_len;
484 
485  /* precompute 'cpath' so we can avoid doing the lookups lots of times */
486  skip = 0;
487  memset (cpath,
488  0,
489  sizeof (cpath)); /* Just to trigger harder errors later. */
490  total_len = get_path_length + put_path_length;
491  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  {
502  skip = off + 1;
503  continue;
504  }
505  cpath[off - skip] = GCP_get (pid,
506  GNUNET_YES);
507  /* Check that no peer is twice on the path */
508  for (unsigned int i=0;i<off - skip;i++)
509  {
510  if (cpath[i] == cpath[off - skip])
511  {
512  skip = off - i;
513  break;
514  }
515  }
516  }
517  if (skip >= total_len)
518  {
520  "Path discovered from DHT is one big cycle?\n");
521  return;
522  }
523  total_len -= skip;
524 
525  /* First figure out if this path is a subset of an existing path, an
526  extension of an existing path, or a new path. */
527  cm_ctx.cpath_length = total_len;
528  cm_ctx.cpath = cpath;
529  cm_ctx.match = NULL;
530  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  {
538  if (i == total_len - 1)
539  {
540  /* Existing path includes this one, nothing to do! */
542  "Path discovered from DHT is already known\n");
543  return;
544  }
545  if (cm_ctx.match->entries_length == i + 1)
546  {
547  /* Existing path ends in the middle of new path, extend it! */
549  "Trying to extend existing path %s by additional links discovered from DHT\n",
550  GCPP_2s (cm_ctx.match));
551  extend_path (cm_ctx.match,
552  &cpath[i + 1],
553  total_len - i - 1,
554  GNUNET_NO);
555  return;
556  }
557  }
558  }
559 
560  /* No match at all, create completely new path */
561  path = GNUNET_new (struct CadetPeerPath);
562  path->entries_length = total_len;
563  path->entries = GNUNET_new_array (path->entries_length,
564  struct CadetPeerPathEntry *);
565  for (int i=path->entries_length-1;i>=0;i--)
566  {
567  struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
568 
569  path->entries[i] = entry;
570  entry->peer = cpath[i];
571  entry->path = path;
572  }
573  for (int i=path->entries_length-1;i>=0;i--)
574  {
575  struct CadetPeerPathEntry *entry = path->entries[i];
576 
577  GCP_path_entry_add (entry->peer,
578  entry,
579  i);
580  }
581 
582  /* Finally, try to attach it */
583  attach_path (path, 0);
584  if (NULL == path->hn)
585  {
586  /* None of the peers on the path care about it. */
588  "Path discovered from DHT is not interesting to us\n");
589  GNUNET_assert (0 == path->entries_length);
590  GNUNET_assert (NULL == path->entries);
591  GNUNET_free (path);
592  return;
593  }
595  "Created new path %s based on information from DHT\n",
596  GCPP_2s (path));
597 }
598 
599 
607 struct CadetPeerPath *
608 GCPP_get_path_from_route (unsigned int path_length,
609  const struct GNUNET_PeerIdentity *pids)
610 {
611  struct CheckMatchContext cm_ctx;
612  struct CadetPeer *cpath[path_length];
613  struct CadetPeerPath *path;
614 
615  /* precompute inverted 'cpath' so we can avoid doing the lookups and
616  have the correct order */
617  for (unsigned int off=0;off<path_length;off++)
618  cpath[off] = GCP_get (&pids[path_length - 1 - off],
619  GNUNET_YES);
620 
621  /* First figure out if this path is a subset of an existing path, an
622  extension of an existing path, or a new path. */
623  cm_ctx.cpath = cpath;
624  cm_ctx.cpath_length = path_length;
625  cm_ctx.match = NULL;
626  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  {
634  if (i == path_length - 1)
635  {
636  /* Existing path includes this one, return the match! */
638  "Returning existing path %s as inverse for incoming connection\n",
639  GCPP_2s (cm_ctx.match));
640  return cm_ctx.match;
641  }
642  if (cm_ctx.match->entries_length == i + 1)
643  {
644  /* Existing path ends in the middle of new path, extend it! */
646  "Extending existing path %s to create inverse for incoming connection\n",
647  GCPP_2s (cm_ctx.match));
648  extend_path (cm_ctx.match,
649  &cpath[i + 1],
650  path_length - i - 1,
651  GNUNET_YES);
652  /* Check that extension was successful */
653  GNUNET_assert (cm_ctx.match->entries_length == path_length);
654  return cm_ctx.match;
655  }
656  /* Eh, we found a match but couldn't use it? Something is wrong. */
657  GNUNET_break (0);
658  }
659  }
660 
661  /* No match at all, create completely new path */
662  path = GNUNET_new (struct CadetPeerPath);
663  path->entries_length = path_length;
664  path->entries = GNUNET_new_array (path->entries_length,
665  struct CadetPeerPathEntry *);
666  for (int i=path_length-1;i>=0;i--)
667  {
668  struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
669 
670  path->entries[i] = entry;
671  entry->peer = cpath[i];
672  entry->path = path;
673  }
674  for (int i=path_length-1;i>=0;i--)
675  {
676  struct CadetPeerPathEntry *entry = path->entries[i];
677 
678  GCP_path_entry_add (entry->peer,
679  entry,
680  i);
681  }
684  "Created new path %s to create inverse for incoming connection\n",
685  GCPP_2s (path));
686  path->hn = GCP_attach_path (cpath[path_length - 1],
687  path,
688  path_length - 1,
689  GNUNET_YES);
690  return path;
691 }
692 
693 
701 unsigned int
703 {
704  return path->entries_length;
705 }
706 
707 
715 unsigned int
717  struct CadetPeer *cp)
718 {
719  for (unsigned int off = 0;
720  off < path->entries_length;
721  off++)
722  if (cp == GCPP_get_peer_at_offset (path,
723  off))
724  return off;
725  return UINT_MAX;
726 }
727 
728 
736 struct CadetPeer *
738  unsigned int off)
739 {
740  GNUNET_assert (off < path->entries_length);
741  return path->entries[off]->peer;
742 }
743 
744 
751 const char *
752 GCPP_2s (struct CadetPeerPath *path)
753 {
754  static char buf[2048];
755  size_t off;
756  const unsigned int max_plen = (sizeof(buf) - 16) / 5 - 2; /* 5 characters per entry */
757 
758  off = 0;
759  for (unsigned int i = 0;
760  i < path->entries_length;
761  i++)
762  {
763  if ( (path->entries_length > max_plen) &&
764  (i == max_plen / 2) )
765  off += GNUNET_snprintf (&buf[off],
766  sizeof (buf) - off,
767  "...-");
768  if ( (path->entries_length > max_plen) &&
769  (i > max_plen / 2) &&
770  (i < path->entries_length - max_plen / 2) )
771  continue;
772  off += GNUNET_snprintf (&buf[off],
773  sizeof (buf) - off,
774  "%s%s",
776  i))),
777  (i == path->entries_length -1) ? "" : "-");
778  }
779  GNUNET_snprintf (&buf[off],
780  sizeof (buf) - off,
781  "(%p)",
782  path);
783  return buf;
784 }
785 
786 
787 /* end of gnunet-service-cadet-new_paths.c */
struct GNUNET_CONTAINER_HeapNode * hn
Node of this path in the owner&#39;s heap.
Peer description.
Low-level connection to a destination.
static struct GNUNET_TIME_Relative delta
Definition: speedup.c:35
static void recalculate_path_desirability(struct CadetPeerPath *path)
Calculate the path&#39;s desirability score.
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
struct CadetPeer * peer
The peer at this offset of the path.
A connection is a live end-to-end messaging mechanism where the peers are identified by a path and kn...
struct CadetConnection * cc
Connection using this path, or NULL for none.
int GNUNET_snprintf(char *buf, size_t size, const char *format,...)
Like snprintf, just aborts if the buffer is of insufficient size.
const char * GCC_2s(const struct CadetConnection *cc)
Get a (static) string for a connection.
struct GNUNET_PeerIdentity my_full_id
Local peer own ID.
Entry in a peer path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static void extend_path(struct CadetPeerPath *path, struct CadetPeer **peers, unsigned int num_peers, int force)
Extend path path by the num_peers from the peers array, assuming the owners past the current owner wa...
struct CadetPeerPath * path
Path we are using to our destination.
struct CadetPeer * destination
To which peer does this connection go?
struct CadetPeer ** cpath
Array the combined paths.
#define GNUNET_NO
Definition: gnunet_common.h:81
struct GNUNET_CONTAINER_HeapNode * GCP_attach_path(struct CadetPeer *cp, struct CadetPeerPath *path, unsigned int off, int force)
Try adding a path to this peer.
Information we track per tunnel.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
void GCPP_try_path_from_dht(const struct GNUNET_PeerIdentity *get_path, unsigned int get_path_length, const struct GNUNET_PeerIdentity *put_path, unsigned int put_path_length)
Create a peer path based on the result of a DHT lookup.
void GCPP_update_score(struct CadetPeerPath *path, unsigned int off, int delta)
Updates the score for an entry on the path based on our experiences with using path.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
struct CadetPeerPath * match
Set to a matching path, if any.
void GCP_path_entry_remove(struct CadetPeer *cp, struct CadetPeerPathEntry *entry, unsigned int off)
Remove an entry from the DLL of all of the paths that this peer is on.
const char * GCPP_2s(struct CadetPeerPath *path)
Convert a path to a human-readable string.
#define INT_MAX
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
Information we track per peer.
struct CadetPeerPath * GCPP_get_path_from_route(unsigned int path_length, const struct GNUNET_PeerIdentity *pids)
We got an incoming connection, obtain the corresponding path.
static void attach_path(struct CadetPeerPath *path, unsigned int stop_at)
Tries to attach path to a peer, working backwards from the end and stopping at stop_at.
struct CadetPeerPath * path
Path this entry belongs to.
static int check_match(void *cls, struct CadetPeerPath *path, unsigned int off)
Check if the given path is identical on all of the hops until off, and not longer than off...
static char buf[2048]
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
static int result
Global testing status.
#define LOG(level,...)
int score
Path&#39;s historic score up to this point.
Node in the heap.
GNUNET_CONTAINER_HeapCostType desirability
Desirability of the path.
unsigned int cpath_length
How long is the cpath array?
uint64_t GNUNET_CONTAINER_HeapCostType
Cost by which elements in a heap can be ordered.
GNUNET_CONTAINER_HeapCostType GCPP_get_desirability(const struct CadetPeerPath *path)
Return how much we like keeping the path.
static unsigned int num_peers
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
unsigned int GCP_iterate_paths_at(struct CadetPeer *cp, unsigned int dist, GCP_PathIterator callback, void *callback_cls)
Iterate over the paths to cp where cp is at distance dist from us.
void GCP_path_entry_add(struct CadetPeer *cp, struct CadetPeerPathEntry *entry, unsigned int off)
Add an entry to the DLL of all of the paths that this peer is on.
unsigned int GCPP_find_peer(struct CadetPeerPath *path, struct CadetPeer *cp)
Find peer&#39;s offset on path.
The identity of the host (wraps the signing key of the peer).
struct CadetPeer * GCP_get(const struct GNUNET_PeerIdentity *peer_id, int create)
Retrieve the CadetPeer stucture associated with the peer.
void GCPP_del_connection(struct CadetPeerPath *path, unsigned int off, struct CadetConnection *cc)
Notify path that it is no longer used for connection cc which ended at the path&#39;s offset off...
static struct CadetPeer * peers
Operation to get peer ids.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
void GCP_detach_path(struct CadetPeer *cp, struct CadetPeerPath *path, struct GNUNET_CONTAINER_HeapNode *hn)
This peer can no longer own path as the path has been extended and a peer further down the line is no...
double GCP_get_desirability_of_path(struct CadetPeer *cp, unsigned int off)
Calculate how desirable a path is for cp if cp is at offset off.
struct CadetConnection * GCPP_get_connection(struct CadetPeerPath *path, struct CadetPeer *destination, unsigned int off)
Return connection to destination using path, or return NULL if no such connection exists...
struct CadetPeer * GCPP_get_peer_at_offset(struct CadetPeerPath *path, unsigned int off)
Obtain the peer at offset off in path.
#define GNUNET_YES
Definition: gnunet_common.h:80
unsigned int entries_length
Length of the entries array.
static struct GNUNET_PeerIdentity pid
Identity of the peer we transmit to / connect to.
Closure for #find_peer_at() and check_match().
Information regarding a possible path to reach a peer.
void GCPP_add_connection(struct CadetPeerPath *path, unsigned int off, struct CadetConnection *cc)
Notify path that it is used for connection cc which ends at the path&#39;s offset off.
unsigned int GCPP_get_length(struct CadetPeerPath *path)
Return the length of the path.
const char * GNUNET_i2s(const struct GNUNET_PeerIdentity *pid)
Convert a peer identity to a string (for printing debug messages).
#define GNUNET_free(ptr)
Wrapper around free.
const struct GNUNET_PeerIdentity * GCP_get_id(struct CadetPeer *cp)
Obtain the peer identity for a struct CadetPeer.
void GCPP_release(struct CadetPeerPath *path)
The owning peer of this path is no longer interested in maintaining it, so the path should be discard...
unsigned int off
Offset of our destination in path.